// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package inline

import (
	"bytes"
	"fmt"
	"go/ast"
	"go/constant"
	"go/format"
	"go/parser"
	"go/printer"
	"go/token"
	"go/types"
	"maps"
	pathpkg "path"
	"reflect"
	"slices"
	"strconv"
	"strings"

	"golang.org/x/tools/go/ast/astutil"
	"golang.org/x/tools/go/types/typeutil"
	"golang.org/x/tools/internal/analysisinternal"
	internalastutil "golang.org/x/tools/internal/astutil"
	"golang.org/x/tools/internal/typeparams"
	"golang.org/x/tools/internal/typesinternal"
)

// A Caller describes the function call and its enclosing context.
//
// The client is responsible for populating this struct and passing it to Inline.
type Caller struct {
	Fset    *token.FileSet
	Types   *types.Package
	Info    *types.Info
	File    *ast.File
	Call    *ast.CallExpr
	Content []byte // source of file containing

	path          []ast.Node    // path from call to root of file syntax tree
	enclosingFunc *ast.FuncDecl // top-level function/method enclosing the call, if any
}

type logger = func(string, ...any)

// Options specifies parameters affecting the inliner algorithm.
// All fields are optional.
type Options struct {
	Logf          logger // log output function, records decision-making process
	IgnoreEffects bool   // ignore potential side effects of arguments (unsound)
}

// Result holds the result of code transformation.
type Result struct {
	Content     []byte // formatted, transformed content of caller file
	Literalized bool   // chosen strategy replaced callee() with func(){...}()

	// TODO(adonovan): provide an API for clients that want structured
	// output: a list of import additions and deletions plus one or more
	// localized diffs (or even AST transformations, though ownership and
	// mutation are tricky) near the call site.
}

// Inline inlines the called function (callee) into the function call (caller)
// and returns the updated, formatted content of the caller source file.
//
// Inline does not mutate any public fields of Caller or Callee.
func Inline(caller *Caller, callee *Callee, opts *Options) (*Result, error) {
	copy := *opts // shallow copy
	opts = &copy
	// Set default options.
	if opts.Logf == nil {
		opts.Logf = func(string, ...any) {}
	}

	st := &state{
		caller: caller,
		callee: callee,
		opts:   opts,
	}
	return st.inline()
}

// state holds the working state of the inliner.
type state struct {
	caller *Caller
	callee *Callee
	opts   *Options
}

func (st *state) inline() (*Result, error) {
	logf, caller, callee := st.opts.Logf, st.caller, st.callee

	logf("inline %s @ %v",
		debugFormatNode(caller.Fset, caller.Call),
		caller.Fset.PositionFor(caller.Call.Lparen, false))

	if !consistentOffsets(caller) {
		return nil, fmt.Errorf("internal error: caller syntax positions are inconsistent with file content (did you forget to use FileSet.PositionFor when computing the file name?)")
	}

	// Break the string literal so we can use inlining in this file. :)
	if ast.IsGenerated(caller.File) &&
		bytes.Contains(caller.Content, []byte("// Code generated by "+"cmd/cgo; DO NOT EDIT.")) {
		return nil, fmt.Errorf("cannot inline calls from files that import \"C\"")
	}

	res, err := st.inlineCall()
	if err != nil {
		return nil, err
	}

	// Replace the call (or some node that encloses it) by new syntax.
	assert(res.old != nil, "old is nil")
	assert(res.new != nil, "new is nil")

	// A single return operand inlined to a unary
	// expression context may need parens. Otherwise:
	//    func two() int { return 1+1 }
	//    print(-two())  =>  print(-1+1) // oops!
	//
	// Usually it is not necessary to insert ParenExprs
	// as the formatter is smart enough to insert them as
	// needed by the context. But the res.{old,new}
	// substitution is done by formatting res.new in isolation
	// and then splicing its text over res.old, so the
	// formatter doesn't see the parent node and cannot do
	// the right thing. (One solution would be to always
	// format the enclosing node of old, but that requires
	// non-lossy comment handling, #20744.)
	//
	// So, we must analyze the call's context
	// to see whether ambiguity is possible.
	// For example, if the context is x[y:z], then
	// the x subtree is subject to precedence ambiguity
	// (replacing x by p+q would give p+q[y:z] which is wrong)
	// but the y and z subtrees are safe.
	if needsParens(caller.path, res.old, res.new) {
		res.new = &ast.ParenExpr{X: res.new.(ast.Expr)}
	}

	// Some reduction strategies return a new block holding the
	// callee's statements. The block's braces may be elided when
	// there is no conflict between names declared in the block
	// with those declared by the parent block, and no risk of
	// a caller's goto jumping forward across a declaration.
	//
	// This elision is only safe when the ExprStmt is beneath a
	// BlockStmt, CaseClause.Body, or CommClause.Body;
	// (see "statement theory").
	//
	// The inlining analysis may have already determined that eliding braces is
	// safe. Otherwise, we analyze its safety here.
	elideBraces := res.elideBraces
	if !elideBraces {
		if newBlock, ok := res.new.(*ast.BlockStmt); ok {
			i := slices.Index(caller.path, res.old)
			parent := caller.path[i+1]
			var body []ast.Stmt
			switch parent := parent.(type) {
			case *ast.BlockStmt:
				body = parent.List
			case *ast.CommClause:
				body = parent.Body
			case *ast.CaseClause:
				body = parent.Body
			}
			if body != nil {
				callerNames := declares(body)

				// If BlockStmt is a function body,
				// include its receiver, params, and results.
				addFieldNames := func(fields *ast.FieldList) {
					if fields != nil {
						for _, field := range fields.List {
							for _, id := range field.Names {
								callerNames[id.Name] = true
							}
						}
					}
				}
				switch f := caller.path[i+2].(type) {
				case *ast.FuncDecl:
					addFieldNames(f.Recv)
					addFieldNames(f.Type.Params)
					addFieldNames(f.Type.Results)
				case *ast.FuncLit:
					addFieldNames(f.Type.Params)
					addFieldNames(f.Type.Results)
				}

				if len(callerLabels(caller.path)) > 0 {
					// TODO(adonovan): be more precise and reject
					// only forward gotos across the inlined block.
					logf("keeping block braces: caller uses control labels")
				} else if intersects(declares(newBlock.List), callerNames) {
					logf("keeping block braces: avoids name conflict")
				} else {
					elideBraces = true
				}
			}
		}
	}

	// File rewriting. This proceeds in multiple passes, in order to maximally
	// preserve comment positioning. (This could be greatly simplified once
	// comments are stored in the tree.)
	//
	// Don't call replaceNode(caller.File, res.old, res.new)
	// as it mutates the caller's syntax tree.
	// Instead, splice the file, replacing the extent of the "old"
	// node by a formatting of the "new" node, and re-parse.
	// We'll fix up the imports on this new tree, and format again.
	//
	// Inv: f is the result of parsing content, using fset.
	var (
		content = caller.Content
		fset    = caller.Fset
		f       *ast.File // parsed below
	)
	reparse := func() error {
		const mode = parser.ParseComments | parser.SkipObjectResolution | parser.AllErrors
		f, err = parser.ParseFile(fset, "callee.go", content, mode)
		if err != nil {
			// Something has gone very wrong.
			logf("failed to reparse <<%s>>: %v", string(content), err) // debugging
			return err
		}
		return nil
	}
	{
		start := offsetOf(fset, res.old.Pos())
		end := offsetOf(fset, res.old.End())
		var out bytes.Buffer
		out.Write(content[:start])
		// TODO(adonovan): might it make more sense to use
		// callee.Fset when formatting res.new?
		// The new tree is a mix of (cloned) caller nodes for
		// the argument expressions and callee nodes for the
		// function body. In essence the question is: which
		// is more likely to have comments?
		// Usually the callee body will be larger and more
		// statement-heavy than the arguments, but a
		// strategy may widen the scope of the replacement
		// (res.old) from CallExpr to, say, its enclosing
		// block, so the caller nodes dominate.
		// Precise comment handling would make this a
		// non-issue. Formatting wouldn't really need a
		// FileSet at all.
		if elideBraces {
			for i, stmt := range res.new.(*ast.BlockStmt).List {
				if i > 0 {
					out.WriteByte('\n')
				}
				if err := format.Node(&out, fset, stmt); err != nil {
					return nil, err
				}
			}
		} else {
			if err := format.Node(&out, fset, res.new); err != nil {
				return nil, err
			}
		}
		out.Write(content[end:])
		content = out.Bytes()
		if err := reparse(); err != nil {
			return nil, err
		}
	}

	// Add new imports that are still used.
	newImports := trimNewImports(res.newImports, res.new)
	// Insert new imports after last existing import,
	// to avoid migration of pre-import comments.
	// The imports will be organized below.
	if len(newImports) > 0 {
		// If we have imports to add, do so independent of the rest of the file.
		// Otherwise, the length of the new imports may consume floating comments,
		// causing them to be printed inside the imports block.
		var (
			importDecl    *ast.GenDecl
			comments      []*ast.CommentGroup // relevant comments.
			before, after []byte              // pre- and post-amble for the imports block.
		)
		if len(f.Imports) > 0 {
			// Append specs to existing import decl
			importDecl = f.Decls[0].(*ast.GenDecl)
			for _, comment := range f.Comments {
				// Filter comments. Don't use CommentMap.Filter here, because we don't
				// want to include comments that document the import decl itself, for
				// example:
				//
				//  // We don't want this comment to be duplicated.
				//  import (
				//    "something"
				//  )
				if importDecl.Pos() <= comment.Pos() && comment.Pos() < importDecl.End() {
					comments = append(comments, comment)
				}
			}
			before = content[:offsetOf(fset, importDecl.Pos())]
			importDecl.Doc = nil // present in before
			after = content[offsetOf(fset, importDecl.End()):]
		} else {
			// Insert new import decl.
			importDecl = &ast.GenDecl{Tok: token.IMPORT}
			f.Decls = prepend[ast.Decl](importDecl, f.Decls...)

			// Make room for the new declaration after the package declaration.
			pkgEnd := f.Name.End()
			file := fset.File(pkgEnd)
			if file == nil {
				logf("internal error: missing pkg file")
				return nil, fmt.Errorf("missing pkg file for %s", f.Name.Name)
			}
			// Preserve any comments after the package declaration, by splicing in
			// the new import block after the end of the package declaration line.
			line := file.Line(pkgEnd)
			if line < len(file.Lines()) { // line numbers are 1-based
				nextLinePos := file.LineStart(line + 1)
				nextLine := offsetOf(fset, nextLinePos)
				before = slices.Concat(content[:nextLine], []byte("\n"))
				after = slices.Concat([]byte("\n\n"), content[nextLine:])
			} else {
				before = slices.Concat(content, []byte("\n\n"))
			}
		}
		// Add new imports.
		for _, imp := range newImports {
			// Check that the new imports are accessible.
			path, _ := strconv.Unquote(imp.spec.Path.Value)
			if !analysisinternal.CanImport(caller.Types.Path(), path) {
				return nil, fmt.Errorf("can't inline function %v as its body refers to inaccessible package %q", callee, path)
			}
			importDecl.Specs = append(importDecl.Specs, imp.spec)
		}
		var out bytes.Buffer
		out.Write(before)
		commented := &printer.CommentedNode{
			Node:     importDecl,
			Comments: comments,
		}
		if err := format.Node(&out, fset, commented); err != nil {
			logf("failed to format new importDecl: %v", err) // debugging
			return nil, err
		}
		out.Write(after)
		content = out.Bytes()
		if err := reparse(); err != nil {
			return nil, err
		}
	}

	// Delete imports referenced only by caller.Call.Fun.
	for _, oldImport := range res.oldImports {
		specToDelete := oldImport.spec
		name := ""
		if specToDelete.Name != nil {
			name = specToDelete.Name.Name
		}
		path, _ := strconv.Unquote(specToDelete.Path.Value)
		astutil.DeleteNamedImport(caller.Fset, f, name, path)
	}

	var out bytes.Buffer
	if err := format.Node(&out, caller.Fset, f); err != nil {
		return nil, err
	}
	newSrc := out.Bytes()

	literalized := false
	if call, ok := res.new.(*ast.CallExpr); ok && is[*ast.FuncLit](call.Fun) {
		literalized = true
	}

	return &Result{
		Content:     newSrc,
		Literalized: literalized,
	}, nil
}

// An oldImport is an import that will be deleted from the caller file.
type oldImport struct {
	pkgName *types.PkgName
	spec    *ast.ImportSpec
}

// A newImport is an import that will be added to the caller file.
type newImport struct {
	pkgName string
	spec    *ast.ImportSpec
}

// importState tracks information about imports.
type importState struct {
	logf       func(string, ...any)
	caller     *Caller
	importMap  map[string][]string // from package paths in the caller's file to local names
	newImports []newImport         // for references to free names in callee; to be added to the file
	oldImports []oldImport         // referenced only by caller.Call.Fun; to be removed from the file
}

// newImportState returns an importState with initial information about the caller's imports.
func newImportState(logf func(string, ...any), caller *Caller, callee *gobCallee) *importState {
	// For simplicity we ignore existing dot imports, so that a qualified
	// identifier (QI) in the callee is always represented by a QI in the caller,
	// allowing us to treat a QI like a selection on a package name.
	is := &importState{
		logf:      logf,
		caller:    caller,
		importMap: make(map[string][]string),
	}

	for _, imp := range caller.File.Imports {
		if pkgName, ok := importedPkgName(caller.Info, imp); ok &&
			pkgName.Name() != "." &&
			pkgName.Name() != "_" {

			// If the import's sole use is in caller.Call.Fun of the form p.F(...),
			// where p.F is a qualified identifier, the p import may not be
			// necessary.
			//
			// Only the qualified identifier case matters, as other references to
			// imported package names in the Call.Fun expression (e.g.
			// x.after(3*time.Second).f() or time.Second.String()) will remain after
			// inlining, as arguments.
			//
			// If that is the case, proactively check if any of the callee FreeObjs
			// need this import. Doing so eagerly simplifies the resulting logic.
			needed := true
			sel, ok := ast.Unparen(caller.Call.Fun).(*ast.SelectorExpr)
			if ok && soleUse(caller.Info, pkgName) == sel.X {
				needed = false // no longer needed by caller
				// Check to see if any of the inlined free objects need this package.
				for _, obj := range callee.FreeObjs {
					if obj.PkgPath == pkgName.Imported().Path() && obj.Shadow[pkgName.Name()] == 0 {
						needed = true // needed by callee
						break
					}
				}
			}

			// Exclude imports not needed by the caller or callee after inlining; the second
			// return value holds these.
			if needed {
				path := pkgName.Imported().Path()
				is.importMap[path] = append(is.importMap[path], pkgName.Name())
			} else {
				is.oldImports = append(is.oldImports, oldImport{pkgName: pkgName, spec: imp})
			}
		}
	}
	return is
}

// importName finds an existing import name to use in a particular shadowing
// context. It is used to determine the set of new imports in
// localName, and is also used for writing out names in inlining
// strategies below.
func (i *importState) importName(pkgPath string, shadow shadowMap) string {
	for _, name := range i.importMap[pkgPath] {
		// Check that either the import preexisted, or that it was newly added
		// (no PkgName) but is not shadowed, either in the callee (shadows) or
		// caller (caller.lookup).
		if shadow[name] == 0 {
			found := i.caller.lookup(name)
			if is[*types.PkgName](found) || found == nil {
				return name
			}
		}
	}
	return ""
}

