[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

655

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

1304

Please move the patcher into a new file.

[johannes]

split to ASTDiff/ASTPatch

[arphaman]

include/clang/Tooling/ASTDiff/ASTPatch.h

1

Please update the file name in the comment

lib/Tooling/ASTDiff/ASTDiff.cpp

656

You might as well return early here and avoid else entirely

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiff.h

73

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

82

It's fine to have = default in the header

[johannes]

fixes

include/clang/Tooling/ASTDiff/ASTDiff.h

73

ok, i use optional now instead in the unittest

[johannes]

update

include/clang/Tooling/ASTDiff/ASTDiff.h

 // algorithm to match small subtrees.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
 
 #include "clang/Frontend/ASTUnit.h"
+#include "clang/Rewrite/Core/Rewriter.h"
 #include "clang/Tooling/ASTDiff/ASTDiffInternal.h"
 
 namespace clang {
 namespace diff {
 
 enum ChangeKind {
   None,
   Delete,    // (Src): delete node Src.

 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:
+  /// Empty (invalid) SyntaxTree.
+  SyntaxTree();
   /// 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(SyntaxTree &&Other);
+  SyntaxTree &operator=(SyntaxTree &&Other);
+  explicit SyntaxTree(const SyntaxTree &Other);
   ~SyntaxTree();
 
   ASTUnit &getASTUnit() const;
   const ASTContext &getASTContext() const;
+  SourceManager &getSourceManager() const;
+  const LangOptions &getLangOpts() const;
   StringRef getFilename() const;
 
   int getSize() const;
   NodeId getRootId() const;
   using PreorderIterator = NodeId;
   PreorderIterator begin() const;
   PreorderIterator end() const;
 
   const Node &getNode(NodeId Id) const;
   int findPositionInParent(NodeId Id) const;
 
   /// Returns the range that contains the text that is associated with this
   /// node.
-  /* SourceRange getSourceRange(const Node &N) const; */
+  SourceRange getSourceRange(const Node &N) const;
   /// Returns the offsets for the range returned by getSourceRange.
   std::pair<unsigned, unsigned> getSourceRangeOffsets(const Node &N) const;
 
   /// Serialize the node attributes to a string representation. This should
   /// uniquely distinguish nodes of the same kind. Note that this function just
   /// returns a representation of the node value, not considering descendants.
   std::string getNodeValue(NodeId Id) const;
   std::string getNodeValue(const Node &Node) const;

include/clang/Tooling/ASTDiff/ASTPatch.h

+//===- ASTDiff.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"
+
+namespace clang {
+namespace diff {
+
+bool patch(SyntaxTree &ModelSrc, SyntaxTree &ModelDst, SyntaxTree &TargetSrc,
+           const ComparisonOptions &Options, raw_ostream &OS);
+
+} // end namespace diff
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_ASTDIFF_ASTPATCH_H

lib/Tooling/ASTDiff/ASTDiff.cpp

Impl(SyntaxTree *Parent,
        typename std::enable_if<std::is_base_of<Stmt, T>::value, T>::type *Node,
        ASTUnit &AST)
       : Impl(Parent, dyn_cast<Stmt>(Node), AST) {}
   template <class T>
   Impl(SyntaxTree *Parent,
        typename std::enable_if<std::is_base_of<Decl, T>::value, T>::type *Node,
        ASTUnit &AST)
       : Impl(Parent, dyn_cast<Decl>(Node), AST) {}
+  explicit Impl(SyntaxTree *Parent, const Impl &Other);
 
   SyntaxTree *Parent;
   ASTUnit &AST;
   PrintingPolicy TypePP;
   /// Nodes in preorder.
   std::vector<Node> Nodes;
   std::vector<NodeId> Leaves;
   // Maps preorder indices to postorder ones.
public:
 
   std::string getNodeValue(NodeId Id) const;
   std::string getNodeValue(const Node &Node) const;
   std::string getDeclValue(const Decl *D) const;
   std::string getStmtValue(const Stmt *S) const;
 
   HashType hashNode(const Node &N) const;
 
+  SourceRange getSourceRange(const Node &N) const;
+
 private:
   void initTree();
   void setLeftMostDescendants();
 };
 
 static bool isSpecializedNodeExcluded(const Decl *D) { return D->isImplicit(); }
 static bool isSpecializedNodeExcluded(const Stmt *S) { return false; }
 static bool isSpecializedNodeExcluded(CXXCtorInitializer *I) {

 
 SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, ASTUnit &AST)
     : Impl(Parent, AST) {
   PreorderVisitor PreorderWalker(*this);
   PreorderWalker.TraverseStmt(N);
   initTree();
 }
 
+SyntaxTree::Impl::Impl(SyntaxTree *Parent, const Impl &Other)
+    : Impl(Parent, Other.AST) {
+  Nodes = Other.Nodes;
+  Leaves = Other.Leaves;
+  PostorderIds = Other.PostorderIds;
+  NodesBfs = Other.NodesBfs;
+  TemplateArgumentLocations = TemplateArgumentLocations;
+}
+
 static std::vector<NodeId> getSubtreePostorder(const SyntaxTree::Impl &Tree,
                                                NodeId Root) {
   std::vector<NodeId> Postorder;
   std::function<void(NodeId)> Traverse = [&](NodeId Id) {
     const Node &N = Tree.getNode(Id);
     for (NodeId Child : N.Children)
       Traverse(Child);
     Postorder.push_back(Id);
HashType SyntaxTree::Impl::hashNode(const Node &N) const {
   }
   llvm::MD5 Hash;
   DataCollector(DTN, *this, Hash);
   llvm::MD5::MD5Result HashResult;
   Hash.final(HashResult);
   return HashResult;
 }
 
+SourceRange SyntaxTree::Impl::getSourceRange(const Node &N) const {
+  SourceRange Range;
+  if (N.ASTNode.get<TemplateArgument>())
+    Range = TemplateArgumentLocations.at(&N - &Nodes[0]);
+  else {
+    Range = N.ASTNode.getSourceRange();
+    if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>())
+      if (ThisExpr->isImplicit())
+        Range.setEnd(Range.getBegin());
+  }
+  return Range;
+}
+
 /// 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; }
ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
     : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
 
 ASTDiff::~ASTDiff() = default;
 
 NodeId ASTDiff::getMapped(const SyntaxTree &SourceTree, NodeId Id) const {
   return DiffImpl->getMapped(SourceTree.TreeImpl, Id);
 }
 
+SyntaxTree::SyntaxTree() : TreeImpl(nullptr) {}
+
 SyntaxTree::SyntaxTree(ASTUnit &AST)
     : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
           this, AST.getASTContext().getTranslationUnitDecl(), AST)) {}
 
+SyntaxTree::SyntaxTree(SyntaxTree &&Other) = default;
+
+SyntaxTree &SyntaxTree::operator=(SyntaxTree &&Other) = default;
+
+SyntaxTree::SyntaxTree(const SyntaxTree &Other)
+    : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(this, *Other.TreeImpl)) {}
+
 SyntaxTree::~SyntaxTree() = default;
 
 ASTUnit &SyntaxTree::getASTUnit() const { return TreeImpl->AST; }
 
+SourceManager &SyntaxTree::getSourceManager() const {
+  return TreeImpl->AST.getSourceManager();
+}
+
+const LangOptions &SyntaxTree::getLangOpts() const {
+  return TreeImpl->AST.getLangOpts();
+}
+
 const ASTContext &SyntaxTree::getASTContext() const {
   return TreeImpl->AST.getASTContext();
 }
 
 const Node &SyntaxTree::getNode(NodeId Id) const {
   return TreeImpl->getNode(Id);
 }
 
 int SyntaxTree::getSize() const { return TreeImpl->getSize(); }
 NodeId SyntaxTree::getRootId() const { return TreeImpl->getRootId(); }
 SyntaxTree::PreorderIterator SyntaxTree::begin() const {
   return TreeImpl->begin();
 }
 SyntaxTree::PreorderIterator SyntaxTree::end() const { return TreeImpl->end(); }
 
 int SyntaxTree::findPositionInParent(NodeId Id) const {
   return TreeImpl->findPositionInParent(Id);
 }
 
+SourceRange SyntaxTree::getSourceRange(const Node &N) const {
+  return TreeImpl->getSourceRange(N);
+}
+
 std::pair<unsigned, unsigned>
 SyntaxTree::getSourceRangeOffsets(const Node &N) const {
   const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
-  SourceRange Range;
-  if (auto *Arg = N.ASTNode.get<TemplateArgument>())
-    Range = TreeImpl->TemplateArgumentLocations.at(&N - &TreeImpl->Nodes[0]);
-  else {
-    Range = N.ASTNode.getSourceRange();
-    if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>())
-      if (ThisExpr->isImplicit())
-        Range.setEnd(Range.getBegin());
-  }
-  Range = getSourceExtent(TreeImpl->AST, Range);
+  SourceRange Range =
+      getSourceExtent(TreeImpl->AST, TreeImpl->getSourceRange(N));
   unsigned Begin = SrcMgr.getFileOffset(Range.getBegin());
   unsigned End = SrcMgr.getFileOffset(Range.getEnd());
   return {Begin, End};
 }
 
 std::string SyntaxTree::getNodeValue(NodeId Id) const {
   return TreeImpl->getNodeValue(Id);
 }
 
 std::string SyntaxTree::getNodeValue(const Node &N) const {
   return TreeImpl->getNodeValue(N);
 }
 
 } // 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/Rewrite/Core/Rewriter.h"
