built-in jambase is packed now

[k8jam.git] / src / hsregexp.c

/*
 * hsrxCompile and hsrxExec -- regsub and hsrxError are elsewhere
 *
 *  Copyright (c) 1986 by University of Toronto.
 *  Written by Henry Spencer.  Not derived from licensed software.
 *
 *  Permission is granted to anyone to use this software for any
 *  purpose on any computer system, and to redistribute it freely,
 *  subject to the following restrictions:
 *
 *  1. The author is not responsible for the consequences of use of
 *    this software, no matter how awful, even if they arise
 *    from defects in it.
 *
 *  2. The origin of this software must not be misrepresented, either
 *    by explicit claim or by omission.
 *
 *  3. Altered versions must be plainly marked as such, and must not
 *    be misrepresented as being the original software.
 *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
 *** hoptoad!gnu, on 27 Dec 1986, to add \n as an alternative to |
 *** to assist in implementing egrep.
 *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
 *** hoptoad!gnu, on 27 Dec 1986, to add \< and \> for word-matching
 *** as in BSD grep and ex.
 *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
 *** hoptoad!gnu, on 28 Dec 1986, to optimize characters quoted with \.
 *** THIS IS AN ALTERED VERSION.  It was altered by James A. Woods,
 *** ames!jaw, on 19 June 1987, to quash a hsrxCompile() redundancy.
 *** THIS IS AN ALTERED VERSION.  It was altered by Christopher Seiwald
 *** seiwald@vix.com, on 28 August 1993, for use in jam.  Regmagic.h
 *** was moved into regexp.h, and the include of regexp.h now uses "'s
 *** to avoid conflicting with the system regexp.h.  Const, bless its
 *** soul, was removed so it can compile everywhere.  The declaration
 *** of strchr() was in conflict on AIX, so it was removed (as it is
 *** happily defined in string.h).
 *** THIS IS AN ALTERED VERSION.  It was altered by Christopher Seiwald
 *** seiwald@perforce.com, on 20 January 2000, to use function prototypes.
 *** THIS IS AN ALTERED VERSION.  It was altered by Christopher Seiwald
 *** seiwald@perforce.com, on 05 November 2002, to const string literals.
 *
 *   THIS IS AN ALTERED VERSION.  It was altered by Steve Bennett <steveb@workware.net.au>
 *   on 16 October 2010, to remove static state and add better Tcl ARE compatibility.
 *   This includes counted repetitions, UTF-8 support, character classes,
 *   shorthand character classes, increased number of parentheses to 100,
 *   backslash escape sequences, non-greedy ops. It also removes \n as an alternative to |.
 *
 *   THIS IS AN ALTERED VERSION.  It was altered by Ketmar Dark (ketmar@ketmar.no-ip.org>
 *   in Sep, 2011, to add non-capturing brackets (?:...) and backreferences.
 *
 *   THIS IS AN ALTERED VERSION.  It was altered by Ketmar Dark (ketmar@ketmar.no-ip.org>
 *   in Nov, 2011, to add \b and \B
 *
 * Beware that some of this code is subtly aware of the way operator
 * precedence is structured in regular expressions.  Serious changes in
 * regular-expression syntax might require a total rethink.
 */
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "hsregexp.h"


#define MAYBE_UNUSED  __attribute__((unused))

/* obey POSIX bug with the meaning of ')' */
#define OBEY_POSIX_BUGS  0


/**
 * UTF-8 utility functions
 *
 * (c) 2010 Steve Bennett <steveb@workware.net.au>
 *
 * See LICENCE for licence details.
 */
struct casemap {
  unsigned short code; /* code point */
  unsigned short lower; /* code */
  unsigned short upper; /* code */
};


/* generated mapping tables */
#include "hsregexp_unicode_mapping.c"


#define NUMCASEMAP  (sizeof(unicode_case_mapping)/sizeof(*unicode_case_mapping))

static int cmp_casemap (const void *key, const void *cm) {
  return *(int *)key-(int)((const struct casemap *)cm)->code;
}


static int utf8_map_case (int uc, int upper) {
  const struct casemap *cm = bsearch(&uc, unicode_case_mapping, NUMCASEMAP, sizeof(*unicode_case_mapping), cmp_casemap);
  if (cm) uc = upper?cm->upper:cm->lower;
  return uc;
}


/**
 * Converts the given unicode codepoint (0 - 0xffff) to utf-8
 * and stores the result at 'p'.
 *
 * Returns the number of utf-8 characters (1-3).
 */
/* This one is always implemented */
static inline int utf8_fromunicode (char *p, unsigned short uc) {
  if (uc <= 0x7f) { *p = uc; return 1; }
  if (uc <= 0x7ff) { *p++ = 0xc0 | ((uc & 0x7c0) >> 6); *p = 0x80 | (uc & 0x3f); return 2; }
  *p++ = 0xe0 | ((uc & 0xf000) >> 12); *p++ = 0x80 | ((uc & 0xfc0) >> 6); *p = 0x80 | (uc & 0x3f); return 3;
}


/**
 * Returns the unicode codepoint corresponding to the
 * utf-8 sequence 'str'.
 *
 * Stores the result in *uc and returns the number of bytes
 * consumed.
 *
 * If 'str' is null terminated, then an invalid utf-8 sequence
 * at the end of the string will be returned as individual bytes.
 *
 * If it is not null terminated, the length *must* be checked first.
 *
 * Does not support unicode code points > \uffff
 */
static inline int utf8_tounicode (const char *str, int *uc) {
  unsigned const char *s = (unsigned const char *)str;
  //
  if (s[0] < 0xc0) { *uc = s[0]; return 1; }
  if (s[0] < 0xe0) {
    if ((s[1] & 0xc0) == 0x80) { *uc = ((s[0] & ~0xc0) << 6) | (s[1] & ~0x80); return 2; }
  } else if (s[0] < 0xf0) {
    if (((str[1] & 0xc0) == 0x80) && ((str[2] & 0xc0) == 0x80)) {
      *uc = ((s[0] & ~0xe0) << 12) | ((s[1] & ~0x80) << 6) | (s[2] & ~0x80);
      return 3;
    }
  }
  /* invalid sequence, so just return the byte */
  *uc = *s;
  return 1;
}


/**
 * Returns the length of the utf-8 sequence starting with 'c'.
 *
 * Returns 1-4, or -1 if this is not a valid start byte.
 *
 * Note that charlen=4 is not supported by the rest of the API.
 */
static MAYBE_UNUSED inline int utf8_charlen (int c) {
  if ((c&0x80) == 0) return 1;
  if ((c&0xe0) == 0xc0) return 2;
  if ((c&0xf0) == 0xe0) return 3;
  if ((c&0xf8) == 0xf0) return 4;
  /* invalid sequence */
  return -1;
}


/**
 * Returns the number of characters in the utf-8
 * string of the given byte length.
 *
 * Any bytes which are not part of an valid utf-8
 * sequence are treated as individual characters.
 *
 * The string *must* be null terminated.
 *
 * Does not support unicode code points > \uffff
 */
static MAYBE_UNUSED int utf8_strlen (const char *str, int bytelen) {
  int charlen = 0;
  //
  if (bytelen < 0) bytelen = strlen(str);
  while (bytelen) {
    int c, l = utf8_tounicode(str, &c);
    ++charlen;
    str += l;
    bytelen -= l;
  }
  return charlen;
}


/**
 * Returns the byte index of the given character in the utf-8 string.
 *
 * The string *must* be null terminated.
 *
 * This will return the byte length of a utf-8 string
 * if given the char length.
 */
static MAYBE_UNUSED inline int utf8_index (const char *str, int index) {
  const char *s = str;
  //
  while (index--) {
    int c;
    s += utf8_tounicode(s, &c);
  }
  return s-str;
}


/**
 * Returns the number of bytes before 'str' that the previous
 * utf-8 character sequence starts (which may be the middle of a sequence).
 *
 * Looks back at most 'len' bytes backwards, which must be > 0.
 * If no start char is found, returns -len
 */
static MAYBE_UNUSED inline int utf8_prev_len (const char *str, int len) {
  int n = 1;
  //
  //assert(len > 0);
  /* look up to len chars backward for a start-of-char byte */
  while (--len) {
    if ((str[-n] & 0x80) == 0) break; /* start of a 1-byte char */
    if ((str[-n] & 0xc0) == 0xc0) break; /* start of a multi-byte char */
    ++n;
  }
  return n;
}


/**
 * Returns the upper-case variant of the given unicode codepoint.
 *
 * Does not support unicode code points > \uffff
 */
