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  		params := subst.tuple(t.params)
   165  		results := subst.tuple(t.results)
   166  		if params != t.params || results != t.results {
   167  			return &Signature{
   168  				rparams: t.rparams,
   169  				// TODO(gri) why can't we nil out tparams here, rather than in instantiate?
   170  				tparams: t.tparams,
   171  				// instantiated signatures have a nil scope
   172  				recv:     recv,
   173  				params:   params,
   174  				results:  results,
   175  				variadic: t.variadic,
   176  			}
   177  		}
   178  
   179  	case *Union:
   180  		if terms := substList(t.terms, subst.term); terms != nil {
   181  			// term list substitution may introduce duplicate terms (unlikely but possible).
   182  			// This is ok; lazy type set computation will determine the actual type set
   183  			// in normal form.
   184  			return &Union{terms}
   185  		}
   186  
   187  	case *Interface:
   188  		methods := substList(t.methods, subst.func_)
   189  		embeddeds := substList(t.embeddeds, subst.typ)
   190  		if methods != nil || embeddeds != nil {
   191  			if methods == nil {
   192  				methods = t.methods
   193  			}
   194  			if embeddeds == nil {
   195  				embeddeds = t.embeddeds
   196  			}
   197  			iface := subst.check.newInterface()
   198  			iface.embeddeds = embeddeds
   199  			iface.embedPos = t.embedPos
   200  			iface.implicit = t.implicit
   201  			assert(t.complete) // otherwise we are copying incomplete data
   202  			iface.complete = t.complete
   203  			// If we've changed the interface type, we may need to replace its
   204  			// receiver if the receiver type is the original interface. Receivers of
   205  			// *Named type are replaced during named type expansion.
   206  			//
   207  			// Notably, it's possible to reach here and not create a new *Interface,
   208  			// even though the receiver type may be parameterized. For example:
   209  			//
   210  			//  type T[P any] interface{ m() }
   211  			//
   212  			// In this case the interface will not be substituted here, because its
   213  			// method signatures do not depend on the type parameter P, but we still
   214  			// need to create new interface methods to hold the instantiated
   215  			// receiver. This is handled by Named.expandUnderlying.
   216  			iface.methods, _ = replaceRecvType(methods, t, iface)
   217  
   218  			// If check != nil, check.newInterface will have saved the interface for later completion.
   219  			if subst.check == nil { // golang/go#61561: all newly created interfaces must be completed
   220  				iface.typeSet()
   221  			}
   222  			return iface
   223  		}
   224  
   225  	case *Map:
   226  		key := subst.typ(t.key)
   227  		elem := subst.typ(t.elem)
   228  		if key != t.key || elem != t.elem {
   229  			return &Map{key: key, elem: elem}
   230  		}
   231  
   232  	case *Chan:
   233  		elem := subst.typ(t.elem)
   234  		if elem != t.elem {
   235  			return &Chan{dir: t.dir, elem: elem}
   236  		}
   237  
   238  	case *Named:
   239  		// subst is called during expansion, so in this function we need to be
   240  		// careful not to call any methods that would cause t to be expanded: doing
   241  		// so would result in deadlock.
   242  		//
   243  		// So we call t.Origin().TypeParams() rather than t.TypeParams().
   244  		orig := t.Origin()
   245  		n := orig.TypeParams().Len()
   246  		if n == 0 {
   247  			return t // type is not parameterized
   248  		}
   249  
   250  		if t.TypeArgs().Len() != n {
   251  			return Typ[Invalid] // error reported elsewhere
   252  		}
   253  
   254  		// already instantiated
   255  		// For each (existing) type argument 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  		if targs := substList(t.TypeArgs().list(), subst.typ); targs != nil {
   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 cloneVar(v, typ)
   290  		}
   291  	}
   292  	return v
   293  }
   294  
   295  func cloneVar(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 := substList(t.vars, subst.var_); vars != nil {
   305  			return &Tuple{vars: vars}
   306  		}
   307  	}
   308  	return t
   309  }
   310  
   311  // substList applies subst to each element of the incoming slice.
   312  // If at least one element changes, the result is a new slice with
   313  // all the (possibly updated) elements of the incoming slice;
   314  // otherwise the result it nil. The incoming slice is unchanged.
   315  func substList[T comparable](in []T, subst func(T) T) (out []T) {
   316  	for i, t := range in {
   317  		if u := subst(t); u != t {
   318  			if out == nil {
   319  				// lazily allocate a new slice on first substitution
   320  				out = make([]T, len(in))
   321  				copy(out, in)
   322  			}
   323  			out[i] = u
   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 cloneFunc(f, typ)
   333  		}
   334  	}
   335  	return f
   336  }
   337  
   338  func cloneFunc(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) term(t *Term) *Term {
   346  	if typ := subst.typ(t.typ); typ != t.typ {
   347  		return NewTerm(t.tilde, typ)
   348  	}
   349  	return t
   350  }
   351  
   352  // replaceRecvType updates any function receivers that have type old to have
   353  // type new. It does not modify the input slice; if modifications are required,
   354  // the input slice and any affected signatures will be copied before mutating.
   355  //
   356  // The resulting out slice contains the updated functions, and copied reports
   357  // if anything was modified.
   358  func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
   359  	out = in
   360  	for i, method := range in {
   361  		sig := method.Signature()
   362  		if sig.recv != nil && sig.recv.Type() == old {
   363  			if !copied {
   364  				// Allocate a new methods slice before mutating for the first time.
   365  				// This is defensive, as we may share methods across instantiations of
   366  				// a given interface type if they do not get substituted.
   367  				out = make([]*Func, len(in))
   368  				copy(out, in)
   369  				copied = true
   370  			}
   371  			newsig := *sig
   372  			newsig.recv = cloneVar(sig.recv, new)
   373  			out[i] = cloneFunc(method, &newsig)
   374  		}
   375  	}
   376  	return
   377  }
   378
View as plain text