value.go

Documentation: go/constant

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