From 2ebe2779edac8cb53ee6d49d058c3ce1aac3f685 Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Tue, 7 Feb 2017 22:42:51 +0000 Subject: l3 (7feb17) git-svn-id: svn://tug.org/texlive/trunk@43162 c570f23f-e606-0410-a88d-b1316a301751 --- .../source/latex/l3experimental/l3sort/l3sort.dtx | 1147 -------------------- .../source/latex/l3experimental/l3sort/l3sort.ins | 56 - .../source/latex/l3experimental/l3str/l3flag.dtx | 6 +- .../source/latex/l3experimental/l3str/l3regex.dtx | 6 +- .../latex/l3experimental/l3str/l3tl-build.dtx | 6 +- .../latex/l3experimental/xgalley/l3galley.dtx | 8 +- Master/texmf-dist/source/latex/l3kernel/expl3.dtx | 6 +- Master/texmf-dist/source/latex/l3kernel/l3.ins | 6 +- .../source/latex/l3kernel/l3candidates.dtx | 40 +- .../texmf-dist/source/latex/l3kernel/l3clist.dtx | 20 +- Master/texmf-dist/source/latex/l3kernel/l3doc.dtx | 17 +- .../source/latex/l3kernel/l3docstrip.dtx | 21 +- .../texmf-dist/source/latex/l3kernel/l3format.ins | 5 +- .../source/latex/l3kernel/l3oldmodules.dtx | 3 +- Master/texmf-dist/source/latex/l3kernel/l3seq.dtx | 20 +- Master/texmf-dist/source/latex/l3kernel/l3sort.dtx | 1100 +++++++++++++++++++ Master/texmf-dist/source/latex/l3kernel/l3tl.dtx | 36 +- .../source/latex/l3packages/l3keys2e/l3keys2e.dtx | 8 +- .../source/latex/l3packages/xfrac/xfrac.dtx | 8 +- .../source/latex/l3packages/xparse/xparse.dtx | 8 +- .../latex/l3packages/xtemplate/xtemplate.dtx | 8 +- 21 files changed, 1238 insertions(+), 1297 deletions(-) delete mode 100644 Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.dtx delete mode 100644 Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.ins create mode 100644 Master/texmf-dist/source/latex/l3kernel/l3sort.dtx (limited to 'Master/texmf-dist/source') diff --git a/Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.dtx b/Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.dtx deleted file mode 100644 index f3f31911d5c..00000000000 --- a/Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.dtx +++ /dev/null @@ -1,1147 +0,0 @@ -% \iffalse -% -%% File l3sort.dtx (C) Copyright 2012,2014-2016 The LaTeX3 Project -% -% It may be distributed and/or modified under the conditions of the -% LaTeX Project Public License (LPPL), either version 1.3c of this -% license or (at your option) any later version. The latest version -% of this license is in the file -% -% http://www.latex-project.org/lppl.txt -% -% This file is part of the "l3experimental bundle" (The Work in LPPL) -% and all files in that bundle must be distributed together. -% -% ----------------------------------------------------------------------- -% -% The development version of the bundle can be found at -% -% https://github.com/latex3/latex3 -% -% for those people who are interested. -% -%<*driver|package> -% The version of expl3 required is tested as early as possible, as -% some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} -% {} -% {% -% \PackageError{l3sort}{Support package l3kernel too old} -% {% -% Please install an up to date version of l3kernel\MessageBreak -% using your TeX package manager or from CTAN.\MessageBreak -% \MessageBreak -% Loading l3sort will abort!% -% }% -% \endinput -% } -\GetIdInfo$Id: l3sort.dtx 6829 2017-01-28 08:52:51Z joseph $ - {L3 Experimental sorting functions} -% -%<*driver> -\documentclass[full]{l3doc} -\usepackage{amsmath} -\begin{document} - \DocInput{\jobname.dtx} -\end{document} -% -% \fi -% -% \title{^^A -% The \pkg{l3sort} package\\ Sorting lists^^A -% \thanks{This file describes v\ExplFileVersion, -% last revised \ExplFileDate.}^^A -% } -% -% \author{^^A -% The \LaTeX3 Project\thanks -% {^^A -% E-mail: -% \href{mailto:latex-team@latex-project.org} -% {latex-team@latex-project.org}^^A -% }^^A -% } -% -% \date{Released \ExplFileDate} -% -% \maketitle -% -% \begin{documentation} -% ^^A todo: ask list about ltplain, mkpattern.tex, GFnotation.tex, texinfo.tex, lollipop-plain, etex-mac.tex, -% -% \section{\pkg{l3sort} documentation} -% -% \LaTeX3 comes with a facility to sort list variables (sequences, -% token lists, or comma-lists) according to some user-defined -% comparison. For instance, -% \begin{verbatim} -% \clist_set:Nn \l_foo_clist { 3 , 01 , -2 , 5 , +1 } -% \clist_sort:Nn \l_foo_clist -% { -% \int_compare:nNnTF { #1 } > { #2 } -% { \sort_reversed: } -% { \sort_ordered: } -% } -% \end{verbatim} -% will result in \cs{l_foo_clist} holding the values -% |{ -2 , 01 , +1 , 3 , 5 }| sorted in non-decreasing order. -% -% The code defining the comparison should perform -% \cs{sort_reversed:} if the two items given as |#1| -% and |#2| are not in the correct order, and otherwise it -% should call \cs{sort_ordered:} to indicate that -% the order of this pair of items should not be changed. -% -% For instance, a \meta{comparison code} consisting only -% of \cs{sort_ordered:} with no test will yield a trivial -% sort: the final order is identical to the original order. -% Conversely, using a \meta{comparison code} consisting only -% of \cs{sort_reversed:} will reverse the list (in a fairly -% inefficient way). -% -% \begin{texnote} -% Internally, the code from \pkg{l3sort} stores items in \tn{toks} -% registers allocated locally. Thus, the \meta{comparison code} -% should not call \tn{newtoks} or other commands that allocate new -% \tn{toks} registers. On the other hand, altering the value of a -% previously allocated \tn{toks} register is not a problem. -% \end{texnote} -% -% \begin{function}{\seq_sort:Nn, \seq_gsort:Nn} -% \begin{syntax} -% \cs{seq_sort:Nn} \meta{sequence} \Arg{comparison code} -% \end{syntax} -% Sorts the items in the \meta{sequence} according to the -% \meta{comparison code}, and assigns the result to -% \meta{sequence}. -% \end{function} -% -% \begin{function}{\tl_sort:Nn, \tl_gsort:Nn} -% \begin{syntax} -% \cs{tl_sort:Nn} \meta{tl var} \Arg{comparison code} -% \end{syntax} -% Sorts the items in the \meta{tl var} according to the -% \meta{comparison code}, and assigns the result to -% \meta{tl var}. -% \end{function} -% -% \begin{function}{\clist_sort:Nn, \clist_gsort:Nn} -% \begin{syntax} -% \cs{clist_sort:Nn} \meta{clist var} \Arg{comparison code} -% \end{syntax} -% Sorts the items in the \meta{clist var} according to the -% \meta{comparison code}, and assigns the result to -% \meta{clist var}. -% \end{function} -% -% {\renewcommand{\thefootnote}{}\footnotetext{\CodedocExplainEXP}} -% -% \begin{function}[EXP]{\tl_sort:nN} -% \begin{syntax} -% \cs{tl_sort:nN} \Arg{token list} \meta{conditional} -% \end{syntax} -% Sorts the items in the \meta{token list}, using the -% \meta{conditional} to compare items, and leaves the result in the -% input stream. The \meta{conditional} should have signature |:nnTF|, -% and return \texttt{true} if the two items being compared should be -% left in the same order, and \texttt{false} if the items should be -% swapped. -% \begin{texnote} -% The result is returned within \cs{exp_not:n}, which means that the -% token list will not expand further when appearing in an -% \texttt{x}-type argument expansion. -% \end{texnote} -% \end{function} -% -% \end{documentation} -% -% \begin{implementation} -% -% \section{\pkg{l3sort} implementation} -% -% \begin{macrocode} -%<*initex|package> -% \end{macrocode} -% -% \begin{macrocode} -%<@@=sort> -% \end{macrocode} -% -% \begin{macrocode} -%<*package> -\ProvidesExplPackage - {\ExplFileName}{\ExplFileDate}{\ExplFileVersion}{\ExplFileDescription} -% -% \end{macrocode} -% -% \subsection{Variables} -% -% \begin{variable} -% { -% \l_@@_length_int, \l_@@_min_int, \l_@@_top_int, \l_@@_max_int, -% \l_@@_true_max_int -% } -% The sequence has \cs{l_@@_length_int} items and is stored from -% \cs{l_@@_min_int} to $\cs{l_@@_top_int}-1$. While reading the -% sequence in memory, we check that \cs{l_@@_top_int} remains at most -% \cs{l_@@_max_int}, precomputed by \cs{@@_compute_range:}. That -% bound is such that the merge sort will only use \tn{toks} registers -% less than \cs{l_@@_true_max_int}, namely those that have not been -% allocated for use in other code: the user's comparison code could -% alter these. -% \begin{macrocode} -\int_new:N \l_@@_length_int -\int_new:N \l_@@_min_int -\int_new:N \l_@@_top_int -\int_new:N \l_@@_max_int -\int_new:N \l_@@_true_max_int -% \end{macrocode} -% \end{variable} -% -% \begin{variable}{\l_@@_block_int} -% Merge sort is done in several passes. In each pass, blocks of size -% \cs{l_@@_block_int} are merged in pairs. The block size starts -% at $1$, and, for a length in the range $[2^k+1,2^{k+1}]$, reaches -% $2^{k}$ in the last pass. -% \begin{macrocode} -\int_new:N \l_@@_block_int -% \end{macrocode} -% \end{variable} -% -% \begin{variable}{\l_@@_begin_int} -% \begin{variable}{\l_@@_end_int} -% When merging two blocks, \cs{l_@@_begin_int} marks the lowest -% index in the two blocks, and \cs{l_@@_end_int} marks the -% highest index, plus $1$. -% \begin{macrocode} -\int_new:N \l_@@_begin_int -\int_new:N \l_@@_end_int -% \end{macrocode} -% \end{variable} -% \end{variable} -% -% \begin{variable}{\l_@@_A_int} -% \begin{variable}{\l_@@_B_int} -% \begin{variable}{\l_@@_C_int} -% When merging two blocks (whose end-points are \texttt{beg} -% and \texttt{end}), $A$ starts from the high end of the low -% block, and decreases until reaching \texttt{beg}. The index -% $B$ starts from the top of the range and marks the register -% in which a sorted item should be put. Finally, $C$ points -% to the copy of the high block in the interval of registers -% starting at \cs{l_@@_length_int}, upwards. $C$ starts -% from the upper limit of that range. -% \begin{macrocode} -\int_new:N \l_@@_A_int -\int_new:N \l_@@_B_int -\int_new:N \l_@@_C_int -% \end{macrocode} -% \end{variable} -% \end{variable} -% \end{variable} -% -% \subsection{Finding available \tn{toks} registers} -% -% \begin{macro}[int]{\@@_shrink_range:} -% \begin{macro}[aux]{\@@_shrink_range_loop:} -% After \cs{@@_compute_range:} (defined below) determines that -% \tn{toks} registers between \cs{l_@@_min_int} (included) and -% \cs{l_@@_true_max_int} (excluded) have not yet been assigned, -% \cs{@@_shrink_range:} computes \cs{l_@@_max_int} to reflect the need -% for a buffer when merging blocks in the merge sort. Given -% $2^{n}\leq A\leq 2^{n}+2^{n-1}$ registers we can sort $\lfloor -% A/2\rfloor+2^{n-2}$ items while if we have $2^{n}+2^{n-1}\leq A\leq -% 2^{n+1}$ registers we can sort $A-2^{n-1}$ items. We first find out -% a power $2^{n}$ such that $2^{n}\leq A\leq 2^{n+1}$ by repeatedly -% halving \cs{l_@@_block_int}, starting at $2^{15}$ or $2^{14}$ namely -% half the total number of registers, then we use the formulas and set -% \cs{l_@@_max_int}. -% \begin{macrocode} -\cs_new_protected:Npn \@@_shrink_range: - { - \int_set:Nn \l_@@_A_int - { \l_@@_true_max_int - \l_@@_min_int + \c_one } - \int_set:Nn \l_@@_block_int { \c_max_register_int / \c_two } - \@@_shrink_range_loop: - \int_set:Nn \l_@@_max_int - { - \int_compare:nNnTF - { \l_@@_block_int * \c_three / \c_two } > \l_@@_A_int - { - \l_@@_min_int - + ( \l_@@_A_int - \c_one ) / \c_two - + \l_@@_block_int / \c_four - - \c_one - } - { \l_@@_true_max_int - \l_@@_block_int / \c_two } - } - } -\cs_new_protected:Npn \@@_shrink_range_loop: - { - \if_int_compare:w \l_@@_A_int < \l_@@_block_int - \tex_divide:D \l_@@_block_int \c_two - \exp_after:wN \@@_shrink_range_loop: - \fi: - } -% \end{macrocode} -% \end{macro} -% \end{macro} -% -% \begin{macro}[int]{\@@_compute_range:, \@@_redefine_compute_range:} -% \begin{variable}{\c_@@_max_length_int} -% First find out what \tn{toks} have not yet been assigned. There are -% many cases. In \LaTeXe{} with no package, available \tn{toks} range -% from $\tn{count}15+1$ to \cs{c_max_register_int} included (this was -% not altered despite the 2015 changes). When \tn{loctoks} is -% defined, namely in plain (e)\TeX{}, or when the package \pkg{etex} -% is loaded in \LaTeXe{}, redefine \cs{@@_compute_range:} to use the -% range $\tn{count}265$ to $\tn{count}275-1$. The \pkg{elocalloc} -% package also defines \tn{loctoks} but uses yet another number for -% the upper bound, namely \cs{e@alloc@top} (minus one). We must check -% 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 -% $|\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 -% mode is easiest: no \tn{toks} are ever allocated so available -% \tn{toks} range from $0$ to \cs{c_max_register_int} and we -% precompute the result of \cs{@@_shrink_range:}. -% \begin{macrocode} -%<*package> -\cs_new_protected:Npn \@@_compute_range: - { - \int_set:Nn \l_@@_min_int { \tex_count:D 15 + \c_one } - \int_set:Nn \l_@@_true_max_int { \c_max_register_int + \c_one } - \@@_shrink_range: - \if_meaning:w \loctoks \tex_undefined:D \else: - \if_meaning:w \loctoks \scan_stop: \else: - \@@_redefine_compute_range: - \@@_compute_range: - \fi: - \fi: - } -\cs_new_protected:Npn \@@_redefine_compute_range: - { - \cs_if_exist:cTF { ver@elocalloc.sty } - { - \cs_gset_protected:Npn \@@_compute_range: - { - \int_set:Nn \l_@@_min_int { \tex_count:D 265 } - \int_set_eq:NN \l_@@_true_max_int \e@alloc@top - \@@_shrink_range: - } - } - { - \cs_gset_protected:Npn \@@_compute_range: - { - \int_set:Nn \l_@@_min_int { \tex_count:D 265 } - \int_set:Nn \l_@@_true_max_int { \tex_count:D 275 } - \@@_shrink_range: - } - } - } -\cs_if_exist:NT \loctoks { \@@_redefine_compute_range: } -\tl_map_inline:nn { \lastallocatedtoks \c_syst_last_allocated_toks } - { - \cs_if_exist:NT #1 - { - \cs_gset_protected:Npn \@@_compute_range: - { - \int_set:Nn \l_@@_min_int { #1 + \c_one } - \int_set:Nn \l_@@_true_max_int { \c_max_register_int + \c_one } - \@@_shrink_range: - } - } - } -% -%<*initex> -\int_const:Nn \c_@@_max_length_int - { ( \c_max_register_int + 1 ) * 3 / 4 } -\cs_new_protected:Npn \@@_compute_range: - { - \int_set_eq:NN \l_@@_min_int \c_zero - \int_set:Nn \l_@@_true_max_int { \c_max_register_int + \c_one } - \int_set_eq:NN \l_@@_max_int \c_@@_max_length_int - } -% -% \end{macrocode} -% \end{variable} -% \end{macro} -% -% \subsection{Protected user commands} -% -% \begin{macro}[int]{\@@_main:NNNnNn} -% 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. -% \begin{macrocode} -\cs_new_protected:Npn \@@_main:NNNnNn #1#2#3#4#5#6 - { - \group_begin: -% \@@_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} - \tex_advance:D \l_@@_top_int \c_one - } - \int_set:Nn \l_@@_length_int - { \l_@@_top_int - \l_@@_min_int } - \cs_set:Npn \@@_compare:nn ##1 ##2 { #6 } - \int_set_eq:NN \l_@@_block_int \c_one - \@@_level: - \use:x - { - \group_end: - #1 \exp_not:N #5 {#4} - } - } -% \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{macrocode} -\cs_new_protected:Npn \seq_sort:Nn - { - \@@_main:NNNnNn \tl_set:Nn - \seq_map_inline:Nn \seq_map_break:n - { \s__seq \@@_toks:NN \exp_not:N \__seq_item:n } - } -\cs_new_protected:Npn \seq_gsort:Nn - { - \@@_main:NNNnNn \tl_gset:Nn - \seq_map_inline:Nn \seq_map_break:n - { \s__seq \@@_toks:NN \exp_not:N \__seq_item:n } - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}{\tl_sort:Nn, \tl_gsort:Nn} -% 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{macrocode} -\cs_new_protected:Npn \tl_sort:Nn - { - \@@_main:NNNnNn \tl_set:Nn - \tl_map_inline:Nn \tl_map_break:n - { \@@_toks:NN \prg_do_nothing: \prg_do_nothing: } - } -\cs_new_protected:Npn \tl_gsort:Nn - { - \@@_main:NNNnNn \tl_gset:Nn - \tl_map_inline:Nn \tl_map_break:n - { \@@_toks:NN \prg_do_nothing: \prg_do_nothing: } - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}{\clist_sort:Nn, \clist_gsort:Nn} -% \begin{macro}[aux]{\@@_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_new_protected:Npn \@@_clist:NNn #1#2#3 - { - \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} - } - } -% \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 + \c_one \exp_after:wN ; - \fi: - } -% \end{macrocode} -% \end{macro} -% -% \subsection{Merge sort} -% -% \begin{macro}[int]{\@@_level:} -% This function is called once blocks of size \cs{l_@@_block_int} -% (initially $1$) are each sorted. If the whole list fits in one -% block, then we are done (this also takes care of the case of an -% empty list or a list with one item). Otherwise, go through pairs -% of blocks starting from $0$, then double the block size, and repeat. -% \begin{macrocode} -\cs_new_protected:Npn \@@_level: - { - \if_int_compare:w \l_@@_block_int < \l_@@_length_int - \l_@@_end_int \l_@@_min_int - \@@_merge_blocks: - \tex_advance:D \l_@@_block_int \l_@@_block_int - \exp_after:wN \@@_level: - \fi: - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}[int]{\@@_merge_blocks:} -% This function is called to merge a pair of blocks, starting at -% the last value of \cs{l_@@_end_int} (end-point of the previous -% pair of blocks). If shifting by one block to the right we reach -% the end of the list, then this pass has ended: the end of the -% list is sorted already. Otherwise, store the result of that shift in $A$, -% which will index the first block starting from the top end. -% Then locate the end-point (maximum) of the second block: shift -% \texttt{end} upwards by one more block, but keeping it -% $\leq\texttt{top}$. Copy this upper block of \tn{toks} -% registers in registers above \texttt{length}, indexed by $C$: -% this is covered by \cs{@@_copy_block:}. Once this is done we -% are ready to do the actual merger using \cs{@@_merge_blocks_aux:}, -% after shifting $A$, $B$ and $C$ so that they point to the largest -% index in their respective ranges rather than pointing just beyond -% those ranges. Of course, once that pair of blocks is merged, -% move on to the next pair. -% \begin{macrocode} -\cs_new_protected:Npn \@@_merge_blocks: - { - \l_@@_begin_int \l_@@_end_int - \tex_advance:D \l_@@_end_int \l_@@_block_int - \if_int_compare:w \l_@@_end_int < \l_@@_top_int - \l_@@_A_int \l_@@_end_int - \tex_advance:D \l_@@_end_int \l_@@_block_int - \if_int_compare:w \l_@@_end_int > \l_@@_top_int - \l_@@_end_int \l_@@_top_int - \fi: - \l_@@_B_int \l_@@_A_int - \l_@@_C_int \l_@@_top_int - \@@_copy_block: - \tex_advance:D \l_@@_A_int - \c_one - \tex_advance:D \l_@@_B_int - \c_one - \tex_advance:D \l_@@_C_int - \c_one - \exp_after:wN \@@_merge_blocks_aux: - \exp_after:wN \@@_merge_blocks: - \fi: - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}[int]{\@@_copy_block:} -% We wish to store a copy of the \enquote{upper} block of -% \tn{toks} registers, ranging between the initial value of -% \cs{l_@@_B_int} (included) and \cs{l_@@_end_int} -% (excluded) into a new range starting at the initial value -% of \cs{l_@@_C_int}, namely \cs{l_@@_top_int}. -% \begin{macrocode} -\cs_new_protected:Npn \@@_copy_block: - { - \tex_toks:D \l_@@_C_int \tex_toks:D \l_@@_B_int - \tex_advance:D \l_@@_C_int \c_one - \tex_advance:D \l_@@_B_int \c_one - \if_int_compare:w \l_@@_B_int = \l_@@_end_int - \use_i:nn - \fi: - \@@_copy_block: - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}[aux]{\@@_merge_blocks_aux:} -% At this stage, the first block starts at \cs{l_@@_begin_int}, -% and ends at \cs{l_@@_A_int}, and the second block starts at -% \cs{l_@@_top_int} and ends at \cs{l_@@_C_int}. The result -% of the merger is stored at positions indexed by \cs{l_@@_B_int}, -% which starts at $\cs{l_@@_end_int}-1$ and decreases down to -% \cs{l_@@_begin_int}, covering the full range of the two blocks. -% In other words, we are building the merger starting with the -% largest values. -% The comparison function is defined to return either -% \texttt{reversed} or \texttt{ordered}. Of course, this -% means the arguments need to be given in the order they -% appear originally in the list. -% \begin{macrocode} -\cs_new_protected:Npn \@@_merge_blocks_aux: - { - \exp_after:wN \@@_compare:nn \exp_after:wN - { \tex_the:D \tex_toks:D \exp_after:wN \l_@@_A_int \exp_after:wN } - \exp_after:wN { \tex_the:D \tex_toks:D \l_@@_C_int } - \prg_do_nothing: - \@@_return_mark:N - \@@_return_mark:N - \@@_return_none_error: - } -% \end{macrocode} -% \end{macro} -% -% -% \begin{macro}{\sort_ordered:, \sort_reversed:} -% \begin{macro}[aux]{\@@_return_mark:N} -% \begin{macro}[aux]{\@@_return_none_error:, \@@_return_two_error:w} -% The marker removes one token. Each comparison should call -% \cs{sort_ordered:} or \cs{sort_reversed:} exactly -% once. If neither is called, \cs{@@_return_none_error:} is called. -% \begin{macrocode} -\cs_new_protected:Npn \sort_ordered: #1 \@@_return_mark:N - { #1 \@@_return_mark:N \@@_return_two_error:w \@@_ordered: } -\cs_new_protected:Npn \sort_reversed: #1 \@@_return_mark:N - { #1 \@@_return_mark:N \@@_return_two_error:w \@@_return_reversed: } -\cs_new_protected:Npn \@@_return_mark:N #1 { } -\cs_new_protected:Npn \@@_return_none_error: - { - \__msg_kernel_error:nnxx { sort } { return-none } - { \tex_the:D \tex_toks:D \l_@@_A_int } - { \tex_the:D \tex_toks:D \l_@@_C_int } - \@@_ordered: - } -\cs_new_protected:Npn \@@_return_two_error:w - #1 \@@_return_none_error: - { \__msg_kernel_error:nn { sort } { return-two } } -% \end{macrocode} -% \end{macro} -% \end{macro} -% \end{macro} -% -% \begin{macro}[aux]{\@@_ordered:} -% If the comparison function returns \texttt{ordered}, -% then the second argument fed to \cs{@@_compare:nn} -% should remain to the right of the other one. Since -% we build the merger starting from the right, we copy -% that \tn{toks} register into the allotted range, then -% shift the pointers $B$ and $C$, and go on to do one -% more step in the merger, unless the second block has -% been exhausted: then the remainder of the first block -% is already in the correct registers and we are done -% with merging those two blocks. -% \begin{macrocode} -\cs_new_protected:Npn \@@_ordered: - { - \tex_toks:D \l_@@_B_int \tex_toks:D \l_@@_C_int - \tex_advance:D \l_@@_B_int - \c_one - \tex_advance:D \l_@@_C_int - \c_one - \if_int_compare:w \l_@@_C_int < \l_@@_top_int - \use_i:nn - \fi: - \@@_merge_blocks_aux: - } -% \end{macrocode} -% \end{macro} -% \end{macro} -% -% \begin{macro}[aux]{\@@_return_reversed:} -% If the comparison function returns \texttt{reversed}, -% then the next item to add to the merger is the first -% argument, contents of the \tn{toks} register $A$. -% Then shift the pointers $A$ and $B$ to the left, and -% go for one more step for the merger, unless the left -% block was exhausted ($A$ goes below the threshold). -% In that case, all remaining \tn{toks} registers in -% the second block, indexed by $C$, are copied -% to the merger by \cs{@@_merge_blocks_end:}. -% \begin{macrocode} -\cs_new_protected:Npn \@@_return_reversed: - { - \tex_toks:D \l_@@_B_int \tex_toks:D \l_@@_A_int - \tex_advance:D \l_@@_B_int - \c_one - \tex_advance:D \l_@@_A_int - \c_one - \if_int_compare:w \l_@@_A_int < \l_@@_begin_int - \@@_merge_blocks_end: \use_i:nn - \fi: - \@@_merge_blocks_aux: - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}[aux]{\@@_merge_blocks_end:} -% This function's task is to copy the \tn{toks} registers -% in the block indexed by $C$ to the merger indexed by $B$. -% The end can equally be detected by checking when $B$ reaches -% the threshold \texttt{begin}, or when $C$ reaches -% \texttt{top}. -% \begin{macrocode} -\cs_new_protected:Npn \@@_merge_blocks_end: - { - \tex_toks:D \l_@@_B_int \tex_toks:D \l_@@_C_int - \tex_advance:D \l_@@_B_int - \c_one - \tex_advance:D \l_@@_C_int - \c_one - \if_int_compare:w \l_@@_B_int < \l_@@_begin_int - \use_i:nn - \fi: - \@@_merge_blocks_end: - } -% \end{macrocode} -% \end{macro} -% -% \subsection{Expandable sorting} -% -% Sorting expandably is very different from sorting and assigning to a -% variable. Since tokens cannot be stored, they must remain in the -% input stream, and be read through at every step. It is thus -% necessarily much slower (at best $O(n^2\ln n)$) than non-expandable -% sorting functions ($O(n\ln n)$). -% -% A prototypical version of expandable quicksort is as follows. If the -% argument has no item, return nothing, otherwise partition, using the -% first item as a pivot (argument |#4| of \cs{@@:nnNnn}). The -% arguments of \cs{@@:nnNnn} are 1.~items less than |#4|, 2.~items -% greater or equal to |#4|, 3.~comparison, 4.~pivot, 5.~next item to -% test. If |#5| is the tail of the list, call \cs{tl_sort:nN} on |#1| -% and on |#2|, placing |#4| in between; |\use:ff| expands the parts to -% make \cs{tl_sort:nN} \texttt{f}-expandable. Otherwise, compare |#4| -% and |#5| using |#3|. If they are ordered, place |#5| amongst the -% \enquote{greater} items, otherwise amongst the \enquote{lesser} items, -% and continue partitioning. -% \begin{verbatim} -% \cs_new:Npn \tl_sort:nN #1#2 -% { -% \tl_if_blank:nF {#1} -% { -% \__sort:nnNnn { } { } #2 -% #1 \q_recursion_tail \q_recursion_stop -% } -% } -% \cs_new:Npn \__sort:nnNnn #1#2#3#4#5 -% { -% \quark_if_recursion_tail_stop_do:nn {#5} -% { \use:ff { \tl_sort:nN {#1} #3 {#4} } { \tl_sort:nN {#2} #3 } } -% #3 {#4} {#5} -% { \__sort:nnNnn {#1} { #2 {#5} } #3 {#4} } -% { \__sort:nnNnn { #1 {#5} } {#2} #3 {#4} } -% } -% \cs_generate_variant:Nn \use:nn { ff } -% \end{verbatim} -% There are quite a few optimizations available here: the code below is -% less legible, but more than twice as fast. -% -% In the simple version of the code, \cs{@@:nnNnn} is called -% \(O(n\ln n)\) times on average (the number of comparisons required by -% the quicksort algorithm). Hence most of our focus will be on -% optimizing that function. -% -% The first speed up is to avoid testing for the end of the list at -% every call to \cs{@@:nnNnn}. For this, the list is prepared by -% changing each \meta{item} of the original token list into -% \meta{command} \Arg{item}, just like sequences are stored. We arrange -% things such that the \meta{command} is the \meta{conditional} provided -% by the user: the loop over the \meta{prepared tokens} then looks like -% \begin{quote} -% \ttfamily -% \cs{cs_new:Npn}~\cs{@@_loop:wNn}~\ldots{}~|#6#7|\\ -% ~~|{|\\ -% ~~~~|#6|~\Arg{pivot}~|{#7}|~\meta{loop big}~\meta{loop small}\\ -% ~~~~~~\meta{extra arguments}\\ -% ~~|}|\\ -% \cs{@@_loop:wNn}~\ldots{}~\meta{prepared tokens}\\ -% ~~\meta{end-loop}~|{}|~|\q_stop| -% \end{quote} -% In this example, which matches the structure of -% \cs{@@_quick_split_i:NnnnnNn} and a few other functions below, the -% \cs{@@_loop:wNn} auxiliary normally receives the user's -% \meta{conditional} as~|#6| and an \meta{item} as~|#7|. This is -% compared to the \meta{pivot} (the argument~|#5|, not shown here), and -% the \meta{conditional} leaves the \meta{loop big} or \meta{loop small} -% auxiliary, which both have the same form as \cs{@@_loop:wNn}, -% receiving the next pair \meta{conditional} \Arg{item} as |#6| -% and~|#7|. At the end, |#6| is the \meta{end-loop} function, which -% terminates the loop. -% -% The second speed up is to minimize the duplicated tokens between the -% \texttt{true} and \texttt{false} branches of the conditional. For -% this, we introduce two versions of \cs{@@:nnNnn}, which receive -% the new item as~|#1| and place it either into the list~|#2| of items -% less than the pivot~|#4| or into the list~|#3| of items greater or -% equal to the pivot. -% \begin{verbatim} -% \cs_new:Npn \__sort_i:nnnnNn #1#2#3#4#5#6 -% { -% #5 {#4} {#6} \__sort_ii:nnnnNn \__sort_i:nnnnNn -% {#6} { #2 {#1} } {#3} {#4} -% } -% \cs_new:Npn \__sort_ii:nnnnNn #1#2#3#4#5#6 -% { -% #5 {#4} {#6} \__sort_ii:nnnnNn \__sort_i:nnnnNn -% {#6} {#2} { #3 {#1} } {#4} -% } -% \end{verbatim} -% Note that the two functions have the form of \cs{@@_loop:wNn} above, -% receiving as~|#5| the conditional or a function to end the loop. In -% fact, the lists~|#2| and~|#3| must be made of pairs \meta{conditional} -% \Arg{item}, so we have to replace~|{#6}| above by |{|~|#5|~|{#6}|~|}|, -% and |{#1}|~by~|#1|. The actual functions have one more argument, so -% all argument numbers are shifted compared to this code. -% -% The third speed up is to avoid |\use:ff| using a continuation-passing -% style: \cs{@@_quick_split:NnNn} expects a list followed by -% \cs{q_mark} \Arg{code}, and expands to \meta{code} \meta{sorted list}. -% Sorting the two parts of the list around the pivot is done with -% \begin{quote} -% \ttfamily -% \cs{@@_quick_split:NnNn} |#2| \ldots{} \cs{q_mark}\\ -% ~~|{|\\ -% ~~~~\cs{@@_quick_split:NnNn} |#1| \ldots{} \cs{q_mark} \Arg{code}\\ -% ~~~~\Arg{pivot}\\ -% ~~|}| -% \end{quote} -% Items which are larger than the \meta{pivot} are sorted, then placed -% after code that sorts the smaller items, and after the (braced) -% \meta{pivot}. -% -% The fourth speed up is avoid the recursive call to \cs{tl_sort:nN} -% with an empty first argument. For this, we introduce functions -% similar to the \cs{@@_i:nnnnNn} of the last example, but aware of -% whether the list of \meta{conditional} \Arg{item} read so far that are -% less than the pivot, and the list of those greater or equal, are empty -% or not: see \cs{@@_quick_split:NnNn} and functions defined below. -% Knowing whether the lists are empty or not is useless if we do not use -% distinct ending codes as appropriate. The splitting auxiliaries -% communicate to the \meta{end-loop} function (that is initially placed -% after the ``prepared'' list) by placing a specific ending function, -% ignored when looping, but useful at the end. In fact, the -% \meta{end-loop} function does nothing but place the appropriate ending -% function in front of all its arguments. The ending functions take -% care of sorting non-empty sublists, placing the pivot in between, and -% the continuation before. -% -% The final change in fact slows down the code a little, but is required -% to avoid memory issues: schematically, when \TeX{} encounters -% \begin{verbatim} -% \use:n { \use:n { \use:n { ... } ... } ... } -% \end{verbatim} -% the argument of the first \cs{use:n} is not completely read by the -% second \cs{use:n}, hence must remain in memory; then the argument of -% the second \cs{use:n} is not completely read when grabbing the -% argument of the third \cs{use:n}, hence must remain in memory, and so -% on. The memory consumption grows quadratically with the number of -% nested \cs{use:n}. In practice, this means that we must read -% everything until a trailing \cs{q_stop} once in a while, otherwise -% sorting lists of more than a few thousand items would exhaust a -% typical \TeX{}'s memory. -% -% \begin{macro}[EXP]{\tl_sort:nN} -% \begin{macro}[aux, EXP] -% { -% \@@_quick_prepare:Nnnn, -% \@@_quick_prepare_end:NNNnw, -% \@@_quick_cleanup:w -% } -% The code within the \cs{exp_not:f} sorts the list, leaving in most -% cases a leading \cs{exp_not:f}, which stops the expansion, letting -% the result be return within \cs{exp_not:n}. We filter out the case -% of a list with no item, which would otherwise cause problems. Then -% prepare the token list~|#1| by inserting the conditional~|#2| before -% 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 -% \texttt{prepare_end} auxiliary finds the prepared token list -% as~|#4|. The scene is then set up for \cs{@@_quick_split:NnNn}, -% which will sort the prepared list and perform the post action placed -% 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} -\cs_new:Npn \tl_sort:nN #1#2 - { - \exp_not:f - { - \tl_if_blank:nF {#1} - { - \@@_quick_prepare:Nnnn #2 { } { } - #1 - { \__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: - \@@_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 - } -\cs_new:Npn \@@_quick_cleanup:w #1 \s__stop \q_stop {#1} -% \end{macrocode} -% \end{macro} -% \end{macro} -% -% \begin{macro}[EXP, aux] -% { -% \@@_quick_split:NnNn, -% \@@_quick_only_i:NnnnnNn, -% \@@_quick_only_ii:NnnnnNn, -% \@@_quick_split_i:NnnnnNn, -% \@@_quick_split_ii:NnnnnNn -% } -% The \texttt{only_i}, \texttt{only_ii}, \texttt{split_i} and -% \texttt{split_ii} auxiliaries receive a useless first argument, the -% new item~|#2| (that they append to either one of the next two -% arguments), the list~|#3| of items less than the pivot, bigger -% items~|#4|, the pivot~|#5|, a \meta{function}~|#6|, and an -% item~|#7|. The \meta{function} is the user's \meta{conditional} -% except at the end of the list where it is -% \cs{@@_quick_end:nnTFNn}. The comparison is applied to the -% \meta{pivot} and the \meta{item}, and calls the \texttt{only_i} or -% \texttt{split_i} auxiliaries if the \meta{item} is smaller, and the -% \texttt{only_ii} or \texttt{split_ii} auxiliaries otherwise. In -% both cases, the next auxiliary goes to work right away, with no -% intermediate expansion that would slow down operations. Note that -% the argument~|#2| left for the next call has the form -% \meta{conditional} \Arg{item}, so that the lists~|#3| and~|#4| keep -% the right form to be fed to the next sorting function. -% The \texttt{split} auxiliary differs from these in that it is -% missing three of the arguments, which would be empty, and its first -% argument is always the user's \meta{conditional} rather than an -% ending function. -% \begin{macrocode} -\cs_new:Npn \@@_quick_split:NnNn #1#2#3#4 - { - #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 - \@@_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 - \@@_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 - \@@_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 - \@@_quick_split_end:nnnwnw - { #6 {#7} } {#3} { #4 #2 } {#5} - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}[EXP, aux] -% { -% \@@_quick_end:nnTFNn, -% \@@_quick_single_end:nnnwnw, -% \@@_quick_only_i_end:nnnwnw, -% \@@_quick_only_ii_end:nnnwnw, -% \@@_quick_split_end:nnnwnw, -% } -% The \cs{@@_quick_end:nnTFNn} appears instead of the user's -% conditional, and receives as its arguments the pivot~|#1|, a fake -% item~|#2|, a \texttt{true} and a \texttt{false} branches |#3| -% and~|#4|, followed by an ending function~|#5| (one of the four -% auxiliaries here) and another copy~|#6| of the fake item. All those -% are discarded except the function~|#5|. This function receives -% lists~|#1| and~|#2| of items less than or greater than the -% pivot~|#3|, then a continuation code~|#5| just after \cs{q_mark}. -% To avoid a memory problem described earlier, all of the ending -% functions read~|#6| until \cs{q_stop} and place~|#6| back into the -% input stream. When the lists |#1| and~|#2| are empty, the -% \texttt{single} auxiliary simply places the continuation~|#5| before -% the pivot~|{#3}|. When |#2|~is empty, |#1|~is sorted and placed -% before the pivot~|{#3}|, taking care to feed the continuation~|#5| -% as a continuation for the function sorting~|#1|. When |#1|~is -% empty, |#2|~is sorted, and the continuation argument is used to -% place the continuation~|#5| and the pivot~|{#3}| before the sorted -% result. Finally, when both lists are non-empty, items larger than -% the pivot are sorted, then items less than the pivot, and the -% continuations are done in such a way to place the pivot in between. -% \begin{macrocode} -\cs_new:Npn \@@_quick_end:nnTFNn #1#2#3#4#5#6 {#5} -\cs_new:Npn \@@_quick_single_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop - { #5 {#3} #6 \q_stop } -\cs_new:Npn \@@_quick_only_i_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop - { - \@@_quick_split:NnNn #1 - \@@_quick_end:nnTFNn { } \q_mark {#5} - {#3} - #6 \q_stop - } -\cs_new:Npn \@@_quick_only_ii_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop - { - \@@_quick_split:NnNn #2 - \@@_quick_end:nnTFNn { } \q_mark { #5 {#3} } - #6 \q_stop - } -\cs_new:Npn \@@_quick_split_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop - { - \@@_quick_split:NnNn #2 \@@_quick_end:nnTFNn { } \q_mark - { - \@@_quick_split:NnNn #1 - \@@_quick_end:nnTFNn { } \q_mark {#5} - {#3} - } - #6 \q_stop - } -% \end{macrocode} -% \end{macro} -% -% \subsection{Messages} -% -% \begin{macro}[aux]{\@@_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. -% \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: } - } -% \end{macrocode} -% \end{macro} -% -% \begin{macro}[aux]{\@@_disable_toksdef:, \@@_disabled_toksdef:n} -% While sorting, \tn{toksdef} is locally disabled to prevent users -% from using \tn{newtoks} or similar commands in their comparison -% code: the \tn{toks} registers that would be assigned are in use by -% \pkg{l3sort}. In format mode, none of this is needed since there is -% no \tn{toks} allocator. -% \begin{macrocode} -%<*package> -\cs_new_protected:Npn \@@_disable_toksdef: - { \cs_set_eq:NN \toksdef \@@_disabled_toksdef:n } -\cs_new_protected:Npn \@@_disabled_toksdef:n #1 - { - \__msg_kernel_error:nnx { sort } { toksdef } - { \token_to_str:N #1 } - \@@_error: - \tex_toksdef:D #1 - } -\__msg_kernel_new:nnnn { sort } { toksdef } - { 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~ - or~a~similar~command.~The~list~will~not~be~sorted. - } -% -% \end{macrocode} -% \end{macro} -% -% \begin{macro}[aux]{\@@_too_long_error:NNw} -% When there are too many items in a sequence, this is an error, and -% we clean up properly the mapping over items in the list: break using -% the type-specific breaking function |#1|. -% \begin{macrocode} -\cs_new_protected:Npn \@@_too_long_error:NNw #1#2 \fi: - { - \fi: - \__msg_kernel_error:nnxxx { sort } { too-large } - { \token_to_str:N #2 } - { \int_eval:n { \l_@@_true_max_int - \l_@@_min_int } } - { \int_eval:n { \l_@@_top_int - \l_@@_min_int } } - #1 \@@_error: - } -\__msg_kernel_new:nnnn { sort } { too-large } - { The~list~#1~is~too~long~to~be~sorted~by~TeX. } - { - TeX~has~#2~toks~registers~still~available:~ - this~only~allows~to~sort~with~up~to~#3~ - items.~All~extra~items~will~be~deleted. - } -% \end{macrocode} -% \end{macro} -% -% \begin{macrocode} -\__msg_kernel_new:nnnn { sort } { return-none } - { The~comparison~code~did~not~return. } - { - When~sorting~a~list,~the~code~to~compare~items~#1~and~#2~ - did~not~call~ - \iow_char:N\\sort_ordered: ~nor~ - \iow_char:N\\sort_reversed: .~ - Exactly~one~of~these~should~be~called. - } -\__msg_kernel_new:nnnn { sort } { return-two } - { The~comparison~code~returned~multiple~times. } - { - When~sorting~a~list,~the~code~to~compare~items~called~ - \iow_char:N\\sort_ordered: ~or~ - \iow_char:N\\sort_reversed: ~multiple~times.~ - Exactly~one~of~these~should~be~called. - } -% \end{macrocode} -% -% \begin{macrocode} -% -% \end{macrocode} -% -% \end{implementation} -% -% \PrintIndex diff --git a/Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.ins b/Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.ins deleted file mode 100644 index b6165791b96..00000000000 --- a/Master/texmf-dist/source/latex/l3experimental/l3sort/l3sort.ins +++ /dev/null @@ -1,56 +0,0 @@ -\iffalse meta-comment - -File l3sort.ins Copyright (C) 2012,2106 The LaTeX3 Project - -It may be distributed and/or modified under the conditions of the -LaTeX Project Public License (LPPL), either version 1.3c of this -license or (at your option) any later version. The latest version -of this license is in the file - - http://www.latex-project.org/lppl.txt - -This file is part of the "l3experimental bundle" (The Work in LPPL) -and all files in that bundle must be distributed together. - ------------------------------------------------------------------------ - -The development version of the bundle can be found at - - https://github.com/latex3/latex3 - -for those people who are interested. - ------------------------------------------------------------------------ - -Any modification of this file should ensure that the copyright and -license information is placed in the derived files. - -\fi - -\input l3docstrip.tex -\askforoverwritefalse - -\preamble - -Copyright (C) 2012-2016 The LaTeX3 Project - -It may be distributed and/or modified under the conditions of -the LaTeX Project Public License (LPPL), either version 1.3c of -this license or (at your option) any later version. The latest -version of this license is in the file: - - http://www.latex-project.org/lppl.txt - -This file is part of the "l3experimental bundle" (The Work in LPPL) -and all files in that bundle must be distributed together. - -\endpreamble -% stop docstrip adding \endinput -\postamble -\endpostamble - -\keepsilent - -\generate{\file{l3sort.sty}{\from{l3sort.dtx}{package}}} - -\endbatchfile diff --git a/Master/texmf-dist/source/latex/l3experimental/l3str/l3flag.dtx b/Master/texmf-dist/source/latex/l3experimental/l3str/l3flag.dtx index 4fc1e4ad543..441a5be48d1 100644 --- a/Master/texmf-dist/source/latex/l3experimental/l3str/l3flag.dtx +++ b/Master/texmf-dist/source/latex/l3experimental/l3str/l3flag.dtx @@ -23,8 +23,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{l3flag}{Support package l3kernel too old} @@ -36,7 +36,7 @@ % }% % \endinput % } -\GetIdInfo$Id: l3flag.dtx 6829 2017-01-28 08:52:51Z joseph $ +\GetIdInfo$Id: l3flag.dtx 6846 2017-02-07 07:04:19Z joseph $ {L3 Experimental flags} % %<*driver> diff --git a/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx b/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx index 18b0be30f7e..b1711cbd47f 100644 --- a/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx +++ b/Master/texmf-dist/source/latex/l3experimental/l3str/l3regex.dtx @@ -23,8 +23,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{l3regex}{Support package l3kernel too old} @@ -36,7 +36,7 @@ % }% % \endinput % } -\GetIdInfo$Id: l3regex.dtx 6829 2017-01-28 08:52:51Z joseph $ +\GetIdInfo$Id: l3regex.dtx 6846 2017-02-07 07:04:19Z joseph $ {L3 Experimental regular expressions} % %<*driver> diff --git a/Master/texmf-dist/source/latex/l3experimental/l3str/l3tl-build.dtx b/Master/texmf-dist/source/latex/l3experimental/l3str/l3tl-build.dtx index 7b566c75df3..ccf2b6d3705 100644 --- a/Master/texmf-dist/source/latex/l3experimental/l3str/l3tl-build.dtx +++ b/Master/texmf-dist/source/latex/l3experimental/l3str/l3tl-build.dtx @@ -23,8 +23,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{l3tl-build}{Support package l3kernel too old} @@ -36,7 +36,7 @@ % }% % \endinput % } -\GetIdInfo$Id: l3tl-build.dtx 6829 2017-01-28 08:52:51Z joseph $ +\GetIdInfo$Id: l3tl-build.dtx 6846 2017-02-07 07:04:19Z joseph $ {L3 Experimental token list construction} % %<*driver> diff --git a/Master/texmf-dist/source/latex/l3experimental/xgalley/l3galley.dtx b/Master/texmf-dist/source/latex/l3experimental/xgalley/l3galley.dtx index ae956e6e333..f277ed814eb 100644 --- a/Master/texmf-dist/source/latex/l3experimental/xgalley/l3galley.dtx +++ b/Master/texmf-dist/source/latex/l3experimental/xgalley/l3galley.dtx @@ -24,8 +24,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{l3galley}{Support package l3kernel too old} @@ -37,7 +37,7 @@ % }% % \endinput % } -\GetIdInfo$Id: l3galley.dtx 6829 2017-01-28 08:52:51Z joseph $ +\GetIdInfo$Id: l3galley.dtx 6846 2017-02-07 07:04:19Z joseph $ {L3 Experimental galley code} % %<*driver> @@ -2606,7 +2606,7 @@ % \begin{macro}{\@@par} % The primitive is moved as otherwise the clever skipping code will fail. % \begin{macrocode} -\cs_set_eq:cN { @ @ par } \galley_par: +\cs_set_eq:NN \@@@@par \galley_par: % \end{macrocode} % \end{macro} % diff --git a/Master/texmf-dist/source/latex/l3kernel/expl3.dtx b/Master/texmf-dist/source/latex/l3kernel/expl3.dtx index 5a2661885c0..433338287d3 100644 --- a/Master/texmf-dist/source/latex/l3kernel/expl3.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/expl3.dtx @@ -1,6 +1,6 @@ % \iffalse meta-comment % -%% File: expl3.dtx Copyright (C) 1990-2016 The LaTeX3 Project +%% File: expl3.dtx Copyright (C) 1990-2017 The LaTeX3 Project % % It may be distributed and/or modified under the conditions of the % LaTeX Project Public License (LPPL), either version 1.3c of this @@ -23,8 +23,8 @@ %<*driver|generic|package> \def\ExplFileName{expl3}% \def\ExplFileDescription{L3 programming layer}% -\def\ExplFileDate{2017/01/28}% -\def\ExplFileVersion{6834}% +\def\ExplFileDate{2017/02/07}% +\def\ExplFileVersion{6846}% % %<*driver> \documentclass[full]{l3doc} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3.ins b/Master/texmf-dist/source/latex/l3kernel/l3.ins index c86f611940c..3f281392b4e 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3.ins +++ b/Master/texmf-dist/source/latex/l3kernel/l3.ins @@ -1,6 +1,6 @@ \iffalse meta-comment -File l3.ins Copyright (C) 2011,2012,2014-2016 The LaTeX3 Project +File l3.ins Copyright (C) 2011,2012,2014-2017 The LaTeX3 Project It may be distributed and/or modified under the conditions of the LaTeX Project Public License (LPPL), either version 1.3c of this @@ -33,7 +33,7 @@ license information is placed in the derived files. \preamble -Copyright (C) 1990-2016 The LaTeX3 Project +Copyright (C) 1990-2017 The LaTeX3 Project It may be distributed and/or modified under the conditions of the LaTeX Project Public License (LPPL), either version 1.3c of @@ -89,6 +89,7 @@ and all files in that bundle must be distributed together. \from{l3fp-convert.dtx} {package} \from{l3fp-random.dtx} {package} \from{l3fp-assign.dtx} {package} + \from{l3sort.dtx} {package} \from{l3box.dtx} {package} \from{l3coffins.dtx} {package} \from{l3color.dtx} {package} @@ -137,6 +138,7 @@ and all files in that bundle must be distributed together. \generate{\file{l3quark.sty} {\from{l3oldmodules.dtx} {l3quark,oldmodules}}} \generate{\file{l3seq.sty} {\from{l3oldmodules.dtx} {l3seq,oldmodules}}} \generate{\file{l3skip.sty} {\from{l3oldmodules.dtx} {l3skip,oldmodules}}} +\generate{\file{l3sort.sty} {\from{l3oldmodules.dtx} {l3sort,oldmodules}}} \generate{\file{l3str.sty} {\from{l3oldmodules.dtx} {l3str,oldmodules}}} \generate{\file{l3tl.sty} {\from{l3oldmodules.dtx} {l3tl,oldmodules}}} \generate{\file{l3token.sty} {\from{l3oldmodules.dtx} {l3token,oldmodules}}} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3candidates.dtx b/Master/texmf-dist/source/latex/l3kernel/l3candidates.dtx index 62a21ee09ea..9b68994b370 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3candidates.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3candidates.dtx @@ -24,7 +24,7 @@ \documentclass[full]{l3doc} % %<*driver|package> -\GetIdInfo$Id: l3candidates.dtx 6809 2017-01-01 06:33:13Z bruno $ +\GetIdInfo$Id: l3candidates.dtx 6835 2017-01-30 21:25:17Z bruno $ {L3 Experimental additions to l3kernel} % %<*driver> @@ -686,34 +686,6 @@ % \end{function} % % \begin{function}[EXP, added = 2016-12-06] -% {\prop_rand_key:N, \prop_rand_key:c} -% \begin{syntax} -% \cs{prop_rand_key:N} \meta{prop~var} -% \end{syntax} -% Selects a pseudo-random key--value pair in the \meta{property list} -% and returns the \meta{key}. If the \meta{property list} is empty -% the result is empty. This is only available in \pdfTeX{} and -% \LuaTeX{}. -% \end{function} -% -% \begin{function}[EXP, added = 2016-12-06] -% {\prop_rand_value:N, \prop_rand_value:c} -% \begin{syntax} -% \cs{prop_rand_value:N} \meta{prop~var} -% \end{syntax} -% Selects a pseudo-random key--value pair in the \meta{property list} -% and returns the \meta{value}. If the \meta{property list} is empty -% the result is empty. This is only available in \pdfTeX{} and -% \LuaTeX{}. -% \begin{texnote} -% The result is returned within the \tn{unexpanded} -% primitive (\cs{exp_not:n}), which means that the \meta{value} -% will not expand further when appearing in an \texttt{x}-type -% argument expansion. -% \end{texnote} -% \end{function} -% -% \begin{function}[EXP, added = 2016-12-06] % {\prop_rand_key_value:N, \prop_rand_key_value:c} % \begin{syntax} % \cs{prop_rand_key_value:N} \meta{prop~var} @@ -2842,11 +2814,7 @@ % \end{macro} % % \begin{macro}[EXP] -% { -% \prop_rand_key:N, \prop_rand_key:c, -% \prop_rand_value:N, \prop_rand_value:c, -% \prop_rand_key_value:N, \prop_rand_key_value:c -% } +% {\prop_rand_key_value:N, \prop_rand_key_value:c} % \begin{macro}[aux, EXP]{\@@_rand:NN, \@@_rand_item:Nw} % Contrarily to |clist|, |seq| and |tl|, there is no function to get % an item of a |prop| given an integer between $1$ and the number of @@ -2855,8 +2823,6 @@ % end, leave either the key |#3| or the value |#4| in the input % stream. % \begin{macrocode} -\cs_new:Npn \prop_rand_key:N { \@@_rand:NN \use_i:nnn } -\cs_new:Npn \prop_rand_value:N { \@@_rand:NN \use_none:n } \cs_new:Npn \prop_rand_key_value:N { \@@_rand:NN \@@_rand:nNn } \cs_new:Npn \@@_rand:nNn #1#2#3 { \exp_not:n { {#1} {#3} } } \cs_new:Npn \@@_rand:NN #1#2 @@ -2875,8 +2841,6 @@ \exp_after:wN \@@_rand_item:Nw \exp_after:wN #1 \__int_value:w \int_eval:n { #2 - \c_one } \s_@@ } -\cs_generate_variant:Nn \prop_rand_key:N { c } -\cs_generate_variant:Nn \prop_rand_value:N { c } \cs_generate_variant:Nn \prop_rand_key_value:N { c } % \end{macrocode} % \end{macro} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3clist.dtx b/Master/texmf-dist/source/latex/l3kernel/l3clist.dtx index b7364894e39..12aea777839 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3clist.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3clist.dtx @@ -2,7 +2,7 @@ % %% File: l3clist.dtx Copyright (C) 2004-2011 Frank Mittelbach, %% The LaTeX3 project -%% (C) 2012-2016 The LaTeX3 Project +%% (C) 2012-2017 The LaTeX3 Project % % It may be distributed and/or modified under the conditions of the % LaTeX Project Public License (LPPL), either version 1.3c of this @@ -26,7 +26,7 @@ \documentclass[full]{l3doc} % %<*driver|package> -\GetIdInfo$Id: l3clist.dtx 6805 2016-12-28 22:15:52Z joseph $ +\GetIdInfo$Id: l3clist.dtx 6842 2017-02-06 21:51:22Z joseph $ {L3 Comma separated lists} % %<*driver> @@ -305,6 +305,17 @@ % \end{texnote} % \end{function} % +% \begin{function}[added = 2017-02-06] +% {\clist_sort:Nn, \clist_sort:cn, \clist_gsort:Nn, \clist_gsort:cn} +% \begin{syntax} +% \cs{clist_sort:Nn} \meta{clist var} \Arg{comparison code} +% \end{syntax} +% Sorts the items in the \meta{clist var} according to the +% \meta{comparison code}, and assigns the result to +% \meta{clist var}. The details of sorting comparison are +% described in Section~\ref{sec:l3sort:mech}. +% \end{function} +% % \section{Comma list conditionals} % % \begin{function}[EXP,pTF]{\clist_if_empty:N, \clist_if_empty:c} @@ -1358,6 +1369,11 @@ % \end{macro} % \end{macro} % +% \begin{macro} +% {\clist_sort:Nn, \clist_sort:cn, \clist_gsort:Nn, \clist_gsort:cn} +% Implemented in \pkg{l3sort}. +% \end{macro} +% % \subsection{Comma list conditionals} % % \begin{macro}[pTF]{\clist_if_empty:N, \clist_if_empty:c} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3doc.dtx b/Master/texmf-dist/source/latex/l3kernel/l3doc.dtx index fc4319207fb..fc90688aa63 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3doc.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3doc.dtx @@ -62,7 +62,7 @@ Do not distribute a modified version of this file. % %<*driver|class> \RequirePackage{expl3,xparse,calc} -\GetIdInfo$Id: l3doc.dtx 6809 2017-01-01 06:33:13Z bruno $ +\GetIdInfo$Id: l3doc.dtx 6839 2017-02-06 18:52:08Z bruno $ {L3 Experimental documentation class} % % @@ -975,7 +975,7 @@ Do not distribute a modified version of this file. % \begin{macro}[aux]{\@@_replace_at_at_aux:Nn} % The goal is to replace |@@| by the current module name. If there is % no \meta{module~name}, do nothing. Otherwise, sanitize the catcodes -% of |@| and~|_| and replace both |_@@| and |@@| by +% of |@| and~|_|, temporarily change |@@@@| to |aa| with different catcodes and later to |@@|, and replace |__@@| and |_@@| and |@@| by % |__|\meta{module~name}. The result contains |_| with category % code letter because this is what the |macrocode| environment % expects. Other use cases can apply \cs{tl_to_str:n} if needed. @@ -991,12 +991,15 @@ Do not distribute a modified version of this file. #1 \g_@@_module_name_tl } } -\cs_new_protected:Npn \@@_replace_at_at_aux:Nn #1#2 +\cs_new_protected:Npx \@@_replace_at_at_aux:Nn #1#2 { - \tl_replace_all:Non #1 { \token_to_str:N @ } { @ } - \tl_replace_all:Non #1 { \token_to_str:N _ } { _ } - \tl_replace_all:Nnn #1 { _ @ @ } { _ _ #2 } - \tl_replace_all:Nnn #1 { @ @ } { _ _ #2 } + \tl_replace_all:Nnn #1 { \token_to_str:N @ } { @ } + \tl_replace_all:Nnn #1 { \token_to_str:N _ } { _ } + \tl_replace_all:Nnn #1 { @ @ @ @ } { \token_to_str:N a a } + \tl_replace_all:Nnn #1 { _ _ @ @ } { _ _ #2 } + \tl_replace_all:Nnn #1 { _ @ @ } { _ _ #2 } + \tl_replace_all:Nnn #1 { @ @ } { _ _ #2 } + \tl_replace_all:Nnn #1 { \token_to_str:N a a } { @ @ } } % \end{macrocode} % \end{macro} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3docstrip.dtx b/Master/texmf-dist/source/latex/l3kernel/l3docstrip.dtx index 14626c67e4f..7b98fe3889a 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3docstrip.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3docstrip.dtx @@ -100,7 +100,7 @@ % % To extract the code using \pkg{l3docstrip}, the \enquote{guard} concept % used by \textsf{DocStrip} is extended by introduction of the syntax -% \texttt{\%<@@=\meta{module}}. The \meta{module} name will be used when the +% \texttt{\%<@@=\meta{module}>}. The \meta{module} name will be used when the % code is extracted to replace the |@@|, so that % \begin{verbatim} % %<*package> @@ -123,6 +123,10 @@ % where the |__| indicates that the functions and variables are internal % to the \texttt{foo} module. % +% Use |@@@@| to obtain |@@| in the output (|@@@@@| to get |@@@|). For +% longer pieces of code the replacement can be completely suppressed by +% giving an empty module name, namely using the syntax \texttt{\%<@@=>}. +% % \end{documentation} % % \begin{implementation} @@ -188,7 +192,10 @@ % The argument (|#1|) is the replacement text to use, or if empty an % indicator that no replacement should be done. The search material is % one of |__@@|, |_@@| or |@@|, done in order such that all three will end -% up the same in the output. The replacement function is initialised as a +% up the same in the output. The string |@@@@| is hidden from these +% replacements by temporarily turning it into a pair of letters with +% different category codes, not produced by \pkg{docstrip}; this allows to +% get |@@| in the output. The replacement function is initialised as a % do-nothing for the case where |%<@@=| is never seen. % \begin{macrocode} \begingroup @@ -197,10 +204,12 @@ \ifx\relax#1\relax \let\replaceModuleInLine\empty \else - \def\replaceModuleInLine{% - \replaceAllIn\inLine{__@@}{__#1}% - \replaceAllIn\inLine{_@@}{__#1}% - \replaceAllIn\inLine{@@}{__#1}% + \edef\replaceModuleInLine{% + \noexpand\replaceAllIn\noexpand\inLine{@@@@}{\string aa}% + \noexpand\replaceAllIn\noexpand\inLine{__@@}{__#1}% + \noexpand\replaceAllIn\noexpand\inLine{_@@}{__#1}% + \noexpand\replaceAllIn\noexpand\inLine{@@}{__#1}% + \noexpand\replaceAllIn\noexpand\inLine{\string aa}{@@}% }% \fi } diff --git a/Master/texmf-dist/source/latex/l3kernel/l3format.ins b/Master/texmf-dist/source/latex/l3kernel/l3format.ins index 0a4822eb012..d49a7794f86 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3format.ins +++ b/Master/texmf-dist/source/latex/l3kernel/l3format.ins @@ -1,6 +1,6 @@ \iffalse meta-comment -File l3format.ins Copyright (C) 2011,2012,2014-2016 The LaTeX3 Project +File l3format.ins Copyright (C) 2011,2012,2014-2017 The LaTeX3 Project It may be distributed and/or modified under the conditions of the LaTeX Project Public License (LPPL), either version 1.3c of this @@ -33,7 +33,7 @@ license information is placed in the derived files. \preamble -Copyright (C) 1990-2016 The LaTeX3 Project +Copyright (C) 1990-2017 The LaTeX3 Project It may be distributed and/or modified under the conditions of the LaTeX Project Public License (LPPL), either version 1.3c of @@ -89,6 +89,7 @@ and all files in that bundle must be distributed together. \from{l3fp-convert.dtx} {initex} \from{l3fp-random.dtx} {initex} \from{l3fp-assign.dtx} {initex} + \from{l3sort.dtx} {initex} \from{l3box.dtx} {initex} \from{l3coffins.dtx} {initex} \from{l3color.dtx} {initex} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3oldmodules.dtx b/Master/texmf-dist/source/latex/l3kernel/l3oldmodules.dtx index 5fa4071258b..e081a5b3ce5 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3oldmodules.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3oldmodules.dtx @@ -1,6 +1,6 @@ % \iffalse meta-comment % -%% File: l3oldmodules.dtx Copyright (C) 2014,2016 The LaTeX3 Project +%% File: l3oldmodules.dtx Copyright (C) 2014,2016,2017 The LaTeX3 Project % % It may be distributed and/or modified under the conditions of the % LaTeX Project Public License (LPPL), either version 1.3c of this @@ -106,6 +106,7 @@ %{l3quark} %{l3seq} %{l3skip} +%{l3sort} %{l3str} %{l3tl} %{l3token} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3seq.dtx b/Master/texmf-dist/source/latex/l3kernel/l3seq.dtx index e9079d80701..dbc4e4dd295 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3seq.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3seq.dtx @@ -1,6 +1,6 @@ % \iffalse meta-comment % -%% File: l3seq.dtx Copyright (C) 1990-2016 The LaTeX3 Project +%% File: l3seq.dtx Copyright (C) 1990-2017 The LaTeX3 Project % % It may be distributed and/or modified under the conditions of the % LaTeX Project Public License (LPPL), either version 1.3c of this @@ -24,7 +24,7 @@ \documentclass[full]{l3doc} % %<*driver|package> -\GetIdInfo$Id: l3seq.dtx 6805 2016-12-28 22:15:52Z joseph $ +\GetIdInfo$Id: l3seq.dtx 6842 2017-02-06 21:51:22Z joseph $ {L3 Sequences and stacks} % %<*driver> @@ -431,7 +431,6 @@ % \cs{tl_if_eq:nnTF}. % \end{function} % -% % \begin{function}[added = 2014-07-18] % { % \seq_reverse:N, \seq_reverse:c, @@ -443,6 +442,17 @@ % Reverses the order of the items stored in the \meta{sequence}. % \end{function} % +% \begin{function}[added = 2017-02-06] +% {\seq_sort:Nn, \seq_sort:cn, \seq_gsort:Nn, \seq_gsort:cn} +% \begin{syntax} +% \cs{seq_sort:Nn} \meta{sequence} \Arg{comparison code} +% \end{syntax} +% Sorts the items in the \meta{sequence} according to the +% \meta{comparison code}, and assigns the result to +% \meta{sequence}. The details of sorting comparison are +% described in Section~\ref{sec:l3sort:mech}. +% \end{function} +% % \section{Sequence conditionals} % % \begin{function}[EXP,pTF]{\seq_if_empty:N, \seq_if_empty:c} @@ -1391,6 +1401,10 @@ % \end{macro} % \end{macro} % +% \begin{macro}{\seq_sort:Nn, \seq_sort:cn, \seq_gsort:Nn, \seq_gsort:cn} +% Implemented in \pkg{l3sort}. +% \end{macro} +% % \subsection{Sequence conditionals} % % \begin{macro}[pTF]{\seq_if_empty:N, \seq_if_empty:c} diff --git a/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx b/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx new file mode 100644 index 00000000000..a732120976c --- /dev/null +++ b/Master/texmf-dist/source/latex/l3kernel/l3sort.dtx @@ -0,0 +1,1100 @@ +% \iffalse +% +%% File l3sort.dtx (C) Copyright 2012,2014-2017 The LaTeX3 Project +% +% It may be distributed and/or modified under the conditions of the +% LaTeX Project Public License (LPPL), either version 1.3c of this +% license or (at your option) any later version. The latest version +% of this license is in the file +% +% http://www.latex-project.org/lppl.txt +% +% This file is part of the "l3kernel bundle" (The Work in LPPL) +% and all files in that bundle must be distributed together. +% +% ----------------------------------------------------------------------- +% +% The development version of the bundle can be found at +% +% https://github.com/latex3/latex3 +% +% for those people who are interested. +% +%<*driver> +\documentclass[full]{l3doc} +% +%<*driver|package> +\GetIdInfo$Id: l3sort.dtx 6842 2017-02-06 21:51:22Z joseph $ + {L3 Sorting functions} +% +%<*driver> +\begin{document} + \DocInput{\jobname.dtx} +\end{document} +% +% \fi +% +% \title{^^A +% The \pkg{l3sort} package\\ Sorting functions^^A +% \thanks{This file describes v\ExplFileVersion, +% last revised \ExplFileDate.}^^A +% } +% +% \author{^^A +% The \LaTeX3 Project\thanks +% {^^A +% E-mail: +% \href{mailto:latex-team@latex-project.org} +% {latex-team@latex-project.org}^^A +% }^^A +% } +% +% \date{Released \ExplFileDate} +% +% \maketitle +% +% \begin{documentation} +% +% \section{Controlling sorting} +% +% \label{sec:l3sort:mech} +% +% \LaTeX3 comes with a facility to sort list variables (sequences, +% token lists, or comma-lists) according to some user-defined +% comparison. For instance, +% \begin{verbatim} +% \clist_set:Nn \l_foo_clist { 3 , 01 , -2 , 5 , +1 } +% \clist_sort:Nn \l_foo_clist +% { +% \int_compare:nNnTF { #1 } > { #2 } +% { \sort_return_swapped: } +% { \sort_return_same: } +% } +% \end{verbatim} +% will result in \cs{l_foo_clist} holding the values +% |{ -2 , 01 , +1 , 3 , 5 }| sorted in non-decreasing order. +% +% The code defining the comparison should call +% \cs{sort_return_swapped:} if the two items given as |#1| +% and |#2| are not in the correct order, and otherwise it +% should call \cs{sort_return_same:} to indicate that +% the order of this pair of items should not be changed. +% +% For instance, a \meta{comparison code} consisting only +% of \cs{sort_return_same:} with no test will yield a trivial +% sort: the final order is identical to the original order. +% Conversely, using a \meta{comparison code} consisting only +% of \cs{sort_return_swapped:} will reverse the list (in a fairly +% inefficient way). +% +% \begin{texnote} +% The current implementation is limited to sorting approximately +% $20000$ items ($40000$ in Lua\TeX{}), depending on what other +% packages are loaded. +% +% Internally, the code from \pkg{l3sort} stores items in \tn{toks} +% registers allocated locally. Thus, the \meta{comparison code} +% should not call \tn{newtoks} or other commands that allocate new +% \tn{toks} registers. On the other hand, altering the value of a +% previously allocated \tn{toks} register is not a problem. +% \end{texnote} +% +% \end{documentation} +% +% \begin{implementation} +% +% \section{\pkg{l3sort} implementation} +% +% \begin{macrocode} +%<*initex|package> +% \end{macrocode} +% +% \begin{macrocode} +%<@@=sort> +% \end{macrocode} +% +% \subsection{Variables} +% +% \begin{variable} +% { +% \l_@@_length_int, \l_@@_min_int, \l_@@_top_int, \l_@@_max_int, +% \l_@@_true_max_int +% } +% The sequence has \cs{l_@@_length_int} items and is stored from +% \cs{l_@@_min_int} to $\cs{l_@@_top_int}-1$. While reading the +% sequence in memory, we check that \cs{l_@@_top_int} remains at most +% \cs{l_@@_max_int}, precomputed by \cs{@@_compute_range:}. That +% bound is such that the merge sort will only use \tn{toks} registers +% less than \cs{l_@@_true_max_int}, namely those that have not been +% allocated for use in other code: the user's comparison code could +% alter these. +% \begin{macrocode} +\int_new:N \l_@@_length_int +\int_new:N \l_@@_min_int +\int_new:N \l_@@_top_int +\int_new:N \l_@@_max_int +\int_new:N \l_@@_true_max_int +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_@@_block_int} +% Merge sort is done in several passes. In each pass, blocks of size +% \cs{l_@@_block_int} are merged in pairs. The block size starts +% at $1$, and, for a length in the range $[2^k+1,2^{k+1}]$, reaches +% $2^{k}$ in the last pass. +% \begin{macrocode} +\int_new:N \l_@@_block_int +% \end{macrocode} +% \end{variable} +% +% \begin{variable}{\l_@@_begin_int} +% \begin{variable}{\l_@@_end_int} +% When merging two blocks, \cs{l_@@_begin_int} marks the lowest +% index in the two blocks, and \cs{l_@@_end_int} marks the +% highest index, plus $1$. +% \begin{macrocode} +\int_new:N \l_@@_begin_int +\int_new:N \l_@@_end_int +% \end{macrocode} +% \end{variable} +% \end{variable} +% +% \begin{variable}{\l_@@_A_int} +% \begin{variable}{\l_@@_B_int} +% \begin{variable}{\l_@@_C_int} +% When merging two blocks (whose end-points are \texttt{beg} +% and \texttt{end}), $A$ starts from the high end of the low +% block, and decreases until reaching \texttt{beg}. The index +% $B$ starts from the top of the range and marks the register +% in which a sorted item should be put. Finally, $C$ points +% to the copy of the high block in the interval of registers +% starting at \cs{l_@@_length_int}, upwards. $C$ starts +% from the upper limit of that range. +% \begin{macrocode} +\int_new:N \l_@@_A_int +\int_new:N \l_@@_B_int +\int_new:N \l_@@_C_int +% \end{macrocode} +% \end{variable} +% \end{variable} +% \end{variable} +% +% \subsection{Finding available \tn{toks} registers} +% +% \begin{macro}[int]{\@@_shrink_range:} +% \begin{macro}[aux]{\@@_shrink_range_loop:} +% After \cs{@@_compute_range:} (defined below) determines that +% \tn{toks} registers between \cs{l_@@_min_int} (included) and +% \cs{l_@@_true_max_int} (excluded) have not yet been assigned, +% \cs{@@_shrink_range:} computes \cs{l_@@_max_int} to reflect the need +% for a buffer when merging blocks in the merge sort. Given +% $2^{n}\leq A\leq 2^{n}+2^{n-1}$ registers we can sort $\lfloor +% A/2\rfloor+2^{n-2}$ items while if we have $2^{n}+2^{n-1}\leq A\leq +% 2^{n+1}$ registers we can sort $A-2^{n-1}$ items. We first find out +% a power $2^{n}$ such that $2^{n}\leq A\leq 2^{n+1}$ by repeatedly +% halving \cs{l_@@_block_int}, starting at $2^{15}$ or $2^{14}$ namely +% half the total number of registers, then we use the formulas and set +% \cs{l_@@_max_int}. +% \begin{macrocode} +\cs_new_protected:Npn \@@_shrink_range: + { + \int_set:Nn \l_@@_A_int + { \l_@@_true_max_int - \l_@@_min_int + \c_one } + \int_set:Nn \l_@@_block_int { \c_max_register_int / \c_two } + \@@_shrink_range_loop: + \int_set:Nn \l_@@_max_int + { + \int_compare:nNnTF + { \l_@@_block_int * \c_three / \c_two } > \l_@@_A_int + { + \l_@@_min_int + + ( \l_@@_A_int - \c_one ) / \c_two + + \l_@@_block_int / \c_four + - \c_one + } + { \l_@@_true_max_int - \l_@@_block_int / \c_two } + } + } +\cs_new_protected:Npn \@@_shrink_range_loop: + { + \if_int_compare:w \l_@@_A_int < \l_@@_block_int + \tex_divide:D \l_@@_block_int \c_two + \exp_after:wN \@@_shrink_range_loop: + \fi: + } +% \end{macrocode} +% \end{macro} +% \end{macro} +% +% \begin{macro}[int]{\@@_compute_range:, \@@_redefine_compute_range:} +% \begin{variable}{\c_@@_max_length_int} +% First find out what \tn{toks} have not yet been assigned. There are +% many cases. In \LaTeXe{} with no package, available \tn{toks} range +% from $\tn{count}15+1$ to \cs{c_max_register_int} included (this was +% not altered despite the 2015 changes). When \tn{loctoks} is +% defined, namely in plain (e)\TeX{}, or when the package \pkg{etex} +% is loaded in \LaTeXe{}, redefine \cs{@@_compute_range:} to use the +% range $\tn{count}265$ to $\tn{count}275-1$. The \pkg{elocalloc} +% package also defines \tn{loctoks} but uses yet another number for +% the upper bound, namely \cs{e@alloc@top} (minus one). We must check +% 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 +% $|\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 +% mode is easiest: no \tn{toks} are ever allocated so available +% \tn{toks} range from $0$ to \cs{c_max_register_int} and we +% precompute the result of \cs{@@_shrink_range:}. +% \begin{macrocode} +%<*package> +\cs_new_protected:Npn \@@_compute_range: + { + \int_set:Nn \l_@@_min_int { \tex_count:D 15 + \c_one } + \int_set:Nn \l_@@_true_max_int { \c_max_register_int + \c_one } + \@@_shrink_range: + \if_meaning:w \loctoks \tex_undefined:D \else: + \if_meaning:w \loctoks \scan_stop: \else: + \@@_redefine_compute_range: + \@@_compute_range: + \fi: + \fi: + } +\cs_new_protected:Npn \@@_redefine_compute_range: + { + \cs_if_exist:cTF { ver@elocalloc.sty } + { + \cs_gset_protected:Npn \@@_compute_range: + { + \int_set:Nn \l_@@_min_int { \tex_count:D 265 } + \int_set_eq:NN \l_@@_true_max_int \e@alloc@top + \@@_shrink_range: + } + } + { + \cs_gset_protected:Npn \@@_compute_range: + { + \int_set:Nn \l_@@_min_int { \tex_count:D 265 } + \int_set:Nn \l_@@_true_max_int { \tex_count:D 275 } + \@@_shrink_range: + } + } + } +\cs_if_exist:NT \loctoks { \@@_redefine_compute_range: } +\tl_map_inline:nn { \lastallocatedtoks \c_syst_last_allocated_toks } + { + \cs_if_exist:NT #1 + { + \cs_gset_protected:Npn \@@_compute_range: + { + \int_set:Nn \l_@@_min_int { #1 + \c_one } + \int_set:Nn \l_@@_true_max_int { \c_max_register_int + \c_one } + \@@_shrink_range: + } + } + } +% +%<*initex> +\int_const:Nn \c_@@_max_length_int + { ( \c_max_register_int + 1 ) * 3 / 4 } +\cs_new_protected:Npn \@@_compute_range: + { + \int_set_eq:NN \l_@@_min_int \c_zero + \int_set:Nn \l_@@_true_max_int { \c_max_register_int + \c_one } + \int_set_eq:NN \l_@@_max_int \c_@@_max_length_int + } +% +% \end{macrocode} +% \end{variable} +% \end{macro} +% +% \subsection{Protected user commands} +% +% \begin{macro}[int]{\@@_main:NNNnNn} +% 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. +% \begin{macrocode} +\cs_new_protected:Npn \@@_main:NNNnNn #1#2#3#4#5#6 + { + \group_begin: +% \@@_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} + \tex_advance:D \l_@@_top_int \c_one + } + \int_set:Nn \l_@@_length_int + { \l_@@_top_int - \l_@@_min_int } + \cs_set:Npn \@@_compare:nn ##1 ##2 { #6 } + \int_set_eq:NN \l_@@_block_int \c_one + \@@_level: + \use:x + { + \group_end: + #1 \exp_not:N #5 {#4} + } + } +% \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{macrocode} +\cs_new_protected:Npn \seq_sort:Nn + { + \@@_main:NNNnNn \tl_set:Nn + \seq_map_inline:Nn \seq_map_break:n + { \s__seq \@@_toks:NN \exp_not:N \__seq_item:n } + } +\cs_generate_variant:Nn \seq_sort:Nn { c } +\cs_new_protected:Npn \seq_gsort:Nn + { + \@@_main:NNNnNn \tl_gset:Nn + \seq_map_inline:Nn \seq_map_break:n + { \s__seq \@@_toks:NN \exp_not:N \__seq_item:n } + } +\cs_generate_variant:Nn \seq_gsort:Nn { c } +% \end{macrocode} +% \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{macrocode} +\cs_new_protected:Npn \tl_sort:Nn + { + \@@_main:NNNnNn \tl_set:Nn + \tl_map_inline:Nn \tl_map_break:n + { \@@_toks:NN \prg_do_nothing: \prg_do_nothing: } + } +\cs_generate_variant:Nn \tl_sort:Nn { c } +\cs_new_protected:Npn \tl_gsort:Nn + { + \@@_main:NNNnNn \tl_gset:Nn + \tl_map_inline:Nn \tl_map_break:n + { \@@_toks:NN \prg_do_nothing: \prg_do_nothing: } + } +\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}[aux]{\@@_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 + { + \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} + } + } +% \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 + \c_one \exp_after:wN ; + \fi: + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Merge sort} +% +% \begin{macro}[int]{\@@_level:} +% This function is called once blocks of size \cs{l_@@_block_int} +% (initially $1$) are each sorted. If the whole list fits in one +% block, then we are done (this also takes care of the case of an +% empty list or a list with one item). Otherwise, go through pairs +% of blocks starting from $0$, then double the block size, and repeat. +% \begin{macrocode} +\cs_new_protected:Npn \@@_level: + { + \if_int_compare:w \l_@@_block_int < \l_@@_length_int + \l_@@_end_int \l_@@_min_int + \@@_merge_blocks: + \tex_advance:D \l_@@_block_int \l_@@_block_int + \exp_after:wN \@@_level: + \fi: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[int]{\@@_merge_blocks:} +% This function is called to merge a pair of blocks, starting at +% the last value of \cs{l_@@_end_int} (end-point of the previous +% pair of blocks). If shifting by one block to the right we reach +% the end of the list, then this pass has ended: the end of the +% list is sorted already. Otherwise, store the result of that shift in $A$, +% which will index the first block starting from the top end. +% Then locate the end-point (maximum) of the second block: shift +% \texttt{end} upwards by one more block, but keeping it +% $\leq\texttt{top}$. Copy this upper block of \tn{toks} +% registers in registers above \texttt{length}, indexed by $C$: +% this is covered by \cs{@@_copy_block:}. Once this is done we +% are ready to do the actual merger using \cs{@@_merge_blocks_aux:}, +% after shifting $A$, $B$ and $C$ so that they point to the largest +% index in their respective ranges rather than pointing just beyond +% those ranges. Of course, once that pair of blocks is merged, +% move on to the next pair. +% \begin{macrocode} +\cs_new_protected:Npn \@@_merge_blocks: + { + \l_@@_begin_int \l_@@_end_int + \tex_advance:D \l_@@_end_int \l_@@_block_int + \if_int_compare:w \l_@@_end_int < \l_@@_top_int + \l_@@_A_int \l_@@_end_int + \tex_advance:D \l_@@_end_int \l_@@_block_int + \if_int_compare:w \l_@@_end_int > \l_@@_top_int + \l_@@_end_int \l_@@_top_int + \fi: + \l_@@_B_int \l_@@_A_int + \l_@@_C_int \l_@@_top_int + \@@_copy_block: + \tex_advance:D \l_@@_A_int - \c_one + \tex_advance:D \l_@@_B_int - \c_one + \tex_advance:D \l_@@_C_int - \c_one + \exp_after:wN \@@_merge_blocks_aux: + \exp_after:wN \@@_merge_blocks: + \fi: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[int]{\@@_copy_block:} +% We wish to store a copy of the \enquote{upper} block of +% \tn{toks} registers, ranging between the initial value of +% \cs{l_@@_B_int} (included) and \cs{l_@@_end_int} +% (excluded) into a new range starting at the initial value +% of \cs{l_@@_C_int}, namely \cs{l_@@_top_int}. +% \begin{macrocode} +\cs_new_protected:Npn \@@_copy_block: + { + \tex_toks:D \l_@@_C_int \tex_toks:D \l_@@_B_int + \tex_advance:D \l_@@_C_int \c_one + \tex_advance:D \l_@@_B_int \c_one + \if_int_compare:w \l_@@_B_int = \l_@@_end_int + \use_i:nn + \fi: + \@@_copy_block: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\@@_merge_blocks_aux:} +% At this stage, the first block starts at \cs{l_@@_begin_int}, +% and ends at \cs{l_@@_A_int}, and the second block starts at +% \cs{l_@@_top_int} and ends at \cs{l_@@_C_int}. The result +% of the merger is stored at positions indexed by \cs{l_@@_B_int}, +% which starts at $\cs{l_@@_end_int}-1$ and decreases down to +% \cs{l_@@_begin_int}, covering the full range of the two blocks. +% In other words, we are building the merger starting with the +% largest values. +% The comparison function is defined to return either +% \texttt{swapped} or \texttt{same}. Of course, this +% means the arguments need to be given in the order they +% appear originally in the list. +% \begin{macrocode} +\cs_new_protected:Npn \@@_merge_blocks_aux: + { + \exp_after:wN \@@_compare:nn \exp_after:wN + { \tex_the:D \tex_toks:D \exp_after:wN \l_@@_A_int \exp_after:wN } + \exp_after:wN { \tex_the:D \tex_toks:D \l_@@_C_int } + \prg_do_nothing: + \@@_return_mark:N + \@@_return_mark:N + \@@_return_none_error: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{\sort_return_same:, \sort_return_swapped:} +% \begin{macro}[aux]{\@@_return_mark:N} +% \begin{macro}[aux]{\@@_return_none_error:, \@@_return_two_error:w} +% The marker removes one token. Each comparison should call +% \cs{sort_return_same:} or \cs{sort_return_swapped:} exactly +% 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: } +\cs_new_protected:Npn \sort_return_swapped: #1 \@@_return_mark:N + { #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: + { + \__msg_kernel_error:nnxx { sort } { return-none } + { \tex_the:D \tex_toks:D \l_@@_A_int } + { \tex_the:D \tex_toks:D \l_@@_C_int } + \@@_return_same: + } +\cs_new_protected:Npn \@@_return_two_error:w + #1 \@@_return_none_error: + { \__msg_kernel_error:nn { sort } { return-two } } +% \end{macrocode} +% \end{macro} +% \end{macro} +% \end{macro} +% +% \begin{macro}[aux]{\@@_return_same:} +% If the comparison function returns \texttt{same}, +% then the second argument fed to \cs{@@_compare:nn} +% should remain to the right of the other one. Since +% we build the merger starting from the right, we copy +% that \tn{toks} register into the allotted range, then +% shift the pointers $B$ and $C$, and go on to do one +% more step in the merger, unless the second block has +% been exhausted: then the remainder of the first block +% is already in the correct registers and we are done +% with merging those two blocks. +% \begin{macrocode} +\cs_new_protected:Npn \@@_return_same: + { + \tex_toks:D \l_@@_B_int \tex_toks:D \l_@@_C_int + \tex_advance:D \l_@@_B_int - \c_one + \tex_advance:D \l_@@_C_int - \c_one + \if_int_compare:w \l_@@_C_int < \l_@@_top_int + \use_i:nn + \fi: + \@@_merge_blocks_aux: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\@@_return_swapped:} +% If the comparison function returns \texttt{swapped}, +% then the next item to add to the merger is the first +% argument, contents of the \tn{toks} register $A$. +% Then shift the pointers $A$ and $B$ to the left, and +% go for one more step for the merger, unless the left +% block was exhausted ($A$ goes below the threshold). +% In that case, all remaining \tn{toks} registers in +% the second block, indexed by $C$, are copied +% to the merger by \cs{@@_merge_blocks_end:}. +% \begin{macrocode} +\cs_new_protected:Npn \@@_return_swapped: + { + \tex_toks:D \l_@@_B_int \tex_toks:D \l_@@_A_int + \tex_advance:D \l_@@_B_int - \c_one + \tex_advance:D \l_@@_A_int - \c_one + \if_int_compare:w \l_@@_A_int < \l_@@_begin_int + \@@_merge_blocks_end: \use_i:nn + \fi: + \@@_merge_blocks_aux: + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\@@_merge_blocks_end:} +% This function's task is to copy the \tn{toks} registers +% in the block indexed by $C$ to the merger indexed by $B$. +% The end can equally be detected by checking when $B$ reaches +% the threshold \texttt{begin}, or when $C$ reaches +% \texttt{top}. +% \begin{macrocode} +\cs_new_protected:Npn \@@_merge_blocks_end: + { + \tex_toks:D \l_@@_B_int \tex_toks:D \l_@@_C_int + \tex_advance:D \l_@@_B_int - \c_one + \tex_advance:D \l_@@_C_int - \c_one + \if_int_compare:w \l_@@_B_int < \l_@@_begin_int + \use_i:nn + \fi: + \@@_merge_blocks_end: + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Expandable sorting} +% +% Sorting expandably is very different from sorting and assigning to a +% variable. Since tokens cannot be stored, they must remain in the +% input stream, and be read through at every step. It is thus +% necessarily much slower (at best $O(n^2\ln n)$) than non-expandable +% sorting functions ($O(n\ln n)$). +% +% A prototypical version of expandable quicksort is as follows. If the +% argument has no item, return nothing, otherwise partition, using the +% first item as a pivot (argument |#4| of \cs{@@:nnNnn}). The +% arguments of \cs{@@:nnNnn} are 1.~items less than |#4|, 2.~items +% greater or equal to |#4|, 3.~comparison, 4.~pivot, 5.~next item to +% test. If |#5| is the tail of the list, call \cs{tl_sort:nN} on |#1| +% and on |#2|, placing |#4| in between; |\use:ff| expands the parts to +% make \cs{tl_sort:nN} \texttt{f}-expandable. Otherwise, compare |#4| +% and |#5| using |#3|. If they are ordered, place |#5| amongst the +% \enquote{greater} items, otherwise amongst the \enquote{lesser} items, +% and continue partitioning. +% \begin{verbatim} +% \cs_new:Npn \tl_sort:nN #1#2 +% { +% \tl_if_blank:nF {#1} +% { +% \__sort:nnNnn { } { } #2 +% #1 \q_recursion_tail \q_recursion_stop +% } +% } +% \cs_new:Npn \__sort:nnNnn #1#2#3#4#5 +% { +% \quark_if_recursion_tail_stop_do:nn {#5} +% { \use:ff { \tl_sort:nN {#1} #3 {#4} } { \tl_sort:nN {#2} #3 } } +% #3 {#4} {#5} +% { \__sort:nnNnn {#1} { #2 {#5} } #3 {#4} } +% { \__sort:nnNnn { #1 {#5} } {#2} #3 {#4} } +% } +% \cs_generate_variant:Nn \use:nn { ff } +% \end{verbatim} +% There are quite a few optimizations available here: the code below is +% less legible, but more than twice as fast. +% +% In the simple version of the code, \cs{@@:nnNnn} is called +% \(O(n\ln n)\) times on average (the number of comparisons required by +% the quicksort algorithm). Hence most of our focus will be on +% optimizing that function. +% +% The first speed up is to avoid testing for the end of the list at +% every call to \cs{@@:nnNnn}. For this, the list is prepared by +% changing each \meta{item} of the original token list into +% \meta{command} \Arg{item}, just like sequences are stored. We arrange +% things such that the \meta{command} is the \meta{conditional} provided +% by the user: the loop over the \meta{prepared tokens} then looks like +% \begin{quote} +% \ttfamily +% \cs{cs_new:Npn}~\cs{@@_loop:wNn}~\ldots{}~|#6#7|\\ +% ~~|{|\\ +% ~~~~|#6|~\Arg{pivot}~|{#7}|~\meta{loop big}~\meta{loop small}\\ +% ~~~~~~\meta{extra arguments}\\ +% ~~|}|\\ +% \cs{@@_loop:wNn}~\ldots{}~\meta{prepared tokens}\\ +% ~~\meta{end-loop}~|{}|~|\q_stop| +% \end{quote} +% In this example, which matches the structure of +% \cs{@@_quick_split_i:NnnnnNn} and a few other functions below, the +% \cs{@@_loop:wNn} auxiliary normally receives the user's +% \meta{conditional} as~|#6| and an \meta{item} as~|#7|. This is +% compared to the \meta{pivot} (the argument~|#5|, not shown here), and +% the \meta{conditional} leaves the \meta{loop big} or \meta{loop small} +% auxiliary, which both have the same form as \cs{@@_loop:wNn}, +% receiving the next pair \meta{conditional} \Arg{item} as |#6| +% and~|#7|. At the end, |#6| is the \meta{end-loop} function, which +% terminates the loop. +% +% The second speed up is to minimize the duplicated tokens between the +% \texttt{true} and \texttt{false} branches of the conditional. For +% this, we introduce two versions of \cs{@@:nnNnn}, which receive +% the new item as~|#1| and place it either into the list~|#2| of items +% less than the pivot~|#4| or into the list~|#3| of items greater or +% equal to the pivot. +% \begin{verbatim} +% \cs_new:Npn \__sort_i:nnnnNn #1#2#3#4#5#6 +% { +% #5 {#4} {#6} \__sort_ii:nnnnNn \__sort_i:nnnnNn +% {#6} { #2 {#1} } {#3} {#4} +% } +% \cs_new:Npn \__sort_ii:nnnnNn #1#2#3#4#5#6 +% { +% #5 {#4} {#6} \__sort_ii:nnnnNn \__sort_i:nnnnNn +% {#6} {#2} { #3 {#1} } {#4} +% } +% \end{verbatim} +% Note that the two functions have the form of \cs{@@_loop:wNn} above, +% receiving as~|#5| the conditional or a function to end the loop. In +% fact, the lists~|#2| and~|#3| must be made of pairs \meta{conditional} +% \Arg{item}, so we have to replace~|{#6}| above by |{|~|#5|~|{#6}|~|}|, +% and |{#1}|~by~|#1|. The actual functions have one more argument, so +% all argument numbers are shifted compared to this code. +% +% The third speed up is to avoid |\use:ff| using a continuation-passing +% style: \cs{@@_quick_split:NnNn} expects a list followed by +% \cs{q_mark} \Arg{code}, and expands to \meta{code} \meta{sorted list}. +% Sorting the two parts of the list around the pivot is done with +% \begin{quote} +% \ttfamily +% \cs{@@_quick_split:NnNn} |#2| \ldots{} \cs{q_mark}\\ +% ~~|{|\\ +% ~~~~\cs{@@_quick_split:NnNn} |#1| \ldots{} \cs{q_mark} \Arg{code}\\ +% ~~~~\Arg{pivot}\\ +% ~~|}| +% \end{quote} +% Items which are larger than the \meta{pivot} are sorted, then placed +% after code that sorts the smaller items, and after the (braced) +% \meta{pivot}. +% +% The fourth speed up is avoid the recursive call to \cs{tl_sort:nN} +% with an empty first argument. For this, we introduce functions +% similar to the \cs{@@_i:nnnnNn} of the last example, but aware of +% whether the list of \meta{conditional} \Arg{item} read so far that are +% less than the pivot, and the list of those greater or equal, are empty +% or not: see \cs{@@_quick_split:NnNn} and functions defined below. +% Knowing whether the lists are empty or not is useless if we do not use +% distinct ending codes as appropriate. The splitting auxiliaries +% communicate to the \meta{end-loop} function (that is initially placed +% after the ``prepared'' list) by placing a specific ending function, +% ignored when looping, but useful at the end. In fact, the +% \meta{end-loop} function does nothing but place the appropriate ending +% function in front of all its arguments. The ending functions take +% care of sorting non-empty sublists, placing the pivot in between, and +% the continuation before. +% +% The final change in fact slows down the code a little, but is required +% to avoid memory issues: schematically, when \TeX{} encounters +% \begin{verbatim} +% \use:n { \use:n { \use:n { ... } ... } ... } +% \end{verbatim} +% the argument of the first \cs{use:n} is not completely read by the +% second \cs{use:n}, hence must remain in memory; then the argument of +% the second \cs{use:n} is not completely read when grabbing the +% argument of the third \cs{use:n}, hence must remain in memory, and so +% on. The memory consumption grows quadratically with the number of +% nested \cs{use:n}. In practice, this means that we must read +% everything until a trailing \cs{q_stop} once in a while, otherwise +% sorting lists of more than a few thousand items would exhaust a +% typical \TeX{}'s memory. +% +% \begin{macro}[EXP]{\tl_sort:nN} +% \begin{macro}[aux, EXP] +% { +% \@@_quick_prepare:Nnnn, +% \@@_quick_prepare_end:NNNnw, +% \@@_quick_cleanup:w +% } +% The code within the \cs{exp_not:f} sorts the list, leaving in most +% cases a leading \cs{exp_not:f}, which stops the expansion, letting +% the result be return within \cs{exp_not:n}. We filter out the case +% of a list with no item, which would otherwise cause problems. Then +% prepare the token list~|#1| by inserting the conditional~|#2| before +% 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 +% \texttt{prepare_end} auxiliary finds the prepared token list +% as~|#4|. The scene is then set up for \cs{@@_quick_split:NnNn}, +% which will sort the prepared list and perform the post action placed +% 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} +\cs_new:Npn \tl_sort:nN #1#2 + { + \exp_not:f + { + \tl_if_blank:nF {#1} + { + \@@_quick_prepare:Nnnn #2 { } { } + #1 + { \__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: + \@@_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 + } +\cs_new:Npn \@@_quick_cleanup:w #1 \s__stop \q_stop {#1} +% \end{macrocode} +% \end{macro} +% \end{macro} +% +% \begin{macro}[EXP, aux] +% { +% \@@_quick_split:NnNn, +% \@@_quick_only_i:NnnnnNn, +% \@@_quick_only_ii:NnnnnNn, +% \@@_quick_split_i:NnnnnNn, +% \@@_quick_split_ii:NnnnnNn +% } +% The \texttt{only_i}, \texttt{only_ii}, \texttt{split_i} and +% \texttt{split_ii} auxiliaries receive a useless first argument, the +% new item~|#2| (that they append to either one of the next two +% arguments), the list~|#3| of items less than the pivot, bigger +% items~|#4|, the pivot~|#5|, a \meta{function}~|#6|, and an +% item~|#7|. The \meta{function} is the user's \meta{conditional} +% except at the end of the list where it is +% \cs{@@_quick_end:nnTFNn}. The comparison is applied to the +% \meta{pivot} and the \meta{item}, and calls the \texttt{only_i} or +% \texttt{split_i} auxiliaries if the \meta{item} is smaller, and the +% \texttt{only_ii} or \texttt{split_ii} auxiliaries otherwise. In +% both cases, the next auxiliary goes to work right away, with no +% intermediate expansion that would slow down operations. Note that +% the argument~|#2| left for the next call has the form +% \meta{conditional} \Arg{item}, so that the lists~|#3| and~|#4| keep +% the right form to be fed to the next sorting function. +% The \texttt{split} auxiliary differs from these in that it is +% missing three of the arguments, which would be empty, and its first +% argument is always the user's \meta{conditional} rather than an +% ending function. +% \begin{macrocode} +\cs_new:Npn \@@_quick_split:NnNn #1#2#3#4 + { + #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 + \@@_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 + \@@_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 + \@@_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 + \@@_quick_split_end:nnnwnw + { #6 {#7} } {#3} { #4 #2 } {#5} + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[EXP, aux] +% { +% \@@_quick_end:nnTFNn, +% \@@_quick_single_end:nnnwnw, +% \@@_quick_only_i_end:nnnwnw, +% \@@_quick_only_ii_end:nnnwnw, +% \@@_quick_split_end:nnnwnw, +% } +% The \cs{@@_quick_end:nnTFNn} appears instead of the user's +% conditional, and receives as its arguments the pivot~|#1|, a fake +% item~|#2|, a \texttt{true} and a \texttt{false} branches |#3| +% and~|#4|, followed by an ending function~|#5| (one of the four +% auxiliaries here) and another copy~|#6| of the fake item. All those +% are discarded except the function~|#5|. This function receives +% lists~|#1| and~|#2| of items less than or greater than the +% pivot~|#3|, then a continuation code~|#5| just after \cs{q_mark}. +% To avoid a memory problem described earlier, all of the ending +% functions read~|#6| until \cs{q_stop} and place~|#6| back into the +% input stream. When the lists |#1| and~|#2| are empty, the +% \texttt{single} auxiliary simply places the continuation~|#5| before +% the pivot~|{#3}|. When |#2|~is empty, |#1|~is sorted and placed +% before the pivot~|{#3}|, taking care to feed the continuation~|#5| +% as a continuation for the function sorting~|#1|. When |#1|~is +% empty, |#2|~is sorted, and the continuation argument is used to +% place the continuation~|#5| and the pivot~|{#3}| before the sorted +% result. Finally, when both lists are non-empty, items larger than +% the pivot are sorted, then items less than the pivot, and the +% continuations are done in such a way to place the pivot in between. +% \begin{macrocode} +\cs_new:Npn \@@_quick_end:nnTFNn #1#2#3#4#5#6 {#5} +\cs_new:Npn \@@_quick_single_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop + { #5 {#3} #6 \q_stop } +\cs_new:Npn \@@_quick_only_i_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop + { + \@@_quick_split:NnNn #1 + \@@_quick_end:nnTFNn { } \q_mark {#5} + {#3} + #6 \q_stop + } +\cs_new:Npn \@@_quick_only_ii_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop + { + \@@_quick_split:NnNn #2 + \@@_quick_end:nnTFNn { } \q_mark { #5 {#3} } + #6 \q_stop + } +\cs_new:Npn \@@_quick_split_end:nnnwnw #1#2#3#4 \q_mark #5#6 \q_stop + { + \@@_quick_split:NnNn #2 \@@_quick_end:nnTFNn { } \q_mark + { + \@@_quick_split:NnNn #1 + \@@_quick_end:nnTFNn { } \q_mark {#5} + {#3} + } + #6 \q_stop + } +% \end{macrocode} +% \end{macro} +% +% \subsection{Messages} +% +% \begin{macro}[aux]{\@@_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. +% \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: } + } +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\@@_disable_toksdef:, \@@_disabled_toksdef:n} +% While sorting, \tn{toksdef} is locally disabled to prevent users +% from using \tn{newtoks} or similar commands in their comparison +% code: the \tn{toks} registers that would be assigned are in use by +% \pkg{l3sort}. In format mode, none of this is needed since there is +% no \tn{toks} allocator. +% \begin{macrocode} +%<*package> +\cs_new_protected:Npn \@@_disable_toksdef: + { \cs_set_eq:NN \toksdef \@@_disabled_toksdef:n } +\cs_new_protected:Npn \@@_disabled_toksdef:n #1 + { + \__msg_kernel_error:nnx { sort } { toksdef } + { \token_to_str:N #1 } + \@@_error: + \tex_toksdef:D #1 + } +\__msg_kernel_new:nnnn { sort } { toksdef } + { 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~ + or~a~similar~command.~The~list~will~not~be~sorted. + } +% +% \end{macrocode} +% \end{macro} +% +% \begin{macro}[aux]{\@@_too_long_error:NNw} +% When there are too many items in a sequence, this is an error, and +% we clean up properly the mapping over items in the list: break using +% the type-specific breaking function |#1|. +% \begin{macrocode} +\cs_new_protected:Npn \@@_too_long_error:NNw #1#2 \fi: + { + \fi: + \__msg_kernel_error:nnxxx { sort } { too-large } + { \token_to_str:N #2 } + { \int_eval:n { \l_@@_true_max_int - \l_@@_min_int } } + { \int_eval:n { \l_@@_top_int - \l_@@_min_int } } + #1 \@@_error: + } +\__msg_kernel_new:nnnn { sort } { too-large } + { The~list~#1~is~too~long~to~be~sorted~by~TeX. } + { + TeX~has~#2~toks~registers~still~available:~ + this~only~allows~to~sort~with~up~to~#3~ + items.~All~extra~items~will~be~deleted. + } +% \end{macrocode} +% \end{macro} +% +% \begin{macrocode} +\__msg_kernel_new:nnnn { sort } { return-none } + { The~comparison~code~did~not~return. } + { + When~sorting~a~list,~the~code~to~compare~items~#1~and~#2~ + did~not~call~ + \iow_char:N\\sort_return_same: ~nor~ + \iow_char:N\\sort_return_swapped: .~ + Exactly~one~of~these~should~be~called. + } +\__msg_kernel_new:nnnn { sort } { return-two } + { The~comparison~code~returned~multiple~times. } + { + When~sorting~a~list,~the~code~to~compare~items~called~ + \iow_char:N\\sort_return_same: ~or~ + \iow_char:N\\sort_return_swapped: ~multiple~times.~ + Exactly~one~of~these~should~be~called. + } +% \end{macrocode} +% +% \subsection{Deprecated functions} +% +% \begin{macro}[deprecated = 2017-02-06]{\sort_ordered:, \sort_reversed:} +% These functions were renamed for consistency. +% \begin{macrocode} +\cs_new_eq:NN \sort_ordered: \sort_return_same: +\cs_new_eq:NN \sort_reversed: \sort_return_swapped: +% \end{macrocode} +% \end{macro} +% +% \begin{macrocode} +% +% \end{macrocode} +% +% \end{implementation} +% +% \PrintIndex diff --git a/Master/texmf-dist/source/latex/l3kernel/l3tl.dtx b/Master/texmf-dist/source/latex/l3kernel/l3tl.dtx index 8f1fac513ed..1acb5e14625 100644 --- a/Master/texmf-dist/source/latex/l3kernel/l3tl.dtx +++ b/Master/texmf-dist/source/latex/l3kernel/l3tl.dtx @@ -24,7 +24,7 @@ \documentclass[full]{l3doc} % %<*driver|package> -\GetIdInfo$Id: l3tl.dtx 6805 2016-12-28 22:15:52Z joseph $ +\GetIdInfo$Id: l3tl.dtx 6842 2017-02-06 21:51:22Z joseph $ {L3 Token lists} % %<*driver> @@ -783,6 +783,35 @@ % \emph{resets} the content of the variable. % \end{function} % +% \begin{function}[added = 2017-02-06] +% {\tl_sort:Nn, \tl_sort:cn, \tl_gsort:Nn, \tl_gsort:cn} +% \begin{syntax} +% \cs{tl_sort:Nn} \meta{tl var} \Arg{comparison code} +% \end{syntax} +% Sorts the items in the \meta{tl var} according to the +% \meta{comparison code}, and assigns the result to +% \meta{tl var}. The details of sorting comparison are +% described in Section~\ref{sec:l3sort:mech}. +% \end{function} +% +% \begin{function}[added = 2017-02-06, EXP]{\tl_sort:nN} +% \begin{syntax} +% \cs{tl_sort:nN} \Arg{token list} \meta{conditional} +% \end{syntax} +% Sorts the items in the \meta{token list}, using the +% \meta{conditional} to compare items, and leaves the result in the +% input stream. The \meta{conditional} should have signature |:nnTF|, +% and return \texttt{true} if the two items being compared should be +% left in the same order, and \texttt{false} if the items should be +% swapped. The details of sorting comparison are +% described in Section~\ref{sec:l3sort:mech}. +% \begin{texnote} +% The result is returned within \cs{exp_not:n}, which means that the +% token list will not expand further when appearing in an +% \texttt{x}-type argument expansion. +% \end{texnote} +% \end{function} +% % \section{The first token from a token list} % % Functions which deal with either only the very first item (balanced @@ -2404,6 +2433,11 @@ % \end{macro} % \end{macro} % +% \begin{macro} +% {\tl_sort:Nn, \tl_sort:cn, \tl_gsort:Nn, \tl_gsort:cn, \tl_sort:nN} +% Implemented in \pkg{l3sort}. +% \end{macro} +% % \subsection{Token by token changes} % % \begin{variable}{\q_@@_act_mark, \q_@@_act_stop} diff --git a/Master/texmf-dist/source/latex/l3packages/l3keys2e/l3keys2e.dtx b/Master/texmf-dist/source/latex/l3packages/l3keys2e/l3keys2e.dtx index da221d72cfd..df48e99599f 100644 --- a/Master/texmf-dist/source/latex/l3packages/l3keys2e/l3keys2e.dtx +++ b/Master/texmf-dist/source/latex/l3packages/l3keys2e/l3keys2e.dtx @@ -23,8 +23,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{l3keys2e}{Support package l3kernel too old} @@ -38,8 +38,8 @@ % } \def\ExplFileName{l3keys2e} \def\ExplFileDescription{LaTeX2e option processing using LaTeX3 keys} -\def\ExplFileDate{2017/01/28} -\def\ExplFileVersion{6834} +\def\ExplFileDate{2017/02/07} +\def\ExplFileVersion{6846} % %<*driver> \documentclass[full]{l3doc} diff --git a/Master/texmf-dist/source/latex/l3packages/xfrac/xfrac.dtx b/Master/texmf-dist/source/latex/l3packages/xfrac/xfrac.dtx index 37e3eaa7f43..a09cbfae677 100644 --- a/Master/texmf-dist/source/latex/l3packages/xfrac/xfrac.dtx +++ b/Master/texmf-dist/source/latex/l3packages/xfrac/xfrac.dtx @@ -24,8 +24,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{xfrac}{Support package l3kernel too old} @@ -40,8 +40,8 @@ \RequirePackage{amstext,graphicx,l3keys2e,textcomp,xparse,xtemplate} \def\ExplFileName{xfrac} \def\ExplFileDescription{L3 Experimental split-level fractions} -\def\ExplFileDate{2017/01/28} -\def\ExplFileVersion{6834} +\def\ExplFileDate{2017/02/07} +\def\ExplFileVersion{6846} % %<*driver> \documentclass[full]{l3doc} diff --git a/Master/texmf-dist/source/latex/l3packages/xparse/xparse.dtx b/Master/texmf-dist/source/latex/l3packages/xparse/xparse.dtx index 72e95c647ad..f4138d1b0e0 100644 --- a/Master/texmf-dist/source/latex/l3packages/xparse/xparse.dtx +++ b/Master/texmf-dist/source/latex/l3packages/xparse/xparse.dtx @@ -27,8 +27,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{xparse}{Support package l3kernel too old} @@ -42,8 +42,8 @@ % } \def\ExplFileName{xparse} \def\ExplFileDescription{L3 Experimental document command parser} -\def\ExplFileDate{2017/01/28} -\def\ExplFileVersion{6834} +\def\ExplFileDate{2017/02/07} +\def\ExplFileVersion{6846} % %<*driver> \documentclass[full]{l3doc} diff --git a/Master/texmf-dist/source/latex/l3packages/xtemplate/xtemplate.dtx b/Master/texmf-dist/source/latex/l3packages/xtemplate/xtemplate.dtx index 0e0cc211476..31a5c72bffd 100644 --- a/Master/texmf-dist/source/latex/l3packages/xtemplate/xtemplate.dtx +++ b/Master/texmf-dist/source/latex/l3packages/xtemplate/xtemplate.dtx @@ -27,8 +27,8 @@ %<*driver|package> % The version of expl3 required is tested as early as possible, as % some really old versions do not define \ProvidesExplPackage. -\RequirePackage{expl3}[2017/01/28] -%\@ifpackagelater{expl3}{2017/01/28} +\RequirePackage{expl3}[2017/02/07] +%\@ifpackagelater{expl3}{2017/02/07} % {} % {% % \PackageError{xtemplate}{Support package l3kernel too old} @@ -42,8 +42,8 @@ % } \def\ExplFileName{xtemplate} \def\ExplFileDescription{L3 Experimental prototype document functions} -\def\ExplFileDate{2017/01/28} -\def\ExplFileVersion{6834} +\def\ExplFileDate{2017/02/07} +\def\ExplFileVersion{6846} % %<*driver> \documentclass[full]{l3doc} -- cgit v1.2.3