Back to index

php5  5.3.10
regcomp.c
Go to the documentation of this file.
00001 #include <sys/types.h>
00002 #include <stdio.h>
00003 #include <string.h>
00004 #include <ctype.h>
00005 #include <limits.h>
00006 #include <stdlib.h>
00007 
00008 #define POSIX_MISTAKE
00009 
00010 #include "utils.h"
00011 #include "regex.h"
00012 #include "regex2.h"
00013 
00014 #include "cclass.h"
00015 #include "cname.h"
00016 
00017 /*
00018  * parse structure, passed up and down to avoid global variables and
00019  * other clumsinesses
00020  */
00021 struct parse {
00022        unsigned char *next;        /* next character in RE */
00023        unsigned char *end;         /* end of string (-> NUL normally) */
00024        int error;           /* has an error been seen? */
00025        sop *strip;          /* malloced strip */
00026        sopno ssize;         /* malloced strip size (allocated) */
00027        sopno slen;          /* malloced strip length (used) */
00028        int ncsalloc;        /* number of csets allocated */
00029        struct re_guts *g;
00030 #      define NPAREN 10     /* we need to remember () 1-9 for back refs */
00031        sopno pbegin[NPAREN];       /* -> ( ([0] unused) */
00032        sopno pend[NPAREN];  /* -> ) ([0] unused) */
00033 };
00034 
00035 #include "regcomp.ih"
00036 
00037 static unsigned char nuls[10];            /* place to point scanner in event of error */
00038 
00039 /*
00040  * macros for use with parse structure
00041  * BEWARE:  these know that the parse structure is named `p' !!!
00042  */
00043 #define       PEEK() (*p->next)
00044 #define       PEEK2()       (*(p->next+1))
00045 #define       MORE() (p->next < p->end)
00046 #define       MORE2()       (p->next+1 < p->end)
00047 #define       SEE(c) (MORE() && PEEK() == (c))
00048 #define       SEETWO(a, b)  (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
00049 #define       EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
00050 #define       EATTWO(a, b)  ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
00051 #define       NEXT() (p->next++)
00052 #define       NEXT2()       (p->next += 2)
00053 #define       NEXTn(n)      (p->next += (n))
00054 #define       GETNEXT()     (*p->next++)
00055 #define       SETERROR(e)   seterr(p, (e))
00056 #define       REQUIRE(co, e)       (void) ((co) || SETERROR(e))
00057 #define       MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
00058 #define       MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
00059 #define       MUSTNOTSEE(c, e)     (REQUIRE(!MORE() || PEEK() != (c), e))
00060 #define       EMIT(op, sopnd)      doemit(p, (sop)(op), (size_t)(sopnd))
00061 #define       INSERT(op, pos)      doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
00062 #define       AHEAD(pos)           dofwd(p, pos, HERE()-(pos))
00063 #define       ASTERN(sop, pos)     EMIT(sop, HERE()-pos)
00064 #define       HERE()        (p->slen)
00065 #define       THERE()              (p->slen - 1)
00066 #define       THERETHERE()  (p->slen - 2)
00067 #define       DROP(n)       (p->slen -= (n))
00068 
00069 #ifndef NDEBUG
00070 static int never = 0;              /* for use in asserts; shuts lint up */
00071 #else
00072 #define       never  0             /* some <assert.h>s have bugs too */
00073 #endif
00074 
00075 /*
00076  - regcomp - interface for parser and compilation
00077  = API_EXPORT(int) regcomp(regex_t *, const char *, int);
00078  = #define    REG_BASIC     0000
00079  = #define    REG_EXTENDED  0001
00080  = #define    REG_ICASE     0002
00081  = #define    REG_NOSUB     0004
00082  = #define    REG_NEWLINE   0010
00083  = #define    REG_NOSPEC    0020
00084  = #define    REG_PEND      0040
00085  = #define    REG_DUMP      0200
00086  */
00087 API_EXPORT(int)                    /* 0 success, otherwise REG_something */
00088 regcomp(preg, pattern, cflags)
00089 regex_t *preg;
00090 const char *pattern;
00091 int cflags;
00092 {
00093        struct parse pa;
00094        register struct re_guts *g;
00095        register struct parse *p = &pa;
00096        register int i;
00097        register size_t len;
00098 #ifdef REDEBUG
00099 #      define GOODFLAGS(f)  (f)
00100 #else
00101 #      define GOODFLAGS(f)  ((f)&~REG_DUMP)
00102 #endif
00103 
00104        cflags = GOODFLAGS(cflags);
00105        if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
00106               return(REG_INVARG);
00107 
00108        if (cflags&REG_PEND) {
00109               if (preg->re_endp < pattern)
00110                      return(REG_INVARG);
00111               len = preg->re_endp - pattern;
00112        } else
00113               len = strlen((char *)pattern);
00114 
00115        /* do the mallocs early so failure handling is easy */
00116        g = (struct re_guts *)malloc(sizeof(struct re_guts) +
00117                                                  (NC-1)*sizeof(cat_t));
00118        if (g == NULL)
00119               return(REG_ESPACE);
00120        p->ssize = len/(size_t)2*(size_t)3 + (size_t)1;  /* ugh */
00121        p->strip = (sop *)malloc(p->ssize * sizeof(sop));
00122        p->slen = 0;
00123        if (p->strip == NULL) {
00124               free((char *)g);
00125               return(REG_ESPACE);
00126        }
00127 
00128        /* set things up */
00129        p->g = g;
00130        p->next = (unsigned char *)pattern;       /* convenience; we do not modify it */
00131        p->end = p->next + len;
00132        p->error = 0;
00133        p->ncsalloc = 0;
00134        for (i = 0; i < NPAREN; i++) {
00135               p->pbegin[i] = 0;
00136               p->pend[i] = 0;
00137        }
00138        g->csetsize = NC;
00139        g->sets = NULL;
00140        g->setbits = NULL;
00141        g->ncsets = 0;
00142        g->cflags = cflags;
00143        g->iflags = 0;
00144        g->nbol = 0;
00145        g->neol = 0;
00146        g->must = NULL;
00147        g->mlen = 0;
00148        g->nsub = 0;
00149        g->ncategories = 1;  /* category 0 is "everything else" */
00150        g->categories = &g->catspace[0];
00151        (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));
00152        g->backrefs = 0;
00153 
00154        /* do it */
00155        EMIT(OEND, 0);
00156        g->firststate = THERE();
00157        if (cflags&REG_EXTENDED)
00158               p_ere(p, OUT);
00159        else if (cflags&REG_NOSPEC)
00160               p_str(p);
00161        else
00162               p_bre(p, OUT, OUT);
00163        EMIT(OEND, 0);
00164        g->laststate = THERE();
00165 
00166        /* tidy up loose ends and fill things in */
00167        categorize(p, g);
00168        stripsnug(p, g);
00169        findmust(p, g);
00170        g->nplus = pluscount(p, g);
00171        g->magic = MAGIC2;
00172        preg->re_nsub = g->nsub;
00173        preg->re_g = g;
00174        preg->re_magic = MAGIC1;
00175 #ifndef REDEBUG
00176        /* not debugging, so can't rely on the assert() in regexec() */
00177        if (g->iflags&BAD)
00178               SETERROR(REG_ASSERT);
00179 #endif
00180 
00181        /* win or lose, we're done */
00182        if (p->error != 0)   /* lose */
00183               regfree(preg);
00184        return(p->error);
00185 }
00186 
00187 /*
00188  - p_ere - ERE parser top level, concatenation and alternation
00189  == static void p_ere(register struct parse *p, int stop);
00190  */
00191 static void
00192 p_ere(p, stop)
00193 register struct parse *p;
00194 int stop;                   /* character this ERE should end at */
00195 {
00196        register unsigned char c;
00197        register sopno prevback = 0;
00198        register sopno prevfwd = 0;
00199        register sopno conc;
00200        register int first = 1;            /* is this the first alternative? */
00201 
00202        for (;;) {
00203               /* do a bunch of concatenated expressions */
00204               conc = HERE();
00205               while (MORE() && (c = PEEK()) != '|' && c != stop)
00206                      p_ere_exp(p);
00207               (void) REQUIRE(HERE() != conc, REG_EMPTY);       /* require nonempty */
00208 
00209               if (!EAT('|'))
00210                      break;        /* NOTE BREAK OUT */
00211 
00212               if (first) {
00213                      INSERT(OCH_, conc);  /* offset is wrong */
00214                      prevfwd = conc;
00215                      prevback = conc;
00216                      first = 0;
00217               }
00218               ASTERN(OOR1, prevback);
00219               prevback = THERE();
00220               AHEAD(prevfwd);                    /* fix previous offset */
00221               prevfwd = HERE();
00222               EMIT(OOR2, 0);                     /* offset is very wrong */
00223        }
00224 
00225        if (!first) {        /* tail-end fixups */
00226               AHEAD(prevfwd);
00227               ASTERN(O_CH, prevback);
00228        }
00229 
00230        assert(!MORE() || SEE(stop));
00231 }
00232 
00233 /*
00234  - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
00235  == static void p_ere_exp(register struct parse *p);
00236  */
00237 static void
00238 p_ere_exp(p)
00239 register struct parse *p;
00240 {
00241        register unsigned char c;
00242        register sopno pos;
00243        register int count;
00244        register int count2;
00245        register sopno subno;
00246        int wascaret = 0;
00247 
00248        assert(MORE());             /* caller should have ensured this */
00249        c = GETNEXT();
00250 
00251        pos = HERE();
00252        switch (c) {
00253        case '(':
00254               REQUIRE(MORE(), REG_EPAREN);
00255               p->g->nsub++;
00256               subno = p->g->nsub;
00257               if (subno < NPAREN)
00258                      p->pbegin[subno] = HERE();
00259               EMIT(OLPAREN, subno);
00260               if (!SEE(')'))
00261                      p_ere(p, ')');
00262               if (subno < NPAREN) {
00263                      p->pend[subno] = HERE();
00264                      assert(p->pend[subno] != 0);
00265               }
00266               EMIT(ORPAREN, subno);
00267               MUSTEAT(')', REG_EPAREN);
00268               break;
00269 #ifndef POSIX_MISTAKE
00270        case ')':            /* happens only if no current unmatched ( */
00271               /*
00272                * You may ask, why the ifndef?  Because I didn't notice
00273                * this until slightly too late for 1003.2, and none of the
00274                * other 1003.2 regular-expression reviewers noticed it at
00275                * all.  So an unmatched ) is legal POSIX, at least until
00276                * we can get it fixed.
00277                */
00278               SETERROR(REG_EPAREN);
00279               break;
00280 #endif
00281        case '^':
00282               EMIT(OBOL, 0);
00283               p->g->iflags |= USEBOL;
00284               p->g->nbol++;
00285               wascaret = 1;
00286               break;
00287        case '$':
00288               EMIT(OEOL, 0);
00289               p->g->iflags |= USEEOL;
00290               p->g->neol++;
00291               break;
00292        case '|':
00293               SETERROR(REG_EMPTY);
00294               break;
00295        case '*':
00296        case '+':
00297        case '?':
00298               SETERROR(REG_BADRPT);
00299               break;
00300        case '.':
00301               if (p->g->cflags&REG_NEWLINE)
00302                      nonnewline(p);
00303               else
00304                      EMIT(OANY, 0);
00305               break;
00306        case '[':
00307               p_bracket(p);
00308               break;
00309        case '\\':
00310               REQUIRE(MORE(), REG_EESCAPE);
00311               c = GETNEXT();
00312               ordinary(p, c);
00313               break;
00314        case '{':            /* okay as ordinary except if digit follows */
00315               REQUIRE(!MORE() || !isdigit(PEEK()), REG_BADRPT);
00316               /* FALLTHROUGH */
00317        default:
00318               ordinary(p, c);
00319               break;
00320        }
00321 
00322        if (!MORE())
00323               return;
00324        c = PEEK();
00325        /* we call { a repetition if followed by a digit */
00326        if (!( c == '*' || c == '+' || c == '?' ||
00327                             (c == '{' && MORE2() && isdigit(PEEK2())) ))
00328               return;              /* no repetition, we're done */
00329        NEXT();
00330 
00331        REQUIRE(!wascaret, REG_BADRPT);
00332        switch (c) {
00333        case '*':     /* implemented as +? */
00334               /* this case does not require the (y|) trick, noKLUDGE */
00335               INSERT(OPLUS_, pos);
00336               ASTERN(O_PLUS, pos);
00337               INSERT(OQUEST_, pos);
00338               ASTERN(O_QUEST, pos);
00339               break;
00340        case '+':
00341               INSERT(OPLUS_, pos);
00342               ASTERN(O_PLUS, pos);
00343               break;
00344        case '?':
00345               /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
00346               INSERT(OCH_, pos);          /* offset slightly wrong */
00347               ASTERN(OOR1, pos);          /* this one's right */
00348               AHEAD(pos);                 /* fix the OCH_ */
00349               EMIT(OOR2, 0);                     /* offset very wrong... */
00350               AHEAD(THERE());                    /* ...so fix it */
00351               ASTERN(O_CH, THERETHERE());
00352               break;
00353        case '{':
00354               count = p_count(p);
00355               if (EAT(',')) {
00356                      if (isdigit(PEEK())) {
00357                             count2 = p_count(p);
00358                             REQUIRE(count <= count2, REG_BADBR);
00359                      } else        /* single number with comma */
00360                             count2 = INFINITY;
00361               } else        /* just a single number */
00362                      count2 = count;
00363               repeat(p, pos, count, count2);
00364               if (!EAT('}')) {     /* error heuristics */
00365                      while (MORE() && PEEK() != '}')
00366                             NEXT();
00367                      REQUIRE(MORE(), REG_EBRACE);
00368                      SETERROR(REG_BADBR);
00369               }
00370               break;
00371        }
00372 
00373        if (!MORE())
00374               return;
00375        c = PEEK();
00376        if (!( c == '*' || c == '+' || c == '?' ||
00377                             (c == '{' && MORE2() && isdigit(PEEK2())) ) )
00378               return;
00379        SETERROR(REG_BADRPT);
00380 }
00381 
00382 /*
00383  - p_str - string (no metacharacters) "parser"
00384  == static void p_str(register struct parse *p);
00385  */
00386 static void
00387 p_str(p)
00388 register struct parse *p;
00389 {
00390        REQUIRE(MORE(), REG_EMPTY);
00391        while (MORE())
00392               ordinary(p, GETNEXT());
00393 }
00394 
00395 /*
00396  - p_bre - BRE parser top level, anchoring and concatenation
00397  == static void p_bre(register struct parse *p, register int end1, \
00398  ==    register int end2);
00399  * Giving end1 as OUT essentially eliminates the end1/end2 check.
00400  *
00401  * This implementation is a bit of a kludge, in that a trailing $ is first
00402  * taken as an ordinary character and then revised to be an anchor.  The
00403  * only undesirable side effect is that '$' gets included as a character
00404  * category in such cases.  This is fairly harmless; not worth fixing.
00405  * The amount of lookahead needed to avoid this kludge is excessive.
00406  */
00407 static void
00408 p_bre(p, end1, end2)
00409 register struct parse *p;
00410 register int end1;          /* first terminating character */
00411 register int end2;          /* second terminating character */
00412 {
00413        register sopno start = HERE();
00414        register int first = 1;                   /* first subexpression? */
00415        register int wasdollar = 0;
00416 
00417        if (EAT('^')) {
00418               EMIT(OBOL, 0);
00419               p->g->iflags |= USEBOL;
00420               p->g->nbol++;
00421        }
00422        while (MORE() && !SEETWO(end1, end2)) {
00423               wasdollar = p_simp_re(p, first);
00424               first = 0;
00425        }
00426        if (wasdollar) {     /* oops, that was a trailing anchor */
00427               DROP(1);
00428               EMIT(OEOL, 0);
00429               p->g->iflags |= USEEOL;
00430               p->g->neol++;
00431        }
00432 
00433        REQUIRE(HERE() != start, REG_EMPTY);      /* require nonempty */
00434 }
00435 
00436 /*
00437  - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
00438  == static int p_simp_re(register struct parse *p, int starordinary);
00439  */
00440 static int                  /* was the simple RE an unbackslashed $? */
00441 p_simp_re(p, starordinary)
00442 register struct parse *p;
00443 int starordinary;           /* is a leading * an ordinary character? */
00444 {
00445        register int c;
00446        register int count;
00447        register int count2;
00448        register sopno pos;
00449        register int i;
00450        register sopno subno;
00451 #      define BACKSL (1<<CHAR_BIT)
00452 
00453        pos = HERE();        /* repetion op, if any, covers from here */
00454 
00455        assert(MORE());             /* caller should have ensured this */
00456        c = GETNEXT();
00457        if (c == '\\') {
00458               REQUIRE(MORE(), REG_EESCAPE);
00459               c = BACKSL | (unsigned char)GETNEXT();
00460        }
00461        switch (c) {
00462        case '.':
00463               if (p->g->cflags&REG_NEWLINE)
00464                      nonnewline(p);
00465               else
00466                      EMIT(OANY, 0);
00467               break;
00468        case '[':
00469               p_bracket(p);
00470               break;
00471        case BACKSL|'{':
00472               SETERROR(REG_BADRPT);
00473               break;
00474        case BACKSL|'(':
00475               p->g->nsub++;
00476               subno = p->g->nsub;
00477               if (subno < NPAREN)
00478                      p->pbegin[subno] = HERE();
00479               EMIT(OLPAREN, subno);
00480               /* the MORE here is an error heuristic */
00481               if (MORE() && !SEETWO('\\', ')'))
00482                      p_bre(p, '\\', ')');
00483               if (subno < NPAREN) {
00484                      p->pend[subno] = HERE();
00485                      assert(p->pend[subno] != 0);
00486               }
00487               EMIT(ORPAREN, subno);
00488               REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
00489               break;
00490        case BACKSL|')':     /* should not get here -- must be user */
00491        case BACKSL|'}':
00492               SETERROR(REG_EPAREN);
00493               break;
00494        case BACKSL|'1':
00495        case BACKSL|'2':
00496        case BACKSL|'3':
00497        case BACKSL|'4':
00498        case BACKSL|'5':
00499        case BACKSL|'6':
00500        case BACKSL|'7':
00501        case BACKSL|'8':
00502        case BACKSL|'9':
00503               i = (c&~BACKSL) - '0';
00504               assert(i < NPAREN);
00505               if (p->pend[i] != 0) {
00506                      assert(i <= p->g->nsub);
00507                      EMIT(OBACK_, i);
00508                      assert(p->pbegin[i] != 0);
00509                      assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
00510                      assert(OP(p->strip[p->pend[i]]) == ORPAREN);
00511                      (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
00512                      EMIT(O_BACK, i);
00513               } else
00514                      SETERROR(REG_ESUBREG);
00515               p->g->backrefs = 1;
00516               break;
00517        case '*':
00518               REQUIRE(starordinary, REG_BADRPT);
00519               /* FALLTHROUGH */
00520        default:
00521               ordinary(p, (unsigned char)c);     /* takes off BACKSL, if any */
00522               break;
00523        }
00524 
00525        if (EAT('*')) {             /* implemented as +? */
00526               /* this case does not require the (y|) trick, noKLUDGE */
00527               INSERT(OPLUS_, pos);
00528               ASTERN(O_PLUS, pos);
00529               INSERT(OQUEST_, pos);
00530               ASTERN(O_QUEST, pos);
00531        } else if (EATTWO('\\', '{')) {
00532               count = p_count(p);
00533               if (EAT(',')) {
00534                      if (MORE() && isdigit(PEEK())) {
00535                             count2 = p_count(p);
00536                             REQUIRE(count <= count2, REG_BADBR);
00537                      } else        /* single number with comma */
00538                             count2 = INFINITY;
00539               } else        /* just a single number */
00540                      count2 = count;
00541               repeat(p, pos, count, count2);
00542               if (!EATTWO('\\', '}')) {   /* error heuristics */
00543                      while (MORE() && !SEETWO('\\', '}'))
00544                             NEXT();
00545                      REQUIRE(MORE(), REG_EBRACE);
00546                      SETERROR(REG_BADBR);
00547               }
00548        } else if (c == (unsigned char)'$')       /* $ (but not \$) ends it */
00549               return(1);
00550 
00551        return(0);
00552 }
00553 
00554 /*
00555  - p_count - parse a repetition count
00556  == static int p_count(register struct parse *p);
00557  */
00558 static int                  /* the value */
00559 p_count(p)
00560 register struct parse *p;
00561 {
00562        register int count = 0;
00563        register int ndigits = 0;
00564 
00565        while (MORE() && isdigit(PEEK()) && count <= DUPMAX) {
00566               count = count*10 + (GETNEXT() - '0');
00567               ndigits++;
00568        }
00569 
00570        REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
00571        return(count);
00572 }
00573 
00574 /*
00575  - p_bracket - parse a bracketed character list
00576  == static void p_bracket(register struct parse *p);
00577  *
00578  * Note a significant property of this code:  if the allocset() did SETERROR,
00579  * no set operations are done.
00580  */
00581 static void
00582 p_bracket(p)
00583 register struct parse *p;
00584 {
00585        register cset *cs = allocset(p);
00586        register int invert = 0;
00587 
00588        /* Dept of Truly Sickening Special-Case Kludges */
00589        if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
00590               EMIT(OBOW, 0);
00591               NEXTn(6);
00592               return;
00593        }
00594        if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
00595               EMIT(OEOW, 0);
00596               NEXTn(6);
00597               return;
00598        }
00599 
00600        if (EAT('^'))
00601               invert++;     /* make note to invert set at end */
00602        if (EAT(']'))
00603               CHadd(cs, ']');
00604        else if (EAT('-'))
00605               CHadd(cs, '-');
00606        while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
00607               p_b_term(p, cs);
00608        if (EAT('-'))
00609               CHadd(cs, '-');
00610        MUSTEAT(']', REG_EBRACK);
00611 
00612        if (p->error != 0)   /* don't mess things up further */
00613               return;
00614 
00615        if (p->g->cflags&REG_ICASE) {
00616               register int i;
00617               register int ci;
00618 
00619               for (i = p->g->csetsize - 1; i >= 0; i--)
00620                      if (CHIN(cs, i) && isalpha(i)) {
00621                             ci = othercase(i);
00622                             if (ci != i)
00623                                    CHadd(cs, ci);
00624                      }
00625               if (cs->multis != NULL)
00626                      mccase(p, cs);
00627        }
00628        if (invert) {
00629               register int i;
00630 
00631               for (i = p->g->csetsize - 1; i >= 0; i--)
00632                      if (CHIN(cs, i))
00633                             CHsub(cs, i);
00634                      else
00635                             CHadd(cs, i);
00636               if (p->g->cflags&REG_NEWLINE)
00637                      CHsub(cs, '\n');
00638               if (cs->multis != NULL)
00639                      mcinvert(p, cs);
00640        }
00641 
00642        assert(cs->multis == NULL);        /* xxx */
00643 
00644        if (nch(p, cs) == 1) {             /* optimize singleton sets */
00645               ordinary(p, firstch(p, cs));
00646               freeset(p, cs);
00647        } else
00648               EMIT(OANYOF, freezeset(p, cs));
00649 }
00650 
00651 /*
00652  - p_b_term - parse one term of a bracketed character list
00653  == static void p_b_term(register struct parse *p, register cset *cs);
00654  */
00655 static void
00656 p_b_term(p, cs)
00657 register struct parse *p;
00658 register cset *cs;
00659 {
00660        register unsigned char c;
00661        register unsigned char start, finish;
00662        register int i;
00663 
00664        /* classify what we've got */
00665        switch ((MORE()) ? PEEK() : '\0') {
00666        case '[':
00667               c = (MORE2()) ? PEEK2() : '\0';
00668               break;
00669        case '-':
00670               SETERROR(REG_ERANGE);
00671               return;                     /* NOTE RETURN */
00672               break;
00673        default:
00674               c = '\0';
00675               break;
00676        }
00677 
00678        switch (c) {
00679        case ':':            /* character class */
00680               NEXT2();
00681               REQUIRE(MORE(), REG_EBRACK);
00682               c = PEEK();
00683               REQUIRE(c != '-' && c != ']', REG_ECTYPE);
00684               p_b_cclass(p, cs);
00685               REQUIRE(MORE(), REG_EBRACK);
00686               REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
00687               break;
00688        case '=':            /* equivalence class */
00689               NEXT2();
00690               REQUIRE(MORE(), REG_EBRACK);
00691               c = PEEK();
00692               REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
00693               p_b_eclass(p, cs);
00694               REQUIRE(MORE(), REG_EBRACK);
00695               REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
00696               break;
00697        default:             /* symbol, ordinary character, or range */
00698 /* xxx revision needed for multichar stuff */
00699               start = p_b_symbol(p);
00700               if (SEE('-') && MORE2() && PEEK2() != ']') {
00701                      /* range */
00702                      NEXT();
00703                      if (EAT('-'))
00704                             finish = '-';
00705                      else
00706                             finish = p_b_symbol(p);
00707               } else
00708                      finish = start;
00709 /* xxx what about signed chars here... */
00710               REQUIRE(start <= finish, REG_ERANGE);
00711               for (i = start; i <= finish; i++)
00712                      CHadd(cs, i);
00713               break;
00714        }
00715 }
00716 
00717 /*
00718  - p_b_cclass - parse a character-class name and deal with it
00719  == static void p_b_cclass(register struct parse *p, register cset *cs);
00720  */
00721 static void
00722 p_b_cclass(p, cs)
00723 register struct parse *p;
00724 register cset *cs;
00725 {
00726        register unsigned char *sp = p->next;
00727        register const struct cclass *cp;
00728        register size_t len;
00729        register const unsigned char *u;
00730        register unsigned char c;
00731 
00732        while (MORE() && isalpha(PEEK()))
00733               NEXT();
00734        len = p->next - sp;
00735        for (cp = cclasses; cp->name != NULL; cp++)
00736               if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
00737                      break;
00738        if (cp->name == NULL) {
00739               /* oops, didn't find it */
00740               SETERROR(REG_ECTYPE);
00741               return;
00742        }
00743 
00744        u = cp->chars;
00745        while ((c = *u++) != '\0')
00746               CHadd(cs, c);
00747        for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
00748               MCadd(p, cs, u);
00749 }
00750 
00751 /*
00752  - p_b_eclass - parse an equivalence-class name and deal with it
00753  == static void p_b_eclass(register struct parse *p, register cset *cs);
00754  *
00755  * This implementation is incomplete. xxx
00756  */
00757 static void
00758 p_b_eclass(p, cs)
00759 register struct parse *p;
00760 register cset *cs;
00761 {
00762        register unsigned char c;
00763 
00764        c = p_b_coll_elem(p, '=');
00765        CHadd(cs, c);
00766 }
00767 
00768 /*
00769  - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
00770  == static char p_b_symbol(register struct parse *p);
00771  */
00772 static unsigned char               /* value of symbol */
00773 p_b_symbol(p)
00774 register struct parse *p;
00775 {
00776        register unsigned char value;
00777 
00778        REQUIRE(MORE(), REG_EBRACK);
00779        if (!EATTWO('[', '.'))
00780               return(GETNEXT());
00781 
00782        /* collating symbol */
00783        value = p_b_coll_elem(p, '.');
00784        REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
00785        return(value);
00786 }
00787 
00788 /*
00789  - p_b_coll_elem - parse a collating-element name and look it up
00790  == static char p_b_coll_elem(register struct parse *p, int endc);
00791  */
00792 static unsigned char               /* value of collating element */
00793 p_b_coll_elem(p, endc)
00794 register struct parse *p;
00795 int endc;                   /* name ended by endc,']' */
00796 {
00797        register unsigned char *sp = p->next;
00798        register const struct cname *cp;
00799        register int len;
00800 
00801        while (MORE() && !SEETWO(endc, ']'))
00802               NEXT();
00803        if (!MORE()) {
00804               SETERROR(REG_EBRACK);
00805               return(0);
00806        }
00807        len = p->next - sp;
00808        for (cp = cnames; cp->name != NULL; cp++)
00809               if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
00810                      return(cp->code);    /* known name */
00811        if (len == 1)
00812               return(*sp);  /* single character */
00813        SETERROR(REG_ECOLLATE);                   /* neither */
00814        return(0);
00815 }
00816 
00817 /*
00818  - othercase - return the case counterpart of an alphabetic
00819  == static char othercase(int ch);
00820  */
00821 static unsigned char               /* if no counterpart, return ch */
00822 othercase(ch)
00823 int ch;
00824 {
00825        assert(isalpha(ch));
00826        if (isupper(ch))
00827               return(tolower(ch));
00828        else if (islower(ch))
00829               return(toupper(ch));
00830        else                 /* peculiar, but could happen */
00831               return(ch);
00832 }
00833 
00834 /*
00835  - bothcases - emit a dualcase version of a two-case character
00836  == static void bothcases(register struct parse *p, int ch);
00837  *
00838  * Boy, is this implementation ever a kludge...
00839  */
00840 static void
00841 bothcases(p, ch)
00842 register struct parse *p;
00843 int ch;
00844 {
00845        register unsigned char *oldnext = p->next;
00846        register unsigned char *oldend = p->end;
00847        unsigned char bracket[3];
00848 
00849        assert(othercase(ch) != ch);       /* p_bracket() would recurse */
00850        p->next = bracket;
00851        p->end = bracket+2;
00852        bracket[0] = ch;
00853        bracket[1] = ']';
00854        bracket[2] = '\0';
00855        p_bracket(p);
00856        assert(p->next == bracket+2);
00857        p->next = oldnext;
00858        p->end = oldend;
00859 }
00860 
00861 /*
00862  - ordinary - emit an ordinary character
00863  == static void ordinary(register struct parse *p, register int ch);
00864  */
00865 static void
00866 ordinary(p, ch)
00867 register struct parse *p;
00868 register int ch;
00869 {
00870        register cat_t *cap = p->g->categories;
00871 
00872        if ((p->g->cflags&REG_ICASE) && isalpha(ch) && othercase(ch) != ch)
00873               bothcases(p, ch);
00874        else {
00875               EMIT(OCHAR, (unsigned char)ch);
00876               if (cap[ch] == 0)
00877                      cap[ch] = p->g->ncategories++;
00878        }
00879 }
00880 
00881 /*
00882  - nonnewline - emit REG_NEWLINE version of OANY
00883  == static void nonnewline(register struct parse *p);
00884  *
00885  * Boy, is this implementation ever a kludge...
00886  */
00887 static void
00888 nonnewline(p)
00889 register struct parse *p;
00890 {
00891        register unsigned char *oldnext = p->next;
00892        register unsigned char *oldend = p->end;
00893        unsigned char bracket[4];
00894 
00895        p->next = bracket;
00896        p->end = bracket+3;
00897        bracket[0] = '^';
00898        bracket[1] = '\n';
00899        bracket[2] = ']';
00900        bracket[3] = '\0';
00901        p_bracket(p);
00902        assert(p->next == bracket+3);
00903        p->next = oldnext;
00904        p->end = oldend;
00905 }
00906 
00907 /*
00908  - repeat - generate code for a bounded repetition, recursively if needed
00909  == static void repeat(register struct parse *p, sopno start, int from, int to);
00910  */
00911 static void
00912 repeat(p, start, from, to)
00913 register struct parse *p;
00914 sopno start;                /* operand from here to end of strip */
00915 int from;                   /* repeated from this number */
00916 int to;                            /* to this number of times (maybe INFINITY) */
00917 {
00918        register sopno finish = HERE();
00919 #      define N      2
00920 #      define INF    3
00921 #      define REP(f, t)     ((f)*8 + (t))
00922 #      define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
00923        register sopno copy;
00924 
00925        if (p->error != 0)   /* head off possible runaway recursion */
00926               return;
00927 
00928        assert(from <= to);
00929 
00930        switch (REP(MAP(from), MAP(to))) {
00931        case REP(0, 0):                    /* must be user doing this */
00932               DROP(finish-start);  /* drop the operand */
00933               break;
00934        case REP(0, 1):                    /* as x{1,1}? */
00935        case REP(0, N):                    /* as x{1,n}? */
00936        case REP(0, INF):           /* as x{1,}? */
00937               /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
00938               INSERT(OCH_, start);        /* offset is wrong... */
00939               repeat(p, start+1, 1, to);
00940               ASTERN(OOR1, start);
00941               AHEAD(start);               /* ... fix it */
00942               EMIT(OOR2, 0);
00943               AHEAD(THERE());
00944               ASTERN(O_CH, THERETHERE());
00945               break;
00946        case REP(1, 1):                    /* trivial case */
00947               /* done */
00948               break;
00949        case REP(1, N):                    /* as x?x{1,n-1} */
00950               /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
00951               INSERT(OCH_, start);
00952               ASTERN(OOR1, start);
00953               AHEAD(start);
00954               EMIT(OOR2, 0);                     /* offset very wrong... */
00955               AHEAD(THERE());                    /* ...so fix it */
00956               ASTERN(O_CH, THERETHERE());
00957               copy = dupl(p, start+1, finish+1);
00958               assert(copy == finish+4);
00959               repeat(p, copy, 1, to-1);
00960               break;
00961        case REP(1, INF):           /* as x+ */
00962               INSERT(OPLUS_, start);
00963               ASTERN(O_PLUS, start);
00964               break;
00965        case REP(N, N):                    /* as xx{m-1,n-1} */
00966               copy = dupl(p, start, finish);
00967               repeat(p, copy, from-1, to-1);
00968               break;
00969        case REP(N, INF):           /* as xx{n-1,INF} */
00970               copy = dupl(p, start, finish);
00971               repeat(p, copy, from-1, to);
00972               break;
00973        default:                    /* "can't happen" */
00974               SETERROR(REG_ASSERT);       /* just in case */
00975               break;
00976        }
00977 }
00978 
00979 /*
00980  - seterr - set an error condition
00981  == static int seterr(register struct parse *p, int e);
00982  */
00983 static int                  /* useless but makes type checking happy */
00984 seterr(p, e)
00985 register struct parse *p;
00986 int e;
00987 {
00988        if (p->error == 0)   /* keep earliest error condition */
00989               p->error = e;
00990        p->next = nuls;             /* try to bring things to a halt */
00991        p->end = nuls;
00992        return(0);           /* make the return value well-defined */
00993 }
00994 
00995 /*
00996  - allocset - allocate a set of characters for []
00997  == static cset *allocset(register struct parse *p);
00998  */
00999 static cset *
01000 allocset(p)
01001 register struct parse *p;
01002 {
01003        register int no = p->g->ncsets++;
01004        register size_t nc;
01005        register size_t nbytes;
01006        register cset *cs;
01007        register size_t css = (size_t)p->g->csetsize;
01008        register int i;
01009 
01010        if (no >= p->ncsalloc) {    /* need another column of space */
01011               p->ncsalloc += CHAR_BIT;
01012               nc = p->ncsalloc;
01013               assert(nc % CHAR_BIT == 0);
01014               nbytes = nc / CHAR_BIT * css;
01015               if (p->g->sets == NULL)
01016                      p->g->sets = (cset *)malloc(nc * sizeof(cset));
01017               else
01018                      p->g->sets = (cset *)realloc((unsigned char *)p->g->sets,
01019                                                  nc * sizeof(cset));
01020               if (p->g->setbits == NULL)
01021                      p->g->setbits = (uch *)malloc(nbytes);
01022               else {
01023                      p->g->setbits = (uch *)realloc((unsigned char *)p->g->setbits,
01024                                                         nbytes);
01025                      /* xxx this isn't right if setbits is now NULL */
01026                      for (i = 0; i < no; i++)
01027                             p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
01028               }
01029               if (p->g->sets != NULL && p->g->setbits != NULL)
01030                      (void) memset((unsigned char *)p->g->setbits + (nbytes - css),
01031                                                         0, css);
01032               else {
01033                      no = 0;
01034                      SETERROR(REG_ESPACE);
01035                      /* caller's responsibility not to do set ops */
01036               }
01037        }
01038 
01039        assert(p->g->sets != NULL); /* xxx */
01040        cs = &p->g->sets[no];
01041        cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
01042        cs->mask = 1 << ((no) % CHAR_BIT);
01043        cs->hash = 0;
01044        cs->smultis = 0;
01045        cs->multis = NULL;
01046 
01047        return(cs);
01048 }
01049 
01050 /*
01051  - freeset - free a now-unused set
01052  == static void freeset(register struct parse *p, register cset *cs);
01053  */
01054 static void
01055 freeset(p, cs)
01056 register struct parse *p;
01057 register cset *cs;
01058 {
01059        register size_t i;
01060        register cset *top = &p->g->sets[p->g->ncsets];
01061        register size_t css = (size_t)p->g->csetsize;
01062 
01063        for (i = 0; i < css; i++)
01064               CHsub(cs, i);
01065        if (cs == top-1)     /* recover only the easy case */
01066               p->g->ncsets--;
01067 }
01068 
01069 /*
01070  - freezeset - final processing on a set of characters
01071  == static int freezeset(register struct parse *p, register cset *cs);
01072  *
01073  * The main task here is merging identical sets.  This is usually a waste
01074  * of time (although the hash code minimizes the overhead), but can win
01075  * big if REG_ICASE is being used.  REG_ICASE, by the way, is why the hash
01076  * is done using addition rather than xor -- all ASCII [aA] sets xor to
01077  * the same value!
01078  */
01079 static int                  /* set number */
01080 freezeset(p, cs)
01081 register struct parse *p;
01082 register cset *cs;
01083 {
01084        register uch h = cs->hash;
01085        register size_t i;
01086        register cset *top = &p->g->sets[p->g->ncsets];
01087        register cset *cs2;
01088        register size_t css = (size_t)p->g->csetsize;
01089 
01090        /* look for an earlier one which is the same */
01091        for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
01092               if (cs2->hash == h && cs2 != cs) {
01093                      /* maybe */
01094                      for (i = 0; i < css; i++)
01095                             if (!!CHIN(cs2, i) != !!CHIN(cs, i))
01096                                    break;        /* no */
01097                      if (i == css)
01098                             break;               /* yes */
01099               }
01100 
01101        if (cs2 < top) {     /* found one */
01102               freeset(p, cs);
01103               cs = cs2;
01104        }
01105 
01106        return((int)(cs - p->g->sets));
01107 }
01108 
01109 /*
01110  - firstch - return first character in a set (which must have at least one)
01111  == static int firstch(register struct parse *p, register cset *cs);
01112  */
01113 static int                  /* character; there is no "none" value */
01114 firstch(p, cs)
01115 register struct parse *p;
01116 register cset *cs;
01117 {
01118        register size_t i;
01119        register size_t css = (size_t)p->g->csetsize;
01120 
01121        for (i = 0; i < css; i++)
01122               if (CHIN(cs, i))
01123                      return((unsigned char)i);
01124        assert(never);
01125        return(0);           /* arbitrary */
01126 }
01127 
01128 /*
01129  - nch - number of characters in a set
01130  == static int nch(register struct parse *p, register cset *cs);
01131  */
01132 static int
01133 nch(p, cs)
01134 register struct parse *p;
01135 register cset *cs;
01136 {
01137        register size_t i;
01138        register size_t css = (size_t)p->g->csetsize;
01139        register int n = 0;
01140 
01141        for (i = 0; i < css; i++)
01142               if (CHIN(cs, i))
01143                      n++;
01144        return(n);
01145 }
01146 
01147 /*
01148  - mcadd - add a collating element to a cset
01149  == static void mcadd(register struct parse *p, register cset *cs, \
01150  ==    register char *cp);
01151  */
01152 static void
01153 mcadd(p, cs, cp)
01154 register struct parse *p;
01155 register cset *cs;
01156 register const unsigned char *cp;
01157 {
01158        register size_t oldend = cs->smultis;
01159 
01160        cs->smultis += strlen(cp) + 1;
01161        if (cs->multis == NULL)
01162               cs->multis = malloc(cs->smultis);
01163        else
01164               cs->multis = realloc(cs->multis, cs->smultis);
01165        if (cs->multis == NULL) {
01166               SETERROR(REG_ESPACE);
01167               return;
01168        }
01169 
01170        (void) strcpy(cs->multis + oldend - 1, cp);
01171        cs->multis[cs->smultis - 1] = '\0';
01172 }
01173 
01174 #if 0
01175 /*
01176  - mcsub - subtract a collating element from a cset
01177  == static void mcsub(register cset *cs, register unsigned char *cp);
01178  */
01179 static void
01180 mcsub(cs, cp)
01181 register unsigned cset *cs;
01182 register unsigned char *cp;
01183 {
01184        register unsigned char *fp = mcfind(cs, cp);
01185        register size_t len = strlen(fp);
01186 
01187        assert(fp != NULL);
01188        (void) memmove(fp, fp + len + 1,
01189                             cs->smultis - (fp + len + 1 - cs->multis));
01190        cs->smultis -= len;
01191 
01192        if (cs->smultis == 0) {
01193               free(cs->multis);
01194               cs->multis = NULL;
01195               return;
01196        }
01197 
01198        cs->multis = realloc(cs->multis, cs->smultis);
01199        assert(cs->multis != NULL);
01200 }
01201 
01202 /*
01203  - mcin - is a collating element in a cset?
01204  == static int mcin(register cset *cs, register unsigned char *cp);
01205  */
01206 static int
01207 mcin(cs, cp)
01208 register cset *cs;
01209 register unsigned char *cp;
01210 {
01211        return(mcfind(cs, cp) != NULL);
01212 }
01213 
01214 
01215 /*
01216  - mcfind - find a collating element in a cset
01217  == static unsigned char *mcfind(register cset *cs, register unsigned char *cp);
01218  */
01219 static unsigned char *
01220 mcfind(cs, cp)
01221 register cset *cs;
01222 register unsigned char *cp;
01223 {
01224        register unsigned char *p;
01225 
01226        if (cs->multis == NULL)
01227               return(NULL);
01228        for (p = cs->multis; *p != '\0'; p += strlen(p) + 1)
01229               if (strcmp(cp, p) == 0)
01230                      return(p);
01231        return(NULL);
01232 }
01233 #endif
01234 
01235 /*
01236  - mcinvert - invert the list of collating elements in a cset
01237  == static void mcinvert(register struct parse *p, register cset *cs);
01238  *
01239  * This would have to know the set of possibilities.  Implementation
01240  * is deferred.
01241  */
01242 static void
01243 mcinvert(p, cs)
01244 register struct parse *p;
01245 register cset *cs;
01246 {
01247        assert(cs->multis == NULL); /* xxx */
01248 }
01249 
01250 /*
01251  - mccase - add case counterparts of the list of collating elements in a cset
01252  == static void mccase(register struct parse *p, register cset *cs);
01253  *
01254  * This would have to know the set of possibilities.  Implementation
01255  * is deferred.
01256  */
01257 static void
01258 mccase(p, cs)
01259 register struct parse *p;
01260 register cset *cs;
01261 {
01262        assert(cs->multis == NULL); /* xxx */
01263 }
01264 
01265 /*
01266  - isinsets - is this character in any sets?
01267  == static int isinsets(register struct re_guts *g, int c);
01268  */
01269 static int                  /* predicate */
01270 isinsets(g, c)
01271 register struct re_guts *g;
01272 int c;
01273 {
01274        register uch *col;
01275        register int i;
01276        register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
01277        register unsigned uc = (unsigned char)c;
01278 
01279        for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
01280               if (col[uc] != 0)
01281                      return(1);
01282        return(0);
01283 }
01284 
01285 /*
01286  - samesets - are these two characters in exactly the same sets?
01287  == static int samesets(register struct re_guts *g, int c1, int c2);
01288  */
01289 static int                  /* predicate */
01290 samesets(g, c1, c2)
01291 register struct re_guts *g;
01292 int c1;
01293 int c2;
01294 {
01295        register uch *col;
01296        register int i;
01297        register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
01298        register unsigned uc1 = (unsigned char)c1;
01299        register unsigned uc2 = (unsigned char)c2;
01300 
01301        for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
01302               if (col[uc1] != col[uc2])
01303                      return(0);
01304        return(1);
01305 }
01306 
01307 /*
01308  - categorize - sort out character categories
01309  == static void categorize(struct parse *p, register struct re_guts *g);
01310  */
01311 static void
01312 categorize(p, g)
01313 struct parse *p;
01314 register struct re_guts *g;
01315 {
01316        register cat_t *cats = g->categories;
01317        register int c;
01318        register int c2;
01319        register cat_t cat;
01320 
01321        /* avoid making error situations worse */
01322        if (p->error != 0)
01323               return;
01324 
01325        for (c = 0; c <= UCHAR_MAX; c++)
01326               if (cats[c] == 0 && isinsets(g, c)) {
01327                      cat = g->ncategories++;
01328                      cats[c] = cat;
01329                      for (c2 = c+1; c2 <= UCHAR_MAX; c2++)
01330                             if (cats[c2] == 0 && samesets(g, c, c2))
01331                                    cats[c2] = cat;
01332               }
01333 }
01334 
01335 /*
01336  - dupl - emit a duplicate of a bunch of sops
01337  == static sopno dupl(register struct parse *p, sopno start, sopno finish);
01338  */
01339 static sopno                /* start of duplicate */
01340 dupl(p, start, finish)
01341 register struct parse *p;
01342 sopno start;                /* from here */
01343 sopno finish;               /* to this less one */
01344 {
01345        register sopno ret = HERE();
01346        register sopno len = finish - start;
01347 
01348        assert(finish >= start);
01349        if (len == 0)
01350               return(ret);
01351        enlarge(p, p->ssize + len); /* this many unexpected additions */
01352        assert(p->ssize >= p->slen + len);
01353        (void) memcpy((char *)(p->strip + p->slen),
01354               (char *)(p->strip + start), (size_t)len*sizeof(sop));
01355        p->slen += len;
01356        return(ret);
01357 }
01358 
01359 /*
01360  - doemit - emit a strip operator
01361  == static void doemit(register struct parse *p, sop op, size_t opnd);
01362  *
01363  * It might seem better to implement this as a macro with a function as
01364  * hard-case backup, but it's just too big and messy unless there are
01365  * some changes to the data structures.  Maybe later.
01366  */
01367 static void
01368 doemit(p, op, opnd)
01369 register struct parse *p;
01370 sop op;
01371 size_t opnd;
01372 {
01373        /* avoid making error situations worse */
01374        if (p->error != 0)
01375               return;
01376 
01377        /* deal with oversize operands ("can't happen", more or less) */
01378        assert(opnd < 1<<OPSHIFT);
01379 
01380        /* deal with undersized strip */
01381        if (p->slen >= p->ssize)
01382               enlarge(p, (p->ssize+1) / 2 * 3);  /* +50% */
01383        assert(p->slen < p->ssize);
01384 
01385        /* finally, it's all reduced to the easy case */
01386        p->strip[p->slen++] = SOP(op, opnd);
01387 }
01388 
01389 /*
01390  - doinsert - insert a sop into the strip
01391  == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos);
01392  */
01393 static void
01394 doinsert(p, op, opnd, pos)
01395 register struct parse *p;
01396 sop op;
01397 size_t opnd;
01398 sopno pos;
01399 {
01400        register sopno sn;
01401        register sop s;
01402        register int i;
01403 
01404        /* avoid making error situations worse */
01405        if (p->error != 0)
01406               return;
01407 
01408        sn = HERE();
01409        EMIT(op, opnd);             /* do checks, ensure space */
01410        assert(HERE() == sn+1);
01411        s = p->strip[sn];
01412 
01413        /* adjust paren pointers */
01414        assert(pos > 0);
01415        for (i = 1; i < NPAREN; i++) {
01416               if (p->pbegin[i] >= pos) {
01417                      p->pbegin[i]++;
01418               }
01419               if (p->pend[i] >= pos) {
01420                      p->pend[i]++;
01421               }
01422        }
01423 
01424        memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
01425                                           (HERE()-pos-1)*sizeof(sop));
01426        p->strip[pos] = s;
01427 }
01428 
01429 /*
01430  - dofwd - complete a forward reference
01431  == static void dofwd(register struct parse *p, sopno pos, sop value);
01432  */
01433 static void
01434 dofwd(p, pos, value)
01435 register struct parse *p;
01436 register sopno pos;
01437 sop value;
01438 {
01439        /* avoid making error situations worse */
01440        if (p->error != 0)
01441               return;
01442 
01443        assert(value < 1<<OPSHIFT);
01444        p->strip[pos] = OP(p->strip[pos]) | value;
01445 }
01446 
01447 /*
01448  - enlarge - enlarge the strip
01449  == static void enlarge(register struct parse *p, sopno size);
01450  */
01451 static void
01452 enlarge(p, size)
01453 register struct parse *p;
01454 register sopno size;
01455 {
01456        register sop *sp;
01457 
01458        if (p->ssize >= size)
01459               return;
01460 
01461        sp = (sop *)realloc(p->strip, size*sizeof(sop));
01462        if (sp == NULL) {
01463               SETERROR(REG_ESPACE);
01464               return;
01465        }
01466        p->strip = sp;
01467        p->ssize = size;
01468 }
01469 
01470 /*
01471  - stripsnug - compact the strip
01472  == static void stripsnug(register struct parse *p, register struct re_guts *g);
01473  */
01474 static void
01475 stripsnug(p, g)
01476 register struct parse *p;
01477 register struct re_guts *g;
01478 {
01479        g->nstates = p->slen;
01480        g->strip = (sop *)realloc((unsigned char *)p->strip, p->slen * sizeof(sop));
01481        if (g->strip == NULL) {
01482               SETERROR(REG_ESPACE);
01483               g->strip = p->strip;
01484        }
01485 }
01486 
01487 /*
01488  - findmust - fill in must and mlen with longest mandatory literal string
01489  == static void findmust(register struct parse *p, register struct re_guts *g);
01490  *
01491  * This algorithm could do fancy things like analyzing the operands of |
01492  * for common subsequences.  Someday.  This code is simple and finds most
01493  * of the interesting cases.
01494  *
01495  * Note that must and mlen got initialized during setup.
01496  */
01497 static void
01498 findmust(p, g)
01499 struct parse *p;
01500 register struct re_guts *g;
01501 {
01502        register sop *scan;
01503        sop *start = NULL;
01504        register sop *newstart = NULL;
01505        register sopno newlen;
01506        register sop s;
01507        register unsigned char *cp;
01508        register sopno i;
01509 
01510        /* avoid making error situations worse */
01511        if (p->error != 0)
01512               return;
01513 
01514        /* find the longest OCHAR sequence in strip */
01515        newlen = 0;
01516        scan = g->strip + 1;
01517        do {
01518               s = *scan++;
01519               switch (OP(s)) {
01520               case OCHAR:          /* sequence member */
01521                      if (newlen == 0)            /* new sequence */
01522                             newstart = scan - 1;
01523                      newlen++;
01524                      break;
01525               case OPLUS_:         /* things that don't break one */
01526               case OLPAREN:
01527               case ORPAREN:
01528                      break;
01529               case OQUEST_:        /* things that must be skipped */
01530               case OCH_:
01531                      scan--;
01532                      do {
01533                             scan += OPND(s);
01534                             s = *scan;
01535                             /* assert() interferes w debug printouts */
01536                             if (OP(s) != O_QUEST && OP(s) != O_CH &&
01537                                                  OP(s) != OOR2) {
01538                                    g->iflags |= BAD;
01539                                    return;
01540                             }
01541                      } while (OP(s) != O_QUEST && OP(s) != O_CH);
01542                      /* fallthrough */
01543               default:             /* things that break a sequence */
01544                      if (newlen > g->mlen) {            /* ends one */
01545                             start = newstart;
01546                             g->mlen = newlen;
01547                      }
01548                      newlen = 0;
01549                      break;
01550               }
01551        } while (OP(s) != OEND);
01552 
01553        if (g->mlen == 0)           /* there isn't one */
01554               return;
01555 
01556        if (!start) {
01557               g->mlen = 0;
01558               return;
01559        }
01560 
01561        /* turn it into a character string */
01562        g->must = malloc((size_t)g->mlen + 1);
01563        if (g->must == NULL) {             /* argh; just forget it */
01564               g->mlen = 0;
01565               return;
01566        }
01567        cp = g->must;
01568        scan = start;
01569        for (i = g->mlen; i > 0; i--) {
01570               while (OP(s = *scan++) != OCHAR)
01571                      continue;
01572               assert(cp < g->must + g->mlen);
01573               *cp++ = (unsigned char)OPND(s);
01574        }
01575        assert(cp == g->must + g->mlen);
01576        *cp++ = '\0';        /* just on general principles */
01577 }
01578 
01579 /*
01580  - pluscount - count + nesting
01581  == static sopno pluscount(register struct parse *p, register struct re_guts *g);
01582  */
01583 static sopno                /* nesting depth */
01584 pluscount(p, g)
01585 struct parse *p;
01586 register struct re_guts *g;
01587 {
01588        register sop *scan;
01589        register sop s;
01590        register sopno plusnest = 0;
01591        register sopno maxnest = 0;
01592 
01593        if (p->error != 0)
01594               return(0);    /* there may not be an OEND */
01595 
01596        scan = g->strip + 1;
01597        do {
01598               s = *scan++;
01599               switch (OP(s)) {
01600               case OPLUS_:
01601                      plusnest++;
01602                      break;
01603               case O_PLUS:
01604                      if (plusnest > maxnest)
01605                             maxnest = plusnest;
01606                      plusnest--;
01607                      break;
01608               }
01609        } while (OP(s) != OEND);
01610        if (plusnest != 0)
01611               g->iflags |= BAD;
01612        return(maxnest);
01613 }