retex-engine 1.3.0

//! Native l3fp: `\__fp_parse:n` (the expression parser and evaluator) for
//! decimal literals, `+`, `-`, `*`, `/`, unary signs, parentheses, `abs`,
//! `min`, `max`, `round` (with one or two arguments) and `sqrt`, and
//! `\__fp_to_decimal_dispatch:w` (the conversion to `\fp_eval:n`'s output
//! format, see [`TO_DECIMAL`]).
//!
//! `\__fp_parse:n {<expr>}` is the expandable core behind `\fp_eval:n`
//! (= `\fp_to_decimal:n`), LaTeX's `\fpeval`, `\fp_set:Nn`,
//! `\fp_compare:nNnTF`, `\fp_to_dim:n` and so on. Its body is
//! `\exp:w … \exp_end:`, which expands (with `\exp:w`) to l3fp's internal
//! representation of the value:
//!
//! ```text
//! \s__fp \__fp_chk:w 1 <sign> {<exp>} {dddd}{dddd}{dddd}{dddd} \__fp_sep:
//! \s__fp \__fp_chk:w 0 <sign> \s__fp_exact \__fp_sep:     (zero)
//! ```
//!
//! with `<sign>` `0` or `2`, and value `0.dddddddddddddddd × 10^<exp>`
//! (16 significant digits, the first non-zero). With both, `\fp_eval:n`
//! takes four macro calls instead of about 300.
//!
//! # Semantics (verified against l3fp, `expl3-code.tex` 2026-01-19)
//!
//! - Every literal and every operation result is rounded to 16 significant
//!   digits, to nearest with ties to even, on the exact value (literals:
//!   all their digits count). A random differential test of 18 000
//!   expressions against an exact model found no difference.
//! - Zeros keep IEEE signs: `x - x` and `(+0) + (-0)` are `+0`,
//!   `(-0) + (-0)`, `-0`, `0 * -1` and `0 / -3` are `-0`.
//! - Unary `+` and `-` bind tighter than `*` and `/` (l3fp's prefix
//!   precedence is 12, above juxtaposition, `*` and `+`), so `2/-3*4` is
//!   `(2/(-3))*4`; binary operators associate to the left.
//! - Spaces are ignored everywhere, even inside numbers (`1 000` is
//!   `1000`).
//! - Exponents `e`/`E` (letters or other characters) take one optional
//!   sign.
//! - `abs` clears the sign (`abs(-0)` is `0`). `min` and `max` return the
//!   first of equal arguments (`max(-0, 0)` is `-0`). `round(x, n)` rounds
//!   to a multiple of `10^-n` (an integer `n`, 0 by default), ties to even;
//!   a non-zero `x` rounded to zero gives l3fp's `\s__fp_underflow` zero
//!   (no flag), which is only handled natively as the final result (signs
//!   and arithmetic on it are left to l3fp).
//!
//! Everything else declines (returns `false` before any change), so the TeX
//! code runs and gives its own result or error: control sequences
//! (variables, constants, `\c_pi_fp`), other functions and words (`sin`,
//! `pi`, units), function names with spaces or without parentheses
//! (`abs 3`), wrong argument counts, other characters (comparisons, `^`,
//! `**`, tuples), juxtaposition (`2(3)`, `(2)3`, `1.2.3`, `2abs(1)`),
//! malformed numbers (`.`, `1e`, `1e+-3`), empty operands,
//! division by zero, and results or literals near the overflow and
//! underflow thresholds (l3fp raises flags or errors there). Deeply nested
//! parentheses decline too, so TeX's own capacity limits still apply.
//!
//! # Expansion
//!
//! The native result is the token list that `\exp:w` produces from the
//! body. That is only what TeX would see if the body's first token,
//! `\exp:w`, is expanded too, which happens in every context that keeps
//! expanding (`\edef`, `\expanded`, `\romannumeral`/`\exp:w` f-expansion,
//! `\numexpr`, main control, `get_x_token` in general): `\exp:w` runs the
//! whole computation in one step and ends at the `\exp_end:` inside the
//! body, so neither the tokens after the call nor anything observable
//! happens between the call and the result (the computation only
//! expands, with no assignments in the supported subset). The only context
//! that sees the difference is a single expansion step whose result is
//! not expanded further: `\expandafter` (`\exp_after:wN`, o-type
//! arguments, `\exp_not:o`), `\span` in a preamble, Lua's
//! `token.expand`. There the native implementation does not run
//! ([`Engine::one_step`](crate::Engine::one_step)). l3fp itself only
//! calls `\__fp_parse:n` through `\exp:w`.
//!
//! One difference remains, as for every native implementation: the result
//! is one inserted token list instead of the levels of l3fp's macros, so
//! an error message whose context shows those levels would differ. The
//! result is consumed by l3fp's own macros, which raise no errors on it.

use std::cmp::Ordering;

use super::Native;
use crate::Engine;
use crate::cmd::Cmd;
use crate::token::{Token, TokenList};

/// `\__fp_parse:n`.
pub(super) const PARSE: Native = Native {
    name: "__fp_parse:n",
    fingerprints: &[
        (17, 0xfb2c_f44a_d397_391e),
        (14, 0x2699_2289_a96e_8ef4),
        (17, 0x56b6_4172_a704_a406),
    ],
    executes: false,
    run: parse,
};

