[clangd] Support outgoing calls in call hierarchy

[nridge]

Summary

The implementation is very close the the incoming
calls implementation. The results of the outgoing
calls are expected to be the exact symmetry of the
incoming calls.

[qchateau]

• Fix tests

[qchateau]

• Smaller reversed refs memory usage
• Fix Dex::estimateMemoryUsage

[qchateau]

Note: Build fails due to clang-tidy warnings in tests. I chose to keep the naming consistent with what's already in place rather than fix the clang-tidy warning.

[nridge]

Thanks for working on this!

I haven't looked at the whole patch in detail, but I looked at some parts (mainly the SymbolIndex API and what in-memory structures we store to implement it) and wrote a few thoughts.

clang-tools-extra/clangd/XRefs.cpp

1843

If memory usage of Dex::RevRefs becomes a concern, we could consider only storing the references that would pass this filter in the first place. That would trade off time spent building the reverse lookup (we'd have to do symbol lookups or keep around extra state to track the symbol kinds) for space savings.

clang-tools-extra/clangd/index/Index.h

85

As the protocol wants the outgoing calls grouped by symbol, we could consider storing them (and having the SymbolIndex API expose them) in that way.

The main motivation would be space savings on the storage side (Dex::RevRefs), as in the case of multiple calls to the same function we only need to store the target SymbolID once.

However, it may not be worth doing this, as having a large number of outgoing calls to the same target inside a given function is likely to be rare, and vectors have their own overhead. (It's also not clear to what extent the details of the LSP protocol should dictate the shape of the SymbolIndex API.)

133

Perhaps we should have a distinct request structure, for future extensibility?

clang-tools-extra/clangd/index/MemIndex.cpp

97

Looping over all refs seems expensive even for MemIndex. Perhaps we should have a reverse lookup table similar to RevRefs here as well?

[qchateau]

clang-tools-extra/clangd/XRefs.cpp

1843

I've used tried this patch with the whole llvm project indexed. If I remember correctly it's something in the like of 100MB, around 5-10% même usage of clangd. As such it's not very high but it's definitely not negligible, especially for a feature that's not used very often.

clang-tools-extra/clangd/index/Index.h

85

I indeed believe that I'd use more memory than it would save, but I did not try it.
Anyway I think the difference would be minimal, and I'd say we should choose what gives the "best" API

133

Sure, that makes sense

clang-tools-extra/clangd/index/MemIndex.cpp

97

That's pretty fast even on my laptop IIRC, and only used for outgoing calls atm.

[sammccall]

Thanks for looking into this feature!

I do have to ask a fairly naive question though - what's it useful for, beyond protocol completeness? The obvious alternative to a user is looking at a function's implementation, which is an extra context switch but also provides a lot more information. I'm having trouble understanding when this could be better enough to justify much extra complexity/resources.

(Adding a new method to the index interface seems like a fairly substantial thing, and 5-10% to index memory usage is substantial as you say).

[nridge]

I think that, as with incoming calls, the incremental value is in seeing the tree at a glance. So, you might query the outgoing calls for a function, expand the tree, and look over the transitive callees to see if the function ends up performing a certain type of operation (say, a filesystem access).

That said, I will admit that in ~10 years of using Eclipse CDT, which supports both incoming calls and outgoing calls, I can't recall using outgoing calls even once (whereas I did use incoming calls). Of course, other users' experiences may vary.

[qchateau]

You're right, I probably got carried away for the sake of completeness. Allocating extra memory for a feature nobody is going to use is definitely not worth it. Though maybe we can take advantage of what's already been done and if we remove the RevRefs map, and pay the full price of iterating all refs when refersTo is called, we still have this feature. Although slower, it shouldn't take more than a few 100's of milliseconds even on a big project. Which means the feature is usable, at least for most small to medium sized projects, at no extra cost for people who do not use it.

Would this be acceptable ?

[smekkley]

For what it's worth, outgoing call is useful for looking at grand children and jump immediately. Also, clangd doesn't runs on embedded devices, so extra memory allocation isn't a concern at all for most users. @sammccall which part of the code do you find very complex/concerning?

[sammccall]

Time to wake up an old review!

Going to put high-level thoughts on https://github.com/clangd/clangd/discussions/1206, but since one of them is memory usage I wanted to have a look at the concrete data structure here.

TL;DR: I think we can make this cheap enough we don't care about the extra memory. The simple lookup optimization below might be enough (probably not). Dropping non-callee refs from the data structure is likely enough, the deep lookup optimization is likely enough, doing both probably reduces memory usage vs today!

---

Lookup optimization (simple):

DenseMap<SymbolID, vector<RevRef>> is something like 56*containers + 16*refs bytes:

• a `pair<SymbolID, vector<RevRef>, which is 4 pointers per symbol, plus extra buckets so >7 pointers if I'm reading DenseMap right
• a RevRef per entry which is two pointers
• maybe some allocator overhead for all those little vectors? (IDK how allocators work in practice)

Dropping the hashtable and just storing a flat vector<RevRef> sorted by container eliminates the per-symbol costs for 16*refs bytes. If there were only 3-4 refs per function this would save 50%, but there's probably more. The tradeoff is binary search (with double-indirection for compare) instead of hash lookup, but still seems fast enough for what we want it for.

The elephant in the room is that most of these refs we're storing are not callees. If we were to drop those from the lookup structure as discussed inline above, then the ratio of refs:symbols goes down and this optimization becomes relatively more effective.

---

Lookup optimization (deeper): h/t @kadircet

I think it's easiest to explain as a pair of modifications to the current refs data structures (as checked-in, not the ones in this patch).

First: imagine we change RefSlab to produce:

• a big flat vector<Ref> grouped by target.
• a lookup structure consisting of a sorted vector<pair</*Target*/SymbolID, /*Offset*/int>>

This is smaller than our current representation: the lookup structure is 20 * targets bytes instead of the current ~40 * targets bytes and making the ref storage contiguous is ~free.

Clearly this supports lookup of refs for a target by binary searching over the lookup structure by target.

But observe that also given a Ref* we can find its target: binary search over the lookup structure searching for the right offset, rather than target.

Second: have the index compute a permutation of refs grouped by Container. Naively this is a vector<Ref*>, but since we made the array flat it can be vector<int>

Now we can look up the refs for a given container by binary searching within this permutation, as the container is stored in the Refs themselves.

For each result we have to do a second binary search in the lookup structure to get the target symbol, but we expect the #symbols per container to be small so this nesting isn't a great concern.

So the net cost vs HEAD is 4 * refs - 20 * targets bytes, which is less than a quarter of the version above. This takes us to ~2% increase which we can eat even if we store this info for all references.

The costs here are expensive reverse lookups (I don't think we care), slightly more expensive forward lookups (also OK I think), code complexity (*mostly* localized). Obviously this is all somewhat invasive...

(We discussed an even further squeeze: we could use the same trick to avoid our current 8 bytes inside the ref for the container. I think this leads to too many levels of nested binary searches)

clang-tools-extra/clangd/XRefs.cpp

1843

That would trade off time spent building the reverse lookup (we'd have to do symbol lookups or keep around extra state to track the symbol kinds) for space savings.

RefKind is a bitfield, so I think we could just tack on an extra Call bit at indexing time. Technically it's extra state, but it's cheap to compute and free to plumb around.

Then the tradeoff becomes: the index needs to know which refkinds to include in its reverse-lookup structure. In practical terms we could hard-code this, it's an ugly layering violation though. The prettiest version I can think of is to put a constant on RefersToRequest for the supported refkinds.

(A ridiculous answer that almost works is to build it dynamically on first use, based on the queried refkinds: this means only people who use outgoing call hierarchy would pay the memory cost! Unfortunately I think this gets too complicated when we consider threadsafety)

clang-tools-extra/clangd/index/Index.h

133

+1, also for clarity (we're changing the meaning of IDs too).

I'd also consider naming this request something more explicitly paired with refs, like containedRefs, reverseRefs, outgoingRefs. They're not great names in isolation, but I think the idea that this is a second query on the same data is worth emphasizing.

clang-tools-extra/clangd/index/MemIndex.cpp

97

MemIndex basically doesn't scale: it does fuzzyfind by iterating over all symbols. So this sounds likely never to matter in practice.

[nridge]

Thank you Sam for the suggested performance improvements, and outlining a way forward.

@qchateau, are you interested in updating the patch to implement some of the described optimizations / address other comments?

[qchateau]

I'm interested but I don't have enough free time these days. So if anyone wants to take it from there, feel free to reuse my commits (or not).
If I find myself with some free time and nobody else is working on this, I'll give it a shot

[nridge]

Rebased to apply to recent trunk

[nridge]

In D93829#4422090, @qchateau wrote:

So if anyone wants to take it from there, feel free to reuse my commits (or not).

I'm going to pick up this work and try to address Sam's review comments.

[nridge]

To be able to reason about the impact of various memory usage optimizations, I took some baseline measurements.

I used a workload consisting of the LLVM codebase, with the compile_commands.json entries filtered to those containing clang/lib or clang-tools-extra/clangd, a total of 1082 source files. (This is what I happen to use for local clangd development, but I also think it strikes a good balance between being large enough to be representative but not so large that taking local measurements is too much of a hassle.)

I measured the memory usage of the background index by performing the clangd: show memory usage command.

Without this patch (baseline): background_index 560MB (index 372MB, slabs 187MB)
With the patch in its current state: background_index 606MB (index 418MB, slabs 187MB)

This is an increase of (606 - 560) / 560 = 8.2% over baseline, which is consistent with previous reports of 5-10%.

My plan going forward is to implement some of the suggested memory usage optimizations, and measure their impact.

[nridge]

Implement optimization to filter the refs stored in RevRefs to calls only

[nridge]

The updated patch implements one of the optimizations discussed during review, namely filtering the Refs stored in the RevRefs data structure to just those that could be calls.

To this end, the patch introduces a new RefKind, RefKind::Call, as discussed.

With the updated patch, memory usage on the same workload is: background_index 579MB (index 392MB, slabs 187MB).

This is an increase of (579 - 560) / 560 = 3.4% over baseline (down from 8.2% with the original patch!)

[nridge]

Implement the "simple lookup optimization"

[nridge]

The updated patch additionally implements the "simple lookup optimization" discussed in the review.

With this version, memory usage on the test workload is: background_index 574MB (index 387MB, slabs 187MB).

This is an increase of (574 - 560) / 560 = 2.5% over baseline (down from 8.2% with the original patch)

[nridge]

Address other review comments

[nridge]

@sammccall, how would you feel about proceeding with the patch in its current state, with the memory usage increase brought down from 8.2% to 2.5% thanks to the combination of the simple lookup optimization + RefKind filtering, and leaving the "deep lookup optimization" to be explored in a future change?

clang-tools-extra/clangd/ClangdLSPServer.cpp

 //===--- ClangdLSPServer.cpp - LSP server ------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
void ClangdLSPServer::onCallHierarchyIncomingCalls(
     const CallHierarchyIncomingCallsParams &Params,
     Callback<std::vector<CallHierarchyIncomingCall>> Reply) {
   Server->incomingCalls(Params.item, std::move(Reply));
 }
 
 void ClangdLSPServer::onCallHierarchyOutgoingCalls(
     const CallHierarchyOutgoingCallsParams &Params,
     Callback<std::vector<CallHierarchyOutgoingCall>> Reply) {
-  // FIXME: To be implemented.
-  Reply(std::vector<CallHierarchyOutgoingCall>{});
+  Server->outgoingCalls(Params.item, std::move(Reply));
 }
 
 void ClangdLSPServer::applyConfiguration(
     const ConfigurationSettings &Settings) {
   // Per-file update to the compilation database.
   llvm::StringSet<> ModifiedFiles;
   for (auto &Entry : Settings.compilationDatabaseChanges) {
     PathRef File = Entry.first;

clang-tools-extra/clangd/ClangdServer.h

 //===--- ClangdServer.h - Main clangd server code ----------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
public:
   /// Get information about call hierarchy for a given position.
   void prepareCallHierarchy(PathRef File, Position Pos,
                             Callback<std::vector<CallHierarchyItem>> CB);
 
   /// Resolve incoming calls for a given call hierarchy item.
   void incomingCalls(const CallHierarchyItem &Item,
                      Callback<std::vector<CallHierarchyIncomingCall>>);
 
+  /// Resolve outgoing calls for a given call hierarchy item.
+  void outgoingCalls(const CallHierarchyItem &Item,
+                     Callback<std::vector<CallHierarchyOutgoingCall>>);
+
   /// Retrieve the top symbols from the workspace matching a query.
   void workspaceSymbols(StringRef Query, int Limit,
                         Callback<std::vector<SymbolInformation>> CB);
 
   /// Retrieve the symbols within the specified file.
   void documentSymbols(StringRef File,
                        Callback<std::vector<DocumentSymbol>> CB);
 

clang-tools-extra/clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- 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
 //
 //===-------------------------------------------------------------------===//
 
void ClangdServer::incomingCalls(
     const CallHierarchyItem &Item,
     Callback<std::vector<CallHierarchyIncomingCall>> CB) {
   WorkScheduler.run("Incoming Calls", "",
                     [CB = std::move(CB), Item, this]() mutable {
                       CB(clangd::incomingCalls(Item, Index));
                     });
 }
 
+void ClangdServer::outgoingCalls(
+    const CallHierarchyItem &Item,
+    Callback<std::vector<CallHierarchyOutgoingCall>> CB) {
+  WorkScheduler.run("Outgoing Calls", "",
+                    [CB = std::move(CB), Item, this]() mutable {
+                      CB(clangd::outgoingCalls(Item, Index));
+                    });
+}
+
 void ClangdServer::onFileEvent(const DidChangeWatchedFilesParams &Params) {
   // FIXME: Do nothing for now. This will be used for indexing and potentially
   // invalidating other caches.
 }
 
 void ClangdServer::workspaceSymbols(
     llvm::StringRef Query, int Limit,
     Callback<std::vector<SymbolInformation>> CB) {

clang-tools-extra/clangd/XRefs.h

 //===--- XRefs.h -------------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //

 
 /// 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);
 
+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

 //===--- XRefs.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 "XRefs.h"
static llvm::Optional<HierarchyItem> symbolToHierarchyItem(const Symbol &S,
                                                            PathRef TUPath) {
   auto Loc = symbolToLocation(S, TUPath);
   if (!Loc) {
     elog("Failed to convert symbol to hierarchy item: {0}", Loc.takeError());
     return llvm::None;
   }
   HierarchyItem HI;
   HI.name = std::string(S.Name);
+  HI.detail = (S.Scope + S.Name).str();
   HI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
   HI.selectionRange = Loc->range;
   // FIXME: Populate 'range' correctly
   // (https://github.com/clangd/clangd/issues/59).
   HI.range = HI.selectionRange;
   HI.uri = Loc->uri;
   // Store the SymbolID in the 'data' field. The client will
   // send this back in requests to resolve additional levels
incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
   // Sort results by name of container.
   llvm::sort(Results, [](const CallHierarchyIncomingCall &A,
                          const CallHierarchyIncomingCall &B) {
     return A.from.name < B.from.name;
   });
   return Results;
 }
 
+std::vector<CallHierarchyOutgoingCall>
+outgoingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
+  std::vector<CallHierarchyOutgoingCall> Results;
+  if (!Index || Item.data.empty())
+    return Results;
+  auto ID = SymbolID::fromStr(Item.data);
+  if (!ID) {
+    elog("outgoingCalls failed to find symbol: {0}", ID.takeError());
+    return Results;
+  }
+  // In this function, we find outgoing calls based on the index only.
+  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 callee.
+  // This allows us to group different calls to the same function
+  // into the same CallHierarchyOutgoingCall.
+  llvm::DenseMap<SymbolID, std::vector<Range>> CallsOut;
+  // We can populate the ranges based on a refs request only. As we do so, we
+  // also accumulate the callee IDs into a lookup request.
+  LookupRequest CallsOutLookup;
+  Index->refersTo(Request, [&](const auto &R) {
+    auto Loc = indexToLSPLocation(R.Location, Item.uri.file());
+    if (!Loc) {
+      elog("outgoingCalls failed to convert location: {0}", Loc.takeError());
+      return;
+    }
+    auto It = CallsOut.try_emplace(R.Symbol, std::vector<Range>{}).first;
+    It->second.push_back(Loc->range);
+
+    CallsOutLookup.IDs.insert(R.Symbol);
+  });
+  // Perform the lookup request and combine its results with CallsOut to
+  // get complete CallHierarchyOutgoingCall objects.
+  Index->lookup(CallsOutLookup, [&](const Symbol &Callee) {
+    // Filter references to only keep function calls
+    using SK = index::SymbolKind;
+    auto Kind = Callee.SymInfo.Kind;
+    if (Kind != SK::Function && Kind != SK::InstanceMethod &&
+        Kind != SK::ClassMethod && Kind != SK::StaticMethod &&
+        Kind != SK::Constructor && Kind != SK::Destructor &&
+        Kind != SK::ConversionFunction)
+      return;
+
+    auto It = CallsOut.find(Callee.ID);
+    assert(It != CallsOut.end());
+    if (auto CHI = symbolToCallHierarchyItem(Callee, Item.uri.file()))
+      Results.push_back(
+          CallHierarchyOutgoingCall{std::move(*CHI), std::move(It->second)});
+  });
+  // Sort results by name of the callee.
+  llvm::sort(Results, [](const CallHierarchyOutgoingCall &A,
+                         const CallHierarchyOutgoingCall &B) {
+    return A.to.name < B.to.name;
+  });
+  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/index/Index.h

 //===--- Index.h -------------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 

 
 struct RelationsRequest {
   llvm::DenseSet<SymbolID> Subjects;
   RelationKind Predicate;
   /// If set, limit the number of relations returned from the index.
   llvm::Optional<uint32_t> Limit;
 };
 
+struct RefersToResult {
+  /// The source location where the symbol is named.
+  SymbolLocation Location;
+  RefKind Kind = RefKind::Unknown;
+  /// The ID of the symbol which is referred to
+  SymbolID Symbol;
+};
+
 /// Interface for symbol indexes that can be used for searching or
 /// matching symbols among a set of symbols based on names or unique IDs.
 class SymbolIndex {
 public:
   virtual ~SymbolIndex() = default;
 
   /// Matches symbols in the index fuzzily and applies \p Callback on
   /// each matched symbol before returning.
public:
   ///
   /// Results should be returned in arbitrary order.
   /// The returned result must be deep-copied if it's used outside Callback.
   ///
   /// Returns true if there will be more results (limited by Req.Limit);
   virtual bool refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const = 0;
 
+  /// Find all symbols that are referenced by a symbol and apply
+  /// \p Callback on each result.
+  ///
+  /// Results should be returned in arbitrary order.
+  /// The returned result must be deep-copied if it's used outside Callback.
+  ///
+  /// Returns true if there will be more results (limited by Req.Limit);
+  virtual bool
+  refersTo(const RefsRequest &Req,
+           llvm::function_ref<void(const RefersToResult &)> Callback) const = 0;
+
   /// Finds all relations (S, P, O) stored in the index such that S is among
   /// Req.Subjects and P is Req.Predicate, and invokes \p Callback for (S, O) in
   /// each.
   virtual void relations(
       const RelationsRequest &Req,
       llvm::function_ref<void(const SymbolID &Subject, const Symbol &Object)>
           Callback) const = 0;
 
public:
   // SymbolIndex methods delegate to the current index, which is kept alive
   // until the call returns (even if reset() is called).
   bool fuzzyFind(const FuzzyFindRequest &,
                  llvm::function_ref<void(const Symbol &)>) const override;
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override;
   bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
+  bool
+  refersTo(const RefsRequest &,
+           llvm::function_ref<void(const RefersToResult &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
 
   llvm::unique_function<bool(llvm::StringRef) const>
   indexedFiles() const override;
 
   size_t estimateMemoryUsage() const override;

clang-tools-extra/clangd/index/Index.cpp

 //===--- Index.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
 //
 //===----------------------------------------------------------------------===//
 

 void SwapIndex::lookup(const LookupRequest &R,
                        llvm::function_ref<void(const Symbol &)> CB) const {
   return snapshot()->lookup(R, CB);
 }
 bool SwapIndex::refs(const RefsRequest &R,
                      llvm::function_ref<void(const Ref &)> CB) const {
   return snapshot()->refs(R, CB);
 }
+bool SwapIndex::refersTo(
+    const RefsRequest &R,
+    llvm::function_ref<void(const RefersToResult &)> CB) const {
+  return snapshot()->refersTo(R, CB);
+}
 void SwapIndex::relations(
     const RelationsRequest &R,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> CB) const {
   return snapshot()->relations(R, CB);
 }
 
 llvm::unique_function<bool(llvm::StringRef) const>
 SwapIndex::indexedFiles() const {

clang-tools-extra/clangd/index/MemIndex.h

 //===--- MemIndex.h - Dynamic in-memory symbol index. -------------- 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
 //
 //===----------------------------------------------------------------------===//
 
fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   bool refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
+  bool refersTo(
+      const RefsRequest &Req,
+      llvm::function_ref<void(const RefersToResult &)> Callback) const override;
+
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
   llvm::unique_function<bool(llvm::StringRef) const>
   indexedFiles() const override;
 
   size_t estimateMemoryUsage() const override;

clang-tools-extra/clangd/index/MemIndex.cpp

 //===--- MemIndex.cpp - Dynamic in-memory symbol index. ----------*- 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
 //
 //===-------------------------------------------------------------------===//
 
for (const auto &O : SymRefs->second) {
         return true; // More refs were available.
       --Remaining;
       Callback(O);
     }
   }
   return false; // We reported all refs.
 }
 
+bool MemIndex::refersTo(
+    const RefsRequest &Req,
+    llvm::function_ref<void(const RefersToResult &)> Callback) const {
+  trace::Span Tracer("MemIndex refersTo");
+  uint32_t Remaining =
+      Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  for (const auto &Pair : Refs) {
+    for (const auto &R : Pair.second) {
+      if (!static_cast<int>(Req.Filter & R.Kind) ||
+          !Req.IDs.contains(R.Container))
+        continue;
+      if (Remaining == 0)
+        return true; // More refs were available.
+      --Remaining;
+      Callback({R.Location, R.Kind, Pair.first});
+    }
+  }
+  return false; // We reported all refs.
+}
+
 void MemIndex::relations(
     const RelationsRequest &Req,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   for (const SymbolID &Subject : Req.Subjects) {
     LookupRequest LookupReq;
     auto It = Relations.find(

clang-tools-extra/clangd/index/Merge.h

 //===--- Merge.h -------------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
MergedIndex(const SymbolIndex *Dynamic, const SymbolIndex *Static)
       : Dynamic(Dynamic), Static(Static) {}
 
   bool fuzzyFind(const FuzzyFindRequest &,
                  llvm::function_ref<void(const Symbol &)>) const override;
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override;
   bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
+  bool
+  refersTo(const RefsRequest &,
+           llvm::function_ref<void(const RefersToResult &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
   llvm::unique_function<bool(llvm::StringRef) const>
   indexedFiles() const override;
   size_t estimateMemoryUsage() const override {
     return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
   }
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MERGE_H

clang-tools-extra/clangd/index/Merge.cpp

 //===--- Merge.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
 //
 //===----------------------------------------------------------------------===//
 
if (Remaining == 0) {
       return;
     }
     --Remaining;
     Callback(O);
   });
   return More || StaticHadMore;
 }
 
+bool MergedIndex::refersTo(
+    const RefsRequest &Req,
+    llvm::function_ref<void(const RefersToResult &)> Callback) const {
+  trace::Span Tracer("MergedIndex refersTo");
+  bool More = false;
+  uint32_t Remaining =
+      Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  // We don't want duplicated refs from the static/dynamic indexes,
+  // and we can't reliably deduplicate them because offsets may differ slightly.
+  // We consider the dynamic index authoritative and report all its refs,
+  // and only report static index refs from other files.
+  More |= Dynamic->refersTo(Req, [&](const auto &O) {
+    Callback(O);
+    assert(Remaining != 0);
+    --Remaining;
+  });
+  if (Remaining == 0 && More)
+    return More;
+  auto DynamicContainsFile = Dynamic->indexedFiles();
+  // We return less than Req.Limit if static index returns more refs for dirty
+  // files.
+  bool StaticHadMore = Static->refersTo(Req, [&](const auto &O) {
+    if (DynamicContainsFile(O.Location.FileURI))
+      return; // ignore refs that have been seen from dynamic index.
+    if (Remaining == 0) {
+      More = true;
+      return;
+    }
+    --Remaining;
+    Callback(O);
+  });
+  return More || StaticHadMore;
+}
+
 llvm::unique_function<bool(llvm::StringRef) const>
 MergedIndex::indexedFiles() const {
   return [DynamicContainsFile{Dynamic->indexedFiles()},
           StaticContainsFile{Static->indexedFiles()}](llvm::StringRef FileURI) {
     return DynamicContainsFile(FileURI) || StaticContainsFile(FileURI);
   };
 }
 

clang-tools-extra/clangd/index/ProjectAware.cpp

 //===--- ProjectAware.h ------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
public:
 
   /// Only queries the associated index with the current context.
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   /// Query all indexes while prioritizing the associated one (if any).
   bool refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
+  /// Query all indexes while prioritizing the associated one (if any).
+  bool refersTo(
+      const RefsRequest &Req,
+      llvm::function_ref<void(const RefersToResult &)> Callback) const override;
 
   /// Queries only the associates index when Req.RestrictForCodeCompletion is
   /// set, otherwise queries all.
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   /// Query all indexes while prioritizing the associated one (if any).
bool ProjectAwareIndex::refs(
     const RefsRequest &Req,
     llvm::function_ref<void(const Ref &)> Callback) const {
   trace::Span Tracer("ProjectAwareIndex::refs");
   if (auto *Idx = getIndex())
     return Idx->refs(Req, Callback);
   return false;
 }
 
+bool ProjectAwareIndex::refersTo(
+    const RefsRequest &Req,
+    llvm::function_ref<void(const RefersToResult &)> Callback) const {
+  trace::Span Tracer("ProjectAwareIndex::refersTo");
+  if (auto *Idx = getIndex())
+    return Idx->refersTo(Req, Callback);
+  return false;
+}
+
 bool ProjectAwareIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   trace::Span Tracer("ProjectAwareIndex::fuzzyFind");
   if (auto *Idx = getIndex())
     return Idx->fuzzyFind(Req, Callback);
   return false;
 }

clang-tools-extra/clangd/index/dex/Dex.h

 //===--- Dex.h - Dex Symbol Index Implementation ----------------*- 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
 //
 //===----------------------------------------------------------------------===//
 ///
fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   bool refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
+  bool refersTo(
+      const RefsRequest &Req,
+      llvm::function_ref<void(const RefersToResult &)> Callback) const override;
+
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
   llvm::unique_function<bool(llvm::StringRef) const>
   indexedFiles() const override;
 
   size_t estimateMemoryUsage() const override;
private:
   /// which contains all items which can be characterized by such search token.
   /// For example, if the search token is scope "std::", the corresponding
   /// posting list would contain all indices of symbols defined in namespace
   /// std. Inverted index is used to retrieve posting lists which are processed
   /// during the fuzzyFind process.
   llvm::DenseMap<Token, PostingList> InvertedIndex;
   dex::Corpus Corpus;
   llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
+  llvm::DenseMap<SymbolID, std::vector<RefersToResult>> RevRefs;
   static_assert(sizeof(RelationKind) == sizeof(uint8_t),
                 "RelationKind should be of same size as a uint8_t");
   llvm::DenseMap<std::pair<SymbolID, uint8_t>, std::vector<SymbolID>> Relations;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
   // Set of files which were used during this index build.
   llvm::StringSet<> Files;
   // Size of memory retained by KeepAlive.
   size_t BackingDataSize = 0;

clang-tools-extra/clangd/index/dex/Dex.cpp

 //===--- Dex.cpp - Dex Symbol Index Implementation --------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
for (size_t I = 0; I < ScoredSymbols.size(); ++I) {
     Symbols[I] = ScoredSymbols[I].second;
   }
 
   // Build posting lists for symbols.
   IndexBuilder Builder;
   for (DocID SymbolRank = 0; SymbolRank < Symbols.size(); ++SymbolRank)
     Builder.add(*Symbols[SymbolRank], SymbolRank);
   InvertedIndex = Builder.build();
+
+  // Build RevRefs
+  for (const auto &Pair : Refs) {
+    for (const auto &R : Pair.second) {
+      auto It = RevRefs.try_emplace(R.Container).first;
+      It->second.push_back({
+          R.Location, R.Kind,
+          Pair.first, // FIXME: this is teh referee, not the container
+      });
+    }
+  }
 }
 
 std::unique_ptr<Iterator> Dex::iterator(const Token &Tok) const {
   auto It = InvertedIndex.find(Tok);
   return It == InvertedIndex.end() ? Corpus.none()
                                    : It->second.iterator(&It->first);
 }
 
for (const auto &Ref : Refs.lookup(ID)) {
       if (Remaining == 0)
         return true; // More refs were available.
       --Remaining;
       Callback(Ref);
     }
   return false; // We reported all refs.
 }
 
+bool Dex::refersTo(
+    const RefsRequest &Req,
+    llvm::function_ref<void(const RefersToResult &)> Callback) const {
+  trace::Span Tracer("Dex reversed refs");
+  uint32_t Remaining =
+      Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
+  for (const auto &ID : Req.IDs)
+    for (const auto &Ref : RevRefs.lookup(ID)) {
+      if (!static_cast<int>(Req.Filter & Ref.Kind))
+        continue;
+      if (Remaining == 0)
+        return true; // More refs were available.
+      --Remaining;
+      Callback(Ref);
+    }
+  return false; // We reported all refs.
+}
+
 void Dex::relations(
     const RelationsRequest &Req,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
   trace::Span Tracer("Dex relations");
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   for (const SymbolID &Subject : Req.Subjects) {
     LookupRequest LookupReq;

 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
   Bytes += LookupTable.getMemorySize();
   Bytes += InvertedIndex.getMemorySize();
   for (const auto &TokenToPostingList : InvertedIndex)
     Bytes += TokenToPostingList.second.bytes();
   Bytes += Refs.getMemorySize();
+  Bytes += RevRefs.getMemorySize();
   Bytes += Relations.getMemorySize();
   return Bytes + BackingDataSize;
 }
 
 std::vector<std::string> generateProximityURIs(llvm::StringRef URIPath) {
   std::vector<std::string> Result;
   auto ParsedURI = URI::parse(URIPath);
   assert(ParsedURI &&

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"

 using ::testing::ElementsAre;
 using ::testing::Field;
 using ::testing::IsEmpty;
 using ::testing::Matcher;
 using ::testing::UnorderedElementsAre;
 
 // Helpers for matching call hierarchy data structures.
 MATCHER_P(WithName, N, "") { return arg.name == N; }
+MATCHER_P(WithDetail, N, "") { return arg.detail == 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 ItemMatcher>
+::testing::Matcher<CallHierarchyOutgoingCall> To(ItemMatcher M) {
+  return Field(&CallHierarchyOutgoingCall::to, M);
+}
 template <class... RangeMatchers>
-::testing::Matcher<CallHierarchyIncomingCall> FromRanges(RangeMatchers... M) {
+::testing::Matcher<CallHierarchyIncomingCall> IFromRanges(RangeMatchers... M) {
   return Field(&CallHierarchyIncomingCall::fromRanges,
                UnorderedElementsAre(M...));
 }
+template <class... RangeMatchers>
+::testing::Matcher<CallHierarchyOutgoingCall> OFromRanges(RangeMatchers... M) {
+  return Field(&CallHierarchyOutgoingCall::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));
   ASSERT_THAT(Items, ElementsAre(WithName("callee")));
   auto IncomingLevel1 = incomingCalls(Items[0], Index.get());
-  ASSERT_THAT(IncomingLevel1,
-              ElementsAre(AllOf(From(WithName("caller1")),
-                                FromRanges(Source.range("Callee")))));
+  ASSERT_THAT(
+      IncomingLevel1,
+      ElementsAre(AllOf(From(AllOf(WithName("caller1"), WithDetail("caller1"))),
+                        IFromRanges(Source.range("Callee")))));
 
   auto IncomingLevel2 = incomingCalls(IncomingLevel1[0].from, Index.get());
-  ASSERT_THAT(IncomingLevel2,
-              ElementsAre(AllOf(From(WithName("caller2")),
-                                FromRanges(Source.range("Caller1A"),
-                                           Source.range("Caller1B"))),
-                          AllOf(From(WithName("caller3")),
-                                FromRanges(Source.range("Caller1C")))));
+  ASSERT_THAT(
+      IncomingLevel2,
+      ElementsAre(AllOf(From(AllOf(WithName("caller2"), WithDetail("caller2"))),
+                        IFromRanges(Source.range("Caller1A"),
+                  AllOf(From(AllOf(WithName("caller3"), WithDetail("caller3"))),
+                        IFromRanges(Source.range("Caller1C")))));
 
   auto IncomingLevel3 = incomingCalls(IncomingLevel2[0].from, Index.get());
-  ASSERT_THAT(IncomingLevel3,
-              ElementsAre(AllOf(From(WithName("caller3")),
-                                FromRanges(Source.range("Caller2")))));
+  ASSERT_THAT(
+      IncomingLevel3,
+      ElementsAre(AllOf(From(AllOf(WithName("caller3"), WithDetail("caller3"))),
+                        IFromRanges(Source.range("Caller2")))));
 
   auto IncomingLevel4 = incomingCalls(IncomingLevel3[0].from, Index.get());
   EXPECT_THAT(IncomingLevel4, IsEmpty());
 }
 
 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
TEST(CallHierarchy, MainFileOnlyRef) {
   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));
   ASSERT_THAT(Items, ElementsAre(WithName("callee")));
   auto IncomingLevel1 = incomingCalls(Items[0], Index.get());
-  ASSERT_THAT(IncomingLevel1,
-              ElementsAre(AllOf(From(WithName("caller1")),
-                                FromRanges(Source.range("Callee")))));
+  ASSERT_THAT(
+      IncomingLevel1,
+      ElementsAre(AllOf(From(AllOf(WithName("caller1"), WithDetail("caller1"))),
+                        IFromRanges(Source.range("Callee")))));
 
   auto IncomingLevel2 = incomingCalls(IncomingLevel1[0].from, Index.get());
-  EXPECT_THAT(IncomingLevel2,
-              ElementsAre(AllOf(From(WithName("caller2")),
-                                FromRanges(Source.range("Caller1")))));
+  EXPECT_THAT(
+      IncomingLevel2,
+      ElementsAre(AllOf(From(AllOf(WithName("caller2"), WithDetail("caller2"))),
+                        IFromRanges(Source.range("Caller1")))));
 }
 
 TEST(CallHierarchy, IncomingQualified) {
   Annotations Source(R"cpp(
     namespace ns {
     struct Waldo {
       void find();
     };
TEST(CallHierarchy, IncomingQualified) {
   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));
   ASSERT_THAT(Items, ElementsAre(WithName("Waldo::find")));
   auto Incoming = incomingCalls(Items[0], Index.get());
-  EXPECT_THAT(Incoming,
-              ElementsAre(AllOf(From(WithName("caller1")),
-                                FromRanges(Source.range("Caller1"))),
-                          AllOf(From(WithName("caller2")),
-                                FromRanges(Source.range("Caller2")))));
+  EXPECT_THAT(
+      Incoming,
+      ElementsAre(
+          AllOf(From(AllOf(WithName("caller1"), WithDetail("ns::caller1"))),
+                IFromRanges(Source.range("Caller1"))),
+          AllOf(From(AllOf(WithName("caller2"), WithDetail("ns::caller2"))),
+                IFromRanges(Source.range("Caller2")))));
+}
+
+TEST(CallHierarchy, OutgoingOneFile) {
+  // Test outgoing call on the main file, with namespaces and methods
+  Annotations Source(R"cpp(
+    void callee(int);
+    namespace ns {
+      struct Foo {
+        void caller1();
+      };
+      void Foo::caller1() {
+        $Callee[[callee]](42);
       }
+    }
+    namespace {
+      void caller2(ns::Foo& F) {
+        F.$Caller1A[[caller1]]();
+        F.$Caller1B[[caller1]]();
+      }
+    }
+    void call^er3(ns::Foo& F) {
+      F.$Caller1C[[caller1]]();
+      $Caller2[[caller2]](F);
+    }
+  )cpp");
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
 
-TEST(CallHierarchy, IncomingMultiFile) {
+  std::vector<CallHierarchyItem> Items =
+      prepareCallHierarchy(AST, Source.point(), testPath(TU.Filename));
+  ASSERT_THAT(Items, ElementsAre(WithName("caller3")));
+  auto OugoingLevel1 = outgoingCalls(Items[0], Index.get());
+  ASSERT_THAT(
+      OugoingLevel1,
+      ElementsAre(
+          AllOf(To(AllOf(WithName("caller1"), WithDetail("ns::Foo::caller1"))),
+                OFromRanges(Source.range("Caller1C"))),
+          AllOf(To(AllOf(WithName("caller2"), WithDetail("caller2"))),
+                OFromRanges(Source.range("Caller2")))));
+
+  auto OutgoingLevel2 = outgoingCalls(OugoingLevel1[1].to, Index.get());
+  ASSERT_THAT(
+      OutgoingLevel2,
+      ElementsAre(AllOf(
+          To(AllOf(WithName("caller1"), WithDetail("ns::Foo::caller1"))),
+          OFromRanges(Source.range("Caller1A"), Source.range("Caller1B")))));
+
+  auto OutgoingLevel3 = outgoingCalls(OutgoingLevel2[0].to, Index.get());
+  ASSERT_THAT(
+      OutgoingLevel3,
+      ElementsAre(AllOf(To(AllOf(WithName("callee"), WithDetail("callee"))),
+                        OFromRanges(Source.range("Callee")))));
+
+  auto OutgoingLevel4 = outgoingCalls(OutgoingLevel3[0].to, Index.get());
+  EXPECT_THAT(OutgoingLevel4, IsEmpty());
+}
+
+TEST(CallHierarchy, MultiFile) {
   // 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(
+    namespace nsa {
       void caller1();
+    }
   )cpp");
   Annotations Caller1C(R"cpp(
     #include "callee.hh"
     #include "caller1.hh"
+    namespace nsa {
       void caller1() {
         [[calle^e]](42);
       }
+    }
   )cpp");
   Annotations Caller2H(R"cpp(
+    namespace nsb {
       void caller2();
+    }
   )cpp");
   Annotations Caller2C(R"cpp(
     #include "caller1.hh"
     #include "caller2.hh"
+    namespace nsb {
       void caller2() {
-      $A[[caller1]]();
-      $B[[caller1]]();
+        nsa::$A[[caller1]]();
+        nsa::$B[[caller1]]();
+      }
+    }
+  )cpp");
+  Annotations Caller3H(R"cpp(
+    namespace nsa {
+      void call^er3();
     }
   )cpp");
   Annotations Caller3C(R"cpp(
     #include "caller1.hh"
     #include "caller2.hh"
-    void caller3() {
+    namespace nsa {
+      void call^er3() {
         $Caller1[[caller1]]();
-      $Caller2[[caller2]]();
+        nsb::$Caller2[[caller2]]();
+      }
     }
   )cpp");
 
   TestWorkspace Workspace;
   Workspace.addSource("callee.hh", CalleeH.code());
   Workspace.addSource("caller1.hh", Caller1H.code());
   Workspace.addSource("caller2.hh", Caller2H.code());
+  Workspace.addSource("caller3.hh", Caller3H.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) {
+  auto CheckIncomingCalls = [&](ParsedAST &AST, Position Pos, PathRef TUPath) {
     std::vector<CallHierarchyItem> Items =
         prepareCallHierarchy(AST, Pos, TUPath);
     ASSERT_THAT(Items, ElementsAre(WithName("callee")));
     auto IncomingLevel1 = incomingCalls(Items[0], Index.get());
     ASSERT_THAT(IncomingLevel1,
-                ElementsAre(AllOf(From(WithName("caller1")),
-                                  FromRanges(Caller1C.range()))));
+                ElementsAre(AllOf(From(AllOf(WithName("caller1"),
+                                             WithDetail("nsa::caller1"))),
+                                  IFromRanges(Caller1C.range()))));
 
     auto IncomingLevel2 = incomingCalls(IncomingLevel1[0].from, Index.get());
     ASSERT_THAT(
         IncomingLevel2,
-        ElementsAre(AllOf(From(WithName("caller2")),
-                          FromRanges(Caller2C.range("A"), Caller2C.range("B"))),
-                    AllOf(From(WithName("caller3")),
-                          FromRanges(Caller3C.range("Caller1")))));
+        ElementsAre(
+            AllOf(From(AllOf(WithName("caller2"), WithDetail("nsb::caller2"))),
+                  IFromRanges(Caller2C.range("A"), Caller2C.range("B"))),
+            AllOf(From(AllOf(WithName("caller3"), WithDetail("nsa::caller3"))),
+                  IFromRanges(Caller3C.range("Caller1")))));
 
     auto IncomingLevel3 = incomingCalls(IncomingLevel2[0].from, Index.get());
     ASSERT_THAT(IncomingLevel3,
-                ElementsAre(AllOf(From(WithName("caller3")),
-                                  FromRanges(Caller3C.range("Caller2")))));
+                ElementsAre(AllOf(From(AllOf(WithName("caller3"),
+                                             WithDetail("nsa::caller3"))),
+                                  IFromRanges(Caller3C.range("Caller2")))));
 
     auto IncomingLevel4 = incomingCalls(IncomingLevel3[0].from, Index.get());
     EXPECT_THAT(IncomingLevel4, IsEmpty());
   };
 
+  auto CheckOutgoingCalls = [&](ParsedAST &AST, Position Pos, PathRef TUPath) {
+    std::vector<CallHierarchyItem> Items =
+        prepareCallHierarchy(AST, Pos, TUPath);
+    ASSERT_THAT(Items, ElementsAre(WithName("caller3")));
+    auto OutgoingLevel1 = outgoingCalls(Items[0], Index.get());
+    ASSERT_THAT(
+        OutgoingLevel1,
+        ElementsAre(
+            AllOf(To(AllOf(WithName("caller1"), WithDetail("nsa::caller1"))),
+                  OFromRanges(Caller3C.range("Caller1"))),
+            AllOf(To(AllOf(WithName("caller2"), WithDetail("nsb::caller2"))),
+                  OFromRanges(Caller3C.range("Caller2")))));
+
+    auto OutgoingLevel2 = outgoingCalls(OutgoingLevel1[1].to, Index.get());
+    ASSERT_THAT(OutgoingLevel2,
+                ElementsAre(AllOf(
+                    To(AllOf(WithName("caller1"), WithDetail("nsa::caller1"))),
+                    OFromRanges(Caller2C.range("A"), Caller2C.range("B")))));
+
+    auto OutgoingLevel3 = outgoingCalls(OutgoingLevel2[0].to, Index.get());
+    ASSERT_THAT(
+        OutgoingLevel3,
+        ElementsAre(AllOf(To(AllOf(WithName("callee"), WithDetail("callee"))),
+                          OFromRanges(Caller1C.range()))));
+
+    auto OutgoingLevel4 = outgoingCalls(OutgoingLevel3[0].to, Index.get());
+    EXPECT_THAT(OutgoingLevel4, IsEmpty());
+  };
+
   // 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"));
+  CheckIncomingCalls(*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"));
+  CheckIncomingCalls(*AST, CalleeH.point(), testPath("callee.hh"));
+  AST = Workspace.openFile("caller3.hh");
+  ASSERT_TRUE(bool(AST));
+  CheckOutgoingCalls(*AST, Caller3H.point(), testPath("caller3.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"));
+  CheckIncomingCalls(*AST, CalleeC.point(), testPath("callee.cc"));
+  AST = Workspace.openFile("caller3.cc");
+  ASSERT_TRUE(bool(AST));
+  CheckOutgoingCalls(*AST, Caller3C.point(), testPath("caller3.cc"));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

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

 //===-- CodeCompleteTests.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
 //
 //===----------------------------------------------------------------------===//
 
public:
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override {}
 
   bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override {
     return false;
   }
 
+  bool
+  refersTo(const RefsRequest &,
+           llvm::function_ref<void(const RefersToResult &)>) const override {
+    return false;
+  }
+
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override {}
 
   llvm::unique_function<bool(llvm::StringRef) const>
   indexedFiles() const override {
     return [](llvm::StringRef) { return false; };
   }

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

 //===-- RenameTests.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
 //
 //===----------------------------------------------------------------------===//
 
TEST(CrossFileRenameTests, DirtyBuffer) {
   // Run rename on a pagination index which couldn't return all refs in one
   // request, we reject rename on this case.
   class PaginationIndex : public SymbolIndex {
     bool refs(const RefsRequest &Req,
               llvm::function_ref<void(const Ref &)> Callback) const override {
       return true; // has more references
     }
 
+    bool refersTo(const RefsRequest &Req,
+                  llvm::function_ref<void(const RefersToResult &)> Callback)
+        const override {
+      return false;
+    }
+
     bool fuzzyFind(
         const FuzzyFindRequest &Req,
         llvm::function_ref<void(const Symbol &)> Callback) const override {
       return false;
     }
     void
     lookup(const LookupRequest &Req,
            llvm::function_ref<void(const Symbol &)> Callback) const override {}
public:
     bool refs(const RefsRequest &Req,
               llvm::function_ref<void(const Ref &)> Callback) const override {
       // Return two duplicated refs.
       Callback(ReturnedRef);
       Callback(ReturnedRef);
       return false;
     }
 
+    bool refersTo(const RefsRequest &Req,
+                  llvm::function_ref<void(const RefersToResult &)> Callback)
+        const override {
+      return false;
+    }
+
     bool fuzzyFind(const FuzzyFindRequest &,
                    llvm::function_ref<void(const Symbol &)>) const override {
       return false;
     }
     void lookup(const LookupRequest &,
                 llvm::function_ref<void(const Symbol &)>) const override {}
 
     void relations(const RelationsRequest &,