[gostls13.git] / src / cmd / compile / internal / typecheck / subr.go

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package typecheck

import (
        "bytes"
        "fmt"
        "sort"
        "strings"

        "cmd/compile/internal/base"
        "cmd/compile/internal/ir"
        "cmd/compile/internal/types"
        "cmd/internal/obj"
        "cmd/internal/objabi"
        "cmd/internal/src"
)

func AssignConv(n ir.Node, t *types.Type, context string) ir.Node {
        return assignconvfn(n, t, func() string { return context })
}

// LookupNum returns types.LocalPkg.LookupNum(prefix, n).
func LookupNum(prefix string, n int) *types.Sym {
        return types.LocalPkg.LookupNum(prefix, n)
}

// Given funarg struct list, return list of fn args.
func NewFuncParams(tl *types.Type, mustname bool) []*ir.Field {
        var args []*ir.Field
        gen := 0
        for _, t := range tl.Fields().Slice() {
                s := t.Sym
                if mustname && (s == nil || s.Name == "_") {
                        // invent a name so that we can refer to it in the trampoline
                        s = LookupNum(".anon", gen)
                        gen++
                } else if s != nil && s.Pkg != types.LocalPkg {
                        // TODO(mdempsky): Preserve original position, name, and package.
                        s = Lookup(s.Name)
                }
                a := ir.NewField(base.Pos, s, t.Type)
                a.Pos = t.Pos
                a.IsDDD = t.IsDDD()
                args = append(args, a)
        }

        return args
}

// NewName returns a new ONAME Node associated with symbol s.
func NewName(s *types.Sym) *ir.Name {
        n := ir.NewNameAt(base.Pos, s)
        n.Curfn = ir.CurFunc
        return n
}

// NodAddr returns a node representing &n at base.Pos.
func NodAddr(n ir.Node) *ir.AddrExpr {
        return NodAddrAt(base.Pos, n)
}

// NodAddrAt returns a node representing &n at position pos.
func NodAddrAt(pos src.XPos, n ir.Node) *ir.AddrExpr {
        n = markAddrOf(n)
        return ir.NewAddrExpr(pos, n)
}

func markAddrOf(n ir.Node) ir.Node {
        if IncrementalAddrtaken {
                // We can only do incremental addrtaken computation when it is ok
                // to typecheck the argument of the OADDR. That's only safe after the
                // main typecheck has completed, and not loading the inlined body.
                // The argument to OADDR needs to be typechecked because &x[i] takes
                // the address of x if x is an array, but not if x is a slice.
                // Note: OuterValue doesn't work correctly until n is typechecked.
                n = typecheck(n, ctxExpr)
                if x := ir.OuterValue(n); x.Op() == ir.ONAME {
                        x.Name().SetAddrtaken(true)
                }
        } else {
                // Remember that we built an OADDR without computing the Addrtaken bit for
                // its argument. We'll do that later in bulk using computeAddrtaken.
                DirtyAddrtaken = true
        }
        return n
}

// If IncrementalAddrtaken is false, we do not compute Addrtaken for an OADDR Node
// when it is built. The Addrtaken bits are set in bulk by computeAddrtaken.
// If IncrementalAddrtaken is true, then when an OADDR Node is built the Addrtaken
// field of its argument is updated immediately.
var IncrementalAddrtaken = false

// If DirtyAddrtaken is true, then there are OADDR whose corresponding arguments
// have not yet been marked as Addrtaken.
var DirtyAddrtaken = false

func ComputeAddrtaken(top []ir.Node) {
        for _, n := range top {
                var doVisit func(n ir.Node)
                doVisit = func(n ir.Node) {
                        if n.Op() == ir.OADDR {
                                if x := ir.OuterValue(n.(*ir.AddrExpr).X); x.Op() == ir.ONAME {
                                        x.Name().SetAddrtaken(true)
                                        if x.Name().IsClosureVar() {
                                                // Mark the original variable as Addrtaken so that capturevars
                                                // knows not to pass it by value.
                                                x.Name().Defn.Name().SetAddrtaken(true)
                                        }
                                }
                        }
                        if n.Op() == ir.OCLOSURE {
                                ir.VisitList(n.(*ir.ClosureExpr).Func.Body, doVisit)
                        }
                }
                ir.Visit(n, doVisit)
        }
}

// LinksymAddr returns a new expression that evaluates to the address
// of lsym. typ specifies the type of the addressed memory.
func LinksymAddr(pos src.XPos, lsym *obj.LSym, typ *types.Type) *ir.AddrExpr {
        n := ir.NewLinksymExpr(pos, lsym, typ)
        return Expr(NodAddrAt(pos, n)).(*ir.AddrExpr)
}

func NodNil() ir.Node {
        n := ir.NewNilExpr(base.Pos)
        n.SetType(types.Types[types.TNIL])
        return n
}

// AddImplicitDots finds missing fields in obj.field that
// will give the shortest unique addressing and
// modifies the tree with missing field names.
func AddImplicitDots(n *ir.SelectorExpr) *ir.SelectorExpr {
        n.X = typecheck(n.X, ctxType|ctxExpr)
        t := n.X.Type()
        if t == nil {
                return n
        }

        if n.X.Op() == ir.OTYPE {
                return n
        }

        s := n.Sel
        if s == nil {
                return n
        }

        switch path, ambig := dotpath(s, t, nil, false); {
        case path != nil:
                // rebuild elided dots
                for c := len(path) - 1; c >= 0; c-- {
                        dot := ir.NewSelectorExpr(n.Pos(), ir.ODOT, n.X, path[c].field.Sym)
                        dot.SetImplicit(true)
                        dot.SetType(path[c].field.Type)
                        n.X = dot
                }
        case ambig:
                base.Errorf("ambiguous selector %v", n)
                n.X = nil
        }

        return n
}

// CalcMethods calculates all the methods (including embedding) of a non-interface
// type t.
func CalcMethods(t *types.Type) {
        if t == nil || t.AllMethods().Len() != 0 {
                return
        }

        // mark top-level method symbols
        // so that expand1 doesn't consider them.
        for _, f := range t.Methods().Slice() {
                f.Sym.SetUniq(true)
        }

        // generate all reachable methods
        slist = slist[:0]
        expand1(t, true)

        // check each method to be uniquely reachable
        var ms []*types.Field
        for i, sl := range slist {
                slist[i].field = nil
                sl.field.Sym.SetUniq(false)

                var f *types.Field
                path, _ := dotpath(sl.field.Sym, t, &f, false)
                if path == nil {
                        continue
                }

                // dotpath may have dug out arbitrary fields, we only want methods.
                if !f.IsMethod() {
                        continue
                }

                // add it to the base type method list
                f = f.Copy()
                f.Embedded = 1 // needs a trampoline
                for _, d := range path {
                        if d.field.Type.IsPtr() {
                                f.Embedded = 2
                                break
                        }
                }
                ms = append(ms, f)
        }

        for _, f := range t.Methods().Slice() {
                f.Sym.SetUniq(false)
        }

        ms = append(ms, t.Methods().Slice()...)
        sort.Sort(types.MethodsByName(ms))
        t.SetAllMethods(ms)
}

