[clangd] Index Interfaces for Xrefs

[hokein]

Summary

This is the first step of implementing Xrefs in clangd:

• add index interfaces, and related data structures.

[sammccall]

Mostly LG.

I think we can simplify in a couple of places, and you should decide if this patch is *implementing* the new index operation or not. (Currently it implements it for 1/3 implementations, which doesn't seem that useful).

clangd/index/FileIndex.cpp

112

add a log?

112

Can we either implement this for FileIndex/MemIndex/MergedIndex, or none of them?
ATM the scope of the patch is unclear. If we don't implement it, then no need to add Slab etc. If we do, then we get 3 callsites to make sure all that stuff actually works well :-)

clangd/index/Index.cpp

138 ↗

(On Diff #156724)

this is a bitfield, there are at least 8 legal values.

If you intend each occurrence to have only one type, and only the filter to have multiple values, these should probably be different types.

Do we actually need operator<< in this patch, or is the default (print the number) OK for tests?

clangd/index/Index.h

312

Hmm, remove the bit about slab? That's only going to be true in a smaller set of cases than with Symbol.
Not owning the data is a good note, but probably belongs on the struct rather than the member.

344

Again, I'm not sure the builder/slab split is justifiable here. Can we start without it? Cost is ~8 bytes per unique filename, which should be pretty trivial.

372

nit: Results are returned in arbitrary order.?
(Usually we want to document from the POV of a caller, rather than an implementation)

clangd/index/MemIndex.cpp

95

cast to bool rather than int32_t?

clangd/index/MemIndex.h

26

nit: I'm not sure default args make sense here unless we intend for this to be forever an optional feature

28

occurrences here too

[hokein]

Scope the patch to interfaces only.

[hokein]

In D49658#1171410, @sammccall wrote:

Mostly LG.

I think we can simplify in a couple of places, and you should decide if this patch is *implementing* the new index operation or not. (Currently it implements it for 1/3 implementations, which doesn't seem that useful).

Implementing all index operations in the patch would be end up with a large patch, I intend to split the patch as small as possible. Let's scope this patch to interface only.

[ilya-biryukov]

Picking it up since @sammccall is OOO.

Implementing all index operations in the patch would be end up with a large patch, I intend to split the patch as small as possible. Let's scope this patch to interface only.

LG as interface-only patch. just a few nits

clangd/index/Index.h

288

Any strong reason to keep the values in sync with SymbolRole?
It intention is to have tricky conversions (i.e. apply a bit mask and cast to the other type)?

clangd/index/Merge.cpp

81

It's not intended to be called, right?
If that's the case let's assert(false) here. Having those statements does not seem too useful.

[hokein]

clangd/index/Index.h

288

Yeah, this is intended. Our goal here is to align with clang::index library as much as possible rather than diverge too far from it, because we will end up using index-while-build.

clangd/index/Merge.cpp

81

I'm not sure assert(false) is a good fit here, I think this is just a note reminding us that it is not implemented. Anyway, it is a matter of personal taste here.

[hokein]

Rebase

clangd/index/FileIndex.h

public:
 
   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;
 
+
+  void findOccurrences(const OccurrencesRequest &Req,
+                       llvm::function_ref<void(const SymbolOccurrence &)>
+                           Callback) const override;
 private:
   FileSymbols FSymbols;
   MemIndex Index;
   std::vector<std::string> URISchemes;
 };
 
 /// Retrieves namespace and class level symbols in \p AST.
 /// Exposed to assist in unit tests.
 /// If URISchemes is empty, the default schemes in SymbolCollector will be used.
 SymbolSlab indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
                     llvm::ArrayRef<std::string> URISchemes = {});
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H

clangd/index/FileIndex.cpp

 //===--- FileIndex.cpp - Indexes for files. ------------------------ C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "FileIndex.h"
 #include "SymbolCollector.h"
+#include "../Logger.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Lex/Preprocessor.h"
 
 namespace clang {
 namespace clangd {
 
 SymbolSlab indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
                     llvm::ArrayRef<std::string> URISchemes) {

 }
 
 void FileIndex::lookup(
     const LookupRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   Index.lookup(Req, Callback);
 }
 
+void FileIndex::findOccurrences(
+    const OccurrencesRequest &Req,
+    llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
+  log("findOccurrences is not implemented.");
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/Index.h

 private:
   SymbolSlab(llvm::BumpPtrAllocator Arena, std::vector<Symbol> Symbols)
       : Arena(std::move(Arena)), Symbols(std::move(Symbols)) {}
 
   llvm::BumpPtrAllocator Arena; // Owns Symbol data that the Symbols do not.
   std::vector<Symbol> Symbols;  // Sorted by SymbolID to allow lookup.
 };
 
+// Describes the kind of a symbol occurrence.
+//
+// This is a bitfield which can be combined from different kinds.
+enum class SymbolOccurrenceKind : uint8_t {
+  Unknown = 0,
+  Declaration = static_cast<uint8_t>(index::SymbolRole::Declaration),
+  Definition = static_cast<uint8_t>(index::SymbolRole::Definition),
+  Reference = static_cast<uint8_t>(index::SymbolRole::Reference),
+};
+inline SymbolOccurrenceKind operator|(SymbolOccurrenceKind L,
+                                      SymbolOccurrenceKind R) {
+  return static_cast<SymbolOccurrenceKind>(static_cast<uint8_t>(L) |
+                                           static_cast<uint8_t>(R));
+}
+inline SymbolOccurrenceKind &operator|=(SymbolOccurrenceKind &L,
+                                        SymbolOccurrenceKind R) {
+  return L = L | R;
+}
+inline SymbolOccurrenceKind operator&(SymbolOccurrenceKind A,
+                                      SymbolOccurrenceKind B) {
+  return static_cast<SymbolOccurrenceKind>(static_cast<uint8_t>(A) &
+                                           static_cast<uint8_t>(B));
+}
+
+// Represents a symbol occurrence in the source file. It could be a
+// declaration/definition/reference occurrence.
+//
+// WARNING: Location does not own the underlying data - Copies are shallow.
+struct SymbolOccurrence {
+  // The location of the occurrence.
+  SymbolLocation Location;
+  SymbolOccurrenceKind Kind;
+};
+
 struct FuzzyFindRequest {
   /// \brief A query string for the fuzzy find. This is matched against symbols'
   /// un-qualified identifiers and should not contain qualifiers like "::".
   std::string Query;
   /// \brief If this is non-empty, symbols must be in at least one of the scopes
   /// (e.g. namespaces) excluding nested scopes. For example, if a scope "xyz::"
   /// is provided, the matched symbols must be defined in namespace xyz but not
   /// namespace xyz::abc.
struct FuzzyFindRequest {
   /// Paths should be absolute.
   std::vector<std::string> ProximityPaths;
 };
 
 struct LookupRequest {
   llvm::DenseSet<SymbolID> IDs;
 };
 
+struct OccurrencesRequest {
+  llvm::DenseSet<SymbolID> IDs;
+  SymbolOccurrenceKind Filter;
+};
+
 /// \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:
-  //  - getAllOccurrences(SymbolID);
+  /// CrossReference finds all symbol occurrences (e.g. references,
+  /// declarations, definitions) and applies \p Callback on each result.
+  ///
+  /// Resutls are returned in arbitrary order.
+  ///
+  /// The returned result must be deep-copied if it's used outside Callback.
+  virtual void findOccurrences(
+      const OccurrencesRequest &Req,
+      llvm::function_ref<void(const SymbolOccurrence &)> Callback) const = 0;
 };
 
 } // namespace clangd
 } // namespace clang
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clangd/index/MemIndex.h

 
 /// \brief This implements an index for a (relatively small) set of symbols that
 /// can be easily managed in memory.
 class MemIndex : public SymbolIndex {
 public:
   /// \brief (Re-)Build index for `Symbols`. All symbol pointers must remain
   /// accessible as long as `Symbols` is kept alive.
   void build(std::shared_ptr<std::vector<const Symbol *>> Symbols);
 
   /// \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
+  void
   lookup(const LookupRequest &Req,
          llvm::function_ref<void(const Symbol &)> Callback) const override;
 
+  void findOccurrences(const OccurrencesRequest &Req,
+                       llvm::function_ref<void(const SymbolOccurrence &)>
+                           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 (auto &Sym : Snap->Slab)
     Snap->Pointers.push_back(&Sym);
   auto S = std::shared_ptr<std::vector<const Symbol *>>(std::move(Snap),
                                                         &Snap->Pointers);
   auto MemIdx = llvm::make_unique<MemIndex>();
   MemIdx->build(std::move(S));
   return std::move(MemIdx);
 }
 
+void MemIndex::findOccurrences(
+    const OccurrencesRequest &Req,
+    llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
+  log("findOccurrences is not implemented.");
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/Merge.cpp

 //===--- Merge.h ------------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 #include "Merge.h"
+#include "../Logger.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/raw_ostream.h"
 namespace clang {
 namespace clangd {
 namespace {
 using namespace llvm;
 
 class MergedIndex : public SymbolIndex {
Static->lookup(Req, [&](const Symbol &S) {
       else
         Callback(mergeSymbol(*Sym, S, &Scratch));
     });
     for (const auto &ID : RemainingIDs)
       if (const Symbol *Sym = B.find(ID))
         Callback(*Sym);
   }
 
+  void findOccurrences(const OccurrencesRequest &Req,
+                       llvm::function_ref<void(const SymbolOccurrence &)>
+                           Callback) const override {
+    log("findOccurrences is not implemented.");
+  }
+
 private:
   const SymbolIndex *Dynamic, *Static;
 };
 } // namespace
 
 Symbol
 mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch) {
   assert(L.ID == R.ID);

unittests/clangd/CodeCompleteTests.cpp

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 {}
 
+  void findOccurrences(const OccurrencesRequest &Req,
+                       llvm::function_ref<void(const SymbolOccurrence &)>
+                           Callback) 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;