User control of the CPL

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

  Should we adopt the :component-order class-option from Flavors, as a
  simple way for the user to have control of the CPL without making him
  write his own algorithm?
  
    Gregor doesn't like the ability to specify constraints on the
  ordering of classes that only apply conditionally, i.e. if those
  classes are actually present among the superclasses.  He considers
  this bad style.   Moon volunteered to write a proposal with some
  examples, and we agreed to resolve this over the mail.

PROPOSAL:

The :precedence option to defclass is written (:precedence C1 C2 C3 ...)
where the C's are class names.  This specifies that C1 must precede C2
in the CPL, C2 must precede C3, etc.  This defclass option may appear
any number of times.

The default if no :precedence option is specified for a class C with
direct superclasses C1, C2, ..., Cn is (:precedence C C1 C2 ... Cn).  To
completely eliminate all precedence constraints, specify (:precedence C).

In the notation used on page 1-14 of 87-002, the :precedence option
allows direct control over Rc.  Each ordered pair (C1,C2) in Rc is
specified by writing (:precedence C1 C2).  :precedence with more than
two class names is simply a convenient abbreviation for multiple
:precedence options.

OPTIONS:

Optionally we could add an additional requirement that each Ci in a
:precedence option in the defclass for C must be either C or one of C's
direct superclasses.  I am opposed to this, for reasons which should
become clear from the examples.  It doesn't hurt to have extra ordered
pairs in Rc that do not affect the CPL.  Another way of saying this is
that the :precedence option is useful both for relaxing the precedence
constraints, compared with the default, and for adding additional
constraints to the default constraints.

Optionally we could add an additional stipulation that regardless of the
use of :precedence options, a class always precedes its direct
superclasses.  Specifically, in (defclass C (C1 C2 C3) () ...), the
effect of (:precedence C C1), (:precedence C C2), and (:precedence C C3)
is always present; in addition, if the user does not specify a
:precedence option, defclass supplies (:precedence C1 C2 C3).  This
would slightly simplify the following section, but it seems like a
kludgey restriction on how much control over the precedence relations
the user is permitted.  I have found applications that would not work
with this restriction, so I oppose adding this restriction.

Optionally we could add a restriction that a :precedence option in the
defclass for C may not specify that another class precedes C.  Flavors
has such a restriction, however I believe it to be unnecessary and I
oppose making this restriction in CLOS.

EFFECT ON CPL ALGORITHM:

