Skip to main content

neco_monomial/
error.rs

1use alloc::vec::Vec;
2use core::cmp::Ordering;
3use core::fmt;
4use core::mem::size_of;
5
6use neco_bigint::BigintError;
7
8#[derive(Debug, Eq, PartialEq)]
9pub enum MonomialErrorKind {
10    DivisionByZero,
11    ZeroToNegativePower,
12    UndefinedZeroPower,
13    EvenRootOfNegative,
14    InvalidRadicalBasis,
15    CapacityOverflow,
16    AllocationFailure { requested_elements: usize },
17    Bigint(BigintError),
18}
19
20impl MonomialErrorKind {
21    pub fn try_clone(&self) -> Result<Self, MonomialErrorKind> {
22        self.try_clone_internal()
23    }
24
25    pub(crate) fn try_clone_internal(&self) -> Result<Self, MonomialErrorKind> {
26        match self {
27            Self::DivisionByZero => Ok(Self::DivisionByZero),
28            Self::ZeroToNegativePower => Ok(Self::ZeroToNegativePower),
29            Self::UndefinedZeroPower => Ok(Self::UndefinedZeroPower),
30            Self::EvenRootOfNegative => Ok(Self::EvenRootOfNegative),
31            Self::InvalidRadicalBasis => Ok(Self::InvalidRadicalBasis),
32            Self::CapacityOverflow => Ok(Self::CapacityOverflow),
33            Self::AllocationFailure { requested_elements } => Ok(Self::AllocationFailure {
34                requested_elements: *requested_elements,
35            }),
36            Self::Bigint(error) => Ok(Self::Bigint(try_clone_bigint_error(error)?)),
37        }
38    }
39}
40
41impl Ord for MonomialErrorKind {
42    fn cmp(&self, other: &Self) -> Ordering {
43        compare_monomial_errors(self, other)
44    }
45}
46
47pub(crate) fn compare_monomial_errors(
48    left: &MonomialErrorKind,
49    right: &MonomialErrorKind,
50) -> Ordering {
51    error_discriminant(left)
52        .cmp(&error_discriminant(right))
53        .then_with(|| match (left, right) {
54            (
55                MonomialErrorKind::AllocationFailure {
56                    requested_elements: left,
57                },
58                MonomialErrorKind::AllocationFailure {
59                    requested_elements: right,
60                },
61            ) => left.cmp(right),
62            (MonomialErrorKind::Bigint(left), MonomialErrorKind::Bigint(right)) => {
63                compare_bigint_error(left, right)
64            }
65            _ => Ordering::Equal,
66        })
67}
68
69impl PartialOrd for MonomialErrorKind {
70    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
71        Some(self.cmp(other))
72    }
73}
74
75impl fmt::Display for MonomialErrorKind {
76    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
77        formatter.write_str(match self {
78            Self::DivisionByZero => "division by zero",
79            Self::ZeroToNegativePower => "zero raised to a negative power",
80            Self::UndefinedZeroPower => "zero raised to the zero power",
81            Self::EvenRootOfNegative => "even root of a negative value",
82            Self::InvalidRadicalBasis => "invalid radical basis",
83            Self::CapacityOverflow => "monomial element capacity exceeds isize",
84            Self::AllocationFailure { .. } => "monomial element allocation failed",
85            Self::Bigint(error) => return error.fmt(formatter),
86        })
87    }
88}
89
90#[cfg(feature = "std")]
91impl std::error::Error for MonomialErrorKind {}
92
93#[derive(Debug, Eq, PartialEq)]
94pub struct NormalizationErrors<E> {
95    first: E,
96    additional: Vec<E>,
97}
98
99impl<E> NormalizationErrors<E> {
100    pub fn from_one(error: E) -> Self {
101        Self {
102            first: error,
103            additional: Vec::new(),
104        }
105    }
106
107    pub fn len(&self) -> usize {
108        1 + self.additional.len()
109    }
110
111    pub fn is_empty(&self) -> bool {
112        false
113    }
114
115    pub fn errors(&self) -> impl Iterator<Item = &E> {
116        core::iter::once(&self.first).chain(self.additional.iter())
117    }
118
119    pub fn into_parts(self) -> (E, Vec<E>) {
120        (self.first, self.additional)
121    }
122}
123
124impl<E: Ord> NormalizationErrors<E> {
125    pub fn from_errors(mut errors: Vec<E>) -> Option<Self> {
126        errors.sort_unstable();
127        errors.dedup();
128        if errors.is_empty() {
129            return None;
130        }
131        let first = errors.remove(0);
132        Some(Self {
133            first,
134            additional: errors,
135        })
136    }
137}
138
139impl NormalizationErrors<MonomialErrorKind> {
140    pub fn try_clone(&self) -> Result<Self, MonomialErrorKind> {
141        let total = self.additional.len();
142        let mut additional = Vec::new();
143        if total != 0 {
144            reserve_elements_for(&mut additional, total, AllocationTarget::ErrorSet)?;
145        }
146        for error in &self.additional {
147            additional.push(error.try_clone_internal()?);
148        }
149        Ok(Self {
150            first: self.first.try_clone_internal()?,
151            additional,
152        })
153    }
154}
155
156#[derive(Clone, Copy, Debug, Eq, PartialEq)]
157pub(crate) enum AllocationTarget {
158    RawPowerClone,
159    NormalizationIndex,
160    NormalFactor,
161    MergeResult,
162    ErrorSet,
163    RadicalBasis,
164}
165
166pub(crate) fn reserve_elements_for<T>(
167    values: &mut Vec<T>,
168    total_required: usize,
169    target: AllocationTarget,
170) -> Result<(), MonomialErrorKind> {
171    #[cfg(test)]
172    if let Some(failure) = injected_failure(target, total_required) {
173        return Err(failure);
174    }
175    total_required
176        .checked_mul(size_of::<T>())
177        .ok_or(MonomialErrorKind::CapacityOverflow)?;
178    let maximum = if size_of::<T>() == 0 {
179        usize::MAX
180    } else {
181        (isize::MAX as usize) / size_of::<T>()
182    };
183
184    let additional = total_required
185        .checked_sub(values.len())
186        .ok_or(MonomialErrorKind::CapacityOverflow)?;
187    reserve_elements_for_with(target, total_required, maximum, |_, _| {
188        values.try_reserve(additional).map_err(|_| ())
189    })
190}
191
192#[cfg(test)]
193#[derive(Clone, Copy, Debug, Eq, PartialEq)]
194enum InjectedFailure {
195    Capacity,
196    Allocation,
197}
198
199#[cfg(test)]
200std::thread_local! {
201    static INJECTED_TARGET: core::cell::Cell<Option<(AllocationTarget, InjectedFailure)>> = const { core::cell::Cell::new(None) };
202    static OBSERVED_TOTAL: core::cell::Cell<Option<usize>> = const { core::cell::Cell::new(None) };
203}
204
205#[cfg(test)]
206fn injected_failure(target: AllocationTarget, total_required: usize) -> Option<MonomialErrorKind> {
207    INJECTED_TARGET.with(|configured| match configured.get() {
208        Some((expected, failure)) if expected == target => {
209            OBSERVED_TOTAL.with(|observed| observed.set(Some(total_required)));
210            Some(match failure {
211                InjectedFailure::Capacity => MonomialErrorKind::CapacityOverflow,
212                InjectedFailure::Allocation => MonomialErrorKind::AllocationFailure {
213                    requested_elements: total_required,
214                },
215            })
216        }
217        _ => None,
218    })
219}
220
221#[cfg(test)]
222fn with_injected_failure<R>(
223    target: AllocationTarget,
224    failure: InjectedFailure,
225    operation: impl FnOnce() -> R,
226) -> (R, Option<usize>) {
227    INJECTED_TARGET.with(|configured| configured.set(Some((target, failure))));
228    OBSERVED_TOTAL.with(|observed| observed.set(None));
229    let result = operation();
230    let total = OBSERVED_TOTAL.with(core::cell::Cell::get);
231    INJECTED_TARGET.with(|configured| configured.set(None));
232    (result, total)
233}
234
235pub(crate) fn reserve_elements_for_with<F>(
236    target: AllocationTarget,
237    total_required: usize,
238    maximum: usize,
239    reserve_fn: F,
240) -> Result<(), MonomialErrorKind>
241where
242    F: FnOnce(AllocationTarget, usize) -> Result<(), ()>,
243{
244    if total_required > maximum {
245        return Err(MonomialErrorKind::CapacityOverflow);
246    }
247    reserve_fn(target, total_required).map_err(|()| MonomialErrorKind::AllocationFailure {
248        requested_elements: total_required,
249    })
250}
251
252fn error_discriminant(error: &MonomialErrorKind) -> u8 {
253    match error {
254        MonomialErrorKind::DivisionByZero => 0,
255        MonomialErrorKind::ZeroToNegativePower => 1,
256        MonomialErrorKind::UndefinedZeroPower => 2,
257        MonomialErrorKind::EvenRootOfNegative => 3,
258        MonomialErrorKind::InvalidRadicalBasis => 4,
259        MonomialErrorKind::CapacityOverflow => 5,
260        MonomialErrorKind::AllocationFailure { .. } => 6,
261        MonomialErrorKind::Bigint(_) => 7,
262    }
263}
264
265fn bigint_discriminant(error: &BigintError) -> u8 {
266    match error {
267        BigintError::CapacityOverflow => 0,
268        BigintError::AllocationFailure { .. } => 1,
269        BigintError::UnsignedUnderflow => 2,
270        BigintError::DivisionByZero => 3,
271        BigintError::NonExactDivision => 4,
272        BigintError::ZeroDenominator => 5,
273        BigintError::NonFiniteFloat => 6,
274        BigintError::FloatOutOfRange => 7,
275        BigintError::InvalidInterval => 8,
276        BigintError::ExponentOverflow { .. } => 9,
277    }
278}
279
280fn compare_bigint_error(left: &BigintError, right: &BigintError) -> Ordering {
281    bigint_discriminant(left)
282        .cmp(&bigint_discriminant(right))
283        .then_with(|| match (left, right) {
284            (
285                BigintError::AllocationFailure {
286                    requested_limbs: left,
287                },
288                BigintError::AllocationFailure {
289                    requested_limbs: right,
290                },
291            ) => left.cmp(right),
292            (
293                BigintError::ExponentOverflow {
294                    required: left_required,
295                    maximum: left_maximum,
296                },
297                BigintError::ExponentOverflow {
298                    required: right_required,
299                    maximum: right_maximum,
300                },
301            ) => left_required
302                .cmp(right_required)
303                .then_with(|| left_maximum.cmp(right_maximum)),
304            _ => Ordering::Equal,
305        })
306}
307
308fn try_clone_bigint_error(error: &BigintError) -> Result<BigintError, MonomialErrorKind> {
309    Ok(match error {
310        BigintError::CapacityOverflow => BigintError::CapacityOverflow,
311        BigintError::AllocationFailure { requested_limbs } => BigintError::AllocationFailure {
312            requested_limbs: *requested_limbs,
313        },
314        BigintError::UnsignedUnderflow => BigintError::UnsignedUnderflow,
315        BigintError::DivisionByZero => BigintError::DivisionByZero,
316        BigintError::NonExactDivision => BigintError::NonExactDivision,
317        BigintError::ZeroDenominator => BigintError::ZeroDenominator,
318        BigintError::NonFiniteFloat => BigintError::NonFiniteFloat,
319        BigintError::FloatOutOfRange => BigintError::FloatOutOfRange,
320        BigintError::InvalidInterval => BigintError::InvalidInterval,
321        BigintError::ExponentOverflow { required, maximum } => BigintError::ExponentOverflow {
322            required: required.try_clone().map_err(MonomialErrorKind::Bigint)?,
323            maximum: *maximum,
324        },
325    })
326}
327
328impl From<BigintError> for MonomialErrorKind {
329    fn from(error: BigintError) -> Self {
330        Self::Bigint(error)
331    }
332}
333
334#[cfg(test)]
335mod tests {
336    use super::{
337        reserve_elements_for_with, with_injected_failure, AllocationTarget, InjectedFailure,
338        MonomialErrorKind,
339    };
340    use alloc::vec;
341    use neco_bigint::{BigInt, BigUint, BigintError, RawRational};
342
343    use crate::{Monomial, RawMonomial, RawPower};
344
345    fn power(base: u8, numerator: i8, denominator: u8) -> RawPower {
346        RawPower::new(
347            BigUint::try_from(base).unwrap(),
348            RawRational::new(
349                BigInt::try_from(numerator).unwrap(),
350                BigUint::try_from(denominator).unwrap(),
351            ),
352        )
353    }
354
355    fn positive(powers: alloc::vec::Vec<RawPower>) -> Monomial {
356        RawMonomial::positive(powers).normalize().unwrap()
357    }
358
359    #[test]
360    fn reserve_reports_capacity_before_calling_allocator() {
361        let mut called = false;
362        let result = reserve_elements_for_with(AllocationTarget::RawPowerClone, 5, 4, |_, _| {
363            called = true;
364            Ok(())
365        });
366        assert_eq!(result, Err(MonomialErrorKind::CapacityOverflow));
367        assert!(!called);
368    }
369
370    #[test]
371    fn every_storage_target_reports_total_required_on_selective_failure() {
372        let targets = [
373            AllocationTarget::RawPowerClone,
374            AllocationTarget::NormalizationIndex,
375            AllocationTarget::NormalFactor,
376            AllocationTarget::MergeResult,
377            AllocationTarget::ErrorSet,
378            AllocationTarget::RadicalBasis,
379        ];
380        for failed in targets {
381            for current in targets {
382                let result = reserve_elements_for_with(current, 7, 7, |target, total| {
383                    assert_eq!(total, 7);
384                    if target == failed {
385                        Err(())
386                    } else {
387                        Ok(())
388                    }
389                });
390                if current == failed {
391                    assert_eq!(
392                        result,
393                        Err(MonomialErrorKind::AllocationFailure {
394                            requested_elements: 7
395                        })
396                    );
397                } else {
398                    assert_eq!(result, Ok(()));
399                }
400            }
401        }
402    }
403
404    #[test]
405    fn every_storage_target_is_reached_from_its_operation() {
406        for failure in [InjectedFailure::Capacity, InjectedFailure::Allocation] {
407            let expected = |total| match failure {
408                InjectedFailure::Capacity => MonomialErrorKind::CapacityOverflow,
409                InjectedFailure::Allocation => MonomialErrorKind::AllocationFailure {
410                    requested_elements: total,
411                },
412            };
413
414            let raw = RawMonomial::positive(vec![power(2, 1, 1), power(3, 1, 1)]);
415            let (result, observed) =
416                with_injected_failure(AllocationTarget::RawPowerClone, failure, || raw.try_clone());
417            assert_eq!(result, Err(expected(2)));
418            assert_eq!(observed, Some(2));
419
420            let raw = RawMonomial::positive(vec![power(2, 1, 1), power(3, 1, 1)]);
421            let (result, observed) =
422                with_injected_failure(AllocationTarget::NormalizationIndex, failure, || {
423                    raw.normalize()
424                });
425            assert!(result.unwrap_err().errors().eq([&expected(2)]));
426            assert_eq!(observed, Some(2));
427
428            let raw = RawMonomial::positive(vec![power(6, 1, 1)]);
429            let (result, observed) =
430                with_injected_failure(AllocationTarget::NormalFactor, failure, || raw.normalize());
431            assert!(result.unwrap_err().errors().eq([&expected(2)]));
432            assert_eq!(observed, Some(2));
433
434            let left = positive(vec![power(2, 1, 1)]);
435            let right = positive(vec![power(3, 1, 1)]);
436            let (result, observed) =
437                with_injected_failure(AllocationTarget::MergeResult, failure, || left.mul(&right));
438            assert_eq!(result, Err(expected(2)));
439            assert_eq!(observed, Some(2));
440
441            let raw = RawMonomial::positive(vec![power(0, -1, 1), power(0, 0, 1)]);
442            let (result, observed) =
443                with_injected_failure(AllocationTarget::ErrorSet, failure, || raw.normalize());
444            assert!(result.unwrap_err().errors().eq([&expected(2)]));
445            assert_eq!(observed, Some(2));
446
447            let radical = positive(vec![power(6, 1, 2)]);
448            let (result, observed) =
449                with_injected_failure(AllocationTarget::RadicalBasis, failure, || {
450                    radical.split_radical()
451                });
452            assert_eq!(result, Err(expected(2)));
453            assert_eq!(observed, Some(2));
454        }
455    }
456
457    #[test]
458    fn singleton_invalid_does_not_request_error_storage() {
459        let raw = RawMonomial::positive(vec![power(0, -1, 1)]);
460        let (result, observed) = with_injected_failure(
461            AllocationTarget::ErrorSet,
462            InjectedFailure::Allocation,
463            || raw.normalize(),
464        );
465        assert!(result
466            .unwrap_err()
467            .errors()
468            .eq([&MonomialErrorKind::ZeroToNegativePower]));
469        assert_eq!(observed, None);
470    }
471
472    #[test]
473    fn payload_comparison_uses_numeric_order() {
474        let mut errors = vec![
475            MonomialErrorKind::Bigint(BigintError::ExponentOverflow {
476                required: BigUint::try_from(11_u8).unwrap(),
477                maximum: 9,
478            }),
479            MonomialErrorKind::AllocationFailure {
480                requested_elements: 8,
481            },
482            MonomialErrorKind::Bigint(BigintError::AllocationFailure { requested_limbs: 5 }),
483            MonomialErrorKind::AllocationFailure {
484                requested_elements: 3,
485            },
486            MonomialErrorKind::Bigint(BigintError::ExponentOverflow {
487                required: BigUint::try_from(7_u8).unwrap(),
488                maximum: 12,
489            }),
490        ];
491        errors.sort();
492
493        assert_eq!(
494            errors,
495            vec![
496                MonomialErrorKind::AllocationFailure {
497                    requested_elements: 3
498                },
499                MonomialErrorKind::AllocationFailure {
500                    requested_elements: 8
501                },
502                MonomialErrorKind::Bigint(BigintError::AllocationFailure { requested_limbs: 5 }),
503                MonomialErrorKind::Bigint(BigintError::ExponentOverflow {
504                    required: BigUint::try_from(7_u8).unwrap(),
505                    maximum: 12
506                }),
507                MonomialErrorKind::Bigint(BigintError::ExponentOverflow {
508                    required: BigUint::try_from(11_u8).unwrap(),
509                    maximum: 9
510                }),
511            ]
512        );
513    }
514}