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