/*-

 * This code is derived from OpenBSD's libc/regex, original license follows:

 *

 * Copyright (c) 1992, 1993, 1994 Henry Spencer.

 * Copyright (c) 1992, 1993, 1994

 *  The Regents of the University of California.  All rights reserved.

 *

 * This code is derived from software contributed to Berkeley by

 * Henry Spencer.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 * 3. Neither the name of the University nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 * SUCH DAMAGE.

 *

 *  @(#)regcomp.c 8.5 (Berkeley) 3/20/94

 */

#include <sys/types.h>

#include <stdint.h>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <limits.h>

#include <stdlib.h>

#include "regex_impl.h"

#include "regutils.h"

#include "regex2.h"

#include "llvm/Config/config.h"

#include "llvm/Support/Compiler.h"

/* character-class table */

static struct cclass {

  const char *name;

  const char *chars;

  const char *multis;

} cclasses[] = {

  { "alnum",  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\

0123456789",        ""} ,

  { "alpha",  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",

          ""} ,

  { "blank",  " \t",    ""} ,

  { "cntrl",  "\007\b\t\n\v\f\r\1\2\3\4\5\6\16\17\20\21\22\23\24\

\25\26\27\30\31\32\33\34\35\36\37\177", ""} ,

  { "digit",  "0123456789", ""} ,

  { "graph",  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\

0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~",

          ""} ,

  { "lower",  "abcdefghijklmnopqrstuvwxyz",

          ""} ,

  { "print",  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\

0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ",

          ""} ,

  { "punct",  "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~",

          ""} ,

  { "space",  "\t\n\v\f\r ",  ""} ,

  { "upper",  "ABCDEFGHIJKLMNOPQRSTUVWXYZ",

          ""} ,

  { "xdigit", "0123456789ABCDEFabcdef",

          ""} ,

  { NULL,   0,    "" }

};

/* character-name table */

static struct cname {

  const char *name;

  char code;

} cnames[] = {

  { "NUL",      '\0' },

  { "SOH",      '\001' },

  { "STX",      '\002' },

  { "ETX",      '\003' },

  { "EOT",      '\004' },

  { "ENQ",      '\005' },

  { "ACK",      '\006' },

  { "BEL",      '\007' },

  { "alert",      '\007' },

  { "BS",       '\010' },

  { "backspace",      '\b' },

  { "HT",       '\011' },

  { "tab",      '\t' },

  { "LF",       '\012' },

  { "newline",      '\n' },

  { "VT",       '\013' },

  { "vertical-tab",   '\v' },

  { "FF",       '\014' },

  { "form-feed",      '\f' },

  { "CR",       '\015' },

  { "carriage-return",    '\r' },

  { "SO",       '\016' },

  { "SI",       '\017' },

  { "DLE",      '\020' },

  { "DC1",      '\021' },

  { "DC2",      '\022' },

  { "DC3",      '\023' },

  { "DC4",      '\024' },

  { "NAK",      '\025' },

  { "SYN",      '\026' },

  { "ETB",      '\027' },

  { "CAN",      '\030' },

  { "EM",       '\031' },

  { "SUB",      '\032' },

  { "ESC",      '\033' },

  { "IS4",      '\034' },

  { "FS",       '\034' },

  { "IS3",      '\035' },

  { "GS",       '\035' },

  { "IS2",      '\036' },

  { "RS",       '\036' },

  { "IS1",      '\037' },

  { "US",       '\037' },

  { "space",      ' ' },

  { "exclamation-mark",   '!' },

  { "quotation-mark",   '"' },

  { "number-sign",    '#' },

  { "dollar-sign",    '$' },

  { "percent-sign",   '%' },

  { "ampersand",      '&' },

  { "apostrophe",     '\'' },

  { "left-parenthesis",   '(' },

  { "right-parenthesis",    ')' },

  { "asterisk",     '*' },

  { "plus-sign",      '+' },

  { "comma",      ',' },

  { "hyphen",     '-' },

  { "hyphen-minus",   '-' },

  { "period",     '.' },

  { "full-stop",      '.' },

  { "slash",      '/' },

  { "solidus",      '/' },

  { "zero",     '0' },

  { "one",      '1' },

  { "two",      '2' },

  { "three",      '3' },

  { "four",     '4' },

  { "five",     '5' },

  { "six",      '6' },

  { "seven",      '7' },

  { "eight",      '8' },

  { "nine",     '9' },

  { "colon",      ':' },

  { "semicolon",      ';' },

  { "less-than-sign",   '<' },

  { "equals-sign",    '=' },

  { "greater-than-sign",    '>' },

  { "question-mark",    '?' },

  { "commercial-at",    '@' },

  { "left-square-bracket",  '[' },

  { "backslash",      '\\' },

  { "reverse-solidus",    '\\' },

  { "right-square-bracket", ']' },

  { "circumflex",     '^' },

  { "circumflex-accent",    '^' },

  { "underscore",     '_' },

  { "low-line",     '_' },

  { "grave-accent",   '`' },

  { "left-brace",     '{' },

  { "left-curly-bracket",   '{' },

  { "vertical-line",    '|' },

  { "right-brace",    '}' },

  { "right-curly-bracket",  '}' },

  { "tilde",      '~' },

  { "DEL",      '\177' },

  { NULL,       0 }

};

/*

 * parse structure, passed up and down to avoid global variables and

 * other clumsinesses

 */

struct parse {

  char *next;   /* next character in RE */

  char *end;    /* end of string (-> NUL normally) */

  int error;    /* has an error been seen? */

  sop *strip;   /* malloced strip */

  sopno ssize;    /* malloced strip size (allocated) */

  sopno slen;   /* malloced strip length (used) */

  int ncsalloc;   /* number of csets allocated */

  struct re_guts *g;

# define  NPAREN  10  /* we need to remember () 1-9 for back refs */

  sopno pbegin[NPAREN]; /* -> ( ([0] unused) */

  sopno pend[NPAREN]; /* -> ) ([0] unused) */

};

static void p_ere(struct parse *, int);

static void p_ere_exp(struct parse *);

static void p_str(struct parse *);

static void p_bre(struct parse *, int, int);

static int p_simp_re(struct parse *, int);

static int p_count(struct parse *);

static void p_bracket(struct parse *);

static void p_b_term(struct parse *, cset *);

static void p_b_cclass(struct parse *, cset *);

static void p_b_eclass(struct parse *, cset *);

static char p_b_symbol(struct parse *);

static char p_b_coll_elem(struct parse *, int);

static char othercase(int);

static void bothcases(struct parse *, int);

static void ordinary(struct parse *, int);

static void nonnewline(struct parse *);

static void repeat(struct parse *, sopno, int, int);

static int seterr(struct parse *, int);

static cset *allocset(struct parse *);

static void freeset(struct parse *, cset *);

static int freezeset(struct parse *, cset *);

static int firstch(struct parse *, cset *);

static int nch(struct parse *, cset *);

static void mcadd(struct parse *, cset *, const char *);

static void mcinvert(struct parse *, cset *);

static void mccase(struct parse *, cset *);

static int isinsets(struct re_guts *, int);

static int samesets(struct re_guts *, int, int);

static void categorize(struct parse *, struct re_guts *);

static sopno dupl(struct parse *, sopno, sopno);

static void doemit(struct parse *, sop, size_t);

static void doinsert(struct parse *, sop, size_t, sopno);

static void dofwd(struct parse *, sopno, sop);

static void enlarge(struct parse *, sopno);

static void stripsnug(struct parse *, struct re_guts *);

static void findmust(struct parse *, struct re_guts *);

static sopno pluscount(struct parse *, struct re_guts *);

static char nuls[10];   /* place to point scanner in event of error */

/*

 * macros for use with parse structure

 * BEWARE:  these know that the parse structure is named `p' !!!

 */

#define PEEK()  (*p->next)

#define PEEK2() (*(p->next+1))

#define MORE()  (p->next < p->end)

#define MORE2() (p->next+1 < p->end)

#define SEE(c)  (MORE() && PEEK() == (c))

#define SEETWO(a, b)  (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))

#define EAT(c)  ((SEE(c)) ? (NEXT(), 1) : 0)

#define EATTWO(a, b)  ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)

#define NEXT()  (p->next++)

#define NEXT2() (p->next += 2)

#define NEXTn(n)  (p->next += (n))

#define GETNEXT() (*p->next++)

#define SETERROR(e) seterr(p, (e))

#define REQUIRE(co, e)  (void)((co) || SETERROR(e))

#define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))

#define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))

#define MUSTNOTSEE(c, e)  (REQUIRE(!MORE() || PEEK() != (c), e))

#define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))

#define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)

#define AHEAD(pos)    dofwd(p, pos, HERE()-(pos))

#define ASTERN(sop, pos)  EMIT(sop, HERE()-pos)

#define HERE()    (p->slen)

#define THERE()   (p->slen - 1)

#define THERETHERE()  (p->slen - 2)

#define DROP(n) (p->slen -= (n))

#ifdef  _POSIX2_RE_DUP_MAX

#define DUPMAX  _POSIX2_RE_DUP_MAX

#else

#define DUPMAX  255

#endif

#define INFINITY  (DUPMAX + 1)

#ifndef NDEBUG

static int never = 0;   /* for use in asserts; shuts lint up */

#else

#define never 0   /* some <assert.h>s have bugs too */

#endif

/*

 - llvm_regcomp - interface for parser and compilation

 */

int       /* 0 success, otherwise REG_something */

llvm_regcomp(llvm_regex_t *preg, const char *pattern, int cflags)

{

  struct parse pa;

  struct re_guts *g;

  struct parse *p = &pa;

  int i;

  size_t len;

#ifdef REDEBUG

# define  GOODFLAGS(f)  (f)

#else

# define  GOODFLAGS(f)  ((f)&~REG_DUMP)

#endif

  cflags = GOODFLAGS(cflags);

  if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))

    return(REG_INVARG);

  if (cflags&REG_PEND) {

    if (preg->re_endp < pattern)

      return(REG_INVARG);

    len = preg->re_endp - pattern;

  } else

    len = strlen((const char *)pattern);

  /* do the mallocs early so failure handling is easy */

  g = (struct re_guts *)malloc(sizeof(struct re_guts) +

              (NC-1)*sizeof(cat_t));

  if (g == NULL)

    return(REG_ESPACE);

  p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */

  p->strip = (sop *)calloc(p->ssize, sizeof(sop));

  p->slen = 0;

  if (p->strip == NULL) {

    free((char *)g);

    return(REG_ESPACE);

  }

  /* set things up */

  p->g = g;

  p->next = (char *)pattern;  /* convenience; we do not modify it */

  p->end = p->next + len;

  p->error = 0;

  p->ncsalloc = 0;

  for (i = 0; i < NPAREN; i++) {

    p->pbegin[i] = 0;

    p->pend[i] = 0;

  }

  g->csetsize = NC;

  g->sets = NULL;

  g->setbits = NULL;

  g->ncsets = 0;

  g->cflags = cflags;

  g->iflags = 0;

  g->nbol = 0;

  g->neol = 0;

  g->must = NULL;

  g->mlen = 0;

  g->nsub = 0;

  g->ncategories = 1; /* category 0 is "everything else" */

  g->categories = &g->catspace[-(CHAR_MIN)];

  (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));

  g->backrefs = 0;

  /* do it */

  EMIT(OEND, 0);

  g->firststate = THERE();

  if (cflags&REG_EXTENDED)

    p_ere(p, OUT);

  else if (cflags&REG_NOSPEC)

    p_str(p);

  else

    p_bre(p, OUT, OUT);

  EMIT(OEND, 0);

  g->laststate = THERE();

  /* tidy up loose ends and fill things in */

  categorize(p, g);

  stripsnug(p, g);

  findmust(p, g);

  g->nplus = pluscount(p, g);

  g->magic = MAGIC2;

  preg->re_nsub = g->nsub;

  preg->re_g = g;

  preg->re_magic = MAGIC1;

