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.3 90/02/28 18:14:39 lwall Locked $
  11  *
  12  * $Log:        regexec.c,v $
  13  * Revision 3.0.1.3  90/02/28  18:14:39  lwall
  14  * patch9: /[\200-\377]/ didn't work on machines with signed chars
  15  * patch9: \d, \w, and \s could misfire on characters with high bit set
  16  * patch9: /\bfoo/i didn't work
  17  *
  18  * Revision 3.0.1.2  89/12/21  20:16:27  lwall
  19  * patch7: certain patterns didn't match correctly at end of string
  20  *
  21  * Revision 3.0.1.1  89/11/11  04:52:04  lwall
  22  * patch2: /\b$foo/ didn't work
  23  *
  24  * Revision 3.0  89/10/18  15:22:53  lwall
  25  * 3.0 baseline
  26  *
  27  */
  28
  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) 1989, Larry Wall
  52  ****
  53  ****    You may distribute under the terms of the GNU General Public License
  54  ****    as specified in the README file that comes with the perl 3.0 kit.
  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 #define isALNUM(c) (isascii(c) && (isalpha(c) || isdigit(c) || c == '_'))
  73 #define isSPACE(c) (isascii(c) && isspace(c))
  74 #define isDIGIT(c) (isascii(c) && isdigit(c))
  75 #define isUPPER(c) (isascii(c) && isupper(c))
  76
  77 /*
  78  * regexec and friends
  79  */
  80
  81 /*
  82  * Global work variables for regexec().
  83  */
  84 static char *regprecomp;
  85 static char *reginput;          /* String-input pointer. */
  86 static char regprev;            /* char before regbol, \n if none */
  87 static char *regbol;            /* Beginning of input, for ^ check. */
  88 static char *regeol;            /* End of input, for $ check. */
  89 static char **regstartp;        /* Pointer to startp array. */
  90 static char **regendp;          /* Ditto for endp. */
  91 static char *reglastparen;      /* Similarly for lastparen. */
  92 static char *regtill;
  93
  94 static char *regmystartp[10];   /* For remembering backreferences. */
  95 static char *regmyendp[10];
  96
  97 /*
  98  * Forwards.
  99  */
 100 STATIC int regtry();
 101 STATIC int regmatch();
 102 STATIC int regrepeat();
 103
 104 extern int multiline;
 105
 106 /*
 107  - regexec - match a regexp against a string
 108  */
 109 int
 110 regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
 111 register regexp *prog;
 112 char *stringarg;
 113 register char *strend;  /* pointer to null at end of string */
 114 char *strbeg;   /* real beginning of string */
 115 int minend;     /* end of match must be at least minend after stringarg */
 116 STR *screamer;
 117 int safebase;   /* no need to remember string in subbase */
 118 {
 119         register char *s;
 120         register int i;
 121         register char *c;
 122         register char *string = stringarg;
 123         register int tmp;
 124         int minlen = 0;         /* must match at least this many chars */
 125         int dontbother = 0;     /* how many characters not to try at end */
 126
 127         /* Be paranoid... */
 128         if (prog == NULL || string == NULL) {
 129                 fatal("NULL regexp parameter");
 130                 return(0);
 131         }
 132
 133         if (string == strbeg)   /* is ^ valid at stringarg? */
 134             regprev = '\n';
 135         else
 136             regprev = stringarg[-1];
 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                 if (stringarg == strbeg && screamer) {
 159                         if (screamfirst[prog->regmust->str_rare] >= 0)
 160                                 s = screaminstr(screamer,prog->regmust);
 161                         else
 162                                 s = Nullch;
 163                 }
 164 #ifndef lint
 165                 else
 166                         s = fbminstr((unsigned char*)s, (unsigned char*)strend,
 167                             prog->regmust);
 168 #endif
 169                 if (!s) {
 170                         ++prog->regmust->str_u.str_useful;      /* hooray */
 171                         goto phooey;    /* not present */
 172                 }
 173                 else if (prog->regback >= 0) {
 174                         s -= prog->regback;
 175                         if (s < string)
 176                             s = string;
 177                         minlen = prog->regback + prog->regmust->str_cur;
 178                 }
 179                 else if (--prog->regmust->str_u.str_useful < 0) { /* boo */
 180                         str_free(prog->regmust);
 181                         prog->regmust = Nullstr;        /* disable regmust */
 182                         s = string;
 183                 }
 184                 else {
 185                         s = string;
 186                         minlen = prog->regmust->str_cur;
 187                 }
 188         }
 189
 190         /* Mark beginning of line for ^ . */
 191         regbol = string;
 192
 193         /* Mark end of line for $ (and such) */
 194         regeol = strend;
 195
 196         /* see how far we have to get to not match where we matched before */
 197         regtill = string+minend;
 198
 199         /* Simplest case:  anchored match need be tried only once. */
 200         /*  [unless multiline is set] */
 201         if (prog->reganch) {
 202                 if (regtry(prog, string))
 203                         goto got_it;
 204                 else if (multiline) {
 205                         if (minlen)
 206                             dontbother = minlen - 1;
 207                         strend -= dontbother;
 208                         /* for multiline we only have to try after newlines */
 209                         if (s > string)
 210                             s--;
 211                         for (; s < strend; s++) {
 212                             if (*s == '\n') {
 213                                 if (++s < strend && regtry(prog, s))
 214                                     goto got_it;
 215                             }
 216                         }
 217                 }
 218                 goto phooey;
 219         }
 220
 221         /* Messy cases:  unanchored match. */
 222         if (prog->regstart) {
 223                 /* We know what string it must start with. */
 224                 if (prog->regstart->str_pok == 3) {
 225 #ifndef lint
 226                     while ((s = fbminstr((unsigned char*)s,
 227                       (unsigned char*)strend, prog->regstart)) != NULL)
 228 #else
 229                     while (s = Nullch)
 230 #endif
 231                     {
 232                             if (regtry(prog, s))
 233                                     goto got_it;
 234                             s++;
 235                     }
 236                 }
 237                 else {
 238                     c = prog->regstart->str_ptr;
 239                     while ((s = ninstr(s, strend,
 240                       c, c + prog->regstart->str_cur )) != NULL) {
 241                             if (regtry(prog, s))
 242                                     goto got_it;
 243                             s++;
 244                     }
 245                 }
 246                 goto phooey;
 247         }
 248         if (c = prog->regstclass) {
 249                 if (minlen)
 250                     dontbother = minlen - 1;
 251                 strend -= dontbother;   /* don't bother with what can't match */
 252                 /* We know what class it must start with. */
 253                 switch (OP(c)) {
 254                 case ANYOF: case ANYBUT:
 255                     c = OPERAND(c);
 256                     while (s < strend) {
 257                             i = UCHARAT(s);
 258                             if (!(c[i >> 3] & (1 << (i&7))))
 259                                     if (regtry(prog, s))
 260                                             goto got_it;
 261                             s++;
 262                     }
 263                     break;
 264                 case BOUND:
 265                     if (minlen)
 266                         dontbother++,strend--;
 267                     if (s != string) {
 268                         i = s[-1];
 269                         tmp = isALNUM(i);
 270                     }
 271                     else
 272                         tmp = isALNUM(regprev); /* assume not alphanumeric */
 273                     while (s < strend) {
 274                             i = *s;
 275                             if (tmp != isALNUM(i)) {
 276                                     tmp = !tmp;
 277                                     if (regtry(prog, s))
 278                                             goto got_it;
 279                             }
 280                             s++;
 281                     }
 282                     if ((minlen || tmp) && regtry(prog,s))
 283                             goto got_it;
 284                     break;
 285                 case NBOUND:
 286                     if (minlen)
 287                         dontbother++,strend--;
 288                     if (s != string) {
 289                         i = s[-1];
 290                         tmp = isALNUM(i);
 291                     }
 292                     else
 293                         tmp = isALNUM(regprev); /* assume not alphanumeric */
 294                     while (s < strend) {
 295                             i = *s;
 296                             if (tmp != isALNUM(i))
 297                                     tmp = !tmp;
 298                             else if (regtry(prog, s))
 299                                     goto got_it;
 300                             s++;
 301                     }
 302                     if ((minlen || !tmp) && regtry(prog,s))
 303                             goto got_it;
 304                     break;
 305                 case ALNUM:
 306                     while (s < strend) {
 307                             i = *s;
 308                             if (isALNUM(i))
 309                                     if (regtry(prog, s))
 310                                             goto got_it;
 311                             s++;
 312                     }
 313                     break;
 314                 case NALNUM:
 315                     while (s < strend) {
 316                             i = *s;
 317                             if (!isALNUM(i))
 318                                     if (regtry(prog, s))
 319                                             goto got_it;
 320                             s++;
 321                     }
 322                     break;
 323                 case SPACE:
 324                     while (s < strend) {
 325                             if (isSPACE(*s))
 326                                     if (regtry(prog, s))
 327                                             goto got_it;
 328                             s++;
 329                     }
 330                     break;
 331                 case NSPACE:
 332                     while (s < strend) {
 333                             if (!isSPACE(*s))
 334                                     if (regtry(prog, s))
 335                                             goto got_it;
 336                             s++;
 337                     }
 338                     break;
 339                 case DIGIT:
 340                     while (s < strend) {
 341                             if (isDIGIT(*s))
 342                                     if (regtry(prog, s))
 343                                             goto got_it;
 344                             s++;
 345                     }
 346                     break;
 347                 case NDIGIT:
 348                     while (s < strend) {
 349                             if (!isDIGIT(*s))
 350                                     if (regtry(prog, s))
 351                                             goto got_it;
 352                             s++;
 353                     }
 354                     break;
 355                 }
 356         }
 357         else {
 358                 if (minlen)
 359                     dontbother = minlen - 1;
 360                 strend -= dontbother;
 361                 /* We don't know much -- general case. */
 362                 do {
 363                         if (regtry(prog, s))
 364                                 goto got_it;
 365                 } while (s++ < strend);
 366         }
 367
 368         /* Failure. */
 369         goto phooey;
 370
 371     got_it:
 372         if ((!safebase && (prog->nparens || sawampersand)) || prog->do_folding){
 373                 strend += dontbother;   /* uncheat */
 374                 if (safebase)                   /* no need for $digit later */
 375                     s = strbeg;
 376                 else if (strbeg != prog->subbase) {
 377                     i = strend - string + (stringarg - strbeg);
 378                     s = nsavestr(strbeg,i);     /* so $digit will work later */
 379                     if (prog->subbase)
 380                             Safefree(prog->subbase);
 381                     prog->subbase = s;
 382                 }
 383                 else
 384                     s = prog->subbase;
 385                 s += (stringarg - strbeg);
 386                 for (i = 0; i <= prog->nparens; i++) {
 387                         if (prog->endp[i]) {
 388                             prog->startp[i] = s + (prog->startp[i] - string);
 389                             prog->endp[i] = s + (prog->endp[i] - string);
 390                         }
 391                 }
 392                 if (prog->do_folding)
 393                         Safefree(string);
 394         }
 395         return(1);
 396
 397     phooey:
 398         if (prog->do_folding)
 399                 Safefree(string);
 400         return(0);
 401 }
 402
 403 /*
 404  - regtry - try match at specific point
 405  */
 406 static int                      /* 0 failure, 1 success */
 407 regtry(prog, string)
 408 regexp *prog;
 409 char *string;
 410 {
 411         register int i;
 412         register char **sp;
 413         register char **ep;
 414
 415         reginput = string;
 416         regstartp = prog->startp;
 417         regendp = prog->endp;
 418         reglastparen = &prog->lastparen;
 419         prog->lastparen = 0;
 420
 421         sp = prog->startp;
 422         ep = prog->endp;
 423         if (prog->nparens) {
 424                 for (i = NSUBEXP; i > 0; i--) {
 425                         *sp++ = NULL;
 426                         *ep++ = NULL;
 427                 }
 428         }
 429         if (regmatch(prog->program + 1) && reginput >= regtill) {
 430                 prog->startp[0] = string;
 431                 prog->endp[0] = reginput;
 432                 return(1);
 433         } else
 434                 return(0);
 435 }
 436
 437 /*
 438  - regmatch - main matching routine
 439  *
 440  * Conceptually the strategy is simple:  check to see whether the current
 441  * node matches, call self recursively to see whether the rest matches,
 442  * and then act accordingly.  In practice we make some effort to avoid
 443  * recursion, in particular by going through "ordinary" nodes (that don't
 444  * need to know whether the rest of the match failed) by a loop instead of
 445  * by recursion.
 446  */
 447 /* [lwall] I've hoisted the register declarations to the outer block in order to
 448  * maybe save a little bit of pushing and popping on the stack.  It also takes
 449  * advantage of machines that use a register save mask on subroutine entry.
 450  */
 451 static int                      /* 0 failure, 1 success */
 452 regmatch(prog)
 453 char *prog;
 454 {
 455         register char *scan;    /* Current node. */
 456         char *next;             /* Next node. */
 457         register int nextchar;
 458         register int n;         /* no or next */
 459         register int ln;        /* len or last */
 460         register char *s;       /* operand or save */
 461         register char *locinput = reginput;
 462
 463         nextchar = *locinput;
 464         scan = prog;
 465 #ifdef DEBUGGING
 466         if (scan != NULL && regnarrate)
 467                 fprintf(stderr, "%s(\n", regprop(scan));
 468 #endif
 469         while (scan != NULL) {
 470 #ifdef DEBUGGING
 471                 if (regnarrate)
 472                         fprintf(stderr, "%s...\n", regprop(scan));
 473 #endif
 474
 475 #ifdef REGALIGN
 476                 next = scan + NEXT(scan);
 477                 if (next == scan)
 478                     next = NULL;
 479 #else
 480                 next = regnext(scan);
 481 #endif
 482
 483                 switch (OP(scan)) {
 484                 case BOL:
 485                         if (locinput == regbol ? regprev == '\n' :
 486                             ((nextchar || locinput < regeol) &&
 487                               locinput[-1] == '\n') )
 488                         {
 489                                 regtill--;
 490                                 break;
 491                         }
 492                         return(0);
 493                 case EOL:
 494                         if ((nextchar || locinput < regeol) && nextchar != '\n')
 495                                 return(0);
 496                         regtill--;
 497                         break;
 498                 case ANY:
 499                         if ((nextchar == '\0' && locinput >= regeol) ||
 500                           nextchar == '\n')
 501                                 return(0);
 502                         nextchar = *++locinput;
 503                         break;
 504                 case EXACTLY:
 505                         s = OPERAND(scan);
 506                         ln = *s++;
 507                         /* Inline the first character, for speed. */
 508                         if (*s != nextchar)
 509                                 return(0);
 510                         if (locinput + ln > regeol)
 511                                 return 0;
 512                         if (ln > 1 && bcmp(s, locinput, ln) != 0)
 513                                 return(0);
 514                         locinput += ln;
 515                         nextchar = *locinput;
 516                         break;
 517                 case ANYOF:
 518                 case ANYBUT:
 519                         s = OPERAND(scan);
 520                         if (nextchar < 0)
 521                                 nextchar = UCHARAT(locinput);
 522                         if (s[nextchar >> 3] & (1 << (nextchar&7)))
 523                                 return(0);
 524                         nextchar = *++locinput;
 525                         if (!nextchar && locinput > regeol)
 526                                 return 0;
 527                         break;
 528                 case ALNUM:
 529                         if (!nextchar)
 530                                 return(0);
 531                         if (!isALNUM(nextchar))
 532                                 return(0);
 533                         nextchar = *++locinput;
 534                         break;
 535                 case NALNUM:
 536                         if (!nextchar && locinput >= regeol)
 537                                 return(0);
 538                         if (isALNUM(nextchar))
 539                                 return(0);
 540                         nextchar = *++locinput;
 541                         break;
 542                 case NBOUND:
 543                 case BOUND:
 544                         if (locinput == regbol) /* was last char in word? */
 545                                 ln = isALNUM(regprev);
 546                         else
 547                                 ln = isALNUM(locinput[-1]);
 548                         n = isALNUM(nextchar); /* is next char in word? */
 549                         if ((ln == n) == (OP(scan) == BOUND))
 550                                 return(0);
 551                         break;
 552                 case SPACE:
 553                         if (!nextchar && locinput >= regeol)
 554                                 return(0);
 555                         if (!isSPACE(nextchar))
 556                                 return(0);
 557                         nextchar = *++locinput;
 558                         break;
 559                 case NSPACE:
 560                         if (!nextchar)
 561                                 return(0);
 562                         if (isSPACE(nextchar))
 563                                 return(0);
 564                         nextchar = *++locinput;
 565                         break;
 566                 case DIGIT:
 567                         if (!isDIGIT(nextchar))
 568                                 return(0);
 569                         nextchar = *++locinput;
 570                         break;
 571                 case NDIGIT:
 572                         if (!nextchar && locinput >= regeol)
 573                                 return(0);
 574                         if (isDIGIT(nextchar))
 575                                 return(0);
 576                         nextchar = *++locinput;
 577                         break;
 578                 case REF:
 579                 case REF+1:
 580                 case REF+2:
 581                 case REF+3:
 582                 case REF+4:
 583                 case REF+5:
 584                 case REF+6:
 585                 case REF+7:
 586                 case REF+8:
 587                 case REF+9:
 588                         n = OP(scan) - REF;
 589                         s = regmystartp[n];
 590                         if (!s)
 591                             return(0);
 592                         if (!regmyendp[n])
 593                             return(0);
 594                         if (s == regmyendp[n])
 595                             break;
 596                         /* Inline the first character, for speed. */
 597                         if (*s != nextchar)
 598                                 return(0);
 599                         ln = regmyendp[n] - s;
 600                         if (locinput + ln > regeol)
 601                                 return 0;
 602                         if (ln > 1 && bcmp(s, locinput, ln) != 0)
 603                                 return(0);
 604                         locinput += ln;
 605                         nextchar = *locinput;
 606                         break;
 607
 608                 case NOTHING:
 609                         break;
 610                 case BACK:
 611                         break;
 612                 case OPEN+1:
 613                 case OPEN+2:
 614                 case OPEN+3:
 615                 case OPEN+4:
 616                 case OPEN+5:
 617                 case OPEN+6:
 618                 case OPEN+7:
 619                 case OPEN+8:
 620                 case OPEN+9:
 621                         n = OP(scan) - OPEN;
 622                         reginput = locinput;
 623
 624                         regmystartp[n] = locinput;      /* for REF */
 625                         if (regmatch(next)) {
 626                                 /*
 627                                  * Don't set startp if some later
 628                                  * invocation of the same parentheses
 629                                  * already has.
 630                                  */
 631                                 if (regstartp[n] == NULL)
 632                                         regstartp[n] = locinput;
 633                                 return(1);
 634                         } else
 635                                 return(0);
 636                         /* NOTREACHED */
 637                 case CLOSE+1:
 638                 case CLOSE+2:
 639                 case CLOSE+3:
 640                 case CLOSE+4:
 641                 case CLOSE+5:
 642                 case CLOSE+6:
 643                 case CLOSE+7:
 644                 case CLOSE+8:
 645                 case CLOSE+9: {
 646                                 n = OP(scan) - CLOSE;
 647                                 reginput = locinput;
 648
 649                                 regmyendp[n] = locinput;        /* for REF */
 650                                 if (regmatch(next)) {
 651                                         /*
 652                                          * Don't set endp if some later
 653                                          * invocation of the same parentheses
 654                                          * already has.
 655                                          */
 656                                         if (regendp[n] == NULL) {
 657                                                 regendp[n] = locinput;
 658                                                 if (n > *reglastparen)
 659                                                     *reglastparen = n;
 660                                         }
 661                                         return(1);
 662                                 } else
 663                                         return(0);
 664                         }
 665                         /*NOTREACHED*/
 666                 case BRANCH: {
 667                                 if (OP(next) != BRANCH)         /* No choice. */
 668                                         next = NEXTOPER(scan);  /* Avoid recursion. */
 669                                 else {
 670                                         do {
 671                                                 reginput = locinput;
 672                                                 if (regmatch(NEXTOPER(scan)))
 673                                                         return(1);
 674 #ifdef REGALIGN
 675                                                 if (n = NEXT(scan))
 676                                                     scan += n;
 677                                                 else
 678                                                     scan = NULL;
 679 #else
 680                                                 scan = regnext(scan);
 681 #endif
 682                                         } while (scan != NULL && OP(scan) == BRANCH);
 683                                         return(0);
 684                                         /* NOTREACHED */
 685                                 }
 686                         }
 687                         break;
 688                 case STAR:
 689                 case PLUS:
 690                         /*
 691                          * Lookahead to avoid useless match attempts
 692                          * when we know what character comes next.
 693                          */
 694                         if (OP(next) == EXACTLY)
 695                                 nextchar = *(OPERAND(next)+1);
 696                         else
 697                                 nextchar = -1000;
 698                         ln = (OP(scan) == STAR) ? 0 : 1;
 699                         reginput = locinput;
 700                         n = regrepeat(NEXTOPER(scan));
 701                         while (n >= ln) {
 702                                 /* If it could work, try it. */
 703                                 if (nextchar == -1000 || *reginput == nextchar)
 704                                         if (regmatch(next))
 705                                                 return(1);
 706                                 /* Couldn't or didn't -- back up. */
 707                                 n--;
 708                                 reginput = locinput + n;
 709                         }
 710                         return(0);
 711                 case END:
 712                         reginput = locinput; /* put where regtry can find it */
 713                         return(1);      /* Success! */
 714                 default:
 715                         printf("%x %d\n",scan,scan[1]);
 716                         FAIL("regexp memory corruption");
 717                 }
 718
 719                 scan = next;
 720         }
 721
 722         /*
 723          * We get here only if there's trouble -- normally "case END" is
 724          * the terminating point.
 725          */
 726         FAIL("corrupted regexp pointers");
 727         /*NOTREACHED*/
 728 #ifdef lint
 729         return 0;
 730 #endif
 731 }
 732
 733 /*
 734  - regrepeat - repeatedly match something simple, report how many
 735  */
 736 /*
 737  * [This routine now assumes that it will only match on things of length 1.
 738  * That was true before, but now we assume scan - reginput is the count,
 739  * rather than incrementing count on every character.]
 740  */
 741 static int
 742 regrepeat(p)
 743 char *p;
 744 {
 745         register char *scan;
 746         register char *opnd;
 747         register int c;
 748         register char *loceol = regeol;
 749
 750         scan = reginput;
 751         opnd = OPERAND(p);
 752         switch (OP(p)) {
 753         case ANY:
 754                 while (scan < loceol && *scan != '\n')
 755                         scan++;
 756                 break;
 757         case EXACTLY:           /* length of string is 1 */
 758                 opnd++;
 759                 while (scan < loceol && *opnd == *scan)
 760                         scan++;
 761                 break;
 762         case ANYOF:
 763         case ANYBUT:
 764                 c = UCHARAT(scan);
 765                 while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
 766                         scan++;
 767                         c = UCHARAT(scan);
 768                 }
 769                 break;
 770         case ALNUM:
 771                 while (isALNUM(*scan))
 772                         scan++;
 773                 break;
 774         case NALNUM:
 775                 while (scan < loceol && !isALNUM(*scan))
 776                         scan++;
 777                 break;
 778         case SPACE:
 779                 while (scan < loceol && isSPACE(*scan))
 780                         scan++;
 781                 break;
 782         case NSPACE:
 783                 while (scan < loceol && !isSPACE(*scan))
 784                         scan++;
 785                 break;
 786         case DIGIT:
 787                 while (isDIGIT(*scan))
 788                         scan++;
 789                 break;
 790         case NDIGIT:
 791                 while (scan < loceol && !isDIGIT(*scan))
 792                         scan++;
 793                 break;
 794         default:                /* Oh dear.  Called inappropriately. */
 795                 FAIL("internal regexp foulup");
 796                 /* NOTREACHED */
 797         }
 798
 799         c = scan - reginput;
 800         reginput = scan;
 801
 802         return(c);
 803 }
 804
 805 /*
 806  - regnext - dig the "next" pointer out of a node
 807  *
 808  * [Note, when REGALIGN is defined there are two places in regmatch()
 809  * that bypass this code for speed.]
 810  */
 811 char *
 812 regnext(p)
 813 register char *p;
 814 {
 815         register int offset;
 816
 817         if (p == &regdummy)
 818                 return(NULL);
 819
 820         offset = NEXT(p);
 821         if (offset == 0)
 822                 return(NULL);
 823
 824 #ifdef REGALIGN
 825         return(p+offset);
 826 #else
 827         if (OP(p) == BACK)
 828                 return(p-offset);
 829         else
 830                 return(p+offset);
 831 #endif
 832 }