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