lib/libc/regex/regcomp.c

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