added API to compile non-asciiz regular expressions

[libre9.git] / src / libre9 / re9.c

/*
 * The authors of this software are Rob Pike and Ken Thompson.
 * Copyright (c) 2002 by Lucent Technologies.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 *
 * heavily modified by Ketmar // Vampire Avalon
 */
#include "re9.h"

#include <ctype.h>
#include <limits.h>
#include <setjmp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>


/******************************************************************************/
#define PACKED  __attribute__((packed))

#define ARRAYLEN(_a)  ((sizeof((_a)))/sizeof((_a)[0]))

#ifdef RE9_DEBUG
# define dlogf(...)  fprintf(stderr, __VA_ARGS__)
#else
# define dlogf(...)
#endif

//#define RE9_DEBUG_PRG
//#define RE9_CALC_MAXT


/******************************************************************************/
typedef uint32_t re9_rune;


enum {
  PRG_STARTS_WITH_ANY = 0x00,
  PRG_STARTS_WITH_BOL = 0x01,
  PRG_STARTS_WITH_EOL = 0x02,
  PRG_STARTS_WITH_RUNE = 0x04,
  PRG_STARTS_WITH_CLASS = 0x08
};


struct re9_prog_s {
  uint8_t *code; /* vm code */
  uint32_t code_used;
  uint32_t code_alloted;
  uint32_t startinst; /* start pc */
#ifndef RE9_DISABLE_LEARNING
  uint8_t startflags; /* PRG_START_WITH_xxx */
  union {
    uint32_t startrange; /* offset of (vmop_class_t *) with starting range if PRG_STARTS_WITH_CLASS set or re9_rune if PRG_STARTS_WITH_RUNE set */
    re9_rune startrune;
  };
#endif
  int flags; /* RE9_FLAG_CASEINSENS, RE9_FLAG_NONGREEDY will be set if there were some non-greedy splits */
  int nsub;
};


/* note that CLASS opcode is variable-length */
typedef struct PACKED {
  uint32_t opcode:8; /* 0..126: literal char; 127: RUNE; 0xc0..0xff (0300..0377): opcodes */
  uint32_t next:24; /* offset of next opcode */
} vmopcode_t;


/* RUNE */
typedef struct PACKED {
  vmopcode_t opc;
  re9_rune r;
} vmop_rune_t;


/* SPLIT */
typedef struct PACKED {
  vmopcode_t opc;
  uint32_t alt; /* offset of 'alternate' opcode */
} vmop_split_t;


/* MARK */
typedef struct PACKED {
  vmopcode_t opc;
  uint8_t subid; /* bit 7 is RESERVED! 127 subgroups should be enough for everyone */
} vmop_mark_t;


/* CLASS */
typedef struct PACKED {
  vmopcode_t opc;
  uint16_t spi_count; /* number of items in spi */
  re9_rune spi[]; /* span data: spi_count*sizeof(spi[0]); sorted in ascending order */
} vmop_class_t;


/******************************************************************************/
/*
 * Actions and Tokens (re9_inst_t types)
 *
 *  02xx are operators, value == precedence
 *  03xx are tokens, i.e. operands for operators
 */
#define RUNE       0177  /* literal rune */

#define OPERATOR   0200  /* bitmask of all operators */
#define START      0200  /* start, used for marker on stack */
#define RBRA       0201  /* right bracket */
#define LBRA       0202  /* left bracket */
#define ALT        0203  /* alternation */
#define CAT        0204  /* concatentation, implicit operator */
#define STAR       0205  /* closure, *; bit 8 set: non-greedy */
#define PLUS       0206  /* a+ == aa*; bit 8 set: non-greedy */
#define QUEST      0207  /* a? == a|nothing, i.e. 0 or 1 a's; bit 8 set: non-greedy */

#define NOP        0300  /* no operation, internal use only (will be skipped by optimizer) */
#define ANY        0301  /* (and token); any character except newline */
#define ANYNL      0302  /* (and token); any character including newline */
#define BOL        0303  /* (and token); beginning of line */
#define EOL        0304  /* (and token); end of line */
#define CCLASS     0305  /* (and token); character class */
#define NCCLASS    0306  /* (and token); negated character class */
#define WBOUND     0307  /* word boundary assertion (generated by optimizer from rune) */
#define WNBOUND    0310  /* word non-boundary assertion (generated by optimizer from rune) */
#define SPLIT_G    0311  /* greedy split */
#define SPLIT_NG   0312  /* vmop; non-greedy split */
#define SMARK      0313  /* vmop; group start mark */
#define EMARK      0314  /* vmop; group end mark */
/* special splits for '*' -- should be ignored by learn_start() and replaced by optimize() */
#define STAR_G     0315
#define STAR_NG    0316
/* */
#define END        0377  /* vmop; terminate: match found */


/******************************************************************************/
static inline uint32_t vmop_size (const void *op) {
  switch (((const vmopcode_t *)op)->opcode) {
    case RUNE:
      return sizeof(vmop_rune_t);
    case SPLIT_G: case SPLIT_NG:
      return sizeof(vmop_split_t);
    case SMARK: case EMARK:
      return sizeof(vmop_mark_t);
    case CCLASS: case NCCLASS:
      return sizeof(vmop_class_t)+((const vmop_class_t *)op)->spi_count*sizeof(((const vmop_class_t *)op)->spi[0]);
    /*default: ;*/
  }
  return sizeof(vmopcode_t);
}


/******************************************************************************/
#if defined(RE9_DEBUG_PRG) || defined(RE9_DEBUG)
/* return 0 if pc is out of range or next opcode pc (NOT next pointer from vmopcode_t!) */
static void dump_char (FILE *fo, re9_rune r) {
  if (r >= 32 && r < 127 && r != '\'' && r != '\\') {
    fprintf(fo, "%c", r);
  } else {
    fprintf(fo, "\\u%04x", r);
  }
}

static uint32_t dump_opcode (FILE *fo, const re9_prog_t *pp, uint32_t pc) {
  const vmopcode_t *op;
  const vmop_class_t *opc;
  uint32_t f;
  if (pc >= pp->code_used) return 0;
  fprintf(fo, "%05u: 0%03o ", pc, pp->code[pc]);
  /* END */
  if (pp->code[pc] == END) {
    fprintf(fo, "      END\n");
    return pc+vmop_size((void *)(pp->code+pc));
  }
  if (pc+sizeof(vmopcode_t) > pp->code_used) {
    fprintf(fo, "???: INVALID CODE!\n");
    return 0;
  }
  op = (const vmopcode_t *)(pp->code+pc);
  if (pc+vmop_size(op) > pp->code_used) {
    fprintf(fo, "???: INVALID CODE!\n");
    return 0;
  }
  fprintf(fo, "%05u ", op->next);
  /* other */
  switch (op->opcode) {
    case NOP: fprintf(fo, "NOP\n"); break;
    case ANY: fprintf(fo, "ANY\n"); break;
    case ANYNL: fprintf(fo, "ANYNL\n"); break;
    case BOL: fprintf(fo, "BOL\n"); break;
    case EOL: fprintf(fo, "EOL\n"); break;
    case WBOUND: fprintf(fo, "WBOUND\n"); break;
    case WNBOUND: fprintf(fo, "WNBOUND\n"); break;
    case RUNE:
      fprintf(fo, "RUNE     '");
      dump_char(fo, ((const vmop_rune_t *)op)->r);
      fputs("'\n", fo);
      break;
    case CCLASS: case NCCLASS:
      opc = (const vmop_class_t *)op;
      fprintf(fo, "%-8s [", (op->opcode == CCLASS ? "CCLASS" : "NCCLASS"));
      for (f = 0; f < opc->spi_count; f += 2) {
        dump_char(fo, opc->spi[f]);
        if (opc->spi[f] != opc->spi[f+1]) {
          fputc('-', fo);
          dump_char(fo, opc->spi[f+1]);
        }
      }
      fputs("]\n", fo);
      break;
    case SPLIT_G: case SPLIT_NG:
      fprintf(fo, "%-8s %05u\n", (op->opcode == SPLIT_G ? "SPLIT_G" : "SPLIT_NG"), ((const vmop_split_t *)op)->alt);
      break;
    case STAR_G: case STAR_NG:
      fprintf(fo, "%-8s %05u\n", (op->opcode == SPLIT_G ? "STAR_G" : "STAR_NG"), ((const vmop_split_t *)op)->alt);
      break;
    case SMARK: case EMARK:
      fprintf(fo, "%-8s %u\n", (op->opcode == SMARK ? "SMARK" : "EMARK"), ((const vmop_mark_t *)op)->subid);
      break;
    default:
      if (op->opcode < RUNE) {
        fprintf(fo, "RUNE     '");
        dump_char(fo, op->opcode);
        fputs("'\n", fo);
        break;
      }
      fprintf(fo, "INVALID OPCODE!\n");
      return 0;
  }
  return pc+vmop_size(op);
}


static void dump (const re9_prog_t *pp) {
  uint32_t pc = 0;
  fprintf(stderr, "code size: %u\n", pp->code_used);
  while (pc < pp->code_used) if ((pc = dump_opcode(stderr, pp, pc)) == 0) break;
}
#endif


/******************************************************************************/
/* UTF-8 support */

#ifdef RE9_UNICODE_CASE

struct casemap {
  unsigned short code; /* code point */
  unsigned short lower; /* code */
  unsigned short upper; /* code */
};

#include "re9_unicode_mapping.c"


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

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


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


/*
 * returns the upper-case variant of the given unicode codepoint
 * does not support unicode code points > \uffff
 */
static inline re9_rune utf8_upper (re9_rune uc) {
  return (uc < 256 ? (uc < 128 ? toupper(uc) : uc) : utf8_map_case(uc, 1));
}


/*
 * returns the lower-case variant of the given unicode codepoint.
 * does not support unicode code points > \uffff
 */
/*
static inline int utf8_lower (int uc) {
  return (uc < 256 tolower(uc) : utf8_map_case(uc, 0));
}
*/
#define UPPER(_r)  utf8_upper(_r)

#else

#define UPPER(_r)  ((_r) < 128 ? toupper(_r) : (_r))

#endif


enum {
  RE9_UTF_MAX_BYTES = 4,     /* maximum bytes per rune */
  RE9_RUNE_SYNC  = 0x80,     /* cannot represent part of a UTF sequence (<) */
  RE9_RUNE_SELF  = 0x80,     /* rune and UTF sequences are the same (<) */
  RE9_RUNE_ERROR = 0xFFFD,   /* decoding error in UTF */
  RE9_RUNE_MAX   = 0x10FFFF, /* maximum rune value */
  /* */
  RE9_RUNE_SPEC_EOL = RE9_RUNE_MAX+1,
  RE9_RUNE_SPEC_NOTHING = RE9_RUNE_MAX+2,
  RE9_RUNE_SPEC_WBOUND = RE9_RUNE_MAX+3,
  RE9_RUNE_SPEC_WNBOUND = RE9_RUNE_MAX+4,
  RE9_RUNE_SPEC_BOL = RE9_RUNE_MAX+5,
  RE9_RUNE_SPEC_INVALID = RE9_RUNE_MAX+6
};


static const uint8_t utf8_clen[128] = {
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x00-0x0f */
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x10-0x1f */
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x20-0x2f */
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x30-0x3f */
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x40-0x4f */
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x50-0x5f */
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x60-0x6f */
0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, /* 0x70-0x7f */
0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, /* 0x80-0x8f */
0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, /* 0x90-0x9f */
0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, /* 0xa0-0xaf */
0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, /* 0xb0-0xbf */
0x22,0x22,0x22,0x22,0x22,0x22,0x22,0x22, /* 0xc0-0xcf c0-c1: overlong encoding: start of a 2-byte sequence, but code point <= 127 */
0x22,0x22,0x22,0x22,0x22,0x22,0x22,0x22, /* 0xd0-0xdf */
0x33,0x33,0x33,0x33,0x33,0x33,0x33,0x33, /* 0xe0-0xef */
0x44,0x44,0x44,0x44,0x00,0x00,0x00,0x00, /* 0xf0-0xff */
};


/* returns length */
static inline int re9_char2rune (re9_rune *rune, const char *str, const char *eol) {
  if ((intptr_t)(eol-str) > 0) {
    re9_rune r;
    uint8_t c = (unsigned char)(*str++), len = (utf8_clen[c>>1]>>((c&0x01)*4))&0x0f, res = len, oc = c;
    if (len == 0 || eol-str+1 < len) { *rune = RE9_RUNE_ERROR; return 1; }
    else if (len == 1) { *rune = c; return 1; }
    r = c&(0x7c>>len);
    while (--len > 0) {
      if (((c = (unsigned char)(*str++))&0xc0) != 0x80) { *rune = RE9_RUNE_ERROR; return 1; }
      r = (r<<6)|(c&0x3f);
    }
    if ((oc == 0xc0 || oc == 0xc1) && r != 0) r = RE9_RUNE_ERROR; /* overlong encoding: only 'modified utf-8' zero rune allowed here */
    if ((r >= 0xd800 && r <= 0xdfff) || // utf16/utf32 surrogates
        (r >= 0xfdd0 && r <= 0xfdef) || // just for fun
        (r >= 0xfffe && r <= 0xffff) || // fuck BOMs
        r > 0x10ffff) { r = RE9_RUNE_ERROR; /*res = 1;*/ } // bad unicode
    *rune = r;
    return res;
  } else {
    *rune = RE9_RUNE_SPEC_EOL;
    return 0;
  }
}


static inline const char *re8_rune_strchr (const char *s, re9_rune c, const char *eol) {
  if (s >= eol) return NULL;
  /* not part of utf sequence? */
  if (c < RE9_RUNE_SYNC) return memchr(s, c, eol-s);
  while (s < eol) {
    re9_rune r;
    int len = re9_char2rune(&r, s, eol);
    if (r == c) return s;
    s += len;
  }
  return NULL;
}


/******************************************************************************/
/* compiler */

enum {
  RE9_FALSE = 0,
  RE9_TRUE = 1
};


/* parser information */
typedef struct {
  /*re9_inst_t*/uint32_t first;
  /*re9_inst_t*/uint32_t last;
} re9_node_t;


#define NSTACK  (32)

/* compiler data */
typedef struct {
  re9_prog_t *pp;
  /* operand stack */
  re9_node_t andstack[NSTACK];
  re9_node_t *andp;
  /* operator stack */
  int atorstack[NSTACK];
  int *atorp;
  /* */
  int cursubid; /* id of current subexpression */
  int subidstack[NSTACK]; /* parallel to atorstack */
  int *subidp;
  /* */
  int last_was_operand; /* last token was operand */
  int nbra; /* number of opened parens */
  const char *expr; /* pointer to next character in source expression */
  const char *expr_eol;
  int flags; /* parser flags */
  /* */
  int comment_level; /* >0: in comment; counts parens */
  int return_rune_nothing; /* return 'nothing' rune from next lex()? will be reset by lex() */
  re9_rune yyrune; /* last lex'd rune */
  /* last lex'd class */
  re9_rune *yyclass;
  uint32_t yyc_used;
  uint32_t yyc_alloted;
  /* */
  jmp_buf regkaboom;
  const char *errormsg;
} re9_compiler_t;


/******************************************************************************/
static __attribute__((noreturn)) void rcerror (re9_compiler_t *ci, const char *s) {
  ci->errormsg = s;
  longjmp(ci->regkaboom, 1);
}


/******************************************************************************/
static void add_to_class (re9_compiler_t *ci, re9_rune r) {
  if (ci->comment_level == 0) {
    if (ci->yyc_used+1 > ci->yyc_alloted) {
      uint32_t newsz = ((ci->yyc_used+1)|0x1f)+1;
      re9_rune *newr = realloc(ci->yyclass, newsz*sizeof(ci->yyclass[0]));
      if (newr == NULL) rcerror(ci, "out of memory");
      ci->yyclass = newr;
      ci->yyc_alloted = newsz;
    }
    ci->yyclass[ci->yyc_used++] = r;
  }
}


static void add_to_class_two (re9_compiler_t *ci, re9_rune r0, re9_rune r1) {
  if (ci->comment_level == 0) {
    if (ci->yyc_used+2 > ci->yyc_alloted) {
      uint32_t newsz = ((ci->yyc_used+2)|0x1f)+1;
      re9_rune *newr = realloc(ci->yyclass, newsz*sizeof(ci->yyclass[0]));
      if (newr == NULL) rcerror(ci, "out of memory");
      ci->yyclass = newr;
      ci->yyc_alloted = newsz;
    }
    ci->yyclass[ci->yyc_used++] = r0;
    ci->yyclass[ci->yyc_used++] = r1;
  }
}


/******************************************************************************/
/* return 1 if char is quoted */
static int nextc (re9_compiler_t *ci, re9_rune *rp) {
  if (ci->expr >= ci->expr_eol) { *rp = RE9_RUNE_SPEC_EOL; return 1; }
  if ((ci->flags&RE9_FLAG_NONUTF8) == 0) {
    if (ci->expr[0] == '\\' && ci->expr+1 < ci->expr_eol) {
      ci->expr += re9_char2rune(rp, ci->expr+1, ci->expr_eol)+1;
      return 1;
    } else {
      ci->expr += re9_char2rune(rp, ci->expr, ci->expr_eol);
    }
  } else {
    if (ci->expr[0] == '\\' && ci->expr+1 < ci->expr_eol) {
      *rp = (unsigned char)(ci->expr[1]);
      ci->expr += 2;
      return 1;
    } else {
      *rp = (uint8_t)(*ci->expr++);
      if (ci->expr > ci->expr_eol) ci->expr = ci->expr_eol;
    }
  }
  if (ci->flags&RE9_FLAG_CASEINSENS) *rp = UPPER(*rp);
  return 0;
}


static void addmeta_space (re9_compiler_t *ci, int neg) {
  if (!neg) {
    add_to_class_two(ci, '\x9', '\xd');
    add_to_class_two(ci, ' ', ' ');
  } else {
    add_to_class_two(ci, '\1', '\x9'-1);
    add_to_class_two(ci, '\xd'+1, ' '-1);
    add_to_class_two(ci, ' '+1, RE9_RUNE_MAX);
  }
}


static void addmeta_digit (re9_compiler_t *ci, int neg) {
  if (!neg) {
    add_to_class_two(ci, '0', '9');
  } else {
    add_to_class_two(ci, '\1', '0'-1);
    add_to_class_two(ci, '9'+1, RE9_RUNE_MAX);
  }
}


static void addmeta_word (re9_compiler_t *ci, int neg) {
  if (!neg) {
    add_to_class_two(ci, '0', '9');
    add_to_class_two(ci, 'A', 'Z');
    add_to_class_two(ci, '_', '_');
    if ((ci->flags&RE9_FLAG_CASEINSENS) == 0) add_to_class_two(ci, 'a', 'z');
  } else {
    add_to_class_two(ci, '\0', '0'-1);
    add_to_class_two(ci, '9'+1, 'A'-1);
    add_to_class_two(ci, 'Z'+1, '_'-1);
    if ((ci->flags&RE9_FLAG_CASEINSENS) == 0) {
      add_to_class_two(ci, '_'+1, 'a'-1);
      add_to_class_two(ci, 'z'+1, RE9_RUNE_MAX);
    } else {
      add_to_class_two(ci, '_'+1, RE9_RUNE_MAX);
    }
  }
}


