[clang-diff] patching: implement updates

[johannes]

Summary

This allows to patch nodes that have been updated. We use a LCS
algorithm to determine which tokens changed, and update accordingly.

lib/Tooling/ASTDiff/ASTPatch.cpp

public:
   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();
   }
+  decltype(BaseNode.getOwnedTokens()) getOwnedTokens() {
+    return BaseNode.getOwnedTokens();
+  }
 
   // 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.
void addChildAt(PatchedTreeNode &PatchedNode, SourceLocation InsertionLoc) {
     ChildrenLocations.insert(It, InsertionLoc);
   }
 
   SmallVector<SourceLocation, 2> SplitAt;
 };
 } // end anonymous namespace
 
 namespace {
+struct TokenInsertion {
+  enum { BeforeFirst = -1 };
+  int AfterToken = BeforeFirst;
+  int AfterChild = BeforeFirst;
+  unsigned Token;
+};
+} // end anonymous namespace
+
+namespace {
+struct TokenMapping {
+  SmallVector<unsigned, 4> DeletedTokens;
+  SmallVector<TokenInsertion, 4> Insertions;
+  SmallVector<int, 4> Mapping;
+};
+} // end anonymous namespace
+
+namespace {
 class Patcher {
   SyntaxTree &Dst, &Target;
   SourceManager &SM;
   const LangOptions &LangOpts;
   BeforeThanCompare<SourceLocation> Less;
   ASTDiff Diff, TargetDiff;
   RefactoringTool &TargetTool;
   bool Debug;
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);
+  // Uses a LCS algorithm to determine insertions and deletions of tokens.
+  TokenMapping matchTokens(NodeRef InsertionDestination,
+                           NodeRef InsertionSource);
   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;
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.");
+  NodeRef DstParent = *DstNode.getParent();
+  TokenMapping MapDstNew = matchTokens(DstParent, InsertionTarget);
+  BeforeThanCompare<SourceLocation> DstLess(Dst.getSourceManager());
+  auto InsertedLoc = DstNode.getSourceRange().getBegin();
+  assert(InsertedLoc.isValid());
+  auto DstTokens = DstParent.getOwnedTokens();
+  auto NewTokens = InsertionTarget.getOwnedTokens();
+  for (unsigned I = 0; I < NewTokens.size(); ++I) {
+    int DstIndex = MapDstNew.Mapping[I];
+    if (DstIndex == -1)
+      continue;
+    SourceLocation NewLoc = NewTokens[I];
+    SourceLocation DstLoc = DstTokens[DstIndex];
+    if (DstLoc.isValid() && wantToInsertBefore(InsertedLoc, DstLoc, DstLess))
+      return NewLoc;
+  }
+  if (isFromDst(InsertionTarget))
+    return InsertionTarget.getSourceRange().getEnd();
+  assert(NodeRef(InsertionTarget).ASTNode.get<TranslationUnitDecl>());
+  return SM.getLocForEndOfFile(SM.getMainFileID());
 }
 
 SourceLocation Patcher::findLocationForMove(NodeRef DstNode, NodeRef TargetNode,
                                             PatchedTreeNode &NewParent) {
   assert(isFromDst(DstNode));
   assert(isFromTarget(TargetNode));
-  return DstNode.getSourceRange().getEnd();
+  NodeRef DstParent = *DstNode.getParent();
+  auto Range = DstNode.getSourceRange();
+  SourceLocation MyLocInSource = Range.getBegin();
+  TokenMapping MapDstTarget = matchTokens(DstParent, NewParent);
+  BeforeThanCompare<SourceLocation> DstLess(Dst.getSourceManager());
+  auto DstParentTokens = DstParent.getOwnedTokens();
+  auto NewParentTokens = NewParent.getOwnedTokens();
+  for (unsigned I = 0; I < NewParentTokens.size(); ++I) {
+    int DstIndex = MapDstTarget.Mapping[I];
+    if (DstIndex == -1)
+      continue;
+    SourceLocation NewLoc = NewParentTokens[I];
+    SourceLocation DstLoc = DstParentTokens[DstIndex];
+    if (wantToInsertBefore(MyLocInSource, DstLoc, DstLess)) {
+      return NewLoc;
+    }
+  }
+  SourceLocation Loc = NewParent.getSourceRange().getEnd();
+  return Loc.isValid() ? Loc : SM.getLocForEndOfFile(SM.getMainFileID());
 }
 
 void Patcher::markChangedNodes() {
   for (auto Pair : InsertedNodes) {
     NodeRef DstNode = Dst.getNode(Pair.first);
     getPatchedNode(DstNode).Changed = true;
   }
   // Mark nodes in original as changed.
for (unsigned I = 0, E = Children.size(); I < E; ++I) {
     Result += buildSourceText(*Child);
     Offset = Start;
   }
   assert(Offset <= OwnText->size());
   Result += OwnText->substr(Offset, OwnText->size() - Offset);
   return Result;
 }
 