/// Significant digits.
const PREC: u32 = 16;
/// The largest internal exponent handled natively; l3fp's limit is 10000.
/// Values beyond (and their rounding) are left to l3fp, which raises the
/// overflow and underflow flags.
const EXP_LIMIT: i64 = 9990;
/// The deepest parenthesis nesting handled natively.
const DEPTH_LIMIT: u32 = 100;

/// A finite l3fp value.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Fp {
    /// `under`: a non-zero value rounded to zero by `round`, which l3fp
    /// marks `\s__fp_underflow` (without raising the flag). Such a zero is
    /// only handled natively as the final result.
    Zero { neg: bool, under: bool },
    /// `0.m × 10^exp` with `m` the 16 digits of `mant`
    /// (`10^15 <= mant < 10^16`).
    Normal { neg: bool, mant: u64, exp: i32 },
}

const fn pow10(n: u32) -> u128 {
    10u128.pow(n)
}

fn digits(v: u128) -> u32 {
    v.checked_ilog10().map_or(0, |d| d + 1)
}

/// Rounds `v × 10^e` (plus a non-zero amount below `v`'s last digit if
/// `sticky`) to 16 digits, ties to even.
fn round(neg: bool, v: u128, e: i64, sticky: bool) -> Option<Fp> {
    if v == 0 {
        debug_assert!(!sticky);
        return Some(Fp::zero(neg));
    }
    let d = digits(v);
    let (mut m, mut e) = if d > PREC {
        let k = d - PREC;
        let p = pow10(k);
        let (q, r) = (v / p, v % p);
        let half = 5 * pow10(k - 1);
        let up = r > half || (r == half && (sticky || q % 2 == 1));
        (q + u128::from(up), e + i64::from(k))
    } else {
        debug_assert!(!sticky);
        (v * pow10(PREC - d), e - i64::from(PREC - d))
    };
    if m == pow10(PREC) {
        m /= 10;
        e += 1;
    }
    let exp = e + i64::from(PREC);
    if !(-EXP_LIMIT..=EXP_LIMIT).contains(&exp) {
        return None;
    }
    Some(Fp::Normal {
        neg,
        mant: m as u64,
        exp: exp as i32,
    })
}

impl Fp {
    const fn zero(neg: bool) -> Fp {
        Fp::Zero { neg, under: false }
    }

    /// `self`, unless it is an underflow zero (see [`Fp::Zero`]).
    fn exact(self) -> Option<Fp> {
        (!matches!(self, Fp::Zero { under: true, .. })).then_some(self)
    }

    fn with_sign(self, neg: bool) -> Option<Fp> {
        Some(match self.exact()? {
            Fp::Zero { .. } => Fp::zero(neg),
            Fp::Normal { mant, exp, .. } => Fp::Normal { neg, mant, exp },
        })
    }

    fn neg(self) -> Option<Fp> {
        self.with_sign(!self.is_neg())
    }

    fn add(self, other: Fp) -> Option<Fp> {
        match (self.exact()?, other.exact()?) {
            (Fp::Zero { neg: a, .. }, Fp::Zero { neg: b, .. }) => Some(Fp::zero(a && b)),
            (Fp::Zero { .. }, x) | (x, Fp::Zero { .. }) => Some(x),
            (
                Fp::Normal {
                    neg: na,
                    mant: ma,
                    exp: ea,
                },
                Fp::Normal {
                    neg: nb,
                    mant: mb,
                    exp: eb,
                },
            ) => {
                // Let a be the operand with the larger exponent.
                let (na, ma, ea, nb, mb, eb) = if ea >= eb {
                    (na, ma, ea, nb, mb, eb)
                } else {
                    (nb, mb, eb, na, ma, ea)
                };
                let d = (ea - eb) as u32;
                if d >= 20 {
                    // |b| < 10^-19 |a|: less than a hundredth of an ulp of
                    // the result, which rounds to a.
                    return Some(Fp::Normal {
                        neg: na,
                        mant: ma,
                        exp: ea,
                    });
                }
                let va = i128::from(ma) * pow10(d) as i128;
                let vb = i128::from(mb);
                let v = if na { -va } else { va } + if nb { -vb } else { vb };
                if v == 0 {
                    return Some(Fp::zero(false));
                }
                round(
                    v < 0,
                    v.unsigned_abs(),
                    i64::from(eb) - i64::from(PREC),
                    false,
                )
            }
        }
    }

    fn mul(self, other: Fp) -> Option<Fp> {
        match (self.exact()?, other.exact()?) {
            (
                Fp::Normal {
                    neg: na,
                    mant: ma,
                    exp: ea,
                },
                Fp::Normal {
                    neg: nb,
                    mant: mb,
                    exp: eb,
                },
            ) => round(
                na != nb,
                u128::from(ma) * u128::from(mb),
                i64::from(ea) + i64::from(eb) - 2 * i64::from(PREC),
                false,
            ),
            (a, b) => Some(Fp::zero(a.is_neg() != b.is_neg())),
        }
    }

    fn div(self, other: Fp) -> Option<Fp> {
        let Fp::Normal {
            neg: nb,
            mant: mb,
            exp: eb,
        } = other.exact()?
        else {
            return None; // division by zero: l3fp's error and flag
        };
        match self.exact()? {
            Fp::Zero { neg, .. } => Some(Fp::zero(neg != nb)),
            Fp::Normal {
                neg: na,
                mant: ma,
                exp: ea,
            } => {
                // 10^19 < q < 10^21: enough digits for rounding.
                let num = u128::from(ma) * pow10(20);
                let (q, r) = (num / u128::from(mb), num % u128::from(mb));
                round(na != nb, q, i64::from(ea) - i64::from(eb) - 20, r != 0)
            }
        }
    }

