[clang-diff] Move printing of changes to the ASTDiff library

include/clang/Tooling/ASTDiff/ASTDiff.h

enum ChangeKind {
   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.
 };
 
 using NodeRef = const Node &;
 
+void printChangeKind(raw_ostream &OS, ChangeKind Kind);
+
 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;
 

 class ASTDiff {
 public:
   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
   ~ASTDiff();
 
   const Node *getMapped(NodeRef N) const;
   ChangeKind getNodeChange(NodeRef N) const;
 
+  void dumpChanges(raw_ostream &OS, bool DumpMatches = false) 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.
struct Node {
   bool isLeaf() const { return Children.empty(); }
   bool isMacro() const;
   llvm::Optional<StringRef> getIdentifier() const;
   llvm::Optional<std::string> getQualifiedIdentifier() const;
 
   NodeRefIterator begin() const;
   NodeRefIterator end() const;
 
+  void dump(raw_ostream &OS) const {
+    OS << getTypeLabel() << "(" << getId() << ")";
+  }
+
   int findPositionInParent() const;
 
   /// Returns the range that contains the text that is associated with this
   /// node. This is based on DynTypedNode::getSourceRange() with a couple of
   /// workarounds.
   ///
   /// The range for statements includes the trailing semicolon.
   ///
struct Node {
   SmallVector<SourceLocation, 4> getOwnedTokens() const;
 };
 
 void forEachTokenInRange(CharSourceRange Range, SyntaxTree &Tree,
                          std::function<void(Token &)> Body);
 
 inline bool isListSeparator(Token &Tok) { return Tok.is(tok::comma); }
 
-struct NodeRefIterator {
+struct NodeRefIterator
+    : public std::iterator<std::random_access_iterator_tag, NodeId> {
+  using difference_type =
+      std::iterator<std::random_access_iterator_tag, Type>::difference_type;
+
   SyntaxTree::Impl *Tree;
   const NodeId *IdPointer;
   NodeRefIterator(SyntaxTree::Impl *Tree, const NodeId *IdPointer)
       : Tree(Tree), IdPointer(IdPointer) {}
   NodeRef operator*() const;
   NodeRefIterator &operator++();
   NodeRefIterator &operator+(int Offset);
+  difference_type operator-(const NodeRefIterator &Other) const;
   bool operator!=(const NodeRefIterator &Other) const;
+  bool operator==(const NodeRefIterator &Other) const;
 };
 
 } // end namespace diff
 } // end namespace clang
 
 #endif

lib/Tooling/ASTDiff/ASTDiff.cpp

 using namespace clang;
 
 namespace clang {
 namespace diff {
 
 bool ComparisonOptions::isMatchingAllowed(NodeRef N1, NodeRef N2) const {
   return (N1.isMacro() && N2.isMacro()) || N1.getType().isSame(N2.getType());
 }
+void printChangeKind(raw_ostream &OS, ChangeKind Kind) {
+  switch (Kind) {
+  case NoChange:
+    break;
+  case Delete:
+    OS << "Delete";
+    break;
+  case Update:
+    OS << "Update";
+    break;
+  case Insert:
+    OS << "Insert";
+    break;
+  case Move:
+    OS << "Move";
+    break;
+  case UpdateMove:
+    OS << "Update and Move";
+    break;
+  }
+}
 
 namespace {
 struct NodeChange {
   ChangeKind Change = NoChange;
   int Shift = 0;
   NodeChange() = default;
   NodeChange(ChangeKind Change, int Shift) : Change(Change), Shift(Shift) {}
 };
public:
 
   // Compute Change for each node based on similarity.
   void computeChangeKinds();
 
   const Node *getMapped(NodeRef N) const;
 
   ChangeKind getNodeChange(NodeRef N) const;
 
+  void dumpChanges(raw_ostream &OS, bool DumpMatches) const;
+
 private:
   // Adds a mapping between two nodes.
   void link(NodeRef N1, NodeRef N2);
 
   // Returns the mapped node, or null.
   const Node *getDst(NodeRef N1) const;
   const Node *getSrc(NodeRef N2) const;
 

 const Node *ASTDiff::getMapped(NodeRef N) const {
   return DiffImpl->getMapped(N);
 }
 
 ChangeKind ASTDiff::getNodeChange(NodeRef N) const {
   return DiffImpl->getNodeChange(N);
 }
 
+static void dumpDstChange(raw_ostream &OS, const ASTDiff::Impl &Diff,
+                          SyntaxTree::Impl &SrcTree, SyntaxTree::Impl &DstTree,
+                          NodeRef Dst) {
+  const Node *Src = Diff.getMapped(Dst);
+  ChangeKind Change = Diff.getNodeChange(Dst);
+  printChangeKind(OS, Change);
+  switch (Change) {
+  case NoChange:
+    break;
+  case Delete:
+    llvm_unreachable("The destination tree can't have deletions.");
+  case Update:
+    OS << " ";
+    Src->dump(OS);
+    OS << "\n";
+    break;
+  case Insert:
+  case Move:
+  case UpdateMove:
+    OS << " ";
+    Dst.dump(OS);
+    OS << " into ";
+    if (!Dst.getParent())
+      OS << "None";
+    else
+      Dst.getParent()->dump(OS);
+    OS << " at " << Dst.findPositionInParent() << "\n";
+    break;
+  }
+}
+
+void ASTDiff::Impl::dumpChanges(raw_ostream &OS, bool DumpMatches) const {
+  for (NodeRef N2 : T2) {
+    const Node *N1 = getMapped(N2);
+    if (DumpMatches && N1) {
+      OS << "Match ";
+      N1->dump(OS);
+      OS << " to ";
+      N2.dump(OS);
+      OS << "\n";
+    }
+    dumpDstChange(OS, *this, T1, T2, N2);
+  }
+  for (NodeRef N1 : T1) {
+    if (!getMapped(N1)) {
+      OS << "Delete ";
+      N1.dump(OS);
+      OS << "\n";
+    }
+  }
+}
+
+void ASTDiff::dumpChanges(raw_ostream &OS, bool DumpMatches) const {
+  DiffImpl->dumpChanges(OS, DumpMatches);
+}
+
 SyntaxTree::SyntaxTree(ASTUnit &AST)
     : TreeImpl(llvm::make_unique<SyntaxTree::Impl>(
           this, AST.getASTContext().getTranslationUnitDecl(), AST)) {}
 
 SyntaxTree::~SyntaxTree() = default;
 
 ASTUnit &SyntaxTree::getASTUnit() const { return TreeImpl->AST; }
 

tools/clang-diff/ClangDiff.cpp

if (ChildBegin != ChildEnd) {
     for (++ChildBegin; ChildBegin != ChildEnd; ++ChildBegin) {
       OS << ",";
       printNodeAsJson(OS, Tree, *ChildBegin);
     }
   }
   OS << "]}";
 }
 
-static void printNode(raw_ostream &OS, diff::SyntaxTree &Tree,
-                      diff::NodeRef Node) {
-  OS << Node.getTypeLabel();
-  OS << "(" << Node.getId() << ")";
-}
-
 static void printTree(raw_ostream &OS, diff::SyntaxTree &Tree) {
   for (diff::NodeRef Node : Tree) {
     for (int I = 0; I < Node.Depth; ++I)
       OS << " ";
-    printNode(OS, Tree, Node);
+    Node.dump(OS);
     OS << "\n";
   }
 }
 
-static void printDstChange(raw_ostream &OS, diff::ASTDiff &Diff,
-                           diff::SyntaxTree &SrcTree, diff::SyntaxTree &DstTree,
-                           diff::NodeRef Dst) {
-  const diff::Node *Src = Diff.getMapped(Dst);
-  diff::ChangeKind Change = Diff.getNodeChange(Dst);
-  switch (Change) {
-  case diff::NoChange:
-    break;
-  case diff::Delete:
-    llvm_unreachable("The destination tree can't have deletions.");
-  case diff::Update:
-    OS << "Update ";
-    printNode(OS, SrcTree, *Src);
-    OS << "\n";
-    break;
-  case diff::Insert:
-  case diff::Move:
-  case diff::UpdateMove:
-    if (Change == diff::Insert)
-      OS << "Insert";
-    else if (Change == diff::Move)
-      OS << "Move";
-    else if (Change == diff::UpdateMove)
-      OS << "Update and Move";
-    OS << " ";
-    printNode(OS, DstTree, Dst);
-    OS << " into ";
-    if (!Dst.getParent())
-      OS << "None";
-    else
-      printNode(OS, DstTree, *Dst.getParent());
-    OS << " at " << Dst.findPositionInParent() << "\n";
-    break;
-  }
-}
-
 int main(int argc, const char **argv) {
   std::string ErrorMessage;
   std::unique_ptr<CompilationDatabase> CommonCompilations =
       FixedCompilationDatabase::loadFromCommandLine(argc, argv, ErrorMessage);
   if (!CommonCompilations && !ErrorMessage.empty())
     llvm::errs() << ErrorMessage;
   cl::HideUnrelatedOptions(ClangDiffCategory);
   if (!cl::ParseCommandLineOptions(argc, argv)) {
if (HtmlDiff) {
     llvm::outs() << "</div>";
     llvm::outs() << "<div id='R' class='code'>";
     printHtmlForNode(llvm::outs(), Diff, false, DstTree.getRoot(), 0);
     llvm::outs() << "</div>";
     llvm::outs() << "</pre></div></body></html>\n";
     return 0;
   }
 
-  for (diff::NodeRef Dst : DstTree) {
-    const diff::Node *Src = Diff.getMapped(Dst);
-    if (PrintMatches && Src) {
-      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::NodeRef Src : SrcTree) {
-    if (!Diff.getMapped(Src)) {
-      llvm::outs() << "Delete ";
-      printNode(llvm::outs(), SrcTree, Src);
-      llvm::outs() << "\n";
-    }
-  }
+  Diff.dumpChanges(llvm::outs(), PrintMatches);
 
   return 0;
 }