[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

1394

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

1651

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)

1711

can we log the error instead?

1716

nit: early exit if (!FuncOrFuncTempl)continue;

1724

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

1728

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

1755

the error needs to be consumed (preferably by logging)

1759

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?

1767

early exit, also the error needs to be consumed

1770

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

114

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

115

why do we need the index in this one?

119

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

1394

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

114

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

1396

nit: redundant braces

1404

nit: merge the two conditions and drop the braces.

1412

can you qualify Optional here and elsewhere?

1433–1446

nit: drop std::move

1439

nit: redundant braces

1448

nit: again merge conditions and drop braces

1665

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

1674

nit: auto ID

1691

... by SymbolID of the caller.

1694

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.

1705

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

1716

why don't we assert this instead?

clang-tools-extra/clangd/XRefs.h

114

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

114

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

114

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

1694

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

114

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

1665

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

86

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

86

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

[nridge]

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

86

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.
+std::vector<CallHierarchyItem>
+prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath);
+
+std::vector<CallHierarchyIncomingCall>
+incomingCalls(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"

 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LocatedSymbol &S) {
   OS << S.Name << ": " << S.PreferredDeclaration;
   if (S.Definition)
     OS << " def=" << *S.Definition;
   return OS;
 }
 
-// FIXME(nridge): Reduce duplication between this function and declToSym().
-static llvm::Optional<TypeHierarchyItem>
-declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
+template <typename HierarchyItem>
+static llvm::Optional<HierarchyItem> 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()));
   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);
 
-  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()),
+  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<TypeHierarchyItem>
+declToTypeHierarchyItem(const NamedDecl &ND) {
+  auto Result = declToHierarchyItem<TypeHierarchyItem>(ND);
+  if (Result)
+    Result->deprecated = ND.isDeprecated();
+  return Result;
 }
 
-static Optional<TypeHierarchyItem>
-symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index,
+static llvm::Optional<CallHierarchyItem>
+declToCallHierarchyItem(const NamedDecl &ND) {
+  auto Result = declToHierarchyItem<CallHierarchyItem>(ND);
+  if (Result && ND.isDeprecated())
+    Result->tags.push_back(SymbolTag::Deprecated);
+  return Result;
+}
+
+template <typename HierarchyItem>
+static llvm::Optional<HierarchyItem> 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<TypeHierarchyItem>
+symbolToTypeHierarchyItem(const Symbol &S, PathRef TUPath) {
+  auto Result = symbolToHierarchyItem<TypeHierarchyItem>(S, TUPath);
+  if (Result)
+    Result->deprecated = (S.Flags & Symbol::Deprecated);
+  return Result;
+}
+
+static llvm::Optional<CallHierarchyItem>
+symbolToCallHierarchyItem(const Symbol &S, PathRef TUPath) {
+  auto Result = symbolToHierarchyItem<CallHierarchyItem>(S, TUPath);
+  if (Result && (S.Flags & Symbol::Deprecated))
+    Result->tags.push_back(SymbolTag::Deprecated);
+  return Result;
 }
 
 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));
     }
   });
 }
static void fillSuperTypes(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx,
   if (Pattern) {
     if (!RPSet.insert(Pattern).second) {
       return;
     }
   }
 
   for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {
     if (Optional<TypeHierarchyItem> ParentSym =
-            declToTypeHierarchyItem(ASTCtx, *ParentDecl)) {
+            declToTypeHierarchyItem(*ParentDecl)) {
       ParentSym->parents.emplace();
       fillSuperTypes(*ParentDecl, ASTCtx, *ParentSym->parents, RPSet);
       SuperTypes.emplace_back(std::move(*ParentSym));
     }
   }
 
   if (Pattern) {
     RPSet.erase(Pattern);
getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
   // otherwise the type hierarchy item would misleadingly contain the
   // specialization parameters, while the children would involve classes
   // that derive from other specializations of the template.
   if (WantChildren) {
     if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))
       CXXRD = CTSD->getTemplateInstantiationPattern();
   }
 
-  Optional<TypeHierarchyItem> Result =
-      declToTypeHierarchyItem(AST.getASTContext(), *CXXRD);
+  Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(*CXXRD);
   if (!Result)
     return Result;
 
   if (WantParents) {
     Result->parents.emplace();
 
     RecursionProtectionSet RPSet;
     fillSuperTypes(*CXXRD, AST.getASTContext(), *Result->parents, RPSet);
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());
     }
   }
 }
 
+std::vector<CallHierarchyItem>
+prepareCallHierarchy(ParsedAST &AST, Position Pos, PathRef TUPath) {
+  std::vector<CallHierarchyItem> 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<CallHierarchyIncomingCall>
+incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
+  std::vector<CallHierarchyIncomingCall> 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<SymbolID, std::vector<Range>> 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<Range>{}).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<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();
+
+  std::vector<CallHierarchyItem> 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<CallHierarchyItem> 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<CallHierarchyItem> 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<CallHierarchyItem> 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

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) {