Index: clang-tools-extra/trunk/clangd/index/Background.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/Background.cpp
+++ clang-tools-extra/trunk/clangd/index/Background.cpp
@@ -276,6 +276,7 @@
   struct File {
     llvm::DenseSet<const Symbol *> Symbols;
     llvm::DenseSet<const Ref *> Refs;
+    llvm::DenseSet<const Relation *> Relations;
     FileDigest Digest;
   };
   llvm::StringMap<File> Files;
@@ -288,12 +289,16 @@
     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
@@ -319,18 +324,27 @@
       }
     }
   }
+  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
@@ -339,6 +353,7 @@
       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))
@@ -356,7 +371,7 @@
       // 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);
     }
   }
@@ -429,6 +444,7 @@
   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.
@@ -570,9 +586,13 @@
       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);
     }
   }
 
Index: clang-tools-extra/trunk/clangd/index/FileIndex.h
===================================================================
--- clang-tools-extra/trunk/clangd/index/FileIndex.h
+++ clang-tools-extra/trunk/clangd/index/FileIndex.h
@@ -63,7 +63,8 @@
   /// 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
@@ -83,6 +84,8 @@
   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.
@@ -128,15 +131,17 @@
   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);
+SlabTuple indexHeaderSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
+                             const CanonicalIncludes &Includes);
 
 } // namespace clangd
 } // namespace clang
Index: clang-tools-extra/trunk/clangd/index/FileIndex.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/FileIndex.cpp
+++ clang-tools-extra/trunk/clangd/index/FileIndex.cpp
@@ -28,10 +28,10 @@
 namespace clang {
 namespace clangd {
 
-static std::pair<SymbolSlab, RefSlab>
-indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
-             llvm::ArrayRef<Decl *> DeclsToIndex,
-             const CanonicalIncludes &Includes, bool IsIndexMainAST) {
+static SlabTuple indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
+                              llvm::ArrayRef<Decl *> DeclsToIndex,
+                              const CanonicalIncludes &Includes,
+                              bool IsIndexMainAST) {
   SymbolCollector::Options CollectorOpts;
   CollectorOpts.CollectIncludePath = true;
   CollectorOpts.Includes = &Includes;
@@ -65,32 +65,35 @@
 
   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) {
+SlabTuple 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;
+                      /*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);
@@ -98,18 +101,23 @@
     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);
   }
-  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);
@@ -120,6 +128,8 @@
       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;
@@ -187,24 +197,34 @@
     }
   }
 
+  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);
@@ -220,10 +240,12 @@
 void FileIndex::updatePreamble(PathRef Path, ASTContext &AST,
                                std::shared_ptr<Preprocessor> PP,
                                const CanonicalIncludes &Includes) {
-  auto Symbols = indexHeaderSymbols(AST, std::move(PP), Includes);
+  auto Slabs = indexHeaderSymbols(AST, std::move(PP), Includes);
   PreambleSymbols.update(
-      Path, llvm::make_unique<SymbolSlab>(std::move(Symbols)),
-      llvm::make_unique<RefSlab>(), /*CountReferences=*/false);
+      Path, llvm::make_unique<SymbolSlab>(std::move(std::get<0>(Slabs))),
+      llvm::make_unique<RefSlab>(),
+      llvm::make_unique<RelationSlab>(std::move(std::get<2>(Slabs))),
+      /*CountReferences=*/false);
   PreambleIndex.reset(
       PreambleSymbols.buildIndex(UseDex ? IndexType::Heavy : IndexType::Light,
                                  DuplicateHandling::PickOne));
@@ -232,8 +254,9 @@
 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));
Index: clang-tools-extra/trunk/clangd/index/Index.h
===================================================================
--- clang-tools-extra/trunk/clangd/index/Index.h
+++ clang-tools-extra/trunk/clangd/index/Index.h
@@ -73,6 +73,13 @@
   llvm::Optional<uint32_t> Limit;
 };
 
+struct RelationsRequest {
+  llvm::DenseSet<SymbolID> Subjects;
+  index::SymbolRole Predicate;
+  /// If set, limit the number of relations returned from the index.
+  llvm::Optional<uint32_t> Limit;
+};
+
 /// 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 {
