source: doc/proposals/vtable.md @ 90b9e4b

ADTarm-ehast-experimentalcleanup-dtorsenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 90b9e4b was 1b94115, checked in by Andrew Beach <ajbeach@…>, 5 years ago

The vtable proposal has been updated from the early feedback.

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