[clangd] Add OverriddenBy Relation to index.

[usaxena95]

Summary

This was previously explored in reviews.llvm.org/D69094.

For LLVM

• Negligible change in indexing time: 4m4s
• Negligible change in memory usage: 486MB
• Number of relations get 2.3x: 20k to 47k

---

Details:
With OverridenBy relations:
Loaded Dex from static-index.idx with estimated memory usage 510179407 bytes

• number of symbols: 505566
• number of refs: 7813996
• number of relations: 47523

Dex build took 10,368 ms.

Baseline:
Loaded Dex from base-index.idx with estimated memory usage 509652178 bytes

• number of symbols: 505535
• number of refs: 7813807
• number of relations: 20036

Dex build took 10,449 ms.
dexp>

[usaxena95]

added more tests.

[hokein]

Thanks! I think we need to bump the index version number (in index/Serialization.cpp) in order to let the index pick up this change.

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

28–32

nit: can you add an override example here?

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

880

looks like these changes are unexpected?

[usaxena95]

Addressed comments.

[usaxena95]

Bumped the index version. Thanks.

[• Quuxplusone]

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

21

Also here.
And there's a bogus extra space in RelationKind ::BaseOf.

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

24

s/Overriden/Overridden/g

[usaxena95]

Updated sample input for index-serialization test.

[kadircet]

clang-tools-extra/clangd/test/index-serialization/Inputs/sample.cpp

6 ↗

(On Diff #305780)

could you also add a comment for the reason we have this in the test (i.e. Introduces an OverridenBy relation)

[usaxena95]

s/OverridenBy/OverriddenBy

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

24

Thanks.

[usaxena95]

Add documentation for change in index test.

[usaxena95]

Typo fix.

[hokein]

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

31

nit: I would explicitly indicate the base hierarchy here, maybe Derived::Foo() overrides Base::Foo().

[usaxena95]

Addressed final comments. Ready to land.

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 }.
+/// For an example:
+///   - "A is a base class of B" is represented as
+///     { Subject = A, Predicate = BaseOf, Object = B }.
+///   - "A::Foo is overriden by B::Foo" is represented as
+///     { Subject = A::Foo, Predicate = OverridenBy, Object = B::Foo }.
 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

 //   - srcs: information related to include graph
 //   - stri: string table
 //   - symb: symbols
 //   - refs: references to symbols
 
 // The current versioning scheme is simple - non-current versions are rejected.
 // If you make a breaking change, bump this version number to invalidate stored
 // data. Later we may want to support some backward compatibility.
-constexpr static uint32_t Version = 14;
+constexpr static uint32_t Version = 15;
 
 llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data) {
   auto RIFF = riff::readFile(Data);
   if (!RIFF)
     return RIFF.takeError();
   if (RIFF->Type != riff::fourCC("CdIx"))
     return error("wrong RIFF filetype: {0}", riff::fourCCStr(RIFF->Type));
   llvm::StringMap<llvm::StringRef> Chunks;

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

 #include "AST.h"
 #include "CanonicalIncludes.h"
 #include "CodeComplete.h"
 #include "CodeCompletionStrings.h"
 #include "ExpectedTypes.h"
 #include "SourceCode.h"
 #include "SymbolLocation.h"
 #include "URI.h"
+#include "index/Relation.h"
 #include "index/SymbolID.h"
 #include "support/Logger.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/SourceLocation.h"
if (Roles & static_cast<unsigned>(index::SymbolRole::Definition))
     Result |= RefKind::Definition;
   if (Roles & static_cast<unsigned>(index::SymbolRole::Reference))
     Result |= RefKind::Reference;
   if (Spelled)
     Result |= RefKind::Spelled;
   return Result;
 }
 
-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);
+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::handleMacroOccurrence(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))
+    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

 MATCHER(VisibleOutsideFile, "") {
   return static_cast<bool>(arg.Flags & Symbol::VisibleOutsideFile);
 }
 MATCHER(RefRange, "") {
   const Ref &Pos = ::testing::get<0>(arg);
   const Range &Range = ::testing::get<1>(arg);
   return rangesMatch(Pos.Location, Range);
 }
