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