4.3.5 Determining the Class Precedence List

The defclass form for a class provides a total ordering on that class and its direct superclasses. This ordering is called the local precedence order. It is an ordered list of the class and its direct superclasses. The class precedence list for a class C is a total ordering on C and its superclasses that is consistent with the local precedence orders for each of C and its superclasses.

A class precedes its direct superclasses, and a direct superclass precedes all other direct superclasses specified to its right in the superclasses list of the defclass form. For every class C, define

R_C={(C,C₁),(C₁,C₂),...,(C_n-1,C_n)}

Let S_C be the set of C and its superclasses. Let R be

R=⋃_{c∈ SC}R_c

The set R might or might not generate a partial ordering, depending on whether the R_c, c∈ S_C, are consistent; it is assumed that they are consistent and that R generates a partial ordering. When the R_c are not consistent, it is said that R is inconsistent.

To compute the class precedence list for C, topologically sort the elements of S_C with respect to the partial ordering generated by R. When the topological sort must select a class from a set of two or more classes, none of which are preceded by other classes with respect to R, the class selected is chosen deterministically, as described below.

If R is inconsistent, an error is signaled.

4.3.5.1 Topological Sorting

Topological sorting proceeds by finding a class C in S_C such that no other class precedes that element according to the elements in R. The class C is placed first in the result. Remove C from S_C, and remove all pairs of the form (C,D), D∈ S_C, from R. Repeat the process, adding classes with no predecessors to the end of the result. Stop when no element can be found that has no predecessor.

If S_C is not empty and the process has stopped, the set R is inconsistent. If every class in the finite set of classes is preceded by another, then R contains a loop. That is, there is a chain of classes C₁,...,C_n such that C_i precedes C_i+1, 1≤ i<n, and C_n precedes C₁.

Sometimes there are several classes from S_C with no predecessors. In this case select the one that has a direct subclass rightmost in the class precedence list computed so far. (If there is no such candidate class, R does not generate a partial ordering—the R_c, c∈ S_C, are inconsistent.)

In more precise terms, let {N₁,...,N_m}, m≥ 2, be the classes from S_C with no predecessors. Let (C₁... C_n), n≥ 1, be the class precedence list constructed so far. C₁ is the most specific class, and C_n is the least specific. Let 1≤ j≤ n be the largest number such that there exists an i where 1≤ i≤ m and N_i

is a direct superclass of C_j; N_i is placed next.

The effect of this rule for selecting from a set of classes with no predecessors is that the classes in a simple superclass chain are adjacent in the class precedence list and that classes in each relatively separated subgraph are adjacent in the class precedence list. For example, let T₁ and T₂ be subgraphs whose only element in common is the class J. Suppose that no superclass of J appears in either T₁ or T₂, and that J is in the superclass chain of every class in both T₁ and T₂. Let C₁ be the bottom of T₁; and let C₂ be the bottom of T₂. Suppose C is a class whose direct superclasses are C₁ and C₂ in that order, then the class precedence list for C starts with C and is followed by all classes in T₁ except J. All the classes of T₂ are next. The class J and its superclasses appear last.

4.3.5.2 Examples of Class Precedence List Determination

This example determines a class precedence list for the class pie. The following classes are defined:

 (defclass pie (apple cinnamon) ())

 (defclass apple (fruit) ())

 (defclass cinnamon (spice) ())

 (defclass fruit (food) ())

 (defclass spice (food) ())

 (defclass food () ())

The set S_pie = {pie, apple, cinnamon, fruit, spice, food, standard-object, t}. The set R = {(pie, apple), (apple, cinnamon), (apple, fruit), (cinnamon, spice), (fruit, food), (spice, food), (food, standard-object), (standard-object, t)}.

The class pie is not preceded by anything, so it comes first; the result so far is (pie). Remove pie from S and pairs mentioning pie from R to get S = {apple, cinnamon, fruit, spice, food, standard-object, t} and R = {(apple, cinnamon), (apple, fruit), (cinnamon, spice), (fruit, food), (spice, food), (food, standard-object), (standard-object, t)}.

The class apple is not preceded by anything, so it is next; the result is (pie apple). Removing apple and the relevant pairs results in S = {cinnamon, fruit, spice, food, standard-object, t} and R = {(cinnamon, spice), (fruit, food), (spice, food), (food, standard-object), (standard-object, t)}.

The classes cinnamon and fruit are not preceded by anything, so the one with a direct subclass rightmost in the class precedence list computed so far goes next. The class apple is a direct subclass of fruit, and the class pie is a direct subclass of cinnamon. Because apple appears to the right of pie in the class precedence list, fruit goes next, and the result so far is (pie apple fruit). S = {cinnamon, spice, food, standard-object, t}; R = {(cinnamon, spice), (spice, food), (food, standard-object), (standard-object, t)}.

The class cinnamon is next, giving the result so far as (pie apple fruit cinnamon). At this point S = {spice, food, standard-object, t}; R = {(spice, food), (food, standard-object), (standard-object, t)}.

The classes spice, food, standard-object, and t are added in that order, and the class precedence list is (pie apple fruit cinnamon spice food standard-object t).

It is possible to write a set of class definitions that cannot be ordered. For example:

 (defclass new-class (fruit apple) ())

 (defclass apple (fruit) ())

The class fruit must precede apple because the local ordering of superclasses must be preserved. The class apple must precede fruit because a class always precedes its own superclasses. When this situation occurs, an error is signaled, as happens here when the system tries to compute the class precedence list of new-class.

The following might appear to be a conflicting set of definitions:

 (defclass pie (apple cinnamon) ())

 (defclass pastry (cinnamon apple) ())

 (defclass apple () ())

 (defclass cinnamon () ())

The class precedence list for pie is (pie apple cinnamon standard-object t).

The class precedence list for pastry is (pastry cinnamon apple standard-object t).

It is not a problem for apple to precede cinnamon in the ordering of the superclasses of pie but not in the ordering for pastry. However, it is not possible to build a new class that has both pie and pastry as superclasses.