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