lib/libcompat/regexp/regexp.c

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