Source file src/cmd/vendor/golang.org/x/tools/internal/refactor/inline/inline.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  import (
     8  	"bytes"
     9  	"fmt"
    10  	"go/ast"
    11  	"go/constant"
    12  	"go/format"
    13  	"go/parser"
    14  	"go/token"
    15  	"go/types"
    16  	"maps"
    17  	pathpkg "path"
    18  	"reflect"
    19  	"slices"
    20  	"strings"
    21  
    22  	"golang.org/x/tools/go/ast/astutil"
    23  	"golang.org/x/tools/go/types/typeutil"
    24  	internalastutil "golang.org/x/tools/internal/astutil"
    25  	"golang.org/x/tools/internal/astutil/free"
    26  	"golang.org/x/tools/internal/packagepath"
    27  	"golang.org/x/tools/internal/refactor"
    28  	"golang.org/x/tools/internal/typeparams"
    29  	"golang.org/x/tools/internal/typesinternal"
    30  	"golang.org/x/tools/internal/versions"
    31  )
    32  
    33  // A Caller describes the function call and its enclosing context.
    34  //
    35  // The client is responsible for populating this struct and passing it to Inline.
    36  type Caller struct {
    37  	Fset  *token.FileSet
    38  	Types *types.Package
    39  	Info  *types.Info
    40  	File  *ast.File
    41  	Call  *ast.CallExpr
    42  
    43  	// CountUses is an optional optimized computation of
    44  	// the number of times pkgname appears in Info.Uses.
    45  	CountUses func(pkgname *types.PkgName) int
    46  
    47  	path          []ast.Node    // path from call to root of file syntax tree
    48  	enclosingFunc *ast.FuncDecl // top-level function/method enclosing the call, if any
    49  }
    50  
    51  type logger = func(string, ...any)
    52  
    53  // Options specifies parameters affecting the inliner algorithm.
    54  // All fields are optional.
    55  type Options struct {
    56  	Logf          logger // log output function, records decision-making process
    57  	IgnoreEffects bool   // ignore potential side effects of arguments (unsound)
    58  }
    59  
    60  // Result holds the result of code transformation.
    61  type Result struct {
    62  	Edits       []refactor.Edit // edits around CallExpr and imports
    63  	Literalized bool            // chosen strategy replaced callee() with func(){...}()
    64  	BindingDecl bool            // transformation added "var params = args" declaration
    65  }
    66  
    67  // Inline inlines the called function (callee) into the function call (caller)
    68  // and returns the updated, formatted content of the caller source file.
    69  //
    70  // Inline does not mutate any public fields of Caller or Callee.
    71  func Inline(caller *Caller, callee *Callee, opts *Options) (*Result, error) {
    72  	copy := *opts // shallow copy
    73  	opts = &copy
    74  	// Set default options.
    75  	if opts.Logf == nil {
    76  		opts.Logf = func(string, ...any) {}
    77  	}
    78  
    79  	st := &state{
    80  		caller: caller,
    81  		callee: callee,
    82  		opts:   opts,
    83  	}
    84  	return st.inline()
    85  }
    86  
    87  // state holds the working state of the inliner.
    88  type state struct {
    89  	caller *Caller
    90  	callee *Callee
    91  	opts   *Options
    92  }
    93  
    94  func (st *state) inline() (*Result, error) {
    95  	logf, caller, callee := st.opts.Logf, st.caller, st.callee
    96  
    97  	logf("inline %s @ %v",
    98  		debugFormatNode(caller.Fset, caller.Call),
    99  		caller.Fset.PositionFor(caller.Call.Lparen, false))
   100  
   101  	if ast.IsGenerated(caller.File) {
   102  		return nil, fmt.Errorf("cannot inline calls from generated files")
   103  	}
   104  
   105  	res, err := st.inlineCall()
   106  	if err != nil {
   107  		return nil, err
   108  	}
   109  
   110  	// Replace the call (or some node that encloses it) by new syntax.
   111  	assert(res.old != nil, "old is nil")
   112  	assert(res.new != nil, "new is nil")
   113  
   114  	// A single return operand inlined to a unary
   115  	// expression context may need parens. Otherwise:
   116  	//    func two() int { return 1+1 }
   117  	//    print(-two())  =>  print(-1+1) // oops!
   118  	//
   119  	// Usually it is not necessary to insert ParenExprs
   120  	// as the formatter is smart enough to insert them as
   121  	// needed by the context. But the res.{old,new}
   122  	// substitution is done by formatting res.new in isolation
   123  	// and then splicing its text over res.old, so the
   124  	// formatter doesn't see the parent node and cannot do
   125  	// the right thing. (One solution would be to always
   126  	// format the enclosing node of old, but that requires
   127  	// non-lossy comment handling, #20744.)
   128  	//
   129  	// So, we must analyze the call's context
   130  	// to see whether ambiguity is possible.
   131  	// For example, if the context is x[y:z], then
   132  	// the x subtree is subject to precedence ambiguity
   133  	// (replacing x by p+q would give p+q[y:z] which is wrong)
   134  	// but the y and z subtrees are safe.
   135  	if new, ok := res.new.(ast.Expr); ok {
   136  		parent := caller.path[slices.Index(caller.path, res.old)+1]
   137  		res.new = internalastutil.MaybeParenthesize(parent, res.old.(ast.Expr), new)
   138  	}
   139  
   140  	// Some reduction strategies return a new block holding the
   141  	// callee's statements. The block's braces may be elided when
   142  	// there is no conflict between names declared in the block
   143  	// with those declared by the parent block, and no risk of
   144  	// a caller's goto jumping forward across a declaration.
   145  	//
   146  	// This elision is only safe when the ExprStmt is beneath a
   147  	// BlockStmt, CaseClause.Body, or CommClause.Body;
   148  	// (see "statement theory").
   149  	//
   150  	// The inlining analysis may have already determined that eliding braces is
   151  	// safe. Otherwise, we analyze its safety here.
   152  	elideBraces := res.elideBraces
   153  	if !elideBraces {
   154  		if newBlock, ok := res.new.(*ast.BlockStmt); ok {
   155  			i := slices.Index(caller.path, res.old)
   156  			parent := caller.path[i+1]
   157  			var body []ast.Stmt
   158  			switch parent := parent.(type) {
   159  			case *ast.BlockStmt:
   160  				body = parent.List
   161  			case *ast.CommClause:
   162  				body = parent.Body
   163  			case *ast.CaseClause:
   164  				body = parent.Body
   165  			}
   166  			if body != nil {
   167  				callerNames := declares(body)
   168  
   169  				// If BlockStmt is a function body,
   170  				// include its receiver, params, and results.
   171  				addFieldNames := func(fields *ast.FieldList) {
   172  					if fields != nil {
   173  						for _, field := range fields.List {
   174  							for _, id := range field.Names {
   175  								callerNames[id.Name] = true
   176  							}
   177  						}
   178  					}
   179  				}
   180  				switch f := caller.path[i+2].(type) {
   181  				case *ast.FuncDecl:
   182  					addFieldNames(f.Recv)
   183  					addFieldNames(f.Type.Params)
   184  					addFieldNames(f.Type.Results)
   185  				case *ast.FuncLit:
   186  					addFieldNames(f.Type.Params)
   187  					addFieldNames(f.Type.Results)
   188  				}
   189  
   190  				if len(callerLabels(caller.path)) > 0 {
   191  					// TODO(adonovan): be more precise and reject
   192  					// only forward gotos across the inlined block.
   193  					logf("keeping block braces: caller uses control labels")
   194  				} else if intersects(declares(newBlock.List), callerNames) {
   195  					logf("keeping block braces: avoids name conflict")
   196  				} else {
   197  					elideBraces = true
   198  				}
   199  			}
   200  		}
   201  	}
   202  
   203  	var edits []refactor.Edit
   204  
   205  	// Format the cloned callee.
   206  	{
   207  		// TODO(adonovan): might it make more sense to use
   208  		// callee.Fset when formatting res.new?
   209  		// The new tree is a mix of (cloned) caller nodes for
   210  		// the argument expressions and callee nodes for the
   211  		// function body. In essence the question is: which
   212  		// is more likely to have comments?
   213  		// Usually the callee body will be larger and more
   214  		// statement-heavy than the arguments, but a
   215  		// strategy may widen the scope of the replacement
   216  		// (res.old) from CallExpr to, say, its enclosing
   217  		// block, so the caller nodes dominate.
   218  		// Precise comment handling would make this a
   219  		// non-issue. Formatting wouldn't really need a
   220  		// FileSet at all.
   221  
   222  		var out bytes.Buffer
   223  		if elideBraces {
   224  			for i, stmt := range res.new.(*ast.BlockStmt).List {
   225  				if i > 0 {
   226  					out.WriteByte('\n')
   227  				}
   228  				if err := format.Node(&out, caller.Fset, stmt); err != nil {
   229  					return nil, err
   230  				}
   231  			}
   232  		} else {
   233  			if err := format.Node(&out, caller.Fset, res.new); err != nil {
   234  				return nil, err
   235  			}
   236  		}
   237  
   238  		edits = append(edits, refactor.Edit{
   239  			Pos:     res.old.Pos(),
   240  			End:     res.old.End(),
   241  			NewText: out.Bytes(),
   242  		})
   243  	}
   244  
   245  	// Add new imports.
   246  	//
   247  	// It's possible that not all are needed (e.g. for type names
   248  	// that melted away), but we'll let the client (such as an
   249  	// analysis driver) clean it up since it must remove unused
   250  	// imports anyway.
   251  	for _, imp := range res.newImports {
   252  		// Check that the new imports are accessible.
   253  		if !packagepath.CanImport(caller.Types.Path(), imp.path) {
   254  			return nil, fmt.Errorf("can't inline function %v as its body refers to inaccessible package %q", callee, imp.path)
   255  		}
   256  
   257  		// We've already validated the import, so we call
   258  		// AddImportEdits directly to compute the edit.
   259  		name := ""
   260  		if imp.explicit {
   261  			name = imp.name
   262  		}
   263  		edits = append(edits, refactor.AddImportEdits(caller.File, name, imp.path)...)
   264  	}
   265  
   266  	literalized := false
   267  	if call, ok := res.new.(*ast.CallExpr); ok && is[*ast.FuncLit](call.Fun) {
   268  		literalized = true
   269  	}
   270  
   271  	// Delete imports referenced only by caller.Call.Fun.
   272  	//
   273  	// It's ambiguous to let the client (e.g. analysis driver)
   274  	// remove unneeded imports in this case because it is common
   275  	// to inlining a call from "dir1/a".F to "dir2/a".F, which
   276  	// leaves two imports of packages named 'a', both providing a.F.
   277  	//
   278  	// However, the only two import deletion tools at our disposal
   279  	// are astutil.DeleteNamedImport, which mutates the AST, and
   280  	// refactor.Delete{Spec,Decl}, which need a Cursor. So we need
   281  	// to reinvent the wheel here.
   282  	for _, oldImport := range res.oldImports {
   283  		spec := oldImport.spec
   284  
   285  		// Include adjacent comments.
   286  		pos := spec.Pos()
   287  		if doc := spec.Doc; doc != nil {
   288  			pos = doc.Pos()
   289  		}
   290  		end := spec.End()
   291  		if doc := spec.Comment; doc != nil {
   292  			end = doc.End()
   293  		}
   294  
   295  		// Find the enclosing import decl.
   296  		// If it's paren-less, we must delete it too.
   297  		for _, decl := range caller.File.Decls {
   298  			decl, ok := decl.(*ast.GenDecl)
   299  			if !(ok && decl.Tok == token.IMPORT) {
   300  				break // stop at first non-import decl
   301  			}
   302  			if internalastutil.NodeContainsPos(decl, spec.Pos()) && !decl.Rparen.IsValid() {
   303  				// Include adjacent comments.
   304  				pos = decl.Pos()
   305  				if doc := decl.Doc; doc != nil {
   306  					pos = doc.Pos()
   307  				}
   308  				end = decl.End()
   309  				break
   310  			}
   311  		}
   312  
   313  		edits = append(edits, refactor.Edit{
   314  			Pos: pos,
   315  			End: end,
   316  		})
   317  	}
   318  
   319  	return &Result{
   320  		Edits:       edits,
   321  		Literalized: literalized,
   322  		BindingDecl: res.bindingDecl,
   323  	}, nil
   324  }
   325  
   326  // An oldImport is an import that will be deleted from the caller file.
   327  type oldImport struct {
   328  	pkgName *types.PkgName
   329  	spec    *ast.ImportSpec
   330  }
   331  
   332  // A newImport is an import that will be added to the caller file.
   333  type newImport struct {
   334  	name     string
   335  	path     string
   336  	explicit bool // use name as ImportSpec.Name
   337  }
   338  
   339  // importState tracks information about imports.
   340  type importState struct {
   341  	logf       func(string, ...any)
   342  	caller     *Caller
   343  	importMap  map[string][]string // from package paths in the caller's file to local names
   344  	newImports []newImport         // for references to free names in callee; to be added to the file
   345  	oldImports []oldImport         // referenced only by caller.Call.Fun; to be removed from the file
   346  }
   347  
   348  // newImportState returns an importState with initial information about the caller's imports.
   349  func newImportState(logf func(string, ...any), caller *Caller, callee *gobCallee) *importState {
   350  	// For simplicity we ignore existing dot imports, so that a qualified
   351  	// identifier (QI) in the callee is always represented by a QI in the caller,
   352  	// allowing us to treat a QI like a selection on a package name.
   353  	ist := &importState{
   354  		logf:      logf,
   355  		caller:    caller,
   356  		importMap: make(map[string][]string),
   357  	}
   358  
   359  	// Provide an inefficient default implementation of CountUses.
   360  	// (Ideally clients amortize this for the entire package.)
   361  	countUses := caller.CountUses
   362  	if countUses == nil {
   363  		uses := make(map[*types.PkgName]int)
   364  		for _, obj := range caller.Info.Uses {
   365  			if pkgname, ok := obj.(*types.PkgName); ok {
   366  				uses[pkgname]++
   367  			}
   368  		}
   369  		countUses = func(pkgname *types.PkgName) int {
   370  			return uses[pkgname]
   371  		}
   372  	}
   373  
   374  	for _, imp := range caller.File.Imports {
   375  		if pkgName, ok := importedPkgName(caller.Info, imp); ok &&
   376  			pkgName.Name() != "." &&
   377  			pkgName.Name() != "_" {
   378  
   379  			// If the import's sole use is in caller.Call.Fun of the form p.F(...),
   380  			// where p.F is a qualified identifier, the p import may not be
   381  			// necessary.
   382  			//
   383  			// Only the qualified identifier case matters, as other references to
   384  			// imported package names in the Call.Fun expression (e.g.
   385  			// x.after(3*time.Second).f() or time.Second.String()) will remain after
   386  			// inlining, as arguments.
   387  			//
   388  			// If that is the case, proactively check if any of the callee FreeObjs
   389  			// need this import. Doing so eagerly simplifies the resulting logic.
   390  			needed := true
   391  			if sel, ok := ast.Unparen(caller.Call.Fun).(*ast.SelectorExpr); ok &&
   392  				is[*ast.Ident](sel.X) &&
   393  				caller.Info.Uses[sel.X.(*ast.Ident)] == pkgName &&
   394  				countUses(pkgName) == 1 {
   395  				needed = false // no longer needed by caller
   396  				// Check to see if any of the inlined free objects need this package.
   397  				for _, obj := range callee.FreeObjs {
   398  					if obj.PkgPath == pkgName.Imported().Path() && obj.Shadow[pkgName.Name()] == 0 {
   399  						needed = true // needed by callee
   400  						break
   401  					}
   402  				}
   403  			}
   404  
   405  			// Exclude imports not needed by the caller or callee after inlining; the second
   406  			// return value holds these.
   407  			if needed {
   408  				path := pkgName.Imported().Path()
   409  				ist.importMap[path] = append(ist.importMap[path], pkgName.Name())
   410  			} else {
   411  				ist.oldImports = append(ist.oldImports, oldImport{pkgName: pkgName, spec: imp})
   412  			}
   413  		}
   414  	}
   415  	return ist
   416  }
   417  
   418  // importName finds an existing import name to use in a particular shadowing
   419  // context. It is used to determine the set of new imports in
   420  // localName, and is also used for writing out names in inlining
   421  // strategies below.
   422  func (i *importState) importName(pkgPath string, shadow shadowMap) string {
   423  	for _, name := range i.importMap[pkgPath] {
   424  		// Check that either the import preexisted, or that it was newly added
   425  		// (no PkgName) but is not shadowed, either in the callee (shadows) or
   426  		// caller (caller.lookup).
   427  		if shadow[name] == 0 {
   428  			found := i.caller.lookup(name)
   429  			if is[*types.PkgName](found) || found == nil {
   430  				return name
   431  			}
   432  		}
   433  	}
   434  	return ""
   435  }
   436  
   437  // findNewLocalName returns a new local package name to use in a particular shadowing context.
   438  // It considers the existing local name used by the callee, or construct a new local name
   439  // based on the package name.
   440  func (i *importState) findNewLocalName(pkgName, calleePkgName string, shadow shadowMap) string {
   441  	newlyAdded := func(name string) bool {
   442  		return slices.ContainsFunc(i.newImports, func(n newImport) bool { return n.name == name })
   443  	}
   444  
   445  	// shadowedInCaller reports whether a candidate package name
   446  	// already refers to a declaration in the caller.
   447  	shadowedInCaller := func(name string) bool {
   448  		obj := i.caller.lookup(name)
   449  		if obj == nil {
   450  			return false
   451  		}
   452  		// If obj will be removed, the name is available.
   453  		return !slices.ContainsFunc(i.oldImports, func(o oldImport) bool { return o.pkgName == obj })
   454  	}
   455  
   456  	// import added by callee
   457  	//
   458  	// Try to preserve the local package name used by the callee first.
   459  	//
   460  	// If that is shadowed, choose a local package name based on last segment of
   461  	// package path plus, if needed, a numeric suffix to ensure uniqueness.
   462  	//
   463  	// "init" is not a legal PkgName.
   464  	if shadow[calleePkgName] == 0 && !shadowedInCaller(calleePkgName) && !newlyAdded(calleePkgName) && calleePkgName != "init" {
   465  		return calleePkgName
   466  	}
   467  
   468  	base := pkgName
   469  	name := base
   470  	for n := 0; shadow[name] != 0 || shadowedInCaller(name) || newlyAdded(name) || name == "init"; n++ {
   471  		name = fmt.Sprintf("%s%d", base, n)
   472  	}
   473  
   474  	return name
   475  }
   476  
   477  // localName returns the local name for a given imported package path,
   478  // adding one if it doesn't exists.
   479  func (i *importState) localName(pkgPath, pkgName, calleePkgName string, shadow shadowMap) string {
   480  	// Does an import already exist that works in this shadowing context?
   481  	if name := i.importName(pkgPath, shadow); name != "" {
   482  		return name
   483  	}
   484  
   485  	name := i.findNewLocalName(pkgName, calleePkgName, shadow)
   486  	i.logf("adding import %s %q", name, pkgPath)
   487  	// Use explicit pkgname (out of necessity) when it differs from the declared name,
   488  	// or (for good style) when it differs from base(pkgpath).
   489  	i.newImports = append(i.newImports, newImport{
   490  		name:     name,
   491  		path:     pkgPath,
   492  		explicit: name != pkgName || name != pathpkg.Base(pkgPath),
   493  	})
   494  	i.importMap[pkgPath] = append(i.importMap[pkgPath], name)
   495  	return name
   496  }
   497  
   498  type inlineCallResult struct {
   499  	newImports []newImport // to add
   500  	oldImports []oldImport // to remove
   501  
   502  	// If elideBraces is set, old is an ast.Stmt and new is an ast.BlockStmt to
   503  	// be spliced in. This allows the inlining analysis to assert that inlining
   504  	// the block is OK; if elideBraces is unset and old is an ast.Stmt and new is
   505  	// an ast.BlockStmt, braces may still be elided if the post-processing
   506  	// analysis determines that it is safe to do so.
   507  	//
   508  	// Ideally, it would not be necessary for the inlining analysis to "reach
   509  	// through" to the post-processing pass in this way. Instead, inlining could
   510  	// just set old to be an ast.BlockStmt and rewrite the entire BlockStmt, but
   511  	// unfortunately in order to preserve comments, it is important that inlining
   512  	// replace as little syntax as possible.
   513  	elideBraces bool
   514  	bindingDecl bool     // transformation inserted "var params = args" declaration
   515  	old, new    ast.Node // e.g. replace call expr by callee function body expression
   516  }
   517  
   518  // inlineCall returns a pair of an old node (the call, or something
   519  // enclosing it) and a new node (its replacement, which may be a
   520  // combination of caller, callee, and new nodes), along with the set
   521  // of new imports needed.
   522  //
   523  // TODO(adonovan): rethink the 'result' interface. The assumption of a
   524  // one-to-one replacement seems fragile. One can easily imagine the
   525  // transformation replacing the call and adding new variable
   526  // declarations, for example, or replacing a call statement by zero or
   527  // many statements.)
   528  // NOTE(rfindley): we've sort-of done this, with the 'elideBraces' flag that
   529  // allows inlining a statement list. However, due to loss of comments, more
   530  // sophisticated rewrites are challenging.
   531  //
   532  // TODO(rfindley): see if we can reduce the amount of comment lossiness by
   533  // using printer.CommentedNode, which has been useful elsewhere.
   534  //
   535  // TODO(rfindley): inlineCall is getting very long, and very stateful, making
   536  // it very hard to read. The following refactoring may improve readability and
   537  // maintainability:
   538  //   - Rename 'state' to 'callsite', since that is what it encapsulates.
   539  //   - Add results of pre-processing analysis into the callsite struct, such as
   540  //     the effective importMap, new/old imports, arguments, etc. Essentially
   541  //     anything that resulted from initial analysis of the call site, and which
   542  //     may be useful to inlining strategies.
   543  //   - Delegate this call site analysis to a constructor or initializer, such
   544  //     as 'analyzeCallsite', so that it does not consume bandwidth in the
   545  //     'inlineCall' logical flow.
   546  //   - Once analyzeCallsite returns, the callsite is immutable, much in the
   547  //     same way as the Callee and Caller are immutable.
   548  //   - Decide on a standard interface for strategies (and substrategies), such
   549  //     that they may be delegated to a separate method on callsite.
   550  //
   551  // In this way, the logical flow of inline call will clearly follow the
   552  // following structure:
   553  //  1. Analyze the call site.
   554  //  2. Try strategies, in order, until one succeeds.
   555  //  3. Process the results.
   556  //
   557  // If any expensive analysis may be avoided by earlier strategies, it can be
   558  // encapsulated in its own type and passed to subsequent strategies.
   559  func (st *state) inlineCall() (*inlineCallResult, error) {
   560  	logf, caller, callee := st.opts.Logf, st.caller, &st.callee.impl
   561  
   562  	checkInfoFields(caller.Info)
   563  
   564  	// Inlining of dynamic calls is not currently supported,
   565  	// even for local closure calls. (This would be a lot of work.)
   566  	calleeSymbol := typeutil.StaticCallee(caller.Info, caller.Call)
   567  	if calleeSymbol == nil {
   568  		// e.g. interface method
   569  		return nil, fmt.Errorf("cannot inline: not a static function call")
   570  	}
   571  
   572  	// Reject cross-package inlining if callee has
   573  	// free references to unexported symbols.
   574  	samePkg := caller.Types.Path() == callee.PkgPath
   575  	if !samePkg && len(callee.Unexported) > 0 {
   576  		return nil, fmt.Errorf("cannot inline call to %s because body refers to non-exported %s",
   577  			callee.Name, callee.Unexported[0])
   578  	}
   579  
   580  	// Reject cross-file inlining if callee requires a newer dialect of Go (#75726).
   581  	// (Versions default to types.Config.GoVersion, which is unset in many tests,
   582  	// though should be populated by an analysis driver.)
   583  	callerGoVersion := caller.Info.FileVersions[caller.File]
   584  	if callerGoVersion != "" && callee.GoVersion != "" && versions.Before(callerGoVersion, callee.GoVersion) {
   585  		return nil, fmt.Errorf("cannot inline call to %s (declared using %s) into a file using %s",
   586  			callee.Name, callee.GoVersion, callerGoVersion)
   587  	}
   588  
   589  	// -- analyze callee's free references in caller context --
   590  
   591  	// Compute syntax path enclosing Call, innermost first (Path[0]=Call),
   592  	// and outermost enclosing function, if any.
   593  	caller.path, _ = astutil.PathEnclosingInterval(caller.File, caller.Call.Pos(), caller.Call.End())
   594  	for _, n := range caller.path {
   595  		if decl, ok := n.(*ast.FuncDecl); ok {
   596  			caller.enclosingFunc = decl
   597  			break
   598  		}
   599  	}
   600  
   601  	// If call is within a function, analyze all its
   602  	// local vars for the "single assignment" property.
   603  	// (Taking the address &v counts as a potential assignment.)
   604  	var assign1 func(v *types.Var) bool // reports whether v a single-assignment local var
   605  	{
   606  		updatedLocals := make(map[*types.Var]bool)
   607  		if caller.enclosingFunc != nil {
   608  			escape(caller.Info, caller.enclosingFunc, func(v *types.Var, _ bool) {
   609  				updatedLocals[v] = true
   610  			})
   611  			logf("multiple-assignment vars: %v", updatedLocals)
   612  		}
   613  		assign1 = func(v *types.Var) bool { return !updatedLocals[v] }
   614  	}
   615  
   616  	// Extract information about the caller's imports.
   617  	istate := newImportState(logf, caller, callee)
   618  
   619  	// Compute the renaming of the callee's free identifiers.
   620  	objRenames, err := st.renameFreeObjs(istate)
   621  	if err != nil {
   622  		return nil, err
   623  	}
   624  
   625  	res := &inlineCallResult{
   626  		newImports: istate.newImports,
   627  		oldImports: istate.oldImports,
   628  	}
   629  
   630  	// Parse callee function declaration.
   631  	calleeFset, calleeDecl, err := parseCompact(callee.Content)
   632  	if err != nil {
   633  		return nil, err // "can't happen"
   634  	}
   635  
   636  	// replaceCalleeID replaces an identifier in the callee. See [replacer] for
   637  	// more detailed semantics.
   638  	replaceCalleeID := func(offset int, repl ast.Expr, unpackVariadic bool) {
   639  		path, id := findIdent(calleeDecl, calleeDecl.Pos()+token.Pos(offset))
   640  		logf("- replace id %q @ #%d to %q", id.Name, offset, debugFormatNode(calleeFset, repl))
   641  		// Replace f([]T{a, b, c}...) with f(a, b, c).
   642  		if lit, ok := repl.(*ast.CompositeLit); ok && unpackVariadic && len(path) > 0 {
   643  			if call, ok := last(path).(*ast.CallExpr); ok &&
   644  				call.Ellipsis.IsValid() &&
   645  				id == last(call.Args) {
   646  
   647  				call.Args = append(call.Args[:len(call.Args)-1], lit.Elts...)
   648  				call.Ellipsis = token.NoPos
   649  				return
   650  			}
   651  		}
   652  		if len(path) > 0 {
   653  			repl = internalastutil.MaybeParenthesize(last(path), id, repl)
   654  		}
   655  		replaceNode(calleeDecl, id, repl)
   656  	}
   657  
   658  	// Generate replacements for each free identifier.
   659  	// (The same tree may be spliced in multiple times, resulting in a DAG.)
   660  	for _, ref := range callee.FreeRefs {
   661  		if repl := objRenames[ref.Object]; repl != nil {
   662  			replaceCalleeID(ref.Offset, repl, false)
   663  		}
   664  	}
   665  
   666  	// Gather the effective call arguments, including the receiver.
   667  	// Later, elements will be eliminated (=> nil) by parameter substitution.
   668  	args, err := st.arguments(caller, calleeDecl, assign1)
   669  	if err != nil {
   670  		return nil, err // e.g. implicit field selection cannot be made explicit
   671  	}
   672  
   673  	// Gather effective parameter tuple, including the receiver if any.
   674  	// Simplify variadic parameters to slices (in all cases but one).
   675  	var params []*parameter // including receiver; nil => parameter substituted
   676  	{
   677  		sig := calleeSymbol.Type().(*types.Signature)
   678  		if sig.Recv() != nil {
   679  			params = append(params, &parameter{
   680  				obj:       sig.Recv(),
   681  				fieldType: calleeDecl.Recv.List[0].Type,
   682  				info:      callee.Params[0],
   683  			})
   684  		}
   685  
   686  		// Flatten the list of syntactic types.
   687  		var types []ast.Expr
   688  		for _, field := range calleeDecl.Type.Params.List {
   689  			if field.Names == nil {
   690  				types = append(types, field.Type)
   691  			} else {
   692  				for range field.Names {
   693  					types = append(types, field.Type)
   694  				}
   695  			}
   696  		}
   697  
   698  		for i := 0; i < sig.Params().Len(); i++ {
   699  			params = append(params, &parameter{
   700  				obj:       sig.Params().At(i),
   701  				fieldType: types[i],
   702  				info:      callee.Params[len(params)],
   703  			})
   704  		}
   705  
   706  		// Variadic function?
   707  		//
   708  		// There are three possible types of call:
   709  		// - ordinary f(a1, ..., aN)
   710  		// - ellipsis f(a1, ..., slice...)
   711  		// - spread   f(recv?, g()) where g() is a tuple.
   712  		// The first two are desugared to non-variadic calls
   713  		// with an ordinary slice parameter;
   714  		// the third is tricky and cannot be reduced, and (if
   715  		// a receiver is present) cannot even be literalized.
   716  		// Fortunately it is vanishingly rare.
   717  		//
   718  		// TODO(adonovan): extract this to a function.
   719  		if sig.Variadic() {
   720  			lastParam := last(params)
   721  			if len(args) > 0 && last(args).spread {
   722  				// spread call to variadic: tricky
   723  				lastParam.variadic = true
   724  			} else {
   725  				// ordinary/ellipsis call to variadic
   726  
   727  				// simplify decl: func(T...) -> func([]T)
   728  				lastParamField := last(calleeDecl.Type.Params.List)
   729  				lastParamField.Type = &ast.ArrayType{
   730  					Elt: lastParamField.Type.(*ast.Ellipsis).Elt,
   731  				}
   732  
   733  				if caller.Call.Ellipsis.IsValid() {
   734  					// ellipsis call: f(slice...) -> f(slice)
   735  					// nop
   736  				} else {
   737  					// ordinary call: f(a1, ... aN) -> f([]T{a1, ..., aN})
   738  					//
   739  					// Substitution of []T{...} in the callee body may lead to
   740  					// g([]T{a1, ..., aN}...), which we simplify to g(a1, ..., an)
   741  					// later; see replaceCalleeID.
   742  					n := len(params) - 1
   743  					ordinary, extra := args[:n], args[n:]
   744  					var elts []ast.Expr
   745  					freevars := make(map[string]bool)
   746  					pure, effects := true, false
   747  					for _, arg := range extra {
   748  						elts = append(elts, arg.expr)
   749  						pure = pure && arg.pure
   750  						effects = effects || arg.effects
   751  						maps.Copy(freevars, arg.freevars)
   752  					}
   753  					args = append(ordinary, &argument{
   754  						expr: &ast.CompositeLit{
   755  							Type: lastParamField.Type,
   756  							Elts: elts,
   757  						},
   758  						typ:        lastParam.obj.Type(),
   759  						constant:   nil,
   760  						pure:       pure,
   761  						effects:    effects,
   762  						duplicable: false,
   763  						freevars:   freevars,
   764  						variadic:   true,
   765  					})
   766  				}
   767  			}
   768  		}
   769  	}
   770  
   771  	typeArgs := st.typeArguments(caller.Call)
   772  	if len(typeArgs) != len(callee.TypeParams) {
   773  		return nil, fmt.Errorf("cannot inline: type parameter inference is not yet supported")
   774  	}
   775  	if err := substituteTypeParams(logf, callee.TypeParams, typeArgs, params, replaceCalleeID); err != nil {
   776  		return nil, err
   777  	}
   778  
   779  	// Log effective arguments.
   780  	for i, arg := range args {
   781  		logf("arg #%d: %s pure=%t effects=%t duplicable=%t free=%v type=%v",
   782  			i, debugFormatNode(caller.Fset, arg.expr),
   783  			arg.pure, arg.effects, arg.duplicable, arg.freevars, arg.typ)
   784  	}
   785  
   786  	// Note: computation below should be expressed in terms of
   787  	// the args and params slices, not the raw material.
   788  
   789  	// Perform parameter substitution.
   790  	// May eliminate some elements of params/args.
   791  	substitute(logf, caller, params, args, callee.Effects, callee.Falcon, replaceCalleeID)
   792  
   793  	// Update the callee's signature syntax.
   794  	updateCalleeParams(calleeDecl, params)
   795  
   796  	// Create a var (param = arg; ...) decl for use by some strategies.
   797  	bindingDecl := createBindingDecl(logf, caller, args, calleeDecl, callee.Results)
   798  
   799  	var remainingArgs []ast.Expr
   800  	for _, arg := range args {
   801  		if arg != nil {
   802  			remainingArgs = append(remainingArgs, arg.expr)
   803  		}
   804  	}
   805  
   806  	// -- let the inlining strategies begin --
   807  	//
   808  	// When we commit to a strategy, we log a message of the form:
   809  	//
   810  	//   "strategy: reduce expr-context call to { return expr }"
   811  	//
   812  	// This is a terse way of saying:
   813  	//
   814  	//    we plan to reduce a call
   815  	//    that appears in expression context
   816  	//    to a function whose body is of the form { return expr }
   817  
   818  	// TODO(adonovan): split this huge function into a sequence of
   819  	// function calls with an error sentinel that means "try the
   820  	// next strategy", and make sure each strategy writes to the
   821  	// log the reason it didn't match.
   822  
   823  	// Special case: eliminate a call to a function whose body is empty.
   824  	// (=> callee has no results and caller is a statement.)
   825  	//
   826  	//    func f(params) {}
   827  	//    f(args)
   828  	//    => _, _ = args
   829  	//
   830  	if len(calleeDecl.Body.List) == 0 {
   831  		logf("strategy: reduce call to empty body")
   832  
   833  		// Evaluate the arguments for effects and delete the call entirely.
   834  		// Note(golang/go#71486): stmt can be nil if the call is in a go or defer
   835  		// statement.
   836  		// TODO: discard go or defer statements as well.
   837  		if stmt := callStmt(caller.path, false); stmt != nil {
   838  			res.old = stmt
   839  			if nargs := len(remainingArgs); nargs > 0 {
   840  				// Emit "_, _ = args" to discard results.
   841  
   842  				// TODO(adonovan): if args is the []T{a1, ..., an}
   843  				// literal synthesized during variadic simplification,
   844  				// consider unwrapping it to its (pure) elements.
   845  				// Perhaps there's no harm doing this for any slice literal.
   846  
   847  				// Make correction for spread calls
   848  				// f(g()) or recv.f(g()) where g() is a tuple.
   849  				if last := last(args); last != nil && last.spread {
   850  					nspread := last.typ.(*types.Tuple).Len()
   851  					if len(args) > 1 { // [recv, g()]
   852  						// A single AssignStmt cannot discard both, so use a 2-spec var decl.
   853  						res.new = &ast.GenDecl{
   854  							Tok: token.VAR,
   855  							Specs: []ast.Spec{
   856  								&ast.ValueSpec{
   857  									Names:  []*ast.Ident{makeIdent("_")},
   858  									Values: []ast.Expr{args[0].expr},
   859  								},
   860  								&ast.ValueSpec{
   861  									Names:  blanks[*ast.Ident](nspread),
   862  									Values: []ast.Expr{args[1].expr},
   863  								},
   864  							},
   865  						}
   866  						return res, nil
   867  					}
   868  
   869  					// Sole argument is spread call.
   870  					nargs = nspread
   871  				}
   872  
   873  				res.new = &ast.AssignStmt{
   874  					Lhs: blanks[ast.Expr](nargs),
   875  					Tok: token.ASSIGN,
   876  					Rhs: remainingArgs,
   877  				}
   878  
   879  			} else {
   880  				// No remaining arguments: delete call statement entirely
   881  				res.new = &ast.EmptyStmt{}
   882  			}
   883  			return res, nil
   884  		}
   885  	}
   886  
   887  	// If all parameters have been substituted and no result
   888  	// variable is referenced, we don't need a binding decl.
   889  	// This may enable better reduction strategies.
   890  	allResultsUnreferenced := forall(callee.Results, func(i int, r *paramInfo) bool { return len(r.Refs) == 0 })
   891  	needBindingDecl := !allResultsUnreferenced ||
   892  		exists(params, func(i int, p *parameter) bool { return p != nil })
   893  
   894  	// The two strategies below overlap for a tail call of {return exprs}:
   895  	// The expr-context reduction is nice because it keeps the
   896  	// caller's return stmt and merely switches its operand,
   897  	// without introducing a new block, but it doesn't work with
   898  	// implicit return conversions.
   899  	//
   900  	// TODO(adonovan): unify these cases more cleanly, allowing return-
   901  	// operand replacement and implicit conversions, by adding
   902  	// conversions around each return operand (if not a spread return).
   903  
   904  	// Special case: call to { return exprs }.
   905  	//
   906  	// Reduces to:
   907  	//	    { var (bindings); _, _ = exprs }
   908  	//     or   _, _ = exprs
   909  	//     or   expr
   910  	//
   911  	// If:
   912  	// - the body is just "return expr" with trivial implicit conversions,
   913  	//   or the caller's return type matches the callee's,
   914  	// - all parameters and result vars can be eliminated
   915  	//   or replaced by a binding decl,
   916  	// then the call expression can be replaced by the
   917  	// callee's body expression, suitably substituted.
   918  	if len(calleeDecl.Body.List) == 1 &&
   919  		is[*ast.ReturnStmt](calleeDecl.Body.List[0]) &&
   920  		len(calleeDecl.Body.List[0].(*ast.ReturnStmt).Results) > 0 { // not a bare return
   921  		results := calleeDecl.Body.List[0].(*ast.ReturnStmt).Results
   922  
   923  		parent, grandparent := callContext(caller.path)
   924  
   925  		// statement context
   926  		if stmt, ok := parent.(*ast.ExprStmt); ok &&
   927  			(!needBindingDecl || bindingDecl != nil) {
   928  			logf("strategy: reduce stmt-context call to { return exprs }")
   929  			clearPositions(calleeDecl.Body)
   930  
   931  			if callee.ValidForCallStmt {
   932  				logf("callee body is valid as statement")
   933  				// Inv: len(results) == 1
   934  				if !needBindingDecl {
   935  					// Reduces to: expr
   936  					res.old = caller.Call
   937  					res.new = results[0]
   938  				} else {
   939  					// Reduces to: { var (bindings); expr }
   940  					res.bindingDecl = true
   941  					res.old = stmt
   942  					res.new = &ast.BlockStmt{
   943  						List: []ast.Stmt{
   944  							bindingDecl.stmt,
   945  							&ast.ExprStmt{X: results[0]},
   946  						},
   947  					}
   948  				}
   949  			} else {
   950  				logf("callee body is not valid as statement")
   951  				// The call is a standalone statement, but the
   952  				// callee body is not suitable as a standalone statement
   953  				// (f() or <-ch), explicitly discard the results:
   954  				// Reduces to: _, _ = exprs
   955  				discard := &ast.AssignStmt{
   956  					Lhs: blanks[ast.Expr](callee.NumResults),
   957  					Tok: token.ASSIGN,
   958  					Rhs: results,
   959  				}
   960  				res.old = stmt
   961  				if !needBindingDecl {
   962  					// Reduces to: _, _ = exprs
   963  					res.new = discard
   964  				} else {
   965  					// Reduces to: { var (bindings); _, _ = exprs }
   966  					res.bindingDecl = true
   967  					res.new = &ast.BlockStmt{
   968  						List: []ast.Stmt{
   969  							bindingDecl.stmt,
   970  							discard,
   971  						},
   972  					}
   973  				}
   974  			}
   975  			return res, nil
   976  		}
   977  
   978  		// Assignment context.
   979  		//
   980  		// If there is no binding decl, or if the binding decl declares no names,
   981  		// an assignment a, b := f() can be reduced to a, b := x, y.
   982  		if stmt, ok := parent.(*ast.AssignStmt); ok &&
   983  			is[*ast.BlockStmt](grandparent) &&
   984  			(!needBindingDecl || (bindingDecl != nil && len(bindingDecl.names) == 0)) {
   985  
   986  			// Reduces to: { var (bindings); lhs... := rhs... }
   987  			if newStmts, ok := st.assignStmts(stmt, results, istate.importName); ok {
   988  				logf("strategy: reduce assign-context call to { return exprs }")
   989  
   990  				clearPositions(calleeDecl.Body)
   991  
   992  				block := &ast.BlockStmt{
   993  					List: newStmts,
   994  				}
   995  				if needBindingDecl {
   996  					res.bindingDecl = true
   997  					block.List = prepend(bindingDecl.stmt, block.List...)
   998  				}
   999  
  1000  				// assignStmts does not introduce new bindings, and replacing an
  1001  				// assignment only works if the replacement occurs in the same scope.
  1002  				// Therefore, we must ensure that braces are elided.
  1003  				res.elideBraces = true
  1004  				res.old = stmt
  1005  				res.new = block
  1006  				return res, nil
  1007  			}
  1008  		}
  1009  
  1010  		// expression context
  1011  		if !needBindingDecl {
  1012  			clearPositions(calleeDecl.Body)
  1013  
  1014  			anyNonTrivialReturns := hasNonTrivialReturn(callee.Returns)
  1015  
  1016  			if callee.NumResults == 1 {
  1017  				logf("strategy: reduce expr-context call to { return expr }")
  1018  				// (includes some simple tail-calls)
  1019  
  1020  				// Make implicit return conversion explicit.
  1021  				if anyNonTrivialReturns {
  1022  					results[0] = convert(calleeDecl.Type.Results.List[0].Type, results[0])
  1023  				}
  1024  
  1025  				res.old = caller.Call
  1026  				res.new = results[0]
  1027  				return res, nil
  1028  
  1029  			} else if !anyNonTrivialReturns {
  1030  				logf("strategy: reduce spread-context call to { return expr }")
  1031  				// There is no general way to reify conversions in a spread
  1032  				// return, hence the requirement above.
  1033  				//
  1034  				// TODO(adonovan): allow this reduction when no
  1035  				// conversion is required by the context.
  1036  
  1037  				// The call returns multiple results but is
  1038  				// not a standalone call statement. It must
  1039  				// be the RHS of a spread assignment:
  1040  				//   var x, y  = f()
  1041  				//       x, y := f()
  1042  				//       x, y  = f()
  1043  				// or the sole argument to a spread call:
  1044  				//        printf(f())
  1045  				// or spread return statement:
  1046  				//        return f()
  1047  				res.old = parent
  1048  				switch context := parent.(type) {
  1049  				case *ast.AssignStmt:
  1050  					// Inv: the call must be in Rhs[0], not Lhs.
  1051  					assign := shallowCopy(context)
  1052  					assign.Rhs = results
  1053  					res.new = assign
  1054  				case *ast.ValueSpec:
  1055  					// Inv: the call must be in Values[0], not Names.
  1056  					spec := shallowCopy(context)
  1057  					spec.Values = results
  1058  					res.new = spec
  1059  				case *ast.CallExpr:
  1060  					// Inv: the call must be in Args[0], not Fun.
  1061  					call := shallowCopy(context)
  1062  					call.Args = results
  1063  					res.new = call
  1064  				case *ast.ReturnStmt:
  1065  					// Inv: the call must be Results[0].
  1066  					ret := shallowCopy(context)
  1067  					ret.Results = results
  1068  					res.new = ret
  1069  				default:
  1070  					return nil, fmt.Errorf("internal error: unexpected context %T for spread call", context)
  1071  				}
  1072  				return res, nil
  1073  			}
  1074  		}
  1075  	}
  1076  
  1077  	// Special case: tail-call.
  1078  	//
  1079  	// Inlining:
  1080  	//         return f(args)
  1081  	// where:
  1082  	//         func f(params) (results) { body }
  1083  	// reduces to:
  1084  	//         { var (bindings); body }
  1085  	//         { body }
  1086  	// so long as:
  1087  	// - all parameters can be eliminated or replaced by a binding decl,
  1088  	// - call is a tail-call;
  1089  	// - all returns in body have trivial result conversions,
  1090  	//   or the caller's return type matches the callee's,
  1091  	// - there is no label conflict;
  1092  	// - no result variable is referenced by name,
  1093  	//   or implicitly by a bare return.
  1094  	//
  1095  	// The body may use defer, arbitrary control flow, and
  1096  	// multiple returns.
  1097  	//
  1098  	// TODO(adonovan): add a strategy for a 'void tail
  1099  	// call', i.e. a call statement prior to an (explicit
  1100  	// or implicit) return.
  1101  	parent, _ := callContext(caller.path)
  1102  	if ret, ok := parent.(*ast.ReturnStmt); ok &&
  1103  		len(ret.Results) == 1 &&
  1104  		tailCallSafeReturn(caller, calleeSymbol, callee) &&
  1105  		!callee.HasBareReturn &&
  1106  		(!needBindingDecl || bindingDecl != nil) &&
  1107  		!hasLabelConflict(caller.path, callee.Labels) &&
  1108  		allResultsUnreferenced {
  1109  		logf("strategy: reduce tail-call")
  1110  		body := calleeDecl.Body
  1111  		clearPositions(body)
  1112  		if needBindingDecl {
  1113  			res.bindingDecl = true
  1114  			body.List = prepend(bindingDecl.stmt, body.List...)
  1115  		}
  1116  		res.old = ret
  1117  		res.new = body
  1118  		return res, nil
  1119  	}
  1120  
  1121  	// Special case: call to void function
  1122  	//
  1123  	// Inlining:
  1124  	//         f(args)
  1125  	// where:
  1126  	//	   func f(params) { stmts }
  1127  	// reduces to:
  1128  	//         { var (bindings); stmts }
  1129  	//         { stmts }
  1130  	// so long as:
  1131  	// - callee is a void function (no returns)
  1132  	// - callee does not use defer
  1133  	// - there is no label conflict between caller and callee
  1134  	// - all parameters and result vars can be eliminated
  1135  	//   or replaced by a binding decl,
  1136  	// - caller ExprStmt is in unrestricted statement context.
  1137  	if stmt := callStmt(caller.path, true); stmt != nil &&
  1138  		(!needBindingDecl || bindingDecl != nil) &&
  1139  		!callee.HasDefer &&
  1140  		!hasLabelConflict(caller.path, callee.Labels) &&
  1141  		len(callee.Returns) == 0 {
  1142  		logf("strategy: reduce stmt-context call to { stmts }")
  1143  		body := calleeDecl.Body
  1144  		var repl ast.Stmt = body
  1145  		clearPositions(repl)
  1146  		if needBindingDecl {
  1147  			body.List = prepend(bindingDecl.stmt, body.List...)
  1148  		}
  1149  		res.old = stmt
  1150  		res.new = repl
  1151  		return res, nil
  1152  	}
  1153  
  1154  	// TODO(adonovan): parameterless call to { stmts; return expr }
  1155  	// from one of these contexts:
  1156  	//    x, y     = f()
  1157  	//    x, y    := f()
  1158  	//    var x, y = f()
  1159  	// =>
  1160  	//    var (x T1, y T2); { stmts; x, y = expr }
  1161  	//
  1162  	// Because the params are no longer declared simultaneously
  1163  	// we need to check that (for example) x ∉ freevars(T2),
  1164  	// in addition to the usual checks for arg/result conversions,
  1165  	// complex control, etc.
  1166  	// Also test cases where expr is an n-ary call (spread returns).
  1167  
  1168  	// Literalization isn't quite infallible.
  1169  	// Consider a spread call to a method in which
  1170  	// no parameters are eliminated, e.g.
  1171  	// 	new(T).f(g())
  1172  	// where
  1173  	//  	func (recv *T) f(x, y int) { body }
  1174  	//  	func g() (int, int)
  1175  	// This would be literalized to:
  1176  	// 	func (recv *T, x, y int) { body }(new(T), g()),
  1177  	// which is not a valid argument list because g() must appear alone.
  1178  	// Reject this case for now.
  1179  	if len(args) == 2 && args[0] != nil && args[1] != nil && is[*types.Tuple](args[1].typ) {
  1180  		return nil, fmt.Errorf("can't yet inline spread call to method")
  1181  	}
  1182  
  1183  	// Infallible general case: literalization.
  1184  	//
  1185  	//    func(params) { body }(args)
  1186  	//
  1187  	logf("strategy: literalization")
  1188  	funcLit := &ast.FuncLit{
  1189  		Type: calleeDecl.Type,
  1190  		Body: calleeDecl.Body,
  1191  	}
  1192  	// clear positions before prepending the binding decl below, since the
  1193  	// binding decl contains syntax from the caller and we must not mutate the
  1194  	// caller. (This was a prior bug.)
  1195  	clearPositions(funcLit)
  1196  
  1197  	// Literalization can still make use of a binding
  1198  	// decl as it gives a more natural reading order:
  1199  	//
  1200  	//    func() { var params = args; body }()
  1201  	//
  1202  	// TODO(adonovan): relax the allResultsUnreferenced requirement
  1203  	// by adding a parameter-only (no named results) binding decl.
  1204  	if bindingDecl != nil && allResultsUnreferenced {
  1205  		funcLit.Type.Params.List = nil
  1206  		remainingArgs = nil
  1207  		res.bindingDecl = true
  1208  		funcLit.Body.List = prepend(bindingDecl.stmt, funcLit.Body.List...)
  1209  	}
  1210  
  1211  	// Emit a new call to a function literal in place of
  1212  	// the callee name, with appropriate replacements.
  1213  	newCall := &ast.CallExpr{
  1214  		Fun:      funcLit,
  1215  		Ellipsis: token.NoPos, // f(slice...) is always simplified
  1216  		Args:     remainingArgs,
  1217  	}
  1218  	res.old = caller.Call
  1219  	res.new = newCall
  1220  	return res, nil
  1221  }
  1222  
  1223  // renameFreeObjs computes the renaming of the callee's free identifiers.
  1224  // It returns a slice of names (identifiers or selector expressions) corresponding
  1225  // to the callee's free objects (gobCallee.FreeObjs).
  1226  func (st *state) renameFreeObjs(istate *importState) ([]ast.Expr, error) {
  1227  	caller, callee := st.caller, &st.callee.impl
  1228  	objRenames := make([]ast.Expr, len(callee.FreeObjs)) // nil => no change
  1229  	for i, obj := range callee.FreeObjs {
  1230  		// obj is a free object of the callee.
  1231  		//
  1232  		// Possible cases are:
  1233  		// - builtin function, type, or value (e.g. nil, zero)
  1234  		//   => check not shadowed in caller.
  1235  		// - package-level var/func/const/types
  1236  		//   => same package: check not shadowed in caller.
  1237  		//   => otherwise: import other package, form a qualified identifier.
  1238  		//      (Unexported cross-package references were rejected already.)
  1239  		// - type parameter
  1240  		//   => not yet supported
  1241  		// - pkgname
  1242  		//   => import other package and use its local name.
  1243  		//
  1244  		// There can be no free references to labels, fields, or methods.
  1245  
  1246  		// Note that we must consider potential shadowing both
  1247  		// at the caller side (caller.lookup) and, when
  1248  		// choosing new PkgNames, within the callee (obj.shadow).
  1249  
  1250  		var newName ast.Expr
  1251  		if obj.Kind == "pkgname" {
  1252  			// Use locally appropriate import, creating as needed.
  1253  			n := istate.localName(obj.PkgPath, obj.PkgName, obj.Name, obj.Shadow)
  1254  			newName = makeIdent(n) // imported package
  1255  		} else if !obj.ValidPos {
  1256  			// Built-in function, type, or value (e.g. nil, zero):
  1257  			// check not shadowed at caller.
  1258  			found := caller.lookup(obj.Name) // always finds something
  1259  			if found.Pos().IsValid() {
  1260  				return nil, fmt.Errorf("cannot inline, because the callee refers to built-in %q, which in the caller is shadowed by a %s (declared at line %d)",
  1261  					obj.Name, objectKind(found),
  1262  					caller.Fset.PositionFor(found.Pos(), false).Line)
  1263  			}
  1264  
  1265  		} else {
  1266  			// Must be reference to package-level var/func/const/type,
  1267  			// since type parameters are not yet supported.
  1268  			qualify := false
  1269  			if obj.PkgPath == callee.PkgPath {
  1270  				// reference within callee package
  1271  				if caller.Types.Path() == callee.PkgPath {
  1272  					// Caller and callee are in same package.
  1273  					// Check caller has not shadowed the decl.
  1274  					//
  1275  					// This may fail if the callee is "fake", such as for signature
  1276  					// refactoring where the callee is modified to be a trivial wrapper
  1277  					// around the refactored signature.
  1278  					found := caller.lookup(obj.Name)
  1279  					if found != nil && !isPkgLevel(found) {
  1280  						return nil, fmt.Errorf("cannot inline, because the callee refers to %s %q, which in the caller is shadowed by a %s (declared at line %d)",
  1281  							obj.Kind, obj.Name,
  1282  							objectKind(found),
  1283  							caller.Fset.PositionFor(found.Pos(), false).Line)
  1284  					}
  1285  				} else {
  1286  					// Cross-package reference.
  1287  					qualify = true
  1288  				}
  1289  			} else {
  1290  				// Reference to a package-level declaration
  1291  				// in another package, without a qualified identifier:
  1292  				// it must be a dot import.
  1293  				qualify = true
  1294  			}
  1295  
  1296  			// Form a qualified identifier, pkg.Name.
  1297  			if qualify {
  1298  				pkgName := istate.localName(obj.PkgPath, obj.PkgName, obj.PkgName, obj.Shadow)
  1299  				newName = &ast.SelectorExpr{
  1300  					X:   makeIdent(pkgName),
  1301  					Sel: makeIdent(obj.Name),
  1302  				}
  1303  			}
  1304  		}
  1305  		objRenames[i] = newName
  1306  	}
  1307  	return objRenames, nil
  1308  }
  1309  
  1310  type argument struct {
  1311  	expr          ast.Expr
  1312  	typ           types.Type      // may be tuple for sole non-receiver arg in spread call
  1313  	constant      constant.Value  // value of argument if constant
  1314  	spread        bool            // final arg is call() assigned to multiple params
  1315  	pure          bool            // expr is pure (doesn't read variables)
  1316  	effects       bool            // expr has effects (updates variables)
  1317  	duplicable    bool            // expr may be duplicated
  1318  	freevars      map[string]bool // free names of expr
  1319  	variadic      bool            // is explicit []T{...} for eliminated variadic
  1320  	desugaredRecv bool            // is *recv or &recv, where operator was elided
  1321  }
  1322  
  1323  // typeArguments returns the type arguments of the call.
  1324  // It only collects the arguments that are explicitly provided; it does
  1325  // not attempt type inference.
  1326  func (st *state) typeArguments(call *ast.CallExpr) []*argument {
  1327  	var exprs []ast.Expr
  1328  	switch d := ast.Unparen(call.Fun).(type) {
  1329  	case *ast.IndexExpr:
  1330  		exprs = []ast.Expr{d.Index}
  1331  	case *ast.IndexListExpr:
  1332  		exprs = d.Indices
  1333  	default:
  1334  		// No type  arguments
  1335  		return nil
  1336  	}
  1337  	var args []*argument
  1338  	for _, e := range exprs {
  1339  		arg := &argument{expr: e, freevars: freeVars(st.caller.Info, e)}
  1340  		args = append(args, arg)
  1341  	}
  1342  	return args
  1343  }
  1344  
  1345  // arguments returns the effective arguments of the call.
  1346  //
  1347  // If the receiver argument and parameter have
  1348  // different pointerness, make the "&" or "*" explicit.
  1349  //
  1350  // Also, if x.f() is shorthand for promoted method x.y.f(),
  1351  // make the .y explicit in T.f(x.y, ...).
  1352  //
  1353  // Beware that:
  1354  //
  1355  //   - a method can only be called through a selection, but only
  1356  //     the first of these two forms needs special treatment:
  1357  //
  1358  //     expr.f(args)     -> ([&*]expr, args)	MethodVal
  1359  //     T.f(recv, args)  -> (    expr, args)	MethodExpr
  1360  //
  1361  //   - the presence of a value in receiver-position in the call
  1362  //     is a property of the caller, not the callee. A method
  1363  //     (calleeDecl.Recv != nil) may be called like an ordinary
  1364  //     function.
  1365  //
  1366  //   - the types.Signatures seen by the caller (from
  1367  //     StaticCallee) and by the callee (from decl type)
  1368  //     differ in this case.
  1369  //
  1370  // In a spread call f(g()), the sole ordinary argument g(),
  1371  // always last in args, has a tuple type.
  1372  //
  1373  // We compute type-based predicates like pure, duplicable,
  1374  // freevars, etc, now, before we start modifying syntax.
  1375  func (st *state) arguments(caller *Caller, calleeDecl *ast.FuncDecl, assign1 func(*types.Var) bool) ([]*argument, error) {
  1376  	var args []*argument
  1377  
  1378  	callArgs := caller.Call.Args
  1379  	if calleeDecl.Recv != nil {
  1380  		if len(st.callee.impl.TypeParams) > 0 {
  1381  			return nil, fmt.Errorf("cannot inline: generic methods not yet supported")
  1382  		}
  1383  		sel := ast.Unparen(caller.Call.Fun).(*ast.SelectorExpr)
  1384  		seln := caller.Info.Selections[sel]
  1385  		var recvArg ast.Expr
  1386  		switch seln.Kind() {
  1387  		case types.MethodVal: // recv.f(callArgs)
  1388  			recvArg = sel.X
  1389  		case types.MethodExpr: // T.f(recv, callArgs)
  1390  			recvArg = callArgs[0]
  1391  			callArgs = callArgs[1:]
  1392  		}
  1393  		if recvArg != nil {
  1394  			// Compute all the type-based predicates now,
  1395  			// before we start meddling with the syntax;
  1396  			// the meddling will update them.
  1397  			arg := &argument{
  1398  				expr:       recvArg,
  1399  				typ:        caller.Info.TypeOf(recvArg),
  1400  				constant:   caller.Info.Types[recvArg].Value,
  1401  				pure:       pure(caller.Info, assign1, recvArg),
  1402  				effects:    st.effects(caller.Info, recvArg),
  1403  				duplicable: duplicable(caller.Info, recvArg),
  1404  				freevars:   freeVars(caller.Info, recvArg),
  1405  			}
  1406  			recvArg = nil // prevent accidental use
  1407  
  1408  			// Move receiver argument recv.f(args) to argument list f(&recv, args).
  1409  			args = append(args, arg)
  1410  
  1411  			// Make field selections explicit (recv.f -> recv.y.f),
  1412  			// updating arg.{expr,typ}.
  1413  			indices := seln.Index()
  1414  			for _, index := range indices[:len(indices)-1] {
  1415  				fld := typeparams.CoreType(typeparams.Deref(arg.typ)).(*types.Struct).Field(index)
  1416  				if fld.Pkg() != caller.Types && !fld.Exported() {
  1417  					return nil, fmt.Errorf("in %s, implicit reference to unexported field .%s cannot be made explicit",
  1418  						debugFormatNode(caller.Fset, caller.Call.Fun),
  1419  						fld.Name())
  1420  				}
  1421  				if isPointer(arg.typ) {
  1422  					arg.pure = false // implicit *ptr operation => impure
  1423  				}
  1424  				arg.expr = &ast.SelectorExpr{
  1425  					X:   arg.expr,
  1426  					Sel: makeIdent(fld.Name()),
  1427  				}
  1428  				arg.typ = fld.Type()
  1429  				arg.duplicable = false
  1430  			}
  1431  
  1432  			// Make * or & explicit.
  1433  			argIsPtr := isPointer(arg.typ)
  1434  			paramIsPtr := isPointer(seln.Obj().Type().Underlying().(*types.Signature).Recv().Type())
  1435  			if !argIsPtr && paramIsPtr {
  1436  				// &recv
  1437  				arg.expr = &ast.UnaryExpr{Op: token.AND, X: arg.expr}
  1438  				arg.typ = types.NewPointer(arg.typ)
  1439  				arg.desugaredRecv = true
  1440  			} else if argIsPtr && !paramIsPtr {
  1441  				// *recv
  1442  				arg.expr = &ast.StarExpr{X: arg.expr}
  1443  				arg.typ = typeparams.Deref(arg.typ)
  1444  				arg.duplicable = false
  1445  				arg.pure = false
  1446  				arg.desugaredRecv = true
  1447  			}
  1448  		}
  1449  	}
  1450  	for _, expr := range callArgs {
  1451  		tv := caller.Info.Types[expr]
  1452  		args = append(args, &argument{
  1453  			expr:       expr,
  1454  			typ:        tv.Type,
  1455  			constant:   tv.Value,
  1456  			spread:     is[*types.Tuple](tv.Type), // => last
  1457  			pure:       pure(caller.Info, assign1, expr),
  1458  			effects:    st.effects(caller.Info, expr),
  1459  			duplicable: duplicable(caller.Info, expr),
  1460  			freevars:   freeVars(caller.Info, expr),
  1461  		})
  1462  	}
  1463  
  1464  	// Re-typecheck each constant argument expression in a neutral context.
  1465  	//
  1466  	// In a call such as func(int16){}(1), the type checker infers
  1467  	// the type "int16", not "untyped int", for the argument 1,
  1468  	// because it has incorporated information from the left-hand
  1469  	// side of the assignment implicit in parameter passing, but
  1470  	// of course in a different context, the expression 1 may have
  1471  	// a different type.
  1472  	//
  1473  	// So, we must use CheckExpr to recompute the type of the
  1474  	// argument in a neutral context to find its inherent type.
  1475  	// (This is arguably a bug in go/types, but I'm pretty certain
  1476  	// I requested it be this way long ago... -adonovan)
  1477  	//
  1478  	// This is only needed for constants. Other implicit
  1479  	// assignment conversions, such as unnamed-to-named struct or
  1480  	// chan to <-chan, do not result in the type-checker imposing
  1481  	// the LHS type on the RHS value.
  1482  	for _, arg := range args {
  1483  		if arg.constant == nil {
  1484  			continue
  1485  		}
  1486  		info := &types.Info{Types: make(map[ast.Expr]types.TypeAndValue)}
  1487  		if err := types.CheckExpr(caller.Fset, caller.Types, caller.Call.Pos(), arg.expr, info); err != nil {
  1488  			return nil, err
  1489  		}
  1490  		arg.typ = info.TypeOf(arg.expr)
  1491  	}
  1492  
  1493  	return args, nil
  1494  }
  1495  
  1496  type parameter struct {
  1497  	obj       *types.Var // parameter var from caller's signature
  1498  	fieldType ast.Expr   // syntax of type, from calleeDecl.Type.{Recv,Params}
  1499  	info      *paramInfo // information from AnalyzeCallee
  1500  	variadic  bool       // (final) parameter is unsimplified ...T
  1501  }
  1502  
  1503  // A replacer replaces an identifier at the given offset in the callee.
  1504  // The replacement tree must not belong to the caller; use cloneNode as needed.
  1505  // If unpackVariadic is set, the replacement is a composite resulting from
  1506  // variadic elimination, and may be unpacked into variadic calls.
  1507  type replacer = func(offset int, repl ast.Expr, unpackVariadic bool)
  1508  
  1509  // substituteTypeParams replaces type parameters in the callee with the corresponding type arguments
  1510  // from the call.
  1511  func substituteTypeParams(logf logger, typeParams []*paramInfo, typeArgs []*argument, params []*parameter, replace replacer) error {
  1512  	assert(len(typeParams) == len(typeArgs), "mismatched number of type params/args")
  1513  	for i, paramInfo := range typeParams {
  1514  		arg := typeArgs[i]
  1515  		// Perform a simplified, conservative shadow analysis: fail if there is any shadowing.
  1516  		for free := range arg.freevars {
  1517  			if paramInfo.Shadow[free] != 0 {
  1518  				return fmt.Errorf("cannot inline: type argument #%d (type parameter %s) is shadowed", i, paramInfo.Name)
  1519  			}
  1520  		}
  1521  		logf("replacing type param %s with %s", paramInfo.Name, debugFormatNode(token.NewFileSet(), arg.expr))
  1522  		for _, ref := range paramInfo.Refs {
  1523  			replace(ref.Offset, internalastutil.CloneNode(arg.expr), false)
  1524  		}
  1525  		// Also replace parameter field types.
  1526  		// TODO(jba): find a way to do this that is not so slow and clumsy.
  1527  		// Ideally, we'd walk each p.fieldType once, replacing all type params together.
  1528  		for _, p := range params {
  1529  			if id, ok := p.fieldType.(*ast.Ident); ok && id.Name == paramInfo.Name {
  1530  				p.fieldType = arg.expr
  1531  			} else {
  1532  				for _, id := range identsNamed(p.fieldType, paramInfo.Name) {
  1533  					replaceNode(p.fieldType, id, arg.expr)
  1534  				}
  1535  			}
  1536  		}
  1537  	}
  1538  	return nil
  1539  }
  1540  
  1541  func identsNamed(n ast.Node, name string) []*ast.Ident {
  1542  	var ids []*ast.Ident
  1543  	ast.Inspect(n, func(n ast.Node) bool {
  1544  		if id, ok := n.(*ast.Ident); ok && id.Name == name {
  1545  			ids = append(ids, id)
  1546  		}
  1547  		return true
  1548  	})
  1549  	return ids
  1550  }
  1551  
  1552  // substitute implements parameter elimination by substitution.
  1553  //
  1554  // It considers each parameter and its corresponding argument in turn
  1555  // and evaluate these conditions:
  1556  //
  1557  //   - the parameter is neither address-taken nor assigned;
  1558  //   - the argument is pure;
  1559  //   - if the parameter refcount is zero, the argument must
  1560  //     not contain the last use of a local var;
  1561  //   - if the parameter refcount is > 1, the argument must be duplicable;
  1562  //   - the argument (or types.Default(argument) if it's untyped) has
  1563  //     the same type as the parameter.
  1564  //
  1565  // If all conditions are met then the parameter can be substituted and
  1566  // each reference to it replaced by the argument. In that case, the
  1567  // replaceCalleeID function is called for each reference to the
  1568  // parameter, and is provided with its relative offset and replacement
  1569  // expression (argument), and the corresponding elements of params and
  1570  // args are replaced by nil.
  1571  func substitute(logf logger, caller *Caller, params []*parameter, args []*argument, effects []int, falcon falconResult, replace replacer) {
  1572  	// Inv:
  1573  	//  in        calls to     variadic, len(args) >= len(params)-1
  1574  	//  in spread calls to non-variadic, len(args) <  len(params)
  1575  	//  in spread calls to     variadic, len(args) <= len(params)
  1576  	// (In spread calls len(args) = 1, or 2 if call has receiver.)
  1577  	// Non-spread variadics have been simplified away already,
  1578  	// so the args[i] lookup is safe if we stop after the spread arg.
  1579  	assert(len(args) <= len(params), "too many arguments")
  1580  
  1581  	// Collect candidates for substitution.
  1582  	//
  1583  	// An argument is a candidate if it is not otherwise rejected, and any free
  1584  	// variables that are shadowed only by other parameters.
  1585  	//
  1586  	// Therefore, substitution candidates are represented by a graph, where edges
  1587  	// lead from each argument to the other arguments that, if substituted, would
  1588  	// allow the argument to be substituted. We collect these edges in the
  1589  	// [substGraph]. Any node that is known not to be elided from the graph.
  1590  	// Arguments in this graph with no edges are substitutable independent of
  1591  	// other nodes, though they may be removed due to falcon or effects analysis.
  1592  	sg := make(substGraph)
  1593  next:
  1594  	for i, param := range params {
  1595  		arg := args[i]
  1596  
  1597  		// Check argument against parameter.
  1598  		//
  1599  		// Beware: don't use types.Info on arg since
  1600  		// the syntax may be synthetic (not created by parser)
  1601  		// and thus lacking positions and types;
  1602  		// do it earlier (see pure/duplicable/freevars).
  1603  
  1604  		if arg.spread {
  1605  			// spread => last argument, but not always last parameter
  1606  			logf("keeping param %q and following ones: argument %s is spread",
  1607  				param.info.Name, debugFormatNode(caller.Fset, arg.expr))
  1608  			return // give up
  1609  		}
  1610  		assert(!param.variadic, "unsimplified variadic parameter")
  1611  		if param.info.Escapes {
  1612  			logf("keeping param %q: escapes from callee", param.info.Name)
  1613  			continue
  1614  		}
  1615  		if param.info.Assigned {
  1616  			logf("keeping param %q: assigned by callee", param.info.Name)
  1617  			continue // callee needs the parameter variable
  1618  		}
  1619  		if len(param.info.Refs) > 1 && !arg.duplicable {
  1620  			logf("keeping param %q: argument is not duplicable", param.info.Name)
  1621  			continue // incorrect or poor style to duplicate an expression
  1622  		}
  1623  		if len(param.info.Refs) == 0 {
  1624  			if arg.effects {
  1625  				logf("keeping param %q: though unreferenced, it has effects", param.info.Name)
  1626  				continue
  1627  			}
  1628  
  1629  			// If the caller is within a function body,
  1630  			// eliminating an unreferenced parameter might
  1631  			// remove the last reference to a caller local var.
  1632  			if caller.enclosingFunc != nil {
  1633  				for free := range arg.freevars {
  1634  					// TODO(rfindley): we can get this 100% right by looking for
  1635  					// references among other arguments which have non-zero references
  1636  					// within the callee.
  1637  					if v, ok := caller.lookup(free).(*types.Var); ok && within(v.Pos(), caller.enclosingFunc.Body) && !isUsedOutsideCall(caller, v) {
  1638  
  1639  						// Check to see if the substituted var is used within other args
  1640  						// whose corresponding params ARE used in the callee
  1641  						usedElsewhere := func() bool {
  1642  							for i, param := range params {
  1643  								if i < len(args) && len(param.info.Refs) > 0 { // excludes original param
  1644  									for name := range args[i].freevars {
  1645  										if caller.lookup(name) == v {
  1646  											return true
  1647  										}
  1648  									}
  1649  								}
  1650  							}
  1651  							return false
  1652  						}
  1653  						if !usedElsewhere() {
  1654  							logf("keeping param %q: arg contains perhaps the last reference to caller local %v @ %v",
  1655  								param.info.Name, v, caller.Fset.PositionFor(v.Pos(), false))
  1656  							continue next
  1657  						}
  1658  					}
  1659  				}
  1660  			}
  1661  		}
  1662  
  1663  		// Arg is a potential substitution candidate: analyze its shadowing.
  1664  		//
  1665  		// Consider inlining a call f(z, 1) to
  1666  		//
  1667  		// 	func f(x, y int) int { z := y; return x + y + z }
  1668  		//
  1669  		// we can't replace x in the body by z (or any
  1670  		// expression that has z as a free identifier) because there's an
  1671  		// intervening declaration of z that would shadow the caller's one.
  1672  		//
  1673  		// However, we *could* replace x in the body by y, as long as the y
  1674  		// parameter is also removed by substitution.
  1675  
  1676  		sg[arg] = nil // Absent shadowing, the arg is substitutable.
  1677  		for free := range arg.freevars {
  1678  			switch s := param.info.Shadow[free]; {
  1679  			case s < 0:
  1680  				// Shadowed by a non-parameter symbol, so arg is not substitutable.
  1681  				delete(sg, arg)
  1682  			case s > 0:
  1683  				// Shadowed by a parameter; arg may be substitutable, if only shadowed
  1684  				// by other substitutable parameters.
  1685  				if s > len(args) {
  1686  					// Defensive: this should not happen in the current factoring, since
  1687  					// spread arguments are already handled.
  1688  					delete(sg, arg)
  1689  				}
  1690  				if edges, ok := sg[arg]; ok {
  1691  					sg[arg] = append(edges, args[s-1])
  1692  				}
  1693  			}
  1694  		}
  1695  	}
  1696  
  1697  	// Process the initial state of the substitution graph.
  1698  	sg.prune()
  1699  
  1700  	// Now we check various conditions on the substituted argument set as a
  1701  	// whole. These conditions reject substitution candidates, but since their
  1702  	// analysis depends on the full set of candidates, we do not process side
  1703  	// effects of their candidate rejection until after the analysis completes,
  1704  	// in a call to prune. After pruning, we must re-run the analysis to check
  1705  	// for additional rejections.
  1706  	//
  1707  	// Here's an example of that in practice:
  1708  	//
  1709  	// 	var a [3]int
  1710  	//
  1711  	// 	func falcon(x, y, z int) {
  1712  	// 		_ = x + a[y+z]
  1713  	// 	}
  1714  	//
  1715  	// 	func _() {
  1716  	// 		var y int
  1717  	// 		const x, z = 1, 2
  1718  	// 		falcon(y, x, z)
  1719  	// 	}
  1720  	//
  1721  	// In this example, arguments 0 and 1 are shadowed by each other's
  1722  	// corresponding parameter, and so each can be substituted only if they are
  1723  	// both substituted. But the fallible constant analysis finds a violated
  1724  	// constraint: x + z = 3, and so the constant array index would cause a
  1725  	// compile-time error if argument 1 (x) were substituted. Therefore,
  1726  	// following the falcon analysis, we must also prune argument 0.
  1727  	//
  1728  	// As far as I (rfindley) can tell, the falcon analysis should always succeed
  1729  	// after the first pass, as it's not possible for additional bindings to
  1730  	// cause new constraint failures. Nevertheless, we re-run it to be sure.
  1731  	//
  1732  	// However, the same cannot be said of the effects analysis, as demonstrated
  1733  	// by this example:
  1734  	//
  1735  	// 	func effects(w, x, y, z int) {
  1736  	// 		_ = x + w + y + z
  1737  	// 	}
  1738  
  1739  	// 	func _() {
  1740  	// 		v := 0
  1741  	// 		w := func() int { v++; return 0 }
  1742  	// 		x := func() int { v++; return 0 }
  1743  	// 		y := func() int { v++; return 0 }
  1744  	// 		effects(x(), w(), y(), x()) //@ inline(re"effects", effects)
  1745  	// 	}
  1746  	//
  1747  	// In this example, arguments 0, 1, and 3 are related by the substitution
  1748  	// graph. The first effects analysis implies that arguments 0 and 1 must be
  1749  	// bound, and therefore argument 3 must be bound. But then a subsequent
  1750  	// effects analysis forces argument 2 to also be bound.
  1751  
  1752  	// Reject constant arguments as substitution candidates if they cause
  1753  	// violation of falcon constraints.
  1754  	//
  1755  	// Keep redoing the analysis until we no longer reject additional arguments,
  1756  	// as the set of substituted parameters affects the falcon package.
  1757  	for checkFalconConstraints(logf, params, args, falcon, sg) {
  1758  		sg.prune()
  1759  	}
  1760  
  1761  	// As a final step, introduce bindings to resolve any
  1762  	// evaluation order hazards. This must be done last, as
  1763  	// additional subsequent bindings could introduce new hazards.
  1764  	//
  1765  	// As with the falcon analysis, keep redoing the analysis until the no more
  1766  	// arguments are rejected.
  1767  	for resolveEffects(logf, args, effects, sg) {
  1768  		sg.prune()
  1769  	}
  1770  
  1771  	// The remaining candidates are safe to substitute.
  1772  	for i, param := range params {
  1773  		if arg := args[i]; sg.has(arg) {
  1774  
  1775  			// It is safe to substitute param and replace it with arg.
  1776  			// The formatter introduces parens as needed for precedence.
  1777  			//
  1778  			// Because arg.expr belongs to the caller,
  1779  			// we clone it before splicing it into the callee tree.
  1780  			logf("replacing parameter %q by argument %q",
  1781  				param.info.Name, debugFormatNode(caller.Fset, arg.expr))
  1782  			for _, ref := range param.info.Refs {
  1783  				// Apply any transformations necessary for this reference.
  1784  				argExpr := arg.expr
  1785  
  1786  				// If the reference itself is being selected, and we applied desugaring
  1787  				// (an explicit &x or *x), we can undo that desugaring here as it is
  1788  				// not necessary for a selector. We don't need to check addressability
  1789  				// here because if we desugared, the receiver must have been
  1790  				// addressable.
  1791  				if ref.IsSelectionOperand && arg.desugaredRecv {
  1792  					switch e := argExpr.(type) {
  1793  					case *ast.UnaryExpr:
  1794  						argExpr = e.X
  1795  					case *ast.StarExpr:
  1796  						argExpr = e.X
  1797  					}
  1798  				}
  1799  
  1800  				// If the reference requires exact type agreement between parameter and
  1801  				// argument, wrap the argument in an explicit conversion if
  1802  				// substitution might materially change its type. (We already did the
  1803  				// necessary shadowing check on the parameter type syntax.)
  1804  				//
  1805  				// The types must agree in any of these cases:
  1806  				// - the argument affects type inference;
  1807  				// - the reference's concrete type is assigned to an interface type;
  1808  				// - the reference is not an assignment, nor a trivial conversion of an untyped constant.
  1809  				//
  1810  				// In all other cases, no explicit conversion is necessary as either
  1811  				// the type does not matter, or must have already agreed for well-typed
  1812  				// code.
  1813  				//
  1814  				// This is only needed for substituted arguments. All other arguments
  1815  				// are given explicit types in either a binding decl or when using the
  1816  				// literalization strategy.
  1817  				//
  1818  				// If the types are identical, we can eliminate
  1819  				// redundant type conversions such as this:
  1820  				//
  1821  				// Callee:
  1822  				//    func f(i int32) { fmt.Println(i) }
  1823  				// Caller:
  1824  				//    func g() { f(int32(1)) }
  1825  				// Inlined as:
  1826  				//    func g() { fmt.Println(int32(int32(1)))
  1827  				//
  1828  				// Recall that non-trivial does not imply non-identical for constant
  1829  				// conversions; however, at this point state.arguments has already
  1830  				// re-typechecked the constant and set arg.type to its (possibly
  1831  				// "untyped") inherent type, so the conversion from untyped 1 to int32
  1832  				// is non-trivial even though both arg and param have identical types
  1833  				// (int32).
  1834  				needType := ref.AffectsInference ||
  1835  					(ref.Assignable && ref.IfaceAssignment && !param.info.IsInterface) ||
  1836  					(!ref.Assignable && !trivialConversion(arg.constant, arg.typ, param.obj.Type()))
  1837  
  1838  				if needType &&
  1839  					!types.Identical(types.Default(arg.typ), param.obj.Type()) {
  1840  
  1841  					// If arg.expr is already an interface call, strip it.
  1842  					if call, ok := argExpr.(*ast.CallExpr); ok && len(call.Args) == 1 {
  1843  						if typ, ok := isConversion(caller.Info, call); ok && isNonTypeParamInterface(typ) {
  1844  							argExpr = call.Args[0]
  1845  						}
  1846  					}
  1847  
  1848  					argExpr = convert(param.fieldType, argExpr)
  1849  					logf("param %q (offset %d): adding explicit %s -> %s conversion around argument",
  1850  						param.info.Name, ref.Offset, arg.typ, param.obj.Type())
  1851  				}
  1852  				replace(ref.Offset, internalastutil.CloneNode(argExpr).(ast.Expr), arg.variadic)
  1853  			}
  1854  			params[i] = nil // substituted
  1855  			args[i] = nil   // substituted
  1856  		}
  1857  	}
  1858  }
  1859  
  1860  // isConversion reports whether the given call is a type conversion, returning
  1861  // (operand, true) if so.
  1862  //
  1863  // If the call is not a conversion, it returns (nil, false).
  1864  func isConversion(info *types.Info, call *ast.CallExpr) (types.Type, bool) {
  1865  	if tv, ok := info.Types[call.Fun]; ok && tv.IsType() {
  1866  		return tv.Type, true
  1867  	}
  1868  	return nil, false
  1869  }
  1870  
  1871  // isNonTypeParamInterface reports whether t is a non-type parameter interface
  1872  // type.
  1873  func isNonTypeParamInterface(t types.Type) bool {
  1874  	return !typeparams.IsTypeParam(t) && types.IsInterface(t)
  1875  }
  1876  
  1877  // isUsedOutsideCall reports whether v is used outside of caller.Call, within
  1878  // the body of caller.enclosingFunc.
  1879  func isUsedOutsideCall(caller *Caller, v *types.Var) bool {
  1880  	used := false
  1881  	ast.Inspect(caller.enclosingFunc.Body, func(n ast.Node) bool {
  1882  		if n == caller.Call {
  1883  			return false
  1884  		}
  1885  		switch n := n.(type) {
  1886  		case *ast.Ident:
  1887  			if use := caller.Info.Uses[n]; use == v {
  1888  				used = true
  1889  			}
  1890  		case *ast.FuncType:
  1891  			// All params are used.
  1892  			for _, fld := range n.Params.List {
  1893  				for _, n := range fld.Names {
  1894  					if def := caller.Info.Defs[n]; def == v {
  1895  						used = true
  1896  					}
  1897  				}
  1898  			}
  1899  		}
  1900  		return !used // keep going until we find a use
  1901  	})
  1902  	return used
  1903  }
  1904  
  1905  // checkFalconConstraints checks whether constant arguments
  1906  // are safe to substitute (e.g. s[i] -> ""[0] is not safe.)
  1907  //
  1908  // Any failed constraint causes us to reject all constant arguments as
  1909  // substitution candidates (by clearing args[i].substitution=false).
  1910  //
  1911  // TODO(adonovan): we could obtain a finer result rejecting only the
  1912  // freevars of each failed constraint, and processing constraints in
  1913  // order of increasing arity, but failures are quite rare.
  1914  func checkFalconConstraints(logf logger, params []*parameter, args []*argument, falcon falconResult, sg substGraph) bool {
  1915  	// Create a dummy package, as this is the only
  1916  	// way to create an environment for CheckExpr.
  1917  	pkg := types.NewPackage("falcon", "falcon")
  1918  
  1919  	// Declare types used by constraints.
  1920  	for _, typ := range falcon.Types {
  1921  		logf("falcon env: type %s %s", typ.Name, types.Typ[typ.Kind])
  1922  		pkg.Scope().Insert(types.NewTypeName(token.NoPos, pkg, typ.Name, types.Typ[typ.Kind]))
  1923  	}
  1924  
  1925  	// Declared constants and variables for parameters.
  1926  	nconst := 0
  1927  	for i, param := range params {
  1928  		name := param.info.Name
  1929  		if name == "" {
  1930  			continue // unreferenced
  1931  		}
  1932  		arg := args[i]
  1933  		if arg.constant != nil && sg.has(arg) && param.info.FalconType != "" {
  1934  			t := pkg.Scope().Lookup(param.info.FalconType).Type()
  1935  			pkg.Scope().Insert(types.NewConst(token.NoPos, pkg, name, t, arg.constant))
  1936  			logf("falcon env: const %s %s = %v", name, param.info.FalconType, arg.constant)
  1937  			nconst++
  1938  		} else {
  1939  			v := types.NewVar(token.NoPos, pkg, name, arg.typ)
  1940  			typesinternal.SetVarKind(v, typesinternal.PackageVar)
  1941  			pkg.Scope().Insert(v)
  1942  			logf("falcon env: var %s %s", name, arg.typ)
  1943  		}
  1944  	}
  1945  	if nconst == 0 {
  1946  		return false // nothing to do
  1947  	}
  1948  
  1949  	// Parse and evaluate the constraints in the environment.
  1950  	fset := token.NewFileSet()
  1951  	removed := false
  1952  	for _, falcon := range falcon.Constraints {
  1953  		expr, err := parser.ParseExprFrom(fset, "falcon", falcon, 0)
  1954  		if err != nil {
  1955  			panic(fmt.Sprintf("failed to parse falcon constraint %s: %v", falcon, err))
  1956  		}
  1957  		if err := types.CheckExpr(fset, pkg, token.NoPos, expr, nil); err != nil {
  1958  			logf("falcon: constraint %s violated: %v", falcon, err)
  1959  			for j, arg := range args {
  1960  				if arg.constant != nil && sg.has(arg) {
  1961  					logf("keeping param %q due falcon violation", params[j].info.Name)
  1962  					removed = sg.remove(arg) || removed
  1963  				}
  1964  			}
  1965  			break
  1966  		}
  1967  		logf("falcon: constraint %s satisfied", falcon)
  1968  	}
  1969  	return removed
  1970  }
  1971  
  1972  // resolveEffects marks arguments as non-substitutable to resolve
  1973  // hazards resulting from the callee evaluation order described by the
  1974  // effects list.
  1975  //
  1976  // To do this, each argument is categorized as a read (R), write (W),
  1977  // or pure. A hazard occurs when the order of evaluation of a W
  1978  // changes with respect to any R or W. Pure arguments can be
  1979  // effectively ignored, as they can be safely evaluated in any order.
  1980  //
  1981  // The callee effects list contains the index of each parameter in the
  1982  // order it is first evaluated during execution of the callee. In
  1983  // addition, the two special values R∞ and W∞ indicate the relative
  1984  // position of the callee's first non-parameter read and its first
  1985  // effects (or other unknown behavior).
  1986  // For example, the list [0 2 1 R∞ 3 W∞] for func(a, b, c, d)
  1987  // indicates that the callee referenced parameters a, c, and b,
  1988  // followed by an arbitrary read, then parameter d, and finally
  1989  // unknown behavior.
  1990  //
  1991  // When an argument is marked as not substitutable, we say that it is
  1992  // 'bound', in the sense that its evaluation occurs in a binding decl
  1993  // or literalized call. Such bindings always occur in the original
  1994  // callee parameter order.
  1995  //
  1996  // In this context, "resolving hazards" means binding arguments so
  1997  // that they are evaluated in a valid, hazard-free order. A trivial
  1998  // solution to this problem would be to bind all arguments, but of
  1999  // course that's not useful. The goal is to bind as few arguments as
  2000  // possible.
  2001  //
  2002  // The algorithm proceeds by inspecting arguments in reverse parameter
  2003  // order (right to left), preserving the invariant that every
  2004  // higher-ordered argument is either already substituted or does not
  2005  // need to be substituted. At each iteration, if there is an
  2006  // evaluation hazard in the callee effects relative to the current
  2007  // argument, the argument must be bound. Subsequently, if the argument
  2008  // is bound for any reason, each lower-ordered argument must also be
  2009  // bound if either the argument or lower-order argument is a
  2010  // W---otherwise the binding itself would introduce a hazard.
  2011  //
  2012  // Thus, after each iteration, there are no hazards relative to the
  2013  // current argument. Subsequent iterations cannot introduce hazards
  2014  // with that argument because they can result only in additional
  2015  // binding of lower-ordered arguments.
  2016  func resolveEffects(logf logger, args []*argument, effects []int, sg substGraph) bool {
  2017  	effectStr := func(effects bool, idx int) string {
  2018  		i := fmt.Sprint(idx)
  2019  		if idx == len(args) {
  2020  			i = "∞"
  2021  		}
  2022  		return string("RW"[btoi(effects)]) + i
  2023  	}
  2024  	removed := false
  2025  	for i, argi := range slices.Backward(args) {
  2026  		if sg.has(argi) && !argi.pure {
  2027  			// i is not bound: check whether it must be bound due to hazards.
  2028  			idx := slices.Index(effects, i)
  2029  			if idx >= 0 {
  2030  				for _, j := range effects[:idx] {
  2031  					var (
  2032  						ji int  // effective param index
  2033  						jw bool // j is a write
  2034  					)
  2035  					if j == winf || j == rinf {
  2036  						jw = j == winf
  2037  						ji = len(args)
  2038  					} else {
  2039  						jw = args[j].effects
  2040  						ji = j
  2041  					}
  2042  					if ji > i && (jw || argi.effects) { // out of order evaluation
  2043  						logf("binding argument %s: preceded by %s",
  2044  							effectStr(argi.effects, i), effectStr(jw, ji))
  2045  
  2046  						removed = sg.remove(argi) || removed
  2047  						break
  2048  					}
  2049  				}
  2050  			}
  2051  		}
  2052  		if !sg.has(argi) {
  2053  			for j := range i {
  2054  				argj := args[j]
  2055  				if argj.pure {
  2056  					continue
  2057  				}
  2058  				if (argi.effects || argj.effects) && sg.has(argj) {
  2059  					logf("binding argument %s: %s is bound",
  2060  						effectStr(argj.effects, j), effectStr(argi.effects, i))
  2061  
  2062  					removed = sg.remove(argj) || removed
  2063  				}
  2064  			}
  2065  		}
  2066  	}
  2067  	return removed
  2068  }
  2069  
  2070  // A substGraph is a directed graph representing arguments that may be
  2071  // substituted, provided all of their related arguments (or "dependencies") are
  2072  // also substituted. The candidates arguments for substitution are the keys in
  2073  // this graph, and the edges represent shadowing of free variables of the key
  2074  // by parameters corresponding to the dependency arguments.
  2075  //
  2076  // Any argument not present as a map key is known not to be substitutable. Some
  2077  // arguments may have edges leading to other arguments that are not present in
  2078  // the graph. In this case, those arguments also cannot be substituted, because
  2079  // they have free variables that are shadowed by parameters that cannot be
  2080  // substituted. Calling [substGraph.prune] removes these arguments from the
  2081  // graph.
  2082  //
  2083  // The 'prune' operation is not built into the 'remove' step both because
  2084  // analyses (falcon, effects) need local information about each argument
  2085  // independent of dependencies, and for the efficiency of pruning once en masse
  2086  // after each analysis.
  2087  type substGraph map[*argument][]*argument
  2088  
  2089  // has reports whether arg is a candidate for substitution.
  2090  func (g substGraph) has(arg *argument) bool {
  2091  	_, ok := g[arg]
  2092  	return ok
  2093  }
  2094  
  2095  // remove marks arg as not substitutable, reporting whether the arg was
  2096  // previously substitutable.
  2097  //
  2098  // remove does not have side effects on other arguments that may be
  2099  // unsubstitutable as a result of their dependency being removed.
  2100  // Call [substGraph.prune] to propagate these side effects, removing dependent
  2101  // arguments.
  2102  func (g substGraph) remove(arg *argument) bool {
  2103  	pre := len(g)
  2104  	delete(g, arg)
  2105  	return len(g) < pre
  2106  }
  2107  
  2108  // prune updates the graph to remove any keys that reach other arguments not
  2109  // present in the graph.
  2110  func (g substGraph) prune() {
  2111  	// visit visits the forward transitive closure of arg and reports whether any
  2112  	// missing argument was encountered, removing all nodes on the path to it
  2113  	// from arg.
  2114  	//
  2115  	// The seen map is used for cycle breaking. In the presence of cycles, visit
  2116  	// may report a false positive for an intermediate argument. For example,
  2117  	// consider the following graph, where only a and b are candidates for
  2118  	// substitution (meaning, only a and b are present in the graph).
  2119  	//
  2120  	//   a ↔ b
  2121  	//   ↓
  2122  	//  [c]
  2123  	//
  2124  	// In this case, starting a visit from a, visit(b, seen) may report 'true',
  2125  	// because c has not yet been considered. For this reason, we must guarantee
  2126  	// that visit is called with an empty seen map at least once for each node.
  2127  	var visit func(*argument, map[*argument]unit) bool
  2128  	visit = func(arg *argument, seen map[*argument]unit) bool {
  2129  		deps, ok := g[arg]
  2130  		if !ok {
  2131  			return false
  2132  		}
  2133  		if _, ok := seen[arg]; !ok {
  2134  			seen[arg] = unit{}
  2135  			for _, dep := range deps {
  2136  				if !visit(dep, seen) {
  2137  					delete(g, arg)
  2138  					return false
  2139  				}
  2140  			}
  2141  		}
  2142  		return true
  2143  	}
  2144  	for arg := range g {
  2145  		// Remove any argument that is, or transitively depends upon,
  2146  		// an unsubstitutable argument.
  2147  		//
  2148  		// Each visitation gets a fresh cycle-breaking set.
  2149  		visit(arg, make(map[*argument]unit))
  2150  	}
  2151  }
  2152  
  2153  // updateCalleeParams updates the calleeDecl syntax to remove
  2154  // substituted parameters and move the receiver (if any) to the head
  2155  // of the ordinary parameters.
  2156  func updateCalleeParams(calleeDecl *ast.FuncDecl, params []*parameter) {
  2157  	// The logic is fiddly because of the three forms of ast.Field:
  2158  	//
  2159  	//	func(int), func(x int), func(x, y int)
  2160  	//
  2161  	// Also, ensure that all remaining parameters are named
  2162  	// to avoid a mix of named/unnamed when joining (recv, params...).
  2163  	// func (T) f(int, bool) -> (_ T, _ int, _ bool)
  2164  	// (Strictly, we need do this only for methods and only when
  2165  	// the namednesses of Recv and Params differ; that might be tidier.)
  2166  
  2167  	paramIdx := 0 // index in original parameter list (incl. receiver)
  2168  	var newParams []*ast.Field
  2169  	filterParams := func(field *ast.Field) {
  2170  		var names []*ast.Ident
  2171  		if field.Names == nil {
  2172  			// Unnamed parameter field (e.g. func f(int)
  2173  			if params[paramIdx] != nil {
  2174  				// Give it an explicit name "_" since we will
  2175  				// make the receiver (if any) a regular parameter
  2176  				// and one cannot mix named and unnamed parameters.
  2177  				names = append(names, makeIdent("_"))
  2178  			}
  2179  			paramIdx++
  2180  		} else {
  2181  			// Named parameter field e.g. func f(x, y int)
  2182  			// Remove substituted parameters in place.
  2183  			// If all were substituted, delete field.
  2184  			for _, id := range field.Names {
  2185  				if pinfo := params[paramIdx]; pinfo != nil {
  2186  					// Rename unreferenced parameters with "_".
  2187  					// This is crucial for binding decls, since
  2188  					// unlike parameters, they are subject to
  2189  					// "unreferenced var" checks.
  2190  					if len(pinfo.info.Refs) == 0 {
  2191  						id = makeIdent("_")
  2192  					}
  2193  					names = append(names, id)
  2194  				}
  2195  				paramIdx++
  2196  			}
  2197  		}
  2198  		if names != nil {
  2199  			newParams = append(newParams, &ast.Field{
  2200  				Names: names,
  2201  				Type:  field.Type,
  2202  			})
  2203  		}
  2204  	}
  2205  	if calleeDecl.Recv != nil {
  2206  		filterParams(calleeDecl.Recv.List[0])
  2207  		calleeDecl.Recv = nil
  2208  	}
  2209  	for _, field := range calleeDecl.Type.Params.List {
  2210  		filterParams(field)
  2211  	}
  2212  	calleeDecl.Type.Params.List = newParams
  2213  }
  2214  
  2215  // bindingDeclInfo records information about the binding decl produced by
  2216  // createBindingDecl.
  2217  type bindingDeclInfo struct {
  2218  	names map[string]bool // names bound by the binding decl; possibly empty
  2219  	stmt  ast.Stmt        // the binding decl itself
  2220  }
  2221  
  2222  // createBindingDecl constructs a "binding decl" that implements
  2223  // parameter assignment and declares any named result variables
  2224  // referenced by the callee. It returns nil if there were no
  2225  // unsubstituted parameters.
  2226  //
  2227  // It may not always be possible to create the decl (e.g. due to
  2228  // shadowing), in which case it also returns nil; but if it succeeds,
  2229  // the declaration may be used by reduction strategies to relax the
  2230  // requirement that all parameters have been substituted.
  2231  //
  2232  // For example, a call:
  2233  //
  2234  //	f(a0, a1, a2)
  2235  //
  2236  // where:
  2237  //
  2238  //	func f(p0, p1 T0, p2 T1) { body }
  2239  //
  2240  // reduces to:
  2241  //
  2242  //	{
  2243  //	  var (
  2244  //	    p0, p1 T0 = a0, a1
  2245  //	    p2     T1 = a2
  2246  //	  )
  2247  //	  body
  2248  //	}
  2249  //
  2250  // so long as p0, p1 ∉ freevars(T1) or freevars(a2), and so on,
  2251  // because each spec is statically resolved in sequence and
  2252  // dynamically assigned in sequence. By contrast, all
  2253  // parameters are resolved simultaneously and assigned
  2254  // simultaneously.
  2255  //
  2256  // The pX names should already be blank ("_") if the parameter
  2257  // is unreferenced; this avoids "unreferenced local var" checks.
  2258  //
  2259  // Strategies may impose additional checks on return
  2260  // conversions, labels, defer, etc.
  2261  func createBindingDecl(logf logger, caller *Caller, args []*argument, calleeDecl *ast.FuncDecl, results []*paramInfo) *bindingDeclInfo {
  2262  	// Spread calls are tricky as they may not align with the
  2263  	// parameters' field groupings nor types.
  2264  	// For example, given
  2265  	//   func g() (int, string)
  2266  	// the call
  2267  	//   f(g())
  2268  	// is legal with these decls of f:
  2269  	//   func f(int, string)
  2270  	//   func f(x, y any)
  2271  	//   func f(x, y ...any)
  2272  	// TODO(adonovan): support binding decls for spread calls by
  2273  	// splitting parameter groupings as needed.
  2274  	if lastArg := last(args); lastArg != nil && lastArg.spread {
  2275  		logf("binding decls not yet supported for spread calls")
  2276  		return nil
  2277  	}
  2278  
  2279  	var (
  2280  		specs []ast.Spec
  2281  		names = make(map[string]bool) // names defined by previous specs
  2282  	)
  2283  	// shadow reports whether any name referenced by spec is
  2284  	// shadowed by a name declared by a previous spec (since,
  2285  	// unlike parameters, each spec of a var decl is within the
  2286  	// scope of the previous specs).
  2287  	shadow := func(spec *ast.ValueSpec) bool {
  2288  		// Compute union of free names of type and values
  2289  		// and detect shadowing. Values is the arguments
  2290  		// (caller syntax), so we can use type info.
  2291  		// But Type is the untyped callee syntax,
  2292  		// so we have to use a syntax-only algorithm.
  2293  		const includeComplitIdents = true
  2294  		free := free.Names(spec.Type, includeComplitIdents)
  2295  		for _, value := range spec.Values {
  2296  			for name := range freeVars(caller.Info, value) {
  2297  				free[name] = true
  2298  			}
  2299  		}
  2300  		for name := range free {
  2301  			if names[name] {
  2302  				logf("binding decl would shadow free name %q", name)
  2303  				return true
  2304  			}
  2305  		}
  2306  		for _, id := range spec.Names {
  2307  			if id.Name != "_" {
  2308  				names[id.Name] = true
  2309  			}
  2310  		}
  2311  		return false
  2312  	}
  2313  
  2314  	// parameters
  2315  	//
  2316  	// Bind parameters that were not eliminated through
  2317  	// substitution. (Non-nil arguments correspond to the
  2318  	// remaining parameters in calleeDecl.)
  2319  	var values []ast.Expr
  2320  	for _, arg := range args {
  2321  		if arg != nil {
  2322  			values = append(values, arg.expr)
  2323  		}
  2324  	}
  2325  	for _, field := range calleeDecl.Type.Params.List {
  2326  		// Each field (param group) becomes a ValueSpec.
  2327  		spec := &ast.ValueSpec{
  2328  			Names:  cleanNodes(field.Names),
  2329  			Type:   cleanNode(field.Type),
  2330  			Values: values[:len(field.Names)],
  2331  		}
  2332  		values = values[len(field.Names):]
  2333  		if shadow(spec) {
  2334  			return nil
  2335  		}
  2336  		specs = append(specs, spec)
  2337  	}
  2338  	assert(len(values) == 0, "args/params mismatch")
  2339  
  2340  	// results
  2341  	//
  2342  	// Add specs to declare any named result
  2343  	// variables that are referenced by the body.
  2344  	if calleeDecl.Type.Results != nil {
  2345  		resultIdx := 0
  2346  		for _, field := range calleeDecl.Type.Results.List {
  2347  			if field.Names == nil {
  2348  				resultIdx++
  2349  				continue // unnamed field
  2350  			}
  2351  			var names []*ast.Ident
  2352  			for _, id := range field.Names {
  2353  				if len(results[resultIdx].Refs) > 0 {
  2354  					names = append(names, id)
  2355  				}
  2356  				resultIdx++
  2357  			}
  2358  			if len(names) > 0 {
  2359  				spec := &ast.ValueSpec{
  2360  					Names: cleanNodes(names),
  2361  					Type:  cleanNode(field.Type),
  2362  				}
  2363  				if shadow(spec) {
  2364  					return nil
  2365  				}
  2366  				specs = append(specs, spec)
  2367  			}
  2368  		}
  2369  	}
  2370  
  2371  	if len(specs) == 0 {
  2372  		logf("binding decl not needed: all parameters substituted")
  2373  		return nil
  2374  	}
  2375  
  2376  	stmt := &ast.DeclStmt{
  2377  		Decl: &ast.GenDecl{
  2378  			Tok:   token.VAR,
  2379  			Specs: specs,
  2380  		},
  2381  	}
  2382  	logf("binding decl: %s", debugFormatNode(caller.Fset, stmt))
  2383  	return &bindingDeclInfo{names: names, stmt: stmt}
  2384  }
  2385  
  2386  // lookup does a symbol lookup in the lexical environment of the caller.
  2387  func (caller *Caller) lookup(name string) types.Object {
  2388  	pos := caller.Call.Pos()
  2389  	for _, n := range caller.path {
  2390  		if scope := scopeFor(caller.Info, n); scope != nil {
  2391  			if _, obj := scope.LookupParent(name, pos); obj != nil {
  2392  				return obj
  2393  			}
  2394  		}
  2395  	}
  2396  	return nil
  2397  }
  2398  
  2399  func scopeFor(info *types.Info, n ast.Node) *types.Scope {
  2400  	// The function body scope (containing not just params)
  2401  	// is associated with the function's type, not body.
  2402  	switch fn := n.(type) {
  2403  	case *ast.FuncDecl:
  2404  		n = fn.Type
  2405  	case *ast.FuncLit:
  2406  		n = fn.Type
  2407  	}
  2408  	return info.Scopes[n]
  2409  }
  2410  
  2411  // -- predicates over expressions --
  2412  
  2413  // freeVars returns the names of all free identifiers of e:
  2414  // those lexically referenced by it but not defined within it.
  2415  // (Fields and methods are not included.)
  2416  func freeVars(info *types.Info, e ast.Expr) map[string]bool {
  2417  	free := make(map[string]bool)
  2418  	ast.Inspect(e, func(n ast.Node) bool {
  2419  		if id, ok := n.(*ast.Ident); ok {
  2420  			// The isField check is so that we don't treat T{f: 0} as a ref to f.
  2421  			if obj, ok := info.Uses[id]; ok && !within(obj.Pos(), e) && !isField(obj) {
  2422  				free[obj.Name()] = true
  2423  			}
  2424  		}
  2425  		return true
  2426  	})
  2427  	return free
  2428  }
  2429  
  2430  // effects reports whether an expression might change the state of the
  2431  // program (through function calls and channel receives) and affect
  2432  // the evaluation of subsequent expressions.
  2433  func (st *state) effects(info *types.Info, expr ast.Expr) bool {
  2434  	effects := false
  2435  	ast.Inspect(expr, func(n ast.Node) bool {
  2436  		switch n := n.(type) {
  2437  		case *ast.FuncLit:
  2438  			return false // prune descent
  2439  
  2440  		case *ast.CallExpr:
  2441  			if info.Types[n.Fun].IsType() {
  2442  				// A conversion T(x) has only the effect of its operand.
  2443  			} else if !typesinternal.CallsPureBuiltin(info, n) {
  2444  				// A handful of built-ins have no effect
  2445  				// beyond those of their arguments.
  2446  				// All other calls (including append, copy, recover)
  2447  				// have unknown effects.
  2448  				//
  2449  				// As with 'pure', there is room for
  2450  				// improvement by inspecting the callee.
  2451  				effects = true
  2452  			}
  2453  
  2454  		case *ast.UnaryExpr:
  2455  			if n.Op == token.ARROW { // <-ch
  2456  				effects = true
  2457  			}
  2458  		}
  2459  		return true
  2460  	})
  2461  
  2462  	// Even if consideration of effects is not desired,
  2463  	// we continue to compute, log, and discard them.
  2464  	if st.opts.IgnoreEffects && effects {
  2465  		effects = false
  2466  		st.opts.Logf("ignoring potential effects of argument %s",
  2467  			debugFormatNode(st.caller.Fset, expr))
  2468  	}
  2469  
  2470  	return effects
  2471  }
  2472  
  2473  // pure reports whether an expression has the same result no matter
  2474  // when it is executed relative to other expressions, so it can be
  2475  // commuted with any other expression or statement without changing
  2476  // its meaning.
  2477  //
  2478  // An expression is considered impure if it reads the contents of any
  2479  // variable, with the exception of "single assignment" local variables
  2480  // (as classified by the provided callback), which are never updated
  2481  // after their initialization.
  2482  //
  2483  // Pure does not imply duplicable: for example, new(T) and T{} are
  2484  // pure expressions but both return a different value each time they
  2485  // are evaluated, so they are not safe to duplicate.
  2486  //
  2487  // Purity does not imply freedom from run-time panics. We assume that
  2488  // target programs do not encounter run-time panics nor depend on them
  2489  // for correct operation.
  2490  //
  2491  // TODO(adonovan): add unit tests of this function.
  2492  func pure(info *types.Info, assign1 func(*types.Var) bool, e ast.Expr) bool {
  2493  	var pure func(e ast.Expr) bool
  2494  	pure = func(e ast.Expr) bool {
  2495  		switch e := e.(type) {
  2496  		case *ast.ParenExpr:
  2497  			return pure(e.X)
  2498  
  2499  		case *ast.Ident:
  2500  			if v, ok := info.Uses[e].(*types.Var); ok {
  2501  				// In general variables are impure
  2502  				// as they may be updated, but
  2503  				// single-assignment local variables
  2504  				// never change value.
  2505  				//
  2506  				// We assume all package-level variables
  2507  				// may be updated, but for non-exported
  2508  				// ones we could do better by analyzing
  2509  				// the complete package.
  2510  				return !isPkgLevel(v) && assign1(v)
  2511  			}
  2512  
  2513  			// All other kinds of reference are pure.
  2514  			return true
  2515  
  2516  		case *ast.FuncLit:
  2517  			// A function literal may allocate a closure that
  2518  			// references mutable variables, but mutation
  2519  			// cannot be observed without calling the function,
  2520  			// and calls are considered impure.
  2521  			return true
  2522  
  2523  		case *ast.BasicLit:
  2524  			return true
  2525  
  2526  		case *ast.UnaryExpr: // + - ! ^ & but not <-
  2527  			return e.Op != token.ARROW && pure(e.X)
  2528  
  2529  		case *ast.BinaryExpr: // arithmetic, shifts, comparisons, &&/||
  2530  			return pure(e.X) && pure(e.Y)
  2531  
  2532  		case *ast.CallExpr:
  2533  			// A conversion is as pure as its operand.
  2534  			if info.Types[e.Fun].IsType() {
  2535  				return pure(e.Args[0])
  2536  			}
  2537  
  2538  			// Calls to some built-ins are as pure as their arguments.
  2539  			if typesinternal.CallsPureBuiltin(info, e) {
  2540  				for _, arg := range e.Args {
  2541  					if !pure(arg) {
  2542  						return false
  2543  					}
  2544  				}
  2545  				return true
  2546  			}
  2547  
  2548  			// All other calls are impure, so we can
  2549  			// reject them without even looking at e.Fun.
  2550  			//
  2551  			// More sophisticated analysis could infer purity in
  2552  			// commonly used functions such as strings.Contains;
  2553  			// perhaps we could offer the client a hook so that
  2554  			// go/analysis-based implementation could exploit the
  2555  			// results of a purity analysis. But that would make
  2556  			// the inliner's choices harder to explain.
  2557  			return false
  2558  
  2559  		case *ast.CompositeLit:
  2560  			// T{...} is as pure as its elements.
  2561  			for _, elt := range e.Elts {
  2562  				if kv, ok := elt.(*ast.KeyValueExpr); ok {
  2563  					if !pure(kv.Value) {
  2564  						return false
  2565  					}
  2566  					if id, ok := kv.Key.(*ast.Ident); ok {
  2567  						if v, ok := info.Uses[id].(*types.Var); ok && v.IsField() {
  2568  							continue // struct {field: value}
  2569  						}
  2570  					}
  2571  					// map/slice/array {key: value}
  2572  					if !pure(kv.Key) {
  2573  						return false
  2574  					}
  2575  
  2576  				} else if !pure(elt) {
  2577  					return false
  2578  				}
  2579  			}
  2580  			return true
  2581  
  2582  		case *ast.SelectorExpr:
  2583  			if seln, ok := info.Selections[e]; ok {
  2584  				// See types.SelectionKind for background.
  2585  				switch seln.Kind() {
  2586  				case types.MethodExpr:
  2587  					// A method expression T.f acts like a
  2588  					// reference to a func decl, so it is pure.
  2589  					return true
  2590  
  2591  				case types.MethodVal, types.FieldVal:
  2592  					// A field or method selection x.f is pure
  2593  					// if x is pure and the selection does
  2594  					// not indirect a pointer.
  2595  					return !indirectSelection(seln) && pure(e.X)
  2596  
  2597  				default:
  2598  					panic(seln)
  2599  				}
  2600  			} else {
  2601  				// A qualified identifier is
  2602  				// treated like an unqualified one.
  2603  				return pure(e.Sel)
  2604  			}
  2605  
  2606  		case *ast.StarExpr:
  2607  			return false // *ptr depends on the state of the heap
  2608  
  2609  		default:
  2610  			return false
  2611  		}
  2612  	}
  2613  	return pure(e)
  2614  }
  2615  
  2616  // duplicable reports whether it is appropriate for the expression to
  2617  // be freely duplicated.
  2618  //
  2619  // Given the declaration
  2620  //
  2621  //	func f(x T) T { return x + g() + x }
  2622  //
  2623  // an argument y is considered duplicable if we would wish to see a
  2624  // call f(y) simplified to y+g()+y. This is true for identifiers,
  2625  // integer literals, unary negation, and selectors x.f where x is not
  2626  // a pointer. But we would not wish to duplicate expressions that:
  2627  // - have side effects (e.g. nearly all calls),
  2628  // - are not referentially transparent (e.g. &T{}, ptr.field, *ptr), or
  2629  // - are long (e.g. "huge string literal").
  2630  func duplicable(info *types.Info, e ast.Expr) bool {
  2631  	switch e := e.(type) {
  2632  	case *ast.ParenExpr:
  2633  		return duplicable(info, e.X)
  2634  
  2635  	case *ast.Ident:
  2636  		return true
  2637  
  2638  	case *ast.BasicLit:
  2639  		v := info.Types[e].Value
  2640  		switch e.Kind {
  2641  		case token.INT:
  2642  			return true // any int
  2643  		case token.STRING:
  2644  			return consteq(v, kZeroString) // only ""
  2645  		case token.FLOAT:
  2646  			return consteq(v, kZeroFloat) || consteq(v, kOneFloat) // only 0.0 or 1.0
  2647  		}
  2648  
  2649  	case *ast.UnaryExpr: // e.g. +1, -1
  2650  		return (e.Op == token.ADD || e.Op == token.SUB) && duplicable(info, e.X)
  2651  
  2652  	case *ast.CompositeLit:
  2653  		// Empty struct or array literals T{} are duplicable.
  2654  		// (Non-empty literals are too verbose, and slice/map
  2655  		// literals allocate indirect variables.)
  2656  		if len(e.Elts) == 0 {
  2657  			switch info.TypeOf(e).Underlying().(type) {
  2658  			case *types.Struct, *types.Array:
  2659  				return true
  2660  			}
  2661  		}
  2662  		return false
  2663  
  2664  	case *ast.CallExpr:
  2665  		// Treat type conversions as duplicable if they do not observably allocate.
  2666  		// The only cases of observable allocations are
  2667  		// the `[]byte(string)` and `[]rune(string)` conversions.
  2668  		//
  2669  		// Duplicating string([]byte) conversions increases
  2670  		// allocation but doesn't change behavior, but the
  2671  		// reverse, []byte(string), allocates a distinct array,
  2672  		// which is observable.
  2673  
  2674  		if !info.Types[e.Fun].IsType() { // check whether e.Fun is a type conversion
  2675  			return false
  2676  		}
  2677  
  2678  		fun := info.TypeOf(e.Fun)
  2679  		arg := info.TypeOf(e.Args[0])
  2680  
  2681  		switch fun := fun.Underlying().(type) {
  2682  		case *types.Slice:
  2683  			// Do not mark []byte(string) and []rune(string) as duplicable.
  2684  			elem, ok := fun.Elem().Underlying().(*types.Basic)
  2685  			if ok && (elem.Kind() == types.Rune || elem.Kind() == types.Byte) {
  2686  				from, ok := arg.Underlying().(*types.Basic)
  2687  				isString := ok && from.Info()&types.IsString != 0
  2688  				return !isString
  2689  			}
  2690  		case *types.TypeParam:
  2691  			return false // be conservative
  2692  		}
  2693  		return true
  2694  
  2695  	case *ast.SelectorExpr:
  2696  		if seln, ok := info.Selections[e]; ok {
  2697  			// A field or method selection x.f is referentially
  2698  			// transparent if it does not indirect a pointer.
  2699  			return !indirectSelection(seln)
  2700  		}
  2701  		// A qualified identifier pkg.Name is referentially transparent.
  2702  		return true
  2703  	}
  2704  	return false
  2705  }
  2706  
  2707  func consteq(x, y constant.Value) bool {
  2708  	return constant.Compare(x, token.EQL, y)
  2709  }
  2710  
  2711  var (
  2712  	kZeroInt    = constant.MakeInt64(0)
  2713  	kZeroString = constant.MakeString("")
  2714  	kZeroFloat  = constant.MakeFloat64(0.0)
  2715  	kOneFloat   = constant.MakeFloat64(1.0)
  2716  )
  2717  
  2718  // -- inline helpers --
  2719  
  2720  func assert(cond bool, msg string) {
  2721  	if !cond {
  2722  		panic(msg)
  2723  	}
  2724  }
  2725  
  2726  // blanks returns a slice of n > 0 blank identifiers.
  2727  func blanks[E ast.Expr](n int) []E {
  2728  	if n == 0 {
  2729  		panic("blanks(0)")
  2730  	}
  2731  	res := make([]E, n)
  2732  	for i := range res {
  2733  		res[i] = ast.Expr(makeIdent("_")).(E) // ugh
  2734  	}
  2735  	return res
  2736  }
  2737  
  2738  func makeIdent(name string) *ast.Ident {
  2739  	return &ast.Ident{Name: name}
  2740  }
  2741  
  2742  // importedPkgName returns the PkgName object declared by an ImportSpec.
  2743  // TODO(adonovan): make this a method of types.Info (#62037).
  2744  func importedPkgName(info *types.Info, imp *ast.ImportSpec) (*types.PkgName, bool) {
  2745  	var obj types.Object
  2746  	if imp.Name != nil {
  2747  		obj = info.Defs[imp.Name]
  2748  	} else {
  2749  		obj = info.Implicits[imp]
  2750  	}
  2751  	pkgname, ok := obj.(*types.PkgName)
  2752  	return pkgname, ok
  2753  }
  2754  
  2755  func isPkgLevel(obj types.Object) bool {
  2756  	// TODO(adonovan): consider using the simpler obj.Parent() ==
  2757  	// obj.Pkg().Scope() instead. But be sure to test carefully
  2758  	// with instantiations of generics.
  2759  	return obj.Pkg().Scope().Lookup(obj.Name()) == obj
  2760  }
  2761  
  2762  // callContext returns the two nodes immediately enclosing the call
  2763  // (specified as a PathEnclosingInterval), ignoring parens.
  2764  func callContext(callPath []ast.Node) (parent, grandparent ast.Node) {
  2765  	_ = callPath[0].(*ast.CallExpr) // sanity check
  2766  	for _, n := range callPath[1:] {
  2767  		if !is[*ast.ParenExpr](n) {
  2768  			if parent == nil {
  2769  				parent = n
  2770  			} else {
  2771  				return parent, n
  2772  			}
  2773  		}
  2774  	}
  2775  	return parent, nil
  2776  }
  2777  
  2778  // hasLabelConflict reports whether the set of labels of the function
  2779  // enclosing the call (specified as a PathEnclosingInterval)
  2780  // intersects with the set of callee labels.
  2781  func hasLabelConflict(callPath []ast.Node, calleeLabels []string) bool {
  2782  	labels := callerLabels(callPath)
  2783  	for _, label := range calleeLabels {
  2784  		if labels[label] {
  2785  			return true // conflict
  2786  		}
  2787  	}
  2788  	return false
  2789  }
  2790  
  2791  // callerLabels returns the set of control labels in the function (if
  2792  // any) enclosing the call (specified as a PathEnclosingInterval).
  2793  func callerLabels(callPath []ast.Node) map[string]bool {
  2794  	var callerBody *ast.BlockStmt
  2795  	switch f := callerFunc(callPath).(type) {
  2796  	case *ast.FuncDecl:
  2797  		callerBody = f.Body
  2798  	case *ast.FuncLit:
  2799  		callerBody = f.Body
  2800  	}
  2801  	var labels map[string]bool
  2802  	if callerBody != nil {
  2803  		ast.Inspect(callerBody, func(n ast.Node) bool {
  2804  			switch n := n.(type) {
  2805  			case *ast.FuncLit:
  2806  				return false // prune traversal
  2807  			case *ast.LabeledStmt:
  2808  				if labels == nil {
  2809  					labels = make(map[string]bool)
  2810  				}
  2811  				labels[n.Label.Name] = true
  2812  			}
  2813  			return true
  2814  		})
  2815  	}
  2816  	return labels
  2817  }
  2818  
  2819  // callerFunc returns the innermost Func{Decl,Lit} node enclosing the
  2820  // call (specified as a PathEnclosingInterval).
  2821  func callerFunc(callPath []ast.Node) ast.Node {
  2822  	_ = callPath[0].(*ast.CallExpr) // sanity check
  2823  	for _, n := range callPath[1:] {
  2824  		if is[*ast.FuncDecl](n) || is[*ast.FuncLit](n) {
  2825  			return n
  2826  		}
  2827  	}
  2828  	return nil
  2829  }
  2830  
  2831  // callStmt reports whether the function call (specified
  2832  // as a PathEnclosingInterval) appears within an ExprStmt,
  2833  // and returns it if so.
  2834  //
  2835  // If unrestricted, callStmt returns nil if the ExprStmt f() appears
  2836  // in a restricted context (such as "if f(); cond {") where it cannot
  2837  // be replaced by an arbitrary statement. (See "statement theory".)
  2838  func callStmt(callPath []ast.Node, unrestricted bool) *ast.ExprStmt {
  2839  	parent, _ := callContext(callPath)
  2840  	stmt, ok := parent.(*ast.ExprStmt)
  2841  	if ok && unrestricted {
  2842  		switch callPath[slices.Index(callPath, ast.Node(stmt))+1].(type) {
  2843  		case *ast.LabeledStmt,
  2844  			*ast.BlockStmt,
  2845  			*ast.CaseClause,
  2846  			*ast.CommClause:
  2847  			// unrestricted
  2848  		default:
  2849  			// TODO(adonovan): handle restricted
  2850  			// XYZStmt.Init contexts (but not ForStmt.Post)
  2851  			// by creating a block around the if/for/switch:
  2852  			// "if f(); cond {"  ->  "{ stmts; if cond {"
  2853  
  2854  			return nil // restricted
  2855  		}
  2856  	}
  2857  	return stmt
  2858  }
  2859  
  2860  // Statement theory
  2861  //
  2862  // These are all the places a statement may appear in the AST:
  2863  //
  2864  // LabeledStmt.Stmt       Stmt      -- any
  2865  // BlockStmt.List       []Stmt      -- any (but see switch/select)
  2866  // IfStmt.Init            Stmt?     -- simple
  2867  // IfStmt.Body            BlockStmt
  2868  // IfStmt.Else            Stmt?     -- IfStmt or BlockStmt
  2869  // CaseClause.Body      []Stmt      -- any
  2870  // SwitchStmt.Init        Stmt?     -- simple
  2871  // SwitchStmt.Body        BlockStmt -- CaseClauses only
  2872  // TypeSwitchStmt.Init    Stmt?     -- simple
  2873  // TypeSwitchStmt.Assign  Stmt      -- AssignStmt(TypeAssertExpr) or ExprStmt(TypeAssertExpr)
  2874  // TypeSwitchStmt.Body    BlockStmt -- CaseClauses only
  2875  // CommClause.Comm        Stmt?     -- SendStmt or ExprStmt(UnaryExpr) or AssignStmt(UnaryExpr)
  2876  // CommClause.Body      []Stmt      -- any
  2877  // SelectStmt.Body        BlockStmt -- CommClauses only
  2878  // ForStmt.Init           Stmt?     -- simple
  2879  // ForStmt.Post           Stmt?     -- simple
  2880  // ForStmt.Body           BlockStmt
  2881  // RangeStmt.Body         BlockStmt
  2882  //
  2883  // simple = AssignStmt | SendStmt | IncDecStmt | ExprStmt.
  2884  //
  2885  // A BlockStmt cannot replace an ExprStmt in
  2886  // {If,Switch,TypeSwitch}Stmt.Init or ForStmt.Post.
  2887  // That is allowed only within:
  2888  //   LabeledStmt.Stmt       Stmt
  2889  //   BlockStmt.List       []Stmt
  2890  //   CaseClause.Body      []Stmt
  2891  //   CommClause.Body      []Stmt
  2892  
  2893  // replaceNode performs a destructive update of the tree rooted at
  2894  // root, replacing each occurrence of "from" with "to". If to is nil and
  2895  // the element is within a slice, the slice element is removed.
  2896  //
  2897  // The root itself cannot be replaced; an attempt will panic.
  2898  //
  2899  // This function must not be called on the caller's syntax tree.
  2900  //
  2901  // TODO(adonovan): polish this up and move it to astutil package.
  2902  // TODO(adonovan): needs a unit test.
  2903  func replaceNode(root ast.Node, from, to ast.Node) {
  2904  	if from == nil {
  2905  		panic("from == nil")
  2906  	}
  2907  	if reflect.ValueOf(from).IsNil() {
  2908  		panic(fmt.Sprintf("from == (%T)(nil)", from))
  2909  	}
  2910  	if from == root {
  2911  		panic("from == root")
  2912  	}
  2913  	found := false
  2914  	var parent reflect.Value // parent variable of interface type, containing a pointer
  2915  	var visit func(reflect.Value)
  2916  	visit = func(v reflect.Value) {
  2917  		switch v.Kind() {
  2918  		case reflect.Pointer:
  2919  			if v.Interface() == from {
  2920  				found = true
  2921  
  2922  				// If v is a struct field or array element
  2923  				// (e.g. Field.Comment or Field.Names[i])
  2924  				// then it is addressable (a pointer variable).
  2925  				//
  2926  				// But if it was the value an interface
  2927  				// (e.g. *ast.Ident within ast.Node)
  2928  				// then it is non-addressable, and we need
  2929  				// to set the enclosing interface (parent).
  2930  				if !v.CanAddr() {
  2931  					v = parent
  2932  				}
  2933  
  2934  				// to=nil => use zero value
  2935  				var toV reflect.Value
  2936  				if to != nil {
  2937  					toV = reflect.ValueOf(to)
  2938  				} else {
  2939  					toV = reflect.Zero(v.Type()) // e.g. ast.Expr(nil)
  2940  				}
  2941  				v.Set(toV)
  2942  
  2943  			} else if !v.IsNil() {
  2944  				switch v.Interface().(type) {
  2945  				case *ast.Object, *ast.Scope:
  2946  					// Skip fields of types potentially involved in cycles.
  2947  				default:
  2948  					visit(v.Elem())
  2949  				}
  2950  			}
  2951  
  2952  		case reflect.Struct:
  2953  			for i := range v.Type().NumField() {
  2954  				visit(v.Field(i))
  2955  			}
  2956  
  2957  		case reflect.Slice:
  2958  			compact := false
  2959  			for i := range v.Len() {
  2960  				visit(v.Index(i))
  2961  				if v.Index(i).IsNil() {
  2962  					compact = true
  2963  				}
  2964  			}
  2965  			if compact {
  2966  				// Elements were deleted. Eliminate nils.
  2967  				// (Do this is a second pass to avoid
  2968  				// unnecessary writes in the common case.)
  2969  				j := 0
  2970  				for i := range v.Len() {
  2971  					if !v.Index(i).IsNil() {
  2972  						v.Index(j).Set(v.Index(i))
  2973  						j++
  2974  					}
  2975  				}
  2976  				v.SetLen(j)
  2977  			}
  2978  		case reflect.Interface:
  2979  			parent = v
  2980  			visit(v.Elem())
  2981  
  2982  		case reflect.Array, reflect.Chan, reflect.Func, reflect.Map, reflect.UnsafePointer:
  2983  			panic(v) // unreachable in AST
  2984  		default:
  2985  			// bool, string, number: nop
  2986  		}
  2987  		parent = reflect.Value{}
  2988  	}
  2989  	visit(reflect.ValueOf(root))
  2990  	if !found {
  2991  		panic(fmt.Sprintf("%T not found", from))
  2992  	}
  2993  }
  2994  
  2995  // cleanNode returns a clone of node with positions cleared.
  2996  //
  2997  // It should be used for any callee nodes that are formatted using the caller
  2998  // file set.
  2999  func cleanNode[T ast.Node](node T) T {
  3000  	clone := internalastutil.CloneNode(node)
  3001  	clearPositions(clone)
  3002  	return clone
  3003  }
  3004  
  3005  func cleanNodes[T ast.Node](nodes []T) []T {
  3006  	var clean []T
  3007  	for _, node := range nodes {
  3008  		clean = append(clean, cleanNode(node))
  3009  	}
  3010  	return clean
  3011  }
  3012  
  3013  // clearPositions destroys token.Pos information within the tree rooted at root,
  3014  // as positions in callee trees may cause caller comments to be emitted prematurely.
  3015  //
  3016  // In general it isn't safe to clear a valid Pos because some of them
  3017  // (e.g. CallExpr.Ellipsis, TypeSpec.Assign) are significant to
  3018  // go/printer, so this function sets each non-zero Pos to 1, which
  3019  // suffices to avoid advancing the printer's comment cursor.
  3020  //
  3021  // This function mutates its argument; do not invoke on caller syntax.
  3022  //
  3023  // TODO(adonovan): remove this horrendous workaround when #20744 is finally fixed.
  3024  func clearPositions(root ast.Node) {
  3025  	posType := reflect.TypeFor[token.Pos]()
  3026  	ast.Inspect(root, func(n ast.Node) bool {
  3027  		if n != nil {
  3028  			v := reflect.ValueOf(n).Elem() // deref the pointer to struct
  3029  			fields := v.Type().NumField()
  3030  			for i := range fields {
  3031  				f := v.Field(i)
  3032  				// Clearing Pos arbitrarily is destructive,
  3033  				// as its presence may be semantically significant
  3034  				// (e.g. CallExpr.Ellipsis, TypeSpec.Assign)
  3035  				// or affect formatting preferences (e.g. GenDecl.Lparen).
  3036  				//
  3037  				// Note: for proper formatting, it may be necessary to be selective
  3038  				// about which positions we set to 1 vs which we set to token.NoPos.
  3039  				// (e.g. we can set most to token.NoPos, save the few that are
  3040  				// significant).
  3041  				if f.Type() == posType {
  3042  					if f.Interface() != token.NoPos {
  3043  						f.Set(reflect.ValueOf(token.Pos(1)))
  3044  					}
  3045  				}
  3046  			}
  3047  		}
  3048  		return true
  3049  	})
  3050  }
  3051  
  3052  // findIdent finds the Ident beneath root that has the given pos.
  3053  // It returns the path to the ident (excluding the ident), and the ident
  3054  // itself, where the path is the sequence of ast.Nodes encountered in a
  3055  // depth-first search to find ident.
  3056  func findIdent(root ast.Node, pos token.Pos) ([]ast.Node, *ast.Ident) {
  3057  	// TODO(adonovan): opt: skip subtrees that don't contain pos.
  3058  	var (
  3059  		path  []ast.Node
  3060  		found *ast.Ident
  3061  	)
  3062  	ast.Inspect(root, func(n ast.Node) bool {
  3063  		if found != nil {
  3064  			return false
  3065  		}
  3066  		if n == nil {
  3067  			path = path[:len(path)-1]
  3068  			return false
  3069  		}
  3070  		if id, ok := n.(*ast.Ident); ok {
  3071  			if id.Pos() == pos {
  3072  				found = id
  3073  				return true
  3074  			}
  3075  		}
  3076  		path = append(path, n)
  3077  		return true
  3078  	})
  3079  	if found == nil {
  3080  		panic(fmt.Sprintf("findIdent %d not found in %s",
  3081  			pos, debugFormatNode(token.NewFileSet(), root)))
  3082  	}
  3083  	return path, found
  3084  }
  3085  
  3086  func prepend[T any](elem T, slice ...T) []T {
  3087  	return append([]T{elem}, slice...)
  3088  }
  3089  
  3090  // debugFormatNode formats a node or returns a formatting error.
  3091  // Its sloppy treatment of errors is appropriate only for logging.
  3092  func debugFormatNode(fset *token.FileSet, n ast.Node) string {
  3093  	var out strings.Builder
  3094  	if err := format.Node(&out, fset, n); err != nil {
  3095  		out.WriteString(err.Error())
  3096  	}
  3097  	return out.String()
  3098  }
  3099  
  3100  func shallowCopy[T any](ptr *T) *T {
  3101  	copy := *ptr
  3102  	return &copy
  3103  }
  3104  
  3105  // ∀
  3106  func forall[T any](list []T, f func(i int, x T) bool) bool {
  3107  	for i, x := range list {
  3108  		if !f(i, x) {
  3109  			return false
  3110  		}
  3111  	}
  3112  	return true
  3113  }
  3114  
  3115  // ∃
  3116  func exists[T any](list []T, f func(i int, x T) bool) bool {
  3117  	for i, x := range list {
  3118  		if f(i, x) {
  3119  			return true
  3120  		}
  3121  	}
  3122  	return false
  3123  }
  3124  
  3125  // last returns the last element of a slice, or zero if empty.
  3126  func last[T any](slice []T) T {
  3127  	n := len(slice)
  3128  	if n > 0 {
  3129  		return slice[n-1]
  3130  	}
  3131  	return *new(T)
  3132  }
  3133  
  3134  // declares returns the set of lexical names declared by a
  3135  // sequence of statements from the same block, excluding sub-blocks.
  3136  // (Lexical names do not include control labels.)
  3137  func declares(stmts []ast.Stmt) map[string]bool {
  3138  	names := make(map[string]bool)
  3139  	for _, stmt := range stmts {
  3140  		switch stmt := stmt.(type) {
  3141  		case *ast.DeclStmt:
  3142  			for _, spec := range stmt.Decl.(*ast.GenDecl).Specs {
  3143  				switch spec := spec.(type) {
  3144  				case *ast.ValueSpec:
  3145  					for _, id := range spec.Names {
  3146  						names[id.Name] = true
  3147  					}
  3148  				case *ast.TypeSpec:
  3149  					names[spec.Name.Name] = true
  3150  				}
  3151  			}
  3152  
  3153  		case *ast.AssignStmt:
  3154  			if stmt.Tok == token.DEFINE {
  3155  				for _, lhs := range stmt.Lhs {
  3156  					names[lhs.(*ast.Ident).Name] = true
  3157  				}
  3158  			}
  3159  		}
  3160  	}
  3161  	delete(names, "_")
  3162  	return names
  3163  }
  3164  
  3165  // A importNameFunc is used to query local import names in the caller, in a
  3166  // particular shadowing context.
  3167  //
  3168  // The shadow map contains additional names shadowed in the inlined code, at
  3169  // the position the local import name is to be used. The shadow map only needs
  3170  // to contain newly introduced names in the inlined code; names shadowed at the
  3171  // caller are handled automatically.
  3172  type importNameFunc = func(pkgPath string, shadow shadowMap) string
  3173  
  3174  // assignStmts rewrites a statement assigning the results of a call into zero
  3175  // or more statements that assign its return operands, or (nil, false) if no
  3176  // such rewrite is possible. The set of bindings created by the result of
  3177  // assignStmts is the same as the set of bindings created by the callerStmt.
  3178  //
  3179  // The callee must contain exactly one return statement.
  3180  //
  3181  // This is (once again) a surprisingly complex task. For example, depending on
  3182  // types and existing bindings, the assignment
  3183  //
  3184  //	a, b := f()
  3185  //
  3186  // could be rewritten as:
  3187  //
  3188  //	a, b := 1, 2
  3189  //
  3190  // but may need to be written as:
  3191  //
  3192  //	a, b := int8(1), int32(2)
  3193  //
  3194  // In the case where the return statement within f is a spread call to another
  3195  // function g(), we cannot explicitly convert the return values inline, and so
  3196  // it may be necessary to split the declaration and assignment of variables
  3197  // into separate statements:
  3198  //
  3199  //	a, b := g()
  3200  //
  3201  // or
  3202  //
  3203  //	var a int32
  3204  //	a, b = g()
  3205  //
  3206  // or
  3207  //
  3208  //	var (
  3209  //		a int8
  3210  //		b int32
  3211  //	)
  3212  //	a, b = g()
  3213  //
  3214  // Note: assignStmts may return (nil, true) if it determines that the rewritten
  3215  // assignment consists only of _ = nil assignments.
  3216  func (st *state) assignStmts(callerStmt *ast.AssignStmt, returnOperands []ast.Expr, importName importNameFunc) ([]ast.Stmt, bool) {
  3217  	logf, caller, callee := st.opts.Logf, st.caller, &st.callee.impl
  3218  
  3219  	assert(len(callee.Returns) == 1, "unexpected multiple returns")
  3220  	resultInfo := callee.Returns[0]
  3221  
  3222  	// When constructing assign statements, we need to make sure that we don't
  3223  	// modify types on the left-hand side, such as would happen if the type of a
  3224  	// RHS expression does not match the corresponding LHS type at the caller
  3225  	// (due to untyped conversion or interface widening).
  3226  	//
  3227  	// This turns out to be remarkably tricky to handle correctly.
  3228  	//
  3229  	// Substrategies below are labeled as `Substrategy <name>:`.
  3230  
  3231  	// Collect LHS information.
  3232  	var (
  3233  		lhs    []ast.Expr                                // shallow copy of the LHS slice, for mutation
  3234  		defs   = make([]*ast.Ident, len(callerStmt.Lhs)) // indexes in lhs of defining identifiers
  3235  		blanks = make([]bool, len(callerStmt.Lhs))       // indexes in lhs of blank identifiers
  3236  		byType typeutil.Map                              // map of distinct types -> indexes, for writing specs later
  3237  	)
  3238  	for i, expr := range callerStmt.Lhs {
  3239  		lhs = append(lhs, expr)
  3240  		if name, ok := expr.(*ast.Ident); ok {
  3241  			if name.Name == "_" {
  3242  				blanks[i] = true
  3243  				continue // no type
  3244  			}
  3245  
  3246  			if obj, isDef := caller.Info.Defs[name]; isDef {
  3247  				defs[i] = name
  3248  				typ := obj.Type()
  3249  				idxs, _ := byType.At(typ).([]int)
  3250  				idxs = append(idxs, i)
  3251  				byType.Set(typ, idxs)
  3252  			}
  3253  		}
  3254  	}
  3255  
  3256  	// Collect RHS information
  3257  	//
  3258  	// The RHS is either a parallel assignment or spread assignment, but by
  3259  	// looping over both callerStmt.Rhs and returnOperands we handle both.
  3260  	var (
  3261  		rhs             []ast.Expr              // new RHS of assignment, owned by the inliner
  3262  		callIdx         = -1                    // index of the call among the original RHS
  3263  		nilBlankAssigns = make(map[int]unit)    // indexes in rhs of _ = nil assignments, which can be deleted
  3264  		freeNames       = make(map[string]bool) // free(ish) names among rhs expressions
  3265  		nonTrivial      = make(map[int]bool)    // indexes in rhs of nontrivial result conversions
  3266  	)
  3267  	const includeComplitIdents = true
  3268  
  3269  	for i, expr := range callerStmt.Rhs {
  3270  		if expr == caller.Call {
  3271  			assert(callIdx == -1, "malformed (duplicative) AST")
  3272  			callIdx = i
  3273  			for j, returnOperand := range returnOperands {
  3274  				maps.Copy(freeNames, free.Names(returnOperand, includeComplitIdents))
  3275  				rhs = append(rhs, returnOperand)
  3276  				if resultInfo[j]&nonTrivialResult != 0 {
  3277  					nonTrivial[i+j] = true
  3278  				}
  3279  				if blanks[i+j] && resultInfo[j]&untypedNilResult != 0 {
  3280  					nilBlankAssigns[i+j] = unit{}
  3281  				}
  3282  			}
  3283  		} else {
  3284  			// We must clone before clearing positions, since e came from the caller.
  3285  			expr = internalastutil.CloneNode(expr)
  3286  			clearPositions(expr)
  3287  			maps.Copy(freeNames, free.Names(expr, includeComplitIdents))
  3288  			rhs = append(rhs, expr)
  3289  		}
  3290  	}
  3291  	assert(callIdx >= 0, "failed to find call in RHS")
  3292  
  3293  	// Substrategy "splice": Check to see if we can simply splice in the result
  3294  	// expressions from the callee, such as simplifying
  3295  	//
  3296  	//  x, y := f()
  3297  	//
  3298  	// to
  3299  	//
  3300  	//  x, y := e1, e2
  3301  	//
  3302  	// where the types of x and y match the types of e1 and e2.
  3303  	//
  3304  	// This works as long as we don't need to write any additional type
  3305  	// information.
  3306  	if len(nonTrivial) == 0 { // no non-trivial conversions to worry about
  3307  
  3308  		logf("substrategy: splice assignment")
  3309  		return []ast.Stmt{&ast.AssignStmt{
  3310  			Lhs:    lhs,
  3311  			Tok:    callerStmt.Tok,
  3312  			TokPos: callerStmt.TokPos,
  3313  			Rhs:    rhs,
  3314  		}}, true
  3315  	}
  3316  
  3317  	// Inlining techniques below will need to write type information in order to
  3318  	// preserve the correct types of LHS identifiers.
  3319  	//
  3320  	// typeExpr is a simple helper to write out type expressions. It currently
  3321  	// handles (possibly qualified) type names.
  3322  	//
  3323  	// TODO(rfindley):
  3324  	//   1. expand this to handle more type expressions.
  3325  	//   2. refactor to share logic with callee rewriting.
  3326  	universeAny := types.Universe.Lookup("any")
  3327  	typeExpr := func(typ types.Type, shadow shadowMap) ast.Expr {
  3328  		var (
  3329  			typeName string
  3330  			obj      *types.TypeName // nil for basic types
  3331  		)
  3332  		if tname := typesinternal.TypeNameFor(typ); tname != nil {
  3333  			obj = tname
  3334  			typeName = tname.Name()
  3335  		}
  3336  
  3337  		// Special case: check for universe "any".
  3338  		// TODO(golang/go#66921): this may become unnecessary if any becomes a proper alias.
  3339  		if typ == universeAny.Type() {
  3340  			typeName = "any"
  3341  		}
  3342  
  3343  		if typeName == "" {
  3344  			return nil
  3345  		}
  3346  
  3347  		if obj == nil || obj.Pkg() == nil || obj.Pkg() == caller.Types { // local type or builtin
  3348  			if shadow[typeName] != 0 {
  3349  				logf("cannot write shadowed type name %q", typeName)
  3350  				return nil
  3351  			}
  3352  			obj, _ := caller.lookup(typeName).(*types.TypeName)
  3353  			if obj != nil && types.Identical(obj.Type(), typ) {
  3354  				return ast.NewIdent(typeName)
  3355  			}
  3356  		} else if pkgName := importName(obj.Pkg().Path(), shadow); pkgName != "" {
  3357  			return &ast.SelectorExpr{
  3358  				X:   ast.NewIdent(pkgName),
  3359  				Sel: ast.NewIdent(typeName),
  3360  			}
  3361  		}
  3362  		return nil
  3363  	}
  3364  
  3365  	// Substrategy "spread": in the case of a spread call (func f() (T1, T2) return
  3366  	// g()), since we didn't hit the 'splice' substrategy, there must be some
  3367  	// non-declaring expression on the LHS. Simplify this by pre-declaring
  3368  	// variables, rewriting
  3369  	//
  3370  	//   x, y := f()
  3371  	//
  3372  	// to
  3373  	//
  3374  	//  var x int
  3375  	//  x, y = g()
  3376  	//
  3377  	// Which works as long as the predeclared variables do not overlap with free
  3378  	// names on the RHS.
  3379  	if len(rhs) != len(lhs) {
  3380  		assert(len(rhs) == 1 && len(returnOperands) == 1, "expected spread call")
  3381  
  3382  		for _, id := range defs {
  3383  			if id != nil && freeNames[id.Name] {
  3384  				// By predeclaring variables, we're changing them to be in scope of the
  3385  				// RHS. We can't do this if their names are free on the RHS.
  3386  				return nil, false
  3387  			}
  3388  		}
  3389  
  3390  		// Write out the specs, being careful to avoid shadowing free names in
  3391  		// their type expressions.
  3392  		var (
  3393  			specs    []ast.Spec
  3394  			specIdxs []int
  3395  			shadow   = make(shadowMap)
  3396  		)
  3397  		failed := false
  3398  		byType.Iterate(func(typ types.Type, v any) {
  3399  			if failed {
  3400  				return
  3401  			}
  3402  			idxs := v.([]int)
  3403  			specIdxs = append(specIdxs, idxs[0])
  3404  			texpr := typeExpr(typ, shadow)
  3405  			if texpr == nil {
  3406  				failed = true
  3407  				return
  3408  			}
  3409  			spec := &ast.ValueSpec{
  3410  				Type: texpr,
  3411  			}
  3412  			for _, idx := range idxs {
  3413  				spec.Names = append(spec.Names, ast.NewIdent(defs[idx].Name))
  3414  			}
  3415  			specs = append(specs, spec)
  3416  		})
  3417  		if failed {
  3418  			return nil, false
  3419  		}
  3420  		logf("substrategy: spread assignment")
  3421  		return []ast.Stmt{
  3422  			&ast.DeclStmt{
  3423  				Decl: &ast.GenDecl{
  3424  					Tok:   token.VAR,
  3425  					Specs: specs,
  3426  				},
  3427  			},
  3428  			&ast.AssignStmt{
  3429  				Lhs: callerStmt.Lhs,
  3430  				Tok: token.ASSIGN,
  3431  				Rhs: returnOperands,
  3432  			},
  3433  		}, true
  3434  	}
  3435  
  3436  	assert(len(lhs) == len(rhs), "mismatching LHS and RHS")
  3437  
  3438  	// Substrategy "convert": write out RHS expressions with explicit type conversions
  3439  	// as necessary, rewriting
  3440  	//
  3441  	//  x, y := f()
  3442  	//
  3443  	// to
  3444  	//
  3445  	//  x, y := 1, int32(2)
  3446  	//
  3447  	// As required to preserve types.
  3448  	//
  3449  	// In the special case of _ = nil, which is disallowed by the type checker
  3450  	// (since nil has no default type), we delete the assignment.
  3451  	var origIdxs []int // maps back to original indexes after lhs and rhs are pruned
  3452  	i := 0
  3453  	for j := range lhs {
  3454  		if _, ok := nilBlankAssigns[j]; !ok {
  3455  			lhs[i] = lhs[j]
  3456  			rhs[i] = rhs[j]
  3457  			origIdxs = append(origIdxs, j)
  3458  			i++
  3459  		}
  3460  	}
  3461  	lhs = lhs[:i]
  3462  	rhs = rhs[:i]
  3463  
  3464  	if len(lhs) == 0 {
  3465  		logf("trivial assignment after pruning nil blanks assigns")
  3466  		// After pruning, we have no remaining assignments.
  3467  		// Signal this by returning a non-nil slice of statements.
  3468  		return nil, true
  3469  	}
  3470  
  3471  	// Write out explicit conversions as necessary.
  3472  	//
  3473  	// A conversion is necessary if the LHS is being defined, and the RHS return
  3474  	// involved a nontrivial implicit conversion.
  3475  	for i, expr := range rhs {
  3476  		idx := origIdxs[i]
  3477  		if nonTrivial[idx] && defs[idx] != nil {
  3478  			typ := caller.Info.TypeOf(lhs[i])
  3479  			texpr := typeExpr(typ, nil)
  3480  			if texpr == nil {
  3481  				return nil, false
  3482  			}
  3483  			if _, ok := texpr.(*ast.StarExpr); ok {
  3484  				// TODO(rfindley): is this necessary? Doesn't the formatter add these parens?
  3485  				texpr = &ast.ParenExpr{X: texpr} // *T -> (*T)   so that (*T)(x) is valid
  3486  			}
  3487  			rhs[i] = &ast.CallExpr{
  3488  				Fun:  texpr,
  3489  				Args: []ast.Expr{expr},
  3490  			}
  3491  		}
  3492  	}
  3493  	logf("substrategy: convert assignment")
  3494  	return []ast.Stmt{&ast.AssignStmt{
  3495  		Lhs: lhs,
  3496  		Tok: callerStmt.Tok,
  3497  		Rhs: rhs,
  3498  	}}, true
  3499  }
  3500  
  3501  // tailCallSafeReturn reports whether the callee's return statements may be safely
  3502  // used to return from the function enclosing the caller (which must exist).
  3503  func tailCallSafeReturn(caller *Caller, calleeSymbol *types.Func, callee *gobCallee) bool {
  3504  	// It is safe if all callee returns involve only trivial conversions.
  3505  	if !hasNonTrivialReturn(callee.Returns) {
  3506  		return true
  3507  	}
  3508  
  3509  	var callerType types.Type
  3510  	// Find type of innermost function enclosing call.
  3511  	// (Beware: Caller.enclosingFunc is the outermost.)
  3512  loop:
  3513  	for _, n := range caller.path {
  3514  		switch f := n.(type) {
  3515  		case *ast.FuncDecl:
  3516  			callerType = caller.Info.ObjectOf(f.Name).Type()
  3517  			break loop
  3518  		case *ast.FuncLit:
  3519  			callerType = caller.Info.TypeOf(f)
  3520  			break loop
  3521  		}
  3522  	}
  3523  
  3524  	// Non-trivial return conversions in the callee are permitted
  3525  	// if the same non-trivial conversion would occur after inlining,
  3526  	// i.e. if the caller and callee results tuples are identical.
  3527  	callerResults := callerType.(*types.Signature).Results()
  3528  	calleeResults := calleeSymbol.Type().(*types.Signature).Results()
  3529  	return types.Identical(callerResults, calleeResults)
  3530  }
  3531  
  3532  // hasNonTrivialReturn reports whether any of the returns involve a nontrivial
  3533  // implicit conversion of a result expression.
  3534  func hasNonTrivialReturn(returnInfo [][]returnOperandFlags) bool {
  3535  	for _, resultInfo := range returnInfo {
  3536  		for _, r := range resultInfo {
  3537  			if r&nonTrivialResult != 0 {
  3538  				return true
  3539  			}
  3540  		}
  3541  	}
  3542  	return false
  3543  }
  3544  
  3545  type unit struct{} // for representing sets as maps
  3546  

View as plain text