internal/refactor/inline/inline.go

// 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/token"
	"go/types"
	pathpkg "path"
	"reflect"
	"strconv"
	"strings"

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

// 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
}

// 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.
//
// The log records the decision-making process.
//
// 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.
func Inline(logf func(string, ...any), caller *Caller, callee *Callee) ([]byte, error) {
	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?)")
	}

	// TODO(adonovan): use go1.21's ast.IsGenerated.
	// Break the string literal so we can use inlining in this file. :)
	if 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 := inline(logf, caller, &callee.impl)
	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").
	elideBraces := false
	if newBlock, ok := res.new.(*ast.BlockStmt); ok {
		i := nodeIndex(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
			}
		}
	}

	// 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.
	var f *ast.File
	{
		start := offsetOf(caller.Fset, res.old.Pos())
		end := offsetOf(caller.Fset, res.old.End())
		var out bytes.Buffer
		out.Write(caller.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 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, caller.Fset, stmt); err != nil {
					return nil, err
				}
			}
		} else {
			if err := format.Node(&out, caller.Fset, res.new); err != nil {
				return nil, err
			}
		}
		out.Write(caller.Content[end:])
		const mode = parser.ParseComments | parser.SkipObjectResolution | parser.AllErrors
		f, err = parser.ParseFile(caller.Fset, "callee.go", &out, mode)
		if err != nil {
			// Something has gone very wrong.
			logf("failed to parse <<%s>>", &out) // debugging
			return nil, err
		}
	}

	// Add new imports.
	//
	// Insert new imports after last existing import,
	// to avoid migration of pre-import comments.
	// The imports will be organized below.
	if len(res.newImports) > 0 {
		var importDecl *ast.GenDecl
		if len(f.Imports) > 0 {
			// Append specs to existing import decl
			importDecl = f.Decls[0].(*ast.GenDecl)
		} else {
			// Insert new import decl.
			importDecl = &ast.GenDecl{Tok: token.IMPORT}
			f.Decls = prepend[ast.Decl](importDecl, f.Decls...)
		}
		for _, imp := range res.newImports {
			// Check that the new imports are accessible.
			path, _ := strconv.Unquote(imp.spec.Path.Value)
			if !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
	if err := format.Node(&out, caller.Fset, f); err != nil {
		return nil, err
	}
	newSrc := out.Bytes()

	// Remove imports that are no longer referenced.
	//
	// It ought to be possible to compute the set of PkgNames used
	// by the "old" code, compute the free identifiers of the
	// "new" code using a syntax-only (no go/types) algorithm, and
	// see if the reduction in the number of uses of any PkgName
	// equals the number of times it appears in caller.Info.Uses,
	// indicating that it is no longer referenced by res.new.
	//
	// However, the notorious ambiguity of resolving T{F: 0} makes this
	// unreliable: without types, we can't tell whether F refers to
	// a field of struct T, or a package-level const/var of a
	// dot-imported (!) package.
	//
	// So, for now, we run imports.Process, which is
	// unsatisfactory as it has to run the go command, and it
	// looks at the user's module cache state--unnecessarily,
	// since this step cannot add new imports.
	//
	// TODO(adonovan): replace with a simpler implementation since
	// all the necessary imports are present but merely untidy.
	// That will be faster, and also less prone to nondeterminism
	// if there are bugs in our logic for import maintenance.
	//
	// However, golang.org/x/tools/internal/imports.ApplyFixes is
	// too simple as it requires the caller to have figured out
	// all the logical edits. In our case, we know all the new
	// imports that are needed (see newImports), each of which can
	// be specified as:
	//
	//   &imports.ImportFix{
	//     StmtInfo: imports.ImportInfo{path, name,
	//     IdentName: name,
	//     FixType:   imports.AddImport,
	//   }
	//
	// but we don't know which imports are made redundant by the
	// inlining itself. For example, inlining a call to
	// fmt.Println may make the "fmt" import redundant.
	//
	// Also, both imports.Process and internal/imports.ApplyFixes
	// reformat the entire file, which is not ideal for clients
	// such as gopls. (That said, the point of a canonical format
	// is arguably that any tool can reformat as needed without
	// this being inconvenient.)
	//
	// We could invoke imports.Process and parse its result,
	// compare against the original AST, compute a list of import
	// fixes, and return that too.

	// Recompute imports only if there were existing ones.
	if len(f.Imports) > 0 {
		formatted, err := imports.Process("output", newSrc, nil)
		if err != nil {
			logf("cannot reformat: %v <<%s>>", err, &out)
			return nil, err // cannot reformat (a bug?)
		}
		newSrc = formatted
	}
	return newSrc, nil
}

type newImport struct {
	pkgName string
	spec    *ast.ImportSpec
}

type result struct {
	newImports []newImport
	old, new   ast.Node // e.g. replace call expr by callee function body expression
}

// inline 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.)
//
// 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.)
func inline(logf func(string, ...any), caller *Caller, callee *gobCallee) (*result, error) {
	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] }
	}

	// import map, initially populated with caller imports.
	//
	// 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.
	importMap := make(map[string][]string) // maps package path to local name(s)
	for _, imp := range caller.File.Imports {
		if pkgname, ok := importedPkgName(caller.Info, imp); ok &&
			pkgname.Name() != "." &&
			pkgname.Name() != "_" {
			path := pkgname.Imported().Path()
			importMap[path] = append(importMap[path], pkgname.Name())
		}
	}

	// localImportName returns the local name for a given imported package path.
	var newImports []newImport
	localImportName := func(obj *object) string {
		// Does an import exist?
		for _, name := range importMap[obj.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 !obj.Shadow[name] {
				found := caller.lookup(name)
				if is[*types.PkgName](found) || found == nil {
					return name
				}
			}
		}

		newlyAdded := func(name string) bool {
			for _, new := range newImports {
				if new.pkgName == name {
					return true
				}
			}
			return false
		}

		// 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 := obj.PkgName
		name := base
		for n := 0; obj.Shadow[name] || caller.lookup(name) != nil || newlyAdded(name) || name == "init"; n++ {
			name = fmt.Sprintf("%s%d", base, n)
		}

		logf("adding import %s %q", name, obj.PkgPath)
		spec := &ast.ImportSpec{
			Path: &ast.BasicLit{
				Kind:  token.STRING,
				Value: strconv.Quote(obj.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 != obj.PkgName || name != pathpkg.Base(obj.PkgPath) {
			spec.Name = makeIdent(name)
		}
		newImports = append(newImports, newImport{
			pkgName: name,
			spec:    spec,
		})
		importMap[obj.PkgPath] = append(importMap[obj.PkgPath], name)
		return name
	}

	// Compute the renaming of the callee's free identifiers.
	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.
			newName = makeIdent(localImportName(&obj)) // 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 samePkg {
					// 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 := localImportName(&obj)
				newName = &ast.SelectorExpr{
					X:   makeIdent(pkgName),
					Sel: makeIdent(obj.Name),
				}
			}
		}
		objRenames[i] = newName
	}

	res := &result{
		newImports: newImports,
	}

	// 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.
	// The replacement tree must not belong to the caller; use cloneNode as needed.
	replaceCalleeID := func(offset int, repl ast.Expr) {
		id := findIdent(calleeDecl, calleeDecl.Pos()+token.Pos(offset))
		logf("- replace id %q @ #%d to %q", id.Name, offset, debugFormatNode(calleeFset, repl))
		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)
		}
	}

	// Gather the effective call arguments, including the receiver.
	// Later, elements will be eliminated (=> nil) by parameter substitution.
	args, err := 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})
					n := len(params) - 1
					ordinary, extra := args[:n], args[n:]
					var elts []ast.Expr
					pure, effects := true, false
					for _, arg := range extra {
						elts = append(elts, arg.expr)
						pure = pure && arg.pure
						effects = effects || arg.effects
					}
					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:   nil, // not needed
					})
				}
			}
		}
	}

	// 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.
	bindingDeclStmt := 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.
		stmt := callStmt(caller.path, false) // cannot fail
		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

		context := callContext(caller.path)

		// statement context
		if stmt, ok := context.(*ast.ExprStmt); ok &&
			(!needBindingDecl || bindingDeclStmt != 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{
							bindingDeclStmt,
							&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{
							bindingDeclStmt,
							discard,
						},
					}
				}
			}
			return res, nil
		}

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

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

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

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

			} else if callee.TrivialReturns == callee.TotalReturns {
				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 = context
				switch context := context.(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.
	if ret, ok := callContext(caller.path).(*ast.ReturnStmt); ok &&
		len(ret.Results) == 1 &&
		tailCallSafeReturn(caller, calleeSymbol, callee) &&
		!callee.HasBareReturn &&
		(!needBindingDecl || bindingDeclStmt != nil) &&
		!hasLabelConflict(caller.path, callee.Labels) &&
		allResultsUnreferenced {
		logf("strategy: reduce tail-call")
		body := calleeDecl.Body
		clearPositions(body)
		if needBindingDecl {
			body.List = prepend(bindingDeclStmt, 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 || bindingDeclStmt != nil) &&
		!callee.HasDefer &&
		!hasLabelConflict(caller.path, callee.Labels) &&
		callee.TotalReturns == 0 {
		logf("strategy: reduce stmt-context call to { stmts }")
		body := calleeDecl.Body
		var repl ast.Stmt = body
		clearPositions(repl)
		if needBindingDecl {
			body.List = prepend(bindingDeclStmt, 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,
	}

	// 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 bindingDeclStmt != nil && allResultsUnreferenced {
		funcLit.Type.Params.List = nil
		remainingArgs = nil
		funcLit.Body.List = prepend(bindingDeclStmt, 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,
	}
	clearPositions(newCall.Fun)
	res.old = caller.Call
	res.new = newCall
	return res, 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
	substitutable bool            // is candidate for substitution
}

// 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 arguments(caller *Caller, calleeDecl *ast.FuncDecl, assign1 func(*types.Var) bool) ([]*argument, error) {
	var args []*argument

	callArgs := caller.Call.Args
	if calleeDecl.Recv != nil {
		sel := astutil.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:    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] {
				t := deref(arg.typ)
				fld := typeparams.CoreType(t).(*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)
			} else if argIsPtr && !paramIsPtr {
				// *recv
				arg.expr = &ast.StarExpr{X: arg.expr}
				arg.typ = deref(arg.typ)
				arg.duplicable = false
				arg.pure = false
			}
		}
	}
	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:    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
}

// 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 func(string, ...any), caller *Caller, params []*parameter, args []*argument, effects []int, falcon falconResult, replaceCalleeID func(offset int, repl ast.Expr)) {
	// 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.
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) {
						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
					}
				}
			}
		}

		// Check for 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.
		for free := range arg.freevars {
			if param.info.Shadow[free] {
				logf("keeping param %q: cannot replace with argument as it has free ref to %s that is shadowed", param.info.Name, free)
				continue next // shadowing conflict
			}
		}

		arg.substitutable = true // may be substituted, if effects permit
	}

	// Reject constant arguments as substitution candidates
	// if they cause violation of falcon constraints.
	checkFalconConstraints(logf, params, args, falcon)

	// 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.
	resolveEffects(logf, args, effects)

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

			// 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.)
			//
			// 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 len(param.info.Refs) > 0 && !trivialConversion(args[i].typ, params[i].obj) {
				arg.expr = convert(params[i].fieldType, arg.expr)
				logf("param %q: adding explicit %s -> %s conversion around argument",
					param.info.Name, args[i].typ, params[i].obj.Type())
			}

			// 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 {
				replaceCalleeID(ref, internalastutil.CloneNode(arg.expr).(ast.Expr))
			}
			params[i] = nil // substituted
			args[i] = nil   // substituted
		}
	}
}

