[clangd] Call hierarchy (XRefs layer, incoming calls)

[nridge]

Summary

Support for outgoing calls is left for a future change.

[nridge]

Update a comment

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

1317

that's a great change to have, but maybe leave it out of this patch?

1544

can we rather have a template like:

template <typename HierarchyItem>
HierarchyItem fromDecl(const NamedDecl &ND) {
HierarchyItem Result;
auto &Ctx = ND.getASTContext();
....
return Result;
}

To merge this one with the declToCallHierarchy ? The only separate bit seems to be around deprecated. They can be set explicitly outside. (looks like we forgot to add the SymbolTag for deprecated here)

1604

can we log the error instead?

1609

nit: early exit if (!FuncOrFuncTempl)continue;

1617

this can be merged with the typehierarchy implementation using a similar template trick mentioned above.

1621

let's elog instead. I think just saying Failed to convert symbol to hierarchy item: {0} should be fine in the merged implementation.

1648

the error needs to be consumed (preferably by logging)

1652

i suppose the main problem is we might have false positives:

void foo();
void bar() {
 funcTakingFunc(&foo);
}

bar looks like it is calling foo, but it isn't. but i think it is useful, and probably the only place we can point out a potential indirect call without crazy static analysis. So even if we had separate kinds for call and mere references, i believe we would still surface both. Hence, can we just mention this caveat rather than putting a fixme here?

1660

early exit, also the error needs to be consumed

1663

instead of performing a lookup per reference, can we just accumulate the symbolids and do a single lookup after finding all the unique containers?

clang-tools-extra/clangd/XRefs.h

109

what's the distinction between empty and none return values ? (same for others)

110

why do we need the index in this one?

114

In theory AST will have more up-to-date information about ranges/occurrences within the current file. As dynamic index for it might be stale. (the same goes for typehierarchy, we've just forgot about it at the time).

But going from SymbolID to an AST node isn't cheap, especially when the declaration isn't inside the main file. So I suppose it is OK to move with an index only implementation for now, but we should leave a FIXME to remind us about the situation.

[nridge]

Address review comments

clang-tools-extra/clangd/XRefs.cpp

1317

Since we are unifying the function with symbolToCallHierarchyItem, and that didn't have an Index parameter, it made more sense to keep the removal.

clang-tools-extra/clangd/XRefs.h

109

Generally speaking, a None result means "the input was not recognized in some way", while an empty vector result means "there are no results for this input".

For prepareCallHierarchy, the inputs encode a source location, and the operation asks "give me CallHierarchyItems for suitable declarations (i.e. functions) at this location. So, None means "the source location could not be recognized" (sourceLocationInMainFile failed), while an empty result means "there are no declarations of functions at this location".

For incomingCalls and outgoingCalls, the inputs encode a declaration of a function, and the operation asks "give me its callers / callees". So, a None means "could not locate the function (i.e. symbol)", while an empty result means "this function has no callers / callees".

[nridge]

Update variable names and remove a commented declaration

[kadircet]

mostly LG, i haven't looked at the tests yet though.

clang-tools-extra/clangd/XRefs.cpp

1317

nit: redundant braces

1320

nit: merge the two conditions and drop the braces.

1328

can you qualify Optional here and elsewhere?

1338

nit: drop std::move

1344

nit: redundant braces

1353

nit: again merge conditions and drop braces

1558

Results.emplace_back(std::move(*CHI)) ?

1567

nit: auto ID

1584

... by SymbolID of the caller.

1587

nit: s/ResultMap/CallsIn ?

I would also suggest changing value type to SmallVector<Range, 1> that way rather than having a "partially filled" IncomingCall objects in the middle, you can create valid ones directly within the lookup.

1598

nit: auto It = ResultMap.try_emplace(R.Container, CallHierarchyIncomingCall{}).first

1609

why don't we assert this instead?

clang-tools-extra/clangd/XRefs.h

109

Generally speaking, a None result means "the input was not recognized in some way", while an empty vector result means "there are no results for this input".

Makes sense, but that sounds like an implementation detail. I don't see any difference between the two from caller's point of view. Even the logging happens inside the implementation. As for interpreting llvm::None by the caller, i believe it is subject to change, so unless we return an Expected, there's not much value in returning an Optional, and even in such a case, caller probably can't do much but propagate the error (maybe also try with Pos+/-1, but usually that's handled within the XRefs as well).

Returning an empty container is also coherent with rest of the APIs we have in XRefs.h.

So I believe we should drop the optionals here.

[nridge]

clang-tools-extra/clangd/XRefs.h

109

The protocol specifies return types of CallHierarchyItem[] | null for prepareCallHierarchy and CallHierarchyIncomingCall[] | null for incomingCalls.

The | null in there suggests that the protocol intends for there to be a semantic difference between an empty array and null, and that clients may want to do things differently in the two caes (e.g. show an "unable to compute call hierarchy" error dialog vs. show an emty tree).

[kadircet]

clang-tools-extra/clangd/XRefs.h

109

yes, that's indeed a possibility, and the same goes for other features like textDocument/{definition,declaration,references}. AFAICT, we don't signal the difference between "no results" and "something went wrong" for those, and haven't received any complaints yet. So I'd rather keep them coherent, and replace all of them if we see that there are clients taking different actions for real.

[nridge]

Address review comments

[nridge]

clang-tools-extra/clangd/XRefs.cpp

1587

I went with std::vector<Range> as we eventually need that for the final result, and we can move it from one place to another.

clang-tools-extra/clangd/XRefs.h

109

Ok, removed the Optional for consistency with other requests.

[kadircet]

This looks great! Thanks a lot for bearing with me and doing all of this!

clang-tools-extra/clangd/XRefs.cpp

1558

please put the deref inside std::move. as move semantics of Optional are optional (no pun intended :P), i.e. depends on LLVM_HAS_RVALUE_REFERENCE_THIS.

[nridge]

Address final review comment

[nridge]

Thank you for the reviews!

[nridge]

It looks like CallHierarchy.IncomingOneFile in failing on a few of the buildbots (e.g. clang-ppc64be-linux and clang-s390x-linux), while passing on most of them. I cannot reproduce the failure locally.

Any suggestions for what might be the cause, or how to investigate?

[kadircet]

clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp

87

the order of elements in IncomingLevel2 is not sorted, so on some buildbots you are receiving "caller3" as the first element of the result, and "caller2" in others.

sorry for missing it the first time, it might make sense to sort containers by name before returning from incomingCalls

[nridge]

clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp

87

Thanks for catching that! Patch at https://reviews.llvm.org/D92000

[nridge]

clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp

87

Sorry, wrong link, correct link is: https://reviews.llvm.org/D92009

clang-tools-extra/clangd/XRefs.h

 llvm::Optional<TypeHierarchyItem> getTypeHierarchy(
     ParsedAST &AST, Position Pos, int Resolve, TypeHierarchyDirection Direction,
     const SymbolIndex *Index = nullptr, PathRef TUPath = PathRef{});
 
 void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
                           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);
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H

clang-tools-extra/clangd/XRefs.cpp

 #include "clang/Basic/TokenKinds.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/IndexingOptions.h"
 #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"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
   // resolve children of items returned in a previous request
   // for parents.
   if (auto ID = getSymbolID(&ND))
     THI.data = ID.str();
 
   return THI;
 }
 
-static Optional<TypeHierarchyItem>
-symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index,
+static Optional<TypeHierarchyItem> symbolToTypeHierarchyItem(const Symbol &S,
                                                              PathRef TUPath) {
   auto Loc = symbolToLocation(S, TUPath);
   if (!Loc) {
     log("Type hierarchy: {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;
   // FIXME: Populate 'range' correctly
   // (https://github.com/clangd/clangd/issues/59).
   THI.range = THI.selectionRange;
   THI.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();
 
   return std::move(THI);
 }
 
 static void fillSubTypes(const SymbolID &ID,
                          std::vector<TypeHierarchyItem> &SubTypes,
                          const SymbolIndex *Index, int Levels, PathRef TUPath) {
   RelationsRequest Req;
   Req.Subjects.insert(ID);
   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);
       }
       SubTypes.emplace_back(std::move(*ChildSym));
     }
   });
 }
 
 using RecursionProtectionSet = llvm::SmallSet<const CXXRecordDecl *, 4>;
 
 static void fillSuperTypes(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx,
if (Index && Item.data) {
     // We store the item's SymbolID in the 'data' field, and the client
     // passes it back to us in typeHierarchy/resolve.
     if (Expected<SymbolID> ID = SymbolID::fromStr(*Item.data)) {
       fillSubTypes(*ID, *Item.children, Index, ResolveLevels, Item.uri.file());
     }
   }
 }
 
+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.
+  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())
     return {};
   llvm::DenseSet<const Decl *> DeclRefs;
   findExplicitReferences(FD, [&](ReferenceLoc Ref) {
     for (const Decl *D : Ref.Targets) {
       if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() &&
           !Ref.IsDecl)
         DeclRefs.insert(D);
     }
   });
   return DeclRefs;
 }
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/CMakeLists.txt

 include(${CMAKE_CURRENT_SOURCE_DIR}/../quality/CompletionModel.cmake)
 gen_decision_forest(${CMAKE_CURRENT_SOURCE_DIR}/decision_forest_model DecisionForestRuntimeTest ::ns1::ns2::test::Example)
 
 add_custom_target(ClangdUnitTests)
 add_unittest(ClangdUnitTests ClangdTests
   Annotations.cpp
   ASTTests.cpp
   BackgroundIndexTests.cpp
+  CallHierarchyTests.cpp
   CanonicalIncludesTests.cpp
   ClangdTests.cpp
   ClangdLSPServerTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   CollectMacrosTests.cpp
   CompileCommandsTests.cpp
   CompilerTests.cpp

clang-tools-extra/clangd/unittests/CallHierarchyTests.cpp

+//===-- 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

clang-tools-extra/clangd/unittests/TestTU.cpp

 
 RefSlab TestTU::headerRefs() const {
   auto AST = build();
   return std::get<1>(indexMainDecls(AST));
 }
 
 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());
   Idx->updateMain(testPath(Filename), AST);
   return std::move(Idx);
 }
 
 const Symbol &findSymbol(const SymbolSlab &Slab, llvm::StringRef QName) {