Logo Search packages:      
Sourcecode: ksh version File versions  Download package

regcomp.c

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2009 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                 Glenn Fowler <gsf@research.att.com>                  *
*                  David Korn <dgk@research.att.com>                   *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#pragma prototyped

/*
 * posix regex compiler
 */

#include "reglib.h"

#if _PACKAGE_ast
#include "lclib.h"
#endif

#define serialize       re_serialize      /* hp.ia64 <unistd.h>! */

#define C_ESC                 (-1)
#define C_MB                  (-2)

#if _AST_REGEX_DEBUG

#define DEBUG_TEST(f,y,n)     ((debug&(debug_flag=f))?(y):(n))
#define DEBUG_CODE(f,y,n)     do if(debug&(f)){y}else{n} while(0)
#define DEBUG_INIT()          do { char* t; if (!debug) { debug = 0x80000000; if (t = getenv("_AST_regex_comp_debug")) debug |= strtoul(t, NiL, 0); } } while (0)

static unsigned long    debug;
static unsigned long    debug_flag;

#else

#define DEBUG_INIT()
#define DEBUG_TEST(f,y,n)     (n)
#define DEBUG_CODE(f,y,n)     do {n} while(0)

#endif

#if _PACKAGE_ast

typedef struct Cchr_s
{
      Dtlink_t    lnk;
      unsigned char     nam[2];
      Ckey_t            key;
} Cchr_t;

#endif

#define eat(p)          do{if ((p)->token.push)(p)->token.push=0;else (p)->cursor+=(p)->token.len;}while (0)

/*
 * determine whether greedy matching will work, i.e. produce
 * the best match first.  such expressions are "easy", and
 * need no backtracking once a complete match is found.  
 * if an expression has backreferences or alts it's hard
 * else if it has only one closure it's easy
 * else if all closures are simple (i.e. one-character) it's easy
 * else it's hard.
 */

typedef struct Stats_s
{
      unsigned long     l;    /* min length to left of x          */
      unsigned long     k;    /* min length to left of y          */
      unsigned long     m;    /* min length                       */
      unsigned long     n;    /* max length                       */
      unsigned short    a;    /* number of alternations           */
      unsigned short    b;    /* number of backrefs               */
      unsigned short    c;    /* number of closures               */
      unsigned short    i;    /* number of negations              */
      unsigned short    p;    /* number of named subexpressions   */
      unsigned short    s;    /* number of simple closures        */
      unsigned short    t;    /* number of tries                  */
      unsigned short    u;    /* number of unnamed subexpressions */
      Rex_t*            x;    /* max length REX_STRING            */
      Rex_t*            y;    /* max length REX_TRIE              */
} Stats_t;

typedef struct Token_s
{
      unsigned long     min;
      unsigned long     max;
      short       lex;
      short       len;
      short       esc;
      short       att;
      short       push;
} Token_t;

typedef struct Cenv_s
{
      int         delimiter;  /* pattern delimiter          */
      int         error;            /* last error                 */
      int         explicit;   /* explicit match on this char      */
      int         mappeddot;  /* inverse mapped '.'         */
      int         mappednewline;    /* inverse mapped '\n'        */
      int         mappedslash;      /* inverse mapped '/'         */
      regflags_t  flags;            /* flags arg to regcomp       */
      int         type;       /* BRE,ERE,ARE,SRE,KRE        */
      unsigned char*    cursor;           /* curent point in re         */
      unsigned char*    pattern;    /* the original pattern       */
      unsigned char*    literal;    /* literal restart pattern    */
      int         parno;            /* number of last open paren  */
      int         parnest;    /* paren nest count           */
      int         posixkludge;      /* to make * nonspecial       */
      int         regexp;     /* <regexp.h> compatibility   */
      Token_t           token;            /* token lookahead            */
      Stats_t           stats;            /* RE statistics        */
      int         terminator; /* pattern terminator         */
      Rex_t*            paren[2*(BACK_REF_MAX+2)];
                              /* paren[i]!=0 if \i defined  */
      regex_t*    regex;            /* user handle                */
      regdisc_t*  disc;       /* user discipline            */
      unsigned char*    map;        /* external to native ccode map     */
      unsigned char*    MAP;        /* fold and/or map            */
} Cenv_t;

/*
 * allocate a new Rex_t node
 */

static Rex_t*
node(Cenv_t* env, int type, int lo, int hi, size_t extra)
{
      register Rex_t*   e;

      if (e = (Rex_t*)alloc(env->disc, 0, sizeof(Rex_t) + extra))
      {
            memset(e, 0, sizeof(Rex_t) + extra);
            e->type = type;
            e->marked = 0;
            e->lo = lo;
            e->hi = hi;
            e->flags = env->flags;
            e->map = (e->flags & REG_ICASE) ? env->MAP : env->map;
            e->explicit = env->explicit;
            if (extra)
                  e->re.data = (char*)e + sizeof(Rex_t);
      }
      return e;
}

/*
 * free a Trie_node_t node
 */

static void
triedrop(regdisc_t* disc, Trie_node_t* e)
{
      if (e)
      {
            triedrop(disc, e->son);
            triedrop(disc, e->sib);
            alloc(disc, e, 0);
      }
}

/*
 * free a Rex_t node
 */

void
drop(regdisc_t* disc, Rex_t* e)
{
      int   i;
      Rex_t*      x;

      if (e && !(disc->re_flags & REG_NOFREE))
            do
            {
                  switch (e->type)
                  {
                  case REX_ALT:
                  case REX_CONJ:
                        drop(disc, e->re.group.expr.binary.left);
                        drop(disc, e->re.group.expr.binary.right);
                        break;
                  case REX_GROUP:
                  case REX_GROUP_AHEAD:
                  case REX_GROUP_AHEAD_NOT:
                  case REX_GROUP_BEHIND:
                  case REX_GROUP_BEHIND_NOT:
                  case REX_GROUP_CUT:
                  case REX_NEG:
                  case REX_REP:
                        drop(disc, e->re.group.expr.rex);
                        break;
                  case REX_TRIE:
                        for (i = 0; i <= UCHAR_MAX; i++)
                              triedrop(disc, e->re.trie.root[i]);
                        break;
                  }
                  x = e->next;
                  alloc(disc, e, 0);
            } while (e = x);
}

/*
 * mark e and descendants minimal
 */

static void
mark(register Rex_t* e, int set)
{
      if (e && !e->marked)
            do
            {
                  e->marked = 1;
                  if (set)
                        e->flags |= REG_MINIMAL;
                  else
                        e->flags &= ~REG_MINIMAL;
                  switch (e->type)
                  {
                  case REX_ALT:
                  case REX_CONJ:
                  case REX_GROUP_COND:
                        if (e->re.group.expr.binary.left)
                              mark(e->re.group.expr.binary.left, set);
                        if (e->re.group.expr.binary.right)
                              mark(e->re.group.expr.binary.right, set);
                        break;
                  case REX_GROUP:
                  case REX_GROUP_AHEAD:
                  case REX_GROUP_AHEAD_NOT:
                  case REX_GROUP_BEHIND:
                  case REX_GROUP_BEHIND_NOT:
                  case REX_GROUP_CUT:
                  case REX_NEG:
                  case REX_REP:
                  case REX_TRIE:
                        mark(e->re.group.expr.rex, set);
                        break;
                  }
            } while (e = e->next);
}

/*
 * assign subexpression numbers by a preorder tree walk
 */

static int
serialize(Cenv_t* env, Rex_t* e, int n)
{
      do
      {
            e->serial = n++;
            switch (e->type)
            {
            case REX_ALT:
            case REX_GROUP_COND:
                  if (e->re.group.expr.binary.left)
                        n = serialize(env, e->re.group.expr.binary.left, n);
                  e->re.group.expr.binary.serial = n++;
                  if (e->re.group.expr.binary.right)
                        n = serialize(env, e->re.group.expr.binary.right, n);
                  break;
            case REX_CONJ:
                  n = serialize(env, e->re.group.expr.binary.left, n);
                  n = serialize(env, e->re.group.expr.binary.right, n);
                  break;
            case REX_GROUP:
            case REX_GROUP_AHEAD:
            case REX_GROUP_AHEAD_NOT:
            case REX_GROUP_BEHIND:
            case REX_GROUP_BEHIND_NOT:
            case REX_GROUP_CUT:
            case REX_NEG:
            case REX_REP:
                  n = serialize(env, e->re.group.expr.rex, n);
                  break;
            }
      } while (e = e->next);
      return n;
}

/*
 * catenate e and f into a sequence, collapsing them if possible
 */

static Rex_t*
cat(Cenv_t* env, Rex_t* e, Rex_t* f)
{
      Rex_t*      g;

      if (!f)
      {
            drop(env->disc, e);
            return 0;
      }
      if (e->type == REX_NULL)
      {
            drop(env->disc, e);
            return f;
      }
      if (f->type == REX_NULL)
      {
            g = f->next;
            f->next = 0;
            drop(env->disc, f);
            f = g;
      }
      else if (e->type == REX_DOT && f->type == REX_DOT)
      {
            unsigned int      m = e->lo + f->lo;
            unsigned int      n = e->hi + f->hi;

            if (m <= RE_DUP_MAX)
            {
                  if (e->hi > RE_DUP_MAX || f->hi > RE_DUP_MAX)
                  {
                        n = RE_DUP_INF;   
                        goto combine;
                  }
                  else if (n <= RE_DUP_MAX)
                  {
                  combine:
                        e->lo = m;
                        e->hi = n;
                        g = f->next;
                        f->next = 0;
                        drop(env->disc, f);
                        f = g;
                  }
            }
      }
      e->next = f;
      return e;
}

/*
 * collect re statistics
 */

