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
19using ::testing::_;
20using ::testing::AllOf;
21using ::testing::Contains;
22using ::testing::ElementsAre;
23using ::testing::Not;
24using ::testing::Pair;
25using ::testing::UnorderedElementsAre;
26
27namespace clang {
28namespace clangd {
29
30MATCHER_P(named, N, "") { return arg.Name == N; }
31MATCHER_P(qName, N, "") { return (arg.Scope + arg.Name).str() == N; }
32MATCHER(declared, "") {
33 return !StringRef(arg.CanonicalDeclaration.FileURI).empty();
34}
35MATCHER(defined, "") { return !StringRef(arg.Definition.FileURI).empty(); }
36MATCHER_P(fileURI, F, "") { return StringRef(arg.Location.FileURI) == F; }
37::testing::Matcher<const RefSlab &>
38refsAre(std::vector<::testing::Matcher<Ref>> Matchers) {
39 return ElementsAre(matchers: ::testing::Pair(first_matcher: _, second_matcher: UnorderedElementsAreArray(container: Matchers)));
40}
41// URI cannot be empty since it references keys in the IncludeGraph.
42MATCHER(emptyIncludeNode, "") {
43 return arg.Flags == IncludeGraphNode::SourceFlag::None && !arg.URI.empty() &&
44 arg.Digest == FileDigest{._M_elems: {0}} && arg.DirectIncludes.empty();
45}
46
47MATCHER(hadErrors, "") {
48 return arg.Flags & IncludeGraphNode::SourceFlag::HadErrors;
49}
50
51MATCHER_P(numReferences, N, "") { return arg.References == N; }
52
53class MemoryShardStorage : public BackgroundIndexStorage {
54 mutable std::mutex StorageMu;
55 llvm::StringMap<std::string> &Storage;
56 size_t &CacheHits;
57
58public:
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(key: ShardIdentifier);
65 Storage[ShardIdentifier] = llvm::to_string(Value: 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(key: ShardIdentifier);
72 if (!Storage.contains(Key: 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>(args: std::move(*IndexFile));
84 }
85
86 mutable llvm::StringSet<> AccessedPaths;
87};
88
89class BackgroundIndexTest : public ::testing::Test {
90protected:
91 BackgroundIndexTest() { BackgroundQueue::preventThreadStarvationInTests(); }
92};
93
94TEST_F(BackgroundIndexTest, NoCrashOnErrorFile) {
95 MockFS FS;
96 FS.Files[testPath(File: "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(File: "root/A.cc");
106 Cmd.Directory = testPath(File: "root");
107 Cmd.CommandLine = {"clang++", "-DA=1", testPath(File: "root/A.cc")};
108 CDB.setCompileCommand(File: testPath(File: "root/A.cc"), CompilationCommand: Cmd);
109
110 ASSERT_TRUE(Idx.blockUntilIdleForTest());
111}
112
113TEST_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(x: 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(Suffix: "foo.cpp"))
136 C.CompileFlags.Edits.push_back(x: [](std::vector<std::string> &Argv) {
137 Argv = tooling::getInsertArgumentAdjuster(Extra: "-Done=two")(Argv, "");
138 });
139 if (P.ends_with(Suffix: "baz.cpp"))
140 C.Index.Background = Config::BackgroundPolicy::Skip;
141 return Context::current().derive(Key: Config::Key, Value: 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(File: Cmd.Filename);
156 CDB.setCompileCommand(File: FullPath, CompilationCommand: 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
165TEST_F(BackgroundIndexTest, IndexTwoFiles) {
166 MockFS FS;
167 // a.h yields different symbols when included by A.cc vs B.cc.
168 FS.Files[testPath(File: "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(File: "root/A.cc")] =
178 "#include \"A.h\"\nstatic void g() { (void)common; }";
179 FS.Files[testPath(File: "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(File: "root/A.cc");
199 Cmd.Directory = testPath(File: "root");
200 Cmd.CommandLine = {"clang++", "-DA=1", testPath(File: "root/A.cc")};
201 CDB.setCompileCommand(File: testPath(File: "root/A.cc"), CompilationCommand: 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(File: "root/B.cc");
212 Cmd.CommandLine = {"clang++", Cmd.Filename};
213 CDB.setCompileCommand(File: testPath(File: "root/B.cc"), CompilationCommand: 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(Index: Idx, Query: "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
236TEST_F(BackgroundIndexTest, MainFileRefs) {
237 MockFS FS;
238 FS.Files[testPath(File: "root/A.h")] = R"cpp(
239 void header_sym();
240 )cpp";
241 FS.Files[testPath(File: "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(File: "root/A.cc");
254 Cmd.Directory = testPath(File: "root");
255 Cmd.CommandLine = {"clang++", testPath(File: "root/A.cc")};
256 CDB.setCompileCommand(File: testPath(File: "root/A.cc"), CompilationCommand: 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
265TEST_F(BackgroundIndexTest, ShardStorageTest) {
266 MockFS FS;
267 FS.Files[testPath(File: "root/A.h")] = R"cpp(
268 void common();
269 void f_b();
270 class A_CC {};
271 )cpp";
272 FS.Files[testPath(File: "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(File: "root/A.cc");
284 Cmd.Directory = testPath(File: "root");
285 Cmd.CommandLine = {"clang++", testPath(File: "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(File: testPath(File: "root/A.cc"), CompilationCommand: 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(File: testPath(File: "root/A.cc"), CompilationCommand: 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(ShardIdentifier: testPath(File: "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(ShardIdentifier: testPath(File: "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, QName: "A_CC").ID;
329 SymbolID B = findSymbol(*ShardSource->Symbols, QName: "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
336TEST_F(BackgroundIndexTest, DirectIncludesTest) {
337 MockFS FS;
338 FS.Files[testPath(File: "root/B.h")] = "";
339 FS.Files[testPath(File: "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(File: "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(File: "root/A.cc");
354 Cmd.Directory = testPath(File: "root");
355 Cmd.CommandLine = {"clang++", testPath(File: "root/A.cc")};
356 {
357 OverlayCDB CDB(/*Base=*/nullptr);
358 BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; },
359 /*Opts=*/{});
360 CDB.setCompileCommand(File: testPath(File: "root/A.cc"), CompilationCommand: Cmd);
361 ASSERT_TRUE(Idx.blockUntilIdleForTest());
362 }
363
364 auto ShardSource = MSS.loadShard(ShardIdentifier: testPath(File: "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(ShardIdentifier: testPath(File: "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
387TEST_F(BackgroundIndexTest, ShardStorageLoad) {
388 MockFS FS;
389 FS.Files[testPath(File: "root/A.h")] = R"cpp(
390 void common();
391 void f_b();
392 class A_CC {};
393 )cpp";
394 FS.Files[testPath(File: "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(File: "root/A.cc");
403 Cmd.Directory = testPath(File: "root");
404 Cmd.CommandLine = {"clang++", testPath(File: "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(File: testPath(File: "root/A.cc"), CompilationCommand: Cmd);
411 ASSERT_TRUE(Idx.blockUntilIdleForTest());
412 }
413
414 // Change header.
415 FS.Files[testPath(File: "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(File: testPath(File: "root/A.cc"), CompilationCommand: 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(ShardIdentifier: testPath(File: "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(File: "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(File: testPath(File: "root/A.cc"), CompilationCommand: 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(ShardIdentifier: testPath(File: "root/A.h"));
450 EXPECT_NE(ShardHeader, nullptr);
451 EXPECT_THAT(*ShardHeader->Symbols, Contains(named("A_CCnew")));
452 auto ShardSource = MSS.loadShard(ShardIdentifier: testPath(File: "root/A.cc"));
453 EXPECT_NE(ShardSource, nullptr);
454 EXPECT_THAT(*ShardSource->Symbols,
455 Contains(AllOf(named("f_b"), declared(), defined())));
456}
457
458TEST_F(BackgroundIndexTest, ShardStorageEmptyFile) {
459 MockFS FS;
460 FS.Files[testPath(File: "root/A.h")] = R"cpp(
461 void common();
462 void f_b();
463 class A_CC {};
464 )cpp";
465 FS.Files[testPath(File: "root/B.h")] = R"cpp(
466 #include "A.h"
467 )cpp";
468 FS.Files[testPath(File: "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(File: "root/A.cc");
477 Cmd.Directory = testPath(File: "root");
478 Cmd.CommandLine = {"clang++", testPath(File: "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(File: testPath(File: "root/A.cc"), CompilationCommand: 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(ShardIdentifier: testPath(File: "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(File: testPath(File: "root/A.cc"), CompilationCommand: 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(File: "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(File: testPath(File: "root/A.cc"), CompilationCommand: Cmd);
517 ASSERT_TRUE(Idx.blockUntilIdleForTest());
518 }
519 EXPECT_EQ(CacheHits, 3U);
520 ShardHeader = MSS.loadShard(ShardIdentifier: testPath(File: "root/B.h"));
521 EXPECT_NE(ShardHeader, nullptr);
522 EXPECT_THAT(*ShardHeader->Symbols,
523 Contains(AllOf(named("new_func"), declared(), Not(defined()))));
524}
525
526TEST_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(File: "root/A.cc")] = "";
538 Cmd.Filename = "../A.cc";
539 Cmd.Directory = testPath(File: "root/build");
540 Cmd.CommandLine = {"clang++", "../A.cc"};
541 CDB.setCompileCommand(File: testPath(File: "root/build/../A.cc"), CompilationCommand: Cmd);
542 ASSERT_TRUE(Idx.blockUntilIdleForTest());
543
544 FS.Files[testPath(File: "root/B.cc")] = "";
545 Cmd.Filename = "./B.cc";
546 Cmd.Directory = testPath(File: "root");
547 Cmd.CommandLine = {"clang++", "./B.cc"};
548 CDB.setCompileCommand(File: testPath(File: "root/./B.cc"), CompilationCommand: 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
557TEST_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(File: "A.h")] = "void foo();";
568 FS.Files[testPath(File: "B.h")] = "#include \"C.h\"\nasdf;";
569 FS.Files[testPath(File: "C.h")] = "";
570 FS.Files[testPath(File: "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(File: "build");
579 Cmd.CommandLine = {"clang++", "../A.cc"};
580 CDB.setCompileCommand(File: testPath(File: "build/../A.cc"), CompilationCommand: 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(ShardIdentifier: testPath(File: "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(ShardIdentifier: testPath(File: "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(ShardIdentifier: testPath(File: "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(ShardIdentifier: testPath(File: "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
621TEST_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(File: "A.cc")] = "#include \"A.h\"";
632 FS.Files[testPath(File: "A.h")] = "";
633 Cmd.Filename = "../A.cc";
634 Cmd.Directory = testPath(File: "build");
635 Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
636 CDB.setCompileCommand(File: testPath(File: "build/../A.cc"), CompilationCommand: 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(ShardIdentifier: testPath(File: "A.cc"))->Cmd;
645 EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine);
646 EXPECT_EQ(CmdStored.Directory, Cmd.Directory);
647}
648
649TEST_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(File: "A.cc")] = "int theOldFunction();";
660 tooling::CompileCommand Cmd;
661 Cmd.Filename = "../A.cc";
662 Cmd.Directory = testPath(File: "build");
663 Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"};
664 CDB.setCompileCommand(File: testPath(File: "A.cc"), CompilationCommand: 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(Key: testPath(File: "A.cc"));
671 EXPECT_NE("", OldShard);
672
673 // Change the content and command, and notify to reindex it.
674 Cmd.CommandLine.push_back(x: "-DFOO");
675 FS.Files[testPath(File: "A.cc")] = "int theNewFunction();";
676 CDB.setCompileCommand(File: testPath(File: "A.cc"), CompilationCommand: 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
685class BackgroundIndexRebuilderTest : public testing::Test {
686protected:
687 BackgroundIndexRebuilderTest()
688 : Source(IndexContents::All, /*SupportContainedRefs=*/true),
689 Target(std::make_unique<MemIndex>()),
690 Rebuilder(&Target, &Source, /*Threads=*/10) {
691 // Prepare FileSymbols with TestSymbol in it, for checkRebuild.
692 TestSymbol.ID = SymbolID("foo");
693 }
694
695 // Perform Action and determine whether it rebuilt the index or not.
696 bool checkRebuild(std::function<void()> Action) {
697 // Update name so we can tell if the index updates.
698 VersionStorage.push_back(x: "Sym" + std::to_string(val: ++VersionCounter));
699 TestSymbol.Name = VersionStorage.back();
700 SymbolSlab::Builder SB;
701 SB.insert(S: TestSymbol);
702 Source.update(Key: "", Symbols: std::make_unique<SymbolSlab>(args: std::move(SB).build()),
703 Refs: nullptr, Relations: nullptr, CountReferences: false);
704 // Now maybe update the index.
705 Action();
706 // Now query the index to get the name count.
707 std::string ReadName;
708 LookupRequest Req;
709 Req.IDs.insert(V: TestSymbol.ID);
710 Target.lookup(Req,
711 [&](const Symbol &S) { ReadName = std::string(S.Name); });
712 // The index was rebuild if the name is up to date.
713 return ReadName == VersionStorage.back();
714 }
715
716 Symbol TestSymbol;
717 FileSymbols Source;
718 SwapIndex Target;
719 BackgroundIndexRebuilder Rebuilder;
720
721 unsigned VersionCounter = 0;
722 std::deque<std::string> VersionStorage;
723};
724
725TEST_F(BackgroundIndexRebuilderTest, IndexingTUs) {
726 for (unsigned I = 0; I < Rebuilder.TUsBeforeFirstBuild - 1; ++I)
727 EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
728 EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
729 for (unsigned I = 0; I < Rebuilder.TUsBeforeRebuild - 1; ++I)
730 EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
731 EXPECT_TRUE(checkRebuild([&] { Rebuilder.indexedTU(); }));
732}
733
734TEST_F(BackgroundIndexRebuilderTest, LoadingShards) {
735 Rebuilder.startLoading();
736 Rebuilder.loadedShard(ShardCount: 10);
737 Rebuilder.loadedShard(ShardCount: 20);
738 EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
739
740 // No rebuild for no shards.
741 Rebuilder.startLoading();
742 EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
743
744 // Loads can overlap.
745 Rebuilder.startLoading();
746 Rebuilder.loadedShard(ShardCount: 1);
747 Rebuilder.startLoading();
748 Rebuilder.loadedShard(ShardCount: 1);
749 EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); }));
750 Rebuilder.loadedShard(ShardCount: 1);
751 EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
752
753 // No rebuilding for indexed files while loading.
754 Rebuilder.startLoading();
755 for (unsigned I = 0; I < 3 * Rebuilder.TUsBeforeRebuild; ++I)
756 EXPECT_FALSE(checkRebuild([&] { Rebuilder.indexedTU(); }));
757 // But they get indexed when we're done, even if no shards were loaded.
758 EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); }));
759}
760
761TEST(BackgroundQueueTest, Priority) {
762 // Create high and low priority tasks.
763 // Once a bunch of high priority tasks have run, the queue is stopped.
764 // So the low priority tasks should never run.
765 BackgroundQueue Q;
766 std::atomic<unsigned> HiRan(0), LoRan(0);
767 BackgroundQueue::Task Lo([&] { ++LoRan; });
768 BackgroundQueue::Task Hi([&] {
769 if (++HiRan >= 10)
770 Q.stop();
771 });
772 Hi.QueuePri = 100;
773
774 // Enqueuing the low-priority ones first shouldn't make them run first.
775 Q.append(std::vector<BackgroundQueue::Task>(30, Lo));
776 for (unsigned I = 0; I < 30; ++I)
777 Q.push(Hi);
778
779 AsyncTaskRunner ThreadPool;
780 for (unsigned I = 0; I < 5; ++I)
781 ThreadPool.runAsync(Name: "worker", Action: [&] { Q.work(); });
782 // We should test enqueue with active workers, but it's hard to avoid races.
783 // Just make sure we don't crash.
784 Q.push(Lo);
785 Q.append(std::vector<BackgroundQueue::Task>(2, Hi));
786
787 // After finishing, check the tasks that ran.
788 ThreadPool.wait();
789 EXPECT_GE(HiRan, 10u);
790 EXPECT_EQ(LoRan, 0u);
791}
792
793TEST(BackgroundQueueTest, Boost) {
794 std::string Sequence;
795
796 BackgroundQueue::Task A([&] { Sequence.push_back(c: 'A'); });
797 A.Tag = "A";
798 A.QueuePri = 1;
799
800 BackgroundQueue::Task B([&] { Sequence.push_back(c: 'B'); });
801 B.QueuePri = 2;
802 B.Tag = "B";
803
804 {
805 BackgroundQueue Q;
806 Q.append({A, B});
807 Q.work(OnIdle: [&] { Q.stop(); });
808 EXPECT_EQ("BA", Sequence) << "priority order";
809 }
810 Sequence.clear();
811 {
812 BackgroundQueue Q;
813 Q.boost(Tag: "A", NewPriority: 3);
814 Q.append({A, B});
815 Q.work(OnIdle: [&] { Q.stop(); });
816 EXPECT_EQ("AB", Sequence) << "A was boosted before enqueueing";
817 }
818 Sequence.clear();
819 {
820 BackgroundQueue Q;
821 Q.append({A, B});
822 Q.boost(Tag: "A", NewPriority: 3);
823 Q.work(OnIdle: [&] { Q.stop(); });
824 EXPECT_EQ("AB", Sequence) << "A was boosted after enqueueing";
825 }
826}
827
828TEST(BackgroundQueueTest, Duplicates) {
829 std::string Sequence;
830 BackgroundQueue::Task A([&] { Sequence.push_back(c: 'A'); });
831 A.QueuePri = 100;
832 A.Key = 1;
833 BackgroundQueue::Task B([&] { Sequence.push_back(c: 'B'); });
834 // B has no key, and is not subject to duplicate detection.
835 B.QueuePri = 50;
836
837 BackgroundQueue Q;
838 Q.append({A, B, A, B}); // One A is dropped, the other is high priority.
839 Q.work(/*OnIdle=*/[&] {
840 // The first time we go idle, we enqueue the same task again.
841 if (!llvm::is_contained(Range&: Sequence, Element: ' ')) {
842 Sequence.push_back(c: ' ');
843 Q.append({A, B, A, B}); // Both As are dropped.
844 } else {
845 Q.stop();
846 }
847 });
848
849 // This could reasonably be "ABB BBA", if we had good *re*indexing support.
850 EXPECT_EQ("ABB BB", Sequence);
851}
852
853TEST(BackgroundQueueTest, Progress) {
854 using testing::AnyOf;
855 BackgroundQueue::Stats S;
856 BackgroundQueue Q([&](BackgroundQueue::Stats New) {
857 // Verify values are sane.
858 // Items are enqueued one at a time (at least in this test).
859 EXPECT_THAT(New.Enqueued, AnyOf(S.Enqueued, S.Enqueued + 1));
860 // Items are completed one at a time.
861 EXPECT_THAT(New.Completed, AnyOf(S.Completed, S.Completed + 1));
862 // Items are started or completed one at a time.
863 EXPECT_THAT(New.Active, AnyOf(S.Active - 1, S.Active, S.Active + 1));
864 // Idle point only advances in time.
865 EXPECT_GE(New.LastIdle, S.LastIdle);
866 // Idle point is a task that has been completed in the past.
867 EXPECT_LE(New.LastIdle, New.Completed);
868 // LastIdle is now only if we're really idle.
869 EXPECT_EQ(New.LastIdle == New.Enqueued,
870 New.Completed == New.Enqueued && New.Active == 0u);
871 S = New;
872 });
873
874 // Two types of tasks: a ping task enqueues a pong task.
875 // This avoids all enqueues followed by all completions (boring!)
876 std::atomic<int> PingCount(0), PongCount(0);
877 BackgroundQueue::Task Pong([&] { ++PongCount; });
878 BackgroundQueue::Task Ping([&] {
879 ++PingCount;
880 Q.push(Pong);
881 });
882
883 for (int I = 0; I < 1000; ++I)
884 Q.push(Ping);
885 // Spin up some workers and stop while idle.
886 AsyncTaskRunner ThreadPool;
887 for (unsigned I = 0; I < 5; ++I)
888 ThreadPool.runAsync(Name: "worker", Action: [&] { Q.work(OnIdle: [&] { Q.stop(); }); });
889 ThreadPool.wait();
890
891 // Everything's done, check final stats.
892 // Assertions above ensure we got from 0 to 2000 in a reasonable way.
893 EXPECT_EQ(PingCount.load(), 1000);
894 EXPECT_EQ(PongCount.load(), 1000);
895 EXPECT_EQ(S.Active, 0u);
896 EXPECT_EQ(S.Enqueued, 2000u);
897 EXPECT_EQ(S.Completed, 2000u);
898 EXPECT_EQ(S.LastIdle, 2000u);
899}
900
901TEST(BackgroundIndex, Profile) {
902 MockFS FS;
903 MockCompilationDatabase CDB;
904 BackgroundIndex Idx(FS, CDB, [](llvm::StringRef) { return nullptr; },
905 /*Opts=*/{});
906
907 llvm::BumpPtrAllocator Alloc;
908 MemoryTree MT(&Alloc);
909 Idx.profile(MT);
910 ASSERT_THAT(MT.children(),
911 UnorderedElementsAre(Pair("slabs", _), Pair("index", _)));
912}
913
914} // namespace clangd
915} // namespace clang
916

source code of clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp