[clangd] Add an interface that finds symbol by SymbolID in SymbolIndex.

[ioeric]

Summary

Potential use case: argument go-to-definition result with symbol
information (e.g. function definition in cc file) that might not be in the AST.

[sammccall]

Thanks for doing this! Some quibbles about the interface, but this makes index useful for lots more features.

clangd/index/Index.h

275

Can we make this a bulk operation (take an arrayref<SymbolID> or similar?)

There are use cases like augmenting sema-returned results with info from the index where we want a bunch at once. In practice a single bulk operation will be much nicer for an rpc-based index to implement than a single lookup issued many times in parallel.

(The callback interface is really nice here, because the underlying RPC can be streaming!)

275

For extensibility and uniformity with FuzzyFind, we should consider adding a struct around the parameters.

At least one option seems likely to be added here: retrieving the full ("detail") symbol vs the basic symbol (particularly for bulk actions).
Others are less obvious, but could include something like "chase pointers" so that if returning a typedef, the target of the typedef would also be looked up and returned.

275

getSymbol isn't a bad name, but it's a bit hard to talk about without ambiguity because "get" is so overloaded and everything deals with "symbols".. (e.g. "this method gets a symbol as a parameter..."). It's also awkward to use as a noun, which is common with RPCs.

lookup or fetch would be specific enough to avoid this. (Dropping "symbol" from the method name because it's present in the interface name). WDYT?

clangd/index/Merge.cpp

58

(Seems like this is avoidable when looking up a single key, by nesting the second call in the callback. But with a batch operation the slab is probably necessary)

unittests/clangd/IndexTests.cpp

93

Symbol;Scope is already e.g. "ns::", this shouldn't be needed.

112

check the return value

[ioeric]

• - Addressed review comments.

[ioeric]

Thanks for the review!

clangd/index/Index.h

275

Makes sense. I wasn't really sure about getSymbol and wanted your thought. Going with lookup.

unittests/clangd/IndexTests.cpp

93

This wasn't true in the tests. Fixed.

112

This was intended. If no symbol was found, Res would be empty by default. No longer relevant in the new revision.

[sammccall]

clangd/index/Index.h

252

nit: DenseSet? we already have the traits

273

is "at least one matched symbol was found" so useful that we need to provide it in a second way (rather than just invoking the callback at least once)?

Having both fuzzyFind and lookup return bool (but with very different semantics) seems confusing, and I suspect void would be fine here.

clangd/index/Merge.cpp

67

this could just be callback(S)

69

This could also just be callback(mergeSymbol(...)), if we keep track of the IDs we've emitted.
This way the slab would only have symbols from the dynamic index.

This could be just:

• before the static lookup, make a copy RemainingIDs = Req.IDs
• in the static callback, remove the id from RemainingIDs
• after the static lookup, loop through RemainingIDs, look up symbol in dynamic slab, emit

This avoids:

• copying the static index results (which tend to be more numerous)
• build() on the slab builder, which isn't cheap

unittests/clangd/CodeCompleteTests.cpp

693

why comment out the param names here? can't we just either include or omit them?

[ioeric]

• Addressed review comments.

clangd/index/Merge.cpp

69

Good idea. Thanks!

clangd/index/FileIndex.h

public:
   /// \brief Update symbols in \p Path with symbols in \p AST. If \p AST is
   /// nullptr, this removes all symbols in the file
   void update(PathRef Path, ParsedAST *AST);
 
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
+  void lookup(const LookupRequest &Req,
+              llvm::function_ref<void(const Symbol &)> Callback) const override;
+
 private:
   FileSymbols FSymbols;
   MemIndex Index;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H

clangd/index/FileIndex.cpp

 }
 
 bool FileIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   return Index.fuzzyFind(Req, Callback);
 }
 
+void FileIndex::lookup(
+    const LookupRequest &Req,
+    llvm::function_ref<void(const Symbol &)> Callback) const {
+  Index.lookup(Req, Callback);
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/Index.h

struct FuzzyFindRequest {
   ///
   /// The global scope is "", a top level scope is "foo::", etc.
   std::vector<std::string> Scopes;
   /// \brief The number of top candidates to return. The index may choose to
   /// return more than this, e.g. if it doesn't know which candidates are best.
   size_t MaxCandidateCount = UINT_MAX;
 };
 
+struct LookupRequest {
+  llvm::DenseSet<SymbolID> IDs;
+};
+
 /// \brief Interface for symbol indexes that can be used for searching or
 /// matching symbols among a set of symbols based on names or unique IDs.
 class SymbolIndex {
 public:
   virtual ~SymbolIndex() = default;
 
   /// \brief Matches symbols in the index fuzzily and applies \p Callback on
   /// each matched symbol before returning.
   /// If returned Symbols are used outside Callback, they must be deep-copied!
   ///
   /// Returns true if there may be more results (limited by MaxCandidateCount).
   virtual bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const = 0;
 
+  /// Looks up symbols with any of the given symbol IDs and applies \p Callback
+  /// on each matched symbol.
+  /// The returned symbol must be deep-copied if it's used outside Callback.
+  virtual void
+  lookup(const LookupRequest &Req,
+         llvm::function_ref<void(const Symbol &)> Callback) const = 0;
+
   // FIXME: add interfaces for more index use cases:
-  //  - Symbol getSymbolInfo(SymbolID);
   //  - getAllOccurrences(SymbolID);
 };
 
 } // namespace clangd
 } // namespace clang
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clangd/index/MemIndex.h