// localName returns the local name for a given imported package path,
// adding one if it doesn't exists.
func (i *importState) localName(pkgPath, pkgName string, shadow shadowMap) string {
	// Does an import already exist that works in this shadowing context?
	if name := i.importName(pkgPath, shadow); name != "" {
		return name
	}

	newlyAdded := func(name string) bool {
		return slices.ContainsFunc(i.newImports, func(n newImport) bool { return n.pkgName == name })
	}

	// shadowedInCaller reports whether a candidate package name
	// already refers to a declaration in the caller.
	shadowedInCaller := func(name string) bool {
		obj := i.caller.lookup(name)
		if obj == nil {
			return false
		}
		// If obj will be removed, the name is available.
		return !slices.ContainsFunc(i.oldImports, func(o oldImport) bool { return o.pkgName == obj })
	}

	// import added by callee
	//
	// Choose local PkgName based on last segment of
	// package path plus, if needed, a numeric suffix to
	// ensure uniqueness.
	//
	// "init" is not a legal PkgName.
	//
	// TODO(rfindley): is it worth preserving local package names for callee
	// imports? Are they likely to be better or worse than the name we choose
	// here?
	base := pkgName
	name := base
	for n := 0; shadow[name] != 0 || shadowedInCaller(name) || newlyAdded(name) || name == "init"; n++ {
		name = fmt.Sprintf("%s%d", base, n)
	}
	i.logf("adding import %s %q", name, pkgPath)
	spec := &ast.ImportSpec{
		Path: &ast.BasicLit{
			Kind:  token.STRING,
			Value: strconv.Quote(pkgPath),
		},
	}
	// Use explicit pkgname (out of necessity) when it differs from the declared name,
	// or (for good style) when it differs from base(pkgpath).
	if name != pkgName || name != pathpkg.Base(pkgPath) {
		spec.Name = makeIdent(name)
	}
	i.newImports = append(i.newImports, newImport{
		pkgName: name,
		spec:    spec,
	})
	i.importMap[pkgPath] = append(i.importMap[pkgPath], name)
	return name
}

// trimNewImports removes imports that are no longer needed.
//
// The list of new imports as constructed by calls to [importState.localName]
// includes all of the packages referenced by the callee.
// But in the process of inlining, we may have dropped some of those references.
// For example, if the callee looked like this:
//
//	func F(x int) (p.T) {... /* no mention of p */ ...}
//
// and we inlined by assignment:
//
//	v := ...
//
// then the reference to package p drops away.
//
// Remove the excess imports by seeing which remain in new, the expression
// to be inlined.
// We can find those by looking at the free names in new.
// The list of free names cannot include spurious package names.
// Free-name tracking is precise except for the case of an identifier
// key in a composite literal, which names either a field or a value.
// Neither fields nor values are package names.
// Since they are not relevant to removing unused imports, we instruct
// freeishNames to omit composite-literal keys that are identifiers.
func trimNewImports(newImports []newImport, new ast.Node) []newImport {
	free := map[string]bool{}
	const omitComplitIdents = false
	freeishNames(free, new, omitComplitIdents)
	var res []newImport
	for _, ni := range newImports {
		if free[ni.pkgName] {
			res = append(res, ni)
		}
	}
	return res
}

type inlineCallResult struct {
	newImports []newImport // to add
	oldImports []oldImport // to remove

	// If elideBraces is set, old is an ast.Stmt and new is an ast.BlockStmt to
	// be spliced in. This allows the inlining analysis to assert that inlining
	// the block is OK; if elideBraces is unset and old is an ast.Stmt and new is
	// an ast.BlockStmt, braces may still be elided if the post-processing
	// analysis determines that it is safe to do so.
	//
	// Ideally, it would not be necessary for the inlining analysis to "reach
	// through" to the post-processing pass in this way. Instead, inlining could
	// just set old to be an ast.BlockStmt and rewrite the entire BlockStmt, but
	// unfortunately in order to preserve comments, it is important that inlining
	// replace as little syntax as possible.
	elideBraces bool
	old, new    ast.Node // e.g. replace call expr by callee function body expression
}