    fn is_neg(self) -> bool {
        match self {
            Fp::Zero { neg, .. } | Fp::Normal { neg, .. } => neg,
        }
    }

    /// The order of the values (`-0 = +0`).
    fn cmp(self, other: Fp) -> std::cmp::Ordering {
        // A key increasing with the value: (sign class, magnitude).
        let key = |v: Fp| match v {
            Fp::Zero { .. } => (0, 0, 0),
            Fp::Normal { neg, mant, exp } => {
                if neg {
                    (-1, -i64::from(exp), -(mant as i64))
                } else {
                    (1, i64::from(exp), mant as i64)
                }
            }
        };
        key(self).cmp(&key(other))
    }

    /// `min` (`max` if `max`) of `args`: the first of equal values, as
    /// l3fp (`max(-0, 0)` is `-0`).
    fn min_max(args: &[Fp], max: bool) -> Option<Fp> {
        let mut best = args.first()?.exact()?;
        for &a in &args[1..] {
            let o = a.exact()?.cmp(best);
            if o == if max {
                Ordering::Greater
            } else {
                Ordering::Less
            } {
                best = a;
            }
        }
        Some(best)
    }

    /// `sqrt`, correctly rounded (as l3fp's, verified on random values);
    /// `sqrt(-0)` is `-0`, negative values (l3fp's invalid operation)
    /// decline.
    fn sqrt(self) -> Option<Fp> {
        match self.exact()? {
            z @ Fp::Zero { .. } => Some(z),
            Fp::Normal { neg: true, .. } => None,
            Fp::Normal { mant, exp, .. } => {
                // mant × 10^(exp-16), with an even power of ten and 36 or
                // 37 digits: the root has 18 or 19.
                let mut e = i64::from(exp) - i64::from(PREC) - 20;
                let mut m = u128::from(mant) * pow10(20);
                if e % 2 != 0 {
                    m *= 10;
                    e -= 1;
                }
                let r = m.isqrt();
                round(false, r, e / 2, r * r != m)
            }
        }
    }

    /// `round(self, places)`: to the nearest multiple of `10^-places`, ties
    /// to even. A non-zero value rounded to zero is an underflow zero.
    fn round_to(self, places: i64) -> Option<Fp> {
        let Fp::Normal { neg, mant, exp } = self.exact()? else {
            return Some(self);
        };
        // The number of digits kept.
        let k = i64::from(exp) + places;
        if k >= i64::from(PREC) {
            return Some(self);
        }
        let under = Fp::Zero { neg, under: true };
        if k < 0 {
            return Some(under);
        }
        let p = 10u64.pow(PREC - k as u32);
        let (q, r) = (mant / p, mant % p);
        let half = p / 2;
        let q = q + u64::from(r > half || (r == half && q % 2 == 1));
        if q == 0 {
            return Some(under);
        }
        round(neg, u128::from(q), i64::from(exp) - k, false)
    }
}

/// A token of the expression (spaces removed).
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Lex {
    Digit(u8),
    Dot,
    /// A letter (category 11 or 12), and whether a space follows it.
    Letter(u8, bool),
    Comma,
    Plus,
    Minus,
    Star,
    Slash,
    Open,
    Close,
    /// `<`, `=`, `>`, `!`, `?`, `:`, `&`, `|`.
    Lt,
    Eq,
    Gt,
    Excl,
    Quest,
    Colon,
    Amp,
    Pipe,
    /// A floating point variable or constant (`\l_tmpa_fp`, `\c_pi_fp`).
    Value(Fp),
}

/// The tokens of `toks`, or `None` if one is outside the subset. With an
/// engine, control sequences that are fp variables are values.
fn lex(e: Option<&Engine>, toks: &[Token]) -> Option<Vec<Lex>> {
    let mut out = Vec::with_capacity(toks.len());
    for &t in toks {
        if t.is_cs() {
            out.push(Lex::Value(variable(e?, t)?));
            continue;
        }
        let c = t.chr();
        let cmd = t.cmd_code();
        if cmd == Cmd::Spacer as u32 && c == u32::from(b' ') {
            if let Some(Lex::Letter(_, space)) = out.last_mut() {
                *space = true;
            }
            continue;
        }
        let letter = u8::try_from(c).ok().filter(u8::is_ascii_alphabetic);
        let l = if let Some(c) = letter
            && (cmd == Cmd::Letter as u32 || cmd == Cmd::OtherChar as u32)
        {
            Lex::Letter(c, false)
        } else if cmd == Cmd::OtherChar as u32 {
            match char::from_u32(c)? {
                d @ '0'..='9' => Lex::Digit(d as u8 - b'0'),
                '.' => Lex::Dot,
                '+' => Lex::Plus,
                '-' => Lex::Minus,
                '*' => Lex::Star,
                '/' => Lex::Slash,
                '(' => Lex::Open,
                ')' => Lex::Close,
                ',' => Lex::Comma,
                '<' => Lex::Lt,
                '=' => Lex::Eq,
                '>' => Lex::Gt,
                '!' => Lex::Excl,
                '?' => Lex::Quest,
                ':' => Lex::Colon,
                '&' => Lex::Amp,
                '|' => Lex::Pipe,
                _ => return None,
            }
        } else if cmd == Cmd::TabMark as u32 && c == u32::from(b'&') {
            Lex::Amp
        } else {
            return None;
        };
        out.push(l);
    }
    Some(out)
}

