[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

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

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

107

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

clangd/index/Background.cpp

90

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

200

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...

270

"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.

318

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

338

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

374

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

393

Was this error possible before this change too?

396

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?

509

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)

511

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

108

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.

111

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

114

Should this be named VisitedShards?

[ilya-biryukov]

clangd/index/Background.cpp

417

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.

486

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

517

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

520

NIT: s/more smartly/smarter

523

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

528

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

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

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

270

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.

338

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.

374

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.

393

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

486

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?

517

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.

[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

261

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?

270

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?

338

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

414

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

416

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).

425

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

434

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.

468

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

473

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;
...

475

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

486

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.

503

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)

510

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.

525

NIT: use early exits to reduce nesting.

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

527

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.

clangd/index/Background.h

110

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

112

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

121

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

[kadircet]

Address comments

clangd/index/Background.cpp

270

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.

468

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.

475

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

108

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

121

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

[ilya-biryukov]

clangd/index/Background.cpp

270

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).

468

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

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

201

use llvm::StringRef

263

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

111

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

201

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.

270

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

111

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

Looks redundant. Remove?

clangd/index/Background.cpp

201

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.

263

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?

270

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

111

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

263

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.

270

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

263

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

304

NIT: s/we this/this/

305

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)

312

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

403

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.

683

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

clangd/index/Background.h

105

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

215

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

177

a typo: s/that needs/that need/

307

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

[kadircet]

Address comments

[ilya-biryukov]

LGTM. Ship it!

clangd/SourceCode.h

 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_SOURCECODE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_SOURCECODE_H
 #include "Protocol.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Tooling/Core/Replacement.h"
+#include "llvm/Support/Path.h"
 #include "llvm/Support/SHA1.h"
 
 namespace clang {
 class SourceManager;
 
 namespace clangd {
 
 // We tend to generate digests for source codes in a lot of different places.

 ///   - No duplicate or trailing directory separator
 ///
 /// This function should be used when sending paths to clients, so that paths
 /// are normalized as much as possible.
 llvm::Optional<std::string> getRealPath(const FileEntry *F,
                                         const SourceManager &SourceMgr);
 
 bool IsRangeConsecutive(const Range &Left, const Range &Right);
+
+// Handle the symbolic link path case where the current working directory
+// (getCurrentWorkingDirectory) is a symlink./ We always want to the real
+// file path (instead of the symlink path) for the  C++ symbols.
+//
+// Consider the following example:
+//
+//   src dir: /project/src/foo.h
+//   current working directory (symlink): /tmp/build -> /project/src/
+//
+// The file path of Symbol is "/project/src/foo.h" instead of
+// "/tmp/build/foo.h"
+std::string makeCanonicalPath(llvm::StringRef AbsolutePath,
+                              const SourceManager &SM);
 } // namespace clangd
 } // namespace clang
 #endif

clangd/SourceCode.cpp

 Optional<FileDigest> digestFile(const SourceManager &SM, FileID FID) {
   bool Invalid = false;
   StringRef Content = SM.getBufferData(FID, &Invalid);
   if (Invalid)
     return None;
   return digest(Content);
 }
 
+std::string makeCanonicalPath(llvm::StringRef AbsolutePath,
+                              const SourceManager &SM) {
+  if (const DirectoryEntry *Dir = SM.getFileManager().getDirectory(
+          llvm::sys::path::parent_path(AbsolutePath.str()))) {
+    StringRef DirName = SM.getFileManager().getCanonicalName(Dir);
+    llvm::SmallString<128> AbsoluteFilename;
+    llvm::sys::path::append(AbsoluteFilename, DirName,
+                            llvm::sys::path::filename(AbsolutePath.str()));
+    return AbsoluteFilename.str();
+  }
+  return AbsolutePath;
+}
+
 } // namespace clangd
 } // namespace clang

clangd/index/Background.h

