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