regexec.c

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