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.3 $$Date: 91/11/05 18:23:55 $
  11  *
  12  * $Log:        regexec.c,v $
  13  * Revision 4.0.1.3  91/11/05  18:23:55  lwall
  14  * patch11: prepared for ctype implementations that don't define isascii()
  15  * patch11: initial .* in pattern had dependency on value of $*
  16  *
  17  * Revision 4.0.1.2  91/06/07  11:50:33  lwall
  18  * patch4: new copyright notice
  19  * patch4: // wouldn't use previous pattern if it started with a null character
  20  *
  21  * Revision 4.0.1.1  91/04/12  09:07:39  lwall
  22  * patch1: regexec only allocated space for 9 subexpresssions
  23  *
  24  * Revision 4.0  91/03/20  01:39:16  lwall
  25  * 4.0 baseline.
  26  *
  27  */
  28 /*SUPPRESS 112*/
  29 /*
  30  * regcomp and regexec -- regsub and regerror are not used in perl
  31  *
  32  *      Copyright (c) 1986 by University of Toronto.
  33  *      Written by Henry Spencer.  Not derived from licensed software.
  34  *
  35  *      Permission is granted to anyone to use this software for any
  36  *      purpose on any computer system, and to redistribute it freely,
  37  *      subject to the following restrictions:
  38  *
  39  *      1. The author is not responsible for the consequences of use of
  40  *              this software, no matter how awful, even if they arise
  41  *              from defects in it.
  42  *
  43  *      2. The origin of this software must not be misrepresented, either
  44  *              by explicit claim or by omission.
  45  *
  46  *      3. Altered versions must be plainly marked as such, and must not
  47  *              be misrepresented as being the original software.
  48  *
  49  ****    Alterations to Henry's code are...
  50  ****
  51  ****    Copyright (c) 1991, Larry Wall
  52  ****
  53  ****    You may distribute under the terms of either the GNU General Public
  54  ****    License or the Artistic License, as specified in the README file.
  55  *
  56  * Beware that some of this code is subtly aware of the way operator
  57  * precedence is structured in regular expressions.  Serious changes in
  58  * regular-expression syntax might require a total rethink.
  59  */
  60 #include "EXTERN.h"
  61 #include "perl.h"
  62 #include "regcomp.h"
  63
  64 #ifndef STATIC
  65 #define STATIC  static
  66 #endif
  67
  68 #ifdef DEBUGGING
  69 int regnarrate = 0;
  70 #endif
  71
  72 /*
  73  * regexec and friends
  74  */
  75
  76 /*
  77  * Global work variables for regexec().
  78  */
  79 static char *regprecomp;
  80 static char *reginput;          /* String-input pointer. */
  81 static char regprev;            /* char before regbol, \n if none */
  82 static char *regbol;            /* Beginning of input, for ^ check. */
  83 static char *regeol;            /* End of input, for $ check. */
  84 static char **regstartp;        /* Pointer to startp array. */
  85 static char **regendp;          /* Ditto for endp. */
  86 static char *reglastparen;      /* Similarly for lastparen. */
  87 static char *regtill;
  88
  89 static int regmyp_size = 0;
  90 static char **regmystartp = Null(char**);
  91 static char **regmyendp   = Null(char**);
  92
  93 /*
  94  * Forwards.
  95  */
  96 STATIC int regtry();
  97 STATIC int regmatch();
  98 STATIC int regrepeat();
  99
 100 extern int multiline;
 101
 102 /*
 103  - regexec - match a regexp against a string
 104  */
 105 int
 106 regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
 107 register regexp *prog;
 108 char *stringarg;
 109 register char *strend;  /* pointer to null at end of string */
 110 char *strbeg;   /* real beginning of string */
 111 int minend;     /* end of match must be at least minend after stringarg */
 112 STR *screamer;
 113 int safebase;   /* no need to remember string in subbase */
 114 {
 115         register char *s;
 116         register int i;
 117         register char *c;
 118         register char *string = stringarg;
 119         register int tmp;
 120         int minlen = 0;         /* must match at least this many chars */
 121         int dontbother = 0;     /* how many characters not to try at end */
 122
 123         /* Be paranoid... */
 124         if (prog == NULL || string == NULL) {
 125                 fatal("NULL regexp parameter");
 126                 return(0);
 127         }
 128
 129         if (string == strbeg)   /* is ^ valid at stringarg? */
 130             regprev = '\n';
 131         else {
 132             regprev = stringarg[-1];
 133             if (!multiline && regprev == '\n')
 134                 regprev = '\0';         /* force ^ to NOT match */
 135         }
 136         regprecomp = prog->precomp;
 137         /* Check validity of program. */
 138         if (UCHARAT(prog->program) != MAGIC) {
 139                 FAIL("corrupted regexp program");
 140         }
 141
 142         if (prog->do_folding) {
 143                 safebase = FALSE;
 144                 i = strend - string;
 145                 New(1101,c,i+1,char);
 146                 (void)bcopy(string, c, i+1);
 147                 string = c;
 148                 strend = string + i;
 149                 for (s = string; s < strend; s++)
 150                         if (isUPPER(*s))
 151                                 *s = tolower(*s);
 152         }
 153
 154         /* If there is a "must appear" string, look for it. */
 155         s = string;
 156         if (prog->regmust != Nullstr &&
 157             (!(prog->reganch & ROPT_ANCH)
 158              || (multiline && prog->regback >= 0)) ) {
 159                 if (stringarg == strbeg && screamer) {
 160                         if (screamfirst[prog->regmust->str_rare] >= 0)
 161                                 s = screaminstr(screamer,prog->regmust);
 162                         else
 163                                 s = Nullch;
 164                 }
 165 #ifndef lint
 166                 else
 167                         s = fbminstr((unsigned char*)s, (unsigned char*)strend,
 168                             prog->regmust);
 169 #endif
 170                 if (!s) {
 171                         ++prog->regmust->str_u.str_useful;      /* hooray */
 172                         goto phooey;    /* not present */
 173                 }
 174                 else if (prog->regback >= 0) {
 175                         s -= prog->regback;
 176                         if (s < string)
 177                             s = string;
 178                         minlen = prog->regback + prog->regmust->str_cur;
 179                 }
 180                 else if (--prog->regmust->str_u.str_useful < 0) { /* boo */
 181                         str_free(prog->regmust);
 182                         prog->regmust = Nullstr;        /* disable regmust */
 183                         s = string;
 184                 }
 185                 else {
 186                         s = string;
 187                         minlen = prog->regmust->str_cur;
 188                 }
 189         }
 190
 191         /* Mark beginning of line for ^ . */
 192         regbol = string;
 193
 194         /* Mark end of line for $ (and such) */
 195         regeol = strend;
 196
 197         /* see how far we have to get to not match where we matched before */
 198         regtill = string+minend;
 199
 200         /* Allocate our backreference arrays */
 201         if ( regmyp_size < prog->nparens + 1 ) {
 202             /* Allocate or enlarge the arrays */
 203             regmyp_size = prog->nparens + 1;
 204             if ( regmyp_size < 10 ) regmyp_size = 10;   /* minimum */
 205             if ( regmystartp ) {
 206                 /* reallocate larger */
 207                 Renew(regmystartp,regmyp_size,char*);
 208                 Renew(regmyendp,  regmyp_size,char*);
 209             }
 210             else {
 211                 /* Initial allocation */
 212                 New(1102,regmystartp,regmyp_size,char*);
 213                 New(1102,regmyendp,  regmyp_size,char*);
 214             }
 215
 216         }
 217
 218         /* Simplest case:  anchored match need be tried only once. */
 219         /*  [unless multiline is set] */
 220         if (prog->reganch & ROPT_ANCH) {
 221                 if (regtry(prog, string))
 222                         goto got_it;
 223                 else if (multiline || (prog->reganch & ROPT_IMPLICIT)) {
 224                         if (minlen)
 225                             dontbother = minlen - 1;
 226                         strend -= dontbother;
 227                         /* for multiline we only have to try after newlines */
 228                         if (s > string)
 229                             s--;
 230                         while (s < strend) {
 231                             if (*s++ == '\n') {
 232                                 if (s < strend && regtry(prog, s))
 233                                     goto got_it;
 234                             }
 235                         }
 236                 }
 237                 goto phooey;
 238         }
 239
 240         /* Messy cases:  unanchored match. */
 241         if (prog->regstart) {
 242                 if (prog->reganch & ROPT_SKIP) {  /* we have /x+whatever/ */
 243                     /* it must be a one character string */
 244                     i = prog->regstart->str_ptr[0];
 245                     while (s < strend) {
 246                             if (*s == i) {
 247                                     if (regtry(prog, s))
 248                                             goto got_it;
 249                                     s++;
 250                                     while (s < strend && *s == i)
 251                                         s++;
 252                             }
 253                             s++;
 254                     }
 255                 }
 256                 else if (prog->regstart->str_pok == 3) {
 257                     /* We know what string it must start with. */
 258 #ifndef lint
 259                     while ((s = fbminstr((unsigned char*)s,
 260                       (unsigned char*)strend, prog->regstart)) != NULL)
 261 #else
 262                     while (s = Nullch)
 263 #endif
 264                     {
 265                             if (regtry(prog, s))
 266                                     goto got_it;
 267                             s++;
 268                     }
 269                 }
 270                 else {
 271                     c = prog->regstart->str_ptr;
 272                     while ((s = ninstr(s, strend,
 273                       c, c + prog->regstart->str_cur )) != NULL) {
 274                             if (regtry(prog, s))
 275                                     goto got_it;
 276                             s++;
 277                     }
 278                 }
 279                 goto phooey;
 280         }
 281         /*SUPPRESS 560*/
 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                                                 /*SUPPRESS 560*/
 725                                                 if (n = NEXT(scan))
 726                                                     scan += n;
 727                                                 else
 728                                                     scan = NULL;
 729 #else
 730                                                 scan = regnext(scan);
 731 #endif
 732                                         } while (scan != NULL && OP(scan) == BRANCH);
 733                                         return(0);
 734                                         /* NOTREACHED */
 735                                 }
 736                         }
 737                         break;
 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 = 0;
 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 = 0;
 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                         n = regrepeat(scan, n);
 763                         if (!multiline && OP(next) == EOL && ln < n)
 764                             ln = n;                     /* why back off? */
 765                         while (n >= ln) {
 766                                 /* If it could work, try it. */
 767                                 if (nextchar == -1000 || *reginput == nextchar)
 768                                         if (regmatch(next))
 769                                                 return(1);
 770                                 /* Couldn't or didn't -- back up. */
 771                                 n--;
 772                                 reginput = locinput + n;
 773                         }
 774                         return(0);
 775                 case END:
 776                         reginput = locinput; /* put where regtry can find it */
 777                         return(1);      /* Success! */
 778                 default:
 779                         printf("%x %d\n",scan,scan[1]);
 780                         FAIL("regexp memory corruption");
 781                 }
 782
 783                 scan = next;
 784         }
 785
 786         /*
 787          * We get here only if there's trouble -- normally "case END" is
 788          * the terminating point.
 789          */
 790         FAIL("corrupted regexp pointers");
 791         /*NOTREACHED*/
 792 #ifdef lint
 793         return 0;
 794 #endif
 795 }
 796
 797 /*
 798  - regrepeat - repeatedly match something simple, report how many
 799  */
 800 /*
 801  * [This routine now assumes that it will only match on things of length 1.
 802  * That was true before, but now we assume scan - reginput is the count,
 803  * rather than incrementing count on every character.]
 804  */
 805 static int
 806 regrepeat(p, max)
 807 char *p;
 808 int max;
 809 {
 810         register char *scan;
 811         register char *opnd;
 812         register int c;
 813         register char *loceol = regeol;
 814
 815         scan = reginput;
 816         if (max && max < loceol - scan)
 817             loceol = scan + max;
 818         opnd = OPERAND(p);
 819         switch (OP(p)) {
 820         case ANY:
 821                 while (scan < loceol && *scan != '\n')
 822                         scan++;
 823                 break;
 824         case EXACTLY:           /* length of string is 1 */
 825                 opnd++;
 826                 while (scan < loceol && *opnd == *scan)
 827                         scan++;
 828                 break;
 829         case ANYOF:
 830                 c = UCHARAT(scan);
 831                 while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
 832                         scan++;
 833                         c = UCHARAT(scan);
 834                 }
 835                 break;
 836         case ALNUM:
 837                 while (scan < loceol && isALNUM(*scan))
 838                         scan++;
 839                 break;
 840         case NALNUM:
 841                 while (scan < loceol && !isALNUM(*scan))
 842                         scan++;
 843                 break;
 844         case SPACE:
 845                 while (scan < loceol && isSPACE(*scan))
 846                         scan++;
 847                 break;
 848         case NSPACE:
 849                 while (scan < loceol && !isSPACE(*scan))
 850                         scan++;
 851                 break;
 852         case DIGIT:
 853                 while (scan < loceol && isDIGIT(*scan))
 854                         scan++;
 855                 break;
 856         case NDIGIT:
 857                 while (scan < loceol && !isDIGIT(*scan))
 858                         scan++;
 859                 break;
 860         default:                /* Oh dear.  Called inappropriately. */
 861                 FAIL("internal regexp foulup");
 862                 /* NOTREACHED */
 863         }
 864
 865         c = scan - reginput;
 866         reginput = scan;
 867
 868         return(c);
 869 }
 870
 871 /*
 872  - regnext - dig the "next" pointer out of a node
 873  *
 874  * [Note, when REGALIGN is defined there are two places in regmatch()
 875  * that bypass this code for speed.]
 876  */
 877 char *
 878 regnext(p)
 879 register char *p;
 880 {
 881         register int offset;
 882
 883         if (p == &regdummy)
 884                 return(NULL);
 885
 886         offset = NEXT(p);
 887         if (offset == 0)
 888                 return(NULL);
 889
 890 #ifdef REGALIGN
 891         return(p+offset);
 892 #else
 893         if (OP(p) == BACK)
 894                 return(p-offset);
 895         else
 896                 return(p+offset);
 897 #endif
 898 }