retex-engine 1.3.0

//! expl3's regular expressions (l3regex), natively.
//!
//! l3regex compiles a regex into token registers and matches it token by
//! token with TeX macros (an automaton whose states are `\toks`
//! registers, threads in intarrays); mhchem's `\ce`, codehigh and other
//! packages run millions of these macros. The native implementations
//! replace whole operations, the internal functions every public one goes
//! through (expl3 2026-01-19, `l3regex.dtx`):
//!
//! ```tex
//! \cs_new_protected:Npn \__regex_replace_all_aux:nnN #1#2#3
//!   {
//!     \group_begin:
//!       \__regex_multi_match:n { \__regex_extract: }
//!       #1
//!       \exp_args:No \__regex_match:n {#3}
//!       \exp_args:No \__regex_query_set:n {#3}
//!       #2
//!       …
//!     \__regex_group_end_replace:N #3
//!   }
//! ```
//!
//! with `#1` = `\__regex_build:n {<regex>}` or `\__regex_build:N
//! <regex var>`, `#2` = `\__regex_replacement:n {<replacement>}`; likewise
//! `\__regex_replace_once_aux:nnN`, `\__regex_if_match:nn` (behind
//! `\regex_match:nnTF` and friends: the native code sets
//! `\g__regex_success_bool` and the `\__regex_return:` that follows runs
//! as usual), `\__regex_count:nnN`, `\__regex_extract_once:nnN`,
//! `\__regex_extract_all:nnN` and `\__regex_split:nnN`. Their first
//! argument can also be `\__regex_case_build:e {\__regex_tl_odd_items:n
//! {<cases>}}` (`\regex_match_case:nn`, `\regex_replace_case_once:nN`,
//! `\regex_replace_case_all:nN`), with the replacement
//! `\__regex_replacement:e {\tl_item:nn {<cases>} {…}}` or
//! `\__regex_case_replacement:e {\__regex_tl_even_items:n {<cases>}}`;
//! then `\g__regex_case_int`, `\g__regex_case_balance_tl` and
//! `\g__regex_case_replacement_tl` are reproduced too.
//!
//! Everything inside the operation's group is local and vanishes at its
//! end, except what the native code reproduces:
//! - the result, by the code after the group, which the native code
//!   leaves in the input to run as usual (`\tl_set_eq:NN #3
//!   \g__regex_tmp_tl`, `\int_set:Nn #3 {<count>}`,
//!   `\__regex_extract_seq:N #3`);
//! - the global variables: `\g__regex_success_bool`, `\g__regex_tmp_tl`
//!   (the result; for operations without one, the regex as
//!   `\__kernel_str_to_other_fast:n` made it, or unchanged with a regex
//!   variable), `\g__regex_balance_tl` and the definition of
//!   `\__regex_replacement_balance_one_match:n` (replacements),
//!   `\g__tl_analysis_result_tl` (the analysis of the token list);
//! - the auxiliaries the mapping functions define globally:
//!   `\__int_map_<n>:w` (`\int_step_inline:nnn` of `\__regex_match_init:`),
//!   `\__tl_map_<n>:w` (the replays of `\__regex_match_once_init:`, one
//!   level per nested replay), `\__tl_analysis_map_inline_<n>:wNw`;
//! - the intarrays, through [`crate::LuaHost::intarray_set`]: the final
//!   values of every entry the TeX code writes (the matcher simulates
//!   l3regex's automaton exactly, see [`nfa`]);
//! - `\lastnamedcs`: the last `\csname` of the TeX code, which depends on
//!   the operation and, for matching only, on how many tokens
//!   `\tl_build_put_right:Ne` added to `\l__regex_matched_analysis_tl`
//!   since its last `\tl_build_begin:N` (a new level of
//!   `\l__regex_matched_analysis_tl'…` is created after 5, 25, 125, …
//!   additions, observed).
//!
//! The native code declines, and the TeX code runs, for anything it does
//! not reproduce: regex or replacement syntax on which l3regex issues a
//! message (or not covered: `\u` in regexes, `\c{<regex>}` that is not a
//! list of names, category groups `\cX(…)` in replacements), results or
//! submatches with unbalanced braces, `\peek_regex…`, tokens it cannot
//! classify, `\globaldefs`, a pending
//! `\afterassignment`, other definitions of the macros involved, and
//! when Lua's intarrays are not reachable natively (before the first
//! intarray function ran).

mod nfa;
mod syntax;

use std::cell::RefCell;
use std::rc::Rc;

use super::Native;
use super::deps::Deps;
use crate::Engine;
use crate::cmd::Cmd;
use crate::eqtb::{CodeKind, Loc, Meaning, Val};
use crate::hash::CsId;
use crate::primitives_gen::assign_int as ip;
use crate::scan::REG_OFFSET;
use crate::token::{Macro, Token, TokenList};
use nfa::{LastCs, Mode};
use syntax::{C, Piece};

/// The operations.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Op {
    IfMatch,
    Count,
    ExtractOnce,
    ExtractAll,
    Split,
    ReplaceOnce,
    ReplaceAll,
}

pub(super) const IF_MATCH: Native = Native {
    name: "__regex_if_match:nn",
    fingerprints: &[(12, 0xd4d2_9638_e528_a882)],
    executes: true,
    run: |e, a| run(e, a, Op::IfMatch),
};

pub(super) const COUNT: Native = Native {
    name: "__regex_count:nnN",
    fingerprints: &[(26, 0x63c8_7509_6ff2_1daa)],
    executes: true,
    run: |e, a| run(e, a, Op::Count),
};

pub(super) const EXTRACT_ONCE: Native = Native {
    name: "__regex_extract_once:nnN",
    fingerprints: &[(18, 0xb4d2_f730_0312_9adc)],
    executes: true,
    run: |e, a| run(e, a, Op::ExtractOnce),
};

pub(super) const EXTRACT_ALL: Native = Native {
    name: "__regex_extract_all:nnN",
    fingerprints: &[(20, 0xb315_1cf5_fb28_f871)],
    executes: true,
    run: |e, a| run(e, a, Op::ExtractAll),
};

pub(super) const SPLIT: Native = Native {
    name: "__regex_split:nnN",
    fingerprints: &[(66, 0x6968_d900_3db8_07c2)],
    executes: true,
    run: |e, a| run(e, a, Op::Split),
};

pub(super) const REPLACE_ONCE: Native = Native {
    name: "__regex_replace_once_aux:nnN",
    fingerprints: &[(47, 0xb4f6_3e90_c35d_8b4c)],
    executes: true,
    run: |e, a| run(e, a, Op::ReplaceOnce),
};

pub(super) const REPLACE_ALL: Native = Native {
    name: "__regex_replace_all_aux:nnN",
    fingerprints: &[(53, 0x6901_b22d_1208_d76b)],
    executes: true,
    run: |e, a| run(e, a, Op::ReplaceAll),
};

// The macros the operations run (l3regex's, and the expl3 functions it
// uses whose effects the native code reproduces), in four groups checked
// as the operation needs them. Left out: those l3regex redefines while
// it runs (`\__regex_tmp:w`, `\__regex_item_equal:n`, …) or globally
// (`\__regex_replacement_balance_one_match:n`), and variables.

