Changeset 07ac6d0
- Timestamp:
- Apr 9, 2019, 3:02:33 PM (6 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- de23648
- Parents:
- e16797c
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/vtable.md
re16797c r07ac6d0 11 11 should be able to store anything that goes into a trait. 12 12 13 I also include notes on a sample implementation, which primarly exists to show 14 there is a resonable implementation. The code samples for that are in a slight 15 psudo-code to help avoid name mangling and keeps some CFA features while they 16 would actually be writen in C. 17 13 18 Trait Instances 14 19 --------------- … … 42 47 before. 43 48 44 Internally a trait object is a pair of pointers. One to an underlying object 45 and the other to the vtable. All calls on an trait are implemented by looking 46 up the matching function pointer and passing the underlying object and the 47 remaining arguments to it. 48 49 Trait objects can be moved by moving the pointers. Almost all other operations 50 require some functions to be implemented on the underlying type. Depending on 51 what is in the virtual table a trait type could be a dtype or otype. 49 For traits to be used this way they should meet two requirements. First they 50 should only have a single polymorphic type and each assertion should use that 51 type once as a parameter. Extentions may later loosen these requirements. 52 53 If a trait object is used it should generate a series of implicate functions 54 each of which implements one of the functions required by the trait. So for 55 combiner there is an implicate: 56 57 void combine(trait combiner & this, int); 58 59 This function is the one actually called at the end 60 61 The main use case for trait objects is that they can be stored. They can be 62 passed into functions, but using the trait directly is prefred in this case. 63 64 trait drawable(otype T) { 65 void draw(Surface & to, T & draw); 66 Rect(int) drawArea(T & draw); 67 }; 68 69 struct UpdatingSurface { 70 Surface * surface; 71 vector(trait drawable) drawables; 72 }; 73 74 void updateSurface(UpdatingSurface & us) { 75 for (size_t i = 0 ; i < us.drawables.size ; ++i) { 76 draw(us.surface, us.drawables[i]); 77 } 78 } 79 80 Currently these traits are limited to 1 trait parameter and functions should 81 have exactly 1 parameter. We cannot abstract away pairs of types and still 82 pass them into normal functions, which take them seperately. 83 84 The second is required the because we need to get the vtable from somewhere. 85 If there are 0 trait objects than no vtable is avalible, if we have more than 86 1 than the vtables give conflicting answers on what underlying function to 87 call. And even then the underlying type assumes a concrete type. 88 89 This loop can sort of be broken by using the trait object directly in the 90 signature. This has well defined meaning, but might not be useful. 91 92 trait example(otype T) { 93 bool test(T & this, trait example & that); 94 } 95 96 #### Sample Implementation 97 A simple way to implement trait objects is by a pair of pointers. One to the 98 underlying object and one to the vtable. 99 100 struct vtable_drawable { 101 void (*draw)(Surface &, void *); 102 Rect(int) (*drawArea)(void *); 103 }; 104 105 struct drawable { 106 void * object; 107 vtable_drawable * vtable; 108 }; 109 110 The functions that run on the trait object would generally be generated using 111 the following pattern: 112 113 void draw(Surface & surface, drawable & traitObj) { 114 return traitObj.vtable->draw(surface, traitObj.object); 115 } 116 117 There may have to be special cases for things like copy construction, that 118 might require a more sigificant wrapper. On the other hand moving could be 119 implemented by moving the pointers without any need to refer to the base 120 object. 121 122 ### Extention: Multiple Trait Parameters 123 Currently, this gives traits two independent uses. They use the same syntax, 124 except for limits boxable traits have, and yet don't really mix. The most 125 natural way to do this is to allow trait instances to pick one parameter 126 that they are generic over, the others they choose types to implement. 127 128 The two ways to do the selection, the first is do it at the trait definition. 129 Each trait picks out a single parameter which it can box (here the `virtual` 130 qualifier). When you create an instance of a trait object you provide 131 arguments like for a generic structure, but skip over the marked parameter. 132 133 trait combiner(virtual otype T, otype Combined) { 134 void combine(T &, Combined &); 135 } 136 137 trait combiner(int) int_combiner; 138 139 The second is to do it at the instaniation point. A placeholder (here the 140 keyword `virtual`) is used to explicately skip over the parameter that will be 141 abstracted away, with the same rules as above if it was the marked parameter. 142 143 trait combiner(otype T, otype Combined) { 144 void combine(T &, Combined &); 145 }; 146 147 trait combiner(virtual, int) int_combiner; 148 149 Using both (first to set the default, second as a local override) would also 150 work, although might be exessively complicated. 151 152 This is useful in cases where you want to use a generic type, but leave part 153 of it open and store partially generic result. As a simple example 154 155 trait folder(otype T, otype In, otype Out) { 156 void fold(T & this, In); 157 Out fold_result(T & this); 158 } 159 160 Which allows you to fold values without putting them in a container. If they 161 are already in a container this is exessive, but if they are generated over 162 time this gives you a simple interface. This could for instance be used in 163 a profile, where T changes for each profiling statistic and you can plug in 164 multiple profilers for any run by adding them to an array. 52 165 53 166 Hierarchy … … 90 203 the pointer to it. 91 204 205 Exception Example: 206 (Also I'm not sure where I got these casing rules.) 207 208 trait exception(otype T) virtual() { 209 char const * what(T & this); 210 } 211 212 trait io_error(otype T) virtual(exception) { 213 FILE * which_file(T & this); 214 } 215 216 struct eof_error(otype T) virtual(io_error) { 217 FILE * file; 218 } 219 220 char const * what(eof_error &) { 221 return "Tried to read from an empty file."; 222 } 223 224 FILE * which_file(eof_error & this) { 225 return eof_error.file; 226 } 227 228 Ast Example: 229 230 trait ast_node(otype T) virtual() { 231 void print(T & this, ostream & out); 232 void visit(T & this, Visitor & visitor); 233 CodeLocation const & get_code_location(T & this); 234 } 235 236 trait expression_node(otype T) virtual(ast_node) { 237 Type eval_type(T const & this); 238 } 239 240 struct operator_expression virtual(expression_node) { 241 enum operator_kind kind; 242 trait expression_node rands[2]; 243 } 244 245 trait statement_node(otype T) virtual(ast_node) { 246 vector(Label) & get_labels(T & this); 247 } 248 249 struct goto_statement virtual(statement_node) { 250 vector(Label) labels; 251 Label target; 252 } 253 254 trait declaration_node(otype T) virtual(ast_node) { 255 string name_of(T const & this); 256 Type type_of(T const & this); 257 } 258 259 struct using_declaration virtual(declaration_node) { 260 string new_type; 261 Type old_type; 262 } 263 264 struct variable_declaration virtual(declaration_node) { 265 string name; 266 Type type; 267 } 268 269 #### Sample Implementation 270 The type id may be as little as: 271 272 struct typeid { 273 struct typeid const * const parent; 274 }; 275 276 Some linker magic would have to be used to ensure exactly one copy of each 277 structure for each type exists in memory. There seem to be spectial once 278 sections that support this and it should be easier than generating unique 279 ids across compilation units. 280 281 The structure could be extended to contain any additional type information. 282 283 There are two general designs for vtables with type ids. The first is to put 284 the type id at the top of the vtable, this is the most compact and efficient 285 solution but only works if we have exactly 1 vtable for each type. The second 286 is to put a pointer to the type id in each vtable. This has more overhead but 287 allows multiple vtables. 288 289 struct <trait>_vtable { 290 struct typeid const id; 291 292 // Trait dependent list of vtable members. 293 }; 294 295 struct <trait>_vtable { 296 struct typeid const * const id; 297 298 // Trait dependent list of vtable members. 299 }; 300 301 ### Virtual Casts 302 To convert from a pointer to a type higher on the hierarchy to one lower on 303 the hierarchy a check is used to make sure that the underlying type is also 304 of that lower type. 305 306 The proposed syntax for this is: 307 308 trait SubType * new_value = (virtual trait SubType *)super_type; 309 310 It will return the same pointer if it does point to the subtype and null if 311 it does not, doing the check and conversion in one operation. 312 92 313 ### Inline vtables 93 314 Since the structures here are usually made to be turned into trait objects 94 315 it might be worth it to have fields on them to store the virtual table 95 pointer. This would have to be declared on the trait as an assertion, but if 96 it is the trait object could be a single pointer. 97 98 It is trivial to do if the field with the virtual table pointer is fixed. 99 Otherwise some trickery with pointing to the field and storing the offset in 100 the virtual table to recover the main object would have to be used. 316 pointer. This would have to be declared on the trait as an assertion (example: 317 `vtable;` or `T.vtable;`), but if it is the trait object could be a single 318 pointer. 319 320 There are also three options for where the pointer to the vtable. It could be 321 anywhere, a fixed location for each trait or always at the front. For the per- 322 trait solution an extention to specify what it is (example `vtable[0];`) which 323 could also be used to combine it with others. So these options can be combined 324 to allow access to all three options. 101 325 102 326 ### Virtual Tables as Types 103 Here we consider encoding plus the implementation of functions on it . Which104 is to say in the type hierarchy structures aren't concrete types anymore, 105 instead they are parent types to vtables, which combine the encoding and 106 implementation.327 Here we consider encoding plus the implementation of functions on it to be a 328 type. Which is to say in the type hierarchy structures aren't concrete types 329 anymore, instead they are parent types to vtables, which combine the encoding 330 and implementation. 107 331 108 332 Resolution Scope … … 123 347 other. 124 348 125 Some syntax would have to be added. All resolutions can be found at compile 126 time and a single vtable created for each type at compilation time. 349 Some syntax would have to be added to specify the resolution point. To ensure 350 a single instance there may have to be two variants, one forward declaration 351 and one to create the instance. With some compiler magic the forward 352 declaration maybe enough. 353 354 extern trait combiner(struct summation) vtable; 355 trait combiner(struct summation) vtable; 356 357 Or (with the same variants): 358 359 vtable combiner(struct summation); 360 361 The extern variant promises that the vtable will exist while the normal one 362 is where the resolution actually happens. 127 363 128 364 ### Explicit Resolution Points: … … 141 377 vtable. 142 378 379 extern trait combiner(struct summation) vtable sum; 380 trait combiner(struct summation) vtable sum; 381 382 extern trait combiner(struct summation) vtable sum default; 383 trait combiner(struct summation) vtable sum default; 384 385 The extern difference is the same before. The name (sum in the samples) is 386 used at the binding site to say which one is picked. The default keyword can 387 be used in only some of the declarations. 388 389 trait combiner fee = (summation_instance, sum); 390 trait combiner foe = summation_instance; 391 392 (I am not really happy about this syntax, but it kind of works.) 393 The object being bound is required. The name of the vtable is optional if 394 there is exactly one vtable name marked with default. 395 396 These could also be placed inside functions. In which case both the name and 397 the default keyword might be optional. If the name is ommited in an assignment 398 the closest vtable is choosen (returning to the global default rule if no 399 approprate local vtable is in scope). 400 143 401 ### Site Based Resolution: 144 402 Every place in code where the binding of a vtable to an object occurs has
Note: See TracChangeset
for help on using the changeset viewer.