# Expandable, standard TeX only way to compare balanced token lists

Is there a (reasonably) efficient macro that does something similar to \long\def\comparets#1#2{\def\aa{#1}\def\bb{#2}\ifx\aa\bb true\else false\fi} except is expandable (i.e. \newcomparets{<tokens1>}{<tokens2>} would expand into either 'true' or 'false', including inside \edef)? I am looking for a 'pure' TeX (i.e. no extensions, such as e-TeX) solution. I have looked at l3tl macros but they seem to use e-TeX. The solution should work with arbitrary token sequences (including ones containing various flavors of 'funny spaces' and braces and arbitrary control sequences). I cannot seem to find a way to do this without performing several passes.

-
May we ask why no e-TeX? – Joseph Wright Mar 18 '14 at 15:29
e-tex is different to other extensions such as luatex or xetex in that (in all the major distributions), the binary is e-tex and "tex" is just e-tex running in compatibility mode with the extended commands disabled) – David Carlisle Mar 18 '14 at 16:38
Do you really have a solution? I would be surprised that it is possible, if you step through token by token using #1 parsing you lose spaces and {} groups and if you step through using \futurelet it isn't expandable. – David Carlisle Mar 18 '14 at 16:40
@DavidCarlisle I'm not sure you are right about tex: my understanding is that is still just Knuth's TeX (in contrast to etex, pdftex, latex, pdflatex, all of which use the pdfTeX engine) – Joseph Wright Mar 18 '14 at 16:45
@JosephWright yes true. – David Carlisle Mar 18 '14 at 17:00

I am unsure if posting this as an answer to my own question is kosher since it does not really answer it but I will not flag it as such (even assuming I could) so if anyone has a flash of inspiration that solves the original problem, I will gladly label it as a true answer.

Now about the macros. I apologize in advance for the shape they are in. They have been pulled (and re-re-renamed) from a variety of code I have written over the years, so the style is a bit ... eclectic, shall we say. A lot can be optimized below but the problem of multiple passes remains as I will explain later, so if anyone has a clever trick to solve it, please let me know.

There are a couple of caveats:

1) The actual comparison macros are missing, only the analysis part is present, which delivers, in 'prefix expandable' way (e.g. works with the \romannumeral-1 trick) a string of category 11 and 12 tokens that contains enough information to identify every token in the sequence as far as its category, character code, if any, whether it is a brace, its character code, etc. Such strings can be compared directly if desired.

2) Well, 1) is a white lie on two counts:

a) any token that can be grabbed as a parameter (i. e. a non space, non brace) is (grabbed and) just replaced by its \meaning string enclosed in t ... e (both t and e are category 11); note that category 10 tokens with character code other than 32 fall into this category (pun intended). \yygrabtokenraw can be adjusted to provide better analysis (a must if the goal is to compare arbitrary balanced lists of tokens but just boils down to a few carefully written conditionals). Note that just \string is not enough, either, since \escapechar can be -1.

b) the 'top level' recursion step is missing; the main problem here are braces of character code 32; they are dealt with in the very last stage when the length of the sequence is known and one can just \string every one of them up or find out their \meaning. Well, not so fast because if they have category code 32, both \meaning and \string turn them into ordinary spaces (the \meaning will end in two spaces which does not help either) which is one problem \detokenize was invented to correct. Thus we need to decide how to grab them. The one guarantee the code makes is that every opening brace will be correctly identified as either character code 32 (o1e or c1e) or character code other than 32 (o2e, c2e). The code that does this messes up some of the closing braces that follow (their character codes) in order to safely consume the brace so c2e 'markers' following the first one are unreliable (however, if another o1e, o1e or o2e is found, it is a brace of character code 32). The next iteration can grab the braces that are 'deciphered' without messing up the next brace. After many more passes (up to as many as there are closing braces, unfortunately), everything can be resolved. If anyone is interested, I can finish the macros to do this. Only if Knuth ended each \meaning with a dot ...

3) The code spends a lot of time 'propagating expansion'. A typical situation is \somemacro{<long list of benign tokens>}{\string}; \string here needs to be expanded before anything else can happen, so \somemacro spends a lot of time inserting \expandafters in the the <long list ...>. Note that the \romannumeral will fail if the <long list ...> is very long so coding everything as digits will not help. Using \csname <long ...>\endcsname is possible (with an \expandafter follow up) but I am uneasy about polluting TeX's hash table in this case.

