[clang-diff] Move printing of matches and changes to clang-diff

[johannes]

Summary

This also changes the output order of the changes. Now the matches are
printed in pre-order, intertwined with insertions, updates, and moves.
Deletions are printed afterwards.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

187

It doesn't look like this function is used in this patch?

[johannes]

remove unused SubtreeIterator

[arphaman]

Previous Move resulted in llvm_unreachable("TODO");, but now it seems to be fixed. The new output for Move and UpdateMove should be tested in a test.

[johannes]

add test for 'Move' and 'Update and Move' in output

[arphaman]

include/clang/Tooling/ASTDiff/ASTDiff.h

40

Looks like Shift isn't initialized anywhere.

[johannes]

initialize Node::Shift

[arphaman]

LGTM, with one request below:

lib/Tooling/ASTDiff/ASTDiff.cpp

96–101

80 column violation, please re-format.

[johannes]

format

include/clang/Tooling/ASTDiff/ASTDiff.h

 #ifndef LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
 #define LLVM_CLANG_TOOLING_ASTDIFF_ASTDIFF_H
 
 #include "clang/Tooling/ASTDiff/ASTDiffInternal.h"
 
 namespace clang {
 namespace diff {
 
-/// This represents a match between two nodes in the source and destination
-/// trees, meaning that they are likely to be related.
-struct Match {
-  NodeId Src, Dst;
-};
-
 enum ChangeKind {
-  Delete, // (Src): delete node Src.
-  Update, // (Src, Dst): update the value of node Src to match Dst.
-  Insert, // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
-  Move    // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
-};
-
-struct Change {
-  ChangeKind Kind;
-  NodeId Src, Dst;
-  size_t Position;
-
-  Change(ChangeKind Kind, NodeId Src, NodeId Dst, size_t Position)
-      : Kind(Kind), Src(Src), Dst(Dst), Position(Position) {}
-  Change(ChangeKind Kind, NodeId Src) : Kind(Kind), Src(Src) {}
-  Change(ChangeKind Kind, NodeId Src, NodeId Dst)
-      : Kind(Kind), Src(Src), Dst(Dst) {}
+  None,
+  Delete,    // (Src): delete node Src.
+  Update,    // (Src, Dst): update the value of node Src to match Dst.
+  Insert,    // (Src, Dst, Pos): insert Src as child of Dst at offset Pos.
+  Move,      // (Src, Dst, Pos): move Src to be a child of Dst at offset Pos.
+  UpdateMove // Same as Move plus Update.
 };
 
 /// Represents a Clang AST node, alongside some additional information.
 struct Node {
   NodeId Parent, LeftMostDescendant, RightMostDescendant;
-  int Depth, Height;
+  int Depth, Height, Shift;
   ast_type_traits::DynTypedNode ASTNode;
   SmallVector<NodeId, 4> Children;
+  ChangeKind ChangeKind = None;
 
   ast_type_traits::ASTNodeKind getType() const;
   StringRef getTypeLabel() const;
   bool isLeaf() const { return Children.empty(); }
 };
 
 class ASTDiff {
 public:
   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
   ~ASTDiff();
 
-  // Returns a list of matches.
-  std::vector<Match> getMatches();
-  /// Returns an edit script.
-  std::vector<Change> getChanges();
-
-  // Prints an edit action.
-  void printChange(raw_ostream &OS, const Change &Chg) const;
-  // Prints a match between two nodes.
-  void printMatch(raw_ostream &OS, const Match &M) const;
+  // Returns the ID of the node that is mapped to the given node in SourceTree.
+  NodeId getMapped(const SyntaxTree &SourceTree, NodeId Id) const;
 
   class Impl;
 
 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(const ASTContext &AST);
   /// Constructs a tree from any AST node.
   template <class T>
   SyntaxTree(T *Node, const ASTContext &AST)
       : TreeImpl(llvm::make_unique<Impl>(this, Node, AST)) {}
   SyntaxTree(const SyntaxTree &Tree) = delete;
   ~SyntaxTree();
 
   const ASTContext &getASTContext() const;
   StringRef getFilename() const;
 
-  const Node &getNode(NodeId Id) 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;
 
   std::pair<unsigned, unsigned> getFileOffsets(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(const DynTypedNode &DTN) const;
+  std::string getNodeValue(NodeId Id) const;
+  std::string getNodeValue(const Node &Node) const;
 
   class Impl;
   std::unique_ptr<Impl> TreeImpl;
 };
 
 struct ComparisonOptions {
   /// During top-down matching, only consider nodes of at least this height.
   int MinHeight = 2;
 
   /// During bottom-up matching, match only nodes with at least this value as
   /// the ratio of their common descendants.
   double MinSimilarity = 0.5;
 
   /// Whenever two subtrees are matched in the bottom-up phase, the optimal
   /// mapping is computed, unless the size of either subtrees exceeds this.
   int MaxSize = 100;
 
   /// If this is set to true, nodes that have parents that must not be matched
   /// (see NodeComparison) will be allowed to be matched.
   bool EnableMatchingWithUnmatchableParents = false;
 
   bool StopAfterTopDown = false;
 
   /// Returns false if the nodes should never be matched.
-  bool isMatchingAllowed(const DynTypedNode &N1, const DynTypedNode &N2) const {
-    return N1.getNodeKind().isSame(N2.getNodeKind());
+  bool isMatchingAllowed(const Node &N1, const Node &N2) const {
+    return N1.getType().isSame(N2.getType());
   }
 };
 
 } // end namespace diff
 } // end namespace clang
 
 #endif

include/clang/Tooling/ASTDiff/ASTDiffInternal.h

public:
   int Id;
 
   NodeId() : Id(InvalidNodeId) {}
   NodeId(int Id) : Id(Id) {}
 
   operator int() const { return Id; }
   NodeId &operator++() { return ++Id, *this; }
   NodeId &operator--() { return --Id, *this; }
+  // Support defining iterators on NodeId.
+  NodeId &operator*() { return *this; }
 
   bool isValid() const { return Id != InvalidNodeId; }
   bool isInvalid() const { return Id == InvalidNodeId; }
 };
 
 } // end namespace diff
 } // end namespace clang
 #endif

