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