1use 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
29pub enum IntMode {
30 #[default]
32 Big,
33 Tlc,
35}
36
37#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub enum IntOp {
40 Add,
42 Sub,
44 Mul,
46 Div,
48 DivNaturals,
51 Mod,
53 Pow,
55}
56
57const MAX_POW_BITS: u64 = 1 << 26;
60
61fn overflow(what: &str) -> Error {
63 Error::eval_class(
64 crate::TlcClass::eval_exception(2178),
65 format!("Overflow when computing {what}"),
66 )
67}
68
69fn 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 #[must_use]
90 pub fn int_mode(&self) -> IntMode {
91 self.int_mode
92 }
93
94 pub fn set_int_mode(&mut self, mode: IntMode) {
96 self.int_mode = mode;
97 }
98
99 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 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 #[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 #[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 #[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 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 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 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
220fn 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
229fn 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
265fn 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
326fn 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 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 let back = h
399 .int_arith(IntOp::Sub, big, int(1))
400 .unwrap_or(Handle::EMPTY);
401 assert_eq!(back, max);
402 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 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}