source: doc/proposals/virtual.txt @ 80a9898

Proposal for virtual functionality

There are two types of virtual inheritance in this proposal, relaxed
(implicit) and strict (explicit). Relaxed is the simpler case that uses the
existing trait system with the addition of trait references and vtables.
Strict adds some constraints and requires some additional notation but allows
for down-casting.

Relaxed Virtual Inheritance:

Imagine the following code :

trait drawable(otype T) {
      void draw(T* );
};

struct text {
      char* text;
};

void draw(text*);

struct line{
      vec2 start;
      vec2 end;
};

void draw(line*);

While all the members of this simple UI support drawing, creating a UI that
easily supports both these UI requires some tedious boiler-plate code:

enum type_t { text, line };

struct widget {
      type_t type;
      union {
            text t;
            line l;
      };
};

void draw(widget* w) {
      switch(w->type) {
            case text : draw(&w->text); break;
            case line : draw(&w->line); break;
            default : handle_error(); break;
      }
}

While this code will work as implemented, adding any new widgets or any new
widget behaviors requires changing existing code to add the desired
functionality. To ease this maintenance effort required CFA introduces the
concept of trait references.

Using trait references to implement the above gives the following :

trait drawable objects[10];
fill_objects(objects);

while(running) {
      for(drawable object : objects) {
            draw(object);
      }
}

The keyword trait is optional (by the same rules as the struct keyword). This
is not currently supported in CFA and the lookup is not possible to implement
statically. Therefore we need to add a new feature to handle having dynamic
lookups like this.

What we really want to do is express the fact that calling draw() on a trait
reference should find the underlying type of the given parameter and find how
it implements the routine, as in the example with the enumeration and union.

For instance specifying that the drawable trait reference looks up the type
of the first argument to find the implementation would be :

trait drawable(otype T) {
      void draw(virtual T* );
};

This could be implied in simple cases like this one (single parameter on the
trait and single generic parameter on the function). In more complex cases it
would have to be explicitly given, or a strong convention would have to be
enforced (e.g. implementation of trait functions is always drawn from the
first polymorphic parameter).

Instances of a trait are created by wrapping an existing instance of a type
that implements that trait. This wrapper includes all the function pointers
and other values required to preform the dynamic look-up. These are chosen by
the normal look-up rules at the point of abstraction.

One of the limitations of this design is that it does not support double
dispatching, which concretely means traits cannot have routines with more than
one virtual parameter. The program must have a single table to look up the
function on. Using trait references with traits with more than one parameter
is also restricted, initially forbidden, see extension.

Ownership of the underlying structure is also a bit of a trick. Considering
the use cases for trait object, it is probably best to have the underlying
object be heap allocated and owned by the trait object.

Extension: Multi-parameter Virtual Traits:

This implementation can be extended to traits with multiple parameters if
one is called out as being the virtual trait. For example :

trait iterator(otype T, dtype Item) {
        Maybe(Item) next(virtual T *);
}

iterator(int) generators[10];

Which creates a collection of iterators that produce integers, regardless of
how those iterators are implemented. This may require a note that this trait
is virtual on T and not Item, but noting it on the functions may be enough.


Strict Virtual Inheritance:

One powerful feature relaxed virtual does not support is the idea of down
casting. Once something has been converted into a trait reference there is
very little we can do to recover and of the type information, only the trait's
required function implementations are kept.

To allow down casting strict virtual requires that all traits and structures
involved be organized into a tree. Each trait or struct must have a unique
position on this tree (no multiple inheritance).

This is declared as follows :

trait error(otype T) virtual {
        const char * msg(T *);
}

trait io_error(otype T) virtual error {
        FILE * src(T *);
}

struct eof_error virtual io_error {
        FILE * fd;
};

So the trait error is the head of a new tree and io_error is a child of it.

