Logo Search packages:      
Sourcecode: bazaar version File versions

match-regexp.c

/* match-regexp.c - functions for comparing a string to a regexp
 *
 ****************************************************************
 * Copyright (C) 1998, 2000 Thomas Lord
 * 
 * See the file "COPYING" for further information about
 * the copyright and warranty status of this work.
 */


/* #define TRACE */

#include "hackerlab/bugs/panic.h"
#include "hackerlab/char/char-class.h"
#include "hackerlab/char/str.h"
#include "hackerlab/bitsets/bits.h"
#include "hackerlab/rx/nfa-cache.h"
#include "hackerlab/rx/dfa.h"
#include "hackerlab/rx/escape.h"
#ifdef TRACE
#include "hackerlab/vu/safe.h"
#include "hackerlab/rx/dbug.h"

int rx_trace = 0;
int rx_depth_limit = 0;

#endif
#include "hackerlab/rx-posix/errnorx.h"
#include "hackerlab/rx-posix/match-regexp.h"



static unsigned long solns_allocated;
static unsigned long solns_freed;


#define max0(N)         (((N) >= 0) ? (N) : 0)


/* __STDC__ prototypes for static functions */
static int rx_str_vmfn (void * closure,
                  const t_uchar ** burstp,
                  rx_off_t * lenp,
                  rx_off_t * offsetp,
                  rx_off_t start,
                  rx_off_t end,
                  rx_off_t need);
static int rx_str_contextfn (void * closure,
                       struct rx_exp_node * node,
                       rx_off_t start,
                       rx_off_t end,
                       struct rx_registers * regs);
static int rx_solution_fit_cset_p (struct rx_solutions * solns);
static int rx_solution_fit_str_p (struct rx_solutions * solns);
static int rx_solution_fits (struct rx_solutions * solns);
static int rx_dfa_longest_counting (int * label,
                            size_t * match_len,
                            size_t * matches_count,
                            struct rx_dfa * dfa,
                            const t_uchar * str,
                            size_t len);
static int rx_longest_split_guess (int * label, struct rx_solutions * solns);
static int save_nested_registers (struct rx_solutions * solns);
static void restore_nested_registers (struct rx_solutions * solns);
static int rx_next_solution_internal (struct rx_solutions * solns, jmp_buf * err_escape, int depth);



/************************************************************************
 *(h0 "Regexp Matching" 
 *    :includes ("rx-posix/match-regexp.h"))
 * 
 * 
 * In xref:"Regexp Expression Trees", we saw how to build expression
 * trees for regexps and elsewhere how to convert those regexps which
 * are regular expressions to DFA.  In xref:"DFA String Comparisons"
 * we saw DFA-based functions that can compare a string to a regular
 * expression.
 * 
 * But what about those regexps which are not regular expressions?  So
 * far, except for the quasi-standard functions `regexec' and
 * `regnexec', we have no way to match non-regular regexps.
 * 
 * The functions in this chapter implement regexp matching.  The
 * interface is very detailed, but there are only a few functions and
 * they are conceptually simple.
 * 
 */
/*(menu)
 */

/************************************************************************
 *(h1 "An Overview of the Regexp Matching Interface")
 * 
 * Given a regexp, and an input string, a regexp comparison function
 * should return a value that indicates whether or not the string
 * matches, and an array of values filled in with the substring
 * positions of elements of the input string that matched the
 * parenthesized subexpressions in the match.  (For example, see
 * xref:"regexec".)  We start out intending to build a regexp
 * comparison function that fits the preceeding description and make
 * two observations.
 *
 * First, the function needs to be recursive because we only know how
 * to check whether or not some kinds of regexp match by checking
 * whether their subexpressions match.
 * 
 * Second, the function needs to return more than one set of return
 * values because a regexp can often match a string in more than one
 * way -- returning a different set of values for each way of
 * matching.  To find the best overall match for a regexp, we may have
 * to consider more than one way of matching the subexpressions of
 * that regexp.  In fact, the Posix standard for regexps essentially
 * mandates that we perform a potentially exhaustive search through
 * the possible ways of matching subexpressions.  So, our recursive
 * comparison function has to be able to find all of the different
 * ways of matching a particular regexp and string to facilitate that
 * search.
 *
 * Fortunately, we are able to order the search through the set of
 * subexpressions in such a way that we will often find the best
 * answer (and know it is the best answer) early.  So while our
 * recursive comparison function has to be able to return all possible
 * solutions, it should be free to return them in the order we will
 * search them, and to only actually construct a particular solution
 * if it is actually required during a search.  We can usually save
 * time by not building solutions that we don't need to search.
 * 
 * The functions in this chapter implement such a recursive comparison
 * function.  Given a regexp and a string, the functions return a
 * lazilly-constructed stream of all of the possible ways of matching
 * the regexp to the string.  The stream is sorted; in the solution
 * stream of a regexp subexpression, the best match, according to the
 * rules mandated by Posix, is always the earliest match in the stream
 * that also satisfies the constraints of the overall match of the
 * containing expressions.
 *
 * You build one of these streams of subexpression solutions by calling
 * `rx_make_solutions', passing the regexp and input string.  You
 * read off elements of the stream by calling `rx_next_solution' which
 * actually does the work of computing the next solution in the list.
 *
 * Implementing a function like `regexec' or `regnexec' is easy.  
 * `regexec' iterates over each possible starting point for a match:
 *
 *     for (start_pos = 0; start_pos < string_length; ++start_pos)
 * 
 * At each starting position, `regexec' iterates through each possible
 * ending position:
 *
 *     for (end_pos = string_length; end_pos >= start_pos; --end_pos)
 *
 * For each possible starting and ending position, `regexec'
 * constructs a stream of regexp solutions for that substring (by
 * calling `rx_make_solutions').  It tries to read the first solution
 * on that stream by calling `rx_next_solution'.  If the stream is not
 * empty, the first solution in the stream is the best possible
 * solution, and it is returned from `regexec'.
 *
 * When `regexec' calls `rx_next_solution' to find out if the stream
 * of solutions is empty, more streams of solutions may be created for
 * the subexpressions of the overall regexp.  Those recursively
 * created streams may have to be searched to find an overall
 * solution.  Even though `regexec' only reads one solution from the
 * stream it creates, the recursive calls to `rx_next_solution' may
 * read many solutions from the streams they create.
 *
 * As just described, you might think `regexec' and `regnexec' do a
 * lot of work (running so many separate regexp comparisons).  You
 * would be right.  Consequently, the real-world implementations of
 * `regexec' and `regnexec' employ several tricks to reduce the number
 * of regexp comparisons actually performed -- they try to avoid
 * calling the functions in this chapter.  In addition, the functions
 * in this chapter employ several tricks to avoid searching
 * recursively created streams of solutions.  Still, in the general
 * case, functions like `regexec' use the interface described here in
 * the computationally expensive way described above.  (The exact
 * complexity of a search depends on the particular regexp but in the
 * worst cases, it is a polynomial function (of high degree) of the
 * length of the string being searched.)
 * 
 */

/************************************************************************
 *(h1 "Regexp Match Function Data Structures")
 * 
 */

/*(c #s"struct rx_solutions" :category type)
 * struct rx_solutions;
 * 
 * This opaque structure type represents the stream of solutions for
 * matching a particular regexp against a particular string.
 */
struct rx_solutions
{
  int small_p;
  int step;

  int cset_size;
  struct rx_exp_node * exp;
  struct rx_exp_node ** subexps;
  int nsub;
  struct rx_registers * regs;

  rx_off_t start;
  rx_off_t end;

  rx_vmfn vmfn;
  rx_contextfn contextfn;
  void * closure;

  struct rx_unfa * dfa;
  struct rx_dfa match_engine;

  int certainly_fits;         /* we know in advance that rx_solution_fits returns 1 */
  int certain_final_tag;

  int no_fancy_guessing;
  struct rx_unfa * left_dfa;
  struct rx_dfa left_match_engine;

  rx_off_t split_guess;
  struct rx_solutions * left;
  struct rx_solutions * right;

  int interval_x;
  int interval_from;
  int interval_to;
  rx_off_t * saved_rm_so;
  rx_off_t * saved_rm_eo;
  int final_tag;
};

static struct rx_solutions no_solutions;

#if 0
/*(c #s"struct rx_registers" :category type)
 * struct rx_registers;
 * 
 * This structure type holds information about the match position
 * of one regexp subexpression in a (potentially) larger string.
 * It includes at least these fields:
 *
 insert*/
struct rx_registers
{
  rx_off_t rm_so;       /* The start of the match. */
  rx_off_t rm_eo;       /* The end of the match. */
};
/*end-insert
 */
#endif


/************************************************************************
 * Low Level Support for Basic String Matching
 * 
 */

struct rx_str_closure
{
  struct rx_context_rules rules;
  const t_uchar * str;
  rx_off_t len;
};


static int
rx_str_vmfn (void * closure,
           const t_uchar ** burstp,
           rx_off_t * lenp,
           rx_off_t * offsetp,
           rx_off_t start,
           rx_off_t end,
           rx_off_t need)
{
  struct rx_str_closure * strc;

  strc = (struct rx_str_closure *)closure;

  if (   (need < 0)
      || (need > strc->len))
    return 0;

  *burstp = strc->str;
  *lenp = strc->len;
  *offsetp = 0;
  return 0;
}


static int
rx_str_contextfn (void * closure,
              struct rx_exp_node * node,
              rx_off_t start,
              rx_off_t end,
              struct rx_registers * regs)
{
  struct rx_str_closure * strc;

  strc = (struct rx_str_closure *)closure;

  switch (node->intval)
    {
    case '1': case '2': case '3': case '4': case '5':
    case '6': case '7': case '8': case '9':
      {
      int cmp;
      int regn;

      regn = node->intval - '0';
      if (   (regs[regn].rm_so == -1)
          || ((end - start) != (regs[regn].rm_eo - regs[regn].rm_so)))
        return 0;
      else
        {
          if (strc->rules.case_indep)
            cmp = str_casecmp_n ((t_uchar *)strc->str + start,
                           end - start,
                           (t_uchar *)strc->str + regs[regn].rm_so,
                           end - start);
          else
            cmp = str_cmp_n ((t_uchar *)strc->str + start,
                         end - start,
                         (t_uchar *)strc->str + regs[regn].rm_so,
                         end - start);

          return (!cmp
                ? 1
                : 0);
        }
      }

    case '^':
      {
      return ((   (start == end)
             && (   ((start == 0) && !strc->rules.not_bol)
                 || (   (start > 0)
                   && strc->rules.newline_anchor
                   && (strc->str[start - 1] == '\n'))))
            ? 1
            : 0);
      }

    case '$':
      {
      return ((   (start == end)
             && (   ((start == strc->len) && !strc->rules.not_eol)
                 || (   (start < strc->len)
                   && strc->rules.newline_anchor
                   && (strc->str[start] == '\n'))))
            ? 1
            : 0);
      }

    default:
      while (1)
      panic ("unrecognized context function in rx_str_contextfn");
    }
}


/************************************************************************
 *(h1 "Building and Freeing a Stream of Solutions -- The Simplified Common Case")
 * 
 */

#if 0
/*(c rx_basic_make_solutions)
 * struct rx_solutions * 
 * rx_basic_make_solutions (struct rx_registers * regs,
 *                    struct rx_exp_node * expression,
 *                    struct rx_exp_node ** subexps,
 *                    int nsub,
 *                    rx_off_t start,
 *                    rx_off_t end,
 *                    struct rx_context_rules * rules,
 *                    const t_uchar * str,
 *                    int small_p);
 * 
 * Construct a stream of solutions for matching the regexp
 * `expression' against the substring of `str' beginning at `start'
 * and ending at `end'.
 * 
 * Part of the output of stream, the positions of sub-expressions in a
 * solution, will be stored in `regs' each time the next solution is
 * read using `rx_next_solution'.
 * 
 * The parameter `context_rules' contains flags which effect the
 * meaning of some regexp operators.  
 * 
 insert*/
struct rx_context_rules
{
  t_uchar newline_anchor;
  /*        If set, an anchor at a newline matches.*/

  t_uchar not_bol;
  t_uchar not_eol;
  /*  If set, the anchors do not match the beginning and end
      of the complete input string.*/


  t_uchar case_indep;
  /*  If set, all string comparisons should be case independent.*/
};
/*end-insert
 *
 * You must apply `rx_analyze_rexp' to the regexp `expression' before
 * calling his function.  `rx_analyze_rexp' computes recursively
 * defined properties of the subexpressions of the expression and
 * records those properties in the expression tree. During a match,
 * `rx_next_solution' examines those properties to decide how each
 * subexpression should be treated.
 *
 * `rx_analyze_rexp' will return to you an array of the parenthesized
 * subexpressions of `expression' and tell you the total number of
 * subexpressions.  You must pass this information along to
 * `rx_basic_make_solutions' as the `subexps' and `nsub' parameters.
 * 
 * `rx_analyze_rexp' will also fill in the `small_advised_p' field of
 * `expression'.  You can pass this along to `rx_basic_make_solutions'
 * as the parameter `small_p'.  If not 0, `small_p' advises
 * `rx_basic_make_solutions' that the regexp is small and simple and
 * therefore not worthy of several high-latency optimizations that
 * `rx_next_solution' is capable of.  Setting this parameter correctly
 * can improve performance, setting it incorrectly can ruin
 * performance, and `rx_analyze_rexp' can only approximately compute
 * whether or not to set this parameter (it makes a safe guess).  The
 * safest value to pass is 0, which activates the high-latency
 * optimizations, sometimes (slightly) slowing down matches that
 * aren't particularly expensive while (substantially) speeding up
 * some matches that are particularly expensive.
 *
 * `rx_basic_make_solutions' requires that the entire input string be
 * in contiguous memory at one time.  Another function,
 * `rx_make_solutions', can be used if the string is not contiguous in
 * memory or is not all in memory at one time.
 */
#endif
struct rx_solutions *
rx_basic_make_solutions (struct rx_registers * regs,
                   struct rx_exp_node * expression,
                   struct rx_exp_node ** subexps,
                   int nsub,
                   rx_off_t start,
                   rx_off_t end,
                   struct rx_context_rules * rules,
                   const t_uchar * str,
                   int small_p)
{
  struct rx_solutions * solns;
  struct rx_str_closure * closure;

  if (   expression
      && (expression->len >= 0)
      && (expression->len != (end - start)))
    return &no_solutions;

  closure = (struct rx_str_closure *)rx_nfa_cache_malloc (sizeof (*closure));
  if (!closure)
    return 0;
  
  closure->str = str;
  closure->len = end;
  closure->rules = *rules;
  solns =  rx_make_solutions (regs,
                        256, expression, subexps, nsub,
                        start, end, 0,
                        rx_str_vmfn, rx_str_contextfn, (void *)closure, small_p, 0, 0);
  if (!solns)
    {
      rx_nfa_cache_free ((void *)closure);
      return 0;
    }
  return solns;
}


/*(c rx_basic_free_solutions)
 * void rx_basic_free_solutions (struct rx_solutions * solns);
 * 
 * Release all storage held by a stream of regexp solutions allocated
 * by `rx_basic_make_solutions'.
 */
void
rx_basic_free_solutions (struct rx_solutions * solns)
{
  if (solns == 0)
    return;

  if (solns == &no_solutions)
    return;

  rx_nfa_cache_free (rx_solutions_closure (solns));
  rx_free_solutions (solns);
}



/************************************************************************
 * Low Level Support for rx_next_solution
 * 
 * 
 * 
 */

/* static int rx_solution_fit_cset_p (struct rx_solutions * solns);
 * 
 * The expression is a character set node and the current substring is
 * one character long.  Compare the two and return 1 if they match, 0
 * otherwise.
 */
static int
rx_solution_fit_cset_p (struct rx_solutions * solns)
{
  int current_pos;
  const t_uchar * burst;
  rx_off_t burst_addr;
  rx_off_t burst_len;
  rx_off_t rel_pos_in_burst;
  int vmstat;
  const t_uchar * pos;

  current_pos = solns->start;
  vmstat = solns->vmfn (solns->closure,
                  &burst, &burst_len, &burst_addr,
                  current_pos, current_pos + 1, current_pos);

  if (vmstat)
    return vmstat;

  rel_pos_in_burst = current_pos - burst_addr;
  pos = burst + rel_pos_in_burst;
  return !!bits_is_member (solns->exp->cset, *pos);
}


/* static int rx_solution_fit_str_p (struct rx_solutions * solns);
 * 
 * The expression is a string node and the current substring is the
 * same length.  Compare the two and return 1 if they match, 0
 * otherwise.
 */
static int
rx_solution_fit_str_p (struct rx_solutions * solns)
{
  rx_off_t current_pos;
  const t_uchar * burst;
  rx_off_t burst_addr;
  rx_off_t burst_len;
  rx_off_t burst_end_addr;
  rx_off_t rel_pos_in_burst;
  int vmstat;
  rx_off_t count;
  t_uchar * key;


  current_pos = solns->start;
  count = solns->exp->str_len;
  key = (t_uchar *)solns->exp->str;

 next_burst:
  vmstat = solns->vmfn (solns->closure,
                  &burst, &burst_len, &burst_addr,
                  current_pos, solns->end,
                  current_pos);

  if (vmstat)
    return vmstat;

  rel_pos_in_burst = current_pos - burst_addr;
  burst_end_addr = burst_addr + burst_len;

  {
    const t_uchar * pos;

    pos = burst + rel_pos_in_burst;

    if (burst_end_addr >= solns->end)
      {
      while (count)
        {
          if (rx_poll)
            (*rx_poll)();
          if (*pos != *key)
            return 0;
          ++pos;
          ++key;
          --count;
        }
      return 1;
      }
    else
      {
      rx_off_t part_count;
      rx_off_t part_count_init;

      part_count_init = burst_len - rel_pos_in_burst;
      part_count = part_count_init;
      while (part_count)
        {
          if (rx_poll)
            (*rx_poll)();
          if (*pos != *key)
            return 0;
          ++pos;
          ++key;
          --part_count;
        }
      count -= part_count_init;
      current_pos += burst_len - rel_pos_in_burst;
      goto next_burst;
      }
  }
}


/* static int rx_solution_fits (struct rx_solutions * solns);
 * 
 * Compare a DFA which describes a superset of the regexp expression
 * to the current substring and return 1 if they match, 0 otherwise.
 * That the DFA matches is a necessary but not sufficient condition of
 * the regexp expression itself matching.  This test can be used to
 * avoid a more expensive regexp comparison.  Return -1 for ESPACE.
 */
