falcon.go | Explore in Territory

type falconResult …

type falconType …

// falcon identifies "fallible constant" expressions, which are
// expressions that may fail to compile if one or more of their
// operands is changed from non-constant to constant.
//
// Consider:
//
//	func sub(s string, i, j int) string { return s[i:j] }
//
// If parameters are replaced by constants, the compiler is
// required to perform these additional checks:
//
//   - if i is constant, 0 <= i.
//   - if s and i are constant, i <= len(s).
//   - ditto for j.
//   - if i and j are constant, i <= j.
//
// s[i:j] is thus a "fallible constant" expression dependent on {s, i,
// j}. Each falcon creates a set of conditional constraints across one
// or more parameter variables.
//
//   - When inlining a call such as sub("abc", -1, 2), the parameter i
//     cannot be eliminated by substitution as its argument value is
//     negative.
//
//   - When inlining sub("", 2, 1), all three parameters cannot be
//     simultaneously eliminated by substitution without violating i
//     <= len(s) and j <= len(s), but the parameters i and j could be
//     safely eliminated without s.
//
// Parameters that cannot be eliminated must remain non-constant,
// either in the form of a binding declaration:
//
//	{ var i int = -1; return "abc"[i:2] }
//
// or a parameter of a literalization:
//
//	func (i int) string { return "abc"[i:2] }(-1)
//
// These example expressions are obviously doomed to fail at run
// time, but in realistic cases such expressions are dominated by
// appropriate conditions that make them reachable only when safe:
//
//	if 0 <= i && i <= j && j <= len(s) { _ = s[i:j] }
//
// (In principle a more sophisticated inliner could entirely eliminate
// such unreachable blocks based on the condition being always-false
// for the given parameter substitution, but this is tricky to do safely
// because the type-checker considers only a single configuration.
// Consider: if runtime.GOOS == "linux" { ... }.)
//
// We believe this is an exhaustive list of "fallible constant" operations:
//
//   - switch z { case x: case y } 	// duplicate case values
//   - s[i], s[i:j], s[i:j:k]		// index out of bounds (0 <= i <= j <= k <= len(s))
//   - T{x: 0}				// index out of bounds, duplicate index
//   - x/y, x%y, x/=y, x%=y		// integer division by zero; minint/-1 overflow
//   - x+y, x-y, x*y			// arithmetic overflow
//   - x<<y				// shift out of range
//   - -x				// negation of minint
//   - T(x)				// value out of range
//
// The fundamental reason for this elaborate algorithm is that the
// "separate analysis" of callee and caller, as required when running
// in an environment such as unitchecker, means that there is no way
// for us to simply invoke the type checker on the combination of
// caller and callee code, as by the time we analyze the caller, we no
// longer have access to type information for the callee (and, in
// particular, any of its direct dependencies that are not direct
// dependencies of the caller). So, in effect, we are forced to map
// the problem in a neutral (callee-type-independent) constraint
// system that can be verified later.
func falcon(logf func(string, ...any), fset *token.FileSet, params map[*types.Var]*paramInfo, info *types.Info, decl *ast.FuncDecl) falconResult { … }

type falconState …

// typename returns the name in the falcon constraint system
// of a given string/number/bool type t. Falcon types are
// specified directly in go/types data structures rather than
// by name, avoiding potential shadowing conflicts with
// confusing parameter names such as "int".
//
// Also, each distinct type (as determined by types.Identical)
// is mapped to a fresh type in the falcon system so that we
// can map the types in the callee code into a neutral form
// that does not depend on imports, allowing us to detect
// potential conflicts such as
//
//	map[any]{T1(1): 0, T2(1): 0}
//
// where T1=T2.
func (st *falconState) typename(t types.Type) string { … }

// emit emits a Go expression that must have a legal type.
// In effect, we let the go/types constant folding algorithm
// do most of the heavy lifting (though it may be hard to
// believe from the complexity of this algorithm!).
func (st *falconState) emit(constraint ast.Expr) { … }

// emitNonNegative emits an []T{}[index] constraint,
// which ensures index is non-negative if constant.
func (st *falconState) emitNonNegative(index ast.Expr) { … }

// emitMonotonic emits an []T{}[i:j] constraint,
// which ensures i <= j if both are constant.
func (st *falconState) emitMonotonic(i, j ast.Expr) { … }

// emitUnique emits a T{elem1: 0, ... elemN: 0} constraint,
// which ensures that all constant elems are unique.
// T may be a map, slice, or array depending
// on the desired check semantics.
func (st *falconState) emitUnique(typ ast.Expr, elems []ast.Expr) { … }

func (st *falconState) stmt(s ast.Stmt) { … }

// fieldTypes visits the .Type of each field in the list.
func (st *falconState) fieldTypes(fields *ast.FieldList) { … }

// expr visits the expression (or type) and returns a
// non-nil result if the expression is constant or would
// become constant if all suitable function parameters were
// redeclared as constants.
//
// If the expression is constant, st.expr returns its type
// and value (types.TypeAndValue). If the expression would
// become constant, st.expr returns an ast.Expr tree whose
// leaves are literals and parameter references, and whose
// interior nodes are operations that may become constant,
// such as -x, x+y, f(x), and T(x). We call these would-be
// constant expressions "fallible constants", since they may
// fail to type-check for some values of x, i, and j. (We
// refer to the non-nil cases collectively as "maybe
// constant", and the nil case as "definitely non-constant".)
//
// As a side effect, st.expr emits constraints for each
// fallible constant expression; this is its main purpose.
//
// Consequently, st.expr must visit the entire subtree so
// that all necessary constraints are emitted. It may not
// short-circuit the traversal when it encounters a constant
// subexpression as constants may contain arbitrary other
// syntax that may impose constraints. Consider (as always)
// this contrived but legal example of a type parameter (!)
// that contains statement syntax:
//
//	func f[T [unsafe.Sizeof(func() { stmts })]int]()
//
// There is no need to emit constraints for (e.g.) s[i] when s
// and i are already constants, because we know the expression
// is sound, but it is sometimes easier to emit these
// redundant constraints than to avoid them.
func (st *falconState) expr(e ast.Expr) (res any) { … }

// toExpr converts the result of visitExpr to a falcon expression.
// (We don't do this in visitExpr as we first need to discriminate
// constants from maybe-constants.)
func (st *falconState) toExpr(x any) ast.Expr { … }

func makeLiteral(v constant.Value) ast.Expr { … }

func makeIntLit(x int64) *ast.BasicLit { … }

func isBasic(t types.Type, info types.BasicInfo) bool { … }
gotools/internal/refactor/inline/falcon.go