Also the parent trait is implicitly part of the assertions of the children,
so all children implement the same operations as the parent. By the unique
path down the tree, we can also uniquely order them so that a prefix of a
child's vtable has the same format as its parent's.

This gives us an important extra feature, runtime checking of the parent-child
relationship with virtual cast, where a pointer (and maybe a reference) to
a virtual type can be cast to another virtual cast. However the cast is
dynamicly check and only occurs if the underlying type is a child of the type
being cast to. Otherwise null is returned.

(virtual TYPE)EXPR

As an extention, the TYPE may be ommitted if it can be determained from
context, for instance if the cast occurs on the right hand side of an
assignment.

Function look-up follows the same rules as relaxed (behavioural) inheritance.
Traits can be upcast and down cast without losing information unless the
trait is cast down to a structure. Here there are two options.

  Abstraction Time Binding: The more efficient and consistant with other parts
of CFA. Only the trait types use dynamic look-up, if converveted back into a
structure the normal static look-up rules find the function at compile time.
Casting down to a structure type can then result in the loss of a set of
bindings.
  Construction Time Binding: For more consistant handling of the virtual
structs, they are always considered wrapped. Functions are bound to the
instance the moment it is constructed and remain unchanged throughout its
lifetime, so down casting does not lose information.

(We will have to decide between one of these two.)

Extension: Multiple Parents

Although each trait/struct must have a unique position on each tree, it could
have positions on multiple trees. All this requires is the ability to give
multiple parents, as here :

trait region(otype T) virtual drawable, collider;

The restriction being, the parents must come from different trees. This
object (and all of its children) can be cast to either tree. This is handled
by generating a separate vtable for each tree the structure is in.

Extension: Multi-parameter Strict Virtual

If a trait has multiple parameters then one must be called out to be the one
we generate separate vtables for, as in :

trait example(otype T, otype U) virtual(T) ...

This can generate a separate vtable for each U for which all the T+U
implementations are provided. These are then separate nodes in the tree (or
the root of different trees) as if each was created individually. Providing a
single unique instance of these nodes would be the most difficult aspect of
this extension, possibly intractable, though with sufficient hoisting and
link-once duplication it may be possible.

Example:

trait argument(otype T) virtual {
        char short_name(virtual T *);
        bool is_set(virtual T *);
};

trait value_argument(otype T, otype U) virtual(T) argument {
        U get_value(virtual T *);
};

Extension: Structural Inheritance

Currently traits must be the internal nodes and structs the leaf nodes.
Structs could be made internal nodes as well, in which case the child structs
would likely structurally inherit the fields of their parents.


Storing the Virtual Lookup Table (vtable):

We have so far been silent on how the vtable is created, stored and accessed.
The vtables for the two types might be handled slightly differently and then
there is also the hierarchy data for virtual casts.

The hierarchy data is simple conceptually. A single (exactly one copy) pointer
for each type can act as the identity for it. The value of the pointer is
its parent type, with the root pointer being NULL. Additional meta-data
can accompany the parent pointer, such as a string name or the vtable fields.

They types of each vtable can be constructed from the definitions of the
traits (or internal nodes). The stand alone/base vtable is the same for both
kinds of inheritance. It may be argumented differently however (include parent
/this pointer in hierachal inheritance).

Creation of the actual vtable is tricky. For classical single implementation
semantics we would assemble the functions and create one vtable at compile
time. However, not only does this not give CFA-like behaviour, it is
impossible generally because types can satify assertions in different ways at
different times and stop satifying them. A special set of harder rules could
be used, instead we have decided to try creating multiple vtables for each
type. The different vtables will all implement the same type but not always
in the same way.

Storage has some issues from creation. If the contents of every vtable could
be determained at compile time they could all be created and stored
statically. However since thunks can be constructed on the stack and become
the best match, that isn't always possible. Those will have to be stored in
dynamic memory. Which means that all vtables must be stored dynamically or
there must be a way to determain which ones to free when the trait object is
destroyed.