static int
rx_solution_fits (struct rx_solutions * solns)
{
  const t_uchar * burst;
  rx_off_t burst_addr;
  rx_off_t burst_len;
  rx_off_t burst_end_addr;
  rx_off_t rel_pos_in_burst;
  int vmstat;
  rx_off_t current_pos;
        
  if (solns->certainly_fits)
    {
      solns->match_engine.final_tag = solns->certain_final_tag;
      return 1;
    }

  current_pos = solns->start;

 next_burst:
  vmstat = solns->vmfn (solns->closure,
                  &burst, &burst_len, &burst_addr,
                  current_pos, solns->end,
                  current_pos);

  if (vmstat)
    return vmstat;

  rel_pos_in_burst = current_pos - burst_addr;
  burst_end_addr = burst_addr + burst_len;

  if (burst_end_addr >= solns->end)
    {
      int fit_label;

      if (rx_dfa_fits (&fit_label,
                   &solns->match_engine,
                   burst + rel_pos_in_burst,
                   solns->end - current_pos))
      return -1;        /* espace */
      return fit_label;
    }
  else
    {
      int fit_status;
      fit_status = rx_dfa_advance (&solns->match_engine,
                           burst + rel_pos_in_burst,
                           burst_len - rel_pos_in_burst);
      if (fit_status < 0)
      {
        return -1;
      }
      else if (fit_status)
      {
        current_pos += burst_len - rel_pos_in_burst;
        goto next_burst;
      }
      else
      return 0;
    }
}


static int
rx_dfa_longest_counting (int * label,
                   size_t * match_len,
                   size_t * matches_count,
                   struct rx_dfa * dfa,
                   const t_uchar * str,
                   size_t len)
{
  size_t pos;
  size_t n_matches;
  size_t best_len;
  int best_label;

  pos = 0;
  n_matches = 0;
  best_len = 0;
  best_label = rx_dfa_tag (dfa);
  
  if (best_label)
    {
      n_matches = 1;
    }
  
  while (pos < len)
    {
      int adv_stat;
      size_t adv_amt;
    
      adv_stat = rx_dfa_advance_to_final (&adv_amt, dfa, str + pos, len - pos);

      if (adv_stat < 0)
      return -1;

      if (!adv_stat)
      break;

      pos += adv_amt;
      if (rx_dfa_tag (dfa))
      {
        best_len = pos;
        ++n_matches;
        best_label = rx_dfa_tag (dfa);
      }
    }

  *label = best_label;
  *match_len = best_len;
  *matches_count = n_matches;
  return 0;
}


/* adjust split_guess downward to the nearest plausible
 * position.  Return 0 if none exists, 1 otherwise.
 */
static int
rx_longest_split_guess (int * label, struct rx_solutions * solns)
{
  const t_uchar * burst;
  rx_off_t burst_addr;
  rx_off_t burst_len;
  rx_off_t burst_end_addr;
  rx_off_t rel_pos_in_burst;
  int vmstat;
  rx_off_t current_pos;
  size_t n_matches;
  rx_off_t best_guess;
  int best_label;
        
  if (solns->no_fancy_guessing)
    {
      *label = 0;
      return 1;
    }

  current_pos = solns->start;
  n_matches = 0;
  best_guess = -1;
  best_label = 0;

  if (rx_dfa_goto_start_superstate (&solns->left_match_engine, 1))
    return -1;

  while (1)
    {
      int fit_label;
      size_t matches_here;
      size_t len_here;

      vmstat = solns->vmfn (solns->closure,
                      &burst, &burst_len, &burst_addr,
                      current_pos, solns->split_guess,
                      current_pos);

      if (vmstat)
      {
        rx_clear_dfa_state (&solns->left_match_engine);
        return vmstat;
      }

      rel_pos_in_burst = current_pos - burst_addr;
      burst_end_addr = burst_addr + burst_len;

      if (rx_dfa_longest_counting (&fit_label,
                           &len_here,
                           &matches_here,
                           &solns->left_match_engine,
                           burst + rel_pos_in_burst,
                           ((burst_end_addr >= solns->split_guess)
                            ? solns->split_guess - current_pos
                            : burst_end_addr - current_pos)))
      {
        rx_clear_dfa_state (&solns->left_match_engine);
        return -1;
      }
      
      if (fit_label)
      {
        n_matches += matches_here;
        best_guess = len_here + rel_pos_in_burst;
        best_label = fit_label;
      }

      if (!fit_label || (burst_end_addr >= solns->split_guess))
      {
        if (!n_matches)
          {
            rx_clear_dfa_state (&solns->left_match_engine);
            return 0;
          }

        solns->split_guess = best_guess;
        *label = best_label;
        if (n_matches > (best_guess * 2))
          solns->no_fancy_guessing = 1;

        rx_clear_dfa_state (&solns->left_match_engine);
        return 1;
      }

      current_pos += burst_len - rel_pos_in_burst;
    }
}



/************************************************************************
 *(h1 "Reading Elements From a Stream of Solutions")
 * 
 */

/* Save the values of registers for reporting parentheses
 * enclosed in the expression solns->exp.  Initialize
 * those registers to -1.
 * 
 * These are stored in the `solns' structure.  Only one set of register
 * values can be saved, per `solns', at a time.
 */
static int
save_nested_registers (struct rx_solutions * solns)
{
  int first_subexp;
  int last_subexp;
  int n_subexps;
  int x;

  /* Save the value of the set of numbered
   * parentheses in the tree rooted at this
   * expression and initialized them to -1.  If
   * this expression does not match, they will
   * be restored.  If it does match, they get values
   * from that match and not from previous matches.
   */

  first_subexp = solns->exp->min_enclosed_paren;
  last_subexp = solns->exp->max_enclosed_paren;
  n_subexps = 1 + (last_subexp - first_subexp);

  if (!solns->saved_rm_so)
    {
      solns->saved_rm_so = (rx_off_t *)rx_nfa_cache_malloc (sizeof (rx_off_t) * n_subexps);
      solns->saved_rm_eo = (rx_off_t *)rx_nfa_cache_malloc (sizeof (rx_off_t) * n_subexps);
      if (!solns->saved_rm_so || !solns->saved_rm_eo)
      {
        rx_nfa_cache_free ((void *)solns->saved_rm_so);
        rx_nfa_cache_free ((void *)solns->saved_rm_eo);
        return -1;
      }
    }

  for (x = 0; x < n_subexps; ++x)
    {
      solns->saved_rm_so[x] = solns->regs[x + first_subexp].rm_so;
      solns->saved_rm_eo[x] = solns->regs[x + first_subexp].rm_eo;
      solns->regs[x + first_subexp].rm_so = -1;
      solns->regs[x + first_subexp].rm_eo = -1;
    }
  return 0;
}

/* Restore register values saved by `save_nested_registers'.
 * 
 * This doesn't erase the stored values.
 */
static void
restore_nested_registers (struct rx_solutions * solns)
{
  int first_subexp;
  int last_subexp;
  int n_subexps;
  int x;

  first_subexp = solns->exp->min_enclosed_paren;
  last_subexp = solns->exp->max_enclosed_paren;
  n_subexps = 1 + (last_subexp - first_subexp);

  for (x = 0; x < n_subexps; ++x)
    {
      solns->regs[x + first_subexp].rm_so = solns->saved_rm_so[x];
      solns->regs[x + first_subexp].rm_eo = solns->saved_rm_eo[x];
    }
}

/*(c rx_next_solution)
 * int rx_next_solution (struct rx_solutions * solns);
 * 
 * If there are no more solutions in the stream of regexp solutions
 * `solns', return 0.  Otherwise, advance the stream to the next
 * solution and return 1.  Return -1 for ESPACE.
 *
 * Advancing the stream means filling in the `regs' structure that was
 * passed to `rx_basic_make_solutions' or `rx_make_solutions' and
 * establishing the value that will be returned by subsequent calls to
 * `rx_solutions_final_tag'.
 *
 * Solutions are returned in order from best to worst according to the
 * leftmost-longest rule (see xref:"Describing Regexps Formally").
 * 
 * It is possible to asynchronously abort a call to this function.
 * See xref:"Exiting Long-Running Matches".
 */
int
rx_next_solution (struct rx_solutions * solns)
{
  jmp_buf err_escape;

  if (setjmp (err_escape))
    {
      return -1;
    }
  return rx_next_solution_internal (solns, &err_escape, 0);
}


static int
rx_next_solution_internal (struct rx_solutions * solns, jmp_buf * err_escape, int depth)
{
#ifdef TRACE
  if (rx_trace && (!rx_depth_limit || (depth < rx_depth_limit)))
    {
      safe_printfmt (2, "%*s================\n", depth, "");
      safe_printfmt (2, "%*sstep: %d\n", depth, "", solns->step);
      safe_printfmt (2, "%*s----------------\n", depth, "");
      safe_printfmt (2, "%*sexpression:\n", depth, "");
      safe_printfmt (2, "%*s", depth, "");
      rx_unparse_print_rexp (2, 256, solns->exp);
      safe_printfmt (2, "\n");
      safe_printfmt (2, "%*s----------------\n", depth, "");
      safe_printfmt (2, "%*sstring:\n", depth, "");
      {
      const t_uchar * burst;
      rx_off_t burst_addr;
      rx_off_t burst_len;
      rx_off_t rel_pos_in_burst;
      int vmstat;
      
      vmstat = solns->vmfn (solns->closure,
                        &burst, &burst_len, &burst_addr,
                        solns->start, solns->end, solns->start);
      
      if (vmstat)
        panic ("vmstat failure in trace");
      
      rel_pos_in_burst = solns->start - burst_addr;
      safe_printfmt (2, "%*s%.*s\n", depth, "",
                   ((solns->end - solns->start) <= (burst_len - rel_pos_in_burst)
                  ? (solns->end - solns->start)
                  : (burst_len - rel_pos_in_burst)),
                   burst + rel_pos_in_burst);
      }
      safe_printfmt (2, "%*s----------------\n", depth, "");
    }
#endif

#define KNOWN_LENGTH(EXP)     (!(EXP) \
                         ? 0 \
                         : ((EXP)->len >= 0 \
                            ? (EXP)->len \
                            : ((((EXP)->type == r_context) && ((EXP)->intval >= '0') && ((EXP)->intval <= '9')) \
                               ? ((solns->regs[(EXP)->intval - '0'].rm_so >= 0) \
                                ? (solns->regs[(EXP)->intval - '0'].rm_eo - solns->regs[(EXP)->intval - '0'].rm_so) \
                                : -1) \
                               : -1)))


  if (solns == &no_solutions)
    {
      return 0;
    }

  if (!solns->exp)
    {
      if (solns->step != 0)
      {
        return 0;
      }
      else
      {
        solns->step = 1;
        solns->final_tag = 1;
        return (solns->start == solns->end
              ? 1
              : 0);
      }
    }
  else if (!(solns->small_p || solns->exp->observed))
    {
      if (solns->step != 0)
      {
        return 0;
      }
      else if (solns->exp->type == r_string)
      {
        int ans;
        ans = rx_solution_fit_str_p (solns);
        solns->final_tag = 1;
        solns->step = -1;
        return ans;
      }
      else
      {
        int ans;
        ans = rx_solution_fits (solns);
        if (ans < 0)
          longjmp (*err_escape, 1);
        solns->final_tag = solns->match_engine.final_tag;
        solns->step = -1;
        return !!ans;
      }
    }
  else                        /* if (solns->small_p || solns->exp->observed) */
    {
      int fits;
      switch (solns->step)
      {
      case -2:
        if (solns->exp->min_enclosed_paren)
          {
            int first_subexp;
            int last_subexp;
            int x;

            first_subexp = solns->exp->min_enclosed_paren;
            last_subexp = solns->exp->max_enclosed_paren;

            for (x = first_subexp; x <= last_subexp; ++x)
            {
              solns->regs[x].rm_so = solns->saved_rm_so[x - first_subexp];
              solns->regs[x].rm_eo = solns->saved_rm_eo[x - first_subexp];
            }
          }
        return 0;

      case -1:
        return 0;

      case 0:
        if (solns->small_p)
          {
            solns->step = 1;
            goto resolve_fit;
          }
        else
          {
            fits = rx_solution_fits (solns);
            if (fits < 0)
            longjmp (*err_escape, 1);
            /* Set final_tag here because this rough fit test
             * may be all the matching that gets done.
             * For example, consider a paren node containing
             * a true regular expression ending with a cut
             * operator.
             */
            solns->final_tag = solns->match_engine.final_tag;
            if (fits == 0)
            {
              solns->step = -1;
              return fits;
            }
            else
            {
              solns->step = 1;
              goto resolve_fit;
            }
          }

      default:
      resolve_fit:
        switch (solns->exp->type)
          {
          case r_string:
            if (!solns->small_p)
            {
              while (1)
                panic ("bogus regexp in rx_next_solution_internal");
            }
            else
            {
              int answer;
              answer = rx_solution_fit_str_p (solns);
              solns->final_tag = 1;
              solns->step = -1;
              return answer;
            }
            
          case r_cset:
            if (!solns->small_p)
            {
              while (1)
                panic ("bogus regexp in rx_next_solution_internal");
            }
            else
            {
              int answer;
              answer = rx_solution_fit_cset_p (solns);
              solns->final_tag = 1;
              solns->step = -1;
              return answer;
            }
            
          case r_cut:
            if (!solns->small_p)
            {
              while (1)
                panic ("bogus regexp in rx_next_solution_internal");
            }
            else
            {
              solns->final_tag = solns->exp->intval;
              solns->step = -1;
              return !!solns->exp->intval;
            }
            
          case r_parens:
            {
            int paren_stat;
            switch (solns->step)
              {
              case 1:
                if (solns->exp->min_enclosed_paren)
                  {
                  if (save_nested_registers (solns))
                    longjmp (*err_escape, 1);
                  }

                if (   !solns->small_p
                  && (   !solns->exp->left
                      || !solns->exp->left->observed))
                  {
                  /* We already proved that this (simple)
                   * subexpression matches.  Optionally, record
                   * its position.  Return success once, and
                   * failure for all subsequent attempts to find
                   * other matches.
                   */
                  if (solns->exp->intval)
                    {
                      solns->regs[solns->exp->intval].rm_so = solns->start;
                      solns->regs[solns->exp->intval].rm_eo = solns->end;
                    }
                  solns->step = -2;
                  /* Keep the final_tag from the fits test. */
                  return 1;
                  }

                /* We must search through possible matches of the subexpression.
                 */
                solns->left = rx_make_solutions (solns->regs,
                                         solns->cset_size,
                                         solns->exp->left,
                                         solns->subexps,
                                         solns->nsub,
                                         solns->start,
                                         solns->end,
                                         0,
                                         solns->vmfn,
                                         solns->contextfn,
                                         solns->closure,
                                         solns->small_p,
                                         0,
                                         0);
                if (!solns->left)
                  longjmp (*err_escape, 1);

              case 2:
                if (solns->exp->min_enclosed_paren)
                  {
                  int first_subexp;
                  int last_subexp;
                  int x;

                  /* Initialize the parentheses in the tree
                   * rooted at this expression to -1.  
                   */

                  first_subexp = solns->exp->min_enclosed_paren;
                  last_subexp = solns->exp->max_enclosed_paren;

                  for (x = first_subexp; x <= last_subexp; ++x)
                    {
                      solns->regs[x].rm_so = -1;
                      solns->regs[x].rm_eo = -1;
                    }
                  }

                paren_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                if (paren_stat < 0)
                  longjmp (*err_escape, 1);

                if (paren_stat == 1)
                  {
                  if (solns->exp->intval)
                    {
                      solns->regs[solns->exp->intval].rm_so = solns->start;
                      solns->regs[solns->exp->intval].rm_eo = solns->end;
                    }
                  solns->final_tag = solns->left->final_tag;
                  solns->step = 2;
                  return 1;
                  }
                else 
                  {
                  rx_free_solutions (solns->left);
                  solns->left = 0;
                  if (solns->exp->min_enclosed_paren)
                    {
                      /* This expression didn't match.  Restore the old subexpression
                       * positions.
                       */
                      restore_nested_registers (solns);
                    }
                  solns->step = -1;
                  return paren_stat;
                  }
              }
            }

          case r_alternate:
            {
            int alt_stat;
            switch (solns->step)
              {
              case 1:
                solns->left = rx_make_solutions (solns->regs,
                                         solns->cset_size,
                                         solns->exp->left,
                                         solns->subexps,
                                         solns->nsub,
                                         solns->start,
                                         solns->end,
                                         0,
                                         solns->vmfn,
                                         solns->contextfn,
                                         solns->closure,
                                         solns->small_p,
                                         0,
                                         0);
                if (!solns->left)
                  longjmp (*err_escape, 1);

              case 2:
                alt_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                if (alt_stat < 0)
                  longjmp (*err_escape, 1);

                if (alt_stat == 1)
                  {
                  solns->final_tag = solns->left->final_tag;
                  solns->step = 2;
                  return alt_stat;
                  }
                else 
                  {
                  rx_free_solutions (solns->left);
                  solns->left = 0;
                  }

                solns->right = rx_make_solutions (solns->regs,
                                          solns->cset_size,
                                          solns->exp->right,
                                          solns->subexps,
                                          solns->nsub,
                                          solns->start,
                                          solns->end,
                                          0,
                                          solns->vmfn,
                                          solns->contextfn,
                                          solns->closure,
                                          solns->small_p,
                                          0,
                                          0);
                if (!solns->right)
                  longjmp (*err_escape, 1);

              case 4:
                alt_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
                if (alt_stat < 0)
                  longjmp (*err_escape, 1);

                if (alt_stat == 1)
                  {
                  solns->final_tag = solns->right->final_tag;
                  solns->step = 4;
                  return alt_stat;
                  }
                else 
                  {
                  solns->step = -1;
                  rx_free_solutions (solns->right);
                  solns->right = 0;
                  return alt_stat;
                  }
              }
            }

          case r_concat:
            {
            switch (solns->step)
              {
                int concat_stat;
                int split_guess_stat;
                int certain_label;

              case 1:

                if (!solns->exp->left)
                  solns->split_guess = solns->start;
                else
                  {
                  rx_off_t known_left_length;

                  known_left_length = KNOWN_LENGTH (solns->exp->left);
                  if (known_left_length >= 0)
                    {
                      if (known_left_length > (solns->end - solns->start))
                        {
                        solns->step = -1;
                        return 0;
                        }
                      solns->split_guess = solns->start + known_left_length;
                    }
                  else
                    {
                      rx_off_t known_right_length;

                      known_right_length = KNOWN_LENGTH (solns->exp->right);

                      if (known_right_length >= 0)
                        {
                        if (known_right_length > (solns->end - solns->start))
                          {
                            solns->step = -1;
                            return 0;
                          }
                        solns->split_guess = solns->end - known_right_length;
                        }
                      else
                        solns->split_guess = solns->end;
                    }
                  }

              concat_split_guess_loop:

                split_guess_stat = rx_longest_split_guess (&certain_label, solns);

                if (split_guess_stat < 0)
                  longjmp (*err_escape, 1);

                if (!split_guess_stat)
                  {
                  solns->step = -1;
                  return 0;
                  }

                solns->left = rx_make_solutions (solns->regs,
                                         solns->cset_size,
                                         solns->exp->left,
                                         solns->subexps,
                                         solns->nsub,
                                         solns->start,
                                         solns->split_guess,
                                         0,
                                         solns->vmfn,
                                         solns->contextfn,
                                         solns->closure,
                                         solns->small_p,
                                         !!certain_label,
                                         certain_label);
                if (!solns->left)
                  longjmp (*err_escape, 1);

              concat_try_next_left_match:

                concat_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                if (concat_stat < 0)
                  longjmp (*err_escape, 1);

                if (concat_stat != 1)
                  {
                  rx_free_solutions (solns->left);
                  solns->left = 0;
                  if (   (KNOWN_LENGTH (solns->exp->left) < 0)
                      && (KNOWN_LENGTH (solns->exp->right) < 0))
                    {
                      --solns->split_guess;
                      if (solns->split_guess >= solns->start)
                        goto concat_split_guess_loop;
                    }

                  solns->step = -1;
                  return 0;
                  }

                solns->right = rx_make_solutions (solns->regs,
                                          solns->cset_size,
                                          solns->exp->right,
                                          solns->subexps,
                                          solns->nsub,
                                          solns->split_guess,
                                          solns->end,
                                          0,
                                          solns->vmfn,
                                          solns->contextfn,
                                          solns->closure,
                                          solns->small_p,
                                          0,
                                          0);
                if (!solns->right)
                  longjmp (*err_escape, 1);

              case 2:
                concat_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
                if (concat_stat < 0)
                  longjmp (*err_escape, 1);

                if (concat_stat == 1)
                  {
                  solns->final_tag = solns->right->final_tag;
                  solns->step = 2;
                  return concat_stat;
                  }
                else 
                  {
                  rx_free_solutions (solns->right);
                  solns->right = 0;
                  goto concat_try_next_left_match;
                  }
              }
            }

          case r_right_concat:
            {
            switch (solns->step)
              {
                int concat_stat;
                rx_off_t known_left_length;
                rx_off_t known_right_length;

              case 1:
                known_left_length = KNOWN_LENGTH (solns->exp->left);
                known_right_length = KNOWN_LENGTH (solns->exp->right);
                if (known_left_length >= 0)
                  {
                  solns->split_guess = solns->start + known_left_length;
                  }
                else if (known_right_length >= 0)
                  {
                  solns->split_guess = solns->end - known_right_length;
                  }
                else
                  solns->split_guess = solns->start;


              right_concat_split_guess_loop:
                solns->left = rx_make_solutions (solns->regs,
                                         solns->cset_size,
                                         solns->exp->left,
                                         solns->subexps,
                                         solns->nsub,
                                         solns->start,
                                         solns->split_guess,
                                         0,
                                         solns->vmfn,
                                         solns->contextfn,
                                         solns->closure,
                                         solns->small_p,
                                         0,
                                         0);
                if (!solns->left)
                  longjmp (*err_escape, 1);

              right_concat_try_next_left_match:

                concat_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                if (concat_stat < 0)
                  longjmp (*err_escape, 1);

                if (concat_stat != 1)
                  {
                  rx_free_solutions (solns->left);
                  solns->left = 0;
                  if (   (KNOWN_LENGTH (solns->exp->left) < 0)
                      && (KNOWN_LENGTH (solns->exp->right) < 0))
                    {
                      ++solns->split_guess;
                      if (solns->split_guess <= solns->end)
                        goto right_concat_split_guess_loop;
                    }

                  solns->step = -1;
                  return 0;
                  }

                solns->right = rx_make_solutions (solns->regs,
                                          solns->cset_size,
                                          solns->exp->right,
                                          solns->subexps,
                                          solns->nsub,
                                          solns->split_guess,
                                          solns->end,
                                          0,
                                          solns->vmfn,
                                          solns->contextfn,
                                          solns->closure,
                                          solns->small_p,
                                          0,
                                          0);
                if (!solns->right)
                  longjmp (*err_escape, 1);

              case 2:
                concat_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
                if (concat_stat < 0)
                  longjmp (*err_escape, 1);

                if (concat_stat == 1)
                  {
                  solns->final_tag = solns->right->final_tag;
                  solns->step = 2;
                  return concat_stat;
                  }
                else 
                  {
                  rx_free_solutions (solns->right);
                  solns->right = 0;
                  goto right_concat_try_next_left_match;
                  }
              }
            }

          case r_star:
            {
            int star_stat;

            switch (solns->step)
              {
              case 1:
                /* Begin by trying to match the entire string
                 * with a single iteration.
                 */
                solns->left = rx_make_solutions (solns->regs,
                                         solns->cset_size,
                                         solns->exp->left,
                                         solns->subexps,
                                         solns->nsub,
                                         solns->start,
                                         solns->end,
                                         0,
                                         solns->vmfn,
                                         solns->contextfn,
                                         solns->closure,
                                         solns->small_p,
                                         0,
                                         0);
                if (!solns->left)
                  longjmp (*err_escape, 1);


              case 2:
                star_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                if (star_stat < 0)
                  longjmp (*err_escape, 1);

                if (star_stat == 1)
                  {
                  /* found a single-iteration whole-string match */
                  solns->final_tag = solns->left->final_tag;
                  solns->step = 2;
                  return 1;
                  }
                
                /* no more single-iteration whole-string matches */
                rx_free_solutions (solns->left);
                solns->left = 0;
                
                if (solns->start == solns->end)
                  {
                  /* when comaring to the empty string and none of the single-iteration
                   * matches work, try matching with zero iterations, then give up
                   */
                  solns->step = -1;
                  return 1;
                  }
                
                /* when comparing to a non-empty string and none of the single-iteration
                 * matches work, try all matches with two or more non-empty iterations.
                 */
                if (!solns->exp->left || (solns->exp->left->len == 0))
                  {
                  solns->step = -1;
                  return 0;
                  }
                else if (solns->exp->left->len > 0)
                  {
                  if (   (solns->exp->left->len >= (solns->end - solns->start))
                      || (0 != ((solns->end - solns->start) % solns->exp->left->len)))
                    {
                      solns->step = -1;
                      return 0;
                    }
                  solns->split_guess = solns->end - solns->exp->left->len;
                  }
                else
                  solns->split_guess = solns->start + 1;
                
              case 3:
              star_3:

                /* Suppose the string has been split into two parts: s == s1 s2
                 * and we are trying to match R*.
                 *
                 * Recurse by matching s1 against R*, and s2 against R.
                 *
                 * However, if s == s1 and s2 is the empty string, comparing
                 * s1 to R* would cause an infinite recursion.  So instead,
                 * compare s1 to R and s2 to R.
                 *
                 * Comparing s2 to R is often much less expensive than comparing
                 * s1 to R*.  If s2 doesn't match R, time spent comparing s1 to R*
                 * is wasted.  So, before trying s1 against R*, make sure that
                 * s2 can match R.
                 *
                 * Registers are subtle.  There are three possibilities:
                 *
                 *            [A] R contains no reporting parens
                 *            [B] R contains reporting parens
                 *
                 * In case A, matching s1 against R* won't change any registers,
                 * so it is safe to match s to R first.
                 *
                 * In the second case, either
                 * 
                 *            [B1] R is a reporting parenthesized expression
                 *            [B2] R is a non-reporting parenthesized expression
                 * 
                 * In either of those two cases, the first step of
                 * comparing s2 to R is to set all of the
                 * registers for nested reporting parentheses to
                 * -1.  As a result, again, s1 against R* has no (observable) effect
                 * on registers -- so it is safe to match s to R first.
                 *
                 */

                solns->right = rx_make_solutions (solns->regs,
                                          solns->cset_size,
                                          solns->exp->left,
                                          solns->subexps,
                                          solns->nsub,
                                          solns->split_guess,
                                          solns->end,
                                          0,
                                          solns->vmfn,
                                          solns->contextfn,
                                          solns->closure,
                                          solns->small_p,
                                          0,
                                          0);
                if (!solns->right)
                  longjmp (*err_escape, 1);

                star_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
                if (star_stat < 0)
                  longjmp (*err_escape, 1);

                if (star_stat != 1)
                  {
                  /* No match for s2 against R, so guess again:
                   */
                  rx_free_solutions (solns->right);
                  solns->right = 0;
                  if (solns->exp->left->len > 0)
                    {
                      solns->step = -1;
                      return 0;
                    }
                  ++solns->split_guess;
                  if (solns->split_guess > solns->end)
                    {
                      solns->step = -1;
                      return 0;
                    }
                  goto star_3;
                  }

                /* Aha -- s2 matches R.  Does s1 match R*?
                 *
                 * Testing s1 against R* can modify some registers
                 * that were set while matching s2 to R.  These
                 * registers must be saved and then restored before 
                 * returning the overall match.
                 */
                if (save_nested_registers (solns))
                  {
                  longjmp (*err_escape, 1);
                  }

                if (solns->split_guess == solns->end)
                  solns->left = rx_make_solutions (solns->regs,
                                           solns->cset_size,
                                           solns->exp->left,
                                           solns->subexps,
                                           solns->nsub,
                                           solns->start,
                                           solns->split_guess,
                                           0,
                                           solns->vmfn,
                                           solns->contextfn,
                                           solns->closure,
                                           solns->small_p,
                                           0,
                                           0);
                else
                  solns->left = rx_make_solutions (solns->regs,
                                           solns->cset_size,
                                           solns->exp,
                                           solns->subexps,
                                           solns->nsub,
                                           solns->start,
                                           solns->split_guess,
                                           0,
                                           solns->vmfn,
                                           solns->contextfn,
                                           solns->closure,
                                           solns->small_p,
                                           0,
                                           0);
                if (!solns->left)
                  longjmp (*err_escape, 1);
                
                star_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                if (star_stat < 0)
                  longjmp (*err_escape, 1);

                if (star_stat != 1)
                  {
                  /* no matches for the left part of the split string
                   * at this split_guess.
                   */
                  rx_free_solutions (solns->left);
                  rx_free_solutions (solns->right);
                  solns->left = 0;
                  solns->right = 0;
                  if (solns->exp->left->len > 0)
                    {
                      solns->step = -1;
                      return 0;
                    }
                  ++solns->split_guess;
                  if (solns->split_guess > solns->end)
                    {
                      solns->step = -1;
                      return 0;
                    }
                  goto star_3;
                  }

                /* Found at least one solution for both s1 against R* and 
                 * s2 against R.
                 * 
                 * Return that solution.  First, restore the registers from
                 * the s2/R match:
                 * 
                 */

                restore_nested_registers (solns);
                solns->final_tag = solns->right->final_tag;
                solns->step = 4;
                return 1;
                
              case 4:
                /* This is reached when we've found one solution for
                 * s1 against R* and s2 against R, but that solution
                 * was rejected.
                 * 
                 * Try to find another solution for s2/R, using the same
                 * match for s1/R*.
                 */

                star_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
                if (star_stat < 0)
                  longjmp (*err_escape, 1);

                if (star_stat == 1)
                  {
                  /* found a match */
                  solns->final_tag = solns->right->final_tag;
                  solns->step = 4;
                  }

                /* No more matches for s2/R for the current match of s1/R*
                 * 
                 * We could look for another s1/R* match -- but why bother?
                 * Any changes to registers made by such a match are
                 * not observable after any s/R match.  So, try again with
                 * a different split guess:
                 */

                rx_free_solutions (solns->left);
                rx_free_solutions (solns->right);
                solns->left = 0;
                solns->right = 0;
                if (solns->exp->left->len > 0)
                  {
                  solns->step = -1;
                  return 0;
                  }
                ++solns->split_guess;
                if (solns->split_guess > solns->end)
                  {
                  solns->step = -1;
                  return 0;
                  }
                goto star_3;
              }
            }

          case r_interval:
            {
            /* On entry, interval_x is the number of iterations
             * already charged to this interval.  So, instead
             * of {intval, intval2}, the interval is actually:
             * 
             *    { max(0, intval - interval_x), 
             *      max(0, intval2 - interval_x) }
             * 
             */
            switch (solns->step)
              {
                int interval_stat;
                
              case 1:
                solns->interval_from = max0(solns->exp->intval - solns->interval_x);
                solns->interval_to = max0(solns->exp->intval2 - solns->interval_x);

                /* Should we try single iteration solutions?
                 *
                 * Yes if either:
                 *
                 *            (interval_from <= 1) && (interval_to >= 1)
                 * 
                 * or
                 *            ((solns->start == solns->end) && (interval_to >= 1))
                 * 
                 * If the string is the empty string (start == end), and any 
                 * iterations are permitted (interval_to >= 1) then all possible
                 * solutions (except the 0-iteration solution) can be found with 
                 * a single iteration.  Repeated iterations for a null match do not
                 * add new solutions compared to a single iteration because the 
                 * single iteration will always have the same side effects as multiple
                 * iterations ending with that single iteration.  
                 */

                if (   (   (solns->start == solns->end)
                      && (solns->interval_to >= 1)
                      && (   !solns->exp->left
                        || (solns->exp->left->len <= 0)))
                  || (   (solns->interval_from <= 1)
                      && (solns->interval_to >= 1)
                      && (solns->start != solns->end)
                      && solns->exp->left
                      && (   (solns->exp->left->len < 0)
                        || (solns->exp->left->len == (solns->end - solns->start)))))

                  {
                  solns->left = rx_make_solutions (solns->regs,
                                           solns->cset_size,
                                           solns->exp->left,
                                           solns->subexps,
                                           solns->nsub,
                                           solns->start,
                                           solns->end,
                                           0,
                                           solns->vmfn,
                                           solns->contextfn,
                                           solns->closure,
                                           solns->small_p,
                                           0,
                                           0);
                  if (!solns->left)
                    longjmp (*err_escape, 1);
                  case 2:
                  interval_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                  if (interval_stat < 0)
                    longjmp (*err_escape, 1);

                  if (interval_stat != 1)
                    {
                      rx_free_solutions (solns->left);
                      solns->left = 0;
                      goto try_0_iteration_null_match;
                    }
                  else
                    {
                      solns->step = 2;
                      return 1;
                    }
                  }

              try_0_iteration_null_match:

                /* If we're trying to match the empty string, and 0 iterations are
                 * permitted, that is the next best solution.  If we're trying to
                 * match the empty string, the 0 iteration solution is the only
                 * remaining possibility.
                 */
                if (solns->start == solns->end)
                  {
                  solns->step = -1;
                  return (solns->interval_from == 0);
                  }

                /* The string is not empty.  If only 0 iterations are permitted,
                 * then no solutions are possible.
                 */
                if (solns->interval_to == 0)
                  {
                  solns->step = -1;
                  return 0;
                  }

                /* The string is not empty and no single iteration solution works.
                 * Search through solutions with at least two iterations.  We split
                 * the string into two parts, and try to match the left part with N
                 * iterations (N >= 1) and the right part with 1 iteration.
                 * 
                 * To satisfy the left-to-right longest-subexpression rule, the right
                 * part (matched by the last iteration) should be as long as possible.
                 */

                if (!solns->exp->left || (solns->exp->left->len == 0))
                  {
                  /* never reached unless certain other optimizations are removed
                   */
                  solns->step = -1;
                  return 0;
                  }
                else if (solns->exp->left->len > 0)
                  {
                  if (   (solns->exp->left->len > (solns->end - solns->start))
                      || (0 != ((solns->end - solns->start) % solns->exp->left->len)))
                    {
                      solns->step = -1;
                      return 0;
                    }
                  solns->split_guess = solns->end - solns->exp->left->len;
                  }
                else
                  solns->split_guess = solns->start;

              interval_split_start_at_new_split_guess:

                solns->right = rx_make_solutions (solns->regs,
                                          solns->cset_size,
                                          solns->exp->left,
                                          solns->subexps,
                                          solns->nsub,
                                          solns->split_guess,
                                          solns->end,
                                          0,
                                          solns->vmfn,
                                          solns->contextfn,
                                          solns->closure,
                                          solns->small_p,
                                          0,
                                          0);
                if (!solns->right)
                  longjmp (*err_escape, 1);

              next_interval_right_solution:
                interval_stat = rx_next_solution_internal (solns->right, err_escape, depth + 1);
                if (interval_stat < 0)
                  longjmp (*err_escape, 1);

                if (interval_stat != 1)
                  {
                  rx_free_solutions (solns->right);
                  solns->right = 0;

                  
                  if (solns->exp->left->len < 0)
                    {
                      ++solns->split_guess;
                      if (solns->split_guess <= solns->end)
                        goto interval_split_start_at_new_split_guess;
                    }
                  /* No more solutions at all. */
                  solns->step = -1;
                  return 0;
                  }

                /* Found a solution for the right half of the split.
                 */

                if (save_nested_registers (solns))
                  {
                  longjmp (*err_escape, 1);
                  }
                solns->left = rx_make_solutions (solns->regs,
                                         solns->cset_size,
                                         solns->exp,
                                         solns->subexps,
                                         solns->nsub,
                                         solns->start,
                                         solns->split_guess,
                                         solns->interval_x + 1,
                                         solns->vmfn,
                                         solns->contextfn,
                                         solns->closure,
                                         solns->small_p,
                                         0,
                                         0);
                if (!solns->left)
                  longjmp (*err_escape, 1);

                interval_stat = rx_next_solution_internal (solns->left, err_escape, depth + 1);
                if (interval_stat < 0)
                  longjmp (*err_escape, 1);

                if (interval_stat != 1)
                  {
                  /* No more solutions for the left part of the string.
                   */
                  rx_free_solutions (solns->left);
                  solns->left = 0;
                  goto next_interval_right_solution;
                  }

                /* We found an overall solution for the interval.
                 */
                solns->step = 3;
                restore_nested_registers (solns);
                solns->final_tag = solns->right->final_tag;
                return 1;

              case 3:
                rx_free_solutions (solns->left);
                solns->left = 0;
                goto next_interval_right_solution;

              }
            }

          case r_context:
            {
            solns->step = -1;
            solns->final_tag = 1;
            return solns->contextfn (solns->closure,
                               solns->exp,
                               solns->start, solns->end,
                               solns->regs);
            }


          }
      }
      while (1)
      panic ("unreached in rx_next_solution_internal");
    }
}

