[clangd] Store explicit template specializations in index for code navigation purposes

[kadircet]

Summary

This introduces ~4k new symbols, and ~10k refs for LLVM. We need that
information for providing better code navigation support:

• When references for a class template is requested, we should return these specializations as well.
• When children of a specialization is requested, we should be able to query for those symbols(instead of just class template)

Number of symbols: 378574 -> 382784
Number of refs: 5098857 -> 5110689

[gribozavr]

clangd/CodeComplete.cpp

1513

isExplicitTemplateSpecialization?

unittests/clangd/SymbolCollectorTests.cpp

395–401

"Template" -> "Primary template"

"is indexed" -> "are indexed"

[ioeric]

We need that information for providing better code navigation support, like find references, children/base classes etc.

It's not trivial how they make code navigation better. Can you explain and provide examples in the summary? Thanks!

clangd/CodeComplete.cpp

1613

nit: the context here is code completion. Maybe explain why they are not interesting for completion rather than why we index them?

[kadircet]

• Address comments

[gribozavr]

clangd/CodeComplete.cpp

1613

which is the same as the name of the *primary* template in case of template specializations.

[nridge]

Is any representation of the template arguments stored in the index?

[kadircet]

In D59083#1424509, @nridge wrote:

Is any representation of the template arguments stored in the index?

No we only have, class name if you want to do a "name based" search/lookup. But symbol IDs for template specializations are different, so you can query them by ID.
Do you have any use case that needs names?

[nridge]

One of the use cases I imagined for this (unrelated to D58880) is that if the user searches for vector (using workspace/symbols), they get a separate search result for the vector primary template, and a separate one for vector<bool>. For this to be useful, the server needs to print the <bool> as part of the search result.

(For D58880, I would find it useful for be able to look up an explicit spec. by template-id in the tests, but that can probably be worked around.)

[ilya-biryukov]

To split this into multiple independent changes, we could start with storing the symbols for template specializations, but only showing the primary template in the results of workspaceSymbols.
This would enable other features (xrefs, etc), and we could re-add specializations to workspaceSymbols after we improve the presentation.

[kadircet]

• Agree on ilya-biryukov@'s suggestion, changing fuzzyfind to skip template (partial) specializations for now.

[kadircet]

In D59083#1426105, @ilya-biryukov wrote:

To split this into multiple independent changes, we could start with storing the symbols for template specializations, but only showing the primary template in the results of workspaceSymbols.
This would enable other features (xrefs, etc), and we could re-add specializations to workspaceSymbols after we improve the presentation.

SGTM, moving forward with that approach.

clangd/CodeComplete.cpp

for (const auto &Item : Bundle) {
                         Recorder->CCContext.getKind(), Opts);
       else
         Builder->add(Item, SemaCCS);
     }
     return Builder->build();
   }
 };
 
+template <class T> bool isExplicitTemplateSpecialization(const NamedDecl &ND) {
+  if (const auto *TD = dyn_cast<T>(&ND))
+    if (TD->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
+      return true;
+  return false;
+}
+
 } // namespace
 
 clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
   clang::CodeCompleteOptions Result;
   Result.IncludeCodePatterns = EnableSnippets && IncludeCodePatterns;
   Result.IncludeMacros = IncludeMacros;
   Result.IncludeGlobals = true;
   // We choose to include full comments and not do doxygen parsing in
auto InTopLevelScope = [](const NamedDecl &ND) {
     case Decl::Namespace:
     case Decl::LinkageSpec:
       return true;
     default:
       break;
     };
     return false;
   };
+  // We only complete symbol's name, which is the same as the name of the
+  // *primary* template in case of template specializations.
+  if (isExplicitTemplateSpecialization<FunctionDecl>(ND) ||
+      isExplicitTemplateSpecialization<CXXRecordDecl>(ND) ||
+      isExplicitTemplateSpecialization<VarDecl>(ND))
+    return false;
+
   if (InTopLevelScope(ND))
     return true;
 
   if (const auto *EnumDecl = dyn_cast<clang::EnumDecl>(ND.getDeclContext()))
     return InTopLevelScope(*EnumDecl) && !EnumDecl->isScoped();
 
   return false;
 }

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 "Logger.h"
 #include "Quality.h"
 #include "Trace.h"
+#include "clang/Index/IndexSymbol.h"
 
 namespace clang {
 namespace clangd {
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) {
   // Store Slab size before it is moved.
   const auto BackingDataSize = Slab.bytes() + Refs.bytes();
   auto Data = std::make_pair(std::move(Slab), std::move(Refs));
bool MemIndex::fuzzyFind(
 
   TopN<std::pair<float, const Symbol *>> Top(
       Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
   for (const auto Pair : Index) {
     const Symbol *Sym = Pair.second;
 
+    // FIXME: Enable fuzzy find on template specializations once we start
+    // storing template arguments in the name. Currently we only store name for
+    // class template, which would cause duplication in the results.
+    if (Sym->SymInfo.Properties &
+        (static_cast<index::SymbolPropertySet>(
+             index::SymbolProperty::TemplateSpecialization) |
+         static_cast<index::SymbolPropertySet>(
+             index::SymbolProperty::TemplatePartialSpecialization)))
+      continue;
     // Exact match against all possible scopes.
     if (!Req.AnyScope && !llvm::is_contained(Req.Scopes, Sym->Scope))
       continue;
     if (Req.RestrictForCodeCompletion &&
         !(Sym->Flags & Symbol::IndexedForCodeCompletion))
       continue;
 
     if (auto Score = Filter.match(Sym->Name))

clangd/index/SymbolCollector.cpp

return (Roles & static_cast<unsigned>(index::SymbolRole::Definition)) &&
          isa<TagDecl>(&ND) &&
          !SM.isWrittenInMainFile(SM.getExpansionLoc(ND.getLocation()));
 }
 
 RefKind toRefKind(index::SymbolRoleSet Roles) {
   return static_cast<RefKind>(static_cast<unsigned>(RefKind::All) & Roles);
 }
 
-template <class T> bool explicitTemplateSpecialization(const NamedDecl &ND) {
-  if (const auto *TD = dyn_cast<T>(&ND))
-    if (TD->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
-      return true;
-  return false;
-}
-
 } // namespace
 
 SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {}
 
 void SymbolCollector::initialize(ASTContext &Ctx) {
   ASTCtx = &Ctx;
   CompletionAllocator = std::make_shared<GlobalCodeCompletionAllocator>();
   CompletionTUInfo =
bool SymbolCollector::shouldCollectSymbol(const NamedDecl &ND,
   case Decl::ObjCImplementation:
     break;
   default:
     // Record has a few derivations (e.g. CXXRecord, Class specialization), it's
     // easier to cast.
     if (!isa<RecordDecl>(DeclCtx))
       return false;
   }
-  if (explicitTemplateSpecialization<FunctionDecl>(ND) ||
-      explicitTemplateSpecialization<CXXRecordDecl>(ND) ||
-      explicitTemplateSpecialization<VarDecl>(ND))
-    return false;
 
   // Avoid indexing internal symbols in protobuf generated headers.
   if (isPrivateProtoDecl(ND))
     return false;
   return true;
 }
 
 // Always return true to continue indexing.

clangd/index/dex/Dex.cpp

for (size_t I = 0; I < ScoredSymbols.size(); ++I) {
     SymbolQuality[I] = ScoredSymbols[I].first;
     Symbols[I] = ScoredSymbols[I].second;
   }
 
   // Populate TempInvertedIndex with lists for index symbols.
   llvm::DenseMap<Token, std::vector<DocID>> TempInvertedIndex;
   for (DocID SymbolRank = 0; SymbolRank < Symbols.size(); ++SymbolRank) {
     const auto *Sym = Symbols[SymbolRank];
+    // FIXME: Enable fuzzy find on template specializations once we start
+    // storing template arguments in the name. Currently we only store name for
+    // class template, which would cause duplication in the results.
+    if (Sym->SymInfo.Properties &
+        (static_cast<index::SymbolPropertySet>(
+             index::SymbolProperty::TemplateSpecialization) |
+         static_cast<index::SymbolPropertySet>(
+             index::SymbolProperty::TemplatePartialSpecialization)))
+      continue;
     for (const auto &Token : generateSearchTokens(*Sym))
       TempInvertedIndex[Token].push_back(SymbolRank);
   }
 
   // Convert lists of items to posting lists.
   for (const auto &TokenToPostingList : TempInvertedIndex)
     InvertedIndex.insert(
         {TokenToPostingList.first, PostingList(TokenToPostingList.second)});

unittests/clangd/DexTests.cpp

TEST(DexTest, PreferredTypesBoosting) {
 
   Req.PreferredTypes = {Sym1.Type};
   EXPECT_THAT(match(I, Req), ElementsAre("t1"));
 
   Req.PreferredTypes = {Sym2.Type};
   EXPECT_THAT(match(I, Req), ElementsAre("t2"));
 }
 
+TEST(DexTest, TemplateSpecialization) {
+  SymbolSlab::Builder B;
+
+  Symbol S = symbol("TempSpec");
+  S.ID = SymbolID("0");
+  B.insert(S);
+
+  S = symbol("TempSpec");
+  S.ID = SymbolID("1");
+  S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
+      index::SymbolProperty::TemplateSpecialization);
+  B.insert(S);
+
+  S = symbol("TempSpec");
+  S.ID = SymbolID("2");
+  S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
+      index::SymbolProperty::TemplatePartialSpecialization);
+  B.insert(S);
+
+  auto I = dex::Dex::build(std::move(B).build(), RefSlab());
+  FuzzyFindRequest Req;
+  Req.Query = "TempSpec";
+  Req.AnyScope = true;
+
+  std::vector<Symbol> Symbols;
+  I->fuzzyFind(Req, [&Symbols](const Symbol &Sym) { Symbols.push_back(Sym); });
+  EXPECT_EQ(Symbols.size(), 1U);
+  EXPECT_FALSE(Symbols.front().SymInfo.Properties &
+               static_cast<index::SymbolPropertySet>(
+                   index::SymbolProperty::TemplateSpecialization));
+  EXPECT_FALSE(Symbols.front().SymInfo.Properties &
+               static_cast<index::SymbolPropertySet>(
+                   index::SymbolProperty::TemplatePartialSpecialization));
+}
+
 } // namespace
 } // namespace dex
 } // namespace clangd
 } // namespace clang

