Source file src/cmd/compile/internal/typecheck/subr.go

     1  // Copyright 2009 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  package typecheck
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"sort"
    11  	"strconv"
    12  	"strings"
    13  
    14  	"cmd/compile/internal/base"
    15  	"cmd/compile/internal/ir"
    16  	"cmd/compile/internal/types"
    17  	"cmd/internal/objabi"
    18  	"cmd/internal/src"
    19  )
    20  
    21  func AssignConv(n ir.Node, t *types.Type, context string) ir.Node {
    22  	return assignconvfn(n, t, func() string { return context })
    23  }
    24  
    25  // DotImportRefs maps idents introduced by importDot back to the
    26  // ir.PkgName they were dot-imported through.
    27  var DotImportRefs map[*ir.Ident]*ir.PkgName
    28  
    29  // LookupNum looks up the symbol starting with prefix and ending with
    30  // the decimal n. If prefix is too long, LookupNum panics.
    31  func LookupNum(prefix string, n int) *types.Sym {
    32  	var buf [20]byte // plenty long enough for all current users
    33  	copy(buf[:], prefix)
    34  	b := strconv.AppendInt(buf[:len(prefix)], int64(n), 10)
    35  	return types.LocalPkg.LookupBytes(b)
    36  }
    37  
    38  // Given funarg struct list, return list of fn args.
    39  func NewFuncParams(tl *types.Type, mustname bool) []*ir.Field {
    40  	var args []*ir.Field
    41  	gen := 0
    42  	for _, t := range tl.Fields().Slice() {
    43  		s := t.Sym
    44  		if mustname && (s == nil || s.Name == "_") {
    45  			// invent a name so that we can refer to it in the trampoline
    46  			s = LookupNum(".anon", gen)
    47  			gen++
    48  		} else if s != nil && s.Pkg != types.LocalPkg {
    49  			// TODO(mdempsky): Preserve original position, name, and package.
    50  			s = Lookup(s.Name)
    51  		}
    52  		a := ir.NewField(base.Pos, s, nil, t.Type)
    53  		a.Pos = t.Pos
    54  		a.IsDDD = t.IsDDD()
    55  		args = append(args, a)
    56  	}
    57  
    58  	return args
    59  }
    60  
    61  // newname returns a new ONAME Node associated with symbol s.
    62  func NewName(s *types.Sym) *ir.Name {
    63  	n := ir.NewNameAt(base.Pos, s)
    64  	n.Curfn = ir.CurFunc
    65  	return n
    66  }
    67  
    68  // NodAddr returns a node representing &n at base.Pos.
    69  func NodAddr(n ir.Node) *ir.AddrExpr {
    70  	return NodAddrAt(base.Pos, n)
    71  }
    72  
    73  // nodAddrPos returns a node representing &n at position pos.
    74  func NodAddrAt(pos src.XPos, n ir.Node) *ir.AddrExpr {
    75  	n = markAddrOf(n)
    76  	return ir.NewAddrExpr(pos, n)
    77  }
    78  
    79  func markAddrOf(n ir.Node) ir.Node {
    80  	if IncrementalAddrtaken {
    81  		// We can only do incremental addrtaken computation when it is ok
    82  		// to typecheck the argument of the OADDR. That's only safe after the
    83  		// main typecheck has completed, and not loading the inlined body.
    84  		// The argument to OADDR needs to be typechecked because &x[i] takes
    85  		// the address of x if x is an array, but not if x is a slice.
    86  		// Note: OuterValue doesn't work correctly until n is typechecked.
    87  		n = typecheck(n, ctxExpr)
    88  		if x := ir.OuterValue(n); x.Op() == ir.ONAME {
    89  			x.Name().SetAddrtaken(true)
    90  		}
    91  	} else {
    92  		// Remember that we built an OADDR without computing the Addrtaken bit for
    93  		// its argument. We'll do that later in bulk using computeAddrtaken.
    94  		DirtyAddrtaken = true
    95  	}
    96  	return n
    97  }
    98  
    99  // If IncrementalAddrtaken is false, we do not compute Addrtaken for an OADDR Node
   100  // when it is built. The Addrtaken bits are set in bulk by computeAddrtaken.
   101  // If IncrementalAddrtaken is true, then when an OADDR Node is built the Addrtaken
   102  // field of its argument is updated immediately.
   103  var IncrementalAddrtaken = false
   104  
   105  // If DirtyAddrtaken is true, then there are OADDR whose corresponding arguments
   106  // have not yet been marked as Addrtaken.
   107  var DirtyAddrtaken = false
   108  
   109  func ComputeAddrtaken(top []ir.Node) {
   110  	for _, n := range top {
   111  		var doVisit func(n ir.Node)
   112  		doVisit = func(n ir.Node) {
   113  			if n.Op() == ir.OADDR {
   114  				if x := ir.OuterValue(n.(*ir.AddrExpr).X); x.Op() == ir.ONAME {
   115  					x.Name().SetAddrtaken(true)
   116  					if x.Name().IsClosureVar() {
   117  						// Mark the original variable as Addrtaken so that capturevars
   118  						// knows not to pass it by value.
   119  						x.Name().Defn.Name().SetAddrtaken(true)
   120  					}
   121  				}
   122  			}
   123  			if n.Op() == ir.OCLOSURE {
   124  				ir.VisitList(n.(*ir.ClosureExpr).Func.Body, doVisit)
   125  			}
   126  		}
   127  		ir.Visit(n, doVisit)
   128  	}
   129  }
   130  
   131  func NodNil() ir.Node {
   132  	n := ir.NewNilExpr(base.Pos)
   133  	n.SetType(types.Types[types.TNIL])
   134  	return n
   135  }
   136  
   137  // AddImplicitDots finds missing fields in obj.field that
   138  // will give the shortest unique addressing and
   139  // modifies the tree with missing field names.
   140  func AddImplicitDots(n *ir.SelectorExpr) *ir.SelectorExpr {
   141  	n.X = typecheck(n.X, ctxType|ctxExpr)
   142  	if n.X.Diag() {
   143  		n.SetDiag(true)
   144  	}
   145  	t := n.X.Type()
   146  	if t == nil {
   147  		return n
   148  	}
   149  
   150  	if n.X.Op() == ir.OTYPE {
   151  		return n
   152  	}
   153  
   154  	s := n.Sel
   155  	if s == nil {
   156  		return n
   157  	}
   158  
   159  	switch path, ambig := dotpath(s, t, nil, false); {
   160  	case path != nil:
   161  		// rebuild elided dots
   162  		for c := len(path) - 1; c >= 0; c-- {
   163  			dot := ir.NewSelectorExpr(n.Pos(), ir.ODOT, n.X, path[c].field.Sym)
   164  			dot.SetImplicit(true)
   165  			dot.SetType(path[c].field.Type)
   166  			n.X = dot
   167  		}
   168  	case ambig:
   169  		base.Errorf("ambiguous selector %v", n)
   170  		n.X = nil
   171  	}
   172  
   173  	return n
   174  }
   175  
   176  // CalcMethods calculates all the methods (including embedding) of a non-interface
   177  // type t.
   178  func CalcMethods(t *types.Type) {
   179  	if t == nil || t.AllMethods().Len() != 0 {
   180  		return
   181  	}
   182  
   183  	// mark top-level method symbols
   184  	// so that expand1 doesn't consider them.
   185  	for _, f := range t.Methods().Slice() {
   186  		f.Sym.SetUniq(true)
   187  	}
   188  
   189  	// generate all reachable methods
   190  	slist = slist[:0]
   191  	expand1(t, true)
   192  
   193  	// check each method to be uniquely reachable
   194  	var ms []*types.Field
   195  	for i, sl := range slist {
   196  		slist[i].field = nil
   197  		sl.field.Sym.SetUniq(false)
   198  
   199  		var f *types.Field
   200  		path, _ := dotpath(sl.field.Sym, t, &f, false)
   201  		if path == nil {
   202  			continue
   203  		}
   204  
   205  		// dotpath may have dug out arbitrary fields, we only want methods.
   206  		if !f.IsMethod() {
   207  			continue
   208  		}
   209  
   210  		// add it to the base type method list
   211  		f = f.Copy()
   212  		f.Embedded = 1 // needs a trampoline
   213  		for _, d := range path {
   214  			if d.field.Type.IsPtr() {
   215  				f.Embedded = 2
   216  				break
   217  			}
   218  		}
   219  		ms = append(ms, f)
   220  	}
   221  
   222  	for _, f := range t.Methods().Slice() {
   223  		f.Sym.SetUniq(false)
   224  	}
   225  
   226  	ms = append(ms, t.Methods().Slice()...)
   227  	sort.Sort(types.MethodsByName(ms))
   228  	t.SetAllMethods(ms)
   229  }
   230  
   231  // adddot1 returns the number of fields or methods named s at depth d in Type t.
   232  // If exactly one exists, it will be returned in *save (if save is not nil),
   233  // and dotlist will contain the path of embedded fields traversed to find it,
   234  // in reverse order. If none exist, more will indicate whether t contains any
   235  // embedded fields at depth d, so callers can decide whether to retry at
   236  // a greater depth.
   237  func adddot1(s *types.Sym, t *types.Type, d int, save **types.Field, ignorecase bool) (c int, more bool) {
   238  	if t.Recur() {
   239  		return
   240  	}
   241  	t.SetRecur(true)
   242  	defer t.SetRecur(false)
   243  
   244  	var u *types.Type
   245  	d--
   246  	if d < 0 {
   247  		// We've reached our target depth. If t has any fields/methods
   248  		// named s, then we're done. Otherwise, we still need to check
   249  		// below for embedded fields.
   250  		c = lookdot0(s, t, save, ignorecase)
   251  		if c != 0 {
   252  			return c, false
   253  		}
   254  	}
   255  
   256  	u = t
   257  	if u.IsPtr() {
   258  		u = u.Elem()
   259  	}
   260  	if !u.IsStruct() && !u.IsInterface() {
   261  		return c, false
   262  	}
   263  
   264  	var fields *types.Fields
   265  	if u.IsStruct() {
   266  		fields = u.Fields()
   267  	} else {
   268  		fields = u.AllMethods()
   269  	}
   270  	for _, f := range fields.Slice() {
   271  		if f.Embedded == 0 || f.Sym == nil {
   272  			continue
   273  		}
   274  		if d < 0 {
   275  			// Found an embedded field at target depth.
   276  			return c, true
   277  		}
   278  		a, more1 := adddot1(s, f.Type, d, save, ignorecase)
   279  		if a != 0 && c == 0 {
   280  			dotlist[d].field = f
   281  		}
   282  		c += a
   283  		if more1 {
   284  			more = true
   285  		}
   286  	}
   287  
   288  	return c, more
   289  }
   290  
   291  // dotlist is used by adddot1 to record the path of embedded fields
   292  // used to access a target field or method.
   293  // Must be non-nil so that dotpath returns a non-nil slice even if d is zero.
   294  var dotlist = make([]dlist, 10)
   295  
   296  // Convert node n for assignment to type t.
   297  func assignconvfn(n ir.Node, t *types.Type, context func() string) ir.Node {
   298  	if n == nil || n.Type() == nil || n.Type().Broke() {
   299  		return n
   300  	}
   301  
   302  	if t.Kind() == types.TBLANK && n.Type().Kind() == types.TNIL {
   303  		base.Errorf("use of untyped nil")
   304  	}
   305  
   306  	n = convlit1(n, t, false, context)
   307  	if n.Type() == nil {
   308  		return n
   309  	}
   310  	if t.Kind() == types.TBLANK {
   311  		return n
   312  	}
   313  
   314  	// Convert ideal bool from comparison to plain bool
   315  	// if the next step is non-bool (like interface{}).
   316  	if n.Type() == types.UntypedBool && !t.IsBoolean() {
   317  		if n.Op() == ir.ONAME || n.Op() == ir.OLITERAL {
   318  			r := ir.NewConvExpr(base.Pos, ir.OCONVNOP, nil, n)
   319  			r.SetType(types.Types[types.TBOOL])
   320  			r.SetTypecheck(1)
   321  			r.SetImplicit(true)
   322  			n = r
   323  		}
   324  	}
   325  
   326  	if types.Identical(n.Type(), t) {
   327  		return n
   328  	}
   329  
   330  	op, why := Assignop(n.Type(), t)
   331  	if op == ir.OXXX {
   332  		base.Errorf("cannot use %L as type %v in %s%s", n, t, context(), why)
   333  		op = ir.OCONV
   334  	}
   335  
   336  	r := ir.NewConvExpr(base.Pos, op, t, n)
   337  	r.SetTypecheck(1)
   338  	r.SetImplicit(true)
   339  	return r
   340  }
   341  
   342  // Is type src assignment compatible to type dst?
   343  // If so, return op code to use in conversion.
   344  // If not, return OXXX. In this case, the string return parameter may
   345  // hold a reason why. In all other cases, it'll be the empty string.
   346  func Assignop(src, dst *types.Type) (ir.Op, string) {
   347  	if src == dst {
   348  		return ir.OCONVNOP, ""
   349  	}
   350  	if src == nil || dst == nil || src.Kind() == types.TFORW || dst.Kind() == types.TFORW || src.Underlying() == nil || dst.Underlying() == nil {
   351  		return ir.OXXX, ""
   352  	}
   353  
   354  	// 1. src type is identical to dst.
   355  	if types.Identical(src, dst) {
   356  		return ir.OCONVNOP, ""
   357  	}
   358  	return Assignop1(src, dst)
   359  }
   360  
   361  func Assignop1(src, dst *types.Type) (ir.Op, string) {
   362  	// 2. src and dst have identical underlying types and
   363  	//   a. either src or dst is not a named type, or
   364  	//   b. both are empty interface types, or
   365  	//   c. at least one is a gcshape type.
   366  	// For assignable but different non-empty interface types,
   367  	// we want to recompute the itab. Recomputing the itab ensures
   368  	// that itabs are unique (thus an interface with a compile-time
   369  	// type I has an itab with interface type I).
   370  	if types.Identical(src.Underlying(), dst.Underlying()) {
   371  		if src.IsEmptyInterface() {
   372  			// Conversion between two empty interfaces
   373  			// requires no code.
   374  			return ir.OCONVNOP, ""
   375  		}
   376  		if (src.Sym() == nil || dst.Sym() == nil) && !src.IsInterface() {
   377  			// Conversion between two types, at least one unnamed,
   378  			// needs no conversion. The exception is nonempty interfaces
   379  			// which need to have their itab updated.
   380  			return ir.OCONVNOP, ""
   381  		}
   382  		if src.IsShape() || dst.IsShape() {
   383  			// Conversion between a shape type and one of the types
   384  			// it represents also needs no conversion.
   385  			return ir.OCONVNOP, ""
   386  		}
   387  	}
   388  
   389  	// 3. dst is an interface type and src implements dst.
   390  	if dst.IsInterface() && src.Kind() != types.TNIL {
   391  		var missing, have *types.Field
   392  		var ptr int
   393  		if src.IsShape() {
   394  			// Shape types implement things they have already
   395  			// been typechecked to implement, even if they
   396  			// don't have the methods for them.
   397  			return ir.OCONVIFACE, ""
   398  		}
   399  		if implements(src, dst, &missing, &have, &ptr) {
   400  			return ir.OCONVIFACE, ""
   401  		}
   402  
   403  		// we'll have complained about this method anyway, suppress spurious messages.
   404  		if have != nil && have.Sym == missing.Sym && (have.Type.Broke() || missing.Type.Broke()) {
   405  			return ir.OCONVIFACE, ""
   406  		}
   407  
   408  		var why string
   409  		if isptrto(src, types.TINTER) {
   410  			why = fmt.Sprintf(":\n\t%v is pointer to interface, not interface", src)
   411  		} else if have != nil && have.Sym == missing.Sym && have.Nointerface() {
   412  			why = fmt.Sprintf(":\n\t%v does not implement %v (%v method is marked 'nointerface')", src, dst, missing.Sym)
   413  		} else if have != nil && have.Sym == missing.Sym {
   414  			why = fmt.Sprintf(":\n\t%v does not implement %v (wrong type for %v method)\n"+
   415  				"\t\thave %v%S\n\t\twant %v%S", src, dst, missing.Sym, have.Sym, have.Type, missing.Sym, missing.Type)
   416  		} else if ptr != 0 {
   417  			why = fmt.Sprintf(":\n\t%v does not implement %v (%v method has pointer receiver)", src, dst, missing.Sym)
   418  		} else if have != nil {
   419  			why = fmt.Sprintf(":\n\t%v does not implement %v (missing %v method)\n"+
   420  				"\t\thave %v%S\n\t\twant %v%S", src, dst, missing.Sym, have.Sym, have.Type, missing.Sym, missing.Type)
   421  		} else {
   422  			why = fmt.Sprintf(":\n\t%v does not implement %v (missing %v method)", src, dst, missing.Sym)
   423  		}
   424  
   425  		return ir.OXXX, why
   426  	}
   427  
   428  	if isptrto(dst, types.TINTER) {
   429  		why := fmt.Sprintf(":\n\t%v is pointer to interface, not interface", dst)
   430  		return ir.OXXX, why
   431  	}
   432  
   433  	if src.IsInterface() && dst.Kind() != types.TBLANK {
   434  		var missing, have *types.Field
   435  		var ptr int
   436  		var why string
   437  		if implements(dst, src, &missing, &have, &ptr) {
   438  			why = ": need type assertion"
   439  		}
   440  		return ir.OXXX, why
   441  	}
   442  
   443  	// 4. src is a bidirectional channel value, dst is a channel type,
   444  	// src and dst have identical element types, and
   445  	// either src or dst is not a named type.
   446  	if src.IsChan() && src.ChanDir() == types.Cboth && dst.IsChan() {
   447  		if types.Identical(src.Elem(), dst.Elem()) && (src.Sym() == nil || dst.Sym() == nil) {
   448  			return ir.OCONVNOP, ""
   449  		}
   450  	}
   451  
   452  	// 5. src is the predeclared identifier nil and dst is a nillable type.
   453  	if src.Kind() == types.TNIL {
   454  		switch dst.Kind() {
   455  		case types.TPTR,
   456  			types.TFUNC,
   457  			types.TMAP,
   458  			types.TCHAN,
   459  			types.TINTER,
   460  			types.TSLICE:
   461  			return ir.OCONVNOP, ""
   462  		}
   463  	}
   464  
   465  	// 6. rule about untyped constants - already converted by DefaultLit.
   466  
   467  	// 7. Any typed value can be assigned to the blank identifier.
   468  	if dst.Kind() == types.TBLANK {
   469  		return ir.OCONVNOP, ""
   470  	}
   471  
   472  	return ir.OXXX, ""
   473  }
   474  
   475  // Can we convert a value of type src to a value of type dst?
   476  // If so, return op code to use in conversion (maybe OCONVNOP).
   477  // If not, return OXXX. In this case, the string return parameter may
   478  // hold a reason why. In all other cases, it'll be the empty string.
   479  // srcConstant indicates whether the value of type src is a constant.
   480  func Convertop(srcConstant bool, src, dst *types.Type) (ir.Op, string) {
   481  	if src == dst {
   482  		return ir.OCONVNOP, ""
   483  	}
   484  	if src == nil || dst == nil {
   485  		return ir.OXXX, ""
   486  	}
   487  
   488  	// Conversions from regular to go:notinheap are not allowed
   489  	// (unless it's unsafe.Pointer). These are runtime-specific
   490  	// rules.
   491  	// (a) Disallow (*T) to (*U) where T is go:notinheap but U isn't.
   492  	if src.IsPtr() && dst.IsPtr() && dst.Elem().NotInHeap() && !src.Elem().NotInHeap() {
   493  		why := fmt.Sprintf(":\n\t%v is incomplete (or unallocatable), but %v is not", dst.Elem(), src.Elem())
   494  		return ir.OXXX, why
   495  	}
   496  	// (b) Disallow string to []T where T is go:notinheap.
   497  	if src.IsString() && dst.IsSlice() && dst.Elem().NotInHeap() && (dst.Elem().Kind() == types.ByteType.Kind() || dst.Elem().Kind() == types.RuneType.Kind()) {
   498  		why := fmt.Sprintf(":\n\t%v is incomplete (or unallocatable)", dst.Elem())
   499  		return ir.OXXX, why
   500  	}
   501  
   502  	// 1. src can be assigned to dst.
   503  	op, why := Assignop(src, dst)
   504  	if op != ir.OXXX {
   505  		return op, why
   506  	}
   507  
   508  	// The rules for interfaces are no different in conversions
   509  	// than assignments. If interfaces are involved, stop now
   510  	// with the good message from assignop.
   511  	// Otherwise clear the error.
   512  	if src.IsInterface() || dst.IsInterface() {
   513  		return ir.OXXX, why
   514  	}
   515  
   516  	// 2. Ignoring struct tags, src and dst have identical underlying types.
   517  	if types.IdenticalIgnoreTags(src.Underlying(), dst.Underlying()) {
   518  		return ir.OCONVNOP, ""
   519  	}
   520  
   521  	// 3. src and dst are unnamed pointer types and, ignoring struct tags,
   522  	// their base types have identical underlying types.
   523  	if src.IsPtr() && dst.IsPtr() && src.Sym() == nil && dst.Sym() == nil {
   524  		if types.IdenticalIgnoreTags(src.Elem().Underlying(), dst.Elem().Underlying()) {
   525  			return ir.OCONVNOP, ""
   526  		}
   527  	}
   528  
   529  	// 4. src and dst are both integer or floating point types.
   530  	if (src.IsInteger() || src.IsFloat()) && (dst.IsInteger() || dst.IsFloat()) {
   531  		if types.SimType[src.Kind()] == types.SimType[dst.Kind()] {
   532  			return ir.OCONVNOP, ""
   533  		}
   534  		return ir.OCONV, ""
   535  	}
   536  
   537  	// 5. src and dst are both complex types.
   538  	if src.IsComplex() && dst.IsComplex() {
   539  		if types.SimType[src.Kind()] == types.SimType[dst.Kind()] {
   540  			return ir.OCONVNOP, ""
   541  		}
   542  		return ir.OCONV, ""
   543  	}
   544  
   545  	// Special case for constant conversions: any numeric
   546  	// conversion is potentially okay. We'll validate further
   547  	// within evconst. See #38117.
   548  	if srcConstant && (src.IsInteger() || src.IsFloat() || src.IsComplex()) && (dst.IsInteger() || dst.IsFloat() || dst.IsComplex()) {
   549  		return ir.OCONV, ""
   550  	}
   551  
   552  	// 6. src is an integer or has type []byte or []rune
   553  	// and dst is a string type.
   554  	if src.IsInteger() && dst.IsString() {
   555  		return ir.ORUNESTR, ""
   556  	}
   557  
   558  	if src.IsSlice() && dst.IsString() {
   559  		if src.Elem().Kind() == types.ByteType.Kind() {
   560  			return ir.OBYTES2STR, ""
   561  		}
   562  		if src.Elem().Kind() == types.RuneType.Kind() {
   563  			return ir.ORUNES2STR, ""
   564  		}
   565  	}
   566  
   567  	// 7. src is a string and dst is []byte or []rune.
   568  	// String to slice.
   569  	if src.IsString() && dst.IsSlice() {
   570  		if dst.Elem().Kind() == types.ByteType.Kind() {
   571  			return ir.OSTR2BYTES, ""
   572  		}
   573  		if dst.Elem().Kind() == types.RuneType.Kind() {
   574  			return ir.OSTR2RUNES, ""
   575  		}
   576  	}
   577  
   578  	// 8. src is a pointer or uintptr and dst is unsafe.Pointer.
   579  	if (src.IsPtr() || src.IsUintptr()) && dst.IsUnsafePtr() {
   580  		return ir.OCONVNOP, ""
   581  	}
   582  
   583  	// 9. src is unsafe.Pointer and dst is a pointer or uintptr.
   584  	if src.IsUnsafePtr() && (dst.IsPtr() || dst.IsUintptr()) {
   585  		return ir.OCONVNOP, ""
   586  	}
   587  
   588  	// 10. src is map and dst is a pointer to corresponding hmap.
   589  	// This rule is needed for the implementation detail that
   590  	// go gc maps are implemented as a pointer to a hmap struct.
   591  	if src.Kind() == types.TMAP && dst.IsPtr() &&
   592  		src.MapType().Hmap == dst.Elem() {
   593  		return ir.OCONVNOP, ""
   594  	}
   595  
   596  	// 11. src is a slice and dst is a pointer-to-array.
   597  	// They must have same element type.
   598  	if src.IsSlice() && dst.IsPtr() && dst.Elem().IsArray() &&
   599  		types.Identical(src.Elem(), dst.Elem().Elem()) {
   600  		if !types.AllowsGoVersion(curpkg(), 1, 17) {
   601  			return ir.OXXX, ":\n\tconversion of slices to array pointers only supported as of -lang=go1.17"
   602  		}
   603  		return ir.OSLICE2ARRPTR, ""
   604  	}
   605  
   606  	return ir.OXXX, ""
   607  }
   608  
   609  // Code to resolve elided DOTs in embedded types.
   610  
   611  // A dlist stores a pointer to a TFIELD Type embedded within
   612  // a TSTRUCT or TINTER Type.
   613  type dlist struct {
   614  	field *types.Field
   615  }
   616  
   617  // dotpath computes the unique shortest explicit selector path to fully qualify
   618  // a selection expression x.f, where x is of type t and f is the symbol s.
   619  // If no such path exists, dotpath returns nil.
   620  // If there are multiple shortest paths to the same depth, ambig is true.
   621  func dotpath(s *types.Sym, t *types.Type, save **types.Field, ignorecase bool) (path []dlist, ambig bool) {
   622  	// The embedding of types within structs imposes a tree structure onto
   623  	// types: structs parent the types they embed, and types parent their
   624  	// fields or methods. Our goal here is to find the shortest path to
   625  	// a field or method named s in the subtree rooted at t. To accomplish
   626  	// that, we iteratively perform depth-first searches of increasing depth
   627  	// until we either find the named field/method or exhaust the tree.
   628  	for d := 0; ; d++ {
   629  		if d > len(dotlist) {
   630  			dotlist = append(dotlist, dlist{})
   631  		}
   632  		if c, more := adddot1(s, t, d, save, ignorecase); c == 1 {
   633  			return dotlist[:d], false
   634  		} else if c > 1 {
   635  			return nil, true
   636  		} else if !more {
   637  			return nil, false
   638  		}
   639  	}
   640  }
   641  
   642  func expand0(t *types.Type) {
   643  	u := t
   644  	if u.IsPtr() {
   645  		u = u.Elem()
   646  	}
   647  
   648  	if u.IsInterface() {
   649  		for _, f := range u.AllMethods().Slice() {
   650  			if f.Sym.Uniq() {
   651  				continue
   652  			}
   653  			f.Sym.SetUniq(true)
   654  			slist = append(slist, symlink{field: f})
   655  		}
   656  
   657  		return
   658  	}
   659  
   660  	u = types.ReceiverBaseType(t)
   661  	if u != nil {
   662  		for _, f := range u.Methods().Slice() {
   663  			if f.Sym.Uniq() {
   664  				continue
   665  			}
   666  			f.Sym.SetUniq(true)
   667  			slist = append(slist, symlink{field: f})
   668  		}
   669  	}
   670  }
   671  
   672  func expand1(t *types.Type, top bool) {
   673  	if t.Recur() {
   674  		return
   675  	}
   676  	t.SetRecur(true)
   677  
   678  	if !top {
   679  		expand0(t)
   680  	}
   681  
   682  	u := t
   683  	if u.IsPtr() {
   684  		u = u.Elem()
   685  	}
   686  
   687  	if u.IsStruct() || u.IsInterface() {
   688  		var fields *types.Fields
   689  		if u.IsStruct() {
   690  			fields = u.Fields()
   691  		} else {
   692  			fields = u.AllMethods()
   693  		}
   694  		for _, f := range fields.Slice() {
   695  			if f.Embedded == 0 {
   696  				continue
   697  			}
   698  			if f.Sym == nil {
   699  				continue
   700  			}
   701  			expand1(f.Type, false)
   702  		}
   703  	}
   704  
   705  	t.SetRecur(false)
   706  }
   707  
   708  func ifacelookdot(s *types.Sym, t *types.Type, ignorecase bool) (m *types.Field, followptr bool) {
   709  	if t == nil {
   710  		return nil, false
   711  	}
   712  
   713  	path, ambig := dotpath(s, t, &m, ignorecase)
   714  	if path == nil {
   715  		if ambig {
   716  			base.Errorf("%v.%v is ambiguous", t, s)
   717  		}
   718  		return nil, false
   719  	}
   720  
   721  	for _, d := range path {
   722  		if d.field.Type.IsPtr() {
   723  			followptr = true
   724  			break
   725  		}
   726  	}
   727  
   728  	if !m.IsMethod() {
   729  		base.Errorf("%v.%v is a field, not a method", t, s)
   730  		return nil, followptr
   731  	}
   732  
   733  	return m, followptr
   734  }
   735  
   736  // implements reports whether t implements the interface iface. t can be
   737  // an interface, a type parameter, or a concrete type. If implements returns
   738  // false, it stores a method of iface that is not implemented in *m. If the
   739  // method name matches but the type is wrong, it additionally stores the type
   740  // of the method (on t) in *samename.
   741  func implements(t, iface *types.Type, m, samename **types.Field, ptr *int) bool {
   742  	t0 := t
   743  	if t == nil {
   744  		return false
   745  	}
   746  
   747  	if t.IsInterface() || t.IsTypeParam() {
   748  		if t.IsTypeParam() {
   749  			// If t is a simple type parameter T, its type and underlying is the same.
   750  			// If t is a type definition:'type P[T any] T', its type is P[T] and its
   751  			// underlying is T. Therefore we use 't.Underlying() != t' to distinguish them.
   752  			if t.Underlying() != t {
   753  				CalcMethods(t)
   754  			} else {
   755  				// A typeparam satisfies an interface if its type bound
   756  				// has all the methods of that interface.
   757  				t = t.Bound()
   758  			}
   759  		}
   760  		i := 0
   761  		tms := t.AllMethods().Slice()
   762  		for _, im := range iface.AllMethods().Slice() {
   763  			for i < len(tms) && tms[i].Sym != im.Sym {
   764  				i++
   765  			}
   766  			if i == len(tms) {
   767  				*m = im
   768  				*samename = nil
   769  				*ptr = 0
   770  				return false
   771  			}
   772  			tm := tms[i]
   773  			if !types.Identical(tm.Type, im.Type) {
   774  				*m = im
   775  				*samename = tm
   776  				*ptr = 0
   777  				return false
   778  			}
   779  		}
   780  
   781  		return true
   782  	}
   783  
   784  	t = types.ReceiverBaseType(t)
   785  	var tms []*types.Field
   786  	if t != nil {
   787  		CalcMethods(t)
   788  		tms = t.AllMethods().Slice()
   789  	}
   790  	i := 0
   791  	for _, im := range iface.AllMethods().Slice() {
   792  		if im.Broke() {
   793  			continue
   794  		}
   795  		for i < len(tms) && tms[i].Sym != im.Sym {
   796  			i++
   797  		}
   798  		if i == len(tms) {
   799  			*m = im
   800  			*samename, _ = ifacelookdot(im.Sym, t, true)
   801  			*ptr = 0
   802  			return false
   803  		}
   804  		tm := tms[i]
   805  		if tm.Nointerface() || !types.Identical(tm.Type, im.Type) {
   806  			*m = im
   807  			*samename = tm
   808  			*ptr = 0
   809  			return false
   810  		}
   811  		followptr := tm.Embedded == 2
   812  
   813  		// if pointer receiver in method,
   814  		// the method does not exist for value types.
   815  		rcvr := tm.Type.Recv().Type
   816  		if rcvr.IsPtr() && !t0.IsPtr() && !followptr && !types.IsInterfaceMethod(tm.Type) {
   817  			if false && base.Flag.LowerR != 0 {
   818  				base.Errorf("interface pointer mismatch")
   819  			}
   820  
   821  			*m = im
   822  			*samename = nil
   823  			*ptr = 1
   824  			return false
   825  		}
   826  	}
   827  
   828  	return true
   829  }
   830  
   831  func isptrto(t *types.Type, et types.Kind) bool {
   832  	if t == nil {
   833  		return false
   834  	}
   835  	if !t.IsPtr() {
   836  		return false
   837  	}
   838  	t = t.Elem()
   839  	if t == nil {
   840  		return false
   841  	}
   842  	if t.Kind() != et {
   843  		return false
   844  	}
   845  	return true
   846  }
   847  
   848  // lookdot0 returns the number of fields or methods named s associated
   849  // with Type t. If exactly one exists, it will be returned in *save
   850  // (if save is not nil).
   851  func lookdot0(s *types.Sym, t *types.Type, save **types.Field, ignorecase bool) int {
   852  	u := t
   853  	if u.IsPtr() {
   854  		u = u.Elem()
   855  	}
   856  
   857  	c := 0
   858  	if u.IsStruct() || u.IsInterface() {
   859  		var fields *types.Fields
   860  		if u.IsStruct() {
   861  			fields = u.Fields()
   862  		} else {
   863  			fields = u.AllMethods()
   864  		}
   865  		for _, f := range fields.Slice() {
   866  			if f.Sym == s || (ignorecase && f.IsMethod() && strings.EqualFold(f.Sym.Name, s.Name)) {
   867  				if save != nil {
   868  					*save = f
   869  				}
   870  				c++
   871  			}
   872  		}
   873  	}
   874  
   875  	u = t
   876  	if t.Sym() != nil && t.IsPtr() && !t.Elem().IsPtr() {
   877  		// If t is a defined pointer type, then x.m is shorthand for (*x).m.
   878  		u = t.Elem()
   879  	}
   880  	u = types.ReceiverBaseType(u)
   881  	if u != nil {
   882  		for _, f := range u.Methods().Slice() {
   883  			if f.Embedded == 0 && (f.Sym == s || (ignorecase && strings.EqualFold(f.Sym.Name, s.Name))) {
   884  				if save != nil {
   885  					*save = f
   886  				}
   887  				c++
   888  			}
   889  		}
   890  	}
   891  
   892  	return c
   893  }
   894  
   895  var slist []symlink
   896  
   897  // Code to help generate trampoline functions for methods on embedded
   898  // types. These are approx the same as the corresponding AddImplicitDots
   899  // routines except that they expect to be called with unique tasks and
   900  // they return the actual methods.
   901  
   902  type symlink struct {
   903  	field *types.Field
   904  }
   905  
   906  // TypesOf converts a list of nodes to a list
   907  // of types of those nodes.
   908  func TypesOf(x []ir.Node) []*types.Type {
   909  	r := make([]*types.Type, len(x))
   910  	for i, n := range x {
   911  		r[i] = n.Type()
   912  	}
   913  	return r
   914  }
   915  
   916  // addTargs writes out the targs to buffer b as a comma-separated list enclosed by
   917  // brackets.
   918  func addTargs(b *bytes.Buffer, targs []*types.Type) {
   919  	b.WriteByte('[')
   920  	for i, targ := range targs {
   921  		if i > 0 {
   922  			b.WriteByte(',')
   923  		}
   924  		// Make sure that type arguments (including type params), are
   925  		// uniquely specified. LinkString() eliminates all spaces
   926  		// and includes the package path (local package path is "" before
   927  		// linker substitution).
   928  		tstring := targ.LinkString()
   929  		b.WriteString(tstring)
   930  	}
   931  	b.WriteString("]")
   932  }
   933  
   934  // InstTypeName creates a name for an instantiated type, based on the name of the
   935  // generic type and the type args.
   936  func InstTypeName(name string, targs []*types.Type) string {
   937  	b := bytes.NewBufferString(name)
   938  	addTargs(b, targs)
   939  	return b.String()
   940  }
   941  
   942  // makeInstName1 returns the name of the generic function instantiated with the
   943  // given types, which can have type params or shapes, or be concrete types. name is
   944  // the name of the generic function or method.
   945  func makeInstName1(name string, targs []*types.Type, hasBrackets bool) string {
   946  	b := bytes.NewBufferString("")
   947  	i := strings.Index(name, "[")
   948  	assert(hasBrackets == (i >= 0))
   949  	if i >= 0 {
   950  		b.WriteString(name[0:i])
   951  	} else {
   952  		b.WriteString(name)
   953  	}
   954  	addTargs(b, targs)
   955  	if i >= 0 {
   956  		i2 := strings.LastIndex(name[i:], "]")
   957  		assert(i2 >= 0)
   958  		b.WriteString(name[i+i2+1:])
   959  	}
   960  	return b.String()
   961  }
   962  
   963  // MakeFuncInstSym makes the unique sym for a stenciled generic function or method,
   964  // based on the name of the function gf and the targs. It replaces any
   965  // existing bracket type list in the name. MakeInstName asserts that gf has
   966  // brackets in its name if and only if hasBrackets is true.
   967  //
   968  // Names of declared generic functions have no brackets originally, so hasBrackets
   969  // should be false. Names of generic methods already have brackets, since the new
   970  // type parameter is specified in the generic type of the receiver (e.g. func
   971  // (func (v *value[T]).set(...) { ... } has the original name (*value[T]).set.
   972  //
   973  // The standard naming is something like: 'genFn[int,bool]' for functions and
   974  // '(*genType[int,bool]).methodName' for methods
   975  //
   976  // isMethodNode specifies if the name of a method node is being generated (as opposed
   977  // to a name of an instantiation of generic function or name of the shape-based
   978  // function that helps implement a method of an instantiated type). For method nodes
   979  // on shape types, we prepend "nofunc.", because method nodes for shape types will
   980  // have no body, and we want to avoid a name conflict with the shape-based function
   981  // that helps implement the same method for fully-instantiated types. Function names
   982  // are also created at the end of (*Tsubster).typ1, so we append "nofunc" there as
   983  // well, as needed.
   984  func MakeFuncInstSym(gf *types.Sym, targs []*types.Type, isMethodNode, hasBrackets bool) *types.Sym {
   985  	nm := makeInstName1(gf.Name, targs, hasBrackets)
   986  	if targs[0].HasShape() && isMethodNode {
   987  		nm = "nofunc." + nm
   988  	}
   989  	return gf.Pkg.Lookup(nm)
   990  }
   991  
   992  func MakeDictSym(gf *types.Sym, targs []*types.Type, hasBrackets bool) *types.Sym {
   993  	for _, targ := range targs {
   994  		if targ.HasTParam() {
   995  			fmt.Printf("FUNCTION %s\n", gf.Name)
   996  			for _, targ := range targs {
   997  				fmt.Printf("  PARAM %+v\n", targ)
   998  			}
   999  			panic("dictionary should always have concrete type args")
  1000  		}
  1001  	}
  1002  	name := makeInstName1(gf.Name, targs, hasBrackets)
  1003  	name = fmt.Sprintf("%s.%s", objabi.GlobalDictPrefix, name)
  1004  	return gf.Pkg.Lookup(name)
  1005  }
  1006  
  1007  func assert(p bool) {
  1008  	base.Assert(p)
  1009  }
  1010  
  1011  // List of newly fully-instantiated types who should have their methods generated.
  1012  var instTypeList []*types.Type
  1013  
  1014  // NeedInstType adds a new fully-instantiated type to instTypeList.
  1015  func NeedInstType(t *types.Type) {
  1016  	instTypeList = append(instTypeList, t)
  1017  }
  1018  
  1019  // GetInstTypeList returns the current contents of instTypeList.
  1020  func GetInstTypeList() []*types.Type {
  1021  	r := instTypeList
  1022  	return r
  1023  }
  1024  
  1025  // ClearInstTypeList clears the contents of instTypeList.
  1026  func ClearInstTypeList() {
  1027  	instTypeList = nil
  1028  }
  1029  
  1030  // General type substituter, for replacing typeparams with type args.
  1031  type Tsubster struct {
  1032  	Tparams []*types.Type
  1033  	Targs   []*types.Type
  1034  	// If non-nil, the substitution map from name nodes in the generic function to the
  1035  	// name nodes in the new stenciled function.
  1036  	Vars map[*ir.Name]*ir.Name
  1037  	// If non-nil, function to substitute an incomplete (TFORW) type.
  1038  	SubstForwFunc func(*types.Type) *types.Type
  1039  }
  1040  
  1041  // Typ computes the type obtained by substituting any type parameter or shape in t
  1042  // that appears in subst.Tparams with the corresponding type argument in subst.Targs.
  1043  // If t contains no type parameters, the result is t; otherwise the result is a new
  1044  // type. It deals with recursive types by using TFORW types and finding partially or
  1045  // fully created types via sym.Def.
  1046  func (ts *Tsubster) Typ(t *types.Type) *types.Type {
  1047  	// Defer the CheckSize calls until we have fully-defined
  1048  	// (possibly-recursive) top-level type.
  1049  	types.DeferCheckSize()
  1050  	r := ts.typ1(t)
  1051  	types.ResumeCheckSize()
  1052  	return r
  1053  }
  1054  
  1055  func (ts *Tsubster) typ1(t *types.Type) *types.Type {
  1056  	if !t.HasTParam() && !t.HasShape() && t.Kind() != types.TFUNC {
  1057  		// Note: function types need to be copied regardless, as the
  1058  		// types of closures may contain declarations that need
  1059  		// to be copied. See #45738.
  1060  		return t
  1061  	}
  1062  
  1063  	if t.IsTypeParam() || t.IsShape() {
  1064  		for i, tp := range ts.Tparams {
  1065  			if tp == t {
  1066  				return ts.Targs[i]
  1067  			}
  1068  		}
  1069  		// If t is a simple typeparam T, then t has the name/symbol 'T'
  1070  		// and t.Underlying() == t.
  1071  		//
  1072  		// However, consider the type definition: 'type P[T any] T'. We
  1073  		// might use this definition so we can have a variant of type T
  1074  		// that we can add new methods to. Suppose t is a reference to
  1075  		// P[T]. t has the name 'P[T]', but its kind is TTYPEPARAM,
  1076  		// because P[T] is defined as T. If we look at t.Underlying(), it
  1077  		// is different, because the name of t.Underlying() is 'T' rather
  1078  		// than 'P[T]'. But the kind of t.Underlying() is also TTYPEPARAM.
  1079  		// In this case, we do the needed recursive substitution in the
  1080  		// case statement below.
  1081  		if t.Underlying() == t {
  1082  			// t is a simple typeparam that didn't match anything in tparam
  1083  			return t
  1084  		}
  1085  		// t is a more complex typeparam (e.g. P[T], as above, whose
  1086  		// definition is just T).
  1087  		assert(t.Sym() != nil)
  1088  	}
  1089  
  1090  	var newsym *types.Sym
  1091  	var neededTargs []*types.Type
  1092  	var targsChanged bool
  1093  	var forw *types.Type
  1094  
  1095  	if t.Sym() != nil && (t.HasTParam() || t.HasShape()) {
  1096  		// Need to test for t.HasTParam() again because of special TFUNC case above.
  1097  		// Translate the type params for this type according to
  1098  		// the tparam/targs mapping from subst.
  1099  		neededTargs = make([]*types.Type, len(t.RParams()))
  1100  		for i, rparam := range t.RParams() {
  1101  			neededTargs[i] = ts.typ1(rparam)
  1102  			if !types.IdenticalStrict(neededTargs[i], rparam) {
  1103  				targsChanged = true
  1104  			}
  1105  		}
  1106  		// For a named (defined) type, we have to change the name of the
  1107  		// type as well. We do this first, so we can look up if we've
  1108  		// already seen this type during this substitution or other
  1109  		// definitions/substitutions.
  1110  		genName := genericTypeName(t.Sym())
  1111  		newsym = t.Sym().Pkg.Lookup(InstTypeName(genName, neededTargs))
  1112  		if newsym.Def != nil {
  1113  			// We've already created this instantiated defined type.
  1114  			return newsym.Def.Type()
  1115  		}
  1116  
  1117  		// In order to deal with recursive generic types, create a TFORW
  1118  		// type initially and set the Def field of its sym, so it can be
  1119  		// found if this type appears recursively within the type.
  1120  		forw = NewIncompleteNamedType(t.Pos(), newsym)
  1121  		//println("Creating new type by sub", newsym.Name, forw.HasTParam())
  1122  		forw.SetRParams(neededTargs)
  1123  		// Copy the OrigType from the re-instantiated type (which is the sym of
  1124  		// the base generic type).
  1125  		assert(t.OrigType() != nil)
  1126  		forw.SetOrigType(t.OrigType())
  1127  	}
  1128  
  1129  	var newt *types.Type
  1130  
  1131  	switch t.Kind() {
  1132  	case types.TTYPEPARAM:
  1133  		if t.Sym() == newsym && !targsChanged {
  1134  			// The substitution did not change the type.
  1135  			return t
  1136  		}
  1137  		// Substitute the underlying typeparam (e.g. T in P[T], see
  1138  		// the example describing type P[T] above).
  1139  		newt = ts.typ1(t.Underlying())
  1140  		assert(newt != t)
  1141  
  1142  	case types.TARRAY:
  1143  		elem := t.Elem()
  1144  		newelem := ts.typ1(elem)
  1145  		if newelem != elem || targsChanged {
  1146  			newt = types.NewArray(newelem, t.NumElem())
  1147  		}
  1148  
  1149  	case types.TPTR:
  1150  		elem := t.Elem()
  1151  		newelem := ts.typ1(elem)
  1152  		if newelem != elem || targsChanged {
  1153  			newt = types.NewPtr(newelem)
  1154  		}
  1155  
  1156  	case types.TSLICE:
  1157  		elem := t.Elem()
  1158  		newelem := ts.typ1(elem)
  1159  		if newelem != elem || targsChanged {
  1160  			newt = types.NewSlice(newelem)
  1161  		}
  1162  
  1163  	case types.TSTRUCT:
  1164  		newt = ts.tstruct(t, targsChanged)
  1165  		if newt == t {
  1166  			newt = nil
  1167  		}
  1168  
  1169  	case types.TFUNC:
  1170  		newrecvs := ts.tstruct(t.Recvs(), false)
  1171  		newparams := ts.tstruct(t.Params(), false)
  1172  		newresults := ts.tstruct(t.Results(), false)
  1173  		// Translate the tparams of a signature.
  1174  		newtparams := ts.tstruct(t.TParams(), false)
  1175  		if newrecvs != t.Recvs() || newparams != t.Params() ||
  1176  			newresults != t.Results() || newtparams != t.TParams() || targsChanged {
  1177  			// If any types have changed, then the all the fields of
  1178  			// of recv, params, and results must be copied, because they have
  1179  			// offset fields that are dependent, and so must have an
  1180  			// independent copy for each new signature.
  1181  			var newrecv *types.Field
  1182  			if newrecvs.NumFields() > 0 {
  1183  				if newrecvs == t.Recvs() {
  1184  					newrecvs = ts.tstruct(t.Recvs(), true)
  1185  				}
  1186  				newrecv = newrecvs.Field(0)
  1187  			}
  1188  			if newparams == t.Params() {
  1189  				newparams = ts.tstruct(t.Params(), true)
  1190  			}
  1191  			if newresults == t.Results() {
  1192  				newresults = ts.tstruct(t.Results(), true)
  1193  			}
  1194  			var tparamfields []*types.Field
  1195  			if newtparams.HasTParam() {
  1196  				tparamfields = newtparams.FieldSlice()
  1197  			} else {
  1198  				// Completely remove the tparams from the resulting
  1199  				// signature, if the tparams are now concrete types.
  1200  				tparamfields = nil
  1201  			}
  1202  			newt = types.NewSignature(t.Pkg(), newrecv, tparamfields,
  1203  				newparams.FieldSlice(), newresults.FieldSlice())
  1204  		}
  1205  
  1206  	case types.TINTER:
  1207  		newt = ts.tinter(t, targsChanged)
  1208  		if newt == t {
  1209  			newt = nil
  1210  		}
  1211  
  1212  	case types.TMAP:
  1213  		newkey := ts.typ1(t.Key())
  1214  		newval := ts.typ1(t.Elem())
  1215  		if newkey != t.Key() || newval != t.Elem() || targsChanged {
  1216  			newt = types.NewMap(newkey, newval)
  1217  		}
  1218  
  1219  	case types.TCHAN:
  1220  		elem := t.Elem()
  1221  		newelem := ts.typ1(elem)
  1222  		if newelem != elem || targsChanged {
  1223  			newt = types.NewChan(newelem, t.ChanDir())
  1224  		}
  1225  	case types.TFORW:
  1226  		if ts.SubstForwFunc != nil {
  1227  			return ts.SubstForwFunc(forw)
  1228  		} else {
  1229  			assert(false)
  1230  		}
  1231  	case types.TINT, types.TINT8, types.TINT16, types.TINT32, types.TINT64,
  1232  		types.TUINT, types.TUINT8, types.TUINT16, types.TUINT32, types.TUINT64,
  1233  		types.TUINTPTR, types.TBOOL, types.TSTRING, types.TFLOAT32, types.TFLOAT64, types.TCOMPLEX64, types.TCOMPLEX128, types.TUNSAFEPTR:
  1234  		newt = t.Underlying()
  1235  	case types.TUNION:
  1236  		nt := t.NumTerms()
  1237  		newterms := make([]*types.Type, nt)
  1238  		tildes := make([]bool, nt)
  1239  		changed := false
  1240  		for i := 0; i < nt; i++ {
  1241  			term, tilde := t.Term(i)
  1242  			tildes[i] = tilde
  1243  			newterms[i] = ts.typ1(term)
  1244  			if newterms[i] != term {
  1245  				changed = true
  1246  			}
  1247  		}
  1248  		if changed {
  1249  			newt = types.NewUnion(newterms, tildes)
  1250  		}
  1251  	default:
  1252  		panic(fmt.Sprintf("Bad type in (*TSubster).Typ: %v", t.Kind()))
  1253  	}
  1254  	if newt == nil {
  1255  		// Even though there were typeparams in the type, there may be no
  1256  		// change if this is a function type for a function call (which will
  1257  		// have its own tparams/targs in the function instantiation).
  1258  		return t
  1259  	}
  1260  
  1261  	if forw != nil {
  1262  		forw.SetUnderlying(newt)
  1263  		newt = forw
  1264  	}
  1265  
  1266  	if !newt.HasTParam() && !newt.IsFuncArgStruct() {
  1267  		// Calculate the size of any new types created. These will be
  1268  		// deferred until the top-level ts.Typ() or g.typ() (if this is
  1269  		// called from g.fillinMethods()).
  1270  		types.CheckSize(newt)
  1271  	}
  1272  
  1273  	if t.Kind() != types.TINTER && t.Methods().Len() > 0 {
  1274  		// Fill in the method info for the new type.
  1275  		var newfields []*types.Field
  1276  		newfields = make([]*types.Field, t.Methods().Len())
  1277  		for i, f := range t.Methods().Slice() {
  1278  			t2 := ts.typ1(f.Type)
  1279  			oldsym := f.Nname.Sym()
  1280  
  1281  			// Use the name of the substituted receiver to create the
  1282  			// method name, since the receiver name may have many levels
  1283  			// of nesting (brackets) with type names to be substituted.
  1284  			recvType := t2.Recv().Type
  1285  			var nm string
  1286  			if recvType.IsPtr() {
  1287  				recvType = recvType.Elem()
  1288  				nm = "(*" + recvType.Sym().Name + ")." + f.Sym.Name
  1289  			} else {
  1290  				nm = recvType.Sym().Name + "." + f.Sym.Name
  1291  			}
  1292  			if recvType.RParams()[0].HasShape() {
  1293  				// We add "nofunc" to methods of shape type to avoid
  1294  				// conflict with the name of the shape-based helper
  1295  				// function. See header comment of MakeFuncInstSym.
  1296  				nm = "nofunc." + nm
  1297  			}
  1298  			newsym := oldsym.Pkg.Lookup(nm)
  1299  			var nname *ir.Name
  1300  			if newsym.Def != nil {
  1301  				nname = newsym.Def.(*ir.Name)
  1302  			} else {
  1303  				nname = ir.NewNameAt(f.Pos, newsym)
  1304  				nname.SetType(t2)
  1305  				ir.MarkFunc(nname)
  1306  				newsym.Def = nname
  1307  			}
  1308  			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
  1309  			newfields[i].Nname = nname
  1310  		}
  1311  		newt.Methods().Set(newfields)
  1312  		if !newt.HasTParam() && !newt.HasShape() {
  1313  			// Generate all the methods for a new fully-instantiated type.
  1314  
  1315  			NeedInstType(newt)
  1316  		}
  1317  	}
  1318  	return newt
  1319  }
  1320  
  1321  // tstruct substitutes type params in types of the fields of a structure type. For
  1322  // each field, tstruct copies the Nname, and translates it if Nname is in
  1323  // ts.vars. To always force the creation of a new (top-level) struct,
  1324  // regardless of whether anything changed with the types or names of the struct's
  1325  // fields, set force to true.
  1326  func (ts *Tsubster) tstruct(t *types.Type, force bool) *types.Type {
  1327  	if t.NumFields() == 0 {
  1328  		if t.HasTParam() || t.HasShape() {
  1329  			// For an empty struct, we need to return a new type, if
  1330  			// substituting from a generic type or shape type, since it
  1331  			// will change HasTParam/HasShape flags.
  1332  			return types.NewStruct(t.Pkg(), nil)
  1333  		}
  1334  		return t
  1335  	}
  1336  	var newfields []*types.Field
  1337  	if force {
  1338  		newfields = make([]*types.Field, t.NumFields())
  1339  	}
  1340  	for i, f := range t.Fields().Slice() {
  1341  		t2 := ts.typ1(f.Type)
  1342  		if (t2 != f.Type || f.Nname != nil) && newfields == nil {
  1343  			newfields = make([]*types.Field, t.NumFields())
  1344  			for j := 0; j < i; j++ {
  1345  				newfields[j] = t.Field(j)
  1346  			}
  1347  		}
  1348  		if newfields != nil {
  1349  			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
  1350  			newfields[i].Embedded = f.Embedded
  1351  			newfields[i].Note = f.Note
  1352  			if f.IsDDD() {
  1353  				newfields[i].SetIsDDD(true)
  1354  			}
  1355  			if f.Nointerface() {
  1356  				newfields[i].SetNointerface(true)
  1357  			}
  1358  			if f.Nname != nil && ts.Vars != nil {
  1359  				v := ts.Vars[f.Nname.(*ir.Name)]
  1360  				if v != nil {
  1361  					// This is the case where we are
  1362  					// translating the type of the function we
  1363  					// are substituting, so its dcls are in
  1364  					// the subst.ts.vars table, and we want to
  1365  					// change to reference the new dcl.
  1366  					newfields[i].Nname = v
  1367  				} else {
  1368  					// This is the case where we are
  1369  					// translating the type of a function
  1370  					// reference inside the function we are
  1371  					// substituting, so we leave the Nname
  1372  					// value as is.
  1373  					newfields[i].Nname = f.Nname
  1374  				}
  1375  			}
  1376  		}
  1377  	}
  1378  	if newfields != nil {
  1379  		news := types.NewStruct(t.Pkg(), newfields)
  1380  		news.StructType().Funarg = t.StructType().Funarg
  1381  		return news
  1382  	}
  1383  	return t
  1384  
  1385  }
  1386  
  1387  // tinter substitutes type params in types of the methods of an interface type.
  1388  func (ts *Tsubster) tinter(t *types.Type, force bool) *types.Type {
  1389  	if t.Methods().Len() == 0 {
  1390  		if t.HasTParam() || t.HasShape() {
  1391  			// For an empty interface, we need to return a new type, if
  1392  			// substituting from a generic type or shape type, since
  1393  			// since it will change HasTParam/HasShape flags.
  1394  			return types.NewInterface(t.Pkg(), nil, false)
  1395  		}
  1396  		return t
  1397  	}
  1398  	var newfields []*types.Field
  1399  	if force {
  1400  		newfields = make([]*types.Field, t.Methods().Len())
  1401  	}
  1402  	for i, f := range t.Methods().Slice() {
  1403  		t2 := ts.typ1(f.Type)
  1404  		if (t2 != f.Type || f.Nname != nil) && newfields == nil {
  1405  			newfields = make([]*types.Field, t.Methods().Len())
  1406  			for j := 0; j < i; j++ {
  1407  				newfields[j] = t.Methods().Index(j)
  1408  			}
  1409  		}
  1410  		if newfields != nil {
  1411  			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
  1412  		}
  1413  	}
  1414  	if newfields != nil {
  1415  		return types.NewInterface(t.Pkg(), newfields, t.IsImplicit())
  1416  	}
  1417  	return t
  1418  }
  1419  
  1420  // genericSym returns the name of the base generic type for the type named by
  1421  // sym. It simply returns the name obtained by removing everything after the
  1422  // first bracket ("[").
  1423  func genericTypeName(sym *types.Sym) string {
  1424  	return sym.Name[0:strings.Index(sym.Name, "[")]
  1425  }
  1426  
  1427  // getShapes appends the list of the shape types that are used within type t to
  1428  // listp. The type traversal is simplified for two reasons: (1) we can always stop a
  1429  // type traversal when t.HasShape() is false; and (2) shape types can't appear inside
  1430  // a named type, except for the type args of a generic type. So, the traversal will
  1431  // always stop before we have to deal with recursive types.
  1432  func getShapes(t *types.Type, listp *[]*types.Type) {
  1433  	if !t.HasShape() {
  1434  		return
  1435  	}
  1436  	if t.IsShape() {
  1437  		*listp = append(*listp, t)
  1438  		return
  1439  	}
  1440  
  1441  	if t.Sym() != nil {
  1442  		// A named type can't have shapes in it, except for type args of a
  1443  		// generic type. We will have to deal with this differently once we
  1444  		// alloc local types in generic functions (#47631).
  1445  		for _, rparam := range t.RParams() {
  1446  			getShapes(rparam, listp)
  1447  		}
  1448  		return
  1449  	}
  1450  
  1451  	switch t.Kind() {
  1452  	case types.TARRAY, types.TPTR, types.TSLICE, types.TCHAN:
  1453  		getShapes(t.Elem(), listp)
  1454  
  1455  	case types.TSTRUCT:
  1456  		for _, f := range t.FieldSlice() {
  1457  			getShapes(f.Type, listp)
  1458  		}
  1459  
  1460  	case types.TFUNC:
  1461  		for _, f := range t.Recvs().FieldSlice() {
  1462  			getShapes(f.Type, listp)
  1463  		}
  1464  		for _, f := range t.Params().FieldSlice() {
  1465  			getShapes(f.Type, listp)
  1466  		}
  1467  		for _, f := range t.Results().FieldSlice() {
  1468  			getShapes(f.Type, listp)
  1469  		}
  1470  		for _, f := range t.TParams().FieldSlice() {
  1471  			getShapes(f.Type, listp)
  1472  		}
  1473  
  1474  	case types.TINTER:
  1475  		for _, f := range t.Methods().Slice() {
  1476  			getShapes(f.Type, listp)
  1477  		}
  1478  
  1479  	case types.TMAP:
  1480  		getShapes(t.Key(), listp)
  1481  		getShapes(t.Elem(), listp)
  1482  
  1483  	default:
  1484  		panic(fmt.Sprintf("Bad type in getShapes: %v", t.Kind()))
  1485  	}
  1486  
  1487  }
  1488  
  1489  // Shapify takes a concrete type and a type param index, and returns a GCshape type that can
  1490  // be used in place of the input type and still generate identical code.
  1491  // No methods are added - all methods calls directly on a shape should
  1492  // be done by converting to an interface using the dictionary.
  1493  //
  1494  // For now, we only consider two types to have the same shape, if they have exactly
  1495  // the same underlying type or they are both pointer types.
  1496  //
  1497  //  tparam is the associated typeparam - it must be TTYPEPARAM type. If there is a
  1498  //  structural type for the associated type param (not common), then a pointer type t
  1499  //  is mapped to its underlying type, rather than being merged with other pointers.
  1500  //
  1501  //  Shape types are also distinguished by the index of the type in a type param/arg
  1502  //  list. We need to do this so we can distinguish and substitute properly for two
  1503  //  type params in the same function that have the same shape for a particular
  1504  //  instantiation.
  1505  func Shapify(t *types.Type, index int, tparam *types.Type) *types.Type {
  1506  	assert(!t.IsShape())
  1507  	if t.HasShape() {
  1508  		// We are sometimes dealing with types from a shape instantiation
  1509  		// that were constructed from existing shape types, so t may
  1510  		// sometimes have shape types inside it. In that case, we find all
  1511  		// those shape types with getShapes() and replace them with their
  1512  		// underlying type.
  1513  		//
  1514  		// If we don't do this, we may create extra unneeded shape types that
  1515  		// have these other shape types embedded in them. This may lead to
  1516  		// generating extra shape instantiations, and a mismatch between the
  1517  		// instantiations that we used in generating dictionaries and the
  1518  		// instantations that are actually called. (#51303).
  1519  		list := []*types.Type{}
  1520  		getShapes(t, &list)
  1521  		list2 := make([]*types.Type, len(list))
  1522  		for i, shape := range list {
  1523  			list2[i] = shape.Underlying()
  1524  		}
  1525  		ts := Tsubster{
  1526  			Tparams: list,
  1527  			Targs:   list2,
  1528  		}
  1529  		t = ts.Typ(t)
  1530  	}
  1531  	// Map all types with the same underlying type to the same shape.
  1532  	u := t.Underlying()
  1533  
  1534  	// All pointers have the same shape.
  1535  	// TODO: Make unsafe.Pointer the same shape as normal pointers.
  1536  	// Note: pointers to arrays are special because of slice-to-array-pointer
  1537  	// conversions. See issue 49295.
  1538  	if u.Kind() == types.TPTR && u.Elem().Kind() != types.TARRAY &&
  1539  		tparam.Bound().StructuralType() == nil && !u.Elem().NotInHeap() {
  1540  		u = types.Types[types.TUINT8].PtrTo()
  1541  	}
  1542  
  1543  	if shapeMap == nil {
  1544  		shapeMap = map[int]map[*types.Type]*types.Type{}
  1545  	}
  1546  	submap := shapeMap[index]
  1547  	if submap == nil {
  1548  		submap = map[*types.Type]*types.Type{}
  1549  		shapeMap[index] = submap
  1550  	}
  1551  	if s := submap[u]; s != nil {
  1552  		return s
  1553  	}
  1554  
  1555  	// LinkString specifies the type uniquely, but has no spaces.
  1556  	nm := fmt.Sprintf("%s_%d", u.LinkString(), index)
  1557  	sym := types.ShapePkg.Lookup(nm)
  1558  	if sym.Def != nil {
  1559  		// Use any existing type with the same name
  1560  		submap[u] = sym.Def.Type()
  1561  		return submap[u]
  1562  	}
  1563  	name := ir.NewDeclNameAt(u.Pos(), ir.OTYPE, sym)
  1564  	s := types.NewNamed(name)
  1565  	sym.Def = name
  1566  	s.SetUnderlying(u)
  1567  	s.SetIsShape(true)
  1568  	s.SetHasShape(true)
  1569  	types.CalcSize(s)
  1570  	name.SetType(s)
  1571  	name.SetTypecheck(1)
  1572  	submap[u] = s
  1573  	return s
  1574  }
  1575  
  1576  var shapeMap map[int]map[*types.Type]*types.Type
  1577  

View as plain text