Index: doc/proposals/virtual.txt =================================================================== --- doc/proposals/virtual.txt (revision 18d4dbdf64c0caa3e9d333291ba42e6a9327eda7) +++ (revision ) @@ -1,370 +1,0 @@ -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 : - -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 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) { - draw(object); - } -} - -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) { - void draw(virtual T* ); -}; - -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). - -Instances of a trait are created by wrapping an existing instance of a type -that implements that trait. This wrapper includes all the function pointers -and other values required to preform the dynamic look-up. These are chosen by -the normal look-up rules at the point of abstraction. - -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. - -Ownership of the underlying structure is also a bit of a trick. Considering -the use cases for trait object, it is probably best to have the underlying -object be heap allocated and owned by the trait object. - -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 virtual cast, where a pointer (and maybe a reference) to -a virtual type can be cast to another virtual cast. However the cast is -dynamicly check and only occurs if the underlying type is a child of the type -being cast to. Otherwise null is returned. - -(virtual TYPE)EXPR - -As an extention, the TYPE may be ommitted if it can be determained from -context, for instance if the cast occurs on the right hand side of an -assignment. - -Function look-up follows the same rules as relaxed (behavioural) inheritance. -Traits can be upcast and down cast without losing information unless the -trait is cast down to a structure. Here there are two options. - - Abstraction Time Binding: The more efficient and consistant with other parts -of CFA. Only the trait types use dynamic look-up, if converveted back into a -structure the normal static look-up rules find the function at compile time. -Casting down to a structure type can then result in the loss of a set of -bindings. - Construction Time Binding: For more consistant handling of the virtual -structs, they are always considered wrapped. Functions are bound to the -instance the moment it is constructed and remain unchanged throughout its -lifetime, so down casting does not lose information. - -(We will have to decide between one of these two.) - -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. -The vtables for the two types might be handled slightly differently and then -there is also the hierarchy data for virtual casts. - -The hierarchy data is simple conceptually. A single (exactly one copy) pointer -for each type can act as the identity for it. The value of the pointer is -its parent type, with the root pointer being NULL. Additional meta-data -can accompany the parent pointer, such as a string name or the vtable fields. - -They types of each vtable can be constructed from the definitions of the -traits (or internal nodes). The stand alone/base vtable is the same for both -kinds of inheritance. It may be argumented differently however (include parent -/this pointer in hierachal inheritance). - -Creation of the actual vtable is tricky. For classical single implementation -semantics we would assemble the functions and create one vtable at compile -time. However, not only does this not give CFA-like behaviour, it is -impossible generally because types can satify assertions in different ways at -different times and stop satifying them. A special set of harder rules could -be used, instead we have decided to try creating multiple vtables for each -type. The different vtables will all implement the same type but not always -in the same way. - -Storage has some issues from creation. If the contents of every vtable could -be determained at compile time they could all be created and stored -statically. However since thunks can be constructed on the stack and become -the best match, that isn't always possible. Those will have to be stored in -dynamic memory. Which means that all vtables must be stored dynamically or -there must be a way to determain which ones to free when the trait object is -destroyed. - -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. - -It may be worth looking into a way to force the vtable pointer to be in a -particular location, which would save the storage to store the offset and -maybe the offset operation itself (offset = 0). However it may not be worth -introducing a new language feature for. -As of writing, exceptions actually use this system. - - -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. - - -Special Traits: - -trait is_virtual_parent(dtype parent, dtype child) { ... }; - -There are others but I believe this one to be the most important. The trait -holds if the parent type is a strict virtual ancestor (any number of levels) -of child. It will have to exist at least internally to check for upcasts and -it can also be used to optimize virtual casts into upcasts. Or a null value or -error if the cast would never succeed. Exporting it to a special trait allows -users to express that requirement in their own polymorphic code. - - -Implementation: - -Before we can generate any of the nessasary code, the compiler has to get some -additional information about the code that it currently does not collect. - -First it should establish all child->parent links so that it may travel up the -hierarchy to grab the nessasary information, and create the actual parent -pointers in the strict virtual tables. It should also maintain the connections -between the virtual type (structure or trait), the vtable type and the vtable -instance (or default instance for relaxed virtual if multiple are allowed). To -this end a sub-node should be created with the nessasary pointers. Traits and -structs with virtual can create an instance and store all the nessasary data. - -With the hierarchy in place it can generate the vtable type for each type, -it will generally have a function pointer field for each type assertion in -some consistant order. Strict virtual will also have a pointer to the parent's -vtable and intrusive vtables will also have the offset to recover the original -pointer. Sized types will also carry the size. - -Wheither the vtable is intrusive or not should also be save so that the trait -object/reference/pointer knows if it has to store 1 or 2 pointers. A wrapper -function will have to be generated for each type assertion so that they may -be called on the trait type, these can probably be inlined. - -The virtual parameter will also have to be marked (implicately or explicately) -until code generation so that the wrapper functions know where to go to get -the vtable for the function look up. That could probably be added as a -storageclass, although one that is only valid on type assertions. - -The generated vtable will than have to have a vtable instance created and -filled with all the approprate values. Stricter matching may have to be used -to ensure that the functions used are stable. It will also have to use -".gnu.linkonce" or equilant to ensure only one copy exists in the final code -base. Index: doc/proposals/vtable.md =================================================================== --- doc/proposals/vtable.md (revision 18d4dbdf64c0caa3e9d333291ba42e6a9327eda7) +++ doc/proposals/vtable.md (revision 881f590a1fec193bdc7574abc2ee477110cedfcb) @@ -93,4 +93,8 @@ } } + +With a more complete widget trait you could, for example, construct a UI tool +kit that can declare containers that hold widgets without knowing about the +widget types. Making it reasonable to extend the tool kit. The trait types can also be used in the types of assertions on traits as well. @@ -244,13 +248,14 @@ We would also like to implement hierarchical relations between types. - AstNode - |-ParseNode - | |-Declaration - | | |-DeclarationWithType - | | |-StructureDeclaration - | |-Statement - | | |-CompoundStatement - | |-Expression - |-Type + ast_node + |-expression_node + | |-operator_expression + | + |-statement_node + | |-goto_statement + | + |-declaration_node + |-using_declaration + |-variable_declaration Virtual tables by themselves are not quite enough to implement this system. @@ -315,4 +320,10 @@ } +This system does not support multiple inheritance. The system could be +extended to support it or a limited form (ex. you may have multiple parents +but they may not have a common ancestor). However this proposal focuses just +on using hierachy as organization. Other uses for reusable/genaric code or +shared interfaces is left for other features of the language. + ### Extension: Structural Inheritance An extension would be allow structures to be used as internal nodes on the @@ -354,5 +365,5 @@ 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. +allows multiple vtables per type. struct _vtable { @@ -367,4 +378,7 @@ // Trait dependent list of vtable members. }; + +One important restriction is that only one instance of each typeid in memory. +There is a ".gnu.linkonce" feature in the linker that might solve the issue. ### Virtual Casts @@ -423,4 +437,37 @@ io_error * error = (virtual)exc; +#### Sample Implementation +This cast implementation assumes a type id layout similar to the one given +above. Also this code is definitely in the underlying C. Functions that give +this functionality could exist in the standard library but these are meant to +be produced by code translation of the virtual cast. + + bool is_in_subtree(typeid const * root, typeid const * id) { + if (root == id) { + return true + } else if (NULL == id->parent) { + return false; + } else { + return is_in_subtree(root, id->parent); + } + } + + void * virtual_cast(typeid const * target, void * value) { + return is_in_subtree(target, *(typeid const **)value) ? value : NULL; + } + +The virtual cast function might have to be wrapped with some casts to make it +compile without warning. + +For the implicate target type we may be able to lean on the type resolution +system that already exists. If the casting to ancestor type is built into +the resolution then the impicate target could be decided by picking an +overload, generated for each hierarchial type (here io_error and its root +type exception). + + io_error * virtual_cast(exception * value) { + return virtual_cast(io_error_typeid, value); + } + ### Extension: Inline vtables Since the structures here are usually made to be turned into trait objects @@ -436,4 +483,8 @@ to allow access to all three options. +The pointer to virtual table field on structures might implicately added (the +types have to declare they are a child here) or created with a declaration, +possibly like the one used to create the assertion. + ### Virtual Tables as Types Here we consider encoding plus the implementation of functions on it to be a @@ -442,4 +493,20 @@ and implementation. +### Question: Wrapping Structures +One issue is what to do with concrete types at the base of the type tree. +When we are working with the concrete type generally it would like them to be +regular structures with direct calls. On the other hand for interactions with +other types in the hierarchy it is more convenent for the type already to be +cast. + +Which of these two should we use? Should we support both and if so how do we +choose which one is being used at any given time. + +On a related note I have been using pointers two trait types here, as that +is how many existing languages handle it. However the generic objects might +be only one or two pointers wide passing the objects as a whole would not +be very expensive and all operations on the generic objects probably have +to be defined anyways. + Resolution Scope ---------------- @@ -534,5 +601,6 @@ 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. +general solution most can keep vtables from making the existing thunk problem +worse, they don't do anything to solve it. Filling in some fields of a static vtable could cause issues on a recursive @@ -549,2 +617,53 @@ shortest lifetime of a function assigned to it. However this still limits the lifetime "implicitly" and returns to the original problem with thunks. + +Odds And Ends +------------- + +In addition to the main design there are a few extras that should be +considered. They are not part of the core design but make the new uses fully +featured. + +### Extension: Parent-Child Assertion +For hierarchy types in regular traits, generic functions or generic structures +we may want to be able to check parent-child relationships between two types +given. For this we might have to add another primitive assertion. It would +have the following form if declared in code: + + trait is_parent_child(dtype Parent, dtype Child) { } + +This assertion is satified if Parent is an ancestor of Child in a hierarchy. +In other words Child can be statically cast to Parent. The cast from Parent +to child would be dynamically checked as usual. + +However in this form there are two concerns. The first that Parent will +usually be consistent for a given use, it will not be a variable. Second is +that we may also need the assertion functions. To do any casting/conversions +anyways. +TODO: Talk about when we wrap a concrete type and how that leads to "may". + +To this end it may be better that the parent trait combines the usual +assertions plus this new primitive assertion. There may or may not be use +cases for accessing just one half and providing easy access to them may be +required depending on how that turns out. + + trait Parent(dtype T | interface(T)) virtual() { } + +### Extension: sizeof Compatablity +Trait types are always sized, it may even be a fixed size like how pointers +have the same size regardless of what they point at. However their contents +may or may not be of a known size (if the `sized(...)` assertion is used). + +Currently there is no way to access this information. If it is needed a +special syntax would have to be added. Here a special case of `sizeof` is +used. + + struct line aLine; + trait drawable widget = aLine; + + size_t x = sizeof(widget); + size_t y = sizeof(trait drawable); + +As usual `y`, size of the type, is the size of the local storage used to put +the value into. The other case `x` checks the saved stored value in the +virtual table and returns that.