1 | Proposal for virtual functionality |
---|
2 | |
---|
3 | There are two types of virtual inheritance in this proposal, relaxed |
---|
4 | (implicit) and strict (explicit). Relaxed is the simpler case that uses the |
---|
5 | existing trait system with the addition of trait references and vtables. |
---|
6 | Strict adds some constraints and requires some additional notation but allows |
---|
7 | for down-casting. |
---|
8 | |
---|
9 | Relaxed Virtual Inheritance: |
---|
10 | |
---|
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 | |
---|
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: |
---|
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; |
---|
46 | case line : draw(&w->line); break; |
---|
47 | default : handle_error(); break; |
---|
48 | } |
---|
49 | } |
---|
50 | |
---|
51 | While this code will work as implemented, adding any new widgets or any new |
---|
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. |
---|
55 | |
---|
56 | Using trait references to implement the above gives the following : |
---|
57 | |
---|
58 | trait drawable objects[10]; |
---|
59 | fill_objects(objects); |
---|
60 | |
---|
61 | while(running) { |
---|
62 | for(drawable object : objects) { |
---|
63 | draw(object); |
---|
64 | } |
---|
65 | } |
---|
66 | |
---|
67 | The keyword trait is optional (by the same rules as the struct keyword). This |
---|
68 | is not currently supported in CFA and the lookup is not possible to implement |
---|
69 | statically. Therefore we need to add a new feature to handle having dynamic |
---|
70 | lookups like this. |
---|
71 | |
---|
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. |
---|
75 | |
---|
76 | For instance specifying that the drawable trait reference looks up the type |
---|
77 | of the first argument to find the implementation would be : |
---|
78 | |
---|
79 | trait drawable(otype T) { |
---|
80 | void draw(virtual T* ); |
---|
81 | }; |
---|
82 | |
---|
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 |
---|
85 | would have to be explicitly given, or a strong convention would have to be |
---|
86 | enforced (e.g. implementation of trait functions is always drawn from the |
---|
87 | first polymorphic parameter). |
---|
88 | |
---|
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 |
---|
91 | underlying type implementation. Hence a trait reference becomes a kind of |
---|
92 | abstract type, cannot be directly instantiated but can still be used. |
---|
93 | |
---|
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 |
---|
98 | is also restricted, initially forbidden, see extension. |
---|
99 | |
---|
100 | Extension: Multi-parameter Virtual Traits: |
---|
101 | |
---|
102 | This implementation can be extended to traits with multiple parameters if |
---|
103 | one is called out as being the virtual trait. For example : |
---|
104 | |
---|
105 | trait iterator(otype T, dtype Item) { |
---|
106 | Maybe(Item) next(virtual T *); |
---|
107 | } |
---|
108 | |
---|
109 | iterator(int) generators[10]; |
---|
110 | |
---|
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. |
---|
114 | |
---|
115 | |
---|
116 | Strict Virtual Inheritance: |
---|
117 | |
---|
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. |
---|
122 | |
---|
123 | To allow down casting strict virtual requires that all traits and structures |
---|
124 | involved be organized into a tree. Each trait or struct must have a unique |
---|
125 | position on this tree (no multiple inheritance). |
---|
126 | |
---|
127 | This is declared as follows : |
---|
128 | |
---|
129 | trait error(otype T) virtual { |
---|
130 | const char * msg(T *); |
---|
131 | } |
---|
132 | |
---|
133 | trait io_error(otype T) virtual error { |
---|
134 | FILE * src(T *); |
---|
135 | } |
---|
136 | |
---|
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 | |
---|
143 | Also the parent trait is implicitly part of the assertions of the children, |
---|
144 | so all children implement the same operations as the parent. By the unique |
---|
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. |
---|
147 | |
---|
148 | This gives us an important extra feature, runtime checking of the parent-child |
---|
149 | relationship with virtual cast, where a pointer (and maybe a reference) to |
---|
150 | a virtual type can be cast to another virtual cast. However the cast is |
---|
151 | dynamicly check and only occurs if the underlying type is a child of the type |
---|
152 | being cast to. Otherwise null is returned. |
---|
153 | |
---|
154 | (virtual TYPE)EXPR |
---|
155 | |
---|
156 | As an extention, the TYPE may be ommitted if it can be determained from |
---|
157 | context, for instance if the cast occurs on the right hand side of an |
---|
158 | assignment. |
---|
159 | |
---|
160 | Extension: Multiple Parents |
---|
161 | |
---|
162 | Although each trait/struct must have a unique position on each tree, it could |
---|
163 | have positions on multiple trees. All this requires is the ability to give |
---|
164 | multiple parents, as here : |
---|
165 | |
---|
166 | trait region(otype T) virtual drawable, collider; |
---|
167 | |
---|
168 | The restriction being, the parents must come from different trees. This |
---|
169 | object (and all of its children) can be cast to either tree. This is handled |
---|
170 | by generating a separate vtable for each tree the structure is in. |
---|
171 | |
---|
172 | Extension: Multi-parameter Strict Virtual |
---|
173 | |
---|
174 | If a trait has multiple parameters then one must be called out to be the one |
---|
175 | we generate separate vtables for, as in : |
---|
176 | |
---|
177 | trait example(otype T, otype U) virtual(T) ... |
---|
178 | |
---|
179 | This can generate a separate vtable for each U for which all the T+U |
---|
180 | implementations are provided. These are then separate nodes in the tree (or |
---|
181 | the root of different trees) as if each was created individually. Providing a |
---|
182 | single unique instance of these nodes would be the most difficult aspect of |
---|
183 | this extension, possibly intractable, though with sufficient hoisting and |
---|
184 | link-once duplication it may be possible. |
---|
185 | |
---|
186 | Example: |
---|
187 | |
---|
188 | trait argument(otype T) virtual { |
---|
189 | char short_name(virtual T *); |
---|
190 | bool is_set(virtual T *); |
---|
191 | }; |
---|
192 | |
---|
193 | trait value_argument(otype T, otype U) virtual(T) argument { |
---|
194 | U get_value(virtual T *); |
---|
195 | }; |
---|
196 | |
---|
197 | Extension: Structural Inheritance |
---|
198 | |
---|
199 | Currently traits must be the internal nodes and structs the leaf nodes. |
---|
200 | Structs could be made internal nodes as well, in which case the child structs |
---|
201 | would likely structurally inherit the fields of their parents. |
---|
202 | |
---|
203 | |
---|
204 | Storing the Virtual Lookup Table (vtable): |
---|
205 | |
---|
206 | We have so far been silent on how the vtable is created, stored and accessed. |
---|
207 | |
---|
208 | Creation happens at compile time. Function pointers are found by using the |
---|
209 | same best match rules as elsewhere (additional rules for defaults from the |
---|
210 | parent may or may not be required). For strict virtual this must happen at the |
---|
211 | global scope and forbidding static functions, to ensure that a single unique |
---|
212 | vtable is created. Similarly, there may have to be stricter matching rules |
---|
213 | for the functions that go into the vtable, possibly requiring an exact match. |
---|
214 | Relaxed virtual could relax both restrictions, if we allow different vtable |
---|
215 | at different conversion (struct to trait reference) sites. If it is allowed |
---|
216 | local functions being bound to a vtable could cause issues when they go out |
---|
217 | of scope, however this should follow the lifetime rules most C programs |
---|
218 | already follow implicitly. |
---|
219 | |
---|
220 | Most vtables should be stored statically, the only exception being some of |
---|
221 | the relaxed vtables that could have local function pointers. These may be able |
---|
222 | to be stack allocated. All vtables should be immutable and require no manual |
---|
223 | cleanup. |
---|
224 | |
---|
225 | Access has two main options: |
---|
226 | |
---|
227 | The first is through the use of fat pointers, or a tuple of pointers. When the |
---|
228 | object is converted to a trait reference, the pointers to its vtables are |
---|
229 | stored along side it. |
---|
230 | |
---|
231 | This allows for compatibility with existing structures (such as those imported |
---|
232 | from C) and is the default storage method unless a different one is given. |
---|
233 | |
---|
234 | The other is by inlining the vtable pointer as "intrusive vtables". This adds |
---|
235 | a field to the structure to the vtable. The trait reference then has a single |
---|
236 | pointer to this field, the vtable includes an offset to find the beginning of |
---|
237 | the structure again. |
---|
238 | |
---|
239 | This is used if you specify a vtable field in the structure. If given in the |
---|
240 | trait the vtable pointer in the trait reference can then become a single |
---|
241 | pointer to the vtable field and use that to recover the original object |
---|
242 | pointer as well as retrieve all operations. |
---|
243 | |
---|
244 | trait drawable(otype T) { |
---|
245 | vtable drawable; |
---|
246 | }; |
---|
247 | |
---|
248 | struct line { |
---|
249 | vtable drawable; |
---|
250 | vec2 start; |
---|
251 | vec2 end; |
---|
252 | }; |
---|
253 | |
---|
254 | This inline code allows trait references to be converted to plain pointers |
---|
255 | (although they still must be called specially). The vtable field may just be |
---|
256 | an opaque block of memory or it may allow user access to the vtable. If so |
---|
257 | then there should be some way to retrieve the type of the vtable, which will be |
---|
258 | autogenerated and often unique. |
---|
259 | |
---|
260 | It may be worth looking into a way to force the vtable pointer to be in a |
---|
261 | particular location, which would save the storage to store the offset and |
---|
262 | maybe the offset operation itself (offset = 0). However it may not be worth |
---|
263 | introducing a new language feature for. |
---|
264 | As of writing, exceptions actually use this system. |
---|
265 | |
---|
266 | |
---|
267 | Keyword Usage: |
---|
268 | |
---|
269 | It may be desirable to add fewer new keywords than discussed in this proposal. |
---|
270 | It is possible that "virtual" could replace both "vtable" above with |
---|
271 | unambiguous contextual meaning. However, for purposes of clarity in the design |
---|
272 | discussion it is beneficial to keep the keywords for separate concepts distinct. |
---|
273 | |
---|
274 | |
---|
275 | Trait References and Operations: |
---|
276 | |
---|
277 | sizeof(drawable) will return the size of the trait object itself. However : |
---|
278 | |
---|
279 | line a_line; |
---|
280 | drawable widget = a_line; |
---|
281 | sizeof(widget); |
---|
282 | |
---|
283 | Will instead return the sizeof the underlying object, although the trait must |
---|
284 | require that its implementation is sized for there to be a meaningful value |
---|
285 | to return. You may also get the size of the trait reference with |
---|
286 | |
---|
287 | sizeof(&widget); |
---|
288 | |
---|
289 | Calling free on a trait reference will free the memory for the object. It will |
---|
290 | leave the vtables alone, as those are (always?) statically allocated. |
---|
291 | |
---|
292 | |
---|
293 | Special Traits: |
---|
294 | |
---|
295 | trait is_virtual_parent(dtype parent, dtype child) { ... }; |
---|
296 | |
---|
297 | There are others but I believe this one to be the most important. The trait |
---|
298 | holds if the parent type is a strict virtual ancestor (any number of levels) |
---|
299 | of child. It will have to exist at least internally to check for upcasts and |
---|
300 | it can also be used to optimize virtual casts into upcasts. Or a null value or |
---|
301 | error if the cast would never succeed. Exporting it to a special trait allows |
---|
302 | users to express that requirement in their own polymorphic code. |
---|
303 | |
---|
304 | |
---|
305 | Implementation: |
---|
306 | |
---|
307 | Before we can generate any of the nessasary code, the compiler has to get some |
---|
308 | additional information about the code that it currently does not collect. |
---|
309 | |
---|
310 | First it should establish all child->parent links so that it may travel up the |
---|
311 | hierarchy to grab the nessasary information, and create the actual parent |
---|
312 | pointers in the strict virtual tables. It should also maintain the connections |
---|
313 | between the virtual type (structure or trait), the vtable type and the vtable |
---|
314 | instance (or default instance for relaxed virtual if multiple are allowed). To |
---|
315 | this end a sub-node should be created with the nessasary pointers. Traits and |
---|
316 | structs with virtual can create an instance and store all the nessasary data. |
---|
317 | |
---|
318 | With the hierarchy in place it can generate the vtable type for each type, |
---|
319 | it will generally have a function pointer field for each type assertion in |
---|
320 | some consistant order. Strict virtual will also have a pointer to the parent's |
---|
321 | vtable and intrusive vtables will also have the offset to recover the original |
---|
322 | pointer. Sized types will also carry the size. |
---|
323 | |
---|
324 | Wheither the vtable is intrusive or not should also be save so that the trait |
---|
325 | object/reference/pointer knows if it has to store 1 or 2 pointers. A wrapper |
---|
326 | function will have to be generated for each type assertion so that they may |
---|
327 | be called on the trait type, these can probably be inlined. |
---|
328 | |
---|
329 | The virtual parameter will also have to be marked (implicately or explicately) |
---|
330 | until code generation so that the wrapper functions know where to go to get |
---|
331 | the vtable for the function look up. That could probably be added as a |
---|
332 | storageclass, although one that is only valid on type assertions. |
---|
333 | |
---|
334 | The generated vtable will than have to have a vtable instance created and |
---|
335 | filled with all the approprate values. Stricter matching may have to be used |
---|
336 | to ensure that the functions used are stable. It will also have to use |
---|
337 | ".gnu.linkonce" or equilant to ensure only one copy exists in the final code |
---|
338 | base. |
---|