[sod] / lib / sod-structs.3

.\" -*-nroff-*-
.\"
.\" Description of the main Sod data structures
.\"
.\" (c) 2015 Straylight/Edgeware
.\"
.
.\"----- Licensing notice ---------------------------------------------------
.\"
.\" This file is part of the Sensible Object Design, an object system for C.
.\"
.\" 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.
.
.\" Highlight using terminal escapes, rather than overstriking.
.\"\X'tty: sgr 1'
.
.\" String definitions and font selection.
.ie t \{\
.  ds o \(bu
.  if \n(.g .fam P
.\}
.el \{\
.  ds o o
.\}
.
.\" .hP TEXT -- start an indented paragraph with TEXT hanging off to the left
.de hP
.IP
\h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
..
.
.\"--------------------------------------------------------------------------
.TH sod-structs 3 "8 September 2015" "Straylight/Edgeware" "Sensible Object Design"
.
.SH NAME
sod-structs \- main Sod data structures
.
.\"--------------------------------------------------------------------------
.SH SYNOPSIS
.nf
.ft B
#include <sod/sod.h>

typedef struct SodObject__ichain_obj SodObject;
typedef struct SodClass__ichain_obj SodClass;

struct sod_instance {
\h'2n'const struct sod_vtable *_vt;
};

struct sod_vtable {
\h'2n'const SodClass *_class;
\h'2n'size_t _base;
};

struct SodObject__vt_obj {
\h'2n'const SodClass *_class;
\h'2n'size_t _base;
};

struct SodObject__ilayout {
\h'2n'union {
\h'4n'struct SodObject__ichain_obj {
\h'6n'const struct SodObject__vt_obj *_vt;
\h'4n'};
\h'2n'} obj;
};

extern const struct SodClass__ilayout SodObject__classobj;
#define SodObject__class (&SodObject__classobj.obj.cls)

struct SodClass__vt_obj {
\h'2n'const SodClass *_class;
\h'2n'size_t _base;
};

struct SodObject__ilayout {
\h'2n'union {
\h'4n'struct SodClass__ichain_obj {
\h'6n'const struct SodClass__vt_obj *_vt;
\h'6n'struct SodClass__islots {
\h'8n'const char *name;
\h'8n'const char *nick;
\h'8n'size_t initsz;
\h'8n'void *(*imprint)(void *\fIp\fB);
\h'8n'void *(*init)(void *\fIp\fB);
\h'8n'size_t n_supers;
\h'8n'const SodClass *const *supers;
\h'8n'size_t n_cpl;
\h'8n'const SodClass *const *cpl;
\h'8n'const SodClass *link;
\h'8n'const SodClass *head;
\h'8n'size_t level;
\h'8n'size_t n_chains;
\h'8n'const struct sod_chain *chains;
\h'8n'size_t off_islots;
\h'8n'size_t islotsz;
\h'6n'} cls;
\h'4n'};
\h'4n'SodObject obj;
\h'2n'} obj;
};

struct sod_chain {
\h'2n'size_t n_classes;
\h'2n'const SodClass *const *classes;
\h'2n'size_t off_ichain;
\h'2n'const struct sod_vtable *vt;
\h'2n'size_t ichainsz;
};

extern const struct SodClass__ilayout SodClass__classobj;
#define SodClass__class (&SodClass__classobj.obj.cls)
.fi
.ft P
.
.\"--------------------------------------------------------------------------
.SH DESCRIPTION
.
This page 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
.B SodObject
described here.
.
.\"--------------------------------------------------------------------------
.SH COMMON INSTANCE STRUCTURE
.
As described below,
a pointer to an instance actually points to an
.I "instance chain"
structure within the instances overall layout structure.
.PP
Instance chains contain slots and vtable pointers,
as described below.
All instances have the basic structure of a
.BR "struct sod_instance" ,
which has the following members.
.TP
.B "const struct sod_vtable *_vt"
A pointer to a
.IR vtable ,
which has the basic structure of a
.BR "struct sod_vtable" ,
described below.
.PP
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
.BR "struct sod_vtable" ,
which has the following members.
.TP
.B "const SodClass *_class"
A pointer to the instance's class object.
.TP
.B "size_t _base;"
The offset of this chain structure
above the start of the overall instance layout, in bytes.
Subtracting
.B _base
from the instance chain pointer
finds the layout base address.
.
.\"--------------------------------------------------------------------------
.SH BUILT-IN ROOT OBJECTS
.
This section describes the built-in classes
.B SodObject
and
.BR SodClass ,
which are the standard roots of the inheritance and metaclass graphs
respectively.
Specifically,
.B SodObject
has no direct superclasses,
and
.B SodClass
is its own metaclass.
It is not possible to define root classes in module files
because of circularities:
.B SodObject
has
.B SodClass
as its metaclass,
and
.B SodClass
is a subclass of
.BR SodObject .
Extensions can define additional root classes,
but this is tricky,
and not really to be recommended.
.
.SS The SodObject class
The
.B SodObject
class defines no slots or messages.
Because
.B 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.
.PP
Since there are no messages,
and
.B SodClass
also has only one chain,
the vtable contains only the standard class pointer and offset-to-base
members.
In an actual instance of
.B SodObject
(why would you want one?)
the class pointer contains the address of
.B SodObject__class
and the offset is zero.
.
.SS The SodClass class
The
.B SodClass
class defines no messages,
but there are a number of slots.
Its only direct superclass is
.B SodObject
and so (like its superclass) its vtable is trivial.
.PP
The slots defined are as follows.
.TP
.B const char *name;
A pointer to the class's name.
.TP
.B const char *nick;
A pointer to the class's nickname.
.TP
.B size_t initsz;
The size in bytes required to store an instance of the class.
.TP
.BI "void *(*imprint)(void *" p );
A pointer to a function:
given a pointer
.I p
to at least
.I 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
.IR p .
.TP
.BI "void *(*init)(void *" p );
A pointer to a function:
given a pointer
.I p
to at least
.I 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
.IR p .
.TP
.B size_t n_supers;
The number of direct superclasses.
(This is zero exactly in the case of
.BR SodObject .)
.TP
.B const SodClass *const *supers;
A pointer to an array of
.I 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
.I n_supers
is zero,
then this pointer is null.
.TP
.B size_t n_cpl;
The number of superclasses in the class's class precedence list.
.TP
.B 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
.IB c ->cls.cpl[0]
=
.I c
for all class objects
.IR c .
.TP
.B 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).
.TP
.B const SodClass *head;
A pointer to the least-specific class in this class's chain;
so
.IB c ->cls.head->cls.link
is always null,
and either
.IB c ->cls.link
is null
(in which case
.IB c ->cls.head
=
.IR c )
or
.IB c ->cls.head
=
.IB c ->cls.link->cls.head \fR.
.TP
.B size_t level;
The number of less specific superclasses in this class's chain.
If
.IB c ->cls.link
is null then
.IB c ->cls.level
is zero;
otherwise
.IB c ->cls.level
=
.IB c ->cls.link->cls.level
+ 1.
.TP
.B size_t n_chains;
The number of chains formed by the class's superclasses.
.TP
.B const struct sod_chain *chains;
A pointer to an array of
.B 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
.IB c ->cls.chains[0].classes[ c ->cls.level]
=
.IR c .
.TP
.B size_t off_islots;
The offset of the class's
.B islots
structure relative to its containing
.B 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.)
.TP
.B size_t islotsz;
The size required to store the class's direct slots,
i.e., the size of its
.B islots
structure.
The class doesn't define any slots if and only if this is zero.
.PP
The
.B struct sod_chain
structure describes an individual chain of superclasses.
It has the following members.
.TP
.B size_t n_classes;
The number of classes in the chain.
This is always at least one.
.TP
.B const SodClass *const *classes;
A pointer to an array of class pointers
listing the classes in the chain from least- to most-specific.
So
.IB classes [ i ]->cls.head
=
.IB classes [0]
for all
0 \(<=
.I i
<
.IR n_classes ,
.IB classes [0]->cls.link
is always null,
and
.IB classes [ i ]->cls.link
=
.IB classes [ "i\fR \- 1" ]
if
1 \(<=
.I i
<
.IR n_classes .
.TP
.B size_t off_ichain;
The size of the
.B ichain
structure for this chain.
.TP
.B const struct sod_vtable *vt;
The vtable for this chain.
(It is possible, therefore, to duplicate the behaviour of the
.I imprint
function by walking the chain structure.
The
.I imprint
function is much faster, though.)
.TP
.B size_t ichainsz;
The size of the
.B ichain
structure for this chain.
.
.\"--------------------------------------------------------------------------
.SH CLASS AND VTABLE 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.
.PP
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.
.PP
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
.I C
(therefore with nickname
.IR c ).
.
.SS Generic instance structure
The entire state of an instance of
.I C
is contained in a single structure of type
.B struct
.IB C __ilayout \fR.
.IP
.nf
.ft B
struct \fIC\fB__ilayout {
\h'2n'union \fIC\fB__ichainu_\fIh\fB {
\h'4n'struct \fIC\fB__ichain_\fIh\fB {
\h'6n'const struct \fIC\fB__vt_\fIh\fB *_vt;
\h'6n'struct \fIH\fB__islots \fIh\fB;
\h'6n'\fR...\fB
\h'6n'struct \fIC\fB__islots {
\h'8n'\fItype\fB \fIslota\fB;
\h'8n'\fR...\fB
\h'6n'} \fIc\fB;
\h'4n'} \fIc\fB;
\h'4n'\fR...\fB
\h'4n'struct \fIH\fB__ichain_\fIh\fB \fIh\fB;
\h'2n'} \fIh\fB;
\h'2n'union \fIB\fB__ichainu_\fIi\fB \fIi\fB;
\h'2n'\fR...\fB
};

typedef struct \fIC\fB__ichain_\fIh\fB \fIC\fB;
.ft P
.fi
.PP
The set of superclasses of
.IR 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
.IR "chain head" .
Suppose that the chain head of the chain containing
.I C
itself is named
.I H
(though keep in mind that it's possible that
.I H
is in fact
.I C
itself.)
.PP
The
.B ilayout
structure contains one member for each of
.IR C 's
superclass chains.
The first such member is
.IP
.B
.B union
.IB C __ichainu_ h 
.IB h ;
.PP
described below;
this is followed by members
.IP
.B union
.IB B __ichainu_ i 
.IB i ;
.PP
for each other chain,
where
.I I
is the head
and
.I 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
.IR B .)
.PP
The
.B ichainu
union contains a member for each class in the chain.
The first is
.IP
.B struct
.IB C __ichain_ h 
.IB c ;
.PP
and this is followed by corresponding members
.IP
.B struct
.IB A __ichain_ h 
.IB a ;
.PP
for each of
.IR C 's
superclasses
.IR A
in the same chain in some (unimportant) order.
A `pointer to
.IR C '
is always assumed
(and, indeed, defined in C's type system)
to be a pointer to the
.B struct
.IB C __ichain_ h \fR.
.PP
The
.B ichain
structure contains (in order), a pointer
.IP
.B const
.B struct
.IB C __vt_ h
.B *_vt;
.PP
followed by a structure
.IP
.B struct
.IB A __islots
.IB a ;
.PP
for each superclass
.I A
of
.IR C
in the same chain which defines slots,
from least- to most-specific;
if
.I C
defines any slots,
then the last member is
.IP
.B struct
.IB C __islots 
.IB c ;
.PP
Finally, the
.B islots
structure simply contains one member for each slot defined by
.I C
in the order they appear in the class definition.
.
.SS Generic vtable structure
As described above,
each
.B ichain
structure of an instance's storage
has a vtable pointer
.IP
.B const
.B struct
.IB C __vt_ h
.B *_vt;
.PP
In general,
the vtables for the different chains
will have
.I different
structures.
.PP
The instance layout split neatly into disjoint chains.
This is necessary because
each
.B ichain
must have as a prefix the
.B 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.
.PP
A vtable for a class
.I C
with chain head
.I H
has the following general structure.
.IP
.nf
.ft B
union \fIC\fB__vtu_\fIh\fB {
\h'2n'struct \fIC\fB__vt_\fIh\fB {
\h'4n'const \fIP\fB *_class;
\h'4n'size_t _base;
\h'4n'\fR...\fB
\h'4n'const \fIQ\fB *_cls_\fIj\fB;
\h'4n'\fR...\fB
\h'4n'ptrdiff_t _off_\fIi\fB;
\h'4n'\fR...\fB
\h'4n'struct \fIC\fB__vtmsgs_\fIa\fB {
\h'6n'\fItype\fB (*\fImsg\fB)(\fIC\fB *, \fR...\fB);
\h'6n'\fR...\fB
\h'4n'} \fIa\fB;
\h'4n'\fR...\fB
\h'2n'} \fIc\fB;
};

extern const union \fIC\fB__vtu_\fIh\fB \fIC\fB__vtable_\fIh\fB;
.ft P
.fi
.PP
The outer layer is a
.B union
.IB C __vtu_ h
containing a member
.IP
.B struct
.IB A __vt_ h
.IB a ;
.PP
for each of
.IR C 's
superclasses
.I A
in the same chain,
with
.I 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
.B vt
structures.
It's important only because it's the outer
.B vtu
union which is exported by name.
Specifically, for each chain of
.IR C 's
superclasses
there is an external object
.IP
.B const union
.IB A __vtu_ i
.IB C __vtable_ i ;
.PP
where
.I A
and
.I I
are respectively the most and least specific classes in the chain.
.PP
The first member in the
.B vt
structure is the
.I root class pointer
.IP
.B const
.IR P
.B *_class;
.PP
Among the superclasses of
.I C
there must be exactly one class
.I O
which itself has no direct superclasses;
this is the
.I root superclass
of
.IR C .
(This is a rule enforced by the Sod translator.)
The metaclass
.I R
of
.I O
is then the
.I root metaclass
of
.IR C .
The
.B _class
member points to the
.B ichain
structure of most specific superclass
.I P
of
.I M
in the same chain as
.IR R .
.PP
This is followed by the
.I base offset
.IP
.B size_t
.B _base;
.PP
which is simply the offset of the
.B ichain
structure from the instance base.
.PP
The rest of the vtable structure is populated
by walking the superclass chain containing
.I C
as follows.
For each such superclass
.IR B ,
in increasing order of specificity,
walk the class precedence list of
.IR 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.)
.PP
So, let
.I A
be some superclass of
.I C
which has been encountered during this traversal.
.hP \*o
Let
.I N
be the metaclass of
.IR A .
Examine the superclass chains of
.I N
in order of decreasing specificity of their most-specific classes.
Let
.I J
be the chain head of such a chain,
and let
.I Q
be the most specific superclass of
.I M
in the same chain as
.IR J .
Then, if there is currently no class pointer of type
.IR Q ,
then add a member
.RS
.IP
.B const
.I Q
.BI *_cls_ j ;
.PP
to the vtable
pointing to the appropriate
.B islots
structure within
.IR M 's
class object.
.RE
.hP \*o
Examine the superclass chains of
.I A
in order of decreasing specificity of their most-specific classes.
Let
.I I
be the chain head of such a chain.
If there is currently no member
.BI _off_ i
then add a member
.RS
.IP
.B ptrdiff_t
.BI _off_ i ;
.PP
to the vtable,
containing the (signed) offset from the
.B ichain
structure of the chain headed by
.I h
to that of the chain headed by
.I i
within the instance's layout.
.RE
.hP \*o
If class
.I A
defines any messages,
and there is currently no member
.IR a ,
then add a member
.RS
.IP
.B struct
.IB C __vtmsgs_ a
.IB a ;
.PP
to the vtable.
See below.
.RE
.PP
Finally, the
.B 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).
.PP
For a standard message which takes a fixed number of arguments,
defined as
.IP
.I tr
.IB m ( \c
.I t1
.IB a1 , 
.RB ... ,
.I tn
.IB an );
.PP
there is always a `main' entry point,
.IP
.I tr
.BI (* m )( \c
.I C
.BI * me ,
.I t1
.IB a1 , 
.RB ... ,
.I tn
.IB an );
.PP
For a standard message which takes a variable number of arguments,
defined as
.IP
.I tr
.IB m ( \c
.I t1
.IB a1 , 
.RB ... ,
.I tn
.IB an , 
.B ...);
.PP
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
.B va_list
in place of the variable portion of the argument list.
.IP
.I tr
.BI (* m )( \c
.I C
.BI * me ,
.I t1
.IB a1 , 
.RB ... ,
.I tn
.IB an ,
.B ...);
.br
.I tr
.BI (* m __v)( \c
.I C
.BI * me ,
.I t1
.IB a1 , 
.RB ... ,
.I tn
.IB an ,
.B va_list
.IB sod__ap );
.
.SS Additional definitions
In addition to the instance and vtable structures described above,
the following definitions are made for each class
.IR C .
.PP
For each message
.I m
directly defined by
.I C
there is a macro definition
.IP
.B #define
.IB C _ m ( me ,
.RB ... )
.IB me ->_vt-> c . m ( me ,
.RB ... )
.PP
which makes sending the message
.I m
to an instance of (any subclass of)
.I C
somewhat less ugly.
If
.I 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.
.IP
.B #define
.IB C _ m __v( me ,
.RB ...,
.IB sod__ap )
.if !t \{\
\e
.br
\h'4m'\c
.\}
.IB me ->_vt-> c . m __v( me ,
.RB ...,
.IB sod__ap )
.PP
For each proper superclass
.I A
of
.IR C ,
there is a macro defined
.IP
.I A
.BI * C __CONV_ a ( C
.BI * _obj );
.PP
(named in
.IR "upper case" )
which converts a (static-type) pointer to
.I C
to a pointer to the same actual instance,
but statically typed as a pointer to
.IR A .
This is most useful when
.I A
is not in the same chain as
.I C
since in-chain upcasts are both trivial and rarely needed,
but the full set is defined for the sake of completeness.
.PP
Finally, the class object is defined as
.IP
.B extern const struct
.IB R __ilayout
.IB C __classobj;
.br
.B #define
.IB C __class
.BI (& C __classobj. j . r )
.PP
The exported symbol
.IB C __classobj
contains the entire class instance.
This is usually rather unwieldy.
The macro
.IB C __class
is usable as a pointer of type
.B const
.I R
.BR * ,
where
.I R
is the root metaclass of
.IR C ,
i.e., the metaclass of the least specific superclass of
.IR C ;
usually this is
.BR "const SodClass *" .
.
.\"--------------------------------------------------------------------------
.SH SEE ALSO
.BR sod (3).
.
.\"--------------------------------------------------------------------------
.SH AUTHOR
Mark Wooding, <mdw@distorted.org.uk>
.
.\"----- That's all, folks --------------------------------------------------