GopherJS generics support

[nevkontakte]

It appears that generic (a.k.a. type parameters support) is well underway in the upstream Go (dev.typeparams branch) and is likely to be included in 1.18. Which means GopherJS also needs to support this, ideally at the same time as Go 1.18, which I expect is a lot of work. Does anyone have even approximate sense of what it would take to support generics? @flimzy @dmitshur @neelance.

For now, I'm filing this issue to look for a volunteer (or several) to contribute this support. By myself I almost certainly won't be able to implement this, considering that we have several other important features from earlier releases to take care of, such as modules and embed.

Important TODOs:

• Re-enable encoding/xml tests once generics are supported.
• Re-enable checkStringParseRoundTrip() in net/netip/fuzz_test.go.
• Remove compareSlices() override in go/doc/doc_test.go.
• Re-enable TestIssue50208 in reflect package.
• Verify pointers to arrays are wrapped correctly in generic functions.
• [go1.19] Remove generics-related overrides in crypto/elliptic/nistec.go, crypto/internal/boring/bbig/big.go, crypto/internal/nistec/nistec_test.go, crypto/internal/nistec/wrapper.go, go/token/position.go, sync/atomic/atomic.go, sync/atomic/atomic_test.go, testing/helper_test.go, testing/helperfuncs_test.go
• [go1.20] Remove generics-related overrides in compiler/natives/src/sync/map.go, compiler/natives/src/time/format.go, compiler/natives/src/time/format_rfc3339.go, compiler/natives/src/encoding/gob/gob.go, compiler/natives/src/internal/godebug/godebug.go, compiler/natives/src/net/http/http.go, compiler/natives/src/time/export_test.go

[inliquid]

I think it's planned for go1.18.

[nevkontakte]

I've been doing some research on potential ways to support generics in gopherjs and I think it would be good for me to share my thoughts. This isn't a proper design document, but I hope it would help us start a discussion and perhaps make it easier for people to contribute towards this :)

I'll start by sharing links to a few important resources I used:

• Go language specification, specifically its parts related to type parameters and instantiation. Reading these parts helped me understand semantics of generics in Go, what they can or can't do. Thankfully a lot of type-checking heavy lifting is done for us in the go/types package, so all we need to do is the code generation/runtime support.
• Type parameters proposal. This is a loooong read and not strictly necessary, but it has a lot of interesting context of why generics came to be that way.
• And a trio of implementation designs:
  • Generics implementation - Stenciling
  • Generics implementation - Dictionaries
  • Generics implementation - GC Shape Stenciling

These design docs deserve the most attention here, as they describe options the Go team considered for their own implementation. The first two docs present two ends of the spectrum: generate a specialized copy of executable code for each instantiation and generate one copy of universal code, delegating type-specific logic to helper functions passed via the dictionary. Ultimately, the Go team went with the hybrid approach as a trade off between binary size, compile time and complexity.

I think for GopherJS the tradeoff looks significantly differently. For us, output size is a critical concern, but things like stack allocation or memory management are much less relevant, since we delegate those to the javascript runtime. Also on a technical level, stenciling requires the ability to add function instantiations to the imported packages and deduplicate them at the linking stage. This is solvable, but GopherJS is not very well set up for this and will require a significant refactoring to make it possible. This makes me strongly favor the dictionaly-based design.

However, we can take advantage of our dynamic runtime environment and simplify our implementation even further by delaying generics instantiation to the runtime. That way, the compiler won't have to generate dictionaries and subdictionaries from the original design, or include them into the generated binary.

Consider this non-generic type:

type Foo struct{ f string }
func (f Foo) Bar() { println("bar") }

Here is a slightly abbreviated version of the code it compiles into:

Foo = $newType(0, $kindStruct, "main.Foo", true, "main", true, function(f_) { /* field initialization code */ });
Foo.ptr.prototype.Bar = function() { /* Foo.Bar() code */ };
Foo.methods = [{prop: "Bar", name: "Bar", pkg: "", typ: $funcType([], [], false)}];
Foo.init("main", [{prop: "f", name: "f", embedded: false, exported: false, typ: $String, tag: ""}]);

main = function() {
  var f = new Foo.ptr(""); // Using the type!
  $clone(f, Foo).Bar();
};

The important insight here is that we are already delaying type instantiation to the runtime, just before we begin program execution. Why not do the same for generic types, except do this when the generic type is demanded by the program?

Consider the following generic type:

type Foo[T any] struct{ f T }

func (f Foo[T]) Bar() { println("bar") }

Instead of a concrete instantiation we could generate a factory function for it:

Foo = function(T) {
  var instance = $newType(0, $kindStruct, "main.Foo[" + T.typeString +"]", true, "main", true, function(f_) { /* field initialization code */ });
  // Note that the method body closes over the type T and can use it for reflection/whatever purposes.
  instance.ptr.prototype.Bar = function() { /* Foo.Bar() code */ };
  instance.methods = [{prop: "Bar", name: "Bar", pkg: "", typ: $funcType([], [], false)}];
  // Note "typ: T" on the next line — using type parameter!
  instance.init("main", [{prop: "f", name: "f", embedded: false, exported: false, typ: T, tag: ""}]);
  return instance;
}

main = function() {
  var f = new (Foo($String).ptr)(""); // Calling the factory to get the constructor for the new operator.
  $clone(f, Foo($String)).Bar();
};

Of course, this is a simplified example. In the real implementation the factory function will cache and reuse instances of a generic type to improve performance and avoid "same but different" kinds of type conflicts. Similar approach could be applied to standalone generic functions.

Another issue we need to address is type-specific operations. The same operator may mean different things for different types, for example:

• int32(1) + int32(2) compiles into 1 + 2 >> 0
• "one" + "two" compiles into "one" + "two"

The original design solves this by introducing dictionaries that have a virtual table of functions that can be used with the generic type. In our implementation we can use the type instance itself in that role. For example we could define $String.add() and $Int32.add(), which could be called in the generic code as T.add(). Admittedly, this is likely to be worse performance that using the operator directly, but we could modify the compiler to only use these functions in the generic code, thus preventing performance hit in the existing non-generic code.

Finally, we also need to be able to construct types in generic code from passed type parameters, for example:

func Baz[T any]() { 
  x = Foo[[]T]{}
  //...
}

That could be compiled into something like this:

Baz = function(T) {
  return function() {
    x = new (Foo($silceType(T)))();
    // ...
  }
}

So that's as far as I got. It's getting late here, so apologies for all the typos I'm sure I've made in this text 😅 Inviting @flimzy, @paralin and any one else interested to comment.

[nevkontakte]

I created the new generics branch for this work and enabled the typeparam test suite from the Go repository in it. This should give us a decent idea for the level of compatibility we currently have.

@paralin are you still planning to work on it? I think I might start chipping away on this issue, and it would be a shame if we did duplicate work :) That said, I think there is plenty enough work for two people, if you are willing to help.

[paralin]

@nevkontakte I haven't started looking into this yet, but I'm happy to help out where I can if you have something you need done.