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