← Back to branch summary

~vtuson/scopecreator/twitter-template

« back to all changes in this revision

Viewing changes to src/go/src/code.google.com/p/go.tools/go/exact/exact.go

  • Committer: Victor Palau
  • Date: 2015-03-11 14:24:42 UTC
  • Revision ID: vtuson@gmail.com-20150311142442-f2pxp111c8ynv232
public release

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/go/src/code.google.com/p/go.tools/go/exact/exact.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 exact implements mathematically exact values
 
6
// and operations for untyped Go constant values.
 
7
//
 
8
// A special Unknown value may be used when a constant
 
9
// value is unknown due to an error; operations on unknown
 
10
// values produce unknown values.
 
11
//
 
12
package exact
 
13
 
 
14
import (
 
15
        "fmt"
 
16
        "go/token"
 
17
        "math/big"
 
18
        "strconv"
 
19
)
 
20
 
 
21
// Kind specifies the kind of value represented by a Value.
 
22
type Kind int
 
23
 
 
24
// Implementation note: Kinds must be enumerated in
 
25
// order of increasing "complexity" (used by match).
 
26
 
 
27
const (
 
28
        // unknown values
 
29
        Unknown Kind = iota
 
30
 
 
31
        // non-numeric values
 
32
        Bool
 
33
        String
 
34
 
 
35
        // numeric values
 
36
        Int
 
37
        Float
 
38
        Complex
 
39
)
 
40
 
 
41
// A Value represents a mathematically precise value of a given Kind.
 
42
type Value interface {
 
43
        // Kind returns the value kind; it is always the smallest
 
44
        // kind in which the value can be represented exactly.
 
45
        Kind() Kind
 
46
 
 
47
        // String returns a human-readable form of the value.
 
48
        String() string
 
49
 
 
50
        // Prevent external implementations.
 
51
        implementsValue()
 
52
}
 
53
 
 
54
// ----------------------------------------------------------------------------
 
55
// Implementations
 
56
 
 
57
type (
 
58
        unknownVal struct{}
 
59
        boolVal    bool
 
60
        stringVal  string
 
61
        int64Val   int64
 
62
        intVal     struct{ val *big.Int }
 
63
        floatVal   struct{ val *big.Rat }
 
64
        complexVal struct{ re, im *big.Rat }
 
65
)
 
66
 
 
67
func (unknownVal) Kind() Kind { return Unknown }
 
68
func (boolVal) Kind() Kind    { return Bool }
 
69
func (stringVal) Kind() Kind  { return String }
 
70
func (int64Val) Kind() Kind   { return Int }
 
71
func (intVal) Kind() Kind     { return Int }
 
72
func (floatVal) Kind() Kind   { return Float }
 
73
func (complexVal) Kind() Kind { return Complex }
 
74
 
 
75
func (unknownVal) String() string   { return "unknown" }
 
76
func (x boolVal) String() string    { return fmt.Sprintf("%v", bool(x)) }
 
77
func (x stringVal) String() string  { return strconv.Quote(string(x)) }
 
78
func (x int64Val) String() string   { return strconv.FormatInt(int64(x), 10) }
 
79
func (x intVal) String() string     { return x.val.String() }
 
80
func (x floatVal) String() string   { return x.val.String() }
 
81
func (x complexVal) String() string { return fmt.Sprintf("(%s + %si)", x.re, x.im) }
 
82
 
 
83
func (unknownVal) implementsValue() {}
 
84
func (boolVal) implementsValue()    {}
 
85
func (stringVal) implementsValue()  {}
 
86
func (int64Val) implementsValue()   {}
 
87
func (intVal) implementsValue()     {}
 
88
func (floatVal) implementsValue()   {}
 
89
func (complexVal) implementsValue() {}
 
90
 
 
91
// int64 bounds
 
92
var (
 
93
        minInt64 = big.NewInt(-1 << 63)
 
94
        maxInt64 = big.NewInt(1<<63 - 1)
 
95
)
 
96
 
 
97
func normInt(x *big.Int) Value {
 
98
        if minInt64.Cmp(x) <= 0 && x.Cmp(maxInt64) <= 0 {
 
99
                return int64Val(x.Int64())
 
100
        }
 
101
        return intVal{x}
 
102
}
 
103
 
 
104
func normFloat(x *big.Rat) Value {
 
105
        if x.IsInt() {
 
106
                return normInt(x.Num())
 
107
        }
 
108
        return floatVal{x}
 
109
}
 
110
 
 
111
func normComplex(re, im *big.Rat) Value {
 
112
        if im.Sign() == 0 {
 
113
                return normFloat(re)
 
114
        }
 
115
        return complexVal{re, im}
 
116
}
 
117
 
 
118
// ----------------------------------------------------------------------------
 
119
// Factories
 
120
 
 
121
// MakeUnknown returns the Unknown value.
 
122
func MakeUnknown() Value { return unknownVal{} }
 
123
 
 
124
// MakeBool returns the Bool value for x.
 
125
func MakeBool(b bool) Value { return boolVal(b) }
 
126
 
 
127
// MakeString returns the String value for x.
 
128
func MakeString(s string) Value { return stringVal(s) }
 
129
 
 
130
// MakeInt64 returns the Int value for x.
 
131
func MakeInt64(x int64) Value { return int64Val(x) }
 
132
 
 
133
// MakeUint64 returns the Int value for x.
 
134
func MakeUint64(x uint64) Value { return normInt(new(big.Int).SetUint64(x)) }
 
135
 
 
136
// MakeFloat64 returns the numeric value for x.
 
137
// If x is not finite, the result is unknown.
 
138
func MakeFloat64(x float64) Value {
 
139
        if f := new(big.Rat).SetFloat64(x); f != nil {
 
140
                return normFloat(f)
 
141
        }
 
142
        return unknownVal{}
 
143
}
 
144
 
 
145
// MakeFromLiteral returns the corresponding integer, floating-point,
 
146
// imaginary, character, or string value for a Go literal string. The
 
147
// result is nil if the literal string is invalid.
 
148
func MakeFromLiteral(lit string, tok token.Token) Value {
 
149
        switch tok {
 
150
        case token.INT:
 
151
                if x, err := strconv.ParseInt(lit, 0, 64); err == nil {
 
152
                        return int64Val(x)
 
153
                }
 
154
                if x, ok := new(big.Int).SetString(lit, 0); ok {
 
155
                        return intVal{x}
 
156
                }
 
157
 
 
158
        case token.FLOAT:
 
159
                if x, ok := new(big.Rat).SetString(lit); ok {
 
160
                        return normFloat(x)
 
161
                }
 
162
 
 
163
        case token.IMAG:
 
164
                if n := len(lit); n > 0 && lit[n-1] == 'i' {
 
165
                        if im, ok := new(big.Rat).SetString(lit[0 : n-1]); ok {
 
166
                                return normComplex(big.NewRat(0, 1), im)
 
167
                        }
 
168
                }
 
169
 
 
170
        case token.CHAR:
 
171
                if n := len(lit); n >= 2 {
 
172
                        if code, _, _, err := strconv.UnquoteChar(lit[1:n-1], '\''); err == nil {
 
173
                                return int64Val(code)
 
174
                        }
 
175
                }
 
176
 
 
177
        case token.STRING:
 
178
                if s, err := strconv.Unquote(lit); err == nil {
 
179
                        return stringVal(s)
 
180
                }
 
181
        }
 
182
 
 
183
        return nil
 
184
}
 
185
 
 
186
// ----------------------------------------------------------------------------
 
187
// Accessors
 
188
//
 
189
// For unknown arguments the result is the zero value for the respective
 
190
// accessor type, except for Sign, where the result is 1.
 
191
 
 
192
// BoolVal returns the Go boolean value of x, which must be a Bool or an Unknown.
 
193
// If x is Unknown, the result is false.
 
194
func BoolVal(x Value) bool {
 
195
        switch x := x.(type) {
 
196
        case boolVal:
 
197
                return bool(x)
 
198
        case unknownVal:
 
199
                return false
 
200
        }
 
201
        panic(fmt.Sprintf("%v not a Bool", x))
 
202
}
 
203
 
 
204
// StringVal returns the Go string value of x, which must be a String or an Unknown.
 
205
// If x is Unknown, the result is "".
 
206
func StringVal(x Value) string {
 
207
        switch x := x.(type) {
 
208
        case stringVal:
 
209
                return string(x)
 
210
        case unknownVal:
 
211
                return ""
 
212
        }
 
213
        panic(fmt.Sprintf("%v not a String", x))
 
214
}
 
