subst.go

Documentation: go/types

     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 types
     8  
     9  import "go/token"
    10  
    11  type substMap map[*TypeParam]Type
    12  
    13  // makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
    14  // If targs[i] is nil, tpars[i] is not substituted.
    15  func makeSubstMap(tpars []*TypeParam, targs []Type) substMap {
    16  	assert(len(tpars) == len(targs))
    17  	proj := make(substMap, len(tpars))
    18  	for i, tpar := range tpars {
    19  		proj[tpar] = targs[i]
    20  	}
    21  	return proj
    22  }
    23  
    24  // makeRenameMap is like makeSubstMap, but creates a map used to rename type
    25  // parameters in from with the type parameters in to.
    26  func makeRenameMap(from, to []*TypeParam) substMap {
    27  	assert(len(from) == len(to))
    28  	proj := make(substMap, len(from))
    29  	for i, tpar := range from {
    30  		proj[tpar] = to[i]
    31  	}
    32  	return proj
    33  }
    34  
    35  func (m substMap) empty() bool {
    36  	return len(m) == 0
    37  }
    38  
    39  func (m substMap) lookup(tpar *TypeParam) Type {
    40  	if t := m[tpar]; t != nil {
    41  		return t
    42  	}
    43  	return tpar
    44  }
    45  
    46  // subst returns the type typ with its type parameters tpars replaced by the
    47  // corresponding type arguments targs, recursively. subst is pure in the sense
    48  // that it doesn't modify the incoming type. If a substitution took place, the
    49  // result type is different from the incoming type.
    50  //
    51  // If expanding is non-nil, it is the instance type currently being expanded.
    52  // One of expanding or ctxt must be non-nil.
    53  func (check *Checker) subst(pos token.Pos, typ Type, smap substMap, expanding *Named, ctxt *Context) Type {
    54  	assert(expanding != nil || ctxt != nil)
    55  
    56  	if smap.empty() {
    57  		return typ
    58  	}
    59  
    60  	// common cases
    61  	switch t := typ.(type) {
    62  	case *Basic:
    63  		return typ // nothing to do
    64  	case *TypeParam:
    65  		return smap.lookup(t)
    66  	}
    67  
    68  	// general case
    69  	subst := subster{
    70  		pos:       pos,
    71  		smap:      smap,
    72  		check:     check,
    73  		expanding: expanding,
    74  		ctxt:      ctxt,
    75  	}
    76  	return subst.typ(typ)
    77  }
    78  
    79  type subster struct {
    80  	pos       token.Pos
    81  	smap      substMap
    82  	check     *Checker // nil if called via Instantiate
    83  	expanding *Named   // if non-nil, the instance that is being expanded
    84  	ctxt      *Context
    85  }
    86  
    87  func (subst *subster) typ(typ Type) Type {
    88  	switch t := typ.(type) {
    89  	case nil:
    90  		// Call typOrNil if it's possible that typ is nil.
    91  		panic("nil typ")
    92  
    93  	case *Basic:
    94  		// nothing to do
    95  
    96  	case *Array:
    97  		elem := subst.typOrNil(t.elem)
    98  		if elem != t.elem {
    99  			return &Array{len: t.len, elem: elem}
   100  		}
   101  
   102  	case *Slice:
   103  		elem := subst.typOrNil(t.elem)
   104  		if elem != t.elem {
   105  			return &Slice{elem: elem}
   106  		}
   107  
   108  	case *Struct:
   109  		if fields, copied := subst.varList(t.fields); copied {
   110  			s := &Struct{fields: fields, tags: t.tags}
   111  			s.markComplete()
   112  			return s
   113  		}
   114  
   115  	case *Pointer:
   116  		base := subst.typ(t.base)
   117  		if base != t.base {
   118  			return &Pointer{base: base}
   119  		}
   120  
   121  	case *Tuple:
   122  		return subst.tuple(t)
   123  
   124  	case *Signature:
   125  		// Preserve the receiver: it is handled during *Interface and *Named type
   126  		// substitution.
   127  		//
   128  		// Naively doing the substitution here can lead to an infinite recursion in
   129  		// the case where the receiver is an interface. For example, consider the
   130  		// following declaration:
   131  		//
   132  		//  type T[A any] struct { f interface{ m() } }
   133  		//
   134  		// In this case, the type of f is an interface that is itself the receiver
   135  		// type of all of its methods. Because we have no type name to break
   136  		// cycles, substituting in the recv results in an infinite loop of
   137  		// recv->interface->recv->interface->...
   138  		recv := t.recv
   139  
   140  		params := subst.tuple(t.params)
   141  		results := subst.tuple(t.results)
   142  		if params != t.params || results != t.results {
   143  			return &Signature{
   144  				rparams: t.rparams,
   145  				// TODO(rFindley) why can't we nil out tparams here, rather than in instantiate?
   146  				tparams: t.tparams,
   147  				// instantiated signatures have a nil scope
   148  				recv:     recv,
   149  				params:   params,
   150  				results:  results,
   151  				variadic: t.variadic,
   152  			}
   153  		}
   154  
   155  	case *Union:
   156  		terms, copied := subst.termlist(t.terms)
   157  		if copied {
   158  			// term list substitution may introduce duplicate terms (unlikely but possible).
   159  			// This is ok; lazy type set computation will determine the actual type set
   160  			// in normal form.
   161  			return &Union{terms}
   162  		}
   163  
   164  	case *Interface:
   165  		methods, mcopied := subst.funcList(t.methods)
   166  		embeddeds, ecopied := subst.typeList(t.embeddeds)
   167  		if mcopied || ecopied {
   168  			iface := subst.check.newInterface()
   169  			iface.embeddeds = embeddeds
   170  			iface.implicit = t.implicit
   171  			iface.complete = t.complete
   172  			// If we've changed the interface type, we may need to replace its
   173  			// receiver if the receiver type is the original interface. Receivers of
   174  			// *Named type are replaced during named type expansion.
   175  			//
   176  			// Notably, it's possible to reach here and not create a new *Interface,
   177  			// even though the receiver type may be parameterized. For example:
   178  			//
   179  			//  type T[P any] interface{ m() }
   180  			//
   181  			// In this case the interface will not be substituted here, because its
   182  			// method signatures do not depend on the type parameter P, but we still
   183  			// need to create new interface methods to hold the instantiated
   184  			// receiver. This is handled by Named.expandUnderlying.
   185  			iface.methods, _ = replaceRecvType(methods, t, iface)
   186  			return iface
   187  		}
   188  
   189  	case *Map:
   190  		key := subst.typ(t.key)
   191  		elem := subst.typ(t.elem)
   192  		if key != t.key || elem != t.elem {
   193  			return &Map{key: key, elem: elem}
   194  		}
   195  
   196  	case *Chan:
   197  		elem := subst.typ(t.elem)
   198  		if elem != t.elem {
   199  			return &Chan{dir: t.dir, elem: elem}
   200  		}
   201  
   202  	case *Named:
   203  		// dump is for debugging
   204  		dump := func(string, ...any) {}
   205  		if subst.check != nil && trace {
   206  			subst.check.indent++
   207  			defer func() {
   208  				subst.check.indent--
   209  			}()
   210  			dump = func(format string, args ...any) {
   211  				subst.check.trace(subst.pos, format, args...)
   212  			}
   213  		}
   214  
   215  		// subst is called during expansion, so in this function we need to be
   216  		// careful not to call any methods that would cause t to be expanded: doing
   217  		// so would result in deadlock.
   218  		//
   219  		// So we call t.Origin().TypeParams() rather than t.TypeParams().
   220  		orig := t.Origin()
   221  		n := orig.TypeParams().Len()
   222  		if n == 0 {
   223  			dump(">>> %s is not parameterized", t)
   224  			return t // type is not parameterized
   225  		}
   226  
   227  		var newTArgs []Type
   228  		if t.TypeArgs().Len() != n {
   229  			return Typ[Invalid] // error reported elsewhere
   230  		}
   231  
   232  		// already instantiated
   233  		dump(">>> %s already instantiated", t)
   234  		// For each (existing) type argument targ, determine if it needs
   235  		// to be substituted; i.e., if it is or contains a type parameter
   236  		// that has a type argument for it.
   237  		for i, targ := range t.TypeArgs().list() {
   238  			dump(">>> %d targ = %s", i, targ)
   239  			new_targ := subst.typ(targ)
   240  			if new_targ != targ {
   241  				dump(">>> substituted %d targ %s => %s", i, targ, new_targ)
   242  				if newTArgs == nil {
   243  					newTArgs = make([]Type, n)
   244  					copy(newTArgs, t.TypeArgs().list())
   245  				}
   246  				newTArgs[i] = new_targ
   247  			}
   248  		}
   249  
   250  		if newTArgs == nil {
   251  			dump(">>> nothing to substitute in %s", t)
   252  			return t // nothing to substitute
   253  		}
   254  
   255  		// Create a new instance and populate the context to avoid endless
   256  		// recursion. The position used here is irrelevant because validation only
   257  		// occurs on t (we don't call validType on named), but we use subst.pos to
   258  		// help with debugging.
   259  		return subst.check.instance(subst.pos, orig, newTArgs, subst.expanding, subst.ctxt)
   260  
   261  	case *TypeParam:
   262  		return subst.smap.lookup(t)
   263  
   264  	default:
   265  		panic("unimplemented")
   266  	}
   267  
   268  	return typ
   269  }
   270  
   271  // typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
   272  // A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
   273  // where an array/slice element is accessed before it is set up.
   274  func (subst *subster) typOrNil(typ Type) Type {
   275  	if typ == nil {
   276  		return Typ[Invalid]
   277  	}
   278  	return subst.typ(typ)
   279  }
   280  
   281  func (subst *subster) var_(v *Var) *Var {
   282  	if v != nil {
   283  		if typ := subst.typ(v.typ); typ != v.typ {
   284  			return substVar(v, typ)
   285  		}
   286  	}
   287  	return v
   288  }
   289  
   290  func substVar(v *Var, typ Type) *Var {
   291  	copy := *v
   292  	copy.typ = typ
   293  	copy.origin = v.Origin()
   294  	return &copy
   295  }
   296  
   297  func (subst *subster) tuple(t *Tuple) *Tuple {
   298  	if t != nil {
   299  		if vars, copied := subst.varList(t.vars); copied {
   300  			return &Tuple{vars: vars}
   301  		}
   302  	}
   303  	return t
   304  }
   305  
   306  func (subst *subster) varList(in []*Var) (out []*Var, copied bool) {
   307  	out = in
   308  	for i, v := range in {
   309  		if w := subst.var_(v); w != v {
   310  			if !copied {
   311  				// first variable that got substituted => allocate new out slice
   312  				// and copy all variables
   313  				new := make([]*Var, len(in))
   314  				copy(new, out)
   315  				out = new
   316  				copied = true
   317  			}
   318  			out[i] = w
   319  		}
   320  	}
   321  	return
   322  }
   323  
   324  func (subst *subster) func_(f *Func) *Func {
   325  	if f != nil {
   326  		if typ := subst.typ(f.typ); typ != f.typ {
   327  			return substFunc(f, typ)
   328  		}
   329  	}
   330  	return f
   331  }
   332  
   333  func substFunc(f *Func, typ Type) *Func {
   334  	copy := *f
   335  	copy.typ = typ
   336  	copy.origin = f.Origin()
   337  	return &copy
   338  }
   339  
   340  func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) {
   341  	out = in
   342  	for i, f := range in {
   343  		if g := subst.func_(f); g != f {
   344  			if !copied {
   345  				// first function that got substituted => allocate new out slice
   346  				// and copy all functions
   347  				new := make([]*Func, len(in))
   348  				copy(new, out)
   349  				out = new
   350  				copied = true
   351  			}
   352  			out[i] = g
   353  		}
   354  	}
   355  	return
   356  }
   357  
   358  func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
   359  	out = in
   360  	for i, t := range in {
   361  		if u := subst.typ(t); u != t {
   362  			if !copied {
   363  				// first function that got substituted => allocate new out slice
   364  				// and copy all functions
   365  				new := make([]Type, len(in))
   366  				copy(new, out)
   367  				out = new
   368  				copied = true
   369  			}
   370  			out[i] = u
   371  		}
   372  	}
   373  	return
   374  }
   375  
   376  func (subst *subster) termlist(in []*Term) (out []*Term, copied bool) {
   377  	out = in
   378  	for i, t := range in {
   379  		if u := subst.typ(t.typ); u != t.typ {
   380  			if !copied {
   381  				// first function that got substituted => allocate new out slice
   382  				// and copy all functions
   383  				new := make([]*Term, len(in))
   384  				copy(new, out)
   385  				out = new
   386  				copied = true
   387  			}
   388  			out[i] = NewTerm(t.tilde, u)
   389  		}
   390  	}
   391  	return
   392  }
   393  
   394  // replaceRecvType updates any function receivers that have type old to have
   395  // type new. It does not modify the input slice; if modifications are required,
   396  // the input slice and any affected signatures will be copied before mutating.
   397  //
   398  // The resulting out slice contains the updated functions, and copied reports
   399  // if anything was modified.
   400  func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
   401  	out = in
   402  	for i, method := range in {
   403  		sig := method.Type().(*Signature)
   404  		if sig.recv != nil && sig.recv.Type() == old {
   405  			if !copied {
   406  				// Allocate a new methods slice before mutating for the first time.
   407  				// This is defensive, as we may share methods across instantiations of
   408  				// a given interface type if they do not get substituted.
   409  				out = make([]*Func, len(in))
   410  				copy(out, in)
   411  				copied = true
   412  			}
   413  			newsig := *sig
   414  			newsig.recv = substVar(sig.recv, new)
   415  			out[i] = substFunc(method, &newsig)
   416  		}
   417  	}
   418  	return
   419  }
   420
View as plain text