// inlineCall returns a pair of an old node (the call, or something
// enclosing it) and a new node (its replacement, which may be a
// combination of caller, callee, and new nodes), along with the set
// of new imports needed.
//
// TODO(adonovan): rethink the 'result' interface. The assumption of a
// one-to-one replacement seems fragile. One can easily imagine the
// transformation replacing the call and adding new variable
// declarations, for example, or replacing a call statement by zero or
// many statements.)
// NOTE(rfindley): we've sort-of done this, with the 'elideBraces' flag that
// allows inlining a statement list. However, due to loss of comments, more
// sophisticated rewrites are challenging.
//
// TODO(adonovan): in earlier drafts, the transformation was expressed
// by splicing substrings of the two source files because syntax
// trees don't preserve comments faithfully (see #20744), but such
// transformations don't compose. The current implementation is
// tree-based but is very lossy wrt comments. It would make a good
// candidate for evaluating an alternative fully self-contained tree
// representation, such as any proposed solution to #20744, or even
// dst or some private fork of go/ast.)
// TODO(rfindley): see if we can reduce the amount of comment lossiness by
// using printer.CommentedNode, which has been useful elsewhere.
//
// TODO(rfindley): inlineCall is getting very long, and very stateful, making
// it very hard to read. The following refactoring may improve readability and
// maintainability:
//   - Rename 'state' to 'callsite', since that is what it encapsulates.
//   - Add results of pre-processing analysis into the callsite struct, such as
//     the effective importMap, new/old imports, arguments, etc. Essentially
//     anything that resulted from initial analysis of the call site, and which
//     may be useful to inlining strategies.
//   - Delegate this call site analysis to a constructor or initializer, such
//     as 'analyzeCallsite', so that it does not consume bandwidth in the
//     'inlineCall' logical flow.
//   - Once analyzeCallsite returns, the callsite is immutable, much in the
//     same way as the Callee and Caller are immutable.
//   - Decide on a standard interface for strategies (and substrategies), such
//     that they may be delegated to a separate method on callsite.
//
// In this way, the logical flow of inline call will clearly follow the
// following structure:
//  1. Analyze the call site.
//  2. Try strategies, in order, until one succeeds.
//  3. Process the results.
//
// If any expensive analysis may be avoided by earlier strategies, it can be
// encapsulated in its own type and passed to subsequent strategies.
func (st *state) inlineCall() (*inlineCallResult, error) {
	logf, caller, callee := st.opts.Logf, st.caller, &st.callee.impl

	checkInfoFields(caller.Info)

	// Inlining of dynamic calls is not currently supported,
	// even for local closure calls. (This would be a lot of work.)
	calleeSymbol := typeutil.StaticCallee(caller.Info, caller.Call)
	if calleeSymbol == nil {
		// e.g. interface method
		return nil, fmt.Errorf("cannot inline: not a static function call")
	}

	// Reject cross-package inlining if callee has
	// free references to unexported symbols.
	samePkg := caller.Types.Path() == callee.PkgPath
	if !samePkg && len(callee.Unexported) > 0 {
		return nil, fmt.Errorf("cannot inline call to %s because body refers to non-exported %s",
			callee.Name, callee.Unexported[0])
	}

	// -- analyze callee's free references in caller context --

	// Compute syntax path enclosing Call, innermost first (Path[0]=Call),
	// and outermost enclosing function, if any.
	caller.path, _ = astutil.PathEnclosingInterval(caller.File, caller.Call.Pos(), caller.Call.End())
	for _, n := range caller.path {
		if decl, ok := n.(*ast.FuncDecl); ok {
			caller.enclosingFunc = decl
			break
		}
	}

	// If call is within a function, analyze all its
	// local vars for the "single assignment" property.
	// (Taking the address &v counts as a potential assignment.)
	var assign1 func(v *types.Var) bool // reports whether v a single-assignment local var
	{
		updatedLocals := make(map[*types.Var]bool)
		if caller.enclosingFunc != nil {
			escape(caller.Info, caller.enclosingFunc, func(v *types.Var, _ bool) {
				updatedLocals[v] = true
			})
			logf("multiple-assignment vars: %v", updatedLocals)
		}
		assign1 = func(v *types.Var) bool { return !updatedLocals[v] }
	}

	// Extract information about the caller's imports.
	istate := newImportState(logf, caller, callee)

	// Compute the renaming of the callee's free identifiers.
	objRenames, err := st.renameFreeObjs(istate)
	if err != nil {
		return nil, err
	}

	res := &inlineCallResult{
		newImports: istate.newImports,
		oldImports: istate.oldImports,
	}

	// Parse callee function declaration.
	calleeFset, calleeDecl, err := parseCompact(callee.Content)
	if err != nil {
		return nil, err // "can't happen"
	}

	// replaceCalleeID replaces an identifier in the callee. See [replacer] for
	// more detailed semantics.
	replaceCalleeID := func(offset int, repl ast.Expr, unpackVariadic bool) {
		path, id := findIdent(calleeDecl, calleeDecl.Pos()+token.Pos(offset))
		logf("- replace id %q @ #%d to %q", id.Name, offset, debugFormatNode(calleeFset, repl))
		// Replace f([]T{a, b, c}...) with f(a, b, c).
		if lit, ok := repl.(*ast.CompositeLit); ok && unpackVariadic && len(path) > 0 {
			if call, ok := last(path).(*ast.CallExpr); ok &&
				call.Ellipsis.IsValid() &&
				id == last(call.Args) {

				call.Args = append(call.Args[:len(call.Args)-1], lit.Elts...)
				call.Ellipsis = token.NoPos
				return
			}
		}
		replaceNode(calleeDecl, id, repl)
	}

	// Generate replacements for each free identifier.
	// (The same tree may be spliced in multiple times, resulting in a DAG.)
	for _, ref := range callee.FreeRefs {
		if repl := objRenames[ref.Object]; repl != nil {
			replaceCalleeID(ref.Offset, repl, false)
		}
	}

	// Gather the effective call arguments, including the receiver.
	// Later, elements will be eliminated (=> nil) by parameter substitution.
	args, err := st.arguments(caller, calleeDecl, assign1)
	if err != nil {
		return nil, err // e.g. implicit field selection cannot be made explicit
	}

	// Gather effective parameter tuple, including the receiver if any.
	// Simplify variadic parameters to slices (in all cases but one).
	var params []*parameter // including receiver; nil => parameter substituted
	{
		sig := calleeSymbol.Type().(*types.Signature)
		if sig.Recv() != nil {
			params = append(params, &parameter{
				obj:       sig.Recv(),
				fieldType: calleeDecl.Recv.List[0].Type,
				info:      callee.Params[0],
			})
		}

		// Flatten the list of syntactic types.
		var types []ast.Expr
		for _, field := range calleeDecl.Type.Params.List {
			if field.Names == nil {
				types = append(types, field.Type)
			} else {
				for range field.Names {
					types = append(types, field.Type)
				}
			}
		}

		for i := 0; i < sig.Params().Len(); i++ {
			params = append(params, &parameter{
				obj:       sig.Params().At(i),
				fieldType: types[i],
				info:      callee.Params[len(params)],
			})
		}

		// Variadic function?
		//
		// There are three possible types of call:
		// - ordinary f(a1, ..., aN)
		// - ellipsis f(a1, ..., slice...)
		// - spread   f(recv?, g()) where g() is a tuple.
		// The first two are desugared to non-variadic calls
		// with an ordinary slice parameter;
		// the third is tricky and cannot be reduced, and (if
		// a receiver is present) cannot even be literalized.
		// Fortunately it is vanishingly rare.
		//
		// TODO(adonovan): extract this to a function.
		if sig.Variadic() {
			lastParam := last(params)
			if len(args) > 0 && last(args).spread {
				// spread call to variadic: tricky
				lastParam.variadic = true
			} else {
				// ordinary/ellipsis call to variadic

				// simplify decl: func(T...) -> func([]T)
				lastParamField := last(calleeDecl.Type.Params.List)
				lastParamField.Type = &ast.ArrayType{
					Elt: lastParamField.Type.(*ast.Ellipsis).Elt,
				}

				if caller.Call.Ellipsis.IsValid() {
					// ellipsis call: f(slice...) -> f(slice)
					// nop
				} else {
					// ordinary call: f(a1, ... aN) -> f([]T{a1, ..., aN})
					//
					// Substitution of []T{...} in the callee body may lead to
					// g([]T{a1, ..., aN}...), which we simplify to g(a1, ..., an)
					// later; see replaceCalleeID.
					n := len(params) - 1
					ordinary, extra := args[:n], args[n:]
					var elts []ast.Expr
					freevars := make(map[string]bool)
					pure, effects := true, false
					for _, arg := range extra {
						elts = append(elts, arg.expr)
						pure = pure && arg.pure
						effects = effects || arg.effects
						maps.Copy(freevars, arg.freevars)
					}
					args = append(ordinary, &argument{
						expr: &ast.CompositeLit{
							Type: lastParamField.Type,
							Elts: elts,
						},
						typ:        lastParam.obj.Type(),
						constant:   nil,
						pure:       pure,
						effects:    effects,
						duplicable: false,
						freevars:   freevars,
						variadic:   true,
					})
				}
			}
		}
	}

	typeArgs := st.typeArguments(caller.Call)
	if len(typeArgs) != len(callee.TypeParams) {
		return nil, fmt.Errorf("cannot inline: type parameter inference is not yet supported")
	}
	if err := substituteTypeParams(logf, callee.TypeParams, typeArgs, params, replaceCalleeID); err != nil {
		return nil, err
	}

	// Log effective arguments.
	for i, arg := range args {
		logf("arg #%d: %s pure=%t effects=%t duplicable=%t free=%v type=%v",
			i, debugFormatNode(caller.Fset, arg.expr),
			arg.pure, arg.effects, arg.duplicable, arg.freevars, arg.typ)
	}

	// Note: computation below should be expressed in terms of
	// the args and params slices, not the raw material.

	// Perform parameter substitution.
	// May eliminate some elements of params/args.
	substitute(logf, caller, params, args, callee.Effects, callee.Falcon, replaceCalleeID)

	// Update the callee's signature syntax.
	updateCalleeParams(calleeDecl, params)

	// Create a var (param = arg; ...) decl for use by some strategies.
	bindingDecl := createBindingDecl(logf, caller, args, calleeDecl, callee.Results)

	var remainingArgs []ast.Expr
	for _, arg := range args {
		if arg != nil {
			remainingArgs = append(remainingArgs, arg.expr)
		}
	}

	// -- let the inlining strategies begin --
	//
	// When we commit to a strategy, we log a message of the form:
	//
	//   "strategy: reduce expr-context call to { return expr }"
	//
	// This is a terse way of saying:
	//
	//    we plan to reduce a call
	//    that appears in expression context
	//    to a function whose body is of the form { return expr }

	// TODO(adonovan): split this huge function into a sequence of
	// function calls with an error sentinel that means "try the
	// next strategy", and make sure each strategy writes to the
	// log the reason it didn't match.

	// Special case: eliminate a call to a function whose body is empty.
	// (=> callee has no results and caller is a statement.)
	//
	//    func f(params) {}
	//    f(args)
	//    => _, _ = args
	//
	if len(calleeDecl.Body.List) == 0 {
		logf("strategy: reduce call to empty body")

		// Evaluate the arguments for effects and delete the call entirely.
		// Note(golang/go#71486): stmt can be nil if the call is in a go or defer
		// statement.
		// TODO: discard go or defer statements as well.
		if stmt := callStmt(caller.path, false); stmt != nil {
			res.old = stmt
			if nargs := len(remainingArgs); nargs > 0 {
				// Emit "_, _ = args" to discard results.

				// TODO(adonovan): if args is the []T{a1, ..., an}
				// literal synthesized during variadic simplification,
				// consider unwrapping it to its (pure) elements.
				// Perhaps there's no harm doing this for any slice literal.

				// Make correction for spread calls
				// f(g()) or recv.f(g()) where g() is a tuple.
				if last := last(args); last != nil && last.spread {
					nspread := last.typ.(*types.Tuple).Len()
					if len(args) > 1 { // [recv, g()]
						// A single AssignStmt cannot discard both, so use a 2-spec var decl.
						res.new = &ast.GenDecl{
							Tok: token.VAR,
							Specs: []ast.Spec{
								&ast.ValueSpec{
									Names:  []*ast.Ident{makeIdent("_")},
									Values: []ast.Expr{args[0].expr},
								},
								&ast.ValueSpec{
									Names:  blanks[*ast.Ident](nspread),
									Values: []ast.Expr{args[1].expr},
								},
							},
						}
						return res, nil
					}

					// Sole argument is spread call.
					nargs = nspread
				}

				res.new = &ast.AssignStmt{
					Lhs: blanks[ast.Expr](nargs),
					Tok: token.ASSIGN,
					Rhs: remainingArgs,
				}

			} else {
				// No remaining arguments: delete call statement entirely
				res.new = &ast.EmptyStmt{}
			}
			return res, nil
		}
	}

	// If all parameters have been substituted and no result
	// variable is referenced, we don't need a binding decl.
	// This may enable better reduction strategies.
	allResultsUnreferenced := forall(callee.Results, func(i int, r *paramInfo) bool { return len(r.Refs) == 0 })
	needBindingDecl := !allResultsUnreferenced ||
		exists(params, func(i int, p *parameter) bool { return p != nil })

	// The two strategies below overlap for a tail call of {return exprs}:
	// The expr-context reduction is nice because it keeps the
	// caller's return stmt and merely switches its operand,
	// without introducing a new block, but it doesn't work with
	// implicit return conversions.
	//
	// TODO(adonovan): unify these cases more cleanly, allowing return-
	// operand replacement and implicit conversions, by adding
	// conversions around each return operand (if not a spread return).

	// Special case: call to { return exprs }.
	//
	// Reduces to:
	//	    { var (bindings); _, _ = exprs }
	//     or   _, _ = exprs
	//     or   expr
	//
	// If:
	// - the body is just "return expr" with trivial implicit conversions,
	//   or the caller's return type matches the callee's,
	// - all parameters and result vars can be eliminated
	//   or replaced by a binding decl,
	// then the call expression can be replaced by the
	// callee's body expression, suitably substituted.
	if len(calleeDecl.Body.List) == 1 &&
		is[*ast.ReturnStmt](calleeDecl.Body.List[0]) &&
		len(calleeDecl.Body.List[0].(*ast.ReturnStmt).Results) > 0 { // not a bare return
		results := calleeDecl.Body.List[0].(*ast.ReturnStmt).Results

		parent, grandparent := callContext(caller.path)

		// statement context
		if stmt, ok := parent.(*ast.ExprStmt); ok &&
			(!needBindingDecl || bindingDecl != nil) {
			logf("strategy: reduce stmt-context call to { return exprs }")
			clearPositions(calleeDecl.Body)

			if callee.ValidForCallStmt {
				logf("callee body is valid as statement")
				// Inv: len(results) == 1
				if !needBindingDecl {
					// Reduces to: expr
					res.old = caller.Call
					res.new = results[0]
				} else {
					// Reduces to: { var (bindings); expr }
					res.old = stmt
					res.new = &ast.BlockStmt{
						List: []ast.Stmt{
							bindingDecl.stmt,
							&ast.ExprStmt{X: results[0]},
						},
					}
				}
			} else {
				logf("callee body is not valid as statement")
				// The call is a standalone statement, but the
				// callee body is not suitable as a standalone statement
				// (f() or <-ch), explicitly discard the results:
				// Reduces to: _, _ = exprs
				discard := &ast.AssignStmt{
					Lhs: blanks[ast.Expr](callee.NumResults),
					Tok: token.ASSIGN,
					Rhs: results,
				}
				res.old = stmt
				if !needBindingDecl {
					// Reduces to: _, _ = exprs
					res.new = discard
				} else {
					// Reduces to: { var (bindings); _, _ = exprs }
					res.new = &ast.BlockStmt{
						List: []ast.Stmt{
							bindingDecl.stmt,
							discard,
						},
					}
				}
			}
			return res, nil
		}

		// Assignment context.
		//
		// If there is no binding decl, or if the binding decl declares no names,
		// an assignment a, b := f() can be reduced to a, b := x, y.
		if stmt, ok := parent.(*ast.AssignStmt); ok &&
			is[*ast.BlockStmt](grandparent) &&
			(!needBindingDecl || (bindingDecl != nil && len(bindingDecl.names) == 0)) {

			// Reduces to: { var (bindings); lhs... := rhs... }
			if newStmts, ok := st.assignStmts(stmt, results, istate.importName); ok {
				logf("strategy: reduce assign-context call to { return exprs }")

				clearPositions(calleeDecl.Body)

				block := &ast.BlockStmt{
					List: newStmts,
				}
				if needBindingDecl {
					block.List = prepend(bindingDecl.stmt, block.List...)
				}

				// assignStmts does not introduce new bindings, and replacing an
				// assignment only works if the replacement occurs in the same scope.
				// Therefore, we must ensure that braces are elided.
				res.elideBraces = true
				res.old = stmt
				res.new = block
				return res, nil
			}
		}

		// expression context
		if !needBindingDecl {
			clearPositions(calleeDecl.Body)

			anyNonTrivialReturns := hasNonTrivialReturn(callee.Returns)

			if callee.NumResults == 1 {
				logf("strategy: reduce expr-context call to { return expr }")
				// (includes some simple tail-calls)

				// Make implicit return conversion explicit.
				if anyNonTrivialReturns {
					results[0] = convert(calleeDecl.Type.Results.List[0].Type, results[0])
				}

				res.old = caller.Call
				res.new = results[0]
				return res, nil

			} else if !anyNonTrivialReturns {
				logf("strategy: reduce spread-context call to { return expr }")
				// There is no general way to reify conversions in a spread
				// return, hence the requirement above.
				//
				// TODO(adonovan): allow this reduction when no
				// conversion is required by the context.

				// The call returns multiple results but is
				// not a standalone call statement. It must
				// be the RHS of a spread assignment:
				//   var x, y  = f()
				//       x, y := f()
				//       x, y  = f()
				// or the sole argument to a spread call:
				//        printf(f())
				// or spread return statement:
				//        return f()
				res.old = parent
				switch context := parent.(type) {
				case *ast.AssignStmt:
					// Inv: the call must be in Rhs[0], not Lhs.
					assign := shallowCopy(context)
					assign.Rhs = results
					res.new = assign
				case *ast.ValueSpec:
					// Inv: the call must be in Values[0], not Names.
					spec := shallowCopy(context)
					spec.Values = results
					res.new = spec
				case *ast.CallExpr:
					// Inv: the call must be in Args[0], not Fun.
					call := shallowCopy(context)
					call.Args = results
					res.new = call
				case *ast.ReturnStmt:
					// Inv: the call must be Results[0].
					ret := shallowCopy(context)
					ret.Results = results
					res.new = ret
				default:
					return nil, fmt.Errorf("internal error: unexpected context %T for spread call", context)
				}
				return res, nil
			}
		}
	}

	// Special case: tail-call.
	//
	// Inlining:
	//         return f(args)
	// where:
	//         func f(params) (results) { body }
	// reduces to:
	//         { var (bindings); body }
	//         { body }
	// so long as:
	// - all parameters can be eliminated or replaced by a binding decl,
	// - call is a tail-call;
	// - all returns in body have trivial result conversions,
	//   or the caller's return type matches the callee's,
	// - there is no label conflict;
	// - no result variable is referenced by name,
	//   or implicitly by a bare return.
	//
	// The body may use defer, arbitrary control flow, and
	// multiple returns.
	//
	// TODO(adonovan): add a strategy for a 'void tail
	// call', i.e. a call statement prior to an (explicit
	// or implicit) return.
	parent, _ := callContext(caller.path)
	if ret, ok := parent.(*ast.ReturnStmt); ok &&
		len(ret.Results) == 1 &&
		tailCallSafeReturn(caller, calleeSymbol, callee) &&
		!callee.HasBareReturn &&
		(!needBindingDecl || bindingDecl != nil) &&
		!hasLabelConflict(caller.path, callee.Labels) &&
		allResultsUnreferenced {
		logf("strategy: reduce tail-call")
		body := calleeDecl.Body
		clearPositions(body)
		if needBindingDecl {
			body.List = prepend(bindingDecl.stmt, body.List...)
		}
		res.old = ret
		res.new = body
		return res, nil
	}

	// Special case: call to void function
	//
	// Inlining:
	//         f(args)
	// where:
	//	   func f(params) { stmts }
	// reduces to:
	//         { var (bindings); stmts }
	//         { stmts }
	// so long as:
	// - callee is a void function (no returns)
	// - callee does not use defer
	// - there is no label conflict between caller and callee
	// - all parameters and result vars can be eliminated
	//   or replaced by a binding decl,
	// - caller ExprStmt is in unrestricted statement context.
	if stmt := callStmt(caller.path, true); stmt != nil &&
		(!needBindingDecl || bindingDecl != nil) &&
		!callee.HasDefer &&
		!hasLabelConflict(caller.path, callee.Labels) &&
		len(callee.Returns) == 0 {
		logf("strategy: reduce stmt-context call to { stmts }")
		body := calleeDecl.Body
		var repl ast.Stmt = body
		clearPositions(repl)
		if needBindingDecl {
			body.List = prepend(bindingDecl.stmt, body.List...)
		}
		res.old = stmt
		res.new = repl
		return res, nil
	}

	// TODO(adonovan): parameterless call to { stmts; return expr }
	// from one of these contexts:
	//    x, y     = f()
	//    x, y    := f()
	//    var x, y = f()
	// =>
	//    var (x T1, y T2); { stmts; x, y = expr }
	//
	// Because the params are no longer declared simultaneously
	// we need to check that (for example) x ∉ freevars(T2),
	// in addition to the usual checks for arg/result conversions,
	// complex control, etc.
	// Also test cases where expr is an n-ary call (spread returns).

	// Literalization isn't quite infallible.
	// Consider a spread call to a method in which
	// no parameters are eliminated, e.g.
	// 	new(T).f(g())
	// where
	//  	func (recv *T) f(x, y int) { body }
	//  	func g() (int, int)
	// This would be literalized to:
	// 	func (recv *T, x, y int) { body }(new(T), g()),
	// which is not a valid argument list because g() must appear alone.
	// Reject this case for now.
	if len(args) == 2 && args[0] != nil && args[1] != nil && is[*types.Tuple](args[1].typ) {
		return nil, fmt.Errorf("can't yet inline spread call to method")
	}

	// Infallible general case: literalization.
	//
	//    func(params) { body }(args)
	//
	logf("strategy: literalization")
	funcLit := &ast.FuncLit{
		Type: calleeDecl.Type,
		Body: calleeDecl.Body,
	}
	// clear positions before prepending the binding decl below, since the
	// binding decl contains syntax from the caller and we must not mutate the
	// caller. (This was a prior bug.)
	clearPositions(funcLit)

	// Literalization can still make use of a binding
	// decl as it gives a more natural reading order:
	//
	//    func() { var params = args; body }()
	//
	// TODO(adonovan): relax the allResultsUnreferenced requirement
	// by adding a parameter-only (no named results) binding decl.
	if bindingDecl != nil && allResultsUnreferenced {
		funcLit.Type.Params.List = nil
		remainingArgs = nil
		funcLit.Body.List = prepend(bindingDecl.stmt, funcLit.Body.List...)
	}

	// Emit a new call to a function literal in place of
	// the callee name, with appropriate replacements.
	newCall := &ast.CallExpr{
		Fun:      funcLit,
		Ellipsis: token.NoPos, // f(slice...) is always simplified
		Args:     remainingArgs,
	}
	res.old = caller.Call
	res.new = newCall
	return res, nil
}

// renameFreeObjs computes the renaming of the callee's free identifiers.
// It returns a slice of names (identifiers or selector expressions) corresponding
// to the callee's free objects (gobCallee.FreeObjs).
func (st *state) renameFreeObjs(istate *importState) ([]ast.Expr, error) {
	caller, callee := st.caller, &st.callee.impl
	objRenames := make([]ast.Expr, len(callee.FreeObjs)) // nil => no change
	for i, obj := range callee.FreeObjs {
		// obj is a free object of the callee.
		//
		// Possible cases are:
		// - builtin function, type, or value (e.g. nil, zero)
		//   => check not shadowed in caller.
		// - package-level var/func/const/types
		//   => same package: check not shadowed in caller.
		//   => otherwise: import other package, form a qualified identifier.
		//      (Unexported cross-package references were rejected already.)
		// - type parameter
		//   => not yet supported
		// - pkgname
		//   => import other package and use its local name.
		//
		// There can be no free references to labels, fields, or methods.

		// Note that we must consider potential shadowing both
		// at the caller side (caller.lookup) and, when
		// choosing new PkgNames, within the callee (obj.shadow).

		var newName ast.Expr
		if obj.Kind == "pkgname" {
			// Use locally appropriate import, creating as needed.
			n := istate.localName(obj.PkgPath, obj.PkgName, obj.Shadow)
			newName = makeIdent(n) // imported package
		} else if !obj.ValidPos {
			// Built-in function, type, or value (e.g. nil, zero):
			// check not shadowed at caller.
			found := caller.lookup(obj.Name) // always finds something
			if found.Pos().IsValid() {
				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)",
					obj.Name, objectKind(found),
					caller.Fset.PositionFor(found.Pos(), false).Line)
			}

		} else {
			// Must be reference to package-level var/func/const/type,
			// since type parameters are not yet supported.
			qualify := false
			if obj.PkgPath == callee.PkgPath {
				// reference within callee package
				if caller.Types.Path() == callee.PkgPath {
					// Caller and callee are in same package.
					// Check caller has not shadowed the decl.
					//
					// This may fail if the callee is "fake", such as for signature
					// refactoring where the callee is modified to be a trivial wrapper
					// around the refactored signature.
					found := caller.lookup(obj.Name)
					if found != nil && !isPkgLevel(found) {
						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)",
							obj.Kind, obj.Name,
							objectKind(found),
							caller.Fset.PositionFor(found.Pos(), false).Line)
					}
				} else {
					// Cross-package reference.
					qualify = true
				}
			} else {
				// Reference to a package-level declaration
				// in another package, without a qualified identifier:
				// it must be a dot import.
				qualify = true
			}

			// Form a qualified identifier, pkg.Name.
			if qualify {
				pkgName := istate.localName(obj.PkgPath, obj.PkgName, obj.Shadow)
				newName = &ast.SelectorExpr{
					X:   makeIdent(pkgName),
					Sel: makeIdent(obj.Name),
				}
			}
		}
		objRenames[i] = newName
	}
	return objRenames, nil
}

