[clangd] Ignore the static index refs from the dynamic index files.

[ArcsinX]

Summary

This patch fixes the following problem:

• open a file with references to the symbol Foo
• remove all references to Foo (from the dynamic index).
• MergedIndex::refs() result will contain positions of removed references (from the static index).

The idea of this patch is to keep a set of files which were used during index build inside the index.
Thus at processing the static index references we can check if the file of processing reference is a part of the dynamic index or not.

[sammccall]

TL;DR: Cool! I think we should complicate the signature of hasFile() a bit to avoid calling SwapIndex::snapshot() for each file. There's also some quadratic behavior due to calling index ops from MergeIndex when children are MergeIndexes, but N is small and I think we can solve it later.

---

I like the simplicity/elegance of this solution, and the fact that it avoids the scaling pitfall of trying to return a list of all the indexed files.

I am concerned about performance though. At a high level, we try to make index operations fairly coarse/batched and only do a handful of them. This was originally to allow these operations to be RPCs, but of course this assumption gets baked in in other ways too. Introducing a fine-grained operation like this causes some of the assumptions to be violated.

Concretely, SwapIndex (and ProjectAwareIndex) take a lock to obtain the index snapshot to use, and so here we do that for each call to hasFile(). Most indexes are wrapped in SwapIndex for either lazy-loading or dynamic updating.

And we hammer it reasonably hard here, MergeIndex::refs() will call it in a loop for ~100 times, and because there are multiple MergeIndexes in the index stack, we end up with duplication: the first index never gets hasFile(), the second gets it 100 times, the third 200 times, the fourth 300 times. (Currently we have at least 4 indexes in the stack).

Taking 600 locks to call refs() seems... less than ideal. For now they'll probably be uncontended as we only call refs() for interactive actions (find-references and rename), but fundamentally this applies to all requests, not just refs, so I'm not sure this will be true in the future (a fast pseudoparser index will want to consult the previous index to resolve symbols).

This all seems related to the idea that hasFile() isn't implemented for RemoteIndex - it's a pragmatic shortcut, but in principle it'd be nice to be able to implement it, and there's some minimum per-RPC overhead.

---

So, can we do anything about all this?

Locking once for each ref: fundamentally we want to lock once to get the snapshot, then query the snapshot for each file. This changing hasFile to return an oracle that can be cheaply queried, e.g. a signature like unique_function<bool(StringRef)> SymbolIndex::indexedFiles().

The quadratic nature of calling any index ops in MergedIndex: I guess probably not without flattening our binary-tree/linked-list of MergedIndex into an N-way merge. Back in the day, we basically had one static index which was huge, and one dynamic index which was tiny, and the no-copy aspect of MergedIndex was appealing (and it was easy to implement!). But we're probably not coming out ahead anymore vs simply committing to copy everything once. The N-way merge would have other advantages too: we could query large/slow indexes in parallel to improve latency.