#ifndef RE9_DISABLE_POSIX_CLASSES
static void addmeta_upper (re9_compiler_t *ci) {
  add_to_class_two(ci, 'A', 'Z');
}


static void addmeta_lower (re9_compiler_t *ci) {
  if (ci->flags&RE9_FLAG_CASEINSENS) {
    add_to_class_two(ci, 'A', 'Z');
  } else {
    add_to_class_two(ci, 'a', 'z');
  }
}


static void addmeta_alpha (re9_compiler_t *ci) {
  add_to_class_two(ci, 'A', 'Z');
  if ((ci->flags&RE9_FLAG_CASEINSENS) == 0) add_to_class_two(ci, 'a', 'z');
}


static void addmeta_xdigit (re9_compiler_t *ci) {
  add_to_class_two(ci, '0', '9');
  add_to_class_two(ci, 'A', 'F');
  if ((ci->flags&RE9_FLAG_CASEINSENS) == 0) add_to_class_two(ci, 'a', 'f');
}


static void addmeta_punct (re9_compiler_t *ci) {
  add_to_class_two(ci, 33, 47); // !"#$%&'()*+,-./
  add_to_class_two(ci, 58, 64); // :;<=>?@
  add_to_class_two(ci, 91, 96); // [\]^_`
  add_to_class_two(ci, 123, 126); // {|}~
}


/*FIXME:??? this should include '\z'! */
static void addmeta_ascii (re9_compiler_t *ci) {
  add_to_class_two(ci, '\1', '\x7f');
}


static void addmeta_blank (re9_compiler_t *ci) {
  add_to_class_two(ci, '\t', '\t');
  add_to_class_two(ci, ' ', ' ');
}


/*FIXME:??? this should include '\z'! */
static void addmeta_ctrl (re9_compiler_t *ci) {
  add_to_class_two(ci, '\1', '\x1f');
  add_to_class_two(ci, '\x7f', '\x7f');
}


static void addmeta_graph (re9_compiler_t *ci) {
  add_to_class_two(ci, '!', '\x7e');
}


static void addmeta_print (re9_compiler_t *ci) {
  add_to_class_two(ci, ' ', '\x7e');
}
#endif


static void normalize_spans (re9_compiler_t *ci) {
  if (ci->yyc_used > 2) {
    /* we have at least two spans */
    uint32_t cp;
    re9_rune *ep = ci->yyclass+ci->yyc_used;
    re9_rune *p, *np;
    /* sort on span start */
    /* yeah, old good bubble sorting */
    for (p = ci->yyclass; p < ep; p += 2) {
      for (np = p; np < ep; np += 2) {
        if (*np < *p) {
          re9_rune rune;
          rune = np[0];
          np[0] = p[0];
          p[0] = rune;
          rune = np[1];
          np[1] = p[1];
          p[1] = rune;
        }
      }
    }
    /* merge spans */
    for (cp = 2; cp < ci->yyc_used; ) {
      uint32_t f;
      /* if next span start is inside previous span, merge both spans */
      //fprintf(stderr, "prev:(%u,%u); curr:(%u,%u)\n", ci->yyclass[cp-2], ci->yyclass[cp-1], ci->yyclass[cp], ci->yyclass[cp+1]);
      if (ci->yyclass[cp] <= ci->yyclass[cp-1]) {
        /* inside, merge */
        if (ci->yyclass[cp+1] > ci->yyclass[cp-1]) ci->yyclass[cp-1] = ci->yyclass[cp+1];
        /* remove this span */
        for (f = cp+2; f < ci->yyc_used; ++f) ci->yyclass[f-2] = ci->yyclass[f];
        ci->yyc_used -= 2;
      } else if (ci->yyclass[cp-1]+1 == ci->yyclass[cp]) {
        /* we can join this spans */
        ci->yyclass[cp-1] = ci->yyclass[cp+1];
        /* remove this span */
        for (f = cp+2; f < ci->yyc_used; ++f) ci->yyclass[f-2] = ci->yyclass[f];
        ci->yyc_used -= 2;
      } else {
        /* outside, skip */
        cp += 2;
      }
    }
  }
}


/* parse character range */
static int bldcclass (re9_compiler_t *ci) {
  int type;
  re9_rune rune;
  int quoted;
  /* we have already seen the '[' */
  type = CCLASS;
  ci->yyc_used = 0;
  /* look ahead for negation */
  /* SPECIAL CASE!!! negated classes don't match \n */
  quoted = nextc(ci, &rune);
  if (!quoted && rune == '^') {
    type = NCCLASS;
    quoted = nextc(ci, &rune);
    add_to_class_two(ci, '\n', '\n');
  }
  /* parse class into a set of spans */
  for (;; quoted = nextc(ci, &rune)) {
    if (rune == RE9_RUNE_SPEC_EOL) rcerror(ci, "malformed '[]'");
    if (!quoted && rune == ']' && (ci->yyc_used&0x01) == 0) break;
    if (quoted && ((rune >= '0' && rune <= '9') || (rune >= 'a' && rune <= 'z') || (rune >= 'A' && rune <= 'Z'))) {
      /* metacharacters */
      if ((ci->yyc_used&0x01) != 0 || (ci->expr < ci->expr_eol && ci->expr[0] == '-')) rcerror(ci, "malformed '[]'"); /* metacharacter can't be used in rangedef */
      switch (rune) {
        case 'd': case 'D': addmeta_digit(ci, (rune <= 'Z')); break;
        case 's': case 'S': addmeta_space(ci, (rune <= 'Z')); break;
        case 'w': case 'W': addmeta_word(ci, (rune <= 'Z')); break;
        case 'z': add_to_class_two(ci, '\0', '\0'); break;
        case 'Z': add_to_class_two(ci, '\1', RE9_RUNE_MAX); break;
        default:
          rcerror(ci, "invalid metacharacter in '[]'");
          break;
      }
#ifndef RE9_DISABLE_POSIX_CLASSES
    } else if ((ci->yyc_used&0x01) == 0 && !quoted && rune == '[' && ci->expr+6 < ci->expr_eol && ci->expr[0] == ':') {
      if (ci->expr+7 < ci->expr_eol) {
             if (strncmp(ci->expr, ":alnum:]", 8) == 0) { ci->expr += 8; addmeta_alpha(ci); addmeta_digit(ci, 0); }
        else if (strncmp(ci->expr, ":alpha:]", 8) == 0) { ci->expr += 8; addmeta_alpha(ci); }
        else if (strncmp(ci->expr, ":ascii:]", 8) == 0) { ci->expr += 8; addmeta_ascii(ci); }
        else if (strncmp(ci->expr, ":blank:]", 8) == 0) { ci->expr += 8; addmeta_blank(ci); }
        else if (strncmp(ci->expr, ":cntrl:]", 8) == 0) { ci->expr += 8; addmeta_ctrl(ci); }
        else if (strncmp(ci->expr, ":digit:]", 8) == 0) { ci->expr += 8; addmeta_digit(ci, 0); }
        else if (strncmp(ci->expr, ":graph:]", 8) == 0) { ci->expr += 8; addmeta_graph(ci); }
        else if (strncmp(ci->expr, ":lower:]", 8) == 0) { ci->expr += 8; addmeta_lower(ci); }
        else if (strncmp(ci->expr, ":print:]", 8) == 0) { ci->expr += 8; addmeta_print(ci); }
        else if (strncmp(ci->expr, ":punct:]", 8) == 0) { ci->expr += 8; addmeta_punct(ci); }
        else if (strncmp(ci->expr, ":space:]", 8) == 0) { ci->expr += 8; addmeta_space(ci, 0); }
        else if (strncmp(ci->expr, ":upper:]", 8) == 0) { ci->expr += 8; addmeta_upper(ci); }
      } else if (strncmp(ci->expr, ":word:]", 7) == 0) { ci->expr += 7; addmeta_word(ci, 0); }
      else if (ci->expr+8 < ci->expr_eol && strncmp(ci->expr, ":xdigit:]", 9) == 0) { ci->expr += 9; addmeta_xdigit(ci); }
#endif
    } else {
      if (ci->yyc_used&0x01 && rune < ci->yyclass[ci->yyc_used-1]) rcerror(ci, "invalid range in '[]'");
      add_to_class(ci, rune);
      if (ci->yyc_used&0x01) {
        /* this was first char of possible range */
        if (ci->expr < ci->expr_eol && ci->expr[0] == '-') {
          /* rangedef; skip '-' */
          ++ci->expr;
        } else {
          /* one char: convert it to range */
          add_to_class(ci, rune);
        }
      }
    }
  }
  /* sort and store only if we are not in comment */
  if (ci->comment_level == 0) {
    if (ci->yyc_used&0x01) rcerror(ci, "THE THING THAT SHOULD NOT BE: character class parsing error");
    if (ci->yyc_used == 0) rcerror(ci, "empty '[]'");
    normalize_spans(ci);
    /* if we have only one char in range, we can use RUNE instead */
    if (type == CCLASS && ci->yyc_used == 2 && ci->yyclass[0] == ci->yyclass[1]) {
      /* yeah, one char! */
      ci->yyrune = ci->yyclass[0];
      return RUNE;
    }
  }
  return type;
}


