[clang-diff] Match nodes with the same parent and same value

[johannes]

Summary

This adds another pass to the matching algorithm that tries to match nodes with
common parents, if they have similar values.

[johannes]

update

include/clang/Tooling/ASTDiff/ASTDiff.h

struct ComparisonOptions {
   /// 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;
 
   bool StopAfterTopDown = false;
+  bool StopAfterBottomUp = false;
 
   /// Returns false if the nodes should never be matched.
   bool isMatchingAllowed(NodeRef N1, NodeRef N2) const;
 };
 
 class ASTDiff {
 public:
   ASTDiff(SyntaxTree &Src, SyntaxTree &Dst, const ComparisonOptions &Options);

lib/Tooling/ASTDiff/ASTDiff.cpp

private:
   // Uses an optimal albeit slow algorithm to compute a mapping between two
   // subtrees, but only if both have fewer nodes than MaxSize.
   void addOptimalMapping(NodeRef N1, NodeRef N2);
 
   // Computes the ratio of common descendants between the two nodes.
   // Descendants are only considered to be equal when they are mapped.
   double getJaccardSimilarity(NodeRef N1, NodeRef N2) const;
 
+  double getNodeSimilarity(NodeRef N1, NodeRef N2) const;
+
   // Returns the node that has the highest degree of similarity.
   const Node *findCandidate(NodeRef N1) const;
 
+  const Node *findCandidateFromChildren(NodeRef N1, NodeRef P2) const;
+
   // Returns a mapping of identical subtrees.
   void matchTopDown();
 
   // Tries to match any yet unmapped nodes, in a bottom-up fashion.
   void matchBottomUp();
 
+  // Matches nodes, whose parents are matched.
+  void matchChildren();
+
   int findNewPosition(NodeRef N) const;
 
   const ComparisonOptions &Options;
 
   friend class ZhangShashaMatcher;
 };
 
 namespace {
double Denominator = getNumberOfDescendants(N1) - 1 +
                        getNumberOfDescendants(N2) - 1 - CommonDescendants;
   // CommonDescendants is less than the size of one subtree.
   assert(Denominator >= 0 && "Expected non-negative denominator.");
   if (Denominator == 0)
     return 0;
   return CommonDescendants / Denominator;
 }
 
+double ASTDiff::Impl::getNodeSimilarity(NodeRef N1, NodeRef N2) const {
+  auto Ident1 = N1.getIdentifier(), Ident2 = N2.getIdentifier();
+
+  bool SameValue = T1.getNodeValue(N1) == T2.getNodeValue(N2);
+  auto SameIdent = Ident1 && Ident2 && *Ident1 == *Ident2;
+
+  double NodeSimilarity = 0;
+  NodeSimilarity += SameValue;
+  NodeSimilarity += SameIdent;
+
+  assert(haveSameParents(N1, N2));
+  return NodeSimilarity * Options.MinSimilarity;
+}
+
 const Node *ASTDiff::Impl::findCandidate(NodeRef N1) const {
   const Node *Candidate = nullptr;
   double HighestSimilarity = 0.0;
   for (NodeRef N2 : T2) {
     if (!isMatchingPossible(N1, N2))
       continue;
     if (getSrc(N2))
       continue;
     double Similarity = getJaccardSimilarity(N1, N2);
     if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
       HighestSimilarity = Similarity;
       Candidate = &N2;
     }
   }
   return Candidate;
 }
 
