rtti data structures (again)

[Nathan Sidwell]

Jason Merrill wrote:

>  >> We also decided that the flags should move from __class_type_info into
>  >> __vmi_class_type_info, and that the polymorphic flag should be removed.
> 
>  > I think this moving of the flags is a mistake. If I understood correctly,
>  > they indicated information about direct and indirect bases (whether there
>  > was virtuality anywhere in the heirarchy for instance). Such information
>  > can speed up dynamic cast. When walking the inheritance graph, we can
>  > take some early outs, if we know there are no multiple sub object types
>  > within the complete graph. With the flags in every class's type_info, it
>  > becomes easier to get hold of that info. With it only for vmi classes,
>  > we have to remember `unknown' when presented with a complete object of
>  > si type, and fill the information in when/if we find a vmi base.
> 
> So what you're saying is if we try to dynamic_cast from A* to B*, where B
> has a unique A subobject and the A* does not actually point to part of a B,
> if we know that B has no multiple subobjects we can check the passed
> offset, see that it doesn't match, and return failure.  Without that
> information, we would have to recurse up the single-inheritance chain until
> we either reach the A or a class with multiple or virtual bases.
No, the base_offset hint covers this case already. If A is a unique public
base of B base_offset will tell us where it is. If A is a non-unique public
base of B base_offset will tell us (and we search B to find one). If A is
not a public base, base_offset will tell us (and we don't search B).

What I'm talking about is that in a cast from A* to B*, if we know the
complete type has no multiple subobjects, then as soon as we find a B base
we can stop looking. We have to remember the flags from the complete object.
Should the flags only be in vmi type_info's then we also have to remember
that we don't know the subobject status when the complete object is an si.
We fill the flags in when/if we meet a vmi base. This is a minor problem
though, and is bookkeeping.

> I think I'd rather pay that small performance hit than add a word to the
> type_info for each class.  Matt, would this affect locales?
Yes, I suspect the performance hit is minor.

>  > Another case is in a potential cross-cast case, which I had in the
>  > previous email.  Suppose we've found the target base, which we know is
>  > unique, but not found the source base (because we early outed,
>  > maybe). To be a valid cross-cast both the source and target base objects
>  > must be public in the complete object. If we know the complete heirarchy
>  > has no non-public bases, there's no need to search for the source base
>  > in this case.
> 
> But cross-casts only come up in the context of classes with multiple bases,
> so it wouldn't make sense to look for this in single inheritance classes
> anyway.
Consider the following,

struct A {};
struct B {};
struct C : public A, public B {};
struct D : public C {};

consider cross cast from an A subobject to a B subobject. suppose we locate
the B subobject. We know C contains no multiple sub objects, 'cos of it's
vmi flags, therefore as soon as we find the target object we can stop searching.
This could mean we don't trip over the A subobject we started from. Hence
at the end of the search, when we're holding the D complete object we know
that B is an unambiguous public base of D, but we have no idea about A.
For the dynamic cast to be valid, either the A subobject must be a base
of the B target object (which it isn't), or the A subobject must be a public
base of the complete D object. Notice, it is insufficient for it to be a public
base of the common vmi object which contains both A and B. Thus, without the
flags in a single inheritance object, we have to go up the base chain till
we find a vmi object to discover whether any bases are private.

Actually it occurs to me that even this case can be dealt with during the
search for B. We find B and know we've not located the A we started from. So
we continue searching (or early succeed as we know there are no private bases,
at that point because of the vmi flags we've just seen). This is better.

I withdraw my objections about the flags only being in vmi classes.

nathan

-- 
Dr Nathan Sidwell :: sidwell at codesourcery.com
nathan at acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan at cs.bris.ac.uk