// adddot1 returns the number of fields or methods named s at depth d in Type t.
// If exactly one exists, it will be returned in *save (if save is not nil),
// and dotlist will contain the path of embedded fields traversed to find it,
// in reverse order. If none exist, more will indicate whether t contains any
// embedded fields at depth d, so callers can decide whether to retry at
// a greater depth.
func adddot1(s *types.Sym, t *types.Type, d int, save **types.Field, ignorecase bool) (c int, more bool) {
        if t.Recur() {
                return
        }
        t.SetRecur(true)
        defer t.SetRecur(false)

        var u *types.Type
        d--
        if d < 0 {
                // We've reached our target depth. If t has any fields/methods
                // named s, then we're done. Otherwise, we still need to check
                // below for embedded fields.
                c = lookdot0(s, t, save, ignorecase)
                if c != 0 {
                        return c, false
                }
        }

        u = t
        if u.IsPtr() {
                u = u.Elem()
        }
        if !u.IsStruct() && !u.IsInterface() {
                return c, false
        }

        var fields *types.Fields
        if u.IsStruct() {
                fields = u.Fields()
        } else {
                fields = u.AllMethods()
        }
        for _, f := range fields.Slice() {
                if f.Embedded == 0 || f.Sym == nil {
                        continue
                }
                if d < 0 {
                        // Found an embedded field at target depth.
                        return c, true
                }
                a, more1 := adddot1(s, f.Type, d, save, ignorecase)
                if a != 0 && c == 0 {
                        dotlist[d].field = f
                }
                c += a
                if more1 {
                        more = true
                }
        }

        return c, more
}

// dotlist is used by adddot1 to record the path of embedded fields
// used to access a target field or method.
// Must be non-nil so that dotpath returns a non-nil slice even if d is zero.
var dotlist = make([]dlist, 10)

// Convert node n for assignment to type t.
func assignconvfn(n ir.Node, t *types.Type, context func() string) ir.Node {
        if n == nil || n.Type() == nil {
                return n
        }

        if t.Kind() == types.TBLANK && n.Type().Kind() == types.TNIL {
                base.Errorf("use of untyped nil")
        }

        n = convlit1(n, t, false, context)
        if n.Type() == nil {
                base.Fatalf("cannot assign %v to %v", n, t)
        }
        if n.Type().IsUntyped() {
                base.Fatalf("%L has untyped type", n)
        }
        if t.Kind() == types.TBLANK {
                return n
        }
        if types.Identical(n.Type(), t) {
                return n
        }

        op, why := Assignop(n.Type(), t)
        if op == ir.OXXX {
                base.Errorf("cannot use %L as type %v in %s%s", n, t, context(), why)
                op = ir.OCONV
        }

        r := ir.NewConvExpr(base.Pos, op, t, n)
        r.SetTypecheck(1)
        r.SetImplicit(true)
        return r
}

// Is type src assignment compatible to type dst?
// If so, return op code to use in conversion.
// If not, return OXXX. In this case, the string return parameter may
// hold a reason why. In all other cases, it'll be the empty string.
func Assignop(src, dst *types.Type) (ir.Op, string) {
        if src == dst {
                return ir.OCONVNOP, ""
        }
        if src == nil || dst == nil || src.Kind() == types.TFORW || dst.Kind() == types.TFORW || src.Underlying() == nil || dst.Underlying() == nil {
                return ir.OXXX, ""
        }

        // 1. src type is identical to dst.
        if types.Identical(src, dst) {
                return ir.OCONVNOP, ""
        }
        return Assignop1(src, dst)
}

func Assignop1(src, dst *types.Type) (ir.Op, string) {
        // 2. src and dst have identical underlying types and
        //   a. either src or dst is not a named type, or
        //   b. both are empty interface types, or
        //   c. at least one is a gcshape type.
        // For assignable but different non-empty interface types,
        // we want to recompute the itab. Recomputing the itab ensures
        // that itabs are unique (thus an interface with a compile-time
        // type I has an itab with interface type I).
        if types.Identical(src.Underlying(), dst.Underlying()) {
                if src.IsEmptyInterface() {
                        // Conversion between two empty interfaces
                        // requires no code.
                        return ir.OCONVNOP, ""
                }
                if (src.Sym() == nil || dst.Sym() == nil) && !src.IsInterface() {
                        // Conversion between two types, at least one unnamed,
                        // needs no conversion. The exception is nonempty interfaces
                        // which need to have their itab updated.
                        return ir.OCONVNOP, ""
                }
                if src.IsShape() || dst.IsShape() {
                        // Conversion between a shape type and one of the types
                        // it represents also needs no conversion.
                        return ir.OCONVNOP, ""
                }
        }

        // 3. dst is an interface type and src implements dst.
        if dst.IsInterface() && src.Kind() != types.TNIL {
                var missing, have *types.Field
                var ptr int
                if src.IsShape() {
                        // Shape types implement things they have already
                        // been typechecked to implement, even if they
                        // don't have the methods for them.
                        return ir.OCONVIFACE, ""
                }
                if base.Debug.Unified != 0 && src.HasShape() {
                        // Unified IR uses OCONVIFACE for converting all derived types
                        // to interface type, not just type arguments themselves.
                        return ir.OCONVIFACE, ""
                }
                if implements(src, dst, &missing, &have, &ptr) {
                        return ir.OCONVIFACE, ""
                }

                var why string
                if isptrto(src, types.TINTER) {
                        why = fmt.Sprintf(":\n\t%v is pointer to interface, not interface", src)
                } else if have != nil && have.Sym == missing.Sym && have.Nointerface() {
                        why = fmt.Sprintf(":\n\t%v does not implement %v (%v method is marked 'nointerface')", src, dst, missing.Sym)
                } else if have != nil && have.Sym == missing.Sym {
                        why = fmt.Sprintf(":\n\t%v does not implement %v %s", src, dst, wrongTypeFor(have.Sym, have.Type, missing.Sym, missing.Type))
                } else if ptr != 0 {
                        why = fmt.Sprintf(":\n\t%v does not implement %v (%v method has pointer receiver)", src, dst, missing.Sym)
                } else if have != nil {
                        why = fmt.Sprintf(":\n\t%v does not implement %v (missing %v method)\n"+
                                "\t\thave %v%S\n\t\twant %v%S", src, dst, missing.Sym, have.Sym, have.Type, missing.Sym, missing.Type)
                } else {
                        why = fmt.Sprintf(":\n\t%v does not implement %v (missing %v method)", src, dst, missing.Sym)
                }

                return ir.OXXX, why
        }

        if isptrto(dst, types.TINTER) {
                why := fmt.Sprintf(":\n\t%v is pointer to interface, not interface", dst)
                return ir.OXXX, why
        }

        if src.IsInterface() && dst.Kind() != types.TBLANK {
                var missing, have *types.Field
                var ptr int
                var why string
                if implements(dst, src, &missing, &have, &ptr) {
                        why = ": need type assertion"
                }
                return ir.OXXX, why
        }

        // 4. src is a bidirectional channel value, dst is a channel type,
        // src and dst have identical element types, and
        // either src or dst is not a named type.
        if src.IsChan() && src.ChanDir() == types.Cboth && dst.IsChan() {
                if types.Identical(src.Elem(), dst.Elem()) && (src.Sym() == nil || dst.Sym() == nil) {
                        return ir.OCONVNOP, ""
                }
        }

        // 5. src is the predeclared identifier nil and dst is a nillable type.
        if src.Kind() == types.TNIL {
                switch dst.Kind() {
                case types.TPTR,
                        types.TFUNC,
                        types.TMAP,
                        types.TCHAN,
                        types.TINTER,
                        types.TSLICE:
                        return ir.OCONVNOP, ""
                }
        }

        // 6. rule about untyped constants - already converted by DefaultLit.

        // 7. Any typed value can be assigned to the blank identifier.
        if dst.Kind() == types.TBLANK {
                return ir.OCONVNOP, ""
        }

        return ir.OXXX, ""
}

