source: doc/proposals/vtable.md @ 24662ff

aaron-thesisarm-ehcleanup-dtorsdeferred_resnjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexer
Last change on this file since 24662ff was 24662ff, checked in by Andrew Beach <ajbeach@…>, 3 years ago

Added the vtable proposal after much delay.

  • Property mode set to 100644
File size: 7.5 KB
Line 
1Proposal For Use of Virtual Tables
2==================================
3
4This is an adaptation of the earlier virtual proposal, updating it with new
5ideas, reframing it and laying out more design decisions.
6
7The basic concept of a virtual table (vtable) is the same here as in most
8other languages. They will mostly contain function pointers although they
9should be able to store anything that goes into a trait.
10
11This should replace the virtual proposal, although all not all features have
12been converted to the new design.
13
14Trait Instances
15---------------
16
17Currently traits are completely abstract. Data types might implement a trait
18but traits are not themselves data types. This will change that and allow
19instances of traits to be created from instances of data types that implement
20the trait.
21
22    trait combiner(otype T) {
23                void combine(T&, int);
24        };
25
26    struct summation {
27                int sum;
28        };
29
30        void ?{}( struct summation & this ) {
31                this.sum = 0;
32        }
33
34    void combine( struct summation & this, int num ) {
35                this.sum = this.sum + num;
36        }
37
38        trait combiner obj = struct summation{};
39        combine(obj, 5);
40
41Internally a trait object is a pair of pointers. One to an underlying object
42and the other to the vtable. All calls on an trait are implemented by looking
43up the matching function pointer and passing the underlying object and the
44remaining arguments to it.
45
46Trait objects can be copied and moved by copying and moving the pointers.
47They should also be able to own or borrow the underlying object.
48
49Hierarchy
50---------
51
52Virtual tables by them selves are not quite enough to implement the planned
53hierarchy system. An addition of type ids, implemented as pointers which
54point to your parent's type id, is required to actually create the shape of
55the hierarchy. However vtables would allow behaviour to be carried with the
56tree.
57
58The hierachy would be a tree of types, of traits and structs. Currently we do
59not support structural extension, so traits form the internal nodes and
60structures the leaf nodes.
61
62The syntax is undecided but it will include a clause like `virtual (PARENT)`
63on trait and struct definitions. It marks out all types in a hierarchy.
64PARENT may be omitted, if it is this type is the root of a hierachy. Otherwise
65it is the name of the type that is this type's parent in the hierarchy.
66
67Traits define a trait instance type that implements all assertions in this
68trait and its parents up until the root of the hierarchy. Each trait then
69defines a vtable type. Structures will also have a vtable type but it should
70be the same as their parent's.
71
72Trait objects within the tree can be statically cast to a parent type. Casts
73from a parent type to a child type are conditional, they check to make sure
74the underlying instance is an instance of the child type, or an instance of
75one of its children. The type then is recoverable at runtime.
76
77As with regular trait objects, calling a function on a trait object will cause
78a lookup on the the virtual table. The casting rules make sure anything that
79can be cast to a trait type will have all the function implementations for
80that trait.
81
82Converting from a concrete type (structures at the edge of the hierchy) to
83an abstract type works the same as with normal trait objects, the underlying
84object is packaged with a virtal table pointer. Converting back to an abstract
85type requires confirming the underlying type matches, but then simply extracts
86the pointer to it.
87
88### Inline vtables
89Since the structures here are usually made to be turned into trait objects
90it might be worth it to have fields on them to store the virtual table
91pointer. This would have to be declared on the trait as an assertion, but if
92it is the trait object could be a single pointer.
93
94It is trival to do if the field with the virtual table pointer is fixed.
95Otherwise some trickery with pointing to the field and storing the offset in
96the virtual table to recover the main object would have to be used.
97
98### Virtual Tables as Types
99Here we consider encoding plus the implementation of functions on it. Which
100is to say in the type hierarchy structures aren't concrete types anymore,
101instead they are parent types to vtables, which combine the encoding and
102implementation.
103
104Resolution Scope
105----------------
106
107What is the scope of a resolution? When are the functions in a vtable decided
108and how broadly is this applied?
109
110### Type Level:
111Each structure has a single resolution for all of the functions in the
112virtual trait. This is how many languages that implement this or similar
113features do it.
114
115The main thing CFA would need to do it this way is some single point where
116the type declaration, including the functions that satify the trait, are
117all defined. Currently there are many points where this can happen, not all
118of them will have the same definitions and no way to select one over the
119other.
120
121Some syntax would have to be added. All resolutions can be found at compile
122time and a single vtable created for each type at compilation time.
123
124### Explicate Resolution Points:
125Slightly looser than the above, there are explicate points where the vtables
126are resolved, but there is no limit on the number of resolution points that
127might be provided. Each time a object is bound to a trait, one of the
128resolutions is selected. This might be the most flexable option.
129
130An syntax would have to be provided as above. There may also be the option
131to name resolution points so that you can choose between them. This also
132could come with the ablity to forward declare them.
133
134Especially if they are not named, these resolution points should be able to
135appear in functions, where the scoping rules can be used to select one.
136However this also means that stack-allocated functions can end up in the
137vtable.
138
139### Site Based Resolution:
140Every place in code where the binding of a vtable to an object occurs has
141its own resolution. Syntax-wise this is the simplest as it should be able
142to use just the existing declarations and the conversion to trait object.
143It also is very close to the current polymorphic reolution rules.
144
145This works as the explicate resolution points except the resolution points
146are implicate and their would be no selection of which resolution to use. The
147closest (current) resolution is always selected.
148
149This could easily lead to an explosition of vtables as it has the most fine
150grained resolution the number of bindings in a single scope (that produces
151the same binding) could be quite high. Merging identical vtables might help
152reduce that.
153
154Vtable Lifetime Issues
155----------------------
156
157Vtables interact badly with the thunk issue. Conceptually vtables are static
158like type/function data they carry, as those decitions are made by the
159resolver at compile time.
160
161Stack allocated functions interact badly with this because they are not
162static. There are serveral ways to try to resolve this, however without a
163general solution most can only buy time.
164
165Filling in some fields of a static vtable could cause issues on a recursive
166call. And then we are still limited by the lifetime of the stack functions, as
167the vtable with stale pointers is still a problem.
168
169Dynamically allocated vtables introduces memory management overhead and
170requires some way to differentate between dynamic and statically allocated
171tables. The stale function pointer problem continues unless those becomes
172dynamically allocated as well which gives us the same costs again.
173
174Stack allocating the vtable seems like the best issue. The vtable's lifetime
175is now the limiting factor but it should be effectively the same as the
176shortest lifetime of a function assigned to it. However this still limits the
177lifetime "implicately" and returns to the original problem with thunks.
Note: See TracBrowser for help on using the repository browser.