Re: dwarf_output overview

[Mark Wielaard <mjw at redhat dot com>]

On Fri, 2010-08-06 at 15:21 -0700, Roland McGrath wrote:
> Given circular references inside, a tree's own context can indirectly
> become part of tree equality.  But I'm not sure that's actually the way we
> want to think about it, or define it.  It's hazy to me.  (Help me on this!)
> Intuitively, it seems like two comparable trees with internal circularities
> might rightly be found equivalent even in different contexts.  But that's a
> vague notion.  Let's try to consider a case:
> 
> 	<compile_unit>
> 	  <namespace name="A">
> 	    <structure_type id="atype" name="list">
> 	      <member name="next" type="#aptr" data_member_location=0/>
> 	    </structure_type>
> 	  </namespace>
> 	  <pointer_type id="aptr" type="#atype"/>
> 	  <namespace name="B">
> 	    <structure_type id="btype" name="list">
> 	      <member name="next" type="#bptr" data_member_location=0/>
> 	    </structure_type>
> 	  </namespace>
> 	  <pointer_type id="bptr" type="#btype"/>
> 	  <variable name="a" type="#aptr"/>
> 	  <variable name="b" type="#bptr"/>
> 	</compile_unit>
> 
> Ok, that's the first case of circularity I could come up with.  Clearly
> there it does matter not to conflate type="#aptr" vs type="#bptr" in the
> two <variable/> DIEs' attributes.  If we didn't have those "outside"
> references, would it matter?  Well, no, not to tree transformation.

So it isn't about the fact that they contain circular references. It
really is just about whether or not there are references from "outside"
the DIE tree into it.

> Here's another case that's even simpler:
> [...]
> So context does matter for this "simple" circular reference case.  Though
> it would seem not to matter (absent references) in the "more complex" (but
> very common) case with {A,B}::list, above.

This, and our earlier discussions, suggest to me that the previous
definition of equality is missing a qualifier for the first case:

* trees are equal if their tags, attributes, and children lists are
  equal

This should be extended to say:

  [...], if there are no attribute references from DIEs outside the tree
  into the any of the tree DIEs.

  If there are references from outside the tree into any tree DIEs, then
  the trees are equal if their tags, attributes, children lists are
  equal, AND the tree DIEs are in equal-enough contexts.

So context matters if anything points into the tree, since context is
relevant for reference attributes. We can only mark DIE trees equal if
nothing depends on the context they are in (like outside DIE attribute
values pointing at them or any of their children).

Does that make sense?

Then the definition of equality for reference attributes can be
simplified to:

* reference attributes values are equal if their referent DIEs are equal
  trees.

Because equal trees would be in equal-enough contexts already by
definition if anything points to them.

Cheers,

Mark