/* parse metacharacter */
static int bldmeta (re9_compiler_t *ci, re9_rune rune) {
  int rangeop = (rune >= 'a' && rune <= 'z' ? CCLASS : NCCLASS);
  ci->yyc_used = 0;
  switch (rune) {
    case 'd': case 'D': addmeta_digit(ci, 0); break;
    case 's': case 'S': addmeta_space(ci, 0); break;
    case 'w': case 'W': addmeta_word(ci, 0); break;
    case 'Z': add_to_class_two(ci, '\0', '\0'); break;
    case 'z': ci->yyrune = 0; return RUNE;
    case 'b': ci->yyrune = RE9_RUNE_SPEC_WBOUND; return RUNE;
    case 'B': ci->yyrune = RE9_RUNE_SPEC_WNBOUND; return RUNE;
    default: rcerror(ci, "invalid metacharacter");
  }
  return rangeop;
}


/* get token */
static int lex (re9_compiler_t *ci) {
  if (ci->return_rune_nothing) {
    ci->return_rune_nothing = 0;
    ci->yyrune = RE9_RUNE_SPEC_NOTHING;
  } else if (ci->expr >= ci->expr_eol) {
    ci->yyrune = RE9_RUNE_SPEC_EOL;
  } else if (ci->flags&RE9_FLAG_LITERAL) {
    if (ci->expr < ci->expr_eol && ci->expr[0] == '\\') {
      ++ci->expr;
      ci->yyrune = '\\';
    } else {
      /* can't be quoted */
      nextc(ci, &ci->yyrune);
    }
  } else {
    int quoted = nextc(ci, &ci->yyrune);
    if (quoted) {
      /* check for metacharacter */
      if ((ci->yyrune >= '0' && ci->yyrune <= '9') || (ci->yyrune >= 'a' && ci->yyrune <= 'z') || (ci->yyrune >= 'A' && ci->yyrune <= 'Z')) return bldmeta(ci, ci->yyrune);
    } else {
      switch (ci->yyrune) {
        case '*': quoted = STAR; goto closure;
        case '?': quoted = QUEST; goto closure;
        case '+': quoted = PLUS; /* fallthru */
closure:  if (ci->expr < ci->expr_eol && ci->expr[0] == '?') {
#ifndef RE9_DISABLE_NONGREEDY
            ++ci->expr;
            quoted |= 0x100;
#else
            if ((ci->flags&RE9_FLAG_NONGREEDY) == 0) rcerror(ci, "non-greedy closure support was disabled at compile time");
#endif
          }
          return quoted;
        case '|': return ALT;
        case '.': return (ci->flags&RE9_FLAG_ANYDOT ? ANYNL : ANY);
        case '(': return LBRA;
        case ')': return RBRA;
        case '^': return BOL;
        case '$': return EOL;
        case '[': return bldcclass(ci);
      }
    }
  }
  return (ci->yyrune != RE9_RUNE_SPEC_EOL ? RUNE : END);
}


/******************************************************************************/
static inline uint32_t instofs (const re9_compiler_t *ci, const vmopcode_t *op) {
  return (int32_t)(((const uint8_t *)op)-ci->pp->code);
}


static inline vmopcode_t *instptr (re9_compiler_t *ci, uint32_t ofs) {
  return (vmopcode_t *)(ci->pp->code+ofs);
}


/* push instructions to 'operand stack' */
static void push_operand (re9_compiler_t *ci, vmopcode_t *f, vmopcode_t *l) {
  if (ci->andp >= &ci->andstack[NSTACK]) rcerror(ci, "THE THING THAT SHOULD NOT BE: operand stack overflow");
  ci->andp->first = instofs(ci, f);
  ci->andp->last = instofs(ci, l);
  ++ci->andp;
}


/* push token and group id to 'operator stack' */
static void push_operator (re9_compiler_t *ci, int t, int csi) {
  if (ci->atorp >= &ci->atorstack[NSTACK]) rcerror(ci, "THE THING THAT SHOULD NOT BE: operator stack overflow");
  *ci->atorp++ = t;
  *ci->subidp++ = csi;
}


/* pop instriction from 'operand stack' */
static re9_node_t *pop_operand (re9_compiler_t *ci) {
  if (ci->andp <= &ci->andstack[0]) rcerror(ci, "missing operand");
  return --ci->andp;
}


/* pop token from 'operator stack' */
static int pop_operator (re9_compiler_t *ci) {
  if (ci->atorp <= &ci->atorstack[0]) rcerror(ci, "THE THING THAT SHOULD NOT BE: operator stack underflow");
  --ci->subidp;
  return *--ci->atorp;
}


/******************************************************************************/
static void *allot (re9_compiler_t *ci, size_t size) {
  void *res;
  if (ci->pp->code_used+size > ci->pp->code_alloted) {
    uint32_t newsz = ((ci->pp->code_used+size)|0xfff)+1;
    uint8_t *newc = realloc(ci->pp->code, newsz);
    if (newc == NULL) rcerror(ci, "out of memory");
    memset(newc+ci->pp->code_used, 0, newsz-ci->pp->code_used);
    ci->pp->code = newc;
    ci->pp->code_alloted = newsz;
  }
  res = ci->pp->code+ci->pp->code_used;
  ci->pp->code_used += size;
  return res;
}


/* allocate new instruction */
static inline vmopcode_t *newinst (re9_compiler_t *ci, int t) {
  vmopcode_t *op = allot(ci, sizeof(*op));
  op->opcode = t;
  return op;
}


static vmopcode_t *newinst_class (re9_compiler_t *ci, int t) {
  vmop_class_t *op = allot(ci, sizeof(*op)+ci->yyc_used*sizeof(op->spi[0]));
  op->opc.opcode = t;
  if (ci->yyc_used > 0) memcpy(op->spi, ci->yyclass, ci->yyc_used*sizeof(op->spi[0]));
  op->spi_count = ci->yyc_used;
  if (ci->yyc_used&0x01) rcerror(ci, "THE THING THAT SHOULD NOT BE: newinst_class() fucked!");
  return (vmopcode_t *)op;
}


static vmopcode_t *newinst_rune (re9_compiler_t *ci, re9_rune r) {
  if (r < RUNE || r > RE9_RUNE_MAX) {
    vmopcode_t *op = allot(ci, sizeof(*op));
    switch (r) {
      case RE9_RUNE_SPEC_NOTHING: op->opcode = NOP; break;
      case RE9_RUNE_SPEC_WBOUND: op->opcode = WBOUND; break;
      case RE9_RUNE_SPEC_WNBOUND: op->opcode = WNBOUND; break;
      default:
        if (r < RUNE) {
          op->opcode = r;
          break;
        }
        rcerror(ci, "THE THING THAT SHOULD NOT BE: newinst_rune() fucked!");
    }
    return op;
  } else {
    vmop_rune_t *op = allot(ci, sizeof(*op));
    op->opc.opcode = RUNE;
    op->r = r;
    return (vmopcode_t *)op;
  }
}


static vmopcode_t *newinst_mark (re9_compiler_t *ci, int t, int id) {
  if (id >= 0) {
    vmop_mark_t *op = allot(ci, sizeof(*op));
    if (id > 127) rcerror(ci, "too many captures");
    op->opc.opcode = t;
    op->subid = id;
    return (vmopcode_t *)op;
  } else {
    vmopcode_t *op = allot(ci, sizeof(*op));
    op->opcode = NOP;
    return op;
  }
}


static inline vmop_split_t *newinst_split (re9_compiler_t *ci, int t) {
  vmop_split_t *op = allot(ci, sizeof(*op));
#ifndef RE9_DISABLE_NONGREEDY
  op->opc.opcode = ((ci->flags&RE9_FLAG_NONGREEDY) == 0 ? (t&0x100 ? SPLIT_NG : SPLIT_G) : (t&0x100 ? SPLIT_G : SPLIT_NG));
  if ((t&0xff) == STAR) op->opc.opcode = (op->opc.opcode == SPLIT_G ? STAR_G : STAR_NG);
#else
  op->opc.opcode = ((t&0xff) == STAR ? STAR_G : SPLIT_G);
#endif
  return op;
}


static inline vmop_split_t *newinst_split1 (re9_compiler_t *ci, int t) {
  vmop_split_t *op = allot(ci, sizeof(*op));
  op->opc.opcode = t;
  return op;
}


/* process instructions with higher current priority levels */
static void evaluntil (re9_compiler_t *ci, int pri) {
  while (pri == RBRA || (ci->atorp[-1]&0xff) >= (pri&0xff)) {
    re9_node_t *op1, *op2;
    vmopcode_t *inst1, *inst2;
    vmop_split_t *si1;
    int op = pop_operator(ci);
    switch (op) {
      case LBRA: /* must have been RBRA */
        op1 = pop_operand(ci);
        inst2 = newinst_mark(ci, EMARK, *ci->subidp);
        instptr(ci, op1->last)->next = instofs(ci, inst2);
        inst1 = newinst_mark(ci, SMARK, *ci->subidp);
        inst1->next = op1->first;
        push_operand(ci, inst1, inst2);
        return;
      case ALT:
        op2 = pop_operand(ci);
        op1 = pop_operand(ci);
        inst2 = newinst(ci, NOP);
        instptr(ci, op2->last)->next = instptr(ci, op1->last)->next = instofs(ci, inst2);
        si1 = newinst_split1(ci, SPLIT_G);
        si1->alt = op1->first;
        si1->opc.next = op2->first;
        push_operand(ci, (void *)si1, inst2);
        break;
      case CAT:
        op2 = pop_operand(ci);
        op1 = pop_operand(ci);
        instptr(ci, op1->last)->next = op2->first;
        push_operand(ci, instptr(ci, op1->first), instptr(ci, op2->last));
        break;
      case STAR: case STAR|0x100: /* greedy and non-greedy */
        op2 = pop_operand(ci);
        si1 = newinst_split(ci, op);
        instptr(ci, op2->last)->next = instofs(ci, (void *)si1);
        si1->alt = op2->first;
        push_operand(ci, (void *)si1, (void *)si1);
        break;
      case PLUS: case PLUS|0x100: /* greedy and non-greedy */
        op2 = pop_operand(ci);
        si1 = newinst_split(ci, op);
        instptr(ci, op2->last)->next = instofs(ci, (void *)si1);
        si1->alt = op2->first;
        push_operand(ci, instptr(ci, op2->first), (void *)si1);
        break;
      case QUEST: case QUEST|0x100: /* greedy and non-greedy */
        op2 = pop_operand(ci);
        si1 = newinst_split(ci, op);
        inst2 = newinst(ci, NOP);
        si1->opc.next = instofs(ci, inst2);
        si1->alt = op2->first;
        instptr(ci, op2->last)->next = instofs(ci, inst2);
        push_operand(ci, (void *)si1, inst2);
        break;
      default:
        rcerror(ci, "unknown operator in evaluntil");
        break;
    }
  }
}


