clang-tools  9.0.0svn
CodeComplete.cpp
Go to the documentation of this file.
1 //===--- CodeComplete.cpp ----------------------------------------*- C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Code completion has several moving parts:
10 // - AST-based completions are provided using the completion hooks in Sema.
11 // - external completions are retrieved from the index (using hints from Sema)
12 // - the two sources overlap, and must be merged and overloads bundled
13 // - results must be scored and ranked (see Quality.h) before rendering
14 //
15 // Signature help works in a similar way as code completion, but it is simpler:
16 // it's purely AST-based, and there are few candidates.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "CodeComplete.h"
21 #include "AST.h"
22 #include "ClangdUnit.h"
23 #include "CodeCompletionStrings.h"
24 #include "Compiler.h"
25 #include "Diagnostics.h"
26 #include "ExpectedTypes.h"
27 #include "FileDistance.h"
28 #include "FuzzyMatch.h"
29 #include "Headers.h"
30 #include "Logger.h"
31 #include "Protocol.h"
32 #include "Quality.h"
33 #include "SourceCode.h"
34 #include "TUScheduler.h"
35 #include "Trace.h"
36 #include "URI.h"
37 #include "index/Index.h"
38 #include "index/Symbol.h"
39 #include "index/SymbolOrigin.h"
40 #include "clang/AST/Decl.h"
41 #include "clang/AST/DeclBase.h"
42 #include "clang/Basic/CharInfo.h"
43 #include "clang/Basic/LangOptions.h"
44 #include "clang/Basic/SourceLocation.h"
45 #include "clang/Format/Format.h"
46 #include "clang/Frontend/CompilerInstance.h"
47 #include "clang/Frontend/FrontendActions.h"
48 #include "clang/Lex/ExternalPreprocessorSource.h"
49 #include "clang/Lex/Preprocessor.h"
50 #include "clang/Lex/PreprocessorOptions.h"
51 #include "clang/Sema/CodeCompleteConsumer.h"
52 #include "clang/Sema/DeclSpec.h"
53 #include "clang/Sema/Sema.h"
54 #include "llvm/ADT/ArrayRef.h"
55 #include "llvm/ADT/None.h"
56 #include "llvm/ADT/Optional.h"
57 #include "llvm/ADT/SmallVector.h"
58 #include "llvm/ADT/StringExtras.h"
59 #include "llvm/ADT/StringRef.h"
60 #include "llvm/Support/Compiler.h"
61 #include "llvm/Support/Debug.h"
62 #include "llvm/Support/Error.h"
63 #include "llvm/Support/Format.h"
64 #include "llvm/Support/FormatVariadic.h"
65 #include "llvm/Support/ScopedPrinter.h"
66 #include <algorithm>
67 #include <iterator>
68 
69 // We log detailed candidate here if you run with -debug-only=codecomplete.
70 #define DEBUG_TYPE "CodeComplete"
71 
72 namespace clang {
73 namespace clangd {
74 namespace {
75 
76 CompletionItemKind toCompletionItemKind(index::SymbolKind Kind) {
77  using SK = index::SymbolKind;
78  switch (Kind) {
79  case SK::Unknown:
81  case SK::Module:
82  case SK::Namespace:
83  case SK::NamespaceAlias:
85  case SK::Macro:
87  case SK::Enum:
89  // FIXME(ioeric): use LSP struct instead of class when it is suppoted in the
90  // protocol.
91  case SK::Struct:
92  case SK::Class:
93  case SK::Protocol:
94  case SK::Extension:
95  case SK::Union:
97  case SK::TypeAlias:
98  // We use the same kind as the VSCode C++ extension.
99  // FIXME: pick a better option when we have one.
101  case SK::Using:
103  case SK::Function:
104  // FIXME(ioeric): this should probably be an operator. This should be fixed
105  // when `Operator` is support type in the protocol.
106  case SK::ConversionFunction:
108  case SK::Variable:
109  case SK::Parameter:
111  case SK::Field:
113  // FIXME(ioeric): use LSP enum constant when it is supported in the protocol.
114  case SK::EnumConstant:
116  case SK::InstanceMethod:
117  case SK::ClassMethod:
118  case SK::StaticMethod:
119  case SK::Destructor:
121  case SK::InstanceProperty:
122  case SK::ClassProperty:
123  case SK::StaticProperty:
125  case SK::Constructor:
127  }
128  llvm_unreachable("Unhandled clang::index::SymbolKind.");
129 }
130 
132 toCompletionItemKind(CodeCompletionResult::ResultKind ResKind,
133  const NamedDecl *Decl,
134  CodeCompletionContext::Kind CtxKind) {
135  if (Decl)
136  return toCompletionItemKind(index::getSymbolInfo(Decl).Kind);
137  if (CtxKind == CodeCompletionContext::CCC_IncludedFile)
139  switch (ResKind) {
140  case CodeCompletionResult::RK_Declaration:
141  llvm_unreachable("RK_Declaration without Decl");
142  case CodeCompletionResult::RK_Keyword:
144  case CodeCompletionResult::RK_Macro:
145  return CompletionItemKind::Text; // unfortunately, there's no 'Macro'
146  // completion items in LSP.
147  case CodeCompletionResult::RK_Pattern:
149  }
150  llvm_unreachable("Unhandled CodeCompletionResult::ResultKind.");
151 }
152 
153 // Identifier code completion result.
154 struct RawIdentifier {
155  llvm::StringRef Name;
156  unsigned References; // # of usages in file.
157 };
158 
159 /// A code completion result, in clang-native form.
160 /// It may be promoted to a CompletionItem if it's among the top-ranked results.
161 struct CompletionCandidate {
162  llvm::StringRef Name; // Used for filtering and sorting.
163  // We may have a result from Sema, from the index, or both.
164  const CodeCompletionResult *SemaResult = nullptr;
165  const Symbol *IndexResult = nullptr;
166  const RawIdentifier *IdentifierResult = nullptr;
167  llvm::SmallVector<llvm::StringRef, 1> RankedIncludeHeaders;
168 
169  // Returns a token identifying the overload set this is part of.
170  // 0 indicates it's not part of any overload set.
171  size_t overloadSet(const CodeCompleteOptions &Opts) const {
172  if (!Opts.BundleOverloads.getValueOr(false))
173  return 0;
174  llvm::SmallString<256> Scratch;
175  if (IndexResult) {
176  switch (IndexResult->SymInfo.Kind) {
177  case index::SymbolKind::ClassMethod:
178  case index::SymbolKind::InstanceMethod:
179  case index::SymbolKind::StaticMethod:
180 #ifndef NDEBUG
181  llvm_unreachable("Don't expect members from index in code completion");
182 #else
183  LLVM_FALLTHROUGH;
184 #endif
185  case index::SymbolKind::Function:
186  // We can't group overloads together that need different #includes.
187  // This could break #include insertion.
188  return llvm::hash_combine(
189  (IndexResult->Scope + IndexResult->Name).toStringRef(Scratch),
190  headerToInsertIfAllowed(Opts).getValueOr(""));
191  default:
192  return 0;
193  }
194  }
195  if (SemaResult) {
196  // We need to make sure we're consistent with the IndexResult case!
197  const NamedDecl *D = SemaResult->Declaration;
198  if (!D || !D->isFunctionOrFunctionTemplate())
199  return 0;
200  {
201  llvm::raw_svector_ostream OS(Scratch);
202  D->printQualifiedName(OS);
203  }
204  return llvm::hash_combine(Scratch,
205  headerToInsertIfAllowed(Opts).getValueOr(""));
206  }
207  assert(IdentifierResult);
208  return 0;
209  }
210 
211  // The best header to include if include insertion is allowed.
212  llvm::Optional<llvm::StringRef>
213  headerToInsertIfAllowed(const CodeCompleteOptions &Opts) const {
214  if (Opts.InsertIncludes == CodeCompleteOptions::NeverInsert ||
215  RankedIncludeHeaders.empty())
216  return None;
217  if (SemaResult && SemaResult->Declaration) {
218  // Avoid inserting new #include if the declaration is found in the current
219  // file e.g. the symbol is forward declared.
220  auto &SM = SemaResult->Declaration->getASTContext().getSourceManager();
221  for (const Decl *RD : SemaResult->Declaration->redecls())
222  if (SM.isInMainFile(SM.getExpansionLoc(RD->getBeginLoc())))
223  return None;
224  }
225  return RankedIncludeHeaders[0];
226  }
227 
228  using Bundle = llvm::SmallVector<CompletionCandidate, 4>;
229 };
230 using ScoredBundle =
231  std::pair<CompletionCandidate::Bundle, CodeCompletion::Scores>;
232 struct ScoredBundleGreater {
233  bool operator()(const ScoredBundle &L, const ScoredBundle &R) {
234  if (L.second.Total != R.second.Total)
235  return L.second.Total > R.second.Total;
236  return L.first.front().Name <
237  R.first.front().Name; // Earlier name is better.
238  }
239 };
240 
241 // Assembles a code completion out of a bundle of >=1 completion candidates.
242 // Many of the expensive strings are only computed at this point, once we know
243 // the candidate bundle is going to be returned.
244 //
245 // Many fields are the same for all candidates in a bundle (e.g. name), and are
246 // computed from the first candidate, in the constructor.
247 // Others vary per candidate, so add() must be called for remaining candidates.
248 struct CodeCompletionBuilder {
249  CodeCompletionBuilder(ASTContext *ASTCtx, const CompletionCandidate &C,
250  CodeCompletionString *SemaCCS,
251  llvm::ArrayRef<std::string> QueryScopes,
252  const IncludeInserter &Includes,
253  llvm::StringRef FileName,
254  CodeCompletionContext::Kind ContextKind,
255  const CodeCompleteOptions &Opts)
256  : ASTCtx(ASTCtx), ExtractDocumentation(Opts.IncludeComments),
257  EnableFunctionArgSnippets(Opts.EnableFunctionArgSnippets) {
258  add(C, SemaCCS);
259  if (C.SemaResult) {
260  assert(ASTCtx);
261  Completion.Origin |= SymbolOrigin::AST;
262  Completion.Name = llvm::StringRef(SemaCCS->getTypedText());
263  if (Completion.Scope.empty()) {
264  if ((C.SemaResult->Kind == CodeCompletionResult::RK_Declaration) ||
265  (C.SemaResult->Kind == CodeCompletionResult::RK_Pattern))
266  if (const auto *D = C.SemaResult->getDeclaration())
267  if (const auto *ND = dyn_cast<NamedDecl>(D))
268  Completion.Scope =
270  }
271  Completion.Kind = toCompletionItemKind(
272  C.SemaResult->Kind, C.SemaResult->Declaration, ContextKind);
273  // Sema could provide more info on whether the completion was a file or
274  // folder.
275  if (Completion.Kind == CompletionItemKind::File &&
276  Completion.Name.back() == '/')
277  Completion.Kind = CompletionItemKind::Folder;
278  for (const auto &FixIt : C.SemaResult->FixIts) {
279  Completion.FixIts.push_back(toTextEdit(
280  FixIt, ASTCtx->getSourceManager(), ASTCtx->getLangOpts()));
281  }
282  llvm::sort(Completion.FixIts, [](const TextEdit &X, const TextEdit &Y) {
283  return std::tie(X.range.start.line, X.range.start.character) <
284  std::tie(Y.range.start.line, Y.range.start.character);
285  });
286  Completion.Deprecated |=
287  (C.SemaResult->Availability == CXAvailability_Deprecated);
288  }
289  if (C.IndexResult) {
290  Completion.Origin |= C.IndexResult->Origin;
291  if (Completion.Scope.empty())
292  Completion.Scope = C.IndexResult->Scope;
293  if (Completion.Kind == CompletionItemKind::Missing)
294  Completion.Kind = toCompletionItemKind(C.IndexResult->SymInfo.Kind);
295  if (Completion.Name.empty())
296  Completion.Name = C.IndexResult->Name;
297  // If the completion was visible to Sema, no qualifier is needed. This
298  // avoids unneeded qualifiers in cases like with `using ns::X`.
299  if (Completion.RequiredQualifier.empty() && !C.SemaResult) {
300  llvm::StringRef ShortestQualifier = C.IndexResult->Scope;
301  for (llvm::StringRef Scope : QueryScopes) {
302  llvm::StringRef Qualifier = C.IndexResult->Scope;
303  if (Qualifier.consume_front(Scope) &&
304  Qualifier.size() < ShortestQualifier.size())
305  ShortestQualifier = Qualifier;
306  }
307  Completion.RequiredQualifier = ShortestQualifier;
308  }
309  Completion.Deprecated |= (C.IndexResult->Flags & Symbol::Deprecated);
310  }
311  if (C.IdentifierResult) {
312  Completion.Origin |= SymbolOrigin::Identifier;
313  Completion.Kind = CompletionItemKind::Text;
314  Completion.Name = C.IdentifierResult->Name;
315  }
316 
317  // Turn absolute path into a literal string that can be #included.
318  auto Inserted = [&](llvm::StringRef Header)
319  -> llvm::Expected<std::pair<std::string, bool>> {
320  auto DeclaringURI =
321  URI::parse(C.IndexResult->CanonicalDeclaration.FileURI);
322  if (!DeclaringURI)
323  return DeclaringURI.takeError();
324  auto ResolvedDeclaring = URI::resolve(*DeclaringURI, FileName);
325  if (!ResolvedDeclaring)
326  return ResolvedDeclaring.takeError();
327  auto ResolvedInserted = toHeaderFile(Header, FileName);
328  if (!ResolvedInserted)
329  return ResolvedInserted.takeError();
330  auto Spelled = Includes.calculateIncludePath(*ResolvedInserted, FileName);
331  if (!Spelled)
332  return llvm::createStringError(llvm::inconvertibleErrorCode(),
333  "Header not on include path");
334  return std::make_pair(
335  std::move(*Spelled),
336  Includes.shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
337  };
338  bool ShouldInsert = C.headerToInsertIfAllowed(Opts).hasValue();
339  // Calculate include paths and edits for all possible headers.
340  for (const auto &Inc : C.RankedIncludeHeaders) {
341  if (auto ToInclude = Inserted(Inc)) {
342  CodeCompletion::IncludeCandidate Include;
343  Include.Header = ToInclude->first;
344  if (ToInclude->second && ShouldInsert)
345  Include.Insertion = Includes.insert(ToInclude->first);
346  Completion.Includes.push_back(std::move(Include));
347  } else
348  log("Failed to generate include insertion edits for adding header "
349  "(FileURI='{0}', IncludeHeader='{1}') into {2}: {3}",
350  C.IndexResult->CanonicalDeclaration.FileURI, Inc, FileName,
351  ToInclude.takeError());
352  }
353  // Prefer includes that do not need edits (i.e. already exist).
354  std::stable_partition(Completion.Includes.begin(),
355  Completion.Includes.end(),
356  [](const CodeCompletion::IncludeCandidate &I) {
357  return !I.Insertion.hasValue();
358  });
359  }
360 
361  void add(const CompletionCandidate &C, CodeCompletionString *SemaCCS) {
362  assert(bool(C.SemaResult) == bool(SemaCCS));
363  Bundled.emplace_back();
364  BundledEntry &S = Bundled.back();
365  if (C.SemaResult) {
366  bool IsPattern = C.SemaResult->Kind == CodeCompletionResult::RK_Pattern;
367  getSignature(*SemaCCS, &S.Signature, &S.SnippetSuffix,
368  &Completion.RequiredQualifier, IsPattern);
369  S.ReturnType = getReturnType(*SemaCCS);
370  } else if (C.IndexResult) {
371  S.Signature = C.IndexResult->Signature;
372  S.SnippetSuffix = C.IndexResult->CompletionSnippetSuffix;
373  S.ReturnType = C.IndexResult->ReturnType;
374  }
375  if (ExtractDocumentation && Completion.Documentation.empty()) {
376  if (C.IndexResult)
377  Completion.Documentation = C.IndexResult->Documentation;
378  else if (C.SemaResult)
379  Completion.Documentation = getDocComment(*ASTCtx, *C.SemaResult,
380  /*CommentsFromHeader=*/false);
381  }
382  }
383 
384  CodeCompletion build() {
385  Completion.ReturnType = summarizeReturnType();
386  Completion.Signature = summarizeSignature();
387  Completion.SnippetSuffix = summarizeSnippet();
388  Completion.BundleSize = Bundled.size();
389  return std::move(Completion);
390  }
391 
392 private:
393  struct BundledEntry {
394  std::string SnippetSuffix;
395  std::string Signature;
396  std::string ReturnType;
397  };
398 
399  // If all BundledEntrys have the same value for a property, return it.
400  template <std::string BundledEntry::*Member>
401  const std::string *onlyValue() const {
402  auto B = Bundled.begin(), E = Bundled.end();
403  for (auto I = B + 1; I != E; ++I)
404  if (I->*Member != B->*Member)
405  return nullptr;
406  return &(B->*Member);
407  }
408 
409  template <bool BundledEntry::*Member> const bool *onlyValue() const {
410  auto B = Bundled.begin(), E = Bundled.end();
411  for (auto I = B + 1; I != E; ++I)
412  if (I->*Member != B->*Member)
413  return nullptr;
414  return &(B->*Member);
415  }
416 
417  std::string summarizeReturnType() const {
418  if (auto *RT = onlyValue<&BundledEntry::ReturnType>())
419  return *RT;
420  return "";
421  }
422 
423  std::string summarizeSnippet() const {
424  auto *Snippet = onlyValue<&BundledEntry::SnippetSuffix>();
425  if (!Snippet)
426  // All bundles are function calls.
427  // FIXME(ibiryukov): sometimes add template arguments to a snippet, e.g.
428  // we need to complete 'forward<$1>($0)'.
429  return "($0)";
431  return *Snippet;
432 
433  // Replace argument snippets with a simplified pattern.
434  if (Snippet->empty())
435  return "";
436  if (Completion.Kind == CompletionItemKind::Function ||
437  Completion.Kind == CompletionItemKind::Method) {
438  // Functions snippets can be of 2 types:
439  // - containing only function arguments, e.g.
440  // foo(${1:int p1}, ${2:int p2});
441  // We transform this pattern to '($0)' or '()'.
442  // - template arguments and function arguments, e.g.
443  // foo<${1:class}>(${2:int p1}).
444  // We transform this pattern to '<$1>()$0' or '<$0>()'.
445 
446  bool EmptyArgs = llvm::StringRef(*Snippet).endswith("()");
447  if (Snippet->front() == '<')
448  return EmptyArgs ? "<$1>()$0" : "<$1>($0)";
449  if (Snippet->front() == '(')
450  return EmptyArgs ? "()" : "($0)";
451  return *Snippet; // Not an arg snippet?
452  }
453  // 'CompletionItemKind::Interface' matches template type aliases.
454  if (Completion.Kind == CompletionItemKind::Interface ||
455  Completion.Kind == CompletionItemKind::Class) {
456  if (Snippet->front() != '<')
457  return *Snippet; // Not an arg snippet?
458 
459  // Classes and template using aliases can only have template arguments,
460  // e.g. Foo<${1:class}>.
461  if (llvm::StringRef(*Snippet).endswith("<>"))
462  return "<>"; // can happen with defaulted template arguments.
463  return "<$0>";
464  }
465  return *Snippet;
466  }
467 
468  std::string summarizeSignature() const {
469  if (auto *Signature = onlyValue<&BundledEntry::Signature>())
470  return *Signature;
471  // All bundles are function calls.
472  return "(…)";
473  }
474 
475  // ASTCtx can be nullptr if not run with sema.
476  ASTContext *ASTCtx;
477  CodeCompletion Completion;
478  llvm::SmallVector<BundledEntry, 1> Bundled;
479  bool ExtractDocumentation;
481 };
482 
483 // Determine the symbol ID for a Sema code completion result, if possible.
484 llvm::Optional<SymbolID> getSymbolID(const CodeCompletionResult &R,
485  const SourceManager &SM) {
486  switch (R.Kind) {
487  case CodeCompletionResult::RK_Declaration:
488  case CodeCompletionResult::RK_Pattern: {
489  return clang::clangd::getSymbolID(R.Declaration);
490  }
491  case CodeCompletionResult::RK_Macro:
492  return clang::clangd::getSymbolID(*R.Macro, R.MacroDefInfo, SM);
493  case CodeCompletionResult::RK_Keyword:
494  return None;
495  }
496  llvm_unreachable("unknown CodeCompletionResult kind");
497 }
498 
499 // Scopes of the paritial identifier we're trying to complete.
500 // It is used when we query the index for more completion results.
501 struct SpecifiedScope {
502  // The scopes we should look in, determined by Sema.
503  //
504  // If the qualifier was fully resolved, we look for completions in these
505  // scopes; if there is an unresolved part of the qualifier, it should be
506  // resolved within these scopes.
507  //
508  // Examples of qualified completion:
509  //
510  // "::vec" => {""}
511  // "using namespace std; ::vec^" => {"", "std::"}
512  // "namespace ns {using namespace std;} ns::^" => {"ns::", "std::"}
513  // "std::vec^" => {""} // "std" unresolved
514  //
515  // Examples of unqualified completion:
516  //
517  // "vec^" => {""}
518  // "using namespace std; vec^" => {"", "std::"}
519  // "using namespace std; namespace ns { vec^ }" => {"ns::", "std::", ""}
520  //
521  // "" for global namespace, "ns::" for normal namespace.
522  std::vector<std::string> AccessibleScopes;
523  // The full scope qualifier as typed by the user (without the leading "::").
524  // Set if the qualifier is not fully resolved by Sema.
525  llvm::Optional<std::string> UnresolvedQualifier;
526 
527  // Construct scopes being queried in indexes. The results are deduplicated.
528  // This method format the scopes to match the index request representation.
529  std::vector<std::string> scopesForIndexQuery() {
530  std::set<std::string> Results;
531  for (llvm::StringRef AS : AccessibleScopes)
532  Results.insert(
533  (AS + (UnresolvedQualifier ? *UnresolvedQualifier : "")).str());
534  return {Results.begin(), Results.end()};
535  }
536 };
537 
538 // Get all scopes that will be queried in indexes and whether symbols from
539 // any scope is allowed. The first scope in the list is the preferred scope
540 // (e.g. enclosing namespace).
541 std::pair<std::vector<std::string>, bool>
542 getQueryScopes(CodeCompletionContext &CCContext, const Sema &CCSema,
543  const CompletionPrefix &HeuristicPrefix,
544  const CodeCompleteOptions &Opts) {
545  SpecifiedScope Scopes;
546  for (auto *Context : CCContext.getVisitedContexts()) {
547  if (isa<TranslationUnitDecl>(Context))
548  Scopes.AccessibleScopes.push_back(""); // global namespace
549  else if (isa<NamespaceDecl>(Context))
550  Scopes.AccessibleScopes.push_back(printNamespaceScope(*Context));
551  }
552 
553  const CXXScopeSpec *SemaSpecifier =
554  CCContext.getCXXScopeSpecifier().getValueOr(nullptr);
555  // Case 1: unqualified completion.
556  if (!SemaSpecifier) {
557  // Case 2 (exception): sema saw no qualifier, but there appears to be one!
558  // This can happen e.g. in incomplete macro expansions. Use heuristics.
559  if (!HeuristicPrefix.Qualifier.empty()) {
560  vlog("Sema said no scope specifier, but we saw {0} in the source code",
561  HeuristicPrefix.Qualifier);
562  StringRef SpelledSpecifier = HeuristicPrefix.Qualifier;
563  if (SpelledSpecifier.consume_front("::"))
564  Scopes.AccessibleScopes = {""};
565  Scopes.UnresolvedQualifier = SpelledSpecifier;
566  return {Scopes.scopesForIndexQuery(), false};
567  }
568  // The enclosing namespace must be first, it gets a quality boost.
569  std::vector<std::string> EnclosingAtFront;
570  std::string EnclosingScope = printNamespaceScope(*CCSema.CurContext);
571  EnclosingAtFront.push_back(EnclosingScope);
572  for (auto &S : Scopes.scopesForIndexQuery()) {
573  if (EnclosingScope != S)
574  EnclosingAtFront.push_back(std::move(S));
575  }
576  // Allow AllScopes completion as there is no explicit scope qualifier.
577  return {EnclosingAtFront, Opts.AllScopes};
578  }
579  // Case 3: sema saw and resolved a scope qualifier.
580  if (SemaSpecifier && SemaSpecifier->isValid())
581  return {Scopes.scopesForIndexQuery(), false};
582 
583  // Case 4: There was a qualifier, and Sema didn't resolve it.
584  Scopes.AccessibleScopes.push_back(""); // Make sure global scope is included.
585  llvm::StringRef SpelledSpecifier = Lexer::getSourceText(
586  CharSourceRange::getCharRange(SemaSpecifier->getRange()),
587  CCSema.SourceMgr, clang::LangOptions());
588  if (SpelledSpecifier.consume_front("::"))
589  Scopes.AccessibleScopes = {""};
590  Scopes.UnresolvedQualifier = SpelledSpecifier;
591  // Sema excludes the trailing "::".
592  if (!Scopes.UnresolvedQualifier->empty())
593  *Scopes.UnresolvedQualifier += "::";
594 
595  return {Scopes.scopesForIndexQuery(), false};
596 }
597 
598 // Should we perform index-based completion in a context of the specified kind?
599 // FIXME: consider allowing completion, but restricting the result types.
600 bool contextAllowsIndex(enum CodeCompletionContext::Kind K) {
601  switch (K) {
602  case CodeCompletionContext::CCC_TopLevel:
603  case CodeCompletionContext::CCC_ObjCInterface:
604  case CodeCompletionContext::CCC_ObjCImplementation:
605  case CodeCompletionContext::CCC_ObjCIvarList:
606  case CodeCompletionContext::CCC_ClassStructUnion:
607  case CodeCompletionContext::CCC_Statement:
608  case CodeCompletionContext::CCC_Expression:
609  case CodeCompletionContext::CCC_ObjCMessageReceiver:
610  case CodeCompletionContext::CCC_EnumTag:
611  case CodeCompletionContext::CCC_UnionTag:
612  case CodeCompletionContext::CCC_ClassOrStructTag:
613  case CodeCompletionContext::CCC_ObjCProtocolName:
614  case CodeCompletionContext::CCC_Namespace:
615  case CodeCompletionContext::CCC_Type:
616  case CodeCompletionContext::CCC_ParenthesizedExpression:
617  case CodeCompletionContext::CCC_ObjCInterfaceName:
618  case CodeCompletionContext::CCC_ObjCCategoryName:
619  case CodeCompletionContext::CCC_Symbol:
620  case CodeCompletionContext::CCC_SymbolOrNewName:
621  return true;
622  case CodeCompletionContext::CCC_OtherWithMacros:
623  case CodeCompletionContext::CCC_DotMemberAccess:
624  case CodeCompletionContext::CCC_ArrowMemberAccess:
625  case CodeCompletionContext::CCC_ObjCPropertyAccess:
626  case CodeCompletionContext::CCC_MacroName:
627  case CodeCompletionContext::CCC_MacroNameUse:
628  case CodeCompletionContext::CCC_PreprocessorExpression:
629  case CodeCompletionContext::CCC_PreprocessorDirective:
630  case CodeCompletionContext::CCC_SelectorName:
631  case CodeCompletionContext::CCC_TypeQualifiers:
632  case CodeCompletionContext::CCC_ObjCInstanceMessage:
633  case CodeCompletionContext::CCC_ObjCClassMessage:
634  case CodeCompletionContext::CCC_IncludedFile:
635  // FIXME: Provide identifier based completions for the following contexts:
636  case CodeCompletionContext::CCC_Other: // Be conservative.
637  case CodeCompletionContext::CCC_NaturalLanguage:
638  case CodeCompletionContext::CCC_Recovery:
639  case CodeCompletionContext::CCC_NewName:
640  return false;
641  }
642  llvm_unreachable("unknown code completion context");
643 }
644 
645 static bool isInjectedClass(const NamedDecl &D) {
646  if (auto *R = dyn_cast_or_null<RecordDecl>(&D))
647  if (R->isInjectedClassName())
648  return true;
649  return false;
650 }
651 
652 // Some member calls are blacklisted because they're so rarely useful.
653 static bool isBlacklistedMember(const NamedDecl &D) {
654  // Destructor completion is rarely useful, and works inconsistently.
655  // (s.^ completes ~string, but s.~st^ is an error).
656  if (D.getKind() == Decl::CXXDestructor)
657  return true;
658  // Injected name may be useful for A::foo(), but who writes A::A::foo()?
659  if (isInjectedClass(D))
660  return true;
661  // Explicit calls to operators are also rare.
662  auto NameKind = D.getDeclName().getNameKind();
663  if (NameKind == DeclarationName::CXXOperatorName ||
664  NameKind == DeclarationName::CXXLiteralOperatorName ||
665  NameKind == DeclarationName::CXXConversionFunctionName)
666  return true;
667  return false;
668 }
669 
670 // The CompletionRecorder captures Sema code-complete output, including context.
671 // It filters out ignored results (but doesn't apply fuzzy-filtering yet).
672 // It doesn't do scoring or conversion to CompletionItem yet, as we want to
673 // merge with index results first.
674 // Generally the fields and methods of this object should only be used from
675 // within the callback.
676 struct CompletionRecorder : public CodeCompleteConsumer {
677  CompletionRecorder(const CodeCompleteOptions &Opts,
678  llvm::unique_function<void()> ResultsCallback)
679  : CodeCompleteConsumer(Opts.getClangCompleteOpts()),
680  CCContext(CodeCompletionContext::CCC_Other), Opts(Opts),
681  CCAllocator(std::make_shared<GlobalCodeCompletionAllocator>()),
682  CCTUInfo(CCAllocator), ResultsCallback(std::move(ResultsCallback)) {
683  assert(this->ResultsCallback);
684  }
685 
686  std::vector<CodeCompletionResult> Results;
687  CodeCompletionContext CCContext;
688  Sema *CCSema = nullptr; // Sema that created the results.
689  // FIXME: Sema is scary. Can we store ASTContext and Preprocessor, instead?
690 
691  void ProcessCodeCompleteResults(class Sema &S, CodeCompletionContext Context,
692  CodeCompletionResult *InResults,
693  unsigned NumResults) override final {
694  // Results from recovery mode are generally useless, and the callback after
695  // recovery (if any) is usually more interesting. To make sure we handle the
696  // future callback from sema, we just ignore all callbacks in recovery mode,
697  // as taking only results from recovery mode results in poor completion
698  // results.
699  // FIXME: in case there is no future sema completion callback after the
700  // recovery mode, we might still want to provide some results (e.g. trivial
701  // identifier-based completion).
702  if (Context.getKind() == CodeCompletionContext::CCC_Recovery) {
703  log("Code complete: Ignoring sema code complete callback with Recovery "
704  "context.");
705  return;
706  }
707  // If a callback is called without any sema result and the context does not
708  // support index-based completion, we simply skip it to give way to
709  // potential future callbacks with results.
710  if (NumResults == 0 && !contextAllowsIndex(Context.getKind()))
711  return;
712  if (CCSema) {
713  log("Multiple code complete callbacks (parser backtracked?). "
714  "Dropping results from context {0}, keeping results from {1}.",
715  getCompletionKindString(Context.getKind()),
716  getCompletionKindString(this->CCContext.getKind()));
717  return;
718  }
719  // Record the completion context.
720  CCSema = &S;
721  CCContext = Context;
722 
723  // Retain the results we might want.
724  for (unsigned I = 0; I < NumResults; ++I) {
725  auto &Result = InResults[I];
726  // Class members that are shadowed by subclasses are usually noise.
727  if (Result.Hidden && Result.Declaration &&
728  Result.Declaration->isCXXClassMember())
729  continue;
730  if (!Opts.IncludeIneligibleResults &&
731  (Result.Availability == CXAvailability_NotAvailable ||
732  Result.Availability == CXAvailability_NotAccessible))
733  continue;
734  if (Result.Declaration &&
735  !Context.getBaseType().isNull() // is this a member-access context?
736  && isBlacklistedMember(*Result.Declaration))
737  continue;
738  // Skip injected class name when no class scope is not explicitly set.
739  // E.g. show injected A::A in `using A::A^` but not in "A^".
740  if (Result.Declaration && !Context.getCXXScopeSpecifier().hasValue() &&
741  isInjectedClass(*Result.Declaration))
742  continue;
743  // We choose to never append '::' to completion results in clangd.
744  Result.StartsNestedNameSpecifier = false;
745  Results.push_back(Result);
746  }
747  ResultsCallback();
748  }
749 
750  CodeCompletionAllocator &getAllocator() override { return *CCAllocator; }
751  CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
752 
753  // Returns the filtering/sorting name for Result, which must be from Results.
754  // Returned string is owned by this recorder (or the AST).
755  llvm::StringRef getName(const CodeCompletionResult &Result) {
756  switch (Result.Kind) {
757  case CodeCompletionResult::RK_Declaration:
758  if (auto *ID = Result.Declaration->getIdentifier())
759  return ID->getName();
760  break;
761  case CodeCompletionResult::RK_Keyword:
762  return Result.Keyword;
763  case CodeCompletionResult::RK_Macro:
764  return Result.Macro->getName();
765  case CodeCompletionResult::RK_Pattern:
766  return Result.Pattern->getTypedText();
767  }
768  auto *CCS = codeCompletionString(Result);
769  return CCS->getTypedText();
770  }
771 
772  // Build a CodeCompletion string for R, which must be from Results.
773  // The CCS will be owned by this recorder.
774  CodeCompletionString *codeCompletionString(const CodeCompletionResult &R) {
775  // CodeCompletionResult doesn't seem to be const-correct. We own it, anyway.
776  return const_cast<CodeCompletionResult &>(R).CreateCodeCompletionString(
777  *CCSema, CCContext, *CCAllocator, CCTUInfo,
778  /*IncludeBriefComments=*/false);
779  }
780 
781 private:
782  CodeCompleteOptions Opts;
783  std::shared_ptr<GlobalCodeCompletionAllocator> CCAllocator;
784  CodeCompletionTUInfo CCTUInfo;
785  llvm::unique_function<void()> ResultsCallback;
786 };
787 
788 struct ScoredSignature {
789  // When set, requires documentation to be requested from the index with this
790  // ID.
791  llvm::Optional<SymbolID> IDForDoc;
792  SignatureInformation Signature;
793  SignatureQualitySignals Quality;
794 };
795 
796 class SignatureHelpCollector final : public CodeCompleteConsumer {
797 public:
798  SignatureHelpCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
799  const SymbolIndex *Index, SignatureHelp &SigHelp)
800  : CodeCompleteConsumer(CodeCompleteOpts), SigHelp(SigHelp),
801  Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
802  CCTUInfo(Allocator), Index(Index) {}
803 
804  void ProcessOverloadCandidates(Sema &S, unsigned CurrentArg,
805  OverloadCandidate *Candidates,
806  unsigned NumCandidates,
807  SourceLocation OpenParLoc) override {
808  assert(!OpenParLoc.isInvalid());
809  SourceManager &SrcMgr = S.getSourceManager();
810  OpenParLoc = SrcMgr.getFileLoc(OpenParLoc);
811  if (SrcMgr.isInMainFile(OpenParLoc))
812  SigHelp.argListStart = sourceLocToPosition(SrcMgr, OpenParLoc);
813  else
814  elog("Location oustide main file in signature help: {0}",
815  OpenParLoc.printToString(SrcMgr));
816 
817  std::vector<ScoredSignature> ScoredSignatures;
818  SigHelp.signatures.reserve(NumCandidates);
819  ScoredSignatures.reserve(NumCandidates);
820  // FIXME(rwols): How can we determine the "active overload candidate"?
821  // Right now the overloaded candidates seem to be provided in a "best fit"
822  // order, so I'm not too worried about this.
823  SigHelp.activeSignature = 0;
824  assert(CurrentArg <= (unsigned)std::numeric_limits<int>::max() &&
825  "too many arguments");
826  SigHelp.activeParameter = static_cast<int>(CurrentArg);
827  for (unsigned I = 0; I < NumCandidates; ++I) {
828  OverloadCandidate Candidate = Candidates[I];
829  // We want to avoid showing instantiated signatures, because they may be
830  // long in some cases (e.g. when 'T' is substituted with 'std::string', we
831  // would get 'std::basic_string<char>').
832  if (auto *Func = Candidate.getFunction()) {
833  if (auto *Pattern = Func->getTemplateInstantiationPattern())
834  Candidate = OverloadCandidate(Pattern);
835  }
836 
837  const auto *CCS = Candidate.CreateSignatureString(
838  CurrentArg, S, *Allocator, CCTUInfo, true);
839  assert(CCS && "Expected the CodeCompletionString to be non-null");
840  ScoredSignatures.push_back(processOverloadCandidate(
841  Candidate, *CCS,
842  Candidate.getFunction()
843  ? getDeclComment(S.getASTContext(), *Candidate.getFunction())
844  : ""));
845  }
846 
847  // Sema does not load the docs from the preamble, so we need to fetch extra
848  // docs from the index instead.
849  llvm::DenseMap<SymbolID, std::string> FetchedDocs;
850  if (Index) {
851  LookupRequest IndexRequest;
852  for (const auto &S : ScoredSignatures) {
853  if (!S.IDForDoc)
854  continue;
855  IndexRequest.IDs.insert(*S.IDForDoc);
856  }
857  Index->lookup(IndexRequest, [&](const Symbol &S) {
858  if (!S.Documentation.empty())
859  FetchedDocs[S.ID] = S.Documentation;
860  });
861  log("SigHelp: requested docs for {0} symbols from the index, got {1} "
862  "symbols with non-empty docs in the response",
863  IndexRequest.IDs.size(), FetchedDocs.size());
864  }
865 
866  llvm::sort(ScoredSignatures, [](const ScoredSignature &L,
867  const ScoredSignature &R) {
868  // Ordering follows:
869  // - Less number of parameters is better.
870  // - Function is better than FunctionType which is better than
871  // Function Template.
872  // - High score is better.
873  // - Shorter signature is better.
874  // - Alphebatically smaller is better.
875  if (L.Quality.NumberOfParameters != R.Quality.NumberOfParameters)
876  return L.Quality.NumberOfParameters < R.Quality.NumberOfParameters;
877  if (L.Quality.NumberOfOptionalParameters !=
878  R.Quality.NumberOfOptionalParameters)
879  return L.Quality.NumberOfOptionalParameters <
880  R.Quality.NumberOfOptionalParameters;
881  if (L.Quality.Kind != R.Quality.Kind) {
882  using OC = CodeCompleteConsumer::OverloadCandidate;
883  switch (L.Quality.Kind) {
884  case OC::CK_Function:
885  return true;
886  case OC::CK_FunctionType:
887  return R.Quality.Kind != OC::CK_Function;
888  case OC::CK_FunctionTemplate:
889  return false;
890  }
891  llvm_unreachable("Unknown overload candidate type.");
892  }
893  if (L.Signature.label.size() != R.Signature.label.size())
894  return L.Signature.label.size() < R.Signature.label.size();
895  return L.Signature.label < R.Signature.label;
896  });
897 
898  for (auto &SS : ScoredSignatures) {
899  auto IndexDocIt =
900  SS.IDForDoc ? FetchedDocs.find(*SS.IDForDoc) : FetchedDocs.end();
901  if (IndexDocIt != FetchedDocs.end())
902  SS.Signature.documentation = IndexDocIt->second;
903 
904  SigHelp.signatures.push_back(std::move(SS.Signature));
905  }
906  }
907 
908  GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
909 
910  CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
911 
912 private:
913  void processParameterChunk(llvm::StringRef ChunkText,
914  SignatureInformation &Signature) const {
915  // (!) this is O(n), should still be fast compared to building ASTs.
916  unsigned ParamStartOffset = lspLength(Signature.label);
917  unsigned ParamEndOffset = ParamStartOffset + lspLength(ChunkText);
918  // A piece of text that describes the parameter that corresponds to
919  // the code-completion location within a function call, message send,
920  // macro invocation, etc.
921  Signature.label += ChunkText;
922  ParameterInformation Info;
923  Info.labelOffsets.emplace(ParamStartOffset, ParamEndOffset);
924  // FIXME: only set 'labelOffsets' when all clients migrate out of it.
925  Info.labelString = ChunkText;
926 
927  Signature.parameters.push_back(std::move(Info));
928  }
929 
930  void processOptionalChunk(const CodeCompletionString &CCS,
931  SignatureInformation &Signature,
932  SignatureQualitySignals &Signal) const {
933  for (const auto &Chunk : CCS) {
934  switch (Chunk.Kind) {
935  case CodeCompletionString::CK_Optional:
936  assert(Chunk.Optional &&
937  "Expected the optional code completion string to be non-null.");
938  processOptionalChunk(*Chunk.Optional, Signature, Signal);
939  break;
940  case CodeCompletionString::CK_VerticalSpace:
941  break;
942  case CodeCompletionString::CK_CurrentParameter:
943  case CodeCompletionString::CK_Placeholder:
944  processParameterChunk(Chunk.Text, Signature);
945  Signal.NumberOfOptionalParameters++;
946  break;
947  default:
948  Signature.label += Chunk.Text;
949  break;
950  }
951  }
952  }
953 
954  // FIXME(ioeric): consider moving CodeCompletionString logic here to
955  // CompletionString.h.
956  ScoredSignature processOverloadCandidate(const OverloadCandidate &Candidate,
957  const CodeCompletionString &CCS,
958  llvm::StringRef DocComment) const {
959  SignatureInformation Signature;
960  SignatureQualitySignals Signal;
961  const char *ReturnType = nullptr;
962 
963  Signature.documentation = formatDocumentation(CCS, DocComment);
964  Signal.Kind = Candidate.getKind();
965 
966  for (const auto &Chunk : CCS) {
967  switch (Chunk.Kind) {
968  case CodeCompletionString::CK_ResultType:
969  // A piece of text that describes the type of an entity or,
970  // for functions and methods, the return type.
971  assert(!ReturnType && "Unexpected CK_ResultType");
972  ReturnType = Chunk.Text;
973  break;
974  case CodeCompletionString::CK_CurrentParameter:
975  case CodeCompletionString::CK_Placeholder:
976  processParameterChunk(Chunk.Text, Signature);
977  Signal.NumberOfParameters++;
978  break;
979  case CodeCompletionString::CK_Optional: {
980  // The rest of the parameters are defaulted/optional.
981  assert(Chunk.Optional &&
982  "Expected the optional code completion string to be non-null.");
983  processOptionalChunk(*Chunk.Optional, Signature, Signal);
984  break;
985  }
986  case CodeCompletionString::CK_VerticalSpace:
987  break;
988  default:
989  Signature.label += Chunk.Text;
990  break;
991  }
992  }
993  if (ReturnType) {
994  Signature.label += " -> ";
995  Signature.label += ReturnType;
996  }
997  dlog("Signal for {0}: {1}", Signature, Signal);
998  ScoredSignature Result;
999  Result.Signature = std::move(Signature);
1000  Result.Quality = Signal;
1001  Result.IDForDoc =
1002  Result.Signature.documentation.empty() && Candidate.getFunction()
1003  ? clangd::getSymbolID(Candidate.getFunction())
1004  : None;
1005  return Result;
1006  }
1007 
1008  SignatureHelp &SigHelp;
1009  std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
1010  CodeCompletionTUInfo CCTUInfo;
1011  const SymbolIndex *Index;
1012 }; // SignatureHelpCollector
1013 
1014 struct SemaCompleteInput {
1016  const tooling::CompileCommand &Command;
1017  const PreambleData *Preamble;
1018  llvm::StringRef Contents;
1019  size_t Offset;
1020  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS;
1021 };
1022 
1023 void loadMainFilePreambleMacros(const Preprocessor &PP,
1024  const PreambleData &Preamble) {
1025  // The ExternalPreprocessorSource has our macros, if we know where to look.
1026  // We can read all the macros using PreambleMacros->ReadDefinedMacros(),
1027  // but this includes transitively included files, so may deserialize a lot.
1028  ExternalPreprocessorSource *PreambleMacros = PP.getExternalSource();
1029  // As we have the names of the macros, we can look up their IdentifierInfo
1030  // and then use this to load just the macros we want.
1031  IdentifierInfoLookup *PreambleIdentifiers =
1032  PP.getIdentifierTable().getExternalIdentifierLookup();
1033  if (!PreambleIdentifiers || !PreambleMacros)
1034  return;
1035  for (const auto &MacroName : Preamble.MainFileMacros)
1036  if (auto *II = PreambleIdentifiers->get(MacroName))
1037  if (II->isOutOfDate())
1038  PreambleMacros->updateOutOfDateIdentifier(*II);
1039 }
1040 
1041 // Invokes Sema code completion on a file.
1042 // If \p Includes is set, it will be updated based on the compiler invocation.
1043 bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
1044  const clang::CodeCompleteOptions &Options,
1045  const SemaCompleteInput &Input,
1046  IncludeStructure *Includes = nullptr) {
1047  trace::Span Tracer("Sema completion");
1048  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS = Input.VFS;
1049  if (Input.Preamble && Input.Preamble->StatCache)
1050  VFS = Input.Preamble->StatCache->getConsumingFS(std::move(VFS));
1051  ParseInputs ParseInput;
1052  ParseInput.CompileCommand = Input.Command;
1053  ParseInput.FS = VFS;
1054  ParseInput.Contents = Input.Contents;
1055  ParseInput.Opts = ParseOptions();
1056  auto CI = buildCompilerInvocation(ParseInput);
1057  if (!CI) {
1058  elog("Couldn't create CompilerInvocation");
1059  return false;
1060  }
1061  auto &FrontendOpts = CI->getFrontendOpts();
1062  FrontendOpts.SkipFunctionBodies = true;
1063  // Disable typo correction in Sema.
1064  CI->getLangOpts()->SpellChecking = false;
1065  // Setup code completion.
1066  FrontendOpts.CodeCompleteOpts = Options;
1067  FrontendOpts.CodeCompletionAt.FileName = Input.FileName;
1068  std::tie(FrontendOpts.CodeCompletionAt.Line,
1069  FrontendOpts.CodeCompletionAt.Column) =
1070  offsetToClangLineColumn(Input.Contents, Input.Offset);
1071 
1072  std::unique_ptr<llvm::MemoryBuffer> ContentsBuffer =
1073  llvm::MemoryBuffer::getMemBufferCopy(Input.Contents, Input.FileName);
1074  // The diagnostic options must be set before creating a CompilerInstance.
1075  CI->getDiagnosticOpts().IgnoreWarnings = true;
1076  // We reuse the preamble whether it's valid or not. This is a
1077  // correctness/performance tradeoff: building without a preamble is slow, and
1078  // completion is latency-sensitive.
1079  // However, if we're completing *inside* the preamble section of the draft,
1080  // overriding the preamble will break sema completion. Fortunately we can just
1081  // skip all includes in this case; these completions are really simple.
1082  PreambleBounds PreambleRegion =
1083  ComputePreambleBounds(*CI->getLangOpts(), ContentsBuffer.get(), 0);
1084  bool CompletingInPreamble = PreambleRegion.Size > Input.Offset;
1085  // NOTE: we must call BeginSourceFile after prepareCompilerInstance. Otherwise
1086  // the remapped buffers do not get freed.
1087  IgnoreDiagnostics DummyDiagsConsumer;
1088  auto Clang = prepareCompilerInstance(
1089  std::move(CI),
1090  (Input.Preamble && !CompletingInPreamble) ? &Input.Preamble->Preamble
1091  : nullptr,
1092  std::move(ContentsBuffer), std::move(VFS), DummyDiagsConsumer);
1093  Clang->getPreprocessorOpts().SingleFileParseMode = CompletingInPreamble;
1094  Clang->setCodeCompletionConsumer(Consumer.release());
1095 
1097  if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])) {
1098  log("BeginSourceFile() failed when running codeComplete for {0}",
1099  Input.FileName);
1100  return false;
1101  }
1102  // Macros can be defined within the preamble region of the main file.
1103  // They don't fall nicely into our index/Sema dichotomy:
1104  // - they're not indexed for completion (they're not available across files)
1105  // - but Sema code complete won't see them: as part of the preamble, they're
1106  // deserialized only when mentioned.
1107  // Force them to be deserialized so SemaCodeComplete sees them.
1108  if (Input.Preamble)
1109  loadMainFilePreambleMacros(Clang->getPreprocessor(), *Input.Preamble);
1110  if (Includes)
1111  Clang->getPreprocessor().addPPCallbacks(
1112  collectIncludeStructureCallback(Clang->getSourceManager(), Includes));
1113  if (llvm::Error Err = Action.Execute()) {
1114  log("Execute() failed when running codeComplete for {0}: {1}",
1115  Input.FileName, toString(std::move(Err)));
1116  return false;
1117  }
1118  Action.EndSourceFile();
1119 
1120  return true;
1121 }
1122 
1123 // Should we allow index completions in the specified context?
1124 bool allowIndex(CodeCompletionContext &CC) {
1125  if (!contextAllowsIndex(CC.getKind()))
1126  return false;
1127  // We also avoid ClassName::bar (but allow namespace::bar).
1128  auto Scope = CC.getCXXScopeSpecifier();
1129  if (!Scope)
1130  return true;
1131  NestedNameSpecifier *NameSpec = (*Scope)->getScopeRep();
1132  if (!NameSpec)
1133  return true;
1134  // We only query the index when qualifier is a namespace.
1135  // If it's a class, we rely solely on sema completions.
1136  switch (NameSpec->getKind()) {
1137  case NestedNameSpecifier::Global:
1139  case NestedNameSpecifier::NamespaceAlias:
1140  return true;
1141  case NestedNameSpecifier::Super:
1142  case NestedNameSpecifier::TypeSpec:
1143  case NestedNameSpecifier::TypeSpecWithTemplate:
1144  // Unresolved inside a template.
1146  return false;
1147  }
1148  llvm_unreachable("invalid NestedNameSpecifier kind");
1149 }
1150 
1151 std::future<SymbolSlab> startAsyncFuzzyFind(const SymbolIndex &Index,
1152  const FuzzyFindRequest &Req) {
1153  return runAsync<SymbolSlab>([&Index, Req]() {
1154  trace::Span Tracer("Async fuzzyFind");
1155  SymbolSlab::Builder Syms;
1156  Index.fuzzyFind(Req, [&Syms](const Symbol &Sym) { Syms.insert(Sym); });
1157  return std::move(Syms).build();
1158  });
1159 }
1160 
1161 // Creates a `FuzzyFindRequest` based on the cached index request from the
1162 // last completion, if any, and the speculated completion filter text in the
1163 // source code.
1164 FuzzyFindRequest speculativeFuzzyFindRequestForCompletion(
1165  FuzzyFindRequest CachedReq, const CompletionPrefix &HeuristicPrefix) {
1166  CachedReq.Query = HeuristicPrefix.Name;
1167  return CachedReq;
1168 }
1169 
1170 // Runs Sema-based (AST) and Index-based completion, returns merged results.
1171 //
1172 // There are a few tricky considerations:
1173 // - the AST provides information needed for the index query (e.g. which
1174 // namespaces to search in). So Sema must start first.
1175 // - we only want to return the top results (Opts.Limit).
1176 // Building CompletionItems for everything else is wasteful, so we want to
1177 // preserve the "native" format until we're done with scoring.
1178 // - the data underlying Sema completion items is owned by the AST and various
1179 // other arenas, which must stay alive for us to build CompletionItems.
1180 // - we may get duplicate results from Sema and the Index, we need to merge.
1181 //
1182 // So we start Sema completion first, and do all our work in its callback.
1183 // We use the Sema context information to query the index.
1184 // Then we merge the two result sets, producing items that are Sema/Index/Both.
1185 // These items are scored, and the top N are synthesized into the LSP response.
1186 // Finally, we can clean up the data structures created by Sema completion.
1187 //
1188 // Main collaborators are:
1189 // - semaCodeComplete sets up the compiler machinery to run code completion.
1190 // - CompletionRecorder captures Sema completion results, including context.
1191 // - SymbolIndex (Opts.Index) provides index completion results as Symbols
1192 // - CompletionCandidates are the result of merging Sema and Index results.
1193 // Each candidate points to an underlying CodeCompletionResult (Sema), a
1194 // Symbol (Index), or both. It computes the result quality score.
1195 // CompletionCandidate also does conversion to CompletionItem (at the end).
1196 // - FuzzyMatcher scores how the candidate matches the partial identifier.
1197 // This score is combined with the result quality score for the final score.
1198 // - TopN determines the results with the best score.
1199 class CodeCompleteFlow {
1200  PathRef FileName;
1201  IncludeStructure Includes; // Complete once the compiler runs.
1202  SpeculativeFuzzyFind *SpecFuzzyFind; // Can be nullptr.
1203  const CodeCompleteOptions &Opts;
1204 
1205  // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
1206  CompletionRecorder *Recorder = nullptr;
1207  CodeCompletionContext::Kind CCContextKind = CodeCompletionContext::CCC_Other;
1208  // Counters for logging.
1209  int NSema = 0, NIndex = 0, NSemaAndIndex = 0, NIdent = 0;
1210  bool Incomplete = false; // Would more be available with a higher limit?
1211  CompletionPrefix HeuristicPrefix;
1212  llvm::Optional<FuzzyMatcher> Filter; // Initialized once Sema runs.
1213  Range ReplacedRange;
1214  std::vector<std::string> QueryScopes; // Initialized once Sema runs.
1215  // Initialized once QueryScopes is initialized, if there are scopes.
1216  llvm::Optional<ScopeDistance> ScopeProximity;
1217  llvm::Optional<OpaqueType> PreferredType; // Initialized once Sema runs.
1218  // Whether to query symbols from any scope. Initialized once Sema runs.
1219  bool AllScopes = false;
1220  llvm::StringSet<> ContextWords;
1221  // Include-insertion and proximity scoring rely on the include structure.
1222  // This is available after Sema has run.
1223  llvm::Optional<IncludeInserter> Inserter; // Available during runWithSema.
1224  llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
1225  /// Speculative request based on the cached request and the filter text before
1226  /// the cursor.
1227  /// Initialized right before sema run. This is only set if `SpecFuzzyFind` is
1228  /// set and contains a cached request.
1229  llvm::Optional<FuzzyFindRequest> SpecReq;
1230 
1231 public:
1232  // A CodeCompleteFlow object is only useful for calling run() exactly once.
1233  CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes,
1234  SpeculativeFuzzyFind *SpecFuzzyFind,
1235  const CodeCompleteOptions &Opts)
1236  : FileName(FileName), Includes(Includes), SpecFuzzyFind(SpecFuzzyFind),
1237  Opts(Opts) {}
1238 
1239  CodeCompleteResult run(const SemaCompleteInput &SemaCCInput) && {
1240  trace::Span Tracer("CodeCompleteFlow");
1241  HeuristicPrefix =
1242  guessCompletionPrefix(SemaCCInput.Contents, SemaCCInput.Offset);
1243  populateContextWords(SemaCCInput.Contents);
1244  if (Opts.Index && SpecFuzzyFind && SpecFuzzyFind->CachedReq.hasValue()) {
1245  assert(!SpecFuzzyFind->Result.valid());
1246  SpecReq = speculativeFuzzyFindRequestForCompletion(
1247  *SpecFuzzyFind->CachedReq, HeuristicPrefix);
1248  SpecFuzzyFind->Result = startAsyncFuzzyFind(*Opts.Index, *SpecReq);
1249  }
1250 
1251  // We run Sema code completion first. It builds an AST and calculates:
1252  // - completion results based on the AST.
1253  // - partial identifier and context. We need these for the index query.
1254  CodeCompleteResult Output;
1255  auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
1256  assert(Recorder && "Recorder is not set");
1257  CCContextKind = Recorder->CCContext.getKind();
1258  auto Style = getFormatStyleForFile(
1259  SemaCCInput.FileName, SemaCCInput.Contents, SemaCCInput.VFS.get());
1260  // If preprocessor was run, inclusions from preprocessor callback should
1261  // already be added to Includes.
1262  Inserter.emplace(
1263  SemaCCInput.FileName, SemaCCInput.Contents, Style,
1264  SemaCCInput.Command.Directory,
1265  &Recorder->CCSema->getPreprocessor().getHeaderSearchInfo());
1266  for (const auto &Inc : Includes.MainFileIncludes)
1267  Inserter->addExisting(Inc);
1268 
1269  // Most of the cost of file proximity is in initializing the FileDistance
1270  // structures based on the observed includes, once per query. Conceptually
1271  // that happens here (though the per-URI-scheme initialization is lazy).
1272  // The per-result proximity scoring is (amortized) very cheap.
1273  FileDistanceOptions ProxOpts{}; // Use defaults.
1274  const auto &SM = Recorder->CCSema->getSourceManager();
1275  llvm::StringMap<SourceParams> ProxSources;
1276  for (auto &Entry : Includes.includeDepth(
1277  SM.getFileEntryForID(SM.getMainFileID())->getName())) {
1278  auto &Source = ProxSources[Entry.getKey()];
1279  Source.Cost = Entry.getValue() * ProxOpts.IncludeCost;
1280  // Symbols near our transitive includes are good, but only consider
1281  // things in the same directory or below it. Otherwise there can be
1282  // many false positives.
1283  if (Entry.getValue() > 0)
1284  Source.MaxUpTraversals = 1;
1285  }
1286  FileProximity.emplace(ProxSources, ProxOpts);
1287 
1288  Output = runWithSema();
1289  Inserter.reset(); // Make sure this doesn't out-live Clang.
1290  SPAN_ATTACH(Tracer, "sema_completion_kind",
1291  getCompletionKindString(CCContextKind));
1292  log("Code complete: sema context {0}, query scopes [{1}] (AnyScope={2}), "
1293  "expected type {3}",
1294  getCompletionKindString(CCContextKind),
1295  llvm::join(QueryScopes.begin(), QueryScopes.end(), ","), AllScopes,
1296  PreferredType ? Recorder->CCContext.getPreferredType().getAsString()
1297  : "<none>");
1298  });
1299 
1300  Recorder = RecorderOwner.get();
1301 
1302  semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
1303  SemaCCInput, &Includes);
1304  logResults(Output, Tracer);
1305  return Output;
1306  }
1307 
1308  void logResults(const CodeCompleteResult &Output, const trace::Span &Tracer) {
1309  SPAN_ATTACH(Tracer, "sema_results", NSema);
1310  SPAN_ATTACH(Tracer, "index_results", NIndex);
1311  SPAN_ATTACH(Tracer, "merged_results", NSemaAndIndex);
1312  SPAN_ATTACH(Tracer, "identifier_results", NIdent);
1313  SPAN_ATTACH(Tracer, "returned_results", int64_t(Output.Completions.size()));
1314  SPAN_ATTACH(Tracer, "incomplete", Output.HasMore);
1315  log("Code complete: {0} results from Sema, {1} from Index, "
1316  "{2} matched, {3} from identifiers, {4} returned{5}.",
1317  NSema, NIndex, NSemaAndIndex, NIdent, Output.Completions.size(),
1318  Output.HasMore ? " (incomplete)" : "");
1319  assert(!Opts.Limit || Output.Completions.size() <= Opts.Limit);
1320  // We don't assert that isIncomplete means we hit a limit.
1321  // Indexes may choose to impose their own limits even if we don't have one.
1322  }
1323 
1324  CodeCompleteResult
1325  runWithoutSema(llvm::StringRef Content, size_t Offset,
1326  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS) && {
1327  trace::Span Tracer("CodeCompleteWithoutSema");
1328  // Fill in fields normally set by runWithSema()
1329  HeuristicPrefix = guessCompletionPrefix(Content, Offset);
1330  populateContextWords(Content);
1331  CCContextKind = CodeCompletionContext::CCC_Recovery;
1332  Filter = FuzzyMatcher(HeuristicPrefix.Name);
1333  auto Pos = offsetToPosition(Content, Offset);
1334  ReplacedRange.start = ReplacedRange.end = Pos;
1335  ReplacedRange.start.character -= HeuristicPrefix.Name.size();
1336 
1337  llvm::StringMap<SourceParams> ProxSources;
1338  ProxSources[FileName].Cost = 0;
1339  FileProximity.emplace(ProxSources);
1340 
1341  auto Style = getFormatStyleForFile(FileName, Content, VFS.get());
1342  // This will only insert verbatim headers.
1343  Inserter.emplace(FileName, Content, Style,
1344  /*BuildDir=*/"", /*HeaderSearchInfo=*/nullptr);
1345 
1346  auto Identifiers = collectIdentifiers(Content, Style);
1347  std::vector<RawIdentifier> IdentifierResults;
1348  for (const auto &IDAndCount : Identifiers) {
1349  RawIdentifier ID;
1350  ID.Name = IDAndCount.first();
1351  ID.References = IDAndCount.second;
1352  // Avoid treating typed filter as an identifier.
1353  if (ID.Name == HeuristicPrefix.Name)
1354  --ID.References;
1355  if (ID.References > 0)
1356  IdentifierResults.push_back(std::move(ID));
1357  }
1358 
1359  // Simplified version of getQueryScopes():
1360  // - accessible scopes are determined heuristically.
1361  // - all-scopes query if no qualifier was typed (and it's allowed).
1362  SpecifiedScope Scopes;
1363  Scopes.AccessibleScopes =
1364  visibleNamespaces(Content.take_front(Offset), Style);
1365  for (std::string &S : Scopes.AccessibleScopes)
1366  if (!S.empty())
1367  S.append("::"); // visibleNamespaces doesn't include trailing ::.
1368  if (HeuristicPrefix.Qualifier.empty())
1369  AllScopes = Opts.AllScopes;
1370  else if (HeuristicPrefix.Qualifier.startswith("::")) {
1371  Scopes.AccessibleScopes = {""};
1372  Scopes.UnresolvedQualifier = HeuristicPrefix.Qualifier.drop_front(2);
1373  } else
1374  Scopes.UnresolvedQualifier = HeuristicPrefix.Qualifier;
1375  // First scope is the (modified) enclosing scope.
1376  QueryScopes = Scopes.scopesForIndexQuery();
1377  ScopeProximity.emplace(QueryScopes);
1378 
1379  SymbolSlab IndexResults = Opts.Index ? queryIndex() : SymbolSlab();
1380 
1381  CodeCompleteResult Output = toCodeCompleteResult(mergeResults(
1382  /*SemaResults=*/{}, IndexResults, IdentifierResults));
1383  Output.RanParser = false;
1384  logResults(Output, Tracer);
1385  return Output;
1386  }
1387 
1388 private:
1389  void populateContextWords(llvm::StringRef Content) {
1390  // Take last 3 lines before the completion point.
1391  unsigned RangeEnd = HeuristicPrefix.Qualifier.begin() - Content.data(),
1392  RangeBegin = RangeEnd;
1393  for (size_t I = 0; I < 3 && RangeBegin > 0; ++I) {
1394  auto PrevNL = Content.rfind('\n', RangeBegin);
1395  if (PrevNL == StringRef::npos) {
1396  RangeBegin = 0;
1397  break;
1398  }
1399  RangeBegin = PrevNL;
1400  }
1401 
1402  ContextWords = collectWords(Content.slice(RangeBegin, RangeEnd));
1403  dlog("Completion context words: {0}",
1404  llvm::join(ContextWords.keys(), ", "));
1405  }
1406 
1407  // This is called by run() once Sema code completion is done, but before the
1408  // Sema data structures are torn down. It does all the real work.
1409  CodeCompleteResult runWithSema() {
1410  const auto &CodeCompletionRange = CharSourceRange::getCharRange(
1411  Recorder->CCSema->getPreprocessor().getCodeCompletionTokenRange());
1412  // When we are getting completions with an empty identifier, for example
1413  // std::vector<int> asdf;
1414  // asdf.^;
1415  // Then the range will be invalid and we will be doing insertion, use
1416  // current cursor position in such cases as range.
1417  if (CodeCompletionRange.isValid()) {
1418  ReplacedRange = halfOpenToRange(Recorder->CCSema->getSourceManager(),
1419  CodeCompletionRange);
1420  } else {
1421  const auto &Pos = sourceLocToPosition(
1422  Recorder->CCSema->getSourceManager(),
1423  Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
1424  ReplacedRange.start = ReplacedRange.end = Pos;
1425  }
1426  Filter = FuzzyMatcher(
1427  Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
1428  std::tie(QueryScopes, AllScopes) = getQueryScopes(
1429  Recorder->CCContext, *Recorder->CCSema, HeuristicPrefix, Opts);
1430  if (!QueryScopes.empty())
1431  ScopeProximity.emplace(QueryScopes);
1432  PreferredType =
1433  OpaqueType::fromType(Recorder->CCSema->getASTContext(),
1434  Recorder->CCContext.getPreferredType());
1435  // Sema provides the needed context to query the index.
1436  // FIXME: in addition to querying for extra/overlapping symbols, we should
1437  // explicitly request symbols corresponding to Sema results.
1438  // We can use their signals even if the index can't suggest them.
1439  // We must copy index results to preserve them, but there are at most Limit.
1440  auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext))
1441  ? queryIndex()
1442  : SymbolSlab();
1443  trace::Span Tracer("Populate CodeCompleteResult");
1444  // Merge Sema and Index results, score them, and pick the winners.
1445  auto Top =
1446  mergeResults(Recorder->Results, IndexResults, /*Identifiers*/ {});
1447  return toCodeCompleteResult(Top);
1448  }
1449 
1450  CodeCompleteResult
1451  toCodeCompleteResult(const std::vector<ScoredBundle> &Scored) {
1452  CodeCompleteResult Output;
1453 
1454  // Convert the results to final form, assembling the expensive strings.
1455  for (auto &C : Scored) {
1456  Output.Completions.push_back(toCodeCompletion(C.first));
1457  Output.Completions.back().Score = C.second;
1458  Output.Completions.back().CompletionTokenRange = ReplacedRange;
1459  }
1460  Output.HasMore = Incomplete;
1461  Output.Context = CCContextKind;
1462  return Output;
1463  }
1464 
1465  SymbolSlab queryIndex() {
1466  trace::Span Tracer("Query index");
1467  SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit));
1468 
1469  // Build the query.
1470  FuzzyFindRequest Req;
1471  if (Opts.Limit)
1472  Req.Limit = Opts.Limit;
1473  Req.Query = Filter->pattern();
1474  Req.RestrictForCodeCompletion = true;
1475  Req.Scopes = QueryScopes;
1476  Req.AnyScope = AllScopes;
1477  // FIXME: we should send multiple weighted paths here.
1478  Req.ProximityPaths.push_back(FileName);
1479  if (PreferredType)
1480  Req.PreferredTypes.push_back(PreferredType->raw());
1481  vlog("Code complete: fuzzyFind({0:2})", toJSON(Req));
1482 
1483  if (SpecFuzzyFind)
1484  SpecFuzzyFind->NewReq = Req;
1485  if (SpecFuzzyFind && SpecFuzzyFind->Result.valid() && (*SpecReq == Req)) {
1486  vlog("Code complete: speculative fuzzy request matches the actual index "
1487  "request. Waiting for the speculative index results.");
1488  SPAN_ATTACH(Tracer, "Speculative results", true);
1489 
1490  trace::Span WaitSpec("Wait speculative results");
1491  return SpecFuzzyFind->Result.get();
1492  }
1493 
1494  SPAN_ATTACH(Tracer, "Speculative results", false);
1495 
1496  // Run the query against the index.
1497  SymbolSlab::Builder ResultsBuilder;
1498  if (Opts.Index->fuzzyFind(
1499  Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); }))
1500  Incomplete = true;
1501  return std::move(ResultsBuilder).build();
1502  }
1503 
1504  // Merges Sema and Index results where possible, to form CompletionCandidates.
1505  // \p Identifiers is raw idenfiers that can also be completion condidates.
1506  // Identifiers are not merged with results from index or sema.
1507  // Groups overloads if desired, to form CompletionCandidate::Bundles. The
1508  // bundles are scored and top results are returned, best to worst.
1509  std::vector<ScoredBundle>
1510  mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
1511  const SymbolSlab &IndexResults,
1512  const std::vector<RawIdentifier> &IdentifierResults) {
1513  trace::Span Tracer("Merge and score results");
1514  std::vector<CompletionCandidate::Bundle> Bundles;
1515  llvm::DenseMap<size_t, size_t> BundleLookup;
1516  auto AddToBundles = [&](const CodeCompletionResult *SemaResult,
1517  const Symbol *IndexResult,
1518  const RawIdentifier *IdentifierResult) {
1519  CompletionCandidate C;
1520  C.SemaResult = SemaResult;
1521  C.IndexResult = IndexResult;
1522  C.IdentifierResult = IdentifierResult;
1523  if (C.IndexResult) {
1524  C.Name = IndexResult->Name;
1525  C.RankedIncludeHeaders = getRankedIncludes(*C.IndexResult);
1526  } else if (C.SemaResult) {
1527  C.Name = Recorder->getName(*SemaResult);
1528  } else {
1529  assert(IdentifierResult);
1530  C.Name = IdentifierResult->Name;
1531  }
1532  if (auto OverloadSet = C.overloadSet(Opts)) {
1533  auto Ret = BundleLookup.try_emplace(OverloadSet, Bundles.size());
1534  if (Ret.second)
1535  Bundles.emplace_back();
1536  Bundles[Ret.first->second].push_back(std::move(C));
1537  } else {
1538  Bundles.emplace_back();
1539  Bundles.back().push_back(std::move(C));
1540  }
1541  };
1542  llvm::DenseSet<const Symbol *> UsedIndexResults;
1543  auto CorrespondingIndexResult =
1544  [&](const CodeCompletionResult &SemaResult) -> const Symbol * {
1545  if (auto SymID =
1546  getSymbolID(SemaResult, Recorder->CCSema->getSourceManager())) {
1547  auto I = IndexResults.find(*SymID);
1548  if (I != IndexResults.end()) {
1549  UsedIndexResults.insert(&*I);
1550  return &*I;
1551  }
1552  }
1553  return nullptr;
1554  };
1555  // Emit all Sema results, merging them with Index results if possible.
1556  for (auto &SemaResult : SemaResults)
1557  AddToBundles(&SemaResult, CorrespondingIndexResult(SemaResult), nullptr);
1558  // Now emit any Index-only results.
1559  for (const auto &IndexResult : IndexResults) {
1560  if (UsedIndexResults.count(&IndexResult))
1561  continue;
1562  AddToBundles(/*SemaResult=*/nullptr, &IndexResult, nullptr);
1563  }
1564  // Emit identifier results.
1565  for (const auto &Ident : IdentifierResults)
1566  AddToBundles(/*SemaResult=*/nullptr, /*IndexResult=*/nullptr, &Ident);
1567  // We only keep the best N results at any time, in "native" format.
1568  TopN<ScoredBundle, ScoredBundleGreater> Top(
1569  Opts.Limit == 0 ? std::numeric_limits<size_t>::max() : Opts.Limit);
1570  for (auto &Bundle : Bundles)
1571  addCandidate(Top, std::move(Bundle));
1572  return std::move(Top).items();
1573  }
1574 
1575  llvm::Optional<float> fuzzyScore(const CompletionCandidate &C) {
1576  // Macros can be very spammy, so we only support prefix completion.
1577  // We won't end up with underfull index results, as macros are sema-only.
1578  if (C.SemaResult && C.SemaResult->Kind == CodeCompletionResult::RK_Macro &&
1579  !C.Name.startswith_lower(Filter->pattern()))
1580  return None;
1581  return Filter->match(C.Name);
1582  }
1583 
1584  // Scores a candidate and adds it to the TopN structure.
1585  void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
1586  CompletionCandidate::Bundle Bundle) {
1587  SymbolQualitySignals Quality;
1588  SymbolRelevanceSignals Relevance;
1589  Relevance.Context = CCContextKind;
1590  Relevance.Name = Bundle.front().Name;
1591  Relevance.Query = SymbolRelevanceSignals::CodeComplete;
1592  Relevance.FileProximityMatch = FileProximity.getPointer();
1593  if (ScopeProximity)
1594  Relevance.ScopeProximityMatch = ScopeProximity.getPointer();
1595  if (PreferredType)
1596  Relevance.HadContextType = true;
1597  Relevance.ContextWords = &ContextWords;
1598 
1599  auto &First = Bundle.front();
1600  if (auto FuzzyScore = fuzzyScore(First))
1601  Relevance.NameMatch = *FuzzyScore;
1602  else
1603  return;
1605  bool FromIndex = false;
1606  for (const auto &Candidate : Bundle) {
1607  if (Candidate.IndexResult) {
1608  Quality.merge(*Candidate.IndexResult);
1609  Relevance.merge(*Candidate.IndexResult);
1610  Origin |= Candidate.IndexResult->Origin;
1611  FromIndex = true;
1612  if (!Candidate.IndexResult->Type.empty())
1613  Relevance.HadSymbolType |= true;
1614  if (PreferredType &&
1615  PreferredType->raw() == Candidate.IndexResult->Type) {
1616  Relevance.TypeMatchesPreferred = true;
1617  }
1618  }
1619  if (Candidate.SemaResult) {
1620  Quality.merge(*Candidate.SemaResult);
1621  Relevance.merge(*Candidate.SemaResult);
1622  if (PreferredType) {
1623  if (auto CompletionType = OpaqueType::fromCompletionResult(
1624  Recorder->CCSema->getASTContext(), *Candidate.SemaResult)) {
1625  Relevance.HadSymbolType |= true;
1626  if (PreferredType == CompletionType)
1627  Relevance.TypeMatchesPreferred = true;
1628  }
1629  }
1630  Origin |= SymbolOrigin::AST;
1631  }
1632  if (Candidate.IdentifierResult) {
1633  Quality.References = Candidate.IdentifierResult->References;
1634  Relevance.Scope = SymbolRelevanceSignals::FileScope;
1635  Origin |= SymbolOrigin::Identifier;
1636  }
1637  }
1638 
1639  CodeCompletion::Scores Scores;
1640  Scores.Quality = Quality.evaluate();
1641  Scores.Relevance = Relevance.evaluate();
1642  Scores.Total = evaluateSymbolAndRelevance(Scores.Quality, Scores.Relevance);
1643  // NameMatch is in fact a multiplier on total score, so rescoring is sound.
1644  Scores.ExcludingName = Relevance.NameMatch
1645  ? Scores.Total / Relevance.NameMatch
1646  : Scores.Quality;
1647 
1648  dlog("CodeComplete: {0} ({1}) = {2}\n{3}{4}\n", First.Name,
1649  llvm::to_string(Origin), Scores.Total, llvm::to_string(Quality),
1650  llvm::to_string(Relevance));
1651 
1652  NSema += bool(Origin & SymbolOrigin::AST);
1653  NIndex += FromIndex;
1654  NSemaAndIndex += bool(Origin & SymbolOrigin::AST) && FromIndex;
1655  NIdent += bool(Origin & SymbolOrigin::Identifier);
1656  if (Candidates.push({std::move(Bundle), Scores}))
1657  Incomplete = true;
1658  }
1659 
1660  CodeCompletion toCodeCompletion(const CompletionCandidate::Bundle &Bundle) {
1661  llvm::Optional<CodeCompletionBuilder> Builder;
1662  for (const auto &Item : Bundle) {
1663  CodeCompletionString *SemaCCS =
1664  Item.SemaResult ? Recorder->codeCompletionString(*Item.SemaResult)
1665  : nullptr;
1666  if (!Builder)
1667  Builder.emplace(Recorder ? &Recorder->CCSema->getASTContext() : nullptr,
1668  Item, SemaCCS, QueryScopes, *Inserter, FileName,
1669  CCContextKind, Opts);
1670  else
1671  Builder->add(Item, SemaCCS);
1672  }
1673  return Builder->build();
1674  }
1675 };
1676 
1677 template <class T> bool isExplicitTemplateSpecialization(const NamedDecl &ND) {
1678  if (const auto *TD = dyn_cast<T>(&ND))
1679  if (TD->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
1680  return true;
1681  return false;
1682 }
1683 
1684 } // namespace
1685 
1686 clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
1687  clang::CodeCompleteOptions Result;
1688  Result.IncludeCodePatterns = EnableSnippets && IncludeCodePatterns;
1689  Result.IncludeMacros = IncludeMacros;
1690  Result.IncludeGlobals = true;
1691  // We choose to include full comments and not do doxygen parsing in
1692  // completion.
1693  // FIXME: ideally, we should support doxygen in some form, e.g. do markdown
1694  // formatting of the comments.
1695  Result.IncludeBriefComments = false;
1696 
1697  // When an is used, Sema is responsible for completing the main file,
1698  // the index can provide results from the preamble.
1699  // Tell Sema not to deserialize the preamble to look for results.
1700  Result.LoadExternal = !Index;
1701  Result.IncludeFixIts = IncludeFixIts;
1702 
1703  return Result;
1704 }
1705 
1706 CompletionPrefix guessCompletionPrefix(llvm::StringRef Content,
1707  unsigned Offset) {
1708  assert(Offset <= Content.size());
1709  StringRef Rest = Content.take_front(Offset);
1711 
1712  // Consume the unqualified name. We only handle ASCII characters.
1713  // isIdentifierBody will let us match "0invalid", but we don't mind.
1714  while (!Rest.empty() && isIdentifierBody(Rest.back()))
1715  Rest = Rest.drop_back();
1716  Result.Name = Content.slice(Rest.size(), Offset);
1717 
1718  // Consume qualifiers.
1719  while (Rest.consume_back("::") && !Rest.endswith(":")) // reject ::::
1720  while (!Rest.empty() && isIdentifierBody(Rest.back()))
1721  Rest = Rest.drop_back();
1722  Result.Qualifier =
1723  Content.slice(Rest.size(), Result.Name.begin() - Content.begin());
1724 
1725  return Result;
1726 }
1727 
1729 codeComplete(PathRef FileName, const tooling::CompileCommand &Command,
1730  const PreambleData *Preamble, llvm::StringRef Contents,
1731  Position Pos, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS,
1732  CodeCompleteOptions Opts, SpeculativeFuzzyFind *SpecFuzzyFind) {
1733  auto Offset = positionToOffset(Contents, Pos);
1734  if (!Offset) {
1735  elog("Code completion position was invalid {0}", Offset.takeError());
1736  return CodeCompleteResult();
1737  }
1738  auto Flow = CodeCompleteFlow(
1739  FileName, Preamble ? Preamble->Includes : IncludeStructure(),
1740  SpecFuzzyFind, Opts);
1741  return (!Preamble || Opts.RunParser == CodeCompleteOptions::NeverParse)
1742  ? std::move(Flow).runWithoutSema(Contents, *Offset, VFS)
1743  : std::move(Flow).run(
1744  {FileName, Command, Preamble, Contents, *Offset, VFS});
1745 }
1746 
1748  const tooling::CompileCommand &Command,
1749  const PreambleData *Preamble,
1750  llvm::StringRef Contents, Position Pos,
1751  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS,
1752  const SymbolIndex *Index) {
1753  auto Offset = positionToOffset(Contents, Pos);
1754  if (!Offset) {
1755  elog("Code completion position was invalid {0}", Offset.takeError());
1756  return SignatureHelp();
1757  }
1759  clang::CodeCompleteOptions Options;
1760  Options.IncludeGlobals = false;
1761  Options.IncludeMacros = false;
1762  Options.IncludeCodePatterns = false;
1763  Options.IncludeBriefComments = false;
1764  IncludeStructure PreambleInclusions; // Unused for signatureHelp
1765  semaCodeComplete(
1766  llvm::make_unique<SignatureHelpCollector>(Options, Index, Result),
1767  Options,
1768  {FileName, Command, Preamble, Contents, *Offset, std::move(VFS)});
1769  return Result;
1770 }
1771 
1772 bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx) {
1773  auto InTopLevelScope = [](const NamedDecl &ND) {
1774  switch (ND.getDeclContext()->getDeclKind()) {
1775  case Decl::TranslationUnit:
1776  case Decl::Namespace:
1777  case Decl::LinkageSpec:
1778  return true;
1779  default:
1780  break;
1781  };
1782  return false;
1783  };
1784  // We only complete symbol's name, which is the same as the name of the
1785  // *primary* template in case of template specializations.
1786  if (isExplicitTemplateSpecialization<FunctionDecl>(ND) ||
1787  isExplicitTemplateSpecialization<CXXRecordDecl>(ND) ||
1788  isExplicitTemplateSpecialization<VarDecl>(ND))
1789  return false;
1790 
1791  if (InTopLevelScope(ND))
1792  return true;
1793 
1794  if (const auto *EnumDecl = dyn_cast<clang::EnumDecl>(ND.getDeclContext()))
1795  return InTopLevelScope(*EnumDecl) && !EnumDecl->isScoped();
1796 
1797  return false;
1798 }
1799 
1801  CompletionItem LSP;
1802  const auto *InsertInclude = Includes.empty() ? nullptr : &Includes[0];
1803  LSP.label = ((InsertInclude && InsertInclude->Insertion)
1804  ? Opts.IncludeIndicator.Insert
1805  : Opts.IncludeIndicator.NoInsert) +
1806  (Opts.ShowOrigins ? "[" + llvm::to_string(Origin) + "]" : "") +
1807  RequiredQualifier + Name + Signature;
1808 
1809  LSP.kind = Kind;
1810  LSP.detail = BundleSize > 1 ? llvm::formatv("[{0} overloads]", BundleSize)
1811  : ReturnType;
1812  LSP.deprecated = Deprecated;
1813  if (InsertInclude)
1814  LSP.detail += "\n" + InsertInclude->Header;
1815  LSP.documentation = Documentation;
1816  LSP.sortText = sortText(Score.Total, Name);
1817  LSP.filterText = Name;
1818  LSP.textEdit = {CompletionTokenRange, RequiredQualifier + Name};
1819  // Merge continuous additionalTextEdits into main edit. The main motivation
1820  // behind this is to help LSP clients, it seems most of them are confused when
1821  // they are provided with additionalTextEdits that are consecutive to main
1822  // edit.
1823  // Note that we store additional text edits from back to front in a line. That
1824  // is mainly to help LSP clients again, so that changes do not effect each
1825  // other.
1826  for (const auto &FixIt : FixIts) {
1827  if (isRangeConsecutive(FixIt.range, LSP.textEdit->range)) {
1828  LSP.textEdit->newText = FixIt.newText + LSP.textEdit->newText;
1829  LSP.textEdit->range.start = FixIt.range.start;
1830  } else {
1831  LSP.additionalTextEdits.push_back(FixIt);
1832  }
1833  }
1834  if (Opts.EnableSnippets)
1835  LSP.textEdit->newText += SnippetSuffix;
1836 
1837  // FIXME(kadircet): Do not even fill insertText after making sure textEdit is
1838  // compatible with most of the editors.
1839  LSP.insertText = LSP.textEdit->newText;
1842  if (InsertInclude && InsertInclude->Insertion)
1843  LSP.additionalTextEdits.push_back(*InsertInclude->Insertion);
1844 
1845  return LSP;
1846 }
1847 
1848 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const CodeCompletion &C) {
1849  // For now just lean on CompletionItem.
1850  return OS << C.render(CodeCompleteOptions());
1851 }
1852 
1853 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
1854  const CodeCompleteResult &R) {
1855  OS << "CodeCompleteResult: " << R.Completions.size() << (R.HasMore ? "+" : "")
1856  << " (" << getCompletionKindString(R.Context) << ")"
1857  << " items:\n";
1858  for (const auto &C : R.Completions)
1859  OS << C << "\n";
1860  return OS;
1861 }
1862 
1863 } // namespace clangd
1864 } // namespace clang
std::string insertText
A string that should be inserted to a document when selecting this completion.
Definition: Protocol.h:966
std::vector< std::string > AccessibleScopes
Sema * CCSema
llvm::StringRef Name
bool ShowOrigins
Expose origins of completion items in the label (for debugging).
Definition: CodeComplete.h:87
const tooling::CompileCommand & Command
llvm::StringSet collectWords(llvm::StringRef Content)
Collects words from the source code.
Definition: SourceCode.cpp:713
std::shared_ptr< clang::GlobalCodeCompletionAllocator > Allocator
SignatureQualitySignals Quality
llvm::json::Value toJSON(const FuzzyFindRequest &Request)
Definition: Index.cpp:48
CodeCompletionContext::Kind Context
Definition: CodeComplete.h:219
std::string printQualifiedName(const NamedDecl &ND)
Returns the qualified name of ND.
Definition: AST.cpp:75
llvm::Optional< TextEdit > textEdit
An edit which is applied to a document when selecting this completion.
Definition: Protocol.h:977
llvm::StringRef Contents
Always use text-based completion.
Definition: CodeComplete.h:131
llvm::Optional< SymbolID > getSymbolID(const Decl *D)
Gets the symbol ID for a declaration, if possible.
Definition: AST.cpp:154
static llvm::Optional< OpaqueType > fromType(ASTContext &Ctx, QualType Type)
Construct an instance from a clang::QualType.
The primary text to be inserted is treated as a snippet.
llvm::IntrusiveRefCntPtr< llvm::vfs::FileSystem > VFS
ExpectedMatch Candidate
CompletionItemKind kind
The kind of this completion item.
Definition: Protocol.h:947
size_t lspLength(llvm::StringRef Code)
Definition: SourceCode.cpp:117
bool EnableSnippets
When true, completion items will contain expandable code snippets in completion (e.g.
Definition: CodeComplete.h:47
clang::find_all_symbols::SymbolInfo::SymbolKind SymbolKind
Definition: SymbolInfo.cpp:21
The primary text to be inserted is treated as a plain string.
std::string printNamespaceScope(const DeclContext &DC)
Returns the first enclosing namespace scope starting from DC.
Definition: AST.cpp:146
std::vector< CodeCompletion > Completions
Definition: CodeComplete.h:217
Interface for symbol indexes that can be used for searching or matching symbols among a set of symbol...
Definition: Index.h:85
std::pair< StringRef, StringRef > splitQualifiedName(StringRef QName)
Definition: SourceCode.cpp:391
std::string sortText(float Score, llvm::StringRef Name)
Returns a string that sorts in the same order as (-Score, Tiebreak), for LSP.
Definition: Quality.cpp:482
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:23
llvm::Optional< std::string > UnresolvedQualifier
std::vector< CodeCompletionResult > Results
std::string sortText
A string that should be used when comparing this item with other items.
Definition: Protocol.h:958
std::string getDocComment(const ASTContext &Ctx, const CodeCompletionResult &Result, bool CommentsFromHeaders)
Gets a minimally formatted documentation comment of Result, with comment markers stripped.
std::unique_ptr< CompilerInstance > prepareCompilerInstance(std::unique_ptr< clang::CompilerInvocation > CI, const PrecompiledPreamble *Preamble, std::unique_ptr< llvm::MemoryBuffer > Buffer, llvm::IntrusiveRefCntPtr< llvm::vfs::FileSystem > VFS, DiagnosticConsumer &DiagsClient)
Definition: Compiler.cpp:72
Documents should not be synced at all.
std::string documentation
A human-readable string that represents a doc-comment.
Definition: Protocol.h:954
void vlog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:67
std::vector< TextEdit > additionalTextEdits
An optional array of additional text edits that are applied when selecting this completion.
Definition: Protocol.h:982
void elog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:56
std::vector< std::string > visibleNamespaces(llvm::StringRef Code, const format::FormatStyle &Style)
Heuristically determine namespaces visible at a point, without parsing Code.
Definition: SourceCode.cpp:663
bool isRangeConsecutive(const Range &Left, const Range &Right)
Definition: SourceCode.cpp:462
CompletionItemKind
The kind of a completion entry.
Definition: Protocol.h:259
std::string getReturnType(const CodeCompletionString &CCS)
Gets detail to be used as the detail field in an LSP completion item.
SignatureHelp signatureHelp(PathRef FileName, const tooling::CompileCommand &Command, const PreambleData *Preamble, llvm::StringRef Contents, Position Pos, llvm::IntrusiveRefCntPtr< llvm::vfs::FileSystem > VFS, const SymbolIndex *Index)
BindArgumentKind Kind
std::string detail
A human-readable string with additional information about this item, like type or symbol information...
Definition: Protocol.h:951
llvm::Optional< float > Score
std::pair< size_t, size_t > offsetToClangLineColumn(llvm::StringRef Code, size_t Offset)
Definition: SourceCode.cpp:381
std::vector< SymbolDetails > getSymbolInfo(ParsedAST &AST, Position Pos)
Get info about symbols at Pos.
Definition: XRefs.cpp:992
TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M, const LangOptions &L)
Definition: SourceCode.cpp:453
Position offsetToPosition(llvm::StringRef Code, size_t Offset)
Turn an offset in Code into a [line, column] pair.
Definition: SourceCode.cpp:174
bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx)
std::string filterText
A string that should be used when filtering a set of completion items.
Definition: Protocol.h:962
llvm::Expected< size_t > positionToOffset(llvm::StringRef Code, Position P, bool AllowColumnsBeyondLineLength)
Turn a [line, column] pair into an offset in Code.
Definition: SourceCode.cpp:141
A speculative and asynchronous fuzzy find index request (based on cached request) that can be sent be...
Definition: CodeComplete.h:229
bool deprecated
Indicates if this item is deprecated.
Definition: Protocol.h:985
llvm::unique_function< void()> Action
std::string Signature
void log(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:62
static const char * toString(OffsetEncoding OE)
Definition: Protocol.cpp:1017
std::unique_ptr< CompilerInvocation > buildCompilerInvocation(const ParseInputs &Inputs)
Builds compiler invocation that could be used to build AST or preamble.
Definition: Compiler.cpp:44
#define dlog(...)
Definition: Logger.h:72
llvm::Expected< HeaderFile > toHeaderFile(llvm::StringRef Header, llvm::StringRef HintPath)
Creates a HeaderFile from Header which can be either a URI or a literal include.
Definition: Headers.cpp:77
enum clang::clangd::CodeCompleteOptions::CodeCompletionParse RunParser
const Decl * D
Definition: XRefs.cpp:868
const Symbol * IndexResult
PathRef FileName
std::string formatDocumentation(const CodeCompletionString &CCS, llvm::StringRef DocComment)
Assembles formatted documentation for a completion result.
std::string ReturnType
clang::CodeCompleteOptions getClangCompleteOpts() const
Returns options that can be passed to clang&#39;s completion engine.
std::string SnippetSuffix
Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc)
Turn a SourceLocation into a [line, column] pair.
Definition: SourceCode.cpp:186
An information message.
format::FormatStyle getFormatStyleForFile(llvm::StringRef File, llvm::StringRef Content, llvm::vfs::FileSystem *FS)
Choose the clang-format style we should apply to a certain file.
Definition: SourceCode.cpp:485
CodeCompleteResult codeComplete(PathRef FileName, const tooling::CompileCommand &Command, const PreambleData *Preamble, llvm::StringRef Contents, Position Pos, llvm::IntrusiveRefCntPtr< llvm::vfs::FileSystem > VFS, CodeCompleteOptions Opts, SpeculativeFuzzyFind *SpecFuzzyFind)
float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance)
Combine symbol quality and relevance into a single score.
Definition: Quality.cpp:464
CodeCompletionBuilder Builder
size_t Offset
std::string getDeclComment(const ASTContext &Ctx, const NamedDecl &Decl)
Similar to getDocComment, but returns the comment for a NamedDecl.
Represents the signature of a callable.
Definition: Protocol.h:1043
const PreambleData * Preamble
std::unique_ptr< PPCallbacks > collectIncludeStructureCallback(const SourceManager &SM, IncludeStructure *Out)
Returns a PPCallback that visits all inclusions in the main file.
Definition: Headers.cpp:113
llvm::SmallVector< llvm::StringRef, 1 > RankedIncludeHeaders
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
static URISchemeRegistry::Add< TestScheme > X(TestScheme::Scheme, "Test schema")
unsigned References
std::string label
The label of this completion item.
Definition: Protocol.h:943
CompletionItem render(const CodeCompleteOptions &) const
struct clang::clangd::CodeCompleteOptions::IncludeInsertionIndicator IncludeIndicator
CharSourceRange Range
SourceRange for the file name.
llvm::SmallVector< llvm::StringRef, 1 > getRankedIncludes(const Symbol &Sym)
Definition: Headers.cpp:97
CodeCompletionTUInfo CCTUInfo
void getSignature(const CodeCompletionString &CCS, std::string *Signature, std::string *Snippet, std::string *RequiredQualifiers, bool CompletingPattern)
Formats the signature for an item, as a display string and snippet.
llvm::Optional< llvm::Expected< tooling::AtomicChanges > > Result
Definition: Rename.cpp:36
const CodeCompletionResult * SemaResult
std::vector< const char * > Expected
const RawIdentifier * IdentifierResult
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:222
llvm::Optional< FixItHint > FixIt
Indicates if the symbol is deprecated.
Definition: Symbol.h:121
static llvm::Expected< URI > parse(llvm::StringRef Uri)
Parse a URI string "<scheme>:[//<authority>/]<path>".
Definition: URI.cpp:164
static std::string join(ArrayRef< SpecialMemberFunctionsCheck::SpecialMemberFunctionKind > SMFS, llvm::StringRef AndOr)
IncludeStructure Includes
Definition: ClangdUnit.h:61
CompletionPrefix guessCompletionPrefix(llvm::StringRef Content, unsigned Offset)
static llvm::cl::opt< bool > EnableFunctionArgSnippets("function-arg-placeholders", llvm::cl::desc("When disabled, completions contain only parentheses for " "function calls. When enabled, completions also contain " "placeholders for method parameters"), llvm::cl::init(CodeCompleteOptions().EnableFunctionArgSnippets), llvm::cl::Hidden)
llvm::raw_ostream & operator<<(llvm::raw_ostream &OS, const CodeCompletion &C)
InsertTextFormat insertTextFormat
The format of the insert text.
Definition: Protocol.h:970
llvm::StringMap< unsigned > collectIdentifiers(llvm::StringRef Content, const format::FormatStyle &Style)
Collects identifiers with counts in the source code.
Definition: SourceCode.cpp:522
CodeCompletionContext CCContext
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:98
llvm::Optional< SymbolID > IDForDoc
static llvm::Optional< OpaqueType > fromCompletionResult(ASTContext &Ctx, const CodeCompletionResult &R)
Create a type from a code completion result.
Range halfOpenToRange(const SourceManager &SM, CharSourceRange R)
Definition: SourceCode.cpp:373
const SymbolIndex * Index
Definition: Dexp.cpp:84