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