unittests/clangd/IndexTests.cpp

 //===-- IndexTests.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 "TestIndex.h"
 #include "TestTU.h"
 #include "index/FileIndex.h"
 #include "index/Index.h"
 #include "index/MemIndex.h"
 #include "index/Merge.h"
+#include "index/Symbol.h"
+#include "clang/Index/IndexSymbol.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::_;
 using testing::AllOf;
 using testing::AnyOf;
 using testing::ElementsAre;
 using testing::Pair;
TEST(MemIndexTest, Lookup) {
   EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc"));
   EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
               UnorderedElementsAre("ns::abc", "ns::xyz"));
   EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}),
               UnorderedElementsAre("ns::xyz"));
   EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre());
 }
 
+TEST(MemIndexTest, TemplateSpecialization) {
+  SymbolSlab::Builder B;
+
+  Symbol S = symbol("TempSpec");
+  S.ID = SymbolID("0");
+  B.insert(S);
+
+  S = symbol("TempSpec");
+  S.ID = SymbolID("1");
+  S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
+      index::SymbolProperty::TemplateSpecialization);
+  B.insert(S);
+
+  S = symbol("TempSpec");
+  S.ID = SymbolID("2");
+  S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
+      index::SymbolProperty::TemplatePartialSpecialization);
+  B.insert(S);
+
+  auto I = MemIndex::build(std::move(B).build(), RefSlab());
+  FuzzyFindRequest Req;
+  Req.Query = "TempSpec";
+  Req.AnyScope = true;
+
+  std::vector<Symbol> Symbols;
+  I->fuzzyFind(Req, [&Symbols](const Symbol &Sym) { Symbols.push_back(Sym); });
+  EXPECT_EQ(Symbols.size(), 1U);
+  EXPECT_FALSE(Symbols.front().SymInfo.Properties &
+               static_cast<index::SymbolPropertySet>(
+                   index::SymbolProperty::TemplateSpecialization));
+  EXPECT_FALSE(Symbols.front().SymInfo.Properties &
+               static_cast<index::SymbolPropertySet>(
+                   index::SymbolProperty::TemplatePartialSpecialization));
+}
+
 TEST(MergeIndexTest, Lookup) {
   auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()),
        J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab());
   MergedIndex M(I.get(), J.get());
   EXPECT_THAT(lookup(M, SymbolID("ns::A")), UnorderedElementsAre("ns::A"));
   EXPECT_THAT(lookup(M, SymbolID("ns::B")), UnorderedElementsAre("ns::B"));
   EXPECT_THAT(lookup(M, SymbolID("ns::C")), UnorderedElementsAre("ns::C"));
   EXPECT_THAT(lookup(M, {SymbolID("ns::A"), SymbolID("ns::B")}),

unittests/clangd/SymbolCollectorTests.cpp

EXPECT_THAT(Symbols,
                   AllOf(QName("B"), Not(VisibleOutsideFile())),
                   AllOf(QName("c"), Not(VisibleOutsideFile())),
                   // FIXME: ForwardDecl likely *is* visible outside.
                   AllOf(QName("ForwardDecl"), Not(VisibleOutsideFile()))));
 }
 
 TEST_F(SymbolCollectorTest, Template) {
   Annotations Header(R"(
-    // Template is indexed, specialization and instantiation is not.
-    template <class T> struct [[Tmpl]] {T $xdecl[[x]] = 0;};
-    template <> struct Tmpl<int> {};
-    extern template struct Tmpl<float>;
-    template struct Tmpl<double>;
+    // Primary template and explicit specialization are indexed, instantiation
+    // is not.
+    template <class T, class U> struct [[Tmpl]] {T $xdecl[[x]] = 0;};
+    template <> struct $specdecl[[Tmpl]]<int, bool> {};
+    template <class U> struct $partspecdecl[[Tmpl]]<bool, U> {};
+    extern template struct Tmpl<float, bool>;
+    template struct Tmpl<double, bool>;
   )");
   runSymbolCollector(Header.code(), /*Main=*/"");
   EXPECT_THAT(Symbols,
-              UnorderedElementsAreArray(
-                  {AllOf(QName("Tmpl"), DeclRange(Header.range())),
-                   AllOf(QName("Tmpl::x"), DeclRange(Header.range("xdecl")))}));
+              UnorderedElementsAre(
+                  AllOf(QName("Tmpl"), DeclRange(Header.range()),
+                        ForCodeCompletion(true)),
+                  AllOf(QName("Tmpl"), DeclRange(Header.range("specdecl")),
+                        ForCodeCompletion(false)),
+                  AllOf(QName("Tmpl"), DeclRange(Header.range("partspecdecl")),
+                        ForCodeCompletion(false)),
+                  AllOf(QName("Tmpl::x"), DeclRange(Header.range("xdecl")),
+                        ForCodeCompletion(false))));
 }
 
 TEST_F(SymbolCollectorTest, ObjCSymbols) {
   const std::string Header = R"(
     @interface Person
     - (void)someMethodName:(void*)name1 lastName:(void*)lName;
     @end