gdb/regex.c

   1 /* Extended regular expression matching and search library.
   2    Copyright (C) 1985, 1989 Free Software Foundation, Inc.
   3
   4 This program is free software; you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation; either version 2 of the License, or
   7 (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* To test, compile with -Dtest.
  19  This Dtestable feature turns this into a self-contained program
  20  which reads a pattern, describes how it compiles,
  21  then reads a string and searches for it.  */
  22
  23 #ifdef emacs
  24
  25 /* The `emacs' switch turns on certain special matching commands
  26  that make sense only in emacs. */
  27
  28 #include "config.h"
  29 #include "lisp.h"
  30 #include "buffer.h"
  31 #include "syntax.h"
  32
  33 #else  /* not emacs */
  34
  35 /* Make alloca work the best possible way.  */
  36 #ifdef __GNUC__
  37 #define alloca __builtin_alloca
  38 #else
  39 #ifdef sparc
  40 #include <alloca.h>
  41 #endif
  42 #endif
  43
  44 /*
  45  * Define the syntax stuff, so we can do the \<...\> things.
  46  */
  47
  48 #ifndef Sword /* must be non-zero in some of the tests below... */
  49 #define Sword 1
  50 #endif
  51
  52 #define SYNTAX(c) re_syntax_table[c]
  53
  54 #ifdef SYNTAX_TABLE
  55
  56 char *re_syntax_table;
  57
  58 #else
  59
  60 static char re_syntax_table[256];
  61
  62 static void
  63 init_syntax_once ()
  64 {
  65    register int c;
  66    static int done = 0;
  67
  68    if (done)
  69      return;
  70
  71    memset (re_syntax_table, '\0', sizeof re_syntax_table);
  72
  73    for (c = 'a'; c <= 'z'; c++)
  74      re_syntax_table[c] = Sword;
  75
  76    for (c = 'A'; c <= 'Z'; c++)
  77      re_syntax_table[c] = Sword;
  78
  79    for (c = '0'; c <= '9'; c++)
  80      re_syntax_table[c] = Sword;
  81
  82    done = 1;
  83 }
  84
  85 #endif /* SYNTAX_TABLE */
  86 #endif /* not emacs */
  87
  88 #include "regex.h"
  89
  90 /* Number of failure points to allocate space for initially,
  91  when matching.  If this number is exceeded, more space is allocated,
  92  so it is not a hard limit.  */
  93
  94 #ifndef NFAILURES
  95 #define NFAILURES 80
  96 #endif /* NFAILURES */
  97
  98 /* width of a byte in bits */
  99
 100 #define BYTEWIDTH 8
 101
 102 #ifndef SIGN_EXTEND_CHAR
 103 #define SIGN_EXTEND_CHAR(x) (x)
 104 #endif
 105 \f
 106 static int obscure_syntax = 0;
 107
 108 /* Specify the precise syntax of regexp for compilation.
 109    This provides for compatibility for various utilities
 110    which historically have different, incompatible syntaxes.
 111
 112    The argument SYNTAX is a bit-mask containing the two bits
 113    RE_NO_BK_PARENS and RE_NO_BK_VBAR.  */
 114
 115 int
 116 re_set_syntax (syntax)
 117      int syntax;
 118 {
 119   int ret;
 120
 121   ret = obscure_syntax;
 122   obscure_syntax = syntax;
 123   return ret;
 124 }
 125 \f
 126 /* re_compile_pattern takes a regular-expression string
 127    and converts it into a buffer full of byte commands for matching.
 128
 129   PATTERN   is the address of the pattern string
 130   SIZE      is the length of it.
 131   BUFP      is a  struct re_pattern_buffer *  which points to the info
 132             on where to store the byte commands.
 133             This structure contains a  char *  which points to the
 134             actual space, which should have been obtained with malloc.
 135             re_compile_pattern may use  realloc  to grow the buffer space.
 136
 137   The number of bytes of commands can be found out by looking in
 138   the  struct re_pattern_buffer  that bufp pointed to,
 139   after re_compile_pattern returns.
 140 */
 141
 142 #define PATPUSH(ch) (*b++ = (char) (ch))
 143
 144 #define PATFETCH(c) \
 145  {if (p == pend) goto end_of_pattern; \
 146   c = * (unsigned char *) p++; \
 147   if (translate) c = translate[c]; }
 148
 149 #define PATFETCH_RAW(c) \
 150  {if (p == pend) goto end_of_pattern; \
 151   c = * (unsigned char *) p++; }
 152
 153 #define PATUNFETCH p--
 154
 155 #define EXTEND_BUFFER \
 156   { char *old_buffer = bufp->buffer; \
 157     if (bufp->allocated == (1<<16)) goto too_big; \
 158     bufp->allocated *= 2; \
 159     if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \
 160     if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \
 161       goto memory_exhausted; \
 162     c = bufp->buffer - old_buffer; \
 163     b += c; \
 164     if (fixup_jump) \
 165       fixup_jump += c; \
 166     if (laststart) \
 167       laststart += c; \
 168     begalt += c; \
 169     if (pending_exact) \
 170       pending_exact += c; \
 171   }
 172
 173 static void store_jump (), insert_jump ();
 174
 175 char *
 176 re_compile_pattern (pattern, size, bufp)
 177      char *pattern;
 178      int size;
 179      struct re_pattern_buffer *bufp;
 180 {
 181   register char *b = bufp->buffer;
 182   register char *p = pattern;
 183   char *pend = pattern + size;
 184   register unsigned c, c1;
 185   char *p1;
 186   unsigned char *translate = (unsigned char *) bufp->translate;
 187
 188   /* address of the count-byte of the most recently inserted "exactn" command.
 189     This makes it possible to tell whether a new exact-match character
 190     can be added to that command or requires a new "exactn" command. */
 191
 192   char *pending_exact = 0;
 193
 194   /* address of the place where a forward-jump should go
 195     to the end of the containing expression.
 196     Each alternative of an "or", except the last, ends with a forward-jump
 197     of this sort. */
 198
 199   char *fixup_jump = 0;
 200
 201   /* address of start of the most recently finished expression.
 202     This tells postfix * where to find the start of its operand. */
 203
 204   char *laststart = 0;
 205
 206   /* In processing a repeat, 1 means zero matches is allowed */
 207
 208   char zero_times_ok;
 209
 210   /* In processing a repeat, 1 means many matches is allowed */
 211
 212   char many_times_ok;
 213
 214   /* address of beginning of regexp, or inside of last \( */
 215
 216   char *begalt = b;
 217
 218   /* Stack of information saved by \( and restored by \).
 219      Four stack elements are pushed by each \(:
 220        First, the value of b.
 221        Second, the value of fixup_jump.
 222        Third, the value of regnum.
 223        Fourth, the value of begalt.  */
 224
 225   int stackb[40];
 226   int *stackp = stackb;
 227   int *stacke = stackb + 40;
 228   int *stackt;
 229
 230   /* Counts \('s as they are encountered.  Remembered for the matching \),
 231      where it becomes the "register number" to put in the stop_memory command */
 232
 233   int regnum = 1;
 234
 235   bufp->fastmap_accurate = 0;
 236
 237 #ifndef emacs
 238 #ifndef SYNTAX_TABLE
 239   /*
 240    * Initialize the syntax table.
 241    */
 242    init_syntax_once();
 243 #endif
 244 #endif
 245
 246   if (bufp->allocated == 0)
 247     {
 248       bufp->allocated = 28;
 249       if (bufp->buffer)
 250         /* EXTEND_BUFFER loses when bufp->allocated is 0 */
 251         bufp->buffer = (char *) realloc (bufp->buffer, 28);
 252       else
 253         /* Caller did not allocate a buffer.  Do it for him */
 254         bufp->buffer = (char *) malloc (28);
 255       if (!bufp->buffer) goto memory_exhausted;
 256       begalt = b = bufp->buffer;
 257     }
 258
 259   while (p != pend)
 260     {
 261       if (b - bufp->buffer > bufp->allocated - 10)
 262         /* Note that EXTEND_BUFFER clobbers c */
 263         EXTEND_BUFFER;
 264
 265       PATFETCH (c);
 266
 267       switch (c)
 268         {
 269         case '$':
 270           if (obscure_syntax & RE_TIGHT_VBAR)
 271             {
 272               if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS) && p != pend)
 273                 goto normal_char;
 274               /* Make operand of last vbar end before this `$'.  */
 275               if (fixup_jump)
 276                 store_jump (fixup_jump, jump, b);
 277               fixup_jump = 0;
 278               PATPUSH (endline);
 279               break;
 280             }
 281
 282           /* $ means succeed if at end of line, but only in special contexts.
 283             If randomly in the middle of a pattern, it is a normal character. */
 284           if (p == pend || *p == '\n'
 285               || (obscure_syntax & RE_CONTEXT_INDEP_OPS)
 286               || (obscure_syntax & RE_NO_BK_PARENS
 287                   ? *p == ')'
 288                   : *p == '\\' && p[1] == ')')
 289               || (obscure_syntax & RE_NO_BK_VBAR
 290                   ? *p == '|'
 291                   : *p == '\\' && p[1] == '|'))
 292             {
 293               PATPUSH (endline);
 294               break;
 295             }
 296           goto normal_char;
 297
 298         case '^':
 299           /* ^ means succeed if at beg of line, but only if no preceding pattern. */
 300
 301           if (laststart && p[-2] != '\n'
 302               && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
 303             goto normal_char;
 304           if (obscure_syntax & RE_TIGHT_VBAR)
 305             {
 306               if (p != pattern + 1
 307                   && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
 308                 goto normal_char;
 309               PATPUSH (begline);
 310               begalt = b;
 311             }
 312           else
 313             PATPUSH (begline);
 314           break;
 315
 316         case '+':
 317         case '?':
 318           if (obscure_syntax & RE_BK_PLUS_QM)
 319             goto normal_char;
 320         handle_plus:
 321         case '*':
 322           /* If there is no previous pattern, char not special. */
 323           if (!laststart && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
 324             goto normal_char;
 325           /* If there is a sequence of repetition chars,
 326              collapse it down to equivalent to just one.  */
 327           zero_times_ok = 0;
 328           many_times_ok = 0;
 329           while (1)
 330             {
 331               zero_times_ok |= c != '+';
 332               many_times_ok |= c != '?';
 333               if (p == pend)
 334                 break;
 335               PATFETCH (c);
 336               if (c == '*')
 337                 ;
 338               else if (!(obscure_syntax & RE_BK_PLUS_QM)
 339                        && (c == '+' || c == '?'))
 340                 ;
 341               else if ((obscure_syntax & RE_BK_PLUS_QM)
 342                        && c == '\\')
 343                 {
 344                   int c1;
 345                   PATFETCH (c1);
 346                   if (!(c1 == '+' || c1 == '?'))
 347                     {
 348                       PATUNFETCH;
 349                       PATUNFETCH;
 350                       break;
 351                     }
 352                   c = c1;
 353                 }
 354               else
 355                 {
 356                   PATUNFETCH;
 357                   break;
 358                 }
 359             }
 360
 361           /* Star, etc. applied to an empty pattern is equivalent
 362              to an empty pattern.  */
 363           if (!laststart)
 364             break;
 365
 366           /* Now we know whether 0 matches is allowed,
 367              and whether 2 or more matches is allowed.  */
 368           if (many_times_ok)
 369             {
 370               /* If more than one repetition is allowed,
 371                  put in a backward jump at the end.  */
 372               store_jump (b, maybe_finalize_jump, laststart - 3);
 373               b += 3;
 374             }
 375           insert_jump (on_failure_jump, laststart, b + 3, b);
 376           pending_exact = 0;
 377           b += 3;
 378           if (!zero_times_ok)
 379             {
 380               /* At least one repetition required: insert before the loop
 381                  a skip over the initial on-failure-jump instruction */
 382               insert_jump (dummy_failure_jump, laststart, laststart + 6, b);
 383               b += 3;
 384             }
 385           break;
 386
 387         case '.':
 388           laststart = b;
 389           PATPUSH (anychar);
 390           break;
 391
 392         case '[':
 393           while (b - bufp->buffer
 394                  > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH)
 395             /* Note that EXTEND_BUFFER clobbers c */
 396             EXTEND_BUFFER;
 397
 398           laststart = b;
 399           if (*p == '^')
 400             PATPUSH (charset_not), p++;
 401           else
 402             PATPUSH (charset);
 403           p1 = p;
 404
 405           PATPUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
 406           /* Clear the whole map */
 407           memset (b, '\0', (1 << BYTEWIDTH) / BYTEWIDTH);
 408           /* Read in characters and ranges, setting map bits */
 409           while (1)
 410             {
 411               PATFETCH (c);
 412               if (c == ']' && p != p1 + 1) break;
 413               if (*p == '-' && p[1] != ']')
 414                 {
 415                   PATFETCH (c1);
 416                   PATFETCH (c1);
 417                   while (c <= c1)
 418                     b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH), c++;
 419                 }
 420               else
 421                 {
 422                   b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH);
 423                 }
 424             }
 425           /* Discard any bitmap bytes that are all 0 at the end of the map.
 426              Decrement the map-length byte too. */
 427           while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
 428             b[-1]--;
 429           b += b[-1];
 430           break;
 431
 432         case '(':
 433           if (! (obscure_syntax & RE_NO_BK_PARENS))
 434             goto normal_char;
 435           else
 436             goto handle_open;
 437
 438         case ')':
 439           if (! (obscure_syntax & RE_NO_BK_PARENS))
 440             goto normal_char;
 441           else
 442             goto handle_close;
 443
 444         case '\n':
 445           if (! (obscure_syntax & RE_NEWLINE_OR))
 446             goto normal_char;
 447           else
 448             goto handle_bar;
 449
 450         case '|':
 451           if (! (obscure_syntax & RE_NO_BK_VBAR))
 452             goto normal_char;
 453           else
 454             goto handle_bar;
 455
 456         case '\\':
 457           if (p == pend) goto invalid_pattern;
 458           PATFETCH_RAW (c);
 459           switch (c)
 460             {
 461             case '(':
 462               if (obscure_syntax & RE_NO_BK_PARENS)
 463                 goto normal_backsl;
 464             handle_open:
 465               if (stackp == stacke) goto nesting_too_deep;
 466               if (regnum < RE_NREGS)
 467                 {
 468                   PATPUSH (start_memory);
 469                   PATPUSH (regnum);
 470                 }
 471               *stackp++ = b - bufp->buffer;
 472               *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0;
 473               *stackp++ = regnum++;
 474               *stackp++ = begalt - bufp->buffer;
 475               fixup_jump = 0;
 476               laststart = 0;
 477               begalt = b;
 478               break;
 479
 480             case ')':
 481               if (obscure_syntax & RE_NO_BK_PARENS)
 482                 goto normal_backsl;
 483             handle_close:
 484               if (stackp == stackb) goto unmatched_close;
 485               begalt = *--stackp + bufp->buffer;
 486               if (fixup_jump)
 487                 store_jump (fixup_jump, jump, b);
 488               if (stackp[-1] < RE_NREGS)
 489                 {
 490                   PATPUSH (stop_memory);
 491                   PATPUSH (stackp[-1]);
 492                 }
 493               stackp -= 2;
 494               fixup_jump = 0;
 495               if (*stackp)
 496                 fixup_jump = *stackp + bufp->buffer - 1;
 497               laststart = *--stackp + bufp->buffer;
 498               break;
 499
 500             case '|':
 501               if (obscure_syntax & RE_NO_BK_VBAR)
 502                 goto normal_backsl;
 503             handle_bar:
 504               insert_jump (on_failure_jump, begalt, b + 6, b);
 505               pending_exact = 0;
 506               b += 3;
 507               if (fixup_jump)
 508                 store_jump (fixup_jump, jump, b);
 509               fixup_jump = b;
 510               b += 3;
 511               laststart = 0;
 512               begalt = b;
 513               break;
 514
 515 #ifdef emacs
 516             case '=':
 517               PATPUSH (at_dot);
 518               break;
 519
 520             case 's':
 521               laststart = b;
 522               PATPUSH (syntaxspec);
 523               PATFETCH (c);
 524               PATPUSH (syntax_spec_code[c]);
 525               break;
 526
 527             case 'S':
 528               laststart = b;
 529               PATPUSH (notsyntaxspec);
 530               PATFETCH (c);
 531               PATPUSH (syntax_spec_code[c]);
 532               break;
 533 #endif /* emacs */
 534
 535             case 'w':
 536               laststart = b;
 537               PATPUSH (wordchar);
 538               break;
 539
 540             case 'W':
 541               laststart = b;
 542               PATPUSH (notwordchar);
 543               break;
 544
 545             case '<':
 546               PATPUSH (wordbeg);
 547               break;
 548
 549             case '>':
 550               PATPUSH (wordend);
 551               break;
 552
 553             case 'b':
 554               PATPUSH (wordbound);
 555               break;
 556
 557             case 'B':
 558               PATPUSH (notwordbound);
 559               break;
 560
 561             case '`':
 562               PATPUSH (begbuf);
 563               break;
 564
 565             case '\'':
 566               PATPUSH (endbuf);
 567               break;
 568
 569             case '1':
 570             case '2':
 571             case '3':
 572             case '4':
 573             case '5':
 574             case '6':
 575             case '7':
 576             case '8':
 577             case '9':
 578               c1 = c - '0';
 579               if (c1 >= regnum)
 580                 goto normal_char;
 581               for (stackt = stackp - 2;  stackt > stackb;  stackt -= 4)
 582                 if (*stackt == c1)
 583                   goto normal_char;
 584               laststart = b;
 585               PATPUSH (duplicate);
 586               PATPUSH (c1);
 587               break;
 588
 589             case '+':
 590             case '?':
 591               if (obscure_syntax & RE_BK_PLUS_QM)
 592                 goto handle_plus;
 593
 594             default:
 595             normal_backsl:
 596               /* You might think it would be useful for \ to mean
 597                  not to translate; but if we don't translate it
 598                  it will never match anything.  */
 599               if (translate) c = translate[c];
 600               goto normal_char;
 601             }
 602           break;
 603
 604         default:
 605         normal_char:
 606           if (!pending_exact || pending_exact + *pending_exact + 1 != b
 607               || *pending_exact == 0177 || *p == '*' || *p == '^'
 608               || ((obscure_syntax & RE_BK_PLUS_QM)
 609                   ? *p == '\\' && (p[1] == '+' || p[1] == '?')
 610                   : (*p == '+' || *p == '?')))
 611             {
 612               laststart = b;
 613               PATPUSH (exactn);
 614               pending_exact = b;
 615               PATPUSH (0);
 616             }
 617           PATPUSH (c);
 618           (*pending_exact)++;
 619         }
 620     }
 621
 622   if (fixup_jump)
 623     store_jump (fixup_jump, jump, b);
 624
 625   if (stackp != stackb) goto unmatched_open;
 626
 627   bufp->used = b - bufp->buffer;
 628   return 0;
 629
 630  invalid_pattern:
 631   return "Invalid regular expression";
 632
 633  unmatched_open:
 634   return "Unmatched \\(";
 635
 636  unmatched_close:
 637   return "Unmatched \\)";
 638
 639  end_of_pattern:
 640   return "Premature end of regular expression";
 641
 642  nesting_too_deep:
 643   return "Nesting too deep";
 644
 645  too_big:
 646   return "Regular expression too big";
 647
 648  memory_exhausted:
 649   return "Memory exhausted";
 650 }
 651
 652 /* Store where `from' points a jump operation to jump to where `to' points.
 653   `opcode' is the opcode to store. */
 654
 655 static void
 656 store_jump (from, opcode, to)
 657      char *from, *to;
 658      char opcode;
 659 {
 660   from[0] = opcode;
 661   from[1] = (to - (from + 3)) & 0377;
 662   from[2] = (to - (from + 3)) >> 8;
 663 }
 664
 665 /* Open up space at char FROM, and insert there a jump to TO.
 666    CURRENT_END gives te end of the storage no in use,
 667    so we know how much data to copy up.
 668    OP is the opcode of the jump to insert.
 669
 670    If you call this function, you must zero out pending_exact.  */
 671
 672 static void
 673 insert_jump (op, from, to, current_end)
 674      char op;
 675      char *from, *to, *current_end;
 676 {
 677   register char *pto = current_end + 3;
 678   register char *pfrom = current_end;
 679   while (pfrom != from)
 680     *--pto = *--pfrom;
 681   store_jump (from, op, to);
 682 }
 683 \f
 684 /* Given a pattern, compute a fastmap from it.
 685  The fastmap records which of the (1 << BYTEWIDTH) possible characters
 686  can start a string that matches the pattern.
 687  This fastmap is used by re_search to skip quickly over totally implausible text.
 688
 689  The caller must supply the address of a (1 << BYTEWIDTH)-byte data area
 690  as bufp->fastmap.
 691  The other components of bufp describe the pattern to be used.  */
 692
 693 void
 694 re_compile_fastmap (bufp)
 695      struct re_pattern_buffer *bufp;
 696 {
 697   unsigned char *pattern = (unsigned char *) bufp->buffer;
 698   int size = bufp->used;
 699   register char *fastmap = bufp->fastmap;
 700   register unsigned char *p = pattern;
 701   register unsigned char *pend = pattern + size;
 702   register int j;
 703   unsigned char *translate = (unsigned char *) bufp->translate;
 704
 705   unsigned char *stackb[NFAILURES];
 706   unsigned char **stackp = stackb;
 707
 708   memset (fastmap, '\0', (1 << BYTEWIDTH));
 709   bufp->fastmap_accurate = 1;
 710   bufp->can_be_null = 0;
 711
 712   while (p)
 713     {
 714       if (p == pend)
 715         {
 716           bufp->can_be_null = 1;
 717           break;
 718         }
 719 #ifdef SWITCH_ENUM_BUG
 720       switch ((int) ((enum regexpcode) *p++))
 721 #else
 722       switch ((enum regexpcode) *p++)
 723 #endif
 724         {
 725         case exactn:
 726           if (translate)
 727             fastmap[translate[p[1]]] = 1;
 728           else
 729             fastmap[p[1]] = 1;
 730           break;
 731
 732         case begline:
 733         case before_dot:
 734         case at_dot:
 735         case after_dot:
 736         case begbuf:
 737         case endbuf:
 738         case wordbound:
 739         case notwordbound:
 740         case wordbeg:
 741         case wordend:
 742           continue;
 743
 744         case endline:
 745           if (translate)
 746             fastmap[translate['\n']] = 1;
 747           else
 748             fastmap['\n'] = 1;
 749           if (bufp->can_be_null != 1)
 750             bufp->can_be_null = 2;
 751           break;
 752
 753         case finalize_jump:
 754         case maybe_finalize_jump:
 755         case jump:
 756         case dummy_failure_jump:
 757           bufp->can_be_null = 1;
 758           j = *p++ & 0377;
 759           j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
 760           p += j + 1;           /* The 1 compensates for missing ++ above */
 761           if (j > 0)
 762             continue;
 763           /* Jump backward reached implies we just went through
 764              the body of a loop and matched nothing.
 765              Opcode jumped to should be an on_failure_jump.
 766              Just treat it like an ordinary jump.
 767              For a * loop, it has pushed its failure point already;
 768              if so, discard that as redundant.  */
 769           if ((enum regexpcode) *p != on_failure_jump)
 770             continue;
 771           p++;
 772           j = *p++ & 0377;
 773           j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
 774           p += j + 1;           /* The 1 compensates for missing ++ above */
 775           if (stackp != stackb && *stackp == p)
 776             stackp--;
 777           continue;
 778
 779         case on_failure_jump:
 780           j = *p++ & 0377;
 781           j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
 782           p++;
 783           *++stackp = p + j;
 784           continue;
 785
 786         case start_memory:
 787         case stop_memory:
 788           p++;
 789           continue;
 790
 791         case duplicate:
 792           bufp->can_be_null = 1;
 793           fastmap['\n'] = 1;
 794         case anychar:
 795           for (j = 0; j < (1 << BYTEWIDTH); j++)
 796             if (j != '\n')
 797               fastmap[j] = 1;
 798           if (bufp->can_be_null)
 799             return;
 800           /* Don't return; check the alternative paths
 801              so we can set can_be_null if appropriate.  */
 802           break;
 803
 804         case wordchar:
 805           for (j = 0; j < (1 << BYTEWIDTH); j++)
 806             if (SYNTAX (j) == Sword)
 807               fastmap[j] = 1;
 808           break;
 809
 810         case notwordchar:
 811           for (j = 0; j < (1 << BYTEWIDTH); j++)
 812             if (SYNTAX (j) != Sword)
 813               fastmap[j] = 1;
 814           break;
 815
 816 #ifdef emacs
 817         case syntaxspec:
 818           k = *p++;
 819           for (j = 0; j < (1 << BYTEWIDTH); j++)
 820             if (SYNTAX (j) == (enum syntaxcode) k)
 821               fastmap[j] = 1;
 822           break;
 823
 824         case notsyntaxspec:
 825           k = *p++;
 826           for (j = 0; j < (1 << BYTEWIDTH); j++)
 827             if (SYNTAX (j) != (enum syntaxcode) k)
 828               fastmap[j] = 1;
 829           break;
 830 #endif /* emacs */
 831
 832         case charset:
 833           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
 834             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
 835               {
 836                 if (translate)
 837                   fastmap[translate[j]] = 1;
 838                 else
 839                   fastmap[j] = 1;
 840               }
 841           break;
 842
 843         case charset_not:
 844           /* Chars beyond end of map must be allowed */
 845           for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
 846             if (translate)
 847               fastmap[translate[j]] = 1;
 848             else
 849               fastmap[j] = 1;
 850
 851           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
 852             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
 853               {
 854                 if (translate)
 855                   fastmap[translate[j]] = 1;
 856                 else
 857                   fastmap[j] = 1;
 858               }
 859           break;
 860         }
 861
 862       /* Get here means we have successfully found the possible starting characters
 863          of one path of the pattern.  We need not follow this path any farther.
 864          Instead, look at the next alternative remembered in the stack. */
 865       if (stackp != stackb)
 866         p = *stackp--;
 867       else
 868         break;
 869     }
 870 }
 871 \f
 872 /* Like re_search_2, below, but only one string is specified. */
 873
 874 int
 875 re_search (pbufp, string, size, startpos, range, regs)
 876      struct re_pattern_buffer *pbufp;
 877      char *string;
 878      int size, startpos, range;
 879      struct re_registers *regs;
 880 {
 881   return re_search_2 (pbufp, 0, 0, string, size, startpos, range, regs, size);
 882 }
 883
 884 /* Like re_match_2 but tries first a match starting at index STARTPOS,
 885    then at STARTPOS + 1, and so on.
 886    RANGE is the number of places to try before giving up.
 887    If RANGE is negative, the starting positions tried are
 888     STARTPOS, STARTPOS - 1, etc.
 889    It is up to the caller to make sure that range is not so large
 890    as to take the starting position outside of the input strings.
 891
 892 The value returned is the position at which the match was found,
 893  or -1 if no match was found,
 894  or -2 if error (such as failure stack overflow).  */
 895
 896 int
 897 re_search_2 (pbufp, string1, size1, string2, size2, startpos, range, regs, mstop)
 898      struct re_pattern_buffer *pbufp;
 899      char *string1, *string2;
 900      int size1, size2;
 901      int startpos;
 902      register int range;
 903      struct re_registers *regs;
 904      int mstop;
 905 {
 906   register char *fastmap = pbufp->fastmap;
 907   register unsigned char *translate = (unsigned char *) pbufp->translate;
 908   int total = size1 + size2;
 909   int val;
 910
 911   /* Update the fastmap now if not correct already */
 912   if (fastmap && !pbufp->fastmap_accurate)
 913     re_compile_fastmap (pbufp);
 914
 915   /* Don't waste time in a long search for a pattern
 916      that says it is anchored.  */
 917   if (pbufp->used > 0 && (enum regexpcode) pbufp->buffer[0] == begbuf
 918       && range > 0)
 919     {
 920       if (startpos > 0)
 921         return -1;
 922       else
 923         range = 1;
 924     }
 925
 926   while (1)
 927     {
 928       /* If a fastmap is supplied, skip quickly over characters
 929          that cannot possibly be the start of a match.
 930          Note, however, that if the pattern can possibly match
 931          the null string, we must test it at each starting point
 932          so that we take the first null string we get.  */
 933
 934       if (fastmap && startpos < total && pbufp->can_be_null != 1)
 935         {
 936           if (range > 0)
 937             {
 938               register int lim = 0;
 939               register unsigned char *p;
 940               int irange = range;
 941               if (startpos < size1 && startpos + range >= size1)
 942                 lim = range - (size1 - startpos);
 943
 944               p = ((unsigned char *)
 945                    &(startpos >= size1 ? string2 - size1 : string1)[startpos]);
 946
 947               if (translate)
 948                 {
 949                   while (range > lim && !fastmap[translate[*p++]])
 950                     range--;
 951                 }
 952               else
 953                 {
 954                   while (range > lim && !fastmap[*p++])
 955                     range--;
 956                 }
 957               startpos += irange - range;
 958             }
 959           else
 960             {
 961               register unsigned char c;
 962               if (startpos >= size1)
 963                 c = string2[startpos - size1];
 964               else
 965                 c = string1[startpos];
 966               c &= 0xff;
 967               if (translate ? !fastmap[translate[c]] : !fastmap[c])
 968                 goto advance;
 969             }
 970         }
 971
 972       if (range >= 0 && startpos == total
 973           && fastmap && pbufp->can_be_null == 0)
 974         return -1;
 975
 976       val = re_match_2 (pbufp, string1, size1, string2, size2, startpos, regs, mstop);
 977       if (0 <= val)
 978         {
 979           if (val == -2)
 980             return -2;
 981           return startpos;
 982         }
 983
 984 #ifdef C_ALLOCA
 985       alloca (0);
 986 #endif /* C_ALLOCA */
 987
 988     advance:
 989       if (!range) break;
 990       if (range > 0) range--, startpos++; else range++, startpos--;
 991     }
 992   return -1;
 993 }
 994 \f
 995 #ifndef emacs   /* emacs never uses this */
 996 int
 997 re_match (pbufp, string, size, pos, regs)
 998      struct re_pattern_buffer *pbufp;
 999      char *string;
1000      int size, pos;
1001      struct re_registers *regs;
1002 {
1003   return re_match_2 (pbufp, 0, 0, string, size, pos, regs, size);
1004 }
1005 #endif /* emacs */
1006
1007 /* Maximum size of failure stack.  Beyond this, overflow is an error.  */
1008
1009 int re_max_failures = 2000;
1010
1011 static int memcmp_translate();
1012 /* Match the pattern described by PBUFP
1013    against data which is the virtual concatenation of STRING1 and STRING2.
1014    SIZE1 and SIZE2 are the sizes of the two data strings.
1015    Start the match at position POS.
1016    Do not consider matching past the position MSTOP.
1017
1018    If pbufp->fastmap is nonzero, then it had better be up to date.
1019
1020    The reason that the data to match are specified as two components
1021    which are to be regarded as concatenated
1022    is so this function can be used directly on the contents of an Emacs buffer.
1023
1024    -1 is returned if there is no match.  -2 is returned if there is
1025    an error (such as match stack overflow).  Otherwise the value is the length
1026    of the substring which was matched.  */
1027
1028 int
1029 re_match_2 (pbufp, string1, size1, string2, size2, pos, regs, mstop)
1030      struct re_pattern_buffer *pbufp;
1031      unsigned char *string1, *string2;
1032      int size1, size2;
1033      int pos;
1034      struct re_registers *regs;
1035      int mstop;
1036 {
1037   register unsigned char *p = (unsigned char *) pbufp->buffer;
1038   register unsigned char *pend = p + pbufp->used;
1039   /* End of first string */
1040   unsigned char *end1;
1041   /* End of second string */
1042   unsigned char *end2;
1043   /* Pointer just past last char to consider matching */
1044   unsigned char *end_match_1, *end_match_2;
1045   register unsigned char *d, *dend;
1046   register int mcnt;
1047   unsigned char *translate = (unsigned char *) pbufp->translate;
1048
1049  /* Failure point stack.  Each place that can handle a failure further down the line
1050     pushes a failure point on this stack.  It consists of two char *'s.
1051     The first one pushed is where to resume scanning the pattern;
1052     the second pushed is where to resume scanning the strings.
1053     If the latter is zero, the failure point is a "dummy".
1054     If a failure happens and the innermost failure point is dormant,
1055     it discards that failure point and tries the next one. */
1056
1057   unsigned char *initial_stack[2 * NFAILURES];
1058   unsigned char **stackb = initial_stack;
1059   unsigned char **stackp = stackb, **stacke = &stackb[2 * NFAILURES];
1060
1061   /* Information on the "contents" of registers.
1062      These are pointers into the input strings; they record
1063      just what was matched (on this attempt) by some part of the pattern.
1064      The start_memory command stores the start of a register's contents
1065      and the stop_memory command stores the end.
1066
1067      At that point, regstart[regnum] points to the first character in the register,
1068      regend[regnum] points to the first character beyond the end of the register,
1069      regstart_seg1[regnum] is true iff regstart[regnum] points into string1,
1070      and regend_seg1[regnum] is true iff regend[regnum] points into string1.  */
1071
1072   unsigned char *regstart[RE_NREGS];
1073   unsigned char *regend[RE_NREGS];
1074   unsigned char regstart_seg1[RE_NREGS], regend_seg1[RE_NREGS];
1075
1076   /* Set up pointers to ends of strings.
1077      Don't allow the second string to be empty unless both are empty.  */
1078   if (!size2)
1079     {
1080       string2 = string1;
1081       size2 = size1;
1082       string1 = 0;
1083       size1 = 0;
1084     }
1085   end1 = string1 + size1;
1086   end2 = string2 + size2;
1087
1088   /* Compute where to stop matching, within the two strings */
1089   if (mstop <= size1)
1090     {
1091       end_match_1 = string1 + mstop;
1092       end_match_2 = string2;
1093     }
1094   else
1095     {
1096       end_match_1 = end1;
1097       end_match_2 = string2 + mstop - size1;
1098     }
1099
1100   /* Initialize \) text positions to -1
1101      to mark ones that no \( or \) has been seen for.  */
1102
1103   for (mcnt = 0; mcnt < sizeof (regend) / sizeof (*regend); mcnt++)
1104     regend[mcnt] = (unsigned char *) -1;
1105
1106   /* `p' scans through the pattern as `d' scans through the data.
1107      `dend' is the end of the input string that `d' points within.
1108      `d' is advanced into the following input string whenever necessary,
1109      but this happens before fetching;
1110      therefore, at the beginning of the loop,
1111      `d' can be pointing at the end of a string,
1112      but it cannot equal string2.  */
1113
1114   if (pos <= size1)
1115     d = string1 + pos, dend = end_match_1;
1116   else
1117     d = string2 + pos - size1, dend = end_match_2;
1118
1119 /* Write PREFETCH; just before fetching a character with *d.  */
1120 #define PREFETCH \
1121  while (d == dend)                                                  \
1122   { if (dend == end_match_2) goto fail;  /* end of string2 => failure */   \
1123     d = string2;  /* end of string1 => advance to string2. */       \
1124     dend = end_match_2; }
1125
1126   /* This loop loops over pattern commands.
1127      It exits by returning from the function if match is complete,
1128      or it drops through if match fails at this starting point in the input data. */
1129
1130   while (1)
1131     {
1132       if (p == pend)
1133         /* End of pattern means we have succeeded! */
1134         {
1135           /* If caller wants register contents data back, convert it to indices */
1136           if (regs)
1137             {
1138               regs->start[0] = pos;
1139               if (dend == end_match_1)
1140                 regs->end[0] = d - string1;
1141               else
1142                 regs->end[0] = d - string2 + size1;
1143               for (mcnt = 1; mcnt < RE_NREGS; mcnt++)
1144                 {
1145                   if (regend[mcnt] == (unsigned char *) -1)
1146                     {
1147                       regs->start[mcnt] = -1;
1148                       regs->end[mcnt] = -1;
1149                       continue;
1150                     }
1151                   if (regstart_seg1[mcnt])
1152                     regs->start[mcnt] = regstart[mcnt] - string1;
1153                   else
1154                     regs->start[mcnt] = regstart[mcnt] - string2 + size1;
1155                   if (regend_seg1[mcnt])
1156                     regs->end[mcnt] = regend[mcnt] - string1;
1157                   else
1158                     regs->end[mcnt] = regend[mcnt] - string2 + size1;
1159                 }
1160             }
1161           if (dend == end_match_1)
1162             return (d - string1 - pos);
1163           else
1164             return d - string2 + size1 - pos;
1165         }
1166
1167       /* Otherwise match next pattern command */
1168 #ifdef SWITCH_ENUM_BUG
1169       switch ((int) ((enum regexpcode) *p++))
1170 #else
1171       switch ((enum regexpcode) *p++)
1172 #endif
1173         {
1174
1175         /* \( is represented by a start_memory, \) by a stop_memory.
1176             Both of those commands contain a "register number" argument.
1177             The text matched within the \( and \) is recorded under that number.
1178             Then, \<digit> turns into a `duplicate' command which
1179             is followed by the numeric value of <digit> as the register number. */
1180
1181         case start_memory:
1182           regstart[*p] = d;
1183           regstart_seg1[*p++] = (dend == end_match_1);
1184           break;
1185
1186         case stop_memory:
1187           regend[*p] = d;
1188           regend_seg1[*p++] = (dend == end_match_1);
1189           break;
1190
1191         case duplicate:
1192           {
1193             int regno = *p++;   /* Get which register to match against */
1194             register unsigned char *d2, *dend2;
1195
1196             d2 = regstart[regno];
1197             dend2 = ((regstart_seg1[regno] == regend_seg1[regno])
1198                      ? regend[regno] : end_match_1);
1199             while (1)
1200               {
1201                 /* Advance to next segment in register contents, if necessary */
1202                 while (d2 == dend2)
1203                   {
1204                     if (dend2 == end_match_2) break;
1205                     if (dend2 == regend[regno]) break;
1206                     d2 = string2, dend2 = regend[regno];  /* end of string1 => advance to string2. */
1207                   }
1208                 /* At end of register contents => success */
1209                 if (d2 == dend2) break;
1210
1211                 /* Advance to next segment in data being matched, if necessary */
1212                 PREFETCH;
1213
1214                 /* mcnt gets # consecutive chars to compare */
1215                 mcnt = dend - d;
1216                 if (mcnt > dend2 - d2)
1217                   mcnt = dend2 - d2;
1218                 /* Compare that many; failure if mismatch, else skip them. */
1219                 if (translate ? memcmp_translate (d, d2, mcnt, translate) : memcmp (d, d2, mcnt))
1220                   goto fail;
1221                 d += mcnt, d2 += mcnt;
1222               }
1223           }
1224           break;
1225
1226         case anychar:
1227           /* fetch a data character */
1228           PREFETCH;
1229           /* Match anything but a newline.  */
1230           if ((translate ? translate[*d++] : *d++) == '\n')
1231             goto fail;
1232           break;
1233
1234         case charset:
1235         case charset_not:
1236           {
1237             /* Nonzero for charset_not */
1238             int not = 0;
1239             register int c;
1240             if (*(p - 1) == (unsigned char) charset_not)
1241               not = 1;
1242
1243             /* fetch a data character */
1244             PREFETCH;
1245
1246             if (translate)
1247               c = translate [*d];
1248             else
1249               c = *d;
1250
1251             if (c < *p * BYTEWIDTH
1252                 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
1253               not = !not;
1254
1255             p += 1 + *p;
1256
1257             if (!not) goto fail;
1258             d++;
1259             break;
1260           }
1261
1262         case begline:
1263           if (d == string1 || d[-1] == '\n')
1264             break;
1265           goto fail;
1266
1267         case endline:
1268           if (d == end2
1269               || (d == end1 ? (size2 == 0 || *string2 == '\n') : *d == '\n'))
1270             break;
1271           goto fail;
1272
1273         /* "or" constructs ("|") are handled by starting each alternative
1274             with an on_failure_jump that points to the start of the next alternative.
1275             Each alternative except the last ends with a jump to the joining point.
1276             (Actually, each jump except for the last one really jumps
1277              to the following jump, because tensioning the jumps is a hassle.) */
1278
1279         /* The start of a stupid repeat has an on_failure_jump that points
1280            past the end of the repeat text.
1281            This makes a failure point so that, on failure to match a repetition,
1282            matching restarts past as many repetitions have been found
1283            with no way to fail and look for another one.  */
1284
1285         /* A smart repeat is similar but loops back to the on_failure_jump
1286            so that each repetition makes another failure point. */
1287
1288         case on_failure_jump:
1289           if (stackp == stacke)
1290             {
1291               unsigned char **stackx;
1292               if (stacke - stackb > re_max_failures * 2)
1293                 return -2;
1294               stackx = (unsigned char **) alloca (2 * (stacke - stackb)
1295                                          * sizeof (char *));
1296               memcpy (stackx, stackb, (stacke - stackb) * sizeof (char *));
1297               stackp = stackx + (stackp - stackb);
1298               stacke = stackx + 2 * (stacke - stackb);
1299               stackb = stackx;
1300             }
1301           mcnt = *p++ & 0377;
1302           mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
1303           p++;
1304           *stackp++ = mcnt + p;
1305           *stackp++ = d;
1306           break;
1307
1308         /* The end of a smart repeat has an maybe_finalize_jump back.
1309            Change it either to a finalize_jump or an ordinary jump. */
1310
1311         case maybe_finalize_jump:
1312           mcnt = *p++ & 0377;
1313           mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
1314           p++;
1315           {
1316             register unsigned char *p2 = p;
1317             /* Compare what follows with the begining of the repeat.
1318                If we can establish that there is nothing that they would
1319                both match, we can change to finalize_jump */
1320             while (p2 != pend
1321                    && (*p2 == (unsigned char) stop_memory
1322                        || *p2 == (unsigned char) start_memory))
1323               p2++;
1324             if (p2 == pend)
1325               p[-3] = (unsigned char) finalize_jump;
1326             else if (*p2 == (unsigned char) exactn
1327                      || *p2 == (unsigned char) endline)
1328               {
1329                 register int c = *p2 == (unsigned char) endline ? '\n' : p2[2];
1330                 register unsigned char *p1 = p + mcnt;
1331                 /* p1[0] ... p1[2] are an on_failure_jump.
1332                    Examine what follows that */
1333                 if (p1[3] == (unsigned char) exactn && p1[5] != c)
1334                   p[-3] = (unsigned char) finalize_jump;
1335                 else if (p1[3] == (unsigned char) charset
1336                          || p1[3] == (unsigned char) charset_not)
1337                   {
1338                     int not = p1[3] == (unsigned char) charset_not;
1339                     if (c < p1[4] * BYTEWIDTH
1340                         && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
1341                       not = !not;
1342                     /* not is 1 if c would match */
1343                     /* That means it is not safe to finalize */
1344                     if (!not)
1345                       p[-3] = (unsigned char) finalize_jump;
1346                   }
1347               }
1348           }
1349           p -= 2;
1350           if (p[-1] != (unsigned char) finalize_jump)
1351             {
1352               p[-1] = (unsigned char) jump;
1353               goto nofinalize;
1354             }
1355
1356         /* The end of a stupid repeat has a finalize-jump
1357            back to the start, where another failure point will be made
1358            which will point after all the repetitions found so far. */
1359
1360         case finalize_jump:
1361           stackp -= 2;
1362
1363         case jump:
1364         nofinalize:
1365           mcnt = *p++ & 0377;
1366           mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
1367           p += mcnt + 1;        /* The 1 compensates for missing ++ above */
1368           break;
1369
1370         case dummy_failure_jump:
1371           if (stackp == stacke)
1372             {
1373               unsigned char **stackx
1374                 = (unsigned char **) alloca (2 * (stacke - stackb)
1375                                              * sizeof (char *));
1376               memcpy (stackx, stackb, (stacke - stackb) * sizeof (char *));
1377               stackp = stackx + (stackp - stackb);
1378               stacke = stackx + 2 * (stacke - stackb);
1379               stackb = stackx;
1380             }
1381           *stackp++ = 0;
1382           *stackp++ = 0;
1383           goto nofinalize;
1384
1385         case wordbound:
1386           if (d == string1  /* Points to first char */
1387               || d == end2  /* Points to end */
1388               || (d == end1 && size2 == 0)) /* Points to end */
1389             break;
1390           if ((SYNTAX (d[-1]) == Sword)
1391               != (SYNTAX (d == end1 ? *string2 : *d) == Sword))
1392             break;
1393           goto fail;
1394
1395         case notwordbound:
1396           if (d == string1  /* Points to first char */
1397               || d == end2  /* Points to end */
1398               || (d == end1 && size2 == 0)) /* Points to end */
1399             goto fail;
1400           if ((SYNTAX (d[-1]) == Sword)
1401               != (SYNTAX (d == end1 ? *string2 : *d) == Sword))
1402             goto fail;
1403           break;
1404
1405         case wordbeg:
1406           if (d == end2  /* Points to end */
1407               || (d == end1 && size2 == 0) /* Points to end */
1408               || SYNTAX (* (d == end1 ? string2 : d)) != Sword) /* Next char not a letter */
1409             goto fail;
1410           if (d == string1  /* Points to first char */
1411               || SYNTAX (d[-1]) != Sword)  /* prev char not letter */
1412             break;
1413           goto fail;
1414
1415         case wordend:
1416           if (d == string1  /* Points to first char */
1417               || SYNTAX (d[-1]) != Sword)  /* prev char not letter */
1418             goto fail;
1419           if (d == end2  /* Points to end */
1420               || (d == end1 && size2 == 0) /* Points to end */
1421               || SYNTAX (d == end1 ? *string2 : *d) != Sword) /* Next char not a letter */
1422             break;
1423           goto fail;
1424
1425 #ifdef emacs
1426         case before_dot:
1427           if (((d - string2 <= (unsigned) size2)
1428                ? d - bf_p2 : d - bf_p1)
1429               <= point)
1430             goto fail;
1431           break;
1432
1433         case at_dot:
1434           if (((d - string2 <= (unsigned) size2)
1435                ? d - bf_p2 : d - bf_p1)
1436               == point)
1437             goto fail;
1438           break;
1439
1440         case after_dot:
1441           if (((d - string2 <= (unsigned) size2)
1442                ? d - bf_p2 : d - bf_p1)
1443               >= point)
1444             goto fail;
1445           break;
1446
1447         case wordchar:
1448           mcnt = (int) Sword;
1449           goto matchsyntax;
1450
1451         case syntaxspec:
1452           mcnt = *p++;
1453         matchsyntax:
1454           PREFETCH;
1455           if (SYNTAX (*d++) != (enum syntaxcode) mcnt) goto fail;
1456           break;
1457
1458         case notwordchar:
1459           mcnt = (int) Sword;
1460           goto matchnotsyntax;
1461
1462         case notsyntaxspec:
1463           mcnt = *p++;
1464         matchnotsyntax:
1465           PREFETCH;
1466           if (SYNTAX (*d++) == (enum syntaxcode) mcnt) goto fail;
1467           break;
1468 #else
1469         case wordchar:
1470           PREFETCH;
1471           if (SYNTAX (*d++) == 0) goto fail;
1472           break;
1473
1474         case notwordchar:
1475           PREFETCH;
1476           if (SYNTAX (*d++) != 0) goto fail;
1477           break;
1478 #endif /* not emacs */
1479
1480         case begbuf:
1481           if (d == string1)     /* Note, d cannot equal string2 */
1482             break;              /* unless string1 == string2.  */
1483           goto fail;
1484
1485         case endbuf:
1486           if (d == end2 || (d == end1 && size2 == 0))
1487             break;
1488           goto fail;
1489
1490         case exactn:
1491           /* Match the next few pattern characters exactly.
1492              mcnt is how many characters to match. */
1493           mcnt = *p++;
1494           if (translate)
1495             {
1496               do
1497                 {
1498                   PREFETCH;
1499                   if (translate[*d++] != *p++) goto fail;
1500                 }
1501               while (--mcnt);
1502             }
1503           else
1504             {
1505               do
1506                 {
1507                   PREFETCH;
1508                   if (*d++ != *p++) goto fail;
1509                 }
1510               while (--mcnt);
1511             }
1512           break;
1513         }
1514       continue;    /* Successfully matched one pattern command; keep matching */
1515
1516       /* Jump here if any matching operation fails. */
1517     fail:
1518       if (stackp != stackb)
1519         /* A restart point is known.  Restart there and pop it. */
1520         {
1521           if (!stackp[-2])
1522             {   /* If innermost failure point is dormant, flush it and keep looking */
1523               stackp -= 2;
1524               goto fail;
1525             }
1526           d = *--stackp;
1527           p = *--stackp;
1528           if (d >= string1 && d <= end1)
1529             dend = end_match_1;
1530         }
1531       else break;   /* Matching at this starting point really fails! */
1532     }
1533   return -1;         /* Failure to match */
1534 }
1535
1536 static int
1537 memcmp_translate (s1, s2, len, translate)
1538      unsigned char *s1, *s2;
1539      register int len;
1540      unsigned char *translate;
1541 {
1542   register unsigned char *p1 = s1, *p2 = s2;
1543   while (len)
1544     {
1545       if (translate [*p1++] != translate [*p2++]) return 1;
1546       len--;
1547     }
1548   return 0;
1549 }
1550 \f
1551 /* Entry points compatible with bsd4.2 regex library */
1552
1553 #ifndef emacs
1554
1555 static struct re_pattern_buffer re_comp_buf;
1556
1557 char *
1558 re_comp (s)
1559      char *s;
1560 {
1561   if (!s)
1562     {
1563       if (!re_comp_buf.buffer)
1564         return "No previous regular expression";
1565       return 0;
1566     }
1567
1568   if (!re_comp_buf.buffer)
1569     {
1570       if (!(re_comp_buf.buffer = (char *) malloc (200)))
1571         return "Memory exhausted";
1572       re_comp_buf.allocated = 200;
1573       if (!(re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH)))
1574         return "Memory exhausted";
1575     }
1576   return re_compile_pattern (s, strlen (s), &re_comp_buf);
1577 }
1578
1579 int
1580 re_exec (s)
1581      char *s;
1582 {
1583   int len = strlen (s);
1584   return 0 <= re_search (&re_comp_buf, s, len, 0, len, 0);
1585 }
1586
1587 #endif /* emacs */
1588 \f
1589 #ifdef test
1590
1591 #include <stdio.h>
1592
1593 /* Indexed by a character, gives the upper case equivalent of the character */
1594
1595 static char upcase[0400] =
1596   { 000, 001, 002, 003, 004, 005, 006, 007,
1597     010, 011, 012, 013, 014, 015, 016, 017,
1598     020, 021, 022, 023, 024, 025, 026, 027,
1599     030, 031, 032, 033, 034, 035, 036, 037,
1600     040, 041, 042, 043, 044, 045, 046, 047,
1601     050, 051, 052, 053, 054, 055, 056, 057,
1602     060, 061, 062, 063, 064, 065, 066, 067,
1603     070, 071, 072, 073, 074, 075, 076, 077,
1604     0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
1605     0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
1606     0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
1607     0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137,
1608     0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
1609     0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
1610     0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
1611     0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177,
1612     0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207,
1613     0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217,
1614     0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227,
1615     0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237,
1616     0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247,
1617     0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257,
1618     0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267,
1619     0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277,
1620     0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307,
1621     0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317,
1622     0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327,
1623     0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337,
1624     0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347,
1625     0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357,
1626     0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367,
1627     0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377
1628   };
1629
1630 main (argc, argv)
1631      int argc;
1632      char **argv;
1633 {
1634   char pat[80];
1635   struct re_pattern_buffer buf;
1636   int i;
1637   char c;
1638   char fastmap[(1 << BYTEWIDTH)];
1639
1640   /* Allow a command argument to specify the style of syntax.  */
1641   if (argc > 1)
1642     obscure_syntax = atoi (argv[1]);
1643
1644   buf.allocated = 40;
1645   buf.buffer = (char *) malloc (buf.allocated);
1646   buf.fastmap = fastmap;
1647   buf.translate = upcase;
1648
1649   while (1)
1650     {
1651       gets (pat);
1652
1653       if (*pat)
1654         {
1655           re_compile_pattern (pat, strlen(pat), &buf);
1656
1657           for (i = 0; i < buf.used; i++)
1658             printchar (buf.buffer[i]);
1659
1660           putchar ('\n');
1661
1662           printf ("%d allocated, %d used.\n", buf.allocated, buf.used);
1663
1664           re_compile_fastmap (&buf);
1665           printf ("Allowed by fastmap: ");
1666           for (i = 0; i < (1 << BYTEWIDTH); i++)
1667             if (fastmap[i]) printchar (i);
1668           putchar ('\n');
1669         }
1670
1671       gets (pat);       /* Now read the string to match against */
1672
1673       i = re_match (&buf, pat, strlen (pat), 0, 0);
1674       printf ("Match value %d.\n", i);
1675     }
1676 }
1677
1678 #ifdef NOTDEF
1679 print_buf (bufp)
1680      struct re_pattern_buffer *bufp;
1681 {
1682   int i;
1683
1684   printf ("buf is :\n----------------\n");
1685   for (i = 0; i < bufp->used; i++)
1686     printchar (bufp->buffer[i]);
1687
1688   printf ("\n%d allocated, %d used.\n", bufp->allocated, bufp->used);
1689
1690   printf ("Allowed by fastmap: ");
1691   for (i = 0; i < (1 << BYTEWIDTH); i++)
1692     if (bufp->fastmap[i])
1693       printchar (i);
1694   printf ("\nAllowed by translate: ");
1695   if (bufp->translate)
1696     for (i = 0; i < (1 << BYTEWIDTH); i++)
1697       if (bufp->translate[i])
1698         printchar (i);
1699   printf ("\nfastmap is%s accurate\n", bufp->fastmap_accurate ? "" : "n't");
1700   printf ("can %s be null\n----------", bufp->can_be_null ? "" : "not");
1701 }
1702 #endif
1703
1704 printchar (c)
1705      char c;
1706 {
1707   if (c < 041 || c >= 0177)
1708     {
1709       putchar ('\\');
1710       putchar (((c >> 6) & 3) + '0');
1711       putchar (((c >> 3) & 7) + '0');
1712       putchar ((c & 7) + '0');
1713     }
1714   else
1715     putchar (c);
1716 }
1717
1718 error (string)
1719      char *string;
1720 {
1721   puts (string);
1722   exit (1);
1723 }
1724
1725 #endif /* test */