[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

2349

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

100

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

173

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

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

95

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

2349

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

100

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

173

Sure, that makes sense

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

95

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

2349

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

173

+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

95

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.h

void onTypeHierarchy(const TypeHierarchyPrepareParams &,
                        Callback<llvm::json::Value>);
   void onResolveTypeHierarchy(const ResolveTypeHierarchyItemParams &,
                               Callback<llvm::json::Value>);
   void onPrepareCallHierarchy(const CallHierarchyPrepareParams &,
                               Callback<std::vector<CallHierarchyItem>>);
   void onCallHierarchyIncomingCalls(
       const CallHierarchyIncomingCallsParams &,
       Callback<std::vector<CallHierarchyIncomingCall>>);
+  void onCallHierarchyOutgoingCalls(
+      const CallHierarchyOutgoingCallsParams &,
+      Callback<std::vector<CallHierarchyOutgoingCall>>);
   void onClangdInlayHints(const InlayHintsParams &,
                           Callback<llvm::json::Value>);
   void onInlayHint(const InlayHintsParams &, Callback<std::vector<InlayHint>>);
   void onChangeConfiguration(const DidChangeConfigurationParams &);
   void onSymbolInfo(const TextDocumentPositionParams &,
                     Callback<std::vector<SymbolDetails>>);
   void onSelectionRange(const SelectionRangeParams &,
                         Callback<std::vector<SelectionRange>>);

clang-tools-extra/clangd/ClangdLSPServer.cpp

 }
 
 void ClangdLSPServer::onInlayHint(const InlayHintsParams &Params,
                                   Callback<std::vector<InlayHint>> Reply) {
   Server->inlayHints(Params.textDocument.uri.file(), Params.range,
                      std::move(Reply));
 }
 
+void ClangdLSPServer::onCallHierarchyOutgoingCalls(
+    const CallHierarchyOutgoingCallsParams &Params,
+    Callback<std::vector<CallHierarchyOutgoingCall>> Reply) {
+  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;
     auto Old = CDB->getCompileCommand(File);
     auto New =
void ClangdLSPServer::bindMethods(LSPBinder &Bind,
   Bind.method("textDocument/symbolInfo", this, &ClangdLSPServer::onSymbolInfo);
   Bind.method("textDocument/typeHierarchy", this, &ClangdLSPServer::onTypeHierarchy);
   Bind.method("typeHierarchy/resolve", this, &ClangdLSPServer::onResolveTypeHierarchy);
   Bind.method("textDocument/prepareTypeHierarchy", this, &ClangdLSPServer::onPrepareTypeHierarchy);
   Bind.method("typeHierarchy/supertypes", this, &ClangdLSPServer::onSuperTypes);
   Bind.method("typeHierarchy/subtypes", this, &ClangdLSPServer::onSubTypes);
   Bind.method("textDocument/prepareCallHierarchy", this, &ClangdLSPServer::onPrepareCallHierarchy);
   Bind.method("callHierarchy/incomingCalls", this, &ClangdLSPServer::onCallHierarchyIncomingCalls);
+  Bind.method("callHierarchy/outgoingCalls", this, &ClangdLSPServer::onCallHierarchyOutgoingCalls);
   Bind.method("textDocument/selectionRange", this, &ClangdLSPServer::onSelectionRange);
   Bind.method("textDocument/documentLink", this, &ClangdLSPServer::onDocumentLink);
   Bind.method("textDocument/semanticTokens/full", this, &ClangdLSPServer::onSemanticTokens);
   Bind.method("textDocument/semanticTokens/full/delta", this, &ClangdLSPServer::onSemanticTokensDelta);
   Bind.method("clangd/inlayHints", this, &ClangdLSPServer::onClangdInlayHints);
   Bind.method("textDocument/inlayHint", this, &ClangdLSPServer::onInlayHint);
   Bind.method("$/memoryUsage", this, &ClangdLSPServer::onMemoryUsage);
   Bind.method("textDocument/foldingRange", this, &ClangdLSPServer::onFoldingRange);

clang-tools-extra/clangd/ClangdServer.h

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>>);
+
   /// Resolve inlay hints for a given document.
   void inlayHints(PathRef File, std::optional<Range> RestrictRange,
                   Callback<std::vector<InlayHint>>);
 
   /// Retrieve the top symbols from the workspace matching a query.
   void workspaceSymbols(StringRef Query, int Limit,
                         Callback<std::vector<SymbolInformation>> CB);
 

clang-tools-extra/clangd/ClangdServer.cpp

auto Action = [RestrictRange(std::move(RestrictRange)),
                  CB = std::move(CB)](Expected<InputsAndAST> InpAST) mutable {
     if (!InpAST)
       return CB(InpAST.takeError());
     CB(clangd::inlayHints(InpAST->AST, std::move(RestrictRange)));
   };
   WorkScheduler->runWithAST("InlayHints", File, std::move(Action), Transient);
 }
 