type argument struct {
	expr          ast.Expr
	typ           types.Type      // may be tuple for sole non-receiver arg in spread call
	constant      constant.Value  // value of argument if constant
	spread        bool            // final arg is call() assigned to multiple params
	pure          bool            // expr is pure (doesn't read variables)
	effects       bool            // expr has effects (updates variables)
	duplicable    bool            // expr may be duplicated
	freevars      map[string]bool // free names of expr
	variadic      bool            // is explicit []T{...} for eliminated variadic
	desugaredRecv bool            // is *recv or &recv, where operator was elided
}

// typeArguments returns the type arguments of the call.
// It only collects the arguments that are explicitly provided; it does
// not attempt type inference.
func (st *state) typeArguments(call *ast.CallExpr) []*argument {
	var exprs []ast.Expr
	switch d := ast.Unparen(call.Fun).(type) {
	case *ast.IndexExpr:
		exprs = []ast.Expr{d.Index}
	case *ast.IndexListExpr:
		exprs = d.Indices
	default:
		// No type  arguments
		return nil
	}
	var args []*argument
	for _, e := range exprs {
		arg := &argument{expr: e, freevars: freeVars(st.caller.Info, e)}
		// Wrap the instantiating type in parens when it's not an
		// ident or qualified ident to prevent "if x == struct{}"
		// parsing ambiguity, or "T(x)" where T = "*int" or "func()"
		// from misparsing.
		if _, ok := arg.expr.(*ast.Ident); !ok {
			arg.expr = &ast.ParenExpr{X: arg.expr}
		}
		args = append(args, arg)
	}
	return args
}

// arguments returns the effective arguments of the call.
//
// If the receiver argument and parameter have
// different pointerness, make the "&" or "*" explicit.
//
// Also, if x.f() is shorthand for promoted method x.y.f(),
// make the .y explicit in T.f(x.y, ...).
//
// Beware that:
//
//   - a method can only be called through a selection, but only
//     the first of these two forms needs special treatment:
//
//     expr.f(args)     -> ([&*]expr, args)	MethodVal
//     T.f(recv, args)  -> (    expr, args)	MethodExpr
//
//   - the presence of a value in receiver-position in the call
//     is a property of the caller, not the callee. A method
//     (calleeDecl.Recv != nil) may be called like an ordinary
//     function.
//
//   - the types.Signatures seen by the caller (from
//     StaticCallee) and by the callee (from decl type)
//     differ in this case.
//
// In a spread call f(g()), the sole ordinary argument g(),
// always last in args, has a tuple type.
//
// We compute type-based predicates like pure, duplicable,
// freevars, etc, now, before we start modifying syntax.
func (st *state) arguments(caller *Caller, calleeDecl *ast.FuncDecl, assign1 func(*types.Var) bool) ([]*argument, error) {
	var args []*argument

	callArgs := caller.Call.Args
	if calleeDecl.Recv != nil {
		if len(st.callee.impl.TypeParams) > 0 {
			return nil, fmt.Errorf("cannot inline: generic methods not yet supported")
		}
		sel := ast.Unparen(caller.Call.Fun).(*ast.SelectorExpr)
		seln := caller.Info.Selections[sel]
		var recvArg ast.Expr
		switch seln.Kind() {
		case types.MethodVal: // recv.f(callArgs)
			recvArg = sel.X
		case types.MethodExpr: // T.f(recv, callArgs)
			recvArg = callArgs[0]
			callArgs = callArgs[1:]
		}
		if recvArg != nil {
			// Compute all the type-based predicates now,
			// before we start meddling with the syntax;
			// the meddling will update them.
			arg := &argument{
				expr:       recvArg,
				typ:        caller.Info.TypeOf(recvArg),
				constant:   caller.Info.Types[recvArg].Value,
				pure:       pure(caller.Info, assign1, recvArg),
				effects:    st.effects(caller.Info, recvArg),
				duplicable: duplicable(caller.Info, recvArg),
				freevars:   freeVars(caller.Info, recvArg),
			}
			recvArg = nil // prevent accidental use

			// Move receiver argument recv.f(args) to argument list f(&recv, args).
			args = append(args, arg)

			// Make field selections explicit (recv.f -> recv.y.f),
			// updating arg.{expr,typ}.
			indices := seln.Index()
			for _, index := range indices[:len(indices)-1] {
				fld := typeparams.CoreType(typeparams.Deref(arg.typ)).(*types.Struct).Field(index)
				if fld.Pkg() != caller.Types && !fld.Exported() {
					return nil, fmt.Errorf("in %s, implicit reference to unexported field .%s cannot be made explicit",
						debugFormatNode(caller.Fset, caller.Call.Fun),
						fld.Name())
				}
				if isPointer(arg.typ) {
					arg.pure = false // implicit *ptr operation => impure
				}
				arg.expr = &ast.SelectorExpr{
					X:   arg.expr,
					Sel: makeIdent(fld.Name()),
				}
				arg.typ = fld.Type()
				arg.duplicable = false
			}

			// Make * or & explicit.
			argIsPtr := isPointer(arg.typ)
			paramIsPtr := isPointer(seln.Obj().Type().Underlying().(*types.Signature).Recv().Type())
			if !argIsPtr && paramIsPtr {
				// &recv
				arg.expr = &ast.UnaryExpr{Op: token.AND, X: arg.expr}
				arg.typ = types.NewPointer(arg.typ)
				arg.desugaredRecv = true
			} else if argIsPtr && !paramIsPtr {
				// *recv
				arg.expr = &ast.StarExpr{X: arg.expr}
				arg.typ = typeparams.Deref(arg.typ)
				arg.duplicable = false
				arg.pure = false
				arg.desugaredRecv = true
			}
		}
	}
	for _, expr := range callArgs {
		tv := caller.Info.Types[expr]
		args = append(args, &argument{
			expr:       expr,
			typ:        tv.Type,
			constant:   tv.Value,
			spread:     is[*types.Tuple](tv.Type), // => last
			pure:       pure(caller.Info, assign1, expr),
			effects:    st.effects(caller.Info, expr),
			duplicable: duplicable(caller.Info, expr),
			freevars:   freeVars(caller.Info, expr),
		})
	}

	// Re-typecheck each constant argument expression in a neutral context.
	//
	// In a call such as func(int16){}(1), the type checker infers
	// the type "int16", not "untyped int", for the argument 1,
	// because it has incorporated information from the left-hand
	// side of the assignment implicit in parameter passing, but
	// of course in a different context, the expression 1 may have
	// a different type.
	//
	// So, we must use CheckExpr to recompute the type of the
	// argument in a neutral context to find its inherent type.
	// (This is arguably a bug in go/types, but I'm pretty certain
	// I requested it be this way long ago... -adonovan)
	//
	// This is only needed for constants. Other implicit
	// assignment conversions, such as unnamed-to-named struct or
	// chan to <-chan, do not result in the type-checker imposing
	// the LHS type on the RHS value.
	for _, arg := range args {
		if arg.constant == nil {
			continue
		}
		info := &types.Info{Types: make(map[ast.Expr]types.TypeAndValue)}
		if err := types.CheckExpr(caller.Fset, caller.Types, caller.Call.Pos(), arg.expr, info); err != nil {
			return nil, err
		}
		arg.typ = info.TypeOf(arg.expr)
	}

	return args, nil
}

type parameter struct {
	obj       *types.Var // parameter var from caller's signature
	fieldType ast.Expr   // syntax of type, from calleeDecl.Type.{Recv,Params}
	info      *paramInfo // information from AnalyzeCallee
	variadic  bool       // (final) parameter is unsimplified ...T
}

// A replacer replaces an identifier at the given offset in the callee.
// The replacement tree must not belong to the caller; use cloneNode as needed.
// If unpackVariadic is set, the replacement is a composite resulting from
// variadic elimination, and may be unpacked into variadic calls.
type replacer = func(offset int, repl ast.Expr, unpackVariadic bool)

// substituteTypeParams replaces type parameters in the callee with the corresponding type arguments
// from the call.
func substituteTypeParams(logf logger, typeParams []*paramInfo, typeArgs []*argument, params []*parameter, replace replacer) error {
	assert(len(typeParams) == len(typeArgs), "mismatched number of type params/args")
	for i, paramInfo := range typeParams {
		arg := typeArgs[i]
		// Perform a simplified, conservative shadow analysis: fail if there is any shadowing.
		for free := range arg.freevars {
			if paramInfo.Shadow[free] != 0 {
				return fmt.Errorf("cannot inline: type argument #%d (type parameter %s) is shadowed", i, paramInfo.Name)
			}
		}
		logf("replacing type param %s with %s", paramInfo.Name, debugFormatNode(token.NewFileSet(), arg.expr))
		for _, ref := range paramInfo.Refs {
			replace(ref.Offset, internalastutil.CloneNode(arg.expr), false)
		}
		// Also replace parameter field types.
		// TODO(jba): find a way to do this that is not so slow and clumsy.
		// Ideally, we'd walk each p.fieldType once, replacing all type params together.
		for _, p := range params {
			if id, ok := p.fieldType.(*ast.Ident); ok && id.Name == paramInfo.Name {
				p.fieldType = arg.expr
			} else {
				for _, id := range identsNamed(p.fieldType, paramInfo.Name) {
					replaceNode(p.fieldType, id, arg.expr)
				}
			}
		}
	}
	return nil
}

func identsNamed(n ast.Node, name string) []*ast.Ident {
	var ids []*ast.Ident
	ast.Inspect(n, func(n ast.Node) bool {
		if id, ok := n.(*ast.Ident); ok && id.Name == name {
			ids = append(ids, id)
		}
		return true
	})
	return ids
}

// substitute implements parameter elimination by substitution.
//
// It considers each parameter and its corresponding argument in turn
// and evaluate these conditions:
//
//   - the parameter is neither address-taken nor assigned;
//   - the argument is pure;
//   - if the parameter refcount is zero, the argument must
//     not contain the last use of a local var;
//   - if the parameter refcount is > 1, the argument must be duplicable;
//   - the argument (or types.Default(argument) if it's untyped) has
//     the same type as the parameter.
//
// If all conditions are met then the parameter can be substituted and
// each reference to it replaced by the argument. In that case, the
// replaceCalleeID function is called for each reference to the
// parameter, and is provided with its relative offset and replacement
// expression (argument), and the corresponding elements of params and
// args are replaced by nil.
func substitute(logf logger, caller *Caller, params []*parameter, args []*argument, effects []int, falcon falconResult, replace replacer) {
	// Inv:
	//  in        calls to     variadic, len(args) >= len(params)-1
	//  in spread calls to non-variadic, len(args) <  len(params)
	//  in spread calls to     variadic, len(args) <= len(params)
	// (In spread calls len(args) = 1, or 2 if call has receiver.)
	// Non-spread variadics have been simplified away already,
	// so the args[i] lookup is safe if we stop after the spread arg.
	assert(len(args) <= len(params), "too many arguments")

	// Collect candidates for substitution.
	//
	// An argument is a candidate if it is not otherwise rejected, and any free
	// variables that are shadowed only by other parameters.
	//
	// Therefore, substitution candidates are represented by a graph, where edges
	// lead from each argument to the other arguments that, if substituted, would
	// allow the argument to be substituted. We collect these edges in the
	// [substGraph]. Any node that is known not to be elided from the graph.
	// Arguments in this graph with no edges are substitutable independent of
	// other nodes, though they may be removed due to falcon or effects analysis.
	sg := make(substGraph)
next:
	for i, param := range params {
		arg := args[i]

		// Check argument against parameter.
		//
		// Beware: don't use types.Info on arg since
		// the syntax may be synthetic (not created by parser)
		// and thus lacking positions and types;
		// do it earlier (see pure/duplicable/freevars).

		if arg.spread {
			// spread => last argument, but not always last parameter
			logf("keeping param %q and following ones: argument %s is spread",
				param.info.Name, debugFormatNode(caller.Fset, arg.expr))
			return // give up
		}
		assert(!param.variadic, "unsimplified variadic parameter")
		if param.info.Escapes {
			logf("keeping param %q: escapes from callee", param.info.Name)
			continue
		}
		if param.info.Assigned {
			logf("keeping param %q: assigned by callee", param.info.Name)
			continue // callee needs the parameter variable
		}
		if len(param.info.Refs) > 1 && !arg.duplicable {
			logf("keeping param %q: argument is not duplicable", param.info.Name)
			continue // incorrect or poor style to duplicate an expression
		}
		if len(param.info.Refs) == 0 {
			if arg.effects {
				logf("keeping param %q: though unreferenced, it has effects", param.info.Name)
				continue
			}

			// If the caller is within a function body,
			// eliminating an unreferenced parameter might
			// remove the last reference to a caller local var.
			if caller.enclosingFunc != nil {
				for free := range arg.freevars {
					// TODO(rfindley): we can get this 100% right by looking for
					// references among other arguments which have non-zero references
					// within the callee.
					if v, ok := caller.lookup(free).(*types.Var); ok && within(v.Pos(), caller.enclosingFunc.Body) && !isUsedOutsideCall(caller, v) {

						// Check to see if the substituted var is used within other args
						// whose corresponding params ARE used in the callee
						usedElsewhere := func() bool {
							for i, param := range params {
								if i < len(args) && len(param.info.Refs) > 0 { // excludes original param
									for name := range args[i].freevars {
										if caller.lookup(name) == v {
											return true
										}
									}
								}
							}
							return false
						}
						if !usedElsewhere() {
							logf("keeping param %q: arg contains perhaps the last reference to caller local %v @ %v",
								param.info.Name, v, caller.Fset.PositionFor(v.Pos(), false))
							continue next
						}
					}
				}
			}
		}

		// Arg is a potential substition candidate: analyze its shadowing.
		//
		// Consider inlining a call f(z, 1) to
		//
		// 	func f(x, y int) int { z := y; return x + y + z }
		//
		// we can't replace x in the body by z (or any
		// expression that has z as a free identifier) because there's an
		// intervening declaration of z that would shadow the caller's one.
		//
		// However, we *could* replace x in the body by y, as long as the y
		// parameter is also removed by substitution.

		sg[arg] = nil // Absent shadowing, the arg is substitutable.
		for free := range arg.freevars {
			switch s := param.info.Shadow[free]; {
			case s < 0:
				// Shadowed by a non-parameter symbol, so arg is not substitutable.
				delete(sg, arg)
			case s > 0:
				// Shadowed by a parameter; arg may be substitutable, if only shadowed
				// by other substitutable parameters.
				if s > len(args) {
					// Defensive: this should not happen in the current factoring, since
					// spread arguments are already handled.
					delete(sg, arg)
				}
				if edges, ok := sg[arg]; ok {
					sg[arg] = append(edges, args[s-1])
				}
			}
		}
	}

	// Process the initial state of the substitution graph.
	sg.prune()

	// Now we check various conditions on the substituted argument set as a
	// whole. These conditions reject substitution candidates, but since their
	// analysis depends on the full set of candidates, we do not process side
	// effects of their candidate rejection until after the analysis completes,
	// in a call to prune. After pruning, we must re-run the analysis to check
	// for additional rejections.
	//
	// Here's an example of that in practice:
	//
	// 	var a [3]int
	//
	// 	func falcon(x, y, z int) {
	// 		_ = x + a[y+z]
	// 	}
	//
	// 	func _() {
	// 		var y int
	// 		const x, z = 1, 2
	// 		falcon(y, x, z)
	// 	}
	//
	// In this example, arguments 0 and 1 are shadowed by each other's
	// corresponding parameter, and so each can be substituted only if they are
	// both substituted. But the fallible constant analysis finds a violated
	// constraint: x + z = 3, and so the constant array index would cause a
	// compile-time error if argument 1 (x) were substituted. Therefore,
	// following the falcon analysis, we must also prune argument 0.
	//
	// As far as I (rfindley) can tell, the falcon analysis should always succeed
	// after the first pass, as it's not possible for additional bindings to
	// cause new constraint failures. Nevertheless, we re-run it to be sure.
	//
	// However, the same cannot be said of the effects analysis, as demonstrated
	// by this example:
	//
	// 	func effects(w, x, y, z int) {
	// 		_ = x + w + y + z
	// 	}

	// 	func _() {
	// 		v := 0
	// 		w := func() int { v++; return 0 }
	// 		x := func() int { v++; return 0 }
	// 		y := func() int { v++; return 0 }
	// 		effects(x(), w(), y(), x()) //@ inline(re"effects", effects)
	// 	}
	//
	// In this example, arguments 0, 1, and 3 are related by the substitution
	// graph. The first effects analysis implies that arguments 0 and 1 must be
	// bound, and therefore argument 3 must be bound. But then a subsequent
	// effects analysis forces argument 2 to also be bound.

	// Reject constant arguments as substitution candidates if they cause
	// violation of falcon constraints.
	//
	// Keep redoing the analysis until we no longer reject additional arguments,
	// as the set of substituted parameters affects the falcon package.
	for checkFalconConstraints(logf, params, args, falcon, sg) {
		sg.prune()
	}

	// As a final step, introduce bindings to resolve any
	// evaluation order hazards. This must be done last, as
	// additional subsequent bindings could introduce new hazards.
	//
	// As with the falcon analysis, keep redoing the analysis until the no more
	// arguments are rejected.
	for resolveEffects(logf, args, effects, sg) {
		sg.prune()
	}

	// The remaining candidates are safe to substitute.
	for i, param := range params {
		if arg := args[i]; sg.has(arg) {

			// It is safe to substitute param and replace it with arg.
			// The formatter introduces parens as needed for precedence.
			//
			// Because arg.expr belongs to the caller,
			// we clone it before splicing it into the callee tree.
			logf("replacing parameter %q by argument %q",
				param.info.Name, debugFormatNode(caller.Fset, arg.expr))
			for _, ref := range param.info.Refs {
				// Apply any transformations necessary for this reference.
				argExpr := arg.expr

				// If the reference itself is being selected, and we applied desugaring
				// (an explicit &x or *x), we can undo that desugaring here as it is
				// not necessary for a selector. We don't need to check addressability
				// here because if we desugared, the receiver must have been
				// addressable.
				if ref.IsSelectionOperand && arg.desugaredRecv {
					switch e := argExpr.(type) {
					case *ast.UnaryExpr:
						argExpr = e.X
					case *ast.StarExpr:
						argExpr = e.X
					}
				}

				// If the reference requires exact type agreement between parameter and
				// argument, wrap the argument in an explicit conversion if
				// substitution might materially change its type. (We already did the
				// necessary shadowing check on the parameter type syntax.)
				//
				// The types must agree in any of these cases:
				// - the argument affects type inference;
				// - the reference's concrete type is assigned to an interface type;
				// - the reference is not an assignment, nor a trivial conversion of an untyped constant.
				//
				// In all other cases, no explicit conversion is necessary as either
				// the type does not matter, or must have already agreed for well-typed
				// code.
				//
				// This is only needed for substituted arguments. All other arguments
				// are given explicit types in either a binding decl or when using the
				// literalization strategy.
				//
				// If the types are identical, we can eliminate
				// redundant type conversions such as this:
				//
				// Callee:
				//    func f(i int32) { fmt.Println(i) }
				// Caller:
				//    func g() { f(int32(1)) }
				// Inlined as:
				//    func g() { fmt.Println(int32(int32(1)))
				//
				// Recall that non-trivial does not imply non-identical for constant
				// conversions; however, at this point state.arguments has already
				// re-typechecked the constant and set arg.type to its (possibly
				// "untyped") inherent type, so the conversion from untyped 1 to int32
				// is non-trivial even though both arg and param have identical types
				// (int32).
				needType := ref.AffectsInference ||
					(ref.Assignable && ref.IfaceAssignment && !param.info.IsInterface) ||
					(!ref.Assignable && !trivialConversion(arg.constant, arg.typ, param.obj.Type()))

				if needType &&
					!types.Identical(types.Default(arg.typ), param.obj.Type()) {

					// If arg.expr is already an interface call, strip it.
					if call, ok := argExpr.(*ast.CallExpr); ok && len(call.Args) == 1 {
						if typ, ok := isConversion(caller.Info, call); ok && isNonTypeParamInterface(typ) {
							argExpr = call.Args[0]
						}
					}

					argExpr = convert(param.fieldType, argExpr)
					logf("param %q (offset %d): adding explicit %s -> %s conversion around argument",
						param.info.Name, ref.Offset, arg.typ, param.obj.Type())
				}
				replace(ref.Offset, internalastutil.CloneNode(argExpr).(ast.Expr), arg.variadic)
			}
			params[i] = nil // substituted
			args[i] = nil   // substituted
		}
	}
}