static int
stats(register Cenv_t* env, register Rex_t* e)
{
      register unsigned long  n;
      register unsigned long  m;
      unsigned long           cm;
      unsigned long           nm;
      unsigned long           cn;
      unsigned long           nn;
      unsigned long           l;
      unsigned long           k;
      unsigned long           t;
      Rex_t*                  q;
      Rex_t*                  x;
      Rex_t*                  y;
      unsigned char           c;
      unsigned char           b;

      do
      {
            switch (e->type)
            {
            case REX_ALT:
                  x = env->stats.x;
                  l = env->stats.l;
                  y = env->stats.y;
                  k = env->stats.k;
                  t = env->stats.t;
                  if (++env->stats.a <= 0)
                        return 1;
                  cm = env->stats.m;
                  env->stats.m = 0;
                  cn = env->stats.n;
                  env->stats.n = 0;
                  if (stats(env, e->re.group.expr.binary.left))
                        return 1;
                  m = env->stats.m;
                  env->stats.m = 0;
                  n = env->stats.n;
                  env->stats.n = 0;
                  if (e->re.group.expr.binary.right && stats(env, e->re.group.expr.binary.right))
                        return 1;
                  if (env->stats.m > m)
                        env->stats.m = m;
                  else
                        m = env->stats.m;
                  if ((env->stats.m += cm) < m)
                        return 1;
                  if (env->stats.n < n)
                        env->stats.n = n;
                  else
                        n = env->stats.n;
                  if ((env->stats.n += cn) < n)
                        return 1;
                  env->stats.x = x;
                  env->stats.l = l;
                  env->stats.y = y;
                  env->stats.k = k;
                  env->stats.t = t;
                  break;
            case REX_BACK:
                  if (++env->stats.b <= 0)
                        return 1;
                  break;
            case REX_CLASS:
            case REX_COLL_CLASS:
            case REX_DOT:
            case REX_ONECHAR:
                  n = env->stats.m;
                  if ((env->stats.m += e->lo) < n)
                        return 1;
                  if (e->hi != RE_DUP_INF)
                  {
                        n = env->stats.n;
                        if ((env->stats.n += e->hi) < n)
                              return 1;
                  }
                  if (e->lo != e->hi)
                  {
                        if (++env->stats.c <= 0)
                              return 1;
                        if (++env->stats.s <= 0)
                              return 1;
                  }
                  break;
            case REX_CONJ:
                  cm = env->stats.m;
                  env->stats.m = 0;
                  cn = env->stats.n;
                  env->stats.n = 0;
                  if (stats(env, e->re.group.expr.binary.left))
                        return 1;
                  nm = env->stats.m;
                  env->stats.m = 0;
                  nn = env->stats.n;
                  env->stats.n = 0;
                  if (stats(env, e->re.group.expr.binary.right))
                        return 1;
                  if (env->stats.m < nm)
                        env->stats.m = nm;
                  else
                        nm = env->stats.m;
                  if ((env->stats.m += cm) < nm)
                        return 1;
                  if (env->stats.n < nn)
                        env->stats.n = nn;
                  else
                        nn = env->stats.n;
                  if ((env->stats.n += cn) < nn)
                        return 1;
                  break;
            case REX_GROUP:
                  if (e->re.group.number && ++env->stats.p <= 0 || !e->re.group.number && ++env->stats.u <= 0)
                        return 1;
                  if (stats(env, e->re.group.expr.rex))
                        return 1;
                  break;
            case REX_GROUP_AHEAD:
            case REX_GROUP_AHEAD_NOT:
            case REX_GROUP_BEHIND:
            case REX_GROUP_BEHIND_NOT:
                  m = env->stats.m;
                  n = env->stats.n;
                  x = env->stats.x;
                  y = env->stats.y;
                  if (stats(env, e->re.group.expr.rex))
                        return 1;
                  env->stats.m = m;
                  env->stats.n = n;
                  env->stats.x = x;
                  env->stats.y = y;
                  switch (e->type)
                  {
                  case REX_GROUP_AHEAD:
                  case REX_GROUP_BEHIND:
                        if (++env->stats.u <= 0)
                              return 1;
                        break;
                  }
                  break;
            case REX_GROUP_COND:
                  if (++env->stats.u <= 0)
                        return 1;
                  m = env->stats.m;
                  n = env->stats.n;
                  x = env->stats.x;
                  y = env->stats.y;
                  if (e->re.group.size > 0 && ++env->stats.b <= 0)
                        return 1;
                  if (e->re.group.expr.binary.left && stats(env, e->re.group.expr.binary.left))
                        return 1;
                  if (q = e->re.group.expr.binary.right)
                  {
                        if (q->re.group.expr.binary.left && stats(env, q->re.group.expr.binary.left))
                              return 1;
                        if (q->re.group.expr.binary.right && stats(env, q->re.group.expr.binary.right))
                              return 1;
                  }
                  env->stats.m = m;
                  env->stats.n = n;
                  env->stats.x = x;
                  env->stats.y = y;
                  break;
            case REX_GROUP_CUT:
                  if (++env->stats.u <= 0)
                        return 1;
                  m = env->stats.m;
                  n = env->stats.n;
                  x = env->stats.x;
                  y = env->stats.y;
                  if (stats(env, e->re.group.expr.rex))
                        return 1;
                  env->stats.m = m;
                  env->stats.n = n;
                  env->stats.x = x;
                  env->stats.y = y;
                  break;
            case REX_NEG:
                  env->stats.i++;
                  x = env->stats.x;
                  l = env->stats.l;
                  y = env->stats.y;
                  k = env->stats.k;
                  t = env->stats.t;
                  cm = env->stats.m;
                  env->stats.m = 0;
                  if (stats(env, e->re.group.expr.rex))
                        return 1;
                  env->stats.m = !env->stats.m;
                  if ((env->stats.m += cm) < cm)
                        return 1;
                  env->stats.x = x;
                  env->stats.l = l;
                  env->stats.y = y;
                  env->stats.k = k;
                  env->stats.t = t;
                  break;
            case REX_REP:
                  x = env->stats.x;
                  l = env->stats.l;
                  y = env->stats.y;
                  k = env->stats.k;
                  t = env->stats.t;
                  if (++env->stats.c <= 0)
                        return 1;
                  b = env->stats.b;
                  c = env->stats.c;
                  cm = env->stats.m;
                  env->stats.m = 0;
                  if (stats(env, e->re.group.expr.rex))
                        return 1;
                  if (env->stats.m == 1 && b == env->stats.b && c == env->stats.c && ++env->stats.s <= 0)
                        return 1;
                  if (e->lo < 1)
                  {
                        env->stats.x = x;
                        env->stats.l = l;
                        env->stats.y = y;
                        env->stats.k = k;
                        env->stats.t = t;
                        env->stats.m = cm;
                  }
                  else
                  {
                        m = env->stats.m;
                        if ((env->stats.m *= e->lo) > 0 && env->stats.m < m)
                              return 1;
                        m = env->stats.m;
                        if ((env->stats.m += cm) < m)
                              return 1;
                        if (env->stats.x != x)
                              env->stats.l = cm;
                        if (env->stats.y != y)
                              env->stats.k = cm;
                  }
                  break;
            case REX_STRING:
                  if (!e->map)
                  {
                        cm = env->stats.m;
                        if ((env->stats.m += e->re.string.size) < cm)
                              return 1;
                        cn = env->stats.n;
                        if ((env->stats.n += e->re.string.size) < cn)
                              return 1;
                        if (!env->stats.x || env->stats.x->re.string.size < e->re.string.size)
                        {
                              env->stats.x = e;
                              env->stats.l = cm;
                        }
                  }
                  break;
            case REX_TRIE:
                  if (++env->stats.s <= 0)
                        return 1;
                  cm = env->stats.m;
                  if ((env->stats.m += e->re.trie.min) < cm)
                        return 1;
                  cn = env->stats.n;
                  if ((env->stats.n += e->re.trie.max) < cn)
                        return 1;
                  env->stats.t++;
                  if (!env->stats.y || env->stats.y->re.trie.min < e->re.trie.min)
                  {
                        env->stats.y = e;
                        env->stats.k = cm;
                  }
                  break;
            }
      } while (e = e->next);
      return 0;
}

static int  token(Cenv_t*);

static int
magic(register Cenv_t* env, register int c, int escaped)
{
      register char*    sp;
      register int      n;
      int         o = c;
      int         e = env->error;
      int         l = env->token.len;
      short*            mp;
      char*       ep;

      if (mp = state.magic[c])
      {
            c = mp[env->type+escaped];
            if (c >= T_META)
            {
                  sp = (char*)env->cursor + env->token.len;
                  switch (c)
                  {
                  case T_LEFT:
                        n = 0;
                        ep = sp;
                        while (*sp >= '0' && *sp <= '9')
                        {
                              if (n > (INT_MAX / 10))
                              {
                                    env->error = REG_BADBR;
                                    goto bad;
                              }
                              n = n * 10 + *sp++ - '0';
                        }
                        if (sp == ep)
                        {
                              if (env->type < SRE || *sp != ',')
                              {
                                    env->error = *sp ? REG_BADBR : REG_EBRACE;
                                    goto bad;
                              }
                        }
                        else if (n > RE_DUP_MAX)
                        {
                              env->error = REG_BADBR;
                              goto bad;
                        }
                        env->token.min = n;
                        if (*sp == ',')
                        {
                              n = 0;
                              ep = ++sp;
                              while (*sp >= '0' && *sp <= '9')
                              {
                                    if (n > (INT_MAX / 10))
                                    {
                                          env->error = REG_BADBR;
                                          goto bad;
                                    }
                                    n = n * 10 + *sp++ - '0';
                              }
                              if (sp == ep)
                                    n = RE_DUP_INF;
                              else if (n < env->token.min)
                              {
                                    env->error = REG_BADBR;
                                    goto bad;
                              }
                        }
                        env->token.max = n;
                        switch (*sp)
                        {
                        case 0:
                              env->error = REG_EBRACE;
                              goto bad;
                        case '\\':
                              if (!escaped)
                              {
                                    env->error = REG_BADBR;
                                    goto bad;
                              }
                              sp++;
                              break;
                        default:
                              if (escaped)
                              {
                                    env->error = REG_BADBR;
                                    goto bad;
                              }
                              break;
                        }
                        switch (*sp++)
                        {
                        case 0:
                              env->error = REG_EBRACE;
                              goto bad;
                        case '}':
                              break;
                        default:
                              env->error = REG_BADBR;
                              goto bad;
                        }
                        env->token.len = sp - (char*)env->cursor;
                        break;
                  case T_RIGHT:
                        env->error = REG_EBRACE;
                        goto bad;
                  case T_OPEN:
                        if (env->type < SRE && *sp == '?')
                        {
                              env->token.len++;
                              env->token.lex = 0;
                              goto group;
                        }
                        break;
                  case T_ESCAPE:
                        c = chresc(sp - 2, &ep);
                        if (ep < sp)
                              goto bad;
                        env->token.len += ep - sp;
                        if (c >= T_META)
                        {
                              env->token.lex = c;
                              c = C_ESC;
                        }
                        return c;
                  case T_BACK+0:
                  case T_BACK+1:
                  case T_BACK+2:
                  case T_BACK+3:
                  case T_BACK+4:
                  case T_BACK+5:
                  case T_BACK+6:
                  case T_BACK+7:
                        n = chresc(sp - 2, &ep);
                        if (ep > sp + 1)
                        {
                              env->token.len += ep - sp;
                              return n;
                        }
                        /*FALLTHROUGH*/
                  case T_BACK+8:
                  case T_BACK+9:
                        if (env->type == SRE || c == T_BACK && !(env->flags & REG_LENIENT))
                        {
                              env->error = REG_BADESC;
                              goto bad;
                        }
                        if ((env->flags & REG_MULTIREF) && isdigit(*sp))
                        {
                              c = (c - T_BACK) * 10 + (*sp - '0');
                              if (c > 0 && c <= env->parno && env->paren[c])
                                    c += T_BACK;
                              else
                                    c = chresc(sp - 2, &ep);
                              env->token.len++;
                        }
                        if (c == T_BACK)
                              c = 0;
                        break;
                  case T_BAD:
                        if (escaped == 1 && (env->flags & REG_LENIENT) && (c = mp[env->type+escaped+2]) >= T_META)
                              return c;
                        goto bad;
                  }
                  if (env->type >= SRE)
                  {
                        if (c == T_DOT)
                              c = '.';
                        else if (c < T_OPEN)
                        {
                              if (env->type == KRE && *(env->cursor + env->token.len) == '-' && *(env->cursor + env->token.len + 1) == '(')
                              {
                                    env->token.len++;
                                    env->token.att = 1;
                              }
                              if (env->type == KRE && *(env->cursor + env->token.len) == '(')
                              {
                                    env->token.len++;
                                    switch (c)
                                    {
                                    case T_AT:
                                          break;
                                    case T_PERCENT:
                                          env->token.lex = c;
                                          goto group;
                                    case T_TILDE:
                                          env->token.lex = 0;
                                          goto group;
                                    default:
                                          env->token.lex = c;
                                          break;
                                    }
                                    c = T_OPEN;
                              }
                              else if (c == T_STAR)
                                    c = T_DOTSTAR;
                              else if (c == T_QUES)
                                    c = T_DOT;
                              else
                              {
                                    c = o;
                                    env->token.len = l;
                              }
                        }
                        else if (c > T_BACK)
                        {
                              c = (c - T_BACK) * 2 - 1;
                              c = (c > env->parno || !env->paren[c]) ? o : T_BACK + c;
                        }
                        else if (env->type == KRE && !env->parnest && (env->flags & REG_SHELL_GROUP))
                        {
                              if (c == T_AND)
                                    c = '&';
                              else if (c == T_BAR)
                                    c = '|';
                              else if (c == T_OPEN)
                                    c = '(';
                        }
                  }
            }
      }
      else if (escaped == 2)
      {
            if (env->type >= SRE && !(env->flags & REG_SHELL_ESCAPED) || (env->flags & REG_ESCAPE) && (c == '[' || c == '-' || c == ']' || env->delimiter && c == env->delimiter))
                  /*ok*/;
            else
            {
                  env->error = REG_BADESC;
                  goto bad;
            }
      }
      else if (escaped && !(env->flags & REG_LENIENT) && c != ']')
      {
            env->error = REG_BADESC;
            goto bad;
      }
      return c;
 group:
      sp = (char*)env->cursor + env->token.len;
      switch (*sp++)
      {
      case ')':
            break;
      case '#':
            for (;;)
            {
                  switch (*sp++)
                  {
                  case 0:
                        env->error = REG_EPAREN;
                        return T_BAD;
                  case ')':
                        break;
                  default:
                        continue;
                  }
                  break;
            }
            break;
      default:
            return T_GROUP;
      }
      env->cursor = (unsigned char*)sp;
      return token(env);
 bad:
      if (escaped == 2)
            env->error = e;
      else if (env->flags & REG_LENIENT)
            return o;
      else if (escaped == 1 && !env->error)
      {
            if (mp || o == ']')
                  return o;
            env->error = REG_BADESC;
      }
      return T_BAD;
}