215
 
 
216
// Int64Val returns the Go int64 value of x and whether the result is exact;
 
217
// x must be an Int or an Unknown. If the result is not exact, its value is undefined.
 
218
// If x is Unknown, the result is (0, false).
 
219
func Int64Val(x Value) (int64, bool) {
 
220
        switch x := x.(type) {
 
221
        case int64Val:
 
222
                return int64(x), true
 
223
        case intVal:
 
224
                return x.val.Int64(), x.val.BitLen() <= 63
 
225
        case unknownVal:
 
226
                return 0, false
 
227
        }
 
228
        panic(fmt.Sprintf("%v not an Int", x))
 
229
}
 
230
 
 
231
// Uint64Val returns the Go uint64 value of x and whether the result is exact;
 
232
// x must be an Int or an Unknown. If the result is not exact, its value is undefined.
 
233
// If x is Unknown, the result is (0, false).
 
234
func Uint64Val(x Value) (uint64, bool) {
 
235
        switch x := x.(type) {
 
236
        case int64Val:
 
237
                return uint64(x), x >= 0
 
238
        case intVal:
 
239
                return x.val.Uint64(), x.val.Sign() >= 0 && x.val.BitLen() <= 64
 
240
        case unknownVal:
 
241
                return 0, false
 
242
        }
 
243
        panic(fmt.Sprintf("%v not an Int", x))
 
244
}
 
245
 
 
246
// Float64Val returns the nearest Go float64 value of x and whether the result is exact;
 
247
// x must be numeric but not Complex, or Unknown. For values too small (too close to 0)
 
248
// to represent as float64, Float64Val silently underflows to 0. The result sign always
 
249
// matches the sign of x, even for 0.
 
250
// If x is Unknown, the result is (0, false).
 
251
func Float64Val(x Value) (float64, bool) {
 
252
        switch x := x.(type) {
 
253
        case int64Val:
 
254
                f := float64(int64(x))
 
255
                return f, int64Val(f) == x
 
256
        case intVal:
 
257
                return new(big.Rat).SetFrac(x.val, int1).Float64()
 
258
        case floatVal:
 
259
                return x.val.Float64()
 
260
        case unknownVal:
 
261
                return 0, false
 
262
        }
 
263
        panic(fmt.Sprintf("%v not a Float", x))
 
264
}
 
265
 
 
266
// BitLen returns the number of bits required to represent
 
267
// the absolute value x in binary representation; x must be an Int or an Unknown.
 
268
// If x is Unknown, the result is 0.
 
269
func BitLen(x Value) int {
 
270
        switch x := x.(type) {
 
271
        case int64Val:
 
272
                return new(big.Int).SetInt64(int64(x)).BitLen()
 
273
        case intVal:
 
274
                return x.val.BitLen()
 
275
        case unknownVal:
 
276
                return 0
 
277
        }
 
278
        panic(fmt.Sprintf("%v not an Int", x))
 
279
}
 
280
 
 
281
// Sign returns -1, 0, or 1 depending on whether x < 0, x == 0, or x > 0;
 
282
// x must be numeric or Unknown. For complex values x, the sign is 0 if x == 0,
 
283
// otherwise it is != 0. If x is Unknown, the result is 1.
 
284
func Sign(x Value) int {
 
285
        switch x := x.(type) {
 
286
        case int64Val:
 
287
                switch {
 
288
                case x < 0:
 
289
                        return -1
 
290
                case x > 0:
 
291
                        return 1
 
292
                }
 
293
                return 0
 
294
        case intVal:
 
295
                return x.val.Sign()
 
296
        case floatVal:
 
297
                return x.val.Sign()
 
298
        case complexVal:
 
299
                return x.re.Sign() | x.im.Sign()
 
300
        case unknownVal:
 
301
                return 1 // avoid spurious division by zero errors
 
302
        }
 
303
        panic(fmt.Sprintf("%v not numeric", x))
 
304
}
 
305
 
 
306
// ----------------------------------------------------------------------------
 
307
// Support for serializing/deserializing integers
 
308
 
 
309
const (
 
310
        // Compute the size of a Word in bytes.
 
311
        _m       = ^big.Word(0)
 
312
        _log     = _m>>8&1 + _m>>16&1 + _m>>32&1
 
313
        wordSize = 1 << _log
 
314
)
 
