Ignore:
Timestamp:
May 15, 2019, 3:57:26 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
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:
3648d98
Parents:
9e1d485 (diff), be567e9 (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/vtable.md

    r9e1d485 r69bafd2  
    11Proposal For Use of Virtual Tables
    22==================================
    3 
    4 This is an adaptation of the earlier virtual proposal, updating it with new
    5 ideas, re-framing it and laying out more design decisions. It should
    6 eventually replace the earlier proposal, but not all features and syntax have
    7 been converted to the new design.
    83
    94The basic concept of a virtual table (vtable) is the same here as in most
     
    9388        }
    9489    }
     90
     91With a more complete widget trait you could, for example, construct a UI tool
     92kit that can declare containers that hold widgets without knowing about the
     93widget types. Making it reasonable to extend the tool kit.
    9594
    9695The trait types can also be used in the types of assertions on traits as well.
     
    244243We would also like to implement hierarchical relations between types.
    245244
    246     AstNode
    247     |-ParseNode
    248     | |-Declaration
    249     | | |-DeclarationWithType
    250     | | |-StructureDeclaration
    251     | |-Statement
    252     | | |-CompoundStatement
    253     | |-Expression
    254     |-Type
     245    ast_node
     246    |-expression_node
     247    | |-operator_expression
     248    |
     249    |-statement_node
     250    | |-goto_statement
     251    |
     252    |-declaration_node
     253      |-using_declaration
     254      |-variable_declaration
    255255
    256256Virtual tables by themselves are not quite enough to implement this system.
     
    315315    }
    316316
     317This system does not support multiple inheritance. The system could be
     318extended to support it or a limited form (ex. you may have multiple parents
     319but they may not have a common ancestor). However this proposal focuses just
     320on using hierachy as organization. Other uses for reusable/genaric code or
     321shared interfaces is left for other features of the language.
     322
    317323### Extension: Structural Inheritance
    318324An extension would be allow structures to be used as internal nodes on the
     
    354360solution but only works if we have exactly 1 vtable for each type. The second
    355361is to put a pointer to the type id in each vtable. This has more overhead but
    356 allows multiple vtables.
     362allows multiple vtables per type.
    357363
    358364    struct <trait>_vtable {
     
    367373        // Trait dependent list of vtable members.
    368374    };
     375
     376One important restriction is that only one instance of each typeid in memory.
     377There is a ".gnu.linkonce" feature in the linker that might solve the issue.
    369378
    370379### Virtual Casts
     
    423432    io_error * error = (virtual)exc;
    424433
     434#### Sample Implementation
     435This cast implementation assumes a type id layout similar to the one given
     436above. Also this code is definitely in the underlying C. Functions that give
     437this functionality could exist in the standard library but these are meant to
     438be produced by code translation of the virtual cast.
     439
     440    bool is_in_subtree(typeid const * root, typeid const * id) {
     441        if (root == id) {
     442            return true
     443        } else if (NULL == id->parent) {
     444            return false;
     445        } else {
     446            return is_in_subtree(root, id->parent);
     447        }
     448    }
     449
     450    void * virtual_cast(typeid const * target, void * value) {
     451        return is_in_subtree(target, *(typeid const **)value) ? value : NULL;
     452    }
     453
     454The virtual cast function might have to be wrapped with some casts to make it
     455compile without warning.
     456
     457For the implicate target type we may be able to lean on the type resolution
     458system that already exists. If the casting to ancestor type is built into
     459the resolution then the impicate target could be decided by picking an
     460overload, generated for each hierarchial type (here io_error and its root
     461type exception).
     462
     463    io_error * virtual_cast(exception * value) {
     464        return virtual_cast(io_error_typeid, value);
     465    }
     466
    425467### Extension: Inline vtables
    426468Since the structures here are usually made to be turned into trait objects
     
    436478to allow access to all three options.
    437479
     480The pointer to virtual table field on structures might implicately added (the
     481types have to declare they are a child here) or created with a declaration,
     482possibly like the one used to create the assertion.
     483
    438484### Virtual Tables as Types
    439485Here we consider encoding plus the implementation of functions on it to be a
     
    442488and implementation.
    443489
     490### Question: Wrapping Structures
     491One issue is what to do with concrete types at the base of the type tree.
     492When we are working with the concrete type generally it would like them to be
     493regular structures with direct calls. On the other hand for interactions with
     494other types in the hierarchy it is more convenent for the type already to be
     495cast.
     496
     497Which of these two should we use? Should we support both and if so how do we
     498choose which one is being used at any given time.
     499
     500On a related note I have been using pointers two trait types here, as that
     501is how many existing languages handle it. However the generic objects might
     502be only one or two pointers wide passing the objects as a whole would not
     503be very expensive and all operations on the generic objects probably have
     504to be defined anyways.
     505
    444506Resolution Scope
    445507----------------
     
    534596Stack allocated functions interact badly with this because they are not
    535597static. There are several ways to try to resolve this, however without a
    536 general solution most can only buy time.
     598general solution most can keep vtables from making the existing thunk problem
     599worse, they don't do anything to solve it.
    537600
    538601Filling in some fields of a static vtable could cause issues on a recursive
     
    549612shortest lifetime of a function assigned to it. However this still limits the
    550613lifetime "implicitly" and returns to the original problem with thunks.
     614
     615Odds And Ends
     616-------------
     617
     618In addition to the main design there are a few extras that should be
     619considered. They are not part of the core design but make the new uses fully
     620featured.
     621
     622### Extension: Parent-Child Assertion
     623For hierarchy types in regular traits, generic functions or generic structures
     624we may want to be able to check parent-child relationships between two types
     625given. For this we might have to add another primitive assertion. It would
     626have the following form if declared in code:
     627
     628    trait is_parent_child(dtype Parent, dtype Child) { <built-in magic> }
     629
     630This assertion is satified if Parent is an ancestor of Child in a hierarchy.
     631In other words Child can be statically cast to Parent. The cast from Parent
     632to child would be dynamically checked as usual.
     633
     634However in this form there are two concerns. The first that Parent will
     635usually be consistent for a given use, it will not be a variable. Second is
     636that we may also need the assertion functions. To do any casting/conversions
     637anyways.
     638TODO: Talk about when we wrap a concrete type and how that leads to "may".
     639
     640To this end it may be better that the parent trait combines the usual
     641assertions plus this new primitive assertion. There may or may not be use
     642cases for accessing just one half and providing easy access to them may be
     643required depending on how that turns out.
     644
     645    trait Parent(dtype T | interface(T)) virtual(<grand-parent?>) { }
     646
     647### Extension: sizeof Compatablity
     648Trait types are always sized, it may even be a fixed size like how pointers
     649have the same size regardless of what they point at. However their contents
     650may or may not be of a known size (if the `sized(...)` assertion is used).
     651
     652Currently there is no way to access this information. If it is needed a
     653special syntax would have to be added. Here a special case of `sizeof` is
     654used.
     655
     656    struct line aLine;
     657    trait drawable widget = aLine;
     658
     659    size_t x = sizeof(widget);
     660    size_t y = sizeof(trait drawable);
     661
     662As usual `y`, size of the type, is the size of the local storage used to put
     663the value into. The other case `x` checks the saved stored value in the
     664virtual table and returns that.
Note: See TracChangeset for help on using the changeset viewer.