The first and third paragraphs on page 1-15 of 87-002 would need to be
changed.  The statement "there can be only one such candidate class" is
no longer true once the user can relax the constraints using the
:precedence option.  A more complex disambiguation rule is necessarily
required.  I suggest replacing the first paragraph on 1-15 with:

  Sometimes there are several classes from Sc with no predecessors.  In
  this case, we select one of these candidate classes according to the
  following rule:  Traverse the superclasses of each member of the CPL
  found so far, associating the number (d*n*n)-(i*n)+b with the class at
  depth d and breadth b in the tree rooted at the ith element of the CPL
  found so far (make it a tree by considering only the first occurrence
  in breadth-first order of each class).  n is the number of classes
  involved (the initial length of Sc).  Choose the candidate with the
  smallest associated number, considering the minimum if several numbers
  are associated with one class.  This algorithm selects a unique
  candidate because no two associated numbers are equal.

  A class is always the first element of its own CPL.  Thus the CPL
  computed so far, used in the above rule, can never be empty.  This
  implies an additional check: when computing the CPL of C, if (C',C) is
  an element of R, signal an error reporting that it is invalid for C'
  to precede C.
 
The above rule is the simplest rule I could find that is compatible with
the 87-002 rule.  Other rules I considered were not compatible with the
87-002 rule and had additional undesirable properties.  Note that in all
cases when the :precedence option is not used this rule produces the
same answer as the one in 87-002, and produces it in essentially the
same way.  In this case d=1 for the winning candidate.

There are more efficient implementations than computing all the numbers
and then finding the minimum number, however that's the easiest way I could
find to explain it.  An actual implementation could traverse all the trees
in parallel, in a suitable order, and take the first candidate it encounters.

Note that the last sentence in the first paragraph on 1-15 is irrelevant
to the paragraph and repeats what was already said in the last paragraph
on 1-14, so I would simply remove it.

The third paragraph on 1-15 could be replaced with a more precise
specification of the rule quoted above, if desired.


EXAMPLES:

For brevity I have omitted from R all pairs involving the class t.

;Two superclasses and we don't care about their order
;CPL=(example2 example super-2 super-1 t) 
;R={(example-2,example),(example,super-1),(example,super-2),(super-2,super-1)}
(defclass example (super-1 super-2) ()
  (:precedence example super-1)
  (:precedence example super-2))
(defclass example-2 (example super-2 super-1) ())

;Two mixins that can be used separately but they interact and therefore
;if they are used together, they must be used in a certain order to work.
;Specifically, mixin-2 must be before mixin-1.
(defclass base-class () ())
(defclass use-1 (mixin-1 base-class) ())
(defclass use-2 (mixin-2 base-class) ())
(defclass use-both (mixin-1 mixin-2 base-class) ())
(defclass use-both-2 (use-1 use-2) ())
(defclass mixin-1 (base-class) ()
  (:precedence mixin-2 mixin-1 base-class))
(defclass mixin-2 (base-class) ()
  (:precedence mixin-2 mixin-1 base-class))
;use-1 and use-2 will not accidentally include the other mixin
;use-both will get an error for inconsistent precedence constraints
;use-both-2 will get a CPL of (use-both-2 use-1 use-2 mixin-2 mixin-1 base-class t)
;R={(use-both-2,use-1),(use-1,use-2),(use-1,mixin-1),(mixin-1,base-class),
;   (use-2,mixin-2),(mixin-2,base-class),(mixin-2,mixin-1)}

;"Gross example" that helped me shoot down various other rules for
;resolving topological sort ambiguities
;CPL is (a c b e d t)
;R is {(a,b),(b,d),(c,b),(e,d)}.
(defclass a (b d) ())
(defclass b (c) ()
  (:precedence b))
(defclass c () ()
  (:precedence c b))
(defclass d (e) ()
  (:precedence d))
(defclass e () ()
  (:precedence e d))

;Two examples taken from actual (ugh, bletch) window code:

;This one shows two mixins that have an ordering constraint among them,
;but are not always used together.  Rather than rely on any class that
;includes both to specify the constraint correctly, we specify it here.
;The user is adding more constraints to the default constraints.
(DEFCLASS DONT-SELECT-WITH-MOUSE-MIXIN (ESSENTIAL-WINDOW) ()
  ;; If TV:SELECT-MIXIN is present, we must
  ;; override its :NAME-FOR-SELECTION method
  (:PRECEDENCE TV:DONT-SELECT-WITH-MOUSE-MIXIN
	       TV:SELECT-MIXIN
	       TV:ESSENTIAL-WINDOW))

;This one shows a class that is just a bundle of useful mixins, but doesn't
;want to constrain the order of those mixins.
;The user is specifying fewer than the default constraints
(DEFCLASS WINDOW (STREAM-MIXIN BORDERS-MIXIN LABEL-MIXIN SELECT-MIXIN
		  GRAPHICS-MIXIN MINIMUM-WINDOW) ()
  ;; The mixins already come with almost all necessary constraints.
  ;; Relax the constraints that would normally be implied by the above list
  ;; of components, so that subclasses of WINDOW can rearrange things.
  ;; Put the label inside the border.
  (:PRECEDENCE BORDERS-MIXIN LABEL-MIXIN)
  ;; For esthetics, force WINDOW to precede MINIMUM-WINDOW
  (:PRECEDENCE WINDOW MINIMUM-WINDOW))