Additional Support for Generics

[kyleheadley]

This issue tracks multiple steps of inferring and constraining type variables, aka generics.

• Limited Support for user-defined generics
• Call site type variable inference
• 1. Bugfix: "Unrolled" type variables need to be "rerolled" or otherwise have their number of pointers tracked
• 2. Rewrite malloc, etc. as generic functions
  • a. Store type variable data in constraint variables
  • b. Rewrite void* as T* with _Itype_for_any(T) annotation on functions
• 3. Add constraints based on type variables
• 4. Extend to multiple type variables per function by analyzing call site consistency
• 5. Generalize type variable depth, ie T**
• 6. Consider unsafe and itype generics
• 7. Research __BoundsInterface that may be present on checkedc type variables and incorporate it.

Existing code allows users to write generic functions with multiple type variables, as long as function parameters are each a single pointer to the type. It will also add type arguments to call sites.

1. There is a bug that adds pointers to generic types when these are compared to other types. The comparison may not be necessary (stop it at a generic base type as success), but may be more important in further steps here. Include a count of a number of pointers in constraint variable so that later comparisons or rewriting can be consistent with the intended type. The pointers are added in ConstraintVariables.cpp::getAtom()

2. Split into two parts for convenience.

   a) Next step is to rewrite functions defined with void* parameters. This will require creation of type variables, so theefunction and constraint variables need to store them. Luckily, code only relies on per-call site type variable indexes, so a function can store the number of type variables, and a variable can store an index. Existing code that looks up these indexes, especially Utils.cpp::getTypeVariableType() needs to be moved into the constraint variable creation stage.

   b) To allow rewriting, we need to check for void* parameters and returns in functionCVs. These can be converted into T*. This can be done by changing the GenericIndex and adding code to stop rewriting at T, similar to the typedef code. Or by creating and inserting a TypeDefType with a TypeVariableType inside to use the typedef code as is happening currently. The rewriter can then check for changes and insert the new types. Parameters should work with little to no changes, but Itype_for_any(T) has never yet been inserted into code.

3. We need generic index constrain propagation for the more useful aspects of generic inference. Since 3C is not set up for this, it means new atoms or new constraint resolution code. Research the possibilities and implement a way to rewrite void* decls as _Ptr<T> within a function that uses the variable appropriately.

4. Next we infer the number of type variables of a generic function by creating and analyzing call site constraints. Current code checks consistency of arguments against their type variable index, but here we take it further and assume each inconsistency is a new type variable (for generated code). TypeVariableAnaysis.cpp::updateEntry() and its callers will need to be rewritten and be able to update function and variable constraints.

5. So far all code assumes that generic constraint variables are of the form T*. We need to generalize to any number of pointers to support all code. This will complicate most of the code written for the above steps. In particular, loops will be needed to find pointer depth. Code used to work with typedef level could be copied or reused for this purpose. There is also a bug where the solved generic variable in one callsite interferes with another. Handling this step properly should solve the bug, which may be a good place to start. See type_params_xfail1.c

6. Generics are only rewritten if all params are safe. This means we'll always have _Ptr<T> i and never T* i : Itype(_Ptr<T>). It's uncertain if this capability will be of much use.

7. Internally to CheckedC, type variables have a __BoundsInterface. This is likely an advanced interface for checking bounds of arrays deeper within the type variable. Research what it really is, why it may be important, and implement it.

Additionally, constraint variables used as a function's internal parameters may not need to be marked as generic. After a pending pull request they will be independent of the external parameters and may only need to be created with a base type T to be used properly. Reevaluate after the code is included.

[kyleheadley]

Bugfix #361 Solves number 1 above. Typedef info was used to "reroll" the type, preventing rewriting from accessing atoms beyond the generic var. There is still interference when there are multiple uses of a generic function, demonstrated in "type_params_xfail1.c" and associated "type_params.c" regression tests.

This could be solved by copying (or reusing) most of the typedef level code but applying it where generics are accessed. This has been added to step 4.

[kyleheadley]

Pull request #372 adds type variable index count to constraint variables. They can now be changed and later look-ups will read the new numbers. Work on this issue is paused, so I'm splitting number 2 in the opening post into 2a and 2b to track current progress.

[kyleheadley]

PR #639 adds support for rewriting single-void functions as generic. This is done only if the parameter is not wild by other means, and so there are no unsafe or itype generics. These are now downgraded to something we'll consider later. We also need to upgrade constraint propagation, as it is now recognized as necessary for wrappers around malloc. I've updated the opening post to reflect these changes.