[clang-diff] Initial implementation of patching

[johannes]

Summary

This commit adds a function diff::patch that takes three syntax trees
as inputs: a source, a destination and a target. It tries to apply the
differences between source and destination to target. Currently,
comments and preprocessor statements are ignored.

[arphaman]

I don't think AST manipulation is the right way to do patching. You've already hit the limitations here in this patch where you can't really remove a statement unless its parent is a CompoundStmt.

I think the right way to do AST patching is to take a 3rd AST(lets call it a target AST), find the set of matching nodes that correspond to all nodes that have to be patched and then perform patching by rewriting the source for the target AST.
Let's say you want to start with remove. If you take the following files:

$ cat src.cpp
void printf(const char *, ...);
void foo(int x) {
  printf("%d", x, x);
}
$ cat dst.cpp
void printf(const char *, ...);
void foo(int x) {
  printf("%d", x); // the second 'x' is removed.
}
$ cat target.cpp
void printf(const char *, ...);
void foo(int x) {
  printf("different string %d", x, x);
}

You'll find that the difference between src.cpp and dst.cpp is Delete DeclRefExpr: x(10). Then you can take target.cpp, find the matching DeclRefExpr node, and create a source replacement (see tooling's Replacement) that removes ", x" from target.cpp.

[johannes]

use rewriter to patch a third AST

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

455

You can drop the auto *Arg since Arg is unused.

1365

Please move the patcher into a new file.

[johannes]

split to ASTDiff/ASTPatch

[arphaman]

include/clang/Tooling/ASTDiff/ASTPatch.h

2

Please update the file name in the comment

lib/Tooling/ASTDiff/ASTDiff.cpp

456

You might as well return early here and avoid else entirely

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiff.h

81

Why do you need to create an empty tree? What about using llvm::Optional instead?

88

It's fine to have = default in the header

[johannes]

fixes

include/clang/Tooling/ASTDiff/ASTDiff.h

81

ok, i use optional now instead in the unittest

[johannes]

update

