Skip to main content

dive_value/
int.rs

1//! TLA+ integers in both modes: TLC's 32-bit semantics and arbitrary precision.
2//!
3//! Port of the integer semantics of `tlc2.module.Naturals` and `tlc2.module.Integers`
4//! (tlaplus `94d0c50`): which operations overflow, the overflow messages, floored
5//! `\div`, non-negative `%`, and the rejection of literals above `2^31 - 1`
6//! (`tlc2.tool.impl.SpecProcessor`, `NumeralKind`). [`Int::div`] is
7//! `Integers.Divide`; [`Int::div_naturals`] is `Naturals.Divide`, which TLC uses for
8//! a specification that loads `Naturals` but not `Integers` (fixture `RvNatDiv`).
9//! An earlier note here said TLC always uses `Integers.Divide`: that was measured
10//! with `-dumpTrace json`, which itself loads `Integers` (issue #35).
11
12use std::cmp::Ordering;
13use std::fmt;
14use std::sync::Arc;
15
16use num_bigint::BigInt;
17use num_integer::Integer as _;
18use num_traits::{One, Signed, ToPrimitive};
19
20use crate::ctx::IntMode;
21use crate::error::{ErrorKind, Result, ValueError};
22
23/// An integer: inline when it fits in an `i64`, otherwise a shared big integer.
24///
25/// Constructors keep the representation canonical (`Big` only outside `i64` range);
26/// equality, ordering and hashing are numeric even for a hand-built non-canonical `Big`.
27#[derive(Clone)]
28pub enum Int {
29    /// A value in `i64` range.
30    Small(i64),
31    /// A value outside `i64` range.
32    Big(Arc<BigInt>),
33}
34
35/// The largest exponent bit-size dive will compute in big mode: results above
36/// 2^26 bits (8 MiB) are refused with [`ErrorKind::DiveLimit`].
37const MAX_POW_BITS: u64 = 1 << 26;
38
39fn overflow(what: &str) -> ValueError {
40    ValueError::new(
41        ErrorKind::Overflow,
42        format!("Overflow when computing {what}"),
43    )
44}
45
46impl Int {
47    /// Zero.
48    pub const ZERO: Self = Self::Small(0);
49    /// One.
50    pub const ONE: Self = Self::Small(1);
51
52    /// Converts a big integer, keeping the representation canonical.
53    #[must_use]
54    pub fn from_big(b: BigInt) -> Self {
55        match b.to_i64() {
56            Some(v) => Self::Small(v),
57            None => Self::Big(Arc::new(b)),
58        }
59    }
60
61    /// The value as an `i64`, if it fits.
62    #[must_use]
63    pub fn to_i64(&self) -> Option<i64> {
64        match self {
65            Self::Small(v) => Some(*v),
66            Self::Big(b) => b.to_i64(),
67        }
68    }
69
70    /// The value as an `i32` (a TLC `IntValue`), if it fits.
71    #[must_use]
72    pub fn to_i32(&self) -> Option<i32> {
73        self.to_i64().and_then(|v| i32::try_from(v).ok())
74    }
75
76    /// The value as a big integer.
77    #[must_use]
78    pub fn to_big(&self) -> BigInt {
79        match self {
80            Self::Small(v) => BigInt::from(*v),
81            Self::Big(b) => (**b).clone(),
82        }
83    }
84
85    /// Whether the value is negative.
86    #[must_use]
87    pub fn is_negative(&self) -> bool {
88        match self {
89            Self::Small(v) => *v < 0,
90            Self::Big(b) => b.is_negative(),
91        }
92    }
93
94    /// Parses a decimal numeral as written in a spec.
95    ///
96    /// In [`IntMode::Tlc`] a numeral above `2^31 - 1` is `EC.TLC_INTEGER_TOO_BIG`, even
97    /// when it is the operand of unary minus (`-2147483648` is rejected, as in TLC).
98    ///
99    /// # Errors
100    /// [`ErrorKind::IntegerTooBig`] in TLC mode; [`ErrorKind::Argument`] if `digits` is
101    /// not a non-empty string of ASCII digits.
102    pub fn from_literal(digits: &str, mode: IntMode) -> Result<Self> {
103        if digits.is_empty() || !digits.bytes().all(|b| b.is_ascii_digit()) {
104            return Err(ValueError::new(
105                ErrorKind::Argument,
106                format!("Not a decimal numeral: {digits}"),
107            ));
108        }
109        let big: BigInt = digits.parse().map_err(|_| {
110            ValueError::new(
111                ErrorKind::Argument,
112                format!("Not a decimal numeral: {digits}"),
113            )
114        })?;
115        Self::from_literal_value(big, digits, mode)
116    }
117
118    /// Accepts a numeral already converted to a big integer (for `\b`, `\o`, `\h`
119    /// numerals). `text` is the numeral as SANY prints it, used in the error message.
120    ///
121    /// # Errors
122    /// [`ErrorKind::IntegerTooBig`] in TLC mode when the value exceeds `2^31 - 1`.
123    pub fn from_literal_value(value: BigInt, text: &str, mode: IntMode) -> Result<Self> {
124        let v = Self::from_big(value);
125        if mode == IntMode::Tlc && v.to_i32().is_none() {
126            return Err(ValueError::new(
127                ErrorKind::IntegerTooBig,
128                format!("TLC can't handle a number this big.\n{text}"),
129            ));
130        }
131        Ok(v)
132    }
133
134    fn tlc_operand(&self) -> Result<i32> {
135        self.to_i32().ok_or_else(|| {
136            ValueError::new(
137                ErrorKind::Overflow,
138                format!("Overflow when computing {self} (not a 32-bit TLC integer)"),
139            )
140        })
141    }
142
143    /// `a + b`.
144    ///
145    /// # Errors
146    /// [`ErrorKind::Overflow`] in TLC mode (`Overflow when computing a+b`).
147    pub fn add(&self, other: &Self, mode: IntMode) -> Result<Self> {
148        match mode {
149            IntMode::Tlc => {
150                let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
151                a.checked_add(b)
152                    .map(|r| Self::Small(i64::from(r)))
153                    .ok_or_else(|| overflow(&format!("{a}+{b}")))
154            }
155            IntMode::Big => Ok(match (self, other) {
156                (Self::Small(a), Self::Small(b)) => match a.checked_add(*b) {
157                    Some(r) => Self::Small(r),
158                    None => Self::from_big(BigInt::from(*a) + b),
159                },
160                _ => Self::from_big(self.to_big() + other.to_big()),
161            }),
162        }
163    }
164
165    /// `a - b`.
166    ///
167    /// # Errors
168    /// [`ErrorKind::Overflow`] in TLC mode (`Overflow when computing a-b`).
169    pub fn sub(&self, other: &Self, mode: IntMode) -> Result<Self> {
170        match mode {
171            IntMode::Tlc => {
172                let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
173                a.checked_sub(b)
174                    .map(|r| Self::Small(i64::from(r)))
175                    .ok_or_else(|| overflow(&format!("{a}-{b}")))
176            }
177            IntMode::Big => Ok(match (self, other) {
178                (Self::Small(a), Self::Small(b)) => match a.checked_sub(*b) {
179                    Some(r) => Self::Small(r),
180                    None => Self::from_big(BigInt::from(*a) - b),
181                },
182                _ => Self::from_big(self.to_big() - other.to_big()),
183            }),
184        }
185    }
186
187    /// `a * b`.
188    ///
189    /// # Errors
190    /// [`ErrorKind::Overflow`] in TLC mode (`Overflow when computing a*b`).
191    pub fn mul(&self, other: &Self, mode: IntMode) -> Result<Self> {
192        match mode {
193            IntMode::Tlc => {
194                let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
195                a.checked_mul(b)
196                    .map(|r| Self::Small(i64::from(r)))
197                    .ok_or_else(|| overflow(&format!("{a}*{b}")))
198            }
199            IntMode::Big => Ok(match (self, other) {
200                (Self::Small(a), Self::Small(b)) => match a.checked_mul(*b) {
201                    Some(r) => Self::Small(r),
202                    None => Self::from_big(BigInt::from(*a) * b),
203                },
204                _ => Self::from_big(self.to_big() * other.to_big()),
205            }),
206        }
207    }
208
209    /// Unary minus, `-a` (`Integers.Neg`).
210    ///
211    /// # Errors
212    /// [`ErrorKind::Overflow`] in TLC mode for `-(-2^31)`
213    /// (`Overflow when computing --2147483648`).
214    pub fn neg(&self, mode: IntMode) -> Result<Self> {
215        match mode {
216            IntMode::Tlc => {
217                let a = self.tlc_operand()?;
218                a.checked_neg()
219                    .map(|r| Self::Small(i64::from(r)))
220                    .ok_or_else(|| overflow("--2147483648"))
221            }
222            IntMode::Big => Ok(match self {
223                Self::Small(a) => match a.checked_neg() {
224                    Some(r) => Self::Small(r),
225                    None => Self::from_big(-BigInt::from(*a)),
226                },
227                Self::Big(b) => Self::from_big(-(**b).clone()),
228            }),
229        }
230    }
231
232    /// Floored division, `a \div b` (`Integers.Divide`).
233    ///
234    /// # Errors
235    /// [`ErrorKind::DivisionByZero`] when `b = 0`; [`ErrorKind::Overflow`] in TLC mode
236    /// for `-2^31 \div -1`.
237    pub fn div(&self, other: &Self, mode: IntMode) -> Result<Self> {
238        if other.is_zero() {
239            return Err(ValueError::new(
240                ErrorKind::DivisionByZero,
241                "The second argument of \\div is 0.",
242            ));
243        }
244        match mode {
245            IntMode::Tlc => {
246                let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
247                if a == i32::MIN && b == -1 {
248                    return Err(overflow("-2147483648 \\div -1"));
249                }
250                Ok(Self::Small(i64::from(num_integer::Integer::div_floor(
251                    &a, &b,
252                ))))
253            }
254            IntMode::Big => Ok(match (self, other) {
255                (Self::Small(a), Self::Small(b)) if !(*a == i64::MIN && *b == -1) => {
256                    Self::Small(num_integer::Integer::div_floor(a, b))
257                }
258                _ => Self::from_big(self.to_big().div_floor(&other.to_big())),
259            }),
260        }
261    }
262
263    /// `a \div b` as `Naturals.Divide` computes it, for specifications that load
264    /// `Naturals` but not `Integers`.
265    ///
266    /// In TLC mode this ports `tlc2.module.Naturals.Divide` (tlaplus `94d0c50`):
267    /// Java's truncating `int` division, decremented when the quotient is
268    /// *negative* and inexact. A quotient that truncates to `0` is therefore
269    /// never decremented, so `-1 \div 2` and `1 \div -2` are `0`, not the floored
270    /// `-1`; and `-2147483648 \div -1` wraps to `-2147483648` instead of
271    /// overflowing. In big mode it is floored division, like [`Int::div`].
272    ///
273    /// ```
274    /// use dive_value::{Int, IntMode};
275    /// let q = |a: i64, b: i64| Int::from(a).div_naturals(&Int::from(b), IntMode::Tlc);
276    /// assert_eq!(q(-1, 2)?, Int::from(0_i64));
277    /// assert_eq!(q(-7, 2)?, Int::from(-4_i64));
278    /// assert_eq!(q(-2_147_483_648, -1)?, Int::from(-2_147_483_648_i64));
279    /// assert_eq!(Int::from(-1_i64).div(&Int::from(2_i64), IntMode::Tlc)?, Int::from(-1_i64));
280    /// # Ok::<(), dive_value::ValueError>(())
281    /// ```
282    ///
283    /// # Errors
284    /// [`ErrorKind::DivisionByZero`] when `b = 0`.
285    pub fn div_naturals(&self, other: &Self, mode: IntMode) -> Result<Self> {
286        match mode {
287            IntMode::Tlc => {
288                if other.is_zero() {
289                    return self.div(other, mode);
290                }
291                let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
292                let mut q = a.wrapping_div(b);
293                if q < 0 && q.wrapping_mul(b) != a {
294                    q -= 1;
295                }
296                Ok(Self::Small(i64::from(q)))
297            }
298            IntMode::Big => self.div(other, mode),
299        }
300    }
301
302    /// `a % b`, defined for `b > 0`, with a result in `0 .. b-1` (`Integers.Mod`).
303    ///
304    /// # Errors
305    /// [`ErrorKind::Argument`] when `b <= 0`.
306    pub fn rem(&self, other: &Self, mode: IntMode) -> Result<Self> {
307        if !other.is_positive() {
308            return Err(ValueError::new(
309                ErrorKind::Argument,
310                format!(
311                    "The second argument of % should be a positive number, but instead it is:\n{other}"
312                ),
313            ));
314        }
315        match mode {
316            IntMode::Tlc => {
317                let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
318                Ok(Self::Small(i64::from(num_integer::Integer::mod_floor(
319                    &a, &b,
320                ))))
321            }
322            IntMode::Big => Ok(match (self, other) {
323                (Self::Small(a), Self::Small(b)) => {
324                    Self::Small(num_integer::Integer::mod_floor(a, b))
325                }
326                _ => Self::from_big(self.to_big().mod_floor(&other.to_big())),
327            }),
328        }
329    }
330
331    /// `a ^ b` for `b >= 0` (`Integers.Expt`).
332    ///
333    /// # Errors
334    /// [`ErrorKind::Argument`] when `b < 0`; [`ErrorKind::NullPowerNull`] for `0^0`;
335    /// [`ErrorKind::Overflow`] in TLC mode (`Overflow when computing a^b`);
336    /// [`ErrorKind::DiveLimit`] in big mode when the result would exceed 2^26 bits.
337    pub fn pow(&self, other: &Self, mode: IntMode) -> Result<Self> {
338        if other.is_negative() {
339            return Err(ValueError::new(
340                ErrorKind::Argument,
341                format!(
342                    "The second argument of ^ should be a natural number, but instead it is:\n{other}"
343                ),
344            ));
345        }
346        if other.is_zero() {
347            if self.is_zero() {
348                return Err(ValueError::new(
349                    ErrorKind::NullPowerNull,
350                    "0^0 is undefined.",
351                ));
352            }
353            return Ok(Self::ONE);
354        }
355        match mode {
356            IntMode::Tlc => {
357                let (a, b) = (self.tlc_operand()?, other.tlc_operand()?);
358                let mut res = i64::from(a);
359                for _ in 1..b {
360                    // |res| is non-decreasing for |a| >= 2, and bounded for |a| <= 1,
361                    // so stopping early gives TLC's answer without its O(b) loop.
362                    if a.unsigned_abs() <= 1 {
363                        res = if a == -1 && b % 2 == 0 {
364                            1
365                        } else {
366                            i64::from(a)
367                        };
368                        break;
369                    }
370                    res *= i64::from(a);
371                    if res < i64::from(i32::MIN) || res > i64::from(i32::MAX) {
372                        return Err(overflow(&format!("{a}^{b}")));
373                    }
374                }
375                Ok(Self::Small(res))
376            }
377            IntMode::Big => {
378                let base = self.to_big();
379                if base.abs() <= BigInt::one() {
380                    let odd = other.to_big().is_odd();
381                    return Ok(if base.is_negative() && !odd {
382                        Self::ONE
383                    } else {
384                        self.clone()
385                    });
386                }
387                let exp = other.to_i64().and_then(|e| u64::try_from(e).ok());
388                let bits = base.bits();
389                match exp {
390                    Some(e) if e.saturating_mul(bits) <= MAX_POW_BITS => {
391                        let e = u32::try_from(e).unwrap_or(u32::MAX);
392                        Ok(Self::from_big(num_traits::Pow::pow(base, e)))
393                    }
394                    _ => Err(ValueError::new(
395                        ErrorKind::DiveLimit,
396                        format!(
397                            "The value of {self}^{other} is too large: it exceeds dive's limit of {MAX_POW_BITS} bits."
398                        ),
399                    )),
400                }
401            }
402        }
403    }
404
405    fn is_zero(&self) -> bool {
406        matches!(self, Self::Small(0))
407    }
408
409    fn is_positive(&self) -> bool {
410        match self {
411            Self::Small(v) => *v > 0,
412            Self::Big(b) => b.is_positive(),
413        }
414    }
415}
416
417impl From<i64> for Int {
418    fn from(v: i64) -> Self {
419        Self::Small(v)
420    }
421}
422
423impl From<i32> for Int {
424    fn from(v: i32) -> Self {
425        Self::Small(i64::from(v))
426    }
427}
428
429/// Numeric order. A `Big` that fits in an `i64` (possible only by building the
430/// variant directly) still compares by value.
431impl Ord for Int {
432    fn cmp(&self, other: &Self) -> Ordering {
433        match (self, other) {
434            (Self::Small(a), Self::Small(b)) => a.cmp(b),
435            _ => self.to_big().cmp(&other.to_big()),
436        }
437    }
438}
439
440impl PartialEq for Int {
441    fn eq(&self, other: &Self) -> bool {
442        self.cmp(other) == Ordering::Equal
443    }
444}
445
446impl Eq for Int {}
447
448impl std::hash::Hash for Int {
449    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
450        match self.to_i64() {
451            Some(v) => v.hash(state),
452            None => self.to_big().hash(state),
453        }
454    }
455}
456
457impl PartialOrd for Int {
458    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
459        Some(self.cmp(other))
460    }
461}
462
463impl fmt::Display for Int {
464    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
465        match self {
466            Self::Small(v) => write!(f, "{v}"),
467            Self::Big(b) => write!(f, "{b}"),
468        }
469    }
470}
471
472impl fmt::Debug for Int {
473    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
474        fmt::Display::fmt(self, f)
475    }
476}