Skip to main content

cauchy_ode/
math_expr.rs

1// SPDX-License-Identifier: BSL-1.0
2// Distributed under the Boost Software License, Version 1.0.
3// See LICENSE or https://www.boost.org/LICENSE_1_0.txt.
4
5#![doc = include_str!("../MATH_EXPR.md")]
6
7use num_traits::Float;
8use std::collections::HashMap;
9use std::fmt::{Display, Formatter};
10
11mod parser;
12pub use parser::ParseError;
13
14#[derive(Clone, Debug, PartialEq)]
15pub enum Operation<'a, T> {
16    Variable(&'a str),
17    Constant(T),
18    Add,
19    Subtract,
20    Multiply,
21    Divide,
22    Power,
23    Negate,
24    Sine,
25    Cosine,
26    Tangent,
27    ArcSine,
28    ArcCosine,
29    ArcTangent,
30    HyperbolicSine,
31    HyperbolicCosine,
32    HyperbolicTangent,
33    Sign,
34    AbsoluteValue,
35    Exponent,
36    SquareRoot,
37    NaturalLogarithm,
38    CommonLogarithm,
39    ImmediateIf,
40}
41
42#[derive(Debug, PartialEq)]
43pub enum EvaluationError<'a, T> {
44    InvalidOperandCount {
45        operation: Operation<'a, T>,
46        expected: usize,
47        actual: usize,
48    },
49    VariableNotDefined(&'a str),
50}
51
52#[derive(Clone, Debug, PartialEq)]
53pub struct MathExpr<'a, T: Float> {
54    operation: Operation<'a, T>,
55    operands: Vec<MathExpr<'a, T>>,
56}
57
58impl<'a, T: Float + std::fmt::Debug> MathExpr<'a, T> {
59    /// Returns all variable names, including those in conditional branches.
60    pub fn variables(&self) -> std::collections::HashSet<&'a str> {
61        let mut variables = std::collections::HashSet::new();
62        self.collect_variables(&mut variables);
63        variables
64    }
65
66    fn collect_variables(&self, variables: &mut std::collections::HashSet<&'a str>) {
67        if let Operation::Variable(name) = self.operation {
68            variables.insert(name);
69        }
70        for operand in &self.operands {
71            operand.collect_variables(variables);
72        }
73    }
74
75    /// Substitutes a variable structurally, without rewriting expression text.
76    pub fn substitute(&self, name: &str, replacement: &Self) -> Self {
77        if matches!(self.operation, Operation::Variable(variable) if variable == name) {
78            return replacement.clone();
79        }
80        Self::new(
81            self.operation.clone(),
82            self.operands
83                .iter()
84                .map(|operand| operand.substitute(name, replacement))
85                .collect(),
86        )
87    }
88
89    fn new(operation: Operation<'a, T>, operands: Vec<MathExpr<'a, T>>) -> Self {
90        Self {
91            operation,
92            operands,
93        }
94    }
95
96    pub fn new_var(name: &'a str) -> Self {
97        Self {
98            operation: Operation::Variable(name),
99            operands: vec![],
100        }
101    }
102    pub fn new_const(value: T) -> Self {
103        Self {
104            operation: Operation::Constant(value),
105            operands: vec![],
106        }
107    }
108
109    pub fn new_add(left: Self, right: Self) -> Self {
110        Self::new(Operation::Add, vec![left, right])
111    }
112
113    pub fn new_subtract(left: Self, right: Self) -> Self {
114        Self::new(Operation::Subtract, vec![left, right])
115    }
116
117    pub fn new_multiply(left: Self, right: Self) -> Self {
118        Self::new(Operation::Multiply, vec![left, right])
119    }
120
121    pub fn new_divide(numerator: Self, denominator: Self) -> Self {
122        Self::new(Operation::Divide, vec![numerator, denominator])
123    }
124
125    pub fn new_power(base: Self, exponent: Self) -> Self {
126        let negated_constant = match (&exponent.operation, exponent.operands.as_slice()) {
127            (Operation::Negate, [operand]) => operand.constant_value().map(|value| -value),
128            _ => None,
129        };
130        let exponent = match negated_constant {
131            Some(value) => Self::new_const(value),
132            None => exponent,
133        };
134
135        Self::new(Operation::Power, vec![base, exponent])
136    }
137
138    pub fn new_negate(operand: Self) -> Self {
139        Self::new(Operation::Negate, vec![operand])
140    }
141
142    pub fn new_sin(operand: Self) -> Self {
143        Self::new(Operation::Sine, vec![operand])
144    }
145
146    pub fn new_cos(operand: Self) -> Self {
147        Self::new(Operation::Cosine, vec![operand])
148    }
149
150    pub fn new_tan(operand: Self) -> Self {
151        Self::new(Operation::Tangent, vec![operand])
152    }
153
154    pub fn new_asin(operand: Self) -> Self {
155        Self::new(Operation::ArcSine, vec![operand])
156    }
157
158    pub fn new_acos(operand: Self) -> Self {
159        Self::new(Operation::ArcCosine, vec![operand])
160    }
161
162    pub fn new_atan(operand: Self) -> Self {
163        Self::new(Operation::ArcTangent, vec![operand])
164    }
165
166    pub fn new_sinh(operand: Self) -> Self {
167        Self::new(Operation::HyperbolicSine, vec![operand])
168    }
169
170    pub fn new_cosh(operand: Self) -> Self {
171        Self::new(Operation::HyperbolicCosine, vec![operand])
172    }
173
174    pub fn new_tanh(operand: Self) -> Self {
175        Self::new(Operation::HyperbolicTangent, vec![operand])
176    }
177
178    pub fn new_sign(operand: Self) -> Self {
179        Self::new(Operation::Sign, vec![operand])
180    }
181
182    pub fn new_abs(operand: Self) -> Self {
183        Self::new(Operation::AbsoluteValue, vec![operand])
184    }
185
186    pub fn new_exp(operand: Self) -> Self {
187        Self::new(Operation::Exponent, vec![operand])
188    }
189
190    pub fn new_sqrt(operand: Self) -> Self {
191        Self::new(Operation::SquareRoot, vec![operand])
192    }
193
194    pub fn new_log(operand: Self) -> Self {
195        Self::new(Operation::NaturalLogarithm, vec![operand])
196    }
197
198    pub fn new_log10(operand: Self) -> Self {
199        Self::new(Operation::CommonLogarithm, vec![operand])
200    }
201
202    pub fn new_iif(check: Self, if_less_than_zero: Self, otherwise: Self) -> Self {
203        Self::new(
204            Operation::ImmediateIf,
205            vec![check, if_less_than_zero, otherwise],
206        )
207    }
208
209    pub fn derive(&self, by_var: &str) -> Self {
210        let two = T::from(2).expect("2 must be representable by floating-point types");
211
212        match &self.operation {
213            Operation::Constant(_) => Self::new_const(T::zero()),
214            Operation::Variable(name) => {
215                if *name == by_var {
216                    Self::new_const(T::one())
217                } else {
218                    Self::new_const(T::zero())
219                }
220            }
221            Operation::Add => {
222                let (left, right) = self.binary_operands(Operation::Add).unwrap();
223                Self::new_add(left.derive(by_var), right.derive(by_var))
224            }
225            Operation::Subtract => {
226                let (left, right) = self.binary_operands(Operation::Subtract).unwrap();
227                Self::new_subtract(left.derive(by_var), right.derive(by_var))
228            }
229            Operation::Multiply => {
230                let (left, right) = self.binary_operands(Operation::Multiply).unwrap();
231                Self::new_add(
232                    Self::new_multiply(left.derive(by_var), (*right).clone()),
233                    Self::new_multiply((*left).clone(), right.derive(by_var)),
234                )
235            }
236            Operation::Divide => {
237                let (numerator, denominator) = self.binary_operands(Operation::Divide).unwrap();
238                Self::new_divide(
239                    Self::new_subtract(
240                        Self::new_multiply(numerator.derive(by_var), (*denominator).clone()),
241                        Self::new_multiply((*numerator).clone(), denominator.derive(by_var)),
242                    ),
243                    Self::new_multiply((*denominator).clone(), (*denominator).clone()),
244                )
245            }
246            Operation::Power => {
247                let (base, exponent) = self.binary_operands(Operation::Power).unwrap();
248                match exponent.constant_value() {
249                    Some(value) if value == T::zero() => Self::new_const(T::zero()),
250                    Some(value) if value == T::one() => base.derive(by_var),
251                    Some(value) => Self::new_multiply(
252                        Self::new_multiply(
253                            Self::new_const(value),
254                            Self::new_power(base.clone(), Self::new_const(value - T::one())),
255                        ),
256                        base.derive(by_var),
257                    ),
258                    None => Self::new_multiply(
259                        self.clone(),
260                        Self::new_add(
261                            Self::new_multiply(
262                                exponent.derive(by_var),
263                                Self::new_log(base.clone()),
264                            ),
265                            Self::new_multiply(
266                                exponent.clone(),
267                                Self::new_divide(base.derive(by_var), base.clone()),
268                            ),
269                        ),
270                    ),
271                }
272            }
273            Operation::Negate => {
274                let (operand,) = self.unary_operands(Operation::Negate).unwrap();
275                Self::new_negate(operand.derive(by_var))
276            }
277            Operation::Sine => {
278                let (operand,) = self.unary_operands(Operation::Sine).unwrap();
279                Self::new_multiply(operand.derive(by_var), Self::new_cos(operand.clone()))
280            }
281            Operation::Cosine => {
282                let (operand,) = self.unary_operands(Operation::Cosine).unwrap();
283                Self::new_multiply(
284                    operand.derive(by_var),
285                    Self::new_negate(Self::new_sin(operand.clone())),
286                )
287            }
288            Operation::Tangent => {
289                let (operand,) = self.unary_operands(Operation::Tangent).unwrap();
290                Self::new_divide(
291                    operand.derive(by_var),
292                    Self::new_power(Self::new_cos(operand.clone()), Self::new_const(two)),
293                )
294            }
295            Operation::ArcSine => {
296                let (operand,) = self.unary_operands(Operation::ArcSine).unwrap();
297                Self::new_divide(
298                    operand.derive(by_var),
299                    Self::new_sqrt(Self::new_subtract(
300                        Self::new_const(T::one()),
301                        Self::new_power(operand.clone(), Self::new_const(two)),
302                    )),
303                )
304            }
305            Operation::ArcCosine => {
306                let (operand,) = self.unary_operands(Operation::ArcCosine).unwrap();
307                Self::new_divide(
308                    Self::new_negate(operand.derive(by_var)),
309                    Self::new_sqrt(Self::new_subtract(
310                        Self::new_const(T::one()),
311                        Self::new_power(operand.clone(), Self::new_const(two)),
312                    )),
313                )
314            }
315            Operation::ArcTangent => {
316                let (operand,) = self.unary_operands(Operation::ArcTangent).unwrap();
317                Self::new_divide(
318                    operand.derive(by_var),
319                    Self::new_add(
320                        Self::new_const(T::one()),
321                        Self::new_power(operand.clone(), Self::new_const(two)),
322                    ),
323                )
324            }
325            Operation::HyperbolicSine => {
326                let (operand,) = self.unary_operands(Operation::HyperbolicSine).unwrap();
327                Self::new_multiply(operand.derive(by_var), Self::new_cosh(operand.clone()))
328            }
329            Operation::HyperbolicCosine => {
330                let (operand,) = self.unary_operands(Operation::HyperbolicCosine).unwrap();
331                Self::new_multiply(operand.derive(by_var), Self::new_sinh(operand.clone()))
332            }
333            Operation::HyperbolicTangent => {
334                let (operand,) = self.unary_operands(Operation::HyperbolicTangent).unwrap();
335                Self::new_divide(
336                    operand.derive(by_var),
337                    Self::new_power(Self::new_cosh(operand.clone()), Self::new_const(two)),
338                )
339            }
340            Operation::Sign => Self::new_const(T::zero()),
341            Operation::AbsoluteValue => {
342                let (operand,) = self.unary_operands(Operation::AbsoluteValue).unwrap();
343                Self::new_multiply(operand.derive(by_var), Self::new_sign(operand.clone()))
344            }
345            Operation::Exponent => {
346                let (operand,) = self.unary_operands(Operation::Exponent).unwrap();
347                Self::new_multiply(operand.derive(by_var), Self::new_exp(operand.clone()))
348            }
349            Operation::SquareRoot => {
350                let (operand,) = self.unary_operands(Operation::SquareRoot).unwrap();
351                Self::new_divide(
352                    operand.derive(by_var),
353                    Self::new_multiply(Self::new_const(two), Self::new_sqrt(operand.clone())),
354                )
355            }
356            Operation::NaturalLogarithm => {
357                let (operand,) = self.unary_operands(Operation::NaturalLogarithm).unwrap();
358                Self::new_divide(operand.derive(by_var), operand.clone())
359            }
360            Operation::CommonLogarithm => {
361                let (operand,) = self.unary_operands(Operation::CommonLogarithm).unwrap();
362                let ten = T::from(10).expect("10 must be representable by floating-point types");
363                Self::new_divide(
364                    operand.derive(by_var),
365                    Self::new_multiply(operand.clone(), Self::new_const(ten.ln())),
366                )
367            }
368            Operation::ImmediateIf => {
369                let (check, if_less_than_zero, otherwise) =
370                    self.ternary_operands(Operation::ImmediateIf).unwrap();
371                Self::new_iif(
372                    check.clone(),
373                    if_less_than_zero.derive(by_var),
374                    otherwise.derive(by_var),
375                )
376            }
377        }
378    }
379
380    /// Applies real-algebra identities, not strict IEEE-754 equivalences.
381    /// Reassociation may change rounding, overflow, or signed zero; eliminating
382    /// expressions (including redundant iif checks) may remove evaluation errors.
383    pub fn simplify(&self) -> Self {
384        match &self.operation {
385            Operation::Variable(name) => Self::new_var(name),
386            Operation::Constant(value) => Self::new_const(*value),
387            Operation::Add => {
388                let (left, right) = self.binary_operands(Operation::Add).unwrap();
389                Self::simplify_sum(left.simplify(), right.simplify(), false)
390            }
391            Operation::Subtract => {
392                let (left, right) = self.binary_operands(Operation::Subtract).unwrap();
393                Self::simplify_sum(left.simplify(), right.simplify(), true)
394            }
395            Operation::Multiply => {
396                let (left, right) = self.binary_operands(Operation::Multiply).unwrap();
397                Self::simplify_product(left.simplify(), right.simplify())
398            }
399            Operation::Divide => {
400                let (numerator, denominator) = self.binary_operands(Operation::Divide).unwrap();
401                Self::simplify_quotient(numerator.simplify(), denominator.simplify())
402            }
403            Operation::Power => {
404                let (base, exponent) = self.binary_operands(Operation::Power).unwrap();
405                Self::simplify_power(base.simplify(), exponent.simplify())
406            }
407            Operation::Negate => {
408                let (operand,) = self.unary_operands(Operation::Negate).unwrap();
409                Self::simplify_negation(operand.simplify())
410            }
411            Operation::Sine => {
412                let (operand,) = self.unary_operands(Operation::Sine).unwrap();
413                let operand = operand.simplify();
414                match operand.constant_value() {
415                    Some(value) => Self::new_const(value.sin()),
416                    None => Self::simplify_parity(Operation::Sine, operand, true),
417                }
418            }
419            Operation::Cosine => {
420                let (operand,) = self.unary_operands(Operation::Cosine).unwrap();
421                let operand = operand.simplify();
422                match operand.constant_value() {
423                    Some(value) => Self::new_const(value.cos()),
424                    None => Self::simplify_parity(Operation::Cosine, operand, false),
425                }
426            }
427            Operation::Tangent => {
428                let (operand,) = self.unary_operands(Operation::Tangent).unwrap();
429                let operand = operand.simplify();
430                match operand.constant_value() {
431                    Some(value) => Self::new_const(value.tan()),
432                    None => Self::simplify_parity(Operation::Tangent, operand, true),
433                }
434            }
435            Operation::ArcSine => {
436                let (operand,) = self.unary_operands(Operation::ArcSine).unwrap();
437                let operand = operand.simplify();
438                match operand.constant_value() {
439                    Some(value) => Self::new_const(value.asin()),
440                    None => Self::simplify_parity(Operation::ArcSine, operand, true),
441                }
442            }
443            Operation::ArcCosine => {
444                let (operand,) = self.unary_operands(Operation::ArcCosine).unwrap();
445                let operand = operand.simplify();
446                match operand.constant_value() {
447                    Some(value) => Self::new_const(value.acos()),
448                    None => Self::new_acos(operand),
449                }
450            }
451            Operation::ArcTangent => {
452                let (operand,) = self.unary_operands(Operation::ArcTangent).unwrap();
453                let operand = operand.simplify();
454                match operand.constant_value() {
455                    Some(value) => Self::new_const(value.atan()),
456                    None => Self::simplify_parity(Operation::ArcTangent, operand, true),
457                }
458            }
459            Operation::HyperbolicSine => {
460                let (operand,) = self.unary_operands(Operation::HyperbolicSine).unwrap();
461                let operand = operand.simplify();
462                match operand.constant_value() {
463                    Some(value) => Self::new_const(value.sinh()),
464                    None => Self::simplify_parity(Operation::HyperbolicSine, operand, true),
465                }
466            }
467            Operation::HyperbolicCosine => {
468                let (operand,) = self.unary_operands(Operation::HyperbolicCosine).unwrap();
469                let operand = operand.simplify();
470                match operand.constant_value() {
471                    Some(value) => Self::new_const(value.cosh()),
472                    None => Self::simplify_parity(Operation::HyperbolicCosine, operand, false),
473                }
474            }
475            Operation::HyperbolicTangent => {
476                let (operand,) = self.unary_operands(Operation::HyperbolicTangent).unwrap();
477                let operand = operand.simplify();
478                match operand.constant_value() {
479                    Some(value) => Self::new_const(value.tanh()),
480                    None => Self::simplify_parity(Operation::HyperbolicTangent, operand, true),
481                }
482            }
483            Operation::Sign => {
484                let (operand,) = self.unary_operands(Operation::Sign).unwrap();
485                let operand = operand.simplify();
486                match operand.constant_value() {
487                    Some(value) => Self::new_const(Self::sign_value(value)),
488                    None => Self::new_sign(operand),
489                }
490            }
491            Operation::AbsoluteValue => {
492                let (operand,) = self.unary_operands(Operation::AbsoluteValue).unwrap();
493                let operand = operand.simplify();
494                match operand.constant_value() {
495                    Some(value) => Self::new_const(value.abs()),
496                    None => match (&operand.operation, operand.operands.as_slice()) {
497                        (Operation::AbsoluteValue, [_]) => operand,
498                        (Operation::Negate, [inner]) => Self::new_abs(inner.clone()).simplify(),
499                        _ => Self::new_abs(operand),
500                    },
501                }
502            }
503            Operation::Exponent => {
504                let (operand,) = self.unary_operands(Operation::Exponent).unwrap();
505                let operand = operand.simplify();
506                match operand.constant_value() {
507                    Some(value) => Self::new_const(value.exp()),
508                    None => Self::new_exp(operand),
509                }
510            }
511            Operation::SquareRoot => {
512                let (operand,) = self.unary_operands(Operation::SquareRoot).unwrap();
513                let operand = operand.simplify();
514                match operand.constant_value() {
515                    Some(value) => Self::new_const(value.sqrt()),
516                    None => Self::new_sqrt(operand),
517                }
518            }
519            Operation::NaturalLogarithm => {
520                let (operand,) = self.unary_operands(Operation::NaturalLogarithm).unwrap();
521                let operand = operand.simplify();
522                match operand.constant_value() {
523                    Some(value) => Self::new_const(value.ln()),
524                    None => Self::new_log(operand),
525                }
526            }
527            Operation::CommonLogarithm => {
528                let (operand,) = self.unary_operands(Operation::CommonLogarithm).unwrap();
529                let operand = operand.simplify();
530                match operand.constant_value() {
531                    Some(value) => Self::new_const(value.log10()),
532                    None => Self::new_log10(operand),
533                }
534            }
535            Operation::ImmediateIf => {
536                let (check, if_less_than_zero, otherwise) =
537                    self.ternary_operands(Operation::ImmediateIf).unwrap();
538                let check = check.simplify();
539
540                match check.constant_value() {
541                    Some(value) if value < T::zero() => if_less_than_zero.simplify(),
542                    Some(_) => otherwise.simplify(),
543                    None => {
544                        let left = if_less_than_zero.simplify();
545                        let right = otherwise.simplify();
546                        if Self::equivalent_terms(&left, &right) {
547                            left
548                        } else {
549                            Self::new_iif(check, left, right)
550                        }
551                    }
552                }
553            }
554        }
555    }
556
557    fn simplify_sum(left: Self, right: Self, subtract_right: bool) -> Self {
558        let mut terms = Vec::new();
559        let mut constant = T::zero();
560
561        Self::collect_addends(&left, T::one(), &mut terms, &mut constant);
562        let right_sign = if subtract_right { -T::one() } else { T::one() };
563        Self::collect_addends(&right, right_sign, &mut terms, &mut constant);
564
565        let mut result = None;
566        for (coefficient, term) in terms {
567            if coefficient == T::zero() {
568                continue;
569            }
570
571            let term = Self::scale_term(coefficient, term);
572            result = Some(match result {
573                Some(expression) => Self::new_add(expression, term),
574                None => term,
575            });
576        }
577
578        if constant != T::zero() {
579            let constant = Self::new_const(constant);
580            result = Some(match result {
581                Some(expression) => Self::new_add(expression, constant),
582                None => constant,
583            });
584        }
585
586        result.unwrap_or_else(|| Self::new_const(T::zero()))
587    }
588
589    fn collect_addends(expression: &Self, sign: T, terms: &mut Vec<(T, Self)>, constant: &mut T) {
590        match (&expression.operation, expression.operands.as_slice()) {
591            (Operation::Add, [left, right]) => {
592                Self::collect_addends(left, sign, terms, constant);
593                Self::collect_addends(right, sign, terms, constant);
594            }
595            (Operation::Subtract, [left, right]) => {
596                Self::collect_addends(left, sign, terms, constant);
597                Self::collect_addends(right, -sign, terms, constant);
598            }
599            (Operation::Negate, [inner]) => {
600                Self::collect_addends(inner, -sign, terms, constant);
601            }
602            (Operation::Constant(value), []) => *constant = *constant + sign * *value,
603            _ => {
604                let (coefficient, term) = expression.coefficient_and_term();
605                let coefficient = sign * coefficient;
606
607                if let Some((existing_coefficient, _)) = terms
608                    .iter_mut()
609                    .find(|(_, existing)| Self::equivalent_terms(existing, &term))
610                {
611                    *existing_coefficient = *existing_coefficient + coefficient;
612                } else {
613                    terms.push((coefficient, term));
614                }
615            }
616        }
617    }
618
619    fn coefficient_and_term(&self) -> (T, Self) {
620        match (&self.operation, self.operands.as_slice()) {
621            (Operation::Multiply, [coefficient, term]) => match coefficient.constant_value() {
622                Some(value) => (value, term.clone()),
623                None => (T::one(), self.clone()),
624            },
625            (Operation::Negate, [term]) => (-T::one(), term.clone()),
626            _ => (T::one(), self.clone()),
627        }
628    }
629
630    fn scale_term(coefficient: T, term: Self) -> Self {
631        if coefficient == T::zero() {
632            Self::new_const(T::zero())
633        } else if coefficient == T::one() {
634            term
635        } else if coefficient == -T::one() {
636            Self::new_negate(term)
637        } else {
638            Self::new_multiply(Self::new_const(coefficient), term)
639        }
640    }
641
642    fn simplify_product(left: Self, right: Self) -> Self {
643        let mut coefficient = T::one();
644        let mut factors = Vec::new();
645        Self::collect_factors(left, &mut coefficient, &mut factors);
646        Self::collect_factors(right, &mut coefficient, &mut factors);
647        if factors.is_empty() || coefficient == T::zero() {
648            return Self::new_const(coefficient);
649        }
650
651        let mut powers: Vec<(Self, T)> = Vec::new();
652        for factor in factors {
653            let (base, exponent) = match (&factor.operation, factor.operands.as_slice()) {
654                (Operation::Power, [base, exponent]) => match exponent.constant_value() {
655                    Some(n) if n.is_finite() && n > T::zero() && n.fract() == T::zero() => {
656                        (base.clone(), n)
657                    }
658                    // Do not merge fractional, negative, or symbolic powers.
659                    _ => {
660                        powers.push((factor, T::one()));
661                        continue;
662                    }
663                },
664                _ => (factor, T::one()),
665            };
666            if let Some((_, existing)) = powers.iter_mut().find(|(term, n)| {
667                Self::equivalent_terms(term, &base) && (*n + exponent).is_finite()
668            }) {
669                *existing = *existing + exponent;
670            } else {
671                powers.push((base, exponent));
672            }
673        }
674        let term = powers
675            .into_iter()
676            .map(|(base, exponent)| Self::simplify_power(base, Self::new_const(exponent)))
677            .reduce(Self::new_multiply)
678            .unwrap();
679        Self::scale_term(coefficient, term)
680    }
681
682    fn collect_factors(expression: Self, coefficient: &mut T, factors: &mut Vec<Self>) {
683        match expression.operation {
684            Operation::Constant(value) => *coefficient = *coefficient * value,
685            Operation::Negate => {
686                *coefficient = -*coefficient;
687                Self::collect_factors(
688                    expression.operands.into_iter().next().unwrap(),
689                    coefficient,
690                    factors,
691                );
692            }
693            Operation::Multiply => {
694                for operand in expression.operands {
695                    Self::collect_factors(operand, coefficient, factors);
696                }
697            }
698            _ => factors.push(expression),
699        }
700    }
701
702    // Compare products as multisets without imposing an arbitrary printed order.
703    fn equivalent_terms(left: &Self, right: &Self) -> bool {
704        if left == right {
705            return true;
706        }
707        if left.operation != Operation::Multiply || right.operation != Operation::Multiply {
708            return false;
709        }
710        fn flatten<'e, 'a, T: Float>(
711            expression: &'e MathExpr<'a, T>,
712            factors: &mut Vec<&'e MathExpr<'a, T>>,
713        ) {
714            if expression.operation == Operation::Multiply {
715                for operand in &expression.operands {
716                    flatten(operand, factors);
717                }
718            } else {
719                factors.push(expression);
720            }
721        }
722        let (mut lhs, mut rhs) = (Vec::new(), Vec::new());
723        flatten(left, &mut lhs);
724        flatten(right, &mut rhs);
725        if lhs.len() != rhs.len() {
726            return false;
727        }
728        for factor in lhs {
729            if let Some(index) = rhs.iter().position(|other| factor == *other) {
730                rhs.swap_remove(index);
731            } else {
732                return false;
733            }
734        }
735        true
736    }
737
738    fn simplify_parity(operation: Operation<'a, T>, operand: Self, odd: bool) -> Self {
739        let (coefficient, term) = operand.coefficient_and_term();
740        if coefficient < T::zero() {
741            let positive = Self::scale_term(-coefficient, term);
742            let function = Self::new(operation, vec![positive]);
743            if odd {
744                Self::new_negate(function)
745            } else {
746                function
747            }
748        } else {
749            Self::new(operation, vec![operand])
750        }
751    }
752
753    fn simplify_quotient(numerator: Self, denominator: Self) -> Self {
754        match (numerator.constant_value(), denominator.constant_value()) {
755            (Some(numerator), Some(denominator)) => Self::new_const(numerator / denominator),
756            (Some(value), _) if value == T::zero() => Self::new_const(T::zero()),
757            _ if numerator == denominator => Self::new_const(T::one()),
758            (_, Some(value)) if value == T::one() => numerator,
759            (_, Some(value)) if value == -T::one() => Self::simplify_negation(numerator),
760            (_, Some(value)) if value.is_finite() && value != T::zero() => {
761                let (coefficient, term) = numerator.coefficient_and_term();
762                let scaled = coefficient / value;
763                if scaled.is_finite() && (scaled != T::zero() || coefficient == T::zero()) {
764                    Self::scale_term(scaled, term)
765                } else {
766                    Self::new_divide(numerator, denominator)
767                }
768            }
769            _ => Self::new_divide(numerator, denominator),
770        }
771    }
772
773    fn simplify_power(base: Self, exponent: Self) -> Self {
774        if base.constant_value() == Some(T::one()) {
775            return Self::new_const(T::one());
776        }
777        if let Some(exponent_value) = exponent.constant_value() {
778            if exponent_value == T::zero() {
779                return Self::new_const(T::one());
780            }
781            if exponent_value == T::one() {
782                return base;
783            }
784
785            if let (Operation::Power, [inner_base, inner_exponent]) =
786                (&base.operation, base.operands.as_slice())
787                && let Some(inner_exponent) = inner_exponent.constant_value()
788            {
789                let exponents_are_integers = inner_exponent.is_finite()
790                    && inner_exponent.fract() == T::zero()
791                    && exponent_value.is_finite()
792                    && exponent_value.fract() == T::zero();
793                if exponents_are_integers {
794                    return Self::simplify_power(
795                        inner_base.clone(),
796                        Self::new_const(inner_exponent * exponent_value),
797                    );
798                }
799            }
800
801            if let Some(base_value) = base.constant_value() {
802                return Self::new_const(base_value.powf(exponent_value));
803            }
804        }
805
806        Self::new_power(base, exponent)
807    }
808
809    fn simplify_negation(operand: Self) -> Self {
810        if let Some(value) = operand.constant_value() {
811            return Self::new_const(-value);
812        }
813
814        match (&operand.operation, operand.operands.as_slice()) {
815            (Operation::Negate, [inner]) => inner.clone(),
816            (Operation::Multiply, _) => Self::simplify_product(Self::new_const(-T::one()), operand),
817            _ => Self::new_negate(operand),
818        }
819    }
820
821    fn constant_value(&self) -> Option<T> {
822        match self.operation {
823            Operation::Constant(value) => Some(value),
824            _ => None,
825        }
826    }
827
828    fn sign_value(value: T) -> T {
829        if value.is_nan() {
830            value
831        } else if value > T::zero() {
832            T::one()
833        } else if value < T::zero() {
834            -T::one()
835        } else {
836            T::zero()
837        }
838    }
839
840    pub fn evaluate(&self, args: &HashMap<&str, T>) -> Result<T, EvaluationError<'a, T>> {
841        match &self.operation {
842            Operation::Variable(name) => args
843                .get(*name)
844                .copied()
845                .ok_or(EvaluationError::VariableNotDefined(name)),
846            Operation::Constant(value) => Ok(*value),
847            Operation::Add => {
848                let (left, right) = self.binary_operands(Operation::Add)?;
849                Ok(left.evaluate(args)? + right.evaluate(args)?)
850            }
851            Operation::Subtract => {
852                let (left, right) = self.binary_operands(Operation::Subtract)?;
853                Ok(left.evaluate(args)? - right.evaluate(args)?)
854            }
855            Operation::Multiply => {
856                let (left, right) = self.binary_operands(Operation::Multiply)?;
857                Ok(left.evaluate(args)? * right.evaluate(args)?)
858            }
859            Operation::Divide => {
860                let (numerator, denominator) = self.binary_operands(Operation::Divide)?;
861                Ok(numerator.evaluate(args)? / denominator.evaluate(args)?)
862            }
863            Operation::Power => {
864                let (base, exponent) = self.binary_operands(Operation::Power)?;
865                Ok(base.evaluate(args)?.powf(exponent.evaluate(args)?))
866            }
867            Operation::Negate => {
868                let (operand,) = self.unary_operands(Operation::Negate)?;
869                Ok(-operand.evaluate(args)?)
870            }
871            Operation::Sine => {
872                let (operand,) = self.unary_operands(Operation::Sine)?;
873                Ok(operand.evaluate(args)?.sin())
874            }
875            Operation::Cosine => {
876                let (operand,) = self.unary_operands(Operation::Cosine)?;
877                Ok(operand.evaluate(args)?.cos())
878            }
879            Operation::Tangent => {
880                let (operand,) = self.unary_operands(Operation::Tangent)?;
881                Ok(operand.evaluate(args)?.tan())
882            }
883            Operation::ArcSine => {
884                let (operand,) = self.unary_operands(Operation::ArcSine)?;
885                Ok(operand.evaluate(args)?.asin())
886            }
887            Operation::ArcCosine => {
888                let (operand,) = self.unary_operands(Operation::ArcCosine)?;
889                Ok(operand.evaluate(args)?.acos())
890            }
891            Operation::ArcTangent => {
892                let (operand,) = self.unary_operands(Operation::ArcTangent)?;
893                Ok(operand.evaluate(args)?.atan())
894            }
895            Operation::HyperbolicSine => {
896                let (operand,) = self.unary_operands(Operation::HyperbolicSine)?;
897                Ok(operand.evaluate(args)?.sinh())
898            }
899            Operation::HyperbolicCosine => {
900                let (operand,) = self.unary_operands(Operation::HyperbolicCosine)?;
901                Ok(operand.evaluate(args)?.cosh())
902            }
903            Operation::HyperbolicTangent => {
904                let (operand,) = self.unary_operands(Operation::HyperbolicTangent)?;
905                Ok(operand.evaluate(args)?.tanh())
906            }
907            Operation::Sign => {
908                let (operand,) = self.unary_operands(Operation::Sign)?;
909                Ok(Self::sign_value(operand.evaluate(args)?))
910            }
911            Operation::AbsoluteValue => {
912                let (operand,) = self.unary_operands(Operation::AbsoluteValue)?;
913                Ok(operand.evaluate(args)?.abs())
914            }
915            Operation::Exponent => {
916                let (operand,) = self.unary_operands(Operation::Exponent)?;
917                Ok(operand.evaluate(args)?.exp())
918            }
919            Operation::SquareRoot => {
920                let (operand,) = self.unary_operands(Operation::SquareRoot)?;
921                Ok(operand.evaluate(args)?.sqrt())
922            }
923            Operation::NaturalLogarithm => {
924                let (operand,) = self.unary_operands(Operation::NaturalLogarithm)?;
925                Ok(operand.evaluate(args)?.ln())
926            }
927            Operation::CommonLogarithm => {
928                let (operand,) = self.unary_operands(Operation::CommonLogarithm)?;
929                Ok(operand.evaluate(args)?.log10())
930            }
931            Operation::ImmediateIf => {
932                let (check, if_less_than_zero, otherwise) =
933                    self.ternary_operands(Operation::ImmediateIf)?;
934                if check.evaluate(args)? < T::zero() {
935                    if_less_than_zero.evaluate(args)
936                } else {
937                    otherwise.evaluate(args)
938                }
939            }
940        }
941    }
942
943    fn unary_operands(
944        &self,
945        operation: Operation<'a, T>,
946    ) -> Result<(&Self,), EvaluationError<'a, T>> {
947        match self.operands.as_slice() {
948            [operand] => Ok((operand,)),
949            operands => Err(EvaluationError::InvalidOperandCount {
950                operation,
951                expected: 1,
952                actual: operands.len(),
953            }),
954        }
955    }
956
957    fn binary_operands(
958        &self,
959        operation: Operation<'a, T>,
960    ) -> Result<(&Self, &Self), EvaluationError<'a, T>> {
961        match self.operands.as_slice() {
962            [left, right] => Ok((left, right)),
963            operands => Err(EvaluationError::InvalidOperandCount {
964                operation,
965                expected: 2,
966                actual: operands.len(),
967            }),
968        }
969    }
970
971    fn ternary_operands(
972        &self,
973        operation: Operation<'a, T>,
974    ) -> Result<(&Self, &Self, &Self), EvaluationError<'a, T>> {
975        match self.operands.as_slice() {
976            [first, second, third] => Ok((first, second, third)),
977            operands => Err(EvaluationError::InvalidOperandCount {
978                operation,
979                expected: 3,
980                actual: operands.len(),
981            }),
982        }
983    }
984}
985
986impl<T: Float> Display for Operation<'_, T> {
987    fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result {
988        match self {
989            Operation::Variable(name) => write!(formatter, "{name}"),
990            Operation::Constant(_) => write!(formatter, "Constant"),
991            Operation::Add => write!(formatter, "+"),
992            Operation::Subtract => write!(formatter, "-"),
993            Operation::Multiply => write!(formatter, "*"),
994            Operation::Divide => write!(formatter, "/"),
995            Operation::Power => write!(formatter, "^"),
996            Operation::Negate => write!(formatter, "-"),
997            Operation::Sine => write!(formatter, "sin"),
998            Operation::Cosine => write!(formatter, "cos"),
999            Operation::Tangent => write!(formatter, "tan"),
1000            Operation::ArcSine => write!(formatter, "asin"),
1001            Operation::ArcCosine => write!(formatter, "acos"),
1002            Operation::ArcTangent => write!(formatter, "atan"),
1003            Operation::HyperbolicSine => write!(formatter, "sinh"),
1004            Operation::HyperbolicCosine => write!(formatter, "cosh"),
1005            Operation::HyperbolicTangent => write!(formatter, "tanh"),
1006            Operation::Sign => write!(formatter, "sign"),
1007            Operation::AbsoluteValue => write!(formatter, "abs"),
1008            Operation::Exponent => write!(formatter, "exp"),
1009            Operation::SquareRoot => write!(formatter, "sqrt"),
1010            Operation::NaturalLogarithm => write!(formatter, "log"),
1011            Operation::CommonLogarithm => write!(formatter, "log10"),
1012            Operation::ImmediateIf => write!(formatter, "iif"),
1013        }
1014    }
1015}
1016
1017impl<T: Float + Display> Display for MathExpr<'_, T> {
1018    fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result {
1019        match (&self.operation, self.operands.as_slice()) {
1020            (Operation::Variable(name), []) => write!(formatter, "{name}"),
1021            (Operation::Constant(value), []) => write!(formatter, "{value}"),
1022            (Operation::Add, [left, right]) => write!(formatter, "({left} + {right})"),
1023            (Operation::Subtract, [left, right]) => write!(formatter, "({left} - {right})"),
1024            (Operation::Multiply, [left, right]) => write!(formatter, "({left} * {right})"),
1025            (Operation::Divide, [numerator, denominator]) => {
1026                write!(formatter, "({numerator} / {denominator})")
1027            }
1028            (Operation::Power, [base, exponent]) => {
1029                write!(formatter, "({base} ^ {exponent})")
1030            }
1031            (Operation::Negate, [operand]) => write!(formatter, "(-{operand})"),
1032            (Operation::Sine, [operand]) => write!(formatter, "sin({operand})"),
1033            (Operation::Cosine, [operand]) => write!(formatter, "cos({operand})"),
1034            (Operation::Tangent, [operand]) => write!(formatter, "tan({operand})"),
1035            (Operation::ArcSine, [operand]) => write!(formatter, "asin({operand})"),
1036            (Operation::ArcCosine, [operand]) => write!(formatter, "acos({operand})"),
1037            (Operation::ArcTangent, [operand]) => write!(formatter, "atan({operand})"),
1038            (Operation::HyperbolicSine, [operand]) => write!(formatter, "sinh({operand})"),
1039            (Operation::HyperbolicCosine, [operand]) => write!(formatter, "cosh({operand})"),
1040            (Operation::HyperbolicTangent, [operand]) => write!(formatter, "tanh({operand})"),
1041            (Operation::Sign, [operand]) => write!(formatter, "sign({operand})"),
1042            (Operation::AbsoluteValue, [operand]) => write!(formatter, "abs({operand})"),
1043            (Operation::Exponent, [operand]) => write!(formatter, "exp({operand})"),
1044            (Operation::SquareRoot, [operand]) => write!(formatter, "sqrt({operand})"),
1045            (Operation::NaturalLogarithm, [operand]) => write!(formatter, "log({operand})"),
1046            (Operation::CommonLogarithm, [operand]) => write!(formatter, "log10({operand})"),
1047            (Operation::ImmediateIf, [check, if_less_than_zero, otherwise]) => {
1048                write!(formatter, "iif({check}, {if_less_than_zero}, {otherwise})")
1049            }
1050            _ => Err(std::fmt::Error),
1051        }
1052    }
1053}
1054
1055impl<T: Float> Display for EvaluationError<'_, T> {
1056    fn fmt(&self, formatter: &mut Formatter<'_>) -> std::fmt::Result {
1057        match self {
1058            EvaluationError::InvalidOperandCount {
1059                operation,
1060                expected,
1061                actual,
1062            } => write!(
1063                formatter,
1064                "{operation} expects {expected} operands, but received {actual}"
1065            ),
1066            EvaluationError::VariableNotDefined(name) => {
1067                write!(formatter, "Variable {name} not defined")
1068            }
1069        }
1070    }
1071}
1072
1073// impl<T: Float> Error for EvaluationError<T> {}
1074
1075#[cfg(test)]
1076mod tests;