[clangd] *Prototype* Drop dynamic index symbols from files that are already indexed in static index.

[ioeric]

Summary

Currently, dynamic index collects symbols for the entire TU for each open/active
file. When static index is enabled, this can be wasteful as (intuitively) most files in a
TU should remain the same. Duplicate symbols in both dynamic index and static index can
lead to unncessary memory usage and merging duplcated symbols can contribute to latency.

To avoid indexing the same files in both dynamic index and static index, we also collect
hash values/digests for all headers in the TU during indexing time and expose an interface
from the index to get digests for files. Dynamic/file index can simply drop symbols from
files whose digests are the same as those in static index.

[ioeric]

Code is not polished. I'd like to get some high-level feedback before proceeding further and splitting this into smaller patches.

clangd/ClangdServer.cpp

 
 ClangdServer::ClangdServer(GlobalCompilationDatabase &CDB,
                            FileSystemProvider &FSProvider,
                            DiagnosticsConsumer &DiagConsumer,
                            const Options &Opts)
     : CDB(CDB), DiagConsumer(DiagConsumer), FSProvider(FSProvider),
       ResourceDir(Opts.ResourceDir ? Opts.ResourceDir->str()
                                    : getStandardResourceDir()),
-      FileIdx(Opts.BuildDynamicSymbolIndex ? new FileIndex(Opts.URISchemes)
-                                           : nullptr),
+      FileIdx(Opts.BuildDynamicSymbolIndex
+                  ? new FileIndex(Opts.URISchemes, Opts.StaticIndex)
       PCHs(std::make_shared<PCHContainerOperations>()),
       // Pass a callback into `WorkScheduler` to extract symbols from a newly
       // parsed file and rebuild the file index synchronously each time an AST
       // is parsed.
       // FIXME(ioeric): this can be slow and we may be able to index on less
       // critical paths.
       WorkScheduler(
           Opts.AsyncThreadsCount, Opts.StorePreamblesInMemory,

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

 #include "clang/Tooling/Execution.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/ThreadPool.h"
 #include "llvm/Support/YAMLTraits.h"
+#include <sstream>
+#include <string>
 
 using namespace llvm;
 using namespace clang::tooling;
 using clang::clangd::SymbolSlab;
 
 namespace clang {
 namespace clangd {
 namespace {
 
+// The index to prepend to
+const llvm::StringRef kFileDigestKeyPrefix = "digest:";
+
 static llvm::cl::opt<std::string> AssumedHeaderDir(
     "assume-header-dir",
     llvm::cl::desc("The index includes header that a symbol is defined in. "
                    "If the absolute path cannot be determined (e.g. an "
                    "in-memory VFS) then the relative path is resolved against "
                    "this directory, which must be absolute. If this flag is "
                    "not given, such headers will have relative paths."),
     llvm::cl::init(""));
public:
             CI.getDiagnostics().hasUncompilableErrorOccurred()) {
           llvm::errs()
               << "Found uncompilable errors in the translation unit. Igoring "
                  "collected symbols...\n";
           return;
         }
 
         auto Symbols = Collector->takeSymbols();
-        for (const auto &Sym : Symbols) {
+        for (const auto &Sym : Symbols)
           Ctx->reportResult(Sym.ID.str(), SymbolToYAML(Sym));
-        }
+        for (const auto &Digest : Symbols.fileDigests())
+          Ctx->reportResult((kFileDigestKeyPrefix + Digest.first).str(),
+                            std::to_string(Digest.second));
       }
 
     private:
       tooling::ExecutionContext *Ctx;
       std::shared_ptr<SymbolCollector> Collector;
       std::unique_ptr<CanonicalIncludes> Includes;
       std::unique_ptr<CommentHandler> PragmaHandler;
     };

 };
 
 // Combine occurrences of the same symbol across translation units.
 SymbolSlab mergeSymbols(tooling::ToolResults *Results) {
   SymbolSlab::Builder UniqueSymbols;
   llvm::BumpPtrAllocator Arena;
   Symbol::Details Scratch;
   Results->forEachResult([&](llvm::StringRef Key, llvm::StringRef Value) {
+    if (Key.startswith(kFileDigestKeyPrefix)) {
+      size_t Digest;
+      std::stringstream(Value) >> Digest;
+      UniqueSymbols.addFileDigest(Key.substr(kFileDigestKeyPrefix.size()),
+                                  Digest);
+    } else {
       Arena.Reset();
       llvm::yaml::Input Yin(Value, &Arena);
       auto Sym = clang::clangd::SymbolFromYAML(Yin, Arena);
       clang::clangd::SymbolID ID;
       Key >> ID;
       if (const auto *Existing = UniqueSymbols.find(ID))
         UniqueSymbols.insert(mergeSymbol(*Existing, Sym, &Scratch));
       else
         UniqueSymbols.insert(Sym);
+    }
   });
   return std::move(UniqueSymbols).build();
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang
 

clangd/index/FileIndex.h

 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
 
 #include "../ClangdUnit.h"
 #include "Index.h"
 #include "MemIndex.h"
 #include "clang/Lex/Preprocessor.h"
+#include "llvm/ADT/DenseMap.h"
 
 namespace clang {
 namespace clangd {
 
 /// \brief A container of Symbols from several source files. It can be updated
 /// at source-file granularity, replacing all symbols from one file with a new
 /// set.
 ///
 /// This implements a snapshot semantics for symbols in a file. Each update to a
 /// file will create a new snapshot for all symbols in the file. Snapshots are
 /// managed with shared pointers that are shared between this class and the
 /// 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 refereces to snapshots.
 class FileSymbols {
 public:
   /// \brief Updates all symbols in a file. If \p Slab is nullptr, symbols for
   /// \p Path will be removed.
   void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab);
 
   // The shared_ptr keeps the symbols alive
-  std::shared_ptr<std::vector<const Symbol *>> allSymbols();
+  std::shared_ptr<MemIndex::SymbolSlabView> allSymbols();
 
 private:
   mutable std::mutex Mutex;
 
   /// \brief Stores the latest snapshots for all active files.
   llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSlabs;
 };
 
 /// \brief This manages symbls from files and an in-memory index on all symbols.
 class FileIndex : public SymbolIndex {
 public:
-  /// If URISchemes is empty, the default schemes in SymbolCollector will be
+  /// If \p URISchemes is empty, the default schemes in SymbolCollector will be
   /// used.
-  FileIndex(std::vector<std::string> URISchemes = {});
+  /// \p OverlayedIndex is optional underlying index overlayed by the file
+  /// index. If an overlayed index is provided, this will ignore symbols from
+  /// headers whose file digests are the same.
+  FileIndex(std::vector<std::string> URISchemes = {},
+            const SymbolIndex *OverlayedIndex = nullptr);
 
   /// \brief Update symbols in \p Path with symbols in \p AST. If \p AST is
   /// nullptr, this removes all symbols in the file.
   /// If \p AST is not null, \p PP cannot be null and it should be the
   /// preprocessor that was used to build \p AST.
   void update(PathRef Path, ASTContext *AST, std::shared_ptr<Preprocessor> PP);
 
   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
+  fileDigests(const FileDigestRequest &Req,
+              llvm::function_ref<void(llvm::StringRef URI, FileDigest Digest)>
+                  Callback) const override;
+
 private:
   FileSymbols FSymbols;
   MemIndex Index;
   std::vector<std::string> URISchemes;
+  const SymbolIndex *OverlayedIndex;
 };
 
 /// 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 "Index.h"
+#include "MemIndex.h"
 #include "SymbolCollector.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Lex/Preprocessor.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 
 namespace clang {
 namespace clangd {
 
 SymbolSlab indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
                     llvm::ArrayRef<std::string> URISchemes) {
   SymbolCollector::Options CollectorOpts;
   // FIXME(ioeric): we might also want to collect include headers. We would need
SymbolSlab indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
   std::vector<const Decl *> TopLevelDecls(
       AST.getTranslationUnitDecl()->decls().begin(),
       AST.getTranslationUnitDecl()->decls().end());
   index::indexTopLevelDecls(AST, TopLevelDecls, Collector, IndexOpts);
 
   return Collector.takeSymbols();
 }
 
-FileIndex::FileIndex(std::vector<std::string> URISchemes)
-    : URISchemes(std::move(URISchemes)) {}
+FileIndex::FileIndex(std::vector<std::string> URISchemes,
+                     const SymbolIndex *OverlayedIndex)
+    : URISchemes(std::move(URISchemes)), OverlayedIndex(OverlayedIndex) {}
 
 void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Slab) {
   std::lock_guard<std::mutex> Lock(Mutex);
   if (!Slab)
     FileToSlabs.erase(Path);
   else
     FileToSlabs[Path] = std::move(Slab);
 }
 
-std::shared_ptr<std::vector<const Symbol *>> FileSymbols::allSymbols() {
+std::shared_ptr<MemIndex::SymbolSlabView> FileSymbols::allSymbols() {
   // The snapshot manages life time of symbol slabs and provides pointers of all
   // symbols in all slabs.
   struct Snapshot {
-    std::vector<const Symbol *> Pointers;
+    MemIndex::SymbolSlabView View;
     std::vector<std::shared_ptr<SymbolSlab>> KeepAlive;
   };
+
   auto Snap = std::make_shared<Snapshot>();
   {
     std::lock_guard<std::mutex> Lock(Mutex);
 
     for (const auto &FileAndSlab : FileToSlabs) {
       Snap->KeepAlive.push_back(FileAndSlab.second);
       for (const auto &Iter : *FileAndSlab.second)
-        Snap->Pointers.push_back(&Iter);
+        Snap->View.Pointers.push_back(&Iter);
+      const auto &SlabDigests = FileAndSlab.second->fileDigests();
+      Snap->View.Digests.insert(SlabDigests.begin(), SlabDigests.end());
     }
   }
-  auto *Pointers = &Snap->Pointers;
+  auto *View = &Snap->View;
   // Use aliasing constructor to keep the snapshot alive along with the
   // pointers.
-  return {std::move(Snap), Pointers};
+  return {std::move(Snap), View};
+}
+
+static SymbolSlab dropSymbolsFromIndexedFiles(const SymbolIndex &Index,
+                                              SymbolSlab Slab) {
+  const auto &SlabDigests = Slab.fileDigests();
+  FileDigestRequest Req;
+  for (const auto &Digest : SlabDigests)
+    Req.URIs.insert(Digest.first);
+
+  llvm::StringSet<> IndexedURIs;
+  Index.fileDigests(Req, [&](StringRef URI, FileDigest Digest) {
+    auto I = SlabDigests.find(URI);
+    if ((I != SlabDigests.end()) && (I->second == Digest))
+      IndexedURIs.insert(URI);
+  });
+  if (IndexedURIs.empty())
+    return Slab;
+  SymbolSlab::Builder Syms;
+  for (const auto &Sym : Slab)
+    if (IndexedURIs.find(Sym.CanonicalDeclaration.FileURI) == IndexedURIs.end())
+      Syms.insert(Sym);
+  for (const auto &Digest : SlabDigests)
+    Syms.addFileDigest(Digest.first, Digest.second);
+  return std::move(Syms).build();
 }
 
 void FileIndex::update(PathRef Path, ASTContext *AST,
                        std::shared_ptr<Preprocessor> PP) {
   if (!AST) {
     FSymbols.update(Path, nullptr);
   } else {
     assert(PP);
     auto Slab = llvm::make_unique<SymbolSlab>();
-    *Slab = indexAST(*AST, PP, URISchemes);
+    auto ASTSlab = indexAST(*AST, PP, URISchemes);
+    *Slab = OverlayedIndex ? dropSymbolsFromIndexedFiles(*OverlayedIndex,
+                                                         std::move(ASTSlab))
+                           : std::move(ASTSlab);
     FSymbols.update(Path, std::move(Slab));
   }
   auto Symbols = FSymbols.allSymbols();
   Index.build(std::move(Symbols));
 }
 
 bool FileIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   return Index.fuzzyFind(Req, Callback);
 }
 
 void FileIndex::lookup(
     const LookupRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   Index.lookup(Req, Callback);
 }
 
+void FileIndex::fileDigests(
+    const FileDigestRequest &Req,
+    llvm::function_ref<void(llvm::StringRef URI, FileDigest Digest)> Callback)
+    const {
+  Index.fileDigests(Req, Callback);
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/Index.h

 //===--- Index.h ------------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Lex/Lexer.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 #include <array>
+#include <cstdint>
 #include <string>
 
 namespace clang {
 namespace clangd {
 
 struct SymbolLocation {
   // Specify a position (Line, Column) of symbol. Using Line/Column allows us to
   // build LSP responses without reading the file content.

 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.
 double quality(const Symbol &S);
 
+using FileDigest = uint64_t;
+
 // An immutable symbol container that stores a set of symbols.
 // The container will maintain the lifetime of the symbols.
 class SymbolSlab {
 public:
   using const_iterator = std::vector<Symbol>::const_iterator;
   using iterator = const_iterator;
+  using FileDigests = llvm::DenseMap<llvm::StringRef, FileDigest>;
 
   SymbolSlab() = default;
 
   const_iterator begin() const { return Symbols.begin(); }
   const_iterator end() const { return Symbols.end(); }
   const_iterator find(const SymbolID &SymID) const;
 
+  // Note that the string reference keys do not own the underlying string data.
+  const FileDigests &fileDigests() const { return Digests; }
+
   size_t size() const { return Symbols.size(); }
   // Estimates the total memory usage.
   size_t bytes() const {
     return sizeof(*this) + Arena.getTotalMemory() +
            Symbols.capacity() * sizeof(Symbol);
   }
 
   // SymbolSlab::Builder is a mutable container that can 'freeze' to SymbolSlab.
   // The frozen SymbolSlab will use less memory.
   class Builder {
   public:
     // Adds a symbol, overwriting any existing one with the same ID.
     // This is a deep copy: underlying strings will be owned by the slab.
     void insert(const Symbol &S);
 
     // Returns the symbol with an ID, if it exists. Valid until next insert().
     const Symbol *find(const SymbolID &ID) {
       auto I = SymbolIndex.find(ID);
       return I == SymbolIndex.end() ? nullptr : &Symbols[I->second];
     }
 
+    // Adds the digest for the header file with \p URI.
+    void addFileDigest(llvm::StringRef URI, size_t Digest);
+
     // Consumes the builder to finalize the slab.
     SymbolSlab build() &&;
 
   private:
     llvm::BumpPtrAllocator Arena;
     // Intern table for strings. Contents are on the arena.
     llvm::DenseSet<llvm::StringRef> Strings;
     std::vector<Symbol> Symbols;
     // Values are indices into Symbols vector.
     llvm::DenseMap<SymbolID, size_t> SymbolIndex;
+    FileDigests Digests;
   };
 
 private:
-  SymbolSlab(llvm::BumpPtrAllocator Arena, std::vector<Symbol> Symbols)
-      : Arena(std::move(Arena)), Symbols(std::move(Symbols)) {}
+  SymbolSlab(llvm::BumpPtrAllocator Arena, std::vector<Symbol> Symbols,
+             FileDigests Digests)
+      : Arena(std::move(Arena)), Symbols(std::move(Symbols)),
+        Digests(std::move(Digests)) {}
 
   llvm::BumpPtrAllocator Arena; // Owns Symbol data that the Symbols do not.
   std::vector<Symbol> Symbols;  // Sorted by SymbolID to allow lookup.
+  // Digests of all header files in TU.
+  FileDigests Digests;
 };
 
 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 {
   /// Paths should be absolute.
   std::vector<std::string> ProximityPaths;
 };
 
 struct LookupRequest {
   llvm::DenseSet<SymbolID> IDs;
 };
 
+struct FileDigestRequest {
+  llvm::StringSet<> URIs;
+};
+
 /// \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;
 
+  /// Gets digests of all files in the index. If a file is not indexed, no
+  /// digest will be returned.
+  virtual void
+  fileDigests(const FileDigestRequest &Req,
+              llvm::function_ref<void(llvm::StringRef URI, FileDigest Digest)>)
+      const = 0;
+
   // FIXME: add interfaces for more index use cases:
   //  - getAllOccurrences(SymbolID);
 };
 
 } // namespace clangd
 } // namespace clang
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clangd/index/Index.cpp

 //===--- Index.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Index.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
auto It = std::lower_bound(Symbols.begin(), Symbols.end(), ID,
                              [](const Symbol &S, const SymbolID &I) {
                                return S.ID < I;
                              });
   if (It != Symbols.end() && It->ID == ID)
     return It;
   return Symbols.end();
 }
 
-// Copy the underlying data of the symbol into the owned arena.
-static void own(Symbol &S, DenseSet<StringRef> &Strings,
-                BumpPtrAllocator &Arena) {
-  // Intern replaces V with a reference to the same string owned by the arena.
-  auto Intern = [&](StringRef &V) {
-    auto R = Strings.insert(V);
-    if (R.second) { // New entry added to the table, copy the string.
-      *R.first = V.copy(Arena);
-    }
-    V = *R.first;
-  };
+// Returns a reference to the same string as \p V owned by the arena.
+static StringRef InternStr(DenseSet<StringRef> &Strings,
+                           BumpPtrAllocator &Arena, StringRef &V) {
+  return *R.first;
+}
+
+// Copy the underlying data of the symbol into the owned arena.
+static void own(Symbol &S, DenseSet<StringRef> &Strings,
+                BumpPtrAllocator &Arena) {
+  auto Intern = [&](StringRef &V) { V = InternStr(Strings, Arena, V); };
 
   // We need to copy every StringRef field onto the arena.
   Intern(S.Name);
   Intern(S.Scope);
   Intern(S.CanonicalDeclaration.FileURI);
   Intern(S.Definition.FileURI);
 
   Intern(S.Signature);
if (R.second) {
     Symbols.push_back(S);
     own(Symbols.back(), Strings, Arena);
   } else {
     auto &Copy = Symbols[R.first->second] = S;
     own(Copy, Strings, Arena);
   }
 }
 
+void SymbolSlab::Builder::addFileDigest(llvm::StringRef URI, size_t Digest) {
+  Digests[InternStr(Strings, Arena, URI)] = Digest;
+}
+
 SymbolSlab SymbolSlab::Builder::build() && {
   Symbols = {Symbols.begin(), Symbols.end()}; // Force shrink-to-fit.
   // Sort symbols so the slab can binary search over them.
   std::sort(Symbols.begin(), Symbols.end(),
             [](const Symbol &L, const Symbol &R) { return L.ID < R.ID; });
   // We may have unused strings from overwritten symbols. Build a new arena.
   BumpPtrAllocator NewArena;
   DenseSet<StringRef> Strings;
   for (auto &S : Symbols)
     own(S, Strings, NewArena);
-  return SymbolSlab(std::move(NewArena), std::move(Symbols));
+  for (auto &D : Digests)
+    D.getFirst() = InternStr(Strings, NewArena, D.getFirst());
+  return SymbolSlab(std::move(NewArena), std::move(Symbols),
+                    std::move(Digests));
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/MemIndex.h

 
 namespace clang {
 namespace clangd {
 
 /// \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);
+  /// A view of a set symbols. This does not own the underlying data of symbols.
+  struct SymbolSlabView {
+    std::vector<const Symbol *> Pointers;
+    SymbolSlab::FileDigests Digests;
+  };
+  /// \brief (Re-)Build index for `Symbols`. All symbol pointers and references
+  /// must remain accessible as long as `Symbols` is kept alive.
+  void build(std::shared_ptr<SymbolSlabView> 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
-  lookup(const LookupRequest &Req,
+  void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
+  void
+  fileDigests(const FileDigestRequest &Req,
+              llvm::function_ref<void(llvm::StringRef URI, FileDigest Digest)>
+                  Callback) const override;
+
 private:
-  std::shared_ptr<std::vector<const Symbol *>> Symbols;
+  std::shared_ptr<SymbolSlabView> 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

 #include "MemIndex.h"
 #include "../FuzzyMatch.h"
 #include "../Logger.h"
 #include <queue>
 
 namespace clang {
 namespace clangd {
 
-void MemIndex::build(std::shared_ptr<std::vector<const Symbol *>> Syms) {
+void MemIndex::build(std::shared_ptr<SymbolSlabView> Syms) {
   llvm::DenseMap<SymbolID, const Symbol *> TempIndex;
-  for (const Symbol *Sym : *Syms)
+  for (const Symbol *Sym : Syms->Pointers)
     TempIndex[Sym->ID] = Sym;
 
   // Swap out the old symbols and index.
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     Index = std::move(TempIndex);
     Symbols = std::move(Syms); // Relase old symbols.
   }
bool More = false;
     for (; !Top.empty(); Top.pop())
       Callback(*Top.top().second);
   }
   return More;
 }
 
 void MemIndex::lookup(const LookupRequest &Req,
                       llvm::function_ref<void(const Symbol &)> Callback) const {
+  std::lock_guard<std::mutex> Lock(Mutex);
   for (const auto &ID : Req.IDs) {
     auto I = Index.find(ID);
     if (I != Index.end())
       Callback(*I->second);
   }
 }
 
+void MemIndex::fileDigests(
+    const FileDigestRequest &Req,
+    llvm::function_ref<void(llvm::StringRef URI, FileDigest Digest)> Callback)
+    const {
+  std::lock_guard<std::mutex> Lock(Mutex);
+  for (auto &U : Req.URIs) {
+    auto I = Symbols->Digests.find(StringRef(U.getKey()));
+    if (I != Symbols->Digests.end())
+      Callback(I->first, I->second);
+  }
+}
+
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab) {
   struct Snapshot {
     SymbolSlab Slab;
-    std::vector<const Symbol *> Pointers;
+    SymbolSlabView View;
   };
   auto Snap = std::make_shared<Snapshot>();
   Snap->Slab = std::move(Slab);
   for (auto &Sym : Snap->Slab)
-    Snap->Pointers.push_back(&Sym);
-  auto S = std::shared_ptr<std::vector<const Symbol *>>(std::move(Snap),
-                                                        &Snap->Pointers);
+    Snap->View.Pointers.push_back(&Sym);
+  const auto &SlabDigests = Snap->Slab.fileDigests();
+  Snap->View.Digests.insert(SlabDigests.begin(), SlabDigests.end());
+
+  auto S = std::shared_ptr<SymbolSlabView>(std::move(Snap), &Snap->View);
   auto MemIdx = llvm::make_unique<MemIndex>();
   MemIdx->build(std::move(S));
   return std::move(MemIdx);
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/Merge.cpp

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 fileDigests(const FileDigestRequest &Req,
+                   llvm::function_ref<void(StringRef URI, FileDigest Digest)>
+                       Callback) const override {
+    llvm::StringMap<FileDigest> Digests;
+    // Query the static index first so that dynamic index can override digests
+    // for the common files later.
+    Static->fileDigests(Req,
+                        [&](StringRef U, FileDigest D) { Digests[U] = D; });
+    Dynamic->fileDigests(Req,
+                         [&](StringRef U, FileDigest D) { Digests[U] = D; });
+    for (const auto &Digest : Digests)
+      Callback(Digest.first(), Digest.second);
+  }
+
 private:
   const SymbolIndex *Dynamic, *Static;
 };
 } // namespace
 
 Symbol
 mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch) {
   assert(L.ID == R.ID);

clangd/index/SymbolCollector.h

 //===--- SymbolCollector.h ---------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CanonicalIncludes.h"
 #include "Index.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 
 namespace clang {
 namespace clangd {
 
 /// \brief Collect declarations (symbols) from an AST.
public:
 
   SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
 
   void finish() override;
 
 private:
   const Symbol *addDeclaration(const NamedDecl &, SymbolID);
   void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
+  void addFileDigest(StringRef URI, const SourceManager &SM, FileID FID);
 
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
   ASTContext *ASTCtx;
   std::shared_ptr<Preprocessor> PP;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
   std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo;
   Options Opts;
   // Symbols referenced from the current TU, flushed on finish().
   llvm::DenseSet<const NamedDecl *> ReferencedDecls;
   llvm::DenseSet<const IdentifierInfo *> ReferencedMacros;
   // 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;
+  // URIs whose digests have been recorded. Reset on finish().
+  llvm::DenseSet<StringRef> Digested;
 };
 
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.cpp

 #include "SymbolCollector.h"
 #include "../AST.h"
 #include "../CodeComplete.h"
 #include "../CodeCompletionStrings.h"
 #include "../Logger.h"
 #include "../SourceCode.h"
 #include "../URI.h"
 #include "CanonicalIncludes.h"
+#include "SymbolYAML.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/USRGeneration.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 
 namespace {
bool SymbolCollector::handleDeclOccurence(
 
   llvm::SmallString<128> USR;
   if (index::generateUSRForDecl(ND, USR))
     return true;
   SymbolID ID(USR);
 
   const NamedDecl &OriginalDecl = *cast<NamedDecl>(ASTNode.OrigD);
   const Symbol *BasicSymbol = Symbols.find(ID);
+  FileID FID = SM.getFileID(findNameLoc(ND));
   if (!BasicSymbol) // Regardless of role, ND is the canonical declaration.
     BasicSymbol = addDeclaration(*ND, std::move(ID));
-  else if (isPreferredDeclaration(OriginalDecl, Roles))
+  else if (isPreferredDeclaration(OriginalDecl, Roles)) {
     // If OriginalDecl is preferred, replace the existing canonical
     // declaration (e.g. a class forward declaration). There should be at most
     // one duplicate as we expect to see only one preferred declaration per
     // TU, because in practice they are definitions.
     BasicSymbol = addDeclaration(OriginalDecl, std::move(ID));
+    FID = SM.getFileID(findNameLoc(&OriginalDecl));
+  }
+
+  if (!BasicSymbol->CanonicalDeclaration.FileURI.empty())
+    addFileDigest(BasicSymbol->CanonicalDeclaration.FileURI, SM, FID);
 
   if (Roles & static_cast<unsigned>(index::SymbolRole::Definition))
     addDefinition(OriginalDecl, *BasicSymbol);
+
   return true;
 }
 
 bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
                                            const MacroInfo *MI,
                                            index::SymbolRoleSet Roles,
                                            SourceLocation Loc) {
   if (!Opts.CollectMacro)
if (Symbols.find(ID) != nullptr)
     return true;
 
   Symbol S;
   S.ID = std::move(ID);
   S.Name = Name->getName();
   S.IsIndexedForCodeCompletion = true;
   S.SymInfo = index::getSymbolInfoForMacro(*MI);
   std::string FileURI;
-  if (auto DeclLoc = getTokenLocation(MI->getDefinitionLoc(), SM, Opts,
-                                      PP->getLangOpts(), FileURI))
+  SourceLocation MLoc = MI->getDefinitionLoc();
+  if (auto DeclLoc =
+          getTokenLocation(MLoc, SM, Opts, PP->getLangOpts(), FileURI))
     S.CanonicalDeclaration = *DeclLoc;
 
+  if (!S.CanonicalDeclaration.FileURI.empty())
+    addFileDigest(S.CanonicalDeclaration.FileURI, SM, SM.getFileID(MLoc));
+
   CodeCompletionResult SymbolCompletion(Name);
   const auto *CCS = SymbolCompletion.CreateCodeCompletionStringForMacro(
       *PP, *CompletionAllocator, *CompletionTUInfo);
   std::string Signature;
   std::string SnippetSuffix;
   getSignature(*CCS, &Signature, &SnippetSuffix);
 
   std::string Include;
for (const IdentifierInfo *II : ReferencedMacros) {
       if (const auto *MI = PP->getMacroDefinition(II).getMacroInfo())
         if (!index::generateUSRForMacro(II->getName(), MI->getDefinitionLoc(),
                                         PP->getSourceManager(), USR))
           IncRef(SymbolID(USR));
     }
   }
   ReferencedDecls.clear();
   ReferencedMacros.clear();
+  CanonicalDecls.clear();
+  Digested.clear();
 }
 
 const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
                                               SymbolID ID) {
   auto &Ctx = ND.getASTContext();
   auto &SM = Ctx.getSourceManager();
 
   Symbol S;
void SymbolCollector::addDefinition(const NamedDecl &ND,
   std::string FileURI;
   if (auto DefLoc = getTokenLocation(findNameLoc(&ND),
                                      ND.getASTContext().getSourceManager(),
                                      Opts, ASTCtx->getLangOpts(), FileURI))
     S.Definition = *DefLoc;
   Symbols.insert(S);
 }
 
+void SymbolCollector::addFileDigest(StringRef URI, const SourceManager &SM,
+                                    FileID FID) {
+  if (FID.isInvalid() || !Digested.insert(URI).second)
+    return; // Ignore if file is invalid or already recorded.
+  bool Invalid = false;
+  StringRef Content = SM.getBufferData(FID, &Invalid);
+  if (!Invalid)
+    Symbols.addFileDigest(URI, llvm::hash_value(Content));
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolYAML.cpp

 //===--- SymbolYAML.cpp ------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolYAML.h"
 #include "Index.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
+#include <vector>
+
+namespace clangd_yaml_internal {
+struct NormalizedDigest {
+  llvm::StringRef URI;
+  size_t Digest;
+};
+
+struct NormalizedSymbolSlab {
+  std::vector<clang::clangd::Symbol> Syms;
+  std::vector<NormalizedDigest> Digests;
+};
+} // namespace clangd_yaml_internal
 
 LLVM_YAML_IS_DOCUMENT_LIST_VECTOR(clang::clangd::Symbol)
+LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Symbol)
+LLVM_YAML_IS_SEQUENCE_VECTOR(clangd_yaml_internal::NormalizedDigest)
 
 namespace llvm {
 namespace yaml {
 
 using clang::clangd::Symbol;
 using clang::clangd::SymbolID;
 using clang::clangd::SymbolLocation;
+using clang::clangd::SymbolSlab;
 using clang::index::SymbolInfo;
-using clang::index::SymbolLanguage;
 using clang::index::SymbolKind;
+using clang::index::SymbolLanguage;
 
 // Helper to (de)serialize the SymbolID. We serialize it as a hex string.
 struct NormalizedSymbolID {
   NormalizedSymbolID(IO &) {}
   NormalizedSymbolID(IO &, const SymbolID& ID) {
     llvm::raw_string_ostream OS(HexString);
     OS << ID;
   }
#define DEFINE_ENUM(name) IO.enumCase(Value, #name, SymbolKind::name)
     DEFINE_ENUM(ConversionFunction);
     DEFINE_ENUM(Parameter);
     DEFINE_ENUM(Using);
 
 #undef DEFINE_ENUM
   }
 };
 
+template <> struct MappingTraits<clangd_yaml_internal::NormalizedDigest> {
+  static void mapping(IO &IO, clangd_yaml_internal::NormalizedDigest &Digest) {
+    IO.mapRequired("URI", Digest.URI);
+    IO.mapRequired("Digest", Digest.Digest);
+  }
+};
+
+template <> struct MappingTraits<clangd_yaml_internal::NormalizedSymbolSlab> {
+  static void mapping(IO &IO,
+                      clangd_yaml_internal::NormalizedSymbolSlab &NSlab) {
+    IO.mapRequired("Symbols", NSlab.Syms);
+    IO.mapRequired("FileDigests", NSlab.Digests);
+  }
+};
+
 } // namespace yaml
 } // namespace llvm
 
 namespace clang {
 namespace clangd {
 
 SymbolSlab symbolsFromYAML(llvm::StringRef YAMLContent) {
   // Store data of pointer fields (excl. `StringRef`) like `Detail`.
   llvm::BumpPtrAllocator Arena;
   llvm::yaml::Input Yin(YAMLContent, &Arena);
-  std::vector<Symbol> S;
-  Yin >> S;
+  clangd_yaml_internal::NormalizedSymbolSlab NSlab;
+  Yin >> NSlab;
 
   SymbolSlab::Builder Syms;
-  for (auto &Sym : S)
+  for (auto &Sym : NSlab.Syms)
     Syms.insert(Sym);
+  for (auto &Digest : NSlab.Digests)
+    Syms.addFileDigest(Digest.URI, Digest.Digest);
   return std::move(Syms).build();
 }
 
 Symbol SymbolFromYAML(llvm::yaml::Input &Input, llvm::BumpPtrAllocator &Arena) {
   // We could grab Arena out of Input, but it'd be a huge hazard for callers.
   assert(Input.getContext() == &Arena);
   Symbol S;
   Input >> S;
   return S;
 }
 
 void SymbolsToYAML(const SymbolSlab& Symbols, llvm::raw_ostream &OS) {
   llvm::yaml::Output Yout(OS);
-  for (Symbol S : Symbols) // copy: Yout<< requires mutability.
-    Yout << S;
+  clangd_yaml_internal::NormalizedSymbolSlab NSlab;
+  for (auto &Sym : Symbols)
+    NSlab.Syms.push_back(Sym);
+  for (auto &Digest : Symbols.fileDigests())
+    NSlab.Digests.push_back({Digest.first, Digest.second});
+  Yout << NSlab;
 }
 
 std::string SymbolToYAML(Symbol Sym) {
   std::string Str;
   llvm::raw_string_ostream OS(Str);
   llvm::yaml::Output Yout(OS);
   Yout << Sym;
   return OS.str();
 }
 
 } // namespace clangd
 } // namespace clang

clangd/tool/ClangdMain.cpp

 // The size of global symbols should be relatively small, so that all symbols
 // can be managed in memory.
 std::unique_ptr<SymbolIndex> buildStaticIndex(llvm::StringRef YamlSymbolFile) {
   auto Buffer = llvm::MemoryBuffer::getFile(YamlSymbolFile);
   if (!Buffer) {
     llvm::errs() << "Can't open " << YamlSymbolFile << "\n";
     return nullptr;
   }
-  auto Slab = symbolsFromYAML(Buffer.get()->getBuffer());
-  SymbolSlab::Builder SymsBuilder;
-  for (auto Sym : Slab)
-    SymsBuilder.insert(Sym);
-
-  return MemIndex::build(std::move(SymsBuilder).build());
+  return MemIndex::build(symbolsFromYAML(Buffer.get()->getBuffer()));
 }
 } // 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 "
                    "parent paths of each source file."));

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
+  fileDigests(const FileDigestRequest &,
+              llvm::function_ref<void(llvm::StringRef URI, FileDigest Digest)>)
+      const override {}
+
   const std::vector<FuzzyFindRequest> allRequests() const { return Requests; }
 
 private:
   mutable std::vector<FuzzyFindRequest> Requests;
 };
 
 std::vector<FuzzyFindRequest> captureIndexRequests(llvm::StringRef Code) {
   clangd::CodeCompleteOptions Opts;

unittests/clangd/FileIndexTests.cpp

 //===-- FileIndexTests.cpp  ---------------------------*- C++ -*-----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangdUnit.h"
 #include "TestFS.h"
 #include "TestTU.h"
 #include "index/FileIndex.h"
+#include "index/Index.h"
+#include "index/MemIndex.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PCHContainerOperations.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/Hashing.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::UnorderedElementsAre;
 
 namespace clang {
 namespace clangd {
 

 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::vector<std::string>
-getSymbolNames(const std::vector<const Symbol *> &Symbols) {
+getSymbolNames(const MemIndex::SymbolSlabView &Symbols) {
   std::vector<std::string> Names;
-  for (const Symbol *Sym : Symbols)
+  for (const Symbol *Sym : Symbols.Pointers)
     Names.push_back(Sym->Name);
   return Names;
 }
 
 TEST(FileSymbolsTest, UpdateAndGet) {
   FileSymbols FS;
   EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
 
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, DropSymbolFromIndexedFileWithSameDigest) {
+  StringRef URI = "unittest:///foo.h";
+  StringRef Header = "namespace ns { class Foo {}; }";
+
+  SymbolSlab::Builder WithSameDigest;
+  WithSameDigest.addFileDigest(URI, llvm::hash_value(Header));
+  auto MemIdx = MemIndex::build(std::move(WithSameDigest).build());
+
+  FileIndex M(/*URISchemes=*/{"unittest"}, MemIdx.get());
+  update(M, "foo", Header);
+  FuzzyFindRequest Req;
+  Req.Query = "";
+  Req.Scopes = {"ns::"};
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre());
+}
+
+TEST(FileIndexTest, NoDropSymbolFromFileWithDifferentDigest) {
+  StringRef URI = "unittest:///foo.h";
+  StringRef Header = "namespace ns { class Foo {}; }";
+
+  SymbolSlab::Builder WithDifferentDigest;
+  WithDifferentDigest.addFileDigest(URI, llvm::hash_value(Header) + 1);
+  auto MemIdx = MemIndex::build(std::move(WithDifferentDigest).build());
+
+  FileIndex M(/*URISchemes=*/{"unittest"}, MemIdx.get());
+  update(M, "foo", Header);
+  FuzzyFindRequest Req;
+  Req.Query = "";
+  Req.Scopes = {"ns::"};
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::Foo"));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/IndexTests.cpp

TEST(SymbolSlab, FindAndIterate) {
   EXPECT_THAT(S, UnorderedElementsAre(Named("X"), Named("Y"), Named("Z")));
   EXPECT_EQ(S.end(), S.find(SymbolID("W")));
   for (const char *Sym : {"X", "Y", "Z"})
     EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym));
 }
 
 struct SlabAndPointers {
   SymbolSlab Slab;
-  std::vector<const Symbol *> Pointers;
+  MemIndex::SymbolSlabView View;
 };
 
 // Create a slab of symbols with the given qualified names as both IDs and
 // names. The life time of the slab is managed by the returned shared pointer.
 // If \p WeakSymbols is provided, it will be pointed to the managed object in
 // the returned shared pointer.
-std::shared_ptr<std::vector<const Symbol *>>
+std::shared_ptr<MemIndex::SymbolSlabView>
 generateSymbols(std::vector<std::string> QualifiedNames,
                 std::weak_ptr<SlabAndPointers> *WeakSymbols = nullptr) {
   SymbolSlab::Builder Slab;
   for (llvm::StringRef QName : QualifiedNames)
     Slab.insert(symbol(QName));
 
   auto Storage = std::make_shared<SlabAndPointers>();
   Storage->Slab = std::move(Slab).build();
   for (const auto &Sym : Storage->Slab)
-    Storage->Pointers.push_back(&Sym);
+    Storage->View.Pointers.push_back(&Sym);
   if (WeakSymbols)
     *WeakSymbols = Storage;
-  auto *Pointers = &Storage->Pointers;
-  return {std::move(Storage), Pointers};
+  return {std::move(Storage), &Storage->View};
 }
 
 // Create a slab of symbols with IDs and names [Begin, End], otherwise identical
 // to the `generateSymbols` above.
-std::shared_ptr<std::vector<const Symbol *>>
+std::shared_ptr<MemIndex::SymbolSlabView>
 generateNumSymbols(int Begin, int End,
                    std::weak_ptr<SlabAndPointers> *WeakSymbols = nullptr) {
   std::vector<std::string> Names;
   for (int i = Begin; i <= End; i++)
     Names.push_back(std::to_string(i));
   return generateSymbols(Names, WeakSymbols);
 }
 
TEST(MemIndexTest, MemIndexSymbolsRecycled) {
   EXPECT_TRUE(Symbols.expired());
 }
 
 TEST(MemIndexTest, MemIndexDeduplicate) {
   auto Symbols = generateNumSymbols(0, 10);
 
   // Inject some duplicates and make sure we only match the same symbol once.
   auto Sym = symbol("7");
-  Symbols->push_back(&Sym);
-  Symbols->push_back(&Sym);
-  Symbols->push_back(&Sym);
+  Symbols->Pointers.push_back(&Sym);
+  Symbols->Pointers.push_back(&Sym);
+  Symbols->Pointers.push_back(&Sym);
 
   FuzzyFindRequest Req;
   Req.Query = "7";
   MemIndex I;
   I.build(std::move(Symbols));
   auto Matches = match(I, Req);
   EXPECT_EQ(Matches.size(), 1u);
 }

unittests/clangd/SymbolCollectorTests.cpp

EXPECT_THAT(Symbols,
               UnorderedElementsAre(
                   QName("nx"),
                   AllOf(QName("nx::f"), Labeled("f()"), Snippet("f()")),
                   AllOf(QName("nx::ff"), Labeled("ff(int x, double y)"),
                         Snippet("ff(${1:int x}, ${2:double y})"))));
 }
 
 TEST_F(SymbolCollectorTest, YAMLConversions) {
-  const std::string YAML1 = R"(
----
-ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF856
+  const std::string YAML = R"(---
+Symbols:         
+  - ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF856
     Name:   'Foo1'
     Scope:   'clang::'
     SymInfo:
       Kind:            Function
       Lang:            Cpp
     CanonicalDeclaration:
       FileURI:        file:///path/foo.h
       Start:
         Line: 1
         Column: 0
       End:
         Line: 1
         Column: 1
     IsIndexedForCodeCompletion:    true
     Detail:
       Documentation:    'Foo doc'
       ReturnType:    'int'
+FileDigests:     
+  - URI:             'file:///a'
+    Digest:          123
 ...
 )";
-  const std::string YAML2 = R"(
----
-ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF858
-Name:   'Foo2'
-Scope:   'clang::'
-SymInfo:
-  Kind:            Function
-  Lang:            Cpp
-CanonicalDeclaration:
-  FileURI:        file:///path/bar.h
-  Start:
-    Line: 1
-    Column: 0
-  End:
-    Line: 1
-    Column: 1
-IsIndexedForCodeCompletion:    false
-Signature:    '-sig'
-CompletionSnippetSuffix:    '-snippet'
-...
-)";
-
-  auto Symbols1 = symbolsFromYAML(YAML1);
+  auto Symbols = symbolsFromYAML(YAML);
 
-  EXPECT_THAT(Symbols1,
-              UnorderedElementsAre(AllOf(QName("clang::Foo1"), Labeled("Foo1"),
-                                         Doc("Foo doc"), ReturnType("int"),
-                                         DeclURI("file:///path/foo.h"),
-                                         ForCodeCompletion(true))));
-  auto Symbols2 = symbolsFromYAML(YAML2);
-  EXPECT_THAT(Symbols2, UnorderedElementsAre(AllOf(
-                            QName("clang::Foo2"), Labeled("Foo2-sig"),
-                            Not(HasReturnType()), DeclURI("file:///path/bar.h"),
-                            ForCodeCompletion(false))));
-
-  std::string ConcatenatedYAML;
-  {
-    llvm::raw_string_ostream OS(ConcatenatedYAML);
-    SymbolsToYAML(Symbols1, OS);
-    SymbolsToYAML(Symbols2, OS);
-  }
-  auto ConcatenatedSymbols = symbolsFromYAML(ConcatenatedYAML);
-  EXPECT_THAT(ConcatenatedSymbols,
-              UnorderedElementsAre(QName("clang::Foo1"),
-                                   QName("clang::Foo2")));
+  auto SymbolsExpected = [](const SymbolSlab &Symbols) {
+    EXPECT_THAT(Symbols,
+                UnorderedElementsAre(
+                    AllOf(QName("clang::Foo1"), Labeled("Foo1"), Doc("Foo doc"),
+                          ReturnType("int"), DeclURI("file:///path/foo.h"),
+    auto D = Symbols.fileDigests().find("file:///a");
+    assert(D != Symbols.fileDigests().end());
+    EXPECT_EQ(D->second, 123ull);
+  };
+  SymbolsExpected(Symbols);
+
+  // Convert symbols to yaml again and back.
+  std::string Yout;
+  llvm::raw_string_ostream OS(Yout);
+  SymbolsToYAML(Symbols, OS);
+  OS.flush();
+  SymbolsExpected(symbolsFromYAML(Yout));
 }
 
 TEST_F(SymbolCollectorTest, IncludeHeaderSameAsFileURI) {
   CollectorOpts.CollectIncludePath = true;
   runSymbolCollector("class Foo {};", /*Main=*/"");
   EXPECT_THAT(Symbols,
               UnorderedElementsAre(AllOf(QName("Foo"), DeclURI(TestHeaderURI),
                                          IncludeHeader(TestHeaderURI))));