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 /* $Header: regexec.c,v 3.0.1.6 90/11/10 02:00:57 lwall Locked $
  11  *
  12  * $Log:        regexec.c,v $
  13  * Revision 3.0.1.6  90/11/10  02:00:57  lwall
  14  * patch38: patterns like /^foo.*bar/ sped up some
  15  * patch38: /[^whatever]+/ could scan past end of string
  16  *
  17  * Revision 3.0.1.5  90/10/16  10:25:36  lwall
  18  * patch29: /^pat/ occasionally matched in middle of string when $* = 0
  19  * patch29: /.{n,m}$/ could match with fewer than n characters remaining
  20  * patch29: /\d{9}/ could match more than 9 characters
  21  *
  22  * Revision 3.0.1.4  90/08/09  05:12:03  lwall
  23  * patch19: sped up /x+y/ patterns greatly by not retrying on every x
  24  * patch19: inhibited backoff on patterns anchored to the end like /\s+$/
  25  * patch19: sped up {m,n} on simple items
  26  * patch19: $' broke on embedded nulls
  27  * patch19: $ will now only match at end of string if $* == 0
  28  *
  29  * Revision 3.0.1.3  90/02/28  18:14:39  lwall
  30  * patch9: /[\200-\377]/ didn't work on machines with signed chars
  31  * patch9: \d, \w, and \s could misfire on characters with high bit set
  32  * patch9: /\bfoo/i didn't work
  33  *
  34  * Revision 3.0.1.2  89/12/21  20:16:27  lwall
  35  * patch7: certain patterns didn't match correctly at end of string
  36  *
  37  * Revision 3.0.1.1  89/11/11  04:52:04  lwall
  38  * patch2: /\b$foo/ didn't work
  39  *
  40  * Revision 3.0  89/10/18  15:22:53  lwall
  41  * 3.0 baseline
  42  *
  43  */
  44
  45 /*
  46  * regcomp and regexec -- regsub and regerror are not used in perl
  47  *
  48  *      Copyright (c) 1986 by University of Toronto.
  49  *      Written by Henry Spencer.  Not derived from licensed software.
  50  *
  51  *      Permission is granted to anyone to use this software for any
  52  *      purpose on any computer system, and to redistribute it freely,
  53  *      subject to the following restrictions:
  54  *
  55  *      1. The author is not responsible for the consequences of use of
  56  *              this software, no matter how awful, even if they arise
  57  *              from defects in it.
  58  *
  59  *      2. The origin of this software must not be misrepresented, either
  60  *              by explicit claim or by omission.
  61  *
  62  *      3. Altered versions must be plainly marked as such, and must not
  63  *              be misrepresented as being the original software.
  64  *
  65  ****    Alterations to Henry's code are...
  66  ****
  67  ****    Copyright (c) 1989, Larry Wall
  68  ****
  69  ****    You may distribute under the terms of the GNU General Public License
  70  ****    as specified in the README file that comes with the perl 3.0 kit.
  71  *
  72  * Beware that some of this code is subtly aware of the way operator
  73  * precedence is structured in regular expressions.  Serious changes in
  74  * regular-expression syntax might require a total rethink.
  75  */
  76 #include "EXTERN.h"
  77 #include "perl.h"
  78 #include "regcomp.h"
  79
  80 #ifndef STATIC
  81 #define STATIC  static
  82 #endif
  83
  84 #ifdef DEBUGGING
  85 int regnarrate = 0;
  86 #endif
  87
  88 #define isALNUM(c) (isascii(c) && (isalpha(c) || isdigit(c) || c == '_'))
  89 #define isSPACE(c) (isascii(c) && isspace(c))
  90 #define isDIGIT(c) (isascii(c) && isdigit(c))
  91 #define isUPPER(c) (isascii(c) && isupper(c))
  92
  93 /*
  94  * regexec and friends
  95  */
  96
  97 /*
  98  * Global work variables for regexec().
  99  */
 100 static char *regprecomp;
 101 static char *reginput;          /* String-input pointer. */
 102 static char regprev;            /* char before regbol, \n if none */
 103 static char *regbol;            /* Beginning of input, for ^ check. */
 104 static char *regeol;            /* End of input, for $ check. */
 105 static char **regstartp;        /* Pointer to startp array. */
 106 static char **regendp;          /* Ditto for endp. */
 107 static char *reglastparen;      /* Similarly for lastparen. */
 108 static char *regtill;
 109
 110 static char *regmystartp[10];   /* For remembering backreferences. */
 111 static char *regmyendp[10];
 112
 113 /*
 114  * Forwards.
 115  */
 116 STATIC int regtry();
 117 STATIC int regmatch();
 118 STATIC int regrepeat();
 119
 120 extern int multiline;
 121
 122 /*
 123  - regexec - match a regexp against a string
 124  */
 125 int
 126 regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
 127 register regexp *prog;
 128 char *stringarg;
 129 register char *strend;  /* pointer to null at end of string */
 130 char *strbeg;   /* real beginning of string */
 131 int minend;     /* end of match must be at least minend after stringarg */
 132 STR *screamer;
 133 int safebase;   /* no need to remember string in subbase */
 134 {
 135         register char *s;
 136         register int i;
 137         register char *c;
 138         register char *string = stringarg;
 139         register int tmp;
 140         int minlen = 0;         /* must match at least this many chars */
 141         int dontbother = 0;     /* how many characters not to try at end */
 142
 143         /* Be paranoid... */
 144         if (prog == NULL || string == NULL) {
 145                 fatal("NULL regexp parameter");
 146                 return(0);
 147         }
 148
 149         if (string == strbeg)   /* is ^ valid at stringarg? */
 150             regprev = '\n';
 151         else {
 152             regprev = stringarg[-1];
 153             if (!multiline && regprev == '\n')
 154                 regprev = '\0';         /* force ^ to NOT match */
 155         }
 156         regprecomp = prog->precomp;
 157         /* Check validity of program. */
 158         if (UCHARAT(prog->program) != MAGIC) {
 159                 FAIL("corrupted regexp program");
 160         }
 161
 162         if (prog->do_folding) {
 163                 safebase = FALSE;
 164                 i = strend - string;
 165                 New(1101,c,i+1,char);
 166                 (void)bcopy(string, c, i+1);
 167                 string = c;
 168                 strend = string + i;
 169                 for (s = string; s < strend; s++)
 170                         if (isUPPER(*s))
 171                                 *s = tolower(*s);
 172         }
 173
 174         /* If there is a "must appear" string, look for it. */
 175         s = string;
 176         if (prog->regmust != Nullstr &&
 177             (!(prog->reganch & 1) || (multiline && prog->regback >= 0)) ) {
 178                 if (stringarg == strbeg && screamer) {
 179                         if (screamfirst[prog->regmust->str_rare] >= 0)
 180                                 s = screaminstr(screamer,prog->regmust);
 181                         else
 182                                 s = Nullch;
 183                 }
 184 #ifndef lint
 185                 else
 186                         s = fbminstr((unsigned char*)s, (unsigned char*)strend,
 187                             prog->regmust);
 188 #endif
 189                 if (!s) {
 190                         ++prog->regmust->str_u.str_useful;      /* hooray */
 191                         goto phooey;    /* not present */
 192                 }
 193                 else if (prog->regback >= 0) {
 194                         s -= prog->regback;
 195                         if (s < string)
 196                             s = string;
 197                         minlen = prog->regback + prog->regmust->str_cur;
 198                 }
 199                 else if (--prog->regmust->str_u.str_useful < 0) { /* boo */
 200                         str_free(prog->regmust);
 201                         prog->regmust = Nullstr;        /* disable regmust */
 202                         s = string;
 203                 }
 204                 else {
 205                         s = string;
 206                         minlen = prog->regmust->str_cur;
 207                 }
 208         }
 209
 210         /* Mark beginning of line for ^ . */
 211         regbol = string;
 212
 213         /* Mark end of line for $ (and such) */
 214         regeol = strend;
 215
 216         /* see how far we have to get to not match where we matched before */
 217         regtill = string+minend;
 218
 219         /* Simplest case:  anchored match need be tried only once. */
 220         /*  [unless multiline is set] */
 221         if (prog->reganch & 1) {
 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 & 2) {        /* 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 & 2) == 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->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 = NSUBEXP; 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                 case REF+1:
 654                 case REF+2:
 655                 case REF+3:
 656                 case REF+4:
 657                 case REF+5:
 658                 case REF+6:
 659                 case REF+7:
 660                 case REF+8:
 661                 case REF+9:
 662                         n = OP(scan) - REF;
 663                         s = regmystartp[n];
 664                         if (!s)
 665                             return(0);
 666                         if (!regmyendp[n])
 667                             return(0);
 668                         if (s == regmyendp[n])
 669                             break;
 670                         /* Inline the first character, for speed. */
 671                         if (*s != nextchar)
 672                                 return(0);
 673                         ln = regmyendp[n] - s;
 674                         if (locinput + ln > regeol)
 675                                 return 0;
 676                         if (ln > 1 && bcmp(s, locinput, ln) != 0)
 677                                 return(0);
 678                         locinput += ln;
 679                         nextchar = *locinput;
 680                         break;
 681
 682                 case NOTHING:
 683                         break;
 684                 case BACK:
 685                         break;
 686                 case OPEN+1:
 687                 case OPEN+2:
 688                 case OPEN+3:
 689                 case OPEN+4:
 690                 case OPEN+5:
 691                 case OPEN+6:
 692                 case OPEN+7:
 693                 case OPEN+8:
 694                 case OPEN+9:
 695                         n = OP(scan) - OPEN;
 696                         reginput = locinput;
 697
 698                         regmystartp[n] = locinput;      /* for REF */
 699                         if (regmatch(next)) {
 700                                 /*
 701                                  * Don't set startp if some later
 702                                  * invocation of the same parentheses
 703                                  * already has.
 704                                  */
 705                                 if (regstartp[n] == NULL)
 706                                         regstartp[n] = locinput;
 707                                 return(1);
 708                         } else
 709                                 return(0);
 710                         /* NOTREACHED */
 711                 case CLOSE+1:
 712                 case CLOSE+2:
 713                 case CLOSE+3:
 714                 case CLOSE+4:
 715                 case CLOSE+5:
 716                 case CLOSE+6:
 717                 case CLOSE+7:
 718                 case CLOSE+8:
 719                 case CLOSE+9: {
 720                                 n = OP(scan) - CLOSE;
 721                                 reginput = locinput;
 722
 723                                 regmyendp[n] = locinput;        /* for REF */
 724                                 if (regmatch(next)) {
 725                                         /*
 726                                          * Don't set endp if some later
 727                                          * invocation of the same parentheses
 728                                          * already has.
 729                                          */
 730                                         if (regendp[n] == NULL) {
 731                                                 regendp[n] = locinput;
 732                                                 if (n > *reglastparen)
 733                                                     *reglastparen = n;
 734                                         }
 735                                         return(1);
 736                                 } else
 737                                         return(0);
 738                         }
 739                         /*NOTREACHED*/
 740                 case BRANCH: {
 741                                 if (OP(next) != BRANCH)         /* No choice. */
 742                                         next = NEXTOPER(scan);  /* Avoid recursion. */
 743                                 else {
 744                                         do {
 745                                                 reginput = locinput;
 746                                                 if (regmatch(NEXTOPER(scan)))
 747                                                         return(1);
 748 #ifdef REGALIGN
 749                                                 if (n = NEXT(scan))
 750                                                     scan += n;
 751                                                 else
 752                                                     scan = NULL;
 753 #else
 754                                                 scan = regnext(scan);
 755 #endif
 756                                         } while (scan != NULL && OP(scan) == BRANCH);
 757                                         return(0);
 758                                         /* NOTREACHED */
 759                                 }
 760                         }
 761                         break;
 762                 case CURLY:
 763                         ln = ARG1(scan);  /* min to match */
 764                         n  = ARG2(scan);  /* max to match */
 765                         scan = NEXTOPER(scan) + 4;
 766                         goto repeat;
 767                 case STAR:
 768                         ln = 0;
 769                         n = 0;
 770                         scan = NEXTOPER(scan);
 771                         goto repeat;
 772                 case PLUS:
 773                         /*
 774                          * Lookahead to avoid useless match attempts
 775                          * when we know what character comes next.
 776                          */
 777                         ln = 1;
 778                         n = 0;
 779                         scan = NEXTOPER(scan);
 780                     repeat:
 781                         if (OP(next) == EXACTLY)
 782                                 nextchar = *(OPERAND(next)+1);
 783                         else
 784                                 nextchar = -1000;
 785                         reginput = locinput;
 786                         n = regrepeat(scan, n);
 787                         if (!multiline && OP(next) == EOL && ln < n)
 788                             ln = n;                     /* why back off? */
 789                         while (n >= ln) {
 790                                 /* If it could work, try it. */
 791                                 if (nextchar == -1000 || *reginput == nextchar)
 792                                         if (regmatch(next))
 793                                                 return(1);
 794                                 /* Couldn't or didn't -- back up. */
 795                                 n--;
 796                                 reginput = locinput + n;
 797                         }
 798                         return(0);
 799                 case END:
 800                         reginput = locinput; /* put where regtry can find it */
 801                         return(1);      /* Success! */
 802                 default:
 803                         printf("%x %d\n",scan,scan[1]);
 804                         FAIL("regexp memory corruption");
 805                 }
 806
 807                 scan = next;
 808         }
 809
 810         /*
 811          * We get here only if there's trouble -- normally "case END" is
 812          * the terminating point.
 813          */
 814         FAIL("corrupted regexp pointers");
 815         /*NOTREACHED*/
 816 #ifdef lint
 817         return 0;
 818 #endif
 819 }
 820
 821 /*
 822  - regrepeat - repeatedly match something simple, report how many
 823  */
 824 /*
 825  * [This routine now assumes that it will only match on things of length 1.
 826  * That was true before, but now we assume scan - reginput is the count,
 827  * rather than incrementing count on every character.]
 828  */
 829 static int
 830 regrepeat(p, max)
 831 char *p;
 832 int max;
 833 {
 834         register char *scan;
 835         register char *opnd;
 836         register int c;
 837         register char *loceol = regeol;
 838
 839         scan = reginput;
 840         if (max && max < loceol - scan)
 841             loceol = scan + max;
 842         opnd = OPERAND(p);
 843         switch (OP(p)) {
 844         case ANY:
 845                 while (scan < loceol && *scan != '\n')
 846                         scan++;
 847                 break;
 848         case EXACTLY:           /* length of string is 1 */
 849                 opnd++;
 850                 while (scan < loceol && *opnd == *scan)
 851                         scan++;
 852                 break;
 853         case ANYOF:
 854                 c = UCHARAT(scan);
 855                 while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
 856                         scan++;
 857                         c = UCHARAT(scan);
 858                 }
 859                 break;
 860         case ALNUM:
 861                 while (scan < loceol && isALNUM(*scan))
 862                         scan++;
 863                 break;
 864         case NALNUM:
 865                 while (scan < loceol && !isALNUM(*scan))
 866                         scan++;
 867                 break;
 868         case SPACE:
 869                 while (scan < loceol && isSPACE(*scan))
 870                         scan++;
 871                 break;
 872         case NSPACE:
 873                 while (scan < loceol && !isSPACE(*scan))
 874                         scan++;
 875                 break;
 876         case DIGIT:
 877                 while (scan < loceol && isDIGIT(*scan))
 878                         scan++;
 879                 break;
 880         case NDIGIT:
 881                 while (scan < loceol && !isDIGIT(*scan))
 882                         scan++;
 883                 break;
 884         default:                /* Oh dear.  Called inappropriately. */
 885                 FAIL("internal regexp foulup");
 886                 /* NOTREACHED */
 887         }
 888
 889         c = scan - reginput;
 890         reginput = scan;
 891
 892         return(c);
 893 }
 894
 895 /*
 896  - regnext - dig the "next" pointer out of a node
 897  *
 898  * [Note, when REGALIGN is defined there are two places in regmatch()
 899  * that bypass this code for speed.]
 900  */
 901 char *
 902 regnext(p)
 903 register char *p;
 904 {
 905         register int offset;
 906
 907         if (p == &regdummy)
 908                 return(NULL);
 909
 910         offset = NEXT(p);
 911         if (offset == 0)
 912                 return(NULL);
 913
 914 #ifdef REGALIGN
 915         return(p+offset);
 916 #else
 917         if (OP(p) == BACK)
 918                 return(p-offset);
 919         else
 920                 return(p+offset);
 921 #endif
 922 }