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
317fn one_at_layer(layer: ExactLayer) -> Result<ExactValue, EvalError> {
318 match layer {
319 ExactLayer::Monomial => Ok(ExactValue::Monomial(Monomial::one())),
320 ExactLayer::FormSum => Ok(ExactValue::FormSum(FormSum::one()?)),
321 ExactLayer::Algebraic => Ok(ExactValue::Algebraic(RealAlgebraic::from_form_sum(
322 &FormSum::one()?,
323 )?)),
324 }
325}
326
327fn negative_one() -> Result<Monomial, EvalError> {
328 RawMonomial::negative(Vec::new())
329 .normalize()
330 .map_err(|errors| EvalError::Monomial(errors.into_parts().0))
331}
332
333fn pow_form_sum_integer(
334 value: &FormSum,
335 exponent: &neco_bigint::BigInt,
336) -> Result<FormSum, EvalError> {
337 let mut result = FormSum::one()?;
338 let mut power = if exponent.sign() == Sign::Negative {
339 FormSum::one()?.div(value)?
340 } else {
341 value.try_clone()?
342 };
343 let bit_len = exponent.magnitude().bit_len();
344 for bit in 0..bit_len {
345 if exponent.magnitude().bit(bit) {
346 result = result.mul(&power)?;
347 }
348 if bit + 1 < bit_len {
349 power = power.mul(&power)?;
350 }
351 }
352 Ok(result)
353}
354
355#[cfg(test)]
356mod tests {
357 use neco_algnum::RealAlgebraic;
358 use neco_bigint::{BigInt, BigUint, RawRational, ReducedRational};
359 use neco_formsum::FormSum;
360 use neco_monomial::{Monomial, RawMonomial, RawPower};
361
362 use super::{add_exact, div_exact, mul_exact, neg_exact, pow_exact, sub_exact};
363 use crate::{ExactLayer, ExactValue};
364
365 fn layer_values(one: bool) -> [ExactValue; 3] {
366 let monomial = if one {
367 Monomial::one()
368 } else {
369 Monomial::zero()
370 };
371 let form = FormSum::from_monomial(&monomial).unwrap();
372 let algebraic = RealAlgebraic::from_form_sum(&form).unwrap();
373 [
374 ExactValue::Monomial(monomial),
375 ExactValue::FormSum(form),
376 ExactValue::Algebraic(algebraic),
377 ]
378 }
379
380 fn monomial(sign: bool, powers: &[(u32, i32)]) -> Monomial {
381 let powers = powers
382 .iter()
383 .map(|&(base, power)| {
384 RawPower::new(
385 BigUint::try_from(base).unwrap(),
386 RawRational::new(BigInt::try_from(power).unwrap(), BigUint::one().unwrap()),
387 )
388 })
389 .collect();
390 if sign {
391 RawMonomial::positive(powers)
392 } else {
393 RawMonomial::negative(powers)
394 }
395 .normalize()
396 .unwrap()
397 }
398
399 fn at_layer(value: Monomial, layer: ExactLayer) -> ExactValue {
400 match layer {
401 ExactLayer::Monomial => ExactValue::Monomial(value),
402 ExactLayer::FormSum => ExactValue::FormSum(FormSum::from_monomial(&value).unwrap()),
403 ExactLayer::Algebraic => {
404 let form = FormSum::from_monomial(&value).unwrap();
405 ExactValue::Algebraic(RealAlgebraic::from_form_sum(&form).unwrap())
406 }
407 }
408 }
409
410 fn integer_at_layer(value: u32, layer: ExactLayer) -> ExactValue {
411 at_layer(monomial(true, &[(value, 1)]), layer)
412 }
413
414 fn exponent(numerator: i32, denominator: u32) -> ReducedRational {
415 RawRational::new(
416 BigInt::try_from(numerator).unwrap(),
417 BigUint::try_from(denominator).unwrap(),
418 )
419 .reduce()
420 .unwrap()
421 .into_reduced()
422 }
423
424 #[test]
425 fn production_binary_results_cover_every_operation_table_cell() {
426 let layers = [
427 ExactLayer::Monomial,
428 ExactLayer::FormSum,
429 ExactLayer::Algebraic,
430 ];
431 let operations = [
432 (
433 add_exact as fn(&ExactValue, &ExactValue) -> Result<ExactValue, crate::EvalError>,
434 0_u8,
435 ),
436 (sub_exact, 1),
437 (mul_exact, 2),
438 (div_exact, 3),
439 ];
440 for left_layer in layers {
441 for right_layer in layers {
442 let add_sub = if left_layer == ExactLayer::Algebraic
443 || right_layer == ExactLayer::Algebraic
444 {
445 ExactLayer::Algebraic
446 } else {
447 ExactLayer::FormSum
448 };
449 let mul_div = if left_layer == ExactLayer::Algebraic
450 || right_layer == ExactLayer::Algebraic
451 {
452 ExactLayer::Algebraic
453 } else if left_layer == ExactLayer::Monomial && right_layer == ExactLayer::Monomial
454 {
455 ExactLayer::Monomial
456 } else {
457 ExactLayer::FormSum
458 };
459 for (operation, operation_id) in operations {
460 let left = integer_at_layer(2, left_layer);
461 let right = integer_at_layer(3, right_layer);
462 let result_layer = if operation_id >= 2 { mul_div } else { add_sub };
463 let expected_monomial = match operation_id {
464 0 => monomial(true, &[(5, 1)]),
465 1 => monomial(false, &[]),
466 2 => monomial(true, &[(2, 1), (3, 1)]),
467 3 => monomial(true, &[(2, 1), (3, -1)]),
468 _ => unreachable!(),
469 };
470 assert_eq!(
471 operation(&left, &right).unwrap(),
472 at_layer(expected_monomial, result_layer)
473 );
474 }
475 }
476 }
477 }
478
479 #[test]
480 fn production_unary_and_power_results_cover_every_layer() {
481 let layers = [
482 ExactLayer::Monomial,
483 ExactLayer::FormSum,
484 ExactLayer::Algebraic,
485 ];
486 let integer = exponent(2, 1);
487 let rational = exponent(1, 2);
488 for layer in layers {
489 let value = integer_at_layer(2, layer);
490 assert_eq!(
491 neg_exact(&value).unwrap(),
492 at_layer(monomial(false, &[(2, 1)]), layer)
493 );
494 assert_eq!(
495 pow_exact(&value, &integer).unwrap(),
496 integer_at_layer(4, layer)
497 );
498 let rational_layer = if layer == ExactLayer::Monomial {
499 ExactLayer::Monomial
500 } else {
501 ExactLayer::Algebraic
502 };
503 assert_eq!(
504 pow_exact(&value, &rational).unwrap(),
505 at_layer(
506 monomial(true, &[(2, 1)]).pow(&rational).unwrap(),
507 rational_layer,
508 )
509 );
510 }
511 }
512
513 #[test]
514 fn structural_zero_is_decided_in_every_exact_layer() {
515 for value in layer_values(false) {
516 assert!(value.is_zero());
517 }
518 for value in layer_values(true) {
519 assert!(!value.is_zero());
520 }
521 }
522}