1// Copyright 2017 The Bazel 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 5package starlark 6 7import ( 8 "fmt" 9 "math" 10 "math/big" 11 "reflect" 12 "strconv" 13 14 "go.starlark.net/syntax" 15) 16 17// Int is the type of a Starlark int. 18// 19// The zero value is not a legal value; use MakeInt(0). 20type Int struct{ impl intImpl } 21 22// --- high-level accessors --- 23 24// MakeInt returns a Starlark int for the specified signed integer. 25func MakeInt(x int) Int { return MakeInt64(int64(x)) } 26 27// MakeInt64 returns a Starlark int for the specified int64. 28func MakeInt64(x int64) Int { 29 if math.MinInt32 <= x && x <= math.MaxInt32 { 30 return makeSmallInt(x) 31 } 32 return makeBigInt(big.NewInt(x)) 33} 34 35// MakeUint returns a Starlark int for the specified unsigned integer. 36func MakeUint(x uint) Int { return MakeUint64(uint64(x)) } 37 38// MakeUint64 returns a Starlark int for the specified uint64. 39func MakeUint64(x uint64) Int { 40 if x <= math.MaxInt32 { 41 return makeSmallInt(int64(x)) 42 } 43 return makeBigInt(new(big.Int).SetUint64(x)) 44} 45 46// MakeBigInt returns a Starlark int for the specified big.Int. 47// The new Int value will contain a copy of x. The caller is safe to modify x. 48func MakeBigInt(x *big.Int) Int { 49 if n := x.BitLen(); n < 32 || n == 32 && x.Int64() == math.MinInt32 { 50 return makeSmallInt(x.Int64()) 51 } 52 z := new(big.Int).Set(x) 53 return makeBigInt(z) 54} 55 56var ( 57 zero, one = makeSmallInt(0), makeSmallInt(1) 58 oneBig = big.NewInt(1) 59 60 _ HasUnary = Int{} 61) 62 63// Unary implements the operations +int, -int, and ~int. 64func (i Int) Unary(op syntax.Token) (Value, error) { 65 switch op { 66 case syntax.MINUS: 67 return zero.Sub(i), nil 68 case syntax.PLUS: 69 return i, nil 70 case syntax.TILDE: 71 return i.Not(), nil 72 } 73 return nil, nil 74} 75 76// Int64 returns the value as an int64. 77// If it is not exactly representable the result is undefined and ok is false. 78func (i Int) Int64() (_ int64, ok bool) { 79 iSmall, iBig := i.get() 80 if iBig != nil { 81 x, acc := bigintToInt64(iBig) 82 if acc != big.Exact { 83 return // inexact 84 } 85 return x, true 86 } 87 return iSmall, true 88} 89 90// BigInt returns a new big.Int with the same value as the Int. 91func (i Int) BigInt() *big.Int { 92 iSmall, iBig := i.get() 93 if iBig != nil { 94 return new(big.Int).Set(iBig) 95 } 96 return big.NewInt(iSmall) 97} 98 99// bigInt returns the value as a big.Int. 100// It differs from BigInt in that this method returns the actual 101// reference and any modification will change the state of i. 102func (i Int) bigInt() *big.Int { 103 iSmall, iBig := i.get() 104 if iBig != nil { 105 return iBig 106 } 107 return big.NewInt(iSmall) 108} 109 110// Uint64 returns the value as a uint64. 111// If it is not exactly representable the result is undefined and ok is false. 112func (i Int) Uint64() (_ uint64, ok bool) { 113 iSmall, iBig := i.get() 114 if iBig != nil { 115 x, acc := bigintToUint64(iBig) 116 if acc != big.Exact { 117 return // inexact 118 } 119 return x, true 120 } 121 if iSmall < 0 { 122 return // inexact 123 } 124 return uint64(iSmall), true 125} 126 127// The math/big API should provide this function. 128func bigintToInt64(i *big.Int) (int64, big.Accuracy) { 129 sign := i.Sign() 130 if sign > 0 { 131 if i.Cmp(maxint64) > 0 { 132 return math.MaxInt64, big.Below 133 } 134 } else if sign < 0 { 135 if i.Cmp(minint64) < 0 { 136 return math.MinInt64, big.Above 137 } 138 } 139 return i.Int64(), big.Exact 140} 141 142// The math/big API should provide this function. 143func bigintToUint64(i *big.Int) (uint64, big.Accuracy) { 144 sign := i.Sign() 145 if sign > 0 { 146 if i.BitLen() > 64 { 147 return math.MaxUint64, big.Below 148 } 149 } else if sign < 0 { 150 return 0, big.Above 151 } 152 return i.Uint64(), big.Exact 153} 154 155var ( 156 minint64 = new(big.Int).SetInt64(math.MinInt64) 157 maxint64 = new(big.Int).SetInt64(math.MaxInt64) 158) 159 160func (i Int) Format(s fmt.State, ch rune) { 161 iSmall, iBig := i.get() 162 if iBig != nil { 163 iBig.Format(s, ch) 164 return 165 } 166 big.NewInt(iSmall).Format(s, ch) 167} 168func (i Int) String() string { 169 iSmall, iBig := i.get() 170 if iBig != nil { 171 return iBig.Text(10) 172 } 173 return strconv.FormatInt(iSmall, 10) 174} 175func (i Int) Type() string { return "int" } 176func (i Int) Freeze() {} // immutable 177func (i Int) Truth() Bool { return i.Sign() != 0 } 178func (i Int) Hash() (uint32, error) { 179 iSmall, iBig := i.get() 180 var lo big.Word 181 if iBig != nil { 182 lo = iBig.Bits()[0] 183 } else { 184 lo = big.Word(iSmall) 185 } 186 return 12582917 * uint32(lo+3), nil 187} 188func (x Int) CompareSameType(op syntax.Token, v Value, depth int) (bool, error) { 189 y := v.(Int) 190 xSmall, xBig := x.get() 191 ySmall, yBig := y.get() 192 if xBig != nil || yBig != nil { 193 return threeway(op, x.bigInt().Cmp(y.bigInt())), nil 194 } 195 return threeway(op, signum64(xSmall-ySmall)), nil 196} 197 198// Float returns the float value nearest i. 199func (i Int) Float() Float { 200 iSmall, iBig := i.get() 201 if iBig != nil { 202 f, _ := new(big.Float).SetInt(iBig).Float64() 203 return Float(f) 204 } 205 return Float(iSmall) 206} 207 208// finiteFloat returns the finite float value nearest i, 209// or an error if the magnitude is too large. 210func (i Int) finiteFloat() (Float, error) { 211 f := i.Float() 212 if math.IsInf(float64(f), 0) { 213 return 0, fmt.Errorf("int too large to convert to float") 214 } 215 return f, nil 216} 217 218func (x Int) Sign() int { 219 xSmall, xBig := x.get() 220 if xBig != nil { 221 return xBig.Sign() 222 } 223 return signum64(xSmall) 224} 225 226func (x Int) Add(y Int) Int { 227 xSmall, xBig := x.get() 228 ySmall, yBig := y.get() 229 if xBig != nil || yBig != nil { 230 return MakeBigInt(new(big.Int).Add(x.bigInt(), y.bigInt())) 231 } 232 return MakeInt64(xSmall + ySmall) 233} 234func (x Int) Sub(y Int) Int { 235 xSmall, xBig := x.get() 236 ySmall, yBig := y.get() 237 if xBig != nil || yBig != nil { 238 return MakeBigInt(new(big.Int).Sub(x.bigInt(), y.bigInt())) 239 } 240 return MakeInt64(xSmall - ySmall) 241} 242func (x Int) Mul(y Int) Int { 243 xSmall, xBig := x.get() 244 ySmall, yBig := y.get() 245 if xBig != nil || yBig != nil { 246 return MakeBigInt(new(big.Int).Mul(x.bigInt(), y.bigInt())) 247 } 248 return MakeInt64(xSmall * ySmall) 249} 250func (x Int) Or(y Int) Int { 251 xSmall, xBig := x.get() 252 ySmall, yBig := y.get() 253 if xBig != nil || yBig != nil { 254 return MakeBigInt(new(big.Int).Or(x.bigInt(), y.bigInt())) 255 } 256 return makeSmallInt(xSmall | ySmall) 257} 258func (x Int) And(y Int) Int { 259 xSmall, xBig := x.get() 260 ySmall, yBig := y.get() 261 if xBig != nil || yBig != nil { 262 return MakeBigInt(new(big.Int).And(x.bigInt(), y.bigInt())) 263 } 264 return makeSmallInt(xSmall & ySmall) 265} 266func (x Int) Xor(y Int) Int { 267 xSmall, xBig := x.get() 268 ySmall, yBig := y.get() 269 if xBig != nil || yBig != nil { 270 return MakeBigInt(new(big.Int).Xor(x.bigInt(), y.bigInt())) 271 } 272 return makeSmallInt(xSmall ^ ySmall) 273} 274func (x Int) Not() Int { 275 xSmall, xBig := x.get() 276 if xBig != nil { 277 return MakeBigInt(new(big.Int).Not(xBig)) 278 } 279 return makeSmallInt(^xSmall) 280} 281func (x Int) Lsh(y uint) Int { return MakeBigInt(new(big.Int).Lsh(x.bigInt(), y)) } 282func (x Int) Rsh(y uint) Int { return MakeBigInt(new(big.Int).Rsh(x.bigInt(), y)) } 283 284// Precondition: y is nonzero. 285func (x Int) Div(y Int) Int { 286 xSmall, xBig := x.get() 287 ySmall, yBig := y.get() 288 // http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floors.html 289 if xBig != nil || yBig != nil { 290 xb, yb := x.bigInt(), y.bigInt() 291 292 var quo, rem big.Int 293 quo.QuoRem(xb, yb, &rem) 294 if (xb.Sign() < 0) != (yb.Sign() < 0) && rem.Sign() != 0 { 295 quo.Sub(&quo, oneBig) 296 } 297 return MakeBigInt(&quo) 298 } 299 quo := xSmall / ySmall 300 rem := xSmall % ySmall 301 if (xSmall < 0) != (ySmall < 0) && rem != 0 { 302 quo -= 1 303 } 304 return MakeInt64(quo) 305} 306 307// Precondition: y is nonzero. 308func (x Int) Mod(y Int) Int { 309 xSmall, xBig := x.get() 310 ySmall, yBig := y.get() 311 if xBig != nil || yBig != nil { 312 xb, yb := x.bigInt(), y.bigInt() 313 314 var quo, rem big.Int 315 quo.QuoRem(xb, yb, &rem) 316 if (xb.Sign() < 0) != (yb.Sign() < 0) && rem.Sign() != 0 { 317 rem.Add(&rem, yb) 318 } 319 return MakeBigInt(&rem) 320 } 321 rem := xSmall % ySmall 322 if (xSmall < 0) != (ySmall < 0) && rem != 0 { 323 rem += ySmall 324 } 325 return makeSmallInt(rem) 326} 327 328func (i Int) rational() *big.Rat { 329 iSmall, iBig := i.get() 330 if iBig != nil { 331 return new(big.Rat).SetInt(iBig) 332 } 333 return new(big.Rat).SetInt64(iSmall) 334} 335 336// AsInt32 returns the value of x if is representable as an int32. 337func AsInt32(x Value) (int, error) { 338 i, ok := x.(Int) 339 if !ok { 340 return 0, fmt.Errorf("got %s, want int", x.Type()) 341 } 342 iSmall, iBig := i.get() 343 if iBig != nil { 344 return 0, fmt.Errorf("%s out of range", i) 345 } 346 return int(iSmall), nil 347} 348 349// AsInt sets *ptr to the value of Starlark int x, if it is exactly representable, 350// otherwise it returns an error. 351// The type of ptr must be one of the pointer types *int, *int8, *int16, *int32, or *int64, 352// or one of their unsigned counterparts including *uintptr. 353func AsInt(x Value, ptr interface{}) error { 354 xint, ok := x.(Int) 355 if !ok { 356 return fmt.Errorf("got %s, want int", x.Type()) 357 } 358 359 bits := reflect.TypeOf(ptr).Elem().Size() * 8 360 switch ptr.(type) { 361 case *int, *int8, *int16, *int32, *int64: 362 i, ok := xint.Int64() 363 if !ok || bits < 64 && !(-1<<(bits-1) <= i && i < 1<<(bits-1)) { 364 return fmt.Errorf("%s out of range (want value in signed %d-bit range)", xint, bits) 365 } 366 switch ptr := ptr.(type) { 367 case *int: 368 *ptr = int(i) 369 case *int8: 370 *ptr = int8(i) 371 case *int16: 372 *ptr = int16(i) 373 case *int32: 374 *ptr = int32(i) 375 case *int64: 376 *ptr = int64(i) 377 } 378 379 case *uint, *uint8, *uint16, *uint32, *uint64, *uintptr: 380 i, ok := xint.Uint64() 381 if !ok || bits < 64 && i >= 1<<bits { 382 return fmt.Errorf("%s out of range (want value in unsigned %d-bit range)", xint, bits) 383 } 384 switch ptr := ptr.(type) { 385 case *uint: 386 *ptr = uint(i) 387 case *uint8: 388 *ptr = uint8(i) 389 case *uint16: 390 *ptr = uint16(i) 391 case *uint32: 392 *ptr = uint32(i) 393 case *uint64: 394 *ptr = uint64(i) 395 case *uintptr: 396 *ptr = uintptr(i) 397 } 398 default: 399 panic(fmt.Sprintf("invalid argument type: %T", ptr)) 400 } 401 return nil 402} 403 404// NumberToInt converts a number x to an integer value. 405// An int is returned unchanged, a float is truncated towards zero. 406// NumberToInt reports an error for all other values. 407func NumberToInt(x Value) (Int, error) { 408 switch x := x.(type) { 409 case Int: 410 return x, nil 411 case Float: 412 f := float64(x) 413 if math.IsInf(f, 0) { 414 return zero, fmt.Errorf("cannot convert float infinity to integer") 415 } else if math.IsNaN(f) { 416 return zero, fmt.Errorf("cannot convert float NaN to integer") 417 } 418 return finiteFloatToInt(x), nil 419 420 } 421 return zero, fmt.Errorf("cannot convert %s to int", x.Type()) 422} 423 424// finiteFloatToInt converts f to an Int, truncating towards zero. 425// f must be finite. 426func finiteFloatToInt(f Float) Int { 427 if math.MinInt64 <= f && f <= math.MaxInt64 { 428 // small values 429 return MakeInt64(int64(f)) 430 } 431 rat := f.rational() 432 if rat == nil { 433 panic(f) // non-finite 434 } 435 return MakeBigInt(new(big.Int).Div(rat.Num(), rat.Denom())) 436} 437