// 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 func(string, ...any), params []*parameter, args []*argument, falcon falconResult) {
	// 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 && arg.substitutable && 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 {
			pkg.Scope().Insert(types.NewVar(token.NoPos, pkg, name, arg.typ))
			logf("falcon env: var %s %s", name, arg.typ)
		}
	}
	if nconst == 0 {
		return // nothing to do
	}

	// Parse and evaluate the constraints in the environment.
	fset := token.NewFileSet()
	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 && arg.substitutable {
					logf("keeping param %q due falcon violation", params[j].info.Name)
					arg.substitutable = false
				}
			}
			break
		}
		logf("falcon: constraint %s satisfied", falcon)
	}
}

// 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 func(string, ...any), args []*argument, effects []int) {
	effectStr := func(effects bool, idx int) string {
		i := fmt.Sprint(idx)
		if idx == len(args) {
			i = "∞"
		}
		return string("RW"[btoi(effects)]) + i
	}
	for i := len(args) - 1; i >= 0; i-- {
		argi := args[i]
		if argi.substitutable && !argi.pure {
			// i is not bound: check whether it must be bound due to hazards.
			idx := 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))
						argi.substitutable = false
						break
					}
				}
			}
		}
		if !argi.substitutable {
			for j := 0; j < i; j++ {
				argj := args[j]
				if argj.pure {
					continue
				}
				if (argi.effects || argj.effects) && argj.substitutable {
					logf("binding argument %s: %s is bound",
						effectStr(argj.effects, j), effectStr(argi.effects, i))
					argj.substitutable = false
				}
			}
		}
	}
}

