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}