Re: comparing die trees/graphs

[Mark Wielaard <mjw at redhat dot com>]

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