315
 
 
316
// Bytes returns the bytes for the absolute value of x in little-
 
317
// endian binary representation; x must be an Int.
 
318
func Bytes(x Value) []byte {
 
319
        var val *big.Int
 
320
        switch x := x.(type) {
 
321
        case int64Val:
 
322
                val = new(big.Int).SetInt64(int64(x))
 
323
        case intVal:
 
324
                val = x.val
 
325
        default:
 
326
                panic(fmt.Sprintf("%v not an Int", x))
 
327
        }
 
328
 
 
329
        words := val.Bits()
 
330
        bytes := make([]byte, len(words)*wordSize)
 
331
 
 
332
        i := 0
 
333
        for _, w := range words {
 
334
                for j := 0; j < wordSize; j++ {
 
335
                        bytes[i] = byte(w)
 
336
                        w >>= 8
 
337
                        i++
 
338
                }
 
339
        }
 
340
        // remove leading 0's
 
341
        for i > 0 && bytes[i-1] == 0 {
 
342
                i--
 
343
        }
 
344
 
 
345
        return bytes[:i]
 
346
}
 
347
 
 
348
// MakeFromBytes returns the Int value given the bytes of its little-endian
 
349
// binary representation. An empty byte slice argument represents 0.
 
350
func MakeFromBytes(bytes []byte) Value {
 
351
        words := make([]big.Word, (len(bytes)+(wordSize-1))/wordSize)
 
352
 
 
353
        i := 0
 
354
        var w big.Word
 
355
        var s uint
 
356
        for _, b := range bytes {
 
357
                w |= big.Word(b) << s
 
358
                if s += 8; s == wordSize*8 {
 
359
                        words[i] = w
 
360
                        i++
 
361
                        w = 0
 
362
                        s = 0
 
363
                }
 
364
        }
 
365
        // store last word
 
366
        if i < len(words) {
 
367
                words[i] = w
 
368
                i++
 
369
        }
 
370
        // remove leading 0's
 
371
        for i > 0 && words[i-1] == 0 {
 
372
                i--
 
373
        }
 
374
 
 
375
        return normInt(new(big.Int).SetBits(words[:i]))
 
376
}
 
377
 
 
378
// ----------------------------------------------------------------------------
 
379
// Support for disassembling fractions
 
380
 
 
381
// Num returns the numerator of x; x must be Int, Float, or Unknown.
 
382
// If x is Unknown, the result is Unknown, otherwise it is an Int.
 
383
func Num(x Value) Value {
 
384
        switch x := x.(type) {
 
385
        case unknownVal, int64Val, intVal:
 
386
                return x
 
387
        case floatVal:
 
388
                return normInt(x.val.Num())
 
389
        }
 
390
        panic(fmt.Sprintf("%v not Int or Float", x))
 
391
}
 
392
 
 
393
// Denom returns the denominator of x; x must be Int, Float, or Unknown.
 
394
// If x is Unknown, the result is Unknown, otherwise it is an Int >= 1.
 
395
func Denom(x Value) Value {
 
396
        switch x := x.(type) {
 
397
        case unknownVal:
 
398
                return x
 
399
        case int64Val, intVal:
 
400
                return int64Val(1)
 
401
        case floatVal:
 
402
                return normInt(x.val.Denom())
 
403
        }
 
404
        panic(fmt.Sprintf("%v not Int or Float", x))
 
405
}
 
406
 
 
407
// ----------------------------------------------------------------------------
 
408
// Support for assembling/disassembling complex numbers
 
409
 
 
410
// MakeImag returns the numeric value x*i (possibly 0);
 
411
// x must be Int, Float, or Unknown.
 
412
// If x is Unknown, the result is Unknown.
 
413
func MakeImag(x Value) Value {
 
414
        var im *big.Rat
 
415
        switch x := x.(type) {
 
416
        case unknownVal:
 
417
                return x
 
418
        case int64Val:
 
419
                im = big.NewRat(int64(x), 1)
 
420
        case intVal:
 
421
                im = new(big.Rat).SetFrac(x.val, int1)
 
422
        case floatVal:
 
423
                im = x.val
 
424
        default:
 
425
                panic(fmt.Sprintf("%v not Int or Float", x))
 
426
        }
 
427
        return normComplex(rat0, im)
 
428
}
 
