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 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 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 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 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 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 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 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. 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 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 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 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 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 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>> 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>> 365 trigramsAre(std::initializer_list<std::string> Trigrams) { 366 return tokensAre(Trigrams, Token::Kind::Trigram); 367 } 368 369 TEST(DexTrigrams, IdentifierTrigrams) { 370 EXPECT_THAT(generateIdentifierTrigrams("X86"), 371 trigramsAre({"x86", "x", "x8"})); 372 373 EXPECT_THAT(generateIdentifierTrigrams("nl"), trigramsAre({"nl", "n"})); 374 375 EXPECT_THAT(generateIdentifierTrigrams("n"), trigramsAre({"n"})); 376 377 EXPECT_THAT(generateIdentifierTrigrams("clangd"), 378 trigramsAre({"c", "cl", "cla", "lan", "ang", "ngd"})); 379 380 EXPECT_THAT(generateIdentifierTrigrams("abc_def"), 381 trigramsAre({"a", "ab", "ad", "abc", "abd", "ade", "bcd", "bde", 382 "cde", "def"})); 383 384 EXPECT_THAT(generateIdentifierTrigrams("a_b_c_d_e_"), 385 trigramsAre({"a", "a_", "ab", "abc", "bcd", "cde"})); 386 387 EXPECT_THAT(generateIdentifierTrigrams("unique_ptr"), 388 trigramsAre({"u", "un", "up", "uni", "unp", "upt", "niq", "nip", 389 "npt", "iqu", "iqp", "ipt", "que", "qup", "qpt", 390 "uep", "ept", "ptr"})); 391 392 EXPECT_THAT( 393 generateIdentifierTrigrams("TUDecl"), 394 trigramsAre({"t", "tu", "td", "tud", "tde", "ude", "dec", "ecl"})); 395 396 EXPECT_THAT(generateIdentifierTrigrams("IsOK"), 397 trigramsAre({"i", "is", "io", "iso", "iok", "sok"})); 398 399 EXPECT_THAT( 400 generateIdentifierTrigrams("abc_defGhij__klm"), 401 trigramsAre({"a", "ab", "ad", "abc", "abd", "ade", "adg", "bcd", 402 "bde", "bdg", "cde", "cdg", "def", "deg", "dgh", "dgk", 403 "efg", "egh", "egk", "fgh", "fgk", "ghi", "ghk", "gkl", 404 "hij", "hik", "hkl", "ijk", "ikl", "jkl", "klm"})); 405 } 406 407 TEST(DexTrigrams, QueryTrigrams) { 408 EXPECT_THAT(generateQueryTrigrams("c"), trigramsAre({"c"})); 409 EXPECT_THAT(generateQueryTrigrams("cl"), trigramsAre({"cl"})); 410 EXPECT_THAT(generateQueryTrigrams("cla"), trigramsAre({"cla"})); 411 412 EXPECT_THAT(generateQueryTrigrams(""), trigramsAre({})); 413 EXPECT_THAT(generateQueryTrigrams("_"), trigramsAre({"_"})); 414 EXPECT_THAT(generateQueryTrigrams("__"), trigramsAre({"__"})); 415 EXPECT_THAT(generateQueryTrigrams("___"), trigramsAre({})); 416 417 EXPECT_THAT(generateQueryTrigrams("X86"), trigramsAre({"x86"})); 418 419 EXPECT_THAT(generateQueryTrigrams("clangd"), 420 trigramsAre({"cla", "lan", "ang", "ngd"})); 421 422 EXPECT_THAT(generateQueryTrigrams("abc_def"), 423 trigramsAre({"abc", "bcd", "cde", "def"})); 424 425 EXPECT_THAT(generateQueryTrigrams("a_b_c_d_e_"), 426 trigramsAre({"abc", "bcd", "cde"})); 427 428 EXPECT_THAT(generateQueryTrigrams("unique_ptr"), 429 trigramsAre({"uni", "niq", "iqu", "que", "uep", "ept", "ptr"})); 430 431 EXPECT_THAT(generateQueryTrigrams("TUDecl"), 432 trigramsAre({"tud", "ude", "dec", "ecl"})); 433 434 EXPECT_THAT(generateQueryTrigrams("IsOK"), trigramsAre({"iso", "sok"})); 435 436 EXPECT_THAT(generateQueryTrigrams("abc_defGhij__klm"), 437 trigramsAre({"abc", "bcd", "cde", "def", "efg", "fgh", "ghi", 438 "hij", "ijk", "jkl", "klm"})); 439 } 440 441 TEST(DexSearchTokens, SymbolPath) { 442 EXPECT_THAT(generateProximityURIs( 443 "unittest:///clang-tools-extra/clangd/index/Token.h"), 444 ElementsAre("unittest:///clang-tools-extra/clangd/index/Token.h", 445 "unittest:///clang-tools-extra/clangd/index", 446 "unittest:///clang-tools-extra/clangd", 447 "unittest:///clang-tools-extra", "unittest:///")); 448 449 EXPECT_THAT(generateProximityURIs("unittest:///a/b/c.h"), 450 ElementsAre("unittest:///a/b/c.h", "unittest:///a/b", 451 "unittest:///a", "unittest:///")); 452 } 453 454 //===----------------------------------------------------------------------===// 455 // Index tests. 456 //===----------------------------------------------------------------------===// 457 458 TEST(Dex, Lookup) { 459 auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(), 460 RelationSlab()); 461 EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc")); 462 EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}), 463 UnorderedElementsAre("ns::abc", "ns::xyz")); 464 EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), 465 UnorderedElementsAre("ns::xyz")); 466 EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre()); 467 } 468 469 TEST(Dex, FuzzyFind) { 470 auto Index = 471 Dex::build(generateSymbols({"ns::ABC", "ns::BCD", "::ABC", 472 "ns::nested::ABC", "other::ABC", "other::A"}), 473 RefSlab(), RelationSlab()); 474 FuzzyFindRequest Req; 475 Req.Query = "ABC"; 476 Req.Scopes = {"ns::"}; 477 EXPECT_THAT(match(*Index, Req), UnorderedElementsAre("ns::ABC")); 478 Req.Scopes = {"ns::", "ns::nested::"}; 479 EXPECT_THAT(match(*Index, Req), 480 UnorderedElementsAre("ns::ABC", "ns::nested::ABC")); 481 Req.Query = "A"; 482 Req.Scopes = {"other::"}; 483 EXPECT_THAT(match(*Index, Req), 484 UnorderedElementsAre("other::A", "other::ABC")); 485 Req.Query = ""; 486 Req.Scopes = {}; 487 Req.AnyScope = true; 488 EXPECT_THAT(match(*Index, Req), 489 UnorderedElementsAre("ns::ABC", "ns::BCD", "::ABC", 490 "ns::nested::ABC", "other::ABC", 491 "other::A")); 492 } 493 494 TEST(DexTest, DexLimitedNumMatches) { 495 auto I = Dex::build(generateNumSymbols(0, 100), RefSlab(), RelationSlab()); 496 FuzzyFindRequest Req; 497 Req.Query = "5"; 498 Req.AnyScope = true; 499 Req.Limit = 3; 500 bool Incomplete; 501 auto Matches = match(*I, Req, &Incomplete); 502 EXPECT_TRUE(Req.Limit); 503 EXPECT_EQ(Matches.size(), *Req.Limit); 504 EXPECT_TRUE(Incomplete); 505 } 506 507 TEST(DexTest, FuzzyMatch) { 508 auto I = Dex::build( 509 generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}), 510 RefSlab(), RelationSlab()); 511 FuzzyFindRequest Req; 512 Req.Query = "lol"; 513 Req.AnyScope = true; 514 Req.Limit = 2; 515 EXPECT_THAT(match(*I, Req), 516 UnorderedElementsAre("LaughingOutLoud", "LittleOldLady")); 517 } 518 519 TEST(DexTest, ShortQuery) { 520 auto I = Dex::build(generateSymbols({"OneTwoThreeFour"}), RefSlab(), 521 RelationSlab()); 522 FuzzyFindRequest Req; 523 Req.AnyScope = true; 524 bool Incomplete; 525 526 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour")); 527 EXPECT_FALSE(Incomplete) << "Empty string is not a short query"; 528 529 Req.Query = "t"; 530 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre()); 531 EXPECT_TRUE(Incomplete) << "Short queries have different semantics"; 532 533 Req.Query = "tt"; 534 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre()); 535 EXPECT_TRUE(Incomplete) << "Short queries have different semantics"; 536 537 Req.Query = "ttf"; 538 EXPECT_THAT(match(*I, Req, &Incomplete), ElementsAre("OneTwoThreeFour")); 539 EXPECT_FALSE(Incomplete) << "3-char string is not a short query"; 540 } 541 542 TEST(DexTest, MatchQualifiedNamesWithoutSpecificScope) { 543 auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(), 544 RelationSlab()); 545 FuzzyFindRequest Req; 546 Req.AnyScope = true; 547 Req.Query = "y"; 548 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); 549 } 550 551 TEST(DexTest, MatchQualifiedNamesWithGlobalScope) { 552 auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(), 553 RelationSlab()); 554 FuzzyFindRequest Req; 555 Req.Query = "y"; 556 Req.Scopes = {""}; 557 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3")); 558 } 559 560 TEST(DexTest, MatchQualifiedNamesWithOneScope) { 561 auto I = 562 Dex::build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), 563 RefSlab(), RelationSlab()); 564 FuzzyFindRequest Req; 565 Req.Query = "y"; 566 Req.Scopes = {"a::"}; 567 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2")); 568 } 569 570 TEST(DexTest, MatchQualifiedNamesWithMultipleScopes) { 571 auto I = 572 Dex::build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), 573 RefSlab(), RelationSlab()); 574 FuzzyFindRequest Req; 575 Req.Query = "y"; 576 Req.Scopes = {"a::", "b::"}; 577 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3")); 578 } 579 580 TEST(DexTest, NoMatchNestedScopes) { 581 auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab(), 582 RelationSlab()); 583 FuzzyFindRequest Req; 584 Req.Query = "y"; 585 Req.Scopes = {"a::"}; 586 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1")); 587 } 588 589 TEST(DexTest, WildcardScope) { 590 auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2", "c::y3"}), 591 RefSlab(), RelationSlab()); 592 FuzzyFindRequest Req; 593 Req.AnyScope = true; 594 Req.Query = "y"; 595 Req.Scopes = {"a::"}; 596 EXPECT_THAT(match(*I, Req), 597 UnorderedElementsAre("a::y1", "a::b::y2", "c::y3")); 598 } 599 600 TEST(DexTest, IgnoreCases) { 601 auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(), 602 RelationSlab()); 603 FuzzyFindRequest Req; 604 Req.Query = "AB"; 605 Req.Scopes = {"ns::"}; 606 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); 607 } 608 609 TEST(DexTest, UnknownPostingList) { 610 // Regression test: we used to ignore unknown scopes and accept any symbol. 611 auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(), 612 RelationSlab()); 613 FuzzyFindRequest Req; 614 Req.Scopes = {"ns2::"}; 615 EXPECT_THAT(match(*I, Req), UnorderedElementsAre()); 616 } 617 618 TEST(DexTest, Lookup) { 619 auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(), 620 RelationSlab()); 621 EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc")); 622 EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}), 623 UnorderedElementsAre("ns::abc", "ns::xyz")); 624 EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), 625 UnorderedElementsAre("ns::xyz")); 626 EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre()); 627 } 628 629 TEST(DexTest, SymbolIndexOptionsFilter) { 630 auto CodeCompletionSymbol = symbol("Completion"); 631 auto NonCodeCompletionSymbol = symbol("NoCompletion"); 632 CodeCompletionSymbol.Flags = Symbol::SymbolFlag::IndexedForCodeCompletion; 633 NonCodeCompletionSymbol.Flags = Symbol::SymbolFlag::None; 634 std::vector<Symbol> Symbols{CodeCompletionSymbol, NonCodeCompletionSymbol}; 635 Dex I(Symbols, RefSlab(), RelationSlab()); 636 FuzzyFindRequest Req; 637 Req.AnyScope = true; 638 Req.RestrictForCodeCompletion = false; 639 EXPECT_THAT(match(I, Req), ElementsAre("Completion", "NoCompletion")); 640 Req.RestrictForCodeCompletion = true; 641 EXPECT_THAT(match(I, Req), ElementsAre("Completion")); 642 } 643 644 TEST(DexTest, ProximityPathsBoosting) { 645 auto RootSymbol = symbol("root::abc"); 646 RootSymbol.CanonicalDeclaration.FileURI = "unittest:///file.h"; 647 auto CloseSymbol = symbol("close::abc"); 648 CloseSymbol.CanonicalDeclaration.FileURI = "unittest:///a/b/c/d/e/f/file.h"; 649 650 std::vector<Symbol> Symbols{CloseSymbol, RootSymbol}; 651 Dex I(Symbols, RefSlab(), RelationSlab()); 652 653 FuzzyFindRequest Req; 654 Req.AnyScope = true; 655 Req.Query = "abc"; 656 // The best candidate can change depending on the proximity paths. 657 Req.Limit = 1; 658 659 // FuzzyFind request comes from the file which is far from the root: expect 660 // CloseSymbol to come out. 661 Req.ProximityPaths = {testPath("a/b/c/d/e/f/file.h")}; 662 EXPECT_THAT(match(I, Req), ElementsAre("close::abc")); 663 664 // FuzzyFind request comes from the file which is close to the root: expect 665 // RootSymbol to come out. 666 Req.ProximityPaths = {testPath("file.h")}; 667 EXPECT_THAT(match(I, Req), ElementsAre("root::abc")); 668 } 669 670 TEST(DexTests, Refs) { 671 llvm::DenseMap<SymbolID, std::vector<Ref>> Refs; 672 auto AddRef = [&](const Symbol &Sym, const char *Filename, RefKind Kind) { 673 auto &SymbolRefs = Refs[Sym.ID]; 674 SymbolRefs.emplace_back(); 675 SymbolRefs.back().Kind = Kind; 676 SymbolRefs.back().Location.FileURI = Filename; 677 }; 678 auto Foo = symbol("foo"); 679 auto Bar = symbol("bar"); 680 AddRef(Foo, "foo.h", RefKind::Declaration); 681 AddRef(Foo, "foo.cc", RefKind::Definition); 682 AddRef(Foo, "reffoo.h", RefKind::Reference); 683 AddRef(Bar, "bar.h", RefKind::Declaration); 684 685 RefsRequest Req; 686 Req.IDs.insert(Foo.ID); 687 Req.Filter = RefKind::Declaration | RefKind::Definition; 688 689 std::vector<std::string> Files; 690 Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab()) 691 .refs(Req, [&](const Ref &R) { Files.push_back(R.Location.FileURI); }); 692 EXPECT_THAT(Files, UnorderedElementsAre("foo.h", "foo.cc")); 693 694 Req.Limit = 1; 695 Files.clear(); 696 Dex(std::vector<Symbol>{Foo, Bar}, Refs, RelationSlab()) 697 .refs(Req, [&](const Ref &R) { Files.push_back(R.Location.FileURI); }); 698 EXPECT_THAT(Files, ElementsAre(AnyOf("foo.h", "foo.cc"))); 699 } 700 701 TEST(DexTests, Relations) { 702 auto Parent = symbol("Parent"); 703 auto Child1 = symbol("Child1"); 704 auto Child2 = symbol("Child2"); 705 706 std::vector<Symbol> Symbols{Parent, Child1, Child2}; 707 708 std::vector<Relation> Relations{{Parent.ID, RelationKind::BaseOf, Child1.ID}, 709 {Parent.ID, RelationKind::BaseOf, Child2.ID}}; 710 711 Dex I{Symbols, RefSlab(), Relations}; 712 713 std::vector<SymbolID> Results; 714 RelationsRequest Req; 715 Req.Subjects.insert(Parent.ID); 716 Req.Predicate = RelationKind::BaseOf; 717 I.relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { 718 Results.push_back(Object.ID); 719 }); 720 EXPECT_THAT(Results, UnorderedElementsAre(Child1.ID, Child2.ID)); 721 } 722 723 TEST(DexTest, PreferredTypesBoosting) { 724 auto Sym1 = symbol("t1"); 725 Sym1.Type = "T1"; 726 auto Sym2 = symbol("t2"); 727 Sym2.Type = "T2"; 728 729 std::vector<Symbol> Symbols{Sym1, Sym2}; 730 Dex I(Symbols, RefSlab(), RelationSlab()); 731 732 FuzzyFindRequest Req; 733 Req.AnyScope = true; 734 Req.Query = "t"; 735 // The best candidate can change depending on the preferred type. 736 Req.Limit = 1; 737 738 Req.PreferredTypes = {Sym1.Type}; 739 EXPECT_THAT(match(I, Req), ElementsAre("t1")); 740 741 Req.PreferredTypes = {Sym2.Type}; 742 EXPECT_THAT(match(I, Req), ElementsAre("t2")); 743 } 744 745 TEST(DexTest, TemplateSpecialization) { 746 SymbolSlab::Builder B; 747 748 Symbol S = symbol("TempSpec"); 749 S.ID = SymbolID("0"); 750 B.insert(S); 751 752 S = symbol("TempSpec"); 753 S.ID = SymbolID("1"); 754 S.TemplateSpecializationArgs = "<int, bool>"; 755 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>( 756 index::SymbolProperty::TemplateSpecialization); 757 B.insert(S); 758 759 S = symbol("TempSpec"); 760 S.ID = SymbolID("2"); 761 S.TemplateSpecializationArgs = "<int, U>"; 762 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>( 763 index::SymbolProperty::TemplatePartialSpecialization); 764 B.insert(S); 765 766 auto I = dex::Dex::build(std::move(B).build(), RefSlab(), RelationSlab()); 767 FuzzyFindRequest Req; 768 Req.AnyScope = true; 769 770 Req.Query = "TempSpec"; 771 EXPECT_THAT(match(*I, Req), 772 UnorderedElementsAre("TempSpec", "TempSpec<int, bool>", 773 "TempSpec<int, U>")); 774 775 // FIXME: Add filtering for template argument list. 776 Req.Query = "TempSpec<int"; 777 EXPECT_THAT(match(*I, Req), IsEmpty()); 778 } 779 780 } // namespace 781 } // namespace dex 782 } // namespace clangd 783 } // namespace clang 784