[clangd] SymbolOccurrences -> Refs and cleanup

[sammccall]

Summary

A few things that I noticed while merging the SwapIndex patch:

• SymbolOccurrences and particularly SymbolOccurrenceSlab are unwieldy names, and these names appear *a lot*. Ref, RefSlab, etc seem clear enough and read/format much better.
• The asymmetry between SymbolSlab and RefSlab (build() vs freeze()) is confusing and irritating, and doesn't even save much code. Avoiding RefSlab::Builder was my idea, but it was a bad one; add it.
• DenseMap<SymbolID, ArrayRef<Ref>> seems like a reasonable compromise for constructing MemIndex - and means many less wasted allocations than the current DenseMap<SymbolID, vector<Ref*>> for FileIndex, and none for slabs.
• RefSlab::find() is not needed, so we can get rid of the DenseMap after building the slab.
• A few naming/consistency fixes: e.g. Slabs,Refs -> Symbols,Refs.

[sammccall]

Remove RefsSlab::find()

[hokein]

Thanks for cleaning it up! I admit that SymbolOccurrences is a loong name. A few nits.

clangd/index/FileIndex.cpp

120

So the sort is intended to make returned refs ordered?

clangd/index/Index.h

367

we should be careful if Refs is empty. Calling front() on empty container is undefined behavior.

clangd/index/MemIndex.h

22

This type seems not used in this patch, consider removing it or using it to replace existing llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> usage.

unittests/clangd/FileIndexTests.cpp

346

My fault here. This is not safe, we need to store the underlying FileURI data.

unittests/clangd/IndexTests.cpp

273

The same here.

[ioeric]

nice!

clangd/index/Index.cpp

147

maybe also mention that this would make lookup faster?

clangd/index/Merge.cpp

12

nit: shouldn't the main header be sorted higher?

We should also put all #includes in one block so that clang-format can sort them properly.

[sammccall]

In D51605#1222636, @hokein wrote:

Thanks for cleaning it up! I admit that SymbolOccurrences is a loong name. A few nits.

Yeah, I hope you don't mind! The references stuff is awesome, I'm hoping to make it work with static index soon!

clangd/index/FileIndex.cpp

120

Yeah, I'm worried about the fact that we have no ranking at all, so the natural implementation of refs() with limit will return randomly different results after each dynamic index rebuild.
Added a comment here, also happy to remove the sorting if you prefer.

clangd/index/Index.h

367

the arg to sizeof() is an unevaluated context, so it never actually gets called (just the type is evaluated).
Changed to sizeof(value_type) for clarity though.

clangd/index/Merge.cpp

12

Ah, <set> was confusing clang-format's main-header heuristic.

unittests/clangd/FileIndexTests.cpp

346

well, the contract on SymbolIndex doesn't say so, but in this concrete case, we know the implementation so it's not too bad.

In any case, avoided the issue (changed getRefPaths -> getRefs which returns a slab)

[sammccall]

Address comments

[lebedev.ri]

clangd/index/Index.cpp

152

I noticed this by accident, but i'm pretty sure std::sort() should not be used in LLVM sources at all.
llvm::sort() should be used everywhere.

[sammccall]

clangd/index/Index.cpp

152

OK, I'll send a cleanup, thanks!

[hokein]

LGTM, thanks!

clangd/index/FileIndex.cpp

120

Sounds good to me.

clangd/ClangdServer.cpp

std::unique_ptr<ParsingCallbacks> makeUpdateCallbacks() {
     };
     return llvm::make_unique<CB>(this);
   };
 
 private:
   // Contains information from each file's preamble only.
   // These are large, but update fairly infrequently (preambles are stable).
   // Missing information:
-  //  - symbol occurrences (these are always "from the main file")
+  //  - symbol refs (these are always "from the main file")
   //  - definition locations in the main file
   //
   // FIXME: Because the preambles for different TUs have large overlap and
   // FileIndex doesn't deduplicate, this uses lots of extra RAM.
   // The biggest obstacle in fixing this: the obvious approach of partitioning
   // by declaring file (rather than main file) fails if headers provide
   // different symbols based on preprocessor state.
   FileIndex PreambleIdx;
   // Contains information from each file's main AST.
   // These are updated frequently (on file change), but are relatively small.
   // Mostly contains:
-  //  - occurrences of symbols declared in the preamble and referenced from main
+  //  - refs to symbols declared in the preamble and referenced from main
   //  - symbols declared both in the main file and the preamble
   // (Note that symbols *only* in the main file are not indexed).
   FileIndex MainFileIdx;
   std::unique_ptr<SymbolIndex> MergedIndex;
 };
 
 ClangdServer::Options ClangdServer::optsForTest() {
   ClangdServer::Options Opts;

clangd/index/FileIndex.h

 /// users. For each file, this class only stores a pointer pointing to the
 /// newest snapshot, and an outdated snapshot is deleted by the last owner of
 /// the snapshot, either this class or the symbol index.
 ///
 /// The snapshot semantics keeps critical sections minimal since we only need
 /// locking when we swap or obtain references to snapshots.
 class FileSymbols {
 public:
-  /// Updates all symbols and occurrences in a file.
+  /// Updates all symbols and refs in a file.
   /// If either is nullptr, corresponding data for \p Path will be removed.
   void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
-              std::unique_ptr<SymbolOccurrenceSlab> Occurrences);
+              std::unique_ptr<RefSlab> Refs);
 
   // The index keeps the symbols alive.
   std::unique_ptr<SymbolIndex> buildMemIndex();
 
 private:
   mutable std::mutex Mutex;
 
-  /// Stores the latest snapshots for all active files.
-  llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSlabs;
-  /// Stores the latest occurrence slabs for all active files.
-  llvm::StringMap<std::shared_ptr<SymbolOccurrenceSlab>> FileToOccurrenceSlabs;
+  /// Stores the latest symbol snapshots for all active files.
+  llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSymbols;
+  /// Stores the latest ref snapshots for all active files.
+  llvm::StringMap<std::shared_ptr<RefSlab>> FileToRefs;
 };
 
 /// This manages symbols from files and an in-memory index on all symbols.
 class FileIndex : public SwapIndex {
 public:
   /// If URISchemes is empty, the default schemes in SymbolCollector will be
   /// used.
   FileIndex(std::vector<std::string> URISchemes = {});

 private:
   // Only update() should swap the index.
   using SwapIndex::reset;
 
   FileSymbols FSymbols;
   std::vector<std::string> URISchemes;
 };
 
-/// Retrieves symbols and symbol occurrences in \p AST.
+/// Retrieves symbols and refs in \p AST.
 /// Exposed to assist in unit tests.
 /// If URISchemes is empty, the default schemes in SymbolCollector will be used.
 /// If \p TopLevelDecls is set, only these decls are indexed. Otherwise, all top
 /// level decls obtained from \p AST are indexed.
-std::pair<SymbolSlab, SymbolOccurrenceSlab>
+std::pair<SymbolSlab, RefSlab>
 indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
          llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls = llvm::None,
          llvm::ArrayRef<std::string> URISchemes = {});
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H

clangd/index/FileIndex.cpp

 #include "../Logger.h"
 #include "SymbolCollector.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Lex/Preprocessor.h"
 
 namespace clang {
 namespace clangd {
 
-std::pair<SymbolSlab, SymbolOccurrenceSlab>
+std::pair<SymbolSlab, RefSlab>
 indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
          llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls,
          llvm::ArrayRef<std::string> URISchemes) {
   SymbolCollector::Options CollectorOpts;
   // FIXME(ioeric): we might also want to collect include headers. We would need
   // 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.
indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
 
   std::vector<Decl *> DeclsToIndex;
   if (TopLevelDecls)
     DeclsToIndex.assign(TopLevelDecls->begin(), TopLevelDecls->end());
   else
     DeclsToIndex.assign(AST.getTranslationUnitDecl()->decls().begin(),
                         AST.getTranslationUnitDecl()->decls().end());
 
-  // We only collect occurrences when indexing main AST.
+  // We only collect refs when indexing main AST.
   // FIXME: this is a hacky way to detect whether we are indexing preamble AST
   // or main AST, we should make it explicitly.
   bool IsIndexMainAST = TopLevelDecls.hasValue();
   if (IsIndexMainAST)
-    CollectorOpts.OccurrenceFilter = AllOccurrenceKinds;
+    CollectorOpts.RefFilter = RefKind::All;
 
   SymbolCollector Collector(std::move(CollectorOpts));
   Collector.setPreprocessor(PP);
   index::indexTopLevelDecls(AST, DeclsToIndex, Collector, IndexOpts);
 
   const auto &SM = AST.getSourceManager();
   const auto *MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
   std::string FileName = MainFileEntry ? MainFileEntry->getName() : "";
 
   auto Syms = Collector.takeSymbols();
-  auto Occurrences = Collector.takeOccurrences();
+  auto Refs = Collector.takeRefs();
   vlog("index {0}AST for {1}: \n"
        "  symbol slab: {2} symbols, {3} bytes\n"
-       "  occurrence slab: {4} symbols, {5} bytes",
+       "  ref slab: {4} symbols, {5} bytes",
        IsIndexMainAST ? "Main" : "Preamble", FileName, Syms.size(),
-       Syms.bytes(), Occurrences.size(), Occurrences.bytes());
-  return {std::move(Syms), std::move(Occurrences)};
+       Syms.bytes(), Refs.size(), Refs.bytes());
+  return {std::move(Syms), std::move(Refs)};
 }
 
 FileIndex::FileIndex(std::vector<std::string> URISchemes)
     : URISchemes(std::move(URISchemes)) {
   reset(FSymbols.buildMemIndex());
 }
 
