The complete rule for type header layout is shown in
Rule 1. Rule 1 looks like the simple type rule
of Figure 7, except that
it attempts to merge the supertype headers using the function *merge*,
defined by the rules in Figure 10.
Like the rule of Figure 7, Rule 1
makes *T*_{1}
the primary supertype by aligning its header with that of *T*.

**Rule 1:** Type header layout

When a type has no supertypes, the result of the merge is considered to
be empty, so the dispatch header for such a type contains just a single
dispatch vector with the methods of *T*, starting from index 0. With this
interpretation, Rule 1 covers all cases for type header construction.

The function *merge* takes a list of types and
produces a layout that merges the headers of all the types. There
are three cases that the function considers, described in
the rules M1, M2, and M3 of Figure 10.

Rule M1 states the obvious base case: merging a single type header yields the type header itself.

Rule M2 actually performs a merge. The antecedent to M2 captures exactly the merge cases described in Figure 9, stating that

<_{H} *merge*(*T*
_{1},...,*T*_{n-1})

If *x* is non-empty, Rule M2 requires that there be no branches along
the path from *T*_{n} to *S*,
matching the antecedent to
merge case 1. If *x*
is empty, Rule M2 requires only that *S*
be a primary supertype of
*T*_{n},
matching the antecedent to merge case 2. The merge result
from Rule M2 similarly matches the results of the two merge cases.
In case 1, using Rule M2 to merge in *T*_{n}
does not increase the
size of the type header. In case 2, the size of the type header increases,
but only by the size difference of
and .

If rules M1 and M2 fail, Rule M3 must be used: as in Figure 7,
append at the start of the previous merge. This rule
increases the size of the type header by the height of
,
so Rule M2 is always preferable when it can be applied.
The rules for *merge* are complete, because M3 can always
be applied in the case when M2 cannot.

For the merge rules to be correct, type headers in a primary supertype chain must be aligned with each other. This alignment is guaranteed because rules M2 and M3 keep the result of the previous merge aligned with the last word of the result merge.

Also, embedded type headers must be located at a known offset from
the end of the type header so that supertype conversion works properly;
Rule M1 clearly preserves this property. Rule M3 keeps all embedded type
headers in *y* at the same offset, and all embedded type headers in
*T*_{n}
are offset by the height of *y*, which is a known constant. Therefore,
M3 preserves the property. Rule M2 is more complex.
Clearly, M2 keeps any embedded headers in and *y* at the same offset.
Now, consider the embedded information in *x*.
Rule M2 can satisfy
either of the merge cases of Figure 9.
If it satisfies
case 1, then has the same height as
,
so the dispatch information in *x* is
located at the same offset in the resulting merge. If Rule M2 satisfies
case 2, then may be larger than ,
but *x* is empty. Inductively, the known-offset property is preserved by
the combination of Rule 1 and the merge rules.

The order in which the supertypes are merged is important, because it
may determine whether Rule M2 can be applied. The indices on the
supertypes in Rule 1 can be assigned in an order that allows as much
merging as possible. The current Theta implementation does not attempt
to find an optimal ordering, since the number of supertypes is usually
small. It successively picks supertypes and places them in an ordered
list for *merge* using the following heuristic.
At each iteration, it preferentially picks a supertype whose header
can be merged into the minimal number of unpicked supertype headers.
Thus, it avoids adding a header until it has added any headers that
it can be merged into.
Usually, there is a supertype that cannot be merged into any other
supertype headers. It breaks ties by picking a supertype that
can be merged by Rule M2 into the layout of the currently picked supertypes.
The picked supertype is appended to the end of the ordered
list, and the process repeats.

Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
*Proceedings of OOPSLA '95*, pp. 124-139.

Copyright © 1995 Association for Computing Machinery