1 #include "CompileCommands.h"
2 #include "Config.h"
3 #include "Headers.h"
4 #include "SyncAPI.h"
5 #include "TestFS.h"
6 #include "TestIndex.h"
7 #include "TestTU.h"
8 #include "index/Background.h"
9 #include "index/BackgroundRebuild.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 "llvm/Support/Threading.h"
15 #include "gmock/gmock.h"
16 #include "gtest/gtest.h"
17 #include <deque>
18 #include <thread>
19
20 using ::testing::_;
21 using ::testing::AllOf;
22 using ::testing::Contains;
23 using ::testing::ElementsAre;
24 using ::testing::Not;
25 using ::testing::Pair;
26 using ::testing::UnorderedElementsAre;
27
28 namespace clang {
29 namespace clangd {
30
31 MATCHER_P(Named, N, "") { return arg.Name == N; }
32 MATCHER_P(QName, N, "") { return (arg.Scope + arg.Name).str() == N; }
33 MATCHER(Declared, "") {
34 return !StringRef(arg.CanonicalDeclaration.FileURI).empty();
35 }
36 MATCHER(Defined, "") { return !StringRef(arg.Definition.FileURI).empty(); }
37 MATCHER_P(FileURI, F, "") { return StringRef(arg.Location.FileURI) == F; }
38 ::testing::Matcher<const RefSlab &>
RefsAre(std::vector<::testing::Matcher<Ref>> Matchers)39 RefsAre(std::vector<::testing::Matcher<Ref>> Matchers) {
40 return ElementsAre(::testing::Pair(_, UnorderedElementsAreArray(Matchers)));
41 }
42 // URI cannot be empty since it references keys in the IncludeGraph.
43 MATCHER(EmptyIncludeNode, "") {
44 return arg.Flags == IncludeGraphNode::SourceFlag::None && !arg.URI.empty() &&
45 arg.Digest == FileDigest{{0}} && arg.DirectIncludes.empty();
46 }
47
48 MATCHER(HadErrors, "") {
49 return arg.Flags & IncludeGraphNode::SourceFlag::HadErrors;
50 }
51
52 MATCHER_P(NumReferences, N, "") { return arg.References == N; }
53
54 class MemoryShardStorage : public BackgroundIndexStorage {
55 mutable std::mutex StorageMu;
56 llvm::StringMap<std::string> &Storage;
57 size_t &CacheHits;
58
59 public:
MemoryShardStorage(llvm::StringMap<std::string> & Storage,size_t & CacheHits)60 MemoryShardStorage(llvm::StringMap<std::string> &Storage, size_t &CacheHits)
61 : Storage(Storage), CacheHits(CacheHits) {}
storeShard(llvm::StringRef ShardIdentifier,IndexFileOut Shard) const62 llvm::Error storeShard(llvm::StringRef ShardIdentifier,
63 IndexFileOut Shard) const override {
64 std::lock_guard<std::mutex> Lock(StorageMu);
65 AccessedPaths.insert(ShardIdentifier);
66 Storage[ShardIdentifier] = llvm::to_string(Shard);
67 return llvm::Error::success();
68 }
69 std::unique_ptr<IndexFileIn>
loadShard(llvm::StringRef ShardIdentifier) const70 loadShard(llvm::StringRef ShardIdentifier) const override {
71 std::lock_guard<std::mutex> Lock(StorageMu);
72 AccessedPaths.insert(ShardIdentifier);
73 if (Storage.find(ShardIdentifier) == Storage.end()) {
74 return nullptr;
75 }
76 auto IndexFile = readIndexFile(Storage[ShardIdentifier]);
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:
BackgroundIndexTest()91 BackgroundIndexTest() { BackgroundQueue::preventThreadStarvationInTests(); }
92 };
93
TEST_F(BackgroundIndexTest,NoCrashOnErrorFile)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
TEST_F(BackgroundIndexTest,Config)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
TEST_F(BackgroundIndexTest,IndexTwoFiles)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
TEST_F(BackgroundIndexTest,MainFileRefs)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
TEST_F(BackgroundIndexTest,ShardStorageTest)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 std::string A_CC = "";
273 FS.Files[testPath("root/A.cc")] = R"cpp(
274 #include "A.h"
275 void g() { (void)common; }
276 class B_CC : public A_CC {};
277 )cpp";
278
279 llvm::StringMap<std::string> Storage;
280 size_t CacheHits = 0;
281 MemoryShardStorage MSS(Storage, CacheHits);
282
283 tooling::CompileCommand Cmd;
284 Cmd.Filename = testPath("root/A.cc");
285 Cmd.Directory = testPath("root");
286 Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
287 // Check nothing is loaded from Storage, but A.cc and A.h has been stored.
288 {
289 OverlayCDB CDB(/*Base=*/nullptr);
290 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
291 /*Opts=*/{});
292 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
293 ASSERT_TRUE(Idx.blockUntilIdleForTest());
294 }
295 EXPECT_EQ(CacheHits, 0U);
296 EXPECT_EQ(Storage.size(), 2U);
297
298 {
299 OverlayCDB CDB(/*Base=*/nullptr);
300 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
301 /*Opts=*/{});
302 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
303 ASSERT_TRUE(Idx.blockUntilIdleForTest());
304 }
305 EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
306 EXPECT_EQ(Storage.size(), 2U);
307
308 auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
309 EXPECT_NE(ShardHeader, nullptr);
310 EXPECT_THAT(
311 *ShardHeader->Symbols,
312 UnorderedElementsAre(Named("common"), Named("A_CC"),
313 AllOf(Named("f_b"), Declared(), Not(Defined()))));
314 for (const auto &Ref : *ShardHeader->Refs)
315 EXPECT_THAT(Ref.second,
316 UnorderedElementsAre(FileURI("unittest:///root/A.h")));
317
318 auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
319 EXPECT_NE(ShardSource, nullptr);
320 EXPECT_THAT(*ShardSource->Symbols,
321 UnorderedElementsAre(Named("g"), Named("B_CC")));
322 for (const auto &Ref : *ShardSource->Refs)
323 EXPECT_THAT(Ref.second,
324 UnorderedElementsAre(FileURI("unittest:///root/A.cc")));
325
326 // The BaseOf relationship between A_CC and B_CC is stored in both the file
327 // containing the definition of the subject (A_CC) and the file containing
328 // the definition of the object (B_CC).
329 SymbolID A = findSymbol(*ShardHeader->Symbols, "A_CC").ID;
330 SymbolID B = findSymbol(*ShardSource->Symbols, "B_CC").ID;
331 EXPECT_THAT(*ShardHeader->Relations,
332 UnorderedElementsAre(Relation{A, RelationKind::BaseOf, B}));
333 EXPECT_THAT(*ShardSource->Relations,
334 UnorderedElementsAre(Relation{A, RelationKind::BaseOf, B}));
335 }
336
TEST_F(BackgroundIndexTest,DirectIncludesTest)337 TEST_F(BackgroundIndexTest, DirectIncludesTest) {
338 MockFS FS;
339 FS.Files[testPath("root/B.h")] = "";
340 FS.Files[testPath("root/A.h")] = R"cpp(
341 #include "B.h"
342 void common();
343 void f_b();
344 class A_CC {};
345 )cpp";
346 std::string A_CC = "#include \"A.h\"\nvoid g() { (void)common; }";
347 FS.Files[testPath("root/A.cc")] = A_CC;
348
349 llvm::StringMap<std::string> Storage;
350 size_t CacheHits = 0;
351 MemoryShardStorage MSS(Storage, CacheHits);
352
353 tooling::CompileCommand Cmd;
354 Cmd.Filename = testPath("root/A.cc");
355 Cmd.Directory = testPath("root");
356 Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
357 {
358 OverlayCDB CDB(/*Base=*/nullptr);
359 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
360 /*Opts=*/{});
361 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
362 ASSERT_TRUE(Idx.blockUntilIdleForTest());
363 }
364
365 auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
366 EXPECT_TRUE(ShardSource->Sources);
367 EXPECT_EQ(ShardSource->Sources->size(), 2U); // A.cc, A.h
368 EXPECT_THAT(
369 ShardSource->Sources->lookup("unittest:///root/A.cc").DirectIncludes,
370 UnorderedElementsAre("unittest:///root/A.h"));
371 EXPECT_NE(ShardSource->Sources->lookup("unittest:///root/A.cc").Digest,
372 FileDigest{{0}});
373 EXPECT_THAT(ShardSource->Sources->lookup("unittest:///root/A.h"),
374 EmptyIncludeNode());
375
376 auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
377 EXPECT_TRUE(ShardHeader->Sources);
378 EXPECT_EQ(ShardHeader->Sources->size(), 2U); // A.h, B.h
379 EXPECT_THAT(
380 ShardHeader->Sources->lookup("unittest:///root/A.h").DirectIncludes,
381 UnorderedElementsAre("unittest:///root/B.h"));
382 EXPECT_NE(ShardHeader->Sources->lookup("unittest:///root/A.h").Digest,
383 FileDigest{{0}});
384 EXPECT_THAT(ShardHeader->Sources->lookup("unittest:///root/B.h"),
385 EmptyIncludeNode());
386 }
387
TEST_F(BackgroundIndexTest,ShardStorageLoad)388 TEST_F(BackgroundIndexTest, ShardStorageLoad) {
389 MockFS FS;
390 FS.Files[testPath("root/A.h")] = R"cpp(
391 void common();
392 void f_b();
393 class A_CC {};
394 )cpp";
395 FS.Files[testPath("root/A.cc")] =
396 "#include \"A.h\"\nvoid g() { (void)common; }";
397
398 llvm::StringMap<std::string> Storage;
399 size_t CacheHits = 0;
400 MemoryShardStorage MSS(Storage, CacheHits);
401
402 tooling::CompileCommand Cmd;
403 Cmd.Filename = testPath("root/A.cc");
404 Cmd.Directory = testPath("root");
405 Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
406 // Check nothing is loaded from Storage, but A.cc and A.h has been stored.
407 {
408 OverlayCDB CDB(/*Base=*/nullptr);
409 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
410 /*Opts=*/{});
411 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
412 ASSERT_TRUE(Idx.blockUntilIdleForTest());
413 }
414
415 // Change header.
416 FS.Files[testPath("root/A.h")] = R"cpp(
417 void common();
418 void f_b();
419 class A_CC {};
420 class A_CCnew {};
421 )cpp";
422 {
423 OverlayCDB CDB(/*Base=*/nullptr);
424 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
425 /*Opts=*/{});
426 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
427 ASSERT_TRUE(Idx.blockUntilIdleForTest());
428 }
429 EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
430
431 // Check if the new symbol has arrived.
432 auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
433 EXPECT_NE(ShardHeader, nullptr);
434 EXPECT_THAT(*ShardHeader->Symbols, Contains(Named("A_CCnew")));
435
436 // Change source.
437 FS.Files[testPath("root/A.cc")] =
438 "#include \"A.h\"\nvoid g() { (void)common; }\nvoid f_b() {}";
439 {
440 CacheHits = 0;
441 OverlayCDB CDB(/*Base=*/nullptr);
442 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
443 /*Opts=*/{});
444 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
445 ASSERT_TRUE(Idx.blockUntilIdleForTest());
446 }
447 EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache.
448
449 // Check if the new symbol has arrived.
450 ShardHeader = MSS.loadShard(testPath("root/A.h"));
451 EXPECT_NE(ShardHeader, nullptr);
452 EXPECT_THAT(*ShardHeader->Symbols, Contains(Named("A_CCnew")));
453 auto ShardSource = MSS.loadShard(testPath("root/A.cc"));
454 EXPECT_NE(ShardSource, nullptr);
455 EXPECT_THAT(*ShardSource->Symbols,
456 Contains(AllOf(Named("f_b"), Declared(), Defined())));
457 }
458
TEST_F(BackgroundIndexTest,ShardStorageEmptyFile)459 TEST_F(BackgroundIndexTest, ShardStorageEmptyFile) {
460 MockFS FS;
461 FS.Files[testPath("root/A.h")] = R"cpp(
462 void common();
463 void f_b();
464 class A_CC {};
465 )cpp";
466 FS.Files[testPath("root/B.h")] = R"cpp(
467 #include "A.h"
468 )cpp";
469 FS.Files[testPath("root/A.cc")] =
470 "#include \"B.h\"\nvoid g() { (void)common; }";
471
472 llvm::StringMap<std::string> Storage;
473 size_t CacheHits = 0;
474 MemoryShardStorage MSS(Storage, CacheHits);
475
476 tooling::CompileCommand Cmd;
477 Cmd.Filename = testPath("root/A.cc");
478 Cmd.Directory = testPath("root");
479 Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
480 // Check that A.cc, A.h and B.h has been stored.
481 {
482 OverlayCDB CDB(/*Base=*/nullptr);
483 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
484 /*Opts=*/{});
485 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
486 ASSERT_TRUE(Idx.blockUntilIdleForTest());
487 }
488 EXPECT_THAT(Storage.keys(),
489 UnorderedElementsAre(testPath("root/A.cc"), testPath("root/A.h"),
490 testPath("root/B.h")));
491 auto ShardHeader = MSS.loadShard(testPath("root/B.h"));
492 EXPECT_NE(ShardHeader, nullptr);
493 EXPECT_TRUE(ShardHeader->Symbols->empty());
494
495 // Check that A.cc, A.h and B.h has been loaded.
496 {
497 CacheHits = 0;
498 OverlayCDB CDB(/*Base=*/nullptr);
499 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
500 /*Opts=*/{});
501 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
502 ASSERT_TRUE(Idx.blockUntilIdleForTest());
503 }
504 EXPECT_EQ(CacheHits, 3U);
505
506 // Update B.h to contain some symbols.
507 FS.Files[testPath("root/B.h")] = R"cpp(
508 #include "A.h"
509 void new_func();
510 )cpp";
511 // Check that B.h has been stored with new contents.
512 {
513 CacheHits = 0;
514 OverlayCDB CDB(/*Base=*/nullptr);
515 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
516 /*Opts=*/{});
517 CDB.setCompileCommand(testPath("root/A.cc"), Cmd);
518 ASSERT_TRUE(Idx.blockUntilIdleForTest());
519 }
520 EXPECT_EQ(CacheHits, 3U);
521 ShardHeader = MSS.loadShard(testPath("root/B.h"));
522 EXPECT_NE(ShardHeader, nullptr);
523 EXPECT_THAT(*ShardHeader->Symbols,
524 Contains(AllOf(Named("new_func"), Declared(), Not(Defined()))));
525 }
526
TEST_F(BackgroundIndexTest,NoDotsInAbsPath)527 TEST_F(BackgroundIndexTest, NoDotsInAbsPath) {
528 MockFS FS;
529 llvm::StringMap<std::string> Storage;
530 size_t CacheHits = 0;
531 MemoryShardStorage MSS(Storage, CacheHits);
532 OverlayCDB CDB(/*Base=*/nullptr);
533 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
534 /*Opts=*/{});
535 ASSERT_TRUE(Idx.blockUntilIdleForTest());
536
537 tooling::CompileCommand Cmd;
538 FS.Files[testPath("root/A.cc")] = "";
539 Cmd.Filename = "../A.cc";
540 Cmd.Directory = testPath("root/build");
541 Cmd.CommandLine = {"clang++", "../A.cc"};
542 CDB.setCompileCommand(testPath("root/build/../A.cc"), Cmd);
543 ASSERT_TRUE(Idx.blockUntilIdleForTest());
544
545 FS.Files[testPath("root/B.cc")] = "";
546 Cmd.Filename = "./B.cc";
547 Cmd.Directory = testPath("root");
548 Cmd.CommandLine = {"clang++", "./B.cc"};
549 CDB.setCompileCommand(testPath("root/./B.cc"), Cmd);
550 ASSERT_TRUE(Idx.blockUntilIdleForTest());
551
552 for (llvm::StringRef AbsPath : MSS.AccessedPaths.keys()) {
553 EXPECT_FALSE(AbsPath.contains("./")) << AbsPath;
554 EXPECT_FALSE(AbsPath.contains("../")) << AbsPath;
555 }
556 }
557
TEST_F(BackgroundIndexTest,UncompilableFiles)558 TEST_F(BackgroundIndexTest, UncompilableFiles) {
559 MockFS FS;
560 llvm::StringMap<std::string> Storage;
561 size_t CacheHits = 0;
562 MemoryShardStorage MSS(Storage, CacheHits);
563 OverlayCDB CDB(/*Base=*/nullptr);
564 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
565 /*Opts=*/{});
566
567 tooling::CompileCommand Cmd;
568 FS.Files[testPath("A.h")] = "void foo();";
569 FS.Files[testPath("B.h")] = "#include \"C.h\"\nasdf;";
570 FS.Files[testPath("C.h")] = "";
571 FS.Files[testPath("A.cc")] = R"cpp(
572 #include "A.h"
573 #include "B.h"
574 #include "not_found_header.h"
575
576 void foo() {}
577 )cpp";
578 Cmd.Filename = "../A.cc";
579 Cmd.Directory = testPath("build");
580 Cmd.CommandLine = {"clang++", "../A.cc"};
581 CDB.setCompileCommand(testPath("build/../A.cc"), Cmd);
582 ASSERT_TRUE(Idx.blockUntilIdleForTest());
583
584 EXPECT_THAT(Storage.keys(), ElementsAre(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
TEST_F(BackgroundIndexTest,CmdLineHash)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(), ElementsAre(testPath("A.cc"), testPath("A.h")));
640 // Make sure we only store the Cmd for main file.
641 EXPECT_FALSE(MSS.loadShard(testPath("A.h"))->Cmd);
642
643 tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd;
644 EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine);
645 EXPECT_EQ(CmdStored.Directory, Cmd.Directory);
646 }
647
TEST_F(BackgroundIndexTest,Reindex)648 TEST_F(BackgroundIndexTest, Reindex) {
649 MockFS FS;
650 llvm::StringMap<std::string> Storage;
651 size_t CacheHits = 0;
652 MemoryShardStorage MSS(Storage, CacheHits);
653 OverlayCDB CDB(/*Base=*/nullptr);
654 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
655 /*Opts=*/{});
656
657 // Index a file.
658 FS.Files[testPath("A.cc")] = "int theOldFunction();";
659 tooling::CompileCommand Cmd;
660 Cmd.Filename = "../A.cc";
661 Cmd.Directory = testPath("build");
662 Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
663 CDB.setCompileCommand(testPath("A.cc"), Cmd);
664 ASSERT_TRUE(Idx.blockUntilIdleForTest());
665
666 // Verify the result is indexed and stored.
667 EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
668 EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
669 std::string OldShard = Storage.lookup(testPath("A.cc"));
670 EXPECT_NE("", OldShard);
671
672 // Change the content and command, and notify to reindex it.
673 Cmd.CommandLine.push_back("-DFOO");
674 FS.Files[testPath("A.cc")] = "int theNewFunction();";
675 CDB.setCompileCommand(testPath("A.cc"), Cmd);
676 ASSERT_TRUE(Idx.blockUntilIdleForTest());
677
678 // Currently, we will never index the same main file again.
679 EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size());
680 EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size());
681 EXPECT_EQ(OldShard, Storage.lookup(testPath("A.cc")));
682 }
683
684 class BackgroundIndexRebuilderTest : public testing::Test {
685 protected:
BackgroundIndexRebuilderTest()686 BackgroundIndexRebuilderTest()
687 : Source(IndexContents::All), Target(std::make_unique<MemIndex>()),
688 Rebuilder(&Target, &Source, /*Threads=*/10) {
689 // Prepare FileSymbols with TestSymbol in it, for checkRebuild.
690 TestSymbol.ID = SymbolID("foo");
691 }
692
693 // Perform Action and determine whether it rebuilt the index or not.
checkRebuild(std::function<void ()> Action)694 bool checkRebuild(std::function<void()> Action) {
695 // Update name so we can tell if the index updates.
696 VersionStorage.push_back("Sym" + std::to_string(++VersionCounter));
697 TestSymbol.Name = VersionStorage.back();
698 SymbolSlab::Builder SB;
699 SB.insert(TestSymbol);
700 Source.update("", std::make_unique<SymbolSlab>(std::move(SB).build()),
701 nullptr, nullptr, false);
702 // Now maybe update the index.
703 Action();
704 // Now query the index to get the name count.
705 std::string ReadName;
706 LookupRequest Req;
707 Req.IDs.insert(TestSymbol.ID);
708 Target.lookup(Req,
709 [&](const Symbol &S) { ReadName = std::string(S.Name); });
710 // The index was rebuild if the name is up to date.
711 return ReadName == VersionStorage.back();
712 }
713
714 Symbol TestSymbol;
715 FileSymbols Source;
716 SwapIndex Target;
717 BackgroundIndexRebuilder Rebuilder;
718
719 unsigned VersionCounter = 0;
720 std::deque<std::string> VersionStorage;
721 };
722
TEST_F(BackgroundIndexRebuilderTest,IndexingTUs)723 TEST_F(BackgroundIndexRebuilderTest, IndexingTUs) {
724 for (unsigned I = 0; I < Rebuilder.TUsBeforeFirstBuild - 1; ++I)
725 EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
726 EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
727 for (unsigned I = 0; I < Rebuilder.TUsBeforeRebuild - 1; ++I)
728 EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
729 EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
730 }
731
TEST_F(BackgroundIndexRebuilderTest,LoadingShards)732 TEST_F(BackgroundIndexRebuilderTest, LoadingShards) {
733 Rebuilder.startLoading();
734 Rebuilder.loadedShard(10);
735 Rebuilder.loadedShard(20);
736 EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
737
738 // No rebuild for no shards.
739 Rebuilder.startLoading();
740 EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
741
742 // Loads can overlap.
743 Rebuilder.startLoading();
744 Rebuilder.loadedShard(1);
745 Rebuilder.startLoading();
746 Rebuilder.loadedShard(1);
747 EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
748 Rebuilder.loadedShard(1);
749 EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
750
751 // No rebuilding for indexed files while loading.
752 Rebuilder.startLoading();
753 for (unsigned I = 0; I < 3 * Rebuilder.TUsBeforeRebuild; ++I)
754 EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
755 // But they get indexed when we're done, even if no shards were loaded.
756 EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
757 }
758
TEST(BackgroundQueueTest,Priority)759 TEST(BackgroundQueueTest, Priority) {
760 // Create high and low priority tasks.
761 // Once a bunch of high priority tasks have run, the queue is stopped.
762 // So the low priority tasks should never run.
763 BackgroundQueue Q;
764 std::atomic<unsigned> HiRan(0), LoRan(0);
765 BackgroundQueue::Task Lo([&] { ++LoRan; });
766 BackgroundQueue::Task Hi([&] {
767 if (++HiRan >= 10)
768 Q.stop();
769 });
770 Hi.QueuePri = 100;
771
772 // Enqueuing the low-priority ones first shouldn't make them run first.
773 Q.append(std::vector<BackgroundQueue::Task>(30, Lo));
774 for (unsigned I = 0; I < 30; ++I)
775 Q.push(Hi);
776
777 AsyncTaskRunner ThreadPool;
778 for (unsigned I = 0; I < 5; ++I)
779 ThreadPool.runAsync("worker", [&] { Q.work(); });
780 // We should test enqueue with active workers, but it's hard to avoid races.
781 // Just make sure we don't crash.
782 Q.push(Lo);
783 Q.append(std::vector<BackgroundQueue::Task>(2, Hi));
784
785 // After finishing, check the tasks that ran.
786 ThreadPool.wait();
787 EXPECT_GE(HiRan, 10u);
788 EXPECT_EQ(LoRan, 0u);
789 }
790
TEST(BackgroundQueueTest,Boost)791 TEST(BackgroundQueueTest, Boost) {
792 std::string Sequence;
793
794 BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
795 A.Tag = "A";
796 A.QueuePri = 1;
797
798 BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
799 B.QueuePri = 2;
800 B.Tag = "B";
801
802 {
803 BackgroundQueue Q;
804 Q.append({A, B});
805 Q.work([&] { Q.stop(); });
806 EXPECT_EQ("BA", Sequence) << "priority order";
807 }
808 Sequence.clear();
809 {
810 BackgroundQueue Q;
811 Q.boost("A", 3);
812 Q.append({A, B});
813 Q.work([&] { Q.stop(); });
814 EXPECT_EQ("AB", Sequence) << "A was boosted before enqueueing";
815 }
816 Sequence.clear();
817 {
818 BackgroundQueue Q;
819 Q.append({A, B});
820 Q.boost("A", 3);
821 Q.work([&] { Q.stop(); });
822 EXPECT_EQ("AB", Sequence) << "A was boosted after enqueueing";
823 }
824 }
825
TEST(BackgroundQueueTest,Duplicates)826 TEST(BackgroundQueueTest, Duplicates) {
827 std::string Sequence;
828 BackgroundQueue::Task A([&] { Sequence.push_back('A'); });
829 A.QueuePri = 100;
830 A.Key = 1;
831 BackgroundQueue::Task B([&] { Sequence.push_back('B'); });
832 // B has no key, and is not subject to duplicate detection.
833 B.QueuePri = 50;
834
835 BackgroundQueue Q;
836 Q.append({A, B, A, B}); // One A is dropped, the other is high priority.
837 Q.work(/*OnIdle=*/[&] {
838 // The first time we go idle, we enqueue the same task again.
839 if (!llvm::is_contained(Sequence, ' ')) {
840 Sequence.push_back(' ');
841 Q.append({A, B, A, B}); // Both As are dropped.
842 } else {
843 Q.stop();
844 }
845 });
846
847 // This could reasonably be "ABB BBA", if we had good *re*indexing support.
848 EXPECT_EQ("ABB BB", Sequence);
849 }
850
TEST(BackgroundQueueTest,Progress)851 TEST(BackgroundQueueTest, Progress) {
852 using testing::AnyOf;
853 BackgroundQueue::Stats S;
854 BackgroundQueue Q([&](BackgroundQueue::Stats New) {
855 // Verify values are sane.
856 // Items are enqueued one at a time (at least in this test).
857 EXPECT_THAT(New.Enqueued, AnyOf(S.Enqueued, S.Enqueued + 1));
858 // Items are completed one at a time.
859 EXPECT_THAT(New.Completed, AnyOf(S.Completed, S.Completed + 1));
860 // Items are started or completed one at a time.
861 EXPECT_THAT(New.Active, AnyOf(S.Active - 1, S.Active, S.Active + 1));
862 // Idle point only advances in time.
863 EXPECT_GE(New.LastIdle, S.LastIdle);
864 // Idle point is a task that has been completed in the past.
865 EXPECT_LE(New.LastIdle, New.Completed);
866 // LastIdle is now only if we're really idle.
867 EXPECT_EQ(New.LastIdle == New.Enqueued,
868 New.Completed == New.Enqueued && New.Active == 0u);
869 S = New;
870 });
871
872 // Two types of tasks: a ping task enqueues a pong task.
873 // This avoids all enqueues followed by all completions (boring!)
874 std::atomic<int> PingCount(0), PongCount(0);
875 BackgroundQueue::Task Pong([&] { ++PongCount; });
876 BackgroundQueue::Task Ping([&] {
877 ++PingCount;
878 Q.push(Pong);
879 });
880
881 for (int I = 0; I < 1000; ++I)
882 Q.push(Ping);
883 // Spin up some workers and stop while idle.
884 AsyncTaskRunner ThreadPool;
885 for (unsigned I = 0; I < 5; ++I)
886 ThreadPool.runAsync("worker", [&] { Q.work([&] { Q.stop(); }); });
887 ThreadPool.wait();
888
889 // Everything's done, check final stats.
890 // Assertions above ensure we got from 0 to 2000 in a reasonable way.
891 EXPECT_EQ(PingCount.load(), 1000);
892 EXPECT_EQ(PongCount.load(), 1000);
893 EXPECT_EQ(S.Active, 0u);
894 EXPECT_EQ(S.Enqueued, 2000u);
895 EXPECT_EQ(S.Completed, 2000u);
896 EXPECT_EQ(S.LastIdle, 2000u);
897 }
898
TEST(BackgroundIndex,Profile)899 TEST(BackgroundIndex, Profile) {
900 MockFS FS;
901 MockCompilationDatabase CDB;
902 BackgroundIndex Idx(FS, CDB, [](llvm::StringRef) { return nullptr; },
903 /*Opts=*/{});
904
905 llvm::BumpPtrAllocator Alloc;
906 MemoryTree MT(&Alloc);
907 Idx.profile(MT);
908 ASSERT_THAT(MT.children(),
909 UnorderedElementsAre(Pair("slabs", _), Pair("index", _)));
910 }
911
912 } // namespace clangd
913 } // namespace clang
914