[clangd] Explicitly avoid background-indexing the same file twice.

[sammccall]

Summary

This used to implicitly never happen due to only discovering each CDB once.

We may want to carefully support reindexing one day, but we need to do it carefully (tricky tradeoffs) and it would need further support in background indexer.

Making this explicit here rather than just turning off rebroadcast in background index for a few reasons:

• allows *new* files in the same CDB to be indexed
• relying on bugs-at-a-distance cancelling each other out is bound to bite us
• gets us closer to actually supporting reindexing, which requires similar tracking

[sammccall]

In fact, never index the same file twice at all.

[kadircet]

thank, as discussed offline this looks like the right thing to do before the branch cut. we might re-evaluate our decision around re-indexing on cmd changes and canonicalization one day ...

LGTM! (with some small comments)

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

143–144

nit: while here can we s/Cmd/FilePath ?

144

why do we drop std::move here ? these are strings in the end and indexFileTask is still expecting a value not a reference.

360

nit: might be nice to have this in a separate patch

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

220

i suppose this is no longer needed ?

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

868

both As are dropped here right ? not just one.

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

public:
   /// A work item on the thread pool's queue.
   struct Task {
     explicit Task(std::function<void()> Run) : Run(std::move(Run)) {}
 
     std::function<void()> Run;
     llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Background;
     unsigned QueuePri = 0; // Higher-priority tasks will run first.
     std::string Tag;       // Allows priority to be boosted later.
+    uint64_t Key = 0;      // If the key matches a previous task, drop this one.
+                           // (in practice this means we never reindex a file).
 
     bool operator<(const Task &O) const { return QueuePri < O.QueuePri; }
   };
 
   // Describes the number of tasks processed by the queue.
   struct Stats {
     unsigned Enqueued = 0;  // Total number of tasks ever enqueued.
     unsigned Active = 0;    // Tasks being currently processed by a worker.
public:
   // Disables thread priority lowering to ensure progress on loaded systems.
   // Only affects tasks that run after the call.
   static void preventThreadStarvationInTests();
   LLVM_NODISCARD bool
   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds);
 
 private:
   void notifyProgress() const; // Requires lock Mu
+  bool adjust(Task &T);
 
   std::mutex Mu;
   Stats Stat;
   std::condition_variable CV;
   bool ShouldStop = false;
   std::vector<Task> Queue; // max-heap
   llvm::StringMap<unsigned> Boosts;
   std::function<void(Stats)> OnProgress;
