retex-engine 1.3.0-alpha.2

//! l3regex's syntax: the escape loop (`\__regex_escape_use:nnnn`), the
//! regex compiler (`\__regex_compile:n`) and the replacement compiler
//! (`\__regex_replacement:n`), transcribed function by function so that
//! the compiled form is the one l3regex builds, and every path on which
//! l3regex issues a message is detected (the caller then declines and the
//! TeX code runs, with its message).
//!
//! The compiler produces the compiled regex as a list of [`C`] items, one
//! per token of the token list l3regex stores (`\l__regex_tmp_regex`, the
//! contents of a regex variable): the same list is obtained from a
//! variable compiled by TeX ([`from_tokens`]), and [`parse`] turns either
//! into the tree [`Node`] that the matcher builds its automaton from.

/// One step of `\__regex_escape_loop:N` over the detokenized string.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(super) enum Esc {
    /// A character not preceded by a backslash.
    Unescaped(u32),
    /// A character preceded by a backslash (not one of the escapes below).
    Escaped(u32),
    /// The character of `\a`, `\e`, `\f`, `\n`, `\r`, `\t`, `\x..`.
    Raw(u32),
}

/// `\__regex_escape_use:nnnn` on the characters of
/// `\__kernel_str_to_other_fast:n {<text>}`: unescaped spaces are dropped
/// (`\__regex_escape_ :w` is empty), `\a\e\f\n\r\t\x` give characters.
/// `None` for the paths that issue messages (trailing backslash, bad
/// `\x`) and for `\x` giving character 0.
pub(super) fn escape_loop(s: &[u32]) -> Option<Vec<Esc>> {
    let mut out = Vec::with_capacity(s.len());
    let mut i = 0;
    while i < s.len() {
        let c = s[i];
        i += 1;
        if c == u32::from(b'\\') {
            // `\__regex_escape_\:w`; a trailing backslash is an error.
            let d = *s.get(i)?;
            i += 1;
            let raw = match char::from_u32(d)? {
                'a' => 7,
                't' => 9,
                'n' => 10,
                'f' => 12,
                'r' => 13,
                'e' => 27,
                'x' => {
                    let v = escape_x(s, &mut i)?;
                    if v == 0 {
                        return None;
                    }
                    v
                }
                _ => {
                    out.push(Esc::Escaped(d));
                    continue;
                }
            };
            out.push(Esc::Raw(raw));
        } else if c != u32::from(b' ') {
            out.push(Esc::Unescaped(c));
        }
    }
    Some(out)
}

fn hex(c: u32) -> Option<u32> {
    char::from_u32(c)?.to_digit(16)
}

/// `\__regex_escape_x:w` and friends: `\x{<hex>}` (spaces allowed) or up
/// to two hex digits, spaces skipped before; no digit gives 0.
fn escape_x(s: &[u32], i: &mut usize) -> Option<u32> {
    while s.get(*i) == Some(&u32::from(b' ')) {
        *i += 1;
    }
    let Some(&c) = s.get(*i) else {
        return Some(0);
    };
    let mut v: u64 = 0;
    if c == u32::from(b'{') {
        *i += 1;
        loop {
            let c = *s.get(*i)?; // end: x-missing-rbrace
            *i += 1;
            if let Some(h) = hex(c) {
                v = v * 16 + u64::from(h);
                if v > 0x10_FFFF {
                    return None; // x-overflow (or TeX's own overflow)
                }
            } else if c == u32::from(b'}') {
                break;
            } else if c != u32::from(b' ') {
                return None; // x-missing-rbrace
            }
        }
        return Some(v as u32);
    }
    let Some(h) = hex(c) else {
        return Some(0);
    };
    *i += 1;
    v = u64::from(h);
    if let Some(h2) = s.get(*i).copied().and_then(hex) {
        *i += 1;
        v = v * 16 + u64::from(h2);
    }
    Some(v as u32)
}

/// `\__regex_char_if_special:NTF`: printable ASCII that is not a letter
/// or digit.
fn special(c: u32) -> bool {
    matches!(c, 32..=47 | 58..=64 | 91..=96 | 123..=126)
}

/// `\__regex_char_if_alphanumeric:NTF`.
pub(super) fn alnum(c: u32) -> bool {
    matches!(c, 48..=57 | 65..=90 | 97..=122)
}

/// The kind of group.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(super) enum GroupKind {
    /// `\__regex_group:nnnN`.
    Capture,
    /// `\__regex_group_no_capture:nnnN`.
    NoCapture,
    /// `\__regex_group_resetting:nnnN`.
    Resetting,
}

/// The tests of assertions.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(super) enum Test {
    /// `\__regex_A_test:` (start of the token list).
    A,
    /// `\__regex_G_test:` (start of the match attempt).
    G,
    /// `\__regex_Z_test:` (end).
    Z,
    /// `\__regex_b_test:` (word boundary).
    B,
}

/// The properties and POSIX classes (`\__regex_prop_d:`,
/// `\__regex_posix_alpha:`, …), by name.
pub(super) const PROPS: &[&str] = &[
    "__regex_prop_.:",
    "__regex_prop_d:",
    "__regex_prop_h:",
    "__regex_prop_s:",
    "__regex_prop_v:",
    "__regex_prop_w:",
    "__regex_prop_N:",
    "__regex_posix_alnum:",
    "__regex_posix_alpha:",
    "__regex_posix_ascii:",
    "__regex_posix_blank:",
    "__regex_posix_cntrl:",
    "__regex_posix_digit:",
    "__regex_posix_graph:",
    "__regex_posix_lower:",
    "__regex_posix_print:",
    "__regex_posix_punct:",
    "__regex_posix_space:",
    "__regex_posix_upper:",
    "__regex_posix_word:",
    "__regex_posix_xdigit:",
];

/// One token of a compiled regex.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(super) enum C {
    Branch,
    Class,
    Group(GroupKind),
    Assertion,
    K,
    True,
    False,
    Open,
    Close,
    /// A character (category 12): digits and `-` of numbers, the
    /// characters of control sequence names.
    Ch(u32),
    /// A number written by the compiler (stands for its digits).
    Num(i32),
    /// `\__regex_item_caseful_equal:n` (false) or `…caseless…` (true).
    ItemEq(bool),
    /// `\__regex_item_caseful_range:nn` or `…caseless…`.
    ItemRange(bool),
    ItemCatcode,
    ItemCatcodeRev,
    ItemReverse,
    ItemExact,
    ItemExactCs,
    ItemCs,
    /// A property, index in [`PROPS`].
    Prop(u8),
    Test(Test),
    ScanStop,
}

