git.sur5r.net Git - openldap/blob - servers/slapd/regex.c

   1 #include "portable.h"
   2
   3 #if defined( MACOS ) || defined( DOS ) || defined( _WIN32 ) || defined( NEED_BSDREGEX )
   4 #include "regex.h"
   5
   6 /*
   7  * regex - Regular expression pattern matching  and replacement
   8  *
   9  * By:  Ozan S. Yigit (oz)
  10  *      Dept. of Computer Science
  11  *      York University
  12  *
  13  * These routines are the PUBLIC DOMAIN equivalents of regex
  14  * routines as found in 4.nBSD UN*X, with minor extensions.
  15  *
  16  * These routines are derived from various implementations found
  17  * in software tools books, and Conroy's grep. They are NOT derived
  18  * from licensed/restricted software.
  19  * For more interesting/academic/complicated implementations,
  20  * see Henry Spencer's regexp routines, or GNU Emacs pattern
  21  * matching module.
  22  *
  23  * Vendor Modification history:
  24  *
  25  * Revision 1.2  1996/04/25  16:24:11  mcs
  26  * make re_exec() match "" with ".*" and similar patterns
  27  * hopefully this change doesn't break anything else!
  28  *
  29  * Revision 1.1  1995/02/03  15:56:52  tim
  30  * Initial revision
  31  *
  32  * Revision 1.11  1994/12/14  21:33:45  mcs
  33  * use new NEED_BSDREGEX
  34  * fix pmatch() prototype
  35  *
  36  * Revision 1.10  1994/12/12  18:16:39  mcs
  37  * use on NetBSD
  38  *
  39  * Revision 1.9  1994/11/15  19:16:35  mcs
  40  * add (CHAR) cast to make VisualC++ happy
  41  *
  42  * Revision 1.8  1994/11/08  21:14:32  mcs
  43  * WIN32 changes
  44  *
  45  * Revision 1.7  1994/07/23  19:51:24  mcs
  46  * use ANSI-style inline function parameters
  47  *
  48  * Revision 1.6  1993/10/18  01:52:32  tim
  49  * include for VMS
  50  *
  51  * Revision 1.5  1993/09/28  21:37:54  mcs
  52  * HP/UX needs the regex we include (not in its libc)
  53  *
  54  * Revision 1.4  1993/08/27  15:59:52  mcs
  55  * use CHAR for deftab
  56  *
  57  * Revision 1.3  1993/08/27  15:49:47  mcs
  58  * added missing 0 to octal constants
  59  * use unsigned char for CHAR under DOS
  60  *
  61  * Revision 1.2  1993/08/27  14:57:48  mcs
  62  * add proto. for pmatch
  63  *
  64  * Revision 1.1  1993/08/18  21:20:02  mcs
  65  * Initial revision
  66  *
  67  * Revision 1.4  1991/10/17  03:56:42  oz
  68  * miscellaneous changes, small cleanups etc.
  69  *
  70  * Revision 1.3  1989/04/01  14:18:09  oz
  71  * Change all references to a dfa: this is actually an nfa.
  72  *
  73  * Revision 1.2  88/08/28  15:36:04  oz
  74  * Use a complement bitmap to represent NCL.
  75  * This removes the need to have seperate
  76  * code in the pmatch case block - it is
  77  * just CCL code now.
  78  *
  79  * Use the actual CCL code in the CLO
  80  * section of pmatch. No need for a recursive
  81  * pmatch call.
  82  *
  83  * Use a bitmap table to set char bits in an
  84  * 8-bit chunk.
  85  *
  86  * Interfaces:
  87  *      re_comp:        compile a regular expression into a NFA.
  88  *
  89  *                      char *re_comp(s)
  90  *                      char *s;
  91  *
  92  *      re_exec:        execute the NFA to match a pattern.
  93  *
  94  *                      int re_exec(s)
  95  *                      char *s;
  96  *
  97  *      re_modw         change re_exec's understanding of what a "word"
  98  *                      looks like (for \< and \>) by adding into the
  99  *                      hidden word-syntax table.
 100  *
 101  *                      void re_modw(s)
 102  *                      char *s;
 103  *
 104  *      re_subs:        substitute the matched portions in a new string.
 105  *
 106  *                      int re_subs(src, dst)
 107  *                      char *src;
 108  *                      char *dst;
 109  *
 110  *      re_fail:        failure routine for re_exec.
 111  *
 112  *                      void re_fail(msg, op)
 113  *                      char *msg;
 114  *                      char op;
 115  *
 116  * Regular Expressions:
 117  *
 118  *      [1]     char    matches itself, unless it is a special
 119  *                      character (metachar): . \ [ ] * + ^ $
 120  *
 121  *      [2]     .       matches any character.
 122  *
 123  *      [3]     \       matches the character following it, except
 124  *                      when followed by a left or right round bracket,
 125  *                      a digit 1 to 9 or a left or right angle bracket.
 126  *                      (see [7], [8] and [9])
 127  *                      It is used as an escape character for all
 128  *                      other meta-characters, and itself. When used
 129  *                      in a set ([4]), it is treated as an ordinary
 130  *                      character.
 131  *
 132  *      [4]     [set]   matches one of the characters in the set.
 133  *                      If the first character in the set is "^",
 134  *                      it matches a character NOT in the set, i.e.
 135  *                      complements the set. A shorthand S-E is
 136  *                      used to specify a set of characters S upto
 137  *                      E, inclusive. The special characters "]" and
 138  *                      "-" have no special meaning if they appear
 139  *                      as the first chars in the set.
 140  *                      examples:        match:
 141  *
 142  *                              [a-z]    any lowercase alpha
 143  *
 144  *                              [^]-]    any char except ] and -
 145  *
 146  *                              [^A-Z]   any char except uppercase
 147  *                                       alpha
 148  *
 149  *                              [a-zA-Z] any alpha
 150  *
 151  *      [5]     *       any regular expression form [1] to [4], followed by
 152  *                      closure char (*) matches zero or more matches of
 153  *                      that form.
 154  *
 155  *      [6]     +       same as [5], except it matches one or more.
 156  *
 157  *      [7]             a regular expression in the form [1] to [10], enclosed
 158  *                      as \(form\) matches what form matches. The enclosure
 159  *                      creates a set of tags, used for [8] and for
 160  *                      pattern substution. The tagged forms are numbered
 161  *                      starting from 1.
 162  *
 163  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
 164  *                      previously tagged regular expression ([7]) matched.
 165  *
 166  *      [9]     \<      a regular expression starting with a \< construct
 167  *              \>      and/or ending with a \> construct, restricts the
 168  *                      pattern matching to the beginning of a word, and/or
 169  *                      the end of a word. A word is defined to be a character
 170  *                      string beginning and/or ending with the characters
 171  *                      A-Z a-z 0-9 and _. It must also be preceded and/or
 172  *                      followed by any character outside those mentioned.
 173  *
 174  *      [10]            a composite regular expression xy where x and y
 175  *                      are in the form [1] to [10] matches the longest
 176  *                      match of x followed by a match for y.
 177  *
 178  *      [11]    ^       a regular expression starting with a ^ character
 179  *              $       and/or ending with a $ character, restricts the
 180  *                      pattern matching to the beginning of the line,
 181  *                      or the end of line. [anchors] Elsewhere in the
 182  *                      pattern, ^ and $ are treated as ordinary characters.
 183  *
 184  *
 185  * Acknowledgements:
 186  *
 187  *      HCR's Hugh Redelmeier has been most helpful in various
 188  *      stages of development. He convinced me to include BOW
 189  *      and EOW constructs, originally invented by Rob Pike at
 190  *      the University of Toronto.
 191  *
 192  * References:
 193  *              Software tools                  Kernighan & Plauger
 194  *              Software tools in Pascal        Kernighan & Plauger
 195  *              Grep [rsx-11 C dist]            David Conroy
 196  *              ed - text editor                Un*x Programmer's Manual
 197  *              Advanced editing on Un*x        B. W. Kernighan
 198  *              RegExp routines                 Henry Spencer
 199  *
 200  * Notes:
 201  *
 202  *      This implementation uses a bit-set representation for character
 203  *      classes for speed and compactness. Each character is represented
 204  *      by one bit in a 128-bit block. Thus, CCL always takes a
 205  *      constant 16 bytes in the internal nfa, and re_exec does a single
 206  *      bit comparison to locate the character in the set.
 207  *
 208  * Examples:
 209  *
 210  *      pattern:        foo*.*
 211  *      compile:        CHR f CHR o CLO CHR o END CLO ANY END END
 212  *      matches:        fo foo fooo foobar fobar foxx ...
 213  *
 214  *      pattern:        fo[ob]a[rz]
 215  *      compile:        CHR f CHR o CCL bitset CHR a CCL bitset END
 216  *      matches:        fobar fooar fobaz fooaz
 217  *
 218  *      pattern:        foo\\+
 219  *      compile:        CHR f CHR o CHR o CHR \ CLO CHR \ END END
 220  *      matches:        foo\ foo\\ foo\\\  ...
 221  *
 222  *      pattern:        \(foo\)[1-3]\1  (same as foo[1-3]foo)
 223  *      compile:        BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
 224  *      matches:        foo1foo foo2foo foo3foo
 225  *
 226  *      pattern:        \(fo.*\)-\1
 227  *      compile:        BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
 228  *      matches:        foo-foo fo-fo fob-fob foobar-foobar ...
 229  */
 230
 231 #define MAXNFA  1024
 232 #define MAXTAG  10
 233
 234 #define OKP     1
 235 #define NOP     0
 236
 237 #define CHR     1
 238 #define ANY     2
 239 #define CCL     3
 240 #define BOL     4
 241 #define EOL     5
 242 #define BOT     6
 243 #define EOT     7
 244 #define BOW     8
 245 #define EOW     9
 246 #define REF     10
 247 #define CLO     11
 248
 249 #define END     0
 250
 251 /*
 252  * The following defines are not meant to be changeable.
 253  * They are for readability only.
 254  */
 255 #define MAXCHR  128
 256 #define CHRBIT  8
 257 #define BITBLK  MAXCHR/CHRBIT
 258 #define BLKIND  0170
 259 #define BITIND  07
 260
 261 #define ASCIIB  0177
 262
 263 #if defined( DOS ) || defined( _WIN32 )
 264 typedef unsigned char CHAR;
 265 #else /* DOS */
 266 typedef /*unsigned*/ char CHAR;
 267 #endif /* DOS */
 268
 269 static int  tagstk[MAXTAG];             /* subpat tag stack..*/
 270 static CHAR nfa[MAXNFA];                /* automaton..       */
 271 static int  sta = NOP;                  /* status of lastpat */
 272
 273 static CHAR bittab[BITBLK];             /* bit table for CCL */
 274                                         /* pre-set bits...   */
 275 static CHAR bitarr[] = {1,2,4,8,16,32,64,128};
 276
 277 static void
 278 chset(CHAR c)
 279 {
 280         bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
 281 }
 282
 283 #define badpat(x)       (*nfa = END, x)
 284 #define store(x)        *mp++ = x
 285
 286 char *
 287 re_comp( char *pat )
 288 {
 289         register char *p;               /* pattern pointer   */
 290         register CHAR *mp=nfa;          /* nfa pointer       */
 291         register CHAR *lp;              /* saved pointer..   */
 292         register CHAR *sp=nfa;          /* another one..     */
 293
 294         register int tagi = 0;          /* tag stack index   */
 295         register int tagc = 1;          /* actual tag count  */
 296
 297         register int n;
 298         register CHAR mask;             /* xor mask -CCL/NCL */
 299         int c1, c2;
 300
 301         if (!pat || !*pat)
 302                 if (sta)
 303                         return 0;
 304                 else
 305                         return badpat("No previous regular expression");
 306         sta = NOP;
 307
 308         for (p = pat; *p; p++) {
 309                 lp = mp;
 310                 switch(*p) {
 311
 312                 case '.':               /* match any char..  */
 313                         store(ANY);
 314                         break;
 315
 316                 case '^':               /* match beginning.. */
 317                         if (p == pat)
 318                                 store(BOL);
 319                         else {
 320                                 store(CHR);
 321                                 store(*p);
 322                         }
 323                         break;
 324
 325                 case '$':               /* match endofline.. */
 326                         if (!*(p+1))
 327                                 store(EOL);
 328                         else {
 329                                 store(CHR);
 330                                 store(*p);
 331                         }
 332                         break;
 333
 334                 case '[':               /* match char class..*/
 335                         store(CCL);
 336
 337                         if (*++p == '^') {
 338                                 mask = 0377;
 339                                 p++;
 340                         }
 341                         else
 342                                 mask = 0;
 343
 344                         if (*p == '-')          /* real dash */
 345                                 chset(*p++);
 346                         if (*p == ']')          /* real brac */
 347                                 chset(*p++);
 348                         while (*p && *p != ']') {
 349                                 if (*p == '-' && *(p+1) && *(p+1) != ']') {
 350                                         p++;
 351                                         c1 = *(p-2) + 1;
 352                                         c2 = *p++;
 353                                         while (c1 <= c2)
 354                                                 chset((CHAR)c1++);
 355                                 }
 356 #ifdef EXTEND
 357                                 else if (*p == '\\' && *(p+1)) {
 358                                         p++;
 359                                         chset(*p++);
 360                                 }
 361 #endif
 362                                 else
 363                                         chset(*p++);
 364                         }
 365                         if (!*p)
 366                                 return badpat("Missing ]");
 367
 368                         for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
 369                                 store(mask ^ bittab[n]);
 370
 371                         break;
 372
 373                 case '*':               /* match 0 or more.. */
 374                 case '+':               /* match 1 or more.. */
 375                         if (p == pat)
 376                                 return badpat("Empty closure");
 377                         lp = sp;                /* previous opcode */
 378                         if (*lp == CLO)         /* equivalence..   */
 379                                 break;
 380                         switch(*lp) {
 381
 382                         case BOL:
 383                         case BOT:
 384                         case EOT:
 385                         case BOW:
 386                         case EOW:
 387                         case REF:
 388                                 return badpat("Illegal closure");
 389                         default:
 390                                 break;
 391                         }
 392
 393                         if (*p == '+')
 394                                 for (sp = mp; lp < sp; lp++)
 395                                         store(*lp);
 396
 397                         store(END);
 398                         store(END);
 399                         sp = mp;
 400                         while (--mp > lp)
 401                                 *mp = mp[-1];
 402                         store(CLO);
 403                         mp = sp;
 404                         break;
 405
 406                 case '\\':              /* tags, backrefs .. */
 407                         switch(*++p) {
 408
 409                         case '(':
 410                                 if (tagc < MAXTAG) {
 411                                         tagstk[++tagi] = tagc;
 412                                         store(BOT);
 413                                         store(tagc++);
 414                                 }
 415                                 else
 416                                         return badpat("Too many \\(\\) pairs");
 417                                 break;
 418                         case ')':
 419                                 if (*sp == BOT)
 420                                         return badpat("Null pattern inside \\(\\)");
 421                                 if (tagi > 0) {
 422                                         store(EOT);
 423                                         store(tagstk[tagi--]);
 424                                 }
 425                                 else
 426                                         return badpat("Unmatched \\)");
 427                                 break;
 428                         case '<':
 429                                 store(BOW);
 430                                 break;
 431                         case '>':
 432                                 if (*sp == BOW)
 433                                         return badpat("Null pattern inside \\<\\>");
 434                                 store(EOW);
 435                                 break;
 436                         case '1':
 437                         case '2':
 438                         case '3':
 439                         case '4':
 440                         case '5':
 441                         case '6':
 442                         case '7':
 443                         case '8':
 444                         case '9':
 445                                 n = *p-'0';
 446                                 if (tagi > 0 && tagstk[tagi] == n)
 447                                         return badpat("Cyclical reference");
 448                                 if (tagc > n) {
 449                                         store(REF);
 450                                         store(n);
 451                                 }
 452                                 else
 453                                         return badpat("Undetermined reference");
 454                                 break;
 455 #ifdef EXTEND
 456                         case 'b':
 457                                 store(CHR);
 458                                 store('\b');
 459                                 break;
 460                         case 'n':
 461                                 store(CHR);
 462                                 store('\n');
 463                                 break;
 464                         case 'f':
 465                                 store(CHR);
 466                                 store('\f');
 467                                 break;
 468                         case 'r':
 469                                 store(CHR);
 470                                 store('\r');
 471                                 break;
 472                         case 't':
 473                                 store(CHR);
 474                                 store('\t');
 475                                 break;
 476 #endif
 477                         default:
 478                                 store(CHR);
 479                                 store(*p);
 480                         }
 481                         break;
 482
 483                 default :               /* an ordinary char  */
 484                         store(CHR);
 485                         store(*p);
 486                         break;
 487                 }
 488                 sp = lp;
 489         }
 490         if (tagi > 0)
 491                 return badpat("Unmatched \\(");
 492         store(END);
 493         sta = OKP;
 494         return 0;
 495 }
 496
 497
 498 static char *bol;
 499 char *bopat[MAXTAG];
 500 char *eopat[MAXTAG];
 501 #ifdef NEEDPROTOS
 502 static char *pmatch( char *lp, CHAR *ap );
 503 #else /* NEEDPROTOS */
 504 static char *pmatch();
 505 #endif /* NEEDPROTOS */
 506
 507 /*
 508  * re_exec:
 509  *      execute nfa to find a match.
 510  *
 511  *      special cases: (nfa[0])
 512  *              BOL
 513  *                      Match only once, starting from the
 514  *                      beginning.
 515  *              CHR
 516  *                      First locate the character without
 517  *                      calling pmatch, and if found, call
 518  *                      pmatch for the remaining string.
 519  *              END
 520  *                      re_comp failed, poor luser did not
 521  *                      check for it. Fail fast.
 522  *
 523  *      If a match is found, bopat[0] and eopat[0] are set
 524  *      to the beginning and the end of the matched fragment,
 525  *      respectively.
 526  *
 527  */
 528
 529 int
 530 re_exec( char *lp )
 531 {
 532         register char c;
 533         register char *ep = 0;
 534         register CHAR *ap = nfa;
 535
 536         bol = lp;
 537
 538         bopat[0] = 0;
 539         bopat[1] = 0;
 540         bopat[2] = 0;
 541         bopat[3] = 0;
 542         bopat[4] = 0;
 543         bopat[5] = 0;
 544         bopat[6] = 0;
 545         bopat[7] = 0;
 546         bopat[8] = 0;
 547         bopat[9] = 0;
 548
 549         switch(*ap) {
 550
 551         case BOL:                       /* anchored: match from BOL only */
 552                 ep = pmatch(lp,ap);
 553                 break;
 554         case CHR:                       /* ordinary char: locate it fast */
 555                 c = *(ap+1);
 556                 while (*lp && *lp != c)
 557                         lp++;
 558                 if (!*lp)               /* if EOS, fail, else fall thru. */
 559                         return 0;
 560         default:                        /* regular matching all the way. */
 561                 do {
 562                         if ((ep = pmatch(lp,ap)))
 563                                 break;
 564                         lp++;
 565                 } while (*lp);
 566
 567                 break;
 568         case END:                       /* munged automaton. fail always */
 569                 return 0;
 570         }
 571         if (!ep)
 572                 return 0;
 573
 574         bopat[0] = lp;
 575         eopat[0] = ep;
 576         return 1;
 577 }
 578
 579 /*
 580  * pmatch: internal routine for the hard part
 581  *
 582  *      This code is partly snarfed from an early grep written by
 583  *      David Conroy. The backref and tag stuff, and various other
 584  *      innovations are by oz.
 585  *
 586  *      special case optimizations: (nfa[n], nfa[n+1])
 587  *              CLO ANY
 588  *                      We KNOW .* will match everything upto the
 589  *                      end of line. Thus, directly go to the end of
 590  *                      line, without recursive pmatch calls. As in
 591  *                      the other closure cases, the remaining pattern
 592  *                      must be matched by moving backwards on the
 593  *                      string recursively, to find a match for xy
 594  *                      (x is ".*" and y is the remaining pattern)
 595  *                      where the match satisfies the LONGEST match for
 596  *                      x followed by a match for y.
 597  *              CLO CHR
 598  *                      We can again scan the string forward for the
 599  *                      single char and at the point of failure, we
 600  *                      execute the remaining nfa recursively, same as
 601  *                      above.
 602  *
 603  *      At the end of a successful match, bopat[n] and eopat[n]
 604  *      are set to the beginning and end of subpatterns matched
 605  *      by tagged expressions (n = 1 to 9).
 606  *
 607  */
 608
 609 #ifndef re_fail
 610 extern void re_fail();
 611 #endif /* re_fail */
 612
 613 /*
 614  * character classification table for word boundary operators BOW
 615  * and EOW. the reason for not using ctype macros is that we can
 616  * let the user add into our own table. see re_modw. This table
 617  * is not in the bitset form, since we may wish to extend it in the
 618  * future for other character classifications.
 619  *
 620  *      TRUE for 0-9 A-Z a-z _
 621  */
 622 static char chrtyp[MAXCHR] = {
 623         0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 624         0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 625         0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 626         0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 627         0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
 628         1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
 629         0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
 630         1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 631         1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 632         1, 0, 0, 0, 0, 1, 0, 1, 1, 1,
 633         1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 634         1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 635         1, 1, 1, 0, 0, 0, 0, 0
 636         };
 637
 638 #define inascii(x)      (0177&(x))
 639 #define iswordc(x)      chrtyp[inascii(x)]
 640 #define isinset(x,y)    ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
 641
 642 /*
 643  * skip values for CLO XXX to skip past the closure
 644  */
 645
 646 #define ANYSKIP 2       /* [CLO] ANY END ...         */
 647 #define CHRSKIP 3       /* [CLO] CHR chr END ...     */
 648 #define CCLSKIP 18      /* [CLO] CCL 16bytes END ... */
 649
 650 static char *
 651 pmatch( char *lp, CHAR *ap)
 652 {
 653         register int op, c, n;
 654         register char *e;               /* extra pointer for CLO */
 655         register char *bp;              /* beginning of subpat.. */
 656         register char *ep;              /* ending of subpat..    */
 657         char *are;                      /* to save the line ptr. */
 658
 659         while ((op = *ap++) != END)
 660                 switch(op) {
 661
 662                 case CHR:
 663                         if (*lp++ != *ap++)
 664                                 return 0;
 665                         break;
 666                 case ANY:
 667                         if (!*lp++)
 668                                 return 0;
 669                         break;
 670                 case CCL:
 671                         c = *lp++;
 672                         if (!isinset(ap,c))
 673                                 return 0;
 674                         ap += BITBLK;
 675                         break;
 676                 case BOL:
 677                         if (lp != bol)
 678                                 return 0;
 679                         break;
 680                 case EOL:
 681                         if (*lp)
 682                                 return 0;
 683                         break;
 684                 case BOT:
 685                         bopat[*ap++] = lp;
 686                         break;
 687                 case EOT:
 688                         eopat[*ap++] = lp;
 689                         break;
 690                 case BOW:
 691                         if (lp!=bol && iswordc(lp[-1]) || !iswordc(*lp))
 692                                 return 0;
 693                         break;
 694                 case EOW:
 695                         if (lp==bol || !iswordc(lp[-1]) || iswordc(*lp))
 696                                 return 0;
 697                         break;
 698                 case REF:
 699                         n = *ap++;
 700                         bp = bopat[n];
 701                         ep = eopat[n];
 702                         while (bp < ep)
 703                                 if (*bp++ != *lp++)
 704                                         return 0;
 705                         break;
 706                 case CLO:
 707                         are = lp;
 708                         switch(*ap) {
 709
 710                         case ANY:
 711                                 while (*lp)
 712                                         lp++;
 713                                 n = ANYSKIP;
 714                                 break;
 715                         case CHR:
 716                                 c = *(ap+1);
 717                                 while (*lp && c == *lp)
 718                                         lp++;
 719                                 n = CHRSKIP;
 720                                 break;
 721                         case CCL:
 722                                 while ((c = *lp) && isinset(ap+1,c))
 723                                         lp++;
 724                                 n = CCLSKIP;
 725                                 break;
 726                         default:
 727                                 re_fail("closure: bad nfa.", *ap);
 728                                 return 0;
 729                         }
 730
 731                         ap += n;
 732
 733                         while (lp >= are) {
 734                                 if (e = pmatch(lp, ap))
 735                                         return e;
 736                                 --lp;
 737                         }
 738                         return 0;
 739                 default:
 740                         re_fail("re_exec: bad nfa.", op);
 741                         return 0;
 742                 }
 743         return lp;
 744 }
 745
 746 /*
 747  * re_modw:
 748  *      add new characters into the word table to change re_exec's
 749  *      understanding of what a word should look like. Note that we
 750  *      only accept additions into the word definition.
 751  *
 752  *      If the string parameter is 0 or null string, the table is
 753  *      reset back to the default containing A-Z a-z 0-9 _. [We use
 754  *      the compact bitset representation for the default table]
 755  */
 756
 757 static CHAR deftab[16] = {
 758         0, 0, 0, 0, 0, 0, 0377, 003, 0376, 0377, 0377, 0207,
 759         0376, 0377, 0377, 007
 760 };
 761
 762 void
 763 re_modw( char *s )
 764 {
 765         register int i;
 766
 767         if (!s || !*s) {
 768                 for (i = 0; i < MAXCHR; i++)
 769                         if (!isinset(deftab,i))
 770                                 iswordc(i) = 0;
 771         }
 772         else
 773                 while(*s)
 774                         iswordc(*s++) = 1;
 775 }
 776
 777 /*
 778  * re_subs:
 779  *      substitute the matched portions of the src in dst.
 780  *
 781  *      &       substitute the entire matched pattern.
 782  *
 783  *      \digit  substitute a subpattern, with the given tag number.
 784  *              Tags are numbered from 1 to 9. If the particular
 785  *              tagged subpattern does not exist, null is substituted.
 786  */
 787 int
 788 re_subs( char *src, char *dst)
 789 {
 790         register char c;
 791         register int  pin;
 792         register char *bp;
 793         register char *ep;
 794
 795         if (!*src || !bopat[0])
 796                 return 0;
 797
 798         while (c = *src++) {
 799                 switch(c) {
 800
 801                 case '&':
 802                         pin = 0;
 803                         break;
 804
 805                 case '\\':
 806                         c = *src++;
 807                         if (c >= '0' && c <= '9') {
 808                                 pin = c - '0';
 809                                 break;
 810                         }
 811
 812                 default:
 813                         *dst++ = c;
 814                         continue;
 815                 }
 816
 817                 if ((bp = bopat[pin]) && (ep = eopat[pin])) {
 818                         while (*bp && bp < ep)
 819                                 *dst++ = *bp++;
 820                         if (bp < ep)
 821                                 return 0;
 822                 }
 823         }
 824         *dst = (char) 0;
 825         return 1;
 826 }
 827
 828 #ifdef DEBUG
 829 /*
 830  * symbolic - produce a symbolic dump of the nfa
 831  */
 832 symbolic( char *s )
 833 {
 834         printf("pattern: %s\n", s);
 835         printf("nfacode:\n");
 836         nfadump(nfa);
 837 }
 838
 839 static
 840 nfadump( CHAR *ap)
 841 {
 842         register int n;
 843
 844         while (*ap != END)
 845                 switch(*ap++) {
 846                 case CLO:
 847                         printf("CLOSURE");
 848                         nfadump(ap);
 849                         switch(*ap) {
 850                         case CHR:
 851                                 n = CHRSKIP;
 852                                 break;
 853                         case ANY:
 854                                 n = ANYSKIP;
 855                                 break;
 856                         case CCL:
 857                                 n = CCLSKIP;
 858                                 break;
 859                         }
 860                         ap += n;
 861                         break;
 862                 case CHR:
 863                         printf("\tCHR %c\n",*ap++);
 864                         break;
 865                 case ANY:
 866                         printf("\tANY .\n");
 867                         break;
 868                 case BOL:
 869                         printf("\tBOL -\n");
 870                         break;
 871                 case EOL:
 872                         printf("\tEOL -\n");
 873                         break;
 874                 case BOT:
 875                         printf("BOT: %d\n",*ap++);
 876                         break;
 877                 case EOT:
 878                         printf("EOT: %d\n",*ap++);
 879                         break;
 880                 case BOW:
 881                         printf("BOW\n");
 882                         break;
 883                 case EOW:
 884                         printf("EOW\n");
 885                         break;
 886                 case REF:
 887                         printf("REF: %d\n",*ap++);
 888                         break;
 889                 case CCL:
 890                         printf("\tCCL [");
 891                         for (n = 0; n < MAXCHR; n++)
 892                                 if (isinset(ap,(CHAR)n)) {
 893                                         if (n < ' ')
 894                                                 printf("^%c", n ^ 0x040);
 895                                         else
 896                                                 printf("%c", n);
 897                                 }
 898                         printf("]\n");
 899                         ap += BITBLK;
 900                         break;
 901                 default:
 902                         printf("bad nfa. opcode %o\n", ap[-1]);
 903                         exit(1);
 904                         break;
 905                 }
 906 }
 907 #endif
 908 #endif /* MACOS or DOS or NEED_BSDREGEX */