Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
351 lines (317 sloc) 8.66 KB
// Copyright 2017 The Bazel Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package starlark
import (
"fmt"
"math"
"math/big"
"strconv"
"go.starlark.net/syntax"
)
// Int is the type of a Starlark int.
type Int struct {
// We use only the signed 32 bit range of small to ensure
// that small+small and small*small do not overflow.
small int64 // minint32 <= small <= maxint32
big *big.Int // big != nil <=> value is not representable as int32
}
// newBig allocates a new big.Int.
func newBig(x int64) *big.Int {
if 0 <= x && int64(big.Word(x)) == x {
// x is guaranteed to fit into a single big.Word.
// Most starlark ints are small,
// but math/big assumes that since you've chosen to use math/big,
// your big.Ints will probably grow, so it over-allocates.
// Avoid that over-allocation by manually constructing a single-word slice.
// See https://golang.org/cl/150999, which will hopefully land in Go 1.13.
return new(big.Int).SetBits([]big.Word{big.Word(x)})
}
return big.NewInt(x)
}
// MakeInt returns a Starlark int for the specified signed integer.
func MakeInt(x int) Int { return MakeInt64(int64(x)) }
// MakeInt64 returns a Starlark int for the specified int64.
func MakeInt64(x int64) Int {
if math.MinInt32 <= x && x <= math.MaxInt32 {
return Int{small: x}
}
return Int{big: newBig(x)}
}
// MakeUint returns a Starlark int for the specified unsigned integer.
func MakeUint(x uint) Int { return MakeUint64(uint64(x)) }
// MakeUint64 returns a Starlark int for the specified uint64.
func MakeUint64(x uint64) Int {
if x <= math.MaxInt32 {
return Int{small: int64(x)}
}
if uint64(big.Word(x)) == x {
// See comment in newBig for an explanation of this optimization.
return Int{big: new(big.Int).SetBits([]big.Word{big.Word(x)})}
}
return Int{big: new(big.Int).SetUint64(x)}
}
// MakeBigInt returns a Starlark int for the specified big.Int.
// The caller must not subsequently modify x.
func MakeBigInt(x *big.Int) Int {
if n := x.BitLen(); n < 32 || n == 32 && x.Int64() == math.MinInt32 {
return Int{small: x.Int64()}
}
return Int{big: x}
}
var (
zero, one = Int{small: 0}, Int{small: 1}
oneBig = newBig(1)
_ HasUnary = Int{}
)
// Unary implements the operations +int, -int, and ~int.
func (i Int) Unary(op syntax.Token) (Value, error) {
switch op {
case syntax.MINUS:
return zero.Sub(i), nil
case syntax.PLUS:
return i, nil
case syntax.TILDE:
return i.Not(), nil
}
return nil, nil
}
// Int64 returns the value as an int64.
// If it is not exactly representable the result is undefined and ok is false.
func (i Int) Int64() (_ int64, ok bool) {
if i.big != nil {
x, acc := bigintToInt64(i.big)
if acc != big.Exact {
return // inexact
}
return x, true
}
return i.small, true
}
// BigInt returns the value as a big.Int.
// The returned variable must not be modified by the client.
func (i Int) BigInt() *big.Int {
if i.big != nil {
return i.big
}
return newBig(i.small)
}
// Uint64 returns the value as a uint64.
// If it is not exactly representable the result is undefined and ok is false.
func (i Int) Uint64() (_ uint64, ok bool) {
if i.big != nil {
x, acc := bigintToUint64(i.big)
if acc != big.Exact {
return // inexact
}
return x, true
}
if i.small < 0 {
return // inexact
}
return uint64(i.small), true
}
// The math/big API should provide this function.
func bigintToInt64(i *big.Int) (int64, big.Accuracy) {
sign := i.Sign()
if sign > 0 {
if i.Cmp(maxint64) > 0 {
return math.MaxInt64, big.Below
}
} else if sign < 0 {
if i.Cmp(minint64) < 0 {
return math.MinInt64, big.Above
}
}
return i.Int64(), big.Exact
}
// The math/big API should provide this function.
func bigintToUint64(i *big.Int) (uint64, big.Accuracy) {
sign := i.Sign()
if sign > 0 {
if i.BitLen() > 64 {
return math.MaxUint64, big.Below
}
} else if sign < 0 {
return 0, big.Above
}
return i.Uint64(), big.Exact
}
var (
minint64 = new(big.Int).SetInt64(math.MinInt64)
maxint64 = new(big.Int).SetInt64(math.MaxInt64)
)
func (i Int) Format(s fmt.State, ch rune) {
if i.big != nil {
i.big.Format(s, ch)
return
}
newBig(i.small).Format(s, ch)
}
func (i Int) String() string {
if i.big != nil {
return i.big.Text(10)
}
return strconv.FormatInt(i.small, 10)
}
func (i Int) Type() string { return "int" }
func (i Int) Freeze() {} // immutable
func (i Int) Truth() Bool { return i.Sign() != 0 }
func (i Int) Hash() (uint32, error) {
var lo big.Word
if i.big != nil {
lo = i.big.Bits()[0]
} else {
lo = big.Word(i.small)
}
return 12582917 * uint32(lo+3), nil
}
func (x Int) CompareSameType(op syntax.Token, v Value, depth int) (bool, error) {
y := v.(Int)
if x.big != nil || y.big != nil {
return threeway(op, x.BigInt().Cmp(y.BigInt())), nil
}
return threeway(op, signum64(x.small-y.small)), nil
}
// Float returns the float value nearest i.
func (i Int) Float() Float {
if i.big != nil {
f, _ := new(big.Float).SetInt(i.big).Float64()
return Float(f)
}
return Float(i.small)
}
func (x Int) Sign() int {
if x.big != nil {
return x.big.Sign()
}
return signum64(x.small)
}
func (x Int) Add(y Int) Int {
if x.big != nil || y.big != nil {
return MakeBigInt(new(big.Int).Add(x.BigInt(), y.BigInt()))
}
return MakeInt64(x.small + y.small)
}
func (x Int) Sub(y Int) Int {
if x.big != nil || y.big != nil {
return MakeBigInt(new(big.Int).Sub(x.BigInt(), y.BigInt()))
}
return MakeInt64(x.small - y.small)
}
func (x Int) Mul(y Int) Int {
if x.big != nil || y.big != nil {
return MakeBigInt(new(big.Int).Mul(x.BigInt(), y.BigInt()))
}
return MakeInt64(x.small * y.small)
}
func (x Int) Or(y Int) Int {
if x.big != nil || y.big != nil {
return Int{big: new(big.Int).Or(x.BigInt(), y.BigInt())}
}
return Int{small: x.small | y.small}
}
func (x Int) And(y Int) Int {
if x.big != nil || y.big != nil {
return MakeBigInt(new(big.Int).And(x.BigInt(), y.BigInt()))
}
return Int{small: x.small & y.small}
}
func (x Int) Xor(y Int) Int {
if x.big != nil || y.big != nil {
return MakeBigInt(new(big.Int).Xor(x.BigInt(), y.BigInt()))
}
return Int{small: x.small ^ y.small}
}
func (x Int) Not() Int {
if x.big != nil {
return MakeBigInt(new(big.Int).Not(x.big))
}
return Int{small: ^x.small}
}
func (x Int) Lsh(y uint) Int { return MakeBigInt(new(big.Int).Lsh(x.BigInt(), y)) }
func (x Int) Rsh(y uint) Int { return MakeBigInt(new(big.Int).Rsh(x.BigInt(), y)) }
// Precondition: y is nonzero.
func (x Int) Div(y Int) Int {
// http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floors.html
if x.big != nil || y.big != nil {
xb, yb := x.BigInt(), y.BigInt()
var quo, rem big.Int
quo.QuoRem(xb, yb, &rem)
if (xb.Sign() < 0) != (yb.Sign() < 0) && rem.Sign() != 0 {
quo.Sub(&quo, oneBig)
}
return MakeBigInt(&quo)
}
quo := x.small / y.small
rem := x.small % y.small
if (x.small < 0) != (y.small < 0) && rem != 0 {
quo -= 1
}
return MakeInt64(quo)
}
// Precondition: y is nonzero.
func (x Int) Mod(y Int) Int {
if x.big != nil || y.big != nil {
xb, yb := x.BigInt(), y.BigInt()
var quo, rem big.Int
quo.QuoRem(xb, yb, &rem)
if (xb.Sign() < 0) != (yb.Sign() < 0) && rem.Sign() != 0 {
rem.Add(&rem, yb)
}
return MakeBigInt(&rem)
}
rem := x.small % y.small
if (x.small < 0) != (y.small < 0) && rem != 0 {
rem += y.small
}
return Int{small: rem}
}
func (i Int) rational() *big.Rat {
if i.big != nil {
return new(big.Rat).SetInt(i.big)
}
return new(big.Rat).SetInt64(i.small)
}
// AsInt32 returns the value of x if is representable as an int32.
func AsInt32(x Value) (int, error) {
i, ok := x.(Int)
if !ok {
return 0, fmt.Errorf("got %s, want int", x.Type())
}
if i.big != nil {
return 0, fmt.Errorf("%s out of range", i)
}
return int(i.small), nil
}
// NumberToInt converts a number x to an integer value.
// An int is returned unchanged, a float is truncated towards zero.
// NumberToInt reports an error for all other values.
func NumberToInt(x Value) (Int, error) {
switch x := x.(type) {
case Int:
return x, nil
case Float:
f := float64(x)
if math.IsInf(f, 0) {
return zero, fmt.Errorf("cannot convert float infinity to integer")
} else if math.IsNaN(f) {
return zero, fmt.Errorf("cannot convert float NaN to integer")
}
return finiteFloatToInt(x), nil
}
return zero, fmt.Errorf("cannot convert %s to int", x.Type())
}
// finiteFloatToInt converts f to an Int, truncating towards zero.
// f must be finite.
func finiteFloatToInt(f Float) Int {
if math.MinInt64 <= f && f <= math.MaxInt64 {
// small values
return MakeInt64(int64(f))
}
rat := f.rational()
if rat == nil {
panic(f) // non-finite
}
return MakeBigInt(new(big.Int).Div(rat.Num(), rat.Denom()))
}
You can’t perform that action at this time.