Implementing a pseudo-batch form of hasFiles as an RPC for remote-index: we'd need to give up on getting answers for files one-by-one. That would be OK for an N-way merge (since we'd fetch all results before merging, we could build a list). But servers typically index *everything* under a certain directory, so fetching the list of directories and evaluating per-file queries client-side is a cheap and reasonable alternative (that's more accurate than return false!)

[ArcsinX]

bool SymbolIndex::hasFile(llvm::StringRef) => llvm::unique_function<bool(llvm::StringRef)> SymbolIndex::indexedFiles()

[ArcsinX]

Thanks for your reply. I have updated the patch (changed signature of hasFile), but remote-index scenario is not clear for me yet.

In D93393#2458168, @sammccall wrote:

Implementing a pseudo-batch form of hasFiles as an RPC for remote-index: we'd need to give up on getting answers for files one-by-one. That would be OK for an N-way merge (since we'd fetch all results before merging, we could build a list). But servers typically index *everything* under a certain directory, so fetching the list of directories and evaluating per-file queries client-side is a cheap and reasonable alternative (that's more accurate than return false!)

Seems I need some clarifications here.
Is it should be like this?:

• [client]->[server] Give me all directories and subdirectories
• [client]<-[server] All directories are .....

(we need this only once)

IndexClient::indexedFiles() {
<returns function which checks if the file is inside a directory from the list (i.e. full filename starts with a directory from the list)>
}

What structure should be used for directories list? I think we can use Trie

Am I right about your suggestion?

[sammccall]

Thanks, this should work with some slight tweaks.
Biggest question is if we really need/want to allow this function to be null.

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

127

Maybe to be really explicit, add the lifetime constraint: "The function must only be called while the index is alive."

127

it looks below like you allow this to return nullptr. TL;DR: I think we probably shouldn't, and just return false with a fixme in RemoteIndex, and false without a fixme in ProjectAwareIndex.

If we do this, we should:

• explicitly call out that possibility, because it's error-prone
• carefully define the semantics

In the implementations nullptr seems to be used in two ways:

• to mean "always no", as in ProjectAwareIndex with no project.
• to mean "always don't-know", as in RemoteIndex. The problem is

I don't see any reason to use nullptr for "no" instead of returning [](StringRef){return false;}.
The "don't-know" is more appealing, because the indexes don't have to lie and instead the caller handles the ambiguity. The problem is you can't be consistent about it. Given a MergedIndex where Static->indexedFiles() is non-null and Dynamic->indexFiles() is null, then the answer can be "yes" or "don't know" depending on the file, and we can't express that, so we have to lie anyway.

We could add a tristate return value for the function, but given that it's plausible we could actually implement indexedFiles() for remote index later, I think we should just return false in the "don't know" case for now, with a FIXME there.

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

116

need to consumeError(Path.takeError()) here, or we'll crash in debug mode on error

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

127

this is calling indexedFiles() once for each file we're checking, rather than once overall.

You want to move these variables to the capture list instead. (There should be no need to capture this in the end)

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

122

(this is definitely-no-files, so as mentioned above [](StringRef){return false;} seems more appropriate)

clang-tools-extra/clangd/index/dex/Dex.cpp

320

and need to consume error here

[sammccall]

In D93393#2460066, @ArcsinX wrote:

Thanks for your reply. I have updated the patch (changed signature of hasFile), but remote-index scenario is not clear for me yet.

Sorry, I didn't see this before comments.

To be clear, I'm *not* asking you to add remote support in this patch, I'm just thinking aloud at what it might be like.
The "return false" behavior is fine for now. The remote index is basically at the bottom of the stack, so it's mostly moot. And "return false" yields the old behavior anyway.

I just want to think aloud about how we can add it on :-)

In D93393#2458168, @sammccall wrote:

Implementing a pseudo-batch form of hasFiles as an RPC for remote-index: we'd need to give up on getting answers for files one-by-one. That would be OK for an N-way merge (since we'd fetch all results before merging, we could build a list). But servers typically index *everything* under a certain directory, so fetching the list of directories and evaluating per-file queries client-side is a cheap and reasonable alternative (that's more accurate than return false!)

Seems I need some clarifications here.
Is it should be like this?:

• [client]->[server] Give me all directories and subdirectories
• [client]<-[server] All directories are .....

(we need this only once)

Right - we could fetch it when the connection goes up, or on every request, or even configure it entirely client-side (the client knows about the "mount point" of the index and maybe we could assume it's fully-populated). I'm a little hazy on this, @kbobyrev @kadircet would know what's best here once back from vacation.

IndexClient::indexedFiles() {
<returns function which checks if the file is inside a directory from the list (i.e. full filename starts with a directory from the list)>
}

What structure should be used for directories list? I think we can use Trie

Probably just a string or flat list - I think this is exactly one directory today, maybe a short list in future.
(We have the assumption of a single root for path-translation purposes, not sure if we've seen any need for that root to be "partly-populated" yet. If so we may just end up creating one Index instance per directory and share stubs between them.)

But again, this isn't something you need to build now, unless you're really keen :-)

[ArcsinX]

Make indexedFiles() to return [](StringRef){return false;} instead of nullptr.
Add comments.
Do not call indexedFiles() at every file check for MergeIndex.
Consume error if URI::resolve() fails.

[sammccall]

Fantastic, thanks so much!

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

129

Currently the signature says that the returned function is not const/threadsafe.
If you prefer, you can have it be unique_function<bool(StringRef) const>, then the contract is that it's const/threadsafe and you don't need mutable here.

Up to you though, I can't think of a case where we *need* it to be threadsafe.

[ArcsinX]

Fix comment inside IndexClient::indexedFiles()

[ArcsinX]

unique_function<bool(StringRef)> indexedFiles() const => unique_function<bool(StringRef) const> indexedFiles() const
StringRef => llvm::StringRef for consistency

[ArcsinX]

Thank you for review!

[ArcsinX]

StringRef => llvm::StringRef in one more place.

[ArcsinX]

Fix format
Rebase

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

 }
 
 std::unique_ptr<SymbolIndex>
 FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle,
                         size_t *Version) {
   std::vector<std::shared_ptr<SymbolSlab>> SymbolSlabs;
   std::vector<std::shared_ptr<RefSlab>> RefSlabs;
   std::vector<std::shared_ptr<RelationSlab>> RelationSlabs;
+  llvm::StringSet<> Files;
   std::vector<RefSlab *> MainFileRefs;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
-    for (const auto &FileAndSymbols : SymbolsSnapshot)
+    for (const auto &FileAndSymbols : SymbolsSnapshot) {
       SymbolSlabs.push_back(FileAndSymbols.second);
+      Files.insert(FileAndSymbols.first());
+    }
     for (const auto &FileAndRefs : RefsSnapshot) {
       RefSlabs.push_back(FileAndRefs.second.Slab);
       if (FileAndRefs.second.CountReferences)
         MainFileRefs.push_back(RefSlabs.back().get());
     }
     for (const auto &FileAndRelations : RelationsSnapshot)
       RelationSlabs.push_back(FileAndRelations.second);
 
FileSymbols::buildIndex(IndexType Type, DuplicateHandling DuplicateHandle,
   for (const auto &RefSlab : RefSlabs)
     StorageSize += RefSlab->bytes();
 
   // Index must keep the slabs and contiguous ranges alive.
   switch (Type) {
   case IndexType::Light:
     return std::make_unique<MemIndex>(
         llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
-        std::move(AllRelations),
+        std::move(AllRelations), std::move(Files),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
                         std::move(RefsStorage), std::move(SymsStorage)),
         StorageSize);
   case IndexType::Heavy:
     return std::make_unique<dex::Dex>(
         llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
-        std::move(AllRelations),
+        std::move(AllRelations), std::move(Files),
         std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
                         std::move(RefsStorage), std::move(SymsStorage)),
         StorageSize);
   }
   llvm_unreachable("Unknown clangd::IndexType");
 }
 
 void FileSymbols::profile(MemoryTree &MT) const {

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

 //===--- Index.h -------------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 
 #include "Ref.h"
 #include "Relation.h"
 #include "Symbol.h"
 #include "SymbolID.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/FunctionExtras.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/JSON.h"
 #include <mutex>
 #include <string>
 
 namespace clang {
 namespace clangd {
public:
   /// Finds all relations (S, P, O) stored in the index such that S is among
   /// Req.Subjects and P is Req.Predicate, and invokes \p Callback for (S, O) in
   /// each.
   virtual void relations(
       const RelationsRequest &Req,
       llvm::function_ref<void(const SymbolID &Subject, const Symbol &Object)>
           Callback) const = 0;
 
+  /// Returns function which checks if the specified file was used to build this
+  /// index or not. The function must only be called while the index is alive.
+  virtual llvm::unique_function<bool(llvm::StringRef) const>
+  indexedFiles() const = 0;
+
   /// Returns estimated size of index (in bytes).
   virtual size_t estimateMemoryUsage() const = 0;
 };
 
 // Delegating implementation of SymbolIndex whose delegate can be swapped out.
 class SwapIndex : public SymbolIndex {
 public:
   // If an index is not provided, reset() must be called.
   SwapIndex(std::unique_ptr<SymbolIndex> Index = nullptr)
       : Index(std::move(Index)) {}
   void reset(std::unique_ptr<SymbolIndex>);
 
   // SymbolIndex methods delegate to the current index, which is kept alive
   // until the call returns (even if reset() is called).
   bool fuzzyFind(const FuzzyFindRequest &,
                  llvm::function_ref<void(const Symbol &)>) const override;
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override;
   bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
 
+  llvm::unique_function<bool(llvm::StringRef) const>
+  indexedFiles() const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
   std::shared_ptr<SymbolIndex> snapshot() const;
   mutable std::mutex Mutex;
   std::shared_ptr<SymbolIndex> Index;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

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

bool SwapIndex::refs(const RefsRequest &R,
   return snapshot()->refs(R, CB);
 }
 void SwapIndex::relations(
     const RelationsRequest &R,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> CB) const {
   return snapshot()->relations(R, CB);
 }
 
+llvm::unique_function<bool(llvm::StringRef) const>
+SwapIndex::indexedFiles() const {
+  return snapshot()->indexedFiles();
+}
+
 size_t SwapIndex::estimateMemoryUsage() const {
   return snapshot()->estimateMemoryUsage();
 }
 
 } // namespace clangd
 } // namespace clang

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

 //===--- MemIndex.h - 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H
 
 #include "Index.h"
+#include "llvm/ADT/StringSet.h"
 #include <mutex>
 
 namespace clang {
 namespace clangd {
 
 /// MemIndex is a naive in-memory index suitable for a small set of symbols.
 class MemIndex : public SymbolIndex {
 public:
MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations,
       : MemIndex(std::forward<SymbolRange>(Symbols),
                  std::forward<RefRange>(Refs),
                  std::forward<RelationRange>(Relations)) {
     KeepAlive = std::shared_ptr<void>(
         std::make_shared<Payload>(std::move(BackingData)), nullptr);
     this->BackingDataSize = BackingDataSize;
   }
 
+  template <typename SymbolRange, typename RefRange, typename RelationRange,
+            typename FileRange, typename Payload>
+  MemIndex(SymbolRange &&Symbols, RefRange &&Refs, RelationRange &&Relations,
+           FileRange &&Files, Payload &&BackingData, size_t BackingDataSize)
+      : MemIndex(std::forward<SymbolRange>(Symbols),
+                 std::forward<RefRange>(Refs),
+                 std::forward<RelationRange>(Relations),
+                 std::forward<Payload>(BackingData), BackingDataSize) {
+    this->Files = std::forward<FileRange>(Files);
+  }
+
   /// Builds an index from slabs. The index takes ownership of the data.
   static std::unique_ptr<SymbolIndex> build(SymbolSlab Symbols, RefSlab Refs,
                                             RelationSlab Relations);
 
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   bool refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
+  llvm::unique_function<bool(llvm::StringRef) const>
+  indexedFiles() const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
   // Index is a set of symbols that are deduplicated by symbol IDs.
   llvm::DenseMap<SymbolID, const Symbol *> Index;
   // A map from symbol ID to symbol refs, support query by IDs.
   llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
   // A map from (subject, predicate) pair to objects.
   static_assert(sizeof(RelationKind) == sizeof(uint8_t),
                 "RelationKind should be of same size as a uint8_t");
   llvm::DenseMap<std::pair<SymbolID, uint8_t>, std::vector<SymbolID>> Relations;
+  // Set of files which were used during this index build.
+  llvm::StringSet<> Files;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
   // Size of memory retained by KeepAlive.
   size_t BackingDataSize = 0;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H

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

if (It != Relations.end()) {
           LookupReq.IDs.insert(Obj);
         }
       }
     }
     lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
   }
 }
 
