nridge created this revision.
nridge added reviewers: sammccall, kadircet.
Herald added subscribers: cfe-commits, jdoerfert, arphaman, mgrang, jkorous,
MaskRay, ioeric, ilya-biryukov.
Herald added a project: clang.
This is an early draft of an implementation of type hierarchy subtypes.
There is enough here to pass some basic tests, but the implementation is
incomplete (for example, the index support is in place for MemIndex but not
Dex, and the serialization support for YAML but not RIFF).
My objective at this point is to get some high-level feedback on the addition
of "relations" to the index model and API. If this direction seems reasonable,
I will proceed and fill in the missing pieces of the implementation.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D58880
Files:
clang-tools-extra/clangd/ClangdServer.cpp
clang-tools-extra/clangd/XRefs.cpp
clang-tools-extra/clangd/XRefs.h
clang-tools-extra/clangd/index/Background.cpp
clang-tools-extra/clangd/index/FileIndex.cpp
clang-tools-extra/clangd/index/FileIndex.h
clang-tools-extra/clangd/index/Index.cpp
clang-tools-extra/clangd/index/Index.h
clang-tools-extra/clangd/index/MemIndex.cpp
clang-tools-extra/clangd/index/MemIndex.h
clang-tools-extra/clangd/index/Merge.cpp
clang-tools-extra/clangd/index/Merge.h
clang-tools-extra/clangd/index/Serialization.cpp
clang-tools-extra/clangd/index/Serialization.h
clang-tools-extra/clangd/index/SymbolCollector.cpp
clang-tools-extra/clangd/index/SymbolCollector.h
clang-tools-extra/clangd/index/YAMLSerialization.cpp
clang-tools-extra/clangd/index/dex/Dex.cpp
clang-tools-extra/clangd/index/dex/Dex.h
clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp
clang-tools-extra/unittests/clangd/FileIndexTests.cpp
clang-tools-extra/unittests/clangd/IndexTests.cpp
clang-tools-extra/unittests/clangd/TestTU.cpp
clang-tools-extra/unittests/clangd/XRefsTests.cpp
Index: clang-tools-extra/unittests/clangd/XRefsTests.cpp
===================================================================
--- clang-tools-extra/unittests/clangd/XRefsTests.cpp
+++ clang-tools-extra/unittests/clangd/XRefsTests.cpp
@@ -1761,6 +1761,87 @@
EXPECT_THAT(typeAncestors(Child3), ElementsAre());
}
+SymbolID findSymbolIDByName(llvm::StringRef Name, SymbolIndex *Index) {
+ SymbolID Result;
+ FuzzyFindRequest Request;
+ Request.Query = Name;
+ Request.AnyScope = true;
+ Request.Limit = 1;
+ int ResultCount = 0;
+ Index->fuzzyFind(Request, [&](const Symbol &S) {
+ Result = S.ID;
+ ++ResultCount;
+ });
+ EXPECT_EQ(1, ResultCount);
+ return Result;
+}
+
+std::vector<SymbolID> collectSubtypes(SymbolID Type, SymbolIndex *Index) {
+ std::vector<SymbolID> Result;
+ llvm::errs() << "Querying subtypes of " << Type << "\n";
+ Index->relations(Type, RelationKind::Subtype,
+ [&Result](const SymbolID &ID) { Result.push_back(ID); });
+ return Result;
+}
+
+TEST(Subtypes, SimpleInheritance) {
+ Annotations Source(R"cpp(
+struct Parent {
+ int a;
+};
+
+struct Child1 : Parent {
+ int b;
+};
+
+struct Child2 : Child1 {
+ int c;
+};
+)cpp");
+
+ TestTU TU = TestTU::withCode(Source.code());
+ auto Index = TU.index();
+
+ SymbolID Parent = findSymbolIDByName("Parent", Index.get());
+ SymbolID Child1 = findSymbolIDByName("Child1", Index.get());
+ SymbolID Child2 = findSymbolIDByName("Child2", Index.get());
+
+ EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(Child1));
+ EXPECT_THAT(collectSubtypes(Child1, Index.get()), ElementsAre(Child2));
+}
+
+TEST(Subtypes, MultipleInheritance) {
+ Annotations Source(R"cpp(
+struct Parent1 {
+ int a;
+};
+
+struct Parent2 {
+ int b;
+};
+
+struct Parent3 : Parent2 {
+ int c;
+};
+
+struct Child : Parent1, Parent3 {
+ int d;
+};
+)cpp");
+
+ TestTU TU = TestTU::withCode(Source.code());
+ auto Index = TU.index();
+
+ SymbolID Parent1 = findSymbolIDByName("Parent1", Index.get());
+ SymbolID Parent2 = findSymbolIDByName("Parent2", Index.get());
+ SymbolID Parent3 = findSymbolIDByName("Parent3", Index.get());
+ SymbolID Child = findSymbolIDByName("Child", Index.get());
+
+ EXPECT_THAT(collectSubtypes(Parent1, Index.get()), ElementsAre(Child));
+ EXPECT_THAT(collectSubtypes(Parent2, Index.get()), ElementsAre(Parent3));
+ EXPECT_THAT(collectSubtypes(Parent3, Index.get()), ElementsAre(Child));
+}
+
// Parts of getTypeHierarchy() are tested in more detail by the
// FindRecordTypeAt.* and TypeAncestor.* tests above. This test exercises the
// entire operation.
Index: clang-tools-extra/unittests/clangd/TestTU.cpp
===================================================================
--- clang-tools-extra/unittests/clangd/TestTU.cpp
+++ clang-tools-extra/unittests/clangd/TestTU.cpp
@@ -65,7 +65,9 @@
std::unique_ptr<SymbolIndex> TestTU::index() const {
auto AST = build();
- auto Idx = llvm::make_unique<FileIndex>(/*UseDex=*/true);
+ // UseDex is temporarily set to false so we can test subtypes support
+ // before implementing it in Dex.
+ auto Idx = llvm::make_unique<FileIndex>(/*UseDex=*/false);
Idx->updatePreamble(Filename, AST.getASTContext(), AST.getPreprocessorPtr(),
AST.getCanonicalIncludes());
Idx->updateMain(Filename, AST);
Index: clang-tools-extra/unittests/clangd/IndexTests.cpp
===================================================================
--- clang-tools-extra/unittests/clangd/IndexTests.cpp
+++ clang-tools-extra/unittests/clangd/IndexTests.cpp
@@ -77,8 +77,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.
@@ -90,12 +91,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;
@@ -110,7 +112,7 @@
TEST(MemIndexTest, FuzzyMatch) {
auto I = MemIndex::build(
generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
- RefSlab());
+ RefSlab(), RelationSlab());
FuzzyFindRequest Req;
Req.Query = "lol";
Req.AnyScope = true;
@@ -120,8 +122,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;
@@ -129,8 +131,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 = {""};
@@ -139,7 +141,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::"};
@@ -148,7 +151,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::"};
@@ -156,7 +160,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::"};
@@ -164,7 +169,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::"};
@@ -172,7 +178,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"));
@@ -182,8 +189,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"));
@@ -197,8 +206,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/unittests/clangd/FileIndexTests.cpp
===================================================================
--- clang-tools-extra/unittests/clangd/FileIndexTests.cpp
+++ clang-tools-extra/unittests/clangd/FileIndexTests.cpp
@@ -82,7 +82,7 @@
FileSymbols FS;
EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""), IsEmpty());
- FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"));
+ FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc"), nullptr);
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 +91,8 @@
TEST(FileSymbolsTest, Overlap) {
FileSymbols FS;
- FS.update("f1", numSlab(1, 3), nullptr);
- FS.update("f2", numSlab(3, 5), nullptr);
+ FS.update("f1", numSlab(1, 3), nullptr, nullptr);
+ FS.update("f2", numSlab(3, 5), nullptr, nullptr);
for (auto Type : {IndexType::Light, IndexType::Heavy})
EXPECT_THAT(runFuzzyFind(*FS.buildIndex(Type), ""),
UnorderedElementsAre(QName("1"), QName("2"), QName("3"),
@@ -111,8 +111,8 @@
auto X2 = symbol("x");
X2.Definition.FileURI = "file:///x2";
- FS.update("f1", OneSymboSlab(X1), nullptr);
- FS.update("f2", OneSymboSlab(X2), nullptr);
+ FS.update("f1", OneSymboSlab(X1), nullptr, nullptr);
+ FS.update("f2", OneSymboSlab(X2), nullptr, nullptr);
for (auto Type : {IndexType::Light, IndexType::Heavy})
EXPECT_THAT(
runFuzzyFind(*FS.buildIndex(Type, DuplicateHandling::Merge), "x"),
@@ -124,14 +124,14 @@
FileSymbols FS;
SymbolID ID("1");
- FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"));
+ FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc"), nullptr);
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);
+ FS.update("f1", nullptr, nullptr, nullptr);
auto Empty = FS.buildIndex(IndexType::Light);
EXPECT_THAT(runFuzzyFind(*Empty, ""), IsEmpty());
EXPECT_THAT(getRefs(*Empty, ID), ElementsAre());
Index: clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp
===================================================================
--- clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp
+++ clang-tools-extra/unittests/clangd/DiagnosticsTests.cpp
@@ -71,7 +71,6 @@
return true;
}
-
// Helper function to make tests shorter.
Position pos(int line, int character) {
Position Res;
@@ -316,7 +315,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) {
@@ -372,7 +371,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(),
@@ -589,4 +589,3 @@
} // namespace
} // namespace clangd
} // namespace clang
-
Index: clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
===================================================================
--- clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
+++ clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
@@ -85,7 +85,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,
@@ -999,6 +999,9 @@
void refs(const RefsRequest &,
llvm::function_ref<void(const Ref &)>) const override {}
+ void relations(const SymbolID &, RelationKind,
+ 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; }
Index: clang-tools-extra/clangd/index/dex/Dex.h
===================================================================
--- clang-tools-extra/clangd/index/dex/Dex.h
+++ clang-tools-extra/clangd/index/dex/Dex.h
@@ -72,6 +72,10 @@
void refs(const RefsRequest &Req,
llvm::function_ref<void(const Ref &)> Callback) const override;
+ void
+ relations(const SymbolID &ID, RelationKind Kind,
+ llvm::function_ref<void(const SymbolID &)> Callback) const override;
+
size_t estimateMemoryUsage() const override;
private:
Index: clang-tools-extra/clangd/index/dex/Dex.cpp
===================================================================
--- clang-tools-extra/clangd/index/dex/Dex.cpp
+++ clang-tools-extra/clangd/index/dex/Dex.cpp
@@ -259,6 +259,11 @@
}
}
+void Dex::relations(const SymbolID &ID, RelationKind Kind,
+ llvm::function_ref<void(const SymbolID &)> Callback) const {
+ // TODO: Implement.
+}
+
size_t Dex::estimateMemoryUsage() const {
size_t Bytes = Symbols.size() * sizeof(const Symbol *);
Bytes += SymbolQuality.size() * sizeof(float);
Index: clang-tools-extra/clangd/index/YAMLSerialization.cpp
===================================================================
--- clang-tools-extra/clangd/index/YAMLSerialization.cpp
+++ clang-tools-extra/clangd/index/YAMLSerialization.cpp
@@ -29,14 +29,18 @@
LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Symbol::IncludeHeaderWithReferences)
LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Ref)
+LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::SymbolID)
namespace {
using RefBundle =
std::pair<clang::clangd::SymbolID, std::vector<clang::clangd::Ref>>;
+using RelationBundle =
+ std::pair<clang::clangd::RelationKey, std::vector<clang::clangd::SymbolID>>;
// This is a pale imitation of std::variant<Symbol, RefBundle>
struct VariantEntry {
llvm::Optional<clang::clangd::Symbol> Symbol;
llvm::Optional<RefBundle> Refs;
+ llvm::Optional<RelationBundle> Relations;
};
// A class helps YAML to serialize the 32-bit encoded position (Line&Column),
// as YAMLIO can't directly map bitfields.
@@ -51,6 +55,7 @@
using clang::clangd::Ref;
using clang::clangd::RefKind;
+using clang::clangd::RelationKind;
using clang::clangd::Symbol;
using clang::clangd::SymbolID;
using clang::clangd::SymbolLocation;
@@ -271,6 +276,34 @@
}
};
+struct NormalizedRelationKind {
+ NormalizedRelationKind(IO &) {}
+ NormalizedRelationKind(IO &, RelationKind O) {
+ Kind = static_cast<uint8_t>(O);
+ }
+
+ RelationKind denormalize(IO &) { return static_cast<RelationKind>(Kind); }
+
+ uint8_t Kind = 0;
+};
+
+template <> struct MappingTraits<SymbolID> {
+ static void mapping(IO &IO, SymbolID &ID) {
+ MappingNormalization<NormalizedSymbolID, SymbolID> NSymbolID(IO, ID);
+ IO.mapRequired("ID", NSymbolID->HexString);
+ }
+};
+
+template <> struct MappingTraits<RelationBundle> {
+ static void mapping(IO &IO, RelationBundle &Relations) {
+ MappingNormalization<NormalizedRelationKind, RelationKind> NKind(
+ IO, Relations.first.Kind);
+ IO.mapRequired("Symbol", Relations.first.Symbol);
+ IO.mapRequired("Kind", NKind->Kind);
+ IO.mapRequired("Relations", Relations.second);
+ }
+};
+
template <> struct MappingTraits<VariantEntry> {
static void mapping(IO &IO, VariantEntry &Variant) {
if (IO.mapTag("!Symbol", Variant.Symbol.hasValue())) {
@@ -281,6 +314,10 @@
if (!IO.outputting())
Variant.Refs.emplace();
MappingTraits<RefBundle>::mapping(IO, *Variant.Refs);
+ } else if (IO.mapTag("!Relations", Variant.Relations.hasValue())) {
+ if (!IO.outputting())
+ Variant.Relations.emplace();
+ MappingTraits<RelationBundle>::mapping(IO, *Variant.Relations);
}
}
};
@@ -304,11 +341,18 @@
Entry.Refs = Sym;
Yout << Entry;
}
+ if (O.Relations)
+ for (auto &E : *O.Relations) {
+ VariantEntry Entry;
+ Entry.Relations = E;
+ Yout << Entry;
+ }
}
llvm::Expected<IndexFileIn> readYAML(llvm::StringRef Data) {
SymbolSlab::Builder Symbols;
RefSlab::Builder Refs;
+ RelationSlab::Builder Relations;
llvm::BumpPtrAllocator
Arena; // store the underlying data of Position::FileURI.
llvm::UniqueStringSaver Strings(Arena);
@@ -325,12 +369,16 @@
if (Variant.Refs)
for (const auto &Ref : Variant.Refs->second)
Refs.insert(Variant.Refs->first, Ref);
+ if (Variant.Relations)
+ for (const auto &Relation : Variant.Relations->second)
+ Relations.insert(Variant.Relations->first, Relation);
Yin.nextDocument();
}
IndexFileIn Result;
Result.Symbols.emplace(std::move(Symbols).build());
Result.Refs.emplace(std::move(Refs).build());
+ Result.Relations.emplace(std::move(Relations).build());
return std::move(Result);
}
Index: clang-tools-extra/clangd/index/SymbolCollector.h
===================================================================
--- clang-tools-extra/clangd/index/SymbolCollector.h
+++ clang-tools-extra/clangd/index/SymbolCollector.h
@@ -108,11 +108,13 @@
SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
RefSlab takeRefs() { return std::move(Refs).build(); }
+ RelationSlab takeRelations() { return std::move(Relations).build(); }
void finish() override;
private:
- const Symbol *addDeclaration(const NamedDecl &, SymbolID, bool IsMainFileSymbol);
+ const Symbol *addDeclaration(const NamedDecl &, SymbolID,
+ bool IsMainFileSymbol);
void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
// All Symbols collected from the AST.
@@ -121,6 +123,8 @@
// Only symbols declared in preamble (from #include) and referenced from the
// main file will be included.
RefSlab::Builder Refs;
+ // All relations collected from the AST.
+ RelationSlab::Builder Relations;
ASTContext *ASTCtx;
std::shared_ptr<Preprocessor> PP;
std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
Index: clang-tools-extra/clangd/index/SymbolCollector.cpp
===================================================================
--- clang-tools-extra/clangd/index/SymbolCollector.cpp
+++ clang-tools-extra/clangd/index/SymbolCollector.cpp
@@ -14,6 +14,7 @@
#include "Logger.h"
#include "SourceCode.h"
#include "URI.h"
+#include "XRefs.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclBase.h"
#include "clang/AST/DeclCXX.h"
@@ -201,7 +202,7 @@
// the first seen declaration as canonical declaration is not a good enough
// heuristic.
bool isPreferredDeclaration(const NamedDecl &ND, index::SymbolRoleSet Roles) {
- const auto& SM = ND.getASTContext().getSourceManager();
+ const auto &SM = ND.getASTContext().getSourceManager();
return (Roles & static_cast<unsigned>(index::SymbolRole::Definition)) &&
isa<TagDecl>(&ND) &&
!SM.isWrittenInMainFile(SM.getExpansionLoc(ND.getLocation()));
@@ -323,8 +324,8 @@
// ND is the canonical (i.e. first) declaration. If it's in the main file,
// then no public declaration was visible, so assume it's main-file only.
- bool IsMainFileOnly = SM.isWrittenInMainFile(SM.getExpansionLoc(
- ND->getBeginLoc()));
+ bool IsMainFileOnly =
+ SM.isWrittenInMainFile(SM.getExpansionLoc(ND->getBeginLoc()));
if (!shouldCollectSymbol(*ND, *ASTCtx, Opts, IsMainFileOnly))
return true;
// Do not store references to main-file symbols.
@@ -513,8 +514,7 @@
FilesToIndexCache.clear();
}
-const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
- SymbolID ID,
+const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND, SymbolID ID,
bool IsMainFileOnly) {
auto &Ctx = ND.getASTContext();
auto &SM = Ctx.getSourceManager();
@@ -612,6 +612,19 @@
getTokenLocation(Loc, SM, Opts, ASTCtx->getLangOpts(), FileURI))
S.Definition = *DefLoc;
Symbols.insert(S);
+
+ // Store subtype relations.
+ const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(&ND);
+ if (!RD)
+ return;
+ for (const Decl *Ancestor : typeAncestors(RD)) {
+ if (auto ID = getSymbolID(Ancestor)) {
+ // We are a subtype to each of our ancestors.
+ llvm::errs() << "Recording subtype relationship from " << *ID << " to "
+ << S.ID << "\n";
+ Relations.insert({*ID, RelationKind::Subtype}, S.ID);
+ }
+ }
}
} // namespace clangd
Index: clang-tools-extra/clangd/index/Serialization.h
===================================================================
--- clang-tools-extra/clangd/index/Serialization.h
+++ clang-tools-extra/clangd/index/Serialization.h
@@ -39,6 +39,7 @@
struct IndexFileIn {
llvm::Optional<SymbolSlab> Symbols;
llvm::Optional<RefSlab> Refs;
+ llvm::Optional<RelationSlab> Relations;
// Keys are URIs of the source files.
llvm::Optional<IncludeGraph> Sources;
};
@@ -49,6 +50,7 @@
struct IndexFileOut {
const SymbolSlab *Symbols = nullptr;
const RefSlab *Refs = nullptr;
+ const RelationSlab *Relations = nullptr;
// Keys are URIs of the source files.
const IncludeGraph *Sources = nullptr;
// TODO: Support serializing Dex posting lists.
@@ -57,7 +59,8 @@
IndexFileOut() = default;
IndexFileOut(const IndexFileIn &I)
: Symbols(I.Symbols ? I.Symbols.getPointer() : nullptr),
- Refs(I.Refs ? I.Refs.getPointer() : nullptr) {}
+ Refs(I.Refs ? I.Refs.getPointer() : nullptr),
+ Relations(I.Relations ? I.Relations.getPointer() : nullptr) {}
};
// Serializes an index file.
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const IndexFileOut &O);
Index: clang-tools-extra/clangd/index/Serialization.cpp
===================================================================
--- clang-tools-extra/clangd/index/Serialization.cpp
+++ clang-tools-extra/clangd/index/Serialization.cpp
@@ -558,6 +558,7 @@
SymbolSlab Symbols;
RefSlab Refs;
+ RelationSlab Relations; // TODO: Populate.
{
trace::Span Tracer("ParseIndex");
if (auto I = readIndexFile(Buffer->get()->getBuffer())) {
@@ -565,6 +566,8 @@
Symbols = std::move(*I->Symbols);
if (I->Refs)
Refs = std::move(*I->Refs);
+ if (I->Relations)
+ Relations = std::move(*I->Relations);
} else {
llvm::errs() << "Bad Index: " << llvm::toString(I.takeError()) << "\n";
return nullptr;
@@ -573,15 +576,18 @@
size_t NumSym = Symbols.size();
size_t NumRefs = Refs.numRefs();
+ size_t NumRelations = Relations.numRelations();
trace::Span Tracer("BuildIndex");
auto Index = UseDex ? dex::Dex::build(std::move(Symbols), std::move(Refs))
- : MemIndex::build(std::move(Symbols), std::move(Refs));
+ : 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",
+ " - number of refs: {4}\n"
+ " - numnber of relations: {5}",
UseDex ? "Dex" : "MemIndex", SymbolFilename,
- Index->estimateMemoryUsage(), NumSym, NumRefs);
+ Index->estimateMemoryUsage(), NumSym, NumRefs, NumRelations);
return Index;
}
Index: clang-tools-extra/clangd/index/Merge.h
===================================================================
--- clang-tools-extra/clangd/index/Merge.h
+++ clang-tools-extra/clangd/index/Merge.h
@@ -42,6 +42,8 @@
llvm::function_ref<void(const Symbol &)>) const override;
void refs(const RefsRequest &,
llvm::function_ref<void(const Ref &)>) const override;
+ void relations(const SymbolID &, RelationKind,
+ llvm::function_ref<void(const SymbolID &)>) const override;
size_t estimateMemoryUsage() const override {
return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
}
Index: clang-tools-extra/clangd/index/Merge.cpp
===================================================================
--- clang-tools-extra/clangd/index/Merge.cpp
+++ clang-tools-extra/clangd/index/Merge.cpp
@@ -118,6 +118,14 @@
});
}
+void MergedIndex::relations(
+ const SymbolID &ID, RelationKind Kind,
+ llvm::function_ref<void(const SymbolID &)> Callback) const {
+ // TODO: Implement properly.
+ Static->relations(ID, Kind, Callback);
+ Dynamic->relations(ID, Kind, Callback);
+}
+
// 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/clangd/index/MemIndex.h
===================================================================
--- clang-tools-extra/clangd/index/MemIndex.h
+++ clang-tools-extra/clangd/index/MemIndex.h
@@ -20,26 +20,31 @@
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 std::pair<RelationKey, llvm::ArrayRef<SymbolID>> &R : Relations)
+ this->Relations.try_emplace(R.first, R.second.begin(), R.second.end());
}
// 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 +56,10 @@
void refs(const RefsRequest &Req,
llvm::function_ref<void(const Ref &)> Callback) const override;
+ void
+ relations(const SymbolID &ID, RelationKind Kind,
+ llvm::function_ref<void(const SymbolID &)> Callback) const override;
+
size_t estimateMemoryUsage() const override;
private:
@@ -58,6 +67,7 @@
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;
+ llvm::DenseMap<RelationKey, llvm::ArrayRef<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/clangd/index/MemIndex.cpp
===================================================================
--- clang-tools-extra/clangd/index/MemIndex.cpp
+++ clang-tools-extra/clangd/index/MemIndex.cpp
@@ -15,11 +15,14 @@
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),
+ auto Data =
+ std::make_tuple(std::move(Slab), std::move(Refs), std::move(Relations));
+ return llvm::make_unique<MemIndex>(std::get<0>(Data), std::get<1>(Data),
+ std::get<2>(Data), std::move(Data),
BackingDataSize);
}
@@ -83,6 +86,17 @@
}
}
+void MemIndex::relations(
+ const SymbolID &ID, RelationKind Kind,
+ llvm::function_ref<void(const SymbolID &)> Callback) const {
+ auto Rels = Relations.find({ID, Kind});
+ if (Rels == Relations.end())
+ return;
+ for (const auto &S : Rels->second) {
+ Callback(S);
+ }
+}
+
size_t MemIndex::estimateMemoryUsage() const {
return Index.getMemorySize() + Refs.getMemorySize() + BackingDataSize;
}
Index: clang-tools-extra/clangd/index/Index.h
===================================================================
--- clang-tools-extra/clangd/index/Index.h
+++ clang-tools-extra/clangd/index/Index.h
@@ -43,9 +43,7 @@
void setColumn(uint32_t Column);
uint32_t column() const { return Column; }
- bool hasOverflow() const {
- return Line >= MaxLine || Column >= MaxColumn;
- }
+ bool hasOverflow() const { return Line >= MaxLine || Column >= MaxColumn; }
static constexpr uint32_t MaxLine = (1 << 20) - 1;
static constexpr uint32_t MaxColumn = (1 << 12) - 1;
@@ -247,11 +245,13 @@
SymbolFlag Flags = SymbolFlag::None;
/// FIXME: also add deprecation message and fixit?
};
-inline Symbol::SymbolFlag operator|(Symbol::SymbolFlag A, Symbol::SymbolFlag B) {
+inline Symbol::SymbolFlag operator|(Symbol::SymbolFlag A,
+ Symbol::SymbolFlag B) {
return static_cast<Symbol::SymbolFlag>(static_cast<uint8_t>(A) |
static_cast<uint8_t>(B));
}
-inline Symbol::SymbolFlag &operator|=(Symbol::SymbolFlag &A, Symbol::SymbolFlag B) {
+inline Symbol::SymbolFlag &operator|=(Symbol::SymbolFlag &A,
+ Symbol::SymbolFlag B) {
return A = A | B;
}
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S);
@@ -432,6 +432,71 @@
size_t NumRefs = 0;
};
+enum class RelationKind { Subtype };
+
+struct RelationKey {
+ SymbolID Symbol;
+ RelationKind Kind;
+
+ bool operator==(const RelationKey &Other) const {
+ return Symbol == Other.Symbol && Kind == Other.Kind;
+ }
+
+private:
+ friend llvm::hash_code hash_value(const RelationKey &Key) {
+ return llvm::hash_combine(Key.Symbol, static_cast<int>(Key.Kind));
+ }
+};
+
+class RelationSlab {
+public:
+ using value_type = std::pair<RelationKey, llvm::ArrayRef<SymbolID>>;
+ using const_iterator = std::vector<value_type>::const_iterator;
+ using iterator = const_iterator;
+
+ RelationSlab() = default;
+ RelationSlab(RelationSlab &&Slab) = default;
+ RelationSlab &operator=(RelationSlab &&RHS) = default;
+
+ const_iterator begin() const { return Relations.begin(); }
+ const_iterator end() const { return Relations.end(); }
+ size_t size() const { return Relations.size(); }
+ size_t numRelations() const { return NumRelations; }
+ bool empty() const { return Relations.empty(); }
+
+ size_t bytes() const {
+ return sizeof(*this) + Arena.getTotalMemory() +
+ sizeof(value_type) * Relations.size();
+ }
+
+ // RelationSlab::Builder is a mutable container that can 'freeze' to
+ // RelationSlab.
+ class Builder {
+ public:
+ Builder() {}
+ // Adds a relation to the slab. Deep copy: Strings will be owned by the
+ // slab.
+ void insert(const RelationKey &Key, const SymbolID &S);
+ // Consumes the builder to finalize the slab.
+ RelationSlab build() &&;
+
+ private:
+ llvm::BumpPtrAllocator Arena;
+ llvm::DenseMap<RelationKey, std::vector<SymbolID>> Relations;
+ };
+
+private:
+ RelationSlab(std::vector<value_type> Relations, llvm::BumpPtrAllocator Arena,
+ size_t NumRelations)
+ : Arena(std::move(Arena)), Relations(std::move(Relations)),
+ NumRelations(NumRelations) {}
+
+ llvm::BumpPtrAllocator Arena;
+ std::vector<value_type> Relations;
+ // Number of all relations.
+ size_t NumRelations = 0;
+};
+
struct FuzzyFindRequest {
/// \brief A query string for the fuzzy find. This is matched against symbols'
/// un-qualified identifiers and should not contain qualifiers like "::".
@@ -512,6 +577,10 @@
virtual void refs(const RefsRequest &Req,
llvm::function_ref<void(const Ref &)> Callback) const = 0;
+ virtual void
+ relations(const SymbolID &ID, RelationKind Kind,
+ llvm::function_ref<void(const SymbolID &)> Callback) const = 0;
+
/// Returns estimated size of index (in bytes).
// FIXME(kbobyrev): Currently, this only returns the size of index itself
// excluding the size of actual symbol slab index refers to. We should include
@@ -535,6 +604,9 @@
llvm::function_ref<void(const Symbol &)>) const override;
void refs(const RefsRequest &,
llvm::function_ref<void(const Ref &)>) const override;
+ void relations(const SymbolID &, RelationKind,
+ llvm::function_ref<void(const SymbolID &)>) const override;
+
size_t estimateMemoryUsage() const override;
private:
@@ -546,4 +618,30 @@
} // namespace clangd
} // namespace clang
+namespace llvm {
+
+// Support RelationKeys as DenseMap keys.
+template <> struct DenseMapInfo<clang::clangd::RelationKey> {
+ static inline clang::clangd::RelationKey getEmptyKey() {
+ return {DenseMapInfo<clang::clangd::SymbolID>::getEmptyKey(),
+ clang::clangd::RelationKind::Subtype};
+ }
+
+ static inline clang::clangd::RelationKey getTombstoneKey() {
+ return {DenseMapInfo<clang::clangd::SymbolID>::getTombstoneKey(),
+ clang::clangd::RelationKind::Subtype};
+ }
+
+ static unsigned getHashValue(const clang::clangd::RelationKey &Key) {
+ return hash_value(Key);
+ }
+
+ static bool isEqual(const clang::clangd::RelationKey &LHS,
+ const clang::clangd::RelationKey &RHS) {
+ return LHS == RHS;
+ }
+};
+
+} // namespace llvm
+
#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
Index: clang-tools-extra/clangd/index/Index.cpp
===================================================================
--- clang-tools-extra/clangd/index/Index.cpp
+++ clang-tools-extra/clangd/index/Index.cpp
@@ -158,6 +158,28 @@
return RefSlab(std::move(Result), std::move(Arena), NumRefs);
}
+void RelationSlab::Builder::insert(const RelationKey &Key, const SymbolID &S) {
+ Relations[Key].push_back(S);
+}
+
+RelationSlab RelationSlab::Builder::build() && {
+ // Reallocate relations on the arena to reduce waste and indirections when
+ // reading.
+ std::vector<std::pair<RelationKey, llvm::ArrayRef<SymbolID>>> Result;
+ Result.reserve(Relations.size());
+ size_t NumRelations = 0;
+ for (auto &Entry : Relations) {
+ auto &Rels = Entry.second;
+
+ NumRelations += Rels.size();
+ auto *Array = Arena.Allocate<SymbolID>(Rels.size());
+ std::uninitialized_copy(Rels.begin(), Rels.end(), Array);
+ Result.emplace_back(Entry.first,
+ llvm::ArrayRef<SymbolID>(Array, Rels.size()));
+ }
+ return RelationSlab(std::move(Result), std::move(Arena), NumRelations);
+}
+
void SwapIndex::reset(std::unique_ptr<SymbolIndex> Index) {
// Keep the old index alive, so we don't destroy it under lock (may be slow).
std::shared_ptr<SymbolIndex> Pin;
@@ -210,6 +232,11 @@
llvm::function_ref<void(const Ref &)> CB) const {
return snapshot()->refs(R, CB);
}
+void SwapIndex::relations(const SymbolID &ID, RelationKind Kind,
+ llvm::function_ref<void(const SymbolID &)> CB) const {
+ return snapshot()->relations(ID, Kind, CB);
+}
+
size_t SwapIndex::estimateMemoryUsage() const {
return snapshot()->estimateMemoryUsage();
}
Index: clang-tools-extra/clangd/index/FileIndex.h
===================================================================
--- clang-tools-extra/clangd/index/FileIndex.h
+++ clang-tools-extra/clangd/index/FileIndex.h
@@ -60,7 +60,8 @@
/// Updates all symbols and refs in a file.
/// If either is nullptr, corresponding data for \p Path will be removed.
void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
- std::unique_ptr<RefSlab> Refs);
+ std::unique_ptr<RefSlab> Refs,
+ std::unique_ptr<RelationSlab> Relations);
// The index keeps the symbols alive.
std::unique_ptr<SymbolIndex>
@@ -74,6 +75,8 @@
llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSymbols;
/// Stores the latest ref snapshots for all active files.
llvm::StringMap<std::shared_ptr<RefSlab>> 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.
@@ -119,10 +122,12 @@
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.
Index: clang-tools-extra/clangd/index/FileIndex.cpp
===================================================================
--- clang-tools-extra/clangd/index/FileIndex.cpp
+++ clang-tools-extra/clangd/index/FileIndex.cpp
@@ -27,10 +27,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;
@@ -64,15 +64,18 @@
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} symbols, {8} relations, {9} 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.numRelations(),
+ 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);
@@ -83,13 +86,13 @@
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) {
+ std::unique_ptr<RefSlab> Refs,
+ std::unique_ptr<RelationSlab> Relations) {
std::lock_guard<std::mutex> Lock(Mutex);
if (!Symbols)
FileToSymbols.erase(Path);
@@ -99,18 +102,25 @@
FileToRefs.erase(Path);
else
FileToRefs[Path] = std::move(Refs);
+ 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::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);
+ for (const auto &FileAndRelations : FileToRelations)
+ RelationSlabs.push_back(FileAndRelations.second);
}
std::vector<const Symbol *> AllSymbols;
std::vector<Symbol> SymsStorage;
@@ -166,20 +176,51 @@
}
}
+ std::vector<SymbolID>
+ RelationsStorage; // Continguous ranges for each RelationKey.
+ llvm::DenseMap<RelationKey, llvm::ArrayRef<SymbolID>> AllRelations;
+ {
+ llvm::DenseMap<RelationKey, llvm::SmallVector<SymbolID, 4>> MergedRelations;
+ size_t Count = 0;
+ for (const auto &RelationSlab : RelationSlabs) {
+ for (const auto &E : *RelationSlab) {
+ MergedRelations[E.first].append(E.second.begin(), E.second.end());
+ Count += E.second.size();
+ }
+ }
+ RelationsStorage.reserve(Count);
+ AllRelations.reserve(MergedRelations.size());
+ for (auto &E : MergedRelations) {
+ auto &Relations = E.second;
+ // Sorting isn't required, but yields more stable results over rebuilds.
+ llvm::sort(Relations);
+ llvm::copy(Relations, back_inserter(RelationsStorage));
+ AllRelations.try_emplace(
+ E.first,
+ llvm::ArrayRef<SymbolID>(
+ &RelationsStorage[RelationsStorage.size() - Relations.size()],
+ Relations.size()));
+ }
+ }
+
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)),
+ std::move(RelationSlabs), std::move(RefsStorage),
+ std::move(SymsStorage), std::move(RelationsStorage)),
StorageSize);
case IndexType::Heavy:
return llvm::make_unique<dex::Dex>(
@@ -200,9 +241,9 @@
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>());
+ PreambleSymbols.update(
+ Path, llvm::make_unique<SymbolSlab>(std::move(Symbols)),
+ llvm::make_unique<RefSlab>(), llvm::make_unique<RelationSlab>());
PreambleIndex.reset(
PreambleSymbols.buildIndex(UseDex ? IndexType::Heavy : IndexType::Light,
DuplicateHandling::PickOne));
@@ -211,8 +252,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))));
MainFileIndex.reset(
MainFileSymbols.buildIndex(IndexType::Light, DuplicateHandling::PickOne));
}
Index: clang-tools-extra/clangd/index/Background.cpp
===================================================================
--- clang-tools-extra/clangd/index/Background.cpp
+++ clang-tools-extra/clangd/index/Background.cpp
@@ -316,12 +316,14 @@
llvm::StringRef Path = FileIt.getKey();
SymbolSlab::Builder Syms;
RefSlab::Builder Refs;
+ RelationSlab::Builder Relations; // TODO: Populate.
for (const auto *S : FileIt.second.Symbols)
Syms.insert(*S);
for (const auto *R : FileIt.second.Refs)
Refs.insert(RefToIDs[R], *R);
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
@@ -330,6 +332,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))
@@ -347,7 +350,8 @@
// 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));
}
}
}
@@ -557,8 +561,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));
+ IndexedSymbols.update(SI.AbsolutePath, std::move(SS), std::move(RS),
+ std::move(RelS));
}
}
Index: clang-tools-extra/clangd/XRefs.h
===================================================================
--- clang-tools-extra/clangd/XRefs.h
+++ clang-tools-extra/clangd/XRefs.h
@@ -67,7 +67,8 @@
/// Get type hierarchy information at \p Pos.
llvm::Optional<TypeHierarchyItem>
getTypeHierarchy(ParsedAST &AST, Position Pos, int Resolve,
- llvm::Optional<TypeHierarchyDirection> Direction);
+ llvm::Optional<TypeHierarchyDirection> Direction,
+ const SymbolIndex *Index = nullptr);
/// Convert a a URI (such as that returned by toURI()) into a form suitable
/// for use in protocol replies (e.g. Location.uri, DocumentSymbol.uri).
Index: clang-tools-extra/clangd/XRefs.cpp
===================================================================
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -882,8 +882,67 @@
}
static Optional<TypeHierarchyItem>
+symbolIDToTypeHierarchyItem(const SymbolID &ID, const SymbolIndex *Index) {
+ LookupRequest Request;
+ Request.IDs.insert(ID);
+ Optional<TypeHierarchyItem> Result;
+ Index->lookup(Request, [&Result](const Symbol &S) {
+ TypeHierarchyItem THI;
+ THI.name = S.Name;
+ THI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
+ THI.deprecated = (S.Flags & Symbol::Deprecated);
+ Position Start, End;
+ auto &CD = S.Definition ? S.Definition : S.CanonicalDeclaration;
+ Start.line = CD.Start.line();
+ Start.character = CD.Start.column();
+ End.line = CD.End.line();
+ End.character = CD.End.column();
+ // TODO: How to get entire range like in declToTypeHierarchyItem()?
+ THI.range = {Start, End};
+ THI.selectionRange = {Start, End};
+ // TODO: Reuse code between here and getWorkspaceSymbols().
+ auto Uri = URI::parse(CD.FileURI);
+ if (!Uri) {
+ log("Type hierarchy: Could not parse URI '{0}' for symbol '{1}'.",
+ CD.FileURI, S.Name);
+ return;
+ }
+ // TODO: Pass in ClangdServer::WorkspaceRoot as a HintPath.
+ StringRef HintPath;
+ auto Path = URI::resolve(*Uri, HintPath);
+ if (!Path) {
+ log("Type hierarchy: Could not resolve path for URI '{0}' for symbol "
+ "'{1}'.",
+ Uri->toString(), S.Name);
+ return;
+ }
+ THI.uri = URIForFile::canonicalize(*Path, HintPath);
+
+ Result = std::move(THI);
+ });
+ return Result;
+}
+
+static void fillSubTypes(const SymbolID &ID,
+ std::vector<TypeHierarchyItem> &SubTypes,
+ const SymbolIndex *Index, int Levels) {
+ Index->relations(ID, RelationKind::Subtype,
+ [Index, Levels, &SubTypes](const SymbolID &Sub) {
+ if (Optional<TypeHierarchyItem> ChildSym =
+ symbolIDToTypeHierarchyItem(Sub, Index)) {
+ if (Levels > 1) {
+ ChildSym->children.emplace();
+ fillSubTypes(Sub, *ChildSym->children, Index,
+ Levels - 1);
+ }
+ SubTypes.emplace_back(std::move(*ChildSym));
+ }
+ });
+}
+
+static Optional<TypeHierarchyItem>
getTypeHierarchy(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx, int Levels,
- TypeHierarchyDirection Direction) {
+ TypeHierarchyDirection Direction, const SymbolIndex *Index) {
Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(ASTCtx, CXXRD);
if (!Result || Levels <= 0)
return Result;
@@ -895,7 +954,7 @@
for (const CXXRecordDecl *ParentDecl : typeAncestors(&CXXRD)) {
if (Optional<TypeHierarchyItem> ParentSym =
getTypeHierarchy(*ParentDecl, ASTCtx, Levels - 1,
- TypeHierarchyDirection::Parents)) {
+ TypeHierarchyDirection::Parents, Index)) {
Result->parents->emplace_back(std::move(*ParentSym));
}
}
@@ -905,7 +964,11 @@
Direction == TypeHierarchyDirection::Both) {
Result->children.emplace();
- // TODO: Populate subtypes.
+ if (Index) {
+ if (Optional<SymbolID> ID = getSymbolID(&CXXRD)) {
+ fillSubTypes(*ID, *Result->children, Index, Levels);
+ }
+ }
}
return Result;
@@ -972,7 +1035,8 @@
llvm::Optional<TypeHierarchyItem>
getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
- llvm::Optional<TypeHierarchyDirection> Direction) {
+ llvm::Optional<TypeHierarchyDirection> Direction,
+ const SymbolIndex *Index) {
const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
if (!CXXRD)
return llvm::None;
@@ -980,7 +1044,7 @@
TypeHierarchyDirection ResolveDirection =
Direction.getValueOr(TypeHierarchyDirection::Parents);
return getTypeHierarchy(*CXXRD, AST.getASTContext(), ResolveLevels,
- ResolveDirection);
+ ResolveDirection, Index);
}
} // namespace clangd
Index: clang-tools-extra/clangd/ClangdServer.cpp
===================================================================
--- clang-tools-extra/clangd/ClangdServer.cpp
+++ clang-tools-extra/clangd/ClangdServer.cpp
@@ -526,12 +526,12 @@
PathRef File, Position Pos, int Resolve,
llvm::Optional<TypeHierarchyDirection> Direction,
Callback<Optional<TypeHierarchyItem>> CB) {
- auto Action = [Pos, Resolve,
- Direction](Callback<Optional<TypeHierarchyItem>> CB,
- Expected<InputsAndAST> InpAST) {
+ auto Action = [Pos, Resolve, Direction,
+ this](Callback<Optional<TypeHierarchyItem>> CB,
+ Expected<InputsAndAST> InpAST) {
if (!InpAST)
return CB(InpAST.takeError());
- CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction));
+ CB(clangd::getTypeHierarchy(InpAST->AST, Pos, Resolve, Direction, Index));
};
WorkScheduler.runWithAST("Type Hierarchy", File, Bind(Action, std::move(CB)));
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