// Can we convert a value of type src to a value of type dst?
// If so, return op code to use in conversion (maybe OCONVNOP).
// If not, return OXXX. In this case, the string return parameter may
// hold a reason why. In all other cases, it'll be the empty string.
// srcConstant indicates whether the value of type src is a constant.
func Convertop(srcConstant bool, src, dst *types.Type) (ir.Op, string) {
        if src == dst {
                return ir.OCONVNOP, ""
        }
        if src == nil || dst == nil {
                return ir.OXXX, ""
        }

        // Conversions from regular to not-in-heap are not allowed
        // (unless it's unsafe.Pointer). These are runtime-specific
        // rules.
        // (a) Disallow (*T) to (*U) where T is not-in-heap but U isn't.
        if src.IsPtr() && dst.IsPtr() && dst.Elem().NotInHeap() && !src.Elem().NotInHeap() {
                why := fmt.Sprintf(":\n\t%v is incomplete (or unallocatable), but %v is not", dst.Elem(), src.Elem())
                return ir.OXXX, why
        }
        // (b) Disallow string to []T where T is not-in-heap.
        if src.IsString() && dst.IsSlice() && dst.Elem().NotInHeap() && (dst.Elem().Kind() == types.ByteType.Kind() || dst.Elem().Kind() == types.RuneType.Kind()) {
                why := fmt.Sprintf(":\n\t%v is incomplete (or unallocatable)", dst.Elem())
                return ir.OXXX, why
        }

        // 1. src can be assigned to dst.
        op, why := Assignop(src, dst)
        if op != ir.OXXX {
                return op, why
        }

        // The rules for interfaces are no different in conversions
        // than assignments. If interfaces are involved, stop now
        // with the good message from assignop.
        // Otherwise clear the error.
        if src.IsInterface() || dst.IsInterface() {
                return ir.OXXX, why
        }

        // 2. Ignoring struct tags, src and dst have identical underlying types.
        if types.IdenticalIgnoreTags(src.Underlying(), dst.Underlying()) {
                return ir.OCONVNOP, ""
        }

        // 3. src and dst are unnamed pointer types and, ignoring struct tags,
        // their base types have identical underlying types.
        if src.IsPtr() && dst.IsPtr() && src.Sym() == nil && dst.Sym() == nil {
                if types.IdenticalIgnoreTags(src.Elem().Underlying(), dst.Elem().Underlying()) {
                        return ir.OCONVNOP, ""
                }
        }

        // 4. src and dst are both integer or floating point types.
        if (src.IsInteger() || src.IsFloat()) && (dst.IsInteger() || dst.IsFloat()) {
                if types.SimType[src.Kind()] == types.SimType[dst.Kind()] {
                        return ir.OCONVNOP, ""
                }
                return ir.OCONV, ""
        }

        // 5. src and dst are both complex types.
        if src.IsComplex() && dst.IsComplex() {
                if types.SimType[src.Kind()] == types.SimType[dst.Kind()] {
                        return ir.OCONVNOP, ""
                }
                return ir.OCONV, ""
        }

        // Special case for constant conversions: any numeric
        // conversion is potentially okay. We'll validate further
        // within evconst. See #38117.
        if srcConstant && (src.IsInteger() || src.IsFloat() || src.IsComplex()) && (dst.IsInteger() || dst.IsFloat() || dst.IsComplex()) {
                return ir.OCONV, ""
        }

        // 6. src is an integer or has type []byte or []rune
        // and dst is a string type.
        if src.IsInteger() && dst.IsString() {
                return ir.ORUNESTR, ""
        }

        if src.IsSlice() && dst.IsString() {
                if src.Elem().Kind() == types.ByteType.Kind() {
                        return ir.OBYTES2STR, ""
                }
                if src.Elem().Kind() == types.RuneType.Kind() {
                        return ir.ORUNES2STR, ""
                }
        }

        // 7. src is a string and dst is []byte or []rune.
        // String to slice.
        if src.IsString() && dst.IsSlice() {
                if dst.Elem().Kind() == types.ByteType.Kind() {
                        return ir.OSTR2BYTES, ""
                }
                if dst.Elem().Kind() == types.RuneType.Kind() {
                        return ir.OSTR2RUNES, ""
                }
        }

        // 8. src is a pointer or uintptr and dst is unsafe.Pointer.
        if (src.IsPtr() || src.IsUintptr()) && dst.IsUnsafePtr() {
                return ir.OCONVNOP, ""
        }

        // 9. src is unsafe.Pointer and dst is a pointer or uintptr.
        if src.IsUnsafePtr() && (dst.IsPtr() || dst.IsUintptr()) {
                return ir.OCONVNOP, ""
        }

        // 10. src is map and dst is a pointer to corresponding hmap.
        // This rule is needed for the implementation detail that
        // go gc maps are implemented as a pointer to a hmap struct.
        if src.Kind() == types.TMAP && dst.IsPtr() &&
                src.MapType().Hmap == dst.Elem() {
                return ir.OCONVNOP, ""
        }

        // 11. src is a slice and dst is an array or pointer-to-array.
        // They must have same element type.
        if src.IsSlice() {
                if dst.IsArray() && types.Identical(src.Elem(), dst.Elem()) {
                        return ir.OSLICE2ARR, ""
                }
                if dst.IsPtr() && dst.Elem().IsArray() &&
                        types.Identical(src.Elem(), dst.Elem().Elem()) {
                        return ir.OSLICE2ARRPTR, ""
                }
        }

        return ir.OXXX, ""
}

// Code to resolve elided DOTs in embedded types.

// A dlist stores a pointer to a TFIELD Type embedded within
// a TSTRUCT or TINTER Type.
type dlist struct {
        field *types.Field
}

// dotpath computes the unique shortest explicit selector path to fully qualify
// a selection expression x.f, where x is of type t and f is the symbol s.
// If no such path exists, dotpath returns nil.
// If there are multiple shortest paths to the same depth, ambig is true.
func dotpath(s *types.Sym, t *types.Type, save **types.Field, ignorecase bool) (path []dlist, ambig bool) {
        // The embedding of types within structs imposes a tree structure onto
        // types: structs parent the types they embed, and types parent their
        // fields or methods. Our goal here is to find the shortest path to
        // a field or method named s in the subtree rooted at t. To accomplish
        // that, we iteratively perform depth-first searches of increasing depth
        // until we either find the named field/method or exhaust the tree.
        for d := 0; ; d++ {
                if d > len(dotlist) {
                        dotlist = append(dotlist, dlist{})
                }
                if c, more := adddot1(s, t, d, save, ignorecase); c == 1 {
                        return dotlist[:d], false
                } else if c > 1 {
                        return nil, true
                } else if !more {
                        return nil, false
                }
        }
}

func expand0(t *types.Type) {
        u := t
        if u.IsPtr() {
                u = u.Elem()
        }

        if u.IsInterface() {
                for _, f := range u.AllMethods().Slice() {
                        if f.Sym.Uniq() {
                                continue
                        }
                        f.Sym.SetUniq(true)
                        slist = append(slist, symlink{field: f})
                }

                return
        }

        u = types.ReceiverBaseType(t)
        if u != nil {
                for _, f := range u.Methods().Slice() {
                        if f.Sym.Uniq() {
                                continue
                        }
                        f.Sym.SetUniq(true)
                        slist = append(slist, symlink{field: f})
                }
        }
}

func expand1(t *types.Type, top bool) {
        if t.Recur() {
                return
        }
        t.SetRecur(true)

        if !top {
                expand0(t)
        }

        u := t
        if u.IsPtr() {
                u = u.Elem()
        }

        if u.IsStruct() || u.IsInterface() {
                var fields *types.Fields
                if u.IsStruct() {
                        fields = u.Fields()
                } else {
                        fields = u.AllMethods()
                }
                for _, f := range fields.Slice() {
                        if f.Embedded == 0 {
                                continue
                        }
                        if f.Sym == nil {
                                continue
                        }
                        expand1(f.Type, false)
                }
        }

        t.SetRecur(false)
}

func ifacelookdot(s *types.Sym, t *types.Type, ignorecase bool) (m *types.Field, followptr bool) {
        if t == nil {
                return nil, false
        }

        path, ambig := dotpath(s, t, &m, ignorecase)
        if path == nil {
                if ambig {
                        base.Errorf("%v.%v is ambiguous", t, s)
                }
                return nil, false
        }

        for _, d := range path {
                if d.field.Type.IsPtr() {
                        followptr = true
                        break
                }
        }

        if !m.IsMethod() {
                base.Errorf("%v.%v is a field, not a method", t, s)
                return nil, followptr
        }

        return m, followptr
}

// implements reports whether t implements the interface iface. t can be
// an interface, a type parameter, or a concrete type. If implements returns
// false, it stores a method of iface that is not implemented in *m. If the
// method name matches but the type is wrong, it additionally stores the type
// of the method (on t) in *samename.
func implements(t, iface *types.Type, m, samename **types.Field, ptr *int) bool {
        t0 := t
        if t == nil {
                return false
        }

        if t.IsInterface() || t.IsTypeParam() {
                if t.IsTypeParam() {
                        // If t is a simple type parameter T, its type and underlying is the same.
                        // If t is a type definition:'type P[T any] T', its type is P[T] and its
                        // underlying is T. Therefore we use 't.Underlying() != t' to distinguish them.
                        if t.Underlying() != t {
                                CalcMethods(t)
                        } else {
                                // A typeparam satisfies an interface if its type bound
                                // has all the methods of that interface.
                                t = t.Bound()
                        }
                }
                i := 0
                tms := t.AllMethods().Slice()
                for _, im := range iface.AllMethods().Slice() {
                        for i < len(tms) && tms[i].Sym != im.Sym {
                                i++
                        }
                        if i == len(tms) {
                                *m = im
                                *samename = nil
                                *ptr = 0
                                return false
                        }
                        tm := tms[i]
                        if !types.Identical(tm.Type, im.Type) {
                                *m = im
                                *samename = tm
                                *ptr = 0
                                return false
                        }
                }

                return true
        }

        t = types.ReceiverBaseType(t)
        var tms []*types.Field
        if t != nil {
                CalcMethods(t)
                tms = t.AllMethods().Slice()
        }
        i := 0
        for _, im := range iface.AllMethods().Slice() {
                for i < len(tms) && tms[i].Sym != im.Sym {
                        i++
                }
                if i == len(tms) {
                        *m = im
                        *samename, _ = ifacelookdot(im.Sym, t, true)
                        *ptr = 0
                        return false
                }
                tm := tms[i]
                if tm.Nointerface() || !types.Identical(tm.Type, im.Type) {
                        *m = im
                        *samename = tm
                        *ptr = 0
                        return false
                }
                followptr := tm.Embedded == 2

                // if pointer receiver in method,
                // the method does not exist for value types.
                rcvr := tm.Type.Recv().Type
                if rcvr.IsPtr() && !t0.IsPtr() && !followptr && !types.IsInterfaceMethod(tm.Type) {
                        if false && base.Flag.LowerR != 0 {
                                base.Errorf("interface pointer mismatch")
                        }

                        *m = im
                        *samename = nil
                        *ptr = 1
                        return false
                }
        }

        return true
}

func isptrto(t *types.Type, et types.Kind) bool {
        if t == nil {
                return false
        }
        if !t.IsPtr() {
                return false
        }
        t = t.Elem()
        if t == nil {
                return false
        }
        if t.Kind() != et {
                return false
        }
        return true
}

// lookdot0 returns the number of fields or methods named s associated
// with Type t. If exactly one exists, it will be returned in *save
// (if save is not nil).
func lookdot0(s *types.Sym, t *types.Type, save **types.Field, ignorecase bool) int {
        u := t
        if u.IsPtr() {
                u = u.Elem()
        }

        c := 0
        if u.IsStruct() || u.IsInterface() {
                var fields *types.Fields
                if u.IsStruct() {
                        fields = u.Fields()
                } else {
                        fields = u.AllMethods()
                }
                for _, f := range fields.Slice() {
                        if f.Sym == s || (ignorecase && f.IsMethod() && strings.EqualFold(f.Sym.Name, s.Name)) {
                                if save != nil {
                                        *save = f
                                }
                                c++
                        }
                }
        }

        u = t
        if t.Sym() != nil && t.IsPtr() && !t.Elem().IsPtr() {
                // If t is a defined pointer type, then x.m is shorthand for (*x).m.
                u = t.Elem()
        }
        u = types.ReceiverBaseType(u)
        if u != nil {
                for _, f := range u.Methods().Slice() {
                        if f.Embedded == 0 && (f.Sym == s || (ignorecase && strings.EqualFold(f.Sym.Name, s.Name))) {
                                if save != nil {
                                        *save = f
                                }
                                c++
                        }
                }
        }

        return c
}

var slist []symlink

// Code to help generate trampoline functions for methods on embedded
// types. These are approx the same as the corresponding AddImplicitDots
// routines except that they expect to be called with unique tasks and
// they return the actual methods.

type symlink struct {
        field *types.Field
}

// TypesOf converts a list of nodes to a list
// of types of those nodes.
func TypesOf(x []ir.Ntype) []*types.Type {
        r := make([]*types.Type, len(x))
        for i, n := range x {
                r[i] = n.Type()
        }
        return r
}

// addTargs writes out the targs to buffer b as a comma-separated list enclosed by
// brackets.
func addTargs(b *bytes.Buffer, targs []*types.Type) {
        b.WriteByte('[')
        for i, targ := range targs {
                if i > 0 {
                        b.WriteByte(',')
                }
                // Make sure that type arguments (including type params), are
                // uniquely specified. LinkString() eliminates all spaces
                // and includes the package path (local package path is "" before
                // linker substitution).
                tstring := targ.LinkString()
                b.WriteString(tstring)
        }
        b.WriteString("]")
}

// InstTypeName creates a name for an instantiated type, based on the name of the
// generic type and the type args.
func InstTypeName(name string, targs []*types.Type) string {
        b := bytes.NewBufferString(name)
        addTargs(b, targs)
        return b.String()
}

// makeInstName1 returns the name of the generic function instantiated with the
// given types, which can have type params or shapes, or be concrete types. name is
// the name of the generic function or method.
func makeInstName1(name string, targs []*types.Type, hasBrackets bool) string {
        b := bytes.NewBufferString("")
        i := strings.Index(name, "[")
        assert(hasBrackets == (i >= 0))
        if i >= 0 {
                b.WriteString(name[0:i])
        } else {
                b.WriteString(name)
        }
        addTargs(b, targs)
        if i >= 0 {
                i2 := strings.LastIndex(name[i:], "]")
                assert(i2 >= 0)
                b.WriteString(name[i+i2+1:])
        }
        return b.String()
}

// MakeFuncInstSym makes the unique sym for a stenciled generic function or method,
// based on the name of the function gf and the targs. It replaces any
// existing bracket type list in the name. MakeInstName asserts that gf has
// brackets in its name if and only if hasBrackets is true.
//
// Names of declared generic functions have no brackets originally, so hasBrackets
// should be false. Names of generic methods already have brackets, since the new
// type parameter is specified in the generic type of the receiver (e.g. func
// (func (v *value[T]).set(...) { ... } has the original name (*value[T]).set.
//
// The standard naming is something like: 'genFn[int,bool]' for functions and
// '(*genType[int,bool]).methodName' for methods
//
// isMethodNode specifies if the name of a method node is being generated (as opposed
// to a name of an instantiation of generic function or name of the shape-based
// function that helps implement a method of an instantiated type). For method nodes
// on shape types, we prepend "nofunc.", because method nodes for shape types will
// have no body, and we want to avoid a name conflict with the shape-based function
// that helps implement the same method for fully-instantiated types. Function names
// are also created at the end of (*Tsubster).typ1, so we append "nofunc" there as
// well, as needed.
func MakeFuncInstSym(gf *types.Sym, targs []*types.Type, isMethodNode, hasBrackets bool) *types.Sym {
        nm := makeInstName1(gf.Name, targs, hasBrackets)
        if targs[0].HasShape() && isMethodNode {
                nm = "nofunc." + nm
        }
        return gf.Pkg.Lookup(nm)
}

func MakeDictSym(gf *types.Sym, targs []*types.Type, hasBrackets bool) *types.Sym {
        for _, targ := range targs {
                if targ.HasTParam() {
                        fmt.Printf("FUNCTION %s\n", gf.Name)
                        for _, targ := range targs {
                                fmt.Printf("  PARAM %+v\n", targ)
                        }
                        panic("dictionary should always have concrete type args")
                }
        }
        name := makeInstName1(gf.Name, targs, hasBrackets)
        name = fmt.Sprintf("%s.%s", objabi.GlobalDictPrefix, name)
        return gf.Pkg.Lookup(name)
}

func assert(p bool) {
        base.Assert(p)
}

// List of newly fully-instantiated types who should have their methods generated.
var instTypeList []*types.Type

// NeedInstType adds a new fully-instantiated type to instTypeList.
func NeedInstType(t *types.Type) {
        instTypeList = append(instTypeList, t)
}

// GetInstTypeList returns the current contents of instTypeList.
func GetInstTypeList() []*types.Type {
        r := instTypeList
        return r
}

// ClearInstTypeList clears the contents of instTypeList.
func ClearInstTypeList() {
        instTypeList = nil
}

// General type substituter, for replacing typeparams with type args.
type Tsubster struct {
        Tparams []*types.Type
        Targs   []*types.Type
        // If non-nil, the substitution map from name nodes in the generic function to the
        // name nodes in the new stenciled function.
        Vars map[*ir.Name]*ir.Name
        // If non-nil, function to substitute an incomplete (TFORW) type.
        SubstForwFunc func(*types.Type) *types.Type
        // Prevent endless recursion on functions. See #51832.
        Funcs map[*types.Type]bool
}

