[clangd] Support extraction of binary "subexpressions" like a + [[b + c]].

[sammccall]

Summary

These aren't formally subexpressions in C++, in this case + is left-associative.
However informally +, *, etc are usually (mathematically) associative and users
consider these subexpressions.

We detect these and in simple cases support extracting the partial expression.
As well as builtin associative operators, we assume that overloads of them
are associative and support those too.

[SureYeaah]

clang-tools-extra/clangd/refactor/tweaks/ExtractVariable.cpp

210 ↗

(On Diff #211276)

A related FIXME would be helpful since it's pretty easy to fix(I think?) and seems like something important.

213 ↗

(On Diff #211276)

Why do we need an anon namespace inside another anon namespace?

217 ↗

(On Diff #211276)

Wouldn't it make more sense this to have this in some other place (maybe Selection) because other refactorings might want to make use of this feature?

235 ↗

(On Diff #211276)

Can we negate this if to reduce nesting?

283 ↗

(On Diff #211276)

We're considering the case where all the operators are the same. Isn't it true that in that case, the End will be the the first 'selected RHS' that we find during the traversal? If so, can't we just get rid of the IsStart?

393 ↗

(On Diff #211276)

Why not just compute this inside ExtractionContext?

[sammccall]

clang-tools-extra/clangd/refactor/tweaks/ExtractVariable.cpp

213 ↗

(On Diff #211276)

Oops, forgot we already were in one.

217 ↗

(On Diff #211276)

It's possible, but I think we should cross that bridge when we come to it, because it's not obvious what those other refactorings are.

There might be some subtle ways in which I've specialized the code for this use case, and it's easier to see that and polish it when we have more use cases in hand.

283 ↗

(On Diff #211276)

Oh, right - I'm assuming a much more general tree than can actually exist.
This code is trying to handle an arbitrary binary tree of binops, but of course each actual operator is either left-associative or right-associative, and so it's a linked-list-shaped binary tree.
And the actual code is pretty simple, but the explanation sure is complicated.

And in fact, all the operators are left-associative! I didn't really want to hard-code that, but it'll simplify the code a lot I think.

So this should probably just be a simple loop:

findEndpoints(L, R):
  while (LL, RL) = parseBinop(L):
    L = (LL is selected) ? LL : RL
  return (L, R)

I'll rewrite this tomorrow. Thanks for the hint!

[sammccall]

Address minor comments, but not tree-traversal simplification yet.

[sammccall]

Rather than handling arbitrary trees, exploit the fact that the operator is left-associative.

[sammccall]

This is ready for another round, I think.

clang-tools-extra/clangd/refactor/tweaks/ExtractVariable.cpp

393 ↗

(On Diff #211276)

Using ExtractionContext to cache values that are used in several places but not everywhere seems confusing and to obfuscate the data flow.

In particular, when is it going to be initialized? Not in the constructor, because we don't want to do this during compare. On first access? That seems much less clear than explicitly computing it and passing it around.

[SureYeaah]

clang-tools-extra/clangd/refactor/tweaks/ExtractVariable.cpp

50 ↗

(On Diff #211679)

Nit: same parameter order for replaceWithVar and insertDeclaration.

245 ↗

(On Diff #211679)

Why do we need to check this for CXXOperatorCallExpr and not BinaryOperator?

305 ↗

(On Diff #211679)

For 1 + [[2 + 3 * 4]] + 5, we probably don't get an invalid range from this function. If so, we might want to add one more check where we parse End and compare it's operator.

314 ↗

(On Diff #211679)

Nit: For [[a + b + c]],

     +
   /  \
  +    c
 / \
a   b

For the second + as Op, a would be completely selected. So Op.LHS can be partially or completely selected.

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

448 ↗

(On Diff #211679)

Can we have some tests with macros as well?

[sammccall]

clang-tools-extra/clangd/refactor/tweaks/ExtractVariable.cpp

50 ↗

(On Diff #211679)

I think this *is* the same parameter order semantically: this is roughly (thing, definition) in both cases.
The fact that the *types* match but in the opposite order is just a coincidence I think?

245 ↗

(On Diff #211679)

Because there's no child AST node corresponding to a builtin +, but there is one corresponding to an overloaded +: a DeclRefExpr to an operator+ FunctionDecl.

305 ↗

(On Diff #211679)

I'm not quite sure what you mean here.

Annotating the operators, for 1 +a [[2 +b 3 *c 4]] +d 5:

• N is *c
• RHS is 4
• LHS is 1 +a 2 +b 3 *c 4.

The point is that RHS can never be an operator of the same type, because if we replaced RHS with x +e y then N would be that +e instead (since + is left-associative).

314 ↗

(On Diff #211679)

Yeah, I meant "at least partially". Elaborated comment.

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

448 ↗

(On Diff #211679)

Added a simple one that just verifies we support operands being wrapped in macros, but not operators.

[sammccall]

Elaborate tests and comments.

[SureYeaah]

clang-tools-extra/clangd/refactor/tweaks/ExtractVariable.cpp

50 ↗

(On Diff #211679)

Sorry yes, makes sense.

305 ↗

(On Diff #211679)

But isn't the tree something like

             +
          /    \ 
         +     5
      /     \
  +           *
/  \       /   \
1    2    3    4

[SureYeaah]

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

448 ↗

(On Diff #211679)

Isn't it the same behavior in both cases?

[sammccall]

clang-tools-extra/clangd/refactor/tweaks/ExtractVariable.cpp

305 ↗

(On Diff #211679)

Whoops, somehow I transcribed that without noticing c was a * instead of a +.

From offline discussion: the code is apparently correct here: RHS can't be a matching operator, because it violates associativity: the parse tree would be rotated in that case. We don't care to distinguish between mismatching operator vs some other node entirely.

• Expanded a comment to cover this more explicitly
• adjusted a testcase to ensure that we expand a +-selection across a * on the RHS as well as the LHS.

There's also the idea that it would be nice to verify that we don't bail out of this function just because the selection covers some mismatched operator. The idea of a test that we keep digging right if left mismatches and vice versa is appealing, but as described we never need to to dig right, so such a case doesn't exist. I've settled for ensuring that 0 + 1 * [2 + 3] * 4 + 5 expands to cover 1 and 4, but not 0 or 5.

[sammccall]

Improve testcase, expand comment to clarify RHS non-traversal.

clang-tools-extra/trunk/clangd/Selection.h

struct Node {
     ast_type_traits::DynTypedNode ASTNode;
     // The extent to which this node is covered by the selection.
     Selection Selected;
     // Walk up the AST to get the DeclContext of this Node,
     // which is not the node itself.
     const DeclContext& getDeclContext() const;
     // Printable node kind, like "CXXRecordDecl" or "AutoTypeLoc".
     std::string kind() const;
+    // If this node is a wrapper with no syntax (e.g. implicit cast), return
+    // its contents. (If multiple wrappers are present, unwraps all of them).
+    const Node& ignoreImplicit() const;
   };
   // The most specific common ancestor of all the selected nodes.
   // Returns nullptr if the common ancestor is the root.
   // (This is to avoid accidentally traversing the TUDecl and thus preamble).
   const Node *commonAncestor() const;
   // The selection node corresponding to TranslationUnitDecl.
   const Node &root() const { return *Root; }
 

clang-tools-extra/trunk/clangd/Selection.cpp

if (const Decl* Current = CurrentNode->ASTNode.get<Decl>()) {
         if (auto *DC = dyn_cast<DeclContext>(Current))
           return *DC;
       return *Current->getDeclContext();
     }
   }
   llvm_unreachable("A tree must always be rooted at TranslationUnitDecl.");
 }
 
+const SelectionTree::Node &SelectionTree::Node::ignoreImplicit() const {
+  if (Children.size() == 1 &&
+      Children.front()->ASTNode.getSourceRange() == ASTNode.getSourceRange())
+    return Children.front()->ignoreImplicit();
+  return *this;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/refactor/tweaks/ExtractVariable.cpp

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 // information regarding the Expr that is being extracted
 class ExtractionContext {
 public:
   ExtractionContext(const SelectionTree::Node *Node, const SourceManager &SM,
                     const ASTContext &Ctx);
   const clang::Expr *getExpr() const { return Expr; }
   const SelectionTree::Node *getExprNode() const { return ExprNode; }
   bool isExtractable() const { return Extractable; }
+  // The half-open range for the expression to be extracted.
+  SourceRange getExtractionChars() const;
   // Generate Replacement for replacing selected expression with given VarName
-  tooling::Replacement replaceWithVar(llvm::StringRef VarName) const;
+  tooling::Replacement replaceWithVar(SourceRange Chars,
+                                      llvm::StringRef VarName) const;
   // Generate Replacement for declaring the selected Expr as a new variable
-  tooling::Replacement insertDeclaration(llvm::StringRef VarName) const;
+  tooling::Replacement insertDeclaration(llvm::StringRef VarName,
+                                         SourceRange InitChars) const;
 
 private:
   bool Extractable = false;
   const clang::Expr *Expr;
   const SelectionTree::Node *ExprNode;
   // Stmt before which we will extract
   const clang::Stmt *InsertionPoint = nullptr;
   const SourceManager &SM;
if (const clang::Stmt *CurParent = CurNode->Parent->ASTNode.get<Stmt>()) {
         if (CurParent->getBeginLoc().isMacroID())
           continue;
         return CurInsertionPoint;
       }
     }
   }
   return nullptr;
 }
+
 // returns the replacement for substituting the extraction with VarName
 tooling::Replacement
-ExtractionContext::replaceWithVar(llvm::StringRef VarName) const {
-  const llvm::Optional<SourceRange> ExtractionRng =
-      toHalfOpenFileRange(SM, Ctx.getLangOpts(), getExpr()->getSourceRange());
-  unsigned ExtractionLength = SM.getFileOffset(ExtractionRng->getEnd()) -
-                              SM.getFileOffset(ExtractionRng->getBegin());
-  return tooling::Replacement(SM, ExtractionRng->getBegin(), ExtractionLength,
-                              VarName);
+ExtractionContext::replaceWithVar(SourceRange Chars,
+                                  llvm::StringRef VarName) const {
+  unsigned ExtractionLength =
+      SM.getFileOffset(Chars.getEnd()) - SM.getFileOffset(Chars.getBegin());
+  return tooling::Replacement(SM, Chars.getBegin(), ExtractionLength, VarName);
 }
 // returns the Replacement for declaring a new variable storing the extraction
 tooling::Replacement
-ExtractionContext::insertDeclaration(llvm::StringRef VarName) const {
-  const llvm::Optional<SourceRange> ExtractionRng =
-      toHalfOpenFileRange(SM, Ctx.getLangOpts(), getExpr()->getSourceRange());
-  assert(ExtractionRng && "ExtractionRng should not be null");
-  llvm::StringRef ExtractionCode = toSourceCode(SM, *ExtractionRng);
+ExtractionContext::insertDeclaration(llvm::StringRef VarName,
+                                     SourceRange InitializerChars) const {
+  llvm::StringRef ExtractionCode = toSourceCode(SM, InitializerChars);
   const SourceLocation InsertionLoc =
       toHalfOpenFileRange(SM, Ctx.getLangOpts(),
                           InsertionPoint->getSourceRange())
           ->getBegin();
   // FIXME: Replace auto with explicit type and add &/&& as necessary
   std::string ExtractedVarDecl = std::string("auto ") + VarName.str() + " = " +
                                  ExtractionCode.str() + "; ";
   return tooling::Replacement(SM, InsertionLoc, 0, ExtractedVarDecl);
 }
 
+// Helpers for handling "binary subexpressions" like a + [[b + c]] + d.
+//
+// These are special, because the formal AST doesn't match what users expect:
+// - the AST is ((a + b) + c) + d, so the ancestor expression is `a + b + c`.
+// - but extracting `b + c` is reasonable, as + is (mathematically) associative.
+//
+// So we try to support these cases with some restrictions:
+//  - the operator must be associative
+//  - no mixing of operators is allowed
+//  - we don't look inside macro expansions in the subexpressions
+//  - we only adjust the extracted range, so references in the unselected parts
+//    of the AST expression (e.g. `a`) are still considered referenced for
+//    the purposes of calculating the insertion point.
+//    FIXME: it would be nice to exclude these references, by micromanaging
+//    the computeReferencedDecls() calls around the binary operator tree.
+
+// Information extracted about a binary operator encounted in a SelectionTree.
+// It can represent either an overloaded or built-in operator.
+struct ParsedBinaryOperator {
+  BinaryOperatorKind Kind;
+  SourceLocation ExprLoc;
+  llvm::SmallVector<const SelectionTree::Node*, 8> SelectedOperands;
+
+  // If N is a binary operator, populate this and return true.
+  bool parse(const SelectionTree::Node &N) {
+    SelectedOperands.clear();
+
+    if (const BinaryOperator *Op =
+        llvm::dyn_cast_or_null<BinaryOperator>(N.ASTNode.get<Expr>())) {
+      Kind = Op->getOpcode();
+      ExprLoc = Op->getExprLoc();
+      SelectedOperands = N.Children;
+      return true;
+    }
+    if (const CXXOperatorCallExpr *Op =
+            llvm::dyn_cast_or_null<CXXOperatorCallExpr>(
+                N.ASTNode.get<Expr>())) {
+      if (!Op->isInfixBinaryOp())
+        return false;
+
+      Kind = BinaryOperator::getOverloadedOpcode(Op->getOperator());
+      ExprLoc = Op->getExprLoc();
+      // Not all children are args, there's also the callee (operator).
+      for (const auto* Child : N.Children) {
+        const Expr *E = Child->ASTNode.get<Expr>();
+        assert(E && "callee and args should be Exprs!");
+        if (E == Op->getArg(0) || E == Op->getArg(1))
+          SelectedOperands.push_back(Child);
+      }
+      return true;
+    }
+    return false;
+  }
+
+  bool associative() const {
+    // Must also be left-associative, or update getBinaryOperatorRange()!
+    switch (Kind) {
+    case BO_Add:
+    case BO_Mul:
+    case BO_And:
+    case BO_Or:
+    case BO_Xor:
+    case BO_LAnd:
+    case BO_LOr:
+      return true;
+    default:
+      return false;
+    }
+  }
+
+  bool crossesMacroBoundary(const SourceManager &SM) {
+    FileID F = SM.getFileID(ExprLoc);
+    for (const SelectionTree::Node *Child : SelectedOperands)
+      if (SM.getFileID(Child->ASTNode.get<Expr>()->getExprLoc()) != F)
+        return true;
+    return false;
+  }
+};
+
+// If have an associative operator at the top level, then we must find
+// the start point (rightmost in LHS) and end point (leftmost in RHS).
+// We can only descend into subtrees where the operator matches.
+//
+// e.g. for a + [[b + c]] + d
+//        +
+//       / \
+//  N-> +   d
+//     / \
+//    +   c <- End
+//   / \
+//  a   b <- Start
+const SourceRange getBinaryOperatorRange(const SelectionTree::Node &N,
+                                         const SourceManager &SM,
+                                         const LangOptions &LangOpts) {
+  // If N is not a suitable binary operator, bail out.
+  ParsedBinaryOperator Op;
+  if (!Op.parse(N.ignoreImplicit()) || !Op.associative() ||
+      Op.crossesMacroBoundary(SM) || Op.SelectedOperands.size() != 2)
+    return SourceRange();
+  BinaryOperatorKind OuterOp = Op.Kind;
+
+  // Because the tree we're interested in contains only one operator type, and
+  // all eligible operators are left-associative, the shape of the tree is
+  // very restricted: it's a linked list along the left edges.
+  // This simplifies our implementation.
+  const SelectionTree::Node *Start = Op.SelectedOperands.front(); // LHS
+  const SelectionTree::Node *End = Op.SelectedOperands.back();    // RHS
+  // End is already correct: it can't be an OuterOp (as it's left-associative).
+  // Start needs to be pushed down int the subtree to the right spot.
+  while (Op.parse(Start->ignoreImplicit()) && Op.Kind == OuterOp &&
+         !Op.crossesMacroBoundary(SM)) {
+    assert(!Op.SelectedOperands.empty() && "got only operator on one side!");
+    if (Op.SelectedOperands.size() == 1) { // Only Op.RHS selected
+      Start = Op.SelectedOperands.back();
+      break;
+    }
+    // Op.LHS is (at least partially) selected, so descend into it.
+    Start = Op.SelectedOperands.front();
+  }
+
+  return SourceRange(
+      toHalfOpenFileRange(SM, LangOpts, Start->ASTNode.getSourceRange())
+          ->getBegin(),
+      toHalfOpenFileRange(SM, LangOpts, End->ASTNode.getSourceRange())
+          ->getEnd());
+}
+
+SourceRange ExtractionContext::getExtractionChars() const {
+  // Special case: we're extracting an associative binary subexpression.
+  SourceRange BinaryOperatorRange =
+      getBinaryOperatorRange(*ExprNode, SM, Ctx.getLangOpts());
+  if (BinaryOperatorRange.isValid())
+    return BinaryOperatorRange;
+
+  // Usual case: we're extracting the whole expression.
+  return *toHalfOpenFileRange(SM, Ctx.getLangOpts(), Expr->getSourceRange());
+}
+
 /// Extracts an expression to the variable dummy
 /// Before:
 /// int x = 5 + 4 * 3;
 ///         ^^^^^
 /// After:
 /// auto dummy = 5 + 4;
 /// int x = dummy * 3;
 class ExtractVariable : public Tweak {
bool ExtractVariable::prepare(const Selection &Inputs) {
   const SelectionTree::Node *N = Inputs.ASTSelection.commonAncestor();
   return computeExtractionContext(N, SM, Ctx);
 }
 
 Expected<Tweak::Effect> ExtractVariable::apply(const Selection &Inputs) {
   tooling::Replacements Result;
   // FIXME: get variable name from user or suggest based on type
   std::string VarName = "dummy";
+  SourceRange Range = Target->getExtractionChars();
   // insert new variable declaration
-  if (auto Err = Result.add(Target->insertDeclaration(VarName)))
+  if (auto Err = Result.add(Target->insertDeclaration(VarName, Range)))
     return std::move(Err);
   // replace expression with variable name
-  if (auto Err = Result.add(Target->replaceWithVar(VarName)))
+  if (auto Err = Result.add(Target->replaceWithVar(Range, VarName)))
     return std::move(Err);
   return Effect::applyEdit(Result);
 }
 
 // Find the CallExpr whose callee is an ancestor of the DeclRef
 const SelectionTree::Node *getCallExpr(const SelectionTree::Node *DeclRef) {
   // we maintain a stack of all exprs encountered while traversing the
   // selectiontree because the callee of the callexpr can be an ancestor of the

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

for (const SelectionTree::Node *N : allNodes(T))
         Complete.push_back(nodeRange(N, AST));
       else if (N->Selected == SelectionTree::Partial)
         Partial.push_back(nodeRange(N, AST));
     EXPECT_THAT(Complete, UnorderedElementsAreArray(Test.ranges("C"))) << C;
     EXPECT_THAT(Partial, UnorderedElementsAreArray(Test.ranges())) << C;
   }
 }
 
+TEST(SelectionTest, Implicit) {
+  const char* Test = R"cpp(
+    struct S { S(const char*); };
+    int f(S);
+    int x = f("^");
+  )cpp";
+  auto AST = TestTU::withCode(Annotations(Test).code()).build();
+  auto T = makeSelectionTree(Test, AST);
+
+  const SelectionTree::Node *Str = T.commonAncestor();
+  EXPECT_EQ("StringLiteral", nodeKind(Str)) << "Implicit selected?";
+  EXPECT_EQ("ImplicitCastExpr", nodeKind(Str->Parent));
+  EXPECT_EQ("CXXConstructExpr", nodeKind(Str->Parent->Parent));
+  EXPECT_EQ(Str, &Str->Parent->Parent->ignoreImplicit())
+      << "Didn't unwrap " << nodeKind(&Str->Parent->Parent->ignoreImplicit());
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/unittests/TweakTests.cpp

const std::vector<std::pair<llvm::StringLiteral, llvm::StringLiteral>>
                  };)cpp"},
           // Function DeclRefExpr
           {R"cpp(int f() {
                    return [[f]]();
                  })cpp",
            R"cpp(int f() {
                    auto dummy = f(); return dummy;
                  })cpp"},
-          
           // FIXME: Wrong result for \[\[clang::uninitialized\]\] int b = [[1]];
           // since the attr is inside the DeclStmt and the bounds of
           // DeclStmt don't cover the attribute.
+
+          // Binary subexpressions
+          {R"cpp(void f() {
+                   int x = 1 + [[2 + 3 + 4]] + 5;
+                 })cpp",
+           R"cpp(void f() {
+                   auto dummy = 2 + 3 + 4; int x = 1 + dummy + 5;
+                 })cpp"},
+          {R"cpp(void f() {
+                   int x = [[1 + 2 + 3]] + 4 + 5;
+                 })cpp",
+           R"cpp(void f() {
+                   auto dummy = 1 + 2 + 3; int x = dummy + 4 + 5;
+                 })cpp"},
+          {R"cpp(void f() {
+                   int x = 1 + 2 + [[3 + 4 + 5]];
+                 })cpp",
+           R"cpp(void f() {
+                   auto dummy = 3 + 4 + 5; int x = 1 + 2 + dummy;
+                 })cpp"},
+          // Non-associative operations have no special support
+          {R"cpp(void f() {
+                   int x = 1 - [[2 - 3 - 4]] - 5;
+                 })cpp",
+           R"cpp(void f() {
+                   auto dummy = 1 - 2 - 3 - 4; int x = dummy - 5;
+                 })cpp"},
+          // A mix of associative operators isn't associative.
+          {R"cpp(void f() {
+                   int x = 0 + 1 * [[2 + 3]] * 4 + 5;
+                 })cpp",
+           R"cpp(void f() {
+                   auto dummy = 1 * 2 + 3 * 4; int x = 0 + dummy + 5;
+                 })cpp"},
+          // Overloaded operators are supported, we assume associativity
+          // as if they were built-in.
+          {R"cpp(struct S {
+                   S(int);
+                 };
+                 S operator+(S, S);
+
+                 void f() {
+                   S x = S(1) + [[S(2) + S(3) + S(4)]] + S(5);
+                 })cpp",
+           R"cpp(struct S {
+                   S(int);
+                 };
+                 S operator+(S, S);
+
+                 void f() {
+                   auto dummy = S(2) + S(3) + S(4); S x = S(1) + dummy + S(5);
+                 })cpp"},
+           // Don't try to analyze across macro boundaries
+           // FIXME: it'd be nice to do this someday (in a safe way)
+          {R"cpp(#define ECHO(X) X
+                 void f() {
+                   int x = 1 + [[ECHO(2 + 3) + 4]] + 5;
+                 })cpp",
+           R"cpp(#define ECHO(X) X
+                 void f() {
+                   auto dummy = 1 + ECHO(2 + 3) + 4; int x = dummy + 5;
+                 })cpp"},
+          {R"cpp(#define ECHO(X) X
+                 void f() {
+                   int x = 1 + [[ECHO(2) + ECHO(3) + 4]] + 5;
+                 })cpp",
+           R"cpp(#define ECHO(X) X
+                 void f() {
+                   auto dummy = 1 + ECHO(2) + ECHO(3) + 4; int x = dummy + 5;
+                 })cpp"},
       };
   for (const auto &IO : InputOutputs) {
     checkTransform(ID, IO.first, IO.second);
   }
 }
 
 TEST(TweakTest, AnnotateHighlightings) {
   llvm::StringLiteral ID = "AnnotateHighlightings";