+  llvm::DenseSet<uint64_t> SeenKeys;
 };
 
 // Builds an in-memory index by by running the static indexer action over
 // all commands in a compilation database. Indexing happens in the background.
 // FIXME: it should watch for changes to files on disk.
 class BackgroundIndex : public SwapIndex {
 public:
   struct Options {
private:
   std::vector<std::string> loadProject(std::vector<std::string> MainFiles);
 
   BackgroundQueue::Task
   changedFilesTask(const std::vector<std::string> &ChangedFiles);
   BackgroundQueue::Task indexFileTask(std::string Path);
 
   // from lowest to highest priority
   enum QueuePriority {
     IndexFile,
     IndexBoostedFile,
     LoadShards,
   };
   BackgroundQueue Queue;
   AsyncTaskRunner ThreadPool;
   GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

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

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Threading.h"
+#include "llvm/Support/xxhash.h"
 
 #include <algorithm>
 #include <atomic>
 #include <chrono>
 #include <condition_variable>
 #include <cstddef>
 #include <memory>
 #include <mutex>
BackgroundQueue::Task T([this, ChangedFiles] {
     SPAN_ATTACH(Tracer, "files", int64_t(ChangedFiles.size()));
 
     auto NeedsReIndexing = loadProject(std::move(ChangedFiles));
     // Run indexing for files that need to be updated.
     std::shuffle(NeedsReIndexing.begin(), NeedsReIndexing.end(),
                  std::mt19937(std::random_device{}()));
     std::vector<BackgroundQueue::Task> Tasks;
     Tasks.reserve(NeedsReIndexing.size());
-    for (auto &Cmd : NeedsReIndexing)
-      Tasks.push_back(indexFileTask(std::move(Cmd)));
+    for (const auto &File : NeedsReIndexing)
+      Tasks.push_back(indexFileTask(std::move(File)));
     Queue.append(std::move(Tasks));
   });
 
   T.QueuePri = LoadShards;
   T.ThreadPri = llvm::ThreadPriority::Default;
   return T;
 }
 
 static llvm::StringRef filenameWithoutExtension(llvm::StringRef Path) {
   Path = llvm::sys::path::filename(Path);
   return Path.drop_back(llvm::sys::path::extension(Path).size());
 }
 
 BackgroundQueue::Task BackgroundIndex::indexFileTask(std::string Path) {
   std::string Tag = filenameWithoutExtension(Path).str();
+  uint64_t Key = llvm::xxHash64(Path);
   BackgroundQueue::Task T([this, Path(std::move(Path))] {
     llvm::Optional<WithContext> WithProvidedContext;
     if (ContextProvider)
       WithProvidedContext.emplace(ContextProvider(Path));
     auto Cmd = CDB.getCompileCommand(Path);
     if (!Cmd)
       return;
     if (auto Error = index(std::move(*Cmd)))
       elog("Indexing {0} failed: {1}", Path, std::move(Error));
   });
   T.QueuePri = IndexFile;
   T.Tag = std::move(Tag);
+  T.Key = Key;
   return T;
 }
 
 void BackgroundIndex::boostRelated(llvm::StringRef Path) {
   if (isHeaderFile(Path))
     Queue.boost(filenameWithoutExtension(Path), IndexBoostedFile);
 }
 

 
 // Restores shards for \p MainFiles from index storage. Then checks staleness of
 // those shards and returns a list of TUs that needs to be indexed to update
 // staleness.
 std::vector<std::string>
 BackgroundIndex::loadProject(std::vector<std::string> MainFiles) {
   // Drop files where background indexing is disabled in config.
   if (ContextProvider)
     llvm::erase_if(MainFiles, [&](const std::string &TU) {
       // Load the config for each TU, as indexing may be selectively enabled.
       WithContext WithProvidedContext(ContextProvider(TU));
       return Config::current().Index.Background ==
              Config::BackgroundPolicy::Skip;
     });
   Rebuilder.startLoading();
   // Load shards for all of the mainfiles.
   const std::vector<LoadedShard> Result =

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

 void BackgroundQueue::stop() {
   {
     std::lock_guard<std::mutex> QueueLock(Mu);
     ShouldStop = true;
   }
   CV.notify_all();
 }
 
+// Tweaks the priority of a newly-enqueued task, or returns false to cancel it.
+bool BackgroundQueue::adjust(Task &T) {
+  // It is tempting to drop duplicates of queued tasks, and merely deprioritize
+  // duplicates of completed tasks (i.e. reindexing on CDB changes). But:
+  //  - the background indexer doesn't support reindexing well, e.g. staleness
+  //    is checked at *enqueue* time only, and doesn't account for compile flags
+  //  - reindexing on compile flags is often a poor use of CPU in practice
+  if (T.Key && !SeenKeys.insert(T.Key).second)
+    return false;
+  T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
+  return true;
+}
+
 void BackgroundQueue::push(Task T) {
   {
     std::lock_guard<std::mutex> Lock(Mu);
-    T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
+    if (!adjust(T))
+      return;
     Queue.push_back(std::move(T));
     std::push_heap(Queue.begin(), Queue.end());
     ++Stat.Enqueued;
     notifyProgress();
   }
   CV.notify_all();
 }
 
 void BackgroundQueue::append(std::vector<Task> Tasks) {
   {
     std::lock_guard<std::mutex> Lock(Mu);
-    for (Task &T : Tasks)
-      T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
-    std::move(Tasks.begin(), Tasks.end(), std::back_inserter(Queue));
+    for (Task &T : Tasks) {
+      if (!adjust(T))
+        continue;
+      Queue.push_back(std::move(T));
+      ++Stat.Enqueued;
+    }
     std::make_heap(Queue.begin(), Queue.end());
-    Stat.Enqueued += Tasks.size();
     notifyProgress();
   }
   CV.notify_all();
 }
 
 void BackgroundQueue::boost(llvm::StringRef Tag, unsigned NewPriority) {
   std::lock_guard<std::mutex> Lock(Mu);
   unsigned &Boost = Boosts[Tag];

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

 #include "CompileCommands.h"
 #include "Config.h"
 #include "Headers.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "TestIndex.h"
 #include "TestTU.h"
 #include "index/Background.h"
 #include "index/BackgroundRebuild.h"
 #include "clang/Tooling/ArgumentsAdjusters.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/Threading.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <deque>
 #include <thread>
 
 using ::testing::_;
TEST_F(BackgroundIndexTest, CmdLineHash) {
   Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
   CDB.setCompileCommand(testPath("build/../A.cc"), Cmd);
   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 
   EXPECT_THAT(Storage.keys(), ElementsAre(testPath("A.cc"), testPath("A.h")));
   // Make sure we only store the Cmd for main file.
   EXPECT_FALSE(MSS.loadShard(testPath("A.h"))->Cmd);
 
-  {
-    tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd;
-    EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine);
-    EXPECT_EQ(CmdStored.Directory, Cmd.Directory);
-  }
 
-  // FIXME: Changing compile commands should be enough to invalidate the cache.
-  FS.Files[testPath("A.cc")] = " ";
-  Cmd.CommandLine = {"clang++", "../A.cc", "-Dfoo", "-fsyntax-only"};
-  CDB.setCompileCommand(testPath("build/../A.cc"), Cmd);
+TEST_F(BackgroundIndexTest, Reindex) {
+  MockFS FS;
+  llvm::StringMap<std::string> Storage;
+  size_t CacheHits = 0;
+  MemoryShardStorage MSS(Storage, CacheHits);
+  OverlayCDB CDB(/*Base=*/nullptr);
+  BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
+                      /*Opts=*/{});
+
+  // Index a file.
+  FS.Files[testPath("A.cc")] = "int theOldFunction();";
+  tooling::CompileCommand Cmd;
+  Cmd.Filename = "../A.cc";
+  Cmd.Directory = testPath("build");
+  Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
+  CDB.setCompileCommand(testPath("A.cc"), Cmd);
   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 
-  EXPECT_FALSE(MSS.loadShard(testPath("A.h"))->Cmd);
+  // Verify the result is indexed and stored.
+  EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
+  EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
+  std::string OldShard = Storage.lookup(testPath("A.cc"));
+  EXPECT_NE("", OldShard);
 
-  {
-    tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd;
-    EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine);
-    EXPECT_EQ(CmdStored.Directory, Cmd.Directory);
-  }
+  // Change the content and command, and notify to reindex it.
+  Cmd.CommandLine.push_back("-DFOO");
+  FS.Files[testPath("A.cc")] = "int theNewFunction();";
+  CDB.setCompileCommand(testPath("A.cc"), Cmd);
+  ASSERT_TRUE(Idx.blockUntilIdleForTest());
+
+  // Currently, we will never index the same main file again.
+  EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
+  EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
+  EXPECT_EQ(OldShard, Storage.lookup(testPath("A.cc")));
 }
 
 class BackgroundIndexRebuilderTest : public testing::Test {
 protected:
   BackgroundIndexRebuilderTest()
       : Target(std::make_unique<MemIndex>()),
         Rebuilder(&Target, &Source, /*Threads=*/10) {
     // Prepare FileSymbols with TestSymbol in it, for checkRebuild.
Sequence.clear();
     BackgroundQueue Q;
     Q.append({A, B});
     Q.boost("A", 3);
     Q.work([&] { Q.stop(); });
     EXPECT_EQ("AB", Sequence) << "A was boosted after enqueueing";
   }
 }
 
+TEST(BackgroundQueueTest, Duplicates) {
+  std::string Sequence;
+  BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
+  A.QueuePri = 100;
+  A.Key = 1;
+  BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
+  // B has no key, and is not subject to duplicate detection.
+  B.QueuePri = 50;
+
+  BackgroundQueue Q;
+  Q.append({A, B, A, B}); // One A is dropped, the other is high priority.
+  Q.work(/*OnIdle=*/[&] {
+    // The first time we go idle, we enqueue the same task again.
+    if (!llvm::is_contained(Sequence, ' ')) {
+      Sequence.push_back(' ');
+      Q.append({A, B, A, B}); // Both As are dropped.
+    } else {
+      Q.stop();
+    }
+  });
+
+  // This could reasonably be "ABB BBA", if we had good *re*indexing support.
+  EXPECT_EQ("ABB BB", Sequence);
+}
+
 TEST(BackgroundQueueTest, Progress) {
   using testing::AnyOf;
   BackgroundQueue::Stats S;
   BackgroundQueue Q([&](BackgroundQueue::Stats New) {
     // Verify values are sane.
     // Items are enqueued one at a time (at least in this test).
     EXPECT_THAT(New.Enqueued, AnyOf(S.Enqueued, S.Enqueued + 1));
     // Items are completed one at a time.