[clangd] Fix selection on multi-dimensional array.

[sammccall]

Ooh, this is messy indeed. Thanks for digging!

clang-tools-extra/clangd/Selection.cpp

526

I don't think this is a complete solution: won't the inner ArrayTypeLoc still end up owning both sets of brackets?

I think maybe a better solution is making getSourceRange(ArrayTypeLoc) return only ATL.getBracketRange(), and then modify canSafelySkipNode to to avoid pruning based on this small range.

This is vaguely similar to how DeclTypeLoc works today (though in that case the reduced range is the one reported by the AST).

527

ConstantArrayType isn't the only kind of array, see the other subclasses of ArrayType

[hokein]

clang-tools-extra/clangd/Selection.cpp

526

won't the inner ArrayTypeLoc still end up owning both sets of brackets?

yes, unfortunately, the inner ATL still owns both sets of brackets, that means go-to-def (etc) won't work on an overloaded subscript operator [], I don't have a better solution to fix that. I guess it is ok to live with that as it might be a rare case in practice.

I think maybe a better solution is making getSourceRange(ArrayTypeLoc) return only ATL.getBracketRange(), and then modify canSafelySkipNode to to avoid pruning based on this small range.

yeah, indeed I tried this approach before coming up the current approach, and I didn't find a satisfied solution (BracketRange is not enough, otherwise we will lose the array type int).

// int array[Size][100];
// ~~~      [-2 -]~~~~~  ConstantArrayTypeLoc int[Size][100]
// [1]            [-3-]  |-ConstantArrayTypeLoc int[100]

Ideally, the inner ATL should own tokens int ([1]) and tokens [100] ([3]). And in the canSafelySkipNode, we want to skip the inner ATL if the cursor is in the source range of array[Size], it seems quite tricky to get the source range (the range of int [1] in particular). Of course we could use some lexer hacks or call ATL.getElementLoc() recursively until we hit a non-array type loc (it can easily go up to O(n^2) for super-multi-dimensional arrays).

527

oh, right. There are three others, we could do similar for them. Will do that if we agree on the current approach.

[hokein]

refine the patch based on D116536, and one more test.

clang-tools-extra/clangd/Selection.cpp

if (const auto *RE = N->ASTNode.get<RecoveryExpr>()) {
       RecoveryType.record(RE->isTypeDependent() ? 0 : 1, LanguageLabel);
       return;
     }
   }
   if (Common)
     SelectionUsedRecovery.record(0, LanguageLabel); // unused.
 }
 
+// Return the range covering a node and all its children.
 SourceRange getSourceRange(const DynTypedNode &N) {
   // MemberExprs to implicitly access anonymous fields should not claim any
   // tokens for themselves. Given:
   //   struct A { struct { int b; }; };
   // The clang AST reports the following nodes for an access to b:
   //   A().b;
   //   [----] MemberExpr, base = A().<anonymous>, member = b
   //   [----] MemberExpr: base = A(), member = <anonymous>
public:
   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc X) {
     return traverseNode(
         &X, [&] { return Base::TraverseNestedNameSpecifierLoc(X); });
   }
   bool TraverseConstructorInitializer(CXXCtorInitializer *X) {
     return traverseNode(
         X, [&] { return Base::TraverseConstructorInitializer(X); });
   }
   bool TraverseCXXBaseSpecifier(const CXXBaseSpecifier &X) {
     return traverseNode(&X, [&] { return Base::TraverseCXXBaseSpecifier(X); });
   }
   bool TraverseAttr(Attr *X) {
     return traverseNode(X, [&] { return Base::TraverseAttr(X); });
   }
   // Stmt is the same, but this form allows the data recursion optimization.
   bool dataTraverseStmtPre(Stmt *X) {
     if (!X || isImplicit(X))
       return false;
void push(DynTypedNode Node) {
     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));
-    claimRange(getSourceRange(N.ASTNode), N.Selected);
+    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());
if (const Decl *D = N.get<Decl>()) {
         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) {
+    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);
+        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).
   void claimRange(SourceRange S, SelectionTree::Selection &Result) {
     for (const auto &ClaimedRange :
          UnclaimedExpandedTokens.erase(TokenBuf.expandedTokens(S)))
       update(Result, SelChecker.test(ClaimedRange));

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

Case Cases[] = {
             };
           )cpp",
           "CXXCtorInitializer", // Not the CXXConstructExpr!
       },
       // Tricky case: anonymous struct is a sibling of the VarDecl.
       {"[[st^ruct {int x;}]] y;", "CXXRecordDecl"},
       {"[[struct {int x;} ^y]];", "VarDecl"},
       {"struct {[[int ^x]];} y;", "FieldDecl"},
+
+      // 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"},
+
       // 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.