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