/// The value of an fp variable: a parameterless macro whose body is a
/// finite value's tuple (zeros with `\s__fp_exact`).
fn variable(e: &Engine, t: Token) -> Option<Fp> {
    let m = e.eqtb.meaning(t.cs_id());
    if m.cmd != Cmd::Call {
        return None;
    }
    let mac = m.mac.as_ref()?;
    if mac.protected {
        return None;
    }
    let body = mac.tokens.strip_prefix(&[Token::END_MATCH])?;
    let s_fp = e.hash.lookup(b"s__fp").map(Token::cs)?;
    let (&first, rest) = body.split_first()?;
    if first != s_fp {
        return None;
    }
    let (v, n) = read_tuple(e, rest)?;
    if n != rest.len() {
        return None;
    }
    if let Fp::Zero { under: false, .. } | Fp::Normal { .. } = v {
        // A zero read back carries \s__fp_exact or \s__fp_underflow: only
        // the exact marker is a plain zero.
        if let Fp::Zero { .. } = v
            && rest.get(3) != e.hash.lookup(b"s__fp_exact").map(Token::cs).as_ref()
        {
            return None;
        }
        return Some(v);
    }
    None
}

/// `1` or `0`, as l3fp's `\c_one_fp` and `\c_zero_fp`.
fn truth(b: bool) -> Fp {
    if b {
        Fp::Normal {
            neg: false,
            mant: 1_000_000_000_000_000,
            exp: 1,
        }
    } else {
        Fp::zero(false)
    }
}

fn is_zero(v: Fp) -> bool {
    matches!(v, Fp::Zero { .. })
}

struct Parser {
    lex: Vec<Lex>,
    pos: usize,
    depth: u32,
}

impl Parser {
    fn peek(&self) -> Option<Lex> {
        self.lex.get(self.pos).copied()
    }

    /// `?:` (precedences 4 and 3), right to left.
    fn ternary(&mut self) -> Option<Fp> {
        let c = self.or()?;
        if self.peek() != Some(Lex::Quest) {
            return Some(c);
        }
        self.pos += 1;
        let a = self.ternary()?;
        if self.peek()? != Lex::Colon {
            return None; // l3fp's missing-colon error
        }
        self.pos += 1;
        let b = self.ternary()?;
        Some(if is_zero(c.exact()?) { b } else { a })
    }

    /// `||` (precedence 5): the first value unless it is zero.
    fn or(&mut self) -> Option<Fp> {
        let mut v = self.and()?;
        while self.peek() == Some(Lex::Pipe) {
            self.pos += 1;
            if self.peek()? != Lex::Pipe {
                return None;
            }
            self.pos += 1;
            let w = self.and()?;
            v = if is_zero(v.exact()?) { w } else { v };
        }
        Some(v)
    }

    /// `&&` (precedence 6): the first value if it is zero.
    fn and(&mut self) -> Option<Fp> {
        let mut v = self.comparison()?;
        while self.peek() == Some(Lex::Amp) {
            self.pos += 1;
            if self.peek()? != Lex::Amp {
                return None;
            }
            self.pos += 1;
            let w = self.comparison()?;
            v = if is_zero(v.exact()?) { v } else { w };
        }
        Some(v)
    }

    /// The relation after a value: the flags for less, equal, greater
    /// (`!` first negates), as `\__fp_parse_compare:NNNNNNN` collects them.
    fn relation(&mut self) -> Option<Option<[bool; 3]>> {
        let (mut set, mut flags) = match self.peek() {
            Some(Lex::Excl) => {
                self.pos += 1;
                (false, [true; 3])
            }
            Some(Lex::Lt | Lex::Eq | Lex::Gt) => (true, [false; 3]),
            _ => return Some(None),
        };
        let mut any = false;
        loop {
            match self.peek() {
                Some(Lex::Lt) => flags[0] = set,
                Some(Lex::Eq) => flags[1] = set,
                Some(Lex::Gt) => flags[2] = set,
                Some(Lex::Quest) => {} // unordered: never for finite values
                _ => break,
            }
            any = true;
            self.pos += 1;
            let _ = &mut set;
        }
        if !any {
            return None; // `!` alone: l3fp's error
        }
        Some(Some(flags))
    }

    /// Comparisons (precedence 7), chained as l3fp chains them.
    fn comparison(&mut self) -> Option<Fp> {
        let mut a = self.sum()?;
        let mut result: Option<bool> = None;
        while let Some(flags) = self.relation()? {
            let b = self.sum()?;
            let holds = match a.exact()?.cmp(b.exact()?) {
                Ordering::Less => flags[0],
                Ordering::Equal => flags[1],
                Ordering::Greater => flags[2],
            };
            result = Some(result.unwrap_or(true) && holds);
            a = b;
        }
        Some(match result {
            Some(r) => truth(r),
            None => a,
        })
    }

    fn sum(&mut self) -> Option<Fp> {
        let mut v = self.product()?;
        loop {
            match self.peek() {
                Some(Lex::Plus) => {
                    self.pos += 1;
                    v = v.add(self.product()?)?;
                }
                Some(Lex::Minus) => {
                    self.pos += 1;
                    v = v.add(self.product()?.neg()?)?;
                }
                _ => return Some(v),
            }
        }
    }

