[clangd] Index API and implementations for relations

[nridge]

Summary

This builds on the relations support added in D59407, D62459, and D62471 to expose relations in SymbolIndex and its implementations.

[nridge]

This isn't quite ready for a thorough review, but I have a question for now: in BackgroundIndex::update, there is a step where we partition symbols and references into files.

For relations, should we include a copy in both the file containing the definition of the subject, and (if different) the file containing the definition of the object?

[kadircet]

In D62839#1528597, @nridge wrote:

For relations, should we include a copy in both the file containing the definition of the subject, and (if different) the file containing the definition of the object?

The point of sharding is to reduce duplication, so I would rather store it only in subject's definition location.

[nridge]

Fill in BackgroundIndex and Dex implementations

[nridge]

Ok, this is probably ready for a first round of review now.

I know I should add new test cases to at least DexTests and BackgroundIndexTests, I'll do this in the next version of the patch.

[kadircet]

clang-tools-extra/clangd/index/Background.cpp

293

nit: rename to SymbolIDToFile?

329

nit: braces

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

201

redundant scope

223

no need to pass RelationSlabs in here AllRelations are just value types.

247–248

I think we need to pass relationslab in here. Since we might miss relations like the following that are outside the main file:

class A {};
class B : public A {};

Would be glad if you could prove me right/wrong with a unittest as well.

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

112

We might need additional options, like limiting number of results. Could you instead accept a RelsRequest object? You can check RefsRequest for a sample

clang-tools-extra/clangd/index/MemIndex.cpp

22–23

+ Relations.bytes()

24

no need to put Relations into Data they are just values, right?

92

nit: braces

clang-tools-extra/clangd/index/MemIndex.h

29

why not just store densemap<<s,p>,arrayref<o>> ?

clang-tools-extra/clangd/index/Merge.cpp

126

avoiding deduplicates is not enough, we also wouldn't want to report stale relations coming from static index.

Could you check the logic in MergedIndex::refs, and hopefully refactor it into a class to share between these two?

clang-tools-extra/clangd/index/dex/Dex.cpp

28–30

+rels.size()

269

nit: braces

clang-tools-extra/clangd/index/dex/Dex.h

109

let's store densemap<<s,p>, arrayref<o>> here as well

[nridge]

Addressed most review comments, also added some tests

[nridge]

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

112

I called it RelationsRequest to avoid visual confusion with RefsRequest.

clang-tools-extra/clangd/index/MemIndex.h

29

I used std::vector<o> because it wasn't clear where the array would live otherwise.

clang-tools-extra/clangd/index/Merge.cpp

126

The description in MergedIndex::refs() says:

// We don't want duplicated refs from the static/dynamic indexes,
// and we can't reliably deduplicate 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.

It seems to me that the problem of "can't reliably deduplicate them because offsets may differ slightly" doesn't apply to relations, as there are no offsets involved. So, is there still a need to have additional logic here?

If so, what would the logic be -- don't return an object O1 from the static index if we've returned an object O2 from the dynamic index defined in the same file as O1? (Note that to implement this, we'd have to additionally look up each SymbolID we return in the symbol table, as we don't otherwise know what file the object is located in.)

clang-tools-extra/clangd/index/dex/Dex.cpp

28–30

Size is only the backing data size, so if we don't include the relations in the backing data, we shouldn't include Rels.size(), right?

[kadircet]

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

202

nit: braces

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

76

let's have a limit as well

112

yeah that's a good call thanks!

139

thinking about this callback, I don't think there is any user that will make use of the SymbolIDs without querying for a Symbol.

So to reduce this boilerplate let's rather move this lookup into this API(all SymbolIndex implementations provide lookup anyway so they all have a way to convert a SymbolID into a Symbol) and change the callback to accept a const Symbol& instead of a SymbolID

clang-tools-extra/clangd/index/Merge.cpp

126

yes I was referring to second part actually, but you are right we have no good way of distinguishing stale information in this case. Let's leave it as it is, but add a comment stating that we might return stale relations from static index.

clang-tools-extra/clangd/index/dex/Dex.cpp

28–30

ok, but then let's make sure we include size of the densemap in estimateMemoryUsage manually.

clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp

220

could we instead check only relation is A_CC isbaseof B_CC ?

[nridge]

Address remaining review comments

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

247–248

You are right! Fixed, and added a test to FileIndexTests.

[kadircet]

LGTM, except the batch query support.

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

94

we should have only a couple call sites to this function. Let's rather change those instead of introducing a new helper.

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

77

sorry for missing it in previous iteration. but this should also enable batch queries. let's make this one a llvm::DenseMap<SymbolID>.
And in the callback we should output both the SymbolID of the Subject and Object.

We have a network based index(internally) and it uses this batch query optimization to get rid of network latency.

111

I think the old comment is better. No need to expose internals.

clang-tools-extra/clangd/index/dex/Dex.cpp

244

could you revert these changes?

268

can you also add a span

trace::Span Tracer("Dex relations");

[nridge]

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

77

What is an example use case for a batch query? In a typical LSP editor, the user can only request a type hierarchy for one class at a time.

[kadircet]

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

77

yes, that's not really applicable to TypeHierarchy, but we are rather introducing another endpoint to an existing API(SymbolIndex), which will be used by a lot more clients later on.

The first example that comes to my mind is, fetching all overrides of a class' virtual methods for example.

[nridge]

Address latest review comments

[nridge]

clang-tools-extra/clangd/index/dex/Dex.cpp

244

Reverted. Not sure how they were introduced in the first place... rebase error perhaps.

[kadircet]

LGTM, thanks!

[hintonda]

This seems to have broken gcc 5.4 builds -- for example see http://lab.llvm.org:8011/builders/clang-cmake-armv7-lnt/builds/29/steps/build%20stage%201/logs/stdio.

I believe the following patch should fix the problem:

diff --git a/clang-tools-extra/clangd/index/FileIndex.cpp b/clang-tools-extra/clangd/index/FileIndex.cpp
index a90c51b0990..802e4c4a396 100644
--- a/clang-tools-extra/clangd/index/FileIndex.cpp
+++ b/clang-tools-extra/clangd/index/FileIndex.cpp
@@ -72,7 +72,7 @@ static SlabTuple indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
        "  relations slab: {7} relations, {8} bytes",
        FileName, IsIndexMainAST, Syms.size(), Syms.bytes(), Refs.size(),
        Refs.numRefs(), Refs.bytes(), Relations.size(), Relations.bytes());
