johannes added inline comments.
================
Comment at: lib/Tooling/ASTDiff/ASTDiff.cpp:730
+
+Mapping TreeComparator::matchTopDown() const {
+ PriorityList L1(T1);
----------------
arphaman wrote:
> Johannes, it seems to me that your implementation of the top-down portion of
> the GumTree algorithm doesn't use the `an empty list A of candidate mappings`
> that's described in the paper (and that you have in the Python prototype). Is
> that correct or am I missing something?
Yes, initially I implemented it as it is described in the paper, but then I
realized that the list of candidate mappings will always stay empty, because
the condition in the top-down algorithm in the paper on line 14 will never be
true. Maybe I am mistaken here, but if `t1` and `t2` are isomorphic, then none
of the descendants of `t1` will be isomorphic to `t2`. I mean, the height of
isomorphic trees must be equal, and the descendant does not have the same
height. So to me this looks like an error in the paper, I probably should have
communicated this.
What I did instead is, I had a look at the reference implementation, and what
they do instead of using a list of candidate mappings is to just use a data
structure for the mapping that allows multiple matches for each node.
After matching collecting all candidates this way, they extract the unambiguous
matches and then sort the ambiguous matches by their parents' similarity.
[[
https://github.com/GumTreeDiff/gumtree/blob/develop/core/src/main/java/com/github/gumtreediff/matchers/heuristic/gt/AbstractSubtreeMatcher.java
| AbstractSubtreeMatcher.java ]]
[[
https://github.com/GumTreeDiff/gumtree/blob/develop/core/src/main/java/com/github/gumtreediff/matchers/heuristic/gt/GreedySubtreeMatcher.java
| GreedySubtreeMatcher.java ]]
This seems to be a good solution, I plan to implement that in the future.
https://reviews.llvm.org/D34329
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
