[LibTooling] Add support to Transformer for composing rules as an ordered choice.

[ymandel]

Summary

This revision updates RewriteRule to support multiple subrules that are interpreted as an ordered-choice. With this feature, users can write the rules that appear later in the list of subrules knowing that previous rules' patterns *have not matched*, freeing them from reasoning about those cases in the current pattern.

[ilya-biryukov]

• Could you provide a few real-world motivating examples? Especially interested in cases that were complicated before and are easy to do now?
• Do we expect most the rules to be written using the new API or is this something that's gonna be used in 5-10% of the cases?
• Could we consider expressing the CompositeRewriteRule as a RewriteRule itself? That might require extending the RewriteRule abstraction, but the mental model that makes sense to me is: a rewrite rule matches some AST nodes and applies replacements to them. A CompositeRewriteRule seems to match the same model, despite the fact it contains other rules. Would be nice if we could make this fact internal to the implementation.

Also a bit uneasy about the naming. Composite suggests the individual rules compose one after another, while in practice only one alternative is chosen.

[ymandel]

In D61335#1488212, @ilya-biryukov wrote:

• Could you provide a few real-world motivating examples? Especially interested in cases that were complicated before and are easy to do now?

Sure, below are some examples based on actual tidies I've written (although not released). Let me know whether you think any of these should be expressed in the comments:

EXAMPLE 1
Consider a type T with a deterministic serialization function, serialize(). For performance reasons, we would like to make it non deterministic. Therefore, we want to drop the expectation that a.serialize() = b.serialize() iff a = b (although we’ll maintain deserialize(a.serialize()) = a).

Let’s assume this comes up in testing. We have three cases to consider:

EXPECT_EQ(a.serialize(), b.serialize());
EXPECT_EQ(a, b.serialize());
EXPECT_EQ(a.serialize(), b);

With ordered choice, you can encode the above directly into matchers and then compose them into an ordered choice rule. Without it, you’d have to write these as

EXPECT_EQ(a.serialize(), b.serialize());
EXPECT_EQ(a, b.serialize());  // where a != a’.serialize()
EXPECT_EQ(a.serialize(), b);  // where b != b’.serialize()

where the constraints in the comments are explicitly in the matchers.

EXAMPLE 2
Consider patterns of the form

absl::WrapUnique(e.release())

where e is an expression of type std::unique_ptr<...>. This pattern was necessary in gcc for certain circumstances relating to upcasting the value type of the unique_ptr. It is not necessary in clang, and so should be removed.

In some cases, it should be rewritten to e and sometimes to std::move(e), depending on the value category of e and the context (the expression of a return statement or not). That is, there are two cases:
absl::WrapUnique(e.release()) rewrites to e, if e is an r/x-value OR the call appears as a return expression,
absl::WrapUnique(e.release()) rewrites to std::move(e).
With ordered choice, the second case is written plainly (that is, just translate that expression to a matcher). Without it, you need to further express: unless e is an r/x-value OR the call appears as a return expression.

EXAMPLE 3
More generally, anywhere you’d use anyOf(m1.bind(“m1”), m2.bind(“m2”)) and then dispatch on those tags in your code to decide what to do, we’ll lift that behavior to the rule level, so you can write
makeOrderedRule({

makeRule(m1, action1), makeRule(m2, action2), …

});

• Do we expect most the rules to be written using the new API or is this something that's gonna be used in 5-10% of the cases?

I'd expect higher than 10% but not the majority of cases. However, given that this semantics exactly matches that of anyOf, it may well be more common than I expect.

• Could we consider expressing the CompositeRewriteRule as a RewriteRule itself? That might require extending the RewriteRule abstraction, but the mental model that makes sense to me is: a rewrite rule matches some AST nodes and applies replacements to them. A CompositeRewriteRule seems to match the same model, despite the fact it contains other rules. Would be nice if we could make this fact internal to the implementation.

Also a bit uneasy about the naming. Composite suggests the individual rules compose one after another, while in practice only one alternative is chosen.