+StringRef getTokenText(SourceLocation Loc, SyntaxTree &Tree) {
+  Token Tok;
+  bool Failure =
+      Lexer::getRawToken(Loc, Tok, Tree.getSourceManager(), Tree.getLangOpts(),
+                         /*IgnoreWhiteSpace=*/true);
+  assert(!Failure);
+  auto TokenRange = CharSourceRange::getCharRange({Loc, Tok.getEndLoc()});
+  return Lexer::getSourceText(TokenRange, Tree.getSourceManager(),
+                              Tree.getLangOpts());
+}
+
+TokenMapping Patcher::matchTokens(NodeRef NodeA, NodeRef NodeB) {
+  TokenMapping TheMapping;
+  auto &TreeA = NodeA.getTree(), &TreeB = NodeB.getTree();
+  auto A = NodeA.getOwnedTokens(), B = NodeB.getOwnedTokens();
+  auto SizeA = A.size(), SizeB = B.size();
+  std::vector<std::unique_ptr<int[]>> C(SizeA + 1);
+  auto AreSameTokens = [&](SourceLocation LocA, SourceLocation LocB) {
+    return getTokenText(LocA, TreeA) == getTokenText(LocB, TreeB);
+  };
+  for (auto &Row : C)
+    Row = llvm::make_unique<int[]>(SizeB + 1);
+  for (unsigned I = 0; I <= SizeA; ++I)
+    C[I][0] = 0;
+  for (unsigned J = 0; J <= SizeB; ++J)
+    C[0][J] = 0;
+  for (unsigned I = 1; I <= SizeA; ++I) {
+    for (unsigned J = 1; J <= SizeB; ++J) {
+      if (AreSameTokens(A[I - 1], B[J - 1]))
+        C[I][J] = C[I - 1][J - 1] + 1;
+      else
+        C[I][J] = std::max(C[I][J - 1], C[I - 1][J]);
+    }
+  }
+  auto FillUpMapping = [&](unsigned UpTo) {
+    while (TheMapping.Mapping.size() < UpTo)
+      TheMapping.Mapping.push_back(-1);
+  };
+  std::function<void(unsigned, unsigned)> BacktrackChanges = [&](unsigned I,
+                                                                 unsigned J) {
+    if (I > 0 && J > 0 && AreSameTokens(A[I - 1], B[J - 1])) {
+      BacktrackChanges(I - 1, J - 1);
+      FillUpMapping(J - 1);
+      TheMapping.Mapping.push_back(I - 1);
+    } else if (I > 0 && (J == 0 || C[I][J - 1] < C[I - 1][J])) {
+      BacktrackChanges(I - 1, J);
+      TheMapping.DeletedTokens.push_back(I - 1);
+    } else if (J > 0 && (I == 0 || C[I][J - 1] >= C[I - 1][J])) {
+      BacktrackChanges(I, J - 1);
+      unsigned ChildIndex = 0;
+      SourceLocation TokLoc = B[J - 1];
+      BeforeThanCompare<SourceLocation> LessB(TreeB.getSourceManager());
+      TokenInsertion Insertion;
+      Insertion.Token = J - 1;
+      if (I != 0) {
+        Insertion.AfterToken = I - 1;
+        for (NodeRef Child : NodeB) {
+          SourceLocation ChildLoc = Child.getSourceRange().getBegin();
+          if (LessB(TokLoc, ChildLoc) && ChildIndex) {
+            Insertion.AfterChild = ChildIndex - 1;
+            break;
+          }
+          ++ChildIndex;
+        }
+      }
+      TheMapping.Insertions.emplace_back(Insertion);
+    }
+  };
+  BacktrackChanges(SizeA, SizeB);
+  FillUpMapping(SizeB);
+  return TheMapping;
+}
+
+static void AppendToken(std::string &Text, SourceLocation Loc, SyntaxTree &Tree,
+                        bool UnlessListSeparator = false) {
+  Token Tok;
+  bool Failure =
+      Lexer::getRawToken(Loc, Tok, Tree.getSourceManager(), Tree.getLangOpts(),
+                         /*IgnoreWhiteSpace=*/true);
+  assert(!Failure);
+  auto TokenRange = CharSourceRange::getCharRange({Loc, Tok.getEndLoc()});
+  if (UnlessListSeparator && isListSeparator(Tok))
+    return;
+  Text += " ";
+  Text += Lexer::getSourceText(TokenRange, Tree.getSourceManager(),
+                               Tree.getLangOpts());
+}
+
+static bool haveCommonElement(ArrayRef<unsigned> A, ArrayRef<unsigned> B) {
+  assert(std::is_sorted(A.begin(), A.end()) &&
+         std::is_sorted(B.begin(), B.end()));
+  for (unsigned I = 0, J = 0, SizeA = A.size(), SizeB = B.size();
+       I < SizeA && J < SizeB;) {
+    if (A[I] == B[J])
+      return true;
+    if (A[I] > B[J])
+      ++J;
+    else
+      ++I;
+  }
+  return false;
+}
+
+static bool isInRange(SourceLocation Loc, CharSourceRange Range,
+                      BeforeThanCompare<SourceLocation> &Less) {
+  return !Less(Loc, Range.getBegin()) && !Less(Range.getEnd(), Loc);
+};
+
 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();
