nridge created this revision.
nridge added a reviewer: kadircet.
Herald added subscribers: cfe-commits, usaxena95, arphaman, mgorny.
Herald added a project: clang.
nridge requested review of this revision.
Herald added subscribers: MaskRay, ilya-biryukov.
Support for outgoing calls is left for a future change.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D91122
Files:
clang-tools-extra/clangd/XRefs.cpp
clang-tools-extra/clangd/XRefs.h
clang-tools-extra/clangd/unittests/CMakeLists.txt
clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp
clang-tools-extra/clangd/unittests/TestTU.cpp
Index: clang-tools-extra/clangd/unittests/TestTU.cpp
===================================================================
--- clang-tools-extra/clangd/unittests/TestTU.cpp
+++ clang-tools-extra/clangd/unittests/TestTU.cpp
@@ -156,7 +156,8 @@
std::unique_ptr<SymbolIndex> TestTU::index() const {
auto AST = build();
- auto Idx = std::make_unique<FileIndex>(/*UseDex=*/true);
+ auto Idx = std::make_unique<FileIndex>(/*UseDex=*/true,
+ /*CollectMainFileRefs=*/true);
Idx->updatePreamble(testPath(Filename), /*Version=*/"null",
AST.getASTContext(), AST.getPreprocessorPtr(),
AST.getCanonicalIncludes());
Index: clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp
@@ -0,0 +1,272 @@
+//===-- CallHierarchyTests.cpp ---------------------------*- C++ -*-------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "Annotations.h"
+#include "Compiler.h"
+#include "Matchers.h"
+#include "ParsedAST.h"
+#include "SyncAPI.h"
+#include "TestFS.h"
+#include "TestTU.h"
+#include "TestWorkspace.h"
+#include "XRefs.h"
+#include "index/FileIndex.h"
+#include "index/SymbolCollector.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/Index/IndexingAction.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using ::testing::AllOf;
+using ::testing::ElementsAre;
+using ::testing::Field;
+using ::testing::Matcher;
+using ::testing::UnorderedElementsAre;
+
+// Helpers for matching call hierarchy data structures.
+MATCHER_P(WithName, N, "") { return arg.Name == N; }
+MATCHER_P(WithSelectionRange, R, "") { return arg.SelectionRange == R; }
+
+template <class ItemMatcher>
+::testing::Matcher<CallHierarchyIncomingCall> From(ItemMatcher M) {
+ return Field(&CallHierarchyIncomingCall::From, M);
+}
+template <class... RangeMatchers>
+::testing::Matcher<CallHierarchyIncomingCall> FromRanges(RangeMatchers... M) {
+ return Field(&CallHierarchyIncomingCall::FromRanges,
+ UnorderedElementsAre(M...));
+}
+
+TEST(CallHierarchy, IncomingOneFile) {
+ Annotations Source(R"cpp(
+ void call^ee(int);
+ void caller1() {
+ $Callee[[callee]](42);
+ }
+ void caller2() {
+ $Caller1A[[caller1]]();
+ $Caller1B[[caller1]]();
+ }
+ void caller3() {
+ $Caller1C[[caller1]]();
+ $Caller2[[caller2]]();
+ }
+ )cpp");
+ TestTU TU = TestTU::withCode(Source.code());
+ auto AST = TU.build();
+ auto Index = TU.index();
+
+ llvm::Optional<std::vector<CallHierarchyItem>> Items = prepareCallHierarchy(
+ AST, Source.point(), Index.get(), testPath(TU.Filename));
+ ASSERT_TRUE(bool(Items));
+ EXPECT_THAT(*Items, ElementsAre(WithName("callee")));
+ auto IncomingLevel1 = incomingCalls((*Items)[0], Index.get());
+ ASSERT_TRUE(bool(IncomingLevel1));
+ EXPECT_THAT(*IncomingLevel1,
+ ElementsAre(AllOf(From(WithName("caller1")),
+ FromRanges(Source.range("Callee")))));
+
+ auto IncomingLevel2 = incomingCalls((*IncomingLevel1)[0].From, Index.get());
+ ASSERT_TRUE(bool(IncomingLevel2));
+ EXPECT_THAT(
+ *IncomingLevel2,
+ UnorderedElementsAre(
+ AllOf(From(WithName("caller2")),
+ FromRanges(Source.range("Caller1A"), Source.range("Caller1B"))),
+ AllOf(From(WithName("caller3")),
+ FromRanges(Source.range("Caller1C")))));
+
+ auto IncomingLevel3 = incomingCalls((*IncomingLevel2)[0].From, Index.get());
+ ASSERT_TRUE(bool(IncomingLevel3));
+ EXPECT_THAT(*IncomingLevel3,
+ ElementsAre(AllOf(From(WithName("caller3")),
+ FromRanges(Source.range("Caller2")))));
+
+ auto IncomingLevel4 = incomingCalls((*IncomingLevel3)[0].From, Index.get());
+ ASSERT_TRUE(bool(IncomingLevel4));
+ EXPECT_THAT(*IncomingLevel4, ElementsAre());
+}
+
+TEST(CallHierarchy, MainFileOnlyRef) {
+ // In addition to testing that we store refs to main-file only symbols,
+ // this tests that anonymous namespaces do not interfere with the
+ // symbol re-identification process in callHierarchyItemToSymbo().
+ Annotations Source(R"cpp(
+ void call^ee(int);
+ namespace {
+ void caller1() {
+ $Callee[[callee]](42);
+ }
+ }
+ void caller2() {
+ $Caller1[[caller1]]();
+ }
+ )cpp");
+ TestTU TU = TestTU::withCode(Source.code());
+ auto AST = TU.build();
+ auto Index = TU.index();
+
+ llvm::Optional<std::vector<CallHierarchyItem>> Items = prepareCallHierarchy(
+ AST, Source.point(), Index.get(), testPath(TU.Filename));
+ ASSERT_TRUE(bool(Items));
+ EXPECT_THAT(*Items, ElementsAre(WithName("callee")));
+ auto IncomingLevel1 = incomingCalls((*Items)[0], Index.get());
+ ASSERT_TRUE(bool(IncomingLevel1));
+ EXPECT_THAT(*IncomingLevel1,
+ ElementsAre(AllOf(From(WithName("caller1")),
+ FromRanges(Source.range("Callee")))));
+
+ auto IncomingLevel2 = incomingCalls((*IncomingLevel1)[0].From, Index.get());
+ ASSERT_TRUE(bool(IncomingLevel2));
+ EXPECT_THAT(*IncomingLevel2,
+ UnorderedElementsAre(AllOf(From(WithName("caller2")),
+ FromRanges(Source.range("Caller1")))));
+}
+
+TEST(CallHierarchy, IncomingQualified) {
+ Annotations Source(R"cpp(
+ namespace ns {
+ struct Waldo {
+ void find();
+ };
+ void Waldo::find() {}
+ void caller1(Waldo &W) {
+ W.$Caller1[[f^ind]]();
+ }
+ void caller2(Waldo &W) {
+ W.$Caller2[[find]]();
+ }
+ }
+ )cpp");
+ TestTU TU = TestTU::withCode(Source.code());
+ auto AST = TU.build();
+ auto Index = TU.index();
+
+ llvm::Optional<std::vector<CallHierarchyItem>> Items = prepareCallHierarchy(
+ AST, Source.point(), Index.get(), testPath(TU.Filename));
+ ASSERT_TRUE(bool(Items));
+ EXPECT_THAT(*Items, ElementsAre(WithName("ns::Waldo::find")));
+ auto Incoming = incomingCalls((*Items)[0], Index.get());
+ ASSERT_TRUE(bool(Incoming));
+ EXPECT_THAT(*Incoming,
+ UnorderedElementsAre(AllOf(From(WithName("caller1")),
+ FromRanges(Source.range("Caller1"))),
+ AllOf(From(WithName("caller2")),
+ FromRanges(Source.range("Caller2")))));
+}
+
+TEST(CallHierarchy, IncomingMultiFile) {
+ // The test uses a .hh suffix for header files to get clang
+ // to parse them in C++ mode. .h files are parsed in C mode
+ // by default, which causes problems because e.g. symbol
+ // USRs are different in C mode (do not include function signatures).
+
+ Annotations CalleeH(R"cpp(
+ void calle^e(int);
+ )cpp");
+ Annotations CalleeC(R"cpp(
+ #include "callee.hh"
+ void calle^e(int) {}
+ )cpp");
+ Annotations Caller1H(R"cpp(
+ void caller1();
+ )cpp");
+ Annotations Caller1C(R"cpp(
+ #include "callee.hh"
+ #include "caller1.hh"
+ void caller1() {
+ [[calle^e]](42);
+ }
+ )cpp");
+ Annotations Caller2H(R"cpp(
+ void caller2();
+ )cpp");
+ Annotations Caller2C(R"cpp(
+ #include "caller1.hh"
+ #include "caller2.hh"
+ void caller2() {
+ $A[[caller1]]();
+ $B[[caller1]]();
+ }
+ )cpp");
+ Annotations Caller3C(R"cpp(
+ #include "caller1.hh"
+ #include "caller2.hh"
+ void caller3() {
+ $Caller1[[caller1]]();
+ $Caller2[[caller2]]();
+ }
+ )cpp");
+
+ TestWorkspace Workspace;
+ Workspace.addSource("callee.hh", CalleeH.code());
+ Workspace.addSource("caller1.hh", Caller1H.code());
+ Workspace.addSource("caller2.hh", Caller2H.code());
+ Workspace.addMainFile("callee.cc", CalleeC.code());
+ Workspace.addMainFile("caller1.cc", Caller1C.code());
+ Workspace.addMainFile("caller2.cc", Caller2C.code());
+ Workspace.addMainFile("caller3.cc", Caller3C.code());
+
+ auto Index = Workspace.index();
+
+ auto CheckCallHierarchy = [&](ParsedAST &AST, Position Pos, PathRef TUPath) {
+ llvm::Optional<std::vector<CallHierarchyItem>> Items =
+ prepareCallHierarchy(AST, Pos, Index.get(), TUPath);
+ ASSERT_TRUE(bool(Items));
+ EXPECT_THAT(*Items, ElementsAre(WithName("callee")));
+ auto IncomingLevel1 = incomingCalls((*Items)[0], Index.get());
+ ASSERT_TRUE(bool(IncomingLevel1));
+ EXPECT_THAT(*IncomingLevel1,
+ ElementsAre(AllOf(From(WithName("caller1")),
+ FromRanges(Caller1C.range()))));
+
+ auto IncomingLevel2 = incomingCalls((*IncomingLevel1)[0].From, Index.get());
+ ASSERT_TRUE(bool(IncomingLevel2));
+ EXPECT_THAT(*IncomingLevel2,
+ UnorderedElementsAre(
+ AllOf(From(WithName("caller2")),
+ FromRanges(Caller2C.range("A"), Caller2C.range("B"))),
+ AllOf(From(WithName("caller3")),
+ FromRanges(Caller3C.range("Caller1")))));
+
+ auto IncomingLevel3 = incomingCalls((*IncomingLevel2)[0].From, Index.get());
+ ASSERT_TRUE(bool(IncomingLevel3));
+ EXPECT_THAT(*IncomingLevel3,
+ ElementsAre(AllOf(From(WithName("caller3")),
+ FromRanges(Caller3C.range("Caller2")))));
+
+ auto IncomingLevel4 = incomingCalls((*IncomingLevel3)[0].From, Index.get());
+ ASSERT_TRUE(bool(IncomingLevel4));
+ EXPECT_THAT(*IncomingLevel4, ElementsAre());
+ };
+
+ // Check that invoking from a call site works.
+ auto AST = Workspace.openFile("caller1.cc");
+ ASSERT_TRUE(bool(AST));
+ CheckCallHierarchy(*AST, Caller1C.point(), testPath("caller1.cc"));
+
+ // Check that invoking from the declaration site works.
+ AST = Workspace.openFile("callee.hh");
+ ASSERT_TRUE(bool(AST));
+ CheckCallHierarchy(*AST, CalleeH.point(), testPath("callee.hh"));
+
+ // Check that invoking from the definition site works.
+ AST = Workspace.openFile("callee.cc");
+ ASSERT_TRUE(bool(AST));
+ CheckCallHierarchy(*AST, CalleeC.point(), testPath("callee.cc"));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang
Index: clang-tools-extra/clangd/unittests/CMakeLists.txt
===================================================================
--- clang-tools-extra/clangd/unittests/CMakeLists.txt
+++ clang-tools-extra/clangd/unittests/CMakeLists.txt
@@ -36,6 +36,7 @@
Annotations.cpp
ASTTests.cpp
BackgroundIndexTests.cpp
+ CallHierarchyTests.cpp
CanonicalIncludesTests.cpp
ClangdTests.cpp
ClangdLSPServerTests.cpp
Index: clang-tools-extra/clangd/XRefs.h
===================================================================
--- clang-tools-extra/clangd/XRefs.h
+++ clang-tools-extra/clangd/XRefs.h
@@ -105,6 +105,17 @@
TypeHierarchyDirection Direction,
const SymbolIndex *Index);
+/// Get call hierarchy information at \p Pos.
+llvm::Optional<std::vector<CallHierarchyItem>>
+prepareCallHierarchy(ParsedAST &AST, Position Pos, const SymbolIndex *Index,
+ PathRef TUPath);
+
+llvm::Optional<std::vector<CallHierarchyIncomingCall>>
+incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index);
+
+llvm::Optional<std::vector<CallHierarchyOutgoingCall>>
+outgoingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index);
+
/// Returns all decls that are referenced in the \p FD except local symbols.
llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
const FunctionDecl *FD);
Index: clang-tools-extra/clangd/XRefs.cpp
===================================================================
--- clang-tools-extra/clangd/XRefs.cpp
+++ clang-tools-extra/clangd/XRefs.cpp
@@ -47,6 +47,7 @@
#include "clang/Index/USRGeneration.h"
#include "clang/Tooling/Syntax/Tokens.h"
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
@@ -1313,9 +1314,8 @@
return THI;
}
-static Optional<TypeHierarchyItem>
-symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index,
- PathRef TUPath) {
+static Optional<TypeHierarchyItem> symbolToTypeHierarchyItem(const Symbol &S,
+ PathRef TUPath) {
auto Loc = symbolToLocation(S, TUPath);
if (!Loc) {
log("Type hierarchy: {0}", Loc.takeError());
@@ -1346,7 +1346,7 @@
Req.Predicate = RelationKind::BaseOf;
Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
if (Optional<TypeHierarchyItem> ChildSym =
- symbolToTypeHierarchyItem(Object, Index, TUPath)) {
+ symbolToTypeHierarchyItem(Object, TUPath)) {
if (Levels > 1) {
ChildSym->children.emplace();
fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath);
@@ -1540,6 +1540,157 @@
}
}
+static llvm::Optional<CallHierarchyItem>
+declToCallHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
+ auto &SM = Ctx.getSourceManager();
+ SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager());
+ SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
+ SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
+ const auto DeclRange =
+ toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});
+ if (!DeclRange)
+ return llvm::None;
+ auto FilePath =
+ getCanonicalPath(SM.getFileEntryForID(SM.getFileID(NameLoc)), SM);
+ auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
+ if (!FilePath || !TUPath)
+ return llvm::None; // Not useful without a uri.
+
+ Position NameBegin = sourceLocToPosition(SM, NameLoc);
+ Position NameEnd = sourceLocToPosition(
+ SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
+
+ index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
+ // FIXME: this is not classifying constructors, destructors and operators
+ // correctly (they're all "methods").
+ SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
+
+ CallHierarchyItem CHI;
+ // We need to print the fully qualified name, otherwise we can't recover
+ // the symbol from the CallHierarchyItem.
+ CHI.Name = printQualifiedName(ND);
+ CHI.Kind = SK;
+ if (ND.isDeprecated()) {
+ CHI.Tags.push_back(SymbolTag::Deprecated);
+ }
+ CHI.Rng = Range{sourceLocToPosition(SM, DeclRange->getBegin()),
+ sourceLocToPosition(SM, DeclRange->getEnd())};
+ CHI.SelectionRange = Range{NameBegin, NameEnd};
+ if (!CHI.Rng.contains(CHI.Rng)) {
+ // 'selectionRange' must be contained in 'range', so in cases where clang
+ // reports unrelated ranges we need to reconcile somehow.
+ CHI.Rng = CHI.SelectionRange;
+ }
+
+ CHI.Uri = URIForFile::canonicalize(*FilePath, *TUPath);
+
+ // Compute the SymbolID and store it in the 'data' field.
+ // This allows typeHierarchy/resolve to be used to
+ // resolve children of items returned in a previous request
+ // for parents.
+ if (auto ID = getSymbolID(&ND)) {
+ CHI.Data = ID.str();
+ }
+
+ return CHI;
+}
+
+llvm::Optional<std::vector<CallHierarchyItem>>
+prepareCallHierarchy(ParsedAST &AST, Position Pos, const SymbolIndex *Index,
+ PathRef TUPath) {
+ const auto &SM = AST.getSourceManager();
+ auto Loc = sourceLocationInMainFile(SM, Pos);
+ if (!Loc) {
+ llvm::consumeError(Loc.takeError());
+ return llvm::None;
+ }
+ std::vector<CallHierarchyItem> Result;
+ for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) {
+ if (Decl->isFunctionOrFunctionTemplate()) {
+ if (auto CHI = declToCallHierarchyItem(AST.getASTContext(), *Decl))
+ Result.push_back(*std::move(CHI));
+ }
+ }
+ return Result;
+}
+
+llvm::Optional<CallHierarchyItem> symbolToCallHierarchyItem(const Symbol &S,
+ PathRef TUPath) {
+ auto Loc = symbolToLocation(S, TUPath);
+ if (!Loc) {
+ log("Type hierarchy: {0}", Loc.takeError());
+ return llvm::None;
+ }
+ CallHierarchyItem CHI;
+ CHI.Name = std::string(S.Name);
+ CHI.Kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
+ if (S.Flags & Symbol::Deprecated)
+ CHI.Tags.push_back(SymbolTag::Deprecated);
+ CHI.Detail = S.Signature.str();
+ CHI.SelectionRange = Loc->range;
+ // FIXME: Populate 'range' correctly
+ // (https://github.com/clangd/clangd/issues/59).
+ CHI.Rng = CHI.SelectionRange;
+ CHI.Uri = Loc->uri;
+ // Store the SymbolID in the 'data' field. The client will
+ // send this back in incomingCalls and outgoingCalls, allowing us to
+ // continue resolving additional levels of the type hierarchy.
+ CHI.Data = S.ID.str();
+
+ return std::move(CHI);
+}
+
+llvm::Optional<std::vector<CallHierarchyIncomingCall>>
+incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
+ if (!Index || !Item.Data)
+ return llvm::None;
+ Expected<SymbolID> ID = SymbolID::fromStr(*Item.Data);
+ if (!ID)
+ return llvm::None;
+ RefsRequest Request;
+ Request.IDs.insert(*ID);
+ // FIXME: Perhaps we should be even more specific and introduce a
+ // RefKind for calls, and use that?
+ Request.Filter = RefKind::Reference;
+ // Initially store the results in a map keyed by SymbolID.
+ // This allows us to group different calls with the same caller
+ // into the same CallHierarchyIncomingCall.
+ llvm::DenseMap<SymbolID, CallHierarchyIncomingCall> ResultMap;
+ Index->refs(Request, [&](const Ref &R) {
+ if (auto Loc = indexToLSPLocation(R.Location, Item.Uri.file())) {
+ LookupRequest Lookup;
+ Lookup.IDs.insert(R.Container);
+ Index->lookup(Lookup, [&](const Symbol &Caller) {
+ // See if we already have a CallHierarchyIncomingCall for this caller.
+ auto It = ResultMap.find(Caller.ID);
+ if (It == ResultMap.end()) {
+ // If not, try to create one.
+ if (auto CHI = symbolToCallHierarchyItem(Caller, Item.Uri.file())) {
+ CallHierarchyIncomingCall Call;
+ Call.From = *CHI;
+ It = ResultMap.insert({Caller.ID, std::move(Call)}).first;
+ }
+ }
+ if (It != ResultMap.end()) {
+ It->second.FromRanges.push_back(Loc->range);
+ }
+ });
+ }
+ });
+ // Flatten the results into a vector.
+ std::vector<CallHierarchyIncomingCall> Results;
+ for (auto &&Entry : ResultMap) {
+ Results.push_back(std::move(Entry.second));
+ }
+ return Results;
+}
+
+llvm::Optional<std::vector<CallHierarchyOutgoingCall>>
+outgoingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
+ // TODO: Implement.
+ return llvm::None;
+}
+
llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
const FunctionDecl *FD) {
if (!FD->hasBody())
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
