[clangd] Store the containing symbol for refs

[nridge]

Summary

This is needed to implement call hierarchy.

[kadircet]

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

349

What does ASTNode.Parent correspond to in here? I couldn't find any clarifications on libIndex side, are we sure that's always what we want? It would be nice to have some tests demonstrating what this corresponds to in a variety of cases.

Also why do we only store NamedDecls as containers? It makes sense from CallHierarchy perspective as we are only interested in function-like containers, and they are nameddecls (?). But these might as well be TranslationUnitDecl (?) for top level declarations,

[nridge]

Use Decl rather than NamedDecl, and add a test

[nridge]

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

349

I wrote a test with various cases I could think of, and the choice of decl coming from ASTNode.Parent seems reasonable to me.

[kadircet]

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

91

i am afraid we are going to have an indeterminate value here if for whatever reason Container detection fails. (e.g. for macros, or if ASTNode.Parent set to nullptr by libindex).

Sent out https://reviews.llvm.org/D90397 to address the issue.

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

779

can we also have an assertion checking containers for top level symbols are the same ?

and extend the test to have multiple declarations inside:

• a namespace
• inside a record (like S1)

and ensure the container is same for those (and different than top-level symbols themselves). It is okay for those symbols.

Note that it is OK for namespaces to be not in the index, i just want to make sure the containers for the top-level symbols inside a namespace are the same.

[nridge]

Address review comments

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

91

Good catch, and thank you for addressing this!

[kadircet]

thanks, LGTM!

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

782

can you also assert containers here are non-null (and below)

803

nit: i would suggest writing these in the form of:

auto Container = [](StringRef RangeName){
  auto Ref = findRefWithRange(RangeName;
  ASSERT_TRUE(Ref);
  ASSERT_FALSE(Ref->Container.isNull());
  return Ref->Container;
};
EXPECT_EQ(Container("sym1"), Container("sym2"));
EXPECT_NE(Container("sym1"), Container("sym2"));

then you could update the ones above as:

EXPECT_EQ(Container("rangename"), findSymbol(Symbols, "symname"));

[nridge]

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

782

It looks like the container is null for toplevel decls. Is that a problem?

[nridge]

Address review comments

[nridge]

(I will wait for a response about the containers for top-level decls before committing.)

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

803

Revised as suggested, except for allowing a null container for top-level decls.

[kadircet]

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

770

nit: instead of making this part of the lambda and complicating the signature I would just check this holds for classscope1 and namespacescope1 explicitly. it should be true for other cases anyways, as we are checking equality with non-null smybolids.

782

I think that's OK for now, might be worth leaving a comment tho. (at Ref::Container)

[nridge]

Address final review comments

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 Container;
 };
 
 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.Container) <
+         std::tie(R.Location, R.Kind, R.Container);
 }
 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.Container) ==
+         std::tie(R.Location, R.Kind, R.Container);
 }
 
 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.Container.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.Container = 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 Decl *Container;
+  };
   // 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, 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);
   if (!OriginalDecl)
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 container information for macro references.
+    MacroRefs[ID].push_back({Loc, Roles, /*Container=*/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);
+      R.Container = getSymbolID(LocAndRole.Container);
   // 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/unittests/SymbolCollectorTests.cpp

 MATCHER(IncludeHeader, "") { return !arg.IncludeHeaders.empty(); }
 MATCHER_P(IncludeHeader, P, "") {
   return (arg.IncludeHeaders.size() == 1) &&
          (arg.IncludeHeaders.begin()->IncludeHeader == P);
 }
 MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References, "") {
   return (arg.IncludeHeader == IncludeHeader) && (arg.References == References);
 }
+bool rangesMatch(const SymbolLocation &Loc, const Range &R) {
+  return std::make_tuple(Loc.Start.line(), Loc.Start.column(), Loc.End.line(),
+                         Loc.End.column()) ==
+         std::make_tuple(R.start.line, R.start.character, R.end.line,
+                         R.end.character);
+}
 MATCHER_P(DeclRange, Pos, "") {
-  return std::make_tuple(arg.CanonicalDeclaration.Start.line(),
-                         arg.CanonicalDeclaration.Start.column(),
-                         arg.CanonicalDeclaration.End.line(),
-                         arg.CanonicalDeclaration.End.column()) ==
-         std::make_tuple(Pos.start.line, Pos.start.character, Pos.end.line,
-                         Pos.end.character);
-}
-MATCHER_P(DefRange, Pos, "") {
-  return std::make_tuple(
-             arg.Definition.Start.line(), arg.Definition.Start.column(),
-             arg.Definition.End.line(), arg.Definition.End.column()) ==
-         std::make_tuple(Pos.start.line, Pos.start.character, Pos.end.line,
-                         Pos.end.character);
+  return rangesMatch(arg.CanonicalDeclaration, Pos);
 }