/******************************************************************************/
/* process operator */
static void operator (re9_compiler_t *ci, int t) {
  int csi = ci->cursubid;
  if (ci->comment_level) {
    /* in comment */
    if (t == RBRA || t == LBRA) {
      ci->nbra += (t == LBRA ? 1 : -1);
      ci->comment_level += (t == LBRA ? 1 : -1);
    }
  } else {
    /* not in comment */
    if (t == RBRA && --ci->nbra < 0) rcerror(ci, "unmatched right paren");
    if (t == LBRA) {
      ++ci->nbra;
      csi = -1;
      if (ci->expr < ci->expr_eol && ci->expr[0] == '?') {
        if (ci->expr+1 < ci->expr_eol && ci->expr[1] == ':') {
          ci->expr += 2;
        } else if (ci->expr+1 < ci->expr_eol && ci->expr[1] == '#') {
          ci->expr += 2;
          ci->comment_level = 1;
          ci->last_was_operand = RE9_TRUE;
          return;
        } else {
          rcerror(ci, "invalid paren flags");
        }
      } else {
        if ((csi = ++ci->cursubid) >= RE9_SUBEXP_MAX) rcerror(ci, "too many subexpressions");
        ci->pp->nsub = csi;
      }
      if (ci->last_was_operand) operator(ci, CAT);
      /* process empty parens */
      if (ci->expr < ci->expr_eol && ci->expr[0] == ')') ci->return_rune_nothing = 1; /* hack: next lex() will return 'nothing' rune */
    } else {
      evaluntil(ci, t);
    }
    if (t != RBRA) push_operator(ci, t, csi);
  }
  switch (t&0xff) {
    case STAR: case QUEST: case PLUS: case RBRA:
      ci->last_was_operand = RE9_TRUE; /* these look like operands */
      break;
    default:
      ci->last_was_operand = RE9_FALSE;
      break;
  }
}


/* process operand: rune or character class */
static void operand (re9_compiler_t *ci, int t) {
  if (ci->comment_level == 0) {
    vmopcode_t *i;
    if (ci->last_was_operand) operator(ci, CAT); /* concatenate is implicit */
    switch (t) {
      case CCLASS: case NCCLASS:
        i = newinst_class(ci, t);
        break;
      case RUNE:
        i = newinst_rune(ci, ci->yyrune);
        break;
      default:
        i = newinst(ci, t);
        break;
    }
    push_operand(ci, i, i);
  }
  ci->last_was_operand = RE9_TRUE;
}


#ifndef RE9_DISABLE_LEARNING
/* trace VM code and build 'starting range' */
/* return !0 if we hit 'ANY*' */
static int learn_start_tracer (re9_compiler_t *ci, uint32_t pc) {
  for (;;) {
    uint8_t opcode = ci->pp->code[pc];
    const vmop_class_t *opc;
    re9_rune pr;
    uint32_t f;
    if (opcode < RUNE) {
      /* wow, a solid hit */
      add_to_class_two(ci, opcode, opcode);
      return 0;
    }
    switch (opcode) {
      case RUNE: /* another solid hit */
        add_to_class_two(ci, ((const vmop_rune_t *)(ci->pp->code+pc))->r, ((const vmop_rune_t *)(ci->pp->code+pc))->r);
        return 0;
      case ANY: case ANYNL: /* shit... */
        ci->yyc_used = 0;
        add_to_class_two(ci, 0, RE9_RUNE_MAX);
        return 1;
      case SPLIT_G: case SPLIT_NG: /* choose your way to die */
      case STAR_G: case STAR_NG: /* i can do better analyzis here, but i don't care for now */
        if (learn_start_tracer(ci, ((const vmop_split_t *)(ci->pp->code+pc))->alt)) return 1; /* no way to go */
        break;
      case BOL:
        ci->pp->startflags |= PRG_STARTS_WITH_BOL;
        return 0;
      case EOL:
        ci->pp->startflags |= PRG_STARTS_WITH_EOL;
        return 0;
      case CCLASS:
        opc = ((const vmop_class_t *)(ci->pp->code+pc));
        for (f = 0; f < opc->spi_count; ++f) add_to_class(ci, opc->spi[f]);
        return 0;
      case NCCLASS:
        /* oh, this is harder than previous one */
        /* we realy on the fact that range was sorted and there are gaps between ranges */
        opc = ((const vmop_class_t *)(ci->pp->code+pc));
        if (opc->spi[0] > 0) add_to_class_two(ci, 0, opc->spi[0]-1);
        pr = opc->spi[1]+1;
        for (f = 2; f < opc->spi_count && pr <= RE9_RUNE_MAX; f += 2) {
          add_to_class_two(ci, pr, opc->spi[f]-1);
          pr = opc->spi[f+1]+1;
        }
        if (pr <= RE9_RUNE_MAX) add_to_class_two(ci, pr, RE9_RUNE_MAX);
        return 0;
      case END:
        /*return 0;*/
        ci->yyc_used = 0;
        add_to_class_two(ci, 0, RE9_RUNE_MAX);
        return 1;
      /* ignore all other shit */
    }
    pc = instptr(ci, pc)->next;
  }
}


static void learn_start (re9_compiler_t *ci) {
  int any;
  ci->yyc_used = 0;
  ci->pp->startflags = 0;
  ci->pp->startrange = 0;
  ci->pp->startrune = 0;
  any = learn_start_tracer(ci, ci->pp->startinst);
  if (any || ci->yyc_used == 0) {
    ci->pp->startflags = PRG_STARTS_WITH_ANY;
    //fprintf(stderr, "PRG_STARTS_WITH_ANY\n");
  } else {
    /* generate CCLASS */
    normalize_spans(ci);
    if (ci->yyc_used == 2 && ci->yyclass[0] == ci->yyclass[1]) {
      /* simple RUNE will be enough */
      ci->pp->startflags |= PRG_STARTS_WITH_RUNE;
      ci->pp->startrune = ci->yyclass[0];
      //fprintf(stderr, "PRG_STARTS_WITH_RUNE: %u\n", ci->pp->startrune);
    } else {
      ci->pp->startflags |= PRG_STARTS_WITH_CLASS;
      ci->pp->startrange = instofs(ci, newinst_class(ci, CCLASS));
      //fprintf(stderr, "PRG_STARTS_WITH_CLASS\n ");
#ifdef RE9_DEBUG_PRG
      //dump_opcode(stderr, ci->pp, ci->pp->startrange);
#endif
    }
  }
}
#endif


/*TODO:??? collapse some things, get rid of nops? */
static void optimize (re9_compiler_t *ci) {
  re9_prog_t *pp = ci->pp;
  uint32_t pc;
  /* */
#ifndef RE9_DISABLE_LEARNING
  learn_start(ci);
#endif
  /* get rid of NOOP chains */
  for (pc = 0; pc < pp->code_used; pc += vmop_size(pp->code+pc)) {
    vmopcode_t *inst = instptr(ci, pc), *target;
    target = instptr(ci, inst->next);
    while (target->opcode == NOP) target = instptr(ci, target->next);
    if (inst->opcode == STAR_G) inst->opcode = SPLIT_G;
    else if (inst->opcode == STAR_NG) inst->opcode = SPLIT_NG;
    inst->next = instofs(ci, target);
    if (inst->opcode == SPLIT_NG || inst->opcode == SPLIT_G) {
      vmop_split_t *op = (vmop_split_t *)inst;
      target = instptr(ci, op->alt);
      while (target->opcode == NOP) target = instptr(ci, target->next);
      op->alt = instofs(ci, target);
      if (inst->opcode == SPLIT_NG) ci->pp->flags |= RE9_FLAG_NONGREEDY;
    }
  }
  /* move startinst on non-NOOP */
  while (instptr(ci, pp->startinst)->opcode == NOP) pp->startinst = instptr(ci, pp->startinst)->next;
  /* shrink code area */
  if (pc > pp->code_alloted) {
    uint8_t *newc;
    pp->code_used = pp->code_alloted = pc;
    newc = realloc(pp->code, pc);
    if (newc != NULL) pp->code = newc;
  }
}