static MAYBE_UNUSED int utf8_upper (int uc) {
  if (isascii(uc)) return toupper(uc);
  return utf8_map_case(uc, 1);
}


/**
 * Returns the lower-case variant of the given unicode codepoint.
 *
 * NOTE: Use utf8_upper() in preference for case-insensitive matching.
 *
 * Does not support unicode code points > \uffff
 */
static MAYBE_UNUSED int utf8_lower (int uc) {
  if (isascii(uc)) return tolower(uc);
  return utf8_map_case(uc, 0);
}


static MAYBE_UNUSED inline int utf8_charequal (const char *s1, const char *s2) {
  int c1, c2;
  //
  utf8_tounicode(s1, &c1);
  utf8_tounicode(s2, &c2);
  return c1==c2;
}


#define UCHAR(c)  ((unsigned char)(c))


/* This *MUST* be less than (255-20-2)/2=116 */
#define HSRX_MAX_PAREN  (100)

/*
 * Structure for regexp "program". This is essentially a linear encoding
 * of a nondeterministic finite-state machine (aka syntax charts or
 * "railroad normal form" in parsing technology). Each node is an opcode
 * plus a "next" pointer, possibly plus an operand. "Next" pointers of
 * all nodes except BRANCH implement concatenation; a "next" pointer with
 * a BRANCH on both ends of it is connecting two alternatives. Here we
 * have one of the subtle syntax dependencies: an individual BRANCH (as
 * opposed to a collection of them) is never concatenated with anything
 * because of operator precedence. The operand of some types of node is
 * a literal string; for others, it is a node leading into a sub-FSM.
 * In particular, the operand of a BRANCH node is the first node of the
 * branch.
 * (NB this is *not* a tree structure: the tail of the branch connects
 * to the thing following the set of BRANCHes.)
 * The opcodes are:
 */
/* definition_num   opnd?       meaning */
#define END       0 /* no       end of program */
#define BOL       1 /* no       match "" at beginning of line */
#define EOL       2 /* no       match "" at end of line */
#define ANY       3 /* no       match any one character */
#define ANYOF     4 /* str      match any character in this string */
#define ANYBUT    5 /* str      match any character not in this string */
#define BRANCH    6 /* node     match this alternative, or the next... */
#define BACK      7 /* no       match "", "next" ptr points backward */
#define EXACTLY   8 /* str      match this string */
#define NOTHING   9 /* no       match empty string */
#define REP      10 /* max,min  match this (simple) thing [min,max] times */
#define REPMIN   11 /* max,min  match this (simple) thing [min,max] times, mininal match */
#define REPX     12 /* max,min  match this (complex) thing [min,max] times */
#define REPXMIN  13 /* max,min  match this (complex) thing [min,max] times, minimal match */
/* no 14 */
#define WORDA    15 /* no       match "" at wordchar, where prev is nonword */
#define WORDZ    16 /* no       match "" at nonwordchar, where prev is word */
#define BACKREF  17 /* captnum  match previous capture here */
#define WBRK     18 /* no       match word break -- \b */
#define WNBRK    19 /* no       match non-word-break -- \B */
/* */
#define OPEN     20 /* no       mark this point in input as start of #n (OPEN+1 is number 1, etc) */
#define CLOSE    (OPEN+HSRX_MAX_PAREN) /* analogous to OPEN */
#define CLOSEEND (CLOSE+HSRX_MAX_PAREN)

#define NCOPEN    (CLOSEEND+0)
#define NCCLOSE   (CLOSEEND+1)


/*
 * The first byte of the regexp internal "program" is actually this magic
 * number; the start node begins in the second byte.
 */
#define HSRX_MAGIC  (0xFADED00DUL)


/*
 * Opcode notes:
 *
 * BRANCH The set of branches constituting a single choice are hooked
 *    together with their "next" pointers, since precedence prevents
 *    anything being concatenated to any individual branch.  The
 *    "next" pointer of the last BRANCH in a choice points to the
 *    thing following the whole choice.  This is also where the
 *    final "next" pointer of each individual branch points; each
 *    branch starts with the operand node of a BRANCH node.
 *
 * BACK   Normal "next" pointers all implicitly point forward; BACK
 *    exists to make loop structures possible.
 *
 * STAR,PLUS  '?', and complex '*' and '+', are implemented as circular
 *    BRANCH structures using BACK.  Simple cases (one character
 *    per match) are implemented with STAR and PLUS for speed
 *    and to minimize recursive plunges.
 *
 * OPEN,CLOSE ...are numbered at compile time.
 */


/*
 * A node is one char of opcode followed by two chars of "next" pointer.
 * "Next" pointers are stored as two 8-bit pieces, high order first.  The
 * value is a positive offset from the opcode of the node containing it.
 * An operand, if any, simply follows the node.  (Note that much of the
 * code generation knows about this implicit relationship.)
 *
 * Using two bytes for the "next" pointer is vast overkill for most things,
 * but allows patterns to get big without disasters.
 */
#define OP(preg, p)    (preg->program[p])
#define NEXT(preg, p)  (preg->program[p+1])
#define OPERAND(p)     ((p)+2)


/*
 * Utility definitions.
 */

#define FAIL(R,M)   {(R)->err = (M); return (M);}
#define ISMULT(c)   ((c)=='*'||(c)=='+'||(c)=='?'||(c) == '{')
#define META        "$.[()|?{+*"


/*
 * Flags to be passed up and down.
 */
#define WORST     0 /* worst case */
#define HASWIDTH  1 /* known never to match null string */
#define SIMPLE    2 /* simple enough to be STAR/PLUS operand */
#define SPSTART   4 /* starts with * or + */


#define MAX_REP_COUNT  (1000000)


/*
 * Forward declarations for hsrxCompile()'s friends.
 */
static int reg (HSRegExp *preg, int paren /*parenthesized?*/, int *flagp);
static int regpiece (HSRegExp *preg, int *flagp);
static int regbranch (HSRegExp *preg, int *flagp);
static int regatom (HSRegExp *preg, int *flagp);
static int regnode (HSRegExp *preg, int op);
static int regnext (HSRegExp *preg, int p);
static void regc (HSRegExp *preg, int b);
static int reginsert (HSRegExp *preg, int op, int size, int opnd);
static void regtail_ (HSRegExp *preg, int p, int val, int line);
static void regoptail (HSRegExp *preg, int p, int val);
#define regtail(PREG, P, VAL)  regtail_(PREG, P, VAL, __LINE__)

static int reg_range_find (HSRegExp *preg, const int *string, int c);
static const char *str_find (HSRegExp *preg, const char *string, int c);
static int prefix_cmp (HSRegExp *preg, const int *prog, int proglen, const char *string);

#ifdef HSRX_DEBUG
int hsrxNarrate = 0;
void hsrxDump (HSRegExp *preg);
static const char *regprop (int op);
#endif


/**
 * Returns the length of the null-terminated integer sequence.
 */
static
#if __GNUC__ > 2
__attribute__((pure))
#endif
inline int str_int_len (const int *seq) {
  int n = 0;
  while (*seq++) ++n;
  return n;
}


/*
 - hsrxCompile - compile a regular expression into internal code
 *
 * We can't allocate space until we know how big the compiled form will be,
 * but we can't compile it (and thus know how big it is) until we've got a
 * place to put the code.  So we cheat:  we compile it twice, once with code
 * generation turned off and size counting turned on, and once "for real".
 * This also means that we don't allocate space until we are sure that the
 * thing really will compile successfully, and we never have to move the
 * code and thus invalidate pointers into it.  (Note that it has to be in
 * one piece because free() must be able to free it all.)
 *
 * Beware that the optimization-preparation code in here knows about some
 * of the structure of the compiled regexp.
 */
int hsrxCompile (HSRegExp *preg, const char *exp, int cflags) {
  int scan, longest, flags;
  unsigned int len;
  //
#ifdef HSRX_DEBUG
  fprintf(stderr, "Compiling: '%s'\n", exp);
#endif
  memset(preg, 0, sizeof(*preg));
  if (exp == NULL) FAIL(preg, HSRX_ERR_NULL_ARGUMENT);
  /* first pass: determine size, legality */
  preg->start = exp; /* for '^' special */
  preg->cflags = cflags;
  preg->regparse = exp;
  /* XXX: for now, start unallocated */
  preg->program = NULL;
  preg->proglen = 0;
#if 1
  /* allocate space */
  preg->proglen = (strlen(exp)+1)*5;
  preg->program = malloc(preg->proglen*sizeof(int));
  if (preg->program == NULL) FAIL(preg, HSRX_ERR_NOMEM);
#endif
  /* note that since we store a magic value as the first item in the program, program offsets will never be 0 */
  regc(preg, HSRX_MAGIC);
  if (reg(preg, 0, &flags) == 0) return preg->err;
  /* small enough for pointer-storage convention? */
  if (preg->re_nsub >= HSRX_MAX_PAREN) FAIL(preg, HSRX_ERR_TOO_BIG); /* probably could be 65535L */
  preg->bmatch = malloc(sizeof(HSRxMatch)*(preg->re_nsub+1));
  if (preg->bmatch == NULL) FAIL(preg, HSRX_ERR_NOMEM);
  /* dig out information for optimizations. */
  preg->regstart = 0; /* worst-case defaults */
  preg->reganch = 0;
  preg->regmust = 0;
  preg->regmlen = 0;
  scan = 1; /* first BRANCH */
  if (OP(preg, regnext(preg, scan)) == END) {
    /* only one top-level choice */
    scan = OPERAND(scan);
    /* starting-point info */
    if (OP(preg, scan) == EXACTLY) preg->regstart = preg->program[OPERAND(scan)];
    else if (OP(preg, scan) == BOL) ++preg->reganch;
    /*
     * If there's something expensive in the r.e., find the
     * longest literal string that must appear and make it the
     * regmust.  Resolve ties in favor of later strings, since
     * the regstart check works with the beginning of the r.e.
     * and avoiding duplication strengthens checking.  Not a
     * strong reason, but sufficient in the absence of others.
     */
    if (flags&SPSTART) {
      longest = 0;
      len = 0;
      for (; scan != 0; scan = regnext(preg, scan)) {
        if (OP(preg, scan) == EXACTLY) {
          int plen = str_int_len(preg->program+OPERAND(scan));
          if (plen >= len) {
            longest = OPERAND(scan);
            len = plen;
          }
        }
      }
      preg->regmust = longest;
      preg->regmlen = len;
    }
  }
#ifdef HSRX_DEBUG
  hsrxDump(preg);
#endif
  return 0;
}


/*
 - reg - regular expression, i.e. main body or parenthesized thing
 *
 * Caller must absorb opening parenthesis.
 *
 * Combining parenthesis handling with the base level of regular expression
 * is a trifle forced, but the need to tie the tails of the branches to what
 * follows makes it hard to avoid.
 *
 * paren:
 *   0: not parentesized
 *   1: normal parens
 *   2: non-capturing parens
 */
static int reg (HSRegExp *preg, int paren, int *flagp) {
  int ret, br, ender, flags;
  int parno = 0;
  //
  *flagp = HASWIDTH; /* tentatively */
  /* make an OPEN node, if parenthesized */
  if (paren) {
    // new (capturing) paren
    parno = paren==1?++preg->re_nsub:-666;
    ret = regnode(preg, paren==1?OPEN+parno:NCOPEN);
  } else {
    ret = 0;
  }
  /* pick up the branches, linking them together */
  br = regbranch(preg, &flags);
  if (br == 0) return 0;
  if (ret != 0) regtail(preg, ret, br); /* OPEN -> first */ else ret = br;
  if (!(flags&HASWIDTH)) *flagp &= ~HASWIDTH;
  *flagp |= flags&SPSTART;
  while (*preg->regparse == '|') {
    ++preg->regparse;
    br = regbranch(preg, &flags);
    if (br == 0) return 0;
    regtail(preg, ret, br); /* BRANCH -> BRANCH */
    if (!(flags&HASWIDTH)) *flagp &= ~HASWIDTH;
    *flagp |= flags&SPSTART;
  }
  /* make a closing node, and hook it on the end */
  ender = regnode(preg, (paren)?(paren==1?CLOSE+parno:NCCLOSE):END);
  regtail(preg, ret, ender);
  /* hook the tails of the branches to the closing node */
  for (br = ret; br != 0; br = regnext(preg, br)) regoptail(preg, br, ender);
  /* check for proper termination */
  if (paren) {
    if (preg->cflags&HSRX_EXTENDED) {
      if (*preg->regparse++ != ')') { preg->err = HSRX_ERR_UNMATCHED_PAREN; return 0; }
    } else {
      if (preg->regparse[0] != '\\' || preg->regparse[1] != ')') { preg->err = HSRX_ERR_UNMATCHED_PAREN; return 0; }
      preg->regparse += 2;
    }
  }
  if (!paren && *preg->regparse != '\0') {
    if (preg->cflags&HSRX_EXTENDED) {
      if (*preg->regparse == ')') { preg->err = HSRX_ERR_UNMATCHED_PAREN; return 0; }
    } else {
      if (preg->regparse[0] == '\\' && preg->regparse[1] == ')') { preg->err = HSRX_ERR_UNMATCHED_PAREN; return 0; }
    }
    preg->err = HSRX_ERR_JUNK_ON_END;
    return 0;
  }
  preg->start = NULL;
  return ret;
}


/*
 - regbranch - one alternative of an | operator
 *
 * Implements the concatenation operator.
 */
static int regbranch (HSRegExp *preg, int *flagp) {
  int ret, chain, latest, flags;
  //
  *flagp = WORST; /* tentatively */
  ret = regnode(preg, BRANCH);
  chain = 0;
  while (*preg->regparse != '\0') {
    if (preg->cflags&HSRX_EXTENDED) {
      if (*preg->regparse == ')' || *preg->regparse == '|') break;
    } else {
      if (preg->regparse[0] == '\\' && preg->regparse[1] == ')') break;
    }
    latest = regpiece(preg, &flags);
    if (latest == 0) return 0;
    *flagp |= flags&HASWIDTH;
    if (chain == 0) *flagp |= flags&SPSTART; /* first piece */ else regtail(preg, chain, latest);
    chain = latest;
  }
  if (chain == 0) regnode(preg, NOTHING); /* loop ran zero times */
  return ret;
}


/*
 - regpiece - something followed by possible [*+?]
 *
 * Note that the branching code sequences used for ? and the general cases
 * of * and + are somewhat optimized:  they use the same NOTHING node as
 * both the endmarker for their branch list and the body of the last branch.
 * It might seem that this node could be dispensed with entirely, but the
 * endmarker role is not redundant.
 */
static int regpiece (HSRegExp *preg, int *flagp) {
  char op;
  int ret, next, flags, min, max;
  int chain = 0;
  //
  ret = regatom(preg, &flags);
  if (ret == 0) return 0;
  op = *preg->regparse;
  if (preg->cflags&HSRX_EXTENDED) {
    if (!ISMULT(op)) { *flagp = flags; return ret; }
    if (!(flags&HASWIDTH) && op != '?') { preg->err = HSRX_ERR_OPERAND_COULD_BE_EMPTY; return 0; }
  } else {
    if (op != '*') {
      if (op == '\\' && preg->regparse[1] == '{') {
        op = '{';
        ++preg->regparse; /* skip slash */
      } else {
        *flagp = flags;
        return ret;
      }
    }
  }
  /* handle braces (counted repetition) by expansion */
  if (op == '{') {
    /* for non-extended regexps this is the only possible path */
    char *end;
    //
    ++preg->regparse; /* skip paren */
    while (isspace(*preg->regparse)) ++preg->regparse; /* skip spaces */
    /* first number */
    if (*preg->regparse == ',') {
      ++preg->regparse;
      min = 0;
    } else {
      min = strtoul(preg->regparse, &end, 10);
      if (end == preg->regparse) { preg->err = HSRX_ERR_BAD_COUNT; return 0; }
      preg->regparse = end;
    }
    /* second number */
    while (isspace(*preg->regparse)) ++preg->regparse; /* skip spaces */
    if (*preg->regparse == ',') {
      ++preg->regparse;
      while (isspace(*preg->regparse)) ++preg->regparse; /* skip spaces */
      if (!(isdigit(*preg->regparse))) {
        max = MAX_REP_COUNT;
      } else {
        max = strtoul(preg->regparse, &end, 10);
        if (end == preg->regparse) { preg->err = HSRX_ERR_BAD_COUNT; return 0; }
        preg->regparse = end;
      }
    } else {
      max = min;
    }
    if (max > min || min < 0 || max < 0 || min > MAX_REP_COUNT || max > MAX_REP_COUNT) { preg->err = HSRX_ERR_BAD_COUNT; return 0; }
    /* check for proper termination */
    while (isspace(*preg->regparse)) ++preg->regparse; /* skip spaces */
    if (preg->cflags&HSRX_EXTENDED) {
      if (*preg->regparse != '}') { preg->err = HSRX_ERR_UNMATCHED_BRACES; return 0; }
      ++preg->regparse;
    } else {
      if (preg->regparse[0] != '\\' || preg->regparse[1] != '}') { preg->err = HSRX_ERR_UNMATCHED_BRACES; return 0; }
      preg->regparse += 2;
    }
  } else {
    min = op=='+'?1:0;
    max = op=='?'?1:MAX_REP_COUNT;
    ++preg->regparse; /* skip special */
  }
  /* insert 'repeat' opcode */
  if ((preg->cflags&HSRX_EXTENDED) && *preg->regparse == '?') {
    ++preg->regparse;
    next = reginsert(preg, flags&SIMPLE?REPMIN:REPXMIN, 5, ret);
  } else {
    next = reginsert(preg, flags&SIMPLE?REP:REPX, 5, ret);
  }
  preg->program[ret+2] = max;
  preg->program[ret+3] = min;
  preg->program[ret+4] = 0;
  *flagp = (min)?(WORST|HASWIDTH):(WORST|SPSTART);
  if (!(flags&SIMPLE)) {
    int back = regnode(preg, BACK);
    regtail(preg, back, ret);
    regtail(preg, next, back);
  }
  if (preg->cflags&HSRX_EXTENDED) {
    if (ISMULT(*preg->regparse)) { preg->err = HSRX_ERR_NESTED_COUNT; return 0; }
  } else {
    if (*preg->regparse == '*' || (preg->regparse[0] == '\\' && preg->regparse[1] == '{')) { preg->err = HSRX_ERR_NESTED_COUNT; return 0; }
  }
  return chain?chain:ret;
}


