home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / perl-5.003-src.tgz / tar.out / fsf / perl / regexec.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  25KB  |  1,120 lines
  1. /*    regexec.c
  2.  */
  3.  
  4. /*
  5.  * "One Ring to rule them all, One Ring to find them..."
  6.  */
  7.  
  8. /* NOTE: this is derived from Henry Spencer's regexp code, and should not
  9.  * confused with the original package (see point 3 below).  Thanks, Henry!
  10.  */
  11.  
  12. /* Additional note: this code is very heavily munged from Henry's version
  13.  * in places.  In some spots I've traded clarity for efficiency, so don't
  14.  * blame Henry for some of the lack of readability.
  15.  */
  16.  
  17. /* The names of the functions have been changed from regcomp and
  18.  * regexec to  pregcomp and pregexec in order to avoid conflicts
  19.  * with the POSIX routines of the same names.
  20. */
  21.  
  22. /*SUPPRESS 112*/
  23. /*
  24.  * pregcomp and pregexec -- regsub and regerror are not used in perl
  25.  *
  26.  *    Copyright (c) 1986 by University of Toronto.
  27.  *    Written by Henry Spencer.  Not derived from licensed software.
  28.  *
  29.  *    Permission is granted to anyone to use this software for any
  30.  *    purpose on any computer system, and to redistribute it freely,
  31.  *    subject to the following restrictions:
  32.  *
  33.  *    1. The author is not responsible for the consequences of use of
  34.  *        this software, no matter how awful, even if they arise
  35.  *        from defects in it.
  36.  *
  37.  *    2. The origin of this software must not be misrepresented, either
  38.  *        by explicit claim or by omission.
  39.  *
  40.  *    3. Altered versions must be plainly marked as such, and must not
  41.  *        be misrepresented as being the original software.
  42.  *
  43.  ****    Alterations to Henry's code are...
  44.  ****
  45.  ****    Copyright (c) 1991-1994, Larry Wall
  46.  ****
  47.  ****    You may distribute under the terms of either the GNU General Public
  48.  ****    License or the Artistic License, as specified in the README file.
  49.  *
  50.  * Beware that some of this code is subtly aware of the way operator
  51.  * precedence is structured in regular expressions.  Serious changes in
  52.  * regular-expression syntax might require a total rethink.
  53.  */
  54. #include "EXTERN.h"
  55. #include "perl.h"
  56. #include "regcomp.h"
  57.  
  58. #ifndef STATIC
  59. #define    STATIC    static
  60. #endif
  61.  
  62. #ifdef DEBUGGING
  63. static I32 regnarrate = 0;
  64. static char* regprogram = 0;
  65. #endif
  66.  
  67. /* Current curly descriptor */
  68. typedef struct curcur CURCUR;
  69. struct curcur {
  70.     int        parenfloor;    /* how far back to strip paren data */
  71.     int        cur;        /* how many instances of scan we've matched */
  72.     int        min;        /* the minimal number of scans to match */
  73.     int        max;        /* the maximal number of scans to match */
  74.     int        minmod;        /* whether to work our way up or down */
  75.     char *    scan;        /* the thing to match */
  76.     char *    next;        /* what has to match after it */
  77.     char *    lastloc;    /* where we started matching this scan */
  78.     CURCUR *    oldcc;        /* current curly before we started this one */
  79. };
  80.  
  81. static CURCUR* regcc;
  82.  
  83. typedef I32 CHECKPOINT;
  84.  
  85. CHECKPOINT regcppush _((I32 parenfloor));
  86. char * regcppop _((void));
  87.  
  88. CHECKPOINT
  89. regcppush(parenfloor)
  90. I32 parenfloor;
  91. {
  92.     int retval = savestack_ix;
  93.     int i = (regsize - parenfloor) * 3;
  94.     int p;
  95.  
  96.     SSCHECK(i + 5);
  97.     for (p = regsize; p > parenfloor; p--) {
  98.     SSPUSHPTR(regendp[p]);
  99.     SSPUSHPTR(regstartp[p]);
  100.     SSPUSHINT(p);
  101.     }
  102.     SSPUSHINT(regsize);
  103.     SSPUSHINT(*reglastparen);
  104.     SSPUSHPTR(reginput);
  105.     SSPUSHINT(i + 3);
  106.     SSPUSHINT(SAVEt_REGCONTEXT);
  107.     return retval;
  108. }
  109.  
  110. char*
  111. regcppop()
  112. {
  113.     I32 i = SSPOPINT;
  114.     U32 paren = 0;
  115.     char *input;
  116.     char *tmps;
  117.     assert(i == SAVEt_REGCONTEXT);
  118.     i = SSPOPINT;
  119.     input = (char *) SSPOPPTR;
  120.     *reglastparen = SSPOPINT;
  121.     regsize = SSPOPINT;
  122.     for (i -= 3; i > 0; i -= 3) {
  123.     paren = (U32)SSPOPINT;
  124.     regstartp[paren] = (char *) SSPOPPTR;
  125.     tmps = (char*)SSPOPPTR;
  126.     if (paren <= *reglastparen)
  127.         regendp[paren] = tmps;
  128.     }
  129.     for (paren = *reglastparen + 1; paren <= regnpar; paren++) {
  130.     if (paren > regsize)
  131.         regstartp[paren] = Nullch;
  132.     regendp[paren] = Nullch;
  133.     }
  134.     return input;
  135. }
  136.  
  137. #define regcpblow(cp) leave_scope(cp)
  138.  
  139. /*
  140.  * pregexec and friends
  141.  */
  142.  
  143. /*
  144.  * Forwards.
  145.  */
  146.  
  147. static I32 regmatch _((char *prog));
  148. static I32 regrepeat _((char *p, I32 max));
  149. static I32 regtry _((regexp *prog, char *startpos));
  150.  
  151. /*
  152.  - pregexec - match a regexp against a string
  153.  */
  154. I32
  155. pregexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
  156. register regexp *prog;
  157. char *stringarg;
  158. register char *strend;    /* pointer to null at end of string */
  159. char *strbeg;    /* real beginning of string */
  160. I32 minend;    /* end of match must be at least minend after stringarg */
  161. SV *screamer;
  162. I32 safebase;    /* no need to remember string in subbase */
  163. {
  164.     register char *s;
  165.     register I32 i;
  166.     register char *c;
  167.     register char *startpos = stringarg;
  168.     register I32 tmp;
  169.     I32 minlen = 0;        /* must match at least this many chars */
  170.     I32 dontbother = 0;    /* how many characters not to try at end */
  171.     CURCUR cc;
  172.  
  173.     cc.cur = 0;
  174.     cc.oldcc = 0;
  175.     regcc = &cc;
  176.  
  177. #ifdef DEBUGGING
  178.     regnarrate = debug & 512;
  179.     regprogram = prog->program;
  180. #endif
  181.  
  182.     /* Be paranoid... */
  183.     if (prog == NULL || startpos == NULL) {
  184.     croak("NULL regexp parameter");
  185.     return 0;
  186.     }
  187.  
  188.     if (startpos == strbeg)    /* is ^ valid at stringarg? */
  189.     regprev = '\n';
  190.     else {
  191.     regprev = stringarg[-1];
  192.     if (!multiline && regprev == '\n')
  193.         regprev = '\0';        /* force ^ to NOT match */
  194.     }
  195.     regprecomp = prog->precomp;
  196.     regnpar = prog->nparens;
  197.     /* Check validity of program. */
  198.     if (UCHARAT(prog->program) != MAGIC) {
  199.     FAIL("corrupted regexp program");
  200.     }
  201.  
  202.     if (prog->do_folding) {
  203.     i = strend - startpos;
  204.     New(1101,c,i+1,char);
  205.     Copy(startpos, c, i+1, char);
  206.     startpos = c;
  207.     strend = startpos + i;
  208.     for (s = startpos; s < strend; s++)
  209.         if (isUPPER(*s))
  210.         *s = toLOWER(*s);
  211.     }
  212.  
  213.     /* If there is a "must appear" string, look for it. */
  214.     s = startpos;
  215.     if (prog->regmust != Nullsv &&
  216.     (!(prog->reganch & ROPT_ANCH)
  217.      || (multiline && prog->regback >= 0)) )
  218.     {
  219.     if (stringarg == strbeg && screamer) {
  220.         if (screamfirst[BmRARE(prog->regmust)] >= 0)
  221.             s = screaminstr(screamer,prog->regmust);
  222.         else
  223.             s = Nullch;
  224.     }
  225.     else
  226.         s = fbm_instr((unsigned char*)s, (unsigned char*)strend,
  227.         prog->regmust);
  228.     if (!s) {
  229.         ++BmUSEFUL(prog->regmust);    /* hooray */
  230.         goto phooey;    /* not present */
  231.     }
  232.     else if (prog->regback >= 0) {
  233.         s -= prog->regback;
  234.         if (s < startpos)
  235.         s = startpos;
  236.         minlen = prog->regback + SvCUR(prog->regmust);
  237.     }
  238.     else if (!prog->naughty && --BmUSEFUL(prog->regmust) < 0) { /* boo */
  239.         SvREFCNT_dec(prog->regmust);
  240.         prog->regmust = Nullsv;    /* disable regmust */
  241.         s = startpos;
  242.     }
  243.     else {
  244.         s = startpos;
  245.         minlen = SvCUR(prog->regmust);
  246.     }
  247.     }
  248.  
  249.     /* Mark beginning of line for ^ . */
  250.     regbol = startpos;
  251.  
  252.     /* Mark end of line for $ (and such) */
  253.     regeol = strend;
  254.  
  255.     /* see how far we have to get to not match where we matched before */
  256.     regtill = startpos+minend;
  257.  
  258.     /* Simplest case:  anchored match need be tried only once. */
  259.     /*  [unless multiline is set] */
  260.     if (prog->reganch & ROPT_ANCH) {
  261.     if (regtry(prog, startpos))
  262.         goto got_it;
  263.     else if (multiline || (prog->reganch & ROPT_IMPLICIT)) {
  264.         if (minlen)
  265.         dontbother = minlen - 1;
  266.         strend -= dontbother;
  267.         /* for multiline we only have to try after newlines */
  268.         if (s > startpos)
  269.         s--;
  270.         while (s < strend) {
  271.         if (*s++ == '\n') {
  272.             if (s < strend && regtry(prog, s))
  273.             goto got_it;
  274.         }
  275.         }
  276.     }
  277.     goto phooey;
  278.     }
  279.  
  280.     /* Messy cases:  unanchored match. */
  281.     if (prog->regstart) {
  282.     if (prog->reganch & ROPT_SKIP) {  /* we have /x+whatever/ */
  283.         /* it must be a one character string */
  284.         i = SvPVX(prog->regstart)[0];
  285.         while (s < strend) {
  286.         if (*s == i) {
  287.             if (regtry(prog, s))
  288.             goto got_it;
  289.             s++;
  290.             while (s < strend && *s == i)
  291.             s++;
  292.         }
  293.         s++;
  294.         }
  295.     }
  296.     else if (SvPOK(prog->regstart) == 3) {
  297.         /* We know what string it must start with. */
  298.         while ((s = fbm_instr((unsigned char*)s,
  299.           (unsigned char*)strend, prog->regstart)) != NULL)
  300.         {
  301.         if (regtry(prog, s))
  302.             goto got_it;
  303.         s++;
  304.         }
  305.     }
  306.     else {
  307.         c = SvPVX(prog->regstart);
  308.         while ((s = ninstr(s, strend, c, c + SvCUR(prog->regstart))) != NULL)
  309.         {
  310.         if (regtry(prog, s))
  311.             goto got_it;
  312.         s++;
  313.         }
  314.     }
  315.     goto phooey;
  316.     }
  317.     /*SUPPRESS 560*/
  318.     if (c = prog->regstclass) {
  319.     I32 doevery = (prog->reganch & ROPT_SKIP) == 0;
  320.  
  321.     if (minlen)
  322.         dontbother = minlen - 1;
  323.     strend -= dontbother;    /* don't bother with what can't match */
  324.     tmp = 1;
  325.     /* We know what class it must start with. */
  326.     switch (OP(c)) {
  327.     case ANYOF:
  328.         c = OPERAND(c);
  329.         while (s < strend) {
  330.         i = UCHARAT(s);
  331.         if (!(c[i >> 3] & (1 << (i&7)))) {
  332.             if (tmp && regtry(prog, s))
  333.             goto got_it;
  334.             else
  335.             tmp = doevery;
  336.         }
  337.         else
  338.             tmp = 1;
  339.         s++;
  340.         }
  341.         break;
  342.     case BOUND:
  343.         if (minlen)
  344.         dontbother++,strend--;
  345.         if (s != startpos) {
  346.         i = s[-1];
  347.         tmp = isALNUM(i);
  348.         }
  349.         else
  350.         tmp = isALNUM(regprev);    /* assume not alphanumeric */
  351.         while (s < strend) {
  352.         i = *s;
  353.         if (tmp != isALNUM(i)) {
  354.             tmp = !tmp;
  355.             if (regtry(prog, s))
  356.             goto got_it;
  357.         }
  358.         s++;
  359.         }
  360.         if ((minlen || tmp) && regtry(prog,s))
  361.         goto got_it;
  362.         break;
  363.     case NBOUND:
  364.         if (minlen)
  365.         dontbother++,strend--;
  366.         if (s != startpos) {
  367.         i = s[-1];
  368.         tmp = isALNUM(i);
  369.         }
  370.         else
  371.         tmp = isALNUM(regprev);    /* assume not alphanumeric */
  372.         while (s < strend) {
  373.         i = *s;
  374.         if (tmp != isALNUM(i))
  375.             tmp = !tmp;
  376.         else if (regtry(prog, s))
  377.             goto got_it;
  378.         s++;
  379.         }
  380.         if ((minlen || !tmp) && regtry(prog,s))
  381.         goto got_it;
  382.         break;
  383.     case ALNUM:
  384.         while (s < strend) {
  385.         i = *s;
  386.         if (isALNUM(i)) {
  387.             if (tmp && regtry(prog, s))
  388.             goto got_it;
  389.             else
  390.             tmp = doevery;
  391.         }
  392.         else
  393.             tmp = 1;
  394.         s++;
  395.         }
  396.         break;
  397.     case NALNUM:
  398.         while (s < strend) {
  399.         i = *s;
  400.         if (!isALNUM(i)) {
  401.             if (tmp && regtry(prog, s))
  402.             goto got_it;
  403.             else
  404.             tmp = doevery;
  405.         }
  406.         else
  407.             tmp = 1;
  408.         s++;
  409.         }
  410.         break;
  411.     case SPACE:
  412.         while (s < strend) {
  413.         if (isSPACE(*s)) {
  414.             if (tmp && regtry(prog, s))
  415.             goto got_it;
  416.             else
  417.             tmp = doevery;
  418.         }
  419.         else
  420.             tmp = 1;
  421.         s++;
  422.         }
  423.         break;
  424.     case NSPACE:
  425.         while (s < strend) {
  426.         if (!isSPACE(*s)) {
  427.             if (tmp && regtry(prog, s))
  428.             goto got_it;
  429.             else
  430.             tmp = doevery;
  431.         }
  432.         else
  433.             tmp = 1;
  434.         s++;
  435.         }
  436.         break;
  437.     case DIGIT:
  438.         while (s < strend) {
  439.         if (isDIGIT(*s)) {
  440.             if (tmp && regtry(prog, s))
  441.             goto got_it;
  442.             else
  443.             tmp = doevery;
  444.         }
  445.         else
  446.             tmp = 1;
  447.         s++;
  448.         }
  449.         break;
  450.     case NDIGIT:
  451.         while (s < strend) {
  452.         if (!isDIGIT(*s)) {
  453.             if (tmp && regtry(prog, s))
  454.             goto got_it;
  455.             else
  456.             tmp = doevery;
  457.         }
  458.         else
  459.             tmp = 1;
  460.         s++;
  461.         }
  462.         break;
  463.     }
  464.     }
  465.     else {
  466.     if (minlen)
  467.         dontbother = minlen - 1;
  468.     strend -= dontbother;
  469.     /* We don't know much -- general case. */
  470.     do {
  471.         if (regtry(prog, s))
  472.         goto got_it;
  473.     } while (s++ < strend);
  474.     }
  475.  
  476.     /* Failure. */
  477.     goto phooey;
  478.  
  479. got_it:
  480.     strend += dontbother;    /* uncheat */
  481.     prog->subbeg = strbeg;
  482.     prog->subend = strend;
  483.     if ((!safebase && (prog->nparens || sawampersand)) || prog->do_folding) {
  484.     i = strend - startpos + (stringarg - strbeg);
  485.     if (safebase) {            /* no need for $digit later */
  486.         s = strbeg;
  487.         prog->subend = s+i;
  488.     }
  489.     else if (strbeg != prog->subbase) {
  490.         s = savepvn(strbeg,i);    /* so $digit will work later */
  491.         if (prog->subbase)
  492.         Safefree(prog->subbase);
  493.         prog->subbeg = prog->subbase = s;
  494.         prog->subend = s+i;
  495.     }
  496.     else {
  497.         prog->subbeg = s = prog->subbase;
  498.         prog->subend = s+i;
  499.     }
  500.     s += (stringarg - strbeg);
  501.     for (i = 0; i <= prog->nparens; i++) {
  502.         if (prog->endp[i]) {
  503.         prog->startp[i] = s + (prog->startp[i] - startpos);
  504.         prog->endp[i] = s + (prog->endp[i] - startpos);
  505.         }
  506.     }
  507.     if (prog->do_folding)
  508.         Safefree(startpos);
  509.     }
  510.     return 1;
  511.  
  512. phooey:
  513.     if (prog->do_folding)
  514.     Safefree(startpos);
  515.     return 0;
  516. }
  517.  
  518. /*
  519.  - regtry - try match at specific point
  520.  */
  521. static I32            /* 0 failure, 1 success */
  522. regtry(prog, startpos)
  523. regexp *prog;
  524. char *startpos;
  525. {
  526.     register I32 i;
  527.     register char **sp;
  528.     register char **ep;
  529.  
  530.     reginput = startpos;
  531.     regstartp = prog->startp;
  532.     regendp = prog->endp;
  533.     reglastparen = &prog->lastparen;
  534.     prog->lastparen = 0;
  535.     regsize = 0;
  536.  
  537.     sp = prog->startp;
  538.     ep = prog->endp;
  539.     if (prog->nparens) {
  540.     for (i = prog->nparens; i >= 0; i--) {
  541.         *sp++ = NULL;
  542.         *ep++ = NULL;
  543.     }
  544.     }
  545.     if (regmatch(prog->program + 1) && reginput >= regtill) {
  546.     prog->startp[0] = startpos;
  547.     prog->endp[0] = reginput;
  548.     return 1;
  549.     }
  550.     else
  551.     return 0;
  552. }
  553.  
  554. /*
  555.  - regmatch - main matching routine
  556.  *
  557.  * Conceptually the strategy is simple:  check to see whether the current
  558.  * node matches, call self recursively to see whether the rest matches,
  559.  * and then act accordingly.  In practice we make some effort to avoid
  560.  * recursion, in particular by going through "ordinary" nodes (that don't
  561.  * need to know whether the rest of the match failed) by a loop instead of
  562.  * by recursion.
  563.  */
  564. /* [lwall] I've hoisted the register declarations to the outer block in order to
  565.  * maybe save a little bit of pushing and popping on the stack.  It also takes
  566.  * advantage of machines that use a register save mask on subroutine entry.
  567.  */
  568. static I32            /* 0 failure, 1 success */
  569. regmatch(prog)
  570. char *prog;
  571. {
  572.     register char *scan;    /* Current node. */
  573.     char *next;            /* Next node. */
  574.     register I32 nextchar;
  575.     register I32 n;        /* no or next */
  576.     register I32 ln;        /* len or last */
  577.     register char *s;        /* operand or save */
  578.     register char *locinput = reginput;
  579.     int minmod = 0;
  580. #ifdef DEBUGGING
  581.     static int regindent = 0;
  582.     regindent++;
  583. #endif
  584.  
  585.     nextchar = *locinput;
  586.     scan = prog;
  587.     while (scan != NULL) {
  588. #ifdef DEBUGGING
  589. #define sayYES goto yes
  590. #define sayNO goto no
  591. #define saySAME(x) if (x) goto yes; else goto no
  592.     if (regnarrate) {
  593.         fprintf(stderr, "%*s%2d%-8.8s\t<%.10s>\n", regindent*2, "",
  594.         scan - regprogram, regprop(scan), locinput);
  595.     }
  596. #else
  597. #define sayYES return 1
  598. #define sayNO return 0
  599. #define saySAME(x) return x
  600. #endif
  601.  
  602. #ifdef REGALIGN
  603.     next = scan + NEXT(scan);
  604.     if (next == scan)
  605.         next = NULL;
  606. #else
  607.     next = regnext(scan);
  608. #endif
  609.  
  610.     switch (OP(scan)) {
  611.     case BOL:
  612.         if (locinput == regbol
  613.         ? regprev == '\n'
  614.         : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
  615.         {
  616.         /* regtill = regbol; */
  617.         break;
  618.         }
  619.         sayNO;
  620.     case MBOL:
  621.         if (locinput == regbol
  622.         ? regprev == '\n'
  623.         : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
  624.         {
  625.         break;
  626.         }
  627.         sayNO;
  628.     case SBOL:
  629.         if (locinput == regbol && regprev == '\n')
  630.         break;
  631.         sayNO;
  632.     case GBOL:
  633.         if (locinput == regbol)
  634.         break;
  635.         sayNO;
  636.     case EOL:
  637.         if (multiline)
  638.         goto meol;
  639.         else
  640.         goto seol;
  641.     case MEOL:
  642.       meol:
  643.         if ((nextchar || locinput < regeol) && nextchar != '\n')
  644.         sayNO;
  645.         break;
  646.     case SEOL:
  647.       seol:
  648.         if ((nextchar || locinput < regeol) && nextchar != '\n')
  649.         sayNO;
  650.         if (regeol - locinput > 1)
  651.         sayNO;
  652.         break;
  653.     case SANY:
  654.         if (!nextchar && locinput >= regeol)
  655.         sayNO;
  656.         nextchar = *++locinput;
  657.         break;
  658.     case ANY:
  659.         if (!nextchar && locinput >= regeol || nextchar == '\n')
  660.         sayNO;
  661.         nextchar = *++locinput;
  662.         break;
  663.     case EXACTLY:
  664.         s = OPERAND(scan);
  665.         ln = *s++;
  666.         /* Inline the first character, for speed. */
  667.         if (*s != nextchar)
  668.         sayNO;
  669.         if (regeol - locinput < ln)
  670.         sayNO;
  671.         if (ln > 1 && bcmp(s, locinput, ln) != 0)
  672.         sayNO;
  673.         locinput += ln;
  674.         nextchar = *locinput;
  675.         break;
  676.     case ANYOF:
  677.         s = OPERAND(scan);
  678.         if (nextchar < 0)
  679.         nextchar = UCHARAT(locinput);
  680.         if (s[nextchar >> 3] & (1 << (nextchar&7)))
  681.         sayNO;
  682.         if (!nextchar && locinput >= regeol)
  683.         sayNO;
  684.         nextchar = *++locinput;
  685.         break;
  686.     case ALNUM:
  687.         if (!nextchar)
  688.         sayNO;
  689.         if (!isALNUM(nextchar))
  690.         sayNO;
  691.         nextchar = *++locinput;
  692.         break;
  693.     case NALNUM:
  694.         if (!nextchar && locinput >= regeol)
  695.         sayNO;
  696.         if (isALNUM(nextchar))
  697.         sayNO;
  698.         nextchar = *++locinput;
  699.         break;
  700.     case NBOUND:
  701.     case BOUND:
  702.         if (locinput == regbol)    /* was last char in word? */
  703.         ln = isALNUM(regprev);
  704.         else 
  705.         ln = isALNUM(locinput[-1]);
  706.         n = isALNUM(nextchar); /* is next char in word? */
  707.         if ((ln == n) == (OP(scan) == BOUND))
  708.         sayNO;
  709.         break;
  710.     case SPACE:
  711.         if (!nextchar && locinput >= regeol)
  712.         sayNO;
  713.         if (!isSPACE(nextchar))
  714.         sayNO;
  715.         nextchar = *++locinput;
  716.         break;
  717.     case NSPACE:
  718.         if (!nextchar)
  719.         sayNO;
  720.         if (isSPACE(nextchar))
  721.         sayNO;
  722.         nextchar = *++locinput;
  723.         break;
  724.     case DIGIT:
  725.         if (!isDIGIT(nextchar))
  726.         sayNO;
  727.         nextchar = *++locinput;
  728.         break;
  729.     case NDIGIT:
  730.         if (!nextchar && locinput >= regeol)
  731.         sayNO;
  732.         if (isDIGIT(nextchar))
  733.         sayNO;
  734.         nextchar = *++locinput;
  735.         break;
  736.     case REF:
  737.         n = ARG1(scan);  /* which paren pair */
  738.         s = regstartp[n];
  739.         if (!s)
  740.         sayNO;
  741.         if (!regendp[n])
  742.         sayNO;
  743.         if (s == regendp[n])
  744.         break;
  745.         /* Inline the first character, for speed. */
  746.         if (*s != nextchar)
  747.         sayNO;
  748.         ln = regendp[n] - s;
  749.         if (locinput + ln > regeol)
  750.         sayNO;
  751.         if (ln > 1 && bcmp(s, locinput, ln) != 0)
  752.         sayNO;
  753.         locinput += ln;
  754.         nextchar = *locinput;
  755.         break;
  756.  
  757.     case NOTHING:
  758.         break;
  759.     case BACK:
  760.         break;
  761.     case OPEN:
  762.         n = ARG1(scan);  /* which paren pair */
  763.         regstartp[n] = locinput;
  764.         if (n > regsize)
  765.         regsize = n;
  766.         break;
  767.     case CLOSE:
  768.         n = ARG1(scan);  /* which paren pair */
  769.         regendp[n] = locinput;
  770.         if (n > *reglastparen)
  771.         *reglastparen = n;
  772.         break;
  773.     case CURLYX: {
  774.         CURCUR cc;
  775.         CHECKPOINT cp = savestack_ix;
  776.         cc.oldcc = regcc;
  777.         regcc = &cc;
  778.         cc.parenfloor = *reglastparen;
  779.         cc.cur = -1;
  780.         cc.min = ARG1(scan);
  781.         cc.max  = ARG2(scan);
  782.         cc.scan = NEXTOPER(scan) + 4;
  783.         cc.next = next;
  784.         cc.minmod = minmod;
  785.         cc.lastloc = 0;
  786.         reginput = locinput;
  787.         n = regmatch(PREVOPER(next));    /* start on the WHILEM */
  788.         regcpblow(cp);
  789.         regcc = cc.oldcc;
  790.         saySAME(n);
  791.         }
  792.         /* NOT REACHED */
  793.     case WHILEM: {
  794.         /*
  795.          * This is really hard to understand, because after we match
  796.          * what we're trying to match, we must make sure the rest of
  797.          * the RE is going to match for sure, and to do that we have
  798.          * to go back UP the parse tree by recursing ever deeper.  And
  799.          * if it fails, we have to reset our parent's current state
  800.          * that we can try again after backing off.
  801.          */
  802.  
  803.         CURCUR* cc = regcc;
  804.         n = cc->cur + 1;    /* how many we know we matched */
  805.         reginput = locinput;
  806.  
  807. #ifdef DEBUGGING
  808.         if (regnarrate)
  809.             fprintf(stderr, "%*s  %d  %lx\n", regindent*2, "",
  810.             n, (long)cc);
  811. #endif
  812.  
  813.         /* If degenerate scan matches "", assume scan done. */
  814.  
  815.         if (locinput == cc->lastloc) {
  816.             regcc = cc->oldcc;
  817.             ln = regcc->cur;
  818.             if (regmatch(cc->next))
  819.             sayYES;
  820.             regcc->cur = ln;
  821.             regcc = cc;
  822.             sayNO;
  823.         }
  824.  
  825.         /* First just match a string of min scans. */
  826.  
  827.         if (n < cc->min) {
  828.             cc->cur = n;
  829.             cc->lastloc = locinput;
  830.             if (regmatch(cc->scan))
  831.             sayYES;
  832.             cc->cur = n - 1;
  833.             sayNO;
  834.         }
  835.  
  836.         /* Prefer next over scan for minimal matching. */
  837.  
  838.         if (cc->minmod) {
  839.             regcc = cc->oldcc;
  840.             ln = regcc->cur;
  841.             if (regmatch(cc->next))
  842.             sayYES;    /* All done. */
  843.             regcc->cur = ln;
  844.             regcc = cc;
  845.  
  846.             if (n >= cc->max)    /* Maximum greed exceeded? */
  847.             sayNO;
  848.  
  849.             /* Try scanning more and see if it helps. */
  850.             reginput = locinput;
  851.             cc->cur = n;
  852.             cc->lastloc = locinput;
  853.             if (regmatch(cc->scan))
  854.             sayYES;
  855.             cc->cur = n - 1;
  856.             sayNO;
  857.         }
  858.  
  859.         /* Prefer scan over next for maximal matching. */
  860.  
  861.         if (n < cc->max) {    /* More greed allowed? */
  862.             regcppush(cc->parenfloor);
  863.             cc->cur = n;
  864.             cc->lastloc = locinput;
  865.             if (regmatch(cc->scan))
  866.             sayYES;
  867.             regcppop();        /* Restore some previous $<digit>s? */
  868.             reginput = locinput;
  869.         }
  870.  
  871.         /* Failed deeper matches of scan, so see if this one works. */
  872.         regcc = cc->oldcc;
  873.         ln = regcc->cur;
  874.         if (regmatch(cc->next))
  875.             sayYES;
  876.         regcc->cur = ln;
  877.         regcc = cc;
  878.         cc->cur = n - 1;
  879.         sayNO;
  880.         }
  881.         /* NOT REACHED */
  882.     case BRANCH: {
  883.         if (OP(next) != BRANCH)      /* No choice. */
  884.             next = NEXTOPER(scan);/* Avoid recursion. */
  885.         else {
  886.             int lastparen = *reglastparen;
  887.             do {
  888.             reginput = locinput;
  889.             if (regmatch(NEXTOPER(scan)))
  890.                 sayYES;
  891.             for (n = *reglastparen; n > lastparen; n--)
  892.                 regendp[n] = 0;
  893.             *reglastparen = n;
  894.                 
  895. #ifdef REGALIGN
  896.             /*SUPPRESS 560*/
  897.             if (n = NEXT(scan))
  898.                 scan += n;
  899.             else
  900.                 scan = NULL;
  901. #else
  902.             scan = regnext(scan);
  903. #endif
  904.             } while (scan != NULL && OP(scan) == BRANCH);
  905.             sayNO;
  906.             /* NOTREACHED */
  907.         }
  908.         }
  909.         break;
  910.     case MINMOD:
  911.         minmod = 1;
  912.         break;
  913.     case CURLY:
  914.         ln = ARG1(scan);  /* min to match */
  915.         n  = ARG2(scan);  /* max to match */
  916.         scan = NEXTOPER(scan) + 4;
  917.         goto repeat;
  918.     case STAR:
  919.         ln = 0;
  920.         n = 32767;
  921.         scan = NEXTOPER(scan);
  922.         goto repeat;
  923.     case PLUS:
  924.         /*
  925.         * Lookahead to avoid useless match attempts
  926.         * when we know what character comes next.
  927.         */
  928.         ln = 1;
  929.         n = 32767;
  930.         scan = NEXTOPER(scan);
  931.       repeat:
  932.         if (OP(next) == EXACTLY)
  933.         nextchar = *(OPERAND(next)+1);
  934.         else
  935.         nextchar = -1000;
  936.         reginput = locinput;
  937.         if (minmod) {
  938.         minmod = 0;
  939.         if (ln && regrepeat(scan, ln) < ln)
  940.             sayNO;
  941.         while (n >= ln || (n == 32767 && ln > 0)) { /* ln overflow ? */
  942.             /* If it could work, try it. */
  943.             if (nextchar == -1000 || *reginput == nextchar)
  944.             if (regmatch(next))
  945.                 sayYES;
  946.             /* Couldn't or didn't -- back up. */
  947.             reginput = locinput + ln;
  948.             if (regrepeat(scan, 1)) {
  949.             ln++;
  950.             reginput = locinput + ln;
  951.             }
  952.             else
  953.             sayNO;
  954.         }
  955.         }
  956.         else {
  957.         n = regrepeat(scan, n);
  958.         if (ln < n && regkind[(U8)OP(next)] == EOL &&
  959.             (!multiline || OP(next) == SEOL))
  960.             ln = n;            /* why back off? */
  961.         while (n >= ln) {
  962.             /* If it could work, try it. */
  963.             if (nextchar == -1000 || *reginput == nextchar)
  964.             if (regmatch(next))
  965.                 sayYES;
  966.             /* Couldn't or didn't -- back up. */
  967.             n--;
  968.             reginput = locinput + n;
  969.         }
  970.         }
  971.         sayNO;
  972.     case SUCCEED:
  973.     case END:
  974.         reginput = locinput;    /* put where regtry can find it */
  975.         sayYES;            /* Success! */
  976.     case IFMATCH:
  977.         reginput = locinput;
  978.         scan = NEXTOPER(scan);
  979.         if (!regmatch(scan))
  980.         sayNO;
  981.         break;
  982.     case UNLESSM:
  983.         reginput = locinput;
  984.         scan = NEXTOPER(scan);
  985.         if (regmatch(scan))
  986.         sayNO;
  987.         break;
  988.     default:
  989.         fprintf(stderr, "%x %d\n",(unsigned)scan,scan[1]);
  990.         FAIL("regexp memory corruption");
  991.     }
  992.     scan = next;
  993.     }
  994.  
  995.     /*
  996.     * We get here only if there's trouble -- normally "case END" is
  997.     * the terminating point.
  998.     */
  999.     FAIL("corrupted regexp pointers");
  1000.     /*NOTREACHED*/
  1001.     sayNO;
  1002.  
  1003. yes:
  1004. #ifdef DEBUGGING
  1005.     regindent--;
  1006. #endif
  1007.     return 1;
  1008.  
  1009. no:
  1010. #ifdef DEBUGGING
  1011.     regindent--;
  1012. #endif
  1013.     return 0;
  1014. }
  1015.  
  1016. /*
  1017.  - regrepeat - repeatedly match something simple, report how many
  1018.  */
  1019. /*
  1020.  * [This routine now assumes that it will only match on things of length 1.
  1021.  * That was true before, but now we assume scan - reginput is the count,
  1022.  * rather than incrementing count on every character.]
  1023.  */
  1024. static I32
  1025. regrepeat(p, max)
  1026. char *p;
  1027. I32 max;
  1028. {
  1029.     register char *scan;
  1030.     register char *opnd;
  1031.     register I32 c;
  1032.     register char *loceol = regeol;
  1033.  
  1034.     scan = reginput;
  1035.     if (max != 32767 && max < loceol - scan)
  1036.       loceol = scan + max;
  1037.     opnd = OPERAND(p);
  1038.     switch (OP(p)) {
  1039.     case ANY:
  1040.     while (scan < loceol && *scan != '\n')
  1041.         scan++;
  1042.     break;
  1043.     case SANY:
  1044.     scan = loceol;
  1045.     break;
  1046.     case EXACTLY:        /* length of string is 1 */
  1047.     opnd++;
  1048.     while (scan < loceol && *opnd == *scan)
  1049.         scan++;
  1050.     break;
  1051.     case ANYOF:
  1052.     c = UCHARAT(scan);
  1053.     while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
  1054.         scan++;
  1055.         c = UCHARAT(scan);
  1056.     }
  1057.     break;
  1058.     case ALNUM:
  1059.     while (scan < loceol && isALNUM(*scan))
  1060.         scan++;
  1061.     break;
  1062.     case NALNUM:
  1063.     while (scan < loceol && !isALNUM(*scan))
  1064.         scan++;
  1065.     break;
  1066.     case SPACE:
  1067.     while (scan < loceol && isSPACE(*scan))
  1068.         scan++;
  1069.     break;
  1070.     case NSPACE:
  1071.     while (scan < loceol && !isSPACE(*scan))
  1072.         scan++;
  1073.     break;
  1074.     case DIGIT:
  1075.     while (scan < loceol && isDIGIT(*scan))
  1076.         scan++;
  1077.     break;
  1078.     case NDIGIT:
  1079.     while (scan < loceol && !isDIGIT(*scan))
  1080.         scan++;
  1081.     break;
  1082.     default:        /* Called on something of 0 width. */
  1083.     break;        /* So match right here or not at all. */
  1084.     }
  1085.  
  1086.     c = scan - reginput;
  1087.     reginput = scan;
  1088.  
  1089.     return(c);
  1090. }
  1091.  
  1092. /*
  1093.  - regnext - dig the "next" pointer out of a node
  1094.  *
  1095.  * [Note, when REGALIGN is defined there are two places in regmatch()
  1096.  * that bypass this code for speed.]
  1097.  */
  1098. char *
  1099. regnext(p)
  1100. register char *p;
  1101. {
  1102.     register I32 offset;
  1103.  
  1104.     if (p == ®dummy)
  1105.     return(NULL);
  1106.  
  1107.     offset = NEXT(p);
  1108.     if (offset == 0)
  1109.     return(NULL);
  1110.  
  1111. #ifdef REGALIGN
  1112.     return(p+offset);
  1113. #else
  1114.     if (OP(p) == BACK)
  1115.     return(p-offset);
  1116.     else
  1117.     return(p+offset);
  1118. #endif
  1119. }
  1120.