diff options
author | Karl Berry <karl@freefriends.org> | 2018-04-30 22:39:09 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2018-04-30 22:39:09 +0000 |
commit | a28e1bfccd6fe522fcd296426e4d89c7fb4f19b6 (patch) | |
tree | b72347e08575b56fcfed87c4d837b48dcfd1e02a /Master/texmf-dist/source/latex/l3kernel/l3sort.dtx | |
parent | b40c37a9e22b8235ff9c0bc256d00f7af94304c3 (diff) |
l3 (30apr18)
git-svn-id: svn://tug.org/texlive/trunk@47516 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/source/latex/l3kernel/l3sort.dtx')
-rw-r--r-- | Master/texmf-dist/source/latex/l3kernel/l3sort.dtx | 303 |
1 files changed, 152 insertions, 151 deletions
diff --git a/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx b/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx index 10569020f22..45982d61328 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx @@ -41,7 +41,7 @@ % }^^A % } % -% \date{Released 2018/03/05} +% \date{Released 2018-04-30} % % \maketitle % @@ -81,7 +81,7 @@ % % \begin{texnote} % The current implementation is limited to sorting approximately -% $20000$ items ($40000$ in Lua\TeX{}), depending on what other +% $20000$ items ($40000$ in \LuaTeX{}), depending on what other % packages are loaded. % % Internally, the code from \pkg{l3sort} stores items in \tn{toks} @@ -91,6 +91,18 @@ % previously allocated \tn{toks} register is not a problem. % \end{texnote} % +% \begin{function}[added = 2017-02-06]{\sort_return_same:, \sort_return_swapped:} +% \begin{syntax} +% \cs{seq_sort:Nn} \meta{seq~var} +% ~~|{| \ldots{} \cs{sort_return_same:} or \cs{sort_return_swapped:} \ldots{} |}| +% \end{syntax} +% Indicates whether to keep the order or swap the order of two items +% that are compared in the sorting code. Only one of the +% \cs[no-index]{sort_return_\ldots{}} functions should be used by the +% code, according to the results of some tests on the items |#1| and +% |#2| to be compared. +% \end{function} +% % \end{documentation} % % \begin{implementation} @@ -107,6 +119,20 @@ % % \subsection{Variables} % +% \begin{variable}{\g_@@_internal_seq, \g_@@_internal_tl} +% Sorting happens in a group; the result is stored in those global +% variables before being copied outside the group to the proper +% places. For seq and tl this is more efficient than using \cs{use:x} +% (or some \cs{exp_args:NNNx}) to smuggle the definition outside the +% group since \TeX{} does not need to re-read tokens. For clist we +% don't gain anything since the result is converted from seq to clist +% anyways. +% \begin{macrocode} +\seq_new:N \g_@@_internal_seq +\tl_new:N \g_@@_internal_tl +% \end{macrocode} +% \end{variable} +% % \begin{variable} % { % \l_@@_length_int, \l_@@_min_int, \l_@@_top_int, \l_@@_max_int, @@ -232,7 +258,7 @@ % for \tn{loctoks} every time a sorting function is called, as % \pkg{etex} or \pkg{elocalloc} could be loaded. % -% In Con\TeX{}t MkIV the range is from +% In \ConTeXt{} MkIV the range is from % $|\c_syst_last_allocated_toks|+1$ to \cs{c_max_register_int}, and in % MkII it is from $|\lastallocatedtoks|+1$ to \cs{c_max_register_int}. % In all these cases, call \cs{@@_shrink_range:}. The \LaTeX3 format @@ -303,163 +329,124 @@ % % \subsection{Protected user commands} % -% \begin{macro}{\@@_main:NNNnNn} +% \begin{macro}{\@@_main:NNNn} % Sorting happens in three steps. First store items in \tn{toks} % registers ranging from \cs{l_@@_min_int} to $\cs{l_@@_top_int}-1$, -% while checking that the list is not too -% long. If we reach the maximum length, all further -% items are entirely ignored after raising an error. -% Secondly, sort the array of \tn{toks} registers, -% using the user-defined sorting function, |#6|. -% Finally, unpack the \tn{toks} registers (now sorted) -% into a variable of the right type, by \texttt{x}-expanding -% the code in |#4|, specific to each type of list. +% while checking that the list is not too long. If we reach the +% maximum length, that's an error; exit the group. Secondly, sort the +% array of \tn{toks} registers, using the user-defined sorting +% function: \cs{@@_level:} calls \cs{@@_compare:nn} as needed. +% Finally, unpack the \tn{toks} registers (now sorted) into the target +% tl, or into \cs{g_@@_internal_seq} for seq and clist. This is done +% by \cs{@@_seq:NNNNn} and \cs{@@_tl:NNn}. % \begin{macrocode} -\cs_new_protected:Npn \@@_main:NNNnNn #1#2#3#4#5#6 +\cs_new_protected:Npn \@@_main:NNNn #1#2#3#4 { - \group_begin: -%<package> \@@_disable_toksdef: - \@@_compute_range: - \int_set_eq:NN \l_@@_top_int \l_@@_min_int - #2 #5 - { - \if_int_compare:w \l_@@_top_int = \l_@@_max_int - \@@_too_long_error:NNw #3 #5 - \fi: - \tex_toks:D \l_@@_top_int {##1} - \int_incr:N \l_@@_top_int - } - \int_set:Nn \l_@@_length_int - { \l_@@_top_int - \l_@@_min_int } - \cs_set:Npn \@@_compare:nn ##1 ##2 { #6 } - \int_set:Nn \l_@@_block_int { 1 } - \@@_level: - \use:x - { - \group_end: - #1 \exp_not:N #5 {#4} - } +%<package> \@@_disable_toksdef: + \@@_compute_range: + \int_set_eq:NN \l_@@_top_int \l_@@_min_int + #1 #3 + { + \if_int_compare:w \l_@@_top_int = \l_@@_max_int + \@@_too_long_error:NNw #2 #3 + \fi: + \tex_toks:D \l_@@_top_int {##1} + \int_incr:N \l_@@_top_int + } + \int_set:Nn \l_@@_length_int + { \l_@@_top_int - \l_@@_min_int } + \cs_set:Npn \@@_compare:nn ##1 ##2 {#4} + \int_set:Nn \l_@@_block_int { 1 } + \@@_level: } % \end{macrocode} % \end{macro} % -% \begin{macro}{\seq_sort:Nn, \seq_gsort:Nn} -% The first argument to \cs{@@_main:NNNnNn} is the final -% assignment function used, either \cs{tl_set:Nn} or -% \cs{tl_gset:Nn} to control local versus global results. -% The second argument is what mapping function is used when storing -% items to \tn{toks} registers, and the third breaks away from the -% loop. The fourth is used to build back the correct kind of list -% from the contents of the \tn{toks} registers, including the leading -% \cs{s__seq}. Fifth and sixth -% arguments are the variable to sort, and the sorting method -% as inline code. +% \begin{macro}{\tl_sort:Nn, \tl_sort:cn, \tl_gsort:Nn, \tl_gsort:cn} +% \begin{macro}{\@@_tl:NNn} +% \begin{macro}[EXP]{\@@_tl_toks:w} +% Call the main sorting function then unpack \tn{toks} registers +% outside the group into the target token list. The unpacking is done +% by \cs{@@_tl_toks:w}; registers are numbered from \cs{l_@@_min_int} +% to $\cs{l_@@_top_int}-1$. For expansion behaviour we need a couple +% of primitives. The \cs{tl_gclear:N} reduces memory usage. The +% \cs{prg_break_point:} is used by \cs{@@_main:NNNn} when the list is +% too long. % \begin{macrocode} -\cs_new_protected:Npn \seq_sort:Nn +\cs_new_protected:Npn \tl_sort:Nn { \@@_tl:NNn \tl_set_eq:NN } +\cs_generate_variant:Nn \tl_sort:Nn { c } +\cs_new_protected:Npn \tl_gsort:Nn { \@@_tl:NNn \tl_gset_eq:NN } +\cs_generate_variant:Nn \tl_gsort:Nn { c } +\cs_new_protected:Npn \@@_tl:NNn #1#2#3 { - \@@_main:NNNnNn \tl_set:Nn - \seq_map_inline:Nn \seq_map_break:n - { \s__seq \@@_toks:NN \exp_not:N \__seq_item:n } + \group_begin: + \@@_main:NNNn \tl_map_inline:Nn \tl_map_break:n #2 {#3} + \tl_gset:Nx \g_@@_internal_tl + { \@@_tl_toks:w \l_@@_min_int ; } + \group_end: + #1 #2 \g_@@_internal_tl + \tl_gclear:N \g_@@_internal_tl + \prg_break_point: } -\cs_generate_variant:Nn \seq_sort:Nn { c } -\cs_new_protected:Npn \seq_gsort:Nn +\cs_new:Npn \@@_tl_toks:w #1 ; { - \@@_main:NNNnNn \tl_gset:Nn - \seq_map_inline:Nn \seq_map_break:n - { \s__seq \@@_toks:NN \exp_not:N \__seq_item:n } + \if_int_compare:w #1 < \l_@@_top_int + { \tex_the:D \tex_toks:D #1 } + \exp_after:wN \@@_tl_toks:w + \int_value:w \int_eval:n { #1 + 1 } \exp_after:wN ; + \fi: } -\cs_generate_variant:Nn \seq_gsort:Nn { c } % \end{macrocode} % \end{macro} +% \end{macro} +% \end{macro} % -% \begin{macro}{\tl_sort:Nn, \tl_sort:cn, \tl_gsort:Nn, \tl_gsort:cn} -% Again, use \cs{tl_set:Nn} or \cs{tl_gset:Nn} to control -% the scope of the assignment. Mapping through the token -% list is done with \cs{tl_map_inline:Nn}, and producing -% the token list is very similar to sequences, removing -% \cs{__seq_item:n}. +% \begin{macro}{\seq_sort:Nn, \seq_sort:cn, \seq_gsort:Nn, \seq_gsort:cn} +% \begin{macro}{\clist_sort:Nn, \clist_sort:cn, \clist_gsort:Nn, \clist_gsort:cn} +% \begin{macro}{\@@_seq:NNNNn} +% Use the same general framework for seq and clist. Apply the general +% sorting code, then unpack \tn{toks} into \cs{g_@@_internal_seq}. +% Outside the group copy or convert (for clist) the data to the target +% variable. The \cs{seq_gclear:N} reduces memory usage. The +% \cs{prg_break_point:} is used by \cs{@@_main:NNNn} when the list is +% too long. % \begin{macrocode} -\cs_new_protected:Npn \tl_sort:Nn +\cs_new_protected:Npn \seq_sort:Nn + { \@@_seq:NNNNn \seq_map_inline:Nn \seq_map_break:n \seq_set_eq:NN } +\cs_generate_variant:Nn \seq_sort:Nn { c } +\cs_new_protected:Npn \seq_gsort:Nn + { \@@_seq:NNNNn \seq_map_inline:Nn \seq_map_break:n \seq_gset_eq:NN } +\cs_generate_variant:Nn \seq_gsort:Nn { c } +\cs_new_protected:Npn \clist_sort:Nn { - \@@_main:NNNnNn \tl_set:Nn - \tl_map_inline:Nn \tl_map_break:n - { \@@_toks:NN \prg_do_nothing: \prg_do_nothing: } + \@@_seq:NNNNn \clist_map_inline:Nn \clist_map_break:n + \clist_set_from_seq:NN } -\cs_generate_variant:Nn \tl_sort:Nn { c } -\cs_new_protected:Npn \tl_gsort:Nn +\cs_generate_variant:Nn \clist_sort:Nn { c } +\cs_new_protected:Npn \clist_gsort:Nn { - \@@_main:NNNnNn \tl_gset:Nn - \tl_map_inline:Nn \tl_map_break:n - { \@@_toks:NN \prg_do_nothing: \prg_do_nothing: } + \@@_seq:NNNNn \clist_map_inline:Nn \clist_map_break:n + \clist_gset_from_seq:NN } -\cs_generate_variant:Nn \tl_gsort:Nn { c } -% \end{macrocode} -% \end{macro} -% -% \begin{macro} -% {\clist_sort:Nn, \clist_sort:cn, \clist_gsort:Nn, \clist_gsort:cn} -% \begin{macro}{\@@_clist:NNn} -% The case of empty comma-lists is a little bit special as usual, -% and filtered out: there is nothing to sort in that case. -% Otherwise, the input is done with \cs{clist_map_inline:Nn}, -% and the output requires some more elaborate processing than -% for sequences and token lists. The first comma must be removed. -% An item must be wrapped in an extra set of braces if it contains -% either the space or the comma characters. This is taken care of -% by \cs{clist_wrap_item:n}, but \cs{@@_toks:NN} would simply -% feed \cs{tex_the:D} \cs{tex_toks:D} \meta{number} as an -% argument to that function; hence we need to expand this argument -% once to unpack the register. -% \begin{macrocode} -\cs_new_protected:Npn \clist_sort:Nn - { \@@_clist:NNn \tl_set:Nn } -\cs_new_protected:Npn \clist_gsort:Nn - { \@@_clist:NNn \tl_gset:Nn } -\cs_generate_variant:Nn \clist_sort:Nn { c } \cs_generate_variant:Nn \clist_gsort:Nn { c } -\cs_new_protected:Npn \@@_clist:NNn #1#2#3 +\cs_new_protected:Npn \@@_seq:NNNNn #1#2#3#4#5 { - \clist_if_empty:NF #2 - { - \@@_main:NNNnNn #1 - \clist_map_inline:Nn \clist_map_break:n - { - \exp_last_unbraced:Nf \use_none:n - { \@@_toks:NN \exp_args:No \__clist_wrap_item:n } - } - #2 {#3} - } + \group_begin: + \@@_main:NNNn #1 #2 #4 {#5} + \seq_gset_from_inline_x:Nnn \g_@@_internal_seq + { + \int_step_function:nnN + { \l_@@_min_int } { \l_@@_top_int - 1 } + } + { \tex_the:D \tex_toks:D ##1 } + \group_end: + #3 #4 \g_@@_internal_seq + \seq_gclear:N \g_@@_internal_seq + \prg_break_point: } % \end{macrocode} % \end{macro} % \end{macro} -% -% \begin{macro}{\@@_toks:NN, \@@_toks:NNw} -% Unpack the various \tn{toks} registers, from \cs{l_@@_min_int} to -% $\cs{l_@@_top_int}-1$. The functions |#1| and |#2| allow us to treat -% the three data structures in a unified way: -% \begin{itemize} -% \item for sequences, they are \cs{exp_not:N} \cs{__seq_item:n}, -% expanding to the \cs{__seq_item:n} separator, as expected; -% \item for token lists, they expand to nothing; -% \item for comma lists, they expand to \cs{exp_args:No} -% \cs{clist_wrap_item:n}, taking care of unpacking the register -% before letting the undocumented internal \pkg{clist} function -% \cs{clist_wrap_item:n} do the work of putting a comma and possibly -% braces. -% \end{itemize} -% \begin{macrocode} -\cs_new:Npn \@@_toks:NN #1#2 - { \@@_toks:NNw #1 #2 \l_@@_min_int ; } -\cs_new:Npn \@@_toks:NNw #1#2#3 ; - { - \if_int_compare:w #3 < \l_@@_top_int - #1 #2 { \tex_the:D \tex_toks:D #3 } - \exp_after:wN \@@_toks:NNw \exp_after:wN #1 \exp_after:wN #2 - \__int_value:w \__int_eval:w #3 + 1 \exp_after:wN ; - \fi: - } -% \end{macrocode} % \end{macro} % % \subsection{Merge sort} @@ -579,9 +566,17 @@ % once. If neither is called, \cs{@@_return_none_error:} is called. % \begin{macrocode} \cs_new_protected:Npn \sort_return_same: #1 \@@_return_mark:N - { #1 \@@_return_mark:N \@@_return_two_error:w \@@_return_same: } + { + #1 + \@@_return_mark:N + \@@_return_two_error:w \@@_return_same: + } \cs_new_protected:Npn \sort_return_swapped: #1 \@@_return_mark:N - { #1 \@@_return_mark:N \@@_return_two_error:w \@@_return_swapped: } + { + #1 + \@@_return_mark:N + \@@_return_two_error:w \@@_return_swapped: + } \cs_new_protected:Npn \@@_return_mark:N #1 { } \cs_new_protected:Npn \@@_return_none_error: { @@ -827,11 +822,11 @@ % each item. The \texttt{prepare} auxiliary receives the conditional % as~|#1|, the prepared token list so far as~|#2|, the next prepared % item as~|#3|, and the item after that as~|#4|. The loop ends -% when~|#4| contains \cs{__prg_break_point:}, then the +% when~|#4| contains \cs{prg_break_point:}, then the % \texttt{prepare_end} auxiliary finds the prepared token list % as~|#4|. The scene is then set up for \cs{@@_quick_split:NnNn}, % which sorts the prepared list and perform the post action placed -% after \cs{q_mark}, namely removing the trailing \cs{s__stop} and +% after \cs{q_mark}, namely removing the trailing \cs{s_stop} and % \cs{q_stop} and leaving \cs{exp_stop_f:} to stop % \texttt{f}-expansion. % \begin{macrocode} @@ -843,23 +838,23 @@ { \@@_quick_prepare:Nnnn #2 { } { } #1 - { \__prg_break_point: \@@_quick_prepare_end:NNNnw } + { \prg_break_point: \@@_quick_prepare_end:NNNnw } \q_stop } } } \cs_new:Npn \@@_quick_prepare:Nnnn #1#2#3#4 { - \__prg_break: #4 \__prg_break_point: + \prg_break: #4 \prg_break_point: \@@_quick_prepare:Nnnn #1 { #2 #3 } { #1 {#4} } } \cs_new:Npn \@@_quick_prepare_end:NNNnw #1#2#3#4#5 \q_stop { \@@_quick_split:NnNn #4 \@@_quick_end:nnTFNn { } \q_mark { \@@_quick_cleanup:w \exp_stop_f: } - \s__stop \q_stop + \s_stop \q_stop } -\cs_new:Npn \@@_quick_cleanup:w #1 \s__stop \q_stop {#1} +\cs_new:Npn \@@_quick_cleanup:w #1 \s_stop \q_stop {#1} % \end{macrocode} % \end{macro} % \end{macro} @@ -895,31 +890,36 @@ % \begin{macrocode} \cs_new:Npn \@@_quick_split:NnNn #1#2#3#4 { - #3 {#2} {#4} \@@_quick_only_ii:NnnnnNn \@@_quick_only_i:NnnnnNn + #3 {#2} {#4} \@@_quick_only_ii:NnnnnNn + \@@_quick_only_i:NnnnnNn \@@_quick_single_end:nnnwnw { #3 {#4} } { } { } {#2} } \cs_new:Npn \@@_quick_only_i:NnnnnNn #1#2#3#4#5#6#7 { - #6 {#5} {#7} \@@_quick_split_ii:NnnnnNn \@@_quick_only_i:NnnnnNn + #6 {#5} {#7} \@@_quick_split_ii:NnnnnNn + \@@_quick_only_i:NnnnnNn \@@_quick_only_i_end:nnnwnw { #6 {#7} } { #3 #2 } { } {#5} } \cs_new:Npn \@@_quick_only_ii:NnnnnNn #1#2#3#4#5#6#7 { - #6 {#5} {#7} \@@_quick_only_ii:NnnnnNn \@@_quick_split_i:NnnnnNn + #6 {#5} {#7} \@@_quick_only_ii:NnnnnNn + \@@_quick_split_i:NnnnnNn \@@_quick_only_ii_end:nnnwnw { #6 {#7} } { } { #4 #2 } {#5} } \cs_new:Npn \@@_quick_split_i:NnnnnNn #1#2#3#4#5#6#7 { - #6 {#5} {#7} \@@_quick_split_ii:NnnnnNn \@@_quick_split_i:NnnnnNn + #6 {#5} {#7} \@@_quick_split_ii:NnnnnNn + \@@_quick_split_i:NnnnnNn \@@_quick_split_end:nnnwnw { #6 {#7} } { #3 #2 } {#4} {#5} } \cs_new:Npn \@@_quick_split_ii:NnnnnNn #1#2#3#4#5#6#7 { - #6 {#5} {#7} \@@_quick_split_ii:NnnnnNn \@@_quick_split_i:NnnnnNn + #6 {#5} {#7} \@@_quick_split_ii:NnnnnNn + \@@_quick_split_i:NnnnnNn \@@_quick_split_end:nnnwnw { #6 {#7} } {#3} { #4 #2 } {#5} } @@ -989,14 +989,14 @@ % \begin{macro}{\@@_error:} % Bailing out of the sorting code is a bit tricky. It may not be safe % to use a delimited argument, so instead we redefine many -% \pkg{l3sort} commands to be trivial, with \cs{@@_level:} getting rid -% of the final assignment. This error recovery won't work in a group. +% \pkg{l3sort} commands to be trivial, with \cs{@@_level:} jumping to +% the break point. This error recovery won't work in a group. % \begin{macrocode} \cs_new_protected:Npn \@@_error: { \cs_set_eq:NN \@@_merge_blocks_aux: \prg_do_nothing: \cs_set_eq:NN \@@_merge_blocks: \prg_do_nothing: - \cs_set_protected:Npn \@@_level: \use:x ##1 { \group_end: } + \cs_set_protected:Npn \@@_level: { \group_end: \prg_break: } } % \end{macrocode} % \end{macro} @@ -1022,7 +1022,8 @@ { Allocation~of~\iow_char:N\\toks~registers~impossible~while~sorting. } { The~comparison~code~used~for~sorting~a~list~has~attempted~to~ - define~#1~as~a~new~\iow_char:N\\toks~register~using~\iow_char:N\\newtoks~ + define~#1~as~a~new~\iow_char:N\\toks~register~using~ + \iow_char:N\\newtoks~ or~a~similar~command.~The~list~will~not~be~sorted. } %</package> @@ -1048,7 +1049,7 @@ { TeX~has~#2~toks~registers~still~available:~ this~only~allows~to~sort~with~up~to~#3~ - items.~All~extra~items~will~be~deleted. + items.~The~list~will~not~be~sorted. } % \end{macrocode} % \end{macro} |