Skip to main content

neco_expr/
value.rs

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}