-  return {std::move(Syms), std::move(Refs), std::move(Relations)};
+  return std::make_tuple(std::move(Syms), std::move(Refs), std::move(Relations));
 }

 SlabTuple indexMainDecls(ParsedAST &AST) {

Fixed in r363504.

[nridge]

Thanks for fixing that!

clang-tools-extra/clangd/index/Background.cpp

 /// information on IndexStorage.
 void BackgroundIndex::update(llvm::StringRef MainFile, IndexFileIn Index,
                              const llvm::StringMap<FileDigest> &DigestsSnapshot,
                              BackgroundIndexStorage *IndexStorage) {
   // Partition symbols/references into files.
   struct File {
     llvm::DenseSet<const Symbol *> Symbols;
     llvm::DenseSet<const Ref *> Refs;
+    llvm::DenseSet<const Relation *> Relations;
     FileDigest Digest;
   };
   llvm::StringMap<File> Files;
   URIToFileCache URICache(MainFile);
   for (const auto &IndexIt : *Index.Sources) {
     const auto &IGN = IndexIt.getValue();
     const auto AbsPath = URICache.resolve(IGN.URI);
     const auto DigestIt = DigestsSnapshot.find(AbsPath);
     // File has different contents.
     if (DigestIt == DigestsSnapshot.end() || DigestIt->getValue() != IGN.Digest)
       Files.try_emplace(AbsPath).first->getValue().Digest = IGN.Digest;
   }
+  // This map is used to figure out where to store relations.
+  llvm::DenseMap<SymbolID, File *> SymbolIDToFile;
   for (const auto &Sym : *Index.Symbols) {
     if (Sym.CanonicalDeclaration) {
       auto DeclPath = URICache.resolve(Sym.CanonicalDeclaration.FileURI);
       const auto FileIt = Files.find(DeclPath);
-      if (FileIt != Files.end())
+      if (FileIt != Files.end()) {
         FileIt->second.Symbols.insert(&Sym);
+        SymbolIDToFile[Sym.ID] = &FileIt->second;
+      }
     }
     // For symbols with different declaration and definition locations, we store
     // the full symbol in both the header file and the implementation file, so
     // that merging can tell the preferred symbols (from canonical headers) from
     // other symbols (e.g. forward declarations).
     if (Sym.Definition &&
         Sym.Definition.FileURI != Sym.CanonicalDeclaration.FileURI) {
       auto DefPath = URICache.resolve(Sym.Definition.FileURI);
for (const auto &R : SymRefs.second) {
       const auto FileIt = Files.find(Path);
       if (FileIt != Files.end()) {
         auto &F = FileIt->getValue();
         RefToIDs[&R] = SymRefs.first;
         F.Refs.insert(&R);
       }
     }
   }
+  for (const auto &Rel : *Index.Relations) {
+    const auto FileIt = SymbolIDToFile.find(Rel.Subject);
+    if (FileIt != SymbolIDToFile.end())
+      FileIt->second->Relations.insert(&Rel);
+  }
 
   // Build and store new slabs for each updated file.
   for (const auto &FileIt : Files) {
     llvm::StringRef Path = FileIt.getKey();
     SymbolSlab::Builder Syms;
     RefSlab::Builder Refs;
+    RelationSlab::Builder Relations;
     for (const auto *S : FileIt.second.Symbols)
       Syms.insert(*S);
     for (const auto *R : FileIt.second.Refs)
       Refs.insert(RefToIDs[R], *R);
+    for (const auto *Rel : FileIt.second.Relations)
+      Relations.insert(*Rel);
     auto SS = llvm::make_unique<SymbolSlab>(std::move(Syms).build());
     auto RS = llvm::make_unique<RefSlab>(std::move(Refs).build());
+    auto RelS = llvm::make_unique<RelationSlab>(std::move(Relations).build());
     auto IG = llvm::make_unique<IncludeGraph>(
         getSubGraph(URI::create(Path), Index.Sources.getValue()));
     // We need to store shards before updating the index, since the latter
     // consumes slabs.
     if (IndexStorage) {
       IndexFileOut Shard;
       Shard.Symbols = SS.get();
       Shard.Refs = RS.get();
+      Shard.Relations = RelS.get();
       Shard.Sources = IG.get();
 
       if (auto Error = IndexStorage->storeShard(Path, Shard))
         elog("Failed to write background-index shard for file {0}: {1}", Path,
              std::move(Error));
     }
     {
       std::lock_guard<std::mutex> Lock(DigestsMu);
       auto Hash = FileIt.second.Digest;
       // Skip if file is already up to date.
       auto DigestIt = IndexedFileDigests.try_emplace(Path);
       if (!DigestIt.second && DigestIt.first->second == Hash)
         continue;
       DigestIt.first->second = Hash;
       // This can override a newer version that is added in another thread, if
       // this thread sees the older version but finishes later. This should be
       // rare in practice.
-      IndexedSymbols.update(Path, std::move(SS), std::move(RS),
+      IndexedSymbols.update(Path, std::move(SS), std::move(RS), std::move(RelS),
                             Path == MainFile);
     }
   }
 }
 
 void BackgroundIndex::buildIndex() {
   assert(BuildIndexPeriodMs > 0);
   while (true) {
return llvm::createStringError(llvm::inconvertibleErrorCode(),
                                    "Couldn't build compiler instance");
 
   SymbolCollector::Options IndexOpts;
   IndexOpts.FileFilter = createFileFilter(DigestsSnapshot);
   IndexFileIn Index;
   auto Action = createStaticIndexingAction(
       IndexOpts, [&](SymbolSlab S) { Index.Symbols = std::move(S); },
       [&](RefSlab R) { Index.Refs = std::move(R); },
+      [&](RelationSlab R) { Index.Relations = std::move(R); },
       [&](IncludeGraph IG) { Index.Sources = std::move(IG); });
 
   // We're going to run clang here, and it could potentially crash.
   // We could use CrashRecoveryContext to try to make indexing crashes nonfatal,
   // but the leaky "recovery" is pretty scary too in a long-running process.
   // If crashes are a real problem, maybe we should fork a child process.
 
   const FrontendInputFile &Input = Clang->getFrontendOpts().Inputs.front();
// Load shard information into background-index.
     for (const ShardInfo &SI : IntermediateSymbols) {
       auto SS =
           SI.Shard->Symbols
               ? llvm::make_unique<SymbolSlab>(std::move(*SI.Shard->Symbols))
               : nullptr;
       auto RS = SI.Shard->Refs
                     ? llvm::make_unique<RefSlab>(std::move(*SI.Shard->Refs))
                     : nullptr;
+      auto RelS =
+          SI.Shard->Relations
+              ? llvm::make_unique<RelationSlab>(std::move(*SI.Shard->Relations))
+              : nullptr;
       IndexedFileDigests[SI.AbsolutePath] = SI.Digest;
       IndexedSymbols.update(SI.AbsolutePath, std::move(SS), std::move(RS),
-                            SI.CountReferences);
+                            std::move(RelS), SI.CountReferences);
     }
   }
 
   return Dependencies;
 }
 
 // Goes over each changed file and loads them from index. Returns the list of
 // TUs that had out-of-date/no shards.

clang-tools-extra/clangd/index/FileIndex.h

 /// locking when we swap or obtain references to snapshots.
 class FileSymbols {
 public:
   /// Updates all symbols and refs in a file.
   /// If either is nullptr, corresponding data for \p Path will be removed.
   /// If CountReferences is true, \p Refs will be used for counting References
   /// during merging.
   void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
-              std::unique_ptr<RefSlab> Refs, bool CountReferences);
+              std::unique_ptr<RefSlab> Refs,
+              std::unique_ptr<RelationSlab> Relations, bool CountReferences);
 
   /// The index keeps the symbols alive.
   /// Will count Symbol::References based on number of references in the main
   /// files, while building the index with DuplicateHandling::Merge option.
   std::unique_ptr<SymbolIndex>
   buildIndex(IndexType,
              DuplicateHandling DuplicateHandle = DuplicateHandling::PickOne);
 
 private:
   struct RefSlabAndCountReferences {
     std::shared_ptr<RefSlab> Slab;
     bool CountReferences = false;
   };
   mutable std::mutex Mutex;
 
   /// 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<RefSlabAndCountReferences> FileToRefs;
+  /// Stores the latest relation snapshots for all active files.
+  llvm::StringMap<std::shared_ptr<RelationSlab>> FileToRelations;
 };
 
 /// This manages symbols from files and an in-memory index on all symbols.
 /// FIXME: Expose an interface to remove files that are closed.
 class FileIndex : public MergedIndex {
 public:
   FileIndex(bool UseDex = true);
 
private:
   // Mostly contains:
   //  - 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).
   FileSymbols MainFileSymbols;
   SwapIndex MainFileIndex;
 };
 
+using SlabTuple = std::tuple<SymbolSlab, RefSlab, RelationSlab>;
+
 /// Retrieves symbols and refs of local top level decls in \p AST (i.e.
 /// `AST.getLocalTopLevelDecls()`).
 /// Exposed to assist in unit tests.
-std::pair<SymbolSlab, RefSlab> indexMainDecls(ParsedAST &AST);
+SlabTuple indexMainDecls(ParsedAST &AST);
 
 /// Idex declarations from \p AST and macros from \p PP that are declared in
 /// included headers.
 SymbolSlab indexHeaderSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
                               const CanonicalIncludes &Includes);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H

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

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include <memory>
 
 namespace clang {
 namespace clangd {
 
-static std::pair<SymbolSlab, RefSlab>
-indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
+static SlabTuple indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
                               llvm::ArrayRef<Decl *> DeclsToIndex,
-             const CanonicalIncludes &Includes, bool IsIndexMainAST) {
+                              const CanonicalIncludes &Includes,
+                              bool IsIndexMainAST) {
   SymbolCollector::Options CollectorOpts;
   CollectorOpts.CollectIncludePath = true;
   CollectorOpts.Includes = &Includes;
   CollectorOpts.CountReferences = false;
   CollectorOpts.Origin = SymbolOrigin::Dynamic;
 
   index::IndexingOptions IndexOpts;
   // We only need declarations, because we don't count references.
static SlabTuple indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
   index::indexTopLevelDecls(AST, *PP, 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 Refs = Collector.takeRefs();
+  auto Relations = Collector.takeRelations();
   vlog("index AST for {0} (main={1}): \n"
        "  symbol slab: {2} symbols, {3} bytes\n"
-       "  ref slab: {4} symbols, {5} refs, {6} bytes",
+       "  ref slab: {4} symbols, {5} refs, {6} bytes\n"
+       "  relations slab: {7} relations, {8} bytes",
        FileName, IsIndexMainAST, Syms.size(), Syms.bytes(), Refs.size(),
-       Refs.numRefs(), Refs.bytes());
-  return {std::move(Syms), std::move(Refs)};
+       Refs.numRefs(), Refs.bytes(), Relations.size(), Relations.bytes());
+  return {std::move(Syms), std::move(Refs), std::move(Relations)};
 }
 
-std::pair<SymbolSlab, RefSlab> indexMainDecls(ParsedAST &AST) {
+SlabTuple indexMainDecls(ParsedAST &AST) {
   return indexSymbols(AST.getASTContext(), AST.getPreprocessorPtr(),
                       AST.getLocalTopLevelDecls(), AST.getCanonicalIncludes(),
                       /*IsIndexMainAST=*/true);
 }
 
 SymbolSlab indexHeaderSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
                               const CanonicalIncludes &Includes) {
   std::vector<Decl *> DeclsToIndex(
       AST.getTranslationUnitDecl()->decls().begin(),
       AST.getTranslationUnitDecl()->decls().end());
-  return indexSymbols(AST, std::move(PP), DeclsToIndex, Includes,
-                      /*IsIndexMainAST=*/false)
-      .first;
+  return std::get<0>(indexSymbols(AST, std::move(PP), DeclsToIndex, Includes,
+                                  /*IsIndexMainAST=*/false));
 }
 
 void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Symbols,
-                         std::unique_ptr<RefSlab> Refs, bool CountReferences) {
+                         std::unique_ptr<RefSlab> Refs,
+                         std::unique_ptr<RelationSlab> Relations,
+                         bool CountReferences) {
   std::lock_guard<std::mutex> Lock(Mutex);
   if (!Symbols)
     FileToSymbols.erase(Path);
   else
     FileToSymbols[Path] = std::move(Symbols);
   if (!Refs) {
     FileToRefs.erase(Path);
-    return;
-  }
+  } else {
     RefSlabAndCountReferences Item;
     Item.CountReferences = CountReferences;
     Item.Slab = std::move(Refs);
     FileToRefs[Path] = std::move(Item);
   }
