843 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "TestFS.h"10#include "TestIndex.h"11#include "index/Index.h"12#include "index/SymbolID.h"13#include "index/dex/Dex.h"14#include "index/dex/Iterator.h"15#include "index/dex/Token.h"16#include "index/dex/Trigram.h"17#include "llvm/Support/ScopedPrinter.h"18#include "gmock/gmock.h"19#include "gtest/gtest.h"20#include <string>21#include <vector>22 23using ::testing::AnyOf;24using ::testing::ElementsAre;25using ::testing::IsEmpty;26using ::testing::UnorderedElementsAre;27 28namespace clang {29namespace clangd {30namespace dex {31namespace {32 33//===----------------------------------------------------------------------===//34// Query iterator tests.35//===----------------------------------------------------------------------===//36 37std::vector<DocID> consumeIDs(Iterator &It) {38 auto IDAndScore = consume(It);39 std::vector<DocID> IDs(IDAndScore.size());40 for (size_t I = 0; I < IDAndScore.size(); ++I)41 IDs[I] = IDAndScore[I].first;42 return IDs;43}44 45TEST(DexIterators, DocumentIterator) {46 const PostingList L({4, 7, 8, 20, 42, 100});47 auto DocIterator = L.iterator();48 49 EXPECT_EQ(DocIterator->peek(), 4U);50 EXPECT_FALSE(DocIterator->reachedEnd());51 52 DocIterator->advance();53 EXPECT_EQ(DocIterator->peek(), 7U);54 EXPECT_FALSE(DocIterator->reachedEnd());55 56 DocIterator->advanceTo(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 68TEST(DexIterators, AndTwoLists) {69 Corpus C{10000};70 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});71 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});72 73 auto And = C.intersect(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 93TEST(DexIterators, AndThreeLists) {94 Corpus C{10000};95 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});96 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});97 const PostingList L2({1, 4, 7, 11, 30, 60, 320, 9000});98 99 auto And = C.intersect(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 108TEST(DexIterators, AndEmpty) {109 Corpus C{10000};110 const PostingList L1{1};111 const PostingList L2{2};112 // These iterators are empty, but the optimizer can't tell.113 auto Empty1 = C.intersect(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 120TEST(DexIterators, OrTwoLists) {121 Corpus C{10000};122 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});123 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});124 125 auto Or = C.unionOf(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 154TEST(DexIterators, OrThreeLists) {155 Corpus C{10000};156 const PostingList L0({0, 5, 7, 10, 42, 320, 9000});157 const PostingList L1({0, 4, 7, 10, 30, 60, 320, 9000});158 const PostingList L2({1, 4, 7, 11, 30, 60, 320, 9000});159 160 auto Or = C.unionOf(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 real181// queries. It should be updated once new iterators (such as boosting, limiting,182// etc iterators) appear. However, it is not exhaustive and it would be183// beneficial to implement automatic generation (e.g. fuzzing) of query trees184// for more comprehensive testing.185TEST(DexIterators, QueryTree) {186 //187 // +-----------------+188 // |And Iterator:1, 5|189 // +--------+--------+190 // |191 // |192 // +-------------+----------------------+193 // | |194 // | |195 // +----------v----------+ +----------v------------+196 // |And Iterator: 1, 5, 9| |Or Iterator: 0, 1, 3, 5|197 // +----------+----------+ +----------+------------+198 // | |199 // +------+-----+ ------------+200 // | | | |201 // +-------v-----+ +----+---+ +---v----+ +----v---+202 // |1, 3, 5, 8, 9| |Boost: 2| |Boost: 3| |Boost: 4|203 // +-------------+ +----+---+ +---+----+ +----+---+204 // | | |205 // +----v-----+ +-v--+ +---v---+206 // |1, 5, 7, 9| |1, 5| |0, 3, 5|207 // +----------+ +----+ +-------+208 //209 Corpus C{10};210 const PostingList L0({1, 3, 5, 8, 9});211 const PostingList L1({1, 5, 7, 9});212 const PostingList L2({1, 5});213 const PostingList L3({0, 3, 5});214 215 // Root of the query tree: [1, 5]216 auto Root = C.intersect(217 // Lower And Iterator: [1, 5, 9]218 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 241TEST(DexIterators, StringRepresentation) {242 Corpus C{10};243 const PostingList L1({1, 3, 5});244 const PostingList L2({1, 7, 9});245 246 // No token given, prints full posting list.247 auto I1 = L1.iterator();248 EXPECT_EQ(llvm::to_string(*I1), "[1 3 5]");249 250 // Token given, uses token's string representation.251 Token Tok(Token::Kind::Trigram, "L2");252 auto I2 = L1.iterator(&Tok);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 261TEST(DexIterators, Limit) {262 Corpus C{10000};263 const PostingList L0({3, 6, 7, 20, 42, 100});264 const PostingList L1({1, 3, 5, 6, 7, 30, 100});265 const PostingList L2({0, 3, 5, 7, 8, 100});266 267 auto DocIterator = C.limit(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 282TEST(DexIterators, True) {283 EXPECT_TRUE(Corpus{0}.all()->reachedEnd());284 EXPECT_THAT(consumeIDs(*Corpus{4}.all()), ElementsAre(0, 1, 2, 3));285}286 287TEST(DexIterators, Boost) {288 Corpus C{5};289 auto BoostIterator = C.boost(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 316TEST(DexIterators, Optimizations) {317 Corpus C{5};318 const PostingList L1{1};319 const PostingList L2{2};320 const PostingList L3{3};321 322 // empty and/or yield true/false323 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-circuit327 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 flattened335 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 levels343 EXPECT_EQ(llvm::to_string(*C.intersect(344 C.intersect(L1.iterator(), C.intersect()), C.unionOf(C.all()))),345 "[1]");346}347 348//===----------------------------------------------------------------------===//349// Search token tests.350//===----------------------------------------------------------------------===//351 352::testing::Matcher<std::vector<Token>>353tokensAre(std::initializer_list<std::string> Strings, Token::Kind Kind) {354 std::vector<Token> Tokens;355 for (const auto &TokenData : Strings) {356 Tokens.push_back(Token(Kind, TokenData));357 }358 return ::testing::UnorderedElementsAreArray(Tokens);359}360 361::testing::Matcher<std::vector<Token>>362trigramsAre(std::initializer_list<std::string> Trigrams) {363 return tokensAre(Trigrams, Token::Kind::Trigram);364}365 366std::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 375TEST(DexTrigrams, IdentifierTrigrams) {376 EXPECT_THAT(identifierTrigramTokens("X86"), trigramsAre({"x86", "x", "x8"}));377 378 EXPECT_THAT(identifierTrigramTokens("nl"), trigramsAre({"nl", "n"}));379 380 EXPECT_THAT(identifierTrigramTokens("n"), trigramsAre({"n"}));381 382 EXPECT_THAT(identifierTrigramTokens("clangd"),383 trigramsAre({"c", "cl", "cla", "lan", "ang", "ngd"}));384 385 EXPECT_THAT(identifierTrigramTokens("abc_def"),386 trigramsAre({"a", "d", "ab", "ad", "de", "abc", "abd", "ade",387 "bcd", "bde", "cde", "def"}));388 389 EXPECT_THAT(identifierTrigramTokens("a_b_c_d_e_"),390 trigramsAre({"a", "b", "ab", "bc", "abc", "bcd", "cde"}));391 392 EXPECT_THAT(identifierTrigramTokens("unique_ptr"),393 trigramsAre({"u", "p", "un", "up", "pt", "uni", "unp",394 "upt", "niq", "nip", "npt", "iqu", "iqp", "ipt",395 "que", "qup", "qpt", "uep", "ept", "ptr"}));396 397 EXPECT_THAT(identifierTrigramTokens("TUDecl"),398 trigramsAre({"t", "d", "tu", "td", "de", "tud", "tde", "ude",399 "dec", "ecl"}));400 401 EXPECT_THAT(identifierTrigramTokens("IsOK"),402 trigramsAre({"i", "o", "is", "ok", "io", "iso", "iok", "sok"}));403 404 EXPECT_THAT(identifierTrigramTokens("_pb"),405 trigramsAre({"_", "_p", "p", "pb"}));406 EXPECT_THAT(identifierTrigramTokens("__pb"),407 trigramsAre({"_", "_p", "p", "pb"}));408 409 EXPECT_THAT(identifierTrigramTokens("abc_defGhij__klm"),410 trigramsAre({"a", "d", "ab", "ad", "dg", "de", "abc",411 "abd", "ade", "adg", "bcd", "bde", "bdg", "cde",412 "cdg", "def", "deg", "dgh", "dgk", "efg", "egh",413 "egk", "fgh", "fgk", "ghi", "ghk", "gkl", "hij",414 "hik", "hkl", "ijk", "ikl", "jkl", "klm"}));415 EXPECT_THAT(identifierTrigramTokens(""), IsEmpty());416}417 418TEST(DexTrigrams, QueryTrigrams) {419 EXPECT_THAT(generateQueryTrigrams("c"), trigramsAre({"c"}));420 EXPECT_THAT(generateQueryTrigrams("cl"), trigramsAre({"cl"}));421 EXPECT_THAT(generateQueryTrigrams("cla"), trigramsAre({"cla"}));422 423 EXPECT_THAT(generateQueryTrigrams(""), trigramsAre({}));424 EXPECT_THAT(generateQueryTrigrams("_"), trigramsAre({"_"}));425 EXPECT_THAT(generateQueryTrigrams("__"), trigramsAre({"_"}));426 EXPECT_THAT(generateQueryTrigrams("___"), trigramsAre({"_"}));427 428 EXPECT_THAT(generateQueryTrigrams("m_"), trigramsAre({"m"}));429 430 EXPECT_THAT(generateQueryTrigrams("p_b"), trigramsAre({"pb"}));431 EXPECT_THAT(generateQueryTrigrams("pb_"), trigramsAre({"pb"}));432 EXPECT_THAT(generateQueryTrigrams("_p"), trigramsAre({"_p"}));433 EXPECT_THAT(generateQueryTrigrams("_pb_"), trigramsAre({"pb"}));434 EXPECT_THAT(generateQueryTrigrams("__pb"), trigramsAre({"pb"}));435 436 EXPECT_THAT(generateQueryTrigrams("X86"), trigramsAre({"x86"}));437 438 EXPECT_THAT(generateQueryTrigrams("clangd"),439 trigramsAre({"cla", "lan", "ang", "ngd"}));440 441 EXPECT_THAT(generateQueryTrigrams("abc_def"),442 trigramsAre({"abc", "bcd", "cde", "def"}));443 444 EXPECT_THAT(generateQueryTrigrams("a_b_c_d_e_"),445 trigramsAre({"abc", "bcd", "cde"}));446 447 EXPECT_THAT(generateQueryTrigrams("unique_ptr"),448 trigramsAre({"uni", "niq", "iqu", "que", "uep", "ept", "ptr"}));449 450 EXPECT_THAT(generateQueryTrigrams("TUDecl"),451 trigramsAre({"tud", "ude", "dec", "ecl"}));452 453 EXPECT_THAT(generateQueryTrigrams("IsOK"), trigramsAre({"iso", "sok"}));454 455 EXPECT_THAT(generateQueryTrigrams("abc_defGhij__klm"),456 trigramsAre({"abc", "bcd", "cde", "def", "efg", "fgh", "ghi",457 "hij", "ijk", "jkl", "klm"}));458}459 460TEST(DexSearchTokens, SymbolPath) {461 EXPECT_THAT(generateProximityURIs(462 "unittest:///clang-tools-extra/clangd/index/Token.h"),463 ElementsAre("unittest:///clang-tools-extra/clangd/index/Token.h",464 "unittest:///clang-tools-extra/clangd/index",465 "unittest:///clang-tools-extra/clangd",466 "unittest:///clang-tools-extra", "unittest:///"));467 468 EXPECT_THAT(generateProximityURIs("unittest:///a/b/c.h"),469 ElementsAre("unittest:///a/b/c.h", "unittest:///a/b",470 "unittest:///a", "unittest:///"));471}472 473//===----------------------------------------------------------------------===//474// Index tests.475//===----------------------------------------------------------------------===//476 477TEST(Dex, Lookup) {478 auto I = Dex::build(generateSymbols({"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 488TEST(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 513TEST(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 527TEST(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 539TEST(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 582TEST(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 591TEST(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 600TEST(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 610TEST(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 620TEST(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 629TEST(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 640TEST(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 649TEST(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 658TEST(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 669TEST(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 684TEST(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: expect700 // 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: expect705 // RootSymbol to come out.706 Req.ProximityPaths = {testPath("file.h")};707 EXPECT_THAT(match(I, Req), ElementsAre("root::abc"));708}709 710TEST(DexTests, Refs) {711 llvm::DenseMap<SymbolID, std::vector<Ref>> Refs;712 auto AddRef = [&](const Symbol &Sym, const char *Filename, RefKind Kind) {713 auto &SymbolRefs = Refs[Sym.ID];714 SymbolRefs.emplace_back();715 SymbolRefs.back().Kind = Kind;716 SymbolRefs.back().Location.FileURI = Filename;717 };718 auto Foo = symbol("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 745TEST(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 767TEST(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 781TEST(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 803TEST(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} // namespace840} // namespace dex841} // namespace clangd842} // namespace clang843