/**
 * Add all characters in the inclusive range between lower and upper.
 *
 * Handles a swapped range (upper < lower).
 */
static void reg_addrange (HSRegExp *preg, int lower, int upper) {
  if (lower > upper) reg_addrange(preg, upper, lower);
  /* add a range as length, start */
  regc(preg, upper-lower+1);
  regc(preg, lower);
}


/**
 * Add a null-terminated literal string as a set of ranges.
 */
/*
static void reg_addrange_str (HSRegExp *preg, const char *str) {
  while (*str) { reg_addrange(preg, *str, *str); ++str; }
}
*/


/**
 * Extracts the next unicode char from utf8.
 *
 * If 'upper' is set, converts the char to uppercase.
 */
static inline int reg_utf8_tounicode_case (HSRegExp *preg, const char *s, int *uc, int upper) {
  if (preg->cflags&HSRX_UTF8) {
    int l = utf8_tounicode(s, uc);
    if (upper) *uc = utf8_upper(*uc);
    return l;
  }
  *uc = upper?toupper(*s):(unsigned char)(*s);
  return 1;
}


/**
 * Extracts the next unicode char from utf8.
 *
 * If 'upper' is set, converts the char to uppercase.
 */
static inline int reg_utf8_tounicode_caseR (HSRegExp *preg, const char *s, int *uc, int upper) {
  if (preg->eflags&HSRX_UTF8) {
    int l = utf8_tounicode(s, uc);
    if (upper) *uc = utf8_upper(*uc);
    return l;
  }
  *uc = upper?toupper(*s):(unsigned char)(*s);
  return 1;
}


/**
 * Converts a hex digit to decimal.
 *
 * Returns -1 for an invalid hex digit.
 */
static inline int hexdigitval (int c) {
  if (c >= '0' && c <= '9') return c-'0';
  if (c >= 'a' && c <= 'f') return c-'a'+10;
  if (c >= 'A' && c <= 'F') return c-'A'+10;
  return -1;
}


/**
 * Parses up to 'n' hex digits at 's' and stores the result in *uc.
 *
 * Returns the number of hex digits parsed.
 * If there are no hex digits, returns 0 and stores nothing.
 */
static int parse_hex (const char *s, int n, int *uc) {
  int k, val = 0;
  //
  for (k = 0; k < n; ++k) {
    int c = hexdigitval(*s++);
    if (c == -1) break;
    val = (val<<4)|c;
  }
  if (k) *uc = val;
  return k;
}


/**
 * Call for chars after a backlash to decode the escape sequence.
 *
 * Stores the result in *ch.
 *
 * Returns the number of bytes consumed.
 */
static int reg_decode_escape (const char *s, int *ch) {
  int n;
  const char *s0 = s;
  //
  *ch = *s++;
  switch (*ch) {
    case 'a': *ch = '\a'; break;
    case 'b': *ch = '\b'; break;
    case 'e': *ch = 27; break;
    case 'f': *ch = '\f'; break;
    case 'n': *ch = '\n'; break;
    case 'r': *ch = '\r'; break;
    case 't': *ch = '\t'; break;
    case 'v': *ch = '\v'; break;
    case 'u':
      if ((n = parse_hex(s, 4, ch)) > 0) s += n;
      break;
    case 'x':
      if ((n = parse_hex(s, 2, ch)) > 0) s += n;
      break;
    case '\0':
      --s;
      *ch = '\\';
      break;
  }
  return s-s0;
}


/*
 - regatom - the lowest level
 *
 * Optimization:  gobbles an entire sequence of ordinary characters so that
 * it can turn them into a single node, which is smaller to store and
 * faster to run.  Backslashed characters are exceptions, each becoming a
 * separate node; the code is simpler that way and it's not worth fixing.
 */
