-
Notifications
You must be signed in to change notification settings - Fork 570
An alternate approach to generics support #1272
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Merged
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This commit updates the run.go to do correct flag parsing and lists all failing test cases as known failures.
The library scans type-checked Go AST and incrementally discovers instantiations of generic types and functions in it. Each instantiation is recorded with the origin object and a set of type arguments. The scan is seeded from two sources: - Any Instances that have been added to the working InstanceSet externally (for example, from references by other packages). - Any instances that are discovered within the non-generic code in the package itself. The discovery proceeds to search for instances in the generic code by traversing its AST for each set of previously discovered type arguments. In that scan, whenever a type is defined in terms of a type param, we map it onto a concrete type given the current set of type arguments. For now, the library is not fully ready to handle generic instances that come across the package boundaries, that will come later. The type mapping logic turns out to be fairly complex, so instead of reimplementing it I decided to cheat and "borrow" it from the go/types package via a go:linkname directive. I didn't want to vendor it because I expect it would be changing fairly regularly in future. We shall see whether this was a wise choice. This commit also includes a couple of supporting refactorings: - Moved the symbols logic used by go:linkname to a separate package, since it turned out to be useful for generics as well. - Added a testingx helper library with a generic `Must(t)` helper to make trivial error handling in tests less verbose.
When translating a function with type params, we translate it for each discovered combination of type arguments. Like regular functions, generic ones are assigned a variable name, but instead of representing the function directly, it is mapping from instance keys to type-specific translation of the function. The key is a string that is derived from type arguments and is guaranteed to be different for different set of type arguments. To make this possible, I've make following changes: - For functions we now emit two decls, one that reserves the variable name, and one per instantiation that generates function body. This is necessary to make sure variable containing generic functions is initialized once. - Decl struct now has a new RefExpr field that contains a JS expression referencing the object the decl represents. This is necessary because the variable name that was previously used for linkname purposes is now stored in a different decl as explained above. - Mapping from object names to variable names is now stored in funcContext. This is necessary since each generic function is translated several times and we need to create a new local variable for objects within it each time. - Added handling of ast.IndexExpr and ast.IndexListExpr in the compiler for the purposes of specifying type parameters. At this stage, the implementation is incomplete in several major ways: - Generic types are not supported. - Generic instantiation discovery is only possible within a single package. Detecting instantiations from other packages will require changes to the build package. - When translating generic functions we do not yet apply type parameter to type argument mapping. - DCE does not distinguish between different instantiations of the same object and doesn't properly handle variable reservation decls. All those issues will be addressed in later commits.
Instead of using type information directly from types.Info.TypeOf, we now use a funcContext.typeOf, which passes the resulting type through typeparams.Resolver. If we are translating a parameterized code, it will perform type parameter substitution according to the type arguments of the instance we are currently translating. This allows us to generate a type-specific code for each function instance, making sure correct operations are used in each case.
Initially I thought it would be trivial to derive them from the main type instances, but it led to more duplicated code than necessary, so now they will be discovered and processed explicitly.
Similar to standalone functions, we generate a set of initialization code for each combination of type parameters discovered. Code for metadata initialization is generated with type argument substitution active for the given instantiation. Methods are translated essentially the same as standalone functions, except that they are assigned to the receiver type object instead of a standalone variable.
Type expressions for generic types contain an index expressions, which was previously impossible. With this change, we correctly recognize and check them.
Previously passing any type other than int would cause a type assertion failure and a panic. This bug could be triggered when evaluating a result of len() built-in for array types. However, it remained hidden in non-generic code, since the expression was determined to be constant, short-circuiting translation. Apparently, in generic code go/types can't prove the constant value, thus revealing the bug.
Prior to this change, while scanning for seed generic instances we would not traverser generic function (or method) bodies, which lead to generic types declared inside them not being added to objMap. Later, when an instance of such type was discovered, we had no matching AST node to process for further instantiations. With this change, we do traverse generic function bodies, but only to populate objMap. We ignore potential type instantiations in this case because they would be defined in terms of a type param, which are not interesting to us.
When calling a method on a type param or a type defined using a type param we replace the original selection from go/types.Info.Selections with a synthetic counterpart for the instantiated receiver type. Unfortunately, we can't construct instances of types.Selection due to its fields being private, so we create an interface-compatible implementation instead.
Prior to generics an inline type was always first encountered by the compiler at its decl statement, where it reserved the variable name for it. With generics, it may be encountered before that when translating one of the instantiations of a generic type. With this change, variable name allocation will happen correctly regardless of where it would be encountered first.
Such variables are stored in a single-element arrays, and the pointer object is stored in the $ptr property of such an array. The earlier refactoring of object name assignment made the code generation to emit `varname[0].$ptr` instead of `varname.$ptr`, which broke it for primitive types. This change restores the original behavior.
Prior to this change the discovered instance would have referred to the *types.Var object representing the implicitly declared struct field. With this change, we extract the *types.TypeName that represents the instantiated type.
Since we can now traverse the same AST subtree multiple types while processing different generic instances, type declaration statements may be visited more than once as well. The collected type list is then used to emit JS for type definitions, so duplicate *types.TypeName entries led to emitting duplicate code. Using set semantics prevents that. Note that we use ordered set to make sure code generation remains deterministic.
Previously used symbol.Name produces a collision when types with the same name declared in two different scopes, for example: ```go func f() { type E struct{} var e E _ = e } func g() { type E struct{} var e E _ = e } ``` In the example above, two declarations of `E` are actually two different objects, but their instances would have been mixed up.
This change fixes a class of generic instance collisions caused by type name shadowing by generating synthetic numeric keys for each type instance in the program instead of deriving a string-based key from type arguments. Each instance added to the InstanceSet is assigned a number which is guaranteed to be unique among all instances of the same object. This allows us to distinguish two different instances of `f` in the example below: ```go func f[T any]() {} func main() { type X int f[X]() { type X string // Shadows outer X. f[X]() } } ```
Prior to this change, when a generic function had named result variables, we had an identity mismatch when accessing result variables through the instantiated function signature vs through the function body AST. The latter references the types.Var instance defined in terms of type parameters, whereas the former produced synthetic instantiated versions of the same types.Var objects. As a result, two different names were assigned to what should be the same object, depending on how it was reached. With this change, we preserve the original, uninstantiated signature, which result variables match the ones referenced in the body AST. Whenever we need access to the instantiated signature types we perform type substitution ad-hoc.
Prior to this change, we did not substitute type parameters with instantiated counterparts, which led to the incorrect treatment of the type param types as interfaces and invalid type assertion results. This change corrects the mistake. Although typeswitch2.go and typeswitch5.go generate a different output from upstream Go, it is semantically equivalent and the difference is down to console.log() behaving slightly differently than println() in native Go.
Despite being defined in the unsafe package, these functions actually are implemented as builtins. For non-generic types go/types automatically computes constant values for corresponding AST nodes, but without type substitution it can't do the same for generic code. To make it work, we explicitly implement these builtins in our code, where type substitution takes effect, using go/types.Sizes to provide actual byte values.
Previously we've been using similar functionality from go/types package. Since it was unexported, we've used a //go:linkname directive to gain access to it. However, upgrade to go1.19 changed arguments of the function in ways that are difficult to replicate, so I switched to an equivalent reimplementation from the go/ssa package. This version is implemented in terms of public go/types interface, so it's easy to vendor and update. To simplify code updates in future I kept all original code intact and added a separate source file that exports the necessary functions for gopherjs use.
- typeswitch5.go now uses fmt.Println() and passes. - Most generics-related tests added in 1.19 also pass now.
Previously it was masked by missing generics support, but now it revealed another latent bug: gopherjs#1271.
450914c
to
8a80f06
Compare
I like this implementation a lot better. Makes a lot of sense! Thanks so much for your hard work on this @nevkontakte - I will try to test this with some of my repos soon. |
flimzy
reviewed
Feb 25, 2024
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Will look more closely when not watching kids
flimzy
approved these changes
Feb 25, 2024
I tried to fixup original comments to keep the history tidier, but that generated far too many merge conflicts than it's worth. Let it be my lesson for why pull requests shall be of a modest size.
7 tasks
7 tasks
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This pull request contains a proof-of-concept implementation of generics in GopherJS, which differs from the one I described in this comment and partially implemented in the generics branch.
Conceptually, this implementation falls in the monomorphization category, where for each instantiation of a generic type of function, a separate, specialized version of the executable code is generated. In gopherjs, we do this in two phases:
Most of the generics-related logic is located in the
compiler/internal/typeparams
package. Type parameter substitution logic has been borrowed more or less verbatim fromgolang.org/x/tools/go/ssa
and is located incompiler/internal/typeparams/subst
.The most obvious disadvantage of this approach is bigger generated code size, since each instantiation of a generic type pretty much generates a whole copy of the thing. However, this drawback is offset by several significant advantages:
In future we can also considerably improve code size by moving towards the stenciling approach vanilla Go took, as well as using DCE to remove unused pieces of generic instances independently from each other.
Implementation in this branch currently passes all test cases in the
typeparams
suite in the Go repo (sans a few legitimate divergencies from vanilla), but in not quite ready for production use. Most notably:build
package.compiler/analysis
package instance-aware.typeparam/nested.go
test case represents those edge cases.