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