[clang-diff] Store changes within ASTDiff::Impl

[johannes]

Summary

This way we avoid modifying SyntaxTree::Impl except during
construction.

include/clang/Tooling/ASTDiff/ASTDiff.h

 };
 
 class ASTDiff {
 public:
   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);
   ~ASTDiff();
 
   const Node *getMapped(NodeRef N) const;
+  ChangeKind getNodeChange(NodeRef N) const;
 
   class Impl;
 
 private:
   std::unique_ptr<Impl> DiffImpl;
 };
 
 /// SyntaxTree objects represent subtrees of the AST.
public:
   class Impl;
   std::unique_ptr<Impl> TreeImpl;
 };
 
 /// Represents a Clang AST node, alongside some additional information.
 struct Node {
   SyntaxTree::Impl &Tree;
   NodeId Parent, LeftMostDescendant, RightMostDescendant;
-  int Depth, Height, Shift = 0;
+  int Depth, Height;
   ast_type_traits::DynTypedNode ASTNode;
   SmallVector<NodeId, 4> Children;
-  ChangeKind Change = NoChange;
   Node(SyntaxTree::Impl &Tree) : Tree(Tree), Children() {}
   Node(NodeRef Other) = delete;
   explicit Node(Node &&Other) = default;
   Node &operator=(NodeRef Other) = delete;
   Node &operator=(Node &&Other) = default;
 
   NodeId getId() const;
   SyntaxTree &getTree() const;

lib/Tooling/ASTDiff/ASTDiff.cpp

 
 namespace clang {
 namespace diff {
 
 bool ComparisonOptions::isMatchingAllowed(NodeRef N1, NodeRef N2) const {
   return (N1.isMacro() && N2.isMacro()) || N1.getType().isSame(N2.getType());
 }
 
+namespace {
+struct NodeChange {
+  ChangeKind Change = NoChange;
+  int Shift = 0;
+  NodeChange() = default;
+  NodeChange(ChangeKind Change, int Shift) : Change(Change), Shift(Shift) {}
+};
+} // end anonymous namespace
+
 class ASTDiff::Impl {
 private:
   std::unique_ptr<NodeId[]> SrcToDst, DstToSrc;
 
 public:
   SyntaxTree::Impl &T1, &T2;
+  std::map<NodeId, NodeChange> ChangesT1, ChangesT2;
 
   Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
        const ComparisonOptions &Options);
 
   /// Matches nodes one-by-one based on their similarity.
   void computeMapping();
 
   // Compute Change for each node based on similarity.
   void computeChangeKinds();
 
   const Node *getMapped(NodeRef N) const;
 
+  ChangeKind getNodeChange(NodeRef N) 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;
 
public:
 
   int getSize() const { return Nodes.size(); }
   NodeRef getRoot() const { return getNode(getRootId()); }
   NodeId getRootId() const { return 0; }
   PreorderIterator begin() const { return &getRoot(); }
   PreorderIterator end() const { return begin() + getSize(); }
 
   NodeRef getNode(NodeId Id) const { return Nodes[Id]; }
-  Node &getMutableNode(NodeId Id) { return Nodes[Id]; }
-  Node &getMutableNode(NodeRef N) { return getMutableNode(N.getId()); }
+  Node &getMutableNode(NodeRef N) { return Nodes[N.getId()]; }
+  Node &getMutableNode(NodeId Id) { return getMutableNode(getNode(Id)); }
 
 private:
   void initTree();
   void setLeftMostDescendants();
 };
 
 NodeRef NodeRefIterator::operator*() const { return Tree->getNode(*IdPointer); }
 
void ASTDiff::Impl::computeMapping() {
   matchBottomUp();
   if (Options.StopAfterBottomUp)
     return;
   matchChildren();
 }
 
 void ASTDiff::Impl::computeChangeKinds() {
   for (NodeRef N1 : T1) {
-    if (!getDst(N1)) {
-      T1.getMutableNode(N1).Change = Delete;
-      T1.getMutableNode(N1).Shift -= 1;
-    }
+    if (!getDst(N1))
+      ChangesT1.emplace(N1.getId(), NodeChange(Delete, -1));
   }
   for (NodeRef N2 : T2) {
-    if (!getSrc(N2)) {
-      T2.getMutableNode(N2).Change = Insert;
-      T2.getMutableNode(N2).Shift -= 1;
-    }
+    if (!getSrc(N2))
+      ChangesT2.emplace(N2.getId(), NodeChange(Insert, -1));
   }
   for (NodeRef N1 : T1.NodesBfs) {
     if (!getDst(N1))
       continue;
     NodeRef N2 = *getDst(N1);
     if (!haveSameParents(N1, N2) ||
         findNewPosition(N1) != findNewPosition(N2)) {
-      T1.getMutableNode(N1).Shift -= 1;
-      T2.getMutableNode(N2).Shift -= 1;
+      ChangesT1[N1.getId()].Shift -= 1;
+      ChangesT2[N2.getId()].Shift -= 1;
     }
   }
   for (NodeRef N2 : T2.NodesBfs) {
     if (!getSrc(N2))
       continue;
     NodeRef N1 = *getSrc(N2);
-    Node &MutableN1 = T1.getMutableNode(N1);
-    Node &MutableN2 = T2.getMutableNode(N2);
     if (!haveSameParents(N1, N2) ||
         findNewPosition(N1) != findNewPosition(N2)) {
-      MutableN1.Change = MutableN2.Change = Move;
+      ChangesT1[N1.getId()].Change = ChangesT2[N2.getId()].Change = Move;
     }
     if (areNodesDifferent(N1, N2)) {
-      MutableN1.Change = MutableN2.Change =
-          (N1.Change == Move ? UpdateMove : Update);
+      bool Moved = ChangesT1[N1.getId()].Change == Move;
+      ChangesT1[N1.getId()].Change = ChangesT2[N2.getId()].Change =
+          (Moved ? UpdateMove : Update);
     }
   }
 }
 
 const Node *ASTDiff::Impl::getMapped(NodeRef N) const {
   if (&N.Tree == &T1)
     return getDst(N);
   assert(&N.Tree == &T2 && "Invalid tree.");

 }
 const Node *ASTDiff::Impl::getSrc(NodeRef N2) const {
   assert(&N2.Tree == &T2 && "Invalid tree.");
   return DstToSrc[N2.getId()].isValid() ? &T1.getNode(DstToSrc[N2.getId()])
                                         : nullptr;
 }
 
 int ASTDiff::Impl::findNewPosition(NodeRef N) const {
+  const std::map<NodeId, NodeChange> *Changes;
+  if (&N.Tree == &T1)
+    Changes = &ChangesT1;
+  else
+    Changes = &ChangesT2;
+
   if (!N.getParent())
     return 0;
   int Position = N.findPositionInParent();
   for (NodeRef Sibling : *N.getParent()) {
-    Position += Sibling.Shift;
+    if (Changes->count(Sibling.getId()))
+      Position += Changes->at(Sibling.getId()).Shift;
     if (&Sibling == &N)
       return Position;
   }
   llvm_unreachable("Node not found amongst parent's children.");
 }
 
+ChangeKind ASTDiff::Impl::getNodeChange(NodeRef N) const {
+  const std::map<NodeId, NodeChange> *Changes;
+  if (&N.Tree == &T1) {
+    Changes = &ChangesT1;
+  } else {
+    assert(&N.Tree == &T2 && "Invalid tree.");
+    Changes = &ChangesT2;
+  }
+  if (Changes->count(N.getId()))
+    return Changes->at(N.getId()).Change;
+  return NoChange;
+}
+
 ASTDiff::ASTDiff(SyntaxTree &T1, SyntaxTree &T2,
                  const ComparisonOptions &Options)
     : DiffImpl(llvm::make_unique<Impl>(*T1.TreeImpl, *T2.TreeImpl, Options)) {}
 
 ASTDiff::~ASTDiff() = default;
 
 const Node *ASTDiff::getMapped(NodeRef N) const {
   return DiffImpl->getMapped(N);
 }
 
+ChangeKind ASTDiff::getNodeChange(NodeRef N) const {
+  return DiffImpl->getNodeChange(N);
+}
+
 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

static unsigned printHtmlForNode(raw_ostream &OS, const diff::ASTDiff &Diff,
   std::tie(Begin, End) = Node.getSourceRangeOffsets();
   const SourceManager &SM = Tree.getASTContext().getSourceManager();
   auto Code = SM.getBuffer(SM.getMainFileID())->getBuffer();
   for (; Offset < Begin; ++Offset)
     printHtml(OS, Code[Offset]);
   OS << "<span id='" << MyTag << Node.getId() << "' "
      << "tid='" << OtherTag << TargetId << "' ";
   OS << "title='";
+  diff::ChangeKind Change = Diff.getNodeChange(Node);
   printHtml(OS, Node.getTypeLabel());
   OS << "\n" << LeftId << " -> " << RightId << "'";
-  if (Node.Change != diff::NoChange)
-    OS << " class='" << getChangeKindAbbr(Node.Change) << "'";
+  if (Change != diff::NoChange)
+    OS << " class='" << getChangeKindAbbr(Change) << "'";
   OS << ">";
 
   for (diff::NodeRef Child : Node)
     Offset = printHtmlForNode(OS, Diff, IsLeft, Child, Offset);
 
   for (; Offset < End; ++Offset)
     printHtml(OS, Code[Offset]);
   if (&Node == &Tree.getRoot()) {
for (diff::NodeRef Node : Tree) {
     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);
-  switch (Dst.Change) {
+  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 (Dst.Change == diff::Insert)
+    if (Change == diff::Insert)
       OS << "Insert";
-    else if (Dst.Change == diff::Move)
+    else if (Change == diff::Move)
       OS << "Move";
-    else if (Dst.Change == diff::UpdateMove)
+    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());