subst.go

Documentation: go/types

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