-void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
-                         std::unique_ptr<SymbolOccurrenceSlab> Occurrences) {
+void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Symbols,
+                         std::unique_ptr<RefSlab> Refs) {
   std::lock_guard<std::mutex> Lock(Mutex);
-  if (!Slab)
-    FileToSlabs.erase(Path);
+  if (!Symbols)
+    FileToSymbols.erase(Path);
   else
-    FileToSlabs[Path] = std::move(Slab);
-  if (!Occurrences)
-    FileToOccurrenceSlabs.erase(Path);
+    FileToSymbols[Path] = std::move(Symbols);
+  if (!Refs)
+    FileToRefs.erase(Path);
   else
-    FileToOccurrenceSlabs[Path] = std::move(Occurrences);
+    FileToRefs[Path] = std::move(Refs);
 }
 
 std::unique_ptr<SymbolIndex> FileSymbols::buildMemIndex() {
-  std::vector<std::shared_ptr<SymbolSlab>> Slabs;
-  std::vector<std::shared_ptr<SymbolOccurrenceSlab>> OccurrenceSlabs;
+  std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
+  std::vector<std::shared_ptr<RefSlab>> RefSlabs;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
-    for (const auto &FileAndSlab : FileToSlabs)
-      Slabs.push_back(FileAndSlab.second);
-    for (const auto &FileAndOccurrenceSlab : FileToOccurrenceSlabs)
-      OccurrenceSlabs.push_back(FileAndOccurrenceSlab.second);
+    for (const auto &FileAndSymbols : FileToSymbols)
+      SymbolSlabs.push_back(FileAndSymbols.second);
+    for (const auto &FileAndRefs : FileToRefs)
+      RefSlabs.push_back(FileAndRefs.second);
   }
   std::vector<const Symbol *> AllSymbols;
-  for (const auto &Slab : Slabs)
+  for (const auto &Slab : SymbolSlabs)
     for (const auto &Sym : *Slab)
       AllSymbols.push_back(&Sym);
-  MemIndex::OccurrenceMap AllOccurrences;
-  for (const auto &OccurrenceSlab : OccurrenceSlabs)
-    for (const auto &Sym : *OccurrenceSlab) {
-      auto &Entry = AllOccurrences[Sym.first];
-      for (const auto &Occ : Sym.second)
-        Entry.push_back(&Occ);
-    }
+
+  std::vector<Ref> RefsStorage; // Contiguous ranges for each SymbolID.
+  llvm::DenseMap<SymbolID, ArrayRef<Ref>> AllRefs;
+  {
+    llvm::DenseMap<SymbolID, SmallVector<Ref, 4>> MergedRefs;
+    size_t Count = 0;
+    for (const auto &RefSlab : RefSlabs)
+      for (const auto &Sym : *RefSlab) {
+        MergedRefs[Sym.first].append(Sym.second.begin(), Sym.second.end());
+        Count += Sym.second.size();
+      }
+    RefsStorage.reserve(Count);
+    AllRefs.reserve(MergedRefs.size());
+    for (auto &Sym : MergedRefs) {
+      auto &SymRefs = Sym.second;
+      // Sorting isn't required, but yields more stable results over rebuilds.
+      std::sort(SymRefs.begin(), SymRefs.end());
+      std::copy(SymRefs.begin(), SymRefs.end(), back_inserter(RefsStorage));
+      AllRefs.try_emplace(
+          Sym.first,
+          ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
+                        SymRefs.size()));
+    }
 
-  // Index must keep the slabs alive.
+  // Index must keep the slabs and contiguous ranges alive.
   return llvm::make_unique<MemIndex>(
-      llvm::make_pointee_range(AllSymbols), std::move(AllOccurrences),
-      std::make_pair(std::move(Slabs), std::move(OccurrenceSlabs)));
+      llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
+      std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
+                      std::move(RefsStorage)));
 }
 
 void FileIndex::update(PathRef Path, ASTContext *AST,
                        std::shared_ptr<Preprocessor> PP,
                        llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls) {
   if (!AST) {
     FSymbols.update(Path, nullptr, nullptr);
   } else {
     assert(PP);
-    auto Slab = llvm::make_unique<SymbolSlab>();
-    auto OccurrenceSlab = llvm::make_unique<SymbolOccurrenceSlab>();
-    std::tie(*Slab, *OccurrenceSlab) =
-        indexAST(*AST, PP, TopLevelDecls, URISchemes);
-    FSymbols.update(Path, std::move(Slab), std::move(OccurrenceSlab));
+    auto Contents = indexAST(*AST, PP, TopLevelDecls, URISchemes);
+    FSymbols.update(Path,
+                    llvm::make_unique<SymbolSlab>(std::move(Contents.first)),
+                    llvm::make_unique<RefSlab>(std::move(Contents.second)));
   }
   reset(FSymbols.buildMemIndex());
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/Index.h

struct IncludeHeaderWithReferences {
     unsigned References = 0;
   };
   /// One Symbol can potentially be incuded via different headers.
   ///   - If we haven't seen a definition, this covers all declarations.
   ///   - If we have seen a definition, this covers declarations visible from
   ///   any definition.
   llvm::SmallVector<IncludeHeaderWithReferences, 1> IncludeHeaders;
 
-  // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S);
 
 // Computes query-independent quality score for a Symbol.
 // This currently falls in the range [1, ln(#indexed documents)].
 // FIXME: this should probably be split into symbol -> signals
 //        and signals -> score, so it can be reused for Sema completions.

 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.
+// Describes the kind of a cross-reference.
 //
 // This is a bitfield which can be combined from different kinds.
-enum class SymbolOccurrenceKind : uint8_t {
+enum class RefKind : 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),
+  All = Declaration | Definition | Reference,
 };
-inline SymbolOccurrenceKind operator|(SymbolOccurrenceKind L,
-                                      SymbolOccurrenceKind R) {
-  return static_cast<SymbolOccurrenceKind>(static_cast<uint8_t>(L) |
-                                           static_cast<uint8_t>(R));
+inline RefKind operator|(RefKind L, RefKind R) {
+  return static_cast<RefKind>(static_cast<uint8_t>(L) |
 }
-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));
+inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; }
+inline RefKind operator&(RefKind A, RefKind B) {
+  return static_cast<RefKind>(static_cast<uint8_t>(A) &
 }
-llvm::raw_ostream &operator<<(llvm::raw_ostream &, SymbolOccurrenceKind);
-static const SymbolOccurrenceKind AllOccurrenceKinds =
-    SymbolOccurrenceKind::Declaration | SymbolOccurrenceKind::Definition |
-    SymbolOccurrenceKind::Reference;
+llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefKind);
 
-// Represents a symbol occurrence in the source file. It could be a
-// declaration/definition/reference occurrence.
+// Represents a symbol occurrence in the source file.
+// Despite the name, it could be a declaration/definition/reference.
 //
 // WARNING: Location does not own the underlying data - Copies are shallow.
