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//
13package constant
14
15import (
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.
27type Kind int
28
29const (
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.
44type 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.
67const prec = 512
68
69type (
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
85func (unknownVal) Kind() Kind { return Unknown }
86func (boolVal) Kind() Kind    { return Bool }
87func (*stringVal) Kind() Kind { return String }
88func (int64Val) Kind() Kind   { return Int }
89func (intVal) Kind() Kind     { return Int }
90func (ratVal) Kind() Kind     { return Float }
91func (floatVal) Kind() Kind   { return Float }
92func (complexVal) Kind() Kind { return Complex }
93
94func (unknownVal) String() string { return "unknown" }
95func (x boolVal) String() string  { return strconv.FormatBool(bool(x)) }
96
97// String returns a possibly shortened quoted form of the String value.
98func (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.
120func (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.
134func 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.
148func (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
169func (x int64Val) String() string { return strconv.FormatInt(int64(x), 10) }
170func (x intVal) String() string   { return x.val.String() }
171func (x ratVal) String() string   { return rtof(x).String() }
172
173// String returns a decimal approximation of the Float value.
174func (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
220func (x complexVal) String() string { return fmt.Sprintf("(%s + %si)", x.re, x.im) }
221
222func (x unknownVal) ExactString() string { return x.String() }
223func (x boolVal) ExactString() string    { return x.String() }
224func (x *stringVal) ExactString() string { return strconv.Quote(x.string()) }
225func (x int64Val) ExactString() string   { return x.String() }
226func (x intVal) ExactString() string     { return x.String() }
227
228func (x ratVal) ExactString() string {
229	r := x.val
230	if r.IsInt() {
231		return r.Num().String()
232	}
233	return r.String()
234}
235
236func (x floatVal) ExactString() string { return x.val.Text('p', 0) }
237
238func (x complexVal) ExactString() string {
239	return fmt.Sprintf("(%s + %si)", x.re.ExactString(), x.im.ExactString())
240}
241
242func (unknownVal) implementsValue() {}
243func (boolVal) implementsValue()    {}
244func (*stringVal) implementsValue() {}
245func (int64Val) implementsValue()   {}
246func (ratVal) implementsValue()     {}
247func (intVal) implementsValue()     {}
248func (floatVal) implementsValue()   {}
249func (complexVal) implementsValue() {}
250
251func newInt() *big.Int     { return new(big.Int) }
252func newRat() *big.Rat     { return new(big.Rat) }
253func newFloat() *big.Float { return new(big.Float).SetPrec(prec) }
254
255func i64toi(x int64Val) intVal   { return intVal{newInt().SetInt64(int64(x))} }
256func i64tor(x int64Val) ratVal   { return ratVal{newRat().SetInt64(int64(x))} }
257func i64tof(x int64Val) floatVal { return floatVal{newFloat().SetInt64(int64(x))} }
258func itor(x intVal) ratVal       { return ratVal{newRat().SetInt(x.val)} }
259func itof(x intVal) floatVal     { return floatVal{newFloat().SetInt(x.val)} }
260
261func 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
267func vtoc(x Value) complexVal { return complexVal{x, int64Val(0)} }
268
269func 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.
278const maxExp = 4 << 10
279
280func 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
293var floatVal0 = floatVal{newFloat()}
294
295func makeFloat(x *big.Float) Value {
296	// convert -0
297	if x.Sign() == 0 {
298		return floatVal0
299	}
300	return floatVal{x}
301}
302
303func makeComplex(re, im Value) Value {
304	return complexVal{re, im}
305}
306
307func 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			r, _ := newRat().SetString(lit)
319			return ratVal{r}
320		}
321		// otherwise use floats
322		return makeFloat(f)
323	}
324	return nil
325}
326
327// smallRat reports whether x would lead to "reasonably"-sized fraction
328// if converted to a *big.Rat.
329func smallRat(x *big.Float) bool {
330	if !x.IsInf() {
331		e := x.MantExp(nil)
332		return -maxExp < e && e < maxExp
333	}
334	return false
335}
336
337// ----------------------------------------------------------------------------
338// Factories
339
340// MakeUnknown returns the Unknown value.
341func MakeUnknown() Value { return unknownVal{} }
342
343// MakeBool returns the Bool value for b.
344func MakeBool(b bool) Value { return boolVal(b) }
345
346// MakeString returns the String value for s.
347func MakeString(s string) Value { return &stringVal{s: s} }
348
349// MakeInt64 returns the Int value for x.
350func MakeInt64(x int64) Value { return int64Val(x) }
351
352// MakeUint64 returns the Int value for x.
353func MakeUint64(x uint64) Value {
354	if x < 1<<63 {
355		return int64Val(int64(x))
356	}
357	return intVal{newInt().SetUint64(x)}
358}
359
360// MakeFloat64 returns the Float value for x.
361// If x is not finite, the result is an Unknown.
362func MakeFloat64(x float64) Value {
363	if math.IsInf(x, 0) || math.IsNaN(x) {
364		return unknownVal{}
365	}
366	// convert -0 to 0
367	if x == 0 {
368		return int64Val(0)
369	}
370	return ratVal{newRat().SetFloat64(x)}
371}
372
373// MakeFromLiteral returns the corresponding integer, floating-point,
374// imaginary, character, or string value for a Go literal string. The
375// tok value must be one of token.INT, token.FLOAT, token.IMAG,
376// token.CHAR, or token.STRING. The final argument must be zero.
377// If the literal string syntax is invalid, the result is an Unknown.
378func MakeFromLiteral(lit string, tok token.Token, zero uint) Value {
379	if zero != 0 {
380		panic("MakeFromLiteral called with non-zero last argument")
381	}
382
383	switch tok {
384	case token.INT:
385		if x, err := strconv.ParseInt(lit, 0, 64); err == nil {
386			return int64Val(x)
387		}
388		if x, ok := newInt().SetString(lit, 0); ok {
389			return intVal{x}
390		}
391
392	case token.FLOAT:
393		if x := makeFloatFromLiteral(lit); x != nil {
394			return x
395		}
396
397	case token.IMAG:
398		if n := len(lit); n > 0 && lit[n-1] == 'i' {
399			if im := makeFloatFromLiteral(lit[:n-1]); im != nil {
400				return makeComplex(int64Val(0), im)
401			}
402		}
403
404	case token.CHAR:
405		if n := len(lit); n >= 2 {
406			if code, _, _, err := strconv.UnquoteChar(lit[1:n-1], '\''); err == nil {
407				return MakeInt64(int64(code))
408			}
409		}
410
411	case token.STRING:
412		if s, err := strconv.Unquote(lit); err == nil {
413			return MakeString(s)
414		}
415
416	default:
417		panic(fmt.Sprintf("%v is not a valid token", tok))
418	}
419
420	return unknownVal{}
421}
422
423// ----------------------------------------------------------------------------
424// Accessors
425//
426// For unknown arguments the result is the zero value for the respective
427// accessor type, except for Sign, where the result is 1.
428
429// BoolVal returns the Go boolean value of x, which must be a Bool or an Unknown.
430// If x is Unknown, the result is false.
431func BoolVal(x Value) bool {
432	switch x := x.(type) {
433	case boolVal:
434		return bool(x)
435	case unknownVal:
436		return false
437	default:
438		panic(fmt.Sprintf("%v not a Bool", x))
439	}
440}
441
442// StringVal returns the Go string value of x, which must be a String or an Unknown.
443// If x is Unknown, the result is "".
444func StringVal(x Value) string {
445	switch x := x.(type) {
446	case *stringVal:
447		return x.string()
448	case unknownVal:
449		return ""
450	default:
451		panic(fmt.Sprintf("%v not a String", x))
452	}
453}
454
455// Int64Val returns the Go int64 value of x and whether the result is exact;
456// x must be an Int or an Unknown. If the result is not exact, its value is undefined.
457// If x is Unknown, the result is (0, false).
458func Int64Val(x Value) (int64, bool) {
459	switch x := x.(type) {
460	case int64Val:
461		return int64(x), true
462	case intVal:
463		return x.val.Int64(), false // not an int64Val and thus not exact
464	case unknownVal:
465		return 0, false
466	default:
467		panic(fmt.Sprintf("%v not an Int", x))
468	}
469}
470
471// Uint64Val returns the Go uint64 value of x and whether the result is exact;
472// x must be an Int or an Unknown. If the result is not exact, its value is undefined.
473// If x is Unknown, the result is (0, false).
474func Uint64Val(x Value) (uint64, bool) {
475	switch x := x.(type) {
476	case int64Val:
477		return uint64(x), x >= 0
478	case intVal:
479		return x.val.Uint64(), x.val.IsUint64()
480	case unknownVal:
481		return 0, false
482	default:
483		panic(fmt.Sprintf("%v not an Int", x))
484	}
485}
486
487// Float32Val is like Float64Val but for float32 instead of float64.
488func Float32Val(x Value) (float32, bool) {
489	switch x := x.(type) {
490	case int64Val:
491		f := float32(x)
492		return f, int64Val(f) == x
493	case intVal:
494		f, acc := newFloat().SetInt(x.val).Float32()
495		return f, acc == big.Exact
496	case ratVal:
497		return x.val.Float32()
498	case floatVal:
499		f, acc := x.val.Float32()
500		return f, acc == big.Exact
501	case unknownVal:
502		return 0, false
503	default:
504		panic(fmt.Sprintf("%v not a Float", x))
505	}
506}
507
508// Float64Val returns the nearest Go float64 value of x and whether the result is exact;
509// x must be numeric or an Unknown, but not Complex. For values too small (too close to 0)
510// to represent as float64, Float64Val silently underflows to 0. The result sign always
511// matches the sign of x, even for 0.
512// If x is Unknown, the result is (0, false).
513func Float64Val(x Value) (float64, bool) {
514	switch x := x.(type) {
515	case int64Val:
516		f := float64(int64(x))
517		return f, int64Val(f) == x
518	case intVal:
519		f, acc := newFloat().SetInt(x.val).Float64()
520		return f, acc == big.Exact
521	case ratVal:
522		return x.val.Float64()
523	case floatVal:
524		f, acc := x.val.Float64()
525		return f, acc == big.Exact
526	case unknownVal:
527		return 0, false
528	default:
529		panic(fmt.Sprintf("%v not a Float", x))
530	}
531}
532
533// BitLen returns the number of bits required to represent
534// the absolute value x in binary representation; x must be an Int or an Unknown.
535// If x is Unknown, the result is 0.
536func BitLen(x Value) int {
537	switch x := x.(type) {
538	case int64Val:
539		return i64toi(x).val.BitLen()
540	case intVal:
541		return x.val.BitLen()
542	case unknownVal:
543		return 0
544	default:
545		panic(fmt.Sprintf("%v not an Int", x))
546	}
547}
548
549// Sign returns -1, 0, or 1 depending on whether x < 0, x == 0, or x > 0;
550// x must be numeric or Unknown. For complex values x, the sign is 0 if x == 0,
551// otherwise it is != 0. If x is Unknown, the result is 1.
552func Sign(x Value) int {
553	switch x := x.(type) {
554	case int64Val:
555		switch {
556		case x < 0:
557			return -1
558		case x > 0:
559			return 1
560		}
561		return 0
562	case intVal:
563		return x.val.Sign()
564	case ratVal:
565		return x.val.Sign()
566	case floatVal:
567		return x.val.Sign()
568	case complexVal:
569		return Sign(x.re) | Sign(x.im)
570	case unknownVal:
571		return 1 // avoid spurious division by zero errors
572	default:
573		panic(fmt.Sprintf("%v not numeric", x))
574	}
575}
576
577// ----------------------------------------------------------------------------
578// Support for assembling/disassembling numeric values
579
580const (
581	// Compute the size of a Word in bytes.
582	_m       = ^big.Word(0)
583	_log     = _m>>8&1 + _m>>16&1 + _m>>32&1
584	wordSize = 1 << _log
585)
586
587// Bytes returns the bytes for the absolute value of x in little-
588// endian binary representation; x must be an Int.
589func Bytes(x Value) []byte {
590	var t intVal
591	switch x := x.(type) {
592	case int64Val:
593		t = i64toi(x)
594	case intVal:
595		t = x
596	default:
597		panic(fmt.Sprintf("%v not an Int", x))
598	}
599
600	words := t.val.Bits()
601	bytes := make([]byte, len(words)*wordSize)
602
603	i := 0
604	for _, w := range words {
605		for j := 0; j < wordSize; j++ {
606			bytes[i] = byte(w)
607			w >>= 8
608			i++
609		}
610	}
611	// remove leading 0's
612	for i > 0 && bytes[i-1] == 0 {
613		i--
614	}
615
616	return bytes[:i]
617}
618
619// MakeFromBytes returns the Int value given the bytes of its little-endian
620// binary representation. An empty byte slice argument represents 0.
621func MakeFromBytes(bytes []byte) Value {
622	words := make([]big.Word, (len(bytes)+(wordSize-1))/wordSize)
623
624	i := 0
625	var w big.Word
626	var s uint
627	for _, b := range bytes {
628		w |= big.Word(b) << s
629		if s += 8; s == wordSize*8 {
630			words[i] = w
631			i++
632			w = 0
633			s = 0
634		}
635	}
636	// store last word
637	if i < len(words) {
638		words[i] = w
639		i++
640	}
641	// remove leading 0's
642	for i > 0 && words[i-1] == 0 {
643		i--
644	}
645
646	return makeInt(newInt().SetBits(words[:i]))
647}
648
649// Num returns the numerator of x; x must be Int, Float, or Unknown.
650// If x is Unknown, or if it is too large or small to represent as a
651// fraction, the result is Unknown. Otherwise the result is an Int
652// with the same sign as x.
653func Num(x Value) Value {
654	switch x := x.(type) {
655	case int64Val, intVal:
656		return x
657	case ratVal:
658		return makeInt(x.val.Num())
659	case floatVal:
660		if smallRat(x.val) {
661			r, _ := x.val.Rat(nil)
662			return makeInt(r.Num())
663		}
664	case unknownVal:
665		break
666	default:
667		panic(fmt.Sprintf("%v not Int or Float", x))
668	}
669	return unknownVal{}
670}
671
672// Denom returns the denominator of x; x must be Int, Float, or Unknown.
673// If x is Unknown, or if it is too large or small to represent as a
674// fraction, the result is Unknown. Otherwise the result is an Int >= 1.
675func Denom(x Value) Value {
676	switch x := x.(type) {
677	case int64Val, intVal:
678		return int64Val(1)
679	case ratVal:
680		return makeInt(x.val.Denom())
681	case floatVal:
682		if smallRat(x.val) {
683			r, _ := x.val.Rat(nil)
684			return makeInt(r.Denom())
685		}
686	case unknownVal:
687		break
688	default:
689		panic(fmt.Sprintf("%v not Int or Float", x))
690	}
691	return unknownVal{}
692}
693
694// MakeImag returns the Complex value x*i;
695// x must be Int, Float, or Unknown.
696// If x is Unknown, the result is Unknown.
697func MakeImag(x Value) Value {
698	switch x.(type) {
699	case unknownVal:
700		return x
701	case int64Val, intVal, ratVal, floatVal:
702		return makeComplex(int64Val(0), x)
703	default:
704		panic(fmt.Sprintf("%v not Int or Float", x))
705	}
706}
707
708// Real returns the real part of x, which must be a numeric or unknown value.
709// If x is Unknown, the result is Unknown.
710func Real(x Value) Value {
711	switch x := x.(type) {
712	case unknownVal, int64Val, intVal, ratVal, floatVal:
713		return x
714	case complexVal:
715		return x.re
716	default:
717		panic(fmt.Sprintf("%v not numeric", x))
718	}
719}
720
721// Imag returns the imaginary part of x, which must be a numeric or unknown value.
722// If x is Unknown, the result is Unknown.
723func Imag(x Value) Value {
724	switch x := x.(type) {
725	case unknownVal:
726		return x
727	case int64Val, intVal, ratVal, floatVal:
728		return int64Val(0)
729	case complexVal:
730		return x.im
731	default:
732		panic(fmt.Sprintf("%v not numeric", x))
733	}
734}
735
736// ----------------------------------------------------------------------------
737// Numeric conversions
738
739// ToInt converts x to an Int value if x is representable as an Int.
740// Otherwise it returns an Unknown.
741func ToInt(x Value) Value {
742	switch x := x.(type) {
743	case int64Val, intVal:
744		return x
745
746	case ratVal:
747		if x.val.IsInt() {
748			return makeInt(x.val.Num())
749		}
750
751	case floatVal:
752		// avoid creation of huge integers
753		// (Existing tests require permitting exponents of at least 1024;
754		// allow any value that would also be permissible as a fraction.)
755		if smallRat(x.val) {
756			i := newInt()
757			if _, acc := x.val.Int(i); acc == big.Exact {
758				return makeInt(i)
759			}
760
761			// If we can get an integer by rounding up or down,
762			// assume x is not an integer because of rounding
763			// errors in prior computations.
764
765			const delta = 4 // a small number of bits > 0
766			var t big.Float
767			t.SetPrec(prec - delta)
768
769			// try rounding down a little
770			t.SetMode(big.ToZero)
771			t.Set(x.val)
772			if _, acc := t.Int(i); acc == big.Exact {
773				return makeInt(i)
774			}
775
776			// try rounding up a little
777			t.SetMode(big.AwayFromZero)
778			t.Set(x.val)
779			if _, acc := t.Int(i); acc == big.Exact {
780				return makeInt(i)
781			}
782		}
783
784	case complexVal:
785		if re := ToFloat(x); re.Kind() == Float {
786			return ToInt(re)
787		}
788	}
789
790	return unknownVal{}
791}
792
793// ToFloat converts x to a Float value if x is representable as a Float.
794// Otherwise it returns an Unknown.
795func ToFloat(x Value) Value {
796	switch x := x.(type) {
797	case int64Val:
798		return i64tof(x)
799	case intVal:
800		return itof(x)
801	case ratVal, floatVal:
802		return x
803	case complexVal:
804		if im := ToInt(x.im); im.Kind() == Int && Sign(im) == 0 {
805			// imaginary component is 0
806			return ToFloat(x.re)
807		}
808	}
809	return unknownVal{}
810}
811
812// ToComplex converts x to a Complex value if x is representable as a Complex.
813// Otherwise it returns an Unknown.
814func ToComplex(x Value) Value {
815	switch x := x.(type) {
816	case int64Val:
817		return vtoc(i64tof(x))
818	case intVal:
819		return vtoc(itof(x))
820	case ratVal:
821		return vtoc(x)
822	case floatVal:
823		return vtoc(x)
824	case complexVal:
825		return x
826	}
827	return unknownVal{}
828}
829
830// ----------------------------------------------------------------------------
831// Operations
832
833// is32bit reports whether x can be represented using 32 bits.
834func is32bit(x int64) bool {
835	const s = 32
836	return -1<<(s-1) <= x && x <= 1<<(s-1)-1
837}
838
839// is63bit reports whether x can be represented using 63 bits.
840func is63bit(x int64) bool {
841	const s = 63
842	return -1<<(s-1) <= x && x <= 1<<(s-1)-1
843}
844
845// UnaryOp returns the result of the unary expression op y.
846// The operation must be defined for the operand.
847// If prec > 0 it specifies the ^ (xor) result size in bits.
848// If y is Unknown, the result is Unknown.
849//
850func UnaryOp(op token.Token, y Value, prec uint) Value {
851	switch op {
852	case token.ADD:
853		switch y.(type) {
854		case unknownVal, int64Val, intVal, ratVal, floatVal, complexVal:
855			return y
856		}
857
858	case token.SUB:
859		switch y := y.(type) {
860		case unknownVal:
861			return y
862		case int64Val:
863			if z := -y; z != y {
864				return z // no overflow
865			}
866			return makeInt(newInt().Neg(big.NewInt(int64(y))))
867		case intVal:
868			return makeInt(newInt().Neg(y.val))
869		case ratVal:
870			return makeRat(newRat().Neg(y.val))
871		case floatVal:
872			return makeFloat(newFloat().Neg(y.val))
873		case complexVal:
874			re := UnaryOp(token.SUB, y.re, 0)
875			im := UnaryOp(token.SUB, y.im, 0)
876			return makeComplex(re, im)
877		}
878
879	case token.XOR:
880		z := newInt()
881		switch y := y.(type) {
882		case unknownVal:
883			return y
884		case int64Val:
885			z.Not(big.NewInt(int64(y)))
886		case intVal:
887			z.Not(y.val)
888		default:
889			goto Error
890		}
891		// For unsigned types, the result will be negative and
892		// thus "too large": We must limit the result precision
893		// to the type's precision.
894		if prec > 0 {
895			z.AndNot(z, newInt().Lsh(big.NewInt(-1), prec)) // z &^= (-1)<<prec
896		}
897		return makeInt(z)
898
899	case token.NOT:
900		switch y := y.(type) {
901		case unknownVal:
902			return y
903		case boolVal:
904			return !y
905		}
906	}
907
908Error:
909	panic(fmt.Sprintf("invalid unary operation %s%v", op, y))
910}
911
912func ord(x Value) int {
913	switch x.(type) {
914	default:
915		// force invalid value into "x position" in match
916		// (don't panic here so that callers can provide a better error message)
917		return -1
918	case unknownVal:
919		return 0
920	case boolVal, *stringVal:
921		return 1
922	case int64Val:
923		return 2
924	case intVal:
925		return 3
926	case ratVal:
927		return 4
928	case floatVal:
929		return 5
930	case complexVal:
931		return 6
932	}
933}
934
935// match returns the matching representation (same type) with the
936// smallest complexity for two values x and y. If one of them is
937// numeric, both of them must be numeric. If one of them is Unknown
938// or invalid (say, nil) both results are that value.
939//
940func match(x, y Value) (_, _ Value) {
941	if ord(x) > ord(y) {
942		y, x = match(y, x)
943		return x, y
944	}
945	// ord(x) <= ord(y)
946
947	switch x := x.(type) {
948	case boolVal, *stringVal, complexVal:
949		return x, y
950
951	case int64Val:
952		switch y := y.(type) {
953		case int64Val:
954			return x, y
955		case intVal:
956			return i64toi(x), y
957		case ratVal:
958			return i64tor(x), y
959		case floatVal:
960			return i64tof(x), y
961		case complexVal:
962			return vtoc(x), y
963		}
964
965	case intVal:
966		switch y := y.(type) {
967		case intVal:
968			return x, y
969		case ratVal:
970			return itor(x), y
971		case floatVal:
972			return itof(x), y
973		case complexVal:
974			return vtoc(x), y
975		}
976
977	case ratVal:
978		switch y := y.(type) {
979		case ratVal:
980			return x, y
981		case floatVal:
982			return rtof(x), y
983		case complexVal:
984			return vtoc(x), y
985		}
986
987	case floatVal:
988		switch y := y.(type) {
989		case floatVal:
990			return x, y
991		case complexVal:
992			return vtoc(x), y
993		}
994	}
995
996	// force unknown and invalid values into "x position" in callers of match
997	// (don't panic here so that callers can provide a better error message)
998	return x, x
999}
1000
1001// BinaryOp returns the result of the binary expression x op y.
1002// The operation must be defined for the operands. If one of the
1003// operands is Unknown, the result is Unknown.
1004// BinaryOp doesn't handle comparisons or shifts; use Compare
1005// or Shift instead.
1006//
1007// To force integer division of Int operands, use op == token.QUO_ASSIGN
1008// instead of token.QUO; the result is guaranteed to be Int in this case.
1009// Division by zero leads to a run-time panic.
1010//
1011func BinaryOp(x_ Value, op token.Token, y_ Value) Value {
1012	x, y := match(x_, y_)
1013
1014	switch x := x.(type) {
1015	case unknownVal:
1016		return x
1017
1018	case boolVal:
1019		y := y.(boolVal)
1020		switch op {
1021		case token.LAND:
1022			return x && y
1023		case token.LOR:
1024			return x || y
1025		}
1026
1027	case int64Val:
1028		a := int64(x)
1029		b := int64(y.(int64Val))
1030		var c int64
1031		switch op {
1032		case token.ADD:
1033			if !is63bit(a) || !is63bit(b) {
1034				return makeInt(newInt().Add(big.NewInt(a), big.NewInt(b)))
1035			}
1036			c = a + b
1037		case token.SUB:
1038			if !is63bit(a) || !is63bit(b) {
1039				return makeInt(newInt().Sub(big.NewInt(a), big.NewInt(b)))
1040			}
1041			c = a - b
1042		case token.MUL:
1043			if !is32bit(a) || !is32bit(b) {
1044				return makeInt(newInt().Mul(big.NewInt(a), big.NewInt(b)))
1045			}
1046			c = a * b
1047		case token.QUO:
1048			return makeRat(big.NewRat(a, b))
1049		case token.QUO_ASSIGN: // force integer division
1050			c = a / b
1051		case token.REM:
1052			c = a % b
1053		case token.AND:
1054			c = a & b
1055		case token.OR:
1056			c = a | b
1057		case token.XOR:
1058			c = a ^ b
1059		case token.AND_NOT:
1060			c = a &^ b
1061		default:
1062			goto Error
1063		}
1064		return int64Val(c)
1065
1066	case intVal:
1067		a := x.val
1068		b := y.(intVal).val
1069		c := newInt()
1070		switch op {
1071		case token.ADD:
1072			c.Add(a, b)
1073		case token.SUB:
1074			c.Sub(a, b)
1075		case token.MUL:
1076			c.Mul(a, b)
1077		case token.QUO:
1078			return makeRat(newRat().SetFrac(a, b))
1079		case token.QUO_ASSIGN: // force integer division
1080			c.Quo(a, b)
1081		case token.REM:
1082			c.Rem(a, b)
1083		case token.AND:
1084			c.And(a, b)
1085		case token.OR:
1086			c.Or(a, b)
1087		case token.XOR:
1088			c.Xor(a, b)
1089		case token.AND_NOT:
1090			c.AndNot(a, b)
1091		default:
1092			goto Error
1093		}
1094		return makeInt(c)
1095
1096	case ratVal:
1097		a := x.val
1098		b := y.(ratVal).val
1099		c := newRat()
1100		switch op {
1101		case token.ADD:
1102			c.Add(a, b)
1103		case token.SUB:
1104			c.Sub(a, b)
1105		case token.MUL:
1106			c.Mul(a, b)
1107		case token.QUO:
1108			c.Quo(a, b)
1109		default:
1110			goto Error
1111		}
1112		return makeRat(c)
1113
1114	case floatVal:
1115		a := x.val
1116		b := y.(floatVal).val
1117		c := newFloat()
1118		switch op {
1119		case token.ADD:
1120			c.Add(a, b)
1121		case token.SUB:
1122			c.Sub(a, b)
1123		case token.MUL:
1124			c.Mul(a, b)
1125		case token.QUO:
1126			c.Quo(a, b)
1127		default:
1128			goto Error
1129		}
1130		return makeFloat(c)
1131
1132	case complexVal:
1133		y := y.(complexVal)
1134		a, b := x.re, x.im
1135		c, d := y.re, y.im
1136		var re, im Value
1137		switch op {
1138		case token.ADD:
1139			// (a+c) + i(b+d)
1140			re = add(a, c)
1141			im = add(b, d)
1142		case token.SUB:
1143			// (a-c) + i(b-d)
1144			re = sub(a, c)
1145			im = sub(b, d)
1146		case token.MUL:
1147			// (ac-bd) + i(bc+ad)
1148			ac := mul(a, c)
1149			bd := mul(b, d)
1150			bc := mul(b, c)
1151			ad := mul(a, d)
1152			re = sub(ac, bd)
1153			im = add(bc, ad)
1154		case token.QUO:
1155			// (ac+bd)/s + i(bc-ad)/s, with s = cc + dd
1156			ac := mul(a, c)
1157			bd := mul(b, d)
1158			bc := mul(b, c)
1159			ad := mul(a, d)
1160			cc := mul(c, c)
1161			dd := mul(d, d)
1162			s := add(cc, dd)
1163			re = add(ac, bd)
1164			re = quo(re, s)
1165			im = sub(bc, ad)
1166			im = quo(im, s)
1167		default:
1168			goto Error
1169		}
1170		return makeComplex(re, im)
1171
1172	case *stringVal:
1173		if op == token.ADD {
1174			return &stringVal{l: x, r: y.(*stringVal)}
1175		}
1176	}
1177
1178Error:
1179	panic(fmt.Sprintf("invalid binary operation %v %s %v", x_, op, y_))
1180}
1181
1182func add(x, y Value) Value { return BinaryOp(x, token.ADD, y) }
1183func sub(x, y Value) Value { return BinaryOp(x, token.SUB, y) }
1184func mul(x, y Value) Value { return BinaryOp(x, token.MUL, y) }
1185func quo(x, y Value) Value { return BinaryOp(x, token.QUO, y) }
1186
1187// Shift returns the result of the shift expression x op s
1188// with op == token.SHL or token.SHR (<< or >>). x must be
1189// an Int or an Unknown. If x is Unknown, the result is x.
1190//
1191func Shift(x Value, op token.Token, s uint) Value {
1192	switch x := x.(type) {
1193	case unknownVal:
1194		return x
1195
1196	case int64Val:
1197		if s == 0 {
1198			return x
1199		}
1200		switch op {
1201		case token.SHL:
1202			z := i64toi(x).val
1203			return makeInt(z.Lsh(z, s))
1204		case token.SHR:
1205			return x >> s
1206		}
1207
1208	case intVal:
1209		if s == 0 {
1210			return x
1211		}
1212		z := newInt()
1213		switch op {
1214		case token.SHL:
1215			return makeInt(z.Lsh(x.val, s))
1216		case token.SHR:
1217			return makeInt(z.Rsh(x.val, s))
1218		}
1219	}
1220
1221	panic(fmt.Sprintf("invalid shift %v %s %d", x, op, s))
1222}
1223
1224func cmpZero(x int, op token.Token) bool {
1225	switch op {
1226	case token.EQL:
1227		return x == 0
1228	case token.NEQ:
1229		return x != 0
1230	case token.LSS:
1231		return x < 0
1232	case token.LEQ:
1233		return x <= 0
1234	case token.GTR:
1235		return x > 0
1236	case token.GEQ:
1237		return x >= 0
1238	}
1239	panic(fmt.Sprintf("invalid comparison %v %s 0", x, op))
1240}
1241
1242// Compare returns the result of the comparison x op y.
1243// The comparison must be defined for the operands.
1244// If one of the operands is Unknown, the result is
1245// false.
1246//
1247func Compare(x_ Value, op token.Token, y_ Value) bool {
1248	x, y := match(x_, y_)
1249
1250	switch x := x.(type) {
1251	case unknownVal:
1252		return false
1253
1254	case boolVal:
1255		y := y.(boolVal)
1256		switch op {
1257		case token.EQL:
1258			return x == y
1259		case token.NEQ:
1260			return x != y
1261		}
1262
1263	case int64Val:
1264		y := y.(int64Val)
1265		switch op {
1266		case token.EQL:
1267			return x == y
1268		case token.NEQ:
1269			return x != y
1270		case token.LSS:
1271			return x < y
1272		case token.LEQ:
1273			return x <= y
1274		case token.GTR:
1275			return x > y
1276		case token.GEQ:
1277			return x >= y
1278		}
1279
1280	case intVal:
1281		return cmpZero(x.val.Cmp(y.(intVal).val), op)
1282
1283	case ratVal:
1284		return cmpZero(x.val.Cmp(y.(ratVal).val), op)
1285
1286	case floatVal:
1287		return cmpZero(x.val.Cmp(y.(floatVal).val), op)
1288
1289	case complexVal:
1290		y := y.(complexVal)
1291		re := Compare(x.re, token.EQL, y.re)
1292		im := Compare(x.im, token.EQL, y.im)
1293		switch op {
1294		case token.EQL:
1295			return re && im
1296		case token.NEQ:
1297			return !re || !im
1298		}
1299
1300	case *stringVal:
1301		xs := x.string()
1302		ys := y.(*stringVal).string()
1303		switch op {
1304		case token.EQL:
1305			return xs == ys
1306		case token.NEQ:
1307			return xs != ys
1308		case token.LSS:
1309			return xs < ys
1310		case token.LEQ:
1311			return xs <= ys
1312		case token.GTR:
1313			return xs > ys
1314		case token.GEQ:
1315			return xs >= ys
1316		}
1317	}
1318
1319	panic(fmt.Sprintf("invalid comparison %v %s %v", x_, op, y_))
1320}
1321