#ifndef REDEBUG

  /* not debugging, so can't rely on the assert() in llvm_regexec() */

  if (g->iflags&REGEX_BAD)

    SETERROR(REG_ASSERT);

#endif

  /* win or lose, we're done */

  if (p->error != 0) /* lose */

    llvm_regfree(preg);

  return(p->error);

}

/*

 - p_ere - ERE parser top level, concatenation and alternation

 */

static void

p_ere(struct parse *p, int stop)  /* character this ERE should end at */

{

  char c;

  sopno prevback = 0;

  sopno prevfwd = 0;

  sopno conc;

  int first = 1;    /* is this the first alternative? */

  for (;;) {

    /* do a bunch of concatenated expressions */

    conc = HERE();

    while (MORE() && (c = PEEK()) != '|' && c != stop)

      p_ere_exp(p);

    REQUIRE(HERE() != conc, REG_EMPTY);  /* require nonempty */

    if (!EAT('|'))

      break;   /* NOTE BREAK OUT */

    if (first) {

      INSERT(OCH_, conc); /* offset is wrong */

      prevfwd = conc;

      prevback = conc;

      first = 0;

    }

    ASTERN(OOR1, prevback);

    prevback = THERE();

    AHEAD(prevfwd);      /* fix previous offset */

    prevfwd = HERE();

    EMIT(OOR2, 0);      /* offset is very wrong */

  }

  if (!first) {   /* tail-end fixups */

    AHEAD(prevfwd);

    ASTERN(O_CH, prevback);

  }

  assert(!MORE() || SEE(stop));

}

