lib/libcompat/regexp/regexp.c

   1 /*
   2  * regcomp and regexec -- regsub and regerror are elsewhere
   3  *
   4  *      Copyright (c) 1986 by University of Toronto.
   5  *      Written by Henry Spencer.  Not derived from licensed software.
   6  *
   7  *      Permission is granted to anyone to use this software for any
   8  *      purpose on any computer system, and to redistribute it freely,
   9  *      subject to the following restrictions:
  10  *
  11  *      1. The author is not responsible for the consequences of use of
  12  *              this software, no matter how awful, even if they arise
  13  *              from defects in it.
  14  *
  15  *      2. The origin of this software must not be misrepresented, either
  16  *              by explicit claim or by omission.
  17  *
  18  *      3. Altered versions must be plainly marked as such, and must not
  19  *              be misrepresented as being the original software.
  20  *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  21  *** hoptoad!gnu, on 27 Dec 1986, to add \n as an alternative to |
  22  *** to assist in implementing egrep.
  23  *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  24  *** hoptoad!gnu, on 27 Dec 1986, to add \< and \> for word-matching
  25  *** as in BSD grep and ex.
  26  *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  27  *** hoptoad!gnu, on 28 Dec 1986, to optimize characters quoted with \.
  28  *** THIS IS AN ALTERED VERSION.  It was altered by James A. Woods,
  29  *** ames!jaw, on 19 June 1987, to quash a regcomp() redundancy.
  30  *
  31  * Beware that some of this code is subtly aware of the way operator
  32  * precedence is structured in regular expressions.  Serious changes in
  33  * regular-expression syntax might require a total rethink.
  34  */
  35 #include <limits.h>
  36 #include <regexp.h>
  37 #include <stdio.h>
  38 #include <ctype.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41 #include "collate.h"
  42 #include "regmagic.h"
  43
  44 /*
  45  * The "internal use only" fields in regexp.h are present to pass info from
  46  * compile to execute that permits the execute phase to run lots faster on
  47  * simple cases.  They are:
  48  *
  49  * regstart     char that must begin a match; '\0' if none obvious
  50  * reganch      is the match anchored (at beginning-of-line only)?
  51  * regmust      string (pointer into program) that match must include, or NULL
  52  * regmlen      length of regmust string
  53  *
  54  * Regstart and reganch permit very fast decisions on suitable starting points
  55  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  56  * of lines that cannot possibly match.  The regmust tests are costly enough
  57  * that regcomp() supplies a regmust only if the r.e. contains something
  58  * potentially expensive (at present, the only such thing detected is * or +
  59  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  60  * supplied because the test in regexec() needs it and regcomp() is computing
  61  * it anyway.
  62  */
  63
  64 /*
  65  * Structure for regexp "program".  This is essentially a linear encoding
  66  * of a nondeterministic finite-state machine (aka syntax charts or
  67  * "railroad normal form" in parsing technology).  Each node is an opcode
  68  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  69  * all nodes except BRANCH implement concatenation; a "next" pointer with
  70  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  71  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  72  * opposed to a collection of them) is never concatenated with anything
  73  * because of operator precedence.)  The operand of some types of node is
  74  * a literal string; for others, it is a node leading into a sub-FSM.  In
  75  * particular, the operand of a BRANCH node is the first node of the branch.
  76  * (NB this is *not* a tree structure:  the tail of the branch connects
  77  * to the thing following the set of BRANCHes.)  The opcodes are:
  78  */
  79
  80 /* definition   number  opnd?   meaning */
  81 #define END     0       /* no   End of program. */
  82 #define BOL     1       /* no   Match "" at beginning of line. */
  83 #define EOL     2       /* no   Match "" at end of line. */
  84 #define ANY     3       /* no   Match any one character. */
  85 #define ANYOF   4       /* str  Match any character in this string. */
  86 #define ANYBUT  5       /* str  Match any character not in this string. */
  87 #define BRANCH  6       /* node Match this alternative, or the next... */
  88 #define BACK    7       /* no   Match "", "next" ptr points backward. */
  89 #define EXACTLY 8       /* str  Match this string. */
  90 #define NOTHING 9       /* no   Match empty string. */
  91 #define STAR    10      /* node Match this (simple) thing 0 or more times. */
  92 #define PLUS    11      /* node Match this (simple) thing 1 or more times. */
  93 #define WORDA   12      /* no   Match "" at wordchar, where prev is nonword */
  94 #define WORDZ   13      /* no   Match "" at nonwordchar, where prev is word */
  95 #define OPEN    20      /* no   Mark this point in input as start of #n. */
  96                         /*      OPEN+1 is number 1, etc. */
  97 #define CLOSE   30      /* no   Analogous to OPEN. */
  98
  99 /*
 100  * Opcode notes:
 101  *
 102  * BRANCH       The set of branches constituting a single choice are hooked
 103  *              together with their "next" pointers, since precedence prevents
 104  *              anything being concatenated to any individual branch.  The
 105  *              "next" pointer of the last BRANCH in a choice points to the
 106  *              thing following the whole choice.  This is also where the
 107  *              final "next" pointer of each individual branch points; each
 108  *              branch starts with the operand node of a BRANCH node.
 109  *
 110  * BACK         Normal "next" pointers all implicitly point forward; BACK
 111  *              exists to make loop structures possible.
 112  *
 113  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
 114  *              BRANCH structures using BACK.  Simple cases (one character
 115  *              per match) are implemented with STAR and PLUS for speed
 116  *              and to minimize recursive plunges.
 117  *
 118  * OPEN,CLOSE   ...are numbered at compile time.
 119  */
 120
 121 /*
 122  * A node is one char of opcode followed by two chars of "next" pointer.
 123  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
 124  * value is a positive offset from the opcode of the node containing it.
 125  * An operand, if any, simply follows the node.  (Note that much of the
 126  * code generation knows about this implicit relationship.)
 127  *
 128  * Using two bytes for the "next" pointer is vast overkill for most things,
 129  * but allows patterns to get big without disasters.
 130  */
 131 #define OP(p)   (*(p))
 132 #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
 133 #define OPERAND(p)      ((p) + 3)
 134
 135 /*
 136  * See regmagic.h for one further detail of program structure.
 137  */
 138
 139
 140 /*
 141  * Utility definitions.
 142  */
 143 #ifndef CHARBITS
 144 #define UCHARAT(p)      ((int)*(unsigned char *)(p))
 145 #else
 146 #define UCHARAT(p)      ((int)*(p)&CHARBITS)
 147 #endif
 148
 149 #define FAIL(m) { regerror(m); return(NULL); }
 150 #define ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')
 151
 152 /*
 153  * Flags to be passed up and down.
 154  */
 155 #define HASWIDTH        01      /* Known never to match null string. */
 156 #define SIMPLE          02      /* Simple enough to be STAR/PLUS operand. */
 157 #define SPSTART         04      /* Starts with * or +. */
 158 #define WORST           0       /* Worst case. */
 159
 160 /*
 161  * Global work variables for regcomp().
 162  */
 163 static char *regparse;          /* Input-scan pointer. */
 164 static int regnpar;             /* () count. */
 165 static char regdummy;
 166 static char *regcode;           /* Code-emit pointer; &regdummy = don't. */
 167 static long regsize;            /* Code size. */
 168
 169 /*
 170  * Forward declarations for regcomp()'s friends.
 171  */
 172 #ifndef STATIC
 173 #define STATIC  static
 174 #endif
 175 STATIC char *reg();
 176 STATIC char *regbranch();
 177 STATIC char *regpiece();
 178 STATIC char *regatom();
 179 STATIC char *regnode();
 180 STATIC char *regnext();
 181 STATIC void regc();
 182 STATIC void reginsert();
 183 STATIC void regtail();
 184 STATIC void regoptail();
 185 #ifdef STRCSPN
 186 STATIC int strcspn();
 187 #endif
 188
 189 /*
 190  - regcomp - compile a regular expression into internal code
 191  *
 192  * We can't allocate space until we know how big the compiled form will be,
 193  * but we can't compile it (and thus know how big it is) until we've got a
 194  * place to put the code.  So we cheat:  we compile it twice, once with code
 195  * generation turned off and size counting turned on, and once "for real".
 196  * This also means that we don't allocate space until we are sure that the
 197  * thing really will compile successfully, and we never have to move the
 198  * code and thus invalidate pointers into it.  (Note that it has to be in
 199  * one piece because free() must be able to free it all.)
 200  *
 201  * Beware that the optimization-preparation code in here knows about some
 202  * of the structure of the compiled regexp.
 203  */
 204 regexp *
 205 regcomp(exp)
 206 const char *exp;
 207 {
 208         register regexp *r;
 209         register char *scan;
 210         register char *longest;
 211         register int len;
 212         int flags;
 213
 214         if (exp == NULL)
 215                 FAIL("NULL argument");
 216
 217         /* First pass: determine size, legality. */
 218 #ifdef notdef
 219         if (exp[0] == '.' && exp[1] == '*') exp += 2;  /* aid grep */
 220 #endif
 221         regparse = (char *)exp;
 222         regnpar = 1;
 223         regsize = 0L;
 224         regcode = &regdummy;
 225         regc(MAGIC);
 226         if (reg(0, &flags) == NULL)
 227                 return(NULL);
 228
 229         /* Small enough for pointer-storage convention? */
 230         if (regsize >= 32767L)          /* Probably could be 65535L. */
 231                 FAIL("regexp too big");
 232
 233         /* Allocate space. */
 234         r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
 235         if (r == NULL)
 236                 FAIL("out of space");
 237
 238         /* Second pass: emit code. */
 239         regparse = (char *)exp;
 240         regnpar = 1;
 241         regcode = r->program;
 242         regc(MAGIC);
 243         if (reg(0, &flags) == NULL)
 244                 return(NULL);
 245
 246         /* Dig out information for optimizations. */
 247         r->regstart = '\0';     /* Worst-case defaults. */
 248         r->reganch = 0;
 249         r->regmust = NULL;
 250         r->regmlen = 0;
 251         scan = r->program+1;                    /* First BRANCH. */
 252         if (OP(regnext(scan)) == END) {         /* Only one top-level choice. */
 253                 scan = OPERAND(scan);
 254
 255                 /* Starting-point info. */
 256                 if (OP(scan) == EXACTLY)
 257                         r->regstart = *OPERAND(scan);
 258                 else if (OP(scan) == BOL)
 259                         r->reganch++;
 260
 261                 /*
 262                  * If there's something expensive in the r.e., find the
 263                  * longest literal string that must appear and make it the
 264                  * regmust.  Resolve ties in favor of later strings, since
 265                  * the regstart check works with the beginning of the r.e.
 266                  * and avoiding duplication strengthens checking.  Not a
 267                  * strong reason, but sufficient in the absence of others.
 268                  */
 269                 if (flags&SPSTART) {
 270                         longest = NULL;
 271                         len = 0;
 272                         for (; scan != NULL; scan = regnext(scan))
 273                                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
 274                                         longest = OPERAND(scan);
 275                                         len = strlen(OPERAND(scan));
 276                                 }
 277                         r->regmust = longest;
 278                         r->regmlen = len;
 279                 }
 280         }
 281
 282         return(r);
 283 }
 284
 285 /*
 286  - reg - regular expression, i.e. main body or parenthesized thing
 287  *
 288  * Caller must absorb opening parenthesis.
 289  *
 290  * Combining parenthesis handling with the base level of regular expression
 291  * is a trifle forced, but the need to tie the tails of the branches to what
 292  * follows makes it hard to avoid.
 293  */
 294 static char *
 295 reg(paren, flagp)
 296 int paren;                      /* Parenthesized? */
 297 int *flagp;
 298 {
 299         register char *ret;
 300         register char *br;
 301         register char *ender;
 302         register int parno;
 303         int flags;
 304
 305         *flagp = HASWIDTH;      /* Tentatively. */
 306
 307         /* Make an OPEN node, if parenthesized. */
 308         if (paren) {
 309                 if (regnpar >= NSUBEXP)
 310                         FAIL("too many ()");
 311                 parno = regnpar;
 312                 regnpar++;
 313                 ret = regnode(OPEN+parno);
 314         } else
 315                 ret = NULL;
 316
 317         /* Pick up the branches, linking them together. */
 318         br = regbranch(&flags);
 319         if (br == NULL)
 320                 return(NULL);
 321         if (ret != NULL)
 322                 regtail(ret, br);       /* OPEN -> first. */
 323         else
 324                 ret = br;
 325         if (!(flags&HASWIDTH))
 326                 *flagp &= ~HASWIDTH;
 327         *flagp |= flags&SPSTART;
 328         while (*regparse == '|' || *regparse == '\n') {
 329                 regparse++;
 330                 br = regbranch(&flags);
 331                 if (br == NULL)
 332                         return(NULL);
 333                 regtail(ret, br);       /* BRANCH -> BRANCH. */
 334                 if (!(flags&HASWIDTH))
 335                         *flagp &= ~HASWIDTH;
 336                 *flagp |= flags&SPSTART;
 337         }
 338
 339         /* Make a closing node, and hook it on the end. */
 340         ender = regnode((paren) ? CLOSE+parno : END);
 341         regtail(ret, ender);
 342
 343         /* Hook the tails of the branches to the closing node. */
 344         for (br = ret; br != NULL; br = regnext(br))
 345                 regoptail(br, ender);
 346
 347         /* Check for proper termination. */
 348         if (paren && *regparse++ != ')') {
 349                 FAIL("unmatched ()");
 350         } else if (!paren && *regparse != '\0') {
 351                 if (*regparse == ')') {
 352                         FAIL("unmatched ()");
 353                 } else
 354                         FAIL("junk on end");    /* "Can't happen". */
 355                 /* NOTREACHED */
 356         }
 357
 358         return(ret);
 359 }
 360
 361 /*
 362  - regbranch - one alternative of an | operator
 363  *
 364  * Implements the concatenation operator.
 365  */
 366 static char *
 367 regbranch(flagp)
 368 int *flagp;
 369 {
 370         register char *ret;
 371         register char *chain;
 372         register char *latest;
 373         int flags;
 374
 375         *flagp = WORST;         /* Tentatively. */
 376
 377         ret = regnode(BRANCH);
 378         chain = NULL;
 379         while (*regparse != '\0' && *regparse != ')' &&
 380                *regparse != '\n' && *regparse != '|') {
 381                 latest = regpiece(&flags);
 382                 if (latest == NULL)
 383                         return(NULL);
 384                 *flagp |= flags&HASWIDTH;
 385                 if (chain == NULL)      /* First piece. */
 386                         *flagp |= flags&SPSTART;
 387                 else
 388                         regtail(chain, latest);
 389                 chain = latest;
 390         }
 391         if (chain == NULL)      /* Loop ran zero times. */
 392                 (void) regnode(NOTHING);
 393
 394         return(ret);
 395 }
 396
 397 /*
 398  - regpiece - something followed by possible [*+?]
 399  *
 400  * Note that the branching code sequences used for ? and the general cases
 401  * of * and + are somewhat optimized:  they use the same NOTHING node as
 402  * both the endmarker for their branch list and the body of the last branch.
 403  * It might seem that this node could be dispensed with entirely, but the
 404  * endmarker role is not redundant.
 405  */
 406 static char *
 407 regpiece(flagp)
 408 int *flagp;
 409 {
 410         register char *ret;
 411         register char op;
 412         register char *next;
 413         int flags;
 414
 415         ret = regatom(&flags);
 416         if (ret == NULL)
 417                 return(NULL);
 418
 419         op = *regparse;
 420         if (!ISMULT(op)) {
 421                 *flagp = flags;
 422                 return(ret);
 423         }
 424
 425         if (!(flags&HASWIDTH) && op != '?')
 426                 FAIL("*+ operand could be empty");
 427         *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
 428
 429         if (op == '*' && (flags&SIMPLE))
 430                 reginsert(STAR, ret);
 431         else if (op == '*') {
 432                 /* Emit x* as (x&|), where & means "self". */
 433                 reginsert(BRANCH, ret);                 /* Either x */
 434                 regoptail(ret, regnode(BACK));          /* and loop */
 435                 regoptail(ret, ret);                    /* back */
 436                 regtail(ret, regnode(BRANCH));          /* or */
 437                 regtail(ret, regnode(NOTHING));         /* null. */
 438         } else if (op == '+' && (flags&SIMPLE))
 439                 reginsert(PLUS, ret);
 440         else if (op == '+') {
 441                 /* Emit x+ as x(&|), where & means "self". */
 442                 next = regnode(BRANCH);                 /* Either */
 443                 regtail(ret, next);
 444                 regtail(regnode(BACK), ret);            /* loop back */
 445                 regtail(next, regnode(BRANCH));         /* or */
 446                 regtail(ret, regnode(NOTHING));         /* null. */
 447         } else if (op == '?') {
 448                 /* Emit x? as (x|) */
 449                 reginsert(BRANCH, ret);                 /* Either x */
 450                 regtail(ret, regnode(BRANCH));          /* or */
 451                 next = regnode(NOTHING);                /* null. */
 452                 regtail(ret, next);
 453                 regoptail(ret, next);
 454         }
 455         regparse++;
 456         if (ISMULT(*regparse))
 457                 FAIL("nested *?+");
 458
 459         return(ret);
 460 }
 461
 462 /*
 463  - regatom - the lowest level
 464  *
 465  * Optimization:  gobbles an entire sequence of ordinary characters so that
 466  * it can turn them into a single node, which is smaller to store and
 467  * faster to run.  Backslashed characters are exceptions, each becoming a
 468  * separate node; the code is simpler that way and it's not worth fixing.
 469  */
 470 static char *
 471 regatom(flagp)
 472 int *flagp;
 473 {
 474         register char *ret;
 475         int flags;
 476
 477         *flagp = WORST;         /* Tentatively. */
 478
 479         switch (*regparse++) {
 480         /* FIXME: these chars only have meaning at beg/end of pat? */
 481         case '^':
 482                 ret = regnode(BOL);
 483                 break;
 484         case '$':
 485                 ret = regnode(EOL);
 486                 break;
 487         case '.':
 488                 ret = regnode(ANY);
 489                 *flagp |= HASWIDTH|SIMPLE;
 490                 break;
 491         case '[': {
 492                         register int class;
 493                         register int classend;
 494                         int i;
 495
 496                         if (*regparse == '^') { /* Complement of range. */
 497                                 ret = regnode(ANYBUT);
 498                                 regparse++;
 499                         } else
 500                                 ret = regnode(ANYOF);
 501                         if (*regparse == ']' || *regparse == '-')
 502                                 regc(*regparse++);
 503                         while (*regparse != '\0' && *regparse != ']') {
 504                                 if (*regparse == '-') {
 505                                         regparse++;
 506                                         if (*regparse == ']' || *regparse == '\0')
 507                                                 regc('-');
 508                                         else {
 509                                                 class = UCHARAT(regparse-2);
 510                                                 classend = UCHARAT(regparse);
 511                                                 if (__collate_load_error) {
 512                                                         if (class > classend)
 513                                                                 FAIL("invalid [] range");
 514                                                         for (class++; class <= classend; class++)
 515                                                                 regc(class);
 516                                                 } else {
 517                                                         if (__collate_range_cmp(class, classend) > 0)
 518                                                                 FAIL("invalid [] range");
 519                                                         for (i = 0; i <= UCHAR_MAX; i++)
 520                                                                 if (   i != class
 521                                                                     && __collate_range_cmp(class, i) <= 0
 522                                                                     && __collate_range_cmp(i, classend) <= 0
 523                                                                    )
 524                                                                         regc(i);
 525                                                 }
 526                                                 regparse++;
 527                                         }
 528                                 } else
 529                                         regc(*regparse++);
 530                         }
 531                         regc('\0');
 532                         if (*regparse != ']')
 533                                 FAIL("unmatched []");
 534                         regparse++;
 535                         *flagp |= HASWIDTH|SIMPLE;
 536                 }
 537                 break;
 538         case '(':
 539                 ret = reg(1, &flags);
 540                 if (ret == NULL)
 541                         return(NULL);
 542                 *flagp |= flags&(HASWIDTH|SPSTART);
 543                 break;
 544         case '\0':
 545         case '|':
 546         case '\n':
 547         case ')':
 548                 FAIL("internal urp");   /* Supposed to be caught earlier. */
 549                 break;
 550         case '?':
 551         case '+':
 552         case '*':
 553                 FAIL("?+* follows nothing");
 554                 break;
 555         case '\\':
 556                 switch (*regparse++) {
 557                 case '\0':
 558                         FAIL("trailing \\");
 559                         break;
 560                 case '<':
 561                         ret = regnode(WORDA);
 562                         break;
 563                 case '>':
 564                         ret = regnode(WORDZ);
 565                         break;
 566                 /* FIXME: Someday handle \1, \2, ... */
 567                 default:
 568                         /* Handle general quoted chars in exact-match routine */
 569                         goto de_fault;
 570                 }
 571                 break;
 572         de_fault:
 573         default:
 574                 /*
 575                  * Encode a string of characters to be matched exactly.
 576                  *
 577                  * This is a bit tricky due to quoted chars and due to
 578                  * '*', '+', and '?' taking the SINGLE char previous
 579                  * as their operand.
 580                  *
 581                  * On entry, the char at regparse[-1] is going to go
 582                  * into the string, no matter what it is.  (It could be
 583                  * following a \ if we are entered from the '\' case.)
 584                  *
 585                  * Basic idea is to pick up a good char in  ch  and
 586                  * examine the next char.  If it's *+? then we twiddle.
 587                  * If it's \ then we frozzle.  If it's other magic char
 588                  * we push  ch  and terminate the string.  If none of the
 589                  * above, we push  ch  on the string and go around again.
 590                  *
 591                  *  regprev  is used to remember where "the current char"
 592                  * starts in the string, if due to a *+? we need to back
 593                  * up and put the current char in a separate, 1-char, string.
 594                  * When  regprev  is NULL,  ch  is the only char in the
 595                  * string; this is used in *+? handling, and in setting
 596                  * flags |= SIMPLE at the end.
 597                  */
 598                 {
 599                         char *regprev;
 600                         register char ch;
 601
 602                         regparse--;                     /* Look at cur char */
 603                         ret = regnode(EXACTLY);
 604                         for ( regprev = 0 ; ; ) {
 605                                 ch = *regparse++;       /* Get current char */
 606                                 switch (*regparse) {    /* look at next one */
 607
 608                                 default:
 609                                         regc(ch);       /* Add cur to string */
 610                                         break;
 611
 612                                 case '.': case '[': case '(':
 613                                 case ')': case '|': case '\n':
 614                                 case '$': case '^':
 615                                 case '\0':
 616                                 /* FIXME, $ and ^ should not always be magic */
 617                                 magic:
 618                                         regc(ch);       /* dump cur char */
 619                                         goto done;      /* and we are done */
 620
 621                                 case '?': case '+': case '*':
 622                                         if (!regprev)   /* If just ch in str, */
 623                                                 goto magic;     /* use it */
 624                                         /* End mult-char string one early */
 625                                         regparse = regprev; /* Back up parse */
 626                                         goto done;
 627
 628                                 case '\\':
 629                                         regc(ch);       /* Cur char OK */
 630                                         switch (regparse[1]){ /* Look after \ */
 631                                         case '\0':
 632                                         case '<':
 633                                         case '>':
 634                                         /* FIXME: Someday handle \1, \2, ... */
 635                                                 goto done; /* Not quoted */
 636                                         default:
 637                                                 /* Backup point is \, scan                                                       * point is after it. */
 638                                                 regprev = regparse;
 639                                                 regparse++;
 640                                                 continue;       /* NOT break; */
 641                                         }
 642                                 }
 643                                 regprev = regparse;     /* Set backup point */
 644                         }
 645                 done:
 646                         regc('\0');
 647                         *flagp |= HASWIDTH;
 648                         if (!regprev)           /* One char? */
 649                                 *flagp |= SIMPLE;
 650                 }
 651                 break;
 652         }
 653
 654         return(ret);
 655 }
 656
 657 /*
 658  - regnode - emit a node
 659  */
 660 static char *                   /* Location. */
 661 regnode(op)
 662 char op;
 663 {
 664         register char *ret;
 665         register char *ptr;
 666
 667         ret = regcode;
 668         if (ret == &regdummy) {
 669                 regsize += 3;
 670                 return(ret);
 671         }
 672
 673         ptr = ret;
 674         *ptr++ = op;
 675         *ptr++ = '\0';          /* Null "next" pointer. */
 676         *ptr++ = '\0';
 677         regcode = ptr;
 678
 679         return(ret);
 680 }
 681
 682 /*
 683  - regc - emit (if appropriate) a byte of code
 684  */
 685 static void
 686 regc(b)
 687 char b;
 688 {
 689         if (regcode != &regdummy)
 690                 *regcode++ = b;
 691         else
 692                 regsize++;
 693 }
 694
 695 /*
 696  - reginsert - insert an operator in front of already-emitted operand
 697  *
 698  * Means relocating the operand.
 699  */
 700 static void
 701 reginsert(op, opnd)
 702 char op;
 703 char *opnd;
 704 {
 705         register char *src;
 706         register char *dst;
 707         register char *place;
 708
 709         if (regcode == &regdummy) {
 710                 regsize += 3;
 711                 return;
 712         }
 713
 714         src = regcode;
 715         regcode += 3;
 716         dst = regcode;
 717         while (src > opnd)
 718                 *--dst = *--src;
 719
 720         place = opnd;           /* Op node, where operand used to be. */
 721         *place++ = op;
 722         *place++ = '\0';
 723         *place++ = '\0';
 724 }
 725
 726 /*
 727  - regtail - set the next-pointer at the end of a node chain
 728  */
 729 static void
 730 regtail(p, val)
 731 char *p;
 732 char *val;
 733 {
 734         register char *scan;
 735         register char *temp;
 736         register int offset;
 737
 738         if (p == &regdummy)
 739                 return;
 740
 741         /* Find last node. */
 742         scan = p;
 743         for (;;) {
 744                 temp = regnext(scan);
 745                 if (temp == NULL)
 746                         break;
 747                 scan = temp;
 748         }
 749
 750         if (OP(scan) == BACK)
 751                 offset = scan - val;
 752         else
 753                 offset = val - scan;
 754         *(scan+1) = (offset>>8)&0377;
 755         *(scan+2) = offset&0377;
 756 }
 757
 758 /*
 759  - regoptail - regtail on operand of first argument; nop if operandless
 760  */
 761 static void
 762 regoptail(p, val)
 763 char *p;
 764 char *val;
 765 {
 766         /* "Operandless" and "op != BRANCH" are synonymous in practice. */
 767         if (p == NULL || p == &regdummy || OP(p) != BRANCH)
 768                 return;
 769         regtail(OPERAND(p), val);
 770 }
 771
 772 /*
 773  * regexec and friends
 774  */
 775
 776 /*
 777  * Global work variables for regexec().
 778  */
 779 static char *reginput;          /* String-input pointer. */
 780 static char *regbol;            /* Beginning of input, for ^ check. */
 781 static char **regstartp;        /* Pointer to startp array. */
 782 static char **regendp;          /* Ditto for endp. */
 783
 784 /*
 785  * Forwards.
 786  */
 787 STATIC int regtry();
 788 STATIC int regmatch();
 789 STATIC int regrepeat();
 790
 791 #ifdef DEBUG
 792 int regnarrate = 0;
 793 void regdump();
 794 STATIC char *regprop();
 795 #endif
 796
 797 /*
 798  - regexec - match a regexp against a string
 799  */
 800 int
 801 regexec(prog, string)
 802 register const regexp *prog;
 803 register const char *string;
 804 {
 805         register char *s;
 806         extern char *strchr();
 807
 808         /* Be paranoid... */
 809         if (prog == NULL || string == NULL) {
 810                 regerror("NULL parameter");
 811                 return(0);
 812         }
 813
 814         /* Check validity of program. */
 815         if (UCHARAT(prog->program) != MAGIC) {
 816                 regerror("corrupted program");
 817                 return(0);
 818         }
 819
 820         /* If there is a "must appear" string, look for it. */
 821         if (prog->regmust != NULL) {
 822                 s = (char *)string;
 823                 while ((s = strchr(s, prog->regmust[0])) != NULL) {
 824                         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
 825                                 break;  /* Found it. */
 826                         s++;
 827                 }
 828                 if (s == NULL)  /* Not present. */
 829                         return(0);
 830         }
 831
 832         /* Mark beginning of line for ^ . */
 833         regbol = (char *)string;
 834
 835         /* Simplest case:  anchored match need be tried only once. */
 836         if (prog->reganch)
 837                 return(regtry(prog, string));
 838
 839         /* Messy cases:  unanchored match. */
 840         s = (char *)string;
 841         if (prog->regstart != '\0')
 842                 /* We know what char it must start with. */
 843                 while ((s = strchr(s, prog->regstart)) != NULL) {
 844                         if (regtry(prog, s))
 845                                 return(1);
 846                         s++;
 847                 }
 848         else
 849                 /* We don't -- general case. */
 850                 do {
 851                         if (regtry(prog, s))
 852                                 return(1);
 853                 } while (*s++ != '\0');
 854
 855         /* Failure. */
 856         return(0);
 857 }
 858
 859 /*
 860  - regtry - try match at specific point
 861  */
 862 static int                      /* 0 failure, 1 success */
 863 regtry(prog, string)
 864 regexp *prog;
 865 char *string;
 866 {
 867         register int i;
 868         register char **sp;
 869         register char **ep;
 870
 871         reginput = string;
 872         regstartp = prog->startp;
 873         regendp = prog->endp;
 874
 875         sp = prog->startp;
 876         ep = prog->endp;
 877         for (i = NSUBEXP; i > 0; i--) {
 878                 *sp++ = NULL;
 879                 *ep++ = NULL;
 880         }
 881         if (regmatch(prog->program + 1)) {
 882                 prog->startp[0] = string;
 883                 prog->endp[0] = reginput;
 884                 return(1);
 885         } else
 886                 return(0);
 887 }
 888
 889 /*
 890  - regmatch - main matching routine
 891  *
 892  * Conceptually the strategy is simple:  check to see whether the current
 893  * node matches, call self recursively to see whether the rest matches,
 894  * and then act accordingly.  In practice we make some effort to avoid
 895  * recursion, in particular by going through "ordinary" nodes (that don't
 896  * need to know whether the rest of the match failed) by a loop instead of
 897  * by recursion.
 898  */
 899 static int                      /* 0 failure, 1 success */
 900 regmatch(prog)
 901 char *prog;
 902 {
 903         register char *scan;    /* Current node. */
 904         char *next;             /* Next node. */
 905
 906         scan = prog;
 907 #ifdef DEBUG
 908         if (scan != NULL && regnarrate)
 909                 fprintf(stderr, "%s(\n", regprop(scan));
 910 #endif
 911         while (scan != NULL) {
 912 #ifdef DEBUG
 913                 if (regnarrate)
 914                         fprintf(stderr, "%s...\n", regprop(scan));
 915 #endif
 916                 next = regnext(scan);
 917
 918                 switch (OP(scan)) {
 919                 case BOL:
 920                         if (reginput != regbol)
 921                                 return(0);
 922                         break;
 923                 case EOL:
 924                         if (*reginput != '\0')
 925                                 return(0);
 926                         break;
 927                 case WORDA:
 928                         /* Must be looking at a letter, digit, or _ */
 929                         if ((!isalnum((unsigned char)*reginput)) && *reginput != '_')
 930                                 return(0);
 931                         /* Prev must be BOL or nonword */
 932                         if (reginput > regbol &&
 933                             (isalnum((unsigned char)reginput[-1]) || reginput[-1] == '_'))
 934                                 return(0);
 935                         break;
 936                 case WORDZ:
 937                         /* Must be looking at non letter, digit, or _ */
 938                         if (isalnum((unsigned char)*reginput) || *reginput == '_')
 939                                 return(0);
 940                         /* We don't care what the previous char was */
 941                         break;
 942                 case ANY:
 943                         if (*reginput == '\0')
 944                                 return(0);
 945                         reginput++;
 946                         break;
 947                 case EXACTLY: {
 948                                 register int len;
 949                                 register char *opnd;
 950
 951                                 opnd = OPERAND(scan);
 952                                 /* Inline the first character, for speed. */
 953                                 if (*opnd != *reginput)
 954                                         return(0);
 955                                 len = strlen(opnd);
 956                                 if (len > 1 && strncmp(opnd, reginput, len) != 0)
 957                                         return(0);
 958                                 reginput += len;
 959                         }
 960                         break;
 961                 case ANYOF:
 962                         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
 963                                 return(0);
 964                         reginput++;
 965                         break;
 966                 case ANYBUT:
 967                         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
 968                                 return(0);
 969                         reginput++;
 970                         break;
 971                 case NOTHING:
 972                         break;
 973                 case BACK:
 974                         break;
 975                 case OPEN+1:
 976                 case OPEN+2:
 977                 case OPEN+3:
 978                 case OPEN+4:
 979                 case OPEN+5:
 980                 case OPEN+6:
 981                 case OPEN+7:
 982                 case OPEN+8:
 983                 case OPEN+9: {
 984                                 register int no;
 985                                 register char *save;
 986
 987                                 no = OP(scan) - OPEN;
 988                                 save = reginput;
 989
 990                                 if (regmatch(next)) {
 991                                         /*
 992                                          * Don't set startp if some later
 993                                          * invocation of the same parentheses
 994                                          * already has.
 995                                          */
 996                                         if (regstartp[no] == NULL)
 997                                                 regstartp[no] = save;
 998                                         return(1);
 999                                 } else
1000                                         return(0);
1001                         }
1002                         break;
1003                 case CLOSE+1:
1004                 case CLOSE+2:
1005                 case CLOSE+3:
1006                 case CLOSE+4:
1007                 case CLOSE+5:
1008                 case CLOSE+6:
1009                 case CLOSE+7:
1010                 case CLOSE+8:
1011                 case CLOSE+9: {
1012                                 register int no;
1013                                 register char *save;
1014
1015                                 no = OP(scan) - CLOSE;
1016                                 save = reginput;
1017
1018                                 if (regmatch(next)) {
1019                                         /*
1020                                          * Don't set endp if some later
1021                                          * invocation of the same parentheses
1022                                          * already has.
1023                                          */
1024                                         if (regendp[no] == NULL)
1025                                                 regendp[no] = save;
1026                                         return(1);
1027                                 } else
1028                                         return(0);
1029                         }
1030                         break;
1031                 case BRANCH: {
1032                                 register char *save;
1033
1034                                 if (OP(next) != BRANCH)         /* No choice. */
1035                                         next = OPERAND(scan);   /* Avoid recursion. */
1036                                 else {
1037                                         do {
1038                                                 save = reginput;
1039                                                 if (regmatch(OPERAND(scan)))
1040                                                         return(1);
1041                                                 reginput = save;
1042                                                 scan = regnext(scan);
1043                                         } while (scan != NULL && OP(scan) == BRANCH);
1044                                         return(0);
1045                                         /* NOTREACHED */
1046                                 }
1047                         }
1048                         break;
1049                 case STAR:
1050                 case PLUS: {
1051                                 register char nextch;
1052                                 register int no;
1053                                 register char *save;
1054                                 register int min;
1055
1056                                 /*
1057                                  * Lookahead to avoid useless match attempts
1058                                  * when we know what character comes next.
1059                                  */
1060                                 nextch = '\0';
1061                                 if (OP(next) == EXACTLY)
1062                                         nextch = *OPERAND(next);
1063                                 min = (OP(scan) == STAR) ? 0 : 1;
1064                                 save = reginput;
1065                                 no = regrepeat(OPERAND(scan));
1066                                 while (no >= min) {
1067                                         /* If it could work, try it. */
1068                                         if (nextch == '\0' || *reginput == nextch)
1069                                                 if (regmatch(next))
1070                                                         return(1);
1071                                         /* Couldn't or didn't -- back up. */
1072                                         no--;
1073                                         reginput = save + no;
1074                                 }
1075                                 return(0);
1076                         }
1077                         break;
1078                 case END:
1079                         return(1);      /* Success! */
1080                         break;
1081                 default:
1082                         regerror("memory corruption");
1083                         return(0);
1084                         break;
1085                 }
1086
1087                 scan = next;
1088         }
1089
1090         /*
1091          * We get here only if there's trouble -- normally "case END" is
1092          * the terminating point.
1093          */
1094         regerror("corrupted pointers");
1095         return(0);
1096 }
1097
1098 /*
1099  - regrepeat - repeatedly match something simple, report how many
1100  */
1101 static int
1102 regrepeat(p)
1103 char *p;
1104 {
1105         register int count = 0;
1106         register char *scan;
1107         register char *opnd;
1108
1109         scan = reginput;
1110         opnd = OPERAND(p);
1111         switch (OP(p)) {
1112         case ANY:
1113                 count = strlen(scan);
1114                 scan += count;
1115                 break;
1116         case EXACTLY:
1117                 while (*opnd == *scan) {
1118                         count++;
1119                         scan++;
1120                 }
1121                 break;
1122         case ANYOF:
1123                 while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
1124                         count++;
1125                         scan++;
1126                 }
1127                 break;
1128         case ANYBUT:
1129                 while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
1130                         count++;
1131                         scan++;
1132                 }
1133                 break;
1134         default:                /* Oh dear.  Called inappropriately. */
1135                 regerror("internal foulup");
1136                 count = 0;      /* Best compromise. */
1137                 break;
1138         }
1139         reginput = scan;
1140
1141         return(count);
1142 }
1143
1144 /*
1145  - regnext - dig the "next" pointer out of a node
1146  */
1147 static char *
1148 regnext(p)
1149 register char *p;
1150 {
1151         register int offset;
1152
1153         if (p == &regdummy)
1154                 return(NULL);
1155
1156         offset = NEXT(p);
1157         if (offset == 0)
1158                 return(NULL);
1159
1160         if (OP(p) == BACK)
1161                 return(p-offset);
1162         else
1163                 return(p+offset);
1164 }
1165
1166 #ifdef DEBUG
1167
1168 STATIC char *regprop();
1169
1170 /*
1171  - regdump - dump a regexp onto stdout in vaguely comprehensible form
1172  */
1173 void
1174 regdump(r)
1175 regexp *r;
1176 {
1177         register char *s;
1178         register char op = EXACTLY;     /* Arbitrary non-END op. */
1179         register char *next;
1180         extern char *strchr();
1181
1182
1183         s = r->program + 1;
1184         while (op != END) {     /* While that wasn't END last time... */
1185                 op = OP(s);
1186                 printf("%2d%s", s-r->program, regprop(s));      /* Where, what. */
1187                 next = regnext(s);
1188                 if (next == NULL)               /* Next ptr. */
1189                         printf("(0)");
1190                 else
1191                         printf("(%d)", (s-r->program)+(next-s));
1192                 s += 3;
1193                 if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
1194                         /* Literal string, where present. */
1195                         while (*s != '\0') {
1196                                 putchar(*s);
1197                                 s++;
1198                         }
1199                         s++;
1200                 }
1201                 putchar('\n');
1202         }
1203
1204         /* Header fields of interest. */
1205         if (r->regstart != '\0')
1206                 printf("start `%c' ", r->regstart);
1207         if (r->reganch)
1208                 printf("anchored ");
1209         if (r->regmust != NULL)
1210                 printf("must have \"%s\"", r->regmust);
1211         printf("\n");
1212 }
1213
1214 /*
1215  - regprop - printable representation of opcode
1216  */
1217 static char *
1218 regprop(op)
1219 char *op;
1220 {
1221         register char *p;
1222         static char buf[50];
1223
1224         (void) strcpy(buf, ":");
1225
1226         switch (OP(op)) {
1227         case BOL:
1228                 p = "BOL";
1229                 break;
1230         case EOL:
1231                 p = "EOL";
1232                 break;
1233         case ANY:
1234                 p = "ANY";
1235                 break;
1236         case ANYOF:
1237                 p = "ANYOF";
1238                 break;
1239         case ANYBUT:
1240                 p = "ANYBUT";
1241                 break;
1242         case BRANCH:
1243                 p = "BRANCH";
1244                 break;
1245         case EXACTLY:
1246                 p = "EXACTLY";
1247                 break;
1248         case NOTHING:
1249                 p = "NOTHING";
1250                 break;
1251         case BACK:
1252                 p = "BACK";
1253                 break;
1254         case END:
1255                 p = "END";
1256                 break;
1257         case OPEN+1:
1258         case OPEN+2:
1259         case OPEN+3:
1260         case OPEN+4:
1261         case OPEN+5:
1262         case OPEN+6:
1263         case OPEN+7:
1264         case OPEN+8:
1265         case OPEN+9:
1266                 sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
1267                 p = NULL;
1268                 break;
1269         case CLOSE+1:
1270         case CLOSE+2:
1271         case CLOSE+3:
1272         case CLOSE+4:
1273         case CLOSE+5:
1274         case CLOSE+6:
1275         case CLOSE+7:
1276         case CLOSE+8:
1277         case CLOSE+9:
1278                 sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
1279                 p = NULL;
1280                 break;
1281         case STAR:
1282                 p = "STAR";
1283                 break;
1284         case PLUS:
1285                 p = "PLUS";
1286                 break;
1287         case WORDA:
1288                 p = "WORDA";
1289                 break;
1290         case WORDZ:
1291                 p = "WORDZ";
1292                 break;
1293         default:
1294                 regerror("corrupted opcode");
1295                 break;
1296         }
1297         if (p != NULL)
1298                 (void) strcat(buf, p);
1299         return(buf);
1300 }
1301 #endif
1302
1303 /*
1304  * The following is provided for those people who do not have strcspn() in
1305  * their C libraries.  They should get off their butts and do something
1306  * about it; at least one public-domain implementation of those (highly
1307  * useful) string routines has been published on Usenet.
1308  */
1309 #ifdef STRCSPN
1310 /*
1311  * strcspn - find length of initial segment of s1 consisting entirely
1312  * of characters not from s2
1313  */
1314
1315 static int
1316 strcspn(s1, s2)
1317 char *s1;
1318 char *s2;
1319 {
1320         register char *scan1;
1321         register char *scan2;
1322         register int count;
1323
1324         count = 0;
1325         for (scan1 = s1; *scan1 != '\0'; scan1++) {
1326                 for (scan2 = s2; *scan2 != '\0';)       /* ++ moved down. */
1327                         if (*scan1 == *scan2++)
1328                                 return(count);
1329                 count++;
1330         }
1331         return(count);
1332 }
1333 #endif