[libTooling] In Transformer, generalize `applyFirst` to admit rules with incompatible matchers.

[ymandel]

Summary

This patch removes an (artificial) limitation of applyFirst, which requires
that all of the rules' matchers can be grouped together in a single anyOf().
This change generalizes the code to group the matchers into separate anyOfs
based on compatibility. Correspondingly, buildMatcher is changed to
buildMatchers, to allow for returning a set of matchers rather than just one.

[ymandel]

fix comment.

[gribozavr]

clang/lib/Tooling/Refactoring/Transformer.cpp

83–86

I'd find it more readable to s/A/MaybeBase/ and s/B/MaybeDerived/.

88–89

I don't understand how Matcher<Base> implicitly converts to Matcher<Derived> -- is the order correct?

88–89

A.isSame(TypeKind) && B.isSame(QualKind) -- is the order correct here?

QualType is a more general kind than Type. That's why Type implicitly converts to QualType. Therefore, QualType is the "base", and Type is "derived". Therefore:

A.isSame(QualKind) && B.isSame(TypeKind)

AKA

MaybeBase.isSame(QualKind) && MaybeDerived.isSame(TypeKind)

88–89

WDYT about moving this API into a static method on ASTNodeKind, and then calling it from DynTypedMatcher::canConvertTo, deduplicating the logic?

89

"CompatibleCasesBucket" ?

93

Would it be easier to implement this algorithm using ASTNodeKind::getMostDerivedCommonAncestor instead of isBaseOf?

Go over all buckets, for each bucket check if common ancestor between the bucket kind and the new case kind is not none. If it is not none, insert the new case into that bucket, and update bucket's kind to the new common ancestor kind.

You could also go as far as setting the bucket's kind to always the the root of the corresponding kind hierarchy (TemplateArgument, TemplateName, Decl, Stmt etc.), since given enough diverse cases, the bucket kind will converge to the root kind.

102

"sub/super class" part does not seem correct to me -- it must be one or the other (if it can be either, we would only have one bucket for everything).

WDYT about

"Adds the new case to the bucket that contains compatible cases."

I don't think we need to explain the algorithm in the contract.

104

I would find it more readable to s/CaseId/NewCaseId/ and s/Case/NewCase/. Up to you.

106

I don't understand why it is going backwards.

109

The comment merely repeats the code -- consider removing it.

110

If isBaseOf(Bucket.Kind, CaseKind) is true, then Bucket.Kind is the more general type. So I don't understand why we are changing the bucket kind to the more specific one, CaseKind.

clang/unittests/Tooling/TransformerTest.cpp

506

If this test and the test below are testing rule ordering only, I find them to have too much unrelated detail. We could do something simpler and more self-contained like:

input:

void f1();
void f2();
void call_f1() { f1(); }
void call_f2() { f2(); }

