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 / engine.c < prev    next >
C/C++ Source or Header  |  2000-08-31  |  26KB  |  1,027 lines
  1. /*
  2.  * The matching engine and friends.  This file is #included by regexec.c
  3.  * after suitable #defines of a variety of macros used herein, so that
  4.  * different state representations can be used without duplicating masses
  5.  * of code.
  6.  */
  7.  
  8. #ifdef SNAMES
  9. #define    matcher    smatcher
  10. #define    fast    sfast
  11. #define    slow    sslow
  12. #define    dissect    sdissect
  13. #define    backref    sbackref
  14. #define    step    sstep
  15. #define    print    sprint
  16. #define    at    sat
  17. #define    match    smat
  18. #endif
  19. #ifdef LNAMES
  20. #define    matcher    lmatcher
  21. #define    fast    lfast
  22. #define    slow    lslow
  23. #define    dissect    ldissect
  24. #define    backref    lbackref
  25. #define    step    lstep
  26. #define    print    lprint
  27. #define    at    lat
  28. #define    match    lmat
  29. #endif
  30.  
  31. /* another structure passed up and down to avoid zillions of parameters */
  32. struct match {
  33.     struct re_guts *g;
  34.     int eflags;
  35.     regmatch_t *pmatch;    /* [nsub+1] (0 element unused) */
  36.     char *offp;        /* offsets work from here */
  37.     char *beginp;        /* start of string -- virtual NUL precedes */
  38.     char *endp;        /* end of string -- virtual NUL here */
  39.     char *coldp;        /* can be no match starting before here */
  40.     char **lastpos;        /* [nplus+1] */
  41.     STATEVARS;
  42.     states st;        /* current states */
  43.     states fresh;        /* states for a fresh start */
  44.     states tmp;        /* temporary */
  45.     states empty;        /* empty set of states */
  46. };
  47.  
  48. #include "engine.ih"
  49.  
  50. #ifdef REDEBUG
  51. #define    SP(t, s, c)    print(m, t, s, c, stdout)
  52. #define    AT(t, p1, p2, s1, s2)    at(m, t, p1, p2, s1, s2)
  53. #define    NOTE(str)    { if (m->eflags®_TRACE) printf("=%s\n", (str)); }
  54. #else
  55. #define    SP(t, s, c)    /* nothing */
  56. #define    AT(t, p1, p2, s1, s2)    /* nothing */
  57. #define    NOTE(s)    /* nothing */
  58. #endif
  59.  
  60. /*
  61.  - matcher - the actual matching engine
  62.  == static int matcher(register struct re_guts *g, char *string, \
  63.  ==    size_t nmatch, regmatch_t pmatch[], int eflags);
  64.  */
  65. static int            /* 0 success, REG_NOMATCH failure */
  66. matcher(g, str, nmatch, pmatch, eflags)
  67. register struct re_guts *g;
  68. char *str;
  69. size_t nmatch;
  70. regmatch_t pmatch[];
  71. int eflags;
  72. {
  73.     register char *endp;
  74.     register uint i;
  75.     struct match mv;
  76.     register struct match *m = &mv;
  77.     register char *dp;
  78.     register const sopno gf = g->firststate+1;    /* +1 for OEND */
  79.     register const sopno gl = g->laststate;
  80.     char *start;
  81.     char *stop;
  82.  
  83.     /* simplify the situation where possible */
  84.     if (g->cflags®_NOSUB)
  85.         nmatch = 0;
  86.     if (eflags®_STARTEND) {
  87.         start = str + pmatch[0].rm_so;
  88.         stop = str + pmatch[0].rm_eo;
  89.     } else {
  90.         start = str;
  91.         stop = start + strlen(start);
  92.     }
  93.     if (stop < start)
  94.         return(REG_INVARG);
  95.  
  96.     /* prescreening; this does wonders for this rather slow code */
  97.     if (g->must != NULL) {
  98.         for (dp = start; dp < stop; dp++)
  99.             if (*dp == g->must[0] && stop - dp >= g->mlen &&
  100.                 memcmp(dp, g->must, (size_t)g->mlen) == 0)
  101.                 break;
  102.         if (dp == stop)        /* we didn't find g->must */
  103.             return(REG_NOMATCH);
  104.     }
  105.  
  106.     /* match struct setup */
  107.     m->g = g;
  108.     m->eflags = eflags;
  109.     m->pmatch = NULL;
  110.     m->lastpos = NULL;
  111.     m->offp = str;
  112.     m->beginp = start;
  113.     m->endp = stop;
  114.     STATESETUP(m, 4);
  115.     SETUP(m->st);
  116.     SETUP(m->fresh);
  117.     SETUP(m->tmp);
  118.     SETUP(m->empty);
  119.     CLEAR(m->empty);
  120.  
  121.     /* this loop does only one repetition except for backrefs */
  122.     for (;;) {
  123.         endp = fast(m, start, stop, gf, gl);
  124.         if (endp == NULL) {        /* a miss */
  125.           if (m->pmatch != NULL)
  126.             free((char *)m->pmatch);
  127.           if (m->lastpos != NULL)
  128.             free((char *)m->lastpos);
  129.           STATETEARDOWN(m);
  130.           return(REG_NOMATCH);
  131.         }
  132.         if (nmatch == 0 && !g->backrefs)
  133.             break;        /* no further info needed */
  134.  
  135.         /* where? */
  136.         assert(m->coldp != NULL);
  137.         for (;;) {
  138.             NOTE("finding start");
  139.             endp = slow(m, m->coldp, stop, gf, gl);
  140.             if (endp != NULL)
  141.                 break;
  142.             assert(m->coldp < m->endp);
  143.             m->coldp++;
  144.         }
  145.         if (nmatch == 1 && !g->backrefs)
  146.             break;        /* no further info needed */
  147.  
  148.         /* oh my, he wants the subexpressions... */
  149.         if (m->pmatch == NULL)
  150.             m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
  151.                             sizeof(regmatch_t));
  152.         if (m->pmatch == NULL) {
  153.               if (m->lastpos != NULL)
  154.                 free((char *)m->lastpos);
  155.             STATETEARDOWN(m);
  156.             return(REG_ESPACE);
  157.         }
  158.         for (i = 1; i <= m->g->nsub; i++)
  159.             m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
  160.         if (!g->backrefs && !(m->eflags®_BACKR)) {
  161.             NOTE("dissecting");
  162.             dp = dissect(m, m->coldp, endp, gf, gl);
  163.         } else {
  164.             if (g->nplus > 0 && m->lastpos == NULL)
  165.                 m->lastpos = (char **)malloc((g->nplus+1) *
  166.                             sizeof(char *));
  167.             if (g->nplus > 0 && m->lastpos == NULL) {
  168.                 free(m->pmatch);
  169.                 STATETEARDOWN(m);
  170.                 return(REG_ESPACE);
  171.             }
  172.             NOTE("backref dissect");
  173.             dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
  174.         }
  175.         if (dp != NULL)
  176.             break;
  177.  
  178.         /* uh-oh... we couldn't find a subexpression-level match */
  179.         assert(g->backrefs);    /* must be back references doing it */
  180.         assert(g->nplus == 0 || m->lastpos != NULL);
  181.         for (;;) {
  182.             if (dp != NULL || endp <= m->coldp)
  183.                 break;        /* defeat */
  184.             NOTE("backoff");
  185.             endp = slow(m, m->coldp, endp-1, gf, gl);
  186.             if (endp == NULL)
  187.                 break;        /* defeat */
  188.             /* try it on a shorter possibility */
  189. #ifndef NDEBUG
  190.             for (i = 1; i <= m->g->nsub; i++) {
  191.                 assert(m->pmatch[i].rm_so == -1);
  192.                 assert(m->pmatch[i].rm_eo == -1);
  193.             }
  194. #endif
  195.             NOTE("backoff dissect");
  196.             dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
  197.         }
  198.         assert(dp == NULL || dp == endp);
  199.         if (dp != NULL)        /* found a shorter one */
  200.             break;
  201.  
  202.         /* despite initial appearances, there is no match here */
  203.         NOTE("false alarm");
  204.         start = m->coldp + 1;    /* recycle starting later */
  205.         assert(start <= stop);
  206.     }
  207.  
  208.     /* fill in the details if requested */
  209.     if (nmatch > 0) {
  210.         pmatch[0].rm_so = m->coldp - m->offp;
  211.         pmatch[0].rm_eo = endp - m->offp;
  212.     }
  213.     if (nmatch > 1) {
  214.         assert(m->pmatch != NULL);
  215.         for (i = 1; i < nmatch; i++)
  216.             if (i <= m->g->nsub)
  217.                 pmatch[i] = m->pmatch[i];
  218.             else {
  219.                 pmatch[i].rm_so = -1;
  220.                 pmatch[i].rm_eo = -1;
  221.             }
  222.     }
  223.  
  224.     if (m->pmatch != NULL)
  225.         free((char *)m->pmatch);
  226.     if (m->lastpos != NULL)
  227.         free((char *)m->lastpos);
  228.     STATETEARDOWN(m);
  229.     return(0);
  230. }
  231.  
  232. /*
  233.  - dissect - figure out what matched what, no back references
  234.  == static char *dissect(register struct match *m, char *start, \
  235.  ==    char *stop, sopno startst, sopno stopst);
  236.  */
  237. static char *            /* == stop (success) always */
  238. dissect(m, start, stop, startst, stopst)
  239. register struct match *m;
  240. char *start;
  241. char *stop;
  242. sopno startst;
  243. sopno stopst;
  244. {
  245.     register uint i;
  246.     register sopno ss;    /* start sop of current subRE */
  247.     register sopno es;    /* end sop of current subRE */
  248.     register char *sp;    /* start of string matched by it */
  249.     register char *stp;    /* string matched by it cannot pass here */
  250.     register char *rest;    /* start of rest of string */
  251.     register char *tail;    /* string unmatched by rest of RE */
  252.     register sopno ssub;    /* start sop of subsubRE */
  253.     register sopno esub;    /* end sop of subsubRE */
  254.     register char *ssp;    /* start of string matched by subsubRE */
  255.     register char *sep;    /* end of string matched by subsubRE */
  256.     register char *oldssp;    /* previous ssp */
  257.     register char *dp;
  258.  
  259.     AT("diss", start, stop, startst, stopst);
  260.     sp = start;
  261.     for (ss = startst; ss < stopst; ss = es) {
  262.         /* identify end of subRE */
  263.         es = ss;
  264.         switch (OP(m->g->strip[es])) {
  265.         case OPLUS_:
  266.         case OQUEST_:
  267.             es += OPND(m->g->strip[es]);
  268.             break;
  269.         case OCH_:
  270.             while (OP(m->g->strip[es]) != O_CH)
  271.                 es += OPND(m->g->strip[es]);
  272.             break;
  273.         }
  274.         es++;
  275.  
  276.         /* figure out what it matched */
  277.         switch (OP(m->g->strip[ss])) {
  278.         case OEND:
  279.             assert(nope);
  280.             break;
  281.         case OCHAR:
  282.             sp++;
  283.             break;
  284.         case OBOL:
  285.         case OEOL:
  286.         case OBOW:
  287.         case OEOW:
  288.             break;
  289.         case OANY:
  290.         case OANYOF:
  291.             sp++;
  292.             break;
  293.         case OBACK_:
  294.         case O_BACK:
  295.             assert(nope);
  296.             break;
  297.         /* cases where length of match is hard to find */
  298.         case OQUEST_:
  299.             stp = stop;
  300.             for (;;) {
  301.                 /* how long could this one be? */
  302.                 rest = slow(m, sp, stp, ss, es);
  303.                 assert(rest != NULL);    /* it did match */
  304.                 /* could the rest match the rest? */
  305.                 tail = slow(m, rest, stop, es, stopst);
  306.                 if (tail == stop)
  307.                     break;        /* yes! */
  308.                 /* no -- try a shorter match for this one */
  309.                 stp = rest - 1;
  310.                 assert(stp >= sp);    /* it did work */
  311.             }
  312.             ssub = ss + 1;
  313.             esub = es - 1;
  314.             /* did innards match? */
  315.             if (slow(m, sp, rest, ssub, esub) != NULL) {
  316.                 dp = dissect(m, sp, rest, ssub, esub);
  317.                 assert(dp == rest);
  318.             } else        /* no */
  319.                 assert(sp == rest);
  320.             sp = rest;
  321.             break;
  322.         case OPLUS_:
  323.             stp = stop;
  324.             for (;;) {
  325.                 /* how long could this one be? */
  326.                 rest = slow(m, sp, stp, ss, es);
  327.                 assert(rest != NULL);    /* it did match */
  328.                 /* could the rest match the rest? */
  329.                 tail = slow(m, rest, stop, es, stopst);
  330.                 if (tail == stop)
  331.                     break;        /* yes! */
  332.                 /* no -- try a shorter match for this one */
  333.                 stp = rest - 1;
  334.                 assert(stp >= sp);    /* it did work */
  335.             }
  336.             ssub = ss + 1;
  337.             esub = es - 1;
  338.             ssp = sp;
  339.             oldssp = ssp;
  340.             for (;;) {    /* find last match of innards */
  341.                 sep = slow(m, ssp, rest, ssub, esub);
  342.                 if (sep == NULL || sep == ssp)
  343.                     break;    /* failed or matched null */
  344.                 oldssp = ssp;    /* on to next try */
  345.                 ssp = sep;
  346.             }
  347.             if (sep == NULL) {
  348.                 /* last successful match */
  349.                 sep = ssp;
  350.                 ssp = oldssp;
  351.             }
  352.             assert(sep == rest);    /* must exhaust substring */
  353.             assert(slow(m, ssp, sep, ssub, esub) == rest);
  354.             dp = dissect(m, ssp, sep, ssub, esub);
  355.             assert(dp == sep);
  356.             sp = rest;
  357.             break;
  358.         case OCH_:
  359.             stp = stop;
  360.             for (;;) {
  361.                 /* how long could this one be? */
  362.                 rest = slow(m, sp, stp, ss, es);
  363.                 assert(rest != NULL);    /* it did match */
  364.                 /* could the rest match the rest? */
  365.                 tail = slow(m, rest, stop, es, stopst);
  366.                 if (tail == stop)
  367.                     break;        /* yes! */
  368.                 /* no -- try a shorter match for this one */
  369.                 stp = rest - 1;
  370.                 assert(stp >= sp);    /* it did work */
  371.             }
  372.             ssub = ss + 1;
  373.             esub = ss + OPND(m->g->strip[ss]) - 1;
  374.             assert(OP(m->g->strip[esub]) == OOR1);
  375.             for (;;) {    /* find first matching branch */
  376.                 if (slow(m, sp, rest, ssub, esub) == rest)
  377.                     break;    /* it matched all of it */
  378.                 /* that one missed, try next one */
  379.                 assert(OP(m->g->strip[esub]) == OOR1);
  380.                 esub++;
  381.                 assert(OP(m->g->strip[esub]) == OOR2);
  382.                 ssub = esub + 1;
  383.                 esub += OPND(m->g->strip[esub]);
  384.                 if (OP(m->g->strip[esub]) == OOR2)
  385.                     esub--;
  386.                 else
  387.                     assert(OP(m->g->strip[esub]) == O_CH);
  388.             }
  389.             dp = dissect(m, sp, rest, ssub, esub);
  390.             assert(dp == rest);
  391.             sp = rest;
  392.             break;
  393.         case O_PLUS:
  394.         case O_QUEST:
  395.         case OOR1:
  396.         case OOR2:
  397.         case O_CH:
  398.             assert(nope);
  399.             break;
  400.         case OLPAREN:
  401.             i = OPND(m->g->strip[ss]);
  402.             assert(0 < i && i <= m->g->nsub);
  403.             m->pmatch[i].rm_so = sp - m->offp;
  404.             break;
  405.         case ORPAREN:
  406.             i = OPND(m->g->strip[ss]);
  407.             assert(0 < i && i <= m->g->nsub);
  408.             m->pmatch[i].rm_eo = sp - m->offp;
  409.             break;
  410.         default:        /* uh oh */
  411.             assert(nope);
  412.             break;
  413.         }
  414.     }
  415.  
  416.     assert(sp == stop);
  417.     return(sp);
  418. }
  419.  
  420. /*
  421.  - backref - figure out what matched what, figuring in back references
  422.  == static char *backref(register struct match *m, char *start, \
  423.  ==    char *stop, sopno startst, sopno stopst, sopno lev);
  424.  */
  425. static char *            /* == stop (success) or NULL (failure) */
  426. backref(m, start, stop, startst, stopst, lev)
  427. register struct match *m;
  428. char *start;
  429. char *stop;
  430. sopno startst;
  431. sopno stopst;
  432. sopno lev;            /* PLUS nesting level */
  433. {
  434.     register uint i;
  435.     register sopno ss;    /* start sop of current subRE */
  436.     register char *sp;    /* start of string matched by it */
  437.     register sopno ssub;    /* start sop of subsubRE */
  438.     register sopno esub;    /* end sop of subsubRE */
  439.     register char *ssp;    /* start of string matched by subsubRE */
  440.     register char *dp;
  441.     register size_t len;
  442.     register int hard;
  443.     register sop s;
  444.     register regoff_t offsave;
  445.     register cset *cs;
  446.  
  447.     AT("back", start, stop, startst, stopst);
  448.     sp = start;
  449.  
  450.     /* get as far as we can with easy stuff */
  451.     hard = 0;
  452.     for (ss = startst; !hard && ss < stopst; ss++)
  453.         switch (OP(s = m->g->strip[ss])) {
  454.         case OCHAR:
  455.             if (sp == stop || *sp++ != (char)OPND(s))
  456.                 return(NULL);
  457.             break;
  458.         case OANY:
  459.             if (sp == stop)
  460.                 return(NULL);
  461.             sp++;
  462.             break;
  463.         case OANYOF:
  464.             cs = &m->g->sets[OPND(s)];
  465.             if (sp == stop || !CHIN(cs, *sp++))
  466.                 return(NULL);
  467.             break;
  468.         case OBOL:
  469.             if ( (sp == m->beginp && !(m->eflags®_NOTBOL)) ||
  470.                     (sp < m->endp && *(sp-1) == '\n' &&
  471.                         (m->g->cflags®_NEWLINE)) )
  472.                 { /* yes */ }
  473.             else
  474.                 return(NULL);
  475.             break;
  476.         case OEOL:
  477.             if ( (sp == m->endp && !(m->eflags®_NOTEOL)) ||
  478.                     (sp < m->endp && *sp == '\n' &&
  479.                         (m->g->cflags®_NEWLINE)) )
  480.                 { /* yes */ }
  481.             else
  482.                 return(NULL);
  483.             break;
  484.         case OBOW:
  485.             if (( (sp == m->beginp && !(m->eflags®_NOTBOL)) ||
  486.                     (sp < m->endp && *(sp-1) == '\n' &&
  487.                         (m->g->cflags®_NEWLINE)) ||
  488.                     (sp > m->beginp &&
  489.                             !ISWORD(*(sp-1))) ) &&
  490.                     (sp < m->endp && ISWORD(*sp)) )
  491.                 { /* yes */ }
  492.             else
  493.                 return(NULL);
  494.             break;
  495.         case OEOW:
  496.             if (( (sp == m->endp && !(m->eflags®_NOTEOL)) ||
  497.                     (sp < m->endp && *sp == '\n' &&
  498.                         (m->g->cflags®_NEWLINE)) ||
  499.                     (sp < m->endp && !ISWORD(*sp)) ) &&
  500.                     (sp > m->beginp && ISWORD(*(sp-1))) )
  501.                 { /* yes */ }
  502.             else
  503.                 return(NULL);
  504.             break;
  505.         case O_QUEST:
  506.             break;
  507.         case OOR1:    /* matches null but needs to skip */
  508.             ss++;
  509.             s = m->g->strip[ss];
  510.             do {
  511.                 assert(OP(s) == OOR2);
  512.                 ss += OPND(s);
  513.             } while (OP(s = m->g->strip[ss]) != O_CH);
  514.             /* note that the ss++ gets us past the O_CH */
  515.             break;
  516.         default:    /* have to make a choice */
  517.             hard = 1;
  518.             break;
  519.         }
  520.     if (!hard) {        /* that was it! */
  521.         if (sp != stop)
  522.             return(NULL);
  523.         return(sp);
  524.     }
  525.     ss--;            /* adjust for the for's final increment */
  526.  
  527.     /* the hard stuff */
  528.     AT("hard", sp, stop, ss, stopst);
  529.     s = m->g->strip[ss];
  530.     switch (OP(s)) {
  531.     case OBACK_:        /* the vilest depths */
  532.         i = OPND(s);
  533.         assert(0 < i && i <= m->g->nsub);
  534.         if (m->pmatch[i].rm_eo == -1)
  535.             return(NULL);
  536.         assert(m->pmatch[i].rm_so != -1);
  537.         len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
  538.         assert((size_t) (stop - m->beginp) >= len);
  539.         if (sp > stop - len)
  540.             return(NULL);    /* not enough left to match */
  541.         ssp = m->offp + m->pmatch[i].rm_so;
  542.         if (memcmp(sp, ssp, len) != 0)
  543.             return(NULL);
  544.         while (m->g->strip[ss] != SOP(O_BACK, i))
  545.             ss++;
  546.         return(backref(m, sp+len, stop, ss+1, stopst, lev));
  547.         break;
  548.     case OQUEST_:        /* to null or not */
  549.         dp = backref(m, sp, stop, ss+1, stopst, lev);
  550.         if (dp != NULL)
  551.             return(dp);    /* not */
  552.         return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
  553.         break;
  554.     case OPLUS_:
  555.         assert(m->lastpos != NULL);
  556.         assert(lev+1 <= m->g->nplus);
  557.         m->lastpos[lev+1] = sp;
  558.         return(backref(m, sp, stop, ss+1, stopst, lev+1));
  559.         break;
  560.     case O_PLUS:
  561.         if (sp == m->lastpos[lev])    /* last pass matched null */
  562.             return(backref(m, sp, stop, ss+1, stopst, lev-1));
  563.         /* try another pass */
  564.         m->lastpos[lev] = sp;
  565.         dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
  566.         if (dp == NULL)
  567.             return(backref(m, sp, stop, ss+1, stopst, lev-1));
  568.         else
  569.             return(dp);
  570.         break;
  571.     case OCH_:        /* find the right one, if any */
  572.         ssub = ss + 1;
  573.         esub = ss + OPND(s) - 1;
  574.         assert(OP(m->g->strip[esub]) == OOR1);
  575.         for (;;) {    /* find first matching branch */
  576.             dp = backref(m, sp, stop, ssub, esub, lev);
  577.             if (dp != NULL)
  578.                 return(dp);
  579.             /* that one missed, try next one */
  580.             if (OP(m->g->strip[esub]) == O_CH)
  581.                 return(NULL);    /* there is none */
  582.             esub++;
  583.             assert(OP(m->g->strip[esub]) == OOR2);
  584.             ssub = esub + 1;
  585.             esub += OPND(m->g->strip[esub]);
  586.             if (OP(m->g->strip[esub]) == OOR2)
  587.                 esub--;
  588.             else
  589.                 assert(OP(m->g->strip[esub]) == O_CH);
  590.         }
  591.         break;
  592.     case OLPAREN:        /* must undo assignment if rest fails */
  593.         i = OPND(s);
  594.         assert(0 < i && i <= m->g->nsub);
  595.         offsave = m->pmatch[i].rm_so;
  596.         m->pmatch[i].rm_so = sp - m->offp;
  597.         dp = backref(m, sp, stop, ss+1, stopst, lev);
  598.         if (dp != NULL)
  599.             return(dp);
  600.         m->pmatch[i].rm_so = offsave;
  601.         return(NULL);
  602.         break;
  603.     case ORPAREN:        /* must undo assignment if rest fails */
  604.         i = OPND(s);
  605.         assert(0 < i && i <= m->g->nsub);
  606.         offsave = m->pmatch[i].rm_eo;
  607.         m->pmatch[i].rm_eo = sp - m->offp;
  608.         dp = backref(m, sp, stop, ss+1, stopst, lev);
  609.         if (dp != NULL)
  610.             return(dp);
  611.         m->pmatch[i].rm_eo = offsave;
  612.         return(NULL);
  613.         break;
  614.     default:        /* uh oh */
  615.         assert(nope);
  616.         break;
  617.     }
  618.  
  619.     /* "can't happen" */
  620.     assert(nope);
  621.     /* NOTREACHED */
  622.     return 0;                /* Keep gcc happy */
  623. }
  624.  
  625. /*
  626.  - fast - step through the string at top speed
  627.  == static char *fast(register struct match *m, char *start, \
  628.  ==    char *stop, sopno startst, sopno stopst);
  629.  */
  630. static char *            /* where tentative match ended, or NULL */
  631. fast(m, start, stop, startst, stopst)
  632. register struct match *m;
  633. char *start;
  634. char *stop;
  635. sopno startst;
  636. sopno stopst;
  637. {
  638.     register states st = m->st;
  639.     register states fresh = m->fresh;
  640.     register states tmp = m->tmp;
  641.     register char *p = start;
  642.     register int c = (start == m->beginp) ? OUT : *(start-1);
  643.     register int lastc;    /* previous c */
  644.     register int flagch;
  645.     register int i;
  646.     register char *coldp;    /* last p after which no match was underway */
  647.  
  648.     CLEAR(st);
  649.     SET1(st, startst);
  650.     st = step(m->g, startst, stopst, st, NOTHING, st);
  651.     ASSIGN(fresh, st);
  652.     SP("start", st, *p);
  653.     coldp = NULL;
  654.     for (;;) {
  655.         /* next character */
  656.         lastc = c;
  657.         c = (p == m->endp) ? OUT : *p;
  658.         if (EQ(st, fresh))
  659.             coldp = p;
  660.  
  661.         /* is there an EOL and/or BOL between lastc and c? */
  662.         flagch = '\0';
  663.         i = 0;
  664.         if ( (lastc == '\n' && m->g->cflags®_NEWLINE) ||
  665.                 (lastc == OUT && !(m->eflags®_NOTBOL)) ) {
  666.             flagch = BOL;
  667.             i = m->g->nbol;
  668.         }
  669.         if ( (c == '\n' && m->g->cflags®_NEWLINE) ||
  670.                 (c == OUT && !(m->eflags®_NOTEOL)) ) {
  671.             flagch = (flagch == BOL) ? BOLEOL : EOL;
  672.             i += m->g->neol;
  673.         }
  674.         if (i != 0) {
  675.             for (; i > 0; i--)
  676.                 st = step(m->g, startst, stopst, st, flagch, st);
  677.             SP("boleol", st, c);
  678.         }
  679.  
  680.         /* how about a word boundary? */
  681.         if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
  682.                     (c != OUT && ISWORD(c)) ) {
  683.             flagch = BOW;
  684.         }
  685.         if ( (lastc != OUT && ISWORD(lastc)) &&
  686.                 (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
  687.             flagch = EOW;
  688.         }
  689.         if (flagch == BOW || flagch == EOW) {
  690.             st = step(m->g, startst, stopst, st, flagch, st);
  691.             SP("boweow", st, c);
  692.         }
  693.  
  694.         /* are we done? */
  695.         if (ISSET(st, stopst) || p == stop)
  696.             break;        /* NOTE BREAK OUT */
  697.  
  698.         /* no, we must deal with this character */
  699.         ASSIGN(tmp, st);
  700.         ASSIGN(st, fresh);
  701.         assert(c != OUT);
  702.         st = step(m->g, startst, stopst, tmp, c, st);
  703.         SP("aft", st, c);
  704.         assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
  705.         p++;
  706.     }
  707.  
  708.     assert(coldp != NULL);
  709.     m->coldp = coldp;
  710.     if (ISSET(st, stopst))
  711.         return(p+1);
  712.     else
  713.         return(NULL);
  714. }
  715.  
  716. /*
  717.  - slow - step through the string more deliberately
  718.  == static char *slow(register struct match *m, char *start, \
  719.  ==    char *stop, sopno startst, sopno stopst);
  720.  */
  721. static char *            /* where it ended */
  722. slow(m, start, stop, startst, stopst)
  723. register struct match *m;
  724. char *start;
  725. char *stop;
  726. sopno startst;
  727. sopno stopst;
  728. {
  729.     register states st = m->st;
  730.     register states empty = m->empty;
  731.     register states tmp = m->tmp;
  732.     register char *p = start;
  733.     register int c = (start == m->beginp) ? OUT : *(start-1);
  734.     register int lastc;    /* previous c */
  735.     register int flagch;
  736.     register int i;
  737.     register char *matchp;    /* last p at which a match ended */
  738.  
  739.     AT("slow", start, stop, startst, stopst);
  740.     CLEAR(st);
  741.     SET1(st, startst);
  742.     SP("sstart", st, *p);
  743.     st = step(m->g, startst, stopst, st, NOTHING, st);
  744.     matchp = NULL;
  745.     for (;;) {
  746.         /* next character */
  747.         lastc = c;
  748.         c = (p == m->endp) ? OUT : *p;
  749.  
  750.         /* is there an EOL and/or BOL between lastc and c? */
  751.         flagch = '\0';
  752.         i = 0;
  753.         if ( (lastc == '\n' && m->g->cflags®_NEWLINE) ||
  754.                 (lastc == OUT && !(m->eflags®_NOTBOL)) ) {
  755.             flagch = BOL;
  756.             i = m->g->nbol;
  757.         }
  758.         if ( (c == '\n' && m->g->cflags®_NEWLINE) ||
  759.                 (c == OUT && !(m->eflags®_NOTEOL)) ) {
  760.             flagch = (flagch == BOL) ? BOLEOL : EOL;
  761.             i += m->g->neol;
  762.         }
  763.         if (i != 0) {
  764.             for (; i > 0; i--)
  765.                 st = step(m->g, startst, stopst, st, flagch, st);
  766.             SP("sboleol", st, c);
  767.         }
  768.  
  769.         /* how about a word boundary? */
  770.         if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
  771.                     (c != OUT && ISWORD(c)) ) {
  772.             flagch = BOW;
  773.         }
  774.         if ( (lastc != OUT && ISWORD(lastc)) &&
  775.                 (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
  776.             flagch = EOW;
  777.         }
  778.         if (flagch == BOW || flagch == EOW) {
  779.             st = step(m->g, startst, stopst, st, flagch, st);
  780.             SP("sboweow", st, c);
  781.         }
  782.  
  783.         /* are we done? */
  784.         if (ISSET(st, stopst))
  785.             matchp = p;
  786.         if (EQ(st, empty) || p == stop)
  787.             break;        /* NOTE BREAK OUT */
  788.  
  789.         /* no, we must deal with this character */
  790.         ASSIGN(tmp, st);
  791.         ASSIGN(st, empty);
  792.         assert(c != OUT);
  793.         st = step(m->g, startst, stopst, tmp, c, st);
  794.         SP("saft", st, c);
  795.         assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
  796.         p++;
  797.     }
  798.  
  799.     return(matchp);
  800. }
  801.  
  802.  
  803. /*
  804.  - step - map set of states reachable before char to set reachable after
  805.  == static states step(register struct re_guts *g, sopno start, sopno stop, \
  806.  ==    register states bef, int ch, register states aft);
  807.  == #define    BOL    (OUT+1)
  808.  == #define    EOL    (BOL+1)
  809.  == #define    BOLEOL    (BOL+2)
  810.  == #define    NOTHING    (BOL+3)
  811.  == #define    BOW    (BOL+4)
  812.  == #define    EOW    (BOL+5)
  813.  == #define    CODEMAX    (BOL+5)        // highest code used
  814.  == #define    NONCHAR(c)    ((c) > CHAR_MAX)
  815.  == #define    NNONCHAR    (CODEMAX-CHAR_MAX)
  816.  */
  817. static states
  818. step(g, start, stop, bef, ch, aft)
  819. register struct re_guts *g;
  820. sopno start;            /* start state within strip */
  821. sopno stop;            /* state after stop state within strip */
  822. register states bef;        /* states reachable before */
  823. int ch;                /* character or NONCHAR code */
  824. register states aft;        /* states already known reachable after */
  825. {
  826.     register cset *cs;
  827.     register sop s;
  828.     register sopno pc;
  829.     register onestate here;        /* note, macros know this name */
  830.     register sopno look;
  831.     register int i;
  832.  
  833.     for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
  834.         s = g->strip[pc];
  835.         switch (OP(s)) {
  836.         case OEND:
  837.             assert(pc == stop-1);
  838.             break;
  839.         case OCHAR:
  840.             /* only characters can match */
  841.             assert(!NONCHAR(ch) || ch != (char)OPND(s));
  842.             if (ch == (char)OPND(s))
  843.                 FWD(aft, bef, 1);
  844.             break;
  845.         case OBOL:
  846.             if (ch == BOL || ch == BOLEOL)
  847.                 FWD(aft, bef, 1);
  848.             break;
  849.         case OEOL:
  850.             if (ch == EOL || ch == BOLEOL)
  851.                 FWD(aft, bef, 1);
  852.             break;
  853.         case OBOW:
  854.             if (ch == BOW)
  855.                 FWD(aft, bef, 1);
  856.             break;
  857.         case OEOW:
  858.             if (ch == EOW)
  859.                 FWD(aft, bef, 1);
  860.             break;
  861.         case OANY:
  862.             if (!NONCHAR(ch))
  863.                 FWD(aft, bef, 1);
  864.             break;
  865.         case OANYOF:
  866.             cs = &g->sets[OPND(s)];
  867.             if (!NONCHAR(ch) && CHIN(cs, ch))
  868.                 FWD(aft, bef, 1);
  869.             break;
  870.         case OBACK_:        /* ignored here */
  871.         case O_BACK:
  872.             FWD(aft, aft, 1);
  873.             break;
  874.         case OPLUS_:        /* forward, this is just an empty */
  875.             FWD(aft, aft, 1);
  876.             break;
  877.         case O_PLUS:        /* both forward and back */
  878.             FWD(aft, aft, 1);
  879.             i = ISSETBACK(aft, OPND(s));
  880.             BACK(aft, aft, OPND(s));
  881.             if (!i && ISSETBACK(aft, OPND(s))) {
  882.                 /* oho, must reconsider loop body */
  883.                 pc -= OPND(s) + 1;
  884.                 INIT(here, pc);
  885.             }
  886.             break;
  887.         case OQUEST_:        /* two branches, both forward */
  888.             FWD(aft, aft, 1);
  889.             FWD(aft, aft, OPND(s));
  890.             break;
  891.         case O_QUEST:        /* just an empty */
  892.             FWD(aft, aft, 1);
  893.             break;
  894.         case OLPAREN:        /* not significant here */
  895.         case ORPAREN:
  896.             FWD(aft, aft, 1);
  897.             break;
  898.         case OCH_:        /* mark the first two branches */
  899.             FWD(aft, aft, 1);
  900.             assert(OP(g->strip[pc+OPND(s)]) == OOR2);
  901.             FWD(aft, aft, OPND(s));
  902.             break;
  903.         case OOR1:        /* done a branch, find the O_CH */
  904.             if (ISSTATEIN(aft, here)) {
  905.                 for (look = 1;
  906.                         OP(s = g->strip[pc+look]) != O_CH;
  907.                         look += OPND(s))
  908.                     assert(OP(s) == OOR2);
  909.                 FWD(aft, aft, look);
  910.             }
  911.             break;
  912.         case OOR2:        /* propagate OCH_'s marking */
  913.             FWD(aft, aft, 1);
  914.             if (OP(g->strip[pc+OPND(s)]) != O_CH) {
  915.                 assert(OP(g->strip[pc+OPND(s)]) == OOR2);
  916.                 FWD(aft, aft, OPND(s));
  917.             }
  918.             break;
  919.         case O_CH:        /* just empty */
  920.             FWD(aft, aft, 1);
  921.             break;
  922.         default:        /* ooooops... */
  923.             assert(nope);
  924.             break;
  925.         }
  926.     }
  927.  
  928.     return(aft);
  929. }
  930.  
  931. #ifdef REDEBUG
  932. /*
  933.  - print - print a set of states
  934.  == #ifdef REDEBUG
  935.  == static void print(struct match *m, char *caption, states st, \
  936.  ==    int ch, FILE *d);
  937.  == #endif
  938.  */
  939. static void
  940. print(m, caption, st, ch, d)
  941. struct match *m;
  942. char *caption;
  943. states st;
  944. int ch;
  945. FILE *d;
  946. {
  947.     register struct re_guts *g = m->g;
  948.     register int i;
  949.     register int first = 1;
  950.     char buf[10];
  951.  
  952.     if (!(m->eflags®_TRACE))
  953.         return;
  954.  
  955.     fprintf(d, "%s", caption);
  956.     if (ch != '\0')
  957.         fprintf(d, " %s", printchar(ch,buf));
  958.     for (i = 0; i < g->nstates; i++)
  959.         if (ISSET(st, i)) {
  960.             fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
  961.             first = 0;
  962.         }
  963.     fprintf(d, "\n");
  964. }
  965.  
  966. /*
  967.  - at - print current situation
  968.  == #ifdef REDEBUG
  969.  == static void at(struct match *m, char *title, char *start, char *stop, \
  970.  ==                        sopno startst, sopno stopst);
  971.  == #endif
  972.  */
  973. static void
  974. at(m, title, start, stop, startst, stopst)
  975. struct match *m;
  976. char *title;
  977. char *start;
  978. char *stop;
  979. sopno startst;
  980. sopno stopst;
  981. {
  982.     char buf[10];
  983.     if (!(m->eflags®_TRACE))
  984.         return;
  985.  
  986.     printf("%s %s-", title, printchar(*start,buf));
  987.     printf("%s ", printchar(*stop,buf));
  988.     printf("%ld-%ld\n", (long)startst, (long)stopst,buf);
  989. }
  990.  
  991. #ifndef PCHARDONE
  992. #define    PCHARDONE    /* never again */
  993. /*
  994.  - printchar - make a character printable
  995.  == #ifdef REDEBUG
  996.  == static char *printchar(int ch);
  997.  == #endif
  998.  *
  999.  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
  1000.  * duplicate here avoids having a debugging-capable regexec.o tied to
  1001.  * a matching debug.o, and this is convenient.  It all disappears in
  1002.  * the non-debug compilation anyway, so it doesn't matter much.
  1003.  */
  1004. static char *            /* -> representation */
  1005. printchar(ch,pbuf)
  1006. int ch;
  1007. char *pbuf;
  1008. {
  1009.     if (isprint(ch) || ch == ' ')
  1010.         sprintf(pbuf, "%c", ch);
  1011.     else
  1012.         sprintf(pbuf, "\\%o", ch);
  1013.     return(pbuf);
  1014. }
  1015. #endif
  1016. #endif
  1017.  
  1018. #undef    matcher
  1019. #undef    fast
  1020. #undef    slow
  1021. #undef    dissect
  1022. #undef    backref
  1023. #undef    step
  1024. #undef    print
  1025. #undef    at
  1026. #undef    match
  1027.