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

View as plain text