static int regatom (HSRegExp *preg, int *flagp) {
  int ret, flags, ch;
  int nocase = preg->cflags&HSRX_ICASE;
  int n = reg_utf8_tounicode_case(preg, preg->regparse, &ch, nocase);
  int forced = 0;
  //
  *flagp = WORST; /* tentatively */
  preg->regparse += n;
  switch (ch) {
    case '^': /* this char only have special meaning at beging of pat */
      if (preg->regparse-n != preg->start) {
        switch (*(preg->regparse-n-1)) {
          case '(': break;
          case '|': if (preg->cflags&HSRX_EXTENDED) break; /* fallthru */
          default: forced = 1; goto de_fault;
        }
      }
      ret = regnode(preg, BOL);
      if (!(preg->cflags&HSRX_EXTENDED) && *preg->regparse == '*') goto de_fault;
      break;
    case '$': /* this char only have special meaning at end of pat */
      switch (*preg->regparse) {
        case 0: case ')': break;
        case '|': if (preg->cflags&HSRX_EXTENDED) break; /* fallthru */
        default: forced = 1; goto de_fault;
      }
      ret = regnode(preg, EOL);
      break;
    case '.':
      ret = regnode(preg, ANY);
      *flagp |= HASWIDTH|SIMPLE;
      break;
    case '[': {
      const char *pattern = preg->regparse;
      //
      if (*pattern == '^') {
        /* complement of range */
        ret = regnode(preg, ANYBUT);
        ++pattern;
      } else {
        ret = regnode(preg, ANYOF);
      }
      /* special case: if the first char is ']' or '-', it is part of the set */
      if (*pattern == ']' || *pattern == '-') {
        reg_addrange(preg, *pattern, *pattern);
        ++pattern;
      }
      while (*pattern && *pattern != ']') {
        /* is this a range? a-z */
        int start, end;
        //
        pattern += reg_utf8_tounicode_case(preg, pattern, &start, nocase);
        if (start == '\\') {
          pattern += reg_decode_escape(pattern, &start);
          if (start == 0) { preg->err = HSRX_ERR_NULL_CHAR; return 0; }
        }
        if (pattern[0] == '-' && pattern[1]) {
          ++pattern; /* skip '-' */
          pattern += reg_utf8_tounicode_case(preg, pattern, &end, nocase);
          if (end == '\\') {
            pattern += reg_decode_escape(pattern, &end);
            if (end == 0) { preg->err = HSRX_ERR_NULL_CHAR; return 0; }
          }
          reg_addrange(preg, start, end);
          continue;
        }
        if ((preg->cflags&HSRX_EXTENDED) && start == '[') {
          if (strncmp(pattern, ":alpha:]", 8) == 0) {
            pattern += 8;
            if (!nocase) reg_addrange(preg, 'a', 'z');
            reg_addrange(preg, 'A', 'Z');
            continue;
          }
          if (strncmp(pattern, ":alnum:]", 8) == 0) {
            pattern += 8;
            if (!nocase) reg_addrange(preg, 'a', 'z');
            reg_addrange(preg, 'A', 'Z');
            reg_addrange(preg, '0', '9');
            continue;
          }
          if (strncmp(pattern, ":space:]", 8) == 0) {
            pattern += 8;
            //reg_addrange_str(preg, " \t\r\n\f\v");
            reg_addrange(preg, 9, 13);
            reg_addrange(preg, 32, 32);
            continue;
          }
          if (strncmp(pattern, ":blank:]", 8) == 0) {
            pattern += 8;
            //reg_addrange_str(preg, " \t\f\v");
            reg_addrange(preg, 9, 9);
            reg_addrange(preg, 11, 12);
            reg_addrange(preg, 32, 32);
            continue;
          }
          if (strncmp(pattern, ":digit:]", 8) == 0) {
            pattern += 8;
            reg_addrange(preg, '0', '9');
            continue;
          }
          if (strncmp(pattern, ":lower:]", 8) == 0) {
            pattern += 8;
            if (nocase) reg_addrange(preg, 'A', 'Z'); else reg_addrange(preg, 'a', 'z');
            continue;
          }
          if (strncmp(pattern, ":upper:]", 8) == 0) {
            pattern += 8;
            reg_addrange(preg, 'A', 'Z');
            continue;
          }
          if (strncmp(pattern, ":xdigit:]", 9) == 0) {
            pattern += 9;
            reg_addrange(preg, '0', '9');
            if (!nocase) reg_addrange(preg, 'a', 'f');
            reg_addrange(preg, 'A', 'F');
            continue;
          }
        }
        /* not a range, so just add the char */
        reg_addrange(preg, start, start);
      }
      regc(preg, 0);
      if (*pattern) ++pattern;
      preg->regparse = pattern;
      *flagp |= HASWIDTH|SIMPLE;
      } break;
    case '(':
      // only for exteded mode
      if (preg->regparse[0] == '?' && preg->regparse[1] == ':') {
        // non-capturing bracket
        preg->regparse += 2;
        ret = reg(preg, 2, &flags);
        goto bracecont;
      }
bracestart:
      ret = reg(preg, 1, &flags);
bracecont:
      if (ret == 0) return 0;
      *flagp |= flags&(HASWIDTH|SPSTART);
      break;
    case '\0': preg->err = HSRX_ERR_INTERNAL; return 0; /* supposed to be caught earlier */
    case ')':
#if OBEY_POSIX_BUGS
      forced = 1;
      goto de_fault;
#endif
    case '|':
      if (preg->cflags&HSRX_EXTENDED) { preg->err = HSRX_ERR_INTERNAL; return 0; } /* supposed to be caught earlier */
      forced = 1;
      goto de_fault;
    case '?':
    case '+':
    case '{':
    case '*':
      if (preg->cflags&HSRX_EXTENDED) { preg->err = HSRX_ERR_COUNT_FOLLOWS_NOTHING; return 0; }
      forced = 1;
      goto de_fault;
    case '\\':
      switch (*preg->regparse++) {
        case '\0': preg->err = HSRX_ERR_TRAILING_BACKSLASH; return 0;
        case '<': case 'm': ret = regnode(preg, WORDA); break;
        case '>': case 'M': ret = regnode(preg, WORDZ); break;
        case 'd': case 'D':
          ret = regnode(preg, preg->regparse[-1]=='d'?ANYOF:ANYBUT);
          reg_addrange(preg, '0', '9');
          regc(preg, 0);
          *flagp |= HASWIDTH|SIMPLE;
          break;
        case 'b': ret = regnode(preg, WBRK); break;
        case 'B': ret = regnode(preg, WNBRK); break;
        case 'w': case 'W':
          ret = regnode(preg, preg->regparse[-1]=='w'?ANYOF:ANYBUT);
          if (!(preg->cflags&HSRX_ICASE)) reg_addrange(preg, 'a', 'z');
          reg_addrange(preg, 'A', 'Z');
          reg_addrange(preg, '0', '9');
          reg_addrange(preg, '_', '_');
          regc(preg, 0);
          *flagp |= HASWIDTH|SIMPLE;
          break;
        case 's': case 'S':
          ret = regnode(preg, preg->regparse[-1]=='s'?ANYOF:ANYBUT);
          //reg_addrange_str(preg," \t\r\n\f\v");
          reg_addrange(preg, 9, 13);
          reg_addrange(preg, 32, 32);
          regc(preg, 0);
          *flagp |= HASWIDTH|SIMPLE;
          break;
        case '(':
          if (!(preg->cflags&HSRX_EXTENDED)) goto bracestart;
          goto escnotspecial;
        case '{':
          if (!(preg->cflags&HSRX_EXTENDED)) { preg->err = HSRX_ERR_COUNT_FOLLOWS_NOTHING; return 0; }
          goto escnotspecial;
        case ')':
        case '}':
          if (!(preg->cflags&HSRX_EXTENDED)) { preg->err = HSRX_ERR_INTERNAL; return 0; } /* supposed to be caught earlier */
          goto escnotspecial;
        case '0' ... '9':
          n = 0; ch = 0; --(preg->regparse);
          while (isdigit(preg->regparse[0])) {
            n = (n*10)+preg->regparse[0]-'0';
            if (n > HSRX_MAX_PAREN) { preg->regparse -= ch; preg->err = HSRX_ERR_INVALID_BACKREF; return 0; }
            ++(preg->regparse);
            ++ch;
          }
          if (ch > 1) {
            /* eat possible ';' */
            if (preg->regparse[0] == ';') { ++(preg->regparse); ++ch; }
          }
          if (n < 1 || n > preg->re_nsub) { preg->regparse -= ch; preg->err = HSRX_ERR_INVALID_BACKREF; return 0; }
          ret = regnode(preg, BACKREF);
          regc(preg, n);
          break;
        default:
          /* handle general quoted chars in exact-match routine */
          /* back up to include the backslash */
escnotspecial:
          --preg->regparse;
          forced = 1;
          goto de_fault;
      }
      break;
de_fault:
    default: {
      /* encode a string of characters to be matched exactly */
      int added = 0;
      /* back up to pick up the first char of interest */
      preg->regparse -= n;
      ret = regnode(preg, EXACTLY);
      /* note that a META operator such as ? or * consumes the preceding char */
      /* thus we must be careful to look ahead by 2 and add the last char as it's own EXACTLY if necessary */
      /* until end of string or a META char is reached */
      while (*preg->regparse && (forced || strchr(META, *preg->regparse) == NULL)) {
        forced = 0;
        n = reg_utf8_tounicode_case(preg, preg->regparse, &ch, preg->cflags&HSRX_ICASE);
        if (ch == '\\' && preg->regparse[n]) {
          /* non-trailing backslash: is this a special escape, or a regular escape? */
          if (strchr("<>mMwds", preg->regparse[n])) break; /* a special escape; all done with EXACTLY */
          if (!(preg->cflags&HSRX_EXTENDED) && strchr("(){}", preg->regparse[n])) break; /* a special escape; all done with EXACTLY */
          /* decode it; note that we add the length for the escape
           * sequence to the length for the backlash so we can skip
           * the entire sequence, or not as required
           */
          n += reg_decode_escape(preg->regparse+n, &ch);
          if (ch == 0) { preg->err = HSRX_ERR_NULL_CHAR; return 0; }
        }
        /* now we have one char 'ch' of length 'n'; check to see if the following char is a MULT */
        if (((preg->cflags&HSRX_EXTENDED) && ISMULT(preg->regparse[n])) ||
            (!(preg->cflags&HSRX_EXTENDED) && (preg->regparse[n] == '*' || (preg->regparse[n] == '\\' && preg->regparse[n+1] == '{')))) {
          /* yes, but do we already have some EXACTLY chars? */
          if (added) break; /* yes, so return what we have and pick up the current char next time around */
          /* no, so add this single char and finish */
          regc(preg, ch);
          ++added;
          preg->regparse += n;
          break;
        }
        /* no, so just add this char normally */
        regc(preg, ch);
        ++added;
        preg->regparse += n;
      }
      regc(preg, 0);
      *flagp |= HASWIDTH;
      if (added == 1) *flagp |= SIMPLE;
      break;
    }
    break;
  }
  return ret;
}


static void reg_grow (HSRegExp *preg, int n) {
  if (preg->p+n >= preg->proglen) {
    preg->proglen = (preg->p+n)*2;
    preg->program = realloc(preg->program, preg->proglen*sizeof(int));
  }
}


/*
 - regnode - emit a node
 */
/* location */
static int regnode (HSRegExp *preg, int op) {
  reg_grow(preg, 2);
  preg->program[preg->p++] = op;
  preg->program[preg->p++] = 0;
  /* return the start of the node */
  return preg->p-2;
}


