callee.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package inline
     6  
     7  // This file defines the analysis of the callee function.
     8  
     9  import (
    10  	"bytes"
    11  	"encoding/gob"
    12  	"fmt"
    13  	"go/ast"
    14  	"go/parser"
    15  	"go/token"
    16  	"go/types"
    17  	"slices"
    18  	"strings"
    19  
    20  	"golang.org/x/tools/go/types/typeutil"
    21  	"golang.org/x/tools/internal/astutil"
    22  	"golang.org/x/tools/internal/typeparams"
    23  	"golang.org/x/tools/internal/typesinternal"
    24  )
    25  
    26  // A Callee holds information about an inlinable function. Gob-serializable.
    27  type Callee struct {
    28  	impl gobCallee
    29  }
    30  
    31  func (callee *Callee) String() string { return callee.impl.Name }
    32  
    33  type gobCallee struct {
    34  	Content []byte // file content, compacted to a single func decl
    35  
    36  	// results of type analysis (does not reach go/types data structures)
    37  	PkgPath          string                 // package path of declaring package
    38  	Name             string                 // user-friendly name for error messages
    39  	GoVersion        string                 // version of Go effective in callee file
    40  	Unexported       []string               // names of free objects that are unexported
    41  	FreeRefs         []freeRef              // locations of references to free objects
    42  	FreeObjs         []object               // descriptions of free objects
    43  	ValidForCallStmt bool                   // function body is "return expr" where expr is f() or <-ch
    44  	NumResults       int                    // number of results (according to type, not ast.FieldList)
    45  	Params           []*paramInfo           // information about parameters (incl. receiver)
    46  	TypeParams       []*paramInfo           // information about type parameters
    47  	Results          []*paramInfo           // information about result variables
    48  	Effects          []int                  // order in which parameters are evaluated (see calleefx)
    49  	HasDefer         bool                   // uses defer
    50  	HasBareReturn    bool                   // uses bare return in non-void function
    51  	Returns          [][]returnOperandFlags // metadata about result expressions for each return
    52  	Labels           []string               // names of all control labels
    53  	Falcon           falconResult           // falcon constraint system
    54  }
    55  
    56  // returnOperandFlags records metadata about a single result expression in a return
    57  // statement.
    58  type returnOperandFlags int
    59  
    60  const (
    61  	nonTrivialResult returnOperandFlags = 1 << iota // return operand has non-trivial conversion to result type
    62  	untypedNilResult                                // return operand is nil literal
    63  )
    64  
    65  // A freeRef records a reference to a free object. Gob-serializable.
    66  // (This means free relative to the FuncDecl as a whole, i.e. excluding parameters.)
    67  type freeRef struct {
    68  	Offset int // byte offset of the reference relative to the FuncDecl
    69  	Object int // index into Callee.freeObjs
    70  }
    71  
    72  // An object abstracts a free types.Object referenced by the callee. Gob-serializable.
    73  type object struct {
    74  	Name    string // Object.Name()
    75  	Kind    string // one of {var,func,const,type,pkgname,nil,builtin}
    76  	PkgPath string // path of object's package (or imported package if kind="pkgname")
    77  	PkgName string // name of object's package (or imported package if kind="pkgname")
    78  	// TODO(rfindley): should we also track LocalPkgName here? Do we want to
    79  	// preserve the local package name?
    80  	ValidPos bool      // Object.Pos().IsValid()
    81  	Shadow   shadowMap // shadowing info for the object's refs
    82  }
    83  
    84  // AnalyzeCallee analyzes a function that is a candidate for inlining
    85  // and returns a Callee that describes it. The Callee object, which is
    86  // serializable, can be passed to one or more subsequent calls to
    87  // Inline, each with a different Caller.
    88  //
    89  // This design allows separate analysis of callers and callees in the
    90  // golang.org/x/tools/go/analysis framework: the inlining information
    91  // about a callee can be recorded as a "fact".
    92  //
    93  // The content should be the actual input to the compiler, not the
    94  // apparent source file according to any //line directives that
    95  // may be present within it.
    96  func AnalyzeCallee(logf func(string, ...any), fset *token.FileSet, pkg *types.Package, info *types.Info, decl *ast.FuncDecl, content []byte) (*Callee, error) {
    97  	checkInfoFields(info)
    98  
    99  	// The client is expected to have determined that the callee
   100  	// is a function with a declaration (not a built-in or var).
   101  	fn := info.Defs[decl.Name].(*types.Func)
   102  	sig := fn.Type().(*types.Signature)
   103  
   104  	logf("analyzeCallee %v @ %v", fn, fset.PositionFor(decl.Pos(), false))
   105  
   106  	// Create user-friendly name ("pkg.Func" or "(pkg.T).Method")
   107  	var name string
   108  	if sig.Recv() == nil {
   109  		name = fmt.Sprintf("%s.%s", fn.Pkg().Name(), fn.Name())
   110  	} else {
   111  		name = fmt.Sprintf("(%s).%s", types.TypeString(sig.Recv().Type(), (*types.Package).Name), fn.Name())
   112  	}
   113  
   114  	if decl.Body == nil {
   115  		return nil, fmt.Errorf("cannot inline function %s as it has no body", name)
   116  	}
   117  
   118  	// Record the file's Go goVersion so that we don't
   119  	// inline newer code into file using an older dialect.
   120  	//
   121  	// Using the file version is overly conservative.
   122  	// A more precise solution would be for the type checker to
   123  	// record which language features the callee actually needs;
   124  	// see https://go.dev/issue/75726.
   125  	//
   126  	// We don't have the ast.File handy, so instead of a
   127  	// lookup we must scan the entire FileVersions map.
   128  	var goVersion string
   129  	for file, v := range info.FileVersions {
   130  		if file.Pos() < decl.Pos() && decl.Pos() < file.End() {
   131  			goVersion = v
   132  			break
   133  		}
   134  	}
   135  
   136  	// Record the location of all free references in the FuncDecl.
   137  	// (Parameters are not free by this definition.)
   138  	var (
   139  		fieldObjs    = fieldObjs(sig)
   140  		freeObjIndex = make(map[types.Object]int)
   141  		freeObjs     []object
   142  		freeRefs     []freeRef // free refs that may need renaming
   143  		unexported   []string  // free refs to unexported objects, for later error checks
   144  	)
   145  	var f func(n ast.Node, stack []ast.Node) bool
   146  	var stack []ast.Node
   147  	stack = append(stack, decl.Type) // for scope of function itself
   148  	visit := func(n ast.Node, stack []ast.Node) { astutil.PreorderStack(n, stack, f) }
   149  	f = func(n ast.Node, stack []ast.Node) bool {
   150  		switch n := n.(type) {
   151  		case *ast.SelectorExpr:
   152  			// Check selections of free fields/methods.
   153  			if sel, ok := info.Selections[n]; ok &&
   154  				!within(sel.Obj().Pos(), decl) &&
   155  				!n.Sel.IsExported() {
   156  				sym := fmt.Sprintf("(%s).%s", info.TypeOf(n.X), n.Sel.Name)
   157  				unexported = append(unexported, sym)
   158  			}
   159  
   160  			// Don't recur into SelectorExpr.Sel.
   161  			visit(n.X, stack)
   162  			return false
   163  
   164  		case *ast.CompositeLit:
   165  			// Check for struct literals that refer to unexported fields,
   166  			// whether keyed or unkeyed. (Logic assumes well-typedness.)
   167  			litType := typeparams.Deref(info.TypeOf(n))
   168  			if s, ok := typeparams.CoreType(litType).(*types.Struct); ok {
   169  				if n.Type != nil {
   170  					visit(n.Type, stack)
   171  				}
   172  				for i, elt := range n.Elts {
   173  					var field *types.Var
   174  					var value ast.Expr
   175  					if kv, ok := elt.(*ast.KeyValueExpr); ok {
   176  						field = info.Uses[kv.Key.(*ast.Ident)].(*types.Var)
   177  						value = kv.Value
   178  					} else {
   179  						field = s.Field(i)
   180  						value = elt
   181  					}
   182  					if !within(field.Pos(), decl) && !field.Exported() {
   183  						sym := fmt.Sprintf("(%s).%s", litType, field.Name())
   184  						unexported = append(unexported, sym)
   185  					}
   186  
   187  					// Don't recur into KeyValueExpr.Key.
   188  					visit(value, stack)
   189  				}
   190  				return false
   191  			}
   192  
   193  		case *ast.Ident:
   194  			if obj, ok := info.Uses[n]; ok {
   195  				// Methods and fields are handled by SelectorExpr and CompositeLit.
   196  				if isField(obj) || isMethod(obj) {
   197  					panic(obj)
   198  				}
   199  				// Inv: id is a lexical reference.
   200  
   201  				// A reference to an unexported package-level declaration
   202  				// cannot be inlined into another package.
   203  				if !n.IsExported() &&
   204  					obj.Pkg() != nil && obj.Parent() == obj.Pkg().Scope() {
   205  					unexported = append(unexported, n.Name)
   206  				}
   207  
   208  				// Record free reference (incl. self-reference).
   209  				if obj == fn || !within(obj.Pos(), decl) {
   210  					objidx, ok := freeObjIndex[obj]
   211  					if !ok {
   212  						objidx = len(freeObjIndex)
   213  						var pkgPath, pkgName string
   214  						if pn, ok := obj.(*types.PkgName); ok {
   215  							pkgPath = pn.Imported().Path()
   216  							pkgName = pn.Imported().Name()
   217  						} else if obj.Pkg() != nil {
   218  							pkgPath = obj.Pkg().Path()
   219  							pkgName = obj.Pkg().Name()
   220  						}
   221  						freeObjs = append(freeObjs, object{
   222  							Name:     obj.Name(),
   223  							Kind:     objectKind(obj),
   224  							PkgName:  pkgName,
   225  							PkgPath:  pkgPath,
   226  							ValidPos: obj.Pos().IsValid(),
   227  						})
   228  						freeObjIndex[obj] = objidx
   229  					}
   230  
   231  					freeObjs[objidx].Shadow = freeObjs[objidx].Shadow.add(info, fieldObjs, obj.Name(), stack)
   232  
   233  					freeRefs = append(freeRefs, freeRef{
   234  						Offset: int(n.Pos() - decl.Pos()),
   235  						Object: objidx,
   236  					})
   237  				}
   238  			}
   239  		}
   240  		return true
   241  	}
   242  	visit(decl, stack)
   243  
   244  	// Analyze callee body for "return expr" form,
   245  	// where expr is f() or <-ch. These forms are
   246  	// safe to inline as a standalone statement.
   247  	validForCallStmt := false
   248  	if len(decl.Body.List) != 1 {
   249  		// not just a return statement
   250  	} else if ret, ok := decl.Body.List[0].(*ast.ReturnStmt); ok && len(ret.Results) == 1 {
   251  		validForCallStmt = func() bool {
   252  			switch expr := ast.Unparen(ret.Results[0]).(type) {
   253  			case *ast.CallExpr: // f(x)
   254  				callee := typeutil.Callee(info, expr)
   255  				if callee == nil {
   256  					return false // conversion T(x)
   257  				}
   258  
   259  				// The only non-void built-in functions that may be
   260  				// called as a statement are copy and recover
   261  				// (though arguably a call to recover should never
   262  				// be inlined as that changes its behavior).
   263  				if builtin, ok := callee.(*types.Builtin); ok {
   264  					return builtin.Name() == "copy" ||
   265  						builtin.Name() == "recover"
   266  				}
   267  
   268  				return true // ordinary call f()
   269  
   270  			case *ast.UnaryExpr: // <-x
   271  				return expr.Op == token.ARROW // channel receive <-ch
   272  			}
   273  
   274  			// No other expressions are valid statements.
   275  			return false
   276  		}()
   277  	}
   278  
   279  	// Record information about control flow in the callee
   280  	// (but not any nested functions).
   281  	var (
   282  		hasDefer      = false
   283  		hasBareReturn = false
   284  		returnInfo    [][]returnOperandFlags
   285  		labels        []string
   286  	)
   287  	ast.Inspect(decl.Body, func(n ast.Node) bool {
   288  		switch n := n.(type) {
   289  		case *ast.FuncLit:
   290  			return false // prune traversal
   291  		case *ast.DeferStmt:
   292  			hasDefer = true
   293  		case *ast.LabeledStmt:
   294  			labels = append(labels, n.Label.Name)
   295  		case *ast.ReturnStmt:
   296  
   297  			// Are implicit assignment conversions
   298  			// to result variables all trivial?
   299  			var resultInfo []returnOperandFlags
   300  			if len(n.Results) > 0 {
   301  				argInfo := func(i int) (ast.Expr, types.Type) {
   302  					expr := n.Results[i]
   303  					return expr, info.TypeOf(expr)
   304  				}
   305  				if len(n.Results) == 1 && sig.Results().Len() > 1 {
   306  					// Spread return: return f() where f.Results > 1.
   307  					tuple := info.TypeOf(n.Results[0]).(*types.Tuple)
   308  					argInfo = func(i int) (ast.Expr, types.Type) {
   309  						return nil, tuple.At(i).Type()
   310  					}
   311  				}
   312  				for i := range sig.Results().Len() {
   313  					expr, typ := argInfo(i)
   314  					var flags returnOperandFlags
   315  					if typ == types.Typ[types.UntypedNil] { // untyped nil is preserved by go/types
   316  						flags |= untypedNilResult
   317  					}
   318  					if !trivialConversion(info.Types[expr].Value, typ, sig.Results().At(i).Type()) {
   319  						flags |= nonTrivialResult
   320  					}
   321  					resultInfo = append(resultInfo, flags)
   322  				}
   323  			} else if sig.Results().Len() > 0 {
   324  				hasBareReturn = true
   325  			}
   326  			returnInfo = append(returnInfo, resultInfo)
   327  		}
   328  		return true
   329  	})
   330  
   331  	// Reject attempts to inline cgo-generated functions.
   332  	for _, obj := range freeObjs {
   333  		// There are others (iconst fconst sconst fpvar macro)
   334  		// but this is probably sufficient.
   335  		if strings.HasPrefix(obj.Name, "_Cfunc_") ||
   336  			strings.HasPrefix(obj.Name, "_Ctype_") ||
   337  			strings.HasPrefix(obj.Name, "_Cvar_") {
   338  			return nil, fmt.Errorf("cannot inline cgo-generated functions")
   339  		}
   340  	}
   341  
   342  	// Compact content to just the FuncDecl.
   343  	//
   344  	// As a space optimization, we don't retain the complete
   345  	// callee file content; all we need is "package _; func f() { ... }".
   346  	// This reduces the size of analysis facts.
   347  	//
   348  	// Offsets in the callee information are "relocatable"
   349  	// since they are all relative to the FuncDecl.
   350  
   351  	content = append([]byte("package _\n"),
   352  		content[offsetOf(fset, decl.Pos()):offsetOf(fset, decl.End())]...)
   353  	// Sanity check: re-parse the compacted content.
   354  	if _, _, err := parseCompact(content); err != nil {
   355  		return nil, err
   356  	}
   357  
   358  	params, results, effects, falcon := analyzeParams(logf, fset, info, decl)
   359  	tparams := analyzeTypeParams(logf, fset, info, decl)
   360  	return &Callee{gobCallee{
   361  		Content:          content,
   362  		PkgPath:          pkg.Path(),
   363  		Name:             name,
   364  		GoVersion:        goVersion,
   365  		Unexported:       unexported,
   366  		FreeObjs:         freeObjs,
   367  		FreeRefs:         freeRefs,
   368  		ValidForCallStmt: validForCallStmt,
   369  		NumResults:       sig.Results().Len(),
   370  		Params:           params,
   371  		TypeParams:       tparams,
   372  		Results:          results,
   373  		Effects:          effects,
   374  		HasDefer:         hasDefer,
   375  		HasBareReturn:    hasBareReturn,
   376  		Returns:          returnInfo,
   377  		Labels:           labels,
   378  		Falcon:           falcon,
   379  	}}, nil
   380  }
   381  
   382  // parseCompact parses a Go source file of the form "package _\n func f() { ... }"
   383  // and returns the sole function declaration.
   384  func parseCompact(content []byte) (*token.FileSet, *ast.FuncDecl, error) {
   385  	fset := token.NewFileSet()
   386  	const mode = parser.ParseComments | parser.SkipObjectResolution | parser.AllErrors
   387  	f, err := parser.ParseFile(fset, "callee.go", content, mode)
   388  	if err != nil {
   389  		return nil, nil, fmt.Errorf("internal error: cannot compact file: %v", err)
   390  	}
   391  	return fset, f.Decls[0].(*ast.FuncDecl), nil
   392  }
   393  
   394  // A paramInfo records information about a callee receiver, parameter, or result variable.
   395  type paramInfo struct {
   396  	Name        string    // parameter name (may be blank, or even "")
   397  	Index       int       // index within signature
   398  	IsResult    bool      // false for receiver or parameter, true for result variable
   399  	IsInterface bool      // parameter has a (non-type parameter) interface type
   400  	Assigned    bool      // parameter appears on left side of an assignment statement
   401  	Escapes     bool      // parameter has its address taken
   402  	Refs        []refInfo // information about references to parameter within body
   403  	Shadow      shadowMap // shadowing info for the above refs; see [shadowMap]
   404  	FalconType  string    // name of this parameter's type (if basic) in the falcon system
   405  }
   406  
   407  type refInfo struct {
   408  	Offset           int  // FuncDecl-relative byte offset of parameter ref within body
   409  	Assignable       bool // ref appears in context of assignment to known type
   410  	IfaceAssignment  bool // ref is being assigned to an interface
   411  	AffectsInference bool // ref type may affect type inference
   412  	// IsSelectionOperand indicates whether the parameter reference is the
   413  	// operand of a selection (param.f). If so, and param's argument is itself
   414  	// a receiver parameter (a common case), we don't need to desugar (&v or *ptr)
   415  	// the selection: if param.Method is a valid selection, then so is param.fieldOrMethod.
   416  	IsSelectionOperand bool
   417  }
   418  
   419  // analyzeParams computes information about parameters of the function declared by decl,
   420  // including a simple "address taken" escape analysis.
   421  //
   422  // It returns two new arrays, one of the receiver and parameters, and
   423  // the other of the result variables of the function.
   424  //
   425  // The input must be well-typed.
   426  func analyzeParams(logf func(string, ...any), fset *token.FileSet, info *types.Info, decl *ast.FuncDecl) (params, results []*paramInfo, effects []int, _ falconResult) {
   427  	sig := signature(fset, info, decl)
   428  
   429  	paramInfos := make(map[*types.Var]*paramInfo)
   430  	{
   431  		newParamInfo := func(param *types.Var, isResult bool) *paramInfo {
   432  			info := &paramInfo{
   433  				Name:        param.Name(),
   434  				IsResult:    isResult,
   435  				Index:       len(paramInfos),
   436  				IsInterface: isNonTypeParamInterface(param.Type()),
   437  			}
   438  			paramInfos[param] = info
   439  			return info
   440  		}
   441  		if sig.Recv() != nil {
   442  			params = append(params, newParamInfo(sig.Recv(), false))
   443  		}
   444  		for v := range sig.Params().Variables() {
   445  			params = append(params, newParamInfo(v, false))
   446  		}
   447  		for v := range sig.Results().Variables() {
   448  			results = append(results, newParamInfo(v, true))
   449  		}
   450  	}
   451  
   452  	// Search function body for operations &x, x.f(), and x = y
   453  	// where x is a parameter, and record it.
   454  	escape(info, decl, func(v *types.Var, escapes bool) {
   455  		if info := paramInfos[v]; info != nil {
   456  			if escapes {
   457  				info.Escapes = true
   458  			} else {
   459  				info.Assigned = true
   460  			}
   461  		}
   462  	})
   463  
   464  	// Record locations of all references to parameters.
   465  	// And record the set of intervening definitions for each parameter.
   466  	//
   467  	// TODO(adonovan): combine this traversal with the one that computes
   468  	// FreeRefs. The tricky part is that calleefx needs this one first.
   469  	fieldObjs := fieldObjs(sig)
   470  	var stack []ast.Node
   471  	stack = append(stack, decl.Type) // for scope of function itself
   472  	astutil.PreorderStack(decl.Body, stack, func(n ast.Node, stack []ast.Node) bool {
   473  		if id, ok := n.(*ast.Ident); ok {
   474  			if v, ok := info.Uses[id].(*types.Var); ok {
   475  				if pinfo, ok := paramInfos[v]; ok {
   476  					// Record ref information, and any intervening (shadowing) names.
   477  					//
   478  					// If the parameter v has an interface type, and the reference id
   479  					// appears in a context where assignability rules apply, there may be
   480  					// an implicit interface-to-interface widening. In that case it is
   481  					// not necessary to insert an explicit conversion from the argument
   482  					// to the parameter's type.
   483  					//
   484  					// Contrapositively, if param is not an interface type, then the
   485  					// assignment may lose type information, for example in the case that
   486  					// the substituted expression is an untyped constant or unnamed type.
   487  					stack = append(stack, n) // (the two calls below want n)
   488  					assignable, ifaceAssign, affectsInference := analyzeAssignment(info, stack)
   489  					ref := refInfo{
   490  						Offset:             int(n.Pos() - decl.Pos()),
   491  						Assignable:         assignable,
   492  						IfaceAssignment:    ifaceAssign,
   493  						AffectsInference:   affectsInference,
   494  						IsSelectionOperand: isSelectionOperand(stack),
   495  					}
   496  					pinfo.Refs = append(pinfo.Refs, ref)
   497  					pinfo.Shadow = pinfo.Shadow.add(info, fieldObjs, pinfo.Name, stack)
   498  				}
   499  			}
   500  		}
   501  		return true
   502  	})
   503  
   504  	// Compute subset and order of parameters that are strictly evaluated.
   505  	// (Depends on Refs computed above.)
   506  	effects = calleefx(info, decl.Body, paramInfos)
   507  	logf("effects list = %v", effects)
   508  
   509  	falcon := falcon(logf, fset, paramInfos, info, decl)
   510  
   511  	return params, results, effects, falcon
   512  }
   513  
   514  // analyzeTypeParams computes information about the type parameters of the function declared by decl.
   515  func analyzeTypeParams(_ logger, fset *token.FileSet, info *types.Info, decl *ast.FuncDecl) []*paramInfo {
   516  	sig := signature(fset, info, decl)
   517  	paramInfos := make(map[*types.TypeName]*paramInfo)
   518  	var params []*paramInfo
   519  	collect := func(tpl *types.TypeParamList) {
   520  		for tparam := range tpl.TypeParams() {
   521  			typeName := tparam.Obj()
   522  			info := &paramInfo{Name: typeName.Name()}
   523  			params = append(params, info)
   524  			paramInfos[typeName] = info
   525  		}
   526  	}
   527  	collect(sig.RecvTypeParams())
   528  	collect(sig.TypeParams())
   529  
   530  	// Find references.
   531  	// We don't care about most of the properties that matter for parameter references:
   532  	// a type is immutable, cannot have its address taken, and does not undergo conversions.
   533  	// TODO(jba): can we nevertheless combine this with the traversal in analyzeParams?
   534  	var stack []ast.Node
   535  	stack = append(stack, decl.Type) // for scope of function itself
   536  	astutil.PreorderStack(decl.Body, stack, func(n ast.Node, stack []ast.Node) bool {
   537  		if id, ok := n.(*ast.Ident); ok {
   538  			if v, ok := info.Uses[id].(*types.TypeName); ok {
   539  				if pinfo, ok := paramInfos[v]; ok {
   540  					ref := refInfo{Offset: int(n.Pos() - decl.Pos())}
   541  					pinfo.Refs = append(pinfo.Refs, ref)
   542  					pinfo.Shadow = pinfo.Shadow.add(info, nil, pinfo.Name, stack)
   543  				}
   544  			}
   545  		}
   546  		return true
   547  	})
   548  	return params
   549  }
   550  
   551  func signature(fset *token.FileSet, info *types.Info, decl *ast.FuncDecl) *types.Signature {
   552  	fnobj, ok := info.Defs[decl.Name]
   553  	if !ok {
   554  		panic(fmt.Sprintf("%s: no func object for %q",
   555  			fset.PositionFor(decl.Name.Pos(), false), decl.Name)) // ill-typed?
   556  	}
   557  	return fnobj.Type().(*types.Signature)
   558  }
   559  
   560  // -- callee helpers --
   561  
   562  // analyzeAssignment looks at the given stack, and analyzes certain
   563  // attributes of the innermost expression.
   564  //
   565  // In all cases we 'fail closed' when we cannot detect (or for simplicity
   566  // choose not to detect) the condition in question, meaning we err on the side
   567  // of the more restrictive rule. This is noted for each result below.
   568  //
   569  //   - assignable reports whether the expression is used in a position where
   570  //     assignability rules apply, such as in an actual assignment, as call
   571  //     argument, or in a send to a channel. Defaults to 'false'. If assignable
   572  //     is false, the other two results are irrelevant.
   573  //   - ifaceAssign reports whether that assignment is to an interface type.
   574  //     This is important as we want to preserve the concrete type in that
   575  //     assignment. Defaults to 'true'. Notably, if the assigned type is a type
   576  //     parameter, we assume that it could have interface type.
   577  //   - affectsInference is (somewhat vaguely) defined as whether or not the
   578  //     type of the operand may affect the type of the surrounding syntax,
   579  //     through type inference. It is infeasible to completely reverse engineer
   580  //     type inference, so we over approximate: if the expression is an argument
   581  //     to a call to a generic function (but not method!) that uses type
   582  //     parameters, assume that unification of that argument may affect the
   583  //     inferred types.
   584  func analyzeAssignment(info *types.Info, stack []ast.Node) (assignable, ifaceAssign, affectsInference bool) {
   585  	remaining, parent, expr := exprContext(stack)
   586  	if parent == nil {
   587  		return false, false, false
   588  	}
   589  
   590  	// TODO(golang/go#70638): simplify when types.Info records implicit conversions.
   591  
   592  	// Types do not need to match for assignment to a variable.
   593  	if assign, ok := parent.(*ast.AssignStmt); ok {
   594  		for i, v := range assign.Rhs {
   595  			if v == expr {
   596  				if i >= len(assign.Lhs) {
   597  					return false, false, false // ill typed
   598  				}
   599  				// Check to see if the assignment is to an interface type.
   600  				if i < len(assign.Lhs) {
   601  					// TODO: We could handle spread calls here, but in current usage expr
   602  					// is an ident.
   603  					if id, _ := assign.Lhs[i].(*ast.Ident); id != nil && info.Defs[id] != nil {
   604  						// Types must match for a defining identifier in a short variable
   605  						// declaration.
   606  						return false, false, false
   607  					}
   608  					// In all other cases, types should be known.
   609  					typ := info.TypeOf(assign.Lhs[i])
   610  					return true, typ == nil || types.IsInterface(typ), false
   611  				}
   612  				// Default:
   613  				return assign.Tok == token.ASSIGN, true, false
   614  			}
   615  		}
   616  	}
   617  
   618  	// Types do not need to match for an initializer with known type.
   619  	if spec, ok := parent.(*ast.ValueSpec); ok && spec.Type != nil {
   620  		if slices.Contains(spec.Values, expr) {
   621  			typ := info.TypeOf(spec.Type)
   622  			return true, typ == nil || types.IsInterface(typ), false
   623  		}
   624  	}
   625  
   626  	// Types do not need to match for index expressions.
   627  	if ix, ok := parent.(*ast.IndexExpr); ok {
   628  		if ix.Index == expr {
   629  			typ := info.TypeOf(ix.X)
   630  			if typ == nil {
   631  				return true, true, false
   632  			}
   633  			m, _ := typeparams.CoreType(typ).(*types.Map)
   634  			return true, m == nil || types.IsInterface(m.Key()), false
   635  		}
   636  	}
   637  
   638  	// Types do not need to match for composite literal keys, values, or
   639  	// fields.
   640  	if kv, ok := parent.(*ast.KeyValueExpr); ok {
   641  		var under types.Type
   642  		if len(remaining) > 0 {
   643  			if complit, ok := remaining[len(remaining)-1].(*ast.CompositeLit); ok {
   644  				if typ := info.TypeOf(complit); typ != nil {
   645  					// Unpointer to allow for pointers to slices or arrays, which are
   646  					// permitted as the types of nested composite literals without a type
   647  					// name.
   648  					under = typesinternal.Unpointer(typeparams.CoreType(typ))
   649  				}
   650  			}
   651  		}
   652  		if kv.Key == expr { // M{expr: ...}: assign to map key
   653  			m, _ := under.(*types.Map)
   654  			return true, m == nil || types.IsInterface(m.Key()), false
   655  		}
   656  		if kv.Value == expr {
   657  			switch under := under.(type) {
   658  			case interface{ Elem() types.Type }: // T{...: expr}: assign to map/array/slice element
   659  				return true, types.IsInterface(under.Elem()), false
   660  			case *types.Struct: // Struct{k: expr}
   661  				if id, _ := kv.Key.(*ast.Ident); id != nil {
   662  					for field := range under.Fields() {
   663  						if info.Uses[id] == field {
   664  							return true, types.IsInterface(field.Type()), false
   665  						}
   666  					}
   667  				}
   668  			default:
   669  				return true, true, false
   670  			}
   671  		}
   672  	}
   673  	if lit, ok := parent.(*ast.CompositeLit); ok {
   674  		for i, v := range lit.Elts {
   675  			if v == expr {
   676  				typ := info.TypeOf(lit)
   677  				if typ == nil {
   678  					return true, true, false
   679  				}
   680  				// As in the KeyValueExpr case above, unpointer to handle pointers to
   681  				// array/slice literals.
   682  				under := typesinternal.Unpointer(typeparams.CoreType(typ))
   683  				switch under := under.(type) {
   684  				case interface{ Elem() types.Type }: // T{expr}: assign to map/array/slice element
   685  					return true, types.IsInterface(under.Elem()), false
   686  				case *types.Struct: // Struct{expr}: assign to unkeyed struct field
   687  					if i < under.NumFields() {
   688  						return true, types.IsInterface(under.Field(i).Type()), false
   689  					}
   690  				}
   691  				return true, true, false
   692  			}
   693  		}
   694  	}
   695  
   696  	// Types do not need to match for values sent to a channel.
   697  	if send, ok := parent.(*ast.SendStmt); ok {
   698  		if send.Value == expr {
   699  			typ := info.TypeOf(send.Chan)
   700  			if typ == nil {
   701  				return true, true, false
   702  			}
   703  			ch, _ := typeparams.CoreType(typ).(*types.Chan)
   704  			return true, ch == nil || types.IsInterface(ch.Elem()), false
   705  		}
   706  	}
   707  
   708  	// Types do not need to match for an argument to a call, unless the
   709  	// corresponding parameter has type parameters, as in that case the
   710  	// argument type may affect inference.
   711  	if call, ok := parent.(*ast.CallExpr); ok {
   712  		if _, ok := isConversion(info, call); ok {
   713  			return false, false, false // redundant conversions are handled at the call site
   714  		}
   715  		// Ordinary call. Could be a call of a func, builtin, or function value.
   716  		for i, arg := range call.Args {
   717  			if arg == expr {
   718  				typ := info.TypeOf(call.Fun)
   719  				if typ == nil {
   720  					return true, true, false
   721  				}
   722  				sig, _ := typeparams.CoreType(typ).(*types.Signature)
   723  				if sig != nil {
   724  					// Find the relevant parameter type, accounting for variadics.
   725  					paramType := paramTypeAtIndex(sig, call, i)
   726  					ifaceAssign := paramType == nil || types.IsInterface(paramType)
   727  					affectsInference := false
   728  					switch callee := typeutil.Callee(info, call).(type) {
   729  					case *types.Builtin:
   730  						// Consider this litmus test:
   731  						//
   732  						//   func f(x int64) any { return max(x) }
   733  						//   func main() { fmt.Printf("%T", f(42)) }
   734  						//
   735  						// If we lose the implicit conversion from untyped int
   736  						// to int64, the type inferred for the max(x) call changes,
   737  						// resulting in a different dynamic behavior: it prints
   738  						// int, not int64.
   739  						//
   740  						// Inferred result type affected:
   741  						//    new
   742  						//    complex, real, imag
   743  						//    min, max
   744  						//
   745  						// Dynamic behavior change:
   746  						//    append         -- dynamic type of append([]any(nil), x)[0]
   747  						//    delete(m, x)   -- dynamic key type where m is map[any]unit
   748  						//    panic          -- dynamic type of panic value
   749  						//
   750  						// Unaffected:
   751  						//    recover
   752  						//    make
   753  						//    len, cap
   754  						//    clear
   755  						//    close
   756  						//    copy
   757  						//    print, println  -- only uses underlying types (?)
   758  						//
   759  						// The dynamic type cases are all covered by
   760  						// the ifaceAssign logic.
   761  						switch callee.Name() {
   762  						case "new", "complex", "real", "imag", "min", "max":
   763  							affectsInference = true
   764  						}
   765  
   766  					case *types.Func:
   767  						// Only standalone (non-method) functions have type
   768  						// parameters affected by the call arguments.
   769  						if sig2 := callee.Signature(); sig2.Recv() == nil {
   770  							originParamType := paramTypeAtIndex(sig2, call, i)
   771  							affectsInference = originParamType == nil || new(typeparams.Free).Has(originParamType)
   772  						}
   773  					}
   774  					return true, ifaceAssign, affectsInference
   775  				}
   776  			}
   777  		}
   778  	}
   779  
   780  	return false, false, false
   781  }
   782  
   783  // paramTypeAtIndex returns the effective parameter type at the given argument
   784  // index in call, if valid.
   785  func paramTypeAtIndex(sig *types.Signature, call *ast.CallExpr, index int) types.Type {
   786  	if plen := sig.Params().Len(); sig.Variadic() && index >= plen-1 && !call.Ellipsis.IsValid() {
   787  		if s, ok := sig.Params().At(plen - 1).Type().(*types.Slice); ok {
   788  			return s.Elem()
   789  		}
   790  	} else if index < plen {
   791  		return sig.Params().At(index).Type()
   792  	}
   793  	return nil // ill typed
   794  }
   795  
   796  // exprContext returns the innermost parent->child expression nodes for the
   797  // given outer-to-inner stack, after stripping parentheses, along with the
   798  // remaining stack up to the parent node.
   799  //
   800  // If no such context exists, returns (nil, nil, nil).
   801  func exprContext(stack []ast.Node) (remaining []ast.Node, parent ast.Node, expr ast.Expr) {
   802  	expr, _ = stack[len(stack)-1].(ast.Expr)
   803  	if expr == nil {
   804  		return nil, nil, nil
   805  	}
   806  	i := len(stack) - 2
   807  	for ; i >= 0; i-- {
   808  		if pexpr, ok := stack[i].(*ast.ParenExpr); ok {
   809  			expr = pexpr
   810  		} else {
   811  			parent = stack[i]
   812  			break
   813  		}
   814  	}
   815  	if parent == nil {
   816  		return nil, nil, nil
   817  	}
   818  	// inv: i is the index of parent in the stack.
   819  	return stack[:i], parent, expr
   820  }
   821  
   822  // isSelectionOperand reports whether the innermost node of stack is operand
   823  // (x) of a selection x.f.
   824  func isSelectionOperand(stack []ast.Node) bool {
   825  	_, parent, expr := exprContext(stack)
   826  	if parent == nil {
   827  		return false
   828  	}
   829  	sel, ok := parent.(*ast.SelectorExpr)
   830  	return ok && sel.X == expr
   831  }
   832  
   833  // A shadowMap records information about shadowing at any of the parameter's
   834  // references within the callee decl.
   835  //
   836  // For each name shadowed at a reference to the parameter within the callee
   837  // body, shadow map records the 1-based index of the callee decl parameter
   838  // causing the shadowing, or -1, if the shadowing is not due to a callee decl.
   839  // A value of zero (or missing) indicates no shadowing. By convention,
   840  // self-shadowing is excluded from the map.
   841  //
   842  // For example, in the following callee
   843  //
   844  //	func f(a, b int) int {
   845  //		c := 2 + b
   846  //		return a + c
   847  //	}
   848  //
   849  // the shadow map of a is {b: 2, c: -1}, because b is shadowed by the 2nd
   850  // parameter. The shadow map of b is {a: 1}, because c is not shadowed at the
   851  // use of b.
   852  type shadowMap map[string]int
   853  
   854  // add returns the [shadowMap] augmented by the set of names
   855  // locally shadowed at the location of the reference in the callee
   856  // (identified by the stack). The name of the reference itself is
   857  // excluded.
   858  //
   859  // These shadowed names may not be used in a replacement expression
   860  // for the reference.
   861  func (s shadowMap) add(info *types.Info, paramIndexes map[types.Object]int, exclude string, stack []ast.Node) shadowMap {
   862  	for _, n := range stack {
   863  		if scope := scopeFor(info, n); scope != nil {
   864  			for _, name := range scope.Names() {
   865  				if name != exclude {
   866  					if s == nil {
   867  						s = make(shadowMap)
   868  					}
   869  					obj := scope.Lookup(name)
   870  					if idx, ok := paramIndexes[obj]; ok {
   871  						s[name] = idx + 1
   872  					} else {
   873  						s[name] = -1
   874  					}
   875  				}
   876  			}
   877  		}
   878  	}
   879  	return s
   880  }
   881  
   882  // fieldObjs returns a map of each types.Object defined by the given signature
   883  // to its index in the parameter list. Parameters with missing or blank name
   884  // are skipped.
   885  func fieldObjs(sig *types.Signature) map[types.Object]int {
   886  	m := make(map[types.Object]int)
   887  	for i := range sig.Params().Len() {
   888  		if p := sig.Params().At(i); p.Name() != "" && p.Name() != "_" {
   889  			m[p] = i
   890  		}
   891  	}
   892  	return m
   893  }
   894  
   895  func isField(obj types.Object) bool {
   896  	if v, ok := obj.(*types.Var); ok && v.IsField() {
   897  		return true
   898  	}
   899  	return false
   900  }
   901  
   902  func isMethod(obj types.Object) bool {
   903  	if f, ok := obj.(*types.Func); ok && f.Type().(*types.Signature).Recv() != nil {
   904  		return true
   905  	}
   906  	return false
   907  }
   908  
   909  // -- serialization --
   910  
   911  var (
   912  	_ gob.GobEncoder = (*Callee)(nil)
   913  	_ gob.GobDecoder = (*Callee)(nil)
   914  )
   915  
   916  func (callee *Callee) GobEncode() ([]byte, error) {
   917  	var out bytes.Buffer
   918  	if err := gob.NewEncoder(&out).Encode(callee.impl); err != nil {
   919  		return nil, err
   920  	}
   921  	return out.Bytes(), nil
   922  }
   923  
   924  func (callee *Callee) GobDecode(data []byte) error {
   925  	return gob.NewDecoder(bytes.NewReader(data)).Decode(&callee.impl)
   926  }
   927
View as plain text