[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|, which has the
following member.
\begin{description} \let\makelabel\code
\item[const struct sod_vtable *_vt] A pointer to a \emph{vtable}, which has
  the basic structure of a @|struct sod_vtable|, described below.
\end{description}

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[const SodClass *_class] A pointer to the instance's class object.
\item[size_t _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}

%%%--------------------------------------------------------------------------
\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{prog}
  struct SodObject__vt_obj \{ \\ \ind
    const SodClass *_class; \\
    size_t _base; \- \\
  \};
  \\[\bigskipamount]
  struct SodObject__ilayout \{ \\ \ind
    union \{ \\ \ind
      struct SodObject__ichain_obj \{ \\ \ind
        const struct SodObject__vt_obj *_vt; \- \\
      \}; \- \\
    \} obj; \- \\
  \};
\end{prog}

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.

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

\begin{prog}
  struct SodClass__vt_obj \{ \\ \ind
    const SodClass *_class; \\
    size_t _base; \- \\
  \};
  \\[\bigskipamount]
  struct SodObject__ilayout \{ \\ \ind
    union \{ \\ \ind
      struct SodClass__ichain_obj \{ \\ \ind
        const struct SodClass__vt_obj *_vt; \\
        struct SodClass__islots \{ \\ \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; \- \\
        \} cls; \- \\
      \}; \\
      SodObject obj; \- \\
    \} obj; \- \\
  \};
\end{prog}

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[const char *name] A pointer to the class's name.

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

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

\item[void *(*imprint)(void *@<p>)] 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[void *(*init)(void *@<p>)] 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[size_t n_supers] The number of direct superclasses.  (This is zero
  exactly in the case of @|SodObject|.)

\item[const SodClass *const *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[size_t n_cpl] The number of superclasses in the class's class
  precedence list.

\item[const SodClass *const *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[const SodClass *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[const SodClass *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[size_t 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[size_t n_chains]
The number of chains formed by the class's superclasses.

\item[const struct sod_chain *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[size_t 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[size_t 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}

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

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

\item[const SodClass *const *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[size_t off_ichain] The size of the @|ichain| structure for this chain.

\item[const struct sod_vtable *vt] The vtable for this chain.  (It is
  possible, therefore, to duplicate the behaviour of the @<imprint> function
  by walking the chain structure.  The @<imprint> function is much faster,
  though.)

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

\end{description}

%%%--------------------------------------------------------------------------
\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.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: