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