@@ -103,6 +110,14 @@
   virtual void refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const = 0;
 
+  /// Finds all relations (S, P, O) stored in the index such that S is among
+  /// Req.Subjects and P is Req.Predicate, and invokes \p Callback for (S, O) in
+  /// each.
+  virtual void relations(
+      const RelationsRequest &Req,
+      llvm::function_ref<void(const SymbolID &Subject, const Symbol &Object)>
+          Callback) const = 0;
+
   /// Returns estimated size of index (in bytes).
   virtual size_t estimateMemoryUsage() const = 0;
 };
@@ -123,6 +138,10 @@
               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 Symbol &)>)
+      const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
Index: clang-tools-extra/trunk/clangd/index/Index.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/Index.cpp
+++ clang-tools-extra/trunk/clangd/index/Index.cpp
@@ -69,6 +69,12 @@
                      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 &, const Symbol &)> CB) const {
+  return snapshot()->relations(R, CB);
+}
+
 size_t SwapIndex::estimateMemoryUsage() const {
   return snapshot()->estimateMemoryUsage();
 }
Index: clang-tools-extra/trunk/clangd/index/IndexAction.h
===================================================================
--- clang-tools-extra/trunk/clangd/index/IndexAction.h
+++ clang-tools-extra/trunk/clangd/index/IndexAction.h
@@ -27,6 +27,7 @@
     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
Index: clang-tools-extra/trunk/clangd/index/IndexAction.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/IndexAction.cpp
+++ clang-tools-extra/trunk/clangd/index/IndexAction.cpp
@@ -116,9 +116,11 @@
               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())) {}
@@ -155,6 +157,8 @@
     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.
@@ -168,6 +172,7 @@
 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;
@@ -181,6 +186,7 @@
     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 =
@@ -198,7 +204,8 @@
   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
Index: clang-tools-extra/trunk/clangd/index/MemIndex.h
===================================================================
--- clang-tools-extra/trunk/clangd/index/MemIndex.h
+++ clang-tools-extra/trunk/clangd/index/MemIndex.h
@@ -20,26 +20,32 @@
 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,
@@ -51,6 +57,10 @@
   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 &, const Symbol &)>
+                     Callback) const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
@@ -58,6 +68,9 @@
   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;
Index: clang-tools-extra/trunk/clangd/index/MemIndex.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/MemIndex.cpp
+++ clang-tools-extra/trunk/clangd/index/MemIndex.cpp
@@ -16,12 +16,13 @@
 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(
@@ -84,8 +85,29 @@
   }
 }
 
+void MemIndex::relations(
+    const RelationsRequest &Req,
+    llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
+  uint32_t Remaining =
+      Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  for (const SymbolID &Subject : Req.Subjects) {
+    LookupRequest LookupReq;
+    auto It = Relations.find(std::make_pair(Subject, Req.Predicate));
+    if (It != Relations.end()) {
+      for (const auto &Obj : It->second) {
+        if (Remaining > 0) {
+          --Remaining;
+          LookupReq.IDs.insert(Obj);
+        }
+      }
+    }
+    lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
+  }
+}
+
 size_t MemIndex::estimateMemoryUsage() const {
-  return Index.getMemorySize() + Refs.getMemorySize() + BackingDataSize;
+  return Index.getMemorySize() + Refs.getMemorySize() +
+         Relations.getMemorySize() + BackingDataSize;
 }
 
 } // namespace clangd
Index: clang-tools-extra/trunk/clangd/index/Merge.h
===================================================================
--- clang-tools-extra/trunk/clangd/index/Merge.h
+++ clang-tools-extra/trunk/clangd/index/Merge.h
@@ -42,6 +42,9 @@
               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 Symbol &)>)
+      const override;
   size_t estimateMemoryUsage() const override {
     return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
   }
Index: clang-tools-extra/trunk/clangd/index/Merge.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/Merge.cpp
+++ clang-tools-extra/trunk/clangd/index/Merge.cpp
@@ -95,7 +95,7 @@
   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.
   //
@@ -120,6 +120,31 @@
   });
 }
 