static int
token(register Cenv_t* env)
{
      int   c;
      int   posixkludge;

      if (env->token.push)
            return env->token.lex;
      env->token.att = env->token.esc = 0;
      if ((env->token.len = MBSIZE(env->cursor)) > 1)
            return env->token.lex = C_MB;
      env->token.lex = 0;
      for (;;)
      {
            c = *env->cursor;
            if (c == 0 || c == env->delimiter || c == env->terminator)
                  return T_END;
            if (!(env->flags & REG_COMMENT))
                  break;
            if (c == '#')
            {
                  do
                  {
                        c = *++env->cursor;
                        if (c == 0 || c == env->delimiter)
                              return T_END;
                  } while (c != '\n');
            }
            else if (!isspace(c))
                  break;
            env->cursor++;
      }
      if (c == '\n' && (env->flags & REG_MULTIPLE) && !env->delimiter)
      {
            if (env->parnest)
            {
                  env->error = REG_EPAREN;
                  return T_BAD;
            }
            env->parno = 0;
            env->pattern = env->cursor + 1;
            return T_BAR;
      }
      if (env->flags & REG_LITERAL)
            return c;
      if (posixkludge = env->posixkludge)
      {
            env->posixkludge = 0;
            if (c == '*')
                  return c;
      }
      if (c == '\\')
      {
            if (env->flags & REG_SHELL_ESCAPED)
                  return c;
            if (!(c = *(env->cursor + 1)) || c == env->terminator)
            {
                  if (env->flags & REG_LENIENT)
                  {
                        if (c)
                        {
                              env->token.esc = env->token.len;
                              env->token.len += MBSIZE(env->cursor + 1);
                              return c;
                        }
                        return '\\';
                  }
                  env->error = REG_EESCAPE;
                  return T_BAD;
            }
            env->token.esc = env->token.len;
            env->token.len += MBSIZE(env->cursor + 1);
            if (env->delimiter && c == 'n')
                  return '\n';
            else if (c == env->delimiter)
                  return magic(env, c, 0);
            else if (c == '(' && env->type == BRE)
                  env->posixkludge = 1;
            else if (c == ')' && env->type == BRE && env->parnest <= 0)
            {
                  env->error = REG_EPAREN;
                  return T_BAD;
            }
            else if (isspace(c) && (env->flags & REG_COMMENT))
                  return c;
            return magic(env, c, 1);
      }
      else if (c == '$')
      {
            if (env->type == BRE && (*(env->cursor + 1) == 0 || *(env->cursor + 1) == env->delimiter || *(env->cursor + 1) == env->terminator || *(env->cursor + 1) == '\\' && *(env->cursor + 2) == ')') || (env->flags & REG_MULTIPLE) && *(env->cursor + 1) == '\n')
                  return T_DOLL;
      }
      else if (c == '^')
      {
            if (env->type == BRE && (env->cursor == env->pattern || posixkludge))
            {
                  env->posixkludge = 1;
                  return T_CFLX;
            }
      }
      else if (c == ')')
      {
            if (env->type != BRE && env->parnest <= 0)
                  return c;
      }
      else if (c == '/' && env->explicit == env->mappedslash)
      {
            while (*(env->cursor + env->token.len) == c)
                  env->token.len++;
            return T_SLASHPLUS;
      }
      return magic(env, c, 0);
}

static Celt_t*
col(Celt_t* ce, int ic, unsigned char* bp, int bw, int bc, unsigned char* ep, int ew, int ec)
{
      register char*          s;
      register unsigned char* k;
      register unsigned char* e;
      register int            c;
      register int            cc;
      int               bt;
      int               et;
      Ckey_t                  key;

      cc = 0;
      for (;;)
      {
            k = key;
            if (bw == 1)
            {
                  c = bc;
                  if (ic)
                  {
                        if (isupper(c))
                        {
                              c = tolower(c);
                              cc = -1;
                        }
                        else if (islower(c))
                        {
                              c = toupper(c);
                              cc = -1;
                        }
                  }
                  *k++ = c;
            }
            else if (bw < COLL_KEY_MAX)
            {
                  s = (char*)bp;
                  if (ic)
                  {
                        c = mbchar(s);
                        if (iswupper(c))
                        {
                              c = towlower(c);
                              cc = 1;
                        }
                        else if (iswlower(c))
                        {
                              c = towupper(c);
                              cc = 1;
                        }
                  }
                  if (cc > 0)
                  {
                        cc = -1;
                        k += wctomb((char*)k, c);
                  }
                  else
                        for (e = k + bw; k < e; *k++ = *s++);
            }
            *k = 0;
            mbxfrm(ce->beg, key, COLL_KEY_MAX);
            if (ep)
            {
                  k = key;
                  c = mbchar(k);
                  if (iswupper(c))
                        bt = COLL_range_uc;
                  else if (iswlower(c))
                        bt = COLL_range_lc;
                  else
                        bt = COLL_range;
                  k = key;
                  if (ew == 1)
                  {
                        c = ec;
                        if (ic)
                        {
                              if (isupper(c))
                              {
                                    c = tolower(c);
                                    cc = -1;
                              }
                              else if (islower(c))
                              {
                                    c = toupper(c);
                                    cc = -1;
                              }
                        }
                        *k++ = c;
                  }
                  else if (ew < COLL_KEY_MAX)
                  {
                        s = (char*)ep;
                        if (ic)
                        {
                              c = mbchar(s);
                              if (iswupper(c))
                              {
                                    c = towlower(c);
                                    cc = 1;
                              }
                              else if (iswlower(c))
                              {
                                    c = towupper(c);
                                    cc = 1;
                              }
                        }
                        if (cc > 0)
                        {
                              cc = -1;
                              k += wctomb((char*)k, c);
                        }
                        else
                              for (e = k + ew; k < e; *k++ = *s++);
                  }
                  *k = 0;
                  mbxfrm(ce->end, key, COLL_KEY_MAX);
                  k = key;
                  c = mbchar(k);
                  if (iswupper(c))
                        et = COLL_range_uc;
                  else if (iswlower(c))
                        et = COLL_range_lc;
                  else
                        et = COLL_range;
                  ce->typ = bt == et ? bt : COLL_range;
            }
            else
                  ce->typ = COLL_char;
            ce++;
            if (!ic || !cc)
                  break;
            ic = 0;
      }
      return ce;
}

static Rex_t*
bra(Cenv_t* env)
{
      Rex_t*            e;
      int         c;
      int         i;
      int         w;
      int         neg;
      int         last;
      int         inrange;
      int         complicated;
      int         collate;
      int         elements;
      unsigned char*    first;
      unsigned char*    start;
      unsigned char*    begin;
      unsigned char*    s;
      regclass_t  f;
      unsigned char     buf[4 * (COLL_KEY_MAX + 1)];
#if _PACKAGE_ast
      int         ic;
      char        mbc[COLL_KEY_MAX + 1];
#endif

      if (!(e = node(env, REX_CLASS, 1, 1, sizeof(Set_t))))
            return 0;
      collate = complicated = elements = 0;
      if (*env->cursor == '^' || env->type >= SRE && *env->cursor == '!')
      {
            env->cursor++;
            neg = 1;
      }
      else
            neg = 0;
      first = env->cursor;
      start = first + MBSIZE(first);
      if (*env->cursor == 0 || *(env->cursor + 1) == 0 || *env->cursor == env->terminator || *(env->cursor + 1) == env->terminator || (env->flags & REG_ESCAPE) && (*env->cursor == env->delimiter || *env->cursor != '\\' && *(env->cursor + 1) == env->delimiter))
            goto error;
      begin = env->cursor + MBSIZE(env->cursor);

      /*
       * inrange: 0=no, 1=possibly, 2=definitely
       */

      inrange = 0;
      for (;;)
      {
            if (!(c = *env->cursor) || c == env->terminator || (env->flags & REG_ESCAPE) && c == env->delimiter)
                  goto error;
            env->cursor += (w = MBSIZE(env->cursor));
            if (c == '\\')
            {
                  if (*env->cursor)
                  {
                        if (*env->cursor == 'n')
                        {
                              env->cursor++;
                              c = '\n';
                        }
                        else if (env->type < SRE || !(env->flags & REG_SHELL_ESCAPED))
                        {
                              env->token.len = 1;
                              w = magic(env, *env->cursor, 2);
                              if (env->token.len > 1 || w != T_BAD)
                              {
                                    if (env->token.len == 1 && (f = classfun(w)))
                                    {
                                          if (inrange > 1)
                                          {
                                                if (env->type < SRE && !(env->flags & REG_LENIENT))
                                                      goto erange;
                                                inrange = 0;
                                          }
                                          env->cursor++;
                                          for (c = 0; c <= UCHAR_MAX; c++)
                                                if ((*f)(c))
                                                      setadd(e->re.charclass, c);
                                          complicated++;
                                          elements++;
                                          continue;
                                    }
                                    if (env->token.len > 1 || w >= 0 && w < T_META)
                                    {
                                          c = w;
                                          if (c > UCHAR_MAX)
                                          {
                                                if (env->type < SRE && !(env->flags & REG_LENIENT) && !mbwide())
                                                      goto erange;
                                                c = UCHAR_MAX;
                                          }
                                          env->cursor += env->token.len;
                                    }
                              }
                        }
                  }
            }
            else if (c == ']')
            {
                  if (env->cursor == begin)
                  {
                        last = c;
                        inrange = 1;
                        continue;
                  }
                  if (inrange != 0)
                  {
                        setadd(e->re.charclass, last);
                        elements++;
                        if (inrange == 2)
                        {
                              setadd(e->re.charclass, '-');
                              elements++;
                        }
                  }
                  break;
            }
            else if (c == '-')
            {
                  if (!inrange && env->cursor != begin && *env->cursor != ']')
                  {
                        if (env->type < SRE && !(env->flags & REG_LENIENT))
                              goto erange;
                        continue;
                  }
                  else if (inrange == 1)
                  {
                        inrange = 2;
                        complicated++;
                        continue;
                  }
            }
            else if (c == '[')
            {
                  switch (*env->cursor)
                  {
                  case 0:
                        goto error;
                  case ':':
                        if (env->regexp)
                              goto normal;
                        if (inrange == 1)
                        {
                              setadd(e->re.charclass, last);
                              elements++;
                        }
                        if (!(f = regclass((char*)env->cursor, (char**)&env->cursor)))
                        {
                              if (env->cursor == start && (c = *(env->cursor + 1)))
                              {
                                    s = start = env->cursor + 1;
                                    while (*++s && *s != ':');
                                    if (*s == ':' && *(s + 1) == ']' && *(s + 2) == ']')
                                    {
                                          if ((i = (s - start)) == 1)
                                          {
                                                switch (c)
                                                {
                                                case '<':
                                                      i = REX_WBEG;
                                                      break;
                                                case '>':
                                                      i = REX_WEND;
                                                      break;
                                                default:
                                                      i = 0;
                                                      break;
                                                }
                                                if (i)
                                                {
                                                      env->cursor = s + 3;
                                                      drop(env->disc, e);
                                                      return node(env, i, 0, 0, 0);
                                                }
                                          }
                                    }
                              }
                              env->error = REG_ECTYPE;
                              goto error;
                        }
                        for (c = 0; c <= UCHAR_MAX; c++)
                              if ((*f)(c))
                                    setadd(e->re.charclass, c);
                        inrange = 0;
                        complicated++;
                        elements++;
                        continue;
                  case '=':
                        if (env->regexp)
                              goto normal;
                        if (inrange == 2)
                              goto erange;
                        if (inrange == 1)
                        {
                              setadd(e->re.charclass, last);
                              elements++;
                        }
                        if ((c = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)buf, sizeof(buf))) < 0)
                              goto ecollate;
                        if (c > 1)
                              collate++;
                        else
                              setadd(e->re.charclass, buf[0]);
                        c = buf[0];
                        inrange = 0;
                        complicated++;
                        elements++;
                        continue;
                  case '.':
                        if (env->regexp)
                              goto normal;
                        if ((c = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)buf, sizeof(buf))) < 0)
                              goto ecollate;
                        if (c > 1)
                              collate++;
                        c = buf[0];
                        complicated++;
                        break;
                  default:
                  normal:
                        if (*env->cursor == env->terminator || *env->cursor == env->delimiter && (env->flags & REG_ESCAPE))
                              goto error;
                        break;
                  }
            }
            else if (w > 1)
                  complicated++;
            if (inrange == 2)
            {
                  if (last > c)
                  {
                        if (env->type < SRE && !(env->flags & REG_LENIENT))
                              goto erange;
                        setadd(e->re.charclass, last);
                        setadd(e->re.charclass, c);
                  }
                  else
                        for (i = last; i <= c; i++)
                              setadd(e->re.charclass, i);
                  inrange = env->type >= SRE || (env->flags & REG_LENIENT);
                  elements += 2;
            }
            else if (inrange == 1)
            {
                  setadd(e->re.charclass, last);
                  elements++;
            }
            else
                  inrange = 1;
            last = c;
      }
