diff options
author | Karl Berry <karl@freefriends.org> | 2012-02-06 01:22:53 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2012-02-06 01:22:53 +0000 |
commit | a851d6714a00e2a09b93ba3e251d8665290c0ab8 (patch) | |
tree | 3ba045c487cc9e5e28e73714cb6312d0e556b924 /Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx | |
parent | a9533a6794104fad593912e3481304047dcd0025 (diff) |
l3experimental 3287
git-svn-id: svn://tug.org/texlive/trunk@25308 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx')
-rw-r--r-- | Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx | 2855 |
1 files changed, 1709 insertions, 1146 deletions
diff --git a/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx b/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx index d921b0b7e56..9c2b82c248d 100644 --- a/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx +++ b/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx @@ -35,7 +35,7 @@ % %<*driver|package> \RequirePackage{expl3} -\GetIdInfo$Id: l3regex.dtx 3200 2012-01-16 03:50:54Z bruno $ +\GetIdInfo$Id: l3regex.dtx 3259 2012-01-29 20:50:48Z bruno $ {L3 Experimental Regular Expressions} %</driver|package> %<*driver> @@ -77,7 +77,7 @@ % extraction of submatches, splitting, and replacement, all acting % on token lists. The syntax of regular expressions is mostly a subset % of the PCRE syntax (and very close to POSIX), with some additions -% due to the fact that we act on lists of tokens rather than characters. +% due to the fact that \TeX{} manipulates tokens rather than characters. % For performance reasons, only a limited set of features are implemented. % Notably, back-references are not supported. % @@ -101,12 +101,12 @@ % (here, a word). % % If a regular expression is to be used several times, -% it can be compiled once, and stored in a token list +% it can be compiled once, and stored in a regex % variable using \cs{regex_const:Nn}. For example, % \begin{verbatim} -% \regex_const:Nn \c_foo_regex_tl { \c{begin} \cB. (\c[^BE].*) \cE. } +% \regex_const:Nn \c_foo_regex { \c{begin} \cB. (\c[^BE].*) \cE. } % \end{verbatim} -% stores in \cs{c_foo_regex_tl} a regular expression which matches the +% stores in \cs{c_foo_regex} a regular expression which matches the % starting marker for an environment: \cs{begin}, followed by a % begin-group token (|\cB.|), then any number of tokens which are % neither begin-group nor end-group character tokens (|\c[^BE].*|), @@ -145,8 +145,9 @@ % using the |\c|\Arg{regex} syntax (see below). % % Any special character which appears at a place where its special -% behaviour cannot apply matches itself instead (for instance, -% a quantifier appearing at the beginning of a string). +% behaviour cannot apply matches itself instead (for instance, a +% quantifier appearing at the beginning of a string), after raising a +% warning. % % Characters. % \begin{l3regex-syntax} @@ -179,6 +180,7 @@ % \item[\\S] Any token not matched by |\s|. % \item[\\V] Any token not matched by |\v|. % \item[\\W] Any token not matched by |\w|. +% \item[\\N] Any token not matched by |\n|. % \end{l3regex-syntax} % Of those, |.|, |\D|, |\H|, |\N|, |\S|, |\V|, and |\W| will match arbitrary % control sequences. @@ -282,6 +284,14 @@ % digits, namely digits with category other, or uppercase letters from % |A| to |F| with category either letter or other. % +% The |\u| escape sequence allows to insert the contents of a token list +% directly into a regular expression or a replacement, avoiding the need +% to escape special characters. Namely, |\u|\Arg{tl~var~name} matches +% the exact contents of the token list \meta{tl~var}. Within a |\c{...}| +% control sequence matching, the |\u| escape sequence only expands its +% argument once, in effect performing \cs{tl_to_str:v}. Quantifiers are +% not supported directly: use a group. +% % Options can be set with |(?|\meta{option}|)| and % unset with |(?-|\meta{option}|)|. Options are local % to the group in which they are set, and revert to their @@ -336,9 +346,7 @@ % which must be one of |CBEMTPUDSLOA|. % \item[\\c\Arg{text}] Produces the control sequence with csname % \meta{text}. The \meta{text} may contain references to the submatches -% |\0|, |\1| \emph{etc.} As an experimental feature, |\c{...}| can be -% nested, but the behaviour is not yet fully specified. Use at own risks. -%^^A todo: decide what the right behaviour should be. +% |\0|, |\1| \emph{etc.} % \end{l3regex-syntax} % % \subsection{Precompiling regular expressions} @@ -346,50 +354,36 @@ % 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 +% regular expression is stored in a variable. All % of the \pkg{l3regex} module's functions can be given their % regular expression argument either as an explicit string % or as a precompiled regular expression. % +% \begin{function}{\regex_new:N} +% \begin{syntax} +% \cs{regex_new:N} \meta{regex~var} +% \end{syntax} +% Creates a new \meta{regex~var} or raises an error if the +% name is already taken. The declaration is global. The +% \meta{regex~var} will initially be such that it never matches. +% \end{function} +% % \begin{function}{\regex_set:Nn, \regex_gset:Nn, \regex_const:Nn} % \begin{syntax} -% \cs{regex_set:Nn} \meta{tl var} \Arg{regex} +% \cs{regex_set:Nn} \meta{regex~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 +% in the \meta{regex~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) } +% \regex_new:N \l_my_regex +% \regex_set:Nn \l_my_regex { my\ (simple\ )? reg(ex|ular\ expression) } % \end{verbatim} % The assignment is local for \cs{regex_set:Nn} and global for % \cs{regex_gset:Nn}. Use \cs{regex_const:Nn} for precompiled expressions % which will never change. % \end{function} % -% \begin{function}{\regex_to_str:N} -% \begin{syntax} -% \cs{regex_to_str:N} \meta{regex var} -% \end{syntax} -% Converts the \meta{regex var}, previously defined using -% \cs{regex_(g)set:Nn}, to a string, which can be safely -% read back when the \LaTeX3 syntax is active -% (as triggered by \cs{ExplSyntaxOn}). -% Line breaks are inserted at various places, to \emph{try} -% and keep the line length short. -% For instance, if \cs{l_my_stream} is an open stream for writing, -% and \cs{l_regex_tl} is a regex variable, you can save its definition -% using -% \begin{verbatim} -% \iow_now:Nx \l_my_stream -% { -% \tl_to_str:n { \tl_set:Nn \l_my_regex_tl } { \iow_newline: -% \regex_to_str:N \l_my_regex_tl -% } -% } -% \end{verbatim} -% \end{function} -% % \subsection{Matching} % % All regular expression functions are available in both |:n| and |:N| @@ -542,13 +536,9 @@ % % The following need to be done now. % \begin{itemize} -% \item The \texttt{\{\}} quantifiers are only partially implemented. -% \item Clean up the use of messages. -% \item Triple check magic numbers. -% \item Test \cs{par}. -% \item Add tests for every regex and replacement feature. -% \item Make sure the documentation is correct, and the code comments -% are as well. +% \item Clean up the use of messages. +% \item Code comments. +% \item Rewrite the documentation in a clearer way. % \end{itemize} % % Code improvements to come. @@ -559,14 +549,15 @@ % \item Use \tn{dimen} registers rather than \cs{l_regex_nesting_tl} % to build \cs{regex_nesting:n}. % \item Reduce the number of epsilon-transitions in alternatives. -% \item Improve nesting of |\c| in the replacement text. % \item Move the \enquote{reconstruction} part of \pkg{l3regex} % to \pkg{l3tl-analysis}. % \item Optimize regexes for csnames when the regex is a simple string. -% \item Optimize simple strings: use less states -% (|abcade| should give two states, for |abc| and |ade|). +% \item Optimize simple strings: use less states (|abcade| should give +% two states, for |abc| and |ade|). [Does that really make sense?] % \item Optimize groups with no alternative. % \item Optimize the use of \cs{prg_stepwise_...} functions. +% \item Decide what |\c{\c{...}}| should do in the replacement text. +% \item Fix the |\c{\cBx}| bug in replacement text. % \end{itemize} % % The following features are likely to be implemented at some point @@ -638,52 +629,164 @@ \RequirePackage{l3str, l3tl-analysis, l3flag} % \end{macrocode} % +% \subsection{Plan of attack} +% % Most regex engines use backtracking. This allows to provide very % powerful features (back-references come to mind first), but it is -% costly. 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. +% costly, and raises the problem of catastrophic backtracking. Since +% \TeX{} is not first and foremost a programming language, complicated +% code tends to run slowly, and we must use faster, albeit slightly more +% restrictive, techniques, coming from automata theory. % % Given a regular expression of $n$ characters, we build a % non-deterministic finite automaton (NFA) with roughly $n$ states, -% which accepts precisely those token lists matching that regular expression. -% We then run the token list through the NFA, and check the return value. +% which accepts precisely those token lists matching that regular +% expression. Then loop through the query token list one token (one +% \enquote{index}) at a time, exploring in parallel every possible path +% through the NFA. We keep track of an array of the states currently +% \enquote{active}, which are to be considered in order when the next +% token is read. +% +% We use the following vocabulary in the code comments (and in variable +% names). +% \begin{itemize} +% \item \emph{Query}: the token list to which we apply the regular +% expression. +% \item \emph{Index}: each token in the query is labelled by an integer +% \meta{index}, with $\cs{l_regex_min_index_int} - 1 \leq \meta{index} +% \leq \cs{l_regex_max_index_int}$. The lowest and highest indexes +% correspond to imaginary begin and end markers (with inacessible +% category code and character code). +% \item \emph{Step}:^^A todo: fill +% \item \emph{State}: each state of the NFA is labelled by an integer +% \meta{state} with $0 \leq \meta{state} < +% \cs{l_regex_max_state_int}$. +% \item \emph{Active state}: state of the NFA that is reached when +% reading the query string for the matching. Those states are +% ordered according to the greediness of quantifiers. +% \end{itemize} +% +% To acheive a good performance, we abuse \TeX{}'s registers in two +% ways. We access registers directly by number rather than tying them +% to control sequence using \cs{int_new:N} and other allocation +% functions. And we store integers in \tn{dimen} registers in scaled +% points (\texttt{sp}), using \TeX{}'s implicit conversion from +% dimensions to integers in some contexts. Specifically, the registers +% are used as follows. +% \begin{itemize} +% \item \tn{toks}\meta{state} has two parts: a property list which +% holds the submatch information, followed by the tests and actions +% to perform in the \meta{state} of the NFA. +% \item \tn{dimen}\meta{state} is equal to the last step in which +% the \meta{state} was active. +% \item \tn{skip}$i$ holds the \meta{state} number corresponding to +% the $i$-th active \meta{state} (in order of precedence: smaller is +% more important) and has no shrink or stretch components. +% \item \tn{toks}\meta{index} holds \meta{tokens} which \texttt{o}- +% and \texttt{x}-expand to the \meta{index}-th token in the query. +% \end{itemize} +% \tn{count} registers are not abused, which means that we can safely +% use named integers. % -% The code is structured as follows. 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. +% The code is structured as follows. Variables, constants and various +% helper functions are introduced first, to limit the clutter in later +% parts. Then functions pertaining to parsing the regular expression are +% defined: that part is rather long because of the many bells and +% whistles of the regex notation. The next subsection takes care of +% running the NFA. Finally, user functions. % % \subsection{Constants and variables} % +% \subsubsection{Generic} +% % \begin{macro}{\regex_tmp:w} -% \begin{variable}{\l_regex_tmpa_tl, \l_regex_tmpb_tl, \l_regex_tmpc_tl} -% \begin{variable}{\l_regex_tmpa_int, \l_regex_tmpb_int} -% Temporary variables. +% \begin{variable} +% {\l_regex_internal_a_int, \l_regex_internal_b_int, \l_regex_internal_c_int} +% \begin{variable}{\l_regex_internal_a_tl, \l_regex_internal_b_tl} +% \begin{variable}{\g_regex_internal_tl} +% Temporary variables used for various purposes. % \begin{macrocode} \cs_new:Npn \regex_tmp:w { } -\tl_new:N \l_regex_tmpa_tl -\tl_new:N \l_regex_tmpb_tl -\tl_new:N \l_regex_tmpc_tl -\int_new:N \l_regex_tmpa_int -\int_new:N \l_regex_tmpb_int +\tl_new:N \l_regex_internal_a_tl +\tl_new:N \l_regex_internal_b_tl +\int_new:N \l_regex_internal_a_int +\int_new:N \l_regex_internal_b_int +\int_new:N \l_regex_internal_c_int +\tl_new:N \g_regex_internal_tl % \end{macrocode} % \end{variable} % \end{variable} +% \end{variable} % \end{macro} % -% \begin{variable}{\l_regex_group_begin_flag} -% \begin{variable}{\l_regex_group_end_flag} -% Those flags are raised to indicate extra begin-group -% or end-group tokens when extracting submatches. +% \begin{variable} +% { +% \c_regex_d_tl, \c_regex_D_tl, \c_regex_h_tl, \c_regex_H_tl, +% \c_regex_s_tl, \c_regex_S_tl, \c_regex_v_tl, \c_regex_V_tl, +% \c_regex_w_tl, \c_regex_W_tl, \c_regex_N_tl +% } +% +% These constant token lists encode which characters are recognized by +% |\d|, |\D|, |\w|, \emph{etc.} in regular expressions. Namely, +% |\d=[0-9]|, |\w=[0-9A-Z_a-z]|, \verb*+\s=[\ \^^I\^^J\^^L\^^M]+, +% \verb*+\h=[\ \^^I]+, |\v=[\^^J-\^^M]|, and the upper case +% counterparts match anything that the lower case does not match. The +% order in which the various tests appear is optimized for usual +% mostly lower case letter text. % \begin{macrocode} -\flag_new:N \l_regex_group_begin_flag -\flag_new:N \l_regex_group_end_flag +\tl_const:Nn \c_regex_d_tl + { \regex_item_range:nn \c_forty_eight { 57 } } % 0--9 +\tl_const:Nn \c_regex_h_tl + { + \regex_item_equal:n \c_thirty_two % space + \regex_item_equal:n \c_nine % tab + } +\tl_const:Nn \c_regex_s_tl + { + \regex_item_equal:n \c_thirty_two % space + \regex_item_equal:n \c_nine % tab + \regex_item_equal:n \c_ten % lf + \regex_item_equal:n \c_twelve % ff + \regex_item_equal:n \c_thirteen % cr + } +\tl_const:Nn \c_regex_v_tl + { \regex_item_range:nn \c_ten \c_thirteen } % lf, vtab, ff, cr +\tl_const:Nn \c_regex_w_tl + { + \regex_item_range:nn \c_ninety_seven { 122 } % a--z + \regex_item_range:nn \c_sixty_five { 90 } % A--Z + \regex_item_range:nn \c_forty_eight { 57 } % 0--9 + \regex_item_equal:n { 95 } % _ + } +\tl_const:Nn \c_regex_D_tl + { \c_regex_d_tl \regex_break_point:TF { } \regex_break_true:w } +\tl_const:Nn \c_regex_H_tl + { \c_regex_h_tl \regex_break_point:TF { } \regex_break_true:w } +\tl_const:Nn \c_regex_S_tl + { \c_regex_s_tl \regex_break_point:TF { } \regex_break_true:w } +\tl_const:Nn \c_regex_V_tl + { \c_regex_v_tl \regex_break_point:TF { } \regex_break_true:w } +\tl_const:Nn \c_regex_W_tl + { \c_regex_w_tl \regex_break_point:TF { } \regex_break_true:w } +\tl_const:Nn \c_regex_N_tl + { + \regex_item_equal:n \c_ten + \regex_break_point:TF { } { \regex_break_true:w } + } % \end{macrocode} % \end{variable} +% +% \begin{variable}{\c_regex_._tl} +% The dot meta-character matches any character, except the end marker, +% whose character code is $-2$. +% \begin{macrocode} +\tl_const:cn { c_regex_._tl } + { + \if_num:w \l_regex_current_char_int > - \c_two + \exp_after:wN \regex_break_true:w + \fi: + } +% \end{macrocode} % \end{variable} % % \subsubsection{Variables used while building} @@ -746,6 +849,10 @@ % This number is used when a branch of the alternation ends. % Capturing groups can be arbitrarily nested, and we keep track of % the stack of ID numbers in \cs{l_regex_capturing_group_seq}. +% The \texttt{max_int} variable is used in the case of the special +% groups \verb+(?|...|...)+, which reset the capturing group number in +% each alternative: at the end of the group, we must use a number +% larger than every capturing group appearing in any alternative. % \begin{macrocode} \int_new:N \l_regex_capturing_group_int \seq_new:N \l_regex_capturing_group_seq @@ -784,7 +891,9 @@ % all allowed catcodes $c$. The latter is local to each capturing % group, and we reset \cs{l_regex_catcodes_int} to that value after % each character or class, changing it only when encountering a |\c| -% escape. +% escape. Errata: the \cs{l_regex_catcodes_default_int} is not used +% yet, because the idea of having \verb+\cL(...|...)+ act on the whole +% contents of the group is not yet implemented. % \begin{macrocode} \int_new:N \l_regex_catcodes_int \int_new:N \l_regex_catcodes_default_int @@ -814,194 +923,108 @@ % \end{macrocode} % \end{variable} % -% \begin{variable}{\l_regex_tmpa_regex_tl} -% This holds a temporary pre-compiled regular expression -% when matching a control sequence name. -% \begin{macrocode} -\tl_new:N \l_regex_tmpa_regex_tl +% \begin{variable}{\l_regex_tests_bool,\l_regex_tests_tl} +% The tests which should be performed on an item of the token list are +% stored in \cs{l_regex_tests_tl}. In the case of character classes, +% \cs{l_regex_tests_bool} is \texttt{false} for negative character +% classes. In the other case, \cs{l_regex_tests_tl} is directly +% converted to a state of the NFA. The two variables are cleared +% (boolean set to \texttt{true}) after looking for a quantifier for +% the class or single character or property. It would seem cleaner to +% clear them instead before grabbing the next character or class, but +% that doesn't interact correctly with constructions like |\cL[...]| +% where |\cL| inserts some tests in \cs{l_regex_tests_tl}, which +% should not be eliminated before finding the class. +% \begin{macrocode} +\bool_new:N \l_regex_tests_bool +\tl_new:N \l_regex_tests_tl % \end{macrocode} % \end{variable} % -% \subsubsection{Character classes} -% -% \begin{variable}{\l_regex_class_bool,\l_regex_class_tl} -% \begin{variable}{\l_regex_class_saved_bool,\l_regex_class_saved_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. In nested class, which can only occur as -% |[\c[...]]|, the two variables from the outer class must be saved -% while processing the inner class. +% \begin{variable} +% { +% \l_regex_tests_saved_bool, +% \l_regex_tests_saved_tl, +% \l_regex_catcodes_saved_int +% } +% In nested class, which can only occur as |[\cA[...]]|, the variables +% \cs{l_regex_tests_bool}, \cs{l_regex_tests_tl}, and +% \cs{l_regex_catcodes_int} from the outer class must be saved while +% processing the inner class. % \begin{macrocode} -\bool_new:N \l_regex_class_bool -\tl_new:N \l_regex_class_tl -\bool_new:N \l_regex_class_saved_bool -\tl_new:N \l_regex_class_saved_tl +\bool_new:N \l_regex_tests_saved_bool +\tl_new:N \l_regex_tests_saved_tl +\int_new:N \l_regex_catcodes_saved_int % \end{macrocode} % \end{variable} -% \end{variable} % -% \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. +% \subsubsection{Variables used when matching} +% +% \begin{variable}{\l_regex_min_index_int} +% \begin{variable}{\l_regex_max_index_int} +% The tokens in the query are indexed from \cs{l_regex_min_index_int} +% for the first to $\cs{l_regex_max_index_int}-1$ for the last, and +% their information is stored in \tn{muskip} and \tn{toks} registers +% with those numbers. We don't start from $0$ because the \tn{toks} +% registers with low numbers are used to hold the states of the NFA. % \begin{macrocode} -\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 - } +\int_new:N \l_regex_min_index_int +\int_new:N \l_regex_max_index_int % \end{macrocode} % \end{variable} % \end{variable} -% \end{variable} -% \end{variable} -% \end{variable} -% \end{variable} -% -% \subsubsection{Variables used when matching} % % \begin{variable}{\l_regex_nesting_int} -% This integer is used to keep track of begin and end-group tokens. +% The first phase when matching is to go once through the query token +% list and store the information for each token as \tn{muskip} and +% \tn{toks} registers. During this phase, \cs{l_regex_nesting_int} +% counts the balance of begin-group and end-group character tokens +% which appear before a given point in the string, and is stored as +% the shrink component of the \tn{muskip} registers. This integer is +% also used to keep track of the balance in the replacement text. % \begin{macrocode} \int_new:N \l_regex_nesting_int % \end{macrocode} % \end{variable} % -% \begin{variable}{\l_regex_min_step_int} -% \begin{variable}{\l_regex_max_step_int} -% This integer holds the value of the step corresponding to -% the left end of the token list, \emph{i.e.}, when the token -% list is stored in \tn{toks} registers, the \tn{toks} register -% \cs{l_regex_min_step_int} holds the first token in the token -% list. In fact, this number is always one more than -% \cs{l_regex_max_state_int}, but it is more practical to give -% that a name. -% \begin{macrocode} -\int_new:N \l_regex_min_step_int -\int_new:N \l_regex_max_step_int -% \end{macrocode} -% \end{variable} -% \end{variable} -% -% \begin{variable}{\l_regex_current_step_int} -% \begin{variable}{\l_regex_start_step_int} -% \begin{variable}{\l_regex_success_step_int} +% \begin{variable}{\l_regex_current_index_int} +% \begin{variable}{\l_regex_start_index_int} +% \begin{variable}{\l_regex_success_index_int} % While reading through the query token list, -% \cs{l_regex_current_step_int} is the position in the -% token list, starting at \cs{l_regex_min_step_int} for -% the left-most token. -% 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). +% \cs{l_regex_current_index_int} is the position in the token list, +% starting at \cs{l_regex_min_index_int} for the first token. +% Each match begins at the position given by +% \cs{l_regex_start_index_int}. Whenever an execution thread succeeds, +% the corresponding index is stored into \cs{l_regex_success_index_int}, +% which will be the next starting index (except in the case of empty +% matches). % \begin{macrocode} -\int_new:N \l_regex_current_step_int -\int_new:N \l_regex_start_step_int -\int_new:N \l_regex_success_step_int +\int_new:N \l_regex_current_index_int +\int_new:N \l_regex_start_index_int +\int_new:N \l_regex_success_index_int % \end{macrocode} % \end{variable} % \end{variable} % \end{variable} % -% \begin{variable}{\l_regex_unique_id_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_id_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_id_int -% \end{macrocode} -% \end{variable} -% % \begin{variable}{\l_regex_current_char_int} % \begin{variable}{\l_regex_current_catcode_int} % \begin{variable}{\l_regex_current_token_tl} % \begin{variable}{\l_regex_last_char_int} % \begin{variable}{\l_regex_case_changed_char_int} -% The character codes of the character at the current position -% in the token list, 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. +% The character and category codes of the token at the current +% position; \meta{tokens} which \texttt{o}- and \texttt{x}-expand to +% the token (as provided by \cs{tl_analysis:n}); the character code of +% the token at the previous position; and the character code of the +% result of changing the case of the current token +% (|A-Z|$\leftrightarrow$|a-z|). This last integer is only computed if +% the \enquote{case insensitive} option |(?i)| is used in the regex. +% The \cs{l_regex_current_char_int} variable is also used in various +% other phases to hold a character code. % \begin{macrocode} \int_new:N \l_regex_current_char_int \int_new:N \l_regex_current_catcode_int -\tl_new:N \l_regex_current_token_tl +\tl_new:N \l_regex_current_token_tl \int_new:N \l_regex_last_char_int \int_new:N \l_regex_case_changed_char_int % \end{macrocode} @@ -1025,7 +1048,7 @@ % 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, +% In some cases of groups with quantifiers, % \cs{l_regex_current_state_int} is shifted to a fake value for % transitions to point to the correct states. % \begin{macrocode} @@ -1050,40 +1073,77 @@ % \end{variable} % \end{variable} % -% \begin{variable}{\l_regex_max_index_int} +% \begin{variable}{\l_regex_step_int} +% In the case of repeated matches, \cs{l_regex_current_index_int} +% is reset to the end-position of the previous match. In contrast, +% \cs{l_regex_step_int} is simply incremented to provide +% a unique number for each iteration of the matching loop. This +% is handy to attach each set of submatch information to a given +% iteration (and automatically discard it when it corresponds to +% a past iteration). +% \begin{macrocode} +\int_new:N \l_regex_step_int +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_regex_max_active_int} % All the currently active states are kept in order of precedence % in the \tn{skip} registers, which for our purpose serve as an array: % the $i$th item of the array is \tn{skip}$i$. The largest index used -% after treating the previous character is \cs{l_regex_max_index_int}. +% after treating the previous character is \cs{l_regex_max_active_int}. % At the start of every step, the whole array is unpacked, so that the -% space can immediately be reused, and \cs{l_regex_max_index_int} reset -% to zero, effectively clearing the array. +% space can immediately be reused, and \cs{l_regex_max_active_int} is +% reset to zero, effectively clearing the array. % \begin{macrocode} -\int_new:N \l_regex_max_index_int +\int_new:N \l_regex_max_active_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 token list. For multiple matching, -% the token list is set to repeat the matching. +% \begin{variable}{\l_regex_every_match_tl} +% Every time a match is found, this token list is used. For single +% matching, the token list is empty. For multiple matching, the token +% list is set to repeat the matching. % \begin{macrocode} \tl_new:N \l_regex_every_match_tl % \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_regex_fresh_thread_bool} +% \begin{variable}{\l_regex_success_empty_bool} +% \begin{macro}{\regex_if_two_empty_matches:F} +% When doing multiple matches, we need to avoid infinite loops where +% each iteration matches the same empty token list. When an empty +% token list is matched, the next successful match of the same empty +% token list is suppressed. We detect empty matches by setting +% \cs{l_regex_fresh_thread_bool} to \texttt{true} for threads which +% directly come from the start of the regular expression, and testing +% that boolean whenever a thread succeeds. The function +% \cs{regex_if_two_empty_matches:F} is redefined at every match +% attempt, depending on whether the previous match was empty or not: +% if it was, then the function must cancel a purported success if it +% is empty and at the same spot as the previous match; otherwise, we +% definitely don't have two identical empty matches, so the function +% is \cs{use:n}. +% \begin{macrocode} +\bool_new:N \l_regex_fresh_thread_bool +\bool_new:N \l_regex_success_empty_bool +\cs_new_eq:NN \regex_if_two_empty_matches:F \use:n +% \end{macrocode} % \end{macro} +% \end{variable} +% \end{variable} % % \begin{variable}{\g_regex_success_bool} % \begin{variable}{\l_regex_saved_success_bool} % \begin{variable}{\l_regex_success_match_bool} -% The boolean \cs{g_regex_success_bool} is true if there was -% at least one match, and \cs{l_regex_success_match_bool} is -% true if the current match attempt was successful. -% The variable \cs{g_regex_success_bool} is the only global -% variable in this whole module. When nesting \cs{regex} -% functions internally, the value of \cs{g_regex_success_bool} -% is saved into \cs{l_regex_saved_success_bool}, which is local, -% hence not affected by the changes due to inner regex functions. +% The boolean \cs{g_regex_success_bool} is true if there was at least +% one successful match, and \cs{l_regex_success_match_bool} is true if +% the current match attempt was successful. The variable +% \cs{g_regex_success_bool} is the only global variable in this whole +% module. When nesting \cs{regex} functions internally, the value of +% \cs{g_regex_success_bool} is saved into +% \cs{l_regex_saved_success_bool}, which is local, hence not affected +% by the changes due to inner regex functions. % \begin{macrocode} \bool_new:N \g_regex_success_bool \bool_new:N \l_regex_saved_success_bool @@ -1093,55 +1153,63 @@ % \end{variable} % \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 token list. 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. +% \subsubsection{Regular expression variables} +% +% \begin{variable}{\c_regex_no_match_regex} +% This regular expression matches nothing, but is still a valid +% regular expression. It is used as the initial value for regular +% expressions declared using \cs{regex_new:N}. % \begin{macrocode} -\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 +\tl_const:Nn \c_regex_no_match_regex + { + \regex_nfa:Nw \c_regex_no_match_regex + \l_regex_max_state_int = \c_one + \l_regex_capturing_group_int = \c_zero + \tex_toks:D \c_zero { \s_stop } + \s_stop + } +% \end{macrocode} +% \end{variable} +% +% \begin{macro}{\regex_new:N} +% As for many data types deriving from the \texttt{tl} data type, +% creating a new one is simply a matter of checking that it does not +% exist yet, and setting it equal to a default value. +% \begin{macrocode} +\cs_new_protected:Npn \regex_new:N #1 + { + \chk_if_free_cs:N #1 + \cs_gset_eq:NN #1 \c_regex_no_match_regex + } % \end{macrocode} -% \end{macro} -% \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{variable}{\l_regex_internal_regex} +% This holds a temporary pre-compiled regular expression +% when matching a control sequence name. % \begin{macrocode} -\bool_new:N \l_regex_success_empty_bool -\bool_new:N \l_regex_fresh_thread_bool +\regex_new:N \l_regex_internal_regex % \end{macrocode} % \end{variable} -% \end{variable} % -% \subsubsection{Variables used when building the replacement} +% \subsubsection{Other variables} +%^^A todo: move? +%^^A todo: run with the check-declarations option. % -% \begin{variable}{\l_regex_replacement_int} +% \begin{variable}{\l_regex_replacement_csnames_int} +% The behaviour of closing braces inside a replacement text depends on +% whether a sequences |\c{| or |\u{| has been encountered. The number +% of \enquote{open} such sequences that should be closed by |}| is +% stored in \cs{l_regex_replacement_csnames_int}, and decreased by +% $1$ by each |}|. % \begin{macrocode} -\int_new:N \l_regex_replacement_int +\int_new:N \l_regex_replacement_csnames_int % \end{macrocode} % \end{variable} % -% \begin{variable}{\l_regex_replacement_csnames_int} +% \begin{variable}{\l_regex_replacement_int} % \begin{macrocode} -\int_new:N \l_regex_replacement_csnames_int +\int_new:N \l_regex_replacement_int % \end{macrocode} % \end{variable} % @@ -1154,8 +1222,6 @@ % \end{variable} % \end{variable} % -% \subsubsection{Variables used for user functions} -% % \begin{variable}{\l_regex_match_count_int} % The number of matches found so far is stored % in \cs{l_regex_match_count_int}. This is only used @@ -1165,23 +1231,29 @@ % \end{macrocode} % \end{variable} % +% \begin{variable}{regex_begin, regex_end} +% Those flags are raised to indicate extra begin-group +% or end-group tokens when extracting submatches. +% \begin{macrocode} +\flag_new:n { regex_begin } +\flag_new:n { regex_end } +% \end{macrocode} +% \end{variable} +% % \subsection{Helpers} % % \subsubsection{Toks} % -% When performing the matching, the \tn{toks} registers hold submatch -% information, followed by the instruction for a given state of the NFA. -% The two parts are separated by \cs{s_stop}. +% Two unrelated sets of functions for manipulating \tn{toks} registers. % % \begin{macro}[int]{\regex_toks_put_left:Nx} % \begin{macro}[int]{\regex_toks_put_right:Nx} % During the building phase, every \tn{toks} register starts with -% \cs{s_stop}, and we wish to add \texttt{x}-expanded material -% to those registers. The expansion is done \enquote{by hand} for +% \cs{s_stop}, and we wish to add \texttt{x}-expanded material to +% those registers. The expansion is done \enquote{by hand} for % optimization (these operations are used quite a lot). When adding % material to the left, we define \cs{regex_tmp:w} to remove the -% \cs{s_stop} marker and put it back to the left of the new -% material. +% \cs{s_stop} marker and put it back to the left of the new material. % \begin{macrocode} \cs_new_protected:Npn \regex_toks_put_left:Nx #1#2 { @@ -1199,20 +1271,52 @@ % \end{macro} % \end{macro} % -% \subsubsection{Extracting parts of the query token list} -% -% \begin{macro}[int]{\regex_query_substr:nn} -% \begin{macro}[int]{\regex_query_submatch:nn} -% \begin{macro}[int]{\regex_query_submatch:w} -% The token list is stored in \tn{toks} registers: -% the first is \cs{l_regex_min_step_int}, the last is (we don't care yet). +% \begin{macro}[int, rEXP]{\regex_toks_range:nn} +% \begin{macro}[aux, rEXP]{\regex_toks_range:ww} +% Some non-expandable functions store pieces of their result in +% \tn{toks} registers. Those pieces are concatenated using +% \cs{regex_toks_range:nn}, which expects two integers, \meta{start} +% and \meta{end}, and expands to the contents of the \tn{toks} +% registers from \meta{start} (inclusive) to \meta{end} +% (exclusive). This correctly expands to nothing if \meta{start} +% $\geq$ \meta{end}. % \begin{macrocode} -\cs_new:Npn \regex_query_substr:nn #1#2 +\cs_new:Npn \regex_toks_range:nn #1#2 { - \if_num:w \int_eval:w #1 < \int_eval:w #2 \int_eval_end: - \str_aux_toks_range:nn {#1} {#2} + \exp_after:wN \regex_toks_range:ww + \int_use:N \int_eval:w #1 \exp_after:wN ; + \int_use:N \int_eval:w #2 ; + \prg_break_point:n { } + } +\cs_new:Npn \regex_toks_range:ww #1 ; #2 ; + { + \if_num:w #1 < #2 \exp_stop_f: + \else: + \exp_after:wN \prg_map_break: \fi: + \tex_the:D \tex_toks:D #1 \exp_stop_f: + \exp_after:wN \regex_toks_range:ww + \int_use:N \int_eval:w #1 + \c_one ; #2 ; } +% \end{macrocode} +% \end{macro} +% \end{macro} +% +% On the one hand, when performing the matching, the \tn{toks} registers +% hold submatch information, followed by the instruction for a given +% state of the NFA. The two parts are separated by \cs{s_stop}. On the +% other hand, we provide functions to unpack the contents from a range +% of \tn{toks} within an \texttt{x}-expanding assignment. +% +% When it is time to extract submatches from the token list, the various +% tokens are stored in \tn{toks} registers numbered from +% \cs{l_regex_min_index_int} inclusive to \cs{l_regex_max_index_int} +% exclusive. Furthermore, the \tn{skip} registers hold\ldots{} ^^A ?? +% +% \begin{macro}[int]{\regex_query_submatch:nn} +% \begin{macro}[int]{\regex_query_submatch:w} +%^^A ?? +% \begin{macrocode} \cs_new:Npn \regex_query_submatch:nn #1#2 { \if_num:w #1 < \l_regex_capturing_group_int @@ -1222,14 +1326,13 @@ } \cs_new:Npn \regex_query_submatch:w #1 ; { - \regex_query_substr:nn + \regex_toks_range:nn { \tex_skip:D #1 } { \etex_gluestretch:D \tex_skip:D #1 } } % \end{macrocode} % \end{macro} % \end{macro} -% \end{macro} % % \subsubsection{Sequences} % @@ -1243,13 +1346,13 @@ % \begin{macrocode} \cs_new_protected:Npn \regex_seq_pop_int:NN #1#2 { - \seq_pop:NN #1 \l_regex_tmpa_tl - \int_set:Nn #2 \l_regex_tmpa_tl + \seq_pop:NN #1 \l_regex_internal_a_tl + \int_set:Nn #2 \l_regex_internal_a_tl } \cs_new_protected:Npn \regex_seq_get_int:NN #1#2 { - \seq_get:NN #1 \l_regex_tmpa_tl - \int_set:Nn #2 \l_regex_tmpa_tl + \seq_get:NN #1 \l_regex_internal_a_tl + \int_set:Nn #2 \l_regex_internal_a_tl } \cs_new_protected:Npn \regex_seq_push_int:NN #1#2 { \seq_push:No #1 { \int_use:N #2 } } @@ -1267,13 +1370,54 @@ % \begin{macrocode} \cs_new_protected:Npn \regex_seq_pop_use:N #1 { - \seq_pop:NN #1 \l_regex_tmpa_tl - \l_regex_tmpa_tl + \seq_pop:NN #1 \l_regex_internal_a_tl + \l_regex_internal_a_tl } \cs_new_protected:Npn \regex_seq_get_use:N #1 { - \seq_get:NN #1 \l_regex_tmpa_tl - \l_regex_tmpa_tl + \seq_get:NN #1 \l_regex_internal_a_tl + \l_regex_internal_a_tl + } +% \end{macrocode} +% \end{macro} +% \end{macro} +% +% \subsubsection{Grabbing digits} +% +% \begin{macro}[int]{\regex_get_digits:nw} +% \begin{macro}[aux]{\regex_get_digits_loop:N,\regex_get_digits_end:w} +% When parsing the \texttt{\{} quantifier, we need a tool to grab +% digits until reaching the first non-digit. This +% \cs{regex_get_digits:nw} function places whatever digits it found as +% a brace group after |#1|. +% \begin{macrocode} +\cs_new_protected:Npn \regex_get_digits:nw #1 + { + \tex_afterassignment:D \regex_tmp:w + \cs_set_nopar:Npx \regex_tmp:w + { + \exp_not:n {#1} + { \if_false: } } \fi: + \regex_get_digits_aux:NN + } +\cs_new:Npn \regex_get_digits_aux:NN #1#2 + { + \if_meaning:w \regex_build_raw:N #1 + \if_num:w 9 < 1 \exp_not:N #2 \exp_stop_f: + #2 + \else: + \regex_get_digits_end:w #1 #2 + \fi: + \else: + \regex_get_digits_end:w #1 #2 + \fi: + \regex_get_digits_aux:NN + } +\cs_new:Npn \regex_get_digits_end:w #1 \fi: #2 \regex_get_digits_aux:NN + { + \fi: #2 + \if_false: { { \fi: } } + #1 } % \end{macrocode} % \end{macro} @@ -1303,19 +1447,6 @@ % \end{macro} % \end{macro} % -% \begin{macro}{\regex_item_dot:} -% The dot meta-character matches any character, -% except the end marker. -% \begin{macrocode} -\cs_new_protected_nopar:Npn \regex_item_dot: - { - \if_num:w \l_regex_current_char_int > - \c_two - \exp_after:wN \regex_break_true:w - \fi: - } -% \end{macrocode} -% \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} @@ -1394,7 +1525,7 @@ % \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 +% they will expand at the building phase, hard-coding which % states take care of caseless versus caseful matching. % \begin{macrocode} \cs_new:Npn \regex_item_equal:n { \regex_item_caseful_equal:n } @@ -1407,7 +1538,7 @@ % % \begin{macro}[int]{\regex_build_caseless:,\regex_build_caseful:} % Switch between caseful and caseless matching. -% This is only done during the building step. +% This is only done during the building phase. % \begin{macrocode} \cs_new_protected_nopar:Npn \regex_build_caseless: { @@ -1426,23 +1557,27 @@ % \end{macrocode} % \end{macro} % -% \begin{macro}{\regex_item_catcode:nT} +% \begin{macro}[int]{\regex_item_catcode:nT} +% \begin{macro}[aux]{\regex_item_catcode_aux:} % The argument is a sum of powers of $4$ with exponents given by the % allowed category codes (between $0$ and $13$). Dividing by a given % power of $4$ gives an odd result if and only if that category code % is allowed. If the catcode does not match, then skip the character % code tests which follow. % \begin{macrocode} +\cs_new_protected:Npn \regex_item_catcode_aux: + { + " + \if_case:w \l_regex_current_catcode_int + 1 \or: 4 \or: 10 \or: 40 + \or: 100 \or: \or: 1000 \or: 4000 + \or: 10000 \or: \or: 100000 \or: 400000 + \or: 1000000 \or: 4000000 \else: 1*\c_zero + \fi: + } \cs_new_protected:Npn \regex_item_catcode:nT #1 { - \if_int_odd:w \int_eval:w #1 / " - \if_case:w \l_regex_current_catcode_int - 1 \or: 4 \or: 10 \or: 40 - \or: 100 \or: \or: 1000 \or: 4000 - \or: 10000 \or: \or: 100000 \or: 400000 - \or: 1000000 \or: 4000000 \else: 1*\c_zero - \fi: - \int_eval_end: + \if_int_odd:w \int_eval:w #1 / \regex_item_catcode_aux: \int_eval_end: \exp_after:wN \use:n \else: \exp_after:wN \use_none:n @@ -1450,6 +1585,7 @@ } % \end{macrocode} % \end{macro} +% \end{macro} % % \begin{macro}[int]{\regex_item_cs:n} % Match a control sequence (the argument is a pre-compiled regex). @@ -1463,9 +1599,9 @@ { \int_compare:nNnT \l_regex_current_catcode_int = \c_zero { - \tl_set:Nn \l_regex_tmpa_regex_tl {#1} + \tl_set:Nn \l_regex_internal_regex {#1} \bool_set_eq:NN \l_regex_saved_success_bool \g_regex_success_bool - \exp_args:NNx \regex_match:NnTF \l_regex_tmpa_regex_tl + \exp_args:NNx \regex_match:NnTF \l_regex_internal_regex { \exp_after:wN \exp_after:wN \exp_after:wN \cs_to_str:N \l_regex_current_token_tl @@ -1480,67 +1616,246 @@ % \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 +% \subsubsection{Simple character escape} +% +% Before actually parsing the regular expression or the replacement +% text, we go through them once, converting |\n| to the character $10$, +% \emph{etc.} In this pass, we also convert any special character +% (\texttt{*}, \texttt{?}, \texttt{\{}, etc.) or escaped alphanumeric +% character into a marker indicating that this was a special sequence, +% and replace escaped special characters and non-escaped alphanumeric +% characters by markers indicating that those were \enquote{raw} +% characters. The rest of the code can then avoid caring about escaping +% issues (those can become quite complex to handle in combination with +% ranges in character classes). +% +% Usage: \cs{regex_escape_use:nnnn} \meta{inline~1} \meta{inline~2} +% \meta{inline~3} \Arg{token list} The \meta{token list} is converted to +% a string, then read from left to right, interpreting backslashes as +% escaping the next character. Unescaped characters are fed to the +% function \meta{fn1}, and escaped characters are fed to the function +% \meta{fn2} within an \texttt{x}-expansion context (typically those +% functions perform some tests on their argument to decide how to output +% them). The escape sequences |\a|, |\e|, |\f|, |\n|, |\r|, |\t| and +% |\x| are recognized, and those are replaced by the corresponding +% character, then fed to \meta{fn3}. The result is then left in the +% input stream. +% +% The idea is to feed unescaped characters to one function, +% escaped characters to another, and feed |\a|, |\e|, |\f|, +% |\n|, |\r|, |\t| and |\x| converted to the appropriate +% character to a third function. Spaces are ignored unless +% escaped. +% +% \begin{macro}[int]{\regex_escape_use:nnnn} +% \begin{macro}[aux]{\regex_escape_loop:N} +% \begin{macro}[aux]+\regex_escape_\:w+ +% Go through |#4| once, applying |#1|, |#2|, or |#3| to each character +% (after de-escaping it), then leave the result in the input +% stream. Most of the work is done within an \texttt{x}-expanding +% assignment, but the |\x| escape sequence cannot be done in that +% way. Therefore, we interrupt the assignment at each |\x| escape +% sequence, store the partial result in a \tn{toks} register, and at +% the end unpack all of the \tn{toks} registers to the left of the +% last chunk of \cs{l_regex_internal_a_tl}. +% \begin{macrocode} +\cs_new_protected:Npn \regex_escape_use:nnnn #1#2#3#4 { - \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 + \group_begin: + \cs_set_nopar:Npn \regex_escape_unescaped:N ##1 { #1 } + \cs_set_nopar:Npn \regex_escape_escaped:N ##1 { #2 } + \cs_set_nopar:Npn \regex_escape_raw:N ##1 { #3 } + \int_set:Nn \tex_escapechar:D { 92 } + \str_gset_other:Nn \g_regex_internal_tl {#4} + \int_zero:N \l_regex_internal_a_int + \tl_set:Nx \l_regex_internal_a_tl + { + \exp_after:wN \regex_escape_loop:N \g_regex_internal_tl + { break } \prg_break_point:n { } + } + \use:x + { + \group_end: + \regex_toks_range:nn \c_zero \l_regex_internal_a_int + \exp_not:o \l_regex_internal_a_tl + } } -\cs_new:Npn \regex_get_digits_aux:NN #1#2 +\cs_new:Npn \regex_escape_loop:N #1 { - \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_if_exist_use:cF { regex_escape_\token_to_str:N #1:w } + { \regex_escape_unescaped:N #1 } + \regex_escape_loop:N } -\cs_new:Npn \regex_get_digits_end:w #1 \fi: #2 \regex_get_digits_aux:NN +\cs_new_nopar:cpn { regex_escape_ \c_backslash_str :w } + \regex_escape_loop:N #1 { - \fi: #2 - \if_false: { { \fi: } } - #1 + \cs_if_exist_use:cF { regex_escape_/\token_to_str:N #1:w } + { \regex_escape_escaped:N #1 } + \regex_escape_loop:N } % \end{macrocode} % \end{macro} % \end{macro} +% \end{macro} % -% \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{macro}[aux]{\regex_escape_unescaped:N} +% \begin{macro}[aux]{\regex_escape_escaped:N} +% \begin{macro}[aux]{\regex_escape_raw:N} +% Those functions are never called before being given a new meaning, +% so their definitions here don't matter. % \begin{macrocode} -\prg_new_conditional:Npnn \regex_token_if_other_digit:N #1 { TF } +\cs_new_eq:NN \regex_escape_unescaped:N ? +\cs_new_eq:NN \regex_escape_escaped:N ? +\cs_new_eq:NN \regex_escape_raw:N ? +% \end{macrocode} +% \end{macro} +% \end{macro} +% \end{macro} +% +% \begin{macro}[aux]+\regex_escape_\q_recursion_tail:w+ +% \begin{macro}[aux]+\regex_escape_/\q_recursion_tail:w+ +% \begin{macro}[aux]+\regex_escape_ :w+ +% \begin{macro}[aux] +% { +% \regex_escape_/a:w, \regex_escape_/e:w, \regex_escape_/f:w, +% \regex_escape_/n:w, \regex_escape_/r:w, \regex_escape_/t:w +% } +% The loop is ended upon seeing \cs{q_recursion_tail}. +% Spaces are ignored, and |\a|, |\e|, |\f|, |\n|, |\r|, |\t| take +% their meaning here. +% \begin{macrocode} +\cs_new_eq:NN \regex_escape_break:w \prg_map_break: +\cs_new_nopar:cpn { regex_escape_/break:w } + { + \if_false: { \fi: } + \msg_kernel_error:nn { regex } { trailing-backslash } + \exp_after:wN \use_none:n \exp_after:wN { \if_false: } \fi: + } +\cs_new_nopar:cpn { regex_escape_~:w } { } +\cs_new_nopar:cpx { regex_escape_/a:w } + { \exp_not:N \regex_escape_raw:N \iow_char:N \^^G } +\cs_new_nopar:cpx { regex_escape_/t:w } + { \exp_not:N \regex_escape_raw:N \iow_char:N \^^I } +\cs_new_nopar:cpx { regex_escape_/n:w } + { \exp_not:N \regex_escape_raw:N \iow_char:N \^^J } +\cs_new_nopar:cpx { regex_escape_/f:w } + { \exp_not:N \regex_escape_raw:N \iow_char:N \^^L } +\cs_new_nopar:cpx { regex_escape_/r:w } + { \exp_not:N \regex_escape_raw:N \iow_char:N \^^M } +\cs_new_nopar:cpx { regex_escape_/e:w } + { \exp_not:N \regex_escape_raw:N \iow_char:N \^^[ } +% \end{macrocode} +% \end{macro} +% \end{macro} +% \end{macro} +% \end{macro} +% +% \begin{macro}[aux]{\regex_escape_/x:w} +% \begin{macro}[aux]{\regex_escape_x_test:N} +% \begin{macro}[aux]{\regex_escape_x_unbraced_i:N} +% \begin{macro}[aux]{\regex_escape_x_unbraced_ii:N} +% \begin{macro}[aux]{\regex_escape_x_braced_loop:N} +% \begin{macro}[aux]{\regex_escape_x_braced_end:N} +% \begin{macro}[aux]{\regex_escape_x_end:} +% When |\x| is encountered, interrupt the assignment, +% and distinguish the cases of a braced or unbraced syntax. +% In the braced case, collect arbitrarily many hexadecimal digits, +% building the number in \cs{l_regex_current_char_int} (using +% \cs{str_aux_hexadecimal_use:NTF}), and check that +% the run of digits was stopped by a closing brace. +% In the unbraced case, collect up to two hexadecimal digits, +% possibly less, building the character number in \cs{l_regex_current_char_int}. +% In both cases, once all digits have been collected, use +% the \TeX{} primitive \tn{lowercase} to produce that character, +% and use an \cs{if_false:} trick to restart the assignment. +% \begin{macrocode} +\cs_new_nopar:cpn { regex_escape_/x:w } \regex_escape_loop:N + { + \if_false: { \fi: } + \tex_toks:D \l_regex_internal_a_int + \exp_after:wN { \l_regex_internal_a_tl } + \int_incr:N \l_regex_internal_a_int + \int_zero:N \l_regex_current_char_int + \regex_escape_x_test:N + } +\cs_new_protected:Npx \regex_escape_x_test:N #1 + { + \exp_not:N \token_if_eq_charcode:NNTF \c_space_token #1 + { \exp_not:N \regex_escape_x_test:N } + { + \l_regex_current_char_int = "0 + \exp_not:N \token_if_eq_charcode:NNTF \c_lbrace_str #1 + { \exp_not:N \regex_escape_x_braced_loop:N } + { \exp_not:N \regex_escape_x_unbraced_i:N #1 } + } + } +\cs_new:Npn \regex_escape_x_unbraced_i:N #1 { - \if_num:w \c_nine < 1 \exp_not:N #1 \exp_stop_f: - \prg_return_true: \else: \prg_return_false: \fi: + \str_aux_hexadecimal_use:NTF #1 + { \regex_escape_x_unbraced_ii:N } + { \exp_stop_f: \regex_escape_x_end: #1 } } +\cs_new:Npn \regex_escape_x_unbraced_ii:N #1 + { + \token_if_eq_charcode:NNTF \c_space_token #1 + { \regex_escape_x_unbraced_ii:N } + { + \str_aux_hexadecimal_use:NTF #1 + { \exp_stop_f: \regex_escape_x_end: } + { \exp_stop_f: \regex_escape_x_end: #1 } + } + } +\cs_new:Npn \regex_escape_x_braced_loop:N #1 + { + \token_if_eq_charcode:NNTF \c_space_token #1 + { \regex_escape_x_braced_loop:N } + { + \str_aux_hexadecimal_use:NTF #1 + { \regex_escape_x_braced_loop:N } + { \exp_stop_f: \regex_escape_x_braced_end:N #1 } + } + } +\cs_new_protected:Npx \regex_escape_x_braced_end:N #1 + { + \exp_not:N \token_if_eq_charcode:NNTF \c_rbrace_str #1 + { \exp_not:N \regex_escape_x_end: } + { + \msg_kernel_error:nnx { regex } { x-missing-rbrace } + { \int_use:N \l_regex_current_char_int } + \exp_not:N \regex_escape_x_end: #1 + } + } +\group_begin: + \char_set_catcode_other:N \^^@ + \cs_new_protected_nopar:Npn \regex_escape_x_end: + { + \if_num:w \l_regex_current_char_int > \c_max_char_int + \msg_kernel_error:nnx { regex } { x-overflow } + { \int_use:N \l_regex_current_char_int } + \exp_after:wN \use:n + \else: + \tex_lccode:D \c_zero \l_regex_current_char_int + \exp_after:wN \tl_to_lowercase:n + \fi: + { + \tl_set:Nx \l_regex_internal_a_tl + { \if_false: } \fi: + \regex_escape_raw:N ^^@ + \regex_escape_loop:N + } + } +\group_end: % \end{macrocode} % \end{macro} +% \end{macro} +% \end{macro} +% \end{macro} +% \end{macro} +% \end{macro} +% \end{macro} % -% \begin{macro}[EXP,aux]{\regex_aux_char_if_alphanumeric:NTF} -% \begin{macro}[EXP,aux]{\regex_aux_char_if_special:NTF} +% \begin{macro}[EXP,aux]{\regex_char_if_alphanumeric:NTF} +% \begin{macro}[EXP,aux]{\regex_char_if_special:NTF} % These two tests are used in the first pass when parsing a % regular expression. That pass is responsible for finding % escaped and non-escaped characters, and recognizing which @@ -1564,7 +1879,7 @@ % 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 } +\prg_new_conditional:Npnn \regex_char_if_special:N #1 { TF } { \if_num:w `#1 < \c_ninety_one \if_num:w `#1 < \c_fifty_eight @@ -1586,7 +1901,7 @@ \fi: \fi: } -\prg_new_conditional:Npnn \regex_aux_char_if_alphanumeric:N #1 { TF } +\prg_new_conditional:Npnn \regex_char_if_alphanumeric:N #1 { TF } { \if_num:w `#1 < \c_ninety_one \if_num:w `#1 < \c_fifty_eight @@ -1617,41 +1932,41 @@ % When building the NFA corresponding to a given regex, we can be in % ten distinct modes, which we label by some magic numbers: % \begin{itemize} -% \item[-6] |[\c{...}]| control sequence in a class, -% \item[-2] |\c{...}| control sequence, -% \item[0] |...| outer, -% \item[2] |\c...| catcode test, -% \item[6] |[\c...]| catcode test in a class, -% \item[-63] |[\c{[...]}]| class inside mode $-6$, -% \item[-23] |\c{[...]}| class inside mode $-2$, -% \item[3] |[...]| class inside mode $-3$, -% \item[23] |\c[...]| class inside mode $2$, -% \item[63] |[\c[...]]| class inside mode $6$. +% \item[-6] |[\c{...}]| control sequence in a class, +% \item[-2] |\c{...}| control sequence, +% \item[0] |...| outer, +% \item[2] |\c...| catcode test, +% \item[6] |[\c...]| catcode test in a class, +% \item[-63] |[\c{[...]}]| class inside mode $-6$, +% \item[-23] |\c{[...]}| class inside mode $-2$, +% \item[3] |[...]| class inside mode $-3$, +% \item[23] |\c[...]| class inside mode $2$, +% \item[63] |[\c[...]]| class inside mode $6$. % \end{itemize} % This list is exhaustive, because |\c| escape sequences cannot be % nested, and character classes cannot be nested directly. The choice % of numbers is such as to optimize the most useful tests, and make % transitions from one mode to another as simple as possible. % \begin{itemize} -% \item Even modes mean that we are not directly in a character class. -% In this case, a left bracket appends $3$ to the mode. In a character -% class, a right bracket changes the mode as $m\to (m-15)/13$, -% truncated. -% \item Grouping, assertion, and anchors are allowed in non-positive -% even modes ($0$, $-2$, $-6$), and do not change the mode. Otherwise, -% they trigger an error. -% \item A left bracket is special in even modes, appending $3$ to the -% mode; in those modes, quantifiers and the dot are recognized, and -% the right bracket is normal. In odd modes (within classes), the left -% bracket is normal, but the right bracket ends the class, changing -% the mode from $m$ to $(m-15)/13$, truncated; also, ranges are -% recognized. -% \item In non-negative modes, left and right braces are normal. In -% negative modes, however, left braces trigger a warning; right braces -% end the control sequence, going from $-2$ to $0$ or $-6$ to $3$, -% with error recovery for odd modes. -% \item Properties (such as the |\d| character class) can appear in any -% mode. +% \item Even modes mean that we are not directly in a character class. +% In this case, a left bracket appends $3$ to the mode. In a +% character class, a right bracket changes the mode as $m\to +% (m-15)/13$, truncated. +% \item Grouping, assertion, and anchors are allowed in non-positive +% even modes ($0$, $-2$, $-6$), and do not change the +% mode. Otherwise, they trigger an error. +% \item A left bracket is special in even modes, appending $3$ to the +% mode; in those modes, quantifiers and the dot are recognized, and +% the right bracket is normal. In odd modes (within classes), the +% left bracket is normal, but the right bracket ends the class, +% changing the mode from $m$ to $(m-15)/13$, truncated; also, ranges +% are recognized. +% \item In non-negative modes, left and right braces are normal. In +% negative modes, however, left braces trigger a warning; right +% braces end the control sequence, going from $-2$ to $0$ or $-6$ to +% $3$, with error recovery for odd modes. +% \item Properties (such as the |\d| character class) can appear in +% any mode. % \end{itemize} % % \begin{macro}[int, EXP]{\regex_build_if_in_class:TF} @@ -1671,13 +1986,32 @@ % \end{macrocode} % \end{macro} % +% \begin{macro}{\regex_build_if_assertions_forbidden:TF} +% Assertions are only allowed in modes $0$, $-2$, and $-6$, +% \emph{i.e.}, even, non-positive modes. +% \begin{macrocode} +\cs_new_nopar:Npn \regex_build_if_assertions_forbidden:TF + { + \if_int_odd:w \l_regex_build_mode_int + \exp_after:wN \use_i:nn + \else: + \if_int_compare:w \l_regex_build_mode_int > \c_zero + \exp_after:wN \exp_after:wN \exp_after:wN \use_i:nn + \else: + \exp_after:wN \exp_after:wN \exp_after:wN \use_ii:nn + \fi: + \fi: + } +% \end{macrocode} +% \end{macro} +% % \subsubsection{Helpers for building an NFA} % % \begin{macro}[int]{\regex_build_new_state:} -% 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_stop}, hence initialize the new register appropriately. -% Then set \cs{l_regex_left/right_state_int} to their new values. +% Add a new state to the NFA. At the end of the building phase, we +% want every \tn{toks} register to start with \cs{s_stop}, hence +% initialize the new register appropriately. Then update +% the left, right, and max \meta{states}. % \begin{macrocode} \cs_new_protected_nopar:Npn \regex_build_new_state: { @@ -1715,84 +2049,125 @@ % % \subsubsection{From regex to NFA: framework} % -%^^A In order for the construction \verb"ab|cd" to work, we enclose the -%^^A whole pattern within parentheses (in the code below, -%^^A \cs{regex_build_open_aux:} and \cs{regex_build_close_aux:}). These -%^^A have the added benefit to form a capturing group: hence we get the -%^^A 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 search is not anchored: to achieve that, we insert state(s) -% responsible for repeating the match attempt on every token -% in the token list. -% 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{macro}[int]{\regex_build:w, \regex_build_end:} +% \begin{macro}[int]{\regex_build_exit_class:, \regex_build_exit_groups:} +% There are two situations where we want to convert a regular +% expression given as a string to an NFA. The first case is when the +% regex is given directly by the user, as an \texttt{n} argument to +% one of the \pkg{l3regex} functions, and the second case is when +% building the regex given as an argument of the |\c{...}| escape +% sequence within another regular expression. In both cases, some +% variables must be reset before starting to build the NFA, using +% \cs{regex_build:w}. Once building has ended (for instance when +% encountering the closing brace in |\c{...}|), we make sure to close +% any dangling class or open group, then add +% \cs{regex_action_success:} to make the match successful if it +% reaches the last state. The capturing group number is incremented: +% then its value tells us how many capturing group there are, +% including $0$. % \begin{macrocode} -\cs_new_protected:Npn \regex_build:n #1 +\cs_new_protected_nopar:Npn \regex_build:w { - \int_set_eq:NN \l_regex_build_mode_int \c_zero - \regex_build:w + \int_set_eq:NN \l_regex_catcodes_default_int \c_regex_catcodes_all_int + \int_set_eq:NN \l_regex_catcodes_int \l_regex_catcodes_default_int + \int_set_eq:NN \l_regex_capturing_group_int \c_zero + \tl_clear:N \l_regex_tests_tl + \bool_set_true:N \l_regex_tests_bool + \int_zero:N \l_regex_max_state_int \regex_build_new_state: - \regex_toks_put_right:Nx \l_regex_left_state_int - { \regex_action_start_wildcard: } - \regex_build_open_aux: - \str_escape_use:NNNn - \regex_build_i_unescaped:N - \regex_build_i_escaped:N - \regex_build_i_raw:N - { #1 } - \prg_do_nothing: \prg_do_nothing: - \prg_do_nothing: \prg_do_nothing: - \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_escape_use: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:Npn \regex_build_i_unescaped:N #1 +\cs_new_protected_nopar:Npn \regex_build_end: { - \regex_aux_char_if_special:NTF #1 - { \exp_not:N \regex_build_special:N #1 } - { \exp_not:N \regex_build_raw:N #1 } + \regex_build_exit_class: + \regex_build_exit_groups: + \regex_toks_put_right:Nx \l_regex_right_state_int + { \regex_action_success: } + \int_incr:N \l_regex_capturing_group_int } -\cs_new:Npn \regex_build_i_escaped:N #1 +\cs_new_protected_nopar:Npn \regex_build_exit_class: { - \regex_aux_char_if_alphanumeric:NTF #1 - { \exp_not:N \regex_build_escaped:N #1 } - { \exp_not:N \regex_build_raw:N #1 } + \regex_build_if_in_class:TF + { + \msg_kernel_error:nn { regex } { missing-rbrack } + \use:c { regex_build_]: } + } + { } + } +\cs_new_protected_nopar:Npn \regex_build_exit_groups: + { + \seq_if_empty:NF \l_regex_capturing_group_seq + { + \msg_kernel_error:nnx { regex } { missing-rparen } + { \seq_length:N \l_regex_capturing_group_seq } + \prg_replicate:nn + { \seq_length:N \l_regex_capturing_group_seq } + { \regex_build_close_aux: \regex_build_group_: } + } } -\cs_new:Npn \regex_build_i_raw:N #1 - { \exp_not:N \regex_build_raw:N #1 } % \end{macrocode} % \end{macro} % \end{macro} +% +% \begin{macro}[int]{\regex_build:n} +% Setup some variables with \cs{regex_build:w}, and additionally set +% the build mode to $0$: we are neither in a class nor a |\c| +% construction. Initiate the regular expression by a wildcard: the +% search is unanchored and should be tried at every index in the token +% list. We surround the regular expression by parentheses with +% \cs{regex_build_open_aux:} and \cs{regex_build_close_aux:}, so that +% any alternative appears within a group (\emph{e.g.}, \verb"ab|cd" +% will now be within the external group); this also forms a capturing +% group (labelled $0$), which gives us the whole match as the $0$-th +% submatch. The regular expression itself is parsed by using the +% generic framework of \cs{regex_escape_use:nnnn} to recognize special +% characters, escaped ones, and escape sequences such as |\n| or +% |\x{02f}|. This results in successive \cs{regex_build_raw:N}, +% \cs{regex_build_escaped:N}, \cs{regex_build_special:N} followed by +% their arguments. The trailing \cs{prg_do_nothing:} ensure that the +% look-ahead done by some of the operations is harmless. Finally, +% \cs{regex_build_end:} adds the finishing code (checking that +% parentheses are properly nested, for instance). +% \begin{macrocode} +\cs_new_protected:Npn \regex_build:n #1 + { + \regex_build:w + \int_set_eq:NN \l_regex_build_mode_int \c_zero + \regex_build_new_state: + \regex_toks_put_right:Nx \l_regex_left_state_int + { \regex_action_start_wildcard: } + \regex_build_open_aux: + \regex_escape_use:nnnn + { + \regex_char_if_special:NTF ##1 + \regex_build_special:N \regex_build_raw:N ##1 + } + { + \regex_char_if_alphanumeric:NTF ##1 + \regex_build_escaped:N \regex_build_raw:N ##1 + } + { \regex_build_raw:N ##1 } + { #1 } + \prg_do_nothing: \prg_do_nothing: + \prg_do_nothing: \prg_do_nothing: + \int_compare:nNnT \l_regex_build_mode_int < \c_zero + { + \msg_kernel_error:nn { regex } { c-missing-rbrace } + \exp_after:wN \regex_build_special:N \c_rbrace_str + } + \seq_put_right:Nn \l_regex_capturing_group_seq {0} + \regex_build_close_aux: \regex_build_group_: + \regex_build_end: + } +% \end{macrocode} % \end{macro} % % \begin{macro}[aux]{\regex_build_special:N} % \begin{macro}[aux]{\regex_build_escaped:N} -% If the control character has a particular meaning in regexes, the -% corresponding function is used. Otherwise, it is interpreted as a -% raw character. We distinguish special characters from escaped -% alphanumeric characters because in character classes, unknown -% escaped alphanumeric characters raise an error, while special -% charcters are silently converted to raw characters. +% If the special character or escaped alphanumeric has a particular +% meaning in regexes, the corresponding function is used. Otherwise, +% it is interpreted as a raw character. We distinguish special +% characters from escaped alphanumeric characters because they behave +% differently when appearing as an end-point of a range. % \begin{macrocode} \cs_new_protected:Npn \regex_build_special:N #1 { @@ -1808,64 +2183,24 @@ % \end{macro} % \end{macro} % -% \begin{macro}[int]{\regex_build:w} -% Hopefully, we didn't forget to initialize anything here. -% \begin{macrocode} -\cs_new_protected_nopar:Npn \regex_build:w - { - \int_set_eq:NN \l_regex_catcodes_default_int \c_regex_catcodes_all_int - \int_set_eq:NN \l_regex_capturing_group_int \c_zero - \int_zero:N \l_regex_max_state_int - \regex_build_new_state: - \tl_clear:N \l_regex_class_tl - \bool_set_true:N \l_regex_class_bool - \int_set_eq:NN \l_regex_catcodes_int \l_regex_catcodes_default_int - } -% \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: - { - \regex_seq_push_int:NN \l_regex_capturing_group_seq \c_zero - \regex_build_close_aux: \regex_build_group_: - \seq_if_empty:NF \l_regex_capturing_group_seq - { - \msg_kernel_error:nnx { regex } { missing-rparen } - { \seq_length:N \l_regex_capturing_group_seq } - \prg_replicate:nn - { \seq_length:N \l_regex_capturing_group_seq } - { \regex_build_close_aux: \regex_build_group_: } - } - \regex_toks_put_right:Nx \l_regex_right_state_int - { \regex_action_success: } - \int_incr:N \l_regex_capturing_group_int - } -% \end{macrocode} -% \end{macro} -% % \begin{macro}[int]{\regex_build_one:n, \regex_build_one:x} % In a class, add the argument to the current class. Outside a class, -% this argument is the whole \enquote{class}, and we look for -% quantifiers. +% this argument is the only test, and we look for quantifiers. % \begin{macrocode} \cs_new_protected:Npn \regex_build_one:n #1 { \regex_build_one:x { \exp_not:n {#1} } } \cs_new_protected:Npn \regex_build_one:x #1 { - \tl_put_right:Nx \l_regex_class_tl + \tl_put_right:Nx \l_regex_tests_tl { - \if_num:w \l_regex_catcodes_int = \c_regex_catcodes_all_int - \exp_after:wN \use:n - \else: + \if_num:w \l_regex_catcodes_int < \c_regex_catcodes_all_int \regex_item_catcode:nT { \int_use:N \l_regex_catcodes_int } + \else: + \exp_after:wN \use:n \fi: {#1} } + \int_set_eq:NN \l_regex_catcodes_int \l_regex_catcodes_default_int \if_num:w \l_regex_build_mode_int = \c_two \l_regex_build_mode_int = \c_zero \else: @@ -1880,51 +2215,34 @@ % \end{macrocode} % \end{macro} % -% \begin{macro}{\regex_build_tmp_class:n} -% ^^A todo: rename, not tmp, and used for class & single. +% \begin{macro}{\regex_tests_action_cost:n} % The argument is the target state if the test succeeds. % \begin{macrocode} -\cs_new:Npn \regex_build_tmp_class:n #1 +\cs_new:Npn \regex_tests_action_cost:n #1 { - \exp_not:o \l_regex_class_tl - \bool_if:NTF \l_regex_class_bool + \exp_not:o \l_regex_tests_tl + \bool_if:NTF \l_regex_tests_bool { \regex_break_point:TF { \regex_action_cost:n {#1} } { } } { \regex_break_point:TF { } { \regex_action_cost:n {#1} } } } % \end{macrocode} % \end{macro} % -% \begin{macro}[int]{\regex_class_put:N} -% \begin{macro}[int]{\regex_class_put:NN} -% This function is used to rapidly put a character in a character -% class being built, avoiding some tests implied by \cs{regex_build_one:x}. -% \begin{macrocode} -\cs_new_protected:Npn \regex_class_put:N #1 - { - \tl_put_right:Nx \l_regex_class_tl - { \regex_item_equal:n { \int_value:w `#1 ~ } } - } -\cs_new_protected:Npn \regex_class_put:NN #1#2 - { - \tl_put_right:Nx \l_regex_class_tl - { \regex_item_range:nn { \int_value:w `#1 ~ } { \int_value:w `#2 ~ } } - } -% \end{macrocode} -% \end{macro} -% \end{macro} +% \subsubsection{Raw characters} % -% \begin{macro}[int]{\regex_build_raw_alphanum_is_error:N} -% Within character classes, some special character and escape -% sequences do not have any meaning. Special characters are -% interpreted as their \enquote{raw} counterpart, but escape sequences -% without a meaning, \emph{e.g.}, |\A|, are most likely an error: -% this should be |A|. +% \begin{macro}[int]{\regex_build_raw_error:N} +% Within character classes, some escaped alphanumeric sequences such +% as |\b| do not have any meaning. They are replaced by a raw +% character, after spitting out an error. % \begin{macrocode} -\cs_new_protected:Npn \regex_build_raw_alphanum_is_error:N #1 +\cs_new_protected:Npn \regex_build_raw_error:N #1 { - \regex_aux_char_if_alphanumeric:NTF #1 - { \msg_kernel_error:nnx { regex } { class-bad-escape } { #1 } } - { \regex_build_raw:N #1 } + \if_int_odd:w \l_regex_build_mode_int + \msg_kernel_error:nnx { regex } { class-bad-escape } {#1} + \else: + \msg_kernel_error:nnx { regex } { catcode-bad-escape } {#1} + \fi: + \regex_build_raw:N #1 } % \end{macrocode} % \end{macro} @@ -1961,21 +2279,28 @@ \token_if_eq_meaning:NNTF #2 \regex_build_escaped:N % [ { \use_i:nn } { \str_if_eq:nnTF { #2#3 } { \regex_build_special:N ] } } { - \msg_kernel_warning:nnx { regex } { end-range-missing } % [ - { #1 - \if_meaning:w #3 ] \else: \c_backslash_str \fi: #3 } - \regex_class_put:N #1 - \regex_class_put:N - + \msg_kernel_warning:nnxx { regex } { range-missing-end } % [ + {#1} { \token_if_eq_charcode:NNF #3 ] { \c_backslash_str } #3 } + \tl_put_right:Nx \l_regex_tests_tl + { + \regex_item_equal:n { \int_value:w `#1 ~ } + \regex_item_equal:n { \int_value:w `- ~ } + } #2#3 } { \if_num:w `#1 > `#3 \exp_stop_f: - \msg_kernel_error:nnxx { regex } { backwards-range } {#1} {#3} + \msg_kernel_error:nnxx { regex } { range-backwards } {#1} {#3} \else: - \if_num:w `#1 = `#3 \exp_stop_f: - \regex_class_put:N #3 - \else: - \regex_class_put:NN #1#3 - \fi: + \tl_put_right:Nx \l_regex_tests_tl + { + \if_num:w `#1 = `#3 \exp_stop_f: + \regex_item_equal:n + \else: + \regex_item_range:nn { \int_value:w `#1 ~ } + \fi: + { \int_value:w `#3 ~ } + } \fi: } } @@ -1986,14 +2311,14 @@ % % \begin{macro}[aux]{\regex_build_.:} % In a class, the dot has no special meaning. Outside, insert -% \cs{regex_item_dot:}, which matches any character or control +% \cs{c_regex_._tl}, which matches any character or control % sequence, and refuses $-2$, which marks the end of the token list. % \begin{macrocode} -\cs_new_protected_nopar:cpn { regex_build_.: } +\cs_new_protected_nopar:cpx { regex_build_.: } { - \regex_build_if_in_class:TF + \exp_not:N \regex_build_if_in_class:TF { \regex_build_raw:N . } - { \regex_build_one:x \regex_item_dot: } + { \regex_build_one:n \exp_not:c { c_regex_._tl } } } % \end{macrocode} % \end{macro} @@ -2024,16 +2349,18 @@ % % \subsubsection{Anchoring and simple assertions} % -% \begin{macro}[aux]{\regex_build_simple_assertion:Nn} -% Assertions are not allowed within character classes: the raw -% character |#1| is inserted instead. Otherwise, use the test |#2|; -% if the assertion is successful, move from the \texttt{left} state to -% the \texttt{right} state. +% \begin{macro}[aux]{\regex_build_simple_assertion:nn} +% Assertions are only allowed in modes $0$, $-2$ and $-6$. In +% character classes, or immediately following a category code test, +% escaped letters cause errors, while the meaning of special +% characters is ignored: |#1| is used instead. In modes where the +% assertion is allowed, we insert the test |#2|; if the assertion is +% successful, move from the \texttt{left} state to the \texttt{right} +% state. % \begin{macrocode} -\cs_new_protected:Npn \regex_build_simple_assertion:Nn #1#2 +\cs_new_protected:Npn \regex_build_simple_assertion:nn #1#2 { - \regex_build_if_in_class:TF - { \regex_build_raw_alphanum_is_error:N #1 } + \regex_build_if_assertions_forbidden:TF {#1} { \regex_build_new_state: \regex_toks_put_right:Nx \l_regex_left_state_int @@ -2047,7 +2374,7 @@ } } } - %^^A \regex_assertion_quantifier: + %^^A todo: add \regex_assertion_quantifier: } } % \end{macrocode} @@ -2061,38 +2388,41 @@ % \begin{macro}[aux]{\regex_build_/z:} % Anchoring at the start corresponds to checking that the current % character is the first in the token list. Anchoring to the beginning -% of the match attempt uses \cs{l_regex_start_step_int} instead of +% of the match attempt uses \cs{l_regex_start_index_int} instead of % \cs{c_zero}. End anchors match the end of the token list, marked by % a character code of $-2$. % \begin{macrocode} \cs_new_protected_nopar:cpn { regex_build_^: } { - \regex_build_simple_assertion:Nn ^ - { \int_compare:nNnT \l_regex_min_step_int = \l_regex_current_step_int } + \regex_build_simple_assertion:nn { \regex_build_raw:N ^ } + { \int_compare:nNnT \l_regex_min_index_int = \l_regex_current_index_int } } \cs_new_protected_nopar:cpn { regex_build_/A: } { - \regex_build_simple_assertion:Nn A - { \int_compare:nNnT \l_regex_min_step_int = \l_regex_current_step_int } + \regex_build_simple_assertion:nn { \regex_build_raw_error:N A } + { \int_compare:nNnT \l_regex_min_index_int = \l_regex_current_index_int } } \cs_new_protected_nopar:cpn { regex_build_/G: } { - \regex_build_simple_assertion:Nn G - { \int_compare:nNnT \l_regex_start_step_int = \l_regex_current_step_int } - } -\cs_new_protected_nopar:cpn { regex_build_$: } % $ - { - \regex_build_simple_assertion:Nn $ % $ - { \int_compare:nNnT \l_regex_current_char_int < \c_minus_one } + \regex_build_simple_assertion:nn { \regex_build_raw_error:N G } + { \int_compare:nNnT \l_regex_start_index_int = \l_regex_current_index_int } } +\group_begin: + \char_set_catcode_other:N \$ + \cs_new_protected_nopar:cpn { regex_build_$: } % $ + { + \regex_build_simple_assertion:nn { \regex_build_raw:N $ } % $ + { \int_compare:nNnT \l_regex_current_char_int < \c_minus_one } + } +\group_end: \cs_new_protected_nopar:cpn { regex_build_/Z: } { - \regex_build_simple_assertion:Nn Z + \regex_build_simple_assertion:nn { \regex_build_raw_error:N Z } { \int_compare:nNnT \l_regex_current_char_int < \c_minus_one } } \cs_new_protected_nopar:cpn { regex_build_/z: } { - \regex_build_simple_assertion:Nn z + \regex_build_simple_assertion:nn { \regex_build_raw_error:N z } { \int_compare:nNnT \l_regex_current_char_int < \c_minus_one } } % \end{macrocode} @@ -2113,12 +2443,12 @@ % \begin{macrocode} \cs_new_protected_nopar:cpn { regex_build_/b: } { - \regex_build_simple_assertion:Nn b - { \regex_if_word_boundary:TF \use:n \use_none:n } + \regex_build_simple_assertion:nn { \regex_build_raw_error:N b } + { \regex_if_word_boundary:T } } \cs_new_protected_nopar:cpn { regex_build_/B: } { - \regex_build_simple_assertion:Nn B + \regex_build_simple_assertion:nn { \regex_build_raw_error:N B } { \regex_if_word_boundary:TF { } } } \cs_new_protected_nopar:Npn \regex_if_word_boundary:TF @@ -2131,6 +2461,8 @@ { \group_end: \c_regex_w_tl } \regex_break_point:TF } +\cs_new_protected_nopar:Npn \regex_if_word_boundary:T + { \regex_if_word_boundary:TF \use:n \use_none:n } % \end{macrocode} % \end{macro} % \end{macro} @@ -2156,7 +2488,7 @@ % the mode ($m\to (m-15)/13$, truncated) to reflect the fact that we % are leaving the class. If we are still in a class after leaving one, % then this is the case |[...\cL[...]...]|, and we insert the relevant -% closing material in \cs{l_regex_class_tl}. Otherwise look for +% closing material in \cs{l_regex_tests_tl}. Otherwise look for % quantifiers. % \begin{macrocode} \cs_new_protected:cpn { regex_build_]: } @@ -2164,21 +2496,22 @@ \regex_build_if_in_class:TF { \if_num:w \l_regex_build_mode_int > \c_sixteen - \tl_set:Nx \l_regex_class_tl + \tl_set:Nx \l_regex_tests_tl { - \exp_not:o \l_regex_class_saved_tl - \if_num:w \l_regex_catcodes_int < \c_regex_catcodes_all_int - \regex_item_catcode:nT { \int_use:N \l_regex_catcodes_int } + \exp_not:o \l_regex_tests_saved_tl + \if_num:w \l_regex_catcodes_saved_int < \c_regex_catcodes_all_int + \regex_item_catcode:nT + { \int_use:N \l_regex_catcodes_saved_int } \else: \exp_after:wN \use:n \fi: { - \exp_not:o \l_regex_class_tl - \bool_if:NF \l_regex_class_bool - { \regex_break_point:TF { } { \regex_break_true:w } } + \exp_not:o \l_regex_tests_tl + \bool_if:NF \l_regex_tests_bool + { \regex_break_point:TF { } \regex_break_true:w } } } - \bool_set_eq:NN \l_regex_class_bool \l_regex_class_saved_bool + \bool_set_eq:NN \l_regex_tests_bool \l_regex_tests_saved_bool \fi: \tex_advance:D \l_regex_build_mode_int - \c_fifteen \tex_divide:D \l_regex_build_mode_int \c_thirteen @@ -2191,17 +2524,15 @@ % \end{macrocode} % \end{macro} % -%^^A todo: ignore spaces everywhere!! -% % \begin{macro}[aux]{\regex_class_first:NNNN} % This starts a class. Change the mode by appending $3$ to it, and -% reset the variables \cs{l_regex_class_tl} and +% reset the variables \cs{l_regex_tests_tl} and % \cs{l_regex_bool_tl}. In the special case of mode $63$ % (|[\c[...]]|), we open a group, to avoid overriding the setting of -% \cs{l_regex_class_bool} and \cs{l_regex_class_tl}; the group ends at +% \cs{l_regex_tests_bool} and \cs{l_regex_tests_tl}; the group ends at % the matching right bracket. If the first character is |^|, then the % class is inverted. We keep track of this in -% \cs{l_regex_class_bool}. If the next character is a right bracket, +% \cs{l_regex_tests_bool}. If the next character is a right bracket, % then it should be changed to a raw one (dirty hack here; the |F| % argument of \cs{str_if_eq:nnTF} is the trailing |#3|). % \begin{macrocode} @@ -2209,14 +2540,16 @@ { \l_regex_build_mode_int = \int_value:w \l_regex_build_mode_int 3 ~ % \if_num:w \l_regex_build_mode_int > \c_sixteen - \tl_set_eq:NN \l_regex_class_saved_tl \l_regex_class_tl - \bool_set_eq:NN \l_regex_class_saved_bool \l_regex_class_bool + \tl_set_eq:NN \l_regex_tests_saved_tl \l_regex_tests_tl + \bool_set_eq:NN \l_regex_tests_saved_bool \l_regex_tests_bool + \int_set_eq:NN \l_regex_catcodes_saved_int \l_regex_catcodes_int + \int_set_eq:NN \l_regex_catcodes_int \c_regex_catcodes_all_int \fi: \token_if_eq_meaning:NNTF #1 \regex_build_special:N { \token_if_eq_charcode:NNTF #2 ^ { - \bool_set_false:N \l_regex_class_bool % [ + \bool_set_false:N \l_regex_tests_bool % [ \str_if_eq:nnTF {#3#4} { \regex_build_special:N ] } { \regex_build_raw:N } } @@ -2269,8 +2602,7 @@ } { \cs_if_exist_use:cF { regex_build_c_#3: } } { - \msg_kernel_error:nnxx { regex } { c-command } - { regular~expression } { #3 } + \msg_kernel_error:nnx { regex } { c-missing-category } {#3} #2 #3 } } @@ -2292,11 +2624,12 @@ % \end{macrocode} % \end{macro} % -% \begin{macro}[aux]{\regex_build_c_[:} ^^A] +% \begin{macro}[aux]{\regex_build_c_[:} % \begin{macro}[aux]{\regex_build_c_lbrack_loop:NN} % \begin{macro}[aux]{\regex_build_c_lbrack_end:} % \begin{macro}[aux]{\regex_build_add:N} -% +% When encountering |\c[|, the task is to collect uppercase letters +% representing character categories. % \begin{macrocode} \cs_new_protected:cpn { regex_build_c_[: } #1#2 { @@ -2328,8 +2661,7 @@ { \regex_build_c_lbrack_end: } } { - \msg_kernel_error:nnxx { regex } { c-command } - { regular-expression } { #2 } + \msg_kernel_error:nnx { regex } { c-missing-rbrack } {#2} \regex_build_c_lbrack_end: } } @@ -2356,24 +2688,30 @@ % \end{macro} % % ^^A{ -% \begin{macro}+\regex_build}:+ -% Non-escaped right braces are only special if they appear -% when building the regular expression for a csname. Otherwise, +% \begin{macro}+\regex_build_}:+ +% Non-escaped right braces are only special if they appear when +% building the regular expression for a csname. In that case, make +% sure that any character class and group is closed, anchor the match +% at the end, add the code for making the match successful, and expand +% the contents of the regular expression we just built. Otherwise, % replace the brace with an escaped brace. % \begin{macrocode} \cs_new_protected:cpn { regex_build_ \c_rbrace_str : } - { %^^A incorrect recovery for \c{...(...[...} with missing ) or ]. + { \int_compare:nNnTF \l_regex_build_mode_int < \c_zero { - \use:c { regex_build_/Z: } - \regex_toks_put_right:Nx \l_regex_right_state_int - { \regex_action_success: } - \int_incr:N \l_regex_capturing_group_int + \regex_build_exit_class: + \regex_build_exit_groups: + \regex_build_escaped:N Z + \regex_build_end: \use:x { \group_end: \regex_build_one:n - { \regex_item_cs:n { \regex_set_aux:N ? } } + { + \regex_item_cs:n + { \regex_set_aux:N \l_regex_internal_regex } + } } } { \exp_after:wN \regex_build_raw:N \c_rbrace_str } @@ -2488,7 +2826,7 @@ \tl_if_empty:nTF {#2} { \regex_build_quantifier_aux:nnNN { {#1} } { n* } } { \regex_build_quantifier_aux:nnNN { {#1} {#2} } { nn } } - } %^^A todo: catch the case m>n + } { \regex_build_quantifier_end:nn { } { } \use:x @@ -2513,9 +2851,8 @@ \cs_new_protected:Npn \regex_build_quantifier_end:nn #1#2 { \use:c { regex_build_ \l_regex_one_or_group_tl _ #1 : } #2 - \tl_clear:N \l_regex_class_tl - \bool_set_true:N \l_regex_class_bool - \int_set_eq:NN \l_regex_catcodes_int \l_regex_catcodes_default_int + \tl_clear:N \l_regex_tests_tl + \bool_set_true:N \l_regex_tests_bool } % \end{macrocode} % \end{macro} @@ -2536,138 +2873,131 @@ % \end{macrocode} % \end{macro} % +% \begin{macro}[aux]{\regex_build_one_n:, \regex_build_one_n?:} % \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: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: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: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. +% This function is called in case the syntax is +% \texttt{\{\meta{int}\}}. Greedy and lazy operators are identical, +% since the number of repetitions is fixed. Build one state for each +% repetition, with a transition controlled by the tests that we have +% collected. The case where we find no quantifier is the special case +% $n=1$. % \begin{macrocode} -\cs_new_protected_nopar:cpn { regex_build_one_*: } - { - \regex_build_transitions: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_*?: } +\cs_new_protected:Npn \regex_build_one_n: #1 { - \regex_build_transitions:NNNN - \regex_action_free:n \l_regex_right_state_int - \regex_build_tmp_class:n \l_regex_left_state_int + \prg_replicate:nn {#1} + { + \regex_build_transition:NN + \regex_tests_action_cost:n \l_regex_right_state_int + } } +\cs_new_eq:cN { regex_build_one_n?: } \regex_build_one_n: +\cs_new_protected_nopar:Npn \regex_build_one_: + { \regex_build_one_n: \c_one } % \end{macrocode} % \end{macro} % \end{macro} % -% \begin{macro}[aux]{\regex_build_one_+:} -% \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{macro}[aux]{\regex_build_one_n*:, \regex_build_one_n*?:} +% \begin{macro}[aux]{\regex_build_one_*:, \regex_build_one_*?:} +% \begin{macro}[aux]{\regex_build_one_+:, \regex_build_one_+?:} +% Those functions are called in case the syntax is +% \texttt{\{\meta{int},\}}. The |*| and |+| quantifiers (greedy or +% lazy) are special cases for $n=0$ or $n=1$. In the case $n=0$, +% build a costly transition going from the current state to itself, +% and a free transition moving to a new state. In the case $n\geq 1$, +% reuse \cs{regex_build_one_n:} to match $n$ repetition, then add free +% transitions from the last state to the previous one, and from the +% last state to a new one. The greedy and lazy versions only differ in +% the order of transitions. % \begin{macrocode} -\cs_new_protected_nopar:cpn { regex_build_one_+: } +\cs_new_protected:cpn { regex_build_one_n*: } #1 { - \regex_build_one_: - \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int - \regex_build_transitions:NNNN - \regex_action_free:n \l_regex_tmpa_int - \regex_action_free:n \l_regex_right_state_int + \int_compare:nNnTF {#1} = \c_zero + { + \regex_build_transitions:NNNN + \regex_tests_action_cost:n \l_regex_left_state_int + \regex_action_free:n \l_regex_right_state_int + } + { + \regex_build_one_n: {#1} + \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int + \regex_build_transitions:NNNN + \regex_action_free:n \l_regex_internal_a_int + \regex_action_free:n \l_regex_right_state_int + } } -\cs_new_protected_nopar:cpn { regex_build_one_+?: } +\cs_new_protected:cpn { regex_build_one_n*?: } #1 { - \regex_build_one_: - \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int - \regex_build_transitions:NNNN - \regex_action_free:n \l_regex_right_state_int - \regex_action_free:n \l_regex_tmpa_int + \int_compare:nNnTF {#1} = \c_zero + { + \regex_build_transitions:NNNN + \regex_action_free:n \l_regex_right_state_int + \regex_tests_action_cost:n \l_regex_left_state_int + } + { + \regex_build_one_n: {#1} + \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int + \regex_build_transitions:NNNN + \regex_action_free:n \l_regex_right_state_int + \regex_action_free:n \l_regex_internal_a_int + } } +\cs_new_protected_nopar:cpx { regex_build_one_*: } + { \exp_not:c { regex_build_one_n*: } \c_zero } +\cs_new_protected_nopar:cpx { regex_build_one_*?: } + { \exp_not:c { regex_build_one_n*?: } \c_zero } +\cs_new_protected_nopar:cpx { regex_build_one_+: } + { \exp_not:c { regex_build_one_n*: } \c_one } +\cs_new_protected_nopar:cpx { regex_build_one_+?: } + { \exp_not:c { regex_build_one_n*?: } \c_one } % \end{macrocode} % \end{macro} % \end{macro} -% -% \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: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{macro}[aux]{\regex_build_one_nn:, \regex_build_one_nn?:} +% \begin{macro}[aux]{\regex_build_one_?:, \regex_build_one_??:} +% \begin{macro}[aux]{\regex_build_one_nn_aux:nnnn} +% Those functions are called when the syntax is +% \texttt{\{\meta{int},\meta{int}\}}, or for the |?| quantifier, with +% $m=0$ and $n=1$. % \begin{macrocode} -\cs_new_protected:cpx { regex_build_one_n*: } #1 +\cs_new_protected_nopar:Npn \regex_build_one_nn: { - \exp_not:N \prg_replicate:nn {#1} { \exp_not:N \regex_build_one_: } - \exp_not:c { regex_build_one_*: } + \regex_build_one_nn_aux:nnnn { } + { + \regex_build_transitions:NNNN + \regex_tests_action_cost:n \l_regex_right_state_int + \regex_action_free:n \l_regex_internal_a_int + } } -\cs_new_protected:cpx { regex_build_one_n*?: } #1 +\cs_new_protected_nopar:cpn { regex_build_one_nn?: } { - \exp_not:N \prg_replicate:nn {#1} { \exp_not:N \regex_build_one_: } - \exp_not:c { regex_build_one_*?: } + \regex_build_one_nn_aux:nnnn {?} + { + \regex_build_transitions:NNNN + \regex_action_free:n \l_regex_internal_a_int + \regex_tests_action_cost:n \l_regex_right_state_int + } } -% \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:Npn \regex_build_one_nn_aux:Nnn #1#2#3 +\cs_new_protected:Npn \regex_build_one_nn_aux:nnnn #1#2#3#4 { - \prg_replicate:nn {#2} { \regex_build_one_: } - \prg_replicate:nn {#3-#2} {#1} + \regex_build_one_n: {#3} + \int_compare:nNnTF {#3} > {#4} + { + \msg_kernel_error:nnxxx + { regex } { quantifier-backwards } {#3} {#4} {#1} + } + { + \int_set:Nn \l_regex_internal_a_int + { \l_regex_right_state_int + #4 - #3 } + \prg_replicate:nn { #4 - #3 } { #2 } + } } -\cs_new_protected_nopar: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_??: } } +\cs_new_protected_nopar:cpn { regex_build_one_?: } + { \regex_build_one_nn: \c_zero \c_one } +\cs_new_protected_nopar:cpx { regex_build_one_??: } + { \exp_not:c { regex_build_one_nn?: } \c_zero \c_one } % \end{macrocode} % \end{macro} % \end{macro} @@ -2751,7 +3081,7 @@ \regex_seq_pop_int:NN \l_regex_left_state_seq \l_regex_left_state_int \regex_seq_pop_int:NN \l_regex_right_state_seq \l_regex_right_state_int \regex_seq_pop_use:N \l_regex_end_group_seq - \seq_pop:NN \l_regex_end_alternation_seq \l_regex_tmpa_tl + \seq_pop:NN \l_regex_end_alternation_seq \l_regex_internal_a_tl } % \end{macrocode} % Building each branch. @@ -2798,7 +3128,7 @@ { \cs_if_exist_use:cF { regex_build_special_group_\token_to_str:N #2 : } { - \msg_kernel_error:nnx { regex } { unsupported } + \msg_kernel_error:nnx { regex } { special-group-unknown } { (? \token_to_str:N #2 } %) \regex_build_special:N ( % ) \regex_build_raw:N ? @@ -2888,7 +3218,7 @@ \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 } } + { \msg_kernel_error:nnx { regex } { unknown-option } { #3 } } \regex_build_options:NNN #1 } { @@ -2897,7 +3227,7 @@ { ) } { } { - } { \regex_build_options:NNN - } } - { \msg_error:nnx { regex } { invalid-in-option } { #3 } } + { \msg_kernel_error:nnx { regex } { invalid-in-option } { #3 } } } } \cs_new_protected_nopar:cpn { regex_build_option_+i: } @@ -2938,88 +3268,76 @@ % \begin{macrocode} \cs_new_protected:Npn \regex_build_group_submatches:NN #1#2 { - \seq_pop:NN \l_regex_capturing_group_seq \l_regex_tmpa_tl - \int_compare:nNnF { \l_regex_tmpa_tl } < \c_zero + \seq_pop:NN \l_regex_capturing_group_seq \l_regex_internal_a_tl + \int_compare:nNnF { \l_regex_internal_a_tl } < \c_zero { \regex_toks_put_left:Nx #1 - { \regex_action_submatch:n { \l_regex_tmpa_tl < } } + { \regex_action_submatch:n { \l_regex_internal_a_tl < } } \regex_toks_put_left:Nx #2 - { \regex_action_submatch:n { \l_regex_tmpa_tl > } } + { \regex_action_submatch:n { \l_regex_internal_a_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: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: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_stop - #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} +% \cs{l_regex_internal_a_int} to a new state. % % \begin{macro}[aux]{\regex_build_group_qs_aux:NN} % \begin{macro}[aux]{\regex_build_group_?:} % \begin{macro}[aux]{\regex_build_group_??:} -% \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}. +% \cs{l_regex_internal_a_int}. % The second transition corresponds to skipping the group; % it has lower priority (\texttt{put_right}) for greedy % operators, and higher priority (\texttt{put_left}) for % lazy operators. +% We shift the left state to avoid interactions with +% \texttt{action_submatch}. % \begin{macrocode} +\cs_new_protected_nopar:Npn \regex_build_group_qs_aux: + { + \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int + \regex_build_new_state: + \tex_toks:D \l_regex_right_state_int = \tex_toks:D \l_regex_internal_a_int + \regex_toks_put_left:Nx \l_regex_right_state_int + { + \int_sub:Nn \l_regex_current_state_int + { + \int_eval:n % ^^A here we lie! + { \l_regex_right_state_int - \l_regex_internal_a_int } + } + } + \use:x + { + \tex_toks:D \l_regex_internal_a_int + { + \s_stop + \regex_action_free:n + { + \int_eval:n + { \l_regex_right_state_int - \l_regex_internal_a_int } + } + } + } + \regex_build_group_submatches:NN + \l_regex_right_state_int \l_regex_left_state_int + } \cs_new_protected:Npn \regex_build_group_qs_aux:NN #1#2 { - \regex_build_group_shift:N \regex_action_free:n + \regex_build_group_qs_aux: \int_set_eq:NN \l_regex_right_state_int \l_regex_left_state_int \regex_build_transition:NN \regex_action_free:n #1 - #2 \l_regex_tmpa_int + #2 \l_regex_internal_a_int { \regex_action_free:n - { \int_eval:n { \l_regex_right_state_int - \l_regex_tmpa_int } } + { \int_eval:n { \l_regex_right_state_int - \l_regex_internal_a_int } } } } \cs_new_protected_nopar:cpn { regex_build_group_?: } @@ -3032,112 +3350,83 @@ \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: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: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{macro}[aux]{\regex_build_group_transition_right_max:} +% The braced quantifiers rely on replicating the states corresponding +% to the group that has just been built, and joining the right state +% of each copy to the left state of the next copy. Once this function +% has been run, \cs{l_regex_internal_a_int} points to the last copy of +% the initial left-most state, \cs{l_regex_left/right_state_int} have +% their initial values. Furthermore, \cs{l_regex_max_state_int} is set +% appropriately to the largest allocated \tn{toks} register plus $1$. % \begin{macrocode} -\cs_new_protected:Npn \regex_build_group_n_aux:n #1 +\cs_new_protected:Npn \regex_build_group_transition_right_max: { \regex_toks_put_right:Nx \l_regex_right_state_int { \regex_action_free:n - { - \int_eval:n %^^A todo: document why that value. - { \l_regex_max_state_int - \c_one - \l_regex_left_state_int } - } + { \int_eval:n { \l_regex_max_state_int - \l_regex_right_state_int } } } - \int_set_eq:NN \l_regex_tmpa_int \l_regex_left_state_int - \int_set_eq:NN \l_regex_tmpb_int \l_regex_max_state_int + } +\cs_new_protected:Npn \regex_build_group_n_aux:n #1 + { + \int_set_eq:NN \l_regex_internal_a_int \l_regex_left_state_int + \int_set_eq:NN \l_regex_internal_b_int \l_regex_max_state_int + \int_add:Nn \l_regex_right_state_int + { ( #1 - 1 ) * ( \l_regex_max_state_int - \l_regex_left_state_int ) } \int_set:Nn \l_regex_max_state_int { \l_regex_left_state_int - + #1 * ( \l_regex_max_state_int - \l_regex_left_state_int ) + + (#1) * ( \l_regex_max_state_int - \l_regex_left_state_int ) } - \int_while_do:nNnn \l_regex_tmpb_int < \l_regex_max_state_int + \int_while_do:nNnn \l_regex_internal_b_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 + \tex_toks:D \l_regex_internal_b_int + = \tex_toks:D \l_regex_internal_a_int + \int_incr:N \l_regex_internal_a_int + \int_incr:N \l_regex_internal_b_int } } % \end{macrocode} % \end{macro} +% \end{macro} % -% \begin{macro}[aux]{\regex_build_group_n:} -% \begin{macro}[aux]{\regex_build_group_n?:} +% \begin{macro}[aux]{\regex_build_group_n:, \regex_build_group_n?:} +% \begin{macro}[aux]{\regex_build_group_:} % These functions are called in case the syntax is -% \texttt{\{\meta{int}\}}. Greedy and lazy operators -% are identical, since the number of repetitions is fixed. -% We only record the submatch information at the last repetition. +% \texttt{\{\meta{int}\}}, or in the absence of quantifier (with +% $n=1$). Greedy and lazy operators are identical, since the number of +% repetitions is fixed. We only record the submatch information at +% the last repetition; and of course, in the case $n=0$, we record +% nothing. % \begin{macrocode} \cs_new_protected:Npn \regex_build_group_n: #1 - { % ^^A todo: catch case #1 <= 0. + { + \regex_build_group_transition_right_max: \regex_build_group_n_aux:n {#1} - \regex_build_transition:NN - \regex_action_free:n \l_regex_right_state_int - \regex_build_group_submatches:NN - \l_regex_tmpa_int \l_regex_left_state_int + \regex_build_new_state: + \int_compare:nNnF {#1} = \c_zero + { + \regex_build_group_submatches:NN + \l_regex_internal_a_int \l_regex_left_state_int + } } \cs_new_eq:cN { regex_build_group_n?: } \regex_build_group_n: +\cs_new_protected_nopar:Npn \regex_build_group_: + { \regex_build_group_n: \c_one } % \end{macrocode} % \end{macro} % \end{macro} % -% \begin{macro}[aux]{\regex_build_group_n*:} -% \begin{macro}[aux]{\regex_build_group_n*?:} +% \begin{macro}[aux]{\regex_build_group_n*:, \regex_build_group_n*?:} +% \begin{macro}[aux]{\regex_build_group_*:, \regex_build_group_*?:} +% \begin{macro}[aux]{\regex_build_group_+:, \regex_build_group_+?:} +% \begin{macro}[aux]{\regex_build_group_n_star_aux:NNn} % These functions are called in case the syntax is % \texttt{\{\meta{int},\}}. They are somewhat hybrid between % the \texttt{\{\meta{int}\}} and the \texttt{*} quantifiers. @@ -3146,61 +3435,271 @@ % case no iteration was made, here, we know that the submatch % information is overwritten in any case. % \begin{macrocode} -\cs_new_protected:cpn { regex_build_group_n*: } #1 - { % ^^A todo: catch case #1 <= 0. - \regex_build_group_n_aux:n {#1} - \regex_build_transitions: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*: } + { + \regex_build_group_n_star_aux:NNn + \regex_toks_put_right:Nx \regex_toks_put_left:Nx } -\cs_new_protected:cpn { regex_build_group_n*?: } #1 - { % ^^A todo: catch case #1 <= 0. - \regex_build_group_n_aux:n {#1} - \regex_build_transitions: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 +\cs_new_protected_nopar:cpn { regex_build_group_n*?: } + { + \regex_build_group_n_star_aux:NNn + \regex_toks_put_left:Nx \regex_toks_put_right:Nx } +\cs_new_protected:Npn \regex_build_group_n_star_aux:NNn #1#2#3 + { + \int_compare:nNnTF {#3} = \c_zero + { \regex_build_group_qs_aux:NN \l_regex_internal_a_int #1 } + { + \regex_build_group_transition_right_max: + \regex_build_group_n_aux:n {#3} + \regex_build_new_state: + #2 \l_regex_left_state_int + { + \regex_action_free:n + { + \int_eval:n + { \l_regex_internal_a_int - \l_regex_left_state_int } + } + } + \regex_build_group_submatches:NN + \l_regex_internal_a_int \l_regex_left_state_int + } + } +\cs_new_protected_nopar:cpx { regex_build_group_*: } + { \exp_not:c { regex_build_group_n*: } \c_zero } +\cs_new_protected_nopar:cpx { regex_build_group_*?: } + { \exp_not:c { regex_build_group_n*?: } \c_zero } +\cs_new_protected_nopar:cpx { regex_build_group_+: } + { \exp_not:c { regex_build_group_n*: } \c_one } +\cs_new_protected_nopar:cpx { regex_build_group_+?: } + { \exp_not:c { regex_build_group_n*?: } \c_one } % \end{macrocode} % \end{macro} % \end{macro} +% \end{macro} +% \end{macro} % -% \begin{macro}[aux]{\regex_build_group_nn:} -% \begin{macro}[aux]{\regex_build_group_nn?:} +% \begin{macro}[aux]{\regex_build_group_nn:, \regex_build_group_nn?:} +% \begin{macro}[aux]{\regex_build_group_nn_aux:nnnn} +% \begin{macro}[aux, rEXP]{\regex_build_group_nn_aux_ii:w} % These functions are called when the syntax is either % \texttt{\{\meta{int},\}} or \texttt{\{\meta{int},\meta{int}\}}. % \begin{macrocode} -\cs_new_protected: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:Npn \regex_build_group_nn: + { + \regex_build_group_nn_aux:nnnn { } + \regex_build_group_transition_right_max: + } +\cs_new_protected_nopar:cpn { regex_build_group_nn?: } + { + \regex_build_group_nn_aux:nnnn { } + { + \use:x + { + \tex_toks:D \l_regex_right_state_int + { + \exp_after:wN \regex_build_group_nn_aux_ii:w + \tex_the:D \tex_toks:D \l_regex_right_state_int + } + } + } + } +\cs_new_protected:Npn \regex_build_group_nn_aux:nnnn #1#2#3#4 + { + \int_compare:nNnTF {#3} > {#4} + { + \msg_kernel_error:nnxxx + { regex } { quantifier-backwards } {#3} {#4} {#1} + } + { + \int_compare:nNnTF {#3} = \c_zero + { + \regex_build_group_qs_aux: + \int_set_eq:NN \l_regex_right_state_int \l_regex_left_state_int + \int_set_eq:NN \l_regex_left_state_int \l_regex_internal_a_int + \regex_build_group_transition_right_max: + \regex_build_group_n_aux:n { #4 - #3 } + \int_set_eq:NN \l_regex_internal_c_int \l_regex_right_state_int + \int_set_eq:NN \l_regex_right_state_int \l_regex_left_state_int + \prg_replicate:nn { #4 - #3 } + { + #2 + \int_add:Nn \l_regex_right_state_int + { \l_regex_internal_b_int - \l_regex_internal_a_int } + } + \int_set_eq:NN \l_regex_right_state_int \l_regex_internal_c_int + \int_set_eq:NN \l_regex_left_state_int \l_regex_internal_a_int + \regex_build_new_state: + } + { + \regex_build_group_transition_right_max: + \regex_build_group_n_aux:n {#3} + \int_set_eq:NN \l_regex_left_state_int \l_regex_internal_a_int + \regex_build_group_submatches:NN + \l_regex_left_state_int \l_regex_right_state_int + \regex_build_group_n_aux:n { #4 - #3 + \c_one } + \int_sub:Nn \l_regex_right_state_int + { \l_regex_internal_a_int - \l_regex_left_state_int } + \prg_replicate:nn { #4 - #3 } + { + #2 + \int_add:Nn \l_regex_right_state_int + { \l_regex_internal_b_int - \l_regex_internal_a_int } + } + \int_set_eq:NN \l_regex_left_state_int \l_regex_internal_a_int + \regex_build_new_state: + } + } + } +\cs_new_protected:Npn \regex_build_group_nn_aux_ii:w #1 \regex_action_free:n + { + #1 + \regex_action_free:n + { + \int_eval:n + { \l_regex_max_state_int - \l_regex_right_state_int } + } + \regex_action_free:n + } +% \end{macrocode} +% \end{macro} +% \end{macro} +% \end{macro} +% +% \subsubsection{Matching raw token lists with \cs{u}} +% +%^^A todo: document interactions between caselessness and |\u{...}| +%^^A todo: clarify when l_regex_catcodes_int is reset. +% +% \begin{macro}[aux]{\regex_build_/u:} +% \begin{macro}[aux]{\regex_build_u_loop:NN} +% The |\u| escape is invalid in classes nad directly following a +% catcode test. Otherwise, it must be followed by a left brace. We +% then collect the characters for the argument of |\u| within an +% \texttt{x}-expanding assignment. In principle we could just wait to +% encounter a right brace, but this is unsafe: if the right brace is +% missing, then we will reach the end-markers of the regex, and +% continue, leading to obscure fatal errors. Instead, we only allow +% raw and special characters, and stop when encountering a special +% right brace. +% \begin{macrocode} +\cs_new_protected:cpn { regex_build_/u: } #1#2 + { + \regex_build_if_assertions_forbidden:TF + { \regex_build_raw_error:N u #1#2 } + { + \str_if_eq:xxTF {#1#2} { \regex_build_special:N \c_lbrace_str } + { + \tl_set:Nx \l_regex_internal_a_tl { \if_false: } \fi: + \regex_build_u_loop:NN + } + { + \msg_kernel_error:nn { regex } { u-missing-lbrace } + #1#2 + } + } } -\cs_new_protected: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} +\cs_new:Npn \regex_build_u_loop:NN #1#2 + { + \token_if_eq_meaning:NNTF #1 \regex_build_raw:N + { #2 \regex_build_u_loop:NN } + { + \token_if_eq_meaning:NNTF #1 \regex_build_special:N + { + \exp_after:wN \token_if_eq_charcode:NNTF \c_rbrace_str #2 + { \if_false: { \fi: } \regex_build_u_end: } + { #2 \regex_build_u_loop:NN } + } + { + \if_false: { \fi: } + \msg_kernel_error:nnx { regex } { u-missing-rbrace } {#2} + \regex_build_u_end: + #1#2 + } + } } % \end{macrocode} % \end{macro} % \end{macro} % -% \subsection{Matching} +% \begin{macro}[aux]{\regex_build_u_end:} +% Once we have extracted the variable's name, we store the contents of +% that variable in \cs{l_regex_internal_a_tl}. The behaviour of |\u| +% then depends on whether we are within a |\c{...}| escape (in this +% case, the variable is turned to a string), or not. Afterwards, clean +% up the value of \cs{l_regex_tests_tl}, but not +% \cs{l_regex_tests_bool}, because this is guaranteed to be +% \texttt{true} at the start, and is not affected by anything we do +% here. +% \begin{macrocode} +\cs_new_protected:Npn \regex_build_u_end: + { + \tl_set:Nv \l_regex_internal_a_tl \l_regex_internal_a_tl + \if_num:w \l_regex_build_mode_int = \c_zero + \regex_build_u_not_cs: + \else: + \regex_build_u_in_cs: + \fi: + \tl_clear:N \l_regex_tests_tl + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\regex_build_u_in_cs:} +% When |\u| appears within a control sequence, the variable is +% converted to a string, and we add to the NFA one state per +% character. We use \cs{regex_build_one_:} directly, as this avoids +% having to search for a quantifier. +% \begin{macrocode} +\cs_new_protected:Npn \regex_build_u_in_cs: + { + \exp_args:NNo \str_gset_other:Nn \g_regex_internal_tl + { \l_regex_internal_a_tl } + \tl_map_inline:Nn \g_regex_internal_tl + { + \tl_set:Nx \l_regex_tests_tl { \regex_item_equal:n { `##1 } } + \regex_build_one_: + } + } +% \end{macrocode} +% \end{macro} % -% \subsubsection{Use of \TeX{} registers when matching} +% \begin{macro}[aux]{\regex_build_u_not_cs:} +% In mode $0$, the |\u| escape adds one state to the NFA for each +% token in \cs{l_regex_internal_a_tl}. The tests corresponding to a +% given \meta{token} are: first test the category, then, if the +% \meta{token} is a control sequence, compare the string +% representations, otherwise compare the character codes. We could +% compare the string representations in all cases, but that doesn't +% interact well with caseless matching. +% \begin{macrocode} +\cs_new_protected:Npn \regex_build_u_not_cs: + { + \exp_args:No \tl_analysis_map_inline:nn { \l_regex_internal_a_tl } + { + \tl_set:Nx \l_regex_tests_tl + { + \exp_not:N \int_compare:nNnT + \l_regex_current_catcode_int = { \int_value:w "##2 } + { + \int_compare:nNnTF { "##2 } = \c_zero + { + \exp_not:n + { \str_if_eq:xxT { \l_regex_current_token_tl } {##1} } + { \regex_break_true:w } + } + { \regex_item_equal:n {##3} } + } + } + \regex_build_one_: + } + } +% \end{macrocode} +% \end{macro} % -% 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 token list 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 token is read. +% \subsection{Matching} % -% At every step, we unpack that array of active states and +% At every index, we unpack that array of active states and % empty it. Then loop over all active states, and perform the % instruction at that state of the NFA. This can involve % \enquote{free} transitions to other states, or transitions @@ -3255,27 +3754,19 @@ % 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, -%^^A todo: update: submatches' end-points are muskips. -% 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 +% \cs{l_regex_max_active_int}, and converting the integer % to a dimension (suitable for a \tn{skip} assignment) in % scaled points. % \begin{macrocode} \cs_new_protected:Npn \regex_store_state:n #1 { - \int_incr:N \l_regex_max_index_int - \tex_skip:D \l_regex_max_index_int #1 sp \scan_stop: + \int_incr:N \l_regex_max_active_int + \tex_skip:D \l_regex_max_active_int #1 sp \scan_stop: \regex_store_submatches:n {#1} } % \end{macrocode} @@ -3291,7 +3782,7 @@ % 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_id_int} in \texttt{sp}. +% \cs{l_regex_step_int} in \texttt{sp}. % The primitive conditional is ended before unpacking % the \tn{toks} register. % \begin{macrocode} @@ -3301,10 +3792,9 @@ { \regex_state_use_aux:n { \exp_after:wN \use_none_delimit_by_s_stop:w } } \cs_new_protected:Npn \regex_state_use_aux:n #1 { - \if_num:w \tex_dimen:D \l_regex_current_state_int - < \l_regex_unique_id_int + \if_num:w \tex_dimen:D \l_regex_current_state_int < \l_regex_step_int \tex_dimen:D \l_regex_current_state_int - = \l_regex_unique_id_int sp \scan_stop: + = \l_regex_step_int sp \scan_stop: #1 \tex_the:D \tex_toks:D \exp_after:wN \l_regex_current_state_int \fi: \scan_stop: @@ -3364,11 +3854,7 @@ { \exp_after:wN \c_zero \exp_after:wN \regex_state_submatches:nn \exp_after:wN - { - \int_value:w \int_eval:w - \l_regex_unique_id_int + \c_one - \exp_after:wN - } + { \int_value:w \int_eval:w \l_regex_step_int + \c_one \exp_after:wN } \exp_after:wN { \l_regex_current_submatches_prop } \regex_state_submatches:nn {#1} {#2} \s_stop @@ -3385,7 +3871,7 @@ % \begin{macrocode} \cs_new_protected:Npn \regex_state_submatches:nn #1#2 { - \if_num:w #1 = \l_regex_unique_id_int + \if_num:w #1 = \l_regex_step_int \tl_set:Nn \l_regex_current_submatches_prop { #2 } \fi: } @@ -3403,51 +3889,42 @@ % \begin{macrocode} \cs_new_protected:Npn \regex_match:n #1 { - \tl_set_analysis:Nn \l_regex_tmpa_tl {#1} - \int_zero:N \l_regex_nesting_int - \int_set_eq:NN \l_regex_current_step_int \l_regex_max_state_int + \int_set_eq:NN \l_regex_current_index_int \l_regex_max_state_int \regex_query_set:nnn { } { -1 } { -2 } - \int_set_eq:NN \l_regex_min_step_int \l_regex_current_step_int - \exp_after:wN \regex_query_set_loop:ww - \l_regex_tmpa_tl - \s_tl { ? \prg_map_break: } \s_tl - \prg_break_point:n { } - \int_set_eq:NN \l_regex_max_step_int \l_regex_current_step_int + \int_set_eq:NN \l_regex_min_index_int \l_regex_current_index_int + \tl_analysis_map_inline:nn {#1} + { + \regex_query_set:nnn {##1} {"##2} {##3} + \if_case:w "##2 \exp_stop_f: + \or: \int_incr:N \l_regex_nesting_int + \or: \int_decr:N \l_regex_nesting_int + \fi: + } + \int_set_eq:NN \l_regex_max_index_int \l_regex_current_index_int \regex_query_set:nnn { } { -1 } { -2 } - \regex_match_initial_setup: \regex_match_once: } -\cs_new:Npn \regex_query_set_loop:ww #1 \s_tl #2#3 \s_tl - { - \use_none:n #2 - \regex_query_set:nnn {#1} {"#2} {#3} - \if_case:w "#2 \exp_stop_f: - \or: \int_incr:N \l_regex_nesting_int - \or: \int_decr:N \l_regex_nesting_int - \fi: - \regex_query_set_loop:ww - } \cs_new_protected:Npn \regex_query_set:nnn #1#2#3 { - \tex_muskip:D \l_regex_current_step_int + \tex_muskip:D \l_regex_current_index_int = \etex_gluetomu:D #3 sp plus #2 sp minus \l_regex_nesting_int sp \scan_stop: - \tex_toks:D \l_regex_current_step_int {#1} - \int_incr:N \l_regex_current_step_int + \tex_toks:D \l_regex_current_index_int {#1} + \int_incr:N \l_regex_current_index_int } \cs_new_protected_nopar:Npn \regex_query_get: { \tl_set:Nx \l_regex_current_token_tl - { \tex_the:D \tex_toks:D \l_regex_current_step_int } + { \tex_the:D \tex_toks:D \l_regex_current_index_int } \l_regex_current_char_int - = \etex_mutoglue:D \tex_muskip:D \l_regex_current_step_int + = \etex_mutoglue:D \tex_muskip:D \l_regex_current_index_int \l_regex_current_catcode_int = \etex_gluestretch:D - \etex_mutoglue:D \tex_muskip:D \l_regex_current_step_int + \etex_mutoglue:D \tex_muskip:D \l_regex_current_index_int } % \end{macrocode} % \end{macro} @@ -3482,13 +3959,14 @@ % \begin{macrocode} \cs_new_protected_nopar:Npn \regex_match_initial_setup: { - \prg_stepwise_inline:nnnn {0} {1} { \l_regex_max_state_int - \c_one } - { \tex_dimen:D ##1 \c_minus_one sp \scan_stop: } - \int_set_eq:NN \l_regex_unique_id_int \c_minus_one - \int_set:Nn \l_regex_start_step_int - { \l_regex_min_step_int - \c_one } - \int_set_eq:NN \l_regex_current_step_int \l_regex_min_step_int - \int_set_eq:NN \l_regex_success_step_int \l_regex_min_step_int + \int_set_eq:NN \l_regex_step_int \c_minus_one + \prg_stepwise_inline:nnnn + \c_zero \c_one { \l_regex_max_state_int - \c_one } + { \tex_dimen:D ##1 \l_regex_step_int sp \scan_stop: } + \int_set:Nn \l_regex_start_index_int + { \l_regex_min_index_int - \c_one } + \int_set_eq:NN \l_regex_current_index_int \l_regex_min_index_int + \int_set_eq:NN \l_regex_success_index_int \l_regex_min_index_int \int_set_eq:NN \l_regex_submatch_int \l_regex_max_state_int \bool_set_false:N \l_regex_success_empty_bool \bool_gset_false:N \g_regex_success_bool @@ -3504,21 +3982,21 @@ { \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:Nn \l_regex_current_step_int - { \l_regex_start_step_int - \c_one } + { \cs_set_eq:NN \regex_if_two_empty_matches:F \regex_if_match_empty:F } + { \cs_set_eq:NN \regex_if_two_empty_matches:F \use:n } + \int_set_eq:NN \l_regex_start_index_int \l_regex_success_index_int + \int_set:Nn \l_regex_current_index_int + { \l_regex_start_index_int - \c_one } \bool_set_false:N \l_regex_success_match_bool - \int_zero:N \l_regex_max_index_int + \int_zero:N \l_regex_max_active_int \regex_store_state:n {0} %^^A _state_int! } % \end{macrocode} % \end{macro} % % \begin{macro}[aux]{\regex_match_loop:} -% \begin{macro}[aux]{\regex_match_one_index:n} -% \begin{macro}[aux]{\regex_match_one_index_aux:n} +% \begin{macro}[aux]{\regex_match_one_active:n} +% \begin{macro}[aux]{\regex_match_one_active_aux:n} % Setup what needs to be reset at every character, % then set \cs{l_regex_current_char_int} to the % character code of the token that is read @@ -3532,38 +4010,37 @@ % \begin{macrocode} \cs_new_protected_nopar:Npn \regex_match_loop: { - \int_incr:N \l_regex_current_step_int - \int_incr:N \l_regex_unique_id_int + \int_incr:N \l_regex_current_index_int + \int_incr:N \l_regex_step_int \bool_set_false:N \l_regex_fresh_thread_bool \int_set_eq:NN \l_regex_last_char_int \l_regex_current_char_int \regex_query_get: \regex_match_loop_case_hook: - \cs_set_nopar:Npx \regex_tmp:w + \use:x { - \int_zero:N \l_regex_max_index_int - \regex_match_one_index:w 1 ; \prg_break_point:n { } + \int_zero:N \l_regex_max_active_int + \regex_match_one_active:w 1 ; \prg_break_point:n { } \exp_not:N \prg_break_point:n { } } - \regex_tmp:w \if_num:w \l_regex_current_char_int < \c_minus_one \exp_after:wN \prg_map_break: \fi: - \if_num:w \l_regex_max_index_int = \c_zero + \if_num:w \l_regex_max_active_int = \c_zero \exp_after:wN \prg_map_break: \fi: \regex_match_loop: } -\cs_new:Npn \regex_match_one_index:w #1; +\cs_new:Npn \regex_match_one_active:w #1; { - \if_num:w #1 > \l_regex_max_index_int + \if_num:w #1 > \l_regex_max_active_int \exp_after:wN \prg_map_break: \fi: - \regex_match_one_index_aux:n + \regex_match_one_active_aux:n { \int_value:w \tex_skip:D #1 } - \exp_after:wN \regex_match_one_index:w + \exp_after:wN \regex_match_one_active:w \int_use:N \int_eval:w #1 + \c_one ; } -\cs_new_protected:Npn \regex_match_one_index_aux:n #1 +\cs_new_protected:Npn \regex_match_one_active_aux:n #1 { \int_set:Nn \l_regex_current_state_int {#1} \prop_clear:N \l_regex_current_submatches_prop @@ -3604,7 +4081,7 @@ % % \subsubsection{Actions when matching} % -% \begin{macro}[aux]{\regex_action_start_wildcard:} +% \begin{macro}[int]{\regex_action_start_wildcard:} %: the first state has a free transition to the second % state, where the regular expression really begins, and a costly % transition to itself, to try again at the next character. ^^A ?? @@ -3627,7 +4104,7 @@ % \end{macrocode} % \end{macro} % -% \begin{macro}[aux]{\regex_action_cost:n} +% \begin{macro}[int]{\regex_action_cost:n} % A transition which consumes the current character and moves % to state |#1|. % \begin{macrocode} @@ -3639,7 +4116,7 @@ % \end{macrocode} % \end{macro} % -% \begin{macro}[aux]{\regex_action_success:} +% \begin{macro}[int]{\regex_action_success:} % There is a successful match when an execution path reaches % the end of the regular expression. Then store the current % step and submatches. The current step is then interrupted @@ -3650,12 +4127,12 @@ % \begin{macrocode} \cs_new_protected_nopar:Npn \regex_action_success: { - \regex_last_match_empty:F + \regex_if_two_empty_matches:F { \bool_set_true:N \l_regex_success_match_bool \bool_set_eq:NN \l_regex_success_empty_bool \l_regex_fresh_thread_bool - \int_set_eq:NN \l_regex_success_step_int \l_regex_current_step_int + \int_set_eq:NN \l_regex_success_index_int \l_regex_current_index_int \prop_set_eq:NN \l_regex_success_submatches_prop \l_regex_current_submatches_prop \prg_map_break: @@ -3664,7 +4141,7 @@ % \end{macrocode} % \end{macro} % -% \begin{macro}[aux]{\regex_action_free:n} +% \begin{macro}[int]{\regex_action_free:n} % To copy a thread, check whether the program state has already % been used at this character. If not, store submatches in the % new state, and insert the instructions for that state in the @@ -3674,7 +4151,7 @@ % \begin{macrocode} \cs_new_protected:Npn \regex_action_free:n #1 { - \cs_set_nopar:Npx \regex_tmp:w + \use:x { \int_add:Nn \l_regex_current_state_int {#1} \regex_state_use: @@ -3683,23 +4160,34 @@ \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} +% \begin{macro}[int]{\regex_action_submatch:n} % Update the current submatches with the information -% from the current step. +% from the current index. % \begin{macrocode} \cs_new_protected:Npn \regex_action_submatch:n #1 { \prop_put:Nno \l_regex_current_submatches_prop {#1} - { \int_use:N \l_regex_current_step_int } + { \int_use:N \l_regex_current_index_int } } % \end{macrocode} % \end{macro} % +% \subsubsection{??}%^^A todo: title +% +% \begin{macro}{\regex_if_match_empty:T, \regex_if_match_empty:F} +% +% \begin{macrocode} +\cs_new:Npn \regex_if_match_empty:T + { \int_compare:nNnT \l_regex_start_index_int = \l_regex_current_index_int } +\cs_new:Npn \regex_if_match_empty:F + { \int_compare:nNnF \l_regex_start_index_int = \l_regex_current_index_int } +% \end{macrocode} +% \end{macro} +% % \subsection{Replacement} % % \begin{macro}[rEXP]{\regex_submatch_nesting_aux:n} @@ -3717,7 +4205,7 @@ % \begin{macro}[int]{\regex_replacement:n} % Our goal here is to analyse the replacement text. First take care % of detecting escaped and non-escaped characters using -% \cs{str_escape_use:NNNn} with three protected arguments. +% \cs{regex_escape_use:nnnn} with three protected arguments. % This inserts in the input stream a token list of the form % \meta{fn 1} \meta{char 1} \ldots{} \meta{fn $N$} \meta{char $N$}, % where \meta{fn $i$} is one of the three functions, and \meta{char $i$} @@ -3730,10 +4218,10 @@ \int_zero:N \l_regex_replacement_int \int_zero:N \l_regex_nesting_int \tl_clear:N \l_regex_nesting_tl - \str_escape_use:NNNn - \regex_replacement_unescaped:N - \regex_replacement_escaped:N - \regex_replacement_raw:N + \regex_escape_use:nnnn + { \regex_replacement_unescaped:N ##1 } + { \regex_replacement_escaped:N ##1 } + { \regex_replacement_raw:N ##1 } {#1} \prg_do_nothing: \prg_do_nothing: \cs_set:Npx \regex_nesting:n ##1 @@ -3745,9 +4233,9 @@ \use:x { \exp_not:n { \cs_set:Npn \regex_replacement_tl:n ##1 } - { \str_aux_toks_range:nn \c_zero \l_regex_replacement_int } + { \regex_toks_range:nn \c_zero \l_regex_replacement_int } } - % ^^A rename! Careful with \cP\#. + % ^^A rename! } % \end{macrocode} % \end{macro} @@ -3788,19 +4276,14 @@ } \cs_new_protected:Npn \regex_replacement_escaped:N #1 { - \if_charcode:w c #1 - \exp_after:wN \regex_replacement_c:w - \else: - \if_charcode:w g #1 - \exp_after:wN \exp_after:wN \exp_after:wN \regex_replacement_g:w - \else: + \cs_if_exist_use:cF { regex_replacement_#1:w } + { \if_num:w \c_one < 1#1 \exp_stop_f: \regex_replacement_put_submatch:n {#1} \else: \regex_replacement_put:n #1 \fi: - \fi: - \fi: + } } \cs_new_protected:Npn \regex_replacement_put_submatch:n #1 { @@ -3827,7 +4310,7 @@ { \exp_not:n { #1#2 } } { \regex_replacement_unescaped:N \c_lbrace_str } { - \int_zero:N \l_regex_tmpa_int + \int_zero:N \l_regex_internal_a_int \regex_replacement_g_digits:NN } { \regex_replacement_error:NNN g #1 #2 } @@ -3837,13 +4320,13 @@ \token_if_eq_meaning:NNTF #1 \regex_replacement_unescaped:N { \if_num:w \c_one < 1#2 \exp_stop_f: - \int_set:Nn \l_regex_tmpa_int { \c_ten * \l_regex_tmpa_int + #2 } + \int_set:Nn \l_regex_internal_a_int { \c_ten * \l_regex_internal_a_int + #2 } \exp_after:wN \use_i:nnn \exp_after:wN \regex_replacement_g_digits:NN \else: \if_charcode:w \c_rbrace_str #2 \exp_args:No \regex_replacement_put_submatch:n - { \int_use:N \l_regex_tmpa_int } + { \int_use:N \l_regex_internal_a_int } \exp_after:wN \exp_after:wN \exp_after:wN \use_none:nn \else: \exp_after:wN \exp_after:wN @@ -3855,6 +4338,16 @@ { \regex_replacement_error:NNN g } #1 #2 } +\cs_new_protected:Npn \regex_replacement_u:w #1#2 + { + \str_if_eq:xxTF { #1#2 } { \regex_replacement_unescaped:N \c_lbrace_str } + { + \int_incr:N \l_regex_replacement_csnames_int + \regex_replacement_put:n + { \exp_not:n { \exp_after:wN \exp_not:V \cs:w } } + } + { \regex_replacement_error:NNN u #1#2 } + } \cs_new_protected:Npn \regex_replacement_c:w #1#2 { \token_if_eq_meaning:NNTF #1 \regex_replacement_unescaped:N @@ -3870,8 +4363,6 @@ \regex_replacement_put:n { \exp_not:n { \exp_after:wN \regex_replacement_exp_not:N \cs:w } } } -\cs_new_eq:cc { regex_replacement_c_C:w } - { regex_replacement_c_ \c_lbrace_str :w } \cs_new:Npn \regex_replacement_exp_not:N #1 { \exp_not:n {#1} } \group_begin: @@ -3989,11 +4480,11 @@ { \group_begin: \regex_build:n {#3} - \cs_set_nopar:Npx \regex_tmp:w - { #1 \exp_not:N #2 { \regex_set_aux:N #2 } } - \exp_after:wN - \group_end: - \regex_tmp:w + \use:x + { + \group_end: + #1 \exp_not:N #2 { \regex_set_aux:N #2 } + } } % \end{macrocode} % \end{macro} @@ -4026,7 +4517,7 @@ \regex_match_loop_caseless_hook: } \prg_stepwise_function:nnnN - {0} {1} {\l_regex_max_state_int - \c_one } + \c_zero \c_one {\l_regex_max_state_int - \c_one } \regex_set_aux:n \s_stop } @@ -4050,29 +4541,6 @@ % \end{macrocode} % \end{macro} % -% \begin{macro}[int, rEXP]{\regex_to_str:N} -% \begin{macro}[int, rEXP]{\regex_to_str_aux:w} -% Of course, we could simply set \cs{regex_to_str:N} equal -% to \cs{tl_to_str:N}. After all, regex variables are in particular -% token list variables. We do some more processing to start each -% line with \cs{tex_toks:D} instead of a single very long line. -% \begin{macrocode} -\cs_new:Npn \regex_to_str:N #1 - { - \exp_after:wN \regex_to_str_aux:Nw #1 - \tex_toks:D \q_stop \prg_map_break: \tex_toks:D - \prg_break_point:n { } - } -\cs_new:Npn \regex_to_str_aux:Nw #1#2\tex_toks:D - { - \use_none_delimit_by_q_stop:w #2 \q_stop - \tl_to_str:n {#1#2} \iow_newline: - \regex_to_str_aux:Nw \tex_toks:D - } -% \end{macrocode} -% \end{macro} -% \end{macro} -% % \subsubsection{Generic auxiliary functions} % % Most of \pkg{l3regex}'s work is done within a group. @@ -4236,9 +4704,9 @@ \cs_new_protected:Npn \regex_group_end_extract_seq:N #1 { \cs_set_eq:NN \seq_item:n \scan_stop: - \flag_lower:N \l_regex_group_begin_flag - \flag_lower:N \l_regex_group_end_flag - \tl_set:Nx \l_regex_tmpa_tl + \flag_clear:n { regex_begin } + \flag_clear:n { regex_end } + \tl_set:Nx \l_regex_internal_a_tl { \prg_stepwise_function:nnnN \l_regex_max_state_int @@ -4246,12 +4714,13 @@ { \l_regex_submatch_int - \c_one } \regex_extract_seq_aux:n } - \flag_test:NF \l_regex_group_begin_flag - { \flag_test:NF \l_regex_group_end_flag { \use_none:nnn } } - \msg_kernel_error:nn { regex } { sequence-unbalanced } - \tl_set:Nx \l_regex_tmpa_tl { \l_regex_tmpa_tl } + \int_compare:nNnF + { \flag_height:n { regex_begin } + \flag_height:n { regex_end } } + = \c_zero + { \msg_kernel_error:nn { regex } { sequence-unbalanced } } + \tl_set:Nx \l_regex_internal_a_tl { \l_regex_internal_a_tl } \exp_args:NNNo \group_end: - \tl_set:Nn #1 \l_regex_tmpa_tl + \tl_set:Nn #1 \l_regex_internal_a_tl } \cs_new:Npn \regex_extract_seq_aux:n #1 { @@ -4262,14 +4731,14 @@ } } \cs_new:Npn \regex_extract_seq_aux:ww #1; #2; - { %^^A todo: use flags + { \if_num:w #1 < \c_zero - \flag_raise:N \l_regex_group_end_flag + \flag_raise:n { regex_end } \prg_replicate:nn {-#1} { \exp_not:n { { \if_false: } \fi: } } \fi: \regex_query_submatch:w #2; \if_num:w #1 > \c_zero - \flag_raise:N \l_regex_group_begin_flag + \flag_raise:n { regex_begin } \prg_replicate:nn {#1} { \exp_not:n { \if_false: { \fi: } } } \fi: } @@ -4406,20 +4875,20 @@ \group_begin: \tl_set:Nn \l_regex_every_match_tl { - \if_num:w \l_regex_start_step_int < \l_regex_success_step_int + \if_num:w \l_regex_start_index_int < \l_regex_success_index_int \regex_extract: \tex_skip:D \l_regex_submatch_start_int - = \l_regex_start_step_int sp + = \l_regex_start_index_int sp plus \tex_skip:D \l_regex_submatch_start_int \scan_stop: \fi: \regex_match_once: } #1 {#2} {#3} \tex_skip:D \l_regex_submatch_int - = \l_regex_start_step_int sp - plus \l_regex_current_step_int sp \scan_stop: + = \l_regex_start_index_int sp + plus \l_regex_current_index_int sp \scan_stop: \int_incr:N \l_regex_submatch_int - \if_num:w \l_regex_start_step_int = \l_regex_current_step_int + \if_num:w \l_regex_start_index_int = \l_regex_current_index_int \if_meaning:w \c_true_bool \l_regex_success_empty_bool \int_decr:N \l_regex_submatch_int \fi: @@ -4448,34 +4917,34 @@ \exp_args:Nno #1 {#2} #4 \if_meaning:w \c_true_bool \g_regex_success_bool \regex_extract: - \int_set:Nn \l_regex_tmpa_int + \int_set:Nn \l_regex_internal_a_int { \regex_nesting:n { \l_regex_submatch_start_int } } - \if_num:w \l_regex_tmpa_int = \c_zero + \if_num:w \l_regex_internal_a_int = \c_zero \else: \msg_kernel_error:nnx { regex } { replace-unbalanced } - { \l_regex_tmpa_int } + { \l_regex_internal_a_int } \fi: - \tl_set:Nx \l_regex_tmpa_tl + \tl_set:Nx \l_regex_internal_a_tl { - \if_num:w \l_regex_tmpa_int < \c_zero - \prg_replicate:nn { - \l_regex_tmpa_int } + \if_num:w \l_regex_internal_a_int < \c_zero + \prg_replicate:nn { - \l_regex_internal_a_int } { \exp_not:n { { \if_false: } \fi: } } \fi: - \regex_query_substr:nn - { \l_regex_min_step_int } + \regex_toks_range:nn + { \l_regex_min_index_int } { \tex_skip:D \l_regex_submatch_start_int } \regex_replacement_tl:n { \l_regex_submatch_start_int } - \regex_query_substr:nn + \regex_toks_range:nn { \etex_gluestretch:D \tex_skip:D \l_regex_submatch_start_int } - { \l_regex_max_step_int } - \if_num:w \l_regex_tmpa_int > \c_zero - \prg_replicate:nn { \l_regex_tmpa_int } + { \l_regex_max_index_int } + \if_num:w \l_regex_internal_a_int > \c_zero + \prg_replicate:nn { \l_regex_internal_a_int } { \exp_not:n { \if_false: { \fi: } } } \fi: } - \tl_set:Nx \l_regex_tmpa_tl { \l_regex_tmpa_tl } + \tl_set:Nx \l_regex_internal_a_tl { \l_regex_internal_a_tl } \exp_args:NNNo \group_end: - \tl_set:Nn #4 \l_regex_tmpa_tl + \tl_set:Nn #4 \l_regex_internal_a_tl \else: \group_end: \fi: @@ -4500,12 +4969,12 @@ \regex_extract: \tex_skip:D \l_regex_submatch_start_int = \tex_the:D \tex_skip:D \l_regex_submatch_start_int - minus \l_regex_start_step_int sp \scan_stop: + minus \l_regex_start_index_int sp \scan_stop: \regex_match_once: } \regex_replacement:n {#3} \exp_args:Nno #1 {#2} #4 - \int_set:Nn \l_regex_tmpa_int + \int_set:Nn \l_regex_internal_a_int { 0 \prg_stepwise_function:nnnN @@ -4514,15 +4983,15 @@ { \l_regex_submatch_int - \c_one } \regex_nesting:n } - \if_num:w \l_regex_tmpa_int = \c_zero + \if_num:w \l_regex_internal_a_int = \c_zero \else: \msg_kernel_error:nnx { regex } { replace-unbalanced } - { \l_regex_tmpa_int } + { \l_regex_internal_a_int } \fi: - \tl_set:Nx \l_regex_tmpa_tl + \tl_set:Nx \l_regex_internal_a_tl { - \if_num:w \l_regex_tmpa_int < \c_zero - \prg_replicate:nn { - \l_regex_tmpa_int } + \if_num:w \l_regex_internal_a_int < \c_zero + \prg_replicate:nn { - \l_regex_internal_a_int } { \exp_not:n { { \if_false: } \fi: } } \fi: \prg_stepwise_function:nnnN @@ -4530,20 +4999,20 @@ \l_regex_capturing_group_int { \l_regex_submatch_int - \c_one } \regex_replace_all_aux:n - \regex_query_substr:nn - \l_regex_start_step_int \l_regex_max_step_int - \if_num:w \l_regex_tmpa_int > \c_zero - \prg_replicate:nn { \l_regex_tmpa_int } + \regex_toks_range:nn + \l_regex_start_index_int \l_regex_max_index_int + \if_num:w \l_regex_internal_a_int > \c_zero + \prg_replicate:nn { \l_regex_internal_a_int } { \exp_not:n { \if_false: { \fi: } } } \fi: } - \tl_set:Nx \l_regex_tmpa_tl { \l_regex_tmpa_tl } + \tl_set:Nx \l_regex_internal_a_tl { \l_regex_internal_a_tl } \exp_args:NNNo \group_end: - \tl_set:Nn #4 \l_regex_tmpa_tl + \tl_set:Nn #4 \l_regex_internal_a_tl } \cs_new:Npn \regex_replace_all_aux:n #1 { - \regex_query_substr:nn + \regex_toks_range:nn { \etex_glueshrink:D \tex_skip:D #1 } { \tex_skip:D #1 } \regex_replacement_tl:n {#1} } @@ -4552,14 +5021,152 @@ % % \subsection{Messages} % +% Messages for the preparsing phase. +% \begin{macrocode} +\msg_kernel_new:nnnn { regex } { trailing-backslash } + { Trailing~escape~character~\iow_char:N\\. } + { + A~regular~expression~or~its~replacement~text~ends~with~ + the~escape~character~\iow_char:N\\.~It~will~be~ignored. + } +\msg_kernel_new:nnnn { regex } { x-missing-rbrace } + { Missing~closing~brace~in~\iow_char:N\\x~hexadecimal~sequence. } + { + You~wrote~something~like~ + `\iow_char:N\\x\{\int_to_hexadecimal:n{#1}'.~ + The~closing~brace~is~missing. + } +\msg_kernel_new:nnnn { regex } { x-overflow } + { Character~code~'#1'~too~large~in~\iow_char:N\\x~hexadecimal~sequence. } + { + You~wrote~something~like~ + `\iow_char:N\\x\{\int_to_hexadecimal:n{#1}\}'.~ + The~character~code~'#1'~is~larger~than~\int_use:N \c_max_char_int. + } +% \end{macrocode} +% +% Messages for missing or extra closing brackets and parentheses, with +% some fancy singular/plural handling for the case of parentheses. +% \begin{macrocode} +\msg_kernel_new:nnnn { regex } { missing-rbrack } + { Missing~right~bracket~inserted~in~regular~expression. } + { + LaTeX~was~given~a~regular~expression~where~a~character~class~ + was~started~with~'[',~but~the~matching~']'~is~missing. + } +\msg_kernel_new:nnnn { regex } { missing-rparen } + { + Missing~right~parenthes\int_compare:nTF{#1=1}{i}{e}s~ + inserted~in~regular~expression. + } + { + LaTeX~was~given~a~regular~expression~with~\int_eval:n{#1}~ + more~left~parenthes\int_compare:nTF{#1=1}{i}{e}s~than~right~ + parenthes\int_compare:nTF{#1=1}{i}{e}s. + } +\msg_kernel_new:nnnn { regex } { extra-rparen } + { Extra~right~parenthesis~ignored~in~regular~expression. } + { + LaTeX~came~across~a~closing~parenthesis~when~no~submatch~group~ + was~open.~The~parenthesis~will~be~ignored. + } +% \end{macrocode} +% +% Sometimes escaped alphanumerics are not allowed everywhere. +% \begin{macrocode} +\msg_kernel_new:nnnn { regex } { class-bad-escape } + { Invalid~escape~\c_backslash_str #1~in~character~class. } + { + The~escape~sequence~\iow_char:N\\#1~may~not~appear~within~ + a~character~class.~For~instance,~assertions~(which~match~zero~ + characters)~would~not~make~sense~there. + } +\msg_kernel_new:nnnn { regex } { catcode-bad-escape } + { Invalid~escape~\c_backslash_str #1~following~category~test. } + { + The~escape~sequence~\iow_char:N\\#1~may~not~appear~following~ + a~category~test~such~as~\iow_char:N\\cL~or~ + \iow_char:N\\c[\iow_char:N\^BE]. + } +% \end{macrocode} +% +% Range errors. +% \begin{macrocode} +\msg_kernel_new:nnnn { regex } { range-missing-end } + { Invalid~end-point~for~range~'#1-#2'~in~character~class. } + { + The~end-point~'#2'~of~the~range~'#1-#2'~may~not~serve~as~an~ + end-point~for~a~range:~alphanumeric~characters~should~not~be~ + escaped,~and~non-alphanumeric~characters~should~be~escaped. + } +\msg_kernel_new:nnnn { regex } { range-backwards } + { Range~[#1-#2]~out~of~order~in~character~class. } + { + In~ranges~of~characters~[x-y]~appearing~in~character~classes,~ + the~first~character~code~must~not~be~larger~than~the~second.~ + Here,~#1~has~character~code~\int_eval:n {`#1},~while~#2~has~ + character~code~\int_eval:n {`#2}. + } +% \end{macrocode} +% +% Errors related to |\c| and |\u|. +% \begin{macrocode} +\msg_kernel_new:nnnn { regex } { c-bad-mode } + { Invalid~nested~\iow_char:N\\c~escape~in~regular~expression. } + { + The~\iow_char:N\\c~escape~cannot~be~used~within~ + a~control~sequence~test~'\iow_char:N\\c{...}'.~ + To~combine~several~category~tests,~use~'\iow_char:N\\c[...]'. + } +\msg_kernel_new:nnnn { regex } { c-missing-rbrace } + { Missing~right~brace~inserted~for~\iow_char:N\\c~escape. } + { + LaTeX~was~given~a~regular~expression~where~a~ + '\iow_char:N\\c\iow_char:N\{...'~construction~was~not~ended~ + with~a~closing~brace~'\iow_char:N\}'. + } +\msg_kernel_new:nnnn { regex } { c-missing-rbrack } + { Missing~right~bracket~inserted~for~\iow_char:N\\c~escape. } + { + A~construction~'\iow_char:N\\c[...'~appears~in~a~ + regular~expression,~but~the~closing~']'~is~not~present. + } +\msg_kernel_new:nnnn { regex } { c-missing-category } + { Invalid~character~'#1'~following~\iow_char\\c~escape. } + { + In~regular~expressions,~the~\iow_char:N\\c~escape~sequence~ + may~only~be~followed~by~a~left~brace,~a~left~bracket,~or~a~ + capital~letter~representing~a~character~category,~namely~ + one~of~ABCDELMOPSTU. + } +\msg_kernel_new:nnnn { regex } { u-missing-lbrace } + { Missing~left~brace~following~\iow_char:N\\u~escape. } + { + The~\iow_char:N\\u~escape~sequence~must~be~followed~by~ + a~brace~group~with~the~name~of~the~variable~to~use. + } +\msg_kernel_new:nnnn { regex } { u-missing-rbrace } + { Missing~right~brace~inserted~for~\iow_char:N\\u~escape. } + { + LaTeX~ + \tl_if_empty:xTF {#2} + { reached~the~end~of~the~string~ } + { encountered~an~escaped~alphanumeric~character '\iow_char:N\\#2'~ } + when~parsing~the~argument~of~an~'\iow_char:N\\u\iow_char:N\{...\}'~escape. + } +% \end{macrocode} +% +% In various cases, the result of a \pkg{l3regex} operation can leave us +% with an unbalanced token list, which we must re-balance by adding +% begin-group or end-group character tokens. % \begin{macrocode} \msg_kernel_new:nnnn { regex } { sequence-unbalanced } { Missing~ - \flag_test:NTF \l_regex_group_end_flag + \flag_if_raised:nTF { regex_end } { left~ - \flag_test:NTF \l_regex_group_begin_flag + \flag_if_raised:nTF { regex_begin } { and~right~braces } { brace } } { right~brace } @@ -4591,35 +5198,8 @@ } % \end{macrocode} % +% Messages related to NFA variables. % \begin{macrocode} -\msg_kernel_new:nnnn { regex } { missing-rparen } - { Missing~right~parenthesis~added~in~regular~expression. } - { - LaTeX~was~given~a~regular~expression~with~\int_eval:n{#1}~ - more~left~parenthes\int_compare:nTF{#1=1}{i}{e}s~than~right~ - parenthes\int_compare:nTF{#1=1}{i}{e}s. - } -\msg_kernel_new:nnnn { regex } { extra-rparen } - { Extra~right~parenthesis~ignored~in~regular~expression. } - { - LaTeX~came~across~a~closing~parenthesis~when~no~submatch~group~ - was~open.~The~parenthesis~will~be~ignored. - } -\msg_kernel_new:nnnn { regex } { backwards-range } - { Range~[#1-#2]~out~of~order~in~character~class. } - { - In~ranges~of~characters~[x-y]~appearing~in~character~classes,~ - the~first~character~code~must~not~be~larger~than~the~second.~ - Here,~#1~has~character~code~\int_eval:n {`#1},~while~#2~has~ - character~code~\int_eval:n {`#2}. - } -\msg_kernel_new:nnnn { regex } { unsupported } - { Unsupported~construction~`#1'. } - { - The~construction~`#1'~is~not~supported~by~the~LaTeX~ - regular~expression~module.~Perhaps~some~character~should~ - have~been~escaped? - } \msg_kernel_new:nnnn { regex } { not-nfa } { This~is~not~a~regular~expression~variable. } { @@ -4628,29 +5208,8 @@ is~\\\\ \ \ \ \ \token_to_str:N #1 = \token_to_meaning:N #1 . } -% \end{macrocode} -% -% \begin{macrocode} -% \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 } { 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_kernel_new:nnn { regex } { nfa-misused } + { Automaton~#1 used~incorrectly. } % \end{macrocode} % % \begin{macrocode} @@ -4683,17 +5242,21 @@ % \end{macrocode} % % \begin{macrocode} -\msg_kernel_new:nnn { regex } { nfa-misused } - { Automaton~#1 used~incorrectly. } -% \end{macrocode} -% -% \begin{macrocode} %</package> % \end{macrocode} % % \end{implementation} % % \endinput +%^^A +%^^A \msg_new:nnn { regex } { 4 } +%^^A { Numbers~out~of~order~in~\iow_char:N\{\iow_char\}~quantifier. } +%^^A \msg_new:nnn { regex } { 44 } { Invalid~UTF-8~string } +%^^A \msg_new:nnn { regex } { 46 } +%^^A { Malformed~\iow_char:N\\P~or\iow_char:N\\p~sequence } +%^^A \msg_new:nnn { regex } { 47 } +%^^A { Unknown~property~after~\iow_char:N\\P~or\iow_char:N\\p } +%^^A %^^A NOT IMPLEMENTED %^^A \cx "control-x", where x is any ASCII character %^^A \C one byte, even in UTF-8 mode (best avoided) |