git.sur5r.net Git - openldap/blob - contrib/tweb/regular.c

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