#if _PACKAGE_ast
      if (complicated && mbcoll())
      {
            Dt_t*             dt;
            Cchr_t*                 cc;
            Cchr_t*                 tc;
            Cchr_t*                 xc;
            Celt_t*                 ce;
            Cchr_t                  key;
            int               rw;
            int               rc;
            int               wc;
            unsigned char*          rp;
            unsigned char*          pp;
            char*             wp;
            char              cb[2][COLL_KEY_MAX+1];

            static Dtdisc_t         disc;

            static const char primary[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

            if (!(dt = (Dt_t*)LCINFO(AST_LC_COLLATE)->data))
            {
                  disc.key = offsetof(Cchr_t, key);
                  if ((cc = newof(0, Cchr_t, elementsof(primary), 0)) && (dt = dtopen(&disc, Dttree)))
                  {
                        for (i = 0; i < elementsof(primary) - 1; i++, cc++)
                        {
                              cc->nam[0] = primary[i];
                              mbxfrm(cc->key, cc->nam, COLL_KEY_MAX);
                              dtinsert(dt, cc);
                        }
                        for (i = 0; i < elementsof(cc->key); i++)
                              cc->key[i] = ~0;
                        dtinsert(dt, cc);
                        LCINFO(AST_LC_COLLATE)->data = (void*)dt;
                  }
                  else
                  {
                        if (cc)
                              free(cc);
                        drop(env->disc, e);
                        return 0;
                  }
            }
            if (dt)
            {
                  drop(env->disc, e);
                  if (ic = env->flags & REG_ICASE)
                        elements *= 2;
                  if (!(e = node(env, REX_COLL_CLASS, 1, 1, (elements + 2) * sizeof(Celt_t))))
                        return 0;
                  ce = (Celt_t*)e->re.data;
                  e->re.collate.invert = neg;
                  e->re.collate.elements = ce;
                  env->cursor = first;
                  inrange = 0;
                  for (;;)
                  {
                        if ((c = *env->cursor) == 0 || c == env->terminator || (env->flags & REG_ESCAPE) && c == env->delimiter)
                              goto error;
                        pp = env->cursor;
                        env->cursor += (w = MBSIZE(env->cursor));
                        if (c == '\\')
                        {
                              if (*env->cursor)
                              {
                                    if (*env->cursor == 'n')
                                    {
                                          pp = env->cursor++;
                                          c = '\n';
                                    }
                                    else if (env->type < SRE || !(env->flags & REG_SHELL_ESCAPED))
                                    {
                                          env->token.len = 1;
                                          w = magic(env, *env->cursor, 2);
                                          if (env->token.len > 1 || w != T_BAD)
                                          {
                                                if (env->token.len == 1 && (f = classfun(w)))
                                                {
                                                      if (inrange > 1)
                                                      {
                                                            if (env->type < SRE && !(env->flags & REG_LENIENT))
                                                                  goto erange;
                                                            inrange = 0;
                                                      }
                                                      env->cursor++;
                                                      ce->fun = f;
                                                      ce->typ = COLL_call;
                                                      ce++;
                                                      continue;
                                                }
                                                if (env->token.len > 1 || w >= 0 && w < T_META)
                                                {
                                                      c = w;
                                                      w = wctomb(mbc, c);
                                                      pp = (unsigned char*)mbc;
                                                      env->cursor += env->token.len;
                                                }
                                          }
                                    }
                              }
                        }
                        else if (c == ']')
                        {
                              if (env->cursor == begin)
                              {
                                    rp = pp;
                                    rw = w;
                                    inrange = 1;
                                    continue;
                              }
                              if (inrange != 0)
                              {
                                    ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
                                    if (inrange == 2)
                                          ce = col(ce, ic, NiL, 1, '-', NiL, 0, 0);
                              }
                              break;
                        }
                        else if (c == '-')
                        {
                              if (!inrange && env->cursor != begin && *env->cursor != ']')
                              {
                                    if (env->type < SRE && !(env->flags & REG_LENIENT))
                                          goto erange;
                                    continue;
                              }
                              else if (inrange == 1)
                              {
                                    inrange = 2;
                                    continue;
                              }
                        }
                        else if (c == '[')
                        {
                              switch (*env->cursor)
                              {
                              case 0:
                                    goto error;
                              case ':':
                                    if (env->regexp)
                                          goto complicated_normal;
                                    if (inrange == 1)
                                          ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
                                    if (!(f = regclass((char*)env->cursor, (char**)&env->cursor)))
                                    {
                                          if (env->cursor == start && (c = *(env->cursor + 1)) && *(env->cursor + 2) == ':' && *(env->cursor + 3) == ']' && *(env->cursor + 4) == ']')
                                          {
                                                switch (c)
                                                {
                                                case '<':
                                                      i = REX_WBEG;
                                                      break;
                                                case '>':
                                                      i = REX_WEND;
                                                      break;
                                                default:
                                                      i = 0;
                                                      break;
                                                }
                                                if (i)
                                                {
                                                      env->cursor += 5;
                                                      drop(env->disc, e);
                                                      return node(env, i, 0, 0, 0);
                                                }
                                          }
                                          env->error = REG_ECTYPE;
                                          goto error;
                                    }
                                    ce->fun = f;
                                    ce->typ = COLL_call;
                                    ce++;
                                    inrange = 0;
                                    continue;
                              case '=':
                                    if (env->regexp)
                                          goto complicated_normal;
                                    if (inrange == 2)
                                          goto erange;
                                    if (inrange == 1)
                                          ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
                                    pp = (unsigned char*)cb[inrange];
                                    rp = env->cursor + 1;
                                    if ((rw = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)pp, COLL_KEY_MAX)) < 0)
                                          goto ecollate;
                                    wp = (char*)pp;
                                    wc = mbchar(wp);
                                    c = 0;
                                    if (ic)
                                    {
                                          if (iswupper(wc))
                                          {
                                                wc = towlower(wc);
                                                rw = wctomb((char*)pp, wc);
                                                c = 'u';
                                          }
                                          else if (iswlower(wc))
                                                c = 'l';
                                    }
                                    for (;;)
                                    {
                                          mbxfrm(key.key, (char*)pp, COLL_KEY_MAX);
                                          if (!(cc = (Cchr_t*)dtsearch(dt, &key)) && !(cc = (Cchr_t*)dtprev(dt, &key)))
                                                goto ecollate;
                                          xc = (tc = (Cchr_t*)dtprev(dt, cc)) && !strcasecmp((char*)tc->nam, (char*)cc->nam) ? tc : cc;
                                          if (c == 'l' || c == 'L' && !(c = 0))
                                                ce->typ = COLL_range_lc;
                                          else if (c == 'u' || c == 'U' && !(c = 0))
                                                ce->typ = COLL_range_uc;
                                          else
                                                ce->typ = COLL_range;
                                          strcpy((char*)ce->beg, (char*)xc->key);
                                          if (!(cc = (Cchr_t*)dtnext(dt, cc)))
                                                goto ecollate;
                                          if (!strcasecmp((char*)xc->nam, (char*)cc->nam) && (tc = (Cchr_t*)dtnext(dt, cc)))
                                                cc = tc;
                                          strcpy((char*)ce->end, (char*)cc->key);
                                          ce->max = -1;
                                          ce++;
                                          if (!c)
                                                break;
                                          if (c == 'u')
                                          {
                                                wc = towlower(wc);
                                                c = 'L';
                                          }
                                          else
                                          {
                                                wc = towupper(wc);
                                                c = 'U';
                                          }
                                          rw = wctomb((char*)pp, wc);
                                    }
                                    inrange = 0;
                                    c = *pp;
                                    continue;
                              case '.':
                                    if (env->regexp)
                                          goto complicated_normal;
                                    pp = (unsigned char*)cb[inrange];
                                    if ((w = regcollate((char*)env->cursor, (char**)&env->cursor, (char*)pp, COLL_KEY_MAX)) < 0)
                                          goto ecollate;
                                    c = buf[0];
                                    break;
                              default:
                              complicated_normal:
                                    if (*env->cursor == env->terminator || *env->cursor == env->delimiter && (env->flags & REG_ESCAPE))
                                          goto error;
                                    break;
                              }
                        }
                        if (inrange == 2)
                        {
                              ce = col(ce, ic, rp, rw, rc, pp, w, c);
                              if (strcmp((char*)ce->beg, (char*)ce->end) > 0)
                              {
                                    if (env->type < SRE && !(env->flags & REG_LENIENT))
                                          goto erange;
                                    (ce-1)->typ = COLL_char;
                                    strcpy((char*)ce->beg, (char*)(ce-1)->end);
                                    ce->typ = COLL_char;
                                    ce++;
                              }
                              inrange = env->type >= SRE || (env->flags & REG_LENIENT);
                        }
                        else if (inrange == 1)
                              ce = col(ce, ic, rp, rw, rc, NiL, 0, 0);
                        else
                              inrange = 1;
                        rp = pp;
                        rw = w;
                        rc = c;
                  }
                  ce->typ = COLL_end;
                  return e;
            }
      }
#endif
      if (collate)
            goto ecollate;
      if (env->flags & REG_ICASE)
            for (i = 0; i <= UCHAR_MAX; i++)
                  if (settst(e->re.charclass, i))
                  {
                        if (isupper(i))
                              c = tolower(i);
                        else if (islower(i))
                              c = toupper(i);
                        else
                              continue;
                        setadd(e->re.charclass, c);
                  }
      if (neg)
      {
            for (i = 0; i < elementsof(e->re.charclass->bits); i++)
                  e->re.charclass->bits[i] ^= ~0;
            if (env->explicit >= 0)
                  setclr(e->re.charclass, env->explicit);
      }
      return e;
 ecollate:
      env->error = REG_ECOLLATE;
      goto error;
 erange:
      env->error = REG_ERANGE;
 error:
      drop(env->disc, e);
      if (!env->error)
            env->error = REG_EBRACK;
      return 0;
}

static Rex_t*
ccl(Cenv_t* env, int type)
{
      int         i;
      Rex_t*            e;
      Celt_t*           ce;
      regclass_t  f;

      if (!(f = classfun(type)))
      {
            env->error = REG_BADESC;
            return 0;
      }
      if (!mbcoll())
      {
            if (!(e = node(env, REX_CLASS, 1, 1, sizeof(Set_t))))
                  return 0;
            for (i = 0; i <= UCHAR_MAX; i++)
                  if ((*f)(i))
                        setadd(e->re.charclass, i);
            if (env->explicit >= 0)
                  setclr(e->re.charclass, env->explicit);
      }
      else
      {
            if (!(e = node(env, REX_COLL_CLASS, 1, 1, 2 * sizeof(Celt_t))))
                  return 0;
            ce = (Celt_t*)e->re.data;
            e->re.collate.invert = 0;
            e->re.collate.elements = ce;
            ce->fun = f;
            ce->typ = COLL_call;
            ce++;
            ce->typ = COLL_end;
      }
      return e;
}

static Rex_t*
rep(Cenv_t* env, Rex_t* e, int number, int last)
{
      Rex_t*            f;
      unsigned long     m = 0;
      unsigned long     n = RE_DUP_INF;
      int         minimal = -1;

      if (!e)
            return 0;
      switch (token(env))
      {
      case T_BANG:
            eat(env);
            if (!(f = node(env, REX_NEG, m, n, 0)))
            {
                  drop(env->disc, e);
                  return 0;
            }
            f->re.group.expr.rex = e;
            return f;
      case T_QUES:
            eat(env);
            n = 1;
            break;
      case T_STAR:
            eat(env);
            break;
      case T_PLUS:
            eat(env);
            m = 1;
            break;
      case T_LEFT:
            eat(env);
            m = env->token.min;
            n = env->token.max;
            break;
      default:
            return e;
      }
      if (env->token.att)
            minimal = 1;
      else if (env->type < SRE)
            switch (token(env))
            {
            case T_QUES:
                  eat(env);
                  minimal = !(env->flags & REG_MINIMAL);
                  break;
            case T_STAR: /*AST*/
                  eat(env);
                  minimal = !!(env->flags & REG_MINIMAL);
                  break;
            }
      switch (e->type)
      {
      case REX_DOT:
      case REX_CLASS:
      case REX_COLL_CLASS:
      case REX_ONECHAR:
            e->lo = m;
            e->hi = n;
            if (minimal >= 0)
                  mark(e, minimal);
            return e;
#if HUH_2002_08_07
      case REX_BEG:
#endif
      case REX_BEG_STR:
      case REX_END_STR:
      case REX_FIN_STR:
      case REX_WBEG:
      case REX_WEND:
      case REX_WORD:
      case REX_WORD_NOT:
            env->error = REG_BADRPT;
            drop(env->disc, e);
            return 0;
      }
      if (m == 1 && n == 1)
      {
            if (minimal >= 0)
                  mark(e, minimal);
            return e;
      }
      if (!(f = node(env, REX_REP, m, n, 0)))
      {
            drop(env->disc, e);
            return 0;
      }
      f->re.group.expr.rex = e;
      f->re.group.number = number;
      f->re.group.last = last;
      if (minimal >= 0)
            mark(f, minimal);
      if (m <= n && n)
      {
            for (; e && e->type >= REX_GROUP && e->type <= REX_GROUP_CUT; e = e->re.group.expr.rex);
            if (e && e->type == REX_NEG)
                  f->type = REX_GROUP;
      }
      return f;
}

