subst.go

     1  // Copyright 2018 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This file implements type parameter substitution.
     6  
     7  package types2
     8  
     9  import "cmd/compile/internal/syntax"
    10  
    11  type substMap map[*TypeParam]Type
    12  
    13  // makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
    14  // If targs[i] is nil, tpars[i] is not substituted.
    15  func makeSubstMap(tpars []*TypeParam, targs []Type) substMap {
    16  	assert(len(tpars) == len(targs))
    17  	proj := make(substMap, len(tpars))
    18  	for i, tpar := range tpars {
    19  		proj[tpar] = targs[i]
    20  	}
    21  	return proj
    22  }
    23  
    24  // makeRenameMap is like makeSubstMap, but creates a map used to rename type
    25  // parameters in from with the type parameters in to.
    26  func makeRenameMap(from, to []*TypeParam) substMap {
    27  	assert(len(from) == len(to))
    28  	proj := make(substMap, len(from))
    29  	for i, tpar := range from {
    30  		proj[tpar] = to[i]
    31  	}
    32  	return proj
    33  }
    34  
    35  func (m substMap) empty() bool {
    36  	return len(m) == 0
    37  }
    38  
    39  func (m substMap) lookup(tpar *TypeParam) Type {
    40  	if t := m[tpar]; t != nil {
    41  		return t
    42  	}
    43  	return tpar
    44  }
    45  
    46  // subst returns the type typ with its type parameters tpars replaced by the
    47  // corresponding type arguments targs, recursively. subst doesn't modify the
    48  // incoming type. If a substitution took place, the result type is different
    49  // from the incoming type.
    50  //
    51  // If the given context is non-nil, it is used in lieu of check.Config.Context.
    52  func (check *Checker) subst(pos syntax.Pos, typ Type, smap substMap, ctxt *Context) Type {
    53  	if smap.empty() {
    54  		return typ
    55  	}
    56  
    57  	// common cases
    58  	switch t := typ.(type) {
    59  	case *Basic:
    60  		return typ // nothing to do
    61  	case *TypeParam:
    62  		return smap.lookup(t)
    63  	}
    64  
    65  	// general case
    66  	subst := subster{
    67  		pos:   pos,
    68  		smap:  smap,
    69  		check: check,
    70  		ctxt:  check.bestContext(ctxt),
    71  	}
    72  	return subst.typ(typ)
    73  }
    74  
    75  type subster struct {
    76  	pos   syntax.Pos
    77  	smap  substMap
    78  	check *Checker // nil if called via Instantiate
    79  	ctxt  *Context
    80  }
    81  
    82  func (subst *subster) typ(typ Type) Type {
    83  	switch t := typ.(type) {
    84  	case nil:
    85  		// Call typOrNil if it's possible that typ is nil.
    86  		panic("nil typ")
    87  
    88  	case *Basic:
    89  		// nothing to do
    90  
    91  	case *Array:
    92  		elem := subst.typOrNil(t.elem)
    93  		if elem != t.elem {
    94  			return &Array{len: t.len, elem: elem}
    95  		}
    96  
    97  	case *Slice:
    98  		elem := subst.typOrNil(t.elem)
    99  		if elem != t.elem {
   100  			return &Slice{elem: elem}
   101  		}
   102  
   103  	case *Struct:
   104  		if fields, copied := subst.varList(t.fields); copied {
   105  			s := &Struct{fields: fields, tags: t.tags}
   106  			s.markComplete()
   107  			return s
   108  		}
   109  
   110  	case *Pointer:
   111  		base := subst.typ(t.base)
   112  		if base != t.base {
   113  			return &Pointer{base: base}
   114  		}
   115  
   116  	case *Tuple:
   117  		return subst.tuple(t)
   118  
   119  	case *Signature:
   120  		// Preserve the receiver: it is handled during *Interface and *Named type
   121  		// substitution.
   122  		//
   123  		// Naively doing the substitution here can lead to an infinite recursion in
   124  		// the case where the receiver is an interface. For example, consider the
   125  		// following declaration:
   126  		//
   127  		//  type T[A any] struct { f interface{ m() } }
   128  		//
   129  		// In this case, the type of f is an interface that is itself the receiver
   130  		// type of all of its methods. Because we have no type name to break
   131  		// cycles, substituting in the recv results in an infinite loop of
   132  		// recv->interface->recv->interface->...
   133  		recv := t.recv
   134  
   135  		params := subst.tuple(t.params)
   136  		results := subst.tuple(t.results)
   137  		if params != t.params || results != t.results {
   138  			return &Signature{
   139  				rparams: t.rparams,
   140  				// TODO(gri) why can't we nil out tparams here, rather than in instantiate?
   141  				tparams: t.tparams,
   142  				// instantiated signatures have a nil scope
   143  				recv:     recv,
   144  				params:   params,
   145  				results:  results,
   146  				variadic: t.variadic,
   147  			}
   148  		}
   149  
   150  	case *Union:
   151  		terms, copied := subst.termlist(t.terms)
   152  		if copied {
   153  			// term list substitution may introduce duplicate terms (unlikely but possible).
   154  			// This is ok; lazy type set computation will determine the actual type set
   155  			// in normal form.
   156  			return &Union{terms}
   157  		}
   158  
   159  	case *Interface:
   160  		methods, mcopied := subst.funcList(t.methods)
   161  		embeddeds, ecopied := subst.typeList(t.embeddeds)
   162  		if mcopied || ecopied {
   163  			iface := subst.check.newInterface()
   164  			iface.embeddeds = embeddeds
   165  			iface.implicit = t.implicit
   166  			iface.complete = t.complete
   167  			// If we've changed the interface type, we may need to replace its
   168  			// receiver if the receiver type is the original interface. Receivers of
   169  			// *Named type are replaced during named type expansion.
   170  			//
   171  			// Notably, it's possible to reach here and not create a new *Interface,
   172  			// even though the receiver type may be parameterized. For example:
   173  			//
   174  			//  type T[P any] interface{ m() }
   175  			//
   176  			// In this case the interface will not be substituted here, because its
   177  			// method signatures do not depend on the type parameter P, but we still
   178  			// need to create new interface methods to hold the instantiated
   179  			// receiver. This is handled by expandNamed.
   180  			iface.methods, _ = replaceRecvType(methods, t, iface)
   181  			return iface
   182  		}
   183  
   184  	case *Map:
   185  		key := subst.typ(t.key)
   186  		elem := subst.typ(t.elem)
   187  		if key != t.key || elem != t.elem {
   188  			return &Map{key: key, elem: elem}
   189  		}
   190  
   191  	case *Chan:
   192  		elem := subst.typ(t.elem)
   193  		if elem != t.elem {
   194  			return &Chan{dir: t.dir, elem: elem}
   195  		}
   196  
   197  	case *Named:
   198  		// dump is for debugging
   199  		dump := func(string, ...interface{}) {}
   200  		if subst.check != nil && subst.check.conf.Trace {
   201  			subst.check.indent++
   202  			defer func() {
   203  				subst.check.indent--
   204  			}()
   205  			dump = func(format string, args ...interface{}) {
   206  				subst.check.trace(subst.pos, format, args...)
   207  			}
   208  		}
   209  
   210  		// subst is called by expandNamed, so in this function we need to be
   211  		// careful not to call any methods that would cause t to be expanded: doing
   212  		// so would result in deadlock.
   213  		//
   214  		// So we call t.orig.TypeParams() rather than t.TypeParams() here and
   215  		// below.
   216  		if t.orig.TypeParams().Len() == 0 {
   217  			dump(">>> %s is not parameterized", t)
   218  			return t // type is not parameterized
   219  		}
   220  
   221  		var newTArgs []Type
   222  		if t.targs.Len() != t.orig.TypeParams().Len() {
   223  			return Typ[Invalid] // error reported elsewhere
   224  		}
   225  
   226  		// already instantiated
   227  		dump(">>> %s already instantiated", t)
   228  		// For each (existing) type argument targ, determine if it needs
   229  		// to be substituted; i.e., if it is or contains a type parameter
   230  		// that has a type argument for it.
   231  		for i, targ := range t.targs.list() {
   232  			dump(">>> %d targ = %s", i, targ)
   233  			new_targ := subst.typ(targ)
   234  			if new_targ != targ {
   235  				dump(">>> substituted %d targ %s => %s", i, targ, new_targ)
   236  				if newTArgs == nil {
   237  					newTArgs = make([]Type, t.orig.TypeParams().Len())
   238  					copy(newTArgs, t.targs.list())
   239  				}
   240  				newTArgs[i] = new_targ
   241  			}
   242  		}
   243  
   244  		if newTArgs == nil {
   245  			dump(">>> nothing to substitute in %s", t)
   246  			return t // nothing to substitute
   247  		}
   248  
   249  		// before creating a new named type, check if we have this one already
   250  		h := subst.ctxt.instanceHash(t.orig, newTArgs)
   251  		dump(">>> new type hash: %s", h)
   252  		if named := subst.ctxt.lookup(h, t.orig, newTArgs); named != nil {
   253  			dump(">>> found %s", named)
   254  			return named
   255  		}
   256  
   257  		// Create a new instance and populate the context to avoid endless
   258  		// recursion. The position used here is irrelevant because validation only
   259  		// occurs on t (we don't call validType on named), but we use subst.pos to
   260  		// help with debugging.
   261  		t.orig.resolve(subst.ctxt)
   262  		return subst.check.instance(subst.pos, t.orig, newTArgs, subst.ctxt)
   263  
   264  		// Note that if we were to expose substitution more generally (not just in
   265  		// the context of a declaration), we'd have to substitute in
   266  		// named.underlying as well.
   267  		//
   268  		// But this is unnecessary for now.
   269  
   270  	case *TypeParam:
   271  		return subst.smap.lookup(t)
   272  
   273  	default:
   274  		unimplemented()
   275  	}
   276  
   277  	return typ
   278  }
   279  
   280  // typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
   281  // A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
   282  // where an array/slice element is accessed before it is set up.
   283  func (subst *subster) typOrNil(typ Type) Type {
   284  	if typ == nil {
   285  		return Typ[Invalid]
   286  	}
   287  	return subst.typ(typ)
   288  }
   289  
   290  func (subst *subster) var_(v *Var) *Var {
   291  	if v != nil {
   292  		if typ := subst.typ(v.typ); typ != v.typ {
   293  			return substVar(v, typ)
   294  		}
   295  	}
   296  	return v
   297  }
   298  
   299  func substVar(v *Var, typ Type) *Var {
   300  	copy := *v
   301  	copy.typ = typ
   302  	return &copy
   303  }
   304  
   305  func (subst *subster) tuple(t *Tuple) *Tuple {
   306  	if t != nil {
   307  		if vars, copied := subst.varList(t.vars); copied {
   308  			return &Tuple{vars: vars}
   309  		}
   310  	}
   311  	return t
   312  }
   313  
   314  func (subst *subster) varList(in []*Var) (out []*Var, copied bool) {
   315  	out = in
   316  	for i, v := range in {
   317  		if w := subst.var_(v); w != v {
   318  			if !copied {
   319  				// first variable that got substituted => allocate new out slice
   320  				// and copy all variables
   321  				new := make([]*Var, len(in))
   322  				copy(new, out)
   323  				out = new
   324  				copied = true
   325  			}
   326  			out[i] = w
   327  		}
   328  	}
   329  	return
   330  }
   331  
   332  func (subst *subster) func_(f *Func) *Func {
   333  	if f != nil {
   334  		if typ := subst.typ(f.typ); typ != f.typ {
   335  			copy := *f
   336  			copy.typ = typ
   337  			return &copy
   338  		}
   339  	}
   340  	return f
   341  }
   342  
   343  func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) {
   344  	out = in
   345  	for i, f := range in {
   346  		if g := subst.func_(f); g != f {
   347  			if !copied {
   348  				// first function that got substituted => allocate new out slice
   349  				// and copy all functions
   350  				new := make([]*Func, len(in))
   351  				copy(new, out)
   352  				out = new
   353  				copied = true
   354  			}
   355  			out[i] = g
   356  		}
   357  	}
   358  	return
   359  }
   360  
   361  func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
   362  	out = in
   363  	for i, t := range in {
   364  		if u := subst.typ(t); u != t {
   365  			if !copied {
   366  				// first function that got substituted => allocate new out slice
   367  				// and copy all functions
   368  				new := make([]Type, len(in))
   369  				copy(new, out)
   370  				out = new
   371  				copied = true
   372  			}
   373  			out[i] = u
   374  		}
   375  	}
   376  	return
   377  }
   378  
   379  func (subst *subster) termlist(in []*Term) (out []*Term, copied bool) {
   380  	out = in
   381  	for i, t := range in {
   382  		if u := subst.typ(t.typ); u != t.typ {
   383  			if !copied {
   384  				// first function that got substituted => allocate new out slice
   385  				// and copy all functions
   386  				new := make([]*Term, len(in))
   387  				copy(new, out)
   388  				out = new
   389  				copied = true
   390  			}
   391  			out[i] = NewTerm(t.tilde, u)
   392  		}
   393  	}
   394  	return
   395  }
   396  
   397  // replaceRecvType updates any function receivers that have type old to have
   398  // type new. It does not modify the input slice; if modifications are required,
   399  // the input slice and any affected signatures will be copied before mutating.
   400  //
   401  // The resulting out slice contains the updated functions, and copied reports
   402  // if anything was modified.
   403  func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
   404  	out = in
   405  	for i, method := range in {
   406  		sig := method.Type().(*Signature)
   407  		if sig.recv != nil && sig.recv.Type() == old {
   408  			if !copied {
   409  				// Allocate a new methods slice before mutating for the first time.
   410  				// This is defensive, as we may share methods across instantiations of
   411  				// a given interface type if they do not get substituted.
   412  				out = make([]*Func, len(in))
   413  				copy(out, in)
   414  				copied = true
   415  			}
   416  			newsig := *sig
   417  			newsig.recv = substVar(sig.recv, new)
   418  			out[i] = NewFunc(method.pos, method.pkg, method.name, &newsig)
   419  		}
   420  	}
   421  	return
   422  }
   423
View as plain text