subst.go

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