+  unsigned NumTokens;
+  TokenMapping MapSrcDst, MapSrcTarget;
+  auto Tokens = PatchedNode.getOwnedTokens();
+  decltype(Tokens) DstTokens;
+  if (IsUpdate) {
+    assert(isFromTarget(PatchedNode));
+    NodeRef DstNode = *Diff.getMapped(*SrcNode);
+    DstTokens = DstNode.getOwnedTokens();
+    MapSrcDst = matchTokens(*SrcNode, DstNode);
+    MapSrcTarget = matchTokens(*SrcNode, PatchedNode);
+    NumTokens = PatchedNode.getOwnedTokens().size();
+  }
+  unsigned NextChild = 0, NextToken = 0, NextTokenInSrc = 0,
+           NextInsertedToken = 0;
   BeforeThanCompare<SourceLocation> MyLess(Tree.getSourceManager());
-  for (auto &MySubRange : PatchedNode.splitSourceRanges(MySourceRanges)) {
+  auto AppendInsertedTokens = [&](int LastToken, int LastChild) {
+    while (NextInsertedToken < MapSrcDst.Insertions.size()) {
+      TokenInsertion &Insertion = MapSrcDst.Insertions[NextInsertedToken];
+      if (Insertion.AfterChild > LastChild || Insertion.AfterToken > LastToken)
+        break;
+      AppendToken(*OwnText, DstTokens[Insertion.Token], Dst);
+      *OwnText += " ";
+      ++NextInsertedToken;
+    }
+  };
+  auto AppendChildren = [&](CharSourceRange &InRange) {
     SourceLocation ChildBegin;
-    SourceLocation InsertionBegin;
-    while (ChildIndex < NumChildren &&
-           ((ChildBegin = ChildrenLocations[ChildIndex]).isInvalid() ||
-            wantToInsertBefore(ChildBegin, MySubRange.getEnd(), MyLess))) {
+    while (NextChild < NumChildren &&
+           ((ChildBegin = ChildrenLocations[NextChild]).isInvalid() ||
+            wantToInsertBefore(ChildBegin, InRange.getEnd(), MyLess))) {
       ChildrenOffsets.push_back(OwnText->size());
-      ++ChildIndex;
+      NodeRef Child = *Children[NextChild];
+      const DynTypedNode &DTN = Child.ASTNode,
+                         &ParentDTN = NodeRef(PatchedNode).ASTNode;
+      if ((DTN.get<ParmVarDecl>() ||
+           (ParentDTN.get<CallExpr>() && NextChild > 0)) &&
+          NextChild + 1 < NumChildren) {
+        *OwnText += ", ";
       }
-    if (IsUpdate) {
-      llvm_unreachable("Not implemented.");
-    } else {
-      *OwnText += Lexer::getSourceText(MySubRange, Tree.getSourceManager(),
-                                       Tree.getLangOpts());
+      ++NextChild;
     }
+  };
+  auto DeletedBegin = MapSrcDst.DeletedTokens.begin();
+  auto DeletedEnd = MapSrcDst.DeletedTokens.end();
+  auto IsTokenDeleted = [&](unsigned TokenInSrc) {
+    auto DeletedLoc = std::find(DeletedBegin, DeletedEnd, TokenInSrc);
+    if (DeletedLoc != DeletedEnd) {
+      DeletedBegin = DeletedLoc;
+      return true;
+    }
+    return false;
+  };
+  auto AppendAndInsertTokens = [&](CharSourceRange &InRange) {
+    SourceLocation TokenBegin;
+    while (NextToken < NumTokens &&
+           isInRange((TokenBegin = Tokens[NextToken]), InRange, Less)) {
+      auto TokenIterator = std::find(MapSrcTarget.Mapping.begin(),
+                                     MapSrcTarget.Mapping.end(), NextToken);
+      bool IsTokenMapped = TokenIterator != MapSrcTarget.Mapping.end();
+      if (IsTokenMapped)
+        NextTokenInSrc = *TokenIterator;
+      if (!IsTokenMapped || !IsTokenDeleted(NextTokenInSrc)) {
+        AppendToken(*OwnText, TokenBegin, Target,
+                    /*UnlessListSeparator=*/true);
       }
-  while (ChildIndex++ < NumChildren)
+      if (IsTokenMapped) {
+        AppendInsertedTokens(NextTokenInSrc, NextChild - 1);
+      }
+      ++NextToken;
+    }
+  };
+
+  AppendInsertedTokens(TokenInsertion::BeforeFirst,
+                       TokenInsertion::BeforeFirst);
+  bool AnyTokenDeletedTwice =
+      haveCommonElement(MapSrcDst.DeletedTokens, MapSrcTarget.DeletedTokens);
+  IsUpdate = IsUpdate && !AnyTokenDeletedTwice;
+  for (auto &MySubRange :
+       PatchedNode.splitSourceRanges(PatchedNode.getOwnedSourceRanges())) {
+    SourceLocation LastTokenLocation;
+    AppendChildren(MySubRange);
+    if (IsUpdate)
+      AppendAndInsertTokens(MySubRange);
+    else {
+      forEachTokenInRange(
+          MySubRange, Tree, [&Tree, &OwnText, &LastTokenLocation](Token &Tok) {
+            AppendToken(*OwnText, (LastTokenLocation = Tok.getLocation()), Tree,
+                        /*UnlessListSeparator=*/true);
+          });
+    }
+  }
+  while (NextChild++ < NumChildren) {
     ChildrenOffsets.push_back(OwnText->size());
+    AppendInsertedTokens(NextTokenInSrc, NextChild - 1);
+  }
 }
 
 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))

