On Fri, 2010-07-16 at 02:17 -0700, Roland McGrath wrote:
> - For two DIEs to be equal the attribute values of the
attributes with
> the same key names that have references to DIEs as value should:
> a) Be both not yet seen DIEs in the respective trees so far, and
> be equal DIEs (in this case we can just treat the attribute
> reference as we would a child DIE, compare it in order).
> Or:
> b) Be both already seen DIEs in the respective trees so far, and be
> in the "same location".
I don't understand the "already seen" or not distinction here. Whether
they are forward references or not doesn't matter in any way I can think
of (except in how you'd implement it, of course). Regardless, you need
the subtrees to be equal and their locations to be equivalent.
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.
To me we are comparing paths, and "already seen" nodes/dies are just
things that have to be the same on both paths.
> The "same location" means that the references to the
DIEs in the trees
> are at the same place if we would walk the tree in the order chosen
> above.
Approximately, yes. I've called this "equivalent context" rather than
"same location" to abstract it a little.
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).
For the overall goal of maximal sharing constrained only by the real
high-level semantic needs to avoid wrong conflations, we'll want some
flexibility to ignore some kinds of attribute differences.
This decision is encoded in dwarf_comparator::equal_enough. The current
definition of "equal enough" is that we ignore the reference attributes.
That's as much as anything else just because another vector of complex
equality checking with references would just make things even harder to
think about. In practice, I'm pretty sure the differences between
"context" DIEs that matter semantically are not in their references.
I am not sure I am following that. Isn't what they reference precisely
what makes them similar or not?
> To keep the order of the nodes I would keep two stacks of DIEs
that
> represent the path traveled so far. That way whether or not a DIE has
> already been seen is just whether it is already on the stack, and the
> "location" can just be expressed as the index of that DIE into the
> stack.
The comparator does a depth-first recursive traversal. So it has a live
call frame associated with each DIE currently under consideration.
Remembering anything beyond that is done by the tracker.
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.
I'm not sure I followed exactly what you meant about a stack or
how it
relates to the tracking we have going on now.
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.
If you follow forward references immediately to answer the equality
question, you will cover lots of the tree out of order relative to the
main comparison walk. If you did no caching, you would repeat many
subtree comparisons many many times.
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)?
Cheers,
Mark