• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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