[24662ff] | 1 | Proposal For Use of Virtual Tables
|
---|
| 2 | ==================================
|
---|
| 3 |
|
---|
| 4 | The basic concept of a virtual table (vtable) is the same here as in most
|
---|
[18d4dbd] | 5 | other languages that use them. They will mostly contain function pointers
|
---|
| 6 | although they should be able to store anything that goes into a trait.
|
---|
[24662ff] | 7 |
|
---|
[18d4dbd] | 8 | I also include notes on a sample implementation, which primarily exists to show
|
---|
| 9 | there is a reasonable implementation. The code samples for that are in a slight
|
---|
| 10 | pseudo-code to help avoid name mangling and keeps some CFA features while they
|
---|
| 11 | would actually be written in C.
|
---|
[07ac6d0] | 12 |
|
---|
[24662ff] | 13 | Trait Instances
|
---|
| 14 | ---------------
|
---|
| 15 |
|
---|
| 16 | Currently traits are completely abstract. Data types might implement a trait
|
---|
[18d4dbd] | 17 | but traits are not themselves data types. Which is to say you cannot have an
|
---|
| 18 | instance of a trait. This proposal will change that and allow instances of
|
---|
| 19 | traits to be created from instances of data types that implement the trait.
|
---|
| 20 |
|
---|
| 21 | For example:
|
---|
[24662ff] | 22 |
|
---|
| 23 | trait combiner(otype T) {
|
---|
[18d4dbd] | 24 | void combine(T&, int);
|
---|
| 25 | };
|
---|
[24662ff] | 26 |
|
---|
| 27 | struct summation {
|
---|
[18d4dbd] | 28 | int sum;
|
---|
| 29 | };
|
---|
[24662ff] | 30 |
|
---|
[18d4dbd] | 31 | void ?{}( struct summation & this ) {
|
---|
| 32 | this.sum = 0;
|
---|
| 33 | }
|
---|
[24662ff] | 34 |
|
---|
| 35 | void combine( struct summation & this, int num ) {
|
---|
[18d4dbd] | 36 | this.sum = this.sum + num;
|
---|
| 37 | }
|
---|
[24662ff] | 38 |
|
---|
[18d4dbd] | 39 | trait combiner obj = struct summation{};
|
---|
| 40 | combine(obj, 5);
|
---|
[24662ff] | 41 |
|
---|
[1b94115] | 42 | As with `struct` (and `union` and `enum`), `trait` might be optional when
|
---|
| 43 | using the trait as a type name. A trait may be used in assertion list as
|
---|
| 44 | before.
|
---|
| 45 |
|
---|
[07ac6d0] | 46 | For traits to be used this way they should meet two requirements. First they
|
---|
| 47 | should only have a single polymorphic type and each assertion should use that
|
---|
[18d4dbd] | 48 | type once as a parameter. Extensions may later loosen these requirements.
|
---|
| 49 |
|
---|
| 50 | Also note this applies to the final expanded list of assertions. Consider:
|
---|
[07ac6d0] | 51 |
|
---|
[18d4dbd] | 52 | trait foo(otype T, otype U) {
|
---|
| 53 | ... functions that use T once ...
|
---|
| 54 | }
|
---|
| 55 |
|
---|
| 56 | trait bar(otype S | foo(S, char)) {
|
---|
| 57 | ... functions that use S once ...
|
---|
| 58 | }
|
---|
[07ac6d0] | 59 |
|
---|
[18d4dbd] | 60 | In this example `bar` may be used as a type but `foo` may not.
|
---|
[07ac6d0] | 61 |
|
---|
[18d4dbd] | 62 | When a trait is used as a type it creates a generic object which combines
|
---|
| 63 | the base structure (an instance of `summation` in this case) and the vtable,
|
---|
| 64 | which is currently created and provided by a hidden mechanism.
|
---|
| 65 |
|
---|
| 66 | The generic object type for each trait also implements that trait. This is
|
---|
| 67 | actually the only means by which it can be used. The type of these functions
|
---|
| 68 | look something like this:
|
---|
| 69 |
|
---|
| 70 | void combine(trait combiner & this, int num);
|
---|
[07ac6d0] | 71 |
|
---|
| 72 | The main use case for trait objects is that they can be stored. They can be
|
---|
[18d4dbd] | 73 | passed into functions, but using the trait directly is preferred in this case.
|
---|
[07ac6d0] | 74 |
|
---|
| 75 | trait drawable(otype T) {
|
---|
| 76 | void draw(Surface & to, T & draw);
|
---|
| 77 | Rect(int) drawArea(T & draw);
|
---|
| 78 | };
|
---|
| 79 |
|
---|
| 80 | struct UpdatingSurface {
|
---|
| 81 | Surface * surface;
|
---|
| 82 | vector(trait drawable) drawables;
|
---|
| 83 | };
|
---|
| 84 |
|
---|
| 85 | void updateSurface(UpdatingSurface & us) {
|
---|
| 86 | for (size_t i = 0 ; i < us.drawables.size ; ++i) {
|
---|
| 87 | draw(us.surface, us.drawables[i]);
|
---|
| 88 | }
|
---|
| 89 | }
|
---|
| 90 |
|
---|
[881f590] | 91 | With a more complete widget trait you could, for example, construct a UI tool
|
---|
| 92 | kit that can declare containers that hold widgets without knowing about the
|
---|
| 93 | widget types. Making it reasonable to extend the tool kit.
|
---|
| 94 |
|
---|
[18d4dbd] | 95 | The trait types can also be used in the types of assertions on traits as well.
|
---|
| 96 | In this usage they passed as the underlying object and vtable pair as they
|
---|
| 97 | are stored. The trait types can also be used in that trait's definition, which
|
---|
| 98 | means you can pass two instances of a trait to a single function. However the
|
---|
| 99 | look-up of the one that is not used to look up any functions, until another
|
---|
| 100 | function that uses that object in the generic/look-up location is called.
|
---|
[07ac6d0] | 101 |
|
---|
| 102 | trait example(otype T) {
|
---|
| 103 | bool test(T & this, trait example & that);
|
---|
| 104 | }
|
---|
| 105 |
|
---|
[18d4dbd] | 106 | ### Explanation Of Restrictions
|
---|
| 107 |
|
---|
| 108 | The two restrictions on traits that can be used as trait objects are:
|
---|
| 109 |
|
---|
| 110 | 1. Only one generic parameter may be defined in the trait's header.
|
---|
| 111 | 2. Each function assertion must have one parameter with the type of the
|
---|
| 112 | generic parameter. They may or may not return a value of that type.
|
---|
| 113 |
|
---|
| 114 | Elsewhere in this proposal I suggest ways to broaden these requirements.
|
---|
| 115 | A simple example would be if a trait meets requirement 1 but not 2, then
|
---|
| 116 | the assertions that do not satisfy the exactly one parameter requirement can
|
---|
| 117 | be ignored.
|
---|
| 118 |
|
---|
| 119 | However I would like to talk about why these two rules are in place in the
|
---|
| 120 | first place and the problems that any exceptions to these rules must avoid.
|
---|
| 121 |
|
---|
| 122 | The problems appear when the dispatcher function which operates on the
|
---|
| 123 | generic object.
|
---|
| 124 |
|
---|
| 125 | trait combiner(otype T, otype U) {
|
---|
| 126 | void combine(T&, U);
|
---|
| 127 | }
|
---|
| 128 |
|
---|
| 129 | This one is so strange I don't have proper syntax for it but let us say that
|
---|
| 130 | the concrete dispatcher would be typed as
|
---|
| 131 | `void combine(combiner(T) &, combiner(U));`. Does the function that combine
|
---|
| 132 | the two underlying types exist to dispatch too?
|
---|
| 133 |
|
---|
| 134 | Maybe not. If `combiner(T)` works with ints and `combiner(U)` is a char then
|
---|
| 135 | they could not be. It would have to enforce that all pairs of any types
|
---|
| 136 | that are wrapped in this way. Which would pretty much destroy any chance of
|
---|
| 137 | separate compilation.
|
---|
| 138 |
|
---|
| 139 | Even then it would be more expensive as the wrappers would have to carry ids
|
---|
| 140 | that you use to look up on an <number of types>+1 dimensional table.
|
---|
| 141 |
|
---|
| 142 | The second restriction has a similar issue but makes a bit more sense to
|
---|
| 143 | write out.
|
---|
| 144 |
|
---|
| 145 | trait Series(otype T) {
|
---|
| 146 | ... size, iterators, getters ...
|
---|
| 147 | T join(T const &, T const &);
|
---|
| 148 | }
|
---|
| 149 |
|
---|
| 150 | With the dispatcher typed as:
|
---|
| 151 |
|
---|
| 152 | Series join(Series const &, Series const &);
|
---|
| 153 |
|
---|
| 154 | Because these instances are generic and hide the underlying implementation we
|
---|
| 155 | do not know what that implementation is. Unfortunately this also means the
|
---|
| 156 | implementation for the two parameters might not be the same. Once we have
|
---|
| 157 | two different types involved this devolves into the first case.
|
---|
| 158 |
|
---|
| 159 | We could check at run-time that the have the same underlying type, but this
|
---|
| 160 | would likely time and space overhead and there is no clear recovery path.
|
---|
| 161 |
|
---|
[07ac6d0] | 162 | #### Sample Implementation
|
---|
| 163 | A simple way to implement trait objects is by a pair of pointers. One to the
|
---|
| 164 | underlying object and one to the vtable.
|
---|
| 165 |
|
---|
| 166 | struct vtable_drawable {
|
---|
| 167 | void (*draw)(Surface &, void *);
|
---|
| 168 | Rect(int) (*drawArea)(void *);
|
---|
| 169 | };
|
---|
| 170 |
|
---|
| 171 | struct drawable {
|
---|
| 172 | void * object;
|
---|
| 173 | vtable_drawable * vtable;
|
---|
| 174 | };
|
---|
| 175 |
|
---|
| 176 | The functions that run on the trait object would generally be generated using
|
---|
| 177 | the following pattern:
|
---|
| 178 |
|
---|
| 179 | void draw(Surface & surface, drawable & traitObj) {
|
---|
| 180 | return traitObj.vtable->draw(surface, traitObj.object);
|
---|
| 181 | }
|
---|
[24662ff] | 182 |
|
---|
[07ac6d0] | 183 | There may have to be special cases for things like copy construction, that
|
---|
[18d4dbd] | 184 | might require a more significant wrapper. On the other hand moving could be
|
---|
[07ac6d0] | 185 | implemented by moving the pointers without any need to refer to the base
|
---|
| 186 | object.
|
---|
| 187 |
|
---|
[18d4dbd] | 188 | ### Extension: Multiple Trait Parameters
|
---|
| 189 | The base proposal in effect creates another use for the trait syntax that is
|
---|
| 190 | related to the ones currently in the language but is also separate from them.
|
---|
| 191 | The current uses generic functions and generic types, this new use could be
|
---|
| 192 | described as generic objects.
|
---|
| 193 |
|
---|
| 194 | A generic object is of a concrete type and has concrete functions that work on
|
---|
| 195 | it. It is generic in that it is a wrapper for an unknown type. Traits serve
|
---|
| 196 | a similar role here as in generic functions as they limit what the function
|
---|
| 197 | can be generic over.
|
---|
| 198 |
|
---|
| 199 | This combines the use allowing to have a generic type that is a generic
|
---|
| 200 | object. All but one of the trait's parameters is given a concrete type,
|
---|
| 201 | conceptually currying the trait to create a trait with on generic parameter
|
---|
| 202 | that fits the original restrictions. The resulting concrete generic object
|
---|
| 203 | type is different with each set of provided parameters and their values.
|
---|
| 204 |
|
---|
| 205 | Then it just becomes a question of where this is done. Again both examples use
|
---|
| 206 | a basic syntax to show the idea.
|
---|
| 207 |
|
---|
| 208 | trait iterator(virtual otype T, otype Item) {
|
---|
| 209 | bool has_next(T const &);
|
---|
| 210 | Item get_next(T const *);
|
---|
[07ac6d0] | 211 | }
|
---|
| 212 |
|
---|
[18d4dbd] | 213 | iterator(int) int_it = begin(container_of_ints);
|
---|
[07ac6d0] | 214 |
|
---|
[18d4dbd] | 215 | The first option is to do it at the definition of the trait. One parameter
|
---|
| 216 | is selected (here with the `virtual` keyword, but other rules like "the first"
|
---|
| 217 | could also be used) and when an instance of the trait is created all the
|
---|
| 218 | other parameters must be provided.
|
---|
[07ac6d0] | 219 |
|
---|
[18d4dbd] | 220 | trait iterator(otype T, otype Item) {
|
---|
| 221 | bool has_next(T const &);
|
---|
[0f740d6] | 222 | Item get_next(T &);
|
---|
[18d4dbd] | 223 | }
|
---|
[07ac6d0] | 224 |
|
---|
[18d4dbd] | 225 | iterator(virtual, int) int_it = begin(container_of_ints);
|
---|
[07ac6d0] | 226 |
|
---|
[18d4dbd] | 227 | The second option is to skip a parameter as part of the type instance
|
---|
| 228 | definition. One parameter is explicitly skipped (again with the `virtual`
|
---|
| 229 | keyword) and the others have concrete types. The skipped one is the one we
|
---|
| 230 | are generic on.
|
---|
[07ac6d0] | 231 |
|
---|
[18d4dbd] | 232 | Incidentally in both examples `container_of_ints` may itself be a generic
|
---|
| 233 | object and `begin` returns a generic iterator with unknown implementation.
|
---|
[07ac6d0] | 234 |
|
---|
[18d4dbd] | 235 | These options are not exclusive. Defining a default on the trait allows for
|
---|
| 236 | an object to be created as in the first example. However, whether the
|
---|
| 237 | default is provided or not, the second syntax can be used to pick a
|
---|
| 238 | parameter on instantiation.
|
---|
[24662ff] | 239 |
|
---|
[fbfd97bd] | 240 | ### Extension: Object Access
|
---|
| 241 | This requires that the resolution scope (see below) is at the type level or
|
---|
| 242 | has explicate points with names. These are the tables and table names used
|
---|
| 243 | here.
|
---|
| 244 |
|
---|
| 245 | The system already knows where to find the virtual table and the object. If
|
---|
| 246 | the tables have particular identities, or on the user side names, then it is
|
---|
| 247 | meaningful to check if a binding virtual table is the same* as another. The
|
---|
| 248 | main use of this is virtual table declarations also give the type they bind
|
---|
| 249 | and if a binding table matches a known table then the underlyind object in the
|
---|
| 250 | trait object must be of that type.
|
---|
| 251 |
|
---|
| 252 | * By identity, by value would work and in some senses be more flexiable. But
|
---|
| 253 | it would be slower and refering to further away functions would be harder.
|
---|
| 254 |
|
---|
| 255 | This gives one of the main new features of the hierarchical use of virtual
|
---|
| 256 | tables (see below); the ability to recover the underlying object. Or a pointer
|
---|
| 257 | of the approprate type it which both reflects the implementation and gives a
|
---|
| 258 | convenent way to encode the boolean/conditional aspect of the operation which
|
---|
| 259 | is that a different virtual table might be in use.
|
---|
| 260 |
|
---|
| 261 | There are two general ways to reperent this; a cast or a field access. The
|
---|
| 262 | cast is traditional and would definitely fit if a single pointer repersents
|
---|
| 263 | a trait object with the virtual table as part of the object. However for a
|
---|
| 264 | double pointer field access might be more approprate. By this system though
|
---|
| 265 | it is not the type that is used as the identifier but the virtual table. If
|
---|
| 266 | there is one table per type than it becomes equivilant again. Otherwise the
|
---|
| 267 | table has to be used as the identifier and the type is just a result of that
|
---|
| 268 | which seems important for syntax.
|
---|
| 269 |
|
---|
[24662ff] | 270 | Hierarchy
|
---|
| 271 | ---------
|
---|
| 272 |
|
---|
[18d4dbd] | 273 | We would also like to implement hierarchical relations between types.
|
---|
| 274 |
|
---|
[881f590] | 275 | ast_node
|
---|
| 276 | |-expression_node
|
---|
| 277 | | |-operator_expression
|
---|
| 278 | |
|
---|
| 279 | |-statement_node
|
---|
| 280 | | |-goto_statement
|
---|
| 281 | |
|
---|
| 282 | |-declaration_node
|
---|
| 283 | |-using_declaration
|
---|
| 284 | |-variable_declaration
|
---|
[18d4dbd] | 285 |
|
---|
| 286 | Virtual tables by themselves are not quite enough to implement this system.
|
---|
| 287 | A vtable is just a list of functions and there is no way to check at run-time
|
---|
| 288 | what these functions, we carry that knowledge with the table.
|
---|
| 289 |
|
---|
| 290 | This proposal adds type ids to check for position in the hierarchy and an
|
---|
| 291 | explicate syntax for establishing a hierarchical relation between traits and
|
---|
| 292 | their implementing types. The ids should uniquely identify each type and
|
---|
| 293 | allow retrieval of the type's parent if one exists. By recursion this allows
|
---|
| 294 | the ancestor relation between any two hierarchical types can be checked.
|
---|
| 295 |
|
---|
| 296 | The hierarchy is created with traits as the internal nodes and structures
|
---|
| 297 | as the leaf nodes. The structures may be used normally and the traits can
|
---|
| 298 | be used to create generic objects as in the first section (the same
|
---|
| 299 | restrictions apply). However these type objects store their type id which can
|
---|
| 300 | be recovered to figure out which type they are or at least check to see if
|
---|
| 301 | they fall into a given sub-tree at run-time.
|
---|
| 302 |
|
---|
| 303 | Here is an example of part of a hierarchy. The `virtual(PARENT)` syntax is
|
---|
| 304 | just an example. But when used it give the name of the parent type or if
|
---|
| 305 | empty it shows that this type is the root of its hierarchy.
|
---|
[07ac6d0] | 306 | (Also I'm not sure where I got these casing rules.)
|
---|
| 307 |
|
---|
| 308 | trait ast_node(otype T) virtual() {
|
---|
| 309 | void print(T & this, ostream & out);
|
---|
| 310 | void visit(T & this, Visitor & visitor);
|
---|
| 311 | CodeLocation const & get_code_location(T & this);
|
---|
| 312 | }
|
---|
| 313 |
|
---|
| 314 | trait expression_node(otype T) virtual(ast_node) {
|
---|
| 315 | Type eval_type(T const & this);
|
---|
| 316 | }
|
---|
| 317 |
|
---|
| 318 | struct operator_expression virtual(expression_node) {
|
---|
| 319 | enum operator_kind kind;
|
---|
| 320 | trait expression_node rands[2];
|
---|
| 321 | }
|
---|
| 322 |
|
---|
| 323 | trait statement_node(otype T) virtual(ast_node) {
|
---|
| 324 | vector(Label) & get_labels(T & this);
|
---|
| 325 | }
|
---|
| 326 |
|
---|
| 327 | struct goto_statement virtual(statement_node) {
|
---|
| 328 | vector(Label) labels;
|
---|
| 329 | Label target;
|
---|
| 330 | }
|
---|
| 331 |
|
---|
| 332 | trait declaration_node(otype T) virtual(ast_node) {
|
---|
| 333 | string name_of(T const & this);
|
---|
| 334 | Type type_of(T const & this);
|
---|
| 335 | }
|
---|
| 336 |
|
---|
| 337 | struct using_declaration virtual(declaration_node) {
|
---|
| 338 | string new_type;
|
---|
| 339 | Type old_type;
|
---|
| 340 | }
|
---|
| 341 |
|
---|
| 342 | struct variable_declaration virtual(declaration_node) {
|
---|
| 343 | string name;
|
---|
| 344 | Type type;
|
---|
| 345 | }
|
---|
| 346 |
|
---|
[881f590] | 347 | This system does not support multiple inheritance. The system could be
|
---|
| 348 | extended to support it or a limited form (ex. you may have multiple parents
|
---|
| 349 | but they may not have a common ancestor). However this proposal focuses just
|
---|
| 350 | on using hierachy as organization. Other uses for reusable/genaric code or
|
---|
| 351 | shared interfaces is left for other features of the language.
|
---|
| 352 |
|
---|
[18d4dbd] | 353 | ### Extension: Structural Inheritance
|
---|
| 354 | An extension would be allow structures to be used as internal nodes on the
|
---|
| 355 | inheritance tree. Its child types would have to implement the same fields.
|
---|
| 356 |
|
---|
| 357 | The weaker restriction would be to convert the fields into field assertions
|
---|
| 358 | (Not implemented yet: `U T.x` means there is a field of type you on the type
|
---|
| 359 | T. Offset unknown and passed in/stored with function pointers.)
|
---|
| 360 | A concrete child would have to declare the same set of fields with the same
|
---|
| 361 | types. This is of a more functional style.
|
---|
| 362 |
|
---|
| 363 | The stronger restriction is that the fields of the parent are a prefix of the
|
---|
| 364 | child's fields. Possibly automatically inserted. This the imperative view and
|
---|
| 365 | may also have less overhead.
|
---|
| 366 |
|
---|
| 367 | ### Extension: Unions and Enumerations
|
---|
| 368 | Currently there is no reason unions and enumerations, in the cases they
|
---|
| 369 | do implement the trait, could not be in the hierarchy as leaf nodes.
|
---|
| 370 |
|
---|
| 371 | It does not work with structural induction, but that could just be a compile
|
---|
| 372 | time check that all ancestors are traits or do not add field assertions.
|
---|
| 373 |
|
---|
[07ac6d0] | 374 | #### Sample Implementation
|
---|
| 375 | The type id may be as little as:
|
---|
| 376 |
|
---|
| 377 | struct typeid {
|
---|
| 378 | struct typeid const * const parent;
|
---|
| 379 | };
|
---|
| 380 |
|
---|
| 381 | Some linker magic would have to be used to ensure exactly one copy of each
|
---|
[18d4dbd] | 382 | structure for each type exists in memory. There seem to be special once
|
---|
[07ac6d0] | 383 | sections that support this and it should be easier than generating unique
|
---|
| 384 | ids across compilation units.
|
---|
| 385 |
|
---|
| 386 | The structure could be extended to contain any additional type information.
|
---|
| 387 |
|
---|
| 388 | There are two general designs for vtables with type ids. The first is to put
|
---|
| 389 | the type id at the top of the vtable, this is the most compact and efficient
|
---|
| 390 | solution but only works if we have exactly 1 vtable for each type. The second
|
---|
| 391 | is to put a pointer to the type id in each vtable. This has more overhead but
|
---|
[881f590] | 392 | allows multiple vtables per type.
|
---|
[07ac6d0] | 393 |
|
---|
| 394 | struct <trait>_vtable {
|
---|
| 395 | struct typeid const id;
|
---|
| 396 |
|
---|
| 397 | // Trait dependent list of vtable members.
|
---|
| 398 | };
|
---|
| 399 |
|
---|
| 400 | struct <trait>_vtable {
|
---|
| 401 | struct typeid const * const id;
|
---|
| 402 |
|
---|
| 403 | // Trait dependent list of vtable members.
|
---|
| 404 | };
|
---|
| 405 |
|
---|
[881f590] | 406 | One important restriction is that only one instance of each typeid in memory.
|
---|
| 407 | There is a ".gnu.linkonce" feature in the linker that might solve the issue.
|
---|
| 408 |
|
---|
[07ac6d0] | 409 | ### Virtual Casts
|
---|
[18d4dbd] | 410 | The generic objects may be cast up and down the hierarchy.
|
---|
[07ac6d0] | 411 |
|
---|
[18d4dbd] | 412 | Casting to an ancestor type always succeeds. From one generic type to another
|
---|
| 413 | is just a reinterpretation and could be implicate. Wrapping and unwrapping
|
---|
| 414 | a concrete type will probably use the same syntax as in the first section.
|
---|
| 415 |
|
---|
| 416 | Casting from an ancestor to a descendent requires a check. The underlying
|
---|
| 417 | type may or may not belong to the sub-tree headed by that descendent. For this
|
---|
| 418 | we introduce a new cast operator, which returns the pointer unchanged if the
|
---|
| 419 | check succeeds and null otherwise.
|
---|
[07ac6d0] | 420 |
|
---|
| 421 | trait SubType * new_value = (virtual trait SubType *)super_type;
|
---|
| 422 |
|
---|
[18d4dbd] | 423 | For the following example I am using the as of yet finished exception system.
|
---|
| 424 |
|
---|
| 425 | trait exception(otype T) virtual() {
|
---|
| 426 | char const * what(T & this);
|
---|
| 427 | }
|
---|
| 428 |
|
---|
| 429 | trait io_error(otype T) virtual(exception) {
|
---|
| 430 | FILE * which_file(T & this);
|
---|
| 431 | }
|
---|
| 432 |
|
---|
| 433 | struct eof_error(otype T) virtual(io_error) {
|
---|
| 434 | FILE * file;
|
---|
| 435 | }
|
---|
| 436 |
|
---|
| 437 | char const * what(eof_error &) {
|
---|
| 438 | return "Tried to read from an empty file.";
|
---|
| 439 | }
|
---|
| 440 |
|
---|
| 441 | FILE * which_file(eof_error & this) {
|
---|
| 442 | return eof_error.file;
|
---|
| 443 | }
|
---|
| 444 |
|
---|
| 445 | bool handleIoError(exception * exc) {
|
---|
| 446 | io_error * error = (virtual io_error *)exc;
|
---|
| 447 | if (NULL == error) {
|
---|
| 448 | return false;
|
---|
| 449 | }
|
---|
| 450 | ...
|
---|
| 451 | return true;
|
---|
| 452 | }
|
---|
| 453 |
|
---|
| 454 | ### Extension: Implicate Virtual Cast Target
|
---|
| 455 | This is a small extension, even in the example above `io_error *` is repeated
|
---|
| 456 | in the cast and the variable being assigned to. Using return type inference
|
---|
| 457 | would allow the second type to be skipped in cases it is clear what type is
|
---|
| 458 | being checked against.
|
---|
| 459 |
|
---|
| 460 | The line then becomes:
|
---|
| 461 |
|
---|
| 462 | io_error * error = (virtual)exc;
|
---|
[07ac6d0] | 463 |
|
---|
[881f590] | 464 | #### Sample Implementation
|
---|
| 465 | This cast implementation assumes a type id layout similar to the one given
|
---|
| 466 | above. Also this code is definitely in the underlying C. Functions that give
|
---|
| 467 | this functionality could exist in the standard library but these are meant to
|
---|
| 468 | be produced by code translation of the virtual cast.
|
---|
| 469 |
|
---|
| 470 | bool is_in_subtree(typeid const * root, typeid const * id) {
|
---|
| 471 | if (root == id) {
|
---|
| 472 | return true
|
---|
| 473 | } else if (NULL == id->parent) {
|
---|
| 474 | return false;
|
---|
| 475 | } else {
|
---|
| 476 | return is_in_subtree(root, id->parent);
|
---|
| 477 | }
|
---|
| 478 | }
|
---|
| 479 |
|
---|
| 480 | void * virtual_cast(typeid const * target, void * value) {
|
---|
| 481 | return is_in_subtree(target, *(typeid const **)value) ? value : NULL;
|
---|
| 482 | }
|
---|
| 483 |
|
---|
| 484 | The virtual cast function might have to be wrapped with some casts to make it
|
---|
| 485 | compile without warning.
|
---|
| 486 |
|
---|
| 487 | For the implicate target type we may be able to lean on the type resolution
|
---|
| 488 | system that already exists. If the casting to ancestor type is built into
|
---|
| 489 | the resolution then the impicate target could be decided by picking an
|
---|
| 490 | overload, generated for each hierarchial type (here io_error and its root
|
---|
| 491 | type exception).
|
---|
| 492 |
|
---|
| 493 | io_error * virtual_cast(exception * value) {
|
---|
| 494 | return virtual_cast(io_error_typeid, value);
|
---|
| 495 | }
|
---|
| 496 |
|
---|
[18d4dbd] | 497 | ### Extension: Inline vtables
|
---|
[24662ff] | 498 | Since the structures here are usually made to be turned into trait objects
|
---|
[18d4dbd] | 499 | it might be worth it to have fields in them to store the virtual table
|
---|
[07ac6d0] | 500 | pointer. This would have to be declared on the trait as an assertion (example:
|
---|
| 501 | `vtable;` or `T.vtable;`), but if it is the trait object could be a single
|
---|
| 502 | pointer.
|
---|
[24662ff] | 503 |
|
---|
[07ac6d0] | 504 | There are also three options for where the pointer to the vtable. It could be
|
---|
| 505 | anywhere, a fixed location for each trait or always at the front. For the per-
|
---|
[18d4dbd] | 506 | trait solution an extension to specify what it is (example `vtable[0];`) which
|
---|
[07ac6d0] | 507 | could also be used to combine it with others. So these options can be combined
|
---|
| 508 | to allow access to all three options.
|
---|
[24662ff] | 509 |
|
---|
[881f590] | 510 | The pointer to virtual table field on structures might implicately added (the
|
---|
| 511 | types have to declare they are a child here) or created with a declaration,
|
---|
| 512 | possibly like the one used to create the assertion.
|
---|
| 513 |
|
---|
[936d95c] | 514 | ### Extension: Associated Types Use
|
---|
| 515 | If the `associated_types.md` proposal is accepted the following trait could
|
---|
| 516 | be added:
|
---|
| 517 |
|
---|
| 518 | trait is_virtual(dtype T) {
|
---|
| 519 | dtype table;
|
---|
| 520 | // An example assertion:
|
---|
| 521 | const table & get_virtual_table(T &);
|
---|
| 522 | }
|
---|
| 523 |
|
---|
| 524 | There may be more assertions but there has to be at least one way to find
|
---|
| 525 | the (possibly default) virtual table. It is required to construct instances
|
---|
| 526 | of the type.
|
---|
| 527 |
|
---|
| 528 | Without the assotiated type it would look like this:
|
---|
| 529 |
|
---|
| 530 | trait is_virtual(dtype T, dtype table) {
|
---|
| 531 | const table & get_virtual_table(T &);
|
---|
| 532 | }
|
---|
| 533 |
|
---|
| 534 | Which is just a little bit longer to use but becomes more problematic if the
|
---|
| 535 | user has to explicately provide the table's name as it doesn't really have its
|
---|
| 536 | own type name. If it does it is probably mangled.
|
---|
| 537 |
|
---|
[24662ff] | 538 | ### Virtual Tables as Types
|
---|
[07ac6d0] | 539 | Here we consider encoding plus the implementation of functions on it to be a
|
---|
| 540 | type. Which is to say in the type hierarchy structures aren't concrete types
|
---|
| 541 | anymore, instead they are parent types to vtables, which combine the encoding
|
---|
| 542 | and implementation.
|
---|
[24662ff] | 543 |
|
---|
[881f590] | 544 | ### Question: Wrapping Structures
|
---|
| 545 | One issue is what to do with concrete types at the base of the type tree.
|
---|
| 546 | When we are working with the concrete type generally it would like them to be
|
---|
| 547 | regular structures with direct calls. On the other hand for interactions with
|
---|
| 548 | other types in the hierarchy it is more convenent for the type already to be
|
---|
| 549 | cast.
|
---|
| 550 |
|
---|
| 551 | Which of these two should we use? Should we support both and if so how do we
|
---|
| 552 | choose which one is being used at any given time.
|
---|
| 553 |
|
---|
| 554 | On a related note I have been using pointers two trait types here, as that
|
---|
| 555 | is how many existing languages handle it. However the generic objects might
|
---|
| 556 | be only one or two pointers wide passing the objects as a whole would not
|
---|
| 557 | be very expensive and all operations on the generic objects probably have
|
---|
| 558 | to be defined anyways.
|
---|
| 559 |
|
---|
[24662ff] | 560 | Resolution Scope
|
---|
| 561 | ----------------
|
---|
| 562 |
|
---|
| 563 | What is the scope of a resolution? When are the functions in a vtable decided
|
---|
| 564 | and how broadly is this applied?
|
---|
| 565 |
|
---|
| 566 | ### Type Level:
|
---|
| 567 | Each structure has a single resolution for all of the functions in the
|
---|
| 568 | virtual trait. This is how many languages that implement this or similar
|
---|
| 569 | features do it.
|
---|
| 570 |
|
---|
| 571 | The main thing CFA would need to do it this way is some single point where
|
---|
[1b94115] | 572 | the type declaration, including the functions that satisfy the trait, are
|
---|
[24662ff] | 573 | all defined. Currently there are many points where this can happen, not all
|
---|
[18d4dbd] | 574 | of them have the same definitions and no way to select one over the other.
|
---|
[24662ff] | 575 |
|
---|
[07ac6d0] | 576 | Some syntax would have to be added to specify the resolution point. To ensure
|
---|
| 577 | a single instance there may have to be two variants, one forward declaration
|
---|
| 578 | and one to create the instance. With some compiler magic the forward
|
---|
| 579 | declaration maybe enough.
|
---|
| 580 |
|
---|
| 581 | extern trait combiner(struct summation) vtable;
|
---|
| 582 | trait combiner(struct summation) vtable;
|
---|
| 583 |
|
---|
| 584 | Or (with the same variants):
|
---|
| 585 |
|
---|
| 586 | vtable combiner(struct summation);
|
---|
| 587 |
|
---|
| 588 | The extern variant promises that the vtable will exist while the normal one
|
---|
| 589 | is where the resolution actually happens.
|
---|
[24662ff] | 590 |
|
---|
[1b94115] | 591 | ### Explicit Resolution Points:
|
---|
| 592 | Slightly looser than the above, there are explicit points where the vtables
|
---|
[24662ff] | 593 | are resolved, but there is no limit on the number of resolution points that
|
---|
| 594 | might be provided. Each time a object is bound to a trait, one of the
|
---|
[1b94115] | 595 | resolutions is selected. This might be the most flexible option.
|
---|
[24662ff] | 596 |
|
---|
| 597 | An syntax would have to be provided as above. There may also be the option
|
---|
| 598 | to name resolution points so that you can choose between them. This also
|
---|
[1b94115] | 599 | could come with the ability to forward declare them.
|
---|
[24662ff] | 600 |
|
---|
| 601 | Especially if they are not named, these resolution points should be able to
|
---|
| 602 | appear in functions, where the scoping rules can be used to select one.
|
---|
| 603 | However this also means that stack-allocated functions can end up in the
|
---|
| 604 | vtable.
|
---|
| 605 |
|
---|
[07ac6d0] | 606 | extern trait combiner(struct summation) vtable sum;
|
---|
| 607 | trait combiner(struct summation) vtable sum;
|
---|
| 608 |
|
---|
| 609 | extern trait combiner(struct summation) vtable sum default;
|
---|
| 610 | trait combiner(struct summation) vtable sum default;
|
---|
| 611 |
|
---|
| 612 | The extern difference is the same before. The name (sum in the samples) is
|
---|
| 613 | used at the binding site to say which one is picked. The default keyword can
|
---|
| 614 | be used in only some of the declarations.
|
---|
| 615 |
|
---|
[fbfd97bd] | 616 | trait combiner fee = {summation_instance, sum};
|
---|
[07ac6d0] | 617 | trait combiner foe = summation_instance;
|
---|
| 618 |
|
---|
| 619 | (I am not really happy about this syntax, but it kind of works.)
|
---|
| 620 | The object being bound is required. The name of the vtable is optional if
|
---|
| 621 | there is exactly one vtable name marked with default.
|
---|
| 622 |
|
---|
| 623 | These could also be placed inside functions. In which case both the name and
|
---|
[18d4dbd] | 624 | the default keyword might be optional. If the name is omitted in an assignment
|
---|
| 625 | the closest vtable is chosen (returning to the global default rule if no
|
---|
| 626 | appropriate local vtable is in scope).
|
---|
[07ac6d0] | 627 |
|
---|
[24662ff] | 628 | ### Site Based Resolution:
|
---|
| 629 | Every place in code where the binding of a vtable to an object occurs has
|
---|
| 630 | its own resolution. Syntax-wise this is the simplest as it should be able
|
---|
| 631 | to use just the existing declarations and the conversion to trait object.
|
---|
[1b94115] | 632 | It also is very close to the current polymorphic resolution rules.
|
---|
[24662ff] | 633 |
|
---|
[1b94115] | 634 | This works as the explicit resolution points except the resolution points
|
---|
| 635 | are implicit and their would be no selection of which resolution to use. The
|
---|
[24662ff] | 636 | closest (current) resolution is always selected.
|
---|
| 637 |
|
---|
[1b94115] | 638 | This could easily lead to an explosion of vtables as it has the most fine
|
---|
[24662ff] | 639 | grained resolution the number of bindings in a single scope (that produces
|
---|
| 640 | the same binding) could be quite high. Merging identical vtables might help
|
---|
| 641 | reduce that.
|
---|
| 642 |
|
---|
| 643 | Vtable Lifetime Issues
|
---|
| 644 | ----------------------
|
---|
| 645 |
|
---|
| 646 | Vtables interact badly with the thunk issue. Conceptually vtables are static
|
---|
[1b94115] | 647 | like type/function data they carry, as those decisions are made by the
|
---|
[24662ff] | 648 | resolver at compile time.
|
---|
| 649 |
|
---|
| 650 | Stack allocated functions interact badly with this because they are not
|
---|
[1b94115] | 651 | static. There are several ways to try to resolve this, however without a
|
---|
[881f590] | 652 | general solution most can keep vtables from making the existing thunk problem
|
---|
| 653 | worse, they don't do anything to solve it.
|
---|
[24662ff] | 654 |
|
---|
| 655 | Filling in some fields of a static vtable could cause issues on a recursive
|
---|
| 656 | call. And then we are still limited by the lifetime of the stack functions, as
|
---|
| 657 | the vtable with stale pointers is still a problem.
|
---|
| 658 |
|
---|
| 659 | Dynamically allocated vtables introduces memory management overhead and
|
---|
[1b94115] | 660 | requires some way to differentiate between dynamic and statically allocated
|
---|
[24662ff] | 661 | tables. The stale function pointer problem continues unless those becomes
|
---|
| 662 | dynamically allocated as well which gives us the same costs again.
|
---|
| 663 |
|
---|
| 664 | Stack allocating the vtable seems like the best issue. The vtable's lifetime
|
---|
| 665 | is now the limiting factor but it should be effectively the same as the
|
---|
| 666 | shortest lifetime of a function assigned to it. However this still limits the
|
---|
[1b94115] | 667 | lifetime "implicitly" and returns to the original problem with thunks.
|
---|
[881f590] | 668 |
|
---|
| 669 | Odds And Ends
|
---|
| 670 | -------------
|
---|
| 671 |
|
---|
| 672 | In addition to the main design there are a few extras that should be
|
---|
| 673 | considered. They are not part of the core design but make the new uses fully
|
---|
| 674 | featured.
|
---|
| 675 |
|
---|
| 676 | ### Extension: Parent-Child Assertion
|
---|
| 677 | For hierarchy types in regular traits, generic functions or generic structures
|
---|
| 678 | we may want to be able to check parent-child relationships between two types
|
---|
| 679 | given. For this we might have to add another primitive assertion. It would
|
---|
| 680 | have the following form if declared in code:
|
---|
| 681 |
|
---|
| 682 | trait is_parent_child(dtype Parent, dtype Child) { <built-in magic> }
|
---|
| 683 |
|
---|
| 684 | This assertion is satified if Parent is an ancestor of Child in a hierarchy.
|
---|
| 685 | In other words Child can be statically cast to Parent. The cast from Parent
|
---|
| 686 | to child would be dynamically checked as usual.
|
---|
| 687 |
|
---|
| 688 | However in this form there are two concerns. The first that Parent will
|
---|
| 689 | usually be consistent for a given use, it will not be a variable. Second is
|
---|
| 690 | that we may also need the assertion functions. To do any casting/conversions
|
---|
| 691 | anyways.
|
---|
| 692 | TODO: Talk about when we wrap a concrete type and how that leads to "may".
|
---|
| 693 |
|
---|
| 694 | To this end it may be better that the parent trait combines the usual
|
---|
| 695 | assertions plus this new primitive assertion. There may or may not be use
|
---|
| 696 | cases for accessing just one half and providing easy access to them may be
|
---|
| 697 | required depending on how that turns out.
|
---|
| 698 |
|
---|
| 699 | trait Parent(dtype T | interface(T)) virtual(<grand-parent?>) { }
|
---|
| 700 |
|
---|
| 701 | ### Extension: sizeof Compatablity
|
---|
| 702 | Trait types are always sized, it may even be a fixed size like how pointers
|
---|
| 703 | have the same size regardless of what they point at. However their contents
|
---|
| 704 | may or may not be of a known size (if the `sized(...)` assertion is used).
|
---|
| 705 |
|
---|
| 706 | Currently there is no way to access this information. If it is needed a
|
---|
| 707 | special syntax would have to be added. Here a special case of `sizeof` is
|
---|
| 708 | used.
|
---|
| 709 |
|
---|
| 710 | struct line aLine;
|
---|
| 711 | trait drawable widget = aLine;
|
---|
| 712 |
|
---|
| 713 | size_t x = sizeof(widget);
|
---|
| 714 | size_t y = sizeof(trait drawable);
|
---|
| 715 |
|
---|
| 716 | As usual `y`, size of the type, is the size of the local storage used to put
|
---|
| 717 | the value into. The other case `x` checks the saved stored value in the
|
---|
| 718 | virtual table and returns that.
|
---|