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