+void MergedIndex::relations(
+    const RelationsRequest &Req,
+    llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
+  uint32_t Remaining =
+      Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  // Return results from both indexes but avoid duplicates.
+  // We might return stale relations from the static index;
+  // we don't currently have a good way of identifying them.
+  llvm::DenseSet<std::pair<SymbolID, SymbolID>> SeenRelations;
+  Dynamic->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
+    Callback(Subject, Object);
+    SeenRelations.insert(std::make_pair(Subject, Object.ID));
+    --Remaining;
+  });
+  if (Remaining == 0)
+    return;
+  Static->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
+    if (Remaining > 0 &&
+        !SeenRelations.count(std::make_pair(Subject, Object.ID))) {
+      --Remaining;
+      Callback(Subject, Object);
+    }
+  });
+}
+
 // 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) {
Index: clang-tools-extra/trunk/clangd/index/Relation.h
===================================================================
--- clang-tools-extra/trunk/clangd/index/Relation.h
+++ clang-tools-extra/trunk/clangd/index/Relation.h
@@ -85,4 +85,31 @@
 } // 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
Index: clang-tools-extra/trunk/clangd/index/Serialization.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/Serialization.cpp
+++ clang-tools-extra/trunk/clangd/index/Serialization.cpp
@@ -656,8 +656,10 @@
   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"
Index: clang-tools-extra/trunk/clangd/index/dex/Dex.h
===================================================================
--- clang-tools-extra/trunk/clangd/index/dex/Dex.h
+++ clang-tools-extra/trunk/clangd/index/dex/Dex.h
@@ -41,26 +41,32 @@
 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,
@@ -72,6 +78,10 @@
   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 &, const Symbol &)>
+                     Callback) const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
@@ -96,6 +106,8 @@
   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;
Index: clang-tools-extra/trunk/clangd/index/dex/Dex.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/dex/Dex.cpp
+++ clang-tools-extra/trunk/clangd/index/dex/Dex.cpp
@@ -23,10 +23,14 @@
 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 {
@@ -259,6 +263,27 @@
     }
 }
 
+void Dex::relations(
+    const RelationsRequest &Req,
+    llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
+  trace::Span Tracer("Dex relations");
+  uint32_t Remaining =
+      Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  for (const SymbolID &Subject : Req.Subjects) {
+    LookupRequest LookupReq;
+    auto It = Relations.find(std::make_pair(Subject, Req.Predicate));
+    if (It != Relations.end()) {
+      for (const auto &Object : It->second) {
+        if (Remaining > 0) {
+          --Remaining;
+          LookupReq.IDs.insert(Object);
+        }
+      }
+    }
+    lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
+  }
+}
+
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
@@ -267,6 +292,7 @@
   for (const auto &TokenToPostingList : InvertedIndex)
     Bytes += TokenToPostingList.second.bytes();
   Bytes += Refs.getMemorySize();
+  Bytes += Relations.getMemorySize();
   return Bytes + BackingDataSize;
 }
 
Index: clang-tools-extra/trunk/clangd/indexer/IndexerMain.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/indexer/IndexerMain.cpp
+++ clang-tools-extra/trunk/clangd/indexer/IndexerMain.cpp
@@ -62,6 +62,12 @@
                      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();
   }
@@ -71,6 +77,7 @@
   ~IndexActionFactory() {
     Result.Symbols = std::move(Symbols).build();
     Result.Refs = std::move(Refs).build();
+    Result.Relations = std::move(Relations).build();
   }
 
 private:
@@ -78,6 +85,7 @@
   std::mutex SymbolsMu;
   SymbolSlab::Builder Symbols;
   RefSlab::Builder Refs;
+  RelationSlab::Builder Relations;
 };
 
 } // namespace
Index: clang-tools-extra/trunk/clangd/unittests/BackgroundIndexTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/BackgroundIndexTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/BackgroundIndexTests.cpp
@@ -1,5 +1,6 @@
 #include "SyncAPI.h"
 #include "TestFS.h"
+#include "TestTU.h"
 #include "index/Background.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/Threading.h"
@@ -170,8 +171,12 @@
       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;
@@ -214,8 +219,21 @@
 
   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")));