-struct SymbolOccurrence {
-  // The location of the occurrence.
+struct Ref {
+  // The source location where the symbol is named.
   SymbolLocation Location;
-  SymbolOccurrenceKind Kind = SymbolOccurrenceKind::Unknown;
+  RefKind Kind = RefKind::Unknown;
 };
-inline bool operator<(const SymbolOccurrence &L, const SymbolOccurrence &R) {
+inline bool operator<(const Ref &L, const Ref &R) {
   return std::tie(L.Location, L.Kind) < std::tie(R.Location, R.Kind);
 }
-inline bool operator==(const SymbolOccurrence &L, const SymbolOccurrence &R) {
+inline bool operator==(const Ref &L, const Ref &R) {
   return std::tie(L.Location, L.Kind) == std::tie(R.Location, R.Kind);
 }
-llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
-                              const SymbolOccurrence &Occurrence);
+llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Ref &);
 
-// An efficient structure of storing large set of symbol occurrences in memory.
+// An efficient structure of storing large set of symbol references in memory.
 // Filenames are deduplicated.
-class SymbolOccurrenceSlab {
+class RefSlab {
 public:
-  using const_iterator =
-      llvm::DenseMap<SymbolID, std::vector<SymbolOccurrence>>::const_iterator;
+  using value_type = std::pair<SymbolID, llvm::ArrayRef<Ref>>;
+  using const_iterator = std::vector<value_type>::const_iterator;
   using iterator = const_iterator;
 
-  SymbolOccurrenceSlab() : UniqueStrings(Arena) {}
-
-  static SymbolOccurrenceSlab createEmpty() {
-    SymbolOccurrenceSlab Empty;
-    Empty.freeze();
-    return Empty;
-  }
-
-  // Define move semantics for the slab, allowing assignment from an rvalue.
-  // Implicit move assignment is deleted by the compiler because
-  // StringSaver has a reference type member.
-  SymbolOccurrenceSlab(SymbolOccurrenceSlab &&Slab) = default;
-  SymbolOccurrenceSlab &operator=(SymbolOccurrenceSlab &&RHS) {
-    assert(RHS.Frozen &&
-           "SymbolOcucrrenceSlab must be frozen when move assigned!");
-    Arena = std::move(RHS.Arena);
-    Frozen = true;
-    Occurrences = std::move(RHS.Occurrences);
-    return *this;
-  }
-
-  const_iterator begin() const { return Occurrences.begin(); }
-  const_iterator end() const { return Occurrences.end(); }
+  RefSlab() = default;
+  RefSlab(RefSlab &&Slab) = default;
+  RefSlab &operator=(RefSlab &&RHS) = default;
+
+  const_iterator begin() const { return Refs.begin(); }
+  const_iterator end() const { return Refs.end(); }
+  size_t size() const { return Refs.size(); }
 
   size_t bytes() const {
-    return sizeof(*this) + Arena.getTotalMemory() + Occurrences.getMemorySize();
+    return sizeof(*this) + Arena.getTotalMemory() +
+           sizeof(value_type) * Refs.size();
   }
 
-  size_t size() const { return Occurrences.size(); }
-
-  // Adds a symbol occurrence.
-  // This is a deep copy: underlying FileURI will be owned by the slab.
-  void insert(const SymbolID &SymID, const SymbolOccurrence &Occurrence);
-
-  llvm::ArrayRef<SymbolOccurrence> find(const SymbolID &ID) const {
-    assert(Frozen && "SymbolOccurrenceSlab must be frozen before looking up!");
-    auto It = Occurrences.find(ID);
-    if (It == Occurrences.end())
-      return {};
-    return It->second;
-  }
+  // RefSlab::Builder is a mutable container that can 'freeze' to RefSlab.
+  class Builder {
+  public:
+    Builder() : UniqueStrings(Arena) {}
+    // Adds a ref to the slab. Deep copy: Strings will be owned by the slab.
+    void insert(const SymbolID &ID, const Ref &S);
+    // Consumes the builder to finalize the slab.
+    RefSlab build() &&;
 
-  void freeze();
+  private:
+    llvm::BumpPtrAllocator Arena;
+    llvm::UniqueStringSaver UniqueStrings; // Contents on the arena.
+    llvm::DenseMap<SymbolID, std::vector<Ref>> Refs;
+  };
 
 private:
-  bool Frozen = false;
+  RefSlab(std::vector<value_type> Refs, llvm::BumpPtrAllocator Arena)
+      : Arena(std::move(Arena)), Refs(std::move(Refs)) {}
+
   llvm::BumpPtrAllocator Arena;
-  llvm::UniqueStringSaver UniqueStrings;
-  llvm::DenseMap<SymbolID, std::vector<SymbolOccurrence>> Occurrences;
+  std::vector<value_type> Refs;
 };
 
 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::"
struct FuzzyFindRequest {
   }
   bool operator!=(const FuzzyFindRequest &Req) const { return !(*this == Req); }
 };
 
 struct LookupRequest {
   llvm::DenseSet<SymbolID> IDs;
 };
 
-struct OccurrencesRequest {
+struct RefsRequest {
   llvm::DenseSet<SymbolID> IDs;
-  SymbolOccurrenceKind Filter = AllOccurrenceKinds;
+  RefKind Filter = RefKind::All;
 };
 
 /// 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;
 
-  /// CrossReference finds all symbol occurrences (e.g. references,
-  /// declarations, definitions) and applies \p Callback on each result.
-  ///
-  /// Results are returned in arbitrary order.
+  /// Finds all occurrences (e.g. references, declarations, definitions) of a
+  /// symbol and applies \p Callback on each result.
   ///
+  /// Results should be 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;
+  virtual void refs(const RefsRequest &Req,
+                    llvm::function_ref<void(const Ref &)> Callback) const = 0;
 
   /// Returns estimated size of index (in bytes).
   // FIXME(kbobyrev): Currently, this only returns the size of index itself
   // excluding the size of actual symbol slab index refers to. We should include
   // both.
   virtual size_t estimateMemoryUsage() const = 0;
 };
 
 // Delegating implementation of SymbolIndex whose delegate can be swapped out.
 class SwapIndex : public SymbolIndex {
 public:
   // If an index is not provided, reset() must be called.
   SwapIndex(std::unique_ptr<SymbolIndex> Index = nullptr)
       : Index(std::move(Index)) {}
   void reset(std::unique_ptr<SymbolIndex>);
 
   // SymbolIndex methods delegate to the current index, which is kept alive
   // until the call returns (even if reset() is called).
   bool fuzzyFind(const FuzzyFindRequest &,
                  llvm::function_ref<void(const Symbol &)>) const override;
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override;
-  void findOccurrences(
-      const OccurrencesRequest &,
-      llvm::function_ref<void(const SymbolOccurrence &)>) const override;
+  void refs(const RefsRequest &,
+            llvm::function_ref<void(const Ref &)>) const override;
   size_t estimateMemoryUsage() const override;
 
 private:
   std::shared_ptr<SymbolIndex> snapshot() const;
   mutable std::mutex Mutex;
   std::shared_ptr<SymbolIndex> Index;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clangd/index/Index.cpp

SymbolSlab SymbolSlab::Builder::build() && {
   // We may have unused strings from overwritten symbols. Build a new arena.
   BumpPtrAllocator NewArena;
   llvm::UniqueStringSaver Strings(NewArena);
   for (auto &S : Symbols)
     own(S, Strings, NewArena);
   return SymbolSlab(std::move(NewArena), std::move(Symbols));
 }
 
-raw_ostream &operator<<(raw_ostream &OS, SymbolOccurrenceKind K) {
-  if (K == SymbolOccurrenceKind::Unknown)
+raw_ostream &operator<<(raw_ostream &OS, RefKind K) {
+  if (K == RefKind::Unknown)
     return OS << "Unknown";
   static const std::vector<const char *> Messages = {"Decl", "Def", "Ref"};
   bool VisitedOnce = false;
   for (unsigned I = 0; I < Messages.size(); ++I) {
     if (static_cast<uint8_t>(K) & 1u << I) {
       if (VisitedOnce)
         OS << ", ";
       OS << Messages[I];
       VisitedOnce = true;
     }
   }
   return OS;
 }
 
-llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
-                              const SymbolOccurrence &Occurrence) {
-  OS << Occurrence.Location << ":" << Occurrence.Kind;
-  return OS;
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Ref &R) {
+  return OS << R.Location << ":" << R.Kind;
 }
 
-void SymbolOccurrenceSlab::insert(const SymbolID &SymID,
-                                  const SymbolOccurrence &Occurrence) {
-  assert(!Frozen &&
-         "Can't insert a symbol occurrence after the slab has been frozen!");
-  auto &SymOccurrences = Occurrences[SymID];
-  SymOccurrences.push_back(Occurrence);
-  SymOccurrences.back().Location.FileURI =
-      UniqueStrings.save(Occurrence.Location.FileURI);
-}
-
-void SymbolOccurrenceSlab::freeze() {
-  // Deduplicate symbol occurrences.
-  for (auto &IDAndOccurrence : Occurrences) {
-    auto &Occurrence = IDAndOccurrence.getSecond();
-    std::sort(Occurrence.begin(), Occurrence.end());
-    Occurrence.erase(std::unique(Occurrence.begin(), Occurrence.end()),
-                     Occurrence.end());
+void RefSlab::Builder::insert(const SymbolID &ID, const Ref &S) {
+  auto &M = Refs[ID];
+  M.push_back(S);
+  M.back().Location.FileURI = UniqueStrings.save(M.back().Location.FileURI);
+}
+
+RefSlab RefSlab::Builder::build() && {
+  // We can reuse the arena, as it only has unique strings and we need them all.
+  // Reallocate refs on the arena to reduce waste and indirections when reading.
+  std::vector<std::pair<SymbolID, ArrayRef<Ref>>> Result;
+  Result.reserve(Refs.size());
+  for (auto &Sym : Refs) {
+    auto &SymRefs = Sym.second;
+    std::sort(SymRefs.begin(), SymRefs.end());
+    // TODO: do we really need to dedup?
+    SymRefs.erase(std::unique(SymRefs.begin(), SymRefs.end()), SymRefs.end());
+
+    auto *Array = Arena.Allocate<Ref>(SymRefs.size());
+    std::uninitialized_copy(SymRefs.begin(), SymRefs.end(), Array);
+    Result.emplace_back(Sym.first, ArrayRef<Ref>(Array, SymRefs.size()));
   }
-  Frozen = true;
+  return RefSlab(std::move(Result), std::move(Arena));
 }
 
 void SwapIndex::reset(std::unique_ptr<SymbolIndex> Index) {
   // Keep the old index alive, so we don't destroy it under lock (may be slow).
   std::shared_ptr<SymbolIndex> Pin;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     Pin = std::move(this->Index);
     this->Index = std::move(Index);
   }
 }
 std::shared_ptr<SymbolIndex> SwapIndex::snapshot() const {
   std::lock_guard<std::mutex> Lock(Mutex);
   return Index;
 }
 
 bool SwapIndex::fuzzyFind(const FuzzyFindRequest &R,
                           llvm::function_ref<void(const Symbol &)> CB) const {
   return snapshot()->fuzzyFind(R, CB);
 }
 void SwapIndex::lookup(const LookupRequest &R,
                        llvm::function_ref<void(const Symbol &)> CB) const {
   return snapshot()->lookup(R, CB);
 }
-void SwapIndex::findOccurrences(
-    const OccurrencesRequest &R,
-    llvm::function_ref<void(const SymbolOccurrence &)> CB) const {
-  return snapshot()->findOccurrences(R, CB);
+void SwapIndex::refs(const RefsRequest &R,
+                     llvm::function_ref<void(const Ref &)> CB) const {
+  return snapshot()->refs(R, CB);
 }
 size_t SwapIndex::estimateMemoryUsage() const {
   return snapshot()->estimateMemoryUsage();
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/MemIndex.h

 #include <mutex>
 
 namespace clang {
 namespace clangd {
 
 /// MemIndex is a naive in-memory index suitable for a small set of symbols.
 class MemIndex : public SymbolIndex {
 public:
-  /// Maps from a symbol ID to all corresponding symbol occurrences.
-  /// The map doesn't own occurrence objects.
-  using OccurrenceMap =
-      llvm::DenseMap<SymbolID, std::vector<const SymbolOccurrence *>>;
-
   MemIndex() = default;
-  // All symbols and occurrences must outlive this index.
-  // TODO: find a better type for Occurrences here.
-  template <typename SymbolRange>
-  MemIndex(SymbolRange &&Symbols, OccurrenceMap Occurrences)
-      : Occurrences(std::move(Occurrences)) {
+  // All symbols and refs must outlive this index.
+  template <typename SymbolRange, typename RefRange>
+  MemIndex(SymbolRange &&Symbols, RefRange &&Refs) {
     for (const Symbol &S : Symbols)
       Index[S.ID] = &S;
+    for (const std::pair<SymbolID, llvm::ArrayRef<Ref>> &R : Refs)
+      this->Refs.try_emplace(R.first, R.second.begin(), R.second.end());
   }
   // Symbols are owned by BackingData, Index takes ownership.
-  template <typename Range, typename Payload>
-  MemIndex(Range &&Symbols, OccurrenceMap Occurrences, Payload &&BackingData)
-      : MemIndex(std::forward<Range>(Symbols), std::move(Occurrences)) {
+  template <typename SymbolRange, typename RefRange, typename Payload>
+  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, Payload &&BackingData)
+      : MemIndex(std::forward<SymbolRange>(Symbols),
+                 std::forward<RefRange>(Refs)) {
     KeepAlive = std::shared_ptr<void>(
         std::make_shared<Payload>(std::move(BackingData)), nullptr);
   }
 
-  /// Builds an index from a slab. The index takes ownership of the data.
-  static std::unique_ptr<SymbolIndex> build(SymbolSlab Slab,
-                                            SymbolOccurrenceSlab Occurrences);
+  /// Builds an index from slabs. The index takes ownership of the data.
+  static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs);
 
   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;
+  void refs(const RefsRequest &Req,
+            llvm::function_ref<void(const Ref &)> Callback) const override;
 
   size_t estimateMemoryUsage() const override;
 
 private:
   // Index is a set of symbols that are deduplicated by symbol IDs.
   llvm::DenseMap<SymbolID, const Symbol *> Index;
-  // A map from symbol ID to symbol occurrences, support query by IDs.
-  OccurrenceMap Occurrences;
+  // A map from symbol ID to symbol refs, support query by IDs.
+  llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H

clangd/index/MemIndex.cpp

 #include "MemIndex.h"
 #include "../FuzzyMatch.h"
 #include "../Logger.h"
 #include <queue>
 
 namespace clang {
 namespace clangd {
 
-std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab,
-                                             SymbolOccurrenceSlab Occurrences) {
-  OccurrenceMap M;
-  for (const auto &SymbolAndOccurrences : Occurrences) {
-    auto &Entry = M[SymbolAndOccurrences.first];
-    for (const auto &Occurrence : SymbolAndOccurrences.second)
-      Entry.push_back(&Occurrence);
-  }
-  auto Data = std::make_pair(std::move(Slab), std::move(Occurrences));
-  return llvm::make_unique<MemIndex>(Data.first, std::move(M), std::move(Data));
+std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) {
+  auto Data = std::make_pair(std::move(Slab), std::move(Refs));
+  return llvm::make_unique<MemIndex>(Data.first, Data.second, std::move(Data));
 }
 
 bool MemIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
 
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);
   }
 }
 
-void MemIndex::findOccurrences(
-    const OccurrencesRequest &Req,
-    llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
+void MemIndex::refs(const RefsRequest &Req,
+                    llvm::function_ref<void(const Ref &)> Callback) const {
   for (const auto &ReqID : Req.IDs) {
-    auto FoundOccurrences = Occurrences.find(ReqID);
-    if (FoundOccurrences == Occurrences.end())
+    auto SymRefs = Refs.find(ReqID);
+    if (SymRefs == Refs.end())
       continue;
-    for (const auto *O : FoundOccurrences->second) {
-      if (static_cast<int>(Req.Filter & O->Kind))
-        Callback(*O);
-    }
+    for (const auto &O : SymRefs->second)
+      if (static_cast<int>(Req.Filter & O.Kind))
+        Callback(O);
   }
 }
 
 size_t MemIndex::estimateMemoryUsage() const {
   return Index.getMemorySize();
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/Merge.h

 Symbol mergeSymbol(const Symbol &L, const Symbol &R);
 
 // mergeIndex returns a composite index based on two provided Indexes:
 //  - the Dynamic index covers few files, but is relatively up-to-date.
 //  - the Static index covers a bigger set of files, but is relatively stale.
 // The returned index attempts to combine results, and avoid duplicates.
 //
 // FIXME: We don't have a mechanism in Index to track deleted symbols and
-// occurrences in dirty files, so the merged index may return stale symbols
-// and occurrences from Static index.
+// refs in dirty files, so the merged index may return stale symbols
+// and refs from Static index.
 std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic,
                                         const SymbolIndex *Static);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MERGE_H

clangd/index/Merge.cpp

 //===--- Merge.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
-#include <set>
-
 #include "Merge.h"
 #include "../Logger.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/raw_ostream.h"
+#include <set>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using namespace llvm;
 
 class MergedIndex : public SymbolIndex {
Static->lookup(Req, [&](const Symbol &S) {
       else
         Callback(mergeSymbol(*Sym, S));
     });
     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 {
-    // We don't want duplicated occurrences from the static/dynamic indexes,
-    // and we can't reliably duplicate them because occurrence offsets may
-    // differ slightly.
-    // We consider the dynamic index authoritative and report all its
-    // occurrences, and only report static index occurrences from other files.
+  void refs(const RefsRequest &Req,
+            llvm::function_ref<void(const Ref &)> Callback) const override {
+    // We don't want duplicated refs from the static/dynamic indexes,
+    // and we can't reliably duplicate them because offsets may differ slightly.
+    // We consider the dynamic index authoritative and report all its refs,
+    // and only report static index refs from other files.
     //
     // FIXME: The heuristic fails if the dynamic index contains a file, but all
-    // occurrences were removed (we will report stale ones from the static
-    // index). Ultimately we should explicit check which index has the file
-    // instead.
-    std::set<std::string> DynamicIndexFileURIs;
-    Dynamic->findOccurrences(Req, [&](const SymbolOccurrence &O) {
+    // refs were removed (we will report stale ones from the static index).
+    // Ultimately we should explicit check which index has the file instead.
+    llvm::StringSet<> DynamicIndexFileURIs;
+    Dynamic->refs(Req, [&](const Ref &O) {
       DynamicIndexFileURIs.insert(O.Location.FileURI);
       Callback(O);
     });
-    Static->findOccurrences(Req, [&](const SymbolOccurrence &O) {
-      if (DynamicIndexFileURIs.count(O.Location.FileURI))
-        return;
+    Static->refs(Req, [&](const Ref &O) {
+      if (!DynamicIndexFileURIs.count(O.Location.FileURI))
         Callback(O);
     });
   }
 
   size_t estimateMemoryUsage() const override {
     return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
   }
 
 private:

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;
-    /// The symbol occurrence kind that will be collected.
-    /// If not set (Unknown), SymbolCollector will not collect any symbol
-    /// occurrences.
-    SymbolOccurrenceKind OccurrenceFilter = SymbolOccurrenceKind::Unknown;
+    /// The symbol ref kinds that will be collected.
+    /// If not set, SymbolCollector will not collect refs.
+    RefKind RefFilter = RefKind::Unknown;
     // Every symbol collected will be stamped with this origin.
     SymbolOrigin Origin = SymbolOrigin::Unknown;
     /// Collect macros.
     /// Note that SymbolCollector must be run with preprocessor in order to
     /// collect macros. For example, `indexTopLevelDecls` will not index any
     /// macro even if this is true.
     bool CollectMacro = false;
   };
handleDeclOccurence(const Decl *D, index::SymbolRoleSet Roles,
                       SourceLocation Loc,
                       index::IndexDataConsumer::ASTNodeInfo ASTNode) override;
 
   bool handleMacroOccurence(const IdentifierInfo *Name, const MacroInfo *MI,
                             index::SymbolRoleSet Roles,
                             SourceLocation Loc) override;
 
   SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
-
-  SymbolOccurrenceSlab takeOccurrences() {
-    SymbolOccurrences.freeze();
-    return std::move(SymbolOccurrences);
-  }
+  RefSlab takeRefs() { return std::move(Refs).build(); }
 
   void finish() override;
 
 private:
   const Symbol *addDeclaration(const NamedDecl &, SymbolID);
   void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
 
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
-  // All symbol occurrences collected from the AST.
-  // Only symbols declared in preamble (from #include) and references from the
+  // All refs collected from the AST.
+  // Only symbols declared in preamble (from #include) and referenced from the
   // main file will be included.
-  SymbolOccurrenceSlab SymbolOccurrences;
+  RefSlab::Builder Refs;
   ASTContext *ASTCtx;
   std::shared_ptr<Preprocessor> PP;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
   std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo;
   Options Opts;
-  using DeclOccurrence = std::pair<SourceLocation, index::SymbolRoleSet>;
+  using DeclRef = std::pair<SourceLocation, index::SymbolRoleSet>;
   // Symbols referenced from the current TU, flushed on finish().
   llvm::DenseSet<const NamedDecl *> ReferencedDecls;
   llvm::DenseSet<const IdentifierInfo *> ReferencedMacros;
-  llvm::DenseMap<const NamedDecl *, std::vector<DeclOccurrence>>
-      DeclOccurrences;
+  llvm::DenseMap<const NamedDecl *, std::vector<DeclRef>> DeclRefs;
   // Maps canonical declaration provided by clang to canonical declaration for
   // an index symbol, if clangd prefers a different declaration than that
   // provided by clang. For example, friend declaration might be considered
   // canonical by clang but should not be considered canonical in the index
   // unless it's a definition.
   llvm::DenseMap<const Decl *, const Decl *> CanonicalDecls;
 };
 
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.cpp

 // heuristic.
 bool isPreferredDeclaration(const NamedDecl &ND, index::SymbolRoleSet Roles) {
   using namespace clang::ast_matchers;
   return (Roles & static_cast<unsigned>(index::SymbolRole::Definition)) &&
          llvm::isa<TagDecl>(&ND) &&
          match(decl(isExpansionInMainFile()), ND, ND.getASTContext()).empty();
 }
 
-SymbolOccurrenceKind toOccurrenceKind(index::SymbolRoleSet Roles) {
-  return static_cast<SymbolOccurrenceKind>(
-      static_cast<unsigned>(AllOccurrenceKinds) & Roles);
+RefKind toRefKind(index::SymbolRoleSet Roles) {
+  return static_cast<RefKind>(static_cast<unsigned>(RefKind::All) & Roles);
 }
 
 } // namespace
 
 SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {}
 
 void SymbolCollector::initialize(ASTContext &Ctx) {
   ASTCtx = &Ctx;
bool SymbolCollector::handleDeclOccurence(
   // D may not be an interesting symbol, but it's cheaper to check at the end.
   auto &SM = ASTCtx->getSourceManager();
   auto SpellingLoc = SM.getSpellingLoc(Loc);
   if (Opts.CountReferences &&
       (Roles & static_cast<unsigned>(index::SymbolRole::Reference)) &&
       SM.getFileID(SpellingLoc) == SM.getMainFileID())
     ReferencedDecls.insert(ND);
 
-  if ((static_cast<unsigned>(Opts.OccurrenceFilter) & Roles) &&
+  if ((static_cast<unsigned>(Opts.RefFilter) & Roles) &&
       SM.getFileID(SpellingLoc) == SM.getMainFileID())
-    DeclOccurrences[ND].emplace_back(SpellingLoc, Roles);
+    DeclRefs[ND].emplace_back(SpellingLoc, Roles);
 
   // Don't continue indexing if this is a mere reference.
   if (!(Roles & static_cast<unsigned>(index::SymbolRole::Declaration) ||
         Roles & static_cast<unsigned>(index::SymbolRole::Definition)))
     return true;
   if (!shouldCollectSymbol(*ND, *ASTCtx, Opts))
     return true;
 
if (Opts.CollectMacro) {
     }
   }
 
   const auto &SM = ASTCtx->getSourceManager();
   auto* MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
 
   if (auto MainFileURI = toURI(SM, MainFileEntry->getName(), Opts)) {
     std::string MainURI = *MainFileURI;
-    for (const auto &It : DeclOccurrences) {
+    for (const auto &It : DeclRefs) {
       if (auto ID = getSymbolID(It.first)) {
         if (Symbols.find(*ID)) {
           for (const auto &LocAndRole : It.second) {
-            SymbolOccurrence Occurrence;
+            Ref R;
             auto Range =
                 getTokenRange(LocAndRole.first, SM, ASTCtx->getLangOpts());
-            Occurrence.Location.Start = Range.first;
-            Occurrence.Location.End = Range.second;
-            Occurrence.Location.FileURI = MainURI;
-            Occurrence.Kind = toOccurrenceKind(LocAndRole.second);
-            SymbolOccurrences.insert(*ID, Occurrence);
+            R.Location.Start = Range.first;
+            R.Location.End = Range.second;
+            R.Location.FileURI = MainURI;
+            R.Kind = toRefKind(LocAndRole.second);
+            Refs.insert(*ID, R);
           }
         }
       }
     }
   } else {
     log("Failed to create URI for main file: {0}", MainFileEntry->getName());
   }
 
   ReferencedDecls.clear();
   ReferencedMacros.clear();
-  DeclOccurrences.clear();
+  DeclRefs.clear();
 }
 
 const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
                                               SymbolID ID) {
   auto &Ctx = ND.getASTContext();
   auto &SM = Ctx.getSourceManager();
 
   Symbol S;

clangd/index/dex/DexIndex.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;
+  void refs(const RefsRequest &Req,
+            llvm::function_ref<void(const Ref &)> Callback) const override;
 
   size_t estimateMemoryUsage() const override;
 
 private:
   void buildIndex();
 
   std::vector<const Symbol *> Symbols;
   llvm::DenseMap<SymbolID, const Symbol *> LookupTable;

clangd/index/dex/DexIndex.cpp

void DexIndex::lookup(const LookupRequest &Req,
                       llvm::function_ref<void(const Symbol &)> Callback) const {
   for (const auto &ID : Req.IDs) {
     auto I = LookupTable.find(ID);
     if (I != LookupTable.end())
       Callback(*I->second);
   }
 }
 
-void DexIndex::findOccurrences(
-    const OccurrencesRequest &Req,
-    llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
-  log("findOccurrences is not implemented.");
+void DexIndex::refs(const RefsRequest &Req,
+                    llvm::function_ref<void(const Ref &)> Callback) const {
+  log("refs is not implemented.");
 }
 
 size_t DexIndex::estimateMemoryUsage() const {
   size_t Bytes =
       LookupTable.size() * sizeof(std::pair<SymbolID, const Symbol *>);
   Bytes += SymbolQuality.size() * sizeof(std::pair<const Symbol *, float>);
   Bytes += InvertedIndex.size() * sizeof(Token);
 

clangd/tool/ClangdMain.cpp

if (!Buffer) {
     return nullptr;
   }
   auto Slab = symbolsFromYAML(Buffer.get()->getBuffer());
   SymbolSlab::Builder SymsBuilder;
   for (auto Sym : Slab)
     SymsBuilder.insert(Sym);
 
   return UseDex ? dex::DexIndex::build(std::move(SymsBuilder).build())
-                : MemIndex::build(std::move(SymsBuilder).build(),
-                                  SymbolOccurrenceSlab::createEmpty());
+                : MemIndex::build(std::move(SymsBuilder).build(), RefSlab());
 }
 
 } // namespace
 
 static llvm::cl::opt<Path> CompileCommandsDir(
     "compile-commands-dir",
     llvm::cl::desc("Specify a path to look for compile_commands.json. If path "
                    "is invalid, clangd will look in the current directory and "

unittests/clangd/CodeCompleteTests.cpp

Matcher<const std::vector<CodeCompletion> &> Has(std::string Name,
   return Contains(AllOf(Named(std::move(Name)), Kind(K)));
 }
 MATCHER(IsDocumented, "") { return !arg.Documentation.empty(); }
 
 std::unique_ptr<SymbolIndex> memIndex(std::vector<Symbol> Symbols) {
   SymbolSlab::Builder Slab;
   for (const auto &Sym : Symbols)
     Slab.insert(Sym);
-  return MemIndex::build(std::move(Slab).build(),
-                         SymbolOccurrenceSlab::createEmpty());
+  return MemIndex::build(std::move(Slab).build(), RefSlab());
 }
 
 CodeCompleteResult completions(ClangdServer &Server, StringRef TestCode,
                                Position point,
                                std::vector<Symbol> IndexSymbols = {},
                                clangd::CodeCompleteOptions Opts = {}) {
   std::unique_ptr<SymbolIndex> OverrideIndex;
   if (!IndexSymbols.empty()) {
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 {}
+  void refs(const RefsRequest &,
+            llvm::function_ref<void(const Ref &)>) const override {}
 
   // This is incorrect, but IndexRequestCollector is not an actual index and it
   // isn't used in production code.
   size_t estimateMemoryUsage() const override { return 0; }
 
   const std::vector<FuzzyFindRequest> consumeRequests() const {
     auto Reqs = std::move(Requests);
     Requests = {};

unittests/clangd/FileIndexTests.cpp

 #include "gmock/gmock.h"
 #include "index/FileIndex.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PCHContainerOperations.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "gtest/gtest.h"
 
-using testing::UnorderedElementsAre;
+using testing::_;
 using testing::AllOf;
+using testing::ElementsAre;
+using testing::Pair;
+using testing::UnorderedElementsAre;
 
-MATCHER_P(OccurrenceRange, Range, "") {
+MATCHER_P(RefRange, Range, "") {
   return std::tie(arg.Location.Start.Line, arg.Location.Start.Column,
                   arg.Location.End.Line, arg.Location.End.Column) ==
          std::tie(Range.start.line, Range.start.character, Range.end.line,
                   Range.end.character);
 }
 MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
 
 namespace clang {
 namespace clangd {
-
 namespace {
+testing::Matcher<const RefSlab &>
+RefsAre(std::vector<testing::Matcher<Ref>> Matchers) {
+  return ElementsAre(testing::Pair(_, UnorderedElementsAreArray(Matchers)));
+}
 
 Symbol symbol(llvm::StringRef ID) {
   Symbol Sym;
   Sym.ID = SymbolID(ID);
   Sym.Name = ID;
   return Sym;
 }
 
 std::unique_ptr<SymbolSlab> numSlab(int Begin, int End) {
   SymbolSlab::Builder Slab;
   for (int i = Begin; i <= End; i++)
     Slab.insert(symbol(std::to_string(i)));
   return llvm::make_unique<SymbolSlab>(std::move(Slab).build());
 }
 
-std::unique_ptr<SymbolOccurrenceSlab> occurrenceSlab(const SymbolID &ID,
-                                                     llvm::StringRef Path) {
-  auto Slab = llvm::make_unique<SymbolOccurrenceSlab>();
-  SymbolOccurrence Occurrence;
-  Occurrence.Location.FileURI = Path;
-  Occurrence.Kind = SymbolOccurrenceKind::Reference;
-  Slab->insert(ID, Occurrence);
-  return Slab;
+std::unique_ptr<RefSlab> refSlab(const SymbolID &ID, llvm::StringRef Path) {
+  RefSlab::Builder Slab;
+  Ref R;
+  R.Location.FileURI = Path;
+  R.Kind = RefKind::Reference;
+  Slab.insert(ID, R);
+  return llvm::make_unique<RefSlab>(std::move(Slab).build());
 }
 
 std::vector<std::string> getSymbolNames(const SymbolIndex &I,
                                         std::string Query = "") {
   FuzzyFindRequest Req;
   Req.Query = Query;
   std::vector<std::string> Names;
   I.fuzzyFind(Req, [&](const Symbol &S) { Names.push_back(S.Name); });
   return Names;
 }
 
-std::vector<std::string> getOccurrencePaths(const SymbolIndex &I, SymbolID ID) {
-  OccurrencesRequest Req;
+RefSlab getRefs(const SymbolIndex &I, SymbolID ID) {
+  RefsRequest Req;
   Req.IDs = {ID};
-  std::vector<std::string> Paths;
-  I.findOccurrences(Req, [&](const SymbolOccurrence &S) {
-    Paths.push_back(S.Location.FileURI);
-  });
-  return Paths;
-}
-
-std::unique_ptr<SymbolOccurrenceSlab> emptyOccurrence() {
-  auto EmptySlab = llvm::make_unique<SymbolOccurrenceSlab>();
-  EmptySlab->freeze();
-  return EmptySlab;
+  RefSlab::Builder Slab;
+  I.refs(Req, [&](const Ref &S) { Slab.insert(ID, S); });
+  return std::move(Slab).build();
 }
 
 TEST(FileSymbolsTest, UpdateAndGet) {
   FileSymbols FS;
   EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()), UnorderedElementsAre());
 
-  FS.update("f1", numSlab(1, 3), occurrenceSlab(SymbolID("1"), "f1.cc"));
+  FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"));
   EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()),
               UnorderedElementsAre("1", "2", "3"));
-  EXPECT_THAT(getOccurrencePaths(*FS.buildMemIndex(), SymbolID("1")),
-              UnorderedElementsAre("f1.cc"));
+  EXPECT_THAT(getRefs(*FS.buildMemIndex(), SymbolID("1")),
+              RefsAre({FileURI("f1.cc")}));
 }
 
 TEST(FileSymbolsTest, Overlap) {
   FileSymbols FS;
-  FS.update("f1", numSlab(1, 3), emptyOccurrence());
-  FS.update("f2", numSlab(3, 5), emptyOccurrence());
+  FS.update("f1", numSlab(1, 3), nullptr);
+  FS.update("f2", numSlab(3, 5), nullptr);
   EXPECT_THAT(getSymbolNames(*FS.buildMemIndex()),
               UnorderedElementsAre("1", "2", "3", "4", "5"));
 }
 
 TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
   FileSymbols FS;
 
   SymbolID ID("1");
-  FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc"));
+  FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"));
 
   auto Symbols = FS.buildMemIndex();
   EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
-  EXPECT_THAT(getOccurrencePaths(*Symbols, ID), UnorderedElementsAre("f1.cc"));
+  EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")}));
 
   FS.update("f1", nullptr, nullptr);
   auto Empty = FS.buildMemIndex();
   EXPECT_THAT(getSymbolNames(*Empty), UnorderedElementsAre());
-  EXPECT_THAT(getOccurrencePaths(*Empty, ID), UnorderedElementsAre());
+  EXPECT_THAT(getRefs(*Empty, ID), ElementsAre());
 
   EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
-  EXPECT_THAT(getOccurrencePaths(*Symbols, ID), UnorderedElementsAre("f1.cc"));
+  EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")}));
 }
 
 std::vector<std::string> match(const SymbolIndex &I,
                                const FuzzyFindRequest &Req) {
   std::vector<std::string> Matches;
   I.fuzzyFind(Req, [&](const Symbol &Sym) {
     Matches.push_back((Sym.Scope + Sym.Name).str());
   });
TEST(FileIndexTest, RebuildWithPreamble) {
   Req.Query = "";
   Req.Scopes = {"", "ns_in_header::"};
 
   EXPECT_THAT(
       match(Index, Req),
       UnorderedElementsAre("ns_in_header", "ns_in_header::func_in_header"));
 }
 
-TEST(FileIndexTest, Occurrences) {
+TEST(FileIndexTest, Refs) {
   const char *HeaderCode = "class Foo {};";
   Annotations MainCode(R"cpp(
   void f() {
     $foo[[Foo]] foo;
   }
   )cpp");
 
   auto Foo =
       findSymbol(TestTU::withHeaderCode(HeaderCode).headerSymbols(), "Foo");
 
-  OccurrencesRequest Request;
+  RefsRequest Request;
   Request.IDs = {Foo.ID};
-  Request.Filter = SymbolOccurrenceKind::Declaration |
-                   SymbolOccurrenceKind::Definition |
-                   SymbolOccurrenceKind::Reference;
 
   FileIndex Index(/*URISchemes*/ {"unittest"});
   // Add test.cc
   TestTU Test;
   Test.HeaderCode = HeaderCode;
   Test.Code = MainCode.code();
   Test.Filename = "test.cc";
   auto AST = Test.build();
   Index.update(Test.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(),
                AST.getLocalTopLevelDecls());
   // Add test2.cc
   TestTU Test2;
   Test2.HeaderCode = HeaderCode;
   Test2.Code = MainCode.code();
   Test2.Filename = "test2.cc";
   AST = Test2.build();
   Index.update(Test2.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(),
                AST.getLocalTopLevelDecls());
 
-  std::vector<SymbolOccurrence> Results;
-  Index.findOccurrences(
-      Request, [&Results](const SymbolOccurrence &O) { Results.push_back(O); });
-
-  EXPECT_THAT(Results,
-              UnorderedElementsAre(AllOf(OccurrenceRange(MainCode.range("foo")),
-                                         FileURI("unittest:///test.cc")),
-                                   AllOf(OccurrenceRange(MainCode.range("foo")),
-                                         FileURI("unittest:///test2.cc"))));
+  EXPECT_THAT(getRefs(Index, Foo.ID),
+              RefsAre({AllOf(RefRange(MainCode.range("foo")),
+                       AllOf(RefRange(MainCode.range("foo")),
+                             FileURI("unittest:///test2.cc"))}));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/IndexTests.cpp

 #include "TestTU.h"
 #include "gmock/gmock.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "index/MemIndex.h"
 #include "index/Merge.h"
 #include "gtest/gtest.h"
 
+using testing::_;
 using testing::AllOf;
 using testing::ElementsAre;
+using testing::Pair;
 using testing::Pointee;
 using testing::UnorderedElementsAre;
 using namespace llvm;
 
 namespace clang {
 namespace clangd {
 namespace {
 
 MATCHER_P(Named, N, "") { return arg.Name == N; }
-MATCHER_P(OccurrenceRange, Range, "") {
+MATCHER_P(RefRange, Range, "") {
   return std::tie(arg.Location.Start.Line, arg.Location.Start.Column,
                   arg.Location.End.Line, arg.Location.End.Column) ==
          std::tie(Range.start.line, Range.start.character, Range.end.line,
                   Range.end.character);
 }
 MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
 
 TEST(SymbolSlab, FindAndIterate) {
TEST(SymbolSlab, FindAndIterate) {
   for (const char *Sym : {"X", "Y", "Z"})
     EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym));
 }
 
 TEST(SwapIndexTest, OldIndexRecycled) {
   auto Token = std::make_shared<int>();
   std::weak_ptr<int> WeakToken = Token;
 
-  SwapIndex S(llvm::make_unique<MemIndex>(
-      SymbolSlab(), MemIndex::OccurrenceMap(), std::move(Token)));
+  SwapIndex S(
+      llvm::make_unique<MemIndex>(SymbolSlab(), RefSlab(), std::move(Token)));
   EXPECT_FALSE(WeakToken.expired());     // Current MemIndex keeps it alive.
   S.reset(llvm::make_unique<MemIndex>()); // Now the MemIndex is destroyed.
   EXPECT_TRUE(WeakToken.expired());      // So the token is too.
 }
 
 TEST(MemIndexTest, MemIndexDeduplicate) {
   std::vector<Symbol> Symbols = {symbol("1"), symbol("2"), symbol("3"),
                                  symbol("2") /* duplicate */};
   FuzzyFindRequest Req;
   Req.Query = "2";
-  MemIndex I(Symbols, MemIndex::OccurrenceMap());
+  MemIndex I(Symbols, RefSlab());
   EXPECT_THAT(match(I, Req), ElementsAre("2"));
 }
 
 TEST(MemIndexTest, MemIndexLimitedNumMatches) {
-  auto I = MemIndex::build(generateNumSymbols(0, 100), SymbolOccurrenceSlab());
+  auto I = MemIndex::build(generateNumSymbols(0, 100), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "5";
   Req.MaxCandidateCount = 3;
   bool Incomplete;
   auto Matches = match(*I, Req, &Incomplete);
   EXPECT_EQ(Matches.size(), Req.MaxCandidateCount);
   EXPECT_TRUE(Incomplete);
 }
 
 TEST(MemIndexTest, FuzzyMatch) {
   auto I = MemIndex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
-      SymbolOccurrenceSlab());
+      RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.MaxCandidateCount = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
-  auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}),
-                           SymbolOccurrenceSlab());
+  auto I =
+      MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
-  auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}),
-                           SymbolOccurrenceSlab());
+  auto I =
+      MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
   auto I = MemIndex::build(
-      generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}),
-      SymbolOccurrenceSlab());
+      generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
   auto I = MemIndex::build(
-      generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}),
-      SymbolOccurrenceSlab());
+      generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::", "b::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3"));
 }
 
 TEST(MemIndexTest, NoMatchNestedScopes) {
-  auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}),
-                           SymbolOccurrenceSlab());
+  auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1"));
 }
 
 TEST(MemIndexTest, IgnoreCases) {
-  auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}),
-                           SymbolOccurrenceSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab());
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 
 TEST(MemIndexTest, Lookup) {
-  auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}),
-                           SymbolOccurrenceSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab());
   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) {
-  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}),
-                           SymbolOccurrenceSlab()),
-       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}),
-                           SymbolOccurrenceSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()),
+       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab());
   auto M = mergeIndex(I.get(), J.get());
   EXPECT_THAT(lookup(*M, SymbolID("ns::A")), UnorderedElementsAre("ns::A"));
   EXPECT_THAT(lookup(*M, SymbolID("ns::B")), UnorderedElementsAre("ns::B"));
   EXPECT_THAT(lookup(*M, SymbolID("ns::C")), UnorderedElementsAre("ns::C"));
   EXPECT_THAT(lookup(*M, {SymbolID("ns::A"), SymbolID("ns::B")}),
               UnorderedElementsAre("ns::A", "ns::B"));
   EXPECT_THAT(lookup(*M, {SymbolID("ns::A"), SymbolID("ns::C")}),
               UnorderedElementsAre("ns::A", "ns::C"));
   EXPECT_THAT(lookup(*M, SymbolID("ns::D")), UnorderedElementsAre());
   EXPECT_THAT(lookup(*M, {}), UnorderedElementsAre());
 }
 
 TEST(MergeIndexTest, FuzzyFind) {
-  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}),
-                           SymbolOccurrenceSlab()),
-       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}),
-                           SymbolOccurrenceSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()),
+       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab());
   FuzzyFindRequest Req;
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*mergeIndex(I.get(), J.get()), Req),
               UnorderedElementsAre("ns::A", "ns::B", "ns::C"));
 }
 
 TEST(MergeTest, Merge) {
   Symbol L, R;
TEST(MergeTest, PreferSymbolWithDefn) {
 
   R.Definition.FileURI = "file:/right.cpp"; // Now right will be favored.
   M = mergeSymbol(L, R);
   EXPECT_EQ(M.CanonicalDeclaration.FileURI, "file:/right.h");
   EXPECT_EQ(M.Definition.FileURI, "file:/right.cpp");
   EXPECT_EQ(M.Name, "right");
 }
 
-TEST(MergeIndexTest, FindOccurrences) {
+TEST(MergeIndexTest, Refs) {
   FileIndex Dyn({"unittest"});
   FileIndex StaticIndex({"unittest"});
   auto MergedIndex = mergeIndex(&Dyn, &StaticIndex);
 
   const char *HeaderCode = "class Foo;";
   auto HeaderSymbols = TestTU::withHeaderCode("class Foo;").headerSymbols();
   auto Foo = findSymbol(HeaderSymbols, "Foo");
 
   // Build dynamic index for test.cc.
   Annotations Test1Code(R"(class $Foo[[Foo]];)");
   TestTU Test;
   Test.HeaderCode = HeaderCode;
   Test.Code = Test1Code.code();
   Test.Filename = "test.cc";
   auto AST = Test.build();
   Dyn.update(Test.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(),
              AST.getLocalTopLevelDecls());
 
   // Build static index for test.cc.
   Test.HeaderCode = HeaderCode;
   Test.Code = "// static\nclass Foo {};";
   Test.Filename = "test.cc";
   auto StaticAST = Test.build();
-  // Add stale occurrences for test.cc.
+  // Add stale refs for test.cc.
   StaticIndex.update(Test.Filename, &StaticAST.getASTContext(),
                      StaticAST.getPreprocessorPtr(),
                      StaticAST.getLocalTopLevelDecls());
 
-  // Add occcurrences for test2.cc
+  // Add refs for test2.cc
   Annotations Test2Code(R"(class $Foo[[Foo]] {};)");
   TestTU Test2;
   Test2.HeaderCode = HeaderCode;
   Test2.Code = Test2Code.code();
   Test2.Filename = "test2.cc";
   StaticAST = Test2.build();
   StaticIndex.update(Test2.Filename, &StaticAST.getASTContext(),
                      StaticAST.getPreprocessorPtr(),
                      StaticAST.getLocalTopLevelDecls());
 
-  OccurrencesRequest Request;
+  RefsRequest Request;
   Request.IDs = {Foo.ID};
-  Request.Filter = AllOccurrenceKinds;
-  std::vector<SymbolOccurrence> Results;
-  MergedIndex->findOccurrences(
-      Request, [&](const SymbolOccurrence &O) { Results.push_back(O); });
+  RefSlab::Builder Results;
+  MergedIndex->refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); });
 