static int
isstring(Rex_t* e)
{
      switch (e->type)
      {
      case REX_ONECHAR:
            return e->lo == 1 && e->hi == 1;
      case REX_STRING:
            return 1;
      }
      return 0;
}

static Trie_node_t*
trienode(Cenv_t* env, int c)
{
      Trie_node_t*      t;

      if (t = (Trie_node_t*)alloc(env->disc, 0, sizeof(Trie_node_t)))
      {
            memset(t, 0, sizeof(Trie_node_t));
            t->c = c;
      }
      return t;
}

static int
insert(Cenv_t* env, Rex_t* f, Rex_t* g)
{
      unsigned char*    s;
      unsigned char*    e;
      Trie_node_t*      t;
      int         len;
      unsigned char     tmp[2];

      switch (f->type)
      {
      case REX_ONECHAR:
            *(s = tmp) = f->re.onechar;
            e = s + 1;
            break;
      case REX_STRING:
            s = f->re.string.base;
            e = s + f->re.string.size;
            break;
      default:
            return 1;
      }
      if (!(t = g->re.trie.root[*s]) && !(t = g->re.trie.root[*s] = trienode(env, *s)))
            return 1;
      for (len = 1;;)
      {
            if (t->c == *s)
            {
                  if (++s >= e)
                        break;
                  if (!t->son && !(t->son = trienode(env, *s)))
                        return 1;
                  t = t->son;
                  len++;
            }
            else
            {
                  if (!t->sib && !(t->sib = trienode(env, *s)))
                        return 1;
                  t = t->sib;
            }
      }
      if (g->re.trie.min > len)
            g->re.trie.min = len;
      if (g->re.trie.max < len)
            g->re.trie.max = len;
      t->end = 1;
      return 0;
}

/*
 * trie() tries to combine nontrivial e and f into a REX_TRIE
 * unless 0 is returned, e and f are deleted as far as possible
 * also called by regcomb
 */

static Rex_t*
trie(Cenv_t* env, Rex_t* e, Rex_t* f)
{
      Rex_t*      g;

      if (e->next || f->next || !isstring(e) || e->flags != f->flags)
            return 0;
      if (isstring(f))
      {
            if (!(g = node(env, REX_TRIE, 0, 0, (UCHAR_MAX + 1) * sizeof(Trie_node_t*))))
                  return 0;
            g->re.trie.min = INT_MAX;
            if (insert(env, f, g))
                  goto nospace;
            drop(env->disc, f);
      }
      else if (f->type != REX_TRIE)
            return 0;
      else
            g = f;
      if (insert(env, e, g))
            goto nospace;
      drop(env->disc, e);
      return g;
 nospace:
      if (g != f)
            drop(env->disc, g);
      return 0;
}

static Rex_t*           alt(Cenv_t*, int, int);

static int
chr(register Cenv_t* env, int* escaped)
{
      unsigned char*    p;
      int         c;

      *escaped = 0;
      if (!(c = *env->cursor))
            return -1;
      env->cursor++;
      if (c == '\\')
      {
            if (env->flags & REG_SHELL_ESCAPED)
                  return c;
            if (!(c = *(env->cursor + 1)) || c == env->terminator)
            {
                  if (env->flags & REG_LENIENT)
                        return c ? c : '\\';
                  env->error = REG_EESCAPE;
                  return -1;
            }
            p = env->cursor;
            c = chresc((char*)env->cursor - 1, (char**)&env->cursor);
            *escaped = env->cursor - p;
      }
      return c;
}

/*
 * open the perly gates
 */

static Rex_t*
grp(Cenv_t* env, int parno)
{
      Rex_t*            e;
      Rex_t*            f;
      int         c;
      int         i;
      int         n;
      int         x;
      int         esc;
      int         typ;
      int         beg;
      unsigned char*    p;

      beg = env->pattern == env->cursor - env->token.len;
      if (!(c = env->token.lex) && (c = *env->cursor))
            env->cursor++;
      env->token.len = 0;
      env->parnest++;
      typ = -1;
      switch (c)
      {
      case '-':
      case '+':
      case 'a':
      case 'g':
      case 'i':
      case 'l':
      case 'm':
      case 'p':
      case 'r':
      case 's':
      case 'x':
      case 'A':
      case 'B':
      case 'E':
      case 'F':
      case 'G':
      case 'I':
      case 'K':
      case 'L':
      case 'M':   /* glob(3) */
      case 'N':   /* glob(3) */
      case 'O':   /* glob(3) */
      case 'R':   /* pcre */
      case 'S':
      case 'U':   /* pcre */
      case 'X':   /* pcre */
            x = REX_GROUP;
            i = 1;
            env->token.push = 1;
            for (;;)
            {
                  switch (c)
                  {
                  case ')':
                        if (!(env->flags & REG_LITERAL))
                        {
                              env->error = REG_BADRPT;
                              return 0;
                        }
                        /*FALLTHROUGH*/
                  case 0:
                  case T_CLOSE:
                        x = 0;
                        goto done;
                  case ':':
                        eat(env);
                        if (token(env) == T_CLOSE)
                              x = 0;
                        goto done;
                  case '-':
                        i = 0;
                        break;
                  case '+':
                        i = 1;
                        break;
                  case 'a':
                        if (i)
                              env->flags |= (REG_LEFT|REG_RIGHT);
                        else
                              env->flags &= ~(REG_LEFT|REG_RIGHT);
                        break;
                  case 'g':
                        if (i)
                              env->flags &= ~REG_MINIMAL;
                        else
                              env->flags |= REG_MINIMAL;
                        break;
                  case 'i':
                        if (i)
                              env->flags |= REG_ICASE;
                        else
                              env->flags &= ~REG_ICASE;
                        break;
                  case 'l':
                        if (i)
                              env->flags |= REG_LEFT;
                        else
                              env->flags &= ~REG_LEFT;
                        break;
                  case 'm':
                        if (i)
                              env->flags |= REG_NEWLINE;
                        else
                              env->flags &= ~REG_NEWLINE;
                        env->explicit = (env->flags & (REG_NEWLINE|REG_SPAN)) == REG_NEWLINE ? env->mappednewline : -1;
                        break;
                  case 'p':
                        if (i)
                              env->flags &= ~REG_LENIENT;
                        else
                              env->flags |= REG_LENIENT;
                        break;
                  case 'r':
                        if (i)
                              env->flags |= REG_RIGHT;
                        else
                              env->flags &= ~REG_RIGHT;
                        break;
                  case 's':
                        if (i)
                              env->flags |= REG_SPAN;
                        else
                              env->flags &= ~REG_SPAN;
                        env->explicit = (env->flags & (REG_NEWLINE|REG_SPAN)) == REG_NEWLINE ? env->mappednewline : -1;
                        break;
                  case 'x':
                        if (i)
                              env->flags |= REG_COMMENT;
                        else
                              env->flags &= ~REG_COMMENT;
                        break;
                  case 'A':
                        env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_SHELL|REG_LEFT|REG_RIGHT);
                        env->flags |= REG_AUGMENTED|REG_EXTENDED;
                        typ = ARE;
                        break;
                  case 'B':
                  case 'G':
                        env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_SHELL|REG_LEFT|REG_RIGHT);
                        typ = BRE;
                        break;
                  case 'E':
                        env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_SHELL|REG_LEFT|REG_RIGHT);
                        env->flags |= REG_EXTENDED;
                        typ = ERE;
                        break;
                  case 'F':
                  case 'L':
                        env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_SHELL|REG_LEFT|REG_RIGHT);
                        env->flags |= REG_LITERAL;
                        typ = ERE;
                        break;
                  case 'K':
                        env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_SHELL|REG_LEFT|REG_RIGHT);
                        env->flags |= REG_AUGMENTED|REG_SHELL|REG_LEFT|REG_RIGHT;
                        typ = KRE;
                        break;
                  case 'M':
                        /* used by caller to disable glob(3) GLOB_BRACE */
                        break;
                  case 'N':
                        /* used by caller to disable glob(3) GLOB_NOCHECK */
                        break;
                  case 'O':
                        /* used by caller to disable glob(3) GLOB_STARSTAR */
                        break;
                  case 'S':
                        env->flags &= ~(REG_AUGMENTED|REG_EXTENDED|REG_LITERAL|REG_SHELL|REG_LEFT|REG_RIGHT);
                        env->flags |= REG_SHELL|REG_LEFT|REG_RIGHT;
                        typ = SRE;
                        break;
                  case 'U': /* PCRE_UNGREEDY */
                        if (i)
                              env->flags |= REG_MINIMAL;
                        else
                              env->flags &= ~REG_MINIMAL;
                        break;
                  case 'X': /* PCRE_EXTRA */
                        break;
                  default:
                        env->error = REG_BADRPT;
                        return 0;
                  }
                  eat(env);
                  c = token(env);
            }
      done:
            break;
      case ':':
            x = REX_GROUP;
            break;
      case '=':
            x = REX_GROUP_AHEAD;
            break;
      case '!':
            x = REX_GROUP_AHEAD_NOT;
            break;
      case '<':
            switch (token(env))
            {
            case '=':
                  x = REX_GROUP_BEHIND;
                  break;
            case '!':
            case T_BANG:
                  x = REX_GROUP_BEHIND_NOT;
                  break;
            default:
                  env->error = REG_BADRPT;
                  return 0;
            }
            eat(env);
            break;
      case '>':
            x = REX_GROUP_CUT;
            break;
      case '%':
      case T_PERCENT:
            e = node(env, REX_NEST, 0, 0, (UCHAR_MAX + 1) * sizeof(unsigned short));
            e->re.nest.primary = isalnum(*env->cursor) ? -1 : *env->cursor;
            n = 1;
            for (;;)
            {
                  switch (i = chr(env, &esc))
                  {
                  case -1:
                  case 0:
                  invalid:
                        env->cursor -= esc + 1;
                        env->error = REG_EPAREN;
                        return 0;
                  case 'D':
                        x = REX_NEST_delimiter;
                        /*FALLTHROUGH*/
                  delimiter:
                        if ((i = chr(env, &esc)) < 0)
                              goto invalid;
                        if (e->re.nest.type[i] & ~x)
                              goto invalid;
                        e->re.nest.type[i] = x;
                        continue;
                  case 'E':
                        x = REX_NEST_escape;
                        goto delimiter;
                  case 'L':
                        x = REX_NEST_literal;
                        goto quote;
                  case 'O':
                        switch (i = chr(env, &esc))
                        {
                        case 'T':
                              e->re.nest.type[UCHAR_MAX+1] |= REX_NEST_terminator;
                              break;
                        default:
                              goto invalid;
                        }
                        continue;
                  case 'Q':
                        x = REX_NEST_quote;
                        /*FALLTHROUGH*/
                  quote:
                        if ((i = chr(env, &esc)) < 0)
                              goto invalid;
                        if (e->re.nest.type[i] & ~x)
                              goto invalid;
                        e->re.nest.type[i] = x|REX_NEST_open|REX_NEST_close|(i<<REX_NEST_SHIFT);
                        continue;
                  case 'S':
                        x = REX_NEST_separator;
                        goto delimiter;
                  case 'T':
                        x = REX_NEST_terminator;
                        goto delimiter;
                  case '|':
                  case '&':
                        if (!esc)
                              goto invalid;
                        goto nesting;
                  case '(':
                        if (!esc)
                              n++;
                        goto nesting;
                  case ')':
                        if (!esc && !--n)
                              break;
                        goto nesting;
                  default:
                  nesting:
                        if (isalnum(i) || (e->re.nest.type[i] & (REX_NEST_close|REX_NEST_escape|REX_NEST_literal|REX_NEST_quote|REX_NEST_delimiter|REX_NEST_separator|REX_NEST_terminator)))
                              goto invalid;
                        e->re.nest.type[i] = REX_NEST_open;
                        if ((x = chr(env, &esc)) < 0 || (e->re.nest.type[x] & (REX_NEST_close|REX_NEST_escape|REX_NEST_delimiter|REX_NEST_separator|REX_NEST_terminator)))
                              goto invalid;
                        if (!esc)
                        {
                              if (x == ')' && !--n)
                                    goto invalid;
                              else if (x == '(')
                                    n++;
                        }
                        e->re.nest.type[x] |= REX_NEST_close;
                        e->re.nest.type[i] |= x << REX_NEST_SHIFT;
                        continue;
                  }
                  break;
            }
            env->parnest--;
            if (c == T_PERCENT)
                  for (n = 0; n < 2; n++)
                  {
                        parno = ++env->parno;
                        if (!(f = node(env, REX_GROUP, 0, 0, 0)))
                        {
                              drop(env->disc, e);
                              return 0;
                        }
                        if (parno < elementsof(env->paren))
                              env->paren[parno] = f;
                        f->re.group.back = 0;
                        f->re.group.number = parno;
                        f->re.group.expr.rex = e;
                        e = f;
                  }
            return e;
      case '(':
            c = 0;
            if (isdigit(*env->cursor))
            {
                  f = 0;
                  do
                  {
                        if (c > (INT_MAX / 10))
                        {
                              env->error = REG_BADRPT;
                              return 0;
                        }
                        c = c * 10 + (*env->cursor++ - '0');
                  } while (isdigit(*env->cursor));
                  if (*env->cursor++ != ')')
                  {
                        env->error = REG_BADRPT;
                        return 0;
                  }
                  if (c && env->type >= SRE)
                        c = c * 2 - 1;
                  if (!c || c > env->parno || !env->paren[c])
                  {
                        if (!(env->flags & REG_LENIENT))
                        {
                              env->error = REG_ESUBREG;
                              return 0;
                        }
                        if (c)
                              c = -1;
                  }
            }
            else
            {
                  if (env->type < SRE && *env->cursor++ != '?')
                  {
                        env->error = REG_BADRPT;
                        return 0;
                  }
                  if (!(f = grp(env, parno + 1)) && env->error)
                        return 0;
            }
            if (!(e = node(env, REX_GROUP_COND, 0, 0, 0)))
            {
                  drop(env->disc, f);
                  return 0;
            }
            e->re.group.size = c;
            e->re.group.expr.binary.left = f;
            if (!(e->re.group.expr.binary.right = alt(env, parno, 1)))
            {
                  drop(env->disc, e);
                  return 0;
            }
            if (token(env) != T_CLOSE)
            {
                  env->error = REG_EPAREN;
                  return 0;
            }
            eat(env);
            env->parnest--;
            return rep(env, e, parno, parno);
      case '{':
            p = env->cursor;
            n = 1;
            while (c = *env->cursor)
            {
                  if (c == '\\' && *(env->cursor + 1))
                        env->cursor++;
                  else if (c == '{')
                        n++;
                  else if (c == '}' && !--n)
                        break;
                  else if (c == env->delimiter || c == env->terminator)
                        break;
                  env->cursor++;
            }
            if (c != '}')
            {
                  env->error = REG_EBRACE;
                  return 0;
            }
            if (*++env->cursor != ')')
            {
                  env->error = REG_EPAREN;
                  return 0;
            }
            env->cursor++;
            env->parnest--;
            if (env->disc->re_version < REG_VERSION_EXEC)
            {
                  env->error = REG_BADRPT;
                  return 0;
            }
            if (!env->disc->re_execf)
                  return 0;
            if (!(e = node(env, REX_EXEC, 0, 0, 0)))
                  return 0;
            e->re.exec.text = (const char*)p;
            e->re.exec.size = env->cursor - p - 2;
            if (!env->disc->re_compf)
                  e->re.exec.data = 0;
            else
                  e->re.exec.data = (*env->disc->re_compf)(env->regex, e->re.exec.text, e->re.exec.size, env->disc);
            return e;
      case '0': case '1': case '2': case '3': case '4':
      case '5': case '6': case '7': case '8': case '9':
            c -= '0';
            while (isdigit(*env->cursor))
            {
                  if (c > (INT_MAX / 10))
                  {
                        env->error = REG_ESUBREG;
                        return 0;
                  }
                  c = c * 10 + *env->cursor++ - '0';
            }
            if (*env->cursor == ')')
            {
                  env->cursor++;
                  env->parnest--;
                  env->token.len = 1;
                  if (c > env->parno || !env->paren[c])
                  {
                        env->error = REG_ESUBREG;
                        return 0;
                  }
                  env->paren[c]->re.group.back = 1;
                  return rep(env, node(env, REX_BACK, c, 0, 0), 0, 0);
            }
            /*FALLTHROUGH*/
      default:
            env->error = REG_BADRPT;
            return 0;
      }
      if (x && !(e = alt(env, parno, 0)))
            return 0;
      c = token(env);
      env->parnest--;
      if (c != T_CLOSE && (!(env->flags & REG_LITERAL) || c != ')'))
      {
            env->error = REG_EPAREN;
            return 0;
      }
      eat(env);
      if (typ >= 0)
      {
            if (beg)
                  env->pattern = env->cursor;
            env->type = typ;
      }
      if (!x)
            return 0;
      if (!(f = node(env, x, 0, 0, 0)))
      {
            drop(env->disc, e);
            return 0;
      }
      f->re.group.expr.rex = e;
      if (x == REX_GROUP_BEHIND || x == REX_GROUP_BEHIND_NOT)
      {
            if (stats(env, e))
            {
                  drop(env->disc, f);
                  if (!env->error)
                        env->error = REG_ECOUNT;
                  return 0;
            }
            f->re.group.size = env->stats.m;
            memset(&env->stats, 0, sizeof(env->stats));
      }
      switch (x)
      {
      case REX_GROUP:
      case REX_GROUP_CUT:
            f = rep(env, f, parno, env->parno);
            break;
      }
      return f;
}