replaceF1 = makeRule(
  callExpr(callee(functionDecl(hasName("f1"))),
  change(text("REPLACE_F1"))
)

replaceF1orF2 = makeRule(
  callExpr(callee(functionDecl(hasAnyName("f1", "f2"))),
  change(text("REPLACE_F1_OR_F2"))
)

applyFirst({replaceF1, replaceF1orF2})
=> check that the output is =>
void f1();
void f2();
void call_f1() { REPLACE_F1; }
void call_f2() { REPLACE_F1_OR_F2; }

applyFirst({replaceF1orF2, replaceF1})
=> check that the output is =>
void f1();
void f2();
void call_f1() { REPLACE_F1_OR_F2; }
void call_f2() { REPLACE_F1_OR_F2; }

Up to you.

599

Ditto, I think we can make a simpler and more self-contained test:

input:

void f1();
void f2();
void call_f1() { f1(); }

stmtRule = makeRule(
  callExpr(callee(functionDecl(hasName("f1"))),
  change(text("STMT_RULE")))

declRule = makeRule(
  functionDecl(hasName("f2")).bind("fun"),
  change(name("fun"), text("DECL_RULE")))

rule = applyFirst({stmtRule, declRule})

expected output:

void f1();
void DECL_RULE();
void call_f1() { STMT_RULE(); }

[ymandel]

Rewrote the code and tests.

[ymandel]

Thanks for your detailed and helpful feedback.

clang/lib/Tooling/Refactoring/Transformer.cpp

93

Based on our discussion, I've drastically simplified the code. As per our discussion: since each matcher must be a node matcher, we only have the root AST types to consider. Therefore, there's no need for comparison of relative levels in the kind hierarchy -- we simply map each matcher to a root kind and then put it in that bucket. This lets us remove lots of custom code.

clang/unittests/Tooling/TransformerTest.cpp

506

Much nicer. Thanks!

599

I kept a little of the complexity of the old test -- I still have a third rule with the same kind as the first to make sure rules are bucketed together even when separated by different rule.

[gribozavr]

Nice simplification, thanks!

clang/lib/Tooling/Refactoring/Transformer.cpp

127

unordered_map?

[ymandel]

I was going to add a test for Type/QualType and realized that they don't carry any source location info. Therefore, I don't think they belong as top-level matchers for rewrite rules. Instead, users should use typeLoc(loc(<type matcher here>). Therefore, the logic of getKind can be eliminated in favor of using K.getSupportedKind() directly. However, that means we'll need to keep them out of the collection of matchers that we're processing.

For that, I propose either we ban them in buildMatchers() or we detect them and wrap them in typeLoc(loc(<type matcher here>). I'm fine with either one, but prefer the latter. WDYT?

clang/lib/Tooling/Refactoring/Transformer.cpp

127

fails because ASTNodeKind doesn't have a hash function. Which is odd since there's an obvious one we could define, but doesn't seem worth doing just for here.

[gribozavr]

In D65877#1625493, @ymandel wrote:

I was going to add a test for Type/QualType and realized that they don't carry any source location info. Therefore, I don't think they belong as top-level matchers for rewrite rules.

Agreed.

Instead, users should use typeLoc(loc(<type matcher here>). Therefore, the logic of getKind can be eliminated in favor of using K.getSupportedKind() directly. However, that means we'll need to keep them out of the collection of matchers that we're processing.

For that, I propose either we ban them in buildMatchers() or we detect them and wrap them in typeLoc(loc(<type matcher here>). I'm fine with either one, but prefer the latter. WDYT?

I'd prefer we ban them completely, and let the user wrap them manually if they need to. While some users would appreciate the ergonomics, I think AST matchers are complicated even without us adding more implicit behavior on top.

[ymandel]

Bans qualtype and type and adds corresponding comments and test.

[ymandel]

In D65877#1625616, @gribozavr wrote:

I'd prefer we ban them completely, and let the user wrap them manually if they need to. While some users would appreciate the ergonomics, I think AST matchers are complicated even without us adding more implicit behavior on top.

Done. I came to the same conclusion once I started implementing. Less (magic) is more, in this case.

[gribozavr]

clang/lib/Tooling/Refactoring/Transformer.cpp

132

Returning an empty vector is a valid API choice, but why not assert instead? If an empty vector is returned, unsupported matchers are silently ignored instead of being diagnosed.

[ymandel]

Changed early return to assertion; updated test.

[ymandel]

clang/lib/Tooling/Refactoring/Transformer.cpp

132

Good point. I generally dislike assertions, but at this point the caller is passing a malformed-rule and it is not the place for returning errors. If we plug this support into a UI, we can add filters on the front end that fail nicely and return error messages rather than die.

clang/include/clang/Tooling/Refactoring/Transformer.h

 ///   auto R = makeRule(callExpr(callee(functionDecl(hasName("foo")))),
 ///            change(text("bar()")));
 ///   AddInclude(R, "path/to/bar_header.h");
 ///   AddInclude(R, "vector", IncludeFormat::Angled);
 /// \endcode
 void addInclude(RewriteRule &Rule, llvm::StringRef Header,
                 IncludeFormat Format = IncludeFormat::Quoted);
 
-/// Applies the first rule whose pattern matches; other rules are ignored.
-///
-/// N.B. All of the rules must use the same kind of matcher (that is, share a
-/// base class in the AST hierarchy).  However, this constraint is caused by an
-/// implementation detail and should be lifted in the future.
+/// Applies the first rule whose pattern matches; other rules are ignored.  If
+/// the matchers are independent then order doesn't matter. In that case,
+/// `applyFirst` is simply joining the set of rules into one.
 //
 // `applyFirst` is like an `anyOf` matcher with an edit action attached to each
 // of its cases. Anywhere you'd use `anyOf(m1.bind("id1"), m2.bind("id2"))` and
 // then dispatch on those ids in your code for control flow, `applyFirst` lifts
 // that behavior to the rule level.  So, you can write `applyFirst({makeRule(m1,
 // action1), makeRule(m2, action2), ...});`
 //
 // For example, consider a type `T` with a deterministic serialization function,

 /// 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`.
 namespace detail {
 /// Builds a single matcher for the rule, covering all of the rule's cases.
+/// Only supports Rules whose cases' matchers all share the same base "kind"
+/// (`Stmt`, `Decl`, etc.)  Deprecated: use `buildMatchers` instead, which
+/// supports mixing matchers of different kinds.
 ast_matchers::internal::DynTypedMatcher buildMatcher(const RewriteRule &Rule);
 
+/// Builds a set of matchers that cover the rule (one for each distinct matcher
+/// base kind: Stmt, Decl, etc.)
+std::vector<ast_matchers::internal::DynTypedMatcher>
+buildMatchers(const RewriteRule &Rule);
+
 /// Returns the \c Case of \c Rule that was selected in the match result.
 /// Assumes a matcher built with \c buildMatcher.
 const RewriteRule::Case &
 findSelectedCase(const ast_matchers::MatchFinder::MatchResult &Result,
                  const RewriteRule &Rule);
 
 /// A source "transformation," represented by a character range in the source to
 /// be replaced and a corresponding replacement string.

clang/lib/Tooling/Refactoring/Transformer.cpp

 }
 
 void tooling::addInclude(RewriteRule &Rule, StringRef Header,
                          IncludeFormat Format) {
   for (auto &Case : Rule.Cases)
     Case.AddedIncludes.emplace_back(Header.str(), Format);
 }
 
-// Determines whether A is a base type of B in the class hierarchy, including
-// the implicit relationship of Type and QualType.
-static bool isBaseOf(ASTNodeKind A, ASTNodeKind B) {
+// Gets the kind corresponding to the given matcher for assigning it to bucket.
+// Requires that the `M` is a node matcher.
+static ASTNodeKind getKind(const DynTypedMatcher &M) {
+  ASTNodeKind K = M.getSupportedKind();
   static auto TypeKind = ASTNodeKind::getFromNodeKind<Type>();
   static auto QualKind = ASTNodeKind::getFromNodeKind<QualType>();
-  /// Mimic the implicit conversions of Matcher<>.
-  /// - From Matcher<Type> to Matcher<QualType>
-  /// - From Matcher<Base> to Matcher<Derived>
-  return (A.isSame(TypeKind) && B.isSame(QualKind)) || A.isBaseOf(B);
-}
-
-// Try to find a common kind to which all of the rule's matchers can be
-// converted.
-static ASTNodeKind
-findCommonKind(const SmallVectorImpl<RewriteRule::Case> &Cases) {
-  assert(!Cases.empty() && "Rule must have at least one case.");
-  ASTNodeKind JoinKind = Cases[0].Matcher.getSupportedKind();
-  // Find a (least) Kind K, for which M.canConvertTo(K) holds, for all matchers
-  // M in Rules.
-  for (const auto &Case : Cases) {
-    auto K = Case.Matcher.getSupportedKind();
-    if (isBaseOf(JoinKind, K)) {
-      JoinKind = K;
-      continue;
-    }
-    if (K.isSame(JoinKind) || isBaseOf(K, JoinKind))
-      // JoinKind is already the lowest.
-      continue;
-    // K and JoinKind are unrelated -- there is no least common kind.
-    return ASTNodeKind();
-  }
-  return JoinKind;
+  // Type and QualType can be put together, but otherwise each root type is
+  // distinct.
+  if (K.isSame(TypeKind)) return QualKind;
+  return K;
 }
 
 // Binds each rule's matcher to a unique (and deterministic) tag based on
-// `TagBase`.
-static std::vector<DynTypedMatcher>
-taggedMatchers(StringRef TagBase,
-               const SmallVectorImpl<RewriteRule::Case> &Cases) {
+// `TagBase` and the id paired with the case.
+static std::vector<DynTypedMatcher> taggedMatchers(
+    StringRef TagBase,
+    const SmallVectorImpl<std::pair<size_t, RewriteRule::Case>> &Cases) {
   std::vector<DynTypedMatcher> Matchers;
   Matchers.reserve(Cases.size());
-  size_t count = 0;
   for (const auto &Case : Cases) {
-    std::string Tag = (TagBase + Twine(count)).str();
-    ++count;
-    auto M = Case.Matcher.tryBind(Tag);
+    std::string Tag = (TagBase + Twine(Case.first)).str();
+    auto M = Case.second.Matcher.tryBind(Tag);
     assert(M && "RewriteRule matchers should be bindable.");
     Matchers.push_back(*std::move(M));
   }
   return Matchers;
 }
 
 // Simply gathers the contents of the various rules into a single rule. The
 // actual work to combine these into an ordered choice is deferred to matcher
 // registration.
 RewriteRule tooling::applyFirst(ArrayRef<RewriteRule> Rules) {
   RewriteRule R;
   for (auto &Rule : Rules)
     R.Cases.append(Rule.Cases.begin(), Rule.Cases.end());
   return R;
 }
 
-static DynTypedMatcher joinCaseMatchers(const RewriteRule &Rule) {
-  assert(!Rule.Cases.empty() && "Rule must have at least one case.");
-  if (Rule.Cases.size() == 1)
-    return Rule.Cases[0].Matcher;
+std::vector<DynTypedMatcher>
+tooling::detail::buildMatchers(const RewriteRule &Rule) {
+  // Map the cases into buckets of matchers -- one for each "root" AST kind,
+  // which guarantees that they can be combined in a single anyOf matcher. Each
+  // case is paired with an identifying number that is converted to a string id
+  // in `taggedMatchers`.
+  std::map<ASTNodeKind, SmallVector<std::pair<size_t, RewriteRule::Case>, 1>>
+      Buckets;
+  const SmallVectorImpl<RewriteRule::Case> &Cases = Rule.Cases;
+  for (int I = 0, N = Cases.size(); I < N; ++I)
+    Buckets[getKind(Cases[I].Matcher)].emplace_back(I, Cases[I]);
 
-  auto CommonKind = findCommonKind(Rule.Cases);
-  assert(!CommonKind.isNone() && "Cases must have compatible matchers.");
-  return DynTypedMatcher::constructVariadic(
-      DynTypedMatcher::VO_AnyOf, CommonKind, taggedMatchers("Tag", Rule.Cases));
+  std::vector<DynTypedMatcher> Matchers;
+  for (const auto &Bucket : Buckets) {
+    DynTypedMatcher M = DynTypedMatcher::constructVariadic(
+        DynTypedMatcher::VO_AnyOf, Bucket.first,
+        taggedMatchers("Tag", Bucket.second));
+    M.setAllowBind(true);
+    // `tryBind` is guaranteed to succeed, because `AllowBind` was set to true.
+    Matchers.push_back(*M.tryBind(RewriteRule::RootID));
+  }
+  return Matchers;
 }
 
 DynTypedMatcher tooling::detail::buildMatcher(const RewriteRule &Rule) {
-  DynTypedMatcher M = joinCaseMatchers(Rule);
-  M.setAllowBind(true);
-  // `tryBind` is guaranteed to succeed, because `AllowBind` was set to true.
-  return *M.tryBind(RewriteRule::RootID);
+  std::vector<DynTypedMatcher> Ms = buildMatchers(Rule);
+  assert(Ms.size() == 1 && "Cases must have compatible matchers.");
+  return Ms[0];
 }
 
 // Finds the case that was "selected" -- that is, whose matcher triggered the
 // `MatchResult`.
 const RewriteRule::Case &
 tooling::detail::findSelectedCase(const MatchResult &Result,
                                   const RewriteRule &Rule) {
   if (Rule.Cases.size() == 1)
     return Rule.Cases[0];
 
   auto &NodesMap = Result.Nodes.getMap();
   for (size_t i = 0, N = Rule.Cases.size(); i < N; ++i) {
     std::string Tag = ("Tag" + Twine(i)).str();
     if (NodesMap.find(Tag) != NodesMap.end())
       return Rule.Cases[i];
   }
   llvm_unreachable("No tag found for this rule.");
 }
 
 constexpr llvm::StringLiteral RewriteRule::RootID;
 
 void Transformer::registerMatchers(MatchFinder *MatchFinder) {
-  MatchFinder->addDynamicMatcher(tooling::detail::buildMatcher(Rule), this);
+  for (auto &Matcher : tooling::detail::buildMatchers(Rule))
+    MatchFinder->addDynamicMatcher(Matcher, this);
 }
 
 void Transformer::run(const MatchResult &Result) {
   if (Result.Context->getDiagnostics().hasErrorOccurred())
     return;
 
   // Verify the existence and validity of the AST node that roots this rule.
   auto &NodesMap = Result.Nodes.getMap();
if (auto Err = AC.replace(*Result.SourceManager, T.Range, T.Replacement)) {
       Consumer(std::move(Err));
       return;
     }
   }
 
   for (const auto &I : Case.AddedIncludes) {
     auto &Header = I.first;
     switch (I.second) {
-      case IncludeFormat::Quoted:
-        AC.addHeader(Header);
-        break;
-      case IncludeFormat::Angled:
-        AC.addHeader((llvm::Twine("<") + Header + ">").str());
-        break;
     }
   }
 
   Consumer(std::move(AC));
 }

clang/unittests/Tooling/TransformerTest.cpp

std::string Expected = R"cc(
     int x = PROTO.foo();
     int y = flag.GetProto().foo();
     int f(string s) { return REPLACED; }
   )cc";
 
   testRule(applyFirst({ruleStrlenSize(), FlagRule}), Input, Expected);
 }
 
-// Version of ruleStrlenSizeAny that inserts a method with a different name than
-// ruleStrlenSize, so we can tell their effect apart.
-RewriteRule ruleStrlenSizeDistinct() {
-  StringRef S;
-  return makeRule(
-      callExpr(callee(functionDecl(hasName("strlen"))),
-               hasArgument(0, cxxMemberCallExpr(
-                                  on(expr().bind(S)),
-                                  callee(cxxMethodDecl(hasName("c_str")))))),
-      change(text("DISTINCT")));
-}
-
 TEST_F(TransformerTest, OrderedRuleRelated) {
   std::string Input = R"cc(
-    namespace foo {
-    struct mystring {
-      char* c_str();
-    };
-    int f(mystring s) { return strlen(s.c_str()); }
-    }  // namespace foo
-    int g(string s) { return strlen(s.c_str()); }
+    void f1();
+    void f2();
+    void call_f1() { f1(); }
+    void call_f2() { f2(); }
   )cc";
   std::string Expected = R"cc(
-    namespace foo {
-    struct mystring {
-      char* c_str();
-    };
-    int f(mystring s) { return DISTINCT; }
-    }  // namespace foo
-    int g(string s) { return REPLACED; }
+    void f1();
+    void f2();
+    void call_f1() { REPLACE_F1; }
+    void call_f2() { REPLACE_F1_OR_F2; }
   )cc";
 
-  testRule(applyFirst({ruleStrlenSize(), ruleStrlenSizeDistinct()}), Input,
-           Expected);
+  RewriteRule ReplaceF1 =
+      makeRule(callExpr(callee(functionDecl(hasName("f1")))),
+               change(text("REPLACE_F1")));
+  RewriteRule ReplaceF1OrF2 =
+      makeRule(callExpr(callee(functionDecl(hasAnyName("f1", "f2")))),
+               change(text("REPLACE_F1_OR_F2")));
+  testRule(applyFirst({ReplaceF1, ReplaceF1OrF2}), Input, Expected);
 }
 
-// Change the order of the rules to get a different result.
+// Change the order of the rules to get a different result. When `ReplaceF1OrF2`
+// comes first, it applies for both uses, so `ReplaceF1` never applies.
 TEST_F(TransformerTest, OrderedRuleRelatedSwapped) {
   std::string Input = R"cc(
-    namespace foo {
-    struct mystring {
-      char* c_str();
-    };
-    int f(mystring s) { return strlen(s.c_str()); }
-    }  // namespace foo
-    int g(string s) { return strlen(s.c_str()); }
-  )cc";
-  std::string Expected = R"cc(
-    namespace foo {
-    struct mystring {
-      char* c_str();
-    };
-    int f(mystring s) { return DISTINCT; }
-    }  // namespace foo
-    int g(string s) { return DISTINCT; }
-  )cc";
+    void f1();
+    void f2();
+    void call_f1() { f1(); }
+    void call_f2() { f2(); }
+  )cc";
+  std::string Expected = R"cc(
+    void f1();
+    void f2();
+    void call_f1() { REPLACE_F1_OR_F2; }
+    void call_f2() { REPLACE_F1_OR_F2; }
+  )cc";
+
+  RewriteRule ReplaceF1 =
+      makeRule(callExpr(callee(functionDecl(hasName("f1")))),
+               change(text("REPLACE_F1")));
+  RewriteRule ReplaceF1OrF2 =
+      makeRule(callExpr(callee(functionDecl(hasAnyName("f1", "f2")))),
+               change(text("REPLACE_F1_OR_F2")));
+  testRule(applyFirst({ReplaceF1OrF2, ReplaceF1}), Input, Expected);
+}
+
+// Verify that a set of rules whose matchers have different base kinds works
+// properly, including that `applyFirst` produces multiple matchers.  We test
+// two different kinds of rules: Expr and Decl. We place the Decl rule in the
+// middle to test that `buildMatchers` works even when the kinds aren't grouped
+// together.
+TEST_F(TransformerTest, OrderedRuleMultipleKinds) {
+  std::string Input = R"cc(
+    void f1();
+    void f2();
+    void call_f1() { f1(); }
+    void call_f2() { f2(); }
+  )cc";
+  std::string Expected = R"cc(
+    void f1();
+    void DECL_RULE();
+    void call_f1() { REPLACE_F1; }
+    void call_f2() { REPLACE_F1_OR_F2; }
+  )cc";
+
+  RewriteRule ReplaceF1 =
+      makeRule(callExpr(callee(functionDecl(hasName("f1")))),
+               change(text("REPLACE_F1")));
+  RewriteRule ReplaceF1OrF2 =
+      makeRule(callExpr(callee(functionDecl(hasAnyName("f1", "f2")))),
+               change(text("REPLACE_F1_OR_F2")));
+  RewriteRule DeclRule = makeRule(functionDecl(hasName("f2")).bind("fun"),
+                                  change(name("fun"), text("DECL_RULE")));
 
