Re: comparing die trees/graphs

[Roland McGrath <roland at redhat dot com>]

> (I am not yet really clear which attributes matter for the
> context path and which don't).

It's not really well-established yet.  We'll want to tune that later on.
To a first approximation, we can say it's none of the attributes of the
root compile_unit entry, and all of the attributes of other levels of the
tree.

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

Right.  Since non-reference attributes are most of the actual "meat", it's
natural to compare attributes before children, since in a mismatch usually
the simply-valued attributes won't match.  This makes attribute references
before children seem like the natural order as to the graph walking.

Here's another example to consider.  (I'll use "id" as a fake attribute to
indicate what entry reference attributes point to.)

	<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="#p2"/>
	  <pointer_type id="p2" type="#t1"/>
	</compile_unit>
vs
	<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"/>
	</compile_unit>

Now, compare just the "v" entry.  In the first file, the walk goes:
	"v" -> p2 -> t1 -> "next" -> p1 -> t1 * CYCLE
In the second file, it goes:
	"v" -> p1 -> t1 -> "next" -> p1 * CYCLE

But, these two "v" entries are equal.  When you hit it, you know you have a
cycle on the rhs, but don't have a cycle on the lhs.  You can't tell that
the parallel p1's are equal or aren't until you follow the lhs further.

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


Thanks,
Roland