source: doc/proposals/virtual.txt @ d49bfa8

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since d49bfa8 was d49bfa8, checked in by Andrew Beach <ajbeach@…>, 4 years ago

That might be everything from yesterday. Hungry now.

  • Property mode set to 100644
File size: 9.4 KB
Line 
1Proposal for virtual functionality
2
3There are two types of virtual inheritance in this proposal, relaxed
4(implicate) and strict (explicate). Relaxed is the simpler case that uses the
5existing trait system with the addition of trait references and vtables.
6Strict adds some constrants 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 indented, 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 suported 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 implemenation 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 explicately given, or a strong convention would have to be
86enforced.
87
88Once a function in a trait has been marked as virtual it defines a new
89function that takes in that trait's reference and then dynamically calls the
90underlying type implemenation. Hence a trait reference becomes a kind of
91abstract type, cannot be directly instantiated but can still be used.
92
93One of the limitations of this design is that it does not support double
94dispatching, which concretely means traits cannot have routines with more than
95one virtual parameter. The program must have a single table to look up the
96function on. Using trait references with traits with more than one parameter
97is also restricted, inistially forbidden, see extention.
98
99Extention: Multi-parameter Virtual Traits:
100
101This implementation can be extented to traits with multiple parameters if
102one is called out as being the virtual trait. For example :
103
104trait iterator(otype T, dtype Item) {
105        Maybe(Item) next(virtual T *);
106}
107
108iterator(int) generators[10];
109
110Which creates a collection of iterators that produce integers, regardless of
111how those iterators are implemented. This may require a note that this trait
112is virtual on T and not Item, but noting it on the functions may be enough.
113
114
115Strict Virtual Inheritance:
116
117One powerful feature relaxed virtual does not support is the idea of down
118casting. Once something has been converted into a trait reference there is
119very little we can do to recover and of the type information, only the trait's
120required function implementations are kept.
121
122To allow down casting strict virtual requires that all traits and structures
123involved be orginized into a tree. Each trait or struct must have a unique
124position on this tree (no multiple inheritance).
125
126This is declared as follows :
127
128trait error(otype T) virtual {
129        const char * msg(T *);
130}
131
132trait io_error(otype T) virtual error {
133        FILE * src(T *);
134}
135
136struct eof_error virtual io_error {
137        FILE * fd;
138};
139
140So the trait error is the head of a new tree and io_error is a child of it.
141
142Also the parent trait is implicately part of the assertions of the children,
143so all children implement the same operations as the parent. By the unique
144path down the tree, we can also uniquely order them so that prefixs of a
145child's vtable has the same format as the parent's.
146
147This gives us an important extra feature, runtime checking of the parent-child
148relationship with a C++ dynamic_cast like operation. Allowing checked
149convertions from trait references to more particular references, which works
150if the underlying type is, or is a child of, the new trait type.
151
152Extention: Multiple Parents
153
154Although each trait/struct must have a unique position on each tree, it could
155have positions on multiple trees. All this requires is the ability to give
156multiple parents, as here :
157
158trait region(otype T) virtual drawable, collider;
159
160The restriction being, the parents must come from different trees. This
161object (and all of its children) can be cast to either tree. This is handled
162by generating a seperate vtable for each tree the structure is in.
163
164Extention: Multi-parameter Strict Virtual
165
166If a trait has multiple parameters than one must be called out to be the one
167we generate seperate vtables for, as in :
168
169trait example(otype T, otype U) virtual(T) ...
170
171This can generate a seperate vtable for each U for which all the T+U
172implementations are provided. These are then seperate nodes in the tree (or
173the root of different trees) as if each was created individually.
174
175Example:
176
177trait argument(otype T) virtual {
178        char short_name(virtual T *);
179        bool is_set(virtual T *);
180};
181
182trait value_argument(otype T, otype U) virtual(T) argument {
183        U get_value(virtual T *);
184};
185
186Extention: Structural Inheritance
187
188Currently traits must be the internal nodes and structs the leaf nodes.
189Structs could be made internal nodes as well, and might specify structural
190inheritance.
191
192
193Storing the Virtual Lookup Table (vtable):
194
195We have so fare been silent on how the vtable is created, stored and accessed.
196
197Creation happens at compile time. Function pointers are found by using the
198same best match rules as elsewhere (additional rules for defaults from the
199parent may or may not be reqired). For strict virtual this must happen at the
200global scope and forbiding static functions, to ensure that a single unique
201vtable is created. Similarly, there may have to be stricter matching rules
202for the functions that go into the vtable, possibly requiring an exact match.
203Relaxed virtual could relax both restrictions, if we allow different vtable
204at different conversion (struct to trait reference) sites. If it is allowed
205local functions being bound to a vtable could cause issues when they go out
206of scope, however this should follow the lifetime rules most C programs
207already follow implicately.
208
209Most vtables should be stored statically, the only exception being some of
210the relaxed vtables that could have local function pointers. These may be able
211to be stack allocated. All vtables should be immutable and require no manual
212cleanup.
213
214Access has two main options:
215
216The first is through the use of fat pointers, or a tuple of pointers. When the
217object is converted to a trait reference, the pointers to its vtables are
218stored along side it.
219
220This allows for compatability with existing structures (such as those imported
221from C) and is the default storage method unless a different one is given.
222
223The other is by inlining the vtable pointer as "intrusive vtables". This adds
224a field to the structure to the vtable. The trait reference than has a single
225pointer to this field, the vtable includes an offset to find the beginning of
226the structure again.
227
228This is used if you specify a vtable field in the structure. If given in the
229trait the vtable pointer in the trait reference can then become a single
230pointer to the vtable field and use that to recover the original object
231pointer as well as retrive all operations.
232
233trait drawable(otype T) {
234        vtable drawable;
235};
236
237struct line {
238        vtable drawable;
239        vec2 start;
240        vec2 end;
241};
242
243This inline code allows trait references to be converted to plain pointers
244(although they still must be called specially). The vtable field may just be
245an opaque block of memory or it may allow user access to the vtable. If so
246than there should be some way to retrive the type of the vtable, which will be
247autogenerated and often unique.
248
249
250Keyword Usage:
251
252It may be desirable to add fewer new keywords than discussed in this proposal.
253It is possible that "virtual" could replace both "vtable" above with
254unambiguous contextual meaning. However, for purposes of clarity in the design
255discussion it is beneficial to keep the keywords for separate concepts distinct.
256
257
258Trait References and Operations:
259
260sizeof(drawable) will return the size of the trait object itself. However :
261
262line a_line;
263drawable widget = a_line;
264sizeof(widget);
265
266Will instead return the sizeof the underlying object, although the trait must
267require that its implementation is sized for there to be a meaningful value
268to return. You may also get the size of the trait reference with
269
270sizeof(&widget);
271
272Calling free on a trait reference will free the memory for the object. It will
273leave the vtables alone, as those are (always?) statically allocated.
Note: See TracBrowser for help on using the repository browser.