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