source: doc/proposals/virtual.txt @ 61dafb8

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resnenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since 61dafb8 was 50fb7df, checked in by Andrew Beach <ajbeach@…>, 6 years ago

Updated the virtual proposal to cover the more dynamic approach.

  • Property mode set to 100644
File size: 14.4 KB
RevLine 
[63c2bca]1Proposal for virtual functionality
2
[d49bfa8]3There 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]5existing trait system with the addition of trait references and vtables.
[c72f9fd]6Strict adds some constraints and requires some additional notation but allows
[d49bfa8]7for down-casting.
8
9Relaxed Virtual Inheritance:
10
[63c2bca]11Imagine the following code :
12
13trait drawable(otype T) {
14      void draw(T* );
15};
16
17struct text {
18      char* text;
19};
20
21void draw(text*);
22
23struct line{
24      vec2 start;
25      vec2 end;
26};
27
28void draw(line*);
29
[c72f9fd]30While all the members of this simple UI support drawing, creating a UI that
31easily supports both these UI requires some tedious boiler-plate code:
[63c2bca]32
33enum type_t { text, line };
34
35struct widget {
36      type_t type;
37      union {
38            text t;
39            line l;
40      };
41};
42
43void 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]51While this code will work as implemented, adding any new widgets or any new
[d49bfa8]52widget behaviors requires changing existing code to add the desired
53functionality. To ease this maintenance effort required CFA introduces the
54concept of trait references.
[63c2bca]55
[d49bfa8]56Using trait references to implement the above gives the following :
[63c2bca]57
[d49bfa8]58trait drawable objects[10];
[63c2bca]59fill_objects(objects);
60
61while(running) {
[d49bfa8]62      for(drawable object : objects) {
[63c2bca]63            draw(object);
64      }
65}
66
[d49bfa8]67The keyword trait is optional (by the same rules as the struct keyword). This
[e1e4aa9]68is not currently supported in CFA and the lookup is not possible to implement
[d49bfa8]69statically. Therefore we need to add a new feature to handle having dynamic
70lookups like this.
[63c2bca]71
[d49bfa8]72What we really want to do is express the fact that calling draw() on a trait
73reference should find the underlying type of the given parameter and find how
74it implements the routine, as in the example with the enumeration and union.
[63c2bca]75
[d49bfa8]76For instance specifying that the drawable trait reference looks up the type
[e1e4aa9]77of the first argument to find the implementation would be :
[63c2bca]78
79trait drawable(otype T) {
80      void draw(virtual T* );
81};
82
[d49bfa8]83This could be implied in simple cases like this one (single parameter on the
84trait and single generic parameter on the function). In more complex cases it
[c72f9fd]85would have to be explicitly given, or a strong convention would have to be
[e1e4aa9]86enforced (e.g. implementation of trait functions is always drawn from the
[c72f9fd]87first polymorphic parameter).
[63c2bca]88
[50fb7df]89Instances of a trait are created by wrapping an existing instance of a type
90that implements that trait. This wrapper includes all the function pointers
91and other values required to preform the dynamic look-up. These are chosen by
92the normal look-up rules at the point of abstraction.
[63c2bca]93
[d49bfa8]94One of the limitations of this design is that it does not support double
95dispatching, which concretely means traits cannot have routines with more than
96one virtual parameter. The program must have a single table to look up the
97function on. Using trait references with traits with more than one parameter
[c72f9fd]98is also restricted, initially forbidden, see extension.
[63c2bca]99
[50fb7df]100Ownership of the underlying structure is also a bit of a trick. Considering
101the use cases for trait object, it is probably best to have the underlying
102object be heap allocated and owned by the trait object.
103
[c72f9fd]104Extension: Multi-parameter Virtual Traits:
[63c2bca]105
[e1e4aa9]106This implementation can be extended to traits with multiple parameters if
[d49bfa8]107one is called out as being the virtual trait. For example :
[63c2bca]108
[d49bfa8]109trait iterator(otype T, dtype Item) {
110        Maybe(Item) next(virtual T *);
111}
[63c2bca]112
[d49bfa8]113iterator(int) generators[10];
[63c2bca]114
[d49bfa8]115Which creates a collection of iterators that produce integers, regardless of
116how those iterators are implemented. This may require a note that this trait
117is virtual on T and not Item, but noting it on the functions may be enough.
[da81e1d0]118
[63c2bca]119
[d49bfa8]120Strict Virtual Inheritance:
[63c2bca]121
[d49bfa8]122One powerful feature relaxed virtual does not support is the idea of down
123casting. Once something has been converted into a trait reference there is
124very little we can do to recover and of the type information, only the trait's
125required function implementations are kept.
[63c2bca]126
[d49bfa8]127To allow down casting strict virtual requires that all traits and structures
[e1e4aa9]128involved be organized into a tree. Each trait or struct must have a unique
[d49bfa8]129position on this tree (no multiple inheritance).
[63c2bca]130
[d49bfa8]131This is declared as follows :
[63c2bca]132
[d49bfa8]133trait error(otype T) virtual {
134        const char * msg(T *);
[63c2bca]135}
136
[d49bfa8]137trait io_error(otype T) virtual error {
138        FILE * src(T *);
[63c2bca]139}
140
[d49bfa8]141struct eof_error virtual io_error {
142        FILE * fd;
143};
144
145So the trait error is the head of a new tree and io_error is a child of it.
146
[c72f9fd]147Also the parent trait is implicitly part of the assertions of the children,
[d49bfa8]148so all children implement the same operations as the parent. By the unique
[c72f9fd]149path down the tree, we can also uniquely order them so that a prefix of a
150child's vtable has the same format as its parent's.
[d49bfa8]151
152This gives us an important extra feature, runtime checking of the parent-child
[c3b96677]153relationship with virtual cast, where a pointer (and maybe a reference) to
154a virtual type can be cast to another virtual cast. However the cast is
155dynamicly check and only occurs if the underlying type is a child of the type
156being cast to. Otherwise null is returned.
157
158(virtual TYPE)EXPR
159
160As an extention, the TYPE may be ommitted if it can be determained from
161context, for instance if the cast occurs on the right hand side of an
162assignment.
[d49bfa8]163
[50fb7df]164Function look-up follows the same rules as relaxed (behavioural) inheritance.
165Traits can be upcast and down cast without losing information unless the
166trait is cast down to a structure. Here there are two options.
167
168  Abstraction Time Binding: The more efficient and consistant with other parts
169of CFA. Only the trait types use dynamic look-up, if converveted back into a
170structure the normal static look-up rules find the function at compile time.
171Casting down to a structure type can then result in the loss of a set of
172bindings.
173  Construction Time Binding: For more consistant handling of the virtual
174structs, they are always considered wrapped. Functions are bound to the
175instance the moment it is constructed and remain unchanged throughout its
176lifetime, so down casting does not lose information.
177
178(We will have to decide between one of these two.)
179
[e1e4aa9]180Extension: Multiple Parents
[d49bfa8]181
182Although each trait/struct must have a unique position on each tree, it could
183have positions on multiple trees. All this requires is the ability to give
184multiple parents, as here :
185
186trait region(otype T) virtual drawable, collider;
[63c2bca]187
[d49bfa8]188The restriction being, the parents must come from different trees. This
189object (and all of its children) can be cast to either tree. This is handled
[e1e4aa9]190by generating a separate vtable for each tree the structure is in.
[63c2bca]191
[e1e4aa9]192Extension: Multi-parameter Strict Virtual
[d49bfa8]193
[e1e4aa9]194If a trait has multiple parameters then one must be called out to be the one
195we generate separate vtables for, as in :
[d49bfa8]196
197trait example(otype T, otype U) virtual(T) ...
198
[e1e4aa9]199This can generate a separate vtable for each U for which all the T+U
200implementations are provided. These are then separate nodes in the tree (or
201the root of different trees) as if each was created individually. Providing a
202single unique instance of these nodes would be the most difficult aspect of
203this extension, possibly intractable, though with sufficient hoisting and
[c72f9fd]204link-once duplication it may be possible.
[d49bfa8]205
206Example:
207
208trait argument(otype T) virtual {
209        char short_name(virtual T *);
210        bool is_set(virtual T *);
[63c2bca]211};
212
[d49bfa8]213trait value_argument(otype T, otype U) virtual(T) argument {
214        U get_value(virtual T *);
215};
216
[e1e4aa9]217Extension: Structural Inheritance
[d49bfa8]218
219Currently traits must be the internal nodes and structs the leaf nodes.
[e1e4aa9]220Structs could be made internal nodes as well, in which case the child structs
[c72f9fd]221would likely structurally inherit the fields of their parents.
[d49bfa8]222
223
224Storing the Virtual Lookup Table (vtable):
225
[c72f9fd]226We have so far been silent on how the vtable is created, stored and accessed.
[50fb7df]227The vtables for the two types might be handled slightly differently and then
228there is also the hierarchy data for virtual casts.
229
230The hierarchy data is simple conceptually. A single (exactly one copy) pointer
231for each type can act as the identity for it. The value of the pointer is
232its parent type, with the root pointer being NULL. Additional meta-data
233can accompany the parent pointer, such as a string name or the vtable fields.
234
235They types of each vtable can be constructed from the definitions of the
236traits (or internal nodes). The stand alone/base vtable is the same for both
237kinds of inheritance. It may be argumented differently however (include parent
238/this pointer in hierachal inheritance).
239
240Creation of the actual vtable is tricky. For classical single implementation
241semantics we would assemble the functions and create one vtable at compile
242time. However, not only does this not give CFA-like behaviour, it is
243impossible generally because types can satify assertions in different ways at
244different times and stop satifying them. A special set of harder rules could
245be used, instead we have decided to try creating multiple vtables for each
246type. The different vtables will all implement the same type but not always
247in the same way.
248
249Storage has some issues from creation. If the contents of every vtable could
250be determained at compile time they could all be created and stored
251statically. However since thunks can be constructed on the stack and become
252the best match, that isn't always possible. Those will have to be stored in
253dynamic memory. Which means that all vtables must be stored dynamically or
254there must be a way to determain which ones to free when the trait object is
255destroyed.
[d49bfa8]256
257Access has two main options:
258
259The first is through the use of fat pointers, or a tuple of pointers. When the
260object is converted to a trait reference, the pointers to its vtables are
261stored along side it.
262
[e1e4aa9]263This allows for compatibility with existing structures (such as those imported
[d49bfa8]264from C) and is the default storage method unless a different one is given.
265
266The other is by inlining the vtable pointer as "intrusive vtables". This adds
[e1e4aa9]267a field to the structure to the vtable. The trait reference then has a single
[d49bfa8]268pointer to this field, the vtable includes an offset to find the beginning of
269the structure again.
270
271This is used if you specify a vtable field in the structure. If given in the
272trait the vtable pointer in the trait reference can then become a single
273pointer to the vtable field and use that to recover the original object
[e1e4aa9]274pointer as well as retrieve all operations.
[d49bfa8]275
276trait drawable(otype T) {
277        vtable drawable;
278};
279
280struct line {
281        vtable drawable;
282        vec2 start;
283        vec2 end;
284};
285
286This inline code allows trait references to be converted to plain pointers
287(although they still must be called specially). The vtable field may just be
288an opaque block of memory or it may allow user access to the vtable. If so
[e1e4aa9]289then there should be some way to retrieve the type of the vtable, which will be
[d49bfa8]290autogenerated and often unique.
291
[c3b96677]292It may be worth looking into a way to force the vtable pointer to be in a
293particular location, which would save the storage to store the offset and
294maybe the offset operation itself (offset = 0). However it may not be worth
295introducing a new language feature for.
296As of writing, exceptions actually use this system.
297
[d49bfa8]298
299Keyword Usage:
300
301It may be desirable to add fewer new keywords than discussed in this proposal.
302It is possible that "virtual" could replace both "vtable" above with
303unambiguous contextual meaning. However, for purposes of clarity in the design
304discussion it is beneficial to keep the keywords for separate concepts distinct.
305
306
307Trait References and Operations:
[63c2bca]308
[d49bfa8]309sizeof(drawable) will return the size of the trait object itself. However :
[63c2bca]310
[d49bfa8]311line a_line;
312drawable widget = a_line;
313sizeof(widget);
[da81e1d0]314
[d49bfa8]315Will instead return the sizeof the underlying object, although the trait must
316require that its implementation is sized for there to be a meaningful value
317to return. You may also get the size of the trait reference with
[da81e1d0]318
[d49bfa8]319sizeof(&widget);
[da81e1d0]320
[d49bfa8]321Calling free on a trait reference will free the memory for the object. It will
322leave the vtables alone, as those are (always?) statically allocated.
[c3b96677]323
324
325Special Traits:
326
327trait is_virtual_parent(dtype parent, dtype child) { ... };
328
329There are others but I believe this one to be the most important. The trait
330holds if the parent type is a strict virtual ancestor (any number of levels)
331of child. It will have to exist at least internally to check for upcasts and
332it can also be used to optimize virtual casts into upcasts. Or a null value or
333error if the cast would never succeed. Exporting it to a special trait allows
334users to express that requirement in their own polymorphic code.
335
336
337Implementation:
338
339Before we can generate any of the nessasary code, the compiler has to get some
340additional information about the code that it currently does not collect.
341
342First it should establish all child->parent links so that it may travel up the
343hierarchy to grab the nessasary information, and create the actual parent
344pointers in the strict virtual tables. It should also maintain the connections
345between the virtual type (structure or trait), the vtable type and the vtable
346instance (or default instance for relaxed virtual if multiple are allowed). To
347this end a sub-node should be created with the nessasary pointers. Traits and
348structs with virtual can create an instance and store all the nessasary data.
349
350With the hierarchy in place it can generate the vtable type for each type,
351it will generally have a function pointer field for each type assertion in
352some consistant order. Strict virtual will also have a pointer to the parent's
353vtable and intrusive vtables will also have the offset to recover the original
354pointer. Sized types will also carry the size.
355
356Wheither the vtable is intrusive or not should also be save so that the trait
357object/reference/pointer knows if it has to store 1 or 2 pointers. A wrapper
358function will have to be generated for each type assertion so that they may
359be called on the trait type, these can probably be inlined.
360
361The virtual parameter will also have to be marked (implicately or explicately)
362until code generation so that the wrapper functions know where to go to get
363the vtable for the function look up. That could probably be added as a
364storageclass, although one that is only valid on type assertions.
365
366The generated vtable will than have to have a vtable instance created and
367filled with all the approprate values. Stricter matching may have to be used
368to ensure that the functions used are stable. It will also have to use
369".gnu.linkonce" or equilant to ensure only one copy exists in the final code
370base.
Note: See TracBrowser for help on using the repository browser.