// isConversion reports whether the given call is a type conversion, returning
// (operand, true) if so.
//
// If the call is not a conversion, it returns (nil, false).
func isConversion(info *types.Info, call *ast.CallExpr) (types.Type, bool) {
	if tv, ok := info.Types[call.Fun]; ok && tv.IsType() {
		return tv.Type, true
	}
	return nil, false
}

// isNonTypeParamInterface reports whether t is a non-type parameter interface
// type.
func isNonTypeParamInterface(t types.Type) bool {
	return !typeparams.IsTypeParam(t) && types.IsInterface(t)
}

// isUsedOutsideCall reports whether v is used outside of caller.Call, within
// the body of caller.enclosingFunc.
func isUsedOutsideCall(caller *Caller, v *types.Var) bool {
	used := false
	ast.Inspect(caller.enclosingFunc.Body, func(n ast.Node) bool {
		if n == caller.Call {
			return false
		}
		switch n := n.(type) {
		case *ast.Ident:
			if use := caller.Info.Uses[n]; use == v {
				used = true
			}
		case *ast.FuncType:
			// All params are used.
			for _, fld := range n.Params.List {
				for _, n := range fld.Names {
					if def := caller.Info.Defs[n]; def == v {
						used = true
					}
				}
			}
		}
		return !used // keep going until we find a use
	})
	return used
}

// checkFalconConstraints checks whether constant arguments
// are safe to substitute (e.g. s[i] -> ""[0] is not safe.)
//
// Any failed constraint causes us to reject all constant arguments as
// substitution candidates (by clearing args[i].substitution=false).
//
// TODO(adonovan): we could obtain a finer result rejecting only the
// freevars of each failed constraint, and processing constraints in
// order of increasing arity, but failures are quite rare.
func checkFalconConstraints(logf logger, params []*parameter, args []*argument, falcon falconResult, sg substGraph) bool {
	// Create a dummy package, as this is the only
	// way to create an environment for CheckExpr.
	pkg := types.NewPackage("falcon", "falcon")

	// Declare types used by constraints.
	for _, typ := range falcon.Types {
		logf("falcon env: type %s %s", typ.Name, types.Typ[typ.Kind])
		pkg.Scope().Insert(types.NewTypeName(token.NoPos, pkg, typ.Name, types.Typ[typ.Kind]))
	}

	// Declared constants and variables for for parameters.
	nconst := 0
	for i, param := range params {
		name := param.info.Name
		if name == "" {
			continue // unreferenced
		}
		arg := args[i]
		if arg.constant != nil && sg.has(arg) && param.info.FalconType != "" {
			t := pkg.Scope().Lookup(param.info.FalconType).Type()
			pkg.Scope().Insert(types.NewConst(token.NoPos, pkg, name, t, arg.constant))
			logf("falcon env: const %s %s = %v", name, param.info.FalconType, arg.constant)
			nconst++
		} else {
			v := types.NewVar(token.NoPos, pkg, name, arg.typ)
			typesinternal.SetVarKind(v, typesinternal.PackageVar)
			pkg.Scope().Insert(v)
			logf("falcon env: var %s %s", name, arg.typ)
		}
	}
	if nconst == 0 {
		return false // nothing to do
	}

	// Parse and evaluate the constraints in the environment.
	fset := token.NewFileSet()
	removed := false
	for _, falcon := range falcon.Constraints {
		expr, err := parser.ParseExprFrom(fset, "falcon", falcon, 0)
		if err != nil {
			panic(fmt.Sprintf("failed to parse falcon constraint %s: %v", falcon, err))
		}
		if err := types.CheckExpr(fset, pkg, token.NoPos, expr, nil); err != nil {
			logf("falcon: constraint %s violated: %v", falcon, err)
			for j, arg := range args {
				if arg.constant != nil && sg.has(arg) {
					logf("keeping param %q due falcon violation", params[j].info.Name)
					removed = sg.remove(arg) || removed
				}
			}
			break
		}
		logf("falcon: constraint %s satisfied", falcon)
	}
	return removed
}

// resolveEffects marks arguments as non-substitutable to resolve
// hazards resulting from the callee evaluation order described by the
// effects list.
//
// To do this, each argument is categorized as a read (R), write (W),
// or pure. A hazard occurs when the order of evaluation of a W
// changes with respect to any R or W. Pure arguments can be
// effectively ignored, as they can be safely evaluated in any order.
//
// The callee effects list contains the index of each parameter in the
// order it is first evaluated during execution of the callee. In
// addition, the two special values R∞ and W∞ indicate the relative
// position of the callee's first non-parameter read and its first
// effects (or other unknown behavior).
// For example, the list [0 2 1 R∞ 3 W∞] for func(a, b, c, d)
// indicates that the callee referenced parameters a, c, and b,
// followed by an arbitrary read, then parameter d, and finally
// unknown behavior.
//
// When an argument is marked as not substitutable, we say that it is
// 'bound', in the sense that its evaluation occurs in a binding decl
// or literalized call. Such bindings always occur in the original
// callee parameter order.
//
// In this context, "resolving hazards" means binding arguments so
// that they are evaluated in a valid, hazard-free order. A trivial
// solution to this problem would be to bind all arguments, but of
// course that's not useful. The goal is to bind as few arguments as
// possible.
//
// The algorithm proceeds by inspecting arguments in reverse parameter
// order (right to left), preserving the invariant that every
// higher-ordered argument is either already substituted or does not
// need to be substituted. At each iteration, if there is an
// evaluation hazard in the callee effects relative to the current
// argument, the argument must be bound. Subsequently, if the argument
// is bound for any reason, each lower-ordered argument must also be
// bound if either the argument or lower-order argument is a
// W---otherwise the binding itself would introduce a hazard.
//
// Thus, after each iteration, there are no hazards relative to the
// current argument. Subsequent iterations cannot introduce hazards
// with that argument because they can result only in additional
// binding of lower-ordered arguments.
func resolveEffects(logf logger, args []*argument, effects []int, sg substGraph) bool {
	effectStr := func(effects bool, idx int) string {
		i := fmt.Sprint(idx)
		if idx == len(args) {
			i = "∞"
		}
		return string("RW"[btoi(effects)]) + i
	}
	removed := false
	for i := len(args) - 1; i >= 0; i-- {
		argi := args[i]
		if sg.has(argi) && !argi.pure {
			// i is not bound: check whether it must be bound due to hazards.
			idx := slices.Index(effects, i)
			if idx >= 0 {
				for _, j := range effects[:idx] {
					var (
						ji int  // effective param index
						jw bool // j is a write
					)
					if j == winf || j == rinf {
						jw = j == winf
						ji = len(args)
					} else {
						jw = args[j].effects
						ji = j
					}
					if ji > i && (jw || argi.effects) { // out of order evaluation
						logf("binding argument %s: preceded by %s",
							effectStr(argi.effects, i), effectStr(jw, ji))

						removed = sg.remove(argi) || removed
						break
					}
				}
			}
		}
		if !sg.has(argi) {
			for j := 0; j < i; j++ {
				argj := args[j]
				if argj.pure {
					continue
				}
				if (argi.effects || argj.effects) && sg.has(argj) {
					logf("binding argument %s: %s is bound",
						effectStr(argj.effects, j), effectStr(argi.effects, i))

					removed = sg.remove(argj) || removed
				}
			}
		}
	}
	return removed
}

// A substGraph is a directed graph representing arguments that may be
// substituted, provided all of their related arguments (or "dependencies") are
// also substituted. The candidates arguments for substitution are the keys in
// this graph, and the edges represent shadowing of free variables of the key
// by parameters corresponding to the dependency arguments.
//
// Any argument not present as a map key is known not to be substitutable. Some
// arguments may have edges leading to other arguments that are not present in
// the graph. In this case, those arguments also cannot be substituted, because
// they have free variables that are shadowed by parameters that cannot be
// substituted. Calling [substGraph.prune] removes these arguments from the
// graph.
//
// The 'prune' operation is not built into the 'remove' step both because
// analyses (falcon, effects) need local information about each argument
// independent of dependencies, and for the efficiency of pruning once en masse
// after each analysis.
type substGraph map[*argument][]*argument

// has reports whether arg is a candidate for substitution.
func (g substGraph) has(arg *argument) bool {
	_, ok := g[arg]
	return ok
}

// remove marks arg as not substitutable, reporting whether the arg was
// previously substitutable.
//
// remove does not have side effects on other arguments that may be
// unsubstitutable as a result of their dependency being removed.
// Call [substGraph.prune] to propagate these side effects, removing dependent
// arguments.
func (g substGraph) remove(arg *argument) bool {
	pre := len(g)
	delete(g, arg)
	return len(g) < pre
}

// prune updates the graph to remove any keys that reach other arguments not
// present in the graph.
func (g substGraph) prune() {
	// visit visits the forward transitive closure of arg and reports whether any
	// missing argument was encountered, removing all nodes on the path to it
	// from arg.
	//
	// The seen map is used for cycle breaking. In the presence of cycles, visit
	// may report a false positive for an intermediate argument. For example,
	// consider the following graph, where only a and b are candidates for
	// substitution (meaning, only a and b are present in the graph).
	//
	//   a ↔ b
	//   ↓
	//  [c]
	//
	// In this case, starting a visit from a, visit(b, seen) may report 'true',
	// because c has not yet been considered. For this reason, we must guarantee
	// that visit is called with an empty seen map at least once for each node.
	var visit func(*argument, map[*argument]unit) bool
	visit = func(arg *argument, seen map[*argument]unit) bool {
		deps, ok := g[arg]
		if !ok {
			return false
		}
		if _, ok := seen[arg]; !ok {
			seen[arg] = unit{}
			for _, dep := range deps {
				if !visit(dep, seen) {
					delete(g, arg)
					return false
				}
			}
		}
		return true
	}
	for arg := range g {
		// Remove any argument that is, or transitively depends upon,
		// an unsubstitutable argument.
		//
		// Each visitation gets a fresh cycle-breaking set.
		visit(arg, make(map[*argument]unit))
	}
}

