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

// This file defines the analysis of the callee function.

import (
	"bytes"
	"encoding/gob"
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
	"go/types"
	"strings"

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

// A Callee holds information about an inlinable function. Gob-serializable.
type Callee struct {
	impl gobCallee
}

func (callee *Callee) String() string { return callee.impl.Name }

type gobCallee struct {
	Content []byte // file content, compacted to a single func decl

	// results of type analysis (does not reach go/types data structures)
	PkgPath          string                 // package path of declaring package
	Name             string                 // user-friendly name for error messages
	Unexported       []string               // names of free objects that are unexported
	FreeRefs         []freeRef              // locations of references to free objects
	FreeObjs         []object               // descriptions of free objects
	ValidForCallStmt bool                   // function body is "return expr" where expr is f() or <-ch
	NumResults       int                    // number of results (according to type, not ast.FieldList)
	Params           []*paramInfo           // information about parameters (incl. receiver)
	Results          []*paramInfo           // information about result variables
	Effects          []int                  // order in which parameters are evaluated (see calleefx)
	HasDefer         bool                   // uses defer
	HasBareReturn    bool                   // uses bare return in non-void function
	Returns          [][]returnOperandFlags // metadata about result expressions for each return
	Labels           []string               // names of all control labels
	Falcon           falconResult           // falcon constraint system
}

// returnOperandFlags records metadata about a single result expression in a return
// statement.
type returnOperandFlags int

const (
	nonTrivialResult returnOperandFlags = 1 << iota // return operand has non-trivial conversion to result type
	untypedNilResult                                // return operand is nil literal
)

// A freeRef records a reference to a free object. Gob-serializable.
// (This means free relative to the FuncDecl as a whole, i.e. excluding parameters.)
type freeRef struct {
	Offset int // byte offset of the reference relative to the FuncDecl
	Object int // index into Callee.freeObjs
}

// An object abstracts a free types.Object referenced by the callee. Gob-serializable.
type object struct {
	Name    string // Object.Name()
	Kind    string // one of {var,func,const,type,pkgname,nil,builtin}
	PkgPath string // path of object's package (or imported package if kind="pkgname")
	PkgName string // name of object's package (or imported package if kind="pkgname")
	// TODO(rfindley): should we also track LocalPkgName here? Do we want to
	// preserve the local package name?
	ValidPos bool            // Object.Pos().IsValid()
	Shadow   map[string]bool // names shadowed at one of the object's refs
}

// AnalyzeCallee analyzes a function that is a candidate for inlining
// and returns a Callee that describes it. The Callee object, which is
// serializable, can be passed to one or more subsequent calls to
// Inline, each with a different Caller.
//
// This design allows separate analysis of callers and callees in the
// golang.org/x/tools/go/analysis framework: the inlining information
// about a callee can be recorded as a "fact".
//
// The content should be the actual input to the compiler, not the
// apparent source file according to any //line directives that
// may be present within it.
func AnalyzeCallee(logf func(string, ...any), fset *token.FileSet, pkg *types.Package, info *types.Info, decl *ast.FuncDecl, content []byte) (*Callee, error) {
	checkInfoFields(info)

	// The client is expected to have determined that the callee
	// is a function with a declaration (not a built-in or var).
	fn := info.Defs[decl.Name].(*types.Func)
	sig := fn.Type().(*types.Signature)

	logf("analyzeCallee %v @ %v", fn, fset.PositionFor(decl.Pos(), false))

	// Create user-friendly name ("pkg.Func" or "(pkg.T).Method")
	var name string
	if sig.Recv() == nil {
		name = fmt.Sprintf("%s.%s", fn.Pkg().Name(), fn.Name())
	} else {
		name = fmt.Sprintf("(%s).%s", types.TypeString(sig.Recv().Type(), (*types.Package).Name), fn.Name())
	}

	if decl.Body == nil {
		return nil, fmt.Errorf("cannot inline function %s as it has no body", name)
	}

	// TODO(adonovan): support inlining of instantiated generic
	// functions by replacing each occurrence of a type parameter
	// T by its instantiating type argument (e.g. int). We'll need
	// to 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 funcHasTypeParams(decl) {
		return nil, fmt.Errorf("cannot inline generic function %s: type parameters are not yet supported", name)
	}

	// Record the location of all free references in the FuncDecl.
	// (Parameters are not free by this definition.)
	var (
		freeObjIndex = make(map[types.Object]int)
		freeObjs     []object
		freeRefs     []freeRef // free refs that may need renaming
		unexported   []string  // free refs to unexported objects, for later error checks
	)
	var f func(n ast.Node) bool
	visit := func(n ast.Node) { ast.Inspect(n, f) }
	var stack []ast.Node
	stack = append(stack, decl.Type) // for scope of function itself
	f = func(n ast.Node) bool {
		if n != nil {
			stack = append(stack, n) // push
		} else {
			stack = stack[:len(stack)-1] // pop
		}
		switch n := n.(type) {
		case *ast.SelectorExpr:
			// Check selections of free fields/methods.
			if sel, ok := info.Selections[n]; ok &&
				!within(sel.Obj().Pos(), decl) &&
				!n.Sel.IsExported() {
				sym := fmt.Sprintf("(%s).%s", info.TypeOf(n.X), n.Sel.Name)
				unexported = append(unexported, sym)
			}

			// Don't recur into SelectorExpr.Sel.
			visit(n.X)
			return false

		case *ast.CompositeLit:
			// Check for struct literals that refer to unexported fields,
			// whether keyed or unkeyed. (Logic assumes well-typedness.)
			litType := typeparams.Deref(info.TypeOf(n))
			if s, ok := typeparams.CoreType(litType).(*types.Struct); ok {
				if n.Type != nil {
					visit(n.Type)
				}
				for i, elt := range n.Elts {
					var field *types.Var
					var value ast.Expr
					if kv, ok := elt.(*ast.KeyValueExpr); ok {
						field = info.Uses[kv.Key.(*ast.Ident)].(*types.Var)
						value = kv.Value
					} else {
						field = s.Field(i)
						value = elt
					}
					if !within(field.Pos(), decl) && !field.Exported() {
						sym := fmt.Sprintf("(%s).%s", litType, field.Name())
						unexported = append(unexported, sym)
					}

					// Don't recur into KeyValueExpr.Key.
					visit(value)
				}
				return false
			}

		case *ast.Ident:
			if obj, ok := info.Uses[n]; ok {
				// Methods and fields are handled by SelectorExpr and CompositeLit.
				if isField(obj) || isMethod(obj) {
					panic(obj)
				}
				// Inv: id is a lexical reference.

				// A reference to an unexported package-level declaration
				// cannot be inlined into another package.
				if !n.IsExported() &&
					obj.Pkg() != nil && obj.Parent() == obj.Pkg().Scope() {
					unexported = append(unexported, n.Name)
				}

				// Record free reference (incl. self-reference).
				if obj == fn || !within(obj.Pos(), decl) {
					objidx, ok := freeObjIndex[obj]
					if !ok {
						objidx = len(freeObjIndex)
						var pkgpath, pkgname string
						if pn, ok := obj.(*types.PkgName); ok {
							pkgpath = pn.Imported().Path()
							pkgname = pn.Imported().Name()
						} else if obj.Pkg() != nil {
							pkgpath = obj.Pkg().Path()
							pkgname = obj.Pkg().Name()
						}
						freeObjs = append(freeObjs, object{
							Name:     obj.Name(),
							Kind:     objectKind(obj),
							PkgName:  pkgname,
							PkgPath:  pkgpath,
							ValidPos: obj.Pos().IsValid(),
						})
						freeObjIndex[obj] = objidx
					}

					freeObjs[objidx].Shadow = addShadows(freeObjs[objidx].Shadow, info, obj.Name(), stack)

					freeRefs = append(freeRefs, freeRef{
						Offset: int(n.Pos() - decl.Pos()),
						Object: objidx,
					})
				}
			}
		}
		return true
	}
	visit(decl)

	// Analyze callee body for "return expr" form,
	// where expr is f() or <-ch. These forms are
	// safe to inline as a standalone statement.
	validForCallStmt := false
	if len(decl.Body.List) != 1 {
		// not just a return statement
	} else if ret, ok := decl.Body.List[0].(*ast.ReturnStmt); ok && len(ret.Results) == 1 {
		validForCallStmt = func() bool {
			switch expr := astutil.Unparen(ret.Results[0]).(type) {
			case *ast.CallExpr: // f(x)
				callee := typeutil.Callee(info, expr)
				if callee == nil {
					return false // conversion T(x)
				}

				// The only non-void built-in functions that may be
				// called as a statement are copy and recover
				// (though arguably a call to recover should never
				// be inlined as that changes its behavior).
				if builtin, ok := callee.(*types.Builtin); ok {
					return builtin.Name() == "copy" ||
						builtin.Name() == "recover"
				}

				return true // ordinary call f()

			case *ast.UnaryExpr: // <-x
				return expr.Op == token.ARROW // channel receive <-ch
			}

			// No other expressions are valid statements.
			return false
		}()
	}

	// Record information about control flow in the callee
	// (but not any nested functions).
	var (
		hasDefer      = false
		hasBareReturn = false
		returnInfo    [][]returnOperandFlags
		labels        []string
	)
	ast.Inspect(decl.Body, func(n ast.Node) bool {
		switch n := n.(type) {
		case *ast.FuncLit:
			return false // prune traversal
		case *ast.DeferStmt:
			hasDefer = true
		case *ast.LabeledStmt:
			labels = append(labels, n.Label.Name)
		case *ast.ReturnStmt:

			// Are implicit assignment conversions
			// to result variables all trivial?
			var resultInfo []returnOperandFlags
			if len(n.Results) > 0 {
				argInfo := func(i int) (ast.Expr, types.Type) {
					expr := n.Results[i]
					return expr, info.TypeOf(expr)
				}
				if len(n.Results) == 1 && sig.Results().Len() > 1 {
					// Spread return: return f() where f.Results > 1.
					tuple := info.TypeOf(n.Results[0]).(*types.Tuple)
					argInfo = func(i int) (ast.Expr, types.Type) {
						return nil, tuple.At(i).Type()
					}
				}
				for i := 0; i < sig.Results().Len(); i++ {
					expr, typ := argInfo(i)
					var flags returnOperandFlags
					if typ == types.Typ[types.UntypedNil] { // untyped nil is preserved by go/types
						flags |= untypedNilResult
					}
					if !trivialConversion(info.Types[expr].Value, typ, sig.Results().At(i).Type()) {
						flags |= nonTrivialResult
					}
					resultInfo = append(resultInfo, flags)
				}
			} else if sig.Results().Len() > 0 {
				hasBareReturn = true
			}
			returnInfo = append(returnInfo, resultInfo)
		}
		return true
	})

	// Reject attempts to inline cgo-generated functions.
	for _, obj := range freeObjs {
		// There are others (iconst fconst sconst fpvar macro)
		// but this is probably sufficient.
		if strings.HasPrefix(obj.Name, "_Cfunc_") ||
			strings.HasPrefix(obj.Name, "_Ctype_") ||
			strings.HasPrefix(obj.Name, "_Cvar_") {
			return nil, fmt.Errorf("cannot inline cgo-generated functions")
		}
	}

	// Compact content to just the FuncDecl.
	//
	// As a space optimization, we don't retain the complete
	// callee file content; all we need is "package _; func f() { ... }".
	// This reduces the size of analysis facts.
	//
	// Offsets in the callee information are "relocatable"
	// since they are all relative to the FuncDecl.

	content = append([]byte("package _\n"),
		content[offsetOf(fset, decl.Pos()):offsetOf(fset, decl.End())]...)
	// Sanity check: re-parse the compacted content.
	if _, _, err := parseCompact(content); err != nil {
		return nil, err
	}

	params, results, effects, falcon := analyzeParams(logf, fset, info, decl)
	return &Callee{gobCallee{
		Content:          content,
		PkgPath:          pkg.Path(),
		Name:             name,
		Unexported:       unexported,
		FreeObjs:         freeObjs,
		FreeRefs:         freeRefs,
		ValidForCallStmt: validForCallStmt,
		NumResults:       sig.Results().Len(),
		Params:           params,
		Results:          results,
		Effects:          effects,
		HasDefer:         hasDefer,
		HasBareReturn:    hasBareReturn,
		Returns:          returnInfo,
		Labels:           labels,
		Falcon:           falcon,
	}}, nil
}

