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