Source file src/go/constant/value.go

     1  // Copyright 2013 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 constant implements Values representing untyped
     6  // Go constants and their corresponding operations.
     7  //
     8  // A special Unknown value may be used when a value
     9  // is unknown due to an error. Operations on unknown
    10  // values produce unknown values unless specified
    11  // otherwise.
    12  //
    13  package constant
    14  
    15  import (
    16  	"fmt"
    17  	"go/token"
    18  	"math"
    19  	"math/big"
    20  	"math/bits"
    21  	"strconv"
    22  	"strings"
    23  	"sync"
    24  	"unicode/utf8"
    25  )
    26  
    27  //go:generate stringer -type Kind
    28  
    29  // Kind specifies the kind of value represented by a Value.
    30  type Kind int
    31  
    32  const (
    33  	// unknown values
    34  	Unknown Kind = iota
    35  
    36  	// non-numeric values
    37  	Bool
    38  	String
    39  
    40  	// numeric values
    41  	Int
    42  	Float
    43  	Complex
    44  )
    45  
    46  // A Value represents the value of a Go constant.
    47  type Value interface {
    48  	// Kind returns the value kind.
    49  	Kind() Kind
    50  
    51  	// String returns a short, quoted (human-readable) form of the value.
    52  	// For numeric values, the result may be an approximation;
    53  	// for String values the result may be a shortened string.
    54  	// Use ExactString for a string representing a value exactly.
    55  	String() string
    56  
    57  	// ExactString returns an exact, quoted (human-readable) form of the value.
    58  	// If the Value is of Kind String, use StringVal to obtain the unquoted string.
    59  	ExactString() string
    60  
    61  	// Prevent external implementations.
    62  	implementsValue()
    63  }
    64  
    65  // ----------------------------------------------------------------------------
    66  // Implementations
    67  
    68  // Maximum supported mantissa precision.
    69  // The spec requires at least 256 bits; typical implementations use 512 bits.
    70  const prec = 512
    71  
    72  // TODO(gri) Consider storing "error" information in an unknownVal so clients
    73  //           can provide better error messages. For instance, if a number is
    74  //           too large (incl. infinity), that could be recorded in unknownVal.
    75  //           See also #20583 and #42695 for use cases.
    76  
    77  // Representation of values:
    78  //
    79  // Values of Int and Float Kind have two different representations each: int64Val
    80  // and intVal, and ratVal and floatVal. When possible, the "smaller", respectively
    81  // more precise (for Floats) representation is chosen. However, once a Float value
    82  // is represented as a floatVal, any subsequent results remain floatVals (unless
    83  // explicitly converted); i.e., no attempt is made to convert a floatVal back into
    84  // a ratVal. The reasoning is that all representations but floatVal are mathematically
    85  // exact, but once that precision is lost (by moving to floatVal), moving back to
    86  // a different representation implies a precision that's not actually there.
    87  
    88  type (
    89  	unknownVal struct{}
    90  	boolVal    bool
    91  	stringVal  struct {
    92  		// Lazy value: either a string (l,r==nil) or an addition (l,r!=nil).
    93  		mu   sync.Mutex
    94  		s    string
    95  		l, r *stringVal
    96  	}
    97  	int64Val   int64                    // Int values representable as an int64
    98  	intVal     struct{ val *big.Int }   // Int values not representable as an int64
    99  	ratVal     struct{ val *big.Rat }   // Float values representable as a fraction
   100  	floatVal   struct{ val *big.Float } // Float values not representable as a fraction
   101  	complexVal struct{ re, im Value }
   102  )
   103  
   104  func (unknownVal) Kind() Kind { return Unknown }
   105  func (boolVal) Kind() Kind    { return Bool }
   106  func (*stringVal) Kind() Kind { return String }
   107  func (int64Val) Kind() Kind   { return Int }
   108  func (intVal) Kind() Kind     { return Int }
   109  func (ratVal) Kind() Kind     { return Float }
   110  func (floatVal) Kind() Kind   { return Float }
   111  func (complexVal) Kind() Kind { return Complex }
   112  
   113  func (unknownVal) String() string { return "unknown" }
   114  func (x boolVal) String() string  { return strconv.FormatBool(bool(x)) }
   115  
   116  // String returns a possibly shortened quoted form of the String value.
   117  func (x *stringVal) String() string {
   118  	const maxLen = 72 // a reasonable length
   119  	s := strconv.Quote(x.string())
   120  	if utf8.RuneCountInString(s) > maxLen {
   121  		// The string without the enclosing quotes is greater than maxLen-2 runes
   122  		// long. Remove the last 3 runes (including the closing '"') by keeping
   123  		// only the first maxLen-3 runes; then add "...".
   124  		i := 0
   125  		for n := 0; n < maxLen-3; n++ {
   126  			_, size := utf8.DecodeRuneInString(s[i:])
   127  			i += size
   128  		}
   129  		s = s[:i] + "..."
   130  	}
   131  	return s
   132  }
   133  
   134  // string constructs and returns the actual string literal value.
   135  // If x represents an addition, then it rewrites x to be a single
   136  // string, to speed future calls. This lazy construction avoids
   137  // building different string values for all subpieces of a large
   138  // concatenation. See golang.org/issue/23348.
   139  func (x *stringVal) string() string {
   140  	x.mu.Lock()
   141  	if x.l != nil {
   142  		x.s = strings.Join(reverse(x.appendReverse(nil)), "")
   143  		x.l = nil
   144  		x.r = nil
   145  	}
   146  	s := x.s
   147  	x.mu.Unlock()
   148  
   149  	return s
   150  }
   151  
   152  // reverse reverses x in place and returns it.
   153  func reverse(x []string) []string {
   154  	n := len(x)
   155  	for i := 0; i+i < n; i++ {
   156  		x[i], x[n-1-i] = x[n-1-i], x[i]
   157  	}
   158  	return x
   159  }
   160  
   161  // appendReverse appends to list all of x's subpieces, but in reverse,
   162  // and returns the result. Appending the reversal allows processing
   163  // the right side in a recursive call and the left side in a loop.
   164  // Because a chain like a + b + c + d + e is actually represented
   165  // as ((((a + b) + c) + d) + e), the left-side loop avoids deep recursion.
   166  // x must be locked.
   167  func (x *stringVal) appendReverse(list []string) []string {
   168  	y := x
   169  	for y.r != nil {
   170  		y.r.mu.Lock()
   171  		list = y.r.appendReverse(list)
   172  		y.r.mu.Unlock()
   173  
   174  		l := y.l
   175  		if y != x {
   176  			y.mu.Unlock()
   177  		}
   178  		l.mu.Lock()
   179  		y = l
   180  	}
   181  	s := y.s
   182  	if y != x {
   183  		y.mu.Unlock()
   184  	}
   185  	return append(list, s)
   186  }
   187  
   188  func (x int64Val) String() string { return strconv.FormatInt(int64(x), 10) }
   189  func (x intVal) String() string   { return x.val.String() }
   190  func (x ratVal) String() string   { return rtof(x).String() }
   191  
   192  // String returns a decimal approximation of the Float value.
   193  func (x floatVal) String() string {
   194  	f := x.val
   195  
   196  	// Don't try to convert infinities (will not terminate).
   197  	if f.IsInf() {
   198  		return f.String()
   199  	}
   200  
   201  	// Use exact fmt formatting if in float64 range (common case):
   202  	// proceed if f doesn't underflow to 0 or overflow to inf.
   203  	if x, _ := f.Float64(); f.Sign() == 0 == (x == 0) && !math.IsInf(x, 0) {
   204  		return fmt.Sprintf("%.6g", x)
   205  	}
   206  
   207  	// Out of float64 range. Do approximate manual to decimal
   208  	// conversion to avoid precise but possibly slow Float
   209  	// formatting.
   210  	// f = mant * 2**exp
   211  	var mant big.Float
   212  	exp := f.MantExp(&mant) // 0.5 <= |mant| < 1.0
   213  
   214  	// approximate float64 mantissa m and decimal exponent d
   215  	// f ~ m * 10**d
   216  	m, _ := mant.Float64()                     // 0.5 <= |m| < 1.0
   217  	d := float64(exp) * (math.Ln2 / math.Ln10) // log_10(2)
   218  
   219  	// adjust m for truncated (integer) decimal exponent e
   220  	e := int64(d)
   221  	m *= math.Pow(10, d-float64(e))
   222  
   223  	// ensure 1 <= |m| < 10
   224  	switch am := math.Abs(m); {
   225  	case am < 1-0.5e-6:
   226  		// The %.6g format below rounds m to 5 digits after the
   227  		// decimal point. Make sure that m*10 < 10 even after
   228  		// rounding up: m*10 + 0.5e-5 < 10 => m < 1 - 0.5e6.
   229  		m *= 10
   230  		e--
   231  	case am >= 10:
   232  		m /= 10
   233  		e++
   234  	}
   235  
   236  	return fmt.Sprintf("%.6ge%+d", m, e)
   237  }
   238  
   239  func (x complexVal) String() string { return fmt.Sprintf("(%s + %si)", x.re, x.im) }
   240  
   241  func (x unknownVal) ExactString() string { return x.String() }
   242  func (x boolVal) ExactString() string    { return x.String() }
   243  func (x *stringVal) ExactString() string { return strconv.Quote(x.string()) }
   244  func (x int64Val) ExactString() string   { return x.String() }
   245  func (x intVal) ExactString() string     { return x.String() }
   246  
   247  func (x ratVal) ExactString() string {
   248  	r := x.val
   249  	if r.IsInt() {
   250  		return r.Num().String()
   251  	}
   252  	return r.String()
   253  }
   254  
   255  func (x floatVal) ExactString() string { return x.val.Text('p', 0) }
   256  
   257  func (x complexVal) ExactString() string {
   258  	return fmt.Sprintf("(%s + %si)", x.re.ExactString(), x.im.ExactString())
   259  }
   260  
   261  func (unknownVal) implementsValue() {}
   262  func (boolVal) implementsValue()    {}
   263  func (*stringVal) implementsValue() {}
   264  func (int64Val) implementsValue()   {}
   265  func (ratVal) implementsValue()     {}
   266  func (intVal) implementsValue()     {}
   267  func (floatVal) implementsValue()   {}
   268  func (complexVal) implementsValue() {}
   269  
   270  func newInt() *big.Int     { return new(big.Int) }
   271  func newRat() *big.Rat     { return new(big.Rat) }
   272  func newFloat() *big.Float { return new(big.Float).SetPrec(prec) }
   273  
   274  func i64toi(x int64Val) intVal   { return intVal{newInt().SetInt64(int64(x))} }
   275  func i64tor(x int64Val) ratVal   { return ratVal{newRat().SetInt64(int64(x))} }
   276  func i64tof(x int64Val) floatVal { return floatVal{newFloat().SetInt64(int64(x))} }
   277  func itor(x intVal) ratVal       { return ratVal{newRat().SetInt(x.val)} }
   278  func itof(x intVal) floatVal     { return floatVal{newFloat().SetInt(x.val)} }
   279  func rtof(x ratVal) floatVal     { return floatVal{newFloat().SetRat(x.val)} }
   280  func vtoc(x Value) complexVal    { return complexVal{x, int64Val(0)} }
   281  
   282  func makeInt(x *big.Int) Value {
   283  	if x.IsInt64() {
   284  		return int64Val(x.Int64())
   285  	}
   286  	return intVal{x}
   287  }
   288  
   289  func makeRat(x *big.Rat) Value {
   290  	a := x.Num()
   291  	b := x.Denom()
   292  	if smallInt(a) && smallInt(b) {
   293  		// ok to remain fraction
   294  		return ratVal{x}
   295  	}
   296  	// components too large => switch to float
   297  	return floatVal{newFloat().SetRat(x)}
   298  }
   299  
   300  var floatVal0 = floatVal{newFloat()}
   301  
   302  func makeFloat(x *big.Float) Value {
   303  	// convert -0
   304  	if x.Sign() == 0 {
   305  		return floatVal0
   306  	}
   307  	if x.IsInf() {
   308  		return unknownVal{}
   309  	}
   310  	// No attempt is made to "go back" to ratVal, even if possible,
   311  	// to avoid providing the illusion of a mathematically exact
   312  	// representation.
   313  	return floatVal{x}
   314  }
   315  
   316  func makeComplex(re, im Value) Value {
   317  	if re.Kind() == Unknown || im.Kind() == Unknown {
   318  		return unknownVal{}
   319  	}
   320  	return complexVal{re, im}
   321  }
   322  
   323  func makeFloatFromLiteral(lit string) Value {
   324  	if f, ok := newFloat().SetString(lit); ok {
   325  		if smallFloat(f) {
   326  			// ok to use rationals
   327  			if f.Sign() == 0 {
   328  				// Issue 20228: If the float underflowed to zero, parse just "0".
   329  				// Otherwise, lit might contain a value with a large negative exponent,
   330  				// such as -6e-1886451601. As a float, that will underflow to 0,
   331  				// but it'll take forever to parse as a Rat.
   332  				lit = "0"
   333  			}
   334  			if r, ok := newRat().SetString(lit); ok {
   335  				return ratVal{r}
   336  			}
   337  		}
   338  		// otherwise use floats
   339  		return makeFloat(f)
   340  	}
   341  	return nil
   342  }
   343  
   344  // Permit fractions with component sizes up to maxExp
   345  // before switching to using floating-point numbers.
   346  const maxExp = 4 << 10
   347  
   348  // smallInt reports whether x would lead to "reasonably"-sized fraction
   349  // if converted to a *big.Rat.
   350  func smallInt(x *big.Int) bool {
   351  	return x.BitLen() < maxExp
   352  }
   353  
   354  // smallFloat64 reports whether x would lead to "reasonably"-sized fraction
   355  // if converted to a *big.Rat.
   356  func smallFloat64(x float64) bool {
   357  	if math.IsInf(x, 0) {
   358  		return false
   359  	}
   360  	_, e := math.Frexp(x)
   361  	return -maxExp < e && e < maxExp
   362  }
   363  
   364  // smallFloat reports whether x would lead to "reasonably"-sized fraction
   365  // if converted to a *big.Rat.
   366  func smallFloat(x *big.Float) bool {
   367  	if x.IsInf() {
   368  		return false
   369  	}
   370  	e := x.MantExp(nil)
   371  	return -maxExp < e && e < maxExp
   372  }
   373  
   374  // ----------------------------------------------------------------------------
   375  // Factories
   376  
   377  // MakeUnknown returns the Unknown value.
   378  func MakeUnknown() Value { return unknownVal{} }
   379  
   380  // MakeBool returns the Bool value for b.
   381  func MakeBool(b bool) Value { return boolVal(b) }
   382  
   383  // MakeString returns the String value for s.
   384  func MakeString(s string) Value { return &stringVal{s: s} }
   385  
   386  // MakeInt64 returns the Int value for x.
   387  func MakeInt64(x int64) Value { return int64Val(x) }
   388  
   389  // MakeUint64 returns the Int value for x.
   390  func MakeUint64(x uint64) Value {
   391  	if x < 1<<63 {
   392  		return int64Val(int64(x))
   393  	}
   394  	return intVal{newInt().SetUint64(x)}
   395  }
   396  
   397  // MakeFloat64 returns the Float value for x.
   398  // If x is -0.0, the result is 0.0.
   399  // If x is not finite, the result is an Unknown.
   400  func MakeFloat64(x float64) Value {
   401  	if math.IsInf(x, 0) || math.IsNaN(x) {
   402  		return unknownVal{}
   403  	}
   404  	if smallFloat64(x) {
   405  		return ratVal{newRat().SetFloat64(x + 0)} // convert -0 to 0
   406  	}
   407  	return floatVal{newFloat().SetFloat64(x + 0)}
   408  }
   409  
   410  // MakeFromLiteral returns the corresponding integer, floating-point,
   411  // imaginary, character, or string value for a Go literal string. The
   412  // tok value must be one of token.INT, token.FLOAT, token.IMAG,
   413  // token.CHAR, or token.STRING. The final argument must be zero.
   414  // If the literal string syntax is invalid, the result is an Unknown.
   415  func MakeFromLiteral(lit string, tok token.Token, zero uint) Value {
   416  	if zero != 0 {
   417  		panic("MakeFromLiteral called with non-zero last argument")
   418  	}
   419  
   420  	switch tok {
   421  	case token.INT:
   422  		if x, err := strconv.ParseInt(lit, 0, 64); err == nil {
   423  			return int64Val(x)
   424  		}
   425  		if x, ok := newInt().SetString(lit, 0); ok {
   426  			return intVal{x}
   427  		}
   428  
   429  	case token.FLOAT:
   430  		if x := makeFloatFromLiteral(lit); x != nil {
   431  			return x
   432  		}
   433  
   434  	case token.IMAG:
   435  		if n := len(lit); n > 0 && lit[n-1] == 'i' {
   436  			if im := makeFloatFromLiteral(lit[:n-1]); im != nil {
   437  				return makeComplex(int64Val(0), im)
   438  			}
   439  		}
   440  
   441  	case token.CHAR:
   442  		if n := len(lit); n >= 2 {
   443  			if code, _, _, err := strconv.UnquoteChar(lit[1:n-1], '\''); err == nil {
   444  				return MakeInt64(int64(code))
   445  			}
   446  		}
   447  
   448  	case token.STRING:
   449  		if s, err := strconv.Unquote(lit); err == nil {
   450  			return MakeString(s)
   451  		}
   452  
   453  	default:
   454  		panic(fmt.Sprintf("%v is not a valid token", tok))
   455  	}
   456  
   457  	return unknownVal{}
   458  }
   459  
   460  // ----------------------------------------------------------------------------
   461  // Accessors
   462  //
   463  // For unknown arguments the result is the zero value for the respective
   464  // accessor type, except for Sign, where the result is 1.
   465  
   466  // BoolVal returns the Go boolean value of x, which must be a Bool or an Unknown.
   467  // If x is Unknown, the result is false.
   468  func BoolVal(x Value) bool {
   469  	switch x := x.(type) {
   470  	case boolVal:
   471  		return bool(x)
   472  	case unknownVal:
   473  		return false
   474  	default:
   475  		panic(fmt.Sprintf("%v not a Bool", x))
   476  	}
   477  }
   478  
   479  // StringVal returns the Go string value of x, which must be a String or an Unknown.
   480  // If x is Unknown, the result is "".
   481  func StringVal(x Value) string {
   482  	switch x := x.(type) {
   483  	case *stringVal:
   484  		return x.string()
   485  	case unknownVal:
   486  		return ""
   487  	default:
   488  		panic(fmt.Sprintf("%v not a String", x))
   489  	}
   490  }
   491  
   492  // Int64Val returns the Go int64 value of x and whether the result is exact;
   493  // x must be an Int or an Unknown. If the result is not exact, its value is undefined.
   494  // If x is Unknown, the result is (0, false).
   495  func Int64Val(x Value) (int64, bool) {
   496  	switch x := x.(type) {
   497  	case int64Val:
   498  		return int64(x), true
   499  	case intVal:
   500  		return x.val.Int64(), false // not an int64Val and thus not exact
   501  	case unknownVal:
   502  		return 0, false
   503  	default:
   504  		panic(fmt.Sprintf("%v not an Int", x))
   505  	}
   506  }
   507  
   508  // Uint64Val returns the Go uint64 value of x and whether the result is exact;
   509  // x must be an Int or an Unknown. If the result is not exact, its value is undefined.
   510  // If x is Unknown, the result is (0, false).
   511  func Uint64Val(x Value) (uint64, bool) {
   512  	switch x := x.(type) {
   513  	case int64Val:
   514  		return uint64(x), x >= 0
   515  	case intVal:
   516  		return x.val.Uint64(), x.val.IsUint64()
   517  	case unknownVal:
   518  		return 0, false
   519  	default:
   520  		panic(fmt.Sprintf("%v not an Int", x))
   521  	}
   522  }
   523  
   524  // Float32Val is like Float64Val but for float32 instead of float64.
   525  func Float32Val(x Value) (float32, bool) {
   526  	switch x := x.(type) {
   527  	case int64Val:
   528  		f := float32(x)
   529  		return f, int64Val(f) == x
   530  	case intVal:
   531  		f, acc := newFloat().SetInt(x.val).Float32()
   532  		return f, acc == big.Exact
   533  	case ratVal:
   534  		return x.val.Float32()
   535  	case floatVal:
   536  		f, acc := x.val.Float32()
   537  		return f, acc == big.Exact
   538  	case unknownVal:
   539  		return 0, false
   540  	default:
   541  		panic(fmt.Sprintf("%v not a Float", x))
   542  	}
   543  }
   544  
   545  // Float64Val returns the nearest Go float64 value of x and whether the result is exact;
   546  // x must be numeric or an Unknown, but not Complex. For values too small (too close to 0)
   547  // to represent as float64, Float64Val silently underflows to 0. The result sign always
   548  // matches the sign of x, even for 0.
   549  // If x is Unknown, the result is (0, false).
   550  func Float64Val(x Value) (float64, bool) {
   551  	switch x := x.(type) {
   552  	case int64Val:
   553  		f := float64(int64(x))
   554  		return f, int64Val(f) == x
   555  	case intVal:
   556  		f, acc := newFloat().SetInt(x.val).Float64()
   557  		return f, acc == big.Exact
   558  	case ratVal:
   559  		return x.val.Float64()
   560  	case floatVal:
   561  		f, acc := x.val.Float64()
   562  		return f, acc == big.Exact
   563  	case unknownVal:
   564  		return 0, false
   565  	default:
   566  		panic(fmt.Sprintf("%v not a Float", x))
   567  	}
   568  }
   569  
   570  // Val returns the underlying value for a given constant. Since it returns an
   571  // interface, it is up to the caller to type assert the result to the expected
   572  // type. The possible dynamic return types are:
   573  //
   574  //    x Kind             type of result
   575  //    -----------------------------------------
   576  //    Bool               bool
   577  //    String             string
   578  //    Int                int64 or *big.Int
   579  //    Float              *big.Float or *big.Rat
   580  //    everything else    nil
   581  //
   582  func Val(x Value) any {
   583  	switch x := x.(type) {
   584  	case boolVal:
   585  		return bool(x)
   586  	case *stringVal:
   587  		return x.string()
   588  	case int64Val:
   589  		return int64(x)
   590  	case intVal:
   591  		return x.val
   592  	case ratVal:
   593  		return x.val
   594  	case floatVal:
   595  		return x.val
   596  	default:
   597  		return nil
   598  	}
   599  }
   600  
   601  // Make returns the Value for x.
   602  //
   603  //    type of x        result Kind
   604  //    ----------------------------
   605  //    bool             Bool
   606  //    string           String
   607  //    int64            Int
   608  //    *big.Int         Int
   609  //    *big.Float       Float
   610  //    *big.Rat         Float
   611  //    anything else    Unknown
   612  //
   613  func Make(x any) Value {
   614  	switch x := x.(type) {
   615  	case bool:
   616  		return boolVal(x)
   617  	case string:
   618  		return &stringVal{s: x}
   619  	case int64:
   620  		return int64Val(x)
   621  	case *big.Int:
   622  		return makeInt(x)
   623  	case *big.Rat:
   624  		return makeRat(x)
   625  	case *big.Float:
   626  		return makeFloat(x)
   627  	default:
   628  		return unknownVal{}
   629  	}
   630  }
   631  
   632  // BitLen returns the number of bits required to represent
   633  // the absolute value x in binary representation; x must be an Int or an Unknown.
   634  // If x is Unknown, the result is 0.
   635  func BitLen(x Value) int {
   636  	switch x := x.(type) {
   637  	case int64Val:
   638  		u := uint64(x)
   639  		if x < 0 {
   640  			u = uint64(-x)
   641  		}
   642  		return 64 - bits.LeadingZeros64(u)
   643  	case intVal:
   644  		return x.val.BitLen()
   645  	case unknownVal:
   646  		return 0
   647  	default:
   648  		panic(fmt.Sprintf("%v not an Int", x))
   649  	}
   650  }
   651  
   652  // Sign returns -1, 0, or 1 depending on whether x < 0, x == 0, or x > 0;
   653  // x must be numeric or Unknown. For complex values x, the sign is 0 if x == 0,
   654  // otherwise it is != 0. If x is Unknown, the result is 1.
   655  func Sign(x Value) int {
   656  	switch x := x.(type) {
   657  	case int64Val:
   658  		switch {
   659  		case x < 0:
   660  			return -1
   661  		case x > 0:
   662  			return 1
   663  		}
   664  		return 0
   665  	case intVal:
   666  		return x.val.Sign()
   667  	case ratVal:
   668  		return x.val.Sign()
   669  	case floatVal:
   670  		return x.val.Sign()
   671  	case complexVal:
   672  		return Sign(x.re) | Sign(x.im)
   673  	case unknownVal:
   674  		return 1 // avoid spurious division by zero errors
   675  	default:
   676  		panic(fmt.Sprintf("%v not numeric", x))
   677  	}
   678  }
   679  
   680  // ----------------------------------------------------------------------------
   681  // Support for assembling/disassembling numeric values
   682  
   683  const (
   684  	// Compute the size of a Word in bytes.
   685  	_m       = ^big.Word(0)
   686  	_log     = _m>>8&1 + _m>>16&1 + _m>>32&1
   687  	wordSize = 1 << _log
   688  )
   689  
   690  // Bytes returns the bytes for the absolute value of x in little-
   691  // endian binary representation; x must be an Int.
   692  func Bytes(x Value) []byte {
   693  	var t intVal
   694  	switch x := x.(type) {
   695  	case int64Val:
   696  		t = i64toi(x)
   697  	case intVal:
   698  		t = x
   699  	default:
   700  		panic(fmt.Sprintf("%v not an Int", x))
   701  	}
   702  
   703  	words := t.val.Bits()
   704  	bytes := make([]byte, len(words)*wordSize)
   705  
   706  	i := 0
   707  	for _, w := range words {
   708  		for j := 0; j < wordSize; j++ {
   709  			bytes[i] = byte(w)
   710  			w >>= 8
   711  			i++
   712  		}
   713  	}
   714  	// remove leading 0's
   715  	for i > 0 && bytes[i-1] == 0 {
   716  		i--
   717  	}
   718  
   719  	return bytes[:i]
   720  }
   721  
   722  // MakeFromBytes returns the Int value given the bytes of its little-endian
   723  // binary representation. An empty byte slice argument represents 0.
   724  func MakeFromBytes(bytes []byte) Value {
   725  	words := make([]big.Word, (len(bytes)+(wordSize-1))/wordSize)
   726  
   727  	i := 0
   728  	var w big.Word
   729  	var s uint
   730  	for _, b := range bytes {
   731  		w |= big.Word(b) << s
   732  		if s += 8; s == wordSize*8 {
   733  			words[i] = w
   734  			i++
   735  			w = 0
   736  			s = 0
   737  		}
   738  	}
   739  	// store last word
   740  	if i < len(words) {
   741  		words[i] = w
   742  		i++
   743  	}
   744  	// remove leading 0's
   745  	for i > 0 && words[i-1] == 0 {
   746  		i--
   747  	}
   748  
   749  	return makeInt(newInt().SetBits(words[:i]))
   750  }
   751  
   752  // Num returns the numerator of x; x must be Int, Float, or Unknown.
   753  // If x is Unknown, or if it is too large or small to represent as a
   754  // fraction, the result is Unknown. Otherwise the result is an Int
   755  // with the same sign as x.
   756  func Num(x Value) Value {
   757  	switch x := x.(type) {
   758  	case int64Val, intVal:
   759  		return x
   760  	case ratVal:
   761  		return makeInt(x.val.Num())
   762  	case floatVal:
   763  		if smallFloat(x.val) {
   764  			r, _ := x.val.Rat(nil)
   765  			return makeInt(r.Num())
   766  		}
   767  	case unknownVal:
   768  		break
   769  	default:
   770  		panic(fmt.Sprintf("%v not Int or Float", x))
   771  	}
   772  	return unknownVal{}
   773  }
   774  
   775  // Denom returns the denominator of x; x must be Int, Float, or Unknown.
   776  // If x is Unknown, or if it is too large or small to represent as a
   777  // fraction, the result is Unknown. Otherwise the result is an Int >= 1.
   778  func Denom(x Value) Value {
   779  	switch x := x.(type) {
   780  	case int64Val, intVal:
   781  		return int64Val(1)
   782  	case ratVal:
   783  		return makeInt(x.val.Denom())
   784  	case floatVal:
   785  		if smallFloat(x.val) {
   786  			r, _ := x.val.Rat(nil)
   787  			return makeInt(r.Denom())
   788  		}
   789  	case unknownVal:
   790  		break
   791  	default:
   792  		panic(fmt.Sprintf("%v not Int or Float", x))
   793  	}
   794  	return unknownVal{}
   795  }
   796  
   797  // MakeImag returns the Complex value x*i;
   798  // x must be Int, Float, or Unknown.
   799  // If x is Unknown, the result is Unknown.
   800  func MakeImag(x Value) Value {
   801  	switch x.(type) {
   802  	case unknownVal:
   803  		return x
   804  	case int64Val, intVal, ratVal, floatVal:
   805  		return makeComplex(int64Val(0), x)
   806  	default:
   807  		panic(fmt.Sprintf("%v not Int or Float", x))
   808  	}
   809  }
   810  
   811  // Real returns the real part of x, which must be a numeric or unknown value.
   812  // If x is Unknown, the result is Unknown.
   813  func Real(x Value) Value {
   814  	switch x := x.(type) {
   815  	case unknownVal, int64Val, intVal, ratVal, floatVal:
   816  		return x
   817  	case complexVal:
   818  		return x.re
   819  	default:
   820  		panic(fmt.Sprintf("%v not numeric", x))
   821  	}
   822  }
   823  
   824  // Imag returns the imaginary part of x, which must be a numeric or unknown value.
   825  // If x is Unknown, the result is Unknown.
   826  func Imag(x Value) Value {
   827  	switch x := x.(type) {
   828  	case unknownVal:
   829  		return x
   830  	case int64Val, intVal, ratVal, floatVal:
   831  		return int64Val(0)
   832  	case complexVal:
   833  		return x.im
   834  	default:
   835  		panic(fmt.Sprintf("%v not numeric", x))
   836  	}
   837  }
   838  
   839  // ----------------------------------------------------------------------------
   840  // Numeric conversions
   841  
   842  // ToInt converts x to an Int value if x is representable as an Int.
   843  // Otherwise it returns an Unknown.
   844  func ToInt(x Value) Value {
   845  	switch x := x.(type) {
   846  	case int64Val, intVal:
   847  		return x
   848  
   849  	case ratVal:
   850  		if x.val.IsInt() {
   851  			return makeInt(x.val.Num())
   852  		}
   853  
   854  	case floatVal:
   855  		// avoid creation of huge integers
   856  		// (Existing tests require permitting exponents of at least 1024;
   857  		// allow any value that would also be permissible as a fraction.)
   858  		if smallFloat(x.val) {
   859  			i := newInt()
   860  			if _, acc := x.val.Int(i); acc == big.Exact {
   861  				return makeInt(i)
   862  			}
   863  
   864  			// If we can get an integer by rounding up or down,
   865  			// assume x is not an integer because of rounding
   866  			// errors in prior computations.
   867  
   868  			const delta = 4 // a small number of bits > 0
   869  			var t big.Float
   870  			t.SetPrec(prec - delta)
   871  
   872  			// try rounding down a little
   873  			t.SetMode(big.ToZero)
   874  			t.Set(x.val)
   875  			if _, acc := t.Int(i); acc == big.Exact {
   876  				return makeInt(i)
   877  			}
   878  
   879  			// try rounding up a little
   880  			t.SetMode(big.AwayFromZero)
   881  			t.Set(x.val)
   882  			if _, acc := t.Int(i); acc == big.Exact {
   883  				return makeInt(i)
   884  			}
   885  		}
   886  
   887  	case complexVal:
   888  		if re := ToFloat(x); re.Kind() == Float {
   889  			return ToInt(re)
   890  		}
   891  	}
   892  
   893  	return unknownVal{}
   894  }
   895  
   896  // ToFloat converts x to a Float value if x is representable as a Float.
   897  // Otherwise it returns an Unknown.
   898  func ToFloat(x Value) Value {
   899  	switch x := x.(type) {
   900  	case int64Val:
   901  		return i64tor(x) // x is always a small int
   902  	case intVal:
   903  		if smallInt(x.val) {
   904  			return itor(x)
   905  		}
   906  		return itof(x)
   907  	case ratVal, floatVal:
   908  		return x
   909  	case complexVal:
   910  		if Sign(x.im) == 0 {
   911  			return ToFloat(x.re)
   912  		}
   913  	}
   914  	return unknownVal{}
   915  }
   916  
   917  // ToComplex converts x to a Complex value if x is representable as a Complex.
   918  // Otherwise it returns an Unknown.
   919  func ToComplex(x Value) Value {
   920  	switch x := x.(type) {
   921  	case int64Val, intVal, ratVal, floatVal:
   922  		return vtoc(x)
   923  	case complexVal:
   924  		return x
   925  	}
   926  	return unknownVal{}
   927  }
   928  
   929  // ----------------------------------------------------------------------------
   930  // Operations
   931  
   932  // is32bit reports whether x can be represented using 32 bits.
   933  func is32bit(x int64) bool {
   934  	const s = 32
   935  	return -1<<(s-1) <= x && x <= 1<<(s-1)-1
   936  }
   937  
   938  // is63bit reports whether x can be represented using 63 bits.
   939  func is63bit(x int64) bool {
   940  	const s = 63
   941  	return -1<<(s-1) <= x && x <= 1<<(s-1)-1
   942  }
   943  
   944  // UnaryOp returns the result of the unary expression op y.
   945  // The operation must be defined for the operand.
   946  // If prec > 0 it specifies the ^ (xor) result size in bits.
   947  // If y is Unknown, the result is Unknown.
   948  //
   949  func UnaryOp(op token.Token, y Value, prec uint) Value {
   950  	switch op {
   951  	case token.ADD:
   952  		switch y.(type) {
   953  		case unknownVal, int64Val, intVal, ratVal, floatVal, complexVal:
   954  			return y
   955  		}
   956  
   957  	case token.SUB:
   958  		switch y := y.(type) {
   959  		case unknownVal:
   960  			return y
   961  		case int64Val:
   962  			if z := -y; z != y {
   963  				return z // no overflow
   964  			}
   965  			return makeInt(newInt().Neg(big.NewInt(int64(y))))
   966  		case intVal:
   967  			return makeInt(newInt().Neg(y.val))
   968  		case ratVal:
   969  			return makeRat(newRat().Neg(y.val))
   970  		case floatVal:
   971  			return makeFloat(newFloat().Neg(y.val))
   972  		case complexVal:
   973  			re := UnaryOp(token.SUB, y.re, 0)
   974  			im := UnaryOp(token.SUB, y.im, 0)
   975  			return makeComplex(re, im)
   976  		}
   977  
   978  	case token.XOR:
   979  		z := newInt()
   980  		switch y := y.(type) {
   981  		case unknownVal:
   982  			return y
   983  		case int64Val:
   984  			z.Not(big.NewInt(int64(y)))
   985  		case intVal:
   986  			z.Not(y.val)
   987  		default:
   988  			goto Error
   989  		}
   990  		// For unsigned types, the result will be negative and
   991  		// thus "too large": We must limit the result precision
   992  		// to the type's precision.
   993  		if prec > 0 {
   994  			z.AndNot(z, newInt().Lsh(big.NewInt(-1), prec)) // z &^= (-1)<<prec
   995  		}
   996  		return makeInt(z)
   997  
   998  	case token.NOT:
   999  		switch y := y.(type) {
  1000  		case unknownVal:
  1001  			return y
  1002  		case boolVal:
  1003  			return !y
  1004  		}
  1005  	}
  1006  
  1007  Error:
  1008  	panic(fmt.Sprintf("invalid unary operation %s%v", op, y))
  1009  }
  1010  
  1011  func ord(x Value) int {
  1012  	switch x.(type) {
  1013  	default:
  1014  		// force invalid value into "x position" in match
  1015  		// (don't panic here so that callers can provide a better error message)
  1016  		return -1
  1017  	case unknownVal:
  1018  		return 0
  1019  	case boolVal, *stringVal:
  1020  		return 1
  1021  	case int64Val:
  1022  		return 2
  1023  	case intVal:
  1024  		return 3
  1025  	case ratVal:
  1026  		return 4
  1027  	case floatVal:
  1028  		return 5
  1029  	case complexVal:
  1030  		return 6
  1031  	}
  1032  }
  1033  
  1034  // match returns the matching representation (same type) with the
  1035  // smallest complexity for two values x and y. If one of them is
  1036  // numeric, both of them must be numeric. If one of them is Unknown
  1037  // or invalid (say, nil) both results are that value.
  1038  //
  1039  func match(x, y Value) (_, _ Value) {
  1040  	switch ox, oy := ord(x), ord(y); {
  1041  	case ox < oy:
  1042  		x, y = match0(x, y)
  1043  	case ox > oy:
  1044  		y, x = match0(y, x)
  1045  	}
  1046  	return x, y
  1047  }
  1048  
  1049  // match0 must only be called by match.
  1050  // Invariant: ord(x) < ord(y)
  1051  func match0(x, y Value) (_, _ Value) {
  1052  	// Prefer to return the original x and y arguments when possible,
  1053  	// to avoid unnecessary heap allocations.
  1054  
  1055  	switch y.(type) {
  1056  	case intVal:
  1057  		switch x1 := x.(type) {
  1058  		case int64Val:
  1059  			return i64toi(x1), y
  1060  		}
  1061  	case ratVal:
  1062  		switch x1 := x.(type) {
  1063  		case int64Val:
  1064  			return i64tor(x1), y
  1065  		case intVal:
  1066  			return itor(x1), y
  1067  		}
  1068  	case floatVal:
  1069  		switch x1 := x.(type) {
  1070  		case int64Val:
  1071  			return i64tof(x1), y
  1072  		case intVal:
  1073  			return itof(x1), y
  1074  		case ratVal:
  1075  			return rtof(x1), y
  1076  		}
  1077  	case complexVal:
  1078  		return vtoc(x), y
  1079  	}
  1080  
  1081  	// force unknown and invalid values into "x position" in callers of match
  1082  	// (don't panic here so that callers can provide a better error message)
  1083  	return x, x
  1084  }
  1085  
  1086  // BinaryOp returns the result of the binary expression x op y.
  1087  // The operation must be defined for the operands. If one of the
  1088  // operands is Unknown, the result is Unknown.
  1089  // BinaryOp doesn't handle comparisons or shifts; use Compare
  1090  // or Shift instead.
  1091  //
  1092  // To force integer division of Int operands, use op == token.QUO_ASSIGN
  1093  // instead of token.QUO; the result is guaranteed to be Int in this case.
  1094  // Division by zero leads to a run-time panic.
  1095  //
  1096  func BinaryOp(x_ Value, op token.Token, y_ Value) Value {
  1097  	x, y := match(x_, y_)
  1098  
  1099  	switch x := x.(type) {
  1100  	case unknownVal:
  1101  		return x
  1102  
  1103  	case boolVal:
  1104  		y := y.(boolVal)
  1105  		switch op {
  1106  		case token.LAND:
  1107  			return x && y
  1108  		case token.LOR:
  1109  			return x || y
  1110  		}
  1111  
  1112  	case int64Val:
  1113  		a := int64(x)
  1114  		b := int64(y.(int64Val))
  1115  		var c int64
  1116  		switch op {
  1117  		case token.ADD:
  1118  			if !is63bit(a) || !is63bit(b) {
  1119  				return makeInt(newInt().Add(big.NewInt(a), big.NewInt(b)))
  1120  			}
  1121  			c = a + b
  1122  		case token.SUB:
  1123  			if !is63bit(a) || !is63bit(b) {
  1124  				return makeInt(newInt().Sub(big.NewInt(a), big.NewInt(b)))
  1125  			}
  1126  			c = a - b
  1127  		case token.MUL:
  1128  			if !is32bit(a) || !is32bit(b) {
  1129  				return makeInt(newInt().Mul(big.NewInt(a), big.NewInt(b)))
  1130  			}
  1131  			c = a * b
  1132  		case token.QUO:
  1133  			return makeRat(big.NewRat(a, b))
  1134  		case token.QUO_ASSIGN: // force integer division
  1135  			c = a / b
  1136  		case token.REM:
  1137  			c = a % b
  1138  		case token.AND:
  1139  			c = a & b
  1140  		case token.OR:
  1141  			c = a | b
  1142  		case token.XOR:
  1143  			c = a ^ b
  1144  		case token.AND_NOT:
  1145  			c = a &^ b
  1146  		default:
  1147  			goto Error
  1148  		}
  1149  		return int64Val(c)
  1150  
  1151  	case intVal:
  1152  		a := x.val
  1153  		b := y.(intVal).val
  1154  		c := newInt()
  1155  		switch op {
  1156  		case token.ADD:
  1157  			c.Add(a, b)
  1158  		case token.SUB:
  1159  			c.Sub(a, b)
  1160  		case token.MUL:
  1161  			c.Mul(a, b)
  1162  		case token.QUO:
  1163  			return makeRat(newRat().SetFrac(a, b))
  1164  		case token.QUO_ASSIGN: // force integer division
  1165  			c.Quo(a, b)
  1166  		case token.REM:
  1167  			c.Rem(a, b)
  1168  		case token.AND:
  1169  			c.And(a, b)
  1170  		case token.OR:
  1171  			c.Or(a, b)
  1172  		case token.XOR:
  1173  			c.Xor(a, b)
  1174  		case token.AND_NOT:
  1175  			c.AndNot(a, b)
  1176  		default:
  1177  			goto Error
  1178  		}
  1179  		return makeInt(c)
  1180  
  1181  	case ratVal:
  1182  		a := x.val
  1183  		b := y.(ratVal).val
  1184  		c := newRat()
  1185  		switch op {
  1186  		case token.ADD:
  1187  			c.Add(a, b)
  1188  		case token.SUB:
  1189  			c.Sub(a, b)
  1190  		case token.MUL:
  1191  			c.Mul(a, b)
  1192  		case token.QUO:
  1193  			c.Quo(a, b)
  1194  		default:
  1195  			goto Error
  1196  		}
  1197  		return makeRat(c)
  1198  
  1199  	case floatVal:
  1200  		a := x.val
  1201  		b := y.(floatVal).val
  1202  		c := newFloat()
  1203  		switch op {
  1204  		case token.ADD:
  1205  			c.Add(a, b)
  1206  		case token.SUB:
  1207  			c.Sub(a, b)
  1208  		case token.MUL:
  1209  			c.Mul(a, b)
  1210  		case token.QUO:
  1211  			c.Quo(a, b)
  1212  		default:
  1213  			goto Error
  1214  		}
  1215  		return makeFloat(c)
  1216  
  1217  	case complexVal:
  1218  		y := y.(complexVal)
  1219  		a, b := x.re, x.im
  1220  		c, d := y.re, y.im
  1221  		var re, im Value
  1222  		switch op {
  1223  		case token.ADD:
  1224  			// (a+c) + i(b+d)
  1225  			re = add(a, c)
  1226  			im = add(b, d)
  1227  		case token.SUB:
  1228  			// (a-c) + i(b-d)
  1229  			re = sub(a, c)
  1230  			im = sub(b, d)
  1231  		case token.MUL:
  1232  			// (ac-bd) + i(bc+ad)
  1233  			ac := mul(a, c)
  1234  			bd := mul(b, d)
  1235  			bc := mul(b, c)
  1236  			ad := mul(a, d)
  1237  			re = sub(ac, bd)
  1238  			im = add(bc, ad)
  1239  		case token.QUO:
  1240  			// (ac+bd)/s + i(bc-ad)/s, with s = cc + dd
  1241  			ac := mul(a, c)
  1242  			bd := mul(b, d)
  1243  			bc := mul(b, c)
  1244  			ad := mul(a, d)
  1245  			cc := mul(c, c)
  1246  			dd := mul(d, d)
  1247  			s := add(cc, dd)
  1248  			re = add(ac, bd)
  1249  			re = quo(re, s)
  1250  			im = sub(bc, ad)
  1251  			im = quo(im, s)
  1252  		default:
  1253  			goto Error
  1254  		}
  1255  		return makeComplex(re, im)
  1256  
  1257  	case *stringVal:
  1258  		if op == token.ADD {
  1259  			return &stringVal{l: x, r: y.(*stringVal)}
  1260  		}
  1261  	}
  1262  
  1263  Error:
  1264  	panic(fmt.Sprintf("invalid binary operation %v %s %v", x_, op, y_))
  1265  }
  1266  
  1267  func add(x, y Value) Value { return BinaryOp(x, token.ADD, y) }
  1268  func sub(x, y Value) Value { return BinaryOp(x, token.SUB, y) }
  1269  func mul(x, y Value) Value { return BinaryOp(x, token.MUL, y) }
  1270  func quo(x, y Value) Value { return BinaryOp(x, token.QUO, y) }
  1271  
  1272  // Shift returns the result of the shift expression x op s
  1273  // with op == token.SHL or token.SHR (<< or >>). x must be
  1274  // an Int or an Unknown. If x is Unknown, the result is x.
  1275  //
  1276  func Shift(x Value, op token.Token, s uint) Value {
  1277  	switch x := x.(type) {
  1278  	case unknownVal:
  1279  		return x
  1280  
  1281  	case int64Val:
  1282  		if s == 0 {
  1283  			return x
  1284  		}
  1285  		switch op {
  1286  		case token.SHL:
  1287  			z := i64toi(x).val
  1288  			return makeInt(z.Lsh(z, s))
  1289  		case token.SHR:
  1290  			return x >> s
  1291  		}
  1292  
  1293  	case intVal:
  1294  		if s == 0 {
  1295  			return x
  1296  		}
  1297  		z := newInt()
  1298  		switch op {
  1299  		case token.SHL:
  1300  			return makeInt(z.Lsh(x.val, s))
  1301  		case token.SHR:
  1302  			return makeInt(z.Rsh(x.val, s))
  1303  		}
  1304  	}
  1305  
  1306  	panic(fmt.Sprintf("invalid shift %v %s %d", x, op, s))
  1307  }
  1308  
  1309  func cmpZero(x int, op token.Token) bool {
  1310  	switch op {
  1311  	case token.EQL:
  1312  		return x == 0
  1313  	case token.NEQ:
  1314  		return x != 0
  1315  	case token.LSS:
  1316  		return x < 0
  1317  	case token.LEQ:
  1318  		return x <= 0
  1319  	case token.GTR:
  1320  		return x > 0
  1321  	case token.GEQ:
  1322  		return x >= 0
  1323  	}
  1324  	panic(fmt.Sprintf("invalid comparison %v %s 0", x, op))
  1325  }
  1326  
  1327  // Compare returns the result of the comparison x op y.
  1328  // The comparison must be defined for the operands.
  1329  // If one of the operands is Unknown, the result is
  1330  // false.
  1331  //
  1332  func Compare(x_ Value, op token.Token, y_ Value) bool {
  1333  	x, y := match(x_, y_)
  1334  
  1335  	switch x := x.(type) {
  1336  	case unknownVal:
  1337  		return false
  1338  
  1339  	case boolVal:
  1340  		y := y.(boolVal)
  1341  		switch op {
  1342  		case token.EQL:
  1343  			return x == y
  1344  		case token.NEQ:
  1345  			return x != y
  1346  		}
  1347  
  1348  	case int64Val:
  1349  		y := y.(int64Val)
  1350  		switch op {
  1351  		case token.EQL:
  1352  			return x == y
  1353  		case token.NEQ:
  1354  			return x != y
  1355  		case token.LSS:
  1356  			return x < y
  1357  		case token.LEQ:
  1358  			return x <= y
  1359  		case token.GTR:
  1360  			return x > y
  1361  		case token.GEQ:
  1362  			return x >= y
  1363  		}
  1364  
  1365  	case intVal:
  1366  		return cmpZero(x.val.Cmp(y.(intVal).val), op)
  1367  
  1368  	case ratVal:
  1369  		return cmpZero(x.val.Cmp(y.(ratVal).val), op)
  1370  
  1371  	case floatVal:
  1372  		return cmpZero(x.val.Cmp(y.(floatVal).val), op)
  1373  
  1374  	case complexVal:
  1375  		y := y.(complexVal)
  1376  		re := Compare(x.re, token.EQL, y.re)
  1377  		im := Compare(x.im, token.EQL, y.im)
  1378  		switch op {
  1379  		case token.EQL:
  1380  			return re && im
  1381  		case token.NEQ:
  1382  			return !re || !im
  1383  		}
  1384  
  1385  	case *stringVal:
  1386  		xs := x.string()
  1387  		ys := y.(*stringVal).string()
  1388  		switch op {
  1389  		case token.EQL:
  1390  			return xs == ys
  1391  		case token.NEQ:
  1392  			return xs != ys
  1393  		case token.LSS:
  1394  			return xs < ys
  1395  		case token.LEQ:
  1396  			return xs <= ys
  1397  		case token.GTR:
  1398  			return xs > ys
  1399  		case token.GEQ:
  1400  			return xs >= ys
  1401  		}
  1402  	}
  1403  
  1404  	panic(fmt.Sprintf("invalid comparison %v %s %v", x_, op, y_))
  1405  }
  1406  

View as plain text