// updateCalleeParams updates the calleeDecl syntax to remove
// substituted parameters and move the receiver (if any) to the head
// of the ordinary parameters.
func updateCalleeParams(calleeDecl *ast.FuncDecl, params []*parameter) {
	// The logic is fiddly because of the three forms of ast.Field:
	//
	//	func(int), func(x int), func(x, y int)
	//
	// Also, ensure that all remaining parameters are named
	// to avoid a mix of named/unnamed when joining (recv, params...).
	// func (T) f(int, bool) -> (_ T, _ int, _ bool)
	// (Strictly, we need do this only for methods and only when
	// the namednesses of Recv and Params differ; that might be tidier.)

	paramIdx := 0 // index in original parameter list (incl. receiver)
	var newParams []*ast.Field
	filterParams := func(field *ast.Field) {
		var names []*ast.Ident
		if field.Names == nil {
			// Unnamed parameter field (e.g. func f(int)
			if params[paramIdx] != nil {
				// Give it an explicit name "_" since we will
				// make the receiver (if any) a regular parameter
				// and one cannot mix named and unnamed parameters.
				names = append(names, makeIdent("_"))
			}
			paramIdx++
		} else {
			// Named parameter field e.g. func f(x, y int)
			// Remove substituted parameters in place.
			// If all were substituted, delete field.
			for _, id := range field.Names {
				if pinfo := params[paramIdx]; pinfo != nil {
					// Rename unreferenced parameters with "_".
					// This is crucial for binding decls, since
					// unlike parameters, they are subject to
					// "unreferenced var" checks.
					if len(pinfo.info.Refs) == 0 {
						id = makeIdent("_")
					}
					names = append(names, id)
				}
				paramIdx++
			}
		}
		if names != nil {
			newParams = append(newParams, &ast.Field{
				Names: names,
				Type:  field.Type,
			})
		}
	}
	if calleeDecl.Recv != nil {
		filterParams(calleeDecl.Recv.List[0])
		calleeDecl.Recv = nil
	}
	for _, field := range calleeDecl.Type.Params.List {
		filterParams(field)
	}
	calleeDecl.Type.Params.List = newParams
}

// bindingDeclInfo records information about the binding decl produced by
// createBindingDecl.
type bindingDeclInfo struct {
	names map[string]bool // names bound by the binding decl; possibly empty
	stmt  ast.Stmt        // the binding decl itself
}

// createBindingDecl constructs a "binding decl" that implements
// parameter assignment and declares any named result variables
// referenced by the callee. It returns nil if there were no
// unsubstituted parameters.
//
// It may not always be possible to create the decl (e.g. due to
// shadowing), in which case it also returns nil; but if it succeeds,
// the declaration may be used by reduction strategies to relax the
// requirement that all parameters have been substituted.
//
// For example, a call:
//
//	f(a0, a1, a2)
//
// where:
//
//	func f(p0, p1 T0, p2 T1) { body }
//
// reduces to:
//
//	{
//	  var (
//	    p0, p1 T0 = a0, a1
//	    p2     T1 = a2
//	  )
//	  body
//	}
//
// so long as p0, p1 ∉ freevars(T1) or freevars(a2), and so on,
// because each spec is statically resolved in sequence and
// dynamically assigned in sequence. By contrast, all
// parameters are resolved simultaneously and assigned
// simultaneously.
//
// The pX names should already be blank ("_") if the parameter
// is unreferenced; this avoids "unreferenced local var" checks.
//
// Strategies may impose additional checks on return
// conversions, labels, defer, etc.
func createBindingDecl(logf logger, caller *Caller, args []*argument, calleeDecl *ast.FuncDecl, results []*paramInfo) *bindingDeclInfo {
	// Spread calls are tricky as they may not align with the
	// parameters' field groupings nor types.
	// For example, given
	//   func g() (int, string)
	// the call
	//   f(g())
	// is legal with these decls of f:
	//   func f(int, string)
	//   func f(x, y any)
	//   func f(x, y ...any)
	// TODO(adonovan): support binding decls for spread calls by
	// splitting parameter groupings as needed.
	if lastArg := last(args); lastArg != nil && lastArg.spread {
		logf("binding decls not yet supported for spread calls")
		return nil
	}

	var (
		specs []ast.Spec
		names = make(map[string]bool) // names defined by previous specs
	)
	// shadow reports whether any name referenced by spec is
	// shadowed by a name declared by a previous spec (since,
	// unlike parameters, each spec of a var decl is within the
	// scope of the previous specs).
	shadow := func(spec *ast.ValueSpec) bool {
		// Compute union of free names of type and values
		// and detect shadowing. Values is the arguments
		// (caller syntax), so we can use type info.
		// But Type is the untyped callee syntax,
		// so we have to use a syntax-only algorithm.
		free := make(map[string]bool)
		for _, value := range spec.Values {
			for name := range freeVars(caller.Info, value) {
				free[name] = true
			}
		}
		const includeComplitIdents = true
		freeishNames(free, spec.Type, includeComplitIdents)
		for name := range free {
			if names[name] {
				logf("binding decl would shadow free name %q", name)
				return true
			}
		}
		for _, id := range spec.Names {
			if id.Name != "_" {
				names[id.Name] = true
			}
		}
		return false
	}

	// parameters
	//
	// Bind parameters that were not eliminated through
	// substitution. (Non-nil arguments correspond to the
	// remaining parameters in calleeDecl.)
	var values []ast.Expr
	for _, arg := range args {
		if arg != nil {
			values = append(values, arg.expr)
		}
	}
	for _, field := range calleeDecl.Type.Params.List {
		// Each field (param group) becomes a ValueSpec.
		spec := &ast.ValueSpec{
			Names:  cleanNodes(field.Names),
			Type:   cleanNode(field.Type),
			Values: values[:len(field.Names)],
		}
		values = values[len(field.Names):]
		if shadow(spec) {
			return nil
		}
		specs = append(specs, spec)
	}
	assert(len(values) == 0, "args/params mismatch")

	// results
	//
	// Add specs to declare any named result
	// variables that are referenced by the body.
	if calleeDecl.Type.Results != nil {
		resultIdx := 0
		for _, field := range calleeDecl.Type.Results.List {
			if field.Names == nil {
				resultIdx++
				continue // unnamed field
			}
			var names []*ast.Ident
			for _, id := range field.Names {
				if len(results[resultIdx].Refs) > 0 {
					names = append(names, id)
				}
				resultIdx++
			}
			if len(names) > 0 {
				spec := &ast.ValueSpec{
					Names: cleanNodes(names),
					Type:  cleanNode(field.Type),
				}
				if shadow(spec) {
					return nil
				}
				specs = append(specs, spec)
			}
		}
	}

	if len(specs) == 0 {
		logf("binding decl not needed: all parameters substituted")
		return nil
	}

	stmt := &ast.DeclStmt{
		Decl: &ast.GenDecl{
			Tok:   token.VAR,
			Specs: specs,
		},
	}
	logf("binding decl: %s", debugFormatNode(caller.Fset, stmt))
	return &bindingDeclInfo{names: names, stmt: stmt}
}

// lookup does a symbol lookup in the lexical environment of the caller.
func (caller *Caller) lookup(name string) types.Object {
	pos := caller.Call.Pos()
	for _, n := range caller.path {
		if scope := scopeFor(caller.Info, n); scope != nil {
			if _, obj := scope.LookupParent(name, pos); obj != nil {
				return obj
			}
		}
	}
	return nil
}

func scopeFor(info *types.Info, n ast.Node) *types.Scope {
	// The function body scope (containing not just params)
	// is associated with the function's type, not body.
	switch fn := n.(type) {
	case *ast.FuncDecl:
		n = fn.Type
	case *ast.FuncLit:
		n = fn.Type
	}
	return info.Scopes[n]
}

// -- predicates over expressions --

// freeVars returns the names of all free identifiers of e:
// those lexically referenced by it but not defined within it.
// (Fields and methods are not included.)
func freeVars(info *types.Info, e ast.Expr) map[string]bool {
	free := make(map[string]bool)
	ast.Inspect(e, func(n ast.Node) bool {
		if id, ok := n.(*ast.Ident); ok {
			// The isField check is so that we don't treat T{f: 0} as a ref to f.
			if obj, ok := info.Uses[id]; ok && !within(obj.Pos(), e) && !isField(obj) {
				free[obj.Name()] = true
			}
		}
		return true
	})
	return free
}

// effects reports whether an expression might change the state of the
// program (through function calls and channel receives) and affect
// the evaluation of subsequent expressions.
func (st *state) effects(info *types.Info, expr ast.Expr) bool {
	effects := false
	ast.Inspect(expr, func(n ast.Node) bool {
		switch n := n.(type) {
		case *ast.FuncLit:
			return false // prune descent

		case *ast.CallExpr:
			if info.Types[n.Fun].IsType() {
				// A conversion T(x) has only the effect of its operand.
			} else if !callsPureBuiltin(info, n) {
				// A handful of built-ins have no effect
				// beyond those of their arguments.
				// All other calls (including append, copy, recover)
				// have unknown effects.
				//
				// As with 'pure', there is room for
				// improvement by inspecting the callee.
				effects = true
			}

		case *ast.UnaryExpr:
			if n.Op == token.ARROW { // <-ch
				effects = true
			}
		}
		return true
	})

	// Even if consideration of effects is not desired,
	// we continue to compute, log, and discard them.
	if st.opts.IgnoreEffects && effects {
		effects = false
		st.opts.Logf("ignoring potential effects of argument %s",
			debugFormatNode(st.caller.Fset, expr))
	}

	return effects
}

// pure reports whether an expression has the same result no matter
// when it is executed relative to other expressions, so it can be
// commuted with any other expression or statement without changing
// its meaning.
//
// An expression is considered impure if it reads the contents of any
// variable, with the exception of "single assignment" local variables
// (as classified by the provided callback), which are never updated
// after their initialization.
//
// Pure does not imply duplicable: for example, new(T) and T{} are
// pure expressions but both return a different value each time they
// are evaluated, so they are not safe to duplicate.
//
// Purity does not imply freedom from run-time panics. We assume that
// target programs do not encounter run-time panics nor depend on them
// for correct operation.
//
// TODO(adonovan): add unit tests of this function.
func pure(info *types.Info, assign1 func(*types.Var) bool, e ast.Expr) bool {
	var pure func(e ast.Expr) bool
	pure = func(e ast.Expr) bool {
		switch e := e.(type) {
		case *ast.ParenExpr:
			return pure(e.X)

		case *ast.Ident:
			if v, ok := info.Uses[e].(*types.Var); ok {
				// In general variables are impure
				// as they may be updated, but
				// single-assignment local variables
				// never change value.
				//
				// We assume all package-level variables
				// may be updated, but for non-exported
				// ones we could do better by analyzing
				// the complete package.
				return !isPkgLevel(v) && assign1(v)
			}

			// All other kinds of reference are pure.
			return true

		case *ast.FuncLit:
			// A function literal may allocate a closure that
			// references mutable variables, but mutation
			// cannot be observed without calling the function,
			// and calls are considered impure.
			return true

		case *ast.BasicLit:
			return true

		case *ast.UnaryExpr: // + - ! ^ & but not <-
			return e.Op != token.ARROW && pure(e.X)

		case *ast.BinaryExpr: // arithmetic, shifts, comparisons, &&/||
			return pure(e.X) && pure(e.Y)

		case *ast.CallExpr:
			// A conversion is as pure as its operand.
			if info.Types[e.Fun].IsType() {
				return pure(e.Args[0])
			}

			// Calls to some built-ins are as pure as their arguments.
			if callsPureBuiltin(info, e) {
				for _, arg := range e.Args {
					if !pure(arg) {
						return false
					}
				}
				return true
			}

			// All other calls are impure, so we can
			// reject them without even looking at e.Fun.
			//
			// More sophisticated analysis could infer purity in
			// commonly used functions such as strings.Contains;
			// perhaps we could offer the client a hook so that
			// go/analysis-based implementation could exploit the
			// results of a purity analysis. But that would make
			// the inliner's choices harder to explain.
			return false

		case *ast.CompositeLit:
			// T{...} is as pure as its elements.
			for _, elt := range e.Elts {
				if kv, ok := elt.(*ast.KeyValueExpr); ok {
					if !pure(kv.Value) {
						return false
					}
					if id, ok := kv.Key.(*ast.Ident); ok {
						if v, ok := info.Uses[id].(*types.Var); ok && v.IsField() {
							continue // struct {field: value}
						}
					}
					// map/slice/array {key: value}
					if !pure(kv.Key) {
						return false
					}

				} else if !pure(elt) {
					return false
				}
			}
			return true

		case *ast.SelectorExpr:
			if seln, ok := info.Selections[e]; ok {
				// See types.SelectionKind for background.
				switch seln.Kind() {
				case types.MethodExpr:
					// A method expression T.f acts like a
					// reference to a func decl, so it is pure.
					return true

				case types.MethodVal, types.FieldVal:
					// A field or method selection x.f is pure
					// if x is pure and the selection does
					// not indirect a pointer.
					return !indirectSelection(seln) && pure(e.X)

				default:
					panic(seln)
				}
			} else {
				// A qualified identifier is
				// treated like an unqualified one.
				return pure(e.Sel)
			}

		case *ast.StarExpr:
			return false // *ptr depends on the state of the heap

		default:
			return false
		}
	}
	return pure(e)
}

// callsPureBuiltin reports whether call is a call of a built-in
// function that is a pure computation over its operands (analogous to
// a + operator). Because it does not depend on program state, it may
// be evaluated at any point--though not necessarily at multiple
// points (consider new, make).
func callsPureBuiltin(info *types.Info, call *ast.CallExpr) bool {
	if id, ok := ast.Unparen(call.Fun).(*ast.Ident); ok {
		if b, ok := info.ObjectOf(id).(*types.Builtin); ok {
			switch b.Name() {
			case "len", "cap", "complex", "imag", "real", "make", "new", "max", "min":
				return true
			}
			// Not: append clear close copy delete panic print println recover
		}
	}
	return false
}

