source: doc/proposals/virtual.txt@ c0e7723

Proposal for virtual functionality

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 indented, 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 dynamic types, in a manner similar to C++.

A simple usage of dynamic type with the previous example would look like :

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

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

However, this is not currently do-able in the current CFA and furthermore is not
possible to implement statically. Therefore we need to add a new feature to handle
having dynamic types like this (That is types that are found dynamically not types
that change dynamically).

C++ uses inheritance and virtual functions to find the
desired type dynamically. CFA takes inspiration from this solution.

What we really want to do is express the fact that calling draw() on a object
should find the dynamic type of the parameter before calling the routine, much like the
hand written example given above. We can express this by adding the virtual keyword on
the parameter of the constraints on our trait:

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

This expresses the idea that drawable is similar to an abstract base class in C++ and
also gives meaning to trying to take a pointer of drawable. That is anything that can
be cast to a drawable pointer has the necessary information to call the draw routine on
that type. Before that drawable was only a abstract type while now it also points to a
piece of storage which specify which behavior the object will have at run time.

This storage needs to be allocate somewhere. C++ just adds an invisible pointer at
the beginning of the struct but we can do something more explicit for users, actually
have a visible special field :

struct text {
      char* text;
      vtable drawable;
};

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

With these semantics, adding a "vtable drawable" means that text pointers and line pointers are now
convertible to drawable pointers. This conversion will not necessarily be a type only change however, indeed,
the drawable pointer will point to the field "vtable drawable" not the head of the struct. However, since all
the types are known at compile time, converting pointers becomes a simple offset operations.

The vtable field contains a pointer to a vtable which contains all the information needed for the caller
to find the function pointer of the desired behavior.

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. This design
would have many ambiguities if it did support multiple virtual parameter. A futher limitation is 
that traits over more than one type cannot have vtables meaningfully defined for them, as the 
particular vtable to use would be a function of the other type(s) the trait is defined over.

It is worth noting that the function pointers in these vtables are bound at object construction, rather than 
function call-site, as in Cforall's existing polymorphic functions. As such, it is possible that two objects 
with the same static type would have a different vtable (consider what happens if draw(line*) is overridden 
between the definitions of two line objects). Given that the virtual drawable* erases static types though, 
this should not be confusing in practice. A more distressing possibility is that of creating an object that 
outlives the scope of one of the functions in its vtable. This is certainly a possible bug, but it is of a 
type that C programmers are familiar with, and should be able to avoid by the usual methods.

Extensibility.

One of the obvious critics of this implementation is that it lacks extensibility for classes
that cannot be modified (ex: Linux C headers). However this solution can be extended to
allow more extensibility by adding "Fat pointers".

Indeed, users could already "solve" this issue by writing their own fat pointers as such:

trait MyContext(otype T) {
      void* get_stack(virtual T*)
};

void* get_stack(ucontext_t *context);

struct fat_ucontext_t {
      vtable MyContext;
      ucontext_t *context;
}

//Tedious forwarding routine
void* get_stack(fat_ucontext_t *ptr) {
      return get_stack(ptr->context);
}

However, users would have to write all the virtual methods they want to override and make
them all simply forward to the existing method that takes the corresponding POCO(Plain Old C Object).

The alternative we propose is to use language level fat pointers :

trait MyContext(otype T) {
      void* get_stack(virtual T*)
};

void* get_stack(ucontext_t *context);

//The type vptr(ucontext_t) all
vptr(ucontext_t) context;

These behave exactly as the previous example but all the forwarding routines are automatically generated.

Bikeshedding.

It may be desirable to add fewer new keywords than discussed in this proposal; it is possible that "virtual" 
could replace both "vtable" and "vptr" 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.