[sod] / doc / structures.tex

%%% -*-latex-*-
%%%
%%% In-depth exploration of the generated structures
%%%
%%% (c) 2015 Straylight/Edgeware
%%%

%%%----- Licensing notice ---------------------------------------------------
%%%
%%% This file is part of the Simple Object Definition system.
%%%
%%% SOD is free software; you can redistribute it and/or modify
%%% it under the terms of the GNU General Public License as published by
%%% the Free Software Foundation; either version 2 of the License, or
%%% (at your option) any later version.
%%%
%%% SOD is distributed in the hope that it will be useful,
%%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%%% GNU General Public License for more details.
%%%
%%% You should have received a copy of the GNU General Public License
%%% along with SOD; if not, write to the Free Software Foundation,
%%% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

\chapter{Object structures} \label{ch:structures}

This chapter describes the structure and layout of standard Sod objects,
classes and associated metadata.  Note that Sod's object system is very
flexible and it's possible for an extension to define a new root class which
works very differently from the standard @|SodObject| described here.

The concrete types described in \xref{sec:structures.common} and
\ref{sec:structures.root} are declared by the header file @|<sod/sod.h>|.
The definitions described in sections \ref{sec:structures.layout} are defined
in the header file generated by the containing module.

%%%--------------------------------------------------------------------------
\section{Common instance structure} \label{sec:structures.common}

As described below, a pointer to an instance actually points to an
\emph{instance chain} structure within the instances overall layout
structure.

Instance chains contain slots and vtable pointers, as described below.  All
instances have the basic structure of a @|struct sod_instance|.

\begin{describe}[struct sod_instance]{type}
    {struct sod_instance \{ \\ \ind
       const struct sod_vtable *_vt; \- \\
     \};}

  The basic structure of all instances.  Members are as follows.
  \begin{description} \let\makelabel\code
  \item[_vt] A pointer to a \emph{vtable}, which has the basic structure of a
    @|struct sod_vtable|, described below.
  \end{description}
\end{describe}

\begin{describe}[struct sod_vtable]{type}
    {struct sod_vtable \{ \\ \ind
       const SodClass *_class; \\
       size_t _base; \- \\
     \};}

  A vtable contains static metadata needed for efficient conversions and
  message dispatch, and pointers to the instance's class.  Each chain points
  to a different vtable.  All vtables have the basic structure of a @|struct
  sod_vtable|, which has the following members.
  \begin{description} \let\makelabel\code
  \item[_class] A pointer to the instance's class object.
  \item[_base] The offset of this chain structure above the start of the
    overall instance layout, in bytes.  Subtracting @|_base| from the
    instance chain pointer finds the layout base address.
  \end{description}
\end{describe}

%%%--------------------------------------------------------------------------
\section{Built-in root objects} \label{sec:structures.root}

This section describes the built-in classes @|SodObject| and @|SodClass|,
which are the standard roots of the inheritance and metaclass graphs
respectively.  Specifically, @|SodObject| has no direct superclasses, and
@|SodClass| is its own metaclass.  It is not possible to define root classes
in module files because of circularities: @|SodObject| has @|SodClass| as its
metaclass, and @|SodClass| is a subclass of @|SodObject|.  Extensions can
define additional root classes, but this is tricky, and not really to be
recommended.


\subsection{The SodObject class} \label{sec:structures.root.sodobject}

\begin{figure}[tbp]
  \begin{tabular}{p{10pt}p{10pt}}
    \begin{prog}
      struct SodObject__ilayout \{ \\ \ind
        union \{ \\ \ind
          struct SodObject__ichain_obj \{ \\ \ind
            const struct SodObject__vt_obj *_vt; \- \\
          \} obj; \- \\
        \} obj; \- \\
      \};
    \end{prog}
    &
    \begin{prog}
      struct SodObject__vt_obj \{ \\ \ind
        const SodClass *_class; \\
        size_t _base; \- \\
      \};
    \end{prog} \\
  \end{tabular}
  \caption{Instance and vtable layout of @|SodObject|}
  \label{fig:structures.root.sodobject}
\end{figure}

\begin{describe}[SodObject]{cls}
    {[nick = obj, metaclass = SodClass, lisp_metaclass = sod_class] \\
     class SodObject \{ \}}

  The @|SodObject| class defines no slots or messages.  Because @|SodObject|
  has no direct superclasses, there is only one chain, and no inherited
  slots or messages, so the single chain contains only a vtable pointer.

  Since there are no messages, and @|SodClass| also has only one chain, the
  vtable contains only the standard class pointer and offset-to-base members.
  In a direct instance of @|SodObject| (why would you want one?)  the class
  pointer contains the address of @|SodObject__class| and the offset is zero.

  The instance and vtable layout of @|SodObject| is shown in
  \xref{fig:structures.root.sodobject}.