// duplicable reports whether it is appropriate for the expression to
// be freely duplicated.
//
// Given the declaration
//
//	func f(x T) T { return x + g() + x }
//
// an argument y is considered duplicable if we would wish to see a
// call f(y) simplified to y+g()+y. This is true for identifiers,
// integer literals, unary negation, and selectors x.f where x is not
// a pointer. But we would not wish to duplicate expressions that:
// - have side effects (e.g. nearly all calls),
// - are not referentially transparent (e.g. &T{}, ptr.field, *ptr), or
// - are long (e.g. "huge string literal").
func duplicable(info *types.Info, e ast.Expr) bool {
	switch e := e.(type) {
	case *ast.ParenExpr:
		return duplicable(info, e.X)

	case *ast.Ident:
		return true

	case *ast.BasicLit:
		v := info.Types[e].Value
		switch e.Kind {
		case token.INT:
			return true // any int
		case token.STRING:
			return consteq(v, kZeroString) // only ""
		case token.FLOAT:
			return consteq(v, kZeroFloat) || consteq(v, kOneFloat) // only 0.0 or 1.0
		}

	case *ast.UnaryExpr: // e.g. +1, -1
		return (e.Op == token.ADD || e.Op == token.SUB) && duplicable(info, e.X)

	case *ast.CompositeLit:
		// Empty struct or array literals T{} are duplicable.
		// (Non-empty literals are too verbose, and slice/map
		// literals allocate indirect variables.)
		if len(e.Elts) == 0 {
			switch info.TypeOf(e).Underlying().(type) {
			case *types.Struct, *types.Array:
				return true
			}
		}
		return false

	case *ast.CallExpr:
		// Treat type conversions as duplicable if they do not observably allocate.
		// The only cases of observable allocations are
		// the `[]byte(string)` and `[]rune(string)` conversions.
		//
		// Duplicating string([]byte) conversions increases
		// allocation but doesn't change behavior, but the
		// reverse, []byte(string), allocates a distinct array,
		// which is observable.

		if !info.Types[e.Fun].IsType() { // check whether e.Fun is a type conversion
			return false
		}

		fun := info.TypeOf(e.Fun)
		arg := info.TypeOf(e.Args[0])

		switch fun := fun.Underlying().(type) {
		case *types.Slice:
			// Do not mark []byte(string) and []rune(string) as duplicable.
			elem, ok := fun.Elem().Underlying().(*types.Basic)
			if ok && (elem.Kind() == types.Rune || elem.Kind() == types.Byte) {
				from, ok := arg.Underlying().(*types.Basic)
				isString := ok && from.Info()&types.IsString != 0
				return !isString
			}
		case *types.TypeParam:
			return false // be conservative
		}
		return true

	case *ast.SelectorExpr:
		if seln, ok := info.Selections[e]; ok {
			// A field or method selection x.f is referentially
			// transparent if it does not indirect a pointer.
			return !indirectSelection(seln)
		}
		// A qualified identifier pkg.Name is referentially transparent.
		return true
	}
	return false
}

func consteq(x, y constant.Value) bool {
	return constant.Compare(x, token.EQL, y)
}

var (
	kZeroInt    = constant.MakeInt64(0)
	kZeroString = constant.MakeString("")
	kZeroFloat  = constant.MakeFloat64(0.0)
	kOneFloat   = constant.MakeFloat64(1.0)
)

// -- inline helpers --

func assert(cond bool, msg string) {
	if !cond {
		panic(msg)
	}
}

// blanks returns a slice of n > 0 blank identifiers.
func blanks[E ast.Expr](n int) []E {
	if n == 0 {
		panic("blanks(0)")
	}
	res := make([]E, n)
	for i := range res {
		res[i] = ast.Expr(makeIdent("_")).(E) // ugh
	}
	return res
}

func makeIdent(name string) *ast.Ident {
	return &ast.Ident{Name: name}
}

// importedPkgName returns the PkgName object declared by an ImportSpec.
// TODO(adonovan): make this a method of types.Info (#62037).
func importedPkgName(info *types.Info, imp *ast.ImportSpec) (*types.PkgName, bool) {
	var obj types.Object
	if imp.Name != nil {
		obj = info.Defs[imp.Name]
	} else {
		obj = info.Implicits[imp]
	}
	pkgname, ok := obj.(*types.PkgName)
	return pkgname, ok
}

func isPkgLevel(obj types.Object) bool {
	// TODO(adonovan): consider using the simpler obj.Parent() ==
	// obj.Pkg().Scope() instead. But be sure to test carefully
	// with instantiations of generics.
	return obj.Pkg().Scope().Lookup(obj.Name()) == obj
}

// callContext returns the two nodes immediately enclosing the call
// (specified as a PathEnclosingInterval), ignoring parens.
func callContext(callPath []ast.Node) (parent, grandparent ast.Node) {
	_ = callPath[0].(*ast.CallExpr) // sanity check
	for _, n := range callPath[1:] {
		if !is[*ast.ParenExpr](n) {
			if parent == nil {
				parent = n
			} else {
				return parent, n
			}
		}
	}
	return parent, nil
}

// hasLabelConflict reports whether the set of labels of the function
// enclosing the call (specified as a PathEnclosingInterval)
// intersects with the set of callee labels.
func hasLabelConflict(callPath []ast.Node, calleeLabels []string) bool {
	labels := callerLabels(callPath)
	for _, label := range calleeLabels {
		if labels[label] {
			return true // conflict
		}
	}
	return false
}

// callerLabels returns the set of control labels in the function (if
// any) enclosing the call (specified as a PathEnclosingInterval).
func callerLabels(callPath []ast.Node) map[string]bool {
	var callerBody *ast.BlockStmt
	switch f := callerFunc(callPath).(type) {
	case *ast.FuncDecl:
		callerBody = f.Body
	case *ast.FuncLit:
		callerBody = f.Body
	}
	var labels map[string]bool
	if callerBody != nil {
		ast.Inspect(callerBody, func(n ast.Node) bool {
			switch n := n.(type) {
			case *ast.FuncLit:
				return false // prune traversal
			case *ast.LabeledStmt:
				if labels == nil {
					labels = make(map[string]bool)
				}
				labels[n.Label.Name] = true
			}
			return true
		})
	}
	return labels
}

// callerFunc returns the innermost Func{Decl,Lit} node enclosing the
// call (specified as a PathEnclosingInterval).
func callerFunc(callPath []ast.Node) ast.Node {
	_ = callPath[0].(*ast.CallExpr) // sanity check
	for _, n := range callPath[1:] {
		if is[*ast.FuncDecl](n) || is[*ast.FuncLit](n) {
			return n
		}
	}
	return nil
}

// callStmt reports whether the function call (specified
// as a PathEnclosingInterval) appears within an ExprStmt,
// and returns it if so.
//
// If unrestricted, callStmt returns nil if the ExprStmt f() appears
// in a restricted context (such as "if f(); cond {") where it cannot
// be replaced by an arbitrary statement. (See "statement theory".)
func callStmt(callPath []ast.Node, unrestricted bool) *ast.ExprStmt {
	parent, _ := callContext(callPath)
	stmt, ok := parent.(*ast.ExprStmt)
	if ok && unrestricted {
		switch callPath[slices.Index(callPath, ast.Node(stmt))+1].(type) {
		case *ast.LabeledStmt,
			*ast.BlockStmt,
			*ast.CaseClause,
			*ast.CommClause:
			// unrestricted
		default:
			// TODO(adonovan): handle restricted
			// XYZStmt.Init contexts (but not ForStmt.Post)
			// by creating a block around the if/for/switch:
			// "if f(); cond {"  ->  "{ stmts; if cond {"

			return nil // restricted
		}
	}
	return stmt
}

// Statement theory
//
// These are all the places a statement may appear in the AST:
//
// LabeledStmt.Stmt       Stmt      -- any
// BlockStmt.List       []Stmt      -- any (but see switch/select)
// IfStmt.Init            Stmt?     -- simple
// IfStmt.Body            BlockStmt
// IfStmt.Else            Stmt?     -- IfStmt or BlockStmt
// CaseClause.Body      []Stmt      -- any
// SwitchStmt.Init        Stmt?     -- simple
// SwitchStmt.Body        BlockStmt -- CaseClauses only
// TypeSwitchStmt.Init    Stmt?     -- simple
// TypeSwitchStmt.Assign  Stmt      -- AssignStmt(TypeAssertExpr) or ExprStmt(TypeAssertExpr)
// TypeSwitchStmt.Body    BlockStmt -- CaseClauses only
// CommClause.Comm        Stmt?     -- SendStmt or ExprStmt(UnaryExpr) or AssignStmt(UnaryExpr)
// CommClause.Body      []Stmt      -- any
// SelectStmt.Body        BlockStmt -- CommClauses only
// ForStmt.Init           Stmt?     -- simple
// ForStmt.Post           Stmt?     -- simple
// ForStmt.Body           BlockStmt
// RangeStmt.Body         BlockStmt
//
// simple = AssignStmt | SendStmt | IncDecStmt | ExprStmt.
//
// A BlockStmt cannot replace an ExprStmt in
// {If,Switch,TypeSwitch}Stmt.Init or ForStmt.Post.
// That is allowed only within:
//   LabeledStmt.Stmt       Stmt
//   BlockStmt.List       []Stmt
//   CaseClause.Body      []Stmt
//   CommClause.Body      []Stmt

// replaceNode performs a destructive update of the tree rooted at
// root, replacing each occurrence of "from" with "to". If to is nil and
// the element is within a slice, the slice element is removed.
//
// The root itself cannot be replaced; an attempt will panic.
//
// This function must not be called on the caller's syntax tree.
//
// TODO(adonovan): polish this up and move it to astutil package.
// TODO(adonovan): needs a unit test.
func replaceNode(root ast.Node, from, to ast.Node) {
	if from == nil {
		panic("from == nil")
	}
	if reflect.ValueOf(from).IsNil() {
		panic(fmt.Sprintf("from == (%T)(nil)", from))
	}
	if from == root {
		panic("from == root")
	}
	found := false
	var parent reflect.Value // parent variable of interface type, containing a pointer
	var visit func(reflect.Value)
	visit = func(v reflect.Value) {
		switch v.Kind() {
		case reflect.Pointer:
			if v.Interface() == from {
				found = true

				// If v is a struct field or array element
				// (e.g. Field.Comment or Field.Names[i])
				// then it is addressable (a pointer variable).
				//
				// But if it was the value an interface
				// (e.g. *ast.Ident within ast.Node)
				// then it is non-addressable, and we need
				// to set the enclosing interface (parent).
				if !v.CanAddr() {
					v = parent
				}

				// to=nil => use zero value
				var toV reflect.Value
				if to != nil {
					toV = reflect.ValueOf(to)
				} else {
					toV = reflect.Zero(v.Type()) // e.g. ast.Expr(nil)
				}
				v.Set(toV)

			} else if !v.IsNil() {
				switch v.Interface().(type) {
				case *ast.Object, *ast.Scope:
					// Skip fields of types potentially involved in cycles.
				default:
					visit(v.Elem())
				}
			}

		case reflect.Struct:
			for i := range v.Type().NumField() {
				visit(v.Field(i))
			}

		case reflect.Slice:
			compact := false
			for i := range v.Len() {
				visit(v.Index(i))
				if v.Index(i).IsNil() {
					compact = true
				}
			}
			if compact {
				// Elements were deleted. Eliminate nils.
				// (Do this is a second pass to avoid
				// unnecessary writes in the common case.)
				j := 0
				for i := range v.Len() {
					if !v.Index(i).IsNil() {
						v.Index(j).Set(v.Index(i))
						j++
					}
				}
				v.SetLen(j)
			}
		case reflect.Interface:
			parent = v
			visit(v.Elem())

		case reflect.Array, reflect.Chan, reflect.Func, reflect.Map, reflect.UnsafePointer:
			panic(v) // unreachable in AST
		default:
			// bool, string, number: nop
		}
		parent = reflect.Value{}
	}
	visit(reflect.ValueOf(root))
	if !found {
		panic(fmt.Sprintf("%T not found", from))
	}
}

// cleanNode returns a clone of node with positions cleared.
//
// It should be used for any callee nodes that are formatted using the caller
// file set.
func cleanNode[T ast.Node](node T) T {
	clone := internalastutil.CloneNode(node)
	clearPositions(clone)
	return clone
}

func cleanNodes[T ast.Node](nodes []T) []T {
	var clean []T
	for _, node := range nodes {
		clean = append(clean, cleanNode(node))
	}
	return clean
}

// clearPositions destroys token.Pos information within the tree rooted at root,
// as positions in callee trees may cause caller comments to be emitted prematurely.
//
// In general it isn't safe to clear a valid Pos because some of them
// (e.g. CallExpr.Ellipsis, TypeSpec.Assign) are significant to
// go/printer, so this function sets each non-zero Pos to 1, which
// suffices to avoid advancing the printer's comment cursor.
//
// This function mutates its argument; do not invoke on caller syntax.
//
// TODO(adonovan): remove this horrendous workaround when #20744 is finally fixed.
func clearPositions(root ast.Node) {
	posType := reflect.TypeOf(token.NoPos)
	ast.Inspect(root, func(n ast.Node) bool {
		if n != nil {
			v := reflect.ValueOf(n).Elem() // deref the pointer to struct
			fields := v.Type().NumField()
			for i := range fields {
				f := v.Field(i)
				// Clearing Pos arbitrarily is destructive,
				// as its presence may be semantically significant
				// (e.g. CallExpr.Ellipsis, TypeSpec.Assign)
				// or affect formatting preferences (e.g. GenDecl.Lparen).
				//
				// Note: for proper formatting, it may be necessary to be selective
				// about which positions we set to 1 vs which we set to token.NoPos.
				// (e.g. we can set most to token.NoPos, save the few that are
				// significant).
				if f.Type() == posType {
					if f.Interface() != token.NoPos {
						f.Set(reflect.ValueOf(token.Pos(1)))
					}
				}
			}
		}
		return true
	})
}

// findIdent finds the Ident beneath root that has the given pos.
// It returns the path to the ident (excluding the ident), and the ident
// itself, where the path is the sequence of ast.Nodes encountered in a
// depth-first search to find ident.
func findIdent(root ast.Node, pos token.Pos) ([]ast.Node, *ast.Ident) {
	// TODO(adonovan): opt: skip subtrees that don't contain pos.
	var (
		path  []ast.Node
		found *ast.Ident
	)
	ast.Inspect(root, func(n ast.Node) bool {
		if found != nil {
			return false
		}
		if n == nil {
			path = path[:len(path)-1]
			return false
		}
		if id, ok := n.(*ast.Ident); ok {
			if id.Pos() == pos {
				found = id
				return true
			}
		}
		path = append(path, n)
		return true
	})
	if found == nil {
		panic(fmt.Sprintf("findIdent %d not found in %s",
			pos, debugFormatNode(token.NewFileSet(), root)))
	}
	return path, found
}

func prepend[T any](elem T, slice ...T) []T {
	return append([]T{elem}, slice...)
}

// debugFormatNode formats a node or returns a formatting error.
// Its sloppy treatment of errors is appropriate only for logging.
func debugFormatNode(fset *token.FileSet, n ast.Node) string {
	var out strings.Builder
	if err := format.Node(&out, fset, n); err != nil {
		out.WriteString(err.Error())
	}
	return out.String()
}

func shallowCopy[T any](ptr *T) *T {
	copy := *ptr
	return &copy
}

// ∀
func forall[T any](list []T, f func(i int, x T) bool) bool {
	for i, x := range list {
		if !f(i, x) {
			return false
		}
	}
	return true
}

// ∃
func exists[T any](list []T, f func(i int, x T) bool) bool {
	for i, x := range list {
		if f(i, x) {
			return true
		}
	}
	return false
}

// last returns the last element of a slice, or zero if empty.
func last[T any](slice []T) T {
	n := len(slice)
	if n > 0 {
		return slice[n-1]
	}
	return *new(T)
}

// consistentOffsets reports whether the portion of caller.Content
// that corresponds to caller.Call can be parsed as a call expression.
// If not, the client has provided inconsistent information, possibly
// because they forgot to ignore line directives when computing the
// filename enclosing the call.
// This is just a heuristic.
func consistentOffsets(caller *Caller) bool {
	start := offsetOf(caller.Fset, caller.Call.Pos())
	end := offsetOf(caller.Fset, caller.Call.End())
	if !(0 < start && start < end && end <= len(caller.Content)) {
		return false
	}
	expr, err := parser.ParseExpr(string(caller.Content[start:end]))
	if err != nil {
		return false
	}
	return is[*ast.CallExpr](expr)
}