/*

 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op

 */

static void

p_ere_exp(struct parse *p)

{

  char c;

  sopno pos;

  int count;

  int count2;

  int backrefnum;

  sopno subno;

  int wascaret = 0;

  assert(MORE());   /* caller should have ensured this */

  c = GETNEXT();

  pos = HERE();

  switch (c) {

  case '(':

    REQUIRE(MORE(), REG_EPAREN);

    p->g->nsub++;

    subno = p->g->nsub;

    if (subno < NPAREN)

      p->pbegin[subno] = HERE();

    EMIT(OLPAREN, subno);

    if (!SEE(')'))

      p_ere(p, ')');

    if (subno < NPAREN) {

      p->pend[subno] = HERE();

      assert(p->pend[subno] != 0);

    }

    EMIT(ORPAREN, subno);

    MUSTEAT(')', REG_EPAREN);

    break;

#ifndef POSIX_MISTAKE

  case ')':   /* happens only if no current unmatched ( */

    /*

     * You may ask, why the ifndef?  Because I didn't notice

     * this until slightly too late for 1003.2, and none of the

     * other 1003.2 regular-expression reviewers noticed it at

     * all.  So an unmatched ) is legal POSIX, at least until

     * we can get it fixed.

     */

    SETERROR(REG_EPAREN);

    break;

#endif

  case '^':

    EMIT(OBOL, 0);

    p->g->iflags |= USEBOL;

    p->g->nbol++;

    wascaret = 1;

    break;

  case '$':

    EMIT(OEOL, 0);

    p->g->iflags |= USEEOL;

    p->g->neol++;

    break;

  case '|':

    SETERROR(REG_EMPTY);

    break;

  case '*':

  case '+':

  case '?':

    SETERROR(REG_BADRPT);

    break;

  case '.':

    if (p->g->cflags&REG_NEWLINE)

      nonnewline(p);

    else

      EMIT(OANY, 0);

    break;

  case '[':

    p_bracket(p);

    break;

  case '\\':

    REQUIRE(MORE(), REG_EESCAPE);

    c = GETNEXT();

    if (c >= '1' && c <= '9') {

      /* \[0-9] is taken to be a back-reference to a previously specified

       * matching group. backrefnum will hold the number. The matching

       * group must exist (i.e. if \4 is found there must have been at

       * least 4 matching groups specified in the pattern previously).

       */

      backrefnum = c - '0';

      if (p->pend[backrefnum] == 0) {

        SETERROR(REG_ESUBREG);

        break;

      }

      /* Make sure everything checks out and emit the sequence

       * that marks a back-reference to the parse structure.

       */

      assert(backrefnum <= p->g->nsub);

      EMIT(OBACK_, backrefnum);

      assert(p->pbegin[backrefnum] != 0);

      assert(OP(p->strip[p->pbegin[backrefnum]]) != OLPAREN);

      assert(OP(p->strip[p->pend[backrefnum]]) != ORPAREN);

      (void) dupl(p, p->pbegin[backrefnum]+1, p->pend[backrefnum]);

      EMIT(O_BACK, backrefnum);

      p->g->backrefs = 1;

    } else {

      /* Other chars are simply themselves when escaped with a backslash.

       */

      ordinary(p, c);

    }

    break;

  case '{':   /* okay as ordinary except if digit follows */

    REQUIRE(!MORE() || !isdigit((uch)PEEK()), REG_BADRPT);

    LLVM_FALLTHROUGH;

  default:

    ordinary(p, c);

    break;

  }

  if (!MORE())

    return;

  c = PEEK();

  /* we call { a repetition if followed by a digit */

  if (!( c == '*' || c == '+' || c == '?' ||

        (c == '{' && MORE2() && isdigit((uch)PEEK2())) ))

    return;   /* no repetition, we're done */

  NEXT();

  REQUIRE(!wascaret, REG_BADRPT);

  switch (c) {

  case '*': /* implemented as +? */

    /* this case does not require the (y|) trick, noKLUDGE */

    INSERT(OPLUS_, pos);

    ASTERN(O_PLUS, pos);

    INSERT(OQUEST_, pos);

    ASTERN(O_QUEST, pos);

    break;

  case '+':

    INSERT(OPLUS_, pos);

    ASTERN(O_PLUS, pos);

    break;

  case '?':

    /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */

    INSERT(OCH_, pos);    /* offset slightly wrong */

    ASTERN(OOR1, pos);    /* this one's right */

    AHEAD(pos);      /* fix the OCH_ */

    EMIT(OOR2, 0);      /* offset very wrong... */

    AHEAD(THERE());      /* ...so fix it */

    ASTERN(O_CH, THERETHERE());

    break;

  case '{':

    count = p_count(p);

    if (EAT(',')) {

      if (isdigit((uch)PEEK())) {

        count2 = p_count(p);

        REQUIRE(count <= count2, REG_BADBR);

      } else    /* single number with comma */

        count2 = INFINITY;

    } else    /* just a single number */

      count2 = count;

    repeat(p, pos, count, count2);

    if (!EAT('}')) { /* error heuristics */

      while (MORE() && PEEK() != '}')

        NEXT();

      REQUIRE(MORE(), REG_EBRACE);

      SETERROR(REG_BADBR);

    }

    break;

  }

  if (!MORE())

    return;

  c = PEEK();

  if (!( c == '*' || c == '+' || c == '?' ||

        (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) )

    return;

  SETERROR(REG_BADRPT);

}

/*

 - p_str - string (no metacharacters) "parser"

 */

static void

p_str(struct parse *p)

{

  REQUIRE(MORE(), REG_EMPTY);

  while (MORE())

    ordinary(p, GETNEXT());

}

/*

 - p_bre - BRE parser top level, anchoring and concatenation

 * Giving end1 as OUT essentially eliminates the end1/end2 check.

 *

 * This implementation is a bit of a kludge, in that a trailing $ is first

 * taken as an ordinary character and then revised to be an anchor.  The

 * only undesirable side effect is that '$' gets included as a character

 * category in such cases.  This is fairly harmless; not worth fixing.

 * The amount of lookahead needed to avoid this kludge is excessive.

 */

static void

p_bre(struct parse *p,

    int end1,   /* first terminating character */

    int end2)   /* second terminating character */

{

  sopno start = HERE();

  int first = 1;      /* first subexpression? */

  int wasdollar = 0;

  if (EAT('^')) {

    EMIT(OBOL, 0);

    p->g->iflags |= USEBOL;

    p->g->nbol++;

  }

  while (MORE() && !SEETWO(end1, end2)) {

    wasdollar = p_simp_re(p, first);

    first = 0;

  }

  if (wasdollar) { /* oops, that was a trailing anchor */

    DROP(1);

    EMIT(OEOL, 0);

    p->g->iflags |= USEEOL;

    p->g->neol++;

  }

  REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */

}

/*

 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition

 */

static int      /* was the simple RE an unbackslashed $? */

p_simp_re(struct parse *p,

    int starordinary)   /* is a leading * an ordinary character? */

{

  int c;

  int count;

  int count2;

  sopno pos;

  int i;

  sopno subno;

# define  BACKSL  (1<<CHAR_BIT)

        pos = HERE(); /* repetition op, if any, covers from here */

        assert(MORE()); /* caller should have ensured this */

        c = GETNEXT();

  if (c == '\\') {

    REQUIRE(MORE(), REG_EESCAPE);

    c = BACKSL | GETNEXT();

  }

  switch (c) {

  case '.':

    if (p->g->cflags&REG_NEWLINE)

      nonnewline(p);

    else

      EMIT(OANY, 0);

    break;

  case '[':

    p_bracket(p);

    break;

  case BACKSL|'{':

    SETERROR(REG_BADRPT);

    break;

  case BACKSL|'(':

    p->g->nsub++;

    subno = p->g->nsub;

    if (subno < NPAREN)

      p->pbegin[subno] = HERE();

    EMIT(OLPAREN, subno);

    /* the MORE here is an error heuristic */

    if (MORE() && !SEETWO('\\', ')'))

      p_bre(p, '\\', ')');

    if (subno < NPAREN) {

      p->pend[subno] = HERE();

      assert(p->pend[subno] != 0);

    }

    EMIT(ORPAREN, subno);

    REQUIRE(EATTWO('\\', ')'), REG_EPAREN);

    break;

  case BACKSL|')': /* should not get here -- must be user */

  case BACKSL|'}':

    SETERROR(REG_EPAREN);

    break;

  case BACKSL|'1':

  case BACKSL|'2':

  case BACKSL|'3':

  case BACKSL|'4':

  case BACKSL|'5':

  case BACKSL|'6':

  case BACKSL|'7':

  case BACKSL|'8':

  case BACKSL|'9':

    i = (c&~BACKSL) - '0';

    assert(i < NPAREN);

    if (p->pend[i] != 0) {

      assert(i <= p->g->nsub);

      EMIT(OBACK_, i);

      assert(p->pbegin[i] != 0);

      assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);

      assert(OP(p->strip[p->pend[i]]) == ORPAREN);

      (void) dupl(p, p->pbegin[i]+1, p->pend[i]);

      EMIT(O_BACK, i);

    } else

      SETERROR(REG_ESUBREG);

    p->g->backrefs = 1;

    break;

  case '*':

    REQUIRE(starordinary, REG_BADRPT);

    LLVM_FALLTHROUGH;

  default:

    ordinary(p, (char)c);

    break;

  }

  if (EAT('*')) {   /* implemented as +? */

    /* this case does not require the (y|) trick, noKLUDGE */

    INSERT(OPLUS_, pos);

    ASTERN(O_PLUS, pos);

    INSERT(OQUEST_, pos);

    ASTERN(O_QUEST, pos);

  } else if (EATTWO('\\', '{')) {

    count = p_count(p);

    if (EAT(',')) {

      if (MORE() && isdigit((uch)PEEK())) {

        count2 = p_count(p);

        REQUIRE(count <= count2, REG_BADBR);

      } else    /* single number with comma */

        count2 = INFINITY;

    } else    /* just a single number */

      count2 = count;

    repeat(p, pos, count, count2);

    if (!EATTWO('\\', '}')) { /* error heuristics */

      while (MORE() && !SEETWO('\\', '}'))

        NEXT();

      REQUIRE(MORE(), REG_EBRACE);

      SETERROR(REG_BADBR);

    }

  } else if (c == '$') /* $ (but not \$) ends it */

    return(1);

  return(0);

}

