path: root/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx

% \iffalse meta-comment
%
%% File: l3regex.dtx Copyright (C) 2011-2012 The LaTeX3 Project
%%
%% It may be distributed and/or modified under the conditions of the
%% LaTeX Project Public License (LPPL), either version 1.3c of this
%% license or (at your option) any later version.  The latest version
%% of this license is in the file
%%
%%    http://www.latex-project.org/lppl.txt
%%
%% This file is part of the "l3experimental bundle" (The Work in LPPL)
%% and all files in that bundle must be distributed together.
%%
%% The released version of this bundle is available from CTAN.
%%
%% -----------------------------------------------------------------------
%%
%% The development version of the bundle can be found at
%%
%%    http://www.latex-project.org/svnroot/experimental/trunk/
%%
%% for those people who are interested.
%%
%%%%%%%%%%%
%% NOTE: %%
%%%%%%%%%%%
%%
%%   Snapshots taken from the repository represent work in progress and may
%%   not work or may contain conflicting material!  We therefore ask
%%   people _not_ to put them into distributions, archives, etc. without
%%   prior consultation with the LaTeX3 Project.
%%
%% -----------------------------------------------------------------------
%
%<*driver|package>
\RequirePackage{expl3}
\GetIdInfo$Id: l3regex.dtx 3259 2012-01-29 20:50:48Z bruno $
  {L3 Experimental Regular Expressions}
%</driver|package>
%<*driver>
\documentclass[full]{l3doc}
\usepackage{amsmath}
\begin{document}
  \DocInput{\jobname.dtx}
\end{document}
%</driver>
% \fi
%
% \title{^^A
%   The \textsf{l3regex} package: regular expressions in \TeX{}^^A
%   \thanks{This file describes v\ExplFileVersion,
%     last revised \ExplFileDate.}^^A
% }
%
% \author{^^A
%  The \LaTeX3 Project\thanks
%    {^^A
%      E-mail:
%        \href{mailto:latex-team@latex-project.org}
%          {latex-team@latex-project.org}^^A
%    }^^A
% }
%
% \date{Released \ExplFileDate}
%
% \maketitle
%
% \begin{documentation}
% \newenvironment{l3regex-syntax}
%   {\begin{itemize}\def\\{\char`\\}\def\makelabel##1{\hss\llap{\ttfamily##1}}}
%   {\end{itemize}}
%
% \section{\pkg{l3regex} documentation}
%
% The \pkg{l3regex} package provides regular expression testing,
% extraction of submatches, splitting, and replacement, all acting
% on token lists. The syntax of regular expressions is mostly a subset
% of the PCRE syntax (and very close to POSIX), with some additions
% due to the fact that \TeX{} manipulates tokens rather than characters.
% For performance reasons, only a limited set of features are implemented.
% Notably, back-references are not supported.
%
% Let us give a few examples. After
% \begin{verbatim}
%   \tl_set:Nn \l_my_tl { That~cat. }
%   \regex_replace_once:nnN { at } { is } \l_my_tl
% \end{verbatim}
% the token list variable \cs{l_my_tl} holds the text
% \enquote{\texttt{This cat.}}, where the first
% occurrence of \enquote{\texttt{at}} was replaced
% by \enquote{\texttt{is}}. A more complicated example is
% a pattern to add a comma at the end of each word:
% \begin{verbatim}
%   \regex_replace_all:nnN { \w+ } { \0 , } \l_my_tl
% \end{verbatim}
% The |\w| sequence represents any \enquote{word} character,
% and |+| indicates that the |\w| sequence should be repeated
% as many times as possible (at least once), hence matching a word in the
% input token list. In the replacement text, |\0| denotes the full match
% (here, a word).
%
% If a regular expression is to be used several times,
% it can be compiled once, and stored in a regex
% variable using \cs{regex_const:Nn}. For example,
% \begin{verbatim}
%    \regex_const:Nn \c_foo_regex { \c{begin} \cB. (\c[^BE].*) \cE. }
% \end{verbatim}
% stores in \cs{c_foo_regex} a regular expression which matches the
% starting marker for an environment: \cs{begin}, followed by a
% begin-group token (|\cB.|), then any number of tokens which are
% neither begin-group nor end-group character tokens (|\c[^BE].*|),
% ending with an end-group token (|\cE.|). As explained in the next
% section, the parentheses \enquote{capture} the result of |\c[^BE].*|,
% giving us access to the name of the environment when doing
% replacements.
%
% \subsection{Syntax of regular expressions}
%
% Most characters match exactly themselves,
% with an arbitrary category code. Some characters are
% special and must be escaped with a backslash (\emph{e.g.}, |\*|
% matches a star character). Some escape sequences of
% the form backslash--letter also have a special meaning
% (for instance |\d| matches any digit). As a rule,
% \begin{itemize}
% \item every alphanumeric character (\texttt{A}--\texttt{Z},
%   \texttt{a}--\texttt{z}, \texttt{0}--\texttt{9}) matches
%   exactly itself, and should not be escaped, because
%   |\A|, |\B|, \ldots{} have special meanings;
% \item non-alphanumeric printable ascii characters can (and should)
%   always be escaped: many of them have special meanings (\emph{e.g.},
%   use |\(|, |\)|, |\?|, |\.|);
% \item spaces should always be escaped (even in character
%   classes);
% \item any other character may be escaped or not, without any
%   effect: both versions will match exactly that character.
% \end{itemize}
% Note that these rules play nicely with the fact that many
% non-alphanumeric characters are difficult to input into \TeX{}
% under normal category codes. For instance, |\\abc\%|
% matches the characters |\abc%| (with arbitrary category codes),
% but does not match the control sequence |\abc| followed by a
% percent character. Matching control sequences can be done
% using the |\c|\Arg{regex} syntax (see below).
%
% Any special character which appears at a place where its special
% behaviour cannot apply matches itself instead (for instance, a
% quantifier appearing at the beginning of a string), after raising a
% warning.
%
% Characters.
% \begin{l3regex-syntax}
%   \item[\\x\{hh\ldots{}\}] Character with hex code \texttt{hh\ldots{}}
%   \item[\\xhh] Character with hex code \texttt{hh}.
%   \item[\\a] Alarm (hex 07).
%   \item[\\e] Escape (hex 1B).
%   \item[\\f] Form-feed (hex 0C).
%   \item[\\n] New line (hex 0A).
%   \item[\\r] Carriage return (hex 0D).
%   \item[\\t] Horizontal tab (hex 09).
% \end{l3regex-syntax}
%
% Character types.
% \begin{l3regex-syntax}
%   \item[.] A single period matches any token.
%   \item[\\d] Any decimal digit.
%   \item[\\h] Any horizontal space character,
%     equivalent to |[\ \^^I]|: space and tab.
%   \item[\\s] Any space character,
%     equivalent to |[\ \^^I\^^J\^^L\^^M]|.
%   \item[\\v] Any vertical space character,
%     equivalent to |[\^^J\^^K\^^L\^^M]|. Note that |\^^K| is a vertical space,
%     but not a space, for compatibility with Perl.
%   \item[\\w] Any word character, \emph{i.e.},
%     alpha-numerics and underscore, equivalent to |[A-Za-z0-9\_]|.
%   \item[\\D] Any token not matched by |\d|.
%   \item[\\H] Any token not matched by |\h|.
%   \item[\\N] Any token other than the |\n| character (hex 0A).
%   \item[\\S] Any token not matched by |\s|.
%   \item[\\V] Any token not matched by |\v|.
%   \item[\\W] Any token not matched by |\w|.
%   \item[\\N] Any token not matched by |\n|.
% \end{l3regex-syntax}
% Of those, |.|, |\D|, |\H|, |\N|, |\S|, |\V|, and |\W| will match arbitrary
% control sequences.
%
% Character classes match exactly one character in the subject string.
% \begin{l3regex-syntax}
%   \item[{[\ldots{}]}] Positive character class.
%     Matches any of the specified tokens.
%   \item[{[\char`\^\ldots{}]}] Negative character class.
%     Matches any token other than the specified characters.
%   \item[{[x-y]}] Range (can be used with escaped characters).
% \end{l3regex-syntax}
% For instance, |[a-oq-z\cC.]| matches any lowercase latin letter
% except |p|, as well as control sequences (see below for a description
% of |\c|).
%
% Quantifiers (repetition).
% \begin{l3regex-syntax}
%   \item[?] $0$ or $1$, greedy.
%   \item[??] $0$ or $1$, lazy.
%   \item[*] $0$ or more, greedy.
%   \item[*?] $0$ or more, lazy.
%   \item[+] $1$ or more, greedy.
%   \item[+?] $1$ or more, lazy.
%   \item[\{$n$\}] Exactly $n$.
%   \item[\{$n,$\}] $n$ or more, greedy.
%   \item[\{$n,$\}?] $n$ or more, lazy.
%   \item[\{$n,m$\}] At least $n$, no more than $m$, greedy.
%   \item[\{$n,m$\}?] At least $n$, no more than $m$, lazy.
% \end{l3regex-syntax}
%
% Anchors and simple assertions.
% \begin{l3regex-syntax}
%   \item[\\b] Word boundary: either the previous token is matched by
%     |\w| and the next by |\W|, or the opposite. For this purpose,
%     the ends of the token list are considered as |\W|.
%   \item[\\B] Not a word boundary: between two |\w| tokens
%     or two |\W| tokens (including the boundary).
%   \item[\char`^ \textrm{or} \\A]
%     Start of the subject token list.
%   \item[\char`$\textrm{,} \\Z \textrm{or} \\z]
%     End of the subject token list.
%   \item[\\G] Start of the current match. This is only different from |^|
%     in the case of multiple matches: for instance
%     |\regex_count:nnN { \G a } { aaba } \l_tmpa_int| yields $2$, but
%     replacing |\G| by |^| would result in \cs{l_tmpa_int} holding the
%     value $1$.
% \end{l3regex-syntax}
%
% Alternation and capturing groups.
% \begin{l3regex-syntax}
%   \item[A\char`|B\char`|C] Either one of \texttt{A}, \texttt{B},
%     or \texttt{C}.
%   \item[(\ldots{})] Capturing group.
%   \item[(?:\ldots{})] Non-capturing group.
%   \item[(?\char`|\ldots{})] Non-capturing group which resets
%     the group number for capturing groups in each alternative.
%     The following group will be numbered with the first unused
%     group number.
% \end{l3regex-syntax}
%
% The |\c| escape sequence allows to test the category code of tokens,
% and match control sequences. Each character category is represented
% by a single uppercase letter:
% \begin{itemize}
% \item |C| for control sequences;
% \item |B| for begin-group tokens;
% \item |E| for end-group tokens;
% \item |M| for math shift;
% \item |T| for alignment tab tokens;
% \item |P| for macro parameter tokens;
% \item |U| for superscript tokens (up);
% \item |D| for subscript tokens (down);
% \item |S| for spaces;
% \item |L| for letters;
% \item |O| for others; and
% \item |A| for active characters.
% \end{itemize}
% The |\c| escape sequence is used as follows.
% \begin{l3regex-syntax}
%   \item[\\c\Arg{regex}] A control sequence whose csname matches the
%     \meta{regex}, anchored at the beginning and end, so that |\c{begin}|
%     matches exactly \cs{begin}, and nothing else.
%   \item[\\cX\meta{character or class}] Matches a token with category
%     code |X| (any of |CBEMTPUDSLOA|) if it is also matched by the
%     \meta{character or class}.  For instance, |\cL[A-Z]| matches
%     uppercase letters of category code letter, |\cC.| matches any
%     control sequence, and |\cO\d| matches digits of category other.
%   \item[{\\c[XYZ]\meta{character or class}}] Matches a token with
%     category |X|, |Y|, or |Z| (each being any of |CBEMTPUDSLOA|),
%     if it is also matched by the \meta{character or class}. For instance,
%     |\c[LSO].| matches tokens of category letter, space, or other.
%   \item[{\\c[\char`\^XYZ]\meta{character or class}}] Matches a token with
%     category different from |X|, |Y|, or |Z| (each being any of
%     |CBEMTPUDSLOA|), if it is also matched by the \meta{character or
%       class}.  For instance, |\c[LSO].| matches tokens of category
%     letter, space, or other.
% \end{l3regex-syntax}
% The category code tests can be used inside classes; for instance,
% |[\cO\d \c[LO][A-F]]| matches what \TeX{} considers as hexadecimal
% digits, namely digits with category other, or uppercase letters from
% |A| to |F| with category either letter or other.
%
% The |\u| escape sequence allows to insert the contents of a token list
% directly into a regular expression or a replacement, avoiding the need
% to escape special characters. Namely, |\u|\Arg{tl~var~name} matches
% the exact contents of the token list \meta{tl~var}. Within a |\c{...}|
% control sequence matching, the |\u| escape sequence only expands its
% argument once, in effect performing \cs{tl_to_str:v}. Quantifiers are
% not supported directly: use a group.
%
% Options can be set with |(?|\meta{option}|)| and
% unset with |(?-|\meta{option}|)|. Options are local
% to the group in which they are set, and revert to their
% previous setting upon reaching the closing parenthesis.
% For instance, in \verb"(?i)a(b(?-i)c|d)e", the |i| option
% applies to the letters |a|, |b| and |e|.
% \begin{l3regex-syntax}
%   \item[(?i) \textrm{and} (?-i)] Toggle to a case
%     insensitive/sensitive mode. This only applies to ascii letters
%     (mapping \texttt{A}--\texttt{Z} to \texttt{a}--\texttt{z}).
%     For instance, |(?i)[Y-\\]| matches the characters |Y|, |Z|, |[|,
%     |\|, and the lower case letters |y| and |z|, while |(?i)[^aeiou]|
%     matches any character which is not a vowel.
% \end{l3regex-syntax}
%
% In character classes, only |^|, |-|, |]|, |\| and spaces are special,
% and should be escaped. Other non-alphanumeric characters can
% still be escaped without harm. The escape sequences |\d|,
% |\D|, etc. are also supported in character classes.
% If the first character is |^|, then the meaning of the character
% class is inverted. Ranges of characters can be expressed using
% |-|, for instance, |[\D 0-5]| is equivalent to |[^6-9]|.
%
% Capturing groups are a means of extracting information about the
% match. Parenthesized groups are labelled in the order of their
% opening parenthesis, starting at $1$. The contents of those groups
% corresponding to the \enquote{best} match (leftmost longest)
% can be extracted and stored in a sequence of strings using for
% instance \cs{regex_extract_once:nnNTF}.
%
% \subsection{Syntax of in the replacement text}
%
% Most of the features described in regular expressions do not make sense
% within the replacement text. Escaped characters are supported as inside
% regular expressions. The whole match is accessed as |\0|, and the first
% $9$ submatches are accessed as |\1|, \ldots{}, |\9|. Submatches with
% numbers higher than $9$ are accessed as |\g{|\meta{number}|}| instead.
%
% For instance,
% \begin{verbatim}
%   \tl_set:Nn \l_my_tl { Hello,~world! }
%   \regex_replace_all:nnN { ([er]?l|o) . } { \(\0\-\-\1\) } \l_my_tl
% \end{verbatim}
% results in \cs{l_my_tl} holding |H(ell--el)(o,--o) w(or--o)(ld--l)!|
%
% The characters inserted by the replacement have category code $12$
% (other) by default. The escape sequence |\c| allows to insert characters
% with arbitrary category codes, as well as control sequences.
% \begin{l3regex-syntax}
% \item[\\cXY] Produces the character |Y| (which can be given as
%   an escape sequence such as |\t| for tab) with category code |X|,
%   which must be one of |CBEMTPUDSLOA|.
% \item[\\c\Arg{text}] Produces the control sequence with csname
%   \meta{text}. The \meta{text} may contain references to the submatches
%   |\0|, |\1| \emph{etc.}
% \end{l3regex-syntax}
%
% \subsection{Precompiling regular expressions}
%
% If a regular expression is to be used several times,
% it is better to compile it once rather than doing it
% each time the regular expression is used. The precompiled
% regular expression is stored in a variable. All
% of the \pkg{l3regex} module's functions can be given their
% regular expression argument either as an explicit string
% or as a precompiled regular expression.
%
% \begin{function}{\regex_new:N}
%   \begin{syntax}
%     \cs{regex_new:N} \meta{regex~var}
%   \end{syntax}
%   Creates a new \meta{regex~var} or raises an error if the
%   name is already taken. The declaration is global. The
%   \meta{regex~var} will initially be such that it never matches.
% \end{function}
%
% \begin{function}{\regex_set:Nn, \regex_gset:Nn, \regex_const:Nn}
%   \begin{syntax}
%     \cs{regex_set:Nn} \meta{regex~var} \Arg{regex}
%   \end{syntax}
%   Stores a precompiled version of the \meta{regular expression}
%   in the \meta{regex~var}. For instance, this function can be used
%   as
%   \begin{verbatim}
%     \regex_new:N \l_my_regex
%     \regex_set:Nn \l_my_regex { my\ (simple\ )? reg(ex|ular\ expression) }
%   \end{verbatim}
%   The assignment is local for \cs{regex_set:Nn} and global for
%   \cs{regex_gset:Nn}. Use \cs{regex_const:Nn} for precompiled expressions
%   which will never change.
% \end{function}
%
% \subsection{Matching}
%
% All regular expression functions are available in both |:n| and |:N|
% variants. The former require a \enquote{standard} regular expression,
% while the later require a precompiled expression as generated by
% \cs{regex_(g)set:Nn}.
%
% \begin{function}[TF]{\regex_match:nn, \regex_match:Nn}
%   \begin{syntax}
%     \cs{regex_match:nnTF} \Arg{regex} \Arg{token list} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Tests whether the \meta{regular expression} matches any part
%   of the \meta{token list}. For instance,
%   \begin{verbatim}
%     \regex_match:nnTF { b [cde]* } { abecdcx } { TRUE } { FALSE }
%     \regex_match:nnTF { [b-dq-w] } { example } { TRUE } { FALSE }
%   \end{verbatim}
%   leaves \texttt{TRUE} then \texttt{FALSE} in the input stream.
% \end{function}
%
% \begin{function}{\regex_count:nnN, \regex_count:NnN}
%   \begin{syntax}
%     \cs{regex_count:nnN} \Arg{regex} \Arg{token list} \meta{int var}
%   \end{syntax}
%   Sets \meta{int var} within the current \TeX{} group level
%   equal to the number of times
%   \meta{regular expression} appears in \meta{token list}.
%   The search starts by finding the left-most longest match,
%   respecting greedy and ungreedy operators. Then the search
%   starts again from the character following the last character
%   of the previous match, until reaching the end of the token list.
%   Infinite loops are prevented in the case where the regular expression
%   can match an empty string: then we count one match between each
%   pair of characters.
%   For instance,
%   \begin{verbatim}
%     \int_new:N \l_foo_int
%     \regex_count:nnN { (b+|c) } { abbababcbb } \l_foo_int
%   \end{verbatim}
%   results in \cs{l_foo_int} taking the value $5$.
% \end{function}
%
% \subsection{Submatch extraction}
%
% \begin{function}[TF]{\regex_extract_once:nnN, \regex_extract_once:NnN}
%   \begin{syntax}
%     \cs{regex_extract_once:nnN} \Arg{regex} \Arg{token list} \meta{seq~var}
%     \cs{regex_extract_once:nnNTF} \Arg{regex} \Arg{token list} \meta{seq~var} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Finds the first match of the \meta{regular expression}
%   in the \meta{token list}. If it exists, the match is stored
%   as the zeroeth item of the \meta{seq~var}, and further
%   items are the contents of capturing groups, in the order
%   of their opening parenthesis. The \meta{seq~var}
%   is assigned locally. If there is no match,
%   the \meta{seq~var} is cleared.
%   The testing versions insert the \meta{true code} into the input
%   stream if a match was found, and the \meta{false code} otherwise.
%   For instance, assume that you type
%   \begin{verbatim}
%     \regex_extract_once:nnNTF { \A(La)?TeX(!*)\Z } { LaTeX!!! } \l_foo_seq
%       { true } { false }
%   \end{verbatim}
%   Then the regular expression (anchored at the start with |\A| and
%   at the end with |\Z|) will match the whole token list. The first
%   capturing group, |(La)?|, matches |La|, and the second capturing
%   group, |(!*)|, matches |!!!|. Thus, |\l_foo_seq| will contain
%   the items |{LaTeX!!!}|, |{La}|, and |{!!!}|, and the \texttt{true}
%   branch is left in the input stream.
% \end{function}
%
% \begin{function}[TF]{\regex_extract_all:nnN, \regex_extract_all:NnN}
%   \begin{syntax}
%     \cs{regex_extract_all:nnN} \Arg{regex} \Arg{token list} \meta{seq~var}
%     \cs{regex_extract_all:nnNTF} \Arg{regex} \Arg{token list} \meta{seq~var} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Finds all matches of the \meta{regular expression}
%   in the \meta{token list}, and stores all the submatch information
%   in a single sequence (concatenating the results of
%   multiple \cs{regex_extract_once:nnN} calls).
%   The \meta{seq~var} is assigned locally. If there is no match,
%   the \meta{seq~var} is cleared.
%   The testing versions insert the \meta{true code} into the input
%   stream if a match was found, and the \meta{false code} otherwise.
%   For instance, assume that you type
%   \begin{verbatim}
%     \regex_extract_all:nnNTF { \w+ } { Hello,~world! } \l_foo_seq
%       { true } { false }
%   \end{verbatim}
%   Then the regular expression will match twice, and the resulting
%   sequence contains the two items |{Hello}| and |{world}|,
%   and the \texttt{true} branch is left in the input stream.
% \end{function}
%
% \begin{function}[TF]{\regex_split:nnN, \regex_split:NnN}
%   \begin{syntax}
%     \cs{regex_split:nnN} \Arg{regular expression} \Arg{token list} \meta{seq~var}
%     \cs{regex_split:nnNTF} \Arg{regular expression} \Arg{token list} \meta{seq~var} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Splits the \meta{token list} into a sequence of parts, delimited by
%   matches of the \meta{regular expression}. If the \meta{regular expression}
%   has capturing groups, then the token lists that they match are stored as
%   items of the sequence as well. The assignment to \meta{seq~var} is local.
%   If no match is found the resulting \meta{seq~var} has the
%   \meta{token list} as its sole item. If the \meta{regular expression}
%   matches the empty token list, then the \meta{token list} is split
%   into single tokens.
%   The testing versions insert the \meta{true code} into the input
%   stream if a match was found, and the \meta{false code} otherwise.
%   For example, after
%   \begin{verbatim}
%     \seq_new:N \l_path_seq
%     \regex_split:nnNTF { / } { the/path/for/this/file.tex } \l_path_seq
%       { true } { false }
%   \end{verbatim}
%   the sequence |\l_path_seq| contains the items |{the}|, |{path}|,
%   |{for}|, |{this}|, and |{file.tex}|, and the \texttt{true} branch
%   is left in the input stream.
% \end{function}
%
% \subsection{Replacement}
%
% \begin{function}[TF]{\regex_replace_once:nnN,\regex_replace_once:NnN}
%   \begin{syntax}
%     \cs{regex_replace_once:nnN} \Arg{regular expression} \Arg{replacement} \meta{tl~var}
%     \cs{regex_replace_once:nnNTF} \Arg{regular expression} \Arg{replacement} \meta{tl~var} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Searches for the \meta{regular expression} in the \meta{token list}
%   and replaces the first match with the \meta{replacement}. The result
%   is assigned locally to \meta{tl~var}. In the \meta{replacement},
%   |\0| represents the full match, |\1| represent the contents
%   of the first capturing group, |\2| of the second, \emph{etc.}
% \end{function}
%
% \begin{function}[TF]{\regex_replace_all:nnN, \regex_replace_all:NnN}
%   \begin{syntax}
%     \cs{regex_replace_all:nnN} \Arg{regular expression} \Arg{replacement} \meta{tl~var}
%     \cs{regex_replace_all:nnNTF} \Arg{regular expression} \Arg{replacement} \meta{tl~var} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Replaces all occurrences of the \cs{regular expression}
%   in the \meta{token list} by the \meta{replacement}, where
%   |\0| represents the full match, |\1|
%   represent the contents of the first capturing group,
%   |\2| of the second, \emph{etc.} Every match
%   is treated independently, and matches cannot overlap.
%   The result is assigned locally to \meta{tl~var}.
% \end{function}
%
% \subsection{Bugs, misfeatures, future work, and other possibilities}
%
% The following need to be done now.
% \begin{itemize}
%   \item Clean up the use of messages.
%   \item Code comments.
%   \item Rewrite the documentation in a clearer way.
% \end{itemize}
%
% Code improvements to come.
% \begin{itemize}
% \item \cs{regex_show:N} to show how a given regular expression is
%   interpreted.
% \item Test for the maximum register \cs{c_max_register_int}.
% \item Use \tn{dimen} registers rather than \cs{l_regex_nesting_tl}
%   to build \cs{regex_nesting:n}.
% \item Reduce the number of epsilon-transitions in alternatives.
% \item Move the \enquote{reconstruction} part of \pkg{l3regex}
%   to \pkg{l3tl-analysis}.
% \item Optimize regexes for csnames when the regex is a simple string.
% \item Optimize simple strings: use less states (|abcade| should give
%   two states, for |abc| and |ade|). [Does that really make sense?]
% \item Optimize groups with no alternative.
% \item Optimize the use of \cs{prg_stepwise_...} functions.
% \item Decide what |\c{\c{...}}| should do in the replacement text.
% \item Fix the |\c{\cBx}| bug in replacement text.
% \end{itemize}
%
% The following features are likely to be implemented at some point
% in the future.
% \begin{itemize}
% \item General look-ahead/behind assertions.
% \item Regex matching on external files.
% \item Conditional subpatterns with look ahead/behind: \enquote{if
%     what follows is [\ldots{}], then [\ldots{}]}.
% \item |(*..)| and |(?..)| sequences to set some options
%   (partially implemented).
% \item |\K| for resetting the beginning of the match.
% \item UTF-8 mode for pdf\TeX{}.
% \item Newline conventions are not done.
%   In particular, we should have an option for |.| not to match newlines.
%   Also, |\A| should differ from |^|, and |\Z|, |\z| and |$| should
%   differ.
% \item Unicode properties: |\p{..}| and |\P{..}|;
%   |\X| which should match any \enquote{extended} Unicode sequence.
%   This requires to manipulate a lot of data, hence a lot of optimization
%   ahead.
% \end{itemize}
%
% The following features of PCRE or Perl will probably not be implemented.
% \begin{itemize}
% \item |\ddd|, matching the character with code \texttt{ddd} in octal;
% \item POSIX character classes |[:alpha:]| \emph{etc.}, this is redundant;
% \item Callout with |(?C...)|, we cannot run arbitrary user code during
%   the matching, because the regex code uses registers in an unsafe way;
% \item Conditional subpatterns (other than with a look-ahead
%   or look-behind condition): this is non-regular, isn't it?
% \item Named subpatterns: \TeX{} programmers have lived so far without
%   any need for named macro parameters.
% \end{itemize}
%
% The following features of PCRE or perl will definitely not be implemented.
% \begin{itemize}
% \item |\cx|, similar to \TeX{}'s own |\^^x|;
% \item Comments: \TeX{} already has its own system for comments.
% \item |\Q...\E| escaping: this would require to read the argument
%   verbatim, which is not in the scope of this module.
% \item Atomic grouping, possessive quantifiers: those tools, mostly
%   meant to fix catastrophic backtracking, are unnecessary in a
%   non-backtracking algorithm, and difficult to implement.
% \item Subroutine calls: this syntactic sugar is difficult to include
%   in a non-backtracking algorithm, in particular because the
%   corresponding group should be treated as atomic. Also, we cannot
%   afford to run user code within the regular expression matching,
%   because of our \enquote{misuse} of registers.
% \item Recursion: this is a non-regular feature.
% \item Back-references: non-regular feature, this requires backtracking,
%   which is prohibitively slow.
% \item Backtracking control verbs: intrinsically tied to backtracking.
% \item |\C| single byte in UTF-8 mode: Xe\TeX{} and Lua\TeX{} serve
%   us characters directly, and splitting those into bytes is tricky,
%   encoding dependent, and most likely not useful anyways.
% \end{itemize}
%
% \end{documentation}
%
% \begin{implementation}
%
% \section{\pkg{l3regex} implementation}
%
%<*package>
%    \begin{macrocode}
\ProvidesExplPackage
  {\ExplFileName}{\ExplFileDate}{\ExplFileVersion}{\ExplFileDescription}
\RequirePackage{l3str, l3tl-analysis, l3flag}
%    \end{macrocode}
%
% \subsection{Plan of attack}
%
% Most regex engines use backtracking. This allows to provide very
% powerful features (back-references come to mind first), but it is
% costly, and raises the problem of catastrophic backtracking. Since
% \TeX{} is not first and foremost a programming language, complicated
% code tends to run slowly, and we must use faster, albeit slightly more
% restrictive, techniques, coming from automata theory.
%
% Given a regular expression of $n$ characters, we build a
% non-deterministic finite automaton (NFA) with roughly $n$ states,
% which accepts precisely those token lists matching that regular
% expression. Then loop through the query token list one token (one
% \enquote{index}) at a time, exploring in parallel every possible path
% through the NFA. We keep track of an array of the states currently
% \enquote{active}, which are to be considered in order when the next
% token is read.
%
% We use the following vocabulary in the code comments (and in variable
% names).
% \begin{itemize}
%   \item \emph{Query}: the token list to which we apply the regular
%     expression.
%   \item \emph{Index}: each token in the query is labelled by an integer
%     \meta{index}, with $\cs{l_regex_min_index_int} - 1 \leq \meta{index}
%     \leq \cs{l_regex_max_index_int}$. The lowest and highest indexes
%     correspond to imaginary begin and end markers (with inacessible
%     category code and character code).
%   \item \emph{Step}:^^A todo: fill
%   \item \emph{State}: each state of the NFA is labelled by an integer
%     \meta{state} with $0 \leq \meta{state} <
%     \cs{l_regex_max_state_int}$.
%   \item \emph{Active state}: state of the NFA that is reached when
%     reading the query string for the matching. Those states are
%     ordered according to the greediness of quantifiers.
% \end{itemize}
%
% To acheive a good performance, we abuse \TeX{}'s registers in two
% ways.  We access registers directly by number rather than tying them
% to control sequence using \cs{int_new:N} and other allocation
% functions. And we store integers in \tn{dimen} registers in scaled
% points (\texttt{sp}), using \TeX{}'s implicit conversion from
% dimensions to integers in some contexts. Specifically, the registers
% are used as follows.
% \begin{itemize}
%   \item \tn{toks}\meta{state} has two parts: a property list which
%     holds the submatch information, followed by the tests and actions
%     to perform in the \meta{state} of the NFA.
%   \item \tn{dimen}\meta{state} is equal to the last step in which
%     the \meta{state} was active.
%   \item \tn{skip}$i$ holds the \meta{state} number corresponding to
%     the $i$-th active \meta{state} (in order of precedence: smaller is
%     more important) and has no shrink or stretch components.
%   \item \tn{toks}\meta{index} holds \meta{tokens} which \texttt{o}-
%     and \texttt{x}-expand to the \meta{index}-th token in the query.
% \end{itemize}
% \tn{count} registers are not abused, which means that we can safely
% use named integers.
%
% The code is structured as follows. Variables, constants and various
% helper functions are introduced first, to limit the clutter in later
% parts. Then functions pertaining to parsing the regular expression are
% defined: that part is rather long because of the many bells and
% whistles of the regex notation. The next subsection takes care of
% running the NFA. Finally, user functions.
%
% \subsection{Constants and variables}
%
% \subsubsection{Generic}
%
% \begin{macro}{\regex_tmp:w}
% \begin{variable}
%   {\l_regex_internal_a_int, \l_regex_internal_b_int, \l_regex_internal_c_int}
% \begin{variable}{\l_regex_internal_a_tl, \l_regex_internal_b_tl}
% \begin{variable}{\g_regex_internal_tl}
%   Temporary variables used for various purposes.
%    \begin{macrocode}
\cs_new:Npn \regex_tmp:w { }
\tl_new:N   \l_regex_internal_a_tl
\tl_new:N   \l_regex_internal_b_tl
\int_new:N  \l_regex_internal_a_int
\int_new:N  \l_regex_internal_b_int
\int_new:N  \l_regex_internal_c_int
\tl_new:N   \g_regex_internal_tl
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
% \end{macro}
%
% \begin{variable}
%   {
%     \c_regex_d_tl, \c_regex_D_tl, \c_regex_h_tl, \c_regex_H_tl,
%     \c_regex_s_tl, \c_regex_S_tl, \c_regex_v_tl, \c_regex_V_tl,
%     \c_regex_w_tl, \c_regex_W_tl, \c_regex_N_tl
%   }
%
%   These constant token lists encode which characters are recognized by
%   |\d|, |\D|, |\w|, \emph{etc.}  in regular expressions. Namely,
%   |\d=[0-9]|, |\w=[0-9A-Z_a-z]|, \verb*+\s=[\ \^^I\^^J\^^L\^^M]+,
%   \verb*+\h=[\ \^^I]+, |\v=[\^^J-\^^M]|, and the upper case
%   counterparts match anything that the lower case does not match.  The
%   order in which the various tests appear is optimized for usual
%   mostly lower case letter text.
%    \begin{macrocode}
\tl_const:Nn \c_regex_d_tl
  { \regex_item_range:nn \c_forty_eight { 57 } } % 0--9
\tl_const:Nn \c_regex_h_tl
  {
    \regex_item_equal:n \c_thirty_two % space
    \regex_item_equal:n \c_nine       % tab
  }
\tl_const:Nn \c_regex_s_tl
  {
    \regex_item_equal:n \c_thirty_two % space
    \regex_item_equal:n \c_nine       % tab
    \regex_item_equal:n \c_ten        % lf
    \regex_item_equal:n \c_twelve     % ff
    \regex_item_equal:n \c_thirteen   % cr
  }
\tl_const:Nn \c_regex_v_tl
  { \regex_item_range:nn \c_ten \c_thirteen } % lf, vtab, ff, cr
\tl_const:Nn \c_regex_w_tl
  {
    \regex_item_range:nn \c_ninety_seven { 122 } % a--z
    \regex_item_range:nn \c_sixty_five   {  90 } % A--Z
    \regex_item_range:nn \c_forty_eight  {  57 } % 0--9
    \regex_item_equal:n  { 95 } % _
  }
\tl_const:Nn \c_regex_D_tl
  { \c_regex_d_tl \regex_break_point:TF { } \regex_break_true:w }
\tl_const:Nn \c_regex_H_tl
  { \c_regex_h_tl \regex_break_point:TF { } \regex_break_true:w }
\tl_const:Nn \c_regex_S_tl
  { \c_regex_s_tl \regex_break_point:TF { } \regex_break_true:w }
\tl_const:Nn \c_regex_V_tl
  { \c_regex_v_tl \regex_break_point:TF { } \regex_break_true:w }
\tl_const:Nn \c_regex_W_tl
  { \c_regex_w_tl \regex_break_point:TF { } \regex_break_true:w }
\tl_const:Nn \c_regex_N_tl
  {
    \regex_item_equal:n \c_ten
    \regex_break_point:TF { } { \regex_break_true:w }
  }
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\c_regex_._tl}
%   The dot meta-character matches any character, except the end marker,
%   whose character code is $-2$.
%    \begin{macrocode}
\tl_const:cn { c_regex_._tl }
  {
    \if_num:w \l_regex_current_char_int > - \c_two
      \exp_after:wN \regex_break_true:w
    \fi:
  }
%    \end{macrocode}
% \end{variable}
%
% \subsubsection{Variables used while building}
%
% \begin{variable}{\l_regex_build_mode_int}
%   While building, ten modes are recognized, labelled $-63$, $-23$,
%   $-6$, $-2$, $0$, $2$, $3$, $6$, $23$, $63$. See
%   section~\ref{sec:regex-modes}.
%    \begin{macrocode}
\int_new:N \l_regex_build_mode_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_max_state_int}
% \begin{variable}{\l_regex_left_state_int, \l_regex_right_state_int}
%   The end-point states of the last group (which any quantifier
%   would repeat) are stored as \cs{l_regex_left/right_state_int}.
%   For simple strings of characters, the left and right pointers
%   only differ by one.
%   The last state that was allocated is $\cs{l_regex_max_state_int}-1$,
%   so that \cs{l_regex_max_state_int} always points to a free state.
%    \begin{macrocode}
\int_new:N  \l_regex_max_state_int
\int_new:N  \l_regex_left_state_int
\int_new:N  \l_regex_right_state_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_left_state_seq, \l_regex_right_state_seq}
%   Alternatives are implemented by branching from a state into the
%   various choices, then merging those into another state. We store
%   information about those states in two sequences.
%    \begin{macrocode}
\seq_new:N  \l_regex_left_state_seq
\seq_new:N  \l_regex_right_state_seq
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_end_group_seq}
% \begin{variable}{\l_regex_end_alternation_seq}
%   These sequences hold actions to be performed at the end of a group,
%   and at the end of each branch of the alternation, respectively.
%   Currently, \cs{l_regex_end_group_seq} is used to keep track of
%   letter case, and \cs{l_regex_end_alternation_seq} is used
%   for \verb"(?|...)" groups.
%    \begin{macrocode}
\seq_new:N  \l_regex_end_group_seq
\seq_new:N  \l_regex_end_alternation_seq
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_capturing_group_int}
% \begin{variable}{\l_regex_capturing_group_seq}
% \begin{variable}{\l_regex_capturing_group_max_int}
%   \cs{l_regex_capturing_group_int} is the ID number of the current
%   capturing group, starting at $0$ for a group enclosing the full
%   regular expression, and counting in the order of their left parenthesis.
%   This number is used when a branch of the alternation ends.
%   Capturing groups can be arbitrarily nested, and we keep track of
%   the stack of ID numbers in \cs{l_regex_capturing_group_seq}.
%   The \texttt{max_int} variable is used in the case of the special
%   groups \verb+(?|...|...)+, which reset the capturing group number in
%   each alternative: at the end of the group, we must use a number
%   larger than every capturing group appearing in any alternative.
%    \begin{macrocode}
\int_new:N  \l_regex_capturing_group_int
\seq_new:N  \l_regex_capturing_group_seq
\int_new:N  \l_regex_capturing_group_max_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_one_or_group_tl}
%   When looking for quantifiers, this variable holds either
%   \enquote{one} or \enquote{group} depending on whether the
%   object to which the quantifier applies matches one character
%   (\emph{i.e.}, is a character or character class), or is a group.
%    \begin{macrocode}
\tl_new:N   \l_regex_one_or_group_tl
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_catcodes_int, \l_regex_catcodes_default_int}
% \begin{variable}
%   {
%     \c_regex_catcode_C_int, \c_regex_catcode_B_int, \c_regex_catcode_E_int,
%     \c_regex_catcode_M_int, \c_regex_catcode_T_int, \c_regex_catcode_P_int,
%     \c_regex_catcode_U_int, \c_regex_catcode_D_int, \c_regex_catcode_S_int,
%     \c_regex_catcode_L_int, \c_regex_catcode_O_int, \c_regex_catcode_A_int
%   }
% \begin{variable}{\c_regex_catcodes_all_int}
%   We wish to allow constructions such as |\c[^BE](..\cL[a-z]..)|,
%   matching two tokens which are neither a begin-group nor an end-group
%   token, followed by a token of category letter and character code in
%   |[a-z]|, followed by two more tokens which are neither begin-group
%   nor end-group tokens. For this to work, we need to keep track of
%   lists of allowed category codes: \cs{l_regex_catcodes_int} and
%   \cs{l_regex_catcodes_default_int} are bitmaps, sums of $4^c$, for
%   all allowed catcodes $c$. The latter is local to each capturing
%   group, and we reset \cs{l_regex_catcodes_int} to that value after
%   each character or class, changing it only when encountering a |\c|
%   escape. Errata: the \cs{l_regex_catcodes_default_int} is not used
%   yet, because the idea of having \verb+\cL(...|...)+ act on the whole
%   contents of the group is not yet implemented.
%    \begin{macrocode}
\int_new:N \l_regex_catcodes_int
\int_new:N \l_regex_catcodes_default_int
\int_const:Nn \c_regex_catcode_C_int { "1 }
\int_const:Nn \c_regex_catcode_B_int { "4 }
\int_const:Nn \c_regex_catcode_E_int { "10 }
\int_const:Nn \c_regex_catcode_M_int { "40 }
\int_const:Nn \c_regex_catcode_T_int { "100 }
\int_const:Nn \c_regex_catcode_P_int { "1000 }
\int_const:Nn \c_regex_catcode_U_int { "4000 }
\int_const:Nn \c_regex_catcode_D_int { "10000 }
\int_const:Nn \c_regex_catcode_S_int { "100000 }
\int_const:Nn \c_regex_catcode_L_int { "400000 }
\int_const:Nn \c_regex_catcode_O_int { "1000000 }
\int_const:Nn \c_regex_catcode_A_int { "4000000 }
\int_const:Nn \c_regex_catcodes_all_int { "5515155 }
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_catcodes_bool}
%   Controls whether the bitmap of category codes built should be
%   inverted or not.
%    \begin{macrocode}
\bool_new:N \l_regex_catcodes_bool
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_tests_bool,\l_regex_tests_tl}
%   The tests which should be performed on an item of the token list are
%   stored in \cs{l_regex_tests_tl}. In the case of character classes,
%   \cs{l_regex_tests_bool} is \texttt{false} for negative character
%   classes. In the other case, \cs{l_regex_tests_tl} is directly
%   converted to a state of the NFA. The two variables are cleared
%   (boolean set to \texttt{true}) after looking for a quantifier for
%   the class or single character or property. It would seem cleaner to
%   clear them instead before grabbing the next character or class, but
%   that doesn't interact correctly with constructions like |\cL[...]|
%   where |\cL| inserts some tests in \cs{l_regex_tests_tl}, which
%   should not be eliminated before finding the class.
%    \begin{macrocode}
\bool_new:N \l_regex_tests_bool
\tl_new:N   \l_regex_tests_tl
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}
%   {
%     \l_regex_tests_saved_bool,
%     \l_regex_tests_saved_tl,
%     \l_regex_catcodes_saved_int
%   }
%   In nested class, which can only occur as |[\cA[...]]|, the variables
%   \cs{l_regex_tests_bool}, \cs{l_regex_tests_tl}, and
%   \cs{l_regex_catcodes_int} from the outer class must be saved while
%   processing the inner class.
%    \begin{macrocode}
\bool_new:N \l_regex_tests_saved_bool
\tl_new:N   \l_regex_tests_saved_tl
\int_new:N  \l_regex_catcodes_saved_int
%    \end{macrocode}
% \end{variable}
%
% \subsubsection{Variables used when matching}
%
% \begin{variable}{\l_regex_min_index_int}
% \begin{variable}{\l_regex_max_index_int}
%   The tokens in the query are indexed from \cs{l_regex_min_index_int}
%   for the first to $\cs{l_regex_max_index_int}-1$ for the last, and
%   their information is stored in \tn{muskip} and \tn{toks} registers
%   with those numbers. We don't start from $0$ because the \tn{toks}
%   registers with low numbers are used to hold the states of the NFA.
%    \begin{macrocode}
\int_new:N \l_regex_min_index_int
\int_new:N \l_regex_max_index_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_nesting_int}
%   The first phase when matching is to go once through the query token
%   list and store the information for each token as \tn{muskip} and
%   \tn{toks} registers. During this phase, \cs{l_regex_nesting_int}
%   counts the balance of begin-group and end-group character tokens
%   which appear before a given point in the string, and is stored as
%   the shrink component of the \tn{muskip} registers. This integer is
%   also used to keep track of the balance in the replacement text.
%    \begin{macrocode}
\int_new:N \l_regex_nesting_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_current_index_int}
% \begin{variable}{\l_regex_start_index_int}
% \begin{variable}{\l_regex_success_index_int}
%   While reading through the query token list,
%   \cs{l_regex_current_index_int} is the position in the token list,
%   starting at \cs{l_regex_min_index_int} for the first token.
%   Each match begins at the position given by
%   \cs{l_regex_start_index_int}. Whenever an execution thread succeeds,
%   the corresponding index is stored into \cs{l_regex_success_index_int},
%   which will be the next starting index (except in the case of empty
%   matches).
%   \begin{macrocode}
\int_new:N \l_regex_current_index_int
\int_new:N \l_regex_start_index_int
\int_new:N \l_regex_success_index_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_current_char_int}
% \begin{variable}{\l_regex_current_catcode_int}
% \begin{variable}{\l_regex_current_token_tl}
% \begin{variable}{\l_regex_last_char_int}
% \begin{variable}{\l_regex_case_changed_char_int}
%   The character and category codes of the token at the current
%   position; \meta{tokens} which \texttt{o}- and \texttt{x}-expand to
%   the token (as provided by \cs{tl_analysis:n}); the character code of
%   the token at the previous position; and the character code of the
%   result of changing the case of the current token
%   (|A-Z|$\leftrightarrow$|a-z|). This last integer is only computed if
%   the \enquote{case insensitive} option |(?i)| is used in the regex.
%   The \cs{l_regex_current_char_int} variable is also used in various
%   other phases to hold a character code.
%    \begin{macrocode}
\int_new:N \l_regex_current_char_int
\int_new:N \l_regex_current_catcode_int
\tl_new:N  \l_regex_current_token_tl
\int_new:N \l_regex_last_char_int
\int_new:N \l_regex_case_changed_char_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_caseless_bool}
%   True if caseless matching is used within the regular expression.
%   This controls whether \cs{l_regex_case_changed_char_int} is computed.
%    \begin{macrocode}
\bool_new:N \l_regex_caseless_bool
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_current_state_int}
%   For every character in the token list, each of the active states is
%   considered in turn.
%   The variable \cs{l_regex_current_state_int} holds the state
%   of the NFA which is currently considered: transitions are then
%   given as shifts relative to the current state.
%   In some cases of groups with quantifiers,
%   \cs{l_regex_current_state_int} is shifted to a fake value for
%   transitions to point to the correct states.
%    \begin{macrocode}
\int_new:N \l_regex_current_state_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_current_submatches_prop}
% \begin{variable}{\l_regex_success_submatches_prop}
%   The submatches for the thread which lies at the
%   \cs{l_regex_current_state_int} are stored in a property
%   list variable. This property list is stored by
%   \cs{regex_action_cost:n} into the \tn{toks} register
%   for the target state of the transition. When a thread
%   succeeds, this property list is copied to
%   \cs{l_regex_success_submatches_prop} and only the last
%   sucessful thread will remain there.
%    \begin{macrocode}
\prop_new:N \l_regex_current_submatches_prop
\prop_new:N \l_regex_success_submatches_prop
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_step_int}
%   In the case of repeated matches, \cs{l_regex_current_index_int}
%   is reset to the end-position of the previous match. In contrast,
%   \cs{l_regex_step_int} is simply incremented to provide
%   a unique number for each iteration of the matching loop. This
%   is handy to attach each set of submatch information to a given
%   iteration (and automatically discard it when it corresponds to
%   a past iteration).
%    \begin{macrocode}
\int_new:N \l_regex_step_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_max_active_int}
%   All the currently active states are kept in order of precedence
%   in the \tn{skip} registers, which for our purpose serve as an array:
%   the $i$th item of the array is \tn{skip}$i$. The largest index used
%   after treating the previous character is \cs{l_regex_max_active_int}.
%   At the start of every step, the whole array is unpacked, so that the
%   space can immediately be reused, and \cs{l_regex_max_active_int} is
%   reset to zero, effectively clearing the array.
%    \begin{macrocode}
\int_new:N \l_regex_max_active_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_every_match_tl}
%   Every time a match is found, this token list is used.  For single
%   matching, the token list is empty. For multiple matching, the token
%   list is set to repeat the matching.
%    \begin{macrocode}
\tl_new:N \l_regex_every_match_tl
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_fresh_thread_bool}
% \begin{variable}{\l_regex_success_empty_bool}
% \begin{macro}{\regex_if_two_empty_matches:F}
%   When doing multiple matches, we need to avoid infinite loops where
%   each iteration matches the same empty token list. When an empty
%   token list is matched, the next successful match of the same empty
%   token list is suppressed. We detect empty matches by setting
%   \cs{l_regex_fresh_thread_bool} to \texttt{true} for threads which
%   directly come from the start of the regular expression, and testing
%   that boolean whenever a thread succeeds. The function
%   \cs{regex_if_two_empty_matches:F} is redefined at every match
%   attempt, depending on whether the previous match was empty or not:
%   if it was, then the function must cancel a purported success if it
%   is empty and at the same spot as the previous match; otherwise, we
%   definitely don't have two identical empty matches, so the function
%   is \cs{use:n}.
%    \begin{macrocode}
\bool_new:N \l_regex_fresh_thread_bool
\bool_new:N \l_regex_success_empty_bool
\cs_new_eq:NN \regex_if_two_empty_matches:F \use:n
%    \end{macrocode}
% \end{macro}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\g_regex_success_bool}
% \begin{variable}{\l_regex_saved_success_bool}
% \begin{variable}{\l_regex_success_match_bool}
%   The boolean \cs{g_regex_success_bool} is true if there was at least
%   one successful match, and \cs{l_regex_success_match_bool} is true if
%   the current match attempt was successful.  The variable
%   \cs{g_regex_success_bool} is the only global variable in this whole
%   module. When nesting \cs{regex} functions internally, the value of
%   \cs{g_regex_success_bool} is saved into
%   \cs{l_regex_saved_success_bool}, which is local, hence not affected
%   by the changes due to inner regex functions.
%    \begin{macrocode}
\bool_new:N \g_regex_success_bool
\bool_new:N \l_regex_saved_success_bool
\bool_new:N \l_regex_success_match_bool
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \subsubsection{Regular expression variables}
%
% \begin{variable}{\c_regex_no_match_regex}
%   This regular expression matches nothing, but is still a valid
%   regular expression. It is used as the initial value for regular
%   expressions declared using \cs{regex_new:N}.
%    \begin{macrocode}
\tl_const:Nn \c_regex_no_match_regex
  {
    \regex_nfa:Nw \c_regex_no_match_regex
      \l_regex_max_state_int = \c_one
      \l_regex_capturing_group_int = \c_zero
      \tex_toks:D \c_zero { \s_stop }
    \s_stop
  }
%    \end{macrocode}
% \end{variable}
%
% \begin{macro}{\regex_new:N}
%   As for many data types deriving from the \texttt{tl} data type,
%   creating a new one is simply a matter of checking that it does not
%   exist yet, and setting it equal to a default value.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_new:N #1
  {
    \chk_if_free_cs:N #1
    \cs_gset_eq:NN #1 \c_regex_no_match_regex
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{variable}{\l_regex_internal_regex}
%   This holds a temporary pre-compiled regular expression
%   when matching a control sequence name.
%    \begin{macrocode}
\regex_new:N \l_regex_internal_regex
%    \end{macrocode}
% \end{variable}
%
% \subsubsection{Other variables}
%^^A todo: move?
%^^A todo: run with the check-declarations option.
%
% \begin{variable}{\l_regex_replacement_csnames_int}
%   The behaviour of closing braces inside a replacement text depends on
%   whether a sequences |\c{| or |\u{| has been encountered. The number
%       of \enquote{open} such sequences that should be closed by |}| is
%     stored in \cs{l_regex_replacement_csnames_int}, and decreased by
%     $1$ by each |}|.
%    \begin{macrocode}
\int_new:N \l_regex_replacement_csnames_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_replacement_int}
%    \begin{macrocode}
\int_new:N \l_regex_replacement_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_submatch_int}
% \begin{variable}{\l_regex_submatch_start_int}
%    \begin{macrocode}
\int_new:N \l_regex_submatch_int
\int_new:N \l_regex_submatch_start_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_match_count_int}
%   The number of matches found so far is stored
%   in \cs{l_regex_match_count_int}. This is only used
%   in the \cs{regex_count:nnN} functions.
%    \begin{macrocode}
\int_new:N \l_regex_match_count_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{regex_begin, regex_end}
%   Those flags are raised to indicate extra begin-group
%   or end-group tokens when extracting submatches.
%    \begin{macrocode}
\flag_new:n { regex_begin }
\flag_new:n { regex_end }
%    \end{macrocode}
% \end{variable}
%
% \subsection{Helpers}
%
% \subsubsection{Toks}
%
% Two unrelated sets of functions for manipulating \tn{toks} registers.
%
% \begin{macro}[int]{\regex_toks_put_left:Nx}
% \begin{macro}[int]{\regex_toks_put_right:Nx}
%   During the building phase, every \tn{toks} register starts with
%   \cs{s_stop}, and we wish to add \texttt{x}-expanded material to
%   those registers. The expansion is done \enquote{by hand} for
%   optimization (these operations are used quite a lot). When adding
%   material to the left, we define \cs{regex_tmp:w} to remove the
%   \cs{s_stop} marker and put it back to the left of the new material.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_toks_put_left:Nx #1#2
  {
    \cs_set_nopar:Npx \regex_tmp:w \s_stop { \s_stop #2 }
    \tex_toks:D #1 \exp_after:wN \exp_after:wN \exp_after:wN
      { \exp_after:wN \regex_tmp:w \tex_the:D \tex_toks:D #1 }
  }
\cs_new_protected:Npn \regex_toks_put_right:Nx #1#2
  {
    \cs_set_nopar:Npx \regex_tmp:w {#2}
    \tex_toks:D #1 \exp_after:wN
      { \tex_the:D \tex_toks:D \exp_after:wN #1 \regex_tmp:w }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int, rEXP]{\regex_toks_range:nn}
% \begin{macro}[aux, rEXP]{\regex_toks_range:ww}
%   Some non-expandable functions store pieces of their result in
%   \tn{toks} registers.  Those pieces are concatenated using
%   \cs{regex_toks_range:nn}, which expects two integers, \meta{start}
%   and \meta{end}, and expands to the contents of the \tn{toks}
%   registers from \meta{start} (inclusive) to \meta{end}
%   (exclusive). This correctly expands to nothing if \meta{start}
%   $\geq$ \meta{end}.
%    \begin{macrocode}
\cs_new:Npn \regex_toks_range:nn #1#2
  {
    \exp_after:wN \regex_toks_range:ww
    \int_use:N \int_eval:w #1 \exp_after:wN ;
    \int_use:N \int_eval:w #2 ;
    \prg_break_point:n { }
  }
\cs_new:Npn \regex_toks_range:ww #1 ; #2 ;
  {
    \if_num:w #1 < #2 \exp_stop_f:
    \else:
      \exp_after:wN \prg_map_break:
    \fi:
    \tex_the:D \tex_toks:D #1 \exp_stop_f:
    \exp_after:wN \regex_toks_range:ww
      \int_use:N \int_eval:w #1 + \c_one ; #2 ;
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% On the one hand, when performing the matching, the \tn{toks} registers
% hold submatch information, followed by the instruction for a given
% state of the NFA. The two parts are separated by \cs{s_stop}.  On the
% other hand, we provide functions to unpack the contents from a range
% of \tn{toks} within an \texttt{x}-expanding assignment.
%
% When it is time to extract submatches from the token list, the various
% tokens are stored in \tn{toks} registers numbered from
% \cs{l_regex_min_index_int} inclusive to \cs{l_regex_max_index_int}
% exclusive. Furthermore, the \tn{skip} registers hold\ldots{} ^^A ??
%
% \begin{macro}[int]{\regex_query_submatch:nn}
% \begin{macro}[int]{\regex_query_submatch:w}
%^^A ??
%    \begin{macrocode}
\cs_new:Npn \regex_query_submatch:nn #1#2
  {
    \if_num:w #1 < \l_regex_capturing_group_int
      \exp_after:wN \regex_query_submatch:w
      \int_use:N \int_eval:w #1 + #2 ;
    \fi:
  }
\cs_new:Npn \regex_query_submatch:w #1 ;
  {
    \regex_toks_range:nn
      { \tex_skip:D #1 }
      { \etex_gluestretch:D \tex_skip:D #1 }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Sequences}
%
% \begin{macro}[int]{\regex_seq_pop_int:NN}
% \begin{macro}[int]{\regex_seq_get_int:NN}
% \begin{macro}[int]{\regex_seq_push_int:NN}
%   When building the regular expression, we keep track of some integers
%   (pointers to various states) without help from \TeX{}'s grouping.
%   Here are variants of \cs{seq_pop:NN} and \cs{seq_get:NN} which
%   assign using \cs{int_set:Nn} rather than \cs{tl_set:Nn}.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_seq_pop_int:NN #1#2
  {
    \seq_pop:NN #1 \l_regex_internal_a_tl
    \int_set:Nn #2 \l_regex_internal_a_tl
  }
\cs_new_protected:Npn \regex_seq_get_int:NN #1#2
  {
    \seq_get:NN #1 \l_regex_internal_a_tl
    \int_set:Nn #2 \l_regex_internal_a_tl
  }
\cs_new_protected:Npn \regex_seq_push_int:NN #1#2
  { \seq_push:No #1 { \int_use:N #2 } }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_seq_pop_use:N}
% \begin{macro}[int]{\regex_seq_get_use:N}
%   When building the regular expression, some settings are kept
%   local to capturing groups without any help from \TeX{}'s grouping.
%   This is done \enquote{by hand}, in sequences whose items should
%   be run immediately.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_seq_pop_use:N #1
  {
    \seq_pop:NN #1 \l_regex_internal_a_tl
    \l_regex_internal_a_tl
  }
\cs_new_protected:Npn \regex_seq_get_use:N #1
  {
    \seq_get:NN #1 \l_regex_internal_a_tl
    \l_regex_internal_a_tl
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Grabbing digits}
%
% \begin{macro}[int]{\regex_get_digits:nw}
% \begin{macro}[aux]{\regex_get_digits_loop:N,\regex_get_digits_end:w}
%   When parsing the \texttt{\{} quantifier, we need a tool to grab
%   digits until reaching the first non-digit. This
%   \cs{regex_get_digits:nw} function places whatever digits it found as
%   a brace group after |#1|.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_get_digits:nw #1
  {
    \tex_afterassignment:D \regex_tmp:w
    \cs_set_nopar:Npx \regex_tmp:w
      {
        \exp_not:n {#1}
        { \if_false: } } \fi:
        \regex_get_digits_aux:NN
  }
\cs_new:Npn \regex_get_digits_aux:NN #1#2
  {
    \if_meaning:w \regex_build_raw:N #1
      \if_num:w 9 < 1 \exp_not:N #2 \exp_stop_f:
        #2
      \else:
        \regex_get_digits_end:w #1 #2
      \fi:
    \else:
      \regex_get_digits_end:w #1 #2
    \fi:
    \regex_get_digits_aux:NN
  }
\cs_new:Npn \regex_get_digits_end:w #1 \fi: #2 \regex_get_digits_aux:NN
  {
    \fi: #2
    \if_false: { { \fi: } }
    #1
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Testing characters}
%
% \begin{macro}[int]{\regex_break_point:TF}
% \begin{macro}[int]{\regex_break_true:w}
%   When testing whether a character of the query token list matches
%   a given character class in the regular expression, we often
%   have to test it against several ranges of characters, checking
%   if any one of those matches. This is done with a structure like
%   \begin{quote}
%     \meta{test1} \ldots{} \meta{test$\sb{n}$} \\
%     \cs{regex_break_point:TF} \Arg{true code} \Arg{false code}
%   \end{quote}
%   If any of the tests succeeds, it calls \cs{regex_break_true:w},
%   which cleans up and leaves \meta{true code} in the input stream.
%   Otherwise, \cs{regex_break_point:TF} leaves the \meta{false code}
%   in the input stream.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_break_true:w
   #1 \regex_break_point:TF #2 #3 {#2}
\cs_new_protected:Npn \regex_break_point:TF #1 #2 { #2 }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_item_caseful_equal:n}
% \begin{macro}[int]{\regex_item_caseful_range:nn}
% \begin{macro}[int]{\regex_item_caseful_geq:n}
%   Simple comparisons triggering \cs{regex_break_true:w} when true.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_item_caseful_equal:n #1
  {
    \if_num:w #1 = \l_regex_current_char_int
      \exp_after:wN \regex_break_true:w
    \fi:
  }
\cs_new_protected:Npn \regex_item_caseful_range:nn #1 #2
  {
    \reverse_if:N \if_num:w #1 > \l_regex_current_char_int
      \reverse_if:N \if_num:w #2 < \l_regex_current_char_int
        \exp_after:wN \exp_after:wN \exp_after:wN \regex_break_true:w
      \fi:
    \fi:
  }
\cs_new_protected:Npn \regex_item_caseful_geq:n #1
  {
    \reverse_if:N \if_num:w #1 > \l_regex_current_char_int
      \exp_after:wN \regex_break_true:w
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_item_caseless_equal:n}
% \begin{macro}[int]{\regex_item_caseless_range:nn}
% \begin{macro}[int]{\regex_item_caseless_geq:n}
%   For caseless matching, we perform the test both on
%   \cs{l_regex_current_char_int} and on
%   \cs{l_regex_case_changed_char_int}.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_item_caseless_equal:n #1
  {
    \if_num:w #1 = \l_regex_current_char_int
      \exp_after:wN \regex_break_true:w
    \fi:
    \if_num:w #1 = \l_regex_case_changed_char_int
      \exp_after:wN \regex_break_true:w
    \fi:
  }
\cs_new_protected:Npn \regex_item_caseless_range:nn #1 #2
  {
    \reverse_if:N \if_num:w #1 > \l_regex_current_char_int
      \reverse_if:N \if_num:w #2 < \l_regex_current_char_int
        \exp_after:wN \exp_after:wN \exp_after:wN \regex_break_true:w
      \fi:
    \fi:
    \reverse_if:N \if_num:w #1 > \l_regex_case_changed_char_int
      \reverse_if:N \if_num:w #2 < \l_regex_case_changed_char_int
        \exp_after:wN \exp_after:wN \exp_after:wN \regex_break_true:w
      \fi:
    \fi:
  }
\cs_new_protected:Npn \regex_item_caseless_geq:n #1
  {
    \reverse_if:N \if_num:w #1 > \l_regex_current_char_int
      \exp_after:wN \regex_break_true:w
    \fi:
    \reverse_if:N \if_num:w #1 > \l_regex_case_changed_char_int
      \exp_after:wN \regex_break_true:w
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_item_equal:n}
% \begin{macro}[int]{\regex_item_range:nn}
% \begin{macro}[int]{\regex_item_geq:n}
%   By default, matching takes the letter case into account.
%   Note that those functions are not protected:
%   they will expand at the building phase, hard-coding which
%   states take care of caseless versus caseful matching.
%    \begin{macrocode}
\cs_new:Npn \regex_item_equal:n  { \regex_item_caseful_equal:n }
\cs_new:Npn \regex_item_range:nn { \regex_item_caseful_range:nn }
\cs_new:Npn \regex_item_geq:n    { \regex_item_caseful_geq:n }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_build_caseless:,\regex_build_caseful:}
%   Switch between caseful and caseless matching.
%   This is only done during the building phase.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_caseless:
  {
    \bool_set_true:N \l_regex_caseless_bool
    \cs_set:Npn \regex_item_equal:n  { \regex_item_caseless_equal:n }
    \cs_set:Npn \regex_item_range:nn { \regex_item_caseless_range:nn }
    \cs_set:Npn \regex_item_geq:n    { \regex_item_caseless_geq:n }
  }
\cs_new_protected_nopar:Npn \regex_build_caseful:
  {
    \bool_set_false:N \l_regex_caseless_bool
    \cs_set:Npn \regex_item_equal:n  { \regex_item_caseful_equal:n }
    \cs_set:Npn \regex_item_range:nn { \regex_item_caseful_range:nn }
    \cs_set:Npn \regex_item_geq:n    { \regex_item_caseful_geq:n }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_item_catcode:nT}
% \begin{macro}[aux]{\regex_item_catcode_aux:}
%   The argument is a sum of powers of $4$ with exponents given by the
%   allowed category codes (between $0$ and $13$). Dividing by a given
%   power of $4$ gives an odd result if and only if that category code
%   is allowed. If the catcode does not match, then skip the character
%   code tests which follow.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_item_catcode_aux:
  {
    "
    \if_case:w \l_regex_current_catcode_int
         1       \or: 4       \or: 10      \or: 40
    \or: 100     \or:         \or: 1000    \or: 4000
    \or: 10000   \or:         \or: 100000  \or: 400000
    \or: 1000000 \or: 4000000 \else: 1*\c_zero
    \fi:
  }
\cs_new_protected:Npn \regex_item_catcode:nT #1
  {
    \if_int_odd:w \int_eval:w #1 / \regex_item_catcode_aux: \int_eval_end:
      \exp_after:wN \use:n
    \else:
      \exp_after:wN \use_none:n
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_item_cs:n}
%   Match a control sequence (the argument is a pre-compiled regex).
%   First test the catcode of the current token to be zero.
%   Then perform the matching test, and break if the csname
%   indeed matches. The three \cs{exp_after:wN} expand the contents
%   of \cs{l_regex_current_token_tl} (of the form \cs{exp_not:n}
%   \Arg{control sequence}) to \meta{control sequence}.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_item_cs:n #1
  {
    \int_compare:nNnT \l_regex_current_catcode_int = \c_zero
      {
        \tl_set:Nn \l_regex_internal_regex {#1}
        \bool_set_eq:NN \l_regex_saved_success_bool \g_regex_success_bool
        \exp_args:NNx \regex_match:NnTF \l_regex_internal_regex
          {
            \exp_after:wN \exp_after:wN
            \exp_after:wN \cs_to_str:N \l_regex_current_token_tl
          }
          {
            \bool_gset_eq:NN \g_regex_success_bool \l_regex_saved_success_bool
            \regex_break_true:w
          }
          { \bool_gset_eq:NN \g_regex_success_bool \l_regex_saved_success_bool }
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Simple character escape}
%
% Before actually parsing the regular expression or the replacement
% text, we go through them once, converting |\n| to the character $10$,
% \emph{etc.} In this pass, we also convert any special character
% (\texttt{*}, \texttt{?}, \texttt{\{}, etc.) or escaped alphanumeric
% character into a marker indicating that this was a special sequence,
% and replace escaped special characters and non-escaped alphanumeric
% characters by markers indicating that those were \enquote{raw}
% characters. The rest of the code can then avoid caring about escaping
% issues (those can become quite complex to handle in combination with
% ranges in character classes).
%
% Usage: \cs{regex_escape_use:nnnn} \meta{inline~1} \meta{inline~2}
% \meta{inline~3} \Arg{token list} The \meta{token list} is converted to
% a string, then read from left to right, interpreting backslashes as
% escaping the next character.  Unescaped characters are fed to the
% function \meta{fn1}, and escaped characters are fed to the function
% \meta{fn2} within an \texttt{x}-expansion context (typically those
% functions perform some tests on their argument to decide how to output
% them).  The escape sequences |\a|, |\e|, |\f|, |\n|, |\r|, |\t| and
% |\x| are recognized, and those are replaced by the corresponding
% character, then fed to \meta{fn3}. The result is then left in the
% input stream.
%
% The idea is to feed unescaped characters to one function,
% escaped characters to another, and feed |\a|, |\e|, |\f|,
% |\n|, |\r|, |\t| and |\x| converted to the appropriate
% character to a third function. Spaces are ignored unless
% escaped.
%
% \begin{macro}[int]{\regex_escape_use:nnnn}
% \begin{macro}[aux]{\regex_escape_loop:N}
% \begin{macro}[aux]+\regex_escape_\:w+
%   Go through |#4| once, applying |#1|, |#2|, or |#3| to each character
%   (after de-escaping it), then leave the result in the input
%   stream. Most of the work is done within an \texttt{x}-expanding
%   assignment, but the |\x| escape sequence cannot be done in that
%   way. Therefore, we interrupt the assignment at each |\x| escape
%   sequence, store the partial result in a \tn{toks} register, and at
%   the end unpack all of the \tn{toks} registers to the left of the
%   last chunk of \cs{l_regex_internal_a_tl}.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_escape_use:nnnn #1#2#3#4
  {
    \group_begin:
      \cs_set_nopar:Npn \regex_escape_unescaped:N ##1 { #1 }
      \cs_set_nopar:Npn \regex_escape_escaped:N ##1 { #2 }
      \cs_set_nopar:Npn \regex_escape_raw:N ##1 { #3 }
      \int_set:Nn \tex_escapechar:D { 92 }
      \str_gset_other:Nn \g_regex_internal_tl {#4}
      \int_zero:N \l_regex_internal_a_int
      \tl_set:Nx \l_regex_internal_a_tl
        {
          \exp_after:wN \regex_escape_loop:N \g_regex_internal_tl
          { break } \prg_break_point:n { }
        }
      \use:x
        {
          \group_end:
          \regex_toks_range:nn \c_zero \l_regex_internal_a_int
          \exp_not:o \l_regex_internal_a_tl
        }
  }
\cs_new:Npn \regex_escape_loop:N #1
  {
    \cs_if_exist_use:cF { regex_escape_\token_to_str:N #1:w }
      { \regex_escape_unescaped:N #1 }
    \regex_escape_loop:N
  }
\cs_new_nopar:cpn { regex_escape_ \c_backslash_str :w }
    \regex_escape_loop:N #1
  {
    \cs_if_exist_use:cF { regex_escape_/\token_to_str:N #1:w }
      { \regex_escape_escaped:N #1 }
    \regex_escape_loop:N
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_escape_unescaped:N}
% \begin{macro}[aux]{\regex_escape_escaped:N}
% \begin{macro}[aux]{\regex_escape_raw:N}
%   Those functions are never called before being given a new meaning,
%   so their definitions here don't matter.
%    \begin{macrocode}
\cs_new_eq:NN \regex_escape_unescaped:N ?
\cs_new_eq:NN \regex_escape_escaped:N   ?
\cs_new_eq:NN \regex_escape_raw:N       ?
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]+\regex_escape_\q_recursion_tail:w+
% \begin{macro}[aux]+\regex_escape_/\q_recursion_tail:w+
% \begin{macro}[aux]+\regex_escape_ :w+
% \begin{macro}[aux]
%   {
%     \regex_escape_/a:w, \regex_escape_/e:w, \regex_escape_/f:w,
%     \regex_escape_/n:w, \regex_escape_/r:w, \regex_escape_/t:w
%   }
%   The loop is ended upon seeing \cs{q_recursion_tail}.
%   Spaces are ignored, and |\a|, |\e|, |\f|, |\n|, |\r|, |\t| take
%   their meaning here.
%    \begin{macrocode}
\cs_new_eq:NN \regex_escape_break:w \prg_map_break:
\cs_new_nopar:cpn { regex_escape_/break:w }
  {
    \if_false: { \fi: }
    \msg_kernel_error:nn { regex } { trailing-backslash }
    \exp_after:wN \use_none:n \exp_after:wN { \if_false: } \fi:
  }
\cs_new_nopar:cpn { regex_escape_~:w } { }
\cs_new_nopar:cpx { regex_escape_/a:w }
  { \exp_not:N \regex_escape_raw:N \iow_char:N \^^G }
\cs_new_nopar:cpx { regex_escape_/t:w }
  { \exp_not:N \regex_escape_raw:N \iow_char:N \^^I }
\cs_new_nopar:cpx { regex_escape_/n:w }
  { \exp_not:N \regex_escape_raw:N \iow_char:N \^^J }
\cs_new_nopar:cpx { regex_escape_/f:w }
  { \exp_not:N \regex_escape_raw:N \iow_char:N \^^L }
\cs_new_nopar:cpx { regex_escape_/r:w }
  { \exp_not:N \regex_escape_raw:N \iow_char:N \^^M }
\cs_new_nopar:cpx { regex_escape_/e:w }
  { \exp_not:N \regex_escape_raw:N \iow_char:N \^^[ }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_escape_/x:w}
% \begin{macro}[aux]{\regex_escape_x_test:N}
% \begin{macro}[aux]{\regex_escape_x_unbraced_i:N}
% \begin{macro}[aux]{\regex_escape_x_unbraced_ii:N}
% \begin{macro}[aux]{\regex_escape_x_braced_loop:N}
% \begin{macro}[aux]{\regex_escape_x_braced_end:N}
% \begin{macro}[aux]{\regex_escape_x_end:}
%   When |\x| is encountered, interrupt the assignment,
%   and distinguish the cases of a braced or unbraced syntax.
%   In the braced case, collect arbitrarily many hexadecimal digits,
%   building the number in \cs{l_regex_current_char_int} (using
%   \cs{str_aux_hexadecimal_use:NTF}), and check that
%   the run of digits was stopped by a closing brace.
%   In the unbraced case, collect up to two hexadecimal digits,
%   possibly less, building the character number in \cs{l_regex_current_char_int}.
%   In both cases, once all digits have been collected, use
%   the \TeX{} primitive \tn{lowercase} to produce that character,
%   and use an \cs{if_false:} trick to restart the assignment.
%    \begin{macrocode}
\cs_new_nopar:cpn { regex_escape_/x:w } \regex_escape_loop:N
  {
    \if_false: { \fi: }
    \tex_toks:D \l_regex_internal_a_int
      \exp_after:wN { \l_regex_internal_a_tl }
    \int_incr:N \l_regex_internal_a_int
    \int_zero:N \l_regex_current_char_int
    \regex_escape_x_test:N
  }
\cs_new_protected:Npx \regex_escape_x_test:N #1
  {
    \exp_not:N \token_if_eq_charcode:NNTF \c_space_token #1
      { \exp_not:N \regex_escape_x_test:N }
      {
        \l_regex_current_char_int = "0
          \exp_not:N \token_if_eq_charcode:NNTF \c_lbrace_str #1
            { \exp_not:N \regex_escape_x_braced_loop:N }
            { \exp_not:N \regex_escape_x_unbraced_i:N #1 }
      }
  }
\cs_new:Npn \regex_escape_x_unbraced_i:N #1
  {
    \str_aux_hexadecimal_use:NTF #1
      { \regex_escape_x_unbraced_ii:N }
      { \exp_stop_f: \regex_escape_x_end: #1 }
  }
\cs_new:Npn \regex_escape_x_unbraced_ii:N #1
  {
    \token_if_eq_charcode:NNTF \c_space_token #1
      { \regex_escape_x_unbraced_ii:N }
      {
        \str_aux_hexadecimal_use:NTF #1
          { \exp_stop_f: \regex_escape_x_end: }
          { \exp_stop_f: \regex_escape_x_end: #1 }
      }
  }
\cs_new:Npn \regex_escape_x_braced_loop:N #1
  {
    \token_if_eq_charcode:NNTF \c_space_token #1
      { \regex_escape_x_braced_loop:N }
      {
        \str_aux_hexadecimal_use:NTF #1
          { \regex_escape_x_braced_loop:N }
          { \exp_stop_f: \regex_escape_x_braced_end:N #1 }
      }
  }
\cs_new_protected:Npx \regex_escape_x_braced_end:N #1
  {
    \exp_not:N \token_if_eq_charcode:NNTF \c_rbrace_str #1
      { \exp_not:N \regex_escape_x_end: }
      {
        \msg_kernel_error:nnx { regex } { x-missing-rbrace }
          { \int_use:N \l_regex_current_char_int }
        \exp_not:N \regex_escape_x_end: #1
      }
  }
\group_begin:
  \char_set_catcode_other:N \^^@
  \cs_new_protected_nopar:Npn \regex_escape_x_end:
    {
      \if_num:w \l_regex_current_char_int > \c_max_char_int
        \msg_kernel_error:nnx { regex } { x-overflow }
          { \int_use:N \l_regex_current_char_int }
        \exp_after:wN \use:n
      \else:
        \tex_lccode:D \c_zero \l_regex_current_char_int
        \exp_after:wN \tl_to_lowercase:n
      \fi:
        {
          \tl_set:Nx \l_regex_internal_a_tl
            { \if_false: } \fi:
            \regex_escape_raw:N ^^@
            \regex_escape_loop:N
        }
    }
\group_end:
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[EXP,aux]{\regex_char_if_alphanumeric:NTF}
% \begin{macro}[EXP,aux]{\regex_char_if_special:NTF}
%   These two tests are used in the first pass when parsing a
%   regular expression. That pass is responsible for finding
%   escaped and non-escaped characters, and recognizing which
%   ones have special meanings and which should be interpreted
%   as \enquote{raw} characters. Namely,
%   \begin{itemize}
%     \item alphanumerics are \enquote{raw} if they are not escaped,
%       and may have a special meaning when escaped;
%     \item non-alphanumeric printable ascii characters are \enquote{raw}
%       if they are escaped, and may have a special meaning when not escaped;
%     \item characters other than printable ascii are always \enquote{raw}.
%   \end{itemize}
%   The code is ugly, and highly based on magic numbers and the ascii
%   codes of characters. This is mostly unavoidable for performance
%   reasons: testing for instance with \cs{str_if_contains_char:nN}
%   would be much slower. Maybe the tests can be optimized a little
%   bit more.
%   Here, \enquote{alphanumeric} means \texttt{0}--\texttt{9},
%   \texttt{A}--\texttt{Z}, \texttt{a}--\texttt{z};
%   \enquote{special} character means non-alphanumeric
%   but printable ascii, from space (hex \texttt{20}) to
%   \texttt{del} (hex \texttt{7E}).
%    \begin{macrocode}
\prg_new_conditional:Npnn \regex_char_if_special:N #1 { TF }
  {
    \if_num:w `#1 < \c_ninety_one
      \if_num:w `#1 < \c_fifty_eight
        \if_num:w `#1 < \c_forty_eight
          \if_num:w `#1 < \c_thirty_two
            \prg_return_false: \else: \prg_return_true: \fi:
        \else: \prg_return_false: \fi:
      \else:
        \if_num:w `#1 < \c_sixty_five
          \prg_return_true: \else: \prg_return_false: \fi:
      \fi:
    \else:
      \if_num:w `#1 < \c_one_hundred_twenty_three
        \if_num:w `#1 < \c_ninety_seven
          \prg_return_true: \else: \prg_return_false: \fi:
      \else:
        \if_num:w `#1 < \c_one_hundred_twenty_seven
          \prg_return_true: \else: \prg_return_false: \fi:
      \fi:
    \fi:
  }
\prg_new_conditional:Npnn \regex_char_if_alphanumeric:N #1 { TF }
  {
    \if_num:w `#1 < \c_ninety_one
      \if_num:w `#1 < \c_fifty_eight
        \if_num:w `#1 < \c_forty_eight
          \prg_return_false: \else: \prg_return_true: \fi:
      \else:
        \if_num:w `#1 < \c_sixty_five
          \prg_return_false: \else: \prg_return_true: \fi:
      \fi:
    \else:
      \if_num:w `#1 < \c_one_hundred_twenty_three
        \if_num:w `#1 < \c_ninety_seven
          \prg_return_false: \else: \prg_return_true: \fi:
      \else:
        \prg_return_false:
      \fi:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsection{Building}
%
% \subsubsection{Build mode}
% \label{sec:regex-modes}
%
% When building the NFA corresponding to a given regex, we can be in
% ten distinct modes, which we label by some magic numbers:
% \begin{itemize}
%   \item[-6] |[\c{...}]| control sequence in a class,
%   \item[-2] |\c{...}| control sequence,
%   \item[0] |...| outer,
%   \item[2] |\c...| catcode test,
%   \item[6] |[\c...]| catcode test in a class,
%   \item[-63] |[\c{[...]}]| class inside mode $-6$,
%   \item[-23] |\c{[...]}| class inside mode $-2$,
%   \item[3] |[...]| class inside mode $-3$,
%   \item[23] |\c[...]| class inside mode $2$,
%   \item[63] |[\c[...]]| class inside mode $6$.
% \end{itemize}
% This list is exhaustive, because |\c| escape sequences cannot be
% nested, and character classes cannot be nested directly. The choice
% of numbers is such as to optimize the most useful tests, and make
% transitions from one mode to another as simple as possible.
% \begin{itemize}
%   \item Even modes mean that we are not directly in a character class.
%     In this case, a left bracket appends $3$ to the mode. In a
%     character class, a right bracket changes the mode as $m\to
%     (m-15)/13$, truncated.
%   \item Grouping, assertion, and anchors are allowed in non-positive
%     even modes ($0$, $-2$, $-6$), and do not change the
%     mode. Otherwise, they trigger an error.
%   \item A left bracket is special in even modes, appending $3$ to the
%     mode; in those modes, quantifiers and the dot are recognized, and
%     the right bracket is normal. In odd modes (within classes), the
%     left bracket is normal, but the right bracket ends the class,
%     changing the mode from $m$ to $(m-15)/13$, truncated; also, ranges
%     are recognized.
%   \item In non-negative modes, left and right braces are normal. In
%     negative modes, however, left braces trigger a warning; right
%     braces end the control sequence, going from $-2$ to $0$ or $-6$ to
%     $3$, with error recovery for odd modes.
%   \item Properties (such as the |\d| character class) can appear in
%     any mode.
% \end{itemize}
%
% \begin{macro}[int, EXP]{\regex_build_if_in_class:TF}
%   Test whether we are currently in a character class (at the
%   inner-most level of nesting). There, many escape sequences are not
%   recognized, and special characters are normal. Also, for every raw
%   character, we must look ahead for a possible raw dash.
%   \begin{macrocode}
\cs_new_nopar:Npn \regex_build_if_in_class:TF
  {
    \if_int_odd:w \l_regex_build_mode_int
      \exp_after:wN \use_i:nn
    \else:
      \exp_after:wN \use_ii:nn
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\regex_build_if_assertions_forbidden:TF}
%   Assertions are only allowed in modes $0$, $-2$, and $-6$,
%   \emph{i.e.}, even, non-positive modes.
%    \begin{macrocode}
\cs_new_nopar:Npn \regex_build_if_assertions_forbidden:TF
  {
    \if_int_odd:w \l_regex_build_mode_int
      \exp_after:wN \use_i:nn
    \else:
      \if_int_compare:w \l_regex_build_mode_int > \c_zero
        \exp_after:wN \exp_after:wN \exp_after:wN \use_i:nn
      \else:
        \exp_after:wN \exp_after:wN \exp_after:wN \use_ii:nn
      \fi:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Helpers for building an NFA}
%
% \begin{macro}[int]{\regex_build_new_state:}
%   Add a new state to the NFA. At the end of the building phase, we
%   want every \tn{toks} register to start with \cs{s_stop}, hence
%   initialize the new register appropriately.  Then update
%   the left, right, and max \meta{states}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_new_state:
  {
    \tex_toks:D \l_regex_max_state_int { \s_stop }
    \int_set_eq:NN \l_regex_left_state_int \l_regex_right_state_int
    \int_set_eq:NN \l_regex_right_state_int \l_regex_max_state_int
    \int_incr:N \l_regex_max_state_int
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_transition:NN}
% \begin{macro}[aux]{\regex_build_transitions:NNNN}
%   These functions create a new state, and put one or two transitions
%   starting from the old current state.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_transition:NN #1#2
  {
    \regex_build_new_state:
    \regex_toks_put_right:Nx \l_regex_left_state_int
      { #1 { \int_eval:n { #2 - \l_regex_left_state_int } } }
  }
\cs_new_protected:Npn \regex_build_transitions:NNNN #1#2#3#4
  {
    \regex_build_new_state:
    \regex_toks_put_right:Nx \l_regex_left_state_int
      {
        #1 { \int_eval:n { #2 - \l_regex_left_state_int } }
        #3 { \int_eval:n { #4 - \l_regex_left_state_int } }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{From regex to NFA: framework}
%
% \begin{macro}[int]{\regex_build:w, \regex_build_end:}
% \begin{macro}[int]{\regex_build_exit_class:, \regex_build_exit_groups:}
%   There are two situations where we want to convert a regular
%   expression given as a string to an NFA. The first case is when the
%   regex is given directly by the user, as an \texttt{n} argument to
%   one of the \pkg{l3regex} functions, and the second case is when
%   building the regex given as an argument of the |\c{...}| escape
%   sequence within another regular expression. In both cases, some
%   variables must be reset before starting to build the NFA, using
%   \cs{regex_build:w}. Once building has ended (for instance when
%   encountering the closing brace in |\c{...}|), we make sure to close
%   any dangling class or open group, then add
%   \cs{regex_action_success:} to make the match successful if it
%   reaches the last state. The capturing group number is incremented:
%   then its value tells us how many capturing group there are,
%   including $0$.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build:w
  {
    \int_set_eq:NN \l_regex_catcodes_default_int \c_regex_catcodes_all_int
    \int_set_eq:NN \l_regex_catcodes_int \l_regex_catcodes_default_int
    \int_set_eq:NN \l_regex_capturing_group_int \c_zero
    \tl_clear:N \l_regex_tests_tl
    \bool_set_true:N \l_regex_tests_bool
    \int_zero:N \l_regex_max_state_int
    \regex_build_new_state:
  }
\cs_new_protected_nopar:Npn \regex_build_end:
  {
    \regex_build_exit_class:
    \regex_build_exit_groups:
    \regex_toks_put_right:Nx \l_regex_right_state_int
      { \regex_action_success: }
    \int_incr:N \l_regex_capturing_group_int
  }
\cs_new_protected_nopar:Npn \regex_build_exit_class:
  {
    \regex_build_if_in_class:TF
      {
        \msg_kernel_error:nn { regex } { missing-rbrack }
        \use:c { regex_build_]: }
      }
      { }
  }
\cs_new_protected_nopar:Npn \regex_build_exit_groups:
  {
    \seq_if_empty:NF \l_regex_capturing_group_seq
      {
        \msg_kernel_error:nnx { regex } { missing-rparen }
          { \seq_length:N \l_regex_capturing_group_seq }
        \prg_replicate:nn
          { \seq_length:N \l_regex_capturing_group_seq }
          { \regex_build_close_aux: \regex_build_group_: }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_build:n}
%   Setup some variables with \cs{regex_build:w}, and additionally set
%   the build mode to $0$: we are neither in a class nor a |\c|
%   construction. Initiate the regular expression by a wildcard: the
%   search is unanchored and should be tried at every index in the token
%   list. We surround the regular expression by parentheses with
%   \cs{regex_build_open_aux:} and \cs{regex_build_close_aux:}, so that
%   any alternative appears within a group (\emph{e.g.}, \verb"ab|cd"
%   will now be within the external group); this also forms a capturing
%   group (labelled $0$), which gives us the whole match as the $0$-th
%   submatch. The regular expression itself is parsed by using the
%   generic framework of \cs{regex_escape_use:nnnn} to recognize special
%   characters, escaped ones, and escape sequences such as |\n| or
%   |\x{02f}|. This results in successive \cs{regex_build_raw:N},
%   \cs{regex_build_escaped:N}, \cs{regex_build_special:N} followed by
%   their arguments. The trailing \cs{prg_do_nothing:} ensure that the
%   look-ahead done by some of the operations is harmless.  Finally,
%   \cs{regex_build_end:} adds the finishing code (checking that
%   parentheses are properly nested, for instance).
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build:n #1
  {
    \regex_build:w
      \int_set_eq:NN \l_regex_build_mode_int \c_zero
      \regex_build_new_state:
      \regex_toks_put_right:Nx \l_regex_left_state_int
        { \regex_action_start_wildcard: }
      \regex_build_open_aux:
        \regex_escape_use:nnnn
          {
            \regex_char_if_special:NTF ##1
              \regex_build_special:N \regex_build_raw:N ##1
          }
          {
            \regex_char_if_alphanumeric:NTF ##1
              \regex_build_escaped:N \regex_build_raw:N ##1
          }
          { \regex_build_raw:N ##1 }
          { #1 }
        \prg_do_nothing: \prg_do_nothing:
        \prg_do_nothing: \prg_do_nothing:
      \int_compare:nNnT \l_regex_build_mode_int < \c_zero
        {
          \msg_kernel_error:nn { regex } { c-missing-rbrace }
          \exp_after:wN \regex_build_special:N \c_rbrace_str
        }
      \seq_put_right:Nn \l_regex_capturing_group_seq {0}
      \regex_build_close_aux: \regex_build_group_:
    \regex_build_end:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_special:N}
% \begin{macro}[aux]{\regex_build_escaped:N}
%   If the special character or escaped alphanumeric has a particular
%   meaning in regexes, the corresponding function is used. Otherwise,
%   it is interpreted as a raw character. We distinguish special
%   characters from escaped alphanumeric characters because they behave
%   differently when appearing as an end-point of a range.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_special:N #1
  {
    \cs_if_exist_use:cF { regex_build_#1: }
      { \regex_build_raw:N #1 }
  }
\cs_new_protected:Npn \regex_build_escaped:N #1
  {
    \cs_if_exist_use:cF { regex_build_/#1: }
      { \regex_build_raw:N #1 }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_build_one:n, \regex_build_one:x}
%   In a class, add the argument to the current class. Outside a class,
%   this argument is the only test, and we look for quantifiers.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_one:n #1
  { \regex_build_one:x { \exp_not:n {#1} } }
\cs_new_protected:Npn \regex_build_one:x #1
  {
    \tl_put_right:Nx \l_regex_tests_tl
      {
        \if_num:w \l_regex_catcodes_int < \c_regex_catcodes_all_int
          \regex_item_catcode:nT { \int_use:N \l_regex_catcodes_int }
        \else:
          \exp_after:wN \use:n
        \fi:
        {#1}
      }
    \int_set_eq:NN \l_regex_catcodes_int \l_regex_catcodes_default_int
    \if_num:w \l_regex_build_mode_int = \c_two
      \l_regex_build_mode_int = \c_zero
    \else:
      \if_num:w \l_regex_build_mode_int = \c_six
        \l_regex_build_mode_int = \c_three
      \fi:
    \fi:
    \if_int_odd:w \l_regex_build_mode_int \else:
      \exp_after:wN \regex_build_one_quantifier:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\regex_tests_action_cost:n}
%   The argument is the target state if the test succeeds.
%    \begin{macrocode}
\cs_new:Npn \regex_tests_action_cost:n #1
  {
    \exp_not:o \l_regex_tests_tl
    \bool_if:NTF \l_regex_tests_bool
      { \regex_break_point:TF { \regex_action_cost:n {#1} } { } }
      { \regex_break_point:TF { } { \regex_action_cost:n {#1} } }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Raw characters}
%
% \begin{macro}[int]{\regex_build_raw_error:N}
%   Within character classes, some escaped alphanumeric sequences such
%   as |\b| do not have any meaning. They are replaced by a raw
%   character, after spitting out an error.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_raw_error:N #1
  {
    \if_int_odd:w \l_regex_build_mode_int
      \msg_kernel_error:nnx { regex } { class-bad-escape } {#1}
    \else:
      \msg_kernel_error:nnx { regex } { catcode-bad-escape } {#1}
    \fi:
    \regex_build_raw:N #1
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_build_raw:N}
%   If we are in a character class and the next character is an
%   unescaped dash, this denotes a range. Otherwise, the current
%   character |#1| matches itself.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_raw:N #1#2#3
  {
    \regex_build_if_in_class:TF
      { \str_if_eq:nnTF {#2#3} { \regex_build_special:N - } }
      { \use_ii:nn }
      { \regex_class_range:Nw #1 }
      {
        \regex_build_one:x { \regex_item_equal:n { \int_value:w `#1 ~ } }
        #2 #3
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_range:Nw}
%   We have just read a raw character followed by a dash; this should be
%   followed by an end-point for the range.  If the following character
%   is an escaped alphanumeric, or if it is an unescaped right bracket,
%   then we have an error, so we put the initial character and the dash
%   back, as raw characters. Otherwise, build the range, checking that
%   it is in the right order, and optimizing for equal end-points.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_class_range:Nw #1#2#3
  {
    \token_if_eq_meaning:NNTF #2 \regex_build_escaped:N % [
      { \use_i:nn } { \str_if_eq:nnTF { #2#3 } { \regex_build_special:N ] } }
      {
        \msg_kernel_warning:nnxx { regex } { range-missing-end } % [
          {#1} { \token_if_eq_charcode:NNF #3 ] { \c_backslash_str } #3 }
        \tl_put_right:Nx \l_regex_tests_tl
          {
            \regex_item_equal:n { \int_value:w `#1 ~ }
            \regex_item_equal:n { \int_value:w `- ~ }
          }
        #2#3
      }
      {
        \if_num:w `#1 > `#3 \exp_stop_f:
          \msg_kernel_error:nnxx { regex } { range-backwards } {#1} {#3}
        \else:
          \tl_put_right:Nx \l_regex_tests_tl
            {
              \if_num:w `#1 = `#3 \exp_stop_f:
                \regex_item_equal:n
              \else:
                \regex_item_range:nn { \int_value:w `#1 ~ }
              \fi:
              { \int_value:w `#3 ~ }
            }
        \fi:
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Character properties}
%
% \begin{macro}[aux]{\regex_build_.:}
%   In a class, the dot has no special meaning. Outside, insert
%   \cs{c_regex_._tl}, which matches any character or control
%   sequence, and refuses $-2$, which marks the end of the token list.
%    \begin{macrocode}
\cs_new_protected_nopar:cpx { regex_build_.: }
  {
    \exp_not:N \regex_build_if_in_class:TF
      { \regex_build_raw:N . }
      { \regex_build_one:n \exp_not:c { c_regex_._tl } }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_/d:,\regex_build_/D:}
% \begin{macro}[aux]{\regex_build_/h:,\regex_build_/H:}
% \begin{macro}[aux]{\regex_build_/s:,\regex_build_/S:}
% \begin{macro}[aux]{\regex_build_/v:,\regex_build_/V:}
% \begin{macro}[aux]{\regex_build_/w:,\regex_build_/W:}
% \begin{macro}[aux]{\regex_build_/N:}
%   The constants \cs{c_regex_d_tl}, \emph{etc.} hold
%   a list of tests which match the corresponding character
%   class, and jump to the \cs{regex_break_point:TF} marker.
%   As for a normal character, we check for quantifiers.
%    \begin{macrocode}
\tl_map_inline:nn { dDhHsSvVwWN }
  {
    \cs_new_protected_nopar:cpx { regex_build_/#1: }
      { \regex_build_one:n \exp_not:c { c_regex_#1_tl } }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Anchoring and simple assertions}
%
% \begin{macro}[aux]{\regex_build_simple_assertion:nn}
%   Assertions are only allowed in modes $0$, $-2$ and $-6$. In
%   character classes, or immediately following a category code test,
%   escaped letters cause errors, while the meaning of special
%   characters is ignored: |#1| is used instead. In modes where the
%   assertion is allowed, we insert the test |#2|; if the assertion is
%   successful, move from the \texttt{left} state to the \texttt{right}
%   state.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_simple_assertion:nn #1#2
  {
    \regex_build_if_assertions_forbidden:TF {#1}
      {
        \regex_build_new_state:
        \regex_toks_put_right:Nx \l_regex_left_state_int
          {
            \exp_not:n {#2}
              {
                \regex_action_free:n
                  {
                    \int_eval:n
                      { \l_regex_right_state_int - \l_regex_left_state_int }
                  }
              }
          }
        %^^A todo: add \regex_assertion_quantifier:
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]+\regex_build_^:+
% \begin{macro}[aux]{\regex_build_/A:}
% \begin{macro}[aux]{\regex_build_/G:}
% \begin{macro}[aux]+\regex_build_$:+
% \begin{macro}[aux]{\regex_build_/Z:}
% \begin{macro}[aux]{\regex_build_/z:}
%   Anchoring at the start corresponds to checking that the current
%   character is the first in the token list. Anchoring to the beginning
%   of the match attempt uses \cs{l_regex_start_index_int} instead of
%   \cs{c_zero}. End anchors match the end of the token list, marked by
%   a character code of $-2$.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_^: }
  {
    \regex_build_simple_assertion:nn { \regex_build_raw:N ^ }
      { \int_compare:nNnT \l_regex_min_index_int = \l_regex_current_index_int }
  }
\cs_new_protected_nopar:cpn { regex_build_/A: }
  {
    \regex_build_simple_assertion:nn { \regex_build_raw_error:N A }
      { \int_compare:nNnT \l_regex_min_index_int = \l_regex_current_index_int }
  }
\cs_new_protected_nopar:cpn { regex_build_/G: }
  {
    \regex_build_simple_assertion:nn { \regex_build_raw_error:N G }
      { \int_compare:nNnT \l_regex_start_index_int = \l_regex_current_index_int }
  }
\group_begin:
  \char_set_catcode_other:N \$
  \cs_new_protected_nopar:cpn { regex_build_$: } % $
    {
      \regex_build_simple_assertion:nn { \regex_build_raw:N $ } % $
        { \int_compare:nNnT \l_regex_current_char_int < \c_minus_one }
    }
\group_end:
\cs_new_protected_nopar:cpn { regex_build_/Z: }
  {
    \regex_build_simple_assertion:nn { \regex_build_raw_error:N Z }
      { \int_compare:nNnT \l_regex_current_char_int < \c_minus_one }
  }
\cs_new_protected_nopar:cpn { regex_build_/z: }
  {
    \regex_build_simple_assertion:nn { \regex_build_raw_error:N z }
      { \int_compare:nNnT \l_regex_current_char_int < \c_minus_one }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_build_/b:}
% \begin{macro}[int]{\regex_build_/B:}
% \begin{macro}[aux]{\regex_if_word_boundary:TF}
%   Contrarily to |^| and |$|, which could be implemented without
%   really knowing what precedes in the token list, this requires
%   more information, namely, the knowledge of the last character
%   code. Case sensitivity does not change word boundaries.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_/b: }
  {
    \regex_build_simple_assertion:nn { \regex_build_raw_error:N b }
      { \regex_if_word_boundary:T }
  }
\cs_new_protected_nopar:cpn { regex_build_/B: }
  {
    \regex_build_simple_assertion:nn { \regex_build_raw_error:N B }
      { \regex_if_word_boundary:TF { } }
  }
\cs_new_protected_nopar:Npn \regex_if_word_boundary:TF
  {
    \group_begin:
      \int_set_eq:NN \l_regex_current_char_int \l_regex_last_char_int
      \c_regex_w_tl
      \regex_break_point:TF
        { \group_end: \c_regex_W_tl \regex_item_equal:n { -2 } }
        { \group_end: \c_regex_w_tl }
    \regex_break_point:TF
  }
\cs_new_protected_nopar:Npn \regex_if_word_boundary:T
  { \regex_if_word_boundary:TF \use:n \use_none:n }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Entering and exiting character classes}
%
% \begin{macro}[aux]{\regex_build_[:}
%   In a class, left brackets mean nothing. Outside a class, this starts
%   a class, whose first characters may have a special meaning.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_[: }
  {
    \regex_build_if_in_class:TF
      { \regex_build_raw:N [ }
      { \regex_class_first:NNNN }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_]:}
%   Outside a class, right brackets have no meaning. In a class, change
%   the mode ($m\to (m-15)/13$, truncated) to reflect the fact that we
%   are leaving the class. If we are still in a class after leaving one,
%   then this is the case |[...\cL[...]...]|, and we insert the relevant
%   closing material in \cs{l_regex_tests_tl}. Otherwise look for
%   quantifiers.
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_]: }
  {
    \regex_build_if_in_class:TF
      {
        \if_num:w \l_regex_build_mode_int > \c_sixteen
          \tl_set:Nx \l_regex_tests_tl
            {
              \exp_not:o \l_regex_tests_saved_tl
              \if_num:w \l_regex_catcodes_saved_int < \c_regex_catcodes_all_int
                \regex_item_catcode:nT
                  { \int_use:N \l_regex_catcodes_saved_int }
              \else:
                \exp_after:wN \use:n
              \fi:
                {
                  \exp_not:o \l_regex_tests_tl
                  \bool_if:NF \l_regex_tests_bool
                    { \regex_break_point:TF { } \regex_break_true:w }
                }
            }
          \bool_set_eq:NN \l_regex_tests_bool \l_regex_tests_saved_bool
        \fi:
        \tex_advance:D \l_regex_build_mode_int - \c_fifteen
        \tex_divide:D \l_regex_build_mode_int \c_thirteen
        \if_int_odd:w \l_regex_build_mode_int \else:
          \exp_after:wN \regex_build_one_quantifier:
        \fi:
      }
      { \regex_build_raw:N ] }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_first:NNNN}
%   This starts a class. Change the mode by appending $3$ to it, and
%   reset the variables \cs{l_regex_tests_tl} and
%   \cs{l_regex_bool_tl}. In the special case of mode $63$
%   (|[\c[...]]|), we open a group, to avoid overriding the setting of
%   \cs{l_regex_tests_bool} and \cs{l_regex_tests_tl}; the group ends at
%   the matching right bracket. If the first character is |^|, then the
%   class is inverted. We keep track of this in
%   \cs{l_regex_tests_bool}. If the next character is a right bracket,
%   then it should be changed to a raw one (dirty hack here; the |F|
%   argument of \cs{str_if_eq:nnTF} is the trailing |#3|).
%    \begin{macrocode}
\cs_new_protected:Npn \regex_class_first:NNNN #1#2#3#4
  {
    \l_regex_build_mode_int = \int_value:w \l_regex_build_mode_int 3 ~ %
    \if_num:w \l_regex_build_mode_int > \c_sixteen
      \tl_set_eq:NN   \l_regex_tests_saved_tl     \l_regex_tests_tl
      \bool_set_eq:NN \l_regex_tests_saved_bool   \l_regex_tests_bool
      \int_set_eq:NN  \l_regex_catcodes_saved_int \l_regex_catcodes_int
      \int_set_eq:NN  \l_regex_catcodes_int       \c_regex_catcodes_all_int
    \fi:
    \token_if_eq_meaning:NNTF #1 \regex_build_special:N
      {
        \token_if_eq_charcode:NNTF #2 ^
          {
            \bool_set_false:N \l_regex_tests_bool % [
            \str_if_eq:nnTF {#3#4} { \regex_build_special:N ] }
              { \regex_build_raw:N }
          }
          { % [
            \token_if_eq_charcode:NNTF #2 ]
              { \regex_build_raw:N #2 }
              { #1 #2 }
          }
      }
      { #1 #2 }
    #3 #4
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Catcodes and csnames}
%
% \begin{macro}[aux]{\regex_build_/c:}
%   The |\c| escape sequence is only allowed in modes $0$ and $3$,
%   \emph{i.e.}, not within any other |\c| escape sequence.
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_/c: }
  {
    \if_case:w \l_regex_build_mode_int
      \exp_after:wN \regex_build_c_aux:wNN
    \or: \or: \or: \exp_after:wN \regex_build_c_aux:wNN
    \fi:
    \msg_kernel_error:nn { regex } { c-bad-mode }
    \s_stop
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_c_aux:wNN}
%   The |\c| escape sequence can be followed by a capital letter
%   representing a character category, by a left bracket which starts a
%   list of categories, or by a brace group holding a regular expression
%   for a control sequence name. Otherwise, raise an error.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_c_aux:wNN #1 \s_stop #2#3
  {
    \token_if_eq_meaning:NNTF #2 \regex_build_raw:N
      {
        \cs_if_exist:cTF { c_regex_catcode_#3_int }
          {
            \int_set_eq:Nc \l_regex_catcodes_int { c_regex_catcode_#3_int }
            \l_regex_build_mode_int
              = \if_case:w \l_regex_build_mode_int \c_two \else: \c_six \fi:
          }
      }
      { \cs_if_exist_use:cF { regex_build_c_#3: } }
          {
            \msg_kernel_error:nnx { regex } { c-missing-category } {#3}
            #2 #3
          }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}+\regex_build_c_{:+ ^^A }
%   The case of a left brace is easy, based on what we have done so far:
%   in a group, build the regular expression, after changing the mode to
%   forbid nesting |\c|.
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_c_ \c_lbrace_str : }
  {
    \group_begin:
      \l_regex_build_mode_int
        = - \if_case:w \l_regex_build_mode_int \c_two \else: \c_six \fi:
      \regex_build:w
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_c_[:}
% \begin{macro}[aux]{\regex_build_c_lbrack_loop:NN}
% \begin{macro}[aux]{\regex_build_c_lbrack_end:}
% \begin{macro}[aux]{\regex_build_add:N}
%   When encountering |\c[|, the task is to collect uppercase letters
%   representing character categories.
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_c_[: } #1#2
  {
    \int_zero:N \l_regex_catcodes_int
    \str_if_eq:nnTF { #1 #2 } { \regex_build_special:N ^ }
      {
        \bool_set_false:N \l_regex_catcodes_bool
        \regex_build_c_lbrack_loop:NN
      }
      {
        \bool_set_true:N \l_regex_catcodes_bool
        \regex_build_c_lbrack_loop:NN
        #1#2
      }
  }
\cs_new_protected:Npn \regex_build_c_lbrack_loop:NN #1#2
  {
    \token_if_eq_meaning:NNTF #1 \regex_build_raw:N
      {
        \cs_if_exist:cTF { c_regex_catcode_#2_int }
          {
            \exp_args:Nc \regex_build_c_lbrack_add:N
              { c_regex_catcode_#2_int }
            \regex_build_c_lbrack_loop:NN
          }
      }
      { % [
        \token_if_eq_charcode:NNTF #2 ]
          { \regex_build_c_lbrack_end: }
      }
          {
            \msg_kernel_error:nnx { regex } { c-missing-rbrack } {#2}
            \regex_build_c_lbrack_end:
          }
  }
\cs_new_protected_nopar:Npn \regex_build_c_lbrack_end:
  {
    \l_regex_build_mode_int
      = \if_case:w \l_regex_build_mode_int \c_two \else: \c_six \fi:
    \if_meaning:w \c_false_bool \l_regex_catcodes_bool
      \int_set:Nn \l_regex_catcodes_int
        { \c_regex_catcodes_all_int - \l_regex_catcodes_int }
    \fi:
  }
\cs_new_protected:Npn \regex_build_c_lbrack_add:N #1
  {
    \if_int_odd:w \int_eval:w \l_regex_catcodes_int / #1 \int_eval_end:
    \else:
      \tex_advance:D \l_regex_catcodes_int #1
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% ^^A{
% \begin{macro}+\regex_build_}:+
%   Non-escaped right braces are only special if they appear when
%   building the regular expression for a csname. In that case, make
%   sure that any character class and group is closed, anchor the match
%   at the end, add the code for making the match successful, and expand
%   the contents of the regular expression we just built.  Otherwise,
%   replace the brace with an escaped brace.
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_ \c_rbrace_str : }
  {
    \int_compare:nNnTF \l_regex_build_mode_int < \c_zero
      {
        \regex_build_exit_class:
        \regex_build_exit_groups:
        \regex_build_escaped:N Z
        \regex_build_end:
        \use:x
          {
            \group_end:
              \regex_build_one:n
                {
                  \regex_item_cs:n
                    { \regex_set_aux:N \l_regex_internal_regex }
                }
          }
      }
      { \exp_after:wN \regex_build_raw:N \c_rbrace_str }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Quantifiers}
%
% \begin{macro}[int]{\regex_build_quantifier:w}
%   This looks ahead and finds any quantifier (control character
%   equal to either of |?+*{|). ^^A}
%   When all characters for the quantifier are found, the corresponding
%   function is called.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_quantifier:w #1#2
  {
    \token_if_eq_meaning:NNTF #1 \regex_build_special:N
      {
        \cs_if_exist_use:cF { regex_build_quantifier_#2:w }
          {
            \regex_build_quantifier_end:nn { } { }
            #1 #2
          }
      }
      {
        \regex_build_quantifier_end:nn { } { }
        #1 #2
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_quantifier_?:w}
% \begin{macro}[aux]{\regex_build_quantifier_*:w}
% \begin{macro}[aux]{\regex_build_quantifier_+:w}
%   For each \enquote{basic} quantifier, |?|, |*|, |+|, feed the correct
%   arguments to \cs{regex_build_quantifier_aux:nnNN}.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_quantifier_?:w }
  { \regex_build_quantifier_aux:nnNN { } { ? } }
\cs_new_protected_nopar:cpn { regex_build_quantifier_*:w }
  { \regex_build_quantifier_aux:nnNN { } { * } }
\cs_new_protected_nopar:cpn { regex_build_quantifier_+:w }
  { \regex_build_quantifier_aux:nnNN { } { + } }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_quantifier_aux:nnNN}
%   Once the \enquote{main} quantifier (\texttt{?}, \texttt{*},
%   \texttt{+} or a braced construction) is found, we check
%   whether it is lazy (followed by a question mark),
%   and calls the appropriate function. Here |#1| holds some extra
%   arguments that the final function needs in the case of braced
%   constructions, and is empty otherwise.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_quantifier_aux:nnNN #1#2#3#4
  {
    \str_if_eq:nnTF { #3 #4 } { \regex_build_special:N ? }
      { \regex_build_quantifier_end:nn { #2 #4 } {#1} }
      {
        \regex_build_quantifier_end:nn { #2 } {#1}
        #3 #4
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]+\regex_build_quantifier_{:w+ ^^A}
% \begin{macro}[aux]{\regex_build_quantifier_lbrace:n}
% \begin{macro}[aux]{\regex_build_quantifier_lbrace:nw}
% \begin{macro}[aux]{\regex_build_quantifier_lbrace:nnw}
%   Three possible syntaxes: \texttt{\{\meta{int}\}},
%   \texttt{\{\meta{int},\}}, or \texttt{\{\meta{int},\meta{int}\}}.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_quantifier_ \c_lbrace_str :w }
  { \regex_get_digits:nw { \regex_build_quantifier_lbrace:n } }
\cs_new_protected:Npn \regex_build_quantifier_lbrace:n #1
  {
    \tl_if_empty:nTF {#1}
      {
        \regex_build_quantifier_end:nn { } { }
        \exp_after:wN \regex_build_raw:N \c_lbrace_str
      }
      { \regex_build_quantifier_lbrace:nw {#1} }
  }
\cs_new_protected:Npx \regex_build_quantifier_lbrace:nw #1#2#3
  {
    \exp_not:N \prg_case_str:nnn { #2 #3 }
      {
        { \exp_not:N \regex_build_special:N , }
          {
            \exp_not:N \regex_get_digits:nw
              { \exp_not:N \regex_build_quantifier_lbrace:nnw {#1} }
          }
        { \exp_not:N \regex_build_special:N \c_rbrace_str }
          { \exp_not:N \regex_build_quantifier_end:nn {n} { {#1} } }
      }
      {
        \exp_not:N \regex_build_quantifier_end:nn { } { }
        \exp_not:N \regex_build_raw:N \c_lbrace_str #1#2
      }
  }
\cs_new_protected:Npn \regex_build_quantifier_lbrace:nnw #1#2#3#4
  {
    \str_if_eq:xxTF
      { \exp_not:n {#3#4} }
      { \exp_not:N \regex_build_special:N \c_rbrace_str }
      {
        \tl_if_empty:nTF {#2}
          { \regex_build_quantifier_aux:nnNN { {#1} } { n* } }
          { \regex_build_quantifier_aux:nnNN { {#1} {#2} } { nn } }
      }
      {
        \regex_build_quantifier_end:nn { } { }
        \use:x
          {
            \exp_args:No \tl_map_function:nN
              { \c_lbrace_str #1 , #2 }
              \regex_build_raw:N
          }
        #3 #4
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_quantifier_end:nn}
%   When all quantifiers are found, we will call the relevant
%   \cs{regex_build_one/group_\meta{quantifiers}:} function.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_quantifier_end:nn #1#2
  {
    \use:c { regex_build_ \l_regex_one_or_group_tl _ #1 : } #2
    \tl_clear:N \l_regex_tests_tl
    \bool_set_true:N \l_regex_tests_bool
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Quantifiers for one character or character class}
%
% \begin{macro}[aux]{\regex_build_one_quantifier:}
%   Used for one single character, or a character class.
%   Contrarily to \cs{regex_build_group_quantifier:},
%   we don't need to keep track of submatches, and no thread
%   can be created within one repetition, so things are relatively easy.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_one_quantifier:
  {
    \tl_set:Nx \l_regex_one_or_group_tl { one }
    \regex_build_quantifier:w
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_n:, \regex_build_one_n?:}
% \begin{macro}[aux]{\regex_build_one_:}
%   This function is called in case the syntax is
%   \texttt{\{\meta{int}\}}. Greedy and lazy operators are identical,
%   since the number of repetitions is fixed. Build one state for each
%   repetition, with a transition controlled by the tests that we have
%   collected. The case where we find no quantifier is the special case
%   $n=1$.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_one_n: #1
  {
    \prg_replicate:nn {#1}
      {
        \regex_build_transition:NN
          \regex_tests_action_cost:n \l_regex_right_state_int
      }
  }
\cs_new_eq:cN { regex_build_one_n?: } \regex_build_one_n:
\cs_new_protected_nopar:Npn \regex_build_one_:
  { \regex_build_one_n: \c_one }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_n*:, \regex_build_one_n*?:}
% \begin{macro}[aux]{\regex_build_one_*:, \regex_build_one_*?:}
% \begin{macro}[aux]{\regex_build_one_+:, \regex_build_one_+?:}
%   Those functions are called in case the syntax is
%   \texttt{\{\meta{int},\}}. The |*| and |+| quantifiers (greedy or
%   lazy) are special cases for $n=0$ or $n=1$.  In the case $n=0$,
%   build a costly transition going from the current state to itself,
%   and a free transition moving to a new state. In the case $n\geq 1$,
%   reuse \cs{regex_build_one_n:} to match $n$ repetition, then add free
%   transitions from the last state to the previous one, and from the
%   last state to a new one. The greedy and lazy versions only differ in
%   the order of transitions.
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_one_n*: } #1
  {
    \int_compare:nNnTF {#1} = \c_zero
      {
        \regex_build_transitions:NNNN
          \regex_tests_action_cost:n \l_regex_left_state_int
          \regex_action_free:n       \l_regex_right_state_int
      }
      {
        \regex_build_one_n: {#1}
        \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int
        \regex_build_transitions:NNNN
          \regex_action_free:n \l_regex_internal_a_int
          \regex_action_free:n \l_regex_right_state_int
      }
  }
\cs_new_protected:cpn { regex_build_one_n*?: } #1
  {
    \int_compare:nNnTF {#1} = \c_zero
      {
        \regex_build_transitions:NNNN
          \regex_action_free:n       \l_regex_right_state_int
          \regex_tests_action_cost:n \l_regex_left_state_int
      }
      {
        \regex_build_one_n: {#1}
        \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int
        \regex_build_transitions:NNNN
          \regex_action_free:n \l_regex_right_state_int
          \regex_action_free:n \l_regex_internal_a_int
      }
  }
\cs_new_protected_nopar:cpx { regex_build_one_*: }
  { \exp_not:c { regex_build_one_n*: } \c_zero }
\cs_new_protected_nopar:cpx { regex_build_one_*?: }
  { \exp_not:c { regex_build_one_n*?: } \c_zero }
\cs_new_protected_nopar:cpx { regex_build_one_+: }
  { \exp_not:c { regex_build_one_n*: } \c_one }
\cs_new_protected_nopar:cpx { regex_build_one_+?: }
  { \exp_not:c { regex_build_one_n*?: } \c_one }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_nn:, \regex_build_one_nn?:}
% \begin{macro}[aux]{\regex_build_one_?:,  \regex_build_one_??:}
% \begin{macro}[aux]{\regex_build_one_nn_aux:nnnn}
%   Those functions are called when the syntax is
%   \texttt{\{\meta{int},\meta{int}\}}, or for the |?| quantifier, with
%   $m=0$ and $n=1$.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_one_nn:
  {
    \regex_build_one_nn_aux:nnnn { }
      {
        \regex_build_transitions:NNNN
          \regex_tests_action_cost:n \l_regex_right_state_int
          \regex_action_free:n       \l_regex_internal_a_int
      }
  }
\cs_new_protected_nopar:cpn { regex_build_one_nn?: }
  {
    \regex_build_one_nn_aux:nnnn {?}
      {
        \regex_build_transitions:NNNN
          \regex_action_free:n       \l_regex_internal_a_int
          \regex_tests_action_cost:n \l_regex_right_state_int
      }
  }
\cs_new_protected:Npn \regex_build_one_nn_aux:nnnn #1#2#3#4
  {
    \regex_build_one_n: {#3}
    \int_compare:nNnTF {#3} > {#4}
      {
        \msg_kernel_error:nnxxx
          { regex } { quantifier-backwards } {#3} {#4} {#1}
      }
      {
        \int_set:Nn \l_regex_internal_a_int
          { \l_regex_right_state_int + #4 - #3 }
        \prg_replicate:nn { #4 - #3 } { #2 }
      }
  }
\cs_new_protected_nopar:cpn { regex_build_one_?: }
  { \regex_build_one_nn: \c_zero \c_one }
\cs_new_protected_nopar:cpx { regex_build_one_??: }
  { \exp_not:c { regex_build_one_nn?: } \c_zero \c_one }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Groups and alternation}
%
% We support the syntax \texttt{\meta{expr1}|\ldots{}%^^A
%   |\meta{expr$\sb{n}$}} for alternations.
%
% \begin{macro}[aux]{\regex_build_(:, \regex_build_):}
% \begin{macro}[aux]{\regex_build_open_aux:}
% \begin{macro}[aux]+\regex_build_|:+
% \begin{macro}[aux]{\regex_build_begin_alternation:,
%     \regex_build_end_alternation:}
%   Grouping and alternation go together.
%   \begin{itemize}
%     \item Allocate the next available number for the end vertex
%       of the alternation/group and store it on a stack (so that nested
%       alternations work).
%     \item Put free transitions to separate all cases of the alternation.
%     \item Build each branch separately, and merge them to the common
%       end-node.
%     \item Test for a quantifier, and if needed, transfer the initial
%       vertex to a new vertex.
%   \end{itemize}
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_(: } #1#2
  {
    \regex_build_if_in_class:TF
      {
        \regex_build_raw:N (
        #1 #2
      }
      {
        \str_if_eq:nnTF { #1 #2 } { \regex_build_special:N ? }
          { \regex_build_special_group:NN }
          {
            \int_incr:N \l_regex_capturing_group_int
            \regex_seq_push_int:NN
              \l_regex_capturing_group_seq \l_regex_capturing_group_int
            \regex_build_open_aux:
            #1 #2
          }
      }
  }
\cs_new_protected_nopar:Npn \regex_build_open_aux:
  {
    \regex_build_new_state:
    \regex_seq_push_int:NN \l_regex_left_state_seq  \l_regex_left_state_int
    \regex_seq_push_int:NN \l_regex_right_state_seq \l_regex_right_state_int
    \bool_if:NTF \l_regex_caseless_bool
      { \seq_push:Nn \l_regex_end_group_seq \regex_build_caseless: }
      { \seq_push:Nn \l_regex_end_group_seq \regex_build_caseful: }
    \seq_push:Nn \l_regex_end_alternation_seq { }
    \regex_build_begin_alternation:
  }
\cs_new_protected_nopar:cpn { regex_build_|: }
  {
    \regex_build_if_in_class:TF { \regex_build_raw:N | }
      {
        \regex_build_end_alternation:
        \regex_build_begin_alternation:
      }
  }
\cs_new_protected_nopar:cpn { regex_build_): }
  {
    \regex_build_if_in_class:TF { \regex_build_raw:N ) }
      {
        \seq_if_empty:NTF \l_regex_capturing_group_seq
          { \msg_kernel_error:nn { regex } { extra-rparen } }
          {
            \regex_build_close_aux:
            \regex_build_group_quantifier:
          }
      }
  }
\cs_new_protected_nopar:Npn \regex_build_close_aux:
  {
    \regex_build_end_alternation:
    \regex_seq_pop_int:NN \l_regex_left_state_seq  \l_regex_left_state_int
    \regex_seq_pop_int:NN \l_regex_right_state_seq \l_regex_right_state_int
    \regex_seq_pop_use:N \l_regex_end_group_seq
    \seq_pop:NN \l_regex_end_alternation_seq \l_regex_internal_a_tl
  }
%    \end{macrocode}
%   Building each branch.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_begin_alternation:
  {
    \regex_build_new_state:
    \regex_seq_get_int:NN \l_regex_left_state_seq \l_regex_left_state_int
    \regex_toks_put_right:Nx \l_regex_left_state_int
      {
        \regex_action_free:n
          {
            \int_eval:n
              { \l_regex_right_state_int - \l_regex_left_state_int }
          }
      }
  }
\cs_new_protected_nopar:Npn \regex_build_end_alternation:
  {
    \int_set_eq:NN \l_regex_left_state_int \l_regex_right_state_int
    \regex_seq_get_int:NN \l_regex_right_state_seq \l_regex_right_state_int
    \regex_toks_put_right:Nx \l_regex_left_state_int
      {
        \regex_action_free:n
          {
            \int_eval:n
              { \l_regex_right_state_int - \l_regex_left_state_int }
          }
      }
    \regex_seq_get_use:N \l_regex_end_alternation_seq
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\regex_build_special_group:NN}
%   Same method as elsewhere: if the combination |(?#1| ^^A )
%   is known, then use that. Otherwise, treat the question mark
%   as if it had been escaped.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_special_group:NN #1#2
  {
    \cs_if_exist_use:cF { regex_build_special_group_\token_to_str:N #2 : }
      {
        \msg_kernel_error:nnx { regex } { special-group-unknown }
          { (? \token_to_str:N #2 } %)
        \regex_build_special:N ( % )
        \regex_build_raw:N ?
        #1 #2
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\regex_build_special_group_::}
%   Non-capturing groups are like capturing groups, except that
%   we set the group id to \texttt{-1}, which will then inhibit
%   submatching in \cs{regex_build_group_submatches:NN}.
%   The group number is not increased.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_special_group_:: }
  {
    \regex_seq_push_int:NN \l_regex_capturing_group_seq \c_minus_one
    \regex_build_open_aux:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}+\regex_build_special_group_|:+
%   The special group \verb"(?|..|..)" is non-capturing
%   (hence we set the |capturing_group| to $-1$), and resets
%   the group number in each branch of the alternation.
%   We use a variant of \cs{regex_build_open_aux:}, adding
%   some code to be performed at every alternation, and at
%   the end of the group. Namely, we keep track of
%   the maximal value that \cs{l_regex_capturing_group_int}
%   takes, and restore that value when the group end,
%   and in every branch, we reset the capturing group number.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_special_group_|: }
  {
    \regex_seq_push_int:NN \l_regex_capturing_group_seq \c_minus_one
    \regex_build_new_state:
    \regex_seq_push_int:NN \l_regex_left_state_seq  \l_regex_left_state_int
    \regex_seq_push_int:NN \l_regex_right_state_seq \l_regex_right_state_int
    \seq_push:Nx \l_regex_end_alternation_seq
      {
        \exp_not:N \int_compare:nNnT
          \l_regex_capturing_group_int
          > \l_regex_capturing_group_max_int
          {
            \int_set_eq:NN
              \l_regex_capturing_group_max_int
              \l_regex_capturing_group_int
          }
        \int_set:Nn \l_regex_capturing_group_int
          { \int_use:N \l_regex_capturing_group_int }
      }
    \seq_push:Nx \l_regex_end_group_seq
      {
        \bool_if:NTF \l_regex_caseless_bool
          \regex_build_caseless:
          \regex_build_caseful:
        \int_set_eq:NN
          \l_regex_capturing_group_int
          \l_regex_capturing_group_max_int
      }
    \regex_build_begin_alternation:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\regex_build_special_group_i:}
% \begin{macro}{\regex_build_special_group_-:}
% \begin{macro}[aux]{\regex_build_options:NNN}
% \begin{macro}[aux]{\regex_build_option_+i:}
% \begin{macro}[aux]{\regex_build_option_-i:}
%   The match can be made case-insensitive by setting the option
%   with \texttt{(?i)}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_special_group_i:
  {
    \regex_build_options:NNN +
    \regex_build_raw:N i
  }
\cs_new_protected_nopar:cpn { regex_build_special_group_-: }
  {
    \regex_build_options:NNN -
  }
\cs_new_protected:Npn \regex_build_options:NNN #1#2#3
  {
    \token_if_eq_meaning:NNTF \regex_build_raw:N #2
      {
        \cs_if_exist_use:cF { regex_build_option_#1#3: }
          { \msg_kernel_error:nnx { regex } { unknown-option } { #3 } }
        \regex_build_options:NNN #1
      }
      {
        \prg_case_str:nnn { #3 }
          { % (
            { ) } { }
            { - } { \regex_build_options:NNN - }
          }
          { \msg_kernel_error:nnx { regex } { invalid-in-option } { #3 } }
      }
  }
\cs_new_protected_nopar:cpn { regex_build_option_+i: }
  {
    \regex_build_caseless:
    \cs_set_eq:NN \regex_match_loop_case_hook:
      \regex_match_loop_caseless_hook:
  }
\cs_new_protected_nopar:cpn { regex_build_option_-i: }
  { \regex_build_caseful: }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Quantifiers for groups}
%
% \begin{macro}[aux]{\regex_build_group_quantifier:}
%   Used for one group. We need to keep track of submatches,
%   threads can be created within one repetition, so things are hard.
%   The code for the group that was just built starts
%   at \cs{l_regex_left_state_int} and ends at
%   \cs{l_regex_right_state_int}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_quantifier:
  {
    \tl_set:Nn \l_regex_one_or_group_tl { group }
    \regex_build_quantifier:w
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_submatches:NN}
%   Once the quantifier is found by \cs{regex_build_quantifier:w},
%   we insert the code for tracking submatches.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_group_submatches:NN #1#2
  {
    \seq_pop:NN \l_regex_capturing_group_seq \l_regex_internal_a_tl
    \int_compare:nNnF { \l_regex_internal_a_tl } < \c_zero
      {
        \regex_toks_put_left:Nx #1
          { \regex_action_submatch:n { \l_regex_internal_a_tl < } }
        \regex_toks_put_left:Nx #2
          { \regex_action_submatch:n { \l_regex_internal_a_tl > } }
      }
  }
%    \end{macrocode}
% \end{macro}
%
%   Most quantifiers require to add an extra state before the group.
%   This is done by shifting the current contents of the \cs{tex_toks:D}
%   \cs{l_regex_internal_a_int} to a new state.
%
% \begin{macro}[aux]{\regex_build_group_qs_aux:NN}
% \begin{macro}[aux]{\regex_build_group_?:}
% \begin{macro}[aux]{\regex_build_group_??:}
%   Shift the state at which the group begins using
%   \cs{regex_build_group_shift:N}, then add two transitions.
%   The first transition is taken once the group has been
%   traversed: in the case of \texttt{?} and \texttt{??},
%   we should exit by going to \cs{l_regex_right_state_int},
%   while for \texttt{*} and \texttt{*?} we loop by going to
%   \cs{l_regex_internal_a_int}.
%   The second transition corresponds to skipping the group;
%   it has lower priority (\texttt{put_right}) for greedy
%   operators, and higher priority (\texttt{put_left}) for
%   lazy operators.
%   We shift the left state to avoid interactions with
%   \texttt{action_submatch}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_qs_aux:
  {
    \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int
    \regex_build_new_state:
    \tex_toks:D \l_regex_right_state_int = \tex_toks:D \l_regex_internal_a_int
    \regex_toks_put_left:Nx \l_regex_right_state_int
      {
        \int_sub:Nn \l_regex_current_state_int
          {
            \int_eval:n % ^^A here we lie!
              { \l_regex_right_state_int - \l_regex_internal_a_int }
          }
      }
    \use:x
      {
        \tex_toks:D \l_regex_internal_a_int
          {
            \s_stop
            \regex_action_free:n
              {
                \int_eval:n
                  { \l_regex_right_state_int - \l_regex_internal_a_int }
              }
          }
      }
    \regex_build_group_submatches:NN
      \l_regex_right_state_int \l_regex_left_state_int
  }
\cs_new_protected:Npn \regex_build_group_qs_aux:NN #1#2
  {
    \regex_build_group_qs_aux:
    \int_set_eq:NN \l_regex_right_state_int \l_regex_left_state_int
    \regex_build_transition:NN \regex_action_free:n #1
    #2 \l_regex_internal_a_int
      {
        \regex_action_free:n
          { \int_eval:n { \l_regex_right_state_int - \l_regex_internal_a_int } }
      }
  }
\cs_new_protected_nopar:cpn { regex_build_group_?: }
  {
    \regex_build_group_qs_aux:NN
      \l_regex_right_state_int \regex_toks_put_right:Nx
  }
\cs_new_protected_nopar:cpn { regex_build_group_??: }
  {
    \regex_build_group_qs_aux:NN
      \l_regex_right_state_int \regex_toks_put_left:Nx
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_n_aux:n}
% \begin{macro}[aux]{\regex_build_group_transition_right_max:}
%   The braced quantifiers rely on replicating the states corresponding
%   to the group that has just been built, and joining the right state
%   of each copy to the left state of the next copy. Once this function
%   has been run, \cs{l_regex_internal_a_int} points to the last copy of
%   the initial left-most state, \cs{l_regex_left/right_state_int} have
%   their initial values. Furthermore, \cs{l_regex_max_state_int} is set
%   appropriately to the largest allocated \tn{toks} register plus $1$.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_group_transition_right_max:
  {
    \regex_toks_put_right:Nx \l_regex_right_state_int
      {
        \regex_action_free:n
          { \int_eval:n { \l_regex_max_state_int - \l_regex_right_state_int } }
      }
  }
\cs_new_protected:Npn \regex_build_group_n_aux:n #1
  {
    \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int
    \int_set_eq:NN \l_regex_internal_b_int \l_regex_max_state_int
    \int_add:Nn \l_regex_right_state_int
      { ( #1 - 1 ) * ( \l_regex_max_state_int - \l_regex_left_state_int ) }
    \int_set:Nn \l_regex_max_state_int
      {
        \l_regex_left_state_int
        + (#1) * ( \l_regex_max_state_int - \l_regex_left_state_int )
      }
    \int_while_do:nNnn \l_regex_internal_b_int < \l_regex_max_state_int
      {
        \tex_toks:D \l_regex_internal_b_int
          = \tex_toks:D \l_regex_internal_a_int
        \int_incr:N \l_regex_internal_a_int
        \int_incr:N \l_regex_internal_b_int
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_n:, \regex_build_group_n?:}
% \begin{macro}[aux]{\regex_build_group_:}
%   These functions are called in case the syntax is
%   \texttt{\{\meta{int}\}}, or in the absence of quantifier (with
%   $n=1$). Greedy and lazy operators are identical, since the number of
%   repetitions is fixed.  We only record the submatch information at
%   the last repetition; and of course, in the case $n=0$, we record
%   nothing.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_group_n: #1
  {
    \regex_build_group_transition_right_max:
    \regex_build_group_n_aux:n {#1}
    \regex_build_new_state:
    \int_compare:nNnF {#1} = \c_zero
      {
        \regex_build_group_submatches:NN
          \l_regex_internal_a_int \l_regex_left_state_int
      }
  }
\cs_new_eq:cN { regex_build_group_n?: } \regex_build_group_n:
\cs_new_protected_nopar:Npn \regex_build_group_:
  { \regex_build_group_n: \c_one }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_n*:, \regex_build_group_n*?:}
% \begin{macro}[aux]{\regex_build_group_*:, \regex_build_group_*?:}
% \begin{macro}[aux]{\regex_build_group_+:, \regex_build_group_+?:}
% \begin{macro}[aux]{\regex_build_group_n_star_aux:NNn}
%   These functions are called in case the syntax is
%   \texttt{\{\meta{int},\}}. They are somewhat hybrid between
%   the \texttt{\{\meta{int}\}} and the \texttt{*} quantifiers.
%   Contrarily to the \texttt{*} quantifier, for which we had
%   to be careful not to overwrite the submatch information in
%   case no iteration was made, here, we know that the submatch
%   information is overwritten in any case.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_group_n*: }
  {
    \regex_build_group_n_star_aux:NNn
      \regex_toks_put_right:Nx \regex_toks_put_left:Nx
  }
\cs_new_protected_nopar:cpn { regex_build_group_n*?: }
  {
    \regex_build_group_n_star_aux:NNn
      \regex_toks_put_left:Nx \regex_toks_put_right:Nx
  }
\cs_new_protected:Npn \regex_build_group_n_star_aux:NNn #1#2#3
  {
    \int_compare:nNnTF {#3} = \c_zero
      { \regex_build_group_qs_aux:NN \l_regex_internal_a_int #1 }
      {
        \regex_build_group_transition_right_max:
        \regex_build_group_n_aux:n {#3}
        \regex_build_new_state:
        #2 \l_regex_left_state_int
          {
            \regex_action_free:n
              {
                \int_eval:n
                  { \l_regex_internal_a_int - \l_regex_left_state_int }
              }
          }
        \regex_build_group_submatches:NN
          \l_regex_internal_a_int \l_regex_left_state_int
      }
  }
\cs_new_protected_nopar:cpx { regex_build_group_*: }
  { \exp_not:c { regex_build_group_n*: } \c_zero }
\cs_new_protected_nopar:cpx { regex_build_group_*?: }
  { \exp_not:c { regex_build_group_n*?: } \c_zero }
\cs_new_protected_nopar:cpx { regex_build_group_+: }
  { \exp_not:c { regex_build_group_n*: } \c_one }
\cs_new_protected_nopar:cpx { regex_build_group_+?: }
  { \exp_not:c { regex_build_group_n*?: } \c_one }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_nn:, \regex_build_group_nn?:}
% \begin{macro}[aux]{\regex_build_group_nn_aux:nnnn}
% \begin{macro}[aux, rEXP]{\regex_build_group_nn_aux_ii:w}
%   These functions are called when the syntax is either
%   \texttt{\{\meta{int},\}} or \texttt{\{\meta{int},\meta{int}\}}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_nn:
  {
    \regex_build_group_nn_aux:nnnn { }
      \regex_build_group_transition_right_max:
  }
\cs_new_protected_nopar:cpn { regex_build_group_nn?: }
  {
    \regex_build_group_nn_aux:nnnn { }
      {
        \use:x
          {
            \tex_toks:D \l_regex_right_state_int
              {
                \exp_after:wN \regex_build_group_nn_aux_ii:w
                \tex_the:D \tex_toks:D \l_regex_right_state_int
              }
          }
      }
  }
\cs_new_protected:Npn \regex_build_group_nn_aux:nnnn #1#2#3#4
  {
    \int_compare:nNnTF {#3} > {#4}
      {
        \msg_kernel_error:nnxxx
          { regex } { quantifier-backwards } {#3} {#4} {#1}
      }
      {
        \int_compare:nNnTF {#3} = \c_zero
          {
            \regex_build_group_qs_aux:
            \int_set_eq:NN \l_regex_right_state_int \l_regex_left_state_int
            \int_set_eq:NN \l_regex_left_state_int  \l_regex_internal_a_int
            \regex_build_group_transition_right_max:
            \regex_build_group_n_aux:n { #4 - #3 }
            \int_set_eq:NN \l_regex_internal_c_int \l_regex_right_state_int
            \int_set_eq:NN \l_regex_right_state_int \l_regex_left_state_int
            \prg_replicate:nn { #4 - #3 }
              {
                #2
                \int_add:Nn \l_regex_right_state_int
                  { \l_regex_internal_b_int - \l_regex_internal_a_int }
              }
            \int_set_eq:NN \l_regex_right_state_int \l_regex_internal_c_int
            \int_set_eq:NN \l_regex_left_state_int \l_regex_internal_a_int
            \regex_build_new_state:
          }
          {
            \regex_build_group_transition_right_max:
            \regex_build_group_n_aux:n {#3}
            \int_set_eq:NN \l_regex_left_state_int \l_regex_internal_a_int
            \regex_build_group_submatches:NN
              \l_regex_left_state_int \l_regex_right_state_int
            \regex_build_group_n_aux:n { #4 - #3 + \c_one }
            \int_sub:Nn \l_regex_right_state_int
              { \l_regex_internal_a_int - \l_regex_left_state_int }
            \prg_replicate:nn { #4 - #3 }
              {
                #2
                \int_add:Nn \l_regex_right_state_int
                  { \l_regex_internal_b_int - \l_regex_internal_a_int }
              }
            \int_set_eq:NN \l_regex_left_state_int \l_regex_internal_a_int
            \regex_build_new_state:
          }
      }
  }
\cs_new_protected:Npn \regex_build_group_nn_aux_ii:w #1 \regex_action_free:n
  {
    #1
    \regex_action_free:n
      {
        \int_eval:n
          { \l_regex_max_state_int - \l_regex_right_state_int }
      }
    \regex_action_free:n
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Matching raw token lists with \cs{u}}
%
%^^A todo: document interactions between caselessness and |\u{...}|
%^^A todo: clarify when l_regex_catcodes_int is reset.
%
% \begin{macro}[aux]{\regex_build_/u:}
% \begin{macro}[aux]{\regex_build_u_loop:NN}
%   The |\u| escape is invalid in classes nad directly following a
%   catcode test. Otherwise, it must be followed by a left brace. We
%   then collect the characters for the argument of |\u| within an
%   \texttt{x}-expanding assignment. In principle we could just wait to
%   encounter a right brace, but this is unsafe: if the right brace is
%   missing, then we will reach the end-markers of the regex, and
%   continue, leading to obscure fatal errors. Instead, we only allow
%   raw and special characters, and stop when encountering a special
%   right brace.
%    \begin{macrocode}
\cs_new_protected:cpn { regex_build_/u: } #1#2
  {
    \regex_build_if_assertions_forbidden:TF
      { \regex_build_raw_error:N u #1#2 }
      {
        \str_if_eq:xxTF {#1#2} { \regex_build_special:N \c_lbrace_str }
          {
            \tl_set:Nx \l_regex_internal_a_tl { \if_false: } \fi:
            \regex_build_u_loop:NN
          }
          {
            \msg_kernel_error:nn { regex } { u-missing-lbrace }
            #1#2
          }
      }
  }
\cs_new:Npn \regex_build_u_loop:NN #1#2
  {
    \token_if_eq_meaning:NNTF #1 \regex_build_raw:N
      { #2 \regex_build_u_loop:NN }
      {
        \token_if_eq_meaning:NNTF #1 \regex_build_special:N
          {
            \exp_after:wN \token_if_eq_charcode:NNTF \c_rbrace_str #2
              { \if_false: { \fi: } \regex_build_u_end: }
              { #2 \regex_build_u_loop:NN }
          }
          {
            \if_false: { \fi: }
            \msg_kernel_error:nnx { regex } { u-missing-rbrace } {#2}
            \regex_build_u_end:
            #1#2
          }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_u_end:}
%   Once we have extracted the variable's name, we store the contents of
%   that variable in \cs{l_regex_internal_a_tl}. The behaviour of |\u|
%   then depends on whether we are within a |\c{...}| escape (in this
%   case, the variable is turned to a string), or not. Afterwards, clean
%   up the value of \cs{l_regex_tests_tl}, but not
%   \cs{l_regex_tests_bool}, because this is guaranteed to be
%   \texttt{true} at the start, and is not affected by anything we do
%   here.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_u_end:
  {
    \tl_set:Nv \l_regex_internal_a_tl \l_regex_internal_a_tl
    \if_num:w \l_regex_build_mode_int = \c_zero
      \regex_build_u_not_cs:
    \else:
      \regex_build_u_in_cs:
    \fi:
    \tl_clear:N \l_regex_tests_tl
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_u_in_cs:}
%   When |\u| appears within a control sequence, the variable is
%   converted to a string, and we add to the NFA one state per
%   character. We use \cs{regex_build_one_:} directly, as this avoids
%   having to search for a quantifier.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_u_in_cs:
  {
    \exp_args:NNo \str_gset_other:Nn \g_regex_internal_tl
      { \l_regex_internal_a_tl }
    \tl_map_inline:Nn \g_regex_internal_tl
      {
        \tl_set:Nx \l_regex_tests_tl { \regex_item_equal:n { `##1 } }
        \regex_build_one_:
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_u_not_cs:}
%   In mode $0$, the |\u| escape adds one state to the NFA for each
%   token in \cs{l_regex_internal_a_tl}. The tests corresponding to a
%   given \meta{token} are: first test the category, then, if the
%   \meta{token} is a control sequence, compare the string
%   representations, otherwise compare the character codes. We could
%   compare the string representations in all cases, but that doesn't
%   interact well with caseless matching.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_build_u_not_cs:
  {
    \exp_args:No \tl_analysis_map_inline:nn { \l_regex_internal_a_tl }
      {
        \tl_set:Nx \l_regex_tests_tl
          {
            \exp_not:N \int_compare:nNnT
              \l_regex_current_catcode_int = { \int_value:w "##2 }
              {
                \int_compare:nNnTF { "##2 } = \c_zero
                  {
                    \exp_not:n
                      { \str_if_eq:xxT { \l_regex_current_token_tl } {##1} }
                      { \regex_break_true:w }
                  }
                  { \regex_item_equal:n {##3} }
              }
          }
        \regex_build_one_:
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsection{Matching}
%
% At every index,  we unpack  that array  of active states and
% empty it. Then loop over all active states, and perform the
% instruction  at  that state  of  the NFA.  This can involve
% \enquote{free} transitions to other states,  or transitions
% which  \enquote{consume}  the  current character.  For free
% transitions, the instruction at the new state of the NFA is
% performed.  When a transition consumes a character, the new
% state is put  in the array of \tn{skip} registers:  it will
% be active again when the next character is read.
%
% If two paths through the NFA \enquote{collide} in the sense
% that  they  reach  the  same state  when  reading  a  given
% character, then any future execution  will be identical for
% both.  Hence,  it is indeed enough  to keep track of  which
% states are active. [In the presence of back-references, the
% future execution is affected by how the previous match took
% place;  this  is why we  cannot  support  those non-regular
% features.]
%
% Many of the functions require extracting the submatches for
% the \enquote{best} match.  Execution paths  through the NFA
% are  ordered  by  precedence:  for  instance,  the  regular
% expression \texttt{a?}  creates two paths,  matching either
% an empty token list or a single \texttt{a}; the path matching
% an \texttt{a} has higher precedence. When two paths collide,
% the path with the highest precedence is kept, and the other
% one is discarded. The submatch information for a given path
% is stored  at  the start  of the  \tn{toks} register  which
% holds the state at which that path currently is.
%
% Deciding  to  store  the submatch information  in \tn{toks}
% registers alongside  with states  of the NFA  unfortunately
% implies some shuffling around. The two other options are to
% store the submatch information  in one control sequence per
% path, which wastes csnames, or to store all of the submatch
% information in one property list, which turns out to be too
% slow. A tricky aspect of submatch tracking  is to know when
% to get rid of submatch information.  This naturally happens
% when submatch information  is stored in \tn{toks} registers:
% if  the information  is not moved,  it will be  overwritten
% later.
%
% The presence  of $\epsilon$-transitions  (transitions which
% consume  no character)  leads to  potential  infinite loops;
% for instance the regular expression  |(a??)*| could lead to
% an infinite recursion, where |a??| matches no character, |*|
% loops back to the start of the group,  and |a??| matches no
% character again.  Therefore,  we need to  keep track of the
% states  of  the  NFA  visited  at  the  current step.  More
% precisely,  a state  is marked  as \enquote{visited} if the
% instructions for that state have been inserted in the input
% stream, by setting the corresponding \tn{dimen} register to
% a value which uniquely identifies at which step it was last
% inserted.
%
% \subsubsection{Helpers for running the NFA}
%
% \begin{macro}[aux]{\regex_store_state:n}
%   Put the given state in the array of \tn{skip} registers.
%   This is done by increasing the pointer
%   \cs{l_regex_max_active_int}, and converting the integer
%   to a dimension (suitable for a \tn{skip} assignment) in
%   scaled points.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_store_state:n #1
  {
    \int_incr:N \l_regex_max_active_int
    \tex_skip:D \l_regex_max_active_int #1 sp \scan_stop:
    \regex_store_submatches:n {#1}
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_state_use:}
% \begin{macro}[int]{\regex_state_use_with_submatches:}
% \begin{macro}[aux]{\regex_state_use_aux_ii:w}
% \begin{macro}[aux]{\regex_state_use_aux:n}
%   Use a given program instruction, unless it has already been
%   executed at this step. The \tn{toks} registers begin with
%   some submatch information, ignored by \cs{regex_state_use:},
%   but not by \cs{regex_state_use_with_submatches:}.
%   A state is free if it is not marker as taken, namely
%   if the corresponding \tn{dimen} register is not
%   \cs{l_regex_step_int} in \texttt{sp}.
%   The primitive conditional is ended before unpacking
%   the \tn{toks} register.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_state_use_with_submatches:
  { \regex_state_use_aux:n { } }
\cs_new_protected_nopar:Npn \regex_state_use:
  { \regex_state_use_aux:n { \exp_after:wN \use_none_delimit_by_s_stop:w } }
\cs_new_protected:Npn \regex_state_use_aux:n #1
  {
    \if_num:w \tex_dimen:D \l_regex_current_state_int < \l_regex_step_int
      \tex_dimen:D \l_regex_current_state_int
        = \l_regex_step_int sp \scan_stop:
      #1 \tex_the:D \tex_toks:D \exp_after:wN \l_regex_current_state_int
    \fi:
    \scan_stop:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Submatch tracking when running the NFA}
%
% \begin{macro}[int]{\regex_disable_submatches:}
%   Some user functions don't require tracking submatches.
%   We get a performance improvement by simply defining the
%   relevant functions to remove their argument and do nothing
%   with it.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_disable_submatches:
  {
    \cs_set_eq:NN \regex_state_use_with_submatches: \regex_state_use:
    \cs_set_eq:NN \regex_store_submatches:n
      \regex_protected_use_none:n
    \cs_set_eq:NN \regex_action_submatches:n
      \regex_protected_use_none:n
  }
\cs_new_protected:Npn \regex_protected_use_none:n #1 { }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_store_submatches:n}
% \begin{macro}[aux]{\regex_store_submatches_aux:w}
% \begin{macro}[aux]{\regex_store_submatches_aux_ii:Nnnw}
%   The submatch information pertaining to one given thread is moved
%   from state to state as we execute the NFA.
%   We make sure that most of the \tn{toks} register is not read
%   before being assigned again to that same register.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_store_submatches:n #1
  {
    \tex_toks:D #1 \exp_after:wN
      {
        \tex_romannumeral:D
        \exp_after:wN \regex_store_submatches_aux:w
        \tex_the:D \tex_toks:D #1
      }
  }
\cs_new_protected:Npn \regex_store_submatches_aux:w #1 \s_stop
  {
    \regex_store_submatches_aux_ii:Nnnw
      #1
      \regex_state_submatches:nn \c_minus_one \q_prop
    \s_stop
  }
\cs_new_protected:Npn \regex_store_submatches_aux_ii:Nnnw
    \regex_state_submatches:nn #1 #2 #3 \s_stop
  {
    \exp_after:wN \c_zero
    \exp_after:wN \regex_state_submatches:nn \exp_after:wN
      { \int_value:w \int_eval:w \l_regex_step_int + \c_one \exp_after:wN }
      \exp_after:wN { \l_regex_current_submatches_prop }
    \regex_state_submatches:nn {#1} {#2}
    \s_stop
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_state_submatches:nn}
%   This function is inserted by \cs{regex_store_submatches:n}
%   in the \tn{toks} register holding a given state, and it is
%   performed when the state is used.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_state_submatches:nn #1#2
  {
    \if_num:w #1 = \l_regex_step_int
      \tl_set:Nn \l_regex_current_submatches_prop { #2 }
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Matching: framework}
%
% \begin{macro}[int]{\regex_match:n}
%^^A todo: update doc.
%   Then reset a few variables which should be set only once,
%   before the first match, even in the case of multiple matches.
%   Then run the NFA (\cs{regex_match_once:} matches multiple times
%   when appropriate).
%    \begin{macrocode}
\cs_new_protected:Npn \regex_match:n #1
  {
    \int_zero:N \l_regex_nesting_int
    \int_set_eq:NN \l_regex_current_index_int \l_regex_max_state_int
    \regex_query_set:nnn { } { -1 } { -2 }
    \int_set_eq:NN \l_regex_min_index_int \l_regex_current_index_int
    \tl_analysis_map_inline:nn {#1}
      {
        \regex_query_set:nnn {##1} {"##2} {##3}
        \if_case:w "##2 \exp_stop_f:
        \or: \int_incr:N \l_regex_nesting_int
        \or: \int_decr:N \l_regex_nesting_int
        \fi:
      }
    \int_set_eq:NN \l_regex_max_index_int \l_regex_current_index_int
    \regex_query_set:nnn { } { -1 } { -2 }
    \regex_match_initial_setup:
    \regex_match_once:
  }
\cs_new_protected:Npn \regex_query_set:nnn #1#2#3
  {
    \tex_muskip:D \l_regex_current_index_int
      = \etex_gluetomu:D
        #3 sp
        plus #2 sp
        minus \l_regex_nesting_int sp
      \scan_stop:
    \tex_toks:D \l_regex_current_index_int {#1}
    \int_incr:N \l_regex_current_index_int
  }
\cs_new_protected_nopar:Npn \regex_query_get:
  {
    \tl_set:Nx \l_regex_current_token_tl
      { \tex_the:D \tex_toks:D \l_regex_current_index_int }
    \l_regex_current_char_int
      = \etex_mutoglue:D \tex_muskip:D \l_regex_current_index_int
    \l_regex_current_catcode_int = \etex_gluestretch:D
      \etex_mutoglue:D \tex_muskip:D \l_regex_current_index_int
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_match_once:}
%   Set up more variables in \cs{regex_match_setup:}.
%   If there was a match, use the token list \cs{l_regex_every_match_tl},
%   which may call \cs{regex_match_once:} again to achieve multiple matches.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_once:
  {
    \regex_match_setup:
    \regex_query_get:
    \regex_match_loop:
    \prg_break_point:n { }
    \bool_if:NT \l_regex_success_match_bool
      {
        \bool_gset_true:N \g_regex_success_bool
        \l_regex_every_match_tl
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_match_initial_setup:}
%   This function holds the setup that should be done
%   only once for one given pattern matching.
%   It is called only once for the whole token list.
%   On the other hand, \cs{regex_match_setup:}
%   is called for every match in the token list in case of
%   repeated matches.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_initial_setup:
  {
    \int_set_eq:NN \l_regex_step_int \c_minus_one
    \prg_stepwise_inline:nnnn
      \c_zero \c_one { \l_regex_max_state_int - \c_one }
      { \tex_dimen:D ##1 \l_regex_step_int sp \scan_stop: }
    \int_set:Nn \l_regex_start_index_int
      { \l_regex_min_index_int - \c_one }
    \int_set_eq:NN \l_regex_current_index_int \l_regex_min_index_int
    \int_set_eq:NN \l_regex_success_index_int \l_regex_min_index_int
    \int_set_eq:NN \l_regex_submatch_int \l_regex_max_state_int
    \bool_set_false:N \l_regex_success_empty_bool
    \bool_gset_false:N \g_regex_success_bool
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_match_setup:}
%   Every time a match starts, \cs{regex_match_setup:} resets
%   a few variables.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_setup:
  {
    \prop_clear:N \l_regex_current_submatches_prop
    \bool_if:NTF \l_regex_success_empty_bool
      { \cs_set_eq:NN \regex_if_two_empty_matches:F \regex_if_match_empty:F }
      { \cs_set_eq:NN \regex_if_two_empty_matches:F \use:n }
    \int_set_eq:NN \l_regex_start_index_int \l_regex_success_index_int
    \int_set:Nn \l_regex_current_index_int
      { \l_regex_start_index_int - \c_one }
    \bool_set_false:N \l_regex_success_match_bool
    \int_zero:N \l_regex_max_active_int
    \regex_store_state:n {0} %^^A _state_int!
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_match_loop:}
% \begin{macro}[aux]{\regex_match_one_active:n}
% \begin{macro}[aux]{\regex_match_one_active_aux:n}
%   Setup what needs to be reset at every character,
%   then set \cs{l_regex_current_char_int} to the
%   character code of the token that is read
%   (and $-1$ for the end of the token list), and loop
%   over the elements of the \tn{skip} array. Then repeat.
%   There are a couple of tests to stop reading the token list
%   when no active state is left, or when the end is reached.
%   At every step in reading the token list, we store the character
%   code of the current character in \cs{l_regex_current_char_int},
%   unless the end was reached: then we store $-1$.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_loop:
  {
    \int_incr:N \l_regex_current_index_int
    \int_incr:N \l_regex_step_int
    \bool_set_false:N \l_regex_fresh_thread_bool
    \int_set_eq:NN \l_regex_last_char_int \l_regex_current_char_int
    \regex_query_get:
    \regex_match_loop_case_hook:
    \use:x
      {
        \int_zero:N \l_regex_max_active_int
        \regex_match_one_active:w 1 ; \prg_break_point:n { }
        \exp_not:N \prg_break_point:n { }
      }
    \if_num:w \l_regex_current_char_int < \c_minus_one
      \exp_after:wN \prg_map_break:
    \fi:
    \if_num:w \l_regex_max_active_int = \c_zero
      \exp_after:wN \prg_map_break:
    \fi:
    \regex_match_loop:
  }
\cs_new:Npn \regex_match_one_active:w #1;
  {
    \if_num:w #1 > \l_regex_max_active_int
      \exp_after:wN \prg_map_break:
    \fi:
    \regex_match_one_active_aux:n
      { \int_value:w \tex_skip:D #1 }
    \exp_after:wN \regex_match_one_active:w
    \int_use:N \int_eval:w #1 + \c_one ;
  }
\cs_new_protected:Npn \regex_match_one_active_aux:n #1
  {
    \int_set:Nn \l_regex_current_state_int {#1}
    \prop_clear:N \l_regex_current_submatches_prop
    \regex_state_use_with_submatches:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\regex_match_loop_case_hook:}
% \begin{macro}{\regex_match_loop_caseless_hook:}
%   In the case where the regular expression contains caseless matching,
%   the \cs{regex_match_loop_case_hook:} (normally empty) is redefined
%   to set \cs{l_regex_case_changed_char_int} properly.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_loop_case_hook: { }
\cs_new_protected_nopar:Npn \regex_match_loop_caseless_hook:
  {
    \int_set_eq:NN \l_regex_case_changed_char_int \l_regex_current_char_int
    \if_num:w \l_regex_current_char_int < \c_ninety_one
      \if_num:w \l_regex_current_char_int < \c_sixty_five
      \else:
        \int_add:Nn \l_regex_case_changed_char_int { \c_thirty_two }
      \fi:
    \else:
      \if_num:w \l_regex_current_char_int < \c_one_hundred_twenty_three
        \if_num:w \l_regex_current_char_int < \c_ninety_seven
        \else:
          \int_sub:Nn \l_regex_case_changed_char_int { \c_thirty_two }
        \fi:
      \fi:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Actions when matching}
%
% \begin{macro}[int]{\regex_action_start_wildcard:}
%: the first state has a free transition to the second
%   state, where the regular expression really begins, and a costly
%   transition to itself, to try again at the next character. ^^A ??
%   The search is made unanchored at the start by putting
%   a free transition to the real start of the NFA, and a
%   costly transition to the same state, waiting for the
%   next token in the query. This combination
%   could be reused (with some changes). We sometimes need
%   to know that the match for a given thread starts at
%   this character. For that, we use the boolean
%   \cs{l_regex_fresh_thread_bool}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_action_start_wildcard:
  {
    \bool_set_true:N \l_regex_fresh_thread_bool
    \regex_action_free:n {1}
    \bool_set_false:N \l_regex_fresh_thread_bool
    \regex_action_cost:n {0}
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_action_cost:n}
%   A transition which consumes the current character and moves
%   to state |#1|.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_action_cost:n #1
  {
    \exp_args:Nf \regex_store_state:n
      { \int_eval:n { \l_regex_current_state_int + #1 } }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_action_success:}
%   There is a successful match when an execution path reaches
%   the end of the regular expression. Then store the current
%   step and submatches. The current step is then interrupted
%   with \cs{prg_map_break:},
%   and only paths with higher precedence are pursued further.
%   The values stored here may be overwritten by a later success
%   of a path with higher precedence.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_action_success:
  {
    \regex_if_two_empty_matches:F
      {
        \bool_set_true:N \l_regex_success_match_bool
        \bool_set_eq:NN \l_regex_success_empty_bool
          \l_regex_fresh_thread_bool
        \int_set_eq:NN \l_regex_success_index_int \l_regex_current_index_int
        \prop_set_eq:NN \l_regex_success_submatches_prop
          \l_regex_current_submatches_prop
        \prg_map_break:
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_action_free:n}
%   To copy a thread, check whether the program state has already
%   been used at this character. If not, store submatches in the
%   new state, and insert the instructions for that state in the
%   input stream.
%   Then restore the old value of \cs{l_regex_current_state_int}
%   and of the current submatches.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_action_free:n #1
  {
    \use:x
      {
        \int_add:Nn \l_regex_current_state_int {#1}
        \regex_state_use:
        \int_set:Nn \l_regex_current_state_int
          { \int_use:N \l_regex_current_state_int }
        \tl_set:Nn \exp_not:N \l_regex_current_submatches_prop
          { \exp_not:o \l_regex_current_submatches_prop }
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_action_submatch:n}
%   Update the current submatches with the information
%   from the current index.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_action_submatch:n #1
  {
    \prop_put:Nno \l_regex_current_submatches_prop {#1}
      { \int_use:N \l_regex_current_index_int }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{??}%^^A todo: title
%
% \begin{macro}{\regex_if_match_empty:T, \regex_if_match_empty:F}
%
%    \begin{macrocode}
\cs_new:Npn \regex_if_match_empty:T
  { \int_compare:nNnT \l_regex_start_index_int = \l_regex_current_index_int }
\cs_new:Npn \regex_if_match_empty:F
  { \int_compare:nNnF \l_regex_start_index_int = \l_regex_current_index_int }
%    \end{macrocode}
% \end{macro}
%
% \subsection{Replacement}
%
% \begin{macro}[rEXP]{\regex_submatch_nesting_aux:n}
%    \begin{macrocode}
\cs_new_protected:Npn \regex_submatch_nesting_aux:n #1
  {
    + \etex_glueshrink:D \etex_mutoglue:D \etex_muexpr:D
        \tex_muskip:D \etex_gluestretch:D \tex_skip:D #1
        - \tex_muskip:D \tex_skip:D #1
    \scan_stop:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_replacement:n}
%   Our goal here is to analyse the replacement text. First take care
%   of detecting escaped and non-escaped characters using
%   \cs{regex_escape_use:nnnn} with three protected arguments.
%   This inserts in the input stream a token list of the form
%   \meta{fn 1} \meta{char 1} \ldots{} \meta{fn $N$} \meta{char $N$},
%   where \meta{fn $i$} is one of the three functions, and \meta{char $i$}
%   a character in the string |#1|.
%    \begin{macrocode}
\cs_new:Npn \regex_nesting:n #1 { } %^^A move. Rename?
\tl_new:N \l_regex_nesting_tl
\cs_new_protected:Npn \regex_replacement:n #1
  {
    \int_zero:N \l_regex_replacement_int
    \int_zero:N \l_regex_nesting_int
    \tl_clear:N \l_regex_nesting_tl
    \regex_escape_use:nnnn
      { \regex_replacement_unescaped:N ##1 }
      { \regex_replacement_escaped:N ##1 }
      { \regex_replacement_raw:N ##1 }
      {#1}
    \prg_do_nothing: \prg_do_nothing:
    \cs_set:Npx \regex_nesting:n ##1
      {
        + \int_use:N \l_regex_nesting_int
        \l_regex_nesting_tl
        - \regex_submatch_nesting_aux:n {##1}
      }
    \use:x
      {
        \exp_not:n { \cs_set:Npn \regex_replacement_tl:n ##1 }
          { \regex_toks_range:nn \c_zero \l_regex_replacement_int }
      }
      % ^^A rename!
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_replacement_raw:N}
%    \begin{macrocode}
\cs_new_protected:Npn \regex_replacement_raw:N #1
  { \regex_replacement_put:n {#1} }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_replacement_put:n}
%   Raw characters are stored in a toks register.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_replacement_put:n #1
  {
    \tex_toks:D \l_regex_replacement_int {#1}
    \int_incr:N \l_regex_replacement_int
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_replacement_escaped:N}
% \begin{macro}[aux]{\regex_replacement_submatch:w}
% \begin{macro}[aux]{\regex_replacement_submatch_aux:nN}
%    \begin{macrocode}
\cs_new_protected:Npn \regex_replacement_unescaped:N #1
  {
    \if_charcode:w \c_rbrace_str #1
      \if_num:w \l_regex_replacement_csnames_int > \c_zero
        \regex_replacement_put:n \cs_end:
      \else:
        \regex_replacement_put:n #1
      \fi:
    \else:
      \regex_replacement_put:n #1
    \fi:
  }
\cs_new_protected:Npn \regex_replacement_escaped:N #1
  {
    \cs_if_exist_use:cF { regex_replacement_#1:w }
      {
        \if_num:w \c_one < 1#1 \exp_stop_f:
          \regex_replacement_put_submatch:n {#1}
        \else:
          \regex_replacement_put:n #1
        \fi:
      }
  }
\cs_new_protected:Npn \regex_replacement_put_submatch:n #1
  {
    \regex_replacement_put:n
      { \regex_query_submatch:nn {#1} {##1} }
    \if_num:w \l_regex_replacement_csnames_int = \c_zero
      \tl_put_right:Nn \l_regex_nesting_tl
        {
          \exp_not:N \if_num:w #1 < \l_regex_capturing_group_int
            \regex_submatch_nesting_aux:n { \int_eval:w #1+##1 \int_eval_end: }
          \exp_not:N \fi:
        }
    \fi:
  }
\cs_new_protected:Npn \regex_replacement_error:NNN #1#2#3
  {
    \msg_kernel_error:nnxx { regex } { #1-command }
      { replacement~text } {#3}
    #2 #3
  }
\cs_new_protected:Npn \regex_replacement_g:w #1#2
  {
    \str_if_eq:xxTF
      { \exp_not:n { #1#2 } }
      { \regex_replacement_unescaped:N \c_lbrace_str }
      {
        \int_zero:N \l_regex_internal_a_int
        \regex_replacement_g_digits:NN
      }
      { \regex_replacement_error:NNN g #1 #2 }
  }
\cs_new_protected:Npn \regex_replacement_g_digits:NN #1#2
  {
    \token_if_eq_meaning:NNTF #1 \regex_replacement_unescaped:N
      {
        \if_num:w \c_one < 1#2 \exp_stop_f:
          \int_set:Nn \l_regex_internal_a_int { \c_ten * \l_regex_internal_a_int + #2 }
          \exp_after:wN \use_i:nnn
          \exp_after:wN \regex_replacement_g_digits:NN
        \else:
          \if_charcode:w \c_rbrace_str #2
            \exp_args:No \regex_replacement_put_submatch:n
              { \int_use:N \l_regex_internal_a_int }
            \exp_after:wN \exp_after:wN \exp_after:wN \use_none:nn
          \else:
            \exp_after:wN \exp_after:wN
            \exp_after:wN \regex_replacement_error:NNN
            \exp_after:wN \exp_after:wN \exp_after:wN g
          \fi:
        \fi:
      }
      { \regex_replacement_error:NNN g }
    #1 #2
  }
\cs_new_protected:Npn \regex_replacement_u:w #1#2
  {
    \str_if_eq:xxTF { #1#2 } { \regex_replacement_unescaped:N \c_lbrace_str }
      {
        \int_incr:N \l_regex_replacement_csnames_int
        \regex_replacement_put:n
          { \exp_not:n { \exp_after:wN \exp_not:V \cs:w } }
      }
      { \regex_replacement_error:NNN u #1#2 }
  }
\cs_new_protected:Npn \regex_replacement_c:w #1#2
  {
    \token_if_eq_meaning:NNTF #1 \regex_replacement_unescaped:N
      {
        \cs_if_exist_use:cF { regex_replacement_c_#2:w }
          { \regex_replacement_error:NNN c #1#2 }
      }
      { \regex_replacement_error:NNN c #1#2 }
  }
\cs_new_protected_nopar:cpn { regex_replacement_c_ \c_lbrace_str :w }
  {
    \int_incr:N \l_regex_replacement_csnames_int
    \regex_replacement_put:n
      { \exp_not:n { \exp_after:wN \regex_replacement_exp_not:N \cs:w } }
  }
\cs_new:Npn \regex_replacement_exp_not:N #1 { \exp_not:n {#1} }
\group_begin:

  \char_set_catcode_math_superscript:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_U:w
    { \regex_replacement_char:nNN { ^^@ } }

  \char_set_catcode_alignment:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_T:w
    { \regex_replacement_char:nNN { ^^@ } }

  \cs_new_protected:Npn \regex_replacement_c_S:w #1#2
    {
      \int_compare:nNnTF { `#2 } = \c_zero
        { \regex_replacement_error:NNN c #1#2 }
        {
          \char_set_lccode:nn {32} { `#2 }
          \tl_to_lowercase:n { \regex_replacement_put:n {~} }
        }
    }

  \char_set_catcode_parameter:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_P:w
    { \regex_replacement_char:nNN { ^^@^^@^^@^^@^^@^^@^^@^^@ } }

  \char_set_catcode_other:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_O:w
    { \regex_replacement_char:nNN { ^^@ } }

  \char_set_catcode_math_toggle:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_M:w
    { \regex_replacement_char:nNN { ^^@ } }

  \char_set_catcode_letter:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_L:w
    { \regex_replacement_char:nNN { ^^@ } }

  \char_set_catcode_group_end:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_E:w
    {
      \int_decr:N \l_regex_nesting_int
      \regex_replacement_char:nNN { \if_false: { \fi:  ^^@ }
    }

  \char_set_catcode_math_subscript:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_D:w
    { \regex_replacement_char:nNN { ^^@ } }

  \char_set_catcode_group_begin:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_B:w
    {
      \int_incr:N \l_regex_nesting_int
      \regex_replacement_char:nNN { \exp_after:wN ^^@ \if_false: } \fi: }
    }

  \char_set_catcode_active:N \^^@
  \cs_new_protected_nopar:Npn \regex_replacement_c_A:w
    { \regex_replacement_char:nNN { \exp_not:N ^^@ } }

\group_end:

\cs_new_protected:Npn \regex_replacement_char:nNN #1#2#3
  {
    \char_set_lccode:nn \c_zero { `#3 }
    \tl_to_lowercase:n
      { \regex_replacement_put:n { \exp_not:n {#1} } }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsection{User commands}
%
% \subsubsection{Precompiled pattern}
%
% A given pattern is often reused to match many different query token lists.
% We thus give a means of storing the NFA corresponding to a given
% pattern in a token list variable of the form
% \begin{quote}
%   \cs{regex_nfa:Nw} \meta{variable~name} \\
%   \meta{assignments} \\
%   \cs{tex_toks:D} 0 \{ \meta{instruction0} \} \\
%   \ldots{}                              \\
%   \cs{tex_toks:D} $n$ \{ \meta{instruction$\sb{n}$} \} \\
%   \cs{s_stop}
% \end{quote}
% where $n$ is the number of states in the NFA,
% and the various \meta{instruction$\sb{i}$} control
% how the NFA behaves in state $i$. The \cs{regex_nfa:Nw}
% function removes the whole NFA from the input stream
% and produces an error: the \meta{nfa var} should only be
% accessed through dedicated functions. This rather drastic
% approach is taken because assignments triggered by the
% contents of \meta{nfa var} may overwrite data which is used
% elsewhere, unless everything is done carefully in a group.
%
% \begin{macro}{\regex_gset:Nn}
% \begin{macro}{\regex_const:Nn}
% \begin{macro}{\regex_set:Nn}
% \begin{macro}[aux]{\regex_set_aux:NNn}
%   The three user functions only differ with which function is used
%   to assign the pre-compiled regular expression to the user's variable.
%   Internally, they all first build the NFA corresponding to the regex,
%   then store the contents of all the necessary \tn{toks} registers
%   in the user's variable.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_set:Nn
  { \regex_set_aux:NNn \tl_set:Nn }
\cs_new_protected_nopar:Npn \regex_gset:Nn
  { \regex_set_aux:NNn \tl_gset:Nn }
\cs_new_protected_nopar:Npn \regex_const:Nn
  { \regex_set_aux:NNn \tl_const:Nn }
\cs_new_protected:Npn \regex_set_aux:NNn #1#2#3
  {
    \group_begin:
      \regex_build:n {#3}
      \use:x
        {
          \group_end:
          #1 \exp_not:N #2 { \regex_set_aux:N #2 }
        }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int, rEXP]{\regex_set_aux:N}
% \begin{macro}[aux, rEXP]{\regex_set_aux:n}
% \begin{macro}[aux, EXP]{\regex_nfa:Nw}
%   Within a group, build the NFA corresponding to the given regular
%   expression, with submatch tracking. Then save the contents of all
%   relevant \tn{toks} registers into the variable outside the group.
%   The auxiliary \cs{regex_nfa:Nw} is not protected: this ensures that
%   the NFA will properly be replaced by an error message in expansion
%   contexts.
%    \begin{macrocode}
\cs_new:Npn \regex_set_aux:N #1
  {
    \exp_not:n { \regex_nfa:Nw #1 }
    \l_regex_max_state_int
      = \int_use:N \l_regex_max_state_int
    \l_regex_capturing_group_int
      = \int_use:N \l_regex_capturing_group_int
    \token_if_eq_meaning:NNT
      \regex_match_loop_case_hook:
      \regex_match_loop_caseless_hook:
      {
        \cs_set_eq:NN \regex_match_loop_case_hook:
          \regex_match_loop_caseless_hook:
      }
    \prg_stepwise_function:nnnN
      \c_zero \c_one {\l_regex_max_state_int - \c_one }
      \regex_set_aux:n
    \s_stop
  }
\cs_new:Npn \regex_set_aux:n #1
  { \tex_toks:D #1 { \tex_the:D \tex_toks:D #1 } }
\cs_new:Npn \regex_nfa:Nw #1
  {
    \msg_expandable_kernel_error:nnn { regex } { nfa-misused } {#1}
    \use_none_delimit_by_s_stop:w
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int]{\regex_use:N}
%   No error-checking.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_use:N
  { \exp_last_unbraced:No \use_none:nn }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Generic auxiliary functions}
%
% Most of \pkg{l3regex}'s work is done within a group.
%
% \begin{macro}[aux]{\regex_aux_return:}
%   This function triggers either \cs{prg_return_false:}
%   or \cs{prg_return_true:} as appropriate to whether a
%   match was found or not.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_aux_return:
  {
    \if_meaning:w \c_true_bool \g_regex_success_bool
      \prg_return_true:
    \else:
      \prg_return_false:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\regex_aux_build_match:nn}
%   This auxiliary is used by user functions whose \meta{regex} argument
%   is given as an explicit regular expression within braces. In that
%   case, we need to build the automaton corresponding to that regular
%   expression, then perform the matching on the given token list |#2|.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_aux_build_match:nn #1#2
  {
    \regex_build:n {#1}
    \regex_match:n {#2}
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\regex_aux_use_match:Nn}
%   This auxiliary is used by user functions whose \meta{regex} argument
%   is given as a pre-compiled regex variable. We make sure that
%   the token list variable indeed is an automaton (by testing the
%   first token). If not, the match is deemed unsuccessful, after
%   raising an error. If we have an automaton, \enquote{use} it,
%   then perform the matching on the given token list |#2|.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_aux_use_match:Nn #1#2
  {
    \exp_args:No \tl_if_head_eq_meaning:nNTF {#1} \regex_nfa:Nw
      {
        \regex_use:N #1
        \regex_match:n {#2}
      }
      {
        \msg_kernel_error:nnx { regex } { not-nfa } { \token_to_str:N #1 }
        \bool_gset_false:N \g_regex_success_bool
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}
%   {
%     \regex_extract_once:nnN, \regex_extract_once:NnN,
%     \regex_extract_all:nnN,  \regex_extract_all:NnN,
%     \regex_replace_once:nnN, \regex_replace_once:NnN,
%     \regex_replace_all:nnN,  \regex_replace_all:NnN,
%     \regex_split:nnN,        \regex_split:NnN
%   }
% \begin{macro}[TF]
%   {
%     \regex_extract_once:nnN, \regex_extract_once:NnN,
%     \regex_extract_all:nnN,  \regex_extract_all:NnN,
%     \regex_replace_once:nnN, \regex_replace_once:NnN,
%     \regex_replace_all:nnN,  \regex_replace_all:NnN,
%     \regex_split:nnN,        \regex_split:NnN
%   }
%   We define here $40$ user functions, following a common pattern
%   in terms of an auxiliary such as \cs{regex_extract_once_aux:NnnN}
%   (those auxiliaries are defined in the coming sections).
%   The arguments handed to the auxiliary are
%   \cs{regex_aux_build_match:nn} or \cs{regex_aux_use_match:Nn},
%   followed by the three arguments of the user function.
%   The conditionals call \cs{regex_aux_return:} to return
%   either \texttt{true} or \texttt{false} once matching
%   has been performed.
%    \begin{macrocode}
\cs_set_protected:Npn \regex_tmp:w #1#2#3
  {
    \cs_new_protected_nopar:Npn #1
      { #3 \regex_aux_build_match:nn }
    \cs_new_protected_nopar:Npn #2
      { #3 \regex_aux_use_match:Nn }
    \prg_new_protected_conditional:Npnn #1 ##1##2##3 { T , F , TF }
      {
        #3 \regex_aux_build_match:nn {##1} {##2} ##3
        \regex_aux_return:
      }
    \prg_new_protected_conditional:Npnn #2 ##1##2##3 { T , F , TF }
      {
        #3 \regex_aux_use_match:Nn {##1} {##2} ##3
        \regex_aux_return:
      }
  }
\tl_map_inline:nn
  {
    { extract_once } { extract_all }
    { replace_once } { replace_all }
    { split }
  }
  {
    \exp_args:Nccc \regex_tmp:w
      { regex_#1:nnN } { regex_#1:NnN } { regex_#1_aux:NnnN }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Submatches, once the correct match is found}
%
% \begin{macro}[int]{\regex_extract:}
% \begin{macro}[aux]{\regex_extract_aux_b:wn}
% \begin{macro}[aux]{\regex_extract_aux_e:wn}
%
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_extract:
  {
    \int_set_eq:NN \l_regex_submatch_start_int \l_regex_submatch_int
    \if_meaning:w \c_true_bool \g_regex_success_bool
      \prg_replicate:nn \l_regex_capturing_group_int
        {
          \tex_skip:D \l_regex_submatch_int \c_zero sp \scan_stop:
          \int_incr:N \l_regex_submatch_int
        }
      \prop_map_inline:Nn \l_regex_success_submatches_prop
        {
          \if_num:w ##1 \c_max_int
            \exp_after:wN \regex_extract_aux_b:wn \int_use:N
          \else:
            \exp_after:wN \regex_extract_aux_e:wn \int_use:N
          \fi:
          \int_eval:w \l_regex_submatch_start_int + ##1 {##2}
        }
    \fi:
  }
\cs_new_protected:Npn \regex_extract_aux_b:wn #1 < #2
  {
    \tex_skip:D #1 = #2 sp
      plus \etex_gluestretch:D \tex_skip:D #1 \scan_stop:
  }
\cs_new_protected:Npn \regex_extract_aux_e:wn #1 > #2
  {
    \tex_skip:D #1
      = 1 \tex_skip:D #1 plus #2 sp \scan_stop:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\regex_group_end_extract_seq:N}
% \begin{macro}[aux]{\regex_extract_seq_aux:n}
% \begin{macro}[aux]{\regex_extract_seq_aux:ww}
%    \begin{macrocode}
\cs_new_protected:Npn \regex_group_end_extract_seq:N #1
  {
      \cs_set_eq:NN \seq_item:n \scan_stop:
      \flag_clear:n { regex_begin }
      \flag_clear:n { regex_end }
      \tl_set:Nx \l_regex_internal_a_tl
        {
          \prg_stepwise_function:nnnN
            \l_regex_max_state_int
            \c_one
            { \l_regex_submatch_int - \c_one }
            \regex_extract_seq_aux:n
        }
      \int_compare:nNnF
        { \flag_height:n { regex_begin } + \flag_height:n { regex_end } }
        = \c_zero
        { \msg_kernel_error:nn { regex } { sequence-unbalanced } }
      \tl_set:Nx \l_regex_internal_a_tl { \l_regex_internal_a_tl }
    \exp_args:NNNo \group_end:
    \tl_set:Nn #1 \l_regex_internal_a_tl
  }
\cs_new:Npn \regex_extract_seq_aux:n #1
  {
    \seq_item:n
      {
        \exp_after:wN \regex_extract_seq_aux:ww
        \int_value:w \regex_submatch_nesting_aux:n {#1} ; #1;
      }
  }
\cs_new:Npn \regex_extract_seq_aux:ww #1; #2;
  {
    \if_num:w #1 < \c_zero
      \flag_raise:n { regex_end }
      \prg_replicate:nn {-#1} { \exp_not:n { { \if_false: } \fi: } }
    \fi:
    \regex_query_submatch:w #2;
    \if_num:w #1 > \c_zero
      \flag_raise:n { regex_begin }
      \prg_replicate:nn {#1} { \exp_not:n { \if_false: { \fi: } } }
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Matching}
%
% \begin{macro}[TF]{\regex_match:nn}
% \begin{macro}[TF]{\regex_match:Nn}
% \begin{macro}{\regex_match_aux:n}
%   We don't track submatches. Then either build the NFA corresponding
%   to the regular expression, or use a precompiled pattern. Then match,
%   using the internal \cs{regex_match:n}. Finally return the result
%   after closing the group.
%    \begin{macrocode}
\prg_new_protected_conditional:Npnn \regex_match:nn #1#2 { T , F , TF }
  {
    \regex_match_aux:n
      { \regex_aux_build_match:nn {#1} {#2} }
  }
\prg_new_protected_conditional:Npnn \regex_match:Nn #1#2 { T , F , TF }
  {
    \regex_match_aux:n
      { \regex_aux_use_match:Nn #1 {#2} }
  }
\cs_new_protected:Npn \regex_match_aux:n #1
  {
    \group_begin:
      \tl_clear:N \l_regex_every_match_tl
      \regex_disable_submatches:
      #1
    \group_end:
    \regex_aux_return:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\regex_count:nnN}
% \begin{macro}{\regex_count:NnN}
% \begin{macro}{\regex_count_aux:n}
%   Instead of aborting once the first \enquote{longest match} is found,
%   we repeat the search. The code is such that the search will not
%   start on the same character, hence avoiding infinite loops.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_count:nnN
  { \regex_count_aux:NnnN \regex_aux_build_match:nn }
\cs_new_protected_nopar:Npn \regex_count:NnN
  { \regex_count_aux:NnnN \regex_aux_use_match:Nn }
\cs_new_protected:Npn \regex_count_aux:NnnN #1#2#3#4
  {
    \group_begin:
      \regex_disable_submatches:
      \int_zero:N \l_regex_match_count_int
      \tl_set:Nn \l_regex_every_match_tl
        {
          \int_incr:N \l_regex_match_count_int
          \regex_match_once:
        }
      #1 {#2} {#3}
      \exp_args:NNNo
    \group_end:
    \int_set:Nn #4 { \int_use:N \l_regex_match_count_int }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Submatch extraction}
%
% \begin{macro}[aux]{\regex_extract_once_aux:NnnN}
%   As announced, here comes the auxiliary for extracting one match.
%   Since we only want one match, \cs{l_regex_every_match_tl}
%   is empty, and does not trigger the matching code again.
%   After matching, \cs{regex_extract:} extracts submatches
%   into various \tn{skip} registers, and those are then concatenated
%   into a sequence by \cs{regex_group_end_extract_seq:N}. That function
%   is also responsible for closing the group.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_extract_once_aux:NnnN #1#2#3#4
  {
    \group_begin:
      \tl_set:Nn \l_regex_every_match_tl { \regex_extract: }
      #1 {#2} {#3}
      \regex_group_end_extract_seq:N #4
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_extract_all_aux:NnnN}
%^^A todo: update doc
%   The set of submatches will be built progressively
%   in \cs{l_regex_result_seq}. For each match, extract
%   the submatches, and concatenate that to the right of
%   the result sequence, then start matching again.
%   Finally, copy the result in the user's sequence variable.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_extract_all_aux:NnnN #1#2#3#4
  {
    \group_begin:
      \tl_set:Nn \l_regex_every_match_tl
        { \regex_extract: \regex_match_once: }
      #1 {#2} {#3}
      \regex_group_end_extract_seq:N #4
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Splitting a token list by matches of a regex}
%
% \begin{macro}[aux]{\regex_split_aux:NnnN}
%   Recurse through the matches, and for each, do the following.
%   Extract the submatches into various \tn{skip} registers,
%   then replace the match |\0|, which should not be kept in the
%   final result, and replace it by the part of the token list
%   before the match.
%   This process must be inhibited to avoid creating empty items
%   if the regex matched an empty token list at the place where
%   the match attempt started.
%   After the last successful match, we need to add to the result
%   the part of the token list after the last match, unless the
%   last match was empty and at the very end.
%   Finally, \cs{regex_group_end_extract_seq:N} builds a sequence
%   from all the \tn{skip} registers, and assigns it to |#4|
%   after closing the group.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_split_aux:NnnN #1#2#3#4
  {
    \group_begin:
      \tl_set:Nn \l_regex_every_match_tl
        {
          \if_num:w \l_regex_start_index_int < \l_regex_success_index_int
            \regex_extract:
            \tex_skip:D \l_regex_submatch_start_int
              = \l_regex_start_index_int sp
                plus \tex_skip:D \l_regex_submatch_start_int \scan_stop:
          \fi:
          \regex_match_once:
        }
      #1 {#2} {#3}
      \tex_skip:D \l_regex_submatch_int
        = \l_regex_start_index_int sp
          plus \l_regex_current_index_int sp \scan_stop:
      \int_incr:N \l_regex_submatch_int
      \if_num:w \l_regex_start_index_int = \l_regex_current_index_int
        \if_meaning:w \c_true_bool \l_regex_success_empty_bool
          \int_decr:N \l_regex_submatch_int
        \fi:
      \fi:
      \regex_group_end_extract_seq:N #4
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Replacement}
%
% \begin{macro}[aux]{\regex_replace_once_aux:NnnN}
%   The replacement text is analysed by \cs{regex_replacement:n},
%   which defines \cs{regex_replacement_tl:n} to expand to the
%   replaced token list, assuming that submatches are stored in
%   various \tn{skip} registers, as done by \cs{regex_extract:}.
%   If there is a match, we grab
%   the parts before and after it, and get the result
%   by \texttt{x}-expanding twice.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_replace_once_aux:NnnN #1#2#3#4
  {
    \group_begin:
      \tl_clear:N \l_regex_every_match_tl
      \regex_replacement:n {#3}
      \exp_args:Nno #1 {#2} #4
      \if_meaning:w \c_true_bool \g_regex_success_bool
        \regex_extract:
        \int_set:Nn \l_regex_internal_a_int
          { \regex_nesting:n { \l_regex_submatch_start_int } }
        \if_num:w \l_regex_internal_a_int = \c_zero
        \else:
          \msg_kernel_error:nnx { regex } { replace-unbalanced }
            { \l_regex_internal_a_int }
        \fi:
        \tl_set:Nx \l_regex_internal_a_tl
          {
            \if_num:w \l_regex_internal_a_int < \c_zero
              \prg_replicate:nn { - \l_regex_internal_a_int }
                { \exp_not:n { { \if_false: } \fi: } }
            \fi:
            \regex_toks_range:nn
              { \l_regex_min_index_int }
              { \tex_skip:D \l_regex_submatch_start_int }
            \regex_replacement_tl:n { \l_regex_submatch_start_int }
            \regex_toks_range:nn
              { \etex_gluestretch:D \tex_skip:D \l_regex_submatch_start_int }
              { \l_regex_max_index_int }
            \if_num:w \l_regex_internal_a_int > \c_zero
              \prg_replicate:nn { \l_regex_internal_a_int }
                { \exp_not:n { \if_false: { \fi: } } }
            \fi:
          }
        \tl_set:Nx \l_regex_internal_a_tl { \l_regex_internal_a_tl }
        \exp_args:NNNo \group_end:
        \tl_set:Nn #4 \l_regex_internal_a_tl
      \else:
        \group_end:
      \fi:
  }
\cs_new_protected:Npn \regex_replace_once_aux:w #1;
  {
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_replace_all_aux:NnnN}
%   For every match, extract submatches, and add the part before
%   the beginning of the match, as well as the replacement,
%   to the result. After the last match, extract the end
%   of the token list, and add it to the replaced token list.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_replace_all_aux:NnnN #1#2#3#4
  {
    \group_begin:
      \tl_set:Nn \l_regex_every_match_tl
        {
          \regex_extract:
          \tex_skip:D \l_regex_submatch_start_int
            = \tex_the:D \tex_skip:D \l_regex_submatch_start_int
              minus \l_regex_start_index_int sp \scan_stop:
          \regex_match_once:
        }
      \regex_replacement:n {#3}
      \exp_args:Nno #1 {#2} #4
      \int_set:Nn \l_regex_internal_a_int
        {
          0
          \prg_stepwise_function:nnnN
            \l_regex_max_state_int
            \l_regex_capturing_group_int
            { \l_regex_submatch_int - \c_one }
            \regex_nesting:n
        }
      \if_num:w \l_regex_internal_a_int = \c_zero
      \else:
        \msg_kernel_error:nnx { regex } { replace-unbalanced }
          { \l_regex_internal_a_int }
      \fi:
      \tl_set:Nx \l_regex_internal_a_tl
        {
          \if_num:w \l_regex_internal_a_int < \c_zero
            \prg_replicate:nn { - \l_regex_internal_a_int }
              { \exp_not:n { { \if_false: } \fi: } }
          \fi:
          \prg_stepwise_function:nnnN
            \l_regex_max_state_int
            \l_regex_capturing_group_int
            { \l_regex_submatch_int - \c_one }
            \regex_replace_all_aux:n
          \regex_toks_range:nn
            \l_regex_start_index_int \l_regex_max_index_int
          \if_num:w \l_regex_internal_a_int > \c_zero
            \prg_replicate:nn { \l_regex_internal_a_int }
              { \exp_not:n { \if_false: { \fi: } } }
          \fi:
        }
      \tl_set:Nx \l_regex_internal_a_tl { \l_regex_internal_a_tl }
    \exp_args:NNNo \group_end:
    \tl_set:Nn #4 \l_regex_internal_a_tl
  }
\cs_new:Npn \regex_replace_all_aux:n #1
  {
    \regex_toks_range:nn
      { \etex_glueshrink:D \tex_skip:D #1 } { \tex_skip:D #1 }
    \regex_replacement_tl:n {#1}
  }
%    \end{macrocode}
% \end{macro}
%
% \subsection{Messages}
%
% Messages for the preparsing phase.
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { trailing-backslash }
  { Trailing~escape~character~\iow_char:N\\. }
  {
    A~regular~expression~or~its~replacement~text~ends~with~
    the~escape~character~\iow_char:N\\.~It~will~be~ignored.
  }
\msg_kernel_new:nnnn { regex } { x-missing-rbrace }
  { Missing~closing~brace~in~\iow_char:N\\x~hexadecimal~sequence. }
  {
    You~wrote~something~like~
    `\iow_char:N\\x\{\int_to_hexadecimal:n{#1}'.~
    The~closing~brace~is~missing.
  }
\msg_kernel_new:nnnn { regex } { x-overflow }
  { Character~code~'#1'~too~large~in~\iow_char:N\\x~hexadecimal~sequence. }
  {
    You~wrote~something~like~
    `\iow_char:N\\x\{\int_to_hexadecimal:n{#1}\}'.~
    The~character~code~'#1'~is~larger~than~\int_use:N \c_max_char_int.
  }
%    \end{macrocode}
%
% Messages for missing or extra closing brackets and parentheses, with
% some fancy singular/plural handling for the case of parentheses.
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { missing-rbrack }
  { Missing~right~bracket~inserted~in~regular~expression. }
  {
    LaTeX~was~given~a~regular~expression~where~a~character~class~
    was~started~with~'[',~but~the~matching~']'~is~missing.
  }
\msg_kernel_new:nnnn { regex } { missing-rparen }
  {
    Missing~right~parenthes\int_compare:nTF{#1=1}{i}{e}s~
    inserted~in~regular~expression.
  }
  {
    LaTeX~was~given~a~regular~expression~with~\int_eval:n{#1}~
    more~left~parenthes\int_compare:nTF{#1=1}{i}{e}s~than~right~
    parenthes\int_compare:nTF{#1=1}{i}{e}s.
  }
\msg_kernel_new:nnnn { regex } { extra-rparen }
  { Extra~right~parenthesis~ignored~in~regular~expression. }
  {
    LaTeX~came~across~a~closing~parenthesis~when~no~submatch~group~
    was~open.~The~parenthesis~will~be~ignored.
  }
%    \end{macrocode}
%
% Sometimes escaped alphanumerics are not allowed everywhere.
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { class-bad-escape }
  { Invalid~escape~\c_backslash_str #1~in~character~class. }
  {
    The~escape~sequence~\iow_char:N\\#1~may~not~appear~within~
    a~character~class.~For~instance,~assertions~(which~match~zero~
    characters)~would~not~make~sense~there.
  }
\msg_kernel_new:nnnn { regex } { catcode-bad-escape }
  { Invalid~escape~\c_backslash_str #1~following~category~test. }
  {
    The~escape~sequence~\iow_char:N\\#1~may~not~appear~following~
    a~category~test~such~as~\iow_char:N\\cL~or~
    \iow_char:N\\c[\iow_char:N\^BE].
  }
%    \end{macrocode}
%
% Range errors.
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { range-missing-end }
  { Invalid~end-point~for~range~'#1-#2'~in~character~class. }
  {
    The~end-point~'#2'~of~the~range~'#1-#2'~may~not~serve~as~an~
    end-point~for~a~range:~alphanumeric~characters~should~not~be~
    escaped,~and~non-alphanumeric~characters~should~be~escaped.
  }
\msg_kernel_new:nnnn { regex } { range-backwards }
  { Range~[#1-#2]~out~of~order~in~character~class. }
  {
    In~ranges~of~characters~[x-y]~appearing~in~character~classes,~
    the~first~character~code~must~not~be~larger~than~the~second.~
    Here,~#1~has~character~code~\int_eval:n {`#1},~while~#2~has~
    character~code~\int_eval:n {`#2}.
  }
%    \end{macrocode}
%
% Errors related to |\c| and |\u|.
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { c-bad-mode }
  { Invalid~nested~\iow_char:N\\c~escape~in~regular~expression. }
  {
    The~\iow_char:N\\c~escape~cannot~be~used~within~
    a~control~sequence~test~'\iow_char:N\\c{...}'.~
    To~combine~several~category~tests,~use~'\iow_char:N\\c[...]'.
  }
\msg_kernel_new:nnnn { regex } { c-missing-rbrace }
  { Missing~right~brace~inserted~for~\iow_char:N\\c~escape. }
  {
    LaTeX~was~given~a~regular~expression~where~a~
    '\iow_char:N\\c\iow_char:N\{...'~construction~was~not~ended~
    with~a~closing~brace~'\iow_char:N\}'.
  }
\msg_kernel_new:nnnn { regex } { c-missing-rbrack }
  { Missing~right~bracket~inserted~for~\iow_char:N\\c~escape. }
  {
    A~construction~'\iow_char:N\\c[...'~appears~in~a~
    regular~expression,~but~the~closing~']'~is~not~present.
  }
\msg_kernel_new:nnnn { regex } { c-missing-category }
  { Invalid~character~'#1'~following~\iow_char\\c~escape. }
  {
    In~regular~expressions,~the~\iow_char:N\\c~escape~sequence~
    may~only~be~followed~by~a~left~brace,~a~left~bracket,~or~a~
    capital~letter~representing~a~character~category,~namely~
    one~of~ABCDELMOPSTU.
  }
\msg_kernel_new:nnnn { regex } { u-missing-lbrace }
  { Missing~left~brace~following~\iow_char:N\\u~escape. }
  {
    The~\iow_char:N\\u~escape~sequence~must~be~followed~by~
    a~brace~group~with~the~name~of~the~variable~to~use.
  }
\msg_kernel_new:nnnn { regex } { u-missing-rbrace }
  { Missing~right~brace~inserted~for~\iow_char:N\\u~escape. }
  {
    LaTeX~
    \tl_if_empty:xTF {#2}
      { reached~the~end~of~the~string~ }
      { encountered~an~escaped~alphanumeric~character '\iow_char:N\\#2'~ }
    when~parsing~the~argument~of~an~'\iow_char:N\\u\iow_char:N\{...\}'~escape.
  }
%    \end{macrocode}
%
% In various cases, the result of a \pkg{l3regex} operation can leave us
% with an unbalanced token list, which we must re-balance by adding
% begin-group or end-group character tokens.
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { sequence-unbalanced }
  {
    Missing~
    \flag_if_raised:nTF { regex_end }
      {
        left~
        \flag_if_raised:nTF { regex_begin }
          { and~right~braces } { brace }
      }
      { right~brace }
    \ inserted~in~extracted~match.
  }
  {
    LaTeX~was~asked~to~extract~submatches~or~split~a~token~list~
    according~to~a~given~regular~expression,~but~some~of~the~resulting~
    items~were~not~balanced.
  }
\msg_kernel_new:nnnn { regex } { replace-unbalanced }
  { The~result~of~a~replacement~does~not~have~balanced~braces. }
  {
    LaTeX~was~asked~to~do~some~regular~expression~replacement,~
    and~the~resulting~token~list~would~not~have~the~same~number~
    of~begin-group~and~end-group~tokens. \\ \\
    \ \ \ \
    \prg_case_int:nnn {#1}
      {
        { -1 } { A~left~brace~was }
        {  1 } { A~right~brace~was }
      }
      {
        \int_abs:n {#1} ~
        \int_compare:nNnTF {#1} < \c_zero { left } { right } ~
        braces ~ were
      }
    \ inserted.
  }
%    \end{macrocode}
%
% Messages related to NFA variables.
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { not-nfa }
  { This~is~not~a~regular~expression~variable. }
  {
    LaTeX~was~expecting~`#1'~to~be~a~regular~expression~variable.\\
    This~control~sequence~is~not~a~regex~variable.~It's~current~meaning~
    is~\\\\
    \ \ \ \ \token_to_str:N #1 = \token_to_meaning:N #1 .
  }
\msg_kernel_new:nnn { regex } { nfa-misused }
  { Automaton~#1 used~incorrectly. }
%    \end{macrocode}
%
%    \begin{macrocode}
\msg_kernel_new:nnnn { regex } { c-command }
  { Misused~\iow_char:N\\c~or\iow_char:N\\C~command~in~a~#1. }
  {
    In~a~#1,~the~\iow_char:N\\C~escape~sequence~
    can~be~followed~by~one~of~the~letters~ABCDELMOPSTU~
    or~a~brace~group,~not~by~'#2'.
  }
\msg_kernel_new:nnnn { regex } { unknown-option }
  { Unknown~option~`#1'~for~regular~expressions. }
  {
    LaTeX~came~across~something~like~`(?#1)'~in~a~regular~expression,~
    but~the~option~`#1'~is~not~known.~It~will~be~ignored.
  }
\msg_kernel_new:nnnn { regex } { invalid-in-option }
  { Invalid~character~in~option~of~a~regular~expression. }
  {
    The~character~or~escape~sequence~`#1'~is~not~defined~
    as~an~option~within~regular~expressions.
  }
\msg_kernel_new:nnnn { regex } { g-command }
  { Missing~brace~for~the~\iow_char:N\\g~construction~in~a~replacement~text. }
  {
    In~the~replacement~text~for~a~regular~expression~search,~
    submatches~are~represented~either~as~\iow_char:N \\g{dd..d},~
    or~\\d,~where~`d'~are~single~digits.~Here,~a~brace~is~missing.
  }
%    \end{macrocode}
%
%    \begin{macrocode}
%</package>
%    \end{macrocode}
%
% \end{implementation}
%
% \endinput
%^^A
%^^A \msg_new:nnn { regex } { 4 }
%^^A   { Numbers~out~of~order~in~\iow_char:N\{\iow_char\}~quantifier. }
%^^A \msg_new:nnn { regex } { 44 } { Invalid~UTF-8~string }
%^^A \msg_new:nnn { regex } { 46 }
%^^A   { Malformed~\iow_char:N\\P~or\iow_char:N\\p~sequence }
%^^A \msg_new:nnn { regex } { 47 }
%^^A   { Unknown~property~after~\iow_char:N\\P~or\iow_char:N\\p }
%^^A
%^^A NOT IMPLEMENTED
%^^A    \cx        "control-x", where x is any ASCII character
%^^A    \C         one byte, even in UTF-8 mode (best avoided)
%^^A    \p{xx}     a character with the xx property
%^^A    \P{xx}     a character without the xx property
%^^A    \R         a newline sequence
%^^A    \X         an extended Unicode sequence
%^^A    [[:xxx:]]   positive POSIX named set
%^^A    [[:^xxx:]]  negative POSIX named set
%^^A    ?+          0 or 1, possessive
%^^A    *+          0 or more, possessive
%^^A    ++          1 or more, possessive
%^^A    {n,m}+      at least n, no more than m, possessive
%^^A    {n,}+       n or more, possessive
%^^A    \K          reset start of match
%^^A    (?<name>...)    named capturing group (Perl)
%^^A    (?'name'...)    named capturing group (Perl)
%^^A    (?P<name>...)   named capturing group (Python)
%^^A    (?:...)         non-capturing group
%^^A    (?|...)         non-capturing group; reset group numbers for
%^^A                     capturing groups in each alternative
%^^A    (?>...)         atomic, non-capturing group
%^^A    (?#....)        comment (not nestable)
%^^A    (?i)            caseless
%^^A    (?J)            allow duplicate names
%^^A    (?m)            multiline
%^^A    (?s)            single line (dotall)
%^^A    (?U)            default ungreedy (lazy)
%^^A    (?x)            extended (ignore white space)
%^^A    (?-...)         unset option(s)
%^^A    (*NO_START_OPT) no start-match optimization (PCRE_NO_START_OPTIMIZE)
%^^A    (*UTF8)         set UTF-8 mode (PCRE_UTF8)
%^^A    (*UCP)          set PCRE_UCP (use Unicode properties for \d etc)
%^^A    (?=...)         positive look ahead
%^^A    (?!...)         negative look ahead
%^^A    (?<=...)        positive look behind
%^^A    (?<!...)        negative look behind
%^^A    \n              reference by number (can be ambiguous)
%^^A    \gn             reference by number
%^^A    \g{n}           reference by number
%^^A    \g{-n}          relative reference by number
%^^A    \k<name>        reference by name (Perl)
%^^A    \k'name'        reference by name (Perl)
%^^A    \g{name}        reference by name (Perl)
%^^A    \k{name}        reference by name (.NET)
%^^A    (?P=name)       reference by name (Python)
%^^A    (?R)            recurse whole pattern
%^^A    (?n)            call subpattern by absolute number
%^^A    (?+n)           call subpattern by relative number
%^^A    (?-n)           call subpattern by relative number
%^^A    (?&name)        call subpattern by name (Perl)
%^^A    (?P>name)       call subpattern by name (Python)
%^^A    \g<name>        call subpattern by name (Oniguruma)
%^^A    \g'name'        call subpattern by name (Oniguruma)
%^^A    \g<n>           call subpattern by absolute number (Oniguruma)
%^^A    \g'n'           call subpattern by absolute number (Oniguruma)
%^^A    \g<+n>          call subpattern by relative number (PCRE extension)
%^^A    \g'+n'          call subpattern by relative number (PCRE extension)
%^^A    \g<-n>          call subpattern by relative number (PCRE extension)
%^^A    \g'-n'          call subpattern by relative number (PCRE extension)
%^^A    (?(n)...        absolute reference condition
%^^A    (?(+n)...       relative reference condition
%^^A    (?(-n)...       relative reference condition
%^^A    (?(<name>)...   named reference condition (Perl)
%^^A    (?('name')...   named reference condition (Perl)
%^^A    (?(name)...     named reference condition (PCRE)
%^^A    (?(R)...        overall recursion condition
%^^A    (?(Rn)...       specific group recursion condition
%^^A    (?(R&name)...   specific recursion condition
%^^A    (?(DEFINE)...   define subpattern for reference
%^^A    (?(assert)...   assertion condition
%^^A    (*ACCEPT)       force successful match
%^^A    (*FAIL)         force backtrack; synonym (*F)
%^^A    (*COMMIT)       overall failure, no advance of starting point
%^^A    (*PRUNE)        advance to next starting character
%^^A    (*SKIP)         advance start to current matching position
%^^A    (*THEN)         local failure, backtrack to next alternation
%^^A    (*CR)           carriage return only
%^^A    (*LF)           linefeed only
%^^A    (*CRLF)         carriage return followed by linefeed
%^^A    (*ANYCRLF)      all three of the above
%^^A    (*ANY)          any Unicode newline sequence
%^^A    (*BSR_ANYCRLF)  CR, LF, or CRLF
%^^A    (*BSR_UNICODE)  any Unicode newline sequence
%^^A    (?C)      callout
%^^A    (?Cn)     callout with data n