// needsParens reports whether parens are required to avoid ambiguity
// around the new node replacing the specified old node (which is some
// ancestor of the CallExpr identified by its PathEnclosingInterval).
func needsParens(callPath []ast.Node, old, new ast.Node) bool {
	// Find enclosing old node and its parent.
	i := slices.Index(callPath, old)
	if i == -1 {
		panic("not found")
	}

	// There is no precedence ambiguity when replacing
	// (e.g.) a statement enclosing the call.
	if !is[ast.Expr](old) {
		return false
	}

	// An expression beneath a non-expression
	// has no precedence ambiguity.
	parent, ok := callPath[i+1].(ast.Expr)
	if !ok {
		return false
	}

	precedence := func(n ast.Node) int {
		switch n := n.(type) {
		case *ast.UnaryExpr, *ast.StarExpr:
			return token.UnaryPrec
		case *ast.BinaryExpr:
			return n.Op.Precedence()
		}
		return -1
	}

	// Parens are not required if the new node
	// is not unary or binary.
	newprec := precedence(new)
	if newprec < 0 {
		return false
	}

	// Parens are required if parent and child are both
	// unary or binary and the parent has higher precedence.
	if precedence(parent) > newprec {
		return true
	}

	// Was the old node the operand of a postfix operator?
	//  f().sel
	//  f()[i:j]
	//  f()[i]
	//  f().(T)
	//  f()(x)
	switch parent := parent.(type) {
	case *ast.SelectorExpr:
		return parent.X == old
	case *ast.IndexExpr:
		return parent.X == old
	case *ast.SliceExpr:
		return parent.X == old
	case *ast.TypeAssertExpr:
		return parent.X == old
	case *ast.CallExpr:
		return parent.Fun == old
	}
	return false
}

// declares returns the set of lexical names declared by a
// sequence of statements from the same block, excluding sub-blocks.
// (Lexical names do not include control labels.)
func declares(stmts []ast.Stmt) map[string]bool {
	names := make(map[string]bool)
	for _, stmt := range stmts {
		switch stmt := stmt.(type) {
		case *ast.DeclStmt:
			for _, spec := range stmt.Decl.(*ast.GenDecl).Specs {
				switch spec := spec.(type) {
				case *ast.ValueSpec:
					for _, id := range spec.Names {
						names[id.Name] = true
					}
				case *ast.TypeSpec:
					names[spec.Name.Name] = true
				}
			}

		case *ast.AssignStmt:
			if stmt.Tok == token.DEFINE {
				for _, lhs := range stmt.Lhs {
					names[lhs.(*ast.Ident).Name] = true
				}
			}
		}
	}
	delete(names, "_")
	return names
}

// A importNameFunc is used to query local import names in the caller, in a
// particular shadowing context.
//
// The shadow map contains additional names shadowed in the inlined code, at
// the position the local import name is to be used. The shadow map only needs
// to contain newly introduced names in the inlined code; names shadowed at the
// caller are handled automatically.
type importNameFunc = func(pkgPath string, shadow shadowMap) string

// assignStmts rewrites a statement assigning the results of a call into zero
// or more statements that assign its return operands, or (nil, false) if no
// such rewrite is possible. The set of bindings created by the result of
// assignStmts is the same as the set of bindings created by the callerStmt.
//
// The callee must contain exactly one return statement.
//
// This is (once again) a surprisingly complex task. For example, depending on
// types and existing bindings, the assignment
//
//	a, b := f()
//
// could be rewritten as:
//
//	a, b := 1, 2
//
// but may need to be written as:
//
//	a, b := int8(1), int32(2)
//
// In the case where the return statement within f is a spread call to another
// function g(), we cannot explicitly convert the return values inline, and so
// it may be necessary to split the declaration and assignment of variables
// into separate statements:
//
//	a, b := g()
//
// or
//
//	var a int32
//	a, b = g()
//
// or
//
//	var (
//		a int8
//		b int32
//	)
//	a, b = g()
//
// Note: assignStmts may return (nil, true) if it determines that the rewritten
// assignment consists only of _ = nil assignments.
func (st *state) assignStmts(callerStmt *ast.AssignStmt, returnOperands []ast.Expr, importName importNameFunc) ([]ast.Stmt, bool) {
	logf, caller, callee := st.opts.Logf, st.caller, &st.callee.impl

	assert(len(callee.Returns) == 1, "unexpected multiple returns")
	resultInfo := callee.Returns[0]

	// When constructing assign statements, we need to make sure that we don't
	// modify types on the left-hand side, such as would happen if the type of a
	// RHS expression does not match the corresponding LHS type at the caller
	// (due to untyped conversion or interface widening).
	//
	// This turns out to be remarkably tricky to handle correctly.
	//
	// Substrategies below are labeled as `Substrategy <name>:`.

	// Collect LHS information.
	var (
		lhs    []ast.Expr                                // shallow copy of the LHS slice, for mutation
		defs   = make([]*ast.Ident, len(callerStmt.Lhs)) // indexes in lhs of defining identifiers
		blanks = make([]bool, len(callerStmt.Lhs))       // indexes in lhs of blank identifiers
		byType typeutil.Map                              // map of distinct types -> indexes, for writing specs later
	)
	for i, expr := range callerStmt.Lhs {
		lhs = append(lhs, expr)
		if name, ok := expr.(*ast.Ident); ok {
			if name.Name == "_" {
				blanks[i] = true
				continue // no type
			}

			if obj, isDef := caller.Info.Defs[name]; isDef {
				defs[i] = name
				typ := obj.Type()
				idxs, _ := byType.At(typ).([]int)
				idxs = append(idxs, i)
				byType.Set(typ, idxs)
			}
		}
	}

	// Collect RHS information
	//
	// The RHS is either a parallel assignment or spread assignment, but by
	// looping over both callerStmt.Rhs and returnOperands we handle both.
	var (
		rhs             []ast.Expr              // new RHS of assignment, owned by the inliner
		callIdx         = -1                    // index of the call among the original RHS
		nilBlankAssigns = make(map[int]unit)    // indexes in rhs of _ = nil assignments, which can be deleted
		freeNames       = make(map[string]bool) // free(ish) names among rhs expressions
		nonTrivial      = make(map[int]bool)    // indexes in rhs of nontrivial result conversions
	)
	const includeComplitIdents = true

	for i, expr := range callerStmt.Rhs {
		if expr == caller.Call {
			assert(callIdx == -1, "malformed (duplicative) AST")
			callIdx = i
			for j, returnOperand := range returnOperands {
				freeishNames(freeNames, returnOperand, includeComplitIdents)
				rhs = append(rhs, returnOperand)
				if resultInfo[j]&nonTrivialResult != 0 {
					nonTrivial[i+j] = true
				}
				if blanks[i+j] && resultInfo[j]&untypedNilResult != 0 {
					nilBlankAssigns[i+j] = unit{}
				}
			}
		} else {
			// We must clone before clearing positions, since e came from the caller.
			expr = internalastutil.CloneNode(expr)
			clearPositions(expr)
			freeishNames(freeNames, expr, includeComplitIdents)
			rhs = append(rhs, expr)
		}
	}
	assert(callIdx >= 0, "failed to find call in RHS")

	// Substrategy "splice": Check to see if we can simply splice in the result
	// expressions from the callee, such as simplifying
	//
	//  x, y := f()
	//
	// to
	//
	//  x, y := e1, e2
	//
	// where the types of x and y match the types of e1 and e2.
	//
	// This works as long as we don't need to write any additional type
	// information.
	if len(nonTrivial) == 0 { // no non-trivial conversions to worry about

		logf("substrategy: splice assignment")
		return []ast.Stmt{&ast.AssignStmt{
			Lhs:    lhs,
			Tok:    callerStmt.Tok,
			TokPos: callerStmt.TokPos,
			Rhs:    rhs,
		}}, true
	}

	// Inlining techniques below will need to write type information in order to
	// preserve the correct types of LHS identifiers.
	//
	// typeExpr is a simple helper to write out type expressions. It currently
	// handles (possibly qualified) type names.
	//
	// TODO(rfindley):
	//   1. expand this to handle more type expressions.
	//   2. refactor to share logic with callee rewriting.
	universeAny := types.Universe.Lookup("any")
	typeExpr := func(typ types.Type, shadow shadowMap) ast.Expr {
		var (
			typeName string
			obj      *types.TypeName // nil for basic types
		)
		switch typ := typ.(type) {
		case *types.Basic:
			typeName = typ.Name()
		case interface{ Obj() *types.TypeName }: // Named, Alias, TypeParam
			obj = typ.Obj()
			typeName = typ.Obj().Name()
		}

		// Special case: check for universe "any".
		// TODO(golang/go#66921): this may become unnecessary if any becomes a proper alias.
		if typ == universeAny.Type() {
			typeName = "any"
		}

		if typeName == "" {
			return nil
		}

		if obj == nil || obj.Pkg() == nil || obj.Pkg() == caller.Types { // local type or builtin
			if shadow[typeName] != 0 {
				logf("cannot write shadowed type name %q", typeName)
				return nil
			}
			obj, _ := caller.lookup(typeName).(*types.TypeName)
			if obj != nil && types.Identical(obj.Type(), typ) {
				return ast.NewIdent(typeName)
			}
		} else if pkgName := importName(obj.Pkg().Path(), shadow); pkgName != "" {
			return &ast.SelectorExpr{
				X:   ast.NewIdent(pkgName),
				Sel: ast.NewIdent(typeName),
			}
		}
		return nil
	}

	// Substrategy "spread": in the case of a spread call (func f() (T1, T2) return
	// g()), since we didn't hit the 'splice' substrategy, there must be some
	// non-declaring expression on the LHS. Simplify this by pre-declaring
	// variables, rewriting
	//
	//   x, y := f()
	//
	// to
	//
	//  var x int
	//  x, y = g()
	//
	// Which works as long as the predeclared variables do not overlap with free
	// names on the RHS.
	if len(rhs) != len(lhs) {
		assert(len(rhs) == 1 && len(returnOperands) == 1, "expected spread call")

		for _, id := range defs {
			if id != nil && freeNames[id.Name] {
				// By predeclaring variables, we're changing them to be in scope of the
				// RHS. We can't do this if their names are free on the RHS.
				return nil, false
			}
		}

		// Write out the specs, being careful to avoid shadowing free names in
		// their type expressions.
		var (
			specs    []ast.Spec
			specIdxs []int
			shadow   = make(shadowMap)
		)
		failed := false
		byType.Iterate(func(typ types.Type, v any) {
			if failed {
				return
			}
			idxs := v.([]int)
			specIdxs = append(specIdxs, idxs[0])
			texpr := typeExpr(typ, shadow)
			if texpr == nil {
				failed = true
				return
			}
			spec := &ast.ValueSpec{
				Type: texpr,
			}
			for _, idx := range idxs {
				spec.Names = append(spec.Names, ast.NewIdent(defs[idx].Name))
			}
			specs = append(specs, spec)
		})
		if failed {
			return nil, false
		}
		logf("substrategy: spread assignment")
		return []ast.Stmt{
			&ast.DeclStmt{
				Decl: &ast.GenDecl{
					Tok:   token.VAR,
					Specs: specs,
				},
			},
			&ast.AssignStmt{
				Lhs: callerStmt.Lhs,
				Tok: token.ASSIGN,
				Rhs: returnOperands,
			},
		}, true
	}

	assert(len(lhs) == len(rhs), "mismatching LHS and RHS")

	// Substrategy "convert": write out RHS expressions with explicit type conversions
	// as necessary, rewriting
	//
	//  x, y := f()
	//
	// to
	//
	//  x, y := 1, int32(2)
	//
	// As required to preserve types.
	//
	// In the special case of _ = nil, which is disallowed by the type checker
	// (since nil has no default type), we delete the assignment.
	var origIdxs []int // maps back to original indexes after lhs and rhs are pruned
	i := 0
	for j := range lhs {
		if _, ok := nilBlankAssigns[j]; !ok {
			lhs[i] = lhs[j]
			rhs[i] = rhs[j]
			origIdxs = append(origIdxs, j)
			i++
		}
	}
	lhs = lhs[:i]
	rhs = rhs[:i]

	if len(lhs) == 0 {
		logf("trivial assignment after pruning nil blanks assigns")
		// After pruning, we have no remaining assignments.
		// Signal this by returning a non-nil slice of statements.
		return nil, true
	}

	// Write out explicit conversions as necessary.
	//
	// A conversion is necessary if the LHS is being defined, and the RHS return
	// involved a nontrivial implicit conversion.
	for i, expr := range rhs {
		idx := origIdxs[i]
		if nonTrivial[idx] && defs[idx] != nil {
			typ := caller.Info.TypeOf(lhs[i])
			texpr := typeExpr(typ, nil)
			if texpr == nil {
				return nil, false
			}
			if _, ok := texpr.(*ast.StarExpr); ok {
				// TODO(rfindley): is this necessary? Doesn't the formatter add these parens?
				texpr = &ast.ParenExpr{X: texpr} // *T -> (*T)   so that (*T)(x) is valid
			}
			rhs[i] = &ast.CallExpr{
				Fun:  texpr,
				Args: []ast.Expr{expr},
			}
		}
	}
	logf("substrategy: convert assignment")
	return []ast.Stmt{&ast.AssignStmt{
		Lhs: lhs,
		Tok: callerStmt.Tok,
		Rhs: rhs,
	}}, true
}

// tailCallSafeReturn reports whether the callee's return statements may be safely
// used to return from the function enclosing the caller (which must exist).
func tailCallSafeReturn(caller *Caller, calleeSymbol *types.Func, callee *gobCallee) bool {
	// It is safe if all callee returns involve only trivial conversions.
	if !hasNonTrivialReturn(callee.Returns) {
		return true
	}

	var callerType types.Type
	// Find type of innermost function enclosing call.
	// (Beware: Caller.enclosingFunc is the outermost.)
loop:
	for _, n := range caller.path {
		switch f := n.(type) {
		case *ast.FuncDecl:
			callerType = caller.Info.ObjectOf(f.Name).Type()
			break loop
		case *ast.FuncLit:
			callerType = caller.Info.TypeOf(f)
			break loop
		}
	}

	// Non-trivial return conversions in the callee are permitted
	// if the same non-trivial conversion would occur after inlining,
	// i.e. if the caller and callee results tuples are identical.
	callerResults := callerType.(*types.Signature).Results()
	calleeResults := calleeSymbol.Type().(*types.Signature).Results()
	return types.Identical(callerResults, calleeResults)
}

// hasNonTrivialReturn reports whether any of the returns involve a nontrivial
// implicit conversion of a result expression.
func hasNonTrivialReturn(returnInfo [][]returnOperandFlags) bool {
	for _, resultInfo := range returnInfo {
		for _, r := range resultInfo {
			if r&nonTrivialResult != 0 {
				return true
			}
		}
	}
	return false
}

// soleUse returns the ident that refers to obj, if there is exactly one.
func soleUse(info *types.Info, obj types.Object) (sole *ast.Ident) {
	// This is not efficient, but it is called infrequently.
	for id, obj2 := range info.Uses {
		if obj2 == obj {
			if sole != nil {
				return nil // not unique
			}
			sole = id
		}
	}
	return sole
}

type unit struct{} // for representing sets as maps