[libTooling] Add an `EditGenerator` that applies a rule throughout a bound node.

[ymandel]

Summary

The new combinator, rewriteDescendants, applies a rewrite rule to all
descendants of a specified bound node. That rewrite rule can refer to nodes
bound by the parent, both in the matcher and in the edits.

[gribozavr2]

clang/include/clang/Tooling/Transformer/RewriteRule.h

337

Please use three slashes for doc comments.

clang/lib/Tooling/Transformer/RewriteRule.cpp

194

Wouldn't this line move the same value multiple times?

208

The fix seems trivial -- removing the if statement. Why not do that?

clang/unittests/Tooling/TransformerTest.cpp

422

These tests do not demonstrate that the rewrite is only applied to the descendants of the specified AST node -- would be good to test that.

1184

Any particular reason to add these tests at the end of the file instead of grouped together with the rest of the tests for rewriteDescendants above?

[ymandel]

addressed comments.

[ymandel]

clang/include/clang/Tooling/Transformer/RewriteRule.h

337

Done, thanks for catching! Also, added example.

clang/lib/Tooling/Transformer/RewriteRule.cpp

194

good catch!

clang/include/clang/Tooling/Transformer/RewriteRule.h

 /// Assuming that the inner range is enclosed by the outer range, creates
 /// precision edits to remove the parts of the outer range that are not included
 /// in the inner range.
 inline EditGenerator shrinkTo(RangeSelector outer, RangeSelector inner) {
   return editList({remove(enclose(before(outer), before(inner))),
                    remove(enclose(after(inner), after(outer)))});
 }
 
+/// Applies `Rule` to all descendants of the node bound to `NodeId`. `Rule` can
+/// refer to nodes bound by the calling rule. `Rule` is not applied to the node
+/// itself.
+///
+/// For example,
+/// ```
+/// auto InlineX =
+///     makeRule(declRefExpr(to(varDecl(hasName("x")))), changeTo(cat("3")));
+/// makeRule(functionDecl(hasName("f"), hasBody(stmt().bind("body"))).bind("f"),
+///          flatten(
+///            changeTo(name("f"), cat("newName")),
+///            rewriteDescendants("body", InlineX)));
+/// ```
+/// Here, we find the function `f`, change its name to `newName` and change all
+/// appearances of `x` in its body to `3`.
+EditGenerator rewriteDescendants(std::string NodeId, RewriteRule Rule);
+
 /// The following three functions are a low-level part of the RewriteRule
 /// API. We expose them for use in implementing the fixtures that interpret
 /// RewriteRule, like Transformer and TransfomerTidy, or for more advanced
 /// users.
 //
 // FIXME: These functions are really public, if advanced, elements of the
 // RewriteRule API.  Recast them as such.  Or, just declare these functions
 // public and well-supported and move them out of `detail`.

clang/lib/Tooling/Transformer/RewriteRule.cpp

 //===--- Transformer.cpp - Transformer library implementation ---*- 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 "clang/Tooling/Transformer/RewriteRule.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/Stmt.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Transformer/SourceCode.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
public:
   }
 };
 } // namespace
 
 ASTEdit transformer::remove(RangeSelector S) {
   return change(std::move(S), std::make_shared<SimpleTextGenerator>(""));
 }
 
