Changeset 33218c6 for doc/proposals


Ignore:
Timestamp:
Jul 26, 2017, 12:19:41 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
b947fb2
Parents:
e0a653d (diff), ea91c42 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/proposals/virtual.txt

    re0a653d r33218c6  
    11Proposal for virtual functionality
     2
     3There are two types of virtual inheritance in this proposal, relaxed
     4(implicit) and strict (explicit). Relaxed is the simpler case that uses the
     5existing trait system with the addition of trait references and vtables.
     6Strict adds some constraints and requires some additional notation but allows
     7for down-casting.
     8
     9Relaxed Virtual Inheritance:
    210
    311Imagine the following code :
     
    2028void draw(line*);
    2129
    22 While all the members of this simple UI support drawing creating a UI that easily
    23 supports both these UI requires some tedious boiler-plate code :
     30While all the members of this simple UI support drawing, creating a UI that
     31easily supports both these UI requires some tedious boiler-plate code:
    2432
    2533enum type_t { text, line };
     
    4149}
    4250
    43 While this code will work as indented, adding any new widgets or any new widget behaviors
    44 requires changing existing code to add the desired functionality. To ease this maintenance
    45 effort required CFA introduces the concept of dynamic types, in a manner similar to C++.
    46 
    47 A simple usage of dynamic type with the previous example would look like :
    48 
    49 drawable* objects[10];
     51While this code will work as implemented, adding any new widgets or any new
     52widget behaviors requires changing existing code to add the desired
     53functionality. To ease this maintenance effort required CFA introduces the
     54concept of trait references.
     55
     56Using trait references to implement the above gives the following :
     57
     58trait drawable objects[10];
    5059fill_objects(objects);
    5160
    5261while(running) {
    53       for(drawable* object : objects) {
     62      for(drawable object : objects) {
    5463            draw(object);
    5564      }
    5665}
    5766
    58 However, this is not currently do-able in the current CFA and furthermore is not
    59 possible to implement statically. Therefore we need to add a new feature to handle
    60 having dynamic types like this (That is types that are found dynamically not types
    61 that change dynamically).
    62 
    63 C++ uses inheritance and virtual functions to find the
    64 desired type dynamically. CFA takes inspiration from this solution.
    65 
    66 What we really want to do is express the fact that calling draw() on a object
    67 should find the dynamic type of the parameter before calling the routine, much like the
    68 hand written example given above. We can express this by adding the virtual keyword on
    69 the parameter of the constraints on our trait:
     67The keyword trait is optional (by the same rules as the struct keyword). This
     68is not currently supported in CFA and the lookup is not possible to implement
     69statically. Therefore we need to add a new feature to handle having dynamic
     70lookups like this.
     71
     72What we really want to do is express the fact that calling draw() on a trait
     73reference should find the underlying type of the given parameter and find how
     74it implements the routine, as in the example with the enumeration and union.
     75
     76For instance specifying that the drawable trait reference looks up the type
     77of the first argument to find the implementation would be :
    7078
    7179trait drawable(otype T) {
     
    7381};
    7482
    75 This expresses the idea that drawable is similar to an abstract base class in C++ and
    76 also gives meaning to trying to take a pointer of drawable. That is anything that can
    77 be cast to a drawable pointer has the necessary information to call the draw routine on
    78 that type. Before that drawable was only a abstract type while now it also points to a
    79 piece of storage which specify which behavior the object will have at run time.
    80 
    81 This storage needs to be allocate somewhere. C++ just adds an invisible pointer at
    82 the beginning of the struct but we can do something more explicit for users, actually
    83 have a visible special field :
    84 
    85 struct text {
    86       char* text;
    87       vtable drawable;
    88 };
    89 
    90 struct line{
    91       vtable drawable;
    92       vec2 start;
    93       vec2 end;
    94 };
    95 
    96 With these semantics, adding a "vtable drawable" means that text pointers and line pointers are now
    97 convertible to drawable pointers. This conversion will not necessarily be a type only change however, indeed,
    98 the drawable pointer will point to the field "vtable drawable" not the head of the struct. However, since all
    99 the types are known at compile time, converting pointers becomes a simple offset operations.
    100 
    101 The vtable field contains a pointer to a vtable which contains all the information needed for the caller
    102 to find the function pointer of the desired behavior.
    103 
    104 One of the limitations of this design is that it does not support double dispatching, which
    105 concretely means traits cannot have routines with more than one virtual parameter. This design
    106 would have many ambiguities if it did support multiple virtual parameter. A futher limitation is
    107 that traits over more than one type cannot have vtables meaningfully defined for them, as the
    108 particular vtable to use would be a function of the other type(s) the trait is defined over.
    109 
    110 It is worth noting that the function pointers in these vtables are bound at object construction, rather than
    111 function call-site, as in Cforall's existing polymorphic functions. As such, it is possible that two objects
    112 with the same static type would have a different vtable (consider what happens if draw(line*) is overridden
    113 between the definitions of two line objects). Given that the virtual drawable* erases static types though,
    114 this should not be confusing in practice. A more distressing possibility is that of creating an object that
    115 outlives the scope of one of the functions in its vtable. This is certainly a possible bug, but it is of a
    116 type that C programmers are familiar with, and should be able to avoid by the usual methods.
    117 
    118 Extensibility.
    119 
    120 One of the obvious critics of this implementation is that it lacks extensibility for classes
    121 that cannot be modified (ex: Linux C headers). However this solution can be extended to
    122 allow more extensibility by adding "Fat pointers".
    123 
    124 Indeed, users could already "solve" this issue by writing their own fat pointers as such:
    125 
    126 trait MyContext(otype T) {
    127       void* get_stack(virtual T*)
    128 };
    129 
    130 void* get_stack(ucontext_t *context);
    131 
    132 struct fat_ucontext_t {
    133       vtable MyContext;
    134       ucontext_t *context;
    135 }
    136 
    137 //Tedious forwarding routine
    138 void* get_stack(fat_ucontext_t *ptr) {
    139       return get_stack(ptr->context);
    140 }
    141 
    142 However, users would have to write all the virtual methods they want to override and make
    143 them all simply forward to the existing method that takes the corresponding POCO(Plain Old C Object).
    144 
    145 The alternative we propose is to use language level fat pointers :
    146 
    147 trait MyContext(otype T) {
    148       void* get_stack(virtual T*)
    149 };
    150 
    151 void* get_stack(ucontext_t *context);
    152 
    153 //The type vptr(ucontext_t) all
    154 vptr(ucontext_t) context;
    155 
    156 These behave exactly as the previous example but all the forwarding routines are automatically generated.
    157 
    158 Bikeshedding.
    159 
    160 It may be desirable to add fewer new keywords than discussed in this proposal; it is possible that "virtual"
    161 could replace both "vtable" and "vptr" above with unambiguous contextual meaning. However, for purposes of
    162 clarity in the design discussion it is beneficial to keep the keywords for separate concepts distinct.
    163 
     83This could be implied in simple cases like this one (single parameter on the
     84trait and single generic parameter on the function). In more complex cases it
     85would have to be explicitly given, or a strong convention would have to be
     86enforced (e.g. implementation of trait functions is always drawn from the
     87first polymorphic parameter).
     88
     89Once a function in a trait has been marked as virtual it defines a new
     90function that takes in that trait's reference and then dynamically calls the
     91underlying type implementation. Hence a trait reference becomes a kind of
     92abstract type, cannot be directly instantiated but can still be used.
     93
     94One of the limitations of this design is that it does not support double
     95dispatching, which concretely means traits cannot have routines with more than
     96one virtual parameter. The program must have a single table to look up the
     97function on. Using trait references with traits with more than one parameter
     98is also restricted, initially forbidden, see extension.
     99
     100Extension: Multi-parameter Virtual Traits:
     101
     102This implementation can be extended to traits with multiple parameters if
     103one is called out as being the virtual trait. For example :
     104
     105trait iterator(otype T, dtype Item) {
     106        Maybe(Item) next(virtual T *);
     107}
     108
     109iterator(int) generators[10];
     110
     111Which creates a collection of iterators that produce integers, regardless of
     112how those iterators are implemented. This may require a note that this trait
     113is virtual on T and not Item, but noting it on the functions may be enough.
     114
     115
     116Strict Virtual Inheritance:
     117
     118One powerful feature relaxed virtual does not support is the idea of down
     119casting. Once something has been converted into a trait reference there is
     120very little we can do to recover and of the type information, only the trait's
     121required function implementations are kept.
     122
     123To allow down casting strict virtual requires that all traits and structures
     124involved be organized into a tree. Each trait or struct must have a unique
     125position on this tree (no multiple inheritance).
     126
     127This is declared as follows :
     128
     129trait error(otype T) virtual {
     130        const char * msg(T *);
     131}
     132
     133trait io_error(otype T) virtual error {
     134        FILE * src(T *);
     135}
     136
     137struct eof_error virtual io_error {
     138        FILE * fd;
     139};
     140
     141So the trait error is the head of a new tree and io_error is a child of it.
     142
     143Also the parent trait is implicitly part of the assertions of the children,
     144so all children implement the same operations as the parent. By the unique
     145path down the tree, we can also uniquely order them so that a prefix of a
     146child's vtable has the same format as its parent's.
     147
     148This gives us an important extra feature, runtime checking of the parent-child
     149relationship with a C++ dynamic_cast like operation. Allowing checked
     150conversions from trait references to more particular references, which works
     151if the underlying type is, or is a child of, the new trait type.
     152
     153Extension: Multiple Parents
     154
     155Although each trait/struct must have a unique position on each tree, it could
     156have positions on multiple trees. All this requires is the ability to give
     157multiple parents, as here :
     158
     159trait region(otype T) virtual drawable, collider;
     160
     161The restriction being, the parents must come from different trees. This
     162object (and all of its children) can be cast to either tree. This is handled
     163by generating a separate vtable for each tree the structure is in.
     164
     165Extension: Multi-parameter Strict Virtual
     166
     167If a trait has multiple parameters then one must be called out to be the one
     168we generate separate vtables for, as in :
     169
     170trait example(otype T, otype U) virtual(T) ...
     171
     172This can generate a separate vtable for each U for which all the T+U
     173implementations are provided. These are then separate nodes in the tree (or
     174the root of different trees) as if each was created individually. Providing a
     175single unique instance of these nodes would be the most difficult aspect of
     176this extension, possibly intractable, though with sufficient hoisting and
     177link-once duplication it may be possible.
     178
     179Example:
     180
     181trait argument(otype T) virtual {
     182        char short_name(virtual T *);
     183        bool is_set(virtual T *);
     184};
     185
     186trait value_argument(otype T, otype U) virtual(T) argument {
     187        U get_value(virtual T *);
     188};
     189
     190Extension: Structural Inheritance
     191
     192Currently traits must be the internal nodes and structs the leaf nodes.
     193Structs could be made internal nodes as well, in which case the child structs
     194would likely structurally inherit the fields of their parents.
     195
     196
     197Storing the Virtual Lookup Table (vtable):
     198
     199We have so far been silent on how the vtable is created, stored and accessed.
     200
     201Creation happens at compile time. Function pointers are found by using the
     202same best match rules as elsewhere (additional rules for defaults from the
     203parent may or may not be required). For strict virtual this must happen at the
     204global scope and forbidding static functions, to ensure that a single unique
     205vtable is created. Similarly, there may have to be stricter matching rules
     206for the functions that go into the vtable, possibly requiring an exact match.
     207Relaxed virtual could relax both restrictions, if we allow different vtable
     208at different conversion (struct to trait reference) sites. If it is allowed
     209local functions being bound to a vtable could cause issues when they go out
     210of scope, however this should follow the lifetime rules most C programs
     211already follow implicitly.
     212
     213Most vtables should be stored statically, the only exception being some of
     214the relaxed vtables that could have local function pointers. These may be able
     215to be stack allocated. All vtables should be immutable and require no manual
     216cleanup.
     217
     218Access has two main options:
     219
     220The first is through the use of fat pointers, or a tuple of pointers. When the
     221object is converted to a trait reference, the pointers to its vtables are
     222stored along side it.
     223
     224This allows for compatibility with existing structures (such as those imported
     225from C) and is the default storage method unless a different one is given.
     226
     227The other is by inlining the vtable pointer as "intrusive vtables". This adds
     228a field to the structure to the vtable. The trait reference then has a single
     229pointer to this field, the vtable includes an offset to find the beginning of
     230the structure again.
     231
     232This is used if you specify a vtable field in the structure. If given in the
     233trait the vtable pointer in the trait reference can then become a single
     234pointer to the vtable field and use that to recover the original object
     235pointer as well as retrieve all operations.
     236
     237trait drawable(otype T) {
     238        vtable drawable;
     239};
     240
     241struct line {
     242        vtable drawable;
     243        vec2 start;
     244        vec2 end;
     245};
     246
     247This inline code allows trait references to be converted to plain pointers
     248(although they still must be called specially). The vtable field may just be
     249an opaque block of memory or it may allow user access to the vtable. If so
     250then there should be some way to retrieve the type of the vtable, which will be
     251autogenerated and often unique.
     252
     253
     254Keyword Usage:
     255
     256It may be desirable to add fewer new keywords than discussed in this proposal.
     257It is possible that "virtual" could replace both "vtable" above with
     258unambiguous contextual meaning. However, for purposes of clarity in the design
     259discussion it is beneficial to keep the keywords for separate concepts distinct.
     260
     261
     262Trait References and Operations:
     263
     264sizeof(drawable) will return the size of the trait object itself. However :
     265
     266line a_line;
     267drawable widget = a_line;
     268sizeof(widget);
     269
     270Will instead return the sizeof the underlying object, although the trait must
     271require that its implementation is sized for there to be a meaningful value
     272to return. You may also get the size of the trait reference with
     273
     274sizeof(&widget);
     275
     276Calling free on a trait reference will free the memory for the object. It will
     277leave the vtables alone, as those are (always?) statically allocated.
Note: See TracChangeset for help on using the changeset viewer.