From 4075ab402e0f91f145f9ebf9cd325a8b869bc85d Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Sat, 27 Jul 2019 14:43:14 +0100
Subject: [PATCH] doc/concepts.tex: Add class-precedence-list examples, with
 diagrams.

---
 doc/concepts.tex | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 86 insertions(+)

diff --git a/doc/concepts.tex b/doc/concepts.tex
index 399b148..2e3bead 100644
--- a/doc/concepts.tex
+++ b/doc/concepts.tex
@@ -170,6 +170,92 @@ It works as follows.
   class whose subclass appears earliest in $C$'s local precedence order.
 \end{itemize}
 
+\begin{figure}
+  \centering
+  \begin{tikzpicture}[x=7.5mm, y=-14mm, baseline=(current bounding box.east)]
+    \node[lit] at ( 0,  0) (R) {SodObject};
+    \node[lit] at (-3, +1) (A) {A};     \draw[->] (A) -- (R);
+    \node[lit] at (-1, +1) (B) {B};     \draw[->] (B) -- (R);
+    \node[lit] at (+1, +1) (C) {C};     \draw[->] (C) -- (R);
+    \node[lit] at (+3, +1) (D) {D};     \draw[->] (D) -- (R);
+    \node[lit] at (-2, +2) (E) {E};     \draw[->] (E) -- (A);
+                                        \draw[->] (E) -- (B);
+    \node[lit] at (+2, +2) (F) {F};     \draw[->] (F) -- (A);
+                                        \draw[->] (F) -- (D);
+    \node[lit] at (-1, +3) (G) {G};     \draw[->] (G) -- (E);
+                                        \draw[->] (G) -- (C);
+    \node[lit] at (+1, +3) (H) {H};     \draw[->] (H) -- (F);
+    \node[lit] at ( 0, +4) (I) {I};     \draw[->] (I) -- (G);
+                                        \draw[->] (I) -- (H);
+  \end{tikzpicture}
+  \quad
+  \vrule
+  \quad
+  \begin{minipage}[c]{0.45\hsize}
+    \begin{nprog}
+      class A: SodObject \{ \}\quad\=@/* @|A|, @|SodObject| */  \\
+      class B: SodObject \{ \}\>@/* @|B|, @|SodObject| */       \\
+      class C: SodObject \{ \}\>@/* @|B|, @|SodObject| */       \\
+      class D: SodObject \{ \}\>@/* @|B|, @|SodObject| */       \\+
+      class E: A, B \{ \}\quad\=@/* @|E|, @|A|, @|B|, \dots */  \\
+      class F: A, D \{ \}\>@/* @|F|, @|A|, @|D|, \dots */       \\+
+      class G: E, C \{ \}\>@/* @|G|, @|E|, @|A|,
+                                @|B|, @|C|, \dots */            \\
+      class H: F \{ \}\>@/* @|H|, @|F|, @|A|, @|D|, \dots */    \\+
+      class I: G, H \{ \}\>@/* @|I|, @|G|, @|E|, @|H|, @|F|,
+                                @|A|, @|B|, @|C|, @|D|, \dots */
+    \end{nprog}
+  \end{minipage}
+
+  \caption{An example class graph and class precedence lists}
+  \label{fig:concepts.classes.cpl-example}
+\end{figure}
+
+\begin{example}
+  Consider the class relationships shown in
+  \xref{fig:concepts.classes.cpl-example}.
+
+  \begin{itemize}
+
+  \item @|SodObject| has no proper superclasses.  Its class precedence list
+    is therefore simply $\langle @|SodObject| \rangle$.
+
+  \item In general, if $X$ is a direct subclass only of $Y$, and $Y$'s class
+    precedence list is $\langle Y, \ldots \rangle$, then $X$'s class
+    precedence list is $\langle X, Y, \ldots \rangle$.  This explains $A$,
+    $B$, $C$, $D$, and $H$.
+
+  \item $E$'s list is found by merging its local precedence list $\langle E,
+    A, B \rangle$ with the class precedence lists of its direct superclasses,
+    which are $\langle A, @|SodObject| \rangle$ and $\langle B, @|SodObject|
+    \rangle$.  Clearly, @|SodObject| must be last, and $E$'s local precedence
+    list orders the rest, giving $\langle E, A, B, @|SodObject|, \rangle$.
+    $F$ is similar.
+
+  \item We determine $G$'s class precedence list by merging the three lists
+    $\langle G, E, C \rangle$, $\langle E, A, B, @|SodObject| \rangle$, and
+    $\langle C, @|SodObject| \rangle$.  The class precedence list begins
+    $\langle G, E, \ldots \rangle$, but the individual lists don't order $A$
+    and $C$.  Comparing these to $G$'s direct superclasses, we see that $A$
+    is a subclass of $E$, while $C$ is a subclass of -- indeed equal to --
+    $C$; so $A$ must precede $C$, as must $B$, and the final list is $\langle
+    G, E, A, B, C, @|SodObject| \rangle$.
+
+  \item Finally, we determine $I$'s class precedence list by merging $\langle
+    I, G, H \rangle$, $\langle G, E, A, B, C, @|SodObject| \rangle$, and
+    $\langle H, F, A, D, @|SodObject| \rangle$.  The list begins $\langle I,
+    G, \ldots \rangle$, and then we must break a tie between $E$ and $H$; but
+    $E$ is a subclass of $G$, so $E$ wins.  Next, $H$ and $F$ must precede
+    $A$, since these are ordered by $H$'s class precedence list.  Then $B$
+    and $C$ precede $D$, since the former are superclasses of $G$, and the
+    final list is $\langle I, G, E, H, F, A, B, C, D, @|SodObject| \rangle$.
+
+  \end{itemize}
+
+  (This example combines elements from \cite{Barrett:1996:MSL} and
+  \cite{Ducournau:1994:PMM}.)
+\end{example}
+
 \subsubsection{Class links and chains}
 The definition for a class $C$ may distinguish one of its proper superclasses
 as being the \emph{link superclass} for class $C$.  Not every class need have
-- 
2.11.0