\end{describe}


\subsection{The SodClass class} \label{sec:structures.root.sodclass}

\begin{describe}[SodClass]{cls}
    {[nick = cls, link = SodObject] \\
     class SodClass : SodObject \{ \\ \ind
       const char *name; \\
       const char *nick; \\
       size_t initsz; \\
       void *(*imprint)(void *@<p>); \\
       void *(*init)(void *@<p>); \\
       size_t n_supers; \\
       const SodClass *const *supers; \\
       size_t n_cpl; \\
       const SodClass *const *cpl; \\
       const SodClass *link; \\
       const SodClass *head; \\
       size_t level; \\
       size_t n_chains; \\
       const struct sod_chain *chains; \\
       size_t off_islots; \\
       size_t islotsz; \- \\
     \}}

  The @|SodClass| class defines no messages, but there are a number of slots.
  Its only direct superclass is @|SodObject| and so (like its superclass) its
  vtable is trivial.

  The slots defined are as follows.
  \begin{description} \let\makelabel\code

  \item[name] A pointer to the class's name.

  \item[nick] A pointer to the class's nickname.

  \item[initsz] The size in bytes required to store an instance of the class.

  \item[imprint] A pointer to a function: given a pointer @<p> to at least
    @<initsz> bytes of appropriately aligned memory, `imprint' this memory it
    so that it becomes a minimally functional instance of the class: all of
    the vtable and class pointers are properly initialized, but the slots are
    left untouched.  The function returns its argument @<p>.

  \item[init] A pointer to a function: given a pointer @<p> to at least
    @<initsz> bytes of appropriately aligned memory, initialize an instance
    of the class in it: all of the vtable and class pointers are initialized,
    as are slots for which initializers are defined.  Other slots are left
    untouched.  The function returns its argument @<p>.

  \item[n_supers] The number of direct superclasses.  (This is zero exactly
    in the case of @|SodObject|.)

  \item[supers] A pointer to an array of @<n_supers> pointers to class
    objects listing the class's direct superclasses, in the order in which
    they were listed in the class definition.  If @<n_supers> is zero, then
    this pointer is null.

  \item[n_cpl] The number of superclasses in the class's class precedence
    list.

  \item[cpl] A pointer to an array of pointers to class objects listing all
    of the class's superclasses, from most- to least-specific, starting with
    the class itself, so $c@->@|cls|.@|cpl|[0] = c$ for all class objects
    $c$.

  \item[link] If the class is a chain head, then this is a null pointer;
    otherwise it points to the class's distinguished link superclass (which
    might or might not be a direct superclass).

  \item[head] A pointer to the least-specific class in this class's chain; so
    $c@->@|cls|.@|head|@->@|cls|.@|link|$ is always null, and either
    $c@->@|cls|.@|link|$ is null (in which case $c@->@|cls|.@|head| = c$) or
    $c@->@|cls|.@|head| = c@->@|cls|.@|link|@->@|cls|.@|head|$.

  \item[level] The number of less specific superclasses in this class's
    chain.  If $c@->@|cls|.@|link|$ is null then $c@->@|cls|.@|level|$ is
    zero; otherwise $c@->@|cls|.@|level| =
    c@->@|cls|.@|link|@->@|cls|.@|level| + 1$.

  \item[n_chains] The number of chains formed by the class's superclasses.

  \item[chains] A pointer to an array of @|struct sod_chain| structures (see
    below) describing the class's superclass chains, in decreasing order of
    specificity of their most specific classes.  It is always the case that
    $c@->@|cls|.@|chains|[0].@|classes|[c@->@|cls|.@|level|] = c$.

  \item[off_islots] The offset of the class's @|islots| structure relative to
    its containing @|ichain| structure.  The class doesn't define any slots
    if and only if this is zero.  (The offset can't be zero because the
    vtable pointer is at offset zero.)

  \item[islotsz] The size required to store the class's direct slots, i.e.,
    the size of its @|islots| structure.  The class doesn't define any slots
    if and only if this is zero.

  \end{description}
\end{describe}

\begin{describe}[struct sod_chain]{type}
    {struct sod_chain \{ \\ \ind
       size_t n_classes; \\
       const SodClass *const *classes; \\
       size_t off_ichain; \\
       const struct sod_vtable *vt; \\
       size_t ichainsz; \- \\
     \};}

  The @|struct sod_chain| structure describes an individual chain of
  superclasses.  It has the following members.
  \begin{description} \let\makelabel\code

  \item[n_classes] The number of classes in the chain.  This is always at
    least one.

  \item[classes] A pointer to an array of class pointers listing the classes
    in the chain from least- to most-specific.  So
    $@<classes>[i]@->@|cls|.@|head| = @<classes>[0]$ for all $0 \le i <
    @<n_classes>$, $@<classes>[0]@->@|cls|.@|link|$ is always null, and
    $@<classes>[i]@->@|cls|.@|link| = @<classes>[i - 1]$ if $1 \le i <
    @<n_classes>$.

  \item[off_ichain] The size of the @|ichain| structure for this chain.

  \item[vt] The vtable for this chain.  (It is possible, therefore, to
    partially duplicate the behaviour of the @<imprint> function by walking
    the chain structure.\footnote{%
      There isn't enough information readily available to fill in the class
      pointers correctly.} %
    The @<imprint> function is much faster, though.)

  \item[ichainsz] The size of the @|ichain| structure for this chain.

  \end{description}
\end{describe}

%%%--------------------------------------------------------------------------
\section{Class and vtable layout} \label{sec:structures.layout}

The layout algorithms for Sod instances and vtables are nontrivial.  They are
defined here in full detail, since they're effectively fixed by Sod's ABI
compatibility guarantees, so they might as well be documented for the sake of
interoperating programs.

Unfortunately, the descriptions are rather complicated, and, for the most
part not necessary to a working understanding of Sod.  The skeleton structure
definitions shown should be more than enough for readers attempting to make
sense of the generated headers and tables.

In the description that follows, uppercase letters vary over class names,
while the corresponding lowercase letters indicate the class nicknames.
Throughout, we consider a class $C$ (therefore with nickname $c$).


\subsection{Generic instance structure}
\label{sec:structures.layout.instance}

The entire state of an instance of $C$ is contained in a single structure of
type @|struct $C$__ilayout|.

\begin{prog}
  struct $C$__ilayout \{ \\ \ind
    union $C$__ichainu_$h$ \{ \\ \ind
      struct $C$__ichain_$h$ \{ \\ \ind
        const struct $C$__vt_$h$ *_vt; \\
        struct $H$__islots $h$; \\
        \quad$\vdots$ \\
        struct $C$__islots \{ \\ \ind
          @<type>_1 @<slot>_1; \\
          \quad$\vdots$ \\
          @<type>_n @<slot>_n; \- \\
        \} $c$; \- \\
      \} $c$; \\
      struct $H$__ichain_$h$ $h$; \\
      \quad$\vdots$ \- \\
    \} $h$; \\
    union $B$__ichainu_$i$ $i$; \\
    \quad$\vdots$ \- \\
  \};
  \\[\bigskipamount]
  typedef struct $C$__ichain_$h$ $C$;
\end{prog}

The set of superclasses of $C$, including itself, can be partitioned into
chains by following their distinguished superclass links.  (Formally, the
chains are the equivalence classes determined by the reflexive, symmetric,
transitive closure of the `links to' relation.)  Chains are identified by
naming their least specific classes; the least specific class in a chain is
called the \emph{chain head}.  Suppose that the chain head of the chain
containing $C$ itself is named $H$ (though keep in mind that it's possible
that .$H$ is in fact $C$ itself.)

