[clangd] Ensure Ref::Container refers to an indexed symbol

[nridge]

Summary

Fixes https://github.com/clangd/clangd/issues/806

[kadircet]

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

360

why do we need to expose this function in the class interface? ASTCtx is reachable from Decl, and we can just pass in Opts.

Also I believe we should take in a declcontext as an input parameter, and make use of ASTNode.ParentDC for starting the traversal.

This also requires some comments explaining that it'll return the first context that is known by index.

361

in theory enclosing namespace can also be unnamed, something like a BlockDecl.

I think we should enforce the return value to be a named decl, but I don't think we should enforce any intermediate parents to be named decls.

506–507

as mentioned above I think we should start the traversal from ASTNode.ParentDC. any downsides to doing that ? I don't see a case where this container we return is not a DeclContext.

[nridge]

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

506–507

I assume you mean ASTNode.ContainerDC.

I tried this suggestion, but it looks like ContainerDC does not contain what we want in many cases.

For all of the following cases in SymbolCollectorTest.RefContainers:

• ref2 (variable initializer)
• ref3 (function parameter default value)
• ref5 (template parameter default value)
• ref6 (type of variable)
• ref7a (return type of function)
• ref7b (parameter type of function)

ASTNode.ContainerDC is the TranslationUnitDecl (i.e. the DeclContext in which the function or variable is declared) rather than the function or variable itself.

In addition, for ref4 (member initializer), ContainerDC is the RecordDecl rather than the FieldDecl.

So, I don't think this suggestion will work without making the Ref::Container field significantly less specific (and thereby the call hierarchy feature less useful in some cases).

[nridge]

Addressed review comments, except for the one about using ContainerDC, for the reason explained

[kadircet]

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

159

can you also add some info about why we are not using DeclContexts ? something like:

Decls can nest under non-DeclContext nodes, in cases like initializer, where they might be attributed to VarDecl.
Preserving that level of granularity is especially useful for initializers at top-level, as otherwise the only context we
can attach these refs is TranslationUnitDecl, which we don't preserve in the index.
FIXME: Maybe we should have some symbols for representing file-scopes, that way we can show these refs as
being contained in the file-scope.

(Last fixme bit is optional, please add that if you also think the functionality would be more useful that way)

506–507

I assume you mean ASTNode.ContainerDC.

yes, sorry for the mess.

So, I don't think this suggestion will work without making the Ref::Container field significantly less specific (and thereby the call hierarchy feature less useful in some cases).

I can't seem to remember why we went with it in the first place. But now:

int foo();
int x = foo();
void bar() {
  int y = foo();
}