/*
 - regc - emit (if appropriate) a byte of code
 */
static void regc (HSRegExp *preg, int b) {
  reg_grow(preg, 1);
  preg->program[preg->p++] = b;
}


/*
 - reginsert - insert an operator in front of already-emitted operand
 *
 * Means relocating the operand.
 * Returns the new location of the original operand.
 */
static int reginsert (HSRegExp *preg, int op, int size, int opnd) {
  reg_grow(preg, size);
  /* move everything from opnd up */
  memmove(preg->program+opnd+size, preg->program+opnd, sizeof(int)*(preg->p-opnd));
  /* zero out the new space */
  memset(preg->program+opnd, 0, sizeof(int)*size);
  preg->program[opnd] = op;
  preg->p += size;
  return opnd+size;
}


/*
 - regtail - set the next-pointer at the end of a node chain
 */
static void regtail_ (HSRegExp *preg, int p, int val, int line) {
  int scan, temp, offset;
  /* find last node */
  scan = p;
  for (;;) {
    temp = regnext(preg, scan);
    if (temp == 0) break;
    scan = temp;
  }
  offset = OP(preg, scan)==BACK?scan-val:val-scan;
  preg->program[scan+1] = offset;
}


/*
 - regoptail - regtail on operand of first argument; nop if operandless
 */
static void regoptail (HSRegExp *preg, int p, int val) {
  /* "operandless" and "op != BRANCH" are synonymous in practice */
  if (p != 0 && OP(preg, p) == BRANCH) regtail(preg, OPERAND(p), val);
}


/*
 * hsrxExec and friends
 */

/*
 * forwards
 */
static int regtry (HSRegExp *preg, const char *string);
static int regmatch (HSRegExp *preg, int prog);
static int regrepeat (HSRegExp *preg, int p, int max);


/*
 - hsrxExec - match a regexp against a string
 */
int hsrxExec (HSRegExp *preg, const char *string, size_t nmatch, HSRxMatch pmatch[], int eflags) {
  const char *s;
  int scan;
  //int parens[HSRX_MAX_PAREN+1];
  /* be paranoid... */
  if (preg == NULL || preg->program == NULL || string == NULL) return HSRX_ERR_NULL_ARGUMENT;
  /* check validity of program */
  if (*preg->program != HSRX_MAGIC) return HSRX_ERR_CORRUPTED;
#ifdef HSRX_DEBUG
  fprintf(stderr, "hsrxExec: %s\n", string);
  hsrxDump(preg);
#endif
  preg->eflags = eflags;
  preg->pmatch = pmatch;
  preg->nmatch = nmatch;
  preg->start = string; /* all offsets are computed from here */
  /* must clear out the embedded repeat counts */
  for (scan = OPERAND(1); scan != 0; scan = regnext(preg, scan)) {
    switch (OP(preg, scan)) {
      case REP: case REPMIN: case REPX: case REPXMIN: preg->program[scan+4] = 0; break;
    }
  }
  /* clear matches for backrefing */
  for (scan = 0; scan <= preg->re_nsub; ++scan) preg->bmatch[scan].rm_so = preg->bmatch[scan].rm_eo = -1;
  /* if there is a "must appear" string, look for it */
  if (preg->regmust != 0) {
    s = string;
    while ((s = str_find(preg, s, preg->program[preg->regmust])) != NULL) {
      if (prefix_cmp(preg, preg->program+preg->regmust, preg->regmlen, s) >= 0) {
        break;
      }
      ++s;
    }
    if (s == NULL) return HSRX_NOMATCH; /* not present */
  }
  /* mark beginning of line for ^ */
  preg->regbol = string;
  /* simplest case: anchored match need be tried only once (maybe per line) */
  if (preg->reganch) {
    if (!(preg->cflags&HSRX_NEWLINE) && (eflags&HSRX_NOTBOL)) {
      /* this is an anchored search, but not an BOL, so possibly skip to the next line */
      goto nextline;
    }
    for (;;) {
      int ret = regtry(preg, string);
      if (ret) return HSRX_NOERROR;
      if (*string) {
nextline:
        if (preg->cflags&HSRX_NEWLINE) {
          /* try the next anchor? */
          string = strchr(string, '\n');
          if (string == NULL) { preg->regbol = ++string; continue; }
        }
      }
      return HSRX_NOMATCH;
    }
  }
  /* messy cases: unanchored match */
  s = string;
  if (preg->regstart != '\0') {
    /* we know what char it must start with */
    while ((s = str_find(preg, s, preg->regstart)) != NULL) {
      if (regtry(preg, s)) return HSRX_NOERROR;
      ++s;
    }
  } else {
    /* we don't -- general case */
    while (*string) {
      int l;
      if (regtry(preg, s)) return HSRX_NOERROR;
      if (*s == '\0') break;
      l = eflags&HSRX_UTF8?utf8_charlen(*s):1;
      s += l;
    }
  }
  /* failure */
  return HSRX_NOMATCH;
}


/*
 - regtry - try match at specific point
 */
/* 0 failure, 1 success */
static int regtry (HSRegExp *preg, const char *string) {
  int i;
  //
  preg->reginput = string;
  for (i = 0; i < preg->nmatch; ++i) preg->pmatch[i].rm_so = preg->pmatch[i].rm_eo = -1;
  if (regmatch(preg, 1)) {
    if (preg->nmatch > 0 && preg->pmatch != NULL) {
      preg->pmatch[0].rm_so = string-preg->start;
      preg->pmatch[0].rm_eo = preg->reginput-preg->start;
    }
    return 1;
  }
  return 0;
}


/**
 * Returns bytes matched if 'pattern' is a prefix of 'string'.
 *
 * If 'nocase' is non-zero, does a case-insensitive match.
 *
 * Returns -1 on not found.
 */
static int prefix_cmp (HSRegExp *preg, const int *prog, int proglen, const char *string) {
  const char *s = string;
  int nocase = preg->cflags&HSRX_ICASE;
  //
  while (proglen && *s) {
    int ch, n = reg_utf8_tounicode_caseR(preg, s, &ch, nocase);
    //
    if (ch != *prog) return -1;
    ++prog;
    s += n;
    --proglen;
  }
  if (proglen == 0) return s-string;
  return -1;
}


/**
 * Search for the character 'c' in the utf-8 string 'string'.
 *
 * If 'nocase' is set, the 'string' is assumed to be uppercase
 * and 'c' is converted to uppercase before matching.
 *
 * Returns the byte position in the string where the 'c' was found, or
 * NULL if not found.
 */
static const char *str_find (HSRegExp *preg, const char *string, int c) {
  int nocase = preg->cflags&HSRX_ICASE;
  //
  if (nocase) c = utf8_upper(c);
  while (*string) {
    int ch, n = reg_utf8_tounicode_caseR(preg, string, &ch, nocase);
    //
    if (c == ch) return string;
    string += n;
  }
  return NULL;
}


/**
 * Searchs for 'c' in the range 'range'.
 *
 * Returns 1 if found, or 0 if not.
 */
static int reg_range_find (HSRegExp *preg, const int *range, int c) {
  if (preg->cflags&HSRX_ICASE) c = utf8_upper(c);
  while (*range) {
    /*printf("checking %d in range [%d,%d]\n", c, range[1], (range[0]+range[1]-1));*/
    if (c >= range[1] && c <= range[0]+range[1]-1) return 1;
    range += 2;
  }
  return 0;
}


/**
 * Returns true if 'ch' is an end-of-line char.
 *
 * In HSRX_NEWLINE mode, \n is considered EOL in
 * addition to \0
 */
static int reg_iseol (HSRegExp *preg, int ch) {
  if (preg->cflags&HSRX_NEWLINE) return ch=='\0'||ch=='\n';
  return ch=='\0';
}


static int regmatchsimplerepeat (HSRegExp *preg, int scan, int matchmin) {
  int no, c;
  const char *save;
  int nextch = '\0';
  int max = preg->program[scan+2];
  int min = preg->program[scan+3];
  int next = regnext(preg, scan);
  /* lookahead to avoid useless match attempts when we know what character comes next */
  if (OP(preg, next) == EXACTLY) nextch = preg->program[OPERAND(next)];
  save = preg->reginput;
  no = regrepeat(preg, scan+5, max);
  if (no < min) return 0;
  if (matchmin) {
    /* from min up to no */
    max = no;
    no = min;
  }
  /* else from no down to min */
  for (;;) {
    if (matchmin) {
      if (no > max) break;
    } else {
      if (no < min) break;
    }
    preg->reginput = save+utf8_index(save, no);
    reg_utf8_tounicode_caseR(preg, preg->reginput, &c, preg->cflags&HSRX_ICASE);
    /* if it could work, try it */
    if (reg_iseol(preg, nextch) || c == nextch) {
      if (regmatch(preg, next)) return 1;
    }
    if (matchmin) {
      /* couldn't or didn't, add one more */
      ++no;
    } else {
      /* couldn't or didn't, back up */
      --no;
    }
  }
  return 0;
}


