retex-engine 1.3.0

//! l3regex's automaton and matcher, step for step.
//!
//! The automaton is built as `\__regex_build:n` builds it in token
//! registers (`\toks<state>` holds the state's actions): the same state
//! numbers, the same actions in the same order, the same register
//! juggling (`\l__regex_left_state_int`, `\l__regex_tmpa_int`, …) for
//! repeated groups. The matcher then runs the states as
//! `\__regex_match_one_token:nnN` does: threads in priority order, free
//! transitions recursively with the `\g__regex_state_active_intarray`
//! checks (`\__regex_action_free:n` enters a state not finished at this
//! step, `\__regex_action_free_group:n` one not even started), a success
//! abandoning the lower-priority threads (`\prg_break:`), the matched
//! tokens after a success replayed for the next match. Matching that
//! faithfully gives the same matches and submatches in every case, and
//! the final contents of the intarrays l3regex leaves behind.

use super::syntax::{GroupKind, Item, Node, Test};

/// An action of a state, a piece of the contents of its `\toks`.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(super) enum Act {
    /// `\__regex_action_free:n {d}`.
    Free(i32),
    /// `\__regex_action_free_group:n {d}`.
    FreeGroup(i32),
    /// A class's tests, then `\__regex_action_cost:n {d}` if they pass
    /// (class `c` of [`Build::classes`]).
    Test(u32, i32),
    /// `\__regex_action_submatch:nN {k} <` (true) or `>`.
    Submatch(u32, bool),
    /// `\__regex_action_start_wildcard:N`.
    StartWildcard(bool),
    /// `\__regex_action_success:`.
    Success,
    /// An assertion: the test, then the free transition if it gives
    /// `positive`.
    Assert(Test, bool, i32),
    /// `\__regex_command_K:`'s actions around the free transition.
    K(i32),
    /// `\int_gset:Nn \g__regex_case_int {k}` (regex cases).
    SetCase(u32),
}

/// A class: whether it is positive, and its items.
pub(super) struct Class {
    pub positive: bool,
    pub items: Vec<Item>,
}

/// The state of `\__regex_build:N` (its integer registers and sequences).
pub(super) struct Build {
    pub toks: Vec<Vec<Act>>,
    pub classes: Vec<Class>,
    pub min_state: i32,
    pub max: i32,
    left: i32,
    right: i32,
    tmpa: i32,
    tmpb: i32,
    tmpc: i32,
    left_seq: Vec<i32>,
    right_seq: Vec<i32>,
    /// `\l__regex_capturing_group_int`.
    pub groups: i32,
}

/// The largest state number l3regex can use (its `\toks` registers).
const MAX_STATE: i32 = 65535;

impl Build {
    fn toks(&mut self, s: i32) -> Option<&mut Vec<Act>> {
        if !(0..=MAX_STATE).contains(&s) {
            return None;
        }
        let s = s as usize;
        if s >= self.toks.len() {
            self.toks.resize(s + 1, Vec::new());
        }
        Some(&mut self.toks[s])
    }

    fn right_of(&mut self, s: i32, a: Act) -> Option<()> {
        self.toks(s)?.push(a);
        Some(())
    }

    fn left_of(&mut self, s: i32, a: Act) -> Option<()> {
        self.toks(s)?.insert(0, a);
        Some(())
    }

    /// `\__regex_build_new_state:`.
    fn new_state(&mut self) -> Option<()> {
        let m = self.max;
        self.toks(m)?.clear();
        self.left = self.right;
        self.right = m;
        self.max += 1;
        Some(())
    }

    /// `\__regex_build_transitions_laziness:NNNNN`: a new state, with two
    /// transitions, the targets read after it is made. `a`/`b` build the
    /// action from the relative target.
    fn laziness(&mut self, lazy: bool, a: Kind, ta: Target, b: Kind, tb: Target) -> Option<()> {
        self.new_state()?;
        let l = self.left;
        let a = a.act(self.target(ta) - l);
        let b = b.act(self.target(tb) - l);
        if lazy {
            self.right_of(l, a)?;
            self.right_of(l, b)
        } else {
            self.right_of(l, b)?;
            self.right_of(l, a)
        }
    }

    fn target(&self, t: Target) -> i32 {
        match t {
            Target::Left => self.left,
            Target::Right => self.right,
            Target::Tmpa => self.tmpa,
        }
    }

    fn push_lr(&mut self) {
        self.left_seq.push(self.left);
        self.right_seq.push(self.right);
    }

    fn pop_lr(&mut self) -> Option<()> {
        self.left = self.left_seq.pop()?;
        self.right = self.right_seq.pop()?;
        Some(())
    }
}

/// The transitions of [`Build::laziness`]: `\__regex_action_free:n` or a
/// class's `\__regex_tests_action_cost:n`.
#[derive(Clone, Copy)]
enum Kind {
    Free,
    Test(u32),
}

impl Kind {
    fn act(self, d: i32) -> Act {
        match self {
            Kind::Free => Act::Free(d),
            Kind::Test(c) => Act::Test(c, d),
        }
    }
}

/// A register read when a transition is made.
#[derive(Clone, Copy)]
enum Target {
    Left,
    Right,
    Tmpa,
}

/// `\__regex_build:N` of a compiled regex (`\__regex_build_aux:NN` with
/// the wildcard): `None` if the automaton would need registers beyond
/// LuaTeX's.
pub(super) fn build(regex: &[Vec<Node>], min_state: i32) -> Option<Build> {
    let mut b = Build {
        toks: Vec::new(),
        classes: Vec::new(),
        min_state,
        max: min_state,
        left: 0,
        right: 0,
        tmpa: 0,
        tmpb: 0,
        tmpc: 0,
        left_seq: Vec::new(),
        right_seq: Vec::new(),
        groups: 0,
    };
    b.new_state()?;
    b.new_state()?;
    let l = b.left;
    b.right_of(l, Act::StartWildcard(true))?;
    b.group(GroupKind::Capture, regex, 1, 0, false)?;
    let r = b.right;
    b.right_of(r, Act::Success)?;
    Some(b)
}

/// `\__regex_case_build:n` of compiled regexes (`\__regex_case_build_aux:Nn`
/// with the wildcard): the regexes' branches side by side, each regex
/// ending in `\__regex_action_submatch:nN \c_zero_int >`, `\int_gset:Nn
/// \g__regex_case_int {<its number>}` and the success.
pub(super) fn build_case(regexes: &[Vec<Vec<Node>>], min_state: i32) -> Option<Build> {
    let mut b = Build {
        toks: Vec::new(),
        classes: Vec::new(),
        min_state,
        max: min_state,
        left: 0,
        right: 0,
        tmpa: 0,
        tmpb: 0,
        tmpc: 0,
        left_seq: Vec::new(),
        right_seq: Vec::new(),
        groups: 0,
    };
    b.new_state()?;
    b.new_state()?;
    let l = b.left;
    b.right_of(l, Act::StartWildcard(true))?;
    b.new_state()?;
    let l = b.left;
    b.left_of(l, Act::Submatch(0, true))?;
    b.push_lr();
    let mut top = 0;
    for (k, regex) in regexes.iter().enumerate() {
        // \__regex_case_build_loop:n
        b.groups = 1;
        for br in regex {
            b.branch(br)?;
        }
        top = top.max(b.groups);
        b.right = b.right_seq.pop()?;
        let r = b.right;
        let t = b.toks(r)?;
        t.splice(
            0..0,
            [
                Act::Submatch(0, false),
                Act::SetCase(k as u32 + 1),
                Act::Success,
            ],
        );
        let m = b.max;
        b.toks(m)?.clear();
        b.right_seq.push(m);
        b.max += 1;
        if b.max > MAX_STATE {
            return None;
        }
    }
    b.groups = top;
    b.pop_lr()?;
    Some(b)
}

impl Build {
    fn nodes(&mut self, nodes: &[Node]) -> Option<()> {
        for n in nodes {
            match n {
                Node::Class {
                    positive,
                    items,
                    min,
                    max,
                    lazy,
                } => self.class(*positive, items, *min, *max, *lazy)?,
                Node::Group {
                    kind,
                    branches,
                    min,
                    max,
                    lazy,
                } => self.group(*kind, branches, *min, *max, *lazy)?,
                Node::Assert { positive, test } => {
                    self.new_state()?;
                    let d = self.right - self.left;
                    let l = self.left;
                    self.right_of(l, Act::Assert(*test, *positive, d))?;
                }
                Node::K => {
                    self.new_state()?;
                    let d = self.right - self.left;
                    let l = self.left;
                    self.right_of(l, Act::K(d))?;
                }
            }
        }
        Some(())
    }