+
+  // The BaseOf relationship between A_CC and B_CC is stored in the file
+  // containing the definition of the subject (A_CC)
+  SymbolID A = findSymbol(*ShardHeader->Symbols, "A_CC").ID;
+  SymbolID B = findSymbol(*ShardSource->Symbols, "B_CC").ID;
+  EXPECT_THAT(
+      *ShardHeader->Relations,
+      UnorderedElementsAre(Relation{A, index::SymbolRole::RelationBaseOf, B}));
+  // (and not in the file containing the definition of the object (B_CC)).
+  EXPECT_EQ(ShardSource->Relations->size(), 0u);
 }
 
 TEST_F(BackgroundIndexTest, DirectIncludesTest) {
Index: clang-tools-extra/trunk/clangd/unittests/CodeCompleteTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/CodeCompleteTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/CodeCompleteTests.cpp
@@ -90,7 +90,7 @@
   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,
@@ -641,10 +641,10 @@
   CodeCompleteOptions NoInsertion;
   NoInsertion.InsertIncludes = CodeCompleteOptions::NeverInsert;
   Results = completions(Server,
-                             R"cpp(
+                        R"cpp(
           int main() { ns::^ }
       )cpp",
-                             {Sym}, NoInsertion);
+                        {Sym}, NoInsertion);
   EXPECT_THAT(Results.Completions,
               ElementsAre(AllOf(Named("X"), Not(InsertInclude()))));
   // Duplicate based on inclusions in preamble.
@@ -1108,6 +1108,10 @@
   void refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override {}
 
+  void relations(const RelationsRequest &,
+                 llvm::function_ref<void(const SymbolID &, const Symbol &)>)
+      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; }
@@ -2026,19 +2030,19 @@
 
 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]]^",
