1 //===-- IndexTests.cpp -------------------------------*- C++ -*-----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "Annotations.h"
10 #include "TestIndex.h"
11 #include "TestTU.h"
12 #include "index/FileIndex.h"
13 #include "index/Index.h"
14 #include "index/MemIndex.h"
15 #include "index/Merge.h"
16 #include "index/Symbol.h"
17 #include "clang/Index/IndexSymbol.h"
18 #include "gmock/gmock.h"
19 #include "gtest/gtest.h"
20
21 using ::testing::_;
22 using ::testing::AllOf;
23 using ::testing::AnyOf;
24 using ::testing::ElementsAre;
25 using ::testing::IsEmpty;
26 using ::testing::Pair;
27 using ::testing::Pointee;
28 using ::testing::UnorderedElementsAre;
29
30 namespace clang {
31 namespace clangd {
32 namespace {
33
34 MATCHER_P(Named, N, "") { return arg.Name == N; }
35 MATCHER_P(RefRange, Range, "") {
36 return std::make_tuple(arg.Location.Start.line(), arg.Location.Start.column(),
37 arg.Location.End.line(), arg.Location.End.column()) ==
38 std::make_tuple(Range.start.line, Range.start.character,
39 Range.end.line, Range.end.character);
40 }
41 MATCHER_P(FileURI, F, "") { return StringRef(arg.Location.FileURI) == F; }
42
TEST(SymbolLocation,Position)43 TEST(SymbolLocation, Position) {
44 using Position = SymbolLocation::Position;
45 Position Pos;
46
47 Pos.setLine(1);
48 EXPECT_EQ(1u, Pos.line());
49 Pos.setColumn(2);
50 EXPECT_EQ(2u, Pos.column());
51 EXPECT_FALSE(Pos.hasOverflow());
52
53 Pos.setLine(Position::MaxLine + 1); // overflow
54 EXPECT_TRUE(Pos.hasOverflow());
55 EXPECT_EQ(Pos.line(), Position::MaxLine);
56 Pos.setLine(1); // reset the overflowed line.
57
58 Pos.setColumn(Position::MaxColumn + 1); // overflow
59 EXPECT_TRUE(Pos.hasOverflow());
60 EXPECT_EQ(Pos.column(), Position::MaxColumn);
61 }
62
TEST(SymbolSlab,FindAndIterate)63 TEST(SymbolSlab, FindAndIterate) {
64 SymbolSlab::Builder B;
65 B.insert(symbol("Z"));
66 B.insert(symbol("Y"));
67 B.insert(symbol("X"));
68 EXPECT_EQ(nullptr, B.find(SymbolID("W")));
69 for (const char *Sym : {"X", "Y", "Z"})
70 EXPECT_THAT(B.find(SymbolID(Sym)), Pointee(Named(Sym)));
71
72 SymbolSlab S = std::move(B).build();
73 EXPECT_THAT(S, UnorderedElementsAre(Named("X"), Named("Y"), Named("Z")));
74 EXPECT_EQ(S.end(), S.find(SymbolID("W")));
75 for (const char *Sym : {"X", "Y", "Z"})
76 EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym));
77 }
78
TEST(RelationSlab,Lookup)79 TEST(RelationSlab, Lookup) {
80 SymbolID A{"A"};
81 SymbolID B{"B"};
82 SymbolID C{"C"};
83 SymbolID D{"D"};
84
85 RelationSlab::Builder Builder;
86 Builder.insert(Relation{A, RelationKind::BaseOf, B});
87 Builder.insert(Relation{A, RelationKind::BaseOf, C});
88 Builder.insert(Relation{B, RelationKind::BaseOf, D});
89 Builder.insert(Relation{C, RelationKind::BaseOf, D});
90
91 RelationSlab Slab = std::move(Builder).build();
92 EXPECT_THAT(Slab.lookup(A, RelationKind::BaseOf),
93 UnorderedElementsAre(Relation{A, RelationKind::BaseOf, B},
94 Relation{A, RelationKind::BaseOf, C}));
95 }
96
TEST(RelationSlab,Duplicates)97 TEST(RelationSlab, Duplicates) {
98 SymbolID A{"A"};
99 SymbolID B{"B"};
100 SymbolID C{"C"};
101
102 RelationSlab::Builder Builder;
103 Builder.insert(Relation{A, RelationKind::BaseOf, B});
104 Builder.insert(Relation{A, RelationKind::BaseOf, C});
105 Builder.insert(Relation{A, RelationKind::BaseOf, B});
106
107 RelationSlab Slab = std::move(Builder).build();
108 EXPECT_THAT(Slab, UnorderedElementsAre(Relation{A, RelationKind::BaseOf, B},
109 Relation{A, RelationKind::BaseOf, C}));
110 }
111
TEST(SwapIndexTest,OldIndexRecycled)112 TEST(SwapIndexTest, OldIndexRecycled) {
113 auto Token = std::make_shared<int>();
114 std::weak_ptr<int> WeakToken = Token;
115
116 SwapIndex S(std::make_unique<MemIndex>(SymbolSlab(), RefSlab(),
117 RelationSlab(), std::move(Token),
118 /*BackingDataSize=*/0));
119 EXPECT_FALSE(WeakToken.expired()); // Current MemIndex keeps it alive.
120 S.reset(std::make_unique<MemIndex>()); // Now the MemIndex is destroyed.
121 EXPECT_TRUE(WeakToken.expired()); // So the token is too.
122 }
123
TEST(MemIndexTest,MemIndexDeduplicate)124 TEST(MemIndexTest, MemIndexDeduplicate) {
125 std::vector<Symbol> Symbols = {symbol("1"), symbol("2"), symbol("3"),
126 symbol("2") /* duplicate */};
127 FuzzyFindRequest Req;
128 Req.Query = "2";
129 Req.AnyScope = true;
130 MemIndex I(Symbols, RefSlab(), RelationSlab());
131 EXPECT_THAT(match(I, Req), ElementsAre("2"));
132 }
133
TEST(MemIndexTest,MemIndexLimitedNumMatches)134 TEST(MemIndexTest, MemIndexLimitedNumMatches) {
135 auto I =
136 MemIndex::build(generateNumSymbols(0, 100), RefSlab(), RelationSlab());
137 FuzzyFindRequest Req;
138 Req.Query = "5";
139 Req.AnyScope = true;
140 Req.Limit = 3;
141 bool Incomplete;
142 auto Matches = match(*I, Req, &Incomplete);
143 EXPECT_TRUE(Req.Limit);
144 EXPECT_EQ(Matches.size(), *Req.Limit);
145 EXPECT_TRUE(Incomplete);
146 }
147
TEST(MemIndexTest,FuzzyMatch)148 TEST(MemIndexTest, FuzzyMatch) {
149 auto I = MemIndex::build(
150 generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
151 RefSlab(), RelationSlab());
152 FuzzyFindRequest Req;
153 Req.Query = "lol";
154 Req.AnyScope = true;
155 Req.Limit = 2;
156 EXPECT_THAT(match(*I, Req),
157 UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
158 }
159
TEST(MemIndexTest,MatchQualifiedNamesWithoutSpecificScope)160 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
161 auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
162 RelationSlab());
163 FuzzyFindRequest Req;
164 Req.Query = "y";
165 Req.AnyScope = true;
166 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
167 }
168
TEST(MemIndexTest,MatchQualifiedNamesWithGlobalScope)169 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
170 auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(),
171 RelationSlab());
172 FuzzyFindRequest Req;
173 Req.Query = "y";
174 Req.Scopes = {""};
175 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3"));
176 }
177
TEST(MemIndexTest,MatchQualifiedNamesWithOneScope)178 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
179 auto I = MemIndex::build(
180 generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab(),
181 RelationSlab());
182 FuzzyFindRequest Req;
183 Req.Query = "y";
184 Req.Scopes = {"a::"};
185 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2"));
186 }
187
TEST(MemIndexTest,MatchQualifiedNamesWithMultipleScopes)188 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
189 auto I = MemIndex::build(
190 generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab(),
191 RelationSlab());
192 FuzzyFindRequest Req;
193 Req.Query = "y";
194 Req.Scopes = {"a::", "b::"};
195 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3"));
196 }
197
TEST(MemIndexTest,NoMatchNestedScopes)198 TEST(MemIndexTest, NoMatchNestedScopes) {
199 auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab(),
200 RelationSlab());
201 FuzzyFindRequest Req;
202 Req.Query = "y";
203 Req.Scopes = {"a::"};
204 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1"));
205 }
206
TEST(MemIndexTest,IgnoreCases)207 TEST(MemIndexTest, IgnoreCases) {
208 auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(),
209 RelationSlab());
210 FuzzyFindRequest Req;
211 Req.Query = "AB";
212 Req.Scopes = {"ns::"};
213 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
214 }
215
TEST(MemIndexTest,Lookup)216 TEST(MemIndexTest, Lookup) {
217 auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(),
218 RelationSlab());
219 EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc"));
220 EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
221 UnorderedElementsAre("ns::abc", "ns::xyz"));
222 EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}),
223 UnorderedElementsAre("ns::xyz"));
224 EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre());
225 }
226
TEST(MemIndexTest,TemplateSpecialization)227 TEST(MemIndexTest, TemplateSpecialization) {
228 SymbolSlab::Builder B;
229
230 Symbol S = symbol("TempSpec");
231 S.ID = SymbolID("1");
232 B.insert(S);
233
234 S = symbol("TempSpec");
235 S.ID = SymbolID("2");
236 S.TemplateSpecializationArgs = "<int, bool>";
237 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
238 index::SymbolProperty::TemplateSpecialization);
239 B.insert(S);
240
241 S = symbol("TempSpec");
242 S.ID = SymbolID("3");
243 S.TemplateSpecializationArgs = "<int, U>";
244 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>(
245 index::SymbolProperty::TemplatePartialSpecialization);
246 B.insert(S);
247
248 auto I = MemIndex::build(std::move(B).build(), RefSlab(), RelationSlab());
249 FuzzyFindRequest Req;
250 Req.AnyScope = true;
251
252 Req.Query = "TempSpec";
253 EXPECT_THAT(match(*I, Req),
254 UnorderedElementsAre("TempSpec", "TempSpec<int, bool>",
255 "TempSpec<int, U>"));
256
257 // FIXME: Add filtering for template argument list.
258 Req.Query = "TempSpec<int";
259 EXPECT_THAT(match(*I, Req), IsEmpty());
260 }
261
TEST(MergeIndexTest,Lookup)262 TEST(MergeIndexTest, Lookup) {
263 auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
264 RelationSlab()),
265 J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
266 RelationSlab());
267 MergedIndex M(I.get(), J.get());
268 EXPECT_THAT(lookup(M, SymbolID("ns::A")), UnorderedElementsAre("ns::A"));
269 EXPECT_THAT(lookup(M, SymbolID("ns::B")), UnorderedElementsAre("ns::B"));
270 EXPECT_THAT(lookup(M, SymbolID("ns::C")), UnorderedElementsAre("ns::C"));
271 EXPECT_THAT(lookup(M, {SymbolID("ns::A"), SymbolID("ns::B")}),
272 UnorderedElementsAre("ns::A", "ns::B"));
273 EXPECT_THAT(lookup(M, {SymbolID("ns::A"), SymbolID("ns::C")}),
274 UnorderedElementsAre("ns::A", "ns::C"));
275 EXPECT_THAT(lookup(M, SymbolID("ns::D")), UnorderedElementsAre());
276 EXPECT_THAT(lookup(M, {}), UnorderedElementsAre());
277 }
278
TEST(MergeIndexTest,FuzzyFind)279 TEST(MergeIndexTest, FuzzyFind) {
280 auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(),
281 RelationSlab()),
282 J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(),
283 RelationSlab());
284 FuzzyFindRequest Req;
285 Req.Scopes = {"ns::"};
286 EXPECT_THAT(match(MergedIndex(I.get(), J.get()), Req),
287 UnorderedElementsAre("ns::A", "ns::B", "ns::C"));
288 }
289
TEST(MergeTest,Merge)290 TEST(MergeTest, Merge) {
291 Symbol L, R;
292 L.ID = R.ID = SymbolID("hello");
293 L.Name = R.Name = "Foo"; // same in both
294 L.CanonicalDeclaration.FileURI = "file:///left.h"; // differs
295 R.CanonicalDeclaration.FileURI = "file:///right.h";
296 L.References = 1;
297 R.References = 2;
298 L.Signature = "()"; // present in left only
299 R.CompletionSnippetSuffix = "{$1:0}"; // present in right only
300 R.Documentation = "--doc--";
301 L.Origin = SymbolOrigin::Dynamic;
302 R.Origin = SymbolOrigin::Static;
303 R.Type = "expectedType";
304
305 Symbol M = mergeSymbol(L, R);
306 EXPECT_EQ(M.Name, "Foo");
307 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:///left.h");
308 EXPECT_EQ(M.References, 3u);
309 EXPECT_EQ(M.Signature, "()");
310 EXPECT_EQ(M.CompletionSnippetSuffix, "{$1:0}");
311 EXPECT_EQ(M.Documentation, "--doc--");
312 EXPECT_EQ(M.Type, "expectedType");
313 EXPECT_EQ(M.Origin,
314 SymbolOrigin::Dynamic | SymbolOrigin::Static | SymbolOrigin::Merge);
315 }
316
TEST(MergeTest,PreferSymbolWithDefn)317 TEST(MergeTest, PreferSymbolWithDefn) {
318 Symbol L, R;
319
320 L.ID = R.ID = SymbolID("hello");
321 L.CanonicalDeclaration.FileURI = "file:/left.h";
322 R.CanonicalDeclaration.FileURI = "file:/right.h";
323 L.Name = "left";
324 R.Name = "right";
325
326 Symbol M = mergeSymbol(L, R);
327 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/left.h");
328 EXPECT_EQ(StringRef(M.Definition.FileURI), "");
329 EXPECT_EQ(M.Name, "left");
330
331 R.Definition.FileURI = "file:/right.cpp"; // Now right will be favored.
332 M = mergeSymbol(L, R);
333 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/right.h");
334 EXPECT_EQ(StringRef(M.Definition.FileURI), "file:/right.cpp");
335 EXPECT_EQ(M.Name, "right");
336 }
337
TEST(MergeTest,PreferSymbolLocationInCodegenFile)338 TEST(MergeTest, PreferSymbolLocationInCodegenFile) {
339 Symbol L, R;
340
341 L.ID = R.ID = SymbolID("hello");
342 L.CanonicalDeclaration.FileURI = "file:/x.proto.h";
343 R.CanonicalDeclaration.FileURI = "file:/x.proto";
344
345 Symbol M = mergeSymbol(L, R);
346 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/x.proto");
347
348 // Prefer L if both have codegen suffix.
349 L.CanonicalDeclaration.FileURI = "file:/y.proto";
350 M = mergeSymbol(L, R);
351 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/y.proto");
352 }
353
TEST(MergeIndexTest,Refs)354 TEST(MergeIndexTest, Refs) {
355 FileIndex Dyn;
356 FileIndex StaticIndex;
357 MergedIndex Merge(&Dyn, &StaticIndex);
358
359 const char *HeaderCode = "class Foo;";
360 auto HeaderSymbols = TestTU::withHeaderCode("class Foo;").headerSymbols();
361 auto Foo = findSymbol(HeaderSymbols, "Foo");
362
363 // Build dynamic index for test.cc.
364 Annotations Test1Code(R"(class $Foo[[Foo]];)");
365 TestTU Test;
366 Test.HeaderCode = HeaderCode;
367 Test.Code = std::string(Test1Code.code());
368 Test.Filename = "test.cc";
369 auto AST = Test.build();
370 Dyn.updateMain(Test.Filename, AST);
371
372 // Build static index for test.cc.
373 Test.HeaderCode = HeaderCode;
374 Test.Code = "// static\nclass Foo {};";
375 Test.Filename = "test.cc";
376 auto StaticAST = Test.build();
377 // Add stale refs for test.cc.
378 StaticIndex.updateMain(Test.Filename, StaticAST);
379
380 // Add refs for test2.cc
381 Annotations Test2Code(R"(class $Foo[[Foo]] {};)");
382 TestTU Test2;
383 Test2.HeaderCode = HeaderCode;
384 Test2.Code = std::string(Test2Code.code());
385 Test2.Filename = "test2.cc";
386 StaticAST = Test2.build();
387 StaticIndex.updateMain(Test2.Filename, StaticAST);
388
389 RefsRequest Request;
390 Request.IDs = {Foo.ID};
391 RefSlab::Builder Results;
392 EXPECT_FALSE(
393 Merge.refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); }));
394 EXPECT_THAT(
395 std::move(Results).build(),
396 ElementsAre(Pair(
397 _, UnorderedElementsAre(AllOf(RefRange(Test1Code.range("Foo")),
398 FileURI("unittest:///test.cc")),
399 AllOf(RefRange(Test2Code.range("Foo")),
400 FileURI("unittest:///test2.cc"))))));
401
402 Request.Limit = 1;
403 RefSlab::Builder Results2;
404 EXPECT_TRUE(
405 Merge.refs(Request, [&](const Ref &O) { Results2.insert(Foo.ID, O); }));
406 EXPECT_THAT(std::move(Results2).build(),
407 ElementsAre(Pair(
408 _, ElementsAre(AnyOf(FileURI("unittest:///test.cc"),
409 FileURI("unittest:///test2.cc"))))));
410 }
411
TEST(MergeIndexTest,NonDocumentation)412 TEST(MergeIndexTest, NonDocumentation) {
413 using index::SymbolKind;
414 Symbol L, R;
415 L.ID = R.ID = SymbolID("x");
416 L.Definition.FileURI = "file:/x.h";
417 R.Documentation = "Forward declarations because x.h is too big to include";
418 for (auto ClassLikeKind :
419 {SymbolKind::Class, SymbolKind::Struct, SymbolKind::Union}) {
420 L.SymInfo.Kind = ClassLikeKind;
421 EXPECT_EQ(mergeSymbol(L, R).Documentation, "");
422 }
423
424 L.SymInfo.Kind = SymbolKind::Function;
425 R.Documentation = "Documentation from non-class symbols should be included";
426 EXPECT_EQ(mergeSymbol(L, R).Documentation, R.Documentation);
427 }
428
429 MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References, "") {
430 return (arg.IncludeHeader == IncludeHeader) && (arg.References == References);
431 }
432
TEST(MergeTest,MergeIncludesOnDifferentDefinitions)433 TEST(MergeTest, MergeIncludesOnDifferentDefinitions) {
434 Symbol L, R;
435 L.Name = "left";
436 R.Name = "right";
437 L.ID = R.ID = SymbolID("hello");
438 L.IncludeHeaders.emplace_back("common", 1);
439 R.IncludeHeaders.emplace_back("common", 1);
440 R.IncludeHeaders.emplace_back("new", 1);
441
442 // Both have no definition.
443 Symbol M = mergeSymbol(L, R);
444 EXPECT_THAT(M.IncludeHeaders,
445 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u),
446 IncludeHeaderWithRef("new", 1u)));
447
448 // Only merge references of the same includes but do not merge new #includes.
449 L.Definition.FileURI = "file:/left.h";
450 M = mergeSymbol(L, R);
451 EXPECT_THAT(M.IncludeHeaders,
452 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u)));
453
454 // Definitions are the same.
455 R.Definition.FileURI = "file:/right.h";
456 M = mergeSymbol(L, R);
457 EXPECT_THAT(M.IncludeHeaders,
458 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u),
459 IncludeHeaderWithRef("new", 1u)));
460
461 // Definitions are different.
462 R.Definition.FileURI = "file:/right.h";
463 M = mergeSymbol(L, R);
464 EXPECT_THAT(M.IncludeHeaders,
465 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u),
466 IncludeHeaderWithRef("new", 1u)));
467 }
468
469 } // namespace
470 } // namespace clangd
471 } // namespace clang
472