[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

222

i suppose this is no longer needed ?

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

848

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:
+                           //  - in the queue ==> new task is dropped
+                           //  - completed    ==> new task gets priority 0
 
     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> ActiveKeys;
+  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 {
+    ReindexFile = 0, // Implicitly applied by BackgroundQueue
     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 &Cmd : NeedsReIndexing)
+      Tasks.push_back(indexFileTask(Cmd));
     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)
+  if (ContextProvider) {
+    trace::Span Tracer("BackgroundPolicy");
     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 =
       loadIndexShards(MainFiles, IndexStorageFactory, CDB);
   size_t LoadedShards = 0;
   {
     // Update in-memory state.
     std::lock_guard<std::mutex> Lock(ShardVersionsMu);

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

llvm::Optional<Task> Task;
         Queue.clear();
         CV.notify_all();
         return;
       }
       ++Stat.Active;
       std::pop_heap(Queue.begin(), Queue.end());
       Task = std::move(Queue.back());
       Queue.pop_back();
+      if (Task->Key)
+        ActiveKeys.erase(Task->Key);
       notifyProgress();
     }
 
     if (Task->ThreadPri != llvm::ThreadPriority::Default &&
         !PreventStarvation.load())
       llvm::set_thread_priority(Task->ThreadPri);
     Task->Run();
     if (Task->ThreadPri != llvm::ThreadPriority::Default)

 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) {
+  if (T.Key) {
+    if (!ActiveKeys.insert(T.Key).second)
+      return false;
+    if (!SeenKeys.insert(T.Key).second)
+      T.QueuePri = 0;
+  }
+  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::_;
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}); // One A is dropped, the other is zero priority.
+    } else {
+      Q.stop();
+    }
+  });
+
+  EXPECT_EQ("ABB BBA", 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.