lib/Tooling/ASTDiff/ASTDiff.cpp

 private:
   std::unique_ptr<SmallVector<NodeId, 2>[]> SrcToDst, DstToSrc;
 };
 } // end anonymous namespace
 
 class ASTDiff::Impl {
 public:
   SyntaxTree::Impl &T1, &T2;
-  bool IsMappingDone = false;
   Mapping TheMapping;
 
   Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
-       const ComparisonOptions &Options)
-      : T1(T1), T2(T2), Options(Options) {}
+       const ComparisonOptions &Options);
 
   /// Matches nodes one-by-one based on their similarity.
   void computeMapping();
 
-  std::vector<Match> getMatches(Mapping &M);
-
-  /// Finds an edit script that converts T1 to T2.
-  std::vector<Change> computeChanges(Mapping &M);
+  // Compute ChangeKind for each node based on similarity.
+  void computeChangeKinds(Mapping &M);
 
-  void printChangeImpl(raw_ostream &OS, const Change &Chg) const;
-  void printMatchImpl(raw_ostream &OS, const Match &M) const;
-
-  // Returns a mapping of identical subtrees.
-  Mapping matchTopDown() const;
+  NodeId getMapped(const SyntaxTree::Impl &Tree, NodeId Id) const {
+    if (&Tree == &T1)
+      return TheMapping.getDst(Id);
+    assert(&Tree == &T2 && "Invalid tree.");
+    return TheMapping.getSrc(Id);
+  }
 
 private:
   // Returns true if the two subtrees are identical.
   bool identical(NodeId Id1, NodeId Id2) const;
 
   bool canBeAddedToMapping(const Mapping &M, NodeId Id1, NodeId Id2) const;
 
   // Returns false if the nodes must not be mached.
   bool isMatchingPossible(NodeId Id1, NodeId Id2) const;
 