// Typ computes the type obtained by substituting any type parameter or shape in t
// that appears in subst.Tparams with the corresponding type argument in subst.Targs.
// If t contains no type parameters, the result is t; otherwise the result is a new
// type. It deals with recursive types by using TFORW types and finding partially or
// fully created types via sym.Def.
func (ts *Tsubster) Typ(t *types.Type) *types.Type {
        // Defer the CheckSize calls until we have fully-defined
        // (possibly-recursive) top-level type.
        types.DeferCheckSize()
        r := ts.typ1(t)
        types.ResumeCheckSize()
        return r
}

func (ts *Tsubster) typ1(t *types.Type) *types.Type {
        hasParamOrShape := t.HasTParam() || t.HasShape()
        if !hasParamOrShape && t.Kind() != types.TFUNC {
                // Note: function types need to be copied regardless, as the
                // types of closures may contain declarations that need
                // to be copied. See #45738.
                return t
        }

        if t.IsTypeParam() || t.IsShape() {
                for i, tp := range ts.Tparams {
                        if tp == t {
                                return ts.Targs[i]
                        }
                }
                // If t is a simple typeparam T, then t has the name/symbol 'T'
                // and t.Underlying() == t.
                //
                // However, consider the type definition: 'type P[T any] T'. We
                // might use this definition so we can have a variant of type T
                // that we can add new methods to. Suppose t is a reference to
                // P[T]. t has the name 'P[T]', but its kind is TTYPEPARAM,
                // because P[T] is defined as T. If we look at t.Underlying(), it
                // is different, because the name of t.Underlying() is 'T' rather
                // than 'P[T]'. But the kind of t.Underlying() is also TTYPEPARAM.
                // In this case, we do the needed recursive substitution in the
                // case statement below.
                if t.Underlying() == t {
                        // t is a simple typeparam that didn't match anything in tparam
                        return t
                }
                // t is a more complex typeparam (e.g. P[T], as above, whose
                // definition is just T).
                assert(t.Sym() != nil)
        }

        var newsym *types.Sym
        var neededTargs []*types.Type
        var targsChanged bool // == are there any substitutions from this
        var forw *types.Type

        if t.Sym() != nil && hasParamOrShape {
                // Need to test for t.HasTParam() again because of special TFUNC case above.
                // Translate the type params for this type according to
                // the tparam/targs mapping from subst.
                neededTargs = make([]*types.Type, len(t.RParams()))
                for i, rparam := range t.RParams() {
                        neededTargs[i] = ts.typ1(rparam)
                        if !types.IdenticalStrict(neededTargs[i], rparam) {
                                targsChanged = true
                        }
                }
                // For a named (defined) type, we have to change the name of the
                // type as well. We do this first, so we can look up if we've
                // already seen this type during this substitution or other
                // definitions/substitutions.
                genName := genericTypeName(t.Sym())
                newsym = t.Sym().Pkg.Lookup(InstTypeName(genName, neededTargs))
                if newsym.Def != nil {
                        // We've already created this instantiated defined type.
                        return newsym.Def.Type()
                }

                // In order to deal with recursive generic types, create a TFORW
                // type initially and set the Def field of its sym, so it can be
                // found if this type appears recursively within the type.
                forw = NewIncompleteNamedType(t.Pos(), newsym)
                //println("Creating new type by sub", newsym.Name, forw.HasTParam())
                forw.SetRParams(neededTargs)
                // Copy the OrigType from the re-instantiated type (which is the sym of
                // the base generic type).
                assert(t.OrigType() != nil)
                forw.SetOrigType(t.OrigType())
        }

        var newt *types.Type

        switch t.Kind() {
        case types.TTYPEPARAM:
                if t.Sym() == newsym && !targsChanged {
                        // The substitution did not change the type.
                        return t
                }
                // Substitute the underlying typeparam (e.g. T in P[T], see
                // the example describing type P[T] above).
                newt = ts.typ1(t.Underlying())
                assert(newt != t)

        case types.TARRAY:
                elem := t.Elem()
                newelem := ts.typ1(elem)
                if newelem != elem || targsChanged {
                        newt = types.NewArray(newelem, t.NumElem())
                }

        case types.TPTR:
                elem := t.Elem()
                newelem := ts.typ1(elem)
                if newelem != elem || targsChanged {
                        newt = types.NewPtr(newelem)
                }

        case types.TSLICE:
                elem := t.Elem()
                newelem := ts.typ1(elem)
                if newelem != elem || targsChanged {
                        newt = types.NewSlice(newelem)
                }

        case types.TSTRUCT:
                newt = ts.tstruct(t, targsChanged)
                if newt == t {
                        newt = nil
                }

        case types.TFUNC:
                // watch out for endless recursion on plain function types that mention themselves, e.g. "type T func() T"
                if !hasParamOrShape {
                        if ts.Funcs[t] { // Visit such function types only once.
                                return t
                        }
                        if ts.Funcs == nil {
                                // allocate lazily
                                ts.Funcs = make(map[*types.Type]bool)
                        }
                        ts.Funcs[t] = true
                }
                newrecvs := ts.tstruct(t.Recvs(), false)
                newparams := ts.tstruct(t.Params(), false)
                newresults := ts.tstruct(t.Results(), false)
                // Translate the tparams of a signature.
                newtparams := ts.tstruct(t.TParams(), false)
                if newrecvs != t.Recvs() || newparams != t.Params() ||
                        newresults != t.Results() || newtparams != t.TParams() || targsChanged {
                        // If any types have changed, then the all the fields of
                        // of recv, params, and results must be copied, because they have
                        // offset fields that are dependent, and so must have an
                        // independent copy for each new signature.
                        var newrecv *types.Field
                        if newrecvs.NumFields() > 0 {
                                if newrecvs == t.Recvs() {
                                        newrecvs = ts.tstruct(t.Recvs(), true)
                                }
                                newrecv = newrecvs.Field(0)
                        }
                        if newparams == t.Params() {
                                newparams = ts.tstruct(t.Params(), true)
                        }
                        if newresults == t.Results() {
                                newresults = ts.tstruct(t.Results(), true)
                        }
                        var tparamfields []*types.Field
                        if newtparams.HasTParam() {
                                tparamfields = newtparams.FieldSlice()
                        } else {
                                // Completely remove the tparams from the resulting
                                // signature, if the tparams are now concrete types.
                                tparamfields = nil
                        }
                        newt = types.NewSignature(t.Pkg(), newrecv, tparamfields,
                                newparams.FieldSlice(), newresults.FieldSlice())
                }
                if !hasParamOrShape {
                        delete(ts.Funcs, t)
                }

        case types.TINTER:
                newt = ts.tinter(t, targsChanged)
                if newt == t {
                        newt = nil
                }

        case types.TMAP:
                newkey := ts.typ1(t.Key())
                newval := ts.typ1(t.Elem())
                if newkey != t.Key() || newval != t.Elem() || targsChanged {
                        newt = types.NewMap(newkey, newval)
                }

        case types.TCHAN:
                elem := t.Elem()
                newelem := ts.typ1(elem)
                if newelem != elem || targsChanged {
                        newt = types.NewChan(newelem, t.ChanDir())
                }
        case types.TFORW:
                if ts.SubstForwFunc != nil {
                        return ts.SubstForwFunc(forw)
                } else {
                        assert(false)
                }
        case types.TINT, types.TINT8, types.TINT16, types.TINT32, types.TINT64,
                types.TUINT, types.TUINT8, types.TUINT16, types.TUINT32, types.TUINT64,
                types.TUINTPTR, types.TBOOL, types.TSTRING, types.TFLOAT32, types.TFLOAT64, types.TCOMPLEX64, types.TCOMPLEX128, types.TUNSAFEPTR:
                newt = t.Underlying()
        case types.TUNION:
                nt := t.NumTerms()
                newterms := make([]*types.Type, nt)
                tildes := make([]bool, nt)
                changed := false
                for i := 0; i < nt; i++ {
                        term, tilde := t.Term(i)
                        tildes[i] = tilde
                        newterms[i] = ts.typ1(term)
                        if newterms[i] != term {
                                changed = true
                        }
                }
                if changed {
                        newt = types.NewUnion(newterms, tildes)
                }
        default:
                panic(fmt.Sprintf("Bad type in (*TSubster).Typ: %v", t.Kind()))
        }
        if newt == nil {
                // Even though there were typeparams in the type, there may be no
                // change if this is a function type for a function call (which will
                // have its own tparams/targs in the function instantiation).
                return t
        }

        if forw != nil {
                forw.SetUnderlying(newt)
                newt = forw
        }

        if !newt.HasTParam() && !newt.IsFuncArgStruct() {
                // Calculate the size of any new types created. These will be
                // deferred until the top-level ts.Typ() or g.typ() (if this is
                // called from g.fillinMethods()).
                types.CheckSize(newt)
        }

        if t.Kind() != types.TINTER && t.Methods().Len() > 0 {
                // Fill in the method info for the new type.
                var newfields []*types.Field
                newfields = make([]*types.Field, t.Methods().Len())
                for i, f := range t.Methods().Slice() {
                        t2 := ts.typ1(f.Type)
                        oldsym := f.Nname.Sym()

                        // Use the name of the substituted receiver to create the
                        // method name, since the receiver name may have many levels
                        // of nesting (brackets) with type names to be substituted.
                        recvType := t2.Recv().Type
                        var nm string
                        if recvType.IsPtr() {
                                recvType = recvType.Elem()
                                nm = "(*" + recvType.Sym().Name + ")." + f.Sym.Name
                        } else {
                                nm = recvType.Sym().Name + "." + f.Sym.Name
                        }
                        if recvType.RParams()[0].HasShape() {
                                // We add "nofunc" to methods of shape type to avoid
                                // conflict with the name of the shape-based helper
                                // function. See header comment of MakeFuncInstSym.
                                nm = "nofunc." + nm
                        }
                        newsym := oldsym.Pkg.Lookup(nm)
                        var nname *ir.Name
                        if newsym.Def != nil {
                                nname = newsym.Def.(*ir.Name)
                        } else {
                                nname = ir.NewNameAt(f.Pos, newsym)
                                nname.SetType(t2)
                                ir.MarkFunc(nname)
                                newsym.Def = nname
                        }
                        newfields[i] = types.NewField(f.Pos, f.Sym, t2)
                        newfields[i].Nname = nname
                }
                newt.Methods().Set(newfields)
                if !newt.HasTParam() && !newt.HasShape() {
                        // Generate all the methods for a new fully-instantiated type.

                        NeedInstType(newt)
                }
        }
        return newt
}