Great points! I'm fine with collapsing the types into one. As you can see from line 260 in Transformer.h, we're already folding the single rule into the composite rule. As for naming, agreed, but does that concern drop away once we have only a single RewriteRule definition?

[ilya-biryukov]

As for naming, agreed, but does that concern drop away once we have only a single RewriteRule definition?

Sure, that won't be an issue.

The use-cases make sense, thanks for the examples. Could you add one or two to the code? Would probably make sense to express them in code as matchers, rather than explaining what we're trying to do in a natural language.

Let's proceed with making RewriteRule the vocabulary type that we use for transformations like this if we both agree that's a good idea.
There are obviously multiple ways to tackle this, which one you had in mind?

[ymandel]

In D61335#1489680, @ilya-biryukov wrote:

As for naming, agreed, but does that concern drop away once we have only a single RewriteRule definition?

Sure, that won't be an issue.

The use-cases make sense, thanks for the examples. Could you add one or two to the code? Would probably make sense to express them in code as matchers, rather than explaining what we're trying to do in a natural language.

Sounds good, will do.

Let's proceed with making RewriteRule the vocabulary type that we use for transformations like this if we both agree that's a good idea.
There are obviously multiple ways to tackle this, which one you had in mind?

Something like this, although if you have a better name than RewriteAction I'm open to alternatives. e.g. RewriteCase?

struct RewriteAction {
  SmallVector<ASTEdit, 1> Edits;
  TextGenerator Explanation;
};

struct RewriteRule {
  ast_matchers::internal::DynTypedMatcher Matcher;
  std::vector<RewriteAction> Actions;
  static constexpr llvm::StringLiteral RootId = "___root___";
};

Or, nest the definition:

struct RewriteRule {
  struct Action {
    SmallVector<ASTEdit, 1> Edits;
    TextGenerator Explanation;
  };

  ast_matchers::internal::DynTypedMatcher Matcher;
  std::vector<Action> Actions;

  static constexpr llvm::StringLiteral RootId = "___root___";
};

[ymandel]

Gentle ping...

[ilya-biryukov]

Sorry for the delay.
I personally like the RewriteRule::Action best. Allows to use a rather common term, while still avoiding any possible confusion.

[ymandel]

Folded CompositeRewriteRule into RewriteRule and added examples to comments.

[ymandel]

In D61335#1495324, @ilya-biryukov wrote:

Sorry for the delay.
I personally like the RewriteRule::Action best. Allows to use a rather common term, while still avoiding any possible confusion.

I tried going with RewriteRule::Action (it was my preference as well), but found that it didn't work well once I tried folding the composite rules into RewriteRule. The problem is that the Action structure forces you to eagerly join the matchers (which is what my first diff did). But then it doesn't work to join multiple rules that themselves were built with makeOrderedRule. Previously, this was impossible because they had different types, but now a user could conceivably do this. So, I changed the implementation build the joined matcher later. RewriteRule now just stores all of the (sub)rules in a single list, and makeOrderedRule is a trivial merge. The real work is done at registerMatchers()-time where we build the joined matcher for the whole rule. But, this means keeping the whole (sub)rule around, not just the Action part.

Alternatives I considered:

1. We could use the Action structure inside Transformer -- instead of storing a RewriteRule, we could simply store a single matcher and vector of Action. In the constructor, we would call buildMatcher(Rule) and then copy only the action parts from the rules. However, I don't think this added complexity will gain us anything other than a structure which more faithfully reflects the control flow -- the matchers in each case are "dead" once we build the joined matcher, and the Action approach would reflect that.

2. We could add more structure to Case, like:

struct RewriteRule {
  struct Action {
    SmallVector<ASTEdit, 1> Edits;
    TextGenerator Explanation;
  };
  struct Case {
    ast_matchers::internal::DynTypedMatcher Matcher;
    Action A;
  };
  std::vector<Cases> Cases;
};

[ilya-biryukov]

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

196 ↗

(On Diff #198811)

All of the rules must use the same kind of matcher

Could you elaborate why we want this restriction?
Why they can't be of different kinds?

It feels ok to have transformations to completely unrelated nodes and still apply the first one.

224 ↗

(On Diff #198811)

Why would we need braces around each call? Aren't they a rewrite rule in themselves?

232 ↗

(On Diff #198811)

Any ideas for a better name? pickFirst or applyFirst?

240 ↗

(On Diff #198811)

Could they be made private? If not, why?

247 ↗

(On Diff #198811)

s/Action/Case? Or am I missing something?

clang/lib/Tooling/Refactoring/Transformer.cpp

182 ↗

(On Diff #198811)

NIT: maybe name it isBaseOf? When talking about class hierarchies, using 'base' and 'derived' is a common convention.

250 ↗

(On Diff #198811)

I wonder if there a better way to construct an anyOf matcher that can tell which case matched...
It looks to be the reason for a more complicated interface on the transformer side, but I'm not sure there's a way out of it.

Any ideas?

[ymandel]

Agreed on all the comments -- just one question:

clang/lib/Tooling/Refactoring/Transformer.cpp

250 ↗

(On Diff #198811)

I don't quite follow. Which interface complication are you referring to? FWIW, the reason the code here doesn't just use the anyOf() matches is that it doesn't take a vector -- it only has a variadic form.

[ymandel]

Response to comments.

[ymandel]

Thanks for the review. PTAL.

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

196 ↗

(On Diff #198811)

Agreed. The problem is purely from the implementation perspective. Since anyOf() enforces this restriction, I need to either

1. pass it on to the user
2. infer the base kind of each matcher and place them in the appropriate bucket.

I figured for a first pass, we'd go with 1. if you disagree, I can add the logic to bucket them and thereby support arbitrary combinations. FWIW, I think it's a desirable feature, so its not wasted work. its just a matter of splitting up the work.

224 ↗

(On Diff #198811)

typo. thanks!

232 ↗

(On Diff #198811)

Yes, those are both better. Went w/ applyFirst. Also considered applyFirstMatch but not sure that buys much clarity

240 ↗

(On Diff #198811)

I tried to clarify this. But, I'm also fine splitting these three into a separate header file or moving them to the bottom of this one. They're only exposed at all because TransformerTidy lives in a different directory and namespace. WDYT?

[ilya-biryukov]

The implementation LG, thanks! Just a few NITs and comments about the public interface and the comments

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

195 ↗

(On Diff #199465)

NIT: Maybe shorten a bit? Something like

Applies the first rule whose pattern matches, other rules are ignored

The current version has a bit too many details, so it's hard to grasp on a first read.

215 ↗

(On Diff #199465)

NIT: s/Ordered rules allow us/applyFirst allows to... ?

With a new name for the function, "ordered" rules can be confusing

231 ↗

(On Diff #199465)

Maybe start with this? It's a great analogy. Something like this at the start of the comment would be great:

`applyFirst` is similar to `anyOf` matcher with a replace action attached to each of its cases...

196 ↗

(On Diff #198811)

Ah, ok, so this is the restriction of anyOf.

232 ↗

(On Diff #198811)

applyFirst looks good, thanks!

240 ↗

(On Diff #198811)

I see. Maybe additionally put them into namespace detail?
A good way to make sure that any use is a red herring. (Otherwise clients would need to read the code to realize it's an internal function.

clang/lib/Tooling/Refactoring/Transformer.cpp

239 ↗

(On Diff #199465)

NIT: remove redundant {}

262 ↗

(On Diff #199465)

NIT:s/Finds the rule/Finds the case
Would help avoid potential confusion...

250 ↗

(On Diff #198811)

E.g. the restriction that the matchers should have a common kind seems to come from the fact that we need to later find out which case matched.

It this a limitation of the AST matchers design? E.g. I can't match both a type and an expression and bind different subnodes in each submatcher, right?

[ymandel]

responded to comments.

[ymandel]

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

196 ↗

(On Diff #198811)

indeed -- and all the other variadoc operations.

clang/lib/Tooling/Refactoring/Transformer.cpp

250 ↗

(On Diff #198811)

E.g. the restriction that the matchers should have a common kind seems to come from the fact that we need to later find out which case matched.

It this a limitation of the AST matchers design? E.g. I can't match both a type and an expression and bind different subnodes in each submatcher, right?

Yes, as far as I can tell, but I don't think its connected to the binding -- every DynTypedMatcher needs to report what kind it supports. IIRC, this is connected to the desire to specialize matchers to types to provide some static checking for matchers. Since there is no universal/root AST type, there's no root kind, and we're stuck w/ this restriction. If we were willing for the Matcher class to diverge from the AST, we could add a "universal" node kind, but that's another discussion...

In practice, this is mitigated in matchers by forcing the user to call a different addMatcher for each kind. But, that won't work for us since we want to (ultimately) support rules of different (base) kinds.

[ilya-biryukov]

LG, just a few NITs wrt to exposing implementation details in the header.

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

161 ↗

(On Diff #199476)

NIT: maybe clarify what "ordered" means? E.g. "The first rule that matches gets applied and the rest are ignored"

278 ↗

(On Diff #199476)

Can it be declared in .cpp file instead? Or is it used in clang-tidy integration?

282 ↗

(On Diff #199476)

Same here, so far this looks like an implementation detail of Transformer, why not put it into .cpp file?

[ymandel]

adjust some API comments.

[ymandel]

Thanks!!

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

278 ↗

(On Diff #199476)

buildMatcher and findSelectedCase will be used in the clang-tidy integration and in the apply-rule-to-single-node function that I'm planning.

282 ↗

(On Diff #199476)

see above. I think these also make sense as part of the RewriteRule abstraction. that is, you can think of these as methods of RewriteRule and they make sense even without thinking about transformer. That said, if you think there's a way to make this clearer, i"m happy to adjust the comments/name, etc.

[ilya-biryukov]

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

278 ↗

(On Diff #199476)

I'd say this makes these functions a public interface of rewrite rule, albeit it's an "advanced" use-case.
It's probably ok to keep them in detail namespace for now, but would be nice to come up with a proper public functions that allow us to implement those use-cases.
(Or declare these function public and well-supported and move them out of detail at some point)

[ymandel]

updated comments; moved some decls.

[ymandel]

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

278 ↗

(On Diff #199476)

Agreed. I noted this explicitly with a FIXME, reworded the comments to explicitly associate these with RewriteRule and moved them to immediately after the other RewriteRule functions. Transformer is now the last declaration in the file (and should probably be split into its own header at this point, being just one interpreter of RewriteRule among many).

[ymandel]

Synced to HEAD in preparation for committing.

include/clang/Tooling/Refactoring/Transformer.h

 
 /// Variant of \c change that selects the node of the entire match.
 template <typename T> ASTEdit change(std::string Replacement) {
   return change<T>(text(std::move(Replacement)));
 }
 
 /// Description of a source-code transformation.
 //
-// A *rewrite rule* describes a transformation of source code. It has the
-// following components:
+// A *rewrite rule* describes a transformation of source code. A simple rule
+// contains each of the following components:
 //
 // * Matcher: the pattern term, expressed as clang matchers (with Transformer
 //   extensions).
 //
 // * Edits: a set of Edits to the source code, described with ASTEdits.
 //
 // * Explanation: explanation of the rewrite.  This will be displayed to the
 //   user, where possible; for example, in clang-tidy diagnostics.
 //
-// Rules have an additional, implicit, component: the parameters. These are
-// portions of the pattern which are left unspecified, yet named so that we can
-// reference them in the replacement term.  The structure of parameters can be
-// partially or even fully specified, in which case they serve just to identify
-// matched nodes for later reference rather than abstract over portions of the
-// AST.  However, in all cases, we refer to named portions of the pattern as
-// parameters.
+// However, rules can also consist of (sub)rules, where the first that matches
+// is applied and the rest are ignored.  So, the above components are gathered
+// as a `Case` and a rule is a list of cases.
+//
+// Rule cases have an additional, implicit, component: the parameters. These are
+// portions of the pattern which are left unspecified, yet bound in the pattern
+// so that we can reference them in the edits.
 //
-// The \c Transformer class should be used to apply the rewrite rule and obtain
-// the corresponding replacements.
+// The \c Transformer class can be used to apply the rewrite rule and obtain the
+// corresponding replacements.
 struct RewriteRule {
-  // `Matcher` describes the context of this rule. It should always be bound to
-  // at least `RootId`.
+  struct Case {
     ast_matchers::internal::DynTypedMatcher Matcher;
     SmallVector<ASTEdit, 1> Edits;
     TextGenerator Explanation;
+  };
+  // We expect RewriteRules will most commonly include only one case.
+  SmallVector<Case, 1> Cases;
 
   // Id used as the default target of each match. The node described by the
   // matcher is should always be bound to this id.
   static constexpr llvm::StringLiteral RootId = "___root___";
 };
 
-/// Convenience function for constructing a \c RewriteRule. Takes care of
-/// binding the matcher to RootId.
+/// Convenience function for constructing a simple \c RewriteRule.
 RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
                      SmallVector<ASTEdit, 1> Edits);
 
 /// Convenience overload of \c makeRule for common case of only one edit.
 inline RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
                             ASTEdit Edit) {
   SmallVector<ASTEdit, 1> Edits;
   Edits.emplace_back(std::move(Edit));
   return makeRule(std::move(M), std::move(Edits));
 }
 
+/// 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.
+//
+// `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,
+// `serialize()`.  For performance reasons, we would like to make it
+// non-deterministic.  Therefore, we want to drop the expectation that
+// `a.serialize() = b.serialize() iff a = b` (although we'll maintain
+// `deserialize(a.serialize()) = a`).
+//
+// We have three cases to consider (for some equality function, `eq`):
+// ```
+// eq(a.serialize(), b.serialize()) --> eq(a,b)
+// eq(a, b.serialize())             --> eq(deserialize(a), b)
+// eq(a.serialize(), b)             --> eq(a, deserialize(b))
+// ```
+//
+// `applyFirst` allows us to specify each independently:
+// ```
+// auto eq_fun = functionDecl(...);
+// auto method_call = cxxMemberCallExpr(...);
+//
+// auto two_calls = callExpr(callee(eq_fun), hasArgument(0, method_call),
+//                           hasArgument(1, method_call));
+// auto left_call =
+//     callExpr(callee(eq_fun), callExpr(hasArgument(0, method_call)));
+// auto right_call =
+//     callExpr(callee(eq_fun), callExpr(hasArgument(1, method_call)));
+//
+// RewriteRule R = applyFirst({makeRule(two_calls, two_calls_action),
+//                             makeRule(left_call, left_call_action),
+//                             makeRule(right_call, right_call_action)});
+// ```
+RewriteRule applyFirst(ArrayRef<RewriteRule> Rules);
+
 // Define this overload of `change` here because RewriteRule::RootId is not in
 // scope at the declaration point above.
 template <typename T> ASTEdit change(TextGenerator Replacement) {
   return change<T>(RewriteRule::RootId, NodePart::Node, std::move(Replacement));
 }
 
+/// 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`.
+namespace detail {
+/// Builds a single matcher for the rule, covering all of the rule's cases.
+ast_matchers::internal::DynTypedMatcher buildMatcher(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.
 struct Transformation {
   CharSourceRange Range;
   std::string Replacement;
 };
 
 /// Attempts to translate `Edits`, which are in terms of AST nodes bound in the
 /// match `Result`, into Transformations, which are in terms of the source code
-/// text.  This function is a low-level part of the API, provided to support
-/// interpretation of a \c RewriteRule in a tool, like \c Transformer, rather
-/// than direct use by end users.
+/// text.
 ///
 /// Returns an empty vector if any of the edits apply to portions of the source
 /// that are ineligible for rewriting (certain interactions with macros, for
 /// example).  Fails if any invariants are violated relating to bound nodes in
 /// the match.  However, it does not fail in the case of conflicting edits --
 /// conflict handling is left to clients.  We recommend use of the \c
 /// AtomicChange or \c Replacements classes for assistance in detecting such
 /// conflicts.
 Expected<SmallVector<Transformation, 1>>
 translateEdits(const ast_matchers::MatchFinder::MatchResult &Result,
                llvm::ArrayRef<ASTEdit> Edits);
+} // namespace detail
 
 /// Handles the matcher and callback registration for a single rewrite rule, as
 /// defined by the arguments of the constructor.
 class Transformer : public ast_matchers::MatchFinder::MatchCallback {
 public:
   using ChangeConsumer =
       std::function<void(Expected<clang::tooling::AtomicChange> Change)>;
 

lib/Tooling/Refactoring/Transformer.cpp

 #include <string>
 #include <utility>
 #include <vector>
 
 using namespace clang;
 using namespace tooling;
 
 using ast_matchers::MatchFinder;
+using ast_matchers::internal::DynTypedMatcher;
 using ast_type_traits::ASTNodeKind;
 using ast_type_traits::DynTypedNode;
 using llvm::Error;
 using llvm::Expected;
 using llvm::Optional;
 using llvm::StringError;
 using llvm::StringRef;
 using llvm::Twine;
case NodePart::Name:
     return typeError(
         Target, Node.getNodeKind(),
         "NodePart::Name applied to neither DeclRefExpr, NamedDecl nor "
         "CXXCtorInitializer");
   }
   llvm_unreachable("Unexpected case in NodePart type.");
 }
 
-Expected<SmallVector<Transformation, 1>>
-tooling::translateEdits(const MatchResult &Result,
+Expected<SmallVector<tooling::detail::Transformation, 1>>
+tooling::detail::translateEdits(const MatchResult &Result,
                                 llvm::ArrayRef<ASTEdit> Edits) {
   SmallVector<Transformation, 1> Transformations;
   auto &NodesMap = Result.Nodes.getMap();
   for (const auto &Edit : Edits) {
     auto It = NodesMap.find(Edit.Target);
     assert(It != NodesMap.end() && "Edit target must be bound in the match.");
 
     Expected<CharSourceRange> Range = getTargetRange(
         Edit.Target, It->second, Edit.Kind, Edit.Part, *Result.Context);
     if (!Range)
       return Range.takeError();
     if (Range->isInvalid() ||
         isOriginMacroBody(*Result.SourceManager, Range->getBegin()))
       return SmallVector<Transformation, 0>();
     auto Replacement = Edit.Replacement(Result);
     if (!Replacement)
       return Replacement.takeError();
     Transformation T;
     T.Range = *Range;
     T.Replacement = std::move(*Replacement);
     Transformations.push_back(std::move(T));
   }
   return Transformations;
 }
 
-RewriteRule tooling::makeRule(ast_matchers::internal::DynTypedMatcher M,
+RewriteRule tooling::makeRule(DynTypedMatcher M,
                               SmallVector<ASTEdit, 1> Edits) {
+  return RewriteRule{
+      {RewriteRule::Case{std::move(M), std::move(Edits), nullptr}}};
+}
+
+// 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) {
+  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;
+}
+
+// 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) {
+  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);
+    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;
+
+  auto CommonKind = findCommonKind(Rule.Cases);
+  assert(!CommonKind.isNone() && "Cases must have compatible matchers.");
+  return DynTypedMatcher::constructVariadic(
+      DynTypedMatcher::VO_AnyOf, CommonKind, taggedMatchers("Tag", Rule.Cases));
+}
+
+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 RewriteRule{*M.tryBind(RewriteRule::RootId), std::move(Edits),
-                     nullptr};
+  return *M.tryBind(RewriteRule::RootId);
+}
+
+// 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(Rule.Matcher, this);
+  MatchFinder->addDynamicMatcher(tooling::detail::buildMatcher(Rule), 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();
   auto Root = NodesMap.find(RewriteRule::RootId);
   assert(Root != NodesMap.end() && "Transformation failed: missing root node.");
   SourceLocation RootLoc = Result.SourceManager->getExpansionLoc(
       Root->second.getSourceRange().getBegin());
   assert(RootLoc.isValid() && "Invalid location for Root node of match.");
 
-  auto Transformations = translateEdits(Result, Rule.Edits);
+  auto Transformations = tooling::detail::translateEdits(
+      Result, tooling::detail::findSelectedCase(Result, Rule).Edits);
   if (!Transformations) {
     Consumer(Transformations.takeError());
     return;
   }
 
   if (Transformations->empty()) {
     // No rewrite applied (but no error encountered either).
     RootLoc.print(llvm::errs() << "note: skipping match at loc ",

unittests/Tooling/TransformerTest.cpp

return [this](Expected<AtomicChange> C) {
         Changes.push_back(std::move(*C));
       } else {
         consumeError(C.takeError());
         ++ErrorCount;
       }
     };
   }
 
-  void testRule(RewriteRule Rule, StringRef Input, StringRef Expected) {
+  template <typename R>
+  void testRule(R Rule, StringRef Input, StringRef Expected) {
     Transformer T(std::move(Rule), consumer());
     T.registerMatchers(&MatchFinder);
     compareSnippets(Expected, rewrite(Input));
   }
 
   clang::ast_matchers::MatchFinder MatchFinder;
   // Records whether any errors occurred in individual changes.
   int ErrorCount = 0;
static RewriteRule ruleStrlenSize() {
   auto StringType = namedDecl(hasAnyName("::basic_string", "::string"));
   auto R = makeRule(
       callExpr(callee(functionDecl(hasName("strlen"))),
                hasArgument(0, cxxMemberCallExpr(
                                   on(expr(hasType(isOrPointsTo(StringType)))
                                          .bind(StringExpr)),
                                   callee(cxxMethodDecl(hasName("c_str")))))),
       change<clang::Expr>("REPLACED"));
-  R.Explanation = text("Use size() method directly on string.");
+  R.Cases[0].Explanation = text("Use size() method directly on string.");
   return R;
 }
 
 TEST_F(TransformerTest, StrlenSize) {
   std::string Input = "int f(string s) { return strlen(s.c_str()); }";
   std::string Expected = "int f(string s) { return REPLACED; }";
   testRule(ruleStrlenSize(), Input, Expected);
 }
TEST_F(TransformerTest, MultiChange) {
   StringRef C = "C", T = "T", E = "E";
   testRule(makeRule(ifStmt(hasCondition(expr().bind(C)),
                            hasThen(stmt().bind(T)), hasElse(stmt().bind(E))),
                     {change<Expr>(C, "true"), change<Stmt>(T, "{ /* then */ }"),
                      change<Stmt>(E, "{ /* else */ }")}),
            Input, Expected);
 }
 
+TEST_F(TransformerTest, OrderedRuleUnrelated) {
+  StringRef Flag = "flag";
+  RewriteRule FlagRule = makeRule(
+      cxxMemberCallExpr(on(expr(hasType(cxxRecordDecl(
+                                    hasName("proto::ProtoCommandLineFlag"))))
+                               .bind(Flag)),
+                        unless(callee(cxxMethodDecl(hasName("GetProto"))))),
+      change<clang::Expr>(Flag, "PROTO"));
+
+  std::string Input = R"cc(
+    proto::ProtoCommandLineFlag flag;
+    int x = flag.foo();
+    int y = flag.GetProto().foo();
+    int f(string s) { return strlen(s.c_str()); }
+  )cc";
+  std::string Expected = R"cc(
+    proto::ProtoCommandLineFlag flag;
+    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<clang::Expr>("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()); }
+  )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; }
+  )cc";
+
+  testRule(applyFirst({ruleStrlenSize(), ruleStrlenSizeDistinct()}), Input,
+           Expected);
+}
+
+// Change the order of the rules to get a different result.
+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";
+
+  testRule(applyFirst({ruleStrlenSizeDistinct(), ruleStrlenSize()}), 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) {
   std::string Input = "int conflictOneRule() { return 3 + 7; }";
   // Try to change the whole binary-operator expression AND one its operands: