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