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