[clangd] Handle declarators more consistently in Selection.

[sammccall]

Summary

Because declarators nest inside-out, we logically need to claim tokens for
parent declarators logically before child ones.
This is the ultimate reason we had problems with DeclaratorDecl, ArrayType etc.

However actually changing the order of traversal is hard, especially for nodes
that have both declarator and non-declarator children.
Since there's only a few TypeLocs corresponding to declarators, we just
have them claim the exact tokens rather than rely on nesting.

This fixes handling of complex declarators, like
int (*Fun(OuterT^ype))(InnerType);.

This avoids the need for the DeclaratorDecl early-claim hack, which is
removed.
Unfortunately the DeclaratorDecl early-claims were covering up an AST
anomaly around CXXConstructExpr, so we need to fix that up too.

Based on D116623 and D116618

[hokein]

Thanks, this looks better!

clang-tools-extra/clangd/Selection.cpp

757

I'd prefer to keep this comment, while we have some high-level and abstract comment in the new patch, I think it is still useful to give us some details (otherwise, I'd probably forget everything when coming back to read the code a few months later).

I also want to add the example int (*Fun(OuterType))(InnerType); from D116618 here, I understand it might be too verbose (personally, I find it useful to understand this part of code), up to you.

777

nit: FTL.getLParenLoc().

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

209–212

Maybe a FIXME for "CXXConstructExpr is better", but I don't come up with a good fix.

[sammccall]

clang-tools-extra/clangd/Selection.cpp

757

