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 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. 329 func 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. 341 func MakeUnknown() Value { return unknownVal{} } 342 343 // MakeBool returns the Bool value for b. 344 func MakeBool(b bool) Value { return boolVal(b) } 345 346 // MakeString returns the String value for s. 347 func MakeString(s string) Value { return &stringVal{s: s} } 348 349 // MakeInt64 returns the Int value for x. 350 func MakeInt64(x int64) Value { return int64Val(x) } 351 352 // MakeUint64 returns the Int value for x. 353 func 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. 362 func 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. 378 func 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. 431 func 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 "". 444 func 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). 458 func 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). 474 func 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. 488 func 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). 513 func 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. 536 func 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. 552 func 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 580 const ( 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. 589 func 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. 621 func 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. 653 func 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. 675 func 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. 697 func 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. 710 func 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. 723 func 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. 741 func 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. 795 func 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. 814 func 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. 834 func 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. 840 func 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 // 850 func 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 908 Error: 909 panic(fmt.Sprintf("invalid unary operation %s%v", op, y)) 910 } 911 912 func 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 // 940 func 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 // 1011 func 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 1178 Error: 1179 panic(fmt.Sprintf("invalid binary operation %v %s %v", x_, op, y_)) 1180 } 1181 1182 func add(x, y Value) Value { return BinaryOp(x, token.ADD, y) } 1183 func sub(x, y Value) Value { return BinaryOp(x, token.SUB, y) } 1184 func mul(x, y Value) Value { return BinaryOp(x, token.MUL, y) } 1185 func 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 // 1191 func 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 1224 func 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 // 1247 func 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
View as plain text