/// The value of `\c__regex_all_catcodes_int`.
pub(super) const ALL_CATCODES: i32 = 0x5515155;

/// The catcode masks, `\c__regex_catcode_<letter>_int`.
fn catcode_mask(c: u32) -> Option<i32> {
    Some(match char::from_u32(c)? {
        'C' => 0x1,
        'B' => 0x4,
        'E' => 0x10,
        'M' => 0x40,
        'T' => 0x100,
        'P' => 0x1000,
        'U' => 0x4000,
        'D' => 0x10000,
        'S' => 0x100000,
        'L' => 0x400000,
        'O' => 0x1000000,
        'A' => 0x4000000,
        _ => return None,
    })
}

/// The modes of `\l__regex_mode_int`.
const OUTER: i32 = 0;
const CATCODE: i32 = 2;
const CLASS: i32 = 3;
const CATCODE_IN_CLASS: i32 = 6;
const CS: i32 = -2;
const CS_IN_CLASS: i32 = -6;

/// One element of the stream `\__regex_compile:n` executes: the escape
/// loop's `\__regex_compile_special:N c`, `\__regex_compile_raw:N c`,
/// `\__regex_compile_escaped:N c`, and the `\prg_do_nothing:` pairs that
/// follow.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Lx {
    Special(u32),
    Raw(u32),
    Escaped(u32),
    End,
}

impl Lx {
    /// The character, as `\token_to_str:N` or `\if_charcode:w` see it
    /// (none for `\prg_do_nothing:`).
    fn ch(self) -> Option<u32> {
        match self {
            Lx::Special(c) | Lx::Raw(c) | Lx::Escaped(c) => Some(c),
            Lx::End => None,
        }
    }
}

/// What a TeX group of the compiler saves (all its variables are local).
struct Saved {
    mode: i32,
    catcodes: i32,
    default: i32,
    catcodes_bool: bool,
    group_level: i32,
    caseless: bool,
    build: Vec<C>,
}

struct Compiler {
    lx: Vec<Lx>,
    pos: usize,
    mode: i32,
    catcodes: i32,
    default: i32,
    catcodes_bool: bool,
    group_level: i32,
    /// `\__regex_item_equal:n` is `\__regex_item_caseless_equal:n`.
    caseless: bool,
    /// `\l__regex_build_tl`.
    build: Vec<C>,
    stack: Vec<Saved>,
}

/// `\__regex_compile:n` of a detokenized regex: the compiled regex, or
/// `None` where l3regex issues a message, and for `\u`.
pub(super) fn compile(s: &[u32]) -> Option<Vec<C>> {
    let esc = escape_loop(s)?;
    let mut lx: Vec<Lx> = esc
        .into_iter()
        .map(|e| match e {
            Esc::Unescaped(c) if special(c) => Lx::Special(c),
            Esc::Unescaped(c) | Esc::Raw(c) => Lx::Raw(c),
            Esc::Escaped(c) if alnum(c) => Lx::Escaped(c),
            Esc::Escaped(c) => Lx::Raw(c),
        })
        .collect();
    lx.extend([Lx::End, Lx::End]);
    let mut c = Compiler {
        lx,
        pos: 0,
        mode: OUTER,
        catcodes: ALL_CATCODES,
        default: ALL_CATCODES,
        catcodes_bool: false,
        group_level: 0,
        caseless: false,
        build: Vec::new(),
        stack: Vec::new(),
    };
    c.compile_w();
    c.mode = OUTER;
    while c.pos < c.lx.len() {
        let x = c.lx[c.pos];
        c.pos += 1;
        c.dispatch(x)?;
    }
    if c.mode == CATCODE || c.mode < OUTER {
        return None; // c-trailing, c-missing-rbrace
    }
    c.compile_end()
}

impl Compiler {
    fn peek(&self) -> Lx {
        self.lx.get(self.pos).copied().unwrap_or(Lx::End)
    }

    fn peek2(&self) -> Lx {
        self.lx.get(self.pos + 1).copied().unwrap_or(Lx::End)
    }

    fn put(&mut self, items: &[C]) {
        self.build.extend_from_slice(items);
    }

    fn group_begin(&mut self) {
        let build = std::mem::take(&mut self.build);
        self.stack.push(Saved {
            mode: self.mode,
            catcodes: self.catcodes,
            default: self.default,
            catcodes_bool: self.catcodes_bool,
            group_level: self.group_level,
            caseless: self.caseless,
            build,
        });
    }

    /// `\group_end:` after `\tl_build_end:N`: the group's build.
    fn group_end(&mut self) -> Vec<C> {
        let s = self.stack.pop().expect("group");
        self.mode = s.mode;
        self.catcodes = s.catcodes;
        self.default = s.default;
        self.catcodes_bool = s.catcodes_bool;
        self.group_level = s.group_level;
        self.caseless = s.caseless;
        std::mem::replace(&mut self.build, s.build)
    }

    fn in_class(&self) -> bool {
        self.mode & 1 != 0
    }

    fn in_cs(&self) -> bool {
        self.mode & 1 == 0 && self.mode < OUTER
    }

    fn in_class_or_catcode(&self) -> bool {
        self.mode & 1 != 0 || self.mode > OUTER
    }

    /// `\__regex_compile:w`.
    fn compile_w(&mut self) {
        self.group_begin();
        self.group_level = 0;
        self.default = ALL_CATCODES;
        self.catcodes = self.default;
        self.caseless = false;
        self.put(&[C::Branch, C::Open]);
    }

    /// `\__regex_compile_end:`: the compiled regex (the group's build).
    fn compile_end(&mut self) -> Option<Vec<C>> {
        if self.in_class() || self.group_level > 0 {
            return None; // missing-rbrack, missing-rparen
        }
        self.put(&[C::Close]);
        Some(self.group_end())
    }

    fn dispatch(&mut self, x: Lx) -> Option<()> {
        match x {
            Lx::Special(c) => self.special(c),
            Lx::Raw(c) => self.raw(c),
            Lx::Escaped(c) => self.escaped(c),
            Lx::End => Some(()),
        }
    }