+const Node *ASTDiff::Impl::findCandidateFromChildren(NodeRef N1,
+                                                     NodeRef P2) const {
+  const Node *Candidate = nullptr;
+  double HighestSimilarity = 0.0;
+  for (NodeRef N2 : P2) {
+    if (!isMatchingPossible(N1, N2))
+      continue;
+    if (getSrc(N2))
+      continue;
+    double Similarity = getJaccardSimilarity(N1, N2);
+    Similarity += getNodeSimilarity(N1, N2);
+    if (Similarity >= Options.MinSimilarity && Similarity > HighestSimilarity) {
+      HighestSimilarity = Similarity;
+      Candidate = &N2;
+    }
+  }
+  return Candidate;
+}
+
 void ASTDiff::Impl::matchBottomUp() {
   std::vector<NodeId> Postorder = getSubtreePostorder(T1, T1.getRootId());
   for (NodeId Id1 : Postorder) {
     if (Id1 == T1.getRootId() && !getDst(T1.getRoot()) &&
         !getSrc(T2.getRoot())) {
       if (isMatchingPossible(T1.getRoot(), T2.getRoot())) {
         link(T1.getRoot(), T2.getRoot());
         addOptimalMapping(T1.getRoot(), T2.getRoot());
for (NodeId Id1 : Postorder) {
     const Node *N2 = findCandidate(N1);
     if (N2) {
       link(N1, *N2);
       addOptimalMapping(N1, *N2);
     }
   }
 }
 
+void ASTDiff::Impl::matchChildren() {
+  for (NodeRef N1 : T1) {
+    if (getDst(N1))
+      continue;
+    if (!N1.getParent())
+      continue;
+    NodeRef P1 = *N1.getParent();
+    if (!getDst(P1))
+      continue;
+    NodeRef P2 = *getDst(P1);
+    const Node *N2 = findCandidateFromChildren(N1, P2);
+    if (N2) {
+      link(N1, *N2);
+      addOptimalMapping(N1, *N2);
+    }
+  }
+}
+
 void ASTDiff::Impl::matchTopDown() {
   PriorityList L1(T1);
   PriorityList L2(T2);
 
   L1.push(T1.getRootId());
   L2.push(T2.getRootId());
 
   int Max1, Max2;
ASTDiff::Impl::Impl(SyntaxTree::Impl &T1, SyntaxTree::Impl &T2,
   computeChangeKinds();
 }
 
 void ASTDiff::Impl::computeMapping() {
   matchTopDown();
   if (Options.StopAfterTopDown)
     return;
   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;
     }

test/Tooling/clang-diff-bottomup.cpp

 // RUN: %clang_cc1 -E %s > %t.src.cpp
 // RUN: %clang_cc1 -E %s > %t.dst.cpp -DDEST
-// RUN: clang-diff -dump-matches -s=0 %t.src.cpp %t.dst.cpp -- | FileCheck %s
+// RUN: clang-diff -dump-matches -s=0 -stop-diff-after=bottomup %t.src.cpp %t.dst.cpp -- | FileCheck %s
 //
 // Test the bottom-up matching, with maxsize set to 0, so that the optimal matching will never be applied.
 
 #ifndef DEST
 
 void f1() { ; {{;}} }
 void f2() { ;; {{;}} }
 

test/Tooling/clang-diff-heuristics.cpp

+// RUN: %clang_cc1 -E %s > %t.src.cpp
+// RUN: %clang_cc1 -E %s > %t.dst.cpp -DDEST
+// RUN: clang-diff -dump-matches -s=0 %t.src.cpp %t.dst.cpp -- | FileCheck %s
+//
+// Test the heuristics, with maxsize set to 0, so that the optimal matching will never be applied.
+
+#ifndef DEST
+
+void f1() {;}
+
+void f2(int) {;}
+
+#else
+
+// same parents, same value
+// CHECK: Match FunctionDecl: f1(void ())(1) to FunctionDecl: f1(void ())(1)
+// CHECK: Match CompoundStmt
+void f1() {}
+
+// same parents, same identifier
+// CHECK: Match FunctionDecl: f2(void (int))(4) to FunctionDecl: f2(void ())(3)
+// CHECK: Match CompoundStmt
+void f2() {}
+
+#endif

test/Tooling/clang-diff-opt.cpp

 // RUN: %clang_cc1 -E %s > %t.src.cpp
 // RUN: %clang_cc1 -E %s > %t.dst.cpp -DDEST
-// RUN: clang-diff -dump-matches -s=10 %t.src.cpp %t.dst.cpp -- | FileCheck %s
+// RUN: clang-diff -dump-matches -s=10 -stop-diff-after=bottomup %t.src.cpp %t.dst.cpp -- | FileCheck %s
 //
 // Test the behaviour of the matching according to the optimal tree edit
 // distance, implemented with Zhang and Shasha's algorithm.
 // Just for testing we use a tiny value of 10 for maxsize. Subtrees bigger than
 // this size will not be processed by the optimal algorithm.
 
 #ifndef DEST
 

tools/clang-diff/ClangDiff.cpp

if (!Src || !Dst)
     return 1;
 
   diff::ComparisonOptions Options;
   if (MaxSize != -1)
     Options.MaxSize = MaxSize;
   if (!StopAfter.empty()) {
     if (StopAfter == "topdown")
       Options.StopAfterTopDown = true;
-    else if (StopAfter != "bottomup") {
-      llvm::errs() << "Error: Invalid argument for -stop-after\n";
+    else if (StopAfter == "bottomup")
+      Options.StopAfterBottomUp = true;
+    else {
+      llvm::errs() << "Error: Invalid argument for -stop-diff-after\n";
       return 1;
     }
   }
   diff::SyntaxTree SrcTree(Src->getASTContext());
   diff::SyntaxTree DstTree(Dst->getASTContext());
   diff::ASTDiff Diff(SrcTree, DstTree, Options);
 
   if (HtmlDiff) {