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(llvm::make_unique<MemIndex>( 123 SymbolSlab(), RefSlab(), std::move(Token), /*BackingDataSize=*/0)); 124 EXPECT_FALSE(WeakToken.expired()); // Current MemIndex keeps it alive. 125 S.reset(llvm::make_unique<MemIndex>()); // Now the MemIndex is destroyed. 126 EXPECT_TRUE(WeakToken.expired()); // So the token is too. 127 } 128 129 TEST(MemIndexTest, MemIndexDeduplicate) { 130 std::vector<Symbol> Symbols = {symbol("1"), symbol("2"), symbol("3"), 131 symbol("2") /* duplicate */}; 132 FuzzyFindRequest Req; 133 Req.Query = "2"; 134 Req.AnyScope = true; 135 MemIndex I(Symbols, RefSlab()); 136 EXPECT_THAT(match(I, Req), ElementsAre("2")); 137 } 138 139 TEST(MemIndexTest, MemIndexLimitedNumMatches) { 140 auto I = MemIndex::build(generateNumSymbols(0, 100), RefSlab()); 141 FuzzyFindRequest Req; 142 Req.Query = "5"; 143 Req.AnyScope = true; 144 Req.Limit = 3; 145 bool Incomplete; 146 auto Matches = match(*I, Req, &Incomplete); 147 EXPECT_TRUE(Req.Limit); 148 EXPECT_EQ(Matches.size(), *Req.Limit); 149 EXPECT_TRUE(Incomplete); 150 } 151 152 TEST(MemIndexTest, FuzzyMatch) { 153 auto I = MemIndex::build( 154 generateSymbols({"LaughingOutLoud", "LionPopulation", "LittleOldLady"}), 155 RefSlab()); 156 FuzzyFindRequest Req; 157 Req.Query = "lol"; 158 Req.AnyScope = true; 159 Req.Limit = 2; 160 EXPECT_THAT(match(*I, Req), 161 UnorderedElementsAre("LaughingOutLoud", "LittleOldLady")); 162 } 163 164 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) { 165 auto I = 166 MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab()); 167 FuzzyFindRequest Req; 168 Req.Query = "y"; 169 Req.AnyScope = true; 170 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3")); 171 } 172 173 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) { 174 auto I = 175 MemIndex::build(generateSymbols({"a::y1", "b::y2", "y3"}), RefSlab()); 176 FuzzyFindRequest Req; 177 Req.Query = "y"; 178 Req.Scopes = {""}; 179 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("y3")); 180 } 181 182 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) { 183 auto I = MemIndex::build( 184 generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}), RefSlab()); 185 FuzzyFindRequest Req; 186 Req.Query = "y"; 187 Req.Scopes = {"a::"}; 188 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2")); 189 } 190 191 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) { 192 auto I = MemIndex::build( 193 generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}), RefSlab()); 194 FuzzyFindRequest Req; 195 Req.Query = "y"; 196 Req.Scopes = {"a::", "b::"}; 197 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3")); 198 } 199 200 TEST(MemIndexTest, NoMatchNestedScopes) { 201 auto I = MemIndex::build(generateSymbols({"a::y1", "a::b::y2"}), RefSlab()); 202 FuzzyFindRequest Req; 203 Req.Query = "y"; 204 Req.Scopes = {"a::"}; 205 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1")); 206 } 207 208 TEST(MemIndexTest, IgnoreCases) { 209 auto I = MemIndex::build(generateSymbols({"ns::ABC", "ns::abc"}), RefSlab()); 210 FuzzyFindRequest Req; 211 Req.Query = "AB"; 212 Req.Scopes = {"ns::"}; 213 EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc")); 214 } 215 216 TEST(MemIndexTest, Lookup) { 217 auto I = MemIndex::build(generateSymbols({"ns::abc", "ns::xyz"}), RefSlab()); 218 EXPECT_THAT(lookup(*I, SymbolID("ns::abc")), UnorderedElementsAre("ns::abc")); 219 EXPECT_THAT(lookup(*I, {SymbolID("ns::abc"), SymbolID("ns::xyz")}), 220 UnorderedElementsAre("ns::abc", "ns::xyz")); 221 EXPECT_THAT(lookup(*I, {SymbolID("ns::nonono"), SymbolID("ns::xyz")}), 222 UnorderedElementsAre("ns::xyz")); 223 EXPECT_THAT(lookup(*I, SymbolID("ns::nonono")), UnorderedElementsAre()); 224 } 225 226 TEST(MemIndexTest, TemplateSpecialization) { 227 SymbolSlab::Builder B; 228 229 Symbol S = symbol("TempSpec"); 230 S.ID = SymbolID("1"); 231 B.insert(S); 232 233 S = symbol("TempSpec"); 234 S.ID = SymbolID("2"); 235 S.TemplateSpecializationArgs = "<int, bool>"; 236 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>( 237 index::SymbolProperty::TemplateSpecialization); 238 B.insert(S); 239 240 S = symbol("TempSpec"); 241 S.ID = SymbolID("3"); 242 S.TemplateSpecializationArgs = "<int, U>"; 243 S.SymInfo.Properties = static_cast<index::SymbolPropertySet>( 244 index::SymbolProperty::TemplatePartialSpecialization); 245 B.insert(S); 246 247 auto I = MemIndex::build(std::move(B).build(), RefSlab()); 248 FuzzyFindRequest Req; 249 Req.AnyScope = true; 250 251 Req.Query = "TempSpec"; 252 EXPECT_THAT(match(*I, Req), 253 UnorderedElementsAre("TempSpec", "TempSpec<int, bool>", 254 "TempSpec<int, U>")); 255 256 // FIXME: Add filtering for template argument list. 257 Req.Query = "TempSpec<int"; 258 EXPECT_THAT(match(*I, Req), IsEmpty()); 259 } 260 261 TEST(MergeIndexTest, Lookup) { 262 auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()), 263 J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab()); 264 MergedIndex M(I.get(), J.get()); 265 EXPECT_THAT(lookup(M, SymbolID("ns::A")), UnorderedElementsAre("ns::A")); 266 EXPECT_THAT(lookup(M, SymbolID("ns::B")), UnorderedElementsAre("ns::B")); 267 EXPECT_THAT(lookup(M, SymbolID("ns::C")), UnorderedElementsAre("ns::C")); 268 EXPECT_THAT(lookup(M, {SymbolID("ns::A"), SymbolID("ns::B")}), 269 UnorderedElementsAre("ns::A", "ns::B")); 270 EXPECT_THAT(lookup(M, {SymbolID("ns::A"), SymbolID("ns::C")}), 271 UnorderedElementsAre("ns::A", "ns::C")); 272 EXPECT_THAT(lookup(M, SymbolID("ns::D")), UnorderedElementsAre()); 273 EXPECT_THAT(lookup(M, {}), UnorderedElementsAre()); 274 } 275 276 TEST(MergeIndexTest, FuzzyFind) { 277 auto I = MemIndex::build(generateSymbols({"ns::A", "ns::B"}), RefSlab()), 278 J = MemIndex::build(generateSymbols({"ns::B", "ns::C"}), RefSlab()); 279 FuzzyFindRequest Req; 280 Req.Scopes = {"ns::"}; 281 EXPECT_THAT(match(MergedIndex(I.get(), J.get()), Req), 282 UnorderedElementsAre("ns::A", "ns::B", "ns::C")); 283 } 284 285 TEST(MergeTest, Merge) { 286 Symbol L, R; 287 L.ID = R.ID = SymbolID("hello"); 288 L.Name = R.Name = "Foo"; // same in both 289 L.CanonicalDeclaration.FileURI = "file:///left.h"; // differs 290 R.CanonicalDeclaration.FileURI = "file:///right.h"; 291 L.References = 1; 292 R.References = 2; 293 L.Signature = "()"; // present in left only 294 R.CompletionSnippetSuffix = "{$1:0}"; // present in right only 295 R.Documentation = "--doc--"; 296 L.Origin = SymbolOrigin::Dynamic; 297 R.Origin = SymbolOrigin::Static; 298 R.Type = "expectedType"; 299 300 Symbol M = mergeSymbol(L, R); 301 EXPECT_EQ(M.Name, "Foo"); 302 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:///left.h"); 303 EXPECT_EQ(M.References, 3u); 304 EXPECT_EQ(M.Signature, "()"); 305 EXPECT_EQ(M.CompletionSnippetSuffix, "{$1:0}"); 306 EXPECT_EQ(M.Documentation, "--doc--"); 307 EXPECT_EQ(M.Type, "expectedType"); 308 EXPECT_EQ(M.Origin, 309 SymbolOrigin::Dynamic | SymbolOrigin::Static | SymbolOrigin::Merge); 310 } 311 312 TEST(MergeTest, PreferSymbolWithDefn) { 313 Symbol L, R; 314 315 L.ID = R.ID = SymbolID("hello"); 316 L.CanonicalDeclaration.FileURI = "file:/left.h"; 317 R.CanonicalDeclaration.FileURI = "file:/right.h"; 318 L.Name = "left"; 319 R.Name = "right"; 320 321 Symbol M = mergeSymbol(L, R); 322 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/left.h"); 323 EXPECT_EQ(StringRef(M.Definition.FileURI), ""); 324 EXPECT_EQ(M.Name, "left"); 325 326 R.Definition.FileURI = "file:/right.cpp"; // Now right will be favored. 327 M = mergeSymbol(L, R); 328 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/right.h"); 329 EXPECT_EQ(StringRef(M.Definition.FileURI), "file:/right.cpp"); 330 EXPECT_EQ(M.Name, "right"); 331 } 332 333 TEST(MergeTest, PreferSymbolLocationInCodegenFile) { 334 Symbol L, R; 335 336 L.ID = R.ID = SymbolID("hello"); 337 L.CanonicalDeclaration.FileURI = "file:/x.proto.h"; 338 R.CanonicalDeclaration.FileURI = "file:/x.proto"; 339 340 Symbol M = mergeSymbol(L, R); 341 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/x.proto"); 342 343 // Prefer L if both have codegen suffix. 344 L.CanonicalDeclaration.FileURI = "file:/y.proto"; 345 M = mergeSymbol(L, R); 346 EXPECT_EQ(StringRef(M.CanonicalDeclaration.FileURI), "file:/y.proto"); 347 } 348 349 TEST(MergeIndexTest, Refs) { 350 FileIndex Dyn; 351 FileIndex StaticIndex; 352 MergedIndex Merge(&Dyn, &StaticIndex); 353 354 const char *HeaderCode = "class Foo;"; 355 auto HeaderSymbols = TestTU::withHeaderCode("class Foo;").headerSymbols(); 356 auto Foo = findSymbol(HeaderSymbols, "Foo"); 357 358 // Build dynamic index for test.cc. 359 Annotations Test1Code(R"(class $Foo[[Foo]];)"); 360 TestTU Test; 361 Test.HeaderCode = HeaderCode; 362 Test.Code = Test1Code.code(); 363 Test.Filename = "test.cc"; 364 auto AST = Test.build(); 365 Dyn.updateMain(Test.Filename, AST); 366 367 // Build static index for test.cc. 368 Test.HeaderCode = HeaderCode; 369 Test.Code = "// static\nclass Foo {};"; 370 Test.Filename = "test.cc"; 371 auto StaticAST = Test.build(); 372 // Add stale refs for test.cc. 373 StaticIndex.updateMain(Test.Filename, StaticAST); 374 375 // Add refs for test2.cc 376 Annotations Test2Code(R"(class $Foo[[Foo]] {};)"); 377 TestTU Test2; 378 Test2.HeaderCode = HeaderCode; 379 Test2.Code = Test2Code.code(); 380 Test2.Filename = "test2.cc"; 381 StaticAST = Test2.build(); 382 StaticIndex.updateMain(Test2.Filename, StaticAST); 383 384 RefsRequest Request; 385 Request.IDs = {Foo.ID}; 386 RefSlab::Builder Results; 387 Merge.refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); }); 388 EXPECT_THAT( 389 std::move(Results).build(), 390 ElementsAre(Pair( 391 _, UnorderedElementsAre(AllOf(RefRange(Test1Code.range("Foo")), 392 FileURI("unittest:///test.cc")), 393 AllOf(RefRange(Test2Code.range("Foo")), 394 FileURI("unittest:///test2.cc")))))); 395 396 Request.Limit = 1; 397 RefSlab::Builder Results2; 398 Merge.refs(Request, [&](const Ref &O) { Results2.insert(Foo.ID, O); }); 399 EXPECT_THAT(std::move(Results2).build(), 400 ElementsAre(Pair( 401 _, ElementsAre(AnyOf(FileURI("unittest:///test.cc"), 402 FileURI("unittest:///test2.cc")))))); 403 } 404 405 MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References, "") { 406 return (arg.IncludeHeader == IncludeHeader) && (arg.References == References); 407 } 408 409 TEST(MergeTest, MergeIncludesOnDifferentDefinitions) { 410 Symbol L, R; 411 L.Name = "left"; 412 R.Name = "right"; 413 L.ID = R.ID = SymbolID("hello"); 414 L.IncludeHeaders.emplace_back("common", 1); 415 R.IncludeHeaders.emplace_back("common", 1); 416 R.IncludeHeaders.emplace_back("new", 1); 417 418 // Both have no definition. 419 Symbol M = mergeSymbol(L, R); 420 EXPECT_THAT(M.IncludeHeaders, 421 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u), 422 IncludeHeaderWithRef("new", 1u))); 423 424 // Only merge references of the same includes but do not merge new #includes. 425 L.Definition.FileURI = "file:/left.h"; 426 M = mergeSymbol(L, R); 427 EXPECT_THAT(M.IncludeHeaders, 428 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u))); 429 430 // Definitions are the same. 431 R.Definition.FileURI = "file:/right.h"; 432 M = mergeSymbol(L, R); 433 EXPECT_THAT(M.IncludeHeaders, 434 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u), 435 IncludeHeaderWithRef("new", 1u))); 436 437 // Definitions are different. 438 R.Definition.FileURI = "file:/right.h"; 439 M = mergeSymbol(L, R); 440 EXPECT_THAT(M.IncludeHeaders, 441 UnorderedElementsAre(IncludeHeaderWithRef("common", 2u), 442 IncludeHeaderWithRef("new", 1u))); 443 } 444 445 } // namespace 446 } // namespace clangd 447 } // namespace clang 448