[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

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

213

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

217

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

Can we negate this if to reduce nesting?

283

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

Why not just compute this inside ExtractionContext?

[sammccall]

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

213

Oops, forgot we already were in one.

217

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

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

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–51

Nit: same parameter order for replaceWithVar and insertDeclaration.

245

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

305

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

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

Can we have some tests with macros as well?

[sammccall]

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

50–51

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

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

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

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

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

448

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–51

Sorry yes, makes sense.

305

But isn't the tree something like

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

[SureYeaah]

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

448

Isn't it the same behavior in both cases?

[sammccall]

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

305

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/clangd/Selection.h

struct Node {
     llvm::SmallVector<const Node *, 8> Children;
     // The corresponding node from the full AST.
     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;
+    // 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.
   // If there is no selection, this is nullptr.
   const Node *commonAncestor() const;
   // The selection node corresponding to TranslationUnitDecl.
   // If there is no selection, this is nullptr.
   const Node *root() const { return Root; }
 

clang-tools-extra/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/clangd/refactor/tweaks/ExtractVariable.cpp

 //===--- ExtractVariable.cpp ------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "ClangdUnit.h"
 #include "Logger.h"
 #include "Protocol.h"
 #include "Selection.h"
 #include "SourceCode.h"
 #include "refactor/Tweak.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
 #include "clang/AST/OperationKinds.h"
+#include "clang/AST/PrettyPrinter.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/Basic/LangOptions.h"
 #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.
+namespace {
+
+// Information extracted about a binary operator encounted in a SelectionTree.
+// It can represent either an overloaded or built-in operator.
+struct ParsedBinaryOperator {
+  BinaryOperatorKind Kind;
+  bool OperatorSelected = false;
+  llvm::SmallVector<const SelectionTree::Node*, 8> SelectedOperands;
+
+  // If N is a binary operator, populate this and return true.
+  bool parse(const SelectionTree::Node &N) {
+    if (const BinaryOperator *Op =
+        llvm::dyn_cast_or_null<BinaryOperator>(N.ASTNode.get<Expr>())) {
+      Kind = Op->getOpcode();
+      // FIXME: this could also be whitespace around the operand.
+      OperatorSelected = N.Selected;
+      SelectedOperands = N.Children;
+      return true;
+    }
+    if (const CXXOperatorCallExpr *Op =
+            llvm::dyn_cast_or_null<CXXOperatorCallExpr>(
+                N.ASTNode.get<Expr>())) {
+      if (Op->isInfixBinaryOp()) {
+        Kind = BinaryOperator::getOverloadedOpcode(Op->getOperator());
+        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);
+          else
+            OperatorSelected = true;
+        }
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool associative() const {
+    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;
+    }
+  }
+};
+
+// 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 and the
+// operator itself is not selected.
+//
+// e.g. for a + [[b + c]] + d
+//        +
+//       / \
+//  N-> +   d
+//     / \
+// X->+   c <- End
+//   / \
+//  a   b <- Start
+// It's critical that the operator marked X is unselected, otherwise the
+// correct start point would be X itself.
+const SelectionTree::Node *getEndpoint(const SelectionTree::Node &N,
+                                       BinaryOperatorKind OuterOp, bool IsStart,
+                                       const SourceManager &SM) {
+  // If N is not a binary operator of the desired type, we have to stop here.
+  ParsedBinaryOperator Op;
+  if (!Op.parse(N.ignoreImplicit()) || Op.Kind != OuterOp)
+    return &N;
+
+  // Don't support crossing macro boundaries, that way lies madness.
+  auto FileOf = [&](const SelectionTree::Node N) {
+    return SM.getFileID(N.ASTNode.getSourceRange().getBegin());
+  };
+  FileID F = FileOf(N);
+  for (const SelectionTree::Node* Child : Op.SelectedOperands)
+    if (FileOf(*Child) != F)
+      return &N;
+
+  // Assume IsStart is true, so we want the first chunk of the subexpr.
+  // Because we're in a subtree of a Op selection, and we've disallowed
+  // crossing macro boundaries, the selection is a suffix of N.
+  // this first chunk must also be selected.
+  //
+  // The cases:
+  // 1. Operator is selected. (Implies RHS is completely selected)
+  //    1a): RHS is selected but LHS is not. Return RHS.
+  //    1b): RHS and part of LHS is selected. Recurse into LHS to find start.
+  // 2. Operator is not selected. (Implies LHS is not selected)
+  //    2a): RHS is not selected: impossible, as selection would be empty.
+  //    2b): Some of RHS is selected. Recurse into RHS to find start.
+  //
+  // Because only the selected parts are in the SelectionTree, it's tricky to
+  // identify RHS/LHS (there can be 0/1/2 children).
+  // However knowing the selection is a suffix eliminates enough cases to make
+  // it possible.
+  //
+  // (If IsStart is false, we reverse LHS/RHS everywhere)
+  assert(!Op.SelectedOperands.empty() && "got only operator on one side!");
+  assert(Op.SelectedOperands.size() <= 2 && "Funny-shaped binary operator!");
+  if (Op.OperatorSelected) {
+    if (Op.SelectedOperands.size() == 1) // Case 1a
+      return Op.SelectedOperands.front();
+    // Case 1b
+    return getEndpoint(IsStart ? *Op.SelectedOperands.front()
+                               : *Op.SelectedOperands.back(),
+                       OuterOp, IsStart, SM);
+  } else {
+    assert(Op.SelectedOperands.size() == 1 &&
+           "selected both sides but not operator!");
+    return getEndpoint(*Op.SelectedOperands.front(), OuterOp, IsStart, SM);
+  }
+}
+
+} // namespace
+
+SourceRange ExtractionContext::getExtractionChars() const {
+  ParsedBinaryOperator Op;
+  // Special case: we're extracting an associative binary subexpression.
+  if (Op.parse(*ExprNode) && Op.associative() &&
+      Op.SelectedOperands.size() == 2) {
+    const SelectionTree::Node *LHS =
+        getEndpoint(*Op.SelectedOperands.front(), Op.Kind, true, SM);
+    const SelectionTree::Node *RHS =
+        getEndpoint(*Op.SelectedOperands.back(), Op.Kind, true, SM);
+    return SourceRange(toHalfOpenFileRange(SM, Ctx.getLangOpts(),
+                                           LHS->ASTNode.getSourceRange())
+                           ->getBegin(),
+                       toHalfOpenFileRange(SM, Ctx.getLangOpts(),
+                                           RHS->ASTNode.getSourceRange())
+                           ->getEnd());
+  }
+  // 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) {
   Target = llvm::make_unique<ExtractionContext>(N, SM, Ctx);
   return Target->isExtractable();
 }
 
 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);
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

clang-tools-extra/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/clangd/unittests/TweakTests.cpp

const std::vector<std::pair<llvm::StringLiteral, llvm::StringLiteral>>
                  })cpp",
            R"cpp(#define PLUS(x) x++
                  void f(int a) {
                    auto dummy = a; PLUS(dummy);
                  })cpp"},
           // FIXME: Doesn't work correctly 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"},
+          // 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 = 1 * [[2 + 3 * 4]] + 5;
+                 })cpp",
+           R"cpp(void f() {
+                   auto dummy = 1 * 2 + 3 * 4; int x = 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"},
+
       };
   for (const auto &IO : InputOutputs) {
     checkTransform(ID, IO.first, IO.second);
   }
 }
 
 TEST(TweakTest, AnnotateHighlightings) {
   llvm::StringLiteral ID = "AnnotateHighlightings";