Access has two main options:

The first is through the use of fat pointers, or a tuple of pointers. When the
object is converted to a trait reference, the pointers to its vtables are
stored along side it.

This allows for compatibility with existing structures (such as those imported
from C) and is the default storage method unless a different one is given.

The other is by inlining the vtable pointer as "intrusive vtables". This adds
a field to the structure to the vtable. The trait reference then has a single
pointer to this field, the vtable includes an offset to find the beginning of
the structure again.

This is used if you specify a vtable field in the structure. If given in the
trait the vtable pointer in the trait reference can then become a single
pointer to the vtable field and use that to recover the original object
pointer as well as retrieve all operations.

trait drawable(otype T) {
        vtable drawable;
};

struct line {
        vtable drawable;
        vec2 start;
        vec2 end;
};

This inline code allows trait references to be converted to plain pointers
(although they still must be called specially). The vtable field may just be
an opaque block of memory or it may allow user access to the vtable. If so
then there should be some way to retrieve the type of the vtable, which will be
autogenerated and often unique.

It may be worth looking into a way to force the vtable pointer to be in a
particular location, which would save the storage to store the offset and
maybe the offset operation itself (offset = 0). However it may not be worth
introducing a new language feature for.
As of writing, exceptions actually use this system.


Keyword Usage:

It may be desirable to add fewer new keywords than discussed in this proposal.
It is possible that "virtual" could replace both "vtable" above with
unambiguous contextual meaning. However, for purposes of clarity in the design
discussion it is beneficial to keep the keywords for separate concepts distinct.


Trait References and Operations:

sizeof(drawable) will return the size of the trait object itself. However :

line a_line;
drawable widget = a_line;
sizeof(widget);

Will instead return the sizeof the underlying object, although the trait must
require that its implementation is sized for there to be a meaningful value
to return. You may also get the size of the trait reference with

sizeof(&widget);

Calling free on a trait reference will free the memory for the object. It will
leave the vtables alone, as those are (always?) statically allocated.


Special Traits:

trait is_virtual_parent(dtype parent, dtype child) { ... };

There are others but I believe this one to be the most important. The trait
holds if the parent type is a strict virtual ancestor (any number of levels)
of child. It will have to exist at least internally to check for upcasts and
it can also be used to optimize virtual casts into upcasts. Or a null value or
error if the cast would never succeed. Exporting it to a special trait allows
users to express that requirement in their own polymorphic code.


Implementation:

Before we can generate any of the nessasary code, the compiler has to get some
additional information about the code that it currently does not collect.

First it should establish all child->parent links so that it may travel up the
hierarchy to grab the nessasary information, and create the actual parent
pointers in the strict virtual tables. It should also maintain the connections
between the virtual type (structure or trait), the vtable type and the vtable
instance (or default instance for relaxed virtual if multiple are allowed). To
this end a sub-node should be created with the nessasary pointers. Traits and
structs with virtual can create an instance and store all the nessasary data.

With the hierarchy in place it can generate the vtable type for each type,
it will generally have a function pointer field for each type assertion in
some consistant order. Strict virtual will also have a pointer to the parent's
vtable and intrusive vtables will also have the offset to recover the original
pointer. Sized types will also carry the size.

Wheither the vtable is intrusive or not should also be save so that the trait
object/reference/pointer knows if it has to store 1 or 2 pointers. A wrapper
function will have to be generated for each type assertion so that they may
be called on the trait type, these can probably be inlined.

The virtual parameter will also have to be marked (implicately or explicately)
until code generation so that the wrapper functions know where to go to get
the vtable for the function look up. That could probably be added as a
storageclass, although one that is only valid on type assertions.

The generated vtable will than have to have a vtable instance created and
filled with all the approprate values. Stricter matching may have to be used
to ensure that the functions used are stable. It will also have to use
".gnu.linkonce" or equilant to ensure only one copy exists in the final code
base.