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

Documentation: cmd/compile/internal/noder

     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  	"bytes"
    12  	"cmd/compile/internal/base"
    13  	"cmd/compile/internal/ir"
    14  	"cmd/compile/internal/typecheck"
    15  	"cmd/compile/internal/types"
    16  	"cmd/internal/src"
    17  	"fmt"
    18  	"strings"
    19  )
    20  
    21  // For catching problems as we add more features
    22  // TODO(danscales): remove assertions or replace with base.FatalfAt()
    23  func assert(p bool) {
    24  	if !p {
    25  		panic("assertion failed")
    26  	}
    27  }
    28  
    29  // stencil scans functions for instantiated generic function calls and creates the
    30  // required instantiations for simple generic functions. It also creates
    31  // instantiated methods for all fully-instantiated generic types that have been
    32  // encountered already or new ones that are encountered during the stenciling
    33  // process.
    34  func (g *irgen) stencil() {
    35  	g.target.Stencils = make(map[*types.Sym]*ir.Func)
    36  
    37  	// Instantiate the methods of instantiated generic types that we have seen so far.
    38  	g.instantiateMethods()
    39  
    40  	// Don't use range(g.target.Decls) - we also want to process any new instantiated
    41  	// functions that are created during this loop, in order to handle generic
    42  	// functions calling other generic functions.
    43  	for i := 0; i < len(g.target.Decls); i++ {
    44  		decl := g.target.Decls[i]
    45  
    46  		// Look for function instantiations in bodies of non-generic
    47  		// functions or in global assignments (ignore global type and
    48  		// constant declarations).
    49  		switch decl.Op() {
    50  		case ir.ODCLFUNC:
    51  			if decl.Type().HasTParam() {
    52  				// Skip any generic functions
    53  				continue
    54  			}
    55  			// transformCall() below depends on CurFunc being set.
    56  			ir.CurFunc = decl.(*ir.Func)
    57  
    58  		case ir.OAS, ir.OAS2, ir.OAS2DOTTYPE, ir.OAS2FUNC, ir.OAS2MAPR, ir.OAS2RECV, ir.OASOP:
    59  			// These are all the various kinds of global assignments,
    60  			// whose right-hand-sides might contain a function
    61  			// instantiation.
    62  
    63  		default:
    64  			// The other possible ops at the top level are ODCLCONST
    65  			// and ODCLTYPE, which don't have any function
    66  			// instantiations.
    67  			continue
    68  		}
    69  
    70  		// For all non-generic code, search for any function calls using
    71  		// generic function instantiations. Then create the needed
    72  		// instantiated function if it hasn't been created yet, and change
    73  		// to calling that function directly.
    74  		modified := false
    75  		foundFuncInst := false
    76  		ir.Visit(decl, func(n ir.Node) {
    77  			if n.Op() == ir.OFUNCINST {
    78  				// We found a function instantiation that is not
    79  				// immediately called.
    80  				foundFuncInst = true
    81  			}
    82  			if n.Op() != ir.OCALL || n.(*ir.CallExpr).X.Op() != ir.OFUNCINST {
    83  				return
    84  			}
    85  			// We have found a function call using a generic function
    86  			// instantiation.
    87  			call := n.(*ir.CallExpr)
    88  			inst := call.X.(*ir.InstExpr)
    89  			st := g.getInstantiationForNode(inst)
    90  			// Replace the OFUNCINST with a direct reference to the
    91  			// new stenciled function
    92  			call.X = st.Nname
    93  			if inst.X.Op() == ir.OCALLPART {
    94  				// When we create an instantiation of a method
    95  				// call, we make it a function. So, move the
    96  				// receiver to be the first arg of the function
    97  				// call.
    98  				withRecv := make([]ir.Node, len(call.Args)+1)
    99  				dot := inst.X.(*ir.SelectorExpr)
   100  				withRecv[0] = dot.X
   101  				copy(withRecv[1:], call.Args)
   102  				call.Args = withRecv
   103  			}
   104  			// Transform the Call now, which changes OCALL
   105  			// to OCALLFUNC and does typecheckaste/assignconvfn.
   106  			transformCall(call)
   107  			modified = true
   108  		})
   109  
   110  		// If we found an OFUNCINST without a corresponding call in the
   111  		// above decl, then traverse the nodes of decl again (with
   112  		// EditChildren rather than Visit), where we actually change the
   113  		// OFUNCINST node to an ONAME for the instantiated function.
   114  		// EditChildren is more expensive than Visit, so we only do this
   115  		// in the infrequent case of an OFUNCINSt without a corresponding
   116  		// call.
   117  		if foundFuncInst {
   118  			var edit func(ir.Node) ir.Node
   119  			edit = func(x ir.Node) ir.Node {
   120  				if x.Op() == ir.OFUNCINST {
   121  					st := g.getInstantiationForNode(x.(*ir.InstExpr))
   122  					return st.Nname
   123  				}
   124  				ir.EditChildren(x, edit)
   125  				return x
   126  			}
   127  			edit(decl)
   128  		}
   129  		if base.Flag.W > 1 && modified {
   130  			ir.Dump(fmt.Sprintf("\nmodified %v", decl), decl)
   131  		}
   132  		ir.CurFunc = nil
   133  		// We may have seen new fully-instantiated generic types while
   134  		// instantiating any needed functions/methods in the above
   135  		// function. If so, instantiate all the methods of those types
   136  		// (which will then lead to more function/methods to scan in the loop).
   137  		g.instantiateMethods()
   138  	}
   139  
   140  }
   141  
   142  // instantiateMethods instantiates all the methods of all fully-instantiated
   143  // generic types that have been added to g.instTypeList.
   144  func (g *irgen) instantiateMethods() {
   145  	for i := 0; i < len(g.instTypeList); i++ {
   146  		typ := g.instTypeList[i]
   147  		// Get the base generic type by looking up the symbol of the
   148  		// generic (uninstantiated) name.
   149  		baseSym := typ.Sym().Pkg.Lookup(genericTypeName(typ.Sym()))
   150  		baseType := baseSym.Def.(*ir.Name).Type()
   151  		for j, m := range typ.Methods().Slice() {
   152  			name := m.Nname.(*ir.Name)
   153  			targs := make([]ir.Node, len(typ.RParams()))
   154  			for k, targ := range typ.RParams() {
   155  				targs[k] = ir.TypeNode(targ)
   156  			}
   157  			baseNname := baseType.Methods().Slice()[j].Nname.(*ir.Name)
   158  			name.Func = g.getInstantiation(baseNname, targs, true)
   159  		}
   160  	}
   161  	g.instTypeList = nil
   162  
   163  }
   164  
   165  // genericSym returns the name of the base generic type for the type named by
   166  // sym. It simply returns the name obtained by removing everything after the
   167  // first bracket ("[").
   168  func genericTypeName(sym *types.Sym) string {
   169  	return sym.Name[0:strings.Index(sym.Name, "[")]
   170  }
   171  
   172  // getInstantiationForNode returns the function/method instantiation for a
   173  // InstExpr node inst.
   174  func (g *irgen) getInstantiationForNode(inst *ir.InstExpr) *ir.Func {
   175  	if meth, ok := inst.X.(*ir.SelectorExpr); ok {
   176  		return g.getInstantiation(meth.Selection.Nname.(*ir.Name), inst.Targs, true)
   177  	} else {
   178  		return g.getInstantiation(inst.X.(*ir.Name), inst.Targs, false)
   179  	}
   180  }
   181  
   182  // getInstantiation gets the instantiantion of the function or method nameNode
   183  // with the type arguments targs. If the instantiated function is not already
   184  // cached, then it calls genericSubst to create the new instantiation.
   185  func (g *irgen) getInstantiation(nameNode *ir.Name, targs []ir.Node, isMeth bool) *ir.Func {
   186  	sym := makeInstName(nameNode.Sym(), targs, isMeth)
   187  	st := g.target.Stencils[sym]
   188  	if st == nil {
   189  		// If instantiation doesn't exist yet, create it and add
   190  		// to the list of decls.
   191  		st = g.genericSubst(sym, nameNode, targs, isMeth)
   192  		g.target.Stencils[sym] = st
   193  		g.target.Decls = append(g.target.Decls, st)
   194  		if base.Flag.W > 1 {
   195  			ir.Dump(fmt.Sprintf("\nstenciled %v", st), st)
   196  		}
   197  	}
   198  	return st
   199  }
   200  
   201  // makeInstName makes the unique name for a stenciled generic function or method,
   202  // based on the name of the function fy=nsym and the targs. It replaces any
   203  // existing bracket type list in the name. makeInstName asserts that fnsym has
   204  // brackets in its name if and only if hasBrackets is true.
   205  // TODO(danscales): remove the assertions and the hasBrackets argument later.
   206  //
   207  // Names of declared generic functions have no brackets originally, so hasBrackets
   208  // should be false. Names of generic methods already have brackets, since the new
   209  // type parameter is specified in the generic type of the receiver (e.g. func
   210  // (func (v *value[T]).set(...) { ... } has the original name (*value[T]).set.
   211  //
   212  // The standard naming is something like: 'genFn[int,bool]' for functions and
   213  // '(*genType[int,bool]).methodName' for methods
   214  func makeInstName(fnsym *types.Sym, targs []ir.Node, hasBrackets bool) *types.Sym {
   215  	b := bytes.NewBufferString("")
   216  	name := fnsym.Name
   217  	i := strings.Index(name, "[")
   218  	assert(hasBrackets == (i >= 0))
   219  	if i >= 0 {
   220  		b.WriteString(name[0:i])
   221  	} else {
   222  		b.WriteString(name)
   223  	}
   224  	b.WriteString("[")
   225  	for i, targ := range targs {
   226  		if i > 0 {
   227  			b.WriteString(",")
   228  		}
   229  		b.WriteString(targ.Type().String())
   230  	}
   231  	b.WriteString("]")
   232  	if i >= 0 {
   233  		i2 := strings.Index(name[i:], "]")
   234  		assert(i2 >= 0)
   235  		b.WriteString(name[i+i2+1:])
   236  	}
   237  	return typecheck.Lookup(b.String())
   238  }
   239  
   240  // Struct containing info needed for doing the substitution as we create the
   241  // instantiation of a generic function with specified type arguments.
   242  type subster struct {
   243  	g        *irgen
   244  	isMethod bool     // If a method is being instantiated
   245  	newf     *ir.Func // Func node for the new stenciled function
   246  	tparams  []*types.Field
   247  	targs    []ir.Node
   248  	// The substitution map from name nodes in the generic function to the
   249  	// name nodes in the new stenciled function.
   250  	vars map[*ir.Name]*ir.Name
   251  }
   252  
   253  // genericSubst returns a new function with name newsym. The function is an
   254  // instantiation of a generic function or method specified by namedNode with type
   255  // args targs. For a method with a generic receiver, it returns an instantiated
   256  // function type where the receiver becomes the first parameter. Otherwise the
   257  // instantiated method would still need to be transformed by later compiler
   258  // phases.
   259  func (g *irgen) genericSubst(newsym *types.Sym, nameNode *ir.Name, targs []ir.Node, isMethod bool) *ir.Func {
   260  	var tparams []*types.Field
   261  	if isMethod {
   262  		// Get the type params from the method receiver (after skipping
   263  		// over any pointer)
   264  		recvType := nameNode.Type().Recv().Type
   265  		recvType = deref(recvType)
   266  		tparams = make([]*types.Field, len(recvType.RParams()))
   267  		for i, rparam := range recvType.RParams() {
   268  			tparams[i] = types.NewField(src.NoXPos, nil, rparam)
   269  		}
   270  	} else {
   271  		tparams = nameNode.Type().TParams().Fields().Slice()
   272  	}
   273  	gf := nameNode.Func
   274  	// Pos of the instantiated function is same as the generic function
   275  	newf := ir.NewFunc(gf.Pos())
   276  	newf.Pragma = gf.Pragma // copy over pragmas from generic function to stenciled implementation.
   277  	newf.Nname = ir.NewNameAt(gf.Pos(), newsym)
   278  	newf.Nname.Func = newf
   279  	newf.Nname.Defn = newf
   280  	newsym.Def = newf.Nname
   281  	savef := ir.CurFunc
   282  	// transformCall/transformReturn (called during stenciling of the body)
   283  	// depend on ir.CurFunc being set.
   284  	ir.CurFunc = newf
   285  
   286  	assert(len(tparams) == len(targs))
   287  
   288  	subst := &subster{
   289  		g:        g,
   290  		isMethod: isMethod,
   291  		newf:     newf,
   292  		tparams:  tparams,
   293  		targs:    targs,
   294  		vars:     make(map[*ir.Name]*ir.Name),
   295  	}
   296  
   297  	newf.Dcl = make([]*ir.Name, len(gf.Dcl))
   298  	for i, n := range gf.Dcl {
   299  		newf.Dcl[i] = subst.node(n).(*ir.Name)
   300  	}
   301  
   302  	// Ugly: we have to insert the Name nodes of the parameters/results into
   303  	// the function type. The current function type has no Nname fields set,
   304  	// because it came via conversion from the types2 type.
   305  	oldt := nameNode.Type()
   306  	// We also transform a generic method type to the corresponding
   307  	// instantiated function type where the receiver is the first parameter.
   308  	newt := types.NewSignature(oldt.Pkg(), nil, nil,
   309  		subst.fields(ir.PPARAM, append(oldt.Recvs().FieldSlice(), oldt.Params().FieldSlice()...), newf.Dcl),
   310  		subst.fields(ir.PPARAMOUT, oldt.Results().FieldSlice(), newf.Dcl))
   311  
   312  	newf.Nname.SetType(newt)
   313  	ir.MarkFunc(newf.Nname)
   314  	newf.SetTypecheck(1)
   315  	newf.Nname.SetTypecheck(1)
   316  
   317  	// Make sure name/type of newf is set before substituting the body.
   318  	newf.Body = subst.list(gf.Body)
   319  	ir.CurFunc = savef
   320  
   321  	return newf
   322  }
   323  
   324  // node is like DeepCopy(), but creates distinct ONAME nodes, and also descends
   325  // into closures. It substitutes type arguments for type parameters in all the new
   326  // nodes.
   327  func (subst *subster) node(n ir.Node) ir.Node {
   328  	// Use closure to capture all state needed by the ir.EditChildren argument.
   329  	var edit func(ir.Node) ir.Node
   330  	edit = func(x ir.Node) ir.Node {
   331  		switch x.Op() {
   332  		case ir.OTYPE:
   333  			return ir.TypeNode(subst.typ(x.Type()))
   334  
   335  		case ir.ONAME:
   336  			name := x.(*ir.Name)
   337  			if v := subst.vars[name]; v != nil {
   338  				return v
   339  			}
   340  			m := ir.NewNameAt(name.Pos(), name.Sym())
   341  			if name.IsClosureVar() {
   342  				m.SetIsClosureVar(true)
   343  			}
   344  			t := x.Type()
   345  			if t == nil {
   346  				assert(name.BuiltinOp != 0)
   347  			} else {
   348  				newt := subst.typ(t)
   349  				m.SetType(newt)
   350  			}
   351  			m.BuiltinOp = name.BuiltinOp
   352  			m.Curfn = subst.newf
   353  			m.Class = name.Class
   354  			m.Func = name.Func
   355  			subst.vars[name] = m
   356  			m.SetTypecheck(1)
   357  			return m
   358  		case ir.OLITERAL, ir.ONIL:
   359  			if x.Sym() != nil {
   360  				return x
   361  			}
   362  		}
   363  		m := ir.Copy(x)
   364  		if _, isExpr := m.(ir.Expr); isExpr {
   365  			t := x.Type()
   366  			if t == nil {
   367  				// t can be nil only if this is a call that has no
   368  				// return values, so allow that and otherwise give
   369  				// an error.
   370  				_, isCallExpr := m.(*ir.CallExpr)
   371  				_, isStructKeyExpr := m.(*ir.StructKeyExpr)
   372  				if !isCallExpr && !isStructKeyExpr && x.Op() != ir.OPANIC &&
   373  					x.Op() != ir.OCLOSE {
   374  					base.Fatalf(fmt.Sprintf("Nil type for %v", x))
   375  				}
   376  			} else if x.Op() != ir.OCLOSURE {
   377  				m.SetType(subst.typ(x.Type()))
   378  			}
   379  		}
   380  		ir.EditChildren(m, edit)
   381  
   382  		if x.Typecheck() == 3 {
   383  			// These are nodes whose transforms were delayed until
   384  			// their instantiated type was known.
   385  			m.SetTypecheck(1)
   386  			if typecheck.IsCmp(x.Op()) {
   387  				transformCompare(m.(*ir.BinaryExpr))
   388  			} else {
   389  				switch x.Op() {
   390  				case ir.OSLICE, ir.OSLICE3:
   391  					transformSlice(m.(*ir.SliceExpr))
   392  
   393  				case ir.OADD:
   394  					m = transformAdd(m.(*ir.BinaryExpr))
   395  
   396  				case ir.OINDEX:
   397  					transformIndex(m.(*ir.IndexExpr))
   398  
   399  				case ir.OAS2:
   400  					as2 := m.(*ir.AssignListStmt)
   401  					transformAssign(as2, as2.Lhs, as2.Rhs)
   402  
   403  				case ir.OAS:
   404  					as := m.(*ir.AssignStmt)
   405  					lhs, rhs := []ir.Node{as.X}, []ir.Node{as.Y}
   406  					transformAssign(as, lhs, rhs)
   407  
   408  				case ir.OASOP:
   409  					as := m.(*ir.AssignOpStmt)
   410  					transformCheckAssign(as, as.X)
   411  
   412  				case ir.ORETURN:
   413  					transformReturn(m.(*ir.ReturnStmt))
   414  
   415  				case ir.OSEND:
   416  					transformSend(m.(*ir.SendStmt))
   417  
   418  				default:
   419  					base.Fatalf("Unexpected node with Typecheck() == 3")
   420  				}
   421  			}
   422  		}
   423  
   424  		switch x.Op() {
   425  		case ir.OLITERAL:
   426  			t := m.Type()
   427  			if t != x.Type() {
   428  				// types2 will give us a constant with a type T,
   429  				// if an untyped constant is used with another
   430  				// operand of type T (in a provably correct way).
   431  				// When we substitute in the type args during
   432  				// stenciling, we now know the real type of the
   433  				// constant. We may then need to change the
   434  				// BasicLit.val to be the correct type (e.g.
   435  				// convert an int64Val constant to a floatVal
   436  				// constant).
   437  				m.SetType(types.UntypedInt) // use any untyped type for DefaultLit to work
   438  				m = typecheck.DefaultLit(m, t)
   439  			}
   440  
   441  		case ir.OXDOT:
   442  			// A method value/call via a type param will have been
   443  			// left as an OXDOT. When we see this during stenciling,
   444  			// finish the transformation, now that we have the
   445  			// instantiated receiver type. We need to do this now,
   446  			// since the access/selection to the method for the real
   447  			// type is very different from the selection for the type
   448  			// param. m will be transformed to an OCALLPART node. It
   449  			// will be transformed to an ODOTMETH or ODOTINTER node if
   450  			// we find in the OCALL case below that the method value
   451  			// is actually called.
   452  			transformDot(m.(*ir.SelectorExpr), false)
   453  			m.SetTypecheck(1)
   454  
   455  		case ir.OCALL:
   456  			call := m.(*ir.CallExpr)
   457  			switch call.X.Op() {
   458  			case ir.OTYPE:
   459  				// Transform the conversion, now that we know the
   460  				// type argument.
   461  				m = transformConvCall(m.(*ir.CallExpr))
   462  
   463  			case ir.OCALLPART:
   464  				// Redo the transformation of OXDOT, now that we
   465  				// know the method value is being called. Then
   466  				// transform the call.
   467  				call.X.(*ir.SelectorExpr).SetOp(ir.OXDOT)
   468  				transformDot(call.X.(*ir.SelectorExpr), true)
   469  				transformCall(call)
   470  
   471  			case ir.ODOT, ir.ODOTPTR:
   472  				// An OXDOT for a generic receiver was resolved to
   473  				// an access to a field which has a function
   474  				// value. Transform the call to that function, now
   475  				// that the OXDOT was resolved.
   476  				transformCall(call)
   477  
   478  			case ir.ONAME:
   479  				name := call.X.Name()
   480  				if name.BuiltinOp != ir.OXXX {
   481  					switch name.BuiltinOp {
   482  					case ir.OMAKE, ir.OREAL, ir.OIMAG, ir.OLEN, ir.OCAP, ir.OAPPEND:
   483  						// Transform these builtins now that we
   484  						// know the type of the args.
   485  						m = transformBuiltin(call)
   486  					default:
   487  						base.FatalfAt(call.Pos(), "Unexpected builtin op")
   488  					}
   489  				} else {
   490  					// This is the case of a function value that was a
   491  					// type parameter (implied to be a function via a
   492  					// structural constraint) which is now resolved.
   493  					transformCall(call)
   494  				}
   495  
   496  			case ir.OCLOSURE:
   497  				transformCall(call)
   498  
   499  			case ir.OFUNCINST:
   500  				// A call with an OFUNCINST will get transformed
   501  				// in stencil() once we have created & attached the
   502  				// instantiation to be called.
   503  
   504  			default:
   505  				base.FatalfAt(call.Pos(), fmt.Sprintf("Unexpected op with CALL during stenciling: %v", call.X.Op()))
   506  			}
   507  
   508  		case ir.OCLOSURE:
   509  			x := x.(*ir.ClosureExpr)
   510  			// Need to duplicate x.Func.Nname, x.Func.Dcl, x.Func.ClosureVars, and
   511  			// x.Func.Body.
   512  			oldfn := x.Func
   513  			newfn := ir.NewFunc(oldfn.Pos())
   514  			if oldfn.ClosureCalled() {
   515  				newfn.SetClosureCalled(true)
   516  			}
   517  			newfn.SetIsHiddenClosure(true)
   518  			m.(*ir.ClosureExpr).Func = newfn
   519  			// Closure name can already have brackets, if it derives
   520  			// from a generic method
   521  			newsym := makeInstName(oldfn.Nname.Sym(), subst.targs, subst.isMethod)
   522  			newfn.Nname = ir.NewNameAt(oldfn.Nname.Pos(), newsym)
   523  			newfn.Nname.Func = newfn
   524  			newfn.Nname.Defn = newfn
   525  			ir.MarkFunc(newfn.Nname)
   526  			newfn.OClosure = m.(*ir.ClosureExpr)
   527  
   528  			saveNewf := subst.newf
   529  			ir.CurFunc = newfn
   530  			subst.newf = newfn
   531  			newfn.Dcl = subst.namelist(oldfn.Dcl)
   532  			newfn.ClosureVars = subst.namelist(oldfn.ClosureVars)
   533  
   534  			typed(subst.typ(oldfn.Nname.Type()), newfn.Nname)
   535  			typed(newfn.Nname.Type(), m)
   536  			newfn.SetTypecheck(1)
   537  
   538  			// Make sure type of closure function is set before doing body.
   539  			newfn.Body = subst.list(oldfn.Body)
   540  			subst.newf = saveNewf
   541  			ir.CurFunc = saveNewf
   542  
   543  			subst.g.target.Decls = append(subst.g.target.Decls, newfn)
   544  		}
   545  		return m
   546  	}
   547  
   548  	return edit(n)
   549  }
   550  
   551  func (subst *subster) namelist(l []*ir.Name) []*ir.Name {
   552  	s := make([]*ir.Name, len(l))
   553  	for i, n := range l {
   554  		s[i] = subst.node(n).(*ir.Name)
   555  		if n.Defn != nil {
   556  			s[i].Defn = subst.node(n.Defn)
   557  		}
   558  		if n.Outer != nil {
   559  			s[i].Outer = subst.node(n.Outer).(*ir.Name)
   560  		}
   561  	}
   562  	return s
   563  }
   564  
   565  func (subst *subster) list(l []ir.Node) []ir.Node {
   566  	s := make([]ir.Node, len(l))
   567  	for i, n := range l {
   568  		s[i] = subst.node(n)
   569  	}
   570  	return s
   571  }
   572  
   573  // tstruct substitutes type params in types of the fields of a structure type. For
   574  // each field, if Nname is set, tstruct also translates the Nname using
   575  // subst.vars, if Nname is in subst.vars. To always force the creation of a new
   576  // (top-level) struct, regardless of whether anything changed with the types or
   577  // names of the struct's fields, set force to true.
   578  func (subst *subster) tstruct(t *types.Type, force bool) *types.Type {
   579  	if t.NumFields() == 0 {
   580  		if t.HasTParam() {
   581  			// For an empty struct, we need to return a new type,
   582  			// since it may now be fully instantiated (HasTParam
   583  			// becomes false).
   584  			return types.NewStruct(t.Pkg(), nil)
   585  		}
   586  		return t
   587  	}
   588  	var newfields []*types.Field
   589  	if force {
   590  		newfields = make([]*types.Field, t.NumFields())
   591  	}
   592  	for i, f := range t.Fields().Slice() {
   593  		t2 := subst.typ(f.Type)
   594  		if (t2 != f.Type || f.Nname != nil) && newfields == nil {
   595  			newfields = make([]*types.Field, t.NumFields())
   596  			for j := 0; j < i; j++ {
   597  				newfields[j] = t.Field(j)
   598  			}
   599  		}
   600  		if newfields != nil {
   601  			// TODO(danscales): make sure this works for the field
   602  			// names of embedded types (which should keep the name of
   603  			// the type param, not the instantiated type).
   604  			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
   605  			if f.Nname != nil {
   606  				// f.Nname may not be in subst.vars[] if this is
   607  				// a function name or a function instantiation type
   608  				// that we are translating
   609  				v := subst.vars[f.Nname.(*ir.Name)]
   610  				// Be careful not to put a nil var into Nname,
   611  				// since Nname is an interface, so it would be a
   612  				// non-nil interface.
   613  				if v != nil {
   614  					newfields[i].Nname = v
   615  				}
   616  			}
   617  		}
   618  	}
   619  	if newfields != nil {
   620  		return types.NewStruct(t.Pkg(), newfields)
   621  	}
   622  	return t
   623  
   624  }
   625  
   626  // tinter substitutes type params in types of the methods of an interface type.
   627  func (subst *subster) tinter(t *types.Type) *types.Type {
   628  	if t.Methods().Len() == 0 {
   629  		return t
   630  	}
   631  	var newfields []*types.Field
   632  	for i, f := range t.Methods().Slice() {
   633  		t2 := subst.typ(f.Type)
   634  		if (t2 != f.Type || f.Nname != nil) && newfields == nil {
   635  			newfields = make([]*types.Field, t.Methods().Len())
   636  			for j := 0; j < i; j++ {
   637  				newfields[j] = t.Methods().Index(j)
   638  			}
   639  		}
   640  		if newfields != nil {
   641  			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
   642  		}
   643  	}
   644  	if newfields != nil {
   645  		return types.NewInterface(t.Pkg(), newfields)
   646  	}
   647  	return t
   648  }
   649  
   650  // instTypeName creates a name for an instantiated type, based on the name of the
   651  // generic type and the type args
   652  func instTypeName(name string, targs []*types.Type) string {
   653  	b := bytes.NewBufferString(name)
   654  	b.WriteByte('[')
   655  	for i, targ := range targs {
   656  		if i > 0 {
   657  			b.WriteByte(',')
   658  		}
   659  		b.WriteString(targ.String())
   660  	}
   661  	b.WriteByte(']')
   662  	return b.String()
   663  }
   664  
   665  // typ computes the type obtained by substituting any type parameter in t with the
   666  // corresponding type argument in subst. If t contains no type parameters, the
   667  // result is t; otherwise the result is a new type. It deals with recursive types
   668  // by using TFORW types and finding partially or fully created types via sym.Def.
   669  func (subst *subster) typ(t *types.Type) *types.Type {
   670  	if !t.HasTParam() && t.Kind() != types.TFUNC {
   671  		// Note: function types need to be copied regardless, as the
   672  		// types of closures may contain declarations that need
   673  		// to be copied. See #45738.
   674  		return t
   675  	}
   676  
   677  	if t.Kind() == types.TTYPEPARAM {
   678  		for i, tp := range subst.tparams {
   679  			if tp.Type == t {
   680  				return subst.targs[i].Type()
   681  			}
   682  		}
   683  		// If t is a simple typeparam T, then t has the name/symbol 'T'
   684  		// and t.Underlying() == t.
   685  		//
   686  		// However, consider the type definition: 'type P[T any] T'. We
   687  		// might use this definition so we can have a variant of type T
   688  		// that we can add new methods to. Suppose t is a reference to
   689  		// P[T]. t has the name 'P[T]', but its kind is TTYPEPARAM,
   690  		// because P[T] is defined as T. If we look at t.Underlying(), it
   691  		// is different, because the name of t.Underlying() is 'T' rather
   692  		// than 'P[T]'. But the kind of t.Underlying() is also TTYPEPARAM.
   693  		// In this case, we do the needed recursive substitution in the
   694  		// case statement below.
   695  		if t.Underlying() == t {
   696  			// t is a simple typeparam that didn't match anything in tparam
   697  			return t
   698  		}
   699  		// t is a more complex typeparam (e.g. P[T], as above, whose
   700  		// definition is just T).
   701  		assert(t.Sym() != nil)
   702  	}
   703  
   704  	var newsym *types.Sym
   705  	var neededTargs []*types.Type
   706  	var forw *types.Type
   707  
   708  	if t.Sym() != nil {
   709  		// Translate the type params for this type according to
   710  		// the tparam/targs mapping from subst.
   711  		neededTargs = make([]*types.Type, len(t.RParams()))
   712  		for i, rparam := range t.RParams() {
   713  			neededTargs[i] = subst.typ(rparam)
   714  		}
   715  		// For a named (defined) type, we have to change the name of the
   716  		// type as well. We do this first, so we can look up if we've
   717  		// already seen this type during this substitution or other
   718  		// definitions/substitutions.
   719  		genName := genericTypeName(t.Sym())
   720  		newsym = t.Sym().Pkg.Lookup(instTypeName(genName, neededTargs))
   721  		if newsym.Def != nil {
   722  			// We've already created this instantiated defined type.
   723  			return newsym.Def.Type()
   724  		}
   725  
   726  		// In order to deal with recursive generic types, create a TFORW
   727  		// type initially and set the Def field of its sym, so it can be
   728  		// found if this type appears recursively within the type.
   729  		forw = newIncompleteNamedType(t.Pos(), newsym)
   730  		//println("Creating new type by sub", newsym.Name, forw.HasTParam())
   731  		forw.SetRParams(neededTargs)
   732  	}
   733  
   734  	var newt *types.Type
   735  
   736  	switch t.Kind() {
   737  	case types.TTYPEPARAM:
   738  		if t.Sym() == newsym {
   739  			// The substitution did not change the type.
   740  			return t
   741  		}
   742  		// Substitute the underlying typeparam (e.g. T in P[T], see
   743  		// the example describing type P[T] above).
   744  		newt = subst.typ(t.Underlying())
   745  		assert(newt != t)
   746  
   747  	case types.TARRAY:
   748  		elem := t.Elem()
   749  		newelem := subst.typ(elem)
   750  		if newelem != elem {
   751  			newt = types.NewArray(newelem, t.NumElem())
   752  		}
   753  
   754  	case types.TPTR:
   755  		elem := t.Elem()
   756  		newelem := subst.typ(elem)
   757  		if newelem != elem {
   758  			newt = types.NewPtr(newelem)
   759  		}
   760  
   761  	case types.TSLICE:
   762  		elem := t.Elem()
   763  		newelem := subst.typ(elem)
   764  		if newelem != elem {
   765  			newt = types.NewSlice(newelem)
   766  		}
   767  
   768  	case types.TSTRUCT:
   769  		newt = subst.tstruct(t, false)
   770  		if newt == t {
   771  			newt = nil
   772  		}
   773  
   774  	case types.TFUNC:
   775  		newrecvs := subst.tstruct(t.Recvs(), false)
   776  		newparams := subst.tstruct(t.Params(), false)
   777  		newresults := subst.tstruct(t.Results(), false)
   778  		if newrecvs != t.Recvs() || newparams != t.Params() || newresults != t.Results() {
   779  			// If any types have changed, then the all the fields of
   780  			// of recv, params, and results must be copied, because they have
   781  			// offset fields that are dependent, and so must have an
   782  			// independent copy for each new signature.
   783  			var newrecv *types.Field
   784  			if newrecvs.NumFields() > 0 {
   785  				if newrecvs == t.Recvs() {
   786  					newrecvs = subst.tstruct(t.Recvs(), true)
   787  				}
   788  				newrecv = newrecvs.Field(0)
   789  			}
   790  			if newparams == t.Params() {
   791  				newparams = subst.tstruct(t.Params(), true)
   792  			}
   793  			if newresults == t.Results() {
   794  				newresults = subst.tstruct(t.Results(), true)
   795  			}
   796  			newt = types.NewSignature(t.Pkg(), newrecv, t.TParams().FieldSlice(), newparams.FieldSlice(), newresults.FieldSlice())
   797  		}
   798  
   799  	case types.TINTER:
   800  		newt = subst.tinter(t)
   801  		if newt == t {
   802  			newt = nil
   803  		}
   804  
   805  	case types.TMAP:
   806  		newkey := subst.typ(t.Key())
   807  		newval := subst.typ(t.Elem())
   808  		if newkey != t.Key() || newval != t.Elem() {
   809  			newt = types.NewMap(newkey, newval)
   810  		}
   811  
   812  	case types.TCHAN:
   813  		elem := t.Elem()
   814  		newelem := subst.typ(elem)
   815  		if newelem != elem {
   816  			newt = types.NewChan(newelem, t.ChanDir())
   817  			if !newt.HasTParam() {
   818  				// TODO(danscales): not sure why I have to do this
   819  				// only for channels.....
   820  				types.CheckSize(newt)
   821  			}
   822  		}
   823  	}
   824  	if newt == nil {
   825  		// Even though there were typeparams in the type, there may be no
   826  		// change if this is a function type for a function call (which will
   827  		// have its own tparams/targs in the function instantiation).
   828  		return t
   829  	}
   830  
   831  	if t.Sym() == nil {
   832  		// Not a named type, so there was no forwarding type and there are
   833  		// no methods to substitute.
   834  		assert(t.Methods().Len() == 0)
   835  		return newt
   836  	}
   837  
   838  	forw.SetUnderlying(newt)
   839  	newt = forw
   840  
   841  	if t.Kind() != types.TINTER && t.Methods().Len() > 0 {
   842  		// Fill in the method info for the new type.
   843  		var newfields []*types.Field
   844  		newfields = make([]*types.Field, t.Methods().Len())
   845  		for i, f := range t.Methods().Slice() {
   846  			t2 := subst.typ(f.Type)
   847  			oldsym := f.Nname.Sym()
   848  			newsym := makeInstName(oldsym, subst.targs, true)
   849  			var nname *ir.Name
   850  			if newsym.Def != nil {
   851  				nname = newsym.Def.(*ir.Name)
   852  			} else {
   853  				nname = ir.NewNameAt(f.Pos, newsym)
   854  				nname.SetType(t2)
   855  				newsym.Def = nname
   856  			}
   857  			newfields[i] = types.NewField(f.Pos, f.Sym, t2)
   858  			newfields[i].Nname = nname
   859  		}
   860  		newt.Methods().Set(newfields)
   861  		if !newt.HasTParam() {
   862  			// Generate all the methods for a new fully-instantiated type.
   863  			subst.g.instTypeList = append(subst.g.instTypeList, newt)
   864  		}
   865  	}
   866  	return newt
   867  }
   868  
   869  // fields sets the Nname field for the Field nodes inside a type signature, based
   870  // on the corresponding in/out parameters in dcl. It depends on the in and out
   871  // parameters being in order in dcl.
   872  func (subst *subster) fields(class ir.Class, oldfields []*types.Field, dcl []*ir.Name) []*types.Field {
   873  	// Find the starting index in dcl of declarations of the class (either
   874  	// PPARAM or PPARAMOUT).
   875  	var i int
   876  	for i = range dcl {
   877  		if dcl[i].Class == class {
   878  			break
   879  		}
   880  	}
   881  
   882  	// Create newfields nodes that are copies of the oldfields nodes, but
   883  	// with substitution for any type params, and with Nname set to be the node in
   884  	// Dcl for the corresponding PPARAM or PPARAMOUT.
   885  	newfields := make([]*types.Field, len(oldfields))
   886  	for j := range oldfields {
   887  		newfields[j] = oldfields[j].Copy()
   888  		newfields[j].Type = subst.typ(oldfields[j].Type)
   889  		// A param field will be missing from dcl if its name is
   890  		// unspecified or specified as "_". So, we compare the dcl sym
   891  		// with the field sym. If they don't match, this dcl (if there is
   892  		// one left) must apply to a later field.
   893  		if i < len(dcl) && dcl[i].Sym() == oldfields[j].Sym {
   894  			newfields[j].Nname = dcl[i]
   895  			i++
   896  		}
   897  	}
   898  	return newfields
   899  }
   900  
   901  // defer does a single defer of type t, if it is a pointer type.
   902  func deref(t *types.Type) *types.Type {
   903  	if t.IsPtr() {
   904  		return t.Elem()
   905  	}
   906  	return t
   907  }
   908  
   909  // newIncompleteNamedType returns a TFORW type t with name specified by sym, such
   910  // that t.nod and sym.Def are set correctly.
   911  func newIncompleteNamedType(pos src.XPos, sym *types.Sym) *types.Type {
   912  	name := ir.NewDeclNameAt(pos, ir.OTYPE, sym)
   913  	forw := types.NewNamed(name)
   914  	name.SetType(forw)
   915  	sym.Def = name
   916  	return forw
   917  }
   918  

View as plain text