CodeComplete.cpp | Explore in Territory

//===--- CodeComplete.cpp ----------------------------------------*- C++-*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Code completion has several moving parts:
//  - AST-based completions are provided using the completion hooks in Sema.
//  - external completions are retrieved from the index (using hints from Sema)
//  - the two sources overlap, and must be merged and overloads bundled
//  - results must be scored and ranked (see Quality.h) before rendering
//
// Signature help works in a similar way as code completion, but it is simpler:
// it's purely AST-based, and there are few candidates.
//
//===----------------------------------------------------------------------===//

#include "CodeComplete.h"
#include "AST.h"
#include "CodeCompletionStrings.h"
#include "Compiler.h"
#include "ExpectedTypes.h"
#include "Feature.h"
#include "FileDistance.h"
#include "FuzzyMatch.h"
#include "Headers.h"
#include "Hover.h"
#include "Preamble.h"
#include "Protocol.h"
#include "Quality.h"
#include "SourceCode.h"
#include "URI.h"
#include "index/Index.h"
#include "index/Symbol.h"
#include "index/SymbolOrigin.h"
#include "support/Logger.h"
#include "support/Markup.h"
#include "support/Threading.h"
#include "support/ThreadsafeFS.h"
#include "support/Trace.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclBase.h"
#include "clang/Basic/CharInfo.h"
#include "clang/Basic/LangOptions.h"
#include "clang/Basic/SourceLocation.h"
#include "clang/Basic/TokenKinds.h"
#include "clang/Format/Format.h"
#include "clang/Frontend/CompilerInstance.h"
#include "clang/Frontend/FrontendActions.h"
#include "clang/Lex/ExternalPreprocessorSource.h"
#include "clang/Lex/Lexer.h"
#include "clang/Lex/Preprocessor.h"
#include "clang/Lex/PreprocessorOptions.h"
#include "clang/Sema/CodeCompleteConsumer.h"
#include "clang/Sema/DeclSpec.h"
#include "clang/Sema/Sema.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/ScopedPrinter.h"
#include <algorithm>
#include <iterator>
#include <limits>
#include <optional>
#include <utility>

// We log detailed candidate here if you run with -debug-only=codecomplete.
#define DEBUG_TYPE …

