git.cworth.org Git - vogl/blob - src/voglcore/regex/regcomp.c

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