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