Changeset 69bafd2 for doc/proposals/vtable.md

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:

• doc/proposals/vtable.md (modified) (11 diffs)

doc/proposals/vtable.md

@@ -1 +1 @@
 Proposal For Use of Virtual Tables
 ==================================
-
-This is an adaptation of the earlier virtual proposal, updating it with new
-ideas, re-framing it and laying out more design decisions. It should
-eventually replace the earlier proposal, but not all features and syntax have
-been converted to the new design.
 
 The basic concept of a virtual table (vtable) is the same here as in most
@@ -93 +88 @@
         }
     }
+
+With a more complete widget trait you could, for example, construct a UI tool
+kit that can declare containers that hold widgets without knowing about the
+widget types. Making it reasonable to extend the tool kit.
 
 The trait types can also be used in the types of assertions on traits as well.
@@ -244 +243 @@
 We would also like to implement hierarchical relations between types.
 
-    AstNode
-    |-ParseNode
-    | |-Declaration
-    | | |-DeclarationWithType
-    | | |-StructureDeclaration
-    | |-Statement
-    | | |-CompoundStatement
-    | |-Expression
-    |-Type
+    ast_node
+    |-expression_node
+    | |-operator_expression
+    |
+    |-statement_node
+    | |-goto_statement
+    |
+    |-declaration_node
+      |-using_declaration
+      |-variable_declaration
 
 Virtual tables by themselves are not quite enough to implement this system.
@@ -315 +315 @@
     }
 
+This system does not support multiple inheritance. The system could be
+extended to support it or a limited form (ex. you may have multiple parents
+but they may not have a common ancestor). However this proposal focuses just
+on using hierachy as organization. Other uses for reusable/genaric code or
+shared interfaces is left for other features of the language.
+
 ### Extension: Structural Inheritance
 An extension would be allow structures to be used as internal nodes on the
@@ -354 +360 @@
 solution but only works if we have exactly 1 vtable for each type. The second
 is to put a pointer to the type id in each vtable. This has more overhead but
-allows multiple vtables.
+allows multiple vtables per type.
 
     struct <trait>_vtable {
@@ -367 +373 @@
         // Trait dependent list of vtable members.
     };
+
+One important restriction is that only one instance of each typeid in memory.
+There is a ".gnu.linkonce" feature in the linker that might solve the issue.
 
 ### Virtual Casts
@@ -423 +432 @@
     io_error * error = (virtual)exc;
 
+#### Sample Implementation
+This cast implementation assumes a type id layout similar to the one given
+above. Also this code is definitely in the underlying C. Functions that give
+this functionality could exist in the standard library but these are meant to
+be produced by code translation of the virtual cast.
+
+    bool is_in_subtree(typeid const * root, typeid const * id) {
+        if (root == id) {
+            return true
+        } else if (NULL == id->parent) {
+            return false;
+        } else {
+            return is_in_subtree(root, id->parent);
+        }
+    }
+
+    void * virtual_cast(typeid const * target, void * value) {
+        return is_in_subtree(target, *(typeid const **)value) ? value : NULL;
+    }
+
+The virtual cast function might have to be wrapped with some casts to make it
+compile without warning.
+
+For the implicate target type we may be able to lean on the type resolution
+system that already exists. If the casting to ancestor type is built into
+the resolution then the impicate target could be decided by picking an
+overload, generated for each hierarchial type (here io_error and its root
+type exception).
+
+    io_error * virtual_cast(exception * value) {
+        return virtual_cast(io_error_typeid, value);
+    }
+
 ### Extension: Inline vtables
 Since the structures here are usually made to be turned into trait objects
@@ -436 +478 @@
 to allow access to all three options.
 
+The pointer to virtual table field on structures might implicately added (the
+types have to declare they are a child here) or created with a declaration,
+possibly like the one used to create the assertion.
+
 ### Virtual Tables as Types
 Here we consider encoding plus the implementation of functions on it to be a
@@ -442 +488 @@
 and implementation.
 
+### Question: Wrapping Structures
+One issue is what to do with concrete types at the base of the type tree.
+When we are working with the concrete type generally it would like them to be
+regular structures with direct calls. On the other hand for interactions with
+other types in the hierarchy it is more convenent for the type already to be
+cast.
+
+Which of these two should we use? Should we support both and if so how do we
+choose which one is being used at any given time.
+
+On a related note I have been using pointers two trait types here, as that
+is how many existing languages handle it. However the generic objects might
+be only one or two pointers wide passing the objects as a whole would not
+be very expensive and all operations on the generic objects probably have
+to be defined anyways.
+
 Resolution Scope
 ----------------
@@ -534 +596 @@
 Stack allocated functions interact badly with this because they are not
 static. There are several ways to try to resolve this, however without a
-general solution most can only buy time.
+general solution most can keep vtables from making the existing thunk problem
+worse, they don't do anything to solve it.
 
 Filling in some fields of a static vtable could cause issues on a recursive
@@ -549 +612 @@
 shortest lifetime of a function assigned to it. However this still limits the
 lifetime "implicitly" and returns to the original problem with thunks.
+
+Odds And Ends
+-------------
+
+In addition to the main design there are a few extras that should be
+considered. They are not part of the core design but make the new uses fully
+featured.
+
+### Extension: Parent-Child Assertion
+For hierarchy types in regular traits, generic functions or generic structures
+we may want to be able to check parent-child relationships between two types
+given. For this we might have to add another primitive assertion. It would
+have the following form if declared in code:
+
+    trait is_parent_child(dtype Parent, dtype Child) { <built-in magic> }
+
+This assertion is satified if Parent is an ancestor of Child in a hierarchy.
+In other words Child can be statically cast to Parent. The cast from Parent
+to child would be dynamically checked as usual.
+
+However in this form there are two concerns. The first that Parent will
+usually be consistent for a given use, it will not be a variable. Second is
+that we may also need the assertion functions. To do any casting/conversions
+anyways.
+TODO: Talk about when we wrap a concrete type and how that leads to "may".
+
+To this end it may be better that the parent trait combines the usual
+assertions plus this new primitive assertion. There may or may not be use
+cases for accessing just one half and providing easy access to them may be
+required depending on how that turns out.
+
+    trait Parent(dtype T | interface(T)) virtual(<grand-parent?>) { }
+
+### Extension: sizeof Compatablity
+Trait types are always sized, it may even be a fixed size like how pointers
+have the same size regardless of what they point at. However their contents
+may or may not be of a known size (if the `sized(...)` assertion is used).
+
+Currently there is no way to access this information. If it is needed a
+special syntax would have to be added. Here a special case of `sizeof` is
+used.
+
+    struct line aLine;
+    trait drawable widget = aLine;
+
+    size_t x = sizeof(widget);
+    size_t y = sizeof(trait drawable);
+
+As usual `y`, size of the type, is the size of the local storage used to put
+the value into. The other case `x` checks the saved stored value in the
+virtual table and returns that.