static int regmatchrepeat (HSRegExp *preg, int scan, int matchmin) {
  int *scanpt = preg->program+scan;
  int max = scanpt[2];
  int min = scanpt[3];
  //
  /* have we reached min? */
  if (scanpt[4] < min) {
    /* no, so get another one */
    ++(scanpt[4]);
    if (regmatch(preg, scan+5)) return 1;
    --(scanpt[4]);
    return 0;
  }
  if (scanpt[4] > max) return 0;
  if (matchmin) {
    /* minimal, so try other branch first */
    if (regmatch(preg, regnext(preg, scan))) return 1;
    /* no, so try one more */
    ++(scanpt[4]);
    if (regmatch(preg, scan+5)) return 1;
    --(scanpt[4]);
    return 0;
  }
  /* maximal, so try this branch again */
  if (scanpt[4] < max) {
    ++(scanpt[4]);
    if (regmatch(preg, scan+5)) return 1;
    --(scanpt[4]);
  }
  /* at this point we are at max with no match: try the other branch */
  return regmatch(preg, regnext(preg, scan));
}


static int prevChar (HSRegExp *preg) {
  if (preg->reginput == preg->start) return 0;
  if (preg->eflags&HSRX_UTF8) {
    int c;
    const char *pcp = preg->reginput-utf8_prev_len(preg->reginput, preg->reginput-preg->start);
    reg_utf8_tounicode_caseR(preg, pcp, &c, preg->cflags&HSRX_ICASE);
    return c;
  }
  return (unsigned char)(preg->reginput[-1]);
}


/*TODO: unicode word breaks?*/
static inline int isWordChar (int ch) {
  return
    (ch >= 'a' && ch <= 'z') ||
    (ch >= 'A' && ch <= 'Z') ||
    (ch >= '0' && ch <= '9') ||
    (ch == '_');
}


/*
 - regmatch - main matching routine
 *
 * Conceptually the strategy is simple:  check to see whether the current
 * node matches, call self recursively to see whether the rest matches,
 * and then act accordingly.  In practice we make some effort to avoid
 * recursion, in particular by going through "ordinary" nodes (that don't
 * need to know whether the rest of the match failed) by a loop instead of
 * by recursion.
 */
/* 0 failure, 1 success */
static int regmatch (HSRegExp *preg, int prog) {
  int scan; /* current node */
  int next; /* next node */
  //
  scan = prog;
#ifdef HSRX_DEBUG
  if (scan != 0 && hsrxNarrate) fprintf(stderr, "%s(\n", regprop(scan));
#endif
  while (scan != 0) {
    int n, c, s;
#ifdef HSRX_DEBUG
    if (hsrxNarrate) {
      //fprintf(stderr, "%s...\n", regprop(scan));
      fprintf(stderr, "%3d: %s...\n", scan, regprop(OP(preg, scan))); /* where, what */
    }
#endif
    next = regnext(preg, scan);
    n = reg_utf8_tounicode_caseR(preg, preg->reginput, &c, preg->cflags&HSRX_ICASE);
    switch (OP(preg, scan)) {
      case BOL:
        if ((preg->cflags&HSRX_NEWLINE) || !(preg->eflags&HSRX_NOTBOL)) {
          if (preg->reginput != preg->regbol) return 0;
        }
        if (!(preg->cflags&HSRX_NEWLINE) && (preg->eflags&HSRX_NOTBOL)) return 0;
        break;
      case EOL:
        if ((preg->cflags&HSRX_NEWLINE) || !(preg->eflags&HSRX_NOTEOL)) {
          if (!reg_iseol(preg, c)) return 0;
        }
        if (!(preg->cflags&HSRX_NEWLINE) && (preg->eflags&HSRX_NOTEOL)) return 0;
        break;
      case WORDA:
        /* must be looking at a letter, digit, or _ */
        if (!isalnum(UCHAR(c)) && c != '_') return 0;
        /* prev must be BOL or nonword */
        if (preg->reginput > preg->regbol && (isalnum(UCHAR(preg->reginput[-1])) || preg->reginput[-1] == '_')) return 0;
        break;
      case WORDZ:
        /* can't match at BOL */
        if (preg->reginput > preg->regbol) {
          /* current must be EOL or nonword */
          if (reg_iseol(preg, c) || !isalnum(UCHAR(c)) || c != '_') {
            c = preg->reginput[-1];
            /* previous must be word */
            if (isalnum(UCHAR(c)) || c == '_') break;
          }
        }
        /* no */
        return 0;
      case WBRK:
        if (isWordChar(prevChar(preg)) == isWordChar(c)) return 0; /* failed */
        break;
      case WNBRK:
        if (isWordChar(prevChar(preg)) != isWordChar(c)) return 0; /* failed */
        break;
      case ANY:
        if (reg_iseol(preg, c)) return 0;
        preg->reginput += n;
        break;
      case EXACTLY: {
        int opnd = OPERAND(scan);
        int len = str_int_len(preg->program+opnd);
        int slen = prefix_cmp(preg, preg->program+opnd, len, preg->reginput);
        //
        if (slen < 0) return 0;
        preg->reginput += slen;
        } break;
      case ANYOF:
        if (reg_iseol(preg, c) || reg_range_find(preg, preg->program+OPERAND(scan), c) == 0) return 0;
        preg->reginput += n;
        break;
      case ANYBUT:
        if (reg_iseol(preg, c) || reg_range_find(preg, preg->program+OPERAND(scan), c) != 0) return 0;
        preg->reginput += n;
        break;
      case NOTHING: break;
      case BACK: break;
      case BRANCH:
        if (OP(preg, next) != BRANCH) {
          /* no choice */
          next = OPERAND(scan); /* avoid recursion */
        } else {
          const char *save;
          //
          do {
            save = preg->reginput;
            if (regmatch(preg, OPERAND(scan))) return 1;
            preg->reginput = save;
            scan = regnext(preg, scan);
          } while (scan != 0 && OP(preg, scan) == BRANCH);
          return 0;
          /* NOTREACHED */
        }
        break;
      case REP:
      case REPMIN:
        return regmatchsimplerepeat(preg, scan, OP(preg, scan) == REPMIN);
      case REPX:
      case REPXMIN:
        return regmatchrepeat(preg, scan, OP(preg, scan) == REPXMIN);
      case END:
        return 1; /* success! */
      case BACKREF: /* backreference */
        c = preg->program[OPERAND(scan)];
#ifdef HSRX_DEBUG
        printf("BACKREF: %d (%d)\n", c, preg->re_nsub);
#endif
        if (c < 1 || c > preg->re_nsub) return 0; /* invalid backref can't be matched */
        s = preg->bmatch[c].rm_so;
#ifdef HSRX_DEBUG
        printf("  %d;%d\n", s, preg->bmatch[c].rm_eo);
#endif
        if (s < 0 || preg->bmatch[c].rm_eo < s) return 0; /* capture not found yet */
        /* check string */
        n = preg->bmatch[c].rm_eo-s; /* capture length */
        /* dumb compare */
        for (c = 0; c < n; ++c) {
#ifdef HSRX_DEBUG
          printf(" [%c] [%c]\n", preg->reginput[c], preg->start[s+c]);
#endif
          if (!preg->reginput[c] || preg->reginput[c] != preg->start[s+c]) {
#ifdef HSRX_DEBUG
            printf("  FAIL!\n");
#endif
            return 0; /* alas */
          }
        }
#ifdef HSRX_DEBUG
        printf("  HIT!\n");
#endif
        /* move position and return success */
        preg->reginput += n;
        break;
      default:
        if (OP(preg, scan) >= OPEN+1 && OP(preg, scan) <= /*CLOSEEND*/NCCLOSE) {
          const char *save = preg->reginput;
          //int saveso = 0, saveeo = 0;
          //
          if (OP(preg, scan) < CLOSEEND) {
            if (OP(preg, scan) < CLOSE) {
              c = OP(preg, scan)-OPEN;
              preg->bmatch[c].rm_so = save-preg->start;
            } else {
              c = OP(preg, scan)-CLOSE;
              preg->bmatch[c].rm_eo = save-preg->start;
            }
          }
          //
          if (regmatch(preg, next)) {
            /* don't set startp if some later invocation of the same parentheses already has */
            if (OP(preg, scan) < CLOSEEND) {
              /* capturing parens */
              if (OP(preg, scan) < CLOSE) {
                /* open */
                c = OP(preg, scan)-OPEN;
                if (c < preg->nmatch && preg->pmatch[c].rm_so == -1) preg->pmatch[c].rm_so = save-preg->start;
              } else {
                /* close */
                c = OP(preg, scan)-CLOSE;
                if (c < preg->nmatch && preg->pmatch[c].rm_eo == -1) preg->pmatch[c].rm_eo = save-preg->start;
              }
            }
            return 1;
          }
          //
          if (OP(preg, scan) < CLOSEEND) {
            if (OP(preg, scan) < CLOSE) {
              c = OP(preg, scan)-OPEN;
              preg->bmatch[c].rm_so = -1;
            } else {
              c = OP(preg, scan)-CLOSE;
              preg->bmatch[c].rm_eo = -1;
            }
          }
          //
          return 0;
        }
        return HSRX_ERR_INTERNAL;
    }
    scan = next;
  }
  /* we get here only if there's trouble -- normally "case END" is the terminating point */
  return HSRX_ERR_INTERNAL;
}


