\chapter{XSB's POSIX Regular Expression and Wildcard Matching Packages}
\label{chap-posix}

\begin{center}
{\Large {\bf By Michael Kifer}}
\end{center}

XSB has an efficient interface to POSIX pattern regular expression and
wildcard matching functions.  To take advantage of these features, you must
build XSB using a C compiler that supports POSIX 1.0 (for regular
expression matching) and the forthcoming POSIX 2.0 (for wildcard matching).
The recent versions of GCC and SunPro compiler will do, as probably will
many other compilers. This also works under Windows, provided you install
Cygnus' CygWin and use GCC to compile.

\section{{\tt regmatch}: Regular Expression Matching and Substitution}

The following discussion assumes that you are familiar with the syntax of
regular expressions and have a reasonably good idea about their
capabilities. One easily accessible description of POSIX regular
expressions is found in the on-line Emacs manual.

The regular expression matching functionality is provided by the package
called {\tt Regmatch}. To use it interactively, type:
%%
\begin{verbatim}
   :- [regmatch].
\end{verbatim}
%%

If you are planning to use pattern matching from within an XSB program,
then you need to include the following directive:
%%
\begin{verbatim}
    :- import re_match/5, re_bulkmatch/5,
              re_substitute/4, re_substring/4,
              re_charlist_to_string/2
       from regmatch.
\end{verbatim}
%%

\paragraph{Matching.}
The predicates \verb|re_match/5| and \verb|re_bulkmatch/5| perform regular
expression matching.  The predicate \verb|re_substitute/4| replaces
substrings in a list with strings from another list and returns the
resulting new string.

The \verb|re_match/5| predicate has the following calling sequence:
%%
\begin{verbatim}
 re_match(+Regexp, +InputStr, +Offset, ?IgnoreCase, -MatchList)
\end{verbatim}
%%
{\tt Regexp} is a regular expression, {\it e.g.},
``\verb/abc([^;,]*); (dd|ee)*;/''. It can be a Prolog atom or string ({\it i.e.}, a list of
characters). The above expression matches any substring that has ``abc''
followed by a sequence of characters none of which is a ``;'' or a ``,'',
followed by a ``; '', followed by a sequence that consists of zero or more
of ``dd'' or ``ee'' segments, followed by a ``;''. An example of a string
where such a match can be found is ``\verb|123abc&*^; ddeedd;poi|''.

{\tt InputStr} is the string to be matched against. It can be a Prolog atom
or a string (list of characters). {\tt Offset} is an integer offset into
the string. The matching process starts at this offset. {\tt IgnoreCase}
indicates whether the case of the letters is to be ignored. If this
argument is an uninstantiated variable, then the case is \emph{not}
ignored. If this argument is bound to a non-variable, then the case
\emph{is} ignored.

The last argument, {\tt MatchList}, is used to return the results. It
must unify with a list of the form:
%%
\begin{verbatim}
    [match(beg_off0,end_off0), match(beg_off1,end_off1), ...]  
\end{verbatim}
%%
The term \verb|match(beg_off0,end_off0)| represents the substring
that matches the \emph{entire} regular expression,
and the terms \verb|match(beg_off1,end_off1)|, ..., represent the matches
corresponding to the {\em parenthesized subexpressions\/} of the regular
expression.
The terms {\tt beg\_off} and {\tt end\_off} above are integers that specify
beginning and ending offsets of the various matches. Thus, {\tt beg\_off0}
is the offset into {\tt InputStr} that points to the start of the maximal
substring that matches the entire regular expression; {\tt end\_off0} points to the
end of such a substring. In our case, the maximal matching substring is 
``\verb|abc&*^; ddeedd;|'' and the first term in the list returned by
%%
\begin{verbatim}
| ?- re_match('abc([^;,]*); (dd|ee)*;', '123abc&*^; ddeedd;poi', 0, _,L).  
\end{verbatim}
%%
is {\tt match(3,18)}.

The most powerful feature of POSIX pattern matching is the ability to
remember and return substrings matched by parenthesized subexpressions.
When the above predicate succeeds, the terms 2,3, etc., in the above list
represent the offsets for the matches corresponding to the parenthesized
expressions 1,2,etc.
For instance, our earlier regular expression 
  ``\verb/abc([^;,]*); (dd|ee)*;/'' has two parenthetical subexpressions, which
match ``\verb|&*^|'' and ``{\tt dd}, respectively. So, the complete output
from the above call is:
%%
\begin{verbatim}
L = [match(3,18),match(6,9),match(15,17)]  
\end{verbatim}
%%

The maximal number of parenthetical expressions supported by the Regmatch
package is 30. Partial matches to parenthetical expressions 31 and over are
discarded.

The match-terms corresponding to parenthetical expressions can sometimes
report ``\emph{no-use}.'' This is possible when the regular expression
specifies that zero or more occurrences of the parenthesized subexpression
must be matched, and the match was made using zero subexpressions. In this
case, the corresponding match term is \verb|match(-1,-1)|. For instance, 
%%
\begin{verbatim}
| ?- re_match('ab(de)*', 'abcd',0,_,L).
L = [match(0,2),match(-1,-1)]
yes
\end{verbatim}
%%
Here the match that was found is the substring ``ab'' and the parenthesized
subexpression ``de'' was not used. This fact is reported using the special
match term \verb|match(-1,-1)|.

Here is one more example of the power of POSIX regular expression matching:
%%
\begin{verbatim}
| ?- re_match("a(b*|e*)cd\\1",'abbbcdbbbbbo', 0, _, M).  
\end{verbatim}
%%
Here the result is:
%%
\begin{verbatim}
M = [match(0,9),match(1,4)]
\end{verbatim}
%%
The interesting features here are the positional parameter
$\backslash\backslash 1$ and the alternating parenthetical expression {\tt
a(b*|e*)}. The alternating parenthetical expression here can match any
sequence of b's \emph{or} any sequence of e's. Note that if the string to
be matched is not known when we write the program, we will not know a
priori which sequence will be matched: a sequence of b's or a sequence of e's.
Moreover, we do not even know the length of that sequence.

Now, suppose, we want to make sure that the matching substrings look like this:
%%
\begin{verbatim}
abbbcdbbb
aeeeecdeeee
abbbbbbcdbbbbbb
\end{verbatim}
%%
How can we make sure that the suffix that follows ``cd'' is exactly the same
string that is stuck between ``a'' and ``cd''? This is what
$\backslash\backslash 1$ precisely does: it represents the substring
matched by the first parenthetical expression. Similarly, you can use
$\backslash\backslash 2$, etc., if the regular expression contains more
than one parenthetical expression.

The following example illustrates the use of the offset argument:
%%
\begin{verbatim}
| ?- re_match("a(b*|e*)cd\\1",'abbbcdbbbbboabbbcdbbbbbo',2,_,M).  

M = [match(12,21),match(13,16)]  
\end{verbatim}
%%
Here, the string to be matched is double the string from the previous
example. However, because we said that matching should start at offset 2,
the first half of the string is not matched.

The \verb|re_match/5| predicate fails if {\tt Regexp} does not match {\tt
  InputStr} or if the term specified in {\tt MatchList} does not unify with
the result produced by the match.  Otherwise, it succeeds.

We should also note that parenthetical expressions can be represented
using the \verb|\(...\)| notation. What if you want to match a ``('' then?
You must escape it with a ``\verb|\\|'' then:
%%
\begin{verbatim}
| ?- re_match("a(b*)cd\\(",'abbbcd(bbo', 0, _, M).

M = [match(0,7),match(1,4)]
\end{verbatim}
%%
Now, what about matching the backslash itself? Try harder: you need four
backslashes: 
%%
\begin{verbatim}
| ?- re_match("a(b*)cd\\\\",'abbbcd\bbo', 0, _, M).

M = [match(0,7),match(1,4)]
\end{verbatim}
%%

The predicate \verb|re_bulkmatch/5| has the same calling sequence as
\verb|re_match/5|, and the meaning of the arguments is the same, except the
last (output) argument. The difference is that \verb|re_bulkmatch/5|
ignores parenthesized subexpressions in the regular expression and instead
of returning the matches corresponding to these parenthesized
subexpressions it returns the list of all matches for the top-level regular
expression. For instance, 
%%
\begin{verbatim}
| ?- re_bulkmatch('[^a-zA-Z0-9]+', '123&*-456 )7890% 123', 0, 1, X).

X = [match(3,6),match(9,11),match(15,17)]  
\end{verbatim}
%%

\paragraph{Extracting the matches.}
The predicate \verb|re_match/5| provides us with the offsets. How can we
actually get the matched substrings? This is done with the help of the
predicate \verb|re_substring/4|:
%%
\begin{verbatim}
    re_substring(+String, +BeginOffset, +EndOffset, -Result).
\end{verbatim}
%%

This predicate works exactly like {\tt substring/4} described in
Section~\ref{sec-strings}, except that the resulting substring is
not interned (if it is an atom). All you can do with this
string is to immediately convert it into a list (using {\tt atom\_codes/2})
or into a true atom (using {\tt intern\_string/2}, which must be imported
from module machine).

The reason for these complications is to allow the user to control the size
of the atom table. At present, XSB does not have atom table garbage
collection, so heavy use of string manipulation functions can result in
atom table overflow. This danger is particularly severe when XSB is used
for processing HTML pages. This predicate will become an alias to {\tt
  substring/4} when atom garbage collection will be added to XSB.

On the other hand, converting strings into lists (without interning them
first) is safe, because lists are garbage-collected in XSB Version 2.0.

Here is a complete example that shows matching followed by a subsequent 
extraction of the matches:
%%
\begin{verbatim}
| ?- import intern_string/2 from machine.

| ?- Str = 'abbbcd\bbo',
      re_match("a(b*)cd\\\\",Str,0,_,[match(X,Y), match(V,W)|L]),
      re_substring(Str,X,Y,UninternedMatch),
      intern_string(UninternedMatch,Match),
      re_substring(Str,V,W,UninternedParen1),
      atom_codes(UninternedParen1,Paren1).

Str = abbbcd\bbo
X = 0
Y = 7
V = 1
W = 4
L = []
UninternedMatch = abbbcd\
Match = abbbcd\
UninternedParen1 = bbb
Paren1 = [98,98,98]
\end{verbatim}
%%
Note that the strings {\tt UninternedMatch} and {\tt UninternedParen1}
cannot be used by themselves. In the first case, we converted the string
into a Prolog atom and in the second case into a string. The resulting
objects ({\tt Match} and {\tt Paren1}) can be used in further computations.

Observe that XSB reports that {\tt UninternedMatch} and {\tt
UninternedParen1} are both equal the string ``{\tt bbb}'', while {\tt
Match} --- the atom obtained from {\tt UninternedMatch} --- is different.
This is because {\tt UninternedMatch} and {\tt UninternedParen1} are
uninterned and both occupy the same physical space. Thus, the second call
to \verb|re_substring/4| overrides the value stored in this location by the
first call.

\paragraph{Substitution.}
The predicate \verb|re_substitute/4| has the following invocation:
%%
\begin{verbatim}
    re_substitute(+InputStr, +SubstrList, +SubstitutionList, -OutStr)  
\end{verbatim}
%%
This predicate works exactly like {\tt string\_substitute/4} described in
Section~\ref{sec-strings}, except that the result of the substitution is
not interned (for the same reason as in {\tt re\_substring/4}. This
predicate will become an alias to {\tt string\_substitute/4} when atom
garbage collection will be added to XSB.
%%
%%
\begin{verbatim}
| ?- re_bulkmatch('[^a-zA-Z0-9]+', '123&*-456 )7890| 123', 0, _, X),
     re_substitute('123&*-456 )7890| 123', X, ['+++'], Y).

X = [match(3,6),match(9,11),match(15,17)]
Y = 123+++456+++7890+++123
\end{verbatim}
%%

\paragraph{Efficiency considerations.}
%%
\begin{itemize}
  \item  Try not to work with too many regular expressions at once.
    Before a regular expression can be used, it must be compiled (which
    {\tt re\_match/5} does automatically).
    {\tt re\_match/5} maintains a cache of compiled regular expressions, so
    they do not need to be compiled each time they are used. However, if
    more than 8--10 expressions are used simultaneously, repeated
    recompilation might result.
  \item When a list of characters is passed to any one of the above
    predicates, it is converted into a C string. This can be expensive, if
    done too often for the same string.
    
    One way to circumvent the problem is to use {\tt atom\_codes/2} to
    first convert the list into an atom and then use that atom repeatedly
    in the match operations. One problem here might be the aforementioned
    overflow of the atom table. So, if this is a concern, the following
    predicate (which always succeeds) can help:
%%
\begin{verbatim}
   re_charlist_to_string(+ListOfCharacters, -String)  
\end{verbatim}
%%
    This predicate converts lists of characters into uninterned strings,
    which can be used without the fear of atom table overflow:
%%
\begin{verbatim}
| ?- re_charlist_to_string("abcdefg",L).

L = abcdefg  
\end{verbatim}
%%
    The resulting string can be passed to {\tt re\_match/5}, {\tt
    re\_substitute/5}, and {\tt re\_substring/4} for further processing.
  
  Note, however: you cannot call {\tt re\_charlist\_to\_string} before you
  finished working with the string generated by the previous call: all
  calls to this function use the same static buffer to hold the output
  string, so each subsequent call to {\tt re\_charlist\_to\_string} will
  override the previously generated strings.
\end{itemize}
%%


\section{{\tt wildmatch}: Wildcard Matching and Globing}

These interfaces are implemented using the {\tt Wildmatch} package of XSB.
This package provides the following functionality: 
%%
\begin{enumerate}
\item Telling whether a wildcard, like the ones used in Unix shells, match
  against a given string. Wildcards supported are of the kind available in
  tcsh or bash. Alternating characters ({\it e.g.}, ``\verb|[abc]|'' or
  ``\verb|[^abc]|'') are supported.
\item Finding the list of all file names in a given directory that match a
  given wildcard. This facility generalizes {\tt directory/2} (in module {\tt
    directory}), and it is much more efficient.
\item String conversion to lower and upper case.
\end{enumerate}
%%

To use this package, you need to type:
%%
\begin{verbatim}
| ?- [wildmatch].  
\end{verbatim}
%%
If you are planning to use it in an XSB program, you need
this directive:
%%
\begin{verbatim}
:- import glob_directory/4, wildmatch/3, convert_string/3 from wildmatch.
\end{verbatim}
%%

The calling sequence for \verb|glob_directory/4| is:
%%
\begin{verbatim}
   glob_directory(+Wildcard, +Directory, ?MarkDirs, -FileList)  
\end{verbatim}
%%
The parameter {\tt Wildcard} can be either a Prolog atom or a Prolog
string. {\tt Directory} is also an atom or a string; it specifies the
directory to be globbed. {\tt MarkDirs} indicates whether directory names
should be decorated with a trailing slash: if {\tt MarkDirs} is bound, then
directories will be so decorated. If MarkDirs is an unbound variable, then
trailing slashes will not be added.

{\tt FileList} gets the list of files in {\tt Directory} that match {\tt
  Wildcard}.  If {\tt Directory} is bound to an atom, then {\tt FileList}
gets bound to a list of atoms; if {\tt Directory} is a Prolog string, then
{\tt FileList} will be bound to a list of strings as well.

This predicate succeeds is at least one match is found. If no matches are
found or if {\tt Directory} does not exist or cannot be read, then the
predicate fails.

The calling sequence for {\tt wildmatch/3}  is as follows:
%%
\begin{verbatim}
    wildmatch(+Wildcard, +String, ?IgnoreCase)  
\end{verbatim}
%%
{\tt Wildcard} is the same as before. {\tt String} represents the string to
be matched against {\tt Wildcard}. Like {\tt Wildcard}, {\tt String} can be
an atom or a string. {\tt IgnoreCase} indicates whether case of letters
should be ignored during matching. Namely, if this argument is bound to a
non-variable, then the case of letters is ignored. Otherwise, if {\tt
  IgnoreCase} is a variable, then the case of letters is preserved.

This predicate succeeds when {\tt Wildcard} matches {\tt String} and fails
otherwise.

The calling sequence for {\tt convert\_string/3}  is as follows:
%%
\begin{verbatim}
    convert_string(+InputString, +OutputString, +ConversionFlag)  
\end{verbatim}
%%
The input string must be an atom or a character list. The output string
must be unbound. Its type will ``atom'' if so was the input and it will be
a character list if so was the input string. The conversion flag must be
the atom {\tt tolower} or {\tt toupper}. 

This predicate always succeeds, unless there was an error, such as wrong
type argument passed as a parameter.




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "manual2"
%%% End: 