+  if (!Relations)
+    FileToRelations.erase(Path);
+  else
+    FileToRelations[Path] = std::move(Relations);
+}
 
 std::unique_ptr<SymbolIndex>
 FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle) {
   std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
   std::vector<std::shared_ptr<RefSlab>> RefSlabs;
+  std::vector<std::shared_ptr<RelationSlab>> RelationSlabs;
   std::vector<RefSlab *> MainFileRefs;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto &FileAndSymbols : FileToSymbols)
       SymbolSlabs.push_back(FileAndSymbols.second);
     for (const auto &FileAndRefs : FileToRefs) {
       RefSlabs.push_back(FileAndRefs.second.Slab);
       if (FileAndRefs.second.CountReferences)
         MainFileRefs.push_back(RefSlabs.back().get());
     }
+    for (const auto &FileAndRelations : FileToRelations)
+      RelationSlabs.push_back(FileAndRelations.second);
   }
   std::vector<const Symbol *> AllSymbols;
   std::vector<Symbol> SymsStorage;
   switch (DuplicateHandle) {
   case DuplicateHandling::Merge: {
     llvm::DenseMap<SymbolID, Symbol> Merged;
     for (const auto &Slab : SymbolSlabs) {
       for (const auto &Sym : *Slab) {
for (auto &Sym : MergedRefs) {
       llvm::copy(SymRefs, back_inserter(RefsStorage));
       AllRefs.try_emplace(
           Sym.first,
           llvm::ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
                               SymRefs.size()));
     }
   }
 
+  std::vector<Relation> AllRelations;
+  for (const auto &RelationSlab : RelationSlabs) {
+    for (const auto &R : *RelationSlab) {
+      AllRelations.push_back(R);
+    }
+  }
+
   size_t StorageSize =
       RefsStorage.size() * sizeof(Ref) + SymsStorage.size() * sizeof(Symbol);
   for (const auto &Slab : SymbolSlabs)
     StorageSize += Slab->bytes();
   for (const auto &RefSlab : RefSlabs)
     StorageSize += RefSlab->bytes();
+  for (const auto &RelationSlab : RelationSlabs)
+    StorageSize += RelationSlab->bytes();
 
   // Index must keep the slabs and contiguous ranges alive.
   switch (Type) {
   case IndexType::Light:
     return llvm::make_unique<MemIndex>(
         llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
+        std::move(AllRelations),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
                         std::move(RefsStorage), std::move(SymsStorage)),
         StorageSize);
   case IndexType::Heavy:
     return llvm::make_unique<dex::Dex>(
         llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
+        std::move(AllRelations),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
                         std::move(RefsStorage), std::move(SymsStorage)),
         StorageSize);
   }
   llvm_unreachable("Unknown clangd::IndexType");
 }
 
 FileIndex::FileIndex(bool UseDex)
     : MergedIndex(&MainFileIndex, &PreambleIndex), UseDex(UseDex),
       PreambleIndex(llvm::make_unique<MemIndex>()),
       MainFileIndex(llvm::make_unique<MemIndex>()) {}
 
 void FileIndex::updatePreamble(PathRef Path, ASTContext &AST,
                                std::shared_ptr<Preprocessor> PP,
                                const CanonicalIncludes &Includes) {
   auto Symbols = indexHeaderSymbols(AST, std::move(PP), Includes);
   PreambleSymbols.update(
       Path, llvm::make_unique<SymbolSlab>(std::move(Symbols)),
-      llvm::make_unique<RefSlab>(), /*CountReferences=*/false);
+      llvm::make_unique<RefSlab>(), llvm::make_unique<RelationSlab>(),
+      /*CountReferences=*/false);
   PreambleIndex.reset(
       PreambleSymbols.buildIndex(UseDex ? IndexType::Heavy : IndexType::Light,
                                  DuplicateHandling::PickOne));
 }
 
 void FileIndex::updateMain(PathRef Path, ParsedAST &AST) {
   auto Contents = indexMainDecls(AST);
   MainFileSymbols.update(
-      Path, llvm::make_unique<SymbolSlab>(std::move(Contents.first)),
-      llvm::make_unique<RefSlab>(std::move(Contents.second)),
+      Path, llvm::make_unique<SymbolSlab>(std::move(std::get<0>(Contents))),
+      llvm::make_unique<RefSlab>(std::move(std::get<1>(Contents))),
+      llvm::make_unique<RelationSlab>(std::move(std::get<2>(Contents))),
       /*CountReferences=*/true);
   MainFileIndex.reset(
       MainFileSymbols.buildIndex(IndexType::Light, DuplicateHandling::PickOne));
 }
 
 } // namespace clangd
 } // namespace clang

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

struct RefsRequest {
   llvm::DenseSet<SymbolID> IDs;
   RefKind Filter = RefKind::All;
   /// If set, limit the number of refers returned from the index. The index may
   /// choose to return less than this, e.g. it tries to avoid returning stale
   /// results.
   llvm::Optional<uint32_t> Limit;
 };
 
+struct RelationsRequest {
+  SymbolID Subject;
+  index::SymbolRole Predicate;
+};
+
 /// 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.
public:
   /// 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 refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const = 0;
 
+  /// Finds all symbols 'Object' such that (Req.Subject, Req.Predicate, Object)
+  /// form a relation stored in the index and applies \p Callback on each
+  /// result.
+  virtual void
+  relations(const RelationsRequest &Req,
+            llvm::function_ref<void(const SymbolID &)> Callback) const = 0;
+
   /// Returns estimated size of index (in bytes).
   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 refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
+  void relations(const RelationsRequest &,
+                 llvm::function_ref<void(const SymbolID &)>) 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

clang-tools-extra/clangd/index/Index.cpp

 void SwapIndex::lookup(const LookupRequest &R,
                        llvm::function_ref<void(const Symbol &)> CB) const {
   return snapshot()->lookup(R, CB);
 }
 void SwapIndex::refs(const RefsRequest &R,
                      llvm::function_ref<void(const Ref &)> CB) const {
   return snapshot()->refs(R, CB);
 }
