# Capacity exceeded while implementing lookup table

I'd like to implement simple key-value lookup table. I wanted to do it in functional fashion, so I've defined initial state of such table as get function causing error (as table is initially empty). Then I've defined put function that redefined get do that if its argument equals get argument, it should return value and it should fall back to original get in other situation.

Generally, it should become stack of nested ifs. I did it in dedicated package.

If key is in table, then everything works fine. There is a problem if I try to get key that is not there - it should cause error, but instead it causes stack overflow:

\lookupPut{x}{foo}
\lookupPut{y}{bar}
\lookupGet{x} % gives foo
\lookupGet{y} % gives bar
\lookupGet{z} % causes 'capacity exceeded'


TeX capacity exceeded, sorry [input stack size=5000]. \lookupGet{z}

Here's full package source:

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{lookup}

\RequirePackage{ifthen}

\newcommand{\lookupGet}[1]{
\PackageError
{customdetails}
{No #1 key in lookup!}
{
Key #1 was not found in lookup. You can insert it with lookupPut(key, value).
}
}

\newcommand{\lookupPut}[2]{
\let\@lookupHelper\lookupGet
\renewcommand{\lookupGet}[1]{
\PackageInfo{lookup}{get key X #1 X} % X characters are to be sure where string starts and ends
\PackageInfo{lookup}{get val X #2 X}
\PackageInfo{lookup}{get 1st X ##1 X}
\ifthenelse{
\equal{##1}{#1}
}
{#2}
{\@lookupHelper{##1}}
}
}

\endinput


I've got sure that this is proper way to save old version of function - I know that if I use \let, it assigns value resolved at definintion moment, not usage moment (sorry if I'm not clear, I'm still kind of new to TeX and it's naming).

Whether lookup table is good idea is not the case here.

PS. I've got no idea what tags should I use here. If you have one - go on, and edit, please ;)

• Well naturally you get a loop. You are calling \lookupPut twice and the second time \@lookupHelper gets the meaning of the redefined \lookupGet. Use \show to get an idea of the actual definitions of your commands. – Ulrike Fischer Jun 10 '15 at 8:40
• Oh, a way to debug, thanks! I didn't know about that command. I'll try it later and see what I come up with. If I solve this, I'll post the answer here too. – Filip Malczak Jun 10 '15 at 9:00

The easiest way to implement a lookup is using the hash table of TeX by defining a macro \lookup@<key> which expands to <value>:

%%% lookup.sty %%%
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{lookup}[2015/06/10 Lookup for custom details]

\newcommand{\lookupGet}[1]{%
\@ifundefined{lookup@#1}{%
\PackageError{lookup}{No #1 key in lookup}{%
You can insert it with \string\lookupPut{key}{value}.%
}%
}{%
\@nameuse{lookup@#1}%
}%
}
\newcommand{\lookupPut}[2]{%
\@namedef{lookup@#1}{#2}%
}
\endinput


Average runtime complexity is constant: O(1).

The implementation idea of the question checks each key one after another until the right key is found. That makes a linear average runtime complexity: O(n).

The implementation could be done by collecting the key value pairs in a macro. Operations like put, get, lookup, delete could then be implemented by modifying and questioning the list. However the runtime complexity is at least O(n), because the data macro needs to be expanded at least once with all n entries.

Further remarks:

• Line ends are usually converted to spaces. The code in the question have lots of unwanted spaces, they do not vanish in horizontal mode.

• The endless loop is already explained by Ulrike's comment. Extending a macro definition can be done in a better way without the problematic \let assignment using patch commands of package etoolbox, e.g. see macros \appto, \preto.

• @FilipMalczak Useful debug commands are \tracingmacros=1 and \tracingassigns=1 here to show, the macro expansions and assignments in the log. – Heiko Oberdiek Jun 10 '15 at 9:13
• Perhaps note that the 'get' operation can be made expandable but not if an error has to be raised if it fails. (Or at least one can sort out an expandable error but it's trickier.) – Joseph Wright Jun 10 '15 at 9:26
• This works nicely, until the string to be looked up contains itself active content, it seems. – Joachim Breitner Oct 29 '17 at 14:06
• @JoachimBreitner The name of the string should expand to a plain text string like the argument of \label. – Heiko Oberdiek Oct 29 '17 at 16:08

Heiko has already explained the cause of the error. Here's a different implementation for your lookup table.

You can define as many tables as you want and also retrieve values in an expandable way (without error checking, though), but also with error checking; an optional argument to \lookupGet allows to store the item in a control sequence.

## file lookup.sty

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{lookup}

\RequirePackage{xparse}

\ExplSyntaxOn
\DeclareExpandableDocumentCommand{\lookupGetX}{O{default}m}
{
\lookup_get_x:nn { #1 } { #2 }
}
\NewDocumentCommand{\lookupGet}{O{default}mo}
{
\lookup_get_check:nn { #1 } { #2 }
\IfValueTF { #3 }
{
\tl_set_eq:NN #3 \l_lookup_item_tl
}
{
\tl_use:N \l_lookup_item_tl
}
}
\NewDocumentCommand{\lookupPut}{O{default}mm}
{
\lookup_put:nnn { #1 } { #2 } { #3 }
}

\prop_new:N \l_lookup_table_default_prop % the default table
\tl_new:N \l_lookup_item_tl

\cs_new:Npn \lookup_get_x:nn #1 #2
{% syntactic sugar for \prop_item:nn
\prop_item:cn {l_lookup_table_#1_prop} { #2 }
}

\cs_new_protected:Npn \lookup_get_check:nn #1 #2
{
\prop_if_exist:cTF { l_lookup_table_#1_prop }
{% the table exists
\prop_get:cnN { l_lookup_table_#1_prop } { #2 } \l_lookup_item_tl
\quark_if_no_value:VT \l_lookup_item_tl
{% no value available
\msg_error:nnnn { lookup } { no~item } { #1 } { #2 }
\tl_set:Nn \l_lookup_item_tl { ERROR }
}
}
{% the table doesn't exist
\msg_error:nnn { lookup }{ no~table } { #1 }
}
}
\cs_generate_variant:Nn \quark_if_no_value:nT { V }

\cs_new_protected:Npn \lookup_put:nnn #1 #2 #3
{
\prop_if_exist:cF { l_lookup_table_#1_prop }
{
\prop_new:c { l_lookup_table_#1_prop }
}
\prop_put:cnn { l_lookup_table_#1_prop } { #2 } { #3 }
}

\msg_new:nnnn { lookup } { no~item }
{
No~'#2'~key~in~lookup~table~(#1).
}
{
Key~'#2'~was~not~found~in~lookup~table~(#1).~
You~can~insert~it~with~\tl_to_str:N \lookupPut[<table>]{<key>}{<value>}.
}

\msg_new:nnnn { lookup } { no~table }
{
No~'#1'~lookup~table.
}
{
The~lookup~table~'#2'~does~not~exist.
}
\ExplSyntaxOff

\endinput


## file testlookup.tex

\documentclass{article}
\usepackage{lookup}

\begin{document}

% store some values
\lookupPut{x}{foo}
\lookupPut{y}{bar}

\lookupGet{x} % gives foo

\lookupGet{y} % gives bar

\lookupGet{z} % gives ERROR

\lookupGet{y}[\test]
\texttt{\meaning\test} % gives macro:->bar

% a new lookup table

\lookupPut[new]{newx}{newfoo}

\lookupGet[new]{newx} % gives newfoo

\lookupGet[new]{newy} % gives ERROR

\lookupGet[inexistent]{Hey!} % gives ERROR

% check the fully expandable version

\edef\test{\lookupGetX{x} \lookupGetX[new]{newx}}

\texttt{\meaning\test} % gives macro:-> foo newfoo

\end{document}


## terminal output

This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015) (preloaded format=pdflatex)
restricted \write18 enabled.
entering extended mode
(./testlookup.tex
LaTeX2e <2015/01/01>
Babel <3.9l> and hyphenation patterns for 79 languages loaded.
(/usr/local/texlive/2015/texmf-dist/tex/latex/base/article.cls
Document Class: article 2014/09/29 v1.4h Standard LaTeX document class
(/usr/local/texlive/2015/texmf-dist/tex/latex/base/size10.clo)) (./lookup.sty
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3packages/xparse/xparse.sty
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/expl3.sty
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/expl3-code.tex)
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/l3unicode-data.def)
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/l3pdfmode.def))))
(./testlookup.aux)

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!
! lookup error: "no item"
!
! No 'z' key in lookup table (default).
!
! See the lookup documentation for further information.
!
! For immediate help type H <return>.
!...............................................

l.14 \lookupGet{z}
% gives ERROR
?

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!
! lookup error: "no item"
!
! No 'newy' key in lookup table (new).
!
! See the lookup documentation for further information.
!
! For immediate help type H <return>.
!...............................................

l.25 \lookupGet[new]{newy}
% gives ERROR
?

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!
! lookup error: "no table"
!
! No 'inexistent' lookup table.
!
! See the lookup documentation for further information.
!
! For immediate help type H <return>.
!...............................................

l.27 \lookupGet[inexistent]{Hey!}
% gives ERROR
?
[1{/usr/local/texlive/2015/texmf-var/fonts/map/pdftex/updmap/pdftex.map}]
(./testlookup.aux) )</usr/local/texlive/2015/texmf-dist/fonts/type1/public/amsf
onts/cm/cmr10.pfb></usr/local/texlive/2015/texmf-dist/fonts/type1/public/amsfon
ts/cm/cmtt10.pfb>
Output written on testlookup.pdf (1 page, 23121 bytes).
Transcript written on testlookup.log.


## Explanations

With expl3, the programming framework of the future LaTeX, we have available several data type, among which there are property lists, with reference name prop.

A property list variable has a name like \l_<module>_<proper name>_prop or \g_<module>_<proper name>_prop, where l and g denote whether the variable is managed locally or globally.

The package xparse automatically loads expl3 and \ExplSyntaxOn enters the programming framework.

First I define three user level macros, that simply normalize the arguments; for instance \lookupGetX is declared fully expandable and has an optional argument, with default value default and a mandatory argument.

Let's examine \lookup_get_x:nn; it just calls

\prop_item:cn {l_lookup_table_#1_prop} { #2 }


which means: get the value of the property list named as told by the first argument corresponding to the key given in the second argument.

A property list is a collection of key-value pairs. One says

\prop_put:Nnn \l_foo_bar_prop { x } { abc }


so that

\prop_item:Nn \l_foo_bar_prop { x }


will deliver the value associated to the key x in the given property list. However, by changing N with c in the functions we use, we give the name of the variable in braces without the backslash, so we're allowed to use a parameter there. Hence a call

\prop_item:cn { l_lookup_table_default_prop } { x }


will do the same as

\prop_item:Nn \l_lookup_table_default_prop { x }


but, as you see, we can inject different property list names based on an argument to the functions we use.

The function \prop_item:Nn (or its variant \prop_item:cn) returns nothing if the key is not existent. This is why I define another version that does the necessary checks but has the defect it cannot be used in \edef or \write situations. This is \lookup_get_check:nn that uses the second method for retrieving values from property lists:

\prop_get:NnN \l_lookup_table_default_prop { x } \l_lookup_item_tl


retrieves the value associated to the key x (as before I use the variant \prop_get:cnN for being able to name the variable) and stores it in the token list variable \l_lookup_item_tl.

In case the key is not existent, the stored value is a special token \q_no_value that can be looked for and this is used for the error checking via the conditional \quark_if_no_value:VTF that follows the true branch if the variable given as first argument only contains the special token and the false branch otherwise. The true branch issues an error message and changes the value in the token list variable to something more sensible than the special token.

Before trying to retrieve the value, though, a check is made for existence of the referred property list variable, with \prop_if_exist:cTF that follows the true branch if the property list has been set up. In this case the false branch issues a proper error message.

The good news is that, in the programming framework, up to \ExplSyntaxOff, spaces, end-of-lines and blank lines are ignored (except in some special cases). Your code is full of spurious spaces, with this programming style one explicitly tells where spaces are desired, by typing ~.

More on this can be found with texdoc expl3 and texdoc interface3.