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