-  EXPECT_THAT(Results, UnorderedElementsAre(
-                           AllOf(OccurrenceRange(Test1Code.range("Foo")),
+  EXPECT_THAT(
+      std::move(Results).build(),
+      ElementsAre(Pair(
+          _, UnorderedElementsAre(AllOf(RefRange(Test1Code.range("Foo")),
                                         FileURI("unittest:///test.cc")),
-                           AllOf(OccurrenceRange(Test2Code.range("Foo")),
-                                 FileURI("unittest:///test2.cc"))));
+                                  AllOf(RefRange(Test2Code.range("Foo")),
+                                        FileURI("unittest:///test2.cc"))))));
 }
 
 MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References,  "") {
   return (arg.IncludeHeader == IncludeHeader) && (arg.References == References);
 }
 
 TEST(MergeTest, MergeIncludesOnDifferentDefinitions) {
   Symbol L, R;

unittests/clangd/SymbolCollectorTests.cpp

 #include <memory>
 #include <string>
 
 namespace clang {
 namespace clangd {
 
 namespace {
 
+using testing::_;
 using testing::AllOf;
+using testing::Contains;
 using testing::Eq;
 using testing::Field;
 using testing::IsEmpty;
 using testing::Not;
+using testing::Pair;
 using testing::UnorderedElementsAre;
 using testing::UnorderedElementsAreArray;
 
 // GMock helpers for matching Symbol.
 MATCHER_P(Labeled, Label, "") {
   return (arg.Name + arg.Signature).str() == Label;
 }
 MATCHER(HasReturnType, "") { return !arg.ReturnType.empty(); }

 }
 MATCHER_P(DefRange, Pos, "") {
   return std::tie(arg.Definition.Start.Line,
                   arg.Definition.Start.Column, arg.Definition.End.Line,
                   arg.Definition.End.Column) ==
          std::tie(Pos.start.line, Pos.start.character, Pos.end.line,
                   Pos.end.character);
 }
-MATCHER_P(Refs, R, "") { return int(arg.References) == R; }
+MATCHER_P(RefCount, R, "") { return int(arg.References) == R; }
 MATCHER_P(ForCodeCompletion, IsIndexedForCodeCompletion, "") {
   return arg.IsIndexedForCodeCompletion == IsIndexedForCodeCompletion;
 }
-MATCHER(OccurrenceRange, "") {
-  const SymbolOccurrence &Pos = testing::get<0>(arg);
+MATCHER(RefRange, "") {
+  const Ref &Pos = testing::get<0>(arg);
   const Range &Range = testing::get<1>(arg);
   return std::tie(Pos.Location.Start.Line, Pos.Location.Start.Column,
                   Pos.Location.End.Line, Pos.Location.End.Column) ==
          std::tie(Range.start.line, Range.start.character, Range.end.line,
                   Range.end.character);
 }
-testing::Matcher<const std::vector<SymbolOccurrence> &>
+testing::Matcher<const std::vector<Ref> &>
 HaveRanges(const std::vector<Range> Ranges) {
-  return testing::UnorderedPointwise(OccurrenceRange(), Ranges);
+  return testing::UnorderedPointwise(RefRange(), Ranges);
 }
 
 class ShouldCollectSymbolTest : public ::testing::Test {
 public:
   void build(StringRef HeaderCode, StringRef Code = "") {
     File.HeaderFilename = HeaderName;
     File.Filename = FileName;
     File.HeaderCode = HeaderCode;
tooling::ToolInvocation Invocation(
         std::make_shared<PCHContainerOperations>());
 
     InMemoryFileSystem->addFile(TestHeaderName, 0,
                                 llvm::MemoryBuffer::getMemBuffer(HeaderCode));
     InMemoryFileSystem->addFile(TestFileName, 0,
                                 llvm::MemoryBuffer::getMemBuffer(MainCode));
     Invocation.run();
     Symbols = Factory->Collector->takeSymbols();
-    SymbolOccurrences = Factory->Collector->takeOccurrences();
+    Refs = Factory->Collector->takeRefs();
     return true;
   }
 
 protected:
   llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem;
   std::string TestHeaderName;
   std::string TestHeaderURI;
   std::string TestFileName;
   std::string TestFileURI;
   SymbolSlab Symbols;
-  SymbolOccurrenceSlab SymbolOccurrences;
+  RefSlab Refs;
   SymbolCollector::Options CollectorOpts;
   std::unique_ptr<CommentHandler> PragmaHandler;
 };
 
 TEST_F(SymbolCollectorTest, CollectSymbols) {
   const std::string Header = R"(
     class Foo {
       Foo() {}
EXPECT_THAT(
                 DefRange(Main.range("clsdef"))),
           AllOf(QName("print"), DeclRange(Header.range("printdecl")),
                 DefRange(Main.range("printdef"))),
           AllOf(QName("Z"), DeclRange(Header.range("zdecl"))),
           AllOf(QName("foo"), DeclRange(Header.range("foodecl")))
           ));
 }
 
-TEST_F(SymbolCollectorTest, Occurrences) {
+TEST_F(SymbolCollectorTest, Refs) {
   Annotations Header(R"(
   class $foo[[Foo]] {
   public:
     $foo[[Foo]]() {}
     $foo[[Foo]](int);
   };
   class $bar[[Bar]];
   void $func[[func]]();
TEST_F(SymbolCollectorTest, Refs) {
   }
   )");
   Annotations SymbolsOnlyInMainCode(R"(
   int a;
   void b() {}
   static const int c = 0;
   class d {};
   )");
-  CollectorOpts.OccurrenceFilter = AllOccurrenceKinds;
+  CollectorOpts.RefFilter = RefKind::All;
   runSymbolCollector(Header.code(),
                      (Main.code() + SymbolsOnlyInMainCode.code()).str());
   auto HeaderSymbols = TestTU::withHeaderCode(Header.code()).headerSymbols();
 
-  EXPECT_THAT(SymbolOccurrences.find(findSymbol(Symbols, "Foo").ID),
-              HaveRanges(Main.ranges("foo")));
-  EXPECT_THAT(SymbolOccurrences.find(findSymbol(Symbols, "Bar").ID),
-              HaveRanges(Main.ranges("bar")));
-  EXPECT_THAT(SymbolOccurrences.find(findSymbol(Symbols, "func").ID),
-              HaveRanges(Main.ranges("func")));
-
-  // Retrieve IDs for symbols *only* in the main file, and verify these symbols
-  // are not collected.
+  EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "Foo").ID,
+                                  HaveRanges(Main.ranges("foo")))));
+  EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "Bar").ID,
+                                  HaveRanges(Main.ranges("bar")))));
+  EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "func").ID,
+                                  HaveRanges(Main.ranges("func")))));
+  // Symbols *only* in the main file (a, b, c) had no refs collected.
   auto MainSymbols =
       TestTU::withHeaderCode(SymbolsOnlyInMainCode.code()).headerSymbols();