+MATCHER_P(DefRange, Pos, "") { return rangesMatch(arg.Definition, Pos); }
 MATCHER_P(RefCount, R, "") { return int(arg.References) == R; }
 MATCHER_P(ForCodeCompletion, IsIndexedForCodeCompletion, "") {
   return static_cast<bool>(arg.Flags & Symbol::IndexedForCodeCompletion) ==
          IsIndexedForCodeCompletion;
 }
 MATCHER(Deprecated, "") { return arg.Flags & Symbol::Deprecated; }
 MATCHER(ImplementationDetail, "") {
   return arg.Flags & Symbol::ImplementationDetail;
 }
 MATCHER(VisibleOutsideFile, "") {
   return static_cast<bool>(arg.Flags & Symbol::VisibleOutsideFile);
 }
 MATCHER(RefRange, "") {
   const Ref &Pos = ::testing::get<0>(arg);
   const Range &Range = ::testing::get<1>(arg);
-  return std::make_tuple(Pos.Location.Start.line(), Pos.Location.Start.column(),
-                         Pos.Location.End.line(), Pos.Location.End.column()) ==
-         std::make_tuple(Range.start.line, Range.start.character,
-                         Range.end.line, Range.end.character);
+  return rangesMatch(Pos.Location, Range);
 }
 ::testing::Matcher<const std::vector<Ref> &>
 HaveRanges(const std::vector<Range> Ranges) {
   return ::testing::UnorderedPointwise(RefRange(), Ranges);
 }
 
 class ShouldCollectSymbolTest : public ::testing::Test {
 public:
runSymbolCollector(Header.code(),
                      (Main.code() + SymbolsOnlyInMainCode.code()).str());
   EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "a").ID, _)));
   EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "b").ID, _)));
   EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "c").ID, _)));
   // However, references to main-file macros are not collected.
   EXPECT_THAT(Refs, Not(Contains(Pair(findSymbol(Symbols, "FUNC").ID, _))));
 }
 
+TEST_F(SymbolCollectorTest, RefContainers) {
+  Annotations Code(R"cpp(
+    int $toplevel1[[f1]](int);
+    void f2() {
+      (void) $ref1a[[f1]](1);
+      auto fptr = &$ref1b[[f1]];
+    }
+    int $toplevel2[[v1]] = $ref2[[f1]](2);
+    void f3(int arg = $ref3[[f1]](3));
+    struct S1 {
+      int $classscope1[[member1]] = $ref4[[f1]](4);
+      int $classscope2[[member2]] = 42;
+    };
+    constexpr int f4(int x) { return x + 1; }
+    template <int I = $ref5[[f4]](0)> struct S2 {};
+    S2<$ref6[[f4]](0)> v2;
+    S2<$ref7a[[f4]](0)> f5(S2<$ref7b[[f4]](0)>);
+    namespace N {
+      void $namespacescope1[[f6]]();
+      int $namespacescope2[[v3]];
+    }
+  )cpp");
+  CollectorOpts.RefFilter = RefKind::All;
+  CollectorOpts.CollectMainFileRefs = true;
+  runSymbolCollector("", Code.code());
+  auto FindRefWithRange = [&](Range R) -> Optional<Ref> {
+    for (auto &Entry : Refs) {
+      for (auto &Ref : Entry.second) {
+        if (rangesMatch(Ref.Location, R))
+          return Ref;
+      }
+    }
+    return llvm::None;
+  };
+  auto Container = [&](llvm::StringRef RangeName, bool AllowNull = false) {
+    auto Ref = FindRefWithRange(Code.range(RangeName));
+    EXPECT_TRUE(bool(Ref));
+    if (!AllowNull)
+      EXPECT_FALSE(Ref->Container.isNull());
+    return Ref->Container;
+  };
+  EXPECT_EQ(Container("ref1a"),
+            findSymbol(Symbols, "f2").ID); // function body (call)
+  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"),
+            findSymbol(Symbols, "S2").ID); // template parameter default value
+  EXPECT_EQ(Container("ref6"),
+            findSymbol(Symbols, "v2").ID); // type of variable
+  EXPECT_EQ(Container("ref7a"),
+            findSymbol(Symbols, "f5").ID); // return type of function
+  EXPECT_EQ(Container("ref7b"),
+            findSymbol(Symbols, "f5").ID); // parameter type of function
+
+  EXPECT_EQ(Container("toplevel1", /*AllowNull=*/true),
+            Container("toplevel2", /*AllowNull=*/true));
+  EXPECT_EQ(Container("classscope1"), Container("classscope2"));
+  EXPECT_EQ(Container("namespacescope1"), Container("namespacescope2"));
+
+  EXPECT_NE(Container("toplevel1", /*AllowNull=*/true),
+            Container("namespacescope1"));
+  EXPECT_NE(Container("toplevel1", /*AllowNull=*/true),
+            Container("classscope1"));
+  EXPECT_NE(Container("classscope1"), Container("namespacescope1"));
+}
+
 TEST_F(SymbolCollectorTest, MacroRefInHeader) {
   Annotations Header(R"(
   #define $foo[[FOO]](X) (X + 1)
   #define $bar[[BAR]](X) (X + 2)
 
   // Macro defined multiple times.
   #define $ud1[[UD]] 1
   int ud_1 = $ud1[[UD]];