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