+void SwapIndex::relations(const RelationsRequest &R,
+                          llvm::function_ref<void(const SymbolID &)> CB) const {
+  return snapshot()->relations(R, CB);
+}
+
 size_t SwapIndex::estimateMemoryUsage() const {
   return snapshot()->estimateMemoryUsage();
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/IndexAction.h

 //   - include paths are always collected, and canonicalized appropriately
 //   - references are always counted
 //   - all references are collected (if RefsCallback is non-null)
 //   - the symbol origin is set to Static if not specified by caller
 std::unique_ptr<FrontendAction> createStaticIndexingAction(
     SymbolCollector::Options Opts,
     std::function<void(SymbolSlab)> SymbolsCallback,
     std::function<void(RefSlab)> RefsCallback,
+    std::function<void(RelationSlab)> RelationsCallback,
     std::function<void(IncludeGraph)> IncludeGraphCallback);
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/index/IndexAction.cpp

 // Wraps the index action and reports index data after each translation unit.
 class IndexAction : public WrapperFrontendAction {
 public:
   IndexAction(std::shared_ptr<SymbolCollector> C,
               std::unique_ptr<CanonicalIncludes> Includes,
               const index::IndexingOptions &Opts,
               std::function<void(SymbolSlab)> SymbolsCallback,
               std::function<void(RefSlab)> RefsCallback,
+              std::function<void(RelationSlab)> RelationsCallback,
               std::function<void(IncludeGraph)> IncludeGraphCallback)
       : WrapperFrontendAction(index::createIndexingAction(C, Opts, nullptr)),
         SymbolsCallback(SymbolsCallback), RefsCallback(RefsCallback),
+        RelationsCallback(RelationsCallback),
         IncludeGraphCallback(IncludeGraphCallback), Collector(C),
         Includes(std::move(Includes)),
         PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {}
 
   std::unique_ptr<ASTConsumer>
   CreateASTConsumer(CompilerInstance &CI, llvm::StringRef InFile) override {
     CI.getPreprocessor().addCommentHandler(PragmaHandler.get());
     if (IncludeGraphCallback != nullptr)
void EndSourceFileAction() override {
     if (CI.hasDiagnostics() &&
         CI.getDiagnostics().hasUncompilableErrorOccurred()) {
       llvm::errs() << "Skipping TU due to uncompilable errors\n";
       return;
     }
     SymbolsCallback(Collector->takeSymbols());
     if (RefsCallback != nullptr)
       RefsCallback(Collector->takeRefs());
+    if (RelationsCallback != nullptr)
+      RelationsCallback(Collector->takeRelations());
     if (IncludeGraphCallback != nullptr) {
 #ifndef NDEBUG
       // This checks if all nodes are initialized.
       for (const auto &Node : IG)
         assert(Node.getKeyData() == Node.getValue().URI.data());
 #endif
       IncludeGraphCallback(std::move(IG));
     }
   }
 
 private:
   std::function<void(SymbolSlab)> SymbolsCallback;
   std::function<void(RefSlab)> RefsCallback;
+  std::function<void(RelationSlab)> RelationsCallback;
   std::function<void(IncludeGraph)> IncludeGraphCallback;
   std::shared_ptr<SymbolCollector> Collector;
   std::unique_ptr<CanonicalIncludes> Includes;
   std::unique_ptr<CommentHandler> PragmaHandler;
   IncludeGraph IG;
 };
 
 } // namespace
 
 std::unique_ptr<FrontendAction> createStaticIndexingAction(
     SymbolCollector::Options Opts,
     std::function<void(SymbolSlab)> SymbolsCallback,
     std::function<void(RefSlab)> RefsCallback,
+    std::function<void(RelationSlab)> RelationsCallback,
     std::function<void(IncludeGraph)> IncludeGraphCallback) {
   index::IndexingOptions IndexOpts;
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
   Opts.CollectIncludePath = true;
   if (Opts.Origin == SymbolOrigin::Unknown)
     Opts.Origin = SymbolOrigin::Static;
   Opts.StoreAllDocumentation = false;
   if (RefsCallback != nullptr) {
     Opts.RefFilter = RefKind::All;
     Opts.RefsInHeaders = true;
   }
   auto Includes = llvm::make_unique<CanonicalIncludes>();
   addSystemHeadersMapping(Includes.get());
   Opts.Includes = Includes.get();
   return llvm::make_unique<IndexAction>(
       std::make_shared<SymbolCollector>(std::move(Opts)), std::move(Includes),
-      IndexOpts, SymbolsCallback, RefsCallback, IncludeGraphCallback);
+      IndexOpts, SymbolsCallback, RefsCallback, RelationsCallback,
+      IncludeGraphCallback);
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/MemIndex.h

 namespace clang {
 namespace clangd {
 
 /// MemIndex is a naive in-memory index suitable for a small set of symbols.
 class MemIndex : public SymbolIndex {
 public:
   MemIndex() = default;
   // All symbols and refs must outlive this index.
-  template <typename SymbolRange, typename RefRange>
-  MemIndex(SymbolRange &&Symbols, RefRange &&Refs) {
+  template <typename SymbolRange, typename RefRange, typename RelationRange>
+  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations) {
     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());
+    for (const Relation &R : Relations)
+      this->Relations[std::make_pair(R.Subject, R.Predicate)].push_back(
+          R.Object);
   }
   // Symbols are owned by BackingData, Index takes ownership.
-  template <typename SymbolRange, typename RefRange, typename Payload>
-  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, Payload &&BackingData,
-           size_t BackingDataSize)
+  template <typename SymbolRange, typename RefRange, typename RelationRange,
+            typename Payload>
+  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations,
+           Payload &&BackingData, size_t BackingDataSize)
       : MemIndex(std::forward<SymbolRange>(Symbols),
-                 std::forward<RefRange>(Refs)) {
+                 std::forward<RefRange>(Refs),
+                 std::forward<RelationRange>(Relations)) {
     KeepAlive = std::shared_ptr<void>(
         std::make_shared<Payload>(std::move(BackingData)), nullptr);
     this->BackingDataSize = BackingDataSize;
   }
 
   /// Builds an index from slabs. The index takes ownership of the data.
-  static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs);
+  static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs,
+                                            RelationSlab Relations);
 
   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 refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
+  void
+  relations(const RelationsRequest &Req,
+            llvm::function_ref<void(const SymbolID &)> 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 refs, support query by IDs.
   llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
+  // A map from (subject, predicate) pair to objects.
+  llvm::DenseMap<std::pair<SymbolID, index::SymbolRole>, std::vector<SymbolID>>
+      Relations;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
   // Size of memory retained by KeepAlive.
   size_t BackingDataSize = 0;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H

clang-tools-extra/clangd/index/MemIndex.cpp

 #include "Logger.h"
 #include "Quality.h"
 #include "Trace.h"
 #include "clang/Index/IndexSymbol.h"
 
 namespace clang {
 namespace clangd {
 
-std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) {
+std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs,
+                                             RelationSlab Relations) {
   // Store Slab size before it is moved.
   const auto BackingDataSize = Slab.bytes() + Refs.bytes();
   auto Data = std::make_pair(std::move(Slab), std::move(Refs));
-  return llvm::make_unique<MemIndex>(Data.first, Data.second, std::move(Data),
-                                     BackingDataSize);
+  return llvm::make_unique<MemIndex>(Data.first, Data.second, Relations,
+                                     std::move(Data), BackingDataSize);
 }
 
 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.");
   trace::Span Tracer("MemIndex fuzzyFind");
for (const auto &O : SymRefs->second) {
       if (Remaining > 0 && static_cast<int>(Req.Filter & O.Kind)) {
         --Remaining;
         Callback(O);
       }
     }
   }
 }
 
+void MemIndex::relations(
+    const RelationsRequest &Req,
+    llvm::function_ref<void(const SymbolID &)> Callback) const {
+  auto It = Relations.find(std::make_pair(Req.Subject, Req.Predicate));
+  if (It != Relations.end()) {
+    for (const auto &Obj : It->second)
+      Callback(Obj);
+  }
+}
+
 size_t MemIndex::estimateMemoryUsage() const {
-  return Index.getMemorySize() + Refs.getMemorySize() + BackingDataSize;
+  return Index.getMemorySize() + Refs.getMemorySize() +
+         Relations.getMemorySize() + BackingDataSize;
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/Merge.h

MergedIndex(const SymbolIndex *Dynamic, const SymbolIndex *Static)
       : Dynamic(Dynamic), Static(Static) {}
 
   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 refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
+  void relations(const RelationsRequest &,
+                 llvm::function_ref<void(const SymbolID &)>) const override;
   size_t estimateMemoryUsage() const override {
     return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
   }
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MERGE_H

clang-tools-extra/clangd/index/Merge.cpp

 }
 
 void MergedIndex::refs(const RefsRequest &Req,
                        llvm::function_ref<void(const Ref &)> Callback) const {
   trace::Span Tracer("MergedIndex refs");
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   // We don't want duplicated refs from the static/dynamic indexes,
-  // and we can't reliably duplicate them because offsets may differ slightly.
+  // and we can't reliably deduplicate 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
   // 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);
     --Remaining;
   });
   if (Remaining == 0)
     return;
   // We return less than Req.Limit if static index returns more refs for dirty
   // files.
   Static->refs(Req, [&](const Ref &O) {
     if (Remaining > 0 && !DynamicIndexFileURIs.count(O.Location.FileURI)) {
       --Remaining;
       Callback(O);
     }
   });
 }
 
+void MergedIndex::relations(
+    const RelationsRequest &Req,
+    llvm::function_ref<void(const SymbolID &)> Callback) const {
+  // Return results from both indexes but avoid duplicates.
+  llvm::DenseSet<SymbolID> SeenObjects;
+  Dynamic->relations(Req, [&](const SymbolID &ObjectID) {
+    Callback(ObjectID);
+    SeenObjects.insert(ObjectID);
+  });
+  Static->relations(Req, [&](const SymbolID &ObjectID) {
+    if (!SeenObjects.count(ObjectID)) {
+      Callback(ObjectID);
+    }
+  });
+}
+
 // Returns true if \p L is (strictly) preferred to \p R (e.g. by file paths). If
 // neither is preferred, this returns false.
 bool prefer(const SymbolLocation &L, const SymbolLocation &R) {
   if (!L)
     return false;
   if (!R)
     return true;
   auto HasCodeGenSuffix = [](const SymbolLocation &Loc) {

clang-tools-extra/clangd/index/Relation.h

RelationSlab(std::vector<Relation> Relations)
       : Relations(std::move(Relations)) {}
 
   std::vector<Relation> Relations;
 };
 
 } // namespace clangd
 } // namespace clang
 
+namespace llvm {
+
+// Support index::SymbolRole as a DenseMap key for the purpose of looking up
+// relations.
+template <> struct DenseMapInfo<clang::index::SymbolRole> {
+  static inline clang::index::SymbolRole getEmptyKey() {
+    // Choose an enumerator that's not a relation.
+    return clang::index::SymbolRole::Declaration;
+  }
+
+  static inline clang::index::SymbolRole getTombstoneKey() {
+    // Choose another enumerator that's not a relation.
+    return clang::index::SymbolRole::Definition;
+  }
+
+  static unsigned getHashValue(const clang::index::SymbolRole &Key) {
+    return hash_value(Key);
+  }
+
+  static bool isEqual(const clang::index::SymbolRole &LHS,
+                      const clang::index::SymbolRole &RHS) {
+    return LHS == RHS;
+  }
+};
+
+} // namespace llvm
+
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_RELATION_H

clang-tools-extra/clangd/index/Serialization.cpp

RelationSlab Relations;
     }
   }
 
   size_t NumSym = Symbols.size();
   size_t NumRefs = Refs.numRefs();
   size_t NumRelations = Relations.size();
 
   trace::Span Tracer("BuildIndex");
