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