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 /*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     strend += dontbother;       /* uncheat */
 475     prog->subbeg = strbeg;
 476     prog->subend = strend;
 477     if ((!safebase && (prog->nparens || sawampersand)) || prog->do_folding) {
 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             fprintf(stderr, "%2d%-8.8s\t<%.10s>\n",
 581                 scan - regprogram, regprop(scan), locinput);
 582 #endif
 583
 584 #ifdef REGALIGN
 585         next = scan + NEXT(scan);
 586         if (next == scan)
 587             next = NULL;
 588 #else
 589         next = regnext(scan);
 590 #endif
 591
 592         switch (OP(scan)) {
 593         case BOL:
 594             if (locinput == regbol
 595                 ? regprev == '\n'
 596                 : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
 597             {
 598                 /* regtill = regbol; */
 599                 break;
 600             }
 601             return 0;
 602         case MBOL:
 603             if (locinput == regbol
 604                 ? regprev == '\n'
 605                 : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
 606             {
 607                 break;
 608             }
 609             return 0;
 610         case SBOL:
 611             if (locinput == regbol && regprev == '\n')
 612                 break;
 613             return 0;
 614         case GBOL:
 615             if (locinput == regbol)
 616                 break;
 617             return 0;
 618         case EOL:
 619             if (multiline)
 620                 goto meol;
 621             else
 622                 goto seol;
 623         case MEOL:
 624           meol:
 625             if ((nextchar || locinput < regeol) && nextchar != '\n')
 626                 return 0;
 627             break;
 628         case SEOL:
 629           seol:
 630             if ((nextchar || locinput < regeol) && nextchar != '\n')
 631                 return 0;
 632             if (regeol - locinput > 1)
 633                 return 0;
 634             break;
 635         case SANY:
 636             if (!nextchar && locinput >= regeol)
 637                 return 0;
 638             nextchar = *++locinput;
 639             break;
 640         case ANY:
 641             if (!nextchar && locinput >= regeol || nextchar == '\n')
 642                 return 0;
 643             nextchar = *++locinput;
 644             break;
 645         case EXACTLY:
 646             s = OPERAND(scan);
 647             ln = *s++;
 648             /* Inline the first character, for speed. */
 649             if (*s != nextchar)
 650                 return 0;
 651             if (regeol - locinput < ln)
 652                 return 0;
 653             if (ln > 1 && bcmp(s, locinput, ln) != 0)
 654                 return 0;
 655             locinput += ln;
 656             nextchar = *locinput;
 657             break;
 658         case ANYOF:
 659             s = OPERAND(scan);
 660             if (nextchar < 0)
 661                 nextchar = UCHARAT(locinput);
 662             if (s[nextchar >> 3] & (1 << (nextchar&7)))
 663                 return 0;
 664             if (!nextchar && locinput >= regeol)
 665                 return 0;
 666             nextchar = *++locinput;
 667             break;
 668         case ALNUM:
 669             if (!nextchar)
 670                 return 0;
 671             if (!isALNUM(nextchar))
 672                 return 0;
 673             nextchar = *++locinput;
 674             break;
 675         case NALNUM:
 676             if (!nextchar && locinput >= regeol)
 677                 return 0;
 678             if (isALNUM(nextchar))
 679                 return 0;
 680             nextchar = *++locinput;
 681             break;
 682         case NBOUND:
 683         case BOUND:
 684             if (locinput == regbol)     /* was last char in word? */
 685                 ln = isALNUM(regprev);
 686             else
 687                 ln = isALNUM(locinput[-1]);
 688             n = isALNUM(nextchar); /* is next char in word? */
 689             if ((ln == n) == (OP(scan) == BOUND))
 690                 return 0;
 691             break;
 692         case SPACE:
 693             if (!nextchar && locinput >= regeol)
 694                 return 0;
 695             if (!isSPACE(nextchar))
 696                 return 0;
 697             nextchar = *++locinput;
 698             break;
 699         case NSPACE:
 700             if (!nextchar)
 701                 return 0;
 702             if (isSPACE(nextchar))
 703                 return 0;
 704             nextchar = *++locinput;
 705             break;
 706         case DIGIT:
 707             if (!isDIGIT(nextchar))
 708                 return 0;
 709             nextchar = *++locinput;
 710             break;
 711         case NDIGIT:
 712             if (!nextchar && locinput >= regeol)
 713                 return 0;
 714             if (isDIGIT(nextchar))
 715                 return 0;
 716             nextchar = *++locinput;
 717             break;
 718         case REF:
 719             n = ARG1(scan);  /* which paren pair */
 720             s = regstartp[n];
 721             if (!s)
 722                 return 0;
 723             if (!regendp[n])
 724                 return 0;
 725             if (s == regendp[n])
 726                 break;
 727             /* Inline the first character, for speed. */
 728             if (*s != nextchar)
 729                 return 0;
 730             ln = regendp[n] - s;
 731             if (locinput + ln > regeol)
 732                 return 0;
 733             if (ln > 1 && bcmp(s, locinput, ln) != 0)
 734                 return 0;
 735             locinput += ln;
 736             nextchar = *locinput;
 737             break;
 738
 739         case NOTHING:
 740             break;
 741         case BACK:
 742             break;
 743         case OPEN:
 744             n = ARG1(scan);  /* which paren pair */
 745             regstartp[n] = locinput;
 746             if (n > regsize)
 747                 regsize = n;
 748             break;
 749         case CLOSE:
 750             n = ARG1(scan);  /* which paren pair */
 751             regendp[n] = locinput;
 752             if (n > *reglastparen)
 753                 *reglastparen = n;
 754             break;
 755         case CURLYX: {
 756                 CURCUR cc;
 757                 CHECKPOINT cp = savestack_ix;
 758                 cc.oldcc = regcc;
 759                 regcc = &cc;
 760                 cc.parenfloor = *reglastparen;
 761                 cc.cur = -1;
 762                 cc.min = ARG1(scan);
 763                 cc.max  = ARG2(scan);
 764                 cc.scan = NEXTOPER(scan) + 4;
 765                 cc.next = next;
 766                 cc.minmod = minmod;
 767                 cc.lastloc = 0;
 768                 reginput = locinput;
 769                 n = regmatch(PREVOPER(next));   /* start on the WHILEM */
 770                 regcpblow(cp);
 771                 regcc = cc.oldcc;
 772                 return n;
 773             }
 774             /* NOT REACHED */
 775         case WHILEM: {
 776                 /*
 777                  * This is really hard to understand, because after we match
 778                  * what we're trying to match, we must make sure the rest of
 779                  * the RE is going to match for sure, and to do that we have
 780                  * to go back UP the parse tree by recursing ever deeper.  And
 781                  * if it fails, we have to reset our parent's current state
 782                  * that we can try again after backing off.
 783                  */
 784
 785                 CURCUR* cc = regcc;
 786                 n = cc->cur + 1;
 787                 reginput = locinput;
 788
 789                 /* If degenerate scan matches "", assume scan done. */
 790
 791                 if (locinput == cc->lastloc) {
 792                     regcc = cc->oldcc;
 793                     ln = regcc->cur;
 794                     if (regmatch(cc->next))
 795                         return TRUE;
 796                     regcc->cur = ln;
 797                     regcc = cc;
 798                     return FALSE;
 799                 }
 800
 801                 /* First just match a string of min scans. */
 802
 803                 if (n < cc->min) {
 804                     cc->cur = n;
 805                     cc->lastloc = locinput;
 806                     return regmatch(cc->scan);
 807                 }
 808
 809                 /* Prefer next over scan for minimal matching. */
 810
 811                 if (cc->minmod) {
 812                     regcc = cc->oldcc;
 813                     ln = regcc->cur;
 814                     if (regmatch(cc->next))
 815                         return TRUE;    /* All done. */
 816                     regcc->cur = ln;
 817                     regcc = cc;
 818
 819                     if (n >= cc->max)   /* Maximum greed exceeded? */
 820                         return FALSE;
 821
 822                     /* Try scanning more and see if it helps. */
 823                     reginput = locinput;
 824                     cc->cur = n;
 825                     cc->lastloc = locinput;
 826                     return regmatch(cc->scan);
 827                 }
 828
 829                 /* Prefer scan over next for maximal matching. */
 830
 831                 if (n < cc->max) {      /* More greed allowed? */
 832                     regcppush(cc->parenfloor);
 833                     cc->cur = n;
 834                     cc->lastloc = locinput;
 835                     if (regmatch(cc->scan))
 836                         return TRUE;
 837                     regcppop();         /* Restore some previous $<digit>s? */
 838                     reginput = locinput;
 839                 }
 840
 841                 /* Failed deeper matches of scan, so see if this one works. */
 842                 regcc = cc->oldcc;
 843                 ln = regcc->cur;
 844                 if (regmatch(cc->next))
 845                     return TRUE;
 846                 regcc->cur = ln;
 847                 regcc = cc;
 848                 return FALSE;
 849             }
 850             /* NOT REACHED */
 851         case BRANCH: {
 852                 if (OP(next) != BRANCH)   /* No choice. */
 853                     next = NEXTOPER(scan);/* Avoid recursion. */
 854                 else {
 855                     int lastparen = *reglastparen;
 856                     do {
 857                         reginput = locinput;
 858                         if (regmatch(NEXTOPER(scan)))
 859                             return 1;
 860                         for (n = *reglastparen; n > lastparen; n--)
 861                             regendp[n] = 0;
 862                         *reglastparen = n;
 863
 864 #ifdef REGALIGN
 865                         /*SUPPRESS 560*/
 866                         if (n = NEXT(scan))
 867                             scan += n;
 868                         else
 869                             scan = NULL;
 870 #else
 871                         scan = regnext(scan);
 872 #endif
 873                     } while (scan != NULL && OP(scan) == BRANCH);
 874                     return 0;
 875                     /* NOTREACHED */
 876                 }
 877             }
 878             break;
 879         case MINMOD:
 880             minmod = 1;
 881             break;
 882         case CURLY:
 883             ln = ARG1(scan);  /* min to match */
 884             n  = ARG2(scan);  /* max to match */
 885             scan = NEXTOPER(scan) + 4;
 886             goto repeat;
 887         case STAR:
 888             ln = 0;
 889             n = 32767;
 890             scan = NEXTOPER(scan);
 891             goto repeat;
 892         case PLUS:
 893             /*
 894             * Lookahead to avoid useless match attempts
 895             * when we know what character comes next.
 896             */
 897             ln = 1;
 898             n = 32767;
 899             scan = NEXTOPER(scan);
 900           repeat:
 901             if (OP(next) == EXACTLY)
 902                 nextchar = *(OPERAND(next)+1);
 903             else
 904                 nextchar = -1000;
 905             reginput = locinput;
 906             if (minmod) {
 907                 minmod = 0;
 908                 if (ln && regrepeat(scan, ln) < ln)
 909                     return 0;
 910                 while (n >= ln) {
 911                     /* If it could work, try it. */
 912                     if (nextchar == -1000 || *reginput == nextchar)
 913                         if (regmatch(next))
 914                             return 1;
 915                     /* Couldn't or didn't -- back up. */
 916                     reginput = locinput + ln;
 917                     if (regrepeat(scan, 1)) {
 918                         ln++;
 919                         reginput = locinput + ln;
 920                     }
 921                     else
 922                         return 0;
 923                 }
 924             }
 925             else {
 926                 n = regrepeat(scan, n);
 927                 if (ln < n && regkind[(U8)OP(next)] == EOL &&
 928                     (!multiline || OP(next) == SEOL))
 929                     ln = n;                     /* why back off? */
 930                 while (n >= ln) {
 931                     /* If it could work, try it. */
 932                     if (nextchar == -1000 || *reginput == nextchar)
 933                         if (regmatch(next))
 934                             return 1;
 935                     /* Couldn't or didn't -- back up. */
 936                     n--;
 937                     reginput = locinput + n;
 938                 }
 939             }
 940             return 0;
 941         case SUCCEED:
 942         case END:
 943             reginput = locinput;        /* put where regtry can find it */
 944             return 1;                   /* Success! */
 945         case IFMATCH:
 946             reginput = locinput;
 947             scan = NEXTOPER(scan);
 948             if (!regmatch(scan))
 949                 return 0;
 950             break;
 951         case UNLESSM:
 952             reginput = locinput;
 953             scan = NEXTOPER(scan);
 954             if (regmatch(scan))
 955                 return 0;
 956             break;
 957         default:
 958             fprintf(stderr, "%x %d\n",(unsigned)scan,scan[1]);
 959             FAIL("regexp memory corruption");
 960         }
 961         scan = next;
 962     }
 963
 964     /*
 965     * We get here only if there's trouble -- normally "case END" is
 966     * the terminating point.
 967     */
 968     FAIL("corrupted regexp pointers");
 969     /*NOTREACHED*/
 970     return 0;
 971 }
 972
 973 /*
 974  - regrepeat - repeatedly match something simple, report how many
 975  */
 976 /*
 977  * [This routine now assumes that it will only match on things of length 1.
 978  * That was true before, but now we assume scan - reginput is the count,
 979  * rather than incrementing count on every character.]
 980  */
 981 static I32
 982 regrepeat(p, max)
 983 char *p;
 984 I32 max;
 985 {
 986     register char *scan;
 987     register char *opnd;
 988     register I32 c;
 989     register char *loceol = regeol;
 990
 991     scan = reginput;
 992     if (max != 32767 && max < loceol - scan)
 993       loceol = scan + max;
 994     opnd = OPERAND(p);
 995     switch (OP(p)) {
 996     case ANY:
 997         while (scan < loceol && *scan != '\n')
 998             scan++;
 999         break;
1000     case SANY:
1001         scan = loceol;
1002         break;
1003     case EXACTLY:               /* length of string is 1 */
1004         opnd++;
1005         while (scan < loceol && *opnd == *scan)
1006             scan++;
1007         break;
1008     case ANYOF:
1009         c = UCHARAT(scan);
1010         while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
1011             scan++;
1012             c = UCHARAT(scan);
1013         }
1014         break;
1015     case ALNUM:
1016         while (scan < loceol && isALNUM(*scan))
1017             scan++;
1018         break;
1019     case NALNUM:
1020         while (scan < loceol && !isALNUM(*scan))
1021             scan++;
1022         break;
1023     case SPACE:
1024         while (scan < loceol && isSPACE(*scan))
1025             scan++;
1026         break;
1027     case NSPACE:
1028         while (scan < loceol && !isSPACE(*scan))
1029             scan++;
1030         break;
1031     case DIGIT:
1032         while (scan < loceol && isDIGIT(*scan))
1033             scan++;
1034         break;
1035     case NDIGIT:
1036         while (scan < loceol && !isDIGIT(*scan))
1037             scan++;
1038         break;
1039     default:            /* Called on something of 0 width. */
1040         break;          /* So match right here or not at all. */
1041     }
1042
1043     c = scan - reginput;
1044     reginput = scan;
1045
1046     return(c);
1047 }
1048
1049 /*
1050  - regnext - dig the "next" pointer out of a node
1051  *
1052  * [Note, when REGALIGN is defined there are two places in regmatch()
1053  * that bypass this code for speed.]
1054  */
1055 char *
1056 regnext(p)
1057 register char *p;
1058 {
1059     register I32 offset;
1060
1061     if (p == &regdummy)
1062         return(NULL);
1063
1064     offset = NEXT(p);
1065     if (offset == 0)
1066         return(NULL);
1067
1068 #ifdef REGALIGN
1069     return(p+offset);
1070 #else
1071     if (OP(p) == BACK)
1072         return(p-offset);
1073     else
1074         return(p+offset);
1075 #endif
1076 }