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