/*
 - regrepeat - repeatedly match something simple, report how many
 */
static int regrepeat (HSRegExp *preg, int p, int max) {
  const char *scan;
  int opnd, ch, n;
  int count = 0;
  //
  scan = preg->reginput;
  opnd = OPERAND(p);
  switch (OP(preg, p)) {
    case ANY:
      /* no need to handle utf8 specially here */
      while (!reg_iseol(preg, *scan) && count < max) { ++count; ++scan; }
      break;
    case EXACTLY:
      while (count < max) {
        n = reg_utf8_tounicode_caseR(preg, scan, &ch, preg->cflags&HSRX_ICASE);
        if (preg->program[opnd] != ch) break;
        ++count;
        scan += n;
      }
      break;
    case ANYOF:
      while (count < max) {
        n = reg_utf8_tounicode_caseR(preg, scan, &ch, preg->cflags&HSRX_ICASE);
        if (reg_iseol(preg, ch) || reg_range_find(preg, preg->program+opnd, ch) == 0) break;
        ++count;
        scan += n;
      }
      break;
    case ANYBUT:
      while (count < max) {
        n = reg_utf8_tounicode_caseR(preg, scan, &ch, preg->cflags&HSRX_ICASE);
        if (reg_iseol(preg, ch) || reg_range_find(preg, preg->program+opnd, ch) != 0) break;
        ++count;
        scan += n;
      }
      break;
    default: /* ih dear! called inappropriately */
      preg->err = HSRX_ERR_INTERNAL;
      count = 0; /* best compromise */
      break;
  }
  preg->reginput = scan;
  return count;
}


/*
 - regnext - dig the "next" pointer out of a node
 */
static int regnext (HSRegExp *preg, int p) {
  int offset = NEXT(preg, p);
  //
  if (offset == 0) return 0;
  if (OP(preg, p) == BACK) return p-offset;
  return p+offset;
}


#ifdef HSRX_DEBUG
/*
 - hsrxDump - dump a regexp onto stdout in vaguely comprehensible form
 */
static void dumpChar (int ch) {
  if (ch > 255) {
    printf("{0x%x}", (unsigned int)ch);
  } else if (ch < 32 || ch >= 127) {
    printf("{%d}", ch);
  } else {
    putchar(ch);
  }
}


void hsrxDump (HSRegExp *preg) {
  int s, next, i;
  char buf[4];
  int op = EXACTLY; /* arbitrary non-END op */
  //
  for (i = 1; i < preg->p; ++i) {
    printf("%02x ", preg->program[i]);
    if (i%16 == 15) printf("\n");
  }
  printf("\n");
  //
  s = 1;
  /* while that wasn't END last time... */
  while (op != END && s < preg->p) {
    op = OP(preg, s);
    printf("%3d: %-12s", s, regprop(op)); /* where, what */
    next = regnext(preg, s);
    if (next == 0) {
      /* next ptr */
      printf("(0)");
    } else {
      printf("(%d)", next);
    }
    s += 2;
    if (op == REP || op == REPMIN || op == REPX || op == REPXMIN) {
      int max = preg->program[s];
      int min = preg->program[s+1];
      //
      if (max == 65535) printf(" {%d,*}", min); else printf(" {%d,%d}", min, max);
      printf(" %d", preg->program[s+2]);
      s += 3;
    } else if (op == ANYOF || op == ANYBUT) {
      /* set of ranges */
      printf(" r: [");
      while (preg->program[s]) {
        int len = preg->program[s++];
        int first = preg->program[s++];
        /*
        buf[utf8_fromunicode(buf, first)] = 0;
        printf("%s", buf);
        if (len > 1) {
          buf[utf8_fromunicode(buf, first+len-1)] = 0;
          printf("-%s", buf);
        }
        */
        dumpChar(first);
        printf("-");
        if (len > 1) {
          dumpChar(first+len-1);
        } else {
          dumpChar(first);
        }
      }
      printf("]");
      ++s;
    } else if (op == EXACTLY) {
      /* literal string, where present */
      printf(" l: '");
      while (preg->program[s]) {
        /*
        buf[utf8_fromunicode(buf, preg->program[s])] = 0;
        printf("%s", buf);
        */
        dumpChar(preg->program[s]);
        ++s;
      }
      printf("'");
      ++s;
    } else if (op == BACKREF) {
      printf(" refno: %d", preg->program[s++]);
    }
    putchar('\n');
  }
  if (op == END) {
    /* header fields of interest */
    if (preg->regstart) {
      buf[utf8_fromunicode(buf, preg->regstart)] = 0;
      printf("start '%s' ", buf);
    }
    if (preg->reganch) printf("anchored ");
    if (preg->regmust != 0) {
      int i;
      //
      printf("must have:");
      for (i = 0; i < preg->regmlen; ++i) putchar(preg->program[preg->regmust+i]);
      putchar('\n');
    }
  }
  printf("\n");
}


/*
 - regprop - printable representation of opcode
 */
static const char *regprop (int op) {
  static char buf[50];
  //
  switch (op) {
    case BOL: return "BOL";
    case EOL: return "EOL";
    case ANY: return "ANY";
    case ANYOF: return "ANYOF";
    case ANYBUT: return "ANYBUT";
    case BRANCH: return "BRANCH";
    case EXACTLY: return "EXACTLY";
    case NOTHING: return "NOTHING";
    case BACK: return "BACK";
    case END: return "END";
    case REP: return "REP";
    case REPMIN: return "REPMIN";
    case REPX: return "REPX";
    case REPXMIN: return "REPXMIN";
    case WORDA: return "WORDA";
    case WORDZ: return "WORDZ";
    case BACKREF: return "BACKREF";
    case NCOPEN: return "NCOPEN";
    case NCCLOSE: return "NCCLOSE";
    default:
      if (op >= OPEN && op < CLOSE) snprintf(buf, sizeof(buf), "OPEN:%d", op-OPEN);
      else if (op >= CLOSE && op < CLOSEEND) snprintf(buf, sizeof(buf), "CLOSE:%d", op-CLOSE);
      else snprintf(buf, sizeof(buf), "?%d?\n", op);
      return buf;
  }
}
#endif


size_t hsrxError (int errcode, const HSRegExp *preg, char *errbuf,  size_t errbuf_size) {
  static const char *error_strings[] = {
    "success",
    "no match",
    "bad pattern",
    "null argument",
    "unknown error",
    "too big",
    "out of memory",
    "too many ()",
    "parentheses () not balanced",
    "braces {} not balanced",
    "invalid repetition count(s)",
    "extra characters",
    "*+ of empty atom",
    "nested count",
    "internal error",
    "count follows nothing",
    "trailing backslash",
    "corrupted program",
    "contains null char",
    "invalid backreference number",
  };
  const char *err;
  //
  if (errcode < 0 || errcode >= HSRX_ERR_NUM) {
    err = "Bad error code";
  } else {
    err = error_strings[errcode];
  }
  return snprintf(errbuf, errbuf_size, "%s", err);
}


void hsrxFree (HSRegExp *preg) {
  if (preg != NULL) {
    if (preg->bmatch != NULL) free(preg->bmatch); preg->bmatch = NULL;
    if (preg->program != NULL) free(preg->program); preg->program = NULL;
  }
}