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