re9_prog_t *re9_compile_ex (const char *s, const char *eol, int flags, const char **errmsg) {
  int token;
  re9_compiler_t * volatile ci;
  re9_prog_t *pres;
  if (s == NULL) {
    if (errmsg != NULL) *errmsg = "can't parse NULL regexp";
    return NULL;
  }
  if (eol == NULL) eol = s+strlen(s); else if (eol < s) eol = s;
  if ((ci = malloc(sizeof(*ci))) == NULL) {
    if (errmsg != NULL) *errmsg = "out of memory";
    return NULL;
  }
  memset(ci, 0, sizeof(*ci));
  /* get memory for the program */
  ci->pp = malloc(sizeof(*ci->pp));
  if (ci->pp == NULL) {
    free(ci);
    if (errmsg != NULL) *errmsg = "out of memory";
    return NULL;
  }
  memset(ci->pp, 0, sizeof(*ci->pp));
  //ci->pp->nsub = 0;
  ci->pp->flags = (flags&RE9_FLAG_CASEINSENS);
  /* */
  ci->flags = flags;
  if (errmsg != NULL) *errmsg = NULL;
  if (setjmp(ci->regkaboom)) {
    if (errmsg != NULL) *errmsg = ci->errormsg;
    if (ci->yyclass != NULL) free(ci->yyclass);
    if (ci->pp->code != NULL) free(ci->pp->code);
    free(ci->pp);
    free(ci);
    return NULL;
  }
  /* go compile the sucker */
  ci->expr = s;
  ci->expr_eol = eol;
  ci->nbra = 0;
  ci->atorp = ci->atorstack;
  ci->andp = ci->andstack;
  ci->subidp = ci->subidstack;
  ci->last_was_operand = RE9_FALSE;
  ci->cursubid = 0;
  /* start with a low priority operator to prime parser */
  push_operator(ci, START-1, ci->cursubid);
  /* offset 0 should be NOOP */
  newinst(ci, NOP)->next = ci->pp->code_used;
  while ((token = lex(ci)) != END) {
    if ((token&0300) == OPERATOR) operator(ci, token); else operand(ci, token);
  }
  if (ci->comment_level == 0) {
    /* close with a low priority operator */
    evaluntil(ci, START);
    /* force END */
    operand(ci, END);
    evaluntil(ci, START);
  }
#ifdef RE9_DEBUG_PRG
  //if (ci->flags&RE9_FLAG_DUMPPRG) dumpstack(ci);
#endif
  if (ci->nbra) rcerror(ci, "unmatched left paren");
  --ci->andp; /* points to first and only operand */
  ci->pp->startinst = ci->andp->first;
#ifdef RE9_DEBUG_PRG
  if (ci->flags&RE9_FLAG_DUMPPRG) {
    fprintf(stderr, "=== unoptimized ===\n");
    fprintf(stderr, "start: %u\n", ci->pp->startinst);
    dump(ci->pp);
  }
#endif
  optimize(ci);
#ifdef RE9_DEBUG_PRG
  if (ci->flags&RE9_FLAG_DUMPPRG) {
    fprintf(stderr, "=== optimized ===\n");
    fprintf(stderr, "start: %u\n", ci->pp->startinst);
    dump(ci->pp);
    fprintf(stderr, "------\n");
  }
#endif
  pres = ci->pp;
  if (ci->yyclass != NULL) free(ci->yyclass);
  free(ci);
  ++pres->nsub;
  return pres;
}


re9_prog_t *re9_compile (const char *s, int flags, const char **errmsg) {
  return re9_compile_ex(s, NULL, flags, errmsg);
}


int re9_nsub (const re9_prog_t *p) {
  return (p != NULL ? p->nsub : 0);
}


void re9_free (re9_prog_t *p) {
  if (p != NULL) {
    if (p->code != NULL) free(p->code);
    free(p);
  }
}


/******************************************************************************/
/* executor */
#define LASTINST  (0)


/* substitution list */
typedef struct {
  re9_sub_t m[RE9_SUBEXP_MAX];
} re9_sublist_t;


/*
 *  regexec execution lists
 */
#define LISTSIZE     (16)
#define BIGLISTSIZE  (64*LISTSIZE)

typedef struct {
  uint32_t inst; /* instruction of the thread */
  re9_sublist_t se; /* matched subexpressions in this thread */
} re9_listitem_t;


typedef struct {
  re9_listitem_t *start;
  re9_listitem_t *free;
  re9_listitem_t *end;
} re9_list_t;


typedef struct {
  re9_listitem_t *relist[2], *relistf[2];
  int listsize;
  const char *bol;
  const char *eol;
  int flags;
} re9_ljunk_t;


/* save a new match in mp */
static inline void re9l_newmatch (re9_sub_t *mp, int ms, re9_sublist_t *sp) {
  if (mp == NULL || ms <= 0) return;
  if (mp[0].sp == NULL || sp->m[0].sp < mp[0].sp || (sp->m[0].sp == mp[0].sp && sp->m[0].ep > mp[0].ep)) {
    int i;
    for (i = 0; i < ms && i < RE9_SUBEXP_MAX; ++i) mp[i] = sp->m[i];
    for (; i < ms; ++i) mp[i].sp = mp[i].ep = 0;
  }
}


/*
 * Note optimization in re9l_newthread:
 *  *lp must be pending when re9l_newthread called; if *lp has been looked at already, the optimization is a bug
 */
/*
 * lp: list to add to
 * ip: instruction to add
 * ms: number of elements at mp
 * sep: pointers to subexpressions
 */
static inline re9_listitem_t *re9l_newthread (re9_list_t *lp, uint32_t ip, int ms, re9_sublist_t *sep, int nocheck) {
  re9_listitem_t *p;
  if (!nocheck) {
    for (p = lp->start; p->inst != LASTINST; ++p) {
      if (p->inst == ip) {
        dlogf("newthread:%p; found at %u; sep->m[0].sp=%p; p->se.m[0].sp=%p\n", lp, p-lp->start, sep->m[0].sp, p->se.m[0].sp);
        if (sep->m[0].sp < p->se.m[0].sp) {
          if (ms > 1) p->se = *sep; else p->se.m[0] = sep->m[0];
        }
        return p;
      }
    }
  }
  p = lp->free++;
  if (p >= lp->end-1) return NULL;
  dlogf("newthread:%p; new at %u(%u)\n", lp->start, p-lp->start, ip);
  p->inst = ip;
  if (ms > 1) p->se = *sep; else p->se.m[0] = sep->m[0];
  p[1].inst = LASTINST;
  return p;
}


/*
 * same as renewthread, but called with initial empty start pointer
 */
/*
 * lp: list to add to
 * ip: instruction to add
 * ms: number of elements at mp
 * sp: pointers to subexpressions
 */
static inline re9_listitem_t *re9l_newemptythread (re9_list_t *lp, uint32_t ip, int ms, const char *sp, int nocheck) {
  re9_listitem_t *p;
  if (!nocheck) {
    for (p = lp->start; p->inst != LASTINST; ++p) {
      if (p->inst == ip) {
        dlogf("newemptythread:%p; found at %u; sp=%p; p->se.m[0].sp=%p\n", lp, p-lp->start, sp, p->se.m[0].sp);
        if (sp < p->se.m[0].sp) {
          if (ms > 1) memset(&p->se, 0, sizeof(p->se));
          p->se.m[0].sp = sp;
        }
        return p;
      }
    }
  }
  p = lp->free++;
  if (p >= lp->end-1) return NULL;
  dlogf("newemptythread:%p; new at %u(%u)\n", lp->start, p-lp->start, ip);
  p->inst = ip;
  if (ms > 1) memset(&p->se, 0, sizeof(p->se));
  p->se.m[0].sp = sp;
  p[1].inst = LASTINST;
  return p;
}


static inline int is_word_rune (re9_rune r) {
  return
    (r >= '0' && r <= '9') ||
    (r >= 'A' && r <= 'Z') ||
    (r >= 'a' && r <= 'z') ||
    (r >= 128 && r <= RE9_RUNE_MAX) ||
    r == '_';
}


/*
 *  return  0 if no match
 *    >0 if a match
 *    <0 if we ran out of list space
 */
/*
 * progp: program to run
 * bol: string to run machine on
 * mp: subexpression elements
 * ms: number of elements at mp
 * j
 */