/// The macros of every operation: building the automaton from a regex variable, matching, and the expl3 functions they use whose effects are reproduced.
const CORE_NAMES: &[&str] = &[
    "__regex_A_test:",
    "__regex_G_test:",
    "__regex_Z_test:",
    "__regex_action_cost:n",
    "__regex_action_free:n",
    "__regex_action_free_aux:nn",
    "__regex_action_free_group:n",
    "__regex_action_start_wildcard:N",
    "__regex_action_submatch:nN",
    "__regex_action_submatch_aux:w",
    "__regex_action_submatch_auxii:w",
    "__regex_action_submatch_auxiii:w",
    "__regex_action_success:",
    "__regex_assertion:Nn",
    "__regex_b_test:",
    "__regex_branch:n",
    "__regex_break_point:TF",
    "__regex_break_true:w",
    "__regex_build:N",
    "__regex_build_aux:NN",
    "__regex_build_new_state:",
    "__regex_build_transition_left:NNN",
    "__regex_build_transition_right:nNn",
    "__regex_build_transitions_laziness:NNNNN",
    "__regex_class:NnnnN",
    "__regex_class_repeat:n",
    "__regex_class_repeat:nN",
    "__regex_class_repeat:nnN",
    "__regex_command_K:",
    "__regex_compute_case_changed_char:",
    "__regex_count:nnN",
    "__regex_curr_cs_to_str:",
    "__regex_disable_submatches:",
    "__regex_group:nnnN",
    "__regex_group_aux:nnnnN",
    "__regex_group_no_capture:nnnN",
    "__regex_group_repeat:nn",
    "__regex_group_repeat:nnN",
    "__regex_group_repeat:nnnN",
    "__regex_group_repeat_aux:n",
    "__regex_group_resetting:nnnN",
    "__regex_group_resetting_loop:nnNn",
    "__regex_group_submatches:nNN",
    "__regex_if_match:nn",
    "__regex_int_eval:w",
    "__regex_item_caseful_equal:n",
    "__regex_item_caseful_range:nn",
    "__regex_item_caseless_equal:n",
    "__regex_item_caseless_range:nn",
    "__regex_item_catcode:",
    "__regex_item_catcode:nT",
    "__regex_item_catcode_reverse:nT",
    "__regex_item_cs:n",
    "__regex_item_exact:nn",
    "__regex_item_exact_cs:n",
    "__regex_item_reverse:n",
    "__regex_maplike_break:",
    "__regex_match:n",
    "__regex_match_init:",
    "__regex_match_once_init:",
    "__regex_match_once_init_aux:",
    "__regex_match_one_active:n",
    "__regex_match_one_token:nnN",
    "__regex_multi_match:n",
    "__regex_pop_lr_states:",
    "__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:",
    "__regex_prop_.:",
    "__regex_prop_N:",
    "__regex_prop_d:",
    "__regex_prop_h:",
    "__regex_prop_s:",
    "__regex_prop_v:",
    "__regex_prop_w:",
    "__regex_push_lr_states:",
    "__regex_return:",
    "__regex_sep:",
    "__regex_single_match:",
    "__regex_standard_escapechar:",
    "__regex_store_state:n",
    "__regex_store_submatches:nn",
    "__regex_toks_clear:N",
    "__regex_toks_memcpy:NNn",
    "__regex_toks_put_left:Ne",
    "__regex_toks_put_right:Ne",
    "__regex_toks_put_right:Nn",
    "__regex_toks_set:Nn",
    "__regex_toks_use:w",
    "__regex_use_i_delimit_by_q_recursion_stop:nw",
    "__regex_use_none_delimit_by_q_nil:w",
    "__regex_use_none_delimit_by_q_recursion_stop:w",
    "__regex_use_state:",
    "__regex_use_state_and_submatches:w",
    "tl_analysis_map_inline:nn",
    "__tl_analysis:n",
    "__tl_analysis_a:n",
    "__tl_analysis_a_loop:w",
    "__tl_analysis_a_type:w",
    "__tl_analysis_a_space:w",
    "__tl_analysis_a_space_test:w",
    "__tl_analysis_a_bgroup:w",
    "__tl_analysis_a_egroup:w",
    "__tl_analysis_a_group:nw",
    "__tl_analysis_a_group_aux:w",
    "__tl_analysis_a_group_auxii:w",
    "__tl_analysis_a_group_test:w",
    "__tl_analysis_a_store:",
    "__tl_analysis_a_safe:N",
    "__tl_analysis_a_cs:ww",
    "__tl_analysis_b:n",
    "__tl_analysis_b_loop:w",
    "__tl_analysis_b_normals:ww",
    "__tl_analysis_b_normal:wwN",
    "__tl_analysis_b_char:Nn",
    "__tl_analysis_b_char_aux:nww",
    "__tl_analysis_b_cs:Nww",
    "__tl_analysis_b_cs_test:ww",
    "__tl_analysis_b_special:w",
    "__tl_analysis_b_special_char:wN",
    "__tl_analysis_b_special_space:w",
    "__tl_analysis_map:Nn",
    "__tl_analysis_map:NwNw",
    "__tl_analysis_disable:n",
    "__tl_analysis_disable_char:N",
    "__tl_analysis_extract_charcode:",
    "__tl_analysis_extract_charcode_aux:w",
    "__tl_analysis_cs_space_count:NN",
    "__tl_analysis_cs_space_count:w",
    "__tl_analysis_cs_space_count_end:w",
    "tl_map_inline:nn",
    "int_step_inline:nnn",
    "int_step_inline:nnnn",
    "__int_step:NNnnnn",
    "int_step_function:nnnN",
    "int_step_function:nnN",
    "__int_step:w",
    "__int_step:Nw",
    "prg_replicate:nn",
    "__prg_replicate_first:N",
    "__prg_replicate:N",
    "__prg_replicate_",
    "__prg_replicate_first_0:n",
    "__prg_replicate_first_1:n",
    "__prg_replicate_0:n",
    "tl_build_begin:N",
    "__tl_build_begin:NN",
    "__tl_build_begin:NNN",
    "tl_build_put_right:Nn",
    "tl_build_put_right:Ne",
    "__tl_build_last:NNn",
    "__tl_build_put:nn",
    "__tl_build_put:nw",
    "tl_build_end:N",
    "__tl_build_end_loop:NN",
    "tl_build_get_intermediate:NN",
    "__tl_build_get:NNN",
    "__tl_build_get:w",
    "__tl_build_get_end:w",
    "__kernel_intarray_gset:Nnn",
    "__kernel_intarray_item:Nn",
    "__kernel_intarray_range_to_clist:Nnn",
    "__kernel_intarray_gset_range_from_clist:Nnn",
    "__intarray_gset:w",
    "__intarray_item:w",
    "__intarray_range_to_clist:w",
    "__intarray_gset_range:w",
    "bool_gset_true:N",
    "bool_gset_false:N",
    "bool_gset_eq:NN",
    "__kernel_tl_gset:Nx",
    "__kernel_tl_set:Nx",
    "cs_gset_protected:Npn",
    "exp_not:n",
    "__kernel_exp_not:w",
    "int_set:Nn",
    "c_true_bool",
    "c_false_bool",
    "c_zero_int",
    "c_one_int",
    "s__tl",
    "exp_after:wN",
    "if_false:",
    "fi:",
    "scan_stop:",
    "group_begin:",
    "group_end:",
];

/// The compiler and the escape loop (`\\__regex_build:n`).
const COMPILE_NAMES: &[&str] = &[
    "__regex_build:n",
    "__regex_build_aux:Nn",
    "__regex_char_if_alphanumeric:NTF",
    "__regex_char_if_special:NTF",
    "__regex_chk_c_allowed:T",
    "__regex_compile:n",
    "__regex_compile:w",
    "__regex_compile_abort_tokens:n",
    "__regex_compile_anchor_letter:NNN",
    "__regex_compile_c_C:NN",
    "__regex_compile_c_lbrack_add:N",
    "__regex_compile_c_lbrack_end:",
    "__regex_compile_c_lbrack_loop:NN",
    "__regex_compile_c_test:NN",
    "__regex_compile_class:NN",
    "__regex_compile_class:TFNN",
    "__regex_compile_class_catcode:w",
    "__regex_compile_class_normal:w",
    "__regex_compile_class_posix:NNNNw",
    "__regex_compile_class_posix_end:w",
    "__regex_compile_class_posix_loop:w",
    "__regex_compile_class_posix_test:w",
    "__regex_compile_cs_aux:NNnnnN",
    "__regex_compile_cs_aux:Nn",
    "__regex_compile_end:",
    "__regex_compile_end_cs:",
    "__regex_compile_escaped:N",
    "__regex_compile_group_begin:N",
    "__regex_compile_group_end:",
    "__regex_compile_lparen:w",
    "__regex_compile_one:n",
    "__regex_compile_quantifier:w",
    "__regex_compile_quantifier_abort:eNN",
    "__regex_compile_quantifier_braced_auxi:w",
    "__regex_compile_quantifier_braced_auxii:w",
    "__regex_compile_quantifier_braced_auxiii:w",
    "__regex_compile_quantifier_laziness:nnNN",
    "__regex_compile_quantifier_none:",
    "__regex_compile_range:Nw",
    "__regex_compile_raw:N",
    "__regex_compile_raw_error:N",
    "__regex_compile_special:N",
    "__regex_compile_special_group_i:w",
    "__regex_compile_.:",
    "__regex_compile_^:",
    "__regex_compile_$:",
    "__regex_compile_[:",
    "__regex_compile_]:",
    "__regex_compile_(:",
    "__regex_compile_):",
    "__regex_compile_|:",
    "__regex_compile_{:",
    "__regex_compile_}:",
    "__regex_compile_/d:",
    "__regex_compile_/D:",
    "__regex_compile_/h:",
    "__regex_compile_/H:",
    "__regex_compile_/s:",
    "__regex_compile_/S:",
    "__regex_compile_/v:",
    "__regex_compile_/V:",
    "__regex_compile_/w:",
    "__regex_compile_/W:",
    "__regex_compile_/N:",
    "__regex_compile_/A:",
    "__regex_compile_/G:",
    "__regex_compile_/Z:",
    "__regex_compile_/z:",
    "__regex_compile_/b:",
    "__regex_compile_/B:",
    "__regex_compile_/c:",
    "__regex_compile_/u:",
    "__regex_compile_/K:",
    "__regex_compile_c_[:w",
    "__regex_compile_c_{:w",
    "__regex_compile_quantifier_?:w",
    "__regex_compile_quantifier_*:w",
    "__regex_compile_quantifier_+:w",
    "__regex_compile_quantifier_{:w",
    "__regex_compile_special_group_::w",
    "__regex_compile_special_group_|:w",
    "__regex_compile_special_group_-:w",
    "__regex_escape_loop:N",
    "__regex_escape_use:nnnn",
    "__regex_escape_x:N",
    "__regex_escape_x_end:w",
    "__regex_escape_x_loop:N",
    "__regex_escape_x_loop_error:n",
    "__regex_escape_x_test:N",
    "__regex_escape_x_testii:N",
    "__regex_escape_\\:w",
    "__regex_escape_\\scan_stop::w",
    "__regex_escape_/\\scan_stop::w",
    "__regex_escape_ :w",
    "__regex_escape_/a:w",
    "__regex_escape_/e:w",
    "__regex_escape_/f:w",
    "__regex_escape_/n:w",
    "__regex_escape_/r:w",
    "__regex_escape_/t:w",
    "__regex_escape_/x:w",
    "__regex_get_digits:NTFw",
    "__regex_get_digits_loop:nw",
    "__regex_hexadecimal_use:NTF",
    "__regex_if_end_range:NNTF",
    "__regex_if_in_class:TF",
    "__regex_if_in_class_or_catcode:TF",
    "__regex_if_in_cs:TF",
    "__regex_if_raw_digit:NNTF",
    "__regex_if_within_catcode:TF",
    "__regex_mode_quit_c:",
    "__regex_two_if_eq:NNNNTF",
    "__kernel_str_to_other_fast:n",
    "__str_to_other_fast_loop:w",
    "__str_to_other_fast_end:w",
    "tl_to_str:n",
];