public:
 
   /// \brief Build index from a symbol slab.
   static std::unique_ptr<SymbolIndex> build(SymbolSlab Slab);
 
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
+  virtual void
+  lookup(const LookupRequest &Req,
+         llvm::function_ref<void(const Symbol &)> Callback) const override;
+
 private:
   std::shared_ptr<std::vector<const Symbol *>> Symbols;
   // Index is a set of symbols that are deduplicated by symbol IDs.
   // FIXME: build smarter index structure.
   llvm::DenseMap<SymbolID, const Symbol *> Index;
   mutable std::mutex Mutex;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H

clangd/index/MemIndex.cpp

for (const auto Pair : Index) {
       }
     }
     for (; !Top.empty(); Top.pop())
       Callback(*Top.top().second);
   }
   return More;
 }
 
+void MemIndex::lookup(const LookupRequest &Req,
+                      llvm::function_ref<void(const Symbol &)> Callback) const {
+  for (const auto &ID : Req.IDs) {
+    auto I = Index.find(ID);
+    if (I != Index.end())
+      Callback(*I->second);
+  }
+}
+
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab) {
   struct Snapshot {
     SymbolSlab Slab;
     std::vector<const Symbol *> Pointers;
   };
   auto Snap = std::make_shared<Snapshot>();
   Snap->Slab = std::move(Slab);
   for (auto &Sym : Snap->Slab)

clangd/index/Merge.cpp

More |= Static->fuzzyFind(Req, [&](const Symbol &S) {
        Callback(mergeSymbol(*DynS, S, &Scratch));
      });
      for (const Symbol &S : Dyn)
        if (!SeenDynamicSymbols.count(S.ID))
          Callback(S);
      return More;
   }
 