    /// `\__regex_class:NnnnN`.
    fn class(
        &mut self,
        positive: bool,
        items: &[Item],
        min: i32,
        max: i32,
        lazy: bool,
    ) -> Option<()> {
        let c = self.classes.len() as u32;
        self.classes.push(Class {
            positive,
            items: items.to_vec(),
        });
        match max {
            0 => self.class_repeat(c, min),
            -1 => {
                if min == 0 {
                    self.laziness(lazy, Kind::Free, Target::Right, Kind::Test(c), Target::Left)
                } else {
                    self.class_repeat(c, min)?;
                    self.tmpa = self.left;
                    self.laziness(lazy, Kind::Free, Target::Right, Kind::Free, Target::Tmpa)
                }
            }
            _ => {
                self.class_repeat(c, min)?;
                self.tmpa = self.max + max - 1;
                for _ in 0..max.max(0) {
                    self.laziness(lazy, Kind::Free, Target::Tmpa, Kind::Test(c), Target::Right)?;
                    if self.max > MAX_STATE {
                        return None;
                    }
                }
                Some(())
            }
        }
    }

    /// `\__regex_class_repeat:n`.
    fn class_repeat(&mut self, c: u32, n: i32) -> Option<()> {
        for _ in 0..n.max(0) {
            self.new_state()?;
            let (l, d) = (self.left, self.right - self.left);
            self.right_of(l, Act::Test(c, d))?;
            if self.max > MAX_STATE {
                return None;
            }
        }
        Some(())
    }

    /// `\__regex_group:nnnN` and friends, `\__regex_group_aux:nnnnN`.
    fn group(
        &mut self,
        kind: GroupKind,
        branches: &[Vec<Node>],
        min: i32,
        max: i32,
        lazy: bool,
    ) -> Option<()> {
        let num = if kind == GroupKind::Capture {
            self.groups
        } else {
            -1
        };
        if min == 0 {
            self.new_state()?;
            let (l, d) = (self.left, self.right - self.left);
            self.right_of(l, Act::FreeGroup(d))?;
        }
        self.new_state()?;
        self.push_lr();
        match kind {
            GroupKind::Capture => {
                self.groups += 1;
                for br in branches {
                    self.branch(br)?;
                }
            }
            GroupKind::NoCapture => {
                for br in branches {
                    self.branch(br)?;
                }
            }
            GroupKind::Resetting => {
                // \__regex_group_resetting_loop:nnNn
                let base = self.groups;
                let mut top = base;
                for br in branches {
                    self.groups = base;
                    self.branch(br)?;
                    top = top.max(self.groups);
                }
                self.groups = top;
            }
        }
        self.pop_lr()?;
        match max {
            0 => self.group_repeat(num, min),
            -1 => self.group_repeat_star(num, min, lazy),
            _ => self.group_repeat_range(num, min, max, lazy),
        }
    }

    /// `\__regex_branch:n`.
    fn branch(&mut self, nodes: &[Node]) -> Option<()> {
        self.new_state()?;
        self.left = *self.left_seq.last()?;
        let (l, d) = (self.left, self.right - self.left);
        self.right_of(l, Act::Free(d))?;
        self.nodes(nodes)?;
        let target = *self.right_seq.last()?;
        let r = self.right;
        self.right_of(r, Act::Free(target - r))
    }

    /// `\__regex_group_repeat:nn`.
    fn group_repeat(&mut self, num: i32, min: i32) -> Option<()> {
        if min == 0 {
            self.max = self.left - 1;
            self.new_state()
        } else {
            self.repeat_aux(i64::from(min))?;
            let (a, r) = (self.tmpa, self.right);
            self.submatches(num, a, r)?;
            self.new_state()
        }
    }

    /// `\__regex_group_submatches:nNN`.
    fn submatches(&mut self, num: i32, a: i32, b: i32) -> Option<()> {
        if num > -1 {
            self.left_of(a, Act::Submatch(num as u32, true))?;
            self.left_of(b, Act::Submatch(num as u32, false))?;
        }
        Some(())
    }

    /// `\__regex_group_repeat_aux:n`: the group's states copied `n - 1`
    /// more times (`\__regex_toks_memcpy:NNn` advances `tmpa`, `tmpb`).
    fn repeat_aux(&mut self, n: i64) -> Option<()> {
        let (r, m) = (self.right, self.max);
        self.right_of(r, Act::Free(m - r))?;
        self.tmpa = self.left;
        self.tmpb = self.max;
        if n > 1 {
            let c = (n - 1) * i64::from(self.tmpb - self.tmpa);
            if i64::from(self.max) + c > i64::from(MAX_STATE) + 1 {
                return None;
            }
            self.tmpc = c as i32;
            self.right += self.tmpc;
            self.max += self.tmpc;
            for _ in 0..self.tmpc {
                let src = self.toks(self.tmpa)?.clone();
                let dst = self.tmpb;
                *self.toks(dst)? = src;
                self.tmpb += 1;
                self.tmpa += 1;
            }
        }
        Some(())
    }

