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