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