problems with empty base layout algorithm

[Jim Dehnert]

> Date: Wed, 8 Sep 1999 16:51:02 -0400
> Reply-To: allen.chan at ca.ibm.com
> 
> Looking at the non-virtual-base allocation procedure as outlined in the Data
> Layout document, I noticed a couple of problems with the empty base layout
> algorithm.
> 
> Consider the following scenario:
> 
> struct A {};
> struct B : public A {};
> struct C : public A {};
> struct D : public A {};
> struct E { int e; }
> struct F : public B, public C, public D, public E { };
> 
> For the most derived class F, base classes B, C and D are empty bases. To map
> class F, we firsts have to allocate all base classes of F in declaration order.
> If we were to follow the described procedure, this is what we will get:
> 
> 1. The empty base B will be allocated at offset zero.
> 2. The empty base C (which has a type conflict with B, since they have the same
> non-virtual base A), will be allocated at dsize(F), which is zero.

This isn't the intent (nor what's written, though perhaps not
clearly).  We attempt offset zero, which doesn't work because of the
type conflict with B.  Then we "proceed with attempts at dsize(C) as
for non-empty bases."  Such attempts, "[if] a component type conflict
occurs, increment the candidate offset by align(type(D)), and try again,
repeating until success occurs..."

So, when dsize(C) doesn't work (it's zero, and it still doesn't work),
we try dsize(C)+1, dsize(C)+2, ..., until one of them does work.
No subobject is placed without first verifying absence of type
conflicts.

> 3. The empty base D (which has a type conflict with B and C), will be allocated
> at dsize(F), which is zero.
> 4. The base E will be allocated at dsize(F), which is zero.
> 5. sizeof(F) = 4.
> 
> So, even though B, C and D conflict with each other, they are all allocated at
> offset zero.
> 
> To solve the problems, I am proposing the following changes to the
> algorithm for lying out empty bases:
> 
> 1. Maintain an index, ebase(C), which denotes the current offset for
> allocation of empty bases. In the beginning, ebase(C) = 0.
> 2. For each empty base class D in C,
>      2a. If D and all its non-virtual base classes have not been allocated
> before, place D at offset zero.
>      2b. If D or any of its non-virtual base classes have been allocated before,
> place D at ebase(C) + 1. Update ebase(C) = ebase(C) + 1.

There's no reason to update ebase(C) unless the _next_ empty base
conflicts in type.  In addition, updating it doesn't guarantee that the
next empty base class won't conflict, since it (or a subclass) may
conflict with some part of an earlier-allocated base class.

> 3. After all components (virtual and non-virtual components) of C have been laid
> out, update sizeof(C) to max(sizeof(C), ebase(C)).

-	    Jim Dehnert		dehnert at sgi.com
				(650)933-4272