429
 
 
430
// Real returns the real part of x, which must be a numeric or unknown value.
 
431
// If x is Unknown, the result is Unknown.
 
432
func Real(x Value) Value {
 
433
        switch x := x.(type) {
 
434
        case unknownVal, int64Val, intVal, floatVal:
 
435
                return x
 
436
        case complexVal:
 
437
                return normFloat(x.re)
 
438
        }
 
439
        panic(fmt.Sprintf("%v not numeric", x))
 
440
}
 
441
 
 
442
// Imag returns the imaginary part of x, which must be a numeric or unknown value.
 
443
// If x is Unknown, the result is Unknown.
 
444
func Imag(x Value) Value {
 
445
        switch x := x.(type) {
 
446
        case unknownVal:
 
447
                return x
 
448
        case int64Val, intVal, floatVal:
 
449
                return int64Val(0)
 
450
        case complexVal:
 
451
                return normFloat(x.im)
 
452
        }
 
453
        panic(fmt.Sprintf("%v not numeric", x))
 
454
}
 
455
 
 
456
// ----------------------------------------------------------------------------
 
457
// Operations
 
458
 
 
459
// is32bit reports whether x can be represented using 32 bits.
 
460
func is32bit(x int64) bool {
 
461
        const s = 32
 
462
        return -1<<(s-1) <= x && x <= 1<<(s-1)-1
 
463
}
 
464
 
 
465
// is63bit reports whether x can be represented using 63 bits.
 
466
func is63bit(x int64) bool {
 
467
        const s = 63
 
468
        return -1<<(s-1) <= x && x <= 1<<(s-1)-1
 
469
}
 
470
 
 
471
// UnaryOp returns the result of the unary expression op y.
 
472
// The operation must be defined for the operand.
 
473
// If size >= 0 it specifies the ^ (xor) result size in bytes.
 
474
// If y is Unknown, the result is Unknown.
 
475
//
 
476
func UnaryOp(op token.Token, y Value, size int) Value {
 
477
        switch op {
 
478
        case token.ADD:
 
479
                switch y.(type) {
 
480
                case unknownVal, int64Val, intVal, floatVal, complexVal:
 
481
                        return y
 
482
                }
 
483
 
 
484
        case token.SUB:
 
485
                switch y := y.(type) {
 
486
                case unknownVal:
 
487
                        return y
 
488
                case int64Val:
 
489
                        if z := -y; z != y {
 
490
                                return z // no overflow
 
491
                        }
 
492
                        return normInt(new(big.Int).Neg(big.NewInt(int64(y))))
 
493
                case intVal:
 
494
                        return normInt(new(big.Int).Neg(y.val))
 
495
                case floatVal:
 
496
                        return normFloat(new(big.Rat).Neg(y.val))
 
497
                case complexVal:
 
498
                        return normComplex(new(big.Rat).Neg(y.re), new(big.Rat).Neg(y.im))
 
499
                }
 
500
 
 
501
        case token.XOR:
 
502
                var z big.Int
 
503
                switch y := y.(type) {
 
504
                case unknownVal:
 
505
                        return y
 
506
                case int64Val:
 
507
                        z.Not(big.NewInt(int64(y)))
 
508
                case intVal:
 
509
                        z.Not(y.val)
 
510
                default:
 
511
                        goto Error
 
512
                }
 
513
                // For unsigned types, the result will be negative and
 
514
                // thus "too large": We must limit the result size to
 
515
                // the type's size.
 
516
                if size >= 0 {
 
517
                        s := uint(size) * 8
 
518
                        z.AndNot(&z, new(big.Int).Lsh(big.NewInt(-1), s)) // z &^= (-1)<<s
 
519
                }
 
520
                return normInt(&z)
 
521
 
 
522
        case token.NOT:
 
523
                switch y := y.(type) {
 
524
                case unknownVal:
 
525
                        return y
 
526
                case boolVal:
 
527
                        return !y
 
528
                }
 
529
        }
 
530
 
 
531
Error:
 
532
        panic(fmt.Sprintf("invalid unary operation %s%v", op, y))
 
533
}
 
534
 
 
535
var (
 
536
        int1 = big.NewInt(1)
 
537
        rat0 = big.NewRat(0, 1)
 
538
)
 
539
 
 
540
func ord(x Value) int {
 
541
        switch x.(type) {
 
542
        default:
 
543
                return 0
 
544
        case int64Val:
 
545
                return 1
 
546
        case intVal:
 
547
                return 2
 
548
        case floatVal:
 
549
                return 3
 
550
        case complexVal:
 
551
                return 4
 
552
        }
 
553
}
 
554
 
 
555
// match returns the matching representation (same type) with the
 
556
// smallest complexity for two values x and y. If one of them is
 
557
// numeric, both of them must be numeric. If one of them is Unknown,
 
558
// both results are Unknown.
 
559
//
 
560
func match(x, y Value) (_, _ Value) {
 
561
        if ord(x) > ord(y) {
 
562
                y, x = match(y, x)
 
563
                return x, y
 
564
        }
 
565
        // ord(x) <= ord(y)
 
566
 
 
567
        switch x := x.(type) {
 
568
        case unknownVal:
 
569
                return x, x
 
570
 
 
571
        case boolVal, stringVal, complexVal:
 
572
                return x, y
 
573
 
 
574
        case int64Val:
 
575
                switch y := y.(type) {
 
576
                case int64Val:
 
577
                        return x, y
 
578
                case intVal:
 
579
                        return intVal{big.NewInt(int64(x))}, y
 
580
                case floatVal:
 
581
                        return floatVal{big.NewRat(int64(x), 1)}, y
 
582
                case complexVal:
 
583
                        return complexVal{big.NewRat(int64(x), 1), rat0}, y
 
584
                }
 
585
 
 
586
        case intVal:
 
587
                switch y := y.(type) {
 
588
                case intVal:
 
589
                        return x, y
 
590
                case floatVal:
 
591
                        return floatVal{new(big.Rat).SetFrac(x.val, int1)}, y
 
592
                case complexVal:
 
593
                        return complexVal{new(big.Rat).SetFrac(x.val, int1), rat0}, y
 
594
                }
 
595
 
 
596
        case floatVal:
 
597
                switch y := y.(type) {
 
598
                case floatVal:
 
599
                        return x, y
 
600
                case complexVal:
 
601
                        return complexVal{x.val, rat0}, y
 
602
                }
 
603
        }
 
604
 
 
605
        panic("unreachable")
 
606
}
 
607
 
 
608
// BinaryOp returns the result of the binary expression x op y.
 
609
// The operation must be defined for the operands. If one of the
 
610
// operands is Unknown, the result is Unknown.
 
611
// To force integer division of Int operands, use op == token.QUO_ASSIGN
 
612
// instead of token.QUO; the result is guaranteed to be Int in this case.
 
613
// Division by zero leads to a run-time panic.
 
614
//
 
