1 //===-- DexTests.cpp ---------------------------------*- C++ -*-----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "FuzzyMatch.h"
11 #include "TestFS.h"
12 #include "TestIndex.h"
13 #include "index/Index.h"
14 #include "index/Merge.h"
15 #include "index/dex/Dex.h"
16 #include "index/dex/Iterator.h"
17 #include "index/dex/Token.h"
18 #include "index/dex/Trigram.h"
19 #include "llvm/Support/ScopedPrinter.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include "gmock/gmock.h"
22 #include "gtest/gtest.h"
23 #include <string>
24 #include <vector>
25
26 using ::testing::AnyOf;
27 using ::testing::ElementsAre;
28 using ::testing::UnorderedElementsAre;
29
30 namespace clang {
31 namespace clangd {
32 namespace dex {
33 namespace {
34
35 //===----------------------------------------------------------------------===//
36 // Query iterator tests.
37 //===----------------------------------------------------------------------===//
38
consumeIDs(Iterator & It)39 std::vector<DocID> consumeIDs(Iterator &It) {
40 auto IDAndScore = consume(It);
41 std::vector<DocID> IDs(IDAndScore.size());
42 for (size_t I = 0; I < IDAndScore.size(); ++I)
43 IDs[I] = IDAndScore[I].first;
44 return IDs;
45 }
46
TEST(DexIterators,DocumentIterator)47 TEST(DexIterators, DocumentIterator) {
48 const PostingList L({4, 7, 8, 20, 42, 100});
49 auto DocIterator = L.iterator();
50
51 EXPECT_EQ(DocIterator->peek(), 4U);
52 EXPECT_FALSE(DocIterator->reachedEnd());
53
54 DocIterator->advance();
55 EXPECT_EQ(DocIterator->peek(), 7U);
56 EXPECT_FALSE(DocIterator->reachedEnd());
57
58 DocIterator->advanceTo(20);
59 EXPECT_EQ(DocIterator->peek(), 20U);
60 EXPECT_FALSE(DocIterator->reachedEnd());
61
62 DocIterator->advanceTo(65);
63 EXPECT_EQ(DocIterator->peek(), 100U);
64 EXPECT_FALSE(DocIterator->reachedEnd());
65
66 DocIterator->advanceTo(420);
67 EXPECT_TRUE(DocIterator->reachedEnd());
68 }
69
TEST(DexIterators,AndTwoLists)70 TEST(DexIterators, AndTwoLists) {
71 Corpus C{10000};
72 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});
73 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});
74
75 auto And = C.intersect(L1.iterator(), L0.iterator());
76
77 EXPECT_FALSE(And->reachedEnd());
78 EXPECT_THAT(consumeIDs(*And), ElementsAre(0U, 7U, 10U, 320U, 9000U));
79
80 And = C.intersect(L0.iterator(), L1.iterator());
81
82 And->advanceTo(0);
83 EXPECT_EQ(And->peek(), 0U);
84 And->advanceTo(5);
85 EXPECT_EQ(And->peek(), 7U);
86 And->advanceTo(10);
87 EXPECT_EQ(And->peek(), 10U);
88 And->advanceTo(42);
89 EXPECT_EQ(And->peek(), 320U);
90 And->advanceTo(8999);
91 EXPECT_EQ(And->peek(), 9000U);
92 And->advanceTo(9001);
93 }
94
TEST(DexIterators,AndThreeLists)95 TEST(DexIterators, AndThreeLists) {
96 Corpus C{10000};
97 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});
98 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});
99 const PostingList L2({1, 4, 7, 11, 30, 60, 320, 9000});
100
101 auto And = C.intersect(L0.iterator(), L1.iterator(), L2.iterator());
102 EXPECT_EQ(And->peek(), 7U);
103 And->advanceTo(300);
104 EXPECT_EQ(And->peek(), 320U);
105 And->advanceTo(100000);
106
107 EXPECT_TRUE(And->reachedEnd());
108 }
109
TEST(DexIterators,AndEmpty)110 TEST(DexIterators, AndEmpty) {
111 Corpus C{10000};
112 const PostingList L1{1};
113 const PostingList L2{2};
114 // These iterators are empty, but the optimizer can't tell.
115 auto Empty1 = C.intersect(L1.iterator(), L2.iterator());
116 auto Empty2 = C.intersect(L1.iterator(), L2.iterator());
117 // And syncs iterators on construction, and used to fail on empty children.
118 auto And = C.intersect(std::move(Empty1), std::move(Empty2));
119 EXPECT_TRUE(And->reachedEnd());
120 }
121
TEST(DexIterators,OrTwoLists)122 TEST(DexIterators, OrTwoLists) {
123 Corpus C{10000};
124 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});
125 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});
126
127 auto Or = C.unionOf(L0.iterator(), L1.iterator());
128
129 EXPECT_FALSE(Or->reachedEnd());
130 EXPECT_EQ(Or->peek(), 0U);
131 Or->advance();
132 EXPECT_EQ(Or->peek(), 4U);
133 Or->advance();
134 EXPECT_EQ(Or->peek(), 5U);
135 Or->advance();
136 EXPECT_EQ(Or->peek(), 7U);
137 Or->advance();
138 EXPECT_EQ(Or->peek(), 10U);
139 Or->advance();
140 EXPECT_EQ(Or->peek(), 30U);
141 Or->advanceTo(42);
142 EXPECT_EQ(Or->peek(), 42U);
143 Or->advanceTo(300);
144 EXPECT_EQ(Or->peek(), 320U);
145 Or->advanceTo(9000);
146 EXPECT_EQ(Or->peek(), 9000U);
147 Or->advanceTo(9001);
148 EXPECT_TRUE(Or->reachedEnd());
149
150 Or = C.unionOf(L0.iterator(), L1.iterator());
151
152 EXPECT_THAT(consumeIDs(*Or),
153 ElementsAre(0U, 4U, 5U, 7U, 10U, 30U, 42U, 60U, 320U, 9000U));
154 }
155
TEST(DexIterators,OrThreeLists)156 TEST(DexIterators, OrThreeLists) {
157 Corpus C{10000};
158 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});
159 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});
160 const PostingList L2({1, 4, 7, 11, 30, 60, 320, 9000});
161
162 auto Or = C.unionOf(L0.iterator(), L1.iterator(), L2.iterator());
163
164 EXPECT_FALSE(Or->reachedEnd());
165 EXPECT_EQ(Or->peek(), 0U);
166
167 Or->advance();
168 EXPECT_EQ(Or->peek(), 1U);
169
170 Or->advance();
171 EXPECT_EQ(Or->peek(), 4U);
172
173 Or->advanceTo(7);
174
175 Or->advanceTo(59);
176 EXPECT_EQ(Or->peek(), 60U);
177
178 Or->advanceTo(9001);
179 EXPECT_TRUE(Or->reachedEnd());
180 }
181
182 // FIXME(kbobyrev): The testcase below is similar to what is expected in real
183 // queries. It should be updated once new iterators (such as boosting, limiting,
184 // etc iterators) appear. However, it is not exhaustive and it would be
185 // beneficial to implement automatic generation (e.g. fuzzing) of query trees
186 // for more comprehensive testing.
TEST(DexIterators,QueryTree)187 TEST(DexIterators, QueryTree) {
188 //
189 // +-----------------+
190 // |And Iterator:1, 5|
191 // +--------+--------+
192 // |
193 // |
194 // +-------------+----------------------+
195 // | |
196 // | |
197 // +----------v----------+ +----------v------------+
198 // |And Iterator: 1, 5, 9| |Or Iterator: 0, 1, 3, 5|
199 // +----------+----------+ +----------+------------+
200 // | |
201 // +------+-----+ ------------+
202 // | | | |
203 // +-------v-----+ +----+---+ +---v----+ +----v---+
204 // |1, 3, 5, 8, 9| |Boost: 2| |Boost: 3| |Boost: 4|
205 // +-------------+ +----+---+ +---+----+ +----+---+
206 // | | |
207 // +----v-----+ +-v--+ +---v---+
208 // |1, 5, 7, 9| |1, 5| |0, 3, 5|
209 // +----------+ +----+ +-------+
210 //
211 Corpus C{10};
212 const PostingList L0({1, 3, 5, 8, 9});
213 const PostingList L1({1, 5, 7, 9});
214 const PostingList L2({1, 5});
215 const PostingList L3({0, 3, 5});
216
217 // Root of the query tree: [1, 5]
218 auto Root = C.intersect(
219 // Lower And Iterator: [1, 5, 9]
220 C.intersect(L0.iterator(), C.boost(L1.iterator(), 2U)),
221 // Lower Or Iterator: [0, 1, 5]
222 C.unionOf(C.boost(L2.iterator(), 3U), C.boost(L3.iterator(), 4U)));
223
224 EXPECT_FALSE(Root->reachedEnd());
225 EXPECT_EQ(Root->peek(), 1U);
226 Root->advanceTo(0);
227 // Advance multiple times. Shouldn't do anything.
228 Root->advanceTo(1);
229 Root->advanceTo(0);
230 EXPECT_EQ(Root->peek(), 1U);
231 auto ElementBoost = Root->consume();
232 EXPECT_THAT(ElementBoost, 6);
233 Root->advance();
234 EXPECT_EQ(Root->peek(), 5U);
235 Root->advanceTo(5);
236 EXPECT_EQ(Root->peek(), 5U);
237 ElementBoost = Root->consume();
238 EXPECT_THAT(ElementBoost, 8);
239 Root->advanceTo(9000);
240 EXPECT_TRUE(Root->reachedEnd());
241 }
242
TEST(DexIterators,StringRepresentation)243 TEST(DexIterators, StringRepresentation) {
244 Corpus C{10};
245 const PostingList L1({1, 3, 5});
246 const PostingList L2({1, 7, 9});
247
248 // No token given, prints full posting list.
249 auto I1 = L1.iterator();
250 EXPECT_EQ(llvm::to_string(*I1), "[1 3 5]");
251
252 // Token given, uses token's string representation.
253 Token Tok(Token::Kind::Trigram, "L2");
254 auto I2 = L1.iterator(&Tok);
255 EXPECT_EQ(llvm::to_string(*I2), "T=L2");
256
257 auto Tree = C.limit(C.intersect(move(I1), move(I2)), 10);
258 // AND reorders its children, we don't care which order it prints.
259 EXPECT_THAT(llvm::to_string(*Tree), AnyOf("(LIMIT 10 (& [1 3 5] T=L2))",
260 "(LIMIT 10 (& T=L2 [1 3 5]))"));
261 }
262
TEST(DexIterators,Limit)263 TEST(DexIterators, Limit) {
264 Corpus C{10000};
265 const PostingList L0({3, 6, 7, 20, 42, 100});
266 const PostingList L1({1, 3, 5, 6, 7, 30, 100});
267 const PostingList L2({0, 3, 5, 7, 8, 100});
268
269 auto DocIterator = C.limit(L0.iterator(), 42);
270 EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre(3, 6, 7, 20, 42, 100));
271
272 DocIterator = C.limit(L0.iterator(), 3);
273 EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre(3, 6, 7));
274
275 DocIterator = C.limit(L0.iterator(), 0);
276 EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre());
277
278 auto AndIterator =
279 C.intersect(C.limit(C.all(), 343), C.limit(L0.iterator(), 2),
280 C.limit(L1.iterator(), 3), C.limit(L2.iterator(), 42));
281 EXPECT_THAT(consumeIDs(*AndIterator), ElementsAre(3, 7));
282 }
283
TEST(DexIterators,True)284 TEST(DexIterators, True) {
285 EXPECT_TRUE(Corpus{0}.all()->reachedEnd());
286 EXPECT_THAT(consumeIDs(*Corpus{4}.all()), ElementsAre(0, 1, 2, 3));
287 }
288
TEST(DexIterators,Boost)289 TEST(DexIterators, Boost) {
290 Corpus C{5};
291 auto BoostIterator = C.boost(C.all(), 42U);
292 EXPECT_FALSE(BoostIterator->reachedEnd());
293 auto ElementBoost = BoostIterator->consume();
294 EXPECT_THAT(ElementBoost, 42U);
295
296 const PostingList L0({2, 4});
297 const PostingList L1({1, 4});
298 auto Root = C.unionOf(C.all(), C.boost(L0.iterator(), 2U),
299 C.boost(L1.iterator(), 3U));
300
301 ElementBoost = Root->consume();
302 EXPECT_THAT(ElementBoost, 1);
303 Root->advance();
304 EXPECT_THAT(Root->peek(), 1U);
305 ElementBoost = Root->consume();
306 EXPECT_THAT(ElementBoost, 3);
307
308 Root->advance();
309 EXPECT_THAT(Root->peek(), 2U);
310 ElementBoost = Root->consume();
311 EXPECT_THAT(ElementBoost, 2);
312
313 Root->advanceTo(4);
314 ElementBoost = Root->consume();
315 EXPECT_THAT(ElementBoost, 3);
316 }
317
TEST(DexIterators,Optimizations)318 TEST(DexIterators, Optimizations) {
319 Corpus C{5};
320 const PostingList L1{1};
321 const PostingList L2{2};
322 const PostingList L3{3};
323
324 // empty and/or yield true/false
325 EXPECT_EQ(llvm::to_string(*C.intersect()), "true");
326 EXPECT_EQ(llvm::to_string(*C.unionOf()), "false");
327
328 // true/false inside and/or short-circuit
329 EXPECT_EQ(llvm::to_string(*C.intersect(L1.iterator(), C.all())), "[1]");
330 EXPECT_EQ(llvm::to_string(*C.intersect(L1.iterator(), C.none())), "false");
331 // Not optimized to avoid breaking boosts.
332 EXPECT_EQ(llvm::to_string(*C.unionOf(L1.iterator(), C.all())),
333 "(| [1] true)");
334 EXPECT_EQ(llvm::to_string(*C.unionOf(L1.iterator(), C.none())), "[1]");
335
336 // and/or nested inside and/or are flattened
337 EXPECT_EQ(llvm::to_string(*C.intersect(
338 L1.iterator(), C.intersect(L1.iterator(), L1.iterator()))),
339 "(& [1] [1] [1])");
340 EXPECT_EQ(llvm::to_string(*C.unionOf(
341 L1.iterator(), C.unionOf(L2.iterator(), L3.iterator()))),
342 "(| [1] [2] [3])");
343
344 // optimizations combine over multiple levels
345 EXPECT_EQ(llvm::to_string(*C.intersect(
346 C.intersect(L1.iterator(), C.intersect()), C.unionOf(C.all()))),
347 "[1]");
348 }
349
350 //===----------------------------------------------------------------------===//
351 // Search token tests.
352 //===----------------------------------------------------------------------===//
353
354 testing::Matcher<std::vector<Token>>
tokensAre(std::initializer_list<std::string> Strings,Token::Kind Kind)355 tokensAre(std::initializer_list<std::string> Strings, Token::Kind Kind) {
356 std::vector<Token> Tokens;
357 for (const auto &TokenData : Strings) {
358 Tokens.push_back(Token(Kind, TokenData));
359 }
360 return testing::UnorderedElementsAreArray(Tokens);
361 }
362
363 testing::Matcher<std::vector<Token>>
trigramsAre(std::initializer_list<std::string> Trigrams)364 trigramsAre(std::initializer_list<std::string> Trigrams) {
365 return tokensAre(Trigrams, Token::Kind::Trigram);
366 }
367
TEST(DexTrigrams,IdentifierTrigrams)368 TEST(DexTrigrams, IdentifierTrigrams) {
369 EXPECT_THAT(generateIdentifierTrigrams("X86"),
370 trigramsAre({"x86", "x", "x8"}));
371
372 EXPECT_THAT(generateIdentifierTrigrams("nl"), trigramsAre({"nl", "n"}));
373
374 EXPECT_THAT(generateIdentifierTrigrams("n"), trigramsAre({"n"}));
375
376 EXPECT_THAT(generateIdentifierTrigrams("clangd"),
377 trigramsAre({"c", "cl", "cla", "lan", "ang", "ngd"}));
378
379 EXPECT_THAT(generateIdentifierTrigrams("abc_def"),
380 trigramsAre({"a", "ab", "ad", "abc", "abd", "ade", "bcd", "bde",
381 "cde", "def"}));
382
383 EXPECT_THAT(generateIdentifierTrigrams("a_b_c_d_e_"),
384 trigramsAre({"a", "a_", "ab", "abc", "bcd", "cde"}));
385
386 EXPECT_THAT(generateIdentifierTrigrams("unique_ptr"),
387 trigramsAre({"u", "un", "up", "uni", "unp", "upt", "niq", "nip",
388 "npt", "iqu", "iqp", "ipt", "que", "qup", "qpt",
389 "uep", "ept", "ptr"}));
390
391 EXPECT_THAT(
392 generateIdentifierTrigrams("TUDecl"),
393 trigramsAre({"t", "tu", "td", "tud", "tde", "ude", "dec", "ecl"}));
394
395 EXPECT_THAT(generateIdentifierTrigrams("IsOK"),
396 trigramsAre({"i", "is", "io", "iso", "iok", "sok"}));
397
398 EXPECT_THAT(
399 generateIdentifierTrigrams("abc_defGhij__klm"),
400 trigramsAre({"a", "ab", "ad", "abc", "abd", "ade", "adg", "bcd",
401 "bde", "bdg", "cde", "cdg", "def", "deg", "dgh", "dgk",
402 "efg", "egh", "egk", "fgh", "fgk", "ghi", "ghk", "gkl",
403 "hij", "hik", "hkl", "ijk", "ikl", "jkl", "klm"}));
404 }
405
TEST(DexTrigrams,QueryTrigrams)406 TEST(DexTrigrams, QueryTrigrams) {
407 EXPECT_THAT(generateQueryTrigrams("c"), trigramsAre({"c"}));
408 EXPECT_THAT(generateQueryTrigrams("cl"), trigramsAre({"cl"}));
409 EXPECT_THAT(generateQueryTrigrams("cla"), trigramsAre({"cla"}));
410
411 EXPECT_THAT(generateQueryTrigrams(""), trigramsAre({}));
412 EXPECT_THAT(generateQueryTrigrams("_"), trigramsAre({"_"}));
413 EXPECT_THAT(generateQueryTrigrams("__"), trigramsAre({"__"}));
414 EXPECT_THAT(generateQueryTrigrams("___"), trigramsAre({}));
415
416 EXPECT_THAT(generateQueryTrigrams("X86"), trigramsAre({"x86"}));
417
418 EXPECT_THAT(generateQueryTrigrams("clangd"),
419 trigramsAre({"cla", "lan", "ang", "ngd"}));
420
421 EXPECT_THAT(generateQueryTrigrams("abc_def"),
422 trigramsAre({"abc", "bcd", "cde", "def"}));
423
424 EXPECT_THAT(generateQueryTrigrams("a_b_c_d_e_"),
425 trigramsAre({"abc", "bcd", "cde"}));
426
427 EXPECT_THAT(generateQueryTrigrams("unique_ptr"),
428 trigramsAre({"uni", "niq", "iqu", "que", "uep", "ept", "ptr"}));
429
430 EXPECT_THAT(generateQueryTrigrams("TUDecl"),
431 trigramsAre({"tud", "ude", "dec", "ecl"}));
432
433 EXPECT_THAT(generateQueryTrigrams("IsOK"), trigramsAre({"iso", "sok"}));
434
435 EXPECT_THAT(generateQueryTrigrams("abc_defGhij__klm"),
436 trigramsAre({"abc", "bcd", "cde", "def", "efg", "fgh", "ghi",
437 "hij", "ijk", "jkl", "klm"}));
438 }
439
TEST(DexSearchTokens,SymbolPath)440 TEST(DexSearchTokens, SymbolPath) {
441 EXPECT_THAT(generateProximityURIs(
442 "unittest:///clang-tools-extra/clangd/index/Token.h"),
443 ElementsAre("unittest:///clang-tools-extra/clangd/index/Token.h",
444 "unittest:///clang-tools-extra/clangd/index",
445 "unittest:///clang-tools-extra/clangd",
446 "unittest:///clang-tools-extra", "unittest:///"));
447
448 EXPECT_THAT(generateProximityURIs("unittest:///a/b/c.h"),
449 ElementsAre("unittest:///a/b/c.h", "unittest:///a/b",
450 "unittest:///a", "unittest:///"));
451 }
452
453 //===----------------------------------------------------------------------===//
454 // Index tests.
455 //===----------------------------------------------------------------------===//
456
TEST(Dex,Lookup)457 TEST(Dex, Lookup) {
458 auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab());
459 EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc"));
460 EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
461 UnorderedElementsAre("ns::abc", "ns::xyz"));
462 EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}),
463 UnorderedElementsAre("ns::xyz"));
464 EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre());
465 }
466
TEST(Dex,FuzzyFind)467 TEST(Dex, FuzzyFind) {
468 auto Index =
469 Dex::build(generateSymbols({"ns::ABC", "ns::BCD", "::ABC",
470 "ns::nested::ABC", "other::ABC", "other::A"}),
471 RefSlab());
472 FuzzyFindRequest Req;
473 Req.Query = "ABC";
474 Req.Scopes = {"ns::"};
475 EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("ns::ABC"));
476 Req.Scopes = {"ns::", "ns::nested::"};
477 EXPECT_THAT(match(*Index, Req),
478 UnorderedElementsAre("ns::ABC", "ns::nested::ABC"));
479 Req.Query = "A";
480 Req.Scopes = {"other::"};
481 EXPECT_THAT(match(*Index, Req),
482 UnorderedElementsAre("other::A", "other::ABC"));
483 Req.Query = "";
484 Req.Scopes = {};
485 Req.AnyScope = true;
486 EXPECT_THAT(match(*Index, Req),
487 UnorderedElementsAre("ns::ABC", "ns::BCD", "::ABC",
488 "ns::nested::ABC", "other::ABC",
489 "other::A"));
490 }
491
TEST(DexTest,DexLimitedNumMatches)492 TEST(DexTest, DexLimitedNumMatches) {
493 auto I = Dex::build(generateNumSymbols(0, 100), RefSlab());
494 FuzzyFindRequest Req;
495 Req.Query = "5";
496 Req.AnyScope = true;
497 Req.Limit = 3;
498 bool Incomplete;
499 auto Matches = match(*I, Req, &Incomplete);
500 EXPECT_TRUE(Req.Limit);
501 EXPECT_EQ(Matches.size(), *Req.Limit);
502 EXPECT_TRUE(Incomplete);
503 }
504
TEST(DexTest,FuzzyMatch)505 TEST(DexTest, FuzzyMatch) {
506 auto I = Dex::build(
507 generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}),
508 RefSlab());
509 FuzzyFindRequest Req;
510 Req.Query = "lol";
511 Req.AnyScope = true;
512 Req.Limit = 2;
513 EXPECT_THAT(match(*I, Req),
514 UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
515 }
516
TEST(DexTest,ShortQuery)517 TEST(DexTest, ShortQuery) {
518 auto I = Dex::build(generateSymbols({"OneTwoThreeFour"}), RefSlab());
519 FuzzyFindRequest Req;
520 Req.AnyScope = true;
521 bool Incomplete;
522
523 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour"));
524 EXPECT_FALSE(Incomplete) << "Empty string is not a short query";
525
526 Req.Query = "t";
527 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre());
528 EXPECT_TRUE(Incomplete) << "Short queries have different semantics";
529
530 Req.Query = "tt";
531 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre());
532 EXPECT_TRUE(Incomplete) << "Short queries have different semantics";
533
534 Req.Query = "ttf";
535 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour"));
536 EXPECT_FALSE(Incomplete) << "3-char string is not a short query";
537 }
538
TEST(DexTest,MatchQualifiedNamesWithoutSpecificScope)539 TEST(DexTest, MatchQualifiedNamesWithoutSpecificScope) {
540 auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
541 FuzzyFindRequest Req;
542 Req.AnyScope = true;
543 Req.Query = "y";
544 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
545 }
546
TEST(DexTest,MatchQualifiedNamesWithGlobalScope)547 TEST(DexTest, MatchQualifiedNamesWithGlobalScope) {
548 auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab());
549 FuzzyFindRequest Req;
550 Req.Query = "y";
551 Req.Scopes = {""};
552 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3"));
553 }
554
TEST(DexTest,MatchQualifiedNamesWithOneScope)555 TEST(DexTest, MatchQualifiedNamesWithOneScope) {
556 auto I = Dex::build(
557 generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab());
558 FuzzyFindRequest Req;
559 Req.Query = "y";
560 Req.Scopes = {"a::"};
561 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2"));
562 }
563
TEST(DexTest,MatchQualifiedNamesWithMultipleScopes)564 TEST(DexTest, MatchQualifiedNamesWithMultipleScopes) {
565 auto I = Dex::build(
566 generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab());
567 FuzzyFindRequest Req;
568 Req.Query = "y";
569 Req.Scopes = {"a::", "b::"};
570 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3"));
571 }
572
TEST(DexTest,NoMatchNestedScopes)573 TEST(DexTest, NoMatchNestedScopes) {
574 auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab());
575 FuzzyFindRequest Req;
576 Req.Query = "y";
577 Req.Scopes = {"a::"};
578 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1"));
579 }
580
TEST(DexTest,WildcardScope)581 TEST(DexTest, WildcardScope) {
582 auto I =
583 Dex::build(generateSymbols({"a::y1", "a::b::y2", "c::y3"}), RefSlab());
584 FuzzyFindRequest Req;
585 Req.AnyScope = true;
586 Req.Query = "y";
587 Req.Scopes = {"a::"};
588 EXPECT_THAT(match(*I, Req),
589 UnorderedElementsAre("a::y1", "a::b::y2", "c::y3"));
590 }
591
TEST(DexTest,IgnoreCases)592 TEST(DexTest, IgnoreCases) {
593 auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab());
594 FuzzyFindRequest Req;
595 Req.Query = "AB";
596 Req.Scopes = {"ns::"};
597 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
598 }
599
TEST(DexTest,UnknownPostingList)600 TEST(DexTest, UnknownPostingList) {
601 // Regression test: we used to ignore unknown scopes and accept any symbol.
602 auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab());
603 FuzzyFindRequest Req;
604 Req.Scopes = {"ns2::"};
605 EXPECT_THAT(match(*I, Req), UnorderedElementsAre());
606 }
607
TEST(DexTest,Lookup)608 TEST(DexTest, Lookup) {
609 auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab());
610 EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc"));
611 EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}),
612 UnorderedElementsAre("ns::abc", "ns::xyz"));
613 EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}),
614 UnorderedElementsAre("ns::xyz"));
615 EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre());
616 }
617
TEST(DexTest,SymbolIndexOptionsFilter)618 TEST(DexTest, SymbolIndexOptionsFilter) {
619 auto CodeCompletionSymbol = symbol("Completion");
620 auto NonCodeCompletionSymbol = symbol("NoCompletion");
621 CodeCompletionSymbol.Flags = Symbol::SymbolFlag::IndexedForCodeCompletion;
622 NonCodeCompletionSymbol.Flags = Symbol::SymbolFlag::None;
623 std::vector<Symbol> Symbols{CodeCompletionSymbol, NonCodeCompletionSymbol};
624 Dex I(Symbols, RefSlab());
625 FuzzyFindRequest Req;
626 Req.AnyScope = true;
627 Req.RestrictForCodeCompletion = false;
628 EXPECT_THAT(match(I, Req), ElementsAre("Completion", "NoCompletion"));
629 Req.RestrictForCodeCompletion = true;
630 EXPECT_THAT(match(I, Req), ElementsAre("Completion"));
631 }
632
TEST(DexTest,ProximityPathsBoosting)633 TEST(DexTest, ProximityPathsBoosting) {
634 auto RootSymbol = symbol("root::abc");
635 RootSymbol.CanonicalDeclaration.FileURI = "unittest:///file.h";
636 auto CloseSymbol = symbol("close::abc");
637 CloseSymbol.CanonicalDeclaration.FileURI = "unittest:///a/b/c/d/e/f/file.h";
638
639 std::vector<Symbol> Symbols{CloseSymbol, RootSymbol};
640 Dex I(Symbols, RefSlab());
641
642 FuzzyFindRequest Req;
643 Req.AnyScope = true;
644 Req.Query = "abc";
645 // The best candidate can change depending on the proximity paths.
646 Req.Limit = 1;
647
648 // FuzzyFind request comes from the file which is far from the root: expect
649 // CloseSymbol to come out.
650 Req.ProximityPaths = {testPath("a/b/c/d/e/f/file.h")};
651 EXPECT_THAT(match(I, Req), ElementsAre("close::abc"));
652
653 // FuzzyFind request comes from the file which is close to the root: expect
654 // RootSymbol to come out.
655 Req.ProximityPaths = {testPath("file.h")};
656 EXPECT_THAT(match(I, Req), ElementsAre("root::abc"));
657 }
658
TEST(DexTests,Refs)659 TEST(DexTests, Refs) {
660 llvm::DenseMap<SymbolID, std::vector<Ref>> Refs;
661 auto AddRef = [&](const Symbol &Sym, const char *Filename, RefKind Kind) {
662 auto &SymbolRefs = Refs[Sym.ID];
663 SymbolRefs.emplace_back();
664 SymbolRefs.back().Kind = Kind;
665 SymbolRefs.back().Location.FileURI = Filename;
666 };
667 auto Foo = symbol("foo");
668 auto Bar = symbol("bar");
669 AddRef(Foo, "foo.h", RefKind::Declaration);
670 AddRef(Foo, "foo.cc", RefKind::Definition);
671 AddRef(Foo, "reffoo.h", RefKind::Reference);
672 AddRef(Bar, "bar.h", RefKind::Declaration);
673
674 RefsRequest Req;
675 Req.IDs.insert(Foo.ID);
676 Req.Filter = RefKind::Declaration | RefKind::Definition;
677
678 std::vector<std::string> Files;
679 Dex(std::vector<Symbol>{Foo, Bar}, Refs).refs(Req, [&](const Ref &R) {
680 Files.push_back(R.Location.FileURI);
681 });
682 EXPECT_THAT(Files, UnorderedElementsAre("foo.h", "foo.cc"));
683
684 Req.Limit = 1;
685 Files.clear();
686 Dex(std::vector<Symbol>{Foo, Bar}, Refs).refs(Req, [&](const Ref &R) {
687 Files.push_back(R.Location.FileURI);
688 });
689 EXPECT_THAT(Files, ElementsAre(AnyOf("foo.h", "foo.cc")));
690 }
691
692 } // namespace
693 } // namespace dex
694 } // namespace clangd
695 } // namespace clang
696