Skip to content

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 30 commits into from
Mar 2, 2024

Conversation

nevkontakte
Copy link
Member

@nevkontakte nevkontakte commented Feb 25, 2024

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:

  1. Iteratively traverse type-checked AST to discover instantiations of generic objects.
    1. We start with non-generic code and look for references to generic types and functions.
    2. Then we scan bodies of generic types and functions for each combination of type parameters previously discovered, while substituting references to type parameters with the current set of type arguments.
    3. If new instantiations are discovered, they are enqueued for further scanning.
    4. The process completes once no new combinations of type arguments are getting dicsovered.
  2. During transpilation, each generic object is translated multiple times, once for each unique type argument combination discovered in step 1. During translation references to type parameters are once again replaced with corresponding type arguments, producing specialized code for each combination. Non-generic objects are translated as before, only once.

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 from golang.org/x/tools/go/ssa and is located in compiler/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:

  • You only pay the size cost if you use generics. The original approach required moving a lot of logic from compiler to prelude, which made it bigger for everyone.
  • The generated code is equivalent in efficiency to non-generic code. The original approach relied on dynamic dispatch for a lot of low-level operations since exact types were not known at compile time.
  • Changes to the compiler are much, much more limited and easier to maintain. The original approach required duplicating a considerable amount of logic both in compiler (for non-generic code) and in prelude (for generic code).

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:

  • Missing support for detecting generic instantiations across package boundaries. This should be relatively straightforward to implement with a few modifications to the build package.
  • Dead code elimination currently doesn't distinguish different instances of the same function or type: if one of them is used, all of them are considered in alive.
  • Blocking call detection currently conservatively assumes all generic function calls to be blocking. This can be solved by making compiler/analysis package instance-aware.
  • Some edge cases around defining generic types inside generic functions are not fully supported. I need to add support for "context" type parameters (in addition to type's own type parameters) in type instances to make that work fully. typeparam/nested.go test case represents those edge cases.

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.
@nevkontakte nevkontakte added this to the Go spec compliance milestone Feb 25, 2024
@nevkontakte nevkontakte requested a review from flimzy February 25, 2024 01:41
@paralin
Copy link
Contributor

paralin commented Feb 25, 2024

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.

Copy link
Member

@flimzy flimzy left a 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

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.
@nevkontakte nevkontakte merged commit 6de32f8 into gopherjs:generics-ng Mar 2, 2024
@nevkontakte nevkontakte linked an issue Mar 2, 2024 that may be closed by this pull request
7 tasks
@nevkontakte nevkontakte removed a link to an issue Mar 2, 2024
7 tasks
@nevkontakte nevkontakte linked an issue Mar 2, 2024 that may be closed by this pull request
7 tasks
@nevkontakte nevkontakte removed a link to an issue Mar 2, 2024
7 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants