clang-tools-extra/clangd/unittests/SelectionTests.cpp

   1 //===-- SelectionTests.cpp - ----------------------------------------------===//
   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 #include "Annotations.h"
   9 #include "Selection.h"
  10 #include "SourceCode.h"
  11 #include "TestTU.h"
  12 #include "support/TestTracer.h"
  13 #include "clang/AST/ASTConcept.h"
  14 #include "clang/AST/Decl.h"
  15 #include "llvm/Support/Casting.h"
  16 #include "gmock/gmock.h"
  17 #include "gtest/gtest.h"
  18
  19 namespace clang {
  20 namespace clangd {
  21 namespace {
  22 using ::testing::ElementsAreArray;
  23 using ::testing::UnorderedElementsAreArray;
  24
  25 // Create a selection tree corresponding to a point or pair of points.
  26 // This uses the precisely-defined createRight semantics. The fuzzier
  27 // createEach is tested separately.
  28 SelectionTree makeSelectionTree(const StringRef MarkedCode, ParsedAST &AST) {
  29   Annotations Test(MarkedCode);
  30   switch (Test.points().size()) {
  31   case 1: { // Point selection.
  32     unsigned Offset = cantFail(positionToOffset(Test.code(), Test.point()));
  33     return SelectionTree::createRight(AST.getASTContext(), AST.getTokens(),
  34                                       Offset, Offset);
  35   }
  36   case 2: // Range selection.
  37     return SelectionTree::createRight(
  38         AST.getASTContext(), AST.getTokens(),
  39         cantFail(positionToOffset(Test.code(), Test.points()[0])),
  40         cantFail(positionToOffset(Test.code(), Test.points()[1])));
  41   default:
  42     ADD_FAILURE() << "Expected 1-2 points for selection.\n" << MarkedCode;
  43     return SelectionTree::createRight(AST.getASTContext(), AST.getTokens(), 0u,
  44                                       0u);
  45   }
  46 }
  47
  48 Range nodeRange(const SelectionTree::Node *N, ParsedAST &AST) {
  49   if (!N)
  50     return Range{};
  51   const SourceManager &SM = AST.getSourceManager();
  52   const LangOptions &LangOpts = AST.getLangOpts();
  53   StringRef Buffer = SM.getBufferData(SM.getMainFileID());
  54   if (llvm::isa_and_nonnull<TranslationUnitDecl>(N->ASTNode.get<Decl>()))
  55     return Range{Position{}, offsetToPosition(Buffer, Buffer.size())};
  56   auto FileRange =
  57       toHalfOpenFileRange(SM, LangOpts, N->ASTNode.getSourceRange());
  58   assert(FileRange && "We should be able to get the File Range");
  59   return Range{
  60       offsetToPosition(Buffer, SM.getFileOffset(FileRange->getBegin())),
  61       offsetToPosition(Buffer, SM.getFileOffset(FileRange->getEnd()))};
  62 }
  63
  64 std::string nodeKind(const SelectionTree::Node *N) {
  65   return N ? N->kind() : "<null>";
  66 }
  67
  68 std::vector<const SelectionTree::Node *> allNodes(const SelectionTree &T) {
  69   std::vector<const SelectionTree::Node *> Result = {&T.root()};
  70   for (unsigned I = 0; I < Result.size(); ++I) {
  71     const SelectionTree::Node *N = Result[I];
  72     Result.insert(Result.end(), N->Children.begin(), N->Children.end());
  73   }
  74   return Result;
  75 }
  76
  77 // Returns true if Common is a descendent of Root.
  78 // Verifies nothing is selected above Common.
  79 bool verifyCommonAncestor(const SelectionTree::Node &Root,
  80                           const SelectionTree::Node *Common,
  81                           StringRef MarkedCode) {
  82   if (&Root == Common)
  83     return true;
  84   if (Root.Selected)
  85     ADD_FAILURE() << "Selected nodes outside common ancestor\n" << MarkedCode;
  86   bool Seen = false;
  87   for (const SelectionTree::Node *Child : Root.Children)
  88     if (verifyCommonAncestor(*Child, Common, MarkedCode)) {
  89       if (Seen)
  90         ADD_FAILURE() << "Saw common ancestor twice\n" << MarkedCode;
  91       Seen = true;
  92     }
  93   return Seen;
  94 }
  95
  96 TEST(SelectionTest, CommonAncestor) {
  97   struct Case {
  98     // Selection is between ^marks^.
  99     // common ancestor marked with a [[range]].
 100     const char *Code;
 101     const char *CommonAncestorKind;
 102   };
 103   Case Cases[] = {
 104       {
 105           R"cpp(
 106             template <typename T>
 107             int x = [[T::^U::]]ccc();
 108           )cpp",
 109           "NestedNameSpecifierLoc",
 110       },
 111       {
 112           R"cpp(
 113             struct AAA { struct BBB { static int ccc(); };};
 114             int x = AAA::[[B^B^B]]::ccc();
 115           )cpp",
 116           "RecordTypeLoc",
 117       },
 118       {
 119           R"cpp(
 120             struct AAA { struct BBB { static int ccc(); };};
 121             int x = AAA::[[B^BB^]]::ccc();
 122           )cpp",
 123           "RecordTypeLoc",
 124       },
 125       {
 126           R"cpp(
 127             struct AAA { struct BBB { static int ccc(); };};
 128             int x = [[AAA::BBB::c^c^c]]();
 129           )cpp",
 130           "DeclRefExpr",
 131       },
 132       {
 133           R"cpp(
 134             struct AAA { struct BBB { static int ccc(); };};
 135             int x = [[AAA::BBB::cc^c(^)]];
 136           )cpp",
 137           "CallExpr",
 138       },
 139
 140       {
 141           R"cpp(
 142             void foo() { [[if (1^11) { return; } else {^ }]] }
 143           )cpp",
 144           "IfStmt",
 145       },
 146       {
 147           R"cpp(
 148             int x(int);
 149             #define M(foo) x(foo)
 150             int a = 42;
 151             int b = M([[^a]]);
 152           )cpp",
 153           "DeclRefExpr",
 154       },
 155       {
 156           R"cpp(
 157             void foo();
 158             #define CALL_FUNCTION(X) X()
 159             void bar() { CALL_FUNCTION([[f^o^o]]); }
 160           )cpp",
 161           "DeclRefExpr",
 162       },
 163       {
 164           R"cpp(
 165             void foo();
 166             #define CALL_FUNCTION(X) X()
 167             void bar() { [[CALL_FUNC^TION(fo^o)]]; }
 168           )cpp",
 169           "CallExpr",
 170       },
 171       {
 172           R"cpp(
 173             void foo();
 174             #define CALL_FUNCTION(X) X()
 175             void bar() { [[C^ALL_FUNC^TION(foo)]]; }
 176           )cpp",
 177           "CallExpr",
 178       },
 179       {
 180           R"cpp(
 181             void foo();
 182             #^define CALL_FUNCTION(X) X(^)
 183             void bar() { CALL_FUNCTION(foo); }
 184           )cpp",
 185           nullptr,
 186       },
 187       {
 188           R"cpp(
 189             void foo();
 190             #define CALL_FUNCTION(X) X()
 191             void bar() { CALL_FUNCTION(foo^)^; }
 192           )cpp",
 193           nullptr,
 194       },
 195       {
 196           R"cpp(
 197             namespace ns {
 198             #if 0
 199             void fo^o() {}
 200             #endif
 201             }
 202           )cpp",
 203           nullptr,
 204       },
 205       {
 206           R"cpp(
 207             #define TARGET void foo()
 208             [[TAR^GET{ return; }]]
 209           )cpp",
 210           "FunctionDecl",
 211       },
 212       {
 213           R"cpp(
 214             struct S { S(const char*); };
 215             [[S s ^= "foo"]];
 216           )cpp",
 217           // The AST says a CXXConstructExpr covers the = sign in C++14.
 218           // But we consider CXXConstructExpr to only own brackets.
 219           // (It's not the interesting constructor anyway, just S(&&)).
 220           "VarDecl",
 221       },
 222       {
 223           R"cpp(
 224             struct S { S(const char*); };
 225             [[S ^s = "foo"]];
 226           )cpp",
 227           "VarDecl",
 228       },
 229       {
 230           R"cpp(
 231             [[^void]] (*S)(int) = nullptr;
 232           )cpp",
 233           "BuiltinTypeLoc",
 234       },
 235       {
 236           R"cpp(
 237             [[void (*S)^(int)]] = nullptr;
 238           )cpp",
 239           "FunctionProtoTypeLoc",
 240       },
 241       {
 242           R"cpp(
 243             [[void (^*S)(int)]] = nullptr;
 244           )cpp",
 245           "PointerTypeLoc",
 246       },
 247       {
 248           R"cpp(
 249             [[void (*^S)(int) = nullptr]];
 250           )cpp",
 251           "VarDecl",
 252       },
 253       {
 254           R"cpp(
 255             [[void ^(*S)(int)]] = nullptr;
 256           )cpp",
 257           "ParenTypeLoc",
 258       },
 259       {
 260           R"cpp(
 261             struct S {
 262               int foo() const;
 263               int bar() { return [[f^oo]](); }
 264             };
 265           )cpp",
 266           "MemberExpr", // Not implicit CXXThisExpr, or its implicit cast!
 267       },
 268       {
 269           R"cpp(
 270             auto lambda = [](const char*){ return 0; };
 271             int x = lambda([["y^"]]);
 272           )cpp",
 273           "StringLiteral", // Not DeclRefExpr to operator()!
 274       },
 275       {
 276           R"cpp(
 277             struct Foo {};
 278             struct Bar : [[v^ir^tual private Foo]] {};
 279           )cpp",
 280           "CXXBaseSpecifier",
 281       },
 282       {
 283           R"cpp(
 284             struct Foo {};
 285             struct Bar : private [[Fo^o]] {};
 286           )cpp",
 287           "RecordTypeLoc",
 288       },
 289       {
 290           R"cpp(
 291             struct Foo {};
 292             struct Bar : [[Fo^o]] {};
 293           )cpp",
 294           "RecordTypeLoc",
 295       },
 296
 297       // Point selections.
 298       {"void foo() { [[^foo]](); }", "DeclRefExpr"},
 299       {"void foo() { [[f^oo]](); }", "DeclRefExpr"},
 300       {"void foo() { [[fo^o]](); }", "DeclRefExpr"},
 301       {"void foo() { [[foo^()]]; }", "CallExpr"},
 302       {"void foo() { [[foo^]] (); }", "DeclRefExpr"},
 303       {"int bar; void foo() [[{ foo (); }]]^", "CompoundStmt"},
 304       {"int x = [[42]]^;", "IntegerLiteral"},
 305
 306       // Ignores whitespace, comments, and semicolons in the selection.
 307       {"void foo() { [[foo^()]]; /*comment*/^}", "CallExpr"},
 308
 309       // Tricky case: FunctionTypeLoc in FunctionDecl has a hole in it.
 310       {"[[^void]] foo();", "BuiltinTypeLoc"},
 311       {"[[void foo^()]];", "FunctionProtoTypeLoc"},
 312       {"[[^void foo^()]];", "FunctionDecl"},
 313       {"[[void ^foo()]];", "FunctionDecl"},
 314       // Tricky case: two VarDecls share a specifier.
 315       {"[[int ^a]], b;", "VarDecl"},
 316       {"[[int a, ^b]];", "VarDecl"},
 317       // Tricky case: CXXConstructExpr wants to claim the whole init range.
 318       {
 319           R"cpp(
 320             struct X { X(int); };
 321             class Y {
 322               X x;
 323               Y() : [[^x(4)]] {}
 324             };
 325           )cpp",
 326           "CXXCtorInitializer", // Not the CXXConstructExpr!
 327       },
 328       // Tricky case: anonymous struct is a sibling of the VarDecl.
 329       {"[[st^ruct {int x;}]] y;", "CXXRecordDecl"},
 330       {"[[struct {int x;} ^y]];", "VarDecl"},
 331       {"struct {[[int ^x]];} y;", "FieldDecl"},
 332
 333       // Tricky case: nested ArrayTypeLocs have the same token range.
 334       {"const int x = 1, y = 2; int array[^[[x]]][10][y];", "DeclRefExpr"},
 335       {"const int x = 1, y = 2; int array[x][10][^[[y]]];", "DeclRefExpr"},
 336       {"const int x = 1, y = 2; int array[x][^[[10]]][y];", "IntegerLiteral"},
 337       {"const int x = 1, y = 2; [[i^nt]] array[x][10][y];", "BuiltinTypeLoc"},
 338       {"void func(int x) { int v_array[^[[x]]][10]; }", "DeclRefExpr"},
 339
 340       {"int (*getFunc([[do^uble]]))(int);", "BuiltinTypeLoc"},
 341
 342       // Member pointers and pack expansion use declarator syntax, but are
 343       // restricted so they don't need special casing.
 344       {"class X{}; [[int X::^*]]y[10];", "MemberPointerTypeLoc"},
 345       {"template<typename ...T> void foo([[T*^...]]x);",
 346        "PackExpansionTypeLoc"},
 347       {"template<typename ...T> void foo([[^T]]*...x);",
 348        "TemplateTypeParmTypeLoc"},
 349
 350       // FIXME: the AST has no location info for qualifiers.
 351       {"const [[a^uto]] x = 42;", "AutoTypeLoc"},
 352       {"co^nst auto x = 42;", nullptr},
 353
 354       {"^", nullptr},
 355       {"void foo() { [[foo^^]] (); }", "DeclRefExpr"},
 356
 357       // FIXME: Ideally we'd get a declstmt or the VarDecl itself here.
 358       // This doesn't happen now; the RAV doesn't traverse a node containing ;.
 359       {"int x = 42;^", nullptr},
 360
 361       // Common ancestor is logically TUDecl, but we never return that.
 362       {"^int x; int y;^", nullptr},
 363
 364       // Node types that have caused problems in the past.
 365       {"template <typename T> void foo() { [[^T]] t; }",
 366        "TemplateTypeParmTypeLoc"},
 367
 368       // No crash
 369       {
 370           R"cpp(
 371             template <class T> struct Foo {};
 372             template <[[template<class> class /*cursor here*/^U]]>
 373              struct Foo<U<int>*> {};
 374           )cpp",
 375           "TemplateTemplateParmDecl"},
 376
 377       // Foreach has a weird AST, ensure we can select parts of the range init.
 378       // This used to fail, because the DeclStmt for C claimed the whole range.
 379       {
 380           R"cpp(
 381             struct Str {
 382               const char *begin();
 383               const char *end();
 384             };
 385             Str makeStr(const char*);
 386             void loop() {
 387               for (const char C : [[mak^eStr("foo"^)]])
 388                 ;
 389             }
 390           )cpp",
 391           "CallExpr"},
 392
 393       // User-defined literals are tricky: is 12_i one token or two?
 394       // For now we treat it as one, and the UserDefinedLiteral as a leaf.
 395       {
 396           R"cpp(
 397             struct Foo{};
 398             Foo operator""_ud(unsigned long long);
 399             Foo x = [[^12_ud]];
 400           )cpp",
 401           "UserDefinedLiteral"},
 402
 403       {
 404           R"cpp(
 405         int a;
 406         decltype([[^a]] + a) b;
 407         )cpp",
 408           "DeclRefExpr"},
 409       {"[[decltype^(1)]] b;", "DecltypeTypeLoc"}, // Not the VarDecl.
 410       // decltype(auto) is an AutoTypeLoc!
 411       {"[[de^cltype(a^uto)]] a = 1;", "AutoTypeLoc"},
 412
 413       // Objective-C nullability attributes.
 414       {
 415           R"cpp(
 416             @interface I{}
 417             @property(nullable) [[^I]] *x;
 418             @end
 419           )cpp",
 420           "ObjCInterfaceTypeLoc"},
 421       {
 422           R"cpp(
 423             @interface I{}
 424             - (void)doSomething:(nonnull [[i^d]])argument;
 425             @end
 426           )cpp",
 427           "TypedefTypeLoc"},
 428
 429       // Objective-C OpaqueValueExpr/PseudoObjectExpr has weird ASTs.
 430       // Need to traverse the contents of the OpaqueValueExpr to the POE,
 431       // and ensure we traverse only the syntactic form of the PseudoObjectExpr.
 432       {
 433           R"cpp(
 434             @interface I{}
 435             @property(retain) I*x;
 436             @property(retain) I*y;
 437             @end
 438             void test(I *f) { [[^f]].x.y = 0; }
 439           )cpp",
 440           "DeclRefExpr"},
 441       {
 442           R"cpp(
 443             @interface I{}
 444             @property(retain) I*x;
 445             @property(retain) I*y;
 446             @end
 447             void test(I *f) { [[f.^x]].y = 0; }
 448           )cpp",
 449           "ObjCPropertyRefExpr"},
 450       // Examples with implicit properties.
 451       {
 452           R"cpp(
 453             @interface I{}
 454             -(int)foo;
 455             @end
 456             int test(I *f) { return 42 + [[^f]].foo; }
 457           )cpp",
 458           "DeclRefExpr"},
 459       {
 460           R"cpp(
 461             @interface I{}
 462             -(int)foo;
 463             @end
 464             int test(I *f) { return 42 + [[f.^foo]]; }
 465           )cpp",
 466           "ObjCPropertyRefExpr"},
 467       {"struct foo { [[int has^h<:32:>]]; };", "FieldDecl"},
 468       {"struct foo { [[op^erator int()]]; };", "CXXConversionDecl"},
 469       {"struct foo { [[^~foo()]]; };", "CXXDestructorDecl"},
 470       {"struct foo { [[~^foo()]]; };", "CXXDestructorDecl"},
 471       {"template <class T> struct foo { ~foo<[[^T]]>(){} };",
 472        "TemplateTypeParmTypeLoc"},
 473       {"struct foo {}; void bar(foo *f) { [[f->~^foo]](); }", "MemberExpr"},
 474       {"struct foo { [[fo^o(){}]] };", "CXXConstructorDecl"},
 475
 476       {R"cpp(
 477         struct S1 { void f(); };
 478         struct S2 { S1 * operator->(); };
 479         void test(S2 s2) {
 480           s2[[-^>]]f();
 481         }
 482       )cpp",
 483        "DeclRefExpr"}, // DeclRefExpr to the "operator->" method.
 484
 485       // Template template argument.
 486       {R"cpp(
 487         template <typename> class Vector {};
 488         template <template <typename> class Container> class A {};
 489         A<[[V^ector]]> a;
 490       )cpp",
 491        "TemplateArgumentLoc"},
 492
 493       // Attributes
 494       {R"cpp(
 495         void f(int * __attribute__(([[no^nnull]])) );
 496       )cpp",
 497        "NonNullAttr"},
 498
 499       {R"cpp(
 500         // Digraph syntax for attributes to avoid accidental annotations.
 501         class <:[gsl::Owner([[in^t]])]:> X{};
 502       )cpp",
 503        "BuiltinTypeLoc"},
 504
 505       // This case used to crash - AST has a null Attr
 506       {R"cpp(
 507         @interface I
 508         [[@property(retain, nonnull) <:[My^Object2]:> *x]]; // error-ok
 509         @end
 510       )cpp",
 511        "ObjCPropertyDecl"},
 512
 513       {R"cpp(
 514         typedef int Foo;
 515         enum Bar : [[Fo^o]] {};
 516       )cpp",
 517        "TypedefTypeLoc"},
 518       {R"cpp(
 519         typedef int Foo;
 520         enum Bar : [[Fo^o]];
 521       )cpp",
 522        "TypedefTypeLoc"},
 523
 524       // lambda captured var-decl
 525       {R"cpp(
 526         void test(int bar) {
 527           auto l = [^[[foo = bar]]] { };
 528         })cpp",
 529        "VarDecl"},
 530       {R"cpp(
 531         /*error-ok*/
 532         void func() [[{^]])cpp",
 533        "CompoundStmt"},
 534       {R"cpp(
 535         void func() { [[__^func__]]; }
 536         )cpp",
 537        "PredefinedExpr"},
 538
 539       // using enum
 540       {R"cpp(
 541         namespace ns { enum class A {}; };
 542         using enum ns::[[^A]];
 543         )cpp",
 544        "EnumTypeLoc"},
 545       {R"cpp(
 546         namespace ns { enum class A {}; using B = A; };
 547         using enum ns::[[^B]];
 548         )cpp",
 549        "TypedefTypeLoc"},
 550       {R"cpp(
 551         namespace ns { enum class A {}; };
 552         using enum [[^ns::]]A;
 553         )cpp",
 554        "NestedNameSpecifierLoc"},
 555       {R"cpp(
 556         namespace ns { enum class A {}; };
 557         [[using ^enum ns::A]];
 558         )cpp",
 559        "UsingEnumDecl"},
 560       {R"cpp(
 561         namespace ns { enum class A {}; };
 562         [[^using enum ns::A]];
 563         )cpp",
 564        "UsingEnumDecl"},
 565
 566       // concepts
 567       {R"cpp(
 568         template <class> concept C = true;
 569         auto x = [[^C<int>]];
 570       )cpp",
 571        "ConceptReference"},
 572       {R"cpp(
 573         template <class> concept C = true;
 574         [[^C]] auto x = 0;
 575       )cpp",
 576        "ConceptReference"},
 577       {R"cpp(
 578         template <class> concept C = true;
 579         void foo([[^C]] auto x) {}
 580       )cpp",
 581        "ConceptReference"},
 582       {R"cpp(
 583         template <class> concept C = true;
 584         template <[[^C]] x> int i = 0;
 585       )cpp",
 586        "ConceptReference"},
 587       {R"cpp(
 588         namespace ns { template <class> concept C = true; }
 589         auto x = [[ns::^C<int>]];
 590       )cpp",
 591        "ConceptReference"},
 592       {R"cpp(
 593         template <typename T, typename K>
 594         concept D = true;
 595         template <typename T> void g(D<[[^T]]> auto abc) {}
 596       )cpp",
 597        "TemplateTypeParmTypeLoc"},
 598   };
 599
 600   for (const Case &C : Cases) {
 601     trace::TestTracer Tracer;
 602     Annotations Test(C.Code);
 603
 604     TestTU TU;
 605     TU.Code = std::string(Test.code());
 606
 607     TU.ExtraArgs.push_back("-xobjective-c++");
 608     TU.ExtraArgs.push_back("-std=c++20");
 609
 610     auto AST = TU.build();
 611     auto T = makeSelectionTree(C.Code, AST);
 612     EXPECT_EQ("TranslationUnitDecl", nodeKind(&T.root())) << C.Code;
 613
 614     if (Test.ranges().empty()) {
 615       // If no [[range]] is marked in the example, there should be no selection.
 616       EXPECT_FALSE(T.commonAncestor()) << C.Code << "\n" << T;
 617       EXPECT_THAT(Tracer.takeMetric("selection_recovery", "C++"),
 618                   testing::IsEmpty());
 619     } else {
 620       // If there is an expected selection, common ancestor should exist
 621       // with the appropriate node type.
 622       EXPECT_EQ(C.CommonAncestorKind, nodeKind(T.commonAncestor()))
 623           << C.Code << "\n"
 624           << T;
 625       // Convert the reported common ancestor to a range and verify it.
 626       EXPECT_EQ(nodeRange(T.commonAncestor(), AST), Test.range())
 627           << C.Code << "\n"
 628           << T;
 629
 630       // Check that common ancestor is reachable on exactly one path from root,
 631       // and no nodes outside it are selected.
 632       EXPECT_TRUE(verifyCommonAncestor(T.root(), T.commonAncestor(), C.Code))
 633           << C.Code;
 634       EXPECT_THAT(Tracer.takeMetric("selection_recovery", "C++"),
 635                   ElementsAreArray({0}));
 636     }
 637   }
 638 }
 639
 640 // Regression test: this used to match the injected X, not the outer X.
 641 TEST(SelectionTest, InjectedClassName) {
 642   const char *Code = "struct ^X { int x; };";
 643   auto AST = TestTU::withCode(Annotations(Code).code()).build();
 644   auto T = makeSelectionTree(Code, AST);
 645   ASSERT_EQ("CXXRecordDecl", nodeKind(T.commonAncestor())) << T;
 646   auto *D = dyn_cast<CXXRecordDecl>(T.commonAncestor()->ASTNode.get<Decl>());
 647   EXPECT_FALSE(D->isInjectedClassName());
 648 }
 649
 650 TEST(SelectionTree, Metrics) {
 651   const char *Code = R"cpp(
 652     // error-ok: testing behavior on recovery expression
 653     int foo();
 654     int foo(int, int);
 655     int x = fo^o(42);
 656   )cpp";
 657   auto AST = TestTU::withCode(Annotations(Code).code()).build();
 658   trace::TestTracer Tracer;
 659   auto T = makeSelectionTree(Code, AST);
 660   EXPECT_THAT(Tracer.takeMetric("selection_recovery", "C++"),
 661               ElementsAreArray({1}));
 662   EXPECT_THAT(Tracer.takeMetric("selection_recovery_type", "C++"),
 663               ElementsAreArray({1}));
 664 }
 665
 666 // FIXME: Doesn't select the binary operator node in
 667 //          #define FOO(X) X + 1
 668 //          int a, b = [[FOO(a)]];
 669 TEST(SelectionTest, Selected) {
 670   // Selection with ^marks^.
 671   // Partially selected nodes marked with a [[range]].
 672   // Completely selected nodes marked with a $C[[range]].
 673   const char *Cases[] = {
 674       R"cpp( int abc, xyz = [[^ab^c]]; )cpp",
 675       R"cpp( int abc, xyz = [[a^bc^]]; )cpp",
 676       R"cpp( int abc, xyz = $C[[^abc^]]; )cpp",
 677       R"cpp(
 678         void foo() {
 679           [[if ([[1^11]]) $C[[{
 680             $C[[return]];
 681           }]] else [[{^
 682           }]]]]
 683           char z;
 684         }
 685       )cpp",
 686       R"cpp(
 687           template <class T>
 688           struct unique_ptr {};
 689           void foo(^$C[[unique_ptr<$C[[unique_ptr<$C[[int]]>]]>]]^ a) {}
 690       )cpp",
 691       R"cpp(int a = [[5 >^> 1]];)cpp",
 692       R"cpp(
 693         #define ECHO(X) X
 694         ECHO(EC^HO($C[[int]]) EC^HO(a));
 695       )cpp",
 696       R"cpp( $C[[^$C[[int]] a^]]; )cpp",
 697       R"cpp( $C[[^$C[[int]] a = $C[[5]]^]]; )cpp",
 698   };
 699   for (const char *C : Cases) {
 700     Annotations Test(C);
 701     auto AST = TestTU::withCode(Test.code()).build();
 702     auto T = makeSelectionTree(C, AST);
 703
 704     std::vector<Range> Complete, Partial;
 705     for (const SelectionTree::Node *N : allNodes(T))
 706       if (N->Selected == SelectionTree::Complete)
 707         Complete.push_back(nodeRange(N, AST));
 708       else if (N->Selected == SelectionTree::Partial)
 709         Partial.push_back(nodeRange(N, AST));
 710     EXPECT_THAT(Complete, UnorderedElementsAreArray(Test.ranges("C"))) << C;
 711     EXPECT_THAT(Partial, UnorderedElementsAreArray(Test.ranges())) << C;
 712   }
 713 }
 714
 715 TEST(SelectionTest, PathologicalPreprocessor) {
 716   const char *Case = R"cpp(
 717 #define MACRO while(1)
 718     void test() {
 719 #include "Expand.inc"
 720         br^eak;
 721     }
 722   )cpp";
 723   Annotations Test(Case);
 724   auto TU = TestTU::withCode(Test.code());
 725   TU.AdditionalFiles["Expand.inc"] = "MACRO\n";
 726   auto AST = TU.build();
 727   EXPECT_THAT(AST.getDiagnostics(), ::testing::IsEmpty());
 728   auto T = makeSelectionTree(Case, AST);
 729
 730   EXPECT_EQ("BreakStmt", T.commonAncestor()->kind());
 731   EXPECT_EQ("WhileStmt", T.commonAncestor()->Parent->kind());
 732 }
 733
 734 TEST(SelectionTest, IncludedFile) {
 735   const char *Case = R"cpp(
 736     void test() {
 737 #include "Exp^and.inc"
 738         break;
 739     }
 740   )cpp";
 741   Annotations Test(Case);
 742   auto TU = TestTU::withCode(Test.code());
 743   TU.AdditionalFiles["Expand.inc"] = "while(1)\n";
 744   auto AST = TU.build();
 745   auto T = makeSelectionTree(Case, AST);
 746
 747   EXPECT_EQ(nullptr, T.commonAncestor());
 748 }
 749
 750 TEST(SelectionTest, MacroArgExpansion) {
 751   // If a macro arg is expanded several times, we only consider the first one
 752   // selected.
 753   const char *Case = R"cpp(
 754     int mul(int, int);
 755     #define SQUARE(X) mul(X, X);
 756     int nine = SQUARE(^3);
 757   )cpp";
 758   Annotations Test(Case);
 759   auto AST = TestTU::withCode(Test.code()).build();
 760   auto T = makeSelectionTree(Case, AST);
 761   EXPECT_EQ("IntegerLiteral", T.commonAncestor()->kind());
 762   EXPECT_TRUE(T.commonAncestor()->Selected);
 763
 764   // Verify that the common assert() macro doesn't suffer from this.
 765   // (This is because we don't associate the stringified token with the arg).
 766   Case = R"cpp(
 767     void die(const char*);
 768     #define assert(x) (x ? (void)0 : die(#x))
 769     void foo() { assert(^42); }
 770   )cpp";
 771   Test = Annotations(Case);
 772   AST = TestTU::withCode(Test.code()).build();
 773   T = makeSelectionTree(Case, AST);
 774   EXPECT_EQ("IntegerLiteral", T.commonAncestor()->kind());
 775
 776   // Reduced from private bug involving RETURN_IF_ERROR.
 777   // Due to >>-splitting and a bug in isBeforeInTranslationUnit, the inner
 778   // S<int> would claim way too many tokens.
 779   Case = R"cpp(
 780     #define ID(x) x
 781     template <typename T> class S {};
 782     ID(
 783       ID(S<S<int>> x);
 784       int ^y;
 785     )
 786   )cpp";
 787   Test = Annotations(Case);
 788   AST = TestTU::withCode(Test.code()).build();
 789   T = makeSelectionTree(Case, AST);
 790   // not TemplateSpecializationTypeLoc!
 791   EXPECT_EQ("VarDecl", T.commonAncestor()->kind());
 792 }
 793
 794 TEST(SelectionTest, Implicit) {
 795   const char *Test = R"cpp(
 796     struct S { S(const char*); };
 797     int f(S);
 798     int x = f("^");
 799   )cpp";
 800   auto TU = TestTU::withCode(Annotations(Test).code());
 801   // C++14 AST contains some temporaries that C++17 elides.
 802   TU.ExtraArgs.push_back("-std=c++17");
 803   auto AST = TU.build();
 804   auto T = makeSelectionTree(Test, AST);
 805
 806   const SelectionTree::Node *Str = T.commonAncestor();
 807   EXPECT_EQ("StringLiteral", nodeKind(Str)) << "Implicit selected?";
 808   EXPECT_EQ("ImplicitCastExpr", nodeKind(Str->Parent));
 809   EXPECT_EQ("CXXConstructExpr", nodeKind(Str->Parent->Parent));
 810   const SelectionTree::Node *ICE = Str->Parent->Parent->Parent;
 811   EXPECT_EQ("ImplicitCastExpr", nodeKind(ICE));
 812   EXPECT_EQ("CallExpr", nodeKind(ICE->Parent));
 813   EXPECT_EQ(Str, &ICE->ignoreImplicit())
 814       << "Didn't unwrap " << nodeKind(&ICE->ignoreImplicit());
 815
 816   EXPECT_EQ(ICE, &Str->outerImplicit());
 817 }
 818
 819 TEST(SelectionTest, CreateAll) {
 820   llvm::Annotations Test("int$unique^ a=1$ambiguous^+1; $empty^");
 821   auto AST = TestTU::withCode(Test.code()).build();
 822   unsigned Seen = 0;
 823   SelectionTree::createEach(
 824       AST.getASTContext(), AST.getTokens(), Test.point("ambiguous"),
 825       Test.point("ambiguous"), [&](SelectionTree T) {
 826         // Expect to see the right-biased tree first.
 827         if (Seen == 0) {
 828           EXPECT_EQ("BinaryOperator", nodeKind(T.commonAncestor()));
 829         } else if (Seen == 1) {
 830           EXPECT_EQ("IntegerLiteral", nodeKind(T.commonAncestor()));
 831         }
 832         ++Seen;
 833         return false;
 834       });
 835   EXPECT_EQ(2u, Seen);
 836
 837   Seen = 0;
 838   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
 839                             Test.point("ambiguous"), Test.point("ambiguous"),
 840                             [&](SelectionTree T) {
 841                               ++Seen;
 842                               return true;
 843                             });
 844   EXPECT_EQ(1u, Seen) << "Return true --> stop iterating";
 845
 846   Seen = 0;
 847   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
 848                             Test.point("unique"), Test.point("unique"),
 849                             [&](SelectionTree T) {
 850                               ++Seen;
 851                               return false;
 852                             });
 853   EXPECT_EQ(1u, Seen) << "no ambiguity --> only one tree";
 854
 855   Seen = 0;
 856   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
 857                             Test.point("empty"), Test.point("empty"),
 858                             [&](SelectionTree T) {
 859                               EXPECT_FALSE(T.commonAncestor());
 860                               ++Seen;
 861                               return false;
 862                             });
 863   EXPECT_EQ(1u, Seen) << "empty tree still created";
 864
 865   Seen = 0;
 866   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(),
 867                             Test.point("unique"), Test.point("ambiguous"),
 868                             [&](SelectionTree T) {
 869                               ++Seen;
 870                               return false;
 871                             });
 872   EXPECT_EQ(1u, Seen) << "one tree for nontrivial selection";
 873 }
 874
 875 TEST(SelectionTest, DeclContextIsLexical) {
 876   llvm::Annotations Test("namespace a { void $1^foo(); } void a::$2^foo();");
 877   auto AST = TestTU::withCode(Test.code()).build();
 878   {
 879     auto ST = SelectionTree::createRight(AST.getASTContext(), AST.getTokens(),
 880                                          Test.point("1"), Test.point("1"));
 881     EXPECT_FALSE(ST.commonAncestor()->getDeclContext().isTranslationUnit());
 882   }
 883   {
 884     auto ST = SelectionTree::createRight(AST.getASTContext(), AST.getTokens(),
 885                                          Test.point("2"), Test.point("2"));
 886     EXPECT_TRUE(ST.commonAncestor()->getDeclContext().isTranslationUnit());
 887   }
 888 }
 889
 890 TEST(SelectionTest, DeclContextLambda) {
 891   llvm::Annotations Test(R"cpp(
 892     void foo();
 893     auto lambda = [] {
 894       return $1^foo();
 895     };
 896   )cpp");
 897   auto AST = TestTU::withCode(Test.code()).build();
 898   auto ST = SelectionTree::createRight(AST.getASTContext(), AST.getTokens(),
 899                                        Test.point("1"), Test.point("1"));
 900   EXPECT_TRUE(ST.commonAncestor()->getDeclContext().isFunctionOrMethod());
 901 }
 902
 903 TEST(SelectionTest, UsingConcepts) {
 904   llvm::Annotations Test(R"cpp(
 905 namespace ns {
 906 template <typename T>
 907 concept Foo = true;
 908 }
 909
 910 using ns::Foo;
 911
 912 template <Fo^o... T, Fo^o auto U>
 913 auto Func(Fo^o auto V) -> Fo^o decltype(auto) {
 914   Fo^o auto W = V;
 915   return W;
 916 }
 917 )cpp");
 918   auto TU = TestTU::withCode(Test.code());
 919   TU.ExtraArgs.emplace_back("-std=c++2c");
 920   auto AST = TU.build();
 921   for (auto Point : Test.points()) {
 922     auto ST = SelectionTree::createRight(AST.getASTContext(), AST.getTokens(),
 923                                          Point, Point);
 924     auto *C = ST.commonAncestor()->ASTNode.get<ConceptReference>();
 925     EXPECT_TRUE(C && C->getFoundDecl() &&
 926                 C->getFoundDecl()->getKind() == Decl::UsingShadow);
 927   }
 928 }
 929
 930 } // namespace
 931 } // namespace clangd
 932 } // namespace clang