The macros try to identify 'funny spaces' in the first pass, this is the only use for \meaning and \yymatchblankspace below. One can do with \string only.

A test case for the macro is included at the end. If I overlooked something stupid, my apologies (when Joseph Wright and others are suspicious, I tend to be too).

EDIT: On top of whatever else might be off with these, I omitted \long in front of every definition for clarity, so a \par will wreck it.

To expand on provide better analysis above: to resolve pathological cases (such as \escapechar=-1 \let\#=#) one can prepare either a bunch of macros (one (or even two) per character, such as \expandafter\def\csname match#\endcsname #1\##{...}% last '#' is \catcode 13) or a few macros with one \defed as \def\maintest #1<a list of all active characters and single letter cs's>{...} doing all the heavy lifting (by recursively inserting the 'grabbed' token in the potential 'delimiter'). In between options (trading time for space) are also possible. As far as 'that is a lot of macros' it is a concern, of course. My (imperfect) take on this is: 'if one can afford that many \catcode registers, one can afford those special 'conditionals', as well).

I am afraid the expansion propagation problem mentioned above is simply the price of doing recursion in TeX. This problem can be somewhat mitigated by encoding (during the first pass) the tokens with \yysx ? where \def\yysx#1#2{\expandafter\space\expandafter\yysx\expandafter#1\romannumeral-1#2}. This way a \romannumeral-1 in front of a list of \yysx ? entries will 'pass' the expansion to the end of the list while staying intact.

The 'brace post processing' feels like it should be avoidable.

Finally, I have got asked many times 'why no e-TeX?'. I am not sure this is a proper place to discuss it but I have (probably subjective) reasons to avoid it. If anyone can suggest a better place to discuss such preferences, I would appreciate it.

% helper macros (to build test cases, etc); @ is a letter

\def\yyreplacestring#1\in#2\with#3{%
\expandafter\def\expandafter\r@placestring\expandafter##\expandafter1\the#1##2\end{%
\def\r@placestring{##2}% is this the string at the very end?
\ifx\r@placestring\empty % then it is the one we inserted, report
\errmessage{string <\the#1> not present in \the#2}% do not change the register if the string is not there
\else % remove the extra copy of #1\end at the end
\expandafter#2\expandafter\expandafter\expandafter
{\expandafter\r@plac@string\expandafter{\the#3}{##1}##2\end}%
\fi}% end of \r@placestring definition
\expandafter\def\expandafter\r@plac@string
\expandafter##\expandafter1%
\expandafter##\expandafter2%
\expandafter##\expandafter3%
\the#1\end{##2##1##3}%
\expandafter\expandafter\expandafter\r@placestring\expandafter\the\expandafter#2\the#1\end
}

\newtoks\toksa
\newtoks\toksb
\newtoks\toksc
\newtoks\toksd

\def\yybreak#1#2\yycontinue{\fi#1}

\def\eatone#1{}
\def\eatonespace#1 {}
\def\identity#1{#1}
\def\yyfirstoftwo#1#2{#1}
\def\yysecondoftwo#1#2{#2}
\def\yysecondofthree#1#2#3{#2}
\def\yythirdofthree#1#2#3{#3}

% #1 -- call stack'
% #2 -- remaining sequence
% #3 -- parsed' sequence

\def\yypreparsetokensequenc@#1#2#3{%
\yystringempty{#2}{#1{#3}}{\yypreparsetokensequen@@{#1}{#2}{#3}}%
}

\def\yypreparsetokensequen@@#1#2#3{% remaining sequence is nonempty
\yystartsinbrace{#2}{\yydealwithbracedgroup{#1}{#2}{#3}}{\yypreparsetokensequ@n@@{#1}{#2}{#3}}%
}

\def\yydealwithbracedgroup#1#2#3{% the first token of the remaining sequence is a brace
\iffalse{\fi\yydealwithbracedgro@p#2}{#1}{#3}%
}

\def\yydealwithbracedgro@p#1{%
\yypreparsetokensequenc@{\yyrepackagesequence}{#1}{}%
}

% #1 -- parsed sequence
% this is a sequence to propagate expansion' into the next parameter.
% the same can be achieved by packaging the whole sequence with a
% \csname ... \endcsname pair and using a simple \expandafter
% maybe that would be a better idea ...

\def\yyrepackagesequence#1{%
\yyrepackagesequenc@{}#1\end
}

% #1 -- packaged' sequence (\expandafter\expandafter\expandafter ? ...)
% #2 -- the next category 12 character or \end

\def\yyrepackagesequenc@#1#2{%
\ifx#2\end
\yybreak{\yyrepackagesequ@nc@{#1\expandafter\expandafter\expandafter}}%
\else
\yybreak{\yyrepackagesequenc@{#1\expandafter\expandafter\expandafter#2}}%
\yycontinue
}

% #1 -- packaged' sequence (\expandafter\expandafter\expandafter ? ...)
% this macro is followed by the remainder of the original sequence with a so far
% unmatched right brace, the call stack' and the parsed sequence.

\def\yyrepackagesequ@nc@#1{%
\expandafter\expandafter\expandafter\yyrepackagesequ@nc@swap#1{\expandafter\eatone\string}%
}

% #1 -- parsed sequence without packaging

\def\yyrepackagesequ@nc@swap#1#{%
\yyrepackagesequ@nc@sw@p{#1}%
}

% #1 -- parsed inner' sequence
% #2 -- remainder of the original sequence
% #3 -- call stack'
% #4 -- parsed sequence so far

\def\yyrepackagesequ@nc@sw@p#1#2#3#4{%
\yypreparsetokensequenc@{#3}{#2}{#4[#1]}%
}

% braced group' thread ends here

% #1 -- call stack'
% #2 -- remaining sequence
% #3 -- parsed' sequence

\def\yypreparsetokensequ@n@@#1#2#3{% the remaining group in #2 is nonempty and does not start with a brace
\yystartsinspace{#2}{\yyconsumetruespace{#1}{#2}{#3}}{\yypreparsetokenseq@@n@@{#1}{#2}{#3}}%
}

\def\yyconsumetruespace#1#2#3{%
\expandafter\yyconsumetruespac@swap\expandafter{\eatonespace#2}{#1}{#3.}%
}

\def\yyconsumetruespac@swap#1#2#3{%
\yypreparsetokensequenc@{#2}{#1}{#3}%
}

% group starting with a true (character code 32, category code 10) space' thread ends here

% #1 -- call stack'
% #2 -- remaining sequence
% #3 -- parsed' sequence

\def\yypreparsetokenseq@@n@@#1#2#3{% a nonempty group, that does not start with a brace or a true space
\yymatchblankspace{#2}{\yyrescanblankspace{#2}{#1}{#3}}{\yypreparsetokens@q@@n@@{#1}{#2}{#3}}%
}

% #1 -- remaining sequence
% #2 -- call stack'
% #3 -- parsed' sequence

\def\yyrescanblankspace#1#2#3{%
\expandafter\expandafter\expandafter
\yyrescanblankspac@swap
\expandafter\expandafter\expandafter{\expandafter\yynormalizeblankspac@\meaning#1}{#2}{#3*}%
}

\def\yyrescanblankspac@swap#1#2#3{%
\yystartsinspace{#1}{%
\expandafter\yyrescanblankspac@sw@p\expandafter{\eatonespace#1}{#2}{#3}%
}{%
\expandafter\yyrescanblankspac@sw@p\expandafter{\eatone#1}{#2}{#3}%
}%
}

\def\yyrescanblankspac@sw@p#1#2#3{%
\yypreparsetokensequenc@{#2}{#1}{#3}%
}

% group starting with a blank space' ends here

% #1 -- call stack'
% #2 -- remaining sequence
% #3 -- parsed' sequence

\def\yypreparsetokens@q@@n@@#1#2#3{% nonempty group starting with a non blank, non brace token
\expandafter\yypreparsetokens@q@@n@@swap\expandafter{\eatone#2}{#1}{#30}%
}

\def\yypreparsetokens@q@@n@@swap#1#2#3{%
\yypreparsetokensequenc@{#2}{#1}{#3}%
}

% #1 -- string of category code 12 or 10 characters
% #2 -- string of category code 12 or 10 characters

\def\yycomparesimplestrings#1#2{%
\yystringempty{#1}{%
\yystringempty{#2}{\yyfirstoftwo}{\yysecondoftwo}%
}{\yycomparesimplestrings@{#1}{#2}}%
}

\def\yycomparesimplestrings@#1#2{% the first string is nonempty
\yystringempty{#2}{\yysecondoftwo}{\yycomparesimplestrings@@{#1}{#2}}%
}

\def\yycomparesimplestrings@@#1#2{% both strings are nonempty
\yystartsinspace{#1}{%
\yystartsinspace{#2}{\yyabsorbfirstspace{#1}{#2}}{\yysecondoftwo}%
}{%
\yystartsinspace{#2}{\yysecondoftwo}{\yyabsorbfirstnonspace{#1}{#2}}%
}
}

\def\yyabsorbfirstspace#1#2{%
\expandafter\yyabsorbfirstspac@swap\expandafter{\eatonespace#1}{#2}%
}

\def\yyabsorbfirstspac@swap#1#2{%
\expandafter\yyabsorbfirst@swap\expandafter{\eatonespace#2}{#1}%
}

\def\yyabsorbfirstnonspace#1#2{%
\expandafter\yyabsorbfirstnonspac@swap\expandafter{\eatone#1}{#2}%
}

\def\yyabsorbfirstnonspac@swap#1#2{%
\expandafter\yyabsorbfirst@swap\expandafter{\eatone#2}{#1}%
}

\def\yyabsorbfirst@swap#1#2{%
\yycomparesimplestrings{#2}{#1}%
}

% compare strings of category code 12' thread ends here

% #1 -- remaining parsed sequence
% #2 -- analysed sequence

\def\yyanalysetokens@#1#2{%
\yystringempty{#1}{{#2}}%
{\yyanalysetok@ns@#1\end{#2}}%
}

\def\yyanalysetok@ns@#1#2\end{%
\ifx#1.%
\expandafter\yyfirstoftwo
\else
\expandafter\yysecondoftwo
\fi
{\yygrabablank{#2}}%
{%
\ifx#1[% not a space, an opening brace
\expandafter\yyfirstoftwo
\else
\expandafter\yysecondoftwo
\fi
{%
\yydisableobrace{#2}%
}{%
\ifx#1]% not a space, a closing brace
\expandafter\yyfirstoftwo
\else
\expandafter\yysecondoftwo
\fi
{%
\yydisablecbrace{#2}%
}{% neither space nor brace
\yygrabtokenraw{#2}%
}%
}%
}%
}

% #1 -- remaining parsed sequence
% #2 -- analysed sequence
% #3 -- next token

\def\yygrabtokenraw#1#2#3{%
\expandafter\yyanalysetokens@swap\expandafter{\meaning#3}{#1}{#2}%
}

\def\yyanalysetokens@swap#1#2#3{%
\yyanalysetokens@{#2}{#3t#1e}%
}

\def\yygrabablank#1#2 {%
\yyanalysetokens@{#1}{#2s0e}%
}

% #1 -- remaining parsed sequence
% #2 -- analysed sequence

\def\yydisablecbrace#1#2{%
\yydisablecbrac@{}#1\relax#2\end
}

\def\yydisablecbrac@#1#2{%
\ifx#2\end
\yybreak{\yydisablecbrac@@{#1\expandafter\expandafter\expandafter}}%
\else
\yybreak{\yydisablecbrac@{#1\expandafter\expandafter\expandafter#2}}%
\yycontinue
}

\def\yydisablecbrac@@#1{%
\expandafter\expandafter\expandafter
\yydisablecbrace@@@#1\end
\expandafter\expandafter\expandafter
{\iffalse}\fi\string
}

\def\yydisablecbrace@@@#1\relax#2\end#3{%
\yystartsinspace{#3}%
{\expandafter\yyanalysetok@nsswap\expandafter{\eatonespace#3}{#1}{#2c1e}}%
{\expandafter\yyanalysetok@nsswap\expandafter{\eatone#3}{#1}{#2c2e}}%
}

\def\yyanalysetok@nsswap#1#2#3{%
\iffalse{\fi\yyanalysetokens@{#2}{#3}#1}%
}

% #1 -- remaining parsed sequence
% #2 -- analysed sequence

\def\yydisableobrace#1#2{%
\yydisableobrac@{}#1\relax#2\end
}

\def\yydisableobrac@#1#2{%
\ifx#2\end
\yybreak{\yydisableobrac@@{#1\expandafter\expandafter\expandafter}}%
\else
\yybreak{\yydisableobrac@{#1\expandafter\expandafter\expandafter#2}}%
\yycontinue
}

\def\yydisableobrac@@#1{%
\expandafter\expandafter\expandafter
\yydisableobrace@@@#1\end
\expandafter\expandafter\expandafter
{\iffalse}\fi\string
}

\def\yydisableobrace@@@#1\relax#2\end#3{%
\yystartsinspace{#3}%
{\expandafter\yyanalysetok@nsswap\expandafter{\eatonespace#3}{#1}{#2o1e}}%
{\expandafter\yyanalysetok@nsswap\expandafter{\eatone#3}{#1}{#2o2e}}%
}

\uccode\ =\-

% \dotspace expands into a character code \-, category code 10 token (funny space)

\uppercase{\def\dotspace{ }}

\toksa\expandafter\expandafter\expandafter{\expandafter\meaning\dotspace}

\toksb{-}

\toksc{#2}

\toksd\toksa

\yyreplacestring\toksb\in\toksa\with\toksc

\toksc{}
\yyreplacestring\toksb\in\toksd\with\toksc

\expandafter\def\expandafter\yymatchblankspac@\expandafter#\expandafter1\the\toksd{%
\yystringempty{#1}{\expandafter\yysecondofthree\expandafter{\string}}%
{\expandafter\yythirdofthree\expandafter{\string}}%
}

\edef\yymatchblankspace#1{% is it \catcode 10 token?
\noexpand\iffalse{\noexpand\fi
\noexpand\expandafter
\noexpand\yymatchblankspac@
\noexpand\meaning#1\the\toksd}%
}

% the idea behind the sequence below is that a leading character of category code 10
% is replaced either by a character of category code 10 and charachter code 32 or a character
% of category code 12 and character code other than 32
% note that while it is tempting to replace the definition below by something that ends in
% ... blank space #2{ ... with the hope of absorbing the result of \meaning in one step,
% this will not give the desired result in case of an active character,
% say, ~' that had been \let to the normal blank space

\expandafter\def\expandafter\yynormalizeblankspac@\expandafter#\expandafter1\the\toksd{}

\def\yystartsinspace#1{% is it \charcode 32, \catcode 10 token?
\iffalse{\fi\yystartsinspac@#1 }%
}

\def\yystartsinspac@#1 {%
\yystringempty{#1}{\expandafter\yysecondofthree\expandafter{\string}}{\expandafter\yythirdofthree\expandafter{\string}}%
}

\def\yystartsinbrace#1{%
\iffalse{{\fi
\if!\yytoks@mpty#1}}!%
\expandafter\yysecondoftwo
\else
\expandafter\yyfirstoftwo
\fi
}

\def\yystringempty#1{%
\iffalse{{{\fi
\ifcase\yytoks@mpty#1}}\@ne}\z@
\expandafter\yyfirstoftwo
\else
\expandafter\yysecondoftwo
\fi
}

\def\yytoks@mpty{%
\expandafter\eatone\expandafter{\expandafter{%
\ifcase\expandafter1\expandafter}\expandafter}\expandafter\fi\string
}

%% test code begins here

%\tracingmacros=3
%\tracingonline=3

\catcode\ =13\relax%
\def\actspace{ }%
\catcode\ =10\relax%

\catcode\.=13\relax%
\def\actdotspace{.}%
\catcode\.=12\relax%

\edef\makefunkydotspace{\let\expandafter\noexpand\actdotspace= \dotspace}
\edef\makefunkyspace{\let\expandafter\noexpand\actspace= \space}

\makefunkyspace
\makefunkydotspace

\catcode\<=1
\catcode\>=2
\uccode\<=32
\uccode\>=32

% inside the following sequence, < and > will become braces with character code 32 (space),
% \actspace will expand into an active character with character code 32, that has been \let to a
% character code 32, category code 10 token (space)

\uppercase{\edef\temptest{{ } \space\space\dotspace\expandafter\noexpand\actspace\expandafter\noexpand\actdotspace{<> {{}{{ u o l k kk
\end\noexpand\fi\noexpand\else\noexpand\iffalse{}} }}}}}

%\uppercase{\edef\temptest{\dotspace E <>}}

\show\temptest

\def\displaypreparse#1{%
\expandafter\errmessage\expandafter{\romannumeral-1\yypreparsetokensequenc@{\yyanalysetokens@}{#1}{}{}#1}%
}

\expandafter\displaypreparse\expandafter{\temptest}

\end

-
My apologies, I have omitted \catcode\@=11 at the beginning in order not to mess up the 'backtics' (I do not remember if \makeatletter` is available in plain TeX) – alexsh Mar 18 '14 at 23:29
thanks, I'll delete comment – David Carlisle Mar 18 '14 at 23:40