Skip to main content

dive_core/
int.rs

1//! Integers of any size (big integers are the default profile's mode).
2//!
3//! An integer is an inline handle while it fits 61 bits, and otherwise a
4//! compound node of kind [`Kind::BigInt`]: `lo` is the sign (`1` or `-1`)
5//! and `data` the magnitude in 32-bit digits, least significant first, each
6//! an inline integer handle (so the generic walks of the heap never mistake
7//! a digit for a child). The form is canonical, so equal integers have equal
8//! node contents and an inline and a big handle are never equal.
9//!
10//! Arithmetic follows `dive_value::Int` (a port of
11//! `tlc2.module.Naturals` and `tlc2.module.Integers`, tlaplus `94d0c50`):
12//! in [`IntMode::Big`] (the default profile) results are exact; in
13//! [`IntMode::Tlc`] (`--int=tlc`) operands and results are Java `int`s, and
14//! leaving `[-2^31, 2^31 - 1]` is TLC's overflow error, with TLC's message.
15
16use std::cmp::Ordering;
17
18use num_bigint::{BigInt, Sign};
19use num_integer::Integer as _;
20use num_traits::{One, Signed, ToPrimitive, Zero};
21
22use crate::Error;
23use crate::handle::Handle;
24use crate::heap::Heap;
25use crate::node::Kind;
26
27/// The integer semantics of a run.
28#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
29pub enum IntMode {
30    /// Mathematical integers (the default profile).
31    #[default]
32    Big,
33    /// TLC's 32-bit integers (`--int=tlc`, part of `--compat=tlc`).
34    Tlc,
35}
36
37/// A binary integer operation.
38#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub enum IntOp {
40    /// `a + b`.
41    Add,
42    /// `a - b`.
43    Sub,
44    /// `a * b`.
45    Mul,
46    /// `a \div b`, floored (`Integers.Divide`).
47    Div,
48    /// `a \div b` as `Naturals.Divide` computes it, for a specification
49    /// that loads `Naturals` but not `Integers`. Floored in big mode.
50    DivNaturals,
51    /// `a % b`, for `b > 0` (`Integers.Mod`).
52    Mod,
53    /// `a ^ b`, for `b >= 0` (`Integers.Expt`).
54    Pow,
55}
56
57/// The largest result of `^` computed in big mode, in bits (as
58/// `dive_value::Int`).
59const MAX_POW_BITS: u64 = 1 << 26;
60
61/// `EC.TLC_MODULE_OVERFLOW`, an `EvalException`.
62fn overflow(what: &str) -> Error {
63    Error::eval_class(
64        crate::TlcClass::eval_exception(2178),
65        format!("Overflow when computing {what}"),
66    )
67}
68
69/// An `EvalException` of TLC class `code`.
70fn eval_exc(code: u32, what: impl Into<String>) -> Error {
71    Error::eval_class(crate::TlcClass::eval_exception(code), what)
72}
73
74impl IntOp {
75    const fn symbol(self) -> &'static str {
76        match self {
77            Self::Add => "+",
78            Self::Sub => "-",
79            Self::Mul => "*",
80            Self::Div | Self::DivNaturals => " \\div ",
81            Self::Mod => "%",
82            Self::Pow => "^",
83        }
84    }
85}
86
87impl Heap {
88    /// The integer semantics of this heap's arithmetic.
89    #[must_use]
90    pub fn int_mode(&self) -> IntMode {
91        self.int_mode
92    }
93
94    /// Sets the integer semantics (from the run's profile).
95    pub fn set_int_mode(&mut self, mode: IntMode) {
96        self.int_mode = mode;
97    }
98
99    /// An integer, inline when it fits 61 bits.
100    pub fn int_from_i64(&mut self, v: i64) -> Handle {
101        Handle::int(v).unwrap_or_else(|| self.big_node(&BigInt::from(v)))
102    }
103
104    /// An integer, inline when it fits 61 bits.
105    pub fn int_from_big(&mut self, v: &BigInt) -> Handle {
106        match v.to_i64().and_then(Handle::int) {
107            Some(h) => h,
108            None => self.big_node(v),
109        }
110    }
111
112    fn big_node(&mut self, v: &BigInt) -> Handle {
113        let (sign, digits) = v.to_u32_digits();
114        let data: Vec<Handle> = digits
115            .into_iter()
116            .map(|d| Handle::int(i64::from(d)).unwrap_or(Handle::EMPTY))
117            .collect();
118        let sign = if sign == Sign::Minus { -1 } else { 1 };
119        self.symbolic(Kind::BigInt, sign, &data)
120    }
121
122    /// Whether `h` is an integer of any size.
123    #[must_use]
124    pub fn is_int(&self, h: Handle) -> bool {
125        h.as_int().is_some() || (h.is_compound() && self.view(h).kind == Kind::BigInt)
126    }
127
128    /// The value of an integer handle of any size.
129    #[must_use]
130    pub fn big(&self, h: Handle) -> Option<BigInt> {
131        if let Some(v) = h.as_int() {
132            return Some(BigInt::from(v));
133        }
134        if !h.is_compound() {
135            return None;
136        }
137        let v = self.view(h);
138        if v.kind != Kind::BigInt {
139            return None;
140        }
141        let digits: Vec<u32> = v
142            .data
143            .iter()
144            .map(|d| d.as_int().and_then(|x| u32::try_from(x).ok()).unwrap_or(0))
145            .collect();
146        let sign = if v.lo < 0 { Sign::Minus } else { Sign::Plus };
147        Some(BigInt::from_slice(sign, &digits))
148    }
149
150    /// The numeric order of two integers of any size; `None` unless both are
151    /// integers.
152    #[must_use]
153    pub fn int_cmp(&self, a: Handle, b: Handle) -> Option<Ordering> {
154        if let (Some(x), Some(y)) = (a.as_int(), b.as_int()) {
155            return Some(x.cmp(&y));
156        }
157        Some(self.big(a)?.cmp(&self.big(b)?))
158    }
159
160    /// `op(a, b)` under the heap's [`IntMode`].
161    ///
162    /// # Errors
163    /// A non-integer operand; division by zero, `%` by a non-positive
164    /// number, a negative exponent, `0^0`; in TLC mode TLC's overflow; in
165    /// big mode a power above 2^26 bits (unsupported, as the reference).
166    pub fn int_arith(&mut self, op: IntOp, lhs: Handle, rhs: Handle) -> Result<Handle, Error> {
167        if self.int_mode == IntMode::Big
168            && let (Some(x), Some(y)) = (lhs.as_int(), rhs.as_int())
169            && let Some(small) = small_arith(op, x, y)
170        {
171            return small.map(|v| self.int_from_i64(v));
172        }
173        let (Some(x), Some(y)) = (self.big(lhs), self.big(rhs)) else {
174            return Err(Error::eval("expected an integer"));
175        };
176        let value = match self.int_mode {
177            IntMode::Big => big_arith(op, &x, &y)?,
178            IntMode::Tlc => BigInt::from(tlc_arith(op, tlc_operand(&x)?, tlc_operand(&y)?)?),
179        };
180        Ok(self.int_from_big(&value))
181    }
182
183    /// An upper bound, in 64-bit words, on the magnitude of `base ^ exp`
184    /// that [`Heap::int_arith`] would allocate: 0 where the result is inline,
185    /// a Java `int` (TLC mode), an error, or refused above the bit limit
186    /// before allocating. A fuel-bounded machine charges it in advance.
187    pub(crate) fn pow_result_words(&self, base: Handle, exp: Handle) -> u64 {
188        if self.int_mode == IntMode::Tlc {
189            return 0;
190        }
191        let (Some(x), Some(y)) = (self.big(base), self.big(exp)) else {
192            return 0;
193        };
194        if x.abs() <= BigInt::one() || !y.is_positive() {
195            return 0;
196        }
197        let bits = y.to_u64().unwrap_or(u64::MAX).saturating_mul(x.bits());
198        if bits > MAX_POW_BITS { 0 } else { bits / 64 }
199    }
200
201    /// `-a` under the heap's [`IntMode`].
202    ///
203    /// # Errors
204    /// A non-integer operand; in TLC mode `-(-2^31)`.
205    pub fn int_neg(&mut self, a: Handle) -> Result<Handle, Error> {
206        let Some(x) = self.big(a) else {
207            return Err(Error::eval("expected an integer"));
208        };
209        if self.int_mode == IntMode::Tlc {
210            let v = tlc_operand(&x)?;
211            return v
212                .checked_neg()
213                .map(|r| Handle::int(i64::from(r)).unwrap_or(Handle::EMPTY))
214                .ok_or_else(|| overflow("--2147483648"));
215        }
216        Ok(self.int_from_big(&-x))
217    }
218}
219
220/// An operand in TLC mode: a Java `int`.
221fn tlc_operand(v: &BigInt) -> Result<i32, Error> {
222    v.to_i32().ok_or_else(|| {
223        Error::eval(format!(
224            "Overflow when computing {v} (not a 32-bit TLC integer)"
225        ))
226    })
227}
228
229/// The errors that do not depend on the mode, from the operands' signs.
230fn domain_errors(
231    op: IntOp,
232    x_sign: Ordering,
233    y_sign: Ordering,
234    y: &dyn std::fmt::Display,
235) -> Result<(), Error> {
236    match (op, y_sign) {
237        (IntOp::Div | IntOp::DivNaturals, Ordering::Equal) => {
238            Err(eval_exc(2179, "The second argument of \\div is 0."))
239        }
240        (IntOp::Mod, Ordering::Equal | Ordering::Less) => Err(eval_exc(
241            2169,
242            format!(
243                "The second argument of % should be a positive number, but instead it is:\n{y}"
244            ),
245        )),
246        (IntOp::Pow, Ordering::Less) => Err(eval_exc(
247            2169,
248            format!("The second argument of ^ should be a natural number, but instead it is:\n{y}"),
249        )),
250        (IntOp::Pow, Ordering::Equal) if x_sign == Ordering::Equal => {
251            Err(eval_exc(2180, "0^0 is undefined."))
252        }
253        _ => Ok(()),
254    }
255}
256
257fn big_sign(v: &BigInt) -> Ordering {
258    match v.sign() {
259        Sign::Minus => Ordering::Less,
260        Sign::NoSign => Ordering::Equal,
261        Sign::Plus => Ordering::Greater,
262    }
263}
264
265/// Big-mode arithmetic on two `i64`s: `None` when the result needs a big
266/// integer (the slow path then computes it).
267fn small_arith(op: IntOp, x: i64, y: i64) -> Option<Result<i64, Error>> {
268    if let Err(e) = domain_errors(op, x.cmp(&0), y.cmp(&0), &y) {
269        return Some(Err(e));
270    }
271    let r = match op {
272        IntOp::Add => x.checked_add(y),
273        IntOp::Sub => x.checked_sub(y),
274        IntOp::Mul => x.checked_mul(y),
275        IntOp::Div | IntOp::DivNaturals => {
276            if x == i64::MIN && y == -1 {
277                None
278            } else {
279                Some(num_integer::Integer::div_floor(&x, &y))
280            }
281        }
282        IntOp::Mod => Some(x.mod_floor(&y)),
283        IntOp::Pow => {
284            if y == 0 {
285                Some(1)
286            } else {
287                u32::try_from(y).ok().and_then(|e| x.checked_pow(e))
288            }
289        }
290    };
291    r.map(Ok)
292}
293
294fn big_arith(op: IntOp, x: &BigInt, y: &BigInt) -> Result<BigInt, Error> {
295    domain_errors(op, big_sign(x), big_sign(y), y)?;
296    Ok(match op {
297        IntOp::Add => x + y,
298        IntOp::Sub => x - y,
299        IntOp::Mul => x * y,
300        IntOp::Div | IntOp::DivNaturals => x.div_floor(y),
301        IntOp::Mod => x.mod_floor(y),
302        IntOp::Pow => {
303            if y.is_zero() {
304                return Ok(BigInt::one());
305            }
306            if x.abs() <= BigInt::one() {
307                return Ok(if x.is_negative() && y.is_even() {
308                    BigInt::one()
309                } else {
310                    x.clone()
311                });
312            }
313            let e = y
314                .to_u64()
315                .filter(|e| e.saturating_mul(x.bits()) <= MAX_POW_BITS);
316            let Some(e) = e.and_then(|e| u32::try_from(e).ok()) else {
317                return Err(Error::unsupported(format!(
318                    "The value of {x}^{y} is too large: it exceeds dive's limit of {MAX_POW_BITS} bits."
319                )));
320            };
321            num_traits::Pow::pow(x, e)
322        }
323    })
324}
325
326/// TLC-mode arithmetic on Java `int`s (`Naturals`, `Integers`).
327fn tlc_arith(op: IntOp, a: i32, b: i32) -> Result<i32, Error> {
328    domain_errors(op, a.cmp(&0), b.cmp(&0), &b)?;
329    let what = || format!("{a}{}{b}", op.symbol());
330    match op {
331        IntOp::Add => a.checked_add(b).ok_or_else(|| overflow(&what())),
332        IntOp::Sub => a.checked_sub(b).ok_or_else(|| overflow(&what())),
333        IntOp::Mul => a.checked_mul(b).ok_or_else(|| overflow(&what())),
334        IntOp::Div => {
335            if a == i32::MIN && b == -1 {
336                return Err(overflow("-2147483648 \\div -1"));
337            }
338            Ok(num_integer::Integer::div_floor(&a, &b))
339        }
340        IntOp::DivNaturals => {
341            // `Naturals.Divide`: Java's truncating division, decremented
342            // only when the quotient is negative and inexact; wraps on
343            // `-2^31 \div -1`.
344            let mut q = a.wrapping_div(b);
345            if q < 0 && q.wrapping_mul(b) != a {
346                q -= 1;
347            }
348            Ok(q)
349        }
350        IntOp::Mod => Ok(a.mod_floor(&b)),
351        IntOp::Pow => {
352            if b == 0 {
353                return Ok(1);
354            }
355            if a.unsigned_abs() <= 1 {
356                return Ok(if a == -1 && b % 2 == 0 { 1 } else { a });
357            }
358            let mut res = i64::from(a);
359            for _ in 1..b {
360                res *= i64::from(a);
361                if res < i64::from(i32::MIN) || res > i64::from(i32::MAX) {
362                    return Err(overflow(&format!("{a}^{b}")));
363                }
364            }
365            i32::try_from(res).map_err(|_| overflow(&format!("{a}^{b}")))
366        }
367    }
368}
369
370#[cfg(test)]
371mod tests {
372    use std::sync::Arc;
373
374    use super::*;
375    use crate::store::Store;
376
377    fn heap(mode: IntMode) -> Heap {
378        let mut h = Heap::new(Arc::new(Store::default()), false, false);
379        h.set_int_mode(mode);
380        h
381    }
382
383    fn int(v: i64) -> Handle {
384        Handle::int(v).unwrap_or(Handle::EMPTY)
385    }
386
387    #[test]
388    fn big_mode_spills_and_returns_canonically() {
389        let mut h = heap(IntMode::Big);
390        let max = int(crate::handle::INT_MAX);
391        let big = h
392            .int_arith(IntOp::Add, max, int(1))
393            .unwrap_or(Handle::EMPTY);
394        assert!(big.is_compound());
395        assert_eq!(h.kind(big), Some(Kind::BigInt));
396        assert_eq!(h.big(big), Some(BigInt::from(crate::handle::INT_MAX) + 1));
397        // Back into range: inline again.
398        let back = h
399            .int_arith(IntOp::Sub, big, int(1))
400            .unwrap_or(Handle::EMPTY);
401        assert_eq!(back, max);
402        // 2^100, interned and compared.
403        let p = h
404            .int_arith(IntOp::Pow, int(2), int(100))
405            .unwrap_or(Handle::EMPTY);
406        let q = h.int_arith(IntOp::Mul, p, int(1)).unwrap_or(Handle::EMPTY);
407        assert!(h.eq(p, q));
408        assert_eq!(h.hash(p), h.hash(q));
409        let (pp, pq) = (
410            h.intern(p).unwrap_or(Handle::EMPTY),
411            h.intern(q).unwrap_or(Handle::EMPTY),
412        );
413        assert_eq!(pp, pq);
414        let n = h.int_neg(p).unwrap_or(Handle::EMPTY);
415        assert_eq!(h.int_cmp(n, int(0)), Some(Ordering::Less));
416        assert_eq!(
417            h.int_cmp(p, int(i64::from(i32::MAX))),
418            Some(Ordering::Greater)
419        );
420        assert!(!h.poisoned());
421    }
422
423    #[test]
424    fn big_integers_order_among_integers() {
425        let mut hp = heap(IntMode::Big);
426        let big = hp
427            .int_arith(IntOp::Pow, int(10), int(30))
428            .unwrap_or(Handle::EMPTY);
429        let neg = hp.int_neg(big).unwrap_or(Handle::EMPTY);
430        let text = hp.string("a").unwrap_or(Handle::EMPTY);
431        let empty = hp.empty_set();
432        let mut v = vec![text, big, int(3), empty, Handle::TRUE, neg];
433        let set = hp.set_from(&mut v);
434        let got = hp.view(set).data.to_vec();
435        assert_eq!(got, vec![Handle::TRUE, neg, int(3), big, text, empty]);
436        assert!(!hp.poisoned());
437    }
438
439    #[test]
440    fn floored_division_and_modulus() {
441        let mut h = heap(IntMode::Big);
442        let q = |h: &mut Heap, op, a, b| {
443            h.int_arith(op, int(a), int(b))
444                .ok()
445                .and_then(Handle::as_int)
446        };
447        assert_eq!(q(&mut h, IntOp::Div, -7, 2), Some(-4));
448        assert_eq!(q(&mut h, IntOp::Mod, -7, 2), Some(1));
449        assert_eq!(
450            q(&mut h, IntOp::DivNaturals, -1, 2),
451            Some(-1),
452            "floored in big mode"
453        );
454        assert!(h.int_arith(IntOp::Div, int(1), int(0)).is_err());
455        assert!(h.int_arith(IntOp::Mod, int(1), int(0)).is_err());
456        assert!(h.int_arith(IntOp::Pow, int(0), int(0)).is_err());
457        assert!(h.int_arith(IntOp::Pow, int(2), int(-1)).is_err());
458        assert_eq!(q(&mut h, IntOp::Pow, -1, 7), Some(-1));
459    }
460
461    #[test]
462    fn tlc_mode_reproduces_tlc_overflow() {
463        let mut h = heap(IntMode::Tlc);
464        let msg = |r: Result<Handle, Error>| r.err().map(|e| e.message().to_owned());
465        assert_eq!(
466            msg(h.int_arith(IntOp::Add, int(2_147_483_647), int(1))),
467            Some("Overflow when computing 2147483647+1".to_owned())
468        );
469        assert_eq!(
470            msg(h.int_arith(IntOp::Mul, int(65536), int(32768))),
471            Some("Overflow when computing 65536*32768".to_owned())
472        );
473        assert_eq!(
474            msg(h.int_arith(IntOp::Pow, int(2), int(31))),
475            Some("Overflow when computing 2^31".to_owned())
476        );
477        assert_eq!(
478            msg(h.int_neg(int(-2_147_483_648))),
479            Some("Overflow when computing --2147483648".to_owned())
480        );
481        assert_eq!(
482            msg(h.int_arith(IntOp::Div, int(-2_147_483_648), int(-1))),
483            Some("Overflow when computing -2147483648 \\div -1".to_owned())
484        );
485        // `Naturals.Divide` truncates toward zero when the quotient is 0,
486        // and wraps instead of overflowing.
487        let q = |h: &mut Heap, a, b| {
488            h.int_arith(IntOp::DivNaturals, int(a), int(b))
489                .ok()
490                .and_then(Handle::as_int)
491        };
492        assert_eq!(q(&mut h, -1, 2), Some(0));
493        assert_eq!(q(&mut h, -7, 2), Some(-4));
494        assert_eq!(q(&mut h, -2_147_483_648, -1), Some(-2_147_483_648));
495        assert_eq!(
496            h.int_arith(IntOp::Pow, int(2), int(30))
497                .ok()
498                .and_then(Handle::as_int),
499            Some(1 << 30)
500        );
501    }
502}