posix/regex.c

   1 /* Extended regular expression matching and search library,
   2    version 0.12.
   3    (Implements POSIX draft P1003.2/D11.2, except for some of the
   4    internationalization features.)
   5
   6    Copyright (C) 1993, 1994, 1995, 1996, 1997 Free Software Foundation, Inc.
   7
   8    This file is part of the GNU C Library.  Its master source is NOT part of
   9    the C library, however.  The master source lives in /gd/gnu/lib.
  10
  11    The GNU C Library is free software; you can redistribute it and/or
  12    modify it under the terms of the GNU Library General Public License as
  13    published by the Free Software Foundation; either version 2 of the
  14    License, or (at your option) any later version.
  15
  16    The GNU C Library is distributed in the hope that it will be useful,
  17    but WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19    Library General Public License for more details.
  20
  21    You should have received a copy of the GNU Library General Public
  22    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  23    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  24    Boston, MA 02111-1307, USA.  */
  25
  26 /* AIX requires this to be the first thing in the file. */
  27 #if defined (_AIX) && !defined (REGEX_MALLOC)
  28   #pragma alloca
  29 #endif
  30
  31 #undef  _GNU_SOURCE
  32 #define _GNU_SOURCE
  33
  34 #ifdef HAVE_CONFIG_H
  35 #include <config.h>
  36 #endif
  37
  38 #if defined(STDC_HEADERS) && !defined(emacs)
  39 #include <stddef.h>
  40 #else
  41 /* We need this for `regex.h', and perhaps for the Emacs include files.  */
  42 #include <sys/types.h>
  43 #endif
  44
  45 /* For platform which support the ISO C amendement 1 functionality we
  46    support user defined character classes.  */
  47 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
  48 # include <wctype.h>
  49 # include <wchar.h>
  50 #endif
  51
  52 /* This is for other GNU distributions with internationalized messages.  */
  53 #if HAVE_LIBINTL_H || defined (_LIBC)
  54 # include <libintl.h>
  55 #else
  56 # define gettext(msgid) (msgid)
  57 #endif
  58
  59 #ifndef gettext_noop
  60 /* This define is so xgettext can find the internationalizable
  61    strings.  */
  62 #define gettext_noop(String) String
  63 #endif
  64
  65 /* The `emacs' switch turns on certain matching commands
  66    that make sense only in Emacs. */
  67 #ifdef emacs
  68
  69 #include "lisp.h"
  70 #include "buffer.h"
  71 #include "syntax.h"
  72
  73 #else  /* not emacs */
  74
  75 /* If we are not linking with Emacs proper,
  76    we can't use the relocating allocator
  77    even if config.h says that we can.  */
  78 #undef REL_ALLOC
  79
  80 #if defined (STDC_HEADERS) || defined (_LIBC)
  81 #include <stdlib.h>
  82 #else
  83 char *malloc ();
  84 char *realloc ();
  85 #endif
  86
  87 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
  88    If nothing else has been done, use the method below.  */
  89 #ifdef INHIBIT_STRING_HEADER
  90 #if !(defined (HAVE_BZERO) && defined (HAVE_BCOPY))
  91 #if !defined (bzero) && !defined (bcopy)
  92 #undef INHIBIT_STRING_HEADER
  93 #endif
  94 #endif
  95 #endif
  96
  97 /* This is the normal way of making sure we have a bcopy and a bzero.
  98    This is used in most programs--a few other programs avoid this
  99    by defining INHIBIT_STRING_HEADER.  */
 100 #ifndef INHIBIT_STRING_HEADER
 101 #if defined (HAVE_STRING_H) || defined (STDC_HEADERS) || defined (_LIBC)
 102 #include <string.h>
 103 #ifndef bcmp
 104 #define bcmp(s1, s2, n) memcmp ((s1), (s2), (n))
 105 #endif
 106 #ifndef bcopy
 107 #define bcopy(s, d, n)  memcpy ((d), (s), (n))
 108 #endif
 109 #ifndef bzero
 110 #define bzero(s, n)     memset ((s), 0, (n))
 111 #endif
 112 #else
 113 #include <strings.h>
 114 #endif
 115 #endif
 116
 117 /* Define the syntax stuff for \<, \>, etc.  */
 118
 119 /* This must be nonzero for the wordchar and notwordchar pattern
 120    commands in re_match_2.  */
 121 #ifndef Sword
 122 #define Sword 1
 123 #endif
 124
 125 #ifdef SWITCH_ENUM_BUG
 126 #define SWITCH_ENUM_CAST(x) ((int)(x))
 127 #else
 128 #define SWITCH_ENUM_CAST(x) (x)
 129 #endif
 130
 131 #ifdef SYNTAX_TABLE
 132
 133 extern char *re_syntax_table;
 134
 135 #else /* not SYNTAX_TABLE */
 136
 137 /* How many characters in the character set.  */
 138 #define CHAR_SET_SIZE 256
 139
 140 static char re_syntax_table[CHAR_SET_SIZE];
 141
 142 static void
 143 init_syntax_once ()
 144 {
 145    register int c;
 146    static int done = 0;
 147
 148    if (done)
 149      return;
 150
 151    bzero (re_syntax_table, sizeof re_syntax_table);
 152
 153    for (c = 'a'; c <= 'z'; c++)
 154      re_syntax_table[c] = Sword;
 155
 156    for (c = 'A'; c <= 'Z'; c++)
 157      re_syntax_table[c] = Sword;
 158
 159    for (c = '0'; c <= '9'; c++)
 160      re_syntax_table[c] = Sword;
 161
 162    re_syntax_table['_'] = Sword;
 163
 164    done = 1;
 165 }
 166
 167 #endif /* not SYNTAX_TABLE */
 168
 169 #define SYNTAX(c) re_syntax_table[c]
 170
 171 #endif /* not emacs */
 172 \f
 173 /* Get the interface, including the syntax bits.  */
 174 #include "regex.h"
 175
 176 /* isalpha etc. are used for the character classes.  */
 177 #include <ctype.h>
 178
 179 /* Jim Meyering writes:
 180
 181    "... Some ctype macros are valid only for character codes that
 182    isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
 183    using /bin/cc or gcc but without giving an ansi option).  So, all
 184    ctype uses should be through macros like ISPRINT...  If
 185    STDC_HEADERS is defined, then autoconf has verified that the ctype
 186    macros don't need to be guarded with references to isascii. ...
 187    Defining isascii to 1 should let any compiler worth its salt
 188    eliminate the && through constant folding."  */
 189
 190 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII))
 191 #define ISASCII(c) 1
 192 #else
 193 #define ISASCII(c) isascii(c)
 194 #endif
 195
 196 #ifdef isblank
 197 #define ISBLANK(c) (ISASCII (c) && isblank (c))
 198 #else
 199 #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
 200 #endif
 201 #ifdef isgraph
 202 #define ISGRAPH(c) (ISASCII (c) && isgraph (c))
 203 #else
 204 #define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
 205 #endif
 206
 207 #define ISPRINT(c) (ISASCII (c) && isprint (c))
 208 #define ISDIGIT(c) (ISASCII (c) && isdigit (c))
 209 #define ISALNUM(c) (ISASCII (c) && isalnum (c))
 210 #define ISALPHA(c) (ISASCII (c) && isalpha (c))
 211 #define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
 212 #define ISLOWER(c) (ISASCII (c) && islower (c))
 213 #define ISPUNCT(c) (ISASCII (c) && ispunct (c))
 214 #define ISSPACE(c) (ISASCII (c) && isspace (c))
 215 #define ISUPPER(c) (ISASCII (c) && isupper (c))
 216 #define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
 217
 218 #ifndef NULL
 219 #define NULL (void *)0
 220 #endif
 221
 222 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
 223    since ours (we hope) works properly with all combinations of
 224    machines, compilers, `char' and `unsigned char' argument types.
 225    (Per Bothner suggested the basic approach.)  */
 226 #undef SIGN_EXTEND_CHAR
 227 #if __STDC__
 228 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
 229 #else  /* not __STDC__ */
 230 /* As in Harbison and Steele.  */
 231 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
 232 #endif
 233 \f
 234 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
 235    use `alloca' instead of `malloc'.  This is because using malloc in
 236    re_search* or re_match* could cause memory leaks when C-g is used in
 237    Emacs; also, malloc is slower and causes storage fragmentation.  On
 238    the other hand, malloc is more portable, and easier to debug.
 239
 240    Because we sometimes use alloca, some routines have to be macros,
 241    not functions -- `alloca'-allocated space disappears at the end of the
 242    function it is called in.  */
 243
 244 #ifdef REGEX_MALLOC
 245
 246 #define REGEX_ALLOCATE malloc
 247 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
 248 #define REGEX_FREE free
 249
 250 #else /* not REGEX_MALLOC  */
 251
 252 /* Emacs already defines alloca, sometimes.  */
 253 #ifndef alloca
 254
 255 /* Make alloca work the best possible way.  */
 256 #ifdef __GNUC__
 257 #define alloca __builtin_alloca
 258 #else /* not __GNUC__ */
 259 #if HAVE_ALLOCA_H
 260 #include <alloca.h>
 261 #else /* not __GNUC__ or HAVE_ALLOCA_H */
 262 #if 0 /* It is a bad idea to declare alloca.  We always cast the result.  */
 263 #ifndef _AIX /* Already did AIX, up at the top.  */
 264 char *alloca ();
 265 #endif /* not _AIX */
 266 #endif
 267 #endif /* not HAVE_ALLOCA_H */
 268 #endif /* not __GNUC__ */
 269
 270 #endif /* not alloca */
 271
 272 #define REGEX_ALLOCATE alloca
 273
 274 /* Assumes a `char *destination' variable.  */
 275 #define REGEX_REALLOCATE(source, osize, nsize)                          \
 276   (destination = (char *) alloca (nsize),                               \
 277    bcopy (source, destination, osize),                                  \
 278    destination)
 279
 280 /* No need to do anything to free, after alloca.  */
 281 #define REGEX_FREE(arg) ((void)0) /* Do nothing!  But inhibit gcc warning.  */
 282
 283 #endif /* not REGEX_MALLOC */
 284
 285 /* Define how to allocate the failure stack.  */
 286
 287 #if defined (REL_ALLOC) && defined (REGEX_MALLOC)
 288
 289 #define REGEX_ALLOCATE_STACK(size)                              \
 290   r_alloc (&failure_stack_ptr, (size))
 291 #define REGEX_REALLOCATE_STACK(source, osize, nsize)            \
 292   r_re_alloc (&failure_stack_ptr, (nsize))
 293 #define REGEX_FREE_STACK(ptr)                                   \
 294   r_alloc_free (&failure_stack_ptr)
 295
 296 #else /* not using relocating allocator */
 297
 298 #ifdef REGEX_MALLOC
 299
 300 #define REGEX_ALLOCATE_STACK malloc
 301 #define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
 302 #define REGEX_FREE_STACK free
 303
 304 #else /* not REGEX_MALLOC */
 305
 306 #define REGEX_ALLOCATE_STACK alloca
 307
 308 #define REGEX_REALLOCATE_STACK(source, osize, nsize)                    \
 309    REGEX_REALLOCATE (source, osize, nsize)
 310 /* No need to explicitly free anything.  */
 311 #define REGEX_FREE_STACK(arg)
 312
 313 #endif /* not REGEX_MALLOC */
 314 #endif /* not using relocating allocator */
 315
 316
 317 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
 318    `string1' or just past its end.  This works if PTR is NULL, which is
 319    a good thing.  */
 320 #define FIRST_STRING_P(ptr)                                     \
 321   (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
 322
 323 /* (Re)Allocate N items of type T using malloc, or fail.  */
 324 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
 325 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
 326 #define RETALLOC_IF(addr, n, t) \
 327   if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
 328 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
 329
 330 #define BYTEWIDTH 8 /* In bits.  */
 331
 332 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
 333
 334 #undef MAX
 335 #undef MIN
 336 #define MAX(a, b) ((a) > (b) ? (a) : (b))
 337 #define MIN(a, b) ((a) < (b) ? (a) : (b))
 338
 339 typedef char boolean;
 340 #define false 0
 341 #define true 1
 342
 343 static int re_match_2_internal ();
 344 \f
 345 /* These are the command codes that appear in compiled regular
 346    expressions.  Some opcodes are followed by argument bytes.  A
 347    command code can specify any interpretation whatsoever for its
 348    arguments.  Zero bytes may appear in the compiled regular expression.  */
 349
 350 typedef enum
 351 {
 352   no_op = 0,
 353
 354   /* Succeed right away--no more backtracking.  */
 355   succeed,
 356
 357         /* Followed by one byte giving n, then by n literal bytes.  */
 358   exactn,
 359
 360         /* Matches any (more or less) character.  */
 361   anychar,
 362
 363         /* Matches any one char belonging to specified set.  First
 364            following byte is number of bitmap bytes.  Then come bytes
 365            for a bitmap saying which chars are in.  Bits in each byte
 366            are ordered low-bit-first.  A character is in the set if its
 367            bit is 1.  A character too large to have a bit in the map is
 368            automatically not in the set.  */
 369   charset,
 370
 371         /* Same parameters as charset, but match any character that is
 372            not one of those specified.  */
 373   charset_not,
 374
 375         /* Start remembering the text that is matched, for storing in a
 376            register.  Followed by one byte with the register number, in
 377            the range 0 to one less than the pattern buffer's re_nsub
 378            field.  Then followed by one byte with the number of groups
 379            inner to this one.  (This last has to be part of the
 380            start_memory only because we need it in the on_failure_jump
 381            of re_match_2.)  */
 382   start_memory,
 383
 384         /* Stop remembering the text that is matched and store it in a
 385            memory register.  Followed by one byte with the register
 386            number, in the range 0 to one less than `re_nsub' in the
 387            pattern buffer, and one byte with the number of inner groups,
 388            just like `start_memory'.  (We need the number of inner
 389            groups here because we don't have any easy way of finding the
 390            corresponding start_memory when we're at a stop_memory.)  */
 391   stop_memory,
 392
 393         /* Match a duplicate of something remembered. Followed by one
 394            byte containing the register number.  */
 395   duplicate,
 396
 397         /* Fail unless at beginning of line.  */
 398   begline,
 399
 400         /* Fail unless at end of line.  */
 401   endline,
 402
 403         /* Succeeds if at beginning of buffer (if emacs) or at beginning
 404            of string to be matched (if not).  */
 405   begbuf,
 406
 407         /* Analogously, for end of buffer/string.  */
 408   endbuf,
 409
 410         /* Followed by two byte relative address to which to jump.  */
 411   jump,
 412
 413         /* Same as jump, but marks the end of an alternative.  */
 414   jump_past_alt,
 415
 416         /* Followed by two-byte relative address of place to resume at
 417            in case of failure.  */
 418   on_failure_jump,
 419
 420         /* Like on_failure_jump, but pushes a placeholder instead of the
 421            current string position when executed.  */
 422   on_failure_keep_string_jump,
 423
 424         /* Throw away latest failure point and then jump to following
 425            two-byte relative address.  */
 426   pop_failure_jump,
 427
 428         /* Change to pop_failure_jump if know won't have to backtrack to
 429            match; otherwise change to jump.  This is used to jump
 430            back to the beginning of a repeat.  If what follows this jump
 431            clearly won't match what the repeat does, such that we can be
 432            sure that there is no use backtracking out of repetitions
 433            already matched, then we change it to a pop_failure_jump.
 434            Followed by two-byte address.  */
 435   maybe_pop_jump,
 436
 437         /* Jump to following two-byte address, and push a dummy failure
 438            point. This failure point will be thrown away if an attempt
 439            is made to use it for a failure.  A `+' construct makes this
 440            before the first repeat.  Also used as an intermediary kind
 441            of jump when compiling an alternative.  */
 442   dummy_failure_jump,
 443
 444         /* Push a dummy failure point and continue.  Used at the end of
 445            alternatives.  */
 446   push_dummy_failure,
 447
 448         /* Followed by two-byte relative address and two-byte number n.
 449            After matching N times, jump to the address upon failure.  */
 450   succeed_n,
 451
 452         /* Followed by two-byte relative address, and two-byte number n.
 453            Jump to the address N times, then fail.  */
 454   jump_n,
 455
 456         /* Set the following two-byte relative address to the
 457            subsequent two-byte number.  The address *includes* the two
 458            bytes of number.  */
 459   set_number_at,
 460
 461   wordchar,     /* Matches any word-constituent character.  */
 462   notwordchar,  /* Matches any char that is not a word-constituent.  */
 463
 464   wordbeg,      /* Succeeds if at word beginning.  */
 465   wordend,      /* Succeeds if at word end.  */
 466
 467   wordbound,    /* Succeeds if at a word boundary.  */
 468   notwordbound  /* Succeeds if not at a word boundary.  */
 469
 470 #ifdef emacs
 471   ,before_dot,  /* Succeeds if before point.  */
 472   at_dot,       /* Succeeds if at point.  */
 473   after_dot,    /* Succeeds if after point.  */
 474
 475         /* Matches any character whose syntax is specified.  Followed by
 476            a byte which contains a syntax code, e.g., Sword.  */
 477   syntaxspec,
 478
 479         /* Matches any character whose syntax is not that specified.  */
 480   notsyntaxspec
 481 #endif /* emacs */
 482 } re_opcode_t;
 483 \f
 484 /* Common operations on the compiled pattern.  */
 485
 486 /* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
 487
 488 #define STORE_NUMBER(destination, number)                               \
 489   do {                                                                  \
 490     (destination)[0] = (number) & 0377;                                 \
 491     (destination)[1] = (number) >> 8;                                   \
 492   } while (0)
 493
 494 /* Same as STORE_NUMBER, except increment DESTINATION to
 495    the byte after where the number is stored.  Therefore, DESTINATION
 496    must be an lvalue.  */
 497
 498 #define STORE_NUMBER_AND_INCR(destination, number)                      \
 499   do {                                                                  \
 500     STORE_NUMBER (destination, number);                                 \
 501     (destination) += 2;                                                 \
 502   } while (0)
 503
 504 /* Put into DESTINATION a number stored in two contiguous bytes starting
 505    at SOURCE.  */
 506
 507 #define EXTRACT_NUMBER(destination, source)                             \
 508   do {                                                                  \
 509     (destination) = *(source) & 0377;                                   \
 510     (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8;           \
 511   } while (0)
 512
 513 #ifdef DEBUG
 514 static void extract_number _RE_ARGS ((int *dest, unsigned char *source));
 515 static void
 516 extract_number (dest, source)
 517     int *dest;
 518     unsigned char *source;
 519 {
 520   int temp = SIGN_EXTEND_CHAR (*(source + 1));
 521   *dest = *source & 0377;
 522   *dest += temp << 8;
 523 }
 524
 525 #ifndef EXTRACT_MACROS /* To debug the macros.  */
 526 #undef EXTRACT_NUMBER
 527 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
 528 #endif /* not EXTRACT_MACROS */
 529
 530 #endif /* DEBUG */
 531
 532 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
 533    SOURCE must be an lvalue.  */
 534
 535 #define EXTRACT_NUMBER_AND_INCR(destination, source)                    \
 536   do {                                                                  \
 537     EXTRACT_NUMBER (destination, source);                               \
 538     (source) += 2;                                                      \
 539   } while (0)
 540
 541 #ifdef DEBUG
 542 static void extract_number_and_incr _RE_ARGS ((int *destination,
 543                                                unsigned char **source));
 544 static void
 545 extract_number_and_incr (destination, source)
 546     int *destination;
 547     unsigned char **source;
 548 {
 549   extract_number (destination, *source);
 550   *source += 2;
 551 }
 552
 553 #ifndef EXTRACT_MACROS
 554 #undef EXTRACT_NUMBER_AND_INCR
 555 #define EXTRACT_NUMBER_AND_INCR(dest, src) \
 556   extract_number_and_incr (&dest, &src)
 557 #endif /* not EXTRACT_MACROS */
 558
 559 #endif /* DEBUG */
 560 \f
 561 /* If DEBUG is defined, Regex prints many voluminous messages about what
 562    it is doing (if the variable `debug' is nonzero).  If linked with the
 563    main program in `iregex.c', you can enter patterns and strings
 564    interactively.  And if linked with the main program in `main.c' and
 565    the other test files, you can run the already-written tests.  */
 566
 567 #ifdef DEBUG
 568
 569 /* We use standard I/O for debugging.  */
 570 #include <stdio.h>
 571
 572 /* It is useful to test things that ``must'' be true when debugging.  */
 573 #include <assert.h>
 574
 575 static int debug = 0;
 576
 577 #define DEBUG_STATEMENT(e) e
 578 #define DEBUG_PRINT1(x) if (debug) printf (x)
 579 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
 580 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
 581 #define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
 582 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)                           \
 583   if (debug) print_partial_compiled_pattern (s, e)
 584 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)                  \
 585   if (debug) print_double_string (w, s1, sz1, s2, sz2)
 586
 587
 588 /* Print the fastmap in human-readable form.  */
 589
 590 void
 591 print_fastmap (fastmap)
 592     char *fastmap;
 593 {
 594   unsigned was_a_range = 0;
 595   unsigned i = 0;
 596
 597   while (i < (1 << BYTEWIDTH))
 598     {
 599       if (fastmap[i++])
 600         {
 601           was_a_range = 0;
 602           putchar (i - 1);
 603           while (i < (1 << BYTEWIDTH)  &&  fastmap[i])
 604             {
 605               was_a_range = 1;
 606               i++;
 607             }
 608           if (was_a_range)
 609             {
 610               printf ("-");
 611               putchar (i - 1);
 612             }
 613         }
 614     }
 615   putchar ('\n');
 616 }
 617
 618
 619 /* Print a compiled pattern string in human-readable form, starting at
 620    the START pointer into it and ending just before the pointer END.  */
 621
 622 void
 623 print_partial_compiled_pattern (start, end)
 624     unsigned char *start;
 625     unsigned char *end;
 626 {
 627   int mcnt, mcnt2;
 628   unsigned char *p1;
 629   unsigned char *p = start;
 630   unsigned char *pend = end;
 631
 632   if (start == NULL)
 633     {
 634       printf ("(null)\n");
 635       return;
 636     }
 637
 638   /* Loop over pattern commands.  */
 639   while (p < pend)
 640     {
 641       printf ("%d:\t", p - start);
 642
 643       switch ((re_opcode_t) *p++)
 644         {
 645         case no_op:
 646           printf ("/no_op");
 647           break;
 648
 649         case exactn:
 650           mcnt = *p++;
 651           printf ("/exactn/%d", mcnt);
 652           do
 653             {
 654               putchar ('/');
 655               putchar (*p++);
 656             }
 657           while (--mcnt);
 658           break;
 659
 660         case start_memory:
 661           mcnt = *p++;
 662           printf ("/start_memory/%d/%d", mcnt, *p++);
 663           break;
 664
 665         case stop_memory:
 666           mcnt = *p++;
 667           printf ("/stop_memory/%d/%d", mcnt, *p++);
 668           break;
 669
 670         case duplicate:
 671           printf ("/duplicate/%d", *p++);
 672           break;
 673
 674         case anychar:
 675           printf ("/anychar");
 676           break;
 677
 678         case charset:
 679         case charset_not:
 680           {
 681             register int c, last = -100;
 682             register int in_range = 0;
 683
 684             printf ("/charset [%s",
 685                     (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
 686
 687             assert (p + *p < pend);
 688
 689             for (c = 0; c < 256; c++)
 690               if (c / 8 < *p
 691                   && (p[1 + (c/8)] & (1 << (c % 8))))
 692                 {
 693                   /* Are we starting a range?  */
 694                   if (last + 1 == c && ! in_range)
 695                     {
 696                       putchar ('-');
 697                       in_range = 1;
 698                     }
 699                   /* Have we broken a range?  */
 700                   else if (last + 1 != c && in_range)
 701               {
 702                       putchar (last);
 703                       in_range = 0;
 704                     }
 705
 706                   if (! in_range)
 707                     putchar (c);
 708
 709                   last = c;
 710               }
 711
 712             if (in_range)
 713               putchar (last);
 714
 715             putchar (']');
 716
 717             p += 1 + *p;
 718           }
 719           break;
 720
 721         case begline:
 722           printf ("/begline");
 723           break;
 724
 725         case endline:
 726           printf ("/endline");
 727           break;
 728
 729         case on_failure_jump:
 730           extract_number_and_incr (&mcnt, &p);
 731           printf ("/on_failure_jump to %d", p + mcnt - start);
 732           break;
 733
 734         case on_failure_keep_string_jump:
 735           extract_number_and_incr (&mcnt, &p);
 736           printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
 737           break;
 738
 739         case dummy_failure_jump:
 740           extract_number_and_incr (&mcnt, &p);
 741           printf ("/dummy_failure_jump to %d", p + mcnt - start);
 742           break;
 743
 744         case push_dummy_failure:
 745           printf ("/push_dummy_failure");
 746           break;
 747
 748         case maybe_pop_jump:
 749           extract_number_and_incr (&mcnt, &p);
 750           printf ("/maybe_pop_jump to %d", p + mcnt - start);
 751           break;
 752
 753         case pop_failure_jump:
 754           extract_number_and_incr (&mcnt, &p);
 755           printf ("/pop_failure_jump to %d", p + mcnt - start);
 756           break;
 757
 758         case jump_past_alt:
 759           extract_number_and_incr (&mcnt, &p);
 760           printf ("/jump_past_alt to %d", p + mcnt - start);
 761           break;
 762
 763         case jump:
 764           extract_number_and_incr (&mcnt, &p);
 765           printf ("/jump to %d", p + mcnt - start);
 766           break;
 767
 768         case succeed_n:
 769           extract_number_and_incr (&mcnt, &p);
 770           p1 = p + mcnt;
 771           extract_number_and_incr (&mcnt2, &p);
 772           printf ("/succeed_n to %d, %d times", p1 - start, mcnt2);
 773           break;
 774
 775         case jump_n:
 776           extract_number_and_incr (&mcnt, &p);
 777           p1 = p + mcnt;
 778           extract_number_and_incr (&mcnt2, &p);
 779           printf ("/jump_n to %d, %d times", p1 - start, mcnt2);
 780           break;
 781
 782         case set_number_at:
 783           extract_number_and_incr (&mcnt, &p);
 784           p1 = p + mcnt;
 785           extract_number_and_incr (&mcnt2, &p);
 786           printf ("/set_number_at location %d to %d", p1 - start, mcnt2);
 787           break;
 788
 789         case wordbound:
 790           printf ("/wordbound");
 791           break;
 792
 793         case notwordbound:
 794           printf ("/notwordbound");
 795           break;
 796
 797         case wordbeg:
 798           printf ("/wordbeg");
 799           break;
 800
 801         case wordend:
 802           printf ("/wordend");
 803
 804 #ifdef emacs
 805         case before_dot:
 806           printf ("/before_dot");
 807           break;
 808
 809         case at_dot:
 810           printf ("/at_dot");
 811           break;
 812
 813         case after_dot:
 814           printf ("/after_dot");
 815           break;
 816
 817         case syntaxspec:
 818           printf ("/syntaxspec");
 819           mcnt = *p++;
 820           printf ("/%d", mcnt);
 821           break;
 822
 823         case notsyntaxspec:
 824           printf ("/notsyntaxspec");
 825           mcnt = *p++;
 826           printf ("/%d", mcnt);
 827           break;
 828 #endif /* emacs */
 829
 830         case wordchar:
 831           printf ("/wordchar");
 832           break;
 833
 834         case notwordchar:
 835           printf ("/notwordchar");
 836           break;
 837
 838         case begbuf:
 839           printf ("/begbuf");
 840           break;
 841
 842         case endbuf:
 843           printf ("/endbuf");
 844           break;
 845
 846         default:
 847           printf ("?%d", *(p-1));
 848         }
 849
 850       putchar ('\n');
 851     }
 852
 853   printf ("%d:\tend of pattern.\n", p - start);
 854 }
 855
 856
 857 void
 858 print_compiled_pattern (bufp)
 859     struct re_pattern_buffer *bufp;
 860 {
 861   unsigned char *buffer = bufp->buffer;
 862
 863   print_partial_compiled_pattern (buffer, buffer + bufp->used);
 864   printf ("%ld bytes used/%ld bytes allocated.\n",
 865           bufp->used, bufp->allocated);
 866
 867   if (bufp->fastmap_accurate && bufp->fastmap)
 868     {
 869       printf ("fastmap: ");
 870       print_fastmap (bufp->fastmap);
 871     }
 872
 873   printf ("re_nsub: %d\t", bufp->re_nsub);
 874   printf ("regs_alloc: %d\t", bufp->regs_allocated);
 875   printf ("can_be_null: %d\t", bufp->can_be_null);
 876   printf ("newline_anchor: %d\n", bufp->newline_anchor);
 877   printf ("no_sub: %d\t", bufp->no_sub);
 878   printf ("not_bol: %d\t", bufp->not_bol);
 879   printf ("not_eol: %d\t", bufp->not_eol);
 880   printf ("syntax: %lx\n", bufp->syntax);
 881   /* Perhaps we should print the translate table?  */
 882 }
 883
 884
 885 void
 886 print_double_string (where, string1, size1, string2, size2)
 887     const char *where;
 888     const char *string1;
 889     const char *string2;
 890     int size1;
 891     int size2;
 892 {
 893   int this_char;
 894
 895   if (where == NULL)
 896     printf ("(null)");
 897   else
 898     {
 899       if (FIRST_STRING_P (where))
 900         {
 901           for (this_char = where - string1; this_char < size1; this_char++)
 902             putchar (string1[this_char]);
 903
 904           where = string2;
 905         }
 906
 907       for (this_char = where - string2; this_char < size2; this_char++)
 908         putchar (string2[this_char]);
 909     }
 910 }
 911
 912 void
 913 printchar (c)
 914      int c;
 915 {
 916   putc (c, stderr);
 917 }
 918
 919 #else /* not DEBUG */
 920
 921 #undef assert
 922 #define assert(e)
 923
 924 #define DEBUG_STATEMENT(e)
 925 #define DEBUG_PRINT1(x)
 926 #define DEBUG_PRINT2(x1, x2)
 927 #define DEBUG_PRINT3(x1, x2, x3)
 928 #define DEBUG_PRINT4(x1, x2, x3, x4)
 929 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
 930 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
 931
 932 #endif /* not DEBUG */
 933 \f
 934 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
 935    also be assigned to arbitrarily: each pattern buffer stores its own
 936    syntax, so it can be changed between regex compilations.  */
 937 /* This has no initializer because initialized variables in Emacs
 938    become read-only after dumping.  */
 939 reg_syntax_t re_syntax_options;
 940
 941
 942 /* Specify the precise syntax of regexps for compilation.  This provides
 943    for compatibility for various utilities which historically have
 944    different, incompatible syntaxes.
 945
 946    The argument SYNTAX is a bit mask comprised of the various bits
 947    defined in regex.h.  We return the old syntax.  */
 948
 949 reg_syntax_t
 950 re_set_syntax (syntax)
 951     reg_syntax_t syntax;
 952 {
 953   reg_syntax_t ret = re_syntax_options;
 954
 955   re_syntax_options = syntax;
 956 #ifdef DEBUG
 957   if (syntax & RE_DEBUG)
 958     debug = 1;
 959   else if (debug) /* was on but now is not */
 960     debug = 0;
 961 #endif /* DEBUG */
 962   return ret;
 963 }
 964 \f
 965 /* This table gives an error message for each of the error codes listed
 966    in regex.h.  Obviously the order here has to be same as there.
 967    POSIX doesn't require that we do anything for REG_NOERROR,
 968    but why not be nice?  */
 969
 970 static const char *re_error_msgid[] =
 971   {
 972     gettext_noop ("Success"),   /* REG_NOERROR */
 973     gettext_noop ("No match"),  /* REG_NOMATCH */
 974     gettext_noop ("Invalid regular expression"), /* REG_BADPAT */
 975     gettext_noop ("Invalid collation character"), /* REG_ECOLLATE */
 976     gettext_noop ("Invalid character class name"), /* REG_ECTYPE */
 977     gettext_noop ("Trailing backslash"), /* REG_EESCAPE */
 978     gettext_noop ("Invalid back reference"), /* REG_ESUBREG */
 979     gettext_noop ("Unmatched [ or [^"), /* REG_EBRACK */
 980     gettext_noop ("Unmatched ( or \\("), /* REG_EPAREN */
 981     gettext_noop ("Unmatched \\{"), /* REG_EBRACE */
 982     gettext_noop ("Invalid content of \\{\\}"), /* REG_BADBR */
 983     gettext_noop ("Invalid range end"), /* REG_ERANGE */
 984     gettext_noop ("Memory exhausted"), /* REG_ESPACE */
 985     gettext_noop ("Invalid preceding regular expression"), /* REG_BADRPT */
 986     gettext_noop ("Premature end of regular expression"), /* REG_EEND */
 987     gettext_noop ("Regular expression too big"), /* REG_ESIZE */
 988     gettext_noop ("Unmatched ) or \\)"), /* REG_ERPAREN */
 989   };
 990 \f
 991 /* Avoiding alloca during matching, to placate r_alloc.  */
 992
 993 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
 994    searching and matching functions should not call alloca.  On some
 995    systems, alloca is implemented in terms of malloc, and if we're
 996    using the relocating allocator routines, then malloc could cause a
 997    relocation, which might (if the strings being searched are in the
 998    ralloc heap) shift the data out from underneath the regexp
 999    routines.
1000
1001    Here's another reason to avoid allocation: Emacs
1002    processes input from X in a signal handler; processing X input may
1003    call malloc; if input arrives while a matching routine is calling
1004    malloc, then we're scrod.  But Emacs can't just block input while
1005    calling matching routines; then we don't notice interrupts when
1006    they come in.  So, Emacs blocks input around all regexp calls
1007    except the matching calls, which it leaves unprotected, in the
1008    faith that they will not malloc.  */
1009
1010 /* Normally, this is fine.  */
1011 #define MATCH_MAY_ALLOCATE
1012
1013 /* When using GNU C, we are not REALLY using the C alloca, no matter
1014    what config.h may say.  So don't take precautions for it.  */
1015 #ifdef __GNUC__
1016 #undef C_ALLOCA
1017 #endif
1018
1019 /* The match routines may not allocate if (1) they would do it with malloc
1020    and (2) it's not safe for them to use malloc.
1021    Note that if REL_ALLOC is defined, matching would not use malloc for the
1022    failure stack, but we would still use it for the register vectors;
1023    so REL_ALLOC should not affect this.  */
1024 #if (defined (C_ALLOCA) || defined (REGEX_MALLOC)) && defined (emacs)
1025 #undef MATCH_MAY_ALLOCATE
1026 #endif
1027
1028 \f
1029 /* Failure stack declarations and macros; both re_compile_fastmap and
1030    re_match_2 use a failure stack.  These have to be macros because of
1031    REGEX_ALLOCATE_STACK.  */
1032
1033
1034 /* Number of failure points for which to initially allocate space
1035    when matching.  If this number is exceeded, we allocate more
1036    space, so it is not a hard limit.  */
1037 #ifndef INIT_FAILURE_ALLOC
1038 #define INIT_FAILURE_ALLOC 5
1039 #endif
1040
1041 /* Roughly the maximum number of failure points on the stack.  Would be
1042    exactly that if always used MAX_FAILURE_ITEMS items each time we failed.
1043    This is a variable only so users of regex can assign to it; we never
1044    change it ourselves.  */
1045
1046 #ifdef INT_IS_16BIT
1047
1048 #if defined (MATCH_MAY_ALLOCATE)
1049 /* 4400 was enough to cause a crash on Alpha OSF/1,
1050    whose default stack limit is 2mb.  */
1051 long int re_max_failures = 4000;
1052 #else
1053 long int re_max_failures = 2000;
1054 #endif
1055
1056 union fail_stack_elt
1057 {
1058   unsigned char *pointer;
1059   long int integer;
1060 };
1061
1062 typedef union fail_stack_elt fail_stack_elt_t;
1063
1064 typedef struct
1065 {
1066   fail_stack_elt_t *stack;
1067   unsigned long int size;
1068   unsigned long int avail;              /* Offset of next open position.  */
1069 } fail_stack_type;
1070
1071 #else /* not INT_IS_16BIT */
1072
1073 #if defined (MATCH_MAY_ALLOCATE)
1074 /* 4400 was enough to cause a crash on Alpha OSF/1,
1075    whose default stack limit is 2mb.  */
1076 int re_max_failures = 20000;
1077 #else
1078 int re_max_failures = 2000;
1079 #endif
1080
1081 union fail_stack_elt
1082 {
1083   unsigned char *pointer;
1084   int integer;
1085 };
1086
1087 typedef union fail_stack_elt fail_stack_elt_t;
1088
1089 typedef struct
1090 {
1091   fail_stack_elt_t *stack;
1092   unsigned size;
1093   unsigned avail;                       /* Offset of next open position.  */
1094 } fail_stack_type;
1095
1096 #endif /* INT_IS_16BIT */
1097
1098 #define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
1099 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1100 #define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
1101
1102
1103 /* Define macros to initialize and free the failure stack.
1104    Do `return -2' if the alloc fails.  */
1105
1106 #ifdef MATCH_MAY_ALLOCATE
1107 #define INIT_FAIL_STACK()                                               \
1108   do {                                                                  \
1109     fail_stack.stack = (fail_stack_elt_t *)                             \
1110       REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t));    \
1111                                                                         \
1112     if (fail_stack.stack == NULL)                                       \
1113       return -2;                                                        \
1114                                                                         \
1115     fail_stack.size = INIT_FAILURE_ALLOC;                               \
1116     fail_stack.avail = 0;                                               \
1117   } while (0)
1118
1119 #define RESET_FAIL_STACK()  REGEX_FREE_STACK (fail_stack.stack)
1120 #else
1121 #define INIT_FAIL_STACK()                                               \
1122   do {                                                                  \
1123     fail_stack.avail = 0;                                               \
1124   } while (0)
1125
1126 #define RESET_FAIL_STACK()
1127 #endif
1128
1129
1130 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1131
1132    Return 1 if succeeds, and 0 if either ran out of memory
1133    allocating space for it or it was already too large.
1134
1135    REGEX_REALLOCATE_STACK requires `destination' be declared.   */
1136
1137 #define DOUBLE_FAIL_STACK(fail_stack)                                   \
1138   ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1139    ? 0                                                                  \
1140    : ((fail_stack).stack = (fail_stack_elt_t *)                         \
1141         REGEX_REALLOCATE_STACK ((fail_stack).stack,                     \
1142           (fail_stack).size * sizeof (fail_stack_elt_t),                \
1143           ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)),        \
1144                                                                         \
1145       (fail_stack).stack == NULL                                        \
1146       ? 0                                                               \
1147       : ((fail_stack).size <<= 1,                                       \
1148          1)))
1149
1150
1151 /* Push pointer POINTER on FAIL_STACK.
1152    Return 1 if was able to do so and 0 if ran out of memory allocating
1153    space to do so.  */
1154 #define PUSH_PATTERN_OP(POINTER, FAIL_STACK)                            \
1155   ((FAIL_STACK_FULL ()                                                  \
1156     && !DOUBLE_FAIL_STACK (FAIL_STACK))                                 \
1157    ? 0                                                                  \
1158    : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER,       \
1159       1))
1160
1161 /* Push a pointer value onto the failure stack.
1162    Assumes the variable `fail_stack'.  Probably should only
1163    be called from within `PUSH_FAILURE_POINT'.  */
1164 #define PUSH_FAILURE_POINTER(item)                                      \
1165   fail_stack.stack[fail_stack.avail++].pointer = (unsigned char *) (item)
1166
1167 /* This pushes an integer-valued item onto the failure stack.
1168    Assumes the variable `fail_stack'.  Probably should only
1169    be called from within `PUSH_FAILURE_POINT'.  */
1170 #define PUSH_FAILURE_INT(item)                                  \
1171   fail_stack.stack[fail_stack.avail++].integer = (item)
1172
1173 /* Push a fail_stack_elt_t value onto the failure stack.
1174    Assumes the variable `fail_stack'.  Probably should only
1175    be called from within `PUSH_FAILURE_POINT'.  */
1176 #define PUSH_FAILURE_ELT(item)                                  \
1177   fail_stack.stack[fail_stack.avail++] =  (item)
1178
1179 /* These three POP... operations complement the three PUSH... operations.
1180    All assume that `fail_stack' is nonempty.  */
1181 #define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1182 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1183 #define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1184
1185 /* Used to omit pushing failure point id's when we're not debugging.  */
1186 #ifdef DEBUG
1187 #define DEBUG_PUSH PUSH_FAILURE_INT
1188 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1189 #else
1190 #define DEBUG_PUSH(item)
1191 #define DEBUG_POP(item_addr)
1192 #endif
1193
1194
1195 /* Push the information about the state we will need
1196    if we ever fail back to it.
1197
1198    Requires variables fail_stack, regstart, regend, reg_info, and
1199    num_regs be declared.  DOUBLE_FAIL_STACK requires `destination' be
1200    declared.
1201
1202    Does `return FAILURE_CODE' if runs out of memory.  */
1203
1204 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)   \
1205   do {                                                                  \
1206     char *destination;                                                  \
1207     /* Must be int, so when we don't save any registers, the arithmetic \
1208        of 0 + -1 isn't done as unsigned.  */                            \
1209     /* Can't be int, since there is not a shred of a guarantee that int \
1210        is wide enough to hold a value of something to which pointer can \
1211        be assigned */                                                   \
1212     active_reg_t this_reg;                                              \
1213                                                                         \
1214     DEBUG_STATEMENT (failure_id++);                                     \
1215     DEBUG_STATEMENT (nfailure_points_pushed++);                         \
1216     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);           \
1217     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
1218     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
1219                                                                         \
1220     DEBUG_PRINT2 ("  slots needed: %ld\n", NUM_FAILURE_ITEMS);          \
1221     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);       \
1222                                                                         \
1223     /* Ensure we have enough space allocated for what we will push.  */ \
1224     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)                   \
1225       {                                                                 \
1226         if (!DOUBLE_FAIL_STACK (fail_stack))                            \
1227           return failure_code;                                          \
1228                                                                         \
1229         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",              \
1230                        (fail_stack).size);                              \
1231         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1232       }                                                                 \
1233                                                                         \
1234     /* Push the info, starting with the registers.  */                  \
1235     DEBUG_PRINT1 ("\n");                                                \
1236                                                                         \
1237     if (1)                                                              \
1238       for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1239            this_reg++)                                                  \
1240         {                                                               \
1241           DEBUG_PRINT2 ("  Pushing reg: %lu\n", this_reg);              \
1242           DEBUG_STATEMENT (num_regs_pushed++);                          \
1243                                                                         \
1244           DEBUG_PRINT2 ("    start: %p\n", regstart[this_reg]);         \
1245           PUSH_FAILURE_POINTER (regstart[this_reg]);                    \
1246                                                                         \
1247           DEBUG_PRINT2 ("    end: %p\n", regend[this_reg]);             \
1248           PUSH_FAILURE_POINTER (regend[this_reg]);                      \
1249                                                                         \
1250           DEBUG_PRINT2 ("    info: %p\n      ",                         \
1251                         reg_info[this_reg].word.pointer);               \
1252           DEBUG_PRINT2 (" match_null=%d",                               \
1253                         REG_MATCH_NULL_STRING_P (reg_info[this_reg]));  \
1254           DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));  \
1255           DEBUG_PRINT2 (" matched_something=%d",                        \
1256                         MATCHED_SOMETHING (reg_info[this_reg]));        \
1257           DEBUG_PRINT2 (" ever_matched=%d",                             \
1258                         EVER_MATCHED_SOMETHING (reg_info[this_reg]));   \
1259           DEBUG_PRINT1 ("\n");                                          \
1260           PUSH_FAILURE_ELT (reg_info[this_reg].word);                   \
1261         }                                                               \
1262                                                                         \
1263     DEBUG_PRINT2 ("  Pushing  low active reg: %ld\n", lowest_active_reg);\
1264     PUSH_FAILURE_INT (lowest_active_reg);                               \
1265                                                                         \
1266     DEBUG_PRINT2 ("  Pushing high active reg: %ld\n", highest_active_reg);\
1267     PUSH_FAILURE_INT (highest_active_reg);                              \
1268                                                                         \
1269     DEBUG_PRINT2 ("  Pushing pattern %p:\n", pattern_place);            \
1270     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);           \
1271     PUSH_FAILURE_POINTER (pattern_place);                               \
1272                                                                         \
1273     DEBUG_PRINT2 ("  Pushing string %p: `", string_place);              \
1274     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
1275                                  size2);                                \
1276     DEBUG_PRINT1 ("'\n");                                               \
1277     PUSH_FAILURE_POINTER (string_place);                                \
1278                                                                         \
1279     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);            \
1280     DEBUG_PUSH (failure_id);                                            \
1281   } while (0)
1282
1283 /* This is the number of items that are pushed and popped on the stack
1284    for each register.  */
1285 #define NUM_REG_ITEMS  3
1286
1287 /* Individual items aside from the registers.  */
1288 #ifdef DEBUG
1289 #define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
1290 #else
1291 #define NUM_NONREG_ITEMS 4
1292 #endif
1293
1294 /* We push at most this many items on the stack.  */
1295 /* We used to use (num_regs - 1), which is the number of registers
1296    this regexp will save; but that was changed to 5
1297    to avoid stack overflow for a regexp with lots of parens.  */
1298 #define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1299
1300 /* We actually push this many items.  */
1301 #define NUM_FAILURE_ITEMS                               \
1302   (((0                                                  \
1303      ? 0 : highest_active_reg - lowest_active_reg + 1)  \
1304     * NUM_REG_ITEMS)                                    \
1305    + NUM_NONREG_ITEMS)
1306
1307 /* How many items can still be added to the stack without overflowing it.  */
1308 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1309
1310
1311 /* Pops what PUSH_FAIL_STACK pushes.
1312
1313    We restore into the parameters, all of which should be lvalues:
1314      STR -- the saved data position.
1315      PAT -- the saved pattern position.
1316      LOW_REG, HIGH_REG -- the highest and lowest active registers.
1317      REGSTART, REGEND -- arrays of string positions.
1318      REG_INFO -- array of information about each subexpression.
1319
1320    Also assumes the variables `fail_stack' and (if debugging), `bufp',
1321    `pend', `string1', `size1', `string2', and `size2'.  */
1322
1323 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1324 {                                                                       \
1325   DEBUG_STATEMENT (unsigned failure_id;)                                \
1326   active_reg_t this_reg;                                                \
1327   const unsigned char *string_temp;                                     \
1328                                                                         \
1329   assert (!FAIL_STACK_EMPTY ());                                        \
1330                                                                         \
1331   /* Remove failure points and point to how many regs pushed.  */       \
1332   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                                \
1333   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
1334   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size);     \
1335                                                                         \
1336   assert (fail_stack.avail >= NUM_NONREG_ITEMS);                        \
1337                                                                         \
1338   DEBUG_POP (&failure_id);                                              \
1339   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);              \
1340                                                                         \
1341   /* If the saved string location is NULL, it came from an              \
1342      on_failure_keep_string_jump opcode, and we want to throw away the  \
1343      saved NULL, thus retaining our current position in the string.  */ \
1344   string_temp = POP_FAILURE_POINTER ();                                 \
1345   if (string_temp != NULL)                                              \
1346     str = (const char *) string_temp;                                   \
1347                                                                         \
1348   DEBUG_PRINT2 ("  Popping string %p: `", str);                         \
1349   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);      \
1350   DEBUG_PRINT1 ("'\n");                                                 \
1351                                                                         \
1352   pat = (unsigned char *) POP_FAILURE_POINTER ();                       \
1353   DEBUG_PRINT2 ("  Popping pattern %p:\n", pat);                        \
1354   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);                       \
1355                                                                         \
1356   /* Restore register info.  */                                         \
1357   high_reg = (active_reg_t) POP_FAILURE_INT ();                         \
1358   DEBUG_PRINT2 ("  Popping high active reg: %ld\n", high_reg);          \
1359                                                                         \
1360   low_reg = (active_reg_t) POP_FAILURE_INT ();                          \
1361   DEBUG_PRINT2 ("  Popping  low active reg: %ld\n", low_reg);           \
1362                                                                         \
1363   if (1)                                                                \
1364     for (this_reg = high_reg; this_reg >= low_reg; this_reg--)          \
1365       {                                                                 \
1366         DEBUG_PRINT2 ("    Popping reg: %ld\n", this_reg);              \
1367                                                                         \
1368         reg_info[this_reg].word = POP_FAILURE_ELT ();                   \
1369         DEBUG_PRINT2 ("      info: %p\n",                               \
1370                       reg_info[this_reg].word.pointer);                 \
1371                                                                         \
1372         regend[this_reg] = (const char *) POP_FAILURE_POINTER ();       \
1373         DEBUG_PRINT2 ("      end: %p\n", regend[this_reg]);             \
1374                                                                         \
1375         regstart[this_reg] = (const char *) POP_FAILURE_POINTER ();     \
1376         DEBUG_PRINT2 ("      start: %p\n", regstart[this_reg]);         \
1377       }                                                                 \
1378   else                                                                  \
1379     {                                                                   \
1380       for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1381         {                                                               \
1382           reg_info[this_reg].word.integer = 0;                          \
1383           regend[this_reg] = 0;                                         \
1384           regstart[this_reg] = 0;                                       \
1385         }                                                               \
1386       highest_active_reg = high_reg;                                    \
1387     }                                                                   \
1388                                                                         \
1389   set_regs_matched_done = 0;                                            \
1390   DEBUG_STATEMENT (nfailure_points_popped++);                           \
1391 } /* POP_FAILURE_POINT */
1392
1393
1394 \f
1395 /* Structure for per-register (a.k.a. per-group) information.
1396    Other register information, such as the
1397    starting and ending positions (which are addresses), and the list of
1398    inner groups (which is a bits list) are maintained in separate
1399    variables.
1400
1401    We are making a (strictly speaking) nonportable assumption here: that
1402    the compiler will pack our bit fields into something that fits into
1403    the type of `word', i.e., is something that fits into one item on the
1404    failure stack.  */
1405
1406
1407 /* Declarations and macros for re_match_2.  */
1408
1409 typedef union
1410 {
1411   fail_stack_elt_t word;
1412   struct
1413   {
1414       /* This field is one if this group can match the empty string,
1415          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
1416 #define MATCH_NULL_UNSET_VALUE 3
1417     unsigned match_null_string_p : 2;
1418     unsigned is_active : 1;
1419     unsigned matched_something : 1;
1420     unsigned ever_matched_something : 1;
1421   } bits;
1422 } register_info_type;
1423
1424 #define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
1425 #define IS_ACTIVE(R)  ((R).bits.is_active)
1426 #define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
1427 #define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
1428
1429
1430 /* Call this when have matched a real character; it sets `matched' flags
1431    for the subexpressions which we are currently inside.  Also records
1432    that those subexprs have matched.  */
1433 #define SET_REGS_MATCHED()                                              \
1434   do                                                                    \
1435     {                                                                   \
1436       if (!set_regs_matched_done)                                       \
1437         {                                                               \
1438           active_reg_t r;                                               \
1439           set_regs_matched_done = 1;                                    \
1440           for (r = lowest_active_reg; r <= highest_active_reg; r++)     \
1441             {                                                           \
1442               MATCHED_SOMETHING (reg_info[r])                           \
1443                 = EVER_MATCHED_SOMETHING (reg_info[r])                  \
1444                 = 1;                                                    \
1445             }                                                           \
1446         }                                                               \
1447     }                                                                   \
1448   while (0)
1449
1450 /* Registers are set to a sentinel when they haven't yet matched.  */
1451 static char reg_unset_dummy;
1452 #define REG_UNSET_VALUE (&reg_unset_dummy)
1453 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1454 \f
1455 /* Subroutine declarations and macros for regex_compile.  */
1456
1457 static reg_errcode_t regex_compile _RE_ARGS ((const char *pattern, size_t size,
1458                                               reg_syntax_t syntax,
1459                                               struct re_pattern_buffer *bufp));
1460 static void store_op1 _RE_ARGS ((re_opcode_t op, unsigned char *loc, int arg));
1461 static void store_op2 _RE_ARGS ((re_opcode_t op, unsigned char *loc,
1462                                  int arg1, int arg2));
1463 static void insert_op1 _RE_ARGS ((re_opcode_t op, unsigned char *loc,
1464                                   int arg, unsigned char *end));
1465 static void insert_op2 _RE_ARGS ((re_opcode_t op, unsigned char *loc,
1466                                   int arg1, int arg2, unsigned char *end));
1467 static boolean at_begline_loc_p _RE_ARGS ((const char *pattern, const char *p,
1468                                            reg_syntax_t syntax));
1469 static boolean at_endline_loc_p _RE_ARGS ((const char *p, const char *pend,
1470                                            reg_syntax_t syntax));
1471 static reg_errcode_t compile_range _RE_ARGS ((const char **p_ptr,
1472                                               const char *pend,
1473                                               char *translate,
1474                                               reg_syntax_t syntax,
1475                                               unsigned char *b));
1476
1477 /* Fetch the next character in the uncompiled pattern---translating it
1478    if necessary.  Also cast from a signed character in the constant
1479    string passed to us by the user to an unsigned char that we can use
1480    as an array index (in, e.g., `translate').  */
1481 #ifndef PATFETCH
1482 #define PATFETCH(c)                                                     \
1483   do {if (p == pend) return REG_EEND;                                   \
1484     c = (unsigned char) *p++;                                           \
1485     if (translate) c = (unsigned char) translate[c];                    \
1486   } while (0)
1487 #endif
1488
1489 /* Fetch the next character in the uncompiled pattern, with no
1490    translation.  */
1491 #define PATFETCH_RAW(c)                                                 \
1492   do {if (p == pend) return REG_EEND;                                   \
1493     c = (unsigned char) *p++;                                           \
1494   } while (0)
1495
1496 /* Go backwards one character in the pattern.  */
1497 #define PATUNFETCH p--
1498
1499
1500 /* If `translate' is non-null, return translate[D], else just D.  We
1501    cast the subscript to translate because some data is declared as
1502    `char *', to avoid warnings when a string constant is passed.  But
1503    when we use a character as a subscript we must make it unsigned.  */
1504 #ifndef TRANSLATE
1505 #define TRANSLATE(d) \
1506   (translate ? (char) translate[(unsigned char) (d)] : (d))
1507 #endif
1508
1509
1510 /* Macros for outputting the compiled pattern into `buffer'.  */
1511
1512 /* If the buffer isn't allocated when it comes in, use this.  */
1513 #define INIT_BUF_SIZE  32
1514
1515 /* Make sure we have at least N more bytes of space in buffer.  */
1516 #define GET_BUFFER_SPACE(n)                                             \
1517     while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated)  \
1518       EXTEND_BUFFER ()
1519
1520 /* Make sure we have one more byte of buffer space and then add C to it.  */
1521 #define BUF_PUSH(c)                                                     \
1522   do {                                                                  \
1523     GET_BUFFER_SPACE (1);                                               \
1524     *b++ = (unsigned char) (c);                                         \
1525   } while (0)
1526
1527
1528 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
1529 #define BUF_PUSH_2(c1, c2)                                              \
1530   do {                                                                  \
1531     GET_BUFFER_SPACE (2);                                               \
1532     *b++ = (unsigned char) (c1);                                        \
1533     *b++ = (unsigned char) (c2);                                        \
1534   } while (0)
1535
1536
1537 /* As with BUF_PUSH_2, except for three bytes.  */
1538 #define BUF_PUSH_3(c1, c2, c3)                                          \
1539   do {                                                                  \
1540     GET_BUFFER_SPACE (3);                                               \
1541     *b++ = (unsigned char) (c1);                                        \
1542     *b++ = (unsigned char) (c2);                                        \
1543     *b++ = (unsigned char) (c3);                                        \
1544   } while (0)
1545
1546
1547 /* Store a jump with opcode OP at LOC to location TO.  We store a
1548    relative address offset by the three bytes the jump itself occupies.  */
1549 #define STORE_JUMP(op, loc, to) \
1550   store_op1 (op, loc, (int) ((to) - (loc) - 3))
1551
1552 /* Likewise, for a two-argument jump.  */
1553 #define STORE_JUMP2(op, loc, to, arg) \
1554   store_op2 (op, loc, (int) ((to) - (loc) - 3), arg)
1555
1556 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
1557 #define INSERT_JUMP(op, loc, to) \
1558   insert_op1 (op, loc, (int) ((to) - (loc) - 3), b)
1559
1560 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
1561 #define INSERT_JUMP2(op, loc, to, arg) \
1562   insert_op2 (op, loc, (int) ((to) - (loc) - 3), arg, b)
1563
1564
1565 /* This is not an arbitrary limit: the arguments which represent offsets
1566    into the pattern are two bytes long.  So if 2^16 bytes turns out to
1567    be too small, many things would have to change.  */
1568 /* Any other compiler which, like MSC, has allocation limit below 2^16
1569    bytes will have to use approach similar to what was done below for
1570    MSC and drop MAX_BUF_SIZE a bit.  Otherwise you may end up
1571    reallocating to 0 bytes.  Such thing is not going to work too well.
1572    You have been warned!!  */
1573 #if defined(_MSC_VER)  && !defined(WIN32)
1574 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
1575    The REALLOC define eliminates a flurry of conversion warnings,
1576    but is not required. */
1577 #define MAX_BUF_SIZE  65500L
1578 #define REALLOC(p,s) realloc ((p), (size_t) (s))
1579 #else
1580 #define MAX_BUF_SIZE (1L << 16)
1581 #define REALLOC(p,s) realloc ((p), (s))
1582 #endif
1583
1584 /* Extend the buffer by twice its current size via realloc and
1585    reset the pointers that pointed into the old block to point to the
1586    correct places in the new one.  If extending the buffer results in it
1587    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
1588 #define EXTEND_BUFFER()                                                 \
1589   do {                                                                  \
1590     unsigned char *old_buffer = bufp->buffer;                           \
1591     if (bufp->allocated == MAX_BUF_SIZE)                                \
1592       return REG_ESIZE;                                                 \
1593     bufp->allocated <<= 1;                                              \
1594     if (bufp->allocated > MAX_BUF_SIZE)                                 \
1595       bufp->allocated = MAX_BUF_SIZE;                                   \
1596     bufp->buffer = (unsigned char *) REALLOC (bufp->buffer, bufp->allocated);\
1597     if (bufp->buffer == NULL)                                           \
1598       return REG_ESPACE;                                                \
1599     /* If the buffer moved, move all the pointers into it.  */          \
1600     if (old_buffer != bufp->buffer)                                     \
1601       {                                                                 \
1602         b = (b - old_buffer) + bufp->buffer;                            \
1603         begalt = (begalt - old_buffer) + bufp->buffer;                  \
1604         if (fixup_alt_jump)                                             \
1605           fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
1606         if (laststart)                                                  \
1607           laststart = (laststart - old_buffer) + bufp->buffer;          \
1608         if (pending_exact)                                              \
1609           pending_exact = (pending_exact - old_buffer) + bufp->buffer;  \
1610       }                                                                 \
1611   } while (0)
1612
1613
1614 /* Since we have one byte reserved for the register number argument to
1615    {start,stop}_memory, the maximum number of groups we can report
1616    things about is what fits in that byte.  */
1617 #define MAX_REGNUM 255
1618
1619 /* But patterns can have more than `MAX_REGNUM' registers.  We just
1620    ignore the excess.  */
1621 typedef unsigned regnum_t;
1622
1623
1624 /* Macros for the compile stack.  */
1625
1626 /* Since offsets can go either forwards or backwards, this type needs to
1627    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
1628 /* int may be not enough when sizeof(int) == 2.  */
1629 typedef long pattern_offset_t;
1630
1631 typedef struct
1632 {
1633   pattern_offset_t begalt_offset;
1634   pattern_offset_t fixup_alt_jump;
1635   pattern_offset_t inner_group_offset;
1636   pattern_offset_t laststart_offset;
1637   regnum_t regnum;
1638 } compile_stack_elt_t;
1639
1640
1641 typedef struct
1642 {
1643   compile_stack_elt_t *stack;
1644   unsigned size;
1645   unsigned avail;                       /* Offset of next open position.  */
1646 } compile_stack_type;
1647
1648
1649 #define INIT_COMPILE_STACK_SIZE 32
1650
1651 #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
1652 #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
1653
1654 /* The next available element.  */
1655 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
1656
1657
1658 /* Set the bit for character C in a list.  */
1659 #define SET_LIST_BIT(c)                               \
1660   (b[((unsigned char) (c)) / BYTEWIDTH]               \
1661    |= 1 << (((unsigned char) c) % BYTEWIDTH))
1662
1663
1664 /* Get the next unsigned number in the uncompiled pattern.  */
1665 #define GET_UNSIGNED_NUMBER(num)                                        \
1666   { if (p != pend)                                                      \
1667      {                                                                  \
1668        PATFETCH (c);                                                    \
1669        while (ISDIGIT (c))                                              \
1670          {                                                              \
1671            if (num < 0)                                                 \
1672               num = 0;                                                  \
1673            num = num * 10 + c - '0';                                    \
1674            if (p == pend)                                               \
1675               break;                                                    \
1676            PATFETCH (c);                                                \
1677          }                                                              \
1678        }                                                                \
1679     }
1680
1681 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
1682 /* The GNU C library provides support for user-defined character classes
1683    and the functions from ISO C amendement 1.  */
1684 # ifdef CHARCLASS_NAME_MAX
1685 #  define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
1686 # else
1687 /* This shouldn't happen but some implementation might still have this
1688    problem.  Use a reasonable default value.  */
1689 #  define CHAR_CLASS_MAX_LENGTH 256
1690 # endif
1691
1692 # define IS_CHAR_CLASS(string) wctype (string)
1693 #else
1694 # define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
1695
1696 # define IS_CHAR_CLASS(string)                                          \
1697    (STREQ (string, "alpha") || STREQ (string, "upper")                  \
1698     || STREQ (string, "lower") || STREQ (string, "digit")               \
1699     || STREQ (string, "alnum") || STREQ (string, "xdigit")              \
1700     || STREQ (string, "space") || STREQ (string, "print")               \
1701     || STREQ (string, "punct") || STREQ (string, "graph")               \
1702     || STREQ (string, "cntrl") || STREQ (string, "blank"))
1703 #endif
1704 \f
1705 #ifndef MATCH_MAY_ALLOCATE
1706
1707 /* If we cannot allocate large objects within re_match_2_internal,
1708    we make the fail stack and register vectors global.
1709    The fail stack, we grow to the maximum size when a regexp
1710    is compiled.
1711    The register vectors, we adjust in size each time we
1712    compile a regexp, according to the number of registers it needs.  */
1713
1714 static fail_stack_type fail_stack;
1715
1716 /* Size with which the following vectors are currently allocated.
1717    That is so we can make them bigger as needed,
1718    but never make them smaller.  */
1719 static int regs_allocated_size;
1720
1721 static const char **     regstart, **     regend;
1722 static const char ** old_regstart, ** old_regend;
1723 static const char **best_regstart, **best_regend;
1724 static register_info_type *reg_info;
1725 static const char **reg_dummy;
1726 static register_info_type *reg_info_dummy;
1727
1728 /* Make the register vectors big enough for NUM_REGS registers,
1729    but don't make them smaller.  */
1730
1731 static
1732 regex_grow_registers (num_regs)
1733      int num_regs;
1734 {
1735   if (num_regs > regs_allocated_size)
1736     {
1737       RETALLOC_IF (regstart,     num_regs, const char *);
1738       RETALLOC_IF (regend,       num_regs, const char *);
1739       RETALLOC_IF (old_regstart, num_regs, const char *);
1740       RETALLOC_IF (old_regend,   num_regs, const char *);
1741       RETALLOC_IF (best_regstart, num_regs, const char *);
1742       RETALLOC_IF (best_regend,  num_regs, const char *);
1743       RETALLOC_IF (reg_info,     num_regs, register_info_type);
1744       RETALLOC_IF (reg_dummy,    num_regs, const char *);
1745       RETALLOC_IF (reg_info_dummy, num_regs, register_info_type);
1746
1747       regs_allocated_size = num_regs;
1748     }
1749 }
1750
1751 #endif /* not MATCH_MAY_ALLOCATE */
1752 \f
1753 static boolean group_in_compile_stack _RE_ARGS ((compile_stack_type
1754                                                  compile_stack,
1755                                                  regnum_t regnum));
1756
1757 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
1758    Returns one of error codes defined in `regex.h', or zero for success.
1759
1760    Assumes the `allocated' (and perhaps `buffer') and `translate'
1761    fields are set in BUFP on entry.
1762
1763    If it succeeds, results are put in BUFP (if it returns an error, the
1764    contents of BUFP are undefined):
1765      `buffer' is the compiled pattern;
1766      `syntax' is set to SYNTAX;
1767      `used' is set to the length of the compiled pattern;
1768      `fastmap_accurate' is zero;
1769      `re_nsub' is the number of subexpressions in PATTERN;
1770      `not_bol' and `not_eol' are zero;
1771
1772    The `fastmap' and `newline_anchor' fields are neither
1773    examined nor set.  */
1774
1775 /* Return, freeing storage we allocated.  */
1776 #define FREE_STACK_RETURN(value)                \
1777   return (free (compile_stack.stack), value)
1778
1779 static reg_errcode_t
1780 regex_compile (pattern, size, syntax, bufp)
1781      const char *pattern;
1782      size_t size;
1783      reg_syntax_t syntax;
1784      struct re_pattern_buffer *bufp;
1785 {
1786   /* We fetch characters from PATTERN here.  Even though PATTERN is
1787      `char *' (i.e., signed), we declare these variables as unsigned, so
1788      they can be reliably used as array indices.  */
1789   register unsigned char c, c1;
1790
1791   /* A random temporary spot in PATTERN.  */
1792   const char *p1;
1793
1794   /* Points to the end of the buffer, where we should append.  */
1795   register unsigned char *b;
1796
1797   /* Keeps track of unclosed groups.  */
1798   compile_stack_type compile_stack;
1799
1800   /* Points to the current (ending) position in the pattern.  */
1801   const char *p = pattern;
1802   const char *pend = pattern + size;
1803
1804   /* How to translate the characters in the pattern.  */
1805   RE_TRANSLATE_TYPE translate = bufp->translate;
1806
1807   /* Address of the count-byte of the most recently inserted `exactn'
1808      command.  This makes it possible to tell if a new exact-match
1809      character can be added to that command or if the character requires
1810      a new `exactn' command.  */
1811   unsigned char *pending_exact = 0;
1812
1813   /* Address of start of the most recently finished expression.
1814      This tells, e.g., postfix * where to find the start of its
1815      operand.  Reset at the beginning of groups and alternatives.  */
1816   unsigned char *laststart = 0;
1817
1818   /* Address of beginning of regexp, or inside of last group.  */
1819   unsigned char *begalt;
1820
1821   /* Place in the uncompiled pattern (i.e., the {) to
1822      which to go back if the interval is invalid.  */
1823   const char *beg_interval;
1824
1825   /* Address of the place where a forward jump should go to the end of
1826      the containing expression.  Each alternative of an `or' -- except the
1827      last -- ends with a forward jump of this sort.  */
1828   unsigned char *fixup_alt_jump = 0;
1829
1830   /* Counts open-groups as they are encountered.  Remembered for the
1831      matching close-group on the compile stack, so the same register
1832      number is put in the stop_memory as the start_memory.  */
1833   regnum_t regnum = 0;
1834
1835 #ifdef DEBUG
1836   DEBUG_PRINT1 ("\nCompiling pattern: ");
1837   if (debug)
1838     {
1839       unsigned debug_count;
1840
1841       for (debug_count = 0; debug_count < size; debug_count++)
1842         putchar (pattern[debug_count]);
1843       putchar ('\n');
1844     }
1845 #endif /* DEBUG */
1846
1847   /* Initialize the compile stack.  */
1848   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
1849   if (compile_stack.stack == NULL)
1850     return REG_ESPACE;
1851
1852   compile_stack.size = INIT_COMPILE_STACK_SIZE;
1853   compile_stack.avail = 0;
1854
1855   /* Initialize the pattern buffer.  */
1856   bufp->syntax = syntax;
1857   bufp->fastmap_accurate = 0;
1858   bufp->not_bol = bufp->not_eol = 0;
1859
1860   /* Set `used' to zero, so that if we return an error, the pattern
1861      printer (for debugging) will think there's no pattern.  We reset it
1862      at the end.  */
1863   bufp->used = 0;
1864
1865   /* Always count groups, whether or not bufp->no_sub is set.  */
1866   bufp->re_nsub = 0;
1867
1868 #if !defined (emacs) && !defined (SYNTAX_TABLE)
1869   /* Initialize the syntax table.  */
1870    init_syntax_once ();
1871 #endif
1872
1873   if (bufp->allocated == 0)
1874     {
1875       if (bufp->buffer)
1876         { /* If zero allocated, but buffer is non-null, try to realloc
1877              enough space.  This loses if buffer's address is bogus, but
1878              that is the user's responsibility.  */
1879           RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
1880         }
1881       else
1882         { /* Caller did not allocate a buffer.  Do it for them.  */
1883           bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
1884         }
1885       if (!bufp->buffer) FREE_STACK_RETURN (REG_ESPACE);
1886
1887       bufp->allocated = INIT_BUF_SIZE;
1888     }
1889
1890   begalt = b = bufp->buffer;
1891
1892   /* Loop through the uncompiled pattern until we're at the end.  */
1893   while (p != pend)
1894     {
1895       PATFETCH (c);
1896
1897       switch (c)
1898         {
1899         case '^':
1900           {
1901             if (   /* If at start of pattern, it's an operator.  */
1902                    p == pattern + 1
1903                    /* If context independent, it's an operator.  */
1904                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1905                    /* Otherwise, depends on what's come before.  */
1906                 || at_begline_loc_p (pattern, p, syntax))
1907               BUF_PUSH (begline);
1908             else
1909               goto normal_char;
1910           }
1911           break;
1912
1913
1914         case '$':
1915           {
1916             if (   /* If at end of pattern, it's an operator.  */
1917                    p == pend
1918                    /* If context independent, it's an operator.  */
1919                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1920                    /* Otherwise, depends on what's next.  */
1921                 || at_endline_loc_p (p, pend, syntax))
1922                BUF_PUSH (endline);
1923              else
1924                goto normal_char;
1925            }
1926            break;
1927
1928
1929         case '+':
1930         case '?':
1931           if ((syntax & RE_BK_PLUS_QM)
1932               || (syntax & RE_LIMITED_OPS))
1933             goto normal_char;
1934         handle_plus:
1935         case '*':
1936           /* If there is no previous pattern... */
1937           if (!laststart)
1938             {
1939               if (syntax & RE_CONTEXT_INVALID_OPS)
1940                 FREE_STACK_RETURN (REG_BADRPT);
1941               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
1942                 goto normal_char;
1943             }
1944
1945           {
1946             /* Are we optimizing this jump?  */
1947             boolean keep_string_p = false;
1948
1949             /* 1 means zero (many) matches is allowed.  */
1950             char zero_times_ok = 0, many_times_ok = 0;
1951
1952             /* If there is a sequence of repetition chars, collapse it
1953                down to just one (the right one).  We can't combine
1954                interval operators with these because of, e.g., `a{2}*',
1955                which should only match an even number of `a's.  */
1956
1957             for (;;)
1958               {
1959                 zero_times_ok |= c != '+';
1960                 many_times_ok |= c != '?';
1961
1962                 if (p == pend)
1963                   break;
1964
1965                 PATFETCH (c);
1966
1967                 if (c == '*'
1968                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
1969                   ;
1970
1971                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
1972                   {
1973                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
1974
1975                     PATFETCH (c1);
1976                     if (!(c1 == '+' || c1 == '?'))
1977                       {
1978                         PATUNFETCH;
1979                         PATUNFETCH;
1980                         break;
1981                       }
1982
1983                     c = c1;
1984                   }
1985                 else
1986                   {
1987                     PATUNFETCH;
1988                     break;
1989                   }
1990
1991                 /* If we get here, we found another repeat character.  */
1992                }
1993
1994             /* Star, etc. applied to an empty pattern is equivalent
1995                to an empty pattern.  */
1996             if (!laststart)
1997               break;
1998
1999             /* Now we know whether or not zero matches is allowed
2000                and also whether or not two or more matches is allowed.  */
2001             if (many_times_ok)
2002               { /* More than one repetition is allowed, so put in at the
2003                    end a backward relative jump from `b' to before the next
2004                    jump we're going to put in below (which jumps from
2005                    laststart to after this jump).
2006
2007                    But if we are at the `*' in the exact sequence `.*\n',
2008                    insert an unconditional jump backwards to the .,
2009                    instead of the beginning of the loop.  This way we only
2010                    push a failure point once, instead of every time
2011                    through the loop.  */
2012                 assert (p - 1 > pattern);
2013
2014                 /* Allocate the space for the jump.  */
2015                 GET_BUFFER_SPACE (3);
2016
2017                 /* We know we are not at the first character of the pattern,
2018                    because laststart was nonzero.  And we've already
2019                    incremented `p', by the way, to be the character after
2020                    the `*'.  Do we have to do something analogous here
2021                    for null bytes, because of RE_DOT_NOT_NULL?  */
2022                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
2023                     && zero_times_ok
2024                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
2025                     && !(syntax & RE_DOT_NEWLINE))
2026                   { /* We have .*\n.  */
2027                     STORE_JUMP (jump, b, laststart);
2028                     keep_string_p = true;
2029                   }
2030                 else
2031                   /* Anything else.  */
2032                   STORE_JUMP (maybe_pop_jump, b, laststart - 3);
2033
2034                 /* We've added more stuff to the buffer.  */
2035                 b += 3;
2036               }
2037
2038             /* On failure, jump from laststart to b + 3, which will be the
2039                end of the buffer after this jump is inserted.  */
2040             GET_BUFFER_SPACE (3);
2041             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
2042                                        : on_failure_jump,
2043                          laststart, b + 3);
2044             pending_exact = 0;
2045             b += 3;
2046
2047             if (!zero_times_ok)
2048               {
2049                 /* At least one repetition is required, so insert a
2050                    `dummy_failure_jump' before the initial
2051                    `on_failure_jump' instruction of the loop. This
2052                    effects a skip over that instruction the first time
2053                    we hit that loop.  */
2054                 GET_BUFFER_SPACE (3);
2055                 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
2056                 b += 3;
2057               }
2058             }
2059           break;
2060
2061
2062         case '.':
2063           laststart = b;
2064           BUF_PUSH (anychar);
2065           break;
2066
2067
2068         case '[':
2069           {
2070             boolean had_char_class = false;
2071
2072             if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2073
2074             /* Ensure that we have enough space to push a charset: the
2075                opcode, the length count, and the bitset; 34 bytes in all.  */
2076             GET_BUFFER_SPACE (34);
2077
2078             laststart = b;
2079
2080             /* We test `*p == '^' twice, instead of using an if
2081                statement, so we only need one BUF_PUSH.  */
2082             BUF_PUSH (*p == '^' ? charset_not : charset);
2083             if (*p == '^')
2084               p++;
2085
2086             /* Remember the first position in the bracket expression.  */
2087             p1 = p;
2088
2089             /* Push the number of bytes in the bitmap.  */
2090             BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
2091
2092             /* Clear the whole map.  */
2093             bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
2094
2095             /* charset_not matches newline according to a syntax bit.  */
2096             if ((re_opcode_t) b[-2] == charset_not
2097                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
2098               SET_LIST_BIT ('\n');
2099
2100             /* Read in characters and ranges, setting map bits.  */
2101             for (;;)
2102               {
2103                 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2104
2105                 PATFETCH (c);
2106
2107                 /* \ might escape characters inside [...] and [^...].  */
2108                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2109                   {
2110                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2111
2112                     PATFETCH (c1);
2113                     SET_LIST_BIT (c1);
2114                     continue;
2115                   }
2116
2117                 /* Could be the end of the bracket expression.  If it's
2118                    not (i.e., when the bracket expression is `[]' so
2119                    far), the ']' character bit gets set way below.  */
2120                 if (c == ']' && p != p1 + 1)
2121                   break;
2122
2123                 /* Look ahead to see if it's a range when the last thing
2124                    was a character class.  */
2125                 if (had_char_class && c == '-' && *p != ']')
2126                   FREE_STACK_RETURN (REG_ERANGE);
2127
2128                 /* Look ahead to see if it's a range when the last thing
2129                    was a character: if this is a hyphen not at the
2130                    beginning or the end of a list, then it's the range
2131                    operator.  */
2132                 if (c == '-'
2133                     && !(p - 2 >= pattern && p[-2] == '[')
2134                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2135                     && *p != ']')
2136                   {
2137                     reg_errcode_t ret
2138                       = compile_range (&p, pend, translate, syntax, b);
2139                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2140                   }
2141
2142                 else if (p[0] == '-' && p[1] != ']')
2143                   { /* This handles ranges made up of characters only.  */
2144                     reg_errcode_t ret;
2145
2146                     /* Move past the `-'.  */
2147                     PATFETCH (c1);
2148
2149                     ret = compile_range (&p, pend, translate, syntax, b);
2150                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2151                   }
2152
2153                 /* See if we're at the beginning of a possible character
2154                    class.  */
2155
2156                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2157                   { /* Leave room for the null.  */
2158                     char str[CHAR_CLASS_MAX_LENGTH + 1];
2159
2160                     PATFETCH (c);
2161                     c1 = 0;
2162
2163                     /* If pattern is `[[:'.  */
2164                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2165
2166                     for (;;)
2167                       {
2168                         PATFETCH (c);
2169                         if (c == ':' || c == ']' || p == pend
2170                             || c1 == CHAR_CLASS_MAX_LENGTH)
2171                           break;
2172                         str[c1++] = c;
2173                       }
2174                     str[c1] = '\0';
2175
2176                     /* If isn't a word bracketed by `[:' and:`]':
2177                        undo the ending character, the letters, and leave
2178                        the leading `:' and `[' (but set bits for them).  */
2179                     if (c == ':' && *p == ']')
2180                       {
2181 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
2182                         boolean is_lower = STREQ (str, "lower");
2183                         boolean is_upper = STREQ (str, "upper");
2184                         wctype_t wt;
2185                         int ch;
2186
2187                         wt = wctype (str);
2188                         if (wt == 0)
2189                           FREE_STACK_RETURN (REG_ECTYPE);
2190
2191                         /* Throw away the ] at the end of the character
2192                            class.  */
2193                         PATFETCH (c);
2194
2195                         if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2196
2197                         for (ch = 0; ch < 1 << BYTEWIDTH; ++ch)
2198                           {
2199                             if (iswctype (btowc (ch), wt))
2200                               SET_LIST_BIT (ch);
2201
2202                             if (translate && (is_upper || is_lower)
2203                                 && (ISUPPER (ch) || ISLOWER (ch)))
2204                               SET_LIST_BIT (ch);
2205                           }
2206
2207                         had_char_class = true;
2208 #else
2209                         int ch;
2210                         boolean is_alnum = STREQ (str, "alnum");
2211                         boolean is_alpha = STREQ (str, "alpha");
2212                         boolean is_blank = STREQ (str, "blank");
2213                         boolean is_cntrl = STREQ (str, "cntrl");
2214                         boolean is_digit = STREQ (str, "digit");
2215                         boolean is_graph = STREQ (str, "graph");
2216                         boolean is_lower = STREQ (str, "lower");
2217                         boolean is_print = STREQ (str, "print");
2218                         boolean is_punct = STREQ (str, "punct");
2219                         boolean is_space = STREQ (str, "space");
2220                         boolean is_upper = STREQ (str, "upper");
2221                         boolean is_xdigit = STREQ (str, "xdigit");
2222
2223                         if (!IS_CHAR_CLASS (str))
2224                           FREE_STACK_RETURN (REG_ECTYPE);
2225
2226                         /* Throw away the ] at the end of the character
2227                            class.  */
2228                         PATFETCH (c);
2229
2230                         if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2231
2232                         for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
2233                           {
2234                             /* This was split into 3 if's to
2235                                avoid an arbitrary limit in some compiler.  */
2236                             if (   (is_alnum  && ISALNUM (ch))
2237                                 || (is_alpha  && ISALPHA (ch))
2238                                 || (is_blank  && ISBLANK (ch))
2239                                 || (is_cntrl  && ISCNTRL (ch)))
2240                               SET_LIST_BIT (ch);
2241                             if (   (is_digit  && ISDIGIT (ch))
2242                                 || (is_graph  && ISGRAPH (ch))
2243                                 || (is_lower  && ISLOWER (ch))
2244                                 || (is_print  && ISPRINT (ch)))
2245                               SET_LIST_BIT (ch);
2246                             if (   (is_punct  && ISPUNCT (ch))
2247                                 || (is_space  && ISSPACE (ch))
2248                                 || (is_upper  && ISUPPER (ch))
2249                                 || (is_xdigit && ISXDIGIT (ch)))
2250                               SET_LIST_BIT (ch);
2251                             if (   translate && (is_upper || is_lower)
2252                                 && (ISUPPER (ch) || ISLOWER (ch)))
2253                               SET_LIST_BIT (ch);
2254                           }
2255                         had_char_class = true;
2256 #endif  /* libc || wctype.h */
2257                       }
2258                     else
2259                       {
2260                         c1++;
2261                         while (c1--)
2262                           PATUNFETCH;
2263                         SET_LIST_BIT ('[');
2264                         SET_LIST_BIT (':');
2265                         had_char_class = false;
2266                       }
2267                   }
2268                 else
2269                   {
2270                     had_char_class = false;
2271                     SET_LIST_BIT (c);
2272                   }
2273               }
2274
2275             /* Discard any (non)matching list bytes that are all 0 at the
2276                end of the map.  Decrease the map-length byte too.  */
2277             while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
2278               b[-1]--;
2279             b += b[-1];
2280           }
2281           break;
2282
2283
2284         case '(':
2285           if (syntax & RE_NO_BK_PARENS)
2286             goto handle_open;
2287           else
2288             goto normal_char;
2289
2290
2291         case ')':
2292           if (syntax & RE_NO_BK_PARENS)
2293             goto handle_close;
2294           else
2295             goto normal_char;
2296
2297
2298         case '\n':
2299           if (syntax & RE_NEWLINE_ALT)
2300             goto handle_alt;
2301           else
2302             goto normal_char;
2303
2304
2305         case '|':
2306           if (syntax & RE_NO_BK_VBAR)
2307             goto handle_alt;
2308           else
2309             goto normal_char;
2310
2311
2312         case '{':
2313            if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
2314              goto handle_interval;
2315            else
2316              goto normal_char;
2317
2318
2319         case '\\':
2320           if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2321
2322           /* Do not translate the character after the \, so that we can
2323              distinguish, e.g., \B from \b, even if we normally would
2324              translate, e.g., B to b.  */
2325           PATFETCH_RAW (c);
2326
2327           switch (c)
2328             {
2329             case '(':
2330               if (syntax & RE_NO_BK_PARENS)
2331                 goto normal_backslash;
2332
2333             handle_open:
2334               bufp->re_nsub++;
2335               regnum++;
2336
2337               if (COMPILE_STACK_FULL)
2338                 {
2339                   RETALLOC (compile_stack.stack, compile_stack.size << 1,
2340                             compile_stack_elt_t);
2341                   if (compile_stack.stack == NULL) return REG_ESPACE;
2342
2343                   compile_stack.size <<= 1;
2344                 }
2345
2346               /* These are the values to restore when we hit end of this
2347                  group.  They are all relative offsets, so that if the
2348                  whole pattern moves because of realloc, they will still
2349                  be valid.  */
2350               COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
2351               COMPILE_STACK_TOP.fixup_alt_jump
2352                 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
2353               COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
2354               COMPILE_STACK_TOP.regnum = regnum;
2355
2356               /* We will eventually replace the 0 with the number of
2357                  groups inner to this one.  But do not push a
2358                  start_memory for groups beyond the last one we can
2359                  represent in the compiled pattern.  */
2360               if (regnum <= MAX_REGNUM)
2361                 {
2362                   COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
2363                   BUF_PUSH_3 (start_memory, regnum, 0);
2364                 }
2365
2366               compile_stack.avail++;
2367
2368               fixup_alt_jump = 0;
2369               laststart = 0;
2370               begalt = b;
2371               /* If we've reached MAX_REGNUM groups, then this open
2372                  won't actually generate any code, so we'll have to
2373                  clear pending_exact explicitly.  */
2374               pending_exact = 0;
2375               break;
2376
2377
2378             case ')':
2379               if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
2380
2381               if (COMPILE_STACK_EMPTY)
2382                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2383                   goto normal_backslash;
2384                 else
2385                   FREE_STACK_RETURN (REG_ERPAREN);
2386
2387             handle_close:
2388               if (fixup_alt_jump)
2389                 { /* Push a dummy failure point at the end of the
2390                      alternative for a possible future
2391                      `pop_failure_jump' to pop.  See comments at
2392                      `push_dummy_failure' in `re_match_2'.  */
2393                   BUF_PUSH (push_dummy_failure);
2394
2395                   /* We allocated space for this jump when we assigned
2396                      to `fixup_alt_jump', in the `handle_alt' case below.  */
2397                   STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
2398                 }
2399
2400               /* See similar code for backslashed left paren above.  */
2401               if (COMPILE_STACK_EMPTY)
2402                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2403                   goto normal_char;
2404                 else
2405                   FREE_STACK_RETURN (REG_ERPAREN);
2406
2407               /* Since we just checked for an empty stack above, this
2408                  ``can't happen''.  */
2409               assert (compile_stack.avail != 0);
2410               {
2411                 /* We don't just want to restore into `regnum', because
2412                    later groups should continue to be numbered higher,
2413                    as in `(ab)c(de)' -- the second group is #2.  */
2414                 regnum_t this_group_regnum;
2415
2416                 compile_stack.avail--;
2417                 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
2418                 fixup_alt_jump
2419                   = COMPILE_STACK_TOP.fixup_alt_jump
2420                     ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
2421                     : 0;
2422                 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
2423                 this_group_regnum = COMPILE_STACK_TOP.regnum;
2424                 /* If we've reached MAX_REGNUM groups, then this open
2425                    won't actually generate any code, so we'll have to
2426                    clear pending_exact explicitly.  */
2427                 pending_exact = 0;
2428
2429                 /* We're at the end of the group, so now we know how many
2430                    groups were inside this one.  */
2431                 if (this_group_regnum <= MAX_REGNUM)
2432                   {
2433                     unsigned char *inner_group_loc
2434                       = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
2435
2436                     *inner_group_loc = regnum - this_group_regnum;
2437                     BUF_PUSH_3 (stop_memory, this_group_regnum,
2438                                 regnum - this_group_regnum);
2439                   }
2440               }
2441               break;
2442
2443
2444             case '|':                                   /* `\|'.  */
2445               if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
2446                 goto normal_backslash;
2447             handle_alt:
2448               if (syntax & RE_LIMITED_OPS)
2449                 goto normal_char;
2450
2451               /* Insert before the previous alternative a jump which
2452                  jumps to this alternative if the former fails.  */
2453               GET_BUFFER_SPACE (3);
2454               INSERT_JUMP (on_failure_jump, begalt, b + 6);
2455               pending_exact = 0;
2456               b += 3;
2457
2458               /* The alternative before this one has a jump after it
2459                  which gets executed if it gets matched.  Adjust that
2460                  jump so it will jump to this alternative's analogous
2461                  jump (put in below, which in turn will jump to the next
2462                  (if any) alternative's such jump, etc.).  The last such
2463                  jump jumps to the correct final destination.  A picture:
2464                           _____ _____
2465                           |   | |   |
2466                           |   v |   v
2467                          a | b   | c
2468
2469                  If we are at `b', then fixup_alt_jump right now points to a
2470                  three-byte space after `a'.  We'll put in the jump, set
2471                  fixup_alt_jump to right after `b', and leave behind three
2472                  bytes which we'll fill in when we get to after `c'.  */
2473
2474               if (fixup_alt_jump)
2475                 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2476
2477               /* Mark and leave space for a jump after this alternative,
2478                  to be filled in later either by next alternative or
2479                  when know we're at the end of a series of alternatives.  */
2480               fixup_alt_jump = b;
2481               GET_BUFFER_SPACE (3);
2482               b += 3;
2483
2484               laststart = 0;
2485               begalt = b;
2486               break;
2487
2488
2489             case '{':
2490               /* If \{ is a literal.  */
2491               if (!(syntax & RE_INTERVALS)
2492                      /* If we're at `\{' and it's not the open-interval
2493                         operator.  */
2494                   || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
2495                   || (p - 2 == pattern  &&  p == pend))
2496                 goto normal_backslash;
2497
2498             handle_interval:
2499               {
2500                 /* If got here, then the syntax allows intervals.  */
2501
2502                 /* At least (most) this many matches must be made.  */
2503                 int lower_bound = -1, upper_bound = -1;
2504
2505                 beg_interval = p - 1;
2506
2507                 if (p == pend)
2508                   {
2509                     if (syntax & RE_NO_BK_BRACES)
2510                       goto unfetch_interval;
2511                     else
2512                       FREE_STACK_RETURN (REG_EBRACE);
2513                   }
2514
2515                 GET_UNSIGNED_NUMBER (lower_bound);
2516
2517                 if (c == ',')
2518                   {
2519                     GET_UNSIGNED_NUMBER (upper_bound);
2520                     if (upper_bound < 0) upper_bound = RE_DUP_MAX;
2521                   }
2522                 else
2523                   /* Interval such as `{1}' => match exactly once. */
2524                   upper_bound = lower_bound;
2525
2526                 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
2527                     || lower_bound > upper_bound)
2528                   {
2529                     if (syntax & RE_NO_BK_BRACES)
2530                       goto unfetch_interval;
2531                     else
2532                       FREE_STACK_RETURN (REG_BADBR);
2533                   }
2534
2535                 if (!(syntax & RE_NO_BK_BRACES))
2536                   {
2537                     if (c != '\\') FREE_STACK_RETURN (REG_EBRACE);
2538
2539                     PATFETCH (c);
2540                   }
2541
2542                 if (c != '}')
2543                   {
2544                     if (syntax & RE_NO_BK_BRACES)
2545                       goto unfetch_interval;
2546                     else
2547                       FREE_STACK_RETURN (REG_BADBR);
2548                   }
2549
2550                 /* We just parsed a valid interval.  */
2551
2552                 /* If it's invalid to have no preceding re.  */
2553                 if (!laststart)
2554                   {
2555                     if (syntax & RE_CONTEXT_INVALID_OPS)
2556                       FREE_STACK_RETURN (REG_BADRPT);
2557                     else if (syntax & RE_CONTEXT_INDEP_OPS)
2558                       laststart = b;
2559                     else
2560                       goto unfetch_interval;
2561                   }
2562
2563                 /* If the upper bound is zero, don't want to succeed at
2564                    all; jump from `laststart' to `b + 3', which will be
2565                    the end of the buffer after we insert the jump.  */
2566                  if (upper_bound == 0)
2567                    {
2568                      GET_BUFFER_SPACE (3);
2569                      INSERT_JUMP (jump, laststart, b + 3);
2570                      b += 3;
2571                    }
2572
2573                  /* Otherwise, we have a nontrivial interval.  When
2574                     we're all done, the pattern will look like:
2575                       set_number_at <jump count> <upper bound>
2576                       set_number_at <succeed_n count> <lower bound>
2577                       succeed_n <after jump addr> <succeed_n count>
2578                       <body of loop>
2579                       jump_n <succeed_n addr> <jump count>
2580                     (The upper bound and `jump_n' are omitted if
2581                     `upper_bound' is 1, though.)  */
2582                  else
2583                    { /* If the upper bound is > 1, we need to insert
2584                         more at the end of the loop.  */
2585                      unsigned nbytes = 10 + (upper_bound > 1) * 10;
2586
2587                      GET_BUFFER_SPACE (nbytes);
2588
2589                      /* Initialize lower bound of the `succeed_n', even
2590                         though it will be set during matching by its
2591                         attendant `set_number_at' (inserted next),
2592                         because `re_compile_fastmap' needs to know.
2593                         Jump to the `jump_n' we might insert below.  */
2594                      INSERT_JUMP2 (succeed_n, laststart,
2595                                    b + 5 + (upper_bound > 1) * 5,
2596                                    lower_bound);
2597                      b += 5;
2598
2599                      /* Code to initialize the lower bound.  Insert
2600                         before the `succeed_n'.  The `5' is the last two
2601                         bytes of this `set_number_at', plus 3 bytes of
2602                         the following `succeed_n'.  */
2603                      insert_op2 (set_number_at, laststart, 5, lower_bound, b);
2604                      b += 5;
2605
2606                      if (upper_bound > 1)
2607                        { /* More than one repetition is allowed, so
2608                             append a backward jump to the `succeed_n'
2609                             that starts this interval.
2610
2611                             When we've reached this during matching,
2612                             we'll have matched the interval once, so
2613                             jump back only `upper_bound - 1' times.  */
2614                          STORE_JUMP2 (jump_n, b, laststart + 5,
2615                                       upper_bound - 1);
2616                          b += 5;
2617
2618                          /* The location we want to set is the second
2619                             parameter of the `jump_n'; that is `b-2' as
2620                             an absolute address.  `laststart' will be
2621                             the `set_number_at' we're about to insert;
2622                             `laststart+3' the number to set, the source
2623                             for the relative address.  But we are
2624                             inserting into the middle of the pattern --
2625                             so everything is getting moved up by 5.
2626                             Conclusion: (b - 2) - (laststart + 3) + 5,
2627                             i.e., b - laststart.
2628
2629                             We insert this at the beginning of the loop
2630                             so that if we fail during matching, we'll
2631                             reinitialize the bounds.  */
2632                          insert_op2 (set_number_at, laststart, b - laststart,
2633                                      upper_bound - 1, b);
2634                          b += 5;
2635                        }
2636                    }
2637                 pending_exact = 0;
2638                 beg_interval = NULL;
2639               }
2640               break;
2641
2642             unfetch_interval:
2643               /* If an invalid interval, match the characters as literals.  */
2644                assert (beg_interval);
2645                p = beg_interval;
2646                beg_interval = NULL;
2647
2648                /* normal_char and normal_backslash need `c'.  */
2649                PATFETCH (c);
2650
2651                if (!(syntax & RE_NO_BK_BRACES))
2652                  {
2653                    if (p > pattern  &&  p[-1] == '\\')
2654                      goto normal_backslash;
2655                  }
2656                goto normal_char;
2657
2658 #ifdef emacs
2659             /* There is no way to specify the before_dot and after_dot
2660                operators.  rms says this is ok.  --karl  */
2661             case '=':
2662               BUF_PUSH (at_dot);
2663               break;
2664
2665             case 's':
2666               laststart = b;
2667               PATFETCH (c);
2668               BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
2669               break;
2670
2671             case 'S':
2672               laststart = b;
2673               PATFETCH (c);
2674               BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
2675               break;
2676 #endif /* emacs */
2677
2678
2679             case 'w':
2680               if (re_syntax_options & RE_NO_GNU_OPS)
2681                 goto normal_char;
2682               laststart = b;
2683               BUF_PUSH (wordchar);
2684               break;
2685
2686
2687             case 'W':
2688               if (re_syntax_options & RE_NO_GNU_OPS)
2689                 goto normal_char;
2690               laststart = b;
2691               BUF_PUSH (notwordchar);
2692               break;
2693
2694
2695             case '<':
2696               if (re_syntax_options & RE_NO_GNU_OPS)
2697                 goto normal_char;
2698               BUF_PUSH (wordbeg);
2699               break;
2700
2701             case '>':
2702               if (re_syntax_options & RE_NO_GNU_OPS)
2703                 goto normal_char;
2704               BUF_PUSH (wordend);
2705               break;
2706
2707             case 'b':
2708               if (re_syntax_options & RE_NO_GNU_OPS)
2709                 goto normal_char;
2710               BUF_PUSH (wordbound);
2711               break;
2712
2713             case 'B':
2714               if (re_syntax_options & RE_NO_GNU_OPS)
2715                 goto normal_char;
2716               BUF_PUSH (notwordbound);
2717               break;
2718
2719             case '`':
2720               if (re_syntax_options & RE_NO_GNU_OPS)
2721                 goto normal_char;
2722               BUF_PUSH (begbuf);
2723               break;
2724
2725             case '\'':
2726               if (re_syntax_options & RE_NO_GNU_OPS)
2727                 goto normal_char;
2728               BUF_PUSH (endbuf);
2729               break;
2730
2731             case '1': case '2': case '3': case '4': case '5':
2732             case '6': case '7': case '8': case '9':
2733               if (syntax & RE_NO_BK_REFS)
2734                 goto normal_char;
2735
2736               c1 = c - '0';
2737
2738               if (c1 > regnum)
2739                 FREE_STACK_RETURN (REG_ESUBREG);
2740
2741               /* Can't back reference to a subexpression if inside of it.  */
2742               if (group_in_compile_stack (compile_stack, (regnum_t) c1))
2743                 goto normal_char;
2744
2745               laststart = b;
2746               BUF_PUSH_2 (duplicate, c1);
2747               break;
2748
2749
2750             case '+':
2751             case '?':
2752               if (syntax & RE_BK_PLUS_QM)
2753                 goto handle_plus;
2754               else
2755                 goto normal_backslash;
2756
2757             default:
2758             normal_backslash:
2759               /* You might think it would be useful for \ to mean
2760                  not to translate; but if we don't translate it
2761                  it will never match anything.  */
2762               c = TRANSLATE (c);
2763               goto normal_char;
2764             }
2765           break;
2766
2767
2768         default:
2769         /* Expects the character in `c'.  */
2770         normal_char:
2771               /* If no exactn currently being built.  */
2772           if (!pending_exact
2773
2774               /* If last exactn not at current position.  */
2775               || pending_exact + *pending_exact + 1 != b
2776
2777               /* We have only one byte following the exactn for the count.  */
2778               || *pending_exact == (1 << BYTEWIDTH) - 1
2779
2780               /* If followed by a repetition operator.  */
2781               || *p == '*' || *p == '^'
2782               || ((syntax & RE_BK_PLUS_QM)
2783                   ? *p == '\\' && (p[1] == '+' || p[1] == '?')
2784                   : (*p == '+' || *p == '?'))
2785               || ((syntax & RE_INTERVALS)
2786                   && ((syntax & RE_NO_BK_BRACES)
2787                       ? *p == '{'
2788                       : (p[0] == '\\' && p[1] == '{'))))
2789             {
2790               /* Start building a new exactn.  */
2791
2792               laststart = b;
2793
2794               BUF_PUSH_2 (exactn, 0);
2795               pending_exact = b - 1;
2796             }
2797
2798           BUF_PUSH (c);
2799           (*pending_exact)++;
2800           break;
2801         } /* switch (c) */
2802     } /* while p != pend */
2803
2804
2805   /* Through the pattern now.  */
2806
2807   if (fixup_alt_jump)
2808     STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2809
2810   if (!COMPILE_STACK_EMPTY)
2811     FREE_STACK_RETURN (REG_EPAREN);
2812
2813   /* If we don't want backtracking, force success
2814      the first time we reach the end of the compiled pattern.  */
2815   if (syntax & RE_NO_POSIX_BACKTRACKING)
2816     BUF_PUSH (succeed);
2817
2818   free (compile_stack.stack);
2819
2820   /* We have succeeded; set the length of the buffer.  */
2821   bufp->used = b - bufp->buffer;
2822
2823 #ifdef DEBUG
2824   if (debug)
2825     {
2826       DEBUG_PRINT1 ("\nCompiled pattern: \n");
2827       print_compiled_pattern (bufp);
2828     }
2829 #endif /* DEBUG */
2830
2831 #ifndef MATCH_MAY_ALLOCATE
2832   /* Initialize the failure stack to the largest possible stack.  This
2833      isn't necessary unless we're trying to avoid calling alloca in
2834      the search and match routines.  */
2835   {
2836     int num_regs = bufp->re_nsub + 1;
2837
2838     /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
2839        is strictly greater than re_max_failures, the largest possible stack
2840        is 2 * re_max_failures failure points.  */
2841     if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
2842       {
2843         fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
2844
2845 #ifdef emacs
2846         if (! fail_stack.stack)
2847           fail_stack.stack
2848             = (fail_stack_elt_t *) xmalloc (fail_stack.size
2849                                             * sizeof (fail_stack_elt_t));
2850         else
2851           fail_stack.stack
2852             = (fail_stack_elt_t *) xrealloc (fail_stack.stack,
2853                                              (fail_stack.size
2854                                               * sizeof (fail_stack_elt_t)));
2855 #else /* not emacs */
2856         if (! fail_stack.stack)
2857           fail_stack.stack
2858             = (fail_stack_elt_t *) malloc (fail_stack.size
2859                                            * sizeof (fail_stack_elt_t));
2860         else
2861           fail_stack.stack
2862             = (fail_stack_elt_t *) realloc (fail_stack.stack,
2863                                             (fail_stack.size
2864                                              * sizeof (fail_stack_elt_t)));
2865 #endif /* not emacs */
2866       }
2867
2868     regex_grow_registers (num_regs);
2869   }
2870 #endif /* not MATCH_MAY_ALLOCATE */
2871
2872   return REG_NOERROR;
2873 } /* regex_compile */
2874 \f
2875 /* Subroutines for `regex_compile'.  */
2876
2877 /* Store OP at LOC followed by two-byte integer parameter ARG.  */
2878
2879 static void
2880 store_op1 (op, loc, arg)
2881     re_opcode_t op;
2882     unsigned char *loc;
2883     int arg;
2884 {
2885   *loc = (unsigned char) op;
2886   STORE_NUMBER (loc + 1, arg);
2887 }
2888
2889
2890 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2.  */
2891
2892 static void
2893 store_op2 (op, loc, arg1, arg2)
2894     re_opcode_t op;
2895     unsigned char *loc;
2896     int arg1, arg2;
2897 {
2898   *loc = (unsigned char) op;
2899   STORE_NUMBER (loc + 1, arg1);
2900   STORE_NUMBER (loc + 3, arg2);
2901 }
2902
2903
2904 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
2905    for OP followed by two-byte integer parameter ARG.  */
2906
2907 static void
2908 insert_op1 (op, loc, arg, end)
2909     re_opcode_t op;
2910     unsigned char *loc;
2911     int arg;
2912     unsigned char *end;
2913 {
2914   register unsigned char *pfrom = end;
2915   register unsigned char *pto = end + 3;
2916
2917   while (pfrom != loc)
2918     *--pto = *--pfrom;
2919
2920   store_op1 (op, loc, arg);
2921 }
2922
2923
2924 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2.  */
2925
2926 static void
2927 insert_op2 (op, loc, arg1, arg2, end)
2928     re_opcode_t op;
2929     unsigned char *loc;
2930     int arg1, arg2;
2931     unsigned char *end;
2932 {
2933   register unsigned char *pfrom = end;
2934   register unsigned char *pto = end + 5;
2935
2936   while (pfrom != loc)
2937     *--pto = *--pfrom;
2938
2939   store_op2 (op, loc, arg1, arg2);
2940 }
2941
2942
2943 /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
2944    after an alternative or a begin-subexpression.  We assume there is at
2945    least one character before the ^.  */
2946
2947 static boolean
2948 at_begline_loc_p (pattern, p, syntax)
2949     const char *pattern, *p;
2950     reg_syntax_t syntax;
2951 {
2952   const char *prev = p - 2;
2953   boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
2954
2955   return
2956        /* After a subexpression?  */
2957        (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
2958        /* After an alternative?  */
2959     || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
2960 }
2961
2962
2963 /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
2964    at least one character after the $, i.e., `P < PEND'.  */
2965
2966 static boolean
2967 at_endline_loc_p (p, pend, syntax)
2968     const char *p, *pend;
2969     reg_syntax_t syntax;
2970 {
2971   const char *next = p;
2972   boolean next_backslash = *next == '\\';
2973   const char *next_next = p + 1 < pend ? p + 1 : 0;
2974
2975   return
2976        /* Before a subexpression?  */
2977        (syntax & RE_NO_BK_PARENS ? *next == ')'
2978         : next_backslash && next_next && *next_next == ')')
2979        /* Before an alternative?  */
2980     || (syntax & RE_NO_BK_VBAR ? *next == '|'
2981         : next_backslash && next_next && *next_next == '|');
2982 }
2983
2984
2985 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
2986    false if it's not.  */
2987
2988 static boolean
2989 group_in_compile_stack (compile_stack, regnum)
2990     compile_stack_type compile_stack;
2991     regnum_t regnum;
2992 {
2993   int this_element;
2994
2995   for (this_element = compile_stack.avail - 1;
2996        this_element >= 0;
2997        this_element--)
2998     if (compile_stack.stack[this_element].regnum == regnum)
2999       return true;
3000
3001   return false;
3002 }
3003
3004
3005 /* Read the ending character of a range (in a bracket expression) from the
3006    uncompiled pattern *P_PTR (which ends at PEND).  We assume the
3007    starting character is in `P[-2]'.  (`P[-1]' is the character `-'.)
3008    Then we set the translation of all bits between the starting and
3009    ending characters (inclusive) in the compiled pattern B.
3010
3011    Return an error code.
3012
3013    We use these short variable names so we can use the same macros as
3014    `regex_compile' itself.  */
3015
3016 static reg_errcode_t
3017 compile_range (p_ptr, pend, translate, syntax, b)
3018     const char **p_ptr, *pend;
3019     RE_TRANSLATE_TYPE translate;
3020     reg_syntax_t syntax;
3021     unsigned char *b;
3022 {
3023   unsigned this_char;
3024
3025   const char *p = *p_ptr;
3026   unsigned int range_start, range_end;
3027
3028   if (p == pend)
3029     return REG_ERANGE;
3030
3031   /* Even though the pattern is a signed `char *', we need to fetch
3032      with unsigned char *'s; if the high bit of the pattern character
3033      is set, the range endpoints will be negative if we fetch using a
3034      signed char *.
3035
3036      We also want to fetch the endpoints without translating them; the
3037      appropriate translation is done in the bit-setting loop below.  */
3038   /* The SVR4 compiler on the 3B2 had trouble with unsigned const char *.  */
3039   range_start = ((const unsigned char *) p)[-2];
3040   range_end   = ((const unsigned char *) p)[0];
3041
3042   /* Have to increment the pointer into the pattern string, so the
3043      caller isn't still at the ending character.  */
3044   (*p_ptr)++;
3045
3046   /* If the start is after the end, the range is empty.  */
3047   if (range_start > range_end)
3048     return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
3049
3050   /* Here we see why `this_char' has to be larger than an `unsigned
3051      char' -- the range is inclusive, so if `range_end' == 0xff
3052      (assuming 8-bit characters), we would otherwise go into an infinite
3053      loop, since all characters <= 0xff.  */
3054   for (this_char = range_start; this_char <= range_end; this_char++)
3055     {
3056       SET_LIST_BIT (TRANSLATE (this_char));
3057     }
3058
3059   return REG_NOERROR;
3060 }
3061 \f
3062 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
3063    BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
3064    characters can start a string that matches the pattern.  This fastmap
3065    is used by re_search to skip quickly over impossible starting points.
3066
3067    The caller must supply the address of a (1 << BYTEWIDTH)-byte data
3068    area as BUFP->fastmap.
3069
3070    We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
3071    the pattern buffer.
3072
3073    Returns 0 if we succeed, -2 if an internal error.   */
3074
3075 int
3076 re_compile_fastmap (bufp)
3077      struct re_pattern_buffer *bufp;
3078 {
3079   int j, k;
3080 #ifdef MATCH_MAY_ALLOCATE
3081   fail_stack_type fail_stack;
3082 #endif
3083 #ifndef REGEX_MALLOC
3084   char *destination;
3085 #endif
3086   /* We don't push any register information onto the failure stack.  */
3087   unsigned num_regs = 0;
3088
3089   register char *fastmap = bufp->fastmap;
3090   unsigned char *pattern = bufp->buffer;
3091   unsigned char *p = pattern;
3092   register unsigned char *pend = pattern + bufp->used;
3093
3094 #ifdef REL_ALLOC
3095   /* This holds the pointer to the failure stack, when
3096      it is allocated relocatably.  */
3097   fail_stack_elt_t *failure_stack_ptr;
3098 #endif
3099
3100   /* Assume that each path through the pattern can be null until
3101      proven otherwise.  We set this false at the bottom of switch
3102      statement, to which we get only if a particular path doesn't
3103      match the empty string.  */
3104   boolean path_can_be_null = true;
3105
3106   /* We aren't doing a `succeed_n' to begin with.  */
3107   boolean succeed_n_p = false;
3108
3109   assert (fastmap != NULL && p != NULL);
3110
3111   INIT_FAIL_STACK ();
3112   bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.  */
3113   bufp->fastmap_accurate = 1;       /* It will be when we're done.  */
3114   bufp->can_be_null = 0;
3115
3116   while (1)
3117     {
3118       if (p == pend || *p == succeed)
3119         {
3120           /* We have reached the (effective) end of pattern.  */
3121           if (!FAIL_STACK_EMPTY ())
3122             {
3123               bufp->can_be_null |= path_can_be_null;
3124
3125               /* Reset for next path.  */
3126               path_can_be_null = true;
3127
3128               p = fail_stack.stack[--fail_stack.avail].pointer;
3129
3130               continue;
3131             }
3132           else
3133             break;
3134         }
3135
3136       /* We should never be about to go beyond the end of the pattern.  */
3137       assert (p < pend);
3138
3139       switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
3140         {
3141
3142         /* I guess the idea here is to simply not bother with a fastmap
3143            if a backreference is used, since it's too hard to figure out
3144            the fastmap for the corresponding group.  Setting
3145            `can_be_null' stops `re_search_2' from using the fastmap, so
3146            that is all we do.  */
3147         case duplicate:
3148           bufp->can_be_null = 1;
3149           goto done;
3150
3151
3152       /* Following are the cases which match a character.  These end
3153          with `break'.  */
3154
3155         case exactn:
3156           fastmap[p[1]] = 1;
3157           break;
3158
3159
3160         case charset:
3161           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
3162             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
3163               fastmap[j] = 1;
3164           break;
3165
3166
3167         case charset_not:
3168           /* Chars beyond end of map must be allowed.  */
3169           for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
3170             fastmap[j] = 1;
3171
3172           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
3173             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
3174               fastmap[j] = 1;
3175           break;
3176
3177
3178         case wordchar:
3179           for (j = 0; j < (1 << BYTEWIDTH); j++)
3180             if (SYNTAX (j) == Sword)
3181               fastmap[j] = 1;
3182           break;
3183
3184
3185         case notwordchar:
3186           for (j = 0; j < (1 << BYTEWIDTH); j++)
3187             if (SYNTAX (j) != Sword)
3188               fastmap[j] = 1;
3189           break;
3190
3191
3192         case anychar:
3193           {
3194             int fastmap_newline = fastmap['\n'];
3195
3196             /* `.' matches anything ...  */
3197             for (j = 0; j < (1 << BYTEWIDTH); j++)
3198               fastmap[j] = 1;
3199
3200             /* ... except perhaps newline.  */
3201             if (!(bufp->syntax & RE_DOT_NEWLINE))
3202               fastmap['\n'] = fastmap_newline;
3203
3204             /* Return if we have already set `can_be_null'; if we have,
3205                then the fastmap is irrelevant.  Something's wrong here.  */
3206             else if (bufp->can_be_null)
3207               goto done;
3208
3209             /* Otherwise, have to check alternative paths.  */
3210             break;
3211           }
3212
3213 #ifdef emacs
3214         case syntaxspec:
3215           k = *p++;
3216           for (j = 0; j < (1 << BYTEWIDTH); j++)
3217             if (SYNTAX (j) == (enum syntaxcode) k)
3218               fastmap[j] = 1;
3219           break;
3220
3221
3222         case notsyntaxspec:
3223           k = *p++;
3224           for (j = 0; j < (1 << BYTEWIDTH); j++)
3225             if (SYNTAX (j) != (enum syntaxcode) k)
3226               fastmap[j] = 1;
3227           break;
3228
3229
3230       /* All cases after this match the empty string.  These end with
3231          `continue'.  */
3232
3233
3234         case before_dot:
3235         case at_dot:
3236         case after_dot:
3237           continue;
3238 #endif /* emacs */
3239
3240
3241         case no_op:
3242         case begline:
3243         case endline:
3244         case begbuf:
3245         case endbuf:
3246         case wordbound:
3247         case notwordbound:
3248         case wordbeg:
3249         case wordend:
3250         case push_dummy_failure:
3251           continue;
3252
3253
3254         case jump_n:
3255         case pop_failure_jump:
3256         case maybe_pop_jump:
3257         case jump:
3258         case jump_past_alt:
3259         case dummy_failure_jump:
3260           EXTRACT_NUMBER_AND_INCR (j, p);
3261           p += j;
3262           if (j > 0)
3263             continue;
3264
3265           /* Jump backward implies we just went through the body of a
3266              loop and matched nothing.  Opcode jumped to should be
3267              `on_failure_jump' or `succeed_n'.  Just treat it like an
3268              ordinary jump.  For a * loop, it has pushed its failure
3269              point already; if so, discard that as redundant.  */
3270           if ((re_opcode_t) *p != on_failure_jump
3271               && (re_opcode_t) *p != succeed_n)
3272             continue;
3273
3274           p++;
3275           EXTRACT_NUMBER_AND_INCR (j, p);
3276           p += j;
3277
3278           /* If what's on the stack is where we are now, pop it.  */
3279           if (!FAIL_STACK_EMPTY ()
3280               && fail_stack.stack[fail_stack.avail - 1].pointer == p)
3281             fail_stack.avail--;
3282
3283           continue;