static int regexec1 (const re9_prog_t *progp, re9_sub_t *mp, int ms, re9_ljunk_t *j) {
  int flag = 0;
#ifdef RE9_CALC_MAXT
  int maxt = 0;
#endif
  const char *s;
#ifndef RE9_DISABLE_LEARNING
  const char *p;
  int checkstart;
#endif
  re9_rune rprev, r;
  int rune_size;
  re9_list_t tl, nl; /* this list, next list */
  re9_listitem_t *tlp, *tlxn;
  int match, i, flags;
  uint32_t f;
  const vmop_class_t *opc;
  int dont_collapse = 0;
  /* */
  flags = (progp->flags&(RE9_FLAG_CASEINSENS|RE9_FLAG_NONGREEDY))|(j->flags&(RE9_FLAG_NONUTF8|RE9_FLAG_ANYDOT));
  //dont_collapse = (flags&RE9_FLAG_NONGREEDY);
  match = 0;
#ifndef RE9_DISABLE_LEARNING
  checkstart = (progp->startflags != PRG_STARTS_WITH_ANY);
#endif
  if (mp != NULL) {
    for (i = 0; i < ms; ++i) mp[i].sp = mp[i].ep = NULL;
  } else {
    ms = 0;
  }
  if (ms < 0) ms = 0; else if (ms > RE9_SUBEXP_MAX) ms = RE9_SUBEXP_MAX;
  j->relist[0][0].inst = j->relist[1][0].inst = LASTINST;
  j->relistf[0] = j->relist[0];
  j->relistf[1] = j->relist[1];
  /* execute machine once for each character, including terminal NUL */
  s = j->bol;
  rprev = RE9_RUNE_SPEC_BOL;
  for (;;) {
    /* fast check for first char */
#ifndef RE9_DISABLE_LEARNING
    if (checkstart) {
      dlogf("checkstart! 0x%02x\n", progp->startflags);
      switch (progp->startflags) {
        /* simple cases */
        case PRG_STARTS_WITH_BOL:
          if (s == j->bol) break;
          if (s == j->eol) goto mt_quit;
          p = memchr(s, '\n', j->eol-s);
          if (p == NULL || p+1 > j->eol) goto mt_quit;
          s = p+1;
          rprev = (s == j->bol ? RE9_RUNE_SPEC_BOL : s[-1]); /*FIXME: previous rune can be UTF-8 one*/
          break;
        case PRG_STARTS_WITH_EOL:
          if (s == j->eol) goto mt_quit;
          p = memchr(s, '\n', j->eol-s);
          if (p == NULL) p = j->eol;
          s = p;
          rprev = (s == j->bol ? RE9_RUNE_SPEC_BOL : s[-1]); /*FIXME: previous rune can be UTF-8 one*/
          break;
        case PRG_STARTS_WITH_RUNE:
          if ((flags&RE9_FLAG_CASEINSENS) == 0) {
            /* case-sensitive */
            if (progp->startrune < 128 || (flags&RE9_FLAG_NONUTF8)) {
              if (progp->startrune > 255) goto mt_quit; /* can't be found */
              p = memchr(s, progp->startrune, j->eol-s);
            } else {
              p = re8_rune_strchr(s, progp->startrune, j->eol);
            }
          } else {
            /* case-insensitive */
            if (progp->startrune < 128 || (flags&RE9_FLAG_NONUTF8)) {
              if (progp->startrune > 255) goto mt_quit; /* can't be found */
              for (p = s; p < j->eol; ++p) if (UPPER(((unsigned char)*p)) == progp->startrune) break;
            } else {
              p = s;
              while (p < j->eol) {
                rune_size = re9_char2rune(&r, p, j->eol);
                if (UPPER(r) == progp->startrune) break;
                p += rune_size;
              }
            }
          }
          if (p == NULL || p > j->eol) goto mt_quit;
          s = p;
          rprev = (s == j->bol ? RE9_RUNE_SPEC_BOL : s[-1]); /*FIXME: previous rune can be UTF-8 one*/
          break;
        case PRG_STARTS_WITH_CLASS:
          opc = (const vmop_class_t *)(progp->code+progp->startrange);
          while (s < j->eol) {
            r = *(const uint8_t *)s;
            rune_size = (r < RE9_RUNE_SELF || (flags&RE9_FLAG_NONUTF8) ? 1 : re9_char2rune(&r, s, j->eol));
            if (flags&RE9_FLAG_CASEINSENS) r = UPPER(r);
            for (f = 0; f < opc->spi_count; f += 2) if (r >= opc->spi[f] && r <= opc->spi[f+1]) break;
            if (f < opc->spi_count) break;
            s += rune_size;
          }
          if (s >= j->eol) goto mt_quit;
          rprev = (s == j->bol ? RE9_RUNE_SPEC_BOL : s[-1]); /*FIXME: previous rune can be UTF-8 one*/
          break;
        default:
          /* difficult cases */
          if ((progp->startflags&PRG_STARTS_WITH_BOL) && s == j->bol) goto difficult_found;
          if ((progp->startflags&PRG_STARTS_WITH_EOL) && s == j->eol) goto difficult_found;
          opc = (const vmop_class_t *)(progp->code+progp->startrange);
          while (s < j->eol) {
            if (*s == '\n') {
              if (progp->startflags&PRG_STARTS_WITH_BOL) { ++s; break; }
              if (progp->startflags&PRG_STARTS_WITH_EOL) break;
            }
            if (progp->startflags&(PRG_STARTS_WITH_RUNE|PRG_STARTS_WITH_CLASS)) {
              r = *(const uint8_t *)s;
              rune_size = (r < RE9_RUNE_SELF || (flags&RE9_FLAG_NONUTF8) ? 1 : re9_char2rune(&r, s, j->eol));
              if (flags&RE9_FLAG_CASEINSENS) r = UPPER(r);
              if (progp->startflags&PRG_STARTS_WITH_RUNE) {
                if (r == progp->startrune) break;
              } else {
                for (f = 0; f < opc->spi_count; f += 2) if (r >= opc->spi[f] && r <= opc->spi[f+1]) break;
                if (f < opc->spi_count) break;
              }
              s += rune_size;
            } else {
              ++s;
            }
          }
          if (s > j->eol) goto mt_quit;
difficult_found:
          rprev = (s == j->bol ? RE9_RUNE_SPEC_BOL : s[-1]); /*FIXME: previous rune can be UTF-8 one*/
          break;
      }
    }
#endif
    if (s < j->eol) {
      r = *(const uint8_t *)s;
      rune_size = (r < RE9_RUNE_SELF || (flags&RE9_FLAG_NONUTF8) ? 1 : re9_char2rune(&r, s, j->eol));
      if (flags&RE9_FLAG_CASEINSENS) r = UPPER(r);
    } else {
      r = RE9_RUNE_SPEC_EOL;
      rune_size = 0;
    }
    /* switch run lists */
    tl.start = j->relist[flag];
    tl.end = j->relist[flag]+j->listsize;
    tl.free = j->relistf[flag];
    nl.start = j->relist[flag^=1];
    nl.end = j->relist[flag]+j->listsize;
    nl.free = nl.start;
    nl.start->inst = LASTINST;
    dlogf("*** new loop (flag=%d; mt=%d) %p\n", flag, match, tl.start);
    /* add first instruction to current list */
    if (match == 0) {
      if ((tlxn = re9l_newemptythread(&tl, progp->startinst, ms, s, dont_collapse)) == NULL) return -1;
    }
    tlxn = tl.free;
#ifdef RE9_DEBUG
    dlogf(" tlxn=%u\n", tlxn-tl.start);
    for (tlp = tl.start; tlp < tl.free; ++tlp) dlogf("%d: %u\n", tlp-tl.start, tlp->inst);
#endif
    /* execute machine until current list is empty */
    if (tl.start->inst == LASTINST) break; /* nothing to do */
#ifdef RE9_CALC_MAXT
    if (tl.free-tl.start > maxt) maxt = tl.free-tl.start;
#endif
    for (tlp = tl.start; tlp->inst != LASTINST; ++tlp) {
      uint32_t ip;
      dlogf("* new thread (%d) at %u\n", flag, tlp-tl.start);
#ifdef RE9_CALC_MAXT
      if (tlp-tl.start > maxt) maxt = tlp-tl.start;
#endif
      for (ip = tlp->inst; ip != LASTINST; ip = ((const vmopcode_t *)(progp->code+ip))->next) {
        const vmopcode_t *op = (const vmopcode_t *)(progp->code+ip);
#ifdef RE9_DEBUG
        dump_opcode(stderr, progp, ip);
#endif
        if (op->opcode < RUNE) {
          /* ascii character */
          if (op->opcode == r) {
            if (re9l_newthread(&nl, op->next, ms, &tlp->se, dont_collapse) == NULL) return -1;
          }
        } else {
          switch (op->opcode) {
            case RUNE: /* regular character */
              if (((const vmop_rune_t *)op)->r == r) {
                if (re9l_newthread(&nl, op->next, ms, &tlp->se, dont_collapse) == NULL) return -1;
              }
              break;
            case SMARK:
              tlp->se.m[((const vmop_mark_t *)op)->subid].sp = s;
              continue;
            case EMARK:
              tlp->se.m[((const vmop_mark_t *)op)->subid].ep = s;
              continue;
            case ANY:
              if ((flags&RE9_FLAG_ANYDOT) == 0 && r == '\n') break;
              /* fallthru */
            case ANYNL:
              if (re9l_newthread(&nl, op->next, ms, &tlp->se, dont_collapse) == NULL) return -1;
              break;
            case BOL:
              if (s == j->bol || rprev == RE9_RUNE_SPEC_BOL || rprev == '\n') continue;
              break;
            case EOL:
              if (s == j->eol || r == '\n') continue;
              break;
            case WBOUND:
              if (is_word_rune(rprev) != is_word_rune(r)) continue;
              break;
            case WNBOUND:
              if (is_word_rune(rprev) == is_word_rune(r)) continue;
              break;
            case CCLASS:
              opc = (const vmop_class_t *)op;
              for (f = 0; f < opc->spi_count; f += 2) {
                if (r >= opc->spi[f] && r <= opc->spi[f+1]) {
                  if (re9l_newthread(&nl, op->next, ms, &tlp->se, dont_collapse) == NULL) return -1;
                  break;
                }
              }
              break;
            case NCCLASS:
              opc = (const vmop_class_t *)op;
              for (f = 0; f < opc->spi_count; f += 2) if (r >= opc->spi[f] && r <= opc->spi[f+1]) break;
              if (f >= opc->spi_count) {
                if (re9l_newthread(&nl, op->next, ms, &tlp->se, dont_collapse) == NULL) return -1;
              }
              break;
#ifndef RE9_DISABLE_NONGREEDY
            case SPLIT_NG:
              if (re9l_newthread(&tl, op->next, ms, &tlp->se, 1) == NULL) return -1;
              if (re9l_newthread(&tl, ((const vmop_split_t *)op)->alt, ms, &tlp->se, 1) == NULL) return -1;
              break;
            case SPLIT_G:
              if (re9l_newthread(&tl, ((const vmop_split_t *)op)->alt, ms, &tlp->se, 1) == NULL) return -1;
              if (flags&RE9_FLAG_NONGREEDY) {
                if (re9l_newthread(&tl, op->next, ms, &tlp->se, 1) == NULL) return -1;
              } else {
                continue;
              }
              break;
#else
            case SPLIT_G:
              if (re9l_newthread(&tl, ((const vmop_split_t *)op)->alt, ms, &tlp->se, 1) == NULL) return -1;
              continue;
              break;
#endif
            case END: /* match! */
              match = 1;
              tlp->se.m[0].ep = s;
              if (mp != 0) re9l_newmatch(mp, ms, &tlp->se);
              dlogf("HIT at %u! (%d,%d) (%s)\n", tlp-tl.start, tlp->se.m[0].sp-j->bol, tlp->se.m[0].ep-j->bol, (tlp < tlxn ? "old" : "new"));
#ifndef RE9_DISABLE_NONGREEDY
              if (flags&RE9_FLAG_NONGREEDY) {
                /* fuck off all 'old' instructions */
                if ( tlp < tlxn) {
                  /* we are in 'old' area, skip it all */
                  tlp = tlxn-1; /* next one will be 'new' */
                } else {
                  /* we are in 'new' area, stop right here */
                  tlp[1].inst = LASTINST;
                }
              }
#endif
              break;
#ifdef RE9_DEBUG
            default:
              fprintf(stderr, "lebre9: INTRNAL ERROR: invalid command: 0%03o\n", op->opcode);
#endif
          } /* switch */
        } /* if */
        break;
      }
    }
    j->relistf[flag] = nl.free; /* update 'free' pointer */
    dlogf("+ free=%u; sz=%d\n", nl.free-nl.start, j->listsize);
    if (s == j->eol) break;
#ifndef RE9_DISABLE_LEARNING
    checkstart = (progp->startflags != PRG_STARTS_WITH_ANY && nl.start->inst == LASTINST && !match);
#endif
    rprev = r;
    s += rune_size;
    dlogf("+++ (%d) eol=%d\n", r, s == j->eol);
  }
#ifndef RE9_DISABLE_LEARNING
mt_quit:
#endif
#ifdef RE9_CALC_MAXT
  fprintf(stderr, "MAXT=%d\n", maxt);
#endif
  return match;
}