/*(c rx_solutions_final_tag)
 * int rx_solutions_final_tag (struct rx_solutions * solns);
 * 
 * Return the state label of the last DFA state reached during
 * the solution most recently returned by `rx_next_solution'.
 */
int
rx_solutions_final_tag (struct rx_solutions * solns)
{
  return solns->final_tag;
}



/************************************************************************
 *(h1 "Building and Freeing a Stream of Solutions -- The General Case")
 * 
 * The functions in this section are quite general.  They can be used
 * to compare a regexp to a string which is not entirely in memory at
 * any one time.
 */
 
/*(c rx_make_solutions)
 * struct rx_solutions * 
 * rx_make_solutions (struct rx_registers * regs,
 *                int cset_size,
 *                struct rx_exp_node * expression,
 *                struct rx_exp_node ** subexps,
 *                int nsub,
 *                rx_off_t start,
 *                rx_off_t end,
 *                int interval_x,
 *                rx_vmfn vmfn,
 *                rx_contextfn contextfn,
 *                void * closure,
 *                int small_p,
 *                int certainly_fits,
 *                int certain_final_tag);
 * 
 * 
 * Construct a stream-of-solutions to a regexp matching problem.  For
 * arguments which are not documented here, see
 * xref:"rx_basic_make_solutions".
 *
 * If `expression' is of type `r_interval', then `interval_x' 
 * is the number of matches already accumulated for the subexpression.
 * In other words, if expression is `RE{M,N}', it will match as:
 * 
 *    RE{max (0,M - interval_x), max (0, N - interval_x)
 * 
 * This function does not directly accept an input string. Instead,
 * it accepts the parameters `vmfn', `contextfn', and `closure'.
 *
 * `vmfn' is a function which can return the address of a substring
 * containing a chosen character position within the entire input
 * string.  It is used to page-in parts of the input string during a
 * match.  The details of this parameter are given below.
 *
 * `contextfn' is a function that knows how to evaluate regexp
 * expressions which are anchors or backreferences.  These kinds of
 * subexpressions may be defined in terms of parts of the input string
 * that are not in memory or that are not contiguous in memory.  The
 * `contextfn' has the job of sorting that out in an efficient way.
 * The details of this parameter are also given below.
 *
 * `closure' is an opaque parameter that is passed along to `vmfn' and
 * `contextfn'.
 *
 * `small_p', if not 0, means that the regexp is so trivial that
 * heavy-weight optimizations are not likely to pay off.  It is always
 * safe to pass 0 for this parameter.  Internally, Rx passes a non-0
 * value if `expression' is 0 or if `expression->small_advised_p' is
 * non-0.  `expression->small_advised_p' is filled in by
 * `rx_analyze_rexp'.
 * 
 * `certainly_fits', if not 0, means that if `expression' is converted
 * to a true regular expression (such as by `rx_simplify_rexp') and
 * compared to the target string, the target string will certainly match.
 * Setting this field can speed up some matches.  If this field is
 * non-0, `certain_final_tag' must also be set.  It is always safe to 
 * pass 0 for `certainly_fits', though doing so may slow down some matches
 * slightly.
 * 
 * `certain_final_tag' is the final DFA state label returned for a
 * match of simplified form of `expression' against the target string.
 * This field is only used if `certainly_fits' is not 0.
 */
