int.go

Documentation: go.starlark.net/starlark

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