// parseCompact parses a Go source file of the form "package _\n func f() { ... }"
// and returns the sole function declaration.
func parseCompact(content []byte) (*token.FileSet, *ast.FuncDecl, error) {
	fset := token.NewFileSet()
	const mode = parser.ParseComments | parser.SkipObjectResolution | parser.AllErrors
	f, err := parser.ParseFile(fset, "callee.go", content, mode)
	if err != nil {
		return nil, nil, fmt.Errorf("internal error: cannot compact file: %v", err)
	}
	return fset, f.Decls[0].(*ast.FuncDecl), nil
}

// A paramInfo records information about a callee receiver, parameter, or result variable.
type paramInfo struct {
	Name       string          // parameter name (may be blank, or even "")
	Index      int             // index within signature
	IsResult   bool            // false for receiver or parameter, true for result variable
	Assigned   bool            // parameter appears on left side of an assignment statement
	Escapes    bool            // parameter has its address taken
	Refs       []int           // FuncDecl-relative byte offset of parameter ref within body
	Shadow     map[string]bool // names shadowed at one of the above refs
	FalconType string          // name of this parameter's type (if basic) in the falcon system
}

// analyzeParams computes information about parameters of function fn,
// including a simple "address taken" escape analysis.
//
// It returns two new arrays, one of the receiver and parameters, and
// the other of the result variables of function fn.
//
// The input must be well-typed.
func analyzeParams(logf func(string, ...any), fset *token.FileSet, info *types.Info, decl *ast.FuncDecl) (params, results []*paramInfo, effects []int, _ falconResult) {
	fnobj, ok := info.Defs[decl.Name]
	if !ok {
		panic(fmt.Sprintf("%s: no func object for %q",
			fset.PositionFor(decl.Name.Pos(), false), decl.Name)) // ill-typed?
	}

	paramInfos := make(map[*types.Var]*paramInfo)
	{
		sig := fnobj.Type().(*types.Signature)
		newParamInfo := func(param *types.Var, isResult bool) *paramInfo {
			info := &paramInfo{
				Name:     param.Name(),
				IsResult: isResult,
				Index:    len(paramInfos),
			}
			paramInfos[param] = info
			return info
		}
		if sig.Recv() != nil {
			params = append(params, newParamInfo(sig.Recv(), false))
		}
		for i := 0; i < sig.Params().Len(); i++ {
			params = append(params, newParamInfo(sig.Params().At(i), false))
		}
		for i := 0; i < sig.Results().Len(); i++ {
			results = append(results, newParamInfo(sig.Results().At(i), true))
		}
	}

	// Search function body for operations &x, x.f(), and x = y
	// where x is a parameter, and record it.
	escape(info, decl, func(v *types.Var, escapes bool) {
		if info := paramInfos[v]; info != nil {
			if escapes {
				info.Escapes = true
			} else {
				info.Assigned = true
			}
		}
	})

	// Record locations of all references to parameters.
	// And record the set of intervening definitions for each parameter.
	//
	// TODO(adonovan): combine this traversal with the one that computes
	// FreeRefs. The tricky part is that calleefx needs this one first.
	var stack []ast.Node
	stack = append(stack, decl.Type) // for scope of function itself
	ast.Inspect(decl.Body, func(n ast.Node) bool {
		if n != nil {
			stack = append(stack, n) // push
		} else {
			stack = stack[:len(stack)-1] // pop
		}

		if id, ok := n.(*ast.Ident); ok {
			if v, ok := info.Uses[id].(*types.Var); ok {
				if pinfo, ok := paramInfos[v]; ok {
					// Record location of ref to parameter/result
					// and any intervening (shadowing) names.
					offset := int(n.Pos() - decl.Pos())
					pinfo.Refs = append(pinfo.Refs, offset)
					pinfo.Shadow = addShadows(pinfo.Shadow, info, pinfo.Name, stack)
				}
			}
		}
		return true
	})

	// Compute subset and order of parameters that are strictly evaluated.
	// (Depends on Refs computed above.)
	effects = calleefx(info, decl.Body, paramInfos)
	logf("effects list = %v", effects)

	falcon := falcon(logf, fset, paramInfos, info, decl)

	return params, results, effects, falcon
}

