Source file src/cmd/compile/internal/noder/stencil.go

     1  // Copyright 2021 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This file will evolve, since we plan to do a mix of stenciling and passing
     6  // around dictionaries.
     7  
     8  package noder
     9  
    10  import (
    11  	"cmd/compile/internal/base"
    12  	"cmd/compile/internal/ir"
    13  	"cmd/compile/internal/objw"
    14  	"cmd/compile/internal/reflectdata"
    15  	"cmd/compile/internal/typecheck"
    16  	"cmd/compile/internal/types"
    17  	"cmd/internal/obj"
    18  	"cmd/internal/src"
    19  	"fmt"
    20  	"go/constant"
    21  )
    22  
    23  // Enable extra consistency checks.
    24  const doubleCheck = false
    25  
    26  func assert(p bool) {
    27  	base.Assert(p)
    28  }
    29  
    30  // For outputting debug information on dictionary format and instantiated dictionaries
    31  // (type arg, derived types, sub-dictionary, and itab entries).
    32  var infoPrintMode = false
    33  
    34  func infoPrint(format string, a ...interface{}) {
    35  	if infoPrintMode {
    36  		fmt.Printf(format, a...)
    37  	}
    38  }
    39  
    40  var geninst genInst
    41  
    42  func BuildInstantiations() {
    43  	geninst.instInfoMap = make(map[*types.Sym]*instInfo)
    44  	geninst.buildInstantiations()
    45  	geninst.instInfoMap = nil
    46  }
    47  
    48  // buildInstantiations scans functions for generic function calls and methods, and
    49  // creates the required instantiations. It also creates instantiated methods for all
    50  // fully-instantiated generic types that have been encountered already or new ones
    51  // that are encountered during the instantiation process. It scans all declarations
    52  // in typecheck.Target.Decls first, before scanning any new instantiations created.
    53  func (g *genInst) buildInstantiations() {
    54  	// Instantiate the methods of instantiated generic types that we have seen so far.
    55  	g.instantiateMethods()
    56  
    57  	// Scan all currentdecls for call to generic functions/methods.
    58  	n := len(typecheck.Target.Decls)
    59  	for i := 0; i < n; i++ {
    60  		g.scanForGenCalls(typecheck.Target.Decls[i])
    61  	}
    62  
    63  	// Scan all new instantiations created due to g.instantiateMethods() and the
    64  	// scan of current decls. This loop purposely runs until no new
    65  	// instantiations are created.
    66  	for i := 0; i < len(g.newInsts); i++ {
    67  		g.scanForGenCalls(g.newInsts[i])
    68  	}
    69  
    70  	g.finalizeSyms()
    71  
    72  	// All the instantiations and dictionaries have been created. Now go through
    73  	// each new instantiation and transform the various operations that need to make
    74  	// use of their dictionary.
    75  	l := len(g.newInsts)
    76  	for _, fun := range g.newInsts {
    77  		info := g.instInfoMap[fun.Sym()]
    78  		g.dictPass(info)
    79  		if doubleCheck {
    80  			ir.Visit(info.fun, func(n ir.Node) {
    81  				if n.Op() != ir.OCONVIFACE {
    82  					return
    83  				}
    84  				c := n.(*ir.ConvExpr)
    85  				if c.X.Type().HasShape() && !c.X.Type().IsInterface() {
    86  					ir.Dump("BAD FUNCTION", info.fun)
    87  					ir.Dump("BAD CONVERSION", c)
    88  					base.Fatalf("converting shape type to interface")
    89  				}
    90  			})
    91  		}
    92  		if base.Flag.W > 1 {
    93  			ir.Dump(fmt.Sprintf("\ndictpass %v", info.fun), info.fun)
    94  		}
    95  	}
    96  	assert(l == len(g.newInsts))
    97  	g.newInsts = nil
    98  }
    99  
   100  // scanForGenCalls scans a single function (or global assignment), looking for
   101  // references to generic functions/methods. At each such reference, it creates any
   102  // required instantiation and transforms the reference.
   103  func (g *genInst) scanForGenCalls(decl ir.Node) {
   104  	switch decl.Op() {
   105  	case ir.ODCLFUNC:
   106  		if decl.Type().HasTParam() {
   107  			// Skip any generic functions
   108  			return
   109  		}
   110  		// transformCall() below depends on CurFunc being set.
   111  		ir.CurFunc = decl.(*ir.Func)
   112  
   113  	case ir.OAS, ir.OAS2, ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV, ir.OASOP:
   114  		// These are all the various kinds of global assignments,
   115  		// whose right-hand-sides might contain a function
   116  		// instantiation.
   117  
   118  	default:
   119  		// The other possible ops at the top level are ODCLCONST
   120  		// and ODCLTYPE, which don't have any function
   121  		// instantiations.
   122  		return
   123  	}
   124  
   125  	// Search for any function references using generic function/methods. Then
   126  	// create the needed instantiated function if it hasn't been created yet, and
   127  	// change to calling that function directly.
   128  	modified := false
   129  	closureRequired := false
   130  	// declInfo will be non-nil exactly if we are scanning an instantiated function
   131  	declInfo := g.instInfoMap[decl.Sym()]
   132  
   133  	ir.Visit(decl, func(n ir.Node) {
   134  		if n.Op() == ir.OFUNCINST {
   135  			// generic F, not immediately called
   136  			closureRequired = true
   137  		}
   138  		if (n.Op() == ir.OMETHEXPR || n.Op() == ir.OMETHVALUE) && len(deref(n.(*ir.SelectorExpr).X.Type()).RParams()) > 0 && !types.IsInterfaceMethod(n.(*ir.SelectorExpr).Selection.Type) {
   139  			// T.M or x.M, where T or x is generic, but not immediately
   140  			// called. Not necessary if the method selected is
   141  			// actually for an embedded interface field.
   142  			closureRequired = true
   143  		}
   144  		if n.Op() == ir.OCALL && n.(*ir.CallExpr).X.Op() == ir.OFUNCINST {
   145  			// We have found a function call using a generic function
   146  			// instantiation.
   147  			call := n.(*ir.CallExpr)
   148  			inst := call.X.(*ir.InstExpr)
   149  			nameNode, isMeth := g.getInstNameNode(inst)
   150  			targs := typecheck.TypesOf(inst.Targs)
   151  			st := g.getInstantiation(nameNode, targs, isMeth).fun
   152  			dictValue, usingSubdict := g.getDictOrSubdict(declInfo, n, nameNode, targs, isMeth)
   153  			if infoPrintMode {
   154  				dictkind := "Main dictionary"
   155  				if usingSubdict {
   156  					dictkind = "Sub-dictionary"
   157  				}
   158  				if inst.X.Op() == ir.OMETHVALUE {
   159  					fmt.Printf("%s in %v at generic method call: %v - %v\n", dictkind, decl, inst.X, call)
   160  				} else {
   161  					fmt.Printf("%s in %v at generic function call: %v - %v\n", dictkind, decl, inst.X, call)
   162  				}
   163  			}
   164  
   165  			// Transform the Call now, which changes OCALL to
   166  			// OCALLFUNC and does typecheckaste/assignconvfn. Do
   167  			// it before installing the instantiation, so we are
   168  			// checking against non-shape param types in
   169  			// typecheckaste.
   170  			transformCall(call)
   171  
   172  			// Replace the OFUNCINST with a direct reference to the
   173  			// new stenciled function
   174  			call.X = st.Nname
   175  			if inst.X.Op() == ir.OMETHVALUE {
   176  				// When we create an instantiation of a method
   177  				// call, we make it a function. So, move the
   178  				// receiver to be the first arg of the function
   179  				// call.
   180  				call.Args.Prepend(inst.X.(*ir.SelectorExpr).X)
   181  			}
   182  
   183  			// Add dictionary to argument list.
   184  			call.Args.Prepend(dictValue)
   185  			modified = true
   186  		}
   187  		if n.Op() == ir.OCALLMETH && n.(*ir.CallExpr).X.Op() == ir.ODOTMETH && len(deref(n.(*ir.CallExpr).X.Type().Recv().Type).RParams()) > 0 {
   188  			// Method call on a generic type, which was instantiated by stenciling.
   189  			// Method calls on explicitly instantiated types will have an OFUNCINST
   190  			// and are handled above.
   191  			call := n.(*ir.CallExpr)
   192  			meth := call.X.(*ir.SelectorExpr)
   193  			targs := deref(meth.Type().Recv().Type).RParams()
   194  
   195  			t := meth.X.Type()
   196  			baseType := deref(t).OrigType()
   197  			var gf *ir.Name
   198  			for _, m := range baseType.Methods().Slice() {
   199  				if meth.Sel == m.Sym {
   200  					gf = m.Nname.(*ir.Name)
   201  					break
   202  				}
   203  			}
   204  
   205  			// Transform the Call now, which changes OCALL
   206  			// to OCALLFUNC and does typecheckaste/assignconvfn.
   207  			transformCall(call)
   208  
   209  			st := g.getInstantiation(gf, targs, true).fun
   210  			dictValue, usingSubdict := g.getDictOrSubdict(declInfo, n, gf, targs, true)
   211  			// We have to be using a subdictionary, since this is
   212  			// a generic method call.
   213  			assert(usingSubdict)
   214  
   215  			// Transform to a function call, by appending the
   216  			// dictionary and the receiver to the args.
   217  			call.SetOp(ir.OCALLFUNC)
   218  			call.X = st.Nname
   219  			call.Args.Prepend(dictValue, meth.X)
   220  			modified = true
   221  		}
   222  	})
   223  
   224  	// If we found a reference to a generic instantiation that wasn't an
   225  	// immediate call, then traverse the nodes of decl again (with
   226  	// EditChildren rather than Visit), where we actually change the
   227  	// reference to the instantiation to a closure that captures the
   228  	// dictionary, then does a direct call.
   229  	// EditChildren is more expensive than Visit, so we only do this
   230  	// in the infrequent case of an OFUNCINST without a corresponding
   231  	// call.
   232  	if closureRequired {
   233  		modified = true
   234  		var edit func(ir.Node) ir.Node
   235  		var outer *ir.Func
   236  		if f, ok := decl.(*ir.Func); ok {
   237  			outer = f
   238  		}
   239  		edit = func(x ir.Node) ir.Node {
   240  			if x.Op() == ir.OFUNCINST {
   241  				child := x.(*ir.InstExpr).X
   242  				if child.Op() == ir.OMETHEXPR || child.Op() == ir.OMETHVALUE {
   243  					// Call EditChildren on child (x.X),
   244  					// not x, so that we don't do
   245  					// buildClosure() on the
   246  					// METHEXPR/METHVALUE nodes as well.
   247  					ir.EditChildren(child, edit)
   248  					return g.buildClosure(outer, x)
   249  				}
   250  			}
   251  			ir.EditChildren(x, edit)
   252  			switch {
   253  			case x.Op() == ir.OFUNCINST:
   254  				return g.buildClosure(outer, x)
   255  			case (x.Op() == ir.OMETHEXPR || x.Op() == ir.OMETHVALUE) &&
   256  				len(deref(x.(*ir.SelectorExpr).X.Type()).RParams()) > 0 &&
   257  				!types.IsInterfaceMethod(x.(*ir.SelectorExpr).Selection.Type):
   258  				return g.buildClosure(outer, x)
   259  			}
   260  			return x
   261  		}
   262  		edit(decl)
   263  	}
   264  	if base.Flag.W > 1 && modified {
   265  		ir.Dump(fmt.Sprintf("\nmodified %v", decl), decl)
   266  	}
   267  	ir.CurFunc = nil
   268  	// We may have seen new fully-instantiated generic types while
   269  	// instantiating any needed functions/methods in the above
   270  	// function. If so, instantiate all the methods of those types
   271  	// (which will then lead to more function/methods to scan in the loop).
   272  	g.instantiateMethods()
   273  }
   274  
   275  // buildClosure makes a closure to implement x, a OFUNCINST or OMETHEXPR/OMETHVALUE
   276  // of generic type. outer is the containing function (or nil if closure is
   277  // in a global assignment instead of a function).
   278  func (g *genInst) buildClosure(outer *ir.Func, x ir.Node) ir.Node {
   279  	pos := x.Pos()
   280  	var target *ir.Func   // target instantiated function/method
   281  	var dictValue ir.Node // dictionary to use
   282  	var rcvrValue ir.Node // receiver, if a method value
   283  	typ := x.Type()       // type of the closure
   284  	var outerInfo *instInfo
   285  	if outer != nil {
   286  		outerInfo = g.instInfoMap[outer.Sym()]
   287  	}
   288  	usingSubdict := false
   289  	valueMethod := false
   290  	if x.Op() == ir.OFUNCINST {
   291  		inst := x.(*ir.InstExpr)
   292  
   293  		// Type arguments we're instantiating with.
   294  		targs := typecheck.TypesOf(inst.Targs)
   295  
   296  		// Find the generic function/method.
   297  		var gf *ir.Name
   298  		if inst.X.Op() == ir.ONAME {
   299  			// Instantiating a generic function call.
   300  			gf = inst.X.(*ir.Name)
   301  		} else if inst.X.Op() == ir.OMETHVALUE {
   302  			// Instantiating a method value x.M.
   303  			se := inst.X.(*ir.SelectorExpr)
   304  			rcvrValue = se.X
   305  			gf = se.Selection.Nname.(*ir.Name)
   306  		} else {
   307  			panic("unhandled")
   308  		}
   309  
   310  		// target is the instantiated function we're trying to call.
   311  		// For functions, the target expects a dictionary as its first argument.
   312  		// For method values, the target expects a dictionary and the receiver
   313  		// as its first two arguments.
   314  		// dictValue is the value to use for the dictionary argument.
   315  		target = g.getInstantiation(gf, targs, rcvrValue != nil).fun
   316  		dictValue, usingSubdict = g.getDictOrSubdict(outerInfo, x, gf, targs, rcvrValue != nil)
   317  		if infoPrintMode {
   318  			dictkind := "Main dictionary"
   319  			if usingSubdict {
   320  				dictkind = "Sub-dictionary"
   321  			}
   322  			if rcvrValue == nil {
   323  				fmt.Printf("%s in %v for generic function value %v\n", dictkind, outer, inst.X)
   324  			} else {
   325  				fmt.Printf("%s in %v for generic method value %v\n", dictkind, outer, inst.X)
   326  			}
   327  		}
   328  	} else { // ir.OMETHEXPR or ir.METHVALUE
   329  		// Method expression T.M where T is a generic type.
   330  		se := x.(*ir.SelectorExpr)
   331  		targs := deref(se.X.Type()).RParams()
   332  		if len(targs) == 0 {
   333  			panic("bad")
   334  		}
   335  		if x.Op() == ir.OMETHVALUE {
   336  			rcvrValue = se.X
   337  		}
   338  
   339  		// se.X.Type() is the top-level type of the method expression. To
   340  		// correctly handle method expressions involving embedded fields,
   341  		// look up the generic method below using the type of the receiver
   342  		// of se.Selection, since that will be the type that actually has
   343  		// the method.
   344  		recv := deref(se.Selection.Type.Recv().Type)
   345  		if len(recv.RParams()) == 0 {
   346  			// The embedded type that actually has the method is not
   347  			// actually generic, so no need to build a closure.
   348  			return x
   349  		}
   350  		baseType := recv.OrigType()
   351  		var gf *ir.Name
   352  		for _, m := range baseType.Methods().Slice() {
   353  			if se.Sel == m.Sym {
   354  				gf = m.Nname.(*ir.Name)
   355  				break
   356  			}
   357  		}
   358  		if !gf.Type().Recv().Type.IsPtr() {
   359  			// Remember if value method, so we can detect (*T).M case.
   360  			valueMethod = true
   361  		}
   362  		target = g.getInstantiation(gf, targs, true).fun
   363  		dictValue, usingSubdict = g.getDictOrSubdict(outerInfo, x, gf, targs, true)
   364  		if infoPrintMode {
   365  			dictkind := "Main dictionary"
   366  			if usingSubdict {
   367  				dictkind = "Sub-dictionary"
   368  			}
   369  			fmt.Printf("%s in %v for method expression %v\n", dictkind, outer, x)
   370  		}
   371  	}
   372  
   373  	// Build a closure to implement a function instantiation.
   374  	//
   375  	//   func f[T any] (int, int) (int, int) { ...whatever... }
   376  	//
   377  	// Then any reference to f[int] not directly called gets rewritten to
   378  	//
   379  	//   .dictN := ... dictionary to use ...
   380  	//   func(a0, a1 int) (r0, r1 int) {
   381  	//     return .inst.f[int](.dictN, a0, a1)
   382  	//   }
   383  	//
   384  	// Similarly for method expressions,
   385  	//
   386  	//   type g[T any] ....
   387  	//   func (rcvr g[T]) f(a0, a1 int) (r0, r1 int) { ... }
   388  	//
   389  	// Any reference to g[int].f not directly called gets rewritten to
   390  	//
   391  	//   .dictN := ... dictionary to use ...
   392  	//   func(rcvr g[int], a0, a1 int) (r0, r1 int) {
   393  	//     return .inst.g[int].f(.dictN, rcvr, a0, a1)
   394  	//   }
   395  	//
   396  	// Also method values
   397  	//
   398  	//   var x g[int]
   399  	//
   400  	// Any reference to x.f not directly called gets rewritten to
   401  	//
   402  	//   .dictN := ... dictionary to use ...
   403  	//   x2 := x
   404  	//   func(a0, a1 int) (r0, r1 int) {
   405  	//     return .inst.g[int].f(.dictN, x2, a0, a1)
   406  	//   }
   407  
   408  	// Make a new internal function.
   409  	fn, formalParams, formalResults := startClosure(pos, outer, typ)
   410  
   411  	// This is the dictionary we want to use.
   412  	// It may be a constant, it may be the outer functions's dictionary, or it may be
   413  	// a subdictionary acquired from the outer function's dictionary.
   414  	// For the latter, dictVar is a variable in the outer function's scope, set to the subdictionary
   415  	// read from the outer function's dictionary.
   416  	var dictVar *ir.Name
   417  	var dictAssign *ir.AssignStmt
   418  	if outer != nil {
   419  		dictVar = ir.NewNameAt(pos, typecheck.LookupNum(typecheck.LocalDictName, g.dnum))
   420  		dictVar.SetSym(outer.Sym().Pkg.Lookup(dictVar.Sym().Name))
   421  		g.dnum++
   422  		dictVar.Class = ir.PAUTO
   423  		typed(types.Types[types.TUINTPTR], dictVar)
   424  		dictVar.Curfn = outer
   425  		dictAssign = ir.NewAssignStmt(pos, dictVar, dictValue)
   426  		dictAssign.SetTypecheck(1)
   427  		dictVar.Defn = dictAssign
   428  		outer.Dcl = append(outer.Dcl, dictVar)
   429  	}
   430  	// assign the receiver to a temporary.
   431  	var rcvrVar *ir.Name
   432  	var rcvrAssign ir.Node
   433  	if rcvrValue != nil {
   434  		rcvrVar = ir.NewNameAt(pos, typecheck.LookupNum(".rcvr", g.dnum))
   435  		if outer != nil {
   436  			rcvrVar.SetSym(outer.Sym().Pkg.Lookup(rcvrVar.Sym().Name))
   437  		}
   438  		g.dnum++
   439  		typed(rcvrValue.Type(), rcvrVar)
   440  		rcvrAssign = ir.NewAssignStmt(pos, rcvrVar, rcvrValue)
   441  		rcvrAssign.SetTypecheck(1)
   442  		rcvrVar.Defn = rcvrAssign
   443  		if outer == nil {
   444  			rcvrVar.Class = ir.PEXTERN
   445  			typecheck.Target.Decls = append(typecheck.Target.Decls, rcvrAssign)
   446  			typecheck.Target.Externs = append(typecheck.Target.Externs, rcvrVar)
   447  		} else {
   448  			rcvrVar.Class = ir.PAUTO
   449  			rcvrVar.Curfn = outer
   450  			outer.Dcl = append(outer.Dcl, rcvrVar)
   451  		}
   452  	}
   453  
   454  	// Build body of closure. This involves just calling the wrapped function directly
   455  	// with the additional dictionary argument.
   456  
   457  	// First, figure out the dictionary argument.
   458  	var dict2Var ir.Node
   459  	if usingSubdict {
   460  		// Capture sub-dictionary calculated in the outer function
   461  		dict2Var = ir.CaptureName(pos, fn, dictVar)
   462  		typed(types.Types[types.TUINTPTR], dict2Var)
   463  	} else {
   464  		// Static dictionary, so can be used directly in the closure
   465  		dict2Var = dictValue
   466  	}
   467  	// Also capture the receiver variable.
   468  	var rcvr2Var *ir.Name
   469  	if rcvrValue != nil {
   470  		rcvr2Var = ir.CaptureName(pos, fn, rcvrVar)
   471  	}
   472  
   473  	// Build arguments to call inside the closure.
   474  	var args []ir.Node
   475  
   476  	// First the dictionary argument.
   477  	args = append(args, dict2Var)
   478  	// Then the receiver.
   479  	if rcvrValue != nil {
   480  		args = append(args, rcvr2Var)
   481  	}
   482  	// Then all the other arguments (including receiver for method expressions).
   483  	for i := 0; i < typ.NumParams(); i++ {
   484  		if x.Op() == ir.OMETHEXPR && i == 0 {
   485  			// If we are doing a method expression, we need to
   486  			// explicitly traverse any embedded fields in the receiver
   487  			// argument in order to call the method instantiation.
   488  			arg0 := formalParams[0].Nname.(ir.Node)
   489  			arg0 = typecheck.AddImplicitDots(ir.NewSelectorExpr(x.Pos(), ir.OXDOT, arg0, x.(*ir.SelectorExpr).Sel)).X
   490  			if valueMethod && arg0.Type().IsPtr() {
   491  				// For handling the (*T).M case: if we have a pointer
   492  				// receiver after following all the embedded fields,
   493  				// but it's a value method, add a star operator.
   494  				arg0 = ir.NewStarExpr(arg0.Pos(), arg0)
   495  			}
   496  			args = append(args, arg0)
   497  		} else {
   498  			args = append(args, formalParams[i].Nname.(*ir.Name))
   499  		}
   500  	}
   501  
   502  	// Build call itself.
   503  	var innerCall ir.Node = ir.NewCallExpr(pos, ir.OCALL, target.Nname, args)
   504  	innerCall.(*ir.CallExpr).IsDDD = typ.IsVariadic()
   505  	if len(formalResults) > 0 {
   506  		innerCall = ir.NewReturnStmt(pos, []ir.Node{innerCall})
   507  	}
   508  	// Finish building body of closure.
   509  	ir.CurFunc = fn
   510  	// TODO: set types directly here instead of using typecheck.Stmt
   511  	typecheck.Stmt(innerCall)
   512  	ir.CurFunc = nil
   513  	fn.Body = []ir.Node{innerCall}
   514  
   515  	// We're all done with the captured dictionary (and receiver, for method values).
   516  	ir.FinishCaptureNames(pos, outer, fn)
   517  
   518  	// Make a closure referencing our new internal function.
   519  	c := ir.UseClosure(fn.OClosure, typecheck.Target)
   520  	var init []ir.Node
   521  	if outer != nil {
   522  		init = append(init, dictAssign)
   523  	}
   524  	if rcvrValue != nil {
   525  		init = append(init, rcvrAssign)
   526  	}
   527  	return ir.InitExpr(init, c)
   528  }
   529  
   530  // instantiateMethods instantiates all the methods (and associated dictionaries) of
   531  // all fully-instantiated generic types that have been added to typecheck.instTypeList.
   532  // It continues until no more types are added to typecheck.instTypeList.
   533  func (g *genInst) instantiateMethods() {
   534  	for {
   535  		instTypeList := typecheck.GetInstTypeList()
   536  		if len(instTypeList) == 0 {
   537  			break
   538  		}
   539  		typecheck.ClearInstTypeList()
   540  		for _, typ := range instTypeList {
   541  			assert(!typ.HasShape())
   542  			// Mark runtime type as needed, since this ensures that the
   543  			// compiler puts out the needed DWARF symbols, when this
   544  			// instantiated type has a different package from the local
   545  			// package.
   546  			typecheck.NeedRuntimeType(typ)
   547  			// Lookup the method on the base generic type, since methods may
   548  			// not be set on imported instantiated types.
   549  			baseType := typ.OrigType()
   550  			for j, _ := range typ.Methods().Slice() {
   551  				if baseType.Methods().Slice()[j].Nointerface() {
   552  					typ.Methods().Slice()[j].SetNointerface(true)
   553  				}
   554  				baseNname := baseType.Methods().Slice()[j].Nname.(*ir.Name)
   555  				// Eagerly generate the instantiations and dictionaries that implement these methods.
   556  				// We don't use the instantiations here, just generate them (and any
   557  				// further instantiations those generate, etc.).
   558  				// Note that we don't set the Func for any methods on instantiated
   559  				// types. Their signatures don't match so that would be confusing.
   560  				// Direct method calls go directly to the instantiations, implemented above.
   561  				// Indirect method calls use wrappers generated in reflectcall. Those wrappers
   562  				// will use these instantiations if they are needed (for interface tables or reflection).
   563  				_ = g.getInstantiation(baseNname, typ.RParams(), true)
   564  				_ = g.getDictionarySym(baseNname, typ.RParams(), true)
   565  			}
   566  		}
   567  	}
   568  }
   569  
   570  // getInstNameNode returns the name node for the method or function being instantiated, and a bool which is true if a method is being instantiated.
   571  func (g *genInst) getInstNameNode(inst *ir.InstExpr) (*ir.Name, bool) {
   572  	if meth, ok := inst.X.(*ir.SelectorExpr); ok {
   573  		return meth.Selection.Nname.(*ir.Name), true
   574  	} else {
   575  		return inst.X.(*ir.Name), false
   576  	}
   577  }
   578  
   579  // getDictOrSubdict returns, for a method/function call or reference (node n) in an
   580  // instantiation (described by instInfo), a node which is accessing a sub-dictionary
   581  // or main/static dictionary, as needed, and also returns a boolean indicating if a
   582  // sub-dictionary was accessed. nameNode is the particular function or method being
   583  // called/referenced, and targs are the type arguments.
   584  func (g *genInst) getDictOrSubdict(declInfo *instInfo, n ir.Node, nameNode *ir.Name, targs []*types.Type, isMeth bool) (ir.Node, bool) {
   585  	var dict ir.Node
   586  	usingSubdict := false
   587  	if declInfo != nil {
   588  		entry := -1
   589  		for i, de := range declInfo.dictInfo.subDictCalls {
   590  			if n == de.callNode {
   591  				entry = declInfo.dictInfo.startSubDict + i
   592  				break
   593  			}
   594  		}
   595  		// If the entry is not found, it may be that this node did not have
   596  		// any type args that depend on type params, so we need a main
   597  		// dictionary, not a sub-dictionary.
   598  		if entry >= 0 {
   599  			dict = getDictionaryEntry(n.Pos(), declInfo.dictParam, entry, declInfo.dictInfo.dictLen)
   600  			usingSubdict = true
   601  		}
   602  	}
   603  	if !usingSubdict {
   604  		dict = g.getDictionaryValue(n.Pos(), nameNode, targs, isMeth)
   605  	}
   606  	return dict, usingSubdict
   607  }
   608  
   609  // checkFetchBody checks if a generic body can be fetched, but hasn't been loaded
   610  // yet. If so, it imports the body.
   611  func checkFetchBody(nameNode *ir.Name) {
   612  	if nameNode.Func.Body == nil && nameNode.Func.Inl != nil {
   613  		// If there is no body yet but Func.Inl exists, then we can
   614  		// import the whole generic body.
   615  		assert(nameNode.Func.Inl.Cost == 1 && nameNode.Sym().Pkg != types.LocalPkg)
   616  		typecheck.ImportBody(nameNode.Func)
   617  		assert(nameNode.Func.Inl.Body != nil)
   618  		nameNode.Func.Body = nameNode.Func.Inl.Body
   619  		nameNode.Func.Dcl = nameNode.Func.Inl.Dcl
   620  	}
   621  }
   622  
   623  // getInstantiation gets the instantiantion and dictionary of the function or method nameNode
   624  // with the type arguments shapes. If the instantiated function is not already
   625  // cached, then it calls genericSubst to create the new instantiation.
   626  func (g *genInst) getInstantiation(nameNode *ir.Name, shapes []*types.Type, isMeth bool) *instInfo {
   627  	if nameNode.Func == nil {
   628  		// If nameNode.Func is nil, this must be a reference to a method of
   629  		// an imported instantiated type. We will have already called
   630  		// g.instantiateMethods() on the fully-instantiated type, so
   631  		// g.instInfoMap[sym] will be non-nil below.
   632  		rcvr := nameNode.Type().Recv()
   633  		if rcvr == nil || !deref(rcvr.Type).IsFullyInstantiated() {
   634  			base.FatalfAt(nameNode.Pos(), "Unexpected function instantiation %v with no body", nameNode)
   635  		}
   636  	} else {
   637  		checkFetchBody(nameNode)
   638  	}
   639  
   640  	var tparams []*types.Type
   641  	if isMeth {
   642  		// Get the type params from the method receiver (after skipping
   643  		// over any pointer)
   644  		recvType := nameNode.Type().Recv().Type
   645  		recvType = deref(recvType)
   646  		if recvType.IsFullyInstantiated() {
   647  			// Get the type of the base generic type, so we get
   648  			// its original typeparams.
   649  			recvType = recvType.OrigType()
   650  		}
   651  		tparams = recvType.RParams()
   652  	} else {
   653  		fields := nameNode.Type().TParams().Fields().Slice()
   654  		tparams = make([]*types.Type, len(fields))
   655  		for i, f := range fields {
   656  			tparams[i] = f.Type
   657  		}
   658  	}
   659  
   660  	// Convert any non-shape type arguments to their shape, so we can reduce the
   661  	// number of instantiations we have to generate. You can actually have a mix
   662  	// of shape and non-shape arguments, because of inferred or explicitly
   663  	// specified concrete type args.
   664  	s1 := make([]*types.Type, len(shapes))
   665  	for i, t := range shapes {
   666  		var tparam *types.Type
   667  		// Shapes are grouped differently for structural types, so we
   668  		// pass the type param to Shapify(), so we can distinguish.
   669  		tparam = tparams[i]
   670  		if !t.IsShape() {
   671  			s1[i] = typecheck.Shapify(t, i, tparam)
   672  		} else {
   673  			// Already a shape, but make sure it has the correct index.
   674  			s1[i] = typecheck.Shapify(shapes[i].Underlying(), i, tparam)
   675  		}
   676  	}
   677  	shapes = s1
   678  
   679  	sym := typecheck.MakeFuncInstSym(nameNode.Sym(), shapes, false, isMeth)
   680  	info := g.instInfoMap[sym]
   681  	if info == nil {
   682  		// If instantiation doesn't exist yet, create it and add
   683  		// to the list of decls.
   684  		info = &instInfo{
   685  			dictInfo: &dictInfo{},
   686  		}
   687  		info.dictInfo.shapeToBound = make(map[*types.Type]*types.Type)
   688  
   689  		if sym.Def != nil {
   690  			// This instantiation must have been imported from another
   691  			// package (because it was needed for inlining), so we should
   692  			// not re-generate it and have conflicting definitions for the
   693  			// symbol (issue #50121). It will have already gone through the
   694  			// dictionary transformations of dictPass, so we don't actually
   695  			// need the info.dictParam and info.shapeToBound info filled in
   696  			// below. We just set the imported instantiation as info.fun.
   697  			assert(sym.Pkg != types.LocalPkg)
   698  			info.fun = sym.Def.(*ir.Name).Func
   699  			assert(info.fun != nil)
   700  			g.instInfoMap[sym] = info
   701  			return info
   702  		}
   703  
   704  		// genericSubst fills in info.dictParam and info.shapeToBound.
   705  		st := g.genericSubst(sym, nameNode, tparams, shapes, isMeth, info)
   706  		info.fun = st
   707  		g.instInfoMap[sym] = info
   708  
   709  		// getInstInfo fills in info.dictInfo.
   710  		g.getInstInfo(st, shapes, info)
   711  		if base.Flag.W > 1 {
   712  			ir.Dump(fmt.Sprintf("\nstenciled %v", st), st)
   713  		}
   714  
   715  		// This ensures that the linker drops duplicates of this instantiation.
   716  		// All just works!
   717  		st.SetDupok(true)
   718  		typecheck.Target.Decls = append(typecheck.Target.Decls, st)
   719  		g.newInsts = append(g.newInsts, st)
   720  	}
   721  	return info
   722  }
   723  
   724  // Struct containing info needed for doing the substitution as we create the
   725  // instantiation of a generic function with specified type arguments.
   726  type subster struct {
   727  	g        *genInst
   728  	isMethod bool     // If a method is being instantiated
   729  	newf     *ir.Func // Func node for the new stenciled function
   730  	ts       typecheck.Tsubster
   731  	info     *instInfo // Place to put extra info in the instantiation
   732  
   733  	// Map from non-nil, non-ONAME node n to slice of all m, where m.Defn = n
   734  	defnMap map[ir.Node][]**ir.Name
   735  }
   736  
   737  // genericSubst returns a new function with name newsym. The function is an
   738  // instantiation of a generic function or method specified by namedNode with type
   739  // args shapes. For a method with a generic receiver, it returns an instantiated
   740  // function type where the receiver becomes the first parameter. For either a generic
   741  // method or function, a dictionary parameter is the added as the very first
   742  // parameter. genericSubst fills in info.dictParam and info.shapeToBound.
   743  func (g *genInst) genericSubst(newsym *types.Sym, nameNode *ir.Name, tparams []*types.Type, shapes []*types.Type, isMethod bool, info *instInfo) *ir.Func {
   744  	gf := nameNode.Func
   745  	// Pos of the instantiated function is same as the generic function
   746  	newf := ir.NewFunc(gf.Pos())
   747  	newf.Pragma = gf.Pragma // copy over pragmas from generic function to stenciled implementation.
   748  	newf.Nname = ir.NewNameAt(gf.Pos(), newsym)
   749  	newf.Nname.Func = newf
   750  	newf.Nname.Defn = newf
   751  	newsym.Def = newf.Nname
   752  	savef := ir.CurFunc
   753  	// transformCall/transformReturn (called during stenciling of the body)
   754  	// depend on ir.CurFunc being set.
   755  	ir.CurFunc = newf
   756  
   757  	assert(len(tparams) == len(shapes))
   758  
   759  	subst := &subster{
   760  		g:        g,
   761  		isMethod: isMethod,
   762  		newf:     newf,
   763  		info:     info,
   764  		ts: typecheck.Tsubster{
   765  			Tparams: tparams,
   766  			Targs:   shapes,
   767  			Vars:    make(map[*ir.Name]*ir.Name),
   768  		},
   769  		defnMap: make(map[ir.Node][]**ir.Name),
   770  	}
   771  
   772  	newf.Dcl = make([]*ir.Name, 0, len(gf.Dcl)+1)
   773  
   774  	// Create the needed dictionary param
   775  	dictionarySym := newsym.Pkg.Lookup(typecheck.LocalDictName)
   776  	dictionaryType := types.Types[types.TUINTPTR]
   777  	dictionaryName := ir.NewNameAt(gf.Pos(), dictionarySym)
   778  	typed(dictionaryType, dictionaryName)
   779  	dictionaryName.Class = ir.PPARAM
   780  	dictionaryName.Curfn = newf
   781  	newf.Dcl = append(newf.Dcl, dictionaryName)
   782  	for _, n := range gf.Dcl {
   783  		if n.Sym().Name == typecheck.LocalDictName {
   784  			panic("already has dictionary")
   785  		}
   786  		newf.Dcl = append(newf.Dcl, subst.localvar(n))
   787  	}
   788  	dictionaryArg := types.NewField(gf.Pos(), dictionarySym, dictionaryType)
   789  	dictionaryArg.Nname = dictionaryName
   790  	info.dictParam = dictionaryName
   791  
   792  	// We add the dictionary as the first parameter in the function signature.
   793  	// We also transform a method type to the corresponding function type
   794  	// (make the receiver be the next parameter after the dictionary).
   795  	oldt := nameNode.Type()
   796  	var args []*types.Field
   797  	args = append(args, dictionaryArg)
   798  	args = append(args, oldt.Recvs().FieldSlice()...)
   799  	args = append(args, oldt.Params().FieldSlice()...)
   800  
   801  	// Replace the types in the function signature via subst.fields.
   802  	// Ugly: also, we have to insert the Name nodes of the parameters/results into
   803  	// the function type. The current function type has no Nname fields set,
   804  	// because it came via conversion from the types2 type.
   805  	newt := types.NewSignature(oldt.Pkg(), nil, nil,
   806  		subst.fields(ir.PPARAM, args, newf.Dcl),
   807  		subst.fields(ir.PPARAMOUT, oldt.Results().FieldSlice(), newf.Dcl))
   808  
   809  	typed(newt, newf.Nname)
   810  	ir.MarkFunc(newf.Nname)
   811  	newf.SetTypecheck(1)
   812  
   813  	// Make sure name/type of newf is set before substituting the body.
   814  	newf.Body = subst.list(gf.Body)
   815  	if len(newf.Body) == 0 {
   816  		// Ensure the body is nonempty, for issue 49524.
   817  		// TODO: have some other way to detect the difference between
   818  		// a function declared with no body, vs. one with an empty body?
   819  		newf.Body = append(newf.Body, ir.NewBlockStmt(gf.Pos(), nil))
   820  	}
   821  
   822  	if len(subst.defnMap) > 0 {
   823  		base.Fatalf("defnMap is not empty")
   824  	}
   825  
   826  	for i, tp := range tparams {
   827  		info.dictInfo.shapeToBound[shapes[i]] = subst.ts.Typ(tp.Bound())
   828  	}
   829  
   830  	ir.CurFunc = savef
   831  
   832  	return subst.newf
   833  }
   834  
   835  // localvar creates a new name node for the specified local variable and enters it
   836  // in subst.vars. It substitutes type arguments for type parameters in the type of
   837  // name as needed.
   838  func (subst *subster) localvar(name *ir.Name) *ir.Name {
   839  	m := ir.NewNameAt(name.Pos(), name.Sym())
   840  	if name.IsClosureVar() {
   841  		m.SetIsClosureVar(true)
   842  	}
   843  	m.SetType(subst.ts.Typ(name.Type()))
   844  	m.BuiltinOp = name.BuiltinOp
   845  	m.Curfn = subst.newf
   846  	m.Class = name.Class
   847  	assert(name.Class != ir.PEXTERN && name.Class != ir.PFUNC)
   848  	m.Func = name.Func
   849  	subst.ts.Vars[name] = m
   850  	m.SetTypecheck(1)
   851  	m.DictIndex = name.DictIndex
   852  	if name.Defn != nil {
   853  		if name.Defn.Op() == ir.ONAME {
   854  			// This is a closure variable, so its Defn is the outer
   855  			// captured variable, which has already been substituted.
   856  			m.Defn = subst.node(name.Defn)
   857  		} else {
   858  			// The other values of Defn are nodes in the body of the
   859  			// function, so just remember the mapping so we can set Defn
   860  			// properly in node() when we create the new body node. We
   861  			// always call localvar() on all the local variables before
   862  			// we substitute the body.
   863  			slice := subst.defnMap[name.Defn]
   864  			subst.defnMap[name.Defn] = append(slice, &m)
   865  		}
   866  	}
   867  	if name.Outer != nil {
   868  		m.Outer = subst.node(name.Outer).(*ir.Name)
   869  	}
   870  
   871  	return m
   872  }
   873  
   874  // getDictionaryEntry gets the i'th entry in the dictionary dict.
   875  func getDictionaryEntry(pos src.XPos, dict *ir.Name, i int, size int) ir.Node {
   876  	// Convert dictionary to *[N]uintptr
   877  	// All entries in the dictionary are pointers. They all point to static data, though, so we
   878  	// treat them as uintptrs so the GC doesn't need to keep track of them.
   879  	d := ir.NewConvExpr(pos, ir.OCONVNOP, types.Types[types.TUNSAFEPTR], dict)
   880  	d.SetTypecheck(1)
   881  	d = ir.NewConvExpr(pos, ir.OCONVNOP, types.NewArray(types.Types[types.TUINTPTR], int64(size)).PtrTo(), d)
   882  	d.SetTypecheck(1)
   883  	types.CheckSize(d.Type().Elem())
   884  
   885  	// Load entry i out of the dictionary.
   886  	deref := ir.NewStarExpr(pos, d)
   887  	typed(d.Type().Elem(), deref)
   888  	idx := ir.NewConstExpr(constant.MakeUint64(uint64(i)), dict) // TODO: what to set orig to?
   889  	typed(types.Types[types.TUINTPTR], idx)
   890  	r := ir.NewIndexExpr(pos, deref, idx)
   891  	typed(types.Types[types.TUINTPTR], r)
   892  	return r
   893  }
   894  
   895  // getDictionaryType returns a *runtime._type from the dictionary entry i (which
   896  // refers to a type param or a derived type that uses type params). It uses the
   897  // specified dictionary dictParam, rather than the one in info.dictParam.
   898  func getDictionaryType(info *instInfo, dictParam *ir.Name, pos src.XPos, i int) ir.Node {
   899  	if i < 0 || i >= info.dictInfo.startSubDict {
   900  		base.Fatalf(fmt.Sprintf("bad dict index %d", i))
   901  	}
   902  
   903  	r := getDictionaryEntry(pos, dictParam, i, info.dictInfo.startSubDict)
   904  	// change type of retrieved dictionary entry to *byte, which is the
   905  	// standard typing of a *runtime._type in the compiler
   906  	typed(types.Types[types.TUINT8].PtrTo(), r)
   907  	return r
   908  }
   909  
   910  // node is like DeepCopy(), but substitutes ONAME nodes based on subst.ts.vars, and
   911  // also descends into closures. It substitutes type arguments for type parameters in
   912  // all the new nodes and does the transformations that were delayed on the generic
   913  // function.
   914  func (subst *subster) node(n ir.Node) ir.Node {
   915  	// Use closure to capture all state needed by the ir.EditChildren argument.
   916  	var edit func(ir.Node) ir.Node
   917  	edit = func(x ir.Node) ir.Node {
   918  		// Analogous to ir.SetPos() at beginning of typecheck.typecheck() -
   919  		// allows using base.Pos during the transform functions, just like
   920  		// the tc*() functions.
   921  		ir.SetPos(x)
   922  		switch x.Op() {
   923  		case ir.OTYPE:
   924  			return ir.TypeNode(subst.ts.Typ(x.Type()))
   925  
   926  		case ir.ONAME:
   927  			if v := subst.ts.Vars[x.(*ir.Name)]; v != nil {
   928  				return v
   929  			}
   930  			if ir.IsBlank(x) {
   931  				// Special case, because a blank local variable is
   932  				// not in the fn.Dcl list.
   933  				m := ir.NewNameAt(x.Pos(), ir.BlankNode.Sym())
   934  				return typed(subst.ts.Typ(x.Type()), m)
   935  			}
   936  			return x
   937  		case ir.ONONAME:
   938  			// This handles the identifier in a type switch guard
   939  			fallthrough
   940  		case ir.OLITERAL, ir.ONIL:
   941  			if x.Sym() != nil {
   942  				return x
   943  			}
   944  		}
   945  		m := ir.Copy(x)
   946  
   947  		slice, ok := subst.defnMap[x]
   948  		if ok {
   949  			// We just copied a non-ONAME node which was the Defn value
   950  			// of a local variable. Set the Defn value of the copied
   951  			// local variable to this new Defn node.
   952  			for _, ptr := range slice {
   953  				(*ptr).Defn = m
   954  			}
   955  			delete(subst.defnMap, x)
   956  		}
   957  
   958  		if _, isExpr := m.(ir.Expr); isExpr {
   959  			t := x.Type()
   960  			if t == nil {
   961  				// Check for known cases where t can be nil (call
   962  				// that has no return values, and key expressions)
   963  				// and otherwise cause a fatal error.
   964  				_, isCallExpr := m.(*ir.CallExpr)
   965  				_, isStructKeyExpr := m.(*ir.StructKeyExpr)
   966  				_, isKeyExpr := m.(*ir.KeyExpr)
   967  				if !isCallExpr && !isStructKeyExpr && !isKeyExpr && x.Op() != ir.OPANIC &&
   968  					x.Op() != ir.OCLOSE {
   969  					base.FatalfAt(m.Pos(), "Nil type for %v", x)
   970  				}
   971  			} else if x.Op() != ir.OCLOSURE {
   972  				m.SetType(subst.ts.Typ(x.Type()))
   973  			}
   974  		}
   975  
   976  		ir.EditChildren(m, edit)
   977  
   978  		m.SetTypecheck(1)
   979  
   980  		// Do the transformations that we delayed on the generic function
   981  		// node, now that we have substituted in the type args.
   982  		switch x.Op() {
   983  		case ir.OEQ, ir.ONE, ir.OLT, ir.OLE, ir.OGT, ir.OGE:
   984  			transformCompare(m.(*ir.BinaryExpr))
   985  
   986  		case ir.OSLICE, ir.OSLICE3:
   987  			transformSlice(m.(*ir.SliceExpr))
   988  
   989  		case ir.OADD:
   990  			m = transformAdd(m.(*ir.BinaryExpr))
   991  
   992  		case ir.OINDEX:
   993  			transformIndex(m.(*ir.IndexExpr))
   994  
   995  		case ir.OAS2:
   996  			as2 := m.(*ir.AssignListStmt)
   997  			transformAssign(as2, as2.Lhs, as2.Rhs)
   998  
   999  		case ir.OAS:
  1000  			as := m.(*ir.AssignStmt)
  1001  			if as.Y != nil {
  1002  				// transformAssign doesn't handle the case
  1003  				// of zeroing assignment of a dcl (rhs[0] is nil).
  1004  				lhs, rhs := []ir.Node{as.X}, []ir.Node{as.Y}
  1005  				transformAssign(as, lhs, rhs)
  1006  				as.X, as.Y = lhs[0], rhs[0]
  1007  			}
  1008  
  1009  		case ir.OASOP:
  1010  			as := m.(*ir.AssignOpStmt)
  1011  			transformCheckAssign(as, as.X)
  1012  
  1013  		case ir.ORETURN:
  1014  			transformReturn(m.(*ir.ReturnStmt))
  1015  
  1016  		case ir.OSEND:
  1017  			transformSend(m.(*ir.SendStmt))
  1018  
  1019  		case ir.OSELECT:
  1020  			transformSelect(m.(*ir.SelectStmt))
  1021  
  1022  		case ir.OCOMPLIT:
  1023  			transformCompLit(m.(*ir.CompLitExpr))
  1024  
  1025  		case ir.OADDR:
  1026  			transformAddr(m.(*ir.AddrExpr))
  1027  
  1028  		case ir.OLITERAL:
  1029  			t := m.Type()
  1030  			if t != x.Type() {
  1031  				// types2 will give us a constant with a type T,
  1032  				// if an untyped constant is used with another
  1033  				// operand of type T (in a provably correct way).
  1034  				// When we substitute in the type args during
  1035  				// stenciling, we now know the real type of the
  1036  				// constant. We may then need to change the
  1037  				// BasicLit.val to be the correct type (e.g.
  1038  				// convert an int64Val constant to a floatVal
  1039  				// constant).
  1040  				m.SetType(types.UntypedInt) // use any untyped type for DefaultLit to work
  1041  				m = typecheck.DefaultLit(m, t)
  1042  			}
  1043  
  1044  		case ir.OXDOT:
  1045  			// Finish the transformation of an OXDOT, unless this is
  1046  			// bound call or field access on a type param. A bound call
  1047  			// or field access on a type param will be transformed during
  1048  			// the dictPass. Otherwise, m will be transformed to an
  1049  			// OMETHVALUE node. It will be transformed to an ODOTMETH or
  1050  			// ODOTINTER node if we find in the OCALL case below that the
  1051  			// method value is actually called.
  1052  			mse := m.(*ir.SelectorExpr)
  1053  			if src := mse.X.Type(); !src.IsShape() {
  1054  				transformDot(mse, false)
  1055  			}
  1056  
  1057  		case ir.OCALL:
  1058  			call := m.(*ir.CallExpr)
  1059  			switch call.X.Op() {
  1060  			case ir.OTYPE:
  1061  				// Transform the conversion, now that we know the
  1062  				// type argument.
  1063  				m = transformConvCall(call)
  1064  
  1065  			case ir.OMETHVALUE, ir.OMETHEXPR:
  1066  				// Redo the transformation of OXDOT, now that we
  1067  				// know the method value is being called. Then
  1068  				// transform the call.
  1069  				call.X.(*ir.SelectorExpr).SetOp(ir.OXDOT)
  1070  				transformDot(call.X.(*ir.SelectorExpr), true)
  1071  				transformCall(call)
  1072  
  1073  			case ir.ODOT, ir.ODOTPTR:
  1074  				// An OXDOT for a generic receiver was resolved to
  1075  				// an access to a field which has a function
  1076  				// value. Transform the call to that function, now
  1077  				// that the OXDOT was resolved.
  1078  				transformCall(call)
  1079  
  1080  			case ir.ONAME:
  1081  				name := call.X.Name()
  1082  				if name.BuiltinOp != ir.OXXX {
  1083  					m = transformBuiltin(call)
  1084  				} else {
  1085  					// This is the case of a function value that was a
  1086  					// type parameter (implied to be a function via a
  1087  					// structural constraint) which is now resolved.
  1088  					transformCall(call)
  1089  				}
  1090  
  1091  			case ir.OFUNCINST:
  1092  				// A call with an OFUNCINST will get transformed
  1093  				// in stencil() once we have created & attached the
  1094  				// instantiation to be called.
  1095  				// We must transform the arguments of the call now, though,
  1096  				// so that any needed CONVIFACE nodes are exposed,
  1097  				// so the dictionary format is correct.
  1098  				transformEarlyCall(call)
  1099  
  1100  			case ir.OXDOT:
  1101  				// This is the case of a bound call or a field access
  1102  				// on a typeparam, which will be handled in the
  1103  				// dictPass. As with OFUNCINST, we must transform the
  1104  				// arguments of the call now, so any needed CONVIFACE
  1105  				// nodes are exposed.
  1106  				transformEarlyCall(call)
  1107  
  1108  			case ir.ODOTTYPE, ir.ODOTTYPE2:
  1109  				// These are DOTTYPEs that could get transformed into
  1110  				// ODYNAMIC DOTTYPEs by the dict pass.
  1111  
  1112  			default:
  1113  				// Transform a call for all other values of
  1114  				// call.X.Op() that don't require any special
  1115  				// handling.
  1116  				transformCall(call)
  1117  
  1118  			}
  1119  
  1120  		case ir.OCLOSURE:
  1121  			// We're going to create a new closure from scratch, so clear m
  1122  			// to avoid using the ir.Copy by accident until we reassign it.
  1123  			m = nil
  1124  
  1125  			x := x.(*ir.ClosureExpr)
  1126  			// Need to duplicate x.Func.Nname, x.Func.Dcl, x.Func.ClosureVars, and
  1127  			// x.Func.Body.
  1128  			oldfn := x.Func
  1129  			newfn := ir.NewClosureFunc(oldfn.Pos(), subst.newf != nil)
  1130  			ir.NameClosure(newfn.OClosure, subst.newf)
  1131  
  1132  			saveNewf := subst.newf
  1133  			ir.CurFunc = newfn
  1134  			subst.newf = newfn
  1135  			newfn.Dcl = subst.namelist(oldfn.Dcl)
  1136  
  1137  			// Make a closure variable for the dictionary of the
  1138  			// containing function.
  1139  			cdict := ir.CaptureName(oldfn.Pos(), newfn, subst.info.dictParam)
  1140  			typed(types.Types[types.TUINTPTR], cdict)
  1141  			ir.FinishCaptureNames(oldfn.Pos(), saveNewf, newfn)
  1142  			newfn.ClosureVars = append(newfn.ClosureVars, subst.namelist(oldfn.ClosureVars)...)
  1143  
  1144  			// Copy that closure variable to a local one.
  1145  			// Note: this allows the dictionary to be captured by child closures.
  1146  			// See issue 47723.
  1147  			ldict := ir.NewNameAt(x.Pos(), newfn.Sym().Pkg.Lookup(typecheck.LocalDictName))
  1148  			typed(types.Types[types.TUINTPTR], ldict)
  1149  			ldict.Class = ir.PAUTO
  1150  			ldict.Curfn = newfn
  1151  			newfn.Dcl = append(newfn.Dcl, ldict)
  1152  			as := ir.NewAssignStmt(x.Pos(), ldict, cdict)
  1153  			as.SetTypecheck(1)
  1154  			ldict.Defn = as
  1155  			newfn.Body.Append(as)
  1156  
  1157  			// Create inst info for the instantiated closure. The dict
  1158  			// param is the closure variable for the dictionary of the
  1159  			// outer function. Since the dictionary is shared, use the
  1160  			// same dictInfo.
  1161  			cinfo := &instInfo{
  1162  				fun:       newfn,
  1163  				dictParam: ldict,
  1164  				dictInfo:  subst.info.dictInfo,
  1165  			}
  1166  			subst.g.instInfoMap[newfn.Nname.Sym()] = cinfo
  1167  
  1168  			typed(subst.ts.Typ(oldfn.Nname.Type()), newfn.Nname)
  1169  			typed(newfn.Nname.Type(), newfn.OClosure)
  1170  			newfn.SetTypecheck(1)
  1171  
  1172  			outerinfo := subst.info
  1173  			subst.info = cinfo
  1174  			// Make sure type of closure function is set before doing body.
  1175  			newfn.Body.Append(subst.list(oldfn.Body)...)
  1176  			subst.info = outerinfo
  1177  			subst.newf = saveNewf
  1178  			ir.CurFunc = saveNewf
  1179  
  1180  			m = ir.UseClosure(newfn.OClosure, typecheck.Target)
  1181  			subst.g.newInsts = append(subst.g.newInsts, m.(*ir.ClosureExpr).Func)
  1182  			m.(*ir.ClosureExpr).SetInit(subst.list(x.Init()))
  1183  
  1184  		case ir.OSWITCH:
  1185  			m := m.(*ir.SwitchStmt)
  1186  			if m.Tag != nil && m.Tag.Op() == ir.OTYPESW {
  1187  				break // Nothing to do here for type switches.
  1188  			}
  1189  			if m.Tag != nil && !m.Tag.Type().IsInterface() && m.Tag.Type().HasShape() {
  1190  				// To implement a switch on a value that is or has a type parameter, we first convert
  1191  				// that thing we're switching on to an interface{}.
  1192  				m.Tag = assignconvfn(m.Tag, types.Types[types.TINTER])
  1193  			}
  1194  			for _, c := range m.Cases {
  1195  				for i, x := range c.List {
  1196  					// If we have a case that is or has a type parameter, convert that case
  1197  					// to an interface{}.
  1198  					if !x.Type().IsInterface() && x.Type().HasShape() {
  1199  						c.List[i] = assignconvfn(x, types.Types[types.TINTER])
  1200  					}
  1201  				}
  1202  			}
  1203  
  1204  		}
  1205  		return m
  1206  	}
  1207  
  1208  	return edit(n)
  1209  }
  1210  
  1211  // dictPass takes a function instantiation and does the transformations on the
  1212  // operations that need to make use of the dictionary param.
  1213  func (g *genInst) dictPass(info *instInfo) {
  1214  	savef := ir.CurFunc
  1215  	ir.CurFunc = info.fun
  1216  
  1217  	var edit func(ir.Node) ir.Node
  1218  	edit = func(m ir.Node) ir.Node {
  1219  		ir.EditChildren(m, edit)
  1220  
  1221  		switch m.Op() {
  1222  		case ir.OCLOSURE:
  1223  			newf := m.(*ir.ClosureExpr).Func
  1224  			ir.CurFunc = newf
  1225  			outerinfo := info
  1226  			info = g.instInfoMap[newf.Nname.Sym()]
  1227  
  1228  			body := newf.Body
  1229  			for i, n := range body {
  1230  				body[i] = edit(n)
  1231  			}
  1232  
  1233  			info = outerinfo
  1234  			ir.CurFunc = info.fun
  1235  
  1236  		case ir.OXDOT:
  1237  			// This is the case of a dot access on a type param. This is
  1238  			// typically a bound call on the type param, but could be a
  1239  			// field access, if the constraint has a single structural type.
  1240  			mse := m.(*ir.SelectorExpr)
  1241  			src := mse.X.Type()
  1242  			assert(src.IsShape())
  1243  
  1244  			if mse.X.Op() == ir.OTYPE {
  1245  				// Method expression T.M
  1246  				m = g.buildClosure2(info, m)
  1247  				// No need for transformDot - buildClosure2 has already
  1248  				// transformed to OCALLINTER/ODOTINTER.
  1249  			} else {
  1250  				// If we can't find the selected method in the
  1251  				// AllMethods of the bound, then this must be an access
  1252  				// to a field of a structural type. If so, we skip the
  1253  				// dictionary lookups - transformDot() will convert to
  1254  				// the desired direct field access.
  1255  				if isBoundMethod(info.dictInfo, mse) {
  1256  					dst := info.dictInfo.shapeToBound[mse.X.Type()]
  1257  					// Implement x.M as a conversion-to-bound-interface
  1258  					//  1) convert x to the bound interface
  1259  					//  2) call M on that interface
  1260  					if src.IsInterface() {
  1261  						// If type arg is an interface (unusual case),
  1262  						// we do a type assert to the type bound.
  1263  						mse.X = assertToBound(info, info.dictParam, m.Pos(), mse.X, dst)
  1264  					} else {
  1265  						mse.X = convertUsingDictionary(info, info.dictParam, m.Pos(), mse.X, m, dst, true)
  1266  						// Note: we set nonEscaping==true, because we can assume the backing store for the
  1267  						// interface conversion doesn't escape. The method call will immediately go to
  1268  						// a wrapper function which copies all the data out of the interface value.
  1269  						// (It only matters for non-pointer-shaped interface conversions. See issue 50182.)
  1270  					}
  1271  				}
  1272  				transformDot(mse, false)
  1273  			}
  1274  		case ir.OCALL:
  1275  			call := m.(*ir.CallExpr)
  1276  			op := call.X.Op()
  1277  			if op == ir.OMETHVALUE {
  1278  				// Redo the transformation of OXDOT, now that we
  1279  				// know the method value is being called.
  1280  				call.X.(*ir.SelectorExpr).SetOp(ir.OXDOT)
  1281  				transformDot(call.X.(*ir.SelectorExpr), true)
  1282  			}
  1283  			transformCall(call)
  1284  
  1285  		case ir.OCONVIFACE:
  1286  			if m.Type().IsEmptyInterface() && m.(*ir.ConvExpr).X.Type().IsEmptyInterface() {
  1287  				// Was T->interface{}, after stenciling it is now interface{}->interface{}.
  1288  				// No longer need the conversion. See issue 48276.
  1289  				m.(*ir.ConvExpr).SetOp(ir.OCONVNOP)
  1290  				break
  1291  			}
  1292  			mce := m.(*ir.ConvExpr)
  1293  			// Note: x's argument is still typed as a type parameter.
  1294  			// m's argument now has an instantiated type.
  1295  
  1296  			if mce.X.Type().HasShape() || m.Type().HasShape() {
  1297  				m = convertUsingDictionary(info, info.dictParam, m.Pos(), mce.X, m, m.Type(), false)
  1298  			}
  1299  		case ir.ODOTTYPE, ir.ODOTTYPE2:
  1300  			if !m.Type().HasShape() {
  1301  				break
  1302  			}
  1303  			dt := m.(*ir.TypeAssertExpr)
  1304  			var rt ir.Node
  1305  			if dt.Type().IsInterface() || dt.X.Type().IsEmptyInterface() {
  1306  				ix := findDictType(info, m.Type())
  1307  				assert(ix >= 0)
  1308  				rt = getDictionaryType(info, info.dictParam, dt.Pos(), ix)
  1309  			} else {
  1310  				// nonempty interface to noninterface. Need an itab.
  1311  				ix := -1
  1312  				for i, ic := range info.dictInfo.itabConvs {
  1313  					if ic == m {
  1314  						ix = info.dictInfo.startItabConv + i
  1315  						break
  1316  					}
  1317  				}
  1318  				assert(ix >= 0)
  1319  				rt = getDictionaryEntry(dt.Pos(), info.dictParam, ix, info.dictInfo.dictLen)
  1320  			}
  1321  			op := ir.ODYNAMICDOTTYPE
  1322  			if m.Op() == ir.ODOTTYPE2 {
  1323  				op = ir.ODYNAMICDOTTYPE2
  1324  			}
  1325  			m = ir.NewDynamicTypeAssertExpr(dt.Pos(), op, dt.X, rt)
  1326  			m.SetType(dt.Type())
  1327  			m.SetTypecheck(1)
  1328  		case ir.OCASE:
  1329  			if _, ok := m.(*ir.CommClause); ok {
  1330  				// This is not a type switch. TODO: Should we use an OSWITCH case here instead of OCASE?
  1331  				break
  1332  			}
  1333  			m := m.(*ir.CaseClause)
  1334  			for i, c := range m.List {
  1335  				if c.Op() == ir.OTYPE && c.Type().HasShape() {
  1336  					// Use a *runtime._type for the dynamic type.
  1337  					ix := findDictType(info, m.List[i].Type())
  1338  					assert(ix >= 0)
  1339  					dt := ir.NewDynamicType(c.Pos(), getDictionaryEntry(c.Pos(), info.dictParam, ix, info.dictInfo.dictLen))
  1340  
  1341  					// For type switch from nonempty interfaces to non-interfaces, we need an itab as well.
  1342  					if !m.List[i].Type().IsInterface() {
  1343  						if _, ok := info.dictInfo.type2switchType[m.List[i]]; ok {
  1344  							// Type switch from nonempty interface. We need a *runtime.itab
  1345  							// for the dynamic type.
  1346  							ix := -1
  1347  							for j, ic := range info.dictInfo.itabConvs {
  1348  								if ic == m.List[i] {
  1349  									ix = info.dictInfo.startItabConv + j
  1350  									break
  1351  								}
  1352  							}
  1353  							assert(ix >= 0)
  1354  							dt.ITab = getDictionaryEntry(c.Pos(), info.dictParam, ix, info.dictInfo.dictLen)
  1355  						}
  1356  					}
  1357  					typed(m.List[i].Type(), dt)
  1358  					m.List[i] = dt
  1359  				}
  1360  			}
  1361  
  1362  		}
  1363  		return m
  1364  	}
  1365  	edit(info.fun)
  1366  	ir.CurFunc = savef
  1367  }
  1368  
  1369  // findDictType looks for type t in the typeparams or derived types in the generic
  1370  // function info.gfInfo. This will indicate the dictionary entry with the
  1371  // correct concrete type for the associated instantiated function.
  1372  func findDictType(info *instInfo, t *types.Type) int {
  1373  	for i, dt := range info.dictInfo.shapeParams {
  1374  		if dt == t {
  1375  			return i
  1376  		}
  1377  	}
  1378  	for i, dt := range info.dictInfo.derivedTypes {
  1379  		if types.IdenticalStrict(dt, t) {
  1380  			return i + len(info.dictInfo.shapeParams)
  1381  		}
  1382  	}
  1383  	return -1
  1384  }
  1385  
  1386  // convertUsingDictionary converts instantiated value v (type v.Type()) to an interface
  1387  // type dst, by returning a new set of nodes that make use of a dictionary entry. in is the
  1388  // instantiated node of the CONVIFACE node or XDOT node (for a bound method call) that is causing the
  1389  // conversion.
  1390  // If nonEscaping is true, the caller guarantees that the backing store needed for the interface data
  1391  // word will not escape.
  1392  func convertUsingDictionary(info *instInfo, dictParam *ir.Name, pos src.XPos, v ir.Node, in ir.Node, dst *types.Type, nonEscaping bool) ir.Node {
  1393  	assert(v.Type().HasShape() || in.Type().HasShape())
  1394  	assert(dst.IsInterface())
  1395  
  1396  	if v.Type().IsInterface() {
  1397  		// Converting from an interface. The shape-ness of the source doesn't really matter, as
  1398  		// we'll be using the concrete type from the first interface word.
  1399  		if dst.IsEmptyInterface() {
  1400  			// Converting I2E. OCONVIFACE does that for us, and doesn't depend
  1401  			// on what the empty interface was instantiated with. No dictionary entry needed.
  1402  			v = ir.NewConvExpr(pos, ir.OCONVIFACE, dst, v)
  1403  			v.SetTypecheck(1)
  1404  			return v
  1405  		}
  1406  		if !in.Type().HasShape() {
  1407  			// Regular OCONVIFACE works if the destination isn't parameterized.
  1408  			v = ir.NewConvExpr(pos, ir.OCONVIFACE, dst, v)
  1409  			v.SetTypecheck(1)
  1410  			return v
  1411  		}
  1412  
  1413  		// We get the destination interface type from the dictionary and the concrete
  1414  		// type from the argument's itab. Call runtime.convI2I to get the new itab.
  1415  		tmp := typecheck.Temp(v.Type())
  1416  		as := ir.NewAssignStmt(pos, tmp, v)
  1417  		as.SetTypecheck(1)
  1418  		itab := ir.NewUnaryExpr(pos, ir.OITAB, tmp)
  1419  		typed(types.Types[types.TUINTPTR].PtrTo(), itab)
  1420  		idata := ir.NewUnaryExpr(pos, ir.OIDATA, tmp)
  1421  		typed(types.Types[types.TUNSAFEPTR], idata)
  1422  
  1423  		fn := typecheck.LookupRuntime("convI2I")
  1424  		fn.SetTypecheck(1)
  1425  		types.CalcSize(fn.Type())
  1426  		call := ir.NewCallExpr(pos, ir.OCALLFUNC, fn, nil)
  1427  		typed(types.Types[types.TUINT8].PtrTo(), call)
  1428  		ix := findDictType(info, in.Type())
  1429  		assert(ix >= 0)
  1430  		inter := getDictionaryType(info, dictParam, pos, ix)
  1431  		call.Args = []ir.Node{inter, itab}
  1432  		i := ir.NewBinaryExpr(pos, ir.OEFACE, call, idata)
  1433  		typed(dst, i)
  1434  		i.PtrInit().Append(as)
  1435  		return i
  1436  	}
  1437  
  1438  	var rt ir.Node
  1439  	if !dst.IsEmptyInterface() {
  1440  		// We should have an itab entry in the dictionary. Using this itab
  1441  		// will be more efficient than converting to an empty interface first
  1442  		// and then type asserting to dst.
  1443  		ix := -1
  1444  		for i, ic := range info.dictInfo.itabConvs {
  1445  			if ic == in {
  1446  				ix = info.dictInfo.startItabConv + i
  1447  				break
  1448  			}
  1449  		}
  1450  		assert(ix >= 0)
  1451  		rt = getDictionaryEntry(pos, dictParam, ix, info.dictInfo.dictLen)
  1452  	} else {
  1453  		ix := findDictType(info, v.Type())
  1454  		assert(ix >= 0)
  1455  		// Load the actual runtime._type of the type parameter from the dictionary.
  1456  		rt = getDictionaryType(info, dictParam, pos, ix)
  1457  	}
  1458  
  1459  	// Figure out what the data field of the interface will be.
  1460  	data := ir.NewConvExpr(pos, ir.OCONVIDATA, nil, v)
  1461  	typed(types.Types[types.TUNSAFEPTR], data)
  1462  	data.NonEscaping = nonEscaping
  1463  
  1464  	// Build an interface from the type and data parts.
  1465  	var i ir.Node = ir.NewBinaryExpr(pos, ir.OEFACE, rt, data)
  1466  	typed(dst, i)
  1467  	return i
  1468  }
  1469  
  1470  func (subst *subster) namelist(l []*ir.Name) []*ir.Name {
  1471  	s := make([]*ir.Name, len(l))
  1472  	for i, n := range l {
  1473  		s[i] = subst.localvar(n)
  1474  	}
  1475  	return s
  1476  }
  1477  
  1478  func (subst *subster) list(l []ir.Node) []ir.Node {
  1479  	s := make([]ir.Node, len(l))
  1480  	for i, n := range l {
  1481  		s[i] = subst.node(n)
  1482  	}
  1483  	return s
  1484  }
  1485  
  1486  // fields sets the Nname field for the Field nodes inside a type signature, based
  1487  // on the corresponding in/out parameters in dcl. It depends on the in and out
  1488  // parameters being in order in dcl.
  1489  func (subst *subster) fields(class ir.Class, oldfields []*types.Field, dcl []*ir.Name) []*types.Field {
  1490  	// Find the starting index in dcl of declarations of the class (either
  1491  	// PPARAM or PPARAMOUT).
  1492  	var i int
  1493  	for i = range dcl {
  1494  		if dcl[i].Class == class {
  1495  			break
  1496  		}
  1497  	}
  1498  
  1499  	// Create newfields nodes that are copies of the oldfields nodes, but
  1500  	// with substitution for any type params, and with Nname set to be the node in
  1501  	// Dcl for the corresponding PPARAM or PPARAMOUT.
  1502  	newfields := make([]*types.Field, len(oldfields))
  1503  	for j := range oldfields {
  1504  		newfields[j] = oldfields[j].Copy()
  1505  		newfields[j].Type = subst.ts.Typ(oldfields[j].Type)
  1506  		// A PPARAM field will be missing from dcl if its name is
  1507  		// unspecified or specified as "_". So, we compare the dcl sym
  1508  		// with the field sym (or sym of the field's Nname node). (Unnamed
  1509  		// results still have a name like ~r2 in their Nname node.) If
  1510  		// they don't match, this dcl (if there is one left) must apply to
  1511  		// a later field.
  1512  		if i < len(dcl) && (dcl[i].Sym() == oldfields[j].Sym ||
  1513  			(oldfields[j].Nname != nil && dcl[i].Sym() == oldfields[j].Nname.Sym())) {
  1514  			newfields[j].Nname = dcl[i]
  1515  			i++
  1516  		}
  1517  	}
  1518  	return newfields
  1519  }
  1520  
  1521  // deref does a single deref of type t, if it is a pointer type.
  1522  func deref(t *types.Type) *types.Type {
  1523  	if t.IsPtr() {
  1524  		return t.Elem()
  1525  	}
  1526  	return t
  1527  }
  1528  
  1529  // markTypeUsed marks type t as used in order to help avoid dead-code elimination of
  1530  // needed methods.
  1531  func markTypeUsed(t *types.Type, lsym *obj.LSym) {
  1532  	if t.IsInterface() {
  1533  		return
  1534  	}
  1535  	// TODO: This is somewhat overkill, we really only need it
  1536  	// for types that are put into interfaces.
  1537  	// Note: this relocation is also used in cmd/link/internal/ld/dwarf.go
  1538  	reflectdata.MarkTypeUsedInInterface(t, lsym)
  1539  }
  1540  
  1541  // getDictionarySym returns the dictionary for the named generic function gf, which
  1542  // is instantiated with the type arguments targs.
  1543  func (g *genInst) getDictionarySym(gf *ir.Name, targs []*types.Type, isMeth bool) *types.Sym {
  1544  	if len(targs) == 0 {
  1545  		base.Fatalf("%s should have type arguments", gf.Sym().Name)
  1546  	}
  1547  
  1548  	// Enforce that only concrete types can make it to here.
  1549  	for _, t := range targs {
  1550  		if t.HasShape() {
  1551  			panic(fmt.Sprintf("shape %+v in dictionary for %s", t, gf.Sym().Name))
  1552  		}
  1553  	}
  1554  
  1555  	// Get a symbol representing the dictionary.
  1556  	sym := typecheck.MakeDictSym(gf.Sym(), targs, isMeth)
  1557  
  1558  	// Initialize the dictionary, if we haven't yet already.
  1559  	lsym := sym.Linksym()
  1560  	if len(lsym.P) > 0 {
  1561  		// We already started creating this dictionary and its lsym.
  1562  		return sym
  1563  	}
  1564  
  1565  	infoPrint("=== Creating dictionary %v\n", sym.Name)
  1566  	off := 0
  1567  	// Emit an entry for each targ (concrete type or gcshape).
  1568  	for _, t := range targs {
  1569  		infoPrint(" * %v\n", t)
  1570  		s := reflectdata.TypeLinksym(t)
  1571  		off = objw.SymPtr(lsym, off, s, 0)
  1572  		markTypeUsed(t, lsym)
  1573  	}
  1574  
  1575  	instInfo := g.getInstantiation(gf, targs, isMeth)
  1576  	info := instInfo.dictInfo
  1577  
  1578  	subst := typecheck.Tsubster{
  1579  		Tparams: info.shapeParams,
  1580  		Targs:   targs,
  1581  	}
  1582  	// Emit an entry for each derived type (after substituting targs)
  1583  	for _, t := range info.derivedTypes {
  1584  		ts := subst.Typ(t)
  1585  		infoPrint(" - %v\n", ts)
  1586  		s := reflectdata.TypeLinksym(ts)
  1587  		off = objw.SymPtr(lsym, off, s, 0)
  1588  		markTypeUsed(ts, lsym)
  1589  	}
  1590  	// Emit an entry for each subdictionary (after substituting targs)
  1591  	for _, subDictInfo := range info.subDictCalls {
  1592  		var sym *types.Sym
  1593  		n := subDictInfo.callNode
  1594  		switch n.Op() {
  1595  		case ir.OCALL, ir.OCALLFUNC, ir.OCALLMETH:
  1596  			call := n.(*ir.CallExpr)
  1597  			if call.X.Op() == ir.OXDOT || call.X.Op() == ir.ODOTMETH {
  1598  				var nameNode *ir.Name
  1599  				se := call.X.(*ir.SelectorExpr)
  1600  				if se.X.Type().IsShape() {
  1601  					// This is a method call enabled by a type bound.
  1602  
  1603  					// We need this extra check for method expressions,
  1604  					// which don't add in the implicit XDOTs.
  1605  					tmpse := ir.NewSelectorExpr(src.NoXPos, ir.OXDOT, se.X, se.Sel)
  1606  					tmpse = typecheck.AddImplicitDots(tmpse)
  1607  					tparam := tmpse.X.Type()
  1608  					if !tparam.IsShape() {
  1609  						// The method expression is not
  1610  						// really on a typeparam.
  1611  						break
  1612  					}
  1613  					ix := -1
  1614  					for i, shape := range info.shapeParams {
  1615  						if shape == tparam {
  1616  							ix = i
  1617  							break
  1618  						}
  1619  					}
  1620  					assert(ix >= 0)
  1621  					recvType := targs[ix]
  1622  					if recvType.IsInterface() || len(recvType.RParams()) == 0 {
  1623  						// No sub-dictionary entry is
  1624  						// actually needed, since the
  1625  						// type arg is not an
  1626  						// instantiated type that
  1627  						// will have generic methods.
  1628  						break
  1629  					}
  1630  					// This is a method call for an
  1631  					// instantiated type, so we need a
  1632  					// sub-dictionary.
  1633  					targs := recvType.RParams()
  1634  					genRecvType := recvType.OrigType()
  1635  					nameNode = typecheck.Lookdot1(call.X, se.Sel, genRecvType, genRecvType.Methods(), 1).Nname.(*ir.Name)
  1636  					sym = g.getDictionarySym(nameNode, targs, true)
  1637  				} else {
  1638  					// This is the case of a normal
  1639  					// method call on a generic type.
  1640  					assert(subDictInfo.savedXNode == se)
  1641  					sym = g.getSymForMethodCall(se, &subst)
  1642  				}
  1643  			} else {
  1644  				inst, ok := call.X.(*ir.InstExpr)
  1645  				if ok {
  1646  					// Code hasn't been transformed yet
  1647  					assert(subDictInfo.savedXNode == inst)
  1648  				}
  1649  				// If !ok, then the generic method/function call has
  1650  				// already been transformed to a shape instantiation
  1651  				// call. Either way, use the SelectorExpr/InstExpr
  1652  				// node saved in info.
  1653  				cex := subDictInfo.savedXNode
  1654  				if se, ok := cex.(*ir.SelectorExpr); ok {
  1655  					sym = g.getSymForMethodCall(se, &subst)
  1656  				} else {
  1657  					inst := cex.(*ir.InstExpr)
  1658  					nameNode := inst.X.(*ir.Name)
  1659  					subtargs := typecheck.TypesOf(inst.Targs)
  1660  					for i, t := range subtargs {
  1661  						subtargs[i] = subst.Typ(t)
  1662  					}
  1663  					sym = g.getDictionarySym(nameNode, subtargs, false)
  1664  				}
  1665  			}
  1666  
  1667  		case ir.OFUNCINST:
  1668  			inst := n.(*ir.InstExpr)
  1669  			nameNode := inst.X.(*ir.Name)
  1670  			subtargs := typecheck.TypesOf(inst.Targs)
  1671  			for i, t := range subtargs {
  1672  				subtargs[i] = subst.Typ(t)
  1673  			}
  1674  			sym = g.getDictionarySym(nameNode, subtargs, false)
  1675  
  1676  		case ir.OXDOT, ir.OMETHEXPR, ir.OMETHVALUE:
  1677  			sym = g.getSymForMethodCall(n.(*ir.SelectorExpr), &subst)
  1678  
  1679  		default:
  1680  			assert(false)
  1681  		}
  1682  
  1683  		if sym == nil {
  1684  			// Unused sub-dictionary entry, just emit 0.
  1685  			off = objw.Uintptr(lsym, off, 0)
  1686  			infoPrint(" - Unused subdict entry\n")
  1687  		} else {
  1688  			off = objw.SymPtr(lsym, off, sym.Linksym(), 0)
  1689  			infoPrint(" - Subdict %v\n", sym.Name)
  1690  		}
  1691  	}
  1692  
  1693  	g.instantiateMethods()
  1694  	delay := &delayInfo{
  1695  		gf:     gf,
  1696  		targs:  targs,
  1697  		sym:    sym,
  1698  		off:    off,
  1699  		isMeth: isMeth,
  1700  	}
  1701  	g.dictSymsToFinalize = append(g.dictSymsToFinalize, delay)
  1702  	return sym
  1703  }
  1704  
  1705  // getSymForMethodCall gets the dictionary sym for a method call, method value, or method
  1706  // expression that has selector se. subst gives the substitution from shape types to
  1707  // concrete types.
  1708  func (g *genInst) getSymForMethodCall(se *ir.SelectorExpr, subst *typecheck.Tsubster) *types.Sym {
  1709  	// For everything except method expressions, 'recvType = deref(se.X.Type)' would
  1710  	// also give the receiver type. For method expressions with embedded types, we
  1711  	// need to look at the type of the selection to get the final receiver type.
  1712  	recvType := deref(se.Selection.Type.Recv().Type)
  1713  	genRecvType := recvType.OrigType()
  1714  	nameNode := typecheck.Lookdot1(se, se.Sel, genRecvType, genRecvType.Methods(), 1).Nname.(*ir.Name)
  1715  	subtargs := recvType.RParams()
  1716  	s2targs := make([]*types.Type, len(subtargs))
  1717  	for i, t := range subtargs {
  1718  		s2targs[i] = subst.Typ(t)
  1719  	}
  1720  	return g.getDictionarySym(nameNode, s2targs, true)
  1721  }
  1722  
  1723  // finalizeSyms finishes up all dictionaries on g.dictSymsToFinalize, by writing out
  1724  // any needed LSyms for itabs. The itab lsyms create wrappers which need various
  1725  // dictionaries and method instantiations to be complete, so, to avoid recursive
  1726  // dependencies, we finalize the itab lsyms only after all dictionaries syms and
  1727  // instantiations have been created.
  1728  func (g *genInst) finalizeSyms() {
  1729  	for _, d := range g.dictSymsToFinalize {
  1730  		infoPrint("=== Finalizing dictionary %s\n", d.sym.Name)
  1731  
  1732  		lsym := d.sym.Linksym()
  1733  		instInfo := g.getInstantiation(d.gf, d.targs, d.isMeth)
  1734  		info := instInfo.dictInfo
  1735  
  1736  		subst := typecheck.Tsubster{
  1737  			Tparams: info.shapeParams,
  1738  			Targs:   d.targs,
  1739  		}
  1740  
  1741  		// Emit an entry for each itab
  1742  		for _, n := range info.itabConvs {
  1743  			var srctype, dsttype *types.Type
  1744  			switch n.Op() {
  1745  			case ir.OXDOT, ir.OMETHVALUE:
  1746  				se := n.(*ir.SelectorExpr)
  1747  				srctype = subst.Typ(se.X.Type())
  1748  				dsttype = subst.Typ(info.shapeToBound[se.X.Type()])
  1749  			case ir.ODOTTYPE, ir.ODOTTYPE2:
  1750  				srctype = subst.Typ(n.(*ir.TypeAssertExpr).Type())
  1751  				dsttype = subst.Typ(n.(*ir.TypeAssertExpr).X.Type())
  1752  			case ir.OCONVIFACE:
  1753  				srctype = subst.Typ(n.(*ir.ConvExpr).X.Type())
  1754  				dsttype = subst.Typ(n.Type())
  1755  			case ir.OTYPE:
  1756  				srctype = subst.Typ(n.Type())
  1757  				dsttype = subst.Typ(info.type2switchType[n])
  1758  			default:
  1759  				base.Fatalf("itab entry with unknown op %s", n.Op())
  1760  			}
  1761  			if srctype.IsInterface() || dsttype.IsEmptyInterface() {
  1762  				// No itab is wanted if src type is an interface. We
  1763  				// will use a type assert instead.
  1764  				d.off = objw.Uintptr(lsym, d.off, 0)
  1765  				infoPrint(" + Unused itab entry for %v\n", srctype)
  1766  			} else {
  1767  				// Make sure all new fully-instantiated types have
  1768  				// their methods created before generating any itabs.
  1769  				g.instantiateMethods()
  1770  				itabLsym := reflectdata.ITabLsym(srctype, dsttype)
  1771  				d.off = objw.SymPtr(lsym, d.off, itabLsym, 0)
  1772  				markTypeUsed(srctype, lsym)
  1773  				infoPrint(" + Itab for (%v,%v)\n", srctype, dsttype)
  1774  			}
  1775  		}
  1776  
  1777  		objw.Global(lsym, int32(d.off), obj.DUPOK|obj.RODATA)
  1778  		infoPrint("=== Finalized dictionary %s\n", d.sym.Name)
  1779  	}
  1780  	g.dictSymsToFinalize = nil
  1781  }
  1782  
  1783  func (g *genInst) getDictionaryValue(pos src.XPos, gf *ir.Name, targs []*types.Type, isMeth bool) ir.Node {
  1784  	sym := g.getDictionarySym(gf, targs, isMeth)
  1785  
  1786  	// Make (or reuse) a node referencing the dictionary symbol.
  1787  	var n *ir.Name
  1788  	if sym.Def != nil {
  1789  		n = sym.Def.(*ir.Name)
  1790  	} else {
  1791  		// We set the position of a static dictionary to be the position of
  1792  		// one of its uses.
  1793  		n = ir.NewNameAt(pos, sym)
  1794  		n.Curfn = ir.CurFunc
  1795  		n.SetType(types.Types[types.TUINTPTR]) // should probably be [...]uintptr, but doesn't really matter
  1796  		n.SetTypecheck(1)
  1797  		n.Class = ir.PEXTERN
  1798  		sym.Def = n
  1799  	}
  1800  
  1801  	// Return the address of the dictionary.  Addr node gets position that was passed in.
  1802  	np := typecheck.NodAddrAt(pos, n)
  1803  	// Note: treat dictionary pointers as uintptrs, so they aren't pointers
  1804  	// with respect to GC. That saves on stack scanning work, write barriers, etc.
  1805  	// We can get away with it because dictionaries are global variables.
  1806  	// TODO: use a cast, or is typing directly ok?
  1807  	np.SetType(types.Types[types.TUINTPTR])
  1808  	np.SetTypecheck(1)
  1809  	return np
  1810  }
  1811  
  1812  // hasShapeNodes returns true if the type of any node in targs has a shape.
  1813  func hasShapeNodes(targs []ir.Node) bool {
  1814  	for _, n := range targs {
  1815  		if n.Type().HasShape() {
  1816  			return true
  1817  		}
  1818  	}
  1819  	return false
  1820  }
  1821  
  1822  // hasShapeTypes returns true if any type in targs has a shape.
  1823  func hasShapeTypes(targs []*types.Type) bool {
  1824  	for _, t := range targs {
  1825  		if t.HasShape() {
  1826  			return true
  1827  		}
  1828  	}
  1829  	return false
  1830  }
  1831  
  1832  // getInstInfo get the dictionary format for a function instantiation- type params, derived
  1833  // types, and needed subdictionaries and itabs.
  1834  func (g *genInst) getInstInfo(st *ir.Func, shapes []*types.Type, instInfo *instInfo) {
  1835  	info := instInfo.dictInfo
  1836  	info.shapeParams = shapes
  1837  
  1838  	for _, t := range info.shapeParams {
  1839  		b := info.shapeToBound[t]
  1840  		if b.HasShape() {
  1841  			// If a type bound is parameterized (unusual case), then we
  1842  			// may need its derived type to do a type assert when doing a
  1843  			// bound call for a type arg that is an interface.
  1844  			addType(info, nil, b)
  1845  		}
  1846  	}
  1847  
  1848  	for _, n := range st.Dcl {
  1849  		addType(info, n, n.Type())
  1850  		n.DictIndex = uint16(findDictType(instInfo, n.Type()) + 1)
  1851  	}
  1852  
  1853  	if infoPrintMode {
  1854  		fmt.Printf(">>> InstInfo for %v\n", st)
  1855  		for _, t := range info.shapeParams {
  1856  			fmt.Printf("  Typeparam %v\n", t)
  1857  		}
  1858  	}
  1859  
  1860  	// Map to remember when we have seen an instantiated function value or method
  1861  	// expression/value as part of a call, so we can determine when we encounter
  1862  	// an uncalled function value or method expression/value.
  1863  	callMap := make(map[ir.Node]bool)
  1864  
  1865  	var visitFunc func(ir.Node)
  1866  	visitFunc = func(n ir.Node) {
  1867  		switch n.Op() {
  1868  		case ir.OFUNCINST:
  1869  			if !callMap[n] && hasShapeNodes(n.(*ir.InstExpr).Targs) {
  1870  				infoPrint("  Closure&subdictionary required at generic function value %v\n", n.(*ir.InstExpr).X)
  1871  				info.subDictCalls = append(info.subDictCalls, subDictInfo{callNode: n, savedXNode: nil})
  1872  			}
  1873  		case ir.OMETHEXPR, ir.OMETHVALUE:
  1874  			if !callMap[n] && !types.IsInterfaceMethod(n.(*ir.SelectorExpr).Selection.Type) &&
  1875  				len(deref(n.(*ir.SelectorExpr).X.Type()).RParams()) > 0 &&
  1876  				hasShapeTypes(deref(n.(*ir.SelectorExpr).X.Type()).RParams()) {
  1877  				if n.(*ir.SelectorExpr).X.Op() == ir.OTYPE {
  1878  					infoPrint("  Closure&subdictionary required at generic meth expr %v\n", n)
  1879  				} else {
  1880  					infoPrint("  Closure&subdictionary required at generic meth value %v\n", n)
  1881  				}
  1882  				info.subDictCalls = append(info.subDictCalls, subDictInfo{callNode: n, savedXNode: nil})
  1883  			}
  1884  		case ir.OCALL:
  1885  			ce := n.(*ir.CallExpr)
  1886  			if ce.X.Op() == ir.OFUNCINST {
  1887  				callMap[ce.X] = true
  1888  				if hasShapeNodes(ce.X.(*ir.InstExpr).Targs) {
  1889  					infoPrint("  Subdictionary at generic function/method call: %v - %v\n", ce.X.(*ir.InstExpr).X, n)
  1890  					// Save the instExpr node for the function call,
  1891  					// since we will lose this information when the
  1892  					// generic function call is transformed to a call
  1893  					// on the shape instantiation.
  1894  					info.subDictCalls = append(info.subDictCalls, subDictInfo{callNode: n, savedXNode: ce.X})
  1895  				}
  1896  			}
  1897  			// Note: this XDOT code is not actually needed as long as we
  1898  			// continue to disable type parameters on RHS of type
  1899  			// declarations (#45639).
  1900  			if ce.X.Op() == ir.OXDOT {
  1901  				callMap[ce.X] = true
  1902  				if isBoundMethod(info, ce.X.(*ir.SelectorExpr)) {
  1903  					infoPrint("  Optional subdictionary at generic bound call: %v\n", n)
  1904  					info.subDictCalls = append(info.subDictCalls, subDictInfo{callNode: n, savedXNode: nil})
  1905  				}
  1906  			}
  1907  		case ir.OCALLMETH:
  1908  			ce := n.(*ir.CallExpr)
  1909  			if ce.X.Op() == ir.ODOTMETH &&
  1910  				len(deref(ce.X.(*ir.SelectorExpr).X.Type()).RParams()) > 0 {
  1911  				callMap[ce.X] = true
  1912  				if hasShapeTypes(deref(ce.X.(*ir.SelectorExpr).X.Type()).RParams()) {
  1913  					infoPrint("  Subdictionary at generic method call: %v\n", n)
  1914  					// Save the selector for the method call, since we
  1915  					// will eventually lose this information when the
  1916  					// generic method call is transformed into a
  1917  					// function call on the method shape instantiation.
  1918  					info.subDictCalls = append(info.subDictCalls, subDictInfo{callNode: n, savedXNode: ce.X})
  1919  				}
  1920  			}
  1921  		case ir.OCONVIFACE:
  1922  			if n.Type().IsInterface() && !n.Type().IsEmptyInterface() &&
  1923  				(n.Type().HasShape() || n.(*ir.ConvExpr).X.Type().HasShape()) {
  1924  				infoPrint("  Itab for interface conv: %v\n", n)
  1925  				info.itabConvs = append(info.itabConvs, n)
  1926  			}
  1927  		case ir.OXDOT:
  1928  			se := n.(*ir.SelectorExpr)
  1929  			if isBoundMethod(info, se) {
  1930  				infoPrint("  Itab for bound call: %v\n", n)
  1931  				info.itabConvs = append(info.itabConvs, n)
  1932  			}
  1933  		case ir.ODOTTYPE, ir.ODOTTYPE2:
  1934  			if !n.(*ir.TypeAssertExpr).Type().IsInterface() && !n.(*ir.TypeAssertExpr).X.Type().IsEmptyInterface() {
  1935  				infoPrint("  Itab for dot type: %v\n", n)
  1936  				info.itabConvs = append(info.itabConvs, n)
  1937  			}
  1938  		case ir.OCLOSURE:
  1939  			// Visit the closure body and add all relevant entries to the
  1940  			// dictionary of the outer function (closure will just use
  1941  			// the dictionary of the outer function).
  1942  			cfunc := n.(*ir.ClosureExpr).Func
  1943  			for _, n1 := range cfunc.Body {
  1944  				ir.Visit(n1, visitFunc)
  1945  			}
  1946  			for _, n := range cfunc.Dcl {
  1947  				n.DictIndex = uint16(findDictType(instInfo, n.Type()) + 1)
  1948  			}
  1949  		case ir.OSWITCH:
  1950  			ss := n.(*ir.SwitchStmt)
  1951  			if ss.Tag != nil && ss.Tag.Op() == ir.OTYPESW &&
  1952  				!ss.Tag.(*ir.TypeSwitchGuard).X.Type().IsEmptyInterface() {
  1953  				for _, cc := range ss.Cases {
  1954  					for _, c := range cc.List {
  1955  						if c.Op() == ir.OTYPE && c.Type().HasShape() {
  1956  							// Type switch from a non-empty interface - might need an itab.
  1957  							infoPrint("  Itab for type switch: %v\n", c)
  1958  							info.itabConvs = append(info.itabConvs, c)
  1959  							if info.type2switchType == nil {
  1960  								info.type2switchType = map[ir.Node]*types.Type{}
  1961  							}
  1962  							info.type2switchType[c] = ss.Tag.(*ir.TypeSwitchGuard).X.Type()
  1963  						}
  1964  					}
  1965  				}
  1966  			}
  1967  		}
  1968  		addType(info, n, n.Type())
  1969  	}
  1970  
  1971  	for _, stmt := range st.Body {
  1972  		ir.Visit(stmt, visitFunc)
  1973  	}
  1974  	if infoPrintMode {
  1975  		for _, t := range info.derivedTypes {
  1976  			fmt.Printf("  Derived type %v\n", t)
  1977  		}
  1978  		fmt.Printf(">>> Done Instinfo\n")
  1979  	}
  1980  	info.startSubDict = len(info.shapeParams) + len(info.derivedTypes)
  1981  	info.startItabConv = len(info.shapeParams) + len(info.derivedTypes) + len(info.subDictCalls)
  1982  	info.dictLen = len(info.shapeParams) + len(info.derivedTypes) + len(info.subDictCalls) + len(info.itabConvs)
  1983  }
  1984  
  1985  // isBoundMethod returns true if the selection indicated by se is a bound method of
  1986  // se.X. se.X must be a shape type (i.e. substituted directly from a type param). If
  1987  // isBoundMethod returns false, then the selection must be a field access of a
  1988  // structural type.
  1989  func isBoundMethod(info *dictInfo, se *ir.SelectorExpr) bool {
  1990  	bound := info.shapeToBound[se.X.Type()]
  1991  	return typecheck.Lookdot1(se, se.Sel, bound, bound.AllMethods(), 1) != nil
  1992  }
  1993  
  1994  // addType adds t to info.derivedTypes if it is parameterized type (which is not
  1995  // just a simple shape) that is different from any existing type on
  1996  // info.derivedTypes.
  1997  func addType(info *dictInfo, n ir.Node, t *types.Type) {
  1998  	if t == nil || !t.HasShape() {
  1999  		return
  2000  	}
  2001  	if t.IsShape() {
  2002  		return
  2003  	}
  2004  	if t.Kind() == types.TFUNC && n != nil &&
  2005  		(t.Recv() != nil || n.Op() == ir.ONAME && n.Name().Class == ir.PFUNC) {
  2006  		// Don't use the type of a named generic function or method,
  2007  		// since that is parameterized by other typeparams.
  2008  		// (They all come from arguments of a FUNCINST node.)
  2009  		return
  2010  	}
  2011  	if doubleCheck && !parameterizedBy(t, info.shapeParams) {
  2012  		base.Fatalf("adding type with invalid parameters %+v", t)
  2013  	}
  2014  	if t.Kind() == types.TSTRUCT && t.IsFuncArgStruct() {
  2015  		// Multiple return values are not a relevant new type (?).
  2016  		return
  2017  	}
  2018  	// Ignore a derived type we've already added.
  2019  	for _, et := range info.derivedTypes {
  2020  		if types.IdenticalStrict(t, et) {
  2021  			return
  2022  		}
  2023  	}
  2024  	info.derivedTypes = append(info.derivedTypes, t)
  2025  }
  2026  
  2027  // parameterizedBy returns true if t is parameterized by (at most) params.
  2028  func parameterizedBy(t *types.Type, params []*types.Type) bool {
  2029  	return parameterizedBy1(t, params, map[*types.Type]bool{})
  2030  }
  2031  func parameterizedBy1(t *types.Type, params []*types.Type, visited map[*types.Type]bool) bool {
  2032  	if visited[t] {
  2033  		return true
  2034  	}
  2035  	visited[t] = true
  2036  
  2037  	if t.Sym() != nil && len(t.RParams()) > 0 {
  2038  		// This defined type is instantiated. Check the instantiating types.
  2039  		for _, r := range t.RParams() {
  2040  			if !parameterizedBy1(r, params, visited) {
  2041  				return false
  2042  			}
  2043  		}
  2044  		return true
  2045  	}
  2046  	if t.IsShape() {
  2047  		// Check if t is one of the allowed parameters in scope.
  2048  		for _, p := range params {
  2049  			if p == t {
  2050  				return true
  2051  			}
  2052  		}
  2053  		// Couldn't find t in the list of allowed parameters.
  2054  		return false
  2055  
  2056  	}
  2057  	switch t.Kind() {
  2058  	case types.TARRAY, types.TPTR, types.TSLICE, types.TCHAN:
  2059  		return parameterizedBy1(t.Elem(), params, visited)
  2060  
  2061  	case types.TMAP:
  2062  		return parameterizedBy1(t.Key(), params, visited) && parameterizedBy1(t.Elem(), params, visited)
  2063  
  2064  	case types.TFUNC:
  2065  		return parameterizedBy1(t.TParams(), params, visited) && parameterizedBy1(t.Recvs(), params, visited) && parameterizedBy1(t.Params(), params, visited) && parameterizedBy1(t.Results(), params, visited)
  2066  
  2067  	case types.TSTRUCT:
  2068  		for _, f := range t.Fields().Slice() {
  2069  			if !parameterizedBy1(f.Type, params, visited) {
  2070  				return false
  2071  			}
  2072  		}
  2073  		return true
  2074  
  2075  	case types.TINTER:
  2076  		for _, f := range t.Methods().Slice() {
  2077  			if !parameterizedBy1(f.Type, params, visited) {
  2078  				return false
  2079  			}
  2080  		}
  2081  		return true
  2082  
  2083  	case types.TINT, types.TINT8, types.TINT16, types.TINT32, types.TINT64,
  2084  		types.TUINT, types.TUINT8, types.TUINT16, types.TUINT32, types.TUINT64,
  2085  		types.TUINTPTR, types.TBOOL, types.TSTRING, types.TFLOAT32, types.TFLOAT64, types.TCOMPLEX64, types.TCOMPLEX128, types.TUNSAFEPTR:
  2086  		return true
  2087  
  2088  	case types.TUNION:
  2089  		for i := 0; i < t.NumTerms(); i++ {
  2090  			tt, _ := t.Term(i)
  2091  			if !parameterizedBy1(tt, params, visited) {
  2092  				return false
  2093  			}
  2094  		}
  2095  		return true
  2096  
  2097  	default:
  2098  		base.Fatalf("bad type kind %+v", t)
  2099  		return true
  2100  	}
  2101  }
  2102  
  2103  // startClosures starts creation of a closure that has the function type typ. It
  2104  // creates all the formal params and results according to the type typ. On return,
  2105  // the body and closure variables of the closure must still be filled in, and
  2106  // ir.UseClosure() called.
  2107  func startClosure(pos src.XPos, outer *ir.Func, typ *types.Type) (*ir.Func, []*types.Field, []*types.Field) {
  2108  	// Make a new internal function.
  2109  	fn := ir.NewClosureFunc(pos, outer != nil)
  2110  	ir.NameClosure(fn.OClosure, outer)
  2111  
  2112  	// Build formal argument and return lists.
  2113  	var formalParams []*types.Field  // arguments of closure
  2114  	var formalResults []*types.Field // returns of closure
  2115  	for i := 0; i < typ.NumParams(); i++ {
  2116  		t := typ.Params().Field(i).Type
  2117  		arg := ir.NewNameAt(pos, typecheck.LookupNum("a", i))
  2118  		if outer != nil {
  2119  			arg.SetSym(outer.Sym().Pkg.Lookup(arg.Sym().Name))
  2120  		}
  2121  		arg.Class = ir.PPARAM
  2122  		typed(t, arg)
  2123  		arg.Curfn = fn
  2124  		fn.Dcl = append(fn.Dcl, arg)
  2125  		f := types.NewField(pos, arg.Sym(), t)
  2126  		f.Nname = arg
  2127  		f.SetIsDDD(typ.Params().Field(i).IsDDD())
  2128  		formalParams = append(formalParams, f)
  2129  	}
  2130  	for i := 0; i < typ.NumResults(); i++ {
  2131  		t := typ.Results().Field(i).Type
  2132  		result := ir.NewNameAt(pos, typecheck.LookupNum("r", i)) // TODO: names not needed?
  2133  		if outer != nil {
  2134  			result.SetSym(outer.Sym().Pkg.Lookup(result.Sym().Name))
  2135  		}
  2136  		result.Class = ir.PPARAMOUT
  2137  		typed(t, result)
  2138  		result.Curfn = fn
  2139  		fn.Dcl = append(fn.Dcl, result)
  2140  		f := types.NewField(pos, result.Sym(), t)
  2141  		f.Nname = result
  2142  		formalResults = append(formalResults, f)
  2143  	}
  2144  
  2145  	// Build an internal function with the right signature.
  2146  	closureType := types.NewSignature(typ.Pkg(), nil, nil, formalParams, formalResults)
  2147  	typed(closureType, fn.Nname)
  2148  	typed(typ, fn.OClosure)
  2149  	fn.SetTypecheck(1)
  2150  	return fn, formalParams, formalResults
  2151  
  2152  }
  2153  
  2154  // assertToBound returns a new node that converts a node rcvr with interface type to
  2155  // the 'dst' interface type.
  2156  func assertToBound(info *instInfo, dictVar *ir.Name, pos src.XPos, rcvr ir.Node, dst *types.Type) ir.Node {
  2157  	if dst.HasShape() {
  2158  		ix := findDictType(info, dst)
  2159  		assert(ix >= 0)
  2160  		rt := getDictionaryType(info, dictVar, pos, ix)
  2161  		rcvr = ir.NewDynamicTypeAssertExpr(pos, ir.ODYNAMICDOTTYPE, rcvr, rt)
  2162  		typed(dst, rcvr)
  2163  	} else {
  2164  		rcvr = ir.NewTypeAssertExpr(pos, rcvr, nil)
  2165  		typed(dst, rcvr)
  2166  	}
  2167  	return rcvr
  2168  }
  2169  
  2170  // buildClosure2 makes a closure to implement a method expression m (generic form x)
  2171  // which has a shape type as receiver. If the receiver is exactly a shape (i.e. from
  2172  // a typeparam), then the body of the closure converts m.X (the receiver) to the
  2173  // interface bound type, and makes an interface call with the remaining arguments.
  2174  //
  2175  // The returned closure is fully substituted and has already had any needed
  2176  // transformations done.
  2177  func (g *genInst) buildClosure2(info *instInfo, m ir.Node) ir.Node {
  2178  	outer := info.fun
  2179  	pos := m.Pos()
  2180  	typ := m.Type() // type of the closure
  2181  
  2182  	fn, formalParams, formalResults := startClosure(pos, outer, typ)
  2183  
  2184  	// Capture dictionary calculated in the outer function
  2185  	dictVar := ir.CaptureName(pos, fn, info.dictParam)
  2186  	typed(types.Types[types.TUINTPTR], dictVar)
  2187  
  2188  	// Build arguments to call inside the closure.
  2189  	var args []ir.Node
  2190  	for i := 0; i < typ.NumParams(); i++ {
  2191  		args = append(args, formalParams[i].Nname.(*ir.Name))
  2192  	}
  2193  
  2194  	// Build call itself. This involves converting the first argument to the
  2195  	// bound type (an interface) using the dictionary, and then making an
  2196  	// interface call with the remaining arguments.
  2197  	var innerCall ir.Node
  2198  	rcvr := args[0]
  2199  	args = args[1:]
  2200  	assert(m.(*ir.SelectorExpr).X.Type().IsShape())
  2201  	dst := info.dictInfo.shapeToBound[m.(*ir.SelectorExpr).X.Type()]
  2202  	if m.(*ir.SelectorExpr).X.Type().IsInterface() {
  2203  		// If type arg is an interface (unusual case), we do a type assert to
  2204  		// the type bound.
  2205  		rcvr = assertToBound(info, dictVar, pos, rcvr, dst)
  2206  	} else {
  2207  		rcvr = convertUsingDictionary(info, dictVar, pos, rcvr, m, dst, false)
  2208  	}
  2209  	dot := ir.NewSelectorExpr(pos, ir.ODOTINTER, rcvr, m.(*ir.SelectorExpr).Sel)
  2210  	dot.Selection = typecheck.Lookdot1(dot, dot.Sel, dot.X.Type(), dot.X.Type().AllMethods(), 1)
  2211  
  2212  	typed(dot.Selection.Type, dot)
  2213  	innerCall = ir.NewCallExpr(pos, ir.OCALLINTER, dot, args)
  2214  	t := m.Type()
  2215  	if t.NumResults() == 0 {
  2216  		innerCall.SetTypecheck(1)
  2217  	} else if t.NumResults() == 1 {
  2218  		typed(t.Results().Field(0).Type, innerCall)
  2219  	} else {
  2220  		typed(t.Results(), innerCall)
  2221  	}
  2222  	if len(formalResults) > 0 {
  2223  		innerCall = ir.NewReturnStmt(pos, []ir.Node{innerCall})
  2224  		innerCall.SetTypecheck(1)
  2225  	}
  2226  	fn.Body = []ir.Node{innerCall}
  2227  
  2228  	// We're all done with the captured dictionary
  2229  	ir.FinishCaptureNames(pos, outer, fn)
  2230  
  2231  	// Do final checks on closure and return it.
  2232  	return ir.UseClosure(fn.OClosure, typecheck.Target)
  2233  }
  2234  

View as plain text