source: doc/proposals/vtable.md @ 24662ff

Proposal For Use of Virtual Tables
==================================

This is an adaptation of the earlier virtual proposal, updating it with new
ideas, reframing it and laying out more design decisions.

The basic concept of a virtual table (vtable) is the same here as in most
other languages. They will mostly contain function pointers although they
should be able to store anything that goes into a trait.

This should replace the virtual proposal, although all not all features have
been converted to the new design.

Trait Instances
---------------

Currently traits are completely abstract. Data types might implement a trait
but traits are not themselves data types. This will change that and allow
instances of traits to be created from instances of data types that implement
the trait.

    trait combiner(otype T) {
                void combine(T&, int);
        };

    struct summation {
                int sum;
        };

        void ?{}( struct summation & this ) {
                this.sum = 0;
        }

    void combine( struct summation & this, int num ) {
                this.sum = this.sum + num;
        }

        trait combiner obj = struct summation{};
        combine(obj, 5);

Internally a trait object is a pair of pointers. One to an underlying object
and the other to the vtable. All calls on an trait are implemented by looking
up the matching function pointer and passing the underlying object and the
remaining arguments to it.

Trait objects can be copied and moved by copying and moving the pointers.
They should also be able to own or borrow the underlying object.

Hierarchy
---------

Virtual tables by them selves are not quite enough to implement the planned
hierarchy system. An addition of type ids, implemented as pointers which
point to your parent's type id, is required to actually create the shape of
the hierarchy. However vtables would allow behaviour to be carried with the
tree.

The hierachy would be a tree of types, of traits and structs. Currently we do
not support structural extension, so traits form the internal nodes and
structures the leaf nodes.

The syntax is undecided but it will include a clause like `virtual (PARENT)`
on trait and struct definitions. It marks out all types in a hierarchy.
PARENT may be omitted, if it is this type is the root of a hierachy. Otherwise
it is the name of the type that is this type's parent in the hierarchy.

Traits define a trait instance type that implements all assertions in this
trait and its parents up until the root of the hierarchy. Each trait then
defines a vtable type. Structures will also have a vtable type but it should
be the same as their parent's.

Trait objects within the tree can be statically cast to a parent type. Casts
from a parent type to a child type are conditional, they check to make sure
the underlying instance is an instance of the child type, or an instance of
one of its children. The type then is recoverable at runtime.

As with regular trait objects, calling a function on a trait object will cause
a lookup on the the virtual table. The casting rules make sure anything that
can be cast to a trait type will have all the function implementations for
that trait.

Converting from a concrete type (structures at the edge of the hierchy) to
an abstract type works the same as with normal trait objects, the underlying
object is packaged with a virtal table pointer. Converting back to an abstract
type requires confirming the underlying type matches, but then simply extracts
the pointer to it.

### Inline vtables
Since the structures here are usually made to be turned into trait objects
it might be worth it to have fields on them to store the virtual table
pointer. This would have to be declared on the trait as an assertion, but if
it is the trait object could be a single pointer.

It is trival to do if the field with the virtual table pointer is fixed.
Otherwise some trickery with pointing to the field and storing the offset in
the virtual table to recover the main object would have to be used.

### Virtual Tables as Types
Here we consider encoding plus the implementation of functions on it. Which
is to say in the type hierarchy structures aren't concrete types anymore,
instead they are parent types to vtables, which combine the encoding and
implementation.

Resolution Scope
----------------

What is the scope of a resolution? When are the functions in a vtable decided
and how broadly is this applied?

### Type Level:
Each structure has a single resolution for all of the functions in the
virtual trait. This is how many languages that implement this or similar
features do it.

The main thing CFA would need to do it this way is some single point where
the type declaration, including the functions that satify the trait, are
all defined. Currently there are many points where this can happen, not all
of them will have the same definitions and no way to select one over the
other.

Some syntax would have to be added. All resolutions can be found at compile
time and a single vtable created for each type at compilation time.

### Explicate Resolution Points:
Slightly looser than the above, there are explicate points where the vtables
are resolved, but there is no limit on the number of resolution points that
might be provided. Each time a object is bound to a trait, one of the
resolutions is selected. This might be the most flexable option.

An syntax would have to be provided as above. There may also be the option
to name resolution points so that you can choose between them. This also
could come with the ablity to forward declare them.

Especially if they are not named, these resolution points should be able to
appear in functions, where the scoping rules can be used to select one.
However this also means that stack-allocated functions can end up in the
vtable.

### Site Based Resolution:
Every place in code where the binding of a vtable to an object occurs has
its own resolution. Syntax-wise this is the simplest as it should be able
to use just the existing declarations and the conversion to trait object.
It also is very close to the current polymorphic reolution rules.

This works as the explicate resolution points except the resolution points
are implicate and their would be no selection of which resolution to use. The
closest (current) resolution is always selected.

This could easily lead to an explosition of vtables as it has the most fine
grained resolution the number of bindings in a single scope (that produces
the same binding) could be quite high. Merging identical vtables might help
reduce that.

Vtable Lifetime Issues
----------------------

Vtables interact badly with the thunk issue. Conceptually vtables are static
like type/function data they carry, as those decitions are made by the
resolver at compile time.

Stack allocated functions interact badly with this because they are not
static. There are serveral ways to try to resolve this, however without a
general solution most can only buy time.

Filling in some fields of a static vtable could cause issues on a recursive
call. And then we are still limited by the lifetime of the stack functions, as
the vtable with stale pointers is still a problem.

Dynamically allocated vtables introduces memory management overhead and
requires some way to differentate between dynamic and statically allocated
tables. The stale function pointer problem continues unless those becomes
dynamically allocated as well which gives us the same costs again.

Stack allocating the vtable seems like the best issue. The vtable's lifetime
is now the limiting factor but it should be effectively the same as the
shortest lifetime of a function assigned to it. However this still limits the
lifetime "implicately" and returns to the original problem with thunks.