
/* Pure regex interface. */

/* NOTE: This module isn't loaded by the standard prelude, so you'll have to
   add the clause 'using regex;' to your programs in which you want to use
   this interface. */

/* Copyright (c) 2012 by Albert Graef <Dr.Graef@t-online.de>.

   This file is part of the Pure standard library.

   The Pure standard library is free software: you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation, either version 3 of the License,
   or (at your option) any later version.

   Pure is distributed in the hope that it will be useful, but WITHOUT ANY
   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
   FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
   more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

/* ..

   Regex Matching
   --------------

   .. module:: regex

   Please note that, as of Pure 0.48, this part of the system interface is not
   included in the system module any more, but is provided as a separate regex
   module which can be used independently of the system module. To use the
   operations of this module, add the following import declaration to your
   program::

     using regex;

   Since the POSIX regex functions (``regcomp`` and ``regexec``) have a
   somewhat difficult calling sequence, this module provides a couple of
   rather elaborate high-level wrapper functions for use in Pure programs.
   These are implemented in terms of a low-level interface provided in the
   runtime. (The low-level interface isn't documented here, but these
   functions are also callable if you want to create your own regular
   expression engines in Pure.  You might wish to take a look at the
   implementation of the high-level functions in regex.pure to see how this
   can be done.) */

using namespace __C;

namespace __C;
// Initialize some global variables needed for the regex functions. After
// loading this module, see show -gcv * for a list of these.
extern void pure_regex_vars(); pure_regex_vars;
// Lowlevel interface to the POSIX regex functions provided in the runtime.
extern void* pure_regcomp(char* pat, int cflags) = regcomp;
extern int pure_regexec(void* reg, char* s, int eflags) = regexec;
extern int pure_regnext(void* reg, int overlap) = regnext;
extern void pure_regdone(void* reg) = regdone;
extern void pure_regfree(void* reg) = regfree;
extern int pure_regstatus(void* reg) = regstatus;
extern expr* pure_regerror(void* reg) = regerror;
extern expr* pure_regmatch(void* reg) = regmatch;
extern expr* pure_regskip(void* reg) = regskip;
namespace;

public regerr;

/* .. function:: regex pat cflags s eflags

      Compiles and matches a regex in one go, and returns the list of
      submatches (if any).

      :param string pat: the regular expression pattern
      :param int cflags: the compilation flags (bitwise or of any of the flags
      	     	 	 accepted by regcomp(3))
      :param string s:   the subject string to be matched
      :param int eflags: the matching execution flags (bitwise or of any of the
      	     	 	 flags accepted by regexec(3))

   Symbolic :const:`REG_*` constants are provided for the different flag
   values, see the regcomp(3) manpage for an explanation of these. Two
   particularly important compilation flags (to be included in the ``cflags``
   argument) are :const:`REG_NOSUB`, which prevents submatches to be computed,
   and :const:`REG_EXTENDED`, which switches :func:`regex` from "basic" to
   "extended" regular expressions so that it understands all the regular
   expression elements of egrep(1) in the pattern argument.

   Depending on the flags and the outcome of the operation, the result of this
   function can take one of the following forms:

   - ``regerr code msg``: This indicates an error during compilation of the
     pattern (e.g., if there was a syntax error in the pattern). ``code`` is
     the nonzero integer code returned by ``regcomp``, and ``msg`` is the
     corresponding error message string, as returned by ``regerror``. You can
     redefine the :func:`regerr` function as appropriate for your application
     (e.g., if you'd like to print an error message or throw an exception).

   - ``0`` or ``1``: Just a truth value indicates whether the pattern matched
     or not. This will be the form of the result if the :const:`REG_NOSUB`
     flag was specified for compilation, indicating that no submatch
     information is to be computed.

   - ``0`` (indicating no match), or ``1`` (indicating a successful match),
     where the latter value is followed by a tuple of ``(pos,substr)`` pairs
     for each submatch. This will be the form of the result only if the
     :const:`REG_NOSUB` flag was *not* specified for compilation, so that
     submatch information is available.

   Note that, according to POSIX semantics, a return value of 1 does *not*
   generally mean that the entire subject string was matched, unless you
   explicitly tie the pattern to the beginning (``^``) and end (``$``) of the
   string.

   If the result takes the latter form, each ``(pos,substr)`` pair indicates a
   portion of the subject string which was matched; ``pos`` is the position at
   which the match starts, and ``substr`` is the substring (starting at
   position ``pos``) which was matched. The first ``(pos,substr)`` pair always
   indicates which portion of the string was matched by the entire pattern,
   the remaining pairs represent submatches for the parenthesized subpatterns
   of the pattern, as described on the regcomp(3) manual page. Note that some
   submatches may be empty (if they matched the empty string), in which case a
   pair ``(pos,"")`` indicates the (nonnegative) position ``pos`` where the
   subpattern matched the empty string. Other submatches may not participate
   in the match at all, in which case the pair ``(-1,"")`` is returned. */