struct rx_solutions *
rx_make_solutions (struct rx_registers * regs,
               int cset_size,
               struct rx_exp_node * expression,
               struct rx_exp_node ** subexps,
               int nsub,
               rx_off_t start,
               rx_off_t end,
               int interval_x,
               rx_vmfn vmfn,
               rx_contextfn contextfn,
               void * closure,
               int small_p,
               int certainly_fits,
               int certain_final_tag)
{
  struct rx_solutions * solns;

  if (!expression && (start != end))
    return &no_solutions;

  if (   expression
      && (expression->len >= 0)
      && ((expression->type != r_interval)
        ? (expression->len != (end - start))
        : (/* Is an interval expression of fixed length */
           (!expression->len
            ? (end != start)
            : ((expression->len - (interval_x * expression->left->len)) != (end - start))))))
    return &no_solutions;

  solns = (struct rx_solutions *)rx_nfa_cache_malloc (sizeof (*solns));
  if (!solns)
    return 0;

  ++solns_allocated;

  solns->small_p = small_p;
  solns->step = 0;

  solns->cset_size = cset_size;
  solns->exp = expression;
  rx_save_exp (expression);
  solns->subexps = subexps;
  solns->nsub = nsub;
  solns->regs = regs;

  solns->start = start;
  solns->end = end;

  solns->vmfn = vmfn;
  solns->contextfn = contextfn;
  solns->closure = closure;

  solns->dfa = 0;
  solns->match_engine.rx = 0;
  solns->match_engine.state = 0;

  solns->certainly_fits = certainly_fits;
  solns->certain_final_tag = certain_final_tag;

  solns->no_fancy_guessing = 0;
  solns->left_dfa = 0;
  solns->left_match_engine.rx = 0;
  solns->left_match_engine.state = 0;

  solns->split_guess = 0;
  solns->left = 0;
  solns->right = 0;

  solns->interval_x = interval_x;
  solns->interval_from = 0;
  solns->interval_to = 0;

  solns->saved_rm_so = 0;
  solns->saved_rm_eo = 0;
  solns->final_tag = 0;

  if (!small_p)
    {
      if (!solns->exp || !solns->exp->observed)
      {
        solns->dfa = rx_unfa (expression, cset_size);
        if (!solns->dfa)
          {
            rx_free_solutions (solns);
            return 0;
          }
        rx_init_dfa_from_nfa (&solns->match_engine, solns->dfa->nfa);
        if (rx_dfa_goto_start_superstate (&solns->match_engine, 1))
          {
            rx_free_solutions (solns);
            return 0;
          }
      }
      else
      {
        struct rx_exp_node * simplified;
        if (rx_simplify_rexp (&simplified, cset_size, solns->exp, subexps))
          {
            rx_free_solutions (solns);
            return 0;
          }
        solns->dfa = rx_unfa (simplified, cset_size);
        if (!solns->dfa)
          {
            rx_free_exp (simplified);
            rx_free_solutions (solns);
            return 0;
          }
        rx_init_dfa_from_nfa (&solns->match_engine, solns->dfa->nfa);
        if (rx_dfa_goto_start_superstate (&solns->match_engine, 1))
          {
            rx_free_exp (simplified);
            rx_free_solutions (solns);
            return 0;
          }
        rx_free_exp (simplified);
      }
    }


  if (solns->exp && (solns->exp->observed || solns->small_p) && (solns->exp->type == r_concat))
    {
      struct rx_exp_node * left_simplified;
      
      if (rx_simplify_rexp (&left_simplified, cset_size, solns->exp->left, solns->subexps))
      {
        rx_free_solutions (solns);
        return 0;
      }

      solns->left_dfa = rx_unfa (left_simplified, cset_size);
      if (!solns->left_dfa)
      {
        rx_free_exp (left_simplified);
        rx_free_solutions (solns);
        return 0;
      }
      rx_init_dfa_from_nfa (&solns->left_match_engine, solns->left_dfa->nfa);
      rx_free_exp (left_simplified);
    }

  return solns;
}