-  auto Index = UseDex ? dex::Dex::build(std::move(Symbols), std::move(Refs))
-                      : MemIndex::build(std::move(Symbols), std::move(Refs));
+  auto Index = UseDex ? dex::Dex::build(std::move(Symbols), std::move(Refs),
+                                        std::move(Relations))
+                      : MemIndex::build(std::move(Symbols), std::move(Refs),
+                                        std::move(Relations));
   vlog("Loaded {0} from {1} with estimated memory usage {2} bytes\n"
        "  - number of symbols: {3}\n"
        "  - number of refs: {4}\n"
        "  - numnber of relations: {5}",
        UseDex ? "Dex" : "MemIndex", SymbolFilename,
        Index->estimateMemoryUsage(), NumSym, NumRefs, NumRelations);
   return Index;
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/index/dex/Dex.h

 // FIXME(kbobyrev): Introduce serialization and deserialization of the symbol
 // index so that it can be loaded from the disk. Since static index is not
 // changed frequently, it's safe to assume that it has to be built only once
 // (when the clangd process starts). Therefore, it can be easier to store built
 // index on disk and then load it if available.
 class Dex : public SymbolIndex {
 public:
   // All data must outlive this index.
-  template <typename SymbolRange, typename RefsRange>
-  Dex(SymbolRange &&Symbols, RefsRange &&Refs) : Corpus(0) {
+  template <typename SymbolRange, typename RefsRange, typename RelationsRange>
+  Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations)
+      : Corpus(0) {
     for (auto &&Sym : Symbols)
       this->Symbols.push_back(&Sym);
     for (auto &&Ref : Refs)
       this->Refs.try_emplace(Ref.first, Ref.second);
+    for (auto &&Rel : Relations)
+      this->Relations[std::make_pair(Rel.Subject, Rel.Predicate)].push_back(
+          Rel.Object);
     buildIndex();
   }
   // Symbols and Refs are owned by BackingData, Index takes ownership.
-  template <typename SymbolRange, typename RefsRange, typename Payload>
-  Dex(SymbolRange &&Symbols, RefsRange &&Refs, Payload &&BackingData,
-      size_t BackingDataSize)
-      : Dex(std::forward<SymbolRange>(Symbols), std::forward<RefsRange>(Refs)) {
+  template <typename SymbolRange, typename RefsRange, typename RelationsRange,
+            typename Payload>
+  Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations,
+      Payload &&BackingData, size_t BackingDataSize)
+      : Dex(std::forward<SymbolRange>(Symbols), std::forward<RefsRange>(Refs),
+            std::forward<RelationsRange>(Relations)) {
     KeepAlive = std::shared_ptr<void>(
         std::make_shared<Payload>(std::move(BackingData)), nullptr);
     this->BackingDataSize = BackingDataSize;
   }
 
   /// Builds an index from slabs. The index takes ownership of the slab.
-  static std::unique_ptr<SymbolIndex> build(SymbolSlab, RefSlab);
+  static std::unique_ptr<SymbolIndex> build(SymbolSlab, RefSlab, RelationSlab);
 
   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 refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
+  void
+  relations(const RelationsRequest &Req,
+            llvm::function_ref<void(const SymbolID &)> Callback) const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
   void buildIndex();
   std::unique_ptr<Iterator> iterator(const Token &Tok) const;
   std::unique_ptr<Iterator>
   createFileProximityIterator(llvm::ArrayRef<std::string> ProximityPaths) const;
   std::unique_ptr<Iterator>
   createTypeBoostingIterator(llvm::ArrayRef<std::string> Types) const;
 
   /// Stores symbols sorted in the descending order of symbol quality..
   std::vector<const Symbol *> Symbols;
   /// SymbolQuality[I] is the quality of Symbols[I].
   std::vector<float> SymbolQuality;
   llvm::DenseMap<SymbolID, const Symbol *> LookupTable;
   /// Inverted index is a mapping from the search token to the posting list,
   /// which contains all items which can be characterized by such search token.
   /// For example, if the search token is scope "std::", the corresponding
   /// posting list would contain all indices of symbols defined in namespace
   /// std. Inverted index is used to retrieve posting lists which are processed
   /// during the fuzzyFind process.
   llvm::DenseMap<Token, PostingList> InvertedIndex;
   dex::Corpus Corpus;
   llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
+  llvm::DenseMap<std::pair<SymbolID, index::SymbolRole>, std::vector<SymbolID>>
+      Relations;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
   // Size of memory retained by KeepAlive.
   size_t BackingDataSize = 0;
 };
 
 /// Returns Search Token for a number of parent directories of given Path.
 /// Should be used within the index build process.
 ///
 /// This function is exposed for testing only.
 std::vector<std::string> generateProximityURIs(llvm::StringRef URIPath);
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H

clang-tools-extra/clangd/index/dex/Dex.cpp

 #include "llvm/Support/ScopedPrinter.h"
 #include <algorithm>
 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
-std::unique_ptr<SymbolIndex> Dex::build(SymbolSlab Symbols, RefSlab Refs) {
+std::unique_ptr<SymbolIndex> Dex::build(SymbolSlab Symbols, RefSlab Refs,
+                                        RelationSlab Rels) {
   auto Size = Symbols.bytes() + Refs.bytes();
+  // There is no need to include "Rels" in Data because the relations are self-
+  // contained, without references into a backing store.
   auto Data = std::make_pair(std::move(Symbols), std::move(Refs));
-  return llvm::make_unique<Dex>(Data.first, Data.second, std::move(Data), Size);
+  return llvm::make_unique<Dex>(Data.first, Data.second, Rels, std::move(Data),
+                                Size);
 }
 
 namespace {
 
 // Mark symbols which are can be used for code completion.
 const Token RestrictedForCodeCompletion =
     Token(Token::Kind::Sentinel, "Restricted For Code Completion");
 
bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
   // order of cumulative score.
   for (const auto &Item : std::move(Top).items())
     Callback(*Symbols[Item.first]);
   return More;
 }
 
 void Dex::lookup(const LookupRequest &Req,
                  llvm::function_ref<void(const Symbol &)> Callback) const {
   trace::Span Tracer("Dex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = LookupTable.find(ID);
     if (I != LookupTable.end())
       Callback(*I->second);
   }
 }
 
 void Dex::refs(const RefsRequest &Req,
                llvm::function_ref<void(const Ref &)> Callback) const {
   trace::Span Tracer("Dex refs");
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   for (const auto &ID : Req.IDs)
     for (const auto &Ref : Refs.lookup(ID)) {
       if (Remaining > 0 && static_cast<int>(Req.Filter & Ref.Kind)) {
         --Remaining;
         Callback(Ref);
       }
     }
 }
 
+void Dex::relations(const RelationsRequest &Req,
+                    llvm::function_ref<void(const SymbolID &)> Callback) const {
+  auto It = Relations.find(std::make_pair(Req.Subject, Req.Predicate));
+  if (It != Relations.end()) {
+    for (const auto &Object : It->second)
+      Callback(Object);
+  }
+}
+
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
   Bytes += LookupTable.getMemorySize();
   Bytes += InvertedIndex.getMemorySize();
   for (const auto &TokenToPostingList : InvertedIndex)
     Bytes += TokenToPostingList.second.bytes();
   Bytes += Refs.getMemorySize();

clang-tools-extra/clangd/indexer/IndexerMain.cpp

return createStaticIndexingAction(
                [&](RefSlab S) {
                  std::lock_guard<std::mutex> Lock(SymbolsMu);
                  for (const auto &Sym : S) {
                    // Deduplication happens during insertion.
                    for (const auto &Ref : Sym.second)
                      Refs.insert(Sym.first, Ref);
                  }
                },
+               [&](RelationSlab S) {
+                 std::lock_guard<std::mutex> Lock(SymbolsMu);
+                 for (const auto &R : S) {
+                   Relations.insert(R);
+                 }
+               },
                /*IncludeGraphCallback=*/nullptr)
         .release();
   }
 
   // Awkward: we write the result in the destructor, because the executor
   // takes ownership so it's the easiest way to get our data back out.
   ~IndexActionFactory() {
     Result.Symbols = std::move(Symbols).build();
     Result.Refs = std::move(Refs).build();
+    Result.Relations = std::move(Relations).build();
   }
 
 private:
   IndexFileIn &Result;
   std::mutex SymbolsMu;
   SymbolSlab::Builder Symbols;
   RefSlab::Builder Refs;
+  RelationSlab::Builder Relations;
 };
 
 } // namespace
 } // namespace clangd
 } // namespace clang
 
 int main(int argc, const char **argv) {
   llvm::sys::PrintStackTraceOnErrorSignal(argv[0]);

clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp

 
 TEST_F(BackgroundIndexTest, ShardStorageTest) {
   MockFSProvider FS;
   FS.Files[testPath("root/A.h")] = R"cpp(
       void common();
       void f_b();
       class A_CC {};
       )cpp";
-  std::string A_CC = "#include \"A.h\"\nvoid g() { (void)common; }";
-  FS.Files[testPath("root/A.cc")] = A_CC;
+  std::string A_CC = "";
+  FS.Files[testPath("root/A.cc")] = R"cpp(
+      #include "A.h"
+      void g() { (void)common; }
+      class B_CC : public A_CC {};
+      )cpp";
 
   llvm::StringMap<std::string> Storage;
   size_t CacheHits = 0;
   MemoryShardStorage MSS(Storage, CacheHits);
 
   tooling::CompileCommand Cmd;
   Cmd.Filename = testPath("root/A.cc");
   Cmd.Directory = testPath("root");
