//! This crate contains logic for an application to parse and evaluate
//! basic rational number arithmetic using standard operator precedence and
//! associativity.
#![no_std]
#![deny(
    unsafe_code,
    unused,
    warnings,
    clippy::all,
    clippy::cargo,
    clippy::nursery,
    clippy::pedantic
)]
#![allow(
    clippy::arithmetic_side_effects,
    clippy::exhaustive_enums,
    clippy::implicit_return,
    clippy::integer_arithmetic,
    clippy::into_iter_on_ref,
    clippy::question_mark,
    clippy::single_char_lifetime_names,
    clippy::unseparated_literal_suffix
)]
extern crate alloc;
use alloc::string::{String, ToString};
use alloc::vec;
use alloc::vec::Vec;
use cache::Cache;
use core::convert;
use core::fmt::{self, Display, Formatter};
use num_bigint::{BigInt, BigUint, Sign};
use num_rational::Ratio;
use num_integer::Integer;
use num_traits::Pow;
use E::{
    DivByZero, ExpDivByZero, ExpIsNotInt, InvalidAbs, InvalidDec, InvalidPar, InvalidQuit,
    InvalidRecall, MissingLF, MissingTerm, NotEnoughPrevResults, NotNonNegIntFact, TrailingSyms,
};
use O::{Empty, Exit, Prev, Val};
/// Fixed-sized cache that automatically overwrites the oldest data
/// when a new item is added and the cache is full. One can think of
/// [`Cache`] as a very limited but more performant [`VecDeque`][alloc::collections::VecDeque] that only
/// adds new data or reads old data.
pub mod cache;
/// A value from a previous expression that is to be
/// displayed potentially in decimal form.
#[derive(Debug)]
pub struct PrevVal<'a> {
    /// A cached value from a previous expression.
    val: &'a Ratio<BigInt>,
    /// None iff the previous value is to be displayed
    /// in fractional form; otherwise contains the number
    /// of fractional digits from 0 to 9 `val` will be rounded
    /// to.
    round: Option<u8>,
}
impl<'a> Display for PrevVal<'a> {
    #[inline]
    #[allow(unsafe_code, clippy::as_conversions, clippy::indexing_slicing)]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        if let Some(rem) = self.round {
            let r = rem as usize;
            let mult = BigInt::from_biguint(Sign::Plus, BigUint::new(vec![10])).pow(r);
            // int < 0 iff val <= -1. frac < 0 iff val is a negative non-integer.
            let (int, frac) = (self.val * &mult).round().numer().div_rem(&mult);
            let int_str = int.to_string().into_bytes();
            let frac_str = frac.to_string().into_bytes();
            // The max length is the length of int_str plus the number of fractional digits
            // plus a possible negative sign plus a possible decimal point.
            // At most we will over-allocate by 2 precisely when int is negative
            // and r is 0.
            let mut v = Vec::with_capacity(int_str.len() + 2 + r);
            // In the case val is a negative value greater than -1,
            // we have to add the negative sign since 0 is unsigned.
            // Technically this can panic! if one of the Strings returned from
            // to_string is empty; however that is a bug, or at least undesired
            // behavior, in the to_string implementation from BigInt.
            let frac_val = match (int_str[0] == b'-', frac_str[0] == b'-') {
                (false, true) => {
                    v.push(b'-');
                    &frac_str[1..]
                }
                (true, true) => &frac_str[1..],
                _ => frac_str.as_slice(),
            };
            v.extend_from_slice(int_str.as_slice());
            if r > 0 {
                v.push(b'.');
                let len = v.len();
                // frac_val.len() is <= r.
                while v.len() < len + r - frac_val.len() {
                    v.push(b'0');
                }
                v.extend_from_slice(frac_val);
            }
            // SAFETY:
            // v contains precisely the UTF-8 code units returned from Strings
            // returned from the to_string function on the integer and fraction part of
            // val plus optionally the single byte encodings of ".", "-", and "0".
             writeln!(f, "> {}", unsafe { String::from_utf8_unchecked(v) })
        } else {
            writeln!(f, "> {}", self.val)
        }
    }
}
/// The error that is returned when attempting
/// to evaluate the input.
#[derive(Clone, Copy, Debug)]
pub enum E {
    /// The input was not terminated with a line feed.
    MissingLF,
    /// The input began with a `q` but had other non-spaces
    /// that followed it.
    InvalidQuit,
    /// The input began with an `=` but
    /// was otherwise syntactically invalid.
    InvalidRecall,
    /// A sub-expression in the input would have led
    /// to a division by zero.
    DivByZero(usize),
    /// A sub-expression in the input would have led
    /// to a rational number that was not 0 or 1 to be
    /// raised to a non-integer power.
    ExpIsNotInt(usize),
    /// A sub-expression in the input would have led
    /// to 0 being raised to a negative power which itself
    /// would have led to a division by zero.
    ExpDivByZero(usize),
    /// A sub-expression in the input would have led
    /// to a non-integer factorial or a negative integer factorial.
    NotNonNegIntFact(usize),
    /// The input contained a non-empty sequence of digits followed
    /// by `.` which was not followed by a non-empty sequence of digits.
    InvalidDec(usize),
    /// A recall expression was used to recall the *i*-th previous result,
    /// but there are fewer than *i* previous results where
    /// *i ∈ {1, 2, 3, 4, 5, 6, 7, 8}*.
    NotEnoughPrevResults(u8),
    /// The input did not contain a closing `|`.
    InvalidAbs(usize),
    /// The input did not contain a closing `)`.
    InvalidPar(usize),
    /// A sub-expression in the input had a missing terminal expression
    /// where a terminal expression is a decimal literal expression,
    /// recall expression, absolute value expression, or a parenthetical
    /// expression.
    MissingTerm(usize),
    /// The input started with a valid expression but was immediately followed
    /// by symbols that could not be chained with the preceding expression.
    TrailingSyms(usize),
}
impl Display for E {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match *self {
            MissingLF => f.write_str("The last character is not a line feed.\n"),
            InvalidRecall => f.write_str("Invalid recall statement. A recall statement must be of the extended regex form: ^ *= *[0-9]?@[1-8]? *$.\n"),
            InvalidQuit => f.write_str("Invalid quit statement. A quit statement must be of the extended regex form: ^ *q *$.\n"),
            DivByZero(u) => writeln!(f, "Division by zero ending at position {u}."),
            ExpIsNotInt(u) => writeln!(f, "Non-integer exponent with a base that was not 0 or 1 ending at position {u}."),
            ExpDivByZero(u) => writeln!(f, "Non-negative exponent with a base of 0 ending at position {u}."),
            NotNonNegIntFact(u) => writeln!(f, "Factorial of a rational number that was not a non-negative integer ending at position {u}."),
            InvalidDec(u) => writeln!(f, "Invalid decimal literal expression ending at position {u}. A decimal literal expression must be of the extended regex form:  *[0-9]+(\\.[0-9]+)?."),
            NotEnoughPrevResults(len) => writeln!(f, "There are only {len} previous results."),
            InvalidAbs(u) => writeln!(f, "Invalid absolute value expression ending at position {u}. An absolute value expression is an addition expression enclosed in '||'."),
            InvalidPar(u) => writeln!(f, "Invalid parenthetical expression ending at position {u}. A parenthetical expression is an addition expression enclosed in '()'."),
            MissingTerm(u) => writeln!(f, "Missing terminal expression at position {u}. A terminal expression is a decimal literal expression, recall expression, or addition expression enclosed in vertical bars or parentheses."),
            TrailingSyms(u) => writeln!(f, "Trailing symbols starting at position {u}."),
        }
    }
}
/// A successful evaluation of an input.
#[derive(Debug)]
pub enum O<'a> {
    /// The result of a passed expression.
    Val(&'a Ratio<BigInt>),
    /// The previous result of the requested
    /// recall statement.
    Prev(PrevVal<'a>),
    /// The input contained all spaces which is part of our language
    /// but does not do anything.
    Empty,
    /// A quit statement was issued to terminate the program.
    Exit,
}
impl<'a> Display for O<'a> {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match *self {
            Val(r) => writeln!(f, "> {r}"),
            Prev(ref p) => p.fmt(f),
            Empty | Exit => Ok(()),
        }
    }
}
/// Evaluates the supplied input.
pub struct Evaluator<'input, 'cache, 'exp> {
    /// The input to be evaluated.
    utf8: &'input [u8],
    /// The index within `utf8` that evaluation needs to continue.
    /// We use this instead of slicing from `utf8` since we want
    /// to be able to report the position within the input
    /// that an error occurs.
    i: usize,
    /// The cache of previously evaluated expressions.
    prev: &'cache mut Cache<Ratio<BigInt>, 8>,
    /// Buffer used to evaluate exponentiation sub-expressions.
    /// We require buffering exponentiation sub-expressions due
    /// to their being right-associative. Instead of repeatedly
    /// creating temporary internal buffers, we rely on a supplied
    /// buffer that can be re-used across multiple evaluations.
    exp_cache: &'exp mut Vec<Ratio<BigInt>>,
}
impl<'input, 'cache, 'exp> Evaluator<'input, 'cache, 'exp> {
    /// Creates an `Evaluator<'input, 'cache, 'exp>` based on the supplied arguments.
    #[inline]
    pub fn new(
        utf8: &'input [u8],
        prev: &'cache mut Cache<Ratio<BigInt>, 8>,
        exp_cache: &'exp mut Vec<Ratio<BigInt>>,
    ) -> Evaluator<'input, 'cache, 'exp> {
        Self {
            utf8,
            i: 0,
            prev,
            exp_cache,
        }
    }
    /// Evaluates the input consuming the `Evaluator<'input, 'cache, 'exp>`.

    /// # Errors
    ///
    /// Returns an [`E`] iff the input violates the calc language.
    #[inline]
    #[allow(clippy::indexing_slicing)]
    pub fn evaluate(mut self) -> Result<O<'cache>, E> {
        self.utf8 = if self.utf8.last().map_or(true, |b| *b != b'\n') {
            return Err(MissingLF)
        } else {
                &self.utf8[..(self.utf8.len() - 1)]
        };
        self.consume_ws();
        let Some(b) = self.utf8.get(self.i) else {
            return Ok(Empty)
        };
        if *b == b'=' {
            self.i += 1;
            self.consume_ws();
            let Some(b2) = self.utf8.get(self.i) else {
                return Err(InvalidRecall)
            };
            let b3 = *b2;
            let round = b3.is_ascii_digit().then(|| {
                self.i += 1;
                b3 - b'0'
            });
            self.get_recall().map(|val| Prev(PrevVal { val, round }))
        } else if *b == b'q' {
            self.i += 1;
            self.consume_ws();
            if self.i == self.utf8.len() {
                Ok(Exit)
            } else {
                Err(InvalidQuit)
            }
        } else {
            self.get_adds().and_then(move |r| {
                self.consume_ws();
                if self.i == self.utf8.len() {
                    Ok(Val(self.prev.push(r)))
                } else {
                    Err(TrailingSyms(self.i))
                }
            })
        }
    }
    /// Reads from the input until the next non-space byte value.
    #[inline]
    #[allow(clippy::indexing_slicing)]
    fn consume_ws(&mut self) {
        // ControlFlow makes more sense to use in try_fold; however due to a lack
        // of a map_or_else function, it is easier to simply return a Result with
        // Err taking the role of ControlFlow::Break.
        self.i += self.utf8[self.i..]
            .into_iter()
            .try_fold(0, |val, b| {
                if *b == b' ' {
                    Ok(val + 1)
                } else {
                    // Only an "error" in the sense
                    // we want try_fold to terminate.
                    Err(val)
                }
            })
            .map_or_else(convert::identity, convert::identity);
    }
    /// Evaluates addition expressions as defined in the calc language.
    /// This function is used for both addition and subtraction operations which
    /// themselves are based on multiplication expressions.
    #[inline]
    fn get_adds(&mut self) -> Result<Ratio<BigInt>, E> {
        let mut left = self.get_mults()?;
        let mut j;
        self.consume_ws();
        while let Some(i) = self.utf8.get(self.i) {
            j = *i;
            self.consume_ws();
            if j == b'+' {
                self.i += 1;
                self.consume_ws();
                left += self.get_mults()?;
            } else if j == b'-' {
                self.i += 1;
                self.consume_ws();
                left -= self.get_mults()?;
            } else {
                break;
            }
        }
        Ok(left)
    }
    /// Evaluates multiplication expressions as defined in the calc language.
    /// This function is used for both multiplication and division operations which
    /// themselves are based on negation expressions.
    #[inline]
    fn get_mults(&mut self) -> Result<Ratio<BigInt>, E> {
        let mut left = self.get_neg()?;
        let mut right;
        let mut j;
        self.consume_ws();
        while let Some(i) = self.utf8.get(self.i) {
            j = *i;
            self.consume_ws();
            if j == b'*' {
                self.i += 1;
                self.consume_ws();
                left *= self.get_neg()?;
            } else if j == b'/' {
                self.i += 1;
                self.consume_ws();
                right = self.get_neg()?;
                if right.numer().sign() == Sign::NoSign {
                    return Err(DivByZero(self.i));
                }
                left /= right;
            } else {
                break;
            }
        }
        Ok(left)
    }
    /// Evaluates negation expressions as defined in the calc language.
    /// This function is based on exponentiation expressions.
    #[inline]
    fn get_neg(&mut self) -> Result<Ratio<BigInt>, E> {
        let mut count = 0usize;
        while let Some(b) = self.utf8.get(self.i) {
            if *b == b'-' {
                self.i += 1;
                self.consume_ws();
                count += 1;
            } else {
                break;
            }
        }
        self.get_exps()
            .map(|val| if count & 1 == 0 { val } else { -val })
    }
    /// Evaluates exponentiation expressions as defined in the calc language.
    /// This function is based on negation expressions.
    #[inline]
    #[allow(clippy::unwrap_used, clippy::unwrap_in_result)]
    fn get_exps(&mut self) -> Result<Ratio<BigInt>, E> {
        let mut t = self.get_fact()?;
        let ix = self.exp_cache.len();
        let mut prev;
        let mut numer;
        self.exp_cache.push(t);
        self.consume_ws();
        let mut j;
        while let Some(i) = self.utf8.get(self.i) {
            j = *i;
            self.consume_ws();
            if j == b'^' {
                self.i += 1;
                self.consume_ws();
                t = self.get_neg()?;
                // This is safe since we always push a value into it
                // before entering the loop.
                prev = self.exp_cache.last().unwrap();
                numer = prev.numer();
                // Equiv to checking if prev is 0.
                if numer.sign() == Sign::NoSign {
                    if t.numer().sign() == Sign::Minus {
                        return Err(ExpDivByZero(self.i));
                    }
                    self.exp_cache.push(t);
                } else if prev.is_integer() {
                    if numer == &BigInt::new(Sign::Plus, vec![1]) {
                        // 1 raised to anything is 1, so we don't bother
                        // storing the exponent.
                    } else if t.is_integer() {
                        self.exp_cache.push(t);
                    } else {
                        return Err(ExpIsNotInt(self.i));
                    }
                } else if t.is_integer() {
                    self.exp_cache.push(t);
                } else {
                    return Err(ExpIsNotInt(self.i));
                }
            } else {
                break;
            }
        }
        self.exp_cache.drain(ix..).try_rfold(
            Ratio::from_integer(BigInt::new(Sign::Plus, vec![1])),
            |exp, base| {
                if exp.is_integer() {
                    Ok(base.pow(exp.numer()))
                } else if base.numer().sign() == Sign::NoSign {
                    Ok(base)
                } else {
                    Err(ExpIsNotInt(self.i))
                }
            },
        )
    }
    /// Evaluates factorial expressions as defined in the calc language.
    /// This function is based on terminal expressions.
    #[inline]
    fn get_fact(&mut self) -> Result<Ratio<BigInt>, E> {
        /// Calculates the factorial of `val`.
        #[inline]
        fn fact(mut val: BigUint) -> BigUint {
            let zero = BigUint::new(Vec::new());
            let one = BigUint::new(vec![1]);
            let mut calc = BigUint::new(vec![1]);
            while val > zero {
                calc *= &val;
                val -= &one;
            }
            calc
        }
        let t = self.get_term()?;
        let Some(b) = self.utf8.get(self.i) else {
            return Ok(t)
        };
        if *b == b'!' {
            self.i += 1;
            if t.is_integer() {
                // We can make a copy of self.i here, or call map_or instead
                // of map_or_else.
                let i = self.i;
                t.numer()
                    .to_biguint()
                    .map_or_else(|| Err(NotNonNegIntFact(i)), |val| {
                        let mut factorial = fact(val);
                        while let Some(b2) = self.utf8.get(self.i) {
                            if *b2 == b'!' {
                                self.i += 1;
                                factorial = fact(factorial);
                            } else {
                                break;
                            }
                        }
                        Ok(Ratio::from_integer(BigInt::from_biguint(
                            Sign::Plus,
                            factorial,
                        )))
                    })
            } else {
                Err(NotNonNegIntFact(self.i))
            }
        } else {
            Ok(t)
        }
    }
    /// Evaluates terminal expressions as defined in the calc language.
    /// This function is based on parenthetical expressions, absolute value
    /// expressions, recall expressions, and numer literal expressions.
    #[inline]
    #[allow(clippy::option_if_let_else)]
    fn get_term(&mut self) -> Result<Ratio<BigInt>, E> {
        match self.get_rational() {
            Ok(o) => match o {
                Some(r) => Ok(r),
                None => match self.get_prev() {
                    Ok(o2) => match o2 {
                        Some(r2) => Ok(r2.clone()),
                        None => self
                            .get_abs()
                            .and_then(|o3| o3.map_or_else(|| self.get_par(), Ok)),
                    },
                    Err(e2) => Err(e2),
                },
            },
            Err(e) => Err(e),
        }
    }
    /// Evaluates parenthetical expressions as defined in the calc language.
    /// This function is based on addition expressions.
    /// This is the last terminal expression attempted when needing
    /// a terminal expression; as a result, it is the only terminal expression
    /// that does not return an `Option`.
    #[inline]
    fn get_par(&mut self) -> Result<Ratio<BigInt>, E> {
        // This is the last kind of terminal expression that is attempted.
        // If there is no more data, then we have a missing terminal expression.
        let Some(b) = self.utf8.get(self.i) else {
            return Err(MissingTerm(self.i));
        };
        // This is always the last terminal expression we call; so if there is a missing open parenthesis,
        // then the sentence is grammatically incorrect.
        if *b == b'(' {
            self.i += 1;
            self.consume_ws();
            let r = self.get_adds()?;
            self.consume_ws();
            let Some(b2) = self.utf8.get(self.i) else {
                return Err(InvalidPar(self.i))
            };
            let b3 = *b2;
            if b3 == b')' {
                self.i += 1;
                Ok(r)
            } else {
                Err(InvalidPar(self.i))
            }
        } else {
            Err(MissingTerm(self.i))
        }
    }
    /// Evaluates absolute value expressions as defined in the calc language.
    /// This function is based on addition expressions.
    #[inline]
    fn get_abs(&mut self) -> Result<Option<Ratio<BigInt>>, E> {
        let Some(b) = self.utf8.get(self.i) else {
            return Ok(None)
        };
        if *b == b'|' {
            self.i += 1;
            self.consume_ws();
            let r = self.get_adds()?;
            self.consume_ws();
            let Some(b2) = self.utf8.get(self.i) else {
                return Err(InvalidAbs(self.i))
            };
            let b3 = *b2;
            if b3 == b'|' {
                self.i += 1;
                Ok(Some(if r.numer().sign() == Sign::Minus {
                    -r
                } else {
                    r
                }))
            } else {
                Err(InvalidAbs(self.i))
            }
        } else {
            Ok(None)
        }
    }
    /// Obtains the index within `self.prev` that a recall
    /// expression is to return. This is a separate function
    /// from [`get_prev`] due to [`get_recall`] also using this
    /// logic.
    #[inline]
    #[allow(clippy::as_conversions)]
    fn get_prev_idx(&mut self) -> Option<usize> {
        let Some(b) = self.utf8.get(self.i) else {
          return None  
        };
        (*b == b'@').then(|| {
            self.i += 1;
            self.utf8.get(self.i).map_or(0, |b2| {
                if (b'1'..b'9').contains(b2) {
                    self.i += 1;
                    (*b2 - b'1') as usize
                } else {
                    0
                }
            })
        })
    }
    /// Evaluates recall expressions as defined in the calc language.
    #[inline]
    #[allow(clippy::as_conversions, clippy::cast_possible_truncation)]
    fn get_prev(&mut self) -> Result<Option<&Ratio<BigInt>>, E> {
        self.get_prev_idx().map_or_else(|| Ok(None), |i| {
            self.prev
                .get(i)
                .map_or_else(|| Err(NotEnoughPrevResults(self.prev.len() as u8)), |r| Ok(Some(r)))
        })
    }
    /// Evaluates recall statements as defined in the calc language.
    /// This function has to be separate from [`get_prev`] since it returns
    /// a shared reference with 'cache lifetime which requires the function to move self
    /// since it has an exclusive reference to the cache.
    #[inline]
    #[allow(clippy::as_conversions, clippy::cast_possible_truncation)]
    fn get_recall(mut self) -> Result<&'cache Ratio<BigInt>, E> {
        self.get_prev_idx().map_or_else(|| Err(InvalidRecall), move |i| {
            self.consume_ws();
            self.prev.get(i).map_or_else(|| Err(NotEnoughPrevResults(self.prev.len() as u8)), |val| {
                if self.i == self.utf8.len() {
                    Ok(val)
                } else {
                    Err(InvalidRecall)
                }
            })
        })
    }
    /// Evaluates number literal expressions as defined in the calc language.
    #[inline]
    #[allow(
        clippy::as_conversions,
        clippy::cast_lossless,
        clippy::indexing_slicing
    )]
    fn get_rational(&mut self) -> Result<Option<Ratio<BigInt>>, E> {
        #[inline]
        // ControlFlow makes more sense to use in try_fold; however due to a lack
        // of a map_or_else function, it is easier to simply return a Result with
        // Err taking the role of ControlFlow::Break.
        /// Used to parse a sequence of digits into an unsigned integer.
        fn to_biguint(v: &[u8]) -> (BigUint, usize) {
            v.into_iter()
                .try_fold((BigUint::new(Vec::new()), 0), |mut prev, d| {
                    if d.is_ascii_digit() {
                        prev.1 += 1;
                        prev.0 = prev.0 * 10u8 + (*d - b'0');
                        Ok(prev)
                    } else {
                        Err(prev)
                    }
                })
                .map_or_else(convert::identity, convert::identity)
        }
        let (int, len) = to_biguint(&self.utf8[self.i..]);
        if len == 0 {
            return Ok(None);
        }
        self.i += len;
        if let Some(b) = self.utf8.get(self.i) {
            if *b == b'.' {
                self.i += 1;
                let (numer, len2) = to_biguint(&self.utf8[self.i..]);
                if len2 == 0 {
                    Err(InvalidDec(self.i))
                } else {
                    self.i += len2;
                    Ok(Some(
                        Ratio::from_integer(BigInt::from_biguint(Sign::Plus, int))
                            + Ratio::new(
                                BigInt::from_biguint(Sign::Plus, numer),
                                BigInt::from_biguint(Sign::Plus, BigUint::new(vec![10]).pow(len2)),
                            ),
                    ))
                }
            } else {
                Ok(Some(Ratio::from_integer(BigInt::from_biguint(
                    Sign::Plus,
                    int,
                ))))
            }
        } else {
            Ok(Some(Ratio::from_integer(BigInt::from_biguint(
                Sign::Plus,
                int,
            ))))
        }
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn prev_string() {
        assert!(PrevVal { val: &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![12]))), round: None }.to_string() == "> 12\n");
        assert!(PrevVal { val: &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![12]))), round: Some(0) }.to_string() == "> 12\n");
        assert!(PrevVal { val: &Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![12]))), round: Some(1) }.to_string() == "> -12.0\n");
        assert!(PrevVal { val: &Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))), round: None }.to_string() == "> 2/3\n");
        assert!(PrevVal { val: &Ratio::new(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![2])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))), round: Some(0)}.to_string() == "> -1\n");
        assert!(PrevVal { val: &Ratio::new(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![2])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))), round: Some(1)}.to_string() == "> -0.7\n");
        assert!(PrevVal { val: &Ratio::new(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![4])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![6]))), round: Some(2)}.to_string() == "> -0.67\n");
    }
    #[test]
    fn number_literal() {
        // Normal 0 is fine.
        assert!(Evaluator::new(b"0", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(Vec::new()))));
        // Leading 0s and trailing 0s are fine.
        assert!(Evaluator::new(b"0000.00000", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(Vec::new()))));
        // Parsing stops at first non-(digit/period).
        assert!(Evaluator::new(b"1 0", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        let int = b"3397450981271938475135134759823759835414";
        let frac = b"913759810573549872354897210539127530981570";
        let left = Ratio::from_integer(BigInt::parse_bytes(int, 10).unwrap());
        let right = Ratio::new(BigInt::parse_bytes(frac, 10).unwrap(), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![10]).pow(frac.len() + 1)));
        let mut vec = Vec::new();
        vec.extend_from_slice(int);
        vec.push(b'.');
        vec.push(b'0');
        vec.extend_from_slice(frac);
        // Test a number whose integer and fraction portions are larger than u128::MAX.
        assert!(Evaluator::new(vec.as_slice(), &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().unwrap() == left + right);
        // Leading 0s and trailing 0s for a non-zero value are fine.
        assert!(Evaluator::new(b"000000014.0000000000000", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![14]))));
        // A sequence of digits followed immediately by a decimal point but no digits after is invalid.
        assert!(match Evaluator::new(b"1.", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap_err() {
            E::InvalidDec(i) => i == 2,
            _ => false,
        });
        // A sequence of digits followed immediately by a decimal point and space but no digits after is invalid.
        // This just shows that spaces are not ignored in number literals.
        assert!(match Evaluator::new(b"1. 2", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap_err() {
            E::InvalidDec(i) => i == 2,
            _ => false,
        });
        // A non-space starting the input is valid but produces no value.
        // This also shows that an invalid byte sequence does not produce an error here.
        assert!(Evaluator::new(b"a1", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().is_none());
        // A space starting the input is valid but produces no value.
        assert!(Evaluator::new(b" 1", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().is_none());
        // Negative literals don't exist, so this should succeed but produce nothing.
        assert!(Evaluator::new(b"-1", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().is_none());
        // '/' is division and not part of a number literal so only the "numerator" is parsed.
        assert!(Evaluator::new(b"1/2", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // A sequence of digits followed by invalid bytes is valid and produces a number equal to the digits before the invalid bytes.
        assert!(Evaluator::new(b"130alj", &mut Cache::new(), &mut Vec::new()).get_rational().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![130]))));
    }
    #[test]
    fn recall_expression() {
        // If the input does not start with '@', then it's valid but produces nothing.
        assert!(Evaluator::new(b"1", &mut Cache::new(), &mut Vec::new()).get_prev().unwrap().is_none());
        assert!(Evaluator::new(b"a", &mut Cache::new(), &mut Vec::new()).get_prev().unwrap().is_none());
        assert!(Evaluator::new(b" @", &mut Cache::new(), &mut Vec::new()).get_prev().unwrap().is_none());
        // Invalid recall expression since there are no previous results.
        assert!(match Evaluator::new(b"@", &mut Cache::new(), &mut Vec::new()).get_prev().unwrap_err() {
            E::NotEnoughPrevResults(count) => count == 0,
            _ => false,
        });
        // Invalid recall expression since there are no previous results.
        assert!(match Evaluator::new(b"@4", &mut Cache::new(), &mut Vec::new()).get_prev().unwrap_err() {
            E::NotEnoughPrevResults(count) => count == 0,
            _ => false,
        });
        // Invalid recall expression since there are no previous results.
        // The input violates our grammar, but this error happens before that.
        assert!(match Evaluator::new(b"@0", &mut Cache::new(), &mut Vec::new()).get_prev().unwrap_err() {
            E::NotEnoughPrevResults(count) => count == 0,
            _ => false,
        });
        // Successfully extract previous expression.
        let mut cache = Cache::new();
        Evaluator::new(b"1\n", &mut cache, &mut Vec::new()).evaluate().unwrap();
        assert!(Evaluator::new(b"@", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // Invalid characters are ignored at this stage.
        assert!(Evaluator::new(b"@&", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // 0 is not a valid previous value only 1-8 are.
        assert!(Evaluator::new(b"@0", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // 9 is not a valid previous value only 1-8 are.
        assert!(Evaluator::new(b"@9", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // Spaces are not cleaned; otherwise this would error since we only have 1 previous value.
        assert!(Evaluator::new(b"@ 2", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // One digits are looked at so this is not @<ten>.
        assert!(Evaluator::new(b"@10", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // Invalid recall expression since there are no previous results.
        assert!(match Evaluator::new(b"@2", &mut cache, &mut Vec::new()).get_prev().unwrap_err() {
            E::NotEnoughPrevResults(count) => count == 1,
            _ => false,
        });
        Evaluator::new(b"2\n", &mut cache, &mut Vec::new()).evaluate().unwrap();
        // Previous value is correct.
        assert!(Evaluator::new(b"@", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2]))));
        // Second previous value is correct.
        assert!(Evaluator::new(b"@2", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // Invalid recall expression since there are no previous results.
        assert!(match Evaluator::new(b"@3", &mut cache, &mut Vec::new()).get_prev().unwrap_err() {
            E::NotEnoughPrevResults(count) => count == 2,
            _ => false,
        });
        let mut v = vec![0, b'\n'];
        for i in b'3'..=b'8' {
            v[0] = i;
            Evaluator::new(v.as_slice(), &mut cache, &mut Vec::new()).evaluate().unwrap();
        }
        v[0] = b'@';
        for i in b'1'..=b'8' {
            v[1] = i;
            // Cache is filled up correctly storing all previous values.
            assert!(Evaluator::new(v.as_slice(), &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![(b'9' - i) as u32]))));
        }
        // Only parses the first @ since the second @ is not a digit between 1 and 8.
        assert!(Evaluator::new(b"@@", &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![8]))));
        Evaluator::new(b"9\n", &mut cache, &mut Vec::new()).evaluate().unwrap();
        // Oldest value is overwritten; all others remain.
        for i in b'1'..=b'8' {
            v[1] = i;
            assert!(Evaluator::new(v.as_slice(), &mut cache, &mut Vec::new()).get_prev().unwrap().unwrap() == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![((b'9' + 1) - i) as u32]))));
        }
    }
    #[test]
    fn abs() {
        // Missing closing '|'
        assert!(match Evaluator::new(b"|1", &mut Cache::new(), &mut Vec::new()).get_abs().unwrap_err() {
            E::InvalidAbs(i) => i == 2,
            _ => false,
        });
        assert!(match Evaluator::new(b"||1 + 2|", &mut Cache::new(), &mut Vec::new()).get_abs().unwrap_err() {
            E::InvalidAbs(i) => i == 8,
            _ => false,
        });
        assert!(Evaluator::new(b"|  0  |", &mut Cache::new(), &mut Vec::new()).get_abs().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(Vec::new()))));
        assert!(Evaluator::new(b"| -  5 |", &mut Cache::new(), &mut Vec::new()).get_abs().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![5]))));
        assert!(Evaluator::new(b"| | 2 -  5| * 9 |", &mut Cache::new(), &mut Vec::new()).get_abs().unwrap().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![27]))));
        // If the input does not start with '|', then it's valid but produces nothing.
        assert!(Evaluator::new(b" |9|", &mut Cache::new(), &mut Vec::new()).get_abs().unwrap().is_none());
    }
    #[test]
    fn par() {
        // Missing closing ')'
        assert!(match Evaluator::new(b"(1", &mut Cache::new(), &mut Vec::new()).get_par().unwrap_err() {
            E::InvalidPar(i) => i == 2,
            _ => false,
        });
        assert!(match Evaluator::new(b"((1 + 2)", &mut Cache::new(), &mut Vec::new()).get_par().unwrap_err() {
            E::InvalidPar(i) => i == 8,
            _ => false,
        });
        assert!(Evaluator::new(b"(  0  )", &mut Cache::new(), &mut Vec::new()).get_par().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(Vec::new()))));
        assert!(Evaluator::new(b"( -  5 )", &mut Cache::new(), &mut Vec::new()).get_par().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![5]))));
        assert!(Evaluator::new(b"( ( 2 -  5) * 9 )", &mut Cache::new(), &mut Vec::new()).get_par().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![27]))));
        // If the input does not start with '(', then it's invalid since get_par must only be called as the last terminal expression which means whitespace must be consumed already.
        assert!(match Evaluator::new(b" (2)", &mut Cache::new(), &mut Vec::new()).get_par().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
    }
    #[test]
    fn term() {
        assert!(Evaluator::new(b"0000.00000", &mut Cache::new(), &mut Vec::new()).get_term().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(Vec::new()))));
        assert!(Evaluator::new(b"|4|", &mut Cache::new(), &mut Vec::new()).get_term().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4]))));
        assert!(Evaluator::new(b"(4)", &mut Cache::new(), &mut Vec::new()).get_term().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4]))));
        // Terminal expressions do no clean up before or after.
        assert!(match Evaluator::new(b" 2", &mut Cache::new(), &mut Vec::new()).get_term().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        let mut cache = Cache::new();
        Evaluator::new(b"1\n", &mut cache, &mut Vec::new()).evaluate().unwrap();
        assert!(Evaluator::new(b"@", &mut cache, &mut Vec::new()).get_term().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
    }
    #[test]
    fn factorial() {
        // Negative integer is not allowed.
        assert!(match Evaluator::new(b"(-1)!", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap_err() {
            E::NotNonNegIntFact(i) => i == 5,
            _ => false,
        });
        // Non-integer is not allowed.
        assert!(match Evaluator::new(b"2.5!", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap_err() {
            E::NotNonNegIntFact(i) => i == 4,
            _ => false,
        });
        // factorials always become terminal expressions eventually.
        assert!(Evaluator::new(b"7", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![7]))));
        assert!(Evaluator::new(b"(7)", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![7]))));
        assert!(Evaluator::new(b"|7|", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![7]))));
        let mut cache = Cache::new();
        Evaluator::new(b"3\n", &mut cache, &mut Vec::new()).evaluate().unwrap();
        assert!(Evaluator::new(b"@!", &mut cache, &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![6]))));
        assert!(Evaluator::new(b"@", &mut cache, &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))));
        // 0! = 1.
        assert!(Evaluator::new(b"0.0!", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // 1! = 1.
        assert!(Evaluator::new(b"1!", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // 4! = 24, and spaces are not consumed.
        assert!(Evaluator::new(b"4! ", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![24]))));
        // Factorials can be chained.
        assert!(Evaluator::new(b"3!! ", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![720]))));
        // only factorial is consumed.
        assert!(Evaluator::new(b"2!+3", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2]))));
        // Error since leading/trailing whitespace is not consumed by factorial or higher precedence expressions.
        assert!(match Evaluator::new(b" 2!", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        // Error since leading/trailing whitespace is not consumed by factorial or higher precedence expressions.
        assert!(match Evaluator::new(b"-2!", &mut Cache::new(), &mut Vec::new()).get_fact().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
    }
    #[test]
    fn exp() {
        // 1 can be raised to anything and return 1.
        // Also white space is ignored between operator.
        assert!(Evaluator::new(b"1  ^  0", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"1^0.5", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"1^(-1/2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"1.0^(-2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        // 0 can be raised to any non-negative value and will always return 0 unless raised to 0 which will return 1.
        assert!(Evaluator::new(b"0^0", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"0^1", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(vec![0]))));
        assert!(Evaluator::new(b"0^0.5", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(vec![0]))));
        // Anything else can only be raised to integers.
        assert!(Evaluator::new(b"4^0", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"4^1", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4]))));
        assert!(Evaluator::new(b"4^(-2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![16]))));
        assert!(Evaluator::new(b"(-4)^0", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"(-4)^1", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![4]))));
        assert!(Evaluator::new(b"(-4)^2", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![16]))));
        assert!(Evaluator::new(b"(-4)^(-2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![16]))));
        assert!(Evaluator::new(b"(-4)^(-3)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![1])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![64]))));
        assert!(Evaluator::new(b"(2/3)^0", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"(2/3)^(2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![9]))));
        assert!(Evaluator::new(b"(2/3)^(-3)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![27])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![8]))));
        assert!(Evaluator::new(b"(-2/3)^0", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"(-2/3)^(2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![9]))));
        assert!(Evaluator::new(b"(-2/3)^(3)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![8])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![27]))));
        assert!(Evaluator::new(b"(-2/3)^(-2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![9])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4]))));
        assert!(Evaluator::new(b"(-2/3)^(-3)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![27])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![8]))));
        // Error since 0 cannot be raised to a negative power.
        assert!(match Evaluator::new(b"0^(-1)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap_err() {
            E::ExpDivByZero(i) => i == 6,
            _ => false,
        });
        // Error anything other than 0 or 1 cannot be raised to a non-integer power.
        assert!(match Evaluator::new(b"2^(1/2)", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap_err() {
            E::ExpIsNotInt(i) => i == 7,
            _ => false,
        });
        // exps always become factorials eventually.
        assert!(Evaluator::new(b"3!", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![6]))));
        // exponentiation has lower precedence than factorials.
        assert!(Evaluator::new(b"2^3!", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![64]))));
        assert!(Evaluator::new(b"3!^2", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![36]))));
        // Error since leading/trailing whitespace is not consumed by exponentiation or higher precedence expressions.
        assert!(match Evaluator::new(b" 2^2", &mut Cache::new(), &mut Vec::new()).get_exps().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
    }
    #[test]
    fn neg() {
        assert!(Evaluator::new(b"-1", &mut Cache::new(), &mut Vec::new()).get_neg().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"-   -  1", &mut Cache::new(), &mut Vec::new()).get_neg().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"-0", &mut Cache::new(), &mut Vec::new()).get_neg().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::NoSign, BigUint::new(Vec::new()))));
        // negation has lower precedence than exponentiation.
        assert!(Evaluator::new(b"-2^2", &mut Cache::new(), &mut Vec::new()).get_neg().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![4]))));
        // negation always becomes exponentiation eventually.
        assert!(Evaluator::new(b"2.0^2.0", &mut Cache::new(), &mut Vec::new()).get_neg().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4]))));
        // Error since leading/trailing whitespace is not consumed by exponentiation or higher precedence expressions.
        assert!(match Evaluator::new(b" -2", &mut Cache::new(), &mut Vec::new()).get_neg().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
    }
    #[test]
    fn mult() {
        assert!(Evaluator::new(b"2  *   3", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![6]))));
        assert!(Evaluator::new(b"-2  *   3", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![6]))));
        assert!(Evaluator::new(b"2  *   -3.0", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![6]))));
        assert!(Evaluator::new(b"-2.5*-3.5", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![35])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4]))));
        assert!(Evaluator::new(b"4.0 /  6", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))));
        assert!(Evaluator::new(b"6/3", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2]))));
        assert!(Evaluator::new(b"-6/3", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![2]))));
        assert!(Evaluator::new(b"6/-3", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![2]))));
        assert!(Evaluator::new(b"-  6 / -  3", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2]))));
        // Number literals are not strictly equivalent to "ratios" as "ratios" don't exist (i.e., 2/3 is not the ratio of 2 to 3 but is the rational number two divided by the rational number 3).
        assert!(Evaluator::new(b"1/1.5", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() != Evaluator::new(b"1/3/2", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap());
        assert!(Evaluator::new(b"1/1.5", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Evaluator::new(b"1/(3/2)", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap());
        // multiplication always becomes negation eventually.
        assert!(Evaluator::new(b"-2.0", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![2]))));
        // Error since leading/trailing whitespace is not consumed by multiplication or higher precedence expressions.
        assert!(match Evaluator::new(b" 2*2", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b" 2/2", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        // Cannot divide by 0.
        assert!(match Evaluator::new(b"2/0", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap_err() {
            E::DivByZero(i) => i == 3,
            _ => false,
        });
        // multiplication has lower precedence than exponentiation.
        assert!(Evaluator::new(b"2*2^2", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![8]))));
        assert!(Evaluator::new(b"8/2^2", &mut Cache::new(), &mut Vec::new()).get_mults().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2]))));
    }
    #[test]
    fn add() {
        assert!(Evaluator::new(b"2  +   3", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![5]))));
        assert!(Evaluator::new(b"-2  +   3", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"2  +   -3.0", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![1]))));
        assert!(Evaluator::new(b"-2.5+-3.5", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![6]))));
        assert!(Evaluator::new(b"4.0 -  6", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![2]))));
        assert!(Evaluator::new(b"6-3", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))));
        assert!(Evaluator::new(b"-6-3", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![9]))));
        assert!(Evaluator::new(b"6--3", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![9]))));
        assert!(Evaluator::new(b"-  6 - -  3", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![3]))));
        // addition always becomes multiplication eventually.
        assert!(Evaluator::new(b"2 * 8", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![16]))));
        assert!(Evaluator::new(b"8 / 2", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![4]))));
        // Error since leading/trailing whitespace is not consumed by addition or higher precedence expressions.
        assert!(match Evaluator::new(b" 2+2", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b" 2-2", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        // addition has lower precedence than multiplication.
        assert!(Evaluator::new(b"2+2*2", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![6]))));
        assert!(Evaluator::new(b"2+2/2", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))));
        assert!(Evaluator::new(b"2-2*2", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Minus, BigUint::new(vec![2]))));
        assert!(Evaluator::new(b"2-2/2", &mut Cache::new(), &mut Vec::new()).get_adds().unwrap() == Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))));
    }
    #[test]
    fn empty() {
        assert!(match Evaluator::new(b"  \n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap() {
            O::Empty => true,
            _ => false,
        });
        assert!(match Evaluator::new(b"\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap() {
            O::Empty => true,
            _ => false,
        });
        assert!(match Evaluator::new(b"\r\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"\t\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"\n\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"\n ", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingLF => true,
            _ => false,
        });
    }
    #[test]
    fn exit() {
        assert!(match Evaluator::new(b"  q    \n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap() {
            O::Exit=> true,
            _ => false,
        });
        assert!(match Evaluator::new(b"q\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap() {
            O::Exit=> true,
            _ => false,
        });
        assert!(match Evaluator::new(b"\rq\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"\tq\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"q\n\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::InvalidQuit => true,
            _ => false,
        });
        assert!(match Evaluator::new(b"\nq\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"q", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingLF => true,
            _ => false,
        });
    }
    #[test]
    fn recall_statement() {
        let mut cache = Cache::new();
        Evaluator::new(b"1\n", &mut cache, &mut Vec::new()).evaluate().unwrap();
        assert!(match Evaluator::new(b"  =   @    \n", &mut cache, &mut Vec::new()).evaluate().unwrap() {
            O::Prev(v)=> v.val == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))) && v.round.is_none(),
            _ => false,
        });
        assert!(match Evaluator::new(b"  = 2@    \n", &mut cache, &mut Vec::new()).evaluate().unwrap() {
            O::Prev(v)=> v.val == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))) && v.round.unwrap() == 2,
            _ => false,
        });
        assert!(match Evaluator::new(b"=9@1\n", &mut cache, &mut Vec::new()).evaluate().unwrap() {
            O::Prev(v)=> v.val == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))) && v.round.unwrap() == 9,
            _ => false,
        });
        assert!(match Evaluator::new(b"=0@1\n", &mut cache, &mut Vec::new()).evaluate().unwrap() {
            O::Prev(v)=> v.val == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]))) && v.round.unwrap() == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"=@2\n", &mut Cache::new(), &mut Vec::new()).evaluate().unwrap_err() {
            E::NotEnoughPrevResults(count)=> count == 0,
            _ => false,
        });
        assert!(match Evaluator::new(b"=@ 1\n", &mut cache, &mut Vec::new()).evaluate().unwrap_err() {
            E::InvalidRecall => true,
            _ => false,
        });
        assert!(match Evaluator::new(b"=0 @1\n", &mut cache, &mut Vec::new()).evaluate().unwrap_err() {
            E::InvalidRecall => true,
            _ => false,
        });
        assert!(match Evaluator::new(b"=@", &mut cache, &mut Vec::new()).evaluate().unwrap_err() {
            E::MissingLF=> true,
            _ => false,
        });
    }
    #[test]
    fn eval() {
        use core::str::FromStr;
        let mut cache = Cache::new();
        let mut exp = Vec::new();
        assert!(match Evaluator::new(b"1+2\n", &mut cache, &mut exp).evaluate().unwrap() {
            O::Val(i) => i == &Ratio::from_integer(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![3]))),
            _ => false,
        });
        assert!(match Evaluator::new(b"-1/2+2*@\n", &mut cache, &mut exp).evaluate().unwrap() {
            O::Val(i) => i == &Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![11])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2]))),
            _ => false,
        });
        assert!(match Evaluator::new(b"@^@2!\n", &mut cache, &mut exp).evaluate().unwrap() {
            O::Val(i) => i == &Ratio::new(BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1771561])), BigInt::from_biguint(Sign::Plus, BigUint::new(vec![64]))),
            _ => false,
        });
        // Verified with Wolfram Alpha.
        assert!(match Evaluator::new(b"  1 + (2 * |(7.98 - 12/7)|) / 4!^@3!^|1-3|  \n", &mut cache, &mut exp).evaluate().unwrap() {
            O::Val(i) => i == &Ratio::from_str("2841328814244153299237884950647090899374680152474331/2841328814244153299237884950647090899374680152473600").unwrap(),
            _ => false,
        });
        // Invalid UTF-8 does not cause a panic!.
        assert!(match Evaluator::new(&[255, 255, 255, b'\n'], &mut cache, &mut exp).evaluate().unwrap_err() {
            E::MissingTerm(i) => i == 0,
            _ => false,
        });
        assert!(match Evaluator::new(&[b'2', 255, b'\n'], &mut cache, &mut exp).evaluate().unwrap_err() {
            E::TrailingSyms(i) => i == 1,
            _ => false,
        });
        // Exactly one line feed is required.
        assert!(match Evaluator::new(&[b'2', b'\n', b'\n'], &mut cache, &mut exp).evaluate().unwrap_err() {
            E::TrailingSyms(i) => i == 1,
            _ => false,
        });
        assert!(match Evaluator::new(&[b'\n'], &mut cache, &mut exp).evaluate().unwrap() {
            O::Empty => true,
            _ => false,
        });
        // Empty input does not cause a panic!.
        assert!(match Evaluator::new(&[], &mut cache, &mut exp).evaluate().unwrap_err() {
            E::MissingLF => true,
            _ => false,
        });
    }
}