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

   1 #include "CompileCommands.h"
   2 #include "Config.h"
   3 #include "Headers.h"
   4 #include "SyncAPI.h"
   5 #include "TestFS.h"
   6 #include "TestTU.h"
   7 #include "index/Background.h"
   8 #include "index/BackgroundRebuild.h"
   9 #include "index/MemIndex.h"
  10 #include "clang/Tooling/ArgumentsAdjusters.h"
  11 #include "clang/Tooling/CompilationDatabase.h"
  12 #include "llvm/ADT/STLExtras.h"
  13 #include "llvm/Support/ScopedPrinter.h"
  14 #include "gmock/gmock.h"
  15 #include "gtest/gtest.h"
  16 #include <deque>
  17 #include <thread>
  18
  19 using ::testing::_;
  20 using ::testing::AllOf;
  21 using ::testing::Contains;
  22 using ::testing::ElementsAre;
  23 using ::testing::Not;
  24 using ::testing::Pair;
  25 using ::testing::UnorderedElementsAre;
  26
  27 namespace clang {
  28 namespace clangd {
  29
  30 MATCHER_P(named, N, "") { return arg.Name == N; }
  31 MATCHER_P(qName, N, "") { return (arg.Scope + arg.Name).str() == N; }
  32 MATCHER(declared, "") {
  33   return !StringRef(arg.CanonicalDeclaration.FileURI).empty();
  34 }
  35 MATCHER(defined, "") { return !StringRef(arg.Definition.FileURI).empty(); }
  36 MATCHER_P(fileURI, F, "") { return StringRef(arg.Location.FileURI) == F; }
  37 ::testing::Matcher<const RefSlab &>
  38 refsAre(std::vector<::testing::Matcher<Ref>> Matchers) {
  39   return ElementsAre(::testing::Pair(_, UnorderedElementsAreArray(Matchers)));
  40 }
  41 // URI cannot be empty since it references keys in the IncludeGraph.
  42 MATCHER(emptyIncludeNode, "") {
  43   return arg.Flags == IncludeGraphNode::SourceFlag::None && !arg.URI.empty() &&
  44          arg.Digest == FileDigest{{0}} && arg.DirectIncludes.empty();
  45 }
  46
  47 MATCHER(hadErrors, "") {
  48   return arg.Flags & IncludeGraphNode::SourceFlag::HadErrors;
  49 }
  50
  51 MATCHER_P(numReferences, N, "") { return arg.References == N; }
  52
  53 class MemoryShardStorage : public BackgroundIndexStorage {
  54   mutable std::mutex StorageMu;
  55   llvm::StringMap<std::string> &Storage;
  56   size_t &CacheHits;
  57
  58 public:
  59   MemoryShardStorage(llvm::StringMap<std::string> &Storage, size_t &CacheHits)
  60       : Storage(Storage), CacheHits(CacheHits) {}
  61   llvm::Error storeShard(llvm::StringRef ShardIdentifier,
  62                          IndexFileOut Shard) const override {
  63     std::lock_guard<std::mutex> Lock(StorageMu);
  64     AccessedPaths.insert(ShardIdentifier);
  65     Storage[ShardIdentifier] = llvm::to_string(Shard);
  66     return llvm::Error::success();
  67   }
  68   std::unique_ptr<IndexFileIn>
  69   loadShard(llvm::StringRef ShardIdentifier) const override {
  70     std::lock_guard<std::mutex> Lock(StorageMu);
  71     AccessedPaths.insert(ShardIdentifier);
  72     if (Storage.find(ShardIdentifier) == Storage.end()) {
  73       return nullptr;
  74     }
  75     auto IndexFile =
  76         readIndexFile(Storage[ShardIdentifier], SymbolOrigin::Background);
  77     if (!IndexFile) {
  78       ADD_FAILURE() << "Error while reading " << ShardIdentifier << ':'
  79                     << IndexFile.takeError();
  80       return nullptr;
  81     }
  82     CacheHits++;
  83     return std::make_unique<IndexFileIn>(std::move(*IndexFile));
  84   }
  85
  86   mutable llvm::StringSet<> AccessedPaths;
  87 };
  88
  89 class BackgroundIndexTest : public ::testing::Test {
  90 protected:
  91   BackgroundIndexTest() { BackgroundQueue::preventThreadStarvationInTests(); }
  92 };
  93
  94 TEST_F(BackgroundIndexTest, NoCrashOnErrorFile) {
  95   MockFS FS;
  96   FS.Files[testPath("root/A.cc")] = "error file";
  97   llvm::StringMap<std::string> Storage;
  98   size_t CacheHits = 0;
  99   MemoryShardStorage MSS(Storage, CacheHits);
 100   OverlayCDB CDB(/*Base=*/nullptr);
 101   BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 102                       /*Opts=*/{});
 103
 104   tooling::CompileCommand Cmd;
 105   Cmd.Filename = testPath("root/A.cc");
 106   Cmd.Directory = testPath("root");
 107   Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")};
 108   CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 109
 110   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 111 }
 112
 113 TEST_F(BackgroundIndexTest, Config) {
 114   MockFS FS;
 115   // Set up two identical TUs, foo and bar.
 116   // They define foo::one and bar::one.
 117   std::vector<tooling::CompileCommand> Cmds;
 118   for (std::string Name : {"foo", "bar", "baz"}) {
 119     std::string Filename = Name + ".cpp";
 120     std::string Header = Name + ".h";
 121     FS.Files[Filename] = "#include \"" + Header + "\"";
 122     FS.Files[Header] = "namespace " + Name + " { int one; }";
 123     tooling::CompileCommand Cmd;
 124     Cmd.Filename = Filename;
 125     Cmd.Directory = testRoot();
 126     Cmd.CommandLine = {"clang++", Filename};
 127     Cmds.push_back(std::move(Cmd));
 128   }
 129   // Context provider that installs a configuration mutating foo's command.
 130   // This causes it to define foo::two instead of foo::one.
 131   // It also disables indexing of baz entirely.
 132   BackgroundIndex::Options Opts;
 133   Opts.ContextProvider = [](PathRef P) {
 134     Config C;
 135     if (P.endswith("foo.cpp"))
 136       C.CompileFlags.Edits.push_back([](std::vector<std::string> &Argv) {
 137         Argv = tooling::getInsertArgumentAdjuster("-Done=two")(Argv, "");
 138       });
 139     if (P.endswith("baz.cpp"))
 140       C.Index.Background = Config::BackgroundPolicy::Skip;
 141     return Context::current().derive(Config::Key, std::move(C));
 142   };
 143   // Create the background index.
 144   llvm::StringMap<std::string> Storage;
 145   size_t CacheHits = 0;
 146   MemoryShardStorage MSS(Storage, CacheHits);
 147   // We need the CommandMangler, because that applies the config we're testing.
 148   OverlayCDB CDB(/*Base=*/nullptr, /*FallbackFlags=*/{},
 149                  tooling::ArgumentsAdjuster(CommandMangler::forTests()));
 150
 151   BackgroundIndex Idx(
 152       FS, CDB, [&](llvm::StringRef) { return &MSS; }, std::move(Opts));
 153   // Index the two files.
 154   for (auto &Cmd : Cmds) {
 155     std::string FullPath = testPath(Cmd.Filename);
 156     CDB.setCompileCommand(FullPath, std::move(Cmd));
 157   }
 158   // Wait for both files to be indexed.
 159   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 160   EXPECT_THAT(runFuzzyFind(Idx, ""),
 161               UnorderedElementsAre(qName("foo"), qName("foo::two"),
 162                                    qName("bar"), qName("bar::one")));
 163 }
 164
 165 TEST_F(BackgroundIndexTest, IndexTwoFiles) {
 166   MockFS FS;
 167   // a.h yields different symbols when included by A.cc vs B.cc.
 168   FS.Files[testPath("root/A.h")] = R"cpp(
 169       void common();
 170       void f_b();
 171       #if A
 172         class A_CC {};
 173       #else
 174         class B_CC{};
 175       #endif
 176       )cpp";
 177   FS.Files[testPath("root/A.cc")] =
 178       "#include \"A.h\"\nstatic void g() { (void)common; }";
 179   FS.Files[testPath("root/B.cc")] =
 180       R"cpp(
 181       #define A 0
 182       #include "A.h"
 183       void f_b() {
 184         (void)common;
 185         (void)common;
 186         (void)common;
 187         (void)common;
 188       })cpp";
 189   llvm::StringMap<std::string> Storage;
 190   size_t CacheHits = 0;
 191   MemoryShardStorage MSS(Storage, CacheHits);
 192   OverlayCDB CDB(/*Base=*/nullptr);
 193   BackgroundIndex::Options Opts;
 194   BackgroundIndex Idx(
 195       FS, CDB, [&](llvm::StringRef) { return &MSS; }, Opts);
 196
 197   tooling::CompileCommand Cmd;
 198   Cmd.Filename = testPath("root/A.cc");
 199   Cmd.Directory = testPath("root");
 200   Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")};
 201   CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 202
 203   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 204   EXPECT_THAT(runFuzzyFind(Idx, ""),
 205               UnorderedElementsAre(AllOf(named("common"), numReferences(1U)),
 206                                    AllOf(named("A_CC"), numReferences(0U)),
 207                                    AllOf(named("g"), numReferences(1U)),
 208                                    AllOf(named("f_b"), declared(),
 209                                          Not(defined()), numReferences(0U))));
 210
 211   Cmd.Filename = testPath("root/B.cc");
 212   Cmd.CommandLine = {"clang++", Cmd.Filename};
 213   CDB.setCompileCommand(testPath("root/B.cc"), Cmd);
 214
 215   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 216   // B_CC is dropped as we don't collect symbols from A.h in this compilation.
 217   EXPECT_THAT(runFuzzyFind(Idx, ""),
 218               UnorderedElementsAre(AllOf(named("common"), numReferences(5U)),
 219                                    AllOf(named("A_CC"), numReferences(0U)),
 220                                    AllOf(named("g"), numReferences(1U)),
 221                                    AllOf(named("f_b"), declared(), defined(),
 222                                          numReferences(1U))));
 223
 224   auto Syms = runFuzzyFind(Idx, "common");
 225   EXPECT_THAT(Syms, UnorderedElementsAre(named("common")));
 226   auto Common = *Syms.begin();
 227   EXPECT_THAT(getRefs(Idx, Common.ID),
 228               refsAre({fileURI("unittest:///root/A.h"),
 229                        fileURI("unittest:///root/A.cc"),
 230                        fileURI("unittest:///root/B.cc"),
 231                        fileURI("unittest:///root/B.cc"),
 232                        fileURI("unittest:///root/B.cc"),
 233                        fileURI("unittest:///root/B.cc")}));
 234 }
 235
 236 TEST_F(BackgroundIndexTest, MainFileRefs) {
 237   MockFS FS;
 238   FS.Files[testPath("root/A.h")] = R"cpp(
 239       void header_sym();
 240       )cpp";
 241   FS.Files[testPath("root/A.cc")] =
 242       "#include \"A.h\"\nstatic void main_sym() { (void)header_sym; }";
 243
 244   llvm::StringMap<std::string> Storage;
 245   size_t CacheHits = 0;
 246   MemoryShardStorage MSS(Storage, CacheHits);
 247   OverlayCDB CDB(/*Base=*/nullptr);
 248   BackgroundIndex::Options Opts;
 249   BackgroundIndex Idx(
 250       FS, CDB, [&](llvm::StringRef) { return &MSS; }, Opts);
 251
 252   tooling::CompileCommand Cmd;
 253   Cmd.Filename = testPath("root/A.cc");
 254   Cmd.Directory = testPath("root");
 255   Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
 256   CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 257
 258   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 259   EXPECT_THAT(
 260       runFuzzyFind(Idx, ""),
 261       UnorderedElementsAre(AllOf(named("header_sym"), numReferences(1U)),
 262                            AllOf(named("main_sym"), numReferences(1U))));
 263 }
 264
 265 TEST_F(BackgroundIndexTest, ShardStorageTest) {
 266   MockFS FS;
 267   FS.Files[testPath("root/A.h")] = R"cpp(
 268       void common();
 269       void f_b();
 270       class A_CC {};
 271       )cpp";
 272   FS.Files[testPath("root/A.cc")] = R"cpp(
 273       #include "A.h"
 274       void g() { (void)common; }
 275       class B_CC : public A_CC {};
 276       )cpp";
 277
 278   llvm::StringMap<std::string> Storage;
 279   size_t CacheHits = 0;
 280   MemoryShardStorage MSS(Storage, CacheHits);
 281
 282   tooling::CompileCommand Cmd;
 283   Cmd.Filename = testPath("root/A.cc");
 284   Cmd.Directory = testPath("root");
 285   Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
 286   // Check nothing is loaded from Storage, but A.cc and A.h has been stored.
 287   {
 288     OverlayCDB CDB(/*Base=*/nullptr);
 289     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 290                         /*Opts=*/{});
 291     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 292     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 293   }
 294   EXPECT_EQ(CacheHits, 0U);
 295   EXPECT_EQ(Storage.size(), 2U);
 296
 297   {
 298     OverlayCDB CDB(/*Base=*/nullptr);
 299     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 300                         /*Opts=*/{});
 301     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 302     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 303   }
 304   EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
 305   EXPECT_EQ(Storage.size(), 2U);
 306
 307   auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
 308   EXPECT_NE(ShardHeader, nullptr);
 309   EXPECT_THAT(
 310       *ShardHeader->Symbols,
 311       UnorderedElementsAre(named("common"), named("A_CC"),
 312                            AllOf(named("f_b"), declared(), Not(defined()))));
 313   for (const auto &Ref : *ShardHeader->Refs)
 314     EXPECT_THAT(Ref.second,
 315                 UnorderedElementsAre(fileURI("unittest:///root/A.h")));
 316
 317   auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
 318   EXPECT_NE(ShardSource, nullptr);
 319   EXPECT_THAT(*ShardSource->Symbols,
 320               UnorderedElementsAre(named("g"), named("B_CC")));
 321   for (const auto &Ref : *ShardSource->Refs)
 322     EXPECT_THAT(Ref.second,
 323                 UnorderedElementsAre(fileURI("unittest:///root/A.cc")));
 324
 325   // The BaseOf relationship between A_CC and B_CC is stored in both the file
 326   // containing the definition of the subject (A_CC) and the file containing
 327   // the definition of the object (B_CC).
 328   SymbolID A = findSymbol(*ShardHeader->Symbols, "A_CC").ID;
 329   SymbolID B = findSymbol(*ShardSource->Symbols, "B_CC").ID;
 330   EXPECT_THAT(*ShardHeader->Relations,
 331               UnorderedElementsAre(Relation{A, RelationKind::BaseOf, B}));
 332   EXPECT_THAT(*ShardSource->Relations,
 333               UnorderedElementsAre(Relation{A, RelationKind::BaseOf, B}));
 334 }
 335
 336 TEST_F(BackgroundIndexTest, DirectIncludesTest) {
 337   MockFS FS;
 338   FS.Files[testPath("root/B.h")] = "";
 339   FS.Files[testPath("root/A.h")] = R"cpp(
 340       #include "B.h"
 341       void common();
 342       void f_b();
 343       class A_CC {};
 344       )cpp";
 345   FS.Files[testPath("root/A.cc")] =
 346       "#include \"A.h\"\nvoid g() { (void)common; }";
 347
 348   llvm::StringMap<std::string> Storage;
 349   size_t CacheHits = 0;
 350   MemoryShardStorage MSS(Storage, CacheHits);
 351
 352   tooling::CompileCommand Cmd;
 353   Cmd.Filename = testPath("root/A.cc");
 354   Cmd.Directory = testPath("root");
 355   Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
 356   {
 357     OverlayCDB CDB(/*Base=*/nullptr);
 358     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 359                         /*Opts=*/{});
 360     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 361     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 362   }
 363
 364   auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
 365   EXPECT_TRUE(ShardSource->Sources);
 366   EXPECT_EQ(ShardSource->Sources->size(), 2U); // A.cc, A.h
 367   EXPECT_THAT(
 368       ShardSource->Sources->lookup("unittest:///root/A.cc").DirectIncludes,
 369       UnorderedElementsAre("unittest:///root/A.h"));
 370   EXPECT_NE(ShardSource->Sources->lookup("unittest:///root/A.cc").Digest,
 371             FileDigest{{0}});
 372   EXPECT_THAT(ShardSource->Sources->lookup("unittest:///root/A.h"),
 373               emptyIncludeNode());
 374
 375   auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
 376   EXPECT_TRUE(ShardHeader->Sources);
 377   EXPECT_EQ(ShardHeader->Sources->size(), 2U); // A.h, B.h
 378   EXPECT_THAT(
 379       ShardHeader->Sources->lookup("unittest:///root/A.h").DirectIncludes,
 380       UnorderedElementsAre("unittest:///root/B.h"));
 381   EXPECT_NE(ShardHeader->Sources->lookup("unittest:///root/A.h").Digest,
 382             FileDigest{{0}});
 383   EXPECT_THAT(ShardHeader->Sources->lookup("unittest:///root/B.h"),
 384               emptyIncludeNode());
 385 }
 386
 387 TEST_F(BackgroundIndexTest, ShardStorageLoad) {
 388   MockFS FS;
 389   FS.Files[testPath("root/A.h")] = R"cpp(
 390       void common();
 391       void f_b();
 392       class A_CC {};
 393       )cpp";
 394   FS.Files[testPath("root/A.cc")] =
 395       "#include \"A.h\"\nvoid g() { (void)common; }";
 396
 397   llvm::StringMap<std::string> Storage;
 398   size_t CacheHits = 0;
 399   MemoryShardStorage MSS(Storage, CacheHits);
 400
 401   tooling::CompileCommand Cmd;
 402   Cmd.Filename = testPath("root/A.cc");
 403   Cmd.Directory = testPath("root");
 404   Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
 405   // Check nothing is loaded from Storage, but A.cc and A.h has been stored.
 406   {
 407     OverlayCDB CDB(/*Base=*/nullptr);
 408     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 409                         /*Opts=*/{});
 410     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 411     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 412   }
 413
 414   // Change header.
 415   FS.Files[testPath("root/A.h")] = R"cpp(
 416       void common();
 417       void f_b();
 418       class A_CC {};
 419       class A_CCnew {};
 420       )cpp";
 421   {
 422     OverlayCDB CDB(/*Base=*/nullptr);
 423     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 424                         /*Opts=*/{});
 425     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 426     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 427   }
 428   EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
 429
 430   // Check if the new symbol has arrived.
 431   auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
 432   EXPECT_NE(ShardHeader, nullptr);
 433   EXPECT_THAT(*ShardHeader->Symbols, Contains(named("A_CCnew")));
 434
 435   // Change source.
 436   FS.Files[testPath("root/A.cc")] =
 437       "#include \"A.h\"\nvoid g() { (void)common; }\nvoid f_b() {}";
 438   {
 439     CacheHits = 0;
 440     OverlayCDB CDB(/*Base=*/nullptr);
 441     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 442                         /*Opts=*/{});
 443     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 444     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 445   }
 446   EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
 447
 448   // Check if the new symbol has arrived.
 449   ShardHeader = MSS.loadShard(testPath("root/A.h"));
 450   EXPECT_NE(ShardHeader, nullptr);
 451   EXPECT_THAT(*ShardHeader->Symbols, Contains(named("A_CCnew")));
 452   auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
 453   EXPECT_NE(ShardSource, nullptr);
 454   EXPECT_THAT(*ShardSource->Symbols,
 455               Contains(AllOf(named("f_b"), declared(), defined())));
 456 }
 457
 458 TEST_F(BackgroundIndexTest, ShardStorageEmptyFile) {
 459   MockFS FS;
 460   FS.Files[testPath("root/A.h")] = R"cpp(
 461       void common();
 462       void f_b();
 463       class A_CC {};
 464       )cpp";
 465   FS.Files[testPath("root/B.h")] = R"cpp(
 466       #include "A.h"
 467       )cpp";
 468   FS.Files[testPath("root/A.cc")] =
 469       "#include \"B.h\"\nvoid g() { (void)common; }";
 470
 471   llvm::StringMap<std::string> Storage;
 472   size_t CacheHits = 0;
 473   MemoryShardStorage MSS(Storage, CacheHits);
 474
 475   tooling::CompileCommand Cmd;
 476   Cmd.Filename = testPath("root/A.cc");
 477   Cmd.Directory = testPath("root");
 478   Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
 479   // Check that A.cc, A.h and B.h has been stored.
 480   {
 481     OverlayCDB CDB(/*Base=*/nullptr);
 482     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 483                         /*Opts=*/{});
 484     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 485     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 486   }
 487   EXPECT_THAT(Storage.keys(),
 488               UnorderedElementsAre(testPath("root/A.cc"), testPath("root/A.h"),
 489                                    testPath("root/B.h")));
 490   auto ShardHeader = MSS.loadShard(testPath("root/B.h"));
 491   EXPECT_NE(ShardHeader, nullptr);
 492   EXPECT_TRUE(ShardHeader->Symbols->empty());
 493
 494   // Check that A.cc, A.h and B.h has been loaded.
 495   {
 496     CacheHits = 0;
 497     OverlayCDB CDB(/*Base=*/nullptr);
 498     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 499                         /*Opts=*/{});
 500     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 501     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 502   }
 503   EXPECT_EQ(CacheHits, 3U);
 504
 505   // Update B.h to contain some symbols.
 506   FS.Files[testPath("root/B.h")] = R"cpp(
 507       #include "A.h"
 508       void new_func();
 509       )cpp";
 510   // Check that B.h has been stored with new contents.
 511   {
 512     CacheHits = 0;
 513     OverlayCDB CDB(/*Base=*/nullptr);
 514     BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 515                         /*Opts=*/{});
 516     CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
 517     ASSERT_TRUE(Idx.blockUntilIdleForTest());
 518   }
 519   EXPECT_EQ(CacheHits, 3U);
 520   ShardHeader = MSS.loadShard(testPath("root/B.h"));
 521   EXPECT_NE(ShardHeader, nullptr);
 522   EXPECT_THAT(*ShardHeader->Symbols,
 523               Contains(AllOf(named("new_func"), declared(), Not(defined()))));
 524 }
 525
 526 TEST_F(BackgroundIndexTest, NoDotsInAbsPath) {
 527   MockFS FS;
 528   llvm::StringMap<std::string> Storage;
 529   size_t CacheHits = 0;
 530   MemoryShardStorage MSS(Storage, CacheHits);
 531   OverlayCDB CDB(/*Base=*/nullptr);
 532   BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 533                       /*Opts=*/{});
 534   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 535
 536   tooling::CompileCommand Cmd;
 537   FS.Files[testPath("root/A.cc")] = "";
 538   Cmd.Filename = "../A.cc";
 539   Cmd.Directory = testPath("root/build");
 540   Cmd.CommandLine = {"clang++", "../A.cc"};
 541   CDB.setCompileCommand(testPath("root/build/../A.cc"), Cmd);
 542   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 543
 544   FS.Files[testPath("root/B.cc")] = "";
 545   Cmd.Filename = "./B.cc";
 546   Cmd.Directory = testPath("root");
 547   Cmd.CommandLine = {"clang++", "./B.cc"};
 548   CDB.setCompileCommand(testPath("root/./B.cc"), Cmd);
 549   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 550
 551   for (llvm::StringRef AbsPath : MSS.AccessedPaths.keys()) {
 552     EXPECT_FALSE(AbsPath.contains("./")) << AbsPath;
 553     EXPECT_FALSE(AbsPath.contains("../")) << AbsPath;
 554   }
 555 }
 556
 557 TEST_F(BackgroundIndexTest, UncompilableFiles) {
 558   MockFS FS;
 559   llvm::StringMap<std::string> Storage;
 560   size_t CacheHits = 0;
 561   MemoryShardStorage MSS(Storage, CacheHits);
 562   OverlayCDB CDB(/*Base=*/nullptr);
 563   BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 564                       /*Opts=*/{});
 565
 566   tooling::CompileCommand Cmd;
 567   FS.Files[testPath("A.h")] = "void foo();";
 568   FS.Files[testPath("B.h")] = "#include \"C.h\"\nasdf;";
 569   FS.Files[testPath("C.h")] = "";
 570   FS.Files[testPath("A.cc")] = R"cpp(
 571   #include "A.h"
 572   #include "B.h"
 573   #include "not_found_header.h"
 574
 575   void foo() {}
 576   )cpp";
 577   Cmd.Filename = "../A.cc";
 578   Cmd.Directory = testPath("build");
 579   Cmd.CommandLine = {"clang++", "../A.cc"};
 580   CDB.setCompileCommand(testPath("build/../A.cc"), Cmd);
 581   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 582
 583   EXPECT_THAT(Storage.keys(), ElementsAre(testPath("A.cc"), testPath("A.h"),
 584                                           testPath("B.h"), testPath("C.h")));
 585
 586   {
 587     auto Shard = MSS.loadShard(testPath("A.cc"));
 588     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre(named("foo")));
 589     EXPECT_THAT(Shard->Sources->keys(),
 590                 UnorderedElementsAre("unittest:///A.cc", "unittest:///A.h",
 591                                      "unittest:///B.h"));
 592     EXPECT_THAT(Shard->Sources->lookup("unittest:///A.cc"), hadErrors());
 593   }
 594
 595   {
 596     auto Shard = MSS.loadShard(testPath("A.h"));
 597     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre(named("foo")));
 598     EXPECT_THAT(Shard->Sources->keys(),
 599                 UnorderedElementsAre("unittest:///A.h"));
 600     EXPECT_THAT(Shard->Sources->lookup("unittest:///A.h"), hadErrors());
 601   }
 602
 603   {
 604     auto Shard = MSS.loadShard(testPath("B.h"));
 605     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre(named("asdf")));
 606     EXPECT_THAT(Shard->Sources->keys(),
 607                 UnorderedElementsAre("unittest:///B.h", "unittest:///C.h"));
 608     EXPECT_THAT(Shard->Sources->lookup("unittest:///B.h"), hadErrors());
 609   }
 610
 611   {
 612     auto Shard = MSS.loadShard(testPath("C.h"));
 613     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre());
 614     EXPECT_THAT(Shard->Sources->keys(),
 615                 UnorderedElementsAre("unittest:///C.h"));
 616     EXPECT_THAT(Shard->Sources->lookup("unittest:///C.h"), hadErrors());
 617   }
 618 }
 619
 620 TEST_F(BackgroundIndexTest, CmdLineHash) {
 621   MockFS FS;
 622   llvm::StringMap<std::string> Storage;
 623   size_t CacheHits = 0;
 624   MemoryShardStorage MSS(Storage, CacheHits);
 625   OverlayCDB CDB(/*Base=*/nullptr);
 626   BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 627                       /*Opts=*/{});
 628
 629   tooling::CompileCommand Cmd;
 630   FS.Files[testPath("A.cc")] = "#include \"A.h\"";
 631   FS.Files[testPath("A.h")] = "";
 632   Cmd.Filename = "../A.cc";
 633   Cmd.Directory = testPath("build");
 634   Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
 635   CDB.setCompileCommand(testPath("build/../A.cc"), Cmd);
 636   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 637
 638   EXPECT_THAT(Storage.keys(), ElementsAre(testPath("A.cc"), testPath("A.h")));
 639   // Make sure we only store the Cmd for main file.
 640   EXPECT_FALSE(MSS.loadShard(testPath("A.h"))->Cmd);
 641
 642   tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd;
 643   EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine);
 644   EXPECT_EQ(CmdStored.Directory, Cmd.Directory);
 645 }
 646
 647 TEST_F(BackgroundIndexTest, Reindex) {
 648   MockFS FS;
 649   llvm::StringMap<std::string> Storage;
 650   size_t CacheHits = 0;
 651   MemoryShardStorage MSS(Storage, CacheHits);
 652   OverlayCDB CDB(/*Base=*/nullptr);
 653   BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 654                       /*Opts=*/{});
 655
 656   // Index a file.
 657   FS.Files[testPath("A.cc")] = "int theOldFunction();";
 658   tooling::CompileCommand Cmd;
 659   Cmd.Filename = "../A.cc";
 660   Cmd.Directory = testPath("build");
 661   Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
 662   CDB.setCompileCommand(testPath("A.cc"), Cmd);
 663   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 664
 665   // Verify the result is indexed and stored.
 666   EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
 667   EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
 668   std::string OldShard = Storage.lookup(testPath("A.cc"));
 669   EXPECT_NE("", OldShard);
 670
 671   // Change the content and command, and notify to reindex it.
 672   Cmd.CommandLine.push_back("-DFOO");
 673   FS.Files[testPath("A.cc")] = "int theNewFunction();";
 674   CDB.setCompileCommand(testPath("A.cc"), Cmd);
 675   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 676
 677   // Currently, we will never index the same main file again.
 678   EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
 679   EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
 680   EXPECT_EQ(OldShard, Storage.lookup(testPath("A.cc")));
 681 }
 682
 683 class BackgroundIndexRebuilderTest : public testing::Test {
 684 protected:
 685   BackgroundIndexRebuilderTest()
 686       : Source(IndexContents::All), Target(std::make_unique<MemIndex>()),
 687         Rebuilder(&Target, &Source, /*Threads=*/10) {
 688     // Prepare FileSymbols with TestSymbol in it, for checkRebuild.
 689     TestSymbol.ID = SymbolID("foo");
 690   }
 691
 692   // Perform Action and determine whether it rebuilt the index or not.
 693   bool checkRebuild(std::function<void()> Action) {
 694     // Update name so we can tell if the index updates.
 695     VersionStorage.push_back("Sym" + std::to_string(++VersionCounter));
 696     TestSymbol.Name = VersionStorage.back();
 697     SymbolSlab::Builder SB;
 698     SB.insert(TestSymbol);
 699     Source.update("", std::make_unique<SymbolSlab>(std::move(SB).build()),
 700                   nullptr, nullptr, false);
 701     // Now maybe update the index.
 702     Action();
 703     // Now query the index to get the name count.
 704     std::string ReadName;
 705     LookupRequest Req;
 706     Req.IDs.insert(TestSymbol.ID);
 707     Target.lookup(Req,
 708                   [&](const Symbol &S) { ReadName = std::string(S.Name); });
 709     // The index was rebuild if the name is up to date.
 710     return ReadName == VersionStorage.back();
 711   }
 712
 713   Symbol TestSymbol;
 714   FileSymbols Source;
 715   SwapIndex Target;
 716   BackgroundIndexRebuilder Rebuilder;
 717
 718   unsigned VersionCounter = 0;
 719   std::deque<std::string> VersionStorage;
 720 };
 721
 722 TEST_F(BackgroundIndexRebuilderTest, IndexingTUs) {
 723   for (unsigned I = 0; I < Rebuilder.TUsBeforeFirstBuild - 1; ++I)
 724     EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 725   EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 726   for (unsigned I = 0; I < Rebuilder.TUsBeforeRebuild - 1; ++I)
 727     EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 728   EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 729 }
 730
 731 TEST_F(BackgroundIndexRebuilderTest, LoadingShards) {
 732   Rebuilder.startLoading();
 733   Rebuilder.loadedShard(10);
 734   Rebuilder.loadedShard(20);
 735   EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 736
 737   // No rebuild for no shards.
 738   Rebuilder.startLoading();
 739   EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 740
 741   // Loads can overlap.
 742   Rebuilder.startLoading();
 743   Rebuilder.loadedShard(1);
 744   Rebuilder.startLoading();
 745   Rebuilder.loadedShard(1);
 746   EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 747   Rebuilder.loadedShard(1);
 748   EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 749
 750   // No rebuilding for indexed files while loading.
 751   Rebuilder.startLoading();
 752   for (unsigned I = 0; I < 3 * Rebuilder.TUsBeforeRebuild; ++I)
 753     EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 754   // But they get indexed when we're done, even if no shards were loaded.
 755   EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 756 }
 757
 758 TEST(BackgroundQueueTest, Priority) {
 759   // Create high and low priority tasks.
 760   // Once a bunch of high priority tasks have run, the queue is stopped.
 761   // So the low priority tasks should never run.
 762   BackgroundQueue Q;
 763   std::atomic<unsigned> HiRan(0), LoRan(0);
 764   BackgroundQueue::Task Lo([&] { ++LoRan; });
 765   BackgroundQueue::Task Hi([&] {
 766     if (++HiRan >= 10)
 767       Q.stop();
 768   });
 769   Hi.QueuePri = 100;
 770
 771   // Enqueuing the low-priority ones first shouldn't make them run first.
 772   Q.append(std::vector<BackgroundQueue::Task>(30, Lo));
 773   for (unsigned I = 0; I < 30; ++I)
 774     Q.push(Hi);
 775
 776   AsyncTaskRunner ThreadPool;
 777   for (unsigned I = 0; I < 5; ++I)
 778     ThreadPool.runAsync("worker", [&] { Q.work(); });
 779   // We should test enqueue with active workers, but it's hard to avoid races.
 780   // Just make sure we don't crash.
 781   Q.push(Lo);
 782   Q.append(std::vector<BackgroundQueue::Task>(2, Hi));
 783
 784   // After finishing, check the tasks that ran.
 785   ThreadPool.wait();
 786   EXPECT_GE(HiRan, 10u);
 787   EXPECT_EQ(LoRan, 0u);
 788 }
 789
 790 TEST(BackgroundQueueTest, Boost) {
 791   std::string Sequence;
 792
 793   BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
 794   A.Tag = "A";
 795   A.QueuePri = 1;
 796
 797   BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
 798   B.QueuePri = 2;
 799   B.Tag = "B";
 800
 801   {
 802     BackgroundQueue Q;
 803     Q.append({A, B});
 804     Q.work([&] { Q.stop(); });
 805     EXPECT_EQ("BA", Sequence) << "priority order";
 806   }
 807   Sequence.clear();
 808   {
 809     BackgroundQueue Q;
 810     Q.boost("A", 3);
 811     Q.append({A, B});
 812     Q.work([&] { Q.stop(); });
 813     EXPECT_EQ("AB", Sequence) << "A was boosted before enqueueing";
 814   }
 815   Sequence.clear();
 816   {
 817     BackgroundQueue Q;
 818     Q.append({A, B});
 819     Q.boost("A", 3);
 820     Q.work([&] { Q.stop(); });
 821     EXPECT_EQ("AB", Sequence) << "A was boosted after enqueueing";
 822   }
 823 }
 824
 825 TEST(BackgroundQueueTest, Duplicates) {
 826   std::string Sequence;
 827   BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
 828   A.QueuePri = 100;
 829   A.Key = 1;
 830   BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
 831   // B has no key, and is not subject to duplicate detection.
 832   B.QueuePri = 50;
 833
 834   BackgroundQueue Q;
 835   Q.append({A, B, A, B}); // One A is dropped, the other is high priority.
 836   Q.work(/*OnIdle=*/[&] {
 837     // The first time we go idle, we enqueue the same task again.
 838     if (!llvm::is_contained(Sequence, ' ')) {
 839       Sequence.push_back(' ');
 840       Q.append({A, B, A, B}); // Both As are dropped.
 841     } else {
 842       Q.stop();
 843     }
 844   });
 845
 846   // This could reasonably be "ABB BBA", if we had good *re*indexing support.
 847   EXPECT_EQ("ABB BB", Sequence);
 848 }
 849
 850 TEST(BackgroundQueueTest, Progress) {
 851   using testing::AnyOf;
 852   BackgroundQueue::Stats S;
 853   BackgroundQueue Q([&](BackgroundQueue::Stats New) {
 854     // Verify values are sane.
 855     // Items are enqueued one at a time (at least in this test).
 856     EXPECT_THAT(New.Enqueued, AnyOf(S.Enqueued, S.Enqueued + 1));
 857     // Items are completed one at a time.
 858     EXPECT_THAT(New.Completed, AnyOf(S.Completed, S.Completed + 1));
 859     // Items are started or completed one at a time.
 860     EXPECT_THAT(New.Active, AnyOf(S.Active - 1, S.Active, S.Active + 1));
 861     // Idle point only advances in time.
 862     EXPECT_GE(New.LastIdle, S.LastIdle);
 863     // Idle point is a task that has been completed in the past.
 864     EXPECT_LE(New.LastIdle, New.Completed);
 865     // LastIdle is now only if we're really idle.
 866     EXPECT_EQ(New.LastIdle == New.Enqueued,
 867               New.Completed == New.Enqueued && New.Active == 0u);
 868     S = New;
 869   });
 870
 871   // Two types of tasks: a ping task enqueues a pong task.
 872   // This avoids all enqueues followed by all completions (boring!)
 873   std::atomic<int> PingCount(0), PongCount(0);
 874   BackgroundQueue::Task Pong([&] { ++PongCount; });
 875   BackgroundQueue::Task Ping([&] {
 876     ++PingCount;
 877     Q.push(Pong);
 878   });
 879
 880   for (int I = 0; I < 1000; ++I)
 881     Q.push(Ping);
 882   // Spin up some workers and stop while idle.
 883   AsyncTaskRunner ThreadPool;
 884   for (unsigned I = 0; I < 5; ++I)
 885     ThreadPool.runAsync("worker", [&] { Q.work([&] { Q.stop(); }); });
 886   ThreadPool.wait();
 887
 888   // Everything's done, check final stats.
 889   // Assertions above ensure we got from 0 to 2000 in a reasonable way.
 890   EXPECT_EQ(PingCount.load(), 1000);
 891   EXPECT_EQ(PongCount.load(), 1000);
 892   EXPECT_EQ(S.Active, 0u);
 893   EXPECT_EQ(S.Enqueued, 2000u);
 894   EXPECT_EQ(S.Completed, 2000u);
 895   EXPECT_EQ(S.LastIdle, 2000u);
 896 }
 897
 898 TEST(BackgroundIndex, Profile) {
 899   MockFS FS;
 900   MockCompilationDatabase CDB;
 901   BackgroundIndex Idx(FS, CDB, [](llvm::StringRef) { return nullptr; },
 902                       /*Opts=*/{});
 903
 904   llvm::BumpPtrAllocator Alloc;
 905   MemoryTree MT(&Alloc);
 906   Idx.profile(MT);
 907   ASSERT_THAT(MT.children(),
 908               UnorderedElementsAre(Pair("slabs", _), Pair("index", _)));
 909 }
 910
 911 } // namespace clangd
 912 } // namespace clang