+llvm::unique_function<bool(llvm::StringRef) const>
+MemIndex::indexedFiles() const {
+  return [this](llvm::StringRef FileURI) {
+    auto Path = URI::resolve(FileURI);
+    if (!Path) {
+      llvm::consumeError(Path.takeError());
+      return false;
+    }
+    return Files.contains(*Path);
+  };
+}
+
 size_t MemIndex::estimateMemoryUsage() const {
   return Index.getMemorySize() + Refs.getMemorySize() +
          Relations.getMemorySize() + BackingDataSize;
 }
 
 } // namespace clangd
 } // namespace clang

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

bool fuzzyFind(const FuzzyFindRequest &,
                  llvm::function_ref<void(const Symbol &)>) const override;
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override;
   bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override;
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override;
+  llvm::unique_function<bool(llvm::StringRef) const>
+  indexedFiles() const override;
   size_t estimateMemoryUsage() const override {
     return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
   }
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MERGE_H

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

bool MergedIndex::refs(const RefsRequest &Req,
   trace::Span Tracer("MergedIndex refs");
   bool More = false;
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   // We don't want duplicated refs from the static/dynamic indexes,
   // and we can't reliably deduplicate them because offsets may differ slightly.
   // We consider the dynamic index authoritative and report all its refs,
   // and only report static index refs from other files.
-  //
-  // FIXME: The heuristic fails if the dynamic index contains a file, but all
-  // refs were removed (we will report stale ones from the static index).
-  // Ultimately we should explicit check which index has the file instead.
-  llvm::StringSet<> DynamicIndexFileURIs;
   More |= Dynamic->refs(Req, [&](const Ref &O) {
-    DynamicIndexFileURIs.insert(O.Location.FileURI);
     Callback(O);
     assert(Remaining != 0);
     --Remaining;
   });
   if (Remaining == 0 && More)
     return More;
+  auto DynamicContainsFile = Dynamic->indexedFiles();
   // We return less than Req.Limit if static index returns more refs for dirty
   // files.
-  bool StaticHadMore =  Static->refs(Req, [&](const Ref &O) {
-    if (DynamicIndexFileURIs.count(O.Location.FileURI))
+  bool StaticHadMore = Static->refs(Req, [&](const Ref &O) {
+    if (DynamicContainsFile(O.Location.FileURI))
       return; // ignore refs that have been seen from dynamic index.
     if (Remaining == 0) {
       More = true;
       return;
     }
     --Remaining;
     Callback(O);
   });
   return More || StaticHadMore;
 }
 
+llvm::unique_function<bool(llvm::StringRef) const>
+MergedIndex::indexedFiles() const {
+  return [DynamicContainsFile{Dynamic->indexedFiles()},
+          StaticContainsFile{Static->indexedFiles()}](llvm::StringRef FileURI) {
+    return DynamicContainsFile(FileURI) || StaticContainsFile(FileURI);
+  };
+}
+
 void MergedIndex::relations(
     const RelationsRequest &Req,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
   uint32_t Remaining =
       Req.Limit.getValueOr(std::numeric_limits<uint32_t>::max());
   // Return results from both indexes but avoid duplicates.
   // We might return stale relations from the static index;
   // we don't currently have a good way of identifying them.

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

public:
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   /// Query all indexes while prioritizing the associated one (if any).
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
+  llvm::unique_function<bool(llvm::StringRef) const>
+  indexedFiles() const override;
+
   ProjectAwareIndex(IndexFactory Gen) : Gen(std::move(Gen)) {}
 
 private:
   // Returns the index associated with current context, if any.
   SymbolIndex *getIndex() const;
 
   // Storage for all the external indexes.
   mutable std::mutex Mu;

 void ProjectAwareIndex::relations(
     const RelationsRequest &Req,
     llvm::function_ref<void(const SymbolID &, const Symbol &)> Callback) const {
   trace::Span Tracer("ProjectAwareIndex::relations");
   if (auto *Idx = getIndex())
     return Idx->relations(Req, Callback);
 }
 
+llvm::unique_function<bool(llvm::StringRef) const>
+ProjectAwareIndex::indexedFiles() const {
+  trace::Span Tracer("ProjectAwareIndex::indexedFiles");
+  if (auto *Idx = getIndex())
+    return Idx->indexedFiles();
+  return [](llvm::StringRef) { return false; };
+}
+
 SymbolIndex *ProjectAwareIndex::getIndex() const {
   const auto &C = Config::current();
   if (!C.Index.External)
     return nullptr;
   const auto &External = *C.Index.External;
   std::lock_guard<std::mutex> Lock(Mu);
   auto Entry = IndexForSpec.try_emplace(External, nullptr);
   if (Entry.second)

clang-tools-extra/clangd/index/dex/Dex.h

Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations,
       Payload &&BackingData, size_t BackingDataSize)
       : Dex(std::forward<SymbolRange>(Symbols), std::forward<RefsRange>(Refs),
             std::forward<RelationsRange>(Relations)) {
     KeepAlive = std::shared_ptr<void>(
         std::make_shared<Payload>(std::move(BackingData)), nullptr);
     this->BackingDataSize = BackingDataSize;
   }
 
+  template <typename SymbolRange, typename RefsRange, typename RelationsRange,
+            typename FileRange, typename Payload>
+  Dex(SymbolRange &&Symbols, RefsRange &&Refs, RelationsRange &&Relations,
+      FileRange &&Files, Payload &&BackingData, size_t BackingDataSize)
+      : Dex(std::forward<SymbolRange>(Symbols), std::forward<RefsRange>(Refs),
+            std::forward<RelationsRange>(Relations),
+            std::forward<Payload>(BackingData), BackingDataSize) {
+    this->Files = std::forward<FileRange>(Files);
+  }
+
   /// Builds an index from slabs. The index takes ownership of the slab.
   static std::unique_ptr<SymbolIndex> build(SymbolSlab, RefSlab, RelationSlab);
 
   bool
   fuzzyFind(const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   bool refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override;
 
   void relations(const RelationsRequest &Req,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>
                      Callback) const override;
 
+  llvm::unique_function<bool(llvm::StringRef) const>
+  indexedFiles() const override;
+
   size_t estimateMemoryUsage() const override;
 
 private:
   void buildIndex();
   std::unique_ptr<Iterator> iterator(const Token &Tok) const;
   std::unique_ptr<Iterator>
   createFileProximityIterator(llvm::ArrayRef<std::string> ProximityPaths) const;
   std::unique_ptr<Iterator>
private:
   /// during the fuzzyFind process.
   llvm::DenseMap<Token, PostingList> InvertedIndex;
   dex::Corpus Corpus;
   llvm::DenseMap<SymbolID, llvm::ArrayRef<Ref>> Refs;
   static_assert(sizeof(RelationKind) == sizeof(uint8_t),
                 "RelationKind should be of same size as a uint8_t");
   llvm::DenseMap<std::pair<SymbolID, uint8_t>, std::vector<SymbolID>> Relations;
   std::shared_ptr<void> KeepAlive; // poor man's move-only std::any
+  // Set of files which were used during this index build.
+  llvm::StringSet<> Files;
   // Size of memory retained by KeepAlive.
   size_t BackingDataSize = 0;
 };
 
 /// Returns Search Token for a number of parent directories of given Path.
 /// Should be used within the index build process.
 ///
 /// This function is exposed for testing only.
 std::vector<std::string> generateProximityURIs(llvm::StringRef URIPath);
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H

clang-tools-extra/clangd/index/dex/Dex.cpp

if (It != Relations.end()) {
           LookupReq.IDs.insert(Object);
         }
       }
     }
     lookup(LookupReq, [&](const Symbol &Object) { Callback(Subject, Object); });
   }
 }
 