    fn product(&mut self) -> Option<Fp> {
        let mut v = self.unary()?;
        loop {
            match self.peek() {
                Some(Lex::Star) => {
                    self.pos += 1;
                    if self.peek() == Some(Lex::Star) {
                        return None; // `**`, a power
                    }
                    v = v.mul(self.unary()?)?;
                }
                Some(Lex::Slash) => {
                    self.pos += 1;
                    v = v.div(self.unary()?)?;
                }
                _ => return Some(v),
            }
        }
    }

    fn unary(&mut self) -> Option<Fp> {
        let mut neg = false;
        let mut minus = false;
        loop {
            match self.peek()? {
                Lex::Plus => {}
                Lex::Minus => {
                    neg = !neg;
                    minus = true;
                }
                Lex::Excl => {
                    // `!` (precedence 12, like the signs): 1 for zero, else 0.
                    self.pos += 1;
                    let v = self.unary()?.exact()?;
                    let r = truth(is_zero(v));
                    return match (neg, minus) {
                        (true, _) => r.neg(),
                        _ => Some(r),
                    };
                }
                _ => break,
            }
            self.pos += 1;
        }
        let v = self.primary()?;
        match (neg, minus) {
            (true, _) => v.neg(),
            (false, true) => v.exact(),
            (false, false) => Some(v),
        }
    }

    fn primary(&mut self) -> Option<Fp> {
        match self.peek()? {
            Lex::Open => {
                self.depth += 1;
                if self.depth > DEPTH_LIMIT {
                    return None;
                }
                self.pos += 1;
                let v = self.ternary()?;
                if self.peek()? != Lex::Close {
                    return None;
                }
                self.pos += 1;
                self.depth -= 1;
                Some(v)
            }
            Lex::Digit(_) | Lex::Dot => self.number(),
            Lex::Letter(..) => self.function(),
            Lex::Value(v) => {
                self.pos += 1;
                // Juxtaposition after a variable is l3fp's business.
                if matches!(
                    self.peek(),
                    Some(Lex::Digit(_) | Lex::Dot | Lex::Letter(..) | Lex::Open | Lex::Value(_))
                ) {
                    return None;
                }
                Some(v)
            }
            _ => None,
        }
    }

    /// `abs`, `min`, `max` or `round`, followed directly by its
    /// parenthesized arguments.
    fn function(&mut self) -> Option<Fp> {
        let start = self.pos;
        let mut name = Vec::new();
        while let Some(Lex::Letter(c, space)) = self.peek() {
            if space {
                return None; // l3fp's reading of spaced words is not checked
            }
            name.push(c);
            self.pos += 1;
        }
        if self.peek()? != Lex::Open || self.pos - start > 5 {
            return None;
        }
        self.pos += 1;
        self.depth += 1;
        if self.depth > DEPTH_LIMIT {
            return None;
        }
        let mut args = vec![self.ternary()?];
        loop {
            match self.peek()? {
                Lex::Comma => {
                    self.pos += 1;
                    args.push(self.ternary()?);
                }
                Lex::Close => break,
                _ => return None,
            }
        }
        self.pos += 1;
        self.depth -= 1;
        match (&name[..], &args[..]) {
            (b"abs", &[x]) => x.with_sign(false),
            (b"sqrt", &[x]) => x.sqrt(),
            (b"min", _) => Fp::min_max(&args, false),
            (b"max", _) => Fp::min_max(&args, true),
            (b"round", &[x]) => x.round_to(0),
            (b"round", &[x, n]) => x.round_to(places(n)?),
            _ => None,
        }
    }

    /// A decimal literal: digits, an optional fraction, an optional
    /// exponent.
    fn number(&mut self) -> Option<Fp> {
        // The first 17 significant digits, whether any later one is
        // non-zero, and the number of significant digits dropped.
        let mut m: u128 = 0;
        let mut kept = 0u32;
        let mut sticky = false;
        let mut scale: i64 = 0; // m × 10^scale is the mantissa
        let mut any = false;
        let mut frac = false;
        loop {
            match self.peek() {
                Some(Lex::Digit(d)) => {
                    any = true;
                    if m == 0 && d == 0 {
                        // a leading zero
                    } else if kept < PREC + 1 {
                        m = m * 10 + u128::from(d);
                        kept += 1;
                    } else {
                        sticky |= d != 0;
                        scale += 1;
                    }
                    if frac {
                        scale -= 1;
                    }
                }
                Some(Lex::Dot) if !frac => frac = true,
                _ => break,
            }
            self.pos += 1;
        }
        if !any {
            return None; // `.` alone: l3fp reads it as 0
        }
        let mut exp: i64 = 0;
        if let Some(Lex::Letter(b'e' | b'E', _)) = self.peek() {
            self.pos += 1;
            let neg = match self.peek()? {
                Lex::Plus => {
                    self.pos += 1;
                    false
                }
                Lex::Minus => {
                    self.pos += 1;
                    true
                }
                _ => false,
            };
            let mut n = 0;
            while let Some(Lex::Digit(d)) = self.peek() {
                self.pos += 1;
                n += 1;
                exp = exp * 10 + i64::from(d);
                if exp >= 100_000_000 {
                    return None;
                }
            }
            if n == 0 {
                return None;
            }
            if neg {
                exp = -exp;
            }
        }
        // Juxtaposition (`2(3)`, `1.2.3`, `1e5e3`) is l3fp's business.
        if matches!(
            self.peek(),
            Some(Lex::Digit(_) | Lex::Dot | Lex::Letter(..) | Lex::Open | Lex::Value(_))
        ) {
            return None;
        }
        if m == 0 {
            return Some(Fp::zero(false));
        }
        // Scale may be large for very long literals: keep the exponent
        // range check in `round` meaningful.
        let e = scale.checked_add(exp)?;
        if e.abs() > 1_000_000_000 {
            return None;
        }
        round(false, m, e, sticky)
    }
}