Yeah, the example is useful.
My problem was that the examples were showing how each declarator type combined with itself, which was both confusing (as you have to describe which you're talking about) and didn't cover the general case.

I've added a new example, which uses multiple different types of declarators and also shows nontrivial non-declarator types for comparison.

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

209–212

I actually like the way we treat CXXConstructExpr, which is that it owns the brackets and nothing else.
And having VarDecl consistently own the = is nice too.

This is a divergence from the AST so I've left a comment, but I think it's actually good.

(As mentioned offline: the CXXConstructExpr in this case isn't actually the interesting constructor, it's the elidable move construction, so this doesn't really hurt go-to-definition etc)

clang-tools-extra/clangd/Selection.cpp

#endif
   // subtrees that don't touch the selection (canSafelySkipNode), but
   // fine-grained hit-testing is mostly done on the way back up (in pop()).
   // This means children get to claim parts of the selection first, and parents
   // are only selected if they own tokens that no child owned.
   //
   // Nodes *usually* nest nicely: a child's getSourceRange() lies within the
   // parent's, and a node (transitively) owns all tokens in its range.
   //
-  // Exception 1: child range claims tokens that should be owned by the parent.
-  //              e.g. in `void foo(int);`, the FunctionTypeLoc should own
-  //              `void (int)` but the parent FunctionDecl should own `foo`.
-  // To handle this case, certain nodes claim small token ranges *before*
-  // their children are traversed. (see earlySourceRange).
+  // Exception 1: when declarators nest, *inner* declarator is the *outer* type.
+  //              e.g. void foo[5](int) is an array of functions.
+  // To handle this case, declarators are careful to only claim the tokens they
+  // own, rather than claim a range and rely on claim ordering.
   //
   // Exception 2: siblings both claim the same node.
   //              e.g. `int x, y;` produces two sibling VarDecls.
   //                    ~~~~~ x
   //                    ~~~~~~~~ y
   // Here the first ("leftmost") sibling claims the tokens it wants, and the
   // other sibling gets what's left. So selecting "int" only includes the left
   // VarDecl in the selection tree.
#endif
   bool shouldSkipChildren(const Stmt *X) const {
     // UserDefinedLiteral (e.g. 12_i) has two children (12 and _i).
     // Unfortunately TokenBuffer sees 12_i as one token and can't split it.
     // So we treat UserDefinedLiteral as a leaf node, owning the token.
     return llvm::isa<UserDefinedLiteral>(X);
   }
 
   // Pushes a node onto the ancestor stack. Pairs with pop().
-  // Performs early hit detection for some nodes (on the earlySourceRange).
   void push(DynTypedNode Node) {
-    SourceRange Early = earlySourceRange(Node);
     dlog("{1}push: {0}", printNodeToString(Node, PrintPolicy), indent());
     Nodes.emplace_back();
     Nodes.back().ASTNode = std::move(Node);
     Nodes.back().Parent = Stack.top();
     Nodes.back().Selected = NoTokens;
     Stack.push(&Nodes.back());
-    claimRange(Early, Nodes.back().Selected);
   }
 
   // Pops a node off the ancestor stack, and finalizes it. Pairs with push().
   // Performs primary hit detection.
   void pop() {
     Node &N = *Stack.top();
     dlog("{1}pop: {0}", printNodeToString(N.ASTNode, PrintPolicy), indent(-1));
     claimTokensFor(N.ASTNode, N.Selected);
     if (N.Selected == NoTokens)
       N.Selected = SelectionTree::Unselected;
     if (N.Selected || !N.Children.empty()) {
       // Attach to the tree.
       N.Parent->Children.push_back(&N);
     } else {
       // Neither N any children are selected, it doesn't belong in the tree.
       assert(&N == &Nodes.back());
       Nodes.pop_back();
     }
     Stack.pop();
   }
 
-  // Returns the range of tokens that this node will claim directly, and
-  // is not available to the node's children.
-  // Usually empty, but sometimes children cover tokens but shouldn't own them.
-  SourceRange earlySourceRange(const DynTypedNode &N) {
-    if (const Decl *D = N.get<Decl>()) {
-      // We want constructor name to be claimed by TypeLoc not the constructor
-      // itself. Similar for deduction guides, we rather want to select the
-      // underlying TypeLoc.
-      // FIXME: Unfortunately this doesn't work, even though RecursiveASTVisitor
-      // traverses the underlying TypeLoc inside DeclarationName, it is null for
-      // constructors.
-      if (isa<CXXConstructorDecl>(D) || isa<CXXDeductionGuideDecl>(D))
-        return SourceRange();
-      // This will capture Field, Function, MSProperty, NonTypeTemplateParm and
-      // VarDecls. We want the name in the declarator to be claimed by the decl
-      // and not by any children. For example:
-      // void [[foo]]();
-      // int (*[[s]])();
-      // struct X { int [[hash]] [32]; [[operator]] int();}
-      if (const auto *DD = llvm::dyn_cast<DeclaratorDecl>(D))
-        return DD->getLocation();
-    } else if (const auto *CCI = N.get<CXXCtorInitializer>()) {
-      // : [[b_]](42)
-      return CCI->getMemberLocation();
-    }
-    return SourceRange();
-  }
-
   // Claim tokens for N, after processing its children.
   // By default this claims all unclaimed tokens in getSourceRange().
   // We override this if we want to claim fewer tokens (e.g. there are gaps).
   void claimTokensFor(const DynTypedNode &N, SelectionTree::Selection &Result) {
+    // CXXConstructExpr often shows implicit construction, like `string s;`.
+    // Don't associate any tokens with it unless there's some syntax like {}.
+    // This prevents it from claiming 's', its primary location.
+    if (const auto *CCE = N.get<CXXConstructExpr>()) {
+      claimRange(CCE->getParenOrBraceRange(), Result);
+      return;
+    }
+    // ExprWithCleanups is always implicit. It often wraps CXXConstructExpr.
+    // Prevent it claiming 's' in the case above.
+    if (N.get<ExprWithCleanups>())
+      return;
+
+    // Declarators nest "inside out", with parent types inside child ones.
+    // Instead of claiming the whole range (clobbering parent tokens), carefully
+    // claim the tokens owned by this node and non-declarator children.
+    // (We could manipulate traversal order instead, but this is easier).
+    //
+    // Non-declarator types nest normally, and are handled like other nodes.
+    //
+    // Example:
+    //   Vec<R<int>(*[2])(A<char>)> is a Vec of arrays of pointers to functions,
+    //                              which accept A<int> and return R<char>.
+    // The TypeLoc hierarchy:
+    //   Vec<R<int>(*[2])(A<char>)> m;
+    //   Vec<--------------------->      TemplateSpecialization Vec
+    //       --------[2]----------       `-Array
+    //       -------*-------------         `-Pointer
+    //       ------(----)---------           `-Paren
+    //       ------------(-------)             `-Function
+    //       R<--->                              |-TemplateSpecialization R
+    //         int                               | `-Builtin int
+    //                    A<---->                `-TemplateSpecialization A
+    //                      char                   `-Builtin int
+    //
+    // In each row, --- represents unclaimed parts of the SourceRange.
+    // For declarator types, we are careful never to claim these.
+    // For non-declarator types, children are guaranteed to claim them first.
     if (const auto *TL = N.get<TypeLoc>()) {
-      // e.g. EltType Foo[OuterSize][InnerSize];
-      //      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ArrayTypeLoc (Outer)
-      //      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |-ArrayTypeLoc (Inner)
-      //      ~~~~~~~                           | |-RecordType
-      //                             ~~~~~~~~~  | `-Expr (InnerSize)
-      //                  ~~~~~~~~~             `-Expr (OuterSize)
-      // Inner ATL must not claim its whole SourceRange, or it clobbers Outer.
-      if (TL->getAs<ArrayTypeLoc>()) {
-        claimRange(TL->getLocalSourceRange(), Result);
+      if (auto PTL = TL->getAs<ParenTypeLoc>()) {
+        claimRange(PTL.getLParenLoc(), Result);
+        claimRange(PTL.getRParenLoc(), Result);
+        return;
+      }
+      if (auto ATL = TL->getAs<ArrayTypeLoc>()) {
+        claimRange(ATL.getBracketsRange(), Result);
+        return;
+      }
+      if (auto PTL = TL->getAs<PointerTypeLoc>()) {
+        claimRange(PTL.getStarLoc(), Result);
+        return;
+      }
+      if (auto FTL = TL->getAs<FunctionTypeLoc>()) {
+        claimRange(SourceRange(FTL.getLParenLoc(), FTL.getEndLoc()), Result);
         return;
       }
-      // FIXME: maybe LocalSourceRange is a better default for TypeLocs.
-      // It doesn't seem to be usable for FunctionTypeLocs.
     }
     claimRange(getSourceRange(N), Result);
   }
 
   // Perform hit-testing of a complete Node against the selection.
   // This runs for every node in the AST, and must be fast in common cases.
   // This is usually called from pop(), so we can take children into account.
-  // The existing state of Result is relevant (early/late claims can interact).
+  // The existing state of Result is relevant.
   void claimRange(SourceRange S, SelectionTree::Selection &Result) {
     for (const auto &ClaimedRange :
          UnclaimedExpandedTokens.erase(TokenBuf.expandedTokens(S)))
       update(Result, SelChecker.test(ClaimedRange));
 
     if (Result && Result != NoTokens)
       dlog("{1}hit selection: {0}", S.printToString(SM), indent());
   }

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

Case Cases[] = {
             #endif
             }
           )cpp",
           nullptr,
       },
       {
           R"cpp(
             struct S { S(const char*); };
-            S [[s ^= "foo"]];
+            [[S s ^= "foo"]];
           )cpp",
-          "CXXConstructExpr",
+          // The AST says a CXXConstructExpr covers the = sign in C++14.
+          // But we consider CXXConstructExpr to only own brackets.
+          // (It's not the interesting constructor anyway, just S(&&)).
+          "VarDecl",
       },
       {
           R"cpp(
             struct S { S(const char*); };
             [[S ^s = "foo"]];
           )cpp",
           "VarDecl",
       },
       {
           R"cpp(
             [[^void]] (*S)(int) = nullptr;
           )cpp",
           "BuiltinTypeLoc",
       },
       {
           R"cpp(
             [[void (*S)^(int)]] = nullptr;
           )cpp",
           "FunctionProtoTypeLoc",
       },
       {
           R"cpp(
             [[void (^*S)(int)]] = nullptr;
           )cpp",