+llvm::unique_function<bool(llvm::StringRef) const> Dex::indexedFiles() const {
+  return [this](llvm::StringRef FileURI) {
+    auto Path = URI::resolve(FileURI);
+    if (!Path) {
+      llvm::consumeError(Path.takeError());
+      return false;
+    }
+    return Files.contains(*Path);
+  };
+}
+
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
   Bytes += LookupTable.getMemorySize();
   Bytes += InvertedIndex.getMemorySize();
   for (const auto &TokenToPostingList : InvertedIndex)
     Bytes += TokenToPostingList.second.bytes();
   Bytes += Refs.getMemorySize();

clang-tools-extra/clangd/index/remote/Client.cpp

relations(const clangd::RelationsRequest &Request,
                 Callback) const override {
     streamRPC(Request, &remote::v1::SymbolIndex::Stub::Relations,
               // Unpack protobuf Relation.
               [&](std::pair<SymbolID, clangd::Symbol> SubjectAndObject) {
                 Callback(SubjectAndObject.first, SubjectAndObject.second);
               });
   }
 
+  llvm::unique_function<bool(llvm::StringRef) const> indexedFiles() const {
+    // FIXME: For now we always return "false" regardless of whether the file
+    //        was indexed or not. A possible implementation could be based on
+    //        the idea that we do not want to send a request at every
+    //        call of a function returned by IndexClient::indexedFiles().
+    return [](llvm::StringRef) { return false; };
+  }
+
   // IndexClient does not take any space since the data is stored on the
   // server.
   size_t estimateMemoryUsage() const override { return 0; }
 
 private:
   std::unique_ptr<remote::v1::SymbolIndex::Stub> Stub;
   std::shared_ptr<grpc::Channel> Channel;
   llvm::SmallString<256> ServerAddress;

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

