johannes added inline comments.
================
Comment at: lib/Tooling/ASTDiff/ASTDiff.cpp:730
+
+Mapping TreeComparator::matchTopDown() const {
+ PriorityList L1(T1);
----------------
johannes wrote:
> 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.
My bad, I misread the algorithm in the paper, of course the entire tree is
searched for other isomorphic subtrees.
I will still stick to the way it is implemented in gumtree, it should be more
efficient.
https://reviews.llvm.org/D34329
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
