[WIP] Add override relationship.

[hokein]

Summary

Performance (on LLVM): Before 20K relations vs 44K relations after, didn't see memory consumption increase, both ~330MB

[hokein]

closing it in favor of https://reviews.llvm.org/D91610.

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

 #include <cstdint>
 #include <utility>
 
 namespace clang {
 namespace clangd {
 
 enum class RelationKind : uint8_t {
   BaseOf,
+  OverridenBy,
 };
 
 /// Represents a relation between two symbols.
 /// For an example "A is a base class of B" may be represented
 /// as { Subject = A, Predicate = BaseOf, Object = B }.
 struct Relation {
   SymbolID Subject;
   RelationKind Predicate;
   SymbolID Object;
 
   bool operator==(const Relation &Other) const {
     return std::tie(Subject, Predicate, Object) ==
            std::tie(Other.Subject, Other.Predicate, Other.Object);
   }
   // SPO order
   bool operator<(const Relation &Other) const {
     return std::tie(Subject, Predicate, Object) <
            std::tie(Other.Subject, Other.Predicate, Other.Object);
   }
 };
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const RelationKind R);
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Relation &R);
 
 class RelationSlab {
 public:
   using value_type = Relation;
   using const_iterator = std::vector<value_type>::const_iterator;
   using iterator = const_iterator;
 
   RelationSlab() = default;

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

 //===--- Relation.cpp --------------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Relation.h"
 
 #include <algorithm>
 
 namespace clang {
 namespace clangd {
 
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const RelationKind R) {
+  switch (R) {
+  case RelationKind ::BaseOf:
+    return OS << "BaseOf";
+  case RelationKind ::OverridenBy:
+    return OS << "OverridenBy";
+  }
+  llvm_unreachable("Unhandled RelationKind enum");
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Relation &R) {
+  return OS << R.Subject << " " << R.Predicate << " " << R.Object;
+}
+
 llvm::iterator_range<RelationSlab::iterator>
 RelationSlab::lookup(const SymbolID &Subject, RelationKind Predicate) const {
   auto IterPair = std::equal_range(Relations.begin(), Relations.end(),
                                    Relation{Subject, Predicate, SymbolID{}},
                                    [](const Relation &A, const Relation &B) {
                                      return std::tie(A.Subject, A.Predicate) <
                                             std::tie(B.Subject, B.Predicate);
                                    });

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

 namespace clangd {
 namespace {
 llvm::Error makeError(const llvm::Twine &Msg) {
   return llvm::make_error<llvm::StringError>(Msg,
                                              llvm::inconvertibleErrorCode());
 }
 } // namespace
 
-RelationKind symbolRoleToRelationKind(index::SymbolRole Role) {
-  // SymbolRole is used to record relations in the index.
-  // Only handle the relations we actually store currently.
-  // If we start storing more relations, this list can be expanded.
-  switch (Role) {
-  case index::SymbolRole::RelationBaseOf:
-    return RelationKind::BaseOf;
-  default:
-    llvm_unreachable("Unsupported symbol role");
-  }
-}
-
-index::SymbolRole relationKindToSymbolRole(RelationKind Kind) {
-  switch (Kind) {
-  case RelationKind::BaseOf:
-    return index::SymbolRole::RelationBaseOf;
-  }
-  llvm_unreachable("Invalid relation kind");
-}
-
 namespace {
 
 // IO PRIMITIVES
 // We use little-endian 32 bit ints, sometimes with variable-length encoding.
 //
 // Variable-length int encoding (varint) uses the bottom 7 bits of each byte
 // to encode the number, and the top bit to indicate whether more bytes follow.
 // e.g. 9a 2f means [0x1a and keep reading, 0x2f and stop].

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

 #include "CanonicalIncludes.h"
 #include "CodeComplete.h"
 #include "CodeCompletionStrings.h"
 #include "ExpectedTypes.h"
 #include "Logger.h"
 #include "SourceCode.h"
 #include "SymbolLocation.h"
 #include "URI.h"
+#include "index/Relation.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/Specifiers.h"
 #include "clang/Index/IndexSymbol.h"

 }
 
 RefKind toRefKind(index::SymbolRoleSet Roles) {
   return static_cast<RefKind>(static_cast<unsigned>(RefKind::All) & Roles);
 }
 
 bool shouldIndexRelation(const index::SymbolRelation &R) {
   // We currently only index BaseOf relations, for type hierarchy subtypes.
-  return R.Roles & static_cast<unsigned>(index::SymbolRole::RelationBaseOf);
+  return R.Roles & static_cast<unsigned>(index::SymbolRole::RelationBaseOf) ||
+         R.Roles & static_cast<unsigned>(index::SymbolRole::RelationOverrideOf);
+}
+
+llvm::Optional<RelationKind> indexableRelation(const index::SymbolRelation &R) {
+  if (R.Roles & static_cast<unsigned>(index::SymbolRole::RelationBaseOf))
+    return RelationKind::BaseOf;
+  if (R.Roles & static_cast<unsigned>(index::SymbolRole::RelationOverrideOf))
+    return RelationKind::OverridenBy;
+  return None;
 }
 
 } // namespace
 
 SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {}
 
 void SymbolCollector::initialize(ASTContext &Ctx) {
   ASTCtx = &Ctx;
bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
   setIncludeLocation(S, DefLoc);
   Symbols.insert(S);
   return true;
 }
 
 void SymbolCollector::processRelations(
     const NamedDecl &ND, const SymbolID &ID,
     ArrayRef<index::SymbolRelation> Relations) {
-  // Store subtype relations.
-  if (!dyn_cast<TagDecl>(&ND))
-    return;
-
   for (const auto &R : Relations) {
-    if (!shouldIndexRelation(R))
+    // if (!shouldIndexRelation(R))
+    //   continue;
+    auto RKind = indexableRelation(R);
+    if (!RKind)
       continue;
-
     const Decl *Object = R.RelatedSymbol;
 
     auto ObjectID = getSymbolID(Object);
     if (!ObjectID)
       continue;
 
     // Record the relation.
     // TODO: There may be cases where the object decl is not indexed for some
     // reason. Those cases should probably be removed in due course, but for
     // now there are two possible ways to handle it:
     //   (A) Avoid storing the relation in such cases.
     //   (B) Store it anyways. Clients will likely lookup() the SymbolID
     //       in the index and find nothing, but that's a situation they
     //       probably need to handle for other reasons anyways.
     // We currently do (B) because it's simpler.
-    this->Relations.insert(Relation{ID, RelationKind::BaseOf, *ObjectID});
+    if (*RKind == RelationKind::BaseOf)
+      this->Relations.insert({ID, *RKind, *ObjectID});
+    else if (*RKind == RelationKind::OverridenBy)
+      this->Relations.insert({*ObjectID, *RKind, ID});
   }
 }
 
 void SymbolCollector::setIncludeLocation(const Symbol &S, SourceLocation Loc) {
   if (Opts.CollectIncludePath)
     if (shouldCollectIncludePath(S.SymInfo.Kind))
       // Use the expansion location to get the #include header since this is
       // where the symbol is exposed.

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

TEST_F(SymbolCollectorTest, Relations) {
   )";
   runSymbolCollector(Header, /*Main=*/"");
   const Symbol &Base = findSymbol(Symbols, "Base");
   const Symbol &Derived = findSymbol(Symbols, "Derived");
   EXPECT_THAT(Relations,
               Contains(Relation{Base.ID, RelationKind::BaseOf, Derived.ID}));
 }
 
+TEST_F(SymbolCollectorTest, OverrideRelations) {
+  std::string Header = R"cpp(
+    class Base {
+    virtual void foo1();
+    };
+    class Derived1 : public Base {
+    void foo1() override;
+    virtual void foo2();
+    };
+    class Derived2 : public Derived1 {
+    void foo2() override;
+    };
+  )cpp";
+  runSymbolCollector(Header, /*Main=*/"");
+  const Symbol &Base = findSymbol(Symbols, "Base");
+  const Symbol &Derived1 = findSymbol(Symbols, "Derived1");
+  const Symbol &Derived2 = findSymbol(Symbols, "Derived2");
+  const Symbol &Foo1 = findSymbol(Symbols, "Base::foo1");
+  const Symbol &OverrideFoo1 = findSymbol(Symbols, "Derived1::foo1");
+  const Symbol &Foo2 = findSymbol(Symbols, "Derived1::foo2");
+  const Symbol &OverrideFoo2 = findSymbol(Symbols, "Derived2::foo2");
+  EXPECT_THAT(Relations,
+              UnorderedElementsAreArray({
+                  Relation{Foo1.ID, RelationKind::OverridenBy, OverrideFoo1.ID},
+                  Relation{Foo2.ID, RelationKind::OverridenBy, OverrideFoo2.ID},
+                  Relation{Base.ID, RelationKind::BaseOf, Derived1.ID},
+                  Relation{Derived1.ID, RelationKind::BaseOf, Derived2.ID},
+              }));
+}
+
 TEST_F(SymbolCollectorTest, References) {
   const std::string Header = R"(
     class W;
     class X {};
     class Y;
     class Z {}; // not used anywhere
     Y* y = nullptr;  // used in header doesn't count
     #define GLOBAL_Z(name) Z name;