lib/libc/regex/regcomp.c

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