615
func BinaryOp(x Value, op token.Token, y Value) Value {
 
616
        x, y = match(x, y)
 
617
 
 
618
        switch x := x.(type) {
 
619
        case unknownVal:
 
620
                return x
 
621
 
 
622
        case boolVal:
 
623
                y := y.(boolVal)
 
624
                switch op {
 
625
                case token.LAND:
 
626
                        return x && y
 
627
                case token.LOR:
 
628
                        return x || y
 
629
                }
 
630
 
 
631
        case int64Val:
 
632
                a := int64(x)
 
633
                b := int64(y.(int64Val))
 
634
                var c int64
 
635
                switch op {
 
636
                case token.ADD:
 
637
                        if !is63bit(a) || !is63bit(b) {
 
638
                                return normInt(new(big.Int).Add(big.NewInt(a), big.NewInt(b)))
 
639
                        }
 
640
                        c = a + b
 
641
                case token.SUB:
 
642
                        if !is63bit(a) || !is63bit(b) {
 
643
                                return normInt(new(big.Int).Sub(big.NewInt(a), big.NewInt(b)))
 
644
                        }
 
645
                        c = a - b
 
646
                case token.MUL:
 
647
                        if !is32bit(a) || !is32bit(b) {
 
648
                                return normInt(new(big.Int).Mul(big.NewInt(a), big.NewInt(b)))
 
649
                        }
 
650
                        c = a * b
 
651
                case token.QUO:
 
652
                        return normFloat(new(big.Rat).SetFrac(big.NewInt(a), big.NewInt(b)))
 
653
                case token.QUO_ASSIGN: // force integer division
 
654
                        c = a / b
 
655
                case token.REM:
 
656
                        c = a % b
 
657
                case token.AND:
 
658
                        c = a & b
 
659
                case token.OR:
 
660
                        c = a | b
 
661
                case token.XOR:
 
662
                        c = a ^ b
 
663
                case token.AND_NOT:
 
664
                        c = a &^ b
 
665
                default:
 
666
                        goto Error
 
667
                }
 
668
                return int64Val(c)
 
669
 
 
670
        case intVal:
 
671
                a := x.val
 
672
                b := y.(intVal).val
 
673
                var c big.Int
 
674
                switch op {
 
675
                case token.ADD:
 
676
                        c.Add(a, b)
 
677
                case token.SUB:
 
678
                        c.Sub(a, b)
 
679
                case token.MUL:
 
680
                        c.Mul(a, b)
 
681
                case token.QUO:
 
682
                        return normFloat(new(big.Rat).SetFrac(a, b))
 
683
                case token.QUO_ASSIGN: // force integer division
 
684
                        c.Quo(a, b)
 
685
                case token.REM:
 
686
                        c.Rem(a, b)
 
687
                case token.AND:
 
688
                        c.And(a, b)
 
689
                case token.OR:
 
690
                        c.Or(a, b)
 
691
                case token.XOR:
 
692
                        c.Xor(a, b)
 
693
                case token.AND_NOT:
 
694
                        c.AndNot(a, b)
 
695
                default:
 
696
                        goto Error
 
697
                }
 
698
                return normInt(&c)
 
699
 
 
700
        case floatVal:
 
701
                a := x.val
 
702
                b := y.(floatVal).val
 
703
                var c big.Rat
 
704
                switch op {
 
705
                case token.ADD:
 
706
                        c.Add(a, b)
 
707
                case token.SUB:
 
708
                        c.Sub(a, b)
 
709
                case token.MUL:
 
710
                        c.Mul(a, b)
 
711
                case token.QUO:
 
712
                        c.Quo(a, b)
 
713
                default:
 
714
                        goto Error
 
715
                }
 
716
                return normFloat(&c)
 
717
 
 
718
        case complexVal:
 
719
                y := y.(complexVal)
 
720
                a, b := x.re, x.im
 
721
                c, d := y.re, y.im
 
722
                var re, im big.Rat
 
723
                switch op {
 
724
                case token.ADD:
 
725
                        // (a+c) + i(b+d)
 
726
                        re.Add(a, c)
 
727
                        im.Add(b, d)
 
728
                case token.SUB:
 
729
                        // (a-c) + i(b-d)
 
730
                        re.Sub(a, c)
 
731
                        im.Sub(b, d)
 
732
                case token.MUL:
 
733
                        // (ac-bd) + i(bc+ad)
 
734
                        var ac, bd, bc, ad big.Rat
 
735
                        ac.Mul(a, c)
 
736
                        bd.Mul(b, d)
 
737
                        bc.Mul(b, c)
 
738
                        ad.Mul(a, d)
 
739
                        re.Sub(&ac, &bd)
 
740
                        im.Add(&bc, &ad)
 
741
                case token.QUO:
 
742
                        // (ac+bd)/s + i(bc-ad)/s, with s = cc + dd
 
743
                        var ac, bd, bc, ad, s, cc, dd big.Rat
 
744
                        ac.Mul(a, c)
 
745
                        bd.Mul(b, d)
 
746
                        bc.Mul(b, c)
 
747
                        ad.Mul(a, d)
 
748
                        cc.Mul(c, c)
 
749
                        dd.Mul(d, d)
 
750
                        s.Add(&cc, &dd)
 
751
                        re.Add(&ac, &bd)
 
752
                        re.Quo(&re, &s)
 
753
                        im.Sub(&bc, &ad)
 
754
                        im.Quo(&im, &s)
 
755
                default:
 
756
                        goto Error
 
757
                }
 
758
                return normComplex(&re, &im)
 
759
 
 
760
        case stringVal:
 
761
                if op == token.ADD {
 
762
                        return x + y.(stringVal)
 
763
                }
 
764
        }
 
765
 
 
766
Error:
 
767
        panic(fmt.Sprintf("invalid binary operation %v %s %v", x, op, y))
 
768
}
 
