johannes updated this revision to Diff 121641.
johannes added a comment.
update
https://reviews.llvm.org/D36687
Files:
include/clang/Tooling/ASTDiff/ASTDiff.h
lib/Tooling/ASTDiff/ASTDiff.cpp
test/Tooling/clang-diff-bottomup.cpp
test/Tooling/clang-diff-heuristics.cpp
test/Tooling/clang-diff-opt.cpp
tools/clang-diff/ClangDiff.cpp
Index: tools/clang-diff/ClangDiff.cpp
===================================================================
--- tools/clang-diff/ClangDiff.cpp
+++ tools/clang-diff/ClangDiff.cpp
@@ -496,8 +496,10 @@
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;
}
}
Index: test/Tooling/clang-diff-opt.cpp
===================================================================
--- test/Tooling/clang-diff-opt.cpp
+++ test/Tooling/clang-diff-opt.cpp
@@ -1,6 +1,6 @@
// 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.
Index: test/Tooling/clang-diff-heuristics.cpp
===================================================================
--- /dev/null
+++ test/Tooling/clang-diff-heuristics.cpp
@@ -0,0 +1,25 @@
+// 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
Index: test/Tooling/clang-diff-bottomup.cpp
===================================================================
--- test/Tooling/clang-diff-bottomup.cpp
+++ test/Tooling/clang-diff-bottomup.cpp
@@ -1,6 +1,6 @@
// 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.
Index: lib/Tooling/ASTDiff/ASTDiff.cpp
===================================================================
--- lib/Tooling/ASTDiff/ASTDiff.cpp
+++ lib/Tooling/ASTDiff/ASTDiff.cpp
@@ -74,15 +74,22 @@
// 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;
@@ -832,6 +839,20 @@
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;
@@ -849,6 +870,25 @@
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) {
@@ -879,6 +919,24 @@
}
}
+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);
@@ -936,6 +994,9 @@
if (Options.StopAfterTopDown)
return;
matchBottomUp();
+ if (Options.StopAfterBottomUp)
+ return;
+ matchChildren();
}
void ASTDiff::Impl::computeChangeKinds() {
Index: include/clang/Tooling/ASTDiff/ASTDiff.h
===================================================================
--- include/clang/Tooling/ASTDiff/ASTDiff.h
+++ include/clang/Tooling/ASTDiff/ASTDiff.h
@@ -49,6 +49,7 @@
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;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
