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 (
    10  	"cmd/compile/internal/syntax"
    11  )
    12  
    13  type substMap map[*TypeParam]Type
    14  
    15  // makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
    16  // If targs[i] is nil, tpars[i] is not substituted.
    17  func makeSubstMap(tpars []*TypeParam, targs []Type) substMap {
    18  	assert(len(tpars) == len(targs))
    19  	proj := make(substMap, len(tpars))
    20  	for i, tpar := range tpars {
    21  		proj[tpar] = targs[i]
    22  	}
    23  	return proj
    24  }
    25  
    26  // makeRenameMap is like makeSubstMap, but creates a map used to rename type
    27  // parameters in from with the type parameters in to.
    28  func makeRenameMap(from, to []*TypeParam) substMap {
    29  	assert(len(from) == len(to))
    30  	proj := make(substMap, len(from))
    31  	for i, tpar := range from {
    32  		proj[tpar] = to[i]
    33  	}
    34  	return proj
    35  }
    36  
    37  func (m substMap) empty() bool {
    38  	return len(m) == 0
    39  }
    40  
    41  func (m substMap) lookup(tpar *TypeParam) Type {
    42  	if t := m[tpar]; t != nil {
    43  		return t
    44  	}
    45  	return tpar
    46  }
    47  
    48  // subst returns the type typ with its type parameters tpars replaced by the
    49  // corresponding type arguments targs, recursively. subst doesn't modify the
    50  // incoming type. If a substitution took place, the result type is different
    51  // from the incoming type.
    52  //
    53  // If expanding is non-nil, it is the instance type currently being expanded.
    54  // One of expanding or ctxt must be non-nil.
    55  func (check *Checker) subst(pos syntax.Pos, typ Type, smap substMap, expanding *Named, ctxt *Context) Type {
    56  	assert(expanding != nil || ctxt != nil)
    57  
    58  	if smap.empty() {
    59  		return typ
    60  	}
    61  
    62  	// common cases
    63  	switch t := typ.(type) {
    64  	case *Basic:
    65  		return typ // nothing to do
    66  	case *TypeParam:
    67  		return smap.lookup(t)
    68  	}
    69  
    70  	// general case
    71  	subst := subster{
    72  		pos:       pos,
    73  		smap:      smap,
    74  		check:     check,
    75  		expanding: expanding,
    76  		ctxt:      ctxt,
    77  	}
    78  	return subst.typ(typ)
    79  }
    80  
    81  type subster struct {
    82  	pos       syntax.Pos
    83  	smap      substMap
    84  	check     *Checker // nil if called via Instantiate
    85  	expanding *Named   // if non-nil, the instance that is being expanded
    86  	ctxt      *Context
    87  }
    88  
    89  func (subst *subster) typ(typ Type) Type {
    90  	switch t := typ.(type) {
    91  	case nil:
    92  		// Call typOrNil if it's possible that typ is nil.
    93  		panic("nil typ")
    94  
    95  	case *Basic:
    96  		// nothing to do
    97  
    98  	case *Alias:
    99  		// This code follows the code for *Named types closely.
   100  		// TODO(gri) try to factor better
   101  		orig := t.Origin()
   102  		n := orig.TypeParams().Len()
   103  		if n == 0 {
   104  			return t // type is not parameterized
   105  		}
   106  
   107  		// TODO(gri) do we need this for Alias types?
   108  		if t.TypeArgs().Len() != n {
   109  			return Typ[Invalid] // error reported elsewhere
   110  		}
   111  
   112  		// already instantiated
   113  		// For each (existing) type argument determine if it needs
   114  		// to be substituted; i.e., if it is or contains a type parameter
   115  		// that has a type argument for it.
   116  		if targs := substList(t.TypeArgs().list(), subst.typ); targs != nil {
   117  			return subst.check.newAliasInstance(subst.pos, t.orig, targs, subst.expanding, subst.ctxt)
   118  		}
   119  
   120  	case *Array:
   121  		elem := subst.typOrNil(t.elem)
   122  		if elem != t.elem {
   123  			return &Array{len: t.len, elem: elem}
   124  		}
   125  
   126  	case *Slice:
   127  		elem := subst.typOrNil(t.elem)
   128  		if elem != t.elem {
   129  			return &Slice{elem: elem}
   130  		}
   131  
   132  	case *Struct:
   133  		if fields := substList(t.fields, subst.var_); fields != nil {
   134  			s := &Struct{fields: fields, tags: t.tags}
   135  			s.markComplete()
   136  			return s
   137  		}
   138  
   139  	case *Pointer:
   140  		base := subst.typ(t.base)
   141  		if base != t.base {
   142  			return &Pointer{base: base}
   143  		}
   144  
   145  	case *Tuple:
   146  		return subst.tuple(t)
   147  
   148  	case *Signature:
   149  		// Preserve the receiver: it is handled during *Interface and *Named type
   150  		// substitution.
   151  		//
   152  		// Naively doing the substitution here can lead to an infinite recursion in
   153  		// the case where the receiver is an interface. For example, consider the
   154  		// following declaration:
   155  		//
   156  		//  type T[A any] struct { f interface{ m() } }
   157  		//
   158  		// In this case, the type of f is an interface that is itself the receiver
   159  		// type of all of its methods. Because we have no type name to break
   160  		// cycles, substituting in the recv results in an infinite loop of
   161  		// recv->interface->recv->interface->...
   162  		recv := t.recv
   163  
   164  		// If t is a generic method signature whose own type parameters are not
   165  		// themselves the subject of this substitution, we are substituting the
   166  		// receiver type parameters (via Named.expandMethod). Because a method
   167  		// type parameter's bound may refer to a receiver type parameter
   168  		// (e.g. func (G[T]) M[P interface{ ~*T }]), we must create fresh type
   169  		// parameters with substituted bounds, and rename occurrences in params
   170  		// and results so they refer to the fresh parameters. Otherwise the
   171  		// resulting signature would retain a free reference to the original
   172  		// receiver type parameter.
   173  		//
   174  		// Fresh type parameters are always created, even when the bounds are
   175  		// unaffected by the substitution, so that the methods of distinct
   176  		// instances of the receiver type have distinct (method-specific) type
   177  		// parameters.
   178  		//
   179  		// When t's type parameters are the variables being substituted, we are
   180  		// instantiating t itself; the caller (Checker.instance for *Signature)
   181  		// sets tparams to nil afterward, so we leave them in place here.
   182  		tparams := t.tparams
   183  		s := subst
   184  		if n := tparams.Len(); n > 0 {
   185  			// If (any) one of the signature's type parameters is in the
   186  			// substitution map, this subst call is an instantiation of the
   187  			// signature.
   188  			_, instantiating := subst.smap[tparams.At(0)]
   189  			if debug {
   190  				// When calling subst on a signature, the substitution either
   191  				// applies to all of the type parameters (all are in the map)
   192  				// or none of them (none are in the map).
   193  				for _, tp := range tparams.list() {
   194  					_, ok := subst.smap[tp]
   195  					assert(ok == instantiating)
   196  				}
   197  			}
   198  			if !instantiating {
   199  				fresh := make([]*TypeParam, n)
   200  				// We're introducing a fresh set of method type parameters
   201  				// which appear elsewhere in the signature (parameter or
   202  				// result types, or the bounds of other type parameters).
   203  				// Create an updated substitution map containing the
   204  				// existing entries plus an entry for each fresh type
   205  				// parameter so that they are substituted simultaneously
   206  				// when we proceed with the outer substitution.
   207  				smap := make(substMap, len(subst.smap)+n)
   208  				for k, v := range subst.smap {
   209  					smap[k] = v
   210  				}
   211  				for i, tp := range tparams.list() {
   212  					tname := NewTypeName(tp.Obj().Pos(), tp.Obj().Pkg(), tp.Obj().Name(), nil)
   213  					ftp := subst.check.newTypeParam(tname, nil)
   214  					ftp.index = tp.index
   215  					fresh[i] = ftp
   216  					smap[tp] = ftp
   217  					// The fresh parameter stands in for tp in the mono graph,
   218  					// so that instantiations of (e.g.) G[int].M and G[A].M
   219  					// are tracked against the same vertex as the origin's tp.
   220  					if subst.check != nil {
   221  						subst.check.mono.recordCanon(ftp, tp)
   222  					}
   223  				}
   224  				// Now that we have the updated substitution map, use it to
   225  				// compute the constraints for the fresh type parameters.
   226  				for i, tp := range tparams.list() {
   227  					fresh[i].bound = subst.check.subst(subst.pos, tp.bound, smap, subst.expanding, subst.ctxt)
   228  				}
   229  				// Continue with the fresh type parameters and updated map.
   230  				tparams = &TypeParamList{tparams: fresh}
   231  				s = &subster{
   232  					pos:       subst.pos,
   233  					smap:      smap,
   234  					check:     subst.check,
   235  					expanding: subst.expanding,
   236  					ctxt:      subst.ctxt,
   237  				}
   238  			}
   239  		}
   240  
   241  		params := s.tuple(t.params)
   242  		results := s.tuple(t.results)
   243  		if params != t.params || results != t.results || tparams != t.tparams {
   244  			return &Signature{
   245  				rparams: t.rparams,
   246  				tparams: tparams,
   247  				// instantiated signatures have a nil scope
   248  				recv:     recv,
   249  				recvold:  t.recvold,
   250  				params:   params,
   251  				results:  results,
   252  				variadic: t.variadic,
   253  			}
   254  		}
   255  
   256  	case *Union:
   257  		if terms := substList(t.terms, subst.term); terms != nil {
   258  			// term list substitution may introduce duplicate terms (unlikely but possible).
   259  			// This is ok; lazy type set computation will determine the actual type set
   260  			// in normal form.
   261  			return &Union{terms}
   262  		}
   263  
   264  	case *Interface:
   265  		methods := substList(t.methods, subst.func_)
   266  		embeddeds := substList(t.embeddeds, subst.typ)
   267  		if methods != nil || embeddeds != nil {
   268  			if methods == nil {
   269  				methods = t.methods
   270  			}
   271  			if embeddeds == nil {
   272  				embeddeds = t.embeddeds
   273  			}
   274  			iface := subst.check.newInterface()
   275  			iface.embeddeds = embeddeds
   276  			iface.embedPos = t.embedPos
   277  			iface.implicit = t.implicit
   278  			assert(t.complete) // otherwise we are copying incomplete data
   279  			iface.complete = t.complete
   280  			// If we've changed the interface type, we may need to replace its
   281  			// receiver if the receiver type is the original interface. Receivers of
   282  			// *Named type are replaced during named type expansion.
   283  			//
   284  			// Notably, it's possible to reach here and not create a new *Interface,
   285  			// even though the receiver type may be parameterized. For example:
   286  			//
   287  			//  type T[P any] interface{ m() }
   288  			//
   289  			// In this case the interface will not be substituted here, because its
   290  			// method signatures do not depend on the type parameter P, but we still
   291  			// need to create new interface methods to hold the instantiated
   292  			// receiver. This is handled by Named.expandUnderlying.
   293  			iface.methods, _ = replaceRecvType(methods, t, iface)
   294  
   295  			// If check != nil, check.newInterface will have saved the interface for later completion.
   296  			if subst.check == nil { // golang/go#61561: all newly created interfaces must be completed
   297  				iface.typeSet()
   298  			}
   299  			return iface
   300  		}
   301  
   302  	case *Map:
   303  		key := subst.typ(t.key)
   304  		elem := subst.typ(t.elem)
   305  		if key != t.key || elem != t.elem {
   306  			return &Map{key: key, elem: elem}
   307  		}
   308  
   309  	case *Chan:
   310  		elem := subst.typ(t.elem)
   311  		if elem != t.elem {
   312  			return &Chan{dir: t.dir, elem: elem}
   313  		}
   314  
   315  	case *Named:
   316  		// subst is called during expansion, so in this function we need to be
   317  		// careful not to call any methods that would cause t to be expanded: doing
   318  		// so would result in deadlock.
   319  		//
   320  		// So we call t.Origin().TypeParams() rather than t.TypeParams().
   321  		orig := t.Origin()
   322  		n := orig.TypeParams().Len()
   323  		if n == 0 {
   324  			return t // type is not parameterized
   325  		}
   326  
   327  		if t.TypeArgs().Len() != n {
   328  			return Typ[Invalid] // error reported elsewhere
   329  		}
   330  
   331  		// already instantiated
   332  		// For each (existing) type argument determine if it needs
   333  		// to be substituted; i.e., if it is or contains a type parameter
   334  		// that has a type argument for it.
   335  		if targs := substList(t.TypeArgs().list(), subst.typ); targs != nil {
   336  			// Create a new instance and populate the context to avoid endless
   337  			// recursion. The position used here is irrelevant because validation only
   338  			// occurs on t (we don't call validType on named), but we use subst.pos to
   339  			// help with debugging.
   340  			return subst.check.instance(subst.pos, orig, targs, subst.expanding, subst.ctxt)
   341  		}
   342  
   343  	case *TypeParam:
   344  		return subst.smap.lookup(t)
   345  
   346  	default:
   347  		panic("unreachable")
   348  	}
   349  
   350  	return typ
   351  }
   352  
   353  // typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
   354  // A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
   355  // where an array/slice element is accessed before it is set up.
   356  func (subst *subster) typOrNil(typ Type) Type {
   357  	if typ == nil {
   358  		return Typ[Invalid]
   359  	}
   360  	return subst.typ(typ)
   361  }
   362  
   363  func (subst *subster) var_(v *Var) *Var {
   364  	if v != nil {
   365  		if typ := subst.typ(v.typ); typ != v.typ {
   366  			return cloneVar(v, typ)
   367  		}
   368  	}
   369  	return v
   370  }
   371  
   372  func cloneVar(v *Var, typ Type) *Var {
   373  	copy := *v
   374  	copy.typ = typ
   375  	copy.origin = v.Origin()
   376  	return &copy
   377  }
   378  
   379  func (subst *subster) tuple(t *Tuple) *Tuple {
   380  	if t != nil {
   381  		if vars := substList(t.vars, subst.var_); vars != nil {
   382  			return &Tuple{vars: vars}
   383  		}
   384  	}
   385  	return t
   386  }
   387  
   388  // substList applies subst to each element of the incoming slice.
   389  // If at least one element changes, the result is a new slice with
   390  // all the (possibly updated) elements of the incoming slice;
   391  // otherwise the result it nil. The incoming slice is unchanged.
   392  func substList[T comparable](in []T, subst func(T) T) (out []T) {
   393  	for i, t := range in {
   394  		if u := subst(t); u != t {
   395  			if out == nil {
   396  				// lazily allocate a new slice on first substitution
   397  				out = make([]T, len(in))
   398  				copy(out, in)
   399  			}
   400  			out[i] = u
   401  		}
   402  	}
   403  	return
   404  }
   405  
   406  func (subst *subster) func_(f *Func) *Func {
   407  	if f != nil {
   408  		if typ := subst.typ(f.typ); typ != f.typ {
   409  			return cloneFunc(f, typ)
   410  		}
   411  	}
   412  	return f
   413  }
   414  
   415  func cloneFunc(f *Func, typ Type) *Func {
   416  	copy := *f
   417  	copy.typ = typ
   418  	copy.origin = f.Origin()
   419  	return &copy
   420  }
   421  
   422  func (subst *subster) term(t *Term) *Term {
   423  	if typ := subst.typ(t.typ); typ != t.typ {
   424  		return NewTerm(t.tilde, typ)
   425  	}
   426  	return t
   427  }
   428  
   429  // replaceRecvType updates any function receivers that have type old to have
   430  // type new. It does not modify the input slice; if modifications are required,
   431  // the input slice and any affected signatures will be copied before mutating.
   432  //
   433  // The resulting out slice contains the updated functions, and copied reports
   434  // if anything was modified.
   435  func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
   436  	out = in
   437  	for i, method := range in {
   438  		sig := method.Signature()
   439  		if sig.recv != nil && sig.recv.Type() == old {
   440  			if !copied {
   441  				// Allocate a new methods slice before mutating for the first time.
   442  				// This is defensive, as we may share methods across instantiations of
   443  				// a given interface type if they do not get substituted.
   444  				out = make([]*Func, len(in))
   445  				copy(out, in)
   446  				copied = true
   447  			}
   448  			newsig := *sig
   449  			newsig.recv = cloneVar(sig.recv, new)
   450  			out[i] = cloneFunc(method, &newsig)
   451  		}
   452  	}
   453  	return
   454  }
   455
View as plain text