Re: comparing die trees/graphs

[Mark Wielaard <mjw at redhat dot com>]

On Fri, 2010-07-16 at 03:38 -0700, Roland McGrath wrote:
> Which "what"?  The contents of a subtree is not all that matters.
> 
> Consider these two trees:
> 
> 	<compile_unit>
> 	  <namespace name="a">
> 	    <class_type name="foo">
> 	      <member name="x"/>
> 	    </class_type>
> 	  </namespace>
> 	  <variable name="v" type="#ref to a::foo"/>
> 	</compile_unit>
> 
> 	<compile_unit>
> 	  <namespace name="b">
> 	    <class_type name="foo">
> 	      <member name="x"/>
> 	    </class_type>
> 	  </namespace>
> 	  <variable name="v" type="#ref to b::foo"/>
> 	</compile_unit>
> 
> Now, are the two "v" entries equal?  They are if their type attribute
> references are equal.  If "what they reference" means just the subtree,
> then both those "foo" subtrees are identical.  
> 
> But it would be wrong to conflate these two references together and thus
> call each "v" equal to the other.  One has type a::foo and one has type
> b::foo, and never the twain shall meet.

Thanks for that example! OK, I did completely miss that. So for each DIE
to be considered equal you also need to account for the "context path"
from the root (CU). Which is a secondary tree walk...
Except that for this walk you might care about different attributes of
the DIEs to take into consideration for determining what counts as
"equal" (I am not yet really clear which attributes matter for the
context path and which don't).

> > And that is indeed the part I find somewhat hard to understand. In my
> > (simplistic) view all you need is the depth-first recursive traversal
> > (keep track of circularity, mark them, stop recursing, and check it is
> > the same circular reference in both walks). And if the full walk in both
> > trees finds the exact same path with the exact same nodes in both you
> > are done, they are similar.
> 
> It's not quite clear to me what this traversal order is with respect to
> references.  The comparator checks attributes first, then children, so its
> walk follows references depth-first, then children depth-first, at each node.

It shouldn't matter. Just pick one and be consistent. Either first
follow all attribute references (in a particular deterministic order) or
the children. As long as it is clear what the expected order is. Only
attribute references can create circles, but that seems just a
technicality.

Thanks for the explanations. I think I now finally understand what the
comparator/tracker try to match up.

Cheers,

Mark