diff --git a/clang-tools-extra/clangd/XRefs.h b/clang-tools-extra/clangd/XRefs.h --- a/clang-tools-extra/clangd/XRefs.h +++ b/clang-tools-extra/clangd/XRefs.h @@ -110,6 +110,13 @@ TypeHierarchyDirection Direction, const SymbolIndex *Index); +/// Get call hierarchy information at \p Pos. +std::vector +prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath); + +std::vector +incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index); + /// Returns all decls that are referenced in the \p FD except local symbols. llvm::DenseSet getNonLocalDeclRefs(ParsedAST &AST, const FunctionDecl *FD); diff --git a/clang-tools-extra/clangd/XRefs.cpp b/clang-tools-extra/clangd/XRefs.cpp --- a/clang-tools-extra/clangd/XRefs.cpp +++ b/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" @@ -1339,9 +1340,9 @@ return OS; } -// FIXME(nridge): Reduce duplication between this function and declToSym(). -static llvm::Optional -declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) { +template +static llvm::Optional declToHierarchyItem(const NamedDecl &ND) { + ASTContext &Ctx = ND.getASTContext(); auto &SM = Ctx.getSourceManager(); SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager()); SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc())); @@ -1365,54 +1366,84 @@ // correctly. SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind); - TypeHierarchyItem THI; - THI.name = printName(Ctx, ND); - THI.kind = SK; - THI.deprecated = ND.isDeprecated(); - THI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()), - sourceLocToPosition(SM, DeclRange->getEnd())}; - THI.selectionRange = Range{NameBegin, NameEnd}; - if (!THI.range.contains(THI.selectionRange)) { + HierarchyItem HI; + HI.name = printName(Ctx, ND); + HI.kind = SK; + HI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()), + sourceLocToPosition(SM, DeclRange->getEnd())}; + HI.selectionRange = Range{NameBegin, NameEnd}; + if (!HI.range.contains(HI.selectionRange)) { // 'selectionRange' must be contained in 'range', so in cases where clang // reports unrelated ranges we need to reconcile somehow. - THI.range = THI.selectionRange; + HI.range = HI.selectionRange; } - THI.uri = URIForFile::canonicalize(*FilePath, *TUPath); + HI.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)) - THI.data = ID.str(); + HI.data = ID.str(); + + return HI; +} - return THI; +static llvm::Optional +declToTypeHierarchyItem(const NamedDecl &ND) { + auto Result = declToHierarchyItem(ND); + if (Result) + Result->deprecated = ND.isDeprecated(); + return Result; } -static Optional -symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index, - PathRef TUPath) { +static llvm::Optional +declToCallHierarchyItem(const NamedDecl &ND) { + auto Result = declToHierarchyItem(ND); + if (Result && ND.isDeprecated()) + Result->tags.push_back(SymbolTag::Deprecated); + return Result; +} + +template +static llvm::Optional symbolToHierarchyItem(const Symbol &S, + PathRef TUPath) { auto Loc = symbolToLocation(S, TUPath); if (!Loc) { - log("Type hierarchy: {0}", Loc.takeError()); + elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError()); return llvm::None; } - TypeHierarchyItem THI; - THI.name = std::string(S.Name); - THI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind); - THI.deprecated = (S.Flags & Symbol::Deprecated); - THI.selectionRange = Loc->range; + HierarchyItem HI; + HI.name = std::string(S.Name); + HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind); + HI.selectionRange = Loc->range; // FIXME: Populate 'range' correctly // (https://github.com/clangd/clangd/issues/59). - THI.range = THI.selectionRange; - THI.uri = Loc->uri; + HI.range = HI.selectionRange; + HI.uri = Loc->uri; // Store the SymbolID in the 'data' field. The client will - // send this back in typeHierarchy/resolve, allowing us to - // continue resolving additional levels of the type hierarchy. - THI.data = S.ID.str(); + // send this back in requests to resolve additional levels + // of the hierarchy. + HI.data = S.ID.str(); + + return HI; +} - return std::move(THI); +static llvm::Optional +symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) { + auto Result = symbolToHierarchyItem(S, TUPath); + if (Result) + Result->deprecated = (S.Flags & Symbol::Deprecated); + return Result; +} + +static llvm::Optional +symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) { + auto Result = symbolToHierarchyItem(S, TUPath); + if (Result && (S.Flags & Symbol::Deprecated)) + Result->tags.push_back(SymbolTag::Deprecated); + return Result; } static void fillSubTypes(const SymbolID &ID, @@ -1423,7 +1454,7 @@ Req.Predicate = RelationKind::BaseOf; Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { if (Optional ChildSym = - symbolToTypeHierarchyItem(Object, Index, TUPath)) { + symbolToTypeHierarchyItem(Object, TUPath)) { if (Levels > 1) { ChildSym->children.emplace(); fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath); @@ -1452,7 +1483,7 @@ for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) { if (Optional ParentSym = - declToTypeHierarchyItem(ASTCtx, *ParentDecl)) { + declToTypeHierarchyItem(*ParentDecl)) { ParentSym->parents.emplace(); fillSuperTypes(*ParentDecl, ASTCtx, *ParentSym->parents, RPSet); SuperTypes.emplace_back(std::move(*ParentSym)); @@ -1574,8 +1605,7 @@ CXXRD = CTSD->getTemplateInstantiationPattern(); } - Optional Result = - declToTypeHierarchyItem(AST.getASTContext(), *CXXRD); + Optional Result = declToTypeHierarchyItem(*CXXRD); if (!Result) return Result; @@ -1617,6 +1647,78 @@ } } +std::vector +prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) { + std::vector Result; + const auto &SM = AST.getSourceManager(); + auto Loc = sourceLocationInMainFile(SM, Pos); + if (!Loc) { + elog("prepareCallHierarchy failed to convert position to source location: " + "{0}", + Loc.takeError()); + return Result; + } + for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) { + if (!Decl->isFunctionOrFunctionTemplate()) + continue; + if (auto CHI = declToCallHierarchyItem(*Decl)) + Result.emplace_back(std::move(*CHI)); + } + return Result; +} + +std::vector +incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) { + std::vector Results; + if (!Index || Item.data.empty()) + return Results; + auto ID = SymbolID::fromStr(Item.data); + if (!ID) { + elog("incomingCalls failed to find symbol: {0}", ID.takeError()); + return Results; + } + // In this function, we find incoming calls based on the index only. + // In principle, the AST could have more up-to-date information about + // occurrences within the current file. However, going from a SymbolID + // to an AST node isn't cheap, particularly when the declaration isn't + // in the main file. + // FIXME: Consider also using AST information when feasible. + RefsRequest Request; + Request.IDs.insert(*ID); + // We could restrict more specifically to calls by introducing a new RefKind, + // but non-call references (such as address-of-function) can still be + // interesting as they can indicate indirect calls. + Request.Filter = RefKind::Reference; + // Initially store the ranges in a map keyed by SymbolID of the caller. + // This allows us to group different calls with the same caller + // into the same CallHierarchyIncomingCall. + llvm::DenseMap> CallsIn; + // We can populate the ranges based on a refs request only. As we do so, we + // also accumulate the container IDs into a lookup request. + LookupRequest ContainerLookup; + Index->refs(Request, [&](const Ref &R) { + auto Loc = indexToLSPLocation(R.Location, Item.uri.file()); + if (!Loc) { + elog("incomingCalls failed to convert location: {0}", Loc.takeError()); + return; + } + auto It = CallsIn.try_emplace(R.Container, std::vector{}).first; + It->second.push_back(Loc->range); + + ContainerLookup.IDs.insert(R.Container); + }); + // Perform the lookup request and combine its results with CallsIn to + // get complete CallHierarchyIncomingCall objects. + Index->lookup(ContainerLookup, [&](const Symbol &Caller) { + auto It = CallsIn.find(Caller.ID); + assert(It != CallsIn.end()); + if (auto CHI = symbolToCallHierarchyItem(Caller, Item.uri.file())) + Results.push_back( + CallHierarchyIncomingCall{std::move(*CHI), std::move(It->second)}); + }); + return Results; +} + llvm::DenseSet getNonLocalDeclRefs(ParsedAST &AST, const FunctionDecl *FD) { if (!FD->hasBody()) diff --git a/clang-tools-extra/clangd/unittests/CMakeLists.txt b/clang-tools-extra/clangd/unittests/CMakeLists.txt --- a/clang-tools-extra/clangd/unittests/CMakeLists.txt +++ b/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 diff --git a/clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp b/clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp @@ -0,0 +1,256 @@ +//===-- 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 +::testing::Matcher From(ItemMatcher M) { + return Field(&CallHierarchyIncomingCall::from, M); +} +template +::testing::Matcher 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(); + + std::vector Items = + prepareCallHierarchy(AST, Source.point(), testPath(TU.Filename)); + EXPECT_THAT(Items, ElementsAre(WithName("callee"))); + auto IncomingLevel1 = incomingCalls(Items[0], Index.get()); + EXPECT_THAT(IncomingLevel1, + ElementsAre(AllOf(From(WithName("caller1")), + FromRanges(Source.range("Callee"))))); + + auto IncomingLevel2 = incomingCalls(IncomingLevel1[0].from, Index.get()); + 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()); + EXPECT_THAT(IncomingLevel3, + ElementsAre(AllOf(From(WithName("caller3")), + FromRanges(Source.range("Caller2"))))); + + auto IncomingLevel4 = incomingCalls(IncomingLevel3[0].from, Index.get()); + 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(); + + std::vector Items = + prepareCallHierarchy(AST, Source.point(), testPath(TU.Filename)); + EXPECT_THAT(Items, ElementsAre(WithName("callee"))); + auto IncomingLevel1 = incomingCalls(Items[0], Index.get()); + EXPECT_THAT(IncomingLevel1, + ElementsAre(AllOf(From(WithName("caller1")), + FromRanges(Source.range("Callee"))))); + + auto IncomingLevel2 = incomingCalls(IncomingLevel1[0].from, Index.get()); + 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(); + + std::vector Items = + prepareCallHierarchy(AST, Source.point(), testPath(TU.Filename)); + EXPECT_THAT(Items, ElementsAre(WithName("Waldo::find"))); + auto Incoming = incomingCalls(Items[0], Index.get()); + 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) { + std::vector Items = + prepareCallHierarchy(AST, Pos, TUPath); + EXPECT_THAT(Items, ElementsAre(WithName("callee"))); + auto IncomingLevel1 = incomingCalls(Items[0], Index.get()); + EXPECT_THAT(IncomingLevel1, + ElementsAre(AllOf(From(WithName("caller1")), + FromRanges(Caller1C.range())))); + + auto IncomingLevel2 = incomingCalls(IncomingLevel1[0].from, Index.get()); + 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()); + EXPECT_THAT(IncomingLevel3, + ElementsAre(AllOf(From(WithName("caller3")), + FromRanges(Caller3C.range("Caller2"))))); + + auto IncomingLevel4 = incomingCalls(IncomingLevel3[0].from, Index.get()); + 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 diff --git a/clang-tools-extra/clangd/unittests/TestTU.cpp b/clang-tools-extra/clangd/unittests/TestTU.cpp --- a/clang-tools-extra/clangd/unittests/TestTU.cpp +++ b/clang-tools-extra/clangd/unittests/TestTU.cpp @@ -156,7 +156,8 @@ std::unique_ptr TestTU::index() const { auto AST = build(); - auto Idx = std::make_unique(/*UseDex=*/true); + auto Idx = std::make_unique(/*UseDex=*/true, + /*CollectMainFileRefs=*/true); Idx->updatePreamble(testPath(Filename), /*Version=*/"null", AST.getASTContext(), AST.getPreprocessorPtr(), AST.getCanonicalIncludes());