unittests/Tooling/ASTPatchTest.cpp

#define PATCH_ERROR(Src, Dst, Target, ErrorCode)                               \
     ASSERT_FALSE(bool(Result));                                                \
     llvm::handleAllErrors(Result.takeError(),                                  \
                           [&](const diff::PatchingError &PE) {                 \
                             EXPECT_EQ(PE.get(), ErrorCode);                    \
                           });                                                  \
   }
 };
 
+TEST_F(ASTPatchTest, Constructors) {
+  PATCH(R"(class C { C() {} };)",
+        R"(class C { int b; C(int b) : b(b) {} };)",
+        R"(class D { D() {} };)",
+        R"(class D { int b; D(int b) : b(b) {} };)");
+  PATCH(R"(class C { C() {} };)",
+        R"(class C { int b; C(int b) {} };)",
+        R"(class D { D() {} };)",
+        R"(class D { int b;D(int b) {} };)");
+  PATCH(R"(struct C { C() {} };)",
+        R"(struct C { C(int b) {} };)",
+        R"(struct C { C() {} };)",
+        R"(struct C { C(int b) {} };)");
+  PATCH(R"(struct C { C(int a) {} };)",
+        R"(struct C { C(int a, int b) {} };)",
+        R"(struct C { C(int a) {} };)",
+        R"(struct C { C(int a, int b) {} };)");
+  PATCH(R"(struct C { C(int a) {} };)",
+        R"(struct C { C(int b, int a) {} };)",
+        R"(struct C { C(int a) {} };)",
+        R"(struct C { C(int b, int a) {} };)");
+  PATCH(R"(struct C { C(int) {} };)",
+        R"(struct C { C(int) {int x;} };)",
+        R"(struct C { C(int) {} };)",
+        R"(struct C { C(int) {int x;} };)");
+}
 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 (  ); })");