namespace clang {
namespace clangd {

#if CLANGD_DECISION_FOREST
const CodeCompleteOptions::CodeCompletionRankingModel
    CodeCompleteOptions::DefaultRankingModel = …;
#else
const CodeCompleteOptions::CodeCompletionRankingModel
    CodeCompleteOptions::DefaultRankingModel = CodeCompleteOptions::Heuristics;
#endif

namespace {

// Note: changes to this function should also be reflected in the
// CodeCompletionResult overload where appropriate.
CompletionItemKind
toCompletionItemKind(index::SymbolKind Kind,
                     const llvm::StringRef *Signature = nullptr) { … }

// Note: changes to this function should also be reflected in the
// index::SymbolKind overload where appropriate.
CompletionItemKind toCompletionItemKind(const CodeCompletionResult &Res,
                                        CodeCompletionContext::Kind CtxKind) { … }

// FIXME: find a home for this (that can depend on both markup and Protocol).
MarkupContent renderDoc(const markup::Document &Doc, MarkupKind Kind) { … }

Symbol::IncludeDirective insertionDirective(const CodeCompleteOptions &Opts) { … }

// Identifier code completion result.
struct RawIdentifier { … };

/// A code completion result, in clang-native form.
/// It may be promoted to a CompletionItem if it's among the top-ranked results.
struct CompletionCandidate { … };
ScoredBundle;
struct ScoredBundleGreater { … };

// Remove the first template argument from Signature.
// If Signature only contains a single argument an empty string is returned.
std::string removeFirstTemplateArg(llvm::StringRef Signature) { … }

// Assembles a code completion out of a bundle of >=1 completion candidates.
// Many of the expensive strings are only computed at this point, once we know
// the candidate bundle is going to be returned.
//
// Many fields are the same for all candidates in a bundle (e.g. name), and are
// computed from the first candidate, in the constructor.
// Others vary per candidate, so add() must be called for remaining candidates.
struct CodeCompletionBuilder { … };

// Determine the symbol ID for a Sema code completion result, if possible.
SymbolID getSymbolID(const CodeCompletionResult &R, const SourceManager &SM) { … }

// Scopes of the partial identifier we're trying to complete.
// It is used when we query the index for more completion results.
struct SpecifiedScope { … };

// Get all scopes that will be queried in indexes and whether symbols from
// any scope is allowed. The first scope in the list is the preferred scope
// (e.g. enclosing namespace).
SpecifiedScope getQueryScopes(CodeCompletionContext &CCContext,
                              const Sema &CCSema,
                              const CompletionPrefix &HeuristicPrefix,
                              const CodeCompleteOptions &Opts) { … }

// Should we perform index-based completion in a context of the specified kind?
// FIXME: consider allowing completion, but restricting the result types.
bool contextAllowsIndex(enum CodeCompletionContext::Kind K) { … }

static bool isInjectedClass(const NamedDecl &D) { … }

// Some member calls are excluded because they're so rarely useful.
static bool isExcludedMember(const NamedDecl &D) { … }

// The CompletionRecorder captures Sema code-complete output, including context.
// It filters out ignored results (but doesn't apply fuzzy-filtering yet).
// It doesn't do scoring or conversion to CompletionItem yet, as we want to
// merge with index results first.
// Generally the fields and methods of this object should only be used from
// within the callback.
struct CompletionRecorder : public CodeCompleteConsumer { … };

struct ScoredSignature { … };

// Returns the index of the parameter matching argument number "Arg.
// This is usually just "Arg", except for variadic functions/templates, where
// "Arg" might be higher than the number of parameters. When that happens, we
// assume the last parameter is variadic and assume all further args are
// part of it.
int paramIndexForArg(const CodeCompleteConsumer::OverloadCandidate &Candidate,
                     int Arg) { … }

class SignatureHelpCollector final : public CodeCompleteConsumer { … }; // SignatureHelpCollector

// Used only for completion of C-style comments in function call (i.e.
// /*foo=*/7). Similar to SignatureHelpCollector, but needs to do less work.
class ParamNameCollector final : public CodeCompleteConsumer { … };

struct SemaCompleteInput { … };

void loadMainFilePreambleMacros(const Preprocessor &PP,
                                const PreambleData &Preamble) { … }

// Invokes Sema code completion on a file.
// If \p Includes is set, it will be updated based on the compiler invocation.
bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
                      const clang::CodeCompleteOptions &Options,
                      const SemaCompleteInput &Input,
                      IncludeStructure *Includes = nullptr) { … }

// Should we allow index completions in the specified context?
bool allowIndex(CodeCompletionContext &CC) { … }

// Should we include a symbol from the index given the completion kind?
// FIXME: Ideally we can filter in the fuzzy find request itself.
bool includeSymbolFromIndex(CodeCompletionContext::Kind Kind,
                            const Symbol &Sym) { … }

std::future<std::pair<bool, SymbolSlab>>
startAsyncFuzzyFind(const SymbolIndex &Index, const FuzzyFindRequest &Req) { … }

// Creates a `FuzzyFindRequest` based on the cached index request from the
// last completion, if any, and the speculated completion filter text in the
// source code.
FuzzyFindRequest speculativeFuzzyFindRequestForCompletion(
    FuzzyFindRequest CachedReq, const CompletionPrefix &HeuristicPrefix) { … }

// This function is similar to Lexer::findNextToken(), but assumes
// that the input SourceLocation is the completion point (which is
// a case findNextToken() does not handle).
std::optional<Token>
findTokenAfterCompletionPoint(SourceLocation CompletionPoint,
                              const SourceManager &SM,
                              const LangOptions &LangOpts) { … }

// Runs Sema-based (AST) and Index-based completion, returns merged results.
//
// There are a few tricky considerations:
//   - the AST provides information needed for the index query (e.g. which
//     namespaces to search in). So Sema must start first.
//   - we only want to return the top results (Opts.Limit).
//     Building CompletionItems for everything else is wasteful, so we want to
//     preserve the "native" format until we're done with scoring.
//   - the data underlying Sema completion items is owned by the AST and various
//     other arenas, which must stay alive for us to build CompletionItems.
//   - we may get duplicate results from Sema and the Index, we need to merge.
//
// So we start Sema completion first, and do all our work in its callback.
// We use the Sema context information to query the index.
// Then we merge the two result sets, producing items that are Sema/Index/Both.
// These items are scored, and the top N are synthesized into the LSP response.
// Finally, we can clean up the data structures created by Sema completion.
//
// Main collaborators are:
//   - semaCodeComplete sets up the compiler machinery to run code completion.
//   - CompletionRecorder captures Sema completion results, including context.
//   - SymbolIndex (Opts.Index) provides index completion results as Symbols
//   - CompletionCandidates are the result of merging Sema and Index results.
//     Each candidate points to an underlying CodeCompletionResult (Sema), a
//     Symbol (Index), or both. It computes the result quality score.
//     CompletionCandidate also does conversion to CompletionItem (at the end).
//   - FuzzyMatcher scores how the candidate matches the partial identifier.
//     This score is combined with the result quality score for the final score.
//   - TopN determines the results with the best score.
class CodeCompleteFlow { … };

} // namespace

clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const { … }

CompletionPrefix guessCompletionPrefix(llvm::StringRef Content,
                                       unsigned Offset) { … }

// Code complete the argument name on "/*" inside function call.
// Offset should be pointing to the start of the comment, i.e.:
// foo(^/*, rather than foo(/*^) where the cursor probably is.
CodeCompleteResult codeCompleteComment(PathRef FileName, unsigned Offset,
                                       llvm::StringRef Prefix,
                                       const PreambleData *Preamble,
                                       const ParseInputs &ParseInput) { … }

// If Offset is inside what looks like argument comment (e.g.
// "/*^" or "/* foo^"), returns new offset pointing to the start of the /*
// (place where semaCodeComplete should run).
std::optional<unsigned>
maybeFunctionArgumentCommentStart(llvm::StringRef Content) { … }

CodeCompleteResult codeComplete(PathRef FileName, Position Pos,
                                const PreambleData *Preamble,
                                const ParseInputs &ParseInput,
                                CodeCompleteOptions Opts,
                                SpeculativeFuzzyFind *SpecFuzzyFind) { … }

SignatureHelp signatureHelp(PathRef FileName, Position Pos,
                            const PreambleData &Preamble,
                            const ParseInputs &ParseInput,
                            MarkupKind DocumentationFormat) { … }

bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx) { … }

CompletionItem CodeCompletion::render(const CodeCompleteOptions &Opts) const { … }

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const CodeCompletion &C) { … }

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                              const CodeCompleteResult &R) { … }

// Heuristically detect whether the `Line` is an unterminated include filename.
bool isIncludeFile(llvm::StringRef Line) { … }

bool allowImplicitCompletion(llvm::StringRef Content, unsigned Offset) { … }

} // namespace clangd
} // namespace clang
llvm/clang-tools-extra/clangd/CodeComplete.cpp
