blob: 4b4a0f4ad670945acea046f3e8f2de1790b68891 [file] [log] [blame]
// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// This file implements type parameter substitution.
package types
import "go/token"
type substMap map[*TypeParam]Type
// makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
// If targs[i] is nil, tpars[i] is not substituted.
func makeSubstMap(tpars []*TypeParam, targs []Type) substMap {
assert(len(tpars) == len(targs))
proj := make(substMap, len(tpars))
for i, tpar := range tpars {
proj[tpar] = targs[i]
}
return proj
}
// makeRenameMap is like makeSubstMap, but creates a map used to rename type
// parameters in from with the type parameters in to.
func makeRenameMap(from, to []*TypeParam) substMap {
assert(len(from) == len(to))
proj := make(substMap, len(from))
for i, tpar := range from {
proj[tpar] = to[i]
}
return proj
}
func (m substMap) empty() bool {
return len(m) == 0
}
func (m substMap) lookup(tpar *TypeParam) Type {
if t := m[tpar]; t != nil {
return t
}
return tpar
}
// subst returns the type typ with its type parameters tpars replaced by the
// corresponding type arguments targs, recursively. subst is pure in the sense
// that it doesn't modify the incoming type. If a substitution took place, the
// result type is different from the incoming type.
//
// If the given context is non-nil, it is used in lieu of check.Config.Context
func (check *Checker) subst(pos token.Pos, typ Type, smap substMap, ctxt *Context) Type {
if smap.empty() {
return typ
}
// common cases
switch t := typ.(type) {
case *Basic:
return typ // nothing to do
case *TypeParam:
return smap.lookup(t)
}
// general case
subst := subster{
pos: pos,
smap: smap,
check: check,
ctxt: check.bestContext(ctxt),
}
return subst.typ(typ)
}
type subster struct {
pos token.Pos
smap substMap
check *Checker // nil if called via Instantiate
ctxt *Context
}
func (subst *subster) typ(typ Type) Type {
switch t := typ.(type) {
case nil:
// Call typOrNil if it's possible that typ is nil.
panic("nil typ")
case *Basic:
// nothing to do
case *Array:
elem := subst.typOrNil(t.elem)
if elem != t.elem {
return &Array{len: t.len, elem: elem}
}
case *Slice:
elem := subst.typOrNil(t.elem)
if elem != t.elem {
return &Slice{elem: elem}
}
case *Struct:
if fields, copied := subst.varList(t.fields); copied {
s := &Struct{fields: fields, tags: t.tags}
s.markComplete()
return s
}
case *Pointer:
base := subst.typ(t.base)
if base != t.base {
return &Pointer{base: base}
}
case *Tuple:
return subst.tuple(t)
case *Signature:
// Preserve the receiver: it is handled during *Interface and *Named type
// substitution.
//
// Naively doing the substitution here can lead to an infinite recursion in
// the case where the receiver is an interface. For example, consider the
// following declaration:
//
// type T[A any] struct { f interface{ m() } }
//
// In this case, the type of f is an interface that is itself the receiver
// type of all of its methods. Because we have no type name to break
// cycles, substituting in the recv results in an infinite loop of
// recv->interface->recv->interface->...
recv := t.recv
params := subst.tuple(t.params)
results := subst.tuple(t.results)
if params != t.params || results != t.results {
return &Signature{
rparams: t.rparams,
// TODO(rFindley) why can't we nil out tparams here, rather than in instantiate?
tparams: t.tparams,
// instantiated signatures have a nil scope
recv: recv,
params: params,
results: results,
variadic: t.variadic,
}
}
case *Union:
terms, copied := subst.termlist(t.terms)
if copied {
// term list substitution may introduce duplicate terms (unlikely but possible).
// This is ok; lazy type set computation will determine the actual type set
// in normal form.
return &Union{terms}
}
case *Interface:
methods, mcopied := subst.funcList(t.methods)
embeddeds, ecopied := subst.typeList(t.embeddeds)
if mcopied || ecopied {
iface := subst.check.newInterface()
iface.embeddeds = embeddeds
iface.implicit = t.implicit
iface.complete = t.complete
// If we've changed the interface type, we may need to replace its
// receiver if the receiver type is the original interface. Receivers of
// *Named type are replaced during named type expansion.
//
// Notably, it's possible to reach here and not create a new *Interface,
// even though the receiver type may be parameterized. For example:
//
// type T[P any] interface{ m() }
//
// In this case the interface will not be substituted here, because its
// method signatures do not depend on the type parameter P, but we still
// need to create new interface methods to hold the instantiated
// receiver. This is handled by expandNamed.
iface.methods, _ = replaceRecvType(methods, t, iface)
return iface
}
case *Map:
key := subst.typ(t.key)
elem := subst.typ(t.elem)
if key != t.key || elem != t.elem {
return &Map{key: key, elem: elem}
}
case *Chan:
elem := subst.typ(t.elem)
if elem != t.elem {
return &Chan{dir: t.dir, elem: elem}
}
case *Named:
// dump is for debugging
dump := func(string, ...any) {}
if subst.check != nil && trace {
subst.check.indent++
defer func() {
subst.check.indent--
}()
dump = func(format string, args ...any) {
subst.check.trace(subst.pos, format, args...)
}
}
// subst is called by expandNamed, so in this function we need to be
// careful not to call any methods that would cause t to be expanded: doing
// so would result in deadlock.
//
// So we call t.orig.TypeParams() rather than t.TypeParams() here and
// below.
if t.orig.TypeParams().Len() == 0 {
dump(">>> %s is not parameterized", t)
return t // type is not parameterized
}
var newTArgs []Type
if t.targs.Len() != t.orig.TypeParams().Len() {
return Typ[Invalid] // error reported elsewhere
}
// already instantiated
dump(">>> %s already instantiated", t)
// For each (existing) type argument targ, determine if it needs
// to be substituted; i.e., if it is or contains a type parameter
// that has a type argument for it.
for i, targ := range t.targs.list() {
dump(">>> %d targ = %s", i, targ)
new_targ := subst.typ(targ)
if new_targ != targ {
dump(">>> substituted %d targ %s => %s", i, targ, new_targ)
if newTArgs == nil {
newTArgs = make([]Type, t.orig.TypeParams().Len())
copy(newTArgs, t.targs.list())
}
newTArgs[i] = new_targ
}
}
if newTArgs == nil {
dump(">>> nothing to substitute in %s", t)
return t // nothing to substitute
}
// before creating a new named type, check if we have this one already
h := subst.ctxt.instanceHash(t.orig, newTArgs)
dump(">>> new type hash: %s", h)
if named := subst.ctxt.lookup(h, t.orig, newTArgs); named != nil {
dump(">>> found %s", named)
return named
}
// Create a new instance and populate the context to avoid endless
// recursion. The position used here is irrelevant because validation only
// occurs on t (we don't call validType on named), but we use subst.pos to
// help with debugging.
t.orig.resolve(subst.ctxt)
return subst.check.instance(subst.pos, t.orig, newTArgs, subst.ctxt)
// Note that if we were to expose substitution more generally (not just in
// the context of a declaration), we'd have to substitute in
// named.underlying as well.
//
// But this is unnecessary for now.
case *TypeParam:
return subst.smap.lookup(t)
default:
panic("unimplemented")
}
return typ
}
// typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
// A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
// where an array/slice element is accessed before it is set up.
func (subst *subster) typOrNil(typ Type) Type {
if typ == nil {
return Typ[Invalid]
}
return subst.typ(typ)
}
func (subst *subster) var_(v *Var) *Var {
if v != nil {
if typ := subst.typ(v.typ); typ != v.typ {
copy := *v
copy.typ = typ
return &copy
}
}
return v
}
func (subst *subster) tuple(t *Tuple) *Tuple {
if t != nil {
if vars, copied := subst.varList(t.vars); copied {
return &Tuple{vars: vars}
}
}
return t
}
func (subst *subster) varList(in []*Var) (out []*Var, copied bool) {
out = in
for i, v := range in {
if w := subst.var_(v); w != v {
if !copied {
// first variable that got substituted => allocate new out slice
// and copy all variables
new := make([]*Var, len(in))
copy(new, out)
out = new
copied = true
}
out[i] = w
}
}
return
}
func (subst *subster) func_(f *Func) *Func {
if f != nil {
if typ := subst.typ(f.typ); typ != f.typ {
copy := *f
copy.typ = typ
return &copy
}
}
return f
}
func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) {
out = in
for i, f := range in {
if g := subst.func_(f); g != f {
if !copied {
// first function that got substituted => allocate new out slice
// and copy all functions
new := make([]*Func, len(in))
copy(new, out)
out = new
copied = true
}
out[i] = g
}
}
return
}
func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
out = in
for i, t := range in {
if u := subst.typ(t); u != t {
if !copied {
// first function that got substituted => allocate new out slice
// and copy all functions
new := make([]Type, len(in))
copy(new, out)
out = new
copied = true
}
out[i] = u
}
}
return
}
func (subst *subster) termlist(in []*Term) (out []*Term, copied bool) {
out = in
for i, t := range in {
if u := subst.typ(t.typ); u != t.typ {
if !copied {
// first function that got substituted => allocate new out slice
// and copy all functions
new := make([]*Term, len(in))
copy(new, out)
out = new
copied = true
}
out[i] = NewTerm(t.tilde, u)
}
}
return
}
// replaceRecvType updates any function receivers that have type old to have
// type new. It does not modify the input slice; if modifications are required,
// the input slice and any affected signatures will be copied before mutating.
//
// The resulting out slice contains the updated functions, and copied reports
// if anything was modified.
func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
out = in
for i, method := range in {
sig := method.Type().(*Signature)
if sig.recv != nil && sig.recv.Type() == old {
if !copied {
// Allocate a new methods slice before mutating for the first time.
// This is defensive, as we may share methods across instantiations of
// a given interface type if they do not get substituted.
out = make([]*Func, len(in))
copy(out, in)
copied = true
}
newsig := *sig
sig = &newsig
sig.recv = NewVar(sig.recv.pos, sig.recv.pkg, "", new)
out[i] = NewFunc(method.pos, method.pkg, method.name, sig)
}
}
return
}