Changeset 07ac6d0

Apr 9, 2019, 3:02:33 PM (5 years ago)
Andrew Beach <ajbeach@…>
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

Its rough, but I think I have all the content I need in the vtable proposal now.

1 edited


  • doc/proposals/

    re16797c r07ac6d0  
    1111should be able to store anything that goes into a trait.
     13I also include notes on a sample implementation, which primarly exists to show
     14there is a resonable implementation. The code samples for that are in a slight
     15psudo-code to help avoid name mangling and keeps some CFA features while they
     16would actually be writen in C.
    1318Trait Instances
    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.
    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.
     49For traits to be used this way they should meet two requirements. First they
     50should only have a single polymorphic type and each assertion should use that
     51type once as a parameter. Extentions may later loosen these requirements.
     53If a trait object is used it should generate a series of implicate functions
     54each of which implements one of the functions required by the trait. So for
     55combiner there is an implicate:
     57    void combine(trait combiner & this, int);
     59This function is the one actually called at the end
     61The main use case for trait objects is that they can be stored. They can be
     62passed into functions, but using the trait directly is prefred in this case.
     64    trait drawable(otype T) {
     65        void draw(Surface & to, T & draw);
     66        Rect(int) drawArea(T & draw);
     67    };
     69    struct UpdatingSurface {
     70        Surface * surface;
     71        vector(trait drawable) drawables;
     72    };
     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    }
     80Currently these traits are limited to 1 trait parameter and functions should
     81have exactly 1 parameter. We cannot abstract away pairs of types and still
     82pass them into normal functions, which take them seperately.
     84The second is required the because we need to get the vtable from somewhere.
     85If there are 0 trait objects than no vtable is avalible, if we have more than
     861 than the vtables give conflicting answers on what underlying function to
     87call. And even then the underlying type assumes a concrete type.
     89This loop can sort of be broken by using the trait object directly in the
     90signature. This has well defined meaning, but might not be useful.
     92    trait example(otype T) {
     93        bool test(T & this, trait example & that);
     94    }
     96#### Sample Implementation
     97A simple way to implement trait objects is by a pair of pointers. One to the
     98underlying object and one to the vtable.
     100    struct vtable_drawable {
     101        void (*draw)(Surface &, void *);
     102        Rect(int) (*drawArea)(void *);
     103    };
     105    struct drawable {
     106        void * object;
     107        vtable_drawable * vtable;
     108    };
     110The functions that run on the trait object would generally be generated using
     111the following pattern:
     113    void draw(Surface & surface, drawable & traitObj) {
     114        return traitObj.vtable->draw(surface, traitObj.object);
     115    }
     117There may have to be special cases for things like copy construction, that
     118might require a more sigificant wrapper. On the other hand moving could be
     119implemented by moving the pointers without any need to refer to the base
     122### Extention: Multiple Trait Parameters
     123Currently, this gives traits two independent uses. They use the same syntax,
     124except for limits boxable traits have, and yet don't really mix. The most
     125natural way to do this is to allow trait instances to pick one parameter
     126that they are generic over, the others they choose types to implement.
     128The two ways to do the selection, the first is do it at the trait definition.
     129Each trait picks out a single parameter which it can box (here the `virtual`
     130qualifier). When you create an instance of a trait object you provide
     131arguments like for a generic structure, but skip over the marked parameter.
     133    trait combiner(virtual otype T, otype Combined) {
     134        void combine(T &, Combined &);
     135    }
     137    trait combiner(int) int_combiner;
     139The second is to do it at the instaniation point. A placeholder (here the
     140keyword `virtual`) is used to explicately skip over the parameter that will be
     141abstracted away, with the same rules as above if it was the marked parameter.
     143    trait combiner(otype T, otype Combined) {
     144        void combine(T &, Combined &);
     145    };
     147    trait combiner(virtual, int) int_combiner;
     149Using both (first to set the default, second as a local override) would also
     150work, although might be exessively complicated.
     152This is useful in cases where you want to use a generic type, but leave part
     153of it open and store partially generic result. As a simple example
     155    trait folder(otype T, otype In, otype Out) {
     156        void fold(T & this, In);
     157        Out fold_result(T & this);
     158    }
     160Which allows you to fold values without putting them in a container. If they
     161are already in a container this is exessive, but if they are generated over
     162time this gives you a simple interface. This could for instance be used in
     163a profile, where T changes for each profiling statistic and you can plug in
     164multiple profilers for any run by adding them to an array.
    90203the pointer to it.
     205Exception Example:
     206(Also I'm not sure where I got these casing rules.)
     208    trait exception(otype T) virtual() {
     209        char const * what(T & this);
     210    }
     212    trait io_error(otype T) virtual(exception) {
     213        FILE * which_file(T & this);
     214    }
     216    struct eof_error(otype T) virtual(io_error) {
     217        FILE * file;
     218    }
     220    char const * what(eof_error &) {
     221        return "Tried to read from an empty file.";
     222    }
     224    FILE * which_file(eof_error & this) {
     225        return eof_error.file;
     226    }
     228Ast Example:
     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    }
     236    trait expression_node(otype T) virtual(ast_node) {
     237        Type eval_type(T const & this);
     238    }
     240    struct operator_expression virtual(expression_node) {
     241        enum operator_kind kind;
     242        trait expression_node rands[2];
     243    }
     245    trait statement_node(otype T) virtual(ast_node) {
     246        vector(Label) & get_labels(T & this);
     247    }
     249    struct goto_statement virtual(statement_node) {
     250        vector(Label) labels;
     251        Label target;
     252    }
     254    trait declaration_node(otype T) virtual(ast_node) {
     255        string name_of(T const & this);
     256        Type type_of(T const & this);
     257    }
     259    struct using_declaration virtual(declaration_node) {
     260        string new_type;
     261        Type old_type;
     262    }
     264    struct variable_declaration virtual(declaration_node) {
     265        string name;
     266        Type type;
     267    }
     269#### Sample Implementation
     270The type id may be as little as:
     272    struct typeid {
     273        struct typeid const * const parent;
     274    };
     276Some linker magic would have to be used to ensure exactly one copy of each
     277structure for each type exists in memory. There seem to be spectial once
     278sections that support this and it should be easier than generating unique
     279ids across compilation units.
     281The structure could be extended to contain any additional type information.
     283There are two general designs for vtables with type ids. The first is to put
     284the type id at the top of the vtable, this is the most compact and efficient
     285solution but only works if we have exactly 1 vtable for each type. The second
     286is to put a pointer to the type id in each vtable. This has more overhead but
     287allows multiple vtables.
     289    struct <trait>_vtable {
     290        struct typeid const id;
     292        // Trait dependent list of vtable members.
     293    };
     295    struct <trait>_vtable {
     296        struct typeid const * const id;
     298        // Trait dependent list of vtable members.
     299    };
     301### Virtual Casts
     302To convert from a pointer to a type higher on the hierarchy to one lower on
     303the hierarchy a check is used to make sure that the underlying type is also
     304of that lower type.
     306The proposed syntax for this is:
     308    trait SubType * new_value = (virtual trait SubType *)super_type;
     310It will return the same pointer if it does point to the subtype and null if
     311it does not, doing the check and conversion in one operation.
    92313### Inline vtables
    93314Since the structures here are usually made to be turned into trait objects
    94315it 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.
    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.
     316pointer. 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
     320There are also three options for where the pointer to the vtable. It could be
     321anywhere, a fixed location for each trait or always at the front. For the per-
     322trait solution an extention to specify what it is (example `vtable[0];`) which
     323could also be used to combine it with others. So these options can be combined
     324to allow access to all three options.
    102326### Virtual Tables as Types
    103 Here we consider encoding plus the implementation of functions on it. Which
    104 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.
     327Here we consider encoding plus the implementation of functions on it to be a
     328type. Which is to say in the type hierarchy structures aren't concrete types
     329anymore, instead they are parent types to vtables, which combine the encoding
     330and implementation.
    108332Resolution Scope
    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.
     349Some syntax would have to be added to specify the resolution point. To ensure
     350a single instance there may have to be two variants, one forward declaration
     351and one to create the instance. With some compiler magic the forward
     352declaration maybe enough.
     354    extern trait combiner(struct summation) vtable;
     355    trait combiner(struct summation) vtable;
     357Or (with the same variants):
     359    vtable combiner(struct summation);
     361The extern variant promises that the vtable will exist while the normal one
     362is where the resolution actually happens.
    128364### Explicit Resolution Points:
     379    extern trait combiner(struct summation) vtable sum;
     380    trait combiner(struct summation) vtable sum;
     382    extern trait combiner(struct summation) vtable sum default;
     383    trait combiner(struct summation) vtable sum default;
     385The extern difference is the same before. The name (sum in the samples) is
     386used at the binding site to say which one is picked. The default keyword can
     387be used in only some of the declarations.
     389    trait combiner fee = (summation_instance, sum);
     390    trait combiner foe = summation_instance;
     392(I am not really happy about this syntax, but it kind of works.)
     393The object being bound is required. The name of the vtable is optional if
     394there is exactly one vtable name marked with default.
     396These could also be placed inside functions. In which case both the name and
     397the default keyword might be optional. If the name is ommited in an assignment
     398the closest vtable is choosen (returning to the global default rule if no
     399approprate local vtable is in scope).
    143401### Site Based Resolution:
    144402Every place in code where the binding of a vtable to an object occurs has
Note: See TracChangeset for help on using the changeset viewer.