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

source code of clang-tools-extra/clangd/unittests/DexTests.cpp