+#include "clang/Tooling/Core/Replacement.h"
+
+using namespace llvm;
+using namespace clang;
+using namespace tooling;
+
+namespace clang {
+namespace diff {
+
+namespace {
+struct Patcher {
+  SyntaxTree &ModelSrc, &ModelDst, &Target;
+  const ComparisonOptions &Options;
+  raw_ostream &OS;
+  SourceManager &SrcMgr;
+  const LangOptions &LangOpts;
+  Replacements Replaces;
+  SyntaxTree ModelSrcCopy;
+  ASTDiff ModelDiff, ModelTargetDiff;
+
+  Patcher(SyntaxTree &ModelSrc, SyntaxTree &ModelDst, SyntaxTree &Target,
+          const ComparisonOptions &Options, raw_ostream &OS)
+      : ModelSrc(ModelSrc), ModelDst(ModelDst), Target(Target),
+        Options(Options), OS(OS), SrcMgr(Target.getSourceManager()),
+        LangOpts(Target.getLangOpts()), ModelSrcCopy(ModelSrc),
+        ModelDiff(ModelSrc, ModelDst, Options),
+        ModelTargetDiff(ModelSrcCopy, Target, Options) {}
+
+  bool apply() {
+    addDeletions();
+    Rewriter Rewrite(SrcMgr, LangOpts);
+    if (!applyAllReplacements(Replaces, Rewrite)) {
+      llvm::errs() << "Error: Failed to apply replacements.\n";
+      return false;
+    }
+    Rewrite.getEditBuffer(SrcMgr.getMainFileID()).write(OS);
+    return true;
+  }
+
+private:
+  void addDeletions() {
+    for (NodeId Id = ModelSrc.getRootId(), E = ModelSrc.getSize(); Id < E;
+         ++Id) {
+      const Node &ModelNode = ModelSrc.getNode(Id);
+      if (ModelNode.Change != Delete)
+        continue;
+      NodeId TargetId = ModelTargetDiff.getMapped(ModelSrcCopy, Id);
+      if (TargetId.isInvalid())
+        continue;
+      Replacement R(SrcMgr, findRangeForDeletion(TargetId), "", LangOpts);
+      if (Replaces.add(R))
+        llvm::errs() << "Info: Failed to add replacement.\n";
+      Id = ModelNode.RightMostDescendant;
+    }
+  }
+
+  CharSourceRange findRangeForDeletion(NodeId Id) {
+    const Node &N = Target.getNode(Id);
+    SourceRange Range = Target.getSourceRange(N);
+    if (N.Parent.isInvalid())
+      return {Range, false};
+    const Node &Parent = Target.getNode(N.Parent);
+    auto &DTN = N.ASTNode;
+    auto &ParentDTN = Parent.ASTNode;
+    size_t SiblingIndex = Target.findPositionInParent(Id);
+    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) {
+      bool LastSibling = SiblingIndex == Siblings.size() - 1;
+      SourceLocation CommaLoc = Range.getEnd();
+      if (LastSibling)
+        CommaLoc =
+            Target.getSourceRange(Target.getNode(Siblings[SiblingIndex - 1]))
+                .getEnd();
+      CommaLoc =
+          Lexer::findLocationAfterToken(CommaLoc, tok::comma, SrcMgr, LangOpts,
+                                        /*SkipTrailingWhitespaceAndNewLine=*/
+                                        false);
+      assert(CommaLoc.isValid() && "Adjacent token is not a comma.");
+      if (LastSibling)
+        Range.setBegin(
+            CommaLoc.getLocWithOffset(-static_cast<int>(strlen(","))));
+      else
+        Range.setEnd(CommaLoc);
+    } else if (DTN.get<VarDecl>() or
+               (DTN.get<FunctionDecl>() and
+                not DTN.get<FunctionDecl>()->isThisDeclarationADefinition()) or
+               DTN.get<TypeDecl>() or DTN.get<UsingDirectiveDecl>() or
+               DTN.get<ClassTemplateDecl>()) {
+      SourceLocation SemicolonLoc = Lexer::findLocationAfterToken(
+          Range.getEnd(), tok::semi, SrcMgr, LangOpts,
+          /*SkipTrailingWhitespaceAndNewLine=*/false);
+      Range.setEnd(SemicolonLoc);
+    }
+    return CharSourceRange::getTokenRange(Range);
+  }
+};
+} // end anonymous namespace
+
+bool patch(SyntaxTree &ModelSrc, SyntaxTree &ModelDst, SyntaxTree &Target,
+           const ComparisonOptions &Options, raw_ostream &OS) {
+  return Patcher(ModelSrc, ModelDst, Target, Options, OS).apply();
+}
+
+} // 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
+  clangToolingCore
   )

