On Tue, 2010-11-09 at 00:41 -0800, Roland McGrath wrote:
> So the problem comes from including the hash of all reference
attributes
> in the construction of the "unique identifier object" for a attribute
> reference that points to a die. That means that references inside
> circular structures cannot really be completed since during the
> construction of the "unique identifier object" of reference to that
> circular structure itself it can never be fully resolved.
Here you mean the references that are themselves steps along the cyclic
reference chain, right? That is, not each and every reference that
appears inside a DIE tree that is part of a cycle. For example, a
reference whose referent is some <base_type .../> DIE can always be
completed, because that referent has no other references. Likewise, a
<const_type type=.../> can be completed if its type=... referent is a
base_type. Likewise, a <pointer_type type=.../> whose referent is such
a const_type, etc. i.e., any reference that is not itself part of a
cyclic reference chain. I think that's what you meant, but I want
always to be sure we are being precise in understanding each other.
Yes that is what I meant, but you don't really know which reference
attributes those are till you resolve them (fully).
> So it seems that we should declare two "resolved"
states for DIEs. One
> "tree resolved" that takes into account just the basic attributes plus
> all the children "tree resolved". And another "fully resolved"
that
> all attributes, including reference values into account, plus "fully
> resolved" children.
That sounds familiar. In some previous iterations of the 'struct entry'
thing with pending counts, I had multiple different kinds of pending
counts. It all got very confusing and I went back and forth confounding
myself several times before settling on the apparently simpler approach
we have now. That doesn't mean this isn't the right way to go. But it
will take great care, and much better reasoning and commenting than I
did before, to make sure it all makes sense. I'm sure what I did before
is not exactly what you are proposing, but it certainly was a way to
make all the code even harder to follow.
It seems to become very messy if we want to do anything clever so we
don't just scan over the DIE tree twice. At least I get quickly lost
unless I just think of it as a two-pass algorithm (scan over the whole
tree once to calculate hashes just using the children, then scan over
the whole tree again to calculate the hashes taking the reference
attributes into account using the die->hash map of the first pass).
> A reference value then only needs its referent DIE to be
"tree
> resolved" to create the "unique identifier object" for it. That
> "breaks the circle" at the start of a reference attribute value so you
> don't need to track circularity anymore.
Ok, I think that makes sense. But then we come back to the case of
<pointer_type type=.../>. That has no children and no non-reference
attributes, so there is nothing but DW_TAG_pointer_type to contribute to
its hash value, and so all of them hash the same.
Yes, but that isn't a problem I believe. Those DIEs are hash equal in
the "first pass", but we don't use the result of that for any actual
comparison. They get their hash "augmented" by the second pass which
takes the reference attributes into account (using the hash of the first
pass for the DIE the reference attribute points to).
> The disadvantage is that you end up with two "pending
queues" which
> seems to effectively mean you will scan the whole DIE tree twice (or at
> least calculate the hash over a DIE twice, without and then with taking
> reference values into account).
This might not be as repetitive as it sounds. You don't need to visit
the non-reference attributes a second time. In "tree resolved" state,
you can take the complete hash of all the non-reference attributes, and
also hash just the names of the reference attributes, and combine those
together as a single hash value. Then the second pass in "fully
resolved" state will just take the final hashes of the referent DIEs
(pointer-hashes of their .identity () values) and combine those with the
hash saved in the first pass--this yields the hash of an "attrs_pair".
You do then need to visit each child DIE again to combine their final
hashes into the "brood hash", but since each child is fully resolved by
then, that is just a (reduce 'identity children) iteration on the vector
(std::accumulate(c.begin(),c.end(),0,identity_hash) or something).
Yeah, if you look at it as a fully two pass algorithm it might actually
work out pretty simple after all. It just takes "a bit" of extra storage
for all DIEs.
> And since some "tree resolved" DIEs might have the
same hash, but are
> not equal if you take the value references into account, you don't
> have perfect hashes for the attribute reference values. But they only
> collide when referring to the same structural trees with all basic
> attribute in all included DIEs matching completely.
That sounds nice, but the "structural tree" <singleton_tag/> with
"all
basic attributes" being the empty set is a common case.
Maybe I am missing the actual example you have in mind. Could you post
an example tree that shows it?
Thanks,
Mrk