[clangd] Introduce loading of shards within auto-index

[kadircet]

Summary

Whenever a change happens on a CDB, load shards associated with that
CDB before issuing re-index actions.

[kadircet]

• Fix a few problems that come up in the field test.

[ilya-biryukov]

Probably the most important suggestion from my side is trying to clearly separate the enqueue calls (which actually schedule rebuilds of TUs) using clang and the loadShards function.
The index loading should be fast, so I assume we won't win much latency by scheduling the indexing actions in the middle of the shard-loading.
OTOH, separating those two concerns should make the code way more readable (I think, at least).

The concrete proposal is to make loadShards actually only the shards and return a list of TUs that still need to be rebuilt. As the second step, we can enqueue the rebuild of those TUs.

Another important thing that's worth doing is documenting the correctness trade-offs we have in the current model, i.e. when following the include edges of a file (say, foo.h) that had its digest changed, we can potentially:

1. load stale symbols for some other file (say, bar.h) previously included by it,
2. never update those symbols to fresh ones if the include edge was dropped, i.e. foo.h does not include bar.h anymore.

The described situation can lead to stale symbols for bar.h being kept indefinitely in some cases, but has the advantage of reparsing less TUs when rebuilding the index. Overall it's definitely fine to have this trade-off for the time-being, but would be nice if we could document it.

The rest is mostly NITs and code style comments.

And thanks for the change, it's an impressive piece of work!

clangd/SourceCode.h

96 ↗

