Re: comparing die trees/graphs

[Mark Wielaard <mjw at redhat dot com>]

On Fri, 2010-07-16 at 13:05 -0700, Roland McGrath wrote:
> > Nice example. Although you are getting somewhat greedy in what you want
> > to recognize as equal :)
> 
> Those are the correct semantics, even by your problem description.

Yes, they are semantically equal. I was just pointing out that this is
an extra syntactical equivalence recognition step. These do add up. The
concern is more with the added complexity. It might not be that bad in
practice though.

> That's not how I approached it in dwarfcmp.  But that is similar to the
> approach in dwarf_output, where "comparison" is only part of the issue.

OK, so some of the equivalence detection can be done when we read in the
original DIEs and others when we write out the DIEs again.

> > > 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?
> 
> I don't understand this question.

We talked about this a little on irc. Just for the list. The example was
just to highlight that the physical tree (where imported_unit entries
are not expanded) is simpler to compare because there are equal nodes
that don't need any walking. (dwarflint could/can check that
imported_unit subtrees are used only in equivalent context.)

Cheers,

Mark