[clangd] Fix updated file detection logic in indexing

[kadircet]

Summary

Files without any symbols were never marked as updated during indexing, which resulted in failure while writing shards for these files.

This patch fixes the logic to mark files that are seen for the first time but don't contain any symbols as updated.

[ilya-biryukov]

clangd/index/Background.cpp

318

If this the only reason we're traversing Index.Sources? If so, I suggest removing this comment and traversing Files instead.
This would make the code more straightforward and would definitely cost us only a negligible performance penalty.

[kadircet]

• Change the logic to detect updated files to take new files without any symbols into account.

[kadircet]

clangd/index/Background.cpp

318

Well actually, in addition to that I was traversing source files rather than updated files to make sure we write down shards even for sources without any symbols or refs in them. Because current logic in FileFilter didn't take files without any symbols into account.

So this is actually rather about detecting if a file is already up-to-date or not, changing that logic to take new files without any symbols into account.

[kadircet]

• Change FileFilter and update logic to do not care about if there are any symbols coming from a file.

[kadircet]

• Update comments

[ilya-biryukov]

This looks neat, thanks for the change!
Just a few NITs from my side

clangd/index/Background.cpp

264

NIT: maybe rephrase to "different or missing from DigestsSnapshot"?

280

Use value type, since it's an iterator:
auto DigestIt = DigestsSnapshot.find or const auto DigestIt = …

287–288

Maybe avoid extra lookups?

auto FileIt = Files.find(DeclPath);
if (FileIt != Files.end())
  FileIt->Symbols.insert(&Sym);

298–299

Maybe avoid extra lookups here too?

307–308

Same here, maybe avoid extra lookups?

[ilya-biryukov]

LGTM after the NITs are fixed. Unless there are other significant changes planned that I need to look at.

[kadircet]

• Address comments

clangd/index/Background.h

public:
   // 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:
-  /// Given index results from a TU, only update files in \p FilesToUpdate.
-  /// Also stores new index information on IndexStorage.
+  /// Given index results from a TU, only update symbols coming from files with
+  /// different digests than \p DigestsSnapshot. Also stores new index
+  /// information on IndexStorage.
   void update(llvm::StringRef MainFile, IndexFileIn Index,
-              const llvm::StringMap<FileDigest> &FilesToUpdate,
+              const llvm::StringMap<FileDigest> &DigestsSnapshot,
               BackgroundIndexStorage *IndexStorage);
 
   // configuration
   std::string ResourceDir;
   const FileSystemProvider &FSProvider;
   const GlobalCompilationDatabase &CDB;
   Context BackgroundContext;
 

clangd/index/Background.cpp

for (auto &Include : Node.DirectIncludes) {
     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.
+// \p FileDigests contains file digests for the current indexed files.
 decltype(SymbolCollector::Options::FileFilter)
-createFileFilter(const llvm::StringMap<FileDigest> &FileDigests,
-                 llvm::StringMap<FileDigest> &FilesToUpdate) {
-  return [&FileDigests, &FilesToUpdate](const SourceManager &SM, FileID FID) {
+createFileFilter(const llvm::StringMap<FileDigest> &FileDigests) {
+  return [&FileDigests](const SourceManager &SM, FileID FID) {
     const auto *F = SM.getFileEntryForID(FID);
     if (!F)
       return false; // Skip invalid files.
     auto AbsPath = getCanonicalPath(F, SM);
     if (!AbsPath)
       return false; // Skip files without absolute path.
     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;
   };
 }
 
 // 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) {
if (Priority == ThreadPriority::Normal) {
         return Elem.second == ThreadPriority::Low;
       });
     }
     Queue.insert(I, {std::move(T), Priority});
   }
   QueueCV.notify_all();
 }
 