+  // Returns true if the nodes' parents are matched.
+  bool haveSameParents(const Mapping &M, NodeId Id1, NodeId Id2) const;
+
   // Uses an optimal albeit slow algorithm to compute a mapping between two
   // subtrees, but only if both have fewer nodes than MaxSize.
   void addOptimalMapping(Mapping &M, NodeId Id1, NodeId Id2) const;
 
   // Computes the ratio of common descendants between the two nodes.
   // Descendants are only considered to be equal when they are mapped in M.
   double getSimilarity(const Mapping &M, NodeId Id1, NodeId Id2) const;
 
   // Returns the node that has the highest degree of similarity.
   NodeId findCandidate(const Mapping &M, NodeId Id1) const;
 
+  // Returns a mapping of identical subtrees.
+  Mapping matchTopDown() const;
+
   // Tries to match any yet unmapped nodes, in a bottom-up fashion.
   void matchBottomUp(Mapping &M) const;
 
   const ComparisonOptions &Options;
 
   friend class ZhangShashaMatcher;
 };
 
Impl(SyntaxTree *Parent,
        const ASTContext &AST)
       : Impl(Parent, dyn_cast<Decl>(Node), AST) {}
 
   SyntaxTree *Parent;
   const ASTContext &AST;
   std::vector<NodeId> Leaves;
   // Maps preorder indices to postorder ones.
   std::vector<int> PostorderIds;
+  std::vector<NodeId> NodesBfs;
 
   int getSize() const { return Nodes.size(); }
   NodeId getRootId() const { return 0; }
+  PreorderIterator begin() const { return getRootId(); }
+  PreorderIterator end() const { return getSize(); }
 
   const Node &getNode(NodeId Id) const { return Nodes[Id]; }
   Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
   bool isValidNodeId(NodeId Id) const { return Id >= 0 && Id < getSize(); }
   void addNode(Node &N) { Nodes.push_back(N); }
   int getNumberOfDescendants(NodeId Id) const;
   bool isInSubtree(NodeId Id, NodeId SubtreeRoot) const;
+  int findPositionInParent(NodeId Id, bool Shifted = false) const;
 
   std::string getNodeValue(NodeId Id) const;
-  std::string getNodeValue(const DynTypedNode &DTN) const;
-  /// Prints the node as "<type>[: <value>](<postorder-id)"
-  void printNode(NodeId Id) const { printNode(llvm::outs(), Id); }
-  void printNode(raw_ostream &OS, NodeId Id) const;
-
-  void printTree() const;
-  void printTree(NodeId Root) const;
-  void printTree(raw_ostream &OS, NodeId Root) const;
+  std::string getNodeValue(const Node &Node) const;
+
+  struct SubtreeIterator {
+    NodeId Root, End;
+    SubtreeIterator(const SyntaxTree::Impl &Tree, NodeId Root)
+        : Root(Root), End(Tree.getNode(Root).RightMostDescendant + 1) {}
+    PreorderIterator begin() const { return Root; }
+    PreorderIterator end() const { return End; }
+  };
+
+  SubtreeIterator iteratePreorder(NodeId Root) const { return {*this, Root}; }
 
 private:
   /// Nodes in preorder.
   std::vector<Node> Nodes;
 
   void initTree();
   void setLeftMostDescendants();
 };
SyntaxTree::Impl::Impl(SyntaxTree *Parent, Stmt *N, const ASTContext &AST)
   NodeCountVisitor NodeCounter(*this);
   NodeCounter.TraverseStmt(N);
   Nodes.resize(NodeCounter.Count);
   PreorderVisitor PreorderWalker(*this);
   PreorderWalker.TraverseStmt(N);
   initTree();
 }
 
+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);
+  };
+  Traverse(Root);
+  return Postorder;
+}
+
+static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
+                                         NodeId Root) {
+  std::vector<NodeId> Ids;
+  size_t Expanded = 0;
+  Ids.push_back(Root);
+  while (Expanded < Ids.size())
+    for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
+      Ids.push_back(Child);
+  return Ids;
+}
+
 void SyntaxTree::Impl::initTree() {
   setLeftMostDescendants();
   int PostorderId = 0;
   PostorderIds.resize(getSize());
   std::function<void(NodeId)> PostorderTraverse = [&](NodeId Id) {
     for (NodeId Child : getNode(Id).Children)
       PostorderTraverse(Child);
     PostorderIds[Id] = PostorderId;
     ++PostorderId;
   };
   PostorderTraverse(getRootId());
+  NodesBfs = getSubtreeBfs(*this, getRootId());
 }
 
 void SyntaxTree::Impl::setLeftMostDescendants() {
   for (NodeId Leaf : Leaves) {
     getMutableNode(Leaf).LeftMostDescendant = Leaf;
     NodeId Parent, Cur = Leaf;
     while ((Parent = getNode(Cur).Parent).isValid() &&
            getNode(Parent).Children[0] == Cur) {
       Cur = Parent;
       getMutableNode(Cur).LeftMostDescendant = Leaf;
     }
   }
 }
 
