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