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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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