7 files changed, 1125 insertions, 0 deletions
diff --git a/lib/Tooling/Transformer/CMakeLists.txt b/lib/Tooling/Transformer/CMakeLists.txt
new file mode 100644
index 000000000000..68f0cfeee8f6
--- /dev/null
+++ b/lib/Tooling/Transformer/CMakeLists.txt
@@ -0,0 +1,18 @@
+set(LLVM_LINK_COMPONENTS Support)
+
+add_clang_library(clangTransformer
+  RangeSelector.cpp
+  RewriteRule.cpp
+  SourceCode.cpp
+  SourceCodeBuilders.cpp
+  Stencil.cpp
+  Transformer.cpp
+
+  LINK_LIBS
+  clangAST
+  clangASTMatchers
+  clangBasic
+  clangLex
+  clangToolingCore
+  clangToolingRefactoring
+  )
diff --git a/lib/Tooling/Transformer/RangeSelector.cpp b/lib/Tooling/Transformer/RangeSelector.cpp
new file mode 100644
index 000000000000..9f81423c9022
--- /dev/null
+++ b/lib/Tooling/Transformer/RangeSelector.cpp
@@ -0,0 +1,314 @@
+//===--- RangeSelector.cpp - RangeSelector implementations ------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Transformer/RangeSelector.h"
+#include "clang/AST/Expr.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Tooling/Transformer/SourceCode.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Errc.h"
+#include "llvm/Support/Error.h"
+#include <string>
+#include <utility>
+#include <vector>
+
+using namespace clang;
+using namespace transformer;
+
+using ast_matchers::MatchFinder;
+using ast_type_traits::ASTNodeKind;
+using ast_type_traits::DynTypedNode;
+using llvm::Error;
+using llvm::StringError;
+
+using MatchResult = MatchFinder::MatchResult;
+
+static Error invalidArgumentError(Twine Message) {
+  return llvm::make_error<StringError>(llvm::errc::invalid_argument, Message);
+}
+
+static Error typeError(StringRef ID, const ASTNodeKind &Kind) {
+  return invalidArgumentError("mismatched type (node id=" + ID +
+                              " kind=" + Kind.asStringRef() + ")");
+}
+
+static Error typeError(StringRef ID, const ASTNodeKind &Kind,
+                       Twine ExpectedType) {
+  return invalidArgumentError("mismatched type: expected one of " +
+                              ExpectedType + " (node id=" + ID +
+                              " kind=" + Kind.asStringRef() + ")");
+}
+
+static Error missingPropertyError(StringRef ID, Twine Description,
+                                  StringRef Property) {
+  return invalidArgumentError(Description + " requires property '" + Property +
+                              "' (node id=" + ID + ")");
+}
+
+static Expected<DynTypedNode> getNode(const ast_matchers::BoundNodes &Nodes,
+                                      StringRef ID) {
+  auto &NodesMap = Nodes.getMap();
+  auto It = NodesMap.find(ID);
+  if (It == NodesMap.end())
+    return invalidArgumentError("ID not bound: " + ID);
+  return It->second;
+}
+
+// FIXME: handling of macros should be configurable.
+static SourceLocation findPreviousTokenStart(SourceLocation Start,
+                                             const SourceManager &SM,
+                                             const LangOptions &LangOpts) {
+  if (Start.isInvalid() || Start.isMacroID())
+    return SourceLocation();
+
+  SourceLocation BeforeStart = Start.getLocWithOffset(-1);
+  if (BeforeStart.isInvalid() || BeforeStart.isMacroID())
+    return SourceLocation();
+
+  return Lexer::GetBeginningOfToken(BeforeStart, SM, LangOpts);
+}
+
+// Finds the start location of the previous token of kind \p TK.
+// FIXME: handling of macros should be configurable.
+static SourceLocation findPreviousTokenKind(SourceLocation Start,
+                                            const SourceManager &SM,
+                                            const LangOptions &LangOpts,
+                                            tok::TokenKind TK) {
+  while (true) {
+    SourceLocation L = findPreviousTokenStart(Start, SM, LangOpts);
+    if (L.isInvalid() || L.isMacroID())
+      return SourceLocation();
+
+    Token T;
+    if (Lexer::getRawToken(L, T, SM, LangOpts, /*IgnoreWhiteSpace=*/true))
+      return SourceLocation();
+
+    if (T.is(TK))
+      return T.getLocation();
+
+    Start = L;
+  }
+}
+
+static SourceLocation findOpenParen(const CallExpr &E, const SourceManager &SM,
+                                    const LangOptions &LangOpts) {
+  SourceLocation EndLoc =
+      E.getNumArgs() == 0 ? E.getRParenLoc() : E.getArg(0)->getBeginLoc();
+  return findPreviousTokenKind(EndLoc, SM, LangOpts, tok::TokenKind::l_paren);
+}
+
+RangeSelector transformer::before(RangeSelector Selector) {
+  return [Selector](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<CharSourceRange> SelectedRange = Selector(Result);
+    if (!SelectedRange)
+      return SelectedRange.takeError();
+    return CharSourceRange::getCharRange(SelectedRange->getBegin());
+  };
+}
+
+RangeSelector transformer::after(RangeSelector Selector) {
+  return [Selector](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<CharSourceRange> SelectedRange = Selector(Result);
+    if (!SelectedRange)
+      return SelectedRange.takeError();
+    if (SelectedRange->isCharRange())
+      return CharSourceRange::getCharRange(SelectedRange->getEnd());
+    return CharSourceRange::getCharRange(Lexer::getLocForEndOfToken(
+        SelectedRange->getEnd(), 0, Result.Context->getSourceManager(),
+        Result.Context->getLangOpts()));
+  };
+}
+
+RangeSelector transformer::node(std::string ID) {
+  return [ID](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<DynTypedNode> Node = getNode(Result.Nodes, ID);
+    if (!Node)
+      return Node.takeError();
+    return Node->get<Stmt>() != nullptr && Node->get<Expr>() == nullptr
+               ? tooling::getExtendedRange(*Node, tok::TokenKind::semi,
+                                           *Result.Context)
+               : CharSourceRange::getTokenRange(Node->getSourceRange());
+  };
+}
+
+RangeSelector transformer::statement(std::string ID) {
+  return [ID](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<DynTypedNode> Node = getNode(Result.Nodes, ID);
+    if (!Node)
+      return Node.takeError();
+    return tooling::getExtendedRange(*Node, tok::TokenKind::semi,
+                                     *Result.Context);
+  };
+}
+
+RangeSelector transformer::range(RangeSelector Begin, RangeSelector End) {
+  return [Begin, End](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<CharSourceRange> BeginRange = Begin(Result);
+    if (!BeginRange)
+      return BeginRange.takeError();
+    Expected<CharSourceRange> EndRange = End(Result);
+    if (!EndRange)
+      return EndRange.takeError();
+    SourceLocation B = BeginRange->getBegin();
+    SourceLocation E = EndRange->getEnd();
+    // Note: we are precluding the possibility of sub-token ranges in the case
+    // that EndRange is a token range.
+    if (Result.SourceManager->isBeforeInTranslationUnit(E, B)) {
+      return invalidArgumentError("Bad range: out of order");
+    }
+    return CharSourceRange(SourceRange(B, E), EndRange->isTokenRange());
+  };
+}
+
+RangeSelector transformer::range(std::string BeginID, std::string EndID) {
+  return transformer::range(node(std::move(BeginID)), node(std::move(EndID)));
+}
+
+RangeSelector transformer::member(std::string ID) {
+  return [ID](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<DynTypedNode> Node = getNode(Result.Nodes, ID);
+    if (!Node)
+      return Node.takeError();
+    if (auto *M = Node->get<clang::MemberExpr>())
+      return CharSourceRange::getTokenRange(
+          M->getMemberNameInfo().getSourceRange());
+    return typeError(ID, Node->getNodeKind(), "MemberExpr");
+  };
+}
+
+RangeSelector transformer::name(std::string ID) {
+  return [ID](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<DynTypedNode> N = getNode(Result.Nodes, ID);
+    if (!N)
+      return N.takeError();
+    auto &Node = *N;
+    if (const auto *D = Node.get<NamedDecl>()) {
+      if (!D->getDeclName().isIdentifier())
+        return missingPropertyError(ID, "name", "identifier");
+      SourceLocation L = D->getLocation();
+      auto R = CharSourceRange::getTokenRange(L, L);
+      // Verify that the range covers exactly the name.
+      // FIXME: extend this code to support cases like `operator +` or
+      // `foo<int>` for which this range will be too short.  Doing so will
+      // require subcasing `NamedDecl`, because it doesn't provide virtual
+      // access to the \c DeclarationNameInfo.
+      if (tooling::getText(R, *Result.Context) != D->getName())
+        return CharSourceRange();
+      return R;
+    }
+    if (const auto *E = Node.get<DeclRefExpr>()) {
+      if (!E->getNameInfo().getName().isIdentifier())
+        return missingPropertyError(ID, "name", "identifier");
+      SourceLocation L = E->getLocation();
+      return CharSourceRange::getTokenRange(L, L);
+    }
+    if (const auto *I = Node.get<CXXCtorInitializer>()) {
+      if (!I->isMemberInitializer() && I->isWritten())
+        return missingPropertyError(ID, "name", "explicit member initializer");
+      SourceLocation L = I->getMemberLocation();
+      return CharSourceRange::getTokenRange(L, L);
+    }
+    return typeError(ID, Node.getNodeKind(),
+                     "DeclRefExpr, NamedDecl, CXXCtorInitializer");
+  };
+}
+
+namespace {
+// FIXME: make this available in the public API for users to easily create their
+// own selectors.
+
+// Creates a selector from a range-selection function \p Func, which selects a
+// range that is relative to a bound node id.  \c T is the node type expected by
+// \p Func.
+template <typename T, CharSourceRange (*Func)(const MatchResult &, const T &)>
+class RelativeSelector {
+  std::string ID;
+
+public:
+  RelativeSelector(std::string ID) : ID(std::move(ID)) {}
+
+  Expected<CharSourceRange> operator()(const MatchResult &Result) {
+    Expected<DynTypedNode> N = getNode(Result.Nodes, ID);
+    if (!N)
+      return N.takeError();
+    if (const auto *Arg = N->get<T>())
+      return Func(Result, *Arg);
+    return typeError(ID, N->getNodeKind());
+  }
+};
+} // namespace
+
+// FIXME: Change the following functions from being in an anonymous namespace
+// to static functions, after the minimum Visual C++ has _MSC_VER >= 1915
+// (equivalent to Visual Studio 2017 v15.8 or higher). Using the anonymous
+// namespace works around a bug in earlier versions.
+namespace {
+// Returns the range of the statements (all source between the braces).
+CharSourceRange getStatementsRange(const MatchResult &,
+                                   const CompoundStmt &CS) {
+  return CharSourceRange::getCharRange(CS.getLBracLoc().getLocWithOffset(1),
+                                       CS.getRBracLoc());
+}
+} // namespace
+
+RangeSelector transformer::statements(std::string ID) {
+  return RelativeSelector<CompoundStmt, getStatementsRange>(std::move(ID));
+}
+
+namespace {
+// Returns the range of the source between the call's parentheses.
+CharSourceRange getCallArgumentsRange(const MatchResult &Result,
+                                      const CallExpr &CE) {
+  return CharSourceRange::getCharRange(
+      findOpenParen(CE, *Result.SourceManager, Result.Context->getLangOpts())
+          .getLocWithOffset(1),
+      CE.getRParenLoc());
+}
+} // namespace
+
+RangeSelector transformer::callArgs(std::string ID) {
+  return RelativeSelector<CallExpr, getCallArgumentsRange>(std::move(ID));
+}
+
+namespace {
+// Returns the range of the elements of the initializer list. Includes all
+// source between the braces.
+CharSourceRange getElementsRange(const MatchResult &,
+                                 const InitListExpr &E) {
+  return CharSourceRange::getCharRange(E.getLBraceLoc().getLocWithOffset(1),
+                                       E.getRBraceLoc());
+}
+} // namespace
+
+RangeSelector transformer::initListElements(std::string ID) {
+  return RelativeSelector<InitListExpr, getElementsRange>(std::move(ID));
+}
+
+namespace {
+// Returns the range of the else branch, including the `else` keyword.
+CharSourceRange getElseRange(const MatchResult &Result, const IfStmt &S) {
+  return tooling::maybeExtendRange(
+      CharSourceRange::getTokenRange(S.getElseLoc(), S.getEndLoc()),
+      tok::TokenKind::semi, *Result.Context);
+}
+} // namespace
+
+RangeSelector transformer::elseBranch(std::string ID) {
+  return RelativeSelector<IfStmt, getElseRange>(std::move(ID));
+}
+
+RangeSelector transformer::expansion(RangeSelector S) {
+  return [S](const MatchResult &Result) -> Expected<CharSourceRange> {
+    Expected<CharSourceRange> SRange = S(Result);
+    if (!SRange)
+      return SRange.takeError();
+    return Result.SourceManager->getExpansionRange(*SRange);
+  };
+}
diff --git a/lib/Tooling/Transformer/RewriteRule.cpp b/lib/Tooling/Transformer/RewriteRule.cpp
new file mode 100644
index 000000000000..6fa558f7b2ee
--- /dev/null
+++ b/lib/Tooling/Transformer/RewriteRule.cpp
@@ -0,0 +1,178 @@
+//===--- Transformer.cpp - Transformer library implementation ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Transformer/RewriteRule.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Tooling/Transformer/SourceCode.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Errc.h"
+#include "llvm/Support/Error.h"
+#include <map>
+#include <string>
+#include <utility>
+#include <vector>
+
+using namespace clang;
+using namespace transformer;
+
+using ast_matchers::MatchFinder;
+using ast_matchers::internal::DynTypedMatcher;
+using ast_type_traits::ASTNodeKind;
+
+using MatchResult = MatchFinder::MatchResult;
+
+Expected<SmallVector<transformer::detail::Transformation, 1>>
+transformer::detail::translateEdits(const MatchResult &Result,
+                                llvm::ArrayRef<ASTEdit> Edits) {
+  SmallVector<transformer::detail::Transformation, 1> Transformations;
+  for (const auto &Edit : Edits) {
+    Expected<CharSourceRange> Range = Edit.TargetRange(Result);
+    if (!Range)
+      return Range.takeError();
+    llvm::Optional<CharSourceRange> EditRange =
+        tooling::getRangeForEdit(*Range, *Result.Context);
+    // FIXME: let user specify whether to treat this case as an error or ignore
+    // it as is currently done.
+    if (!EditRange)
+      return SmallVector<Transformation, 0>();
+    auto Replacement = Edit.Replacement(Result);
+    if (!Replacement)
+      return Replacement.takeError();
+    transformer::detail::Transformation T;
+    T.Range = *EditRange;
+    T.Replacement = std::move(*Replacement);
+    Transformations.push_back(std::move(T));
+  }
+  return Transformations;
+}
+
+ASTEdit transformer::change(RangeSelector S, TextGenerator Replacement) {
+  ASTEdit E;
+  E.TargetRange = std::move(S);
+  E.Replacement = std::move(Replacement);
+  return E;
+}
+
+RewriteRule transformer::makeRule(DynTypedMatcher M, SmallVector<ASTEdit, 1> Edits,
+                              TextGenerator Explanation) {
+  return RewriteRule{{RewriteRule::Case{
+      std::move(M), std::move(Edits), std::move(Explanation), {}}}};
+}
+
+void transformer::addInclude(RewriteRule &Rule, StringRef Header,
+                         IncludeFormat Format) {
+  for (auto &Case : Rule.Cases)
+    Case.AddedIncludes.emplace_back(Header.str(), Format);
+}
+
+#ifndef NDEBUG
+// Filters for supported matcher kinds. FIXME: Explicitly list the allowed kinds
+// (all node matcher types except for `QualType` and `Type`), rather than just
+// banning `QualType` and `Type`.
+static bool hasValidKind(const DynTypedMatcher &M) {
+  return !M.canConvertTo<QualType>();
+}
+#endif
+
+// Binds each rule's matcher to a unique (and deterministic) tag based on
+// `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());
+  for (const auto &Case : Cases) {
+    std::string Tag = (TagBase + Twine(Case.first)).str();
+    // HACK: Many matchers are not bindable, so ensure that tryBind will work.
+    DynTypedMatcher BoundMatcher(Case.second.Matcher);
+    BoundMatcher.setAllowBind(true);
+    auto M = BoundMatcher.tryBind(Tag);
+    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 transformer::applyFirst(ArrayRef<RewriteRule> Rules) {
+  RewriteRule R;
+  for (auto &Rule : Rules)
+    R.Cases.append(Rule.Cases.begin(), Rule.Cases.end());
+  return R;
+}
+
+std::vector<DynTypedMatcher>
+transformer::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) {
+    assert(hasValidKind(Cases[I].Matcher) &&
+           "Matcher must be non-(Qual)Type node matcher");
+    Buckets[Cases[I].Matcher.getSupportedKind()].emplace_back(I, Cases[I]);
+  }
+
+  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 transformer::detail::buildMatcher(const RewriteRule &Rule) {
+  std::vector<DynTypedMatcher> Ms = buildMatchers(Rule);
+  assert(Ms.size() == 1 && "Cases must have compatible matchers.");
+  return Ms[0];
+}
+
+SourceLocation transformer::detail::getRuleMatchLoc(const MatchResult &Result) {
+  auto &NodesMap = Result.Nodes.getMap();
+  auto Root = NodesMap.find(RewriteRule::RootID);
+  assert(Root != NodesMap.end() && "Transformation failed: missing root node.");
+  llvm::Optional<CharSourceRange> RootRange = tooling::getRangeForEdit(
+      CharSourceRange::getTokenRange(Root->second.getSourceRange()),
+      *Result.Context);
+  if (RootRange)
+    return RootRange->getBegin();
+  // The match doesn't have a coherent range, so fall back to the expansion
+  // location as the "beginning" of the match.
+  return Result.SourceManager->getExpansionLoc(
+      Root->second.getSourceRange().getBegin());
+}
+
+// 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) {
+  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;
diff --git a/lib/Tooling/Transformer/SourceCode.cpp b/lib/Tooling/Transformer/SourceCode.cpp
new file mode 100644
index 000000000000..836401d1e605
--- /dev/null
+++ b/lib/Tooling/Transformer/SourceCode.cpp
@@ -0,0 +1,65 @@
+//===--- SourceCode.cpp - Source code manipulation routines -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file provides functions that simplify extraction of source code.
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Transformer/SourceCode.h"
+#include "clang/Lex/Lexer.h"
+
+using namespace clang;
+
+StringRef clang::tooling::getText(CharSourceRange Range,
+                                  const ASTContext &Context) {
+  return Lexer::getSourceText(Range, Context.getSourceManager(),
+                              Context.getLangOpts());
+}
+
+CharSourceRange clang::tooling::maybeExtendRange(CharSourceRange Range,
+                                                 tok::TokenKind Next,
+                                                 ASTContext &Context) {
+  Optional<Token> Tok = Lexer::findNextToken(
+      Range.getEnd(), Context.getSourceManager(), Context.getLangOpts());
+  if (!Tok || !Tok->is(Next))
+    return Range;
+  return CharSourceRange::getTokenRange(Range.getBegin(), Tok->getLocation());
+}
+
+llvm::Optional<CharSourceRange>
+clang::tooling::getRangeForEdit(const CharSourceRange &EditRange,
+                                const SourceManager &SM,
+                                const LangOptions &LangOpts) {
+  // FIXME: makeFileCharRange() has the disadvantage of stripping off "identity"
+  // macros. For example, if we're looking to rewrite the int literal 3 to 6,
+  // and we have the following definition:
+  //    #define DO_NOTHING(x) x
+  // then
+  //    foo(DO_NOTHING(3))
+  // will be rewritten to
+  //    foo(6)
+  // rather than the arguably better
+  //    foo(DO_NOTHING(6))
+  // Decide whether the current behavior is desirable and modify if not.
+  CharSourceRange Range = Lexer::makeFileCharRange(EditRange, SM, LangOpts);
+  if (Range.isInvalid())
+    return None;
+
+  if (Range.getBegin().isMacroID() || Range.getEnd().isMacroID())
+    return None;
+  if (SM.isInSystemHeader(Range.getBegin()) ||
+      SM.isInSystemHeader(Range.getEnd()))
+    return None;
+
+  std::pair<FileID, unsigned> BeginInfo = SM.getDecomposedLoc(Range.getBegin());
+  std::pair<FileID, unsigned> EndInfo = SM.getDecomposedLoc(Range.getEnd());
+  if (BeginInfo.first != EndInfo.first ||
+      BeginInfo.second > EndInfo.second)
+    return None;
+
+  return Range;
+}
diff --git a/lib/Tooling/Transformer/SourceCodeBuilders.cpp b/lib/Tooling/Transformer/SourceCodeBuilders.cpp
new file mode 100644
index 000000000000..56ec45e8fd1d
--- /dev/null
+++ b/lib/Tooling/Transformer/SourceCodeBuilders.cpp
@@ -0,0 +1,160 @@
+//===--- SourceCodeBuilder.cpp ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Transformer/SourceCodeBuilders.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/Tooling/Transformer/SourceCode.h"
+#include "llvm/ADT/Twine.h"
+#include <string>
+
+using namespace clang;
+using namespace tooling;
+
+const Expr *tooling::reallyIgnoreImplicit(const Expr &E) {
+  const Expr *Expr = E.IgnoreImplicit();
+  if (const auto *CE = dyn_cast<CXXConstructExpr>(Expr)) {
+    if (CE->getNumArgs() > 0 &&
+        CE->getArg(0)->getSourceRange() == Expr->getSourceRange())
+      return CE->getArg(0)->IgnoreImplicit();
+  }
+  return Expr;
+}
+
+bool tooling::mayEverNeedParens(const Expr &E) {
+  const Expr *Expr = reallyIgnoreImplicit(E);
+  // We always want parens around unary, binary, and ternary operators, because
+  // they are lower precedence.
+  if (isa<UnaryOperator>(Expr) || isa<BinaryOperator>(Expr) ||
+      isa<AbstractConditionalOperator>(Expr))
+    return true;
+
+  // We need parens around calls to all overloaded operators except: function
+  // calls, subscripts, and expressions that are already part of an (implicit)
+  // call to operator->. These latter are all in the same precedence level as
+  // dot/arrow and that level is left associative, so they don't need parens
+  // when appearing on the left.
+  if (const auto *Op = dyn_cast<CXXOperatorCallExpr>(Expr))
+    return Op->getOperator() != OO_Call && Op->getOperator() != OO_Subscript &&
+           Op->getOperator() != OO_Arrow;
+
+  return false;
+}
+
+bool tooling::needParensAfterUnaryOperator(const Expr &E) {
+  const Expr *Expr = reallyIgnoreImplicit(E);
+  if (isa<BinaryOperator>(Expr) || isa<AbstractConditionalOperator>(Expr))
+    return true;
+
+  if (const auto *Op = dyn_cast<CXXOperatorCallExpr>(Expr))
+    return Op->getNumArgs() == 2 && Op->getOperator() != OO_PlusPlus &&
+           Op->getOperator() != OO_MinusMinus && Op->getOperator() != OO_Call &&
+           Op->getOperator() != OO_Subscript;
+
+  return false;
+}
+
+llvm::Optional<std::string> tooling::buildParens(const Expr &E,
+                                                 const ASTContext &Context) {
+  StringRef Text = getText(E, Context);
+  if (Text.empty())
+    return llvm::None;
+  if (mayEverNeedParens(E))
+    return ("(" + Text + ")").str();
+  return Text.str();
+}
+
+llvm::Optional<std::string>
+tooling::buildDereference(const Expr &E, const ASTContext &Context) {
+  if (const auto *Op = dyn_cast<UnaryOperator>(&E))
+    if (Op->getOpcode() == UO_AddrOf) {
+      // Strip leading '&'.
+      StringRef Text =
+          getText(*Op->getSubExpr()->IgnoreParenImpCasts(), Context);
+      if (Text.empty())
+        return llvm::None;
+      return Text.str();
+    }
+
+  StringRef Text = getText(E, Context);
+  if (Text.empty())
+    return llvm::None;
+  // Add leading '*'.
+  if (needParensAfterUnaryOperator(E))
+    return ("*(" + Text + ")").str();
+  return ("*" + Text).str();
+}
+
+llvm::Optional<std::string> tooling::buildAddressOf(const Expr &E,
+                                                    const ASTContext &Context) {
+  if (const auto *Op = dyn_cast<UnaryOperator>(&E))
+    if (Op->getOpcode() == UO_Deref) {
+      // Strip leading '*'.
+      StringRef Text =
+          getText(*Op->getSubExpr()->IgnoreParenImpCasts(), Context);
+      if (Text.empty())
+        return llvm::None;
+      return Text.str();
+    }
+  // Add leading '&'.
+  StringRef Text = getText(E, Context);
+  if (Text.empty())
+    return llvm::None;
+  if (needParensAfterUnaryOperator(E)) {
+    return ("&(" + Text + ")").str();
+  }
+  return ("&" + Text).str();
+}
+
+llvm::Optional<std::string> tooling::buildDot(const Expr &E,
+                                              const ASTContext &Context) {
+  if (const auto *Op = llvm::dyn_cast<UnaryOperator>(&E))
+    if (Op->getOpcode() == UO_Deref) {
+      // Strip leading '*', add following '->'.
+      const Expr *SubExpr = Op->getSubExpr()->IgnoreParenImpCasts();
+      StringRef DerefText = getText(*SubExpr, Context);
+      if (DerefText.empty())
+        return llvm::None;
+      if (needParensBeforeDotOrArrow(*SubExpr))
+        return ("(" + DerefText + ")->").str();
+      return (DerefText + "->").str();
+    }
+
+  // Add following '.'.
+  StringRef Text = getText(E, Context);
+  if (Text.empty())
+    return llvm::None;
+  if (needParensBeforeDotOrArrow(E)) {
+    return ("(" + Text + ").").str();
+  }
+  return (Text + ".").str();
+}
+
+llvm::Optional<std::string> tooling::buildArrow(const Expr &E,
+                                                const ASTContext &Context) {
+  if (const auto *Op = llvm::dyn_cast<UnaryOperator>(&E))
+    if (Op->getOpcode() == UO_AddrOf) {
+      // Strip leading '&', add following '.'.
+      const Expr *SubExpr = Op->getSubExpr()->IgnoreParenImpCasts();
+      StringRef DerefText = getText(*SubExpr, Context);
+      if (DerefText.empty())
+        return llvm::None;
+      if (needParensBeforeDotOrArrow(*SubExpr))
+        return ("(" + DerefText + ").").str();
+      return (DerefText + ".").str();
+    }
+
+  // Add following '->'.
+  StringRef Text = getText(E, Context);
+  if (Text.empty())
+    return llvm::None;
+  if (needParensBeforeDotOrArrow(E))
+    return ("(" + Text + ")->").str();
+  return (Text + "->").str();
+}
diff --git a/lib/Tooling/Transformer/Stencil.cpp b/lib/Tooling/Transformer/Stencil.cpp
new file mode 100644
index 000000000000..984950a54e96
--- /dev/null
+++ b/lib/Tooling/Transformer/Stencil.cpp
@@ -0,0 +1,318 @@
+//===--- Stencil.cpp - Stencil implementation -------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Transformer/Stencil.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/Expr.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Tooling/Transformer/SourceCode.h"
+#include "clang/Tooling/Transformer/SourceCodeBuilders.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/Errc.h"
+#include <atomic>
+#include <memory>
+#include <string>
+
+using namespace clang;
+using namespace transformer;
+
+using ast_matchers::MatchFinder;
+using ast_type_traits::DynTypedNode;
+using llvm::errc;
+using llvm::Error;
+using llvm::Expected;
+using llvm::StringError;
+
+static llvm::Expected<DynTypedNode>
+getNode(const ast_matchers::BoundNodes &Nodes, StringRef Id) {
+  auto &NodesMap = Nodes.getMap();
+  auto It = NodesMap.find(Id);
+  if (It == NodesMap.end())
+    return llvm::make_error<llvm::StringError>(llvm::errc::invalid_argument,
+                                               "Id not bound: " + Id);
+  return It->second;
+}
+
+namespace {
+// An arbitrary fragment of code within a stencil.
+struct RawTextData {
+  explicit RawTextData(std::string T) : Text(std::move(T)) {}
+  std::string Text;
+};
+
+// A debugging operation to dump the AST for a particular (bound) AST node.
+struct DebugPrintNodeData {
+  explicit DebugPrintNodeData(std::string S) : Id(std::move(S)) {}
+  std::string Id;
+};
+
+// Operators that take a single node Id as an argument.
+enum class UnaryNodeOperator {
+  Parens,
+  Deref,
+  Address,
+};
+
+// Generic container for stencil operations with a (single) node-id argument.
+struct UnaryOperationData {
+  UnaryOperationData(UnaryNodeOperator Op, std::string Id)
+      : Op(Op), Id(std::move(Id)) {}
+  UnaryNodeOperator Op;
+  std::string Id;
+};
+
+// The fragment of code corresponding to the selected range.
+struct SelectorData {
+  explicit SelectorData(RangeSelector S) : Selector(std::move(S)) {}
+  RangeSelector Selector;
+};
+
+// A stencil operation to build a member access `e.m` or `e->m`, as appropriate.
+struct AccessData {
+  AccessData(StringRef BaseId, StencilPart Member)
+      : BaseId(BaseId), Member(std::move(Member)) {}
+  std::string BaseId;
+  StencilPart Member;
+};
+
+struct IfBoundData {
+  IfBoundData(StringRef Id, StencilPart TruePart, StencilPart FalsePart)
+      : Id(Id), TruePart(std::move(TruePart)), FalsePart(std::move(FalsePart)) {
+  }
+  std::string Id;
+  StencilPart TruePart;
+  StencilPart FalsePart;
+};
+
+std::string toStringData(const RawTextData &Data) {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+  OS << "\"";
+  OS.write_escaped(Data.Text);
+  OS << "\"";
+  OS.flush();
+  return Result;
+}
+
+std::string toStringData(const DebugPrintNodeData &Data) {
+  return (llvm::Twine("dPrint(\"") + Data.Id + "\")").str();
+}
+
+std::string toStringData(const UnaryOperationData &Data) {
+  StringRef OpName;
+  switch (Data.Op) {
+  case UnaryNodeOperator::Parens:
+    OpName = "expression";
+    break;
+  case UnaryNodeOperator::Deref:
+    OpName = "deref";
+    break;
+  case UnaryNodeOperator::Address:
+    OpName = "addressOf";
+    break;
+  }
+  return (OpName + "(\"" + Data.Id + "\")").str();
+}
+
+std::string toStringData(const SelectorData &) { return "selection(...)"; }
+
+std::string toStringData(const AccessData &Data) {
+  return (llvm::Twine("access(\"") + Data.BaseId + "\", " +
+          Data.Member.toString() + ")")
+      .str();
+}
+
+std::string toStringData(const IfBoundData &Data) {
+  return (llvm::Twine("ifBound(\"") + Data.Id + "\", " +
+          Data.TruePart.toString() + ", " + Data.FalsePart.toString() + ")")
+      .str();
+}
+
+std::string toStringData(const MatchConsumer<std::string> &) {
+  return "run(...)";
+}
+
+// The `evalData()` overloads evaluate the given stencil data to a string, given
+// the match result, and append it to `Result`. We define an overload for each
+// type of stencil data.
+
+Error evalData(const RawTextData &Data, const MatchFinder::MatchResult &,
+               std::string *Result) {
+  Result->append(Data.Text);
+  return Error::success();
+}
+
+Error evalData(const DebugPrintNodeData &Data,
+               const MatchFinder::MatchResult &Match, std::string *Result) {
+  std::string Output;
+  llvm::raw_string_ostream Os(Output);
+  auto NodeOrErr = getNode(Match.Nodes, Data.Id);
+  if (auto Err = NodeOrErr.takeError())
+    return Err;
+  NodeOrErr->print(Os, PrintingPolicy(Match.Context->getLangOpts()));
+  *Result += Os.str();
+  return Error::success();
+}
+
+Error evalData(const UnaryOperationData &Data,
+               const MatchFinder::MatchResult &Match, std::string *Result) {
+  const auto *E = Match.Nodes.getNodeAs<Expr>(Data.Id);
+  if (E == nullptr)
+    return llvm::make_error<StringError>(
+        errc::invalid_argument, "Id not bound or not Expr: " + Data.Id);
+  llvm::Optional<std::string> Source;
+  switch (Data.Op) {
+  case UnaryNodeOperator::Parens:
+    Source = tooling::buildParens(*E, *Match.Context);
+    break;
+  case UnaryNodeOperator::Deref:
+    Source = tooling::buildDereference(*E, *Match.Context);
+    break;
+  case UnaryNodeOperator::Address:
+    Source = tooling::buildAddressOf(*E, *Match.Context);
+    break;
+  }
+  if (!Source)
+    return llvm::make_error<StringError>(
+        errc::invalid_argument,
+        "Could not construct expression source from ID: " + Data.Id);
+  *Result += *Source;
+  return Error::success();
+}
+
+Error evalData(const SelectorData &Data, const MatchFinder::MatchResult &Match,
+               std::string *Result) {
+  auto Range = Data.Selector(Match);
+  if (!Range)
+    return Range.takeError();
+  *Result += tooling::getText(*Range, *Match.Context);
+  return Error::success();
+}
+
+Error evalData(const AccessData &Data, const MatchFinder::MatchResult &Match,
+               std::string *Result) {
+  const auto *E = Match.Nodes.getNodeAs<Expr>(Data.BaseId);
+  if (E == nullptr)
+    return llvm::make_error<StringError>(errc::invalid_argument,
+                                         "Id not bound: " + Data.BaseId);
+  if (!E->isImplicitCXXThis()) {
+    if (llvm::Optional<std::string> S =
+            E->getType()->isAnyPointerType()
+                ? tooling::buildArrow(*E, *Match.Context)
+                : tooling::buildDot(*E, *Match.Context))
+      *Result += *S;
+    else
+      return llvm::make_error<StringError>(
+          errc::invalid_argument,
+          "Could not construct object text from ID: " + Data.BaseId);
+  }
+  return Data.Member.eval(Match, Result);
+}
+
+Error evalData(const IfBoundData &Data, const MatchFinder::MatchResult &Match,
+               std::string *Result) {
+  auto &M = Match.Nodes.getMap();
+  return (M.find(Data.Id) != M.end() ? Data.TruePart : Data.FalsePart)
+      .eval(Match, Result);
+}
+
+Error evalData(const MatchConsumer<std::string> &Fn,
+               const MatchFinder::MatchResult &Match, std::string *Result) {
+  Expected<std::string> Value = Fn(Match);
+  if (!Value)
+    return Value.takeError();
+  *Result += *Value;
+  return Error::success();
+}
+
+template <typename T>
+class StencilPartImpl : public StencilPartInterface {
+  T Data;
+
+public:
+  template <typename... Ps>
+  explicit StencilPartImpl(Ps &&... Args) : Data(std::forward<Ps>(Args)...) {}
+
+  Error eval(const MatchFinder::MatchResult &Match,
+             std::string *Result) const override {
+    return evalData(Data, Match, Result);
+  }
+
+  std::string toString() const override { return toStringData(Data); }
+};
+} // namespace
+
+StencilPart Stencil::wrap(StringRef Text) {
+  return transformer::text(Text);
+}
+
+StencilPart Stencil::wrap(RangeSelector Selector) {
+  return transformer::selection(std::move(Selector));
+}
+
+void Stencil::append(Stencil OtherStencil) {
+  for (auto &Part : OtherStencil.Parts)
+    Parts.push_back(std::move(Part));
+}
+
+llvm::Expected<std::string>
+Stencil::eval(const MatchFinder::MatchResult &Match) const {
+  std::string Result;
+  for (const auto &Part : Parts)
+    if (auto Err = Part.eval(Match, &Result))
+      return std::move(Err);
+  return Result;
+}
+
+StencilPart transformer::text(StringRef Text) {
+  return StencilPart(std::make_shared<StencilPartImpl<RawTextData>>(Text));
+}
+
+StencilPart transformer::selection(RangeSelector Selector) {
+  return StencilPart(
+      std::make_shared<StencilPartImpl<SelectorData>>(std::move(Selector)));
+}
+
+StencilPart transformer::dPrint(StringRef Id) {
+  return StencilPart(std::make_shared<StencilPartImpl<DebugPrintNodeData>>(Id));
+}
+
+StencilPart transformer::expression(llvm::StringRef Id) {
+  return StencilPart(std::make_shared<StencilPartImpl<UnaryOperationData>>(
+      UnaryNodeOperator::Parens, Id));
+}
+
+StencilPart transformer::deref(llvm::StringRef ExprId) {
+  return StencilPart(std::make_shared<StencilPartImpl<UnaryOperationData>>(
+      UnaryNodeOperator::Deref, ExprId));
+}
+
+StencilPart transformer::addressOf(llvm::StringRef ExprId) {
+  return StencilPart(std::make_shared<StencilPartImpl<UnaryOperationData>>(
+      UnaryNodeOperator::Address, ExprId));
+}
+
+StencilPart transformer::access(StringRef BaseId, StencilPart Member) {
+  return StencilPart(
+      std::make_shared<StencilPartImpl<AccessData>>(BaseId, std::move(Member)));
+}
+
+StencilPart transformer::ifBound(StringRef Id, StencilPart TruePart,
+                             StencilPart FalsePart) {
+  return StencilPart(std::make_shared<StencilPartImpl<IfBoundData>>(
+      Id, std::move(TruePart), std::move(FalsePart)));
+}
+
+StencilPart transformer::run(MatchConsumer<std::string> Fn) {
+  return StencilPart(
+      std::make_shared<StencilPartImpl<MatchConsumer<std::string>>>(
+          std::move(Fn)));
+}
diff --git a/lib/Tooling/Transformer/Transformer.cpp b/lib/Tooling/Transformer/Transformer.cpp
new file mode 100644
index 000000000000..71f0646f4c0e
--- /dev/null
+++ b/lib/Tooling/Transformer/Transformer.cpp
@@ -0,0 +1,72 @@
+//===--- Transformer.cpp - Transformer library implementation ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Transformer/Transformer.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchersInternal.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Tooling/Refactoring/AtomicChange.h"
+#include "llvm/Support/Error.h"
+#include <utility>
+#include <vector>
+
+using namespace clang;
+using namespace tooling;
+
+using ast_matchers::MatchFinder;
+
+void Transformer::registerMatchers(MatchFinder *MatchFinder) {
+  for (auto &Matcher : transformer::detail::buildMatchers(Rule))
+    MatchFinder->addDynamicMatcher(Matcher, this);
+}
+
+void Transformer::run(const MatchFinder::MatchResult &Result) {
+  if (Result.Context->getDiagnostics().hasErrorOccurred())
+    return;
+
+  transformer::RewriteRule::Case Case =
+      transformer::detail::findSelectedCase(Result, Rule);
+  auto Transformations = transformer::detail::translateEdits(Result, Case.Edits);
+  if (!Transformations) {
+    Consumer(Transformations.takeError());
+    return;
+  }
+
+  if (Transformations->empty()) {
+    // No rewrite applied (but no error encountered either).
+    transformer::detail::getRuleMatchLoc(Result).print(
+        llvm::errs() << "note: skipping match at loc ", *Result.SourceManager);
+    llvm::errs() << "\n";
+    return;
+  }
+
+  // Record the results in the AtomicChange, anchored at the location of the
+  // first change.
+  AtomicChange AC(*Result.SourceManager,
+                  (*Transformations)[0].Range.getBegin());
+  for (const auto &T : *Transformations) {
+    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 transformer::IncludeFormat::Quoted:
+      AC.addHeader(Header);
+      break;
+    case transformer::IncludeFormat::Angled:
+      AC.addHeader((llvm::Twine("<") + Header + ">").str());
+      break;
+    }
+  }
+
+  Consumer(std::move(AC));
+}