/// The replacements: the replacement compiler and the escape loop, the query functions, the end of the group.
const REPLACE_NAMES: &[&str] = &[
    "__regex_escape_loop:N",
    "__regex_escape_use:nnnn",
    "__regex_escape_x:N",
    "__regex_escape_x_end:w",
    "__regex_escape_x_loop:N",
    "__regex_escape_x_loop_error:n",
    "__regex_escape_x_test:N",
    "__regex_escape_x_testii:N",
    "__regex_escape_\\:w",
    "__regex_escape_\\scan_stop::w",
    "__regex_escape_/\\scan_stop::w",
    "__regex_escape_ :w",
    "__regex_escape_/a:w",
    "__regex_escape_/e:w",
    "__regex_escape_/f:w",
    "__regex_escape_/n:w",
    "__regex_escape_/r:w",
    "__regex_escape_/t:w",
    "__regex_escape_/x:w",
    "__regex_group_end_replace:N",
    "__regex_group_end_replace_check:n",
    "__regex_group_end_replace_check:w",
    "__regex_group_end_replace_try:",
    "__regex_intarray_item:NnF",
    "__regex_intarray_item_aux:nNF",
    "__regex_query_range:nn",
    "__regex_query_range_loop:ww",
    "__regex_query_set:n",
    "__regex_query_set_aux:nN",
    "__regex_query_submatch:n",
    "__regex_replace_all:nnN",
    "__regex_replace_all_aux:nnN",
    "__regex_replace_once:nnN",
    "__regex_replace_once_aux:nnN",
    "__regex_replacement:n",
    "__regex_replacement_apply:Nn",
    "__regex_replacement_c:w",
    "__regex_replacement_c_A:w",
    "__regex_replacement_c_B:w",
    "__regex_replacement_c_C:w",
    "__regex_replacement_c_D:w",
    "__regex_replacement_c_E:w",
    "__regex_replacement_c_L:w",
    "__regex_replacement_c_M:w",
    "__regex_replacement_c_O:w",
    "__regex_replacement_c_P:w",
    "__regex_replacement_c_S:w",
    "__regex_replacement_c_T:w",
    "__regex_replacement_c_U:w",
    "__regex_replacement_cat:NNN",
    "__regex_replacement_char:nNN",
    "__regex_replacement_cu_aux:Nw",
    "__regex_replacement_error:NNN",
    "__regex_replacement_escaped:N",
    "__regex_replacement_exp_not:N",
    "__regex_replacement_exp_not:V",
    "__regex_replacement_g:w",
    "__regex_replacement_g_digits:NN",
    "__regex_replacement_lbrace:N",
    "__regex_replacement_normal:n",
    "__regex_replacement_normal_aux:N",
    "__regex_replacement_put:n",
    "__regex_replacement_put_submatch:n",
    "__regex_replacement_put_submatch_aux:n",
    "__regex_replacement_rbrace:N",
    "__regex_replacement_set:n",
    "__regex_replacement_u:w",
    "__regex_submatch_balance:n",
    "tl_gclear:N",
    "tl_gput_right:Nn",
    "tl_gput_right:Ne",
    "cs_gset:Npn",
    "__kernel_str_to_other_fast:n",
    "__str_to_other_fast_loop:w",
    "__str_to_other_fast_end:w",
    "tl_to_str:n",
    "tl_set_eq:NN",
];

/// Extracting and splitting: the query functions, the end of the group, the flags.
const EXTRACT_NAMES: &[&str] = &[
    "__regex_extract:",
    "__regex_extract_all:nnN",
    "__regex_extract_aux:w",
    "__regex_extract_check:n",
    "__regex_extract_check:w",
    "__regex_extract_check_end:w",
    "__regex_extract_check_loop:w",
    "__regex_extract_once:nnN",
    "__regex_extract_seq:N",
    "__regex_extract_seq:NNn",
    "__regex_extract_seq_aux:n",
    "__regex_extract_seq_aux:ww",
    "__regex_extract_seq_loop:Nw",
    "__regex_group_end_extract_seq:N",
    "__regex_intarray_item:NnF",
    "__regex_intarray_item_aux:nNF",
    "__regex_query_range:nn",
    "__regex_query_range_loop:ww",
    "__regex_query_set:n",
    "__regex_query_set_aux:nN",
    "__regex_query_submatch:n",
    "__regex_split:nnN",
    "__regex_submatch_balance:n",
    "flag_clear:N",
    "__flag_clear:wN",
    "flag_height:N",
    "__flag_height_loop:wN",
    "__flag_height_end:wN",
    "seq_clear:N",
    "seq_put_right:No",
];

/// The regex cases (`\regex_match_case:nn`, `\regex_replace_case_…`).
const CASE_NAMES: &[&str] = &[
    "__regex_case_build:n",
    "__regex_case_build:e",
    "__regex_case_build_aux:Nn",
    "__regex_case_build_loop:n",
    "__regex_compile_use:n",
    "__regex_compile_use_aux:w",
    "__regex_tl_odd_items:n",
    "__regex_tl_even_items:n",
    "__regex_tl_even_items_loop:nn",
    "__regex_use_none_delimit_by_q_nil:w",
    "__regex_case_replacement:n",
    "__regex_case_replacement:e",
    "__regex_case_replacement_aux:n",
    "__regex_replacement:e",
    "tl_item:nn",
    "tl_if_single_token:nT",
    "token_to_meaning:N",
    "str_if_eq:nnT",
    "int_gincr:N",
    "int_gzero:N",
    "int_gset:Nn",
    "int_max:nn",
    "seq_pop:NN",
    "seq_push:No",
    "tl_map_tokens:nn",
    "tl_gset:Nn",
    "tl_gset:No",
    "tl_gset_eq:NN",
    "tl_gput_right:No",
];

thread_local! {
    static CASES: RefCell<Deps> = RefCell::new(Deps::new("l3regex cases", CASE_NAMES, &[0xe540_29c7_ed8b_b7f4]));
    static CORE: RefCell<Deps> = RefCell::new(Deps::new("l3regex", CORE_NAMES, &[0x99de_28d1_bf8d_3631]));
    static COMPILE: RefCell<Deps> =
        RefCell::new(Deps::new("l3regex compiler", COMPILE_NAMES, &[0x7e49_ce9c_8da6_4e15]));
    static REPLACE: RefCell<Deps> =
        RefCell::new(Deps::new("l3regex replacement", REPLACE_NAMES, &[0x9cc1_738b_0e52_8eef]));
    static EXTRACT: RefCell<Deps> =
        RefCell::new(Deps::new("l3regex extraction", EXTRACT_NAMES, &[0x01ea_7abd_cb89_f729]));
    static IDS: RefCell<Ids> = RefCell::new(Ids::default());
    static CACHE: RefCell<Cache> = RefCell::new(Cache::default());
}

/// The automata of regexes met before (mhchem matches the same regex
/// variables again and again): by detokenized regex, and by the
/// definition of the regex variable (kept, so its address stays its own).
#[derive(Default)]
struct Cache {
    by_text: std::collections::HashMap<Vec<u32>, Rc<nfa::Build>>,
    by_var: std::collections::HashMap<usize, (Rc<Macro>, Rc<nfa::Build>)>,
}

impl Cache {
    fn trim(&mut self) {
        if self.by_text.len() > 1000 {
            self.by_text.clear();
        }
        if self.by_var.len() > 1000 {
            self.by_var.clear();
        }
    }
}

/// The control sequences the native code reads or writes, by name
/// (looked up again while some are missing and the hash table grew).
#[derive(Default)]
struct Ids {
    ids: Rc<[Option<CsId>]>,
    hash_len: usize,
}

/// The names of [`Ids`]: first the compiled-regex vocabulary
/// ([`syntax::CS_NAMES`] then [`syntax::PROPS`]), then these.
const MORE: &[&str] = &[
    "__regex_build:n",
    "__regex_build:N",
    "__regex_replacement:n",
    "exp_not:n",
    "s__tl",
    "exp_after:wN",
    "if_false:",
    "fi:",
    "__regex_tmp:w",
    "tl_set_eq:NN",
    "g__regex_tmp_tl",
    "int_set:Nn",
    "__regex_extract_seq:N",
    "__regex_submatch_balance:n",
    "__regex_int_eval:w",
    "scan_stop:",
    "__regex_match_one_token:nnN",
    "__regex_query_set_aux:nN",
    "__kernel_intarray_gset:Nnn",
    "g__regex_state_active_intarray",
    "c_one_int",
    "g__regex_success_bool",
    "c_true_bool",
    "c_false_bool",
    "g__tl_analysis_result_tl",
    "g__regex_balance_tl",
    "__regex_replacement_balance_one_match:n",
    "g__kernel_prg_map_int",
    "l__regex_min_state_int",
    "l__regex_min_thread_int",
    "g__regex_case_int",
    "g__regex_thread_info_intarray",
    "g__regex_submatch_prev_intarray",
    "g__regex_submatch_begin_intarray",
    "g__regex_submatch_end_intarray",
    "g__regex_submatch_case_intarray",
    "g__regex_balance_intarray",
    "__intarray:w",
    "l__regex_end_flag0",
    "__intarray_gset:w",
    "__regex_case_build:e",
    "__regex_tl_odd_items:n",
    "__regex_tl_even_items:n",
    "__regex_replacement:e",
    "tl_item:nn",
    "__regex_case_replacement:e",
    "q__regex_nil",
    "if_case:w",
    "or:",
    "__kernel_intarray_item:Nn",
    "exp_not:N",
    "exp_not:c",
    "__regex_replacement_exp_not:N",
    "__regex_replacement_exp_not:V",
    "__regex_query_submatch:n",
    "cs:w",
    "cs_end:",
    "g__regex_case_replacement_tl",
    "g__regex_case_balance_tl",
];

/// Indices in [`Ids`] of the names of [`MORE`].
mod id {
    use super::syntax::{CS_NAMES, PROPS};
    const B: usize = CS_NAMES.len() + PROPS.len();
    pub const BUILD_N: usize = B;
    pub const BUILD_NN: usize = B + 1;
    pub const REPLACEMENT: usize = B + 2;
    pub const EXP_NOT: usize = B + 3;
    pub const S_TL: usize = B + 4;
    pub const EXP_AFTER: usize = B + 5;
    pub const IF_FALSE: usize = B + 6;
    pub const FI: usize = B + 7;
    pub const TMP_W: usize = B + 8;
    pub const TL_SET_EQ: usize = B + 9;
    pub const G_TMP_TL: usize = B + 10;
    pub const INT_SET: usize = B + 11;
    pub const EXTRACT_SEQ: usize = B + 12;
    pub const SUBMATCH_BALANCE: usize = B + 13;
    pub const INT_EVAL: usize = B + 14;
    pub const SCAN_STOP: usize = B + 15;
    pub const MATCH_ONE_TOKEN: usize = B + 16;
    pub const QUERY_SET_AUX: usize = B + 17;
    pub const INTARRAY_GSET: usize = B + 18;
    pub const STATE_ACTIVE: usize = B + 19;
    pub const C_ONE_INT: usize = B + 20;
    pub const SUCCESS_BOOL: usize = B + 21;
    pub const TRUE_BOOL: usize = B + 22;
    pub const FALSE_BOOL: usize = B + 23;
    pub const ANALYSIS_RESULT: usize = B + 24;
    pub const BALANCE_TL: usize = B + 25;
    pub const BALANCE_ONE: usize = B + 26;
    pub const PRG_MAP_INT: usize = B + 27;
    pub const MIN_STATE: usize = B + 28;
    pub const MIN_THREAD: usize = B + 29;
    pub const CASE_INT: usize = B + 30;
    /// The intarrays, in the order of [`super::Array`] (state_active is
    /// [`STATE_ACTIVE`]).
    pub const THREAD_INFO: usize = B + 31;
    pub const INTARRAY_MARKER: usize = B + 37;
    pub const END_FLAG0: usize = B + 38;
    pub const INTARRAY_GSET_W: usize = B + 39;
    pub const CASE_BUILD_E: usize = B + 40;
    pub const TL_ODD_ITEMS: usize = B + 41;
    pub const TL_EVEN_ITEMS: usize = B + 42;
    pub const REPLACEMENT_E: usize = B + 43;
    pub const TL_ITEM: usize = B + 44;
    pub const CASE_REPLACEMENT_E: usize = B + 45;
    pub const Q_NIL: usize = B + 46;
    pub const IF_CASE: usize = B + 47;
    pub const OR: usize = B + 48;
    pub const INTARRAY_ITEM: usize = B + 49;
    pub const EXP_NOT_N: usize = B + 50;
    pub const EXP_NOT_C: usize = B + 51;
    pub const REPL_EXP_NOT_N: usize = B + 52;
    pub const REPL_EXP_NOT_V: usize = B + 53;
    pub const QUERY_SUBMATCH: usize = B + 54;
    pub const CS_W: usize = B + 55;
    pub const CS_END: usize = B + 56;
    pub const CASE_REPLACEMENT_TL: usize = B + 57;
    pub const CASE_BALANCE_TL: usize = B + 58;
    pub const COUNT: usize = B + 59;
}

impl Ids {
    fn refresh(&mut self, e: &Engine) {
        if self.ids.len() == id::COUNT
            && (self.hash_len == e.hash.len() || self.ids.iter().all(Option::is_some))
        {
            return;
        }
        self.hash_len = e.hash.len();
        self.ids = syntax::CS_NAMES
            .iter()
            .chain(syntax::PROPS)
            .chain(MORE)
            .map(|n| e.hash.lookup(n.as_bytes()))
            .collect();
    }
}

fn why<T>(reason: &str) -> Option<T> {
    if super::debug() {
        eprintln!("[native] l3regex declines ({reason})");
    }
    None
}

/// The intarrays the operations write, in the order of their indices.
#[derive(Clone, Copy)]
enum Array {
    StateActive,
    ThreadInfo,
    SubPrev,
    SubBegin,
    SubEnd,
    SubCase,
    Balance,
}

/// What an operation does, worked out before anything changes.
struct Plan {
    /// Intarray writes: (array, first index, values).
    writes: Vec<(Array, i64, Vec<i64>)>,
    success: bool,
    /// `\g__regex_tmp_tl`, if set.
    tmp_tl: Option<Vec<Token>>,
    analysis: Vec<Token>,
    /// `\__tl_analysis_map_inline_<n>:wNw` has `\__regex_query_set_aux:nN`
    /// (else `\__regex_match_one_token:nnN`).
    query_set: bool,
    /// `\g__kernel_prg_map_int` and the replay levels above it.
    base: i32,
    replays: i32,
    /// `\g__regex_balance_tl` and the body of
    /// `\__regex_replacement_balance_one_match:n`.
    balance: Option<(Vec<Token>, Vec<Token>)>,
    last: Last,
    tail: Vec<Token>,
    /// `\g__regex_case_int`, after a regex case.
    case_int: Option<i64>,
    /// `\g__regex_case_balance_tl` and `\g__regex_case_replacement_tl`.
    case_tls: Option<(Vec<Token>, Vec<Token>)>,
}

/// `\lastnamedcs` afterwards.
enum Last {
    Cs(LastCs),
    EndFlag,
    ReplicateZero,
}

fn run(e: &mut Engine, args: &[TokenList], op: Op) -> bool {
    let Some(p) = plan(e, args, op) else {
        return false;
    };
    commit(e, p)
}

fn ids(e: &Engine) -> Rc<[Option<CsId>]> {
    IDS.with(|i| {
        let mut i = i.borrow_mut();
        i.refresh(e);
        i.ids.clone()
    })
}

/// The value of an integer register.
fn count(e: &Engine, cs: Option<CsId>) -> Option<i32> {
    let m = e.eqtb.meaning(cs?);
    if m.cmd != Cmd::AssignInt || m.chr < REG_OFFSET || m.mac.is_some() {
        return None;
    }
    Some(e.eqtb.count[(m.chr - REG_OFFSET) as usize].val)
}

/// The body of a parameterless macro.
fn body(e: &Engine, cs: CsId) -> Option<&[Token]> {
    let m = e.eqtb.meaning(cs);
    if !matches!(m.cmd, Cmd::Call | Cmd::LongCall) {
        return None;
    }
    let mac = m.mac.as_ref()?;
    if mac.tokens.first() != Some(&Token::END_MATCH) {
        return None;
    }
    Some(&mac.tokens[1..])
}

/// `\tl_to_str:n` with `\escapechar` 92 (`\__regex_standard_escapechar:`),
/// as characters.
fn detokenize(e: &mut Engine, toks: &[Token]) -> Vec<u32> {
    let ix = ip::ESCAPECHAR as usize;
    let saved = e.eqtb.int_par[ix].val;
    e.eqtb.int_par[ix].val = 92;
    let s = e.print_to_string(|e| e.show_token_list(toks, 0, toks.len(), i64::MAX));
    e.eqtb.int_par[ix].val = saved;
    crate::utf8x::chars(&s)
}

/// The tokens inside `<cs> {…}`, if `arg` is that.
fn braced_after(arg: &[Token], cs: Option<CsId>) -> Option<&[Token]> {
    let cs = cs?;
    if arg.len() < 3 || arg[0] != Token::cs(cs) {
        return None;
    }
    let open = arg[1];
    let close = arg[arg.len() - 1];
    if open.is_cs() || open.cmd_code() != Cmd::LeftBrace as u32 {
        return None;
    }
    if close.is_cs() || close.cmd_code() != Cmd::RightBrace as u32 {
        return None;
    }
    // The braces must match each other.
    let inner = &arg[2..arg.len() - 1];
    let mut depth = 0i32;
    for &t in inner {
        if !t.is_cs() {
            if t.cmd_code() == Cmd::LeftBrace as u32 {
                depth += 1;
            } else if t.cmd_code() == Cmd::RightBrace as u32 {
                depth -= 1;
                if depth < 0 {
                    return None;
                }
            }
        }
    }
    (depth == 0).then_some(inner)
}

/// A compiled regex as tokens ([`syntax::from_tokens`]'s reverse
/// direction is not needed): the items of a regex variable's body.
fn from_tokens(ids: &[Option<CsId>], toks: &[Token]) -> Option<Vec<C>> {
    let vocab = syntax::CS_NAMES.len() + syntax::PROPS.len();
    let mut out = Vec::with_capacity(toks.len());
    for &t in toks {
        if t.is_cs() {
            let k = ids[..vocab].iter().position(|&i| i == Some(t.cs_id()))?;
            out.push(syntax::cs_item(k));
        } else {
            match t.cmd_code() {
                c if c == Cmd::LeftBrace as u32 => out.push(C::Open),
                c if c == Cmd::RightBrace as u32 => out.push(C::Close),
                c if c == Cmd::OtherChar as u32 => out.push(C::Ch(t.chr())),
                _ => return None,
            }
        }
    }
    Some(out)
}

/// The tokens of `\__kernel_str_to_other_fast:n`: characters of category
/// 12, spaces included.
fn other_string(s: &[u32]) -> Vec<Token> {
    s.iter().map(|&c| Token::other(c)).collect()
}

/// The token list to match, analysed: `None` for tokens the analysis
/// would not classify as expected.
fn analyse(e: &Engine, toks: &[Token]) -> Option<nfa::Input> {
    let mut out = Vec::with_capacity(toks.len() + 1);
    let mut names = vec![Vec::new()];
    for &t in toks {
        if t.is_cs() {
            let id = t.cs_id();
            match e.hash.kind(id) {
                crate::hash::CsKind::Active(c) => out.push(nfa::Tok {
                    ch: *c as i32,
                    cat: 13,
                    name: 0,
                }),
                crate::hash::CsKind::Single(_)
                | crate::hash::CsKind::Multi
                | crate::hash::CsKind::Frozen => {
                    names.push(crate::utf8x::chars(e.hash.name(id)));
                    out.push(nfa::Tok {
                        ch: -1,
                        cat: 0,
                        name: (names.len() - 1) as u32,
                    });
                }
                // The null control sequence and internal ones: name 0
                // (the empty name: \c{...} tests decline).
                _ => out.push(nfa::Tok {
                    ch: -1,
                    cat: 0,
                    name: 0,
                }),
            }
        } else {
            let cat = t.cmd_code();
            if !matches!(cat, 1 | 2 | 3 | 4 | 6 | 7 | 8 | 10 | 11 | 12) {
                return why("token category");
            }
            out.push(nfa::Tok {
                ch: t.chr() as i32,
                cat: cat as u8,
                name: 0,
            });
        }
    }
    out.push(nfa::Tok {
        ch: -2,
        cat: 15,
        name: 0,
    });
    Some(nfa::Input { toks: out, names })
}

/// `\g__tl_analysis_result_tl` for `toks`.
fn analysis_result(ids: &[Option<CsId>], e: &Engine, toks: &[Token]) -> Option<Vec<Token>> {
    let cs = |k: usize| ids[k].map(Token::cs);
    let (exp_not, s_tl, exp_after, if_false, fi) = (
        cs(id::EXP_NOT)?,
        cs(id::S_TL)?,
        cs(id::EXP_AFTER)?,
        cs(id::IF_FALSE)?,
        cs(id::FI)?,
    );
    let other = |c: u8| Token::other(u32::from(c));
    let digits = |out: &mut Vec<Token>, n: i64| {
        out.extend(n.to_string().bytes().map(other));
    };
    let mut out = Vec::with_capacity(toks.len() * 8);
    // Whether a token other than a brace or a space, with character code
    // `{` or `}`, came before: `\__tl_analysis_disable_char:N` set its
    // \lccode to 32, and the brace in the representation of a brace is
    // lowercased (observed).
    let (mut seen_l, mut seen_r) = (false, false);
    for &t in toks {
        if !t.is_cs() && t.cmd_code() == Cmd::LeftBrace as u32 {
            let rb = Token::char(Cmd::RightBrace, if seen_r { 32 } else { 125 });
            out.extend([exp_after, t, if_false, rb, fi, s_tl, other(b'1')]);
            digits(&mut out, i64::from(t.chr()));
        } else if !t.is_cs() && t.cmd_code() == Cmd::RightBrace as u32 {
            let lb = Token::char(Cmd::LeftBrace, if seen_l { 32 } else { 123 });
            out.extend([if_false, lb, fi, t, s_tl, other(b'2')]);
            digits(&mut out, i64::from(t.chr()));
        } else if t == Token::SPACE {
            out.extend([
                exp_not,
                Token::LEFT_BRACE,
                Token::SPACE,
                Token::RIGHT_BRACE,
                s_tl,
                other(b'A'),
            ]);
            digits(&mut out, 32);
        } else {
            out.extend([exp_not, Token::LEFT_BRACE, t, Token::RIGHT_BRACE, s_tl]);
            let code = match (
                t.is_cs(),
                t.is_cs() && matches!(e.hash.kind(t.cs_id()), crate::hash::CsKind::Active(_)),
            ) {
                (false, _) => Some(t.chr()),
                (true, true) => match e.hash.kind(t.cs_id()) {
                    crate::hash::CsKind::Active(c) => Some(*c),
                    _ => None,
                },
                _ => None,
            };
            seen_l |= code == Some(123);
            seen_r |= code == Some(125);
            if t.is_cs() {
                match e.hash.kind(t.cs_id()) {
                    crate::hash::CsKind::Active(c) => {
                        out.push(other(b'D'));
                        digits(&mut out, i64::from(*c));
                    }
                    _ => {
                        out.push(other(b'0'));
                        digits(&mut out, -1);
                    }
                }
            } else {
                out.push(other(match t.cmd_code() {
                    12 => b'C',
                    11 => b'B',
                    3 => b'3',
                    4 => b'4',
                    7 => b'7',
                    8 => b'8',
                    10 => b'A',
                    _ => b'6',
                }));
                digits(&mut out, i64::from(t.chr()));
            }
        }
        out.push(s_tl);
    }
    Some(out)
}

/// `\__regex_query_range:nn a b`: the tokens at positions `a` to `b - 1`
/// (token `k` of the list is at position `k + 2`).
fn query_range(toks: &[Token], a: i64, b: i64, out: &mut Vec<Token>) {
    let lo = a.max(2);
    let hi = b.min(toks.len() as i64 + 2);
    for p in lo..hi {
        out.push(toks[(p - 2) as usize]);
    }
}

/// Whether braces in `toks` nest properly.
fn balanced(toks: &[Token]) -> bool {
    let mut d = 0i64;
    for &t in toks {
        if !t.is_cs() {
            if t.cmd_code() == Cmd::LeftBrace as u32 {
                d += 1;
            } else if t.cmd_code() == Cmd::RightBrace as u32 {
                d -= 1;
                if d < 0 {
                    return false;
                }
            }
        }
    }
    d == 0
}

/// The items of a token list as N-type arguments take them (`\tl_map_…`,
/// `\__regex_tl_even_items:n`, `\tl_item:nn`): spaces skipped, a braced
/// group without its braces, or a token.
fn items(toks: &[Token]) -> Option<Vec<&[Token]>> {
    let mut out = Vec::new();
    let mut i = 0;
    while i < toks.len() {
        let t = toks[i];
        if t == Token::SPACE {
            i += 1;
        } else if !t.is_cs() && t.cmd_code() == Cmd::LeftBrace as u32 {
            let mut depth = 0;
            let mut j = i;
            loop {
                let u = *toks.get(j)?;
                if !u.is_cs() && u.cmd_code() == Cmd::LeftBrace as u32 {
                    depth += 1;
                } else if !u.is_cs() && u.cmd_code() == Cmd::RightBrace as u32 {
                    depth -= 1;
                    if depth == 0 {
                        break;
                    }
                }
                j += 1;
            }
            out.push(&toks[i + 1..j]);
            i = j + 1;
        } else if !t.is_cs() && t.cmd_code() == Cmd::RightBrace as u32 {
            return None;
        } else {
            out.push(&toks[i..=i]);
            i += 1;
        }
    }
    Some(out)
}

/// [`regex`]'s result: the automaton, what compiling leaves in
/// `\g__regex_tmp_tl`, the list of a regex case.
type RegexArg = (Rc<nfa::Build>, Option<Vec<Token>>, Option<Vec<Token>>);

/// The automaton of the regex argument (`\__regex_build:n {<regex>}`,
/// `\__regex_build:N <variable>` or `\__regex_case_build:e
/// {\__regex_tl_odd_items:n {<cases>}}`), what compiling leaves in
/// `\g__regex_tmp_tl` (if anything), and the list of a regex case.
fn regex(e: &mut Engine, ids: &[Option<CsId>], arg: &[Token]) -> Option<RegexArg> {
    if let Some(inner) = braced_after(arg, ids[id::BUILD_N]) {
        if !COMPILE.with(|d| d.borrow_mut().check(e)) {
            return why("dependencies");
        }
        let s = detokenize(e, inner);
        let tmp = other_string(&s);
        if let Some(b) = CACHE.with(|c| c.borrow().by_text.get(&s).cloned()) {
            return Some((b, Some(tmp), None));
        }
        let Some(c) = syntax::compile(&s) else {
            return why("regex syntax");
        };
        let b = automaton(&c)?;
        CACHE.with(|c| {
            let mut c = c.borrow_mut();
            c.trim();
            c.by_text.insert(s, b.clone());
        });
        return Some((b, Some(tmp), None));
    }
    if arg.len() == 2 && Some(arg[0]) == ids[id::BUILD_NN].map(Token::cs) && arg[1].is_cs() {
        let m = e.eqtb.meaning(arg[1].cs_id());
        let Some(mac) = m
            .mac
            .clone()
            .filter(|_| matches!(m.cmd, Cmd::Call | Cmd::LongCall))
        else {
            return why("regex variable");
        };
        let key = Rc::as_ptr(&mac) as usize;
        let hit = CACHE.with(|c| {
            c.borrow()
                .by_var
                .get(&key)
                .filter(|(m, _)| Rc::ptr_eq(m, &mac))
                .map(|(_, b)| b.clone())
        });
        if let Some(b) = hit {
            return Some((b, None, None));
        }
        let Some(body) = body(e, arg[1].cs_id()) else {
            return why("regex variable");
        };
        let Some(c) = from_tokens(ids, body) else {
            return why("regex variable contents");
        };
        let b = automaton(&c)?;
        CACHE.with(|c| {
            let mut c = c.borrow_mut();
            c.trim();
            c.by_var.insert(key, (mac, b.clone()));
        });
        return Some((b, None, None));
    }
    // \__regex_case_build:e {\__regex_tl_odd_items:n {<list>}}
    let inner = braced_after(arg, ids[id::CASE_BUILD_E])?;
    let list = braced_after(inner, ids[id::TL_ODD_ITEMS])?;
    if !CASES.with(|d| d.borrow_mut().check(e)) {
        return why("dependencies");
    }
    if ids[id::Q_NIL].is_some_and(|q| list.contains(&Token::cs(q))) {
        return why("quark in the cases");
    }
    let all = items(list)?;
    let mut tmp = None;
    let mut trees = Vec::new();
    let branch = Token::cs(ids[0]?);
    for item in all.iter().step_by(2) {
        // \__regex_compile_use:n: a regex variable (whose meaning starts
        // with `macro:->\__regex_branch:n`), or a regex to compile.
        let var = match item {
            [t] if t.is_cs() => {
                let m = e.eqtb.meaning(t.cs_id());
                m.mac
                    .as_ref()
                    .filter(|mac| {
                        m.cmd == Cmd::Call
                            && !mac.protected
                            && mac.tokens.first() == Some(&Token::END_MATCH)
                            && mac.tokens.get(1) == Some(&branch)
                    })
                    .map(|mac| mac.tokens[1..].to_vec())
            }
            _ => None,
        };
        let c = match var {
            Some(body) => from_tokens(ids, &body)?,
            None => {
                if !COMPILE.with(|d| d.borrow_mut().check(e)) {
                    return why("dependencies");
                }
                let s = detokenize(e, item);
                tmp = Some(other_string(&s));
                let Some(c) = syntax::compile(&s) else {
                    return why("regex syntax");
                };
                c
            }
        };
        let Some(tree) = syntax::parse(&c) else {
            return why("compiled regex");
        };
        trees.push(tree);
    }
    let Some(b) = nfa::build_case(&trees, 1) else {
        return why("automaton size");
    };
    Some((Rc::new(b), tmp, Some(list.to_vec())))
}

/// The automaton of a compiled regex.
fn automaton(compiled: &[C]) -> Option<Rc<nfa::Build>> {
    let Some(tree) = syntax::parse(compiled) else {
        if super::debug() {
            eprintln!("[native] l3regex: cannot use {compiled:?}");
        }
        return why("compiled regex");
    };
    let Some(b) = nfa::build(&tree, 1) else {
        return why("automaton size");
    };
    Some(Rc::new(b))
}

fn plan(e: &mut Engine, args: &[TokenList], op: Op) -> Option<Plan> {
    if !CORE.with(|d| d.borrow_mut().check(e)) {
        return why("dependencies");
    }
    let group = match op {
        Op::ReplaceOnce | Op::ReplaceAll => Some(&REPLACE),
        Op::ExtractOnce | Op::ExtractAll | Op::Split => Some(&EXTRACT),
        Op::IfMatch | Op::Count => None,
    };
    if let Some(g) = group
        && !g.with(|d| d.borrow_mut().check(e))
    {
        return why("dependencies");
    }
    if e.eqtb.int(ip::GLOBALDEFS) != 0 || e.after_token.0 != 0 {
        return why("\\globaldefs or \\afterassignment");
    }
    let ids = ids(e);
    if count(e, ids[id::MIN_STATE]) != Some(1) || count(e, ids[id::MIN_THREAD]) != Some(0) {
        return why("state variables");
    }
    let base = count(e, ids[id::PRG_MAP_INT])?;
    let case = count(e, ids[id::CASE_INT])?;
    // `\l__regex_end_flag` must not be raised (\__regex_group_end_extract_seq:N).
    if let Some(f) = ids[id::END_FLAG0]
        && e.eqtb.meaning(f).cmd != Cmd::UndefinedCs
    {
        return why("flag");
    }
    // The regex.
    let Some((b, tmp_regex, case_list)) = regex(e, &ids, &args[0]) else {
        return why("regex argument");
    };
    let case = if case_list.is_some() { 0 } else { case };
    // The token list.
    let replace = matches!(op, Op::ReplaceOnce | Op::ReplaceAll);
    let toks: Vec<Token> = if replace {
        if args[2].len() != 1 || !args[2][0].is_cs() {
            return why("token list variable");
        }
        let Some(b) = body(e, args[2][0].cs_id()) else {
            return why("token list variable");
        };
        b.to_vec()
    } else {
        args[1].to_vec()
    };
    if toks
        .iter()
        .any(|t| !t.is_cs() && t.cmd_code() == Cmd::CarRet as u32)
    {
        return why("parameter tokens");
    }
    let input = analyse(e, &toks)?;
    let mode = match op {
        Op::IfMatch | Op::ExtractOnce | Op::ReplaceOnce => Mode::Single,
        Op::Count => Mode::Count,
        Op::ExtractAll | Op::ReplaceAll => Mode::Extract,
        Op::Split => Mode::Split,
    };
    let submatches = !matches!(op, Op::IfMatch | Op::Count);
    let extract_after = matches!(op, Op::ExtractOnce | Op::ReplaceOnce);
    let Some(out) = nfa::run(&b, &input, mode, submatches, i64::from(case), extract_after) else {
        return why("matching");
    };
    let groups = b.groups as usize;
    let mut writes = vec![
        (
            Array::StateActive,
            1,
            out.state_active.get(1..).unwrap_or_default().to_vec(),
        ),
        (
            Array::ThreadInfo,
            1,
            out.thread_info.get(1..).unwrap_or_default().to_vec(),
        ),
    ];
    for (a, v) in [
        (Array::SubPrev, &out.sub_prev),
        (Array::SubBegin, &out.sub_begin),
        (Array::SubEnd, &out.sub_end),
        (Array::SubCase, &out.sub_case),
    ] {
        let mut k = 0;
        while k < v.len() {
            if v[k].is_none() {
                k += 1;
                continue;
            }
            let start = k;
            let mut run = Vec::new();
            while k < v.len()
                && let Some(x) = v[k]
            {
                run.push(x);
                k += 1;
            }
            writes.push((a, start as i64, run));
        }
    }
    let mut p = Plan {
        writes,
        success: out.success,
        tmp_tl: tmp_regex,
        analysis: analysis_result(&ids, e, &toks)?,
        query_set: false,
        base,
        replays: out.max_replay,
        balance: None,
        last: Last::Cs(out.last),
        tail: Vec::new(),
        case_int: case_list.as_ref().map(|_| out.case),
        case_tls: None,
    };
    let cs = |k: usize| ids[k].map(Token::cs);
    let other = |c: u8| Token::other(u32::from(c));
    if op == Op::IfMatch {
        return Some(p);
    }
    if op == Op::Count {
        p.tail.extend([cs(id::INT_SET)?, args[2].first().copied()?]);
        p.tail.push(Token::LEFT_BRACE);
        p.tail.extend(out.count.to_string().bytes().map(other));
        p.tail.push(Token::RIGHT_BRACE);
        if args[2].len() != 1 {
            return why("count variable");
        }
        return Some(p);
    }
    if op == Op::ReplaceOnce && !out.success {
        return Some(p);
    }
    // \__regex_query_set:n: positions 1 to n + 2, the brace depth before
    // each.
    p.query_set = true;
    let n = toks.len();
    let mut bal = Vec::with_capacity(n + 2);
    let mut d = 0i64;
    bal.push(0);
    for &t in &toks {
        bal.push(d);
        if !t.is_cs() {
            if t.cmd_code() == Cmd::LeftBrace as u32 {
                d += 1;
            } else if t.cmd_code() == Cmd::RightBrace as u32 {
                d -= 1;
            }
        }
    }
    bal.push(d);
    let balance_at = |pos: i64| -> i64 {
        if pos > 0 {
            bal.get(pos as usize - 1).copied().unwrap_or(0)
        } else {
            0
        }
    };
    let get = |v: &Vec<Option<i64>>, k: i32| v.get(k as usize).copied().flatten().unwrap_or(0);
    let sub_balance =
        |k: i32| balance_at(get(&out.sub_end, k)) - balance_at(get(&out.sub_begin, k));
    let max_pos = n as i64 + 2;
    if replace {
        let lc = e.eqtb.code_table(CodeKind::Lc);
        if lc.get(u32::from(b'{')) != 0 || lc.get(u32::from(b'}')) != 0 {
            return why("\\lccode of braces");
        }
        // The replacement texts: one, or those of the cases.
        let Some(texts) = replacement_texts(&ids, &args[1], case_list.as_deref(), op, out.case)
        else {
            return why("replacement argument");
        };
        let mut reps = Vec::with_capacity(texts.len());
        for t in &texts {
            let s = detokenize(e, t);
            let cat = |c: u32| e.eqtb.catcode(c);
            let Some(r) = syntax::compile_replacement(&s, groups as u32, &cat) else {
                return why("replacement syntax");
            };
            reps.push(r);
        }
        let by_case = case_list.is_some() && op == Op::ReplaceAll;
        // The matches: the zeroth submatch of each.
        let zeroths: Vec<i32> = if op == Op::ReplaceOnce {
            vec![1]
        } else {
            (1..out.submatch_int).step_by(groups).collect()
        };
        let mut res = Vec::new();
        let mut total = 0i64;
        for &z in &zeroths {
            let k = if by_case {
                get(&out.sub_case, z) - 1
            } else {
                0
            };
            let Some(r) = usize::try_from(k).ok().and_then(|k| reps.get(k)) else {
                return why("case");
            };
            query_range(
                &toks,
                get(&out.sub_prev, z),
                get(&out.sub_begin, z),
                &mut res,
            );
            total += i64::from(r.balance) - sub_balance(z);
            for piece in &r.pieces {
                match piece {
                    Piece::Char(cat, c) => res.push(match cat {
                        13 => Token::cs(e.hash.active(*c)),
                        0 => Token::cs(e.hash.single(*c)),
                        _ => Token::char(Cmd::from_u8(*cat), *c),
                    }),
                    Piece::Sub(k) => {
                        let s = z + *k as i32;
                        total += sub_balance(s);
                        query_range(
                            &toks,
                            get(&out.sub_begin, s),
                            get(&out.sub_end, s),
                            &mut res,
                        );
                    }
                    Piece::Cs(name) => {
                        let mut bytes = Vec::new();
                        for &c in name {
                            crate::utf8x::push(&mut bytes, c);
                        }
                        res.push(Token::cs(e.hash.lookup_or_insert(&bytes)));
                    }
                    Piece::Var(name) => {
                        let mut bytes = Vec::new();
                        for &c in name {
                            crate::utf8x::push(&mut bytes, c);
                        }
                        let Some(v) = e.hash.lookup(&bytes) else {
                            return why("\\u variable");
                        };
                        let m = e.eqtb.meaning(v);
                        if m.mac.as_ref().is_some_and(|m| m.protected) {
                            return why("\\u variable");
                        }
                        let Some(b) = body(e, v) else {
                            return why("\\u variable");
                        };
                        res.extend_from_slice(b);
                    }
                }
            }
        }
        let tail_start = if op == Op::ReplaceOnce {
            get(&out.sub_end, 1)
        } else {
            i64::from(out.start_pos)
        };
        query_range(&toks, tail_start, max_pos, &mut res);
        if total != 0 || !balanced(&res) {
            return why("unbalanced result");
        }
        p.tmp_tl = Some(res);
        // \g__regex_balance_tl and \__regex_replacement_balance_one_match:n
        // (\__regex_replacement_set:n); with cases (\__regex_case_replacement:n)
        // \g__regex_case_balance_tl and \g__regex_case_replacement_tl too.
        let bt = if by_case {
            cs(id::CASE_BALANCE_TL)?;
            cs(id::CASE_REPLACEMENT_TL)?;
            let prefix = [
                cs(id::IF_CASE)?,
                cs(id::INTARRAY_ITEM)?,
                cs(id::THREAD_INFO + 4)?,
                Token::LEFT_BRACE,
                Token::char(Cmd::MacParam, u32::from(b'#')),
                other(b'1'),
                Token::RIGHT_BRACE,
            ];
            let mut cb = prefix.to_vec();
            let mut cr = prefix.to_vec();
            for r in &reps {
                cb.push(cs(id::OR)?);
                cb.extend(balance_tl(&ids, r)?);
                cr.push(cs(id::OR)?);
                cr.extend(build_tl(e, &ids, r)?);
            }
            let mut bt = cb.clone();
            bt.push(cs(id::FI)?);
            p.case_tls = Some((cb, cr));
            bt
        } else {
            balance_tl(&ids, &reps[0])?
        };
        let one = one_match_body(&ids, &bt)?;
        p.balance = Some((bt, one));
        p.last = Last::ReplicateZero;
        p.tail = vec![cs(id::TL_SET_EQ)?, args[2][0], cs(id::G_TMP_TL)?];
    } else {
        // Extracting, splitting: \__regex_group_end_extract_seq:N.
        let mut submatch_int = out.submatch_int;
        let mut writes_split = None;
        if op == Op::Split {
            let k = submatch_int;
            writes_split = Some((k, max_pos, i64::from(out.start_pos)));
            submatch_int += 1;
            if out.empty_success && i64::from(out.start_pos) == max_pos {
                submatch_int -= 1;
            }
        }
        let tmp = cs(id::TMP_W)?;
        let mut res = Vec::new();
        let mut item = Vec::new();
        for k in 1..submatch_int {
            let (b, en) = match writes_split {
                Some((s, end, begin)) if s == k => (begin, end),
                _ => (get(&out.sub_begin, k), get(&out.sub_end, k)),
            };
            let bal_k = balance_at(en) - balance_at(b);
            item.clear();
            query_range(&toks, b, en, &mut item);
            if bal_k != 0 || !balanced(&item) {
                return why("unbalanced submatch");
            }
            res.extend([tmp, Token::LEFT_BRACE, Token::RIGHT_BRACE]);
            res.extend_from_slice(&item);
        }
        res.push(tmp);
        p.tmp_tl = Some(res);
        if let Some((k, end, begin)) = writes_split {
            p.writes.push((Array::SubPrev, i64::from(k), vec![0]));
            p.writes.push((Array::SubEnd, i64::from(k), vec![end]));
            p.writes.push((Array::SubBegin, i64::from(k), vec![begin]));
        }
        p.last = Last::EndFlag;
        p.tail = vec![cs(id::EXTRACT_SEQ)?];
        p.tail.extend_from_slice(&args[2]);
    }
    p.writes.push((Array::Balance, 1, bal));
    Some(p)
}

/// The replacement texts of `#2` (`\__regex_replacement:n {<text>}`), or
/// with cases: `\__regex_replacement:e {\tl_item:nn {<cases>} {2 *
/// \g__regex_case_int}}` (once; the case that matched) or
/// `\__regex_case_replacement:e {\__regex_tl_even_items:n {<cases>}}`
/// (all).
fn replacement_texts<'a>(
    ids: &[Option<CsId>],
    arg: &'a [Token],
    cases: Option<&'a [Token]>,
    op: Op,
    case: i64,
) -> Option<Vec<&'a [Token]>> {
    let Some(cases) = cases else {
        return Some(vec![braced_after(arg, ids[id::REPLACEMENT])?]);
    };
    let call = |inner: &'a [Token], f: usize| -> Option<Vec<&'a [Token]>> {
        let it = items(inner)?;
        (inner.first() == ids[f].map(Token::cs).as_ref()
            && inner.get(1).is_some_and(|t| {
                *t == Token::LEFT_BRACE || (!t.is_cs() && t.cmd_code() == Cmd::LeftBrace as u32)
            })
            && it.get(1) == Some(&cases))
        .then_some(it)
    };
    if op == Op::ReplaceOnce {
        let inner = braced_after(arg, ids[id::REPLACEMENT_E])?;
        let it = call(inner, id::TL_ITEM)?;
        let index = [
            Token::other(u32::from(b'2')),
            Token::other(u32::from(b'*')),
            Token::cs(ids[id::CASE_INT]?),
        ];
        if it.len() != 3 || it[2] != index {
            return None;
        }
        let all = items(cases)?;
        let k = usize::try_from(2 * case - 1).ok()?;
        Some(vec![*all.get(k)?])
    } else {
        let inner = braced_after(arg, ids[id::CASE_REPLACEMENT_E])?;
        let it = call(inner, id::TL_EVEN_ITEMS)?;
        if it.len() != 2 {
            return None;
        }
        Some(items(cases)?.into_iter().skip(1).step_by(2).collect())
    }
}

/// `\g__regex_balance_tl` after `\__regex_replacement_apply:Nn` of `r`:
/// `+ \__regex_submatch_balance:n {\__regex_int_eval:w <k> + #1
/// \scan_stop:}` for each submatch, then `+ <braces>`.
fn balance_tl(ids: &[Option<CsId>], r: &syntax::Replacement) -> Option<Vec<Token>> {
    let cs = |k: usize| ids[k].map(Token::cs);
    let other = |c: u8| Token::other(u32::from(c));
    let (sb, ie, ss) = (
        cs(id::SUBMATCH_BALANCE)?,
        cs(id::INT_EVAL)?,
        cs(id::SCAN_STOP)?,
    );
    let mut v = Vec::new();
    for digits in &r.balance_subs {
        v.extend([other(b'+'), sb, Token::LEFT_BRACE, ie]);
        v.extend(digits.iter().map(|&d| Token::other(d)));
        v.extend([
            other(b'+'),
            Token::char(Cmd::MacParam, u32::from(b'#')),
            other(b'1'),
            ss,
            Token::RIGHT_BRACE,
        ]);
    }
    v.push(other(b'+'));
    v.extend(r.balance.to_string().bytes().map(other));
    Some(v)
}

/// The body of `\__regex_replacement_balance_one_match:n` made by
/// `\cs_gset:Npn … #1 {<balance tl> - \__regex_submatch_balance:n {#1}}`.
fn one_match_body(ids: &[Option<CsId>], bt: &[Token]) -> Option<Vec<Token>> {
    let hash = Token::char(Cmd::MacParam, u32::from(b'#'));
    let one = Token::other(u32::from(b'1'));
    let mut v = Vec::with_capacity(bt.len() + 5);
    let mut i = 0;
    while i < bt.len() {
        if bt[i] == hash && bt.get(i + 1) == Some(&one) {
            v.push(Token::out_param(1));
            i += 2;
        } else {
            v.push(bt[i]);
            i += 1;
        }
    }
    v.extend([
        Token::other(u32::from(b'-')),
        Token::cs(ids[id::SUBMATCH_BALANCE]?),
        Token::LEFT_BRACE,
        Token::out_param(1),
        Token::RIGHT_BRACE,
    ]);
    Some(v)
}

/// `\l__regex_build_tl` of a compiled replacement, as
/// `\__regex_replacement_apply:Nn` passes it on (for
/// `\g__regex_case_replacement_tl`).
fn build_tl(e: &mut Engine, ids: &[Option<CsId>], r: &syntax::Replacement) -> Option<Vec<Token>> {
    let cs = |k: usize| ids[k].map(Token::cs);
    let (exp_not, exp_after, if_false, fi) = (
        cs(id::EXP_NOT)?,
        cs(id::EXP_AFTER)?,
        cs(id::IF_FALSE)?,
        cs(id::FI)?,
    );
    let mut v = Vec::new();
    let name = |v: &mut Vec<Token>, name: &[u32], f: Token| -> Option<()> {
        v.extend([
            exp_not,
            Token::LEFT_BRACE,
            exp_after,
            f,
            cs(id::CS_W)?,
            Token::RIGHT_BRACE,
        ]);
        v.extend(name.iter().map(|&c| {
            if c == u32::from(b' ') {
                Token::SPACE
            } else {
                Token::other(c)
            }
        }));
        v.push(cs(id::CS_END)?);
        Some(())
    };
    for piece in &r.pieces {
        match *piece {
            Piece::Char(13, c) => v.extend([
                exp_not,
                Token::LEFT_BRACE,
                cs(id::EXP_NOT_N)?,
                Token::cs(e.hash.active(c)),
                Token::RIGHT_BRACE,
            ]),
            Piece::Char(1, c) => v.extend([
                exp_not,
                Token::LEFT_BRACE,
                exp_after,
                Token::char(Cmd::LeftBrace, c),
                if_false,
                Token::RIGHT_BRACE,
                fi,
                Token::RIGHT_BRACE,
            ]),
            Piece::Char(2, c) => v.extend([
                exp_not,
                Token::LEFT_BRACE,
                if_false,
                Token::LEFT_BRACE,
                fi,
                Token::char(Cmd::RightBrace, c),
                Token::RIGHT_BRACE,
            ]),
            Piece::Char(6, c) => v.extend([
                exp_not,
                Token::LEFT_BRACE,
                exp_not,
                Token::LEFT_BRACE,
                Token::char(Cmd::MacParam, c),
                Token::char(Cmd::MacParam, c),
                Token::RIGHT_BRACE,
                Token::RIGHT_BRACE,
            ]),
            Piece::Char(0, c) => v.extend([
                cs(id::EXP_NOT_N)?,
                cs(id::REPL_EXP_NOT_N)?,
                cs(id::EXP_NOT_C)?,
                Token::LEFT_BRACE,
                Token::other(c),
                Token::RIGHT_BRACE,
            ]),
            Piece::Char(cat, c) => v.push(Token::char(Cmd::from_u8(cat), c)),
            Piece::Sub(k) => {
                v.extend([
                    cs(id::QUERY_SUBMATCH)?,
                    Token::LEFT_BRACE,
                    cs(id::INT_EVAL)?,
                ]);
                v.extend(k.to_string().bytes().map(|d| Token::other(u32::from(d))));
                v.extend([
                    Token::other(u32::from(b'+')),
                    Token::char(Cmd::MacParam, u32::from(b'#')),
                    Token::other(u32::from(b'1')),
                    cs(id::SCAN_STOP)?,
                    Token::RIGHT_BRACE,
                ]);
            }
            Piece::Cs(ref n) => name(&mut v, n, cs(id::REPL_EXP_NOT_N)?)?,
            Piece::Var(ref n) => name(&mut v, n, cs(id::REPL_EXP_NOT_V)?)?,
        }
    }
    Some(v)
}

/// The number of intarray `cs` (`\__intarray:w <n>`).
fn intarray_number(e: &Engine, ids: &[Option<CsId>], cs: Option<CsId>) -> Option<i64> {
    let b = body(e, cs?)?;
    let marker = Token::cs(ids[id::INTARRAY_MARKER]?);
    let (&first, rest) = b.split_first()?;
    if first != marker {
        return None;
    }
    let mut n: i64 = 0;
    let mut any = false;
    for &t in rest {
        if t == Token::SPACE {
            break;
        }
        if t.is_cs() || t.cmd_code() != Cmd::OtherChar as u32 || !(48..=57).contains(&t.chr()) {
            return None;
        }
        n = n * 10 + i64::from(t.chr() - 48);
        any = true;
    }
    any.then_some(n)
}

/// A global definition of `cs` as a macro.
fn gdef(e: &mut Engine, cs: CsId, long: bool, protected: bool, tokens: Vec<Token>) {
    let m = Meaning {
        cmd: if long { Cmd::LongCall } else { Cmd::Call },
        chr: 0,
        mac: Some(Rc::new(Macro::new(protected, Rc::from(tokens)))),
    };
    e.define(true, Loc::Cs(cs), Val::Meaning(m));
}

/// Defines `name` globally (`\cs_gset_protected:Npn` with `#1`, or
/// `#1#2#3`) unless it has that definition already.
fn gdef_map(e: &mut Engine, name: &str, params: u32, body: Vec<Token>) {
    let cs = e.hash.lookup_or_insert(name.as_bytes());
    let mut tokens: Vec<Token> = (0..params)
        .map(|_| Token::match_token(u32::from(b'#')))
        .collect();
    tokens.push(Token::END_MATCH);
    tokens.extend(body);
    let m = e.eqtb.meaning(cs);
    if m.cmd == Cmd::LongCall
        && let Some(mac) = &m.mac
        && mac.protected
        && *mac.tokens == tokens[..]
    {
        return;
    }
    gdef(e, cs, true, true, tokens);
}

fn commit(e: &mut Engine, p: Plan) -> bool {
    let ids = ids(e);
    let Some(host) = e.lua.clone() else {
        return why::<()>("no Lua").is_some();
    };
    let arrays = [
        id::STATE_ACTIVE,
        id::THREAD_INFO,
        id::THREAD_INFO + 1,
        id::THREAD_INFO + 2,
        id::THREAD_INFO + 3,
        id::THREAD_INFO + 4,
        id::THREAD_INFO + 5,
    ];
    let mut numbers = [0i64; 7];
    for (k, &a) in arrays.iter().enumerate() {
        let Some(n) = intarray_number(e, &ids, ids[a]) else {
            return why::<()>("intarray variables").is_some();
        };
        numbers[k] = n;
    }
    let writes: Vec<(i64, i64, &[i64])> = p
        .writes
        .iter()
        .filter(|w| !w.2.is_empty())
        .map(|(a, first, v)| (numbers[*a as usize], *first, &v[..]))
        .collect();
    // \__intarray_gset:w, through which the arrays are found.
    let gset = ids[id::INTARRAY_GSET_W].map(|c| e.eqtb.meaning(c));
    let Some(gset) = gset.filter(|m| m.cmd == Cmd::LuaCall).map(|m| m.chr as i32) else {
        return why::<()>("intarray functions").is_some();
    };
    if !host.intarray_set(gset, &writes) {
        return why::<()>("intarrays not native").is_some();
    }
    // Nothing declines from here on.
    let cs = |k: usize| ids[k].expect("checked");
    let truth = e
        .eqtb
        .meaning(cs(if p.success {
            id::TRUE_BOOL
        } else {
            id::FALSE_BOOL
        }))
        .clone();
    e.define(true, Loc::Cs(cs(id::SUCCESS_BOOL)), Val::Meaning(truth));
    if let Some(t) = p.tmp_tl {
        let mut v = vec![Token::END_MATCH];
        v.extend(t);
        gdef(e, cs(id::G_TMP_TL), false, false, v);
    }
    let mut v = vec![Token::END_MATCH];
    v.extend(p.analysis);
    gdef(e, cs(id::ANALYSIS_RESULT), false, false, v);
    if let Some((bt, one)) = p.balance {
        let mut v = vec![Token::END_MATCH];
        v.extend(bt);
        gdef(e, cs(id::BALANCE_TL), false, false, v);
        let mut v = vec![Token::match_token(u32::from(b'#')), Token::END_MATCH];
        v.extend(one);
        gdef(e, cs(id::BALANCE_ONE), true, false, v);
    }
    if let Some(v) = p.case_int
        && let Some(cs) = ids[id::CASE_INT]
    {
        let m = e.eqtb.meaning(cs);
        let reg = m.chr - REG_OFFSET;
        e.define(true, Loc::Count(reg), Val::Int(v));
    }
    if let Some((cb, cr)) = p.case_tls {
        for (k, t) in [(id::CASE_BALANCE_TL, cb), (id::CASE_REPLACEMENT_TL, cr)] {
            let mut v = vec![Token::END_MATCH];
            v.extend(t);
            gdef(e, cs(k), false, false, v);
        }
    }
    let level = p.base + 1;
    gdef_map(
        e,
        &format!("__int_map_{level}:w"),
        1,
        vec![
            Token::cs(cs(id::INTARRAY_GSET)),
            Token::cs(cs(id::STATE_ACTIVE)),
            Token::LEFT_BRACE,
            Token::out_param(1),
            Token::RIGHT_BRACE,
            Token::cs(cs(id::C_ONE_INT)),
        ],
    );
    let one_token = Token::cs(cs(id::MATCH_ONE_TOKEN));
    for k in 1..=p.replays.max(1) {
        gdef_map(
            e,
            &format!("__tl_map_{}:w", p.base + k),
            1,
            vec![one_token, Token::out_param(1)],
        );
    }
    let ana = if p.query_set {
        vec![
            Token::cs(cs(id::QUERY_SET_AUX)),
            Token::LEFT_BRACE,
            Token::out_param(1),
            Token::RIGHT_BRACE,
            Token::out_param(3),
        ]
    } else {
        vec![
            one_token,
            Token::LEFT_BRACE,
            Token::out_param(1),
            Token::RIGHT_BRACE,
            Token::LEFT_BRACE,
            Token::out_param(2),
            Token::RIGHT_BRACE,
            Token::out_param(3),
        ]
    };
    gdef_map(e, &format!("__tl_analysis_map_inline_{level}:wNw"), 3, ana);
    e.last_cs_name = match p.last {
        // \flag_height:N \l__regex_end_flag's \if_cs_exist:w, with the
        // engine's \lastnamedcs for a name that is not defined.
        Last::EndFlag => e.lookup_named_cs(b"l__regex_end_flag0"),
        Last::ReplicateZero => e.hash.lookup_or_insert(b"__prg_replicate_first_0:n"),
        Last::Cs(LastCs::Matched(n)) => {
            let name = format!("l__regex_matched_analysis_tl{}", "'".repeat(n as usize));
            e.hash.lookup_or_insert(name.as_bytes())
        }
        Last::Cs(LastCs::TlMap(k)) => e
            .hash
            .lookup_or_insert(format!("__tl_map_{}:w", p.base + k).as_bytes()),
        Last::Cs(LastCs::AnalysisMap(k)) => e
            .hash
            .lookup_or_insert(format!("__tl_analysis_map_inline_{}:wNw", p.base + k).as_bytes()),
        Last::Cs(LastCs::ReplicateFirst(d)) => e
            .hash
            .lookup_or_insert(format!("__prg_replicate_first_{d}:n").as_bytes()),
    };
    e.native_insert(p.tail);
    true
}