(On Diff #177005)

We might want to have a guidance on when this function should be used, similar to getRealPath. Also mention why it's different from the above.

My understanding is that it's only used for canonicalizing the file path for storing them in the index and nowhere else.
Should we discourage usages outside the index? Maybe we can give a more obscure name for this purpose, e.g. canonicalizeForIndex or similar?

107 ↗

(On Diff #177005)

NIT: maybe name it canonicalizePath? A bit shorter. But up to you

107 ↗

(On Diff #177005)

Maybe put this function right after getRealPath? They both "canonicalize" paths, so it makes sense for them to live together.

clangd/index/Background.cpp

92

Why not vfs->makeAbsolute instead of this function? Maybe worth a comment?

237

Ah, it feels we should move this into a helper function and reuse everywhere.
It's a small detail, but it's so easy to forget about it...

Just complaining, no need to do anything about it...

320

"should be rare in practice"

And yet, can we avoid this altogether?

Also, I believe it won't be rare. When processing multiple different TUs, we can easily run into the same header multiple times, possibly with the different contents.
E.g. imagine the index for the whole of clang is being built and the user is editing Sema.h at the same time. We'll definitely be running into this case over and over again.

351–352

Does it make sense for it to be part of makeCanonicalPath?
Both call sites call vfs->getAbsolutePath before calling the function?

386

This looks like an important optimization. Did we move it to some other place? Why should we remove it?

414

The comment does not mention why should we update it. Is it because of the dependencies?

434

Was this error possible before this change too?

446

This log is not getting called more often after this change, right?
Could you send the log -> vlog replacement as a separate patch to keep this change more focused?

463

NIT: s/io/IO
NIT: s/AbsolutePaths/absolute paths (otherwise looks like we're referring to a local variable or a field with this name)

465

We used to shuffle the ChangedFiles before processing them. I believe the reason for doing that are still relevant. Should we restore this? (Or are we doing it somewhere else now and I missed it?)

clangd/index/Background.h

120

Could you elaborate what are the "sources and headers of the Cmd"? The compile command is typically created for a single source file, so this comment looks a bit confusing.

123

Consider creating a simple struct for this pair. The named field access is much more readable than .first and .second

126

Should this be named VisitedShards?

[ilya-biryukov]

clangd/index/Background.cpp

466

NIT: maybe rename to AddShardToIndex or AddShard? LoadShard is too similar to IndexStorage::loadShard, which confused me a little when going through the code for the first time.

471

Maybe return a vector<string> with dependencies that need reindexing? We ignore the dependencies that don't need to be reindexed anyway.

474

NIT: s/more smartly/smarter

477

What is Dependency.second and Dependency.first? Maybe use a named struct instead of a pair here or deconstruct into named variables?

482

Maybe use range-based-for instead? Looks simpler:

for (auto Dep : Dependencies)
  BeingReindexed.insert(Dep.first);

535

maybe log the error? would be nice to somehow recover too, but not sure what we can do here.

clangd/index/BackgroundIndexStorage.cpp

80 ↗

(On Diff #177005)

NIT: maybe send in as a separate patch to keep this more focused? (No need to send for review, just commit it)

[kadircet]

Sending out everything related to canonical path at: D55818

[kadircet]

• Address comments

[kadircet]

clangd/index/Background.cpp

320

Well I am open to ideas, but currently there is no way of knowing whether this is the newer version for the file. Because only information we have is the digest is different than what we currently have and this doesn't yield any chronological information.

386

We kind of moved it into loadShards logic by not running indexing for same file multiple times. I needed to delete this check since we might wanna run indexing on a TU, even if it is up-to-date, to get new symbols coming from one of it's includes.

414

Nice catch, that was the case in one of my experiments but currently during the update we store shards for every source file that exists in include graph even if it has no symbols&refs. So it is no longer necessary.

434

Yes and it got fixed by D55650, just deleting the check it will arrive once I rebase.

471

Yes we ignore them for now, but they might change in one of the consecutive checks. And if that happens we don't need to schedule another TU for re-indexing that dependency, since we mark it as already indexed.

535

Well, if this happens we don't have access to file's contents for some reason. I don't think we can do anything. We might actually want to skip loading these files into index, since they are most likely gone and symbols coming from them won't be accessible. WDYT?

[ilya-biryukov]

Most comments are NITs, the major one that I'd suggest paying most attention to is about rewriting newer results with an older ones.

clangd/index/Background.cpp

311

This means lock/unlock on every iteration of the loop.
Could we move collecting the files we need to process into a separate loop that would only require a single lock over the whole loop?

320

Do we know which request is "newer" when scheduling it?
If so, we could keep the map of the latest hashes of the files we've seen (in addition to the IndexedFileDigests, which correspond to the digest for which we built the index IIUC).

This would give us a simple invariant of the final state we want to bring the index to: IndexedFileDigests should correspond to the latest hashes seen so far. If not, we have to rebuild the index for the corresponding files. That, in turn, gives us a way to resolve conflicts: we should never replace with symbols built for the latest version (hash) of the file we've seen.

Would that work?

386

Thanks for the explanation, removing the optimization makes sense, we should check for dependency hashes in addition to the original file now.

457

NIT: s/enqueues an indexing operation/add to a list of files requiring reindexing
(or any other wording with the same meaning, the important part is that it does not enqueue any indexing operations anymore)

463

NIT: s/VisitedShards/LoadedShards?
To better align with the name of the local var used in loadShards()

464

Now that we don't actually schedule the indexing, maybe rename this to something like FilesToIndex? The current name suggests there's some processing on the files going somewhere in the background, which is not the case.

465

NIT: Instead of writing this comment, we could accept IndexFileIn && as a parameter, which clearly states we're consuming it (this would require handling the nullptr case in the call sites, but that should be ok).

474

NIT: maybe init at the declaration site? i.e. unique_ptr<Slab> SS = Shared->Symbols ? llvm::make_unique<>() : nullptr;
Same for RS.

479

NIT: use early exits to reduce nesting.

if (!Dependency.NeedsReIndexing || BeingReindexed.count(...))
  continue;
...

481

Maybe be a bit more verbose in the message to clearly state which file is a dependency? Something like Enqueuing TU {0} because its dependency {1} needs re-indexing.

483

Would it make sense to collect all symbols into a local variable and only update under a lock once the whole loading process is finished?
I guess that means ~the same memory requirements, but much less locks and unlocks.

517

Should we mark the file as requiring re-indexing at this point?
Not sure how that might happen in practice, but still...

522

NIT: use early exits to reduce nesting. See LLVM Style Guide.

auto U = URI::parse(...);
if (!U) 
  continue;
auto AbsolutePath = URI::resolve(...);
if (!AbsolutePath)
  continue;
...

524

Why do we need an extra check for self-edges here? Shouldn't InQueue.try_emplace handle this too?

535

Logging the error is enough, thanks!

I think the ideal recovery is tracking whenever the files we were missing were added to the filesystem and rebuilding the index when that happens.
That probably requires more work than we'd like to put into it, though, so I don't think investing in this now makes any sense.

clangd/index/Background.h

122

NIT: Provide the default value to avoid UB on uninitialized values.

124

NIT: all the sources that was touched by this Cmd is a bit confusing (e.g. what does "touched by compile command" mean?) Maybe rephrase to something like Loads the shards for a single TU and all of its dependencies

133

Maybe return Expected<vector<..>> instead of using an out parameter?

[kadircet]

Address comments

clangd/index/Background.cpp

320

I am not sure if it would work for non-main files. We update the Hash for the main files at each indexing action, so we can safely keep track of the latest versions. But we collect hashes for dependencies while performing the indexing which happens in parallel. Therefore an indexing action triggered earlier might get an up-to-date version of a dependency than an action triggered later-on.

517

All files are marked as requiring re-indexing by default Dependencies.push_back({AbsolutePath, true}). The second element is always true, and we only mark it as false if we are sure file is up-to-date.

524

It is not looking for a self-edge. It is trying to find source information related to current file(which contains symbols, refs and hash). The nesting seems to be confusing it was just to prevent one redundant try_emplace seems like making the code less readable taking it out.

clangd/index/Background.h

120

It seems like comment become out-dated marking as done.

133

Actually this function can no longer fail, therefore directly returning the vector

[ilya-biryukov]

clangd/index/Background.cpp

320

If updates for each TU are atomic (i.e. all files included in the TU are updated in a single go) we would get the up-to-date index eventually, assuming we rebuild the index when TU dependencies change (we don't schedule rebuilds on changes to included header now, but we're planning to do so at some point).

517

My confusion is coming from the fact that I'm constantly forgetting that we return the queue we're processing afterwards.
Could you put a small comment that file will be returned to the caller as requiring a reindex here?

[ilya-biryukov]

clangd/SourceCode.h

107 ↗

(On Diff #180706)

This changes should go away after the rebase, right?
Could you please run the rebase to make sure the patch is in its final state.

[ilya-biryukov]

clangd/index/Background.cpp

238

use llvm::StringRef

314

I now see that my previous comment about lock/unlock for each file was wrong in the first place.
It feels that's we'd better keep the IndexedFileDigests and IndexedSymbols in sync.

Why don't we update the digest in the next loop that actually updates the symbols?

clangd/index/Background.h

123

NIT: maybe remove the constructor? plain structs can easily be initialized with init lists and adding a constructor forbids per-field assignment, which is a bit nicer in some cases.
Not very important, since it's a private API, but still.

[kadircet]

Address comments && rebase

[kadircet]

There seems to be no unexpected changes after rebase

clangd/index/Background.cpp

238

If the command fails we want to show the filename but we are moving the Cmd, so we need to keep a copy of the filename.

320

Sure, that assumption seems more relaxed than the previous one, just wanna make sure I got it right:
Your suggested solution assumes: Dependencies of a TU won't change during indexing of that TU
Whereas the previous assumption was: Files won't change between close indexing actions

clangd/index/Background.h

123

Once I assign a default value for NeedsReIndexing, I cannot construct Source objects with init lists, therefore I've added a constructor instead.

[ilya-biryukov]

clangd/SourceCode.h

21 ↗

(On Diff #180823)

Looks redundant. Remove?

clangd/index/Background.cpp

238

Ah, we're moving out of Cmd here... I'd say index should accept a const CompileCommand&? If the goal was to optimize for less copies, then we failed - now we need to copy the filename string. index() is not part of this patch, though, so let's not change it.

Could you add a comment that we can't use StringRef because we move from Cmd? It's easy to miss.

313

We still update digests and symbols non-atomically in that case. Could we do both under the same lock, similar to how it's done in loadShards?

320

Exactly. The idea is that eventually we'll start tracking changes and will be able to detect even those cases and rebuild the index accordingly. Just trying to keep us from drifting away from that model too much.

files won't change between close indexing actions

This assumption worked fine for indexing actions running right away, but I think the situation with loading shards is different: the shards we are loading might be old and if we don't want a stale shard (which might be arbitrarily old) to overwrite results of the fresh indexing action. Let me know if I'm missing something here.

clangd/index/Background.h

123

Right, makes sense. You could initialize explicitly, but I can see how constructor might be simpler to use in that particular use-case.
Since we now have a constructor, could you remove the default arg? It's not possible to get an undefined value for NeedsReindexing with a constructor.

[kadircet]

Address comments

clangd/index/Background.cpp

313

Moved update to the end of the loop, but now we might perform unnecessary work for building {symbol,ref}slabs for files that are already up-to-date. It shouldn't be too much of an issue, as a solution we can lock at the entrance and only check if the file was up-to-date, than we update at the exit. Or we can keep a snapshot.

320

Nope, your point seems to be correct

[ilya-biryukov]

clangd/URI.h

131 ↗

(On Diff #180859)

Maybe move it into the Backgroud.cpp, e.g. as a private member of BackoundIndex?
We don't have other use-case for it to the date and it doesn't really good like a good public API at this point, i.e. lacking docs on what it does and why it's useful, which are useful if we move it into a public header.

clangd/index/Background.cpp

313

LG, thanks. I don't think this extra work should pop up in the profiler, so we're good.

341

NIT: s/we this/this/

342

An alternative strategy is to also update if the IndexedFileDigests does not contain a value.
That would ensure we populate some version of all files as fast as possible, but only update for the latest version. To me personally this looks like a reasonable right trade-off (and would require updating just a few lines of code)

349

This might be too verbose even for vlog(), i.e. this would produce thousands of messages for each TU. Maybe omit it?

452

I believe we want to avoid updating the digests for the dependencies if the digest for the main file has changed in the meantime.
Otherwise, we might record the stale versions of the dependency digests for the rest of the index lifetime.

Note that this might invalidate the assertion in update() that checks all files have digests.

600

Didn't we land the periodic rebuilds? Should this be obsolete now?

clangd/index/Background.h

117

NIT: maybe add a comment that we use this to decide which of the concurrently running indexing operations should take precedence?

clangd/index/SymbolCollector.cpp

213 ↗

(On Diff #180859)

NIT: look unrelated, maybe land as a separate NFC commit right away?
Not a big deal, though, feel free to ignore

[ilya-biryukov]

As discussed offline, let's remove the parts of the change that were aiming to fix the consistency issues, the issues were there before this patch, the fix is getting complicated and doesn't really solve all of the problems. All of that suggests it's out of scope for this change.

[kadircet]

Address comments & revert last changes

[ilya-biryukov]

Only one important comment about bringing back the comment.

clangd/index/Background.cpp

224

a typo: s/that needs/that need/

344

Let's bring back the comment about rewriting the newer version.

[kadircet]

Address comments

[ilya-biryukov]

LGTM. Ship it!

clangd/index/Background.h

BackgroundIndex(Context BackgroundContext, llvm::StringRef ResourceDir,
                   size_t BuildIndexPeriodMs = 0,
                   size_t ThreadPoolSize = llvm::hardware_concurrency());
   ~BackgroundIndex(); // Blocks while the current task finishes.
 
   // Enqueue translation units for indexing.
   // The indexing happens in a background thread, so the symbols will be
   // available sometime later.
   void enqueue(const std::vector<std::string> &ChangedFiles);
-  void enqueue(const std::string &File);
 
   // Cause background threads to stop after ther current task, any remaining
   // tasks will be discarded.
   void stop();
 
   // Wait until the queue is empty, to allow deterministic testing.
   LLVM_NODISCARD bool
   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10);
private:
   void buildIndex(); // Rebuild index periodically every BuildIndexPeriodMs.
   const size_t BuildIndexPeriodMs;
   std::atomic<bool> SymbolsUpdatedSinceLastIndex;
   std::mutex IndexMu;
   std::condition_variable IndexCV;
 
   FileSymbols IndexedSymbols;
   llvm::StringMap<FileDigest> IndexedFileDigests; // Key is absolute file path.
   std::mutex DigestsMu;
 
   BackgroundIndexStorage::Factory IndexStorageFactory;
+  struct Source {
+    std::string Path;
+    bool NeedsReIndexing;
+    Source(llvm::StringRef Path, bool NeedsReIndexing)
+        : Path(Path), NeedsReIndexing(NeedsReIndexing) {}
+  };
+  // Loads the shards for a single TU and all of its dependencies. Returns the
+  // list of sources and whether they need to be re-indexed.
+  std::vector<Source> loadShard(const tooling::CompileCommand &Cmd,
+                                BackgroundIndexStorage *IndexStorage,
+                                llvm::StringSet<> &LoadedShards);
+  // Tries to load shards for the ChangedFiles.
+  std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>>
+  loadShards(std::vector<std::string> ChangedFiles);
+  void enqueue(tooling::CompileCommand Cmd, BackgroundIndexStorage *Storage);
 
   // queue management
   using Task = std::function<void()>;
   void run(); // Main loop executed by Thread. Runs tasks from Queue.
   void enqueueTask(Task T, ThreadPriority Prioirty);
   void enqueueLocked(tooling::CompileCommand Cmd,
                      BackgroundIndexStorage *IndexStorage);
   std::mutex QueueMu;

clangd/index/Background.cpp

for (auto &Include : Node.DirectIncludes) {
     auto I = IG.try_emplace(Include).first;
     I->getValue().URI = I->getKey();
     Include = I->getKey();
   }
 
   return IG;
 }
 
 // Creates a filter to not collect index results from files with unchanged
 // digests.
 // \p FileDigests contains file digests for the current indexed files, and all
 // changed files will be added to \p FilesToUpdate.
 decltype(SymbolCollector::Options::FileFilter)
 createFileFilter(const llvm::StringMap<FileDigest> &FileDigests,
                  llvm::StringMap<FileDigest> &FilesToUpdate) {
   return [&FileDigests, &FilesToUpdate](const SourceManager &SM, FileID FID) {
     const auto *F = SM.getFileEntryForID(FID);
return [&FileDigests, &FilesToUpdate](const SourceManager &SM, FileID FID) {
     if (D != FileDigests.end() && D->second == Digest)
       return false; // Skip files that haven't changed.
 
     FilesToUpdate[*AbsPath] = *Digest;
     return true;
   };
 }
 
+// We cannot use vfs->makeAbsolute because Cmd.FileName is either absolute or
+// relative to Cmd.Directory, which might not be the same as current working
+// directory.
+llvm::SmallString<128> getAbsolutePath(const tooling::CompileCommand &Cmd) {
+  llvm::SmallString<128> AbsolutePath;
+  if (llvm::sys::path::is_absolute(Cmd.Filename)) {
+    AbsolutePath = Cmd.Filename;
+  } else {
+    AbsolutePath = Cmd.Directory;
+    llvm::sys::path::append(AbsolutePath, Cmd.Filename);
+  }
+  return AbsolutePath;
+}
 } // namespace
 
 BackgroundIndex::BackgroundIndex(
     Context BackgroundContext, llvm::StringRef ResourceDir,
     const FileSystemProvider &FSProvider, const GlobalCompilationDatabase &CDB,
     BackgroundIndexStorage::Factory IndexStorageFactory,
     size_t BuildIndexPeriodMs, size_t ThreadPoolSize)
     : SwapIndex(llvm::make_unique<MemIndex>()), ResourceDir(ResourceDir),
return wait(Lock, QueueCV, timeoutSeconds(TimeoutSeconds),
               [&] { return Queue.empty() && NumActiveTasks == 0; });
 }
 
 void BackgroundIndex::enqueue(const std::vector<std::string> &ChangedFiles) {
   enqueueTask(
       [this, ChangedFiles] {
         trace::Span Tracer("BackgroundIndexEnqueue");
         // We're doing this asynchronously, because we'll read shards here too.
-        // FIXME: read shards here too.
-
         log("Enqueueing {0} commands for indexing", ChangedFiles.size());
         SPAN_ATTACH(Tracer, "files", int64_t(ChangedFiles.size()));
 
-        // We shuffle the files because processing them in a random order should
-        // quickly give us good coverage of headers in the project.
-        std::vector<unsigned> Permutation(ChangedFiles.size());
-        std::iota(Permutation.begin(), Permutation.end(), 0);
-        std::mt19937 Generator(std::random_device{}());
-        std::shuffle(Permutation.begin(), Permutation.end(), Generator);
-
-        for (const unsigned I : Permutation)
-          enqueue(ChangedFiles[I]);
+        auto NeedsReIndexing = loadShards(std::move(ChangedFiles));
+        // Run indexing for files that need to be updated.
+        std::shuffle(NeedsReIndexing.begin(), NeedsReIndexing.end(),
+                     std::mt19937(std::random_device{}()));
+        for (auto &Elem : NeedsReIndexing)
+          enqueue(std::move(Elem.first), Elem.second);
       },
       ThreadPriority::Normal);
 }
 
-void BackgroundIndex::enqueue(const std::string &File) {
-  ProjectInfo Project;
-  if (auto Cmd = CDB.getCompileCommand(File, &Project)) {
-    auto *Storage = IndexStorageFactory(Project.SourceRoot);
-    // Set priority to low, since background indexing is a long running
-    // task we do not want to eat up cpu when there are any other high
-    // priority threads.
-    enqueueTask(Bind(
-                    [this, File, Storage](tooling::CompileCommand Cmd) {
-                      Cmd.CommandLine.push_back("-resource-dir=" + ResourceDir);
-                      if (auto Error = index(std::move(Cmd), Storage))
-                        log("Indexing {0} failed: {1}", File, std::move(Error));
-                    },
-                    std::move(*Cmd)),
-                ThreadPriority::Low);
-  }
-}
+void BackgroundIndex::enqueue(tooling::CompileCommand Cmd,
+                              BackgroundIndexStorage *Storage) {
+                  [this, Storage](tooling::CompileCommand Cmd) {
+                    // We can't use llvm::StringRef here since we are going to
+                    // move from Cmd during the call below.
+                    const std::string FileName = Cmd.Filename;
+                      elog("Indexing {0} failed: {1}", FileName,
+                           std::move(Error));
+                  std::move(Cmd)),
 
 void BackgroundIndex::enqueueTask(Task T, ThreadPriority Priority) {
   {
     std::lock_guard<std::mutex> Lock(QueueMu);
     auto I = Queue.end();
     // We first store the tasks with Normal priority in the front of the queue.
     // Then we store low priority tasks. Normal priority tasks are pretty rare,
     // they should not grow beyond single-digit numbers, so it is OK to do
for (const auto &R : SymRefs.second) {
         auto &F = Files[Path];
         RefToIDs[&R] = SymRefs.first;
         F.Refs.insert(&R);
       }
     }
   }
 
   // Build and store new slabs for each updated file.
-  for (const auto &F : Files) {
-    llvm::StringRef Path = F.first();
-    vlog("Update symbols in {0}", Path);
+  for (const auto &I : *Index.Sources) {
+    std::string Path = URICache.resolve(I.first());
     SymbolSlab::Builder Syms;
     RefSlab::Builder Refs;
+    auto FileIt = Files.find(Path);
+    if (FileIt != Files.end()) {
+      auto &F = *FileIt;
       for (const auto *S : F.second.Symbols)
         Syms.insert(*S);
       for (const auto *R : F.second.Refs)
         Refs.insert(RefToIDs[R], *R);
-
+    }
     auto SS = llvm::make_unique<SymbolSlab>(std::move(Syms).build());
     auto RS = llvm::make_unique<RefSlab>(std::move(Refs).build());
     auto IG = llvm::make_unique<IncludeGraph>(
         getSubGraph(URI::create(Path), Index.Sources.getValue()));
-
-    auto Hash = FilesToUpdate.lookup(Path);
     // We need to store shards before updating the index, since the latter
     // consumes slabs.
     if (IndexStorage) {
       IndexFileOut Shard;
       Shard.Symbols = SS.get();
       Shard.Refs = RS.get();
       Shard.Sources = IG.get();
 
       if (auto Error = IndexStorage->storeShard(Path, Shard))
         elog("Failed to write background-index shard for file {0}: {1}", Path,
              std::move(Error));
     }
-
+    {
       std::lock_guard<std::mutex> Lock(DigestsMu);
-    // This can override a newer version that is added in another thread,
-    // if this thread sees the older version but finishes later. This should be
+      auto Hash = I.second.Digest;
+      // Skip if file is already up to date.
+      auto DigestIt = IndexedFileDigests.try_emplace(Path);
+      if (!DigestIt.second && DigestIt.first->second == Hash)
+        continue;
+      DigestIt.first->second = Hash;
+      // This can override a newer version that is added in another thread, if
+      // this thread sees the older version but finishes later. This should be
       // rare in practice.
-    IndexedFileDigests[Path] = Hash;
       IndexedSymbols.update(Path, std::move(SS), std::move(RS));
     }
   }
+}
 
 void BackgroundIndex::buildIndex() {
   assert(BuildIndexPeriodMs > 0);
   while (true) {
     {
       std::unique_lock<std::mutex> Lock(IndexMu);
-      if (ShouldStop)  // Avoid waiting if stopped.
+      if (ShouldStop) // Avoid waiting if stopped.
         break;
       // Wait until this is notified to stop or `BuildIndexPeriodMs` has past.
       IndexCV.wait_for(Lock, std::chrono::milliseconds(BuildIndexPeriodMs));
-      if (ShouldStop)  // Avoid rebuilding index if stopped.
+      if (ShouldStop) // Avoid rebuilding index if stopped.
         break;
     }
     if (!SymbolsUpdatedSinceLastIndex.exchange(false))
       continue;
     // There can be symbol update right after the flag is reset above and before
     // index is rebuilt below. The new index would contain the updated symbols
     // but the flag would still be true. This is fine as we would simply run an
     // extra index build.
     reset(
         IndexedSymbols.buildIndex(IndexType::Heavy, DuplicateHandling::Merge));
     log("BackgroundIndex: rebuilt symbol index.");
   }
 }
 
 llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd,
                                    BackgroundIndexStorage *IndexStorage) {
   trace::Span Tracer("BackgroundIndex");
   SPAN_ATTACH(Tracer, "file", Cmd.Filename);
-  llvm::SmallString<128> AbsolutePath;
-  if (llvm::sys::path::is_absolute(Cmd.Filename)) {
-    AbsolutePath = Cmd.Filename;
-  } else {
-    AbsolutePath = Cmd.Directory;
-    llvm::sys::path::append(AbsolutePath, Cmd.Filename);
-  }
+  auto AbsolutePath = getAbsolutePath(Cmd);
 
   auto FS = FSProvider.getFileSystem();
   auto Buf = FS->getBufferForFile(AbsolutePath);
   if (!Buf)
     return llvm::errorCodeToError(Buf.getError());
   auto Hash = digest(Buf->get()->getBuffer());
 
   // Take a snapshot of the digests to avoid locking for each file in the TU.
   llvm::StringMap<FileDigest> DigestsSnapshot;
   {
     std::lock_guard<std::mutex> Lock(DigestsMu);
-    if (IndexedFileDigests.lookup(AbsolutePath) == Hash) {
-      vlog("No need to index {0}, already up to date", AbsolutePath);
-      return llvm::Error::success();
-    }
-
     DigestsSnapshot = IndexedFileDigests;
   }
 
   log("Indexing {0} (digest:={1})", Cmd.Filename, llvm::toHex(Hash));
   ParseInputs Inputs;
   Inputs.FS = std::move(FS);
   Inputs.FS->setCurrentWorkingDirectory(Cmd.Directory);
   Inputs.CompileCommand = std::move(Cmd);
   auto CI = buildCompilerInvocation(Inputs);
   if (!CI)
     return llvm::createStringError(llvm::inconvertibleErrorCode(),
                                    "Couldn't build compiler invocation");
   IgnoreDiagnostics IgnoreDiags;
   auto Clang = prepareCompilerInstance(
       std::move(CI), /*Preamble=*/nullptr, std::move(*Buf),
       std::make_shared<PCHContainerOperations>(), Inputs.FS, IgnoreDiags);
   if (!Clang)
     return llvm::createStringError(llvm::inconvertibleErrorCode(),
                                    "Couldn't build compiler instance");
 
   SymbolCollector::Options IndexOpts;
   llvm::StringMap<FileDigest> FilesToUpdate;
   IndexOpts.FileFilter = createFileFilter(DigestsSnapshot, FilesToUpdate);
   IndexFileIn Index;
   auto Action = createStaticIndexingAction(
       IndexOpts, [&](SymbolSlab S) { Index.Symbols = std::move(S); },
       [&](RefSlab R) { Index.Refs = std::move(R); },
       [&](IncludeGraph IG) { Index.Sources = std::move(IG); });
 
   // We're going to run clang here, and it could potentially crash.
   // We could use CrashRecoveryContext to try to make indexing crashes nonfatal,
   // but the leaky "recovery" is pretty scary too in a long-running process.
   // If crashes are a real problem, maybe we should fork a child process.
 
   const FrontendInputFile &Input = Clang->getFrontendOpts().Inputs.front();
   if (!Action->BeginSourceFile(*Clang, Input))
     return llvm::createStringError(llvm::inconvertibleErrorCode(),
                                    "BeginSourceFile() failed");
   if (!Action->Execute())
     return llvm::createStringError(llvm::inconvertibleErrorCode(),
                                    "Execute() failed");
   Action->EndSourceFile();
   if (Clang->hasDiagnostics() &&
       Clang->getDiagnostics().hasUncompilableErrorOccurred()) {
     return llvm::createStringError(
         llvm::inconvertibleErrorCode(),
         "IndexingAction failed: has uncompilable errors");
   }
 
-  assert(Index.Symbols && Index.Refs && Index.Sources
-     && "Symbols, Refs and Sources must be set.");
+  assert(Index.Symbols && Index.Refs && Index.Sources &&
+         "Symbols, Refs and Sources must be set.");
 
   log("Indexed {0} ({1} symbols, {2} refs, {3} files)",
       Inputs.CompileCommand.Filename, Index.Symbols->size(),
       Index.Refs->numRefs(), Index.Sources->size());
   SPAN_ATTACH(Tracer, "symbols", int(Index.Symbols->size()));
   SPAN_ATTACH(Tracer, "refs", int(Index.Refs->numRefs()));
   SPAN_ATTACH(Tracer, "sources", int(Index.Sources->size()));
 
   update(AbsolutePath, std::move(Index), FilesToUpdate, IndexStorage);
-  {
-    // Make sure hash for the main file is always updated even if there is no
-    // index data in it.
-    std::lock_guard<std::mutex> Lock(DigestsMu);
-    IndexedFileDigests[AbsolutePath] = Hash;
-  }
 
   if (BuildIndexPeriodMs > 0)
     SymbolsUpdatedSinceLastIndex = true;
   else
     reset(
         IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge));
 
   return llvm::Error::success();
 }
 
+std::vector<BackgroundIndex::Source>
+BackgroundIndex::loadShard(const tooling::CompileCommand &Cmd,
+                           BackgroundIndexStorage *IndexStorage,
+                           llvm::StringSet<> &LoadedShards) {
+  struct ShardInfo {
+    std::string AbsolutePath;
+    std::unique_ptr<IndexFileIn> Shard;
+    FileDigest Digest;
+  };
+  std::vector<ShardInfo> IntermediateSymbols;
+  // Make sure we don't have duplicate elements in the queue. Keys are absolute
+  // paths.
+  llvm::StringSet<> InQueue;
+  auto FS = FSProvider.getFileSystem();
+  // Dependencies of this TU, paired with the information about whether they
+  // need to be re-indexed or not.
+  std::vector<Source> Dependencies;
+  std::string AbsolutePath = getAbsolutePath(Cmd).str();
+  // Up until we load the shard related to a dependency it needs to be
+  // re-indexed.
+  Dependencies.emplace_back(AbsolutePath, true);
+  InQueue.insert(AbsolutePath);
+  // Goes over each dependency.
+  for (size_t CurrentDependency = 0; CurrentDependency < Dependencies.size();
+       CurrentDependency++) {
+    llvm::StringRef CurDependencyPath = Dependencies[CurrentDependency].Path;
+    // If we have already seen this shard before(either loaded or failed) don't
+    // re-try again. Since the information in the shard won't change from one TU
+    // to another.
+    if (!LoadedShards.try_emplace(CurDependencyPath).second) {
+      // If the dependency needs to be re-indexed, first occurence would already
+      // have detected that, so we don't need to issue it again.
+      Dependencies[CurrentDependency].NeedsReIndexing = false;
+      continue;
+    }
+
+    auto Shard = IndexStorage->loadShard(CurDependencyPath);
+    if (!Shard || !Shard->Sources) {
+      // File will be returned as requiring re-indexing to caller.
+      vlog("Failed to load shard: {0}", CurDependencyPath);
+      continue;
+    }
+    // These are the edges in the include graph for current dependency.
+    for (const auto &I : *Shard->Sources) {
+      auto U = URI::parse(I.getKey());
+      if (!U)
+        continue;
+      auto AbsolutePath = URI::resolve(*U, CurDependencyPath);
+      if (!AbsolutePath)
+        continue;
+      // Add file as dependency if haven't seen before.
+      if (InQueue.try_emplace(*AbsolutePath).second)
+        Dependencies.emplace_back(*AbsolutePath, true);
+      // The node contains symbol information only for current file, the rest is
+      // just edges.
+      if (*AbsolutePath != CurDependencyPath)
+        continue;
+
+      // We found source file info for current dependency.
+      assert(I.getValue().Digest != FileDigest{{0}} && "Digest is empty?");
+      ShardInfo SI;
+      SI.AbsolutePath = CurDependencyPath;
+      SI.Shard = std::move(Shard);
+      SI.Digest = I.getValue().Digest;
+      IntermediateSymbols.push_back(std::move(SI));
+      // Check if the source needs re-indexing.
+      // Get the digest, skip it if file doesn't exist.
+      auto Buf = FS->getBufferForFile(CurDependencyPath);
+      if (!Buf) {
+        elog("Couldn't get buffer for file: {0}: {1}", CurDependencyPath,
+             Buf.getError().message());
+        continue;
+      }
+      // If digests match then dependency doesn't need re-indexing.
+      Dependencies[CurrentDependency].NeedsReIndexing =
+          digest(Buf->get()->getBuffer()) != I.getValue().Digest;
+    }
+  }
+  // Load shard information into background-index.
+  {
+    std::lock_guard<std::mutex> Lock(DigestsMu);
+    // This can override a newer version that is added in another thread,
+    // if this thread sees the older version but finishes later. This
+    // should be rare in practice.
+    for (const ShardInfo &SI : IntermediateSymbols) {
+      auto SS =
+          SI.Shard->Symbols
+              ? llvm::make_unique<SymbolSlab>(std::move(*SI.Shard->Symbols))
+              : nullptr;
+      auto RS = SI.Shard->Refs
+                    ? llvm::make_unique<RefSlab>(std::move(*SI.Shard->Refs))
+                    : nullptr;
+      IndexedFileDigests[SI.AbsolutePath] = SI.Digest;
+      IndexedSymbols.update(SI.AbsolutePath, std::move(SS), std::move(RS));
+    }
+  }
+
+  return Dependencies;
+}
+
+// Goes over each changed file and loads them from index. Returns the list of
+// TUs that had out-of-date/no shards.
+std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>>
+BackgroundIndex::loadShards(std::vector<std::string> ChangedFiles) {
+  std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>>
+      NeedsReIndexing;
+  // Keeps track of the files that will be reindexed, to make sure we won't
+  // re-index same dependencies more than once. Keys are AbsolutePaths.
+  llvm::StringSet<> FilesToIndex;
+  // Keeps track of the loaded shards to make sure we don't perform redundant
+  // disk IO. Keys are absolute paths.
+  llvm::StringSet<> LoadedShards;
+  for (const auto &File : ChangedFiles) {
+    ProjectInfo PI;
+    auto Cmd = CDB.getCompileCommand(File, &PI);
+    if (!Cmd)
+      continue;
+    BackgroundIndexStorage *IndexStorage = IndexStorageFactory(PI.SourceRoot);
+    auto Dependencies = loadShard(*Cmd, IndexStorage, LoadedShards);
+    for (const auto &Dependency : Dependencies) {
+      if (!Dependency.NeedsReIndexing || FilesToIndex.count(Dependency.Path))
+        continue;
+      // FIXME: Currently, we simply schedule indexing on a TU whenever any of
+      // its dependencies needs re-indexing. We might do it smarter by figuring
+      // out a minimal set of TUs that will cover all the stale dependencies.
+      vlog("Enqueueing TU {0} because its dependency {1} needs re-indexing.",
+           Cmd->Filename, Dependency.Path);
+      NeedsReIndexing.push_back({std::move(*Cmd), IndexStorage});
+      // Mark all of this TU's dependencies as to-be-indexed so that we won't
+      // try to re-index those.
+      for (const auto &Dependency : Dependencies)
+        FilesToIndex.insert(Dependency.Path);
+      break;
+    }
+  }
+  vlog("Loaded all shards");
+  reset(IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge));
+
+  return NeedsReIndexing;
+}
+
 } // namespace clangd
 } // namespace clang

test/clangd/background-index.test

 # foo() is declared in foo.h and defined in foo.cpp.
 # The background index should allow us to go-to-definition on foo().
 # RUN: clangd -background-index -background-index-rebuild-period=0 -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc
 
 # Test that the index is writing files in the expected location.
 # RUN: ls %t/.clangd-index/foo.cpp.*.idx
 
 # Test the index is read from disk: delete code and restart clangd.
-# FIXME: This test currently fails as we don't read the index yet.
 # RUN: rm %t/foo.cpp
-# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | not FileCheck %t/definition.jsonrpc
+# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc

unittests/clangd/BackgroundIndexTests.cpp

 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "index/Background.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/Threading.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <thread>
 
 using testing::_;
 using testing::AllOf;
+using testing::Contains;
 using testing::ElementsAre;
 using testing::Not;
 using testing::UnorderedElementsAre;
 
 namespace clang {
 namespace clangd {
 
 MATCHER_P(Named, N, "") { return arg.Name == N; }
TEST_F(BackgroundIndexTest, IndexTwoFiles) {
   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")}));
 }
 
-TEST_F(BackgroundIndexTest, ShardStorageWriteTest) {
+TEST_F(BackgroundIndexTest, ShardStorageTest) {
   MockFSProvider FS;
   FS.Files[testPath("root/A.h")] = R"cpp(
       void common();
       void f_b();
       class A_CC {};
       )cpp";
   std::string A_CC = "#include \"A.h\"\nvoid g() { (void)common; }";
   FS.Files[testPath("root/A.cc")] = A_CC;
// Check nothing is loaded from Storage, but A.cc and A.h has been stored.
     BackgroundIndex Idx(Context::empty(), "", FS, CDB,
                         [&](llvm::StringRef) { return &MSS; });
     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
     ASSERT_TRUE(Idx.blockUntilIdleForTest());
   }
   EXPECT_EQ(CacheHits, 0U);
   EXPECT_EQ(Storage.size(), 2U);
 
+  {
+    OverlayCDB CDB(/*Base=*/nullptr);
+    BackgroundIndex Idx(Context::empty(), "", FS, CDB,
+                        [&](llvm::StringRef) { return &MSS; });
+    CDB.setCompileCommand(testPath("root"), Cmd);
+    ASSERT_TRUE(Idx.blockUntilIdleForTest());
+  }
+  EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
+  EXPECT_EQ(Storage.size(), 2U);
+
   auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
   EXPECT_NE(ShardHeader, nullptr);
   EXPECT_THAT(
       *ShardHeader->Symbols,
       UnorderedElementsAre(Named("common"), Named("A_CC"),
                            AllOf(Named("f_b"), Declared(), Not(Defined()))));
   for (const auto &Ref : *ShardHeader->Refs)
     EXPECT_THAT(Ref.second,
TEST_F(BackgroundIndexTest, DISABLED_PeriodicalIndex) {
   CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 
   ASSERT_TRUE(Idx.blockUntilIdleForTest());
   EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("X")));
   std::this_thread::sleep_for(std::chrono::milliseconds(1000));
   EXPECT_THAT(runFuzzyFind(Idx, ""), ElementsAre(Named("Y")));
 }
 
+TEST_F(BackgroundIndexTest, ShardStorageLoad) {
+  MockFSProvider FS;
+  FS.Files[testPath("root/A.h")] = R"cpp(
+      void common();
+      void f_b();
+      class A_CC {};
+      )cpp";
+  FS.Files[testPath("root/A.cc")] =
+      "#include \"A.h\"\nvoid g() { (void)common; }";
+
+  llvm::StringMap<std::string> Storage;
+  size_t CacheHits = 0;
+  MemoryShardStorage MSS(Storage, CacheHits);
+
+  tooling::CompileCommand Cmd;
+  Cmd.Filename = testPath("root/A.cc");
+  Cmd.Directory = testPath("root");
+  Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
+  // Check nothing is loaded from Storage, but A.cc and A.h has been stored.
+  {
+    OverlayCDB CDB(/*Base=*/nullptr);
+    BackgroundIndex Idx(Context::empty(), "", FS, CDB,
+                        [&](llvm::StringRef) { return &MSS; });
+    CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
+    ASSERT_TRUE(Idx.blockUntilIdleForTest());
+  }
+
+  // Change header.
+  FS.Files[testPath("root/A.h")] = R"cpp(
+      void common();
+      void f_b();
+      class A_CC {};
+      class A_CCnew {};
+      )cpp";
+  {
+    OverlayCDB CDB(/*Base=*/nullptr);
+    BackgroundIndex Idx(Context::empty(), "", FS, CDB,
+                        [&](llvm::StringRef) { return &MSS; });
+    CDB.setCompileCommand(testPath("root"), Cmd);
+    ASSERT_TRUE(Idx.blockUntilIdleForTest());
+  }
+  EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
+
+  // Check if the new symbol has arrived.
+  auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
+  EXPECT_NE(ShardHeader, nullptr);
+  EXPECT_THAT(*ShardHeader->Symbols, Contains(Named("A_CCnew")));
+
+  // Change source.
+  FS.Files[testPath("root/A.cc")] =
+      "#include \"A.h\"\nvoid g() { (void)common; }\nvoid f_b() {}";
+  {
+    CacheHits = 0;
+    OverlayCDB CDB(/*Base=*/nullptr);
+    BackgroundIndex Idx(Context::empty(), "", FS, CDB,
+                        [&](llvm::StringRef) { return &MSS; });
+    CDB.setCompileCommand(testPath("root"), Cmd);
+    ASSERT_TRUE(Idx.blockUntilIdleForTest());
+  }
+  EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
+
+  // Check if the new symbol has arrived.
+  auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
+  EXPECT_NE(ShardHeader, nullptr);
+  EXPECT_THAT(*ShardSource->Symbols,
+              Contains(AllOf(Named("f_b"), Declared(), Defined())));
+}
+
 } // namespace clangd
 } // namespace clang