static int re9_exec_internal (const re9_prog_t *progp, int flags, const char *bol, re9_sub_t *mp, int ms, re9_listitem_t *rl0, re9_listitem_t *rl1, size_t listsz) {
  re9_ljunk_t j;
  /* use user-specified starting/ending location if specified */
  if ((flags&RE9_FLAG_MT0_RANGE) && mp != NULL) {
    j.bol = (mp->sp != NULL ? mp->sp : bol);
    j.eol = (mp->ep != NULL ? mp->ep : j.bol+strlen(j.bol));
  } else {
    j.eol = (j.bol = bol)+strlen(bol);
  }
  j.flags = flags;
  j.listsize = listsz;
  j.relist[0] = rl0;
  j.relist[1] = rl1;
  return regexec1(progp, mp, ms, &j);
}


/*
 * progp: program to run
 * bol: string to run machine on
 * mp: subexpression elements
 * ms: number of elements at mp
 */
int re9_execute_ex (const re9_prog_t *progp, int flags, const char *bol, re9_sub_t *mp, int ms, size_t maxmem) {
  re9_listitem_t relist[2][LISTSIZE];
  const char *b, *e;
  if ((flags&RE9_FLAG_MT0_RANGE) && mp != NULL) { b = mp[0].sp; e = mp[0].ep; } else { b = e = NULL; }
  int rv = re9_exec_internal(progp, flags, bol, mp, ms, relist[0], relist[1], LISTSIZE);
  if (rv < 0) {
    re9_listitem_t *r[2];
    int listsize = BIGLISTSIZE, rv;
    if (maxmem == 0) maxmem = 1024*1024*32; /* up to 32MB */
    for (;;) {
      int f;
      for (f = 0; f < 2; ++f) {
        if ((r[f] = malloc(listsize*sizeof(re9_listitem_t))) == NULL) {
          while (--f >= 0) free(r[f]);
          return -1;
        }
      }
      if ((flags&RE9_FLAG_MT0_RANGE) && mp != NULL) { mp[0].sp = b; mp[0].ep = e; }
      rv = re9_exec_internal(progp, flags, bol, mp, ms, r[0], r[1], listsize);
      while (--f >= 0) free(r[f]);
      if (rv >= 0) break;
      if (listsize*2*sizeof(re9_listitem_t)*2 > maxmem) {
        size_t nsz = maxmem/(sizeof(re9_listitem_t)*2);
        if (nsz <= listsize) break;
        listsize = nsz;
      } else {
        listsize *= 2;
      }
    }
#ifdef RE9_CALC_MAXT
    if (rv < 0) fprintf(stderr, "OUT OF MEMORY! listsize=%d\n", listsize/2);
#endif
  }
  return rv;
}


int re9_execute (const re9_prog_t *progp, int flags, const char *bol, re9_sub_t *mp, int ms) {
  return re9_execute_ex(progp, flags, bol, mp, ms, 0);
}


/******************************************************************************/
struct re9_prog_prepared_s {
  const re9_prog_t *progp;
  re9_listitem_t *relist[2];
  size_t listsize;
  size_t maxmem;
};


re9_prog_prepared_t *re9_prepare_ex (const re9_prog_t *progp, size_t maxmem) {
  re9_prog_prepared_t *res;
  int f;
  if (progp == NULL) return NULL;
  if ((res = malloc(sizeof(*res))) == NULL) return NULL;
  if (maxmem == 0) maxmem = 1024*1024*32; /* up to 32MB */
  res->progp = progp;
  res->listsize = BIGLISTSIZE;
  res->maxmem = maxmem;
  for (f = 0; f < 2; ++f) {
    if ((res->relist[f] = malloc(res->listsize*sizeof(re9_listitem_t))) == NULL) {
      while (--f >= 0) free(res->relist[f]);
      free(res);
      return NULL;
    }
  }
  return res;
}


re9_prog_prepared_t *re9_prepare (const re9_prog_t *progp) {
  return re9_prepare_ex(progp, 0);
}


int re9_prepared_execute (re9_prog_prepared_t *pp, int flags, const char *bol, re9_sub_t *mp, int ms) {
  if (pp != NULL) {
    int rv, f;
    const char *b, *e;
    if ((flags&RE9_FLAG_MT0_RANGE) && mp != NULL) { b = mp[0].sp; e = mp[0].ep; } else { b = e = NULL; }
    for (;;) {
      rv = re9_exec_internal(pp->progp, flags, bol, mp, ms, pp->relist[0], pp->relist[1], pp->listsize);
      if (rv >= 0 || pp->listsize*sizeof(re9_listitem_t)*2 >= pp->maxmem) break;
      if (pp->listsize*2*sizeof(re9_listitem_t)*2 > pp->maxmem) {
        size_t nsz = pp->maxmem/(sizeof(re9_listitem_t)*2);
        if (nsz <= pp->listsize) break;
        pp->listsize = nsz;
      } else {
        pp->listsize *= 2;
      }
      for (f = 0; f < 2; ++f) {
        re9_listitem_t *r = realloc(pp->relist[f], pp->listsize*sizeof(re9_listitem_t));
        if (r == NULL) break;
        pp->relist[f] = r;
      }
      if (f < 2) { pp->listsize /= 2; rv = -1; break; }
      if ((flags&RE9_FLAG_MT0_RANGE) && mp != NULL) { mp[0].sp = b; mp[0].ep = e; }
    }
#ifdef RE9_CALC_MAXT
    if (rv < 0) fprintf(stderr, "OUT OF MEMORY! listsize=%u\n", pp->listsize);
#endif
    if (pp->listsize > 32767) {
      int f;
#ifdef RE9_CALC_MAXT
      fprintf(stderr, "*SHRINK: %u --> 32768\n", pp->listsize);
#endif
      pp->listsize = 32768;
      for (f = 0; f < 2; ++f) {
        re9_listitem_t *r = realloc(pp->relist[f], pp->listsize*sizeof(re9_listitem_t));
        if (r == NULL) break;
        pp->relist[f] = r;
      }
    }
    return rv;
  }
  return -1;
}


void re9_prepared_free (re9_prog_prepared_t *pp) {
  if (pp != NULL) {
    if (pp->relist[1] != NULL) free(pp->relist[1]);
    if (pp->relist[0] != NULL) free(pp->relist[0]);
    free(pp);
  }
}


/******************************************************************************/
/* substitute into one string using the matches from the last re9_execute() */
int re9_sub (char *dp, size_t dlen, const char *sp, const re9_sub_t *mp, int ms) {
  int res = 0;
  char *dlast;
  if (mp == NULL || ms <= 0) ms = 0;
  if (dp == NULL) dlen = 0;
  dlast = (dlen > 0 ? dp+dlen-1 : NULL);
  while (*sp) {
    if (*sp == '\\' && (sp[1] == '{' || (sp[1] >= '0' && sp[1] <= '9'))) {
      int i = sp[1]-'0';
      if (i > 9) {
        /* parse {...} */
        i = 0;
        sp += 2;
        while (*sp && *sp != '}') {
          if (*sp < '0' || *sp > '9') break;
          i = i*10+sp[0]-'0';
          ++sp;
          if (i > ms) break;
        }
        while (*sp && *sp != '}') ++sp;
        if (*sp == '}') ++sp;
      } else {
        sp += 2;
      }
      if (i < ms && mp[i].sp != NULL) {
        const char *ssp = mp[i].sp;
        int len = (int)(mp[i].ep-ssp); /*FIXME: 2GB strings?*/
        if (len > 0) {
          res += len;
          if (len > dlen) len = dlen;
          if (len > 0) memcpy(dp, ssp, len);
          dlen -= len;
          dp += len;
        }
      }
    } else {
      if (*sp == '\\') {
        if (dlen > 0) {
          *dp++ = (sp[1] == 'z' ? 0 : sp[1]);
          --dlen;
        }
        sp += 2;
      } else {
        if (dlen > 0) { *dp++ = *sp++; --dlen; } else ++sp;
      }
      ++res;
    }
  }
  if (dlen > 0) *dp = '\0'; else if (dlast != NULL) *dlast = '\0';
  return ++res;
}