// 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
}

// 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 func(string, ...any), caller *Caller, args []*argument, calleeDecl *ast.FuncDecl, results []*paramInfo) ast.Stmt {
	// 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
		shadowed = 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
			}
		}
		freeishNames(free, spec.Type)
		for name := range free {
			if shadowed[name] {
				logf("binding decl would shadow free name %q", name)
				return true
			}
		}
		for _, id := range spec.Names {
			if id.Name != "_" {
				shadowed[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:  field.Names,
			Type:   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: names,
					Type:  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 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
}

// freeishNames computes an over-approximation to the free names
// of the type syntax t, inserting values into the map.
//
// Because we don't have go/types annotations, we can't give an exact
// result in all cases. In particular, an array type [n]T might have a
// size such as unsafe.Sizeof(func() int{stmts...}()) and now the
// precise answer depends upon all the statement syntax too. But that
// never happens in practice.
func freeishNames(free map[string]bool, t ast.Expr) {
	var visit func(n ast.Node) bool
	visit = func(n ast.Node) bool {
		switch n := n.(type) {
		case *ast.Ident:
			free[n.Name] = true

		case *ast.SelectorExpr:
			ast.Inspect(n.X, visit)
			return false // don't visit .Sel

		case *ast.Field:
			ast.Inspect(n.Type, visit)
			// Don't visit .Names:
			// FuncType parameters, interface methods, struct fields
			return false
		}
		return true
	}
	ast.Inspect(t, visit)
}

// 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 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
	})
	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 := astutil.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:
		// Don't treat a conversion T(x) as duplicable even
		// if x is duplicable because it could duplicate
		// allocations.
		//
		// TODO(adonovan): there are cases to tease apart here:
		// duplicating string([]byte) conversions increases
		// allocation but doesn't change behavior, but the
		// reverse, []byte(string), allocates a distinct array,
		// which is observable
		return false

	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 node immediately enclosing the call