+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

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

declToHierarchyItem(const NamedDecl &ND, llvm::StringRef TUPath) {
 
   index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
   // FIXME: This is not classifying constructors, destructors and operators
   // correctly.
   SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
 
   HierarchyItem HI;
   HI.name = printName(Ctx, ND);
+  // FIXME: Populate HI.detail the way we do in symbolToHierarchyItem?
   HI.kind = SK;
   HI.range = Range{sourceLocToPosition(SM, DeclRange->getBegin()),
                    sourceLocToPosition(SM, DeclRange->getEnd())};
   HI.selectionRange = Range{NameBegin, NameEnd};
   if (!HI.range.contains(HI.selectionRange)) {
     // 'selectionRange' must be contained in 'range', so in cases where clang
     // reports unrelated ranges we need to reconcile somehow.
     HI.range = HI.selectionRange;
static std::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 std::nullopt;
   }
   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;
 
   return HI;
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.
+  ContainedRefsRequest Request;
+  Request.ID = *ID;
+  // 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->containedRefs(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;
+    bool NotCall = (Kind != SK::Function && Kind != SK::InstanceMethod &&
+                    Kind != SK::ClassMethod && Kind != SK::StaticMethod &&
+                    Kind != SK::Constructor && Kind != SK::Destructor &&
+                    Kind != SK::ConversionFunction);
+    assert(!NotCall);
+
+    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) {

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

struct RefsRequest {
   /// choose to return less than this, e.g. it tries to avoid returning stale
   /// results.
   std::optional<uint32_t> Limit;
   /// If set, populates the container of the reference.
   /// Index implementations may chose to populate containers no matter what.
   bool WantContainer = false;
 };
 
+struct ContainedRefsRequest {
+  /// Note that RefKind::Call just restricts the matched SymbolKind to
+  /// functions, not the form of the reference (e.g. address-of-function,
+  /// which can indicate an indirect call, should still be caught).
+  static const RefKind SupportedRefKinds = RefKind::Call;
+
+  SymbolID ID;
+  /// If set, limit the number of refers returned from the index. The index may
+  /// choose to return less than this, e.g. it tries to avoid returning stale
+  /// results.
+  std::optional<uint32_t> Limit;
+};
+
 struct RelationsRequest {
   llvm::DenseSet<SymbolID> Subjects;
   RelationKind Predicate;
   /// If set, limit the number of relations returned from the index.
   std::optional<uint32_t> Limit;
 };
 
+struct ContainedRefsResult {
+  /// 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;
+};
+
 /// Describes what data is covered by an index.
 ///
 /// Indexes may contain symbols but not references from a file, etc.
 /// This affects merging: if a staler index contains a reference but a fresher
 /// one does not, we want to trust the fresher index *only* if it actually
 /// includes references in general.
 enum class IndexContents : uint8_t {
   None = 0,
public:
   /// Results should be returned in arbitrary order.
   /// The returned result must be deep-copied if it's used outside Callback.
   /// FIXME: there's no indication which result references which symbol.
   ///
   /// 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 containedRefs(
+      const ContainedRefsRequest &Req,
+      llvm::function_ref<void(const ContainedRefsResult &)> 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 containedRefs(
+      const ContainedRefsRequest &,
+      llvm::function_ref<void(const ContainedRefsResult &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
 
   llvm::unique_function<IndexContents(llvm::StringRef) const>
   indexedFiles() const override;
 
   size_t estimateMemoryUsage() const override;

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

 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::containedRefs(
+    const ContainedRefsRequest &R,
+    llvm::function_ref<void(const ContainedRefsResult &)> CB) const {
+  return snapshot()->containedRefs(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<IndexContents(llvm::StringRef) const>
 SwapIndex::indexedFiles() const {

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

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 containedRefs(const ContainedRefsRequest &Req,
+                     llvm::function_ref<void(const ContainedRefsResult &)>
+                         Callback) const override;
+
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
   llvm::unique_function<IndexContents(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
 //
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
 #include "FuzzyMatch.h"
 #include "Quality.h"
+#include "index/Index.h"
 #include "support/Trace.h"
 
 namespace clang {
 namespace clangd {
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs,
                                              RelationSlab Relations) {
   // Store Slab size before it is moved.
for (const auto &O : SymRefs->second) {
         return true; // More refs were available.
       --Remaining;
       Callback(O);
     }
   }
   return false; // We reported all refs.
 }
 
+bool MemIndex::containedRefs(
+    const ContainedRefsRequest &Req,
+    llvm::function_ref<void(const ContainedRefsResult &)> Callback) const {
+  trace::Span Tracer("MemIndex refersTo");
+  uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());
+  for (const auto &Pair : Refs) {
+    for (const auto &R : Pair.second) {
+      if (!static_cast<int>(ContainedRefsRequest::SupportedRefKinds & R.Kind) ||
+          Req.ID != 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.value_or(std::numeric_limits<uint32_t>::max());
   for (const SymbolID &Subject : Req.Subjects) {
     LookupRequest LookupReq;
     auto It = Relations.find(
         std::make_pair(Subject, static_cast<uint8_t>(Req.Predicate)));

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

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 containedRefs(
+      const ContainedRefsRequest &,
+      llvm::function_ref<void(const ContainedRefsResult &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
   llvm::unique_function<IndexContents(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

if (Remaining == 0) {
       return;
     }
     --Remaining;
     Callback(O);
   });
   return More || StaticHadMore;
 }
 
+bool MergedIndex::containedRefs(
+    const ContainedRefsRequest &Req,
+    llvm::function_ref<void(const ContainedRefsResult &)> Callback) const {
+  trace::Span Tracer("MergedIndex refersTo");
+  bool More = false;
+  uint32_t Remaining = Req.Limit.value_or(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->containedRefs(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->containedRefs(Req, [&](const auto &O) {
+    if ((DynamicContainsFile(O.Location.FileURI) & IndexContents::References) !=
+        IndexContents::None)
+      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<IndexContents(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

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 containedRefs(const ContainedRefsRequest &Req,
+                     llvm::function_ref<void(const ContainedRefsResult &)>
+                         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::containedRefs(
+    const ContainedRefsRequest &Req,
+    llvm::function_ref<void(const ContainedRefsResult &)> Callback) const {
+  trace::Span Tracer("ProjectAwareIndex::refersTo");
+  if (auto *Idx = getIndex())
+    return Idx->containedRefs(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/Ref.h

enum class RefKind : uint8_t {
   //     v there is an implicit constructor call here which is not a spelled ref
   // Foo foo;
   // ^ this reference explicitly spells out Foo's name
   // struct Bar {
   //   MACRO Internal;
   //   ^ this references Foo, but does not explicitly spell out its name
   // };
   Spelled = 1 << 3,
+  // A reference which is a call. Used as a filter for which references
+  // to store in data structures used for computing outgoing calls.
+  Call = 1 << 4,
   All = Declaration | Definition | Reference | Spelled,
 };
 
 inline RefKind operator|(RefKind L, RefKind R) {
   return static_cast<RefKind>(static_cast<uint8_t>(L) |
                               static_cast<uint8_t>(R));
 }
 inline RefKind &operator|=(RefKind &L, RefKind R) { return L = L | R; }

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

private:
   Preprocessor *PP = nullptr;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
   std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo;
   Options Opts;
   struct SymbolRef {
     SourceLocation Loc;
     FileID FID;
     index::SymbolRoleSet Roles;
+    index::SymbolKind Kind;
     const Decl *Container;
     bool Spelled;
   };
   void addRef(SymbolID ID, const SymbolRef &SR);
   // Symbols referenced from the current TU, flushed on finish().
   llvm::DenseSet<SymbolID> ReferencedSymbols;
   // Maps canonical declaration provided by clang to canonical declaration for
   // an index symbol, if clangd prefers a different declaration than that

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

 #include "ExpectedTypes.h"
 #include "SourceCode.h"
 #include "URI.h"
 #include "clang-include-cleaner/Analysis.h"
 #include "clang-include-cleaner/IncludeSpeller.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "index/CanonicalIncludes.h"
+#include "index/Ref.h"
 #include "index/Relation.h"
 #include "index/Symbol.h"
 #include "index/SymbolID.h"
 #include "index/SymbolLocation.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclTemplate.h"
bool SymbolCollector::handleDeclOccurrence(
   // FIXME: we should try to use the file locations for other fields.
   if (CollectRef &&
       (!IsMainFileOnly || Opts.CollectMainFileRefs ||
        ND->isExternallyVisible()) &&
       !isa<NamespaceDecl>(ND)) {
     auto FileLoc = SM.getFileLoc(Loc);
     auto FID = SM.getFileID(FileLoc);
     if (Opts.RefsInHeaders || FID == SM.getMainFileID()) {
-      addRef(ID, SymbolRef{FileLoc, FID, Roles,
+      addRef(ID, SymbolRef{FileLoc, FID, Roles, index::getSymbolInfo(ND).Kind,
                            getRefContainer(ASTNode.Parent, Opts),
                            isSpelled(FileLoc, *ND)});
     }
   }
   // Don't continue indexing if this is a mere reference.
   if (!(Roles & (static_cast<unsigned>(index::SymbolRole::Declaration) |
                  static_cast<unsigned>(index::SymbolRole::Definition))))
     return true;
bool IsMainFileOnly =
       !isHeaderFile(SM.getFileEntryRefForID(SM.getMainFileID())->getName(),
                     ASTCtx->getLangOpts());
   // Do not store references to main-file macros.
   if ((static_cast<unsigned>(Opts.RefFilter) & Roles) && !IsMainFileOnly &&
       (Opts.RefsInHeaders || SM.getFileID(SpellingLoc) == SM.getMainFileID())) {
     // FIXME: Populate container information for macro references.
     // FIXME: All MacroRefs are marked as Spelled now, but this should be
     // checked.
-    addRef(ID, SymbolRef{Loc, SM.getFileID(Loc), Roles, /*Container=*/nullptr,
-                         /*Spelled=*/true});
+    addRef(ID,
+           SymbolRef{Loc, SM.getFileID(Loc), Roles, index::SymbolKind::Macro,
+                     /*Container=*/nullptr,
   }
 
   // Collect symbols.
   if (!Opts.CollectMacro)
     return true;
 
   // Skip main-file macros if we are not collecting them.
   if (IsMainFileOnly && !Opts.CollectMainFileSymbols)
bool SymbolCollector::shouldIndexFile(FileID FID) {
   if (!Opts.FileFilter)
     return true;
   auto I = FilesToIndexCache.try_emplace(FID);
   if (I.second)
     I.first->second = Opts.FileFilter(ASTCtx->getSourceManager(), FID);
   return I.first->second;
 }
 
+static bool refIsCall(index::SymbolKind Kind) {
+  using SK = index::SymbolKind;
+  return Kind == SK::Function || Kind == SK::InstanceMethod ||
+         Kind == SK::ClassMethod || Kind == SK::StaticMethod ||
+         Kind == SK::Constructor || Kind == SK::Destructor ||
+         Kind == SK::ConversionFunction;
+}
+
 void SymbolCollector::addRef(SymbolID ID, const SymbolRef &SR) {
   const auto &SM = ASTCtx->getSourceManager();
   // FIXME: use the result to filter out references.
   shouldIndexFile(SR.FID);
   if (const auto FE = SM.getFileEntryRefForID(SR.FID)) {
     auto Range = getTokenRange(SR.Loc, SM, ASTCtx->getLangOpts());
     Ref R;
     R.Location.Start = Range.first;
     R.Location.End = Range.second;
     R.Location.FileURI = HeaderFileURIs->toURI(*FE).c_str();
     R.Kind = toRefKind(SR.Roles, SR.Spelled);
+    if (refIsCall(SR.Kind)) {
+      R.Kind |= RefKind::Call;
+    }
     R.Container = getSymbolIDCached(SR.Container);
     Refs.insert(ID, R);
   }
 }
 
 SymbolID SymbolCollector::getSymbolIDCached(const Decl *D) {
   auto It = DeclToIDCache.try_emplace(D, SymbolID{});
   if (It.second)

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

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 containedRefs(const ContainedRefsRequest &Req,
+                     llvm::function_ref<void(const ContainedRefsResult &)>
+                         Callback) const override;
+
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
   llvm::unique_function<IndexContents(llvm::StringRef) const>
   indexedFiles() const override;
 
   size_t estimateMemoryUsage() const override;
 
 private:
+  class RevRef {
+    const Ref *Reference;
+    SymbolID Target;
+
+  public:
+    RevRef(const Ref &Reference, SymbolID Target)
+        : Reference(&Reference), Target(Target) {}
+    const Ref &ref() const { return *Reference; }
+    ContainedRefsResult containedRefsResult() const {
+      return {ref().Location, ref().Kind, Target};
+    }
+  };
+
   void buildIndex();
+  llvm::iterator_range<std::vector<RevRef>::const_iterator>
+  lookupRevRefs(const SymbolID &Container) const;
   std::unique_ptr<Iterator> iterator(const Token &Tok) const;
   std::unique_ptr<Iterator>
   createFileProximityIterator(llvm::ArrayRef<std::string> ProximityPaths) const;
   std::unique_ptr<Iterator>
   createTypeBoostingIterator(llvm::ArrayRef<std::string> Types) const;
 
   /// Stores symbols sorted in the descending order of symbol quality..
   std::vector<const Symbol *> Symbols;
   /// SymbolQuality[I] is the quality of Symbols[I].
   std::vector<float> SymbolQuality;
   llvm::DenseMap<SymbolID, const Symbol *> LookupTable;
   /// Inverted index is a mapping from the search token to the posting list,
   /// 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;
+  std::vector<RevRef> RevRefs; // sorted by container ID
   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;
   // Contents of the index (symbols, references, etc.)
   IndexContents IdxContents;

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

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 = std::move(Builder).build();
+
+  // Build RevRefs
+  for (const auto &[ID, RefList] : Refs)
+    for (const auto &R : RefList)
+      if ((R.Kind & ContainedRefsRequest::SupportedRefKinds) !=
+          RefKind::Unknown)
+        RevRefs.emplace_back(R, ID);
+  // Sort by container ID so we can use binary search for lookup.
+  llvm::sort(RevRefs, [](const RevRef &A, const RevRef &B) {
+    return A.ref().Container < B.ref().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.
 }
 
+llvm::iterator_range<std::vector<Dex::RevRef>::const_iterator>
+Dex::lookupRevRefs(const SymbolID &Container) const {
+  // equal_range() requires an element of the same type as the elements of the
+  // range, so construct a dummy RevRef with the container of interest.
+  Ref QueryRef;
+  QueryRef.Container = Container;
+  RevRef Query(QueryRef, SymbolID{});
+
+  auto ItPair = std::equal_range(RevRefs.cbegin(), RevRefs.cend(), Query,
+                                 [](const RevRef &A, const RevRef &B) {
+                                   return A.ref().Container < B.ref().Container;
+                                 });
+  return {ItPair.first, ItPair.second};
+}
+
+bool Dex::containedRefs(
+    const ContainedRefsRequest &Req,
+    llvm::function_ref<void(const ContainedRefsResult &)> Callback) const {
+  trace::Span Tracer("Dex reversed refs");
+  uint32_t Remaining = Req.Limit.value_or(std::numeric_limits<uint32_t>::max());
+  for (const auto &Rev : lookupRevRefs(Req.ID)) {
+    // RevRefs are already filtered to ContainedRefsRequest::SupportedRefKinds
+    if (Remaining == 0)
+      return true; // More refs were available.
+    --Remaining;
+    Callback(Rev.containedRefsResult());
+  }
+  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.value_or(std::numeric_limits<uint32_t>::max());
   for (const SymbolID &Subject : Req.Subjects) {
     LookupRequest LookupReq;
     auto It = Relations.find(

 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.size() * sizeof(RevRef);
   Bytes += Relations.getMemorySize();
   return Bytes + BackingDataSize;
 }
 
 // Given foo://bar/one/two
 // Returns        ~~~~~~~~  (or empty for bad URI)
 llvm::StringRef findPathInURI(llvm::StringRef S) {
   S = S.split(':').second;   // Eat scheme.

clang-tools-extra/clangd/test/type-hierarchy-ext.test

 # RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %s
 {"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
 ---
 {"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///main.cpp","languageId":"cpp","version":1,"text":"struct Parent {};\nstruct Child1 : Parent {};\nstruct Child2 : Child1 {};\nstruct Child3 : Child2 {};\nstruct Child4 : Child3 {};"}}}
 ---
 {"jsonrpc":"2.0","id":1,"method":"textDocument/typeHierarchy","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":2,"character":11},"direction":2,"resolve":1}}
 #      CHECK:  "id": 1
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "children": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "data": {
 # CHECK-NEXT:           "symbolID": "A6576FE083F2949A"
 # CHECK-NEXT:        },
+# CHECK-NEXT:        "detail": "Child3",
 # CHECK-NEXT:        "kind": 23,
 # CHECK-NEXT:        "name": "Child3",
 # CHECK-NEXT:        "range": {
 # CHECK-NEXT:          "end": {
 # CHECK-NEXT:            "character": 13,
 # CHECK-NEXT:            "line": 3
 # CHECK-NEXT:          },
 # CHECK-NEXT:          "start": {

 #      CHECK:  "id": 2
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "children": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "data": {
 # CHECK-NEXT:          "symbolID": "5705B382DFC77CBC"
 # CHECK-NEXT:        },
+# CHECK-NEXT:        "detail": "Child4",
 # CHECK-NEXT:        "kind": 23,
 # CHECK-NEXT:        "name": "Child4",
 # CHECK-NEXT:        "range": {
 # CHECK-NEXT:          "end": {
 # CHECK-NEXT:            "character": 13,
 # CHECK-NEXT:            "line": 4
 # CHECK-NEXT:          },
 # CHECK-NEXT:          "start": {

clang-tools-extra/clangd/test/type-hierarchy.test

 # CHECK-NEXT:         "parents": [
 # CHECK-NEXT:           {
 # CHECK-NEXT:            "parents": [],
 # CHECK-NEXT:            "symbolID": "FE546E7B648D69A7"
 # CHECK-NEXT:           }
 # CHECK-NEXT:         ],
 # CHECK-NEXT:         "symbolID": "ECDC0C46D75120F4"
 # CHECK-NEXT:       },
+# CHECK-NEXT:       "detail": "Child1",
 # CHECK-NEXT:       "kind": 23,
 # CHECK-NEXT:       "name": "Child1",
 # CHECK-NEXT:       "range": {
 # CHECK-NEXT:         "end": {
 # CHECK-NEXT:           "character": 13,
 # CHECK-NEXT:           "line": 1
 # CHECK-NEXT:         },
 # CHECK-NEXT:         "start": {

 # CHECK-NEXT:           "character": 7,
 # CHECK-NEXT:           "line": 1
 # CHECK-NEXT:         }
 # CHECK-NEXT:       },
 # CHECK-NEXT:       "uri": "file://{{.*}}/clangd-test/main.cpp"
 # CHECK-NEXT:     }
 # CHECK-NEXT:  ]
 ---
-{"jsonrpc":"2.0","id":2,"method":"typeHierarchy/subtypes","params":{"item":{"uri":"test:///main.cpp","data":{"parents":[{"parents":[{"parents":[],"symbolID":"FE546E7B648D69A7"}],"symbolID":"ECDC0C46D75120F4"}],"symbolID":"8A991335E4E67D08"},"name":"Child2","kind":23,"range":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}},"selectionRange":{"end":{"character":13,"line":3},"start":{"character":7,"line":3}}}}}
-#      CHECK:  "id": 2
-# CHECK-NEXT:  "jsonrpc": "2.0",
-# CHECK-NEXT:  "result": [
-# CHECK-NEXT:     {
-# CHECK-NEXT:       "data": {
-# CHECK-NEXT:         "parents": [
-# CHECK-NEXT:          {
-# CHECK-NEXT:           "parents": [
-# CHECK-NEXT:            {
-# CHECK-NEXT:             "parents": [
-# CHECK-NEXT:               {
-# CHECK-NEXT:                "parents": [],
-# CHECK-NEXT:                "symbolID": "FE546E7B648D69A7"
-# CHECK-NEXT:               }
-# CHECK-NEXT:             ],
-# CHECK-NEXT:             "symbolID": "ECDC0C46D75120F4"
-# CHECK-NEXT:            }
-# CHECK-NEXT:           ],
-# CHECK-NEXT:           "symbolID": "8A991335E4E67D08"
-# CHECK-NEXT:         }
-# CHECK-NEXT:        ],
-# CHECK-NEXT:        "symbolID": "A6576FE083F2949A"
-# CHECK-NEXT:       },
-# CHECK-NEXT:       "kind": 23,
-# CHECK-NEXT:       "name": "Child3",
-# CHECK-NEXT:       "range": {
-# CHECK-NEXT:         "end": {
-# CHECK-NEXT:           "character": 13,
-# CHECK-NEXT:           "line": 3
-# CHECK-NEXT:         },
-# CHECK-NEXT:         "start": {
-# CHECK-NEXT:           "character": 7,
-# CHECK-NEXT:           "line": 3
-# CHECK-NEXT:         }
-# CHECK-NEXT:       },
-# CHECK-NEXT:       "selectionRange": {
-# CHECK-NEXT:         "end": {
-# CHECK-NEXT:           "character": 13,
-# CHECK-NEXT:           "line": 3
-# CHECK-NEXT:         },
-# CHECK-NEXT:         "start": {
-# CHECK-NEXT:           "character": 7,
-# CHECK-NEXT:           "line": 3
-# CHECK-NEXT:         }
-# CHECK-NEXT:       },
-# CHECK-NEXT:       "uri": "file://{{.*}}/clangd-test/main.cpp"
-# CHECK-NEXT:     }
-# CHECK-NEXT:  ]
----
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

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

 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, IncomingOneFileCpp) {
   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, IncomingOneFileObjC) {
   Annotations Source(R"objc(
     @implementation MyClass {}
TEST(CallHierarchy, IncomingOneFileObjC) {
   TU.Filename = "TestTU.m";
   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")))));
+              ElementsAre(AllOf(from(AllOf(withName("caller1"),
+                                           withDetail("MyClass::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"),
+              ElementsAre(AllOf(from(AllOf(withName("caller2"),
+                                           withDetail("MyClass::caller2"))),
+                                iFromRanges(Source.range("Caller1A"),
                                             Source.range("Caller1B"))),
-                          AllOf(from(withName("caller3")),
-                                fromRanges(Source.range("Caller1C")))));
+                          AllOf(from(AllOf(withName("caller3"),
+                                           withDetail("MyClass::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")))));
+              ElementsAre(AllOf(from(AllOf(withName("caller3"),
+                                           withDetail("MyClass::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();
+
+  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, IncomingMultiFileCpp) {
+TEST(CallHierarchy, MultiFileCpp) {
   // 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"));
 }
 
 TEST(CallHierarchy, IncomingMultiFileObjC) {
   // The test uses a .mi suffix for header files to get clang
   // to parse them in ObjC 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).
 
TEST(CallHierarchy, IncomingMultiFileObjC) {
 
   auto CheckCallHierarchy = [&](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()))));
+                                  iFromRanges(Caller1C.range()))));
 
     auto IncomingLevel2 = incomingCalls(IncomingLevel1[0].from, Index.get());
-    ASSERT_THAT(
-        IncomingLevel2,
+    ASSERT_THAT(IncomingLevel2,
                 ElementsAre(AllOf(from(withName("caller2")),
-                          fromRanges(Caller2C.range("A"), Caller2C.range("B"))),
+                                  iFromRanges(Caller2C.range("A"),
+                                              Caller2C.range("B"))),
                             AllOf(from(withName("caller3")),
-                          fromRanges(Caller3C.range("Caller1")))));
+                                  iFromRanges(Caller3C.range("Caller1")))));
 
     auto IncomingLevel3 = incomingCalls(IncomingLevel2[0].from, Index.get());
     ASSERT_THAT(IncomingLevel3,
                 ElementsAre(AllOf(from(withName("caller3")),
-                                  fromRanges(Caller3C.range("Caller2")))));
+                                  iFromRanges(Caller3C.range("Caller2")))));
 
     auto IncomingLevel4 = incomingCalls(IncomingLevel3[0].from, Index.get());
     EXPECT_THAT(IncomingLevel4, IsEmpty());
   };
 
   // Check that invoking from a call site works.
   auto AST = Workspace.openFile("caller1.m");
   ASSERT_TRUE(bool(AST));
TEST(CallHierarchy, CallInLocalVarDecl) {
   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 Incoming = incomingCalls(Items[0], Index.get());
-  ASSERT_THAT(
-      Incoming,
-      ElementsAre(
-          AllOf(from(withName("caller1")), fromRanges(Source.range("call1"))),
-          AllOf(from(withName("caller2")), fromRanges(Source.range("call2"))),
-          AllOf(from(withName("caller3")), fromRanges(Source.range("call3")))));
+  ASSERT_THAT(Incoming, ElementsAre(AllOf(from(withName("caller1")),
+                                          iFromRanges(Source.range("call1"))),
+                                    AllOf(from(withName("caller2")),
+                                          iFromRanges(Source.range("call2"))),
+                                    AllOf(from(withName("caller3")),
+                                          iFromRanges(Source.range("call3")))));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

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

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 containedRefs(
+      const ContainedRefsRequest &,
+      llvm::function_ref<void(const ContainedRefsResult &)>) const override {
+    return false;
+  }
+
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override {}
 
   llvm::unique_function<IndexContents(llvm::StringRef) const>
   indexedFiles() const override {
     return [](llvm::StringRef) { return IndexContents::None; };
   }

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

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 containedRefs(const ContainedRefsRequest &Req,
+                       llvm::function_ref<void(const ContainedRefsResult &)>
+                           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 containedRefs(const ContainedRefsRequest &Req,
+                       llvm::function_ref<void(const ContainedRefsResult &)>
+                           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 &,