-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);
-  };
-  Traverse(Root);
-  return Postorder;
-}
-
-static std::vector<NodeId> getSubtreeBfs(const SyntaxTree::Impl &Tree,
-                                         NodeId Root) {
-  std::vector<NodeId> Ids;
-  size_t Expanded = 0;
-  Ids.push_back(Root);
-  while (Expanded < Ids.size())
-    for (NodeId Child : Tree.getNode(Ids[Expanded++]).Children)
-      Ids.push_back(Child);
-  return Ids;
-}
-
 int SyntaxTree::Impl::getNumberOfDescendants(NodeId Id) const {
   return getNode(Id).RightMostDescendant - Id + 1;
 }
 
 bool SyntaxTree::Impl::isInSubtree(NodeId Id, NodeId SubtreeRoot) const {
   return Id >= SubtreeRoot && Id <= getNode(SubtreeRoot).RightMostDescendant;
 }
 
+int SyntaxTree::Impl::findPositionInParent(NodeId Id, bool Shifted) const {
+  NodeId Parent = getNode(Id).Parent;
+  if (Parent.isInvalid())
+    return 0;
+  const auto &Siblings = getNode(Parent).Children;
+  int Position = 0;
+  for (size_t I = 0, E = Siblings.size(); I < E; ++I) {
+    if (Shifted)
+      Position += getNode(Siblings[I]).Shift;
+    if (Siblings[I] == Id) {
+      Position += I;
+      return Position;
+    }
+  }
+  llvm_unreachable("Node not found in parent's children.");
+}
+
 std::string SyntaxTree::Impl::getNodeValue(NodeId Id) const {
-  return getNodeValue(getNode(Id).ASTNode);
+  return getNodeValue(getNode(Id));
 }
 
