#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use core::sync::atomic::{AtomicU64, Ordering};
use crate::coeff::{
rat_add, rat_div, rat_mul, rat_normalize, Overflow, Plethystic, QAlgebra, Ring,
};
static OVERFLOWS: AtomicU64 = AtomicU64::new(0);
#[cold]
#[inline(never)]
fn note_overflow() {
OVERFLOWS.fetch_add(1, Ordering::Relaxed);
}
pub fn guarded<T>(f: impl FnOnce() -> T) -> Option<T> {
let before = OVERFLOWS.load(Ordering::Relaxed);
let value = f();
(OVERFLOWS.load(Ordering::Relaxed) == before).then_some(value)
}
pub fn overflow_count() -> u64 {
OVERFLOWS.load(Ordering::Relaxed)
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub struct Guarded(pub i128);
crate::coeff::impl_ring_ops!([] Guarded);
crate::coeff::impl_ring_ops!([] GuardedRat);
impl Ring for Guarded {
#[inline]
fn zero() -> Self {
Guarded(0)
}
#[inline]
fn one() -> Self {
Guarded(1)
}
#[inline]
fn is_zero(&self) -> bool {
self.0 == 0
}
#[inline]
fn add_assign(&mut self, other: &Self) {
match self.0.checked_add(other.0) {
Some(v) => self.0 = v,
None => note_overflow(),
}
}
#[inline]
fn mul(&self, other: &Self) -> Self {
match self.0.checked_mul(other.0) {
Some(v) => Guarded(v),
None => {
note_overflow();
Guarded(0)
}
}
}
#[inline]
fn neg(&self) -> Self {
match self.0.checked_neg() {
Some(v) => Guarded(v),
None => {
note_overflow();
Guarded(0)
}
}
}
#[inline]
fn from_i64(n: i64) -> Self {
Guarded(n as i128)
}
#[inline]
fn from_u128(n: u128) -> Self {
if n > i128::MAX as u128 {
note_overflow();
return Guarded(0);
}
Guarded(n as i128)
}
#[inline]
fn from_i128(n: i128) -> Self {
Guarded(n)
}
#[inline]
fn try_from_u128(n: u128) -> Option<Self> {
i128::try_from(n).ok().map(Guarded)
}
#[inline]
fn try_from_i128(n: i128) -> Option<Self> {
Some(Guarded(n))
}
#[inline]
fn div_exact(&self, other: &Self) -> Option<Self> {
if other.0 == -1 {
return Some(self.neg());
}
crate::coeff::div_exact_i128(self.0, other.0).map(Guarded)
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct GuardedRat {
num: i128,
den: i128,
}
struct Reporting;
impl Overflow for Reporting {
#[inline]
fn add(a: i128, b: i128) -> i128 {
ck(a.checked_add(b))
}
#[inline]
fn mul(a: i128, b: i128) -> i128 {
ck(a.checked_mul(b))
}
}
#[inline]
fn ck(v: Option<i128>) -> i128 {
match v {
Some(x) => x,
None => {
note_overflow();
0
}
}
}
impl GuardedRat {
fn new(num: i128, den: i128) -> Self {
if den == 0 {
note_overflow();
return GuardedRat { num: 0, den: 1 };
}
if num == 0 {
return GuardedRat { num: 0, den: 1 };
}
if num == i128::MIN || den == i128::MIN {
note_overflow();
return GuardedRat { num: 0, den: 1 };
}
let (num, den) = rat_normalize(num, den);
GuardedRat { num, den }
}
#[inline]
fn reduced((num, den): (i128, i128)) -> Self {
if den <= 0 || num == i128::MIN {
note_overflow();
return GuardedRat { num: 0, den: 1 };
}
if num == 0 {
return GuardedRat { num: 0, den: 1 };
}
GuardedRat { num, den }
}
pub fn numer(&self) -> i128 {
self.num
}
pub fn denom(&self) -> i128 {
self.den
}
}
impl Ring for GuardedRat {
fn zero() -> Self {
GuardedRat { num: 0, den: 1 }
}
fn one() -> Self {
GuardedRat { num: 1, den: 1 }
}
fn is_zero(&self) -> bool {
self.num == 0
}
fn add_assign(&mut self, other: &Self) {
*self = GuardedRat::reduced(rat_add::<Reporting>(
self.num, self.den, other.num, other.den,
));
}
fn mul(&self, other: &Self) -> Self {
GuardedRat::reduced(rat_mul::<Reporting>(
self.num, self.den, other.num, other.den,
))
}
fn neg(&self) -> Self {
match self.num.checked_neg() {
Some(num) => GuardedRat { num, den: self.den },
None => {
note_overflow();
<Self as Ring>::zero()
}
}
}
fn from_i64(n: i64) -> Self {
GuardedRat {
num: n as i128,
den: 1,
}
}
fn from_u128(n: u128) -> Self {
if n > i128::MAX as u128 {
note_overflow();
return <Self as Ring>::zero();
}
GuardedRat {
num: n as i128,
den: 1,
}
}
fn from_i128(n: i128) -> Self {
if n == i128::MIN {
note_overflow();
return <Self as Ring>::zero();
}
GuardedRat { num: n, den: 1 }
}
fn try_from_u128(n: u128) -> Option<Self> {
i128::try_from(n).ok().map(|num| GuardedRat { num, den: 1 })
}
fn try_from_i128(n: i128) -> Option<Self> {
(n != i128::MIN).then_some(GuardedRat { num: n, den: 1 })
}
fn as_ratio(&self) -> Option<(i128, i128)> {
Some((self.num, self.den))
}
fn from_ratio(num: i128, den: i128) -> Option<Self> {
(den != 0).then(|| GuardedRat::new(num, den))
}
}
impl QAlgebra for GuardedRat {
fn div_u128(&self, n: u128) -> Self {
if n == 0 {
note_overflow();
return <Self as Ring>::zero();
}
if n > i128::MAX as u128 {
note_overflow();
return <Self as Ring>::zero();
}
let n = n as i128;
GuardedRat::reduced(rat_div::<Reporting>(self.num, self.den, n))
}
}
impl crate::coeff::Integral for Guarded {
fn gcd(&self, other: &Self) -> Self {
Guarded(crate::coeff::gcd_i128(self.0, other.0))
}
fn is_negative(&self) -> bool {
self.0 < 0
}
}
impl crate::coeff::Integral for GuardedRat {
fn gcd(&self, other: &Self) -> Self {
if self.is_zero() && other.is_zero() {
<Self as Ring>::zero()
} else {
<Self as Ring>::one()
}
}
fn is_negative(&self) -> bool {
self.num < 0
}
}
impl Plethystic for GuardedRat {
fn frobenius(&self, _n: u32) -> Self {
*self
}
}
#[cfg(test)]
pub(crate) fn serial() -> std::sync::MutexGuard<'static, ()> {
static SERIAL: std::sync::Mutex<()> = std::sync::Mutex::new(());
SERIAL.lock().unwrap_or_else(|e| e.into_inner())
}
#[cfg(test)]
mod tests {
use super::serial;
use super::*;
use crate::coeff::Rational;
use crate::convert::FromSchur;
use crate::partition::Partition;
use crate::sym::{PowerSum, Schur, SymFn};
#[test]
fn arithmetic_inside_the_range_reports_nothing() {
let _g = serial();
let r = guarded(|| {
let a = Guarded(1_000_000);
let b = a.mul(&a);
let mut c = b;
c.add_assign(&b);
c
});
assert_eq!(r, Some(Guarded(2_000_000_000_000)));
}
#[test]
fn multiplication_past_the_width_is_reported() {
let _g = serial();
let r = guarded(|| Guarded(i128::MAX / 2).mul(&Guarded(4)));
assert_eq!(r, None, "overflowing product must not be returned");
}
#[test]
fn addition_past_the_width_is_reported() {
let _g = serial();
let r = guarded(|| {
let mut a = Guarded(i128::MAX);
a.add_assign(&Guarded(1));
a
});
assert_eq!(r, None);
}
#[test]
fn u128_injection_past_i128_is_reported() {
let _g = serial();
let r = guarded(|| <Guarded as Ring>::from_u128(u128::MAX));
assert_eq!(r, None, "a structure constant past i128 must escalate");
}
#[test]
fn negating_the_width_minimum_is_reported_rather_than_wrapped() {
let _g = serial();
let reached = guarded(|| Guarded(i128::MIN / 2).mul(&Guarded(2)));
assert_eq!(
reached,
Some(Guarded(i128::MIN)),
"MIN is a legitimate product, not an overflow"
);
let r = guarded(|| Guarded(i128::MIN).neg());
assert_eq!(r, None, "negating MIN must escalate, not wrap to MIN");
}
#[test]
fn rational_width_minimum_is_reported_at_every_seam() {
let _g = serial();
assert_eq!(
guarded(|| <GuardedRat as Ring>::from_i128(i128::MIN)),
None,
"injecting MIN must escalate"
);
assert_eq!(
guarded(|| GuardedRat::new(i128::MIN, 3)),
None,
"a MIN numerator must escalate"
);
assert_eq!(
guarded(|| GuardedRat::new(3, i128::MIN)),
None,
"a MIN denominator must escalate"
);
assert_eq!(guarded(|| GuardedRat::new(i128::MIN, i128::MIN)), None);
}
#[test]
fn overflow_inside_a_nested_scope_still_reaches_the_outer_one() {
let _g = serial();
let outer = guarded(|| {
let inner = guarded(|| Guarded(i128::MAX).mul(&Guarded(2)));
assert_eq!(inner, None);
7
});
assert_eq!(outer, None, "outer scope must not report success");
}
#[test]
fn rationals_stay_exact_and_report_at_the_edge() {
let _g = serial();
let ok = guarded(|| {
let a = GuardedRat::new(1, 3);
let b = GuardedRat::new(1, 6);
let mut c = a;
c.add_assign(&b);
c
});
assert_eq!(ok, Some(GuardedRat::new(1, 2)));
let bad = guarded(|| GuardedRat::new(i128::MAX, 1).mul(&GuardedRat::new(3, 1)));
assert_eq!(bad, None);
}
#[test]
fn guarded_shortcut_arithmetic_matches_rational() {
let _g = serial();
let nums = [-7i128, -6, -1, 0, 1, 2, 3, 5, 6, 12, 35, 1 << 40];
let dens = [1i128, 2, 3, 4, 6, 7, 12, 30, 1 << 40, (1 << 40) + 1];
let got = guarded(|| {
for &a in &nums {
for &b in &dens {
for &c in &nums {
for &d in &dens {
let (x, y) = (GuardedRat::new(a, b), GuardedRat::new(c, d));
let (rx, ry) = (Rational::new(a, b), Rational::new(c, d));
let mut sum = x;
sum.add_assign(&y);
let mut rsum = rx;
rsum.add_assign(&ry);
assert_eq!(
(sum.num, sum.den),
(rsum.numer(), rsum.denom()),
"{a}/{b} + {c}/{d}"
);
let (prod, rprod) = (x.mul(&y), rx.mul(&ry));
assert_eq!(
(prod.num, prod.den),
(rprod.numer(), rprod.denom()),
"{a}/{b} * {c}/{d}"
);
for n in [1u128, 2, 6, 7, 1 << 40] {
let (q, rq) = (x.div_u128(n), rx.div_u128(n));
assert_eq!(
(q.num, q.den),
(rq.numer(), rq.denom()),
"{a}/{b} / {n}"
);
}
}
}
}
}
});
assert!(got.is_some(), "nothing on this grid leaves i128");
}
#[test]
fn shortcut_paths_refuse_what_normalization_refuses() {
let _g = serial();
let half_min = GuardedRat::new(i128::MIN / 2, 1);
assert_eq!(
guarded(|| half_min.mul(&GuardedRat::new(2, 1))),
None,
"an integer product landing on MIN is reported"
);
assert_eq!(
guarded(|| half_min.mul(&GuardedRat::new(2, 3))),
None,
"a cross-canceled numerator landing on MIN is reported"
);
assert_eq!(
guarded(|| {
let mut x = GuardedRat::new(1, i128::MAX / 2);
x.add_assign(&GuardedRat::new(1, i128::MAX / 2 - 1));
x
}),
None,
"coprime denominators whose product leaves i128 are reported"
);
}
#[test]
fn guarded_conversions_agree_with_the_plain_ring() {
let _g = serial();
for n in 0..=7u32 {
for lambda in crate::partitions_of(n) {
let g: Schur<GuardedRat> =
Schur::monomial(lambda.clone(), <GuardedRat as Ring>::one());
let pg: PowerSum<GuardedRat> =
guarded(|| PowerSum::from_schur(&g)).expect("degree 7 fits i128");
let r: Schur<crate::Rational> =
Schur::monomial(lambda.clone(), crate::Rational::from_int(1));
let pr: PowerSum<crate::Rational> = PowerSum::from_schur(&r);
assert_eq!(pg.terms().len(), pr.terms().len(), "support at {lambda}");
for (mu, c) in pg.terms() {
let want = pr.coeff(mu);
assert_eq!(
(c.numer(), c.denom()),
(want.numer(), want.denom()),
"s_{lambda} -> p at {mu}"
);
}
}
}
}
#[test]
fn a_character_past_i128_is_reported() {
let _g = serial();
let lam = Partition::new([18u32, 16, 14, 12, 10, 8]);
let n = lam.size();
let ones = Partition::new(std::iter::repeat_n(1, n as usize));
let got = guarded(|| crate::character::character_in::<Guarded>(&lam, &ones));
assert_eq!(got, None, "χ^λ(1^n) for |λ| = {n} exceeds i128");
}
}