-  }) {
+           "[[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) {
@@ -2440,10 +2444,10 @@
       /*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"),
+                  SnippetSuffix(" (${1:condition}) {\n${0:statements}\n}"))));
   // However, snippets for functions must *not* end with $0.
   EXPECT_THAT(Results.Completions,
               Contains(AllOf(Named("while_foo"),
Index: clang-tools-extra/trunk/clangd/unittests/DexTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/DexTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/DexTests.cpp
@@ -456,7 +456,8 @@
 //===----------------------------------------------------------------------===//
 
 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"));
@@ -469,7 +470,7 @@
   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::"};
@@ -491,7 +492,7 @@
 }
 
 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;
@@ -506,7 +507,7 @@
 TEST(DexTest, FuzzyMatch) {
   auto I = Dex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
-      RefSlab());
+      RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.AnyScope = true;
@@ -516,7 +517,8 @@
 }
 
 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;
@@ -538,7 +540,8 @@
 }
 
 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";
@@ -546,7 +549,8 @@
 }
 
 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 = {""};
@@ -554,8 +558,9 @@
 }
 
 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::"};
@@ -563,8 +568,9 @@
 }
 
 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::"};
@@ -572,7 +578,8 @@
 }
 
 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::"};
@@ -580,8 +587,8 @@
 }
 
 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";
@@ -591,7 +598,8 @@
 }
 
 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::"};
@@ -600,14 +608,16 @@
 
 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"));
@@ -622,7 +632,7 @@
   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;
@@ -638,7 +648,7 @@
   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;
@@ -677,19 +687,40 @@
   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<Symbol> Symbols{Parent, Child1, Child2};
+
+  std::vector<Relation> Relations{
+      {Parent.ID, index::SymbolRole::RelationBaseOf, Child1.ID},
+      {Parent.ID, index::SymbolRole::RelationBaseOf, Child2.ID}};
+
+  Dex I{Symbols, RefSlab(), Relations};
+
+  std::vector<SymbolID> Results;
+  RelationsRequest Req;
+  Req.Subjects.insert(Parent.ID);
+  Req.Predicate = index::SymbolRole::RelationBaseOf;
+  I.relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
+    Results.push_back(Object.ID);
+  });
+  EXPECT_THAT(Results, UnorderedElementsAre(Child1.ID, Child2.ID));
+}
+
 TEST(DexTest, PreferredTypesBoosting) {
   auto Sym1 = symbol("t1");
   Sym1.Type = "T1";
@@ -697,7 +728,7 @@
   Sym2.Type = "T2";
 
   std::vector<Symbol> Symbols{Sym1, Sym2};
-  Dex I(Symbols, RefSlab());
+  Dex I(Symbols, RefSlab(), RelationSlab());
 
   FuzzyFindRequest Req;
   Req.AnyScope = true;
@@ -733,7 +764,7 @@
       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;
 
Index: clang-tools-extra/trunk/clangd/unittests/DiagnosticsTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/DiagnosticsTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/DiagnosticsTests.cpp
@@ -478,7 +478,7 @@
     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) {
@@ -534,7 +534,8 @@
 
   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(),
Index: clang-tools-extra/trunk/clangd/unittests/FileIndexTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/FileIndexTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/FileIndexTests.cpp
@@ -82,7 +82,8 @@
   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")),
@@ -91,8 +92,8 @@
 
 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"),
@@ -111,8 +112,8 @@
   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"),
@@ -124,14 +125,14 @@
   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());
@@ -347,6 +348,24 @@
   EXPECT_THAT(runFuzzyFind(M, ""), Contains(QName("CLANGD")));
 }
 
+TEST(FileIndexTest, Relations) {
+  TestTU TU;
+  TU.Filename = "f.cpp";
+  TU.HeaderFilename = "f.h";
+  TU.HeaderCode = "class A {}; class B : public A {};";
+  auto AST = TU.build();
+  FileIndex Index;
+  Index.updatePreamble(TU.Filename, AST.getASTContext(),
+                       AST.getPreprocessorPtr(), AST.getCanonicalIncludes());
+  SymbolID A = findSymbol(TU.headerSymbols(), "A").ID;
+  uint32_t Results = 0;
+  RelationsRequest Req;
+  Req.Subjects.insert(A);
+  Req.Predicate = index::SymbolRole::RelationBaseOf;
+  Index.relations(Req, [&](const SymbolID &, const Symbol &) { ++Results; });
+  EXPECT_EQ(Results, 1u);
+}
+
 TEST(FileIndexTest, ReferencesInMainFileWithPreamble) {
   TestTU TU;
   TU.HeaderCode = "class Foo{};";
@@ -369,8 +388,8 @@
 
 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),
                    ""),
@@ -381,12 +400,18 @@
 
 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),
                    ""),
Index: clang-tools-extra/trunk/clangd/unittests/IndexActionTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/IndexActionTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/IndexActionTests.cpp
@@ -77,6 +77,7 @@
         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",
Index: clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/IndexTests.cpp
@@ -119,8 +119,9 @@
   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.
@@ -132,12 +133,13 @@
   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;
@@ -152,7 +154,7 @@
 TEST(MemIndexTest, FuzzyMatch) {
   auto I = MemIndex::build(
       generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
-      RefSlab());
+      RefSlab(), RelationSlab());
   FuzzyFindRequest Req;
   Req.Query = "lol";
   Req.AnyScope = true;
@@ -162,8 +164,8 @@
 }
 
 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;
@@ -171,8 +173,8 @@
 }
 
 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 = {""};
@@ -181,7 +183,8 @@
 
 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::"};
@@ -190,7 +193,8 @@
 
 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::"};
@@ -198,7 +202,8 @@
 }
 
 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::"};
@@ -206,7 +211,8 @@
 }
 
 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::"};
@@ -214,7 +220,8 @@
 }
 
 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"));
@@ -244,7 +251,7 @@
       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;
 
@@ -259,8 +266,10 @@
 }
 
 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"));
@@ -274,8 +283,10 @@
 }
 
 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),
Index: clang-tools-extra/trunk/clangd/unittests/TestTU.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/TestTU.cpp
+++ clang-tools-extra/trunk/clangd/unittests/TestTU.cpp
@@ -69,8 +69,9 @@
 
 SymbolSlab TestTU::headerSymbols() const {
   auto AST = build();
-  return indexHeaderSymbols(AST.getASTContext(), AST.getPreprocessorPtr(),
-                            AST.getCanonicalIncludes());
+  return std::get<0>(indexHeaderSymbols(AST.getASTContext(),
+                                        AST.getPreprocessorPtr(),
+                                        AST.getCanonicalIncludes()));
 }
 
 std::unique_ptr<SymbolIndex> TestTU::index() const {