calling call hierarchy on foo will yield x and bar, creating some sort of discrepancy. I am not really sure if telling first call to foo is contained in x is really useful compared to saying it was contained in filename.cpp (but ofc we can't do that today as container needs to be a symbol in the index, hence the ref will be lost instead). do you also think that would be more useful (i am not really a user of this feature so I would like to hear which is better from some users)?

also I can't say that I find the discrepancy between an initializer in parmvardecl/nontypetemplateparm vs vardecl useful (i know it already exists today, but not really sure why).
they are actually attached to the first declcontext containing them, not the first decl (which you say is more useful, let's leave the fact that they are not indexed out for a while).
moreover it is a behavior we rely on through libindex, as it just marks ASTNode.Parent with declcontext rather than making use of the vardecl. which makes me believe it is not really important to have the top-level symbol as the container. But it is the only way we can retain some container information.
if that's the case, I believe we should make this more explicit, i.e. start a traversal from the node itself, remember the last indexed decl we've seen as a parent and return that if we failed to find any indexed declcontext's containing the decl (with a fixme saying that we could have some file symbols in the index for translationunitdecls).
That way we can say that the container is the first DeclContext containing the reference (with the exception of fixme mentioned).

[nridge]

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

506–507

I am not really sure if telling first call to foo is contained in x is really useful compared to saying it was contained in filename.cpp [...] do you also think that would be more useful (i am not really a user of this feature so I would like to hear which is better from some users)?

In my opinion, in cases where a reference to a function occurs in the initializer (or otherwise in the declaration, such as perhaps in the type) of a namespace-scope variable, it is significantly more useful to show the name of that variable in the call hierarchy, than the name of the containing file.

Consider an example like this:

void FlushAndClearCaches();
...
// elsewhere, at namespace scope:
std::function<void()> OnMemoryPressureCallback = &FlushAndClearCaches;

If I invoke call hierarchy on FlushAndClearCaches (or one of its callees), and I'm looking at the children of the FlushAndClearCaches node in the call hierarchy tree, it is much more informative if the name of the relevant child item is OnMemoryPressureCallback, than if it is a file name. If it's a file name, I need to take the extra step of clicking on the item to navigate to the target file and the reference location inside it, and look there, whereas if it's a variable name I may have all the information I need just from the call hierarchy view.

I think being able to eyeball the call hierarchy view and get and idea of what sorts of functionality calls into a function, without having to click on each item and examine the context, is an important use case.

(It's fair to ask if this logic also applies to local variables. I would say no: local variables are more likely to be implementation details with un-interesting names. The name of the containing function is typically the more interesting part, and is still more granular than a file.)

I appreciate that on a technical level, this is an inconsistency between local variables vs. namespace-scope variables. However, from the point of view of a user of call hierarchy, I think this combination gives the best results.

I am also open to revising what we store in Ref::Container if additional consumers (other than call hierarchy) come up, but for now I think it makes sense to let it be guided by what it useful for call hierarchy. (I surveyed the Eclipse CDT codebase, where the corresponding piece of information in the index has one other consumer besides call hierarchy: it's used to annotate entries in the find-references view with the name of the calling function (https://github.com/clangd/clangd/issues/177). Were we to add this feature, I think we'd want to keep the same treatment of variables as for call hierarchy, for similar reasons.)

[nridge]

Address review comments

[nridge]

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

159

I've added a comment to explain why we're not using`DeclContext` here.

I'm not sure if your other comment is still relevant, if we agree that the current behaviour is the desirable one.

[kadircet]

thanks, lgtm!
sorry for the late reply :( adding a couple nits.

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

170

not need for _or_null as loop condition ensures Enclosing != nullptr

nit: const auto *ND

173

nit: I'd just break here and return Enclosing outside.

506–507

(It's fair to ask if this logic also applies to local variables. I would say no: local variables are more likely to be implementation details with un-interesting names. The name of the containing function is typically the more interesting part, and is still more granular than a file.)

Right, I was mostly saying that if we want this behaviour at one place, why we don't want it at the other. I'd claim that top-level function declaration is also going to be an implementation detail most of the time.

I appreciate that on a technical level, this is an inconsistency between local variables vs. namespace-scope variables. However, from the point of view of a user of call hierarchy, I think this combination gives the best results.

SG. I suppose we can revisit the decision in the future if need be and store the vardecl if need be and make callhiearachy iterate over the parents instead.

[nridge]

Address review comments

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

 llvm::Optional<RelationKind> indexableRelation(const index::SymbolRelation &R) {
   if (R.Roles & static_cast<unsigned>(index::SymbolRole::RelationBaseOf))
     return RelationKind::BaseOf;
   if (R.Roles & static_cast<unsigned>(index::SymbolRole::RelationOverrideOf))
     return RelationKind::OverriddenBy;
   return None;
 }
 
+// Given a ref contained in enclosing decl `Enclosing`, return
+// the decl that should be used as that ref's Ref::Container. This is
+// usually `Enclosing` itself, but in cases where `Enclosing` is not
+// indexed, we walk further up because Ref::Container should always be
+// an indexed symbol.
+// Note: we don't use DeclContext as the container as in some cases
+// it's useful to use a Decl which is not a DeclContext. For example,
+// for a ref occurring in the initializer of a namespace-scope variable,
+// it's useful to use that variable as the container, as otherwise the
+// next enclosing DeclContext would be a NamespaceDecl or TranslationUnitDecl,
+// which are both not indexed and less granular than we'd like for use cases
+// like call hierarchy.
+const Decl *getRefContainer(const Decl *Enclosing,
+                            const SymbolCollector::Options &Opts) {
+  while (Enclosing) {
+    const auto *ND = dyn_cast<NamedDecl>(Enclosing);
+    if (ND && SymbolCollector::shouldCollectSymbol(*ND, ND->getASTContext(),
+                                                   Opts, true)) {
+      break;
+    }
+    Enclosing = dyn_cast_or_null<Decl>(Enclosing->getDeclContext());
+  }
+  return Enclosing;
+}
+
 } // namespace
 
 // Encapsulates decisions about how to record header paths in the index,
 // including filename normalization, URI conversion etc.
 // Expensive checks are cached internally.
 class SymbolCollector::HeaderFileURICache {
   // Weird double-indirect access to PP, which might not be ready yet when
   // HeaderFiles is created but will be by the time it's used.
void SymbolCollector::initialize(ASTContext &Ctx) {
   ASTCtx = &Ctx;
   HeaderFileURIs = std::make_unique<HeaderFileURICache>(
       PP, ASTCtx->getSourceManager(), Opts);
   CompletionAllocator = std::make_shared<GlobalCodeCompletionAllocator>();
   CompletionTUInfo =
       std::make_unique<CodeCompletionTUInfo>(CompletionAllocator);
 }
 
 bool SymbolCollector::shouldCollectSymbol(const NamedDecl &ND,
                                           const ASTContext &ASTCtx,
                                           const Options &Opts,
                                           bool IsMainFileOnly) {
   // Skip anonymous declarations, e.g (anonymous enum/class/struct).
   if (ND.getDeclName().isEmpty())
     return false;
 
   // Skip main-file symbols if we are not collecting them.
   if (IsMainFileOnly && !Opts.CollectMainFileSymbols)
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].push_back(
-        SymbolRef{SM.getFileLoc(Loc), Roles, ASTNode.Parent});
+    DeclRefs[ND].push_back(SymbolRef{SM.getFileLoc(Loc), Roles,
+                                     getRefContainer(ASTNode.Parent, Opts)});
   // 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);

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

 #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 {
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &Stream,
+                              const CallHierarchyItem &Item) {
+  return Stream << Item.name << "@" << Item.selectionRange;
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &Stream,
+                              const CallHierarchyIncomingCall &Call) {
+  Stream << "{ from: " << Call.from << ", ranges: [";
+  for (const auto &R : Call.fromRanges) {
+    Stream << R;
+    Stream << ", ";
+  }
+  return Stream << "] }";
+}
+
 namespace {
 
 using ::testing::AllOf;
 using ::testing::ElementsAre;
 using ::testing::Field;
 using ::testing::IsEmpty;
 using ::testing::Matcher;
 using ::testing::UnorderedElementsAre;
TEST(CallHierarchy, IncomingMultiFile) {
   CheckCallHierarchy(*AST, CalleeH.point(), testPath("callee.hh"));
 
   // Check that invoking from the definition site works.
   AST = Workspace.openFile("callee.cc");
   ASSERT_TRUE(bool(AST));
   CheckCallHierarchy(*AST, CalleeC.point(), testPath("callee.cc"));
 }
 
+TEST(CallHierarchy, CallInLocalVarDecl) {
+  // Tests that local variable declarations are not treated as callers
+  // (they're not indexed, so they can't be represented as call hierarchy
+  // items); instead, the caller should be the containing function.
+  // However, namespace-scope variable declarations should be treated as
+  // callers because those are indexed and there is no enclosing entity
+  // that would be a useful caller.
+  Annotations Source(R"cpp(
+    int call^ee();
+    void caller1() {
+      $call1[[callee]]();
+    }
+    void caller2() {
+      int localVar = $call2[[callee]]();
+    }
+    int caller3 = $call3[[callee]]();
+  )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 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")))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

TEST_F(SymbolCollectorTest, RefContainers) {
   };
   auto Container = [&](llvm::StringRef RangeName) {
     auto Ref = FindRefWithRange(Code.range(RangeName));
     EXPECT_TRUE(bool(Ref));
     return Ref->Container;
   };
   EXPECT_EQ(Container("ref1a"),
             findSymbol(Symbols, "f2").ID); // function body (call)
-  // FIXME: This is wrongly contained by fptr and not f2.
-  EXPECT_NE(Container("ref1b"),
+  EXPECT_EQ(Container("ref1b"),
             findSymbol(Symbols, "f2").ID); // function body (address-of)
   EXPECT_EQ(Container("ref2"),
             findSymbol(Symbols, "v1").ID); // variable initializer
   EXPECT_EQ(Container("ref3"),
             findSymbol(Symbols, "f3").ID); // function parameter default value
   EXPECT_EQ(Container("ref4"),
             findSymbol(Symbols, "S1::member1").ID); // member initializer
   EXPECT_EQ(Container("ref5"),