/// `round`'s number of places: an integer, here at most 1000 in absolute
/// value.
fn places(n: Fp) -> Option<i64> {
    match n.exact()? {
        Fp::Zero { .. } => Some(0),
        Fp::Normal { neg, mant, exp } => {
            if !(1..=4).contains(&exp) {
                return None;
            }
            let p = 10u64.pow(PREC - exp as u32);
            if mant % p != 0 {
                return None;
            }
            let v = (mant / p) as i64;
            (v <= 1000).then_some(if neg { -v } else { v })
        }
    }
}

/// Evaluates an expression of the subset; `None` to decline.
fn eval(e: Option<&Engine>, toks: &[Token]) -> Option<Fp> {
    let mut p = Parser {
        lex: lex(e, toks)?,
        pos: 0,
        depth: 0,
    };
    let v = p.ternary()?;
    (p.pos == p.lex.len()).then_some(v)
}

/// The representation of `v` as l3fp's tokens.
fn tuple(e: &Engine, v: Fp) -> Option<Vec<Token>> {
    let cs = |name: &[u8]| e.hash.lookup(name).map(Token::cs);
    let s_fp = cs(b"s__fp")?;
    let chk = cs(b"__fp_chk:w")?;
    let sep = cs(b"__fp_sep:")?;
    let digit = |d: u64| Token::other(u32::from(b'0') + d as u32);
    let sign = |neg: bool| Token::other(if neg { '2' } else { '0' } as u32);
    let mut out = Vec::with_capacity(36);
    out.extend([s_fp, chk]);
    match v {
        Fp::Zero { neg, under } => {
            let marker = cs(if under {
                b"s__fp_underflow"
            } else {
                b"s__fp_exact"
            })?;
            out.extend([digit(0), sign(neg), marker]);
        }
        Fp::Normal { neg, mant, exp } => {
            out.extend([digit(1), sign(neg), Token::LEFT_BRACE]);
            out.extend(exp.to_string().bytes().map(|b| Token::other(u32::from(b))));
            out.push(Token::RIGHT_BRACE);
            for k in (0..4).rev() {
                let block = mant / 10u64.pow(4 * k) % 10_000;
                out.push(Token::LEFT_BRACE);
                for j in (0..4).rev() {
                    out.push(digit(block / 10u64.pow(j) % 10));
                }
                out.push(Token::RIGHT_BRACE);
            }
        }
    }
    out.push(sep);
    Some(out)
}

fn parse(e: &mut Engine, args: &[TokenList]) -> bool {
    let Some(toks) = eval(Some(e), &args[0]).and_then(|v| tuple(e, v)) else {
        return false;
    };
    e.native_insert(toks);
    true
}

/// `\__fp_to_decimal_dispatch:w`, the first step of `\fp_to_decimal:n`
/// (`\fp_eval:n`, `\fpeval`) and `\fp_to_decimal:N` (`\fp_use:N`) once the
/// value has been computed: `\exp_after:wN \__fp_to_decimal_dispatch:w`
/// followed by the value's tuple. Its argument is the tuple's `\s__fp`;
/// the rest of the tuple follows in the input, where the TeX code reads it
/// with further macros. The native implementation reads it from the
/// current token list (declining if it is not all there) and puts back
/// the decimal string.
///
/// Expansion: as for [`PARSE`], only a single expansion step would see a
/// difference. Expanded further, the TeX code produces its whole result
/// at once: the digits come from `\__fp_trim_zeros_end:w` (or
/// `\__fp_to_decimal_huge:wnnnn`) as one argument, and a leading `-` is
/// put in front with `\exp_after:wN` only after the rest has been
/// f-expanded. It consumes the tuple up to `\__fp_sep:` and nothing more.
pub(super) const TO_DECIMAL: Native = Native {
    name: "__fp_to_decimal_dispatch:w",
    fingerprints: &[(7, 0xf466_93a6_e359_9cb9)],
    executes: false,
    run: to_decimal,
};