include/clang/Tooling/ASTDiff/ASTDiff.h

 private:
   std::unique_ptr<Impl> DiffImpl;
 };
 
 /// SyntaxTree objects represent subtrees of the AST.
 /// They can be constructed from any Decl or Stmt.
 class SyntaxTree {
 public:
   /// Constructs a tree from a translation unit.
   SyntaxTree(ASTUnit &AST);
   /// Constructs a tree from any AST node.
   template <class T>
   SyntaxTree(T *Node, ASTUnit &AST)
       : TreeImpl(llvm::make_unique<Impl>(this, Node, AST)) {}
   SyntaxTree(SyntaxTree &&Other) = default;
   SyntaxTree &operator=(SyntaxTree &&Other) = default;
   ~SyntaxTree();
 
   ASTUnit &getASTUnit() const;
   const ASTContext &getASTContext() const;
   SourceManager &getSourceManager() const;
   const LangOptions &getLangOpts() const;
   StringRef getFilename() const;
 
struct Node {
   /// CXXConstructExpr::getParentOrBraceRange(). So the class name will belong
   /// to the parent.
   CharSourceRange getSourceRange() const;
 
   /// Returns the sub-ranges of getSourceRange() that are exclusively owned by
   /// this node, that is, none of its descendants includes them.
   SmallVector<CharSourceRange, 4> getOwnedSourceRanges() const;
 
+  /// This differs from getSourceRange() in the sense that the range is extended
+  /// to include the trailing comma if the node is within a comma-separated
+  /// list.
+  CharSourceRange findRangeForDeletion() const;
+
   /// Returns the offsets for the range returned by getSourceRange().
   std::pair<unsigned, unsigned> getSourceRangeOffsets() const;
 
   /// Returns the starting locations of all tokens in getOwnedSourceRanges().
   SmallVector<SourceLocation, 4> getOwnedTokens() const;
 };
 
 void forEachTokenInRange(CharSourceRange Range, SyntaxTree &Tree,

include/clang/Tooling/ASTDiff/ASTPatch.h

+//===- ASTPatch.h - Structural patching based on ASTDiff ------*- C++ -*- -===//
+//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTPATCH_H
+#define LLVM_CLANG_TOOLING_ASTDIFF_ASTPATCH_H
+
+#include "clang/Tooling/ASTDiff/ASTDiff.h"
+#include "clang/Tooling/Refactoring.h"
+#include "llvm/Support/Error.h"
+
+namespace clang {
+namespace diff {
+
+enum class patching_error {
+  failed_to_build_AST,
+  failed_to_apply_replacements,
+  failed_to_overwrite_files,
+};
+
+class PatchingError : public llvm::ErrorInfo<PatchingError> {
+public:
+  PatchingError(patching_error Err) : Err(Err) {}
+  std::string message() const override;
+  void log(raw_ostream &OS) const override { OS << message() << "\n"; }
+  patching_error get() const { return Err; }
+  static char ID;
+
+private:
+  std::error_code convertToErrorCode() const override {
+    return llvm::inconvertibleErrorCode();
+  }
+  patching_error Err;
+};
+
+llvm::Error patch(tooling::RefactoringTool &TargetTool, SyntaxTree &Src,
+                  SyntaxTree &Dst, const ComparisonOptions &Options,
+                  bool Debug = false);
+
+} // end namespace diff
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_ASTDIFF_ASTPATCH_H

lib/Tooling/ASTDiff/ASTDiff.cpp

static HashType hashNode(NodeRef N) {
   }
   llvm::MD5::MD5Result HashResult;
   Hash.final(HashResult);
   return HashResult;
 }
 
 static bool areNodesDifferent(NodeRef N1, NodeRef N2) {
   return hashNode(N1) != hashNode(N2);
 }
 
 /// Identifies a node in a subtree by its postorder offset, starting at 1.
 struct SNodeId {
   int Id = 0;
 
   explicit SNodeId(int Id) : Id(Id) {}
   explicit SNodeId() = default;
 
   operator int() const { return Id; }
for (NodeRef Descendant : *this) {
     if (Max.isValid())
       Offset = Max;
     ++ChildIndex;
   }
   AddSegment(Range.getEnd());
   return SourceRanges;
 }
 
+CharSourceRange Node::findRangeForDeletion() const {
+  CharSourceRange Range = getSourceRange();
+  if (!getParent())
+    return Range;
+  NodeRef Parent = *getParent();
+  SyntaxTree &Tree = getTree();
+  SourceManager &SM = Tree.getSourceManager();
+  const LangOptions &LangOpts = Tree.getLangOpts();
+  auto &DTN = ASTNode;
+  auto &ParentDTN = Parent.ASTNode;
+  size_t SiblingIndex = findPositionInParent();
+  const auto &Siblings = Parent.Children;
+  // Remove the comma if the location is within a comma-separated list of
+  // at least size 2 (minus the callee for CallExpr).
+  if ((ParentDTN.get<CallExpr>() && Siblings.size() > 2) ||
+      (DTN.get<ParmVarDecl>() && Siblings.size() > 2)) {
+    bool LastSibling = SiblingIndex == Siblings.size() - 1;
+    SourceLocation CommaLoc;
+    if (LastSibling) {
+      CommaLoc = Parent.getChild(SiblingIndex - 1).getSourceRange().getEnd();
+      Range.setBegin(CommaLoc);
+    } else {
+      Optional<Token> Comma =
+          Lexer::findNextToken(Range.getEnd(), SM, LangOpts);
+      if (Comma && Comma->is(tok::comma))
+        Range.setEnd(Comma->getEndLoc());
+    }
+  }
+  return Range;
+}
+
 void forEachTokenInRange(CharSourceRange Range, SyntaxTree &Tree,
                          std::function<void(Token &)> Body) {
   SourceLocation Begin = Range.getBegin(), End = Range.getEnd();
   SourceManager &SM = Tree.getSourceManager();
   BeforeThanCompare<SourceLocation> Less(SM);
   Token Tok;
   while (Begin.isValid() && Less(Begin, End) &&
          !Lexer::getRawToken(Begin, Tok, SM, Tree.getLangOpts(),

 SyntaxTree::PostorderIterator SyntaxTree::postorder_end() const {
   return TreeImpl->postorder_end();
 }
 llvm::iterator_range<SyntaxTree::PostorderIterator>
 SyntaxTree::postorder() const {
   return TreeImpl->postorder();
 }
 
 } // end namespace diff
 } // end namespace clang

lib/Tooling/ASTDiff/ASTPatch.cpp

+//===- ASTPatch.cpp - Structural patching based on ASTDiff ----*- C++ -*- -===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/ASTDiff/ASTPatch.h"
+
+#include "clang/AST/DeclTemplate.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/Rewrite/Core/Rewriter.h"
+#include "clang/Tooling/Core/Replacement.h"
+
+using namespace llvm;
+using namespace clang;
+using namespace tooling;
+
+namespace clang {
+namespace diff {
+
+static Error error(patching_error code) {
+  return llvm::make_error<PatchingError>(code);
+};
+
+static CharSourceRange makeEmptyCharRange(SourceLocation Point) {
+  return CharSourceRange::getCharRange(Point, Point);
+}
+
+// Returns a comparison function that considers invalid source locations
+// to be less than anything.
+static std::function<bool(SourceLocation, SourceLocation)>
+makeTolerantLess(SourceManager &SM) {
+  return [&SM](SourceLocation A, SourceLocation B) {
+    if (A.isInvalid())
+      return true;
+    if (B.isInvalid())
+      return false;
+    BeforeThanCompare<SourceLocation> Less(SM);
+    return Less(A, B);
+  };
+}
+
+namespace {
+// This wraps a node from Patcher::Target or Patcher::Dst.
+class PatchedTreeNode {
+  NodeRef BaseNode;
+
+public:
+  operator NodeRef() const { return BaseNode; }
+  NodeRef originalNode() const { return *this; }
+  CharSourceRange getSourceRange() const { return BaseNode.getSourceRange(); }
+  NodeId getId() const { return BaseNode.getId(); }
+  SyntaxTree &getTree() const { return BaseNode.getTree(); }
+  StringRef getTypeLabel() const { return BaseNode.getTypeLabel(); }
+  decltype(BaseNode.getOwnedSourceRanges()) getOwnedSourceRanges() {
+    return BaseNode.getOwnedSourceRanges();
+  }
+
+  // This flag indicates whether this node, or any of its descendants was
+  // changed with regards to the original tree.
+  bool Changed = false;
+  // The pointers to the children, including nodes that have been inserted or
+  // moved here.
+  SmallVector<PatchedTreeNode *, 4> Children;
+  // First location for each child.
+  SmallVector<SourceLocation, 4> ChildrenLocations;
+  // The offsets at which the children should be inserted into OwnText.
+  SmallVector<unsigned, 4> ChildrenOffsets;
+
+  // This contains the text of this node, but not the text of it's children.
+  Optional<std::string> OwnText;
+
+  PatchedTreeNode(NodeRef BaseNode) : BaseNode(BaseNode) {}
+  PatchedTreeNode(const PatchedTreeNode &Other) = delete;
+  PatchedTreeNode(PatchedTreeNode &&Other) = default;
+
+  void addInsertion(PatchedTreeNode &PatchedNode, SourceLocation InsertionLoc) {
+    addChildAt(PatchedNode, InsertionLoc);
+  }
+  void addChild(PatchedTreeNode &PatchedNode) {
+    SourceLocation InsertionLoc = PatchedNode.getSourceRange().getBegin();
+    addChildAt(PatchedNode, InsertionLoc);
+  }
+
+private:
+  void addChildAt(PatchedTreeNode &PatchedNode, SourceLocation InsertionLoc) {
+    auto Less = makeTolerantLess(getTree().getSourceManager());
+    auto It = std::lower_bound(ChildrenLocations.begin(),
+                               ChildrenLocations.end(), InsertionLoc, Less);
+    auto Offset = It - ChildrenLocations.begin();
+    Children.insert(Children.begin() + Offset, &PatchedNode);
+    ChildrenLocations.insert(It, InsertionLoc);
+  }
+};
+} // end anonymous namespace
+
+namespace {
+class Patcher {
+  SyntaxTree &Dst, &Target;
+  SourceManager &SM;
+  const LangOptions &LangOpts;
+  BeforeThanCompare<SourceLocation> Less;
+  ASTDiff Diff, TargetDiff;
+  RefactoringTool &TargetTool;
+  bool Debug;
+  std::vector<PatchedTreeNode> PatchedTreeNodes;
+  std::map<NodeId, PatchedTreeNode *> InsertedNodes;
+  // Maps NodeId in Dst to a flag that is true if this node is
+  // part of an inserted subtree.
+  std::vector<bool> AtomicInsertions;
+
+public:
+  Patcher(SyntaxTree &Src, SyntaxTree &Dst, SyntaxTree &Target,
+          const ComparisonOptions &Options, RefactoringTool &TargetTool,
+          bool Debug)
+      : Dst(Dst), Target(Target), SM(Target.getSourceManager()),
+        LangOpts(Target.getLangOpts()), Less(SM), Diff(Src, Dst, Options),
+        TargetDiff(Src, Target, Options), TargetTool(TargetTool), Debug(Debug) {
+  }
+
+  Error apply();
+
+private:
+  void buildPatchedTree();
+  void addInsertedAndMovedNodes();
+  SourceLocation findLocationForInsertion(NodeRef &InsertedNode,
+                                          PatchedTreeNode &InsertionTarget);
+  SourceLocation findLocationForMove(NodeRef DstNode, NodeRef TargetNode,
+                                     PatchedTreeNode &NewParent);
+  void markChangedNodes();
+  Error addReplacementsForChangedNodes();
+  Error addReplacementsForTopLevelChanges();
+
+  // Recursively builds the text that is represented by this subtree.
+  std::string buildSourceText(PatchedTreeNode &PatchedNode);
+  void setOwnedSourceText(PatchedTreeNode &PatchedNode);
+  std::pair<int, bool>
+  findPointOfInsertion(NodeRef N, PatchedTreeNode &TargetParent) const;
+  bool isInserted(const PatchedTreeNode &PatchedNode) const {
+    return isFromDst(PatchedNode);
+  }
+  ChangeKind getChange(NodeRef TargetNode) const {
+    if (!isFromTarget(TargetNode))
+      return NoChange;
+    const Node *SrcNode = TargetDiff.getMapped(TargetNode);
+    if (!SrcNode)
+      return NoChange;
+    return Diff.getNodeChange(*SrcNode);
+  }
+  bool isRemoved(NodeRef TargetNode) const {
+    return getChange(TargetNode) == Delete;
+  }
+  bool isMoved(NodeRef TargetNode) const {
+    return getChange(TargetNode) == Move || getChange(TargetNode) == UpdateMove;
+  }
+  bool isRemovedOrMoved(NodeRef TargetNode) const {
+    return isRemoved(TargetNode) || isMoved(TargetNode);
+  }
+  PatchedTreeNode &findParent(NodeRef N) {
+    if (isFromDst(N))
+      return findDstParent(N);
+    return findTargetParent(N);
+  }
+  PatchedTreeNode &findDstParent(NodeRef DstNode) {
+    const Node *SrcNode = Diff.getMapped(DstNode);
+    NodeRef DstParent = *DstNode.getParent();
+    if (SrcNode) {
+      assert(Diff.getNodeChange(*SrcNode) == Insert);
+      const Node *TargetParent = mapDstToTarget(DstParent);
+      assert(TargetParent);
+      return getTargetPatchedNode(*TargetParent);
+    }
+    return getPatchedNode(DstParent);
+  }
+  PatchedTreeNode &findTargetParent(NodeRef TargetNode) {
+    assert(isFromTarget(TargetNode));
+    const Node *SrcNode = TargetDiff.getMapped(TargetNode);
+    if (SrcNode) {
+      ChangeKind Change = Diff.getNodeChange(*SrcNode);
+      if (Change == Move || Change == UpdateMove) {
+        NodeRef DstNode = *Diff.getMapped(*SrcNode);
+        return getPatchedNode(*DstNode.getParent());
+      }
+    }
+    return getTargetPatchedNode(*TargetNode.getParent());
+  }
+  CharSourceRange getRangeForReplacing(NodeRef TargetNode) const {
+    if (isRemovedOrMoved(TargetNode))
+      return TargetNode.findRangeForDeletion();
+    return TargetNode.getSourceRange();
+  }
+  Error addReplacement(Replacement &&R) {
+    return TargetTool.getReplacements()[R.getFilePath()].add(R);
+  }
+  bool isFromTarget(NodeRef N) const { return &N.getTree() == &Target; }
+  bool isFromDst(NodeRef N) const { return &N.getTree() == &Dst; }
+  PatchedTreeNode &getTargetPatchedNode(NodeRef N) {
+    assert(isFromTarget(N));
+    return PatchedTreeNodes[N.getId()];
+  }
+  PatchedTreeNode &getPatchedNode(NodeRef N) {
+    if (isFromDst(N))
+      return *InsertedNodes.at(N.getId());
+    return PatchedTreeNodes[N.getId()];
+  }
+  const Node *mapDstToTarget(NodeRef DstNode) const {
+    const Node *SrcNode = Diff.getMapped(DstNode);
+    if (!SrcNode)
+      return nullptr;
+    return TargetDiff.getMapped(*SrcNode);
+  }
+  const Node *mapTargetToDst(NodeRef TargetNode) const {
+    const Node *SrcNode = TargetDiff.getMapped(TargetNode);
+    if (!SrcNode)
+      return nullptr;
+    return Diff.getMapped(*SrcNode);
+  }
+};
+} // end anonymous namespace
+
+static void markBiggestSubtrees(std::vector<bool> &Marked, SyntaxTree &Tree,
+                                llvm::function_ref<bool(NodeRef)> Predicate) {
+  Marked.resize(Tree.getSize());
+  for (NodeRef N : Tree.postorder()) {
+    bool AllChildrenMarked =
+        std::all_of(N.begin(), N.end(),
+                    [&Marked](NodeRef Child) { return Marked[Child.getId()]; });
+    Marked[N.getId()] = Predicate(N) && AllChildrenMarked;
+  }
+}
+
+Error Patcher::apply() {
+  if (Debug)
+    Diff.dumpChanges(llvm::errs(), /*DumpMatches=*/true);
+  markBiggestSubtrees(AtomicInsertions, Dst, [this](NodeRef DstNode) {
+    return Diff.getNodeChange(DstNode) == Insert;
+  });
+  buildPatchedTree();
+  addInsertedAndMovedNodes();
+  markChangedNodes();
+  if (auto Err = addReplacementsForChangedNodes())
+    return Err;
+  Rewriter Rewrite(SM, LangOpts);
+  if (!TargetTool.applyAllReplacements(Rewrite))
+    return error(patching_error::failed_to_apply_replacements);
+  if (Rewrite.overwriteChangedFiles())
+    // Some file has not been saved successfully.
+    return error(patching_error::failed_to_overwrite_files);
+  return Error::success();
+}
+
+static bool wantToInsertBefore(SourceLocation Insertion, SourceLocation Point,
+                               BeforeThanCompare<SourceLocation> &Less) {
+  assert(Insertion.isValid());
+  assert(Point.isValid());
+  return Less(Insertion, Point);
+}
+
+void Patcher::buildPatchedTree() {
+  // Firstly, add all nodes of the tree that will be patched to
+  // PatchedTreeNodes. This way, their offset (getId()) is the same as in the
+  // original tree.
+  PatchedTreeNodes.reserve(Target.getSize());
+  for (NodeRef TargetNode : Target)
+    PatchedTreeNodes.emplace_back(TargetNode);
+  // Then add all inserted nodes, from Dst.
+  for (NodeId DstId = Dst.getRootId(), E = Dst.getSize(); DstId < E; ++DstId) {
+    NodeRef DstNode = Dst.getNode(DstId);
+    ChangeKind Change = Diff.getNodeChange(DstNode);
+    if (Change == Insert) {
+      PatchedTreeNodes.emplace_back(DstNode);
+      InsertedNodes.emplace(DstNode.getId(), &PatchedTreeNodes.back());
+      // If the whole subtree is inserted, we can skip the children, as we
+      // will just copy the text of the entire subtree.
+      if (AtomicInsertions[DstId])
+        DstId = DstNode.RightMostDescendant;
+    }
+  }
+  // Add existing children.
+  for (auto &PatchedNode : PatchedTreeNodes) {
+    if (isFromTarget(PatchedNode))
+      for (auto &Child : PatchedNode.originalNode())
+        if (!isRemovedOrMoved(Child))
+          PatchedNode.addChild(getPatchedNode(Child));
+  }
+}
+
+void Patcher::addInsertedAndMovedNodes() {
+  ChangeKind Change = NoChange;
+  for (NodeId DstId = Dst.getRootId(), E = Dst.getSize(); DstId < E;
+       DstId = Change == Insert && AtomicInsertions[DstId]
+                   ? Dst.getNode(DstId).RightMostDescendant + 1
+                   : DstId + 1) {
+    NodeRef DstNode = Dst.getNode(DstId);
+    Change = Diff.getNodeChange(DstNode);
+    if (!(Change == Move || Change == UpdateMove || Change == Insert))
+      continue;
+    NodeRef DstParent = *DstNode.getParent();
+    PatchedTreeNode *InsertionTarget, *NodeToInsert;
+    SourceLocation InsertionLoc;
+    if (Diff.getNodeChange(DstParent) == Insert) {
+      InsertionTarget = &getPatchedNode(DstParent);
+    } else {
+      const Node *TargetParent = mapDstToTarget(DstParent);
+      if (!TargetParent)
+        continue;
+      InsertionTarget = &getTargetPatchedNode(*TargetParent);
+    }
+    if (Change == Insert) {
+      NodeToInsert = &getPatchedNode(DstNode);
+      InsertionLoc = findLocationForInsertion(DstNode, *InsertionTarget);
+    } else {
+      assert(Change == Move || Change == UpdateMove);
+      const Node *TargetNode = mapDstToTarget(DstNode);
+      assert(TargetNode && "Node to update not found.");
+      NodeToInsert = &getTargetPatchedNode(*TargetNode);
+      InsertionLoc =
+          findLocationForMove(DstNode, *TargetNode, *InsertionTarget);
+    }
+    assert(InsertionLoc.isValid());
+    InsertionTarget->addInsertion(*NodeToInsert, InsertionLoc);
+  }
+}
+
+SourceLocation
+Patcher::findLocationForInsertion(NodeRef DstNode,
+                                  PatchedTreeNode &InsertionTarget) {
+  assert(isFromDst(DstNode));
+  assert(isFromDst(InsertionTarget) || isFromTarget(InsertionTarget));
+  int ChildIndex;
+  bool RightOfChild;
+  unsigned NumChildren = InsertionTarget.Children.size();
+  std::tie(ChildIndex, RightOfChild) =
+      findPointOfInsertion(DstNode, InsertionTarget);
+  if (NumChildren && ChildIndex != -1) {
+    auto NeighborRange = InsertionTarget.Children[ChildIndex]->getSourceRange();
+    SourceLocation InsertionLocation =
+        RightOfChild ? NeighborRange.getEnd() : NeighborRange.getBegin();
+    if (InsertionLocation.isValid())
+      return InsertionLocation;
+  }
+  llvm_unreachable("Not implemented.");
+}
+
+SourceLocation Patcher::findLocationForMove(NodeRef DstNode, NodeRef TargetNode,
+                                            PatchedTreeNode &NewParent) {
+  assert(isFromDst(DstNode));
+  assert(isFromTarget(TargetNode));
+  return DstNode.getSourceRange().getEnd();
+}
+
+void Patcher::markChangedNodes() {
+  for (auto Pair : InsertedNodes) {
+    NodeRef DstNode = Dst.getNode(Pair.first);
+    getPatchedNode(DstNode).Changed = true;
+  }
+  // Mark nodes in original as changed.
+  for (NodeRef TargetNode : Target.postorder()) {
+    auto &PatchedNode = PatchedTreeNodes[TargetNode.getId()];
+    const Node *SrcNode = TargetDiff.getMapped(TargetNode);
+    if (!SrcNode)
+      continue;
+    ChangeKind Change = Diff.getNodeChange(*SrcNode);
+    auto &Children = PatchedNode.Children;
+    bool AnyChildChanged =
+        std::any_of(Children.begin(), Children.end(),
+                    [](PatchedTreeNode *Child) { return Child->Changed; });
+    bool AnyChildRemoved = std::any_of(
+        PatchedNode.originalNode().begin(), PatchedNode.originalNode().end(),
+        [this](NodeRef Child) { return isRemovedOrMoved(Child); });
+    assert(!PatchedNode.Changed);
+    PatchedNode.Changed =
+        AnyChildChanged || AnyChildRemoved || Change != NoChange;
+  }
+}
+
+Error Patcher::addReplacementsForChangedNodes() {
+  for (NodeId TargetId = Target.getRootId(), E = Target.getSize(); TargetId < E;
+       ++TargetId) {
+    NodeRef TargetNode = Target.getNode(TargetId);
+    auto &PatchedNode = getTargetPatchedNode(TargetNode);
+    if (!PatchedNode.Changed)
+      continue;
+    if (TargetId == Target.getRootId())
+      return addReplacementsForTopLevelChanges();
+    CharSourceRange Range = getRangeForReplacing(TargetNode);
+    std::string Text =
+        isRemovedOrMoved(PatchedNode) ? "" : buildSourceText(PatchedNode);
+    if (auto Err = addReplacement({SM, Range, Text, LangOpts}))
+      return Err;
+    TargetId = TargetNode.RightMostDescendant;
+  }
+  return Error::success();
+}
+
+Error Patcher::addReplacementsForTopLevelChanges() {
+  auto &Root = getTargetPatchedNode(Target.getRoot());
+  for (unsigned I = 0, E = Root.Children.size(); I < E; ++I) {
+    PatchedTreeNode *Child = Root.Children[I];
+    if (!Child->Changed)
+      continue;
+    std::string ChildText = buildSourceText(*Child);
+    CharSourceRange ChildRange;
+    if (isInserted(*Child) || isMoved(*Child)) {
+      SourceLocation InsertionLoc;
+      unsigned NumChildren = Root.Children.size();
+      int ChildIndex;
+      bool RightOfChild;
+      std::tie(ChildIndex, RightOfChild) = findPointOfInsertion(*Child, Root);
+      if (NumChildren && ChildIndex != -1) {
+        auto NeighborRange = Root.Children[ChildIndex]->getSourceRange();
+        InsertionLoc =
+            RightOfChild ? NeighborRange.getEnd() : NeighborRange.getBegin();
+      } else {
+        InsertionLoc = SM.getLocForEndOfFile(SM.getMainFileID())
+                           .getLocWithOffset(-int(strlen("\n")));
+      }
+      ChildRange = makeEmptyCharRange(InsertionLoc);
+    } else {
+      ChildRange = Child->getSourceRange();
+    }
+    if (auto Err = addReplacement({SM, ChildRange, ChildText, LangOpts})) {
+      return Err;
+    }
+  }
+  for (NodeRef Child : Root.originalNode()) {
+    if (isRemovedOrMoved(Child)) {
+      auto ChildRange = Child.findRangeForDeletion();
+      if (auto Err = addReplacement({SM, ChildRange, "", LangOpts}))
+        return Err;
+    }
+  }
+  return Error::success();
+}
+
+static StringRef trailingText(SourceLocation Loc, SyntaxTree &Tree) {
+  Token NextToken;
+  bool Failure = Lexer::getRawToken(Loc, NextToken, Tree.getSourceManager(),
+                                    Tree.getLangOpts(),
+                                    /*IgnoreWhiteSpace=*/true);
+  if (Failure)
+    return StringRef();
+  assert(!Failure);
+  return Lexer::getSourceText(
+      CharSourceRange::getCharRange({Loc, NextToken.getLocation()}),
+      Tree.getSourceManager(), Tree.getLangOpts());
+}
+
+std::string Patcher::buildSourceText(PatchedTreeNode &PatchedNode) {
+  auto &Children = PatchedNode.Children;
+  auto &ChildrenOffsets = PatchedNode.ChildrenOffsets;
+  auto &OwnText = PatchedNode.OwnText;
+  auto Range = PatchedNode.getSourceRange();
+  SyntaxTree &Tree = PatchedNode.getTree();
+  SourceManager &MySM = Tree.getSourceManager();
+  const LangOptions &MyLangOpts = Tree.getLangOpts();
+  assert(!isRemoved(PatchedNode));
+  if (!PatchedNode.Changed ||
+      (isFromDst(PatchedNode) && AtomicInsertions[PatchedNode.getId()])) {
+    std::string Text = Lexer::getSourceText(Range, MySM, MyLangOpts);
+    // TODO why
+    if (!isFromDst(PatchedNode))
+      Text += trailingText(Range.getEnd(), Tree);
+    return Text;
+  }
+  setOwnedSourceText(PatchedNode);
+  std::string Result;
+  unsigned Offset = 0;
+  assert(ChildrenOffsets.size() == Children.size());
+  for (unsigned I = 0, E = Children.size(); I < E; ++I) {
+    PatchedTreeNode *Child = Children[I];
+    unsigned Start = ChildrenOffsets[I];
+    Result += OwnText->substr(Offset, Start - Offset);
+    Result += buildSourceText(*Child);
+    Offset = Start;
+  }
+  assert(Offset <= OwnText->size());
+  Result += OwnText->substr(Offset, OwnText->size() - Offset);
+  return Result;
+}
+
+void Patcher::setOwnedSourceText(PatchedTreeNode &PatchedNode) {
+  assert(isFromTarget(PatchedNode) || isFromDst(PatchedNode));
+  SyntaxTree &Tree = PatchedNode.getTree();
+  const Node *SrcNode = nullptr;
+  bool IsUpdate = false;
+  auto &OwnText = PatchedNode.OwnText;
+  auto &Children = PatchedNode.Children;
+  auto &ChildrenLocations = PatchedNode.ChildrenLocations;
+  auto &ChildrenOffsets = PatchedNode.ChildrenOffsets;
+  OwnText = "";
+  unsigned NumChildren = Children.size();
+  if (isFromTarget(PatchedNode)) {
+    SrcNode = TargetDiff.getMapped(PatchedNode);
+    ChangeKind Change = SrcNode ? Diff.getNodeChange(*SrcNode) : NoChange;
+    IsUpdate = Change == Update || Change == UpdateMove;
+  }
+  unsigned ChildIndex = 0;
+  auto MySourceRanges = PatchedNode.getOwnedSourceRanges();
+  BeforeThanCompare<SourceLocation> MyLess(Tree.getSourceManager());
+  for (auto &MySubRange : MySourceRanges) {
+    SourceLocation ChildBegin;
+    SourceLocation InsertionBegin;
+    while (ChildIndex < NumChildren &&
+           ((ChildBegin = ChildrenLocations[ChildIndex]).isInvalid() ||
+            wantToInsertBefore(ChildBegin, MySubRange.getEnd(), MyLess))) {
+      ChildrenOffsets.push_back(OwnText->size());
+      ++ChildIndex;
+    }
+    if (IsUpdate) {
+      llvm_unreachable("Not implemented.");
+    } else {
+      *OwnText += Lexer::getSourceText(MySubRange, Tree.getSourceManager(),
+                                       Tree.getLangOpts());
+    }
+  }
+  while (ChildIndex++ < NumChildren)
+    ChildrenOffsets.push_back(OwnText->size());
+}
+
+std::pair<int, bool>
+Patcher::findPointOfInsertion(NodeRef N, PatchedTreeNode &TargetParent) const {
+  assert(isFromDst(N) || isFromTarget(N));
+  assert(isFromTarget(TargetParent));
+  auto MapFunction = [this, &N](PatchedTreeNode &Sibling) {
+    if (isFromDst(N) == isFromDst(Sibling))
+      return &NodeRef(Sibling);
+    if (isFromDst(N))
+      return mapTargetToDst(Sibling);
+    else
+      return mapDstToTarget(Sibling);
+  };
+  unsigned NumChildren = TargetParent.Children.size();
+  BeforeThanCompare<SourceLocation> Less(N.getTree().getSourceManager());
+  auto NodeIndex = N.findPositionInParent();
+  SourceLocation MyLoc = N.getSourceRange().getBegin();
+  assert(MyLoc.isValid());
+  for (unsigned I = 0; I < NumChildren; ++I) {
+    const Node *Sibling = MapFunction(*TargetParent.Children[I]);
+    if (!Sibling)
+      continue;
+    SourceLocation SiblingLoc = Sibling->getSourceRange().getBegin();
+    if (SiblingLoc.isInvalid())
+      continue;
+    if (NodeIndex && Sibling == &N.getParent()->getChild(NodeIndex - 1)) {
+      return {I, /*RightOfSibling=*/true};
+    }
+    if (Less(MyLoc, SiblingLoc)) {
+      return {I, /*RightOfSibling=*/false};
+    }
+  }
+  return {-1, true};
+}
+
+Error patch(RefactoringTool &TargetTool, SyntaxTree &Src, SyntaxTree &Dst,
+            const ComparisonOptions &Options, bool Debug) {
+  std::vector<std::unique_ptr<ASTUnit>> TargetASTs;
+  TargetTool.buildASTs(TargetASTs);
+  if (TargetASTs.size() != 1)
+    return error(patching_error::failed_to_build_AST);
+  SyntaxTree Target(*TargetASTs[0]);
+  return Patcher(Src, Dst, Target, Options, TargetTool, Debug).apply();
+}
+
+std::string PatchingError::message() const {
+  switch (Err) {
+  case patching_error::failed_to_build_AST:
+    return "Failed to build AST.\n";
+  case patching_error::failed_to_apply_replacements:
+    return "Failed to apply replacements.\n";
+  case patching_error::failed_to_overwrite_files:
+    return "Failed to overwrite some file(s).\n";
+  };
+}
+
+char PatchingError::ID = 1;
+
+} // end namespace diff
+} // end namespace clang

lib/Tooling/ASTDiff/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_library(clangToolingASTDiff
   ASTDiff.cpp
+  ASTPatch.cpp
   LINK_LIBS
   clangBasic
   clangAST
   clangLex
+  clangRewrite
+  clangFrontend
+  clangTooling
+  clangToolingCore
   )

test/Tooling/clang-diff-patch.test

+// compare the file with an empty file, patch it to remove all code
+RUN: rm -rf %t && mkdir -p %t
+RUN: cp %S/clang-diff-ast.cpp %t
+RUN: echo > %t/dst.cpp
+RUN: clang-diff %t/clang-diff-ast.cpp %t/dst.cpp \
+RUN:  -patch %t/clang-diff-ast.cpp -- -std=c++11
+// the resulting file should not contain anything other than comments and
+// whitespace
+RUN: cat %t/clang-diff-ast.cpp | grep -v '^#' | grep -v '^\s*//' | not grep -v '^\s*$'

tools/clang-diff/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_executable(clang-diff
   ClangDiff.cpp
   )
 
 target_link_libraries(clang-diff
   clangBasic
   clangFrontend
+  clangRewrite
   clangTooling
+  clangToolingCore
   clangToolingASTDiff
   )

tools/clang-diff/ClangDiff.cpp

 //===- ClangDiff.cpp - compare source files by AST nodes ------*- C++ -*- -===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a tool for syntax tree based comparison using
 // Tooling/ASTDiff.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/ASTDiff/ASTDiff.h"
+#include "clang/Tooling/ASTDiff/ASTPatch.h"
 #include "clang/Tooling/CommonOptionsParser.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 using namespace clang;
 using namespace clang::tooling;
 

 static cl::opt<bool> PrintMatches("dump-matches",
                                   cl::desc("Print the matched nodes."),
                                   cl::init(false), cl::cat(ClangDiffCategory));
 
 static cl::opt<bool> HtmlDiff("html",
                               cl::desc("Output a side-by-side diff in HTML."),
                               cl::init(false), cl::cat(ClangDiffCategory));
 
+static cl::opt<std::string>
+    FileToPatch("patch",
+                cl::desc("Try to apply the edit actions between the two input "
+                         "files to the specified target."),
+                cl::desc("<target>"), cl::cat(ClangDiffCategory));
+
 static cl::opt<std::string> SourcePath(cl::Positional, cl::desc("<source>"),
                                        cl::Required,
                                        cl::cat(ClangDiffCategory));
 
 static cl::opt<std::string> DestinationPath(cl::Positional,
                                             cl::desc("<destination>"),
                                             cl::Optional,
                                             cl::cat(ClangDiffCategory));
else if (StopAfter == "bottomup")
       Options.StopAfterBottomUp = true;
     else {
       llvm::errs() << "Error: Invalid argument for -stop-diff-after\n";
       return 1;
     }
   }
   diff::SyntaxTree SrcTree(*Src);
   diff::SyntaxTree DstTree(*Dst);
+
+  if (!FileToPatch.empty()) {
+    std::array<std::string, 1> Files = {{FileToPatch}};
+    RefactoringTool TargetTool(CommonCompilations
+                                   ? *CommonCompilations
+                                   : *getCompilationDatabase(FileToPatch),
+                               Files);
+    if (auto Err = diff::patch(TargetTool, SrcTree, DstTree, Options)) {
+      llvm::handleAllErrors(
+          std::move(Err),
+          [](const diff::PatchingError &PE) { PE.log(llvm::errs()); },
+          [](const ReplacementError &RE) { RE.log(llvm::errs()); });
+      llvm::errs() << "*** errors occured, patching failed.\n";
+      return 1;
+    }
+    return 0;
+  }
+
   diff::ASTDiff Diff(SrcTree, DstTree, Options);
 
   if (HtmlDiff) {
     llvm::outs() << HtmlDiffHeader << "<pre>";
     llvm::outs() << "<div id='L' class='code'>";
     printHtmlForNode(llvm::outs(), Diff, true, SrcTree.getRoot(), 0);
     llvm::outs() << "</div>";
     llvm::outs() << "<div id='R' class='code'>";

unittests/Tooling/ASTPatchTest.cpp

+//===- unittest/Tooling/ASTPatchTest.cpp ----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/ASTDiff/ASTPatch.h"
+#include "clang/Tooling/ASTDiff/ASTDiff.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Program.h"
+#include "gtest/gtest.h"
+#include <fstream>
+
+using namespace clang;
+using namespace tooling;
+
+std::string ReadShellCommand(const Twine &Command) {
+  char Buffer[128];
+  std::string Result;
+  std::shared_ptr<FILE> Pipe(popen(Command.str().data(), "r"), pclose);
+  if (!Pipe)
+    return Result;
+  while (!feof(Pipe.get())) {
+    if (fgets(Buffer, 128, Pipe.get()) != nullptr)
+      Result += Buffer;
+  }
+  return Result;
+}
+
+class ASTPatchTest : public ::testing::Test {
+  llvm::SmallString<256> TargetFile, ExpectedFile;
+  std::array<std::string, 1> TargetFileArray;
+
+public:
+  void SetUp() override {
+    std::string Suffix = "cpp";
+    ASSERT_FALSE(llvm::sys::fs::createTemporaryFile(
+        "clang-libtooling-patch-target", Suffix, TargetFile));
+    ASSERT_FALSE(llvm::sys::fs::createTemporaryFile(
+        "clang-libtooling-patch-expected", Suffix, ExpectedFile));
+    TargetFileArray[0] = TargetFile.str();
+  }
+  void TearDown() override {
+    llvm::sys::fs::remove(TargetFile);
+    llvm::sys::fs::remove(ExpectedFile);
+  }
+
+  void WriteFile(StringRef Filename, StringRef Contents) {
+    std::ofstream OS(Filename);
+    OS << Contents.str();
+    assert(OS.good());
+  }
+
+  std::string ReadFile(StringRef Filename) {
+    std::ifstream IS(Filename);
+    std::stringstream OS;
+    OS << IS.rdbuf();
+    assert(IS.good());
+    return OS.str();
+  }
+
+  std::string formatExpected(StringRef Code) {
+    WriteFile(ExpectedFile, Code);
+    return ReadShellCommand("clang-format " + ExpectedFile);
+  }
+
+  llvm::Expected<std::string> patchResult(const char *SrcCode,
+                                          const char *DstCode,
+                                          const char *TargetCode) {
+    std::unique_ptr<ASTUnit> SrcAST = buildASTFromCode(SrcCode),
+                             DstAST = buildASTFromCode(DstCode);
+    if (!SrcAST || !DstAST) {
+      if (!SrcAST)
+        llvm::errs() << "Failed to build AST from code:\n" << SrcCode << "\n";
+      if (!DstAST)
+        llvm::errs() << "Failed to build AST from code:\n" << DstCode << "\n";
+      return llvm::make_error<diff::PatchingError>(
+          diff::patching_error::failed_to_build_AST);
+    }
+
+    diff::SyntaxTree Src(*SrcAST);
+    diff::SyntaxTree Dst(*DstAST);
+
+    WriteFile(TargetFile, TargetCode);
+    FixedCompilationDatabase Compilations(".", std::vector<std::string>());
+    RefactoringTool TargetTool(Compilations, TargetFileArray);
+    diff::ComparisonOptions Options;
+
+    if (auto Err = diff::patch(TargetTool, Src, Dst, Options, /*Debug=*/false))
+      return std::move(Err);
+    return ReadShellCommand("clang-format " + TargetFile);
+  }
+
+#define APPEND_NEWLINE(x) x "\n"
+// use macros for this to make test failures have proper line numbers
+#define PATCH(Src, Dst, Target, ExpectedResult)                                \
+  {                                                                            \
+    llvm::Expected<std::string> Result = patchResult(                          \
+        APPEND_NEWLINE(Src), APPEND_NEWLINE(Dst), APPEND_NEWLINE(Target));     \
+    ASSERT_TRUE(bool(Result));                                                 \
+    EXPECT_EQ(Result.get(), formatExpected(APPEND_NEWLINE(ExpectedResult)));   \
+  }
+#define PATCH_ERROR(Src, Dst, Target, ErrorCode)                               \
+  {                                                                            \
+    llvm::Expected<std::string> Result = patchResult(Src, Dst, Target);        \
+    ASSERT_FALSE(bool(Result));                                                \
+    llvm::handleAllErrors(Result.takeError(),                                  \
+                          [&](const diff::PatchingError &PE) {                 \
+                            EXPECT_EQ(PE.get(), ErrorCode);                    \
+                          });                                                  \
+  }
+};
+
+TEST_F(ASTPatchTest, Delete) {
+  PATCH(R"(void f() { { int x = 1; } })",
+        R"(void f() { })",
+        R"(void f() { { int x = 2; } })",
+        R"(void f() {  })");
+  PATCH(R"(void foo(){})",
+        R"()",
+        R"(int x; void foo() {;;} int y;)",
+        R"(int x;  int y;)");
+}
+TEST_F(ASTPatchTest, DeleteCallArguments) {
+  PATCH(R"(void foo(...); void test1() { foo ( 1 + 1); })",
+        R"(void foo(...); void test1() { foo ( ); })",
+        R"(void foo(...); void test2() { foo ( 1 + 1 ); })",
+        R"(void foo(...); void test2() { foo (  ); })");
+}
+TEST_F(ASTPatchTest, DeleteParmVarDecl) {
+  PATCH(R"(void foo(int a);)",
+        R"(void foo();)",
+        R"(void bar(int x);)",
+        R"(void bar();)");
+}
+TEST_F(ASTPatchTest, Insert) {
+  PATCH(R"(class C {              C() {} };)",
+        R"(class C { int b;       C() {} };)",
+        R"(class C { int c;       C() {} };)",
+        R"(class C { int c;int b; C() {} };)");
+  PATCH(R"(class C {        C() {} };)",
+        R"(class C { int b; C() {} };)",
+        R"(class C {        C() {} };)",
+        R"(class C { int b; C() {} };)");
+  PATCH(R"(class C { int x;              };)",
+        R"(class C { int x;int b;        };)",
+        R"(class C { int x ;int c;        };)",
+        R"(class C { int x;int b;int c;  };)");
+  PATCH(R"(class C { int x;              };)",
+        R"(class C { int x;int b;        };)",
+        R"(class C { int x; int c;        };)",
+        R"(class C { int x;int b;int c;  };)");
+  PATCH(R"(class C { int x;              };)",
+        R"(class C { int x;int b;        };)",
+        R"(class C { int x;int c;        };)",
+        R"(class C { int x;int b;int c;  };)");
+  PATCH(R"(int a;)",
+        R"(int a; int x();)",
+        R"(int a;)",
+        R"(int a; int x();)");
+  PATCH(R"(int a; int b;)",
+        R"(int a; int x; int b;)",
+        R"(int a; int b;)",
+        R"(int a; int x; int b;)");
+  PATCH(R"(int b;)",
+        R"(int x; int b;)",
+        R"(int b;)",
+        R"(int x; int b;)");
+  PATCH(R"(void f() {   int x = 1 + 1;   })",
+        R"(void f() { { int x = 1 + 1; } })",
+        R"(void f() {   int x = 1 + 1;   })",
+        R"(void f() { { int x = 1 + 1; } })");
+}
+TEST_F(ASTPatchTest, InsertNoParent) {
+  PATCH(R"(void f() { })",
+        R"(void f() { int x; })",
+        R"()",
+        R"()");
+}
+TEST_F(ASTPatchTest, InsertTopLevel) {
+  PATCH(R"(namespace a {})",
+        R"(namespace a {} void x();)",
+        R"(namespace a {})",
+        R"(namespace a {} void x();)");
+}
+TEST_F(ASTPatchTest, Move) {
+  PATCH(R"(namespace a {  void f(){} })",
+        R"(namespace a {} void f(){}  )",
+        R"(namespace a {  void f(){} })",
+        R"(namespace a {} void f(){}  )");
+  PATCH(R"(namespace a {  void f(){} } int x;)",
+        R"(namespace a {} void f(){}   int x;)",
+        R"(namespace a {  void f(){} } int x;)",
+        R"(namespace a {} void f(){}   int x;)");
+  PATCH(R"(namespace a { namespace { } })",
+        R"(namespace a { })",
+        R"(namespace a { namespace { } })",
+        R"(namespace a { })");
+  PATCH(R"(namespace { int x = 1 + 1; })",
+        R"(namespace { int x = 1 + 1; int y;})",
+        R"(namespace { int x = 1 + 1; })",
+        R"(namespace { int x = 1 + 1; int y;})");
+  PATCH(R"(namespace { int y; int x = 1 + 1; })",
+        R"(namespace { int x = 1 + 1; int y; })",
+        R"(namespace { int y; int x = 1 + 1; })",
+        R"(namespace { int x = 1 + 1; int y; })");
+  PATCH(R"(void f() { ; int x = 1 + 1; })",
+        R"(void f() { int x = 1 + 1; ; })",
+        R"(void f() { ; int x = 1 + 1; })",
+        R"(void f() { int x = 1 + 1; ; })");
+  PATCH(R"(void f() { {{;;;}}        })",
+        R"(void f() { {{{;;;}}}      })",
+        R"(void f() { {{;;;}}        })",
+        R"(void f() { {{{;;;}}}      })");
+}
+TEST_F(ASTPatchTest, MoveNoSource) {
+  PATCH(R"(void f() { })",
+        R"(void f() { int x; })",
+        R"()",
+        R"()");
+}
+TEST_F(ASTPatchTest, MoveNoTarget) {
+  PATCH(R"(int x; void f() { })",
+        R"(void f() { int x; })",
+        R"(int x;)",
+        R"()");
+}
+TEST_F(ASTPatchTest, Newline) {
+  PATCH(R"(void f(){
+;
+})",
+        R"(void f(){
+;
+int x;
+})",
+        R"(void f(){
+;
+})",
+        R"(void f(){
+;
+int x;
+})");
+}
+TEST_F(ASTPatchTest, Nothing) {
+  PATCH(R"()",
+        R"()",
+        R"()",
+        R"()");
+}
+TEST_F(ASTPatchTest, Update) {
+  PATCH(R"(class A { int x; };)",
+        R"(class A { int x; };)",
+        R"(class A { int y; };)",
+        R"(class A { int y; };)");
+}
+TEST_F(ASTPatchTest, UpdateMove) {
+  PATCH(R"(void f() { { int x = 1; } })",
+        R"(void f() { })",
+        R"(void f() { { int x = 2; } })",
+        R"(void f() {  })");
+}

unittests/Tooling/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   Support
   )
 
 # By default MSVC has a 2^16 limit on the number of sections in an object file,
 # and this needs more than that.
 if (MSVC)
   set_source_files_properties(RecursiveASTVisitorTest.cpp PROPERTIES COMPILE_FLAGS /bigobj)
   set_source_files_properties(RecursiveASTVisitorTestExprVisitor.cpp PROPERTIES COMPILE_FLAGS /bigobj)
 endif()
 
 add_clang_unittest(ToolingTests
+  ASTPatchTest.cpp
   ASTSelectionTest.cpp
   CastExprTest.cpp
   CommentHandlerTest.cpp
   CompilationDatabaseTest.cpp
   DiagnosticsYamlTest.cpp
   ExecutionTest.cpp
   FixItTest.cpp
   LexicallyOrderedRecursiveASTVisitorTest.cpp
target_link_libraries(ToolingTests
   clangBasic
   clangFormat
   clangFrontend
   clangLex
   clangRewrite
   clangTooling
   clangToolingCore
   clangToolingRefactor
+  clangToolingASTDiff
   )