-  testRule(applyFirst({ruleStrlenSizeDistinct(), ruleStrlenSize()}), Input,
-           Expected);
+  RewriteRule Rule = applyFirst({ReplaceF1, DeclRule, ReplaceF1OrF2});
+  EXPECT_EQ(tooling::detail::buildMatchers(Rule).size(), 2UL);
+  testRule(Rule, Input, Expected);
 }
 
 //
 // Negative tests (where we expect no transformation to occur).
 //
 
 // Tests for a conflict in edits from a single match for a rule.
 TEST_F(TransformerTest, TextGeneratorFailure) {
TEST_F(TransformerTest, OverlappingEditsInRule) {
   StringRef O = "O", L = "L";
   Transformer T(makeRule(binaryOperator(hasLHS(expr().bind(L))).bind(O),
                          {change(node(O), text("DELETE_OP")),
                           change(node(L), text("DELETE_LHS"))}),
                 consumer());
   T.registerMatchers(&MatchFinder);
   EXPECT_FALSE(rewrite(Input));
   EXPECT_THAT(Changes, IsEmpty());
   EXPECT_EQ(ErrorCount, 1);
 }
 
 // Tests for a conflict in edits across multiple matches (of the same rule).
 TEST_F(TransformerTest, OverlappingEditsMultipleMatches) {
   std::string Input = "int conflictOneRule() { return -7; }";
   // Try to change the whole binary-operator expression AND one its operands:
   StringRef E = "E";
   Transformer T(makeRule(expr().bind(E), change(node(E), text("DELETE_EXPR"))),