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