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.contains(ShardIdentifier)) {
  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.ends_with("foo.cpp"))
 136       C.CompileFlags.Edits.push_back([](std::vector<std::string> &Argv) {
 137         Argv = tooling::getInsertArgumentAdjuster("-Done=two")(Argv, "");
 138       });
 139     if (P.ends_with("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                  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(),
 584               UnorderedElementsAre(testPath("A.cc"), testPath("A.h"),
 585                                    testPath("B.h"), testPath("C.h")));
 586
 587   {
 588     auto Shard = MSS.loadShard(testPath("A.cc"));
 589     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre(named("foo")));
 590     EXPECT_THAT(Shard->Sources->keys(),
 591                 UnorderedElementsAre("unittest:///A.cc", "unittest:///A.h",
 592                                      "unittest:///B.h"));
 593     EXPECT_THAT(Shard->Sources->lookup("unittest:///A.cc"), hadErrors());
 594   }
 595
 596   {
 597     auto Shard = MSS.loadShard(testPath("A.h"));
 598     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre(named("foo")));
 599     EXPECT_THAT(Shard->Sources->keys(),
 600                 UnorderedElementsAre("unittest:///A.h"));
 601     EXPECT_THAT(Shard->Sources->lookup("unittest:///A.h"), hadErrors());
 602   }
 603
 604   {
 605     auto Shard = MSS.loadShard(testPath("B.h"));
 606     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre(named("asdf")));
 607     EXPECT_THAT(Shard->Sources->keys(),
 608                 UnorderedElementsAre("unittest:///B.h", "unittest:///C.h"));
 609     EXPECT_THAT(Shard->Sources->lookup("unittest:///B.h"), hadErrors());
 610   }
 611
 612   {
 613     auto Shard = MSS.loadShard(testPath("C.h"));
 614     EXPECT_THAT(*Shard->Symbols, UnorderedElementsAre());
 615     EXPECT_THAT(Shard->Sources->keys(),
 616                 UnorderedElementsAre("unittest:///C.h"));
 617     EXPECT_THAT(Shard->Sources->lookup("unittest:///C.h"), hadErrors());
 618   }
 619 }
 620
 621 TEST_F(BackgroundIndexTest, CmdLineHash) {
 622   MockFS FS;
 623   llvm::StringMap<std::string> Storage;
 624   size_t CacheHits = 0;
 625   MemoryShardStorage MSS(Storage, CacheHits);
 626   OverlayCDB CDB(/*Base=*/nullptr);
 627   BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 628                       /*Opts=*/{});
 629
 630   tooling::CompileCommand Cmd;
 631   FS.Files[testPath("A.cc")] = "#include \"A.h\"";
 632   FS.Files[testPath("A.h")] = "";
 633   Cmd.Filename = "../A.cc";
 634   Cmd.Directory = testPath("build");
 635   Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
 636   CDB.setCompileCommand(testPath("build/../A.cc"), Cmd);
 637   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 638
 639   EXPECT_THAT(Storage.keys(),
 640               UnorderedElementsAre(testPath("A.cc"), testPath("A.h")));
 641   // Make sure we only store the Cmd for main file.
 642   EXPECT_FALSE(MSS.loadShard(testPath("A.h"))->Cmd);
 643
 644   tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd;
 645   EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine);
 646   EXPECT_EQ(CmdStored.Directory, Cmd.Directory);
 647 }
 648
 649 TEST_F(BackgroundIndexTest, Reindex) {
 650   MockFS FS;
 651   llvm::StringMap<std::string> Storage;
 652   size_t CacheHits = 0;
 653   MemoryShardStorage MSS(Storage, CacheHits);
 654   OverlayCDB CDB(/*Base=*/nullptr);
 655   BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
 656                       /*Opts=*/{});
 657
 658   // Index a file.
 659   FS.Files[testPath("A.cc")] = "int theOldFunction();";
 660   tooling::CompileCommand Cmd;
 661   Cmd.Filename = "../A.cc";
 662   Cmd.Directory = testPath("build");
 663   Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
 664   CDB.setCompileCommand(testPath("A.cc"), Cmd);
 665   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 666
 667   // Verify the result is indexed and stored.
 668   EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
 669   EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
 670   std::string OldShard = Storage.lookup(testPath("A.cc"));
 671   EXPECT_NE("", OldShard);
 672
 673   // Change the content and command, and notify to reindex it.
 674   Cmd.CommandLine.push_back("-DFOO");
 675   FS.Files[testPath("A.cc")] = "int theNewFunction();";
 676   CDB.setCompileCommand(testPath("A.cc"), Cmd);
 677   ASSERT_TRUE(Idx.blockUntilIdleForTest());
 678
 679   // Currently, we will never index the same main file again.
 680   EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
 681   EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
 682   EXPECT_EQ(OldShard, Storage.lookup(testPath("A.cc")));
 683 }
 684
 685 class BackgroundIndexRebuilderTest : public testing::Test {
 686 protected:
 687   BackgroundIndexRebuilderTest()
 688       : Source(IndexContents::All), Target(std::make_unique<MemIndex>()),
 689         Rebuilder(&Target, &Source, /*Threads=*/10) {
 690     // Prepare FileSymbols with TestSymbol in it, for checkRebuild.
 691     TestSymbol.ID = SymbolID("foo");
 692   }
 693
 694   // Perform Action and determine whether it rebuilt the index or not.
 695   bool checkRebuild(std::function<void()> Action) {
 696     // Update name so we can tell if the index updates.
 697     VersionStorage.push_back("Sym" + std::to_string(++VersionCounter));
 698     TestSymbol.Name = VersionStorage.back();
 699     SymbolSlab::Builder SB;
 700     SB.insert(TestSymbol);
 701     Source.update("", std::make_unique<SymbolSlab>(std::move(SB).build()),
 702                   nullptr, nullptr, false);
 703     // Now maybe update the index.
 704     Action();
 705     // Now query the index to get the name count.
 706     std::string ReadName;
 707     LookupRequest Req;
 708     Req.IDs.insert(TestSymbol.ID);
 709     Target.lookup(Req,
 710                   [&](const Symbol &S) { ReadName = std::string(S.Name); });
 711     // The index was rebuild if the name is up to date.
 712     return ReadName == VersionStorage.back();
 713   }
 714
 715   Symbol TestSymbol;
 716   FileSymbols Source;
 717   SwapIndex Target;
 718   BackgroundIndexRebuilder Rebuilder;
 719
 720   unsigned VersionCounter = 0;
 721   std::deque<std::string> VersionStorage;
 722 };
 723
 724 TEST_F(BackgroundIndexRebuilderTest, IndexingTUs) {
 725   for (unsigned I = 0; I < Rebuilder.TUsBeforeFirstBuild - 1; ++I)
 726     EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 727   EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 728   for (unsigned I = 0; I < Rebuilder.TUsBeforeRebuild - 1; ++I)
 729     EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 730   EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 731 }
 732
 733 TEST_F(BackgroundIndexRebuilderTest, LoadingShards) {
 734   Rebuilder.startLoading();
 735   Rebuilder.loadedShard(10);
 736   Rebuilder.loadedShard(20);
 737   EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 738
 739   // No rebuild for no shards.
 740   Rebuilder.startLoading();
 741   EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 742
 743   // Loads can overlap.
 744   Rebuilder.startLoading();
 745   Rebuilder.loadedShard(1);
 746   Rebuilder.startLoading();
 747   Rebuilder.loadedShard(1);
 748   EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 749   Rebuilder.loadedShard(1);
 750   EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 751
 752   // No rebuilding for indexed files while loading.
 753   Rebuilder.startLoading();
 754   for (unsigned I = 0; I < 3 * Rebuilder.TUsBeforeRebuild; ++I)
 755     EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
 756   // But they get indexed when we're done, even if no shards were loaded.
 757   EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
 758 }
 759
 760 TEST(BackgroundQueueTest, Priority) {
 761   // Create high and low priority tasks.
 762   // Once a bunch of high priority tasks have run, the queue is stopped.
 763   // So the low priority tasks should never run.
 764   BackgroundQueue Q;
 765   std::atomic<unsigned> HiRan(0), LoRan(0);
 766   BackgroundQueue::Task Lo([&] { ++LoRan; });
 767   BackgroundQueue::Task Hi([&] {
 768     if (++HiRan >= 10)
 769       Q.stop();
 770   });
 771   Hi.QueuePri = 100;
 772
 773   // Enqueuing the low-priority ones first shouldn't make them run first.
 774   Q.append(std::vector<BackgroundQueue::Task>(30, Lo));
 775   for (unsigned I = 0; I < 30; ++I)
 776     Q.push(Hi);
 777
 778   AsyncTaskRunner ThreadPool;
 779   for (unsigned I = 0; I < 5; ++I)
 780     ThreadPool.runAsync("worker", [&] { Q.work(); });
 781   // We should test enqueue with active workers, but it's hard to avoid races.
 782   // Just make sure we don't crash.
 783   Q.push(Lo);
 784   Q.append(std::vector<BackgroundQueue::Task>(2, Hi));
 785
 786   // After finishing, check the tasks that ran.
 787   ThreadPool.wait();
 788   EXPECT_GE(HiRan, 10u);
 789   EXPECT_EQ(LoRan, 0u);
 790 }
 791
 792 TEST(BackgroundQueueTest, Boost) {
 793   std::string Sequence;
 794
 795   BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
 796   A.Tag = "A";
 797   A.QueuePri = 1;
 798
 799   BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
 800   B.QueuePri = 2;
 801   B.Tag = "B";
 802
 803   {
 804     BackgroundQueue Q;
 805     Q.append({A, B});
 806     Q.work([&] { Q.stop(); });
 807     EXPECT_EQ("BA", Sequence) << "priority order";
 808   }
 809   Sequence.clear();
 810   {
 811     BackgroundQueue Q;
 812     Q.boost("A", 3);
 813     Q.append({A, B});
 814     Q.work([&] { Q.stop(); });
 815     EXPECT_EQ("AB", Sequence) << "A was boosted before enqueueing";
 816   }
 817   Sequence.clear();
 818   {
 819     BackgroundQueue Q;
 820     Q.append({A, B});
 821     Q.boost("A", 3);
 822     Q.work([&] { Q.stop(); });
 823     EXPECT_EQ("AB", Sequence) << "A was boosted after enqueueing";
 824   }
 825 }
 826
 827 TEST(BackgroundQueueTest, Duplicates) {
 828   std::string Sequence;
 829   BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
 830   A.QueuePri = 100;
 831   A.Key = 1;
 832   BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
 833   // B has no key, and is not subject to duplicate detection.
 834   B.QueuePri = 50;
 835
 836   BackgroundQueue Q;
 837   Q.append({A, B, A, B}); // One A is dropped, the other is high priority.
 838   Q.work(/*OnIdle=*/[&] {
 839     // The first time we go idle, we enqueue the same task again.
 840     if (!llvm::is_contained(Sequence, ' ')) {
 841       Sequence.push_back(' ');
 842       Q.append({A, B, A, B}); // Both As are dropped.
 843     } else {
 844       Q.stop();
 845     }
 846   });
 847
 848   // This could reasonably be "ABB BBA", if we had good *re*indexing support.
 849   EXPECT_EQ("ABB BB", Sequence);
 850 }
 851
 852 TEST(BackgroundQueueTest, Progress) {
 853   using testing::AnyOf;
 854   BackgroundQueue::Stats S;
 855   BackgroundQueue Q([&](BackgroundQueue::Stats New) {
 856     // Verify values are sane.
 857     // Items are enqueued one at a time (at least in this test).
 858     EXPECT_THAT(New.Enqueued, AnyOf(S.Enqueued, S.Enqueued + 1));
 859     // Items are completed one at a time.
 860     EXPECT_THAT(New.Completed, AnyOf(S.Completed, S.Completed + 1));
 861     // Items are started or completed one at a time.
 862     EXPECT_THAT(New.Active, AnyOf(S.Active - 1, S.Active, S.Active + 1));
 863     // Idle point only advances in time.
 864     EXPECT_GE(New.LastIdle, S.LastIdle);
 865     // Idle point is a task that has been completed in the past.
 866     EXPECT_LE(New.LastIdle, New.Completed);
 867     // LastIdle is now only if we're really idle.
 868     EXPECT_EQ(New.LastIdle == New.Enqueued,
 869               New.Completed == New.Enqueued && New.Active == 0u);
 870     S = New;
 871   });
 872
 873   // Two types of tasks: a ping task enqueues a pong task.
 874   // This avoids all enqueues followed by all completions (boring!)
 875   std::atomic<int> PingCount(0), PongCount(0);
 876   BackgroundQueue::Task Pong([&] { ++PongCount; });
 877   BackgroundQueue::Task Ping([&] {
 878     ++PingCount;
 879     Q.push(Pong);
 880   });
 881
 882   for (int I = 0; I < 1000; ++I)
 883     Q.push(Ping);
 884   // Spin up some workers and stop while idle.
 885   AsyncTaskRunner ThreadPool;
 886   for (unsigned I = 0; I < 5; ++I)
 887     ThreadPool.runAsync("worker", [&] { Q.work([&] { Q.stop(); }); });
 888   ThreadPool.wait();
 889
 890   // Everything's done, check final stats.
 891   // Assertions above ensure we got from 0 to 2000 in a reasonable way.
 892   EXPECT_EQ(PingCount.load(), 1000);
 893   EXPECT_EQ(PongCount.load(), 1000);
 894   EXPECT_EQ(S.Active, 0u);
 895   EXPECT_EQ(S.Enqueued, 2000u);
 896   EXPECT_EQ(S.Completed, 2000u);
 897   EXPECT_EQ(S.LastIdle, 2000u);
 898 }
 899
 900 TEST(BackgroundIndex, Profile) {
 901   MockFS FS;
 902   MockCompilationDatabase CDB;
 903   BackgroundIndex Idx(FS, CDB, [](llvm::StringRef) { return nullptr; },
 904                       /*Opts=*/{});
 905
 906   llvm::BumpPtrAllocator Alloc;
 907   MemoryTree MT(&Alloc);
 908   Idx.profile(MT);
 909   ASSERT_THAT(MT.children(),
 910               UnorderedElementsAre(Pair("slabs", _), Pair("index", _)));
 911 }
 912
 913 } // namespace clangd
 914 } // namespace clang