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