TEST_F(BackgroundIndexTest, ShardStorageTest) {
   EXPECT_NE(ShardHeader, nullptr);
   EXPECT_THAT(
       *ShardHeader->Symbols,
       UnorderedElementsAre(Named("common"), Named("A_CC"),
                            AllOf(Named("f_b"), Declared(), Not(Defined()))));
   for (const auto &Ref : *ShardHeader->Refs)
     EXPECT_THAT(Ref.second,
                 UnorderedElementsAre(FileURI("unittest:///root/A.h")));
+  // The BaseOf relationship between A_CC and B_CC is stored in the file
+  // containing the definition of the subject (A_CC).
+  EXPECT_EQ(ShardHeader->Relations->size(), 1u);
 
   auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
   EXPECT_NE(ShardSource, nullptr);
-  EXPECT_THAT(*ShardSource->Symbols, UnorderedElementsAre(Named("g")));
-  EXPECT_THAT(*ShardSource->Refs, RefsAre({FileURI("unittest:///root/A.cc")}));
+  EXPECT_THAT(*ShardSource->Symbols,
+              UnorderedElementsAre(Named("g"), Named("B_CC")));
+  for (const auto &Ref : *ShardSource->Refs)
+    EXPECT_THAT(Ref.second,
+                UnorderedElementsAre(FileURI("unittest:///root/A.cc")));
+  EXPECT_EQ(ShardSource->Relations->size(), 0u);
 }
 
 TEST_F(BackgroundIndexTest, DirectIncludesTest) {
   MockFSProvider FS;
   FS.Files[testPath("root/B.h")] = "";
   FS.Files[testPath("root/A.h")] = R"cpp(
       #include "B.h"
       void common();

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

 }
 MATCHER(IsDocumented, "") { return !arg.Documentation.empty(); }
 MATCHER(Deprecated, "") { return arg.Deprecated; }
 
 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(), RefSlab());
+  return MemIndex::build(std::move(Slab).build(), RefSlab(), RelationSlab());
 }
 
 CodeCompleteResult completions(ClangdServer &Server, llvm::StringRef TestCode,
                                Position point,
                                std::vector<Symbol> IndexSymbols = {},
                                clangd::CodeCompleteOptions Opts = {}) {
   std::unique_ptr<SymbolIndex> OverrideIndex;
   if (!IndexSymbols.empty()) {
auto Results = completions(Server,
       )cpp",
                              {Sym});
   EXPECT_THAT(Results.Completions,
               ElementsAre(AllOf(Named("X"), InsertInclude("\"bar.h\""))));
   // Can be disabled via option.
   CodeCompleteOptions NoInsertion;
   NoInsertion.InsertIncludes = CodeCompleteOptions::NeverInsert;
   Results = completions(Server,
-                             R"cpp(
           int main() { ns::^ }
       )cpp",
-                             {Sym}, NoInsertion);
   EXPECT_THAT(Results.Completions,
               ElementsAre(AllOf(Named("X"), Not(InsertInclude()))));
   // Duplicate based on inclusions in preamble.
   Results = completions(Server,
                         R"cpp(
           #include "sub/bar.h"  // not shortest, so should only match resolved.
           int main() { ns::^ }
       )cpp",
public:
   }
 
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override {}
 
   void refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override {}
 
