hokein updated this revision to Diff 163066.
hokein added a comment.
Minor cleanup.
Repository:
rCTE Clang Tools Extra
https://reviews.llvm.org/D51279
Files:
clangd/index/FileIndex.cpp
clangd/index/FileIndex.h
clangd/index/Index.cpp
clangd/index/Index.h
clangd/index/MemIndex.cpp
clangd/index/MemIndex.h
clangd/index/Merge.cpp
clangd/index/Merge.h
clangd/index/SymbolCollector.cpp
clangd/index/SymbolCollector.h
unittests/clangd/FileIndexTests.cpp
unittests/clangd/IndexTests.cpp
unittests/clangd/SymbolCollectorTests.cpp
unittests/clangd/TestTU.cpp
unittests/clangd/TestTU.h
Index: unittests/clangd/TestTU.h
===================================================================
--- unittests/clangd/TestTU.h
+++ unittests/clangd/TestTU.h
@@ -38,6 +38,16 @@
return TU;
}
+ static TestTU withAllCode(llvm::StringRef HeaderCode, llvm::StringRef Code,
+ llvm::StringRef Filename = "") {
+ TestTU TU;
+ TU.HeaderCode = HeaderCode;
+ TU.Code = Code;
+ if (!Filename.empty())
+ TU.Filename = Filename;
+ return TU;
+ }
+
// The code to be compiled.
std::string Code;
std::string Filename = "TestTU.cpp";
Index: unittests/clangd/TestTU.cpp
===================================================================
--- unittests/clangd/TestTU.cpp
+++ unittests/clangd/TestTU.cpp
@@ -45,7 +45,7 @@
SymbolSlab TestTU::headerSymbols() const {
auto AST = build();
- return indexAST(AST.getASTContext(), AST.getPreprocessorPtr());
+ return indexAST(AST.getASTContext(), AST.getPreprocessorPtr()).first;
}
std::unique_ptr<SymbolIndex> TestTU::index() const {
Index: unittests/clangd/SymbolCollectorTests.cpp
===================================================================
--- unittests/clangd/SymbolCollectorTests.cpp
+++ unittests/clangd/SymbolCollectorTests.cpp
@@ -74,6 +74,16 @@
MATCHER_P(ForCodeCompletion, IsIndexedForCodeCompletion, "") {
return arg.IsIndexedForCodeCompletion == IsIndexedForCodeCompletion;
}
+MATCHER(OccurrenceRange, "") {
+ const clang::clangd::SymbolOccurrence& Pos = testing::get<0>(arg);
+ const clang::clangd::Range& Range = testing::get<1>(arg);
+ return std::tie(Pos.Location.Start.Line,
+ Pos.Location.Start.Column,
+ Pos.Location.End.Line,
+ Pos.Location.End.Column) ==
+ std::tie(Range.start.line, Range.start.character, Range.end.line,
+ Range.end.character);
+}
namespace clang {
namespace clangd {
@@ -237,6 +247,7 @@
llvm::MemoryBuffer::getMemBuffer(MainCode));
Invocation.run();
Symbols = Factory->Collector->takeSymbols();
+ SymbolOccurrences = Factory->Collector->takeOccurrences();
return true;
}
@@ -247,6 +258,7 @@
std::string TestFileName;
std::string TestFileURI;
SymbolSlab Symbols;
+ SymbolOccurrenceSlab SymbolOccurrences;
SymbolCollector::Options CollectorOpts;
std::unique_ptr<CommentHandler> PragmaHandler;
};
@@ -413,6 +425,67 @@
));
}
+TEST_F(SymbolCollectorTest, Occurrences) {
+ Annotations Header(R"(
+ class $foo[[Foo]] {
+ public:
+ $foo[[Foo]]() {}
+ $foo[[Foo]](int);
+ };
+ class $bar[[Bar]];
+ void $func[[func]]();
+ )");
+ Annotations Main(R"(
+ class $bar[[Bar]] {};
+
+ void $func[[func]]();
+
+ void fff() {
+ $foo[[Foo]] foo;
+ $bar[[Bar]] bar;
+ $func[[func]]();
+ int abc = 0;
+ $foo[[Foo]] foo2 = abc;
+ }
+ )");
+ Annotations SymbolsOnlyInMainCode(R"(
+ int a;
+ void b() {}
+ static const int c = 0;
+ class d {};
+ )");
+ CollectorOpts.OccurrenceFilter = SymbolOccurrenceKind::Declaration |
+ SymbolOccurrenceKind::Definition |
+ SymbolOccurrenceKind::Reference;
+ runSymbolCollector(Header.code(),
+ (Main.code() + SymbolsOnlyInMainCode.code()).str());
+ auto HeaderSymbols = TestTU::withHeaderCode(Header.code()).headerSymbols();
+
+ EXPECT_THAT(
+ SymbolOccurrences.find(findSymbol(Symbols, "Foo").ID),
+ testing::UnorderedPointwise(OccurrenceRange(), Main.ranges("foo")));
+ EXPECT_THAT(
+ SymbolOccurrences.find(findSymbol(Symbols, "Bar").ID),
+ testing::UnorderedPointwise(OccurrenceRange(), Main.ranges("bar")));
+ EXPECT_THAT(
+ SymbolOccurrences.find(findSymbol(Symbols, "func").ID),
+ testing::UnorderedPointwise(OccurrenceRange(), Main.ranges("func")));
+
+ // Retrieve IDs for symbols *only* in the main file, and verify these symbols
+ // are not collected.
+ auto MainSymbols =
+ TestTU::withHeaderCode(SymbolsOnlyInMainCode.code()).headerSymbols();
+ EXPECT_THAT(
+ SymbolOccurrences.find(findSymbol(MainSymbols, "a").ID),
+ testing::IsEmpty());
+ EXPECT_THAT(
+ SymbolOccurrences.find(findSymbol(MainSymbols, "b").ID),
+ testing::IsEmpty());
+ EXPECT_THAT(
+ SymbolOccurrences.find(findSymbol(MainSymbols, "c").ID),
+ testing::IsEmpty());
+}
+
TEST_F(SymbolCollectorTest, References) {
const std::string Header = R"(
class W;
Index: unittests/clangd/IndexTests.cpp
===================================================================
--- unittests/clangd/IndexTests.cpp
+++ unittests/clangd/IndexTests.cpp
@@ -7,21 +7,36 @@
//
//===----------------------------------------------------------------------===//
+#include "Annotations.h"
#include "TestIndex.h"
+#include "TestTU.h"
+#include "gmock/gmock.h"
+#include "index/FileIndex.h"
#include "index/Index.h"
#include "index/MemIndex.h"
#include "index/Merge.h"
-#include "gmock/gmock.h"
#include "gtest/gtest.h"
using testing::Pointee;
using testing::UnorderedElementsAre;
+using testing::AllOf;
namespace clang {
namespace clangd {
namespace {
+std::shared_ptr<MemIndex::OccurrenceMap> emptyOccurrences() {
+ return llvm::make_unique<MemIndex::OccurrenceMap>();
+}
+
MATCHER_P(Named, N, "") { return arg.Name == N; }
+MATCHER_P(OccurrenceRange, Range, "") {
+ return std::tie(arg.Location.Start.Line, arg.Location.Start.Column,
+ arg.Location.End.Line, arg.Location.End.Column) ==
+ std::tie(Range.start.line, Range.start.character, Range.end.line,
+ Range.end.character);
+}
+MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
TEST(SymbolSlab, FindAndIterate) {
SymbolSlab::Builder B;
@@ -42,14 +57,14 @@
TEST(MemIndexTest, MemIndexSymbolsRecycled) {
MemIndex I;
std::weak_ptr<SlabAndPointers> Symbols;
- I.build(generateNumSymbols(0, 10, &Symbols));
+ I.build(generateNumSymbols(0, 10, &Symbols), emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "7";
EXPECT_THAT(match(I, Req), UnorderedElementsAre("7"));
EXPECT_FALSE(Symbols.expired());
// Release old symbols.
- I.build(generateNumSymbols(0, 0));
+ I.build(generateNumSymbols(0, 0), emptyOccurrences());
EXPECT_TRUE(Symbols.expired());
}
@@ -65,14 +80,14 @@
FuzzyFindRequest Req;
Req.Query = "7";
MemIndex I;
- I.build(std::move(Symbols));
+ I.build(std::move(Symbols), emptyOccurrences());
auto Matches = match(I, Req);
EXPECT_EQ(Matches.size(), 1u);
}
TEST(MemIndexTest, MemIndexLimitedNumMatches) {
MemIndex I;
- I.build(generateNumSymbols(0, 100));
+ I.build(generateNumSymbols(0, 100), emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "5";
Req.MaxCandidateCount = 3;
@@ -85,7 +100,8 @@
TEST(MemIndexTest, FuzzyMatch) {
MemIndex I;
I.build(
- generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}));
+ generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
+ emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "lol";
Req.MaxCandidateCount = 2;
@@ -95,60 +111,62 @@
TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
MemIndex I;
- I.build(generateSymbols({"a::y1", "b::y2", "y3"}));
+ I.build(generateSymbols({"a::y1", "b::y2", "y3"}), emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "y";
EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
}
TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
MemIndex I;
- I.build(generateSymbols({"a::y1", "b::y2", "y3"}));
+ I.build(generateSymbols({"a::y1", "b::y2", "y3"}), emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "y";
Req.Scopes = {""};
EXPECT_THAT(match(I, Req), UnorderedElementsAre("y3"));
}
TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
MemIndex I;
- I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}));
+ I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}),
+ emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "y";
Req.Scopes = {"a::"};
EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2"));
}
TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
MemIndex I;
- I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}));
+ I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}),
+ emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "y";
Req.Scopes = {"a::", "b::"};
EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3"));
}
TEST(MemIndexTest, NoMatchNestedScopes) {
MemIndex I;
- I.build(generateSymbols({"a::y1", "a::b::y2"}));
+ I.build(generateSymbols({"a::y1", "a::b::y2"}), emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "y";
Req.Scopes = {"a::"};
EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1"));
}
TEST(MemIndexTest, IgnoreCases) {
MemIndex I;
- I.build(generateSymbols({"ns::ABC", "ns::abc"}));
+ I.build(generateSymbols({"ns::ABC", "ns::abc"}), emptyOccurrences());
FuzzyFindRequest Req;
Req.Query = "AB";
Req.Scopes = {"ns::"};
EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
}
TEST(MemIndexTest, Lookup) {
MemIndex I;
- I.build(generateSymbols({"ns::abc", "ns::xyz"}));
+ I.build(generateSymbols({"ns::abc", "ns::xyz"}), emptyOccurrences());
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"));
@@ -159,8 +177,8 @@
TEST(MergeIndexTest, Lookup) {
MemIndex I, J;
- I.build(generateSymbols({"ns::A", "ns::B"}));
- J.build(generateSymbols({"ns::B", "ns::C"}));
+ I.build(generateSymbols({"ns::A", "ns::B"}), emptyOccurrences());
+ J.build(generateSymbols({"ns::B", "ns::C"}), emptyOccurrences());
EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::A")),
UnorderedElementsAre("ns::A"));
EXPECT_THAT(lookup(*mergeIndex(&I, &J), SymbolID("ns::B")),
@@ -180,8 +198,8 @@
TEST(MergeIndexTest, FuzzyFind) {
MemIndex I, J;
- I.build(generateSymbols({"ns::A", "ns::B"}));
- J.build(generateSymbols({"ns::B", "ns::C"}));
+ I.build(generateSymbols({"ns::A", "ns::B"}), emptyOccurrences());
+ J.build(generateSymbols({"ns::B", "ns::C"}), emptyOccurrences());
FuzzyFindRequest Req;
Req.Scopes = {"ns::"};
EXPECT_THAT(match(*mergeIndex(&I, &J), Req),
@@ -243,6 +261,55 @@
EXPECT_EQ(M.Name, "right");
}
+TEST(MergeIndexTest, FindOccurrences) {
+ FileIndex Dyn({"unittest"});
+ FileIndex StaticIndex({"unittest"});
+ auto MergedIndex = mergeIndex(&Dyn, &StaticIndex);
+
+ const char *HeaderCode = "class Foo;";
+ auto HeaderSymbols = TestTU::withHeaderCode("class Foo;").headerSymbols();
+ auto Foo = findSymbol(HeaderSymbols, "Foo");
+
+ // Build dynamic index.
+ Annotations Test1Code(R"(class $Foo[[Foo]];)");
+ auto AST =
+ TestTU::withAllCode(HeaderCode, Test1Code.code(), "test.cc").build();
+ Dyn.update("test.cc", &AST.getASTContext(), AST.getPreprocessorPtr(),
+ AST.getLocalTopLevelDecls());
+
+ // Build static index.
+ auto StaticAST =
+ TestTU::withAllCode(HeaderCode, "// static\nclass Foo {};", "test.cc")
+ .build();
+ // Add stale occurrences for test.cc.
+ StaticIndex.update("test.cc", &StaticAST.getASTContext(),
+ StaticAST.getPreprocessorPtr(),
+ StaticAST.getLocalTopLevelDecls());
+
+ // Add occcurrences for test2.cc
+ Annotations Test2Code(R"(class $Foo[[Foo]] {};)");
+ StaticAST =
+ TestTU::withAllCode(HeaderCode, Test2Code.code(), "test2.cc").build();
+ StaticIndex.update("test2.cc", &StaticAST.getASTContext(),
+ StaticAST.getPreprocessorPtr(),
+ StaticAST.getLocalTopLevelDecls());
+
+ OccurrencesRequest Request;
+ Request.IDs = {Foo.ID};
+ Request.Filter = SymbolOccurrenceKind::Declaration |
+ SymbolOccurrenceKind::Definition |
+ SymbolOccurrenceKind::Reference;
+ std::vector<SymbolOccurrence> Results;
+ MergedIndex->findOccurrences(
+ Request, [&](const SymbolOccurrence &O) { Results.push_back(O); });
+
+ EXPECT_THAT(Results, UnorderedElementsAre(
+ AllOf(OccurrenceRange(Test1Code.range("Foo")),
+ FileURI("unittest:///test.cc")),
+ AllOf(OccurrenceRange(Test2Code.range("Foo")),
+ FileURI("unittest:///test2.cc"))));
+}
+
} // namespace
} // namespace clangd
} // namespace clang
Index: unittests/clangd/FileIndexTests.cpp
===================================================================
--- unittests/clangd/FileIndexTests.cpp
+++ unittests/clangd/FileIndexTests.cpp
@@ -7,18 +7,28 @@
//
//===----------------------------------------------------------------------===//
+#include "Annotations.h"
#include "ClangdUnit.h"
#include "TestFS.h"
#include "TestTU.h"
+#include "gmock/gmock.h"
#include "index/FileIndex.h"
#include "clang/Frontend/CompilerInvocation.h"
#include "clang/Frontend/PCHContainerOperations.h"
#include "clang/Lex/Preprocessor.h"
#include "clang/Tooling/CompilationDatabase.h"
-#include "gmock/gmock.h"
#include "gtest/gtest.h"
using testing::UnorderedElementsAre;
+using testing::AllOf;
+
+MATCHER_P(OccurrenceRange, Range, "") {
+ return std::tie(arg.Location.Start.Line, arg.Location.Start.Column,
+ arg.Location.End.Line, arg.Location.End.Column) ==
+ std::tie(Range.start.line, Range.start.character, Range.end.line,
+ Range.end.character);
+}
+MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
namespace clang {
namespace clangd {
@@ -39,42 +49,78 @@
return llvm::make_unique<SymbolSlab>(std::move(Slab).build());
}
+std::unique_ptr<SymbolOccurrenceSlab> occurrenceSlab(const SymbolID &ID,
+ llvm::StringRef Path) {
+ auto Slab = llvm::make_unique<SymbolOccurrenceSlab>();
+ SymbolOccurrence Occurrence;
+ Occurrence.Location.FileURI = Path;
+ Slab->insert(ID, Occurrence);
+ return Slab;
+}
+
std::vector<std::string>
getSymbolNames(const std::vector<const Symbol *> &Symbols) {
std::vector<std::string> Names;
for (const Symbol *Sym : Symbols)
Names.push_back(Sym->Name);
return Names;
}
+std::vector<std::string>
+getOccurrencePath(const std::vector<const SymbolOccurrence *> &Occurrences) {
+ std::vector<std::string> Paths;
+ for (const auto *O : Occurrences)
+ Paths.push_back(O->Location.FileURI);
+ return Paths;
+}
+
+std::unique_ptr<SymbolOccurrenceSlab> emptyOccurrence() {
+ auto EmptySlab = llvm::make_unique<SymbolOccurrenceSlab>();
+ EmptySlab->freeze();
+ return EmptySlab;
+}
+
TEST(FileSymbolsTest, UpdateAndGet) {
FileSymbols FS;
EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
+ EXPECT_TRUE(FS.allOccurrences()->empty());
- FS.update("f1", numSlab(1, 3));
+ SymbolID ID("1");
+ FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc"));
EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
UnorderedElementsAre("1", "2", "3"));
+ auto Occurrences = FS.allOccurrences();
+ EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]),
+ UnorderedElementsAre("f1.cc"));
}
TEST(FileSymbolsTest, Overlap) {
FileSymbols FS;
- FS.update("f1", numSlab(1, 3));
- FS.update("f2", numSlab(3, 5));
+ FS.update("f1", numSlab(1, 3), emptyOccurrence());
+ FS.update("f2", numSlab(3, 5), emptyOccurrence());
EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
UnorderedElementsAre("1", "2", "3", "3", "4", "5"));
}
TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
FileSymbols FS;
- FS.update("f1", numSlab(1, 3));
+ SymbolID ID("1");
+ FS.update("f1", numSlab(1, 3), occurrenceSlab(ID, "f1.cc"));
auto Symbols = FS.allSymbols();
EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
+ auto Occurrences = FS.allOccurrences();
+ EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]),
+ UnorderedElementsAre("f1.cc"));
- FS.update("f1", nullptr);
+ FS.update("f1", nullptr, nullptr);
EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
+
+ EXPECT_TRUE(FS.allOccurrences()->empty());
+ EXPECT_THAT(getOccurrencePath((*Occurrences)[ID]),
+ UnorderedElementsAre("f1.cc"));
}
std::vector<std::string> match(const SymbolIndex &I,
@@ -270,6 +316,45 @@
UnorderedElementsAre("ns_in_header", "ns_in_header::func_in_header"));
}
+TEST(FileIndexTest, Occurrences) {
+ const char *HeaderCode = "class Foo {};";
+ Annotations MainCode(R"cpp(
+ void f() {
+ $foo[[Foo]] foo;
+ }
+ )cpp");
+
+ auto Foo =
+ findSymbol(TestTU::withHeaderCode(HeaderCode).headerSymbols(), "Foo");
+
+ OccurrencesRequest Request;
+ Request.IDs = {Foo.ID};
+ Request.Filter = SymbolOccurrenceKind::Declaration |
+ SymbolOccurrenceKind::Definition |
+ SymbolOccurrenceKind::Reference;
+
+ FileIndex Index(/*URISchemes*/ {"unittest"});
+ // Add test.cc
+ auto AST =
+ TestTU::withAllCode(HeaderCode, MainCode.code(), "test.cc").build();
+ Index.update("test.cc", &AST.getASTContext(), AST.getPreprocessorPtr(),
+ AST.getLocalTopLevelDecls());
+ // Add test2.cc
+ AST = TestTU::withAllCode(HeaderCode, MainCode.code(), "test2.cc").build();
+ Index.update("test2.cc", &AST.getASTContext(), AST.getPreprocessorPtr(),
+ AST.getLocalTopLevelDecls());
+
+ std::vector<SymbolOccurrence> Results;
+ Index.findOccurrences(
+ Request, [&Results](const SymbolOccurrence &O) { Results.push_back(O); });
+
+ EXPECT_THAT(Results,
+ UnorderedElementsAre(AllOf(OccurrenceRange(MainCode.range("foo")),
+ FileURI("unittest:///test.cc")),
+ AllOf(OccurrenceRange(MainCode.range("foo")),
+ FileURI("unittest:///test2.cc"))));
+}
+
} // namespace
} // namespace clangd
} // namespace clang
Index: clangd/index/SymbolCollector.h
===================================================================
--- clangd/index/SymbolCollector.h
+++ clangd/index/SymbolCollector.h
@@ -59,6 +59,10 @@
/// collect macros. For example, `indexTopLevelDecls` will not index any
/// macro even if this is true.
bool CollectMacro = false;
+ /// The symbol occurrence kind that will be collected.
+ /// If not set (Unknown), SymbolCollector will not collect any symbol
+ /// occurrences.
+ SymbolOccurrenceKind OccurrenceFilter = SymbolOccurrenceKind::Unknown;
};
SymbolCollector(Options Opts);
@@ -86,6 +90,10 @@
SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
+ SymbolOccurrenceSlab takeOccurrences() {
+ return std::move(SymbolOccurrences);
+ }
+
void finish() override;
private:
@@ -108,6 +116,13 @@
// canonical by clang but should not be considered canonical in the index
// unless it's a definition.
llvm::DenseMap<const Decl *, const Decl *> CanonicalDecls;
+
+ using DeclOccurrence = std::pair<SourceLocation, index::SymbolRoleSet>;
+ llvm::DenseMap<const NamedDecl*, std::vector<DeclOccurrence>> DeclOccurrences;
+ // All symbol occurrences collected from the AST, assembled on finish().
+ // Only symbols declared in preamble (from #inclues) and references from the
+ // main file will be included.
+ SymbolOccurrenceSlab SymbolOccurrences;
};
} // namespace clangd
Index: clangd/index/SymbolCollector.cpp
===================================================================
--- clangd/index/SymbolCollector.cpp
+++ clangd/index/SymbolCollector.cpp
@@ -224,6 +224,17 @@
match(decl(isExpansionInMainFile()), ND, ND.getASTContext()).empty();
}
+SymbolOccurrenceKind ToOccurrenceKind(index::SymbolRoleSet Roles) {
+ SymbolOccurrenceKind Kind;
+ for (auto Mask :
+ {SymbolOccurrenceKind::Declaration, SymbolOccurrenceKind::Definition,
+ SymbolOccurrenceKind::Reference}) {
+ if (Roles & static_cast<unsigned>(Mask))
+ Kind |= Mask;
+ }
+ return Kind;
+}
+
} // namespace
SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {}
@@ -313,6 +324,10 @@
SM.getFileID(SM.getSpellingLoc(Loc)) == SM.getMainFileID())
ReferencedDecls.insert(ND);
+ if ((static_cast<unsigned>(Opts.OccurrenceFilter) & Roles) &&
+ SM.getFileID(SM.getSpellingLoc(Loc)) == SM.getMainFileID())
+ DeclOccurrences[ND].emplace_back(Loc, Roles);
+
// Don't continue indexing if this is a mere reference.
if (!(Roles & static_cast<unsigned>(index::SymbolRole::Declaration) ||
Roles & static_cast<unsigned>(index::SymbolRole::Definition)))
@@ -436,8 +451,28 @@
IncRef(SymbolID(USR));
}
}
+
+ for (auto& It : DeclOccurrences) {
+ if (auto ID = getSymbolID(It.first)) {
+ if (Symbols.find(*ID)) {
+ for (const auto& LocAndRole: It.second) {
+ std::string FileURI;
+ if (auto DeclLoc = getTokenLocation(LocAndRole.first,
+ ASTCtx->getSourceManager(), Opts,
+ ASTCtx->getLangOpts(), FileURI)) {
+ SymbolOccurrence Occurrence;
+ Occurrence.Location = *DeclLoc;
+ Occurrence.Kind = ToOccurrenceKind(LocAndRole.second);
+ SymbolOccurrences.insert(*ID, Occurrence);
+ }
+ }
+ }
+ }
+ }
+ SymbolOccurrences.freeze();
ReferencedDecls.clear();
ReferencedMacros.clear();
+ DeclOccurrences.clear();
}
const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
Index: clangd/index/Merge.h
===================================================================
--- clangd/index/Merge.h
+++ clangd/index/Merge.h
@@ -24,6 +24,10 @@
// - the Dynamic index covers few files, but is relatively up-to-date.
// - the Static index covers a bigger set of files, but is relatively stale.
// The returned index attempts to combine results, and avoid duplicates.
+//
+// FIXME: We don't have a mechanism in Index to track deleted symbols and
+// occurrences in dirty files, so the merged index may return stale symbols
+// and occurrences from Static index.
std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic,
const SymbolIndex *Static);
Index: clangd/index/Merge.cpp
===================================================================
--- clangd/index/Merge.cpp
+++ clangd/index/Merge.cpp
@@ -81,7 +81,27 @@
void findOccurrences(const OccurrencesRequest &Req,
llvm::function_ref<void(const SymbolOccurrence &)>
Callback) const override {
- log("findOccurrences is not implemented.");
+ // We don't want duplicated occurrences from the static/dynamic indexes,
+ // and we can't reliably duplicate them because occurrence offsets may
+ // differ slightly.
+ // We consider the dynamic index authoritative and report all its
+ // occurrences, and only report static index occurrences from other files.
+ //
+ // FIXME: The heuristic fails if the dynamic index containts a file, but all
+ // occurrences were removed (we will report stale ones from the static
+ // index). Ultimately we should explicit check which index has the file
+ // instead.
+ llvm::DenseSet<llvm::StringRef> DynamicIndexFileURIs;
+ Dynamic->findOccurrences(Req, [&](const SymbolOccurrence &O) {
+ DynamicIndexFileURIs.insert(O.Location.FileURI);
+ Callback(O);
+ });
+ Static->findOccurrences(Req, [&](const SymbolOccurrence &O) {
+ if (DynamicIndexFileURIs.find(O.Location.FileURI) !=
+ DynamicIndexFileURIs.end())
+ return;
+ Callback(O);
+ });
}
private:
Index: clangd/index/MemIndex.h
===================================================================
--- clangd/index/MemIndex.h
+++ clangd/index/MemIndex.h
@@ -16,15 +16,21 @@
namespace clang {
namespace clangd {
-/// \brief This implements an index for a (relatively small) set of symbols that
-/// can be easily managed in memory.
+/// \brief This implements an index for a (relatively small) set of symbols (or
+/// symbol occurrences) that can be easily managed in memory.
class MemIndex : public SymbolIndex {
public:
- /// \brief (Re-)Build index for `Symbols`. All symbol pointers must remain
- /// accessible as long as `Symbols` is kept alive.
- void build(std::shared_ptr<std::vector<const Symbol *>> Symbols);
+ using OccurrenceMap =
+ llvm::DenseMap<SymbolID, std::vector<const SymbolOccurrence *>>;
- /// \brief Build index from a symbol slab.
+ /// \brief (Re-)Build index for `Symbols` and update `Occurrences`.
+ /// All symbol pointers and symbol occurrence pointers must remain accessible
+ /// as long as `Symbols` and `Occurrences` are kept alive.
+ void build(std::shared_ptr<std::vector<const Symbol *>> Symbols,
+ std::shared_ptr<OccurrenceMap> Occurrences);
+
+ /// \brief Build index from a symbol slab. The returned Index doesn't have
+ /// symbol occurrences support.
static std::unique_ptr<SymbolIndex> build(SymbolSlab Slab);
bool
@@ -44,6 +50,8 @@
// Index is a set of symbols that are deduplicated by symbol IDs.
// FIXME: build smarter index structure.
llvm::DenseMap<SymbolID, const Symbol *> Index;
+ // A map from symbol ID to symbol occurrences, support query by IDs.
+ std::shared_ptr<OccurrenceMap> Occurrences;
mutable std::mutex Mutex;
};
Index: clangd/index/MemIndex.cpp
===================================================================
--- clangd/index/MemIndex.cpp
+++ clangd/index/MemIndex.cpp
@@ -15,7 +15,10 @@
namespace clang {
namespace clangd {
-void MemIndex::build(std::shared_ptr<std::vector<const Symbol *>> Syms) {
+void MemIndex::build(std::shared_ptr<std::vector<const Symbol *>> Syms,
+ std::shared_ptr<OccurrenceMap> AllOccurrences) {
+ assert(Syms && "Syms must be set when build MemIndex");
+ assert(AllOccurrences && "Occurrences must be set when build MemIndex");
llvm::DenseMap<SymbolID, const Symbol *> TempIndex;
for (const Symbol *Sym : *Syms)
TempIndex[Sym->ID] = Sym;
@@ -25,12 +28,14 @@
std::lock_guard<std::mutex> Lock(Mutex);
Index = std::move(TempIndex);
Symbols = std::move(Syms); // Relase old symbols.
+ Occurrences = std::move(AllOccurrences);
}
}
std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab) {
auto Idx = llvm::make_unique<MemIndex>();
- Idx->build(getSymbolsFromSlab(std::move(Slab)));
+ auto EmptyOccurrences = llvm::make_unique<OccurrenceMap>();
+ Idx->build(getSymbolsFromSlab(std::move(Slab)), std::move(EmptyOccurrences));
return std::move(Idx);
}
@@ -81,7 +86,16 @@
void MemIndex::findOccurrences(
const OccurrencesRequest &Req,
llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
- log("findOccurrences is not implemented.");
+ std::lock_guard<std::mutex> Lock(Mutex);
+ for (const auto& ReqID : Req.IDs) {
+ auto FoundOccurrences = Occurrences->find(ReqID);
+ if (FoundOccurrences == Occurrences->end())
+ continue;
+ for (const auto *O : FoundOccurrences->second) {
+ if (static_cast<int>(Req.Filter & O->Kind))
+ Callback(*O);
+ }
+ }
}
std::shared_ptr<std::vector<const Symbol *>>
Index: clangd/index/Index.h
===================================================================
--- clangd/index/Index.h
+++ clangd/index/Index.h
@@ -31,9 +31,6 @@
uint32_t Line = 0; // 0-based
// Using UTF-16 code units.
uint32_t Column = 0; // 0-based
- bool operator==(const Position& P) const {
- return Line == P.Line && Column == P.Column;
- }
};
// The URI of the source file where a symbol occurs.
@@ -44,11 +41,25 @@
Position End;
explicit operator bool() const { return !FileURI.empty(); }
- bool operator==(const SymbolLocation& Loc) const {
- return std::tie(FileURI, Start, End) ==
- std::tie(Loc.FileURI, Loc.Start, Loc.End);
- }
};
+inline bool operator==(const SymbolLocation::Position& L,
+ const SymbolLocation::Position& R) {
+ return std::tie(L.Line, L.Column) == std::tie(R.Line, R.Column);
+}
+inline bool operator<(const SymbolLocation::Position &L,
+ const SymbolLocation::Position &R){
+ return std::tie(L.Line, L.Column) < std::tie(R.Line, R.Column);
+}
+inline bool operator==(const SymbolLocation&L,
+ const SymbolLocation&R){
+ return std::tie(L.FileURI, L.Start, L.End) ==
+ std::tie(R.FileURI, R.Start, R.End);
+}
+inline bool operator<(const SymbolLocation&L,
+ const SymbolLocation&R){
+ return std::tie(L.FileURI, L.Start, L.End) <
+ std::tie(R.FileURI, R.Start, R.End);
+}
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &);
// The class identifies a particular C++ symbol (class, function, method, etc).
@@ -323,6 +334,67 @@
SymbolLocation Location;
SymbolOccurrenceKind Kind = SymbolOccurrenceKind::Unknown;
};
+inline bool operator<(const SymbolOccurrence &L, const SymbolOccurrence &R) {
+ return std::tie(L.Location, L.Kind) < std::tie(R.Location, R.Kind);
+}
+inline bool operator==(const SymbolOccurrence &L, const SymbolOccurrence &R) {
+ return std::tie(L.Location, L.Kind) == std::tie(R.Location, R.Kind);
+}
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const SymbolOccurrence &Occurrence);
+
+// An efficient structure of storing large set of symbol occurrences in memory.
+// Filenames are deduplicated.
+class SymbolOccurrenceSlab {
+ public:
+ using const_iterator =
+ llvm::DenseMap<SymbolID, std::vector<SymbolOccurrence>>::const_iterator;
+ using iterator = const_iterator;
+
+ SymbolOccurrenceSlab() : UniqueStrings(Arena) {}
+
+ // Define move semantics for the slab, allowing assignment from an rvalue.
+ // Implicit move assignment is deleted by the compiler because
+ // StringSaver has a reference type member.
+ SymbolOccurrenceSlab(SymbolOccurrenceSlab &&Slab) = default;
+ SymbolOccurrenceSlab& operator=(SymbolOccurrenceSlab&& RHS) {
+ assert(RHS.Frozen &&
+ "SymbolOcucrrenceSlab must be frozen when move assigned!");
+ Arena = std::move(RHS.Arena);
+ Frozen = true;
+ Occurrences = std::move(RHS.Occurrences);
+ return *this;
+ }
+
+ const_iterator begin() const { return Occurrences.begin(); }
+ const_iterator end() const { return Occurrences.end(); }
+
+ size_t bytes() const {
+ return sizeof(*this) + Arena.getTotalMemory() +
+ Occurrences.getMemorySize();
+ }
+
+ size_t size() const { return Occurrences.size(); }
+
+ // Adds a symbol occurrence.
+ // This is a deep copy: underlying FileURI will be owned by the slab.
+ void insert(const SymbolID &SymID, const SymbolOccurrence &Occurrence);
+
+ llvm::ArrayRef<SymbolOccurrence> find(const SymbolID &ID) const {
+ auto It = Occurrences.find(ID);
+ if (It == Occurrences.end())
+ return {};
+ return It->second;
+ }
+
+ void freeze();
+
+private:
+ bool Frozen = false;
+ llvm::BumpPtrAllocator Arena;
+ llvm::UniqueStringSaver UniqueStrings;
+ llvm::DenseMap<SymbolID, std::vector<SymbolOccurrence>> Occurrences;
+};
struct FuzzyFindRequest {
/// \brief A query string for the fuzzy find. This is matched against symbols'
Index: clangd/index/Index.cpp
===================================================================
--- clangd/index/Index.cpp
+++ clangd/index/Index.cpp
@@ -8,6 +8,7 @@
//===----------------------------------------------------------------------===//
#include "Index.h"
+
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/SHA1.h"
#include "llvm/Support/raw_ostream.h"
@@ -128,5 +129,48 @@
return SymbolSlab(std::move(NewArena), std::move(Symbols));
}
+raw_ostream &operator<<(raw_ostream &OS, SymbolOccurrenceKind K) {
+ if (K == SymbolOccurrenceKind::Unknown)
+ return OS << "Unknown";
+ static const std::vector<const char *> Messages = {"Decl", "Def", "Ref"};
+ bool VisitedOnce = false;
+ for (unsigned I = 0; I < Messages.size(); ++I) {
+ if (static_cast<uint8_t>(K) & 1u << I) {
+ if (VisitedOnce)
+ OS << ", ";
+ OS << Messages[I];
+ VisitedOnce = true;
+ }
+ }
+ return OS;
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const SymbolOccurrence &Occurrence) {
+ OS << Occurrence.Location << ":" << Occurrence.Kind;
+ return OS;
+}
+
+void SymbolOccurrenceSlab::insert(const SymbolID &SymID,
+ const SymbolOccurrence &Occurrence) {
+ assert(!Frozen &&
+ "Can't insert a symbol occurrence after the slab has been frozen!");
+ auto& SymOccurrences = Occurrences[SymID];
+ SymOccurrences.push_back(Occurrence);
+ SymOccurrences.back().Location.FileURI =
+ UniqueStrings.save(Occurrence.Location.FileURI);
+}
+
+void SymbolOccurrenceSlab::freeze() {
+ // Deduplicate symbol occurrenes.
+ for (auto &IDAndOccurrence : Occurrences) {
+ auto &Occurrence = IDAndOccurrence.getSecond();
+ std::sort(Occurrence.begin(), Occurrence.end());
+ Occurrence.erase(std::unique(Occurrence.begin(), Occurrence.end()),
+ Occurrence.end());
+ }
+ Frozen = true;
+}
+
} // namespace clangd
} // namespace clang
Index: clangd/index/FileIndex.h
===================================================================
--- clangd/index/FileIndex.h
+++ clangd/index/FileIndex.h
@@ -39,18 +39,25 @@
/// locking when we swap or obtain refereces to snapshots.
class FileSymbols {
public:
- /// \brief Updates all symbols in a file. If \p Slab is nullptr, symbols for
- /// \p Path will be removed.
- void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab);
+ /// \brief Updates all symbols and occurrences in a file.
+ /// If \p Slab (Occurrence) is nullptr, symbols (occurrences) for \p Path
+ /// will be removed.
+ void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
+ std::unique_ptr<SymbolOccurrenceSlab> Occurrences);
// The shared_ptr keeps the symbols alive
std::shared_ptr<std::vector<const Symbol *>> allSymbols();
+ /// Returns all symbol occurrences for all active files.
+ std::shared_ptr<MemIndex::OccurrenceMap> allOccurrences() const;
+
private:
mutable std::mutex Mutex;
/// \brief Stores the latest snapshots for all active files.
llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSlabs;
+ /// Stores the latest occurrence slabs for all active files.
+ llvm::StringMap<std::shared_ptr<SymbolOccurrenceSlab>> FileToOccurrenceSlabs;
};
/// \brief This manages symbls from files and an in-memory index on all symbols.
@@ -87,12 +94,12 @@
std::vector<std::string> URISchemes;
};
-/// Retrieves namespace and class level symbols in \p AST.
+/// Retrieves symbols and symbol occurrences in \p AST.
/// Exposed to assist in unit tests.
/// If URISchemes is empty, the default schemes in SymbolCollector will be used.
/// If \p TopLevelDecls is set, only these decls are indexed. Otherwise, all top
/// level decls obtained from \p AST are indexed.
-SymbolSlab
+std::pair<SymbolSlab, SymbolOccurrenceSlab>
indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls = llvm::None,
llvm::ArrayRef<std::string> URISchemes = {});
Index: clangd/index/FileIndex.cpp
===================================================================
--- clangd/index/FileIndex.cpp
+++ clangd/index/FileIndex.cpp
@@ -16,9 +16,10 @@
namespace clang {
namespace clangd {
-SymbolSlab indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
- llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls,
- llvm::ArrayRef<std::string> URISchemes) {
+std::pair<SymbolSlab, SymbolOccurrenceSlab>
+indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
+ llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls,
+ llvm::ArrayRef<std::string> URISchemes) {
SymbolCollector::Options CollectorOpts;
// FIXME(ioeric): we might also want to collect include headers. We would need
// to make sure all includes are canonicalized (with CanonicalIncludes), which
@@ -31,8 +32,6 @@
CollectorOpts.URISchemes = URISchemes;
CollectorOpts.Origin = SymbolOrigin::Dynamic;
- SymbolCollector Collector(std::move(CollectorOpts));
- Collector.setPreprocessor(PP);
index::IndexingOptions IndexOpts;
// We only need declarations, because we don't count references.
IndexOpts.SystemSymbolFilter =
@@ -46,20 +45,42 @@
DeclsToIndex.assign(AST.getTranslationUnitDecl()->decls().begin(),
AST.getTranslationUnitDecl()->decls().end());
+ // We only collect occurrences when indexing main AST.
+ // FIXME: this is a hacky way to detect whether we are indexing preamble AST
+ // or main AST, we should make it explicitly.
+ if (TopLevelDecls) {
+ CollectorOpts.OccurrenceFilter = SymbolOccurrenceKind::Declaration |
+ SymbolOccurrenceKind::Definition |
+ SymbolOccurrenceKind::Reference;
+ }
+
+ SymbolCollector Collector(std::move(CollectorOpts));
+ Collector.setPreprocessor(PP);
index::indexTopLevelDecls(AST, DeclsToIndex, Collector, IndexOpts);
- return Collector.takeSymbols();
+ auto Syms = Collector.takeSymbols();
+ auto Occurrences = Collector.takeOccurrences();
+ vlog("index for AST: \n"
+ " symbol slab: {0} symbols, {1} bytes\n"
+ " occurrence slab: {2} symbols, {3} bytes",
+ Syms.size(), Syms.bytes(), Occurrences.size(), Occurrences.bytes());
+ return {std::move(Syms), std::move(Occurrences)};
}
FileIndex::FileIndex(std::vector<std::string> URISchemes)
: URISchemes(std::move(URISchemes)) {}
-void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Slab) {
+void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
+ std::unique_ptr<SymbolOccurrenceSlab> Occurrences) {
std::lock_guard<std::mutex> Lock(Mutex);
if (!Slab)
FileToSlabs.erase(Path);
else
FileToSlabs[Path] = std::move(Slab);
+ if (!Occurrences)
+ FileToOccurrenceSlabs.erase(Path);
+ else
+ FileToOccurrenceSlabs[Path] = std::move(Occurrences);
}
std::shared_ptr<std::vector<const Symbol *>> FileSymbols::allSymbols() {
@@ -85,19 +106,47 @@
return {std::move(Snap), Pointers};
}
+std::shared_ptr<MemIndex::OccurrenceMap> FileSymbols::allOccurrences() const {
+ // The snapshot manages life time of symbol occurrence slabs and provides
+ // pointers to all occurrences in all occurence slabs.
+ struct Snapshot {
+ MemIndex::OccurrenceMap Occurrences; // ID => {Occurrence}
+ std::vector<std::shared_ptr<SymbolOccurrenceSlab>> KeepAlive;
+ };
+
+ auto Snap = std::make_shared<Snapshot>();
+ {
+ std::lock_guard<std::mutex> Lock(Mutex);
+
+ for (const auto &FileAndSlab : FileToOccurrenceSlabs) {
+ Snap->KeepAlive.push_back(FileAndSlab.second);
+ for (const auto &IDAndOccurrences : *FileAndSlab.second) {
+ auto &Occurrences = Snap->Occurrences[IDAndOccurrences.first];
+ for (const auto &Occurrence : IDAndOccurrences.second)
+ Occurrences.push_back(&Occurrence);
+ }
+ }
+ }
+
+ return {std::move(Snap), &Snap->Occurrences};
+}
+
void FileIndex::update(PathRef Path, ASTContext *AST,
std::shared_ptr<Preprocessor> PP,
llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls) {
if (!AST) {
- FSymbols.update(Path, nullptr);
+ FSymbols.update(Path, nullptr, nullptr);
} else {
assert(PP);
auto Slab = llvm::make_unique<SymbolSlab>();
- *Slab = indexAST(*AST, PP, TopLevelDecls, URISchemes);
- FSymbols.update(Path, std::move(Slab));
+ auto OccurrenceSlab = llvm::make_unique<SymbolOccurrenceSlab>();
+ auto IndexResults = indexAST(*AST, PP, TopLevelDecls, URISchemes);
+ std::tie(*Slab, *OccurrenceSlab) =
+ indexAST(*AST, PP, TopLevelDecls, URISchemes);
+ FSymbols.update(Path, std::move(Slab), std::move(OccurrenceSlab));
}
auto Symbols = FSymbols.allSymbols();
- Index.build(std::move(Symbols));
+ Index.build(std::move(Symbols), FSymbols.allOccurrences());
}
bool FileIndex::fuzzyFind(
@@ -115,7 +164,7 @@
void FileIndex::findOccurrences(
const OccurrencesRequest &Req,
llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
- log("findOccurrences is not implemented.");
+ Index.findOccurrences(Req, Callback);
}
} // namespace clangd
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