+  PATCH(R"(void foo(...); void test1() { foo (1, 2 + 2); })",
+        R"(void foo(...); void test1() { foo (2 + 2); })",
+        R"(void foo(...); void test2() { foo (/*L*/ 0 /*R*/ , 2 + 2); })",
+        R"(void foo(...); void test2() { foo (/*L*/ /*R*/ 2 + 2); })");
+  PATCH(R"(void foo(...); void test1() { foo (1, 2); })",
+        R"(void foo(...); void test1() { foo (1); })",
+        R"(void foo(...); void test2() { foo (0, /*L*/ 0 /*R*/); })",
+        R"(void foo(...); void test2() { foo (0 /*L*/ /*R*/); })");
+  PATCH(
+      R"(void printf(...); void foo(int x) { printf("%d", x, x); })",
+      R"(void printf(...); void foo(int x) { printf("%d", x); })",
+      R"(void printf(...); void foo(int x) { printf("different string %d", x, x); })",
+      R"(void printf(...); void foo(int x) { printf("different string %d", x); })");
+  PATCH(
+      R"(void printf(...); void foo(int xx) { printf("%d", xx, xx); })",
+      R"(void printf(...); void foo(int xx) { printf("%d", xx); })",
+      R"(void printf(...); void foo(int xx) { printf("different string %d", xx, xx); })",
+      R"(void printf(...); void foo(int xx) { printf("different string %d", xx); })");
 }
 TEST_F(ASTPatchTest, DeleteParmVarDecl) {
+  PATCH(R"(void f(int a, int b, int c);)",
+        R"(void f(int a, int b);)",
+        R"(void b(int o, int b, int c);)",
+        R"(void b(int o, int b);)");
+  PATCH(R"(void f(int a, int b, int c);)",
+        R"(void f(int a, int b);)",
+        R"(void f(int a, int b, int c);)",
+        R"(void f(int a, int b);)");
   PATCH(R"(void foo(int a);)",
         R"(void foo();)",
         R"(void bar(int x);)",
         R"(void bar();)");
+  PATCH(R"(void foo(int a);)",
+        R"(void foo();)",
+        R"(void bar(int x, int y);)",
+        R"(void bar(int y);)");
+  PATCH(R"(void foo(int a, int b);)",
+        R"(void foo(int a);)",
+        R"(void bar(int x, int y);)",
+        R"(void bar(int x);)");
+  PATCH(R"(void foo(int a, int b, int c);)",
+        R"(void foo(int a, int b);)",
+        R"(void bar(int a, int b, int c);)",
+        R"(void bar(int a, int b);)");
 }
 TEST_F(ASTPatchTest, Insert) {
+  PATCH(R"()",
+        R"(int x;)",
+        R"()",
+        R"(int x;)");
+  PATCH(R"()",
+        R"(namespace a {  })",
+        R"()",
+        R"(namespace a {  })");
+  PATCH(R"(class C {               };)",
+        R"(class C { int b;        };)",
+        R"(class C { int c;        };)",
+        R"(class C { int c;int b;  };)");
   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"(class X { void f() { } };       )",
+        R"(class X { void f() { int x; } };)",
+        R"(class Y { void g() { } };       )",
+        R"(class Y { void g() { int x; }}; )");
   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; } })");
