\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#195: A Unique Prefix Handling Command}
\date{May 02, 2004}
\author{Peter Spjuth, Peter Spjuth}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#195}&\textbf{A Unique Prefix Handling Command}\\\hline
Author&

Peter Spjuth \tipmail{peter.spjuth}{space.se}
\par
Peter Spjuth \tipmail{peter.spjuth}{gmail.com}
\\
Created&Sunday, \(\text{2}^{\text{nd}}\) May 2004\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.18 $\\
Keywords&Tcl\\
Obsoletes&105\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP adds a new command to support matching of strings to unique prefixes of patterns, similar to Tcl's existing subcommand-name matching or Tk's option-name matching.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

When code (particularly in script libraries) wants to support shortest unique prefix matching in the manner of the Tcl core (as provided by \textit{Tcl\_GetIndexFromObj}) currently either the prefixes have to be precomputed (by hand or by script) or the matching has to be done backwards. In the first case, this is either error-prone or requires an extra piece of code that has to be developed by the programmer. In the second case, the code has to be converted into a pattern which is matched against the list of supported options in some way, which is either inefficient or has hazards if the string being matched contains characters that are meaningful to the matching engine being used. Instead, it would be far nicer if we could make the core support this directly, so that script authors could just say what they mean.

See also \cite{tip105}, which the text above comes from.

Another benefit of this command is getting an error message that looks like those nice and informative error messages that built in commands have. The proposed command includes a flag to control the error behaviour.

Another use of prefix matching is for completion, such as a combobox showing matching alternatives, or tab completion at a prompt.

The former needs a list of matching elements, and the latter needs a longest common prefix. 

These functionalities are similiar enough to group them but different enought to make it a bad idea for flags, so a prefix ensemble seems approriate for them.

\section{Proposed Change}

To support this, I propose adding a \textbf{::tcl::prefix} ensemble with the following subcommands
\begin{itemize}
\item{}
\textbf{prefix} \textbf{match} ?\textbf{-exact}? ?\textbf{-message} \textit{string}? ?\textbf{-error} \textit{options}? \textit{list} \textit{string}
\item{}
\textbf{prefix} \textbf{longest} \textit{list} \textit{string}
\item{}
\textbf{prefix} \textbf{all} \textit{list} \textit{string}
\end{itemize}

All commands are given a list of possibilities and a string to match.

\textbf{prefix} \textbf{match} returns the matching element in the list or an error. Basically it does what \textit{Tcl\_GetIndexFromObj} does except it returns a string instead of an index. The options \textbf{-exact} and \textbf{-message} corresponds to the \textit{flags} and \textit{msg} arguments to \textit{Tcl\_GetIndexFromObj}. The default value for \textbf{-message} is ``option''.

The \textbf{-error} options are used when no match is found. If \textbf{-error} is empty, no error is generated and an empty string is returned. Otherwise the options are used as \textbf{return} options when generating the error message. The default corresponds to setting ``-level 0''. Example: If \textbf{-error} ``-errorcode MyError -level 1'' is used, an error would be generated as [return -errorcode MyError -level 1 -code error ``ErrMsg''].

\textbf{prefix} \textbf{longest} returns the longest common prefix within the group that matches the given string. If there is no match, an empty string is returned.

\textbf{prefix} \textbf{all} returns a list of all matching elements.

\section{Examples}

Basic use:
\begingroup\small\begin{verbatim}
% namespace import ::tcl::prefix
% prefix match {apa bepa cepa} apa
apa
% prefix match {apa bepa cepa} a
apa
% prefix match -exact {apa bepa cepa} a
bad option "a": must be apa, bepa, or cepa
% prefix match -message "switch" {apa ada bepa cepa} a
ambiguous switch "a": must be apa, ada, bepa, or cepa
% prefix longest {fblocked fconfigure fcopy file fileevent flush} fc
fco
% prefix all {fblocked fconfigure fcopy file fileevent flush} fc
fconfigure fcopy
\end{verbatim}
\endgroup

Simplifying option matching:
\begingroup\small\begin{verbatim}
array set opts {-apa 1 -bepa "" -cepa 0}
foreach {arg val} $args {
    set opts([prefix match {-apa -bepa -cepa} $arg]) $val
}
\end{verbatim}
\endgroup

Switch similar to \cite{tip105}:
\begingroup\small\begin{verbatim}
switch -- [prefix match {apa bepa cepa} $arg] {
    apa  { }
    bepa { }
    cepa { }
}
\end{verbatim}
\endgroup

\section{Alternative names}

Alternative names for the command that have been suggested are \textbf{prefix}, \textbf{string prefix}, \textbf{string disambiguate}, \textbf{string prefixmatch}, \textbf{string matchprefix} and \textbf{lsearch -prefix}.

Any name based on \textit{Tcl\_GetIndexFromObj} feels wrong since this command does not get any index.

\section{Discussion}

Pascal Scheffers wrote:

I am not very fond of new toplevel commands, as they have a habit of breaking existing code, or, more likely, being redefined by existing code. How about \textbf{string prefix ...} or \textbf{lsearch -prefix}? It feels like something that could logically reside inside string handling or list handling.

Donal Fellows wrote:

Hmm, a new matching style for \textbf{lsearch} could work (yet another option for an overly scary command!) especially in conjunction with some of the other options like -inline, but I suspect it'll have to be \textbf{string prefix} or something like that since then we can easily state that the behaviour is not to necessarily return the first matching element. That was what scuppered \#105 after all (much to my annoyance.)

Peter Spjuth: TIP was at this point altered to suggest \textbf{string disambiguate} after a suggestion from Donal.

Donal Fellows wrote:

I'd suggest that the \textbf{-exact} option be dropped, as it is trivially implementable using \textbf{lsearch -exact}, \textbf{dict exists}, \textbf{info exists}, \textbf{switch}, etc. It's also corresponding to a very rarely used flag to Tcl\_GetIndexFromObj.

Peter Spjuth: Other ways to do \textbf{-exact} doesn't give the standardized error message so it has some value for those that want that functionality. The Core uses TCL\_EXACT in a few places where it makes sense so the flag can be useful.

Voices were raised against the proposed \textbf{string disambiguate} and Jeff Hobbs pointed out other prefix related functions that are useful. This lead to the prefix ensemble suggestion.

\section{Reference Implementation}

Partial implementation at: \url{https://sourceforge.net/support/tracker.php?aid=1040206}

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\begin{thebibliography}{TIP \#1}
\addcontentsline{toc}{section}{References}
\bibitem[TIP \#105]{tip105}
Donal K. Fellows,
\emph{Add Prefix Matching for Switch},
on-line at \url{http://purl.org/tcl/tip/105.html}
\end{thebibliography}
\end{document}