-  EXPECT_THAT(SymbolOccurrences.find(findSymbol(MainSymbols, "a").ID),
-              IsEmpty());
-  EXPECT_THAT(SymbolOccurrences.find(findSymbol(MainSymbols, "b").ID),
-              IsEmpty());
-  EXPECT_THAT(SymbolOccurrences.find(findSymbol(MainSymbols, "c").ID),
-              IsEmpty());
+  EXPECT_THAT(Refs, Not(Contains(Pair(findSymbol(MainSymbols, "a").ID, _))));
+  EXPECT_THAT(Refs, Not(Contains(Pair(findSymbol(MainSymbols, "b").ID, _))));
+  EXPECT_THAT(Refs, Not(Contains(Pair(findSymbol(MainSymbols, "c").ID, _))));
 }
 
 TEST_F(SymbolCollectorTest, References) {
   const std::string Header = R"(
     class W;
     class X {};
     class Y;
     class Z {}; // not used anywhere
     Y* y = nullptr;  // used in header doesn't count
     #define GLOBAL_Z(name) Z name;
   )";
   const std::string Main = R"(
     W* w = nullptr;
     W* w2 = nullptr; // only one usage counts
     X x();
     class V;
     V* v = nullptr; // Used, but not eligible for indexing.
     class Y{}; // definition doesn't count as a reference
     GLOBAL_Z(z); // Not a reference to Z, we don't spell the type.
   )";
   CollectorOpts.CountReferences = true;
   runSymbolCollector(Header, Main);
   EXPECT_THAT(Symbols,
-              UnorderedElementsAre(AllOf(QName("W"), Refs(1)),
-                                   AllOf(QName("X"), Refs(1)),
-                                   AllOf(QName("Y"), Refs(0)),
-                                   AllOf(QName("Z"), Refs(0)), QName("y")));
+              UnorderedElementsAre(AllOf(QName("W"), RefCount(1)),
+                                   AllOf(QName("X"), RefCount(1)),
+                                   AllOf(QName("Y"), RefCount(0)),
+                                   AllOf(QName("Z"), RefCount(0)), QName("y")));
 }
 
 TEST_F(SymbolCollectorTest, SymbolRelativeNoFallback) {
   runSymbolCollector("class Foo {};", /*Main=*/"");
   EXPECT_THAT(Symbols, UnorderedElementsAre(
                            AllOf(QName("Foo"), DeclURI(TestHeaderURI))));
 }
 
