source: doc/proposals/vtable.md @ 1241851

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

This is an adaptation of the earlier virtual proposal, updating it with new
ideas, re-framing it and laying out more design decisions. It should
eventually replace the earlier proposal, but not all features and syntax have
been converted to the new design.

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.

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);

As with `struct` (and `union` and `enum`), `trait` might be optional when
using the trait as a type name. A trait may be used in assertion list as
before.

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 moved by moving the pointers. Almost all other operations
require some functions to be implemented on the underlying type. Depending on
what is in the virtual table a trait type could be a dtype or otype.

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 hierarchy 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 hierarchy. 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 run-time.

As with regular trait objects, calling a function on a trait object will cause
a look-up 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 hierarchy) to
an abstract type works the same as with normal trait objects, the underlying
object is packaged with a virtual 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 trivial 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 satisfy 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.

### Explicit Resolution Points:
Slightly looser than the above, there are explicit 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 flexible 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 ability 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 resolution rules.

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

This could easily lead to an explosion 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 decisions are made by the
resolver at compile time.

Stack allocated functions interact badly with this because they are not
static. There are several 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 differentiate 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 "implicitly" and returns to the original problem with thunks.