test/Tooling/clang-diff-patch.test

+// compare the file with an empty file, patch it to remove all code
+RUN: echo > %t.dst.cpp
+RUN: clang-diff %S/clang-diff-ast.cpp %t.dst.cpp -patch %S/clang-diff-ast.cpp \
+RUN: -- -std=c++11 > %t.result.cpp
+// the resulting file should not contain anything other than comments and
+// whitespace
+RUN: cat %t.result.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
   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"
 #include "llvm/Support/Program.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>
+    Patch("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 (!Patch.empty()) {
+    auto Target = getAST(CommonCompilations, Patch);
+    if (!Target)
+      return 1;
+    diff::SyntaxTree TargetTree(*Target);
+    diff::patch(SrcTree, DstTree, TargetTree, Options, llvm::outs());
+    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, SrcTree, true, SrcTree.getRootId(), 0);
     llvm::outs() << "</div>";
     llvm::outs() << "<div id='R' class='code'>";

unittests/Tooling/ASTDiffTest.cpp

+//===- unittest/Tooling/ASTDiffTest.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/ASTDiff.h"
+#include "clang/Tooling/ASTDiff/ASTPatch.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace tooling;
+
+static std::string patchResult(std::array<std::string, 3> Codes) {
+  diff::SyntaxTree Trees[3];
+  std::unique_ptr<ASTUnit> ASTs[3];
+  std::vector<std::string> Args = {};
+  for (int I = 0; I < 3; I++) {
+    ASTs[I] = buildASTFromCode(Codes[I]);
+    if (!ASTs[I]) {
+      llvm::errs() << "Failed to build AST from code:\n" << Codes[I] << "\n";
+      return "";
+    }
+    Trees[I] = diff::SyntaxTree(*ASTs[I]);
+  }
+
+  diff::ComparisonOptions Options;
+  std::string TargetDstCode;
+  llvm::raw_string_ostream OS(TargetDstCode);
+  if (!diff::patch(/*ModelSrc=*/Trees[0], /*ModelDst=*/Trees[1],
+                   /*TargetSrc=*/Trees[2], Options, OS))
+    return "";
+  return OS.str();
+}
+
+// abstract the EXPECT_EQ call so that the code snippets align properly
+// use macros for this to make test failures have proper line numbers
+#define PATCH(Preamble, ModelSrc, ModelDst, Target, Expected)                  \
+  EXPECT_EQ(patchResult({{std::string(Preamble) + ModelSrc,                    \
+                          std::string(Preamble) + ModelDst,                    \
+                          std::string(Preamble) + Target}}),                   \
+            std::string(Preamble) + Expected)
+
+TEST(ASTDiff, TestDeleteArguments) {
+  PATCH(R"(void printf(const char *, ...);)",
+        R"(void foo(int x) { printf("%d", x, x); })",
+        R"(void foo(int x) { printf("%d", x); })",
+        R"(void foo(int x) { printf("different string %d", x, x); })",
+        R"(void foo(int x) { printf("different string %d", x); })");
+
+  PATCH(R"(void foo(...);)",
+        R"(void test1() { foo ( 1 + 1); })",
+        R"(void test1() { foo ( ); })",
+        R"(void test2() { foo ( 1 + 1 ); })",
+        R"(void test2() { foo (  ); })");
+
+  PATCH(R"(void foo(...);)",
+        R"(void test1() { foo (1, 2 + 2); })",
+        R"(void test1() { foo (2 + 2); })",
+        R"(void test2() { foo (/*L*/ 0 /*R*/ , 2 + 2); })",
+        R"(void test2() { foo (/*L*/  2 + 2); })");
+
+  PATCH(R"(void foo(...);)",
+        R"(void test1() { foo (1, 2); })",
+        R"(void test1() { foo (1); })",
+        R"(void test2() { foo (0, /*L*/ 0 /*R*/); })",
+        R"(void test2() { foo (0 /*R*/); })");
+}
+
+TEST(ASTDiff, TestDeleteDecls) {
+  PATCH(R"()",
+        R"()",
+        R"()",
+        R"()",
+        R"()");
+
+  PATCH(R"()",
+        R"(void foo(){})",
+        R"()",
+        R"(int x; void foo() {;;} int y;)",
+        R"(int x;  int y;)");
+}

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
+  ASTDiffTest.cpp
   ASTSelectionTest.cpp
   CastExprTest.cpp
   CommentHandlerTest.cpp
   CompilationDatabaseTest.cpp
   DiagnosticsYamlTest.cpp
   FixItTest.cpp
   LexicallyOrderedRecursiveASTVisitorTest.cpp
   LookupTest.cpp
target_link_libraries(ToolingTests
   clangBasic
   clangFormat
   clangFrontend
   clangLex
   clangRewrite
   clangTooling
   clangToolingCore
   clangToolingRefactor
+  clangToolingASTDiff
   )