[clangd] Track origins of symbols (various indexes, Sema).

[sammccall]

Summary

Surface it in the completion items C++ API, and when a flag is set.

[ioeric]

lgtm. neat!

clangd/index/Index.cpp

50

nit: constexpr?

clangd/CodeComplete.h

struct CodeCompleteOptions {
 
   /// A visual indicator to prepend to the completion label to indicate whether
   /// completion result would trigger an #include insertion or not.
   struct IncludeInsertionIndicator {
     std::string Insert = "•";
     std::string NoInsert = " ";
   } IncludeIndicator;
 
+  /// Expose origins of completion items in the label (for debugging).
+  bool ShowOrigins = false;
+
   // Populated internally by clangd, do not set.
   /// If `Index` is set, it is used to augment the code completion
   /// results.
   /// FIXME(ioeric): we might want a better way to pass the index around inside
   /// clangd.
   const SymbolIndex *Index = nullptr;
 };
 
struct CodeCompletion {
   // the same way, such as function overloads. In this case BundleSize > 1, and
   // the following fields are summaries:
   //  - Signature is e.g. "(...)" for functions.
   //  - SnippetSuffix is similarly e.g. "(${0})".
   //  - ReturnType may be empty
   //  - Documentation may be from one symbol, or a combination of several
   // Other fields should apply equally to all bundled completions.
   unsigned BundleSize = 1;
+  SymbolOrigin Origin = SymbolOrigin::Unknown;
   // The header through which this symbol could be included.
   // Quoted string as expected by an #include directive, e.g. "<memory>".
   // Empty for non-symbol completions, or when not known.
   std::string Header;
   // Present if Header is set and should be inserted to use this item.
   llvm::Optional<TextEdit> HeaderInsertion;
 
   // Scores are used to rank completion items.

clangd/CodeComplete.cpp

 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Index/USRGeneration.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/Support/Format.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include <queue>
 
 // We log detailed candidate here if you run with -debug-only=codecomplete.
 #define DEBUG_TYPE "CodeComplete"
 
 namespace clang {
 namespace clangd {
 namespace {

 struct CodeCompletionBuilder {
   CodeCompletionBuilder(ASTContext &ASTCtx, const CompletionCandidate &C,
                         CodeCompletionString *SemaCCS,
                         const IncludeInserter &Includes, StringRef FileName,
                         const CodeCompleteOptions &Opts)
       : ASTCtx(ASTCtx), ExtractDocumentation(Opts.IncludeComments) {
     add(C, SemaCCS);
     if (C.SemaResult) {
+      Completion.Origin =
+          static_cast<SymbolOrigin>(Completion.Origin | SymbolOrigin::AST);
       Completion.Name = llvm::StringRef(SemaCCS->getTypedText());
       if (Completion.Scope.empty())
         if (C.SemaResult->Kind == CodeCompletionResult::RK_Declaration)
           if (const auto *D = C.SemaResult->getDeclaration())
             if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
               Completion.Scope =
                   splitQualifiedName(printQualifiedName(*ND)).first;
       Completion.Kind =
           toCompletionItemKind(C.SemaResult->Kind, C.SemaResult->Declaration);
     }
     if (C.IndexResult) {
+      Completion.Origin =
+          static_cast<SymbolOrigin>(Completion.Origin | C.IndexResult->Origin);
       if (Completion.Scope.empty())
         Completion.Scope = C.IndexResult->Scope;
       if (Completion.Kind == CompletionItemKind::Missing)
         Completion.Kind = toCompletionItemKind(C.IndexResult->SymInfo.Kind);
       if (Completion.Name.empty())
         Completion.Name = C.IndexResult->Name;
     }
     if (auto Inserted = C.headerToInsertIfNotPresent()) {
void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
     // FIXME: re-enable this after working out why it eats memory.
     // Relevance.FileProximityMatch = FileProximity.getPointer();
     auto &First = Bundle.front();
     if (auto FuzzyScore = fuzzyScore(First))
       Relevance.NameMatch = *FuzzyScore;
     else
       return;
-    unsigned SemaResult = 0, IndexResult = 0;
+    SymbolOrigin Origin = SymbolOrigin::Unknown;
     for (const auto &Candidate : Bundle) {
       if (Candidate.IndexResult) {
         Quality.merge(*Candidate.IndexResult);
         Relevance.merge(*Candidate.IndexResult);
-        ++IndexResult;
+        Origin =
+            static_cast<SymbolOrigin>(Origin | Candidate.IndexResult->Origin);
       }
       if (Candidate.SemaResult) {
         Quality.merge(*Candidate.SemaResult);
         Relevance.merge(*Candidate.SemaResult);
-        ++SemaResult;
+        Origin = static_cast<SymbolOrigin>(Origin | SymbolOrigin::AST);
       }
     }
 
     CodeCompletion::Scores Scores;
     Scores.Quality = Quality.evaluate();
     Scores.Relevance = Relevance.evaluate();
     Scores.Total = evaluateSymbolAndRelevance(Scores.Quality, Scores.Relevance);
     // NameMatch is in fact a multiplier on total score, so rescoring is sound.
     Scores.ExcludingName = Relevance.NameMatch
                                ? Scores.Total / Relevance.NameMatch
                                : Scores.Quality;
 
-    LLVM_DEBUG(llvm::dbgs() << "CodeComplete: " << First.Name << "("
-                            << IndexResult << " index) "
-                            << "(" << SemaResult << " sema)"
-                            << " = " << Scores.Total << "\n"
+    LLVM_DEBUG(llvm::dbgs() << "CodeComplete: " << First.Name << " (" << Origin
+                            << ") = " << Scores.Total << "\n"
                             << Quality << Relevance << "\n");
 
-    NSema += bool(SemaResult);
-    NIndex += bool(IndexResult);
-    NBoth += SemaResult && IndexResult;
+    NSema += bool(Origin & SymbolOrigin::AST);
+    NIndex += bool(Origin & ~SymbolOrigin::AST);
+    NBoth += (Origin & SymbolOrigin::AST) && (Origin & ~SymbolOrigin::AST);
     if (Candidates.push({std::move(Bundle), Scores}))
       Incomplete = true;
   }
 
   CodeCompletion toCodeCompletion(const CompletionCandidate::Bundle &Bundle) {
     llvm::Optional<CodeCompletionBuilder> Builder;
     for (const auto &Item : Bundle) {
       CodeCompletionString *SemaCCS =
return !match(decl(anyOf(InTopLevelScope,
                 ND, ASTCtx)
               .empty();
 }
 
 CompletionItem CodeCompletion::render(const CodeCompleteOptions &Opts) const {
   CompletionItem LSP;
   LSP.label = (HeaderInsertion ? Opts.IncludeIndicator.Insert
                                : Opts.IncludeIndicator.NoInsert) +
+              (Opts.ShowOrigins ? "[" + llvm::to_string(Origin) + "]" : "") +
               RequiredQualifier + Name + Signature;
+
   LSP.kind = Kind;
   LSP.detail = BundleSize > 1 ? llvm::formatv("[{0} overloads]", BundleSize)
                               : ReturnType;
   if (!Header.empty())
     LSP.detail += "\n" + Header;
   LSP.documentation = Documentation;
   LSP.sortText = sortText(Score.Total, Name);
   LSP.filterText = Name;

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

clang::FrontendAction *create() override {
     index::IndexingOptions IndexOpts;
     IndexOpts.SystemSymbolFilter =
         index::IndexingOptions::SystemSymbolFilterKind::All;
     IndexOpts.IndexFunctionLocals = false;
     auto CollectorOpts = SymbolCollector::Options();
     CollectorOpts.FallbackDir = AssumedHeaderDir;
     CollectorOpts.CollectIncludePath = true;
     CollectorOpts.CountReferences = true;
+    CollectorOpts.Origin = SymbolOrigin::Static;
     auto Includes = llvm::make_unique<CanonicalIncludes>();
     addSystemHeadersMapping(Includes.get());
     CollectorOpts.Includes = Includes.get();
     return new WrappedIndexAction(
         std::make_shared<SymbolCollector>(std::move(CollectorOpts)),
         std::move(Includes), IndexOpts, Ctx);
   }
 

clangd/index/FileIndex.cpp

SymbolSlab indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
   // to make sure all includes are canonicalized (with CanonicalIncludes), which
   // is not trivial given the current way of collecting symbols: we only have
   // AST at this point, but we also need preprocessor callbacks (e.g.
   // CommentHandler for IWYU pragma) to canonicalize includes.
   CollectorOpts.CollectIncludePath = false;
   CollectorOpts.CountReferences = false;
   if (!URISchemes.empty())
     CollectorOpts.URISchemes = URISchemes;
+  CollectorOpts.Origin = SymbolOrigin::Dynamic;
 
   SymbolCollector Collector(std::move(CollectorOpts));
   Collector.setPreprocessor(PP);
   index::IndexingOptions IndexOpts;
   // We only need declarations, because we don't count references.
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::DeclarationsOnly;
   IndexOpts.IndexFunctionLocals = false;

clangd/index/Index.h

static bool isEqual(const clang::clangd::SymbolID &LHS,
                       const clang::clangd::SymbolID &RHS) {
     return LHS == RHS;
   }
 };
 } // namespace llvm
 namespace clang {
 namespace clangd {
 
+// Describes the source of information about a symbol.
+// Mainly useful for debugging, e.g. understanding code completion reuslts.
+// This is a bitfield as information can be combined from several sources.
+enum SymbolOrigin : uint8_t {
+  Unknown = 0,
+  AST = 1 << 0,     // Directly from the AST (indexes should not set this).
+  Dynamic = 1 << 1, // From the dynamic index of opened files.
+  Static = 1 << 2,  // From the static, externally-built index.
+  Merge = 1 << 3,   // A non-trivial index merge was performed.
+  // Remaining bits reserved for index implementations.
+};
+raw_ostream &operator<<(raw_ostream &, SymbolOrigin);
+
 // The class presents a C++ symbol, e.g. class, function.
 //
 // WARNING: Symbols do not own much of their underlying data - typically strings
 // are owned by a SymbolSlab. They should be treated as non-owning references.
 // Copies are shallow.
 // When adding new unowned data fields to Symbol, remember to update:
 //   - SymbolSlab::Builder in Index.cpp, to copy them to the slab's storage.
 //   - mergeSymbol in Merge.cpp, to properly combine two Symbols.
struct Symbol {
   //     in the ".h" file corresponding to the definition.
   SymbolLocation CanonicalDeclaration;
   // The number of translation units that reference this symbol from their main
   // file. This number is only meaningful if aggregated in an index.
   unsigned References = 0;
   /// Whether or not this symbol is meant to be used for the code completion.
   /// See also isIndexedForCodeCompletion().
   bool IsIndexedForCodeCompletion = false;
+  /// Where this symbol came from. Usually an index provides a constant value.
+  SymbolOrigin Origin = Unknown;
   /// A brief description of the symbol that can be appended in the completion
   /// candidate list. For example, "(X x, Y y) const" is a function signature.
   llvm::StringRef Signature;
   /// What to insert when completing this symbol, after the symbol name.
   /// This is in LSP snippet syntax (e.g. "({$0})" for a no-args function).
   /// (When snippets are disabled, the symbol name alone is used).
   llvm::StringRef CompletionSnippetSuffix;
 

clangd/index/Index.cpp

 }
 
 void operator>>(StringRef Str, SymbolID &ID) {
   std::string HexString = fromHex(Str);
   assert(HexString.size() == ID.HashValue.size());
   std::copy(HexString.begin(), HexString.end(), ID.HashValue.begin());
 }
 
+raw_ostream &operator<<(raw_ostream &OS, SymbolOrigin O) {
+  if (O == SymbolOrigin::Unknown)
+    return OS << "unknown";
+  constexpr static char Sigils[] = "ADSM4567";
+  for (unsigned I = 0; I < sizeof(Sigils); ++I)
+    if (O & static_cast<SymbolOrigin>(1 << I))
+      OS << Sigils[I];
+  return OS;
+}
+
 raw_ostream &operator<<(raw_ostream &OS, const Symbol &S) {
   return OS << S.Scope << S.Name;
 }
 
 double quality(const Symbol &S) {
   // This avoids a sharp gradient for tail symbols, and also neatly avoids the
   // question of whether 0 references means a bad symbol or missing data.
   if (S.References < 3)

clangd/index/Merge.cpp

if (S.Detail) {
       if (Scratch->ReturnType == "")
         Scratch->ReturnType = O.Detail->ReturnType;
       if (Scratch->IncludeHeader == "")
         Scratch->IncludeHeader = O.Detail->IncludeHeader;
       S.Detail = Scratch;
     } else
       S.Detail = O.Detail;
   }
+
+  S.Origin =
+      static_cast<SymbolOrigin>(S.Origin | O.Origin | SymbolOrigin::Merge);
   return S;
 }
 
 std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic,
                                         const SymbolIndex *Static) {
   return llvm::make_unique<MergedIndex>(Dynamic, Static);
 }
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.h

struct Options {
     /// scheme is found. If no scheme works, symbol location will be dropped.
     std::vector<std::string> URISchemes = {"file"};
     bool CollectIncludePath = false;
     /// If set, this is used to map symbol #include path to a potentially
     /// different #include path.
     const CanonicalIncludes *Includes = nullptr;
     // Populate the Symbol.References field.
     bool CountReferences = false;
+    // Every symbol collected will be stamped with this origin.
+    SymbolOrigin Origin = SymbolOrigin::Unknown;
   };
 
   SymbolCollector(Options Opts);
 
   /// Returns true is \p ND should be collected.
   /// AST matchers require non-const ASTContext.
   static bool shouldCollectSymbol(const NamedDecl &ND, ASTContext &ASTCtx,
                                   const Options &Opts);

clangd/index/SymbolCollector.cpp

const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
   S.Signature = Signature;
   S.CompletionSnippetSuffix = SnippetSuffix;
   Symbol::Details Detail;
   Detail.Documentation = Documentation;
   Detail.ReturnType = ReturnType;
   Detail.IncludeHeader = Include;
   S.Detail = &Detail;
 
+  S.Origin = Opts.Origin;
   Symbols.insert(S);
   return Symbols.find(S.ID);
 }
 
 void SymbolCollector::addDefinition(const NamedDecl &ND,
                                     const Symbol &DeclSym) {
   if (DeclSym.Definition)
     return;

clangd/tool/ClangdMain.cpp

 
 static llvm::cl::opt<bool> EnableIndex(
     "index",
     llvm::cl::desc("Enable index-based features such as global code completion "
                    "and searching for symbols."
                    "Clang uses an index built from symbols in opened files"),
     llvm::cl::init(true));
 
+static llvm::cl::opt<bool>
+    ShowOrigins("debug-origin",
+                llvm::cl::desc("Show origins of completion items"),
+                llvm::cl::init(clangd::CodeCompleteOptions().ShowOrigins),
+                llvm::cl::Hidden);
+
 static llvm::cl::opt<Path> YamlSymbolFile(
     "yaml-symbol-file",
     llvm::cl::desc(
         "YAML-format global symbol file to build the static index. Clangd will "
         "use the static index for global code completion.\n"
         "WARNING: This option is experimental only, and will be removed "
         "eventually. Don't rely on it."),
     llvm::cl::init(""), llvm::cl::Hidden);
if (EnableIndex && !YamlSymbolFile.empty()) {
     Opts.StaticIndex = StaticIdx.get();
   }
   Opts.AsyncThreadsCount = WorkerThreadsCount;
 
   clangd::CodeCompleteOptions CCOpts;
   CCOpts.IncludeIneligibleResults = IncludeIneligibleResults;
   CCOpts.Limit = LimitResults;
   CCOpts.BundleOverloads = CompletionStyle != Detailed;
+  CCOpts.ShowOrigins = ShowOrigins;
 
   // Initialize and run ClangdLSPServer.
   ClangdLSPServer LSPServer(Out, CCOpts, CompileCommandsDirPath, Opts);
   constexpr int NoShutdownRequestErrorCode = 1;
   llvm::set_thread_name("clangd.main");
   // Change stdin to binary to not lose \r\n on windows.
   llvm::sys::ChangeStdinToBinary();
   return LSPServer.run(stdin, InputStyle) ? 0 : NoShutdownRequestErrorCode;
 }

unittests/clangd/CodeCompleteTests.cpp

 MATCHER_P(Kind, K, "") { return arg.Kind == K; }
 MATCHER_P(Doc, D, "") { return arg.Documentation == D; }
 MATCHER_P(ReturnType, D, "") { return arg.ReturnType == D; }
 MATCHER_P(InsertInclude, IncludeHeader, "") {
   return arg.Header == IncludeHeader && bool(arg.HeaderInsertion);
 }
 MATCHER(InsertInclude, "") { return bool(arg.HeaderInsertion); }
 MATCHER_P(SnippetSuffix, Text, "") { return arg.SnippetSuffix == Text; }
+MATCHER_P(Origin, OriginSet, "") { return arg.Origin == OriginSet; }
 
 // Shorthand for Contains(Named(Name)).
 Matcher<const std::vector<CodeCompletion> &> Has(std::string Name) {
   return Contains(Named(std::move(Name)));
 }
 Matcher<const std::vector<CodeCompletion> &> Has(std::string Name,
                                                  CompletionItemKind K) {
   return Contains(AllOf(Named(std::move(Name)), Kind(K)));
if (Pos == llvm::StringRef::npos) {
     Sym.Name = QName.substr(Pos + 2);
     Sym.Scope = QName.substr(0, Pos + 2);
     USR += "@N@" + replace(QName.substr(0, Pos), "::", "@N@"); // ns:: -> @N@ns
   }
   USR += Regex("^.*$").sub(USRFormat, Sym.Name); // e.g. func -> @F@func#
   Sym.ID = SymbolID(USR);
   Sym.SymInfo.Kind = Kind;
   Sym.IsIndexedForCodeCompletion = true;
+  Sym.Origin = SymbolOrigin::Static;
   return Sym;
 }
 Symbol func(StringRef Name) { // Assumes the function has no args.
   return sym(Name, index::SymbolKind::Function, "@F@\\0#"); // no args
 }
 Symbol cls(StringRef Name) {
   return sym(Name, index::SymbolKind::Class, "@S@\\0");
 }

 TEST(CompletionTest, SemaIndexMerge) {
   auto Results = completions(
       R"cpp(
           namespace ns { int local; void both(); }
           void f() { ::ns::^ }
       )cpp",
       {func("ns::both"), cls("ns::Index")});
   // We get results from both index and sema, with no duplicates.
-  EXPECT_THAT(
-      Results.Completions,
-      UnorderedElementsAre(Named("local"), Named("Index"), Named("both")));
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(
+                  AllOf(Named("local"), Origin(SymbolOrigin::AST)),
+                  AllOf(Named("Index"), Origin(SymbolOrigin::Static)),
+                  AllOf(Named("both"),
+                        Origin(SymbolOrigin::AST | SymbolOrigin::Static))));
 }
 
 TEST(CompletionTest, SemaIndexMergeWithLimit) {
   clangd::CodeCompleteOptions Opts;
   Opts.Limit = 1;
   auto Results = completions(
       R"cpp(
           namespace ns { int local; void both(); }
TEST(CompletionTest, Render) {
   C.SnippetSuffix = "(${0:bool})";
   C.ReturnType = "int";
   C.RequiredQualifier = "Foo::";
   C.Scope = "ns::Foo::";
   C.Documentation = "This is x().";
   C.Header = "\"foo.h\"";
   C.Kind = CompletionItemKind::Method;
   C.Score.Total = 1.0;
+  C.Origin =
+      static_cast<SymbolOrigin>(SymbolOrigin::AST | SymbolOrigin::Static);
 
   CodeCompleteOptions Opts;
   Opts.IncludeIndicator.Insert = "^";
   Opts.IncludeIndicator.NoInsert = "";
   Opts.EnableSnippets = false;
 
   auto R = C.render(Opts);
   EXPECT_EQ(R.label, "Foo::x(bool) const");
TEST(CompletionTest, Render) {
   EXPECT_EQ(R.insertText, "Foo::x(${0:bool})");
   EXPECT_EQ(R.insertTextFormat, InsertTextFormat::Snippet);
 
   C.HeaderInsertion.emplace();
   R = C.render(Opts);
   EXPECT_EQ(R.label, "^Foo::x(bool) const");
   EXPECT_THAT(R.additionalTextEdits, Not(IsEmpty()));
 
+  Opts.ShowOrigins = true;
+  R = C.render(Opts);
+  EXPECT_EQ(R.label, "^[AS]Foo::x(bool) const");
+
   C.BundleSize = 2;
   R = C.render(Opts);
   EXPECT_EQ(R.detail, "[2 overloads]\n\"foo.h\"");
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/IndexTests.cpp

TEST(MergeTest, Merge) {
   L.Signature = "()";                   // present in left only
   R.CompletionSnippetSuffix = "{$1:0}"; // present in right only
   Symbol::Details DetL, DetR;
   DetL.ReturnType = "DetL";
   DetR.ReturnType = "DetR";
   DetR.Documentation = "--doc--";
   L.Detail = &DetL;
   R.Detail = &DetR;
+  L.Origin = SymbolOrigin::Dynamic;
+  R.Origin = SymbolOrigin::Static;
 
   Symbol::Details Scratch;
   Symbol M = mergeSymbol(L, R, &Scratch);
   EXPECT_EQ(M.Name, "Foo");
   EXPECT_EQ(M.CanonicalDeclaration.FileURI, "file:///left.h");
   EXPECT_EQ(M.References, 3u);
   EXPECT_EQ(M.Signature, "()");
   EXPECT_EQ(M.CompletionSnippetSuffix, "{$1:0}");
   ASSERT_TRUE(M.Detail);
   EXPECT_EQ(M.Detail->ReturnType, "DetL");
   EXPECT_EQ(M.Detail->Documentation, "--doc--");
+  EXPECT_EQ(M.Origin,
+            SymbolOrigin::Dynamic | SymbolOrigin::Static | SymbolOrigin::Merge);
 }
 
 TEST(MergeTest, PreferSymbolWithDefn) {
   Symbol L, R;
   Symbol::Details Scratch;
 
   L.ID = R.ID = SymbolID("hello");
   L.CanonicalDeclaration.FileURI = "file:/left.h";

unittests/clangd/SymbolCollectorTests.cpp

const std::string Main = R"(
     };
   )";
   CollectorOpts.CountReferences = true;
   runSymbolCollector(Header, Main);
   EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(QName("X"), Refs(1)),
                                             AllOf(QName("Y"), Refs(1))));
 }
 
+TEST_F(SymbolCollectorTest, Origin) {
+  CollectorOpts.Origin = SymbolOrigin::Static;
+  runSymbolCollector("class Foo {};", /*Main=*/"");
+  EXPECT_THAT(Symbols, UnorderedElementsAre(
+                           Field(&Symbol::Origin, SymbolOrigin::Static)));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang