% \iffalse meta-comment
%
%% File: l3regex.dtx Copyright (C) 2011 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 2943 2011-10-30 15:59:43Z 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 strings
% of characters. The syntax of regular expressions is mostly a subset
% of the PCRE syntax (and very close to POSIX). 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}
%   \str_set:Nn \l_my_str { That~cat. }
%   \regex_replace_once:nnN { at } { is } \l_my_str
% \end{verbatim}
% the string variable \cs{l_my_str} 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_str
% \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 string. In the replacement text, |\0| denotes the full match
% (here, a word).
%
% \subsection{Syntax of regular expressions}
%
% Most characters match exactly themselves. Some characters are
% special and must be escaped with a backslash (\emph{e.g.}, |\*|
% matches an explicit 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.},
%   |(|, |)|, |?|, |.|);
% \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 literal string |$%^\abc#|.
% \begin{texnote}
%   When converting the regular expression to a string,
%   the value of the escape character is set to be a backslash.
% \end{texnote}
%
% 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).
%
% 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 character, including newlines.
%   \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 character not matched by |\d|.
%   \item[\\H] Any character not matched by |\h|.
%   \item[\\N] Any character other than the |\n| character (hex 0A).
%   \item[\\S] Any character not matched by |\s|.
%   \item[\\V] Any character not matched by |\v|.
%   \item[\\W] Any character not matched by |\w|.
% \end{l3regex-syntax}
%
% Character classes match exactly one character in the subject string.
% \begin{l3regex-syntax}
%   \item[{[\ldots{}]}] Positive character class.
%     Matches any of the specified characters.
%   \item[{[\char`\^\ldots{}]}] Negative character class.
%     Matches any character other than the specified characters.
%   \item[{[x-y]}] Range (can be used with escaped characters).
% \end{l3regex-syntax}
%
% 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.
%   \item[\\B] Not a word boundary.
%   \item[\char`^ \textrm{or} \\A]
%     Start of the subject string.
%   \item[\char`$\textrm{,} \\Z \textrm{or} \\z]
%     End of the subject string.
%   \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.
% \end{l3regex-syntax}
%
% 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|, |\w|, |\W| 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}
%   \str_set:Nn \l_my_str { Hello,~world! }
%   \regex_replace_all:nnN { ([er]?l|o) . } { \(\0\-\-\1\) } \l_my_str
% \end{verbatim}
% results in \cs{l_my_str} holding |H(ell--el)(o,--o) w(or--o)(ld--l)!|
%
% \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 as a token list 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_set:Nn, \regex_gset:Nn}
%   \begin{syntax}
%     \cs{regex_set:Nn} \meta{tl var} \Arg{regex}
%   \end{syntax}
%   Stores a precompiled version of the \meta{regular expression}
%   in the \meta{tl var}. For instance, this function can be used
%   as
%   \begin{verbatim}
%     \tl_new:N \l_my_regex_tl
%     \regex_set:Nn \l_my_regex_tl { my\ (simple\ )? reg(ex|ular\ expression) }
%   \end{verbatim}
%   The assignment is local for \cs{regex_set:Nn} and global for
%   \cs{regex_gset:Nn}.
%   \begin{texnote}
%     Precompiled regular expressions can be safely written to a file
%     and read when the \LaTeX3 syntax is active (as triggered by
%     \cs{ExplSyntaxOn}).
%   \end{texnote}
% \end{function}
%
% \subsection{String 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{string} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Tests whether the \meta{regular expression} matches any substring
%   of \meta{string}. 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{string} \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{string}.
%   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 string.
%   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{string} \meta{seq~var}
%     \cs{regex_extract_once:nnNTF} \Arg{regex} \Arg{string} \meta{seq~var} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Finds the first match of the \meta{regular expression}
%   in the \meta{string}. 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 not altered.
%   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 { ^(La)?TeX(!*)$ } { LaTeX!!! }
%       \l_foo_seq { true } { false }
%   \end{verbatim}
%   Then the regular expression (anchored at the start with |^| and
%   at the end with |$|) will match the whole string. 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:nnNTF} \Arg{regex} \Arg{string} \meta{seq~var} \Arg{true code} \Arg{false code}
%   \end{syntax}
%   Finds all matches of the \meta{regular expression}
%   in the \meta{string}, and stores all the submatch information
%   in a single sequence (concatenating the results of
%   multiple \cs{regex_extract_once:nnN} calls).
%   For instance, assume that you type
%   \begin{verbatim}
%     \regex_extract_all:nnN { \w+ } { Hello,~world! } \l_foo_seq
%   \end{verbatim}
%   Then the regular expression will match twice, and the resulting
%   sequence contains the two items \texttt{Hello} and \texttt{world}.
% \end{function}
%
% \subsection{String splitting}
%
% \begin{function}{\regex_split:nnN, \regex_split:NnN}
%   \begin{syntax}
%     \cs{regex_split:nnN} \Arg{regular expression} \meta{string} \meta{seq~var}
%   \end{syntax}
%   Searches the \meta{string} into a sequence of substrings, delimited by
%   matches of the \meta{regular expression}. If the \meta{regular expression}
%   has capturing groups, then the substrings 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{string} as
%   its sole item. If the \meta{regular expression} matches the empty string,
%   then the \meta{string} is split into single character substrings.
%   For example, after
%   \begin{verbatim}
%     \seq_new:N \l_path_seq
%     \regex_split:nnN { / } { the/path/for/this/file.tex } \l_path_seq
%   \end{verbatim}
%   the sequence |\l_path_seq| contains the items |{the}|, |{path}|,
%   |{for}|, |{this}|, and |{file.tex}|.
% \end{function}
%
% \subsection{String 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{str~var}
%   \end{syntax}
%   Searches for the \meta{regular expression} in the \meta{string}
%   and replaces the matching part with the \meta{replacement}. The result
%   is assigned locally to \meta{str~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}{\regex_replace_all:nnN, \regex_replace_all:NnN}
%   \begin{syntax}
%     \cs{regex_replace_all:nnN} \Arg{regular expression} \Arg{replacement} \meta{str~var}
%   \end{syntax}
%   Replaces all occurrences of the \cs{regular expression}
%   in the \meta{string} 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{str~var}.
% \end{function}
%
% \subsection{Bugs, misfeatures, future work, and other possibilities}
%
% The following need to be done now.
% \begin{itemize}
% \item The \texttt{\{\}} quantifiers are only partially implemented.
% \item Space's catcode wrong in the result of a replacement!
% \item Newline conventions are not done.
%   In particular, |.| should not match newlines.
%   Also, |\A| should differ from |^|, and |\Z|, |\z| and |$| should
%   differ.
% \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 \verb"(?|..|..)" to reset the capturing group number at the start
%   of each alternative.
% \item |(*..)| and |(?..)| sequences to set some options.
% \item Reduce the number of epsilon-transitions in alternatives.
% \item Optimize simple strings: use less states
%   (|abcade| should give two states, for |abc| and |ade|).
% \item Optimize groups with no alternative.
% \item Optimize the use of \cs{prg_stepwise_...} functions.
% \item |\K| for resetting the beginning of the match.
% \item UTF-8 mode for pdf\TeX{}.
% \end{itemize}
%
% The following features of PCRE or Perl will probably not be implemented.
% \begin{itemize}
% \item Other forms of escapes, and character classes.
%   |\cx|$\simeq$|\^^x|, |\ddd| (octal \texttt{ddd}).
%   POSIX character classes.
%   |\p{..}| and |\P{..}| for having/not having a Unicode property.
%   |\X| for \enquote{extended} Unicode sequence.
% \item Callout with |(?C...)|.
% \item Conditional subpatterns (other than with a look-ahead
%   or look-behind condition): this is non-regular, isn't it?
% \end{itemize}
%
% The following features of PCRE or perl will definitely not be implemented.
% \begin{itemize}
% \item Comments: \TeX{} already has its own system for comments.
% \item Named subpatterns: \TeX{} programmers have lived so far without
%   any need for named macro parameters.
% \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.
% \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}
%    \end{macrocode}
%
% Most regex engines use backtracking. This allows to provide very
% powerful features (back-references come to mind first), but it is
% costly. 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 strings matching that regular expression.
% We then run the string through the NFA, and check the return value.
%
% The code is structured as follows. Various helper functions are
% introduced in the next subsection, to limit the clutter in later
% parts. Then functions pertaining to parsing the regular expression
% are introduced: that part is rather long because of the many bells
% and whistles that we need to cater for. The next subsection takes
% care of running the NFA, and describes how the various \TeX{}
% registers are (ab)used in this module. Finally, user functions.
%
% \subsection{Constants and variables}
%
% \begin{variable}
%   {
%     \c_forty_eight, \c_fifty_eight, \c_sixty_five, \c_ninety_one,
%     \c_ninety_seven, \c_one_hundred_twenty_three,
%     \c_one_hundred_twenty_seven
%   }
%   We declare here some integer values which delimit ranges of
%   ASCII characters of various types.
%    \begin{macrocode}
\int_const:Nn \c_forty_eight  { 48 }
\int_const:Nn \c_fifty_eight  { 58 }
\int_const:Nn \c_sixty_five   { 65 }
\int_const:Nn \c_ninety_one   { 91 }
\int_const:Nn \c_ninety_seven { 97 }
\int_const:Nn \c_one_hundred_twenty_three { 123 }
\int_const:Nn \c_one_hundred_twenty_seven { 127 }
%    \end{macrocode}
% \end{variable}
%
% \begin{macro}{\regex_tmp:w}
% \begin{variable}{\g_regex_tmpa_tl, \l_regex_tmpa_tl, \l_regex_tmpb_tl}
% \begin{variable}{\l_regex_tmpa_int, \l_regex_tmpb_int}
%   Temporary variables.
%    \begin{macrocode}
\cs_new:Npn \regex_tmp:w { }
\tl_new:N   \g_regex_tmpa_tl
\tl_new:N   \l_regex_tmpa_tl
\tl_new:N   \l_regex_tmpb_tl
\int_new:N  \l_regex_tmpa_int
\int_new:N  \l_regex_tmpb_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{macro}
%
% \subsubsection{Variables used while building}
%
% \begin{variable}{\l_regex_max_state_int}
% \begin{variable}{\l_regex_left_state_int, \l_regex_right_state_int}
%   The last state that was allocated is stored in \cs{l_regex_max_state_int},
%   and \cs{l_regex_left/right_state_int} point to both end-points of the
%   last group (which any quantifier would repeat). For simple strings of
%   characters, the left and right pointers only differ by one.
%    \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_group_begin_seq, \l_regex_group_end_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 (several can be
%   active at the same time when nesting groups).
%    \begin{macrocode}
\seq_new:N  \l_regex_group_begin_seq
\seq_new:N  \l_regex_group_end_seq
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_capturing_group_int}
% \begin{variable}{\l_regex_capturing_group_seq}
%   \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}.
%    \begin{macrocode}
\int_new:N  \l_regex_capturing_group_int
\seq_new:N  \l_regex_capturing_group_seq
%    \end{macrocode}
% \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}
%
% \subsubsection{Character classes}
%
% \begin{macro}{\regex_build_tmp_class:n}
% \begin{variable}{\l_regex_class_bool,\l_regex_class_tl}
%   \cs{l_regex_class_bool} is false for negative character classes.
%   \cs{l_regex_class_tl} holds the tests which should be performed
%   to decide whether the \cs{l_regex_current_char_int} matches that
%   character class. Once the class is read completely, the full
%   instructions are stored in \cs{regex_build_tmp_class:n}, whose
%   argument is the target state if the test succeeds. It is also used
%   for all other single-character situations (\emph{e.g.}, |\d|, or |.|).
%    \begin{macrocode}
\cs_new_eq:NN \regex_build_tmp_class:n \use_none:n
\bool_new:N \l_regex_class_bool
\tl_new:N   \l_regex_class_tl
%    \end{macrocode}
% \end{variable}
% \end{macro}
%
% \begin{variable}{\c_regex_d_tl,\c_regex_D_tl}
% \begin{variable}{\c_regex_h_tl,\c_regex_H_tl}
% \begin{variable}{\c_regex_s_tl,\c_regex_S_tl}
% \begin{variable}{\c_regex_v_tl,\c_regex_V_tl}
% \begin{variable}{\c_regex_w_tl,\c_regex_W_tl}
% \begin{variable}{\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]|, |\s=[\ \^^I\^^J\^^L\^^M]|,
%   |\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 ranges 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_D_tl
  {
    \regex_item_geq:n { \c_fifty_eight } % > `9
    \regex_item_range:nn { \c_zero } { 47 } % 0
  }
\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_H_tl
  {
    \regex_item_geq:n { 33 } % > space
    \regex_item_range:nn { \c_ten } { 31 } % tab < ... < space
    \regex_item_range:nn { \c_zero } { \c_eight } % < tab
  }
\tl_const:Nn \c_regex_s_tl
  {
    \regex_item_equal:n  { \c_thirty_two } % space
    \regex_item_range:nn { \c_nine } { \c_ten } % tab, lf
    \regex_item_range:nn { \c_twelve } { \c_thirteen } % ff, cr
  }
\tl_const:Nn \c_regex_S_tl
  {
    \regex_item_geq:n    { 33 } % > space
    \regex_item_range:nn { \c_fourteen } { 31 } % tab < ... < space
    \regex_item_range:nn { \c_zero } { \c_eight } % < tab
    \regex_item_equal:n  { \c_eleven } % vtab
  }
\tl_const:Nn \c_regex_v_tl
  {
    \regex_item_range:nn { \c_ten } { \c_thirteen } % lf, vtab, ff, cr
  }
\tl_const:Nn \c_regex_V_tl
  {
    \regex_item_geq:n    { \c_fourteen } % >cr
    \regex_item_range:nn { \c_zero } { \c_nine } % < lf
  }
\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_W_tl
  {
    \regex_item_range:nn { \c_zero } { 47 } % <`0
    \regex_item_range:nn { \c_fifty_eight } { 64 } % (`9+1)--(`A-1)
    \regex_item_range:nn { \c_ninety_one } { 94 } % (`Z+1)--(`_-1)
    \regex_item_equal:n  { 96 } % `
    \regex_item_geq:n    { \c_one_hundred_twenty_three } % z
  }
\tl_const:Nn \c_regex_N_tl
  {
    \regex_item_geq:n { \c_eleven } % > lf
    \regex_item_range:nn { \c_zero } { \c_nine } % < lf
  }
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \subsubsection{Variables used when matching}
%
% \begin{variable}{\l_regex_query_other_str}
%   The string that is being matched.
%   In that string, spaces have category code \enquote{other}.
%    \begin{macrocode}
\tl_new:N \l_regex_query_other_str
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_current_step_int}
% \begin{variable}{\l_regex_start_step_int}
% \begin{variable}{\l_regex_success_step_int}
%   While reading through the query string, \cs{l_regex_current_step_int}
%   is the position in the string. Each match begins at the position
%   given by \cs{l_regex_start_step_int}. Whenever an execution thread
%   succeeds, the corresponding step is stored into
%   \cs{l_regex_success_step_int}, which will be the next starting step
%   (except in the case of empty matches).
%   \begin{macrocode}
\int_new:N \l_regex_current_step_int
\int_new:N \l_regex_start_step_int
\int_new:N \l_regex_success_step_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_regex_unique_step_int}
%   In the case of repeated matches, \cs{l_regex_current_step_int}
%   is reset to the end-position of the previous match. In contrast,
%   \cs{l_regex_unique_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_unique_step_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_current_char_int}
% \begin{variable}{\l_regex_last_char_int}
% \begin{variable}{\l_regex_case_changed_char_int}
%   The character codes of the character at the current position
%   in the string, and at the previous position, and the current
%   character with its case changed (|A-Z|$\leftrightarrow$|a-z|).
%   The \cs{l_regex_last_char_int} is used to test for word boundaries
%   (|\b| and |\B|). The \cs{l_regex_case_changed_char_int} is
%   only computed if the \enquote{case insensitive} option |(?i)|
%   is used in the regex.
%    \begin{macrocode}
\int_new:N \l_regex_current_char_int
\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}
%
% \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 string, 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 the case 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_max_index_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_index_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_index_int} reset
%   to zero, effectively clearing the array.
%    \begin{macrocode}
\int_new:N \l_regex_max_index_int
%    \end{macrocode}
% \end{variable}
%
% \begin{macro}[int]{\l_regex_every_match_tl}
%   Every time a match is found, this token list is used.
%   For single matching, the token list is set to removing
%   the remainder of the query string. 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{macro}
%
% \begin{variable}{\l_regex_success_bool}
%   The boolean \cs{l_regex_success_bool} is true if the current match
%   attempt was successful.
%    \begin{macrocode}
\bool_new:N \l_regex_success_bool
%    \end{macrocode}
% \end{variable}
%
% \begin{macro}{\regex_last_match_empty:F}
% \begin{macro}[aux]{\regex_last_match_empty_no:F}
% \begin{macro}[aux]{\regex_last_match_empty_yes:F}
%   When doing multiple matches, we need to avoid infinite loops where
%   each iteration matches the same empty string. When we detect such
%   a situation, the next match attempt is shifted by one character.
%   Namely, an empty match is discarded if it follows an empty match
%   at the same position. If the previous match was non-empty,
%   \cs{regex_last_match_empty:F} is simply \cs{use:n}, and keeps
%   the match. If it was empty, then we test whether the new match
%   has moved or not: if it has not, then the success is discarded.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_last_match_empty_no:F #1 {#1}
\cs_new_protected:Npn \regex_last_match_empty_yes:F
  { \int_compare:nNnF \l_regex_start_step_int = \l_regex_current_step_int }
\cs_new_eq:NN \regex_last_match_empty:F \regex_last_match_empty_no:F
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{variable}{\l_regex_success_empty_bool}
% \begin{variable}{\l_regex_fresh_thread_bool}
%   When a match succeeds, \cs{l_regex_success_empty_bool}
%   records whether it is empty. This information is used
%   to initialize \cs{regex_last_match_empty:F} before
%   starting the next match attempt.
%   The boolean \cs{l_regex_fresh_thread_bool} is true
%   when the current thread has started from the beginning of the
%   regular expression at this character.
%   This is probably suboptimal. Improvements welcome.
%    \begin{macrocode}
\bool_new:N \l_regex_success_empty_bool
\bool_new:N \l_regex_fresh_thread_bool
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \subsubsection{Variables used for user functions}
%
% \begin{variable}{\g_regex_submatches_seq}
%   This holds temporarily a sequence of submatches,
%   global so that it exits the group.
%    \begin{macrocode}
\seq_new:N  \g_regex_submatches_seq
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\g_regex_match_count_int}
%   The number of matches found so far is stored
%   in \cs{g_regex_match_count_int}. This is only used
%   in the \cs{regex_count:nnN} functions.
%    \begin{macrocode}
\int_new:N \g_regex_match_count_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\g_regex_extract_all_seq}
%   The \cs{regex_extract_all:nnN} function stores its result
%   in that sequence variable before assigning it to the
%   variable provided by the user.
%    \begin{macrocode}
\seq_new:N \g_regex_extract_all_seq
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\g_regex_split_seq}
%   The \cs{regex_split:nnN} function stores its result
%   in that sequence variable before assigning it to the
%   variable provided by the user.
%    \begin{macrocode}
\seq_new:N \g_regex_split_seq
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_regex_replacement_tl}
% \begin{variable}{\g_regex_replaced_str}
%   The replacement code stores a processed version
%   of the user's argument in \cs{l_regex_replacement_tl}.
%   The result of the replacement is stored in \cs{g_regex_replaced_str},
%   global to exit the group.
%    \begin{macrocode}
\tl_new:N \l_regex_replacement_tl
\tl_new:N \g_regex_replaced_str
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \subsection{Helpers}
%
% \subsubsection{Toks}
%
% \begin{macro}[int]{\s_regex_toks}
%   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_regex_toks}.
%    \begin{macrocode}
\cs_new_eq:NN \s_regex_toks \scan_stop:
%    \end{macrocode}
% \end{macro}
%
% \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_regex_toks}, 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_regex_toks} 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_regex_toks { \s_regex_toks #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}
%
% \subsubsection{Unsafe substring extraction}
%
% \begin{macro}[int]{\regex_query_substr:NN}
% \begin{macro}[aux]{\regex_query_substr_aux:nnn}
%   Extracting submatches from the query string is done
%   in a way similar to \cs{str_substr:Nnn}, but omitting
%   most checks, hence faster.
%    \begin{macrocode}
\cs_new_nopar:Npn \regex_query_substr:NN #1#2
  {
    \exp_after:wN \regex_query_substr_aux:NN
    \exp_after:wN #1
    \exp_after:wN #2
    \l_regex_query_other_str
    \q_stop
  }
\cs_new:Npn \regex_query_substr_aux:NN #1#2
  {
    \str_skip_do:nn {#1}
      { \str_collect_do:nn { #2 - #1 } { \use_i_delimit_by_q_stop:nw } }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Sequences}
%
% \begin{macro}[int]{\regex_seq_pop:N}
% \begin{macro}[int]{\regex_seq_get: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 contain
%   instructions such as |\int_set:Nn| \meta{int~var} \Arg{value},
%   which should be run immediately.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_seq_pop:N #1
  {
    \seq_pop:NN #1 \l_regex_tmpa_tl
    \l_regex_tmpa_tl
  }
\cs_new_protected_nopar:Npn \regex_seq_get:N #1
  {
    \seq_get:NN #1 \l_regex_tmpa_tl
    \l_regex_tmpa_tl
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Testing characters}
%
% \begin{macro}{\regex_item_dot:T}
%   The dot meta-character matches any character,
%   except the end-of-string marker.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_item_dot:T
  { \int_compare:nNnF \l_regex_current_char_int = \c_minus_one }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_break_point:TF}
% \begin{macro}[int]{\regex_break_true:w,\regex_break_false:w}
%   When testing whether a character of the query string 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_nopar:Npn \regex_break_true:w
   #1 \regex_break_point:TF #2 #3 {#2}
\cs_new_protected_nopar:Npn \regex_break_false:w
   #1 \regex_break_point:TF #2 #3 {#3}
\cs_new_protected_nopar: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_nopar: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_nopar: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_nopar: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_nopar: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_nopar: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_nopar: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 step, 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 step.
%    \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}
%
% \subsubsection{Grabbing digits}
%
% \begin{macro}[int]{\regex_get_digits:nw}
% \begin{macro}[aux]{\regex_get_digits_loop:N,\regex_get_digits_end:w}
%   Grabs digits (of category code other), skipping any intervening
%   space, until encountering a non-digit, and places the result
%   in a brace group after |#1|. This is used when parsing the \texttt{\{}
%   quantifier.
%    \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_nopar:Npn \regex_get_digits_aux:NN #1#2
  {
    \if_meaning:w \regex_build_raw:N #1
      \if_charcode:w \c_space_token \exp_not:N #2
      \else:
        \if_num:w 9 < 1 \exp_not:N #2 \exp_stop_f:
          #2
        \else:
          \regex_get_digits_end:w #1 #2
        \fi:
      \fi:
    \else:
      \regex_get_digits_end:w #1 #2
    \fi:
    \regex_get_digits_aux:NN
  }
\cs_new_nopar: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{More character testing}
%
% \begin{macro}[EXP,pTF]{\regex_token_if_other_digit:N}
%   In the replacement text, |\g{|\meta{int}|}| denotes the \meta{int}-th
%   submatch. Parsing this construction robustly requires a test of whether
%   a token is a digit or not.
%    \begin{macrocode}
\prg_new_conditional:Npnn \regex_token_if_other_digit:N #1 { TF }
  {
    \if_num:w \c_nine < 1 \exp_not:N #1 \exp_stop_f:
      \prg_return_true: \else: \prg_return_false: \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[EXP,aux]{\regex_aux_char_if_alphanumeric:NTF}
% \begin{macro}[EXP,aux]{\regex_aux_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_aux_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_aux_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{Helpers for building an NFA}
%
% \begin{macro}[int]{\regex_build_new_state:}
%   Here, we 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_regex_toks}, hence initialize the new register appropriately.
%   Then set \cs{l_regex_left/right_state_int} to their new values.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_new_state:
  {
    \int_compare:nNnTF \l_regex_max_state_int > { 32766 }
      { \msg_error:nn { regex } { -997 } }
      {
        \int_incr:N \l_regex_max_state_int
        \tex_toks:D \l_regex_max_state_int { \s_regex_toks }
      }
    \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
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_transition_aux:NN}
% \begin{macro}[aux]{\regex_build_transitions_aux:NNNN}
%   These functions create a new state, and put one or two transitions
%   starting from the old current state.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_transition_aux: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_nopar:Npn \regex_build_transitions_aux: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}
%
% In order for the construction \verb"ab|cd" to work, we enclose
% the whole pattern within parentheses (in the code below,
% \cs{regex_build_open_aux:} and \cs{regex_build_close_aux:}).
% These have the added benefit
% to form a capturing group: hence we get the data of the whole match
% for free.
%
% \begin{macro}[int]{\regex_build:n}
%   First, reset a few variables. Then use the generic framework defined
%   in \pkg{l3str} to parse the regular expression once, recognizing
%   which characters are raw characters, and which have special meanings.
%   The result is stored in \cs{g_str_result_tl}, and can be run directly.
%   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_setup:
    \str_aux_escape:NNNn
      \regex_build_i_unescaped:N
      \regex_build_i_escaped:N
      \regex_build_i_raw:N
      { #1 }
    \regex_build_open_aux:
      \g_str_result_tl \prg_do_nothing: \prg_do_nothing:
    \seq_push: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_i_unescaped:N}
% \begin{macro}[aux]{\regex_build_i_escaped:N}
% \begin{macro}[aux]{\regex_build_i_raw:N}
%   The \pkg{l3str} function \cs{str_aux_escape:NNNn} goes through
%   the regular expression and finds the |\a|, |\e|, |\f|, |\n|, |\r|,
%   |\t|, and |\x| escape sequences, then distinguishes three cases:
%   non-escaped characters, escaped characters, and \enquote{raw}
%   characters coming from one of the escape sequences.
%   In the particular case of regular expressions, escaped alphanumerics
%   and non-escaped non-alphanumeric printable ascii characters may have
%   special meanings, while everything else should be treated as a raw
%   character.
%    \begin{macrocode}
\cs_new_nopar:Npn \regex_build_i_unescaped:N #1
  {
    \regex_aux_char_if_special:NTF #1
      { \exp_not:N \regex_build_control:N #1 }
      { \exp_not:N \regex_build_raw:N #1 }
  }
\cs_new_nopar:Npn \regex_build_i_escaped:N #1
  {
    \regex_aux_char_if_alphanumeric:NTF #1
      { \exp_not:N \regex_build_control:N #1 }
      { \exp_not:N \regex_build_raw:N #1 }
  }
\cs_new_nopar:Npn \regex_build_i_raw:N #1
  { \exp_not:N \regex_build_raw:N #1 }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_default_control:N}
%   If the control character has a particular meaning in regular expressions,
%   the corresponding function is used. Otherwise, it is interpreted as a raw
%   character. The \cs{regex_build_default_raw:N} function is defined later.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_default_control:N #1
  {
    \cs_if_exist_use:cF { regex_build_#1: }
      { \regex_build_default_raw:N #1 }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_build_setup:}
%   Hopefully, we didn't forget to initialize anything here.
%   The search is not anchored: to achieve that, we insert state(s)
%   responsible for repeating the match attempt on every character
%   of the string.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_setup:
  {
    \cs_set_eq:NN \regex_build_control:N \regex_build_default_control:N
    \cs_set_eq:NN \regex_build_raw:N \regex_build_default_raw:N
    \int_set_eq:NN \l_regex_capturing_group_int \c_zero
    \int_zero:N \l_regex_max_state_int
    \regex_build_new_state:
    \regex_build_new_state:
    \regex_toks_put_right:Nx \l_regex_left_state_int
      { \regex_action_start_wildcard:nn {0} {1} }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_build_end:}
%   If parentheses are not nested properly, an error is raised,
%   and the correct number of parentheses is closed.
%   After that, we insert an instruction for the match to succeed.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_end:
  {
    \seq_if_empty:NF \l_regex_capturing_group_seq
      {
        \msg_error:nn { regex } {22}
        \prg_replicate:nn
          { \seq_length:N \l_regex_capturing_group_seq }
          { \regex_build_close_aux: \regex_build_group_: }
      }
    \regex_toks_put_right:Nx \l_regex_right_state_int
      { \regex_action_success: }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Anchoring and simple assertions}
%
% \begin{macro}[int]{\regex_build_A:}
% \begin{macro}[int]+\regex_build_^:+
% \begin{macro}[int]{\regex_build_G:}
% \begin{macro}[aux]{\regex_build_anchor_start:N}
%   Anchoring at the start corresponds to checking that the current
%   character is the first in the string. Anchoring to the beginning
%   of the match attempt uses \cs{l_regex_start_step_int} instead of
%   \cs{c_zero}.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_^: }
  { \regex_build_anchor_start:N \c_zero }
\cs_new_protected_nopar:Npn \regex_build_A:
  { \regex_build_anchor_start:N \c_zero }
\cs_new_protected_nopar:Npn \regex_build_G:
  { \regex_build_anchor_start:N \l_regex_start_step_int }
\cs_new_protected_nopar:Npn \regex_build_anchor_start:N #1
  {
    \regex_build_new_state:
    \regex_toks_put_right:Nx \l_regex_left_state_int
      {
        \exp_not:N \int_compare:nNnT {#1} = \l_regex_current_step_int
          {
            \regex_action_free:n
              {
                \int_eval:n
                  { \l_regex_right_state_int - \l_regex_left_state_int }
              }
          }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_Z:}
% \begin{macro}[aux]{\regex_build_z:}
% \begin{macro}[aux]+\regex_build_$:+
%   This matches the end of the string, marked by a character code of $-1$.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_$: } % $
  {
    \regex_build_new_state:
    \regex_toks_put_right:Nx \l_regex_left_state_int
      {
        \exp_not:N \int_compare:nNnT
          \c_minus_one = \l_regex_current_char_int
          {
            \regex_action_free:n
              {
                \int_eval:n
                  { \l_regex_right_state_int - \l_regex_left_state_int }
              }
          }
      }
  }
\cs_new_eq:Nc \regex_build_Z: { regex_build_$: } %$
\cs_new_eq:Nc \regex_build_z: { regex_build_$: } %$
%    \end{macrocode}
% \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 string, 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:Npn \regex_build_b:
  {
    \regex_build_new_state:
    \regex_toks_put_right:Nx \l_regex_left_state_int
      {
        \exp_not:N \regex_if_word_boundary:TF
          {
            \regex_action_free:n
              {
                \int_eval:n
                  { \l_regex_right_state_int - \l_regex_left_state_int }
              }
          }
          { }
      }
  }
\cs_new_protected_nopar:Npn \regex_build_B:
  {
    \regex_build_new_state:
    \regex_toks_put_right:Nx \l_regex_left_state_int
      {
        \exp_not:N \regex_if_word_boundary:TF
          { }
          {
            \regex_action_free:n
              {
                \int_eval:n
                  { \l_regex_right_state_int - \l_regex_left_state_int }
              }
          }
      }
  }
\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 { -1 } }
        { \group_end: \c_regex_w_tl }
    \regex_break_point:TF
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Normal character, and simple character classes}
%
% \begin{macro}[aux]{\regex_build_default_raw:N}
%   A normal alphanumeric or an escaped non-alphanumeric
%   (actually, any unknown combination) will match itself
%   and the thread will fail otherwise. We prepare
%   \cs{regex_build_tmp_class:n} with the relevant test and
%   commands. The state shift to be inserted in those
%   commands will come as |##1|: we don't know
%   yet what this will be before checking for quantifiers.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_default_raw:N #1
  {
    \cs_set:Npx \regex_build_tmp_class:n ##1
      {
        \regex_item_equal:n { \int_value:w `#1 }
        \regex_break_point:TF { \regex_action_cost:n { ##1 } } { }
      }
    \regex_build_one_quantifier:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_.:}
%   Similar to \cs{regex_build_default_raw:N} but accepts any character,
%   and refuses $-1$, which marks the end of the string.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_.: }
  {
    \cs_set:Npn \regex_build_tmp_class:n ##1
      { \regex_item_dot:T { \regex_action_cost:n {##1} } }
    \regex_build_one_quantifier:
  }
%    \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:}
% \begin{macro}[aux]{\regex_build_char_type: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}
\cs_new_protected_nopar:Npn \regex_build_char_type:N #1
  {
    \cs_set:Npn \regex_build_tmp_class:n ##1
      {
        \exp_not:N #1
        \regex_break_point:TF { \regex_action_cost:n {##1} } { }
      }
    \regex_build_one_quantifier:
  }
\tl_map_inline:nn { dDhHsSvVwWN }
  {
    \cs_new_protected_nopar:cpx { regex_build_#1: }
      {
        \exp_not:N \regex_build_char_type:N
        \exp_not:c { c_regex_#1_tl }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Character classes}
%
% \begin{macro}[aux]{\regex_build_[:}
%   This starts a class. The code for the class is collected
%   in \cs{l_regex_class_tl}. The first character is special.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_[: }
  {
    \tl_clear:N \l_regex_class_tl
    \cs_set_eq:NN \regex_build_control:N \regex_class_control:N
    \cs_set_eq:NN \regex_build_raw:N \regex_class_raw:N
    \regex_class_first:NN
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_control:N}
%   This function is similar to \cs{regex_build_control:N}. If the control
%   character has a meaning in character classes, call the corresponding
%   function, otherwise, treat it as a raw character, with the
%   \cs{regex_class_raw:N} function, defined later.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_class_control:N #1
  {
    \cs_if_exist_use:cF { regex_class_#1: }
      { \regex_class_raw:N #1 }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_]:}
%   If \texttt{]} appears as the first item of a class, then
%   it doesn't end the class. Otherwise, it's the end,
%   act just as for a single character, but with a more
%   complicated test. And restore \cs{regex_build_control:N}
%   and \cs{regex_build_raw:N}.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_class_]: }
  {
    \tl_if_empty:NTF \l_regex_class_tl %[
      { \regex_class_raw:N ] }
      {
        \cs_set_eq:NN \regex_build_control:N \regex_build_default_control:N
        \cs_set_eq:NN \regex_build_raw:N  \regex_build_default_raw:N
        \cs_set:Npn \regex_build_tmp_class:n ##1
          {
            \exp_not:o \l_regex_class_tl
            \bool_if:NTF \l_regex_class_bool
              { \regex_break_point:TF { \regex_action_cost:n {##1} } { } }
              { \regex_break_point:TF { } { \regex_action_cost:n {##1} } }
          }
        \regex_build_one_quantifier:
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_first:NN}
%   If the first non-space character is |^|, then the class is inverted.
%   We keep track of this in \cs{l_regex_class_bool}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_class_first:NN #1#2
  {
    \str_if_eq:nnTF {#1#2} { \regex_build_control:N ^ }
      { \bool_set_false:N \l_regex_class_bool }
      {
        \bool_set_true:N \l_regex_class_bool
        #1 #2
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_raw:N}
% \begin{macro}[aux]{\regex_class_single:N}
%   Most characters are treated here. We look ahead for an unescaped dash.
%   If there is none, then the character matches itself.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_class_raw:N #1#2#3
  {
    \str_if_eq:nnTF {#2#3} { \regex_build_control:N - }
      { \regex_class_range:Nw #1 }
      {
        \regex_class_single:N #1
        #2 #3
      }
  }
\cs_new_protected_nopar:Npn \regex_class_single:N #1
  {
    \tl_put_right:Nx \l_regex_class_tl
      { \regex_item_equal:n { \int_value:w `#1 } }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_range:Nw}
% \begin{macro}[aux]{\regex_class_range_put:NN}
%   If the character is followed by a dash, we look for
%   the end-point of the range. For \enquote{raw} characters,
%   that's simply |#3|. Most \enquote{control} characters also
%   have no meaning, and can serve as an end-point, but those
%   with a meaning interrupt the range.
%   In the case of a true range, check whether the end-points
%   are in the right order, and optimize in the case of equal
%   end-points.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_class_range:Nw #1#2#3
  {
    \token_if_eq_meaning:NNTF #2 \regex_build_control:N
      {
        \cs_if_exist:cTF { regex_class_#3: }
          {
            \regex_class_single:N #1
            \regex_class_single:N -
            #2#3
          }
          { \regex_class_range_put:NN #1#3 }
      }
      { \regex_class_range_put:NN #1#3 }
  }
\cs_new_protected_nopar:Npn \regex_class_range_put:NN #1#2
  {
    \if_num:w `#1 > `#2 \exp_stop_f:
      \msg_error:nn { regex } {8}
    \else:
      \tl_put_right:Nx \l_regex_class_tl
        {
          \if_num:w `#1 = `#2 \exp_stop_f:
            \regex_item_equal:n
          \else:
            \regex_item_range:nn { \int_value:w `#1 }
          \fi:
          { \int_value:w `#2 }
        }
    \fi:
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_class_d:,\regex_class_D:}
% \begin{macro}[aux]{\regex_class_h:,\regex_class_H:}
% \begin{macro}[aux]{\regex_class_s:,\regex_class_S:}
% \begin{macro}[aux]{\regex_class_v:,\regex_class_V:}
% \begin{macro}[aux]{\regex_class_w:,\regex_class_W:}
%   Similar to \cs{regex_class_single:N}, adding the appropriate
%   ranges of characters to the class. The token lists are not
%   expanded because it is more memory efficient, with a tiny
%   overhead on execution.
%    \begin{macrocode}
\tl_map_inline:nn { dDhHsSvVwWN }
  {
    \cs_new_protected_nopar:cpx { regex_class_#1: }
      {
        \tl_put_right:Nn \exp_not:N \l_regex_class_tl
          { \exp_not:c { c_regex_#1_tl } }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \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_nopar:Npn \regex_build_quantifier:w #1#2
  {
    \token_if_eq_meaning:NNTF #1 \regex_build_control:N
      {
        \cs_if_exist_use:cF { regex_build_quantifier_#2:w }
          {
            \regex_build_quantifier_end:n { }
            #1 #2
          }
      }
      {
        \regex_build_quantifier_end:n { }
        #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_nopar:Npn \regex_build_quantifier_aux:nnNN #1#2#3#4
  {
    \str_if_eq:nnTF { #3 #4 } { \regex_build_control:N ? }
      { \regex_build_quantifier_end:n { #2 #4 } #1 }
      {
        \regex_build_quantifier_end:n { #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_nopar:Npn \regex_build_quantifier_lbrace:n #1
  {
    \tl_if_empty:nTF {#1}
      {
        \regex_build_quantifier_end:n { }
        \exp_after:wN \regex_build_raw:N \c_lbrace_str
      }
      { \regex_build_quantifier_lbrace:nw {#1} }
  }
\cs_new_protected_nopar:Npx \regex_build_quantifier_lbrace:nw #1#2#3
  {
    \exp_not:N \prg_case_str:nnn { #2 #3 }
      {
        { \exp_not:N \regex_build_control:N , }
          {
            \exp_not:N \regex_get_digits:nw
              { \exp_not:N \regex_build_quantifier_lbrace:nnw {#1} }
          }
        { \exp_not:N \regex_build_control:N \c_rbrace_str }
          { \exp_not:N \regex_build_quantifier_end:n {n} {#1} }
      }
      {
        \exp_not:N \regex_build_quantifier_end:n { }
        \exp_not:N \regex_build_raw:N \c_lbrace_str #1#2
      }
  }
\cs_new_protected_nopar:Npn \regex_build_quantifier_lbrace:nnw #1#2#3#4
  {
    \str_if_eq:xxTF
      { \exp_not:n {#3#4} }
      { \exp_not:N \regex_build_control:N \c_rbrace_str }
      {
        \tl_if_empty:nTF {#2}
          { \regex_build_quantifier_aux:nnNN { {#1} } { n* } }
          {
            \int_compare:nNnT {#1} > {#2}
              { \msg_error:nn { regex } {4} }
            \regex_build_quantifier_aux:nnNN { {#1} {#2} } { nn }
          }
      }
      {
        \regex_build_quantifier_end:n { }
        \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:n}
%   When all quantifiers are found, we will call the relevant
%   \cs{regex_build_one/group_\meta{quantifiers}:} function.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_quantifier_end:n #1
  { \use:c { regex_build_ \l_regex_one_or_group_tl _ #1 : } }
%    \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_:}
%   If no quantifier is found, then the character or character class
%   should just be built into a transition from the current
%   \enquote{right} state to a new state.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_one_:
  {
    \regex_build_transition_aux:NN
      \regex_build_tmp_class:n \l_regex_right_state_int
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_?:}
% \begin{macro}[aux]{\regex_build_one_??:}
%   The two transitions are a costly transition controlled by
%   the character class, and a free transition, both going to
%   a common new state. The only difference between the greedy
%   and lazy operators is the order of transitions.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_one_?: }
  {
    \regex_build_transitions_aux:NNNN
      \regex_build_tmp_class:n \l_regex_right_state_int
      \regex_action_free:n     \l_regex_right_state_int
  }
\cs_new_protected_nopar:cpn { regex_build_one_??: }
  {
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n     \l_regex_right_state_int
      \regex_build_tmp_class:n \l_regex_right_state_int
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_*:}
% \begin{macro}[aux]{\regex_build_one_*?:}
%   Build a costly transition going from the current state to itself,
%   and a free transition moving to a new state.
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_one_*: }
  {
    \regex_build_transitions_aux:NNNN
      \regex_build_tmp_class:n \l_regex_left_state_int
      \regex_action_free:n     \l_regex_right_state_int
  }
\cs_new_protected_nopar:cpn { regex_build_one_*?: }
  {
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n     \l_regex_right_state_int
      \regex_build_tmp_class:n \l_regex_left_state_int
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_+:}
% \begin{macro}[aux]{\regex_build_one_+?:}
%   Build a transition from the current state to a new state,
%   controlled by the character class, then build two transitions
%   from this new state to the original state (for repetition)
%   and to another new state (to move on to the rest of the pattern).
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_one_+: }
  {
    \regex_build_one_:
    \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n \l_regex_tmpa_int
      \regex_action_free:n \l_regex_right_state_int
  }
\cs_new_protected_nopar:cpn { regex_build_one_+?: }
  {
    \regex_build_one_:
    \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n \l_regex_right_state_int
      \regex_action_free:n \l_regex_tmpa_int
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_n:}
% \begin{macro}[aux]{\regex_build_one_n?:}
%   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.
%   Simply repeat |#1| times the effect of \cs{regex_build_one_:}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_one_n: #1
  { \prg_replicate:nn {#1} { \regex_build_one_: } }
\cs_new_eq:cN { regex_build_one_n?: } \regex_build_one_n:
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_n*:}
% \begin{macro}[aux]{\regex_build_one_n*?:}
%   This function is called in case the syntax is
%   \texttt{\{\meta{int},\}}.
%    \begin{macrocode}
\cs_new_protected_nopar:cpx { regex_build_one_n*: } #1
  {
    \exp_not:N \prg_replicate:nn {#1} { \exp_not:N \regex_build_one_: }
    \exp_not:c { regex_build_one_*: }
  }
\cs_new_protected_nopar:cpx { regex_build_one_n*?: } #1
  {
    \exp_not:N \prg_replicate:nn {#1} { \exp_not:N \regex_build_one_: }
    \exp_not:c { regex_build_one_*?: }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_one_nn:}
% \begin{macro}[aux]{\regex_build_one_nn?:}
% \begin{macro}[aux]{\regex_build_one_nn_aux:Nnn}
%   This function is called when the syntax is
%   \texttt{\{\meta{int},\meta{int}\}}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_one_nn_aux:Nnn #1#2#3
  {
    \prg_replicate:nn {#2} { \regex_build_one_: }
    \prg_replicate:nn {#3-#2} {#1}
  }
\cs_new_protected_nopar:Npx \regex_build_one_nn:
  { \regex_build_one_nn_aux:Nnn \exp_not:c { regex_build_one_?: } }
\cs_new_protected_nopar:cpx { regex_build_one_nn?: }
  { \regex_build_one_nn_aux:Nnn \exp_not:c { regex_build_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_nopar:cpn { regex_build_(: } #1#2
  {
    \str_if_eq:nnTF { #1 #2 } { \regex_build_control:N ? }
      { \regex_build_special_group:NN }
      {
        \int_incr:N \l_regex_capturing_group_int
        \seq_push:Nx \l_regex_capturing_group_seq
          { \int_use:N \l_regex_capturing_group_int }
        \regex_build_open_aux:
        #1 #2
      }
  }
\cs_new_protected_nopar:Npn \regex_build_open_aux:
  {
    \regex_build_new_state:
    \seq_push:Nx \l_regex_group_begin_seq
      {
        \int_set:Nn \l_regex_left_state_int
          { \int_use:N \l_regex_left_state_int }
      }
    \bool_if:NTF \l_regex_caseless_bool
      { \seq_push:Nn \l_regex_group_end_seq { \regex_build_caseless: } }
      { \seq_push:Nn \l_regex_group_end_seq { \regex_build_caseful: } }
    \seq_push:Nx \l_regex_group_end_seq
      {
        \int_set:Nn \l_regex_right_state_int
          { \int_use:N \l_regex_right_state_int }
      }
    \regex_build_begin_alternation:
  }
\cs_new_protected_nopar:cpn { regex_build_|: }
  {
    \regex_build_end_alternation:
    \regex_build_begin_alternation:
  }
\cs_new_protected_nopar:cpn { regex_build_): }
  {
    \seq_if_empty:NTF \l_regex_capturing_group_seq
      { \msg_error:nn { regex } { 22 } }
      {
        \regex_build_close_aux:
        \regex_build_group_quantifier:
      }
  }
\cs_new_protected_nopar:Npn \regex_build_close_aux:
  {
    \regex_build_end_alternation:
    \regex_seq_pop:N \l_regex_group_begin_seq
    \regex_seq_pop:N \l_regex_group_end_seq
    \regex_seq_pop:N \l_regex_group_end_seq
  }
%    \end{macrocode}
%   Building each branch.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_begin_alternation:
  {
    \regex_build_new_state:
    \regex_seq_get:N \l_regex_group_begin_seq
    \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:N \l_regex_group_end_seq
    \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 }
          }
      }
  }
%    \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_nopar:Npn \regex_build_special_group:NN #1#2
  {
    \cs_if_exist_use:cF { regex_build_special_group_\token_to_str:N #2 : }
      {
        \msg_error:nn { regex } { -998 }
        \regex_build_control: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{*}, 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_:: }
  {
    \seq_push:Nx \l_regex_capturing_group_seq { * }
    \regex_build_open_aux:
  }
%    \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_nopar: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_error:nnx { regex } { unknown-option } { #3 } }
        \regex_build_options:NNN #1
      }
      {
        \prg_case_str:nnn { #3 }
          { % (
            { ) } { }
            { - } { \regex_build_options:NNN - }
          }
          { \msg_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_nopar:Npn \regex_build_group_submatches:NN #1#2
  {
    \seq_pop:NN \l_regex_capturing_group_seq \l_regex_tmpa_tl
    \str_if_eq:xxF { \l_regex_tmpa_tl } { * }
      {
        \regex_toks_put_left:Nx #1
          { \regex_action_submatch:n { \l_regex_tmpa_tl < } }
        \regex_toks_put_left:Nx #2
          { \regex_action_submatch:n { \l_regex_tmpa_tl > } }
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_:}
%   When there is no quantifier, the group is simply inserted as is,
%   and we only need to track submatches, and move to a new state.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_:
  {
    \regex_build_group_submatches:NN
      \l_regex_left_state_int \l_regex_right_state_int
    \regex_build_transition_aux:NN
      \regex_action_free:n \l_regex_right_state_int
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_shift:N}
%   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_tmpa_int} to a new state.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_shift:N #1
  {
    \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int
    \regex_build_new_state:
    \tex_toks:D \l_regex_right_state_int = \tex_toks:D \l_regex_tmpa_int
    \regex_toks_put_left:Nx \l_regex_right_state_int
      {
        \int_set:Nn \l_regex_current_state_int
          { \int_use:N \l_regex_tmpa_int } % ^^A here we lie!
      }
    \cs_set:Npx \regex_tmp:w
      {
        \tex_toks:D \l_regex_tmpa_int
          {
            \s_regex_toks
            #1 { \int_eval:n { \l_regex_right_state_int - \l_regex_tmpa_int } }
          }
      }
    \regex_tmp:w
    \regex_build_group_submatches:NN
      \l_regex_right_state_int \l_regex_left_state_int
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_qs_aux:NN}
% \begin{macro}[aux]{\regex_build_group_?:}
% \begin{macro}[aux]{\regex_build_group_??:}
% \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_tmpa_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.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_qs_aux:NN #1#2
  {
    \regex_build_group_shift:N \regex_action_free:n
    \int_set_eq:NN \l_regex_right_state_int \l_regex_left_state_int
    \regex_build_transition_aux:NN \regex_action_free:n #1
    #2 \l_regex_tmpa_int
      {
        \regex_action_free:n
          { \int_eval:n { \l_regex_right_state_int - \l_regex_tmpa_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
  }
\cs_new_protected_nopar:cpn { regex_build_group_*: }
  {
    \regex_build_group_qs_aux:NN
      \l_regex_tmpa_int \regex_toks_put_right:Nx
  }
\cs_new_protected_nopar:cpn { regex_build_group_*?: }
  {
    \regex_build_group_qs_aux:NN
      \l_regex_tmpa_int \regex_toks_put_left:Nx
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_+:}
% \begin{macro}[aux]{\regex_build_group_+?:}
%   Insert the submatch tracking code, then add two transitions
%   from the current state to the left end of the group (repeating the group),
%   and to a new state (to carry on with the rest of the regular expression).
%    \begin{macrocode}
\cs_new_protected_nopar:cpn { regex_build_group_+: }
  {
    \regex_build_group_submatches:NN
      \l_regex_left_state_int \l_regex_right_state_int
    \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n \l_regex_tmpa_int
      \regex_action_free:n \l_regex_right_state_int
  }
\cs_new_protected_nopar:cpn { regex_build_group_+?: }
  {
    \regex_build_group_submatches:NN
      \l_regex_left_state_int \l_regex_right_state_int
    \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n \l_regex_right_state_int
      \regex_action_free:n \l_regex_tmpa_int
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_n_aux:n}
%   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_tmpa_int} points to the last copy of the initial
%   left-most state, \cs{l_regex_left_state_int} has its initial
%   value, and \cs{l_regex_right_state_int} points to the last
%   copy of the initial right-most state. Furthermore,
%   \cs{l_regex_max_state_int} is set appropriately to the largest
%   allocated \tn{toks} register.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_n_aux:n #1
  {
    \regex_toks_put_right:Nx \l_regex_right_state_int
      {
        \regex_action_free:n
          { \int_eval:n { \l_regex_max_state_int - \l_regex_left_state_int } }
      }
    \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int
    \int_set:Nn \l_regex_tmpb_int { \l_regex_max_state_int + \c_one }
    \int_set:Nn \l_regex_max_state_int
      {
        \l_regex_left_state_int - \c_one
        + #1 * ( \l_regex_max_state_int - \l_regex_left_state_int + \c_one )
      }
    \int_until_do:nNnn \l_regex_tmpb_int > \l_regex_max_state_int
      {
        \tex_toks:D \l_regex_tmpb_int = \tex_toks:D \l_regex_tmpa_int
        \int_incr:N \l_regex_tmpa_int
        \int_incr:N \l_regex_tmpb_int
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_n:}
% \begin{macro}[aux]{\regex_build_group_n?:}
%   These functions are called in case the syntax is
%   \texttt{\{\meta{int}\}}. Greedy and lazy operators
%   are identical, since the number of repetitions is fixed.
%   We only record the submatch information at the last repetition.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_build_group_n: #1
  { % ^^A todo: catch case #1 <= 0.
    \regex_build_group_n_aux:n {#1}
    \regex_build_transition_aux:NN
      \regex_action_free:n \l_regex_right_state_int
    \regex_build_group_submatches:NN
      \l_regex_tmpa_int \l_regex_left_state_int
  }
\cs_new_eq:cN { regex_build_group_n?: } \regex_build_group_n:
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_n*:}
% \begin{macro}[aux]{\regex_build_group_n*?:}
%   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*: } #1
  { % ^^A todo: catch case #1 <= 0.
    \regex_build_group_n_aux:n {#1}
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n \l_regex_tmpa_int
      \regex_action_free:n \l_regex_right_state_int
    \regex_build_group_submatches:NN
      \l_regex_tmpa_int \l_regex_left_state_int
  }
\cs_new_protected_nopar:cpn { regex_build_group_n*?: } #1
  { % ^^A todo: catch case #1 <= 0.
    \regex_build_group_n_aux:n {#1}
    \regex_build_transitions_aux:NNNN
      \regex_action_free:n \l_regex_right_state_int
      \regex_action_free:n \l_regex_tmpa_int
    \regex_build_group_submatches:NN
      \l_regex_tmpa_int \l_regex_left_state_int
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_build_group_nn:}
% \begin{macro}[aux]{\regex_build_group_nn?:}
%   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: #1#2
  { % ^^A Not Implemented Yet!
    \msg_expandable_error:n { Quantifier~{m,n}~not~implemented~yet }
    \use:c { regex_build_group_n*: } {#1}
  }
\cs_new_protected_nopar:cpn { regex_build_group_nn?: } #1#2
  { % ^^A Not Implemented Yet!
    \msg_expandable_error:n { Quantifier~{m,n}~not~implemented~yet }
    \use:c { regex_build_group_n*?: } {#1}
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsection{Matching}
%
% \subsubsection{Use of \TeX{} registers when matching}
%
% The first step in matching a regular expression is to build
% the corresponding NFA and store its states in the \tn{toks}
% registers. Then loop through the query string one character
% (one \enquote{step}) at a time, exploring in parallel every
% possible path through the NFA. We keep track of an array of
% the  states  currently  \enquote{active}.   More  precisely,
% \tn{skip} registers hold the state numbers to be considered
% when the next character of the string is read.
%
% At every step,  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 string  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.
%
% The current approach means that stretch and shrink components
% of \tn{skip} registers,
% as well as all \tn{muskip} registers are unused. It could seem that
% \tn{count} registers are also free for use, but we still want to be
% able to safely use integers, which are implemented as \tn{count}
% registers.
%
% \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_index_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_index_int
    \tex_skip:D \l_regex_max_index_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_unique_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 \regex_state_use_aux_ii:w } }
\cs_new_nopar:Npn \regex_state_use_aux_ii:w #1 \s_regex_toks { }
\cs_new_protected_nopar:Npn \regex_state_use_aux:n #1
  {
    \if_num:w \tex_dimen:D \l_regex_current_state_int
        < \l_regex_unique_step_int
      \tex_dimen:D \l_regex_current_state_int
        = \l_regex_unique_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_regex_toks
  {
    \regex_store_submatches_aux_ii:Nnnw
      #1
      \regex_state_submatches:nn \c_minus_one \q_prop
    \s_regex_toks
  }
\cs_new_protected:Npn \regex_store_submatches_aux_ii:Nnnw
    \regex_state_submatches:nn #1 #2 #3 \s_regex_toks
  {
    \exp_after:wN \c_zero
    \exp_after:wN \regex_state_submatches:nn \exp_after:wN
      {
        \int_value:w \int_eval:w
          \l_regex_unique_step_int + \c_one
        \exp_after:wN
      }
      \exp_after:wN { \l_regex_current_submatches_prop }
    \regex_state_submatches:nn {#1} {#2}
    \s_regex_toks
  }
%    \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_unique_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}
%   Store the query string in \cs{l_regex_query_other_str}.
%   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
  {
    \tl_set:Nx \l_regex_query_other_str { \tl_to_other_str:n {#1} }
    \regex_match_initial_setup:
    \regex_match_once:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_match_once:}
% \begin{macro}[aux]{\regex_match_once_aux:}
% \begin{macro}[aux]{\regex_match_once_aux_ii:N}
%   After setting up more variables in \cs{regex_match_setup:},
%   skip the \cs{l_regex_start_step_int} first characters of the
%   query string, and loop over it.
%   If there was a match, use the token list \cs{l_regex_every_match_tl},
%   which may call \cs{regex_match_once:} to achieve multiple matches.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_once:
  {
    \regex_match_setup:
    \exp_after:wN \regex_match_once_aux: \l_regex_query_other_str
      \q_recursion_tail \q_recursion_stop
    \bool_if:NT \l_regex_success_bool { \l_regex_every_match_tl }
  }
\cs_new_protected_nopar:Npn \regex_match_once_aux:
  {
    \int_compare:nNnTF \l_regex_start_step_int = \c_zero
      {
        \int_set_eq:NN \l_regex_current_char_int \c_minus_one
        \regex_match_loop:N
      }
      {
        \str_skip_do:nn
          { \l_regex_start_step_int - \c_one }
          { \regex_match_once_aux_ii:N }
      }
  }
\cs_new_protected_nopar:Npn \regex_match_once_aux_ii:N #1
  {
    \int_set:Nn \l_regex_current_char_int { `#1 }
    \regex_match_loop:N
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \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 on a given
%   string. It is called only once for the whole string.
%   On the other hand, \cs{regex_match_setup:}
%   is called for every match in the string in case of
%   repeated matches, and \cs{regex_match_loop_setup:N}
%   is called at every step.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_initial_setup:
  {
    \prg_stepwise_inline:nnnn {1} {1} { \l_regex_max_state_int }
      { \tex_dimen:D ##1 \c_minus_one sp \scan_stop: }
    \int_set_eq:NN \l_regex_unique_step_int  \c_minus_one
    \int_set_eq:NN \l_regex_start_step_int   \c_minus_one
    \int_set_eq:NN \l_regex_current_step_int \c_zero
    \int_set_eq:NN \l_regex_success_step_int \c_zero
    \bool_set_false:N \l_regex_success_empty_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_last_match_empty:F \regex_last_match_empty_yes:F }
      { \cs_set_eq:NN \regex_last_match_empty:F \regex_last_match_empty_no:F }
    \int_set_eq:NN \l_regex_start_step_int \l_regex_success_step_int
    \int_set_eq:NN \l_regex_current_step_int \l_regex_start_step_int
    \int_decr:N \l_regex_current_step_int
    \bool_set_false:N \l_regex_success_bool
    \int_zero:N \l_regex_max_index_int
    \regex_store_state:n {1}
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\s_regex_step}
% \begin{macro}[aux]{\regex_break_step:w}
%   When a thread succeeds, all threads with lower precedence
%   can be ignored, and the next character should be read.
%   This is done by skipping to \cs{s_regex_step}. This marker
%   does nothing if no thread succeeded at this step.
%    \begin{macrocode}
\cs_new_eq:NN \s_regex_step \scan_stop:
\cs_new:Npn \regex_break_step:w #1 \s_regex_step { }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_match_loop:N}
% \begin{macro}[aux]{\regex_match_one_index:n}
% \begin{macro}[aux]{\regex_match_one_index_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 character that is read
%   (and $-1$ for the end of the string), and loop
%   over the elements of the \tn{skip} array. Then repeat.
%   There are a couple of tests to stop reading the string
%   when no active state is left, or when the end is reached.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_match_loop:N #1
  {
    \regex_match_loop_setup:N #1
    \cs_set_nopar:Npx \regex_tmp:w
      {
        \int_zero:N \l_regex_max_index_int
        \prg_stepwise_function:nnnN
          {1} {1} { \l_regex_max_index_int }
          \regex_match_one_index:n
      }
    \regex_tmp:w
    \s_regex_step
    \if_num:w \l_regex_max_index_int = \c_zero
      \exp_after:wN \use_none_delimit_by_q_recursion_stop:w
    \fi:
    \quark_if_recursion_tail_stop:N #1
    \regex_match_loop:N
  }
\cs_new_nopar:Npn \regex_match_one_index:n #1
  {
    \regex_match_one_index_aux:n
      { \int_value:w \tex_skip:D #1 }
  }
\cs_new_protected_nopar:Npn \regex_match_one_index_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}[aux]{\regex_match_loop_setup:N}
%   This is called for every character in the string.
%   At every step in reading the query string, 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_setup:N #1
  {
    \int_incr:N \l_regex_current_step_int
    \int_incr:N \l_regex_unique_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
    \if_meaning:w #1 \q_recursion_tail
      \int_set_eq:NN \l_regex_current_char_int \c_minus_one
    \else:
      \int_set:Nn \l_regex_current_char_int {`#1}
    \fi:
    \regex_match_loop_case_hook:
  }
%    \end{macrocode}
% \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}[aux]{\regex_action_start_wildcard:nn}
%: 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 character in the query string. 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:nn #1#2
  {
    \bool_set_true:N \l_regex_fresh_thread_bool
    \regex_action_free:n {#2}
    \bool_set_false:N \l_regex_fresh_thread_bool
    \regex_action_cost:n {#1}
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_action_cost:n}
%   A transition which consumes the current character and moves
%   to state |#1|.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_action_cost:n #1
  {
    \exp_args:Nf \regex_store_state:n %^^A optimize!
      { \int_eval:n { \l_regex_current_state_int + #1 } }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\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,
%   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_last_match_empty:F
      {
        \bool_set_true:N \l_regex_success_bool
        \bool_set_eq:NN \l_regex_success_empty_bool
          \l_regex_fresh_thread_bool
        \int_set_eq:NN \l_regex_success_step_int
          \l_regex_current_step_int
        \prop_set_eq:NN \l_regex_success_submatches_prop
          \l_regex_current_submatches_prop
        \regex_break_step:w
      }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\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_nopar:Npn \regex_action_free:n #1
  {
    \cs_set_nopar:Npx \regex_tmp:w
      {
        \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 }
      }
    \regex_tmp:w
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_action_submatch:n}
%   Update the current submatches with the information
%   from the current step.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_action_submatch:n #1
  {
    \prop_put:Nno \l_regex_current_submatches_prop {#1}
      { \int_use:N \l_regex_current_step_int }
  }
%    \end{macrocode}
% \end{macro}
%
% \subsection{Submatches, once the correct match is found}
%
% \begin{macro}[int]{\regex_extract:}
% \begin{macro}[aux]{\regex_extract_aux:nTF}
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_extract:
  {
    \seq_gclear:N \g_regex_submatches_seq
    \prg_stepwise_inline:nnnn
      {0} {1} { \l_regex_capturing_group_int }
      {
        \regex_extract_aux:nTF { ##1 }
          {
            \seq_gput_right:Nx \g_regex_submatches_seq
              { \regex_query_substr:NN \l_regex_tmpa_tl \l_regex_tmpb_tl }
          }
          { \seq_gput_right:Nn \g_regex_submatches_seq { } }
      }
  }
\cs_new_protected_nopar:Npn \regex_extract_aux:nTF #1#2#3
  {
    \prop_get:NnNTF \l_regex_success_submatches_prop
      { #1 < } \l_regex_tmpa_tl
      {
        \prop_get:NnNTF \l_regex_success_submatches_prop
          { #1 > } \l_regex_tmpb_tl
          {#2}
          {#3}
      }
      {#3}
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsection{User commands}
%
% \subsubsection{Precompiled pattern}
%
% A given pattern is often reused to match many different strings.
% 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{regex_nfa_end:}
% \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_set:Nn}
% \begin{macro}{\regex_gset:Nn}
% \begin{macro}[aux]{\regex_set_aux:NNn}
% \begin{macro}[aux]{\regex_set_aux:n}
% \begin{macro}[aux]{\regex_nfa:Nw}
% \begin{macro}[aux]{\regex_nfa_end:}
%   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 \cs{g_regex_tmpa_tl}, then
%   transferred to the user's tl variable.
%   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_protected_nopar:Npn \regex_set:Nn
  { \regex_set_aux:NNn \tl_set_eq:NN }
\cs_new_protected_nopar:Npn \regex_gset:Nn
  { \regex_set_aux:NNn \tl_gset_eq:NN }
\cs_new_protected:Npn \regex_set_aux:NNn #1#2#3
  {
    \group_begin:
      \regex_build:n {#3}
      \tl_gset:Nx \g_regex_tmpa_tl
        {
          \exp_not:N \regex_nfa:Nw \exp_not:N #2
          \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
            {1} {1} {\l_regex_max_state_int}
            \regex_set_aux:n
          \regex_nfa_end:
        }
    \group_end:
    #1 #2 \g_regex_tmpa_tl
  }
\cs_new_nopar:Npn \regex_set_aux:n #1
  { \tex_toks:D #1 { \tex_the:D \tex_toks:D #1 } }
\cs_new:Npn \regex_nfa:Nw #1 #2 \regex_nfa_end:
  { \msg_expandable_error:n { Automaton~#1 used~incorrectly. } }
\cs_new_eq:NN \regex_nfa_end: \scan_stop:
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[int,TF]{\regex_check_nfa:N}
%   If a token list variable starts with \cs{regex_nfa:Nw},
%   then it most likely holds the data for a precompiled pattern.
%    \begin{macrocode}
\prg_new_protected_conditional:Npnn \regex_check_nfa:N #1 { T , TF }
  { \exp_after:wN \regex_check_nfa_aux:Nw #1 \q_stop }
\cs_new:Npn \regex_check_nfa_aux:Nw #1 #2 \q_stop
  {
    \if_meaning:w \regex_nfa:Nw #1
      \prg_return_true:
    \else:
      \msg_error:nnx { regex } { not-nfa } { \token_to_str:N #1 }
      \prg_return_false:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\regex_use:N}
%   No error-checking.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_use:N #1
  { \exp_after:wN \use_none:nn #1 }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Generic auxiliary functions}
%
% \begin{macro}[aux]{\regex_user_aux:n}
%   This is an auxiliary used by most user functions.
%   The first and second arguments control whether we should track
%   submatches, and whether we track one or multiple submatches.
%   Everything is done within a group, so that |#1| can perform
%   \enquote{unsafe} assignments. Most user functions return a
%   result using \cs{group_insert_after:N}.
%    \begin{macrocode}
\cs_new_protected:Npn \regex_user_aux:n #1
  {
    \group_begin:
      \tl_clear:N \l_regex_every_match_tl
      #1
    \group_end:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_return_after_group:}
%   Most of \pkg{l3regex}'s work is done within a group.
%   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_return_after_group:
  {
    \if_meaning:w \c_true_bool \l_regex_success_bool
      \group_insert_after:N \prg_return_true:
    \else:
      \group_insert_after:N \prg_return_false:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_extract_after_group:N}
%   Extract submatches, and store them in the user-given variable
%   after the group has ended.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_extract_after_group:N #1
  {
    \if_meaning:w \c_true_bool \l_regex_success_bool
      \regex_extract:
      \group_insert_after:N \seq_set_eq:NN
      \group_insert_after:N #1
      \group_insert_after:N \g_regex_submatches_seq
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\regex_count_after_group:N}
%   Same procedure as \cs{regex_extract_after_group:N}, but simpler
%   since the match counting has already taken place.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_count_after_group:N #1
  {
    \group_insert_after:N \int_set_eq:NN
    \group_insert_after:N #1
    \group_insert_after:N \g_regex_match_count_int
  }
%    \end{macrocode}
% \end{macro}
%
% \subsubsection{Matching}
%
% \begin{macro}[TF]{\regex_match:nn}
% \begin{macro}[TF]{\regex_match:Nn}
%   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_user_aux:n
      {
        \regex_disable_submatches:
        \regex_build:n {#1}
        \regex_match:n {#2}
        \regex_return_after_group:
      }
  }
\prg_new_protected_conditional:Npnn \regex_match:Nn #1#2 { T , F , TF }
  {
    \regex_check_nfa:NTF #1
      {
        \regex_user_aux:n
          {
            \regex_disable_submatches:
            \regex_use:N #1
            \regex_match:n {#2}
            \regex_return_after_group:
          }
      }
      { \prg_return_false: }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\regex_count:nnN}
% \begin{macro}{\regex_count:NnN}
%   Instead of aborting once the first \enquote{best 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:Npn \regex_count:nnN #1#2#3
  {
    \regex_user_aux:n
      {
        \regex_disable_submatches:
        \int_gzero:N \g_regex_match_count_int
        \tl_set:Nn \l_regex_every_match_tl
          {
            \int_gincr:N \g_regex_match_count_int
            \regex_match_once:
          }
        \regex_build:n {#1}
        \regex_match:n {#2}
        \regex_count_after_group:N #3
      }
  }
\cs_new_protected:Npn \regex_count:NnN #1#2#3
  {
    \regex_check_nfa:NT #1
      {
        \regex_user_aux:n
          {
            \regex_disable_submatches:
            \int_gzero:N \g_regex_match_count_int
            \tl_set:Nn \l_regex_every_match_tl
              {
                \int_gincr:N \g_regex_match_count_int
                \regex_match_once:
              }
            \regex_use:N #1
            \regex_match:n {#2}
            \regex_count_after_group:N #3
          }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \subsubsection{Submatch extraction}
%
% \begin{macro}{\regex_extract_once:nnN}
% \begin{macro}{\regex_extract_once:NnN}
% \begin{macro}[TF]{\regex_extract_once:nnN}
% \begin{macro}[TF]{\regex_extract_once:NnN}
%    \begin{macrocode}
\cs_new_protected:Npn \regex_extract_once:nnN #1#2#3
  {
    \regex_user_aux:n
      {
        \regex_build:n {#1}
        \regex_match:n {#2}
        \regex_extract_after_group:N #3
      }
  }
\prg_new_protected_conditional:Npnn \regex_extract_once:nnN #1#2#3
  { T , F , TF }
  {
    \regex_user_aux:n
      {
        \regex_build:n {#1}
        \regex_match:n {#2}
        \regex_extract_after_group:N #3
        \regex_return_after_group:
      }
  }
\cs_new_protected:Npn \regex_extract_once:NnN #1#2#3
  {
    \regex_check_nfa:NT #1
      {
        \regex_user_aux:n
          {
            \regex_use:N #1
            \regex_match:n {#2}
            \regex_extract_after_group:N #3
          }
      }
  }
\prg_new_protected_conditional:Npnn \regex_extract_once:NnN #1#2#3
  { T , F , TF }
  {
    \regex_check_nfa:NTF #1
      {
        \regex_user_aux:n
          {
            \regex_use:N #1
            \regex_match:n {#2}
            \regex_extract_after_group:N #3
            \regex_return_after_group:
          }
      }
      { \prg_return_false: }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\regex_extract_all:nnN}
% \begin{macro}{\regex_extract_all:NnN}
% \begin{macro}[aux]{\regex_extract_all_aux:}
% \begin{macro}[aux]{\regex_extract_all_after_group:N}
%   Similarly to \cs{regex_count:nnN} functions,
%   recurse through matches of the pattern. Then we do
%   something slightly different, extracting submatches.
%   Submatches are not extracted if the pattern matched
%   an empty string at the start of the match attempt
%   (to avoid adding spurious empty items to the resulting
%   sequence).
%    \begin{macrocode}
\cs_new_protected:Npn \regex_extract_all:nnN #1#2#3
  {
    \regex_user_aux:n
      {
        \seq_gclear:N \g_regex_extract_all_seq
        \tl_set:Nn \l_regex_every_match_tl { \regex_extract_all_aux: }
        \regex_build:n {#1}
        \regex_match:n {#2}
        \regex_extract_all_after_group:N #3
      }
  }
\cs_new_protected:Npn \regex_extract_all:NnN #1#2#3
  {
    \regex_check_nfa:NT #1
      {
        \regex_user_aux:n
          {
            \seq_gclear:N \g_regex_extract_all_seq
            \tl_set:Nn \l_regex_every_match_tl { \regex_extract_all_aux: }
            \regex_use:N #1
            \regex_match:n {#2}
            \regex_extract_all_after_group:N #3
          }
      }
  }
\cs_new_protected_nopar:Npn \regex_extract_all_aux:
  {
    \regex_extract:
    \seq_gconcat:NNN \g_regex_extract_all_seq
      \g_regex_extract_all_seq \g_regex_submatches_seq
    \regex_match_once:
  }
\cs_new_protected_nopar:Npn \regex_extract_all_after_group:N #1
  {
    \seq_if_empty:NF \g_regex_extract_all_seq
      {
        \regex_extract:
        \group_insert_after:N \seq_set_eq:NN
        \group_insert_after:N #1
        \group_insert_after:N \g_regex_extract_all_seq
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{Splitting a string by matches of a regex}
%
% \begin{macro}{\regex_split:nnN}
% \begin{macro}{\regex_split:NnN}
% \begin{macro}[aux]{\regex_split_aux:}
% \begin{macro}[aux]{\regex_split_after_group:N}
%   Similarly to \cs{regex_count:nnN} functions,
%   recurse through matches of the pattern. Then we do
%   something slightly different, extracting submatches.
%   Submatches are not extracted if the pattern matched
%   an empty string at the start of the match attempt
%   (to avoid adding spurious empty items to the resulting
%   sequence).
%    \begin{macrocode}
\cs_new_protected:Npn \regex_split:nnN #1#2#3
  {
    \regex_user_aux:n
      {
        \seq_gclear:N \g_regex_split_seq
        \tl_set:Nn \l_regex_every_match_tl { \regex_split_aux: }
        \regex_build:n {#1}
        \regex_match:n {#2}
        \regex_split_after_group:N #3
      }
  }
\cs_new_protected:Npn \regex_split:NnN #1#2#3
  {
    \regex_check_nfa:NT #1
      {
        \regex_user_aux:n
          {
            \seq_gclear:N \g_regex_split_seq
            \tl_set:Nn \l_regex_every_match_tl { \regex_split_aux: }
            \regex_use:N #1
            \regex_match:n {#2}
            \regex_split_after_group:N #3
          }
      }
  }
\cs_new_protected_nopar:Npn \regex_split_aux:
  {
    \int_compare:nNnF \l_regex_start_step_int = \l_regex_success_step_int
      {
        \regex_extract:
        \seq_pop:NN \g_regex_submatches_seq \l_regex_tmpa_tl
        \regex_extract_aux:nTF {0}
          {
            \seq_gput_left:Nx \g_regex_submatches_seq
              {
                \regex_query_substr:NN
                  \l_regex_start_step_int \l_regex_tmpa_tl
              }
          }
          { \msg_error:nn { regex } { internal } }
        \seq_gconcat:NNN \g_regex_split_seq
          \g_regex_split_seq \g_regex_submatches_seq
      }
    \regex_match_once:
  }
\cs_new_protected_nopar:Npn \regex_split_after_group:N #1
  {
    \int_compare:nNnTF \l_regex_start_step_int = \l_regex_current_step_int
      {
        \bool_if:NF \l_regex_success_empty_bool
          { \seq_gput_right:Nn \g_regex_split_seq { } }
      }
      {
        \seq_gput_right:Nx \g_regex_split_seq
          {
            \regex_query_substr:NN
              \l_regex_start_step_int \l_regex_current_step_int
          }
      }
    \group_insert_after:N \seq_set_eq:NN
    \group_insert_after:N #1
    \group_insert_after:N \g_regex_split_seq
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection{String replacement}
%
% \begin{macro}[int]{\regex_replacement:n}
% \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:n #1
  {
    \str_aux_escape:NNNn
      \prg_do_nothing:
      \regex_replacement_escaped:N
      \prg_do_nothing:
      {#1}
    \tl_set_eq:NN \l_regex_replacement_tl \g_str_result_tl
    \tl_set:Nx \l_regex_replacement_tl
      { \l_regex_replacement_tl \prg_do_nothing: }
  }
\cs_new_nopar:Npn \regex_replacement_escaped:N #1
  {
    \regex_token_if_other_digit:NTF #1
      {
        \exp_not:n
          { \exp_not:n { \seq_item:Nn \g_regex_submatches_seq } } {#1}
      }
      {
        \token_if_eq_charcode:NNTF g #1
          { \exp_not:N \regex_replacement_submatch:w }
          { #1 }
      }
  }
\cs_new_nopar:Npn \regex_replacement_submatch:w #1
  {
    \exp_after:wN \token_if_eq_meaning:NNTF \c_lbrace_str #1
      { \regex_replacement_submatch_aux:nN { } }
      {
        \regex_token_if_other_digit:NTF #1
          { \exp_not:n { \seq_item:Nn \g_regex_submatches_seq } }
          { \msg_expandable_error:n { \g misused~in~replacement~text. } }
        #1
      }
  }
\cs_new_nopar:Npn \regex_replacement_submatch_aux:nN #1 #2
  {
    \regex_token_if_other_digit:NTF #2
      { \regex_replacement_submatch_aux:nN {#1#2} }
      {
        \exp_not:n { \seq_item:Nn \g_regex_submatches_seq } {#1}
        \exp_after:wN \token_if_eq_meaning:NNF \c_rbrace_str #2
          {
            \msg_expandable_error:n { \g misused~in~replacement~text. }
            #2
          }
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}[aux]{\regex_replace_after_group:N}
%   I wonder why I implemented things with \tn{aftergroup}
%   rather than simply placing that code after the explicit
%   \cs{group_end:} that I have. (General remark.)
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \regex_replace_after_group:N #1
  {
    \group_insert_after:N \tl_set:Nx
    \group_insert_after:N #1
    \group_insert_after:N {
      \group_insert_after:N \tl_to_str:N
      \group_insert_after:N \g_regex_replaced_str
    \group_insert_after:N }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\regex_replace_once:nnN}
% \begin{macro}{\regex_replace_once:NnN}
% \begin{macro}[TF]{\regex_replace_once:nnN}
% \begin{macro}[TF]{\regex_replace_once:NnN}
% \begin{macro}[aux]{\regex_replace_once_aux:Nn}
%    \begin{macrocode}
\cs_new_protected:Npn \regex_replace_once_aux:Nn #1#2
  {
    \group_begin:
      \regex_replace_after_group:N #1
      \tl_clear:N \l_regex_every_match_tl
      #2
      \exp_args:No \regex_match:n {#1}
      \regex_extract:
      \regex_extract_aux:nTF {0}
        {
          \cs_set_nopar:Npn \regex_tmp:w
            { \str_skip_do:nn { \l_regex_tmpb_tl } { } }
          \tl_gset:Nx \g_regex_replaced_str
            {
              \regex_query_substr:NN \c_zero \l_regex_tmpa_tl
              \l_regex_replacement_tl
              \exp_after:wN \regex_tmp:w \l_regex_query_other_str
            }
        }
        { \tl_gset_eq:NN \g_regex_replaced_str \l_regex_query_other_str }
    \group_end:
  }
\cs_new_protected:Npn \regex_replace_once:nnN #1#2#3
  {
    \regex_replace_once_aux:Nn #3
      {
        \regex_build:n {#1}
        \regex_replacement:n {#2}
      }
  }
\cs_new_protected:Npn \regex_replace_once:NnN #1#2#3
  {
    \regex_replace_once_aux:Nn #3
      {
        \regex_use:N #1
        \regex_replacement:n {#2}
      }
  }
\prg_new_protected_conditional:Npnn \regex_replace_once:nnN #1#2#3 {T,F,TF}
  {
    \regex_replace_once_aux:Nn #3
      {
        \regex_build:n {#1}
        \regex_replacement:n {#2}
        \regex_return_after_group:
      }
  }
\prg_new_protected_conditional:Npnn \regex_replace_once:NnN #1#2#3 {T,F,TF}
  {
    \regex_replace_once_aux:Nn #3
      {
        \regex_use:N #1
        \regex_replacement:n {#2}
        \regex_return_after_group:
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\regex_replace_all:nnN}
% \begin{macro}{\regex_replace_all:NnN}
% \begin{macro}[aux]{\regex_replace_all_aux:Nn}
% \begin{macro}[aux]{\regex_replace_all_aux:}
%    \begin{macrocode}
\cs_new_protected:Npn \regex_replace_all_aux:Nn #1#2
  {
    \group_begin:
      \regex_replace_after_group:N #1
      \tl_set:Nn \l_regex_every_match_tl { \regex_replace_all_aux: }
      \tl_gclear:N \g_regex_replaced_str
      #2
      \exp_args:No \regex_match:n {#1}
      \cs_set_nopar:Npn \regex_tmp:w
        { \str_skip_do:nn { \l_regex_start_step_int } { } }
      \tl_gput_right:Nx \g_regex_replaced_str
        { \exp_after:wN \regex_tmp:w \l_regex_query_other_str }
    \group_end:
  }
\cs_new_protected_nopar:Npn \regex_replace_all_aux:
  {
    \regex_extract:
    \regex_extract_aux:nTF {0}
      {
        \tl_gput_right:Nx \g_regex_replaced_str
          {
            \regex_query_substr:NN
              \l_regex_start_step_int \l_regex_tmpa_tl
            \l_regex_replacement_tl
          }
      }
      { \msg_error:nn { regex } { internal } }
    \regex_match_once:
  }
\cs_new_protected:Npn \regex_replace_all:nnN #1#2#3
  {
    \regex_replace_all_aux:Nn #3
      {
        \regex_build:n {#1}
        \regex_replacement:n {#2}
      }
  }
\cs_new_protected:Npn \regex_replace_all:NnN #1#2#3
  {
    \regex_replace_all_aux:Nn #3
      {
        \regex_use:N #1
        \regex_replacement:n {#2}
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsection{Messages}
%
% Negative codes are specific to the \LaTeX3 implementation.
% Other error codes match with the PCRE codes (not all of
% the PCRE errors can occur, since many constructions are
% not supported).
%    \begin{macrocode}
% \msg_new:nnn { regex } { -999 } { File~not~found }
\msg_new:nnn { regex } { -998 } { Unsupported~construct }
\msg_new:nnn { regex } { -997 }
  { The~regular~expression~is~too~large~(32768~states). }
\msg_new:nnn { regex } { 1 } { \iow_char:N\\~at~end~of~pattern }
% \msg_new:nnn { regex } { 2 } { \iow_char:N\\c~at~end~of~pattern }
\msg_new:nnn { regex } { 4 }
  { Numbers~out~of~order~in~\iow_char:N\{\iow_char\}~quantifier. }
\msg_new:nnn { regex } { 6 }
  { Missing~terminating~\iow_char:N\]~for~character~class }
\msg_new:nnn { regex } { 7 }
  { Invalid~escape~sequence~in~character~class }
\msg_new:nnn { regex } { 8 }
  { Range~out~of~order~in~character~class }
\msg_new:nnn { regex } { 22 } { Mismatched~parentheses }
\msg_new:nnn { regex } { 34 }
  { Character~value~in~\iow_char:N\\x{...}~sequence~is~too~large }
% \msg_new:nnn { regex } { 44 } { Invalid~UTF-8~string }
% \msg_new:nnn { regex } { 46 }
%   { Malformed~\iow_char:N\\P~or\iow_char:N\\p~sequence }
% \msg_new:nnn { regex } { 47 }
%   { Unknown~property~after~\iow_char:N\\P~or\iow_char:N\\p }
% \msg_new:nnn { regex } { 68 }
%   { \iow_char:N\\c~must~be~followed~by~an~ASCII~character }
%    \end{macrocode}
%
%    \begin{macrocode}
\msg_new:nnn { regex } { not-nfa }
  {
    LaTeX~was~expecting~a~regular~expression~variable.\\
    Instead,~LaTeX~found~'#1'.
  }
%    \end{macrocode}
%
%    \begin{macrocode}
%</package>
%    \end{macrocode}
%
% \end{implementation}
%
% \endinput
%^^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