769
 
 
770
// Shift returns the result of the shift expression x op s
 
771
// with op == token.SHL or token.SHR (<< or >>). x must be
 
772
// an Int or an Unknown. If x is Unknown, the result is x.
 
773
//
 
774
func Shift(x Value, op token.Token, s uint) Value {
 
775
        switch x := x.(type) {
 
776
        case unknownVal:
 
777
                return x
 
778
 
 
779
        case int64Val:
 
780
                if s == 0 {
 
781
                        return x
 
782
                }
 
783
                switch op {
 
784
                case token.SHL:
 
785
                        z := big.NewInt(int64(x))
 
786
                        return normInt(z.Lsh(z, s))
 
787
                case token.SHR:
 
788
                        return x >> s
 
789
                }
 
790
 
 
791
        case intVal:
 
792
                if s == 0 {
 
793
                        return x
 
794
                }
 
795
                var z big.Int
 
796
                switch op {
 
797
                case token.SHL:
 
798
                        return normInt(z.Lsh(x.val, s))
 
799
                case token.SHR:
 
800
                        return normInt(z.Rsh(x.val, s))
 
801
                }
 
802
        }
 
803
 
 
804
        panic(fmt.Sprintf("invalid shift %v %s %d", x, op, s))
 
805
}
 
806
 
 
807
func cmpZero(x int, op token.Token) bool {
 
808
        switch op {
 
809
        case token.EQL:
 
810
                return x == 0
 
811
        case token.NEQ:
 
812
                return x != 0
 
813
        case token.LSS:
 
814
                return x < 0
 
815
        case token.LEQ:
 
816
                return x <= 0
 
817
        case token.GTR:
 
818
                return x > 0
 
819
        case token.GEQ:
 
820
                return x >= 0
 
821
        }
 
822
        panic("unreachable")
 
823
}
 
824
 
 
825
// Compare returns the result of the comparison x op y.
 
826
// The comparison must be defined for the operands.
 
827
// If one of the operands is Unknown, the result is
 
828
// false.
 
829
//
 
830
func Compare(x Value, op token.Token, y Value) bool {
 
831
        x, y = match(x, y)
 
832
 
 
833
        switch x := x.(type) {
 
834
        case unknownVal:
 
835
                return false
 
836
 
 
837
        case boolVal:
 
838
                y := y.(boolVal)
 
839
                switch op {
 
840
                case token.EQL:
 
841
                        return x == y
 
842
                case token.NEQ:
 
843
                        return x != y
 
844
                }
 
845
 
 
846
        case int64Val:
 
847
                y := y.(int64Val)
 
848
                switch op {
 
849
                case token.EQL:
 
850
                        return x == y
 
851
                case token.NEQ:
 
852
                        return x != y
 
853
                case token.LSS:
 
854
                        return x < y
 
855
                case token.LEQ:
 
856
                        return x <= y
 
857
                case token.GTR:
 
858
                        return x > y
 
859
                case token.GEQ:
 
860
                        return x >= y
 
861
                }
 
862
 
 
863
        case intVal:
 
864
                return cmpZero(x.val.Cmp(y.(intVal).val), op)
 
865
 
 
866
        case floatVal:
 
867
                return cmpZero(x.val.Cmp(y.(floatVal).val), op)
 
868
 
 
869
        case complexVal:
 
870
                y := y.(complexVal)
 
871
                re := x.re.Cmp(y.re)
 
872
                im := x.im.Cmp(y.im)
 
873
                switch op {
 
874
                case token.EQL:
 
875
                        return re == 0 && im == 0
 
876
                case token.NEQ:
 
877
                        return re != 0 || im != 0
 
878
                }
 
879
 
 
880
        case stringVal:
 
881
                y := y.(stringVal)
 
882
                switch op {
 
883
                case token.EQL:
 
884
                        return x == y
 
885
                case token.NEQ:
 
886
                        return x != y
 
887
                case token.LSS:
 
888
                        return x < y
 
889
                case token.LEQ:
 
890
                        return x <= y
 
891
                case token.GTR:
 
892
                        return x > y
 
893
                case token.GEQ:
 
894
                        return x >= y
 
895
                }
 
896
        }
 
897
 
 
898
        panic(fmt.Sprintf("invalid comparison %v %s %v", x, op, y))
 
899
}