[clangd] Use Builder for symbol slabs, and use sorted-vector for storage

[sammccall]

Summary

This improves a few things:

• the insert -> freeze -> read sequence is now enforced/communicated by the type system
• SymbolSlab::const_iterator iterates over symbols, not over id-symbol pairs
• we avoid permanently storing a second copy of the IDs, and the string map's hashtable

The slab size is now down to 21.8MB for the LLVM project.
Of this only 2.7MB is strings, the rest is #symbols * sizeof(Symbol).
sizeof(Symbol) is currently 96, which seems too big - I think
SymbolInfo isn't efficiently packed. That's a topic for another patch!

Also added simple API to see the memory usage/#symbols of a slab, since
it seems likely we will continue to care about this.

[sammccall]

minor doc and code layout tweaks

[ilya-biryukov]

clangd/index/Index.cpp

39 ↗

(On Diff #127918)

Should this be S.ID < I?

41 ↗

(On Diff #127918)

&& It->ID == ID?

72 ↗

(On Diff #127918)

NIT: Maybe put assignment into a separate statement?
It's not too hard to see what's going on in the current code, but this line certainly gave me a pause.

[hokein]

clangd/index/Index.cpp

76 ↗

(On Diff #127918)

use Symbols.shrink_to_fit()?

81 ↗

(On Diff #127918)

Maybe rename it to NewArena, we already have a member called Arena.

clangd/index/Index.h

174 ↗

(On Diff #127918)

worth a comment saying the value of the map is the vector index of Symbols, it took me a while to understand.

182 ↗

(On Diff #127918)

Mention the Symbols is required to be sorted.

clangd/index/SymbolCollector.h

36 ↗

(On Diff #127918)

Maybe name it SymbolBuilder to avoid confusion -- Symbols indicates its type is SymbolSlab.

[sammccall]

Thanks!

clangd/index/Index.cpp

39 ↗

(On Diff #127918)

Wow, good catch (both here and below)!
Added a test (for some reason I thought we had one for this sort of stuff)

76 ↗

(On Diff #127918)

This is only a hint, and on my system it's a no-op. I think we know enough about the lifecycle here to make forcing the shrink worth it.

clangd/index/SymbolCollector.h

36 ↗

(On Diff #127918)

Hmm, I'm not sure SymbolBuilder is a better name - it doesn't build symbols.
I'm not really seeing the association between Symbols and SymbolSlab - a SymbolSlab::Builder is also a collection of symbols.

[sammccall]

Address review comments, and update new GlobalSymbolBuilder tool for new API.

[hokein]

LGTM.

clang-tools-extra/trunk/clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

if (OptionsParser.getCompilations().getAllFiles().empty()) {
     clang::clangd::SymbolIndexActionFactory IndexAction;
     Tool.run(&IndexAction);
     llvm::outs() << SymbolToYAML(IndexAction.Collector->takeSymbols());
     return 0;
   }
 
   // Found compilation database, we iterate all TUs from database to get all
   // symbols, and then merge them into a single SymbolSlab.
-  SymbolSlab GlobalSymbols;
+  SymbolSlab::Builder GlobalSymbols;
   std::mutex SymbolMutex;
   auto AddSymbols = [&](const SymbolSlab& NewSymbols) {
     // Synchronize set accesses.
     std::unique_lock<std::mutex> LockGuard(SymbolMutex);
-    for (auto It : NewSymbols) {
+    for (auto Sym : NewSymbols) {
       // FIXME: Better handling the overlap symbols, currently we overwrite it
       // with the latest one, but we always want to good declarations (class
       // definitions, instead of forward declarations).
-      GlobalSymbols.insert(It.second);
+      GlobalSymbols.insert(Sym);
     }
   };
 
   {
     llvm::ThreadPool Pool;
     for (auto& file : OptionsParser.getCompilations().getAllFiles()) {
       Pool.async([&OptionsParser, &AddSymbols](llvm::StringRef Path) {
         ClangTool Tool(OptionsParser.getCompilations(), {Path});
         clang::clangd::SymbolIndexActionFactory IndexAction;
         Tool.run(&IndexAction);
         AddSymbols(IndexAction.Collector->takeSymbols());
       }, file);
     }
   }
 
-  llvm::outs() << SymbolToYAML(GlobalSymbols);
+  llvm::outs() << SymbolToYAML(std::move(GlobalSymbols).build());
   return 0;
 }

clang-tools-extra/trunk/clangd/index/FileIndex.cpp

std::shared_ptr<std::vector<const Symbol *>> FileSymbols::allSymbols() {
   };
   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.second);
+        Snap->Pointers.push_back(&Iter);
     }
   }
   auto *Pointers = &Snap->Pointers;
   // Use aliasing constructor to keep the snapshot alive along with the
   // pointers.
   return {std::move(Snap), Pointers};
 }
 

clang-tools-extra/trunk/clangd/index/Index.h

 //===--- Symbol.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 "../Context.h"
 #include "clang/Index/IndexSymbol.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringExtras.h"
-#include "llvm/ADT/StringSet.h"
 #include <array>
 #include <string>
 
 namespace clang {
 namespace clangd {
 
 struct SymbolLocation {
   // The absolute path of the source file where a symbol occurs.

 class SymbolID {
 public:
   SymbolID() = default;
   SymbolID(llvm::StringRef USR);
 
   bool operator==(const SymbolID &Sym) const {
     return HashValue == Sym.HashValue;
   }
+  bool operator<(const SymbolID &Sym) const {
+    return HashValue < Sym.HashValue;
+  }
 
 private:
   friend llvm::hash_code hash_value(const SymbolID &ID) {
     // We already have a good hash, just return the first bytes.
     static_assert(sizeof(size_t) <= 20, "size_t longer than SHA1!");
     return *reinterpret_cast<const size_t *>(ID.HashValue.data());
   }
   friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                        const SymbolID &ID);
   friend void operator>>(llvm::StringRef Str, SymbolID &ID);
 
   std::array<uint8_t, 20> HashValue;
 };
 
 // Write SymbolID into the given stream. SymbolID is encoded as a 40-bytes
 // hex string.
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolID &ID);
 
 // Construct SymbolID from a hex string.
 // The HexStr is required to be a 40-bytes hex string, which is encoded from the
 // "<<" operator.
 void operator>>(llvm::StringRef HexStr, SymbolID &ID);
 
+} // namespace clangd
+} // namespace clang
+namespace llvm {
+// Support SymbolIDs as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::SymbolID> {
+  static inline clang::clangd::SymbolID getEmptyKey() {
+    static clang::clangd::SymbolID EmptyKey("EMPTYKEY");
+    return EmptyKey;
+  }
+  static inline clang::clangd::SymbolID getTombstoneKey() {
+    static clang::clangd::SymbolID TombstoneKey("TOMBSTONEKEY");
+    return TombstoneKey;
+  }
+  static unsigned getHashValue(const clang::clangd::SymbolID &Sym) {
+    return hash_value(Sym);
+  }
+  static bool isEqual(const clang::clangd::SymbolID &LHS,
+                      const clang::clangd::SymbolID &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+namespace clang {
+namespace clangd {
+
 // The class presents a C++ symbol, e.g. class, function.
 //
 // WARNING: Symbols do not own much of their underlying data - typically strings
 // are owned by a SymbolSlab. They should be treated as non-owning references.
 // Copies are shallow.
 // When adding new unowned data fields to Symbol, remember to update
-// SymbolSlab::insert to copy them to the slab's storage.
+// SymbolSlab::Builder in Index.cpp to copy them to the slab's storage.
 struct Symbol {
   // The ID of the symbol.
   SymbolID ID;
   // The symbol information, like symbol kind.
   index::SymbolInfo SymInfo;
   // The unqualified name of the symbol, e.g. "bar" (for "n1::n2::bar").
   llvm::StringRef Name;
   // The scope (e.g. namespace) of the symbol, e.g. "n1::n2" (for
struct Symbol {
   SymbolLocation CanonicalDeclaration;
 
   // FIXME: add definition location of the symbol.
   // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
   // FIXME: add code completion information.
 };
 
-// A symbol container that stores a set of symbols. The container will maintain
-// the lifetime of the symbols.
+// 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 = llvm::DenseMap<SymbolID, Symbol>::const_iterator;
+  using const_iterator = std::vector<Symbol>::const_iterator;
 
   SymbolSlab() = default;
 
   const_iterator begin() const;
   const_iterator end() const;
   const_iterator find(const SymbolID &SymID) const;
 
-  // Once called, no more symbols would be added to the SymbolSlab. This
-  // operation is irreversible.
-  void freeze();
+  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);
+  }
 
-  // Adds the symbol to this slab.
+  // 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);
 
-private:
-  // Replaces S with a reference to the same string, owned by this slab.
-  void intern(llvm::StringRef &S) {
-    S = S.empty() ? llvm::StringRef() : Strings.insert(S).first->getKey();
+     // 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];
      }
 
-  bool Frozen = false;
+     // Consumes the builder to finalize the slab.
+     SymbolSlab build() &&;
 
-  // Intern table for strings. Not StringPool as we don't refcount, just insert.
-  // We use BumpPtrAllocator to avoid lots of tiny allocations for nodes.
-  llvm::StringSet<llvm::BumpPtrAllocator> Strings;
-  llvm::DenseMap<SymbolID, Symbol> Symbols;
+   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;
+  };
+
+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.
 };
 
 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"
public:
 
   // FIXME: add interfaces for more index use cases:
   //  - Symbol getSymbolInfo(SymbolID);
   //  - getAllOccurrences(SymbolID);
 };
 
 } // namespace clangd
 } // namespace clang
-
-namespace llvm {
-
-template <> struct DenseMapInfo<clang::clangd::SymbolID> {
-  static inline clang::clangd::SymbolID getEmptyKey() {
-    static clang::clangd::SymbolID EmptyKey("EMPTYKEY");
-    return EmptyKey;
-  }
-  static inline clang::clangd::SymbolID getTombstoneKey() {
-    static clang::clangd::SymbolID TombstoneKey("TOMBSTONEKEY");
-    return TombstoneKey;
-  }
-  static unsigned getHashValue(const clang::clangd::SymbolID &Sym) {
-    return hash_value(Sym);
-  }
-  static bool isEqual(const clang::clangd::SymbolID &LHS,
-                      const clang::clangd::SymbolID &RHS) {
-    return LHS == RHS;
-  }
-};
-
-} // namespace llvm
-
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clang-tools-extra/trunk/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/StringExtras.h"
 #include "llvm/Support/SHA1.h"
 
 namespace clang {
 namespace clangd {
+using namespace llvm;
 
-SymbolID::SymbolID(llvm::StringRef USR)
-    : HashValue(llvm::SHA1::hash(arrayRefFromStringRef(USR))) {}
+SymbolID::SymbolID(StringRef USR)
+    : HashValue(SHA1::hash(arrayRefFromStringRef(USR))) {}
 
-llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolID &ID) {
-  OS << toHex(llvm::toStringRef(ID.HashValue));
+raw_ostream &operator<<(raw_ostream &OS, const SymbolID &ID) {
+  OS << toHex(toStringRef(ID.HashValue));
   return OS;
 }
 
-void operator>>(llvm::StringRef Str, SymbolID &ID) {
+void operator>>(StringRef Str, SymbolID &ID) {
   std::string HexString = fromHex(Str);
   assert(HexString.size() == ID.HashValue.size());
   std::copy(HexString.begin(), HexString.end(), ID.HashValue.begin());
 }
 
 SymbolSlab::const_iterator SymbolSlab::begin() const { return Symbols.begin(); }
 
 SymbolSlab::const_iterator SymbolSlab::end() const { return Symbols.end(); }
 
-SymbolSlab::const_iterator SymbolSlab::find(const SymbolID &SymID) const {
-  return Symbols.find(SymID);
+SymbolSlab::const_iterator SymbolSlab::find(const SymbolID &ID) const {
+  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();
 }
 
-void SymbolSlab::freeze() { Frozen = true; }
+// 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.
+      char *Data = Arena.Allocate<char>(V.size());
+      memcpy(Data, V.data(), V.size());
+      *R.first = StringRef(Data, V.size());
+    }
+    V = *R.first;
+  };
+
+  // We need to copy every StringRef field onto the arena.
+  Intern(S.Name);
+  Intern(S.Scope);
+  Intern(S.CanonicalDeclaration.FilePath);
+}
+
+void SymbolSlab::Builder::insert(const Symbol &S) {
+  auto R = SymbolIndex.try_emplace(S.ID, Symbols.size());
+  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::insert(const Symbol &S) {
-  assert(!Frozen && "Can't insert a symbol after the slab has been frozen!");
-  auto ItInserted = Symbols.try_emplace(S.ID, S);
-  if (!ItInserted.second)
-    return;
-  auto &Sym = ItInserted.first->second;
-
-  // We inserted a new symbol, so copy the underlying data.
-  intern(Sym.Name);
-  intern(Sym.Scope);
-  intern(Sym.CanonicalDeclaration.FilePath);
+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));
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/SymbolCollector.h

public:
   SymbolCollector() = default;
 
   bool
   handleDeclOccurence(const Decl *D, index::SymbolRoleSet Roles,
                       ArrayRef<index::SymbolRelation> Relations, FileID FID,
                       unsigned Offset,
                       index::IndexDataConsumer::ASTNodeInfo ASTNode) override;
 
-  void finish() override;
-
-  SymbolSlab takeSymbols() { return std::move(Symbols); }
+  SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
 
 private:
   // All Symbols collected from the AST.
-  SymbolSlab Symbols;
+  SymbolSlab::Builder Symbols;
 };
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/SymbolCollector.cpp

if (!ND->hasExternalFormalLinkage() || ND->isInAnonymousNamespace())
       return true;
 
     llvm::SmallVector<char, 128> Buff;
     if (index::generateUSRForDecl(ND, Buff))
       return true;
 
     std::string USR(Buff.data(), Buff.size());
     auto ID = SymbolID(USR);
-    if (Symbols.find(ID) != Symbols.end())
+    if (Symbols.find(ID) != nullptr)
       return true;
 
     auto &SM = ND->getASTContext().getSourceManager();
     std::string FilePath =
         makeAbsolutePath(SM, SM.getFilename(D->getLocation()));
     SymbolLocation Location = {FilePath, SM.getFileOffset(D->getLocStart()),
                                SM.getFileOffset(D->getLocEnd())};
     std::string QName = ND->getQualifiedNameAsString();
     auto ScopeAndName = splitQualifiedName(QName);
 
     Symbol S;
     S.ID = std::move(ID);
     S.Scope = ScopeAndName.first;
     S.Name = ScopeAndName.second;
     S.SymInfo = index::getSymbolInfo(D);
     S.CanonicalDeclaration = Location;
     Symbols.insert(S);
   }
 
   return true;
 }
 
-void SymbolCollector::finish() { Symbols.freeze(); }
-
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/SymbolYAML.cpp

 
 namespace clang {
 namespace clangd {
 
 SymbolSlab SymbolFromYAML(llvm::StringRef YAMLContent) {
   std::vector<Symbol> S;
   llvm::yaml::Input Yin(YAMLContent);
   Yin >> S;
-  SymbolSlab Syms;
+  SymbolSlab::Builder Syms;
   for (auto& Sym : S)
-    Syms.insert(std::move(Sym));
-  return Syms;
+    Syms.insert(Sym);
+  return std::move(Syms).build();
 }
 
 std::string SymbolToYAML(const SymbolSlab& Symbols) {
   std::string Str;
   llvm::raw_string_ostream OS(Str);
   llvm::yaml::Output Yout(OS);
-  for (auto &Pair : Symbols) {
-    Symbol MutableSymbol = Pair.second;
-    Yout<< MutableSymbol;
-  }
+  for (Symbol S : Symbols) // copy: Yout<< requires mutability.
+    Yout<< S;
   return OS.str();
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp

 std::unique_ptr<SymbolIndex> simpleIndexFromSymbols(
     std::vector<std::pair<std::string, index::SymbolKind>> Symbols) {
   auto I = llvm::make_unique<MemIndex>();
   struct Snapshot {
     SymbolSlab Slab;
     std::vector<const Symbol *> Pointers;
   };
   auto Snap = std::make_shared<Snapshot>();
+  SymbolSlab::Builder Slab;
   for (const auto &Pair : Symbols) {
     Symbol Sym;
     Sym.ID = SymbolID(Pair.first);
     llvm::StringRef QName = Pair.first;
     size_t Pos = QName.rfind("::");
     if (Pos == llvm::StringRef::npos) {
       Sym.Name = QName;
       Sym.Scope = "";
     } else {
       Sym.Name = QName.substr(Pos + 2);
       Sym.Scope = QName.substr(0, Pos);
     }
     Sym.SymInfo.Kind = Pair.second;
-    Snap->Slab.insert(std::move(Sym));
+    Slab.insert(Sym);
   }
+  Snap->Slab = std::move(Slab).build();
   for (auto &Iter : Snap->Slab)
-    Snap->Pointers.push_back(&Iter.second);
+    Snap->Pointers.push_back(&Iter);
   auto S = std::shared_ptr<std::vector<const Symbol *>>(std::move(Snap),
                                                         &Snap->Pointers);
   I->build(std::move(S));
   return std::move(I);
 }
 
 TEST(CompletionTest, NoIndex) {
   clangd::CodeCompleteOptions Opts;

clang-tools-extra/trunk/unittests/clangd/FileIndexTests.cpp

 
 Symbol symbol(llvm::StringRef ID) {
   Symbol Sym;
   Sym.ID = SymbolID(ID);
   Sym.Name = ID;
   return Sym;
 }
 
-void addNumSymbolsToSlab(int Begin, int End, SymbolSlab *Slab) {
+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)));
+    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) {
   std::vector<std::string> Names;
   for (const Symbol *Sym : Symbols)
     Names.push_back(Sym->Name);
   return Names;
 }
 
 TEST(FileSymbolsTest, UpdateAndGet) {
   FileSymbols FS;
   EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
 
-  auto Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(1, 3, Slab.get());
-
-  FS.update("f1", std::move(Slab));
-
+  FS.update("f1", numSlab(1, 3));
   EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
               UnorderedElementsAre("1", "2", "3"));
 }
 
 TEST(FileSymbolsTest, Overlap) {
   FileSymbols FS;
-
-  auto Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(1, 3, Slab.get());
-
-  FS.update("f1", std::move(Slab));
-
-  Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(3, 5, Slab.get());
-
-  FS.update("f2", std::move(Slab));
-
+  FS.update("f1", numSlab(1, 3));
+  FS.update("f2", numSlab(3, 5));
   EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
               UnorderedElementsAre("1", "2", "3", "3", "4", "5"));
 }
 
 TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
   FileSymbols FS;
 
-  auto Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(1, 3, Slab.get());
-
-  FS.update("f1", std::move(Slab));
+  FS.update("f1", numSlab(1, 3));
 
   auto Symbols = FS.allSymbols();
   EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
 
   FS.update("f1", nullptr);
   EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
-
   EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
 }
 
 std::vector<std::string> match(const SymbolIndex &I,
                                const FuzzyFindRequest &Req) {
   std::vector<std::string> Matches;
   auto Ctx = Context::empty();
   I.fuzzyFind(Ctx, Req, [&](const Symbol &Sym) {

clang-tools-extra/trunk/unittests/clangd/IndexTests.cpp

 //===-- IndexTests.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/Index.h"
 #include "index/MemIndex.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::UnorderedElementsAre;
+using testing::Pointee;
 
 namespace clang {
 namespace clangd {
-
 namespace {
 
 Symbol symbol(llvm::StringRef QName) {
   Symbol Sym;
   Sym.ID = SymbolID(QName.str());
   size_t Pos = QName.rfind("::");
   if (Pos == llvm::StringRef::npos) {
     Sym.Name = QName;
     Sym.Scope = "";
   } else {
     Sym.Name = QName.substr(Pos + 2);
     Sym.Scope = QName.substr(0, Pos);
   }
   return Sym;
 }
 
+MATCHER_P(Named, N, "") { return arg.Name == N; }
+
+TEST(SymbolSlab, FindAndIterate) {
+  SymbolSlab::Builder B;
+  B.insert(symbol("Z"));
+  B.insert(symbol("Y"));
+  B.insert(symbol("X"));
+  EXPECT_EQ(nullptr, B.find(SymbolID("W")));
+  for (const char *Sym : {"X", "Y", "Z"})
+    EXPECT_THAT(B.find(SymbolID(Sym)), Pointee(Named(Sym)));
+
+  SymbolSlab S = std::move(B).build();
+  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;
 };
 
 // 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 *>>
 generateSymbols(std::vector<std::string> QualifiedNames,
                 std::weak_ptr<SlabAndPointers> *WeakSymbols = nullptr) {
-  auto Slab = std::make_shared<SlabAndPointers>();
-  if (WeakSymbols)
-    *WeakSymbols = Slab;
-
+  SymbolSlab::Builder Slab;
   for (llvm::StringRef QName : QualifiedNames)
-    Slab->Slab.insert(symbol(QName));
+    Slab.insert(symbol(QName));
 
-  for (const auto &Sym : Slab->Slab)
-    Slab->Pointers.push_back(&Sym.second);
-
-  auto *Pointers = &Slab->Pointers;
-  return {std::move(Slab), Pointers};
+  auto Storage = std::make_shared<SlabAndPointers>();
+  Storage->Slab = std::move(Slab).build();
+  for (const auto &Sym : Storage->Slab)
+    Storage->Pointers.push_back(&Sym);
+  if (WeakSymbols)
+    *WeakSymbols = Storage;
+  auto *Pointers = &Storage->Pointers;
+  return {std::move(Storage), Pointers};
 }
 
 // Create a slab of symbols with IDs and names [Begin, End], otherwise identical
 // to the `generateSymbols` above.
 std::shared_ptr<std::vector<const Symbol *>>
 generateNumSymbols(int Begin, int End,
                    std::weak_ptr<SlabAndPointers> *WeakSymbols = nullptr) {
   std::vector<std::string> Names;

clang-tools-extra/trunk/unittests/clangd/SymbolCollectorTests.cpp

 #include <string>
 
 using testing::Eq;
 using testing::Field;
 using testing::UnorderedElementsAre;
 
 // GMock helpers for matching Symbol.
 MATCHER_P(QName, Name, "") {
-  return (arg.second.Scope + (arg.second.Scope.empty() ? "" : "::") +
-          arg.second.Name).str() == Name;
+  return (arg.Scope + (arg.Scope.empty() ? "" : "::") + arg.Name).str() == Name;
 }
 
 namespace clang {
 namespace clangd {
 
 namespace {
 class SymbolIndexActionFactory : public tooling::FrontendActionFactory {
 public: