[clangd] Count number of references while merging RefSlabs inside FileIndex

[kadircet]

Summary

For counting number of references clangd was relying on merging every
duplication of a symbol. Unfortunately this does not apply to FileIndex(and one
of its users' BackgroundIndex), since we get rid of duplication by simply
dropping symbols coming from non-canonical locations. So only one or two(coming
from canonical declaration header and defined source file, if exists)
replications of the same symbol reaches merging step.

This patch changes reference counting logic to rather count number of different
RefSlabs a given SymbolID exists.

[ioeric]

I'm not sure if FileIndex is the correct layer to make decision about how References is calculated. Currently, we have two use cases in clangd 1) one slab per TU and 2) one slab per file. It seems to me that we would want different strategies for the two use cases, so it might make sense to make this configurable in FileIndex. And in one case, we have References ~= # of TUs, and in the other case, we would have References ~= # of files. This can over-count References in the second case. It might be fine as an approximation (if there is no better solution), but we should definitely document it (e.g. in BackgroundIndex).

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

50

this is a bit of a code smell. FileIndex is not supposed to know anything about clangd-indexer etc.

175

note that references might not always exist. SymbolCollector can be set up to not collect references.

[kadircet]

In D59481#1432881, @ioeric wrote:

I'm not sure if FileIndex is the correct layer to make decision about how References is calculated. Currently, we have two use cases in clangd 1) one slab per TU and 2) one slab per file. It seems to me that we would want different strategies for the two use cases, so it might make sense to make this configurable in FileIndex. And in one case, we have References ~= # of TUs, and in the other case, we would have References ~= # of files.

References ~= # of TUs case has nothing to do with FileIndex actually, it only happens if references are counted beforehand(which is currently only happening in clangd-indexer).
FileIndex has two ways to handle duplicates during an index merge:

• pickone which doesn't count references at all (this is the oneslab per TU case)
• merge which counts references as number of files this symbol has occured (this is the oneslab per File case)

This can over-count References in the second case. It might be fine as an approximation (if there is no better solution), but we should definitely document it (e.g. in BackgroundIndex).

I don't follow why this can over-count, FileIndex keeps only one RefSlab per each file, so we can't over-count? Did you mean it will be more than #TUs ?

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

50

I've actually just left the comment for review so that we can decide what to do about discrepancy(with my reasoning). It is not like FileIndex is somehow tied to clangd-indexer now?

175

I thought we wouldn't make any promises about References in such a case, do we?

[ioeric]

I don't follow why this can over-count, FileIndex keeps only one RefSlab per each file, so we can't over-count? Did you mean it will be more than #TUs ?

Yes. This is how Symbol::References is described in its documentation. If we want to change/expand the semantic, we need to make it clear in the documentation as well.

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

175

Is this documented somewhere?

References and RefSlab have been two independent things. References existed before RefSlab. Now might be a good time to unify them, but I think we should think about how this is reflected in their definitions (documentation etc) and other producers and consumers of the structures.

[kadircet]

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

175

Both of them are only produced by SymbolCollector, which has an option CountReferences with a comment saying // Populate the Symbol.References field..
Unfortunately that's not what it does, instead it always sets Symol.References field to 1 for every symbol collected during indexing of a single TU.
Then it is up to the consumers to merge those 1s. So even though we say:

/// The number of translation units that reference this symbol from their main
/// file. This number is only meaningful if aggregated in an index.

in the comments of Symbol::References it is totally up-to-the consumer who performs the merging.

The option controls whether Symbol Occurences should be collected or not.

I see two possible options:

• Un-tie SymbolCollector from Symbol::References and rather define it as:

/// This field is for the convenience of an aggregated symbol index

• Rather change Index structure's(consumers of this information) to store(and build) this information internally if they plan to make use of it ?

WDYT?

[ioeric]

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

33

nit: s/every file/every slab/?

There is no "file" in this context.

46

I think we can trigger this assertion with an incomplete background index. For example, we've seen references of a symbol in some files but we've not parsed the file that contains the decls.

50

the comment is useful. I just think it's in the wrong place. If we define the reference counting behavior for FileSymbols, FileSymbolswouldn't need to know about clangd-indexer or background-index. This comment can then live in background index instead.

175

Unfortunately that's not what it does, instead it always sets Symol.References field to 1 for every symbol collected during indexing of a single TU.

Looking at the code, I think Symol.References is indeed only populated (i.e. set to 1) when CountReferences is enabled. Honestly, we should probably get rid of CountReferences; I don't see a reason not to count references.

But the statement count one per TU still stands in SymbolCollector, as it always only handles one TU at a time.

Actually, all I'm asking in the initial comment is to define the References counting behavior when there is no reference ;) I think a reasonable solution is to keep the references untouched when there is no reference, so that References aggregation via mergeSymbol can still work (for one-TU-per-Slab use cases).

And we should probably also document the new behavior e.g. DuplicateHandling in FileIndex.h seems to be a good place.

182–183

this FIXME can be removed?

191

any reason not to count references for PickOne?

[ilya-biryukov]

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

175

Honestly, we should probably get rid of CountReferences; I don't see a reason not to count references

We introduced it to avoid getting partial counts in dynamic index. In the absence of the static index, they would skew ranking towards symbols used inside the files you have open, which is not really a good signal in the first place.

I'm not sure if that actually hurts much in practice, though. It could very possibly be the case that the added complexity isn't worth it.

[kadircet]

• Address comments

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

46

You are right, thanks for pointing this out!

50

Moved into index/background.h

191

Because PickOne is not populating SymsStorage and is merely passing along pointers to SymbolSlabs. Counting references in that case would imply also making a new copy per each unique symbol.

Do you think it is worth it?

[ilya-biryukov]

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

113

We should agree on and stick to a single behavior in both cases.
I suggest keeping the current behavior for now (translation units). Why can't we implement that?

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

52

The comment suggests there's something cheesy going on.
Why would FileSymbols recompute the number of references? Can we avoid this complicated logic?

[kadircet]

It has been a long time since I've proposed that change and even I forgot some of the high level details. Therefore, I wanted to sum up the state again so that we can decide on how to move forward.

Currently we have two different on-disk formats for index in clangd:

• Static index:
  • Merged single file, since merging is done before persistence, the data on-disk contains correct reference counts.
  • Produced by running SymbolCollector on each TU. Collector doesn't keep state between different TUs, merging is done on the caller-site.
  • No need to count references when loading, doesn't interact with FileSymbols.

• Background index:
  • Sharded multiple files.
  • Produced by running SymbolCollector on each TU, but instead of merging we separate those symbols into distinct files. Merging is done later on within FileSymbols which has no information about TUs.

FileSymbols is currently being used by BackgroundIndex and FileIndex(Dynamic Idx):

• In the case of BackgroundIndex, a symbol occurs at most twice(once in the header declaring it and once in the implementation file, if they are distinct), therefore when merging is done symbol references doesn't go above that.
• FileIndex doesn't perform de-duplication before-hand therefore it can perform reference counting while performing the merge. But currently it doesn't perform any merging.

As a result, changing FileSymbols would only effect BackgroundIndex and nothing else. Since merging occurs using the information in RefSlabs this can also be extended to benefit FileIndex and will most definitely be used
by any sort of indexing that performs merging over multiple files.

For unification purposes I would rather delete the References counting logic in SymbolCollector and perform it only at mergers(clangd-indexer and FileSymbols)

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

113

Because FileSymbols only knows about file names and has no idea about whether a given file is TU or not. We might add some heuristics on the file extensions, or change SymbolCollector to count number of files(this would require maintaining a cache to de-duplicate references coming from the same files but originating from a different TU).

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

52

This was the idea behind https://github.com/clangd/clangd/issues/23. Please see the main comment for a higher level discussion.

[ilya-biryukov]

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

113

Update from the offline conversation:
It should be possible to produce the same counts as static-indexer, will wait for an updated revision.

[kadircet]

• Change logic to count references from only main files

[ilya-biryukov]

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

482 ↗

(On Diff #197288)

NIT: maybe initialize with =false to avoid potential UB.
Digest seems uninitialized too, could also ={} for it.

Sorry if this was discussed before and I'm repeating myself, I vaguely remember something similar but not sure what the conclusion was.

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

162

Let's use a named struct here? .second.second is super-hard to read

170

Could we avoid changing the merge logic?
I.e. the proposal is to keep the merging code the same and add a loop that counts references at the end.

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

60

NIT: this comment seems more appropriate at buildIndex, maybe move it there?
(It has the DuplicateHandle parameter, so it's closer to the context.

67

Maybe call the parameter CountReferences?
It would narrow down what the code can do with it and make the code easier to understand

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

49 ↗

(On Diff #197288)

NIT: to avoid warnings, we could use the corresponding suffix at the callsite (e.g. 1u) instead of casts
It's probably ok either way here, but having casts can lead to surprises if one passes negative numbers there

[kadircet]

• Address comments

[ilya-biryukov]

LGTM

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

148

NIT: maybe simplify to the following?

if (!Refs) {
  FileToRefs.erase(Path);
  return;
}
...

up to you.

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

67

NIT: use \p Refs

[kadircet]

• Address comments

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

private:
   llvm::Error index(tooling::CompileCommand,
                     BackgroundIndexStorage *IndexStorage);
   void buildIndex(); // Rebuild index periodically every BuildIndexPeriodMs.
   const size_t BuildIndexPeriodMs;
   std::atomic<bool> SymbolsUpdatedSinceLastIndex;
   std::mutex IndexMu;
   std::condition_variable IndexCV;
 
+  // Note that FileSymbols counts References by incrementing it per each file
+  // mentioning the symbol, including headers. This contradicts with the
+  // behavior inside clangd-indexer, which only counts translation units.
   FileSymbols IndexedSymbols;
   llvm::StringMap<FileDigest> IndexedFileDigests; // Key is absolute file path.
   std::mutex DigestsMu;
 
   BackgroundIndexStorage::Factory IndexStorageFactory;
   struct Source {
     std::string Path;
     bool NeedsReIndexing;

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

 /// file will create a new snapshot for all symbols in the file. Snapshots are
 /// managed with shared pointers that are shared between this class and the
 /// users. For each file, this class only stores a pointer pointing to the
 /// newest snapshot, and an outdated snapshot is deleted by the last owner of
 /// the snapshot, either this class or the symbol index.
 ///
 /// The snapshot semantics keeps critical sections minimal since we only need
 /// locking when we swap or obtain references to snapshots.
+///
+/// Will calculate Symbol::References based on number of RefSlabs referencing it
+/// when building the index with DuplicateHandling::Merge option if any
+/// References exists.
 class FileSymbols {
 public:
   /// Updates all symbols and refs in a file.
   /// If either is nullptr, corresponding data for \p Path will be removed.
   void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab,
               std::unique_ptr<RefSlab> Refs);
 
   // The index keeps the symbols alive.
   std::unique_ptr<SymbolIndex>
   buildIndex(IndexType,
              DuplicateHandling DuplicateHandle = DuplicateHandling::PickOne);
 
 private:

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

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include <memory>
 
 namespace clang {
 namespace clangd {
+namespace {
+// Puts all refs for the same symbol into RefsStorage in a contigious way.
+// If MergedSyms is provided, increments a symbols Reference count once for
+// every slab it was mentioned in.
+void mergeRefs(llvm::ArrayRef<std::shared_ptr<RefSlab>> RefSlabs,
+               std::vector<Ref> &RefsStorage,
+               llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> &AllRefs,
+               llvm::DenseMap<SymbolID, Symbol> *MergedSyms = nullptr) {
+  llvm::DenseMap<SymbolID, llvm::SmallVector<Ref, 4>> MergedRefs;
+  size_t Count = 0;
+  for (const auto &RefSlab : RefSlabs) {
+    for (const auto &Sym : *RefSlab) {
+      auto MergedRefEntry = MergedRefs.try_emplace(Sym.first);
+      MergedRefEntry.first->getSecond().append(Sym.second.begin(),
+                                               Sym.second.end());
+      Count += Sym.second.size();
+      if (MergedSyms) {
+        auto It = MergedSyms->find(Sym.first);
+        // This can happen when indexing is still going on, hopefully in the end
+        // all referenced symbols should exist inside MergedSyms.
+        if (It == MergedSyms->end())
+          continue;
+        // If this is the first time we see references to a symbol, reset its
+        // Reference count, since filesymbols re-count number of references
+        // based on number of refslabs referring to it.
+        if (MergedRefEntry.second)
+          It->getSecond().References = 0;
+        It->getSecond().References++;
+      }
+    }
+  }
+  RefsStorage.reserve(Count);
+  AllRefs.reserve(MergedRefs.size());
+  for (auto &Sym : MergedRefs) {
+    auto &SymRefs = Sym.second;
+    // Sorting isn't required, but yields more stable results over rebuilds.
+    llvm::sort(SymRefs);
+    llvm::copy(SymRefs, back_inserter(RefsStorage));
+    AllRefs.try_emplace(
+        Sym.first,
+        llvm::ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
+                            SymRefs.size()));
+  }
+}
+
+} // namespace
 
 static std::pair<SymbolSlab, RefSlab>
 indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
              llvm::ArrayRef<Decl *> DeclsToIndex,
              const CanonicalIncludes &Includes, bool IsIndexMainAST) {
   SymbolCollector::Options CollectorOpts;
   CollectorOpts.CollectIncludePath = true;
   CollectorOpts.Includes = &Includes;
void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Symbols,
   std::lock_guard<std::mutex> Lock(Mutex);
   if (!Symbols)
     FileToSymbols.erase(Path);
   else
     FileToSymbols[Path] = std::move(Symbols);
   if (!Refs)
     FileToRefs.erase(Path);
   else
     FileToRefs[Path] = std::move(Refs);
 }
 
 std::unique_ptr<SymbolIndex>
 FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle) {
   std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
   std::vector<std::shared_ptr<RefSlab>> RefSlabs;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto &FileAndSymbols : FileToSymbols)
       SymbolSlabs.push_back(FileAndSymbols.second);
     for (const auto &FileAndRefs : FileToRefs)
       RefSlabs.push_back(FileAndRefs.second);
   }
   std::vector<const Symbol *> AllSymbols;
   std::vector<Symbol> SymsStorage;
+  std::vector<Ref> RefsStorage; // Contiguous ranges for each SymbolID.
+  llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> AllRefs;
+
   switch (DuplicateHandle) {
   case DuplicateHandling::Merge: {
     llvm::DenseMap<SymbolID, Symbol> Merged;
     for (const auto &Slab : SymbolSlabs) {
       for (const auto &Sym : *Slab) {
         auto I = Merged.try_emplace(Sym.ID, Sym);
         if (!I.second)
           I.first->second = mergeSymbol(I.first->second, Sym);
       }
     }
+    mergeRefs(RefSlabs, RefsStorage, AllRefs, &Merged);
     SymsStorage.reserve(Merged.size());
     for (auto &Sym : Merged) {
       SymsStorage.push_back(std::move(Sym.second));
       AllSymbols.push_back(&SymsStorage.back());
     }
-    // FIXME: aggregate symbol reference count based on references.
     break;
   }
   case DuplicateHandling::PickOne: {
     llvm::DenseSet<SymbolID> AddedSymbols;
     for (const auto &Slab : SymbolSlabs)
       for (const auto &Sym : *Slab)
         if (AddedSymbols.insert(Sym.ID).second)
           AllSymbols.push_back(&Sym);
+    mergeRefs(RefSlabs, RefsStorage, AllRefs);
     break;
   }
   }
 
-  std::vector<Ref> RefsStorage; // Contiguous ranges for each SymbolID.
-  llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> AllRefs;
-  {
-    llvm::DenseMap<SymbolID, llvm::SmallVector<Ref, 4>> MergedRefs;
-    size_t Count = 0;
-    for (const auto &RefSlab : RefSlabs)
-      for (const auto &Sym : *RefSlab) {
-        MergedRefs[Sym.first].append(Sym.second.begin(), Sym.second.end());
-        Count += Sym.second.size();
-      }
-    RefsStorage.reserve(Count);
-    AllRefs.reserve(MergedRefs.size());
-    for (auto &Sym : MergedRefs) {
-      auto &SymRefs = Sym.second;
-      // Sorting isn't required, but yields more stable results over rebuilds.
-      llvm::sort(SymRefs);
-      llvm::copy(SymRefs, back_inserter(RefsStorage));
-      AllRefs.try_emplace(
-          Sym.first,
-          llvm::ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
-                              SymRefs.size()));
-    }
-  }
-
   size_t StorageSize =
       RefsStorage.size() * sizeof(Ref) + SymsStorage.size() * sizeof(Symbol);
   for (const auto &Slab : SymbolSlabs)
     StorageSize += Slab->bytes();
   for (const auto &RefSlab : RefSlabs)
     StorageSize += RefSlab->bytes();
 
   // Index must keep the slabs and contiguous ranges alive.

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

 RefsAre(std::vector<testing::Matcher<Ref>> Matchers) {
   return ElementsAre(testing::Pair(_, UnorderedElementsAreArray(Matchers)));
 }
 // URI cannot be empty since it references keys in the IncludeGraph.
 MATCHER(EmptyIncludeNode, "") {
   return !arg.IsTU && !arg.URI.empty() && arg.Digest == FileDigest{{0}} &&
          arg.DirectIncludes.empty();
 }
+MATCHER_P(NumReferences, N, "") { return arg.References == N; }
 
 class MemoryShardStorage : public BackgroundIndexStorage {
   mutable std::mutex StorageMu;
   llvm::StringMap<std::string> &Storage;
   size_t &CacheHits;
 
 public:
   MemoryShardStorage(llvm::StringMap<std::string> &Storage, size_t &CacheHits)
TEST_F(BackgroundIndexTest, IndexTwoFiles) {
 
   tooling::CompileCommand Cmd;
   Cmd.Filename = testPath("root/A.cc");
   Cmd.Directory = testPath("root");
   Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")};
   CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 
   ASSERT_TRUE(Idx.blockUntilIdleForTest());
-  EXPECT_THAT(
-      runFuzzyFind(Idx, ""),
-      UnorderedElementsAre(Named("common"), Named("A_CC"), Named("g"),
-                           AllOf(Named("f_b"), Declared(), Not(Defined()))));
+  EXPECT_THAT(runFuzzyFind(Idx, ""),
+              UnorderedElementsAre(AllOf(Named("common"), NumReferences(2U)),
+                                   AllOf(Named("A_CC"), NumReferences(1U)),
+                                   AllOf(Named("g"), NumReferences(0U)),
+                                   AllOf(Named("f_b"), Declared(),
+                                         Not(Defined()), NumReferences(1U))));
 
   Cmd.Filename = testPath("root/B.cc");
   Cmd.CommandLine = {"clang++", Cmd.Filename};
-  CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
+  CDB.setCompileCommand(testPath("root/B.cc"), Cmd);
 
   ASSERT_TRUE(Idx.blockUntilIdleForTest());
   // B_CC is dropped as we don't collect symbols from A.h in this compilation.
   EXPECT_THAT(runFuzzyFind(Idx, ""),
-              UnorderedElementsAre(Named("common"), Named("A_CC"), Named("g"),
-                                   AllOf(Named("f_b"), Declared(), Defined())));
+              UnorderedElementsAre(AllOf(Named("common"), NumReferences(3U)),
+                                   AllOf(Named("A_CC"), NumReferences(1U)),
+                                   AllOf(Named("g"), NumReferences(0U)),
+                                   AllOf(Named("f_b"), Declared(), Defined(),
+                                         NumReferences(2U))));
 
   auto Syms = runFuzzyFind(Idx, "common");
   EXPECT_THAT(Syms, UnorderedElementsAre(Named("common")));
   auto Common = *Syms.begin();
   EXPECT_THAT(getRefs(Idx, Common.ID),
               RefsAre({FileURI("unittest:///root/A.h"),
                        FileURI("unittest:///root/A.cc"),
                        FileURI("unittest:///root/B.cc")}));

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

 MATCHER_P(FileURI, F, "") { return llvm::StringRef(arg.Location.FileURI) == F; }
 MATCHER_P(DeclURI, U, "") {
   return llvm::StringRef(arg.CanonicalDeclaration.FileURI) == U;
 }
 MATCHER_P(DefURI, U, "") {
   return llvm::StringRef(arg.Definition.FileURI) == U;
 }
 MATCHER_P(QName, N, "") { return (arg.Scope + arg.Name).str() == N; }
+MATCHER_P(NumReferences, N, "") {
+  return arg.References == static_cast<unsigned>(N);
+}
 
 namespace clang {
 namespace clangd {
 namespace {
 testing::Matcher<const RefSlab &>
 RefsAre(std::vector<testing::Matcher<Ref>> Matchers) {
   return ElementsAre(testing::Pair(_, UnorderedElementsAreArray(Matchers)));
 }
 
 Symbol symbol(llvm::StringRef ID) {
   Symbol Sym;
   Sym.ID = SymbolID(ID);
   Sym.Name = ID;
+  Sym.References = 1;
   return Sym;
 }
 
 std::unique_ptr<SymbolSlab> numSlab(int Begin, int End) {
   SymbolSlab::Builder Slab;
   for (int i = Begin; i <= End; i++)
     Slab.insert(symbol(std::to_string(i)));
   return llvm::make_unique<SymbolSlab>(std::move(Slab).build());
TEST(FileIndexTest, ReferencesInMainFileWithPreamble) {
   RefsRequest Request;
   Request.IDs.insert(Foo.ID);
 
   // Expect to see references in main file, references in headers are excluded
   // because we only index main AST.
   EXPECT_THAT(getRefs(Index, Foo.ID), RefsAre({RefRange(Main.range())}));
 }
 
+TEST(FileSymbolsTest, CountReferencesNoRefs) {
+  FileSymbols FS;
+  FS.update("f1", numSlab(1, 3), nullptr);
+  FS.update("f2", numSlab(1, 3), nullptr);
+  FS.update("f3", numSlab(1, 3), nullptr);
+  EXPECT_THAT(
+      runFuzzyFind(*FS.buildIndex(IndexType::Light, DuplicateHandling::Merge),
+                   ""),
+      UnorderedElementsAre(AllOf(QName("1"), NumReferences(3)),
+                           AllOf(QName("2"), NumReferences(3)),
+                           AllOf(QName("3"), NumReferences(3))));
+}
+
+TEST(FileSymbolsTest, CountReferencesWithRefs) {
+  FileSymbols FS;
+  FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cpp"));
+  FS.update("f2", numSlab(1, 3), refSlab(SymbolID("2"), "f2.cpp"));
+  FS.update("f3", numSlab(1, 3), refSlab(SymbolID("3"), "f3.cpp"));
+  EXPECT_THAT(
+      runFuzzyFind(*FS.buildIndex(IndexType::Light, DuplicateHandling::Merge),
+                   ""),
+      UnorderedElementsAre(AllOf(QName("1"), NumReferences(1)),
+                           AllOf(QName("2"), NumReferences(1)),
+                           AllOf(QName("3"), NumReferences(1))));
+}
 } // namespace
 } // namespace clangd
 } // namespace clang