+  PATCH(R"(void f() { int x; })",
+        R"(void f() { int x; int y; })",
+        R"(void f() { })",
+        R"(void f() { int y;})");
 }
 TEST_F(ASTPatchTest, InsertNoParent) {
   PATCH(R"(void f() { })",
         R"(void f() { int x; })",
         R"()",
         R"()");
 }
 TEST_F(ASTPatchTest, InsertTopLevel) {
+  PATCH(R"()",
+        R"(namespace { })",
+        R"()",
+        R"(namespace { })");
   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 a = 1 + 1; int z; })",
+        R"(namespace { int y; int x = 1 + 2; })",
+        R"(namespace { int a = 1 + 2; int z; })");
+  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() { int x; })",
+        R"(void f() { int x; int y; })",
+        R"(void f() { })",
+        R"(void f() { int y;})");
   PATCH(R"(void f() { {{;;;}}        })",
         R"(void f() { {{{;;;}}}      })",
         R"(void f() { {{;;;}}        })",
         R"(void f() { {{{;;;}}}      })");
+  PATCH(R"(void f() {;;})",
+        R"(namespace a { void f() {;;} })",
+        R"(void f() {;;})",
+        R"(namespace a { void f() {;;} })");
+  PATCH(R"(void f() {;;})",
+        R"(namespace { void f() {;;} })",
+        R"(void f() {;;})",
+        R"(namespace { void f() {;;} })");
+  PATCH(R"(void f() {;;} namespace {})",
+        R"(namespace { void f() {;;} })",
+        R"(void g() {;;} namespace {})",
+        R"(namespace { void g() {;;} })");
+  PATCH(R"(void f() {;;} namespace {})",
+        R"(namespace { void g() {;;} })",
+        R"(void f() {;;} namespace {})",
+        R"(namespace { void g() {;;} })");
+  PATCH(R"(void f() {})",
+        R"(namespace { void f() {} })",
+        R"(void f() {})",
+        R"( namespace {void f() {}})");
+}
+TEST_F(ASTPatchTest, MoveIntoInserted) {
+  PATCH(R"(void f() { { int x = 1; } })",
+        R"(void f() {   int x = 2;   })",
+        R"(void f() { { int x = 1; } })",
+        R"(void f() {   int x = 2;   })");
 }
 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, MoveTopLevel) {
+  PATCH(R"(void f() {} namespace {})",
+        R"(namespace {void f() {} })",
+        R"(void f() {} namespace {})",
+        R"(namespace {void f() {} })");
+}
 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, Qualifiers) {
+  PATCH(R"(class X { void f()       { } };       )",
+        R"(class X { const void f() { } };)",
+        R"(class Y { void g()       { } };       )",
+        R"(class Y { const void g() { }}; )");
+  PATCH(R"(class X { void f()       { } };       )",
+        R"(class X { void f() const { } };)",
+        R"(class Y { void g()       { } };       )",
+        R"(class Y { void g() const { }}; )");
+  PATCH(R"(class X { void f() const { } };       )",
+        R"(class X { void f()       { } };)",
+        R"(class Y { void g()       { } };       )",
+        R"(class Y { void g()       { }}; )");
+  PATCH(R"(class X { void f() const { } };       )",
+        R"(class X { void f()       { } };)",
+        R"(class Y { void g() const      { } };       )",
+        R"(class Y { void g()       { }}; )");
+  PATCH(R"(class X { void f() { } };       )",
+        R"(class X { void f() const { int x; } };)",
+        R"(class Y { void g() { } };       )",
+        R"(class Y { void g() const { int x; }}; )");
+}
 TEST_F(ASTPatchTest, Update) {
+  PATCH(R"(class A { int f(int) { return f(1); } };)",
+        R"(class A { int g(int) { return g(1); } };)",
+        R"(class A { int f(int) { return f(2); } };)",
+        R"(class A { int g(int) { return g(2); } };)");
   PATCH(R"(class A { int x; };)",
         R"(class A { int x; };)",
         R"(class A { int y; };)",
         R"(class A { int y; };)");
+  PATCH(R"(class A { int x; };)",
+        R"(class B { int x; };)",
+        R"(class A { int x; };)",
+        R"(class B { int x; };)");
+  PATCH(R"(class A { int x; };)",
+        R"(class B { int x; };)",
+        R"(class A { int y; };)",
+        R"(class B { int y; };)");
+  PATCH(R"(int a;)",
+        R"(int b;)",
+        R"(int c;)",
+        R"(int c;)");
+  PATCH(R"(int x = 1 + 2;)",
+        R"(int x = 2 + 2;)",
+        R"(int y = 1 + 3;)",
+        R"(int y = 2 + 3;)");
+  PATCH(R"(int x = 1 + 2;)",
+        R"(int y = 2 + 2;)",
+        R"(int x = 1 + 3;)",
+        R"(int y = 2 + 3;)");
+  PATCH(R"(void f(int a, int b);)",
+        R"(void f(int a);)",
+        R"(void b(int x, int y);)",
+        R"(void b(int x);)");
 }
 TEST_F(ASTPatchTest, UpdateMove) {
   PATCH(R"(void f() { { int x = 1; } })",
+        R"(void f() {   int x = 2;   })",
+        R"(void f() { { int x = 1; } })",
+        R"(void f() {   int x = 2;   })");
+  PATCH(R"(void f() { { int x = 1; } })",
         R"(void f() { })",
         R"(void f() { { int x = 2; } })",
         R"(void f() {  })");
+  PATCH(R"(void f() {;;})",
+        R"(namespace { void f() {;;} })",
+        R"(void g() {;;})",
+        R"( namespace {void g() {;;}})");
   PATCH(R"(void f() {;;} namespace {})",
         R"(namespace { void f() {;;} })",
         R"(void g() {;;} namespace {})",
         R"(namespace { void g() {;;} })");
+  PATCH(R"(void f() {;;} namespace {})",
+        R"(namespace { void g() {;;} })",
+        R"(void f() {;;} namespace {})",
+        R"(namespace { void g() {;;} })");
+}
+TEST_F(ASTPatchTest, UpdateTokenMismatch) {
+  PATCH(R"(int a;)",
+        R"(int b;)",
+        R"(int c;)",
+        R"(int c;)");
 }