source: doc/proposals/virtual.txt @ ff1e0f38

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since ff1e0f38 was c3b96677, checked in by Andrew Beach <ajbeach@…>, 7 years ago

Some ramblings for whoever picks up the work I left behind.

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