\subsubsection{The ilayout structure}
The @|ilayout| structure contains one member for each of $C$'s superclass
chains.  The first such member is
\begin{prog}
  union $C$__ichainu_$h$ $h$;
\end{prog}
described below; this is followed by members
\begin{prog}
  union $B$__ichainu_$i$ $i$;
\end{prog}
for each other chain, where $I$ is the head and $B$ the tail (most-specific)
class of the chain.  The members are in decreasing order of the specificity
of the chains' most-specific classes.  (Note that all but the first of these
unions has already been defined as part of the definition of the
corresponding $B$.)

\subsubsection{The ichainu union}
The @|ichainu| union contains a member for each class in the chain.  The
first is
\begin{prog}
  struct $C$__ichain_$h$ $c$;
\end{prog}
and this is followed by corresponding members
\begin{prog}
  struct $A$__ichain_$h$ $a$;
\end{prog}
for each of $C$'s superclasses $A$ in the same chain in some (unimportant)
order.

\subsubsection{The ichain structure}
The
@|ichain|
structure contains (in order), a pointer
\begin{prog}
  const struct $C$__vt_$h$ *_vt;
\end{prog}
followed by a structure
\begin{prog}
  struct $A$__islots $a$;
\end{prog}
for each superclass $A$ of $C$ in the same chain which defines slots, from
least- to most-specific; if $C$ defines any slots, then the last member is
\begin{prog}
  struct $C$__islots $c$;
