diff --git a/clang-tools-extra/clangd/index/Background.h b/clang-tools-extra/clangd/index/Background.h --- a/clang-tools-extra/clangd/index/Background.h +++ b/clang-tools-extra/clangd/index/Background.h @@ -76,6 +76,9 @@ 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; } }; @@ -114,6 +117,7 @@ private: void notifyProgress() const; // Requires lock Mu + bool adjust(Task &T); std::mutex Mu; Stats Stat; @@ -122,6 +126,8 @@ std::vector Queue; // max-heap llvm::StringMap Boosts; std::function OnProgress; + llvm::DenseSet ActiveKeys; + llvm::DenseSet SeenKeys; }; // Builds an in-memory index by by running the static indexer action over @@ -213,6 +219,7 @@ // from lowest to highest priority enum QueuePriority { + ReindexFile = 0, // Implicitly applied by BackgroundQueue IndexFile, IndexBoostedFile, LoadShards, diff --git a/clang-tools-extra/clangd/index/Background.cpp b/clang-tools-extra/clangd/index/Background.cpp --- a/clang-tools-extra/clangd/index/Background.cpp +++ b/clang-tools-extra/clangd/index/Background.cpp @@ -43,6 +43,7 @@ #include "llvm/Support/Error.h" #include "llvm/Support/Path.h" #include "llvm/Support/Threading.h" +#include "llvm/Support/xxhash.h" #include #include @@ -139,8 +140,8 @@ std::mt19937(std::random_device{}())); std::vector 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)); }); @@ -156,6 +157,7 @@ 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 WithProvidedContext; if (ContextProvider) @@ -168,6 +170,7 @@ }); T.QueuePri = IndexFile; T.Tag = std::move(Tag); + T.Key = Key; return T; } @@ -353,13 +356,15 @@ std::vector BackgroundIndex::loadProject(std::vector 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 Result = diff --git a/clang-tools-extra/clangd/index/BackgroundQueue.cpp b/clang-tools-extra/clangd/index/BackgroundQueue.cpp --- a/clang-tools-extra/clangd/index/BackgroundQueue.cpp +++ b/clang-tools-extra/clangd/index/BackgroundQueue.cpp @@ -33,6 +33,8 @@ std::pop_heap(Queue.begin(), Queue.end()); Task = std::move(Queue.back()); Queue.pop_back(); + if (Task->Key) + ActiveKeys.erase(Task->Key); notifyProgress(); } @@ -72,10 +74,23 @@ 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 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; @@ -87,11 +102,13 @@ void BackgroundQueue::append(std::vector Tasks) { { std::lock_guard 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(); diff --git a/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp b/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp --- a/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp @@ -9,6 +9,7 @@ #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" @@ -829,6 +830,30 @@ } } +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;