    /// `\__regex_group_repeat:nnN`.
    fn group_repeat_star(&mut self, num: i32, min: i32, lazy: bool) -> Option<()> {
        if min == 0 {
            let (l, r) = (self.left, self.right);
            self.submatches(num, l, r)?;
            self.tmpa = self.left - 1;
            let (r, a) = (self.right, self.tmpa);
            self.right_of(r, Act::Free(a - r))?;
            self.new_state()?;
            let (a, r) = (self.tmpa, self.right);
            if lazy {
                self.left_of(a, Act::Free(r - a))
            } else {
                self.right_of(a, Act::Free(r - a))
            }
        } else {
            self.repeat_aux(i64::from(min))?;
            let (a, r) = (self.tmpa, self.right);
            self.submatches(num, a, r)?;
            let (a, r) = (self.tmpa, self.right);
            if lazy {
                self.right_of(r, Act::FreeGroup(a - r))?;
            } else {
                self.left_of(r, Act::FreeGroup(a - r))?;
            }
            self.new_state()
        }
    }

    /// `\__regex_group_repeat:nnnN`.
    fn group_repeat_range(&mut self, num: i32, min: i32, more: i32, lazy: bool) -> Option<()> {
        let (l, r) = (self.left, self.right);
        self.submatches(num, l, r)?;
        self.repeat_aux(i64::from(min) + i64::from(more))?;
        let size = self.tmpb - self.tmpa;
        if lazy {
            self.left = self.max;
            for _ in 0..more {
                self.left -= size;
                let (l, m) = (self.left, self.max);
                self.left_of(l, Act::Free(m - l))?;
            }
        } else {
            for _ in 0..(more - 1).max(0) {
                self.right -= size;
                let (r, m) = (self.right, self.max);
                self.right_of(r, Act::Free(m - r))?;
            }
            if min == 0 {
                self.right = self.left - 1;
            } else {
                self.right -= size;
            }
            let (r, m) = (self.right, self.max);
            self.right_of(r, Act::Free(m - r))?;
        }
        self.new_state()
    }
}

// ----- matching ------------------------------------------------------------

/// A token of the token list being matched, as `\tl_analysis_map_inline`
/// reports it: character code (-1 for control sequences, -2 for the end),
/// category code (0 for control sequences, 15 for the end), and for
/// control sequences the name (for `\c{...}`).
#[derive(Clone, Copy, Debug)]
pub(super) struct Tok {
    pub ch: i32,
    pub cat: u8,
    /// Index of the control sequence's name in [`Input::names`].
    pub name: u32,
}

/// The token list being matched.
pub(super) struct Input {
    pub toks: Vec<Tok>,
    pub names: Vec<Vec<u32>>,
}

/// How each match ends a step (`\l__regex_every_match_tl`).
#[derive(Clone, Copy, PartialEq, Eq)]
pub(super) enum Mode {
    /// `\__regex_single_match:`.
    Single,
    /// `\__regex_multi_match:n` with `\__regex_extract:`.
    Extract,
    /// `\__regex_multi_match:n` with `\int_incr:N \l__regex_match_count_int`.
    Count,
    /// `\__regex_split:nnN`'s.
    Split,
}

/// The last `\csname` l3regex executes, for `\lastnamedcs`.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(super) enum LastCs {
    /// `\l__regex_matched_analysis_tl` with `n` primes (`\tl_build_…`).
    Matched(u32),
    /// `\__tl_map_<n>:w`.
    TlMap(i32),
    /// `\__tl_analysis_map_inline_<n>:wNw`.
    AnalysisMap(i32),
    /// `\__prg_replicate_first_<d>:n`.
    ReplicateFirst(u8),
}

/// What a match leaves.
pub(super) struct Outcome {
    /// `\g__regex_success_bool`.
    pub success: bool,
    /// `\l__regex_match_count_int`.
    pub count: i32,
    /// The intarrays, as (first index, values) of what was written.
    pub state_active: Vec<i64>,
    pub thread_info: Vec<i64>,
    pub sub_prev: Vec<Option<i64>>,
    pub sub_begin: Vec<Option<i64>>,
    pub sub_end: Vec<Option<i64>>,
    pub sub_case: Vec<Option<i64>>,
    /// `\l__regex_submatch_int`, `\l__regex_start_pos_int`,
    /// `\l__regex_empty_success_bool` at the end.
    pub submatch_int: i32,
    pub start_pos: i32,
    pub empty_success: bool,
    /// The deepest `\g__kernel_prg_map_int` of `\tl_map_inline:nn`
    /// (replays), relative to the level of the analysis map (0: none).
    pub max_replay: i32,
    pub last: LastCs,
    /// `\g__regex_case_int` at the end.
    pub case: i64,
}

/// The matcher (the `\l__regex_…` variables of a match).
struct Sim<'a> {
    b: &'a Build,
    input: &'a Input,
    mode: Mode,
    submatches: bool,
    /// `2 * \l__regex_capturing_group_int + 1`.
    width: usize,
    case: i64,
    active: Vec<i64>,
    info: Vec<i64>,
    sub_prev: Vec<Option<i64>>,
    sub_begin: Vec<Option<i64>>,
    sub_end: Vec<Option<i64>>,
    sub_case: Vec<Option<i64>>,
    step: i64,
    curr_pos: i32,
    curr_char: i32,
    last_char: i32,
    curr_cat: u8,
    curr_tok: usize,
    curr_state: i32,
    curr_subs: Vec<i32>,
    /// Saved submatches of the free transitions in progress.
    stack: Vec<i32>,
    /// The threads of the step (a buffer).
    threads: Vec<i64>,
    fresh: bool,
    match_success: bool,
    empty_success: bool,
    two_empty: bool,
    success_pos: i32,
    last_char_success: i32,
    success_subs: Vec<i32>,
    start_pos: i32,
    max_thread: i32,
    submatch_int: i32,
    count: i32,
    g_success: bool,
    depth: u32,
    /// `\l__regex_zeroth_submatch_int`.
    zeroth: i32,
    /// The deepest replay map level.
    max_replay: i32,
    /// Puts into `\l__regex_matched_analysis_tl` since its last begin.
    puts: u32,
    last: LastCs,
}

/// Something that ends the step (`\prg_break:`) or the match.
enum Stop {
    /// A success.
    Break,
    /// Declined (recursion too deep, a token that cannot be judged).
    Unsure,
}

/// The maximum depth of free transitions natively: each level keeps a
/// few levels of TeX's input stack busy, so deeper automata decline
/// (and TeX runs out of input stack as LuaTeX would, if it does).
const MAX_DEPTH: u32 = 500;

/// Runs a match of `b` on `input` (whose last token is the end marker),
/// then `\__regex_extract:` if `extract_after` (single matches). `None`
/// when unsure.
pub(super) fn run(
    b: &Build,
    input: &Input,
    mode: Mode,
    submatches: bool,
    case: i64,
    extract_after: bool,
) -> Option<Outcome> {
    let width = 2 * b.groups as usize + 1;
    let mut s = Sim {
        b,
        input,
        mode,
        submatches,
        width,
        case,
        active: Vec::new(),
        info: Vec::new(),
        sub_prev: Vec::new(),
        sub_begin: Vec::new(),
        sub_end: Vec::new(),
        sub_case: Vec::new(),
        step: 0,
        curr_pos: 0,
        curr_char: -2,
        last_char: -2,
        curr_cat: 15,
        curr_tok: 0,
        curr_state: 0,
        curr_subs: vec![0; width - 1],
        stack: Vec::new(),
        threads: Vec::new(),
        fresh: false,
        match_success: false,
        empty_success: false,
        two_empty: false,
        success_pos: 2,
        last_char_success: -2,
        success_subs: vec![0; width - 1],
        start_pos: 2,
        max_thread: 0,
        submatch_int: 1,
        count: 0,
        g_success: false,
        depth: 0,
        zeroth: 0,
        max_replay: 0,
        puts: 0,
        last: LastCs::Matched(1),
    };
    s.run()?;
    if extract_after && s.g_success {
        s.extract();
    }
    Some(Outcome {
        success: s.g_success,
        count: s.count,
        state_active: s.active,
        thread_info: s.info,
        sub_prev: s.sub_prev,
        sub_begin: s.sub_begin,
        sub_end: s.sub_end,
        sub_case: s.sub_case,
        submatch_int: s.submatch_int,
        start_pos: s.start_pos,
        empty_success: s.empty_success,
        max_replay: s.max_replay,
        last: s.last,
        case: s.case,
    })
}

