source: doc/proposals/virtual.txt @ fe1b6a4

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since fe1b6a4 was ba5131d, checked in by Aaron Moss <a3moss@…>, 8 years ago

Further notes on virtual proposal

  • Property mode set to 100644
File size: 5.9 KB
Line 
1Proposal for virtual functionality
2
3Imagine the following code :
4
5trait drawable(otype T) {
6      void draw(T* );
7};
8
9struct text {
10      char* text;
11};
12
13void draw(text*);
14
15struct line{
16      vec2 start;
17      vec2 end;
18};
19
20void draw(line*);
21
22While all the members of this simple UI support drawing creating a UI that easily
23supports both these UI requires some tedious boiler-plate code :
24
25enum type_t { text, line };
26
27struct widget {
28      type_t type;
29      union {
30            text t;
31            line l;
32      };
33};
34
35void draw(widget* w) {
36      switch(w->type) {
37            case text : draw(&w->text); break;
38            case line : draw(&w->line); break;
39            default : handle_error(); break;
40      }
41}
42
43While this code will work as indented, adding any new widgets or any new widget behaviors
44requires changing existing code to add the desired functionality. To ease this maintenance
45effort required CFA introduces the concept of dynamic types, in a manner similar to C++.
46
47A simple usage of dynamic type with the previous example would look like :
48
49drawable* objects[10];
50fill_objects(objects);
51
52while(running) {
53      for(drawable* object : objects) {
54            draw(object);
55      }
56}
57
58However, this is not currently do-able in the current CFA and furthermore is not
59possible to implement statically. Therefore we need to add a new feature to handle
60having dynamic types like this (That is types that are found dynamically not types
61that change dynamically).
62
63C++ uses inheritance and virtual functions to find the
64desired type dynamically. CFA takes inspiration from this solution.
65
66What we really want to do is express the fact that calling draw() on a object
67should find the dynamic type of the parameter before calling the routine, much like the
68hand written example given above. We can express this by adding the virtual keyword on
69the parameter of the constraints on our trait:
70
71trait drawable(otype T) {
72      void draw(virtual T* );
73};
74
75This expresses the idea that drawable is similar to an abstract base class in C++ and
76also gives meaning to trying to take a pointer of drawable. That is anything that can
77be cast to a drawable pointer has the necessary information to call the draw routine on
78that type. Before that drawable was only a abstract type while now it also points to a
79piece of storage which specify which behavior the object will have at run time.
80
81This storage needs to be allocate somewhere. C++ just adds an invisible pointer at
82the beginning of the struct but we can do something more explicit for users, actually
83have a visible special field :
84
85struct text {
86      char* text;
87      vtable drawable;
88};
89
90struct line{
91      vtable drawable;
92      vec2 start;
93      vec2 end;
94};
95
96With these semantics, adding a "vtable drawable" means that text pointers and line pointers are now
97convertible to drawable pointers. This conversion will not necessarily be a type only change however, indeed,
98the drawable pointer will point to the field "vtable drawable" not the head of the struct. However, since all
99the types are known at compile time, converting pointers becomes a simple offset operations.
100
101The vtable field contains a pointer to a vtable which contains all the information needed for the caller
102to find the function pointer of the desired behavior.
103
104One of the limitations of this design is that it does not support double dispatching, which
105concretely means traits cannot have routines with more than one virtual parameter. This design
106would have many ambiguities if it did support multiple virtual parameter. A futher limitation is
107that traits over more than one type cannot have vtables meaningfully defined for them, as the
108particular vtable to use would be a function of the other type(s) the trait is defined over.
109
110It is worth noting that the function pointers in these vtables are bound at object construction, rather than
111function call-site, as in Cforall's existing polymorphic functions. As such, it is possible that two objects
112with the same static type would have a different vtable (consider what happens if draw(line*) is overridden
113between the definitions of two line objects). Given that the virtual drawable* erases static types though,
114this should not be confusing in practice. A more distressing possibility is that of creating an object that
115outlives the scope of one of the functions in its vtable. This is certainly a possible bug, but it is of a
116type that C programmers are familiar with, and should be able to avoid by the usual methods.
117
118Extensibility.
119
120One of the obvious critics of this implementation is that it lacks extensibility for classes
121that cannot be modified (ex: Linux C headers). However this solution can be extended to
122allow more extensibility by adding "Fat pointers".
123
124Indeed, users could already "solve" this issue by writing their own fat pointers as such:
125
126trait MyContext(otype T) {
127      void* get_stack(virtual T*)
128};
129
130void* get_stack(ucontext_t *context);
131
132struct fat_ucontext_t {
133      vtable MyContext;
134      ucontext_t *context;
135}
136
137//Tedious forwarding routine
138void* get_stack(fat_ucontext_t *ptr) {
139      return get_stack(ptr->context);
140}
141
142However, users would have to write all the virtual methods they want to override and make
143them all simply forward to the existing method that takes the corresponding POCO(Plain Old C Object).
144
145The alternative we propose is to use language level fat pointers :
146
147trait MyContext(otype T) {
148      void* get_stack(virtual T*)
149};
150
151void* get_stack(ucontext_t *context);
152
153//The type vptr(ucontext_t) all
154vptr(ucontext_t) context;
155
156These behave exactly as the previous example but all the forwarding routines are automatically generated.
157
158Bikeshedding.
159
160It may be desirable to add fewer new keywords than discussed in this proposal; it is possible that "virtual"
161could replace both "vtable" and "vptr" above with unambiguous contextual meaning. However, for purposes of
162clarity in the design discussion it is beneficial to keep the keywords for separate concepts distinct.
163
Note: See TracBrowser for help on using the repository browser.