clang-tools-extra/clangd/CodeComplete.cpp

   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 "ExpectedTypes.h"
  25 #include "Feature.h"
  26 #include "FileDistance.h"
  27 #include "FuzzyMatch.h"
  28 #include "Headers.h"
  29 #include "Hover.h"
  30 #include "Preamble.h"
  31 #include "Protocol.h"
  32 #include "Quality.h"
  33 #include "SourceCode.h"
  34 #include "URI.h"
  35 #include "index/Index.h"
  36 #include "index/Symbol.h"
  37 #include "index/SymbolOrigin.h"
  38 #include "support/Logger.h"
  39 #include "support/Markup.h"
  40 #include "support/Threading.h"
  41 #include "support/ThreadsafeFS.h"
  42 #include "support/Trace.h"
  43 #include "clang/AST/Decl.h"
  44 #include "clang/AST/DeclBase.h"
  45 #include "clang/Basic/CharInfo.h"
  46 #include "clang/Basic/LangOptions.h"
  47 #include "clang/Basic/SourceLocation.h"
  48 #include "clang/Basic/TokenKinds.h"
  49 #include "clang/Format/Format.h"
  50 #include "clang/Frontend/CompilerInstance.h"
  51 #include "clang/Frontend/FrontendActions.h"
  52 #include "clang/Lex/ExternalPreprocessorSource.h"
  53 #include "clang/Lex/Lexer.h"
  54 #include "clang/Lex/Preprocessor.h"
  55 #include "clang/Lex/PreprocessorOptions.h"
  56 #include "clang/Sema/CodeCompleteConsumer.h"
  57 #include "clang/Sema/DeclSpec.h"
  58 #include "clang/Sema/Sema.h"
  59 #include "llvm/ADT/ArrayRef.h"
  60 #include "llvm/ADT/SmallVector.h"
  61 #include "llvm/ADT/StringExtras.h"
  62 #include "llvm/ADT/StringRef.h"
  63 #include "llvm/Support/Casting.h"
  64 #include "llvm/Support/Compiler.h"
  65 #include "llvm/Support/Debug.h"
  66 #include "llvm/Support/Error.h"
  67 #include "llvm/Support/FormatVariadic.h"
  68 #include "llvm/Support/ScopedPrinter.h"
  69 #include <algorithm>
  70 #include <iterator>
  71 #include <limits>
  72 #include <optional>
  73 #include <utility>
  74
  75 // We log detailed candidate here if you run with -debug-only=codecomplete.
  76 #define DEBUG_TYPE "CodeComplete"
  77
  78 namespace clang {
  79 namespace clangd {
  80
  81 #if CLANGD_DECISION_FOREST
  82 const CodeCompleteOptions::CodeCompletionRankingModel
  83     CodeCompleteOptions::DefaultRankingModel =
  84         CodeCompleteOptions::DecisionForest;
  85 #else
  86 const CodeCompleteOptions::CodeCompletionRankingModel
  87     CodeCompleteOptions::DefaultRankingModel = CodeCompleteOptions::Heuristics;
  88 #endif
  89
  90 namespace {
  91
  92 CompletionItemKind toCompletionItemKind(index::SymbolKind Kind) {
  93   using SK = index::SymbolKind;
  94   switch (Kind) {
  95   case SK::Unknown:
  96     return CompletionItemKind::Missing;
  97   case SK::Module:
  98   case SK::Namespace:
  99   case SK::NamespaceAlias:
 100     return CompletionItemKind::Module;
 101   case SK::Macro:
 102     return CompletionItemKind::Text;
 103   case SK::Enum:
 104     return CompletionItemKind::Enum;
 105   case SK::Struct:
 106     return CompletionItemKind::Struct;
 107   case SK::Class:
 108   case SK::Extension:
 109   case SK::Union:
 110     return CompletionItemKind::Class;
 111   case SK::Protocol:
 112     // Use interface instead of class for differentiation of classes and
 113     // protocols with the same name (e.g. @interface NSObject vs. @protocol
 114     // NSObject).
 115     return CompletionItemKind::Interface;
 116   case SK::TypeAlias:
 117     // We use the same kind as the VSCode C++ extension.
 118     // FIXME: pick a better option when we have one.
 119     return CompletionItemKind::Interface;
 120   case SK::Using:
 121     return CompletionItemKind::Reference;
 122   case SK::Function:
 123   case SK::ConversionFunction:
 124     return CompletionItemKind::Function;
 125   case SK::Variable:
 126   case SK::Parameter:
 127   case SK::NonTypeTemplateParm:
 128     return CompletionItemKind::Variable;
 129   case SK::Field:
 130     return CompletionItemKind::Field;
 131   case SK::EnumConstant:
 132     return CompletionItemKind::EnumMember;
 133   case SK::InstanceMethod:
 134   case SK::ClassMethod:
 135   case SK::StaticMethod:
 136   case SK::Destructor:
 137     return CompletionItemKind::Method;
 138   case SK::InstanceProperty:
 139   case SK::ClassProperty:
 140   case SK::StaticProperty:
 141     return CompletionItemKind::Property;
 142   case SK::Constructor:
 143     return CompletionItemKind::Constructor;
 144   case SK::TemplateTypeParm:
 145   case SK::TemplateTemplateParm:
 146     return CompletionItemKind::TypeParameter;
 147   case SK::Concept:
 148     return CompletionItemKind::Interface;
 149   }
 150   llvm_unreachable("Unhandled clang::index::SymbolKind.");
 151 }
 152
 153 CompletionItemKind toCompletionItemKind(const CodeCompletionResult &Res,
 154                                         CodeCompletionContext::Kind CtxKind) {
 155   if (Res.Declaration)
 156     return toCompletionItemKind(index::getSymbolInfo(Res.Declaration).Kind);
 157   if (CtxKind == CodeCompletionContext::CCC_IncludedFile)
 158     return CompletionItemKind::File;
 159   switch (Res.Kind) {
 160   case CodeCompletionResult::RK_Declaration:
 161     llvm_unreachable("RK_Declaration without Decl");
 162   case CodeCompletionResult::RK_Keyword:
 163     return CompletionItemKind::Keyword;
 164   case CodeCompletionResult::RK_Macro:
 165     // There is no 'Macro' kind in LSP.
 166     // Avoid using 'Text' to avoid confusion with client-side word-based
 167     // completion proposals.
 168     return Res.MacroDefInfo && Res.MacroDefInfo->isFunctionLike()
 169                ? CompletionItemKind::Function
 170                : CompletionItemKind::Constant;
 171   case CodeCompletionResult::RK_Pattern:
 172     return CompletionItemKind::Snippet;
 173   }
 174   llvm_unreachable("Unhandled CodeCompletionResult::ResultKind.");
 175 }
 176
 177 // FIXME: find a home for this (that can depend on both markup and Protocol).
 178 MarkupContent renderDoc(const markup::Document &Doc, MarkupKind Kind) {
 179   MarkupContent Result;
 180   Result.kind = Kind;
 181   switch (Kind) {
 182   case MarkupKind::PlainText:
 183     Result.value.append(Doc.asPlainText());
 184     break;
 185   case MarkupKind::Markdown:
 186     Result.value.append(Doc.asMarkdown());
 187     break;
 188   }
 189   return Result;
 190 }
 191
 192 Symbol::IncludeDirective insertionDirective(const CodeCompleteOptions &Opts) {
 193   if (!Opts.ImportInsertions || !Opts.MainFileSignals)
 194     return Symbol::IncludeDirective::Include;
 195   return Opts.MainFileSignals->InsertionDirective;
 196 }
 197
 198 // Identifier code completion result.
 199 struct RawIdentifier {
 200   llvm::StringRef Name;
 201   unsigned References; // # of usages in file.
 202 };
 203
 204 /// A code completion result, in clang-native form.
 205 /// It may be promoted to a CompletionItem if it's among the top-ranked results.
 206 struct CompletionCandidate {
 207   llvm::StringRef Name; // Used for filtering and sorting.
 208   // We may have a result from Sema, from the index, or both.
 209   const CodeCompletionResult *SemaResult = nullptr;
 210   const Symbol *IndexResult = nullptr;
 211   const RawIdentifier *IdentifierResult = nullptr;
 212   llvm::SmallVector<SymbolInclude, 1> RankedIncludeHeaders;
 213
 214   // Returns a token identifying the overload set this is part of.
 215   // 0 indicates it's not part of any overload set.
 216   size_t overloadSet(const CodeCompleteOptions &Opts, llvm::StringRef FileName,
 217                      IncludeInserter *Inserter,
 218                      CodeCompletionContext::Kind CCContextKind) const {
 219     if (!Opts.BundleOverloads.value_or(false))
 220       return 0;
 221
 222     // Depending on the index implementation, we can see different header
 223     // strings (literal or URI) mapping to the same file. We still want to
 224     // bundle those, so we must resolve the header to be included here.
 225     std::string HeaderForHash;
 226     if (Inserter) {
 227       if (auto Header = headerToInsertIfAllowed(Opts, CCContextKind)) {
 228         if (auto HeaderFile = toHeaderFile(*Header, FileName)) {
 229           if (auto Spelled =
 230                   Inserter->calculateIncludePath(*HeaderFile, FileName))
 231             HeaderForHash = *Spelled;
 232         } else {
 233           vlog("Code completion header path manipulation failed {0}",
 234                HeaderFile.takeError());
 235         }
 236       }
 237     }
 238
 239     llvm::SmallString<256> Scratch;
 240     if (IndexResult) {
 241       switch (IndexResult->SymInfo.Kind) {
 242       case index::SymbolKind::ClassMethod:
 243       case index::SymbolKind::InstanceMethod:
 244       case index::SymbolKind::StaticMethod:
 245 #ifndef NDEBUG
 246         llvm_unreachable("Don't expect members from index in code completion");
 247 #else
 248         [[fallthrough]];
 249 #endif
 250       case index::SymbolKind::Function:
 251         // We can't group overloads together that need different #includes.
 252         // This could break #include insertion.
 253         return llvm::hash_combine(
 254             (IndexResult->Scope + IndexResult->Name).toStringRef(Scratch),
 255             HeaderForHash);
 256       default:
 257         return 0;
 258       }
 259     }
 260     if (SemaResult) {
 261       // We need to make sure we're consistent with the IndexResult case!
 262       const NamedDecl *D = SemaResult->Declaration;
 263       if (!D || !D->isFunctionOrFunctionTemplate())
 264         return 0;
 265       {
 266         llvm::raw_svector_ostream OS(Scratch);
 267         D->printQualifiedName(OS);
 268       }
 269       return llvm::hash_combine(Scratch, HeaderForHash);
 270     }
 271     assert(IdentifierResult);
 272     return 0;
 273   }
 274
 275   bool contextAllowsHeaderInsertion(CodeCompletionContext::Kind Kind) const {
 276     // Explicitly disable insertions for forward declarations since they don't
 277     // reference the declaration.
 278     if (Kind == CodeCompletionContext::CCC_ObjCClassForwardDecl)
 279       return false;
 280     return true;
 281   }
 282
 283   // The best header to include if include insertion is allowed.
 284   std::optional<llvm::StringRef>
 285   headerToInsertIfAllowed(const CodeCompleteOptions &Opts,
 286                           CodeCompletionContext::Kind ContextKind) const {
 287     if (Opts.InsertIncludes == CodeCompleteOptions::NeverInsert ||
 288         RankedIncludeHeaders.empty() ||
 289         !contextAllowsHeaderInsertion(ContextKind))
 290       return std::nullopt;
 291     if (SemaResult && SemaResult->Declaration) {
 292       // Avoid inserting new #include if the declaration is found in the current
 293       // file e.g. the symbol is forward declared.
 294       auto &SM = SemaResult->Declaration->getASTContext().getSourceManager();
 295       for (const Decl *RD : SemaResult->Declaration->redecls())
 296         if (SM.isInMainFile(SM.getExpansionLoc(RD->getBeginLoc())))
 297           return std::nullopt;
 298     }
 299     Symbol::IncludeDirective Directive = insertionDirective(Opts);
 300     for (const auto &Inc : RankedIncludeHeaders)
 301       if ((Inc.Directive & Directive) != 0)
 302         return Inc.Header;
 303     return std::nullopt;
 304   }
 305
 306   using Bundle = llvm::SmallVector<CompletionCandidate, 4>;
 307 };
 308 using ScoredBundle =
 309     std::pair<CompletionCandidate::Bundle, CodeCompletion::Scores>;
 310 struct ScoredBundleGreater {
 311   bool operator()(const ScoredBundle &L, const ScoredBundle &R) {
 312     if (L.second.Total != R.second.Total)
 313       return L.second.Total > R.second.Total;
 314     return L.first.front().Name <
 315            R.first.front().Name; // Earlier name is better.
 316   }
 317 };
 318
 319 // Remove the first template argument from Signature.
 320 // If Signature only contains a single argument an empty string is returned.
 321 std::string removeFirstTemplateArg(llvm::StringRef Signature) {
 322   auto Rest = Signature.split(",").second;
 323   if (Rest.empty())
 324     return "";
 325   return ("<" + Rest.ltrim()).str();
 326 }
 327
 328 // Assembles a code completion out of a bundle of >=1 completion candidates.
 329 // Many of the expensive strings are only computed at this point, once we know
 330 // the candidate bundle is going to be returned.
 331 //
 332 // Many fields are the same for all candidates in a bundle (e.g. name), and are
 333 // computed from the first candidate, in the constructor.
 334 // Others vary per candidate, so add() must be called for remaining candidates.
 335 struct CodeCompletionBuilder {
 336   CodeCompletionBuilder(ASTContext *ASTCtx, const CompletionCandidate &C,
 337                         CodeCompletionString *SemaCCS,
 338                         llvm::ArrayRef<std::string> AccessibleScopes,
 339                         const IncludeInserter &Includes,
 340                         llvm::StringRef FileName,
 341                         CodeCompletionContext::Kind ContextKind,
 342                         const CodeCompleteOptions &Opts,
 343                         bool IsUsingDeclaration, tok::TokenKind NextTokenKind)
 344       : ASTCtx(ASTCtx),
 345         EnableFunctionArgSnippets(Opts.EnableFunctionArgSnippets),
 346         IsUsingDeclaration(IsUsingDeclaration), NextTokenKind(NextTokenKind) {
 347     Completion.Deprecated = true; // cleared by any non-deprecated overload.
 348     add(C, SemaCCS, ContextKind);
 349     if (C.SemaResult) {
 350       assert(ASTCtx);
 351       Completion.Origin |= SymbolOrigin::AST;
 352       Completion.Name = std::string(llvm::StringRef(SemaCCS->getTypedText()));
 353       Completion.FilterText = SemaCCS->getAllTypedText();
 354       if (Completion.Scope.empty()) {
 355         if ((C.SemaResult->Kind == CodeCompletionResult::RK_Declaration) ||
 356             (C.SemaResult->Kind == CodeCompletionResult::RK_Pattern))
 357           if (const auto *D = C.SemaResult->getDeclaration())
 358             if (const auto *ND = dyn_cast<NamedDecl>(D))
 359               Completion.Scope = std::string(
 360                   splitQualifiedName(printQualifiedName(*ND)).first);
 361       }
 362       Completion.Kind = toCompletionItemKind(*C.SemaResult, ContextKind);
 363       // Sema could provide more info on whether the completion was a file or
 364       // folder.
 365       if (Completion.Kind == CompletionItemKind::File &&
 366           Completion.Name.back() == '/')
 367         Completion.Kind = CompletionItemKind::Folder;
 368       for (const auto &FixIt : C.SemaResult->FixIts) {
 369         Completion.FixIts.push_back(toTextEdit(
 370             FixIt, ASTCtx->getSourceManager(), ASTCtx->getLangOpts()));
 371       }
 372       llvm::sort(Completion.FixIts, [](const TextEdit &X, const TextEdit &Y) {
 373         return std::tie(X.range.start.line, X.range.start.character) <
 374                std::tie(Y.range.start.line, Y.range.start.character);
 375       });
 376     }
 377     if (C.IndexResult) {
 378       Completion.Origin |= C.IndexResult->Origin;
 379       if (Completion.Scope.empty())
 380         Completion.Scope = std::string(C.IndexResult->Scope);
 381       if (Completion.Kind == CompletionItemKind::Missing)
 382         Completion.Kind = toCompletionItemKind(C.IndexResult->SymInfo.Kind);
 383       if (Completion.Name.empty())
 384         Completion.Name = std::string(C.IndexResult->Name);
 385       if (Completion.FilterText.empty())
 386         Completion.FilterText = Completion.Name;
 387       // If the completion was visible to Sema, no qualifier is needed. This
 388       // avoids unneeded qualifiers in cases like with `using ns::X`.
 389       if (Completion.RequiredQualifier.empty() && !C.SemaResult) {
 390         llvm::StringRef ShortestQualifier = C.IndexResult->Scope;
 391         for (llvm::StringRef Scope : AccessibleScopes) {
 392           llvm::StringRef Qualifier = C.IndexResult->Scope;
 393           if (Qualifier.consume_front(Scope) &&
 394               Qualifier.size() < ShortestQualifier.size())
 395             ShortestQualifier = Qualifier;
 396         }
 397         Completion.RequiredQualifier = std::string(ShortestQualifier);
 398       }
 399     }
 400     if (C.IdentifierResult) {
 401       Completion.Origin |= SymbolOrigin::Identifier;
 402       Completion.Kind = CompletionItemKind::Text;
 403       Completion.Name = std::string(C.IdentifierResult->Name);
 404       Completion.FilterText = Completion.Name;
 405     }
 406
 407     // Turn absolute path into a literal string that can be #included.
 408     auto Inserted = [&](llvm::StringRef Header)
 409         -> llvm::Expected<std::pair<std::string, bool>> {
 410       auto ResolvedDeclaring =
 411           URI::resolve(C.IndexResult->CanonicalDeclaration.FileURI, FileName);
 412       if (!ResolvedDeclaring)
 413         return ResolvedDeclaring.takeError();
 414       auto ResolvedInserted = toHeaderFile(Header, FileName);
 415       if (!ResolvedInserted)
 416         return ResolvedInserted.takeError();
 417       auto Spelled = Includes.calculateIncludePath(*ResolvedInserted, FileName);
 418       if (!Spelled)
 419         return error("Header not on include path");
 420       return std::make_pair(
 421           std::move(*Spelled),
 422           Includes.shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
 423     };
 424     bool ShouldInsert =
 425         C.headerToInsertIfAllowed(Opts, ContextKind).has_value();
 426     Symbol::IncludeDirective Directive = insertionDirective(Opts);
 427     // Calculate include paths and edits for all possible headers.
 428     for (const auto &Inc : C.RankedIncludeHeaders) {
 429       if ((Inc.Directive & Directive) == 0)
 430         continue;
 431
 432       if (auto ToInclude = Inserted(Inc.Header)) {
 433         CodeCompletion::IncludeCandidate Include;
 434         Include.Header = ToInclude->first;
 435         if (ToInclude->second && ShouldInsert)
 436           Include.Insertion = Includes.insert(
 437               ToInclude->first, Directive == Symbol::Import
 438                                     ? tooling::IncludeDirective::Import
 439                                     : tooling::IncludeDirective::Include);
 440         Completion.Includes.push_back(std::move(Include));
 441       } else
 442         log("Failed to generate include insertion edits for adding header "
 443             "(FileURI='{0}', IncludeHeader='{1}') into {2}: {3}",
 444             C.IndexResult->CanonicalDeclaration.FileURI, Inc.Header, FileName,
 445             ToInclude.takeError());
 446     }
 447     // Prefer includes that do not need edits (i.e. already exist).
 448     std::stable_partition(Completion.Includes.begin(),
 449                           Completion.Includes.end(),
 450                           [](const CodeCompletion::IncludeCandidate &I) {
 451                             return !I.Insertion.has_value();
 452                           });
 453   }
 454
 455   void add(const CompletionCandidate &C, CodeCompletionString *SemaCCS,
 456            CodeCompletionContext::Kind ContextKind) {
 457     assert(bool(C.SemaResult) == bool(SemaCCS));
 458     Bundled.emplace_back();
 459     BundledEntry &S = Bundled.back();
 460     bool IsConcept = false;
 461     if (C.SemaResult) {
 462       getSignature(*SemaCCS, &S.Signature, &S.SnippetSuffix, C.SemaResult->Kind,
 463                    C.SemaResult->CursorKind,
 464                    /*IncludeFunctionArguments=*/C.SemaResult->FunctionCanBeCall,
 465                    /*RequiredQualifiers=*/&Completion.RequiredQualifier);
 466       S.ReturnType = getReturnType(*SemaCCS);
 467       if (C.SemaResult->Kind == CodeCompletionResult::RK_Declaration)
 468         if (const auto *D = C.SemaResult->getDeclaration())
 469           if (isa<ConceptDecl>(D))
 470             IsConcept = true;
 471     } else if (C.IndexResult) {
 472       S.Signature = std::string(C.IndexResult->Signature);
 473       S.SnippetSuffix = std::string(C.IndexResult->CompletionSnippetSuffix);
 474       S.ReturnType = std::string(C.IndexResult->ReturnType);
 475       if (C.IndexResult->SymInfo.Kind == index::SymbolKind::Concept)
 476         IsConcept = true;
 477     }
 478
 479     /// When a concept is used as a type-constraint (e.g. `Iterator auto x`),
 480     /// and in some other contexts, its first type argument is not written.
 481     /// Drop the parameter from the signature.
 482     if (IsConcept && ContextKind == CodeCompletionContext::CCC_TopLevel) {
 483       S.Signature = removeFirstTemplateArg(S.Signature);
 484       // Dropping the first placeholder from the suffix will leave a $2
 485       // with no $1.
 486       S.SnippetSuffix = removeFirstTemplateArg(S.SnippetSuffix);
 487     }
 488
 489     if (!Completion.Documentation) {
 490       auto SetDoc = [&](llvm::StringRef Doc) {
 491         if (!Doc.empty()) {
 492           Completion.Documentation.emplace();
 493           parseDocumentation(Doc, *Completion.Documentation);
 494         }
 495       };
 496       if (C.IndexResult) {
 497         SetDoc(C.IndexResult->Documentation);
 498       } else if (C.SemaResult) {
 499         const auto DocComment = getDocComment(*ASTCtx, *C.SemaResult,
 500                                               /*CommentsFromHeaders=*/false);
 501         SetDoc(formatDocumentation(*SemaCCS, DocComment));
 502       }
 503     }
 504     if (Completion.Deprecated) {
 505       if (C.SemaResult)
 506         Completion.Deprecated &=
 507             C.SemaResult->Availability == CXAvailability_Deprecated;
 508       if (C.IndexResult)
 509         Completion.Deprecated &=
 510             bool(C.IndexResult->Flags & Symbol::Deprecated);
 511     }
 512   }
 513
 514   CodeCompletion build() {
 515     Completion.ReturnType = summarizeReturnType();
 516     Completion.Signature = summarizeSignature();
 517     Completion.SnippetSuffix = summarizeSnippet();
 518     Completion.BundleSize = Bundled.size();
 519     return std::move(Completion);
 520   }
 521
 522 private:
 523   struct BundledEntry {
 524     std::string SnippetSuffix;
 525     std::string Signature;
 526     std::string ReturnType;
 527   };
 528
 529   // If all BundledEntries have the same value for a property, return it.
 530   template <std::string BundledEntry::*Member>
 531   const std::string *onlyValue() const {
 532     auto B = Bundled.begin(), E = Bundled.end();
 533     for (auto *I = B + 1; I != E; ++I)
 534       if (I->*Member != B->*Member)
 535         return nullptr;
 536     return &(B->*Member);
 537   }
 538
 539   template <bool BundledEntry::*Member> const bool *onlyValue() const {
 540     auto B = Bundled.begin(), E = Bundled.end();
 541     for (auto *I = B + 1; I != E; ++I)
 542       if (I->*Member != B->*Member)
 543         return nullptr;
 544     return &(B->*Member);
 545   }
 546
 547   std::string summarizeReturnType() const {
 548     if (auto *RT = onlyValue<&BundledEntry::ReturnType>())
 549       return *RT;
 550     return "";
 551   }
 552
 553   std::string summarizeSnippet() const {
 554     if (IsUsingDeclaration)
 555       return "";
 556     auto *Snippet = onlyValue<&BundledEntry::SnippetSuffix>();
 557     if (!Snippet)
 558       // All bundles are function calls.
 559       // FIXME(ibiryukov): sometimes add template arguments to a snippet, e.g.
 560       // we need to complete 'forward<$1>($0)'.
 561       return "($0)";
 562
 563     if (Snippet->empty())
 564       return "";
 565
 566     bool MayHaveArgList = Completion.Kind == CompletionItemKind::Function ||
 567                           Completion.Kind == CompletionItemKind::Method ||
 568                           Completion.Kind == CompletionItemKind::Constructor ||
 569                           Completion.Kind == CompletionItemKind::Text /*Macro*/;
 570     // If likely arg list already exists, don't add new parens & placeholders.
 571     //   Snippet: function(int x, int y)
 572     //   func^(1,2) -> function(1, 2)
 573     //             NOT function(int x, int y)(1, 2)
 574     if (MayHaveArgList) {
 575       // Check for a template argument list in the code.
 576       //   Snippet: function<class T>(int x)
 577       //   fu^<int>(1) -> function<int>(1)
 578       if (NextTokenKind == tok::less && Snippet->front() == '<')
 579         return "";
 580       // Potentially followed by regular argument list.
 581       if (NextTokenKind == tok::l_paren) {
 582         //   Snippet: function<class T>(int x)
 583         //   fu^(1,2) -> function<class T>(1, 2)
 584         if (Snippet->front() == '<') {
 585           // Find matching '>', handling nested brackets.
 586           int Balance = 0;
 587           size_t I = 0;
 588           do {
 589             if (Snippet->at(I) == '>')
 590               --Balance;
 591             else if (Snippet->at(I) == '<')
 592               ++Balance;
 593             ++I;
 594           } while (Balance > 0);
 595           return Snippet->substr(0, I);
 596         }
 597         return "";
 598       }
 599     }
 600     if (EnableFunctionArgSnippets)
 601       return *Snippet;
 602
 603     // Replace argument snippets with a simplified pattern.
 604     if (MayHaveArgList) {
 605       // Functions snippets can be of 2 types:
 606       // - containing only function arguments, e.g.
 607       //   foo(${1:int p1}, ${2:int p2});
 608       //   We transform this pattern to '($0)' or '()'.
 609       // - template arguments and function arguments, e.g.
 610       //   foo<${1:class}>(${2:int p1}).
 611       //   We transform this pattern to '<$1>()$0' or '<$0>()'.
 612
 613       bool EmptyArgs = llvm::StringRef(*Snippet).endswith("()");
 614       if (Snippet->front() == '<')
 615         return EmptyArgs ? "<$1>()$0" : "<$1>($0)";
 616       if (Snippet->front() == '(')
 617         return EmptyArgs ? "()" : "($0)";
 618       return *Snippet; // Not an arg snippet?
 619     }
 620     // 'CompletionItemKind::Interface' matches template type aliases.
 621     if (Completion.Kind == CompletionItemKind::Interface ||
 622         Completion.Kind == CompletionItemKind::Class) {
 623       if (Snippet->front() != '<')
 624         return *Snippet; // Not an arg snippet?
 625
 626       // Classes and template using aliases can only have template arguments,
 627       // e.g. Foo<${1:class}>.
 628       if (llvm::StringRef(*Snippet).endswith("<>"))
 629         return "<>"; // can happen with defaulted template arguments.
 630       return "<$0>";
 631     }
 632     return *Snippet;
 633   }
 634
 635   std::string summarizeSignature() const {
 636     if (auto *Signature = onlyValue<&BundledEntry::Signature>())
 637       return *Signature;
 638     // All bundles are function calls.
 639     return "(…)";
 640   }
 641
 642   // ASTCtx can be nullptr if not run with sema.
 643   ASTContext *ASTCtx;
 644   CodeCompletion Completion;
 645   llvm::SmallVector<BundledEntry, 1> Bundled;
 646   bool EnableFunctionArgSnippets;
 647   // No snippets will be generated for using declarations and when the function
 648   // arguments are already present.
 649   bool IsUsingDeclaration;
 650   tok::TokenKind NextTokenKind;
 651 };
 652
 653 // Determine the symbol ID for a Sema code completion result, if possible.
 654 SymbolID getSymbolID(const CodeCompletionResult &R, const SourceManager &SM) {
 655   switch (R.Kind) {
 656   case CodeCompletionResult::RK_Declaration:
 657   case CodeCompletionResult::RK_Pattern: {
 658     // Computing USR caches linkage, which may change after code completion.
 659     if (hasUnstableLinkage(R.Declaration))
 660       return {};
 661     return clang::clangd::getSymbolID(R.Declaration);
 662   }
 663   case CodeCompletionResult::RK_Macro:
 664     return clang::clangd::getSymbolID(R.Macro->getName(), R.MacroDefInfo, SM);
 665   case CodeCompletionResult::RK_Keyword:
 666     return {};
 667   }
 668   llvm_unreachable("unknown CodeCompletionResult kind");
 669 }
 670
 671 // Scopes of the partial identifier we're trying to complete.
 672 // It is used when we query the index for more completion results.
 673 struct SpecifiedScope {
 674   // The scopes we should look in, determined by Sema.
 675   //
 676   // If the qualifier was fully resolved, we look for completions in these
 677   // scopes; if there is an unresolved part of the qualifier, it should be
 678   // resolved within these scopes.
 679   //
 680   // Examples of qualified completion:
 681   //
 682   //   "::vec"                                      => {""}
 683   //   "using namespace std; ::vec^"                => {"", "std::"}
 684   //   "namespace ns {using namespace std;} ns::^"  => {"ns::", "std::"}
 685   //   "std::vec^"                                  => {""}  // "std" unresolved
 686   //
 687   // Examples of unqualified completion:
 688   //
 689   //   "vec^"                                        => {""}
 690   //   "using namespace std; vec^"                   => {"", "std::"}
 691   //   "namespace ns {inline namespace ni { struct Foo {}}}
 692   //    using namespace ns::ni; Fo^ "                => {"", "ns::ni::"}
 693   //   "using namespace std; namespace ns { vec^ }"  => {"ns::", "std::", ""}
 694   //
 695   // "" for global namespace, "ns::" for normal namespace.
 696   std::vector<std::string> AccessibleScopes;
 697   // This is an overestimate of AccessibleScopes, e.g. it ignores inline
 698   // namespaces, to fetch more relevant symbols from index.
 699   std::vector<std::string> QueryScopes;
 700   // The full scope qualifier as typed by the user (without the leading "::").
 701   // Set if the qualifier is not fully resolved by Sema.
 702   std::optional<std::string> UnresolvedQualifier;
 703
 704   std::optional<std::string> EnclosingNamespace;
 705
 706   bool AllowAllScopes = false;
 707
 708   // Scopes that are accessible from current context. Used for dropping
 709   // unnecessary namespecifiers.
 710   std::vector<std::string> scopesForQualification() {
 711     std::set<std::string> Results;
 712     for (llvm::StringRef AS : AccessibleScopes)
 713       Results.insert(
 714           (AS + (UnresolvedQualifier ? *UnresolvedQualifier : "")).str());
 715     return {Results.begin(), Results.end()};
 716   }
 717
 718   // Construct scopes being queried in indexes. The results are deduplicated.
 719   // This method formats the scopes to match the index request representation.
 720   std::vector<std::string> scopesForIndexQuery() {
 721     // The enclosing namespace must be first, it gets a quality boost.
 722     std::vector<std::string> EnclosingAtFront;
 723     if (EnclosingNamespace.has_value())
 724       EnclosingAtFront.push_back(*EnclosingNamespace);
 725     std::set<std::string> Deduplicated;
 726     for (llvm::StringRef S : QueryScopes)
 727       if (S != EnclosingNamespace)
 728         Deduplicated.insert((S + UnresolvedQualifier.value_or("")).str());
 729
 730     EnclosingAtFront.reserve(EnclosingAtFront.size() + Deduplicated.size());
 731     llvm::copy(Deduplicated, std::back_inserter(EnclosingAtFront));
 732
 733     return EnclosingAtFront;
 734   }
 735 };
 736
 737 // Get all scopes that will be queried in indexes and whether symbols from
 738 // any scope is allowed. The first scope in the list is the preferred scope
 739 // (e.g. enclosing namespace).
 740 SpecifiedScope getQueryScopes(CodeCompletionContext &CCContext,
 741                               const Sema &CCSema,
 742                               const CompletionPrefix &HeuristicPrefix,
 743                               const CodeCompleteOptions &Opts) {
 744   SpecifiedScope Scopes;
 745   for (auto *Context : CCContext.getVisitedContexts()) {
 746     if (isa<TranslationUnitDecl>(Context)) {
 747       Scopes.QueryScopes.push_back("");
 748       Scopes.AccessibleScopes.push_back("");
 749     } else if (const auto *ND = dyn_cast<NamespaceDecl>(Context)) {
 750       Scopes.QueryScopes.push_back(printNamespaceScope(*Context));
 751       Scopes.AccessibleScopes.push_back(printQualifiedName(*ND) + "::");
 752     }
 753   }
 754
 755   const CXXScopeSpec *SemaSpecifier =
 756       CCContext.getCXXScopeSpecifier().value_or(nullptr);
 757   // Case 1: unqualified completion.
 758   if (!SemaSpecifier) {
 759     // Case 2 (exception): sema saw no qualifier, but there appears to be one!
 760     // This can happen e.g. in incomplete macro expansions. Use heuristics.
 761     if (!HeuristicPrefix.Qualifier.empty()) {
 762       vlog("Sema said no scope specifier, but we saw {0} in the source code",
 763            HeuristicPrefix.Qualifier);
 764       StringRef SpelledSpecifier = HeuristicPrefix.Qualifier;
 765       if (SpelledSpecifier.consume_front("::")) {
 766         Scopes.AccessibleScopes = {""};
 767         Scopes.QueryScopes = {""};
 768       }
 769       Scopes.UnresolvedQualifier = std::string(SpelledSpecifier);
 770       return Scopes;
 771     }
 772     /// FIXME: When the enclosing namespace contains an inline namespace,
 773     /// it's dropped here. This leads to a behavior similar to
 774     /// https://github.com/clangd/clangd/issues/1451
 775     Scopes.EnclosingNamespace = printNamespaceScope(*CCSema.CurContext);
 776     // Allow AllScopes completion as there is no explicit scope qualifier.
 777     Scopes.AllowAllScopes = Opts.AllScopes;
 778     return Scopes;
 779   }
 780   // Case 3: sema saw and resolved a scope qualifier.
 781   if (SemaSpecifier && SemaSpecifier->isValid())
 782     return Scopes;
 783
 784   // Case 4: There was a qualifier, and Sema didn't resolve it.
 785   Scopes.QueryScopes.push_back(""); // Make sure global scope is included.
 786   llvm::StringRef SpelledSpecifier = Lexer::getSourceText(
 787       CharSourceRange::getCharRange(SemaSpecifier->getRange()),
 788       CCSema.SourceMgr, clang::LangOptions());
 789   if (SpelledSpecifier.consume_front("::"))
 790       Scopes.QueryScopes = {""};
 791   Scopes.UnresolvedQualifier = std::string(SpelledSpecifier);
 792   // Sema excludes the trailing "::".
 793   if (!Scopes.UnresolvedQualifier->empty())
 794     *Scopes.UnresolvedQualifier += "::";
 795
 796   Scopes.AccessibleScopes = Scopes.QueryScopes;
 797
 798   return Scopes;
 799 }
 800
 801 // Should we perform index-based completion in a context of the specified kind?
 802 // FIXME: consider allowing completion, but restricting the result types.
 803 bool contextAllowsIndex(enum CodeCompletionContext::Kind K) {
 804   switch (K) {
 805   case CodeCompletionContext::CCC_TopLevel:
 806   case CodeCompletionContext::CCC_ObjCInterface:
 807   case CodeCompletionContext::CCC_ObjCImplementation:
 808   case CodeCompletionContext::CCC_ObjCIvarList:
 809   case CodeCompletionContext::CCC_ClassStructUnion:
 810   case CodeCompletionContext::CCC_Statement:
 811   case CodeCompletionContext::CCC_Expression:
 812   case CodeCompletionContext::CCC_ObjCMessageReceiver:
 813   case CodeCompletionContext::CCC_EnumTag:
 814   case CodeCompletionContext::CCC_UnionTag:
 815   case CodeCompletionContext::CCC_ClassOrStructTag:
 816   case CodeCompletionContext::CCC_ObjCProtocolName:
 817   case CodeCompletionContext::CCC_Namespace:
 818   case CodeCompletionContext::CCC_Type:
 819   case CodeCompletionContext::CCC_ParenthesizedExpression:
 820   case CodeCompletionContext::CCC_ObjCInterfaceName:
 821   case CodeCompletionContext::CCC_Symbol:
 822   case CodeCompletionContext::CCC_SymbolOrNewName:
 823   case CodeCompletionContext::CCC_ObjCClassForwardDecl:
 824   case CodeCompletionContext::CCC_TopLevelOrExpression:
 825     return true;
 826   case CodeCompletionContext::CCC_OtherWithMacros:
 827   case CodeCompletionContext::CCC_DotMemberAccess:
 828   case CodeCompletionContext::CCC_ArrowMemberAccess:
 829   case CodeCompletionContext::CCC_ObjCCategoryName:
 830   case CodeCompletionContext::CCC_ObjCPropertyAccess:
 831   case CodeCompletionContext::CCC_MacroName:
 832   case CodeCompletionContext::CCC_MacroNameUse:
 833   case CodeCompletionContext::CCC_PreprocessorExpression:
 834   case CodeCompletionContext::CCC_PreprocessorDirective:
 835   case CodeCompletionContext::CCC_SelectorName:
 836   case CodeCompletionContext::CCC_TypeQualifiers:
 837   case CodeCompletionContext::CCC_ObjCInstanceMessage:
 838   case CodeCompletionContext::CCC_ObjCClassMessage:
 839   case CodeCompletionContext::CCC_IncludedFile:
 840   case CodeCompletionContext::CCC_Attribute:
 841   // FIXME: Provide identifier based completions for the following contexts:
 842   case CodeCompletionContext::CCC_Other: // Be conservative.
 843   case CodeCompletionContext::CCC_NaturalLanguage:
 844   case CodeCompletionContext::CCC_Recovery:
 845   case CodeCompletionContext::CCC_NewName:
 846     return false;
 847   }
 848   llvm_unreachable("unknown code completion context");
 849 }
 850
 851 static bool isInjectedClass(const NamedDecl &D) {
 852   if (auto *R = dyn_cast_or_null<RecordDecl>(&D))
 853     if (R->isInjectedClassName())
 854       return true;
 855   return false;
 856 }
 857
 858 // Some member calls are excluded because they're so rarely useful.
 859 static bool isExcludedMember(const NamedDecl &D) {
 860   // Destructor completion is rarely useful, and works inconsistently.
 861   // (s.^ completes ~string, but s.~st^ is an error).
 862   if (D.getKind() == Decl::CXXDestructor)
 863     return true;
 864   // Injected name may be useful for A::foo(), but who writes A::A::foo()?
 865   if (isInjectedClass(D))
 866     return true;
 867   // Explicit calls to operators are also rare.
 868   auto NameKind = D.getDeclName().getNameKind();
 869   if (NameKind == DeclarationName::CXXOperatorName ||
 870       NameKind == DeclarationName::CXXLiteralOperatorName ||
 871       NameKind == DeclarationName::CXXConversionFunctionName)
 872     return true;
 873   return false;
 874 }
 875
 876 // The CompletionRecorder captures Sema code-complete output, including context.
 877 // It filters out ignored results (but doesn't apply fuzzy-filtering yet).
 878 // It doesn't do scoring or conversion to CompletionItem yet, as we want to
 879 // merge with index results first.
 880 // Generally the fields and methods of this object should only be used from
 881 // within the callback.
 882 struct CompletionRecorder : public CodeCompleteConsumer {
 883   CompletionRecorder(const CodeCompleteOptions &Opts,
 884                      llvm::unique_function<void()> ResultsCallback)
 885       : CodeCompleteConsumer(Opts.getClangCompleteOpts()),
 886         CCContext(CodeCompletionContext::CCC_Other), Opts(Opts),
 887         CCAllocator(std::make_shared<GlobalCodeCompletionAllocator>()),
 888         CCTUInfo(CCAllocator), ResultsCallback(std::move(ResultsCallback)) {
 889     assert(this->ResultsCallback);
 890   }
 891
 892   std::vector<CodeCompletionResult> Results;
 893   CodeCompletionContext CCContext;
 894   Sema *CCSema = nullptr; // Sema that created the results.
 895   // FIXME: Sema is scary. Can we store ASTContext and Preprocessor, instead?
 896
 897   void ProcessCodeCompleteResults(class Sema &S, CodeCompletionContext Context,
 898                                   CodeCompletionResult *InResults,
 899                                   unsigned NumResults) final {
 900     // Results from recovery mode are generally useless, and the callback after
 901     // recovery (if any) is usually more interesting. To make sure we handle the
 902     // future callback from sema, we just ignore all callbacks in recovery mode,
 903     // as taking only results from recovery mode results in poor completion
 904     // results.
 905     // FIXME: in case there is no future sema completion callback after the
 906     // recovery mode, we might still want to provide some results (e.g. trivial
 907     // identifier-based completion).
 908     if (Context.getKind() == CodeCompletionContext::CCC_Recovery) {
 909       log("Code complete: Ignoring sema code complete callback with Recovery "
 910           "context.");
 911       return;
 912     }
 913     // If a callback is called without any sema result and the context does not
 914     // support index-based completion, we simply skip it to give way to
 915     // potential future callbacks with results.
 916     if (NumResults == 0 && !contextAllowsIndex(Context.getKind()))
 917       return;
 918     if (CCSema) {
 919       log("Multiple code complete callbacks (parser backtracked?). "
 920           "Dropping results from context {0}, keeping results from {1}.",
 921           getCompletionKindString(Context.getKind()),
 922           getCompletionKindString(this->CCContext.getKind()));
 923       return;
 924     }
 925     // Record the completion context.
 926     CCSema = &S;
 927     CCContext = Context;
 928
 929     // Retain the results we might want.
 930     for (unsigned I = 0; I < NumResults; ++I) {
 931       auto &Result = InResults[I];
 932       // Class members that are shadowed by subclasses are usually noise.
 933       if (Result.Hidden && Result.Declaration &&
 934           Result.Declaration->isCXXClassMember())
 935         continue;
 936       if (!Opts.IncludeIneligibleResults &&
 937           (Result.Availability == CXAvailability_NotAvailable ||
 938            Result.Availability == CXAvailability_NotAccessible))
 939         continue;
 940       if (Result.Declaration &&
 941           !Context.getBaseType().isNull() // is this a member-access context?
 942           && isExcludedMember(*Result.Declaration))
 943         continue;
 944       // Skip injected class name when no class scope is not explicitly set.
 945       // E.g. show injected A::A in `using A::A^` but not in "A^".
 946       if (Result.Declaration && !Context.getCXXScopeSpecifier() &&
 947           isInjectedClass(*Result.Declaration))
 948         continue;
 949       // We choose to never append '::' to completion results in clangd.
 950       Result.StartsNestedNameSpecifier = false;
 951       Results.push_back(Result);
 952     }
 953     ResultsCallback();
 954   }
 955
 956   CodeCompletionAllocator &getAllocator() override { return *CCAllocator; }
 957   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
 958
 959   // Returns the filtering/sorting name for Result, which must be from Results.
 960   // Returned string is owned by this recorder (or the AST).
 961   llvm::StringRef getName(const CodeCompletionResult &Result) {
 962     switch (Result.Kind) {
 963     case CodeCompletionResult::RK_Declaration:
 964       if (auto *ID = Result.Declaration->getIdentifier())
 965         return ID->getName();
 966       break;
 967     case CodeCompletionResult::RK_Keyword:
 968       return Result.Keyword;
 969     case CodeCompletionResult::RK_Macro:
 970       return Result.Macro->getName();
 971     case CodeCompletionResult::RK_Pattern:
 972       break;
 973     }
 974     auto *CCS = codeCompletionString(Result);
 975     const CodeCompletionString::Chunk *OnlyText = nullptr;
 976     for (auto &C : *CCS) {
 977       if (C.Kind != CodeCompletionString::CK_TypedText)
 978         continue;
 979       if (OnlyText)
 980         return CCAllocator->CopyString(CCS->getAllTypedText());
 981       OnlyText = &C;
 982     }
 983     return OnlyText ? OnlyText->Text : llvm::StringRef();
 984   }
 985
 986   // Build a CodeCompletion string for R, which must be from Results.
 987   // The CCS will be owned by this recorder.
 988   CodeCompletionString *codeCompletionString(const CodeCompletionResult &R) {
 989     // CodeCompletionResult doesn't seem to be const-correct. We own it, anyway.
 990     return const_cast<CodeCompletionResult &>(R).CreateCodeCompletionString(
 991         *CCSema, CCContext, *CCAllocator, CCTUInfo,
 992         /*IncludeBriefComments=*/false);
 993   }
 994
 995 private:
 996   CodeCompleteOptions Opts;
 997   std::shared_ptr<GlobalCodeCompletionAllocator> CCAllocator;
 998   CodeCompletionTUInfo CCTUInfo;
 999   llvm::unique_function<void()> ResultsCallback;
1000 };
1001
1002 struct ScoredSignature {
1003   // When not null, requires documentation to be requested from the index with
1004   // this ID.
1005   SymbolID IDForDoc;
1006   SignatureInformation Signature;
1007   SignatureQualitySignals Quality;
1008 };
1009
1010 // Returns the index of the parameter matching argument number "Arg.
1011 // This is usually just "Arg", except for variadic functions/templates, where
1012 // "Arg" might be higher than the number of parameters. When that happens, we
1013 // assume the last parameter is variadic and assume all further args are
1014 // part of it.
1015 int paramIndexForArg(const CodeCompleteConsumer::OverloadCandidate &Candidate,
1016                      int Arg) {
1017   int NumParams = Candidate.getNumParams();
1018   if (auto *T = Candidate.getFunctionType()) {
1019     if (auto *Proto = T->getAs<FunctionProtoType>()) {
1020       if (Proto->isVariadic())
1021         ++NumParams;
1022     }
1023   }
1024   return std::min(Arg, std::max(NumParams - 1, 0));
1025 }
1026
1027 class SignatureHelpCollector final : public CodeCompleteConsumer {
1028 public:
1029   SignatureHelpCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
1030                          MarkupKind DocumentationFormat,
1031                          const SymbolIndex *Index, SignatureHelp &SigHelp)
1032       : CodeCompleteConsumer(CodeCompleteOpts), SigHelp(SigHelp),
1033         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
1034         CCTUInfo(Allocator), Index(Index),
1035         DocumentationFormat(DocumentationFormat) {}
1036
1037   void ProcessOverloadCandidates(Sema &S, unsigned CurrentArg,
1038                                  OverloadCandidate *Candidates,
1039                                  unsigned NumCandidates,
1040                                  SourceLocation OpenParLoc,
1041                                  bool Braced) override {
1042     assert(!OpenParLoc.isInvalid());
1043     SourceManager &SrcMgr = S.getSourceManager();
1044     OpenParLoc = SrcMgr.getFileLoc(OpenParLoc);
1045     if (SrcMgr.isInMainFile(OpenParLoc))
1046       SigHelp.argListStart = sourceLocToPosition(SrcMgr, OpenParLoc);
1047     else
1048       elog("Location oustide main file in signature help: {0}",
1049            OpenParLoc.printToString(SrcMgr));
1050
1051     std::vector<ScoredSignature> ScoredSignatures;
1052     SigHelp.signatures.reserve(NumCandidates);
1053     ScoredSignatures.reserve(NumCandidates);
1054     // FIXME(rwols): How can we determine the "active overload candidate"?
1055     // Right now the overloaded candidates seem to be provided in a "best fit"
1056     // order, so I'm not too worried about this.
1057     SigHelp.activeSignature = 0;
1058     assert(CurrentArg <= (unsigned)std::numeric_limits<int>::max() &&
1059            "too many arguments");
1060
1061     SigHelp.activeParameter = static_cast<int>(CurrentArg);
1062
1063     for (unsigned I = 0; I < NumCandidates; ++I) {
1064       OverloadCandidate Candidate = Candidates[I];
1065       // We want to avoid showing instantiated signatures, because they may be
1066       // long in some cases (e.g. when 'T' is substituted with 'std::string', we
1067       // would get 'std::basic_string<char>').
1068       if (auto *Func = Candidate.getFunction()) {
1069         if (auto *Pattern = Func->getTemplateInstantiationPattern())
1070           Candidate = OverloadCandidate(Pattern);
1071       }
1072       if (static_cast<int>(I) == SigHelp.activeSignature) {
1073         // The activeParameter in LSP relates to the activeSignature. There is
1074         // another, per-signature field, but we currently do not use it and not
1075         // all clients might support it.
1076         // FIXME: Add support for per-signature activeParameter field.
1077         SigHelp.activeParameter =
1078             paramIndexForArg(Candidate, SigHelp.activeParameter);
1079       }
1080
1081       const auto *CCS = Candidate.CreateSignatureString(
1082           CurrentArg, S, *Allocator, CCTUInfo,
1083           /*IncludeBriefComments=*/true, Braced);
1084       assert(CCS && "Expected the CodeCompletionString to be non-null");
1085       ScoredSignatures.push_back(processOverloadCandidate(
1086           Candidate, *CCS,
1087           Candidate.getFunction()
1088               ? getDeclComment(S.getASTContext(), *Candidate.getFunction())
1089               : ""));
1090     }
1091
1092     // Sema does not load the docs from the preamble, so we need to fetch extra
1093     // docs from the index instead.
1094     llvm::DenseMap<SymbolID, std::string> FetchedDocs;
1095     if (Index) {
1096       LookupRequest IndexRequest;
1097       for (const auto &S : ScoredSignatures) {
1098         if (!S.IDForDoc)
1099           continue;
1100         IndexRequest.IDs.insert(S.IDForDoc);
1101       }
1102       Index->lookup(IndexRequest, [&](const Symbol &S) {
1103         if (!S.Documentation.empty())
1104           FetchedDocs[S.ID] = std::string(S.Documentation);
1105       });
1106       vlog("SigHelp: requested docs for {0} symbols from the index, got {1} "
1107            "symbols with non-empty docs in the response",
1108            IndexRequest.IDs.size(), FetchedDocs.size());
1109     }
1110
1111     llvm::sort(ScoredSignatures, [](const ScoredSignature &L,
1112                                     const ScoredSignature &R) {
1113       // Ordering follows:
1114       // - Less number of parameters is better.
1115       // - Aggregate > Function > FunctionType > FunctionTemplate
1116       // - High score is better.
1117       // - Shorter signature is better.
1118       // - Alphabetically smaller is better.
1119       if (L.Quality.NumberOfParameters != R.Quality.NumberOfParameters)
1120         return L.Quality.NumberOfParameters < R.Quality.NumberOfParameters;
1121       if (L.Quality.NumberOfOptionalParameters !=
1122           R.Quality.NumberOfOptionalParameters)
1123         return L.Quality.NumberOfOptionalParameters <
1124                R.Quality.NumberOfOptionalParameters;
1125       if (L.Quality.Kind != R.Quality.Kind) {
1126         using OC = CodeCompleteConsumer::OverloadCandidate;
1127         auto KindPriority = [&](OC::CandidateKind K) {
1128           switch (K) {
1129           case OC::CK_Aggregate:
1130             return 0;
1131           case OC::CK_Function:
1132             return 1;
1133           case OC::CK_FunctionType:
1134             return 2;
1135           case OC::CK_FunctionProtoTypeLoc:
1136             return 3;
1137           case OC::CK_FunctionTemplate:
1138             return 4;
1139           case OC::CK_Template:
1140             return 5;
1141           }
1142           llvm_unreachable("Unknown overload candidate type.");
1143         };
1144         return KindPriority(L.Quality.Kind) < KindPriority(R.Quality.Kind);
1145       }
1146       if (L.Signature.label.size() != R.Signature.label.size())
1147         return L.Signature.label.size() < R.Signature.label.size();
1148       return L.Signature.label < R.Signature.label;
1149     });
1150
1151     for (auto &SS : ScoredSignatures) {
1152       auto IndexDocIt =
1153           SS.IDForDoc ? FetchedDocs.find(SS.IDForDoc) : FetchedDocs.end();
1154       if (IndexDocIt != FetchedDocs.end()) {
1155         markup::Document SignatureComment;
1156         parseDocumentation(IndexDocIt->second, SignatureComment);
1157         SS.Signature.documentation =
1158             renderDoc(SignatureComment, DocumentationFormat);
1159       }
1160
1161       SigHelp.signatures.push_back(std::move(SS.Signature));
1162     }
1163   }
1164
1165   GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
1166
1167   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
1168
1169 private:
1170   void processParameterChunk(llvm::StringRef ChunkText,
1171                              SignatureInformation &Signature) const {
1172     // (!) this is O(n), should still be fast compared to building ASTs.
1173     unsigned ParamStartOffset = lspLength(Signature.label);
1174     unsigned ParamEndOffset = ParamStartOffset + lspLength(ChunkText);
1175     // A piece of text that describes the parameter that corresponds to
1176     // the code-completion location within a function call, message send,
1177     // macro invocation, etc.
1178     Signature.label += ChunkText;
1179     ParameterInformation Info;
1180     Info.labelOffsets.emplace(ParamStartOffset, ParamEndOffset);
1181     // FIXME: only set 'labelOffsets' when all clients migrate out of it.
1182     Info.labelString = std::string(ChunkText);
1183
1184     Signature.parameters.push_back(std::move(Info));
1185   }
1186
1187   void processOptionalChunk(const CodeCompletionString &CCS,
1188                             SignatureInformation &Signature,
1189                             SignatureQualitySignals &Signal) const {
1190     for (const auto &Chunk : CCS) {
1191       switch (Chunk.Kind) {
1192       case CodeCompletionString::CK_Optional:
1193         assert(Chunk.Optional &&
1194                "Expected the optional code completion string to be non-null.");
1195         processOptionalChunk(*Chunk.Optional, Signature, Signal);
1196         break;
1197       case CodeCompletionString::CK_VerticalSpace:
1198         break;
1199       case CodeCompletionString::CK_CurrentParameter:
1200       case CodeCompletionString::CK_Placeholder:
1201         processParameterChunk(Chunk.Text, Signature);
1202         Signal.NumberOfOptionalParameters++;
1203         break;
1204       default:
1205         Signature.label += Chunk.Text;
1206         break;
1207       }
1208     }
1209   }
1210
1211   // FIXME(ioeric): consider moving CodeCompletionString logic here to
1212   // CompletionString.h.
1213   ScoredSignature processOverloadCandidate(const OverloadCandidate &Candidate,
1214                                            const CodeCompletionString &CCS,
1215                                            llvm::StringRef DocComment) const {
1216     SignatureInformation Signature;
1217     SignatureQualitySignals Signal;
1218     const char *ReturnType = nullptr;
1219
1220     markup::Document OverloadComment;
1221     parseDocumentation(formatDocumentation(CCS, DocComment), OverloadComment);
1222     Signature.documentation = renderDoc(OverloadComment, DocumentationFormat);
1223     Signal.Kind = Candidate.getKind();
1224
1225     for (const auto &Chunk : CCS) {
1226       switch (Chunk.Kind) {
1227       case CodeCompletionString::CK_ResultType:
1228         // A piece of text that describes the type of an entity or,
1229         // for functions and methods, the return type.
1230         assert(!ReturnType && "Unexpected CK_ResultType");
1231         ReturnType = Chunk.Text;
1232         break;
1233       case CodeCompletionString::CK_CurrentParameter:
1234       case CodeCompletionString::CK_Placeholder:
1235         processParameterChunk(Chunk.Text, Signature);
1236         Signal.NumberOfParameters++;
1237         break;
1238       case CodeCompletionString::CK_Optional: {
1239         // The rest of the parameters are defaulted/optional.
1240         assert(Chunk.Optional &&
1241                "Expected the optional code completion string to be non-null.");
1242         processOptionalChunk(*Chunk.Optional, Signature, Signal);
1243         break;
1244       }
1245       case CodeCompletionString::CK_VerticalSpace:
1246         break;
1247       default:
1248         Signature.label += Chunk.Text;
1249         break;
1250       }
1251     }
1252     if (ReturnType) {
1253       Signature.label += " -> ";
1254       Signature.label += ReturnType;
1255     }
1256     dlog("Signal for {0}: {1}", Signature, Signal);
1257     ScoredSignature Result;
1258     Result.Signature = std::move(Signature);
1259     Result.Quality = Signal;
1260     const FunctionDecl *Func = Candidate.getFunction();
1261     if (Func && Result.Signature.documentation.value.empty()) {
1262       // Computing USR caches linkage, which may change after code completion.
1263       if (!hasUnstableLinkage(Func))
1264         Result.IDForDoc = clangd::getSymbolID(Func);
1265     }
1266     return Result;
1267   }
1268
1269   SignatureHelp &SigHelp;
1270   std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
1271   CodeCompletionTUInfo CCTUInfo;
1272   const SymbolIndex *Index;
1273   MarkupKind DocumentationFormat;
1274 }; // SignatureHelpCollector
1275
1276 // Used only for completion of C-style comments in function call (i.e.
1277 // /*foo=*/7). Similar to SignatureHelpCollector, but needs to do less work.
1278 class ParamNameCollector final : public CodeCompleteConsumer {
1279 public:
1280   ParamNameCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
1281                      std::set<std::string> &ParamNames)
1282       : CodeCompleteConsumer(CodeCompleteOpts),
1283         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
1284         CCTUInfo(Allocator), ParamNames(ParamNames) {}
1285
1286   void ProcessOverloadCandidates(Sema &S, unsigned CurrentArg,
1287                                  OverloadCandidate *Candidates,
1288                                  unsigned NumCandidates,
1289                                  SourceLocation OpenParLoc,
1290                                  bool Braced) override {
1291     assert(CurrentArg <= (unsigned)std::numeric_limits<int>::max() &&
1292            "too many arguments");
1293
1294     for (unsigned I = 0; I < NumCandidates; ++I) {
1295       if (const NamedDecl *ND = Candidates[I].getParamDecl(CurrentArg))
1296         if (const auto *II = ND->getIdentifier())
1297           ParamNames.emplace(II->getName());
1298     }
1299   }
1300
1301 private:
1302   GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
1303
1304   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
1305
1306   std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
1307   CodeCompletionTUInfo CCTUInfo;
1308   std::set<std::string> &ParamNames;
1309 };
1310
1311 struct SemaCompleteInput {
1312   PathRef FileName;
1313   size_t Offset;
1314   const PreambleData &Preamble;
1315   const std::optional<PreamblePatch> Patch;
1316   const ParseInputs &ParseInput;
1317 };
1318
1319 void loadMainFilePreambleMacros(const Preprocessor &PP,
1320                                 const PreambleData &Preamble) {
1321   // The ExternalPreprocessorSource has our macros, if we know where to look.
1322   // We can read all the macros using PreambleMacros->ReadDefinedMacros(),
1323   // but this includes transitively included files, so may deserialize a lot.
1324   ExternalPreprocessorSource *PreambleMacros = PP.getExternalSource();
1325   // As we have the names of the macros, we can look up their IdentifierInfo
1326   // and then use this to load just the macros we want.
1327   const auto &ITable = PP.getIdentifierTable();
1328   IdentifierInfoLookup *PreambleIdentifiers =
1329       ITable.getExternalIdentifierLookup();
1330
1331   if (!PreambleIdentifiers || !PreambleMacros)
1332     return;
1333   for (const auto &MacroName : Preamble.Macros.Names) {
1334     if (ITable.find(MacroName.getKey()) != ITable.end())
1335       continue;
1336     if (auto *II = PreambleIdentifiers->get(MacroName.getKey()))
1337       if (II->isOutOfDate())
1338         PreambleMacros->updateOutOfDateIdentifier(*II);
1339   }
1340 }
1341
1342 // Invokes Sema code completion on a file.
1343 // If \p Includes is set, it will be updated based on the compiler invocation.
1344 bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
1345                       const clang::CodeCompleteOptions &Options,
1346                       const SemaCompleteInput &Input,
1347                       IncludeStructure *Includes = nullptr) {
1348   trace::Span Tracer("Sema completion");
1349
1350   IgnoreDiagnostics IgnoreDiags;
1351   auto CI = buildCompilerInvocation(Input.ParseInput, IgnoreDiags);
1352   if (!CI) {
1353     elog("Couldn't create CompilerInvocation");
1354     return false;
1355   }
1356   auto &FrontendOpts = CI->getFrontendOpts();
1357   FrontendOpts.SkipFunctionBodies = true;
1358   // Disable typo correction in Sema.
1359   CI->getLangOpts().SpellChecking = false;
1360   // Code completion won't trigger in delayed template bodies.
1361   // This is on-by-default in windows to allow parsing SDK headers; we're only
1362   // disabling it for the main-file (not preamble).
1363   CI->getLangOpts().DelayedTemplateParsing = false;
1364   // Setup code completion.
1365   FrontendOpts.CodeCompleteOpts = Options;
1366   FrontendOpts.CodeCompletionAt.FileName = std::string(Input.FileName);
1367   std::tie(FrontendOpts.CodeCompletionAt.Line,
1368            FrontendOpts.CodeCompletionAt.Column) =
1369       offsetToClangLineColumn(Input.ParseInput.Contents, Input.Offset);
1370
1371   std::unique_ptr<llvm::MemoryBuffer> ContentsBuffer =
1372       llvm::MemoryBuffer::getMemBuffer(Input.ParseInput.Contents,
1373                                        Input.FileName);
1374   // The diagnostic options must be set before creating a CompilerInstance.
1375   CI->getDiagnosticOpts().IgnoreWarnings = true;
1376   // We reuse the preamble whether it's valid or not. This is a
1377   // correctness/performance tradeoff: building without a preamble is slow, and
1378   // completion is latency-sensitive.
1379   // However, if we're completing *inside* the preamble section of the draft,
1380   // overriding the preamble will break sema completion. Fortunately we can just
1381   // skip all includes in this case; these completions are really simple.
1382   PreambleBounds PreambleRegion =
1383       ComputePreambleBounds(CI->getLangOpts(), *ContentsBuffer, 0);
1384   bool CompletingInPreamble = Input.Offset < PreambleRegion.Size ||
1385                               (!PreambleRegion.PreambleEndsAtStartOfLine &&
1386                                Input.Offset == PreambleRegion.Size);
1387   if (Input.Patch)
1388     Input.Patch->apply(*CI);
1389   // NOTE: we must call BeginSourceFile after prepareCompilerInstance. Otherwise
1390   // the remapped buffers do not get freed.
1391   llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS =
1392       Input.ParseInput.TFS->view(Input.ParseInput.CompileCommand.Directory);
1393   if (Input.Preamble.StatCache)
1394     VFS = Input.Preamble.StatCache->getConsumingFS(std::move(VFS));
1395   auto Clang = prepareCompilerInstance(
1396       std::move(CI), !CompletingInPreamble ? &Input.Preamble.Preamble : nullptr,
1397       std::move(ContentsBuffer), std::move(VFS), IgnoreDiags);
1398   Clang->getPreprocessorOpts().SingleFileParseMode = CompletingInPreamble;
1399   Clang->setCodeCompletionConsumer(Consumer.release());
1400
1401   SyntaxOnlyAction Action;
1402   if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])) {
1403     log("BeginSourceFile() failed when running codeComplete for {0}",
1404         Input.FileName);
1405     return false;
1406   }
1407   // Macros can be defined within the preamble region of the main file.
1408   // They don't fall nicely into our index/Sema dichotomy:
1409   //  - they're not indexed for completion (they're not available across files)
1410   //  - but Sema code complete won't see them: as part of the preamble, they're
1411   //    deserialized only when mentioned.
1412   // Force them to be deserialized so SemaCodeComplete sees them.
1413   loadMainFilePreambleMacros(Clang->getPreprocessor(), Input.Preamble);
1414   if (Includes)
1415     Includes->collect(*Clang);
1416   if (llvm::Error Err = Action.Execute()) {
1417     log("Execute() failed when running codeComplete for {0}: {1}",
1418         Input.FileName, toString(std::move(Err)));
1419     return false;
1420   }
1421   Action.EndSourceFile();
1422
1423   return true;
1424 }
1425
1426 // Should we allow index completions in the specified context?
1427 bool allowIndex(CodeCompletionContext &CC) {
1428   if (!contextAllowsIndex(CC.getKind()))
1429     return false;
1430   // We also avoid ClassName::bar (but allow namespace::bar).
1431   auto Scope = CC.getCXXScopeSpecifier();
1432   if (!Scope)
1433     return true;
1434   NestedNameSpecifier *NameSpec = (*Scope)->getScopeRep();
1435   if (!NameSpec)
1436     return true;
1437   // We only query the index when qualifier is a namespace.
1438   // If it's a class, we rely solely on sema completions.
1439   switch (NameSpec->getKind()) {
1440   case NestedNameSpecifier::Global:
1441   case NestedNameSpecifier::Namespace:
1442   case NestedNameSpecifier::NamespaceAlias:
1443     return true;
1444   case NestedNameSpecifier::Super:
1445   case NestedNameSpecifier::TypeSpec:
1446   case NestedNameSpecifier::TypeSpecWithTemplate:
1447   // Unresolved inside a template.
1448   case NestedNameSpecifier::Identifier:
1449     return false;
1450   }
1451   llvm_unreachable("invalid NestedNameSpecifier kind");
1452 }
1453
1454 // Should we include a symbol from the index given the completion kind?
1455 // FIXME: Ideally we can filter in the fuzzy find request itself.
1456 bool includeSymbolFromIndex(CodeCompletionContext::Kind Kind,
1457                             const Symbol &Sym) {
1458   // Objective-C protocols are only useful in ObjC protocol completions,
1459   // in other places they're confusing, especially when they share the same
1460   // identifier with a class.
1461   if (Sym.SymInfo.Kind == index::SymbolKind::Protocol &&
1462       Sym.SymInfo.Lang == index::SymbolLanguage::ObjC)
1463     return Kind == CodeCompletionContext::CCC_ObjCProtocolName;
1464   else if (Kind == CodeCompletionContext::CCC_ObjCProtocolName)
1465     // Don't show anything else in ObjC protocol completions.
1466     return false;
1467
1468   if (Kind == CodeCompletionContext::CCC_ObjCClassForwardDecl)
1469     return Sym.SymInfo.Kind == index::SymbolKind::Class &&
1470            Sym.SymInfo.Lang == index::SymbolLanguage::ObjC;
1471   return true;
1472 }
1473
1474 std::future<std::pair<bool, SymbolSlab>>
1475 startAsyncFuzzyFind(const SymbolIndex &Index, const FuzzyFindRequest &Req) {
1476   return runAsync<std::pair<bool, SymbolSlab>>([&Index, Req]() {
1477     trace::Span Tracer("Async fuzzyFind");
1478     SymbolSlab::Builder Syms;
1479     bool Incomplete =
1480         Index.fuzzyFind(Req, [&Syms](const Symbol &Sym) { Syms.insert(Sym); });
1481     return std::make_pair(Incomplete, std::move(Syms).build());
1482   });
1483 }
1484
1485 // Creates a `FuzzyFindRequest` based on the cached index request from the
1486 // last completion, if any, and the speculated completion filter text in the
1487 // source code.
1488 FuzzyFindRequest speculativeFuzzyFindRequestForCompletion(
1489     FuzzyFindRequest CachedReq, const CompletionPrefix &HeuristicPrefix) {
1490   CachedReq.Query = std::string(HeuristicPrefix.Name);
1491   return CachedReq;
1492 }
1493
1494 // Runs Sema-based (AST) and Index-based completion, returns merged results.
1495 //
1496 // There are a few tricky considerations:
1497 //   - the AST provides information needed for the index query (e.g. which
1498 //     namespaces to search in). So Sema must start first.
1499 //   - we only want to return the top results (Opts.Limit).
1500 //     Building CompletionItems for everything else is wasteful, so we want to
1501 //     preserve the "native" format until we're done with scoring.
1502 //   - the data underlying Sema completion items is owned by the AST and various
1503 //     other arenas, which must stay alive for us to build CompletionItems.
1504 //   - we may get duplicate results from Sema and the Index, we need to merge.
1505 //
1506 // So we start Sema completion first, and do all our work in its callback.
1507 // We use the Sema context information to query the index.
1508 // Then we merge the two result sets, producing items that are Sema/Index/Both.
1509 // These items are scored, and the top N are synthesized into the LSP response.
1510 // Finally, we can clean up the data structures created by Sema completion.
1511 //
1512 // Main collaborators are:
1513 //   - semaCodeComplete sets up the compiler machinery to run code completion.
1514 //   - CompletionRecorder captures Sema completion results, including context.
1515 //   - SymbolIndex (Opts.Index) provides index completion results as Symbols
1516 //   - CompletionCandidates are the result of merging Sema and Index results.
1517 //     Each candidate points to an underlying CodeCompletionResult (Sema), a
1518 //     Symbol (Index), or both. It computes the result quality score.
1519 //     CompletionCandidate also does conversion to CompletionItem (at the end).
1520 //   - FuzzyMatcher scores how the candidate matches the partial identifier.
1521 //     This score is combined with the result quality score for the final score.
1522 //   - TopN determines the results with the best score.
1523 class CodeCompleteFlow {
1524   PathRef FileName;
1525   IncludeStructure Includes;           // Complete once the compiler runs.
1526   SpeculativeFuzzyFind *SpecFuzzyFind; // Can be nullptr.
1527   const CodeCompleteOptions &Opts;
1528
1529   // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
1530   CompletionRecorder *Recorder = nullptr;
1531   CodeCompletionContext::Kind CCContextKind = CodeCompletionContext::CCC_Other;
1532   bool IsUsingDeclaration = false;
1533   // The snippets will not be generated if the token following completion
1534   // location is an opening parenthesis (tok::l_paren) because this would add
1535   // extra parenthesis.
1536   tok::TokenKind NextTokenKind = tok::eof;
1537   // Counters for logging.
1538   int NSema = 0, NIndex = 0, NSemaAndIndex = 0, NIdent = 0;
1539   bool Incomplete = false; // Would more be available with a higher limit?
1540   CompletionPrefix HeuristicPrefix;
1541   std::optional<FuzzyMatcher> Filter; // Initialized once Sema runs.
1542   Range ReplacedRange;
1543   std::vector<std::string> QueryScopes; // Initialized once Sema runs.
1544   std::vector<std::string> AccessibleScopes; // Initialized once Sema runs.
1545   // Initialized once QueryScopes is initialized, if there are scopes.
1546   std::optional<ScopeDistance> ScopeProximity;
1547   std::optional<OpaqueType> PreferredType; // Initialized once Sema runs.
1548   // Whether to query symbols from any scope. Initialized once Sema runs.
1549   bool AllScopes = false;
1550   llvm::StringSet<> ContextWords;
1551   // Include-insertion and proximity scoring rely on the include structure.
1552   // This is available after Sema has run.
1553   std::optional<IncludeInserter> Inserter;  // Available during runWithSema.
1554   std::optional<URIDistance> FileProximity; // Initialized once Sema runs.
1555   /// Speculative request based on the cached request and the filter text before
1556   /// the cursor.
1557   /// Initialized right before sema run. This is only set if `SpecFuzzyFind` is
1558   /// set and contains a cached request.
1559   std::optional<FuzzyFindRequest> SpecReq;
1560
1561 public:
1562   // A CodeCompleteFlow object is only useful for calling run() exactly once.
1563   CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes,
1564                    SpeculativeFuzzyFind *SpecFuzzyFind,
1565                    const CodeCompleteOptions &Opts)
1566       : FileName(FileName), Includes(Includes), SpecFuzzyFind(SpecFuzzyFind),
1567         Opts(Opts) {}
1568
1569   CodeCompleteResult run(const SemaCompleteInput &SemaCCInput) && {
1570     trace::Span Tracer("CodeCompleteFlow");
1571     HeuristicPrefix = guessCompletionPrefix(SemaCCInput.ParseInput.Contents,
1572                                             SemaCCInput.Offset);
1573     populateContextWords(SemaCCInput.ParseInput.Contents);
1574     if (Opts.Index && SpecFuzzyFind && SpecFuzzyFind->CachedReq) {
1575       assert(!SpecFuzzyFind->Result.valid());
1576       SpecReq = speculativeFuzzyFindRequestForCompletion(
1577           *SpecFuzzyFind->CachedReq, HeuristicPrefix);
1578       SpecFuzzyFind->Result = startAsyncFuzzyFind(*Opts.Index, *SpecReq);
1579     }
1580
1581     // We run Sema code completion first. It builds an AST and calculates:
1582     //   - completion results based on the AST.
1583     //   - partial identifier and context. We need these for the index query.
1584     CodeCompleteResult Output;
1585     auto RecorderOwner = std::make_unique<CompletionRecorder>(Opts, [&]() {
1586       assert(Recorder && "Recorder is not set");
1587       CCContextKind = Recorder->CCContext.getKind();
1588       IsUsingDeclaration = Recorder->CCContext.isUsingDeclaration();
1589       auto Style = getFormatStyleForFile(SemaCCInput.FileName,
1590                                          SemaCCInput.ParseInput.Contents,
1591                                          *SemaCCInput.ParseInput.TFS);
1592       const auto NextToken = Lexer::findNextToken(
1593           Recorder->CCSema->getPreprocessor().getCodeCompletionLoc(),
1594           Recorder->CCSema->getSourceManager(), Recorder->CCSema->LangOpts);
1595       if (NextToken)
1596         NextTokenKind = NextToken->getKind();
1597       // If preprocessor was run, inclusions from preprocessor callback should
1598       // already be added to Includes.
1599       Inserter.emplace(
1600           SemaCCInput.FileName, SemaCCInput.ParseInput.Contents, Style,
1601           SemaCCInput.ParseInput.CompileCommand.Directory,
1602           &Recorder->CCSema->getPreprocessor().getHeaderSearchInfo());
1603       for (const auto &Inc : Includes.MainFileIncludes)
1604         Inserter->addExisting(Inc);
1605
1606       // Most of the cost of file proximity is in initializing the FileDistance
1607       // structures based on the observed includes, once per query. Conceptually
1608       // that happens here (though the per-URI-scheme initialization is lazy).
1609       // The per-result proximity scoring is (amortized) very cheap.
1610       FileDistanceOptions ProxOpts{}; // Use defaults.
1611       const auto &SM = Recorder->CCSema->getSourceManager();
1612       llvm::StringMap<SourceParams> ProxSources;
1613       auto MainFileID =
1614           Includes.getID(SM.getFileEntryForID(SM.getMainFileID()));
1615       assert(MainFileID);
1616       for (auto &HeaderIDAndDepth : Includes.includeDepth(*MainFileID)) {
1617         auto &Source =
1618             ProxSources[Includes.getRealPath(HeaderIDAndDepth.getFirst())];
1619         Source.Cost = HeaderIDAndDepth.getSecond() * ProxOpts.IncludeCost;
1620         // Symbols near our transitive includes are good, but only consider
1621         // things in the same directory or below it. Otherwise there can be
1622         // many false positives.
1623         if (HeaderIDAndDepth.getSecond() > 0)
1624           Source.MaxUpTraversals = 1;
1625       }
1626       FileProximity.emplace(ProxSources, ProxOpts);
1627
1628       Output = runWithSema();
1629       Inserter.reset(); // Make sure this doesn't out-live Clang.
1630       SPAN_ATTACH(Tracer, "sema_completion_kind",
1631                   getCompletionKindString(CCContextKind));
1632       log("Code complete: sema context {0}, query scopes [{1}] (AnyScope={2}), "
1633           "expected type {3}{4}",
1634           getCompletionKindString(CCContextKind),
1635           llvm::join(QueryScopes.begin(), QueryScopes.end(), ","), AllScopes,
1636           PreferredType ? Recorder->CCContext.getPreferredType().getAsString()
1637                         : "<none>",
1638           IsUsingDeclaration ? ", inside using declaration" : "");
1639     });
1640
1641     Recorder = RecorderOwner.get();
1642
1643     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
1644                      SemaCCInput, &Includes);
1645     logResults(Output, Tracer);
1646     return Output;
1647   }
1648
1649   void logResults(const CodeCompleteResult &Output, const trace::Span &Tracer) {
1650     SPAN_ATTACH(Tracer, "sema_results", NSema);
1651     SPAN_ATTACH(Tracer, "index_results", NIndex);
1652     SPAN_ATTACH(Tracer, "merged_results", NSemaAndIndex);
1653     SPAN_ATTACH(Tracer, "identifier_results", NIdent);
1654     SPAN_ATTACH(Tracer, "returned_results", int64_t(Output.Completions.size()));
1655     SPAN_ATTACH(Tracer, "incomplete", Output.HasMore);
1656     log("Code complete: {0} results from Sema, {1} from Index, "
1657         "{2} matched, {3} from identifiers, {4} returned{5}.",
1658         NSema, NIndex, NSemaAndIndex, NIdent, Output.Completions.size(),
1659         Output.HasMore ? " (incomplete)" : "");
1660     assert(!Opts.Limit || Output.Completions.size() <= Opts.Limit);
1661     // We don't assert that isIncomplete means we hit a limit.
1662     // Indexes may choose to impose their own limits even if we don't have one.
1663   }
1664
1665   CodeCompleteResult runWithoutSema(llvm::StringRef Content, size_t Offset,
1666                                     const ThreadsafeFS &TFS) && {
1667     trace::Span Tracer("CodeCompleteWithoutSema");
1668     // Fill in fields normally set by runWithSema()
1669     HeuristicPrefix = guessCompletionPrefix(Content, Offset);
1670     populateContextWords(Content);
1671     CCContextKind = CodeCompletionContext::CCC_Recovery;
1672     IsUsingDeclaration = false;
1673     Filter = FuzzyMatcher(HeuristicPrefix.Name);
1674     auto Pos = offsetToPosition(Content, Offset);
1675     ReplacedRange.start = ReplacedRange.end = Pos;
1676     ReplacedRange.start.character -= HeuristicPrefix.Name.size();
1677
1678     llvm::StringMap<SourceParams> ProxSources;
1679     ProxSources[FileName].Cost = 0;
1680     FileProximity.emplace(ProxSources);
1681
1682     auto Style = getFormatStyleForFile(FileName, Content, TFS);
1683     // This will only insert verbatim headers.
1684     Inserter.emplace(FileName, Content, Style,
1685                      /*BuildDir=*/"", /*HeaderSearchInfo=*/nullptr);
1686
1687     auto Identifiers = collectIdentifiers(Content, Style);
1688     std::vector<RawIdentifier> IdentifierResults;
1689     for (const auto &IDAndCount : Identifiers) {
1690       RawIdentifier ID;
1691       ID.Name = IDAndCount.first();
1692       ID.References = IDAndCount.second;
1693       // Avoid treating typed filter as an identifier.
1694       if (ID.Name == HeuristicPrefix.Name)
1695         --ID.References;
1696       if (ID.References > 0)
1697         IdentifierResults.push_back(std::move(ID));
1698     }
1699
1700     // Simplified version of getQueryScopes():
1701     //  - accessible scopes are determined heuristically.
1702     //  - all-scopes query if no qualifier was typed (and it's allowed).
1703     SpecifiedScope Scopes;
1704     Scopes.QueryScopes = visibleNamespaces(
1705         Content.take_front(Offset), format::getFormattingLangOpts(Style));
1706     for (std::string &S : Scopes.QueryScopes)
1707       if (!S.empty())
1708         S.append("::"); // visibleNamespaces doesn't include trailing ::.
1709     if (HeuristicPrefix.Qualifier.empty())
1710       AllScopes = Opts.AllScopes;
1711     else if (HeuristicPrefix.Qualifier.startswith("::")) {
1712       Scopes.QueryScopes = {""};
1713       Scopes.UnresolvedQualifier =
1714           std::string(HeuristicPrefix.Qualifier.drop_front(2));
1715     } else
1716       Scopes.UnresolvedQualifier = std::string(HeuristicPrefix.Qualifier);
1717     // First scope is the (modified) enclosing scope.
1718     QueryScopes = Scopes.scopesForIndexQuery();
1719     AccessibleScopes = QueryScopes;
1720     ScopeProximity.emplace(QueryScopes);
1721
1722     SymbolSlab IndexResults = Opts.Index ? queryIndex() : SymbolSlab();
1723
1724     CodeCompleteResult Output = toCodeCompleteResult(mergeResults(
1725         /*SemaResults=*/{}, IndexResults, IdentifierResults));
1726     Output.RanParser = false;
1727     logResults(Output, Tracer);
1728     return Output;
1729   }
1730
1731 private:
1732   void populateContextWords(llvm::StringRef Content) {
1733     // Take last 3 lines before the completion point.
1734     unsigned RangeEnd = HeuristicPrefix.Qualifier.begin() - Content.data(),
1735              RangeBegin = RangeEnd;
1736     for (size_t I = 0; I < 3 && RangeBegin > 0; ++I) {
1737       auto PrevNL = Content.rfind('\n', RangeBegin);
1738       if (PrevNL == StringRef::npos) {
1739         RangeBegin = 0;
1740         break;
1741       }
1742       RangeBegin = PrevNL;
1743     }
1744
1745     ContextWords = collectWords(Content.slice(RangeBegin, RangeEnd));
1746     dlog("Completion context words: {0}",
1747          llvm::join(ContextWords.keys(), ", "));
1748   }
1749
1750   // This is called by run() once Sema code completion is done, but before the
1751   // Sema data structures are torn down. It does all the real work.
1752   CodeCompleteResult runWithSema() {
1753     const auto &CodeCompletionRange = CharSourceRange::getCharRange(
1754         Recorder->CCSema->getPreprocessor().getCodeCompletionTokenRange());
1755     // When we are getting completions with an empty identifier, for example
1756     //    std::vector<int> asdf;
1757     //    asdf.^;
1758     // Then the range will be invalid and we will be doing insertion, use
1759     // current cursor position in such cases as range.
1760     if (CodeCompletionRange.isValid()) {
1761       ReplacedRange = halfOpenToRange(Recorder->CCSema->getSourceManager(),
1762                                       CodeCompletionRange);
1763     } else {
1764       const auto &Pos = sourceLocToPosition(
1765           Recorder->CCSema->getSourceManager(),
1766           Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
1767       ReplacedRange.start = ReplacedRange.end = Pos;
1768     }
1769     Filter = FuzzyMatcher(
1770         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
1771     auto SpecifiedScopes = getQueryScopes(
1772         Recorder->CCContext, *Recorder->CCSema, HeuristicPrefix, Opts);
1773
1774     QueryScopes = SpecifiedScopes.scopesForIndexQuery();
1775     AccessibleScopes = SpecifiedScopes.scopesForQualification();
1776     AllScopes = SpecifiedScopes.AllowAllScopes;
1777     if (!QueryScopes.empty())
1778       ScopeProximity.emplace(QueryScopes);
1779     PreferredType =
1780         OpaqueType::fromType(Recorder->CCSema->getASTContext(),
1781                              Recorder->CCContext.getPreferredType());
1782     // Sema provides the needed context to query the index.
1783     // FIXME: in addition to querying for extra/overlapping symbols, we should
1784     //        explicitly request symbols corresponding to Sema results.
1785     //        We can use their signals even if the index can't suggest them.
1786     // We must copy index results to preserve them, but there are at most Limit.
1787     auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext))
1788                             ? queryIndex()
1789                             : SymbolSlab();
1790     trace::Span Tracer("Populate CodeCompleteResult");
1791     // Merge Sema and Index results, score them, and pick the winners.
1792     auto Top =
1793         mergeResults(Recorder->Results, IndexResults, /*Identifiers*/ {});
1794     return toCodeCompleteResult(Top);
1795   }
1796
1797   CodeCompleteResult
1798   toCodeCompleteResult(const std::vector<ScoredBundle> &Scored) {
1799     CodeCompleteResult Output;
1800
1801     // Convert the results to final form, assembling the expensive strings.
1802     for (auto &C : Scored) {
1803       Output.Completions.push_back(toCodeCompletion(C.first));
1804       Output.Completions.back().Score = C.second;
1805       Output.Completions.back().CompletionTokenRange = ReplacedRange;
1806     }
1807     Output.HasMore = Incomplete;
1808     Output.Context = CCContextKind;
1809     Output.CompletionRange = ReplacedRange;
1810     return Output;
1811   }
1812
1813   SymbolSlab queryIndex() {
1814     trace::Span Tracer("Query index");
1815     SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit));
1816
1817     // Build the query.
1818     FuzzyFindRequest Req;
1819     if (Opts.Limit)
1820       Req.Limit = Opts.Limit;
1821     Req.Query = std::string(Filter->pattern());
1822     Req.RestrictForCodeCompletion = true;
1823     Req.Scopes = QueryScopes;
1824     Req.AnyScope = AllScopes;
1825     // FIXME: we should send multiple weighted paths here.
1826     Req.ProximityPaths.push_back(std::string(FileName));
1827     if (PreferredType)
1828       Req.PreferredTypes.push_back(std::string(PreferredType->raw()));
1829     vlog("Code complete: fuzzyFind({0:2})", toJSON(Req));
1830
1831     if (SpecFuzzyFind)
1832       SpecFuzzyFind->NewReq = Req;
1833     if (SpecFuzzyFind && SpecFuzzyFind->Result.valid() && (*SpecReq == Req)) {
1834       vlog("Code complete: speculative fuzzy request matches the actual index "
1835            "request. Waiting for the speculative index results.");
1836       SPAN_ATTACH(Tracer, "Speculative results", true);
1837
1838       trace::Span WaitSpec("Wait speculative results");
1839       auto SpecRes = SpecFuzzyFind->Result.get();
1840       Incomplete |= SpecRes.first;
1841       return std::move(SpecRes.second);
1842     }
1843
1844     SPAN_ATTACH(Tracer, "Speculative results", false);
1845
1846     // Run the query against the index.
1847     SymbolSlab::Builder ResultsBuilder;
1848     Incomplete |= Opts.Index->fuzzyFind(
1849         Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); });
1850     return std::move(ResultsBuilder).build();
1851   }
1852
1853   // Merges Sema and Index results where possible, to form CompletionCandidates.
1854   // \p Identifiers is raw identifiers that can also be completion candidates.
1855   // Identifiers are not merged with results from index or sema.
1856   // Groups overloads if desired, to form CompletionCandidate::Bundles. The
1857   // bundles are scored and top results are returned, best to worst.
1858   std::vector<ScoredBundle>
1859   mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
1860                const SymbolSlab &IndexResults,
1861                const std::vector<RawIdentifier> &IdentifierResults) {
1862     trace::Span Tracer("Merge and score results");
1863     std::vector<CompletionCandidate::Bundle> Bundles;
1864     llvm::DenseMap<size_t, size_t> BundleLookup;
1865     auto AddToBundles = [&](const CodeCompletionResult *SemaResult,
1866                             const Symbol *IndexResult,
1867                             const RawIdentifier *IdentifierResult) {
1868       CompletionCandidate C;
1869       C.SemaResult = SemaResult;
1870       C.IndexResult = IndexResult;
1871       C.IdentifierResult = IdentifierResult;
1872       if (C.IndexResult) {
1873         C.Name = IndexResult->Name;
1874         C.RankedIncludeHeaders = getRankedIncludes(*C.IndexResult);
1875       } else if (C.SemaResult) {
1876         C.Name = Recorder->getName(*SemaResult);
1877       } else {
1878         assert(IdentifierResult);
1879         C.Name = IdentifierResult->Name;
1880       }
1881       if (auto OverloadSet = C.overloadSet(
1882               Opts, FileName, Inserter ? &*Inserter : nullptr, CCContextKind)) {
1883         auto Ret = BundleLookup.try_emplace(OverloadSet, Bundles.size());
1884         if (Ret.second)
1885           Bundles.emplace_back();
1886         Bundles[Ret.first->second].push_back(std::move(C));
1887       } else {
1888         Bundles.emplace_back();
1889         Bundles.back().push_back(std::move(C));
1890       }
1891     };
1892     llvm::DenseSet<const Symbol *> UsedIndexResults;
1893     auto CorrespondingIndexResult =
1894         [&](const CodeCompletionResult &SemaResult) -> const Symbol * {
1895       if (auto SymID =
1896               getSymbolID(SemaResult, Recorder->CCSema->getSourceManager())) {
1897         auto I = IndexResults.find(SymID);
1898         if (I != IndexResults.end()) {
1899           UsedIndexResults.insert(&*I);
1900           return &*I;
1901         }
1902       }
1903       return nullptr;
1904     };
1905     // Emit all Sema results, merging them with Index results if possible.
1906     for (auto &SemaResult : SemaResults)
1907       AddToBundles(&SemaResult, CorrespondingIndexResult(SemaResult), nullptr);
1908     // Now emit any Index-only results.
1909     for (const auto &IndexResult : IndexResults) {
1910       if (UsedIndexResults.count(&IndexResult))
1911         continue;
1912       if (!includeSymbolFromIndex(CCContextKind, IndexResult))
1913         continue;
1914       AddToBundles(/*SemaResult=*/nullptr, &IndexResult, nullptr);
1915     }
1916     // Emit identifier results.
1917     for (const auto &Ident : IdentifierResults)
1918       AddToBundles(/*SemaResult=*/nullptr, /*IndexResult=*/nullptr, &Ident);
1919     // We only keep the best N results at any time, in "native" format.
1920     TopN<ScoredBundle, ScoredBundleGreater> Top(
1921         Opts.Limit == 0 ? std::numeric_limits<size_t>::max() : Opts.Limit);
1922     for (auto &Bundle : Bundles)
1923       addCandidate(Top, std::move(Bundle));
1924     return std::move(Top).items();
1925   }
1926
1927   std::optional<float> fuzzyScore(const CompletionCandidate &C) {
1928     // Macros can be very spammy, so we only support prefix completion.
1929     if (((C.SemaResult &&
1930           C.SemaResult->Kind == CodeCompletionResult::RK_Macro) ||
1931          (C.IndexResult &&
1932           C.IndexResult->SymInfo.Kind == index::SymbolKind::Macro)) &&
1933         !C.Name.starts_with_insensitive(Filter->pattern()))
1934       return std::nullopt;
1935     return Filter->match(C.Name);
1936   }
1937
1938   CodeCompletion::Scores
1939   evaluateCompletion(const SymbolQualitySignals &Quality,
1940                      const SymbolRelevanceSignals &Relevance) {
1941     using RM = CodeCompleteOptions::CodeCompletionRankingModel;
1942     CodeCompletion::Scores Scores;
1943     switch (Opts.RankingModel) {
1944     case RM::Heuristics:
1945       Scores.Quality = Quality.evaluateHeuristics();
1946       Scores.Relevance = Relevance.evaluateHeuristics();
1947       Scores.Total =
1948           evaluateSymbolAndRelevance(Scores.Quality, Scores.Relevance);
1949       // NameMatch is in fact a multiplier on total score, so rescoring is
1950       // sound.
1951       Scores.ExcludingName =
1952           Relevance.NameMatch > std::numeric_limits<float>::epsilon()
1953               ? Scores.Total / Relevance.NameMatch
1954               : Scores.Quality;
1955       return Scores;
1956
1957     case RM::DecisionForest:
1958       DecisionForestScores DFScores = Opts.DecisionForestScorer(
1959           Quality, Relevance, Opts.DecisionForestBase);
1960       Scores.ExcludingName = DFScores.ExcludingName;
1961       Scores.Total = DFScores.Total;
1962       return Scores;
1963     }
1964     llvm_unreachable("Unhandled CodeCompletion ranking model.");
1965   }
1966
1967   // Scores a candidate and adds it to the TopN structure.
1968   void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
1969                     CompletionCandidate::Bundle Bundle) {
1970     SymbolQualitySignals Quality;
1971     SymbolRelevanceSignals Relevance;
1972     Relevance.Context = CCContextKind;
1973     Relevance.Name = Bundle.front().Name;
1974     Relevance.FilterLength = HeuristicPrefix.Name.size();
1975     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
1976     Relevance.FileProximityMatch = &*FileProximity;
1977     if (ScopeProximity)
1978       Relevance.ScopeProximityMatch = &*ScopeProximity;
1979     if (PreferredType)
1980       Relevance.HadContextType = true;
1981     Relevance.ContextWords = &ContextWords;
1982     Relevance.MainFileSignals = Opts.MainFileSignals;
1983
1984     auto &First = Bundle.front();
1985     if (auto FuzzyScore = fuzzyScore(First))
1986       Relevance.NameMatch = *FuzzyScore;
1987     else
1988       return;
1989     SymbolOrigin Origin = SymbolOrigin::Unknown;
1990     bool FromIndex = false;
1991     for (const auto &Candidate : Bundle) {
1992       if (Candidate.IndexResult) {
1993         Quality.merge(*Candidate.IndexResult);
1994         Relevance.merge(*Candidate.IndexResult);
1995         Origin |= Candidate.IndexResult->Origin;
1996         FromIndex = true;
1997         if (!Candidate.IndexResult->Type.empty())
1998           Relevance.HadSymbolType |= true;
1999         if (PreferredType &&
2000             PreferredType->raw() == Candidate.IndexResult->Type) {
2001           Relevance.TypeMatchesPreferred = true;
2002         }
2003       }
2004       if (Candidate.SemaResult) {
2005         Quality.merge(*Candidate.SemaResult);
2006         Relevance.merge(*Candidate.SemaResult);
2007         if (PreferredType) {
2008           if (auto CompletionType = OpaqueType::fromCompletionResult(
2009                   Recorder->CCSema->getASTContext(), *Candidate.SemaResult)) {
2010             Relevance.HadSymbolType |= true;
2011             if (PreferredType == CompletionType)
2012               Relevance.TypeMatchesPreferred = true;
2013           }
2014         }
2015         Origin |= SymbolOrigin::AST;
2016       }
2017       if (Candidate.IdentifierResult) {
2018         Quality.References = Candidate.IdentifierResult->References;
2019         Relevance.Scope = SymbolRelevanceSignals::FileScope;
2020         Origin |= SymbolOrigin::Identifier;
2021       }
2022     }
2023
2024     CodeCompletion::Scores Scores = evaluateCompletion(Quality, Relevance);
2025     if (Opts.RecordCCResult)
2026       Opts.RecordCCResult(toCodeCompletion(Bundle), Quality, Relevance,
2027                           Scores.Total);
2028
2029     dlog("CodeComplete: {0} ({1}) = {2}\n{3}{4}\n", First.Name,
2030          llvm::to_string(Origin), Scores.Total, llvm::to_string(Quality),
2031          llvm::to_string(Relevance));
2032
2033     NSema += bool(Origin & SymbolOrigin::AST);
2034     NIndex += FromIndex;
2035     NSemaAndIndex += bool(Origin & SymbolOrigin::AST) && FromIndex;
2036     NIdent += bool(Origin & SymbolOrigin::Identifier);
2037     if (Candidates.push({std::move(Bundle), Scores}))
2038       Incomplete = true;
2039   }
2040
2041   CodeCompletion toCodeCompletion(const CompletionCandidate::Bundle &Bundle) {
2042     std::optional<CodeCompletionBuilder> Builder;
2043     for (const auto &Item : Bundle) {
2044       CodeCompletionString *SemaCCS =
2045           Item.SemaResult ? Recorder->codeCompletionString(*Item.SemaResult)
2046                           : nullptr;
2047       if (!Builder)
2048         Builder.emplace(Recorder ? &Recorder->CCSema->getASTContext() : nullptr,
2049                         Item, SemaCCS, AccessibleScopes, *Inserter, FileName,
2050                         CCContextKind, Opts, IsUsingDeclaration, NextTokenKind);
2051       else
2052         Builder->add(Item, SemaCCS, CCContextKind);
2053     }
2054     return Builder->build();
2055   }
2056 };
2057
2058 } // namespace
2059
2060 clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
2061   clang::CodeCompleteOptions Result;
2062   Result.IncludeCodePatterns = EnableSnippets;
2063   Result.IncludeMacros = true;
2064   Result.IncludeGlobals = true;
2065   // We choose to include full comments and not do doxygen parsing in
2066   // completion.
2067   // FIXME: ideally, we should support doxygen in some form, e.g. do markdown
2068   // formatting of the comments.
2069   Result.IncludeBriefComments = false;
2070
2071   // When an is used, Sema is responsible for completing the main file,
2072   // the index can provide results from the preamble.
2073   // Tell Sema not to deserialize the preamble to look for results.
2074   Result.LoadExternal = !Index;
2075   Result.IncludeFixIts = IncludeFixIts;
2076
2077   return Result;
2078 }
2079
2080 CompletionPrefix guessCompletionPrefix(llvm::StringRef Content,
2081                                        unsigned Offset) {
2082   assert(Offset <= Content.size());
2083   StringRef Rest = Content.take_front(Offset);
2084   CompletionPrefix Result;
2085
2086   // Consume the unqualified name. We only handle ASCII characters.
2087   // isAsciiIdentifierContinue will let us match "0invalid", but we don't mind.
2088   while (!Rest.empty() && isAsciiIdentifierContinue(Rest.back()))
2089     Rest = Rest.drop_back();
2090   Result.Name = Content.slice(Rest.size(), Offset);
2091
2092   // Consume qualifiers.
2093   while (Rest.consume_back("::") && !Rest.endswith(":")) // reject ::::
2094     while (!Rest.empty() && isAsciiIdentifierContinue(Rest.back()))
2095       Rest = Rest.drop_back();
2096   Result.Qualifier =
2097       Content.slice(Rest.size(), Result.Name.begin() - Content.begin());
2098
2099   return Result;
2100 }
2101
2102 // Code complete the argument name on "/*" inside function call.
2103 // Offset should be pointing to the start of the comment, i.e.:
2104 // foo(^/*, rather than foo(/*^) where the cursor probably is.
2105 CodeCompleteResult codeCompleteComment(PathRef FileName, unsigned Offset,
2106                                        llvm::StringRef Prefix,
2107                                        const PreambleData *Preamble,
2108                                        const ParseInputs &ParseInput) {
2109   if (Preamble == nullptr) // Can't run without Sema.
2110     return CodeCompleteResult();
2111
2112   clang::CodeCompleteOptions Options;
2113   Options.IncludeGlobals = false;
2114   Options.IncludeMacros = false;
2115   Options.IncludeCodePatterns = false;
2116   Options.IncludeBriefComments = false;
2117   std::set<std::string> ParamNames;
2118   // We want to see signatures coming from newly introduced includes, hence a
2119   // full patch.
2120   semaCodeComplete(
2121       std::make_unique<ParamNameCollector>(Options, ParamNames), Options,
2122       {FileName, Offset, *Preamble,
2123        PreamblePatch::createFullPatch(FileName, ParseInput, *Preamble),
2124        ParseInput});
2125   if (ParamNames.empty())
2126     return CodeCompleteResult();
2127
2128   CodeCompleteResult Result;
2129   Range CompletionRange;
2130   // Skip /*
2131   Offset += 2;
2132   CompletionRange.start = offsetToPosition(ParseInput.Contents, Offset);
2133   CompletionRange.end =
2134       offsetToPosition(ParseInput.Contents, Offset + Prefix.size());
2135   Result.CompletionRange = CompletionRange;
2136   Result.Context = CodeCompletionContext::CCC_NaturalLanguage;
2137   for (llvm::StringRef Name : ParamNames) {
2138     if (!Name.startswith(Prefix))
2139       continue;
2140     CodeCompletion Item;
2141     Item.Name = Name.str() + "=*/";
2142     Item.FilterText = Item.Name;
2143     Item.Kind = CompletionItemKind::Text;
2144     Item.CompletionTokenRange = CompletionRange;
2145     Item.Origin = SymbolOrigin::AST;
2146     Result.Completions.push_back(Item);
2147   }
2148
2149   return Result;
2150 }
2151
2152 // If Offset is inside what looks like argument comment (e.g.
2153 // "/*^" or "/* foo^"), returns new offset pointing to the start of the /*
2154 // (place where semaCodeComplete should run).
2155 std::optional<unsigned>
2156 maybeFunctionArgumentCommentStart(llvm::StringRef Content) {
2157   while (!Content.empty() && isAsciiIdentifierContinue(Content.back()))
2158     Content = Content.drop_back();
2159   Content = Content.rtrim();
2160   if (Content.endswith("/*"))
2161     return Content.size() - 2;
2162   return std::nullopt;
2163 }
2164
2165 CodeCompleteResult codeComplete(PathRef FileName, Position Pos,
2166                                 const PreambleData *Preamble,
2167                                 const ParseInputs &ParseInput,
2168                                 CodeCompleteOptions Opts,
2169                                 SpeculativeFuzzyFind *SpecFuzzyFind) {
2170   auto Offset = positionToOffset(ParseInput.Contents, Pos);
2171   if (!Offset) {
2172     elog("Code completion position was invalid {0}", Offset.takeError());
2173     return CodeCompleteResult();
2174   }
2175
2176   auto Content = llvm::StringRef(ParseInput.Contents).take_front(*Offset);
2177   if (auto OffsetBeforeComment = maybeFunctionArgumentCommentStart(Content)) {
2178     // We are doing code completion of a comment, where we currently only
2179     // support completing param names in function calls. To do this, we
2180     // require information from Sema, but Sema's comment completion stops at
2181     // parsing, so we must move back the position before running it, extract
2182     // information we need and construct completion items ourselves.
2183     auto CommentPrefix = Content.substr(*OffsetBeforeComment + 2).trim();
2184     return codeCompleteComment(FileName, *OffsetBeforeComment, CommentPrefix,
2185                                Preamble, ParseInput);
2186   }
2187
2188   auto Flow = CodeCompleteFlow(
2189       FileName, Preamble ? Preamble->Includes : IncludeStructure(),
2190       SpecFuzzyFind, Opts);
2191   return (!Preamble || Opts.RunParser == CodeCompleteOptions::NeverParse)
2192              ? std::move(Flow).runWithoutSema(ParseInput.Contents, *Offset,
2193                                               *ParseInput.TFS)
2194              : std::move(Flow).run({FileName, *Offset, *Preamble,
2195                                     /*PreamblePatch=*/
2196                                     PreamblePatch::createMacroPatch(
2197                                         FileName, ParseInput, *Preamble),
2198                                     ParseInput});
2199 }
2200
2201 SignatureHelp signatureHelp(PathRef FileName, Position Pos,
2202                             const PreambleData &Preamble,
2203                             const ParseInputs &ParseInput,
2204                             MarkupKind DocumentationFormat) {
2205   auto Offset = positionToOffset(ParseInput.Contents, Pos);
2206   if (!Offset) {
2207     elog("Signature help position was invalid {0}", Offset.takeError());
2208     return SignatureHelp();
2209   }
2210   SignatureHelp Result;
2211   clang::CodeCompleteOptions Options;
2212   Options.IncludeGlobals = false;
2213   Options.IncludeMacros = false;
2214   Options.IncludeCodePatterns = false;
2215   Options.IncludeBriefComments = false;
2216   semaCodeComplete(
2217       std::make_unique<SignatureHelpCollector>(Options, DocumentationFormat,
2218                                                ParseInput.Index, Result),
2219       Options,
2220       {FileName, *Offset, Preamble,
2221        PreamblePatch::createFullPatch(FileName, ParseInput, Preamble),
2222        ParseInput});
2223   return Result;
2224 }
2225
2226 bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx) {
2227   auto InTopLevelScope = [](const NamedDecl &ND) {
2228     switch (ND.getDeclContext()->getDeclKind()) {
2229     case Decl::TranslationUnit:
2230     case Decl::Namespace:
2231     case Decl::LinkageSpec:
2232       return true;
2233     default:
2234       break;
2235     };
2236     return false;
2237   };
2238   auto InClassScope = [](const NamedDecl &ND) {
2239     return ND.getDeclContext()->getDeclKind() == Decl::CXXRecord;
2240   };
2241   // We only complete symbol's name, which is the same as the name of the
2242   // *primary* template in case of template specializations.
2243   if (isExplicitTemplateSpecialization(&ND))
2244     return false;
2245
2246   // Category decls are not useful on their own outside the interface or
2247   // implementation blocks. Moreover, sema already provides completion for
2248   // these, even if it requires preamble deserialization. So by excluding them
2249   // from the index, we reduce the noise in all the other completion scopes.
2250   if (llvm::isa<ObjCCategoryDecl>(&ND) || llvm::isa<ObjCCategoryImplDecl>(&ND))
2251     return false;
2252
2253   if (InTopLevelScope(ND))
2254     return true;
2255
2256   // Always index enum constants, even if they're not in the top level scope:
2257   // when
2258   // --all-scopes-completion is set, we'll want to complete those as well.
2259   if (const auto *EnumDecl = dyn_cast<clang::EnumDecl>(ND.getDeclContext()))
2260     return (InTopLevelScope(*EnumDecl) || InClassScope(*EnumDecl));
2261
2262   return false;
2263 }
2264
2265 CompletionItem CodeCompletion::render(const CodeCompleteOptions &Opts) const {
2266   CompletionItem LSP;
2267   const auto *InsertInclude = Includes.empty() ? nullptr : &Includes[0];
2268   // We could move our indicators from label into labelDetails->description.
2269   // In VSCode there are rendering issues that prevent these being aligned.
2270   LSP.label = ((InsertInclude && InsertInclude->Insertion)
2271                    ? Opts.IncludeIndicator.Insert
2272                    : Opts.IncludeIndicator.NoInsert) +
2273               (Opts.ShowOrigins ? "[" + llvm::to_string(Origin) + "]" : "") +
2274               RequiredQualifier + Name;
2275   LSP.labelDetails.emplace();
2276   LSP.labelDetails->detail = Signature;
2277
2278   LSP.kind = Kind;
2279   LSP.detail = BundleSize > 1
2280                    ? std::string(llvm::formatv("[{0} overloads]", BundleSize))
2281                    : ReturnType;
2282   LSP.deprecated = Deprecated;
2283   // Combine header information and documentation in LSP `documentation` field.
2284   // This is not quite right semantically, but tends to display well in editors.
2285   if (InsertInclude || Documentation) {
2286     markup::Document Doc;
2287     if (InsertInclude)
2288       Doc.addParagraph().appendText("From ").appendCode(InsertInclude->Header);
2289     if (Documentation)
2290       Doc.append(*Documentation);
2291     LSP.documentation = renderDoc(Doc, Opts.DocumentationFormat);
2292   }
2293   LSP.sortText = sortText(Score.Total, FilterText);
2294   LSP.filterText = FilterText;
2295   LSP.textEdit = {CompletionTokenRange, RequiredQualifier + Name, ""};
2296   // Merge continuous additionalTextEdits into main edit. The main motivation
2297   // behind this is to help LSP clients, it seems most of them are confused when
2298   // they are provided with additionalTextEdits that are consecutive to main
2299   // edit.
2300   // Note that we store additional text edits from back to front in a line. That
2301   // is mainly to help LSP clients again, so that changes do not effect each
2302   // other.
2303   for (const auto &FixIt : FixIts) {
2304     if (FixIt.range.end == LSP.textEdit->range.start) {
2305       LSP.textEdit->newText = FixIt.newText + LSP.textEdit->newText;
2306       LSP.textEdit->range.start = FixIt.range.start;
2307     } else {
2308       LSP.additionalTextEdits.push_back(FixIt);
2309     }
2310   }
2311   if (Opts.EnableSnippets)
2312     LSP.textEdit->newText += SnippetSuffix;
2313
2314   // FIXME(kadircet): Do not even fill insertText after making sure textEdit is
2315   // compatible with most of the editors.
2316   LSP.insertText = LSP.textEdit->newText;
2317   // Some clients support snippets but work better with plaintext.
2318   // So if the snippet is trivial, let the client know.
2319   // https://github.com/clangd/clangd/issues/922
2320   LSP.insertTextFormat = (Opts.EnableSnippets && !SnippetSuffix.empty())
2321                              ? InsertTextFormat::Snippet
2322                              : InsertTextFormat::PlainText;
2323   if (InsertInclude && InsertInclude->Insertion)
2324     LSP.additionalTextEdits.push_back(*InsertInclude->Insertion);
2325
2326   LSP.score = Score.ExcludingName;
2327
2328   return LSP;
2329 }
2330
2331 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const CodeCompletion &C) {
2332   // For now just lean on CompletionItem.
2333   return OS << C.render(CodeCompleteOptions());
2334 }
2335
2336 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
2337                               const CodeCompleteResult &R) {
2338   OS << "CodeCompleteResult: " << R.Completions.size() << (R.HasMore ? "+" : "")
2339      << " (" << getCompletionKindString(R.Context) << ")"
2340      << " items:\n";
2341   for (const auto &C : R.Completions)
2342     OS << C << "\n";
2343   return OS;
2344 }
2345
2346 // Heuristically detect whether the `Line` is an unterminated include filename.
2347 bool isIncludeFile(llvm::StringRef Line) {
2348   Line = Line.ltrim();
2349   if (!Line.consume_front("#"))
2350     return false;
2351   Line = Line.ltrim();
2352   if (!(Line.consume_front("include_next") || Line.consume_front("include") ||
2353         Line.consume_front("import")))
2354     return false;
2355   Line = Line.ltrim();
2356   if (Line.consume_front("<"))
2357     return Line.count('>') == 0;
2358   if (Line.consume_front("\""))
2359     return Line.count('"') == 0;
2360   return false;
2361 }
2362
2363 bool allowImplicitCompletion(llvm::StringRef Content, unsigned Offset) {
2364   // Look at last line before completion point only.
2365   Content = Content.take_front(Offset);
2366   auto Pos = Content.rfind('\n');
2367   if (Pos != llvm::StringRef::npos)
2368     Content = Content.substr(Pos + 1);
2369
2370   // Complete after scope operators.
2371   if (Content.endswith(".") || Content.endswith("->") ||
2372       Content.endswith("::") || Content.endswith("/*"))
2373     return true;
2374   // Complete after `#include <` and #include `<foo/`.
2375   if ((Content.endswith("<") || Content.endswith("\"") ||
2376        Content.endswith("/")) &&
2377       isIncludeFile(Content))
2378     return true;
2379
2380   // Complete words. Give non-ascii characters the benefit of the doubt.
2381   return !Content.empty() && (isAsciiIdentifierContinue(Content.back()) ||
2382                               !llvm::isASCII(Content.back()));
2383 }
2384
2385 } // namespace clangd
2386 } // namespace clang