regex pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else if regexec re s eflags then 0
  else 1,regmatch re when re = sentry regfree (regcomp pat cflags) end;

/* ..

   The following helper functions are provided to analyze the result returned
   by :func:`regex`.

   .. function:: reg_result res

      Returns the result of a :func:`regex` call, i.e., a :func:`regerr` term
      if compilation failed, and a flag indicating whether the match was
      successful otherwise. */

reg_result (regerr code msg) = regerr code msg;
reg_result b::int = b;
reg_result (b::int,_) = b;

/* .. function:: reg_info res

      Returns the submatch info if any, otherwise it returns ``()``. */

reg_info (_::int,info) = info;
reg_info _ = () otherwise;

/* .. function:: reg n info

      Returns the ``n``\ th submatch of the given submatch info, where ``info``
      is the result of a :func:`reg_info` call. */

reg 0 (p,s,_) = p,s;
reg 0 (p,s) = p,s;
reg n::int (_,_,infos) = reg (n-1) infos if n>0;

/* .. function:: regs info

      Returns all valid submatches, i.e., the list of all triples ``(n,p,s)``
      for which ``reg n == (p,s)`` with ``p>=0``. */

regs info = myregs 0 info with
  myregs n (p,s,infos)	= (n,p,s):myregs (n+1) infos if p>=0;
			= myregs (n+1) infos otherwise;
  myregs n (p,s)	= [(n,p,s)] if p>=0;
			= [] otherwise;
end;

/* ..

   In addition, the following convenience functions are provided to perform
   global regex searches, to perform substitutions, and to tokenize a string
   according to a given delimiter regex.

   .. function:: regexg f pat cflags s eflags

      Perform a global regular expression search. This routine will scan the
      entire string for (non-overlapping) instances of the pattern, applies
      the given function ``f`` to the ``reg_info`` for each match, and
      collects all results in a list. Note: Never specify the
      :const:`REG_NOSUB` flag with this function, it needs the submatch
      info. */

regexg f pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else iterwhile check next first
with
  first = if regexec re s eflags then () else f (regmatch re);
  next _ = if regnext re 0 then () else f (regmatch re);
  check _ = regstatus re == 0;
end when re = sentry regfree (regcomp pat cflags) end
if ~(cflags and REG_NOSUB);

/* .. function:: regexgg f pat cflags s eflags

      This works like :func:`regexg`, but allows overlapping matches. */

regexgg f pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else iterwhile check next first
with
  first = if regexec re s eflags then () else f (regmatch re);
  next _ = if regnext re 1 then () else f (regmatch re);
  check _ = regstatus re == 0;
end when re = sentry regfree (regcomp pat cflags) end
if ~(cflags and REG_NOSUB);

/* .. function:: regsub f pat cflags s eflags

      Replaces all non-overlapping instances of a pattern with a computed
      substitution string. To these ends, the given function ``f`` is applied
      to the :func:`reg_info` for each match. The result string is then
      obtained by concatenating ``f info`` for all matches, with the unmatched
      portions of the string in between. To make this work, ``f`` must always
      return a string value; otherwise, :func:`regsub` throws a
      :cons:`bad_string_value` exception. */

regsub f pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else strcat (iterwhile check next first) + regskip re
with
  first = if regexec re s eflags then () else regskip re+h (f (regmatch re));
  next _ = if regnext re 0 then () else regskip re+h (f (regmatch re));
  check _ = regstatus re == 0;
  h x::string = x; h x = throw (bad_string_value x) otherwise;
end when re = sentry regfree (regcomp pat cflags) end
if ~(cflags and REG_NOSUB);

/* .. function:: regsplit pat cflags s eflags

      Splits a string into constituents delimited by substrings matching the
      given pattern. */

regsplit pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else if null s then []
  else iterwhile check next first + [regskip re]
with
  first = if regexec re s eflags then () else regskip re;
  next _ = if regnext re 0 then () else regskip re;
  check _ = regstatus re == 0;
end when re = sentry regfree (regcomp pat cflags) end
if ~(cflags and REG_NOSUB);

/* ..

   Please note that these operations all operate in an eager fashion, i.e.,
   they process the entire input string in one go. This may be unwieldy or at
   least inefficient for huge amounts of text. As a remedy, the following lazy
   alternatives are available:

   .. function:: regexgs f pat cflags s eflags
                 regexggs f pat cflags s eflags
                 regsplits pat cflags s eflags

      These work like :func:`regexg`, :func:`regexgg` and :func:`regsplit`
      above, but return a stream result which enables you to process the
      matches one by one, using "call by need" evaluation. */

regexgs f pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else takewhile check (iterate next first)
with
  first = if regexec re s eflags then () else f (regmatch re);
  next _ = if regnext re 0 then () else f (regmatch re);
  check _ = regstatus re == 0;
end when re = sentry regfree (regcomp pat cflags) end
if ~(cflags and REG_NOSUB);

regexggs f pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else takewhile check (iterate next first)
with
  first = if regexec re s eflags then () else f (regmatch re);
  next _ = if regnext re 1 then () else f (regmatch re);
  check _ = regstatus re == 0;
end when re = sentry regfree (regcomp pat cflags) end
if ~(cflags and REG_NOSUB);

regsplits pat::string cflags::int s::string eflags::int
= if regstatus re then regerr (regstatus re) (regerror re)
  else if null s then []
  else takewhile check (iterate next first) + [regskip re]&
with
  first = if regexec re s eflags then () else regskip re;
  next _ = if regnext re 0 then () else regskip re;
  check _ = regstatus re == 0;
  /* We need fully lazy stream concatenation here. (The standard + operator
     isn't lazy enough, because it's also used for arithmetic operations.) */
  []+ys = ys; (x:xs)+ys = x:(xs+ys)&;
end when re = sentry regfree (regcomp pat cflags) end
if ~(cflags and REG_NOSUB);

