brintos / llvm-project-archived public Read only

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