comparing die trees/graphs

Roland McGrath roland at redhat.com
Fri Jul 16 10:38:34 UTC 2010


> I make that distinction because I really would like to see the
> equivalence as comparing two lists (the depth-first search paths) of
> nodes (DIEs). This might confuse matters a little since we go from
> concept to comparison algorithm immediately.

Ok, I see what you mean.  You are talking about the entire walk here when
you say a "path".

> > The definition for "exact equivalence" I mean is that each parent DIE
> > has matching attributes and equivalent parents.  That's a recursive
> > definition, so it iterates on up to the root of the tree (the CU).
> 
> Why the CU? Isn't the start the starting DIE(s) of the comparison? The
> CU seems to be just another DIE that might be in the (flattened) path
> (both CU DIEs should of course be equivalent if the appear in a
> depth-first walk of the tree).

It sounds like we are talking past each other here.  This paragraph is all
about the "context".  For "context" we are only talking about the tree
path, not any path walking references.

> I am not sure I am following that. Isn't what they reference precisely
> what makes them similar or not?

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.

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

> The stack is just my way of expressing we keep the path of DIEs traveled
> so far. It is just keeping track of when we saw which DIE. And if any
> deeper reference points to a DIE we already seen it will be on that
> stack (path) and for the other DIE tree to be equivalent it needs to
> have a DIE reference to exactly the same point in the stack (path) we
> are constructing while walking the other DIE tree.

Ok.  I think this is similar to what the core of the reference_match logic
does.  Your stack is the call frame stack.  Each recursion records a
pointer in a map keyed by the lhs DIE identity.  It checks this map for an
existing entry, and looks at this record.  What that records is the rhs DIE
identity that recursion is comparing the lhs to.  So if that record matches
the rhs we are comparing to now, then the circularities match.

> I don't doubt that without caching things might be somewhat inefficient.
> But the caching confuses me somewhat, so for now I am trying to ignore
> it. Wouldn't we see every subtree only once, since we are just walking
> the tree from starting DIE in a specific order (breaking cycles when we
> notice we already seen a DIE node earlier in the walk)?

I think that makes sense, yes.


Thanks,
Roland


More information about the elfutils-devel mailing list