/* ..

   Basic Examples
   ~~~~~~~~~~~~~~

   Let's have a look at some simple examples::

     > let pat = "[[:alpha:]][[:alnum:]]*";
     > let s = "1var foo 99 BAR $%&";

   Simple match::

     > regex pat 0 s 0;
     1,1,"var"

   Same without match info::

     > regex pat REG_NOSUB s 0;
     1

   Global match, return the list of all matches::

     > regexg id pat 0 s 0;
     [(1,"var"),(5,"foo"),(12,"BAR")]

   Same with overlapping matches::

     > regexgg id pat 0 s 0;
     [(1,"var"),(2,"ar"),(3,"r"),(5,"foo"),(6,"oo"),(7,"o"),(12,"BAR"),
     (13,"AR"),(14,"R")]

   Note that :func:`id` (the identity function) in the examples above can be
   replaced with an arbitrary function which processes the matches. For
   instance, if we only want the matched strings instead of the full match
   info::

     > regexg (!1) pat 0 s 0;
     ["var","foo","BAR"]

   Lazy versions of both :func:`regexg` and :func:`regexgg` are provided which
   return the result as a stream instead. These can be processed in a "call by
   need" fashion::

     > regexgs id pat 0 s 0;
     (1,"var"):#<thunk 0x7fb1b7976750>
     > last ans;
     12,"BAR"

   Let's verify that the processing is really done lazily::

     > using system;
     > test x = printf "got: %s\n" (str x) $$ x;
     > let xs = regexgs test pat 0 s 0;
     got: 1,"var"
     > xs!1;
     got: 5,"foo"
     5,"foo"
     > last xs;
     got: 12,"BAR"
     12,"BAR"

   As you can see, the first match is produced immediately, while the
   remaining matches are processed as the result stream is traversed. This is
   most useful if you have to deal with bigger amounts of text. By processing
   the result stream in a piecemeal fashion, you can avoid keeping the entire
   result list in memory. For instance, compare the following::

     > let s2 = fget $ fopen "system.pure" "r";
     > stats -m
     > #regexg id pat 0 s2 0;
     7977
     0.18s, 55847 cells
     > #regexgs id pat 0 s2 0;
     7977
     0.12s, 20 cells

   Regex Substitutions and Splitting
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

   We can also perform substitutions on matches::

     > regsub (sprintf "<%d:%s>") pat 0 s 0;
     "1<1:var> <5:foo> 99 <12:BAR> $%&"

   Or split a string using a delimiter pattern (this uses an egrep pattern)::

     > let delim = "[[:space:]]+";
     > regsplit delim REG_EXTENDED s 0;
     ["1var","foo","99","BAR","$%&"]
     > regsplit delim REG_EXTENDED "The   quick brown    fox" 0;
     ["The","quick","brown","fox"]

   The :func:`regsplit` operation also has a lazy variation::

     > regsplits "[[:space:]]+" REG_EXTENDED "The   quick brown    fox" 0;
     "The":#<thunk 0x7fb1b79775b0>
     > last ans;
     "fox"

   Empty Matches
   ~~~~~~~~~~~~~

   Empty matches are permitted, too, subject to the constraint that at most
   one match is reported for each position (which also prevents looping). And
   of course an empty match will only be reported if nothing else matches. For
   instance::

     > regexg id "" REG_EXTENDED "foo" 0;
     [(0,""),(1,""),(2,""),(3,"")]
     > regexg id "o*" REG_EXTENDED "foo" 0;
     [(0,""),(1,"oo"),(3,"")]
     > regexgg id "o*" REG_EXTENDED "foo" 0;
     [(0,""),(1,"oo"),(2,"o"),(3,"")]

   This also works when substituting or splitting::

     > regsub (cst " ") "" REG_EXTENDED "some text" 0;
     " s o m e   t e x t "
     > regsub (cst " ") " ?" REG_EXTENDED "some text" 0;
     " s o m e  t e x t "
     > regsplit "" REG_EXTENDED "some text" 0;
     ["","s","o","m","e"," ","t","e","x","t",""]
     > regsplit " ?" REG_EXTENDED "some text" 0;
     ["","s","o","m","e","","t","e","x","t",""]

   Submatches
   ~~~~~~~~~~

   Parenthesized subexpressions in a pattern yield corresponding submatch
   information, which is useful if we need to retrieve the text matched by a
   given subexpression. For instance, suppose we want to parse environment
   lines, such as those returned by the shell's ``set`` command. These can be
   dissected using the following regex::

     > const env_pat = "^([^=]+)=(.*)$";
     > const env_flags = REG_EXTENDED or REG_NEWLINE;
     > regex env_pat env_flags "SHELL=/bin/sh" 0;
     1,0,"SHELL=/bin/sh",0,"SHELL",6,"/bin/sh"

   Note that we again used an extended regex here, and we also added the
   :const:`REG_NEWLINE` flag so that we properly deal with multiline input.
   The desired information is in the 4th and 6th element of the submatch info,
   we can retrieve that as follows::

     > parse_env s = regexg (\info -> info!3 => info!5) env_pat env_flags s 0;
     > parse_env "SHELL=/bin/sh\nHOME=/home/bar\n";
     ["SHELL"=>"/bin/sh","HOME"=>"/home/bar"]

   We can get hold of the real process environment as follows::

     > using system;
     > let env = parse_env $ fget $ popen "set" "r";
     > #env;
     109
     > head env;
     "BASH"=>"/usr/bin/sh"

   Just for the fun of it, let's convert this to a record, providing easy
   random access to the environment variables::

     > let env = record env;
     > env!!["SHELL","HOME"];
     {"/bin/bash","/home/ag"}

*/