bool refs(const RefsRequest &,
             llvm::function_ref<void(const Ref &)>) const override {
     return false;
   }
 
   void relations(const RelationsRequest &,
                  llvm::function_ref<void(const SymbolID &, const Symbol &)>)
       const override {}
 
+  llvm::unique_function<bool(llvm::StringRef) const>
+  indexedFiles() const override {
+    return [](llvm::StringRef) { return false; };
+  }
+
   // This is incorrect, but IndexRequestCollector is not an actual index and it
   // isn't used in production code.
   size_t estimateMemoryUsage() const override { return 0; }
 
   const std::vector<FuzzyFindRequest> consumeRequests(size_t Num) const {
     std::unique_lock<std::mutex> Lock(Mut);
     EXPECT_TRUE(wait(Lock, ReceivedRequestCV, timeoutSeconds(30),
                      [this, Num] { return Requests.size() == Num; }));

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

TEST(DexTests, Relations) {
   Req.Subjects.insert(Parent.ID);
   Req.Predicate = RelationKind::BaseOf;
   I.relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
     Results.push_back(Object.ID);
   });
   EXPECT_THAT(Results, UnorderedElementsAre(Child1.ID, Child2.ID));
 }
 
+TEST(DexIndex, IndexedFiles) {
+  SymbolSlab Symbols;
+  RefSlab Refs;
+  auto Size = Symbols.bytes() + Refs.bytes();
+  auto Data = std::make_pair(std::move(Symbols), std::move(Refs));
+  llvm::StringSet<> Files = {testPath("foo.cc"), testPath("bar.cc")};
+  Dex I(std::move(Data.first), std::move(Data.second), RelationSlab(),
+        std::move(Files), std::move(Data), Size);
+  auto ContainsFile = I.indexedFiles();
+  EXPECT_TRUE(ContainsFile("unittest:///foo.cc"));
+  EXPECT_TRUE(ContainsFile("unittest:///bar.cc"));
+  EXPECT_FALSE(ContainsFile("unittest:///foobar.cc"));
+}
+
 TEST(DexTest, PreferredTypesBoosting) {
   auto Sym1 = symbol("t1");
   Sym1.Type = "T1";
   auto Sym2 = symbol("t2");
   Sym2.Type = "T2";
 
   std::vector<Symbol> Symbols{Sym1, Sym2};
   Dex I(Symbols, RefSlab(), RelationSlab());

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

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, IndexedFiles) {
+  SymbolSlab Symbols;
+  RefSlab Refs;
+  auto Size = Symbols.bytes() + Refs.bytes();
+  auto Data = std::make_pair(std::move(Symbols), std::move(Refs));
+  llvm::StringSet<> Files = {testPath("foo.cc"), testPath("bar.cc")};
+  MemIndex I(std::move(Data.first), std::move(Data.second), RelationSlab(),
+             std::move(Files), std::move(Data), Size);
+  auto ContainsFile = I.indexedFiles();
+  EXPECT_TRUE(ContainsFile("unittest:///foo.cc"));
+  EXPECT_TRUE(ContainsFile("unittest:///bar.cc"));
+  EXPECT_FALSE(ContainsFile("unittest:///foobar.cc"));
+}
+
 TEST(MemIndexTest, TemplateSpecialization) {
   SymbolSlab::Builder B;
 
   Symbol S = symbol("TempSpec");
   S.ID = SymbolID("1");
   B.insert(S);
 
   S = symbol("TempSpec");
TEST(MergeIndexTest, Refs) {
 
   // Build dynamic index for test.cc.
   Annotations Test1Code(R"(class $Foo[[Foo]];)");
   TestTU Test;
   Test.HeaderCode = HeaderCode;
   Test.Code = std::string(Test1Code.code());
   Test.Filename = "test.cc";
   auto AST = Test.build();
-  Dyn.updateMain(Test.Filename, AST);
+  Dyn.updateMain(testPath(Test.Filename), AST);
 
   // Build static index for test.cc.
   Test.HeaderCode = HeaderCode;
   Test.Code = "// static\nclass Foo {};";
   Test.Filename = "test.cc";
   auto StaticAST = Test.build();
   // Add stale refs for test.cc.
-  StaticIndex.updateMain(Test.Filename, StaticAST);
+  StaticIndex.updateMain(testPath(Test.Filename), StaticAST);
 
   // Add refs for test2.cc
   Annotations Test2Code(R"(class $Foo[[Foo]] {};)");
   TestTU Test2;
   Test2.HeaderCode = HeaderCode;
   Test2.Code = std::string(Test2Code.code());
   Test2.Filename = "test2.cc";
   StaticAST = Test2.build();
-  StaticIndex.updateMain(Test2.Filename, StaticAST);
+  StaticIndex.updateMain(testPath(Test2.Filename), StaticAST);
 
   RefsRequest Request;
   Request.IDs = {Foo.ID};
   RefSlab::Builder Results;
   EXPECT_FALSE(
       Merge.refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); }));
   EXPECT_THAT(
       std::move(Results).build(),
       ElementsAre(Pair(
           _, UnorderedElementsAre(AllOf(RefRange(Test1Code.range("Foo")),
                                         FileURI("unittest:///test.cc")),
                                   AllOf(RefRange(Test2Code.range("Foo")),
                                         FileURI("unittest:///test2.cc"))))));
 
   Request.Limit = 1;
   RefSlab::Builder Results2;
   EXPECT_TRUE(
       Merge.refs(Request, [&](const Ref &O) { Results2.insert(Foo.ID, O); }));
