Wouldn't you also like to pass parts of the parent DIEs down?
Since we
consider context of a DIE relevant for deciding whether they are really
similar. You could add a "context hash" to each DIE based on the simple
(non-reference) attributes of the parent they are embedded in. That way
two DIEs in different context would normally not get the same hash, so
you don't need to compare them plus checking their contexts are the
same.
That indeed might be wise. But I don't think it's really the problem in
our way now. For the current state of affairs, I think we could just
ignore the context and deal purely with identical subtrees, and we'd still
have all the problems we have now.
If it makes it easier to work on it, I think we could well just disable the
context checking bit now and try to improve the "pure" subtree matching.
That alone with the reference graph issues is where our correctness and
performance issues are stuck now.
Since you detect the cycle, could you use the smallest cycle size
instead of zero? Meaning, after X steps following this ref (in some
specific order), you find yourself again. That assumes that DIEs you
want to detect equal have the same circular reference structure.
I thought about something like that before. It certainly merits more
thought. But at the moment, it just makes my head hurt. I do know that
we have cases where things don't have exactly the same physical
structure, but they are equivalent, due to different amounts of sharing.
I thought I gave an example of that earlier. Yes, I did. See
https://fedorahosted.org/pipermail/elfutils-devel/2010-July/001480.html
Thanks,
Roland