1 /*
   2  * Copyright 2013 Garrett D'Amore <garrett@damore.org>
   3  * Copyright 2010 Nexenta Systems, Inc.  All rights reserved.
   4  * Copyright 2012 Milan Jurik. All rights reserved.
   5  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
   6  * Copyright (c) 1992, 1993, 1994
   7  *      The Regents of the University of California.  All rights reserved.
   8  *
   9  * This code is derived from software contributed to Berkeley by
  10  * Henry Spencer.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36 
  37 #include "lint.h"
  38 #include "file64.h"
  39 #include <sys/types.h>
  40 #include <stdio.h>
  41 #include <string.h>
  42 #include <ctype.h>
  43 #include <limits.h>
  44 #include <stdlib.h>
  45 #include <regex.h>
  46 #include <wchar.h>
  47 #include <wctype.h>
  48 
  49 #include "../locale/runetype.h"
  50 #include "../locale/collate.h"
  51 
  52 #include "utils.h"
  53 #include "regex2.h"
  54 
  55 #include "cname.h"
  56 #include "../locale/mblocal.h"
  57 
  58 /*
  59  * parse structure, passed up and down to avoid global variables and
  60  * other clumsinesses
  61  */
  62 struct parse {
  63         const char *next;       /* next character in RE */
  64         const char *end;        /* end of string (-> NUL normally) */
  65         int error;              /* has an error been seen? */
  66         sop *strip;             /* malloced strip */
  67         sopno ssize;            /* malloced strip size (allocated) */
  68         sopno slen;             /* malloced strip length (used) */
  69         int ncsalloc;           /* number of csets allocated */
  70         struct re_guts *g;
  71 #define NPAREN  10              /* we need to remember () 1-9 for back refs */
  72         sopno pbegin[NPAREN];   /* -> ( ([0] unused) */
  73         sopno pend[NPAREN];     /* -> ) ([0] unused) */
  74 };
  75 
  76 /* ========= begin header generated by ./mkh ========= */
  77 #ifdef __cplusplus
  78 extern "C" {
  79 #endif
  80 
  81 /* === regcomp.c === */
  82 static void p_ere(struct parse *p, int stop);
  83 static void p_ere_exp(struct parse *p);
  84 static void p_str(struct parse *p);
  85 static void p_bre(struct parse *p, int end1, int end2);
  86 static int p_simp_re(struct parse *p, int starordinary);
  87 static int p_count(struct parse *p);
  88 static void p_bracket(struct parse *p);
  89 static void p_b_term(struct parse *p, cset *cs);
  90 static void p_b_cclass(struct parse *p, cset *cs);
  91 static void p_b_eclass(struct parse *p, cset *cs);
  92 static wint_t p_b_symbol(struct parse *p);
  93 static wint_t p_b_coll_elem(struct parse *p, wint_t endc);
  94 static wint_t othercase(wint_t ch);
  95 static void bothcases(struct parse *p, wint_t ch);
  96 static void ordinary(struct parse *p, wint_t ch);
  97 static void nonnewline(struct parse *p);
  98 static void repeat(struct parse *p, sopno start, int from, int to);
  99 static int seterr(struct parse *p, int e);
 100 static cset *allocset(struct parse *p);
 101 static void freeset(struct parse *p, cset *cs);
 102 static void CHadd(struct parse *p, cset *cs, wint_t ch);
 103 static void CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max);
 104 static void CHaddtype(struct parse *p, cset *cs, wctype_t wct);
 105 static wint_t singleton(cset *cs);
 106 static sopno dupl(struct parse *p, sopno start, sopno finish);
 107 static void doemit(struct parse *p, sop op, size_t opnd);
 108 static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
 109 static void dofwd(struct parse *p, sopno pos, sop value);
 110 static int enlarge(struct parse *p, sopno size);
 111 static void stripsnug(struct parse *p, struct re_guts *g);
 112 static void findmust(struct parse *p, struct re_guts *g);
 113 static int altoffset(sop *scan, int offset);
 114 static void computejumps(struct parse *p, struct re_guts *g);
 115 static void computematchjumps(struct parse *p, struct re_guts *g);
 116 static sopno pluscount(struct parse *p, struct re_guts *g);
 117 static wint_t wgetnext(struct parse *p);
 118 
 119 #ifdef __cplusplus
 120 }
 121 #endif
 122 /* ========= end header generated by ./mkh ========= */
 123 
 124 static char nuls[10];           /* place to point scanner in event of error */
 125 
 126 /*
 127  * macros for use with parse structure
 128  * BEWARE:  these know that the parse structure is named `p' !!!
 129  */
 130 #define PEEK()  (*p->next)
 131 #define PEEK2() (*(p->next+1))
 132 #define MORE()  (p->next < p->end)
 133 #define MORE2() (p->next+1 < p->end)
 134 #define SEE(c)  (MORE() && PEEK() == (c))
 135 #define SEETWO(a, b)    (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
 136 #define EAT(c)  ((SEE(c)) ? (NEXT(), 1) : 0)
 137 #define EATTWO(a, b)    ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
 138 #define NEXT()  (p->next++)
 139 #define NEXT2() (p->next += 2)
 140 #define NEXTn(n)        (p->next += (n))
 141 #define GETNEXT()       (*p->next++)
 142 #define WGETNEXT()      wgetnext(p)
 143 #define SETERROR(e)     ((void)seterr(p, (e)))
 144 #define REQUIRE(co, e)  ((co) || seterr(p, e))
 145 #define MUSTSEE(c, e)   (REQUIRE(MORE() && PEEK() == (c), e))
 146 #define MUSTEAT(c, e)   (REQUIRE(MORE() && GETNEXT() == (c), e))
 147 #define MUSTNOTSEE(c, e)        (REQUIRE(!MORE() || PEEK() != (c), e))
 148 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
 149 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
 150 #define AHEAD(pos)              dofwd(p, pos, HERE()-(pos))
 151 #define ASTERN(sop, pos)        EMIT(sop, HERE()-pos)
 152 #define HERE()          (p->slen)
 153 #define THERE()         (p->slen - 1)
 154 #define THERETHERE()    (p->slen - 2)
 155 #define DROP(n) (p->slen -= (n))
 156 
 157 #ifndef NDEBUG
 158 static int never = 0;           /* for use in asserts; shuts lint up */
 159 #else
 160 #define never   0               /* some <assert.h>s have bugs too */
 161 #endif
 162 
 163 /*
 164  * regcomp - interface for parser and compilation
 165  */
 166 int                             /* 0 success, otherwise REG_something */
 167 regcomp(regex_t *_RESTRICT_KYWD preg, const char *_RESTRICT_KYWD pattern,
 168     int cflags)
 169 {
 170         struct parse pa;
 171         struct re_guts *g;
 172         struct parse *p = &pa;
 173         int i;
 174         size_t len;
 175         size_t maxlen;
 176 #ifdef REDEBUG
 177 #define GOODFLAGS(f)    (f)
 178 #else
 179 #define GOODFLAGS(f)    ((f)&~REG_DUMP)
 180 #endif
 181 
 182         /* We had REG_INVARG, but we don't have that on Solaris. */
 183         cflags = GOODFLAGS(cflags);
 184         if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
 185                 return (REG_EFATAL);
 186 
 187         if (cflags&REG_PEND) {
 188                 if (preg->re_endp < pattern)
 189                         return (REG_EFATAL);
 190                 len = preg->re_endp - pattern;
 191         } else
 192                 len = strlen(pattern);
 193 
 194         /* do the mallocs early so failure handling is easy */
 195         g = (struct re_guts *)malloc(sizeof (struct re_guts));
 196         if (g == NULL)
 197                 return (REG_ESPACE);
 198         /*
 199          * Limit the pattern space to avoid a 32-bit overflow on buffer
 200          * extension.  Also avoid any signed overflow in case of conversion
 201          * so make the real limit based on a 31-bit overflow.
 202          *
 203          * Likely not applicable on 64-bit systems but handle the case
 204          * generically (who are we to stop people from using ~715MB+
 205          * patterns?).
 206          */
 207         maxlen = ((size_t)-1 >> 1) / sizeof (sop) * 2 / 3;
 208         if (len >= maxlen) {
 209                 free((char *)g);
 210                 return (REG_ESPACE);
 211         }
 212         p->ssize = len/(size_t)2*(size_t)3 + (size_t)1;      /* ugh */
 213         assert(p->ssize >= len);
 214 
 215         p->strip = (sop *)malloc(p->ssize * sizeof (sop));
 216         p->slen = 0;
 217         if (p->strip == NULL) {
 218                 free((char *)g);
 219                 return (REG_ESPACE);
 220         }
 221 
 222         /* set things up */
 223         p->g = g;
 224         p->next = pattern;   /* convenience; we do not modify it */
 225         p->end = p->next + len;
 226         p->error = 0;
 227         p->ncsalloc = 0;
 228         for (i = 0; i < NPAREN; i++) {
 229                 p->pbegin[i] = 0;
 230                 p->pend[i] = 0;
 231         }
 232         g->sets = NULL;
 233         g->ncsets = 0;
 234         g->cflags = cflags;
 235         g->iflags = 0;
 236         g->nbol = 0;
 237         g->neol = 0;
 238         g->must = NULL;
 239         g->moffset = -1;
 240         g->charjump = NULL;
 241         g->matchjump = NULL;
 242         g->mlen = 0;
 243         g->nsub = 0;
 244         g->backrefs = 0;
 245 
 246         /* do it */
 247         EMIT(OEND, 0);
 248         g->firststate = THERE();
 249         if (cflags&REG_EXTENDED)
 250                 p_ere(p, OUT);
 251         else if (cflags&REG_NOSPEC)
 252                 p_str(p);
 253         else
 254                 p_bre(p, OUT, OUT);
 255         EMIT(OEND, 0);
 256         g->laststate = THERE();
 257 
 258         /* tidy up loose ends and fill things in */
 259         stripsnug(p, g);
 260         findmust(p, g);
 261         /*
 262          * only use Boyer-Moore algorithm if the pattern is bigger
 263          * than three characters
 264          */
 265         if (g->mlen > 3) {
 266                 computejumps(p, g);
 267                 computematchjumps(p, g);
 268                 if (g->matchjump == NULL && g->charjump != NULL) {
 269                         free(g->charjump);
 270                         g->charjump = NULL;
 271                 }
 272         }
 273         g->nplus = pluscount(p, g);
 274         g->magic = MAGIC2;
 275         preg->re_nsub = g->nsub;
 276         preg->re_g = g;
 277         preg->re_magic = MAGIC1;
 278 #ifndef REDEBUG
 279         /* not debugging, so can't rely on the assert() in regexec() */
 280         if (g->iflags&BAD)
 281                 SETERROR(REG_EFATAL);
 282 #endif
 283 
 284         /* win or lose, we're done */
 285         if (p->error != 0)   /* lose */
 286                 regfree(preg);
 287         return (p->error);
 288 }
 289 
 290 /*
 291  * p_ere - ERE parser top level, concatenation and alternation
 292  */
 293 static void
 294 p_ere(struct parse *p,
 295     int stop)           /* character this ERE should end at */
 296 {
 297         char c;
 298         sopno prevback;
 299         sopno prevfwd;
 300         sopno conc;
 301         int first = 1;          /* is this the first alternative? */
 302 
 303         for (;;) {
 304                 /* do a bunch of concatenated expressions */
 305                 conc = HERE();
 306                 while (MORE() && (c = PEEK()) != '|' && c != stop)
 307                         p_ere_exp(p);
 308                 /* require nonempty */
 309                 (void) REQUIRE(HERE() != conc, REG_BADPAT);
 310 
 311                 if (!EAT('|'))
 312                         break;          /* NOTE BREAK OUT */
 313 
 314                 if (first) {
 315                         INSERT(OCH_, conc);     /* offset is wrong */
 316                         prevfwd = conc;
 317                         prevback = conc;
 318                         first = 0;
 319                 }
 320                 ASTERN(OOR1, prevback);
 321                 prevback = THERE();
 322                 AHEAD(prevfwd);                 /* fix previous offset */
 323                 prevfwd = HERE();
 324                 EMIT(OOR2, 0);                  /* offset is very wrong */
 325         }
 326 
 327         if (!first) {           /* tail-end fixups */
 328                 AHEAD(prevfwd);
 329                 ASTERN(O_CH, prevback);
 330         }
 331 
 332         assert(!MORE() || SEE(stop));
 333 }
 334 
 335 /*
 336  * p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
 337  */
 338 static void
 339 p_ere_exp(struct parse *p)
 340 {
 341         char c;
 342         wint_t wc;
 343         sopno pos;
 344         int count;
 345         int count2;
 346         sopno subno;
 347         int wascaret = 0;
 348 
 349         assert(MORE());         /* caller should have ensured this */
 350         c = GETNEXT();
 351 
 352         pos = HERE();
 353         switch (c) {
 354         case '(':
 355                 (void) REQUIRE(MORE(), REG_EPAREN);
 356                 p->g->nsub++;
 357                 subno = p->g->nsub;
 358                 if (subno < NPAREN)
 359                         p->pbegin[subno] = HERE();
 360                 EMIT(OLPAREN, subno);
 361                 if (!SEE(')'))
 362                         p_ere(p, ')');
 363                 if (subno < NPAREN) {
 364                         p->pend[subno] = HERE();
 365                         assert(p->pend[subno] != 0);
 366                 }
 367                 EMIT(ORPAREN, subno);
 368                 (void) MUSTEAT(')', REG_EPAREN);
 369                 break;
 370 #ifndef POSIX_MISTAKE
 371         case ')':               /* happens only if no current unmatched ( */
 372                 /*
 373                  * You may ask, why the ifndef?  Because I didn't notice
 374                  * this until slightly too late for 1003.2, and none of the
 375                  * other 1003.2 regular-expression reviewers noticed it at
 376                  * all.  So an unmatched ) is legal POSIX, at least until
 377                  * we can get it fixed.
 378                  */
 379                 SETERROR(REG_EPAREN);
 380                 break;
 381 #endif
 382         case '^':
 383                 EMIT(OBOL, 0);
 384                 p->g->iflags |= USEBOL;
 385                 p->g->nbol++;
 386                 wascaret = 1;
 387                 break;
 388         case '$':
 389                 EMIT(OEOL, 0);
 390                 p->g->iflags |= USEEOL;
 391                 p->g->neol++;
 392                 break;
 393         case '|':
 394                 SETERROR(REG_BADPAT);
 395                 break;
 396         case '*':
 397         case '+':
 398         case '?':
 399         case '{':
 400                 SETERROR(REG_BADRPT);
 401                 break;
 402         case '.':
 403                 if (p->g->cflags&REG_NEWLINE)
 404                         nonnewline(p);
 405                 else
 406                         EMIT(OANY, 0);
 407                 break;
 408         case '[':
 409                 p_bracket(p);
 410                 break;
 411         case '\\':
 412                 (void) REQUIRE(MORE(), REG_EESCAPE);
 413                 wc = WGETNEXT();
 414                 switch (wc) {
 415                 case '<':
 416                         EMIT(OBOW, 0);
 417                         break;
 418                 case '>':
 419                         EMIT(OEOW, 0);
 420                         break;
 421                 default:
 422                         ordinary(p, wc);
 423                         break;
 424                 }
 425                 break;
 426         default:
 427                 if (p->error != 0)
 428                         return;
 429                 p->next--;
 430                 wc = WGETNEXT();
 431                 ordinary(p, wc);
 432                 break;
 433         }
 434 
 435         if (!MORE())
 436                 return;
 437         c = PEEK();
 438         /* we call { a repetition if followed by a digit */
 439         if (!(c == '*' || c == '+' || c == '?' || c == '{'))
 440                 return;         /* no repetition, we're done */
 441         else if (c == '{')
 442                 (void) REQUIRE(MORE2() && \
 443                     (isdigit((uch)PEEK2()) || PEEK2() == ','), REG_BADRPT);
 444         NEXT();
 445 
 446         (void) REQUIRE(!wascaret, REG_BADRPT);
 447         switch (c) {
 448         case '*':       /* implemented as +? */
 449                 /* this case does not require the (y|) trick, noKLUDGE */
 450                 INSERT(OPLUS_, pos);
 451                 ASTERN(O_PLUS, pos);
 452                 INSERT(OQUEST_, pos);
 453                 ASTERN(O_QUEST, pos);
 454                 break;
 455         case '+':
 456                 INSERT(OPLUS_, pos);
 457                 ASTERN(O_PLUS, pos);
 458                 break;
 459         case '?':
 460                 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
 461                 INSERT(OCH_, pos);              /* offset slightly wrong */
 462                 ASTERN(OOR1, pos);              /* this one's right */
 463                 AHEAD(pos);                     /* fix the OCH_ */
 464                 EMIT(OOR2, 0);                  /* offset very wrong... */
 465                 AHEAD(THERE());                 /* ...so fix it */
 466                 ASTERN(O_CH, THERETHERE());
 467                 break;
 468         case '{':
 469                 count = p_count(p);
 470                 if (EAT(',')) {
 471                         if (isdigit((uch)PEEK())) {
 472                                 count2 = p_count(p);
 473                                 (void) REQUIRE(count <= count2, REG_BADBR);
 474                         } else          /* single number with comma */
 475                                 count2 = INFINITY;
 476                 } else          /* just a single number */
 477                         count2 = count;
 478                 repeat(p, pos, count, count2);
 479                 if (!EAT('}')) {        /* error heuristics */
 480                         while (MORE() && PEEK() != '}')
 481                                 NEXT();
 482                         (void) REQUIRE(MORE(), REG_EBRACE);
 483                         SETERROR(REG_BADBR);
 484                 }
 485                 break;
 486         }
 487 
 488         if (!MORE())
 489                 return;
 490         c = PEEK();
 491         if (!(c == '*' || c == '+' || c == '?' ||
 492             (c == '{' && MORE2() && isdigit((uch)PEEK2()))))
 493                 return;
 494         SETERROR(REG_BADRPT);
 495 }
 496 
 497 /*
 498  * p_str - string (no metacharacters) "parser"
 499  */
 500 static void
 501 p_str(struct parse *p)
 502 {
 503         (void) REQUIRE(MORE(), REG_BADPAT);
 504         while (MORE())
 505                 ordinary(p, WGETNEXT());
 506 }
 507 
 508 /*
 509  * p_bre - BRE parser top level, anchoring and concatenation
 510  * Giving end1 as OUT essentially eliminates the end1/end2 check.
 511  *
 512  * This implementation is a bit of a kludge, in that a trailing $ is first
 513  * taken as an ordinary character and then revised to be an anchor.
 514  * The amount of lookahead needed to avoid this kludge is excessive.
 515  */
 516 static void
 517 p_bre(struct parse *p,
 518     int end1,           /* first terminating character */
 519     int end2)           /* second terminating character */
 520 {
 521         sopno start = HERE();
 522         int first = 1;                  /* first subexpression? */
 523         int wasdollar = 0;
 524 
 525         if (EAT('^')) {
 526                 EMIT(OBOL, 0);
 527                 p->g->iflags |= USEBOL;
 528                 p->g->nbol++;
 529         }
 530         while (MORE() && !SEETWO(end1, end2)) {
 531                 wasdollar = p_simp_re(p, first);
 532                 first = 0;
 533         }
 534         if (wasdollar) {        /* oops, that was a trailing anchor */
 535                 DROP(1);
 536                 EMIT(OEOL, 0);
 537                 p->g->iflags |= USEEOL;
 538                 p->g->neol++;
 539         }
 540 
 541         (void) REQUIRE(HERE() != start, REG_BADPAT);    /* require nonempty */
 542 }
 543 
 544 /*
 545  * p_simp_re - parse a simple RE, an atom possibly followed by a repetition
 546  */
 547 static int                      /* was the simple RE an unbackslashed $? */
 548 p_simp_re(struct parse *p,
 549     int starordinary)   /* is a leading * an ordinary character? */
 550 {
 551         int c;
 552         int count;
 553         int count2;
 554         sopno pos;
 555         int i;
 556         wint_t wc;
 557         sopno subno;
 558 #define BACKSL  (1<<CHAR_BIT)
 559 
 560         pos = HERE();           /* repetition op, if any, covers from here */
 561 
 562         assert(MORE());         /* caller should have ensured this */
 563         c = GETNEXT();
 564         if (c == '\\') {
 565                 (void) REQUIRE(MORE(), REG_EESCAPE);
 566                 c = BACKSL | GETNEXT();
 567         }
 568         switch (c) {
 569         case '.':
 570                 if (p->g->cflags&REG_NEWLINE)
 571                         nonnewline(p);
 572                 else
 573                         EMIT(OANY, 0);
 574                 break;
 575         case '[':
 576                 p_bracket(p);
 577                 break;
 578         case BACKSL|'<':
 579                 EMIT(OBOW, 0);
 580                 break;
 581         case BACKSL|'>':
 582                 EMIT(OEOW, 0);
 583                 break;
 584         case BACKSL|'{':
 585                 SETERROR(REG_BADRPT);
 586                 break;
 587         case BACKSL|'(':
 588                 p->g->nsub++;
 589                 subno = p->g->nsub;
 590                 if (subno < NPAREN)
 591                         p->pbegin[subno] = HERE();
 592                 EMIT(OLPAREN, subno);
 593                 /* the MORE here is an error heuristic */
 594                 if (MORE() && !SEETWO('\\', ')'))
 595                         p_bre(p, '\\', ')');
 596                 if (subno < NPAREN) {
 597                         p->pend[subno] = HERE();
 598                         assert(p->pend[subno] != 0);
 599                 }
 600                 EMIT(ORPAREN, subno);
 601                 (void) REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
 602                 break;
 603         case BACKSL|')':        /* should not get here -- must be user */
 604                 SETERROR(REG_EPAREN);
 605                 break;
 606         case BACKSL|'1':
 607         case BACKSL|'2':
 608         case BACKSL|'3':
 609         case BACKSL|'4':
 610         case BACKSL|'5':
 611         case BACKSL|'6':
 612         case BACKSL|'7':
 613         case BACKSL|'8':
 614         case BACKSL|'9':
 615                 i = (c&~BACKSL) - '0';
 616                 assert(i < NPAREN);
 617                 if (p->pend[i] != 0) {
 618                         assert(i <= p->g->nsub);
 619                         EMIT(OBACK_, i);
 620                         assert(p->pbegin[i] != 0);
 621                         assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
 622                         assert(OP(p->strip[p->pend[i]]) == ORPAREN);
 623                         (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
 624                         EMIT(O_BACK, i);
 625                 } else
 626                         SETERROR(REG_ESUBREG);
 627                 p->g->backrefs = 1;
 628                 break;
 629         case '*':
 630                 (void) REQUIRE(starordinary, REG_BADRPT);
 631                 /* FALLTHROUGH */
 632         default:
 633                 if (p->error != 0)
 634                         return (0);     /* Definitely not $... */
 635                 p->next--;
 636                 wc = WGETNEXT();
 637                 ordinary(p, wc);
 638                 break;
 639         }
 640 
 641         if (EAT('*')) {         /* implemented as +? */
 642                 /* this case does not require the (y|) trick, noKLUDGE */
 643                 INSERT(OPLUS_, pos);
 644                 ASTERN(O_PLUS, pos);
 645                 INSERT(OQUEST_, pos);
 646                 ASTERN(O_QUEST, pos);
 647         } else if (EATTWO('\\', '{')) {
 648                 count = p_count(p);
 649                 if (EAT(',')) {
 650                         if (MORE() && isdigit((uch)PEEK())) {
 651                                 count2 = p_count(p);
 652                                 (void) REQUIRE(count <= count2, REG_BADBR);
 653                         } else          /* single number with comma */
 654                                 count2 = INFINITY;
 655                 } else          /* just a single number */
 656                         count2 = count;
 657                 repeat(p, pos, count, count2);
 658                 if (!EATTWO('\\', '}')) {       /* error heuristics */
 659                         while (MORE() && !SEETWO('\\', '}'))
 660                                 NEXT();
 661                         (void) REQUIRE(MORE(), REG_EBRACE);
 662                         SETERROR(REG_BADBR);
 663                 }
 664         } else if (c == '$')    /* $ (but not \$) ends it */
 665                 return (1);
 666 
 667         return (0);
 668 }
 669 
 670 /*
 671  * p_count - parse a repetition count
 672  */
 673 static int                      /* the value */
 674 p_count(struct parse *p)
 675 {
 676         int count = 0;
 677         int ndigits = 0;
 678 
 679         while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) {
 680                 count = count*10 + (GETNEXT() - '0');
 681                 ndigits++;
 682         }
 683 
 684         (void) REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
 685         return (count);
 686 }
 687 
 688 /*
 689  * p_bracket - parse a bracketed character list
 690  */
 691 static void
 692 p_bracket(struct parse *p)
 693 {
 694         cset *cs;
 695         wint_t ch;
 696 
 697         /* Dept of Truly Sickening Special-Case Kludges */
 698         if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
 699                 EMIT(OBOW, 0);
 700                 NEXTn(6);
 701                 return;
 702         }
 703         if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
 704                 EMIT(OEOW, 0);
 705                 NEXTn(6);
 706                 return;
 707         }
 708 
 709         if ((cs = allocset(p)) == NULL)
 710                 return;
 711 
 712         if (p->g->cflags&REG_ICASE)
 713                 cs->icase = 1;
 714         if (EAT('^'))
 715                 cs->invert = 1;
 716         if (EAT(']'))
 717                 CHadd(p, cs, ']');
 718         else if (EAT('-'))
 719                 CHadd(p, cs, '-');
 720         while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
 721                 p_b_term(p, cs);
 722         if (EAT('-'))
 723                 CHadd(p, cs, '-');
 724         (void) MUSTEAT(']', REG_EBRACK);
 725 
 726         if (p->error != 0)   /* don't mess things up further */
 727                 return;
 728 
 729         if (cs->invert && p->g->cflags&REG_NEWLINE)
 730                 cs->bmp['\n' >> 3] |= 1 << ('\n' & 7);
 731 
 732         if ((ch = singleton(cs)) != OUT) {      /* optimize singleton sets */
 733                 ordinary(p, ch);
 734                 freeset(p, cs);
 735         } else
 736                 EMIT(OANYOF, (int)(cs - p->g->sets));
 737 }
 738 
 739 /*
 740  * p_b_term - parse one term of a bracketed character list
 741  */
 742 static void
 743 p_b_term(struct parse *p, cset *cs)
 744 {
 745         char c;
 746         wint_t start, finish;
 747         wint_t i;
 748         locale_t loc = uselocale(NULL);
 749 
 750         /* classify what we've got */
 751         switch ((MORE()) ? PEEK() : '\0') {
 752         case '[':
 753                 c = (MORE2()) ? PEEK2() : '\0';
 754                 break;
 755         case '-':
 756                 SETERROR(REG_ERANGE);
 757                 return;                 /* NOTE RETURN */
 758         default:
 759                 c = '\0';
 760                 break;
 761         }
 762 
 763         switch (c) {
 764         case ':':               /* character class */
 765                 NEXT2();
 766                 (void) REQUIRE(MORE(), REG_EBRACK);
 767                 c = PEEK();
 768                 (void) REQUIRE(c != '-' && c != ']', REG_ECTYPE);
 769                 p_b_cclass(p, cs);
 770                 (void) REQUIRE(MORE(), REG_EBRACK);
 771                 (void) REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
 772                 break;
 773         case '=':               /* equivalence class */
 774                 NEXT2();
 775                 (void) REQUIRE(MORE(), REG_EBRACK);
 776                 c = PEEK();
 777                 (void) REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
 778                 p_b_eclass(p, cs);
 779                 (void) REQUIRE(MORE(), REG_EBRACK);
 780                 (void) REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
 781                 break;
 782         default:                /* symbol, ordinary character, or range */
 783                 start = p_b_symbol(p);
 784                 if (SEE('-') && MORE2() && PEEK2() != ']') {
 785                         /* range */
 786                         NEXT();
 787                         if (EAT('-'))
 788                                 finish = '-';
 789                         else
 790                                 finish = p_b_symbol(p);
 791                 } else
 792                         finish = start;
 793                 if (start == finish)
 794                         CHadd(p, cs, start);
 795                 else {
 796                         if (loc->collate->lc_is_posix) {
 797                                 (void) REQUIRE((uch)start <= (uch)finish,
 798                                     REG_ERANGE);
 799                                 CHaddrange(p, cs, start, finish);
 800                         } else {
 801                                 (void) REQUIRE(_collate_range_cmp(start,
 802                                     finish, loc) <= 0, REG_ERANGE);
 803                                 for (i = 0; i <= UCHAR_MAX; i++) {
 804                                         if (_collate_range_cmp(start, i, loc)
 805                                             <= 0 &&
 806                                             _collate_range_cmp(i, finish, loc)
 807                                             <= 0)
 808                                                 CHadd(p, cs, i);
 809                                 }
 810                         }
 811                 }
 812                 break;
 813         }
 814 }
 815 
 816 /*
 817  * p_b_cclass - parse a character-class name and deal with it
 818  */
 819 static void
 820 p_b_cclass(struct parse *p, cset *cs)
 821 {
 822         const char *sp = p->next;
 823         size_t len;
 824         wctype_t wct;
 825         char clname[16];
 826 
 827         while (MORE() && isalpha((uch)PEEK()))
 828                 NEXT();
 829         len = p->next - sp;
 830         if (len >= sizeof (clname) - 1) {
 831                 SETERROR(REG_ECTYPE);
 832                 return;
 833         }
 834         (void) memcpy(clname, sp, len);
 835         clname[len] = '\0';
 836         if ((wct = wctype(clname)) == 0) {
 837                 SETERROR(REG_ECTYPE);
 838                 return;
 839         }
 840         CHaddtype(p, cs, wct);
 841 }
 842 
 843 /*
 844  * p_b_eclass - parse an equivalence-class name and deal with it
 845  *
 846  * This implementation is incomplete. xxx
 847  */
 848 static void
 849 p_b_eclass(struct parse *p, cset *cs)
 850 {
 851         wint_t c;
 852 
 853         c = p_b_coll_elem(p, '=');
 854         CHadd(p, cs, c);
 855 }
 856 
 857 /*
 858  * p_b_symbol - parse a character or [..]ed multicharacter collating symbol
 859  */
 860 static wint_t                   /* value of symbol */
 861 p_b_symbol(struct parse *p)
 862 {
 863         wint_t value;
 864 
 865         (void) REQUIRE(MORE(), REG_EBRACK);
 866         if (!EATTWO('[', '.'))
 867                 return (WGETNEXT());
 868 
 869         /* collating symbol */
 870         value = p_b_coll_elem(p, '.');
 871         (void) REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
 872         return (value);
 873 }
 874 
 875 /*
 876  * p_b_coll_elem - parse a collating-element name and look it up
 877  */
 878 static wint_t                   /* value of collating element */
 879 p_b_coll_elem(struct parse *p,
 880     wint_t endc)                /* name ended by endc,']' */
 881 {
 882         const char *sp = p->next;
 883         struct cname *cp;
 884         mbstate_t mbs;
 885         wchar_t wc;
 886         size_t clen, len;
 887 
 888         while (MORE() && !SEETWO(endc, ']'))
 889                 NEXT();
 890         if (!MORE()) {
 891                 SETERROR(REG_EBRACK);
 892                 return (0);
 893         }
 894         len = p->next - sp;
 895         for (cp = cnames; cp->name != NULL; cp++)
 896                 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
 897                         return (cp->code);   /* known name */
 898         (void) memset(&mbs, 0, sizeof (mbs));
 899         if ((clen = mbrtowc(&wc, sp, len, &mbs)) == len)
 900                 return (wc);                    /* single character */
 901         else if (clen == (size_t)-1 || clen == (size_t)-2)
 902                 SETERROR(REG_ECHAR);
 903         else
 904                 SETERROR(REG_ECOLLATE);         /* neither */
 905         return (0);
 906 }
 907 
 908 /*
 909  * othercase - return the case counterpart of an alphabetic
 910  */
 911 static wint_t                   /* if no counterpart, return ch */
 912 othercase(wint_t ch)
 913 {
 914         assert(iswalpha(ch));
 915         if (iswupper(ch))
 916                 return (towlower(ch));
 917         else if (iswlower(ch))
 918                 return (towupper(ch));
 919         else                    /* peculiar, but could happen */
 920                 return (ch);
 921 }
 922 
 923 /*
 924  * bothcases - emit a dualcase version of a two-case character
 925  *
 926  * Boy, is this implementation ever a kludge...
 927  */
 928 static void
 929 bothcases(struct parse *p, wint_t ch)
 930 {
 931         const char *oldnext = p->next;
 932         const char *oldend = p->end;
 933         char bracket[3 + MB_LEN_MAX];
 934         size_t n;
 935         mbstate_t mbs;
 936 
 937         assert(othercase(ch) != ch);    /* p_bracket() would recurse */
 938         p->next = bracket;
 939         (void) memset(&mbs, 0, sizeof (mbs));
 940         n = wcrtomb(bracket, ch, &mbs);
 941         assert(n != (size_t)-1);
 942         bracket[n] = ']';
 943         bracket[n + 1] = '\0';
 944         p->end = bracket+n+1;
 945         p_bracket(p);
 946         assert(p->next == p->end);
 947         p->next = oldnext;
 948         p->end = oldend;
 949 }
 950 
 951 /*
 952  * ordinary - emit an ordinary character
 953  */
 954 static void
 955 ordinary(struct parse *p, wint_t ch)
 956 {
 957         cset *cs;
 958 
 959         if ((p->g->cflags&REG_ICASE) && iswalpha(ch) && othercase(ch) != ch)
 960                 bothcases(p, ch);
 961         else if ((ch & OPDMASK) == ch)
 962                 EMIT(OCHAR, ch);
 963         else {
 964                 /*
 965                  * Kludge: character is too big to fit into an OCHAR operand.
 966                  * Emit a singleton set.
 967                  */
 968                 if ((cs = allocset(p)) == NULL)
 969                         return;
 970                 CHadd(p, cs, ch);
 971                 EMIT(OANYOF, (int)(cs - p->g->sets));
 972         }
 973 }
 974 
 975 /*
 976  * nonnewline - emit REG_NEWLINE version of OANY
 977  *
 978  * Boy, is this implementation ever a kludge...
 979  */
 980 static void
 981 nonnewline(struct parse *p)
 982 {
 983         const char *oldnext = p->next;
 984         const char *oldend = p->end;
 985         char bracket[4];
 986 
 987         p->next = bracket;
 988         p->end = bracket+3;
 989         bracket[0] = '^';
 990         bracket[1] = '\n';
 991         bracket[2] = ']';
 992         bracket[3] = '\0';
 993         p_bracket(p);
 994         assert(p->next == bracket+3);
 995         p->next = oldnext;
 996         p->end = oldend;
 997 }
 998 
 999 /*
1000  * repeat - generate code for a bounded repetition, recursively if needed
1001  */
1002 static void
1003 repeat(struct parse *p,
1004     sopno start,                /* operand from here to end of strip */
1005     int from,                   /* repeated from this number */
1006     int to)                     /* to this number of times (maybe INFINITY) */
1007 {
1008         sopno finish = HERE();
1009 #define N       2
1010 #define INF     3
1011 #define REP(f, t)       ((f)*8 + (t))
1012 #define MAP(n)  (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1013         sopno copy;
1014 
1015         if (p->error != 0)   /* head off possible runaway recursion */
1016                 return;
1017 
1018         assert(from <= to);
1019 
1020         switch (REP(MAP(from), MAP(to))) {
1021         case REP(0, 0):                 /* must be user doing this */
1022                 DROP(finish-start);     /* drop the operand */
1023                 break;
1024         case REP(0, 1):                 /* as x{1,1}? */
1025         case REP(0, N):                 /* as x{1,n}? */
1026         case REP(0, INF):               /* as x{1,}? */
1027                 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1028                 INSERT(OCH_, start);            /* offset is wrong... */
1029                 repeat(p, start+1, 1, to);
1030                 ASTERN(OOR1, start);
1031                 AHEAD(start);                   /* ... fix it */
1032                 EMIT(OOR2, 0);
1033                 AHEAD(THERE());
1034                 ASTERN(O_CH, THERETHERE());
1035                 break;
1036         case REP(1, 1):                 /* trivial case */
1037                 /* done */
1038                 break;
1039         case REP(1, N):                 /* as x?x{1,n-1} */
1040                 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1041                 INSERT(OCH_, start);
1042                 ASTERN(OOR1, start);
1043                 AHEAD(start);
1044                 EMIT(OOR2, 0);                  /* offset very wrong... */
1045                 AHEAD(THERE());                 /* ...so fix it */
1046                 ASTERN(O_CH, THERETHERE());
1047                 copy = dupl(p, start+1, finish+1);
1048                 assert(copy == finish+4);
1049                 repeat(p, copy, 1, to-1);
1050                 break;
1051         case REP(1, INF):               /* as x+ */
1052                 INSERT(OPLUS_, start);
1053                 ASTERN(O_PLUS, start);
1054                 break;
1055         case REP(N, N):                 /* as xx{m-1,n-1} */
1056                 copy = dupl(p, start, finish);
1057                 repeat(p, copy, from-1, to-1);
1058                 break;
1059         case REP(N, INF):               /* as xx{n-1,INF} */
1060                 copy = dupl(p, start, finish);
1061                 repeat(p, copy, from-1, to);
1062                 break;
1063         default:                        /* "can't happen" */
1064                 SETERROR(REG_EFATAL);   /* just in case */
1065                 break;
1066         }
1067 }
1068 
1069 /*
1070  * wgetnext - helper function for WGETNEXT() macro. Gets the next wide
1071  * character from the parse struct, signals a REG_ILLSEQ error if the
1072  * character can't be converted. Returns the number of bytes consumed.
1073  */
1074 static wint_t
1075 wgetnext(struct parse *p)
1076 {
1077         mbstate_t mbs;
1078         wchar_t wc;
1079         size_t n;
1080 
1081         (void) memset(&mbs, 0, sizeof (mbs));
1082         n = mbrtowc(&wc, p->next, p->end - p->next, &mbs);
1083         if (n == (size_t)-1 || n == (size_t)-2) {
1084                 SETERROR(REG_ECHAR);
1085                 return (0);
1086         }
1087         if (n == 0)
1088                 n = 1;
1089         p->next += n;
1090         return (wc);
1091 }
1092 
1093 /*
1094  * seterr - set an error condition
1095  */
1096 static int                      /* useless but makes type checking happy */
1097 seterr(struct parse *p, int e)
1098 {
1099         if (p->error == 0)   /* keep earliest error condition */
1100                 p->error = e;
1101         p->next = nuls;              /* try to bring things to a halt */
1102         p->end = nuls;
1103         return (0);             /* make the return value well-defined */
1104 }
1105 
1106 /*
1107  * allocset - allocate a set of characters for []
1108  */
1109 static cset *
1110 allocset(struct parse *p)
1111 {
1112         cset *cs, *ncs;
1113 
1114         ncs = realloc(p->g->sets, (p->g->ncsets + 1) * sizeof (*ncs));
1115         if (ncs == NULL) {
1116                 SETERROR(REG_ESPACE);
1117                 return (NULL);
1118         }
1119         p->g->sets = ncs;
1120         cs = &p->g->sets[p->g->ncsets++];
1121         (void) memset(cs, 0, sizeof (*cs));
1122 
1123         return (cs);
1124 }
1125 
1126 /*
1127  * freeset - free a now-unused set
1128  */
1129 static void
1130 freeset(struct parse *p, cset *cs)
1131 {
1132         cset *top = &p->g->sets[p->g->ncsets];
1133 
1134         free(cs->wides);
1135         free(cs->ranges);
1136         free(cs->types);
1137         (void) memset(cs, 0, sizeof (*cs));
1138         if (cs == top-1)        /* recover only the easy case */
1139                 p->g->ncsets--;
1140 }
1141 
1142 /*
1143  * singleton - Determine whether a set contains only one character,
1144  * returning it if so, otherwise returning OUT.
1145  */
1146 static wint_t
1147 singleton(cset *cs)
1148 {
1149         wint_t i, s, n;
1150 
1151         for (i = n = 0; i < NC; i++)
1152                 if (CHIN(cs, i)) {
1153                         n++;
1154                         s = i;
1155                 }
1156         if (n == 1)
1157                 return (s);
1158         if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 &&
1159             cs->icase == 0)
1160                 return (cs->wides[0]);
1161         /* Don't bother handling the other cases. */
1162         return (OUT);
1163 }
1164 
1165 /*
1166  * CHadd - add character to character set.
1167  */
1168 static void
1169 CHadd(struct parse *p, cset *cs, wint_t ch)
1170 {
1171         wint_t nch, *newwides;
1172         assert(ch >= 0);
1173         if (ch < NC)
1174                 cs->bmp[ch >> 3] |= 1 << (ch & 7);
1175         else {
1176                 newwides = realloc(cs->wides, (cs->nwides + 1) *
1177                     sizeof (*cs->wides));
1178                 if (newwides == NULL) {
1179                         SETERROR(REG_ESPACE);
1180                         return;
1181                 }
1182                 cs->wides = newwides;
1183                 cs->wides[cs->nwides++] = ch;
1184         }
1185         if (cs->icase) {
1186                 if ((nch = towlower(ch)) < NC)
1187                         cs->bmp[nch >> 3] |= 1 << (nch & 7);
1188                 if ((nch = towupper(ch)) < NC)
1189                         cs->bmp[nch >> 3] |= 1 << (nch & 7);
1190         }
1191 }
1192 
1193 /*
1194  * CHaddrange - add all characters in the range [min,max] to a character set.
1195  */
1196 static void
1197 CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max)
1198 {
1199         crange *newranges;
1200 
1201         for (; min < NC && min <= max; min++)
1202                 CHadd(p, cs, min);
1203         if (min >= max)
1204                 return;
1205         newranges = realloc(cs->ranges, (cs->nranges + 1) *
1206             sizeof (*cs->ranges));
1207         if (newranges == NULL) {
1208                 SETERROR(REG_ESPACE);
1209                 return;
1210         }
1211         cs->ranges = newranges;
1212         cs->ranges[cs->nranges].min = min;
1213         cs->ranges[cs->nranges].max = max;
1214         cs->nranges++;
1215 }
1216 
1217 /*
1218  * CHaddtype - add all characters of a certain type to a character set.
1219  */
1220 static void
1221 CHaddtype(struct parse *p, cset *cs, wctype_t wct)
1222 {
1223         wint_t i;
1224         wctype_t *newtypes;
1225 
1226         for (i = 0; i < NC; i++)
1227                 if (iswctype(i, wct))
1228                         CHadd(p, cs, i);
1229         newtypes = realloc(cs->types, (cs->ntypes + 1) *
1230             sizeof (*cs->types));
1231         if (newtypes == NULL) {
1232                 SETERROR(REG_ESPACE);
1233                 return;
1234         }
1235         cs->types = newtypes;
1236         cs->types[cs->ntypes++] = wct;
1237 }
1238 
1239 /*
1240  * dupl - emit a duplicate of a bunch of sops
1241  */
1242 static sopno                    /* start of duplicate */
1243 dupl(struct parse *p,
1244     sopno start,                /* from here */
1245     sopno finish)               /* to this less one */
1246 {
1247         sopno ret = HERE();
1248         sopno len = finish - start;
1249 
1250         assert(finish >= start);
1251         if (len == 0)
1252                 return (ret);
1253         if (!enlarge(p, p->ssize + len)) /* this many unexpected additions */
1254                 return (ret);
1255         assert(p->ssize >= p->slen + len);
1256         (void) memcpy((char *)(p->strip + p->slen),
1257             (char *)(p->strip + start), (size_t)len*sizeof (sop));
1258         p->slen += len;
1259         return (ret);
1260 }
1261 
1262 /*
1263  * doemit - emit a strip operator
1264  *
1265  * It might seem better to implement this as a macro with a function as
1266  * hard-case backup, but it's just too big and messy unless there are
1267  * some changes to the data structures.  Maybe later.
1268  */
1269 static void
1270 doemit(struct parse *p, sop op, size_t opnd)
1271 {
1272         /* avoid making error situations worse */
1273         if (p->error != 0)
1274                 return;
1275 
1276         /* deal with oversize operands ("can't happen", more or less) */
1277         assert(opnd < 1<<OPSHIFT);
1278 
1279         /* deal with undersized strip */
1280         if (p->slen >= p->ssize)
1281                 if (!enlarge(p, (p->ssize+1) / 2 * 3))       /* +50% */
1282                         return;
1283 
1284         /* finally, it's all reduced to the easy case */
1285         p->strip[p->slen++] = SOP(op, opnd);
1286 }
1287 
1288 /*
1289  * doinsert - insert a sop into the strip
1290  */
1291 static void
1292 doinsert(struct parse *p, sop op, size_t opnd, sopno pos)
1293 {
1294         sopno sn;
1295         sop s;
1296         int i;
1297 
1298         /* avoid making error situations worse */
1299         if (p->error != 0)
1300                 return;
1301 
1302         sn = HERE();
1303         EMIT(op, opnd);         /* do checks, ensure space */
1304         assert(HERE() == sn+1);
1305         s = p->strip[sn];
1306 
1307         /* adjust paren pointers */
1308         assert(pos > 0);
1309         for (i = 1; i < NPAREN; i++) {
1310                 if (p->pbegin[i] >= pos) {
1311                         p->pbegin[i]++;
1312                 }
1313                 if (p->pend[i] >= pos) {
1314                         p->pend[i]++;
1315                 }
1316         }
1317 
1318         (void) memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
1319             (HERE()-pos-1)*sizeof (sop));
1320         p->strip[pos] = s;
1321 }
1322 
1323 /*
1324  * dofwd - complete a forward reference
1325  */
1326 static void
1327 dofwd(struct parse *p, sopno pos, sop value)
1328 {
1329         /* avoid making error situations worse */
1330         if (p->error != 0)
1331                 return;
1332 
1333         assert(value < 1<<OPSHIFT);
1334         p->strip[pos] = OP(p->strip[pos]) | value;
1335 }
1336 
1337 /*
1338  * enlarge - enlarge the strip
1339  */
1340 static int
1341 enlarge(struct parse *p, sopno size)
1342 {
1343         sop *sp;
1344 
1345         if (p->ssize >= size)
1346                 return (1);
1347 
1348         sp = (sop *)realloc(p->strip, size*sizeof (sop));
1349         if (sp == NULL) {
1350                 SETERROR(REG_ESPACE);
1351                 return (0);
1352         }
1353         p->strip = sp;
1354         p->ssize = size;
1355         return (1);
1356 }
1357 
1358 /*
1359  * stripsnug - compact the strip
1360  */
1361 static void
1362 stripsnug(struct parse *p, struct re_guts *g)
1363 {
1364         g->nstates = p->slen;
1365         g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof (sop));
1366         if (g->strip == NULL) {
1367                 SETERROR(REG_ESPACE);
1368                 g->strip = p->strip;
1369         }
1370 }
1371 
1372 /*
1373  * findmust - fill in must and mlen with longest mandatory literal string
1374  *
1375  * This algorithm could do fancy things like analyzing the operands of |
1376  * for common subsequences.  Someday.  This code is simple and finds most
1377  * of the interesting cases.
1378  *
1379  * Note that must and mlen got initialized during setup.
1380  */
1381 static void
1382 findmust(struct parse *p, struct re_guts *g)
1383 {
1384         sop *scan;
1385         sop *start = NULL;
1386         sop *newstart = NULL;
1387         sopno newlen;
1388         sop s;
1389         char *cp;
1390         int offset;
1391         char buf[MB_LEN_MAX];
1392         size_t clen;
1393         mbstate_t mbs;
1394         locale_t loc = uselocale(NULL);
1395 
1396         /* avoid making error situations worse */
1397         if (p->error != 0)
1398                 return;
1399 
1400         /*
1401          * It's not generally safe to do a ``char'' substring search on
1402          * multibyte character strings, but it's safe for at least
1403          * UTF-8 (see RFC 3629).
1404          */
1405         if (MB_CUR_MAX > 1 &&
1406             strcmp(loc->runelocale->__encoding, "UTF-8") != 0)
1407                 return;
1408 
1409         /* find the longest OCHAR sequence in strip */
1410         newlen = 0;
1411         offset = 0;
1412         g->moffset = 0;
1413         scan = g->strip + 1;
1414         do {
1415                 s = *scan++;
1416                 switch (OP(s)) {
1417                 case OCHAR:             /* sequence member */
1418                         if (newlen == 0) {              /* new sequence */
1419                                 (void) memset(&mbs, 0, sizeof (mbs));
1420                                 newstart = scan - 1;
1421                         }
1422                         clen = wcrtomb(buf, OPND(s), &mbs);
1423                         if (clen == (size_t)-1)
1424                                 goto toohard;
1425                         newlen += clen;
1426                         break;
1427                 case OPLUS_:            /* things that don't break one */
1428                 case OLPAREN:
1429                 case ORPAREN:
1430                         break;
1431                 case OQUEST_:           /* things that must be skipped */
1432                 case OCH_:
1433                         offset = altoffset(scan, offset);
1434                         scan--;
1435                         do {
1436                                 scan += OPND(s);
1437                                 s = *scan;
1438                                 /* assert() interferes w debug printouts */
1439                                 if (OP(s) != O_QUEST && OP(s) != O_CH &&
1440                                     OP(s) != OOR2) {
1441                                         g->iflags |= BAD;
1442                                         return;
1443                                 }
1444                         } while (OP(s) != O_QUEST && OP(s) != O_CH);
1445                         /* FALLTHROUGH */
1446                 case OBOW:              /* things that break a sequence */
1447                 case OEOW:
1448                 case OBOL:
1449                 case OEOL:
1450                 case O_QUEST:
1451                 case O_CH:
1452                 case OEND:
1453                         if (newlen > g->mlen) {           /* ends one */
1454                                 start = newstart;
1455                                 g->mlen = newlen;
1456                                 if (offset > -1) {
1457                                         g->moffset += offset;
1458                                         offset = newlen;
1459                                 } else
1460                                         g->moffset = offset;
1461                         } else {
1462                                 if (offset > -1)
1463                                         offset += newlen;
1464                         }
1465                         newlen = 0;
1466                         break;
1467                 case OANY:
1468                         if (newlen > g->mlen) {           /* ends one */
1469                                 start = newstart;
1470                                 g->mlen = newlen;
1471                                 if (offset > -1) {
1472                                         g->moffset += offset;
1473                                         offset = newlen;
1474                                 } else
1475                                         g->moffset = offset;
1476                         } else {
1477                                 if (offset > -1)
1478                                         offset += newlen;
1479                         }
1480                         if (offset > -1)
1481                                 offset++;
1482                         newlen = 0;
1483                         break;
1484                 case OANYOF:            /* may or may not invalidate offset */
1485                         /* First, everything as OANY */
1486                         if (newlen > g->mlen) {           /* ends one */
1487                                 start = newstart;
1488                                 g->mlen = newlen;
1489                                 if (offset > -1) {
1490                                         g->moffset += offset;
1491                                         offset = newlen;
1492                                 } else
1493                                         g->moffset = offset;
1494                         } else {
1495                                 if (offset > -1)
1496                                         offset += newlen;
1497                         }
1498                         if (offset > -1)
1499                                 offset++;
1500                         newlen = 0;
1501                         break;
1502                 toohard:
1503                 default:
1504                         /*
1505                          * Anything here makes it impossible or too hard
1506                          * to calculate the offset -- so we give up;
1507                          * save the last known good offset, in case the
1508                          * must sequence doesn't occur later.
1509                          */
1510                         if (newlen > g->mlen) {           /* ends one */
1511                                 start = newstart;
1512                                 g->mlen = newlen;
1513                                 if (offset > -1)
1514                                         g->moffset += offset;
1515                                 else
1516                                         g->moffset = offset;
1517                         }
1518                         offset = -1;
1519                         newlen = 0;
1520                         break;
1521                 }
1522         } while (OP(s) != OEND);
1523 
1524         if (g->mlen == 0) {          /* there isn't one */
1525                 g->moffset = -1;
1526                 return;
1527         }
1528 
1529         /* turn it into a character string */
1530         g->must = malloc((size_t)g->mlen + 1);
1531         if (g->must == NULL) {               /* argh; just forget it */
1532                 g->mlen = 0;
1533                 g->moffset = -1;
1534                 return;
1535         }
1536         cp = g->must;
1537         scan = start;
1538         (void) memset(&mbs, 0, sizeof (mbs));
1539         while (cp < g->must + g->mlen) {
1540                 while (OP(s = *scan++) != OCHAR)
1541                         continue;
1542                 clen = wcrtomb(cp, OPND(s), &mbs);
1543                 assert(clen != (size_t)-1);
1544                 cp += clen;
1545         }
1546         assert(cp == g->must + g->mlen);
1547         *cp++ = '\0';           /* just on general principles */
1548 }
1549 
1550 /*
1551  * altoffset - choose biggest offset among multiple choices
1552  *
1553  * Compute, recursively if necessary, the largest offset among multiple
1554  * re paths.
1555  */
1556 static int
1557 altoffset(sop *scan, int offset)
1558 {
1559         int largest;
1560         int try;
1561         sop s;
1562 
1563         /* If we gave up already on offsets, return */
1564         if (offset == -1)
1565                 return (-1);
1566 
1567         largest = 0;
1568         try = 0;
1569         s = *scan++;
1570         while (OP(s) != O_QUEST && OP(s) != O_CH) {
1571                 switch (OP(s)) {
1572                 case OOR1:
1573                         if (try > largest)
1574                                 largest = try;
1575                         try = 0;
1576                         break;
1577                 case OQUEST_:
1578                 case OCH_:
1579                         try = altoffset(scan, try);
1580                         if (try == -1)
1581                                 return (-1);
1582                         scan--;
1583                         do {
1584                                 scan += OPND(s);
1585                                 s = *scan;
1586                                 if (OP(s) != O_QUEST && OP(s) != O_CH &&
1587                                     OP(s) != OOR2)
1588                                         return (-1);
1589                         } while (OP(s) != O_QUEST && OP(s) != O_CH);
1590                         /*
1591                          * We must skip to the next position, or we'll
1592                          * leave altoffset() too early.
1593                          */
1594                         scan++;
1595                         break;
1596                 case OANYOF:
1597                 case OCHAR:
1598                 case OANY:
1599                         try++;
1600                         /*FALLTHRU*/
1601                 case OBOW:
1602                 case OEOW:
1603                 case OLPAREN:
1604                 case ORPAREN:
1605                 case OOR2:
1606                         break;
1607                 default:
1608                         try = -1;
1609                         break;
1610                 }
1611                 if (try == -1)
1612                         return (-1);
1613                 s = *scan++;
1614         }
1615 
1616         if (try > largest)
1617                 largest = try;
1618 
1619         return (largest+offset);
1620 }
1621 
1622 /*
1623  * computejumps - compute char jumps for BM scan
1624  *
1625  * This algorithm assumes g->must exists and is has size greater than
1626  * zero. It's based on the algorithm found on Computer Algorithms by
1627  * Sara Baase.
1628  *
1629  * A char jump is the number of characters one needs to jump based on
1630  * the value of the character from the text that was mismatched.
1631  */
1632 static void
1633 computejumps(struct parse *p, struct re_guts *g)
1634 {
1635         int ch;
1636         int mindex;
1637 
1638         /* Avoid making errors worse */
1639         if (p->error != 0)
1640                 return;
1641 
1642         g->charjump = (int *)malloc((NC + 1) * sizeof (int));
1643         if (g->charjump == NULL)     /* Not a fatal error */
1644                 return;
1645         /* Adjust for signed chars, if necessary */
1646         g->charjump = &g->charjump[-(CHAR_MIN)];
1647 
1648         /*
1649          * If the character does not exist in the pattern, the jump
1650          * is equal to the number of characters in the pattern.
1651          */
1652         for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++)
1653                 g->charjump[ch] = g->mlen;
1654 
1655         /*
1656          * If the character does exist, compute the jump that would
1657          * take us to the last character in the pattern equal to it
1658          * (notice that we match right to left, so that last character
1659          * is the first one that would be matched).
1660          */
1661         for (mindex = 0; mindex < g->mlen; mindex++)
1662                 g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1;
1663 }
1664 
1665 /*
1666  * computematchjumps - compute match jumps for BM scan
1667  *
1668  * This algorithm assumes g->must exists and is has size greater than
1669  * zero. It's based on the algorithm found on Computer Algorithms by
1670  * Sara Baase.
1671  *
1672  * A match jump is the number of characters one needs to advance based
1673  * on the already-matched suffix.
1674  * Notice that all values here are minus (g->mlen-1), because of the way
1675  * the search algorithm works.
1676  */
1677 static void
1678 computematchjumps(struct parse *p, struct re_guts *g)
1679 {
1680         int mindex;             /* General "must" iterator */
1681         int suffix;             /* Keeps track of matching suffix */
1682         int ssuffix;            /* Keeps track of suffixes' suffix */
1683         int *pmatches;
1684                                 /*
1685                                  * pmatches[k] points to the next i
1686                                  * such that i+1...mlen is a substring
1687                                  * of k+1...k+mlen-i-1
1688                                  */
1689 
1690         /* Avoid making errors worse */
1691         if (p->error != 0)
1692                 return;
1693 
1694         pmatches = (int *)malloc(g->mlen * sizeof (unsigned int));
1695         if (pmatches == NULL) {
1696                 g->matchjump = NULL;
1697                 return;
1698         }
1699 
1700         g->matchjump = (int *)malloc(g->mlen * sizeof (unsigned int));
1701         if (g->matchjump == NULL) {  /* Not a fatal error */
1702                 free(pmatches);
1703                 return;
1704         }
1705 
1706         /* Set maximum possible jump for each character in the pattern */
1707         for (mindex = 0; mindex < g->mlen; mindex++)
1708                 g->matchjump[mindex] = 2*g->mlen - mindex - 1;
1709 
1710         /* Compute pmatches[] */
1711         for (mindex = g->mlen - 1, suffix = g->mlen; mindex >= 0;
1712             mindex--, suffix--) {
1713                 pmatches[mindex] = suffix;
1714 
1715                 /*
1716                  * If a mismatch is found, interrupting the substring,
1717                  * compute the matchjump for that position. If no
1718                  * mismatch is found, then a text substring mismatched
1719                  * against the suffix will also mismatch against the
1720                  * substring.
1721                  */
1722                 while (suffix < g->mlen && g->must[mindex] != g->must[suffix]) {
1723                         g->matchjump[suffix] = MIN(g->matchjump[suffix],
1724                             g->mlen - mindex - 1);
1725                         suffix = pmatches[suffix];
1726                 }
1727         }
1728 
1729         /*
1730          * Compute the matchjump up to the last substring found to jump
1731          * to the beginning of the largest must pattern prefix matching
1732          * it's own suffix.
1733          */
1734         for (mindex = 0; mindex <= suffix; mindex++)
1735                 g->matchjump[mindex] = MIN(g->matchjump[mindex],
1736                     g->mlen + suffix - mindex);
1737 
1738         ssuffix = pmatches[suffix];
1739         while (suffix < g->mlen) {
1740                 while (suffix <= ssuffix && suffix < g->mlen) {
1741                         g->matchjump[suffix] = MIN(g->matchjump[suffix],
1742                             g->mlen + ssuffix - suffix);
1743                         suffix++;
1744                 }
1745                 if (suffix < g->mlen)
1746                         ssuffix = pmatches[ssuffix];
1747         }
1748 
1749         free(pmatches);
1750 }
1751 
1752 /*
1753  * pluscount - count + nesting
1754  */
1755 static sopno                    /* nesting depth */
1756 pluscount(struct parse *p, struct re_guts *g)
1757 {
1758         sop *scan;
1759         sop s;
1760         sopno plusnest = 0;
1761         sopno maxnest = 0;
1762 
1763         if (p->error != 0)
1764                 return (0);     /* there may not be an OEND */
1765 
1766         scan = g->strip + 1;
1767         do {
1768                 s = *scan++;
1769                 switch (OP(s)) {
1770                 case OPLUS_:
1771                         plusnest++;
1772                         break;
1773                 case O_PLUS:
1774                         if (plusnest > maxnest)
1775                                 maxnest = plusnest;
1776                         plusnest--;
1777                         break;
1778                 }
1779         } while (OP(s) != OEND);
1780         if (plusnest != 0)
1781                 g->iflags |= BAD;
1782         return (maxnest);
1783 }