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