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