summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2018-04-30 22:39:09 +0000
committerKarl Berry <karl@freefriends.org>2018-04-30 22:39:09 +0000
commita28e1bfccd6fe522fcd296426e4d89c7fb4f19b6 (patch)
treeb72347e08575b56fcfed87c4d837b48dcfd1e02a /Master/texmf-dist/source/latex/l3kernel/l3sort.dtx
parentb40c37a9e22b8235ff9c0bc256d00f7af94304c3 (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.dtx303
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}