-/// Given index results from a TU, only update files in \p FilesToUpdate.
+/// Given index results from a TU, only update symbols coming from files that
+/// are different or missing from than \p DigestsSnapshot. Also stores new index
+/// information on IndexStorage.
 void BackgroundIndex::update(llvm::StringRef MainFile, IndexFileIn Index,
-                             const llvm::StringMap<FileDigest> &FilesToUpdate,
+                             const llvm::StringMap<FileDigest> &DigestsSnapshot,
                              BackgroundIndexStorage *IndexStorage) {
   // Partition symbols/references into files.
   struct File {
     llvm::DenseSet<const Symbol *> Symbols;
     llvm::DenseSet<const Ref *> Refs;
+    FileDigest Digest;
   };
   llvm::StringMap<File> Files;
   URIToFileCache URICache(MainFile);
+  for (const auto &IndexIt : *Index.Sources) {
+    const auto &IGN = IndexIt.getValue();
+    const auto AbsPath = URICache.resolve(IGN.URI);
+    const auto DigestIt = DigestsSnapshot.find(AbsPath);
+    // File has different contents.
+    if (DigestIt == DigestsSnapshot.end() || DigestIt->getValue() != IGN.Digest)
+      Files.try_emplace(AbsPath).first->getValue().Digest = IGN.Digest;
+  }
   for (const auto &Sym : *Index.Symbols) {
     if (Sym.CanonicalDeclaration) {
       auto DeclPath = URICache.resolve(Sym.CanonicalDeclaration.FileURI);
-      if (FilesToUpdate.count(DeclPath) != 0)
-        Files[DeclPath].Symbols.insert(&Sym);
+      const auto FileIt = Files.find(DeclPath);
+      if (FileIt != Files.end())
+        FileIt->second.Symbols.insert(&Sym);
     }
     // For symbols with different declaration and definition locations, we store
     // the full symbol in both the header file and the implementation file, so
     // that merging can tell the preferred symbols (from canonical headers) from
     // other symbols (e.g. forward declarations).
     if (Sym.Definition &&
         Sym.Definition.FileURI != Sym.CanonicalDeclaration.FileURI) {
       auto DefPath = URICache.resolve(Sym.Definition.FileURI);
-      if (FilesToUpdate.count(DefPath) != 0)
-        Files[DefPath].Symbols.insert(&Sym);
+      const auto FileIt = Files.find(DefPath);
+      if (FileIt != Files.end())
+        FileIt->second.Symbols.insert(&Sym);
     }
   }
   llvm::DenseMap<const Ref *, SymbolID> RefToIDs;
   for (const auto &SymRefs : *Index.Refs) {
     for (const auto &R : SymRefs.second) {
       auto Path = URICache.resolve(R.Location.FileURI);
-      if (FilesToUpdate.count(Path) != 0) {
-        auto &F = Files[Path];
+      const auto FileIt = Files.find(Path);
+      if (FileIt != Files.end()) {
+        auto &F = FileIt->getValue();
         RefToIDs[&R] = SymRefs.first;
         F.Refs.insert(&R);
       }
     }
   }
 
   // Build and store new slabs for each updated file.
-  for (const auto &I : *Index.Sources) {
-    std::string Path = URICache.resolve(I.first());
+  for (const auto &FileIt : Files) {
+    llvm::StringRef Path = FileIt.getKey();
     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);
-    }
+    for (const auto *S : FileIt.second.Symbols)
+    for (const auto *R : FileIt.second.Refs)
     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()));
     // 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);
-      auto Hash = I.second.Digest;
+      auto Hash = FileIt.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.
llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd,
   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);
+  IndexOpts.FileFilter = createFileFilter(DigestsSnapshot);
   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,
llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd,
 
   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);
+  update(AbsolutePath, std::move(Index), DigestsSnapshot, IndexStorage);
 
   if (BuildIndexPeriodMs > 0)
     SymbolsUpdatedSinceLastIndex = true;
   else
     reset(
         IndexedSymbols.buildIndex(IndexType::Light, DuplicateHandling::Merge));
 
   return llvm::Error::success();

unittests/clangd/BackgroundIndexTests.cpp

FS.Files[testPath("root/A.cc")] =
     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"));
+  ShardHeader = MSS.loadShard(testPath("root/A.h"));
   EXPECT_NE(ShardHeader, nullptr);
+  EXPECT_THAT(*ShardHeader->Symbols, Contains(Named("A_CCnew")));
+  auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
+  EXPECT_NE(ShardSource, nullptr);
   EXPECT_THAT(*ShardSource->Symbols,
               Contains(AllOf(Named("f_b"), Declared(), Defined())));
 }
 
+TEST_F(BackgroundIndexTest, ShardStorageEmptyFile) {
+  MockFSProvider FS;
+  FS.Files[testPath("root/A.h")] = R"cpp(
+      void common();
+      void f_b();
+      class A_CC {};
+      )cpp";
+  FS.Files[testPath("root/B.h")] = R"cpp(
+      #include "A.h"
+      )cpp";
+  FS.Files[testPath("root/A.cc")] =
+      "#include \"B.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 that A.cc, A.h and B.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());
+  }
+  EXPECT_THAT(Storage.keys(),
+              UnorderedElementsAre(testPath("root/A.cc"), testPath("root/A.h"),
+                                   testPath("root/B.h")));
+  auto ShardHeader = MSS.loadShard(testPath("root/B.h"));
+  EXPECT_NE(ShardHeader, nullptr);
+  EXPECT_TRUE(ShardHeader->Symbols->empty());
+
+  // Check that A.cc, A.h and B.h has been loaded.
+  {
+    CacheHits = 0;
+    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());
+  }
+  EXPECT_EQ(CacheHits, 3U);
+
+  // Update B.h to contain some symbols.
+  FS.Files[testPath("root/B.h")] = R"cpp(
+      #include "A.h"
+      void new_func();
+      )cpp";
+  // Check that B.h has been stored with new contents.
+  {
+    CacheHits = 0;
+    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());
+  }
+  EXPECT_EQ(CacheHits, 3U);
+  ShardHeader = MSS.loadShard(testPath("root/B.h"));
+  EXPECT_NE(ShardHeader, nullptr);
+  EXPECT_THAT(*ShardHeader->Symbols,
+              Contains(AllOf(Named("new_func"), Declared(), Not(Defined()))));
+}
+
 } // namespace clangd
 } // namespace clang