-std::string SyntaxTree::Impl::getNodeValue(const DynTypedNode &DTN) const {
+std::string SyntaxTree::Impl::getNodeValue(const Node &N) const {
+  const DynTypedNode &DTN = N.ASTNode;
   if (auto *X = DTN.get<BinaryOperator>())
     return X->getOpcodeStr();
   if (auto *X = DTN.get<AccessSpecDecl>()) {
     CharSourceRange Range(X->getSourceRange(), false);
     return Lexer::getSourceText(Range, AST.getSourceManager(),
                                 AST.getLangOpts());
   }
   if (auto *X = DTN.get<IntegerLiteral>()) {
if (X->getTypeForDecl())
           X->getTypeForDecl()->getCanonicalTypeInternal().getAsString() + ";";
   if (DTN.get<Decl>())
     return Value;
   if (DTN.get<Stmt>())
     return "";
   llvm_unreachable("Fatal: unhandled AST node.\n");
 }
 
-void SyntaxTree::Impl::printTree() const { printTree(getRootId()); }
-void SyntaxTree::Impl::printTree(NodeId Root) const {
-  printTree(llvm::outs(), Root);
-}
-
-void SyntaxTree::Impl::printTree(raw_ostream &OS, NodeId Root) const {
-  const Node &N = getNode(Root);
-  for (int I = 0; I < N.Depth; ++I)
-    OS << " ";
-  printNode(OS, Root);
-  OS << "\n";
-  for (NodeId Child : N.Children)
-    printTree(OS, Child);
-}
-
-void SyntaxTree::Impl::printNode(raw_ostream &OS, NodeId Id) const {
-  if (Id.isInvalid()) {
-    OS << "None";
-    return;
-  }
-  OS << getNode(Id).getTypeLabel();
-  if (getNodeValue(Id) != "")
-    OS << ": " << getNodeValue(Id);
-  OS << "(" << PostorderIds[Id] << ")";
-}
-
 /// 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; }
bool ASTDiff::Impl::canBeAddedToMapping(const Mapping &M, NodeId Id1,
   NodeId P1 = N1.Parent;
   NodeId P2 = N2.Parent;
   // Only allow matching if parents can be matched.
   return (P1.isInvalid() && P2.isInvalid()) ||
          (P1.isValid() && P2.isValid() && isMatchingPossible(P1, P2));
 }
 
 bool ASTDiff::Impl::isMatchingPossible(NodeId Id1, NodeId Id2) const {
-  return Options.isMatchingAllowed(T1.getNode(Id1).ASTNode,
-                                   T2.getNode(Id2).ASTNode);
+  return Options.isMatchingAllowed(T1.getNode(Id1), T2.getNode(Id2));
+}
+
+bool ASTDiff::Impl::haveSameParents(const Mapping &M, NodeId Id1,
+                                    NodeId Id2) const {
+  NodeId P1 = T1.getNode(Id1).Parent;
+  NodeId P2 = T2.getNode(Id2).Parent;
+  return (P1.isInvalid() && P2.isInvalid()) ||
+         (P1.isValid() && P2.isValid() && M.getDst(P1) == P2);
 }
 
 void ASTDiff::Impl::addOptimalMapping(Mapping &M, NodeId Id1,
                                       NodeId Id2) const {
   if (std::max(T1.getNumberOfDescendants(Id1), T2.getNumberOfDescendants(Id2)) >
       Options.MaxSize)
     return;
   ZhangShashaMatcher Matcher(*this, T1, T2, Id1, Id2);
for (NodeId Id = Id1 + 1; Id <= N1.RightMostDescendant; ++Id)
     CommonDescendants += int(T2.isInSubtree(M.getDst(Id), Id2));
   return 2.0 * CommonDescendants /
          (T1.getNumberOfDescendants(Id1) + T2.getNumberOfDescendants(Id2));
 }
 
 NodeId ASTDiff::Impl::findCandidate(const Mapping &M, NodeId Id1) const {
   NodeId Candidate;
   double HighestSimilarity = 0.0;
-  for (NodeId Id2 = 0, E = T2.getSize(); Id2 < E; ++Id2) {
+  for (NodeId Id2 : T2) {
     if (!isMatchingPossible(Id1, Id2))
       continue;
     if (M.hasDst(Id2))
       continue;
     double Similarity = getSimilarity(M, Id1, Id2);
     if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
       HighestSimilarity = Similarity;
       Candidate = Id2;
while (std::min(Max1 = L1.peekMax(), Max2 = L2.peekMax()) >
     for (NodeId Id2 : H2) {
       if (!M.hasDst(Id2))
         L2.open(Id2);
     }
   }
   return M;
 }
 
+ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
+                    const ComparisonOptions &Options)
+    : T1(T1), T2(T2), Options(Options) {
+  computeMapping();
+  computeChangeKinds(TheMapping);
+}
+
 void ASTDiff::Impl::computeMapping() {
-  if (IsMappingDone)
-    return;
   TheMapping = matchTopDown();
   if (Options.StopAfterTopDown)
     return;
   matchBottomUp(TheMapping);
-  IsMappingDone = true;
 }
 
-std::vector<Match> ASTDiff::Impl::getMatches(Mapping &M) {
-  std::vector<Match> Matches;
-  for (NodeId Id1 = 0, Id2, E = T1.getSize(); Id1 < E; ++Id1)
-    if ((Id2 = M.getDst(Id1)).isValid())
-      Matches.push_back({Id1, Id2});
-  return Matches;
+void ASTDiff::Impl::computeChangeKinds(Mapping &M) {
+  for (NodeId Id1 : T1) {
+    if (!M.hasSrc(Id1)) {
+      T1.getMutableNode(Id1).ChangeKind = Delete;
+      T1.getMutableNode(Id1).Shift -= 1;
     }
-
-std::vector<Change> ASTDiff::Impl::computeChanges(Mapping &M) {
-  std::vector<Change> Changes;
-  for (NodeId Id2 : getSubtreeBfs(T2, T2.getRootId())) {
-    const Node &N2 = T2.getNode(Id2);
-    NodeId Id1 = M.getSrc(Id2);
-    if (Id1.isValid()) {
-      assert(isMatchingPossible(Id1, Id2) && "Invalid matching.");
-      if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
-        Changes.emplace_back(Update, Id1, Id2);
-      }
-      continue;
+  for (NodeId Id2 : T2) {
+    if (!M.hasDst(Id2)) {
+      T2.getMutableNode(Id2).ChangeKind = Insert;
+      T2.getMutableNode(Id2).Shift -= 1;
     }
-    NodeId P2 = N2.Parent;
-    NodeId P1 = M.getSrc(P2);
-    assert(P1.isValid() &&
-           "Parents must be matched for determining the change type.");
-    Node &Parent1 = T1.getMutableNode(P1);
-    const Node &Parent2 = T2.getNode(P2);
-    auto &Siblings1 = Parent1.Children;
-    const auto &Siblings2 = Parent2.Children;
-    size_t Position;
-    for (Position = 0; Position < Siblings2.size(); ++Position)
-      if (Siblings2[Position] == Id2 || Position >= Siblings1.size())
-        break;
-    Changes.emplace_back(Insert, Id2, P2, Position);
-    Node PatchNode;
-    PatchNode.Parent = P1;
-    PatchNode.LeftMostDescendant = N2.LeftMostDescendant;
-    PatchNode.RightMostDescendant = N2.RightMostDescendant;
-    PatchNode.Depth = N2.Depth;
-    PatchNode.ASTNode = N2.ASTNode;
-    // TODO update Depth if needed
-    NodeId PatchNodeId = T1.getSize();
-    // TODO maybe choose a different data structure for Children.
-    Siblings1.insert(Siblings1.begin() + Position, PatchNodeId);
-    T1.addNode(PatchNode);
-    M.link(PatchNodeId, Id2);
   }
-  for (NodeId Id1 = 0; Id1 < T1.getSize(); ++Id1) {
+  for (NodeId Id1 : T1.NodesBfs) {
     NodeId Id2 = M.getDst(Id1);
     if (Id2.isInvalid())
-      Changes.emplace_back(Delete, Id1, Id2);
+      continue;
+    if (!haveSameParents(M, Id1, Id2) ||
+        T1.findPositionInParent(Id1, true) !=
+            T2.findPositionInParent(Id2, true)) {
+      T1.getMutableNode(Id1).Shift -= 1;
+      T2.getMutableNode(Id2).Shift -= 1;
     }
-  return Changes;
   }
-
-void ASTDiff::Impl::printChangeImpl(raw_ostream &OS, const Change &Chg) const {
-  switch (Chg.Kind) {
-  case Delete:
-    OS << "Delete ";
-    T1.printNode(OS, Chg.Src);
-    OS << "\n";
-    break;
-  case Update:
-    OS << "Update ";
-    T1.printNode(OS, Chg.Src);
-    OS << " to " << T2.getNodeValue(Chg.Dst) << "\n";
-    break;
-  case Insert:
-    OS << "Insert ";
-    T2.printNode(OS, Chg.Src);
-    OS << " into ";
-    T2.printNode(OS, Chg.Dst);
-    OS << " at " << Chg.Position << "\n";
-    break;
-  case Move:
-    llvm_unreachable("TODO");
-    break;
-  };
+  for (NodeId Id2 : T2.NodesBfs) {
+    NodeId Id1 = M.getSrc(Id2);
+    if (Id1.isInvalid())
+      continue;
+    Node &N1 = T1.getMutableNode(Id1);
+    Node &N2 = T2.getMutableNode(Id2);
+    if (Id1.isInvalid())
+      continue;
+    if (!haveSameParents(M, Id1, Id2) ||
+        T1.findPositionInParent(Id1, true) !=
+            T2.findPositionInParent(Id2, true)) {
+      N1.ChangeKind = N2.ChangeKind = Move;
+    }
+    if (T1.getNodeValue(Id1) != T2.getNodeValue(Id2)) {
+      N1.ChangeKind = N2.ChangeKind =
+          (N1.ChangeKind == Move ? UpdateMove : Update);
+    }
   }
-
-void ASTDiff::Impl::printMatchImpl(raw_ostream &OS, const Match &M) const {
-  OS << "Match ";
-  T1.printNode(OS, M.Src);
-  OS << " to ";
-  T2.printNode(OS, M.Dst);
-  OS << "\n";
 }
 
 ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
                  const ComparisonOptions &Options)
     : 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(const ASTContext &AST)
     : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
           this, AST.getTranslationUnitDecl(), AST)) {}
 
-std::vector<Match> ASTDiff::getMatches() {
-  DiffImpl->computeMapping();
-  return DiffImpl->getMatches(DiffImpl->TheMapping);
-}
-
-std::vector<Change> ASTDiff::getChanges() {
-  DiffImpl->computeMapping();
-  return DiffImpl->computeChanges(DiffImpl->TheMapping);
-}
-
-void ASTDiff::printChange(raw_ostream &OS, const Change &Chg) const {
-  DiffImpl->printChangeImpl(OS, Chg);
-}
-
-void ASTDiff::printMatch(raw_ostream &OS, const Match &M) const {
-  DiffImpl->printMatchImpl(OS, M);
-}
-
 SyntaxTree::~SyntaxTree() = default;
 
 const ASTContext &SyntaxTree::getASTContext() const { return TreeImpl->AST; }
 
 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);
+}
 
 std::pair<unsigned, unsigned> SyntaxTree::getFileOffsets(const Node &N) const {
   const SourceManager &SrcMgr = TreeImpl->AST.getSourceManager();
   SourceRange Range = N.ASTNode.getSourceRange();
   SourceLocation BeginLoc = Range.getBegin();
   SourceLocation EndLoc = Lexer::getLocForEndOfToken(
       Range.getEnd(), /*Offset=*/0, SrcMgr, TreeImpl->AST.getLangOpts());
   if (auto *ThisExpr = N.ASTNode.get<CXXThisExpr>()) {
     if (ThisExpr->isImplicit())
       EndLoc = BeginLoc;
   }
   unsigned Begin = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(BeginLoc));
   unsigned End = SrcMgr.getFileOffset(SrcMgr.getExpansionLoc(EndLoc));
   return {Begin, End};
 }
 
-std::string SyntaxTree::getNodeValue(const DynTypedNode &DTN) const {
-  return TreeImpl->getNodeValue(DTN);
+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

test/Tooling/clang-diff-basic.cpp

 // CHECK: Match StringLiteral: foo{{.*}} to StringLiteral: foo
 const char *b = "f" "o" "o";
 
 // unsigned is canonicalized to unsigned int
 // CHECK: Match TypedefDecl: nat;unsigned int;{{.*}} to TypedefDecl: nat;unsigned int;
 typedef unsigned nat;
 
 // CHECK: Match VarDecl: p(int){{.*}} to VarDecl: prod(double)
-// CHECK: Match BinaryOperator: *{{.*}} to BinaryOperator: *
 // CHECK: Update VarDecl: p(int){{.*}} to prod(double)
+// CHECK: Match BinaryOperator: *{{.*}} to BinaryOperator: *
 double prod = 1 * 2 * 10;
 // CHECK: Update DeclRefExpr
 int squared = prod * prod;
 
 class X {
   const char *foo(int i) {
     if (i == 0)
       return "Bar";

tools/clang-diff/ClangDiff.cpp

 static void printNodeAttributes(raw_ostream &OS, diff::SyntaxTree &Tree,
                                 diff::NodeId Id) {
   const diff::Node &N = Tree.getNode(Id);
   OS << R"("id":)" << int(Id);
   OS << R"(,"type":")" << N.getTypeLabel() << '"';
   auto Offsets = Tree.getFileOffsets(N);
   OS << R"(,"begin":)" << Offsets.first;
   OS << R"(,"end":)" << Offsets.second;
-  std::string Value = Tree.getNodeValue(N.ASTNode);
+  std::string Value = Tree.getNodeValue(N);
   if (!Value.empty()) {
     OS << R"(,"value":")";
     printJsonString(OS, Value);
     OS << '"';
   }
 }
 
 static void printNodeAsJson(raw_ostream &OS, diff::SyntaxTree &Tree,
                             diff::NodeId Id) {
   const diff::Node &N = Tree.getNode(Id);
   OS << "{";
   printNodeAttributes(OS, Tree, Id);
   OS << R"(,"children":[)";
   if (N.Children.size() > 0) {
     printNodeAsJson(OS, Tree, N.Children[0]);
     for (size_t I = 1, E = N.Children.size(); I < E; ++I) {
       OS << ",";
       printNodeAsJson(OS, Tree, N.Children[I]);
     }
   }
   OS << "]}";
 }
 
+static void printNode(raw_ostream &OS, diff::SyntaxTree &Tree,
+                      diff::NodeId Id) {
+  if (Id.isInvalid()) {
+    OS << "None";
+    return;
+  }
+  OS << Tree.getNode(Id).getTypeLabel();
+  std::string Value = Tree.getNodeValue(Id);
+  if (!Value.empty())
+    OS << ": " << Value;
+  OS << "(" << Id << ")";
+}
+
+static void printDstChange(raw_ostream &OS, diff::ASTDiff &Diff,
+                           diff::SyntaxTree &SrcTree, diff::SyntaxTree &DstTree,
+                           diff::NodeId Dst) {
+  const diff::Node &DstNode = DstTree.getNode(Dst);
+  diff::NodeId Src = Diff.getMapped(DstTree, Dst);
+  switch (DstNode.ChangeKind) {
+  case diff::None:
+    break;
+  case diff::Delete:
+    llvm_unreachable("The destination tree can't have deletions.");
+  case diff::Update:
+    OS << "Update ";
+    printNode(OS, SrcTree, Src);
+    OS << " to " << DstTree.getNodeValue(Dst) << "\n";
+    break;
+  case diff::Insert:
+  case diff::Move:
+  case diff::UpdateMove:
+    if (DstNode.ChangeKind == diff::Insert)
+      OS << "Insert";
+    else if (DstNode.ChangeKind == diff::Move)
+      OS << "Move";
+    else if (DstNode.ChangeKind == diff::UpdateMove)
+      OS << "Update and Move";
+    OS << " ";
+    printNode(OS, DstTree, Dst);
+    OS << " into ";
+    printNode(OS, DstTree, DstNode.Parent);
+    OS << " at " << DstTree.findPositionInParent(Dst) << "\n";
+    break;
+  }
+}
+
 int main(int argc, const char **argv) {
   cl::HideUnrelatedOptions(ClangDiffCategory);
   if (!cl::ParseCommandLineOptions(argc, argv)) {
     cl::PrintOptionValues();
     return 1;
   }
 
   if (ASTDump) {
if (StopAfter == "topdown")
       Options.StopAfterTopDown = true;
     else if (StopAfter != "bottomup") {
       llvm::errs() << "Error: Invalid argument for -stop-after";
       return 1;
     }
   }
   diff::SyntaxTree SrcTree(Src->getASTContext());
   diff::SyntaxTree DstTree(Dst->getASTContext());
-  diff::ASTDiff DiffTool(SrcTree, DstTree, Options);
-  for (const auto &Match : DiffTool.getMatches())
-    DiffTool.printMatch(llvm::outs(), Match);
-  for (const auto &Change : DiffTool.getChanges())
-    DiffTool.printChange(llvm::outs(), Change);
+  diff::ASTDiff Diff(SrcTree, DstTree, Options);
+
+  for (diff::NodeId Dst : DstTree) {
+    diff::NodeId Src = Diff.getMapped(DstTree, Dst);
+    if (Src.isValid()) {
+      llvm::outs() << "Match ";
+      printNode(llvm::outs(), SrcTree, Src);
+      llvm::outs() << " to ";
+      printNode(llvm::outs(), DstTree, Dst);
+      llvm::outs() << "\n";
+    }
+    printDstChange(llvm::outs(), Diff, SrcTree, DstTree, Dst);
+  }
+  for (diff::NodeId Src : SrcTree) {
+    if (Diff.getMapped(SrcTree, Src).isInvalid()) {
+      llvm::outs() << "Delete ";
+      printNode(llvm::outs(), SrcTree, Src);
+      llvm::outs() << "\n";
+    }
+  }
 
   return 0;
 }