[63c2bca] | 1 | Proposal for virtual functionality |
---|
| 2 | |
---|
[d49bfa8] | 3 | There are two types of virtual inheritance in this proposal, relaxed |
---|
[c72f9fd] | 4 | (implicit) and strict (explicit). Relaxed is the simpler case that uses the |
---|
[d49bfa8] | 5 | existing trait system with the addition of trait references and vtables. |
---|
[c72f9fd] | 6 | Strict adds some constraints and requires some additional notation but allows |
---|
[d49bfa8] | 7 | for down-casting. |
---|
| 8 | |
---|
| 9 | Relaxed Virtual Inheritance: |
---|
| 10 | |
---|
[63c2bca] | 11 | Imagine the following code : |
---|
| 12 | |
---|
| 13 | trait drawable(otype T) { |
---|
| 14 | void draw(T* ); |
---|
| 15 | }; |
---|
| 16 | |
---|
| 17 | struct text { |
---|
| 18 | char* text; |
---|
| 19 | }; |
---|
| 20 | |
---|
| 21 | void draw(text*); |
---|
| 22 | |
---|
| 23 | struct line{ |
---|
| 24 | vec2 start; |
---|
| 25 | vec2 end; |
---|
| 26 | }; |
---|
| 27 | |
---|
| 28 | void draw(line*); |
---|
| 29 | |
---|
[c72f9fd] | 30 | While all the members of this simple UI support drawing, creating a UI that |
---|
| 31 | easily supports both these UI requires some tedious boiler-plate code: |
---|
[63c2bca] | 32 | |
---|
| 33 | enum type_t { text, line }; |
---|
| 34 | |
---|
| 35 | struct widget { |
---|
| 36 | type_t type; |
---|
| 37 | union { |
---|
| 38 | text t; |
---|
| 39 | line l; |
---|
| 40 | }; |
---|
| 41 | }; |
---|
| 42 | |
---|
| 43 | void draw(widget* w) { |
---|
| 44 | switch(w->type) { |
---|
| 45 | case text : draw(&w->text); break; |
---|
[5a0735ac] | 46 | case line : draw(&w->line); break; |
---|
[63c2bca] | 47 | default : handle_error(); break; |
---|
| 48 | } |
---|
| 49 | } |
---|
| 50 | |
---|
[c72f9fd] | 51 | While this code will work as implemented, adding any new widgets or any new |
---|
[d49bfa8] | 52 | widget behaviors requires changing existing code to add the desired |
---|
| 53 | functionality. To ease this maintenance effort required CFA introduces the |
---|
| 54 | concept of trait references. |
---|
[63c2bca] | 55 | |
---|
[d49bfa8] | 56 | Using trait references to implement the above gives the following : |
---|
[63c2bca] | 57 | |
---|
[d49bfa8] | 58 | trait drawable objects[10]; |
---|
[63c2bca] | 59 | fill_objects(objects); |
---|
| 60 | |
---|
| 61 | while(running) { |
---|
[d49bfa8] | 62 | for(drawable object : objects) { |
---|
[63c2bca] | 63 | draw(object); |
---|
| 64 | } |
---|
| 65 | } |
---|
| 66 | |
---|
[d49bfa8] | 67 | The keyword trait is optional (by the same rules as the struct keyword). This |
---|
[e1e4aa9] | 68 | is not currently supported in CFA and the lookup is not possible to implement |
---|
[d49bfa8] | 69 | statically. Therefore we need to add a new feature to handle having dynamic |
---|
| 70 | lookups like this. |
---|
[63c2bca] | 71 | |
---|
[d49bfa8] | 72 | What we really want to do is express the fact that calling draw() on a trait |
---|
| 73 | reference should find the underlying type of the given parameter and find how |
---|
| 74 | it implements the routine, as in the example with the enumeration and union. |
---|
[63c2bca] | 75 | |
---|
[d49bfa8] | 76 | For instance specifying that the drawable trait reference looks up the type |
---|
[e1e4aa9] | 77 | of the first argument to find the implementation would be : |
---|
[63c2bca] | 78 | |
---|
| 79 | trait drawable(otype T) { |
---|
| 80 | void draw(virtual T* ); |
---|
| 81 | }; |
---|
| 82 | |
---|
[d49bfa8] | 83 | This could be implied in simple cases like this one (single parameter on the |
---|
| 84 | trait and single generic parameter on the function). In more complex cases it |
---|
[c72f9fd] | 85 | would have to be explicitly given, or a strong convention would have to be |
---|
[e1e4aa9] | 86 | enforced (e.g. implementation of trait functions is always drawn from the |
---|
[c72f9fd] | 87 | first polymorphic parameter). |
---|
[63c2bca] | 88 | |
---|
[d49bfa8] | 89 | Once a function in a trait has been marked as virtual it defines a new |
---|
| 90 | function that takes in that trait's reference and then dynamically calls the |
---|
[e1e4aa9] | 91 | underlying type implementation. Hence a trait reference becomes a kind of |
---|
[d49bfa8] | 92 | abstract type, cannot be directly instantiated but can still be used. |
---|
[63c2bca] | 93 | |
---|
[d49bfa8] | 94 | One of the limitations of this design is that it does not support double |
---|
| 95 | dispatching, which concretely means traits cannot have routines with more than |
---|
| 96 | one virtual parameter. The program must have a single table to look up the |
---|
| 97 | function on. Using trait references with traits with more than one parameter |
---|
[c72f9fd] | 98 | is also restricted, initially forbidden, see extension. |
---|
[63c2bca] | 99 | |
---|
[c72f9fd] | 100 | Extension: Multi-parameter Virtual Traits: |
---|
[63c2bca] | 101 | |
---|
[e1e4aa9] | 102 | This implementation can be extended to traits with multiple parameters if |
---|
[d49bfa8] | 103 | one is called out as being the virtual trait. For example : |
---|
[63c2bca] | 104 | |
---|
[d49bfa8] | 105 | trait iterator(otype T, dtype Item) { |
---|
| 106 | Maybe(Item) next(virtual T *); |
---|
| 107 | } |
---|
[63c2bca] | 108 | |
---|
[d49bfa8] | 109 | iterator(int) generators[10]; |
---|
[63c2bca] | 110 | |
---|
[d49bfa8] | 111 | Which creates a collection of iterators that produce integers, regardless of |
---|
| 112 | how those iterators are implemented. This may require a note that this trait |
---|
| 113 | is virtual on T and not Item, but noting it on the functions may be enough. |
---|
[da81e1d0] | 114 | |
---|
[63c2bca] | 115 | |
---|
[d49bfa8] | 116 | Strict Virtual Inheritance: |
---|
[63c2bca] | 117 | |
---|
[d49bfa8] | 118 | One powerful feature relaxed virtual does not support is the idea of down |
---|
| 119 | casting. Once something has been converted into a trait reference there is |
---|
| 120 | very little we can do to recover and of the type information, only the trait's |
---|
| 121 | required function implementations are kept. |
---|
[63c2bca] | 122 | |
---|
[d49bfa8] | 123 | To allow down casting strict virtual requires that all traits and structures |
---|
[e1e4aa9] | 124 | involved be organized into a tree. Each trait or struct must have a unique |
---|
[d49bfa8] | 125 | position on this tree (no multiple inheritance). |
---|
[63c2bca] | 126 | |
---|
[d49bfa8] | 127 | This is declared as follows : |
---|
[63c2bca] | 128 | |
---|
[d49bfa8] | 129 | trait error(otype T) virtual { |
---|
| 130 | const char * msg(T *); |
---|
[63c2bca] | 131 | } |
---|
| 132 | |
---|
[d49bfa8] | 133 | trait io_error(otype T) virtual error { |
---|
| 134 | FILE * src(T *); |
---|
[63c2bca] | 135 | } |
---|
| 136 | |
---|
[d49bfa8] | 137 | struct eof_error virtual io_error { |
---|
| 138 | FILE * fd; |
---|
| 139 | }; |
---|
| 140 | |
---|
| 141 | So the trait error is the head of a new tree and io_error is a child of it. |
---|
| 142 | |
---|
[c72f9fd] | 143 | Also the parent trait is implicitly part of the assertions of the children, |
---|
[d49bfa8] | 144 | so all children implement the same operations as the parent. By the unique |
---|
[c72f9fd] | 145 | path down the tree, we can also uniquely order them so that a prefix of a |
---|
| 146 | child's vtable has the same format as its parent's. |
---|
[d49bfa8] | 147 | |
---|
| 148 | This gives us an important extra feature, runtime checking of the parent-child |
---|
| 149 | relationship with a C++ dynamic_cast like operation. Allowing checked |
---|
[e1e4aa9] | 150 | conversions from trait references to more particular references, which works |
---|
[d49bfa8] | 151 | if the underlying type is, or is a child of, the new trait type. |
---|
| 152 | |
---|
[e1e4aa9] | 153 | Extension: Multiple Parents |
---|
[d49bfa8] | 154 | |
---|
| 155 | Although each trait/struct must have a unique position on each tree, it could |
---|
| 156 | have positions on multiple trees. All this requires is the ability to give |
---|
| 157 | multiple parents, as here : |
---|
| 158 | |
---|
| 159 | trait region(otype T) virtual drawable, collider; |
---|
[63c2bca] | 160 | |
---|
[d49bfa8] | 161 | The restriction being, the parents must come from different trees. This |
---|
| 162 | object (and all of its children) can be cast to either tree. This is handled |
---|
[e1e4aa9] | 163 | by generating a separate vtable for each tree the structure is in. |
---|
[63c2bca] | 164 | |
---|
[e1e4aa9] | 165 | Extension: Multi-parameter Strict Virtual |
---|
[d49bfa8] | 166 | |
---|
[e1e4aa9] | 167 | If a trait has multiple parameters then one must be called out to be the one |
---|
| 168 | we generate separate vtables for, as in : |
---|
[d49bfa8] | 169 | |
---|
| 170 | trait example(otype T, otype U) virtual(T) ... |
---|
| 171 | |
---|
[e1e4aa9] | 172 | This can generate a separate vtable for each U for which all the T+U |
---|
| 173 | implementations are provided. These are then separate nodes in the tree (or |
---|
| 174 | the root of different trees) as if each was created individually. Providing a |
---|
| 175 | single unique instance of these nodes would be the most difficult aspect of |
---|
| 176 | this extension, possibly intractable, though with sufficient hoisting and |
---|
[c72f9fd] | 177 | link-once duplication it may be possible. |
---|
[d49bfa8] | 178 | |
---|
| 179 | Example: |
---|
| 180 | |
---|
| 181 | trait argument(otype T) virtual { |
---|
| 182 | char short_name(virtual T *); |
---|
| 183 | bool is_set(virtual T *); |
---|
[63c2bca] | 184 | }; |
---|
| 185 | |
---|
[d49bfa8] | 186 | trait value_argument(otype T, otype U) virtual(T) argument { |
---|
| 187 | U get_value(virtual T *); |
---|
| 188 | }; |
---|
| 189 | |
---|
[e1e4aa9] | 190 | Extension: Structural Inheritance |
---|
[d49bfa8] | 191 | |
---|
| 192 | Currently traits must be the internal nodes and structs the leaf nodes. |
---|
[e1e4aa9] | 193 | Structs could be made internal nodes as well, in which case the child structs |
---|
[c72f9fd] | 194 | would likely structurally inherit the fields of their parents. |
---|
[d49bfa8] | 195 | |
---|
| 196 | |
---|
| 197 | Storing the Virtual Lookup Table (vtable): |
---|
| 198 | |
---|
[c72f9fd] | 199 | We have so far been silent on how the vtable is created, stored and accessed. |
---|
[d49bfa8] | 200 | |
---|
| 201 | Creation happens at compile time. Function pointers are found by using the |
---|
| 202 | same best match rules as elsewhere (additional rules for defaults from the |
---|
[e1e4aa9] | 203 | parent may or may not be required). For strict virtual this must happen at the |
---|
| 204 | global scope and forbidding static functions, to ensure that a single unique |
---|
[d49bfa8] | 205 | vtable is created. Similarly, there may have to be stricter matching rules |
---|
| 206 | for the functions that go into the vtable, possibly requiring an exact match. |
---|
| 207 | Relaxed virtual could relax both restrictions, if we allow different vtable |
---|
| 208 | at different conversion (struct to trait reference) sites. If it is allowed |
---|
| 209 | local functions being bound to a vtable could cause issues when they go out |
---|
| 210 | of scope, however this should follow the lifetime rules most C programs |
---|
[e1e4aa9] | 211 | already follow implicitly. |
---|
[d49bfa8] | 212 | |
---|
| 213 | Most vtables should be stored statically, the only exception being some of |
---|
| 214 | the relaxed vtables that could have local function pointers. These may be able |
---|
| 215 | to be stack allocated. All vtables should be immutable and require no manual |
---|
| 216 | cleanup. |
---|
| 217 | |
---|
| 218 | Access has two main options: |
---|
| 219 | |
---|
| 220 | The first is through the use of fat pointers, or a tuple of pointers. When the |
---|
| 221 | object is converted to a trait reference, the pointers to its vtables are |
---|
| 222 | stored along side it. |
---|
| 223 | |
---|
[e1e4aa9] | 224 | This allows for compatibility with existing structures (such as those imported |
---|
[d49bfa8] | 225 | from C) and is the default storage method unless a different one is given. |
---|
| 226 | |
---|
| 227 | The other is by inlining the vtable pointer as "intrusive vtables". This adds |
---|
[e1e4aa9] | 228 | a field to the structure to the vtable. The trait reference then has a single |
---|
[d49bfa8] | 229 | pointer to this field, the vtable includes an offset to find the beginning of |
---|
| 230 | the structure again. |
---|
| 231 | |
---|
| 232 | This is used if you specify a vtable field in the structure. If given in the |
---|
| 233 | trait the vtable pointer in the trait reference can then become a single |
---|
| 234 | pointer to the vtable field and use that to recover the original object |
---|
[e1e4aa9] | 235 | pointer as well as retrieve all operations. |
---|
[d49bfa8] | 236 | |
---|
| 237 | trait drawable(otype T) { |
---|
| 238 | vtable drawable; |
---|
| 239 | }; |
---|
| 240 | |
---|
| 241 | struct line { |
---|
| 242 | vtable drawable; |
---|
| 243 | vec2 start; |
---|
| 244 | vec2 end; |
---|
| 245 | }; |
---|
| 246 | |
---|
| 247 | This inline code allows trait references to be converted to plain pointers |
---|
| 248 | (although they still must be called specially). The vtable field may just be |
---|
| 249 | an opaque block of memory or it may allow user access to the vtable. If so |
---|
[e1e4aa9] | 250 | then there should be some way to retrieve the type of the vtable, which will be |
---|
[d49bfa8] | 251 | autogenerated and often unique. |
---|
| 252 | |
---|
| 253 | |
---|
| 254 | Keyword Usage: |
---|
| 255 | |
---|
| 256 | It may be desirable to add fewer new keywords than discussed in this proposal. |
---|
| 257 | It is possible that "virtual" could replace both "vtable" above with |
---|
| 258 | unambiguous contextual meaning. However, for purposes of clarity in the design |
---|
| 259 | discussion it is beneficial to keep the keywords for separate concepts distinct. |
---|
| 260 | |
---|
| 261 | |
---|
| 262 | Trait References and Operations: |
---|
[63c2bca] | 263 | |
---|
[d49bfa8] | 264 | sizeof(drawable) will return the size of the trait object itself. However : |
---|
[63c2bca] | 265 | |
---|
[d49bfa8] | 266 | line a_line; |
---|
| 267 | drawable widget = a_line; |
---|
| 268 | sizeof(widget); |
---|
[da81e1d0] | 269 | |
---|
[d49bfa8] | 270 | Will instead return the sizeof the underlying object, although the trait must |
---|
| 271 | require that its implementation is sized for there to be a meaningful value |
---|
| 272 | to return. You may also get the size of the trait reference with |
---|
[da81e1d0] | 273 | |
---|
[d49bfa8] | 274 | sizeof(&widget); |
---|
[da81e1d0] | 275 | |
---|
[d49bfa8] | 276 | Calling free on a trait reference will free the memory for the object. It will |
---|
| 277 | leave the vtables alone, as those are (always?) statically allocated. |
---|