lib/libc/regex/regcomp.c

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