BackgroundIndex(Context BackgroundContext, llvm::StringRef ResourceDir,
                   BackgroundIndexStorage::Factory IndexStorageFactory,
                   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:
   Context BackgroundContext;
 
   // index state
   llvm::Error index(tooling::CompileCommand,
                     BackgroundIndexStorage *IndexStorage);
 
   FileSymbols IndexedSymbols;
   llvm::StringMap<FileDigest> IndexedFileDigests; // Key is absolute file path.
   std::mutex DigestsMu;
 
   BackgroundIndexStorage::Factory IndexStorageFactory;
+  struct Source {
+    std::string Path;
+    bool NeedsReIndexing;
+  };
+  // Loads the shards for all the sources that was touched by this Cmd when the
+  // index was build. 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<> &VisitedShards);
+  llvm::Error loadShards(
+      std::vector<std::string> ChangedFiles,
+      std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>>
+          &NeedsReIndexing);
+  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);
-  void enqueueLocked(tooling::CompileCommand Cmd,
-                     BackgroundIndexStorage *IndexStorage);
   std::mutex QueueMu;
   unsigned NumActiveTasks = 0; // Only idle when queue is empty *and* no tasks.
   std::condition_variable QueueCV;
   bool ShouldStop = false;
   std::deque<Task> Queue;
   std::vector<std::thread> ThreadPool; // FIXME: Abstract this away.
   GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/index/Background.cpp

IncludeGraph getSubGraph(const URI &U, const IncludeGraph &FullGraph) {
   for (auto &Include : Node.DirectIncludes) {
     auto I = IG.try_emplace(Include).first;
     I->getValue().URI = I->getKey();
     Include = I->getKey();
   }
 
   return IG;
 }
+
+// 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 (sys::path::is_absolute(Cmd.Filename)) {
+    AbsolutePath = Cmd.Filename;
+  } else {
+    AbsolutePath = Cmd.Directory;
+    sys::path::append(AbsolutePath, Cmd.Filename);
+  }
+  return AbsolutePath;
+}
 } // namespace
 
 BackgroundIndex::BackgroundIndex(
     Context BackgroundContext, StringRef ResourceDir,
     const FileSystemProvider &FSProvider, const GlobalCompilationDatabase &CDB,
     BackgroundIndexStorage::Factory IndexStorageFactory, size_t ThreadPoolSize)
     : SwapIndex(make_unique<MemIndex>()), ResourceDir(ResourceDir),
       FSProvider(FSProvider), CDB(CDB),

 bool BackgroundIndex::blockUntilIdleForTest(
     llvm::Optional<double> TimeoutSeconds) {
   std::unique_lock<std::mutex> Lock(QueueMu);
   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]);
+    std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>>
+        NeedsReIndexing;
+    if (auto Error = loadShards(std::move(ChangedFiles), NeedsReIndexing))
+      elog("Loading shards failed: {0}", std::move(Error));
+
+    // Run indexing for files that needs 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);
   });
 }
 
-void BackgroundIndex::enqueue(const std::string &File) {
-  ProjectInfo Project;
-  if (auto Cmd = CDB.getCompileCommand(File, &Project)) {
-    auto *Storage = IndexStorageFactory(Project.SourceRoot);
-    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)));
-  }
+void BackgroundIndex::enqueue(tooling::CompileCommand Cmd,
+                              BackgroundIndexStorage *Storage) {
+      [this, Storage](tooling::CompileCommand Cmd) {
+        const std::string FileName = Cmd.Filename;
+          elog("Indexing {0} failed: {1}", FileName, std::move(Error));
+      std::move(Cmd)));
 }
 
 void BackgroundIndex::enqueueTask(Task T) {
   {
     std::lock_guard<std::mutex> Lock(QueueMu);
     Queue.push_back(std::move(T));
   }
   QueueCV.notify_all();
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) {
-    StringRef Path = F.first();
+  for (const auto &I : *Index.Sources) {
+    std::string Path = URICache.resolve(I.first());
+    {
+      auto Hash = I.second.Digest;
+      std::lock_guard<std::mutex> Lock(DigestsMu);
+      // Skip if file is already up to date.
+      auto DigestIt = IndexedFileDigests.try_emplace(Path);
+      if (!DigestIt.second && DigestIt.first->second == Hash)
+        continue;
+      // 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.
+      DigestIt.first->second = Hash;
+    }
     vlog("Update symbols in {0}", Path);
     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
-    // rare in practice.
-    IndexedFileDigests[Path] = Hash;
     IndexedSymbols.update(Path, std::move(SS), std::move(RS));
   }
 }
 
 // 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) {
     StringRef Path;
     if (const auto *F = SM.getFileEntryForID(FID))
       Path = F->getName();
     if (Path.empty())
       return false; // Skip invalid files.
     SmallString<128> AbsPath(Path);
     if (std::error_code EC =
             SM.getFileManager().getVirtualFileSystem()->makeAbsolute(AbsPath)) {
       elog("Warning: could not make absolute file: {0}", EC.message());
       return false; // Skip files without absolute path.
     }
