Re: comparing die trees/graphs

[Mark Wielaard <mjw at redhat dot com>]

On Fri, 2010-07-16 at 14:51 +0200, Mark Wielaard wrote:
> 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 in 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.

Thinking about it a bit more it seems a bit less expensive than what I
described before. You don't need to proof equivalence between every DIE
node on the path. Just if you come across a cycle (back reference to a
point on the walk-path) on one, only then you have to proof that the
next DIE node on the other path is equal (or identical) to the same DIE
node in the same place on the other walk-path. Still seems somewhat
expensive though.

And I do need to convince myself that this will actually terminate in
the case of crazy double double equal DIE nodes in the graph.

Phew,

Mark