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

View as plain text