Re: comparing die trees/graphs

[Roland McGrath <roland at redhat dot com>]

> Nice example. Although you are getting somewhat greedy I what you want
> to recognize as equal :)

Thosea are the correct semantics, even by your problem description.

> 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'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.

> > 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.


Thanks,
Roland