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