On Fri, 2010-07-16 at 04:55 -0700, Roland McGrath wrote: > Here's another example to consider. (I'll use "id" as a fake attribute to > indicate what entry reference attributes point to.) > > <compile_unit> > <structure_type id="t1" name="list"> > <member name="next" type="#p1"/> > </structure_type> > <pointer_type id="p1" type="#t1"/> > <variable name="v" type="#p2"/> > <pointer_type id="p2" type="#t1"/> > </compile_unit> > vs > <compile_unit> > <structure_type id="t1" name="list"> > <member name="next" type="#p1"/> > </structure_type> > <pointer_type id="p1" type="#t1"/> > <variable name="v" type="#p1"/> > </compile_unit> > > Now, compare just the "v" entry. In the first file, the walk goes: > "v" -> p2 -> t1 -> "next" -> p1 -> t1 * CYCLE > In the second file, it goes: > "v" -> p1 -> t1 -> "next" -> p1 * CYCLE > > But, these two "v" entries are equal. When you hit it, you know you have a > cycle on the rhs, but don't have a cycle on the lhs. You can't tell that > the parallel p1's are equal or aren't until you follow the lhs further.
Nice example. Although you are getting somewhat greedy I what you want to recognize as equal :) If you want to recognize such situations you seem to have to do a full duplication/equality check on each new DIE node in your walk against all previous encountered DIEs (and not just compare against the IDs of the DIEs already seen). And if the new DIE is equal to any already encountered you mark it as a cycle to that one instead of treating it as a new one. In your example in CU1 we see p1, notice it is equal to p2 and so create a cycle to it in the walk. Which makes the CU1-v and CU2-v walks the same. That seems rather expensive. No wonder you go crazy about caching these equalities. > In the actual case, the second file is a compressed version of the first > file, where the logical tree looks like: > > <compile_unit> > <structure_type id="t1" name="list"> > <member name="next" type="#p1"/> > </structure_type> > <pointer_type id="p1" type="#t1"/> > <variable name="v" type="#p1"/> > <pointer_type id="p1" type="#t1"/> > </compile_unit> > > because both "p1" nodes (or whole subtrees if they were that) are actually > the same physical thing with imported_unit entries telling us to synthesize > a logical tree view with that subtree grafted in at two places. So then, > both whole compile_unit trees are entirely equal, not just the walk rooted > at "v". I am not completely following this example. So we have two DIE nodes with the exact same identifier. Wouldn't we just treat those always equal anyway? Cheers, Mark _______________________________________________ elfutils-devel mailing list [email protected] https://fedorahosted.org/mailman/listinfo/elfutils-devel