// -- callee helpers --

// addShadows returns the shadows set augmented by the set of names
// locally shadowed at the location of the reference in the callee
// (identified by the stack). The name of the reference itself is
// excluded.
//
// These shadowed names may not be used in a replacement expression
// for the reference.
func addShadows(shadows map[string]bool, info *types.Info, exclude string, stack []ast.Node) map[string]bool {
	for _, n := range stack {
		if scope := scopeFor(info, n); scope != nil {
			for _, name := range scope.Names() {
				if name != exclude {
					if shadows == nil {
						shadows = make(map[string]bool)
					}
					shadows[name] = true
				}
			}
		}
	}
	return shadows
}

func isField(obj types.Object) bool {
	if v, ok := obj.(*types.Var); ok && v.IsField() {
		return true
	}
	return false
}

func isMethod(obj types.Object) bool {
	if f, ok := obj.(*types.Func); ok && f.Type().(*types.Signature).Recv() != nil {
		return true
	}
	return false
}

// -- serialization --

var (
	_ gob.GobEncoder = (*Callee)(nil)
	_ gob.GobDecoder = (*Callee)(nil)
)

func (callee *Callee) GobEncode() ([]byte, error) {
	var out bytes.Buffer
	if err := gob.NewEncoder(&out).Encode(callee.impl); err != nil {
		return nil, err
	}
	return out.Bytes(), nil
}

func (callee *Callee) GobDecode(data []byte) error {
	return gob.NewDecoder(bytes.NewReader(data)).Decode(&callee.impl)
}