+  void relations(const RelationsRequest &,
+                 llvm::function_ref<void(const SymbolID &)>) 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 {
     std::lock_guard<std::mutex> Lock(Mut);
     auto Reqs = std::move(Requests);
     Requests = {};
completions(R"cpp(
     struct Derived : Base {
       ^
     };
   )cpp");
 }
 
 TEST(GuessCompletionPrefix, Filters) {
   for (llvm::StringRef Case : {
            "[[scope::]][[ident]]^",
            "[[]][[]]^",
            "\n[[]][[]]^",
            "[[]][[ab]]^",
            "x.[[]][[ab]]^",
            "x.[[]][[]]^",
            "[[x::]][[ab]]^",
            "[[x::]][[]]^",
            "[[::x::]][[ab]]^",
            "some text [[scope::more::]][[identif]]^ier",
            "some text [[scope::]][[mor]]^e::identifier",
            "weird case foo::[[::bar::]][[baz]]^",
        }) {
     Annotations F(Case);
     auto Offset = cantFail(positionToOffset(F.code(), F.point()));
     auto ToStringRef = [&](Range R) {
       return F.code().slice(cantFail(positionToOffset(F.code(), R.start)),
                             cantFail(positionToOffset(F.code(), R.end)));
     };
     auto WantQualifier = ToStringRef(F.ranges()[0]),
          WantName = ToStringRef(F.ranges()[1]);
auto Results = completions(
       R"cpp(
     void while_foo(int a, int b);
     void test() {
       whil^
     })cpp",
       /*IndexSymbols=*/{}, Options);
 
   // Last placeholder in code patterns should be $0 to put the cursor there.
-  EXPECT_THAT(
-      Results.Completions,
-      Contains(AllOf(Named("while"),
-                     SnippetSuffix(" (${1:condition}) {\n${0:statements}\n}"))));
+  EXPECT_THAT(Results.Completions,
+              Contains(AllOf(
+                  Named("while"),
   // However, snippets for functions must *not* end with $0.
   EXPECT_THAT(Results.Completions,
               Contains(AllOf(Named("while_foo"),
                              SnippetSuffix("(${1:int a}, ${2:int b})"))));
 }
 
 TEST(CompletionTest, WorksWithNullType) {
   auto R = completions(R"cpp(

clang-tools-extra/clangd/unittests/DexTests.cpp

EXPECT_THAT(generateProximityURIs("unittest:///a/b/c.h"),
                           "unittest:///a", "unittest:///"));
 }
 
 //===----------------------------------------------------------------------===//
 // Index tests.
 //===----------------------------------------------------------------------===//
 
 TEST(Dex, Lookup) {
-  auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(),
+                      RelationSlab());
   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(Dex, FuzzyFind) {
   auto Index =
       Dex::build(generateSymbols({"ns::ABC", "ns::BCD", "::ABC",
                                   "ns::nested::ABC", "other::ABC", "other::A"}),
-                 RefSlab());
+                 RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "ABC";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("ns::ABC"));
   Req.Scopes = {"ns::", "ns::nested::"};
   EXPECT_THAT(match(*Index, Req),
               UnorderedElementsAre("ns::ABC", "ns::nested::ABC"));
   Req.Query = "A";
   Req.Scopes = {"other::"};
   EXPECT_THAT(match(*Index, Req),
               UnorderedElementsAre("other::A", "other::ABC"));
   Req.Query = "";
   Req.Scopes = {};
   Req.AnyScope = true;
   EXPECT_THAT(match(*Index, Req),
               UnorderedElementsAre("ns::ABC", "ns::BCD", "::ABC",
                                    "ns::nested::ABC", "other::ABC",
                                    "other::A"));
 }
 
 TEST(DexTest, DexLimitedNumMatches) {
-  auto I = Dex::build(generateNumSymbols(0, 100), RefSlab());
+  auto I = Dex::build(generateNumSymbols(0, 100), RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "5";
   Req.AnyScope = true;
   Req.Limit = 3;
   bool Incomplete;
   auto Matches = match(*I, Req, &Incomplete);
   EXPECT_TRUE(Req.Limit);
   EXPECT_EQ(Matches.size(), *Req.Limit);
   EXPECT_TRUE(Incomplete);
 }
 
 TEST(DexTest, FuzzyMatch) {
   auto I = Dex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
-      RefSlab());
+      RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.AnyScope = true;
   Req.Limit = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 TEST(DexTest, ShortQuery) {
-  auto I = Dex::build(generateSymbols({"OneTwoThreeFour"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"OneTwoThreeFour"}), RefSlab(),
+                      RelationSlab());
   FuzzyFindRequest Req;
   Req.AnyScope = true;
   bool Incomplete;
 
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour"));
   EXPECT_FALSE(Incomplete) << "Empty string is not a short query";
 
   Req.Query = "t";
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre());
   EXPECT_TRUE(Incomplete) << "Short queries have different semantics";
 
   Req.Query = "tt";
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre());
   EXPECT_TRUE(Incomplete) << "Short queries have different semantics";
 
   Req.Query = "ttf";
   EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour"));
   EXPECT_FALSE(Incomplete) << "3-char string is not a short query";
 }
 
 TEST(DexTest, MatchQualifiedNamesWithoutSpecificScope) {
-  auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
+                      RelationSlab());
   FuzzyFindRequest Req;
   Req.AnyScope = true;
   Req.Query = "y";
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
 }
 
 TEST(DexTest, MatchQualifiedNamesWithGlobalScope) {
-  auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
+                      RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3"));
 }
 
 TEST(DexTest, MatchQualifiedNamesWithOneScope) {
-  auto I = Dex::build(
-      generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab());
+  auto I =
+      Dex::build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}),
+                 RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2"));
 }
 
 TEST(DexTest, MatchQualifiedNamesWithMultipleScopes) {
-  auto I = Dex::build(
-      generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab());
+  auto I =
+      Dex::build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}),
+                 RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::", "b::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3"));
 }
 
 TEST(DexTest, NoMatchNestedScopes) {
-  auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab(),
+                      RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1"));
 }
 
 TEST(DexTest, WildcardScope) {
-  auto I =
-      Dex::build(generateSymbols({"a::y1", "a::b::y2", "c::y3"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2", "c::y3"}),
+                      RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.AnyScope = true;
   Req.Query = "y";
   Req.Scopes = {"a::"};
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("a::y1", "a::b::y2", "c::y3"));
 }
 
 TEST(DexTest, IgnoreCases) {
-  auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(),
+                      RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 
 TEST(DexTest, UnknownPostingList) {
   // Regression test: we used to ignore unknown scopes and accept any symbol.
-  auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(),
+                      RelationSlab());
   FuzzyFindRequest Req;
   Req.Scopes = {"ns2::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre());
 }
 
 TEST(DexTest, Lookup) {
-  auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab());
+  auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(),
+                      RelationSlab());
   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(DexTest, SymbolIndexOptionsFilter) {
   auto CodeCompletionSymbol = symbol("Completion");
   auto NonCodeCompletionSymbol = symbol("NoCompletion");
   CodeCompletionSymbol.Flags = Symbol::SymbolFlag::IndexedForCodeCompletion;
   NonCodeCompletionSymbol.Flags = Symbol::SymbolFlag::None;
   std::vector<Symbol> Symbols{CodeCompletionSymbol, NonCodeCompletionSymbol};
-  Dex I(Symbols, RefSlab());
+  Dex I(Symbols, RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.AnyScope = true;
   Req.RestrictForCodeCompletion = false;
   EXPECT_THAT(match(I, Req), ElementsAre("Completion", "NoCompletion"));
   Req.RestrictForCodeCompletion = true;
   EXPECT_THAT(match(I, Req), ElementsAre("Completion"));
 }
 
 TEST(DexTest, ProximityPathsBoosting) {
   auto RootSymbol = symbol("root::abc");
   RootSymbol.CanonicalDeclaration.FileURI = "unittest:///file.h";
   auto CloseSymbol = symbol("close::abc");
   CloseSymbol.CanonicalDeclaration.FileURI = "unittest:///a/b/c/d/e/f/file.h";
 
   std::vector<Symbol> Symbols{CloseSymbol, RootSymbol};
-  Dex I(Symbols, RefSlab());
+  Dex I(Symbols, RefSlab(), RelationSlab());
 
   FuzzyFindRequest Req;
   Req.AnyScope = true;
   Req.Query = "abc";
   // The best candidate can change depending on the proximity paths.
   Req.Limit = 1;
 
   // FuzzyFind request comes from the file which is far from the root: expect
TEST(DexTests, Refs) {
   AddRef(Foo, "reffoo.h", RefKind::Reference);
   AddRef(Bar, "bar.h", RefKind::Declaration);
 
   RefsRequest Req;
   Req.IDs.insert(Foo.ID);
   Req.Filter = RefKind::Declaration | RefKind::Definition;
 
   std::vector<std::string> Files;
-  Dex(std::vector<Symbol>{Foo, Bar}, Refs).refs(Req, [&](const Ref &R) {
-    Files.push_back(R.Location.FileURI);
-  });
+  Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab())
+      .refs(Req, [&](const Ref &R) { Files.push_back(R.Location.FileURI); });
   EXPECT_THAT(Files, UnorderedElementsAre("foo.h", "foo.cc"));
 
   Req.Limit = 1;
   Files.clear();
-  Dex(std::vector<Symbol>{Foo, Bar}, Refs).refs(Req, [&](const Ref &R) {
-    Files.push_back(R.Location.FileURI);
-  });
+  Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab())
+      .refs(Req, [&](const Ref &R) { Files.push_back(R.Location.FileURI); });
   EXPECT_THAT(Files, ElementsAre(AnyOf("foo.h", "foo.cc")));
 }
 
+TEST(DexTests, Relations) {
+  auto Parent = symbol("Parent");
+  auto Child1 = symbol("Child1");
+  auto Child2 = symbol("Child2");
+
+  std::vector<Relation> Relations{
+      {Parent.ID, index::SymbolRole::RelationBaseOf, Child1.ID},
+      {Parent.ID, index::SymbolRole::RelationBaseOf, Child2.ID}};
+
+  Dex I{std::vector<Symbol>{Parent, Child1, Child2}, RefSlab(), Relations};
+
+  std::vector<SymbolID> Results;
+  I.relations(RelationsRequest{Parent.ID, index::SymbolRole::RelationBaseOf},
+              [&](const SymbolID &Object) { Results.push_back(Object); });
+  EXPECT_THAT(Results, UnorderedElementsAre(Child1.ID, Child2.ID));
+}
+
 TEST(DexTest, PreferredTypesBoosting) {
   auto Sym1 = symbol("t1");
   Sym1.Type = "T1";
   auto Sym2 = symbol("t2");
   Sym2.Type = "T2";
 
   std::vector<Symbol> Symbols{Sym1, Sym2};
-  Dex I(Symbols, RefSlab());
+  Dex I(Symbols, RefSlab(), RelationSlab());
 
   FuzzyFindRequest Req;
   Req.AnyScope = true;
   Req.Query = "t";
   // The best candidate can change depending on the preferred type.
   Req.Limit = 1;
 
   Req.PreferredTypes = {Sym1.Type};
TEST(DexTest, TemplateSpecialization) {
 
   S = symbol("TempSpec");
   S.ID = SymbolID("2");
   S.TemplateSpecializationArgs = "<int, U>";
   S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
       index::SymbolProperty::TemplatePartialSpecialization);
   B.insert(S);
 
-  auto I = dex::Dex::build(std::move(B).build(), RefSlab());
+  auto I = dex::Dex::build(std::move(B).build(), RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.AnyScope = true;
 
   Req.Query = "TempSpec";
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("TempSpec", "TempSpec<int, bool>",
                                    "TempSpec<int, U>"));
 

clang-tools-extra/clangd/unittests/DiagnosticsTests.cpp

buildIndexWithSymbol(llvm::ArrayRef<SymbolWithHeader> Syms) {
   for (const auto &S : Syms) {
     Symbol Sym = cls(S.QName);
     Sym.Flags |= Symbol::IndexedForCodeCompletion;
     Sym.CanonicalDeclaration.FileURI = S.DeclaringFile.c_str();
     Sym.Definition.FileURI = S.DeclaringFile.c_str();
     Sym.IncludeHeaders.emplace_back(S.IncludeHeader, 1);
     Slab.insert(Sym);
   }
-  return MemIndex::build(std::move(Slab).build(), RefSlab());
+  return MemIndex::build(std::move(Slab).build(), RefSlab(), RelationSlab());
 }
 
 TEST(IncludeFixerTest, IncompleteType) {
   Annotations Test(R"cpp(
 $insert[[]]namespace ns {
   class X;
   $nested[[X::]]Nested n;
 }
int main() {
   Symbol Sym = cls("ns::X");
   Sym.Flags |= Symbol::IndexedForCodeCompletion;
   Sym.CanonicalDeclaration.FileURI = "unittest:///x.h";
   Sym.Definition.FileURI = "unittest:///x.cc";
   Sym.IncludeHeaders.emplace_back("\"x.h\"", 1);
 
   SymbolSlab::Builder Slab;
   Slab.insert(Sym);
-  auto Index = MemIndex::build(std::move(Slab).build(), RefSlab());
+  auto Index =
+      MemIndex::build(std::move(Slab).build(), RefSlab(), RelationSlab());
   TU.ExternalIndex = Index.get();
 
   EXPECT_THAT(TU.build().getDiagnostics(),
               UnorderedElementsAre(
                   Diag(Test.range("base"), "base class has incomplete type"),
                   Diag(Test.range("access"),
                        "member access into incomplete type 'ns::X'")));
 }

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

std::unique_ptr<RefSlab> refSlab(const SymbolID &ID, const char *Path) {
   Slab.insert(ID, R);
   return llvm::make_unique<RefSlab>(std::move(Slab).build());
 }
 
 TEST(FileSymbolsTest, UpdateAndGet) {
   FileSymbols FS;
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""), IsEmpty());
 
-  FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"), false);
+  FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"), nullptr,
+            false);
   EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""),
               UnorderedElementsAre(QName("1"), QName("2"), QName("3")));
   EXPECT_THAT(getRefs(*FS.buildIndex(IndexType::Light), SymbolID("1")),
               RefsAre({FileURI("f1.cc")}));
 }
 
 TEST(FileSymbolsTest, Overlap) {
   FileSymbols FS;
-  FS.update("f1", numSlab(1, 3), nullptr, false);
-  FS.update("f2", numSlab(3, 5), nullptr, false);
+  FS.update("f1", numSlab(1, 3), nullptr, nullptr, false);
+  FS.update("f2", numSlab(3, 5), nullptr, nullptr, false);
   for (auto Type : {IndexType::Light, IndexType::Heavy})
     EXPECT_THAT(runFuzzyFind(*FS.buildIndex(Type), ""),
                 UnorderedElementsAre(QName("1"), QName("2"), QName("3"),
                                      QName("4"), QName("5")));
 }
 
 TEST(FileSymbolsTest, MergeOverlap) {
   FileSymbols FS;
   auto OneSymboSlab = [](Symbol Sym) {
     SymbolSlab::Builder S;
     S.insert(Sym);
     return llvm::make_unique<SymbolSlab>(std::move(S).build());
   };
   auto X1 = symbol("x");
   X1.CanonicalDeclaration.FileURI = "file:///x1";
   auto X2 = symbol("x");
   X2.Definition.FileURI = "file:///x2";
 
-  FS.update("f1", OneSymboSlab(X1), nullptr, false);
-  FS.update("f2", OneSymboSlab(X2), nullptr, false);
+  FS.update("f1", OneSymboSlab(X1), nullptr, nullptr, false);
+  FS.update("f2", OneSymboSlab(X2), nullptr, nullptr, false);
   for (auto Type : {IndexType::Light, IndexType::Heavy})
     EXPECT_THAT(
         runFuzzyFind(*FS.buildIndex(Type, DuplicateHandling::Merge), "x"),
         UnorderedElementsAre(
             AllOf(QName("x"), DeclURI("file:///x1"), DefURI("file:///x2"))));
 }
 
 TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
   FileSymbols FS;
 
   SymbolID ID("1");