-RewriteRule transformer::makeRule(ast_matchers::internal::DynTypedMatcher M,
-                                  EditGenerator Edits,
+RewriteRule transformer::makeRule(DynTypedMatcher M, EditGenerator Edits,
                                   TextGenerator Explanation) {
   return RewriteRule{{RewriteRule::Case{
       std::move(M), std::move(Edits), std::move(Explanation), {}}}};
 }
 
+namespace {
+
+/// Unconditionally binds the given node set before trying `InnerMatcher` and
+/// keeps the bound nodes on a successful match.
+template <typename T>
+class BindingsMatcher : public ast_matchers::internal::MatcherInterface<T> {
+  ast_matchers::BoundNodes Nodes;
+  const ast_matchers::internal::Matcher<T> InnerMatcher;
+
+public:
+  explicit BindingsMatcher(ast_matchers::BoundNodes Nodes,
+                           ast_matchers::internal::Matcher<T> InnerMatcher)
+      : Nodes(std::move(Nodes)), InnerMatcher(std::move(InnerMatcher)) {}
+
+  bool matches(
+      const T &Node, ast_matchers::internal::ASTMatchFinder *Finder,
+      ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override {
+    ast_matchers::internal::BoundNodesTreeBuilder Result(*Builder);
+    for (const auto &N : Nodes.getMap())
+      Result.setBinding(N.first, N.second);
+    if (InnerMatcher.matches(Node, Finder, &Result)) {
+      *Builder = std::move(Result);
+      return true;
+    }
+    return false;
+  }
+};
+
+/// Matches nodes of type T that have at least one descendant node for which the
+/// given inner matcher matches.  Will match for each descendant node that
+/// matches.  Based on ForEachDescendantMatcher, but takes a dynamic matcher,
+/// instead of a static one, because it is used by RewriteRule, which carries
+/// (only top-level) dynamic matchers.
+template <typename T>
+class DynamicForEachDescendantMatcher
+    : public ast_matchers::internal::MatcherInterface<T> {
+  const DynTypedMatcher DescendantMatcher;
+
+public:
+  explicit DynamicForEachDescendantMatcher(DynTypedMatcher DescendantMatcher)
+      : DescendantMatcher(std::move(DescendantMatcher)) {}
+
+  bool matches(
+      const T &Node, ast_matchers::internal::ASTMatchFinder *Finder,
+      ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override {
+    return Finder->matchesDescendantOf(
+        Node, this->DescendantMatcher, Builder,
+        ast_matchers::internal::ASTMatchFinder::BK_All);
+  }
+};
+
+template <typename T>
+ast_matchers::internal::Matcher<T>
+forEachDescendantDynamically(ast_matchers::BoundNodes Nodes,
+                             DynTypedMatcher M) {
+  return ast_matchers::internal::makeMatcher(new BindingsMatcher<T>(
+      std::move(Nodes),
+      ast_matchers::internal::makeMatcher(
+          new DynamicForEachDescendantMatcher<T>(std::move(M)))));
+}
+
+class ApplyRuleCallback : public MatchFinder::MatchCallback {
+public:
+  ApplyRuleCallback(RewriteRule Rule) : Rule(std::move(Rule)) {}
+
+  template <typename T>
+  void registerMatchers(const ast_matchers::BoundNodes &Nodes,
+                        MatchFinder *MF) {
+    for (auto &Matcher : transformer::detail::buildMatchers(Rule))
+      MF->addMatcher(forEachDescendantDynamically<T>(Nodes, Matcher), this);
+  }
+
+  void run(const MatchFinder::MatchResult &Result) override {
+    if (!Edits)
+      return;
+    transformer::RewriteRule::Case Case =
+        transformer::detail::findSelectedCase(Result, Rule);
+    auto Transformations = Case.Edits(Result);
+    if (!Transformations) {
+      Edits = Transformations.takeError();
+      return;
+    }
+    Edits->append(Transformations->begin(), Transformations->end());
+  }
+
+  RewriteRule Rule;
+
+  // Initialize to a non-error state.
+  Expected<SmallVector<Edit, 1>> Edits = SmallVector<Edit, 1>();
+};
+} // namespace
+
+template <typename T>
+llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
+rewriteDescendantsImpl(const T &Node, RewriteRule Rule,
+                       const MatchResult &Result) {
+  ApplyRuleCallback Callback(std::move(Rule));
+  MatchFinder Finder;
+  Callback.registerMatchers<T>(Result.Nodes, &Finder);
+  Finder.match(Node, *Result.Context);
+  return std::move(Callback.Edits);
+}
+
+EditGenerator transformer::rewriteDescendants(std::string NodeId,
+                                              RewriteRule Rule) {
+  // FIXME: warn or return error if `Rule` contains any `AddedIncludes`, since
+  // these will be dropped.
+  return [NodeId = std::move(NodeId),
+          Rule = std::move(Rule)](const MatchResult &Result)
+             -> llvm::Expected<SmallVector<clang::transformer::Edit, 1>> {
+    const ast_matchers::BoundNodes::IDToNodeMap &NodesMap =
+        Result.Nodes.getMap();
+    auto It = NodesMap.find(NodeId);
+    if (It == NodesMap.end())
+      return llvm::make_error<llvm::StringError>(llvm::errc::invalid_argument,
+                                                 "ID not bound: " + NodeId);
+    if (auto *Node = It->second.get<Decl>())
+      return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
+    if (auto *Node = It->second.get<Stmt>())
+      return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
+    if (auto *Node = It->second.get<TypeLoc>())
+      return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
+
+    return llvm::make_error<llvm::StringError>(
+        llvm::errc::invalid_argument,
+        "type unsupported for recursive rewriting, ID=\"" + NodeId +
+            "\", Kind=" + It->second.getNodeKind().asStringRef());
+  };
+}
+
 void transformer::addInclude(RewriteRule &Rule, StringRef Header,
                              IncludeFormat Format) {
   for (auto &Case : Rule.Cases)
     Case.AddedIncludes.emplace_back(Header.str(), Format);
 }
 
 #ifndef NDEBUG
 // Filters for supported matcher kinds. FIXME: Explicitly list the allowed kinds
 // (all node matcher types except for `QualType` and `Type`), rather than just
 // banning `QualType` and `Type`.

clang/lib/Tooling/Transformer/Transformer.cpp

void Transformer::run(const MatchFinder::MatchResult &Result) {
   transformer::RewriteRule::Case Case =
       transformer::detail::findSelectedCase(Result, Rule);
   auto Transformations = Case.Edits(Result);
   if (!Transformations) {
     Consumer(Transformations.takeError());
     return;
   }
 
-  if (Transformations->empty()) {
-    // No rewrite applied (but no error encountered either).
-    transformer::detail::getRuleMatchLoc(Result).print(
-        llvm::errs() << "note: skipping match at loc ", *Result.SourceManager);
-    llvm::errs() << "\n";
+  if (Transformations->empty())
     return;
-  }
 
   // Group the transformations, by file, into AtomicChanges, each anchored by
   // the location of the first change in that file.
   std::map<FileID, AtomicChange> ChangesByFileID;
   for (const auto &T : *Transformations) {
     auto ID = Result.SourceManager->getFileID(T.Range.getBegin());
     auto Iter = ChangesByFileID
                     .emplace(ID, AtomicChange(*Result.SourceManager,

clang/unittests/Tooling/TransformerTest.cpp

llvm::Optional<std::string> rewrite(StringRef Input) {
     return *ChangedCode;
   }
 
   Transformer::ChangeConsumer consumer() {
     return [this](Expected<AtomicChange> C) {
       if (C) {
         Changes.push_back(std::move(*C));
       } else {
-        consumeError(C.takeError());
+        // FIXME: stash this error rather then printing.
+        llvm::errs() << "Error generating changes: "
+                     << llvm::toString(C.takeError()) << "\n";
         ++ErrorCount;
       }
     };
   }
 
   template <typename R>
   void testRule(R Rule, StringRef Input, StringRef Expected) {
     Transformer T(std::move(Rule), consumer());
TEST_F(TransformerTest, ShrinkTo) {
   std::string Input = "int f(int x) { return x; }";
   std::string Expected = "return x;";
   testRule(makeRule(functionDecl(hasDescendant(returnStmt().bind("return")))
                         .bind("function"),
                     shrinkTo(node("function"), node("return"))),
            Input, Expected);
 }
 
+// Rewrite various Stmts inside a Decl.
+TEST_F(TransformerTest, RewriteDescendantsDeclChangeStmt) {
+  std::string Input =
+      "int f(int x) { int y = x; { int z = x * x; } return x; }";
+  std::string Expected =
+      "int f(int x) { int y = 3; { int z = 3 * 3; } return 3; }";
+  auto InlineX =
+      makeRule(declRefExpr(to(varDecl(hasName("x")))), changeTo(cat("3")));
+  testRule(makeRule(functionDecl(hasName("f")).bind("fun"),
+                    rewriteDescendants("fun", InlineX)),
+           Input, Expected);
+}
+
+// Rewrite various TypeLocs inside a Decl.
+TEST_F(TransformerTest, RewriteDescendantsDeclChangeTypeLoc) {
+  std::string Input = "int f(int *x) { return *x; }";
+  std::string Expected = "char f(char *x) { return *x; }";
+  auto IntToChar = makeRule(typeLoc(loc(qualType(isInteger(), builtinType()))),
+                            changeTo(cat("char")));
+  testRule(makeRule(functionDecl(hasName("f")).bind("fun"),
+                    rewriteDescendants("fun", IntToChar)),
+           Input, Expected);
+}
+
+TEST_F(TransformerTest, RewriteDescendantsStmt) {
+  // Add an unrelated definition to the header that also has a variable named
+  // "x", to test that the rewrite is limited to the scope we intend.
+  appendToHeader(R"cc(int g(int x) { return x; })cc");
+  std::string Input =
+      "int f(int x) { int y = x; { int z = x * x; } return x; }";
+  std::string Expected =
+      "int f(int x) { int y = 3; { int z = 3 * 3; } return 3; }";
+  auto InlineX =
+      makeRule(declRefExpr(to(varDecl(hasName("x")))), changeTo(cat("3")));
+  testRule(makeRule(functionDecl(hasName("f"), hasBody(stmt().bind("body"))),
+                    rewriteDescendants("body", InlineX)),
+           Input, Expected);
+}
+
+TEST_F(TransformerTest, RewriteDescendantsStmtWithAdditionalChange) {
+  std::string Input =
+      "int f(int x) { int y = x; { int z = x * x; } return x; }";
+  std::string Expected =
+      "int newName(int x) { int y = 3; { int z = 3 * 3; } return 3; }";
+  auto InlineX =
+      makeRule(declRefExpr(to(varDecl(hasName("x")))), changeTo(cat("3")));
+  testRule(
+      makeRule(
+          functionDecl(hasName("f"), hasBody(stmt().bind("body"))).bind("f"),
+          flatten(changeTo(name("f"), cat("newName")),
+                  rewriteDescendants("body", InlineX))),
+      Input, Expected);
+}
+
+TEST_F(TransformerTest, RewriteDescendantsTypeLoc) {
+  std::string Input = "int f(int *x) { return *x; }";
+  std::string Expected = "int f(char *x) { return *x; }";
+  auto IntToChar =
+      makeRule(typeLoc(loc(qualType(isInteger(), builtinType()))).bind("loc"),
+               changeTo(cat("char")));
+  testRule(
+      makeRule(functionDecl(hasName("f"),
+                            hasParameter(0, varDecl(hasTypeLoc(
+                                                typeLoc().bind("parmType"))))),
+               rewriteDescendants("parmType", IntToChar)),
+      Input, Expected);
+}
+
+TEST_F(TransformerTest, RewriteDescendantsReferToParentBinding) {
+  std::string Input =
+      "int f(int p) { int y = p; { int z = p * p; } return p; }";
+  std::string Expected =
+      "int f(int p) { int y = 3; { int z = 3 * 3; } return 3; }";
+  std::string VarId = "var";
+  auto InlineVar = makeRule(declRefExpr(to(varDecl(equalsBoundNode(VarId)))),
+                            changeTo(cat("3")));
+  testRule(makeRule(functionDecl(hasName("f"),
+                                 hasParameter(0, varDecl().bind(VarId)))
+                        .bind("fun"),
+                    rewriteDescendants("fun", InlineVar)),
+           Input, Expected);
+}
+
+TEST_F(TransformerTest, RewriteDescendantsUnboundNode) {
+  std::string Input =
+      "int f(int x) { int y = x; { int z = x * x; } return x; }";
+  auto InlineX =
+      makeRule(declRefExpr(to(varDecl(hasName("x")))), changeTo(cat("3")));
+  Transformer T(makeRule(functionDecl(hasName("f")),
+                         rewriteDescendants("UNBOUND", InlineX)),
+                consumer());
+  T.registerMatchers(&MatchFinder);
+  EXPECT_FALSE(rewrite(Input));
+  EXPECT_THAT(Changes, IsEmpty());
+  EXPECT_EQ(ErrorCount, 1);
+}
+
+TEST_F(TransformerTest, RewriteDescendantsInvalidNodeType) {
+  std::string Input =
+      "int f(int x) { int y = x; { int z = x * x; } return x; }";
+  auto IntToChar =
+      makeRule(qualType(isInteger(), builtinType()), changeTo(cat("char")));
+  Transformer T(
+      makeRule(functionDecl(
+                   hasName("f"),
+                   hasParameter(0, varDecl(hasType(qualType().bind("type"))))),
+               rewriteDescendants("type", IntToChar)),
+      consumer());
+  T.registerMatchers(&MatchFinder);
+  EXPECT_FALSE(rewrite(Input));
+  EXPECT_THAT(Changes, IsEmpty());
+  EXPECT_EQ(ErrorCount, 1);
+}
+
 TEST_F(TransformerTest, InsertBeforeEdit) {
   std::string Input = R"cc(
     int f() {
       return 7;
     }
   )cc";
   std::string Expected = R"cc(
     int f() {
TEST_F(TransformerTest, MultipleFiles) {
   EXPECT_THAT(Changes[1].getRemovedHeaders(), IsEmpty());
   UpdatedCode = clang::tooling::applyAllReplacements(
       Source, Changes[1].getReplacements());
   ASSERT_TRUE(static_cast<bool>(UpdatedCode))
       << "Could not update code: " << llvm::toString(UpdatedCode.takeError());
   EXPECT_EQ(format(*UpdatedCode), format(R"cc(#include "input.h"
                         ;)cc"));
 }
 } // namespace