source: doc/proposals/virtual.txt @ a2dbcff1

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resnenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since a2dbcff1 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
Line 
1Proposal for virtual functionality
2
3There are two types of virtual inheritance in this proposal, relaxed
4(implicit) and strict (explicit). Relaxed is the simpler case that uses the
5existing trait system with the addition of trait references and vtables.
6Strict adds some constraints and requires some additional notation but allows
7for down-casting.
8
9Relaxed Virtual Inheritance:
10
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
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:
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;
46            case line : draw(&w->line); break;
47            default : handle_error(); break;
48      }
49}
50
51While this code will work as implemented, adding any new widgets or any new
52widget behaviors requires changing existing code to add the desired
53functionality. To ease this maintenance effort required CFA introduces the
54concept of trait references.
55
56Using trait references to implement the above gives the following :
57
58trait drawable objects[10];
59fill_objects(objects);
60
61while(running) {
62      for(drawable object : objects) {
63            draw(object);
64      }
65}
66
67The keyword trait is optional (by the same rules as the struct keyword). This
68is not currently supported in CFA and the lookup is not possible to implement
69statically. Therefore we need to add a new feature to handle having dynamic
70lookups like this.
71
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.
75
76For instance specifying that the drawable trait reference looks up the type
77of the first argument to find the implementation would be :
78
79trait drawable(otype T) {
80      void draw(virtual T* );
81};
82
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
85would have to be explicitly given, or a strong convention would have to be
86enforced (e.g. implementation of trait functions is always drawn from the
87first polymorphic parameter).
88
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.
93
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
98is also restricted, initially forbidden, see extension.
99
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
104Extension: Multi-parameter Virtual Traits:
105
106This implementation can be extended to traits with multiple parameters if
107one is called out as being the virtual trait. For example :
108
109trait iterator(otype T, dtype Item) {
110        Maybe(Item) next(virtual T *);
111}
112
113iterator(int) generators[10];
114
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.
118
119
120Strict Virtual Inheritance:
121
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.
126
127To allow down casting strict virtual requires that all traits and structures
128involved be organized into a tree. Each trait or struct must have a unique
129position on this tree (no multiple inheritance).
130
131This is declared as follows :
132
133trait error(otype T) virtual {
134        const char * msg(T *);
135}
136
137trait io_error(otype T) virtual error {
138        FILE * src(T *);
139}
140
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
147Also the parent trait is implicitly part of the assertions of the children,
148so all children implement the same operations as the parent. By the unique
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.
151
152This gives us an important extra feature, runtime checking of the parent-child
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.
163
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
180Extension: Multiple Parents
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;
187
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
190by generating a separate vtable for each tree the structure is in.
191
192Extension: Multi-parameter Strict Virtual
193
194If a trait has multiple parameters then one must be called out to be the one
195we generate separate vtables for, as in :
196
197trait example(otype T, otype U) virtual(T) ...
198
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
204link-once duplication it may be possible.
205
206Example:
207
208trait argument(otype T) virtual {
209        char short_name(virtual T *);
210        bool is_set(virtual T *);
211};
212
213trait value_argument(otype T, otype U) virtual(T) argument {
214        U get_value(virtual T *);
215};
216
217Extension: Structural Inheritance
218
219Currently traits must be the internal nodes and structs the leaf nodes.
220Structs could be made internal nodes as well, in which case the child structs
221would likely structurally inherit the fields of their parents.
222
223
224Storing the Virtual Lookup Table (vtable):
225
226We have so far been silent on how the vtable is created, stored and accessed.
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.
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
263This allows for compatibility with existing structures (such as those imported
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
267a field to the structure to the vtable. The trait reference then has a single
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
274pointer as well as retrieve all operations.
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
289then there should be some way to retrieve the type of the vtable, which will be
290autogenerated and often unique.
291
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
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:
308
309sizeof(drawable) will return the size of the trait object itself. However :
310
311line a_line;
312drawable widget = a_line;
313sizeof(widget);
314
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
318
319sizeof(&widget);
320
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.
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.