1use alloc::vec::Vec;
2
3use neco_algnum::RealAlgebraic;
4#[cfg(test)]
5use neco_bigint::BigintError;
6use neco_bigint::{ReducedRational, Sign};
7use neco_formsum::FormSum;
8#[cfg(test)]
9use neco_monomial::MonomialErrorKind;
10use neco_monomial::{Monomial, RawMonomial};
11
12use crate::{AtomId, EvalError, ExprId};
13
14#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
15pub enum ExactLayer {
16 Monomial,
17 FormSum,
18 Algebraic,
19}
20
21#[derive(Debug, Eq, PartialEq)]
22pub enum ExactValue {
23 Monomial(Monomial),
24 FormSum(FormSum),
25 Algebraic(RealAlgebraic),
26}
27
28impl ExactValue {
29 pub fn layer(&self) -> ExactLayer {
30 match self {
31 Self::Monomial(_) => ExactLayer::Monomial,
32 Self::FormSum(_) => ExactLayer::FormSum,
33 Self::Algebraic(_) => ExactLayer::Algebraic,
34 }
35 }
36
37 pub fn is_zero(&self) -> bool {
38 match self {
39 Self::Monomial(value) => value.is_zero(),
40 Self::FormSum(value) => value.is_zero(),
41 Self::Algebraic(value) => algebraic_is_zero(value),
42 }
43 }
44
45 pub fn try_clone(&self) -> Result<Self, EvalError> {
46 match self {
47 Self::Monomial(value) => Ok(Self::Monomial(clone_monomial(value)?)),
48 Self::FormSum(value) => Ok(Self::FormSum(value.try_clone()?)),
49 Self::Algebraic(value) => Ok(Self::Algebraic(value.try_clone()?)),
50 }
51 }
52}
53
54fn algebraic_is_zero(value: &RealAlgebraic) -> bool {
55 value.is_zero()
56}
57
58#[derive(Debug, Eq, PartialEq)]
59pub enum ExprNode {
60 Atom(AtomId),
61 Neg(ExprId),
62 Add(ExprId, ExprId),
63 Sub(ExprId, ExprId),
64 Mul(ExprId, ExprId),
65 Div(ExprId, ExprId),
66 Pow {
67 base: ExprId,
68 exponent: ReducedRational,
69 },
70}
71
72impl ExprNode {
73 pub fn try_clone(&self) -> Result<Self, EvalError> {
74 match self {
75 Self::Atom(atom) => Ok(Self::Atom(*atom)),
76 Self::Neg(child) => Ok(Self::Neg(*child)),
77 Self::Add(left, right) => Ok(Self::Add(*left, *right)),
78 Self::Sub(left, right) => Ok(Self::Sub(*left, *right)),
79 Self::Mul(left, right) => Ok(Self::Mul(*left, *right)),
80 Self::Div(left, right) => Ok(Self::Div(*left, *right)),
81 Self::Pow { base, exponent } => Ok(Self::Pow {
82 base: *base,
83 exponent: clone_exponent(exponent)?,
84 }),
85 }
86 }
87}
88
89fn clone_exponent(value: &ReducedRational) -> Result<ReducedRational, EvalError> {
90 #[cfg(test)]
91 if clone_failure_is(CloneContact::Exponent) {
92 return Err(EvalError::Bigint(BigintError::AllocationFailure {
93 requested_limbs: 17,
94 }));
95 }
96 value.try_clone().map_err(EvalError::Bigint)
97}
98
99fn clone_monomial(value: &Monomial) -> Result<Monomial, EvalError> {
100 #[cfg(test)]
101 if clone_failure_is(CloneContact::Monomial) {
102 return Err(EvalError::Monomial(MonomialErrorKind::AllocationFailure {
103 requested_elements: 19,
104 }));
105 }
106 value.try_clone().map_err(EvalError::Monomial)
107}
108
109#[cfg(test)]
110#[derive(Clone, Copy, Eq, PartialEq)]
111pub(crate) enum CloneContact {
112 Exponent,
113 Monomial,
114}
115
116#[cfg(test)]
117std::thread_local! {
118 static CLONE_FAILURE: core::cell::Cell<Option<CloneContact>> = const { core::cell::Cell::new(None) };
119}
120
121#[cfg(test)]
122fn clone_failure_is(contact: CloneContact) -> bool {
123 CLONE_FAILURE.with(|configured| configured.get() == Some(contact))
124}
125
126#[cfg(test)]
127pub(crate) fn with_clone_failure<R>(contact: CloneContact, operation: impl FnOnce() -> R) -> R {
128 CLONE_FAILURE.with(|configured| configured.set(Some(contact)));
129 let result = operation();
130 CLONE_FAILURE.with(|configured| configured.set(None));
131 result
132}
133
134pub(crate) fn neg_exact(value: &ExactValue) -> Result<ExactValue, EvalError> {
135 match value {
136 ExactValue::Monomial(value) => {
137 let negative_one = negative_one()?;
138 Ok(ExactValue::Monomial(value.mul(&negative_one)?))
139 }
140 ExactValue::FormSum(value) => Ok(ExactValue::FormSum(FormSum::zero().sub(value)?)),
141 ExactValue::Algebraic(value) => {
142 let zero = RealAlgebraic::from_form_sum(&FormSum::zero())?;
143 Ok(ExactValue::Algebraic(zero.sub(value)?))
144 }
145 }
146}
147
148pub(crate) fn add_exact(left: &ExactValue, right: &ExactValue) -> Result<ExactValue, EvalError> {
149 binary_exact(BinaryOperation::Add, left, right)
150}
151
152pub(crate) fn sub_exact(left: &ExactValue, right: &ExactValue) -> Result<ExactValue, EvalError> {
153 binary_exact(BinaryOperation::Sub, left, right)
154}
155
156pub(crate) fn mul_exact(left: &ExactValue, right: &ExactValue) -> Result<ExactValue, EvalError> {
157 binary_exact(BinaryOperation::Mul, left, right)
158}
159
160pub(crate) fn div_exact(left: &ExactValue, right: &ExactValue) -> Result<ExactValue, EvalError> {
161 if right.is_zero() {
162 return Err(EvalError::DivisionByZero);
163 }
164 binary_exact(BinaryOperation::Div, left, right)
165}
166
167pub(crate) fn pow_exact(
168 base: &ExactValue,
169 exponent: &ReducedRational,
170) -> Result<ExactValue, EvalError> {
171 if base.is_zero() {
172 if exponent.is_zero() {
173 return Err(EvalError::UndefinedZeroPower);
174 }
175 if exponent.numerator().sign() == Sign::Negative {
176 return Err(EvalError::ZeroToNegativePower);
177 }
178 }
179 if exponent.is_zero() {
180 return one_at_layer(base.layer());
181 }
182 let integer = exponent.denominator().to_u32() == Some(1);
183 if !integer && !exponent.denominator().bit(0) && sign_of(base)? == Sign::Negative {
184 return Err(EvalError::EvenRootOfNegative);
185 }
186
187 match base {
188 ExactValue::Monomial(value) => Ok(ExactValue::Monomial(value.pow(exponent)?)),
189 ExactValue::FormSum(value) if integer => Ok(ExactValue::FormSum(pow_form_sum_integer(
190 value,
191 exponent.numerator(),
192 )?)),
193 ExactValue::FormSum(value) => Ok(ExactValue::Algebraic(
194 RealAlgebraic::from_form_sum(value)?.pow_rational(exponent)?,
195 )),
196 ExactValue::Algebraic(value) if integer => Ok(ExactValue::Algebraic(
197 value.pow_integer(exponent.numerator())?,
198 )),
199 ExactValue::Algebraic(value) => Ok(ExactValue::Algebraic(value.pow_rational(exponent)?)),
200 }
201}
202
203fn to_algebraic(value: &ExactValue) -> Result<RealAlgebraic, EvalError> {
204 match value {
205 ExactValue::Monomial(value) => Ok(RealAlgebraic::from_form_sum(&FormSum::from_monomial(
206 value,
207 )?)?),
208 ExactValue::FormSum(value) => Ok(RealAlgebraic::from_form_sum(value)?),
209 ExactValue::Algebraic(value) => Ok(value.try_clone()?),
210 }
211}
212
213#[derive(Clone, Copy)]
214enum BinaryOperation {
215 Add,
216 Sub,
217 Mul,
218 Div,
219}
220
221enum FormOperand<'a> {
222 Monomial(&'a Monomial),
223 FormSum(&'a FormSum),
224}
225
226impl FormOperand<'_> {
227 fn into_value(self) -> Result<FormSum, EvalError> {
228 match self {
229 Self::Monomial(value) => Ok(FormSum::from_monomial(value)?),
230 Self::FormSum(value) => Ok(value.try_clone()?),
231 }
232 }
233}
234
235enum BinaryRoute<'a> {
236 Monomial(&'a Monomial, &'a Monomial),
237 FormSum(FormOperand<'a>, FormOperand<'a>),
238 Algebraic(&'a ExactValue, &'a ExactValue),
239}
240
241fn binary_route<'a>(
242 operation: BinaryOperation,
243 left: &'a ExactValue,
244 right: &'a ExactValue,
245) -> BinaryRoute<'a> {
246 match (operation, left, right) {
247 (_, ExactValue::Algebraic(_), _) | (_, _, ExactValue::Algebraic(_)) => {
248 BinaryRoute::Algebraic(left, right)
249 }
250 (
251 BinaryOperation::Mul | BinaryOperation::Div,
252 ExactValue::Monomial(left),
253 ExactValue::Monomial(right),
254 ) => BinaryRoute::Monomial(left, right),
255 (_, ExactValue::Monomial(left), ExactValue::Monomial(right)) => {
256 BinaryRoute::FormSum(FormOperand::Monomial(left), FormOperand::Monomial(right))
257 }
258 (_, ExactValue::Monomial(left), ExactValue::FormSum(right)) => {
259 BinaryRoute::FormSum(FormOperand::Monomial(left), FormOperand::FormSum(right))
260 }
261 (_, ExactValue::FormSum(left), ExactValue::Monomial(right)) => {
262 BinaryRoute::FormSum(FormOperand::FormSum(left), FormOperand::Monomial(right))
263 }
264 (_, ExactValue::FormSum(left), ExactValue::FormSum(right)) => {
265 BinaryRoute::FormSum(FormOperand::FormSum(left), FormOperand::FormSum(right))
266 }
267 }
268}
269
270fn binary_exact(
271 operation: BinaryOperation,
272 left: &ExactValue,
273 right: &ExactValue,
274) -> Result<ExactValue, EvalError> {
275 match binary_route(operation, left, right) {
276 BinaryRoute::Monomial(left, right) => match operation {
277 BinaryOperation::Add => Ok(ExactValue::FormSum(
278 FormSum::from_monomial(left)?.add(&FormSum::from_monomial(right)?)?,
279 )),
280 BinaryOperation::Sub => Ok(ExactValue::FormSum(
281 FormSum::from_monomial(left)?.sub(&FormSum::from_monomial(right)?)?,
282 )),
283 BinaryOperation::Mul => Ok(ExactValue::Monomial(left.mul(right)?)),
284 BinaryOperation::Div => Ok(ExactValue::Monomial(left.div(right)?)),
285 },
286 BinaryRoute::FormSum(left, right) => {
287 let left = left.into_value()?;
288 let right = right.into_value()?;
289 match operation {
290 BinaryOperation::Add => Ok(ExactValue::FormSum(left.add(&right)?)),
291 BinaryOperation::Sub => Ok(ExactValue::FormSum(left.sub(&right)?)),
292 BinaryOperation::Mul => Ok(ExactValue::FormSum(left.mul(&right)?)),
293 BinaryOperation::Div => Ok(ExactValue::FormSum(left.div(&right)?)),
294 }
295 }
296 BinaryRoute::Algebraic(left, right) => {
297 let left = to_algebraic(left)?;
298 let right = to_algebraic(right)?;
299 match operation {
300 BinaryOperation::Add => Ok(ExactValue::Algebraic(left.add(&right)?)),
301 BinaryOperation::Sub => Ok(ExactValue::Algebraic(left.sub(&right)?)),
302 BinaryOperation::Mul => Ok(ExactValue::Algebraic(left.mul(&right)?)),
303 BinaryOperation::Div => Ok(ExactValue::Algebraic(left.div(&right)?)),
304 }
305 }
306 }
307}
308
309fn sign_of(value: &ExactValue) -> Result<Sign, EvalError> {
310 match value {
311 ExactValue::Monomial(value) => Ok(value.sign()),
312 ExactValue::FormSum(value) => Ok(value.sign()?),
313 ExactValue::Algebraic(value) => Ok(value.sign()?),
314 }
315}
316
317pub(crate) fn decide_zero(value: &ExactValue) -> bool {
318 value.is_zero()
319}
320
321pub(crate) fn decide_equality(left: &ExactValue, right: &ExactValue) -> Result<bool, EvalError> {
322 Ok(sub_exact(left, right)?.is_zero())
323}
324
325pub(crate) fn decide_sign(value: &ExactValue) -> Result<Sign, EvalError> {
326 sign_of(value)
327}
328
329fn one_at_layer(layer: ExactLayer) -> Result<ExactValue, EvalError> {
330 match layer {
331 ExactLayer::Monomial => Ok(ExactValue::Monomial(Monomial::one())),
332 ExactLayer::FormSum => Ok(ExactValue::FormSum(FormSum::one()?)),
333 ExactLayer::Algebraic => Ok(ExactValue::Algebraic(RealAlgebraic::from_form_sum(
334 &FormSum::one()?,
335 )?)),
336 }
337}
338
339fn negative_one() -> Result<Monomial, EvalError> {
340 RawMonomial::negative(Vec::new())
341 .normalize()
342 .map_err(|errors| EvalError::Monomial(errors.into_parts().0))
343}
344
345fn pow_form_sum_integer(
346 value: &FormSum,
347 exponent: &neco_bigint::BigInt,
348) -> Result<FormSum, EvalError> {
349 let mut result = FormSum::one()?;
350 let mut power = if exponent.sign() == Sign::Negative {
351 FormSum::one()?.div(value)?
352 } else {
353 value.try_clone()?
354 };
355 let bit_len = exponent.magnitude().bit_len();
356 for bit in 0..bit_len {
357 if exponent.magnitude().bit(bit) {
358 result = result.mul(&power)?;
359 }
360 if bit + 1 < bit_len {
361 power = power.mul(&power)?;
362 }
363 }
364 Ok(result)
365}
366
367#[cfg(test)]
368mod tests {
369 use neco_algnum::RealAlgebraic;
370 use neco_bigint::{BigInt, BigUint, RawRational, ReducedRational};
371 use neco_formsum::FormSum;
372 use neco_monomial::{Monomial, RawMonomial, RawPower};
373
374 use super::{add_exact, div_exact, mul_exact, neg_exact, pow_exact, sub_exact};
375 use crate::{ExactLayer, ExactValue};
376
377 fn layer_values(one: bool) -> [ExactValue; 3] {
378 let monomial = if one {
379 Monomial::one()
380 } else {
381 Monomial::zero()
382 };
383 let form = FormSum::from_monomial(&monomial).unwrap();
384 let algebraic = RealAlgebraic::from_form_sum(&form).unwrap();
385 [
386 ExactValue::Monomial(monomial),
387 ExactValue::FormSum(form),
388 ExactValue::Algebraic(algebraic),
389 ]
390 }
391
392 fn monomial(sign: bool, powers: &[(u32, i32)]) -> Monomial {
393 let powers = powers
394 .iter()
395 .map(|&(base, power)| {
396 RawPower::new(
397 BigUint::try_from(base).unwrap(),
398 RawRational::new(BigInt::try_from(power).unwrap(), BigUint::one().unwrap()),
399 )
400 })
401 .collect();
402 if sign {
403 RawMonomial::positive(powers)
404 } else {
405 RawMonomial::negative(powers)
406 }
407 .normalize()
408 .unwrap()
409 }
410
411 fn at_layer(value: Monomial, layer: ExactLayer) -> ExactValue {
412 match layer {
413 ExactLayer::Monomial => ExactValue::Monomial(value),
414 ExactLayer::FormSum => ExactValue::FormSum(FormSum::from_monomial(&value).unwrap()),
415 ExactLayer::Algebraic => {
416 let form = FormSum::from_monomial(&value).unwrap();
417 ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap())
418 }
419 }
420 }
421
422 fn integer_at_layer(value: u32, layer: ExactLayer) -> ExactValue {
423 at_layer(monomial(true, &[(value, 1)]), layer)
424 }
425
426 fn exponent(numerator: i32, denominator: u32) -> ReducedRational {
427 RawRational::new(
428 BigInt::try_from(numerator).unwrap(),
429 BigUint::try_from(denominator).unwrap(),
430 )
431 .reduce()
432 .unwrap()
433 .into_reduced()
434 }
435
436 #[test]
437 fn production_binary_results_cover_every_operation_table_cell() {
438 let layers = [
439 ExactLayer::Monomial,
440 ExactLayer::FormSum,
441 ExactLayer::Algebraic,
442 ];
443 let operations = [
444 (
445 add_exact as fn(&ExactValue, &ExactValue) -> Result<ExactValue, crate::EvalError>,
446 0_u8,
447 ),
448 (sub_exact, 1),
449 (mul_exact, 2),
450 (div_exact, 3),
451 ];
452 for left_layer in layers {
453 for right_layer in layers {
454 let add_sub = if left_layer == ExactLayer::Algebraic
455 || right_layer == ExactLayer::Algebraic
456 {
457 ExactLayer::Algebraic
458 } else {
459 ExactLayer::FormSum
460 };
461 let mul_div = if left_layer == ExactLayer::Algebraic
462 || right_layer == ExactLayer::Algebraic
463 {
464 ExactLayer::Algebraic
465 } else if left_layer == ExactLayer::Monomial && right_layer == ExactLayer::Monomial
466 {
467 ExactLayer::Monomial
468 } else {
469 ExactLayer::FormSum
470 };
471 for (operation, operation_id) in operations {
472 let left = integer_at_layer(2, left_layer);
473 let right = integer_at_layer(3, right_layer);
474 let result_layer = if operation_id >= 2 { mul_div } else { add_sub };
475 let expected_monomial = match operation_id {
476 0 => monomial(true, &[(5, 1)]),
477 1 => monomial(false, &[]),
478 2 => monomial(true, &[(2, 1), (3, 1)]),
479 3 => monomial(true, &[(2, 1), (3, -1)]),
480 _ => unreachable!(),
481 };
482 assert_eq!(
483 operation(&left, &right).unwrap(),
484 at_layer(expected_monomial, result_layer)
485 );
486 }
487 }
488 }
489 }
490
491 #[test]
492 fn production_unary_and_power_results_cover_every_layer() {
493 let layers = [
494 ExactLayer::Monomial,
495 ExactLayer::FormSum,
496 ExactLayer::Algebraic,
497 ];
498 let integer = exponent(2, 1);
499 let rational = exponent(1, 2);
500 for layer in layers {
501 let value = integer_at_layer(2, layer);
502 assert_eq!(
503 neg_exact(&value).unwrap(),
504 at_layer(monomial(false, &[(2, 1)]), layer)
505 );
506 assert_eq!(
507 pow_exact(&value, &integer).unwrap(),
508 integer_at_layer(4, layer)
509 );
510 let rational_layer = if layer == ExactLayer::Monomial {
511 ExactLayer::Monomial
512 } else {
513 ExactLayer::Algebraic
514 };
515 assert_eq!(
516 pow_exact(&value, &rational).unwrap(),
517 at_layer(
518 monomial(true, &[(2, 1)]).pow(&rational).unwrap(),
519 rational_layer,
520 )
521 );
522 }
523 }
524
525 #[test]
526 fn structural_zero_is_decided_in_every_exact_layer() {
527 for value in layer_values(false) {
528 assert!(value.is_zero());
529 }
530 for value in layer_values(true) {
531 assert!(!value.is_zero());
532 }
533 }
534}