TEST_F(SymbolCollectorTest, ReferencesInFriendDecl) {
   const std::string Main = R"(
     class C {
       friend ::X;
       friend class Y;
     };
   )";
   CollectorOpts.CountReferences = true;
   runSymbolCollector(Header, Main);
-  EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(QName("X"), Refs(1)),
-                                            AllOf(QName("Y"), Refs(1))));
+  EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(QName("X"), RefCount(1)),
+                                            AllOf(QName("Y"), RefCount(1))));
 }
 
 TEST_F(SymbolCollectorTest, Origin) {
   CollectorOpts.Origin = SymbolOrigin::Static;
   runSymbolCollector("class Foo {};", /*Main=*/"");
   EXPECT_THAT(Symbols, UnorderedElementsAre(
                            Field(&Symbol::Origin, SymbolOrigin::Static)));
 }
TEST_F(SymbolCollectorTest, CollectMacros) {
   )");
   const std::string Main = R"(
     #define MAIN 1  // not indexed
     USED(t);
   )";
   CollectorOpts.CountReferences = true;
   CollectorOpts.CollectMacro = true;
   runSymbolCollector(Header.code(), Main);
-  EXPECT_THAT(
-      Symbols,
-      UnorderedElementsAre(
-          QName("p"),
+  EXPECT_THAT(Symbols,
+              UnorderedElementsAre(QName("p"),
                                    AllOf(QName("X"), DeclURI(TestHeaderURI),
                                          IncludeHeader(TestHeaderURI)),
-          AllOf(Labeled("MAC(x)"), Refs(0), DeclRange(Header.range("mac"))),
-          AllOf(Labeled("USED(y)"), Refs(1), DeclRange(Header.range("used")))));
+                                   AllOf(Labeled("MAC(x)"), RefCount(0),
+                                         DeclRange(Header.range("mac"))),
+                                   AllOf(Labeled("USED(y)"), RefCount(1),
+                                         DeclRange(Header.range("used")))));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/TestTU.cpp

 }
 
 SymbolSlab TestTU::headerSymbols() const {
   auto AST = build();
   return indexAST(AST.getASTContext(), AST.getPreprocessorPtr()).first;
 }
 
 std::unique_ptr<SymbolIndex> TestTU::index() const {
-  // FIXME: we should generate proper occurrences for TestTU.
-  return MemIndex::build(headerSymbols(), SymbolOccurrenceSlab::createEmpty());
+  // FIXME: we should generate proper refs for TestTU.
+  return MemIndex::build(headerSymbols(), RefSlab());
 }
 
 const Symbol &findSymbol(const SymbolSlab &Slab, llvm::StringRef QName) {
   const Symbol *Result = nullptr;
   for (const Symbol &S : Slab) {
     if (QName != (S.Scope + S.Name).str())
       continue;
     if (Result) {