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