    fn item_equal(&self, c: u32) -> [C; 4] {
        [
            C::ItemEq(self.caseless),
            C::Open,
            C::Num(c as i32),
            C::Close,
        ]
    }

    /// `\__regex_compile_special:N`.
    fn special(&mut self, c: u32) -> Option<()> {
        match char::from_u32(c)? {
            '.' => {
                if self.in_class() {
                    self.raw(c)
                } else {
                    self.one(&[C::Prop(0)])
                }
            }
            '^' => self.anchor_char(c, Test::A),
            '$' => self.anchor_char(c, Test::Z),
            ']' => self.rbrack(),
            '[' => self.lbrack(),
            '(' => self.lparen(),
            '|' => {
                if self.in_class() {
                    self.raw(c)
                } else {
                    self.put(&[C::Close, C::Branch, C::Open]);
                    Some(())
                }
            }
            ')' => {
                if self.in_class() {
                    self.raw(c)
                } else {
                    self.rparen()
                }
            }
            '{' => {
                if self.in_cs() {
                    None // cu-lbrace
                } else {
                    self.raw(c)
                }
            }
            '}' => {
                if self.in_cs() {
                    self.end_cs()
                } else {
                    self.raw(c)
                }
            }
            _ => self.raw(c),
        }
    }

    /// `\__regex_compile_escaped:N`.
    fn escaped(&mut self, c: u32) -> Option<()> {
        let prop = |name: char| -> Option<u8> {
            Some(match name {
                'd' => 1,
                'h' => 2,
                's' => 3,
                'v' => 4,
                'w' => 5,
                _ => return None,
            })
        };
        let ch = char::from_u32(c)?;
        match ch {
            'd' | 'h' | 's' | 'v' | 'w' => self.one(&[C::Prop(prop(ch)?)]),
            'D' | 'H' | 'S' | 'V' | 'W' => {
                let p = prop(ch.to_ascii_lowercase())?;
                self.one(&[C::ItemReverse, C::Open, C::Prop(p), C::Close])
            }
            'N' => self.one(&[C::Prop(6)]),
            'A' => self.anchor_letter(true, Test::A),
            'G' => self.anchor_letter(true, Test::G),
            'Z' | 'z' => self.anchor_letter(true, Test::Z),
            'b' => self.anchor_letter(true, Test::B),
            'B' => self.anchor_letter(false, Test::B),
            'c' => {
                if self.mode == OUTER || self.mode == CLASS {
                    self.c_test()
                } else {
                    None // c-bad-mode
                }
            }
            'u' => None,
            'K' => {
                if self.mode == OUTER {
                    self.put(&[C::K]);
                    Some(())
                } else {
                    None // bad-escape
                }
            }
            _ => self.raw(c),
        }
    }

    /// `\__regex_compile_raw:N`.
    fn raw(&mut self, c: u32) -> Option<()> {
        if self.in_class() && self.peek() == Lx::Special(u32::from(b'-')) {
            self.pos += 1;
            return self.range(c);
        }
        let item = self.item_equal(c);
        self.one(&item)
    }

    /// `\__regex_compile_one:n`.
    fn one(&mut self, item: &[C]) -> Option<()> {
        self.mode_quit_c();
        if !self.in_class() {
            self.put(&[C::Class, C::True, C::Open]);
        }
        if self.catcodes < ALL_CATCODES {
            let m = self.catcodes;
            self.put(&[C::ItemCatcode, C::Open, C::Num(m), C::Close, C::Open]);
            self.put(item);
            self.put(&[C::Close]);
        } else {
            self.put(item);
        }
        self.catcodes = self.default;
        if !self.in_class() {
            self.quantifier()?;
        }
        Some(())
    }

    /// `\__regex_mode_quit_c:`.
    fn mode_quit_c(&mut self) {
        if self.mode == CATCODE {
            self.mode = OUTER;
        } else if self.mode == CATCODE_IN_CLASS {
            self.mode = CLASS;
        }
    }

    /// `\__regex_compile_quantifier:w`.
    fn quantifier(&mut self) -> Option<()> {
        match self.peek() {
            Lx::Special(q) if q == u32::from(b'?') => {
                self.pos += 1;
                self.laziness(0, 1)
            }
            Lx::Special(q) if q == u32::from(b'*') => {
                self.pos += 1;
                self.laziness(0, -1)
            }
            Lx::Special(q) if q == u32::from(b'+') => {
                self.pos += 1;
                self.laziness(1, -1)
            }
            Lx::Special(q) if q == u32::from(b'{') => {
                self.pos += 1;
                self.braced()
            }
            _ => {
                self.put(&[
                    C::Close,
                    C::Open,
                    C::Num(1),
                    C::Close,
                    C::Open,
                    C::Num(0),
                    C::Close,
                    C::False,
                ]);
                Some(())
            }
        }
    }

    /// `\__regex_compile_quantifier_laziness:nnNN`.
    fn laziness(&mut self, min: i32, max: i32) -> Option<()> {
        let lazy = self.peek() == Lx::Special(u32::from(b'?'));
        if lazy {
            self.pos += 1;
        }
        self.put(&[
            C::Close,
            C::Open,
            C::Num(min),
            C::Close,
            C::Open,
            C::Num(max),
            C::Close,
            if lazy { C::True } else { C::False },
        ]);
        Some(())
    }

    /// `\__regex_get_digits:NTFw`: raw digits, as a TeX number.
    fn digits(&mut self) -> Option<Option<i32>> {
        let is_digit = |x: Lx| matches!(x, Lx::Raw(c) if (48..=57).contains(&c));
        if !is_digit(self.peek()) {
            return Some(None);
        }
        let mut v: i64 = 0;
        while is_digit(self.peek()) {
            let Lx::Raw(c) = self.peek() else {
                unreachable!()
            };
            v = v * 10 + i64::from(c - 48);
            if v > i64::from(i32::MAX) {
                return None; // number too big
            }
            self.pos += 1;
        }
        Some(Some(v as i32))
    }

    /// `\__regex_compile_quantifier_{:w` and its auxiliaries; the paths
    /// that abort (with the invalid-quantifier warning) or find a
    /// backwards quantifier decline.
    fn braced(&mut self) -> Option<()> {
        let a = self.digits()??;
        let rb = Lx::Special(u32::from(b'}'));
        match self.peek() {
            x if x == rb => {
                self.pos += 1;
                self.laziness(a, 0)
            }
            Lx::Special(c) if c == u32::from(b',') => {
                self.pos += 1;
                match self.digits()? {
                    Some(b) => {
                        if self.peek() != rb || a > b {
                            return None;
                        }
                        self.pos += 1;
                        self.laziness(a, b - a)
                    }
                    None => {
                        if self.peek() != rb {
                            return None;
                        }
                        self.pos += 1;
                        self.laziness(a, -1)
                    }
                }
            }
            _ => None,
        }
    }

