diff --git a/clang-tools-extra/clang-tidy/abseil/CleanupCtadCheck.cpp b/clang-tools-extra/clang-tidy/abseil/CleanupCtadCheck.cpp
--- a/clang-tools-extra/clang-tidy/abseil/CleanupCtadCheck.cpp
+++ b/clang-tools-extra/clang-tidy/abseil/CleanupCtadCheck.cpp
@@ -23,7 +23,7 @@
 namespace tidy {
 namespace abseil {
 
-RewriteRule CleanupCtadCheckImpl() {
+RewriteRuleWith<std::string> CleanupCtadCheckImpl() {
   auto warning_message = cat("prefer absl::Cleanup's class template argument "
                              "deduction pattern in C++17 and higher");
 
diff --git a/clang-tools-extra/clang-tidy/abseil/StringFindStrContainsCheck.cpp b/clang-tools-extra/clang-tidy/abseil/StringFindStrContainsCheck.cpp
--- a/clang-tools-extra/clang-tidy/abseil/StringFindStrContainsCheck.cpp
+++ b/clang-tools-extra/clang-tidy/abseil/StringFindStrContainsCheck.cpp
@@ -30,7 +30,7 @@
 using ::clang::transformer::changeTo;
 using ::clang::transformer::makeRule;
 using ::clang::transformer::node;
-using ::clang::transformer::RewriteRule;
+using ::clang::transformer::RewriteRuleWith;
 
 AST_MATCHER(Type, isCharType) { return Node.isCharType(); }
 
@@ -39,7 +39,7 @@
                                                "::absl::string_view";
 static const char DefaultAbseilStringsMatchHeader[] = "absl/strings/match.h";
 
-static transformer::RewriteRule
+static transformer::RewriteRuleWith<std::string>
 makeRewriteRule(const std::vector<std::string> &StringLikeClassNames,
                 StringRef AbseilStringsMatchHeader) {
   auto StringLikeClass = cxxRecordDecl(hasAnyName(SmallVector<StringRef, 4>(
@@ -62,7 +62,7 @@
             hasArgument(1, cxxDefaultArgExpr())),
       onImplicitObjectArgument(expr().bind("string_being_searched")));
 
-  RewriteRule Rule = applyFirst(
+  RewriteRuleWith<std::string> Rule = applyFirst(
       {makeRule(
            binaryOperator(hasOperatorName("=="),
                           hasOperands(ignoringParenImpCasts(StringNpos),
diff --git a/clang-tools-extra/clang-tidy/bugprone/StringviewNullptrCheck.cpp b/clang-tools-extra/clang-tidy/bugprone/StringviewNullptrCheck.cpp
--- a/clang-tools-extra/clang-tidy/bugprone/StringviewNullptrCheck.cpp
+++ b/clang-tools-extra/clang-tidy/bugprone/StringviewNullptrCheck.cpp
@@ -37,7 +37,7 @@
 
 } // namespace
 
-RewriteRule StringviewNullptrCheckImpl() {
+RewriteRuleWith<std::string> StringviewNullptrCheckImpl() {
   auto construction_warning =
       cat("constructing basic_string_view from null is undefined; replace with "
           "the default constructor");
diff --git a/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.h b/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.h
--- a/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.h
+++ b/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.h
@@ -48,15 +48,16 @@
   /// cases where the options disable the check.
   ///
   /// See \c setRule for constraints on the rule.
-  TransformerClangTidyCheck(std::function<Optional<transformer::RewriteRule>(
-                                const LangOptions &, const OptionsView &)>
-                                MakeRule,
-                            StringRef Name, ClangTidyContext *Context);
+  TransformerClangTidyCheck(
+      std::function<Optional<transformer::RewriteRuleWith<std::string>>(
+          const LangOptions &, const OptionsView &)>
+          MakeRule,
+      StringRef Name, ClangTidyContext *Context);
 
   /// Convenience overload of the constructor when the rule doesn't have any
   /// dependencies.
-  TransformerClangTidyCheck(transformer::RewriteRule R, StringRef Name,
-                            ClangTidyContext *Context);
+  TransformerClangTidyCheck(transformer::RewriteRuleWith<std::string> R,
+                            StringRef Name, ClangTidyContext *Context);
 
   void registerPPCallbacks(const SourceManager &SM, Preprocessor *PP,
                            Preprocessor *ModuleExpanderPP) override;
@@ -74,10 +75,10 @@
   /// is a bug.  If no explanation is desired, indicate that explicitly (for
   /// example, by passing `text("no explanation")` to `makeRule` as the
   /// `Explanation` argument).
-  void setRule(transformer::RewriteRule R);
+  void setRule(transformer::RewriteRuleWith<std::string> R);
 
 private:
-  transformer::RewriteRule Rule;
+  transformer::RewriteRuleWith<std::string> Rule;
   IncludeInserter Inserter;
 };
 
diff --git a/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.cpp b/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.cpp
--- a/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.cpp
+++ b/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.cpp
@@ -13,16 +13,17 @@
 namespace clang {
 namespace tidy {
 namespace utils {
-using transformer::RewriteRule;
+using transformer::RewriteRuleBase;
+using transformer::RewriteRuleWith;
 
 #ifndef NDEBUG
-static bool hasExplanation(const RewriteRule::Case &C) {
-  return C.Explanation != nullptr;
+static bool hasGenerator(const transformer::Generator<std::string> &G) {
+  return G != nullptr;
 }
 #endif
 
-static void verifyRule(const RewriteRule &Rule) {
-  assert(llvm::all_of(Rule.Cases, hasExplanation) &&
+static void verifyRule(const RewriteRuleWith<std::string> &Rule) {
+  assert(llvm::all_of(Rule.Metadata, hasGenerator) &&
          "clang-tidy checks must have an explanation by default;"
          " explicitly provide an empty explanation if none is desired");
 }
@@ -39,23 +40,24 @@
 // we would be accessing `getLangOpts` and `Options` before the underlying
 // `ClangTidyCheck` instance was properly initialized.
 TransformerClangTidyCheck::TransformerClangTidyCheck(
-    std::function<Optional<RewriteRule>(const LangOptions &,
-                                        const OptionsView &)>
+    std::function<Optional<RewriteRuleWith<std::string>>(const LangOptions &,
+                                                         const OptionsView &)>
         MakeRule,
     StringRef Name, ClangTidyContext *Context)
     : TransformerClangTidyCheck(Name, Context) {
-  if (Optional<RewriteRule> R = MakeRule(getLangOpts(), Options))
+  if (Optional<RewriteRuleWith<std::string>> R =
+          MakeRule(getLangOpts(), Options))
     setRule(std::move(*R));
 }
 
-TransformerClangTidyCheck::TransformerClangTidyCheck(RewriteRule R,
-                                                     StringRef Name,
-                                                     ClangTidyContext *Context)
+TransformerClangTidyCheck::TransformerClangTidyCheck(
+    RewriteRuleWith<std::string> R, StringRef Name, ClangTidyContext *Context)
     : TransformerClangTidyCheck(Name, Context) {
   setRule(std::move(R));
 }
 
-void TransformerClangTidyCheck::setRule(transformer::RewriteRule R) {
+void TransformerClangTidyCheck::setRule(
+    transformer::RewriteRuleWith<std::string> R) {
   verifyRule(R);
   Rule = std::move(R);
 }
@@ -77,8 +79,9 @@
   if (Result.Context->getDiagnostics().hasErrorOccurred())
     return;
 
-  RewriteRule::Case Case = transformer::detail::findSelectedCase(Result, Rule);
-  Expected<SmallVector<transformer::Edit, 1>> Edits = Case.Edits(Result);
+  size_t I = transformer::detail::findSelectedCase(Result, Rule);
+  Expected<SmallVector<transformer::Edit, 1>> Edits =
+      Rule.Cases[I].Edits(Result);
   if (!Edits) {
     llvm::errs() << "Rewrite failed: " << llvm::toString(Edits.takeError())
                  << "\n";
@@ -89,7 +92,7 @@
   if (Edits->empty())
     return;
 
-  Expected<std::string> Explanation = Case.Explanation->eval(Result);
+  Expected<std::string> Explanation = Rule.Metadata[I]->eval(Result);
   if (!Explanation) {
     llvm::errs() << "Error in explanation: "
                  << llvm::toString(Explanation.takeError()) << "\n";
diff --git a/clang-tools-extra/unittests/clang-tidy/TransformerClangTidyCheckTest.cpp b/clang-tools-extra/unittests/clang-tidy/TransformerClangTidyCheckTest.cpp
--- a/clang-tools-extra/unittests/clang-tidy/TransformerClangTidyCheckTest.cpp
+++ b/clang-tools-extra/unittests/clang-tidy/TransformerClangTidyCheckTest.cpp
@@ -28,14 +28,14 @@
 using transformer::makeRule;
 using transformer::node;
 using transformer::noopEdit;
-using transformer::RewriteRule;
+using transformer::RewriteRuleWith;
 using transformer::RootID;
 using transformer::statement;
 
 // Invert the code of an if-statement, while maintaining its semantics.
-RewriteRule invertIf() {
+RewriteRuleWith<std::string> invertIf() {
   StringRef C = "C", T = "T", E = "E";
-  RewriteRule Rule = makeRule(
+  RewriteRuleWith<std::string> Rule = makeRule(
       ifStmt(hasCondition(expr().bind(C)), hasThen(stmt().bind(T)),
              hasElse(stmt().bind(E))),
       change(statement(RootID), cat("if(!(", node(std::string(C)), ")) ",
@@ -140,8 +140,9 @@
 }
 
 // A trivial rewrite-rule generator that requires Objective-C code.
-Optional<RewriteRule> needsObjC(const LangOptions &LangOpts,
-                                const ClangTidyCheck::OptionsView &Options) {
+Optional<RewriteRuleWith<std::string>>
+needsObjC(const LangOptions &LangOpts,
+          const ClangTidyCheck::OptionsView &Options) {
   if (!LangOpts.ObjC)
     return None;
   return makeRule(clang::ast_matchers::functionDecl(),
@@ -165,8 +166,9 @@
 }
 
 // A trivial rewrite rule generator that checks config options.
-Optional<RewriteRule> noSkip(const LangOptions &LangOpts,
-                             const ClangTidyCheck::OptionsView &Options) {
+Optional<RewriteRuleWith<std::string>>
+noSkip(const LangOptions &LangOpts,
+       const ClangTidyCheck::OptionsView &Options) {
   if (Options.get("Skip", "false") == "true")
     return None;
   return makeRule(clang::ast_matchers::functionDecl(),
@@ -194,10 +196,11 @@
                           Input, nullptr, "input.cc", None, Options));
 }
 
-RewriteRule replaceCall(IncludeFormat Format) {
+RewriteRuleWith<std::string> replaceCall(IncludeFormat Format) {
   using namespace ::clang::ast_matchers;
-  RewriteRule Rule = makeRule(callExpr(callee(functionDecl(hasName("f")))),
-                              change(cat("other()")), cat("no message"));
+  RewriteRuleWith<std::string> Rule =
+      makeRule(callExpr(callee(functionDecl(hasName("f")))),
+               change(cat("other()")), cat("no message"));
   addInclude(Rule, "clang/OtherLib.h", Format);
   return Rule;
 }
@@ -243,10 +246,10 @@
 }
 
 class IncludeOrderCheck : public TransformerClangTidyCheck {
-  static RewriteRule rule() {
+  static RewriteRuleWith<std::string> rule() {
     using namespace ::clang::ast_matchers;
-    RewriteRule Rule = transformer::makeRule(integerLiteral(), change(cat("5")),
-                                             cat("no message"));
+    RewriteRuleWith<std::string> Rule = transformer::makeRule(
+        integerLiteral(), change(cat("5")), cat("no message"));
     addInclude(Rule, "bar.h", IncludeFormat::Quoted);
     return Rule;
   }
diff --git a/clang/include/clang/Tooling/Transformer/RewriteRule.h b/clang/include/clang/Tooling/Transformer/RewriteRule.h
--- a/clang/include/clang/Tooling/Transformer/RewriteRule.h
+++ b/clang/include/clang/Tooling/Transformer/RewriteRule.h
@@ -63,6 +63,8 @@
 
 using TextGenerator = std::shared_ptr<MatchComputation<std::string>>;
 
+template <typename T> using Generator = std::shared_ptr<MatchComputation<T>>;
+
 using AnyGenerator = MatchConsumer<llvm::Any>;
 
 // Description of a source-code edit, expressed in terms of an AST node.
@@ -265,6 +267,8 @@
 // * Explanation: explanation of the rewrite.  This will be displayed to the
 //   user, where possible; for example, in clang-tidy diagnostics.
 //
+// * Metadata: additional data attached to the rewrite.
+//
 // 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.
@@ -275,38 +279,65 @@
 //
 // The \c Transformer class can be used to apply the rewrite rule and obtain the
 // corresponding replacements.
-struct RewriteRule {
+struct RewriteRuleBase {
   struct Case {
     ast_matchers::internal::DynTypedMatcher Matcher;
     EditGenerator Edits;
-    TextGenerator Explanation;
   };
   // We expect RewriteRules will most commonly include only one case.
   SmallVector<Case, 1> Cases;
+};
 
-  /// DEPRECATED: use `::clang::transformer::RootID` instead.
-  static const llvm::StringRef RootID;
+template <typename MetadataT> struct RewriteRuleWith : RewriteRuleBase {
+  SmallVector<Generator<MetadataT>, 1> Metadata;
 };
 
+template <> struct RewriteRuleWith<void> : RewriteRuleBase {};
+
+using RewriteRule = RewriteRuleWith<void>;
+
 /// Constructs a simple \c RewriteRule.
 RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
-                     EditGenerator Edits, TextGenerator Explanation = nullptr);
+                     EditGenerator Edits);
 
 /// Constructs a \c RewriteRule from multiple `ASTEdit`s.
 inline RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
-                            llvm::SmallVector<ASTEdit, 1> Edits,
-                            TextGenerator Explanation = nullptr) {
-  return makeRule(std::move(M), editList(std::move(Edits)),
-                  std::move(Explanation));
+                            llvm::SmallVector<ASTEdit, 1> Edits) {
+  return makeRule(std::move(M), editList(std::move(Edits)));
 }
 
 /// Overload of \c makeRule for common case of only one edit.
 inline RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M,
-                            ASTEdit Edit,
-                            TextGenerator Explanation = nullptr) {
-  return makeRule(std::move(M), edit(std::move(Edit)), std::move(Explanation));
+                            ASTEdit Edit) {
+  return makeRule(std::move(M), edit(std::move(Edit)));
+}
+
+/// Overloads of \c makeRule that also generate metadata when matching.
+/// @{
+template <typename T>
+RewriteRuleWith<T> makeRule(ast_matchers::internal::DynTypedMatcher M,
+                            EditGenerator Edits, Generator<T> Metadata) {
+  RewriteRuleWith<T> R;
+  R.Cases = {{std::move(M), std::move(Edits)}};
+  R.Metadata = {std::move(Metadata)};
+  return R;
+}
+
+template <typename T>
+RewriteRuleWith<T> makeRule(ast_matchers::internal::DynTypedMatcher M,
+                            llvm::SmallVector<ASTEdit, 1> Edits,
+                            Generator<T> Metadata) {
+  return makeRule(std::move(M), editList(std::move(Edits)),
+                  std::move(Metadata));
 }
 
+template <typename T>
+RewriteRuleWith<T> makeRule(ast_matchers::internal::DynTypedMatcher M,
+                            ASTEdit Edit, Generator<T> Metadata) {
+  return makeRule(std::move(M), edit(std::move(Edit)), std::move(Metadata));
+}
+/// @}
+
 /// For every case in Rule, adds an include directive for the given header. The
 /// common use is assumed to be a rule with only one case. For example, to
 /// replace a function call and add headers corresponding to the new code, one
@@ -317,7 +348,7 @@
 ///   addInclude(R, "path/to/bar_header.h");
 ///   addInclude(R, "vector", IncludeFormat::Angled);
 /// \endcode
-void addInclude(RewriteRule &Rule, llvm::StringRef Header,
+void addInclude(RewriteRuleBase &Rule, llvm::StringRef Header,
                 IncludeFormat Format = IncludeFormat::Quoted);
 
 /// Applies the first rule whose pattern matches; other rules are ignored.  If
@@ -359,7 +390,38 @@
 //                             makeRule(left_call, left_call_action),
 //                             makeRule(right_call, right_call_action)});
 // ```
-RewriteRule applyFirst(ArrayRef<RewriteRule> Rules);
+/// @{
+template <typename T>
+RewriteRuleWith<T> applyFirst(ArrayRef<RewriteRuleWith<T>> Rules) {
+  RewriteRuleWith<T> R;
+  for (auto &Rule : Rules) {
+    R.Cases.append(Rule.Cases.begin(), Rule.Cases.end());
+    R.Metadata.append(Rule.Metadata.begin(), Rule.Metadata.end());
+  }
+  return R;
+}
+
+template <>
+RewriteRuleWith<void> applyFirst(ArrayRef<RewriteRuleWith<void>> Rules);
+
+template <typename T>
+RewriteRuleWith<T> applyFirst(const std::vector<RewriteRuleWith<T>> &Rules) {
+  return applyFirst(llvm::makeArrayRef(Rules));
+}
+
+template <typename T>
+RewriteRuleWith<T> applyFirst(std::initializer_list<RewriteRuleWith<T>> Rules) {
+  return applyFirst(llvm::makeArrayRef(Rules.begin(), Rules.end()));
+}
+/// @}
+
+/// Converts a \c RewriteRuleWith<T> to a \c RewriteRule by stripping off the
+/// metadata generators.
+template <typename T>
+std::enable_if_t<!std::is_same<T, void>::value, RewriteRule>
+stripMetadata(RewriteRuleWith<T> Rule) {
+  return RewriteRule{std::move(Rule.Cases)};
+}
 
 /// 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
@@ -423,7 +485,8 @@
 /// Only supports Rules whose cases' matchers 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);
+ast_matchers::internal::DynTypedMatcher
+buildMatcher(const RewriteRuleBase &Rule);
 
 /// Builds a set of matchers that cover the rule.
 ///
@@ -433,7 +496,7 @@
 /// for rewriting. If any such matchers are included, will return an empty
 /// vector.
 std::vector<ast_matchers::internal::DynTypedMatcher>
-buildMatchers(const RewriteRule &Rule);
+buildMatchers(const RewriteRuleBase &Rule);
 
 /// Gets the beginning location of the source matched by a rewrite rule. If the
 /// match occurs within a macro expansion, returns the beginning of the
@@ -443,9 +506,8 @@
 
 /// 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);
+size_t findSelectedCase(const ast_matchers::MatchFinder::MatchResult &Result,
+                        const RewriteRuleBase &Rule);
 } // namespace detail
 } // namespace transformer
 } // namespace clang
diff --git a/clang/include/clang/Tooling/Transformer/Transformer.h b/clang/include/clang/Tooling/Transformer/Transformer.h
--- a/clang/include/clang/Tooling/Transformer/Transformer.h
+++ b/clang/include/clang/Tooling/Transformer/Transformer.h
@@ -18,6 +18,59 @@
 
 namespace clang {
 namespace tooling {
+
+namespace internal_transformer {
+/// Implementation details of \c Transformer with type erasure around
+/// \c RewriteRule and \c RewriteRule<T> as well as the corresponding consumers.
+class TransformerImpl {
+public:
+  virtual ~TransformerImpl() = default;
+
+  void onMatch(const ast_matchers::MatchFinder::MatchResult &Result);
+
+  virtual std::vector<ast_matchers::internal::DynTypedMatcher>
+  buildMatchers() const = 0;
+
+protected:
+  /// Converts a set of \c Edit into a \c AtomicChange per file modified.
+  /// Returns an error if the edits fail to compose, e.g. overlapping edits.
+  static llvm::Expected<llvm::SmallVector<AtomicChange, 1>>
+  convertToAtomicChanges(const llvm::SmallVectorImpl<transformer::Edit> &Edits,
+                         const ast_matchers::MatchFinder::MatchResult &Result);
+
+private:
+  virtual void
+  onMatchImpl(const ast_matchers::MatchFinder::MatchResult &Result) = 0;
+};
+
+/// Implementation for when no metadata is generated as a part of the
+/// \c RewriteRule.
+class PlainConsumer final : public TransformerImpl {
+  transformer::RewriteRule Rule;
+  std::function<void(Expected<llvm::MutableArrayRef<AtomicChange>>)> Consumer;
+
+public:
+  explicit PlainConsumer(
+      transformer::RewriteRule Rule,
+      std::function<void(Expected<llvm::MutableArrayRef<AtomicChange>>)>
+          Consumer)
+      : Rule(std::move(Rule)), Consumer(std::move(Consumer)) {
+    assert(llvm::all_of(Rule.Cases,
+                        [](const transformer::RewriteRule::Case &Case) {
+                          return Case.Edits;
+                        }) &&
+           "edit generator must be provided for each rule");
+  }
+
+private:
+  void onMatchImpl(const ast_matchers::MatchFinder::MatchResult &Result) final;
+  std::vector<ast_matchers::internal::DynTypedMatcher>
+  buildMatchers() const final {
+    return transformer::detail::buildMatchers(Rule);
+  }
+};
+} // namespace internal_transformer
+
 /// Handles the matcher and callback registration for a single `RewriteRule`, as
 /// defined by the arguments of the constructor.
 class Transformer : public ast_matchers::MatchFinder::MatchCallback {
@@ -31,16 +84,36 @@
   using ChangeSetConsumer = std::function<void(
       Expected<llvm::MutableArrayRef<AtomicChange>> Changes)>;
 
-  /// \param Consumer Receives all rewrites for a single match, or an error.
+  template <typename T> struct Result {
+    llvm::MutableArrayRef<AtomicChange> Changes;
+    T Metadata;
+  };
+
+  /// \param Consumer receives all rewrites for a single match, or an error.
   /// Will not necessarily be called for each match; for example, if the rule
   /// generates no edits but does not fail.  Note that clients are responsible
   /// for handling the case that independent \c AtomicChanges conflict with each
   /// other.
-  explicit Transformer(transformer::RewriteRule Rule,
-                       ChangeSetConsumer Consumer)
-      : Rule(std::move(Rule)), Consumer(std::move(Consumer)) {
-    assert(this->Consumer && "Consumer is empty");
-  }
+  template <typename ConsumerFn,
+            std::enable_if_t<
+                llvm::is_invocable<
+                    ConsumerFn,
+                    llvm::Expected<llvm::MutableArrayRef<AtomicChange>>>::value,
+                int> = 0>
+  explicit Transformer(transformer::RewriteRuleWith<void> Rule,
+                       ConsumerFn Consumer)
+      : Impl(std::make_unique<internal_transformer::PlainConsumer>(
+            std::move(Rule), std::move(Consumer))) {}
+
+  /// \param Consumer receives all rewrites and the associated metadata for a
+  /// single match, or an error. Will always be called for each match, even if
+  /// the rule generates no edits.  Note that clients are responsible for
+  /// handling the case that independent \c AtomicChanges conflict with each
+  /// other.
+  template <typename T, typename ConsumerFn,
+            std::enable_if_t<!std::is_same<T, void>::value, int> = 0>
+  explicit Transformer(transformer::RewriteRuleWith<T> Rule,
+                       ConsumerFn Consumer);
 
   /// N.B. Passes `this` pointer to `MatchFinder`.  So, this object should not
   /// be moved after this call.
@@ -51,11 +124,77 @@
   void run(const ast_matchers::MatchFinder::MatchResult &Result) override;
 
 private:
-  transformer::RewriteRule Rule;
-  /// Receives sets of successful rewrites as an
-  /// \c llvm::ArrayRef<AtomicChange>.
-  ChangeSetConsumer Consumer;
+  std::unique_ptr<internal_transformer::TransformerImpl> Impl;
 };
+
+namespace internal_transformer {
+/// Implementation when metadata is generated as a part of the rewrite. This
+/// happens when we have a \c RewriteRuleWith<T>.
+template <typename T> class MetadataConsumer final : public TransformerImpl {
+  transformer::RewriteRuleWith<T> Rule;
+  std::function<void(llvm::Expected<Transformer::Result<T>>)> Consumer;
+
+public:
+  explicit MetadataConsumer(
+      transformer::RewriteRuleWith<T> Rule,
+      std::function<void(llvm::Expected<Transformer::Result<T>>)> Consumer)
+      : Rule(std::move(Rule)), Consumer(std::move(Consumer)) {}
+
+private:
+  void onMatchImpl(const ast_matchers::MatchFinder::MatchResult &Result) final {
+    size_t I = transformer::detail::findSelectedCase(Result, Rule);
+    auto Transformations = Rule.Cases[I].Edits(Result);
+    if (!Transformations) {
+      Consumer(Transformations.takeError());
+      return;
+    }
+
+    llvm::SmallVector<AtomicChange, 1> Changes;
+    if (!Transformations->empty()) {
+      auto C = convertToAtomicChanges(*Transformations, Result);
+      if (C) {
+        Changes = std::move(*C);
+      } else {
+        Consumer(C.takeError());
+        return;
+      }
+    }
+
+    auto Metadata = Rule.Metadata[I]->eval(Result);
+    if (!Metadata) {
+      Consumer(Metadata.takeError());
+      return;
+    }
+
+    Consumer(Transformer::Result<T>{
+        llvm::MutableArrayRef<AtomicChange>(Changes), std::move(*Metadata)});
+  }
+
+  std::vector<ast_matchers::internal::DynTypedMatcher>
+  buildMatchers() const final {
+    return transformer::detail::buildMatchers(Rule);
+  }
+};
+} // namespace internal_transformer
+
+template <typename T, typename ConsumerFn,
+          std::enable_if_t<!std::is_same<T, void>::value, int>>
+Transformer::Transformer(transformer::RewriteRuleWith<T> Rule,
+                         ConsumerFn Consumer)
+    : Impl(std::make_unique<internal_transformer::MetadataConsumer<T>>(
+          std::move(Rule), std::move(Consumer))) {
+  assert(
+      llvm::all_of(Rule.Cases,
+                   [](const transformer::RewriteRuleBase::Case &Case) -> bool {
+                     return !!Case.Edits;
+                   }) &&
+      "edit generator must be provided for each rule");
+  assert(llvm::all_of(Rule.Metadata,
+                      [](const typename transformer::Generator<T> &Metadata)
+                          -> bool { return !!Metadata; }) &&
+         "metadata generator must be provided for each rule");
+}
+
 } // namespace tooling
 } // namespace clang
 
diff --git a/clang/lib/Tooling/Transformer/RewriteRule.cpp b/clang/lib/Tooling/Transformer/RewriteRule.cpp
--- a/clang/lib/Tooling/Transformer/RewriteRule.cpp
+++ b/clang/lib/Tooling/Transformer/RewriteRule.cpp
@@ -166,10 +166,10 @@
   return E;
 }
 
-RewriteRule transformer::makeRule(DynTypedMatcher M, EditGenerator Edits,
-                                  TextGenerator Explanation) {
-  return RewriteRule{{RewriteRule::Case{std::move(M), std::move(Edits),
-                                        std::move(Explanation)}}};
+RewriteRule transformer::makeRule(DynTypedMatcher M, EditGenerator Edits) {
+  RewriteRule R;
+  R.Cases = {{std::move(M), std::move(Edits)}};
+  return R;
 }
 
 namespace {
@@ -247,9 +247,8 @@
   void run(const MatchFinder::MatchResult &Result) override {
     if (!Edits)
       return;
-    transformer::RewriteRule::Case Case =
-        transformer::detail::findSelectedCase(Result, Rule);
-    auto Transformations = Case.Edits(Result);
+    size_t I = transformer::detail::findSelectedCase(Result, Rule);
+    auto Transformations = Rule.Cases[I].Edits(Result);
     if (!Transformations) {
       Edits = Transformations.takeError();
       return;
@@ -325,7 +324,7 @@
   };
 }
 
-void transformer::addInclude(RewriteRule &Rule, StringRef Header,
+void transformer::addInclude(RewriteRuleBase &Rule, StringRef Header,
                              IncludeFormat Format) {
   for (auto &Case : Rule.Cases)
     Case.Edits = flatten(std::move(Case.Edits), addInclude(Header, Format));
@@ -366,7 +365,9 @@
 // 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 transformer::applyFirst(ArrayRef<RewriteRule> Rules) {
+template <>
+RewriteRuleWith<void>
+transformer::applyFirst(ArrayRef<RewriteRuleWith<void>> Rules) {
   RewriteRule R;
   for (auto &Rule : Rules)
     R.Cases.append(Rule.Cases.begin(), Rule.Cases.end());
@@ -374,12 +375,13 @@
 }
 
 std::vector<DynTypedMatcher>
-transformer::detail::buildMatchers(const RewriteRule &Rule) {
+transformer::detail::buildMatchers(const RewriteRuleBase &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>>
+  std::map<ASTNodeKind,
+           SmallVector<std::pair<size_t, RewriteRuleBase::Case>, 1>>
       Buckets;
   const SmallVectorImpl<RewriteRule::Case> &Cases = Rule.Cases;
   for (int I = 0, N = Cases.size(); I < N; ++I) {
@@ -405,7 +407,7 @@
   return Matchers;
 }
 
-DynTypedMatcher transformer::detail::buildMatcher(const RewriteRule &Rule) {
+DynTypedMatcher transformer::detail::buildMatcher(const RewriteRuleBase &Rule) {
   std::vector<DynTypedMatcher> Ms = buildMatchers(Rule);
   assert(Ms.size() == 1 && "Cases must have compatible matchers.");
   return Ms[0];
@@ -428,19 +430,16 @@
 
 // Finds the case that was "selected" -- that is, whose matcher triggered the
 // `MatchResult`.
-const RewriteRule::Case &
-transformer::detail::findSelectedCase(const MatchResult &Result,
-                                  const RewriteRule &Rule) {
+size_t transformer::detail::findSelectedCase(const MatchResult &Result,
+                                             const RewriteRuleBase &Rule) {
   if (Rule.Cases.size() == 1)
-    return Rule.Cases[0];
+    return 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];
+      return i;
   }
   llvm_unreachable("No tag found for this rule.");
 }
-
-const llvm::StringRef RewriteRule::RootID = ::clang::transformer::RootID;
diff --git a/clang/lib/Tooling/Transformer/Transformer.cpp b/clang/lib/Tooling/Transformer/Transformer.cpp
--- a/clang/lib/Tooling/Transformer/Transformer.cpp
+++ b/clang/lib/Tooling/Transformer/Transformer.cpp
@@ -16,35 +16,29 @@
 #include <utility>
 #include <vector>
 
-using namespace clang;
-using namespace tooling;
+namespace clang {
+namespace tooling {
 
-using ast_matchers::MatchFinder;
+using ::clang::ast_matchers::MatchFinder;
 
-void Transformer::registerMatchers(MatchFinder *MatchFinder) {
-  for (auto &Matcher : transformer::detail::buildMatchers(Rule))
-    MatchFinder->addDynamicMatcher(Matcher, this);
-}
+namespace internal_transformer {
 
-void Transformer::run(const MatchFinder::MatchResult &Result) {
+void TransformerImpl::onMatch(
+    const ast_matchers::MatchFinder::MatchResult &Result) {
   if (Result.Context->getDiagnostics().hasErrorOccurred())
     return;
 
-  transformer::RewriteRule::Case Case =
-      transformer::detail::findSelectedCase(Result, Rule);
-  auto Transformations = Case.Edits(Result);
-  if (!Transformations) {
-    Consumer(Transformations.takeError());
-    return;
-  }
-
-  if (Transformations->empty())
-    return;
+  onMatchImpl(Result);
+}
 
+llvm::Expected<llvm::SmallVector<AtomicChange, 1>>
+TransformerImpl::convertToAtomicChanges(
+    const llvm::SmallVectorImpl<transformer::Edit> &Edits,
+    const MatchFinder::MatchResult &Result) {
   // 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) {
+  for (const auto &T : Edits) {
     auto ID = Result.SourceManager->getFileID(T.Range.getBegin());
     auto Iter = ChangesByFileID
                     .emplace(ID, AtomicChange(*Result.SourceManager,
@@ -55,8 +49,7 @@
     case transformer::EditKind::Range:
       if (auto Err =
               AC.replace(*Result.SourceManager, T.Range, T.Replacement)) {
-        Consumer(std::move(Err));
-        return;
+        return std::move(Err);
       }
       break;
     case transformer::EditKind::AddInclude:
@@ -69,5 +62,43 @@
   Changes.reserve(ChangesByFileID.size());
   for (auto &IDChangePair : ChangesByFileID)
     Changes.push_back(std::move(IDChangePair.second));
-  Consumer(llvm::MutableArrayRef<AtomicChange>(Changes));
+
+  return Changes;
+}
+
+void PlainConsumer::onMatchImpl(const MatchFinder::MatchResult &Result) {
+  size_t I = transformer::detail::findSelectedCase(Result, Rule);
+  auto Transformations = Rule.Cases[I].Edits(Result);
+  if (!Transformations) {
+    Consumer(Transformations.takeError());
+    return;
+  }
+
+  if (Transformations->empty())
+    return;
+
+  auto Changes = convertToAtomicChanges(*Transformations, Result);
+  if (!Changes) {
+    Consumer(Changes.takeError());
+    return;
+  }
+
+  Consumer(llvm::MutableArrayRef<AtomicChange>(*Changes));
 }
+
+} // namespace internal_transformer
+
+void Transformer::registerMatchers(MatchFinder *MatchFinder) {
+  for (auto &Matcher : Impl->buildMatchers())
+    MatchFinder->addDynamicMatcher(Matcher, this);
+}
+
+void Transformer::run(const MatchFinder::MatchResult &Result) {
+  if (Result.Context->getDiagnostics().hasErrorOccurred())
+    return;
+
+  Impl->onMatch(Result);
+}
+
+} // namespace tooling
+} // namespace clang
diff --git a/clang/unittests/Tooling/TransformerTest.cpp b/clang/unittests/Tooling/TransformerTest.cpp
--- a/clang/unittests/Tooling/TransformerTest.cpp
+++ b/clang/unittests/Tooling/TransformerTest.cpp
@@ -31,9 +31,11 @@
 using ::clang::transformer::member;
 using ::clang::transformer::name;
 using ::clang::transformer::node;
+using ::clang::transformer::noEdits;
 using ::clang::transformer::remove;
 using ::clang::transformer::rewriteDescendants;
 using ::clang::transformer::RewriteRule;
+using ::clang::transformer::RewriteRuleWith;
 using ::clang::transformer::statement;
 using ::testing::ElementsAre;
 using ::testing::IsEmpty;
@@ -129,7 +131,7 @@
         Changes.insert(Changes.end(), std::make_move_iterator(C->begin()),
                        std::make_move_iterator(C->end()));
       } else {
-        // FIXME: stash this error rather then printing.
+        // FIXME: stash this error rather than printing.
         llvm::errs() << "Error generating changes: "
                      << llvm::toString(C.takeError()) << "\n";
         ++ErrorCount;
@@ -137,27 +139,58 @@
     };
   }
 
-  template <typename R>
-  void testRule(R Rule, StringRef Input, StringRef Expected) {
+  auto consumerWithStringMetadata() {
+    return [this](Expected<Transformer::Result<std::string>> C) {
+      if (C) {
+        Changes.insert(Changes.end(),
+                       std::make_move_iterator(C->Changes.begin()),
+                       std::make_move_iterator(C->Changes.end()));
+        StringMetadata.push_back(std::move(C->Metadata));
+      } else {
+        // FIXME: stash this error rather than printing.
+        llvm::errs() << "Error generating changes: "
+                     << llvm::toString(C.takeError()) << "\n";
+        ++ErrorCount;
+      }
+    };
+  }
+
+  void testRule(RewriteRule Rule, StringRef Input, StringRef Expected) {
     Transformers.push_back(
         std::make_unique<Transformer>(std::move(Rule), consumer()));
     Transformers.back()->registerMatchers(&MatchFinder);
     compareSnippets(Expected, rewrite(Input));
   }
 
-  template <typename R> void testRuleFailure(R Rule, StringRef Input) {
+  void testRule(RewriteRuleWith<std::string> Rule, StringRef Input,
+                StringRef Expected) {
+    Transformers.push_back(std::make_unique<Transformer>(
+        std::move(Rule), consumerWithStringMetadata()));
+    Transformers.back()->registerMatchers(&MatchFinder);
+    compareSnippets(Expected, rewrite(Input));
+  }
+
+  void testRuleFailure(RewriteRule Rule, StringRef Input) {
     Transformers.push_back(
         std::make_unique<Transformer>(std::move(Rule), consumer()));
     Transformers.back()->registerMatchers(&MatchFinder);
     ASSERT_FALSE(rewrite(Input)) << "Expected failure to rewrite code";
   }
 
+  void testRuleFailure(RewriteRuleWith<std::string> Rule, StringRef Input) {
+    Transformers.push_back(std::make_unique<Transformer>(
+        std::move(Rule), consumerWithStringMetadata()));
+    Transformers.back()->registerMatchers(&MatchFinder);
+    ASSERT_FALSE(rewrite(Input)) << "Expected failure to rewrite code";
+  }
+
   // Transformers are referenced by MatchFinder.
   std::vector<std::unique_ptr<Transformer>> Transformers;
   clang::ast_matchers::MatchFinder MatchFinder;
   // Records whether any errors occurred in individual changes.
   int ErrorCount = 0;
   AtomicChanges Changes;
+  std::vector<std::string> StringMetadata;
 
 private:
   FileContentMappings FileContents = {{"header.h", ""}};
@@ -169,7 +202,7 @@
 };
 
 // Given string s, change strlen($s.c_str()) to REPLACED.
-static RewriteRule ruleStrlenSize() {
+static RewriteRuleWith<std::string> ruleStrlenSize() {
   StringRef StringExpr = "strexpr";
   auto StringType = namedDecl(hasAnyName("::basic_string", "::string"));
   auto R = makeRule(
@@ -886,12 +919,12 @@
 
 TEST_F(TransformerTest, OrderedRuleUnrelated) {
   StringRef Flag = "flag";
-  RewriteRule FlagRule = makeRule(
+  RewriteRuleWith<std::string> FlagRule = makeRule(
       cxxMemberCallExpr(on(expr(hasType(cxxRecordDecl(
                                     hasName("proto::ProtoCommandLineFlag"))))
                                .bind(Flag)),
                         unless(callee(cxxMethodDecl(hasName("GetProto"))))),
-      changeTo(node(std::string(Flag)), cat("PROTO")));
+      changeTo(node(std::string(Flag)), cat("PROTO")), cat(""));
 
   std::string Input = R"cc(
     proto::ProtoCommandLineFlag flag;
@@ -1682,4 +1715,39 @@
                    "./input.h"))));
 }
 
+TEST_F(TransformerTest, GeneratesMetadata) {
+  std::string Input = R"cc(int target = 0;)cc";
+  std::string Expected = R"cc(REPLACE)cc";
+  RewriteRuleWith<std::string> Rule = makeRule(
+      varDecl(hasName("target")), changeTo(cat("REPLACE")), cat("METADATA"));
+  testRule(std::move(Rule), Input, Expected);
+  EXPECT_EQ(ErrorCount, 0);
+  EXPECT_THAT(StringMetadata, UnorderedElementsAre("METADATA"));
+}
+
+TEST_F(TransformerTest, GeneratesMetadataWithNoEdits) {
+  std::string Input = R"cc(int target = 0;)cc";
+  RewriteRuleWith<std::string> Rule = makeRule(
+      varDecl(hasName("target")).bind("var"), noEdits(), cat("METADATA"));
+  testRule(std::move(Rule), Input, Input);
+  EXPECT_EQ(ErrorCount, 0);
+  EXPECT_THAT(StringMetadata, UnorderedElementsAre("METADATA"));
+}
+
+TEST_F(TransformerTest, PropagateMetadataErrors) {
+  class AlwaysFail : public transformer::MatchComputation<std::string> {
+    llvm::Error eval(const ast_matchers::MatchFinder::MatchResult &,
+                     std::string *) const override {
+      return llvm::createStringError(llvm::errc::invalid_argument, "ERROR");
+    }
+    std::string toString() const override { return "AlwaysFail"; }
+  };
+  std::string Input = R"cc(int target = 0;)cc";
+  RewriteRuleWith<std::string> Rule = makeRule<std::string>(
+      varDecl(hasName("target")).bind("var"), edit(changeTo(cat("REPLACE"))),
+      std::make_shared<AlwaysFail>());
+  testRuleFailure(std::move(Rule), Input);
+  EXPECT_EQ(ErrorCount, 1);
+}
+
 } // namespace