+    AbsPath = makeCanonicalPath(AbsPath, SM);
     sys::path::remove_dots(AbsPath, /*remove_dot_dot=*/true);
     auto Digest = digestFile(SM, FID);
     if (!Digest)
       return false;
     auto D = FileDigests.find(AbsPath);
     if (D != FileDigests.end() && D->second == Digest)
       return false; // Skip files that haven't changed.
 
     FilesToUpdate[AbsPath] = *Digest;
     return true;
   };
 }
 
 Error BackgroundIndex::index(tooling::CompileCommand Cmd,
                              BackgroundIndexStorage *IndexStorage) {
   trace::Span Tracer("BackgroundIndex");
   SPAN_ATTACH(Tracer, "file", Cmd.Filename);
-  SmallString<128> AbsolutePath;
-  if (sys::path::is_absolute(Cmd.Filename)) {
-    AbsolutePath = Cmd.Filename;
-  } else {
-    AbsolutePath = Cmd.Directory;
-    sys::path::append(AbsolutePath, Cmd.Filename);
-  }
+  auto AbsolutePath = getAbsolutePath(Cmd);
 
   auto FS = FSProvider.getFileSystem();
   auto Buf = FS->getBufferForFile(AbsolutePath);
   if (!Buf)
     return 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 Error::success();
-    }
-
     DigestsSnapshot = IndexedFileDigests;
   }
 
-  log("Indexing {0}", Cmd.Filename, toHex(Hash));
+  vlog("Indexing {0}", Cmd.Filename, 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 createStringError(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 createStringError(inconvertibleErrorCode(),
                              "Couldn't build compiler instance");
 
   SymbolCollector::Options IndexOpts;
   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 createStringError(inconvertibleErrorCode(),
                              "BeginSourceFile() failed");
   if (!Action->Execute())
     return createStringError(inconvertibleErrorCode(), "Execute() failed");
   Action->EndSourceFile();
 
   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);
+
+  // FIXME: this should rebuild once-in-a-while, not after every file.
+  //       At that point we should use Dex, too.
+  vlog("Rebuilding automatic index");
+  reset(IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge));
+
+  return Error::success();
+}
+
+std::vector<BackgroundIndex::Source>
+BackgroundIndex::loadShard(const tooling::CompileCommand &Cmd,
+                           BackgroundIndexStorage *IndexStorage,
+                           llvm::StringSet<> &VisitedShards) {
+  // Adds the given shard's contents into BackgroundIndex.
+  // Consumes Symbols and Refs in Shard.
+  auto AddShardToIndex = [this](llvm::StringRef AbsolutePath,
+                                IndexFileIn *Shard,
+                                const IncludeGraphNode &IGN) {
+    if (!Shard)
+      return;
+    std::unique_ptr<SymbolSlab> SS;
+    std::unique_ptr<RefSlab> RS;
+    if (Shard->Symbols)
+      SS = llvm::make_unique<SymbolSlab>(std::move(*Shard->Symbols));
+    if (Shard->Refs)
+      RS = llvm::make_unique<RefSlab>(std::move(*Shard->Refs));
+    assert(IGN.Digest != FileDigest{{0}} && "Digest is empty?");
+    // Load shard information into background-index.
     {
-    // 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;
+      // 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[AbsolutePath] = IGN.Digest;
+      IndexedSymbols.update(AbsolutePath, std::move(SS), std::move(RS));
+    }
+  };
+
+  // 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.push_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 (!VisitedShards.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) {
+      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) {
+      if (auto U = URI::parse(I.getKey())) {
+        if (auto AbsolutePath = URI::resolve(*U, CurDependencyPath)) {
+          if (*AbsolutePath != CurDependencyPath) {
+            if (InQueue.try_emplace(*AbsolutePath).second)
+              Dependencies.push_back({*AbsolutePath, true});
+            continue;
+          }
+
+          // We found source file info for current dependency.
+          AddShardToIndex(CurDependencyPath, Shard.get(), I.getValue());
+          // 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;
+        }
+      }
+    }
   }
 
+  return Dependencies;
+}
+
+// Goes over each changed file and loads them from index, in the case of a
+// missing or out-dated shard enqueues an indexing operation.
+llvm::Error 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<> BeingReindexed;
+  // 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) {
+      // 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.
+      if (Dependency.NeedsReIndexing &&
+          !BeingReindexed.count(Dependency.Path)) {
+        vlog("Enqueueing {0} for {1}", 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)
+          BeingReindexed.insert(Dependency.Path);
+        break;
+      }
+    }
+  }
   // FIXME: this should rebuild once-in-a-while, not after every file.
   //       At that point we should use Dex, too.
   vlog("Rebuilding automatic index");
   reset(IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge));
 
   return Error::success();
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.cpp

 // the SourceManager.
 Optional<std::string> toURI(const SourceManager &SM, StringRef Path,
                             const SymbolCollector::Options &Opts) {
   SmallString<128> AbsolutePath(Path);
   if (std::error_code EC =
           SM.getFileManager().getVirtualFileSystem()->makeAbsolute(
               AbsolutePath))
     log("Warning: could not make absolute file: {0}", EC.message());
-  if (sys::path::is_absolute(AbsolutePath)) {
-    // Handle the symbolic link path case where the current working directory
-    // (getCurrentWorkingDirectory) is a symlink./ We always want to the real
-    // file path (instead of the symlink path) for the  C++ symbols.
-    //
-    // Consider the following example:
-    //
-    //   src dir: /project/src/foo.h
-    //   current working directory (symlink): /tmp/build -> /project/src/
-    //
-    // The file path of Symbol is "/project/src/foo.h" instead of
-    // "/tmp/build/foo.h"
-    if (const DirectoryEntry *Dir = SM.getFileManager().getDirectory(
-            sys::path::parent_path(AbsolutePath.str()))) {
-      StringRef DirName = SM.getFileManager().getCanonicalName(Dir);
-      SmallString<128> AbsoluteFilename;
-      sys::path::append(AbsoluteFilename, DirName,
-                        sys::path::filename(AbsolutePath.str()));
-      AbsolutePath = AbsoluteFilename;
-    }
-  } else if (!Opts.FallbackDir.empty()) {
+  if (sys::path::is_absolute(AbsolutePath))
+    AbsolutePath = makeCanonicalPath(AbsolutePath, SM);
+  else if (!Opts.FallbackDir.empty())
     sys::fs::make_absolute(Opts.FallbackDir, AbsolutePath);
-  }
 
   sys::path::remove_dots(AbsolutePath, /*remove_dot_dot=*/true);
   return URI::create(AbsolutePath).toString();
 }
 
 // All proto generated headers should start with this line.
 static const char *PROTO_HEADER_COMMENT =
     "// Generated by the protocol buffer compiler.  DO NOT EDIT!";

 
 // Checks whether \p ND is a definition of a TagDecl (class/struct/enum/union)
 // in a header file, in which case clangd would prefer to use ND as a canonical
 // declaration.
 // FIXME: handle symbol types that are not TagDecl (e.g. functions), if using
 // the first seen declaration as canonical declaration is not a good enough
 // heuristic.
 bool isPreferredDeclaration(const NamedDecl &ND, index::SymbolRoleSet Roles) {
   const auto& SM = ND.getASTContext().getSourceManager();
   return (Roles & static_cast<unsigned>(index::SymbolRole::Definition)) &&
          isa<TagDecl>(&ND) &&
          !SM.isWrittenInMainFile(SM.getExpansionLoc(ND.getLocation()));
 }
 
 RefKind toRefKind(index::SymbolRoleSet Roles) {
   return static_cast<RefKind>(static_cast<unsigned>(RefKind::All) & Roles);
 }

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 -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 "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::_;
 using testing::AllOf;
+using testing::Contains;
 using testing::Not;
 using testing::UnorderedElementsAre;
 
 using namespace llvm;
 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,
EXPECT_THAT(
       ShardHeader->Sources->lookup("unittest:///root/A.h").DirectIncludes,
       UnorderedElementsAre("unittest:///root/B.h"));
   EXPECT_NE(ShardHeader->Sources->lookup("unittest:///root/A.h").Digest,
             FileDigest{0});
   EXPECT_THAT(ShardHeader->Sources->lookup("unittest:///root/B.h"),
               EmptyIncludeNode());
 }
 
+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