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