    /// `\__regex_compile_range:Nw`, after `<c>-` in a class.
    fn range(&mut self, c: u32) -> Option<()> {
        let end = self.peek();
        let ok = match end {
            Lx::Raw(_) => true,
            Lx::Special(d) => d != u32::from(b']'),
            _ => false,
        };
        if !ok {
            return None; // range-missing-end
        }
        self.pos += 1;
        let d = end.ch()?;
        if c > d {
            return None; // range-backwards
        }
        if c == d {
            let item = self.item_equal(d);
            self.put(&item);
        } else {
            let cl = self.caseless;
            self.put(&[
                C::ItemRange(cl),
                C::Open,
                C::Num(c as i32),
                C::Close,
                C::Open,
                C::Num(d as i32),
                C::Close,
            ]);
        }
        Some(())
    }

    /// `^` and `$`.
    fn anchor_char(&mut self, c: u32, t: Test) -> Option<()> {
        if self.in_class_or_catcode() {
            return self.raw(c);
        }
        self.put(&[C::Assertion, C::True, C::Open, C::Test(t), C::Close]);
        Some(())
    }

    /// `\__regex_compile_anchor_letter:NNN`.
    fn anchor_letter(&mut self, pos: bool, t: Test) -> Option<()> {
        if self.in_class_or_catcode() {
            return None; // bad-escape
        }
        self.put(&[
            C::Assertion,
            if pos { C::True } else { C::False },
            C::Open,
            C::Test(t),
            C::Close,
        ]);
        Some(())
    }

    /// `\__regex_compile_]:`.
    fn rbrack(&mut self) -> Option<()> {
        if !self.in_class() {
            return self.raw(u32::from(b']'));
        }
        if self.mode > CATCODE_IN_CLASS {
            self.put(&[C::Close]);
        }
        self.mode = (self.mode - 15) / 13;
        if self.mode & 1 == 0 {
            self.quantifier()?;
        }
        Some(())
    }

    /// `\__regex_compile_[:`.
    fn lbrack(&mut self) -> Option<()> {
        if self.in_class() {
            return self.posix_test();
        }
        if self.mode > OUTER {
            // \__regex_compile_class_catcode:w
            let m = self.catcodes;
            if self.mode == CATCODE {
                self.put(&[C::Class, C::True, C::Open]);
            }
            self.catcodes = self.default;
            self.class(
                &[C::ItemCatcode, C::Open, C::Num(m), C::Close, C::Open],
                &[C::ItemCatcodeRev, C::Open, C::Num(m), C::Close, C::Open],
            )
        } else {
            self.class(
                &[C::Class, C::True, C::Open],
                &[C::Class, C::False, C::Open],
            )
        }
    }

    /// `\__regex_compile_class:TFNN` and `\__regex_compile_class:NN`.
    fn class(&mut self, t: &[C], f: &[C]) -> Option<()> {
        self.mode = format!("{}3", self.mode).parse().ok()?;
        if self.peek() == Lx::Special(u32::from(b'^')) {
            self.pos += 1;
            self.put(f);
        } else {
            self.put(t);
        }
        if self.peek().ch() == Some(u32::from(b']')) {
            self.pos += 1;
            return self.raw(u32::from(b']'));
        }
        Some(())
    }

    /// `\__regex_compile_class_posix_test:w`: `[` in a class.
    fn posix_test(&mut self) -> Option<()> {
        match self.peek() {
            Lx::Special(c) if c == u32::from(b':') => return self.posix(),
            Lx::Special(c) if c == u32::from(b'=') || c == u32::from(b'.') => {
                return None; // posix-unsupported
            }
            _ => {}
        }
        self.raw(u32::from(b'['))
    }

    /// `\__regex_compile_class_posix:NNNNw`, after `[:`.
    fn posix(&mut self) -> Option<()> {
        self.pos += 1; // the colon
        let positive = if self.peek() == Lx::Special(u32::from(b'^')) {
            self.pos += 1;
            false
        } else {
            true
        };
        let mut name = String::new();
        while let Lx::Raw(c) = self.peek() {
            name.push(char::from_u32(c)?);
            self.pos += 1;
        }
        if self.peek() != Lx::Special(u32::from(b':'))
            || self.peek2() != Lx::Special(u32::from(b']'))
        {
            return None; // posix-missing-close
        }
        self.pos += 2;
        let full = format!("__regex_posix_{name}:");
        let p = PROPS.iter().position(|&n| n == full)? as u8; // posix-unknown
        if positive {
            self.one(&[C::Prop(p)])
        } else {
            self.one(&[C::ItemReverse, C::Open, C::Prop(p), C::Close])
        }
    }

    /// `\__regex_compile_(:`.
    fn lparen(&mut self) -> Option<()> {
        if self.in_class() {
            return self.raw(u32::from(b'('));
        }
        if self.mode == CATCODE_IN_CLASS {
            return None; // c-lparen-in-class
        }
        if self.peek() == Lx::Special(u32::from(b'?')) {
            let what = self.peek2().ch().and_then(char::from_u32);
            match what {
                Some(':') => {
                    self.pos += 2;
                    self.group_begin_n(GroupKind::NoCapture);
                    Some(())
                }
                Some('|') => {
                    self.pos += 2;
                    self.group_begin_n(GroupKind::Resetting);
                    Some(())
                }
                Some('i') => {
                    self.pos += 2;
                    if self.peek() != Lx::Special(u32::from(b')')) {
                        return None; // unknown-option
                    }
                    self.pos += 1;
                    self.caseless = true;
                    Some(())
                }
                Some('-') => {
                    self.pos += 2;
                    if self.peek() != Lx::Raw(u32::from(b'i'))
                        || self.peek2() != Lx::Special(u32::from(b')'))
                    {
                        return None; // unknown-option
                    }
                    self.pos += 2;
                    self.caseless = false;
                    Some(())
                }
                _ => None, // special-group-unknown
            }
        } else {
            self.group_begin_n(GroupKind::Capture);
            Some(())
        }
    }

    /// `\__regex_compile_group_begin:N`.
    fn group_begin_n(&mut self, kind: GroupKind) {
        self.put(&[C::Group(kind), C::Open]);
        self.mode_quit_c();
        self.group_begin();
        self.default = self.catcodes;
        self.group_level += 1;
        self.put(&[C::Branch, C::Open]);
    }

    /// `\__regex_compile_group_end:`.
    fn rparen(&mut self) -> Option<()> {
        if self.group_level <= 0 {
            return None; // extra-rparen
        }
        self.put(&[C::Close]);
        let inner = self.group_end();
        self.build.extend(inner);
        self.catcodes = self.default;
        self.quantifier()
    }

    /// `\__regex_compile_c_test:NN`, after `\c`.
    fn c_test(&mut self) -> Option<()> {
        match self.peek() {
            Lx::Raw(c) => {
                let m = catcode_mask(c)?; // c-missing-category
                self.pos += 1;
                self.catcodes = m;
                self.mode = if self.mode == OUTER {
                    CATCODE
                } else {
                    CATCODE_IN_CLASS
                };
                if c == u32::from(b'C') {
                    // \__regex_compile_c_C:NN: `.` or `(` must follow.
                    match self.peek() {
                        Lx::Special(d) if d == u32::from(b'.') || d == u32::from(b'(') => {}
                        _ => return None, // c-C-invalid
                    }
                }
                Some(())
            }
            x => match x.ch().and_then(char::from_u32) {
                Some('[') => {
                    self.pos += 1;
                    self.c_lbrack()
                }
                Some('{') => {
                    self.pos += 1;
                    let m = self.mode;
                    self.compile_w();
                    self.mode = if m == OUTER { CS } else { CS_IN_CLASS };
                    Some(())
                }
                _ => None, // c-missing-category
            },
        }
    }

    /// `\__regex_compile_c_[:w`.
    fn c_lbrack(&mut self) -> Option<()> {
        self.mode = if self.mode == OUTER {
            CATCODE
        } else {
            CATCODE_IN_CLASS
        };
        self.catcodes = 0;
        if self.peek() == Lx::Special(u32::from(b'^')) {
            self.pos += 1;
            self.catcodes_bool = false;
        } else {
            self.catcodes_bool = true;
        }
        loop {
            match self.peek() {
                Lx::Raw(c) => {
                    let m = catcode_mask(c)?; // c-missing-rbrack
                    self.pos += 1;
                    if (self.catcodes / m) & 1 == 0 {
                        self.catcodes += m;
                    }
                }
                x if x.ch() == Some(u32::from(b']')) => {
                    self.pos += 1;
                    if !self.catcodes_bool {
                        self.catcodes = ALL_CATCODES - self.catcodes;
                    }
                    return Some(());
                }
                _ => return None, // c-missing-rbrack
            }
        }
    }

    /// `\__regex_compile_end_cs:`: `}` ending `\c{...}`.
    fn end_cs(&mut self) -> Option<()> {
        let regex = self.compile_end()?;
        let names = exact_cs_names(&regex);
        let item: Vec<C> = match names {
            Some(names) => {
                let mut v = vec![C::ItemExactCs, C::Open];
                for (k, n) in names.iter().enumerate() {
                    if k > 0 {
                        v.push(C::ScanStop);
                    }
                    v.extend(n.iter().map(|&c| C::Ch(c)));
                }
                v.push(C::Close);
                v
            }
            None => {
                let mut v = vec![C::ItemCs, C::Open];
                v.extend(regex);
                v.push(C::Close);
                v
            }
        };
        self.one(&item)
    }
}

/// `\__regex_compile_cs_aux:Nn`: when every branch of the regex inside
/// `\c{...}` is a sequence of single characters (positive classes of one
/// `\__regex_item_caseful_equal:n`, repeated exactly `{n}` times), the
/// names it matches; `None` otherwise (`\l__regex_cs_flag` raised).
fn exact_cs_names(regex: &[C]) -> Option<Vec<Vec<u32>>> {
    let tree = parse(regex)?;
    let mut names = Vec::new();
    for branch in tree {
        let mut name = Vec::new();
        for node in branch {
            let Node::Class {
                positive: true,
                items,
                min,
                max: 0,
                ..
            } = node
            else {
                return None;
            };
            let [Item::Eq(c)] = items[..] else {
                return None;
            };
            for _ in 0..min {
                name.push(c as u32);
            }
        }
        names.push(name);
    }
    Some(names)
}

/// A test on the current token.
#[derive(Clone, PartialEq, Eq, Debug)]
pub(super) enum Item {
    /// `\__regex_item_caseful_equal:n`.
    Eq(i32),
    Range(i32, i32),
    /// `\__regex_item_caseless_equal:n`.
    CEq(i32),
    CRange(i32, i32),
    /// `\__regex_item_catcode:nT`.
    Catcode(i32, Vec<Item>),
    /// `\__regex_item_catcode_reverse:nT`.
    CatcodeRev(i32, Vec<Item>),
    /// `\__regex_item_reverse:n`.
    Reverse(Vec<Item>),
    /// `\__regex_item_exact:nn {<catcode>} {<charcode>}`.
    Exact(i32, i32),
    /// `\__regex_item_exact_cs:n`: control sequence names.
    ExactCs(Vec<Vec<u32>>),
    /// `\__regex_prop_.:`: any token.
    Any,
}

/// A node of a compiled regex.
#[derive(Clone, PartialEq, Eq, Debug)]
pub(super) enum Node {
    /// `\__regex_class:NnnnN`.
    Class {
        positive: bool,
        items: Vec<Item>,
        min: i32,
        max: i32,
        lazy: bool,
    },
    Group {
        kind: GroupKind,
        branches: Vec<Vec<Node>>,
        min: i32,
        max: i32,
        lazy: bool,
    },
    /// `\__regex_assertion:Nn`.
    Assert { positive: bool, test: Test },
    /// `\__regex_command_K:`.
    K,
}

/// The items of a property (`\__regex_prop_w:` is four tests, …).
fn prop_items(p: u8) -> Vec<Item> {
    let r = |a: u8, b: u8| Item::Range(i32::from(a), i32::from(b));
    let e = |a: u8| Item::Eq(i32::from(a));
    match PROPS[p as usize] {
        "__regex_prop_.:" => vec![Item::Any],
        "__regex_prop_d:" | "__regex_posix_digit:" => vec![r(b'0', b'9')],
        "__regex_prop_h:" | "__regex_posix_blank:" => vec![e(b' '), e(9)],
        "__regex_prop_s:" => vec![e(b' '), e(9), e(10), e(12), e(13)],
        "__regex_prop_v:" => vec![r(10, 13)],
        "__regex_prop_w:" | "__regex_posix_word:" => {
            vec![r(b'a', b'z'), r(b'A', b'Z'), r(b'0', b'9'), e(b'_')]
        }
        "__regex_prop_N:" => vec![Item::Reverse(vec![e(10)])],
        "__regex_posix_alnum:" => vec![r(b'a', b'z'), r(b'A', b'Z'), r(b'0', b'9')],
        "__regex_posix_alpha:" => vec![r(b'a', b'z'), r(b'A', b'Z')],
        "__regex_posix_ascii:" => vec![r(0, 127)],
        "__regex_posix_cntrl:" => vec![r(0, 31), e(127)],
        "__regex_posix_graph:" => vec![r(b'!', b'~')],
        "__regex_posix_lower:" => vec![r(b'a', b'z')],
        "__regex_posix_print:" => vec![r(b' ', b'~')],
        "__regex_posix_punct:" => vec![r(b'!', b'/'), r(b':', b'@'), r(b'[', b'`'), r(b'{', b'~')],
        "__regex_posix_space:" => vec![e(b' '), r(9, 13)],
        "__regex_posix_upper:" => vec![r(b'A', b'Z')],
        "__regex_posix_xdigit:" => vec![r(b'0', b'9'), r(b'A', b'F'), r(b'a', b'f')],
        _ => unreachable!(),
    }
}

/// A cursor over compiled tokens.
struct P<'a> {
    c: &'a [C],
    i: usize,
}

impl P<'_> {
    fn next(&mut self) -> Option<C> {
        let x = *self.c.get(self.i)?;
        self.i += 1;
        Some(x)
    }

    fn peek(&self) -> Option<C> {
        self.c.get(self.i).copied()
    }

    fn expect(&mut self, x: C) -> Option<()> {
        (self.next()? == x).then_some(())
    }

    fn bool(&mut self) -> Option<bool> {
        match self.next()? {
            C::True => Some(true),
            C::False => Some(false),
            _ => None,
        }
    }

    /// `{<integer>}`: a compiler number or the digits of `\int_use:N`.
    fn num(&mut self) -> Option<i32> {
        self.expect(C::Open)?;
        if let Some(C::Num(n)) = self.peek() {
            self.i += 1;
            self.expect(C::Close)?;
            return Some(n);
        }
        let mut neg = false;
        if self.peek() == Some(C::Ch(u32::from(b'-'))) {
            self.i += 1;
            neg = true;
        }
        let mut v: i64 = 0;
        let mut any = false;
        while let Some(C::Ch(d)) = self.peek() {
            if !(48..=57).contains(&d) {
                return None;
            }
            v = v * 10 + i64::from(d - 48);
            if v > i64::from(i32::MAX) {
                return None;
            }
            any = true;
            self.i += 1;
        }
        self.expect(C::Close)?;
        any.then_some(if neg { -(v as i32) } else { v as i32 })
    }

    fn regex(&mut self) -> Option<Vec<Vec<Node>>> {
        let mut branches = Vec::new();
        while self.peek() == Some(C::Branch) {
            self.i += 1;
            self.expect(C::Open)?;
            let mut nodes = Vec::new();
            while self.peek() != Some(C::Close) {
                nodes.push(self.node()?);
            }
            self.i += 1;
            branches.push(nodes);
        }
        Some(branches)
    }

    fn node(&mut self) -> Option<Node> {
        Some(match self.next()? {
            C::Class => {
                let positive = self.bool()?;
                self.expect(C::Open)?;
                let items = self.items()?;
                self.expect(C::Close)?;
                let min = self.num()?;
                let max = self.num()?;
                let lazy = self.bool()?;
                Node::Class {
                    positive,
                    items,
                    min,
                    max,
                    lazy,
                }
            }
            C::Group(kind) => {
                self.expect(C::Open)?;
                let branches = self.regex()?;
                self.expect(C::Close)?;
                let min = self.num()?;
                let max = self.num()?;
                let lazy = self.bool()?;
                Node::Group {
                    kind,
                    branches,
                    min,
                    max,
                    lazy,
                }
            }
            C::Assertion => {
                let positive = self.bool()?;
                self.expect(C::Open)?;
                let C::Test(test) = self.next()? else {
                    return None;
                };
                self.expect(C::Close)?;
                Node::Assert { positive, test }
            }
            C::K => Node::K,
            _ => return None,
        })
    }

    fn items(&mut self) -> Option<Vec<Item>> {
        let mut items = Vec::new();
        loop {
            match self.peek()? {
                C::Close => return Some(items),
                C::ItemEq(cl) => {
                    self.i += 1;
                    let n = self.num()?;
                    items.push(if cl { Item::CEq(n) } else { Item::Eq(n) });
                }
                C::ItemRange(cl) => {
                    self.i += 1;
                    let a = self.num()?;
                    let b = self.num()?;
                    items.push(if cl {
                        Item::CRange(a, b)
                    } else {
                        Item::Range(a, b)
                    });
                }
                C::ItemCatcode | C::ItemCatcodeRev => {
                    let rev = self.next()? == C::ItemCatcodeRev;
                    let m = self.num()?;
                    self.expect(C::Open)?;
                    let inner = self.items()?;
                    self.expect(C::Close)?;
                    items.push(if rev {
                        Item::CatcodeRev(m, inner)
                    } else {
                        Item::Catcode(m, inner)
                    });
                }
                C::ItemReverse => {
                    self.i += 1;
                    self.expect(C::Open)?;
                    let inner = self.items()?;
                    self.expect(C::Close)?;
                    items.push(Item::Reverse(inner));
                }
                C::ItemExact => {
                    self.i += 1;
                    let a = self.num()?;
                    let b = self.num()?;
                    items.push(Item::Exact(a, b));
                }
                C::ItemExactCs => {
                    self.i += 1;
                    self.expect(C::Open)?;
                    let mut names = vec![Vec::new()];
                    loop {
                        match self.next()? {
                            C::Close => break,
                            C::ScanStop => names.push(Vec::new()),
                            C::Ch(c) => names.last_mut()?.push(c),
                            _ => return None,
                        }
                    }
                    items.push(Item::ExactCs(names));
                }
                C::Prop(p) => {
                    self.i += 1;
                    items.extend(prop_items(p));
                }
                // \__regex_item_cs:n (a regex for the name) is not
                // handled natively.
                _ => return None,
            }
        }
    }
}

/// The tree of a compiled regex: its branches.
pub(super) fn parse(c: &[C]) -> Option<Vec<Vec<Node>>> {
    let mut p = P { c, i: 0 };
    let r = p.regex()?;
    (p.i == c.len()).then_some(r)
}

/// The names of the control sequences of compiled regexes, in the order
/// of [`from_tokens`]'s table.
pub(super) const CS_NAMES: &[&str] = &[
    "__regex_branch:n",
    "__regex_class:NnnnN",
    "__regex_group:nnnN",
    "__regex_group_no_capture:nnnN",
    "__regex_group_resetting:nnnN",
    "__regex_assertion:Nn",
    "__regex_command_K:",
    "c_true_bool",
    "c_false_bool",
    "__regex_item_caseful_equal:n",
    "__regex_item_caseless_equal:n",
    "__regex_item_caseful_range:nn",
    "__regex_item_caseless_range:nn",
    "__regex_item_catcode:nT",
    "__regex_item_catcode_reverse:nT",
    "__regex_item_reverse:n",
    "__regex_item_exact:nn",
    "__regex_item_exact_cs:n",
    "__regex_item_cs:n",
    "__regex_A_test:",
    "__regex_G_test:",
    "__regex_Z_test:",
    "__regex_b_test:",
    "scan_stop:",
];

/// The compiled-regex item of the control sequence at index `k` of
/// [`CS_NAMES`] followed by [`PROPS`].
pub(super) fn cs_item(k: usize) -> C {
    match k {
        0 => C::Branch,
        1 => C::Class,
        2 => C::Group(GroupKind::Capture),
        3 => C::Group(GroupKind::NoCapture),
        4 => C::Group(GroupKind::Resetting),
        5 => C::Assertion,
        6 => C::K,
        7 => C::True,
        8 => C::False,
        9 => C::ItemEq(false),
        10 => C::ItemEq(true),
        11 => C::ItemRange(false),
        12 => C::ItemRange(true),
        13 => C::ItemCatcode,
        14 => C::ItemCatcodeRev,
        15 => C::ItemReverse,
        16 => C::ItemExact,
        17 => C::ItemExactCs,
        18 => C::ItemCs,
        19 => C::Test(Test::A),
        20 => C::Test(Test::G),
        21 => C::Test(Test::Z),
        22 => C::Test(Test::B),
        23 => C::ScanStop,
        k => C::Prop((k - CS_NAMES.len()) as u8),
    }
}

// ----- the replacement text ----------------------------------------------

/// One piece of a compiled replacement text.
#[derive(Clone, PartialEq, Eq, Debug)]
pub(super) enum Piece {
    /// A character with its category: `(catcode, charcode)`; category 13
    /// is the active character, category 0 the single-character control
    /// sequence of `\cC`.
    Char(u8, u32),
    /// `\0`…`\9`, `\g{<n>}`.
    Sub(u32),
    /// `\c{<name>}`.
    Cs(Vec<u32>),
    /// `\u{<name>}`.
    Var(Vec<u32>),
}

/// What [`compile_replacement`] produces.
pub(super) struct Replacement {
    pub pieces: Vec<Piece>,
    /// The submatches in `\g__regex_balance_tl` (outside control sequence
    /// names), as the digits l3regex writes, in order.
    pub balance_subs: Vec<Vec<u32>>,
    /// `\l__regex_balance_int` at the end: begin-group minus end-group
    /// characters.
    pub balance: i32,
}

/// The replacement stream: the escape loop's
/// `\__regex_replacement_rbrace:N`, `…_lbrace:N`, `…_normal:n`,
/// `…_escaped:N`, then `\prg_do_nothing:`.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Rx {
    Normal(u32),
    Lbrace(u32),
    Rbrace(u32),
    Escaped(u32),
    End,
}

impl Rx {
    fn ch(self) -> Option<u32> {
        match self {
            Rx::Normal(c) | Rx::Lbrace(c) | Rx::Rbrace(c) | Rx::Escaped(c) => Some(c),
            Rx::End => None,
        }
    }
}

/// `\__regex_replacement:n` of a detokenized replacement text, for a
/// regex with `groups` capturing groups (`\l__regex_capturing_group_int`);
/// `catcode` gives the current category codes. `None` where l3regex
/// issues a message, and for category groups `\cX(…)`, submatches and
/// `\c`/`\u` inside control sequence names.
pub(super) fn compile_replacement(
    s: &[u32],
    groups: u32,
    catcode: &dyn Fn(u32) -> u8,
) -> Option<Replacement> {
    let mut rx: Vec<Rx> = escape_loop(s)?
        .into_iter()
        .map(|e| match e {
            Esc::Unescaped(c) if c == u32::from(b'}') => Rx::Rbrace(c),
            Esc::Unescaped(c) if c == u32::from(b'{') => Rx::Lbrace(c),
            Esc::Unescaped(c) | Esc::Raw(c) => Rx::Normal(c),
            Esc::Escaped(c) => Rx::Escaped(c),
        })
        .collect();
    rx.push(Rx::End);
    let mut r = Replacement {
        pieces: Vec::new(),
        balance_subs: Vec::new(),
        balance: 0,
    };
    // Inside \c{...} or \u{...}: (is \u, name so far).
    let mut cs: Option<(bool, Vec<u32>)> = None;
    let mut i = 0;
    let next = |i: &mut usize| -> Rx {
        let x = rx.get(*i).copied().unwrap_or(Rx::End);
        *i += 1;
        x
    };
    while i < rx.len() {
        let x = next(&mut i);
        match x {
            Rx::End => {}
            Rx::Normal(c) => normal(&mut r, &mut cs, c, catcode)?,
            Rx::Lbrace(c) => {
                if cs.is_some() {
                    return None; // cu-lbrace
                }
                normal(&mut r, &mut cs, c, catcode)?;
            }
            Rx::Rbrace(c) => match cs.take() {
                Some((u, name)) => {
                    if name.is_empty() {
                        return None;
                    }
                    r.pieces
                        .push(if u { Piece::Var(name) } else { Piece::Cs(name) });
                }
                None => normal(&mut r, &mut cs, c, catcode)?,
            },
            Rx::Escaped(c) => match char::from_u32(c)? {
                'g' => {
                    if next(&mut i) == Rx::Lbrace(u32::from(b'{')) {
                        let mut v: i64 = 0;
                        let mut any = false;
                        loop {
                            match next(&mut i) {
                                Rx::Normal(d) if (48..=57).contains(&d) => {
                                    v = v * 10 + i64::from(d - 48);
                                    if v > i64::from(i32::MAX) {
                                        return None;
                                    }
                                    any = true;
                                }
                                Rx::Rbrace(_) if any => break,
                                _ => return None, // replacement-g
                            }
                        }
                        let digits = v.to_string().bytes().map(u32::from).collect();
                        submatch(&mut r, &cs, v as u32, digits, groups)?;
                    } else {
                        return None;
                    }
                }
                'c' => match next(&mut i) {
                    Rx::Normal(k) if replacement_category(k) => {
                        let y = next(&mut i);
                        let Some(ch) = y.ch() else {
                            return None; // replacement-catcode-end
                        };
                        if cs.is_some() {
                            return None; // replacement-catcode-in-cs
                        }
                        if y == Rx::Normal(u32::from(b'(')) {
                            return None; // category groups: not native
                        }
                        if let Rx::Escaped(e) = y
                            && alnum(e)
                        {
                            return None; // replacement-catcode-escaped
                        }
                        cat_char(&mut r, k, ch)?;
                    }
                    Rx::Lbrace(_) => {
                        if cs.is_some() {
                            return None;
                        }
                        cs = Some((false, Vec::new()));
                    }
                    _ => return None, // replacement-c
                },
                'u' => {
                    if !matches!(next(&mut i), Rx::Lbrace(_)) || cs.is_some() {
                        return None;
                    }
                    cs = Some((true, Vec::new()));
                }
                d @ '0'..='9' => {
                    submatch(&mut r, &cs, d as u32 - 48, vec![d as u32], groups)?;
                }
                _ => normal(&mut r, &mut cs, c, catcode)?,
            },
        }
    }
    if cs.is_some() {
        return None; // replacement-missing-rbrace
    }
    Some(r)
}

/// Whether `\__regex_replacement_c_<k>:w` exists.
fn replacement_category(k: u32) -> bool {
    matches!(
        char::from_u32(k),
        Some('A' | 'B' | 'C' | 'D' | 'E' | 'L' | 'M' | 'O' | 'P' | 'S' | 'T' | 'U')
    )
}

/// `\__regex_replacement_put_submatch:n`.
fn submatch(
    r: &mut Replacement,
    cs: &Option<(bool, Vec<u32>)>,
    k: u32,
    digits: Vec<u32>,
    groups: u32,
) -> Option<()> {
    if k >= groups || cs.is_some() {
        return None; // submatch-too-big; submatches in names: not native
    }
    r.pieces.push(Piece::Sub(k));
    r.balance_subs.push(digits);
    Some(())
}

/// `\__regex_replacement_normal:n` (no category group open).
fn normal(
    r: &mut Replacement,
    cs: &mut Option<(bool, Vec<u32>)>,
    c: u32,
    catcode: &dyn Fn(u32) -> u8,
) -> Option<()> {
    if let Some((_, name)) = cs {
        name.push(c);
        return Some(());
    }
    // \__regex_replacement_normal_aux:N
    let k = if c == u32::from(b' ') {
        b'S'
    } else {
        match catcode(c) {
            1 => b'B',
            2 => b'E',
            3 => b'M',
            4 => b'T',
            6 => b'P',
            7 => b'U',
            8 => b'D',
            10 => b'S',
            11 => b'L',
            13 => b'A',
            _ => b'O',
        }
    };
    cat_char(r, u32::from(k), c)
}

/// `\__regex_replacement_c_<k>:w ? <c>`.
fn cat_char(r: &mut Replacement, k: u32, c: u32) -> Option<()> {
    let cat = match char::from_u32(k)? {
        'A' => 13,
        'B' => {
            r.balance += 1;
            1
        }
        'C' => 0,
        'D' => 8,
        'E' => {
            r.balance -= 1;
            2
        }
        'L' => 11,
        'M' => 3,
        'O' => 12,
        'P' => 6,
        'S' => {
            if c == 0 {
                return None; // replacement-null-space
            }
            10
        }
        'T' => 4,
        'U' => 7,
        _ => return None,
    };
    r.pieces.push(Piece::Char(cat, c));
    Some(())
}

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

    fn s(x: &str) -> Vec<u32> {
        x.chars().map(|c| c as u32).collect()
    }

    #[test]
    fn simple_class_and_group() {
        let c = compile(&s("([a-z]+)\\ (\\w)")).unwrap();
        let t = parse(&c).unwrap();
        assert_eq!(t.len(), 1);
        assert_eq!(t[0].len(), 3);
        assert!(matches!(
            &t[0][0],
            Node::Group {
                kind: GroupKind::Capture,
                ..
            }
        ));
        assert!(matches!(
            &t[0][1],
            Node::Class {
                positive: true,
                min: 1,
                max: 0,
                ..
            }
        ));
    }

    #[test]
    fn exact_cs() {
        let c = compile(&s("\\c{alpha|beta}")).unwrap();
        let t = parse(&c).unwrap();
        let Node::Class { items, .. } = &t[0][0] else {
            panic!()
        };
        assert_eq!(items, &vec![Item::ExactCs(vec![s("alpha"), s("beta")])]);
    }

    #[test]
    fn errors_decline() {
        for bad in ["(", "[a", "a{2,1}", "\\", "a{2", "\\cX", "[[:foo:]]", ")"] {
            assert!(compile(&s(bad)).is_none(), "{bad}");
        }
    }

    #[test]
    fn catcode_classes() {
        let c = compile(&s("\\cB. [^\\cE.]* \\cE.")).unwrap();
        let t = parse(&c).unwrap();
        assert_eq!(t[0].len(), 3);
        let Node::Class {
            positive: false,
            items,
            max: -1,
            ..
        } = &t[0][1]
        else {
            panic!("{:?}", t[0][1])
        };
        assert_eq!(items, &vec![Item::Catcode(0x10, vec![Item::Any])]);
    }
}