-          "FunctionProtoTypeLoc",
+          "PointerTypeLoc",
       },
       {
           R"cpp(
             [[void (*^S)(int) = nullptr]];
           )cpp",
           "VarDecl",
       },
       {
           R"cpp(
             [[void ^(*S)(int)]] = nullptr;
           )cpp",
-          "FunctionProtoTypeLoc",
+          "ParenTypeLoc",
       },
       {
           R"cpp(
             struct S {
               int foo() const;
               int bar() { return [[f^oo]](); }
             };
           )cpp",
Case Cases[] = {
 
       // Tricky case: nested ArrayTypeLocs have the same token range.
       {"const int x = 1, y = 2; int array[^[[x]]][10][y];", "DeclRefExpr"},
       {"const int x = 1, y = 2; int array[x][10][^[[y]]];", "DeclRefExpr"},
       {"const int x = 1, y = 2; int array[x][^[[10]]][y];", "IntegerLiteral"},
       {"const int x = 1, y = 2; [[i^nt]] array[x][10][y];", "BuiltinTypeLoc"},
       {"void func(int x) { int v_array[^[[x]]][10]; }", "DeclRefExpr"},
 
+      {"int (*getFunc([[do^uble]]))(int);", "BuiltinTypeLoc"},
+
       // FIXME: the AST has no location info for qualifiers.
       {"const [[a^uto]] x = 42;", "AutoTypeLoc"},
       {"[[co^nst auto x = 42]];", "VarDecl"},
 
       {"^", nullptr},
       {"void foo() { [[foo^^]] (); }", "DeclRefExpr"},
 
       // FIXME: Ideally we'd get a declstmt or the VarDecl itself here.