+  void
+  lookup(const LookupRequest &Req,
+         llvm::function_ref<void(const Symbol &)> Callback) const override {
+    SymbolSlab::Builder B;
+
+    Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); });
+
+    auto RemainingIDs = Req.IDs;
+    Symbol::Details Scratch;
+    Static->lookup(Req, [&](const Symbol &S) {
+      const Symbol *Sym = B.find(S.ID);
+      RemainingIDs.erase(S.ID);
+      if (!Sym)
+        Callback(S);
+      else
+        Callback(mergeSymbol(*Sym, S, &Scratch));
+    });
+    for (const auto &ID : RemainingIDs)
+      if (const Symbol *Sym = B.find(ID))
+        Callback(*Sym);
+  }
+
 private:
   const SymbolIndex *Dynamic, *Static;
 };
 }
 
 Symbol
 mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch) {
   assert(L.ID == R.ID);

unittests/clangd/CodeCompleteTests.cpp

 public:
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override {
     Requests.push_back(Req);
     return true;
   }
 
+  void lookup(const LookupRequest &,
+              llvm::function_ref<void(const Symbol &)>) const override {}
+
   const std::vector<FuzzyFindRequest> allRequests() const { return Requests; }
 
 private:
   mutable std::vector<FuzzyFindRequest> Requests;
 };
 
 std::vector<FuzzyFindRequest> captureIndexRequests(llvm::StringRef Code) {
   clangd::CodeCompleteOptions Opts;

unittests/clangd/IndexTests.cpp

Symbol symbol(llvm::StringRef QName) {
   Symbol Sym;
   Sym.ID = SymbolID(QName.str());
   size_t Pos = QName.rfind("::");
   if (Pos == llvm::StringRef::npos) {
     Sym.Name = QName;
     Sym.Scope = "";
   } else {
     Sym.Name = QName.substr(Pos + 2);
-    Sym.Scope = QName.substr(0, Pos);
+    Sym.Scope = QName.substr(0, Pos + 2);
   }
   return Sym;
 }
 
 MATCHER_P(Named, N, "") { return arg.Name == N; }
 
 TEST(SymbolSlab, FindAndIterate) {
   SymbolSlab::Builder B;

 generateNumSymbols(int Begin, int End,
                    std::weak_ptr<SlabAndPointers> *WeakSymbols = nullptr) {
   std::vector<std::string> Names;
   for (int i = Begin; i <= End; i++)
     Names.push_back(std::to_string(i));
   return generateSymbols(Names, WeakSymbols);
 }
 
+std::string getQualifiedName(const Symbol &Sym) {
+  return (Sym.Scope + Sym.Name).str();
+}
+
 std::vector<std::string> match(const SymbolIndex &I,
                                const FuzzyFindRequest &Req,
                                bool *Incomplete = nullptr) {
   std::vector<std::string> Matches;
   bool IsIncomplete = I.fuzzyFind(Req, [&](const Symbol &Sym) {
-    Matches.push_back(
-        (Sym.Scope + (Sym.Scope.empty() ? "" : "::") + Sym.Name).str());
+    Matches.push_back(getQualifiedName(Sym));
   });
   if (Incomplete)
     *Incomplete = IsIncomplete;
   return Matches;
 }
 
 TEST(MemIndexTest, MemIndexSymbolsRecycled) {
   MemIndex I;
   std::weak_ptr<SlabAndPointers> Symbols;
   I.build(generateNumSymbols(0, 10, &Symbols));
   FuzzyFindRequest Req;
   Req.Query = "7";
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("7"));
 
   EXPECT_FALSE(Symbols.expired());
   // Release old symbols.
   I.build(generateNumSymbols(0, 0));
   EXPECT_TRUE(Symbols.expired());
 }
TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("y3"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
   MemIndex I;
   I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  Req.Scopes = {"a"};
+  Req.Scopes = {"a::"};
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
   MemIndex I;
   I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  Req.Scopes = {"a", "b"};
+  Req.Scopes = {"a::", "b::"};
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3"));
 }
 
 TEST(MemIndexTest, NoMatchNestedScopes) {
   MemIndex I;
   I.build(generateSymbols({"a::y1", "a::b::y2"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  Req.Scopes = {"a"};
+  Req.Scopes = {"a::"};
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1"));
 }
 
 TEST(MemIndexTest, IgnoreCases) {
   MemIndex I;
   I.build(generateSymbols({"ns::ABC", "ns::abc"}));
   FuzzyFindRequest Req;
   Req.Query = "AB";
-  Req.Scopes = {"ns"};
+  Req.Scopes = {"ns::"};
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 
-TEST(MergeTest, MergeIndex) {
+// Returns qualified names of symbols with any of IDs in the index.
+std::vector<std::string> lookup(const SymbolIndex &I,
+                                llvm::ArrayRef<SymbolID> IDs) {
+  LookupRequest Req;
+  Req.IDs.insert(IDs.begin(), IDs.end());
+  std::vector<std::string> Results;
+  I.lookup(Req, [&](const Symbol &Sym) {
+    Results.push_back(getQualifiedName(Sym));
+  });
+  return Results;
+}
+
+TEST(MemIndexTest, Lookup) {
+  MemIndex I;
+  I.build(generateSymbols({"ns::abc", "ns::xyz"}));
+  EXPECT_THAT(lookup(I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc"));
+  EXPECT_THAT(lookup(I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
+              UnorderedElementsAre("ns::abc", "ns::xyz"));
+  EXPECT_THAT(lookup(I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}),
+              UnorderedElementsAre("ns::xyz"));
+  EXPECT_THAT(lookup(I, SymbolID("ns::nonono")), UnorderedElementsAre());
+}
+
+TEST(MergeIndexTest, Lookup) {
+  MemIndex I, J;
+  I.build(generateSymbols({"ns::A", "ns::B"}));
+  J.build(generateSymbols({"ns::B", "ns::C"}));
+  EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::A")),
+              UnorderedElementsAre("ns::A"));
+  EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::B")),
+              UnorderedElementsAre("ns::B"));
+  EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::C")),
+              UnorderedElementsAre("ns::C"));
+  EXPECT_THAT(
+      lookup(*mergeIndex(&I, &J), {SymbolID("ns::A"), SymbolID("ns::B")}),
+      UnorderedElementsAre("ns::A", "ns::B"));
+  EXPECT_THAT(
+      lookup(*mergeIndex(&I, &J), {SymbolID("ns::A"), SymbolID("ns::C")}),
+      UnorderedElementsAre("ns::A", "ns::C"));
+  EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::D")),
+              UnorderedElementsAre());
+  EXPECT_THAT(lookup(*mergeIndex(&I, &J), {}), UnorderedElementsAre());
+}
+
+TEST(MergeIndexTest, FuzzyFind) {
   MemIndex I, J;
   I.build(generateSymbols({"ns::A", "ns::B"}));
   J.build(generateSymbols({"ns::B", "ns::C"}));
   FuzzyFindRequest Req;
-  Req.Scopes = {"ns"};
+  Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*mergeIndex(&I, &J), Req),
               UnorderedElementsAre("ns::A", "ns::B", "ns::C"));
 }
 
 TEST(MergeTest, Merge) {
   Symbol L, R;
   L.ID = R.ID = SymbolID("hello");
   L.Name = R.Name = "Foo";                    // same in both