\end{prog}
A `pointer to $C$' is always assumed (and, indeed, defined in C's
type system) to be a pointer to the @|struct $C$__ichain_$h$|.

\subsubsection{The islots structure}
Finally, the @|islots| structure simply contains one member for each slot
defined by $C$ in the order they appear in the class definition.


\subsection{Generic vtable structure} \label{sec:structures.layout.vtable}

As described above, each @|ichain| structure of an instance's storage has a
vtable pointer
\begin{prog}
  const struct $C$__vt_$h$ *_vt;
\end{prog}
In general, the vtables for the different chains will have \emph{different}
structures.

The instance layout split neatly into disjoint chains.  This is necessary
because each @|ichain| must have as a prefix the @|ichain| for each
superclass in the same chain, and each slot must be stored in exactly one
place.  The layout of vtables doesn't have this second requirement: it
doesn't matter that there are multiple method entry pointers for the same
effective method as long as they all work correctly.  Indeed, it's essential
that they do, because each chain's method entry function will need to apply a
different offset to the receiver pointer before invoking the effective
method.

A vtable for a class $C$ with chain head $H$ has the following general
structure.
\begin{prog}
  union $C$__vtu_$h$ \{ \\ \ind
    struct $C$__vt_$h$ \{ \\ \ind
      const $P$ *_class; \\
      size_t _base; \\
      \quad$\vdots$ \\
      const $Q$ *_cls_$j$; \\
      \quad$\vdots$ \\
      ptrdiff_t _off_$i$; \\
      \quad$\vdots$ \\
      struct $C$__vtmsgs_$a$ \{ \\ \ind
        @<type> (*@<msg>)($C$ *, $\dots$); \\
        \quad$\vdots$ \- \\
      \} $a$; \\
      \quad$\vdots$ \- \\
    \} $c$; \- \\
  \};
  \\[\bigskipamount]
  extern const union $C$__vtu_$h$ $C$__vtable_$h$;
\end{prog}

\subsubsection{The vtu union}
The outer layer is a @|union $C$__vtu_$h$| containing a member
\begin{prog}
  struct $A$__vt_$h$ $a$;
\end{prog}
for each of $C$'s superclasses $A$ in the same chain, with $C$ itself listed
first.

This is mostly an irrelevant detail,
whose purpose is to defend against malicious compilers:
pointers are always to one of the inner
@|vt|
structures.
It's important only because it's the outer
@|vtu|
union which is exported by name.
Specifically, for each chain of
$C$'s
superclasses
there is an external object
\begin{prog}
  const union $A$__vtu_$i$ $C$__vtable_$i$;
\end{prog}
where $A$ and $I$ are respectively the most and least specific classes in the
chain.

\subsubsection{The vt structure}
The first member in the @|vt| structure is the \emph{root class pointer}
\begin{prog}
  const $P$ *_class;
\end{prog}
Among the superclasses of $C$ there must be exactly one class $O$ which
itself has no direct superclasses; this is the \emph{root superclass} of $C$.
(This is a rule enforced by the Sod translator.)  The metaclass $R$ of $O$ is
then the \emph{root metaclass} of $C$.  The @|_class| member points to the
@|ichain| structure of most specific superclass $P$ of $M$ in the same chain
as $R$.

This is followed by the \emph{base offset}
\begin{prog}
  size_t _base;
\end{prog}
which is simply the offset of the @|ichain| structure from the instance base.

The rest of the vtable structure is populated by walking the superclass chain
containing $C$ as follows.  For each such superclass $B$, in increasing order
of specificity, walk the class precedence list of $B$, again starting with
its least-specific superclass.  (This complex procedure guarantees that the
vtable structure for a class is a prefix of the vtable structure for any of
its subclasses in the same chain.)

So, let $A$ be some superclass of $C$ which has been encountered during this
traversal.

\begin{itemize}

\item Let $N$ be the metaclass of $A$.  Examine the superclass chains of $N$
  in order of decreasing specificity of their most-specific classes.  Let $J$
  be the chain head of such a chain, and let $Q$ be the most specific
  superclass of $M$ in the same chain as $J$.  Then, if there is currently no
  class pointer of type $Q$, then add a member
  \begin{prog}
    const $Q$ *_cls_$j$;
  \end{prog}
  to the vtable pointing to the appropriate @|islots| structure within $M$'s
  class object.

\item Examine the superclass chains of $A$ in order of decreasing specificity
  of their most-specific classes.  Let $I$ be the chain head of such a chain.
  If there is currently no member @|_off_$i$| then add a member
  \begin{prog}
    ptrdiff_t _off_$i$;
  \end{prog}
  to the vtable, containing the (signed) offset from the @|ichain| structure
  of the chain headed by $h$ to that of the chain headed by $i$ within the
  instance's layout.

\item If class $A$ defines any messages, and there is currently no member
  $a$, then add a member
  \begin{prog}
    struct $C$__vtmsgs_$a$ $a$;
  \end{prog}
  to the vtable.  See below.

\end{itemize}

\subsubsection{The vtmsgs structure}
Finally, the @|vtmsgs| structures contain pointers to the effective method
entry functions for the messages defined by a superclass.  There may be more
than one method entry for a message, but all of the entry pointers for a
message appear together, and entry pointers for separate messages appear in
the order in which the messages are defined.  If the receiver class has no
applicable primary method for a message then it's usual for the method entry
pointer to be null (though, as with a lot of things in Sod, extensions may do
something different).

For a standard message which takes a fixed number of arguments, defined as
\begin{prog}
  @<type>_0 $m$(@<type>_1 @<arg>_1, $\ldots$, @<type>_n @<arg>_n);
\end{prog}
there is always a `main' entry point,
\begin{prog}
  @<type>_0 $m$($C$ *me, @<type>_1 @<arg>_1, $\ldots$, @<type>_n @<arg>_n);