/// Reads a tuple without its leading `\s__fp`: the value and the number
/// of tokens. Only l3fp's canonical form of a finite number (zero:
/// `\s__fp_exact`) is accepted.
fn read_tuple(e: &Engine, toks: &[Token]) -> Option<(Fp, usize)> {
    let cs = |name: &[u8]| e.hash.lookup(name).map(Token::cs);
    let other = |t: Token| (!t.is_cs() && t.cmd_code() == Cmd::OtherChar as u32).then(|| t.chr());
    let digit = |t: Token| {
        other(t)
            .filter(|c| (u32::from(b'0')..=u32::from(b'9')).contains(c))
            .map(|c| u64::from(c - u32::from(b'0')))
    };
    let lbrace = |t: Token| !t.is_cs() && t.cmd_code() == Cmd::LeftBrace as u32;
    let rbrace = |t: Token| !t.is_cs() && t.cmd_code() == Cmd::RightBrace as u32;
    let mut it = toks.iter().copied();
    let mut next = || it.next();
    if next()? != cs(b"__fp_chk:w")? {
        return None;
    }
    let (ty, sg) = (next()?, next()?);
    let neg = match other(sg)? {
        0x30 => false,
        0x32 => true,
        _ => return None,
    };
    let sep = cs(b"__fp_sep:")?;
    match other(ty)? {
        0x30 => {
            // `\__fp_to_decimal:w` ignores the marker.
            let m = next()?;
            let ok = m == cs(b"s__fp_exact")? || m == cs(b"s__fp_underflow")?;
            (ok && next()? == sep).then_some((Fp::zero(neg), 5))
        }
        0x31 => {
            let mut n = 3;
            if !lbrace(next()?) {
                return None;
            }
            // The exponent, as `\int_value:w` writes it.
            let mut t = next()?;
            n += 2;
            let eneg = other(t) == Some(u32::from(b'-'));
            if eneg {
                t = next()?;
                n += 1;
            }
            let mut exp: i64 = 0;
            let mut nd = 0;
            while !rbrace(t) {
                let d = digit(t)?;
                if (nd > 0 && exp == 0) || nd >= 6 {
                    return None; // a leading zero, or out of range
                }
                exp = exp * 10 + d as i64;
                nd += 1;
                t = next()?;
                n += 1;
            }
            if nd == 0 || (eneg && exp == 0) || exp > 10_000 {
                return None;
            }
            let mut mant = 0u64;
            for _ in 0..4 {
                if !lbrace(next()?) {
                    return None;
                }
                for _ in 0..4 {
                    mant = mant * 10 + digit(next()?)?;
                }
                if !rbrace(next()?) {
                    return None;
                }
                n += 6;
            }
            if mant < 10u64.pow(PREC - 1) || next()? != sep {
                return None;
            }
            n += 1;
            let exp = if eneg { -exp } else { exp } as i32;
            Some((Fp::Normal { neg, mant, exp }, n))
        }
        _ => None,
    }
}

/// `\fp_to_decimal:n`'s format: no exponent, no trailing zeros, `-0` for
/// negative zero.
fn decimal(v: Fp) -> String {
    match v {
        Fp::Zero { neg, .. } => if neg { "-0" } else { "0" }.into(),
        Fp::Normal { neg, mant, exp } => {
            let digits = mant.to_string();
            let mut s = String::from(if neg { "-" } else { "" });
            if exp >= PREC as i32 {
                s += &digits;
                s.extend(std::iter::repeat_n('0', (exp - PREC as i32) as usize));
            } else if exp > 0 {
                let (int, frac) = digits.split_at(exp as usize);
                s += int;
                let frac = frac.trim_end_matches('0');
                if !frac.is_empty() {
                    s.push('.');
                    s += frac;
                }
            } else {
                s += "0.";
                s.extend(std::iter::repeat_n('0', (-exp) as usize));
                s += digits.trim_end_matches('0');
            }
            s
        }
    }
}

fn to_decimal(e: &mut Engine, args: &[TokenList]) -> bool {
    let Some(s_fp) = e.hash.lookup(b"s__fp").map(Token::cs) else {
        return false;
    };
    if args[0][..] != [s_fp] {
        return false;
    }
    let Some((v, n)) = e.native_following().and_then(|t| read_tuple(e, t)) else {
        return false;
    };
    let out = decimal(v)
        .bytes()
        .map(|b| Token::other(u32::from(b)))
        .collect();
    e.native_skip(n);
    e.native_insert(out);
    true
}

#[cfg(test)]
mod tests {
    use super::*;

    fn lexed(s: &str) -> Vec<Token> {
        s.chars()
            .map(|c| match c {
                ' ' => Token::SPACE,
                'e' | 'E' => Token::letter(c as u32),
                _ => Token::other(c as u32),
            })
            .collect()
    }

    /// The value as l3fp's `\tl_to_str`'d tuple, without the control
    /// sequences.
    fn show(s: &str) -> String {
        match eval(None, &lexed(s)) {
            None => "decline".into(),
            Some(Fp::Zero { neg, under }) => {
                format!(
                    "0{}{}",
                    if neg { 2 } else { 0 },
                    if under { "u" } else { "" }
                )
            }
            Some(Fp::Normal { neg, mant, exp }) => {
                format!("1{}{{{exp}}}{mant}", if neg { 2 } else { 0 })
            }
        }
    }

    #[test]
    fn literals() {
        assert_eq!(show("1"), "10{1}1000000000000000");
        assert_eq!(show(".5"), "10{0}5000000000000000");
        assert_eq!(show("5."), "10{1}5000000000000000");
        assert_eq!(show("1 000"), "10{4}1000000000000000");
        assert_eq!(show("1e-3"), "10{-2}1000000000000000");
        assert_eq!(show("1E+3"), "10{4}1000000000000000");
        assert_eq!(show("1234567890123456.5"), "10{16}1234567890123456");
        assert_eq!(show("1234567890123457.5"), "10{16}1234567890123458");
        assert_eq!(
            show("1234567890123456.5000000000000000000001"),
            "10{16}1234567890123457"
        );
        assert_eq!(show("0.99999999999999995"), "10{1}1000000000000000");
        assert_eq!(show("000.000"), "00");
        assert_eq!(show("0e99999"), "00");
    }

