nridge updated this revision to Diff 189275.
nridge added a comment.
Add tests involving templates and template specializations
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D58880/new/
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
@@ -1773,6 +1773,175 @@
EXPECT_THAT(typeParents(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;
+ 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));
+}
+
+TEST(Subtypes, ClassTemplate) {
+ Annotations Source(R"cpp(
+struct Parent {};
+
+template <typename T>
+struct Child : Parent {};
+)cpp");
+
+ TestTU TU = TestTU::withCode(Source.code());
+ auto Index = TU.index();
+
+ SymbolID Parent = findSymbolIDByName("Parent", Index.get());
+ SymbolID Child = findSymbolIDByName("Child", Index.get());
+
+ EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(Child));
+}
+
+// This test fails because explicit class template specializations
+// are not currently indexed.
+TEST(DISABLED_Subtypes, TemplateSpec1) {
+ Annotations Source(R"cpp(
+template <typename T>
+struct Parent {};
+
+template <>
+struct Parent<int> {};
+
+struct Child1 : Parent<float> {};
+
+struct Child2 : Parent<int> {};
+)cpp");
+
+ TestTU TU = TestTU::withCode(Source.code());
+ auto Index = TU.index();
+
+ SymbolID Parent = findSymbolIDByName("Parent", Index.get());
+ // Even if we start storing explicit specializations in the index,
+ // we will likely need additional changes for
+ // findSymbolIDByName("Parent<int>") to find it.
+ SymbolID ParentSpec = findSymbolIDByName("Parent<int>", 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(ParentSpec, Index.get()), ElementsAre(Child2));
+}
+
+// This test fails because explicit class template specializations
+// are not currently indexed.
+TEST(DISABLED_Subtypes, TemplateSpec2) {
+ Annotations Source(R"cpp(
+struct Parent {};
+
+template <typename T>
+struct Child {};
+
+template <>
+struct Child<int> : Parent {};
+)cpp");
+
+ TestTU TU = TestTU::withCode(Source.code());
+ auto Index = TU.index();
+
+ SymbolID Parent = findSymbolIDByName("Parent", Index.get());
+ SymbolID Child = findSymbolIDByName("Child", Index.get());
+ SymbolID ChildSpec = findSymbolIDByName("Child<int>", Index.get());
+
+ EXPECT_THAT(collectSubtypes(Parent, Index.get()),
+ ElementsAre(Child, ChildSpec));
+}
+
+TEST(Subtypes, DependentBase) {
+ Annotations Source(R"cpp(
+template <typename T>
+struct Parent {};
+
+template <typename T>
+struct Child : Parent<T> {};
+)cpp");
+
+ TestTU TU = TestTU::withCode(Source.code());
+ auto Index = TU.index();
+
+ SymbolID Parent = findSymbolIDByName("Parent", Index.get());
+ SymbolID Child = findSymbolIDByName("Child", Index.get());
+
+ EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(Child));
+}
+
// Parts of getTypeHierarchy() are tested in more detail by the
// FindRecordTypeAt.* and TypeParents.* 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,26 @@
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 *Parent : typeParents(RD)) {
+ if (auto ID = getSymbolID(Parent)) {
+ // We are a subtype to each of our parents.
+ // TODO: There may be cases where the parent type is not indexed for some
+ // reason (e.g. currently we don't index explicit class template
+ // specializations). Those cases should probably be removed in due course,
+ // but for now there are two possible ways to handle it:
+ // (A) Avoid storing the relationship 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.
+ 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,
- TypeHierarchyDirection Direction);
+ TypeHierarchyDirection Direction,
+ const SymbolIndex *Index = nullptr);
} // namespace clangd
} // namespace clang
Index: clang-tools-extra/clangd/XRefs.cpp
===================================================================
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -871,6 +871,65 @@
return THI;
}
+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> getTypeAncestors(const CXXRecordDecl &CXXRD,
ASTContext &ASTCtx) {
Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(ASTCtx, CXXRD);
@@ -885,7 +944,6 @@
Result->parents->emplace_back(std::move(*ParentSym));
}
}
-
return Result;
}
@@ -950,15 +1008,26 @@
llvm::Optional<TypeHierarchyItem>
getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
- TypeHierarchyDirection Direction) {
+ TypeHierarchyDirection Direction, const SymbolIndex *Index) {
const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
if (!CXXRD)
return llvm::None;
Optional<TypeHierarchyItem> Result =
getTypeAncestors(*CXXRD, AST.getASTContext());
- // TODO: Resolve type descendants if direction is Children or Both,
- // and ResolveLevels > 0.
+
+ if ((Direction == TypeHierarchyDirection::Children ||
+ Direction == TypeHierarchyDirection::Both) &&
+ ResolveLevels > 0) {
+ Result->children.emplace();
+
+ if (Index) {
+ if (Optional<SymbolID> ID = getSymbolID(CXXRD)) {
+ fillSubTypes(*ID, *Result->children, Index, ResolveLevels);
+ }
+ }
+ }
+
return Result;
}
Index: clang-tools-extra/clangd/ClangdServer.cpp
===================================================================
--- clang-tools-extra/clangd/ClangdServer.cpp
+++ clang-tools-extra/clangd/ClangdServer.cpp
@@ -525,11 +525,11 @@
void ClangdServer::findTypeHierarchy(PathRef File, Position Pos, int Resolve,
TypeHierarchyDirection Direction,
Callback<Optional<TypeHierarchyItem>> CB) {
- auto Action = [Pos, Resolve, Direction](decltype(CB) CB,
- Expected<InputsAndAST> InpAST) {
+ auto Action = [Pos, Resolve, Direction, this](decltype(CB) 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