/*(include-documentation "match-regexp.h")
 */


/*(c rx_solutions_closure)
 * void * rx_solutions_closure (struct rx_solutions * solns);
 * 
 * Given a stream of regexp solutions, return the `closure'
 * parameter that was passed to `rx_make_solutions'.
 */
void *
rx_solutions_closure (struct rx_solutions * solns)
{
  return solns->closure;
}


/*(c rx_free_solutions)
 * void rx_free_solutions (struct rx_solutions * solns);
 * 
 * Free all storage associated with a stream of regexp solutions
 * allocated by `rx_make_solutions'.  See also
 * xref:"rx_basic_free_solutions".
 */
void
rx_free_solutions (struct rx_solutions * solns)
{
  if (!solns)
    return;

  if (solns == &no_solutions)
    return;

  if (solns->left)
    {
      rx_free_solutions (solns->left);
      solns->left = 0;
    }

  if (solns->right)
    {
      rx_free_solutions (solns->right);
      solns->right = 0;
    }

  if (solns->dfa)
    {
      rx_free_unfa (solns->dfa);
      solns->dfa = 0;
    }

  rx_clear_dfa_state (&solns->match_engine);

  if (solns->left_dfa)
    {
      rx_free_unfa (solns->left_dfa);
      solns->left_dfa = 0;
    }

  rx_clear_dfa_state (&solns->left_match_engine);

  if (solns->exp)
    {
      rx_free_exp (solns->exp);
      solns->exp = 0;
    }

  if (solns->saved_rm_so)
    rx_nfa_cache_free (solns->saved_rm_so);

  if (solns->saved_rm_eo)
    rx_nfa_cache_free (solns->saved_rm_eo);

  rx_nfa_cache_free (solns);
  ++solns_freed;
}





/****************************************************************
 *(h1 "Regexp Tree To Regular Expression Conversion")
 *
 */