// (specified as a PathEnclosingInterval), ignoring parens.
func callContext(callPath []ast.Node) ast.Node {
	_ = callPath[0].(*ast.CallExpr) // sanity check
	for _, n := range callPath[1:] {
		if !is[*ast.ParenExpr](n) {
			return n
		}
	}
	return 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 {
	stmt, ok := callContext(callPath).(*ast.ExprStmt)
	if ok && unrestricted {
		switch callPath[nodeIndex(callPath, 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.Ptr:
			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 := 0; i < v.Type().NumField(); i++ {
				visit(v.Field(i))
			}

		case reflect.Slice:
			compact := false
			for i := 0; i < v.Len(); i++ {
				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 := 0; i < v.Len(); i++ {
					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))
	}
}

// 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 := 0; i < fields; i++ {
				f := v.Field(i)
				if f.Type() == posType {
					// 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).
					if f.Interface() != token.NoPos {
						f.Set(reflect.ValueOf(token.Pos(1)))
					}
				}
			}
		}
		return true
	})
}

// findIdent returns the Ident beneath root that has the given pos.
func findIdent(root ast.Node, pos token.Pos) *ast.Ident {
	// TODO(adonovan): opt: skip subtrees that don't contain pos.
	var found *ast.Ident
	ast.Inspect(root, func(n ast.Node) bool {
		if found != nil {
			return false
		}
		if id, ok := n.(*ast.Ident); ok {
			if id.Pos() == pos {
				found = id
			}
		}
		return true
	})
	if found == nil {
		panic(fmt.Sprintf("findIdent %d not found in %s",
			pos, debugFormatNode(token.NewFileSet(), root)))
	}
	return 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)
}

// canImport reports whether one package is allowed to import another.
//
// TODO(adonovan): allow customization of the accessibility relation
// (e.g. for Bazel).
func canImport(from, to string) bool {
	// TODO(adonovan): better segment hygiene.
	if strings.HasPrefix(to, "internal/") {
		// Special case: only std packages may import internal/...
		// We can't reliably know whether we're in std, so we
		// use a heuristic on the first segment.
		first, _, _ := strings.Cut(from, "/")
		if strings.Contains(first, ".") {
			return false // example.com/foo ∉ std
		}
		if first == "testdata" {
			return false // testdata/foo ∉ std
		}
	}
	if i := strings.LastIndex(to, "/internal/"); i >= 0 {
		return strings.HasPrefix(from, to[:i])
	}
	return true
}

// 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 := nodeIndex(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
}

func nodeIndex(nodes []ast.Node, n ast.Node) int {
	// TODO(adonovan): Use index[ast.Node]() in go1.20.
	for i, node := range nodes {
		if node == n {
			return i
		}
	}
	return -1
}

// 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
}

// 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 callee.TrivialReturns == callee.TotalReturns {
		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)
}