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