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 instantiation of generic types
     6  // through substitution of type parameters by actual
     7  // types.
     8  
     9  package types
    10  
    11  import (
    12  	"bytes"
    13  	"fmt"
    14  	"go/token"
    15  )
    16  
    17  // TODO(rFindley) decide error codes for the errors in this file, and check
    18  //                if error spans can be improved
    19  
    20  type substMap struct {
    21  	// The targs field is currently needed for *Named type substitution.
    22  	// TODO(gri) rewrite that code, get rid of this field, and make this
    23  	//           struct just the map (proj)
    24  	targs []Type
    25  	proj  map[*_TypeParam]Type
    26  }
    27  
    28  // makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
    29  // If targs[i] is nil, tpars[i] is not substituted.
    30  func makeSubstMap(tpars []*TypeName, targs []Type) *substMap {
    31  	assert(len(tpars) == len(targs))
    32  	proj := make(map[*_TypeParam]Type, len(tpars))
    33  	for i, tpar := range tpars {
    34  		// We must expand type arguments otherwise *instance
    35  		// types end up as components in composite types.
    36  		// TODO(gri) explain why this causes problems, if it does
    37  		targ := expand(targs[i]) // possibly nil
    38  		targs[i] = targ
    39  		proj[tpar.typ.(*_TypeParam)] = targ
    40  	}
    41  	return &substMap{targs, proj}
    42  }
    43  
    44  func (m *substMap) String() string {
    45  	return fmt.Sprintf("%s", m.proj)
    46  }
    47  
    48  func (m *substMap) empty() bool {
    49  	return len(m.proj) == 0
    50  }
    51  
    52  func (m *substMap) lookup(tpar *_TypeParam) Type {
    53  	if t := m.proj[tpar]; t != nil {
    54  		return t
    55  	}
    56  	return tpar
    57  }
    58  
    59  func (check *Checker) instantiate(pos token.Pos, typ Type, targs []Type, poslist []token.Pos) (res Type) {
    60  	if trace {
    61  		check.trace(pos, "-- instantiating %s with %s", typ, typeListString(targs))
    62  		check.indent++
    63  		defer func() {
    64  			check.indent--
    65  			var under Type
    66  			if res != nil {
    67  				// Calling under() here may lead to endless instantiations.
    68  				// Test case: type T[P any] T[P]
    69  				// TODO(gri) investigate if that's a bug or to be expected.
    70  				under = res.Underlying()
    71  			}
    72  			check.trace(pos, "=> %s (under = %s)", res, under)
    73  		}()
    74  	}
    75  
    76  	assert(len(poslist) <= len(targs))
    77  
    78  	// TODO(gri) What is better here: work with TypeParams, or work with TypeNames?
    79  	var tparams []*TypeName
    80  	switch t := typ.(type) {
    81  	case *Named:
    82  		tparams = t.tparams
    83  	case *Signature:
    84  		tparams = t.tparams
    85  		defer func() {
    86  			// If we had an unexpected failure somewhere don't panic below when
    87  			// asserting res.(*Signature). Check for *Signature in case Typ[Invalid]
    88  			// is returned.
    89  			if _, ok := res.(*Signature); !ok {
    90  				return
    91  			}
    92  			// If the signature doesn't use its type parameters, subst
    93  			// will not make a copy. In that case, make a copy now (so
    94  			// we can set tparams to nil w/o causing side-effects).
    95  			if t == res {
    96  				copy := *t
    97  				res = &copy
    98  			}
    99  			// After instantiating a generic signature, it is not generic
   100  			// anymore; we need to set tparams to nil.
   101  			res.(*Signature).tparams = nil
   102  		}()
   103  
   104  	default:
   105  		check.dump("%v: cannot instantiate %v", pos, typ)
   106  		unreachable() // only defined types and (defined) functions can be generic
   107  	}
   108  
   109  	// the number of supplied types must match the number of type parameters
   110  	if len(targs) != len(tparams) {
   111  		// TODO(gri) provide better error message
   112  		check.errorf(atPos(pos), _Todo, "got %d arguments but %d type parameters", len(targs), len(tparams))
   113  		return Typ[Invalid]
   114  	}
   115  
   116  	if len(tparams) == 0 {
   117  		return typ // nothing to do (minor optimization)
   118  	}
   119  
   120  	smap := makeSubstMap(tparams, targs)
   121  
   122  	// check bounds
   123  	for i, tname := range tparams {
   124  		tpar := tname.typ.(*_TypeParam)
   125  		iface := tpar.Bound()
   126  		if iface.Empty() {
   127  			continue // no type bound
   128  		}
   129  
   130  		targ := targs[i]
   131  
   132  		// best position for error reporting
   133  		pos := pos
   134  		if i < len(poslist) {
   135  			pos = poslist[i]
   136  		}
   137  
   138  		// The type parameter bound is parameterized with the same type parameters
   139  		// as the instantiated type; before we can use it for bounds checking we
   140  		// need to instantiate it with the type arguments with which we instantiate
   141  		// the parameterized type.
   142  		iface = check.subst(pos, iface, smap).(*Interface)
   143  
   144  		// targ must implement iface (methods)
   145  		// - check only if we have methods
   146  		check.completeInterface(token.NoPos, iface)
   147  		if len(iface.allMethods) > 0 {
   148  			// If the type argument is a pointer to a type parameter, the type argument's
   149  			// method set is empty.
   150  			// TODO(gri) is this what we want? (spec question)
   151  			if base, isPtr := deref(targ); isPtr && asTypeParam(base) != nil {
   152  				check.errorf(atPos(pos), 0, "%s has no methods", targ)
   153  				break
   154  			}
   155  			if m, wrong := check.missingMethod(targ, iface, true); m != nil {
   156  				// TODO(gri) needs to print updated name to avoid major confusion in error message!
   157  				//           (print warning for now)
   158  				// Old warning:
   159  				// check.softErrorf(pos, "%s does not satisfy %s (warning: name not updated) = %s (missing method %s)", targ, tpar.bound, iface, m)
   160  				if m.name == "==" {
   161  					// We don't want to report "missing method ==".
   162  					check.softErrorf(atPos(pos), 0, "%s does not satisfy comparable", targ)
   163  				} else if wrong != nil {
   164  					// TODO(gri) This can still report uninstantiated types which makes the error message
   165  					//           more difficult to read then necessary.
   166  					// TODO(rFindley) should this use parentheses rather than ':' for qualification?
   167  					check.softErrorf(atPos(pos), _Todo,
   168  						"%s does not satisfy %s: wrong method signature\n\tgot  %s\n\twant %s",
   169  						targ, tpar.bound, wrong, m,
   170  					)
   171  				} else {
   172  					check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (missing method %s)", targ, tpar.bound, m.name)
   173  				}
   174  				break
   175  			}
   176  		}
   177  
   178  		// targ's underlying type must also be one of the interface types listed, if any
   179  		if iface.allTypes == nil {
   180  			continue // nothing to do
   181  		}
   182  
   183  		// If targ is itself a type parameter, each of its possible types, but at least one, must be in the
   184  		// list of iface types (i.e., the targ type list must be a non-empty subset of the iface types).
   185  		if targ := asTypeParam(targ); targ != nil {
   186  			targBound := targ.Bound()
   187  			if targBound.allTypes == nil {
   188  				check.softErrorf(atPos(pos), _Todo, "%s does not satisfy %s (%s has no type constraints)", targ, tpar.bound, targ)
   189  				break
   190  			}
   191  			for _, t := range unpackType(targBound.allTypes) {
   192  				if !iface.isSatisfiedBy(t) {
   193  					// TODO(gri) match this error message with the one below (or vice versa)
   194  					check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (%s type constraint %s not found in %s)", targ, tpar.bound, targ, t, iface.allTypes)
   195  					break
   196  				}
   197  			}
   198  			break
   199  		}
   200  
   201  		// Otherwise, targ's type or underlying type must also be one of the interface types listed, if any.
   202  		if !iface.isSatisfiedBy(targ) {
   203  			check.softErrorf(atPos(pos), _Todo, "%s does not satisfy %s (%s or %s not found in %s)", targ, tpar.bound, targ, under(targ), iface.allTypes)
   204  			break
   205  		}
   206  	}
   207  
   208  	return check.subst(pos, typ, smap)
   209  }
   210  
   211  // subst returns the type typ with its type parameters tpars replaced by
   212  // the corresponding type arguments targs, recursively.
   213  // subst is functional in the sense that it doesn't modify the incoming
   214  // type. If a substitution took place, the result type is different from
   215  // from the incoming type.
   216  func (check *Checker) subst(pos token.Pos, typ Type, smap *substMap) Type {
   217  	if smap.empty() {
   218  		return typ
   219  	}
   220  
   221  	// common cases
   222  	switch t := typ.(type) {
   223  	case *Basic:
   224  		return typ // nothing to do
   225  	case *_TypeParam:
   226  		return smap.lookup(t)
   227  	}
   228  
   229  	// general case
   230  	subst := subster{check, pos, make(map[Type]Type), smap}
   231  	return subst.typ(typ)
   232  }
   233  
   234  type subster struct {
   235  	check *Checker
   236  	pos   token.Pos
   237  	cache map[Type]Type
   238  	smap  *substMap
   239  }
   240  
   241  func (subst *subster) typ(typ Type) Type {
   242  	switch t := typ.(type) {
   243  	case nil:
   244  		// Call typOrNil if it's possible that typ is nil.
   245  		panic("nil typ")
   246  
   247  	case *Basic, *bottom, *top:
   248  		// nothing to do
   249  
   250  	case *Array:
   251  		elem := subst.typOrNil(t.elem)
   252  		if elem != t.elem {
   253  			return &Array{len: t.len, elem: elem}
   254  		}
   255  
   256  	case *Slice:
   257  		elem := subst.typOrNil(t.elem)
   258  		if elem != t.elem {
   259  			return &Slice{elem: elem}
   260  		}
   261  
   262  	case *Struct:
   263  		if fields, copied := subst.varList(t.fields); copied {
   264  			return &Struct{fields: fields, tags: t.tags}
   265  		}
   266  
   267  	case *Pointer:
   268  		base := subst.typ(t.base)
   269  		if base != t.base {
   270  			return &Pointer{base: base}
   271  		}
   272  
   273  	case *Tuple:
   274  		return subst.tuple(t)
   275  
   276  	case *Signature:
   277  		// TODO(gri) rethink the recv situation with respect to methods on parameterized types
   278  		// recv := subst.var_(t.recv) // TODO(gri) this causes a stack overflow - explain
   279  		recv := t.recv
   280  		params := subst.tuple(t.params)
   281  		results := subst.tuple(t.results)
   282  		if recv != t.recv || params != t.params || results != t.results {
   283  			return &Signature{
   284  				rparams: t.rparams,
   285  				// TODO(rFindley) why can't we nil out tparams here, rather than in
   286  				//                instantiate above?
   287  				tparams:  t.tparams,
   288  				scope:    t.scope,
   289  				recv:     recv,
   290  				params:   params,
   291  				results:  results,
   292  				variadic: t.variadic,
   293  			}
   294  		}
   295  
   296  	case *_Sum:
   297  		types, copied := subst.typeList(t.types)
   298  		if copied {
   299  			// Don't do it manually, with a Sum literal: the new
   300  			// types list may not be unique and NewSum may remove
   301  			// duplicates.
   302  			return _NewSum(types)
   303  		}
   304  
   305  	case *Interface:
   306  		methods, mcopied := subst.funcList(t.methods)
   307  		types := t.types
   308  		if t.types != nil {
   309  			types = subst.typ(t.types)
   310  		}
   311  		embeddeds, ecopied := subst.typeList(t.embeddeds)
   312  		if mcopied || types != t.types || ecopied {
   313  			iface := &Interface{methods: methods, types: types, embeddeds: embeddeds}
   314  			subst.check.posMap[iface] = subst.check.posMap[t] // satisfy completeInterface requirement
   315  			subst.check.completeInterface(token.NoPos, iface)
   316  			return iface
   317  		}
   318  
   319  	case *Map:
   320  		key := subst.typ(t.key)
   321  		elem := subst.typ(t.elem)
   322  		if key != t.key || elem != t.elem {
   323  			return &Map{key: key, elem: elem}
   324  		}
   325  
   326  	case *Chan:
   327  		elem := subst.typ(t.elem)
   328  		if elem != t.elem {
   329  			return &Chan{dir: t.dir, elem: elem}
   330  		}
   331  
   332  	case *Named:
   333  		subst.check.indent++
   334  		defer func() {
   335  			subst.check.indent--
   336  		}()
   337  		dump := func(format string, args ...interface{}) {
   338  			if trace {
   339  				subst.check.trace(subst.pos, format, args...)
   340  			}
   341  		}
   342  
   343  		if t.tparams == nil {
   344  			dump(">>> %s is not parameterized", t)
   345  			return t // type is not parameterized
   346  		}
   347  
   348  		var newTargs []Type
   349  
   350  		if len(t.targs) > 0 {
   351  			// already instantiated
   352  			dump(">>> %s already instantiated", t)
   353  			assert(len(t.targs) == len(t.tparams))
   354  			// For each (existing) type argument targ, determine if it needs
   355  			// to be substituted; i.e., if it is or contains a type parameter
   356  			// that has a type argument for it.
   357  			for i, targ := range t.targs {
   358  				dump(">>> %d targ = %s", i, targ)
   359  				newTarg := subst.typ(targ)
   360  				if newTarg != targ {
   361  					dump(">>> substituted %d targ %s => %s", i, targ, newTarg)
   362  					if newTargs == nil {
   363  						newTargs = make([]Type, len(t.tparams))
   364  						copy(newTargs, t.targs)
   365  					}
   366  					newTargs[i] = newTarg
   367  				}
   368  			}
   369  
   370  			if newTargs == nil {
   371  				dump(">>> nothing to substitute in %s", t)
   372  				return t // nothing to substitute
   373  			}
   374  		} else {
   375  			// not yet instantiated
   376  			dump(">>> first instantiation of %s", t)
   377  			// TODO(rFindley) can we instead subst the tparam types here?
   378  			newTargs = subst.smap.targs
   379  		}
   380  
   381  		// before creating a new named type, check if we have this one already
   382  		h := instantiatedHash(t, newTargs)
   383  		dump(">>> new type hash: %s", h)
   384  		if named, found := subst.check.typMap[h]; found {
   385  			dump(">>> found %s", named)
   386  			subst.cache[t] = named
   387  			return named
   388  		}
   389  
   390  		// create a new named type and populate caches to avoid endless recursion
   391  		tname := NewTypeName(subst.pos, t.obj.pkg, t.obj.name, nil)
   392  		named := subst.check.newNamed(tname, t.underlying, t.methods) // method signatures are updated lazily
   393  		named.tparams = t.tparams                                     // new type is still parameterized
   394  		named.targs = newTargs
   395  		subst.check.typMap[h] = named
   396  		subst.cache[t] = named
   397  
   398  		// do the substitution
   399  		dump(">>> subst %s with %s (new: %s)", t.underlying, subst.smap, newTargs)
   400  		named.underlying = subst.typOrNil(t.underlying)
   401  		named.orig = named.underlying // for cycle detection (Checker.validType)
   402  
   403  		return named
   404  
   405  	case *_TypeParam:
   406  		return subst.smap.lookup(t)
   407  
   408  	case *instance:
   409  		// TODO(gri) can we avoid the expansion here and just substitute the type parameters?
   410  		return subst.typ(t.expand())
   411  
   412  	default:
   413  		panic("unimplemented")
   414  	}
   415  
   416  	return typ
   417  }
   418  
   419  // TODO(gri) Eventually, this should be more sophisticated.
   420  //           It won't work correctly for locally declared types.
   421  func instantiatedHash(typ *Named, targs []Type) string {
   422  	var buf bytes.Buffer
   423  	writeTypeName(&buf, typ.obj, nil)
   424  	buf.WriteByte('[')
   425  	writeTypeList(&buf, targs, nil, nil)
   426  	buf.WriteByte(']')
   427  
   428  	// With respect to the represented type, whether a
   429  	// type is fully expanded or stored as instance
   430  	// does not matter - they are the same types.
   431  	// Remove the instanceMarkers printed for instances.
   432  	res := buf.Bytes()
   433  	i := 0
   434  	for _, b := range res {
   435  		if b != instanceMarker {
   436  			res[i] = b
   437  			i++
   438  		}
   439  	}
   440  
   441  	return string(res[:i])
   442  }
   443  
   444  func typeListString(list []Type) string {
   445  	var buf bytes.Buffer
   446  	writeTypeList(&buf, list, nil, nil)
   447  	return buf.String()
   448  }
   449  
   450  // typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
   451  // A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
   452  // where an array/slice element is accessed before it is set up.
   453  func (subst *subster) typOrNil(typ Type) Type {
   454  	if typ == nil {
   455  		return Typ[Invalid]
   456  	}
   457  	return subst.typ(typ)
   458  }
   459  
   460  func (subst *subster) var_(v *Var) *Var {
   461  	if v != nil {
   462  		if typ := subst.typ(v.typ); typ != v.typ {
   463  			copy := *v
   464  			copy.typ = typ
   465  			return &copy
   466  		}
   467  	}
   468  	return v
   469  }
   470  
   471  func (subst *subster) tuple(t *Tuple) *Tuple {
   472  	if t != nil {
   473  		if vars, copied := subst.varList(t.vars); copied {
   474  			return &Tuple{vars: vars}
   475  		}
   476  	}
   477  	return t
   478  }
   479  
   480  func (subst *subster) varList(in []*Var) (out []*Var, copied bool) {
   481  	out = in
   482  	for i, v := range in {
   483  		if w := subst.var_(v); w != v {
   484  			if !copied {
   485  				// first variable that got substituted => allocate new out slice
   486  				// and copy all variables
   487  				new := make([]*Var, len(in))
   488  				copy(new, out)
   489  				out = new
   490  				copied = true
   491  			}
   492  			out[i] = w
   493  		}
   494  	}
   495  	return
   496  }
   497  
   498  func (subst *subster) func_(f *Func) *Func {
   499  	if f != nil {
   500  		if typ := subst.typ(f.typ); typ != f.typ {
   501  			copy := *f
   502  			copy.typ = typ
   503  			return &copy
   504  		}
   505  	}
   506  	return f
   507  }
   508  
   509  func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) {
   510  	out = in
   511  	for i, f := range in {
   512  		if g := subst.func_(f); g != f {
   513  			if !copied {
   514  				// first function that got substituted => allocate new out slice
   515  				// and copy all functions
   516  				new := make([]*Func, len(in))
   517  				copy(new, out)
   518  				out = new
   519  				copied = true
   520  			}
   521  			out[i] = g
   522  		}
   523  	}
   524  	return
   525  }
   526  
   527  func (subst *subster) typeList(in []Type) (out []Type, copied bool) {
   528  	out = in
   529  	for i, t := range in {
   530  		if u := subst.typ(t); u != t {
   531  			if !copied {
   532  				// first function that got substituted => allocate new out slice
   533  				// and copy all functions
   534  				new := make([]Type, len(in))
   535  				copy(new, out)
   536  				out = new
   537  				copied = true
   538  			}
   539  			out[i] = u
   540  		}
   541  	}
   542  	return
   543  }
   544
View as plain text