calc_rational 3.1.0

//! [![git]](https://git.philomathiclife.com/calc_rational/log.html) [![crates-io]](https://crates.io/crates/calc_rational) [![docs-rs]](crate)
//!
//! [git]: https://git.philomathiclife.com/git_badge.svg
//! [crates-io]: https://img.shields.io/badge/crates.io-fc8d62?style=for-the-badge&labelColor=555555&logo=rust
//! [docs-rs]: https://img.shields.io/badge/docs.rs-66c2a5?style=for-the-badge&labelColor=555555&logo=docs.rs
//!
//! `calc_lib` is a library for performing basic rational number arithmetic using standard operator precedence
//! and associativity. Internally, it is based on
//! [`Ratio<T>`] and [`BigInt`].
//!   
//! ## Expressions  
//!   
//! The following are the list of expressions in descending order of precedence:  
//!   1. number literals, `@`, `()`, `||`, `round()`, `rand()`  
//!   2. `!`  
//!   3. `^`  
//!   4. `-` (unary negation operator)  
//!   5. `*`, `/`, `mod`  
//!   6. `+`, `-`  
//!   
//! All binary operators are left-associative sans `^` which is right-associative.  
//!   
//! Any expression is allowed to be enclosed in `()`. Note that parentheses are purely for grouping expressions;
//! in particular, you cannot use them to represent multiplication (e.g., `4(2)` is grammatically incorrect and
//! will result in an error message).  
//!   
//! Any expression is allowed to be enclosed in `||`. This unary operator represents absolute value.  
//!   
//! `!` is the factorial operator. Due to its high precedence, something like *-i!^j!* for *i, j ∈ ℕ* is
//! the same thing as *-((i!)^(j!))*. If the expression preceding it does not evaluate to a non-negative integer,
//! then an error will be displayed. Spaces  and tabs are *not* ignored; so `1 !` is grammatically incorrect and
//! will result in an error message.  
//!   
//! `^` is the exponentiation operator. The expression left of the operator can evaluate to any rational number;
//! however the expression right of the operator must evaluate to an integer or ±1/2 unless the expression on
//! the left evaluates to `0` or `1`. In the event of the former, the expression right of the operator must evaluate
//! to a non-negative rational number. In the event of the latter, the expression right of the operator can evaluate to
//! any rational number. Note that `0^0` is defined to be 1. When the operand right of `^` evaluates to ±1/2, then
//! the left operand must be the square of a rational number.  
//!   
//! The unary operator `-` represents negation.  
//!   
//! The operators `*` and `/` represent multiplication and division respectively. Expressions right of `/`
//! must evaluate to any non-zero rational number; otherwise an error will be displayed.  
//!   
//! The binary operator `mod` represents modulo such that *n mod m = r = n - m\*q* for *n,q ∈ ℤ, m ∈ ℤ\\{0}, and r ∈ ℕ*
//! where *r* is the minimum non-negative solution.  
//!   
//! The binary operators `+` and `-` represent addition and subtraction respectively.  
//!   
//! With the aforementioned exception of `!`, all spaces and tabs before and after operators are ignored.  
//!   
//! ## Round expression  
//!   
//! `round(expression, digit)` rounds `expression` to `digit`-number of fractional digits. An error will
//! be displayed if called incorrectly.  
//!   
//! ## Rand expression  
//!   
//! `rand(expression, expression)` generates a random 64-bit integer inclusively between the passed expressions.
//! An error will be displayed if called incorrectly. `rand()` generates a random 64-bit integer.  
//!   
//! ## Numbers  
//!   
//! A number literal is a non-empty sequence of digits or a non-empty sequence of digits immediately followed by `.`
//! which is immediately followed by a non-empty sequence of digits (e.g., `134.901`). This means that number
//! literals represent precisely all rational numbers that are equivalent to a ratio of a non-negative integer
//! to a positive integer whose sole prime factors are 2 or 5. To represent all other rational numbers, the unary
//! operator `-` and binary operator `/` must be used.  
//!   
//! ## Empty expression  
//!   
//! The empty expression (i.e., expression that at most only consists of spaces and tabs) will return
//! the result from the previous non-(empty/store) expression in *decimal* form using the minimum number of digits.
//! In the event an infinite number of digits is required, it will be rounded to 9 fractional digits using normal rounding
//! rules first.  
//!   
//! ## Store expression  
//!   
//! To store the result of the previous non-(empty/store) expression, one simply passes `s`. In addition to storing the
//! result which will subsequently be available via `@`, it displays the result. At most 8 results can be stored at once;
//! at which point, results that are stored overwrite the oldest result.  
//!   
//! ## Recall expression  
//!   
//! `@` is used to recall previously stored results. It can be followed by any *digit* from `1` to `8`.
//! If such a digit does not immediately follow it, then it will be interpreted as if there were a `1`.
//! `@i` returns the *i*-th most-previous stored result where *i ∈ {1, 2, 3, 4, 5, 6, 7, 8}*.
//! Note that spaces and tabs are *not* ignored so `@ 2` is grammatically incorrect and will result in an error message.
//! As emphasized, it does not work on expressions; so both `@@` and `@(1)` are grammatically incorrect.  
//!   
//! ## Character encoding  
//!   
//! All inputs must only contain the ASCII encoding of the following Unicode scalar values: `0`-`9`, `.`, `+`, `-`,
//! `*`, `/`, `^`, `!`, `mod`, `|`, `(`, `)`, `round`, `rand`, `,`, `@`, `s`, &lt;space&gt;, &lt;tab&gt;,
//! &lt;line feed&gt;, &lt;carriage return&gt;, and `q`. Any other byte sequences are grammatically incorrect and will
//! lead to an error message.  
//!   
//! ## Errors  
//!   
//! Errors due to a language violation (e.g., dividing by `0`) manifest into an error message. `panic!`s
//! and [`io::Error`](https://doc.rust-lang.org/std/io/struct.Error.html)s caused by writing to the global
//! standard output stream lead to program abortion.  
//!   
//! ## Exiting  
//!   
//! `q` with any number of spaces and tabs before and after will cause the program to terminate.  
//!   
//! ### Formal language specification  
//!   
//! For a more precise specification of the “calc language”, one can read the
//! [calc language specification](https://git.philomathiclife.com/calc_rational/lang.pdf).
#![expect(
    clippy::doc_paragraphs_missing_punctuation,
    reason = "false positive for crate documentation having image links"
)]
#![expect(
    clippy::arithmetic_side_effects,
    reason = "calculator can't realistically avoid this"
)]
#![no_std]
#![cfg_attr(docsrs, feature(doc_cfg))]
extern crate alloc;
/// Unit tests.
#[cfg(test)]
mod tests;
use LangErr::{
    DivByZero, ExpDivByZero, ExpIsNotIntOrOneHalf, InvalidAbs, InvalidDec, InvalidPar, InvalidQuit,
    InvalidRound, InvalidStore, MissingTerm, ModIsNotInt, ModZero, NotEnoughPrevResults,
    NotNonNegIntFact, SqrtDoesNotExist, TrailingSyms,
};
use O::{Empty, Eval, Exit, Store};
use alloc::{
    string::{String, ToString as _},
    vec,
    vec::Vec,
};
use cache::Cache;
#[cfg(not(feature = "rand"))]
use core::marker::PhantomData;
use core::{
    convert,
    fmt::{self, Display, Formatter},
    ops::Index as _,
};
pub use num_bigint;
use num_bigint::{BigInt, BigUint, Sign};
use num_integer::Integer as _;
pub use num_rational;
use num_rational::Ratio;
#[cfg(feature = "rand")]
use num_traits::ToPrimitive as _;
use num_traits::{Inv as _, Pow as _};
#[cfg(target_os = "openbsd")]
use priv_sep as _;
#[cfg(feature = "rand")]
pub use rand;
#[cfg(feature = "rand")]
use rand::{Rng as _, rngs::ThreadRng};
/// 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;
/// Generalizes [`Iterator`] by using
/// generic associated types.
pub mod lending_iterator;
/// Error due to a language violation.
#[non_exhaustive]
#[cfg_attr(test, derive(Eq, PartialEq))]
#[derive(Debug)]
pub enum LangErr {
    /// The input began with a `q` but had non-whitespace
    /// that followed it.
    InvalidQuit,
    /// The input began with an `s` but had non-whitespace
    /// that followed it.
    InvalidStore,
    /// 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 that is not (+/-) 1/2.
    ExpIsNotIntOrOneHalf(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 number modulo 0.
    ModZero(usize),
    /// A sub-expression in the input would have led
    /// to the mod of two expressions with at least one
    /// not being an integer.
    ModIsNotInt(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 most-recent stored result,
    /// but there are fewer than *i* stored where
    /// *i ∈ {1, 2, 3, 4, 5, 6, 7, 8}*.
    NotEnoughPrevResults(usize),
    /// The input did not contain a closing `|`.
    InvalidAbs(usize),
    /// The input did not contain a closing `)`.
    InvalidPar(usize),
    /// The input contained an invalid round expression.
    InvalidRound(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, parenthetical
    /// expression, or round expression.
    MissingTerm(usize),
    /// The expression that was passed to the square root does not have a solution
    /// in the field of rational numbers.
    SqrtDoesNotExist(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),
    /// The input contained an invalid random expression.
    #[cfg(feature = "rand")]
    InvalidRand(usize),
    /// Error when the second argument is less than first in the rand function.
    #[cfg(feature = "rand")]
    RandInvalidArgs(usize),
    /// Error when there are no 64-bit integers in the interval passed to the random function.
    #[cfg(feature = "rand")]
    RandNoInts(usize),
}
impl Display for LangErr {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match *self {
            InvalidStore => f.write_str("Invalid store expression. A store expression must be of the extended regex form: ^[ \\t]*s[ \\t]*$."),
            InvalidQuit => f.write_str("Invalid quit expression. A quit expression must be of the extended regex form: ^[ \\t]*q[ \\t]*$."),
            DivByZero(u) => write!(f, "Division by zero ending at position {u}."),
            ExpIsNotIntOrOneHalf(u) => write!(f, "Non-integer exponent that is not (+/-) 1/2 with a base that was not 0 or 1 ending at position {u}."),
            ExpDivByZero(u) => write!(f, "Non-negative exponent with a base of 0 ending at position {u}."),
            ModZero(u) => write!(f, "A number modulo 0 ending at position {u}."),
            ModIsNotInt(u) => write!(f, "The modulo expression was applied to at least one non-integer ending at position {u}."),
            NotNonNegIntFact(u) => write!(f, "Factorial of a rational number that was not a non-negative integer ending at position {u}."),
            InvalidDec(u) => write!(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) => write!(f, "There are only {len} previous results."),
            InvalidAbs(u) => write!(f, "Invalid absolute value expression ending at position {u}. An absolute value expression is an addition expression enclosed in '||'."),
            InvalidPar(u) => write!(f, "Invalid parenthetical expression ending at position {u}. A parenthetical expression is an addition expression enclosed in '()'."),
            InvalidRound(u) => write!(f, "Invalid round expression ending at position {u}. A round expression is of the form 'round(<mod expression>, digit)'"),
            SqrtDoesNotExist(u) => write!(f, "The square root of the passed expression does not have a solution in the field of rational numbers ending at position {u}."),
            #[cfg(not(feature = "rand"))]
            MissingTerm(u) => write!(f, "Missing terminal expression at position {u}. A terminal expression is a decimal literal expression, recall expression, absolute value expression, parenthetical expression, or round expression."),
            #[cfg(feature = "rand")]
            MissingTerm(u) => write!(f, "Missing terminal expression at position {u}. A terminal expression is a decimal literal expression, recall expression, absolute value expression, parenthetical expression, round expression, or rand expression."),
            TrailingSyms(u) => write!(f, "Trailing symbols starting at position {u}."),
            #[cfg(feature = "rand")]
            Self::InvalidRand(u) => write!(f, "Invalid rand expression ending at position {u}. A rand expression is of the form 'rand()' or 'rand(<mod expression>, <mod expression>)'."),
            #[cfg(feature = "rand")]
            Self::RandInvalidArgs(u) => write!(f, "The second expression passed to the random function evaluated to rational number less than the first ending at position {u}."),
            #[cfg(feature = "rand")]
            Self::RandNoInts(u) => write!(f, "There are no 64-bit integers within the interval passed to the random function ending at position {u}."),
        }
    }
}
/// A successful evaluation of an input.
#[cfg_attr(test, derive(Eq, PartialEq))]
#[derive(Debug)]
pub enum O<'a> {
    /// The input only contained whitespace.
    /// This returns the previous `Eval`.
    /// It is `None` iff there have been no
    /// previous `Eval` results.
    Empty(&'a Option<Ratio<BigInt>>),
    /// The quit expression was issued to terminate the program.
    Exit,
    /// Result of a "normal" expression.
    Eval(&'a Ratio<BigInt>),
    /// The store expression stores and returns the previous `Eval`.
    /// It is `None` iff there have been no previous `Eval` results.
    Store(&'a Option<Ratio<BigInt>>),
}
impl Display for O<'_> {
    #[expect(
        unsafe_code,
        reason = "manually construct guaranteed UTF-8; thus avoid the needless check"
    )]
    #[expect(clippy::indexing_slicing, reason = "comment justifies correctness")]
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match *self {
            Empty(o) => {
                o.as_ref().map_or(Ok(()), |val| {
                    if val.is_integer() {
                        write!(f, "> {val}")
                    } else {
                        // If the prime factors of the denominator are only 2 and 5,
                        // then the number requires a finite number of digits and thus
                        // will be represented perfectly using the fewest number of digits.
                        // Any other situation will be rounded to 9 fractional digits.
                        // max{twos, fives} represents the minimum number of fractional
                        // digits necessary to represent val.
                        let mut twos = 0;
                        let mut fives = 0;
                        let zero = BigInt::from_biguint(Sign::NoSign, BigUint::new(Vec::new()));
                        let one = BigInt::from_biguint(Sign::Plus, BigUint::new(vec![1]));
                        let two = BigInt::from_biguint(Sign::Plus, BigUint::new(vec![2]));
                        let five = BigInt::from_biguint(Sign::Plus, BigUint::new(vec![5]));
                        let mut denom = val.denom().clone();
                        let mut div_rem;
                        while denom > one {
                            div_rem = denom.div_rem(&two);
                            if div_rem.1 == zero {
                                twos += 1;
                                denom = div_rem.0;
                            } else {
                                break;
                            }
                        }
                        while denom > one {
                            div_rem = denom.div_rem(&five);
                            if div_rem.1 == zero {
                                fives += 1;
                                denom = div_rem.0;
                            } else {
                                break;
                            }
                        }
                        // int < 0 iff val <= -1. frac < 0 iff val is a negative non-integer.
                        let (int, frac, digits) = if denom == one {
                            let (int, mut frac) = val.numer().div_rem(val.denom());
                            while twos > fives {
                                frac *= &five;
                                fives += 1;
                            }
                            while fives > twos {
                                frac *= &two;
                                twos += 1;
                            }
                            (int, frac, twos)
                        } else {
                            // Requires an infinite number of decimal digits to represent, so we display
                            // 9 digits after rounding.
                            let mult =
                                BigInt::from_biguint(Sign::Plus, BigUint::new(vec![10])).pow(9u8);
                            let (int, frac) = (val * &mult).round().numer().div_rem(&mult);
                            (int, frac, 9)
                        };
                        let int_str = int.to_string().into_bytes();
                        let (mut v, frac_str) = if val.numer().sign() == Sign::Minus {
                            // Guaranteed to be non-empty.
                            if int_str[0] == b'-' {
                                (
                                    Vec::with_capacity(int_str.len() + 1 + digits),
                                    (-frac).to_string().into_bytes(),
                                )
                            } else {
                                let mut tmp = Vec::with_capacity(int_str.len() + 2 + digits);
                                tmp.push(b'-');
                                (tmp, (-frac).to_string().into_bytes())
                            }
                        } else {
                            (
                                Vec::with_capacity(int_str.len() + 1 + digits),
                                frac.to_string().into_bytes(),
                            )
                        };
                        v.extend_from_slice(int_str.as_slice());
                        v.push(b'.');
                        // digits >= frac_str.len().
                        v.resize(v.len() + (digits - frac_str.len()), b'0');
                        v.extend_from_slice(frac_str.as_slice());
                        // 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".
                        write!(f, "> {}", unsafe { String::from_utf8_unchecked(v) })
                    }
                })
            }
            Eval(r) => write!(f, "> {r}"),
            Exit => Ok(()),
            Store(o) => o.as_ref().map_or(Ok(()), |val| write!(f, "> {val}")),
        }
    }
}
/// Size of [`Evaluator::cache`].
const CACHE_SIZE: usize = 8;
/// Evaluates the supplied input.
#[derive(Debug)]
pub struct Evaluator<'input, 'cache, 'prev, 'scratch, 'rand> {
    /// 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 stored results.
    cache: &'cache mut Cache<Ratio<BigInt>, CACHE_SIZE>,
    /// The last result.
    prev: &'prev mut Option<Ratio<BigInt>>,
    /// Buffer used to evaluate right-associative sub-expressions.
    scratch: &'scratch mut Vec<Ratio<BigInt>>,
    /// Random number generator.
    #[cfg(feature = "rand")]
    rng: &'rand mut ThreadRng,
    /// Need to use `'rand`.
    #[cfg(not(feature = "rand"))]
    _rng: PhantomData<fn() -> &'rand ()>,
}
#[allow(
    single_use_lifetimes,
    clippy::allow_attributes,
    clippy::elidable_lifetime_names,
    reason = "unify rand and not rand"
)]
impl<'input, 'cache, 'prev, 'scratch, 'rand> Evaluator<'input, 'cache, 'prev, 'scratch, 'rand> {
    /// Creates an `Evaluator<'input, 'cache, 'prev, 'scratch, 'rand>` based on the supplied arguments.
    #[cfg(not(feature = "rand"))]
    #[inline]
    pub fn new(
        utf8: &'input [u8],
        cache: &'cache mut Cache<Ratio<BigInt>, 8>,
        prev: &'prev mut Option<Ratio<BigInt>>,
        scratch: &'scratch mut Vec<Ratio<BigInt>>,
    ) -> Self {
        Self {
            utf8,
            i: 0,
            cache,
            prev,
            scratch,
            _rng: PhantomData,
        }
    }
    /// Creates an `Evaluator<'input, 'cache, 'prev, 'scratch, 'rand>` based on the supplied arguments.
    #[cfg(feature = "rand")]
    #[inline]
    pub const fn new(
        utf8: &'input [u8],
        cache: &'cache mut Cache<Ratio<BigInt>, 8>,
        prev: &'prev mut Option<Ratio<BigInt>>,
        scratch: &'scratch mut Vec<Ratio<BigInt>>,
        rng: &'rand mut ThreadRng,
    ) -> Self {
        Self {
            utf8,
            i: 0,
            cache,
            prev,
            scratch,
            rng,
        }
    }
    /// Evaluates the input consuming the `Evaluator<'input, 'cache, 'exp>`.
    ///
    /// Requires the input to contain one expression (i.e., if there are
    /// multiple newlines, it will error).
    ///
    /// # Errors
    ///
    /// Returns a [`LangErr`] iff the input violates the calc language.
    #[expect(clippy::indexing_slicing, reason = "correct")]
    #[inline]
    pub fn evaluate(mut self) -> Result<O<'prev>, LangErr> {
        self.utf8 = if self.utf8.last().is_none_or(|b| *b != b'\n') {
            self.utf8
        } else {
            &self.utf8[..self.utf8.len()
                - self
                    .utf8
                    .get(self.utf8.len().wrapping_sub(2))
                    .map_or(1, |b| if *b == b'\r' { 2 } else { 1 })]
        };
        self.consume_ws();
        let Some(b) = self.utf8.get(self.i) else {
            return Ok(Empty(self.prev));
        };
        if *b == b'q' {
            self.i += 1;
            self.consume_ws();
            if self.i == self.utf8.len() {
                Ok(Exit)
            } else {
                Err(InvalidQuit)
            }
        } else if *b == b's' {
            self.i += 1;
            self.consume_ws();
            if self.i == self.utf8.len() {
                if let Some(ref val) = *self.prev {
                    self.cache.push(val.clone());
                }
                Ok(Store(self.prev))
            } else {
                Err(InvalidStore)
            }
        } else {
            self.get_adds().and_then(move |val| {
                self.consume_ws();
                if self.i == self.utf8.len() {
                    Ok(Eval(self.prev.insert(val)))
                } else {
                    Err(TrailingSyms(self.i))
                }
            })
        }
    }
    /// Reads from the input until the next non-{space/tab} byte value.
    #[expect(clippy::indexing_slicing, reason = "correct")]
    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..]
            .iter()
            .try_fold(0, |val, b| match *b {
                b' ' | b'\t' => Ok(val + 1),
                _ => Err(val),
            })
            .unwrap_or_else(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.
    fn get_adds(&mut self) -> Result<Ratio<BigInt>, LangErr> {
        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.
    fn get_mults(&mut self) -> Result<Ratio<BigInt>, LangErr> {
        let mut left = self.get_neg()?;
        let mut right;
        let mut j;
        let mut mod_val;
        let mut numer;
        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 if let Some(k) = self.utf8.get(self.i..self.i.saturating_add(3)) {
                if k == b"mod" {
                    if !left.is_integer() {
                        return Err(ModIsNotInt(self.i));
                    }
                    self.i += 3;
                    self.consume_ws();
                    right = self.get_neg()?;
                    if !right.is_integer() {
                        return Err(ModIsNotInt(self.i));
                    }
                    numer = right.numer();
                    if numer.sign() == Sign::NoSign {
                        return Err(ModZero(self.i));
                    }
                    mod_val = left.numer() % numer;
                    left = Ratio::from_integer(if mod_val.sign() == Sign::Minus {
                        if numer.sign() == Sign::Minus {
                            mod_val - numer
                        } else {
                            mod_val + numer
                        }
                    } else {
                        mod_val
                    });
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        Ok(left)
    }
    /// Evaluates negation expressions as defined in the calc language.
    /// This function is based on exponentiation expressions.
    fn get_neg(&mut self) -> Result<Ratio<BigInt>, LangErr> {
        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 })
    }
    /// Gets the square root of value so long as a solution exists.
    #[expect(
        clippy::unreachable,
        reason = "code that shouldn't happen did, so we want to crash"
    )]
    fn sqrt(val: Ratio<BigInt>) -> Option<Ratio<BigInt>> {
        /// Returns the square root of `n` if one exists; otherwise
        /// returns `None`.
        /// MUST NOT pass 0.
        #[expect(clippy::suspicious_operation_groupings, reason = "false positive")]
        fn calc(n: &BigUint) -> Option<BigUint> {
            let mut shift = n.bits();
            shift += shift & 1;
            let mut result = BigUint::new(Vec::new());
            let one = BigUint::new(vec![1]);
            let zero = BigUint::new(Vec::new());
            loop {
                shift -= 2;
                result <<= 1u32;
                result |= &one;
                result ^= if &result * &result > (n >> shift) {
                    &one
                } else {
                    &zero
                };
                if shift == 0 {
                    break (&result * &result == *n).then_some(result);
                }
            }
        }
        let numer = val.numer();
        if numer.sign() == Sign::NoSign {
            Some(val)
        } else {
            numer.try_into().map_or_else(
                |_| None,
                |num| {
                    calc(&num).and_then(|n| {
                        calc(&val.denom().try_into().unwrap_or_else(|_| {
                            unreachable!("Ratio must never have a negative denominator")
                        }))
                        .map(|d| Ratio::new(n.into(), d.into()))
                    })
                },
            )
        }
    }
    /// Evaluates exponentiation expressions as defined in the calc language.
    /// This function is based on negation expressions.
    fn get_exps(&mut self) -> Result<Ratio<BigInt>, LangErr> {
        let mut t = self.get_fact()?;
        let ix = self.scratch.len();
        let mut prev;
        let mut numer;
        self.scratch.push(t);
        self.consume_ws();
        let mut j;
        let one = BigInt::new(Sign::Plus, vec![1]);
        let min_one = BigInt::new(Sign::Minus, vec![1]);
        let two = BigInt::new(Sign::Plus, vec![2]);
        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()?;
                // Safe since we always push at least one value, and we always
                // return immediately once we encounter an error.
                prev = self.scratch.index(self.scratch.len() - 1);
                numer = prev.numer();
                // Equiv to checking if prev is 0.
                if numer.sign() == Sign::NoSign {
                    if t.numer().sign() == Sign::Minus {
                        self.scratch.clear();
                        return Err(ExpDivByZero(self.i));
                    }
                    self.scratch.push(t);
                } else if prev.is_integer() {
                    let t_numer = t.numer();
                    // 1 raised to anything is 1, so we don't bother
                    // storing the exponent.
                    if *numer == one {
                    } else if t.is_integer()
                        || ((*t_numer == one || *t_numer == min_one) && *t.denom() == two)
                    {
                        self.scratch.push(t);
                    } else {
                        self.scratch.clear();
                        return Err(ExpIsNotIntOrOneHalf(self.i));
                    }
                } else if t.is_integer()
                    || ((*t.numer() == one || *t.numer() == min_one) && *t.denom() == two)
                {
                    self.scratch.push(t);
                } else {
                    self.scratch.clear();
                    return Err(ExpIsNotIntOrOneHalf(self.i));
                }
            } else {
                break;
            }
        }
        self.scratch
            .drain(ix..)
            .try_rfold(Ratio::from_integer(one.clone()), |exp, base| {
                if exp.is_integer() {
                    Ok(base.pow(exp.numer()))
                } else if base.numer().sign() == Sign::NoSign {
                    Ok(base)
                } else if *exp.denom() == two {
                    if *exp.numer() == one {
                        Self::sqrt(base).map_or_else(|| Err(SqrtDoesNotExist(self.i)), Ok)
                    } else if *exp.numer() == min_one {
                        Self::sqrt(base)
                            .map_or_else(|| Err(SqrtDoesNotExist(self.i)), |v| Ok(v.inv()))
                    } else {
                        Err(ExpIsNotIntOrOneHalf(self.i))
                    }
                } else {
                    Err(ExpIsNotIntOrOneHalf(self.i))
                }
            })
    }
    /// Evaluates factorial expressions as defined in the calc language.
    /// This function is based on terminal expressions.
    fn get_fact(&mut self) -> Result<Ratio<BigInt>, LangErr> {
        /// Calculates the factorial of `val`.
        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().try_into().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 number literal expressions, parenthetical expressions,
    /// recall expressions, absolute value expressions, round expressions, and possibly
    /// rand expressions if that feature is enabled.
    fn get_term(&mut self) -> Result<Ratio<BigInt>, LangErr> {
        self.get_rational().map_or_else(Err, |o| {
            o.map_or_else(
                || {
                    self.get_par().map_or_else(Err, |o2| {
                        o2.map_or_else(
                            || {
                                self.get_recall().map_or_else(Err, |o3| {
                                    o3.map_or_else(
                                        || {
                                            self.get_abs().map_or_else(Err, |o4| {
                                                o4.map_or_else(
                                                    || {
                                                        self.get_round().and_then(|o5| {
                                                            o5.map_or_else(
                                                                #[cfg(not(feature = "rand"))]
                                                                || Err(MissingTerm(self.i)),
                                                                #[cfg(feature = "rand")]
                                                                || self.get_rand(),
                                                                Ok,
                                                            )
                                                        })
                                                    },
                                                    Ok,
                                                )
                                            })
                                        },
                                        Ok,
                                    )
                                })
                            },
                            Ok,
                        )
                    })
                },
                Ok,
            )
        })
    }
    /// Generates a random 64-bit integer. This function is based on add 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`.
    #[cfg(feature = "rand")]
    fn get_rand(&mut self) -> Result<Ratio<BigInt>, LangErr> {
        /// Generates a random 64-bit integer.
        #[expect(clippy::host_endian_bytes, reason = "must keep platform endianness")]
        fn rand(rng: &mut ThreadRng) -> i64 {
            let mut bytes = [0; 8];
            // `ThreadRng::try_fill_bytes` is infallible, so easier to call `fill_bytes`.
            rng.fill_bytes(&mut bytes);
            i64::from_ne_bytes(bytes)
        }
        /// Generates a random 64-bit integer inclusively between the passed arguments.
        #[expect(
            clippy::integer_division_remainder_used,
            reason = "need for uniform randomness"
        )]
        #[expect(
            clippy::as_conversions,
            clippy::cast_possible_truncation,
            clippy::cast_possible_wrap,
            clippy::cast_sign_loss,
            reason = "lossless conversions between signed integers"
        )]
        fn rand_range(
            rng: &mut ThreadRng,
            lower: &Ratio<BigInt>,
            upper: &Ratio<BigInt>,
            i: usize,
        ) -> Result<i64, LangErr> {
            if lower > upper {
                return Err(LangErr::RandInvalidArgs(i));
            }
            let lo = lower.ceil();
            let up = upper.floor();
            let lo_int = lo.numer();
            let up_int = up.numer();
            if lo_int > &BigInt::from(i64::MAX) || up_int < &BigInt::from(i64::MIN) {
                return Err(LangErr::RandNoInts(i));
            }
            let lo_min = lo_int.to_i64().unwrap_or(i64::MIN);
            let up_max = up_int.to_i64().unwrap_or(i64::MAX);
            if up_max > lo_min || upper.is_integer() || lower.is_integer() {
                let low = i128::from(lo_min);
                // `i64::MAX >= up_max >= low`; so underflow and overflow cannot happen.
                // range is [1, 2^64] so casting to a u128 is fine.
                let modulus = (i128::from(up_max) - low + 1) as u128;
                // range is [0, i64::MAX] so converting to a `u64` is fine.
                // rem represents how many values need to be removed
                // when generating a random i64 in order for uniformity.
                let rem = (0x0001_0000_0000_0000_0000 % modulus) as u64;
                let mut low_adj;
                loop {
                    low_adj = rand(rng) as u64;
                    // Since rem is in [0, i64::MAX], this is the same as low_adj < 0 || low_adj >= rem.
                    if low_adj >= rem {
                        return Ok(
                            // range is [i64::MIN, i64::MAX]; thus casts are safe.
                            // modulus is up_max - low + 1; so as low grows,
                            // % shrinks by the same factor. i64::MAX happens
                            // when low = up_max = i64::MAX or when low = 0,
                            // up_max = i64::MAX and low_adj is i64::MAX.
                            ((u128::from(low_adj) % modulus) as i128 + low) as i64,
                        );
                    }
                }
            } else {
                Err(LangErr::RandNoInts(i))
            }
        }
        // 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..self.i.saturating_add(5)) else {
            return Err(MissingTerm(self.i));
        };
        if b == b"rand(" {
            self.i += 5;
            self.consume_ws();
            let i = self.i;
            self.utf8.get(self.i).map_or_else(
                || Err(LangErr::InvalidRand(i)),
                |p| {
                    if *p == b')' {
                        self.i += 1;
                        Ok(Ratio::from_integer(BigInt::from(rand(self.rng))))
                    } else {
                        let add = self.get_adds()?;
                        let Some(b2) = self.utf8.get(self.i) else {
                            return Err(LangErr::InvalidRand(self.i));
                        };
                        if *b2 == b',' {
                            self.i += 1;
                            self.consume_ws();
                            let add2 = self.get_adds()?;
                            self.consume_ws();
                            let Some(b3) = self.utf8.get(self.i) else {
                                return Err(LangErr::InvalidRand(self.i));
                            };
                            if *b3 == b')' {
                                self.i += 1;
                                rand_range(self.rng, &add, &add2, self.i)
                                    .map(|v| Ratio::from_integer(BigInt::from(v)))
                            } else {
                                Err(LangErr::InvalidRand(self.i))
                            }
                        } else {
                            Err(LangErr::InvalidRand(self.i))
                        }
                    }
                },
            )
        } else {
            Err(MissingTerm(self.i))
        }
    }
    /// Rounds a value to the specified number of fractional digits.
    /// This function is based on add expressions.
    fn get_round(&mut self) -> Result<Option<Ratio<BigInt>>, LangErr> {
        let Some(b) = self.utf8.get(self.i..self.i.saturating_add(6)) else {
            return Ok(None);
        };
        if b == b"round(" {
            self.i += 6;
            self.consume_ws();
            let val = self.get_adds()?;
            self.consume_ws();
            let Some(b2) = self.utf8.get(self.i) else {
                return Err(InvalidRound(self.i));
            };
            let b3 = *b2;
            if b3 == b',' {
                self.i += 1;
                self.consume_ws();
                let Some(b4) = self.utf8.get(self.i) else {
                    return Err(InvalidRound(self.i));
                };
                let r = if b4.is_ascii_digit() {
                    self.i += 1;
                    *b4 - b'0'
                } else {
                    return Err(InvalidRound(self.i));
                };
                self.consume_ws();
                let i = self.i;
                self.utf8.get(self.i).map_or_else(
                    || Err(InvalidRound(i)),
                    |p| {
                        if *p == b')' {
                            self.i += 1;
                            let mult =
                                BigInt::from_biguint(Sign::Plus, BigUint::new(vec![10])).pow(r);
                            Ok(Some((val * &mult).round() / &mult))
                        } else {
                            Err(InvalidRound(self.i))
                        }
                    },
                )
            } else {
                Err(InvalidRound(self.i))
            }
        } else {
            Ok(None)
        }
    }
    /// Evaluates absolute value expressions as defined in the calc language.
    /// This function is based on add expressions.
    fn get_abs(&mut self) -> Result<Option<Ratio<BigInt>>, LangErr> {
        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)
        }
    }
    /// Evaluates recall expressions as defined in the calc language.
    // This does not return a Result<Option<&Ratio<BigInt>>, LangErr>
    // since the only place this function is called is in get_term which
    // would end up needing to clone the Ratio anyway. By not forcing
    // get_term to clone, it can rely on map_or_else over match expressions.
    fn get_recall(&mut self) -> Result<Option<Ratio<BigInt>>, LangErr> {
        let Some(b) = self.utf8.get(self.i) else {
            return Ok(None);
        };
        if *b == b'@' {
            self.i += 1;
            self.cache
                .get(self.utf8.get(self.i).map_or(0, |b2| {
                    if (b'1'..b'9').contains(b2) {
                        self.i += 1;
                        usize::from(*b2 - b'1')
                    } else {
                        0
                    }
                }))
                .map_or_else(
                    || Err(NotEnoughPrevResults(self.cache.len())),
                    |p| Ok(Some(p.clone())),
                )
        } else {
            Ok(None)
        }
    }
    /// Evaluates parenthetical expressions as defined in the calc language.
    /// This function is based on add expressions.
    fn get_par(&mut self) -> Result<Option<Ratio<BigInt>>, LangErr> {
        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(InvalidPar(self.i));
            };
            let b3 = *b2;
            if b3 == b')' {
                self.i += 1;
                Ok(Some(r))
            } else {
                Err(InvalidPar(self.i))
            }
        } else {
            Ok(None)
        }
    }
    /// Evaluates number literal expressions as defined in the calc language.
    #[expect(clippy::indexing_slicing, reason = "correct")]
    fn get_rational(&mut self) -> Result<Option<Ratio<BigInt>>, LangErr> {
        // 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.iter()
                .try_fold((BigUint::new(Vec::new()), 0), |mut prev, d| {
                    if d.is_ascii_digit() {
                        prev.1 += 1;
                        // `*d - b'0'` is guaranteed to return a integer between 0 and 9.
                        prev.0 = prev.0 * 10u8 + (*d - b'0');
                        Ok(prev)
                    } else {
                        Err(prev)
                    }
                })
                .unwrap_or_else(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,
            ))))
        }
    }
}
/// Reads data from `R` passing each line to an [`Evaluator`] to be evaluated.
#[cfg(feature = "std")]
#[derive(Debug)]
pub struct EvalIter<R> {
    /// Reader that contains input data.
    reader: R,
    /// Buffer that is used by `reader` to read
    /// data into.
    input_buffer: Vec<u8>,
    /// Cache of stored results.
    cache: Cache<Ratio<BigInt>, 8>,
    /// Result of the previous expression.
    prev: Option<Ratio<BigInt>>,
    /// Buffer used by [`Evaluator`] to process
    /// sub-expressions.
    exp_buffer: Vec<Ratio<BigInt>>,
    /// Random number generator.
    #[cfg(feature = "rand")]
    rng: ThreadRng,
}
#[cfg(feature = "std")]
impl<R> EvalIter<R> {
    /// Creates a new `EvalIter`.
    #[cfg(feature = "rand")]
    #[inline]
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            input_buffer: Vec::new(),
            cache: Cache::new(),
            prev: None,
            exp_buffer: Vec::new(),
            rng: rand::rng(),
        }
    }
    /// Creates a new `EvalIter`.
    #[cfg(any(doc, not(feature = "rand")))]
    #[inline]
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            input_buffer: Vec::new(),
            cache: Cache::new(),
            prev: None,
            exp_buffer: Vec::new(),
        }
    }
}
#[cfg(feature = "std")]
extern crate std;
#[cfg(feature = "std")]
use std::io::{BufRead, Error};
/// Error returned from [`EvalIter`] when an expression has an error.
#[cfg(feature = "std")]
#[derive(Debug)]
pub enum E {
    /// Error containing [`Error`] which is returned
    /// from [`EvalIter`] when reading from the supplied
    /// [`BufRead`]er.
    Error(Error),
    /// Error containing [`LangErr`] which is returned
    /// from [`EvalIter`] when evaluating a single expression.
    LangErr(LangErr),
}
#[cfg(feature = "std")]
impl Display for E {
    #[inline]
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match *self {
            Self::Error(ref e) => e.fmt(f),
            Self::LangErr(ref e) => e.fmt(f),
        }
    }
}
#[cfg(feature = "std")]
use crate::lending_iterator::LendingIterator;
#[cfg(feature = "std")]
impl<R> LendingIterator for EvalIter<R>
where
    R: BufRead,
{
    type Item<'a>
        = Result<O<'a>, E>
    where
        Self: 'a;
    #[inline]
    fn lend_next(&mut self) -> Option<Result<O<'_>, E>> {
        self.input_buffer.clear();
        self.exp_buffer.clear();
        self.reader
            .read_until(b'\n', &mut self.input_buffer)
            .map_or_else(
                |e| Some(Err(E::Error(e))),
                |c| {
                    if c == 0 {
                        None
                    } else {
                        Evaluator::new(
                            self.input_buffer.as_slice(),
                            &mut self.cache,
                            &mut self.prev,
                            &mut self.exp_buffer,
                            #[cfg(feature = "rand")]
                            &mut self.rng,
                        )
                        .evaluate()
                        .map_or_else(
                            |e| Some(Err(E::LangErr(e))),
                            |o| match o {
                                Empty(_) | Eval(_) | Store(_) => Some(Ok(o)),
                                Exit => None,
                            },
                        )
                    }
                },
            )
    }
}