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,8 @@
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; }
};
@@ -114,6 +116,7 @@
private:
void notifyProgress() const; // Requires lock Mu
+ bool adjust(Task &T);
std::mutex Mu;
Stats Stat;
@@ -122,6 +125,7 @@
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
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 <algorithm>
#include <atomic>
@@ -139,8 +140,8 @@
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));
});
@@ -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<WithContext> WithProvidedContext;
if (ContextProvider)
@@ -168,6 +170,7 @@
});
T.QueuePri = IndexFile;
T.Tag = std::move(Tag);
+ T.Key = Key;
return T;
}
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
@@ -72,10 +72,24 @@
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;
@@ -87,11 +101,13 @@
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();
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"
@@ -666,25 +667,45 @@
// 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);
- }
+ 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 {
@@ -829,6 +850,31 @@
}
}
+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;