\end{prog}

For a standard message which takes a variable number of arguments,
defined as
\begin{prog}
  @<type>_0 $m$(@<type>_1 @<arg>_1, $\ldots$, @<type>_n @<arg>_n, \dots);
\end{prog}
two entry points are defined: the usual `main' entry point which accepts a
variable number of arguments, and a `valist' entry point which accepts an
argument of type @|va_list| in place of the variable portion of the argument
list.
\begin{prog}
  @<type>_0 $m$($C$ *me, @<type>_1 @<arg>_1, $\ldots$,
                @<type>_n @<arg>_n, \dots); \\
  @<type>_0 $m$__v($C$ *me, @<type>_1 @<arg>_1, $\ldots$,
                   @<type>_n @<arg>_n, va_list sod__ap);
\end{prog}


\subsection{Additional definitions} \label{sec:structures.layout.additional}

In addition to the instance and vtable structures described above, the
following definitions are made for each class $C$.

For each message $m$ directly defined by $C$ there is a macro definition
\begin{prog}
  \#define $C$_$m$(@<me>, $\ldots$) @<me>@->_vt@->$c$.$m$(@<me>, $\ldots$)
\end{prog}
which makes sending the message $m$ to an instance of (any subclass of) $C$
somewhat less ugly.

If $m$ takes a variable number of arguments, the macro is more complicated
and is only available in compilers advertising C99 support, but the effect is
the same.  For each variable-argument message, there is also an additional
macro for calling the `valist' entry point.
\begin{prog}
  \#define $C$_$m$__v(@<me>, $\ldots$, @<sod__ap>)
    @<me>@->_vt@->$c$.$m$__v(@<me>, $\ldots$, @<sod__ap>)
\end{prog}

For each proper superclass $A$ of $C$, there is a macro defined
\begin{prog}
  $A$ *$C$__CONV_$a$($C$ *_obj);
\end{prog}
(named in \emph{upper case}) which converts a (static-type) pointer to $C$ to
a pointer to the same actual instance, but statically typed as a pointer to
$A$.  This is most useful when $A$ is not in the same chain as $C$ since
in-chain upcasts are both trivial and rarely needed, but the full set is
defined for the sake of completeness.

Finally, the class object is defined as
\begin{prog}
  extern const struct $R$__ilayout $C$__classobj; \\
  \#define $C$__class (\&$C$__classobj.$j$.$r$)
\end{prog}
The exported symbol @|$C$__classobj| contains the entire class instance.
This is usually rather unwieldy.  The macro @|$C$__class| is usable as a
pointer of type @|const $R$~*|, where $R$ is the root metaclass of $C$, i.e.,
the metaclass of the least specific superclass of $C$; usually this is
@|const SodClass~*|.

%%%----- That's all, folks --------------------------------------------------

%%% Local variables:
%%% mode: LaTeX
%%% TeX-master: "sod.tex"
%%% TeX-PDF-mode: t
%%% End: