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  		targs, updated := subst.typeList(t.TypeArgs().list())
   120  		if updated {
   121  			return subst.check.newAliasInstance(subst.pos, t.orig, targs, subst.expanding, subst.ctxt)
   122  		}
   123  
   124  	case *Array:
   125  		elem := subst.typOrNil(t.elem)
   126  		if elem != t.elem {
   127  			return &Array{len: t.len, elem: elem}
   128  		}
   129  
   130  	case *Slice:
   131  		elem := subst.typOrNil(t.elem)
   132  		if elem != t.elem {
   133  			return &Slice{elem: elem}
   134  		}
   135  
   136  	case *Struct:
   137  		if fields, copied := subst.varList(t.fields); copied {
   138  			s := &Struct{fields: fields, tags: t.tags}
   139  			s.markComplete()
   140  			return s
   141  		}
   142  
   143  	case *Pointer:
   144  		base := subst.typ(t.base)
   145  		if base != t.base {
   146  			return &Pointer{base: base}
   147  		}
   148  
   149  	case *Tuple:
   150  		return subst.tuple(t)
   151  
   152  	case *Signature:
   153  		// Preserve the receiver: it is handled during *Interface and *Named type
   154  		// substitution.
   155  		//
   156  		// Naively doing the substitution here can lead to an infinite recursion in
   157  		// the case where the receiver is an interface. For example, consider the
   158  		// following declaration:
   159  		//
   160  		//  type T[A any] struct { f interface{ m() } }
   161  		//
   162  		// In this case, the type of f is an interface that is itself the receiver
   163  		// type of all of its methods. Because we have no type name to break
   164  		// cycles, substituting in the recv results in an infinite loop of
   165  		// recv->interface->recv->interface->...
   166  		recv := t.recv
   167  
   168  		params := subst.tuple(t.params)
   169  		results := subst.tuple(t.results)
   170  		if params != t.params || results != t.results {
   171  			return &Signature{
   172  				rparams: t.rparams,
   173  				// TODO(gri) why can't we nil out tparams here, rather than in instantiate?
   174  				tparams: t.tparams,
   175  				// instantiated signatures have a nil scope
   176  				recv:     recv,
   177  				params:   params,
   178  				results:  results,
   179  				variadic: t.variadic,
   180  			}
   181  		}
   182  
   183  	case *Union:
   184  		terms, copied := subst.termlist(t.terms)
   185  		if copied {
   186  			// term list substitution may introduce duplicate terms (unlikely but possible).
   187  			// This is ok; lazy type set computation will determine the actual type set
   188  			// in normal form.
   189  			return &Union{terms}
   190  		}
   191  
   192  	case *Interface:
   193  		methods, mcopied := subst.funcList(t.methods)
   194  		embeddeds, ecopied := subst.typeList(t.embeddeds)
   195  		if mcopied || ecopied {
   196  			iface := subst.check.newInterface()
   197  			iface.embeddeds = embeddeds
   198  			iface.embedPos = t.embedPos
   199  			iface.implicit = t.implicit
   200  			assert(t.complete) // otherwise we are copying incomplete data
   201  			iface.complete = t.complete
   202  			// If we've changed the interface type, we may need to replace its
   203  			// receiver if the receiver type is the original interface. Receivers of
   204  			// *Named type are replaced during named type expansion.
   205  			//
   206  			// Notably, it's possible to reach here and not create a new *Interface,
   207  			// even though the receiver type may be parameterized. For example:
   208  			//
   209  			//  type T[P any] interface{ m() }
   210  			//
   211  			// In this case the interface will not be substituted here, because its
   212  			// method signatures do not depend on the type parameter P, but we still
   213  			// need to create new interface methods to hold the instantiated
   214  			// receiver. This is handled by Named.expandUnderlying.
   215  			iface.methods, _ = replaceRecvType(methods, t, iface)
   216  
   217  			// If check != nil, check.newInterface will have saved the interface for later completion.
   218  			if subst.check == nil { // golang/go#61561: all newly created interfaces must be completed
   219  				iface.typeSet()
   220  			}
   221  			return iface
   222  		}
   223  
   224  	case *Map:
   225  		key := subst.typ(t.key)
   226  		elem := subst.typ(t.elem)
   227  		if key != t.key || elem != t.elem {
   228  			return &Map{key: key, elem: elem}
   229  		}
   230  
   231  	case *Chan:
   232  		elem := subst.typ(t.elem)
   233  		if elem != t.elem {
   234  			return &Chan{dir: t.dir, elem: elem}
   235  		}
   236  
   237  	case *Named:
   238  		// subst is called during expansion, so in this function we need to be
   239  		// careful not to call any methods that would cause t to be expanded: doing
   240  		// so would result in deadlock.
   241  		//
   242  		// So we call t.Origin().TypeParams() rather than t.TypeParams().
   243  		orig := t.Origin()
   244  		n := orig.TypeParams().Len()
   245  		if n == 0 {
   246  			return t // type is not parameterized
   247  		}
   248  
   249  		if t.TypeArgs().Len() != n {
   250  			return Typ[Invalid] // error reported elsewhere
   251  		}
   252  
   253  		// already instantiated
   254  		// For each (existing) type argument determine if it needs
   255  		// to be substituted; i.e., if it is or contains a type parameter
   256  		// that has a type argument for it.
   257  		targs, updated := subst.typeList(t.TypeArgs().list())
   258  		if updated {
   259  			// Create a new instance and populate the context to avoid endless
   260  			// recursion. The position used here is irrelevant because validation only
   261  			// occurs on t (we don't call validType on named), but we use subst.pos to
   262  			// help with debugging.
   263  			return subst.check.instance(subst.pos, orig, targs, subst.expanding, subst.ctxt)
   264  		}
   265  
   266  	case *TypeParam:
   267  		return subst.smap.lookup(t)
   268  
   269  	default:
   270  		panic("unreachable")
   271  	}
   272  
   273  	return typ
   274  }
   275  
   276  // typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
   277  // A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
   278  // where an array/slice element is accessed before it is set up.
   279  func (subst *subster) typOrNil(typ Type) Type {
   280  	if typ == nil {
   281  		return Typ[Invalid]
   282  	}
   283  	return subst.typ(typ)
   284  }
   285  
   286  func (subst *subster) var_(v *Var) *Var {
   287  	if v != nil {
   288  		if typ := subst.typ(v.typ); typ != v.typ {
   289  			return substVar(v, typ)
   290  		}
   291  	}
   292  	return v
   293  }
   294  
   295  func substVar(v *Var, typ Type) *Var {
   296  	copy := *v
   297  	copy.typ = typ
   298  	copy.origin = v.Origin()
   299  	return &copy
   300  }
   301  
   302  func (subst *subster) tuple(t *Tuple) *Tuple {
   303  	if t != nil {
   304  		if vars, copied := subst.varList(t.vars); copied {
   305  			return &Tuple{vars: vars}
   306  		}
   307  	}
   308  	return t
   309  }
   310  
   311  func (subst *subster) varList(in []*Var) (out []*Var, copied bool) {
   312  	out = in
   313  	for i, v := range in {
   314  		if w := subst.var_(v); w != v {
   315  			if !copied {
   316  				// first variable that got substituted => allocate new out slice
   317  				// and copy all variables
   318  				new := make([]*Var, len(in))
   319  				copy(new, out)
   320  				out = new
   321  				copied = true
   322  			}
   323  			out[i] = w
   324  		}
   325  	}
   326  	return
   327  }
   328  
   329  func (subst *subster) func_(f *Func) *Func {
   330  	if f != nil {
   331  		if typ := subst.typ(f.typ); typ != f.typ {
   332  			return substFunc(f, typ)
   333  		}
   334  	}
   335  	return f
   336  }
   337  
   338  func substFunc(f *Func, typ Type) *Func {
   339  	copy := *f
   340  	copy.typ = typ
   341  	copy.origin = f.Origin()
   342  	return &copy
   343  }
   344  
   345  func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) {
   346  	out = in
   347  	for i, f := range in {
   348  		if g := subst.func_(f); g != f {
   349  			if !copied {
   350  				// first function that got substituted => allocate new out slice
   351  				// and copy all functions
   352  				new := make([]*Func, len(in))
   353  				copy(new, out)
   354  				out = new
   355  				copied = true
   356  			}
   357  			out[i] = g
   358  		}
   359  	}
   360  	return
   361  }
   362  
   363  func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
   364  	out = in
   365  	for i, t := range in {
   366  		if u := subst.typ(t); u != t {
   367  			if !copied {
   368  				// first function that got substituted => allocate new out slice
   369  				// and copy all functions
   370  				new := make([]Type, len(in))
   371  				copy(new, out)
   372  				out = new
   373  				copied = true
   374  			}
   375  			out[i] = u
   376  		}
   377  	}
   378  	return
   379  }
   380  
   381  func (subst *subster) termlist(in []*Term) (out []*Term, copied bool) {
   382  	out = in
   383  	for i, t := range in {
   384  		if u := subst.typ(t.typ); u != t.typ {
   385  			if !copied {
   386  				// first function that got substituted => allocate new out slice
   387  				// and copy all functions
   388  				new := make([]*Term, len(in))
   389  				copy(new, out)
   390  				out = new
   391  				copied = true
   392  			}
   393  			out[i] = NewTerm(t.tilde, u)
   394  		}
   395  	}
   396  	return
   397  }
   398  
   399  // replaceRecvType updates any function receivers that have type old to have
   400  // type new. It does not modify the input slice; if modifications are required,
   401  // the input slice and any affected signatures will be copied before mutating.
   402  //
   403  // The resulting out slice contains the updated functions, and copied reports
   404  // if anything was modified.
   405  func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
   406  	out = in
   407  	for i, method := range in {
   408  		sig := method.Signature()
   409  		if sig.recv != nil && sig.recv.Type() == old {
   410  			if !copied {
   411  				// Allocate a new methods slice before mutating for the first time.
   412  				// This is defensive, as we may share methods across instantiations of
   413  				// a given interface type if they do not get substituted.
   414  				out = make([]*Func, len(in))
   415  				copy(out, in)
   416  				copied = true
   417  			}
   418  			newsig := *sig
   419  			newsig.recv = substVar(sig.recv, new)
   420  			out[i] = substFunc(method, &newsig)
   421  		}
   422  	}
   423  	return
   424  }
   425
View as plain text