Index: doc/proposals/virtual.txt =================================================================== --- doc/proposals/virtual.txt (revision e0a653db8aa583cd75afd672597c8a9f188a1add) +++ doc/proposals/virtual.txt (revision e2135603bfc33c0e2b6bf4e1ac3d24cf3ebcfd8c) @@ -1,3 +1,11 @@ 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 : @@ -20,6 +28,6 @@ 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 : +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 }; @@ -41,31 +49,31 @@ } -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]; +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) { + 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: +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) { @@ -73,91 +81,197 @@ }; -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. - +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). + +Once a function in a trait has been marked as virtual it defines a new +function that takes in that trait's reference and then dynamically calls the +underlying type implementation. Hence a trait reference becomes a kind of +abstract type, cannot be directly instantiated but can still be used. + +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. + +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 a C++ dynamic_cast like operation. Allowing checked +conversions from trait references to more particular references, which works +if the underlying type is, or is a child of, the new trait type. + +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. + +Creation happens at compile time. Function pointers are found by using the +same best match rules as elsewhere (additional rules for defaults from the +parent may or may not be required). For strict virtual this must happen at the +global scope and forbidding static functions, to ensure that a single unique +vtable is created. Similarly, there may have to be stricter matching rules +for the functions that go into the vtable, possibly requiring an exact match. +Relaxed virtual could relax both restrictions, if we allow different vtable +at different conversion (struct to trait reference) sites. If it is allowed +local functions being bound to a vtable could cause issues when they go out +of scope, however this should follow the lifetime rules most C programs +already follow implicitly. + +Most vtables should be stored statically, the only exception being some of +the relaxed vtables that could have local function pointers. These may be able +to be stack allocated. All vtables should be immutable and require no manual +cleanup. + +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. + + +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.