static Rex_t*
seq(Cenv_t* env)
{
      Rex_t*            e;
      Rex_t*            f;
      Token_t           tok;
      int         c;
      int         i;
      int         n;
      int         x;
      int         parno;
      int         type;
      regflags_t  flags;
      unsigned char*    s;
      unsigned char*    p;
      unsigned char*    t;
      unsigned char*    u;
      unsigned char     buf[256];

      for (;;)
      {
            s = buf;
            while ((c = token(env)) < T_META && s < &buf[sizeof(buf) - env->token.len])
            {     
                  x = c;
                  p = env->cursor;
                  if (c >= 0)
                  {
                        n = 1;
                        *s++ = (env->flags & REG_ICASE) ? toupper(c) : c;
                  }
                  else if (c == C_ESC || (env->flags & REG_ICASE))
                  {
                        c = (c == C_ESC) ? env->token.lex : mbchar(p);
                        if (env->flags & REG_ICASE)
                              c = towupper(c);
                        if ((&buf[sizeof(buf)] - s) < MB_CUR_MAX)
                              break;
                        if ((n = wctomb((char*)s, c)) < 0)
                              *s++ = c;
                        else if (n)
                              s += n;
                        else
                        {
                              n = 1;
                              *s++ = 0;
                        }
                  }
                  else
                  {
                        n = env->token.len - env->token.esc;
                        for (t = p, u = s + n; s < u; *s++ = *t++);
                  }
                  eat(env);
            }
            if (c == T_BAD)
                  return 0;
            if (s > buf)
                  switch (c)
                  {
                  case T_STAR:
                  case T_PLUS:
                  case T_LEFT:
                  case T_QUES:
                  case T_BANG:
                        if ((s -= n) == buf)
                              e = 0;
                        else
                        {
                              i = s - buf;
                              if (!(e = node(env, REX_STRING, 0, 0, i)))
                                    return 0;
                              memcpy((char*)(e->re.string.base = (unsigned char*)e->re.data), (char*)buf, i);
                              e->re.string.size = i;
                        }
                        if (x >= 0)
                        {
                              if (!(f = node(env, REX_ONECHAR, 1, 1, 0)))
                              {
                                    drop(env->disc, e);
                                    return 0;
                              }
                              f->re.onechar = (env->flags & REG_ICASE) ? toupper(x) : x;
                        }
                        else
                        {
                              if (!(f = node(env, REX_STRING, 0, 0, n)))
                                    return 0;
                              memcpy((char*)(f->re.string.base = (unsigned char*)f->re.data), (char*)p, n);
                              f->re.string.size = n;
                        }
                        if (!(f = rep(env, f, 0, 0)) || !(f = cat(env, f, seq(env))))
                        {
                              drop(env->disc, e);
                              return 0;
                        }
                        if (e)
                              f = cat(env, e, f);
                        return f;
                  default:
                        c = s - buf;
                        if (!(e = node(env, REX_STRING, 0, 0, c)))
                              return 0;
                        memcpy((char*)(e->re.string.base = (unsigned char*)e->re.data), (char*)buf, c);
                        e->re.string.size = c;
                        return cat(env, e, seq(env));
                  }
            else if (c > T_BACK)
            {
                  eat(env);
                  c -= T_BACK;
                  if (c > env->parno || !env->paren[c])
                  {
                        env->error = REG_ESUBREG;
                        return 0;
                  }
                  env->paren[c]->re.group.back = 1;
                  e = rep(env, node(env, REX_BACK, c, 0, 0), 0, 0);
            }
            else
                  switch (c)
                  {
                  case T_AND:
                  case T_CLOSE:
                  case T_BAR:
                  case T_END:
                        return node(env, REX_NULL, 0, 0, 0);
                  case T_DOLL:
                        eat(env);
                        e = rep(env, node(env, REX_END, 0, 0, 0), 0, 0);
                        break;
                  case T_CFLX:
                        eat(env);
                        if ((e = node(env, REX_BEG, 0, 0, 0)) && (env->flags & REG_EXTENDED))
                              e = rep(env, e, 0, 0);
                        break;
                  case T_OPEN:
                        tok = env->token;
                        eat(env);
                        flags = env->flags;
                        type = env->type;
                        if (env->token.att)
                              env->flags |= REG_MINIMAL;
                        env->parnest++;
                        if (env->type == KRE)
                              ++env->parno;
                        parno = ++env->parno;
                        if (!(e = alt(env, parno + 1, 0)))
                              break;
                        if (e->type == REX_NULL && env->type == ERE && !(env->flags & REG_NULL))
                        {
                              drop(env->disc, e);
                              env->error = (*env->cursor == 0 || *env->cursor == env->delimiter || *env->cursor == env->terminator) ? REG_EPAREN : REG_ENULL;
                              return 0;
                        } 
                        if (token(env) != T_CLOSE)
                        {
                              drop(env->disc, e);
                              env->error = REG_EPAREN;
                              return 0;
                        } 
                        env->parnest--;
                        eat(env);
                        if (!(f = node(env, REX_GROUP, 0, 0, 0)))
                        {
                              drop(env->disc, e);
                              return 0;
                        }
                        if (parno < elementsof(env->paren))
                              env->paren[parno] = f;
                        f->re.group.back = 0;
                        f->re.group.number = parno;
                        f->re.group.expr.rex = e;
                        if (tok.lex)
                        {
                              tok.push = 1;
                              env->token = tok;
                        }
                        if (!(e = rep(env, f, parno, env->parno)))
                              return 0;
                        if (env->type == KRE)
                        {
                              if (!(f = node(env, REX_GROUP, 0, 0, 0)))
                              {
                                    drop(env->disc, e);
                                    return 0;
                              }
                              if (--parno < elementsof(env->paren))
                                    env->paren[parno] = f;
                              f->re.group.back = 0;
                              f->re.group.number = parno;
                              f->re.group.expr.rex = e;
                              e = f;
                        }
                        env->flags = flags;
                        env->type = type;
                        break;
                  case T_GROUP:
                        p = env->cursor;
                        eat(env);
                        flags = env->flags;
                        type = env->type;
                        if (!(e = grp(env, env->parno + 1)))
                        {
                              if (env->error)
                                    return 0;
                              if (env->literal == env->pattern && env->literal == p)
                                    env->literal = env->cursor;
                              continue;
                        }
                        env->flags = flags;
                        env->type = type;
                        break;
                  case T_BRA:
                        eat(env);
                        if (e = bra(env))
                              e = rep(env, e, 0, 0);
                        break;
                  case T_ALNUM:
                  case T_ALNUM_NOT:
                  case T_DIGIT:
                  case T_DIGIT_NOT:
                  case T_SPACE:
                  case T_SPACE_NOT:
                        eat(env);
                        if (e = ccl(env, c))
                              e = rep(env, e, 0, 0);
                        break;
                  case T_LT:
                        eat(env);
                        e = rep(env, node(env, REX_WBEG, 0, 0, 0), 0, 0);
                        break;
                  case T_GT:
                        eat(env);
                        e = rep(env, node(env, REX_WEND, 0, 0, 0), 0, 0);
                        break;
                  case T_DOT:
                        eat(env);
                        e = rep(env, node(env, REX_DOT, 1, 1, 0), 0, 0);
                        break;
                  case T_DOTSTAR:
                        eat(env);
                        env->token.lex = T_STAR;
                        env->token.push = 1;
                        e = rep(env, node(env, REX_DOT, 1, 1, 0), 0, 0);
                        break;
                  case T_SLASHPLUS:
                        eat(env);
                        env->token.lex = T_PLUS;
                        env->token.push = 1;
                        if (e = node(env, REX_ONECHAR, 1, 1, 0))
                        {
                              e->re.onechar = '/';
                              e = rep(env, e, 0, 0);
                        }
                        break;
                  case T_WORD:
                        eat(env);
                        e = rep(env, node(env, REX_WORD, 0, 0, 0), 0, 0);
                        break;
                  case T_WORD_NOT:
                        eat(env);
                        e = rep(env, node(env, REX_WORD_NOT, 0, 0, 0), 0, 0);
                        break;
                  case T_BEG_STR:
                        eat(env);
                        e = rep(env, node(env, REX_BEG_STR, 0, 0, 0), 0, 0);
                        break;
                  case T_END_STR:
                        eat(env);
                        e = rep(env, node(env, REX_END_STR, 0, 0, 0), 0, 0);
                        break;
                  case T_FIN_STR:
                        eat(env);
                        e = rep(env, node(env, REX_FIN_STR, 0, 0, 0), 0, 0);
                        break;
                  default:
                        env->error = REG_BADRPT;
                        return 0;
                  }
            if (e && *env->cursor != 0 && *env->cursor != env->delimiter && *env->cursor != env->terminator)
                  e = cat(env, e, seq(env));
            return e;
      }
}

