This document describes the implementation of generics via dictionaries and
gcshape stenciling in Go 1.18. It provides more concrete and up-to-date
information than described in the Gcshape design document

The compiler implementation of generics (after typechecking) focuses mainly on creating instantiations of generic functions and methods that will execute with arguments that have concrete types. In order to avoid creating a different function instantiation for each invocation of a generic function/method with distinct type arguments (which would be pure stenciling), we pass a dictionary along with every call to a generic function/method. The dictionary provides relevant information about the type arguments that allows a single function instantiation to run correctly for many distinct type arguments.

However, for simplicity (and performance) of implementation, we do not have a single compilation of a generic function/method for all possible type arguments. Instead, we share an instantiation of a generic function/method among sets of type arguments that have the same gcshape.

Gcshapes

A gcshape (or gcshape grouping) is a collection of types that can all share the same instantiation of a generic function/method in our implementation when specified as one of the type arguments. So, for example, in the case of a generic function with a single type parameter, we only need one function instantiation for all type arguments in the same gcshape grouping. Similarly, for a method of a generic type with a single type parameter, we only need one instantiation for all type arguments (of the generic type) in the same gcshape grouping. A gcshape type is a specific type that we use in the implementation in such an instantiation to fill in for all types of the gcshape grouping.

We are currently implementing gcshapes in a fairly fine-grained manner. Two concrete types are in the same gcshape grouping if and only if they have the same underlying type or they are both pointer types. We are intentionally defining gcshapes such that we don’t ever need to include any operator methods (e.g. the implementation of the “+” operator for a specified type arg) in a dictionary. In particular, fundamentally different built-in types such as int and float64 are never in the same gcshape. Even int16 and int32 have distinct operations (notably left and right shift), so we don’t put them in the same gcshape. Similarly, we intend that all types in a gcshape will always implement builtin methods (such as make / new / len ) in the same way. We could include some very closely related built-in types (such as uint and uintptr) in the same gcshape, but are not currently doing that. This is already implied by our current fine-grain gcshapes, but we also always want an interface type to be in a different gcshape from a non-interface type (even if the non-interface type has the same two-field structure as an interface type). Interface types behave very differently from non-interface types in terms of calling methods, etc.

We currently name each gcshape type based on the unique string representation (as implemented in types.LinkString) of its underlying type. We put all shape types in a unique builtin-package “go.shape”. For implementation reasons (see next section), we happen to include in the name of a gcshape type the index of the gcshape argument in the type parameter list. So, a type with underlying type “string” would correspond to a gcshape type named “go.shape.string_0” or “go.shape.string_1”, depending on whether the type is used as the first or second type argument of a generic function or type. All pointer types are named after a single example type *uint8, so the names of gcshapes for pointer shapes are go.shape.*uint8_0, go.shape.*uint8_1, etc.

We refer to an instantiation of a generic function or method for a specific set of shape type arguments as a shape instantiation.

Dictionary Format

Each dictionary is statically defined at compile-time. A dictionary corresponds to a call site in a program where a specific generic function/method is called with a specific set of concrete type arguments. A dictionary is needed whenever a generic function/method is called, regardless if called from a non-generic or generic function/method. A dictionary is currently named after the fully-qualified generic function/method name being called and the names of the concrete type arguments. Two example dictionary names are main..dict.Map[int,bool] and main..dict.mapCons[int,bool].Apply). These are the dictionaries needed for a call or reference to main.Map[int, bool]() and rcvr.Apply(), where rcvr has type main.mapCons[int, bool]. The dictionary contains the information needed to execute a gcshape-based instantiation of that generic function/method with those concrete type arguments. Dictionaries with the same name are fully de-duped (by some combination of the compiler and the linker).

We can gather information on the expected format of a dictionary by analyzing the shape instantiation of a generic function/method. We analyze an instantiation, instead of the generic function/method itself, because the required dictionary entries can depend on the shape arguments – notably whether a shape argument is an interface type or not. It is important that the instantiation has been “transformed” enough that all implicit interface conversions (OCONVIFACE) have been made explicit. Explicit or implicit interface conversions (in particular, conversions to non-empty interfaces) may require an extra entry in the dictionary.

In order to create the dictionary entries, we often need to substitute the shape type arguments with the real type arguments associated with the dictionary. The shape type arguments must therefore be fully distinguishable, even if several of the type arguments happen to have the same shape (e.g. they are both pointer types). Therefore, as mentioned above, we actually add the index of the type parameter to the shape type, so that different type arguments can be fully distinguished correctly.

The types of entries in a dictionary are as follows:

• The list of the concrete type arguments of the generic function/method
  • Types in the dictionary are always the run-time type descriptor (a pointer to runtime._type)
• The list of all (or needed) derived types, which appear in or are implicit in some way in the generic function/method, substituted with the concrete type arguments.
  • That is, the list of concrete types that are specifically derived from the type parameters of the function/method (e.g. *T, []T, map[K, V], etc) and used in some way in the generic function/method.
  • We currently use the derived types for several cases where we need the runtime type of an expression. These cases include explicit or implicit conversions to an empty interface, and type assertions and type switches, where the type of the source value is an empty interface.
  • The derived type and type argument entries are also used at run time by the debugger to determine the concrete type of arguments and local variables. At compile time, information about the type argument and derived type dictionary entries is emitted with the DWARF info. For each argument or local variable that has a parameterized type, the DWARF info also indicates the dictionary entry that will co