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