clang-tools-extra/clangd/unittests/DexTests.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-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