regexec.c

   1 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
   2  * confused with the original package (see point 3 below).  Thanks, Henry!
   3  */
   4
   5 /* Additional note: this code is very heavily munged from Henry's version
   6  * in places.  In some spots I've traded clarity for efficiency, so don't
   7  * blame Henry for some of the lack of readability.
   8  */
   9
  10 /* $RCSfile: regexec.c,v $$Revision: 4.1 $$Date: 92/08/07 18:26:32 $
  11  *
  12  * $Log:        regexec.c,v $
  13  * Revision 4.1  92/08/07  18:26:32  lwall
  14  *
  15  * Revision 4.0.1.4  92/06/08  15:25:50  lwall
  16  * patch20: pattern modifiers i and g didn't interact right
  17  * patch20: in some cases $` and $' didn't get set by match
  18  * patch20: /x{0}/ was wrongly interpreted as /x{0,}/
  19  *
  20  * Revision 4.0.1.3  91/11/05  18:23:55  lwall
  21  * patch11: prepared for ctype implementations that don't define isascii()
  22  * patch11: initial .* in pattern had dependency on value of $*
  23  *
  24  * Revision 4.0.1.2  91/06/07  11:50:33  lwall
  25  * patch4: new copyright notice
  26  * patch4: // wouldn't use previous pattern if it started with a null character
  27  *
  28  * Revision 4.0.1.1  91/04/12  09:07:39  lwall
  29  * patch1: regexec only allocated space for 9 subexpresssions
  30  *
  31  * Revision 4.0  91/03/20  01:39:16  lwall
  32  * 4.0 baseline.
  33  *
  34  */
  35 /*SUPPRESS 112*/
  36 /*
  37  * regcomp and regexec -- regsub and regerror are not used in perl
  38  *
  39  *      Copyright (c) 1986 by University of Toronto.
  40  *      Written by Henry Spencer.  Not derived from licensed software.
  41  *
  42  *      Permission is granted to anyone to use this software for any
  43  *      purpose on any computer system, and to redistribute it freely,
  44  *      subject to the following restrictions:
  45  *
  46  *      1. The author is not responsible for the consequences of use of
  47  *              this software, no matter how awful, even if they arise
  48  *              from defects in it.
  49  *
  50  *      2. The origin of this software must not be misrepresented, either
  51  *              by explicit claim or by omission.
  52  *
  53  *      3. Altered versions must be plainly marked as such, and must not
  54  *              be misrepresented as being the original software.
  55  *
  56  ****    Alterations to Henry's code are...
  57  ****
  58  ****    Copyright (c) 1991, Larry Wall
  59  ****
  60  ****    You may distribute under the terms of either the GNU General Public
  61  ****    License or the Artistic License, as specified in the README file.
  62  *
  63  * Beware that some of this code is subtly aware of the way operator
  64  * precedence is structured in regular expressions.  Serious changes in
  65  * regular-expression syntax might require a total rethink.
  66  */
  67 #include "EXTERN.h"
  68 #include "perl.h"
  69 #include "regcomp.h"
  70
  71 #ifndef STATIC
  72 #define STATIC  static
  73 #endif
  74
  75 #ifdef DEBUGGING
  76 I32 regnarrate = 0;
  77 #endif
  78
  79 /*
  80  * regexec and friends
  81  */
  82
  83 /*
  84  * Forwards.
  85  */
  86 STATIC I32 regtry();
  87 STATIC I32 regmatch();
  88 STATIC I32 regrepeat();
  89
  90 /*
  91  - regexec - match a regexp against a string
  92  */
  93 I32
  94 regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
  95 register regexp *prog;
  96 char *stringarg;
  97 register char *strend;  /* pointer to null at end of string */
  98 char *strbeg;   /* real beginning of string */
  99 I32 minend;     /* end of match must be at least minend after stringarg */
 100 SV *screamer;
 101 I32 safebase;   /* no need to remember string in subbase */
 102 {
 103         register char *s;
 104         register I32 i;
 105         register char *c;
 106         register char *string = stringarg;
 107         register I32 tmp;
 108         I32 minlen = 0;         /* must match at least this many chars */
 109         I32 dontbother = 0;     /* how many characters not to try at end */
 110
 111         /* Be paranoid... */
 112         if (prog == NULL || string == NULL) {
 113                 croak("NULL regexp parameter");
 114                 return(0);
 115         }
 116
 117         if (string == strbeg)   /* is ^ valid at stringarg? */
 118             regprev = '\n';
 119         else {
 120             regprev = stringarg[-1];
 121             if (!multiline && regprev == '\n')
 122                 regprev = '\0';         /* force ^ to NOT match */
 123         }
 124         regprecomp = prog->precomp;
 125         /* Check validity of program. */
 126         if (UCHARAT(prog->program) != MAGIC) {
 127                 FAIL("corrupted regexp program");
 128         }
 129
 130         if (prog->do_folding) {
 131                 i = strend - string;
 132                 New(1101,c,i+1,char);
 133                 Copy(string, c, i+1, char);
 134                 string = c;
 135                 strend = string + i;
 136                 for (s = string; s < strend; s++)
 137                         if (isUPPER(*s))
 138                                 *s = tolower(*s);
 139         }
 140
 141         /* If there is a "must appear" string, look for it. */
 142         s = string;
 143         if (prog->regmust != Nullsv &&
 144             (!(prog->reganch & ROPT_ANCH)
 145              || (multiline && prog->regback >= 0)) ) {
 146                 if (stringarg == strbeg && screamer) {
 147                         if (screamfirst[BmRARE(prog->regmust)] >= 0)
 148                                 s = screaminstr(screamer,prog->regmust);
 149                         else
 150                                 s = Nullch;
 151                 }
 152 #ifndef lint
 153                 else
 154                         s = fbm_instr((unsigned char*)s, (unsigned char*)strend,
 155                             prog->regmust);
 156 #endif
 157                 if (!s) {
 158                         ++BmUSEFUL(prog->regmust);      /* hooray */
 159                         goto phooey;    /* not present */
 160                 }
 161                 else if (prog->regback >= 0) {
 162                         s -= prog->regback;
 163                         if (s < string)
 164                             s = string;
 165                         minlen = prog->regback + SvCUR(prog->regmust);
 166                 }
 167                 else if (--BmUSEFUL(prog->regmust) < 0) { /* boo */
 168                         SvREFCNT_dec(prog->regmust);
 169                         prog->regmust = Nullsv; /* disable regmust */
 170                         s = string;
 171                 }
 172                 else {
 173                         s = string;
 174                         minlen = SvCUR(prog->regmust);
 175                 }
 176         }
 177
 178         /* Mark beginning of line for ^ . */
 179         regbol = string;
 180
 181         /* Mark end of line for $ (and such) */
 182         regeol = strend;
 183
 184         /* see how far we have to get to not match where we matched before */
 185         regtill = string+minend;
 186
 187         /* Allocate our backreference arrays */
 188         if ( regmyp_size < prog->nparens + 1 ) {
 189             /* Allocate or enlarge the arrays */
 190             regmyp_size = prog->nparens + 1;
 191             if ( regmyp_size < 10 ) regmyp_size = 10;   /* minimum */
 192             if ( regmystartp ) {
 193                 /* reallocate larger */
 194                 Renew(regmystartp,regmyp_size,char*);
 195                 Renew(regmyendp,  regmyp_size,char*);
 196             }
 197             else {
 198                 /* Initial allocation */
 199                 New(1102,regmystartp,regmyp_size,char*);
 200                 New(1102,regmyendp,  regmyp_size,char*);
 201             }
 202
 203         }
 204
 205         /* Simplest case:  anchored match need be tried only once. */
 206         /*  [unless multiline is set] */
 207         if (prog->reganch & ROPT_ANCH) {
 208                 if (regtry(prog, string))
 209                         goto got_it;
 210                 else if (multiline || (prog->reganch & ROPT_IMPLICIT)) {
 211                         if (minlen)
 212                             dontbother = minlen - 1;
 213                         strend -= dontbother;
 214                         /* for multiline we only have to try after newlines */
 215                         if (s > string)
 216                             s--;
 217                         while (s < strend) {
 218                             if (*s++ == '\n') {
 219                                 if (s < strend && regtry(prog, s))
 220                                     goto got_it;
 221                             }
 222                         }
 223                 }
 224                 goto phooey;
 225         }
 226
 227         /* Messy cases:  unanchored match. */
 228         if (prog->regstart) {
 229                 if (prog->reganch & ROPT_SKIP) {  /* we have /x+whatever/ */
 230                     /* it must be a one character string */
 231                     i = SvPVX(prog->regstart)[0];
 232                     while (s < strend) {
 233                             if (*s == i) {
 234                                     if (regtry(prog, s))
 235                                             goto got_it;
 236                                     s++;
 237                                     while (s < strend && *s == i)
 238                                         s++;
 239                             }
 240                             s++;
 241                     }
 242                 }
 243                 else if (SvPOK(prog->regstart) == 3) {
 244                     /* We know what string it must start with. */
 245 #ifndef lint
 246                     while ((s = fbm_instr((unsigned char*)s,
 247                       (unsigned char*)strend, prog->regstart)) != NULL)
 248 #else
 249                     while (s = Nullch)
 250 #endif
 251                     {
 252                             if (regtry(prog, s))
 253                                     goto got_it;
 254                             s++;
 255                     }
 256                 }
 257                 else {
 258                     c = SvPVX(prog->regstart);
 259                     while ((s = ninstr(s, strend,
 260                       c, c + SvCUR(prog->regstart) )) != NULL) {
 261                             if (regtry(prog, s))
 262                                     goto got_it;
 263                             s++;
 264                     }
 265                 }
 266                 goto phooey;
 267         }
 268         /*SUPPRESS 560*/
 269         if (c = prog->regstclass) {
 270                 I32 doevery = (prog->reganch & ROPT_SKIP) == 0;
 271
 272                 if (minlen)
 273                     dontbother = minlen - 1;
 274                 strend -= dontbother;   /* don't bother with what can't match */
 275                 tmp = 1;
 276                 /* We know what class it must start with. */
 277                 switch (OP(c)) {
 278                 case ANYOF:
 279                     c = OPERAND(c);
 280                     while (s < strend) {
 281                             i = UCHARAT(s);
 282                             if (!(c[i >> 3] & (1 << (i&7)))) {
 283                                     if (tmp && regtry(prog, s))
 284                                             goto got_it;
 285                                     else
 286                                             tmp = doevery;
 287                             }
 288                             else
 289                                     tmp = 1;
 290                             s++;
 291                     }
 292                     break;
 293                 case BOUND:
 294                     if (minlen)
 295                         dontbother++,strend--;
 296                     if (s != string) {
 297                         i = s[-1];
 298                         tmp = isALNUM(i);
 299                     }
 300                     else
 301                         tmp = isALNUM(regprev); /* assume not alphanumeric */
 302                     while (s < strend) {
 303                             i = *s;
 304                             if (tmp != isALNUM(i)) {
 305                                     tmp = !tmp;
 306                                     if (regtry(prog, s))
 307                                             goto got_it;
 308                             }
 309                             s++;
 310                     }
 311                     if ((minlen || tmp) && regtry(prog,s))
 312                             goto got_it;
 313                     break;
 314                 case NBOUND:
 315                     if (minlen)
 316                         dontbother++,strend--;
 317                     if (s != string) {
 318                         i = s[-1];
 319                         tmp = isALNUM(i);
 320                     }
 321                     else
 322                         tmp = isALNUM(regprev); /* assume not alphanumeric */
 323                     while (s < strend) {
 324                             i = *s;
 325                             if (tmp != isALNUM(i))
 326                                     tmp = !tmp;
 327                             else if (regtry(prog, s))
 328                                     goto got_it;
 329                             s++;
 330                     }
 331                     if ((minlen || !tmp) && regtry(prog,s))
 332                             goto got_it;
 333                     break;
 334                 case ALNUM:
 335                     while (s < strend) {
 336                             i = *s;
 337                             if (isALNUM(i)) {
 338                                     if (tmp && regtry(prog, s))
 339                                             goto got_it;
 340                                     else
 341                                             tmp = doevery;
 342                             }
 343                             else
 344                                     tmp = 1;
 345                             s++;
 346                     }
 347                     break;
 348                 case NALNUM:
 349                     while (s < strend) {
 350                             i = *s;
 351                             if (!isALNUM(i)) {
 352                                     if (tmp && regtry(prog, s))
 353                                             goto got_it;
 354                                     else
 355                                             tmp = doevery;
 356                             }
 357                             else
 358                                     tmp = 1;
 359                             s++;
 360                     }
 361                     break;
 362                 case SPACE:
 363                     while (s < strend) {
 364                             if (isSPACE(*s)) {
 365                                     if (tmp && regtry(prog, s))
 366                                             goto got_it;
 367                                     else
 368                                             tmp = doevery;
 369                             }
 370                             else
 371                                     tmp = 1;
 372                             s++;
 373                     }
 374                     break;
 375                 case NSPACE:
 376                     while (s < strend) {
 377                             if (!isSPACE(*s)) {
 378                                     if (tmp && regtry(prog, s))
 379                                             goto got_it;
 380                                     else
 381                                             tmp = doevery;
 382                             }
 383                             else
 384                                     tmp = 1;
 385                             s++;
 386                     }
 387                     break;
 388                 case DIGIT:
 389                     while (s < strend) {
 390                             if (isDIGIT(*s)) {
 391                                     if (tmp && regtry(prog, s))
 392                                             goto got_it;
 393                                     else
 394                                             tmp = doevery;
 395                             }
 396                             else
 397                                     tmp = 1;
 398                             s++;
 399                     }
 400                     break;
 401                 case NDIGIT:
 402                     while (s < strend) {
 403                             if (!isDIGIT(*s)) {
 404                                     if (tmp && regtry(prog, s))
 405                                             goto got_it;
 406                                     else
 407                                             tmp = doevery;
 408                             }
 409                             else
 410                                     tmp = 1;
 411                             s++;
 412                     }
 413                     break;
 414                 }
 415         }
 416         else {
 417                 if (minlen)
 418                     dontbother = minlen - 1;
 419                 strend -= dontbother;
 420                 /* We don't know much -- general case. */
 421                 do {
 422                         if (regtry(prog, s))
 423                                 goto got_it;
 424                 } while (s++ < strend);
 425         }
 426
 427         /* Failure. */
 428         goto phooey;
 429
 430     got_it:
 431         prog->subbeg = strbeg;
 432         prog->subend = strend;
 433         if ((!safebase && (prog->nparens || sawampersand)) || prog->do_folding){
 434                 strend += dontbother;   /* uncheat */
 435                 i = strend - string + (stringarg - strbeg);
 436                 if (safebase) {                 /* no need for $digit later */
 437                     s = strbeg;
 438                     prog->subend = s+i;
 439                 }
 440                 else if (strbeg != prog->subbase) {
 441                     s = nsavestr(strbeg,i);     /* so $digit will work later */
 442                     if (prog->subbase)
 443                             Safefree(prog->subbase);
 444                     prog->subbeg = prog->subbase = s;
 445                     prog->subend = s+i;
 446                 }
 447                 else {
 448                     prog->subbeg = s = prog->subbase;
 449                     prog->subend = s+i;
 450                 }
 451                 s += (stringarg - strbeg);
 452                 for (i = 0; i <= prog->nparens; i++) {
 453                         if (prog->endp[i]) {
 454                             prog->startp[i] = s + (prog->startp[i] - string);
 455                             prog->endp[i] = s + (prog->endp[i] - string);
 456                         }
 457                 }
 458                 if (prog->do_folding)
 459                         Safefree(string);
 460         }
 461         return(1);
 462
 463     phooey:
 464         if (prog->do_folding)
 465                 Safefree(string);
 466         return(0);
 467 }
 468
 469 /*
 470  - regtry - try match at specific point
 471  */
 472 static I32                      /* 0 failure, 1 success */
 473 regtry(prog, string)
 474 regexp *prog;
 475 char *string;
 476 {
 477         register I32 i;
 478         register char **sp;
 479         register char **ep;
 480
 481         reginput = string;
 482         regstartp = prog->startp;
 483         regendp = prog->endp;
 484         reglastparen = &prog->lastparen;
 485         prog->lastparen = 0;
 486
 487         sp = prog->startp;
 488         ep = prog->endp;
 489         if (prog->nparens) {
 490                 for (i = prog->nparens; i >= 0; i--) {
 491                         *sp++ = NULL;
 492                         *ep++ = NULL;
 493                 }
 494         }
 495         if (regmatch(prog->program + 1) && reginput >= regtill) {
 496                 prog->startp[0] = string;
 497                 prog->endp[0] = reginput;
 498                 return(1);
 499         } else
 500                 return(0);
 501 }
 502
 503 /*
 504  - regmatch - main matching routine
 505  *
 506  * Conceptually the strategy is simple:  check to see whether the current
 507  * node matches, call self recursively to see whether the rest matches,
 508  * and then act accordingly.  In practice we make some effort to avoid
 509  * recursion, in particular by going through "ordinary" nodes (that don't
 510  * need to know whether the rest of the match failed) by a loop instead of
 511  * by recursion.
 512  */
 513 /* [lwall] I've hoisted the register declarations to the outer block in order to
 514  * maybe save a little bit of pushing and popping on the stack.  It also takes
 515  * advantage of machines that use a register save mask on subroutine entry.
 516  */
 517 static I32                      /* 0 failure, 1 success */
 518 regmatch(prog)
 519 char *prog;
 520 {
 521         register char *scan;    /* Current node. */
 522         char *next;             /* Next node. */
 523         register I32 nextchar;
 524         register I32 n;         /* no or next */
 525         register I32 ln;        /* len or last */
 526         register char *s;       /* operand or save */
 527         register char *locinput = reginput;
 528
 529         nextchar = *locinput;
 530         scan = prog;
 531 #ifdef DEBUGGING
 532         if (scan != NULL && regnarrate)
 533                 fprintf(stderr, "%s(\n", regprop(scan));
 534 #endif
 535         while (scan != NULL) {
 536 #ifdef DEBUGGING
 537                 if (regnarrate)
 538                         fprintf(stderr, "%s...\n", regprop(scan));
 539 #endif
 540
 541 #ifdef REGALIGN
 542                 next = scan + NEXT(scan);
 543                 if (next == scan)
 544                     next = NULL;
 545 #else
 546                 next = regnext(scan);
 547 #endif
 548
 549                 switch (OP(scan)) {
 550                 case BOL:
 551                         if (locinput == regbol ? regprev == '\n' :
 552                             ((nextchar || locinput < regeol) &&
 553                               locinput[-1] == '\n') )
 554                         {
 555                                 /* regtill = regbol; */
 556                                 break;
 557                         }
 558                         return(0);
 559                 case EOL:
 560                         if ((nextchar || locinput < regeol) && nextchar != '\n')
 561                                 return(0);
 562                         if (!multiline && regeol - locinput > 1)
 563                                 return 0;
 564                         /* regtill = regbol; */
 565                         break;
 566                 case ANY:
 567                         if ((nextchar == '\0' && locinput >= regeol) ||
 568                           nextchar == '\n')
 569                                 return(0);
 570                         nextchar = *++locinput;
 571                         break;
 572                 case EXACTLY:
 573                         s = OPERAND(scan);
 574                         ln = *s++;
 575                         /* Inline the first character, for speed. */
 576                         if (*s != nextchar)
 577                                 return(0);
 578                         if (regeol - locinput < ln)
 579                                 return 0;
 580                         if (ln > 1 && bcmp(s, locinput, ln) != 0)
 581                                 return(0);
 582                         locinput += ln;
 583                         nextchar = *locinput;
 584                         break;
 585                 case ANYOF:
 586                         s = OPERAND(scan);
 587                         if (nextchar < 0)
 588                                 nextchar = UCHARAT(locinput);
 589                         if (s[nextchar >> 3] & (1 << (nextchar&7)))
 590                                 return(0);
 591                         if (!nextchar && locinput >= regeol)
 592                                 return 0;
 593                         nextchar = *++locinput;
 594                         break;
 595                 case ALNUM:
 596                         if (!nextchar)
 597                                 return(0);
 598                         if (!isALNUM(nextchar))
 599                                 return(0);
 600                         nextchar = *++locinput;
 601                         break;
 602                 case NALNUM:
 603                         if (!nextchar && locinput >= regeol)
 604                                 return(0);
 605                         if (isALNUM(nextchar))
 606                                 return(0);
 607                         nextchar = *++locinput;
 608                         break;
 609                 case NBOUND:
 610                 case BOUND:
 611                         if (locinput == regbol) /* was last char in word? */
 612                                 ln = isALNUM(regprev);
 613                         else
 614                                 ln = isALNUM(locinput[-1]);
 615                         n = isALNUM(nextchar); /* is next char in word? */
 616                         if ((ln == n) == (OP(scan) == BOUND))
 617                                 return(0);
 618                         break;
 619                 case SPACE:
 620                         if (!nextchar && locinput >= regeol)
 621                                 return(0);
 622                         if (!isSPACE(nextchar))
 623                                 return(0);
 624                         nextchar = *++locinput;
 625                         break;
 626                 case NSPACE:
 627                         if (!nextchar)
 628                                 return(0);
 629                         if (isSPACE(nextchar))
 630                                 return(0);
 631                         nextchar = *++locinput;
 632                         break;
 633                 case DIGIT:
 634                         if (!isDIGIT(nextchar))
 635                                 return(0);
 636                         nextchar = *++locinput;
 637                         break;
 638                 case NDIGIT:
 639                         if (!nextchar && locinput >= regeol)
 640                                 return(0);
 641                         if (isDIGIT(nextchar))
 642                                 return(0);
 643                         nextchar = *++locinput;
 644                         break;
 645                 case REF:
 646                         n = ARG1(scan);  /* which paren pair */
 647                         s = regmystartp[n];
 648                         if (!s)
 649                             return(0);
 650                         if (!regmyendp[n])
 651                             return(0);
 652                         if (s == regmyendp[n])
 653                             break;
 654                         /* Inline the first character, for speed. */
 655                         if (*s != nextchar)
 656                                 return(0);
 657                         ln = regmyendp[n] - s;
 658                         if (locinput + ln > regeol)
 659                                 return 0;
 660                         if (ln > 1 && bcmp(s, locinput, ln) != 0)
 661                                 return(0);
 662                         locinput += ln;
 663                         nextchar = *locinput;
 664                         break;
 665
 666                 case NOTHING:
 667                         break;
 668                 case BACK:
 669                         break;
 670                 case OPEN:
 671                         n = ARG1(scan);  /* which paren pair */
 672                         reginput = locinput;
 673
 674                         regmystartp[n] = locinput;      /* for REF */
 675                         if (regmatch(next)) {
 676                                 /*
 677                                  * Don't set startp if some later
 678                                  * invocation of the same parentheses
 679                                  * already has.
 680                                  */
 681                                 if (regstartp[n] == NULL)
 682                                         regstartp[n] = locinput;
 683                                 return(1);
 684                         } else
 685                                 return(0);
 686                         /* NOTREACHED */
 687                 case CLOSE: {
 688                                 n = ARG1(scan);  /* which paren pair */
 689                                 reginput = locinput;
 690
 691                                 regmyendp[n] = locinput;        /* for REF */
 692                                 if (regmatch(next)) {
 693                                         /*
 694                                          * Don't set endp if some later
 695                                          * invocation of the same parentheses
 696                                          * already has.
 697                                          */
 698                                         if (regendp[n] == NULL) {
 699                                                 regendp[n] = locinput;
 700                                                 if (n > *reglastparen)
 701                                                     *reglastparen = n;
 702                                         }
 703                                         return(1);
 704                                 } else
 705                                         return(0);
 706                         }
 707                         /*NOTREACHED*/
 708                 case BRANCH: {
 709                                 if (OP(next) != BRANCH)         /* No choice. */
 710                                         next = NEXTOPER(scan);  /* Avoid recursion. */
 711                                 else {
 712                                         do {
 713                                                 reginput = locinput;
 714                                                 if (regmatch(NEXTOPER(scan)))
 715                                                         return(1);
 716 #ifdef REGALIGN
 717                                                 /*SUPPRESS 560*/
 718                                                 if (n = NEXT(scan))
 719                                                     scan += n;
 720                                                 else
 721                                                     scan = NULL;
 722 #else
 723                                                 scan = regnext(scan);
 724 #endif
 725                                         } while (scan != NULL && OP(scan) == BRANCH);
 726                                         return(0);
 727                                         /* NOTREACHED */
 728                                 }
 729                         }
 730                         break;
 731 #ifdef NOTYET
 732                 case MINCURLY:
 733                         ln = ARG1(scan);  /* min to match */
 734                         n  = -ARG2(scan);  /* max to match */
 735                         scan = NEXTOPER(scan) + 4;
 736                         goto repeat;
 737 #endif
 738                 case CURLY:
 739                         ln = ARG1(scan);  /* min to match */
 740                         n  = ARG2(scan);  /* max to match */
 741                         scan = NEXTOPER(scan) + 4;
 742                         goto repeat;
 743                 case STAR:
 744                         ln = 0;
 745                         n = 32767;
 746                         scan = NEXTOPER(scan);
 747                         goto repeat;
 748                 case PLUS:
 749                         /*
 750                          * Lookahead to avoid useless match attempts
 751                          * when we know what character comes next.
 752                          */
 753                         ln = 1;
 754                         n = 32767;
 755                         scan = NEXTOPER(scan);
 756                     repeat:
 757                         if (OP(next) == EXACTLY)
 758                                 nextchar = *(OPERAND(next)+1);
 759                         else
 760                                 nextchar = -1000;
 761                         reginput = locinput;
 762                         if (n < 0) {
 763                             n = -n;
 764                             while (n >= ln) {
 765                                     /* If it could work, try it. */
 766                                     if (nextchar == -1000 ||
 767                                         *reginput == nextchar)
 768                                             if (regmatch(next))
 769                                                     return(1);
 770                                     /* Couldn't or didn't -- back up. */
 771                                     ln++;
 772                                     reginput = locinput + ln;
 773                             }
 774                         }
 775                         else {
 776                             n = regrepeat(scan, n);
 777                             if (!multiline && OP(next) == EOL && ln < n)
 778                                 ln = n;                 /* why back off? */
 779                             while (n >= ln) {
 780                                     /* If it could work, try it. */
 781                                     if (nextchar == -1000 ||
 782                                         *reginput == nextchar)
 783                                             if (regmatch(next))
 784                                                     return(1);
 785                                     /* Couldn't or didn't -- back up. */
 786                                     n--;
 787                                     reginput = locinput + n;
 788                             }
 789                         }
 790                         return(0);
 791                 case END:
 792                         reginput = locinput; /* put where regtry can find it */
 793                         return(1);      /* Success! */
 794                 default:
 795                         printf("%x %d\n",scan,scan[1]);
 796                         FAIL("regexp memory corruption");
 797                 }
 798
 799                 scan = next;
 800         }
 801
 802         /*
 803          * We get here only if there's trouble -- normally "case END" is
 804          * the terminating point.
 805          */
 806         FAIL("corrupted regexp pointers");
 807         /*NOTREACHED*/
 808 #ifdef lint
 809         return 0;
 810 #endif
 811 }
 812
 813 /*
 814  - regrepeat - repeatedly match something simple, report how many
 815  */
 816 /*
 817  * [This routine now assumes that it will only match on things of length 1.
 818  * That was true before, but now we assume scan - reginput is the count,
 819  * rather than incrementing count on every character.]
 820  */
 821 static I32
 822 regrepeat(p, max)
 823 char *p;
 824 I32 max;
 825 {
 826         register char *scan;
 827         register char *opnd;
 828         register I32 c;
 829         register char *loceol = regeol;
 830
 831         scan = reginput;
 832         if (max != 32767 && max < loceol - scan)
 833             loceol = scan + max;
 834         opnd = OPERAND(p);
 835         switch (OP(p)) {
 836         case ANY:
 837                 while (scan < loceol && *scan != '\n')
 838                         scan++;
 839                 break;
 840         case EXACTLY:           /* length of string is 1 */
 841                 opnd++;
 842                 while (scan < loceol && *opnd == *scan)
 843                         scan++;
 844                 break;
 845         case ANYOF:
 846                 c = UCHARAT(scan);
 847                 while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
 848                         scan++;
 849                         c = UCHARAT(scan);
 850                 }
 851                 break;
 852         case ALNUM:
 853                 while (scan < loceol && isALNUM(*scan))
 854                         scan++;
 855                 break;
 856         case NALNUM:
 857                 while (scan < loceol && !isALNUM(*scan))
 858                         scan++;
 859                 break;
 860         case SPACE:
 861                 while (scan < loceol && isSPACE(*scan))
 862                         scan++;
 863                 break;
 864         case NSPACE:
 865                 while (scan < loceol && !isSPACE(*scan))
 866                         scan++;
 867                 break;
 868         case DIGIT:
 869                 while (scan < loceol && isDIGIT(*scan))
 870                         scan++;
 871                 break;
 872         case NDIGIT:
 873                 while (scan < loceol && !isDIGIT(*scan))
 874                         scan++;
 875                 break;
 876         default:                /* Oh dear.  Called inappropriately. */
 877                 FAIL("internal regexp foulup");
 878                 /* NOTREACHED */
 879         }
 880
 881         c = scan - reginput;
 882         reginput = scan;
 883
 884         return(c);
 885 }
 886
 887 /*
 888  - regnext - dig the "next" pointer out of a node
 889  *
 890  * [Note, when REGALIGN is defined there are two places in regmatch()
 891  * that bypass this code for speed.]
 892  */
 893 char *
 894 regnext(p)
 895 register char *p;
 896 {
 897         register I32 offset;
 898
 899         if (p == &regdummy)
 900                 return(NULL);
 901
 902         offset = NEXT(p);
 903         if (offset == 0)
 904                 return(NULL);
 905
 906 #ifdef REGALIGN
 907         return(p+offset);
 908 #else
 909         if (OP(p) == BACK)
 910                 return(p-offset);
 911         else
 912                 return(p+offset);
 913 #endif
 914 }