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