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