falcon.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package inline
     6  
     7  // This file defines the callee side of the "fallible constant" analysis.
     8  
     9  import (
    10  	"fmt"
    11  	"go/ast"
    12  	"go/constant"
    13  	"go/format"
    14  	"go/token"
    15  	"go/types"
    16  	"strconv"
    17  	"strings"
    18  
    19  	"golang.org/x/tools/go/types/typeutil"
    20  	"golang.org/x/tools/internal/typeparams"
    21  )
    22  
    23  // falconResult is the result of the analysis of the callee.
    24  type falconResult struct {
    25  	Types       []falconType // types for falcon constraint environment
    26  	Constraints []string     // constraints (Go expressions) on values of fallible constants
    27  }
    28  
    29  // A falconType specifies the name and underlying type of a synthetic
    30  // defined type for use in falcon constraints.
    31  //
    32  // Unique types from callee code are bijectively mapped onto falcon
    33  // types so that constraints are independent of callee type
    34  // information but preserve type equivalence classes.
    35  //
    36  // Fresh names are deliberately obscure to avoid shadowing even if a
    37  // callee parameter has a name like "int" or "any".
    38  type falconType struct {
    39  	Name string
    40  	Kind types.BasicKind // string/number/bool
    41  }
    42  
    43  // falcon identifies "fallible constant" expressions, which are
    44  // expressions that may fail to compile if one or more of their
    45  // operands is changed from non-constant to constant.
    46  //
    47  // Consider:
    48  //
    49  //	func sub(s string, i, j int) string { return s[i:j] }
    50  //
    51  // If parameters are replaced by constants, the compiler is
    52  // required to perform these additional checks:
    53  //
    54  //   - if i is constant, 0 <= i.
    55  //   - if s and i are constant, i <= len(s).
    56  //   - ditto for j.
    57  //   - if i and j are constant, i <= j.
    58  //
    59  // s[i:j] is thus a "fallible constant" expression dependent on {s, i,
    60  // j}. Each falcon creates a set of conditional constraints across one
    61  // or more parameter variables.
    62  //
    63  //   - When inlining a call such as sub("abc", -1, 2), the parameter i
    64  //     cannot be eliminated by substitution as its argument value is
    65  //     negative.
    66  //
    67  //   - When inlining sub("", 2, 1), all three parameters cannot be
    68  //     simultaneously eliminated by substitution without violating i
    69  //     <= len(s) and j <= len(s), but the parameters i and j could be
    70  //     safely eliminated without s.
    71  //
    72  // Parameters that cannot be eliminated must remain non-constant,
    73  // either in the form of a binding declaration:
    74  //
    75  //	{ var i int = -1; return "abc"[i:2] }
    76  //
    77  // or a parameter of a literalization:
    78  //
    79  //	func (i int) string { return "abc"[i:2] }(-1)
    80  //
    81  // These example expressions are obviously doomed to fail at run
    82  // time, but in realistic cases such expressions are dominated by
    83  // appropriate conditions that make them reachable only when safe:
    84  //
    85  //	if 0 <= i && i <= j && j <= len(s) { _ = s[i:j] }
    86  //
    87  // (In principle a more sophisticated inliner could entirely eliminate
    88  // such unreachable blocks based on the condition being always-false
    89  // for the given parameter substitution, but this is tricky to do safely
    90  // because the type-checker considers only a single configuration.
    91  // Consider: if runtime.GOOS == "linux" { ... }.)
    92  //
    93  // We believe this is an exhaustive list of "fallible constant" operations:
    94  //
    95  //   - switch z { case x: case y } 	// duplicate case values
    96  //   - s[i], s[i:j], s[i:j:k]		// index out of bounds (0 <= i <= j <= k <= len(s))
    97  //   - T{x: 0}				// index out of bounds, duplicate index
    98  //   - x/y, x%y, x/=y, x%=y		// integer division by zero; minint/-1 overflow
    99  //   - x+y, x-y, x*y			// arithmetic overflow
   100  //   - x<<y				// shift out of range
   101  //   - -x				// negation of minint
   102  //   - T(x)				// value out of range
   103  //
   104  // The fundamental reason for this elaborate algorithm is that the
   105  // "separate analysis" of callee and caller, as required when running
   106  // in an environment such as unitchecker, means that there is no way
   107  // for us to simply invoke the type checker on the combination of
   108  // caller and callee code, as by the time we analyze the caller, we no
   109  // longer have access to type information for the callee (and, in
   110  // particular, any of its direct dependencies that are not direct
   111  // dependencies of the caller). So, in effect, we are forced to map
   112  // the problem in a neutral (callee-type-independent) constraint
   113  // system that can be verified later.
   114  func falcon(logf func(string, ...any), fset *token.FileSet, params map[*types.Var]*paramInfo, info *types.Info, decl *ast.FuncDecl) falconResult {
   115  
   116  	st := &falconState{
   117  		logf:   logf,
   118  		fset:   fset,
   119  		params: params,
   120  		info:   info,
   121  		decl:   decl,
   122  	}
   123  
   124  	// type mapping
   125  	st.int = st.typename(types.Typ[types.Int])
   126  	st.any = "interface{}" // don't use "any" as it may be shadowed
   127  	for obj, info := range st.params {
   128  		if isBasic(obj.Type(), types.IsConstType) {
   129  			info.FalconType = st.typename(obj.Type())
   130  		}
   131  	}
   132  
   133  	st.stmt(st.decl.Body)
   134  
   135  	return st.result
   136  }
   137  
   138  type falconState struct {
   139  	// inputs
   140  	logf   func(string, ...any)
   141  	fset   *token.FileSet
   142  	params map[*types.Var]*paramInfo
   143  	info   *types.Info
   144  	decl   *ast.FuncDecl
   145  
   146  	// working state
   147  	int       string
   148  	any       string
   149  	typenames typeutil.Map
   150  
   151  	result falconResult
   152  }
   153  
   154  // typename returns the name in the falcon constraint system
   155  // of a given string/number/bool type t. Falcon types are
   156  // specified directly in go/types data structures rather than
   157  // by name, avoiding potential shadowing conflicts with
   158  // confusing parameter names such as "int".
   159  //
   160  // Also, each distinct type (as determined by types.Identical)
   161  // is mapped to a fresh type in the falcon system so that we
   162  // can map the types in the callee code into a neutral form
   163  // that does not depend on imports, allowing us to detect
   164  // potential conflicts such as
   165  //
   166  //	map[any]{T1(1): 0, T2(1): 0}
   167  //
   168  // where T1=T2.
   169  func (st *falconState) typename(t types.Type) string {
   170  	name, ok := st.typenames.At(t).(string)
   171  	if !ok {
   172  		basic := t.Underlying().(*types.Basic)
   173  
   174  		// That dot ۰ is an Arabic zero numeral U+06F0.
   175  		// It is very unlikely to appear in a real program.
   176  		// TODO(adonovan): use a non-heuristic solution.
   177  		name = fmt.Sprintf("%s۰%d", basic, st.typenames.Len())
   178  		st.typenames.Set(t, name)
   179  		st.logf("falcon: emit type %s %s // %q", name, basic, t)
   180  		st.result.Types = append(st.result.Types, falconType{
   181  			Name: name,
   182  			Kind: basic.Kind(),
   183  		})
   184  	}
   185  	return name
   186  }
   187  
   188  // -- constraint emission --
   189  
   190  // emit emits a Go expression that must have a legal type.
   191  // In effect, we let the go/types constant folding algorithm
   192  // do most of the heavy lifting (though it may be hard to
   193  // believe from the complexity of this algorithm!).
   194  func (st *falconState) emit(constraint ast.Expr) {
   195  	var out strings.Builder
   196  	if err := format.Node(&out, st.fset, constraint); err != nil {
   197  		panic(err) // can't happen
   198  	}
   199  	syntax := out.String()
   200  	st.logf("falcon: emit constraint %s", syntax)
   201  	st.result.Constraints = append(st.result.Constraints, syntax)
   202  }
   203  
   204  // emitNonNegative emits an []T{}[index] constraint,
   205  // which ensures index is non-negative if constant.
   206  func (st *falconState) emitNonNegative(index ast.Expr) {
   207  	st.emit(&ast.IndexExpr{
   208  		X: &ast.CompositeLit{
   209  			Type: &ast.ArrayType{
   210  				Elt: makeIdent(st.int),
   211  			},
   212  		},
   213  		Index: index,
   214  	})
   215  }
   216  
   217  // emitMonotonic emits an []T{}[i:j] constraint,
   218  // which ensures i <= j if both are constant.
   219  func (st *falconState) emitMonotonic(i, j ast.Expr) {
   220  	st.emit(&ast.SliceExpr{
   221  		X: &ast.CompositeLit{
   222  			Type: &ast.ArrayType{
   223  				Elt: makeIdent(st.int),
   224  			},
   225  		},
   226  		Low:  i,
   227  		High: j,
   228  	})
   229  }
   230  
   231  // emitUnique emits a T{elem1: 0, ... elemN: 0} constraint,
   232  // which ensures that all constant elems are unique.
   233  // T may be a map, slice, or array depending
   234  // on the desired check semantics.
   235  func (st *falconState) emitUnique(typ ast.Expr, elems []ast.Expr) {
   236  	if len(elems) > 1 {
   237  		var elts []ast.Expr
   238  		for _, elem := range elems {
   239  			elts = append(elts, &ast.KeyValueExpr{
   240  				Key:   elem,
   241  				Value: makeIntLit(0),
   242  			})
   243  		}
   244  		st.emit(&ast.CompositeLit{
   245  			Type: typ,
   246  			Elts: elts,
   247  		})
   248  	}
   249  }
   250  
   251  // -- traversal --
   252  
   253  // The traversal functions scan the callee body for expressions that
   254  // are not constant but would become constant if the parameter vars
   255  // were redeclared as constants, and emits for each one a constraint
   256  // (a Go expression) with the property that it will not type-check
   257  // (using types.CheckExpr) if the particular argument values are
   258  // unsuitable.
   259  //
   260  // These constraints are checked by Inline with the actual
   261  // constant argument values. Violations cause it to reject
   262  // parameters as candidates for substitution.
   263  
   264  func (st *falconState) stmt(s ast.Stmt) {
   265  	ast.Inspect(s, func(n ast.Node) bool {
   266  		switch n := n.(type) {
   267  		case ast.Expr:
   268  			_ = st.expr(n)
   269  			return false // skip usual traversal
   270  
   271  		case *ast.AssignStmt:
   272  			switch n.Tok {
   273  			case token.QUO_ASSIGN, token.REM_ASSIGN:
   274  				// x /= y
   275  				// Possible "integer division by zero"
   276  				// Emit constraint: 1/y.
   277  				_ = st.expr(n.Lhs[0])
   278  				kY := st.expr(n.Rhs[0])
   279  				if kY, ok := kY.(ast.Expr); ok {
   280  					op := token.QUO
   281  					if n.Tok == token.REM_ASSIGN {
   282  						op = token.REM
   283  					}
   284  					st.emit(&ast.BinaryExpr{
   285  						Op: op,
   286  						X:  makeIntLit(1),
   287  						Y:  kY,
   288  					})
   289  				}
   290  				return false // skip usual traversal
   291  			}
   292  
   293  		case *ast.SwitchStmt:
   294  			if n.Init != nil {
   295  				st.stmt(n.Init)
   296  			}
   297  			tBool := types.Type(types.Typ[types.Bool])
   298  			tagType := tBool // default: true
   299  			if n.Tag != nil {
   300  				st.expr(n.Tag)
   301  				tagType = st.info.TypeOf(n.Tag)
   302  			}
   303  
   304  			// Possible "duplicate case value".
   305  			// Emit constraint map[T]int{v1: 0, ..., vN:0}
   306  			// to ensure all maybe-constant case values are unique
   307  			// (unless switch tag is boolean, which is relaxed).
   308  			var unique []ast.Expr
   309  			for _, clause := range n.Body.List {
   310  				clause := clause.(*ast.CaseClause)
   311  				for _, caseval := range clause.List {
   312  					if k := st.expr(caseval); k != nil {
   313  						unique = append(unique, st.toExpr(k))
   314  					}
   315  				}
   316  				for _, stmt := range clause.Body {
   317  					st.stmt(stmt)
   318  				}
   319  			}
   320  			if unique != nil && !types.Identical(tagType.Underlying(), tBool) {
   321  				tname := st.any
   322  				if !types.IsInterface(tagType) {
   323  					tname = st.typename(tagType)
   324  				}
   325  				t := &ast.MapType{
   326  					Key:   makeIdent(tname),
   327  					Value: makeIdent(st.int),
   328  				}
   329  				st.emitUnique(t, unique)
   330  			}
   331  		}
   332  		return true
   333  	})
   334  }
   335  
   336  // fieldTypes visits the .Type of each field in the list.
   337  func (st *falconState) fieldTypes(fields *ast.FieldList) {
   338  	if fields != nil {
   339  		for _, field := range fields.List {
   340  			_ = st.expr(field.Type)
   341  		}
   342  	}
   343  }
   344  
   345  // expr visits the expression (or type) and returns a
   346  // non-nil result if the expression is constant or would
   347  // become constant if all suitable function parameters were
   348  // redeclared as constants.
   349  //
   350  // If the expression is constant, st.expr returns its type
   351  // and value (types.TypeAndValue). If the expression would
   352  // become constant, st.expr returns an ast.Expr tree whose
   353  // leaves are literals and parameter references, and whose
   354  // interior nodes are operations that may become constant,
   355  // such as -x, x+y, f(x), and T(x). We call these would-be
   356  // constant expressions "fallible constants", since they may
   357  // fail to type-check for some values of x, i, and j. (We
   358  // refer to the non-nil cases collectively as "maybe
   359  // constant", and the nil case as "definitely non-constant".)
   360  //
   361  // As a side effect, st.expr emits constraints for each
   362  // fallible constant expression; this is its main purpose.
   363  //
   364  // Consequently, st.expr must visit the entire subtree so
   365  // that all necessary constraints are emitted. It may not
   366  // short-circuit the traversal when it encounters a constant
   367  // subexpression as constants may contain arbitrary other
   368  // syntax that may impose constraints. Consider (as always)
   369  // this contrived but legal example of a type parameter (!)
   370  // that contains statement syntax:
   371  //
   372  //	func f[T [unsafe.Sizeof(func() { stmts })]int]()
   373  //
   374  // There is no need to emit constraints for (e.g.) s[i] when s
   375  // and i are already constants, because we know the expression
   376  // is sound, but it is sometimes easier to emit these
   377  // redundant constraints than to avoid them.
   378  func (st *falconState) expr(e ast.Expr) (res any) { // = types.TypeAndValue | ast.Expr
   379  	tv := st.info.Types[e]
   380  	if tv.Value != nil {
   381  		// A constant value overrides any other result.
   382  		defer func() { res = tv }()
   383  	}
   384  
   385  	switch e := e.(type) {
   386  	case *ast.Ident:
   387  		if v, ok := st.info.Uses[e].(*types.Var); ok {
   388  			if _, ok := st.params[v]; ok && isBasic(v.Type(), types.IsConstType) {
   389  				return e // reference to constable parameter
   390  			}
   391  		}
   392  		// (References to *types.Const are handled by the defer.)
   393  
   394  	case *ast.BasicLit:
   395  		// constant
   396  
   397  	case *ast.ParenExpr:
   398  		return st.expr(e.X)
   399  
   400  	case *ast.FuncLit:
   401  		_ = st.expr(e.Type)
   402  		st.stmt(e.Body)
   403  		// definitely non-constant
   404  
   405  	case *ast.CompositeLit:
   406  		// T{k: v, ...}, where T ∈ {array,*array,slice,map},
   407  		// imposes a constraint that all constant k are
   408  		// distinct and, for arrays [n]T, within range 0-n.
   409  		//
   410  		// Types matter, not just values. For example,
   411  		// an interface-keyed map may contain keys
   412  		// that are numerically equal so long as they
   413  		// are of distinct types. For example:
   414  		//
   415  		//   type myint int
   416  		//   map[any]bool{1: true, 1:        true} // error: duplicate key
   417  		//   map[any]bool{1: true, int16(1): true} // ok
   418  		//   map[any]bool{1: true, myint(1): true} // ok
   419  		//
   420  		// This can be asserted by emitting a
   421  		// constraint of the form T{k1: 0, ..., kN: 0}.
   422  		if e.Type != nil {
   423  			_ = st.expr(e.Type)
   424  		}
   425  		t := types.Unalias(typeparams.Deref(tv.Type))
   426  		ct := typeparams.CoreType(t)
   427  		var mapKeys []ast.Expr // map key expressions; must be distinct if constant
   428  		for _, elt := range e.Elts {
   429  			if kv, ok := elt.(*ast.KeyValueExpr); ok {
   430  				if is[*types.Map](ct) {
   431  					if k := st.expr(kv.Key); k != nil {
   432  						mapKeys = append(mapKeys, st.toExpr(k))
   433  					}
   434  				}
   435  				_ = st.expr(kv.Value)
   436  			} else {
   437  				_ = st.expr(elt)
   438  			}
   439  		}
   440  		if len(mapKeys) > 0 {
   441  			// Inlining a map literal may replace variable key expressions by constants.
   442  			// All such constants must have distinct values.
   443  			// (Array and slice literals do not permit non-constant keys.)
   444  			t := ct.(*types.Map)
   445  			var typ ast.Expr
   446  			if types.IsInterface(t.Key()) {
   447  				typ = &ast.MapType{
   448  					Key:   makeIdent(st.any),
   449  					Value: makeIdent(st.int),
   450  				}
   451  			} else {
   452  				typ = &ast.MapType{
   453  					Key:   makeIdent(st.typename(t.Key())),
   454  					Value: makeIdent(st.int),
   455  				}
   456  			}
   457  			st.emitUnique(typ, mapKeys)
   458  		}
   459  		// definitely non-constant
   460  
   461  	case *ast.SelectorExpr:
   462  		_ = st.expr(e.X)
   463  		_ = st.expr(e.Sel)
   464  		// The defer is sufficient to handle
   465  		// qualified identifiers (pkg.Const).
   466  		// All other cases are definitely non-constant.
   467  
   468  	case *ast.IndexExpr:
   469  		if tv.IsType() {
   470  			// type C[T]
   471  			_ = st.expr(e.X)
   472  			_ = st.expr(e.Index)
   473  		} else {
   474  			// term x[i]
   475  			//
   476  			// Constraints (if x is slice/string/array/*array, not map):
   477  			// - i >= 0
   478  			//     if i is a fallible constant
   479  			// - i < len(x)
   480  			//     if x is array/*array and
   481  			//     i is a fallible constant;
   482  			//  or if s is a string and both i,
   483  			//     s are maybe-constants,
   484  			//     but not both are constants.
   485  			kX := st.expr(e.X)
   486  			kI := st.expr(e.Index)
   487  			if kI != nil && !is[*types.Map](st.info.TypeOf(e.X).Underlying()) {
   488  				if kI, ok := kI.(ast.Expr); ok {
   489  					st.emitNonNegative(kI)
   490  				}
   491  				// Emit constraint to check indices against known length.
   492  				// TODO(adonovan): factor with SliceExpr logic.
   493  				var x ast.Expr
   494  				if kX != nil {
   495  					// string
   496  					x = st.toExpr(kX)
   497  				} else if arr, ok := typeparams.CoreType(typeparams.Deref(st.info.TypeOf(e.X))).(*types.Array); ok {
   498  					// array, *array
   499  					x = &ast.CompositeLit{
   500  						Type: &ast.ArrayType{
   501  							Len: makeIntLit(arr.Len()),
   502  							Elt: makeIdent(st.int),
   503  						},
   504  					}
   505  				}
   506  				if x != nil {
   507  					st.emit(&ast.IndexExpr{
   508  						X:     x,
   509  						Index: st.toExpr(kI),
   510  					})
   511  				}
   512  			}
   513  		}
   514  		// definitely non-constant
   515  
   516  	case *ast.SliceExpr:
   517  		// x[low:high:max]
   518  		//
   519  		// Emit non-negative constraints for each index,
   520  		// plus low <= high <= max <= len(x)
   521  		// for each pair that are maybe-constant
   522  		// but not definitely constant.
   523  
   524  		kX := st.expr(e.X)
   525  		var kLow, kHigh, kMax any
   526  		if e.Low != nil {
   527  			kLow = st.expr(e.Low)
   528  			if kLow != nil {
   529  				if kLow, ok := kLow.(ast.Expr); ok {
   530  					st.emitNonNegative(kLow)
   531  				}
   532  			}
   533  		}
   534  		if e.High != nil {
   535  			kHigh = st.expr(e.High)
   536  			if kHigh != nil {
   537  				if kHigh, ok := kHigh.(ast.Expr); ok {
   538  					st.emitNonNegative(kHigh)
   539  				}
   540  				if kLow != nil {
   541  					st.emitMonotonic(st.toExpr(kLow), st.toExpr(kHigh))
   542  				}
   543  			}
   544  		}
   545  		if e.Max != nil {
   546  			kMax = st.expr(e.Max)
   547  			if kMax != nil {
   548  				if kMax, ok := kMax.(ast.Expr); ok {
   549  					st.emitNonNegative(kMax)
   550  				}
   551  				if kHigh != nil {
   552  					st.emitMonotonic(st.toExpr(kHigh), st.toExpr(kMax))
   553  				}
   554  			}
   555  		}
   556  
   557  		// Emit constraint to check indices against known length.
   558  		var x ast.Expr
   559  		if kX != nil {
   560  			// string
   561  			x = st.toExpr(kX)
   562  		} else if arr, ok := typeparams.CoreType(typeparams.Deref(st.info.TypeOf(e.X))).(*types.Array); ok {
   563  			// array, *array
   564  			x = &ast.CompositeLit{
   565  				Type: &ast.ArrayType{
   566  					Len: makeIntLit(arr.Len()),
   567  					Elt: makeIdent(st.int),
   568  				},
   569  			}
   570  		}
   571  		if x != nil {
   572  			// Avoid slice[::max] if kHigh is nonconstant (nil).
   573  			high, max := st.toExpr(kHigh), st.toExpr(kMax)
   574  			if high == nil {
   575  				high = max // => slice[:max:max]
   576  			}
   577  			st.emit(&ast.SliceExpr{
   578  				X:    x,
   579  				Low:  st.toExpr(kLow),
   580  				High: high,
   581  				Max:  max,
   582  			})
   583  		}
   584  		// definitely non-constant
   585  
   586  	case *ast.TypeAssertExpr:
   587  		_ = st.expr(e.X)
   588  		if e.Type != nil {
   589  			_ = st.expr(e.Type)
   590  		}
   591  
   592  	case *ast.CallExpr:
   593  		_ = st.expr(e.Fun)
   594  		if tv, ok := st.info.Types[e.Fun]; ok && tv.IsType() {
   595  			// conversion T(x)
   596  			//
   597  			// Possible "value out of range".
   598  			kX := st.expr(e.Args[0])
   599  			if kX != nil && isBasic(tv.Type, types.IsConstType) {
   600  				conv := convert(makeIdent(st.typename(tv.Type)), st.toExpr(kX))
   601  				if is[ast.Expr](kX) {
   602  					st.emit(conv)
   603  				}
   604  				return conv
   605  			}
   606  			return nil // definitely non-constant
   607  		}
   608  
   609  		// call f(x)
   610  
   611  		all := true // all args are possibly-constant
   612  		kArgs := make([]ast.Expr, len(e.Args))
   613  		for i, arg := range e.Args {
   614  			if kArg := st.expr(arg); kArg != nil {
   615  				kArgs[i] = st.toExpr(kArg)
   616  			} else {
   617  				all = false
   618  			}
   619  		}
   620  
   621  		// Calls to built-ins with fallibly constant arguments
   622  		// may become constant. All other calls are either
   623  		// constant or non-constant
   624  		if id, ok := e.Fun.(*ast.Ident); ok && all && tv.Value == nil {
   625  			if builtin, ok := st.info.Uses[id].(*types.Builtin); ok {
   626  				switch builtin.Name() {
   627  				case "len", "imag", "real", "complex", "min", "max":
   628  					return &ast.CallExpr{
   629  						Fun:      id,
   630  						Args:     kArgs,
   631  						Ellipsis: e.Ellipsis,
   632  					}
   633  				}
   634  			}
   635  		}
   636  
   637  	case *ast.StarExpr: // *T, *ptr
   638  		_ = st.expr(e.X)
   639  
   640  	case *ast.UnaryExpr:
   641  		// + - ! ^ & <- ~
   642  		//
   643  		// Possible "negation of minint".
   644  		// Emit constraint: -x
   645  		kX := st.expr(e.X)
   646  		if kX != nil && !is[types.TypeAndValue](kX) {
   647  			if e.Op == token.SUB {
   648  				st.emit(&ast.UnaryExpr{
   649  					Op: e.Op,
   650  					X:  st.toExpr(kX),
   651  				})
   652  			}
   653  
   654  			return &ast.UnaryExpr{
   655  				Op: e.Op,
   656  				X:  st.toExpr(kX),
   657  			}
   658  		}
   659  
   660  	case *ast.BinaryExpr:
   661  		kX := st.expr(e.X)
   662  		kY := st.expr(e.Y)
   663  		switch e.Op {
   664  		case token.QUO, token.REM:
   665  			// x/y, x%y
   666  			//
   667  			// Possible "integer division by zero" or
   668  			// "minint / -1" overflow.
   669  			// Emit constraint: x/y or 1/y
   670  			if kY != nil {
   671  				if kX == nil {
   672  					kX = makeIntLit(1)
   673  				}
   674  				st.emit(&ast.BinaryExpr{
   675  					Op: e.Op,
   676  					X:  st.toExpr(kX),
   677  					Y:  st.toExpr(kY),
   678  				})
   679  			}
   680  
   681  		case token.ADD, token.SUB, token.MUL:
   682  			// x+y, x-y, x*y
   683  			//
   684  			// Possible "arithmetic overflow".
   685  			// Emit constraint: x+y
   686  			if kX != nil && kY != nil {
   687  				st.emit(&ast.BinaryExpr{
   688  					Op: e.Op,
   689  					X:  st.toExpr(kX),
   690  					Y:  st.toExpr(kY),
   691  				})
   692  			}
   693  
   694  		case token.SHL, token.SHR:
   695  			// x << y, x >> y
   696  			//
   697  			// Possible "constant shift too large".
   698  			// Either operand may be too large individually,
   699  			// and they may be too large together.
   700  			// Emit constraint:
   701  			//    x << y (if both maybe-constant)
   702  			//    x << 0 (if y is non-constant)
   703  			//    1 << y (if x is non-constant)
   704  			if kX != nil || kY != nil {
   705  				x := st.toExpr(kX)
   706  				if x == nil {
   707  					x = makeIntLit(1)
   708  				}
   709  				y := st.toExpr(kY)
   710  				if y == nil {
   711  					y = makeIntLit(0)
   712  				}
   713  				st.emit(&ast.BinaryExpr{
   714  					Op: e.Op,
   715  					X:  x,
   716  					Y:  y,
   717  				})
   718  			}
   719  
   720  		case token.LSS, token.GTR, token.EQL, token.NEQ, token.LEQ, token.GEQ:
   721  			// < > == != <= <=
   722  			//
   723  			// A "x cmp y" expression with constant operands x, y is
   724  			// itself constant, but I can't see how a constant bool
   725  			// could be fallible: the compiler doesn't reject duplicate
   726  			// boolean cases in a switch, presumably because boolean
   727  			// switches are less like n-way branches and more like
   728  			// sequential if-else chains with possibly overlapping
   729  			// conditions; and there is (sadly) no way to convert a
   730  			// boolean constant to an int constant.
   731  		}
   732  		if kX != nil && kY != nil {
   733  			return &ast.BinaryExpr{
   734  				Op: e.Op,
   735  				X:  st.toExpr(kX),
   736  				Y:  st.toExpr(kY),
   737  			}
   738  		}
   739  
   740  	// types
   741  	//
   742  	// We need to visit types (and even type parameters)
   743  	// in order to reach all the places where things could go wrong:
   744  	//
   745  	// 	const (
   746  	// 		s = ""
   747  	// 		i = 0
   748  	// 	)
   749  	// 	type C[T [unsafe.Sizeof(func() { _ = s[i] })]int] bool
   750  
   751  	case *ast.IndexListExpr:
   752  		_ = st.expr(e.X)
   753  		for _, expr := range e.Indices {
   754  			_ = st.expr(expr)
   755  		}
   756  
   757  	case *ast.Ellipsis:
   758  		if e.Elt != nil {
   759  			_ = st.expr(e.Elt)
   760  		}
   761  
   762  	case *ast.ArrayType:
   763  		if e.Len != nil {
   764  			_ = st.expr(e.Len)
   765  		}
   766  		_ = st.expr(e.Elt)
   767  
   768  	case *ast.StructType:
   769  		st.fieldTypes(e.Fields)
   770  
   771  	case *ast.FuncType:
   772  		st.fieldTypes(e.TypeParams)
   773  		st.fieldTypes(e.Params)
   774  		st.fieldTypes(e.Results)
   775  
   776  	case *ast.InterfaceType:
   777  		st.fieldTypes(e.Methods)
   778  
   779  	case *ast.MapType:
   780  		_ = st.expr(e.Key)
   781  		_ = st.expr(e.Value)
   782  
   783  	case *ast.ChanType:
   784  		_ = st.expr(e.Value)
   785  	}
   786  	return
   787  }
   788  
   789  // toExpr converts the result of visitExpr to a falcon expression.
   790  // (We don't do this in visitExpr as we first need to discriminate
   791  // constants from maybe-constants.)
   792  func (st *falconState) toExpr(x any) ast.Expr {
   793  	switch x := x.(type) {
   794  	case nil:
   795  		return nil
   796  
   797  	case types.TypeAndValue:
   798  		lit := makeLiteral(x.Value)
   799  		if !isBasic(x.Type, types.IsUntyped) {
   800  			// convert to "typed" type
   801  			lit = &ast.CallExpr{
   802  				Fun:  makeIdent(st.typename(x.Type)),
   803  				Args: []ast.Expr{lit},
   804  			}
   805  		}
   806  		return lit
   807  
   808  	case ast.Expr:
   809  		return x
   810  
   811  	default:
   812  		panic(x)
   813  	}
   814  }
   815  
   816  func makeLiteral(v constant.Value) ast.Expr {
   817  	switch v.Kind() {
   818  	case constant.Bool:
   819  		// Rather than refer to the true or false built-ins,
   820  		// which could be shadowed by poorly chosen parameter
   821  		// names, we use 0 == 0 for true and 0 != 0 for false.
   822  		op := token.EQL
   823  		if !constant.BoolVal(v) {
   824  			op = token.NEQ
   825  		}
   826  		return &ast.BinaryExpr{
   827  			Op: op,
   828  			X:  makeIntLit(0),
   829  			Y:  makeIntLit(0),
   830  		}
   831  
   832  	case constant.String:
   833  		return &ast.BasicLit{
   834  			Kind:  token.STRING,
   835  			Value: v.ExactString(),
   836  		}
   837  
   838  	case constant.Int:
   839  		return &ast.BasicLit{
   840  			Kind:  token.INT,
   841  			Value: v.ExactString(),
   842  		}
   843  
   844  	case constant.Float:
   845  		return &ast.BasicLit{
   846  			Kind:  token.FLOAT,
   847  			Value: v.ExactString(),
   848  		}
   849  
   850  	case constant.Complex:
   851  		// The components could be float or int.
   852  		y := makeLiteral(constant.Imag(v))
   853  		y.(*ast.BasicLit).Value += "i" // ugh
   854  		if re := constant.Real(v); !consteq(re, kZeroInt) {
   855  			// complex: x + yi
   856  			y = &ast.BinaryExpr{
   857  				Op: token.ADD,
   858  				X:  makeLiteral(re),
   859  				Y:  y,
   860  			}
   861  		}
   862  		return y
   863  
   864  	default:
   865  		panic(v.Kind())
   866  	}
   867  }
   868  
   869  func makeIntLit(x int64) *ast.BasicLit {
   870  	return &ast.BasicLit{
   871  		Kind:  token.INT,
   872  		Value: strconv.FormatInt(x, 10),
   873  	}
   874  }
   875  
   876  func isBasic(t types.Type, info types.BasicInfo) bool {
   877  	basic, ok := t.Underlying().(*types.Basic)
   878  	return ok && basic.Info()&info != 0
   879  }
   880
View as plain text