static Rex_t*
con(Cenv_t* env)
{
      Rex_t*      e;
      Rex_t*      f;
      Rex_t*      g;

      if (!(e = seq(env)) || !(env->flags & REG_AUGMENTED) || token(env) != T_AND)
            return e;
      eat(env);
      if (!(f = con(env)))
      {
            drop(env->disc, e);
            return 0;
      }
      if (!(g = node(env, REX_CONJ, 0, 0, 0)))
      {
            drop(env->disc, e);
            drop(env->disc, f);
            return 0;
      }
      g->re.group.expr.binary.left = e;
      g->re.group.expr.binary.right = f;
      return g;
}

static Rex_t*
alt(Cenv_t* env, int number, int cond)
{
      Rex_t*      e;
      Rex_t*      f;
      Rex_t*      g;

      if (!(e = con(env)))
            return 0;
      else if (token(env) != T_BAR)
      {
            if (!cond)
                  return e;
            f = 0;
            if (e->type == REX_NULL)
                  goto bad;
      }
      else
      {
            eat(env);
            if (!(f = alt(env, number, 0)))
            {
                  drop(env->disc, e);
                  return 0;
            }
            if ((e->type == REX_NULL || f->type == REX_NULL) && !(env->flags & REG_NULL))
                  goto bad;
            if (!cond && (g = trie(env, e, f)))
                  return g;
      }
      if (!(g = node(env, REX_ALT, 0, 0, 0)))
      {
            env->error = REG_ESPACE;
            goto bad;
      }
      g->re.group.number = number;
      g->re.group.last = env->parno;
      g->re.group.expr.binary.left = e;
      g->re.group.expr.binary.right = f;
      return g;
 bad:
      drop(env->disc, e);
      drop(env->disc, f);
      if (!env->error)
            env->error = REG_ENULL;
      return 0;
}

/*
 * add v to REX_BM tables
 */

static void
bmstr(Cenv_t* env, register Rex_t* a, unsigned char* v, int n, Bm_mask_t b)
{
      int   c;
      int   m;
      size_t      z;

      for (m = 0; m < n; m++)
      {
            if (!(z = n - m - 1))
                  z = HIT;
            c = v[m];
            a->re.bm.mask[m][c] |= b;
            if (z == HIT || !a->re.bm.skip[c] || a->re.bm.skip[c] > z && a->re.bm.skip[c] < HIT)
                  a->re.bm.skip[c] = z;
            if (a->flags & REG_ICASE)
            {
                  if (isupper(c))
                        c = tolower(c);
                  else if (islower(c))
                        c = toupper(c);
                  else
                        continue;
                  a->re.bm.mask[m][c] |= b;
                  if (z == HIT || !a->re.bm.skip[c] || a->re.bm.skip[c] > z && a->re.bm.skip[c] < HIT)
                        a->re.bm.skip[c] = z;
            }
      }
}

/*
 * set up BM table from trie
 */

static int
bmtrie(Cenv_t* env, Rex_t* a, unsigned char* v, Trie_node_t* x, int n, int m, Bm_mask_t b)
{
      do
      {
            v[m] = x->c;
            if (m >= (n - 1))
            {
                  bmstr(env, a, v, n, b);
                  if (!(b <<= 1))
                  {
                        b = 1;
                        a->re.bm.complete = 0;
                  }
                  else if (x->son)
                        a->re.bm.complete = 0;
            }
            else if (x->son)
                  b = bmtrie(env, a, v, x->son, n, m + 1, b);
      } while (x = x->sib);
      return b;
}

/*
 * rewrite the expression tree for some special cases
 * 1. it is a null expression - illegal
 * 2. max length fixed string found -- use BM algorithm
 * 3. it begins with an unanchored string - use KMP algorithm
 * 0 returned on success
 */         

static int
special(Cenv_t* env, regex_t* p)
{
      Rex_t*            a;
      Rex_t*            e;
      Rex_t*            t;
      Rex_t*            x;
      Rex_t*            y;
      unsigned char*    s;
      int*        f;
      int         n;
      int         m;
      int         k;

      DEBUG_INIT();
      if (e = p->env->rex)
      {
            if ((x = env->stats.x) && x->re.string.size < 3)
                  x = 0;
            if ((t = env->stats.y) && t->re.trie.min < 3)
                  t = 0;
            if (x && t)
            {
                  if (x->re.string.size >= t->re.trie.min)
                        t = 0;
                  else
                        x = 0;
            }
            if (x || t)
            {
                  Bm_mask_t** mask;
                  Bm_mask_t*  h;
                  unsigned char*    v;
                  size_t*           q;
                  unsigned long     l;
                  int         i;
                  int         j;

                  if (x)
                  {
                        y = x;
                        n = m = x->re.string.size;
                        l = env->stats.l;
                  }
                  else
                  {
                        y = t;
                        n = t->re.trie.min;
                        m = t->re.trie.max;
                        l = env->stats.k;
                  }
                  if (!(q = (size_t*)alloc(env->disc, 0, (n + 1) * sizeof(size_t))))
                        return 1;
                  if (!(a = node(env, REX_BM, 0, 0, n * (sizeof(Bm_mask_t*) + (UCHAR_MAX + 1) * sizeof(Bm_mask_t)) + (UCHAR_MAX + n + 2) * sizeof(size_t))))
                  {
                        alloc(env->disc, q, 0);
                        return 1;
                  }
                  a->flags = y->flags;
                  a->map = y->map;
                  a->re.bm.size = n;
                  a->re.bm.back = (y == e || y == e->re.group.expr.rex) ? (m - n) : -1;
                  a->re.bm.left = l - 1;
                  a->re.bm.right = env->stats.m - l - n;
                  a->re.bm.complete = (y != e && (e->type != REX_GROUP || y != e->re.group.expr.rex) || e->next || ((a->re.bm.left + a->re.bm.right) >= 0)) ? 0 : n;
                  h = (Bm_mask_t*)&a->re.bm.mask[n];
                  a->re.bm.skip = (size_t*)(h + n * (UCHAR_MAX + 1));
                  a->re.bm.fail = &a->re.bm.skip[UCHAR_MAX + 1];
                  for (m = 0; m <= UCHAR_MAX; m++)
                        a->re.bm.skip[m] = n;
                  a->re.bm.skip[0] = a->re.bm.skip[env->mappednewline] = (y->next && y->next->type == REX_END) ? HIT : (n + a->re.bm.left);
                  for (i = 1; i <= n; i++)
                        a->re.bm.fail[i] = 2 * n - i;
                  mask = a->re.bm.mask;
                  for (m = 0; m < n; m++)
                  {
                        mask[m] = h;
                        h += UCHAR_MAX + 1;
                  }
                  if (x)
                        bmstr(env, a, x->re.string.base, n, 1);
                  else
                  {
                        v = (unsigned char*)q;
                        memset(v, 0, n);
                        m = 1;
                        for (i = 0; i <= UCHAR_MAX; i++)
                              if (t->re.trie.root[i])
                                    m = bmtrie(env, a, v, t->re.trie.root[i], n, 0, m);
                  }
                  mask--;
                  memset(q, 0, n * sizeof(*q));
                  for (k = (j = n) + 1; j > 0; j--, k--)
                  {
                        DEBUG_TEST(0x0010,(sfprintf(sfstderr, "BM#0: k=%d j=%d\n", k, j)),(0));
                        for (q[j] = k; k <= n; k = q[k])
                        {
                              for (m = 0; m <= UCHAR_MAX; m++)
                                    if (mask[k][m] == mask[j][m])
                                    {
                                          DEBUG_TEST(0x0010,sfprintf(sfstderr, "CUT1: mask[%d][%c]=mask[%d][%c]\n", k, m, j, m), (0));
                                          goto cut;
                                    }
                              DEBUG_TEST(0x0010,sfprintf(sfstderr, "BM#2: fail[%d]=%d => %d\n", k, a->re.bm.fail[k], (a->re.bm.fail[k] > n - j) ? (n - j) : a->re.bm.fail[k]), (0));
                              if (a->re.bm.fail[k] > n - j)
                                    a->re.bm.fail[k] = n - j;
                        }
                  cut:  ;
                  }
                  for (i = 1; i <= n; i++)
                        if (a->re.bm.fail[i] > n + k - i)
                        {
                              DEBUG_TEST(0x0010,sfprintf(sfstderr, "BM#4: fail[%d]=%d => %d\n", i, a->re.bm.fail[i], n + k - i), (0));
                              a->re.bm.fail[i] = n + k - i;
                        }
#if _AST_REGEX_DEBUG
                  if (DEBUG_TEST(0x0020,(1),(0)))
                  {
                        sfprintf(sfstderr, "STAT: complete=%d n=%d k=%d l=%d r=%d y=%d:%d e=%d:%d\n", a->re.bm.complete, n, k, a->re.bm.left, a->re.bm.right, y->type, y->next ? y->next->type : 0, e->type, e->next ? e->next->type : 0);
                        for (m = 0; m < n; m++)
                              for (i = 1; i <= UCHAR_MAX; i++)
                                    if (a->re.bm.mask[m][i])
                                          sfprintf(sfstderr, "MASK: [%d]['%c'] = %032..2u\n", m, i, a->re.bm.mask[m][i]);
                        for (i = ' '; i <= UCHAR_MAX; i++)
                              if (a->re.bm.skip[i] >= HIT)
                                    sfprintf(sfstderr, "SKIP: ['%c'] =   *\n", i);
                              else if (a->re.bm.skip[i] > 0 && a->re.bm.skip[i] < n)
                                    sfprintf(sfstderr, "SKIP: ['%c'] = %3d\n", i, a->re.bm.skip[i]);
                        for (j = 31; j >= 0; j--)
                        {
                              sfprintf(sfstderr, "      ");
                        next:
                              for (m = 0; m < n; m++)
                              {
                                    for (i = 0040; i < 0177; i++)
                                          if (a->re.bm.mask[m][i] & (1 << j))
                                          {
                                                sfprintf(sfstderr, "  %c", i);
                                                break;
                                          }
                                    if (i >= 0177)
                                    {
                                          if (j > 0)
                                          {
                                                j--;
                                                goto next;
                                          }
                                          sfprintf(sfstderr, "  ?");
                                    }
                              }
                              sfprintf(sfstderr, "\n");
                        }
                        sfprintf(sfstderr, "FAIL: ");
                        for (m = 1; m <= n; m++)
                              sfprintf(sfstderr, "%3d", a->re.bm.fail[m]);
                        sfprintf(sfstderr, "\n");
                  }
#endif
                  alloc(env->disc, q, 0);
                  a->next = e;
                  p->env->rex = a;
                  return 0;
            }
            switch (e->type)
            {
            case REX_BEG:
                  if (env->flags & REG_NEWLINE)
                        return 0;
                  break;
            case REX_GROUP:
                  if (env->stats.b)
                        return 0;
                  e = e->re.group.expr.rex;
                  if (e->type != REX_DOT)
                        return 0;
                  /*FALLTHROUGH*/
            case REX_DOT:
                  if (e->lo == 0 && e->hi == RE_DUP_INF)
                        break;
                  return 0;
            case REX_NULL:
                  if (env->flags & REG_NULL)
                        break;
                  env->error = REG_ENULL;
                  return 1;
            case REX_STRING:
                  if ((env->flags & (REG_LEFT|REG_LITERAL|REG_RIGHT)) || e->map)
                        return 0;
                  s = e->re.string.base;
                  n = e->re.string.size;
                  if (!(a = node(env, REX_KMP, 0, 0, n * (sizeof(int*) + 1))))
                        return 1;
                  a->flags = e->flags;
                  a->map = e->map;
                  f = a->re.string.fail;
                  memcpy((char*)(a->re.string.base = (unsigned char*)&f[n]), (char*)s, n);
                  s = a->re.string.base;
                  a->re.string.size = n;
                  f[0] = m = -1;
                  for (k = 1; k < n; k++)
                  {
                        while (m >= 0 && s[m+1] != s[k])
                              m = f[m];
                        if (s[m+1] == s[k])
                              m++;
                        f[k] = m;
                  }
                  a->next = e->next;
                  p->env->rex = a;
                  e->next = 0;
                  drop(env->disc, e);
                  break;
            default:
                  return 0;
            }
      }
      p->env->once = 1;
      return 0;
}           