/*(c rx_simplify_rexp)
 * int rx_simplify_rexp (struct rx_exp_node ** answer,
 *                       int cset_size,
 *                       struct rx_exp_node *node,
 *                       struct rx_exp_node ** subexps);
 * 
 * Convert an expression, which might not be a regular expression, into
 * a regular expression matching a superset of the original pattern.
 *
 * This is useful for a matching heuristic: the regular superset
 * language is used to test a candidate string for a match, the
 * original irregular regexp is used to verify the match.  The test
 * using the regular superset is very fast and many non-matching
 * strings can be quickly rejected; the verification using the
 * irregular regexp may be slow, so we avoid it when we can.
 *
 * If the input expression is a regular expression, this is an
 * identity function which increments the reference count of `node'.
 *
 * `answer' is a return parameter.
 *
 * `subexps' is an array of pointers into the expression `node'.
 * Element `N' of the array is the `N'th parenthesized subexpression
 * of the tree rooted at `node'.  This array is usually computed by
 * `rx_analyze_rexp'.
 */
int
rx_simplify_rexp (struct rx_exp_node ** answer,
              int cset_size,
              struct rx_exp_node * node,
              struct rx_exp_node ** subexps)
{
  int err;

  if (!node)
    {
      *answer = 0;
      return 0;
    }

  if (!node->observed)
    {
      rx_save_exp (node);
      *answer = node;
      return 0;
    }

  if (node->simplified)
    {
      rx_save_exp (node->simplified);
      *answer = node->simplified;
      return 0;
    }

  switch (node->type)
    {
    default:
    case r_cset:
    case r_string:
    case r_cut:
      panic ("bogus regexp in rx_simplify_rexp");
      return -1;

    case r_parens:
      err = rx_simplify_rexp (answer, cset_size, node->left, subexps);
      if (err)
      return err;
      break;

    case r_context:
      if (char_is_digit (node->intval))
      {
        err = rx_simplify_rexp (answer, cset_size, subexps [node->intval - '0'], subexps);
        if (err)
          return err;
      }
      else
      *answer = 0;
      break;

    case r_concat:
    case r_right_concat:
    case r_alternate:
    case r_star:
    case r_interval:
      {
      struct rx_exp_node *n;

      n = rx_exp_node (node->type);
      if (!n)
        return REG_ESPACE;

      if (node->cset)
        {
          panic ("found a cset bitset in an unexpected place");
        }

      n->intval = node->intval;
      n->intval2 = node->intval2;
      err = rx_simplify_rexp (&n->left, cset_size, node->left, subexps);
      if (err)
        {
          rx_free_exp (n);
          return err;
        }
      err = rx_simplify_rexp (&n->right, cset_size, node->right, subexps);
      if (err)
        {
          rx_free_exp (n);
          return err;
        }
      *answer = n;
      }
      break;
    }
  
  node->simplified = *answer;
  rx_save_exp (node->simplified);
  return 0;
}



/****************************************************************
 *(h1 "Regexp Tree Analysis")
 *
 */

/*(c rx_analyze_rexp)
 * void rx_analyze_rexp (struct rx_exp_node *** subexps,
 *                       size_t * re_nsub,
 *                       struct rx_exp_node * node);
 * 
 * Recursively analyze the expression tree rooted at `node'.  For each
 * node, fill in the fields `observed', `observation_contingent',
 * `small_advised_p', and `len'.  Build an array of parenthesized
 * sub-expressions in the tree and return that array in `subexps' and
 * the number of elements it contains in `re_nsub'.
 *
 * See `struct rx_exp_node' for information about the meaning of
 * structure fields filled in by this function.
 */
int
rx_analyze_rexp (struct rx_exp_node *** subexps,
             size_t * re_nsub,
             struct rx_exp_node * node)
{
#define rx_max(a, b) ((a) > (b) ? (a) : (b))
#define rx_min(a, b) ((a) < (b) ? (a) : (b))
  if (node)
    {
      size_t this_subexp;

      this_subexp = 0;

      if (node->type == r_parens)
      {
        if (node->intval > 0)
          {
            struct rx_exp_node ** array;

            this_subexp = *re_nsub;
            ++*re_nsub;
            if (!*subexps)
            array = ((struct rx_exp_node **)
                   rx_nfa_cache_malloc (sizeof (struct rx_exp_node *) * *re_nsub));
            else
            array = ((struct rx_exp_node **)
                   rx_nfa_cache_realloc (*subexps,
                                     sizeof (struct rx_exp_node *) * *re_nsub));
            if (!array)
            return -1;
            else
            *subexps = array;
          }
      }

      if (node->left && rx_analyze_rexp (subexps, re_nsub, node->left))
      return -1;

      if (node->right && rx_analyze_rexp (subexps, re_nsub, node->right))
      return -1;

      switch (node->type)
      {
      case r_cset:
        node->len = 1;
        node->observed = 0;
        node->observation_contingent = 1;
        node->small_advised_p = 1;
        node->max_enclosed_paren = 0;
        node->min_enclosed_paren = 0;
        break;

      case r_string:
        node->len = node->str_len;
        node->observed = 0;
        node->observation_contingent = 1;
        node->small_advised_p = 1;
        node->max_enclosed_paren = 0;
        node->min_enclosed_paren = 0;
        break;

      case r_cut:
        node->len = -1;
        node->observed = 0;
        node->observation_contingent = 1;
        node->small_advised_p = 1;
        node->max_enclosed_paren = 0;
        node->min_enclosed_paren = 0;
        break;

      case r_concat:
      case r_right_concat:
      case r_alternate:
        {
          int lob, rob;
          int lobc, robc;
          long llen, rlen;

          lob = (!node->left ? 0 : node->left->observed);
          lobc = (!node->left ? 1 : node->left->observation_contingent);
          rob = (!node->right ? 0 : node->right->observed);
          robc = (!node->right ? 1 : node->right->observation_contingent);
          llen = (!node->left ? 0 : node->left->len);
          rlen = (!node->right ? 0 : node->right->len);

          if ((llen < 0) || (rlen < 0))
            node->len = -1;
          else if ((node->type == r_concat) || (node->type == r_right_concat))
            {
            if (((size_t)llen + (size_t)rlen) > SSIZE_MAX)
              panic ("absurdly large regexp in rx_analyze_rexp");
            node->len = (long)(llen + rlen);
            }
          else /* node->type == r_alternate */
            {
            if (llen == rlen)
              node->len = llen;
            else
              node->len = -1;
            }

          node->observed = lob || rob;
          node->observation_contingent = lobc && robc;

          if ((node->type == r_concat) || (node->type == r_right_concat))
            {
            node->small_advised_p = (   (!node->left || node->left->small_advised_p)
                               && (!node->right || node->right->small_advised_p));
            }
          else /* node->type == r_alternate */
            {
            node->small_advised_p = 0;
            }
          node->max_enclosed_paren = rx_max ((node->left ? node->left->max_enclosed_paren : 0),
                                     (node->right ? node->right->max_enclosed_paren : 0));
          {
            int lmin;
            int rmin;
            lmin = (node->left ? node->left->min_enclosed_paren : 0);
            rmin = (node->right ? node->right->min_enclosed_paren : 0);
            node->min_enclosed_paren = (!lmin
                                ? rmin
                                : (!rmin
                                   ? lmin
                                   : rx_min (lmin, rmin)));
          }
          break;
        }

      case r_star:
        node->len = ((node->left && node->left->len)
                   ? -1
                   : 0);
        node->observed = (node->left
                      ? node->left->observed
                      : 0);
        node->observation_contingent = (node->left
                                ? node->left->observation_contingent
                                : 1);
        node->small_advised_p = 0;
        node->max_enclosed_paren = (node->left ? node->left->max_enclosed_paren : 0);
        node->min_enclosed_paren = (node->left ? node->left->min_enclosed_paren : 0);
        break;

      case  r_interval:
        if (!node->left || (node->left->len == 0) || (node->intval2 == 0))
          node->len = 0;
        else if (node->left->len < 0)
          node->len = -1;
        else if (node->intval == node->intval2)
          {
            if (node->left->len > (SSIZE_MAX / node->intval))
            node->len = -1;
            else
            node->len = node->left->len * node->intval;
          }
        else
          node->len = -1;
        node->observed = 1;
        node->observation_contingent = 0;
        node->small_advised_p = 0;
        node->max_enclosed_paren = (node->left ? node->left->max_enclosed_paren : 0);
        node->min_enclosed_paren = (node->left ? node->left->min_enclosed_paren : 0);
        break;

      case r_parens:
        if (node->intval > 0)
          {
            node->observed = 1;
            (*subexps)[this_subexp] = node;
          }
        else
          node->observed = (node->left
                        ? node->left->observed
                        : 0);
        node->observation_contingent = (   node->observed 
                                && (node->left
                                    ? node->left->observation_contingent
                                    : 1));
        node->len = (node->left
                   ? node->left->len
                   : 0);
        node->small_advised_p = (!node->left || node->left->small_advised_p);
        node->max_enclosed_paren = rx_max (node->intval, (node->left ? node->left->max_enclosed_paren : 0));

        if (node->left && node->left->min_enclosed_paren)
          {
            if (!node->intval)
            node->min_enclosed_paren = node->left->min_enclosed_paren;
            else
            node->min_enclosed_paren = rx_min (node->intval, node->left->min_enclosed_paren);
          }
        else
          node->min_enclosed_paren = node->intval;
        break;

      case r_context:
        switch (node->intval)
          {
          default:
            node->small_advised_p = 1;
            node->observed = 1;
            node->observation_contingent = 0;
            node->len = -1;
            break;
          case '^':
          case '$':
            node->small_advised_p = 1;
            node->observed = 1;
            node->observation_contingent = 0;
            node->len = 0;
            break;
          }
        node->max_enclosed_paren = 0;
        node->min_enclosed_paren = 0;
        break;
      }
    }
  return 0;
}


Generated by  Doxygen 1.6.0   Back to index