On Fri, 2010-08-06 at 15:21 -0700, Roland McGrath wrote:
So the way I've formulated it is with these definitions:
* trees are equal if their tags, attributes, and children lists are equal
* tags are integers, equality is integer equality
* children lists are equal if the same length and respective child trees equal
* attributes are equal if the same name/value pairs and equal values
* non-reference attribute values are "simple" types, equality is
type-appropriate. (Later, it may have strict/non-strict variants of
equality, for things like an exprloc vs a constant for
data_member_location location. The point being there are more details
here in practice, but there is no more algorithmic complexity to be
thinking about now.)
* reference attribute values are equal if their referent DIEs are equal
trees in equal-enough contexts
* what goes into "context" and "equal-enough" is fungible and
be tuned by practical experience with real data later in the project.
To begin with:
* context of a DIE means its parent DIE's tag, non-reference attributes,
and context (hence iterate up to compile_unit level, which is not part of
the context). (From prior discussions here, we will probably refine the
terminal context to include a small subset of compile_unit attributes.
For now, the simple definition stands.)
Hence, referent context is part of reference equality, but a tree's own
context is not part of tree equality.
So from your earlier examples, and this definition, we know that having
two DIEs, A and B, that have an attribute X that refers to some other
DIE can only equal if the DIEs pointed to by A->X and B->X, lets call
them DIE Y and Z, are equal AND have equal[-enough] contexts.
But nothing prevents us from marking Y and Z itself equal. So, lets
assume they are, and we replace them with an imported_unit DIE. How do
we deal with A->X and B->X pointing to Y and Z? I assume they now point
to the imported_unit DIEs themselves so that any "logical" DIE tree will
still be the same.
But what if any other DIE might have an attribute pointing deeper into Y
or Z itself? Where would these attributes point to? If we make point
them somewhere into the partial_unit that replaced Y and Z then a
consumer doesn't know the context anymore.
Am I missing something, or is this a situation that cannot occur?