tac_regexp.c

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