// tstruct substitutes type params in types of the fields of a structure type. For
// each field, tstruct copies the Nname, and translates it if Nname is in
// ts.vars. To always force the creation of a new (top-level) struct,
// regardless of whether anything changed with the types or names of the struct's
// fields, set force to true.
func (ts *Tsubster) tstruct(t *types.Type, force bool) *types.Type {
        if t.NumFields() == 0 {
                if t.HasTParam() || t.HasShape() {
                        // For an empty struct, we need to return a new type, if
                        // substituting from a generic type or shape type, since it
                        // will change HasTParam/HasShape flags.
                        return types.NewStruct(t.Pkg(), nil)
                }
                return t
        }
        var newfields []*types.Field
        if force {
                newfields = make([]*types.Field, t.NumFields())
        }
        for i, f := range t.Fields().Slice() {
                t2 := ts.typ1(f.Type)
                if (t2 != f.Type || f.Nname != nil) && newfields == nil {
                        newfields = make([]*types.Field, t.NumFields())
                        for j := 0; j < i; j++ {
                                newfields[j] = t.Field(j)
                        }
                }
                if newfields != nil {
                        newfields[i] = types.NewField(f.Pos, f.Sym, t2)
                        newfields[i].Embedded = f.Embedded
                        newfields[i].Note = f.Note
                        if f.IsDDD() {
                                newfields[i].SetIsDDD(true)
                        }
                        if f.Nointerface() {
                                newfields[i].SetNointerface(true)
                        }
                        if f.Nname != nil && ts.Vars != nil {
                                n := f.Nname.(*ir.Name)
                                v := ts.Vars[n]
                                if v != nil {
                                        // This is the case where we are
                                        // translating the type of the function we
                                        // are substituting, so its dcls are in
                                        // the subst.ts.vars table, and we want to
                                        // change to reference the new dcl.
                                        newfields[i].Nname = v
                                } else if ir.IsBlank(n) {
                                        // Blank variable is not dcl list. Make a
                                        // new one to not share.
                                        m := ir.NewNameAt(n.Pos(), ir.BlankNode.Sym())
                                        m.SetType(n.Type())
                                        m.SetTypecheck(1)
                                        newfields[i].Nname = m
                                } else {
                                        // This is the case where we are
                                        // translating the type of a function
                                        // reference inside the function we are
                                        // substituting, so we leave the Nname
                                        // value as is.
                                        newfields[i].Nname = f.Nname
                                }
                        }
                }
        }
        if newfields != nil {
                news := types.NewStruct(t.Pkg(), newfields)
                news.StructType().Funarg = t.StructType().Funarg
                return news
        }
        return t

}

