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                         sv_free(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                 if (safebase)                   /* no need for $digit later */
 436                     s = strbeg;
 437                 else if (strbeg != prog->subbase) {
 438                     i = strend - string + (stringarg - strbeg);
 439                     s = nsavestr(strbeg,i);     /* so $digit will work later */
 440                     if (prog->subbase)
 441                             Safefree(prog->subbase);
 442                     prog->subbeg = prog->subbase = s;
 443                     prog->subend = s+i;
 444                 }
 445                 else {
 446                     i = strend - string + (stringarg - strbeg);
 447                     prog->subbeg = s = prog->subbase;
 448                     prog->subend = s+i;
 449                 }
 450                 s += (stringarg - strbeg);
 451                 for (i = 0; i <= prog->nparens; i++) {
 452                         if (prog->endp[i]) {
 453                             prog->startp[i] = s + (prog->startp[i] - string);
 454                             prog->endp[i] = s + (prog->endp[i] - string);
 455                         }
 456                 }
 457                 if (prog->do_folding)
 458                         Safefree(string);
 459         }
 460         return(1);
 461
 462     phooey:
 463         if (prog->do_folding)
 464                 Safefree(string);
 465         return(0);
 466 }
 467
 468 /*
 469  - regtry - try match at specific point
 470  */
 471 static I32                      /* 0 failure, 1 success */
 472 regtry(prog, string)
 473 regexp *prog;
 474 char *string;
 475 {
 476         register I32 i;
 477         register char **sp;
 478         register char **ep;
 479
 480         reginput = string;
 481         regstartp = prog->startp;
 482         regendp = prog->endp;
 483         reglastparen = &prog->lastparen;
 484         prog->lastparen = 0;
 485
 486         sp = prog->startp;
 487         ep = prog->endp;
 488         if (prog->nparens) {
 489                 for (i = prog->nparens; i >= 0; i--) {
 490                         *sp++ = NULL;
 491                         *ep++ = NULL;
 492                 }
 493         }
 494         if (regmatch(prog->program + 1) && reginput >= regtill) {
 495                 prog->startp[0] = string;
 496                 prog->endp[0] = reginput;
 497                 return(1);
 498         } else
 499                 return(0);
 500 }
 501
 502 /*
 503  - regmatch - main matching routine
 504  *
 505  * Conceptually the strategy is simple:  check to see whether the current
 506  * node matches, call self recursively to see whether the rest matches,
 507  * and then act accordingly.  In practice we make some effort to avoid
 508  * recursion, in particular by going through "ordinary" nodes (that don't
 509  * need to know whether the rest of the match failed) by a loop instead of
 510  * by recursion.
 511  */
 512 /* [lwall] I've hoisted the register declarations to the outer block in order to
 513  * maybe save a little bit of pushing and popping on the stack.  It also takes
 514  * advantage of machines that use a register save mask on subroutine entry.
 515  */
 516 static I32                      /* 0 failure, 1 success */
 517 regmatch(prog)
 518 char *prog;
 519 {
 520         register char *scan;    /* Current node. */
 521         char *next;             /* Next node. */
 522         register I32 nextchar;
 523         register I32 n;         /* no or next */
 524         register I32 ln;        /* len or last */
 525         register char *s;       /* operand or save */
 526         register char *locinput = reginput;
 527
 528         nextchar = *locinput;
 529         scan = prog;
 530 #ifdef DEBUGGING
 531         if (scan != NULL && regnarrate)
 532                 fprintf(stderr, "%s(\n", regprop(scan));
 533 #endif
 534         while (scan != NULL) {
 535 #ifdef DEBUGGING
 536                 if (regnarrate)
 537                         fprintf(stderr, "%s...\n", regprop(scan));
 538 #endif
 539
 540 #ifdef REGALIGN
 541                 next = scan + NEXT(scan);
 542                 if (next == scan)
 543                     next = NULL;
 544 #else
 545                 next = regnext(scan);
 546 #endif
 547
 548                 switch (OP(scan)) {
 549                 case BOL:
 550                         if (locinput == regbol ? regprev == '\n' :
 551                             ((nextchar || locinput < regeol) &&
 552                               locinput[-1] == '\n') )
 553                         {
 554                                 /* regtill = regbol; */
 555                                 break;
 556                         }
 557                         return(0);
 558                 case EOL:
 559                         if ((nextchar || locinput < regeol) && nextchar != '\n')
 560                                 return(0);
 561                         if (!multiline && regeol - locinput > 1)
 562                                 return 0;
 563                         /* regtill = regbol; */
 564                         break;
 565                 case ANY:
 566                         if ((nextchar == '\0' && locinput >= regeol) ||
 567                           nextchar == '\n')
 568                                 return(0);
 569                         nextchar = *++locinput;
 570                         break;
 571                 case EXACTLY:
 572                         s = OPERAND(scan);
 573                         ln = *s++;
 574                         /* Inline the first character, for speed. */
 575                         if (*s != nextchar)
 576                                 return(0);
 577                         if (regeol - locinput < ln)
 578                                 return 0;
 579                         if (ln > 1 && bcmp(s, locinput, ln) != 0)
 580                                 return(0);
 581                         locinput += ln;
 582                         nextchar = *locinput;
 583                         break;
 584                 case ANYOF:
 585                         s = OPERAND(scan);
 586                         if (nextchar < 0)
 587                                 nextchar = UCHARAT(locinput);
 588                         if (s[nextchar >> 3] & (1 << (nextchar&7)))
 589                                 return(0);
 590                         if (!nextchar && locinput >= regeol)
 591                                 return 0;
 592                         nextchar = *++locinput;
 593                         break;
 594                 case ALNUM:
 595                         if (!nextchar)
 596                                 return(0);
 597                         if (!isALNUM(nextchar))
 598                                 return(0);
 599                         nextchar = *++locinput;
 600                         break;
 601                 case NALNUM:
 602                         if (!nextchar && locinput >= regeol)
 603                                 return(0);
 604                         if (isALNUM(nextchar))
 605                                 return(0);
 606                         nextchar = *++locinput;
 607                         break;
 608                 case NBOUND:
 609                 case BOUND:
 610                         if (locinput == regbol) /* was last char in word? */
 611                                 ln = isALNUM(regprev);
 612                         else
 613                                 ln = isALNUM(locinput[-1]);
 614                         n = isALNUM(nextchar); /* is next char in word? */
 615                         if ((ln == n) == (OP(scan) == BOUND))
 616                                 return(0);
 617                         break;
 618                 case SPACE:
 619                         if (!nextchar && locinput >= regeol)
 620                                 return(0);
 621                         if (!isSPACE(nextchar))
 622                                 return(0);
 623                         nextchar = *++locinput;
 624                         break;
 625                 case NSPACE:
 626                         if (!nextchar)
 627                                 return(0);
 628                         if (isSPACE(nextchar))
 629                                 return(0);
 630                         nextchar = *++locinput;
 631                         break;
 632                 case DIGIT:
 633                         if (!isDIGIT(nextchar))
 634                                 return(0);
 635                         nextchar = *++locinput;
 636                         break;
 637                 case NDIGIT:
 638                         if (!nextchar && locinput >= regeol)
 639                                 return(0);
 640                         if (isDIGIT(nextchar))
 641                                 return(0);
 642                         nextchar = *++locinput;
 643                         break;
 644                 case REF:
 645                         n = ARG1(scan);  /* which paren pair */
 646                         s = regmystartp[n];
 647                         if (!s)
 648                             return(0);
 649                         if (!regmyendp[n])
 650                             return(0);
 651                         if (s == regmyendp[n])
 652                             break;
 653                         /* Inline the first character, for speed. */
 654                         if (*s != nextchar)
 655                                 return(0);
 656                         ln = regmyendp[n] - s;
 657                         if (locinput + ln > regeol)
 658                                 return 0;
 659                         if (ln > 1 && bcmp(s, locinput, ln) != 0)
 660                                 return(0);
 661                         locinput += ln;
 662                         nextchar = *locinput;
 663                         break;
 664
 665                 case NOTHING:
 666                         break;
 667                 case BACK:
 668                         break;
 669                 case OPEN:
 670                         n = ARG1(scan);  /* which paren pair */
 671                         reginput = locinput;
 672
 673                         regmystartp[n] = locinput;      /* for REF */
 674                         if (regmatch(next)) {
 675                                 /*
 676                                  * Don't set startp if some later
 677                                  * invocation of the same parentheses
 678                                  * already has.
 679                                  */
 680                                 if (regstartp[n] == NULL)
 681                                         regstartp[n] = locinput;
 682                                 return(1);
 683                         } else
 684                                 return(0);
 685                         /* NOTREACHED */
 686                 case CLOSE: {
 687                                 n = ARG1(scan);  /* which paren pair */
 688                                 reginput = locinput;
 689
 690                                 regmyendp[n] = locinput;        /* for REF */
 691                                 if (regmatch(next)) {
 692                                         /*
 693                                          * Don't set endp if some later
 694                                          * invocation of the same parentheses
 695                                          * already has.
 696                                          */
 697                                         if (regendp[n] == NULL) {
 698                                                 regendp[n] = locinput;
 699                                                 if (n > *reglastparen)
 700                                                     *reglastparen = n;
 701                                         }
 702                                         return(1);
 703                                 } else
 704                                         return(0);
 705                         }
 706                         /*NOTREACHED*/
 707                 case BRANCH: {
 708                                 if (OP(next) != BRANCH)         /* No choice. */
 709                                         next = NEXTOPER(scan);  /* Avoid recursion. */
 710                                 else {
 711                                         do {
 712                                                 reginput = locinput;
 713                                                 if (regmatch(NEXTOPER(scan)))
 714                                                         return(1);
 715 #ifdef REGALIGN
 716                                                 /*SUPPRESS 560*/
 717                                                 if (n = NEXT(scan))
 718                                                     scan += n;
 719                                                 else
 720                                                     scan = NULL;
 721 #else
 722                                                 scan = regnext(scan);
 723 #endif
 724                                         } while (scan != NULL && OP(scan) == BRANCH);
 725                                         return(0);
 726                                         /* NOTREACHED */
 727                                 }
 728                         }
 729                         break;
 730 #ifdef NOTYET
 731                 case MINCURLY:
 732                         ln = ARG1(scan);  /* min to match */
 733                         n  = -ARG2(scan);  /* max to match */
 734                         scan = NEXTOPER(scan) + 4;
 735                         goto repeat;
 736 #endif
 737                 case CURLY:
 738                         ln = ARG1(scan);  /* min to match */
 739                         n  = ARG2(scan);  /* max to match */
 740                         scan = NEXTOPER(scan) + 4;
 741                         goto repeat;
 742                 case STAR:
 743                         ln = 0;
 744                         n = 32767;
 745                         scan = NEXTOPER(scan);
 746                         goto repeat;
 747                 case PLUS:
 748                         /*
 749                          * Lookahead to avoid useless match attempts
 750                          * when we know what character comes next.
 751                          */
 752                         ln = 1;
 753                         n = 32767;
 754                         scan = NEXTOPER(scan);
 755                     repeat:
 756                         if (OP(next) == EXACTLY)
 757                                 nextchar = *(OPERAND(next)+1);
 758                         else
 759                                 nextchar = -1000;
 760                         reginput = locinput;
 761                         if (n < 0) {
 762                             n = -n;
 763                             while (n >= ln) {
 764                                     /* If it could work, try it. */
 765                                     if (nextchar == -1000 ||
 766                                         *reginput == nextchar)
 767                                             if (regmatch(next))
 768                                                     return(1);
 769                                     /* Couldn't or didn't -- back up. */
 770                                     ln++;
 771                                     reginput = locinput + ln;
 772                             }
 773                         }
 774                         else {
 775                             n = regrepeat(scan, n);
 776                             if (!multiline && OP(next) == EOL && ln < n)
 777                                 ln = n;                 /* why back off? */
 778                             while (n >= ln) {
 779                                     /* If it could work, try it. */
 780                                     if (nextchar == -1000 ||
 781                                         *reginput == nextchar)
 782                                             if (regmatch(next))
 783                                                     return(1);
 784                                     /* Couldn't or didn't -- back up. */
 785                                     n--;
 786                                     reginput = locinput + n;
 787                             }
 788                         }
 789                         return(0);
 790                 case END:
 791                         reginput = locinput; /* put where regtry can find it */
 792                         return(1);      /* Success! */
 793                 default:
 794                         printf("%x %d\n",scan,scan[1]);
 795                         FAIL("regexp memory corruption");
 796                 }
 797
 798                 scan = next;
 799         }
 800
 801         /*
 802          * We get here only if there's trouble -- normally "case END" is
 803          * the terminating point.
 804          */
 805         FAIL("corrupted regexp pointers");
 806         /*NOTREACHED*/
 807 #ifdef lint
 808         return 0;
 809 #endif
 810 }
 811
 812 /*
 813  - regrepeat - repeatedly match something simple, report how many
 814  */
 815 /*
 816  * [This routine now assumes that it will only match on things of length 1.
 817  * That was true before, but now we assume scan - reginput is the count,
 818  * rather than incrementing count on every character.]
 819  */
 820 static I32
 821 regrepeat(p, max)
 822 char *p;
 823 I32 max;
 824 {
 825         register char *scan;
 826         register char *opnd;
 827         register I32 c;
 828         register char *loceol = regeol;
 829
 830         scan = reginput;
 831         if (max != 32767 && max < loceol - scan)
 832             loceol = scan + max;
 833         opnd = OPERAND(p);
 834         switch (OP(p)) {
 835         case ANY:
 836                 while (scan < loceol && *scan != '\n')
 837                         scan++;
 838                 break;
 839         case EXACTLY:           /* length of string is 1 */
 840                 opnd++;
 841                 while (scan < loceol && *opnd == *scan)
 842                         scan++;
 843                 break;
 844         case ANYOF:
 845                 c = UCHARAT(scan);
 846                 while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
 847                         scan++;
 848                         c = UCHARAT(scan);
 849                 }
 850                 break;
 851         case ALNUM:
 852                 while (scan < loceol && isALNUM(*scan))
 853                         scan++;
 854                 break;
 855         case NALNUM:
 856                 while (scan < loceol && !isALNUM(*scan))
 857                         scan++;
 858                 break;
 859         case SPACE:
 860                 while (scan < loceol && isSPACE(*scan))
 861                         scan++;
 862                 break;
 863         case NSPACE:
 864                 while (scan < loceol && !isSPACE(*scan))
 865                         scan++;
 866                 break;
 867         case DIGIT:
 868                 while (scan < loceol && isDIGIT(*scan))
 869                         scan++;
 870                 break;
 871         case NDIGIT:
 872                 while (scan < loceol && !isDIGIT(*scan))
 873                         scan++;
 874                 break;
 875         default:                /* Oh dear.  Called inappropriately. */
 876                 FAIL("internal regexp foulup");
 877                 /* NOTREACHED */
 878         }
 879
 880         c = scan - reginput;
 881         reginput = scan;
 882
 883         return(c);
 884 }
 885
 886 /*
 887  - regnext - dig the "next" pointer out of a node
 888  *
 889  * [Note, when REGALIGN is defined there are two places in regmatch()
 890  * that bypass this code for speed.]
 891  */
 892 char *
 893 regnext(p)
 894 register char *p;
 895 {
 896         register I32 offset;
 897
 898         if (p == &regdummy)
 899                 return(NULL);
 900
 901         offset = NEXT(p);
 902         if (offset == 0)
 903                 return(NULL);
 904
 905 #ifdef REGALIGN
 906         return(p+offset);
 907 #else
 908         if (OP(p) == BACK)
 909                 return(p-offset);
 910         else
 911                 return(p+offset);
 912 #endif
 913 }