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