1 //===-- IndexTests.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 "Annotations.h" 10 #include "TestIndex.h" 11 #include "TestTU.h" 12 #include "index/FileIndex.h" 13 #include "index/Index.h" 14 #include "index/MemIndex.h" 15 #include "index/Merge.h" 16 #include "index/Symbol.h" 17 #include "clang/Index/IndexSymbol.h" 18 #include "gmock/gmock.h" 19 #include "gtest/gtest.h" 20 21 using ::testing::_; 22 using ::testing::AllOf; 23 using ::testing::AnyOf; 24 using ::testing::ElementsAre; 25 using ::testing::IsEmpty; 26 using ::testing::Pair; 27 using ::testing::Pointee; 28 using ::testing::UnorderedElementsAre; 29 30 namespace clang { 31 namespace clangd { 32 namespace { 33 34 MATCHER_P(Named, N, "") { return arg.Name == N; } 35 MATCHER_P(RefRange, Range, "") { 36 return std::make_tuple(arg.Location.Start.line(), arg.Location.Start.column(), 37 arg.Location.End.line(), arg.Location.End.column()) == 38 std::make_tuple(Range.start.line, Range.start.character, 39 Range.end.line, Range.end.character); 40 } 41 MATCHER_P(FileURI, F, "") { return StringRef(arg.Location.FileURI) == F; } 42 43 TEST(SymbolLocation, Position) { 44 using Position = SymbolLocation::Position; 45 Position Pos; 46 47 Pos.setLine(1); 48 EXPECT_EQ(1u, Pos.line()); 49 Pos.setColumn(2); 50 EXPECT_EQ(2u, Pos.column()); 51 EXPECT_FALSE(Pos.hasOverflow()); 52 53 Pos.setLine(Position::MaxLine + 1); // overflow 54 EXPECT_TRUE(Pos.hasOverflow()); 55 EXPECT_EQ(Pos.line(), Position::MaxLine); 56 Pos.setLine(1); // reset the overflowed line. 57 58 Pos.setColumn(Position::MaxColumn + 1); // overflow 59 EXPECT_TRUE(Pos.hasOverflow()); 60 EXPECT_EQ(Pos.column(), Position::MaxColumn); 61 } 62 63 TEST(SymbolSlab, FindAndIterate) { 64 SymbolSlab::Builder B; 65 B.insert(symbol("Z")); 66 B.insert(symbol("Y")); 67 B.insert(symbol("X")); 68 EXPECT_EQ(nullptr, B.find(SymbolID("W"))); 69 for (const char *Sym : {"X", "Y", "Z"}) 70 EXPECT_THAT(B.find(SymbolID(Sym)), Pointee(Named(Sym))); 71 72 SymbolSlab S = std::move(B).build(); 73 EXPECT_THAT(S, UnorderedElementsAre(Named("X"), Named("Y"), Named("Z"))); 74 EXPECT_EQ(S.end(), S.find(SymbolID("W"))); 75 for (const char *Sym : {"X", "Y", "Z"}) 76 EXPECT_THAT(*S.find(SymbolID(Sym)), Named(Sym)); 77 } 78 79 TEST(RelationSlab, Lookup) { 80 SymbolID A{"A"}; 81 SymbolID B{"B"}; 82 SymbolID C{"C"}; 83 SymbolID D{"D"}; 84 85 RelationSlab::Builder Builder; 86 Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, B}); 87 Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, C}); 88 Builder.insert(Relation{B, index::SymbolRole::RelationBaseOf, D}); 89 Builder.insert(Relation{C, index::SymbolRole::RelationBaseOf, D}); 90 Builder.insert(Relation{B, index::SymbolRole::RelationChildOf, A}); 91 Builder.insert(Relation{C, index::SymbolRole::RelationChildOf, A}); 92 Builder.insert(Relation{D, index::SymbolRole::RelationChildOf, B}); 93 Builder.insert(Relation{D, index::SymbolRole::RelationChildOf, C}); 94 95 RelationSlab Slab = std::move(Builder).build(); 96 EXPECT_THAT( 97 Slab.lookup(A, index::SymbolRole::RelationBaseOf), 98 UnorderedElementsAre(Relation{A, index::SymbolRole::RelationBaseOf, B}, 99 Relation{A, index::SymbolRole::RelationBaseOf, C})); 100 } 101 102 TEST(RelationSlab, Duplicates) { 103 SymbolID A{"A"}; 104 SymbolID B{"B"}; 105 SymbolID C{"C"}; 106 107 RelationSlab::Builder Builder; 108 Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, B}); 109 Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, C}); 110 Builder.insert(Relation{A, index::SymbolRole::RelationBaseOf, B}); 111 112 RelationSlab Slab = std::move(Builder).build(); 113 EXPECT_THAT(Slab, UnorderedElementsAre( 114 Relation{A, index::SymbolRole::RelationBaseOf, B}, 115 Relation{A, index::SymbolRole::RelationBaseOf, C})); 116 } 117 118 TEST(SwapIndexTest, OldIndexRecycled) { 119 auto Token = std::make_shared<int>(); 120 std::weak_ptr<int> WeakToken = Token; 121 122 SwapIndex S(std::make_unique<MemIndex>(SymbolSlab(), RefSlab(), 123 RelationSlab(), std::move(Token), 124 /*BackingDataSize=*/0)); 125 EXPECT_FALSE(WeakToken.expired()); // Current MemIndex keeps it alive. 126 S.reset(std::make_unique<MemIndex>()); // Now the MemIndex is destroyed. 127 EXPECT_TRUE(WeakToken.expired()); // So the token is too. 128 } 129 130 TEST(MemIndexTest, MemIndexDeduplicate) { 131 std::vector<Symbol> Symbols = {symbol("1"), symbol("2"), symbol("3"), 132 symbol("2") /* duplicate */}; 133 FuzzyFindRequest Req; 134 Req.Query = "2"; 135 Req.AnyScope = true; 136 MemIndex I(Symbols, RefSlab(), RelationSlab()); 137 EXPECT_THAT(match(I, Req), ElementsAre("2")); 138 } 139 140 TEST(MemIndexTest, MemIndexLimitedNumMatches) { 141 auto I = 142 MemIndex::build(generateNumSymbols(0, 100), RefSlab(), RelationSlab()); 143 FuzzyFindRequest Req; 144 Req.Query = "5"; 145 Req.AnyScope = true; 146 Req.Limit = 3; 147 bool Incomplete; 148 auto Matches = match(*I, Req, &Incomplete); 149 EXPECT_TRUE(Req.Limit); 150 EXPECT_EQ(Matches.size(), *Req.Limit); 151 EXPECT_TRUE(Incomplete); 152 } 153 154 TEST(MemIndexTest, FuzzyMatch) { 155 auto I = MemIndex::build( 156 generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}), 157 RefSlab(), RelationSlab()); 158 FuzzyFindRequest Req; 159 Req.Query = "lol"; 160 Req.AnyScope = true; 161 Req.Limit = 2; 162 EXPECT_THAT(match(*I, Req), 163 UnorderedElementsAre("LaughingOutLoud", "LittleOldLady")); 164 } 165 166 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) { 167 auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(), 168 RelationSlab()); 169 FuzzyFindRequest Req; 170 Req.Query = "y"; 171 Req.AnyScope = true; 172 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); 173 } 174 175 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) { 176 auto I = MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab(), 177 RelationSlab()); 178 FuzzyFindRequest Req; 179 Req.Query = "y"; 180 Req.Scopes = {""}; 181 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3")); 182 } 183 184 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) { 185 auto I = MemIndex::build( 186 generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab(), 187 RelationSlab()); 188 FuzzyFindRequest Req; 189 Req.Query = "y"; 190 Req.Scopes = {"a::"}; 191 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2")); 192 } 193 194 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) { 195 auto I = MemIndex::build( 196 generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab(), 197 RelationSlab()); 198 FuzzyFindRequest Req; 199 Req.Query = "y"; 200 Req.Scopes = {"a::", "b::"}; 201 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3")); 202 } 203 204 TEST(MemIndexTest, NoMatchNestedScopes) { 205 auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab(), 206 RelationSlab()); 207 FuzzyFindRequest Req; 208 Req.Query = "y"; 209 Req.Scopes = {"a::"}; 210 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1")); 211 } 212 213 TEST(MemIndexTest, IgnoreCases) { 214 auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab(), 215 RelationSlab()); 216 FuzzyFindRequest Req; 217 Req.Query = "AB"; 218 Req.Scopes = {"ns::"}; 219 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); 220 } 221 222 TEST(MemIndexTest, Lookup) { 223 auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab(), 224 RelationSlab()); 225 EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc")); 226 EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}), 227 UnorderedElementsAre("ns::abc", "ns::xyz")); 228 EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), 229 UnorderedElementsAre("ns::xyz")); 230 EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre()); 231 } 232 233 TEST(MemIndexTest, TemplateSpecialization) { 234 SymbolSlab::Builder B; 235 236 Symbol S = symbol("TempSpec"); 237 S.ID = SymbolID("1"); 238 B.insert(S); 239 240 S = symbol("TempSpec"); 241 S.ID = SymbolID("2"); 242 S.TemplateSpecializationArgs = "<int, bool>"; 243 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>( 244 index::SymbolProperty::TemplateSpecialization); 245 B.insert(S); 246 247 S = symbol("TempSpec"); 248 S.ID = SymbolID("3"); 249 S.TemplateSpecializationArgs = "<int, U>"; 250 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>( 251 index::SymbolProperty::TemplatePartialSpecialization); 252 B.insert(S); 253 254 auto I = MemIndex::build(std::move(B).build(), RefSlab(), RelationSlab()); 255 FuzzyFindRequest Req; 256 Req.AnyScope = true; 257 258 Req.Query = "TempSpec"; 259 EXPECT_THAT(match(*I, Req), 260 UnorderedElementsAre("TempSpec", "TempSpec<int, bool>", 261 "TempSpec<int, U>")); 262 263 // FIXME: Add filtering for template argument list. 264 Req.Query = "TempSpec<int"; 265 EXPECT_THAT(match(*I, Req), IsEmpty()); 266 } 267 268 TEST(MergeIndexTest, Lookup) { 269 auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(), 270 RelationSlab()), 271 J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(), 272 RelationSlab()); 273 MergedIndex M(I.get(), J.get()); 274 EXPECT_THAT(lookup(M, SymbolID("ns::A")), UnorderedElementsAre("ns::A")); 275 EXPECT_THAT(lookup(M, SymbolID("ns::B")), UnorderedElementsAre("ns::B")); 276 EXPECT_THAT(lookup(M, SymbolID("ns::C")), UnorderedElementsAre("ns::C")); 277 EXPECT_THAT(lookup(M, {SymbolID("ns::A"), SymbolID("ns::B")}), 278 UnorderedElementsAre("ns::A", "ns::B")); 279 EXPECT_THAT(lookup(M, {SymbolID("ns::A"), SymbolID("ns::C")}), 280 UnorderedElementsAre("ns::A", "ns::C")); 281 EXPECT_THAT(lookup(M, SymbolID("ns::D")), UnorderedElementsAre()); 282 EXPECT_THAT(lookup(M, {}), UnorderedElementsAre()); 283 } 284 285 TEST(MergeIndexTest, FuzzyFind) { 286 auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab(), 287 RelationSlab()), 288 J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab(), 289 RelationSlab()); 290 FuzzyFindRequest Req; 291 Req.Scopes = {"ns::"}; 292 EXPECT_THAT(match(MergedIndex(I.get(), J.get()), Req), 293 UnorderedElementsAre("ns::A", "ns::B", "ns::C")); 294 } 295 296 TEST(MergeTest, Merge) { 297 Symbol L, R; 298 L.ID = R.ID = SymbolID("hello"); 299 L.Name = R.Name = "Foo"; // same in both 300 L.CanonicalDeclaration.FileURI = "file:///left.h"; // differs 301 R.CanonicalDeclaration.FileURI = "file:///right.h"; 302 L.References = 1; 303 R.References = 2; 304 L.Signature = "()"; // present in left only 305 R.CompletionSnippetSuffix = "{$1:0}"; // present in right only 306 R.Documentation = "--doc--"; 307 L.Origin = SymbolOrigin::Dynamic; 308 R.Origin = SymbolOrigin::Static; 309 R.Type = "expectedType"; 310 311 Symbol M = mergeSymbol(L, R); 312 EXPECT_EQ(M.Name, "Foo"); 313 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:///left.h"); 314 EXPECT_EQ(M.References, 3u); 315 EXPECT_EQ(M.Signature, "()"); 316 EXPECT_EQ(M.CompletionSnippetSuffix, "{$1:0}"); 317 EXPECT_EQ(M.Documentation, "--doc--"); 318 EXPECT_EQ(M.Type, "expectedType"); 319 EXPECT_EQ(M.Origin, 320 SymbolOrigin::Dynamic | SymbolOrigin::Static | SymbolOrigin::Merge); 321 } 322 323 TEST(MergeTest, PreferSymbolWithDefn) { 324 Symbol L, R; 325 326 L.ID = R.ID = SymbolID("hello"); 327 L.CanonicalDeclaration.FileURI = "file:/left.h"; 328 R.CanonicalDeclaration.FileURI = "file:/right.h"; 329 L.Name = "left"; 330 R.Name = "right"; 331 332 Symbol M = mergeSymbol(L, R); 333 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/left.h"); 334 EXPECT_EQ(StringRef(M.Definition.FileURI), ""); 335 EXPECT_EQ(M.Name, "left"); 336 337 R.Definition.FileURI = "file:/right.cpp"; // Now right will be favored. 338 M = mergeSymbol(L, R); 339 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/right.h"); 340 EXPECT_EQ(StringRef(M.Definition.FileURI), "file:/right.cpp"); 341 EXPECT_EQ(M.Name, "right"); 342 } 343 344 TEST(MergeTest, PreferSymbolLocationInCodegenFile) { 345 Symbol L, R; 346 347 L.ID = R.ID = SymbolID("hello"); 348 L.CanonicalDeclaration.FileURI = "file:/x.proto.h"; 349 R.CanonicalDeclaration.FileURI = "file:/x.proto"; 350 351 Symbol M = mergeSymbol(L, R); 352 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/x.proto"); 353 354 // Prefer L if both have codegen suffix. 355 L.CanonicalDeclaration.FileURI = "file:/y.proto"; 356 M = mergeSymbol(L, R); 357 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/y.proto"); 358 } 359 360 TEST(MergeIndexTest, Refs) { 361 FileIndex Dyn; 362 FileIndex StaticIndex; 363 MergedIndex Merge(&Dyn, &StaticIndex); 364 365 const char *HeaderCode = "class Foo;"; 366 auto HeaderSymbols = TestTU::withHeaderCode("class Foo;").headerSymbols(); 367 auto Foo = findSymbol(HeaderSymbols, "Foo"); 368 369 // Build dynamic index for test.cc. 370 Annotations Test1Code(R"(class $Foo[[Foo]];)"); 371 TestTU Test; 372 Test.HeaderCode = HeaderCode; 373 Test.Code = Test1Code.code(); 374 Test.Filename = "test.cc"; 375 auto AST = Test.build(); 376 Dyn.updateMain(Test.Filename, AST); 377 378 // Build static index for test.cc. 379 Test.HeaderCode = HeaderCode; 380 Test.Code = "// static\nclass Foo {};"; 381 Test.Filename = "test.cc"; 382 auto StaticAST = Test.build(); 383 // Add stale refs for test.cc. 384 StaticIndex.updateMain(Test.Filename, StaticAST); 385 386 // Add refs for test2.cc 387 Annotations Test2Code(R"(class $Foo[[Foo]] {};)"); 388 TestTU Test2; 389 Test2.HeaderCode = HeaderCode; 390 Test2.Code = Test2Code.code(); 391 Test2.Filename = "test2.cc"; 392 StaticAST = Test2.build(); 393 StaticIndex.updateMain(Test2.Filename, StaticAST); 394 395 RefsRequest Request; 396 Request.IDs = {Foo.ID}; 397 RefSlab::Builder Results; 398 Merge.refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); }); 399 EXPECT_THAT( 400 std::move(Results).build(), 401 ElementsAre(Pair( 402 _, UnorderedElementsAre(AllOf(RefRange(Test1Code.range("Foo")), 403 FileURI("unittest:///test.cc")), 404 AllOf(RefRange(Test2Code.range("Foo")), 405 FileURI("unittest:///test2.cc")))))); 406 407 Request.Limit = 1; 408 RefSlab::Builder Results2; 409 Merge.refs(Request, [&](const Ref &O) { Results2.insert(Foo.ID, O); }); 410 EXPECT_THAT(std::move(Results2).build(), 411 ElementsAre(Pair( 412 _, ElementsAre(AnyOf(FileURI("unittest:///test.cc"), 413 FileURI("unittest:///test2.cc")))))); 414 } 415 416 MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References, "") { 417 return (arg.IncludeHeader == IncludeHeader) && (arg.References == References); 418 } 419 420 TEST(MergeTest, MergeIncludesOnDifferentDefinitions) { 421 Symbol L, R; 422 L.Name = "left"; 423 R.Name = "right"; 424 L.ID = R.ID = SymbolID("hello"); 425 L.IncludeHeaders.emplace_back("common", 1); 426 R.IncludeHeaders.emplace_back("common", 1); 427 R.IncludeHeaders.emplace_back("new", 1); 428 429 // Both have no definition. 430 Symbol M = mergeSymbol(L, R); 431 EXPECT_THAT(M.IncludeHeaders, 432 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u), 433 IncludeHeaderWithRef("new", 1u))); 434 435 // Only merge references of the same includes but do not merge new #includes. 436 L.Definition.FileURI = "file:/left.h"; 437 M = mergeSymbol(L, R); 438 EXPECT_THAT(M.IncludeHeaders, 439 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u))); 440 441 // Definitions are the same. 442 R.Definition.FileURI = "file:/right.h"; 443 M = mergeSymbol(L, R); 444 EXPECT_THAT(M.IncludeHeaders, 445 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u), 446 IncludeHeaderWithRef("new", 1u))); 447 448 // Definitions are different. 449 R.Definition.FileURI = "file:/right.h"; 450 M = mergeSymbol(L, R); 451 EXPECT_THAT(M.IncludeHeaders, 452 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u), 453 IncludeHeaderWithRef("new", 1u))); 454 } 455 456 } // namespace 457 } // namespace clangd 458 } // namespace clang 459