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 23 using ::testing::AnyOf; 24 using ::testing::ElementsAre; 25 using ::testing::IsEmpty; 26 using ::testing::UnorderedElementsAre; 27 28 namespace clang { 29 namespace clangd { 30 namespace dex { 31 namespace { 32 33 //===----------------------------------------------------------------------===// 34 // Query iterator tests. 35 //===----------------------------------------------------------------------===// 36 37 std::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 45 TEST(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(20); 57 EXPECT_EQ(DocIterator->peek(), 20U); 58 EXPECT_FALSE(DocIterator->reachedEnd()); 59 60 DocIterator->advanceTo(65); 61 EXPECT_EQ(DocIterator->peek(), 100U); 62 EXPECT_FALSE(DocIterator->reachedEnd()); 63 64 DocIterator->advanceTo(420); 65 EXPECT_TRUE(DocIterator->reachedEnd()); 66 } 67 68 TEST(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(L1.iterator(), L0.iterator()); 74 75 EXPECT_FALSE(And->reachedEnd()); 76 EXPECT_THAT(consumeIDs(*And), ElementsAre(0U, 7U, 10U, 320U, 9000U)); 77 78 And = C.intersect(L0.iterator(), L1.iterator()); 79 80 And->advanceTo(0); 81 EXPECT_EQ(And->peek(), 0U); 82 And->advanceTo(5); 83 EXPECT_EQ(And->peek(), 7U); 84 And->advanceTo(10); 85 EXPECT_EQ(And->peek(), 10U); 86 And->advanceTo(42); 87 EXPECT_EQ(And->peek(), 320U); 88 And->advanceTo(8999); 89 EXPECT_EQ(And->peek(), 9000U); 90 And->advanceTo(9001); 91 } 92 93 TEST(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(L0.iterator(), L1.iterator(), L2.iterator()); 100 EXPECT_EQ(And->peek(), 7U); 101 And->advanceTo(300); 102 EXPECT_EQ(And->peek(), 320U); 103 And->advanceTo(100000); 104 105 EXPECT_TRUE(And->reachedEnd()); 106 } 107 108 TEST(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(L1.iterator(), L2.iterator()); 114 auto Empty2 = C.intersect(L1.iterator(), L2.iterator()); 115 // And syncs iterators on construction, and used to fail on empty children. 116 auto And = C.intersect(std::move(Empty1), std::move(Empty2)); 117 EXPECT_TRUE(And->reachedEnd()); 118 } 119 120 TEST(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(L0.iterator(), 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(42); 140 EXPECT_EQ(Or->peek(), 42U); 141 Or->advanceTo(300); 142 EXPECT_EQ(Or->peek(), 320U); 143 Or->advanceTo(9000); 144 EXPECT_EQ(Or->peek(), 9000U); 145 Or->advanceTo(9001); 146 EXPECT_TRUE(Or->reachedEnd()); 147 148 Or = C.unionOf(L0.iterator(), L1.iterator()); 149 150 EXPECT_THAT(consumeIDs(*Or), 151 ElementsAre(0U, 4U, 5U, 7U, 10U, 30U, 42U, 60U, 320U, 9000U)); 152 } 153 154 TEST(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(L0.iterator(), L1.iterator(), 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(7); 172 173 Or->advanceTo(59); 174 EXPECT_EQ(Or->peek(), 60U); 175 176 Or->advanceTo(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. 185 TEST(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 C.intersect(L0.iterator(), C.boost(L1.iterator(), 2U)), 219 // Lower Or Iterator: [0, 1, 5] 220 C.unionOf(C.boost(L2.iterator(), 3U), C.boost(L3.iterator(), 4U))); 221 222 EXPECT_FALSE(Root->reachedEnd()); 223 EXPECT_EQ(Root->peek(), 1U); 224 Root->advanceTo(0); 225 // Advance multiple times. Shouldn't do anything. 226 Root->advanceTo(1); 227 Root->advanceTo(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(5); 234 EXPECT_EQ(Root->peek(), 5U); 235 ElementBoost = Root->consume(); 236 EXPECT_THAT(ElementBoost, 8); 237 Root->advanceTo(9000); 238 EXPECT_TRUE(Root->reachedEnd()); 239 } 240 241 TEST(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); 253 EXPECT_EQ(llvm::to_string(*I2), "T=L2"); 254 255 auto Tree = C.limit(C.intersect(std::move(I1), std::move(I2)), 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 261 TEST(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(L0.iterator(), 42); 268 EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre(3, 6, 7, 20, 42, 100)); 269 270 DocIterator = C.limit(L0.iterator(), 3); 271 EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre(3, 6, 7)); 272 273 DocIterator = C.limit(L0.iterator(), 0); 274 EXPECT_THAT(consumeIDs(*DocIterator), ElementsAre()); 275 276 auto AndIterator = 277 C.intersect(C.limit(C.all(), 343), C.limit(L0.iterator(), 2), 278 C.limit(L1.iterator(), 3), C.limit(L2.iterator(), 42)); 279 EXPECT_THAT(consumeIDs(*AndIterator), ElementsAre(3, 7)); 280 } 281 282 TEST(DexIterators, True) { 283 EXPECT_TRUE(Corpus{0}.all()->reachedEnd()); 284 EXPECT_THAT(consumeIDs(*Corpus{4}.all()), ElementsAre(0, 1, 2, 3)); 285 } 286 287 TEST(DexIterators, Boost) { 288 Corpus C{5}; 289 auto BoostIterator = C.boost(C.all(), 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(C.all(), C.boost(L0.iterator(), 2U), 297 C.boost(L1.iterator(), 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(4); 312 ElementBoost = Root->consume(); 313 EXPECT_THAT(ElementBoost, 3); 314 } 315 316 TEST(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>> 353 tokensAre(std::initializer_list<std::string> Strings, Token::Kind Kind) { 354 std::vector<Token> Tokens; 355 for (const auto &TokenData : Strings) { 356 Tokens.push_back(Token(Kind, TokenData)); 357 } 358 return ::testing::UnorderedElementsAreArray(Tokens); 359 } 360 361 ::testing::Matcher<std::vector<Token>> 362 trigramsAre(std::initializer_list<std::string> Trigrams) { 363 return tokensAre(Trigrams, Token::Kind::Trigram); 364 } 365 366 std::vector<Token> identifierTrigramTokens(llvm::StringRef S) { 367 std::vector<Trigram> Trigrams; 368 generateIdentifierTrigrams(S, Trigrams); 369 std::vector<Token> Tokens; 370 for (Trigram T : Trigrams) 371 Tokens.emplace_back(Token::Kind::Trigram, T.str()); 372 return Tokens; 373 } 374 375 TEST(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 418 TEST(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 460 TEST(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 477 TEST(Dex, Lookup) { 478 auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(), 479 RelationSlab(), 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 488 TEST(Dex, FuzzyFind) { 489 auto Index = 490 Dex::build(generateSymbols({"ns::ABC", "ns::BCD", "::ABC", 491 "ns::nested::ABC", "other::ABC", "other::A"}), 492 RefSlab(), RelationSlab(), 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 513 TEST(DexTest, DexLimitedNumMatches) { 514 auto I = 515 Dex::build(generateNumSymbols(0, 100), RefSlab(), RelationSlab(), true); 516 FuzzyFindRequest Req; 517 Req.Query = "5"; 518 Req.AnyScope = true; 519 Req.Limit = 3; 520 bool Incomplete; 521 auto Matches = match(*I, Req, &Incomplete); 522 EXPECT_TRUE(Req.Limit); 523 EXPECT_EQ(Matches.size(), *Req.Limit); 524 EXPECT_TRUE(Incomplete); 525 } 526 527 TEST(DexTest, FuzzyMatch) { 528 auto I = Dex::build( 529 generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}), 530 RefSlab(), RelationSlab(), 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 539 TEST(DexTest, ShortQuery) { 540 auto I = Dex::build(generateSymbols({"_OneTwoFourSix"}), RefSlab(), 541 RelationSlab(), 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 582 TEST(DexTest, MatchQualifiedNamesWithoutSpecificScope) { 583 auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(), 584 RelationSlab(), 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 591 TEST(DexTest, MatchQualifiedNamesWithGlobalScope) { 592 auto I = Dex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(), 593 RelationSlab(), true); 594 FuzzyFindRequest Req; 595 Req.Query = "y"; 596 Req.Scopes = {""}; 597 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3")); 598 } 599 600 TEST(DexTest, MatchQualifiedNamesWithOneScope) { 601 auto I = 602 Dex::build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), 603 RefSlab(), RelationSlab(), 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 610 TEST(DexTest, MatchQualifiedNamesWithMultipleScopes) { 611 auto I = 612 Dex::build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), 613 RefSlab(), RelationSlab(), 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 620 TEST(DexTest, NoMatchNestedScopes) { 621 auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab(), 622 RelationSlab(), true); 623 FuzzyFindRequest Req; 624 Req.Query = "y"; 625 Req.Scopes = {"a::"}; 626 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1")); 627 } 628 629 TEST(DexTest, WildcardScope) { 630 auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2", "c::y3"}), 631 RefSlab(), RelationSlab(), 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 640 TEST(DexTest, IgnoreCases) { 641 auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(), 642 RelationSlab(), 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 649 TEST(DexTest, UnknownPostingList) { 650 // Regression test: we used to ignore unknown scopes and accept any symbol. 651 auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(), 652 RelationSlab(), true); 653 FuzzyFindRequest Req; 654 Req.Scopes = {"ns2::"}; 655 EXPECT_THAT(match(*I, Req), UnorderedElementsAre()); 656 } 657 658 TEST(DexTest, Lookup) { 659 auto I = Dex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(), 660 RelationSlab(), 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 669 TEST(DexTest, SymbolIndexOptionsFilter) { 670 auto CodeCompletionSymbol = symbol("Completion"); 671 auto NonCodeCompletionSymbol = symbol("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 684 TEST(DexTest, ProximityPathsBoosting) { 685 auto RootSymbol = symbol("root::abc"); 686 RootSymbol.CanonicalDeclaration.FileURI = "unittest:///file.h"; 687 auto CloseSymbol = symbol("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("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.h")}; 707 EXPECT_THAT(match(I, Req), ElementsAre("root::abc")); 708 } 709 710 TEST(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("foo"); 719 auto Bar = symbol("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(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 745 TEST(DexTests, Relations) { 746 auto Parent = symbol("Parent"); 747 auto Child1 = symbol("Child1"); 748 auto Child2 = symbol("Child2"); 749 750 std::vector<Symbol> Symbols{Parent, Child1, Child2}; 751 752 std::vector<Relation> Relations{{Parent.ID, RelationKind::BaseOf, Child1.ID}, 753 {Parent.ID, RelationKind::BaseOf, Child2.ID}}; 754 755 Dex I{Symbols, RefSlab(), Relations, true}; 756 757 std::vector<SymbolID> Results; 758 RelationsRequest Req; 759 Req.Subjects.insert(Parent.ID); 760 Req.Predicate = RelationKind::BaseOf; 761 I.relations(Req, [&](const SymbolID &Subject, const Symbol &Object) { 762 Results.push_back(Object.ID); 763 }); 764 EXPECT_THAT(Results, UnorderedElementsAre(Child1.ID, Child2.ID)); 765 } 766 767 TEST(DexIndex, IndexedFiles) { 768 SymbolSlab Symbols; 769 RefSlab Refs; 770 auto Size = Symbols.bytes() + Refs.bytes(); 771 auto Data = std::make_pair(std::move(Symbols), 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 781 TEST(DexTest, PreferredTypesBoosting) { 782 auto Sym1 = symbol("t1"); 783 Sym1.Type = "T1"; 784 auto Sym2 = symbol("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 803 TEST(DexTest, TemplateSpecialization) { 804 SymbolSlab::Builder B; 805 806 Symbol S = symbol("TempSpec"); 807 S.ID = SymbolID("0"); 808 B.insert(S); 809 810 S = symbol("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("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(), 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