[clangd] Call hierarchy (Protocol layer)

[nridge]

Summary

The protocol is based on the spec found here:
https://microsoft.github.io/language-server-protocol/specifications/specification-3-16/#textDocument_prepareCallHierarchy

[nridge]

• Rebased on top of upstream changes
• Rebased on top of TestWorkspace changes
• Merged D89298 into this patch
• Split index changes out to D89670
• Added more tests

[nridge]

Keeping in the draft state for now, as I still need to address this comment from the issue discussion:

The request still has a progressToken attached to it, I presume(it is unclear from the spec) it is preserved between prepare and subsequent requests. So we can keep a mapping in ClangdServer and stash symbolIDs.

[nridge]

Add and use CallHierarchyItem.data

[nridge]

In D89296#2337788, @nridge wrote:

Keeping in the draft state for now, as I still need to address this comment from the issue discussion:

The request still has a progressToken attached to it, I presume(it is unclear from the spec) it is preserved between prepare and subsequent requests. So we can keep a mapping in ClangdServer and stash symbolIDs.

The protocol has since been amended to introduce a data field to CallHierarchyItem in which we can stash the SymbolID, making this workaround unnecessary.

The updated patch uses the data field, and should be ready for review.

[nridge]

Note, testing this with vscode requires this vscode-clangd patch applied (to use a newer version of the client libraries that support the data field).

[nridge]

Kadir, would you like to take a look at this, as you're already familiar with the index changes? :)

[kadircet]

Thanks, I skimmed over it (again) and I think this looks pretty great in general. I couldn't take a look at the details yet, I would really appreciate it if you could chop this one into smaller pieces (i know, i asked it before, but this is still too big). I suppose something like:

• Changes in the XRefs side, introducing {prepare,incoming,outgoing} CallHierarchy bits, relevant Protocol.h additions and unittests for those.
• Surfacing this in ClangdServer and ClangdLSPServer layer, with relevant unit/lit tests. (I would be even more happier if you could split this in two again one for each layer :) )

would be great.

If you can't split it up, that's also fine. I'll go over it eventually, it will just take longer and probably be harder to remember where we left off after each iteration :D

[nridge]

Split patch as requested

[kadircet]

clang-tools-extra/clangd/Protocol.cpp

1174

we should also populate tags and detail conditionally. rather than providing empty strings/vectors.

1203

s/"from"/"to"

clang-tools-extra/clangd/Protocol.h

1351

we use exactly the same names in protocol here, even if they don't adhere to the style guide. i.e. s/Name/name. same for others.

1367

s/Rng/range

1376

i would drop the optional, as there's no difference between empty vs none.

1405

could you put this before CallHierarchyItem ?

1408

could you put this before CallHierarchyIncomingCall, same for outgoing

[nridge]

Address review comments

[nridge]

Forgot to rename a few fields

[kadircet]

thanks, LGTM

clang-tools-extra/clangd/ClangdLSPServer.h

void onPrepareRename(const TextDocumentPositionParams &,
                        Callback<llvm::Optional<Range>>);
   void onRename(const RenameParams &, Callback<WorkspaceEdit>);
   void onHover(const TextDocumentPositionParams &,
                Callback<llvm::Optional<Hover>>);
   void onTypeHierarchy(const TypeHierarchyParams &,
                        Callback<llvm::Optional<TypeHierarchyItem>>);
   void onResolveTypeHierarchy(const ResolveTypeHierarchyItemParams &,
                               Callback<llvm::Optional<TypeHierarchyItem>>);
+  void onPrepareCallHierarchy(
+      const CallHierarchyPrepareParams &,
+      Callback<llvm::Optional<std::vector<CallHierarchyItem>>>);
+  void onCallHierarchyIncomingCalls(
+      const CallHierarchyIncomingCallsParams &,
+      Callback<llvm::Optional<std::vector<CallHierarchyIncomingCall>>>);
+  void onCallHierarchyOutgoingCalls(
+      const CallHierarchyOutgoingCallsParams &,
+      Callback<llvm::Optional<std::vector<CallHierarchyOutgoingCall>>>);
   void onChangeConfiguration(const DidChangeConfigurationParams &);
   void onSymbolInfo(const TextDocumentPositionParams &,
                     Callback<std::vector<SymbolDetails>>);
   void onSelectionRange(const SelectionRangeParams &,
                         Callback<std::vector<SelectionRange>>);
   void onDocumentLink(const DocumentLinkParams &,
                       Callback<std::vector<DocumentLink>>);
   void onSemanticTokens(const SemanticTokensParams &, Callback<SemanticTokens>);

clang-tools-extra/clangd/ClangdLSPServer.cpp

llvm::json::Object Result{
             {"referencesProvider", true},
             {"executeCommandProvider",
              llvm::json::Object{
                  {"commands",
                   {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND,
                    ExecuteCommandParams::CLANGD_APPLY_TWEAK}},
              }},
             {"typeHierarchyProvider", true},
+            {"callHierarchyProvider", true},
         }}}};
   if (NegotiatedOffsetEncoding)
     Result["offsetEncoding"] = *NegotiatedOffsetEncoding;
   if (ClangdServerOpts.TheiaSemanticHighlighting)
     Result.getObject("capabilities")
         ->insert(
             {"semanticHighlighting",
              llvm::json::Object{{"scopes", buildHighlightScopeLookupTable()}}});

 
 void ClangdLSPServer::onResolveTypeHierarchy(
     const ResolveTypeHierarchyItemParams &Params,
     Callback<Optional<TypeHierarchyItem>> Reply) {
   Server->resolveTypeHierarchy(Params.item, Params.resolve, Params.direction,
                                std::move(Reply));
 }
 