+MATCHER_P2(OverridenBy, Subject, Object, "") {
+  return arg == Relation{Subject.ID, RelationKind::OverridenBy, Object.ID};
+}
 ::testing::Matcher<const std::vector<Ref> &>
 HaveRanges(const std::vector<Range> Ranges) {
   return ::testing::UnorderedPointwise(RefRange(), Ranges);
 }
 
 class ShouldCollectSymbolTest : public ::testing::Test {
 public:
   void build(llvm::StringRef HeaderCode, llvm::StringRef Code = "") {

 
 TEST_F(SymbolCollectorTest, SpelledReferences) {
   struct {
     llvm::StringRef Header;
     llvm::StringRef Main;
     llvm::StringRef TargetSymbolName;
   } TestCases[] = {
     {
       R"cpp(
         struct Foo;
         #define MACRO Foo
       )cpp",
       R"cpp(
         struct $spelled[[Foo]] {
           $spelled[[Foo]]();
           ~$spelled[[Foo]]();
         };
TEST_F(SymbolCollectorTest, RefsInHeaders) {
   )");
   runSymbolCollector(Header.code(), "");
   EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "Foo").ID,
                                   HaveRanges(Header.ranges("foo")))));
   EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "MACRO").ID,
                                   HaveRanges(Header.ranges("macro")))));
 }
 
-TEST_F(SymbolCollectorTest, Relations) {
+TEST_F(SymbolCollectorTest, BaseOfRelations) {
   std::string Header = R"(
   class Base {};
   class Derived : public Base {};
   )";
   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, OverrideRelationsSimpleInheritance) {
+  std::string Header = R"cpp(
+    class A {
+      virtual void foo();
+    };
+    class B : public A {
+      void foo() override;  // A::foo
+      virtual void bar();
+    };
+    class C : public B {
+      void bar() override;  // B::bar
+    };
+    class D: public C {
+      void foo() override;  // B::foo
+      void bar() override;  // C::bar
+    };
+  )cpp";
+  runSymbolCollector(Header, /*Main=*/"");
+  const Symbol &AFoo = findSymbol(Symbols, "A::foo");
+  const Symbol &BFoo = findSymbol(Symbols, "B::foo");
+  const Symbol &DFoo = findSymbol(Symbols, "D::foo");
+
+  const Symbol &BBar = findSymbol(Symbols, "B::bar");
+  const Symbol &CBar = findSymbol(Symbols, "C::bar");
+  const Symbol &DBar = findSymbol(Symbols, "D::bar");
+
+  std::vector<Relation> Result;
+  for (const Relation &R : Relations)
+    if (R.Predicate == RelationKind::OverridenBy)
+      Result.push_back(R);
+  EXPECT_THAT(Result, UnorderedElementsAre(
+                          OverridenBy(AFoo, BFoo), OverridenBy(BBar, CBar),
+                          OverridenBy(BFoo, DFoo), OverridenBy(CBar, DBar)));
+}
+
+TEST_F(SymbolCollectorTest, OverrideRelationsMultipleInheritance) {
+  std::string Header = R"cpp(
+    class A {
+      virtual void foo();
+    };
+    class B {
+      virtual void bar();
+    };
+    class C : public B {
+      void bar() override;  // B::bar
+      virtual void baz();
+    }
+    class D : public A, C {
+      void foo() override;  // A::foo
+      void bar() override;  // C::bar
+      void baz() override;  // C::baz
+    };
+  )cpp";
+  runSymbolCollector(Header, /*Main=*/"");
+  const Symbol &AFoo = findSymbol(Symbols, "A::foo");
+  const Symbol &BBar = findSymbol(Symbols, "B::bar");
+  const Symbol &CBar = findSymbol(Symbols, "C::bar");
+  const Symbol &CBaz = findSymbol(Symbols, "C::baz");
+  const Symbol &DFoo = findSymbol(Symbols, "D::foo");
+  const Symbol &DBar = findSymbol(Symbols, "D::bar");
+  const Symbol &DBaz = findSymbol(Symbols, "D::baz");
+
+  std::vector<Relation> Result;
+  for (const Relation &R : Relations)
+    if (R.Predicate == RelationKind::OverridenBy)
+      Result.push_back(R);
+  EXPECT_THAT(Result, UnorderedElementsAre(
+                          OverridenBy(BBar, CBar), OverridenBy(AFoo, DFoo),
+                          OverridenBy(CBar, DBar), OverridenBy(CBaz, DBaz)));
+}
+
 TEST_F(SymbolCollectorTest, CountReferences) {
   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;