/*

 - p_count - parse a repetition count

 */

static int      /* the value */

p_count(struct parse *p)

{

  int count = 0;

  int ndigits = 0;

  while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) {

    count = count*10 + (GETNEXT() - '0');

    ndigits++;

  }

  REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);

  return(count);

}

/*

 - p_bracket - parse a bracketed character list

 *

 * Note a significant property of this code:  if the allocset() did SETERROR,

 * no set operations are done.

 */

static void

p_bracket(struct parse *p)

{

  cset *cs;

  int invert = 0;

  /* Dept of Truly Sickening Special-Case Kludges */

  if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {

    EMIT(OBOW, 0);

    NEXTn(6);

    return;

  }

  if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {

    EMIT(OEOW, 0);

    NEXTn(6);

    return;

  }

  if ((cs = allocset(p)) == NULL) {

    /* allocset did set error status in p */

    return;

  }

  if (EAT('^'))

    invert++; /* make note to invert set at end */

  if (EAT(']'))

    CHadd(cs, ']');

  else if (EAT('-'))

    CHadd(cs, '-');

  while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))

    p_b_term(p, cs);

  if (EAT('-'))

    CHadd(cs, '-');

  MUSTEAT(']', REG_EBRACK);

  if (p->error != 0) { /* don't mess things up further */

    freeset(p, cs);

    return;

  }

  if (p->g->cflags&REG_ICASE) {

    int i;

    int ci;

    for (i = p->g->csetsize - 1; i >= 0; i--)

      if (CHIN(cs, i) && isalpha(i)) {

        ci = othercase(i);

        if (ci != i)

          CHadd(cs, ci);

      }

    if (cs->multis != NULL)

      mccase(p, cs);

  }

  if (invert) {

    int i;

    for (i = p->g->csetsize - 1; i >= 0; i--)

      if (CHIN(cs, i))

        CHsub(cs, i);

      else

        CHadd(cs, i);

    if (p->g->cflags&REG_NEWLINE)

      CHsub(cs, '\n');

    if (cs->multis != NULL)

      mcinvert(p, cs);

  }

  assert(cs->multis == NULL);   /* xxx */

  if (nch(p, cs) == 1) {   /* optimize singleton sets */

    ordinary(p, firstch(p, cs));

    freeset(p, cs);

  } else

    EMIT(OANYOF, freezeset(p, cs));

}

/*

 - p_b_term - parse one term of a bracketed character list

 */

static void

p_b_term(struct parse *p, cset *cs)

{

  char c;

  char start, finish;

  int i;

  /* classify what we've got */

  switch ((MORE()) ? PEEK() : '\0') {

  case '[':

    c = (MORE2()) ? PEEK2() : '\0';