    #[test]
    fn operations() {
        assert_eq!(show("1/3"), "10{0}3333333333333333");
        assert_eq!(show("2/3"), "10{0}6666666666666667");
        assert_eq!(show("1+5e-16"), "10{1}1000000000000000");
        assert_eq!(show("1+1.5e-15"), "10{1}1000000000000002");
        assert_eq!(show("1-5e-17"), "10{1}1000000000000000");
        assert_eq!(show("1-5.0000001e-17"), "10{0}9999999999999999");
        assert_eq!(show("2/-3*4"), "12{1}2666666666666667");
        assert_eq!(show("-1+2"), "10{1}1000000000000000");
        assert_eq!(show("1-2-3"), "12{1}4000000000000000");
        assert_eq!(show("1-1e-30"), "10{1}1000000000000000");
    }

    #[test]
    fn decimal_format() {
        let d = |s: &str| decimal(eval(None, &lexed(s)).unwrap());
        assert_eq!(d("-0"), "-0");
        assert_eq!(d("0"), "0");
        assert_eq!(d("1.5*2+3/7"), "3.428571428571429");
        assert_eq!(d("1e-3"), "0.001");
        assert_eq!(d("-1.25e-5"), "-0.0000125");
        assert_eq!(d("100"), "100");
        assert_eq!(d("1e16"), "10000000000000000");
        assert_eq!(d("12345678901234567890"), "12345678901234570000");
        assert_eq!(d("1234567890123456"), "1234567890123456");
        assert_eq!(d("0.5"), "0.5");
    }

    #[test]
    fn functions() {
        assert_eq!(show("abs(-0)"), "00");
        assert_eq!(show("-abs(-2)"), "12{1}2000000000000000");
        assert_eq!(show("max(-0,0)"), "02");
        assert_eq!(show("min(0,-0)"), "00");
        assert_eq!(show("min(3,1,2)"), "10{1}1000000000000000");
        assert_eq!(show("round(2.5)"), "10{1}2000000000000000");
        assert_eq!(show("round(3.5)"), "10{1}4000000000000000");
        assert_eq!(show("round(-0.4)"), "02u");
        assert_eq!(show("+round(0.4)"), "00u");
        assert_eq!(show("round(1.2345,2)"), "10{1}1230000000000000");
        assert_eq!(show("round(25,-1)"), "10{2}2000000000000000");
        assert_eq!(show("round(5,-1)"), "00u");
        assert_eq!(show("round(9999999999999999,-1)"), "10{17}1000000000000000");
        assert_eq!(show("round((1+2)/7, 2+1)"), "10{0}4290000000000000");
        assert_eq!(show("sqrt(2)"), "10{1}1414213562373095");
        assert_eq!(show("sqrt(-0)"), "02");
        assert_eq!(show("sqrt(1e-999)"), "10{-499}3162277660168379");
        assert_eq!(show("sqrt(-1)"), "decline");
    }

    #[test]
    fn signed_zeros() {
        assert_eq!(show("-0"), "02");
        assert_eq!(show("0*-1"), "02");
        assert_eq!(show("0/-3"), "02");
        assert_eq!(show("1-1"), "00");
        assert_eq!(show("-0+0"), "00");
        assert_eq!(show("-0-0"), "02");
        assert_eq!(show("+-0"), "02");
    }

    #[test]
    fn comparisons_and_logic() {
        let one = "10{1}1000000000000000";
        assert_eq!(show("1<2"), one);
        assert_eq!(show("2<1"), "00");
        assert_eq!(show("1<3<2"), "00");
        assert_eq!(show("1<=1>=1"), one);
        assert_eq!(show("1!=1"), "00");
        assert_eq!(show("1!<2"), "00");
        assert_eq!(show("1<>2"), one);
        assert_eq!(show("-0=0"), one);
        assert_eq!(show("1+2<4*1"), one);
        assert_eq!(show("0&&3"), "00");
        assert_eq!(show("-0&&5"), "02");
        assert_eq!(show("2&&3"), "10{1}3000000000000000");
        assert_eq!(show("2||3"), "10{1}2000000000000000");
        assert_eq!(show("-0||-0"), "02");
        assert_eq!(show("1?2:3?4:5"), "10{1}2000000000000000");
        assert_eq!(show("0?2:0?4:5"), "10{1}5000000000000000");
        assert_eq!(show("!0"), one);
        assert_eq!(show("!-0+1"), "10{1}2000000000000000");
        assert_eq!(show("-!0"), "12{1}1000000000000000");
        assert_eq!(show("2*!0"), "10{1}2000000000000000");
    }

    #[test]
    fn declines() {
        for s in [
            "",
            "()",
            "1+",
            ".",
            "1e",
            "1e+-3",
            "2(3)",
            "(2)3",
            "1.2.3",
            "1e5e3",
            "2**3",
            "1/0",
            "0/0",
            "1e10000",
            "1e-10001",
            "1e9990*10",
            "abs 3",
            "abs (1)",
            "ABS(1)",
            "abs(1,2)",
            "round(1,2,3)",
            "round(1,0.5)",
            "-round(0.4)",
            "round(0.4)+1",
            "max()",
            "exp(1)",
            "1!2",
            "1?2",
            "1&2",
            "1|2",
            "!",
            "1em",
            "(1",
            "1)",
        ] {
            assert_eq!(show(s), "decline", "{s}");
        }
        let deep = format!("{}1{}", "(".repeat(101), ")".repeat(101));
        assert_eq!(show(&deep), "decline");
        let ok = format!("{}1{}", "(".repeat(100), ")".repeat(100));
        assert_eq!(show(&ok), "10{1}1000000000000000");
    }
}