+void ClangdLSPServer::onPrepareCallHierarchy(
+    const CallHierarchyPrepareParams &Params,
+    Callback<Optional<std::vector<CallHierarchyItem>>> Reply) {
+  Server->prepareCallHierarchy(Params.textDocument.uri.file(), Params.position,
+                               std::move(Reply));
+}
+
+void ClangdLSPServer::onCallHierarchyIncomingCalls(
+    const CallHierarchyIncomingCallsParams &Params,
+    Callback<Optional<std::vector<CallHierarchyIncomingCall>>> Reply) {
+  Server->incomingCalls(Params.Item, std::move(Reply));
+}
+
+void ClangdLSPServer::onCallHierarchyOutgoingCalls(
+    const CallHierarchyOutgoingCallsParams &Params,
+    Callback<Optional<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 =
ClangdLSPServer::ClangdLSPServer(
   MsgHandler->bind("textDocument/didClose", &ClangdLSPServer::onDocumentDidClose);
   MsgHandler->bind("textDocument/didChange", &ClangdLSPServer::onDocumentDidChange);
   MsgHandler->bind("textDocument/didSave", &ClangdLSPServer::onDocumentDidSave);
   MsgHandler->bind("workspace/didChangeWatchedFiles", &ClangdLSPServer::onFileEvent);
   MsgHandler->bind("workspace/didChangeConfiguration", &ClangdLSPServer::onChangeConfiguration);
   MsgHandler->bind("textDocument/symbolInfo", &ClangdLSPServer::onSymbolInfo);
   MsgHandler->bind("textDocument/typeHierarchy", &ClangdLSPServer::onTypeHierarchy);
   MsgHandler->bind("typeHierarchy/resolve", &ClangdLSPServer::onResolveTypeHierarchy);
+  MsgHandler->bind("textDocument/prepareCallHierarchy", &ClangdLSPServer::onPrepareCallHierarchy);
+  MsgHandler->bind("callHierarchy/incomingCalls", &ClangdLSPServer::onCallHierarchyIncomingCalls);
+  MsgHandler->bind("callHierarchy/outgoingCalls", &ClangdLSPServer::onCallHierarchyOutgoingCalls);
   MsgHandler->bind("textDocument/selectionRange", &ClangdLSPServer::onSelectionRange);
   MsgHandler->bind("textDocument/documentLink", &ClangdLSPServer::onDocumentLink);
   MsgHandler->bind("textDocument/semanticTokens/full", &ClangdLSPServer::onSemanticTokens);
   MsgHandler->bind("textDocument/semanticTokens/full/delta", &ClangdLSPServer::onSemanticTokensDelta);
   if (Opts.FoldingRanges)
     MsgHandler->bind("textDocument/foldingRange", &ClangdLSPServer::onFoldingRange);
   // clang-format on
 }

clang-tools-extra/clangd/ClangdServer.h

void typeHierarchy(PathRef File, Position Pos, int Resolve,
                      TypeHierarchyDirection Direction,
                      Callback<llvm::Optional<TypeHierarchyItem>> CB);
 
   /// Resolve type hierarchy item in the given direction.
   void resolveTypeHierarchy(TypeHierarchyItem Item, int Resolve,
                             TypeHierarchyDirection Direction,
                             Callback<llvm::Optional<TypeHierarchyItem>> CB);
 
+  /// Get information about call hierarchy for a given position.
+  void prepareCallHierarchy(
+      PathRef File, Position Pos,
+      Callback<llvm::Optional<std::vector<CallHierarchyItem>>> CB);
+
+  /// Resolve incoming calls for a given call hierarchy item.
+  void incomingCalls(
+      const CallHierarchyItem &Item,
+      Callback<llvm::Optional<std::vector<CallHierarchyIncomingCall>>>);
+
+  /// Resolve outgoing calls for a given call hierarchy item.
+  void outgoingCalls(
+      const CallHierarchyItem &Item,
+      Callback<llvm::Optional<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

 
 void ClangdServer::resolveTypeHierarchy(
     TypeHierarchyItem Item, int Resolve, TypeHierarchyDirection Direction,
     Callback<llvm::Optional<TypeHierarchyItem>> CB) {
   clangd::resolveTypeHierarchy(Item, Resolve, Direction, Index);
   CB(Item);
 }
 
+void ClangdServer::prepareCallHierarchy(
+    PathRef File, Position Pos,
+    Callback<llvm::Optional<std::vector<CallHierarchyItem>>> CB) {
+  auto Action = [File = File.str(), Pos, CB = std::move(CB),
+                 this](Expected<InputsAndAST> InpAST) mutable {
+    if (!InpAST)
+      return CB(InpAST.takeError());
+    CB(clangd::prepareCallHierarchy(InpAST->AST, Pos, Index, File));
+  };
+  WorkScheduler.runWithAST("Call Hierarchy", File, std::move(Action));
+}
+
+void ClangdServer::incomingCalls(
+    const CallHierarchyItem &Item,
+    Callback<llvm::Optional<std::vector<CallHierarchyIncomingCall>>> CB) {
+  CB(clangd::incomingCalls(Item, Index));
+}
+
+void ClangdServer::outgoingCalls(
+    const CallHierarchyItem &Item,
+    Callback<llvm::Optional<std::vector<CallHierarchyOutgoingCall>>> CB) {
+  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/Protocol.h

struct ResolveTypeHierarchyItemParams {
   /// The hierarchy levels to resolve. `0` indicates no level.
   int resolve;
 
   /// The direction of the hierarchy levels to resolve.
   TypeHierarchyDirection direction;
 };
 bool fromJSON(const llvm::json::Value &, ResolveTypeHierarchyItemParams &);
 
+enum class SymbolTag { Deprecated = 1 };
+llvm::json::Value toJSON(SymbolTag);
+
+/// Represents programming constructs like functions or constructors
+/// in the context of call hierarchy.
+struct CallHierarchyItem {
+  /// The name of this item.
+  std::string Name;
+
+  /// The kind of this item.
+  SymbolKind Kind;
+
+  /// Tags for this item.
+  std::vector<SymbolTag> Tags;
+
+  /// More detaill for this item, e.g. the signature of a function.
+  std::string Detail;
+
+  /// The resource identifier of this item.
+  URIForFile Uri;
+
+  /// The range enclosing this symbol not including leading / trailing
+  /// whitespace but everything else, e.g. comments and code.
+  Range Rng;
+
+  /// The range that should be selected and revealed when this symbol
+  /// is being picked, e.g. the name of a function.
+  /// Must be contained by `Rng`.
+  Range SelectionRange;
+};
+llvm::json::Value toJSON(const CallHierarchyItem &);
+bool fromJSON(const llvm::json::Value &, CallHierarchyItem &);
+
+/// Represents an incoming call, e.g. a caller of a method or constructor.
+struct CallHierarchyIncomingCall {
+  /// The item that makes the call.
+  CallHierarchyItem From;
+
+  /// The range at which the calls appear.
+  /// This is relative to the caller denoted by `From`.
+  std::vector<Range> FromRanges;
+};
+llvm::json::Value toJSON(const CallHierarchyIncomingCall &);
+
+/// Represents an outgoing call, e.g. calling a getter from a method or
+/// a method from a constructor etc.
+struct CallHierarchyOutgoingCall {
+  /// The item that is called.
+  CallHierarchyItem To;
+
+  /// The range at which this item is called.
+  /// This is the range relative to the caller, and not `To`.
+  std::vector<Range> FromRanges;
+};
+llvm::json::Value toJSON(const CallHierarchyOutgoingCall &);
+
+/// The parameter of a `textDocument/prepareCallHierarchy` request.
+struct CallHierarchyPrepareParams : public TextDocumentPositionParams {};
+
+/// The parameter of a `callHierarchy/incomingCalls` request.
+struct CallHierarchyIncomingCallsParams {
+  CallHierarchyItem Item;
+};
+bool fromJSON(const llvm::json::Value &, CallHierarchyIncomingCallsParams &);
+
+/// The parameter of a `callHierarchy/outgoingCalls` request.
+struct CallHierarchyOutgoingCallsParams {
+  CallHierarchyItem Item;
+};
+bool fromJSON(const llvm::json::Value &, CallHierarchyOutgoingCallsParams &);
+
 struct ReferenceParams : public TextDocumentPositionParams {
   // For now, no options like context.includeDeclaration are supported.
 };
 bool fromJSON(const llvm::json::Value &, ReferenceParams &);
 
 /// Clangd extension: indicates the current state of the file in clangd,
 /// sent from server via the `textDocument/clangd.fileStatus` notification.
 struct FileStatus {

clang-tools-extra/clangd/Protocol.cpp

bool fromJSON(const llvm::json::Value &Params, DidSaveTextDocumentParams &R) {
   llvm::json::ObjectMapper O(Params);
   return O && O.map("textDocument", R.textDocument);
 }
 
 bool fromJSON(const llvm::json::Value &Params, DidChangeTextDocumentParams &R) {
   llvm::json::ObjectMapper O(Params);
   if (!O)
     return false;
-  O.map("forceRebuild", R.forceRebuild);  // Optional clangd extension.
+  O.map("forceRebuild", R.forceRebuild); // Optional clangd extension.
   return O.map("textDocument", R.textDocument) &&
          O.map("contentChanges", R.contentChanges) &&
          O.map("wantDiagnostics", R.wantDiagnostics);
 }
 
 bool fromJSON(const llvm::json::Value &E, FileChangeType &Out) {
   if (auto T = E.getAsInteger()) {
     if (*T < static_cast<int>(FileChangeType::Created) ||
return O && O.map("item", P.item) && O.map("resolve", P.resolve) &&
          O.map("direction", P.direction);
 }
 
 bool fromJSON(const llvm::json::Value &Params, ReferenceParams &R) {
   TextDocumentPositionParams &Base = R;
   return fromJSON(Params, Base);
 }
 
+llvm::json::Value toJSON(SymbolTag Tag) {
+  return llvm::json::Value{static_cast<int>(Tag)};
+}
+
+llvm::json::Value toJSON(const CallHierarchyItem &I) {
+  return llvm::json::Object{
+      {"name", I.Name}, {"kind", static_cast<int>(I.Kind)},
+      {"tags", I.Tags}, {"detail", I.Detail},
+      {"range", I.Rng}, {"selectionRange", I.SelectionRange},
+      {"uri", I.Uri}};
+}
+
+bool fromJSON(const llvm::json::Value &Params, CallHierarchyItem &I) {
+  llvm::json::ObjectMapper O(Params);
+
+  // Populate the required fields only. We don't care about the
+  // optional fields `Tags` and `Detail` for the purpose of
+  // client --> server communication.
+  return O && O.map("name", I.Name) && O.map("kind", I.Kind) &&
+         O.map("uri", I.Uri) && O.map("range", I.Rng) &&
+         O.map("selectionRange", I.SelectionRange);
+}
+
+llvm::json::Value toJSON(const CallHierarchyIncomingCall &C) {
+  return llvm::json::Object{{"from", C.From}, {"fromRanges", C.FromRanges}};
+}
+
+llvm::json::Value toJSON(const CallHierarchyOutgoingCall &C) {
+  return llvm::json::Object{{"from", C.To}, {"fromRanges", C.FromRanges}};
+}
+
+bool fromJSON(const llvm::json::Value &Params,
+              CallHierarchyIncomingCallsParams &P) {
+  llvm::json::ObjectMapper O(Params);
+  return O.map("item", P.Item);
+}
+
+bool fromJSON(const llvm::json::Value &Params,
+              CallHierarchyOutgoingCallsParams &P) {
+  llvm::json::ObjectMapper O(Params);
+  return O.map("item", P.Item);
+}
+
 static const char *toString(OffsetEncoding OE) {
   switch (OE) {
   case OffsetEncoding::UTF8:
     return "utf-8";
   case OffsetEncoding::UTF16:
     return "utf-16";
   case OffsetEncoding::UTF32:
     return "utf-32";

clang-tools-extra/clangd/XRefs.h

 llvm::Optional<TypeHierarchyItem> getTypeHierarchy(
     ParsedAST &AST, Position Pos, int Resolve, TypeHierarchyDirection Direction,
     const SymbolIndex *Index = nullptr, PathRef TUPath = PathRef{});
 
 void resolveTypeHierarchy(TypeHierarchyItem &Item, int ResolveLevels,
                           TypeHierarchyDirection Direction,
                           const SymbolIndex *Index);
 
+/// Get call hierarchy information at \p Pos.
+llvm::Optional<std::vector<CallHierarchyItem>>
+prepareCallHierarchy(ParsedAST &AST, Position Pos, const SymbolIndex *Index,
+                     PathRef TUPath);
+
+llvm::Optional<std::vector<CallHierarchyIncomingCall>>
+incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index);
+
+llvm::Optional<std::vector<CallHierarchyOutgoingCall>>
+outgoingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index);
+
 /// Returns all decls that are referenced in the \p FD except local symbols.
 llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
                                                  const FunctionDecl *FD);
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H

clang-tools-extra/clangd/XRefs.cpp

 //===--- 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"
 #include "AST.h"
 #include "CodeCompletionStrings.h"
 #include "FindSymbols.h"
 #include "FindTarget.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "Quality.h"
 #include "Selection.h"
 #include "SourceCode.h"
 #include "URI.h"
+#include "XRefs.h"
 #include "index/Index.h"
 #include "index/Merge.h"
 #include "index/Relation.h"
 #include "index/SymbolLocation.h"
 #include "support/Logger.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/Attr.h"

 #include "clang/Basic/TokenKinds.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/IndexingOptions.h"
 #include "clang/Index/USRGeneration.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
   // for parents.
   if (auto ID = getSymbolID(&ND)) {
     THI.data = ID->str();
   }
 
   return THI;
 }
 
-static Optional<TypeHierarchyItem>
-symbolToTypeHierarchyItem(const Symbol &S, const SymbolIndex *Index,
+static Optional<TypeHierarchyItem> symbolToTypeHierarchyItem(const Symbol &S,
                                                              PathRef TUPath) {
   auto Loc = symbolToLocation(S, TUPath);
   if (!Loc) {
     log("Type hierarchy: {0}", Loc.takeError());
     return llvm::None;
   }
   TypeHierarchyItem THI;
   THI.name = std::string(S.Name);
   THI.kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);

 static void fillSubTypes(const SymbolID &ID,
                          std::vector<TypeHierarchyItem> &SubTypes,
                          const SymbolIndex *Index, int Levels, PathRef TUPath) {
   RelationsRequest Req;
   Req.Subjects.insert(ID);
   Req.Predicate = RelationKind::BaseOf;
   Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
     if (Optional<TypeHierarchyItem> ChildSym =
-            symbolToTypeHierarchyItem(Object, Index, TUPath)) {
+            symbolToTypeHierarchyItem(Object, TUPath)) {
       if (Levels > 1) {
         ChildSym->children.emplace();
         fillSubTypes(Object.ID, *ChildSym->children, Index, Levels - 1, TUPath);
       }
       SubTypes.emplace_back(std::move(*ChildSym));
     }
   });
 }
if (Index && Item.data) {
     // We store the item's SymbolID in the 'data' field, and the client
     // passes it back to us in typeHierarchy/resolve.
     if (Expected<SymbolID> ID = SymbolID::fromStr(*Item.data)) {
       fillSubTypes(*ID, *Item.children, Index, ResolveLevels, Item.uri.file());
     }
   }
 }
 
+static llvm::Optional<CallHierarchyItem>
+declToCallHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
+  auto &SM = Ctx.getSourceManager();
+  SourceLocation NameLoc = nameLocation(ND, Ctx.getSourceManager());
+  SourceLocation BeginLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getBeginLoc()));
+  SourceLocation EndLoc = SM.getSpellingLoc(SM.getFileLoc(ND.getEndLoc()));
+  const auto DeclRange =
+      toHalfOpenFileRange(SM, Ctx.getLangOpts(), {BeginLoc, EndLoc});
+  if (!DeclRange)
+    return llvm::None;
+  auto FilePath =
+      getCanonicalPath(SM.getFileEntryForID(SM.getFileID(NameLoc)), SM);
+  auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
+  if (!FilePath || !TUPath)
+    return llvm::None; // Not useful without a uri.
+
+  Position NameBegin = sourceLocToPosition(SM, NameLoc);
+  Position NameEnd = sourceLocToPosition(
+      SM, Lexer::getLocForEndOfToken(NameLoc, 0, SM, Ctx.getLangOpts()));
+
+  index::SymbolInfo SymInfo = index::getSymbolInfo(&ND);
+  // FIXME: this is not classifying constructors, destructors and operators
+  //        correctly (they're all "methods").
+  SymbolKind SK = indexSymbolKindToSymbolKind(SymInfo.Kind);
+
+  CallHierarchyItem CHI;
+  // We need to print the fully qualified name, otherwise we can't recover
+  // the symbol from the CallHierarchyItem.
+  CHI.Name = printQualifiedName(ND);
+  CHI.Kind = SK;
+  if (ND.isDeprecated()) {
+    CHI.Tags.push_back(SymbolTag::Deprecated);
+  }
+  CHI.Rng = Range{sourceLocToPosition(SM, DeclRange->getBegin()),
+                  sourceLocToPosition(SM, DeclRange->getEnd())};
+  CHI.SelectionRange = Range{NameBegin, NameEnd};
+  if (!CHI.Rng.contains(CHI.Rng)) {
+    // 'selectionRange' must be contained in 'range', so in cases where clang
+    // reports unrelated ranges we need to reconcile somehow.
+    CHI.Rng = CHI.SelectionRange;
+  }
+
+  CHI.Uri = URIForFile::canonicalize(*FilePath, *TUPath);
+
+  return CHI;
+}
+
+llvm::Optional<std::vector<CallHierarchyItem>>
+prepareCallHierarchy(ParsedAST &AST, Position Pos, const SymbolIndex *Index,
+                     PathRef TUPath) {
+  const auto &SM = AST.getSourceManager();
+  auto Loc = sourceLocationInMainFile(SM, Pos);
+  if (!Loc) {
+    llvm::consumeError(Loc.takeError());
+    return llvm::None;
+  }
+  std::vector<CallHierarchyItem> Result;
+  for (const NamedDecl *Decl : getDeclAtPosition(AST, *Loc, {})) {
+    if (Decl->isFunctionOrFunctionTemplate()) {
+      if (auto CHI = declToCallHierarchyItem(AST.getASTContext(), *Decl))
+        Result.push_back(*std::move(CHI));
+    }
+  }
+  return Result;
+}
+
+static llvm::Optional<Symbol>
+callHierarchyItemToSymbol(const CallHierarchyItem &Item,
+                          const SymbolIndex *Index) {
+  FuzzyFindRequest Request;
+  auto Split = splitQualifiedName(Item.Name);
+  Request.Query = std::string(Split.second);
+  if (!Split.first.empty())
+    Request.Scopes = {std::string(Split.first)};
+  // Explain.
+  Request.AnyScope = true;
+  llvm::Optional<Symbol> Result;
+  bool Found = false;
+  auto OnFuzzyMatch = [&](const Symbol &S) {
+    if (Found)
+      return;
+    if (S.Name != Split.second)
+      return;
+
+    auto LocationMatches = [&](const SymbolLocation &L) {
+      if (!L)
+        return false;
+      auto Loc = indexToLSPLocation(L, Item.Uri.file());
+      if (Loc) {
+        vlog("Comparing locations {0}:{1} and {2}:{3}", Loc->uri.uri(),
+             Loc->range, Item.Uri.uri(), Item.SelectionRange);
+      }
+      return Loc && Loc->uri == Item.Uri && Loc->range == Item.SelectionRange;
+    };
+    if (!(LocationMatches(S.Definition) ||
+          LocationMatches(S.CanonicalDeclaration)))
+      return;
+
+    Result = S;
+    Found = true;
+  };
+  Index->fuzzyFind(Request, OnFuzzyMatch);
+  /*if (!Found && !Request.AnyScope) {
+    // If we didn't find any results when searching with AnyScope=false,
+    // fall back on trying AnyScope=true.
+    // This is a workaround for the fact that symbols in anonymous
+    // namespaces are not found inside a scope that comes from printing
+    // their qualifier (which omits anonymous namespaces).
+    Request.AnyScope = true;
+    Index->fuzzyFind(Request, OnFuzzyMatch);
+  }*/
+  return Result;
+}
+
+llvm::Optional<CallHierarchyItem> symbolToCallHierarchyItem(const Symbol &S,
+                                                            PathRef TUPath) {
+  auto Loc = symbolToLocation(S, TUPath);
+  if (!Loc) {
+    log("Type hierarchy: {0}", Loc.takeError());
+    return llvm::None;
+  }
+  CallHierarchyItem CHI;
+  CHI.Name = std::string(S.Name);
+  CHI.Kind = indexSymbolKindToSymbolKind(S.SymInfo.Kind);
+  if (S.Flags & Symbol::Deprecated)
+    CHI.Tags.push_back(SymbolTag::Deprecated);
+  CHI.Detail = S.Signature.str();
+  CHI.SelectionRange = Loc->range;
+  // FIXME: Populate 'range' correctly
+  // (https://github.com/clangd/clangd/issues/59).
+  CHI.Rng = CHI.SelectionRange;
+  CHI.Uri = Loc->uri;
+
+  return std::move(CHI);
+}
+
+llvm::Optional<std::vector<CallHierarchyIncomingCall>>
+incomingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
+  // Unlike TypeHierarchyItem, CallHierarchyItem does not have a "data"
+  // field into which we can stash a SymbolID (and we can't unilaterally
+  // add one because client implementations of call hierarchy, e.g. the
+  // one in vscode, don't know about it and wouldn't round-trip it).
+  // So, we have to reconstitute the symbol based on the information
+  // present in the CallHierarchyItem.
+  if (!Index)
+    return llvm::None;
+  auto Sym = callHierarchyItemToSymbol(Item, Index);
+  if (!Sym)
+    return llvm::None;
+  RefsRequest Request;
+  Request.IDs.insert(Sym->ID);
+  // FIXME: Perhaps we should be even more specific and introduce a
+  // RefKind for calls, and use that?
+  Request.Filter = RefKind::Reference;
+  // Initially store the results in a map keyed by SymbolID.
+  // This allows us to group different calls with the same caller
+  // into the same CallHierarchyIncomingCall.
+  llvm::DenseMap<SymbolID, CallHierarchyIncomingCall> ResultMap;
+  Index->refs(Request, [&](const Ref &R) {
+    if (auto Loc = indexToLSPLocation(R.Location, Item.Uri.file())) {
+      LookupRequest Lookup;
+      Lookup.IDs.insert(R.Referrer);
+      Index->lookup(Lookup, [&](const Symbol &Caller) {
+        // See if we already have a CallHierarchyIncomingCall for this caller.
+        auto It = ResultMap.find(Caller.ID);
+        if (It == ResultMap.end()) {
+          // If not, try to create one.
+          if (auto CHI = symbolToCallHierarchyItem(Caller, Item.Uri.file())) {
+            CallHierarchyIncomingCall Call;
+            Call.From = *CHI;
+            It = ResultMap.insert({Caller.ID, std::move(Call)}).first;
+          }
+        }
+        if (It != ResultMap.end()) {
+          It->second.FromRanges.push_back(Loc->range);
+        }
+      });
+    }
+  });
+  // Flatten the results into a vector.
+  std::vector<CallHierarchyIncomingCall> Results;
+  for (auto &&Entry : ResultMap) {
+    Results.push_back(std::move(Entry.second));
+  }
+  return Results;
+}
+
+llvm::Optional<std::vector<CallHierarchyOutgoingCall>>
+outgoingCalls(const CallHierarchyItem &Item, const SymbolIndex *Index) {
+  // TODO: Implement.
+  return llvm::None;
+}
+
 llvm::DenseSet<const Decl *> getNonLocalDeclRefs(ParsedAST &AST,
                                                  const FunctionDecl *FD) {
   if (!FD->hasBody())
     return {};
   llvm::DenseSet<const Decl *> DeclRefs;
   findExplicitReferences(FD, [&](ReferenceLoc Ref) {
     for (const Decl *D : Ref.Targets) {
       if (!index::isFunctionLocalSymbol(D) && !D->isTemplateParameter() &&
           !Ref.IsDecl)
         DeclRefs.insert(D);
     }
   });
   return DeclRefs;
 }
 } // namespace clangd
 } // namespace clang

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

 /// Represents a symbol occurrence in the source file.
 /// Despite the name, it could be a declaration/definition/reference.
 ///
 /// WARNING: Location does not own the underlying data - Copies are shallow.
 struct Ref {
   /// The source location where the symbol is named.
   SymbolLocation Location;
   RefKind Kind = RefKind::Unknown;
+  SymbolID Referrer;
 };
 
 inline bool operator<(const Ref &L, const Ref &R) {
-  return std::tie(L.Location, L.Kind) < std::tie(R.Location, R.Kind);
+  return std::tie(L.Location, L.Kind, L.Referrer) <
+         std::tie(R.Location, R.Kind, R.Referrer);
 }
 inline bool operator==(const Ref &L, const Ref &R) {
-  return std::tie(L.Location, L.Kind) == std::tie(R.Location, R.Kind);
+  return std::tie(L.Location, L.Kind, L.Referrer) ==
+         std::tie(R.Location, R.Kind, R.Referrer);
 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Ref &);
 
 /// An efficient structure of storing large set of symbol references in memory.
 /// Filenames are deduplicated.
 class RefSlab {
 public:

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

 
 void writeRefs(const SymbolID &ID, llvm::ArrayRef<Ref> Refs,
                const StringTableOut &Strings, llvm::raw_ostream &OS) {
   OS << ID.raw();
   writeVar(Refs.size(), OS);
   for (const auto &Ref : Refs) {
     OS.write(static_cast<unsigned char>(Ref.Kind));
     writeLocation(Ref.Location, Strings, OS);
+    OS << Ref.Referrer.raw();
   }
 }
 
 std::pair<SymbolID, std::vector<Ref>>
 readRefs(Reader &Data, llvm::ArrayRef<llvm::StringRef> Strings) {
   std::pair<SymbolID, std::vector<Ref>> Result;
   Result.first = Data.consumeID();
   Result.second.resize(Data.consumeVar());
   for (auto &Ref : Result.second) {
     Ref.Kind = static_cast<RefKind>(Data.consume8());
     Ref.Location = readLocation(Data, Strings);
+    Ref.Referrer = Data.consumeID();
   }
   return Result;
 }
 
 // RELATIONS ENCODING
 // A relations section is a flat list of relations. Each relation has:
 //  - SymbolID (subject): 8 bytes
 //  - relation kind (predicate): 1 byte

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

private:
   RefSlab::Builder Refs;
   // All relations collected from the AST.
   RelationSlab::Builder Relations;
   ASTContext *ASTCtx;
   std::shared_ptr<Preprocessor> PP;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
   std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo;
   Options Opts;
-  using SymbolRef = std::pair<SourceLocation, index::SymbolRoleSet>;
+  struct SymbolRef {
+    SourceLocation Loc;
+    index::SymbolRoleSet Roles;
+    const NamedDecl *Referrer;
+  };
   // Symbols referenced from the current TU, flushed on finish().
   llvm::DenseSet<const NamedDecl *> ReferencedDecls;
   llvm::DenseSet<const IdentifierInfo *> ReferencedMacros;
   llvm::DenseMap<const NamedDecl *, std::vector<SymbolRef>> DeclRefs;
   llvm::DenseMap<SymbolID, std::vector<SymbolRef>> MacroRefs;
   // Maps canonical declaration provided by clang to canonical declaration for
   // an index symbol, if clangd prefers a different declaration than that
   // provided by clang. For example, friend declaration might be considered

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

bool SymbolCollector::handleDeclOccurrence(
   // AST-based xref).
   // FIXME: we should try to use the file locations for other fields.
   if (CollectRef &&
       (!IsMainFileOnly || Opts.CollectMainFileRefs ||
        ND->isExternallyVisible()) &&
       !isa<NamespaceDecl>(ND) &&
       (Opts.RefsInHeaders ||
        SM.getFileID(SM.getFileLoc(Loc)) == SM.getMainFileID()))
-    DeclRefs[ND].emplace_back(SM.getFileLoc(Loc), Roles);
+    DeclRefs[ND].push_back(
+        SymbolRef{SM.getFileLoc(Loc), Roles,
+                  dyn_cast_or_null<NamedDecl>(ASTNode.Parent)});
   // Don't continue indexing if this is a mere reference.
   if (IsOnlyRef)
     return true;
 
   // FIXME: ObjCPropertyDecl are not properly indexed here:
   // - ObjCPropertyDecl may have an OrigD of ObjCPropertyImplDecl, which is
   // not a NamedDecl.
   auto *OriginalDecl = dyn_cast<NamedDecl>(ASTNode.OrigD);
bool SymbolCollector::handleMacroOccurrence(const IdentifierInfo *Name,
   auto SpellingLoc = SM.getSpellingLoc(Loc);
   bool IsMainFileOnly =
       SM.isInMainFile(SM.getExpansionLoc(DefLoc)) &&
       !isHeaderFile(SM.getFileEntryForID(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()))
-    MacroRefs[*ID].push_back({Loc, Roles});
+    // FIXME: Populate referrer information for macro references.
+    MacroRefs[*ID].push_back({Loc, Roles, /*Referrer=*/nullptr});
 
   // Collect symbols.
   if (!Opts.CollectMacro)
     return true;
 
   // Skip main-file macros if we are not collecting them.
   if (IsMainFileOnly && !Opts.CollectMainFileSymbols)
     return false;
if (Found == URICache.end()) {
       } else {
         // Ignore cases where we can not find a corresponding file entry for
         // given location, e.g. symbols formed via macro concatenation.
         return None;
       }
     }
     return Found->second;
   };
-  auto CollectRef =
-      [&](SymbolID ID,
-          const std::pair<SourceLocation, index::SymbolRoleSet> &LocAndRole,
+  auto CollectRef = [&](SymbolID ID, const SymbolRef &LocAndRole,
                         bool Spelled = false) {
-        auto FileID = SM.getFileID(LocAndRole.first);
-        // FIXME: use the result to filter out references.
-        shouldIndexFile(FileID);
-        if (auto FileURI = GetURI(FileID)) {
-          auto Range =
-              getTokenRange(LocAndRole.first, SM, ASTCtx->getLangOpts());
-          Ref R;
-          R.Location.Start = Range.first;
-          R.Location.End = Range.second;
-          R.Location.FileURI = FileURI->c_str();
-          R.Kind = toRefKind(LocAndRole.second, Spelled);
-          Refs.insert(ID, R);
-        }
-      };
+    auto FileID = SM.getFileID(LocAndRole.Loc);
+      auto Range = getTokenRange(LocAndRole.Loc, SM, ASTCtx->getLangOpts());
+      R.Kind = toRefKind(LocAndRole.Roles, Spelled);
+      if (auto RefID = getSymbolID(LocAndRole.Referrer))
+        R.Referrer = *RefID;
   // Populate Refs slab from MacroRefs.
   // FIXME: All MacroRefs are marked as Spelled now, but this should be checked.
   for (const auto &IDAndRefs : MacroRefs)
     for (const auto &LocAndRole : IDAndRefs.second)
       CollectRef(IDAndRefs.first, LocAndRole, /*Spelled=*/true);
   // Populate Refs slab from DeclRefs.
   llvm::DenseMap<FileID, std::vector<syntax::Token>> FilesToTokensCache;
   for (auto &DeclAndRef : DeclRefs) {
     if (auto ID = getSymbolID(DeclAndRef.first)) {
       for (auto &LocAndRole : DeclAndRef.second) {
-        const auto FileID = SM.getFileID(LocAndRole.first);
+        const auto FileID = SM.getFileID(LocAndRole.Loc);
         // FIXME: It's better to use TokenBuffer by passing spelled tokens from
         // the caller of SymbolCollector.
         if (!FilesToTokensCache.count(FileID))
           FilesToTokensCache[FileID] =
               syntax::tokenize(FileID, SM, ASTCtx->getLangOpts());
         llvm::ArrayRef<syntax::Token> Tokens = FilesToTokensCache[FileID];
         // Check if the referenced symbol is spelled exactly the same way the
         // corresponding NamedDecl is. If it is, mark this reference as spelled.
         const auto *IdentifierToken =
-            spelledIdentifierTouching(LocAndRole.first, Tokens);
+            spelledIdentifierTouching(LocAndRole.Loc, Tokens);
         DeclarationName Name = DeclAndRef.first->getDeclName();
         const auto NameKind = Name.getNameKind();
         bool IsTargetKind = NameKind == DeclarationName::Identifier ||
                             NameKind == DeclarationName::CXXConstructorName;
         bool Spelled = IdentifierToken && IsTargetKind &&
                        Name.getAsString() == IdentifierToken->text(SM);
         CollectRef(*ID, LocAndRole, Spelled);
       }

clang-tools-extra/clangd/test/initialize-params.test

 # RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %s
 # Test initialize request parameters with rootUri
 {"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootUri":"test:///workspace","capabilities":{},"trace":"off"}}
 #      CHECK:  "id": 0,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "capabilities": {
+# CHECK-NEXT:      "callHierarchyProvider": true,
 # CHECK-NEXT:      "codeActionProvider": true,
 # CHECK-NEXT:      "completionProvider": {
 # CHECK-NEXT:        "allCommitCharacters": [
 # CHECK-NEXT:          " ",
 # CHECK-NEXT:          "\t",
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ")",
 # CHECK-NEXT:          "[",

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

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

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

+//===-- CallHierarchyTests.cpp  ---------------------------*- C++ -*-------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "Annotations.h"
+#include "Compiler.h"
+#include "Matchers.h"
+#include "ParsedAST.h"
+#include "SyncAPI.h"
+#include "TestFS.h"
+#include "TestTU.h"
+#include "XRefs.h"
+#include "index/FileIndex.h"
+#include "index/SymbolCollector.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/Index/IndexingAction.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using ::testing::AllOf;
+using ::testing::ElementsAre;
+using ::testing::Eq;
+using ::testing::Field;
+using ::testing::IsEmpty;
+using ::testing::Matcher;
+using ::testing::Pointee;
+using ::testing::UnorderedElementsAre;
+
+// Helpers for matching call hierarchy data structures.
+MATCHER_P(WithName, N, "") { return arg.Name == N; }
+MATCHER_P(WithSelectionRange, R, "") { return arg.SelectionRange == R; }
+
+template <class ItemMatcher>
+::testing::Matcher<CallHierarchyIncomingCall> From(ItemMatcher M) {
+  return Field(&CallHierarchyIncomingCall::From, M);
+}
+template <class... RangeMatchers>
+::testing::Matcher<CallHierarchyIncomingCall> FromRanges(RangeMatchers... M) {
+  return Field(&CallHierarchyIncomingCall::FromRanges,
+               UnorderedElementsAre(M...));
+}
+
+TEST(CallHierarchy, IncomingOneFile) {
+  Annotations Source(R"cpp(
+    void call^ee(int);
+    void caller1() {
+      $Callee[[callee]](42);
+    }
+    void caller2() {
+      $Caller1A[[caller1]]();
+      $Caller1B[[caller1]]();
+    }
+    void caller3() {
+      $Caller1C[[caller1]]();
+      $Caller2[[caller2]]();
+    }
+  )cpp");
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
+
+  llvm::Optional<std::vector<CallHierarchyItem>> Items = prepareCallHierarchy(
+      AST, Source.point(), Index.get(), testPath(TU.Filename));
+  ASSERT_TRUE(bool(Items));
+  EXPECT_THAT(*Items, ElementsAre(WithName("callee")));
+  auto IncomingLevel1 = incomingCalls((*Items)[0], Index.get());
+  ASSERT_TRUE(bool(IncomingLevel1));
+  EXPECT_THAT(*IncomingLevel1,
+              ElementsAre(AllOf(From(WithName("caller1")),
+                                FromRanges(Source.range("Callee")))));
+
+  auto IncomingLevel2 = incomingCalls((*IncomingLevel1)[0].From, Index.get());
+  ASSERT_TRUE(bool(IncomingLevel2));
+  EXPECT_THAT(
+      *IncomingLevel2,
+      UnorderedElementsAre(
+          AllOf(From(WithName("caller2")),
+                FromRanges(Source.range("Caller1A"), Source.range("Caller1B"))),
+          AllOf(From(WithName("caller3")),
+                FromRanges(Source.range("Caller1C")))));
+
+  auto IncomingLevel3 = incomingCalls((*IncomingLevel2)[0].From, Index.get());
+  ASSERT_TRUE(bool(IncomingLevel3));
+  EXPECT_THAT(*IncomingLevel3,
+              ElementsAre(AllOf(From(WithName("caller3")),
+                                FromRanges(Source.range("Caller2")))));
+
+  auto IncomingLevel4 = incomingCalls((*IncomingLevel3)[0].From, Index.get());
+  ASSERT_TRUE(bool(IncomingLevel4));
+  EXPECT_THAT(*IncomingLevel4, ElementsAre());
+}
+
+TEST(CallHierarchy, IncomingQualified) {
+  Annotations Source(R"cpp(
+    namespace ns {
+    struct Waldo {
+      void find();
+    };
+    void Waldo::find() {}
+    void caller1(Waldo &W) {
+      W.$Caller1[[f^ind]]();
+    }
+    void caller2(Waldo &W) {
+      W.$Caller2[[find]]();
+    }
+    }
+  )cpp");
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
+
+  llvm::Optional<std::vector<CallHierarchyItem>> Items = prepareCallHierarchy(
+      AST, Source.point(), Index.get(), testPath(TU.Filename));
+  ASSERT_TRUE(bool(Items));
+  EXPECT_THAT(*Items, ElementsAre(WithName("find")));
+  auto Incoming = incomingCalls((*Items)[0], Index.get());
+  ASSERT_TRUE(bool(Incoming));
+  EXPECT_THAT(*Incoming,
+              UnorderedElementsAre(AllOf(From(WithName("caller1")),
+                                         FromRanges(Source.range("Caller1"))),
+                                   AllOf(From(WithName("caller2")),
+                                         FromRanges(Source.range("Caller2")))));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang

llvm/utils/gn/secondary/clang-tools-extra/clangd/unittests/BUILD.gn

include_dirs = [
 
     # To pick up the generated DecisionForestRuntimeTest.h file.
     target_gen_dir,
   ]
   sources = [
     "ASTTests.cpp",
     "Annotations.cpp",
     "BackgroundIndexTests.cpp",
+    "CallHierarchyTests.cpp",
     "CanonicalIncludesTests.cpp",
     "ClangdLSPServerTests.cpp",
     "ClangdTests.cpp",
     "CodeCompleteTests.cpp",
     "CodeCompletionStringsTests.cpp",
     "CollectMacrosTests.cpp",
     "CompileCommandsTests.cpp",
     "CompilerTests.cpp",