Index: doc/proposals/vtable.md =================================================================== --- doc/proposals/vtable.md (revision 6dbeef78b56e5d179cf0a9d2ee1f991e73dde4a4) +++ doc/proposals/vtable.md (revision de23648db6ac7c31a3ec9ae33d4c468764a3f72a) @@ -11,4 +11,9 @@ should be able to store anything that goes into a trait. +I also include notes on a sample implementation, which primarly exists to show +there is a resonable implementation. The code samples for that are in a slight +psudo-code to help avoid name mangling and keeps some CFA features while they +would actually be writen in C. + Trait Instances --------------- @@ -42,12 +47,120 @@ 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. +For traits to be used this way they should meet two requirements. First they +should only have a single polymorphic type and each assertion should use that +type once as a parameter. Extentions may later loosen these requirements. + +If a trait object is used it should generate a series of implicate functions +each of which implements one of the functions required by the trait. So for +combiner there is an implicate: + + void combine(trait combiner & this, int); + +This function is the one actually called at the end + +The main use case for trait objects is that they can be stored. They can be +passed into functions, but using the trait directly is prefred in this case. + + trait drawable(otype T) { + void draw(Surface & to, T & draw); + Rect(int) drawArea(T & draw); + }; + + struct UpdatingSurface { + Surface * surface; + vector(trait drawable) drawables; + }; + + void updateSurface(UpdatingSurface & us) { + for (size_t i = 0 ; i < us.drawables.size ; ++i) { + draw(us.surface, us.drawables[i]); + } + } + +Currently these traits are limited to 1 trait parameter and functions should +have exactly 1 parameter. We cannot abstract away pairs of types and still +pass them into normal functions, which take them seperately. + +The second is required the because we need to get the vtable from somewhere. +If there are 0 trait objects than no vtable is avalible, if we have more than +1 than the vtables give conflicting answers on what underlying function to +call. And even then the underlying type assumes a concrete type. + +This loop can sort of be broken by using the trait object directly in the +signature. This has well defined meaning, but might not be useful. + + trait example(otype T) { + bool test(T & this, trait example & that); + } + +#### Sample Implementation +A simple way to implement trait objects is by a pair of pointers. One to the +underlying object and one to the vtable. + + struct vtable_drawable { + void (*draw)(Surface &, void *); + Rect(int) (*drawArea)(void *); + }; + + struct drawable { + void * object; + vtable_drawable * vtable; + }; + +The functions that run on the trait object would generally be generated using +the following pattern: + + void draw(Surface & surface, drawable & traitObj) { + return traitObj.vtable->draw(surface, traitObj.object); + } + +There may have to be special cases for things like copy construction, that +might require a more sigificant wrapper. On the other hand moving could be +implemented by moving the pointers without any need to refer to the base +object. + +### Extention: Multiple Trait Parameters +Currently, this gives traits two independent uses. They use the same syntax, +except for limits boxable traits have, and yet don't really mix. The most +natural way to do this is to allow trait instances to pick one parameter +that they are generic over, the others they choose types to implement. + +The two ways to do the selection, the first is do it at the trait definition. +Each trait picks out a single parameter which it can box (here the `virtual` +qualifier). When you create an instance of a trait object you provide +arguments like for a generic structure, but skip over the marked parameter. + + trait combiner(virtual otype T, otype Combined) { + void combine(T &, Combined &); + } + + trait combiner(int) int_combiner; + +The second is to do it at the instaniation point. A placeholder (here the +keyword `virtual`) is used to explicately skip over the parameter that will be +abstracted away, with the same rules as above if it was the marked parameter. + + trait combiner(otype T, otype Combined) { + void combine(T &, Combined &); + }; + + trait combiner(virtual, int) int_combiner; + +Using both (first to set the default, second as a local override) would also +work, although might be exessively complicated. + +This is useful in cases where you want to use a generic type, but leave part +of it open and store partially generic result. As a simple example + + trait folder(otype T, otype In, otype Out) { + void fold(T & this, In); + Out fold_result(T & this); + } + +Which allows you to fold values without putting them in a container. If they +are already in a container this is exessive, but if they are generated over +time this gives you a simple interface. This could for instance be used in +a profile, where T changes for each profiling statistic and you can plug in +multiple profilers for any run by adding them to an array. Hierarchy @@ -90,19 +203,130 @@ the pointer to it. +Exception Example: +(Also I'm not sure where I got these casing rules.) + + trait exception(otype T) virtual() { + char const * what(T & this); + } + + trait io_error(otype T) virtual(exception) { + FILE * which_file(T & this); + } + + struct eof_error(otype T) virtual(io_error) { + FILE * file; + } + + char const * what(eof_error &) { + return "Tried to read from an empty file."; + } + + FILE * which_file(eof_error & this) { + return eof_error.file; + } + +Ast Example: + + trait ast_node(otype T) virtual() { + void print(T & this, ostream & out); + void visit(T & this, Visitor & visitor); + CodeLocation const & get_code_location(T & this); + } + + trait expression_node(otype T) virtual(ast_node) { + Type eval_type(T const & this); + } + + struct operator_expression virtual(expression_node) { + enum operator_kind kind; + trait expression_node rands[2]; + } + + trait statement_node(otype T) virtual(ast_node) { + vector(Label) & get_labels(T & this); + } + + struct goto_statement virtual(statement_node) { + vector(Label) labels; + Label target; + } + + trait declaration_node(otype T) virtual(ast_node) { + string name_of(T const & this); + Type type_of(T const & this); + } + + struct using_declaration virtual(declaration_node) { + string new_type; + Type old_type; + } + + struct variable_declaration virtual(declaration_node) { + string name; + Type type; + } + +#### Sample Implementation +The type id may be as little as: + + struct typeid { + struct typeid const * const parent; + }; + +Some linker magic would have to be used to ensure exactly one copy of each +structure for each type exists in memory. There seem to be spectial once +sections that support this and it should be easier than generating unique +ids across compilation units. + +The structure could be extended to contain any additional type information. + +There are two general designs for vtables with type ids. The first is to put +the type id at the top of the vtable, this is the most compact and efficient +solution but only works if we have exactly 1 vtable for each type. The second +is to put a pointer to the type id in each vtable. This has more overhead but +allows multiple vtables. + + struct _vtable { + struct typeid const id; + + // Trait dependent list of vtable members. + }; + + struct _vtable { + struct typeid const * const id; + + // Trait dependent list of vtable members. + }; + +### Virtual Casts +To convert from a pointer to a type higher on the hierarchy to one lower on +the hierarchy a check is used to make sure that the underlying type is also +of that lower type. + +The proposed syntax for this is: + + trait SubType * new_value = (virtual trait SubType *)super_type; + +It will return the same pointer if it does point to the subtype and null if +it does not, doing the check and conversion in one operation. + ### 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. +pointer. This would have to be declared on the trait as an assertion (example: +`vtable;` or `T.vtable;`), but if it is the trait object could be a single +pointer. + +There are also three options for where the pointer to the vtable. It could be +anywhere, a fixed location for each trait or always at the front. For the per- +trait solution an extention to specify what it is (example `vtable[0];`) which +could also be used to combine it with others. So these options can be combined +to allow access to all three options. ### 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. +Here we consider encoding plus the implementation of functions on it to be a +type. 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 @@ -123,6 +347,18 @@ 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. +Some syntax would have to be added to specify the resolution point. To ensure +a single instance there may have to be two variants, one forward declaration +and one to create the instance. With some compiler magic the forward +declaration maybe enough. + + extern trait combiner(struct summation) vtable; + trait combiner(struct summation) vtable; + +Or (with the same variants): + + vtable combiner(struct summation); + +The extern variant promises that the vtable will exist while the normal one +is where the resolution actually happens. ### Explicit Resolution Points: @@ -141,4 +377,26 @@ vtable. + extern trait combiner(struct summation) vtable sum; + trait combiner(struct summation) vtable sum; + + extern trait combiner(struct summation) vtable sum default; + trait combiner(struct summation) vtable sum default; + +The extern difference is the same before. The name (sum in the samples) is +used at the binding site to say which one is picked. The default keyword can +be used in only some of the declarations. + + trait combiner fee = (summation_instance, sum); + trait combiner foe = summation_instance; + +(I am not really happy about this syntax, but it kind of works.) +The object being bound is required. The name of the vtable is optional if +there is exactly one vtable name marked with default. + +These could also be placed inside functions. In which case both the name and +the default keyword might be optional. If the name is ommited in an assignment +the closest vtable is choosen (returning to the global default rule if no +approprate local vtable is in scope). + ### Site Based Resolution: Every place in code where the binding of a vtable to an object occurs has