int
regcomp(regex_t* p, const char* pattern, regflags_t flags)
{
      Rex_t*                  e;
      Rex_t*                  f;
      regdisc_t*        disc;
      unsigned char*          fold;
      int               i;
      Cenv_t                  env;

      if (!p)
            return REG_BADPAT;
      if (flags & REG_DISCIPLINE)
      {
            flags &= ~REG_DISCIPLINE;
            disc = p->re_disc;
      }
      else
            disc = &state.disc;
      if (!disc->re_errorlevel)
            disc->re_errorlevel = 2;
      p->env = 0;
      if (!pattern)
            return fatal(disc, REG_BADPAT, pattern);
      if (!state.initialized)
      {
            state.initialized = 1;
            for (i = 0; i < elementsof(state.escape); i++)
                  state.magic[state.escape[i].key] = state.escape[i].val;
      }
      if (!(fold = (unsigned char*)LCINFO(AST_LC_CTYPE)->data))
      {
            if (!(fold = newof(0, unsigned char, UCHAR_MAX, 1)))
                  return fatal(disc, REG_ESPACE, pattern);
            for (i = 0; i <= UCHAR_MAX; i++)
                  fold[i] = toupper(i);
            LCINFO(AST_LC_CTYPE)->data = (void*)fold;
      }
 again:
      if (!(p->env = (Env_t*)alloc(disc, 0, sizeof(Env_t))))
            return fatal(disc, REG_ESPACE, pattern);
      memset(p->env, 0, sizeof(*p->env));
      memset(&env, 0, sizeof(env));
      env.regex = p;
      env.flags = flags;
      env.disc = p->env->disc = disc;
      if (env.flags & REG_AUGMENTED)
            env.flags |= REG_EXTENDED;
      env.mappeddot = '.';
      env.mappednewline = '\n';
      env.mappedslash = '/';
      if (disc->re_version >= REG_VERSION_MAP && disc->re_map)
      {
            env.map = disc->re_map;
            env.MAP = p->env->fold;
            for (i = 0; i <= UCHAR_MAX; i++)
            {
                  env.MAP[i] = fold[env.map[i]];
                  if (env.map[i] == '.')
                        env.mappeddot = i;
                  if (env.map[i] == '\n')
                        env.mappednewline = i;
                  if (env.map[i] == '/')
                        env.mappedslash = i;
            }
      }
      else
            env.MAP = fold;
      env.type = (env.flags & REG_AUGMENTED) ? ARE : (env.flags & REG_EXTENDED) ? ERE : BRE;
      env.explicit = -1;
      if (env.flags & REG_SHELL)
      {
            if (env.flags & REG_SHELL_PATH)
                  env.explicit = env.mappedslash;
            env.flags |= REG_LENIENT|REG_NULL;
            env.type = env.type == BRE ? SRE : KRE;
      }
      if ((env.flags & (REG_NEWLINE|REG_SPAN)) == REG_NEWLINE)
            env.explicit = env.mappednewline;
      p->env->leading = (env.flags & REG_SHELL_DOT) ? env.mappeddot : -1;
      env.posixkludge = !(env.flags & (REG_EXTENDED|REG_SHELL));
      env.regexp = !!(env.flags & REG_REGEXP);
      env.token.lex = 0;
      env.token.push = 0;
      if (env.flags & REG_DELIMITED)
      {
            switch (env.delimiter = *pattern++)
            {
            case 0:
            case '\\':
            case '\n':
            case '\r':
                  env.error = REG_EDELIM;
                  goto bad;
            }
            env.terminator = '\n';
      }
      env.literal = env.pattern = env.cursor = (unsigned char*)pattern;
      if (!(p->env->rex = alt(&env, 1, 0)))
            goto bad;
      if (env.parnest)
      {
            env.error = REG_EPAREN;
            goto bad;
      }
      p->env->stats.re_flags = env.flags & (REG_EXTENDED|REG_AUGMENTED|REG_SHELL);
      if (env.flags & REG_LEFT)
      {
            if (p->env->rex->type != REX_BEG)
            {
                  if (p->env->rex->type == REX_ALT)
                        env.flags &= ~REG_FIRST;
                  if (!(e = node(&env, REX_BEG, 0, 0, 0)))
                  {
                        regfree(p);
                        return fatal(disc, REG_ESPACE, pattern);
                  }
                  e->next = p->env->rex;
                  p->env->rex = e;
                  p->env->once = 1;
            }
            p->env->stats.re_flags |= REG_LEFT;
      }
      for (e = p->env->rex; e->next; e = e->next);
      p->env->done.type = REX_DONE;
      p->env->done.flags = e->flags;
      if (env.flags & REG_RIGHT)
      {
            if (e->type != REX_END)
            {
                  if (p->env->rex->type == REX_ALT)
                        env.flags &= ~REG_FIRST;
                  if (!(f = node(&env, REX_END, 0, 0, 0)))
                  {
                        regfree(p);
                        return fatal(disc, REG_ESPACE, pattern);
                  }
                  f->flags = e->flags;
                  f->map = e->map;
                  e->next = f;
            }
            p->env->stats.re_flags |= REG_RIGHT;
      }
      if (stats(&env, p->env->rex))
      {
            if (!env.error)
                  env.error = REG_ECOUNT;
            goto bad;
      }
      if (env.stats.b)
            p->env->hard = p->env->separate = 1;
      else if (!(env.flags & REG_FIRST) && (env.stats.a || env.stats.c > 1 && env.stats.c != env.stats.s || env.stats.t && (env.stats.t > 1 || env.stats.a || env.stats.c)))
            p->env->hard = 1;
      if (p->env->hard || env.stats.c || env.stats.i)
            p->env->stats.re_min = p->env->stats.re_max = -1;
      else
      {
            if (!(p->env->stats.re_min = env.stats.m))
                  p->env->stats.re_min = -1;
            if (!(p->env->stats.re_max = env.stats.n))
                  p->env->stats.re_max = -1;
      }
      if (special(&env, p))
            goto bad;
      serialize(&env, p->env->rex, 1);
      p->re_nsub = env.stats.p;
      if (env.type == KRE)
            p->re_nsub /= 2;
      if (env.flags & REG_DELIMITED)
      {
            p->re_npat = env.cursor - env.pattern + 1;
            if (*env.cursor == env.delimiter)
                  p->re_npat++;
            else if (env.flags & REG_MUSTDELIM)
            {
                  env.error = REG_EDELIM;
                  goto bad;
            }
            else
                  env.flags &= ~REG_DELIMITED;
      }
      p->env->explicit = env.explicit;
      p->env->flags = env.flags & REG_COMP;
      p->env->min = env.stats.m;
      p->env->nsub = env.stats.p + env.stats.u;
      p->env->refs = 1;
      return 0;
 bad:
      regfree(p);
      if (!env.error)
            env.error = REG_ESPACE;
      if (env.type >= SRE && env.error != REG_ESPACE && !(flags & REG_LITERAL))
      {
            flags |= REG_LITERAL;
            pattern = (const char*)env.literal;
            goto again;
      }
      return fatal(disc, env.error, pattern);
}

/*
 * regcomp() on sized pattern
 * the lazy way around adding and checking env.end
 */

int
regncomp(regex_t* p, const char* pattern, size_t size, regflags_t flags)
{
      char* s;
      int   r;

      if (!(s = malloc(size + 1)))
            return fatal((flags & REG_DISCIPLINE) ? p->re_disc : &state.disc, REG_ESPACE, pattern);
      memcpy(s, pattern, size);
      s[size] = 0;
      r = regcomp(p, s, flags);
      free(s);
      return r;
}

/*
 * combine two compiled regular expressions if possible,
 * replacing first with the combination and freeing second.
 * return 0 on success.
 * the only combinations handled are building a Trie
 * from String|Kmp|Trie and String|Kmp
 */

int
regcomb(regex_t* p, regex_t* q)
{
      Rex_t*      e = p->env->rex;
      Rex_t*      f = q->env->rex;
      Rex_t*      g;
      Cenv_t      env;

      if (!e || !f)
            return fatal(p->env->disc, REG_BADPAT, NiL);
      if (p->env->separate || q->env->separate)
            return REG_ESUBREG;
      memset(&env, 0, sizeof(env));
      env.disc = p->env->disc;
      if (e->type == REX_BM)
      {
            p->env->rex = e->next;
            e->next = 0;
            drop(env.disc, e);
            e = p->env->rex;
      }
      if (f->type == REX_BM)
      {
            q->env->rex = f->next;
            f->next = 0;
            drop(env.disc, f);
            f = q->env->rex;
      }
      if (e->type == REX_BEG && f->type == REX_BEG)
      {
            p->env->flags |= REG_LEFT;
            p->env->rex = e->next;
            e->next = 0;
            drop(env.disc, e);
            e = p->env->rex;
            q->env->rex = f->next;
            f->next = 0;
            drop(env.disc, f);
            f = q->env->rex;
      }
      if (e->next && e->next->type == REX_END && f->next && f->next->type == REX_END)
      {
            p->env->flags |= REG_RIGHT;
            drop(env.disc, e->next);
            e->next = 0;
            drop(env.disc, f->next);
            f->next = 0;
      }
      if (!(g = trie(&env, f, e)))
            return fatal(p->env->disc, REG_BADPAT, NiL);
      p->env->rex = g;
      if (!q->env->once)
            p->env->once = 0;
      q->env->rex = 0;
      if (p->env->flags & REG_LEFT)
      {
            if (!(e = node(&env, REX_BEG, 0, 0, 0)))
            {
                  regfree(p);
                  return fatal(p->env->disc, REG_ESPACE, NiL);
            }
            e->next = p->env->rex;
            p->env->rex = e;
            p->env->once = 1;
      }
      if (p->env->flags & REG_RIGHT)
      {
            for (f = p->env->rex; f->next; f = f->next);
            if (f->type != REX_END)
            {
                  if (!(e = node(&env, REX_END, 0, 0, 0)))
                  {
                        regfree(p);
                        return fatal(p->env->disc, REG_ESPACE, NiL);
                  }
                  f->next = e;
            }
      }
      env.explicit = p->env->explicit;
      env.flags = p->env->flags;
      env.disc = p->env->disc;
      if (stats(&env, p->env->rex))
      {
            regfree(p);
            return fatal(p->env->disc, env.error ? env.error : REG_ECOUNT, NiL);
      }
      if (special(&env, p))
      {
            regfree(p);
            return fatal(p->env->disc, env.error ? env.error : REG_ESPACE, NiL);
      }
      p->env->min = g->re.trie.min;
      return 0;
}

/*
 * copy a reference of p into q
 * p and q may then have separate regsubcomp() instantiations
 */

int
regdup(regex_t* p, regex_t* q)
{
      if (!p || !q)
            return REG_BADPAT;
      *q = *p;
      p->env->refs++;
      q->re_sub = 0;
      return 0;
}

Generated by  Doxygen 1.6.0   Back to index