-  FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"), false);
+  FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"), nullptr, false);
 
   auto Symbols = FS.buildIndex(IndexType::Light);
   EXPECT_THAT(runFuzzyFind(*Symbols, ""),
               UnorderedElementsAre(QName("1"), QName("2"), QName("3")));
   EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")}));
 
-  FS.update("f1", nullptr, nullptr, false);
+  FS.update("f1", nullptr, nullptr, nullptr, false);
   auto Empty = FS.buildIndex(IndexType::Light);
   EXPECT_THAT(runFuzzyFind(*Empty, ""), IsEmpty());
   EXPECT_THAT(getRefs(*Empty, ID), ElementsAre());
 
   EXPECT_THAT(runFuzzyFind(*Symbols, ""),
               UnorderedElementsAre(QName("1"), QName("2"), QName("3")));
   EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")}));
 }
TEST(FileIndexTest, ReferencesInMainFileWithPreamble) {
   // Expect to see references in main file, references in headers are excluded
   // because we only index main AST.
   EXPECT_THAT(getRefs(Index, findSymbol(TU.headerSymbols(), "Foo").ID),
               RefsAre({RefRange(Main.range())}));
 }
 
 TEST(FileSymbolsTest, CountReferencesNoRefSlabs) {
   FileSymbols FS;
-  FS.update("f1", numSlab(1, 3), nullptr, true);
-  FS.update("f2", numSlab(1, 3), nullptr, false);
+  FS.update("f1", numSlab(1, 3), nullptr, nullptr, true);
+  FS.update("f2", numSlab(1, 3), nullptr, nullptr, false);
   EXPECT_THAT(
       runFuzzyFind(*FS.buildIndex(IndexType::Light, DuplicateHandling::Merge),
                    ""),
       UnorderedElementsAre(AllOf(QName("1"), NumReferences(0u)),
                            AllOf(QName("2"), NumReferences(0u)),
                            AllOf(QName("3"), NumReferences(0u))));
 }
 
 TEST(FileSymbolsTest, CountReferencesWithRefSlabs) {
   FileSymbols FS;
-  FS.update("f1cpp", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cpp"), true);
-  FS.update("f1h", numSlab(1, 3), refSlab(SymbolID("1"), "f1.h"), false);
-  FS.update("f2cpp", numSlab(1, 3), refSlab(SymbolID("2"), "f2.cpp"), true);
-  FS.update("f2h", numSlab(1, 3), refSlab(SymbolID("2"), "f2.h"), false);
-  FS.update("f3cpp", numSlab(1, 3), refSlab(SymbolID("3"), "f3.cpp"), true);
-  FS.update("f3h", numSlab(1, 3), refSlab(SymbolID("3"), "f3.h"), false);
+  FS.update("f1cpp", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cpp"), nullptr,
+            true);
+  FS.update("f1h", numSlab(1, 3), refSlab(SymbolID("1"), "f1.h"), nullptr,
+            false);
+  FS.update("f2cpp", numSlab(1, 3), refSlab(SymbolID("2"), "f2.cpp"), nullptr,
+            true);
+  FS.update("f2h", numSlab(1, 3), refSlab(SymbolID("2"), "f2.h"), nullptr,
+            false);
+  FS.update("f3cpp", numSlab(1, 3), refSlab(SymbolID("3"), "f3.cpp"), nullptr,
+            true);
+  FS.update("f3h", numSlab(1, 3), refSlab(SymbolID("3"), "f3.h"), nullptr,
+            false);
   EXPECT_THAT(
       runFuzzyFind(*FS.buildIndex(IndexType::Light, DuplicateHandling::Merge),
                    ""),
       UnorderedElementsAre(AllOf(QName("1"), NumReferences(1u)),
                            AllOf(QName("2"), NumReferences(1u)),
                            AllOf(QName("3"), NumReferences(1u))));
 }
 } // namespace
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/IndexActionTests.cpp

runIndexingAction(llvm::StringRef MainFilePath,
     IndexFileIn IndexFile;
     llvm::IntrusiveRefCntPtr<FileManager> Files(
         new FileManager(FileSystemOptions(), InMemoryFileSystem));
 
     auto Action = createStaticIndexingAction(
         SymbolCollector::Options(),
         [&](SymbolSlab S) { IndexFile.Symbols = std::move(S); },
         [&](RefSlab R) { IndexFile.Refs = std::move(R); },
+        [&](RelationSlab R) { IndexFile.Relations = std::move(R); },
         [&](IncludeGraph IG) { IndexFile.Sources = std::move(IG); });
 
     std::vector<std::string> Args = {"index_action", "-fsyntax-only",
                                      "-xc++",        "-std=c++11",
                                      "-iquote",      testRoot()};
     Args.insert(Args.end(), ExtraArgs.begin(), ExtraArgs.end());
     Args.push_back(MainFilePath);
 

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

EXPECT_THAT(Slab, UnorderedElementsAre(
                         Relation{A, index::SymbolRole::RelationBaseOf, B},
                         Relation{A, index::SymbolRole::RelationBaseOf, C}));
 }
 
 TEST(SwapIndexTest, OldIndexRecycled) {
   auto Token = std::make_shared<int>();
   std::weak_ptr<int> WeakToken = Token;
 
-  SwapIndex S(llvm::make_unique<MemIndex>(
-      SymbolSlab(), RefSlab(), std::move(Token), /*BackingDataSize=*/0));
+  SwapIndex S(llvm::make_unique<MemIndex>(SymbolSlab(), RefSlab(),
+                                          RelationSlab(), std::move(Token),
+                                          /*BackingDataSize=*/0));
   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";
   Req.AnyScope = true;
-  MemIndex I(Symbols, RefSlab());
+  MemIndex I(Symbols, RefSlab(), RelationSlab());
   EXPECT_THAT(match(I, Req), ElementsAre("2"));
 }
 
 TEST(MemIndexTest, MemIndexLimitedNumMatches) {
-  auto I = MemIndex::build(generateNumSymbols(0, 100), RefSlab());
+  auto I =
+      MemIndex::build(generateNumSymbols(0, 100), RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "5";
   Req.AnyScope = true;
   Req.Limit = 3;
   bool Incomplete;
   auto Matches = match(*I, Req, &Incomplete);
   EXPECT_TRUE(Req.Limit);
   EXPECT_EQ(Matches.size(), *Req.Limit);
   EXPECT_TRUE(Incomplete);
 }
 
 TEST(MemIndexTest, FuzzyMatch) {
   auto I = MemIndex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
-      RefSlab());
+      RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.AnyScope = true;
   Req.Limit = 2;
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
-  auto I =
-      MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
+                           RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.AnyScope = true;
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
-  auto I =
-      MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
+                           RelationSlab());
   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"}), RefSlab());
+      generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab(),
+      RelationSlab());
   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"}), RefSlab());
+      generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab(),
+      RelationSlab());
   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"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab(),
+                           RelationSlab());
   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"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(),
+                           RelationSlab());
   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"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(),
+                           RelationSlab());
   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(MemIndexTest, TemplateSpecialization) {
 
   S = symbol("TempSpec");
   S.ID = SymbolID("3");
   S.TemplateSpecializationArgs = "<int, U>";
   S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
       index::SymbolProperty::TemplatePartialSpecialization);
   B.insert(S);
 
-  auto I = MemIndex::build(std::move(B).build(), RefSlab());
+  auto I = MemIndex::build(std::move(B).build(), RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.AnyScope = true;
 
   Req.Query = "TempSpec";
   EXPECT_THAT(match(*I, Req),
               UnorderedElementsAre("TempSpec", "TempSpec<int, bool>",
                                    "TempSpec<int, U>"));
 
   // FIXME: Add filtering for template argument list.
   Req.Query = "TempSpec<int";
   EXPECT_THAT(match(*I, Req), IsEmpty());
 }
 
 TEST(MergeIndexTest, Lookup) {
-  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()),
-       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
+                           RelationSlab()),
+       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
+                           RelationSlab());
   MergedIndex M(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"}), RefSlab()),
-       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab());
+  auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
+                           RelationSlab()),
+       J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
+                           RelationSlab());
   FuzzyFindRequest Req;
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(MergedIndex(I.get(), J.get()), Req),
               UnorderedElementsAre("ns::A", "ns::B", "ns::C"));
 }
 
 TEST(MergeTest, Merge) {
   Symbol L, R;