-  EXPECT_THAT(std::move(Results2).build(),
-              ElementsAre(Pair(
-                  _, ElementsAre(AnyOf(FileURI("unittest:///test.cc"),
-                                       FileURI("unittest:///test2.cc"))))));
+
+  // Remove all refs for test.cc from dynamic index,
+  // merged index should not return results from static index for test.cc.
+  Test.Code = "";
+  AST = Test.build();
+  Dyn.updateMain(testPath(Test.Filename), AST);
+
+  Request.Limit = llvm::None;
+  RefSlab::Builder Results3;
+  EXPECT_FALSE(
+      Merge.refs(Request, [&](const Ref &O) { Results3.insert(Foo.ID, O); }));
+  EXPECT_THAT(std::move(Results3).build(),
+              ElementsAre(Pair(_, UnorderedElementsAre(AllOf(
+                                      RefRange(Test2Code.range("Foo")),
 }
 
+TEST(MergeIndexTest, IndexedFiles) {
+  SymbolSlab DynSymbols;
+  RefSlab DynRefs;
+  auto DynSize = DynSymbols.bytes() + DynRefs.bytes();
+  auto DynData = std::make_pair(std::move(DynSymbols), std::move(DynRefs));
+  llvm::StringSet<> DynFiles = {testPath("foo.cc")};
+  MemIndex DynIndex(std::move(DynData.first), std::move(DynData.second),
+                    RelationSlab(), std::move(DynFiles), std::move(DynData),
+                    DynSize);
+  SymbolSlab StaticSymbols;
+  RefSlab StaticRefs;
+  auto StaticData =
+      std::make_pair(std::move(StaticSymbols), std::move(StaticRefs));
+  llvm::StringSet<> StaticFiles = {testPath("bar.cc")};
+  MemIndex StaticIndex(std::move(StaticData.first),
+                       std::move(StaticData.second), RelationSlab(),
+                       std::move(StaticFiles), std::move(StaticData),
+                       StaticSymbols.bytes() + StaticRefs.bytes());
+  MergedIndex Merge(&DynIndex, &StaticIndex);
+
+  auto ContainsFile = Merge.indexedFiles();
+  EXPECT_TRUE(ContainsFile("unittest:///foo.cc"));
+  EXPECT_TRUE(ContainsFile("unittest:///bar.cc"));
+  EXPECT_FALSE(ContainsFile("unittest:///foobar.cc"));
+}
+
 TEST(MergeIndexTest, NonDocumentation) {
   using index::SymbolKind;
   Symbol L, R;
   L.ID = R.ID = SymbolID("x");
   L.Definition.FileURI = "file:/x.h";
   R.Documentation = "Forward declarations because x.h is too big to include";
   for (auto ClassLikeKind :
        {SymbolKind::Class, SymbolKind::Struct, SymbolKind::Union}) {

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

class PaginationIndex : public SymbolIndex {
     }
     void
     lookup(const LookupRequest &Req,
            llvm::function_ref<void(const Symbol &)> Callback) const override {}
 
     void relations(const RelationsRequest &Req,
                    llvm::function_ref<void(const SymbolID &, const Symbol &)>
                        Callback) const override {}
+
+    llvm::unique_function<bool(llvm::StringRef) const>
+    indexedFiles() const override {
+      return [](llvm::StringRef) { return false; };
+    }
+
     size_t estimateMemoryUsage() const override { return 0; }
   } PIndex;
   Results = rename({MainCode.point(),
                     NewName,
                     AST,
                     MainFilePath,
                     &PIndex,
                     {/*CrossFile=*/true},
bool fuzzyFind(const FuzzyFindRequest &,
       return false;
     }
     void lookup(const LookupRequest &,
                 llvm::function_ref<void(const Symbol &)>) const override {}
 
     void relations(const RelationsRequest &,
                    llvm::function_ref<void(const SymbolID &, const Symbol &)>)
         const override {}
+
+    llvm::unique_function<bool(llvm::StringRef) const>
+    indexedFiles() const override {
+      return [](llvm::StringRef) { return false; };
+    }
+
     size_t estimateMemoryUsage() const override { return 0; }
     Ref ReturnedRef;
   } DIndex(XRefInBarCC);
   llvm::StringRef NewName = "newName";
   auto Results = rename({MainCode.point(),
                          NewName,
                          AST,
                          MainFilePath,

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

 /// /clangd-test/x.h.
 class TestScheme : public URIScheme {
 public:
   static const char *Scheme;
 
   llvm::Expected<std::string>
   getAbsolutePath(llvm::StringRef /*Authority*/, llvm::StringRef Body,
                   llvm::StringRef HintPath) const override {
-    if (!HintPath.startswith(testRoot()))
-      return error("Hint path doesn't start with test root: {0}", HintPath);
+    if (!HintPath.empty() && !HintPath.startswith(testRoot()))
+      return error("Hint path is not empty and doesn't start with {0}: {1}",
+                   testRoot(), HintPath);
     if (!Body.consume_front("/"))
       return error("Body of an unittest: URI must start with '/'");
     llvm::SmallString<16> Path(Body.begin(), Body.end());
     llvm::sys::path::native(Path);
     return testPath(Path);
   }
 
   llvm::Expected<URI>