// tinter substitutes type params in types of the methods of an interface type.
func (ts *Tsubster) tinter(t *types.Type, force bool) *types.Type {
        if t.Methods().Len() == 0 {
                if t.HasTParam() || t.HasShape() {
                        // For an empty interface, we need to return a new type, if
                        // substituting from a generic type or shape type, since
                        // since it will change HasTParam/HasShape flags.
                        return types.NewInterface(t.Pkg(), nil, false)
                }
                return t
        }
        var newfields []*types.Field
        if force {
                newfields = make([]*types.Field, t.Methods().Len())
        }
        for i, f := range t.Methods().Slice() {
                t2 := ts.typ1(f.Type)
                if (t2 != f.Type || f.Nname != nil) && newfields == nil {
                        newfields = make([]*types.Field, t.Methods().Len())
                        for j := 0; j < i; j++ {
                                newfields[j] = t.Methods().Index(j)
                        }
                }
                if newfields != nil {
                        newfields[i] = types.NewField(f.Pos, f.Sym, t2)
                }
        }
        if newfields != nil {
                return types.NewInterface(t.Pkg(), newfields, t.IsImplicit())
        }
        return t
}

// genericTypeName returns the name of the base generic type for the type named by
// sym. It simply returns the name obtained by removing everything after the
// first bracket ("[").
func genericTypeName(sym *types.Sym) string {
        return sym.Name[0:strings.Index(sym.Name, "[")]
}

// getShapes appends the list of the shape types that are used within type t to
// listp. The type traversal is simplified for two reasons: (1) we can always stop a
// type traversal when t.HasShape() is false; and (2) shape types can't appear inside
// a named type, except for the type args of a generic type. So, the traversal will
// always stop before we have to deal with recursive types.
func getShapes(t *types.Type, listp *[]*types.Type) {
        if !t.HasShape() {
                return
        }
        if t.IsShape() {
                *listp = append(*listp, t)
                return
        }

        if t.Sym() != nil {
                // A named type can't have shapes in it, except for type args of a
                // generic type. We will have to deal with this differently once we
                // alloc local types in generic functions (#47631).
                for _, rparam := range t.RParams() {
                        getShapes(rparam, listp)
                }
                return
        }

        switch t.Kind() {
        case types.TARRAY, types.TPTR, types.TSLICE, types.TCHAN:
                getShapes(t.Elem(), listp)

        case types.TSTRUCT:
                for _, f := range t.FieldSlice() {
                        getShapes(f.Type, listp)
                }

        case types.TFUNC:
                for _, f := range t.Recvs().FieldSlice() {
                        getShapes(f.Type, listp)
                }
                for _, f := range t.Params().FieldSlice() {
                        getShapes(f.Type, listp)
                }
                for _, f := range t.Results().FieldSlice() {
                        getShapes(f.Type, listp)
                }
                for _, f := range t.TParams().FieldSlice() {
                        getShapes(f.Type, listp)
                }

        case types.TINTER:
                for _, f := range t.Methods().Slice() {
                        getShapes(f.Type, listp)
                }

        case types.TMAP:
                getShapes(t.Key(), listp)
                getShapes(t.Elem(), listp)

        default:
                panic(fmt.Sprintf("Bad type in getShapes: %v", t.Kind()))
        }

}

// Shapify takes a concrete type and a type param index, and returns a GCshape type that can
// be used in place of the input type and still generate identical code.
// No methods are added - all methods calls directly on a shape should
// be done by converting to an interface using the dictionary.
//
// For now, we only consider two types to have the same shape, if they have exactly
// the same underlying type or they are both pointer types.
//
// tparam is the associated typeparam - it must be TTYPEPARAM type. If there is a
// structural type for the associated type param (not common), then a pointer type t
// is mapped to its underlying type, rather than being merged with other pointers.
//
// Shape types are also distinguished by the index of the type in a type param/arg
// list. We need to do this so we can distinguish and substitute properly for two
// type params in the same function that have the same shape for a particular
// instantiation.
func Shapify(t *types.Type, index int, tparam *types.Type) *types.Type {
        assert(!t.IsShape())
        if t.HasShape() {
                // We are sometimes dealing with types from a shape instantiation
                // that were constructed from existing shape types, so t may
                // sometimes have shape types inside it. In that case, we find all
                // those shape types with getShapes() and replace them with their
                // underlying type.
                //
                // If we don't do this, we may create extra unneeded shape types that
                // have these other shape types embedded in them. This may lead to
                // generating extra shape instantiations, and a mismatch between the
                // instantiations that we used in generating dictionaries and the
                // instantations that are actually called. (#51303).
                list := []*types.Type{}
                getShapes(t, &list)
                list2 := make([]*types.Type, len(list))
                for i, shape := range list {
                        list2[i] = shape.Underlying()
                }
                ts := Tsubster{
                        Tparams: list,
                        Targs:   list2,
                }
                t = ts.Typ(t)
        }
        // Map all types with the same underlying type to the same shape.
        u := t.Underlying()

        // All pointers have the same shape.
        // TODO: Make unsafe.Pointer the same shape as normal pointers.
        // Note: pointers to arrays are special because of slice-to-array-pointer
        // conversions. See issue 49295.
        if u.Kind() == types.TPTR && u.Elem().Kind() != types.TARRAY &&
                tparam.Bound().StructuralType() == nil && !u.Elem().NotInHeap() {
                u = types.Types[types.TUINT8].PtrTo()
        }

        submap := shapeMap[index]
        if submap == nil {
                submap = map[*types.Type]*types.Type{}
                shapeMap[index] = submap
        }
        if s := submap[u]; s != nil {
                return s
        }

        // LinkString specifies the type uniquely, but has no spaces.
        nm := fmt.Sprintf("%s_%d", u.LinkString(), index)
        sym := types.ShapePkg.Lookup(nm)
        if sym.Def != nil {
                // Use any existing type with the same name
                submap[u] = sym.Def.Type()
                return submap[u]
        }
        name := ir.NewDeclNameAt(u.Pos(), ir.OTYPE, sym)
        s := types.NewNamed(name)
        sym.Def = name
        s.SetUnderlying(u)
        s.SetIsShape(true)
        s.SetHasShape(true)
        types.CalcSize(s)
        name.SetType(s)
        name.SetTypecheck(1)
        submap[u] = s
        return s
}

var shapeMap = map[int]map[*types.Type]*types.Type{}