fn set_at(v: &mut Vec<Option<i64>>, i: i32, x: i64) {
    let i = i as usize;
    if v.len() <= i {
        v.resize(i + 1, None);
    }
    v[i] = Some(x);
}

impl Sim<'_> {
    /// `\__regex_match:n`: the replays as a sequence (see the module
    /// documentation of [`super`]).
    fn run(&mut self) -> Option<()> {
        // \__regex_match_init:
        let (lo, hi) = (self.b.min_state, self.b.max);
        self.active = vec![0; hi.max(0) as usize];
        for st in lo..hi {
            self.active[st as usize] = 1;
        }
        self.begin_matched();
        // \__regex_match_once_init: (empty replay), then the analysis map.
        self.once_init(1)?;
        self.last = LastCs::AnalysisMap(1);
        // Replays in progress: the index of their last token.
        let mut replays: Vec<usize> = Vec::new();
        let n = self.input.toks.len();
        let mut next = 0usize;
        loop {
            while let Some(&e) = replays.last() {
                if next > e {
                    replays.pop();
                } else {
                    break;
                }
            }
            if next >= n {
                return Some(());
            }
            let j = next;
            next += 1;
            self.one_token(j)?;
            // \l__regex_every_match_tl, unless threads remain.
            if self.max_thread > 0 && self.curr_char != -2 {
                continue;
            }
            let stop = match self.mode {
                Mode::Single => {
                    self.g_success = self.match_success;
                    true
                }
                _ => {
                    if self.match_success {
                        self.g_success = true;
                        match self.mode {
                            Mode::Count => self.count += 1,
                            Mode::Extract => self.extract(),
                            Mode::Split => {
                                if self.start_pos < self.success_pos {
                                    self.extract();
                                    let z = self.zeroth;
                                    set_at(&mut self.sub_prev, z, 0);
                                    let b = self.sub_begin[z as usize].unwrap_or(0);
                                    set_at(&mut self.sub_end, z, b);
                                    set_at(&mut self.sub_begin, z, i64::from(self.start_pos));
                                }
                            }
                            Mode::Single => unreachable!(),
                        }
                        // The new map's level: one above the maps in
                        // progress, the replays and the analysis map
                        // (which has ended when the end marker is
                        // processed outside any replay).
                        let outer = replays.first().copied().unwrap_or(j);
                        let level = replays.len() as i32 + 1 + i32::from(outer + 1 < n);
                        self.max_replay = self.max_replay.max(level);
                        self.once_init(level)?;
                        next = (self.start_pos - 2) as usize;
                        replays.push(j);
                        false
                    } else {
                        true
                    }
                }
            };
            if stop {
                // \__regex_maplike_break: leaves the innermost map.
                match replays.pop() {
                    None => return Some(()),
                    Some(e) => next = e + 1,
                }
            }
        }
    }

    fn begin_matched(&mut self) {
        self.puts = 0;
        self.last = LastCs::Matched(1);
    }

    /// `\__regex_match_once_init:`; `level` is the replay's map level
    /// (`\g__kernel_prg_map_int` relative to its value before the match).
    fn once_init(&mut self, level: i32) -> Option<()> {
        self.two_empty = self.empty_success;
        self.start_pos = self.success_pos;
        self.match_success = false;
        self.curr_subs.iter_mut().for_each(|x| *x = 0);
        self.max_thread = 0;
        let ms = self.b.min_state;
        self.store_state(ms);
        self.curr_pos = self.start_pos - 1;
        self.curr_char = self.last_char_success;
        // \__regex_match_once_init_aux: and the replay's \tl_map_inline:nn
        self.begin_matched();
        self.last = LastCs::TlMap(level);
        Some(())
    }

    /// `\__regex_store_state:n` (its `\__regex_store_submatches:nn` is not
    /// disabled by `\__regex_disable_submatches:`).
    fn store_state(&mut self, st: i32) {
        let base = self.max_thread as usize * self.width + 1;
        if self.info.len() < base + self.width {
            self.info.resize(base + self.width, 0);
        }
        self.info[base] = i64::from(st);
        for (k, &v) in self.curr_subs.iter().enumerate() {
            self.info[base + 1 + k] = i64::from(v);
        }
        self.max_thread += 1;
    }

    /// `\__regex_match_one_token:nnN` for token `j`.
    fn one_token(&mut self, j: usize) -> Option<()> {
        self.step += 2;
        self.curr_pos += 1;
        self.last_char = self.curr_char;
        let t = self.input.toks[j];
        self.curr_tok = j;
        self.curr_char = t.ch;
        self.curr_cat = t.cat;
        // \tl_build_put_right:Ne \l__regex_matched_analysis_tl
        self.puts += 1;
        if self.puts >= 5 && 5u32.pow(self.puts.ilog(5)) == self.puts {
            self.last = LastCs::Matched(1 + self.puts.ilog(5));
        }
        // The threads, read before any runs.
        let n = self.max_thread as usize;
        let mut threads = std::mem::take(&mut self.threads);
        threads.clear();
        threads.extend_from_slice(&self.info[1..1 + n * self.width]);
        self.max_thread = 0;
        for k in 0..n {
            self.depth = 0;
            self.stack.clear();
            let th = &threads[k * self.width..(k + 1) * self.width];
            self.curr_state = th[0] as i32;
            if self.active_at(self.curr_state)? < self.step {
                for (d, &v) in self.curr_subs.iter_mut().zip(&th[1..]) {
                    *d = v as i32;
                }
                match self.use_state() {
                    Ok(()) => {}
                    Err(Stop::Break) => break,
                    Err(Stop::Unsure) => {
                        self.threads = threads;
                        return None;
                    }
                }
            }
        }
        self.fresh = false;
        self.threads = threads;
        Some(())
    }

    fn active_at(&self, st: i32) -> Option<i64> {
        self.active.get(usize::try_from(st).ok()?).copied()
    }

    /// `\__regex_use_state:`.
    fn use_state(&mut self) -> Result<(), Stop> {
        let st = self.curr_state;
        let i = usize::try_from(st).map_err(|_| Stop::Unsure)?;
        if i >= self.active.len() || i >= self.b.toks.len() {
            return Err(Stop::Unsure);
        }
        self.active[i] = self.step;
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(Stop::Unsure);
        }
        let b = self.b;
        for &a in &b.toks[i] {
            self.act(a)?;
        }
        self.depth -= 1;
        self.active[i] = self.step + 1;
        Ok(())
    }

    /// `\__regex_action_free_aux:nn`: the state and submatches are
    /// restored afterwards.
    fn free(&mut self, d: i32, group: bool) -> Result<(), Stop> {
        let saved_state = self.curr_state;
        let mark = self.stack.len();
        self.stack.extend_from_slice(&self.curr_subs);
        self.curr_state += d;
        let a = self.active_at(self.curr_state).ok_or(Stop::Unsure)?;
        if if group { a < self.step } else { a <= self.step } {
            self.use_state()?;
        }
        self.curr_state = saved_state;
        self.curr_subs.copy_from_slice(&self.stack[mark..]);
        self.stack.truncate(mark);
        Ok(())
    }

    fn act(&mut self, a: Act) -> Result<(), Stop> {
        match a {
            Act::Free(d) => self.free(d, false),
            Act::FreeGroup(d) => self.free(d, true),
            Act::Test(c, d) => {
                let class = &self.b.classes[c as usize];
                let t = self.items(&class.items)?;
                if t == class.positive {
                    self.store_state(self.curr_state + d);
                }
                Ok(())
            }
            Act::Submatch(k, begin) => {
                if self.submatches {
                    let g = (self.width - 1) / 2;
                    let idx = if begin { k as usize } else { k as usize + g };
                    if let Some(x) = self.curr_subs.get_mut(idx) {
                        *x = self.curr_pos;
                    }
                    // \__regex_action_submatch_aux:w's \prg_replicate:nn.
                    self.last = LastCs::ReplicateFirst(first_digit(idx));
                }
                Ok(())
            }
            Act::StartWildcard(w) => {
                self.fresh = true;
                self.free(1, false)?;
                self.fresh = false;
                if w {
                    self.store_state(self.curr_state);
                }
                Ok(())
            }
            Act::Success => {
                if self.two_empty && self.start_pos == self.curr_pos {
                    return Ok(());
                }
                self.match_success = true;
                self.empty_success = self.fresh;
                self.success_pos = self.curr_pos;
                self.last_char_success = self.last_char;
                self.begin_matched();
                self.success_subs.clone_from(&self.curr_subs);
                Err(Stop::Break)
            }
            Act::Assert(t, positive, d) => {
                let r = match t {
                    Test::A => self.last_char == -2,
                    Test::Z => self.curr_char == -2,
                    Test::G => self.curr_pos == self.start_pos,
                    Test::B => word(self.last_char) != word(self.curr_char),
                };
                if r == positive {
                    self.free(d, false)?;
                }
                Ok(())
            }
            Act::SetCase(k) => {
                self.case = i64::from(k);
                Ok(())
            }
            Act::K(d) => {
                if self.submatches
                    && let Some(x) = self.curr_subs.first_mut()
                {
                    *x = self.curr_pos;
                    self.last = LastCs::ReplicateFirst(0);
                }
                self.fresh = true;
                self.free(d, false)?;
                self.fresh = false;
                Ok(())
            }
        }
    }

    /// Whether one of `items` matches the current token.
    fn items(&mut self, items: &[Item]) -> Result<bool, Stop> {
        for it in items {
            if self.item(it)? {
                return Ok(true);
            }
        }
        Ok(false)
    }

    fn item(&mut self, it: &Item) -> Result<bool, Stop> {
        let c = self.curr_char;
        Ok(match it {
            Item::Eq(n) => *n == c,
            Item::Range(a, b) => *a <= c && c <= *b,
            Item::CEq(n) => *n == c || *n == case_changed(c),
            Item::CRange(a, b) => {
                let cc = case_changed(c);
                (*a <= c && c <= *b) || (*a <= cc && cc <= *b)
            }
            Item::Catcode(m, inner) => catcode_in(*m, self.curr_cat) && self.items(inner)?,
            Item::CatcodeRev(m, inner) => catcode_in(*m, self.curr_cat) && !self.items(inner)?,
            Item::Reverse(inner) => !self.items(inner)?,
            Item::Exact(cat, ch) => *cat == i32::from(self.curr_cat) && *ch == c,
            Item::ExactCs(names) => {
                if self.curr_cat != 0 {
                    false
                } else {
                    let name = &self.input.names[self.input.toks[self.curr_tok].name as usize];
                    if name.is_empty() {
                        return Err(Stop::Unsure);
                    }
                    names
                        .iter()
                        .any(|n| n == name && !n.contains(&u32::from(b' ')))
                }
            }
            Item::Any => c > -2,
        })
    }

    /// `\__regex_extract:` (with `\g__regex_success_bool` true).
    fn extract(&mut self) {
        let g = (self.width - 1) / 2;
        let z = self.submatch_int;
        self.zeroth = z;
        for _ in 0..g {
            let k = self.submatch_int;
            set_at(&mut self.sub_prev, k, 0);
            set_at(&mut self.sub_case, k, 0);
            self.submatch_int += 1;
        }
        set_at(&mut self.sub_prev, z, i64::from(self.start_pos));
        set_at(&mut self.sub_case, z, self.case);
        self.last = LastCs::ReplicateFirst(first_digit(g));
        for (k, &v) in self.success_subs.clone().iter().enumerate() {
            if k < g {
                set_at(&mut self.sub_begin, z + k as i32, i64::from(v));
            } else {
                set_at(&mut self.sub_end, z + (k - g) as i32, i64::from(v));
            }
        }
    }
}

/// The first digit of `n` (`\prg_replicate:nn`'s last `\csname`).
pub(super) fn first_digit(n: usize) -> u8 {
    n.to_string().as_bytes()[0] - b'0'
}

/// `\__regex_compute_case_changed_char:`.
fn case_changed(c: i32) -> i32 {
    match c {
        65..=90 => c + 32,
        97..=122 => c - 32,
        _ => c,
    }
}

/// `\__regex_prop_w:`.
fn word(c: i32) -> bool {
    matches!(c, 48..=57 | 65..=90 | 97..=122 | 95)
}

/// `\__regex_item_catcode:nT`'s test: `<mask> / \__regex_item_catcode:`
/// odd, the category's bit being `4^k` (none for the end marker).
fn catcode_in(mask: i32, cat: u8) -> bool {
    let bit: i32 = match cat {
        0 => 0x1,
        1 => 0x4,
        2 => 0x10,
        3 => 0x40,
        4 => 0x100,
        6 => 0x1000,
        7 => 0x4000,
        8 => 0x10000,
        10 => 0x100000,
        11 => 0x400000,
        12 => 0x1000000,
        13 => 0x4000000,
        _ => return false,
    };
    (mask / bit) & 1 != 0
}