"Fossies" - the Fresh Open Source Software Archive

Member "rename-1.3/regex.c" (4 Sep 2001, 176752 Bytes) of package /linux/privat/old/rename-1.3.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /* Extended regular expression matching and search library,
    2    version 0.12.
    3    (Implements POSIX draft P10003.2/D11.2, except for
    4    internationalization features.)
    5 
    6    Copyright (C) 1993, 1994, 1995 Free Software Foundation, Inc.
    7 
    8    This program is free software; you can redistribute it and/or modify
    9    it under the terms of the GNU General Public License as published by
   10    the Free Software Foundation; either version 2, or (at your option)
   11    any later version.
   12 
   13    This program is distributed in the hope that it will be useful,
   14    but WITHOUT ANY WARRANTY; without even the implied warranty of
   15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   16    GNU General Public License for more details.
   17 
   18    You should have received a copy of the GNU General Public License
   19    along with this program; if not, write to the Free Software
   20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
   21 
   22 /* AIX requires this to be the first thing in the file. */
   23 #if defined (_AIX) && !defined (REGEX_MALLOC)
   24   #pragma alloca
   25 #endif
   26 
   27 #undef  _GNU_SOURCE
   28 #define _GNU_SOURCE
   29 
   30 #ifdef HAVE_CONFIG_H
   31 #include "config.h"
   32 #endif
   33 
   34 /* We need this for `regex.h', and perhaps for the Emacs include files.  */
   35 #include <sys/types.h>
   36 
   37 /* This is for other GNU distributions with internationalized messages.  */
   38 #if HAVE_LIBINTL_H || defined (_LIBC)
   39 # include <libintl.h>
   40 #else
   41 # define gettext(msgid) (msgid)
   42 #endif
   43 
   44 #ifndef gettext_noop
   45 /* This define is so xgettext can find the internationalizable
   46    strings.  */
   47 #define gettext_noop(String) String
   48 #endif
   49 
   50 /* The `emacs' switch turns on certain matching commands
   51    that make sense only in Emacs. */
   52 #ifdef emacs
   53 
   54 #include "lisp.h"
   55 #include "buffer.h"
   56 #include "syntax.h"
   57 
   58 #else  /* not emacs */
   59 
   60 /* If we are not linking with Emacs proper,
   61    we can't use the relocating allocator
   62    even if config.h says that we can.  */
   63 #undef REL_ALLOC
   64 
   65 #if defined (STDC_HEADERS) || defined (_LIBC)
   66 #include <stdlib.h>
   67 #else
   68 char *malloc ();
   69 char *realloc ();
   70 #endif
   71 
   72 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
   73    If nothing else has been done, use the method below.  */
   74 #ifdef INHIBIT_STRING_HEADER
   75 #if !(defined (HAVE_BZERO) && defined (HAVE_BCOPY))
   76 #if !defined (bzero) && !defined (bcopy)
   77 #undef INHIBIT_STRING_HEADER
   78 #endif
   79 #endif
   80 #endif
   81 
   82 /* This is the normal way of making sure we have a bcopy and a bzero.
   83    This is used in most programs--a few other programs avoid this
   84    by defining INHIBIT_STRING_HEADER.  */
   85 #ifndef INHIBIT_STRING_HEADER
   86 #if defined (HAVE_STRING_H) || defined (STDC_HEADERS) || defined (_LIBC)
   87 #include <string.h>
   88 #ifndef bcmp
   89 #define bcmp(s1, s2, n) memcmp ((s1), (s2), (n))
   90 #endif
   91 #ifndef bcopy
   92 #define bcopy(s, d, n)  memcpy ((d), (s), (n))
   93 #endif
   94 #ifndef bzero
   95 #define bzero(s, n) memset ((s), 0, (n))
   96 #endif
   97 #else
   98 #include <strings.h>
   99 #endif
  100 #endif
  101 
  102 /* Define the syntax stuff for \<, \>, etc.  */
  103 
  104 /* This must be nonzero for the wordchar and notwordchar pattern
  105    commands in re_match_2.  */
  106 #ifndef Sword
  107 #define Sword 1
  108 #endif
  109 
  110 #ifdef SWITCH_ENUM_BUG
  111 #define SWITCH_ENUM_CAST(x) ((int)(x))
  112 #else
  113 #define SWITCH_ENUM_CAST(x) (x)
  114 #endif
  115 
  116 #ifdef SYNTAX_TABLE
  117 
  118 extern char *re_syntax_table;
  119 
  120 #else /* not SYNTAX_TABLE */
  121 
  122 /* How many characters in the character set.  */
  123 #define CHAR_SET_SIZE 256
  124 
  125 static char re_syntax_table[CHAR_SET_SIZE];
  126 
  127 static void
  128 init_syntax_once ()
  129 {
  130    register int c;
  131    static int done = 0;
  132 
  133    if (done)
  134      return;
  135 
  136    bzero (re_syntax_table, sizeof re_syntax_table);
  137 
  138    for (c = 'a'; c <= 'z'; c++)
  139      re_syntax_table[c] = Sword;
  140 
  141    for (c = 'A'; c <= 'Z'; c++)
  142      re_syntax_table[c] = Sword;
  143 
  144    for (c = '0'; c <= '9'; c++)
  145      re_syntax_table[c] = Sword;
  146 
  147    re_syntax_table['_'] = Sword;
  148 
  149    done = 1;
  150 }
  151 
  152 #endif /* not SYNTAX_TABLE */
  153 
  154 #define SYNTAX(c) re_syntax_table[c]
  155 
  156 #endif /* not emacs */
  157 
  158 /* Get the interface, including the syntax bits.  */
  159 #include "regex.h"
  160 
  161 /* isalpha etc. are used for the character classes.  */
  162 #include <ctype.h>
  163 
  164 /* Jim Meyering writes:
  165 
  166    "... Some ctype macros are valid only for character codes that
  167    isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
  168    using /bin/cc or gcc but without giving an ansi option).  So, all
  169    ctype uses should be through macros like ISPRINT...  If
  170    STDC_HEADERS is defined, then autoconf has verified that the ctype
  171    macros don't need to be guarded with references to isascii. ...
  172    Defining isascii to 1 should let any compiler worth its salt
  173    eliminate the && through constant folding."  */
  174 
  175 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII))
  176 #define IN_CTYPE_DOMAIN(c) 1
  177 #else
  178 #define IN_CTYPE_DOMAIN(c) isascii(c)
  179 #endif
  180 
  181 #ifdef isblank
  182 #define ISBLANK(c) (IN_CTYPE_DOMAIN (c) && isblank (c))
  183 #else
  184 #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
  185 #endif
  186 #ifdef isgraph
  187 #define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isgraph (c))
  188 #else
  189 #define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isprint (c) && !isspace (c))
  190 #endif
  191 
  192 #define ISPRINT(c) (IN_CTYPE_DOMAIN (c) && isprint (c))
  193 #define ISDIGIT(c) (IN_CTYPE_DOMAIN (c) && isdigit (c))
  194 #define ISALNUM(c) (IN_CTYPE_DOMAIN (c) && isalnum (c))
  195 #define ISALPHA(c) (IN_CTYPE_DOMAIN (c) && isalpha (c))
  196 #define ISCNTRL(c) (IN_CTYPE_DOMAIN (c) && iscntrl (c))
  197 #define ISLOWER(c) (IN_CTYPE_DOMAIN (c) && islower (c))
  198 #define ISPUNCT(c) (IN_CTYPE_DOMAIN (c) && ispunct (c))
  199 #define ISSPACE(c) (IN_CTYPE_DOMAIN (c) && isspace (c))
  200 #define ISUPPER(c) (IN_CTYPE_DOMAIN (c) && isupper (c))
  201 #define ISXDIGIT(c) (IN_CTYPE_DOMAIN (c) && isxdigit (c))
  202 
  203 #ifndef NULL
  204 #define NULL (void *)0
  205 #endif
  206 
  207 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
  208    since ours (we hope) works properly with all combinations of
  209    machines, compilers, `char' and `unsigned char' argument types.
  210    (Per Bothner suggested the basic approach.)  */
  211 #undef SIGN_EXTEND_CHAR
  212 #if __STDC__
  213 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
  214 #else  /* not __STDC__ */
  215 /* As in Harbison and Steele.  */
  216 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
  217 #endif
  218 
  219 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
  220    use `alloca' instead of `malloc'.  This is because using malloc in
  221    re_search* or re_match* could cause memory leaks when C-g is used in
  222    Emacs; also, malloc is slower and causes storage fragmentation.  On
  223    the other hand, malloc is more portable, and easier to debug.
  224 
  225    Because we sometimes use alloca, some routines have to be macros,
  226    not functions -- `alloca'-allocated space disappears at the end of the
  227    function it is called in.  */
  228 
  229 #ifdef REGEX_MALLOC
  230 
  231 #define REGEX_ALLOCATE malloc
  232 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
  233 #define REGEX_FREE free
  234 
  235 #else /* not REGEX_MALLOC  */
  236 
  237 /* Emacs already defines alloca, sometimes.  */
  238 #ifndef alloca
  239 
  240 /* Make alloca work the best possible way.  */
  241 #ifdef __GNUC__
  242 #define alloca __builtin_alloca
  243 #else /* not __GNUC__ */
  244 #if HAVE_ALLOCA_H
  245 #include <alloca.h>
  246 #else /* not __GNUC__ or HAVE_ALLOCA_H */
  247 #if 0 /* It is a bad idea to declare alloca.  We always cast the result.  */
  248 #ifndef _AIX /* Already did AIX, up at the top.  */
  249 char *alloca ();
  250 #endif /* not _AIX */
  251 #endif
  252 #endif /* not HAVE_ALLOCA_H */
  253 #endif /* not __GNUC__ */
  254 
  255 #endif /* not alloca */
  256 
  257 #define REGEX_ALLOCATE alloca
  258 
  259 /* Assumes a `char *destination' variable.  */
  260 #define REGEX_REALLOCATE(source, osize, nsize)              \
  261   (destination = (char *) alloca (nsize),               \
  262    bcopy (source, destination, osize),                  \
  263    destination)
  264 
  265 /* No need to do anything to free, after alloca.  */
  266 #define REGEX_FREE(arg) ((void)0) /* Do nothing!  But inhibit gcc warning.  */
  267 
  268 #endif /* not REGEX_MALLOC */
  269 
  270 /* Define how to allocate the failure stack.  */
  271 
  272 #if defined (REL_ALLOC) && defined (REGEX_MALLOC)
  273 
  274 #define REGEX_ALLOCATE_STACK(size)              \
  275   r_alloc (&failure_stack_ptr, (size))
  276 #define REGEX_REALLOCATE_STACK(source, osize, nsize)        \
  277   r_re_alloc (&failure_stack_ptr, (nsize))
  278 #define REGEX_FREE_STACK(ptr)                   \
  279   r_alloc_free (&failure_stack_ptr)
  280 
  281 #else /* not using relocating allocator */
  282 
  283 #ifdef REGEX_MALLOC
  284 
  285 #define REGEX_ALLOCATE_STACK malloc
  286 #define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
  287 #define REGEX_FREE_STACK free
  288 
  289 #else /* not REGEX_MALLOC */
  290 
  291 #define REGEX_ALLOCATE_STACK alloca
  292 
  293 #define REGEX_REALLOCATE_STACK(source, osize, nsize)            \
  294    REGEX_REALLOCATE (source, osize, nsize)
  295 /* No need to explicitly free anything.  */
  296 #define REGEX_FREE_STACK(arg)
  297 
  298 #endif /* not REGEX_MALLOC */
  299 #endif /* not using relocating allocator */
  300 
  301 
  302 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
  303    `string1' or just past its end.  This works if PTR is NULL, which is
  304    a good thing.  */
  305 #define FIRST_STRING_P(ptr)                     \
  306   (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
  307 
  308 /* (Re)Allocate N items of type T using malloc, or fail.  */
  309 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
  310 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
  311 #define RETALLOC_IF(addr, n, t) \
  312   if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
  313 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
  314 
  315 #define BYTEWIDTH 8 /* In bits.  */
  316 
  317 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
  318 
  319 #undef MAX
  320 #undef MIN
  321 #define MAX(a, b) ((a) > (b) ? (a) : (b))
  322 #define MIN(a, b) ((a) < (b) ? (a) : (b))
  323 
  324 typedef char boolean;
  325 #define false 0
  326 #define true 1
  327 
  328 static int re_match_2_internal ();
  329 
  330 /* These are the command codes that appear in compiled regular
  331    expressions.  Some opcodes are followed by argument bytes.  A
  332    command code can specify any interpretation whatsoever for its
  333    arguments.  Zero bytes may appear in the compiled regular expression.  */
  334 
  335 typedef enum
  336 {
  337   no_op = 0,
  338 
  339   /* Succeed right away--no more backtracking.  */
  340   succeed,
  341 
  342         /* Followed by one byte giving n, then by n literal bytes.  */
  343   exactn,
  344 
  345         /* Matches any (more or less) character.  */
  346   anychar,
  347 
  348         /* Matches any one char belonging to specified set.  First
  349            following byte is number of bitmap bytes.  Then come bytes
  350            for a bitmap saying which chars are in.  Bits in each byte
  351            are ordered low-bit-first.  A character is in the set if its
  352            bit is 1.  A character too large to have a bit in the map is
  353            automatically not in the set.  */
  354   charset,
  355 
  356         /* Same parameters as charset, but match any character that is
  357            not one of those specified.  */
  358   charset_not,
  359 
  360         /* Start remembering the text that is matched, for storing in a
  361            register.  Followed by one byte with the register number, in
  362            the range 0 to one less than the pattern buffer's re_nsub
  363            field.  Then followed by one byte with the number of groups
  364            inner to this one.  (This last has to be part of the
  365            start_memory only because we need it in the on_failure_jump
  366            of re_match_2.)  */
  367   start_memory,
  368 
  369         /* Stop remembering the text that is matched and store it in a
  370            memory register.  Followed by one byte with the register
  371            number, in the range 0 to one less than `re_nsub' in the
  372            pattern buffer, and one byte with the number of inner groups,
  373            just like `start_memory'.  (We need the number of inner
  374            groups here because we don't have any easy way of finding the
  375            corresponding start_memory when we're at a stop_memory.)  */
  376   stop_memory,
  377 
  378         /* Match a duplicate of something remembered. Followed by one
  379            byte containing the register number.  */
  380   duplicate,
  381 
  382         /* Fail unless at beginning of line.  */
  383   begline,
  384 
  385         /* Fail unless at end of line.  */
  386   endline,
  387 
  388         /* Succeeds if at beginning of buffer (if emacs) or at beginning
  389            of string to be matched (if not).  */
  390   begbuf,
  391 
  392         /* Analogously, for end of buffer/string.  */
  393   endbuf,
  394 
  395         /* Followed by two byte relative address to which to jump.  */
  396   jump,
  397 
  398     /* Same as jump, but marks the end of an alternative.  */
  399   jump_past_alt,
  400 
  401         /* Followed by two-byte relative address of place to resume at
  402            in case of failure.  */
  403   on_failure_jump,
  404 
  405         /* Like on_failure_jump, but pushes a placeholder instead of the
  406            current string position when executed.  */
  407   on_failure_keep_string_jump,
  408 
  409         /* Throw away latest failure point and then jump to following
  410            two-byte relative address.  */
  411   pop_failure_jump,
  412 
  413         /* Change to pop_failure_jump if know won't have to backtrack to
  414            match; otherwise change to jump.  This is used to jump
  415            back to the beginning of a repeat.  If what follows this jump
  416            clearly won't match what the repeat does, such that we can be
  417            sure that there is no use backtracking out of repetitions
  418            already matched, then we change it to a pop_failure_jump.
  419            Followed by two-byte address.  */
  420   maybe_pop_jump,
  421 
  422         /* Jump to following two-byte address, and push a dummy failure
  423            point. This failure point will be thrown away if an attempt
  424            is made to use it for a failure.  A `+' construct makes this
  425            before the first repeat.  Also used as an intermediary kind
  426            of jump when compiling an alternative.  */
  427   dummy_failure_jump,
  428 
  429     /* Push a dummy failure point and continue.  Used at the end of
  430        alternatives.  */
  431   push_dummy_failure,
  432 
  433         /* Followed by two-byte relative address and two-byte number n.
  434            After matching N times, jump to the address upon failure.  */
  435   succeed_n,
  436 
  437         /* Followed by two-byte relative address, and two-byte number n.
  438            Jump to the address N times, then fail.  */
  439   jump_n,
  440 
  441         /* Set the following two-byte relative address to the
  442            subsequent two-byte number.  The address *includes* the two
  443            bytes of number.  */
  444   set_number_at,
  445 
  446   wordchar, /* Matches any word-constituent character.  */
  447   notwordchar,  /* Matches any char that is not a word-constituent.  */
  448 
  449   wordbeg,  /* Succeeds if at word beginning.  */
  450   wordend,  /* Succeeds if at word end.  */
  451 
  452   wordbound,    /* Succeeds if at a word boundary.  */
  453   notwordbound  /* Succeeds if not at a word boundary.  */
  454 
  455 #ifdef emacs
  456   ,before_dot,  /* Succeeds if before point.  */
  457   at_dot,   /* Succeeds if at point.  */
  458   after_dot,    /* Succeeds if after point.  */
  459 
  460     /* Matches any character whose syntax is specified.  Followed by
  461            a byte which contains a syntax code, e.g., Sword.  */
  462   syntaxspec,
  463 
  464     /* Matches any character whose syntax is not that specified.  */
  465   notsyntaxspec
  466 #endif /* emacs */
  467 } re_opcode_t;
  468 
  469 /* Common operations on the compiled pattern.  */
  470 
  471 /* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
  472 
  473 #define STORE_NUMBER(destination, number)               \
  474   do {                                  \
  475     (destination)[0] = (number) & 0377;                 \
  476     (destination)[1] = (number) >> 8;                   \
  477   } while (0)
  478 
  479 /* Same as STORE_NUMBER, except increment DESTINATION to
  480    the byte after where the number is stored.  Therefore, DESTINATION
  481    must be an lvalue.  */
  482 
  483 #define STORE_NUMBER_AND_INCR(destination, number)          \
  484   do {                                  \
  485     STORE_NUMBER (destination, number);                 \
  486     (destination) += 2;                         \
  487   } while (0)
  488 
  489 /* Put into DESTINATION a number stored in two contiguous bytes starting
  490    at SOURCE.  */
  491 
  492 #define EXTRACT_NUMBER(destination, source)             \
  493   do {                                  \
  494     (destination) = *(source) & 0377;                   \
  495     (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8;       \
  496   } while (0)
  497 
  498 #ifdef DEBUG
  499 static void
  500 extract_number (dest, source)
  501     int *dest;
  502     unsigned char *source;
  503 {
  504   int temp = SIGN_EXTEND_CHAR (*(source + 1));
  505   *dest = *source & 0377;
  506   *dest += temp << 8;
  507 }
  508 
  509 #ifndef EXTRACT_MACROS /* To debug the macros.  */
  510 #undef EXTRACT_NUMBER
  511 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
  512 #endif /* not EXTRACT_MACROS */
  513 
  514 #endif /* DEBUG */
  515 
  516 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
  517    SOURCE must be an lvalue.  */
  518 
  519 #define EXTRACT_NUMBER_AND_INCR(destination, source)            \
  520   do {                                  \
  521     EXTRACT_NUMBER (destination, source);               \
  522     (source) += 2;                          \
  523   } while (0)
  524 
  525 #ifdef DEBUG
  526 static void
  527 extract_number_and_incr (destination, source)
  528     int *destination;
  529     unsigned char **source;
  530 {
  531   extract_number (destination, *source);
  532   *source += 2;
  533 }
  534 
  535 #ifndef EXTRACT_MACROS
  536 #undef EXTRACT_NUMBER_AND_INCR
  537 #define EXTRACT_NUMBER_AND_INCR(dest, src) \
  538   extract_number_and_incr (&dest, &src)
  539 #endif /* not EXTRACT_MACROS */
  540 
  541 #endif /* DEBUG */
  542 
  543 /* If DEBUG is defined, Regex prints many voluminous messages about what
  544    it is doing (if the variable `debug' is nonzero).  If linked with the
  545    main program in `iregex.c', you can enter patterns and strings
  546    interactively.  And if linked with the main program in `main.c' and
  547    the other test files, you can run the already-written tests.  */
  548 
  549 #ifdef DEBUG
  550 
  551 /* We use standard I/O for debugging.  */
  552 #include <stdio.h>
  553 
  554 /* It is useful to test things that ``must'' be true when debugging.  */
  555 #include <assert.h>
  556 
  557 static int debug = 0;
  558 
  559 #define DEBUG_STATEMENT(e) e
  560 #define DEBUG_PRINT1(x) if (debug) printf (x)
  561 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
  562 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
  563 #define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
  564 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)               \
  565   if (debug) print_partial_compiled_pattern (s, e)
  566 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)          \
  567   if (debug) print_double_string (w, s1, sz1, s2, sz2)
  568 
  569 
  570 /* Print the fastmap in human-readable form.  */
  571 
  572 void
  573 print_fastmap (fastmap)
  574     char *fastmap;
  575 {
  576   unsigned was_a_range = 0;
  577   unsigned i = 0;
  578 
  579   while (i < (1 << BYTEWIDTH))
  580     {
  581       if (fastmap[i++])
  582     {
  583       was_a_range = 0;
  584           putchar (i - 1);
  585           while (i < (1 << BYTEWIDTH)  &&  fastmap[i])
  586             {
  587               was_a_range = 1;
  588               i++;
  589             }
  590       if (was_a_range)
  591             {
  592               printf ("-");
  593               putchar (i - 1);
  594             }
  595         }
  596     }
  597   putchar ('\n');
  598 }
  599 
  600 
  601 /* Print a compiled pattern string in human-readable form, starting at
  602    the START pointer into it and ending just before the pointer END.  */
  603 
  604 void
  605 print_partial_compiled_pattern (start, end)
  606     unsigned char *start;
  607     unsigned char *end;
  608 {
  609   int mcnt, mcnt2;
  610   unsigned char *p = start;
  611   unsigned char *pend = end;
  612 
  613   if (start == NULL)
  614     {
  615       printf ("(null)\n");
  616       return;
  617     }
  618 
  619   /* Loop over pattern commands.  */
  620   while (p < pend)
  621     {
  622       printf ("%d:\t", p - start);
  623 
  624       switch ((re_opcode_t) *p++)
  625     {
  626         case no_op:
  627           printf ("/no_op");
  628           break;
  629 
  630     case exactn:
  631       mcnt = *p++;
  632           printf ("/exactn/%d", mcnt);
  633           do
  634         {
  635               putchar ('/');
  636           putchar (*p++);
  637             }
  638           while (--mcnt);
  639           break;
  640 
  641     case start_memory:
  642           mcnt = *p++;
  643           printf ("/start_memory/%d/%d", mcnt, *p++);
  644           break;
  645 
  646     case stop_memory:
  647           mcnt = *p++;
  648       printf ("/stop_memory/%d/%d", mcnt, *p++);
  649           break;
  650 
  651     case duplicate:
  652       printf ("/duplicate/%d", *p++);
  653       break;
  654 
  655     case anychar:
  656       printf ("/anychar");
  657       break;
  658 
  659     case charset:
  660         case charset_not:
  661           {
  662             register int c, last = -100;
  663         register int in_range = 0;
  664 
  665         printf ("/charset [%s",
  666                 (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
  667 
  668             assert (p + *p < pend);
  669 
  670             for (c = 0; c < 256; c++)
  671           if (c / 8 < *p
  672           && (p[1 + (c/8)] & (1 << (c % 8))))
  673         {
  674           /* Are we starting a range?  */
  675           if (last + 1 == c && ! in_range)
  676             {
  677               putchar ('-');
  678               in_range = 1;
  679             }
  680           /* Have we broken a range?  */
  681           else if (last + 1 != c && in_range)
  682               {
  683               putchar (last);
  684               in_range = 0;
  685             }
  686 
  687           if (! in_range)
  688             putchar (c);
  689 
  690           last = c;
  691               }
  692 
  693         if (in_range)
  694           putchar (last);
  695 
  696         putchar (']');
  697 
  698         p += 1 + *p;
  699       }
  700       break;
  701 
  702     case begline:
  703       printf ("/begline");
  704           break;
  705 
  706     case endline:
  707           printf ("/endline");
  708           break;
  709 
  710     case on_failure_jump:
  711           extract_number_and_incr (&mcnt, &p);
  712       printf ("/on_failure_jump to %d", p + mcnt - start);
  713           break;
  714 
  715     case on_failure_keep_string_jump:
  716           extract_number_and_incr (&mcnt, &p);
  717       printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
  718           break;
  719 
  720     case dummy_failure_jump:
  721           extract_number_and_incr (&mcnt, &p);
  722       printf ("/dummy_failure_jump to %d", p + mcnt - start);
  723           break;
  724 
  725     case push_dummy_failure:
  726           printf ("/push_dummy_failure");
  727           break;
  728 
  729         case maybe_pop_jump:
  730           extract_number_and_incr (&mcnt, &p);
  731       printf ("/maybe_pop_jump to %d", p + mcnt - start);
  732       break;
  733 
  734         case pop_failure_jump:
  735       extract_number_and_incr (&mcnt, &p);
  736       printf ("/pop_failure_jump to %d", p + mcnt - start);
  737       break;
  738 
  739         case jump_past_alt:
  740       extract_number_and_incr (&mcnt, &p);
  741       printf ("/jump_past_alt to %d", p + mcnt - start);
  742       break;
  743 
  744         case jump:
  745       extract_number_and_incr (&mcnt, &p);
  746       printf ("/jump to %d", p + mcnt - start);
  747       break;
  748 
  749         case succeed_n:
  750           extract_number_and_incr (&mcnt, &p);
  751           extract_number_and_incr (&mcnt2, &p);
  752       printf ("/succeed_n to %d, %d times", p + mcnt - start, mcnt2);
  753           break;
  754 
  755         case jump_n:
  756           extract_number_and_incr (&mcnt, &p);
  757           extract_number_and_incr (&mcnt2, &p);
  758       printf ("/jump_n to %d, %d times", p + mcnt - start, mcnt2);
  759           break;
  760 
  761         case set_number_at:
  762           extract_number_and_incr (&mcnt, &p);
  763           extract_number_and_incr (&mcnt2, &p);
  764       printf ("/set_number_at location %d to %d", p + mcnt - start, mcnt2);
  765           break;
  766 
  767         case wordbound:
  768       printf ("/wordbound");
  769       break;
  770 
  771     case notwordbound:
  772       printf ("/notwordbound");
  773           break;
  774 
  775     case wordbeg:
  776       printf ("/wordbeg");
  777       break;
  778 
  779     case wordend:
  780       printf ("/wordend");
  781 
  782 #ifdef emacs
  783     case before_dot:
  784       printf ("/before_dot");
  785           break;
  786 
  787     case at_dot:
  788       printf ("/at_dot");
  789           break;
  790 
  791     case after_dot:
  792       printf ("/after_dot");
  793           break;
  794 
  795     case syntaxspec:
  796           printf ("/syntaxspec");
  797       mcnt = *p++;
  798       printf ("/%d", mcnt);
  799           break;
  800 
  801     case notsyntaxspec:
  802           printf ("/notsyntaxspec");
  803       mcnt = *p++;
  804       printf ("/%d", mcnt);
  805       break;
  806 #endif /* emacs */
  807 
  808     case wordchar:
  809       printf ("/wordchar");
  810           break;
  811 
  812     case notwordchar:
  813       printf ("/notwordchar");
  814           break;
  815 
  816     case begbuf:
  817       printf ("/begbuf");
  818           break;
  819 
  820     case endbuf:
  821       printf ("/endbuf");
  822           break;
  823 
  824         default:
  825           printf ("?%d", *(p-1));
  826     }
  827 
  828       putchar ('\n');
  829     }
  830 
  831   printf ("%d:\tend of pattern.\n", p - start);
  832 }
  833 
  834 
  835 void
  836 print_compiled_pattern (bufp)
  837     struct re_pattern_buffer *bufp;
  838 {
  839   unsigned char *buffer = bufp->buffer;
  840 
  841   print_partial_compiled_pattern (buffer, buffer + bufp->used);
  842   printf ("%d bytes used/%d bytes allocated.\n", bufp->used, bufp->allocated);
  843 
  844   if (bufp->fastmap_accurate && bufp->fastmap)
  845     {
  846       printf ("fastmap: ");
  847       print_fastmap (bufp->fastmap);
  848     }
  849 
  850   printf ("re_nsub: %d\t", bufp->re_nsub);
  851   printf ("regs_alloc: %d\t", bufp->regs_allocated);
  852   printf ("can_be_null: %d\t", bufp->can_be_null);
  853   printf ("newline_anchor: %d\n", bufp->newline_anchor);
  854   printf ("no_sub: %d\t", bufp->no_sub);
  855   printf ("not_bol: %d\t", bufp->not_bol);
  856   printf ("not_eol: %d\t", bufp->not_eol);
  857   printf ("syntax: %d\n", bufp->syntax);
  858   /* Perhaps we should print the translate table?  */
  859 }
  860 
  861 
  862 void
  863 print_double_string (where, string1, size1, string2, size2)
  864     const char *where;
  865     const char *string1;
  866     const char *string2;
  867     int size1;
  868     int size2;
  869 {
  870   unsigned this_char;
  871 
  872   if (where == NULL)
  873     printf ("(null)");
  874   else
  875     {
  876       if (FIRST_STRING_P (where))
  877         {
  878           for (this_char = where - string1; this_char < size1; this_char++)
  879             putchar (string1[this_char]);
  880 
  881           where = string2;
  882         }
  883 
  884       for (this_char = where - string2; this_char < size2; this_char++)
  885         putchar (string2[this_char]);
  886     }
  887 }
  888 
  889 #else /* not DEBUG */
  890 
  891 #undef assert
  892 #define assert(e)
  893 
  894 #define DEBUG_STATEMENT(e)
  895 #define DEBUG_PRINT1(x)
  896 #define DEBUG_PRINT2(x1, x2)
  897 #define DEBUG_PRINT3(x1, x2, x3)
  898 #define DEBUG_PRINT4(x1, x2, x3, x4)
  899 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
  900 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
  901 
  902 #endif /* not DEBUG */
  903 
  904 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
  905    also be assigned to arbitrarily: each pattern buffer stores its own
  906    syntax, so it can be changed between regex compilations.  */
  907 /* This has no initializer because initialized variables in Emacs
  908    become read-only after dumping.  */
  909 reg_syntax_t re_syntax_options;
  910 
  911 
  912 /* Specify the precise syntax of regexps for compilation.  This provides
  913    for compatibility for various utilities which historically have
  914    different, incompatible syntaxes.
  915 
  916    The argument SYNTAX is a bit mask comprised of the various bits
  917    defined in regex.h.  We return the old syntax.  */
  918 
  919 reg_syntax_t
  920 re_set_syntax (syntax)
  921     reg_syntax_t syntax;
  922 {
  923   reg_syntax_t ret = re_syntax_options;
  924 
  925   re_syntax_options = syntax;
  926   return ret;
  927 }
  928 
  929 /* This table gives an error message for each of the error codes listed
  930    in regex.h.  Obviously the order here has to be same as there.
  931    POSIX doesn't require that we do anything for REG_NOERROR,
  932    but why not be nice?  */
  933 
  934 static const char *re_error_msgid[] =
  935   {
  936     gettext_noop ("Success"),   /* REG_NOERROR */
  937     gettext_noop ("No match"),  /* REG_NOMATCH */
  938     gettext_noop ("Invalid regular expression"), /* REG_BADPAT */
  939     gettext_noop ("Invalid collation character"), /* REG_ECOLLATE */
  940     gettext_noop ("Invalid character class name"), /* REG_ECTYPE */
  941     gettext_noop ("Trailing backslash"), /* REG_EESCAPE */
  942     gettext_noop ("Invalid back reference"), /* REG_ESUBREG */
  943     gettext_noop ("Unmatched [ or [^"), /* REG_EBRACK */
  944     gettext_noop ("Unmatched ( or \\("), /* REG_EPAREN */
  945     gettext_noop ("Unmatched \\{"), /* REG_EBRACE */
  946     gettext_noop ("Invalid content of \\{\\}"), /* REG_BADBR */
  947     gettext_noop ("Invalid range end"), /* REG_ERANGE */
  948     gettext_noop ("Memory exhausted"), /* REG_ESPACE */
  949     gettext_noop ("Invalid preceding regular expression"), /* REG_BADRPT */
  950     gettext_noop ("Premature end of regular expression"), /* REG_EEND */
  951     gettext_noop ("Regular expression too big"), /* REG_ESIZE */
  952     gettext_noop ("Unmatched ) or \\)"), /* REG_ERPAREN */
  953   };
  954 
  955 /* Avoiding alloca during matching, to placate r_alloc.  */
  956 
  957 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
  958    searching and matching functions should not call alloca.  On some
  959    systems, alloca is implemented in terms of malloc, and if we're
  960    using the relocating allocator routines, then malloc could cause a
  961    relocation, which might (if the strings being searched are in the
  962    ralloc heap) shift the data out from underneath the regexp
  963    routines.
  964 
  965    Here's another reason to avoid allocation: Emacs
  966    processes input from X in a signal handler; processing X input may
  967    call malloc; if input arrives while a matching routine is calling
  968    malloc, then we're scrod.  But Emacs can't just block input while
  969    calling matching routines; then we don't notice interrupts when
  970    they come in.  So, Emacs blocks input around all regexp calls
  971    except the matching calls, which it leaves unprotected, in the
  972    faith that they will not malloc.  */
  973 
  974 /* Normally, this is fine.  */
  975 #define MATCH_MAY_ALLOCATE
  976 
  977 /* When using GNU C, we are not REALLY using the C alloca, no matter
  978    what config.h may say.  So don't take precautions for it.  */
  979 #ifdef __GNUC__
  980 #undef C_ALLOCA
  981 #endif
  982 
  983 /* The match routines may not allocate if (1) they would do it with malloc
  984    and (2) it's not safe for them to use malloc.
  985    Note that if REL_ALLOC is defined, matching would not use malloc for the
  986    failure stack, but we would still use it for the register vectors;
  987    so REL_ALLOC should not affect this.  */
  988 #if (defined (C_ALLOCA) || defined (REGEX_MALLOC)) && defined (emacs)
  989 #undef MATCH_MAY_ALLOCATE
  990 #endif
  991 
  992 
  993 /* Failure stack declarations and macros; both re_compile_fastmap and
  994    re_match_2 use a failure stack.  These have to be macros because of
  995    REGEX_ALLOCATE_STACK.  */
  996 
  997 
  998 /* Number of failure points for which to initially allocate space
  999    when matching.  If this number is exceeded, we allocate more
 1000    space, so it is not a hard limit.  */
 1001 #ifndef INIT_FAILURE_ALLOC
 1002 #define INIT_FAILURE_ALLOC 5
 1003 #endif
 1004 
 1005 /* Roughly the maximum number of failure points on the stack.  Would be
 1006    exactly that if always used MAX_FAILURE_SPACE each time we failed.
 1007    This is a variable only so users of regex can assign to it; we never
 1008    change it ourselves.  */
 1009 #if defined (MATCH_MAY_ALLOCATE)
 1010 int re_max_failures = 20000;
 1011 #else
 1012 int re_max_failures = 2000;
 1013 #endif
 1014 
 1015 union fail_stack_elt
 1016 {
 1017   unsigned char *pointer;
 1018   int integer;
 1019 };
 1020 
 1021 typedef union fail_stack_elt fail_stack_elt_t;
 1022 
 1023 typedef struct
 1024 {
 1025   fail_stack_elt_t *stack;
 1026   unsigned size;
 1027   unsigned avail;           /* Offset of next open position.  */
 1028 } fail_stack_type;
 1029 
 1030 #define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
 1031 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
 1032 #define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
 1033 
 1034 
 1035 /* Define macros to initialize and free the failure stack.
 1036    Do `return -2' if the alloc fails.  */
 1037 
 1038 #ifdef MATCH_MAY_ALLOCATE
 1039 #define INIT_FAIL_STACK()                       \
 1040   do {                                  \
 1041     fail_stack.stack = (fail_stack_elt_t *)             \
 1042       REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t));    \
 1043                                     \
 1044     if (fail_stack.stack == NULL)                   \
 1045       return -2;                            \
 1046                                     \
 1047     fail_stack.size = INIT_FAILURE_ALLOC;               \
 1048     fail_stack.avail = 0;                       \
 1049   } while (0)
 1050 
 1051 #define RESET_FAIL_STACK()  REGEX_FREE_STACK (fail_stack.stack)
 1052 #else
 1053 #define INIT_FAIL_STACK()                       \
 1054   do {                                  \
 1055     fail_stack.avail = 0;                       \
 1056   } while (0)
 1057 
 1058 #define RESET_FAIL_STACK()
 1059 #endif
 1060 
 1061 
 1062 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
 1063 
 1064    Return 1 if succeeds, and 0 if either ran out of memory
 1065    allocating space for it or it was already too large.
 1066 
 1067    REGEX_REALLOCATE_STACK requires `destination' be declared.   */
 1068 
 1069 #define DOUBLE_FAIL_STACK(fail_stack)                   \
 1070   ((fail_stack).size > re_max_failures * MAX_FAILURE_ITEMS      \
 1071    ? 0                                  \
 1072    : ((fail_stack).stack = (fail_stack_elt_t *)             \
 1073         REGEX_REALLOCATE_STACK ((fail_stack).stack,             \
 1074           (fail_stack).size * sizeof (fail_stack_elt_t),        \
 1075           ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)),    \
 1076                                     \
 1077       (fail_stack).stack == NULL                    \
 1078       ? 0                               \
 1079       : ((fail_stack).size <<= 1,                   \
 1080          1)))
 1081 
 1082 
 1083 /* Push pointer POINTER on FAIL_STACK.
 1084    Return 1 if was able to do so and 0 if ran out of memory allocating
 1085    space to do so.  */
 1086 #define PUSH_PATTERN_OP(POINTER, FAIL_STACK)                \
 1087   ((FAIL_STACK_FULL ()                          \
 1088     && !DOUBLE_FAIL_STACK (FAIL_STACK))                 \
 1089    ? 0                                  \
 1090    : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER,   \
 1091       1))
 1092 
 1093 /* Push a pointer value onto the failure stack.
 1094    Assumes the variable `fail_stack'.  Probably should only
 1095    be called from within `PUSH_FAILURE_POINT'.  */
 1096 #define PUSH_FAILURE_POINTER(item)                  \
 1097   fail_stack.stack[fail_stack.avail++].pointer = (unsigned char *) (item)
 1098 
 1099 /* This pushes an integer-valued item onto the failure stack.
 1100    Assumes the variable `fail_stack'.  Probably should only
 1101    be called from within `PUSH_FAILURE_POINT'.  */
 1102 #define PUSH_FAILURE_INT(item)                  \
 1103   fail_stack.stack[fail_stack.avail++].integer = (item)
 1104 
 1105 /* Push a fail_stack_elt_t value onto the failure stack.
 1106    Assumes the variable `fail_stack'.  Probably should only
 1107    be called from within `PUSH_FAILURE_POINT'.  */
 1108 #define PUSH_FAILURE_ELT(item)                  \
 1109   fail_stack.stack[fail_stack.avail++] =  (item)
 1110 
 1111 /* These three POP... operations complement the three PUSH... operations.
 1112    All assume that `fail_stack' is nonempty.  */
 1113 #define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
 1114 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
 1115 #define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
 1116 
 1117 /* Used to omit pushing failure point id's when we're not debugging.  */
 1118 #ifdef DEBUG
 1119 #define DEBUG_PUSH PUSH_FAILURE_INT
 1120 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
 1121 #else
 1122 #define DEBUG_PUSH(item)
 1123 #define DEBUG_POP(item_addr)
 1124 #endif
 1125 
 1126 
 1127 /* Push the information about the state we will need
 1128    if we ever fail back to it.
 1129 
 1130    Requires variables fail_stack, regstart, regend, reg_info, and
 1131    num_regs be declared.  DOUBLE_FAIL_STACK requires `destination' be
 1132    declared.
 1133 
 1134    Does `return FAILURE_CODE' if runs out of memory.  */
 1135 
 1136 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)   \
 1137   do {                                  \
 1138     char *destination;                          \
 1139     /* Must be int, so when we don't save any registers, the arithmetic \
 1140        of 0 + -1 isn't done as unsigned.  */                \
 1141     int this_reg;                           \
 1142                                         \
 1143     DEBUG_STATEMENT (failure_id++);                 \
 1144     DEBUG_STATEMENT (nfailure_points_pushed++);             \
 1145     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);       \
 1146     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
 1147     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
 1148                                     \
 1149     DEBUG_PRINT2 ("  slots needed: %d\n", NUM_FAILURE_ITEMS);       \
 1150     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);   \
 1151                                     \
 1152     /* Ensure we have enough space allocated for what we will push.  */ \
 1153     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)           \
 1154       {                                 \
 1155         if (!DOUBLE_FAIL_STACK (fail_stack))                \
 1156           return failure_code;                      \
 1157                                     \
 1158         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",      \
 1159                (fail_stack).size);              \
 1160         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
 1161       }                                 \
 1162                                     \
 1163     /* Push the info, starting with the registers.  */          \
 1164     DEBUG_PRINT1 ("\n");                        \
 1165                                     \
 1166     if (1)                              \
 1167       for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
 1168        this_reg++)                          \
 1169     {                               \
 1170       DEBUG_PRINT2 ("  Pushing reg: %d\n", this_reg);       \
 1171       DEBUG_STATEMENT (num_regs_pushed++);              \
 1172                                     \
 1173       DEBUG_PRINT2 ("    start: 0x%x\n", regstart[this_reg]);   \
 1174       PUSH_FAILURE_POINTER (regstart[this_reg]);            \
 1175                                     \
 1176       DEBUG_PRINT2 ("    end: 0x%x\n", regend[this_reg]);       \
 1177       PUSH_FAILURE_POINTER (regend[this_reg]);          \
 1178                                     \
 1179       DEBUG_PRINT2 ("    info: 0x%x\n      ", reg_info[this_reg]);  \
 1180       DEBUG_PRINT2 (" match_null=%d",               \
 1181             REG_MATCH_NULL_STRING_P (reg_info[this_reg]));  \
 1182       DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));  \
 1183       DEBUG_PRINT2 (" matched_something=%d",            \
 1184             MATCHED_SOMETHING (reg_info[this_reg]));    \
 1185       DEBUG_PRINT2 (" ever_matched=%d",             \
 1186             EVER_MATCHED_SOMETHING (reg_info[this_reg]));   \
 1187       DEBUG_PRINT1 ("\n");                      \
 1188       PUSH_FAILURE_ELT (reg_info[this_reg].word);           \
 1189     }                               \
 1190                                     \
 1191     DEBUG_PRINT2 ("  Pushing  low active reg: %d\n", lowest_active_reg);\
 1192     PUSH_FAILURE_INT (lowest_active_reg);               \
 1193                                     \
 1194     DEBUG_PRINT2 ("  Pushing high active reg: %d\n", highest_active_reg);\
 1195     PUSH_FAILURE_INT (highest_active_reg);              \
 1196                                     \
 1197     DEBUG_PRINT2 ("  Pushing pattern 0x%x: ", pattern_place);       \
 1198     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);       \
 1199     PUSH_FAILURE_POINTER (pattern_place);               \
 1200                                     \
 1201     DEBUG_PRINT2 ("  Pushing string 0x%x: `", string_place);        \
 1202     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
 1203                  size2);                \
 1204     DEBUG_PRINT1 ("'\n");                       \
 1205     PUSH_FAILURE_POINTER (string_place);                \
 1206                                     \
 1207     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);        \
 1208     DEBUG_PUSH (failure_id);                        \
 1209   } while (0)
 1210 
 1211 /* This is the number of items that are pushed and popped on the stack
 1212    for each register.  */
 1213 #define NUM_REG_ITEMS  3
 1214 
 1215 /* Individual items aside from the registers.  */
 1216 #ifdef DEBUG
 1217 #define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
 1218 #else
 1219 #define NUM_NONREG_ITEMS 4
 1220 #endif
 1221 
 1222 /* We push at most this many items on the stack.  */
 1223 #define MAX_FAILURE_ITEMS ((num_regs - 1) * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
 1224 
 1225 /* We actually push this many items.  */
 1226 #define NUM_FAILURE_ITEMS               \
 1227   (((0                          \
 1228      ? 0 : highest_active_reg - lowest_active_reg + 1)  \
 1229     * NUM_REG_ITEMS)                    \
 1230    + NUM_NONREG_ITEMS)
 1231 
 1232 /* How many items can still be added to the stack without overflowing it.  */
 1233 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
 1234 
 1235 
 1236 /* Pops what PUSH_FAIL_STACK pushes.
 1237 
 1238    We restore into the parameters, all of which should be lvalues:
 1239      STR -- the saved data position.
 1240      PAT -- the saved pattern position.
 1241      LOW_REG, HIGH_REG -- the highest and lowest active registers.
 1242      REGSTART, REGEND -- arrays of string positions.
 1243      REG_INFO -- array of information about each subexpression.
 1244 
 1245    Also assumes the variables `fail_stack' and (if debugging), `bufp',
 1246    `pend', `string1', `size1', `string2', and `size2'.  */
 1247 
 1248 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
 1249 {                                   \
 1250   DEBUG_STATEMENT (fail_stack_elt_t failure_id;)            \
 1251   int this_reg;                             \
 1252   const unsigned char *string_temp;                 \
 1253                                     \
 1254   assert (!FAIL_STACK_EMPTY ());                    \
 1255                                     \
 1256   /* Remove failure points and point to how many regs pushed.  */   \
 1257   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                \
 1258   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
 1259   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size); \
 1260                                     \
 1261   assert (fail_stack.avail >= NUM_NONREG_ITEMS);            \
 1262                                     \
 1263   DEBUG_POP (&failure_id);                      \
 1264   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);      \
 1265                                     \
 1266   /* If the saved string location is NULL, it came from an      \
 1267      on_failure_keep_string_jump opcode, and we want to throw away the  \
 1268      saved NULL, thus retaining our current position in the string.  */ \
 1269   string_temp = POP_FAILURE_POINTER ();                 \
 1270   if (string_temp != NULL)                      \
 1271     str = (const char *) string_temp;                   \
 1272                                     \
 1273   DEBUG_PRINT2 ("  Popping string 0x%x: `", str);           \
 1274   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);  \
 1275   DEBUG_PRINT1 ("'\n");                         \
 1276                                     \
 1277   pat = (unsigned char *) POP_FAILURE_POINTER ();           \
 1278   DEBUG_PRINT2 ("  Popping pattern 0x%x: ", pat);           \
 1279   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);           \
 1280                                     \
 1281   /* Restore register info.  */                     \
 1282   high_reg = (unsigned) POP_FAILURE_INT ();             \
 1283   DEBUG_PRINT2 ("  Popping high active reg: %d\n", high_reg);       \
 1284                                     \
 1285   low_reg = (unsigned) POP_FAILURE_INT ();              \
 1286   DEBUG_PRINT2 ("  Popping  low active reg: %d\n", low_reg);        \
 1287                                     \
 1288   if (1)                                \
 1289     for (this_reg = high_reg; this_reg >= low_reg; this_reg--)      \
 1290       {                                 \
 1291     DEBUG_PRINT2 ("    Popping reg: %d\n", this_reg);       \
 1292                                     \
 1293     reg_info[this_reg].word = POP_FAILURE_ELT ();           \
 1294     DEBUG_PRINT2 ("      info: 0x%x\n", reg_info[this_reg]);    \
 1295                                     \
 1296     regend[this_reg] = (const char *) POP_FAILURE_POINTER ();   \
 1297     DEBUG_PRINT2 ("      end: 0x%x\n", regend[this_reg]);       \
 1298                                     \
 1299     regstart[this_reg] = (const char *) POP_FAILURE_POINTER (); \
 1300     DEBUG_PRINT2 ("      start: 0x%x\n", regstart[this_reg]);   \
 1301       }                                 \
 1302   else                                  \
 1303     {                                   \
 1304       for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
 1305     {                               \
 1306       reg_info[this_reg].word.integer = 0;              \
 1307       regend[this_reg] = 0;                     \
 1308       regstart[this_reg] = 0;                   \
 1309     }                               \
 1310       highest_active_reg = high_reg;                    \
 1311     }                                   \
 1312                                     \
 1313   set_regs_matched_done = 0;                        \
 1314   DEBUG_STATEMENT (nfailure_points_popped++);               \
 1315 } /* POP_FAILURE_POINT */
 1316 
 1317 
 1318 
 1319 /* Structure for per-register (a.k.a. per-group) information.
 1320    Other register information, such as the
 1321    starting and ending positions (which are addresses), and the list of
 1322    inner groups (which is a bits list) are maintained in separate
 1323    variables.
 1324 
 1325    We are making a (strictly speaking) nonportable assumption here: that
 1326    the compiler will pack our bit fields into something that fits into
 1327    the type of `word', i.e., is something that fits into one item on the
 1328    failure stack.  */
 1329 
 1330 typedef union
 1331 {
 1332   fail_stack_elt_t word;
 1333   struct
 1334   {
 1335       /* This field is one if this group can match the empty string,
 1336          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
 1337 #define MATCH_NULL_UNSET_VALUE 3
 1338     unsigned match_null_string_p : 2;
 1339     unsigned is_active : 1;
 1340     unsigned matched_something : 1;
 1341     unsigned ever_matched_something : 1;
 1342   } bits;
 1343 } register_info_type;
 1344 
 1345 #define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
 1346 #define IS_ACTIVE(R)  ((R).bits.is_active)
 1347 #define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
 1348 #define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
 1349 
 1350 
 1351 /* Call this when have matched a real character; it sets `matched' flags
 1352    for the subexpressions which we are currently inside.  Also records
 1353    that those subexprs have matched.  */
 1354 #define SET_REGS_MATCHED()                      \
 1355   do                                    \
 1356     {                                   \
 1357       if (!set_regs_matched_done)                   \
 1358     {                               \
 1359       unsigned r;                           \
 1360       set_regs_matched_done = 1;                    \
 1361       for (r = lowest_active_reg; r <= highest_active_reg; r++) \
 1362         {                               \
 1363           MATCHED_SOMETHING (reg_info[r])               \
 1364         = EVER_MATCHED_SOMETHING (reg_info[r])          \
 1365         = 1;                            \
 1366         }                               \
 1367     }                               \
 1368     }                                   \
 1369   while (0)
 1370 
 1371 /* Registers are set to a sentinel when they haven't yet matched.  */
 1372 static char reg_unset_dummy;
 1373 #define REG_UNSET_VALUE (&reg_unset_dummy)
 1374 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
 1375 
 1376 /* Subroutine declarations and macros for regex_compile.  */
 1377 
 1378 static void store_op1 (), store_op2 ();
 1379 static void insert_op1 (), insert_op2 ();
 1380 static boolean at_begline_loc_p (), at_endline_loc_p ();
 1381 static boolean group_in_compile_stack ();
 1382 static reg_errcode_t compile_range ();
 1383 
 1384 /* Fetch the next character in the uncompiled pattern---translating it
 1385    if necessary.  Also cast from a signed character in the constant
 1386    string passed to us by the user to an unsigned char that we can use
 1387    as an array index (in, e.g., `translate').  */
 1388 #ifndef PATFETCH
 1389 #define PATFETCH(c)                         \
 1390   do {if (p == pend) return REG_EEND;                   \
 1391     c = (unsigned char) *p++;                       \
 1392     if (translate) c = (unsigned char) translate[c];            \
 1393   } while (0)
 1394 #endif
 1395 
 1396 /* Fetch the next character in the uncompiled pattern, with no
 1397    translation.  */
 1398 #define PATFETCH_RAW(c)                         \
 1399   do {if (p == pend) return REG_EEND;                   \
 1400     c = (unsigned char) *p++;                       \
 1401   } while (0)
 1402 
 1403 /* Go backwards one character in the pattern.  */
 1404 #define PATUNFETCH p--
 1405 
 1406 
 1407 /* If `translate' is non-null, return translate[D], else just D.  We
 1408    cast the subscript to translate because some data is declared as
 1409    `char *', to avoid warnings when a string constant is passed.  But
 1410    when we use a character as a subscript we must make it unsigned.  */
 1411 #ifndef TRANSLATE
 1412 #define TRANSLATE(d) \
 1413   (translate ? (char) translate[(unsigned char) (d)] : (d))
 1414 #endif
 1415 
 1416 
 1417 /* Macros for outputting the compiled pattern into `buffer'.  */
 1418 
 1419 /* If the buffer isn't allocated when it comes in, use this.  */
 1420 #define INIT_BUF_SIZE  32
 1421 
 1422 /* Make sure we have at least N more bytes of space in buffer.  */
 1423 #define GET_BUFFER_SPACE(n)                     \
 1424     while (b - bufp->buffer + (n) > bufp->allocated)            \
 1425       EXTEND_BUFFER ()
 1426 
 1427 /* Make sure we have one more byte of buffer space and then add C to it.  */
 1428 #define BUF_PUSH(c)                         \
 1429   do {                                  \
 1430     GET_BUFFER_SPACE (1);                       \
 1431     *b++ = (unsigned char) (c);                     \
 1432   } while (0)
 1433 
 1434 
 1435 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
 1436 #define BUF_PUSH_2(c1, c2)                      \
 1437   do {                                  \
 1438     GET_BUFFER_SPACE (2);                       \
 1439     *b++ = (unsigned char) (c1);                    \
 1440     *b++ = (unsigned char) (c2);                    \
 1441   } while (0)
 1442 
 1443 
 1444 /* As with BUF_PUSH_2, except for three bytes.  */
 1445 #define BUF_PUSH_3(c1, c2, c3)                      \
 1446   do {                                  \
 1447     GET_BUFFER_SPACE (3);                       \
 1448     *b++ = (unsigned char) (c1);                    \
 1449     *b++ = (unsigned char) (c2);                    \
 1450     *b++ = (unsigned char) (c3);                    \
 1451   } while (0)
 1452 
 1453 
 1454 /* Store a jump with opcode OP at LOC to location TO.  We store a
 1455    relative address offset by the three bytes the jump itself occupies.  */
 1456 #define STORE_JUMP(op, loc, to) \
 1457   store_op1 (op, loc, (to) - (loc) - 3)
 1458 
 1459 /* Likewise, for a two-argument jump.  */
 1460 #define STORE_JUMP2(op, loc, to, arg) \
 1461   store_op2 (op, loc, (to) - (loc) - 3, arg)
 1462 
 1463 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
 1464 #define INSERT_JUMP(op, loc, to) \
 1465   insert_op1 (op, loc, (to) - (loc) - 3, b)
 1466 
 1467 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
 1468 #define INSERT_JUMP2(op, loc, to, arg) \
 1469   insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
 1470 
 1471 
 1472 /* This is not an arbitrary limit: the arguments which represent offsets
 1473    into the pattern are two bytes long.  So if 2^16 bytes turns out to
 1474    be too small, many things would have to change.  */
 1475 #define MAX_BUF_SIZE (1L << 16)
 1476 
 1477 
 1478 /* Extend the buffer by twice its current size via realloc and
 1479    reset the pointers that pointed into the old block to point to the
 1480    correct places in the new one.  If extending the buffer results in it
 1481    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
 1482 #define EXTEND_BUFFER()                         \
 1483   do {                                  \
 1484     unsigned char *old_buffer = bufp->buffer;               \
 1485     if (bufp->allocated == MAX_BUF_SIZE)                \
 1486       return REG_ESIZE;                         \
 1487     bufp->allocated <<= 1;                      \
 1488     if (bufp->allocated > MAX_BUF_SIZE)                 \
 1489       bufp->allocated = MAX_BUF_SIZE;                   \
 1490     bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\
 1491     if (bufp->buffer == NULL)                       \
 1492       return REG_ESPACE;                        \
 1493     /* If the buffer moved, move all the pointers into it.  */      \
 1494     if (old_buffer != bufp->buffer)                 \
 1495       {                                 \
 1496         b = (b - old_buffer) + bufp->buffer;                \
 1497         begalt = (begalt - old_buffer) + bufp->buffer;          \
 1498         if (fixup_alt_jump)                     \
 1499           fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
 1500         if (laststart)                          \
 1501           laststart = (laststart - old_buffer) + bufp->buffer;      \
 1502         if (pending_exact)                      \
 1503           pending_exact = (pending_exact - old_buffer) + bufp->buffer;  \
 1504       }                                 \
 1505   } while (0)
 1506 
 1507 
 1508 /* Since we have one byte reserved for the register number argument to
 1509    {start,stop}_memory, the maximum number of groups we can report
 1510    things about is what fits in that byte.  */
 1511 #define MAX_REGNUM 255
 1512 
 1513 /* But patterns can have more than `MAX_REGNUM' registers.  We just
 1514    ignore the excess.  */
 1515 typedef unsigned regnum_t;
 1516 
 1517 
 1518 /* Macros for the compile stack.  */
 1519 
 1520 /* Since offsets can go either forwards or backwards, this type needs to
 1521    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
 1522 typedef int pattern_offset_t;
 1523 
 1524 typedef struct
 1525 {
 1526   pattern_offset_t begalt_offset;
 1527   pattern_offset_t fixup_alt_jump;
 1528   pattern_offset_t inner_group_offset;
 1529   pattern_offset_t laststart_offset;
 1530   regnum_t regnum;
 1531 } compile_stack_elt_t;
 1532 
 1533 
 1534 typedef struct
 1535 {
 1536   compile_stack_elt_t *stack;
 1537   unsigned size;
 1538   unsigned avail;           /* Offset of next open position.  */
 1539 } compile_stack_type;
 1540 
 1541 
 1542 #define INIT_COMPILE_STACK_SIZE 32
 1543 
 1544 #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
 1545 #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
 1546 
 1547 /* The next available element.  */
 1548 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
 1549 
 1550 
 1551 /* Set the bit for character C in a list.  */
 1552 #define SET_LIST_BIT(c)                               \
 1553   (b[((unsigned char) (c)) / BYTEWIDTH]               \
 1554    |= 1 << (((unsigned char) c) % BYTEWIDTH))
 1555 
 1556 
 1557 /* Get the next unsigned number in the uncompiled pattern.  */
 1558 #define GET_UNSIGNED_NUMBER(num)                    \
 1559   { if (p != pend)                          \
 1560      {                                  \
 1561        PATFETCH (c);                            \
 1562        while (ISDIGIT (c))                      \
 1563          {                              \
 1564            if (num < 0)                         \
 1565               num = 0;                          \
 1566            num = num * 10 + c - '0';                    \
 1567            if (p == pend)                       \
 1568               break;                            \
 1569            PATFETCH (c);                        \
 1570          }                              \
 1571        }                                \
 1572     }
 1573 
 1574 #define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
 1575 
 1576 #define IS_CHAR_CLASS(string)                       \
 1577    (STREQ (string, "alpha") || STREQ (string, "upper")          \
 1578     || STREQ (string, "lower") || STREQ (string, "digit")       \
 1579     || STREQ (string, "alnum") || STREQ (string, "xdigit")      \
 1580     || STREQ (string, "space") || STREQ (string, "print")       \
 1581     || STREQ (string, "punct") || STREQ (string, "graph")       \
 1582     || STREQ (string, "cntrl") || STREQ (string, "blank"))
 1583 
 1584 #ifndef MATCH_MAY_ALLOCATE
 1585 
 1586 /* If we cannot allocate large objects within re_match_2_internal,
 1587    we make the fail stack and register vectors global.
 1588    The fail stack, we grow to the maximum size when a regexp
 1589    is compiled.
 1590    The register vectors, we adjust in size each time we
 1591    compile a regexp, according to the number of registers it needs.  */
 1592 
 1593 static fail_stack_type fail_stack;
 1594 
 1595 /* Size with which the following vectors are currently allocated.
 1596    That is so we can make them bigger as needed,
 1597    but never make them smaller.  */
 1598 static int regs_allocated_size;
 1599 
 1600 static const char **     regstart, **     regend;
 1601 static const char ** old_regstart, ** old_regend;
 1602 static const char **best_regstart, **best_regend;
 1603 static register_info_type *reg_info;
 1604 static const char **reg_dummy;
 1605 static register_info_type *reg_info_dummy;
 1606 
 1607 /* Make the register vectors big enough for NUM_REGS registers,
 1608    but don't make them smaller.  */
 1609 
 1610 static
 1611 regex_grow_registers (num_regs)
 1612      int num_regs;
 1613 {
 1614   if (num_regs > regs_allocated_size)
 1615     {
 1616       RETALLOC_IF (regstart,     num_regs, const char *);
 1617       RETALLOC_IF (regend,   num_regs, const char *);
 1618       RETALLOC_IF (old_regstart, num_regs, const char *);
 1619       RETALLOC_IF (old_regend,   num_regs, const char *);
 1620       RETALLOC_IF (best_regstart, num_regs, const char *);
 1621       RETALLOC_IF (best_regend,  num_regs, const char *);
 1622       RETALLOC_IF (reg_info,     num_regs, register_info_type);
 1623       RETALLOC_IF (reg_dummy,    num_regs, const char *);
 1624       RETALLOC_IF (reg_info_dummy, num_regs, register_info_type);
 1625 
 1626       regs_allocated_size = num_regs;
 1627     }
 1628 }
 1629 
 1630 #endif /* not MATCH_MAY_ALLOCATE */
 1631 
 1632 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
 1633    Returns one of error codes defined in `regex.h', or zero for success.
 1634 
 1635    Assumes the `allocated' (and perhaps `buffer') and `translate'
 1636    fields are set in BUFP on entry.
 1637 
 1638    If it succeeds, results are put in BUFP (if it returns an error, the
 1639    contents of BUFP are undefined):
 1640      `buffer' is the compiled pattern;
 1641      `syntax' is set to SYNTAX;
 1642      `used' is set to the length of the compiled pattern;
 1643      `fastmap_accurate' is zero;
 1644      `re_nsub' is the number of subexpressions in PATTERN;
 1645      `not_bol' and `not_eol' are zero;
 1646 
 1647    The `fastmap' and `newline_anchor' fields are neither
 1648    examined nor set.  */
 1649 
 1650 /* Return, freeing storage we allocated.  */
 1651 #define FREE_STACK_RETURN(value)        \
 1652   return (free (compile_stack.stack), value)
 1653 
 1654 static reg_errcode_t
 1655 regex_compile (pattern, size, syntax, bufp)
 1656      const char *pattern;
 1657      int size;
 1658      reg_syntax_t syntax;
 1659      struct re_pattern_buffer *bufp;
 1660 {
 1661   /* We fetch characters from PATTERN here.  Even though PATTERN is
 1662      `char *' (i.e., signed), we declare these variables as unsigned, so
 1663      they can be reliably used as array indices.  */
 1664   register unsigned char c, c1;
 1665 
 1666   /* A random temporary spot in PATTERN.  */
 1667   const char *p1;
 1668 
 1669   /* Points to the end of the buffer, where we should append.  */
 1670   register unsigned char *b;
 1671 
 1672   /* Keeps track of unclosed groups.  */
 1673   compile_stack_type compile_stack;
 1674 
 1675   /* Points to the current (ending) position in the pattern.  */
 1676   const char *p = pattern;
 1677   const char *pend = pattern + size;
 1678 
 1679   /* How to translate the characters in the pattern.  */
 1680   RE_TRANSLATE_TYPE translate = bufp->translate;
 1681 
 1682   /* Address of the count-byte of the most recently inserted `exactn'
 1683      command.  This makes it possible to tell if a new exact-match
 1684      character can be added to that command or if the character requires
 1685      a new `exactn' command.  */
 1686   unsigned char *pending_exact = 0;
 1687 
 1688   /* Address of start of the most recently finished expression.
 1689      This tells, e.g., postfix * where to find the start of its
 1690      operand.  Reset at the beginning of groups and alternatives.  */
 1691   unsigned char *laststart = 0;
 1692 
 1693   /* Address of beginning of regexp, or inside of last group.  */
 1694   unsigned char *begalt;
 1695 
 1696   /* Place in the uncompiled pattern (i.e., the {) to
 1697      which to go back if the interval is invalid.  */
 1698   const char *beg_interval;
 1699 
 1700   /* Address of the place where a forward jump should go to the end of
 1701      the containing expression.  Each alternative of an `or' -- except the
 1702      last -- ends with a forward jump of this sort.  */
 1703   unsigned char *fixup_alt_jump = 0;
 1704 
 1705   /* Counts open-groups as they are encountered.  Remembered for the
 1706      matching close-group on the compile stack, so the same register
 1707      number is put in the stop_memory as the start_memory.  */
 1708   regnum_t regnum = 0;
 1709 
 1710 #ifdef DEBUG
 1711   DEBUG_PRINT1 ("\nCompiling pattern: ");
 1712   if (debug)
 1713     {
 1714       unsigned debug_count;
 1715 
 1716       for (debug_count = 0; debug_count < size; debug_count++)
 1717         putchar (pattern[debug_count]);
 1718       putchar ('\n');
 1719     }
 1720 #endif /* DEBUG */
 1721 
 1722   /* Initialize the compile stack.  */
 1723   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
 1724   if (compile_stack.stack == NULL)
 1725     return REG_ESPACE;
 1726 
 1727   compile_stack.size = INIT_COMPILE_STACK_SIZE;
 1728   compile_stack.avail = 0;
 1729 
 1730   /* Initialize the pattern buffer.  */
 1731   bufp->syntax = syntax;
 1732   bufp->fastmap_accurate = 0;
 1733   bufp->not_bol = bufp->not_eol = 0;
 1734 
 1735   /* Set `used' to zero, so that if we return an error, the pattern
 1736      printer (for debugging) will think there's no pattern.  We reset it
 1737      at the end.  */
 1738   bufp->used = 0;
 1739 
 1740   /* Always count groups, whether or not bufp->no_sub is set.  */
 1741   bufp->re_nsub = 0;
 1742 
 1743 #if !defined (emacs) && !defined (SYNTAX_TABLE)
 1744   /* Initialize the syntax table.  */
 1745    init_syntax_once ();
 1746 #endif
 1747 
 1748   if (bufp->allocated == 0)
 1749     {
 1750       if (bufp->buffer)
 1751     { /* If zero allocated, but buffer is non-null, try to realloc
 1752              enough space.  This loses if buffer's address is bogus, but
 1753              that is the user's responsibility.  */
 1754           RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
 1755         }
 1756       else
 1757         { /* Caller did not allocate a buffer.  Do it for them.  */
 1758           bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
 1759         }
 1760       if (!bufp->buffer) FREE_STACK_RETURN (REG_ESPACE);
 1761 
 1762       bufp->allocated = INIT_BUF_SIZE;
 1763     }
 1764 
 1765   begalt = b = bufp->buffer;
 1766 
 1767   /* Loop through the uncompiled pattern until we're at the end.  */
 1768   while (p != pend)
 1769     {
 1770       PATFETCH (c);
 1771 
 1772       switch (c)
 1773         {
 1774         case '^':
 1775           {
 1776             if (   /* If at start of pattern, it's an operator.  */
 1777                    p == pattern + 1
 1778                    /* If context independent, it's an operator.  */
 1779                 || syntax & RE_CONTEXT_INDEP_ANCHORS
 1780                    /* Otherwise, depends on what's come before.  */
 1781                 || at_begline_loc_p (pattern, p, syntax))
 1782               BUF_PUSH (begline);
 1783             else
 1784               goto normal_char;
 1785           }
 1786           break;
 1787 
 1788 
 1789         case '$':
 1790           {
 1791             if (   /* If at end of pattern, it's an operator.  */
 1792                    p == pend
 1793                    /* If context independent, it's an operator.  */
 1794                 || syntax & RE_CONTEXT_INDEP_ANCHORS
 1795                    /* Otherwise, depends on what's next.  */
 1796                 || at_endline_loc_p (p, pend, syntax))
 1797                BUF_PUSH (endline);
 1798              else
 1799                goto normal_char;
 1800            }
 1801            break;
 1802 
 1803 
 1804     case '+':
 1805         case '?':
 1806           if ((syntax & RE_BK_PLUS_QM)
 1807               || (syntax & RE_LIMITED_OPS))
 1808             goto normal_char;
 1809         handle_plus:
 1810         case '*':
 1811           /* If there is no previous pattern... */
 1812           if (!laststart)
 1813             {
 1814               if (syntax & RE_CONTEXT_INVALID_OPS)
 1815                 FREE_STACK_RETURN (REG_BADRPT);
 1816               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
 1817                 goto normal_char;
 1818             }
 1819 
 1820           {
 1821             /* Are we optimizing this jump?  */
 1822             boolean keep_string_p = false;
 1823 
 1824             /* 1 means zero (many) matches is allowed.  */
 1825             char zero_times_ok = 0, many_times_ok = 0;
 1826 
 1827             /* If there is a sequence of repetition chars, collapse it
 1828                down to just one (the right one).  We can't combine
 1829                interval operators with these because of, e.g., `a{2}*',
 1830                which should only match an even number of `a's.  */
 1831 
 1832             for (;;)
 1833               {
 1834                 zero_times_ok |= c != '+';
 1835                 many_times_ok |= c != '?';
 1836 
 1837                 if (p == pend)
 1838                   break;
 1839 
 1840                 PATFETCH (c);
 1841 
 1842                 if (c == '*'
 1843                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
 1844                   ;
 1845 
 1846                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
 1847                   {
 1848                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
 1849 
 1850                     PATFETCH (c1);
 1851                     if (!(c1 == '+' || c1 == '?'))
 1852                       {
 1853                         PATUNFETCH;
 1854                         PATUNFETCH;
 1855                         break;
 1856                       }
 1857 
 1858                     c = c1;
 1859                   }
 1860                 else
 1861                   {
 1862                     PATUNFETCH;
 1863                     break;
 1864                   }
 1865 
 1866                 /* If we get here, we found another repeat character.  */
 1867                }
 1868 
 1869             /* Star, etc. applied to an empty pattern is equivalent
 1870                to an empty pattern.  */
 1871             if (!laststart)
 1872               break;
 1873 
 1874             /* Now we know whether or not zero matches is allowed
 1875                and also whether or not two or more matches is allowed.  */
 1876             if (many_times_ok)
 1877               { /* More than one repetition is allowed, so put in at the
 1878                    end a backward relative jump from `b' to before the next
 1879                    jump we're going to put in below (which jumps from
 1880                    laststart to after this jump).
 1881 
 1882                    But if we are at the `*' in the exact sequence `.*\n',
 1883                    insert an unconditional jump backwards to the .,
 1884                    instead of the beginning of the loop.  This way we only
 1885                    push a failure point once, instead of every time
 1886                    through the loop.  */
 1887                 assert (p - 1 > pattern);
 1888 
 1889                 /* Allocate the space for the jump.  */
 1890                 GET_BUFFER_SPACE (3);
 1891 
 1892                 /* We know we are not at the first character of the pattern,
 1893                    because laststart was nonzero.  And we've already
 1894                    incremented `p', by the way, to be the character after
 1895                    the `*'.  Do we have to do something analogous here
 1896                    for null bytes, because of RE_DOT_NOT_NULL?  */
 1897                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
 1898             && zero_times_ok
 1899                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
 1900                     && !(syntax & RE_DOT_NEWLINE))
 1901                   { /* We have .*\n.  */
 1902                     STORE_JUMP (jump, b, laststart);
 1903                     keep_string_p = true;
 1904                   }
 1905                 else
 1906                   /* Anything else.  */
 1907                   STORE_JUMP (maybe_pop_jump, b, laststart - 3);
 1908 
 1909                 /* We've added more stuff to the buffer.  */
 1910                 b += 3;
 1911               }
 1912 
 1913             /* On failure, jump from laststart to b + 3, which will be the
 1914                end of the buffer after this jump is inserted.  */
 1915             GET_BUFFER_SPACE (3);
 1916             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
 1917                                        : on_failure_jump,
 1918                          laststart, b + 3);
 1919             pending_exact = 0;
 1920             b += 3;
 1921 
 1922             if (!zero_times_ok)
 1923               {
 1924                 /* At least one repetition is required, so insert a
 1925                    `dummy_failure_jump' before the initial
 1926                    `on_failure_jump' instruction of the loop. This
 1927                    effects a skip over that instruction the first time
 1928                    we hit that loop.  */
 1929                 GET_BUFFER_SPACE (3);
 1930                 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
 1931                 b += 3;
 1932               }
 1933             }
 1934       break;
 1935 
 1936 
 1937     case '.':
 1938           laststart = b;
 1939           BUF_PUSH (anychar);
 1940           break;
 1941 
 1942 
 1943         case '[':
 1944           {
 1945             boolean had_char_class = false;
 1946 
 1947             if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
 1948 
 1949             /* Ensure that we have enough space to push a charset: the
 1950                opcode, the length count, and the bitset; 34 bytes in all.  */
 1951         GET_BUFFER_SPACE (34);
 1952 
 1953             laststart = b;
 1954 
 1955             /* We test `*p == '^' twice, instead of using an if
 1956                statement, so we only need one BUF_PUSH.  */
 1957             BUF_PUSH (*p == '^' ? charset_not : charset);
 1958             if (*p == '^')
 1959               p++;
 1960 
 1961             /* Remember the first position in the bracket expression.  */
 1962             p1 = p;
 1963 
 1964             /* Push the number of bytes in the bitmap.  */
 1965             BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
 1966 
 1967             /* Clear the whole map.  */
 1968             bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
 1969 
 1970             /* charset_not matches newline according to a syntax bit.  */
 1971             if ((re_opcode_t) b[-2] == charset_not
 1972                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
 1973               SET_LIST_BIT ('\n');
 1974 
 1975             /* Read in characters and ranges, setting map bits.  */
 1976             for (;;)
 1977               {
 1978                 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
 1979 
 1980                 PATFETCH (c);
 1981 
 1982                 /* \ might escape characters inside [...] and [^...].  */
 1983                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
 1984                   {
 1985                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
 1986 
 1987                     PATFETCH (c1);
 1988                     SET_LIST_BIT (c1);
 1989                     continue;
 1990                   }
 1991 
 1992                 /* Could be the end of the bracket expression.  If it's
 1993                    not (i.e., when the bracket expression is `[]' so
 1994                    far), the ']' character bit gets set way below.  */
 1995                 if (c == ']' && p != p1 + 1)
 1996                   break;
 1997 
 1998                 /* Look ahead to see if it's a range when the last thing
 1999                    was a character class.  */
 2000                 if (had_char_class && c == '-' && *p != ']')
 2001                   FREE_STACK_RETURN (REG_ERANGE);
 2002 
 2003                 /* Look ahead to see if it's a range when the last thing
 2004                    was a character: if this is a hyphen not at the
 2005                    beginning or the end of a list, then it's the range
 2006                    operator.  */
 2007                 if (c == '-'
 2008                     && !(p - 2 >= pattern && p[-2] == '[')
 2009                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
 2010                     && *p != ']')
 2011                   {
 2012                     reg_errcode_t ret
 2013                       = compile_range (&p, pend, translate, syntax, b);
 2014                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
 2015                   }
 2016 
 2017                 else if (p[0] == '-' && p[1] != ']')
 2018                   { /* This handles ranges made up of characters only.  */
 2019                     reg_errcode_t ret;
 2020 
 2021             /* Move past the `-'.  */
 2022                     PATFETCH (c1);
 2023 
 2024                     ret = compile_range (&p, pend, translate, syntax, b);
 2025                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
 2026                   }
 2027 
 2028                 /* See if we're at the beginning of a possible character
 2029                    class.  */
 2030 
 2031                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
 2032                   { /* Leave room for the null.  */
 2033                     char str[CHAR_CLASS_MAX_LENGTH + 1];
 2034 
 2035                     PATFETCH (c);
 2036                     c1 = 0;
 2037 
 2038                     /* If pattern is `[[:'.  */
 2039                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
 2040 
 2041                     for (;;)
 2042                       {
 2043                         PATFETCH (c);
 2044                         if (c == ':' || c == ']' || p == pend
 2045                             || c1 == CHAR_CLASS_MAX_LENGTH)
 2046                           break;
 2047                         str[c1++] = c;
 2048                       }
 2049                     str[c1] = '\0';
 2050 
 2051                     /* If isn't a word bracketed by `[:' and:`]':
 2052                        undo the ending character, the letters, and leave
 2053                        the leading `:' and `[' (but set bits for them).  */
 2054                     if (c == ':' && *p == ']')
 2055                       {
 2056                         int ch;
 2057                         boolean is_alnum = STREQ (str, "alnum");
 2058                         boolean is_alpha = STREQ (str, "alpha");
 2059                         boolean is_blank = STREQ (str, "blank");
 2060                         boolean is_cntrl = STREQ (str, "cntrl");
 2061                         boolean is_digit = STREQ (str, "digit");
 2062                         boolean is_graph = STREQ (str, "graph");
 2063                         boolean is_lower = STREQ (str, "lower");
 2064                         boolean is_print = STREQ (str, "print");
 2065                         boolean is_punct = STREQ (str, "punct");
 2066                         boolean is_space = STREQ (str, "space");
 2067                         boolean is_upper = STREQ (str, "upper");
 2068                         boolean is_xdigit = STREQ (str, "xdigit");
 2069 
 2070                         if (!IS_CHAR_CLASS (str))
 2071               FREE_STACK_RETURN (REG_ECTYPE);
 2072 
 2073                         /* Throw away the ] at the end of the character
 2074                            class.  */
 2075                         PATFETCH (c);
 2076 
 2077                         if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
 2078 
 2079                         for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
 2080                           {
 2081                 /* This was split into 3 if's to
 2082                    avoid an arbitrary limit in some compiler.  */
 2083                             if (   (is_alnum  && ISALNUM (ch))
 2084                                 || (is_alpha  && ISALPHA (ch))
 2085                                 || (is_blank  && ISBLANK (ch))
 2086                                 || (is_cntrl  && ISCNTRL (ch)))
 2087                   SET_LIST_BIT (ch);
 2088                 if (   (is_digit  && ISDIGIT (ch))
 2089                                 || (is_graph  && ISGRAPH (ch))
 2090                                 || (is_lower  && ISLOWER (ch))
 2091                                 || (is_print  && ISPRINT (ch)))
 2092                   SET_LIST_BIT (ch);
 2093                 if (   (is_punct  && ISPUNCT (ch))
 2094                                 || (is_space  && ISSPACE (ch))
 2095                                 || (is_upper  && ISUPPER (ch))
 2096                                 || (is_xdigit && ISXDIGIT (ch)))
 2097                   SET_LIST_BIT (ch);
 2098                           }
 2099                         had_char_class = true;
 2100                       }
 2101                     else
 2102                       {
 2103                         c1++;
 2104                         while (c1--)
 2105                           PATUNFETCH;
 2106                         SET_LIST_BIT ('[');
 2107                         SET_LIST_BIT (':');
 2108                         had_char_class = false;
 2109                       }
 2110                   }
 2111                 else
 2112                   {
 2113                     had_char_class = false;
 2114                     SET_LIST_BIT (c);
 2115                   }
 2116               }
 2117 
 2118             /* Discard any (non)matching list bytes that are all 0 at the
 2119                end of the map.  Decrease the map-length byte too.  */
 2120             while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
 2121               b[-1]--;
 2122             b += b[-1];
 2123           }
 2124           break;
 2125 
 2126 
 2127     case '(':
 2128           if (syntax & RE_NO_BK_PARENS)
 2129             goto handle_open;
 2130           else
 2131             goto normal_char;
 2132 
 2133 
 2134         case ')':
 2135           if (syntax & RE_NO_BK_PARENS)
 2136             goto handle_close;
 2137           else
 2138             goto normal_char;
 2139 
 2140 
 2141         case '\n':
 2142           if (syntax & RE_NEWLINE_ALT)
 2143             goto handle_alt;
 2144           else
 2145             goto normal_char;
 2146 
 2147 
 2148     case '|':
 2149           if (syntax & RE_NO_BK_VBAR)
 2150             goto handle_alt;
 2151           else
 2152             goto normal_char;
 2153 
 2154 
 2155         case '{':
 2156            if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
 2157              goto handle_interval;
 2158            else
 2159              goto normal_char;
 2160 
 2161 
 2162         case '\\':
 2163           if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
 2164 
 2165           /* Do not translate the character after the \, so that we can
 2166              distinguish, e.g., \B from \b, even if we normally would
 2167              translate, e.g., B to b.  */
 2168           PATFETCH_RAW (c);
 2169 
 2170           switch (c)
 2171             {
 2172             case '(':
 2173               if (syntax & RE_NO_BK_PARENS)
 2174                 goto normal_backslash;
 2175 
 2176             handle_open:
 2177               bufp->re_nsub++;
 2178               regnum++;
 2179 
 2180               if (COMPILE_STACK_FULL)
 2181                 {
 2182                   RETALLOC (compile_stack.stack, compile_stack.size << 1,
 2183                             compile_stack_elt_t);
 2184                   if (compile_stack.stack == NULL) return REG_ESPACE;
 2185 
 2186                   compile_stack.size <<= 1;
 2187                 }
 2188 
 2189               /* These are the values to restore when we hit end of this
 2190                  group.  They are all relative offsets, so that if the
 2191                  whole pattern moves because of realloc, they will still
 2192                  be valid.  */
 2193               COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
 2194               COMPILE_STACK_TOP.fixup_alt_jump
 2195                 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
 2196               COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
 2197               COMPILE_STACK_TOP.regnum = regnum;
 2198 
 2199               /* We will eventually replace the 0 with the number of
 2200                  groups inner to this one.  But do not push a
 2201                  start_memory for groups beyond the last one we can
 2202                  represent in the compiled pattern.  */
 2203               if (regnum <= MAX_REGNUM)
 2204                 {
 2205                   COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
 2206                   BUF_PUSH_3 (start_memory, regnum, 0);
 2207                 }
 2208 
 2209               compile_stack.avail++;
 2210 
 2211               fixup_alt_jump = 0;
 2212               laststart = 0;
 2213               begalt = b;
 2214           /* If we've reached MAX_REGNUM groups, then this open
 2215          won't actually generate any code, so we'll have to
 2216          clear pending_exact explicitly.  */
 2217           pending_exact = 0;
 2218               break;
 2219 
 2220 
 2221             case ')':
 2222               if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
 2223 
 2224               if (COMPILE_STACK_EMPTY) {
 2225                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
 2226                   goto normal_backslash;
 2227                 else
 2228                   FREE_STACK_RETURN (REG_ERPAREN);
 2229           }
 2230 
 2231             handle_close:
 2232               if (fixup_alt_jump)
 2233                 { /* Push a dummy failure point at the end of the
 2234                      alternative for a possible future
 2235                      `pop_failure_jump' to pop.  See comments at
 2236                      `push_dummy_failure' in `re_match_2'.  */
 2237                   BUF_PUSH (push_dummy_failure);
 2238 
 2239                   /* We allocated space for this jump when we assigned
 2240                      to `fixup_alt_jump', in the `handle_alt' case below.  */
 2241                   STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
 2242                 }
 2243 
 2244               /* See similar code for backslashed left paren above.  */
 2245               if (COMPILE_STACK_EMPTY) {
 2246                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
 2247                   goto normal_char;
 2248                 else
 2249                   FREE_STACK_RETURN (REG_ERPAREN);
 2250           }
 2251 
 2252               /* Since we just checked for an empty stack above, this
 2253                  ``can't happen''.  */
 2254               assert (compile_stack.avail != 0);
 2255               {
 2256                 /* We don't just want to restore into `regnum', because
 2257                    later groups should continue to be numbered higher,
 2258                    as in `(ab)c(de)' -- the second group is #2.  */
 2259                 regnum_t this_group_regnum;
 2260 
 2261                 compile_stack.avail--;
 2262                 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
 2263                 fixup_alt_jump
 2264                   = COMPILE_STACK_TOP.fixup_alt_jump
 2265                     ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
 2266                     : 0;
 2267                 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
 2268                 this_group_regnum = COMPILE_STACK_TOP.regnum;
 2269         /* If we've reached MAX_REGNUM groups, then this open
 2270            won't actually generate any code, so we'll have to
 2271            clear pending_exact explicitly.  */
 2272         pending_exact = 0;
 2273 
 2274                 /* We're at the end of the group, so now we know how many
 2275                    groups were inside this one.  */
 2276                 if (this_group_regnum <= MAX_REGNUM)
 2277                   {
 2278                     unsigned char *inner_group_loc
 2279                       = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
 2280 
 2281                     *inner_group_loc = regnum - this_group_regnum;
 2282                     BUF_PUSH_3 (stop_memory, this_group_regnum,
 2283                                 regnum - this_group_regnum);
 2284                   }
 2285               }
 2286               break;
 2287 
 2288 
 2289             case '|':                   /* `\|'.  */
 2290               if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
 2291                 goto normal_backslash;
 2292             handle_alt:
 2293               if (syntax & RE_LIMITED_OPS)
 2294                 goto normal_char;
 2295 
 2296               /* Insert before the previous alternative a jump which
 2297                  jumps to this alternative if the former fails.  */
 2298               GET_BUFFER_SPACE (3);
 2299               INSERT_JUMP (on_failure_jump, begalt, b + 6);
 2300               pending_exact = 0;
 2301               b += 3;
 2302 
 2303               /* The alternative before this one has a jump after it
 2304                  which gets executed if it gets matched.  Adjust that
 2305                  jump so it will jump to this alternative's analogous
 2306                  jump (put in below, which in turn will jump to the next
 2307                  (if any) alternative's such jump, etc.).  The last such
 2308                  jump jumps to the correct final destination.  A picture:
 2309                           _____ _____
 2310                           |   | |   |
 2311                           |   v |   v
 2312                          a | b   | c
 2313 
 2314                  If we are at `b', then fixup_alt_jump right now points to a
 2315                  three-byte space after `a'.  We'll put in the jump, set
 2316                  fixup_alt_jump to right after `b', and leave behind three
 2317                  bytes which we'll fill in when we get to after `c'.  */
 2318 
 2319               if (fixup_alt_jump)
 2320                 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
 2321 
 2322               /* Mark and leave space for a jump after this alternative,
 2323                  to be filled in later either by next alternative or
 2324                  when know we're at the end of a series of alternatives.  */
 2325               fixup_alt_jump = b;
 2326               GET_BUFFER_SPACE (3);
 2327               b += 3;
 2328 
 2329               laststart = 0;
 2330               begalt = b;
 2331               break;
 2332 
 2333 
 2334             case '{':
 2335               /* If \{ is a literal.  */
 2336               if (!(syntax & RE_INTERVALS)
 2337                      /* If we're at `\{' and it's not the open-interval
 2338                         operator.  */
 2339                   || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
 2340                   || (p - 2 == pattern  &&  p == pend))
 2341                 goto normal_backslash;
 2342 
 2343             handle_interval:
 2344               {
 2345                 /* If got here, then the syntax allows intervals.  */
 2346 
 2347                 /* At least (most) this many matches must be made.  */
 2348                 int lower_bound = -1, upper_bound = -1;
 2349 
 2350                 beg_interval = p - 1;
 2351 
 2352                 if (p == pend)
 2353                   {
 2354                     if (syntax & RE_NO_BK_BRACES)
 2355                       goto unfetch_interval;
 2356                     else
 2357                       FREE_STACK_RETURN (REG_EBRACE);
 2358                   }
 2359 
 2360                 GET_UNSIGNED_NUMBER (lower_bound);
 2361 
 2362                 if (c == ',')
 2363                   {
 2364                     GET_UNSIGNED_NUMBER (upper_bound);
 2365                     if (upper_bound < 0) upper_bound = RE_DUP_MAX;
 2366                   }
 2367                 else
 2368                   /* Interval such as `{1}' => match exactly once. */
 2369                   upper_bound = lower_bound;
 2370 
 2371                 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
 2372                     || lower_bound > upper_bound)
 2373                   {
 2374                     if (syntax & RE_NO_BK_BRACES)
 2375                       goto unfetch_interval;
 2376                     else
 2377                       FREE_STACK_RETURN (REG_BADBR);
 2378                   }
 2379 
 2380                 if (!(syntax & RE_NO_BK_BRACES))
 2381                   {
 2382                     if (c != '\\') FREE_STACK_RETURN (REG_EBRACE);
 2383 
 2384                     PATFETCH (c);
 2385                   }
 2386 
 2387                 if (c != '}')
 2388                   {
 2389                     if (syntax & RE_NO_BK_BRACES)
 2390                       goto unfetch_interval;
 2391                     else
 2392                       FREE_STACK_RETURN (REG_BADBR);
 2393                   }
 2394 
 2395                 /* We just parsed a valid interval.  */
 2396 
 2397                 /* If it's invalid to have no preceding re.  */
 2398                 if (!laststart)
 2399                   {
 2400                     if (syntax & RE_CONTEXT_INVALID_OPS)
 2401                       FREE_STACK_RETURN (REG_BADRPT);
 2402                     else if (syntax & RE_CONTEXT_INDEP_OPS)
 2403                       laststart = b;
 2404                     else
 2405                       goto unfetch_interval;
 2406                   }
 2407 
 2408                 /* If the upper bound is zero, don't want to succeed at
 2409                    all; jump from `laststart' to `b + 3', which will be
 2410                    the end of the buffer after we insert the jump.  */
 2411                  if (upper_bound == 0)
 2412                    {
 2413                      GET_BUFFER_SPACE (3);
 2414                      INSERT_JUMP (jump, laststart, b + 3);
 2415                      b += 3;
 2416                    }
 2417 
 2418                  /* Otherwise, we have a nontrivial interval.  When
 2419                     we're all done, the pattern will look like:
 2420                       set_number_at <jump count> <upper bound>
 2421                       set_number_at <succeed_n count> <lower bound>
 2422                       succeed_n <after jump addr> <succeed_n count>
 2423                       <body of loop>
 2424                       jump_n <succeed_n addr> <jump count>
 2425                     (The upper bound and `jump_n' are omitted if
 2426                     `upper_bound' is 1, though.)  */
 2427                  else
 2428                    { /* If the upper bound is > 1, we need to insert
 2429                         more at the end of the loop.  */
 2430                      unsigned nbytes = 10 + (upper_bound > 1) * 10;
 2431 
 2432                      GET_BUFFER_SPACE (nbytes);
 2433 
 2434                      /* Initialize lower bound of the `succeed_n', even
 2435                         though it will be set during matching by its
 2436                         attendant `set_number_at' (inserted next),
 2437                         because `re_compile_fastmap' needs to know.
 2438                         Jump to the `jump_n' we might insert below.  */
 2439                      INSERT_JUMP2 (succeed_n, laststart,
 2440                                    b + 5 + (upper_bound > 1) * 5,
 2441                                    lower_bound);
 2442                      b += 5;
 2443 
 2444                      /* Code to initialize the lower bound.  Insert
 2445                         before the `succeed_n'.  The `5' is the last two
 2446                         bytes of this `set_number_at', plus 3 bytes of
 2447                         the following `succeed_n'.  */
 2448                      insert_op2 (set_number_at, laststart, 5, lower_bound, b);
 2449                      b += 5;
 2450 
 2451                      if (upper_bound > 1)
 2452                        { /* More than one repetition is allowed, so
 2453                             append a backward jump to the `succeed_n'
 2454                             that starts this interval.
 2455 
 2456                             When we've reached this during matching,
 2457                             we'll have matched the interval once, so
 2458                             jump back only `upper_bound - 1' times.  */
 2459                          STORE_JUMP2 (jump_n, b, laststart + 5,
 2460                                       upper_bound - 1);
 2461                          b += 5;
 2462 
 2463                          /* The location we want to set is the second
 2464                             parameter of the `jump_n'; that is `b-2' as
 2465                             an absolute address.  `laststart' will be
 2466                             the `set_number_at' we're about to insert;
 2467                             `laststart+3' the number to set, the source
 2468                             for the relative address.  But we are
 2469                             inserting into the middle of the pattern --
 2470                             so everything is getting moved up by 5.
 2471                             Conclusion: (b - 2) - (laststart + 3) + 5,
 2472                             i.e., b - laststart.
 2473 
 2474                             We insert this at the beginning of the loop
 2475                             so that if we fail during matching, we'll
 2476                             reinitialize the bounds.  */
 2477                          insert_op2 (set_number_at, laststart, b - laststart,
 2478                                      upper_bound - 1, b);
 2479                          b += 5;
 2480                        }
 2481                    }
 2482                 pending_exact = 0;
 2483                 beg_interval = NULL;
 2484               }
 2485               break;
 2486 
 2487             unfetch_interval:
 2488               /* If an invalid interval, match the characters as literals.  */
 2489                assert (beg_interval);
 2490                p = beg_interval;
 2491                beg_interval = NULL;
 2492 
 2493                /* normal_char and normal_backslash need `c'.  */
 2494                PATFETCH (c);
 2495 
 2496                if (!(syntax & RE_NO_BK_BRACES))
 2497                  {
 2498                    if (p > pattern  &&  p[-1] == '\\')
 2499                      goto normal_backslash;
 2500                  }
 2501                goto normal_char;
 2502 
 2503 #ifdef emacs
 2504             /* There is no way to specify the before_dot and after_dot
 2505                operators.  rms says this is ok.  --karl  */
 2506             case '=':
 2507               BUF_PUSH (at_dot);
 2508               break;
 2509 
 2510             case 's':
 2511               laststart = b;
 2512               PATFETCH (c);
 2513               BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
 2514               break;
 2515 
 2516             case 'S':
 2517               laststart = b;
 2518               PATFETCH (c);
 2519               BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
 2520               break;
 2521 #endif /* emacs */
 2522 
 2523 
 2524             case 'w':
 2525               laststart = b;
 2526               BUF_PUSH (wordchar);
 2527               break;
 2528 
 2529 
 2530             case 'W':
 2531               laststart = b;
 2532               BUF_PUSH (notwordchar);
 2533               break;
 2534 
 2535 
 2536             case '<':
 2537               BUF_PUSH (wordbeg);
 2538               break;
 2539 
 2540             case '>':
 2541               BUF_PUSH (wordend);
 2542               break;
 2543 
 2544             case 'b':
 2545               BUF_PUSH (wordbound);
 2546               break;
 2547 
 2548             case 'B':
 2549               BUF_PUSH (notwordbound);
 2550               break;
 2551 
 2552             case '`':
 2553               BUF_PUSH (begbuf);
 2554               break;
 2555 
 2556             case '\'':
 2557               BUF_PUSH (endbuf);
 2558               break;
 2559 
 2560             case '1': case '2': case '3': case '4': case '5':
 2561             case '6': case '7': case '8': case '9':
 2562               if (syntax & RE_NO_BK_REFS)
 2563                 goto normal_char;
 2564 
 2565               c1 = c - '0';
 2566 
 2567               if (c1 > regnum)
 2568                 FREE_STACK_RETURN (REG_ESUBREG);
 2569 
 2570               /* Can't back reference to a subexpression if inside of it.  */
 2571               if (group_in_compile_stack (compile_stack, c1))
 2572                 goto normal_char;
 2573 
 2574               laststart = b;
 2575               BUF_PUSH_2 (duplicate, c1);
 2576               break;
 2577 
 2578 
 2579             case '+':
 2580             case '?':
 2581               if (syntax & RE_BK_PLUS_QM)
 2582                 goto handle_plus;
 2583               else
 2584                 goto normal_backslash;
 2585 
 2586             default:
 2587             normal_backslash:
 2588               /* You might think it would be useful for \ to mean
 2589                  not to translate; but if we don't translate it
 2590                  it will never match anything.  */
 2591               c = TRANSLATE (c);
 2592               goto normal_char;
 2593             }
 2594           break;
 2595 
 2596 
 2597     default:
 2598         /* Expects the character in `c'.  */
 2599     normal_char:
 2600           /* If no exactn currently being built.  */
 2601           if (!pending_exact
 2602 
 2603               /* If last exactn not at current position.  */
 2604               || pending_exact + *pending_exact + 1 != b
 2605 
 2606               /* We have only one byte following the exactn for the count.  */
 2607           || *pending_exact == (1 << BYTEWIDTH) - 1
 2608 
 2609               /* If followed by a repetition operator.  */
 2610               || *p == '*' || *p == '^'
 2611           || ((syntax & RE_BK_PLUS_QM)
 2612           ? *p == '\\' && (p[1] == '+' || p[1] == '?')
 2613           : (*p == '+' || *p == '?'))
 2614           || ((syntax & RE_INTERVALS)
 2615                   && ((syntax & RE_NO_BK_BRACES)
 2616               ? *p == '{'
 2617                       : (p[0] == '\\' && p[1] == '{'))))
 2618         {
 2619           /* Start building a new exactn.  */
 2620 
 2621               laststart = b;
 2622 
 2623           BUF_PUSH_2 (exactn, 0);
 2624           pending_exact = b - 1;
 2625             }
 2626 
 2627       BUF_PUSH (c);
 2628           (*pending_exact)++;
 2629       break;
 2630         } /* switch (c) */
 2631     } /* while p != pend */
 2632 
 2633 
 2634   /* Through the pattern now.  */
 2635 
 2636   if (fixup_alt_jump)
 2637     STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
 2638 
 2639   if (!COMPILE_STACK_EMPTY)
 2640     FREE_STACK_RETURN (REG_EPAREN);
 2641 
 2642   /* If we don't want backtracking, force success
 2643      the first time we reach the end of the compiled pattern.  */
 2644   if (syntax & RE_NO_POSIX_BACKTRACKING)
 2645     BUF_PUSH (succeed);
 2646 
 2647   free (compile_stack.stack);
 2648 
 2649   /* We have succeeded; set the length of the buffer.  */
 2650   bufp->used = b - bufp->buffer;
 2651 
 2652 #ifdef DEBUG
 2653   if (debug)
 2654     {
 2655       DEBUG_PRINT1 ("\nCompiled pattern: \n");
 2656       print_compiled_pattern (bufp);
 2657     }
 2658 #endif /* DEBUG */
 2659 
 2660 #ifndef MATCH_MAY_ALLOCATE
 2661   /* Initialize the failure stack to the largest possible stack.  This
 2662      isn't necessary unless we're trying to avoid calling alloca in
 2663      the search and match routines.  */
 2664   {
 2665     int num_regs = bufp->re_nsub + 1;
 2666 
 2667     /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
 2668        is strictly greater than re_max_failures, the largest possible stack
 2669        is 2 * re_max_failures failure points.  */
 2670     if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
 2671       {
 2672     fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
 2673 
 2674 #ifdef emacs
 2675     if (! fail_stack.stack)
 2676       fail_stack.stack
 2677         = (fail_stack_elt_t *) xmalloc (fail_stack.size
 2678                         * sizeof (fail_stack_elt_t));
 2679     else
 2680       fail_stack.stack
 2681         = (fail_stack_elt_t *) xrealloc (fail_stack.stack,
 2682                          (fail_stack.size
 2683                           * sizeof (fail_stack_elt_t)));
 2684 #else /* not emacs */
 2685     if (! fail_stack.stack)
 2686       fail_stack.stack
 2687         = (fail_stack_elt_t *) malloc (fail_stack.size
 2688                        * sizeof (fail_stack_elt_t));
 2689     else
 2690       fail_stack.stack
 2691         = (fail_stack_elt_t *) realloc (fail_stack.stack,
 2692                         (fail_stack.size
 2693                          * sizeof (fail_stack_elt_t)));
 2694 #endif /* not emacs */
 2695       }
 2696 
 2697     regex_grow_registers (num_regs);
 2698   }
 2699 #endif /* not MATCH_MAY_ALLOCATE */
 2700 
 2701   return REG_NOERROR;
 2702 } /* regex_compile */
 2703 
 2704 /* Subroutines for `regex_compile'.  */
 2705 
 2706 /* Store OP at LOC followed by two-byte integer parameter ARG.  */
 2707 
 2708 static void
 2709 store_op1 (op, loc, arg)
 2710     re_opcode_t op;
 2711     unsigned char *loc;
 2712     int arg;
 2713 {
 2714   *loc = (unsigned char) op;
 2715   STORE_NUMBER (loc + 1, arg);
 2716 }
 2717 
 2718 
 2719 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2.  */
 2720 
 2721 static void
 2722 store_op2 (op, loc, arg1, arg2)
 2723     re_opcode_t op;
 2724     unsigned char *loc;
 2725     int arg1, arg2;
 2726 {
 2727   *loc = (unsigned char) op;
 2728   STORE_NUMBER (loc + 1, arg1);
 2729   STORE_NUMBER (loc + 3, arg2);
 2730 }
 2731 
 2732 
 2733 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
 2734    for OP followed by two-byte integer parameter ARG.  */
 2735 
 2736 static void
 2737 insert_op1 (op, loc, arg, end)
 2738     re_opcode_t op;
 2739     unsigned char *loc;
 2740     int arg;
 2741     unsigned char *end;
 2742 {
 2743   register unsigned char *pfrom = end;
 2744   register unsigned char *pto = end + 3;
 2745 
 2746   while (pfrom != loc)
 2747     *--pto = *--pfrom;
 2748 
 2749   store_op1 (op, loc, arg);
 2750 }
 2751 
 2752 
 2753 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2.  */
 2754 
 2755 static void
 2756 insert_op2 (op, loc, arg1, arg2, end)
 2757     re_opcode_t op;
 2758     unsigned char *loc;
 2759     int arg1, arg2;
 2760     unsigned char *end;
 2761 {
 2762   register unsigned char *pfrom = end;
 2763   register unsigned char *pto = end + 5;
 2764 
 2765   while (pfrom != loc)
 2766     *--pto = *--pfrom;
 2767 
 2768   store_op2 (op, loc, arg1, arg2);
 2769 }
 2770 
 2771 
 2772 /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
 2773    after an alternative or a begin-subexpression.  We assume there is at
 2774    least one character before the ^.  */
 2775 
 2776 static boolean
 2777 at_begline_loc_p (pattern, p, syntax)
 2778     const char *pattern, *p;
 2779     reg_syntax_t syntax;
 2780 {
 2781   const char *prev = p - 2;
 2782   boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
 2783 
 2784   return
 2785        /* After a subexpression?  */
 2786        (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
 2787        /* After an alternative?  */
 2788     || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
 2789 }
 2790 
 2791 
 2792 /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
 2793    at least one character after the $, i.e., `P < PEND'.  */
 2794 
 2795 static boolean
 2796 at_endline_loc_p (p, pend, syntax)
 2797     const char *p, *pend;
 2798     int syntax;
 2799 {
 2800   const char *next = p;
 2801   boolean next_backslash = *next == '\\';
 2802   const char *next_next = p + 1 < pend ? p + 1 : 0;
 2803 
 2804   return
 2805        /* Before a subexpression?  */
 2806        (syntax & RE_NO_BK_PARENS ? *next == ')'
 2807         : next_backslash && next_next && *next_next == ')')
 2808        /* Before an alternative?  */
 2809     || (syntax & RE_NO_BK_VBAR ? *next == '|'
 2810         : next_backslash && next_next && *next_next == '|');
 2811 }
 2812 
 2813 
 2814 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
 2815    false if it's not.  */
 2816 
 2817 static boolean
 2818 group_in_compile_stack (compile_stack, regnum)
 2819     compile_stack_type compile_stack;
 2820     regnum_t regnum;
 2821 {
 2822   int this_element;
 2823 
 2824   for (this_element = compile_stack.avail - 1;
 2825        this_element >= 0;
 2826        this_element--)
 2827     if (compile_stack.stack[this_element].regnum == regnum)
 2828       return true;
 2829 
 2830   return false;
 2831 }
 2832 
 2833 
 2834 /* Read the ending character of a range (in a bracket expression) from the
 2835    uncompiled pattern *P_PTR (which ends at PEND).  We assume the
 2836    starting character is in `P[-2]'.  (`P[-1]' is the character `-'.)
 2837    Then we set the translation of all bits between the starting and
 2838    ending characters (inclusive) in the compiled pattern B.
 2839 
 2840    Return an error code.
 2841 
 2842    We use these short variable names so we can use the same macros as
 2843    `regex_compile' itself.  */
 2844 
 2845 static reg_errcode_t
 2846 compile_range (p_ptr, pend, translate, syntax, b)
 2847     const char **p_ptr, *pend;
 2848     RE_TRANSLATE_TYPE translate;
 2849     reg_syntax_t syntax;
 2850     unsigned char *b;
 2851 {
 2852   unsigned this_char;
 2853 
 2854   const char *p = *p_ptr;
 2855   int range_start, range_end;
 2856 
 2857   if (p == pend)
 2858     return REG_ERANGE;
 2859 
 2860   /* Even though the pattern is a signed `char *', we need to fetch
 2861      with unsigned char *'s; if the high bit of the pattern character
 2862      is set, the range endpoints will be negative if we fetch using a
 2863      signed char *.
 2864 
 2865      We also want to fetch the endpoints without translating them; the
 2866      appropriate translation is done in the bit-setting loop below.  */
 2867   /* The SVR4 compiler on the 3B2 had trouble with unsigned const char *.  */
 2868   range_start = ((const unsigned char *) p)[-2];
 2869   range_end   = ((const unsigned char *) p)[0];
 2870 
 2871   /* Have to increment the pointer into the pattern string, so the
 2872      caller isn't still at the ending character.  */
 2873   (*p_ptr)++;
 2874 
 2875   /* If the start is after the end, the range is empty.  */
 2876   if (range_start > range_end)
 2877     return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
 2878 
 2879   /* Here we see why `this_char' has to be larger than an `unsigned
 2880      char' -- the range is inclusive, so if `range_end' == 0xff
 2881      (assuming 8-bit characters), we would otherwise go into an infinite
 2882      loop, since all characters <= 0xff.  */
 2883   for (this_char = range_start; this_char <= range_end; this_char++)
 2884     {
 2885       SET_LIST_BIT (TRANSLATE (this_char));
 2886     }
 2887 
 2888   return REG_NOERROR;
 2889 }
 2890 
 2891 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
 2892    BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
 2893    characters can start a string that matches the pattern.  This fastmap
 2894    is used by re_search to skip quickly over impossible starting points.
 2895 
 2896    The caller must supply the address of a (1 << BYTEWIDTH)-byte data
 2897    area as BUFP->fastmap.
 2898 
 2899    We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
 2900    the pattern buffer.
 2901 
 2902    Returns 0 if we succeed, -2 if an internal error.   */
 2903 
 2904 int
 2905 re_compile_fastmap (bufp)
 2906      struct re_pattern_buffer *bufp;
 2907 {
 2908   int j, k;
 2909 #ifdef MATCH_MAY_ALLOCATE
 2910   fail_stack_type fail_stack;
 2911 #endif
 2912 #ifndef REGEX_MALLOC
 2913   char *destination;
 2914 #endif
 2915   /* We don't push any register information onto the failure stack.  */
 2916   unsigned num_regs = 0;
 2917 
 2918   register char *fastmap = bufp->fastmap;
 2919   unsigned char *pattern = bufp->buffer;
 2920   unsigned long size = bufp->used;
 2921   unsigned char *p = pattern;
 2922   register unsigned char *pend = pattern + size;
 2923 
 2924   /* This holds the pointer to the failure stack, when
 2925      it is allocated relocatably.  */
 2926 #ifdef REL_ALLOC
 2927   fail_stack_elt_t *failure_stack_ptr;
 2928 #endif
 2929 
 2930   /* Assume that each path through the pattern can be null until
 2931      proven otherwise.  We set this false at the bottom of switch
 2932      statement, to which we get only if a particular path doesn't
 2933      match the empty string.  */
 2934   boolean path_can_be_null = true;
 2935 
 2936   /* We aren't doing a `succeed_n' to begin with.  */
 2937   boolean succeed_n_p = false;
 2938 
 2939   assert (fastmap != NULL && p != NULL);
 2940 
 2941   INIT_FAIL_STACK ();
 2942   bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.  */
 2943   bufp->fastmap_accurate = 1;       /* It will be when we're done.  */
 2944   bufp->can_be_null = 0;
 2945 
 2946   while (1)
 2947     {
 2948       if (p == pend || *p == succeed)
 2949     {
 2950       /* We have reached the (effective) end of pattern.  */
 2951       if (!FAIL_STACK_EMPTY ())
 2952         {
 2953           bufp->can_be_null |= path_can_be_null;
 2954 
 2955           /* Reset for next path.  */
 2956           path_can_be_null = true;
 2957 
 2958           p = fail_stack.stack[--fail_stack.avail].pointer;
 2959 
 2960           continue;
 2961         }
 2962       else
 2963         break;
 2964     }
 2965 
 2966       /* We should never be about to go beyond the end of the pattern.  */
 2967       assert (p < pend);
 2968 
 2969       switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
 2970     {
 2971 
 2972         /* I guess the idea here is to simply not bother with a fastmap
 2973            if a backreference is used, since it's too hard to figure out
 2974            the fastmap for the corresponding group.  Setting
 2975            `can_be_null' stops `re_search_2' from using the fastmap, so
 2976            that is all we do.  */
 2977     case duplicate:
 2978       bufp->can_be_null = 1;
 2979           goto done;
 2980 
 2981 
 2982       /* Following are the cases which match a character.  These end
 2983          with `break'.  */
 2984 
 2985     case exactn:
 2986           fastmap[p[1]] = 1;
 2987       break;
 2988 
 2989 
 2990         case charset:
 2991           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
 2992         if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
 2993               fastmap[j] = 1;
 2994       break;
 2995 
 2996 
 2997     case charset_not:
 2998       /* Chars beyond end of map must be allowed.  */
 2999       for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
 3000             fastmap[j] = 1;
 3001 
 3002       for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
 3003         if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
 3004               fastmap[j] = 1;
 3005           break;
 3006 
 3007 
 3008     case wordchar:
 3009       for (j = 0; j < (1 << BYTEWIDTH); j++)
 3010         if (SYNTAX (j) == Sword)
 3011           fastmap[j] = 1;
 3012       break;
 3013 
 3014 
 3015     case notwordchar:
 3016       for (j = 0; j < (1 << BYTEWIDTH); j++)
 3017         if (SYNTAX (j) != Sword)
 3018           fastmap[j] = 1;
 3019       break;
 3020 
 3021 
 3022         case anychar:
 3023       {
 3024         int fastmap_newline = fastmap['\n'];
 3025 
 3026         /* `.' matches anything ...  */
 3027         for (j = 0; j < (1 << BYTEWIDTH); j++)
 3028           fastmap[j] = 1;
 3029 
 3030         /* ... except perhaps newline.  */
 3031         if (!(bufp->syntax & RE_DOT_NEWLINE))
 3032           fastmap['\n'] = fastmap_newline;
 3033 
 3034         /* Return if we have already set `can_be_null'; if we have,
 3035            then the fastmap is irrelevant.  Something's wrong here.  */
 3036         else if (bufp->can_be_null)
 3037           goto done;
 3038 
 3039         /* Otherwise, have to check alternative paths.  */
 3040         break;
 3041       }
 3042 
 3043 #ifdef emacs
 3044         case syntaxspec:
 3045       k = *p++;
 3046       for (j = 0; j < (1 << BYTEWIDTH); j++)
 3047         if (SYNTAX (j) == (enum syntaxcode) k)
 3048           fastmap[j] = 1;
 3049       break;
 3050 
 3051 
 3052     case notsyntaxspec:
 3053       k = *p++;
 3054       for (j = 0; j < (1 << BYTEWIDTH); j++)
 3055         if (SYNTAX (j) != (enum syntaxcode) k)
 3056           fastmap[j] = 1;
 3057       break;
 3058 
 3059 
 3060       /* All cases after this match the empty string.  These end with
 3061          `continue'.  */
 3062 
 3063 
 3064     case before_dot:
 3065     case at_dot:
 3066     case after_dot:
 3067           continue;
 3068 #endif /* emacs */
 3069 
 3070 
 3071         case no_op:
 3072         case begline:
 3073         case endline:
 3074     case begbuf:
 3075     case endbuf:
 3076     case wordbound:
 3077     case notwordbound:
 3078     case wordbeg:
 3079     case wordend:
 3080         case push_dummy_failure:
 3081           continue;
 3082 
 3083 
 3084     case jump_n:
 3085         case pop_failure_jump:
 3086     case maybe_pop_jump:
 3087     case jump:
 3088         case jump_past_alt:
 3089     case dummy_failure_jump:
 3090           EXTRACT_NUMBER_AND_INCR (j, p);
 3091       p += j;
 3092       if (j > 0)
 3093         continue;
 3094 
 3095           /* Jump backward implies we just went through the body of a
 3096              loop and matched nothing.  Opcode jumped to should be
 3097              `on_failure_jump' or `succeed_n'.  Just treat it like an
 3098              ordinary jump.  For a * loop, it has pushed its failure
 3099              point already; if so, discard that as redundant.  */
 3100           if ((re_opcode_t) *p != on_failure_jump
 3101           && (re_opcode_t) *p != succeed_n)
 3102         continue;
 3103 
 3104           p++;
 3105           EXTRACT_NUMBER_AND_INCR (j, p);
 3106           p += j;
 3107 
 3108           /* If what's on the stack is where we are now, pop it.  */
 3109           if (!FAIL_STACK_EMPTY ()
 3110           && fail_stack.stack[fail_stack.avail - 1].pointer == p)
 3111             fail_stack.avail--;
 3112 
 3113           continue;
 3114 
 3115 
 3116         case on_failure_jump:
 3117         case on_failure_keep_string_jump:
 3118     handle_on_failure_jump:
 3119           EXTRACT_NUMBER_AND_INCR (j, p);
 3120 
 3121           /* For some patterns, e.g., `(a?)?', `p+j' here points to the
 3122              end of the pattern.  We don't want to push such a point,
 3123              since when we restore it above, entering the switch will
 3124              increment `p' past the end of the pattern.  We don't need
 3125              to push such a point since we obviously won't find any more
 3126              fastmap entries beyond `pend'.  Such a pattern can match
 3127              the null string, though.  */
 3128           if (p + j < pend)
 3129             {
 3130               if (!PUSH_PATTERN_OP (p + j, fail_stack))
 3131         {
 3132           RESET_FAIL_STACK ();
 3133           return -2;
 3134         }
 3135             }
 3136           else
 3137             bufp->can_be_null = 1;
 3138 
 3139           if (succeed_n_p)
 3140             {
 3141               EXTRACT_NUMBER_AND_INCR (k, p);   /* Skip the n.  */
 3142               succeed_n_p = false;
 3143         }
 3144 
 3145           continue;
 3146 
 3147 
 3148     case succeed_n:
 3149           /* Get to the number of times to succeed.  */
 3150           p += 2;
 3151 
 3152           /* Increment p past the n for when k != 0.  */
 3153           EXTRACT_NUMBER_AND_INCR (k, p);
 3154           if (k == 0)
 3155         {
 3156               p -= 4;
 3157           succeed_n_p = true;  /* Spaghetti code alert.  */
 3158               goto handle_on_failure_jump;
 3159             }
 3160           continue;
 3161 
 3162 
 3163     case set_number_at:
 3164           p += 4;
 3165           continue;
 3166 
 3167 
 3168     case start_memory:
 3169         case stop_memory:
 3170       p += 2;
 3171       continue;
 3172 
 3173 
 3174     default:
 3175           abort (); /* We have listed all the cases.  */
 3176         } /* switch *p++ */
 3177 
 3178       /* Getting here means we have found the possible starting
 3179          characters for one path of the pattern -- and that the empty
 3180          string does not match.  We need not follow this path further.
 3181          Instead, look at the next alternative (remembered on the
 3182          stack), or quit if no more.  The test at the top of the loop
 3183          does these things.  */
 3184       path_can_be_null = false;
 3185       p = pend;
 3186     } /* while p */
 3187 
 3188   /* Set `can_be_null' for the last path (also the first path, if the
 3189      pattern is empty).  */
 3190   bufp->can_be_null |= path_can_be_null;
 3191 
 3192  done:
 3193   RESET_FAIL_STACK ();
 3194   return 0;
 3195 } /* re_compile_fastmap */
 3196 
 3197 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
 3198    ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use
 3199    this memory for recording register information.  STARTS and ENDS
 3200    must be allocated using the malloc library routine, and must each
 3201    be at least NUM_REGS * sizeof (regoff_t) bytes long.
 3202 
 3203    If NUM_REGS == 0, then subsequent matches should allocate their own
 3204    register data.
 3205 
 3206    Unless this function is called, the first search or match using
 3207    PATTERN_BUFFER will allocate its own register data, without
 3208    freeing the old data.  */
 3209 
 3210 void
 3211 re_set_registers (bufp, regs, num_regs, starts, ends)
 3212     struct re_pattern_buffer *bufp;
 3213     struct re_registers *regs;
 3214     unsigned num_regs;
 3215     regoff_t *starts, *ends;
 3216 {
 3217   if (num_regs)
 3218     {
 3219       bufp->regs_allocated = REGS_REALLOCATE;
 3220       regs->num_regs = num_regs;
 3221       regs->start = starts;
 3222       regs->end = ends;
 3223     }
 3224   else
 3225     {
 3226       bufp->regs_allocated = REGS_UNALLOCATED;
 3227       regs->num_regs = 0;
 3228       regs->start = regs->end = (regoff_t *) 0;
 3229     }
 3230 }
 3231 
 3232 /* Searching routines.  */
 3233 
 3234 /* Like re_search_2, below, but only one string is specified, and
 3235    doesn't let you say where to stop matching. */
 3236 
 3237 int
 3238 re_search (bufp, string, size, startpos, range, regs)
 3239      struct re_pattern_buffer *bufp;
 3240      const char *string;
 3241      int size, startpos, range;
 3242      struct re_registers *regs;
 3243 {
 3244   return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
 3245               regs, size);
 3246 }
 3247 
 3248 
 3249 /* Using the compiled pattern in BUFP->buffer, first tries to match the
 3250    virtual concatenation of STRING1 and STRING2, starting first at index
 3251    STARTPOS, then at STARTPOS + 1, and so on.
 3252 
 3253    STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
 3254 
 3255    RANGE is how far to scan while trying to match.  RANGE = 0 means try
 3256    only at STARTPOS; in general, the last start tried is STARTPOS +
 3257    RANGE.
 3258 
 3259    In REGS, return the indices of the virtual concatenation of STRING1
 3260    and STRING2 that matched the entire BUFP->buffer and its contained
 3261    subexpressions.
 3262 
 3263    Do not consider matching one past the index STOP in the virtual
 3264    concatenation of STRING1 and STRING2.
 3265 
 3266    We return either the position in the strings at which the match was
 3267    found, -1 if no match, or -2 if error (such as failure
 3268    stack overflow).  */
 3269 
 3270 int
 3271 re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop)
 3272      struct re_pattern_buffer *bufp;
 3273      const char *string1, *string2;
 3274      int size1, size2;
 3275      int startpos;
 3276      int range;
 3277      struct re_registers *regs;
 3278      int stop;
 3279 {
 3280   int val;
 3281   register char *fastmap = bufp->fastmap;
 3282   register RE_TRANSLATE_TYPE translate = bufp->translate;
 3283   int total_size = size1 + size2;
 3284   int endpos = startpos + range;
 3285 
 3286   /* Check for out-of-range STARTPOS.  */
 3287   if (startpos < 0 || startpos > total_size)
 3288     return -1;
 3289 
 3290   /* Fix up RANGE if it might eventually take us outside
 3291      the virtual concatenation of STRING1 and STRING2.
 3292      Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE.  */
 3293   if (endpos < 0)
 3294     range = 0 - startpos;
 3295   else if (endpos > total_size)
 3296     range = total_size - startpos;
 3297 
 3298   /* If the search isn't to be a backwards one, don't waste time in a
 3299      search for a pattern that must be anchored.  */
 3300   if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0)
 3301     {
 3302       if (startpos > 0)
 3303     return -1;
 3304       else
 3305     range = 1;
 3306     }
 3307 
 3308 #ifdef emacs
 3309   /* In a forward search for something that starts with \=.
 3310      don't keep searching past point.  */
 3311   if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == at_dot && range > 0)
 3312     {
 3313       range = PT - startpos;
 3314       if (range <= 0)
 3315     return -1;
 3316     }
 3317 #endif /* emacs */
 3318 
 3319   /* Update the fastmap now if not correct already.  */
 3320   if (fastmap && !bufp->fastmap_accurate)
 3321     if (re_compile_fastmap (bufp) == -2)
 3322       return -2;
 3323 
 3324   /* Loop through the string, looking for a place to start matching.  */
 3325   for (;;)
 3326     {
 3327       /* If a fastmap is supplied, skip quickly over characters that
 3328          cannot be the start of a match.  If the pattern can match the
 3329          null string, however, we don't need to skip characters; we want
 3330          the first null string.  */
 3331       if (fastmap && startpos < total_size && !bufp->can_be_null)
 3332     {
 3333       if (range > 0)    /* Searching forwards.  */
 3334         {
 3335           register const char *d;
 3336           register int lim = 0;
 3337           int irange = range;
 3338 
 3339               if (startpos < size1 && startpos + range >= size1)
 3340                 lim = range - (size1 - startpos);
 3341 
 3342           d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
 3343 
 3344               /* Written out as an if-else to avoid testing `translate'
 3345                  inside the loop.  */
 3346           if (translate)
 3347                 while (range > lim
 3348                        && !fastmap[(unsigned char)
 3349                    translate[(unsigned char) *d++]])
 3350                   range--;
 3351           else
 3352                 while (range > lim && !fastmap[(unsigned char) *d++])
 3353                   range--;
 3354 
 3355           startpos += irange - range;
 3356         }
 3357       else              /* Searching backwards.  */
 3358         {
 3359           register char c = (size1 == 0 || startpos >= size1
 3360                                  ? string2[startpos - size1]
 3361                                  : string1[startpos]);
 3362 
 3363           if (!fastmap[(unsigned char) TRANSLATE (c)])
 3364         goto advance;
 3365         }
 3366     }
 3367 
 3368       /* If can't match the null string, and that's all we have left, fail.  */
 3369       if (range >= 0 && startpos == total_size && fastmap
 3370           && !bufp->can_be_null)
 3371     return -1;
 3372 
 3373       val = re_match_2_internal (bufp, string1, size1, string2, size2,
 3374                  startpos, regs, stop);
 3375 #ifndef REGEX_MALLOC
 3376 #ifdef C_ALLOCA
 3377       alloca (0);
 3378 #endif
 3379 #endif
 3380 
 3381       if (val >= 0)
 3382     return startpos;
 3383 
 3384       if (val == -2)
 3385     return -2;
 3386 
 3387     advance:
 3388       if (!range)
 3389         break;
 3390       else if (range > 0)
 3391         {
 3392           range--;
 3393           startpos++;
 3394         }
 3395       else
 3396         {
 3397           range++;
 3398           startpos--;
 3399         }
 3400     }
 3401   return -1;
 3402 } /* re_search_2 */
 3403 
 3404 /* Declarations and macros for re_match_2.  */
 3405 
 3406 static int bcmp_translate ();
 3407 static boolean alt_match_null_string_p (),
 3408                common_op_match_null_string_p (),
 3409                group_match_null_string_p ();
 3410 
 3411 /* This converts PTR, a pointer into one of the search strings `string1'
 3412    and `string2' into an offset from the beginning of that string.  */
 3413 #define POINTER_TO_OFFSET(ptr)          \
 3414   (FIRST_STRING_P (ptr)             \
 3415    ? ((regoff_t) ((ptr) - string1))     \
 3416    : ((regoff_t) ((ptr) - string2 + size1)))
 3417 
 3418 /* Macros for dealing with the split strings in re_match_2.  */
 3419 
 3420 #define MATCHING_IN_FIRST_STRING  (dend == end_match_1)
 3421 
 3422 /* Call before fetching a character with *d.  This switches over to
 3423    string2 if necessary.  */
 3424 #define PREFETCH()                          \
 3425   while (d == dend)                             \
 3426     {                                   \
 3427       /* End of string2 => fail.  */                    \
 3428       if (dend == end_match_2)                      \
 3429         goto fail;                          \
 3430       /* End of string1 => advance to string2.  */          \
 3431       d = string2;                              \
 3432       dend = end_match_2;                       \
 3433     }
 3434 
 3435 
 3436 /* Test if at very beginning or at very end of the virtual concatenation
 3437    of `string1' and `string2'.  If only one string, it's `string2'.  */
 3438 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
 3439 #define AT_STRINGS_END(d) ((d) == end2)
 3440 
 3441 
 3442 /* Test if D points to a character which is word-constituent.  We have
 3443    two special cases to check for: if past the end of string1, look at
 3444    the first character in string2; and if before the beginning of
 3445    string2, look at the last character in string1.  */
 3446 #define WORDCHAR_P(d)                           \
 3447   (SYNTAX ((d) == end1 ? *string2                   \
 3448            : (d) == string2 - 1 ? *(end1 - 1) : *(d))           \
 3449    == Sword)
 3450 
 3451 /* Disabled due to a compiler bug -- see comment at case wordbound */
 3452 #if 0
 3453 /* Test if the character before D and the one at D differ with respect
 3454    to being word-constituent.  */
 3455 #define AT_WORD_BOUNDARY(d)                     \
 3456   (AT_STRINGS_BEG (d) || AT_STRINGS_END (d)             \
 3457    || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
 3458 #endif
 3459 
 3460 /* Free everything we malloc.  */
 3461 #ifdef MATCH_MAY_ALLOCATE
 3462 #define FREE_VAR(var) if (var) REGEX_FREE (var); var = NULL
 3463 #define FREE_VARIABLES()                        \
 3464   do {                                  \
 3465     REGEX_FREE_STACK (fail_stack.stack);                \
 3466     FREE_VAR (regstart);                        \
 3467     FREE_VAR (regend);                          \
 3468     FREE_VAR (old_regstart);                        \
 3469     FREE_VAR (old_regend);                      \
 3470     FREE_VAR (best_regstart);                       \
 3471     FREE_VAR (best_regend);                     \
 3472     FREE_VAR (reg_info);                        \
 3473     FREE_VAR (reg_dummy);                       \
 3474     FREE_VAR (reg_info_dummy);                      \
 3475   } while (0)
 3476 #else
 3477 #define FREE_VARIABLES() ((void)0) /* Do nothing!  But inhibit gcc warning.  */
 3478 #endif /* not MATCH_MAY_ALLOCATE */
 3479 
 3480 /* These values must meet several constraints.  They must not be valid
 3481    register values; since we have a limit of 255 registers (because
 3482    we use only one byte in the pattern for the register number), we can
 3483    use numbers larger than 255.  They must differ by 1, because of
 3484    NUM_FAILURE_ITEMS above.  And the value for the lowest register must
 3485    be larger than the value for the highest register, so we do not try
 3486    to actually save any registers when none are active.  */
 3487 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
 3488 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
 3489 
 3490 /* Matching routines.  */
 3491 
 3492 #ifndef emacs   /* Emacs never uses this.  */
 3493 /* re_match is like re_match_2 except it takes only a single string.  */
 3494 
 3495 int
 3496 re_match (bufp, string, size, pos, regs)
 3497      struct re_pattern_buffer *bufp;
 3498      const char *string;
 3499      int size, pos;
 3500      struct re_registers *regs;
 3501 {
 3502   int result = re_match_2_internal (bufp, NULL, 0, string, size,
 3503                     pos, regs, size);
 3504   alloca (0);
 3505   return result;
 3506 }
 3507 #endif /* not emacs */
 3508 
 3509 
 3510 /* re_match_2 matches the compiled pattern in BUFP against the
 3511    the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
 3512    and SIZE2, respectively).  We start matching at POS, and stop
 3513    matching at STOP.
 3514 
 3515    If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
 3516    store offsets for the substring each group matched in REGS.  See the
 3517    documentation for exactly how many groups we fill.
 3518 
 3519    We return -1 if no match, -2 if an internal error (such as the
 3520    failure stack overflowing).  Otherwise, we return the length of the
 3521    matched substring.  */
 3522 
 3523 int
 3524 re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
 3525      struct re_pattern_buffer *bufp;
 3526      const char *string1, *string2;
 3527      int size1, size2;
 3528      int pos;
 3529      struct re_registers *regs;
 3530      int stop;
 3531 {
 3532   int result = re_match_2_internal (bufp, string1, size1, string2, size2,
 3533                     pos, regs, stop);
 3534   alloca (0);
 3535   return result;
 3536 }
 3537 
 3538 /* This is a separate function so that we can force an alloca cleanup
 3539    afterwards.  */
 3540 static int
 3541 re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 3542      struct re_pattern_buffer *bufp;
 3543      const char *string1, *string2;
 3544      int size1, size2;
 3545      int pos;
 3546      struct re_registers *regs;
 3547      int stop;
 3548 {
 3549   /* General temporaries.  */
 3550   int mcnt;
 3551   unsigned char *p1;
 3552 
 3553   /* Just past the end of the corresponding string.  */
 3554   const char *end1, *end2;
 3555 
 3556   /* Pointers into string1 and string2, just past the last characters in
 3557      each to consider matching.  */
 3558   const char *end_match_1, *end_match_2;
 3559 
 3560   /* Where we are in the data, and the end of the current string.  */
 3561   const char *d, *dend;
 3562 
 3563   /* Where we are in the pattern, and the end of the pattern.  */
 3564   unsigned char *p = bufp->buffer;
 3565   register unsigned char *pend = p + bufp->used;
 3566 
 3567   /* Mark the opcode just after a start_memory, so we can test for an
 3568      empty subpattern when we get to the stop_memory.  */
 3569   unsigned char *just_past_start_mem = 0;
 3570 
 3571   /* We use this to map every character in the string.  */
 3572   RE_TRANSLATE_TYPE translate = bufp->translate;
 3573 
 3574   /* Failure point stack.  Each place that can handle a failure further
 3575      down the line pushes a failure point on this stack.  It consists of
 3576      restart, regend, and reg_info for all registers corresponding to
 3577      the subexpressions we're currently inside, plus the number of such
 3578      registers, and, finally, two char *'s.  The first char * is where
 3579      to resume scanning the pattern; the second one is where to resume
 3580      scanning the strings.  If the latter is zero, the failure point is
 3581      a ``dummy''; if a failure happens and the failure point is a dummy,
 3582      it gets discarded and the next next one is tried.  */
 3583 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global.  */
 3584   fail_stack_type fail_stack;
 3585 #endif
 3586 #ifdef DEBUG
 3587   static unsigned failure_id = 0;
 3588   unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
 3589 #endif
 3590 
 3591   /* This holds the pointer to the failure stack, when
 3592      it is allocated relocatably.  */
 3593 #ifdef REL_ALLOC
 3594   fail_stack_elt_t *failure_stack_ptr;
 3595 #endif
 3596 
 3597   /* We fill all the registers internally, independent of what we
 3598      return, for use in backreferences.  The number here includes
 3599      an element for register zero.  */
 3600   unsigned num_regs = bufp->re_nsub + 1;
 3601 
 3602   /* The currently active registers.  */
 3603   unsigned lowest_active_reg = NO_LOWEST_ACTIVE_REG;
 3604   unsigned highest_active_reg = NO_HIGHEST_ACTIVE_REG;
 3605 
 3606   /* Information on the contents of registers. These are pointers into
 3607      the input strings; they record just what was matched (on this
 3608      attempt) by a subexpression part of the pattern, that is, the
 3609      regnum-th regstart pointer points to where in the pattern we began
 3610      matching and the regnum-th regend points to right after where we
 3611      stopped matching the regnum-th subexpression.  (The zeroth register
 3612      keeps track of what the whole pattern matches.)  */
 3613 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
 3614   const char **regstart, **regend;
 3615 #endif
 3616 
 3617   /* If a group that's operated upon by a repetition operator fails to
 3618      match anything, then the register for its start will need to be
 3619      restored because it will have been set to wherever in the string we
 3620      are when we last see its open-group operator.  Similarly for a
 3621      register's end.  */
 3622 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
 3623   const char **old_regstart, **old_regend;
 3624 #endif
 3625 
 3626   /* The is_active field of reg_info helps us keep track of which (possibly
 3627      nested) subexpressions we are currently in. The matched_something
 3628      field of reg_info[reg_num] helps us tell whether or not we have
 3629      matched any of the pattern so far this time through the reg_num-th
 3630      subexpression.  These two fields get reset each time through any
 3631      loop their register is in.  */
 3632 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global.  */
 3633   register_info_type *reg_info;
 3634 #endif
 3635 
 3636   /* The following record the register info as found in the above
 3637      variables when we find a match better than any we've seen before.
 3638      This happens as we backtrack through the failure points, which in
 3639      turn happens only if we have not yet matched the entire string. */
 3640   unsigned best_regs_set = false;
 3641 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
 3642   const char **best_regstart, **best_regend;
 3643 #endif
 3644 
 3645   /* Logically, this is `best_regend[0]'.  But we don't want to have to
 3646      allocate space for that if we're not allocating space for anything
 3647      else (see below).  Also, we never need info about register 0 for
 3648      any of the other register vectors, and it seems rather a kludge to
 3649      treat `best_regend' differently than the rest.  So we keep track of
 3650      the end of the best match so far in a separate variable.  We
 3651      initialize this to NULL so that when we backtrack the first time
 3652      and need to test it, it's not garbage.  */
 3653   const char *match_end = NULL;
 3654 
 3655   /* This helps SET_REGS_MATCHED avoid doing redundant work.  */
 3656   int set_regs_matched_done = 0;
 3657 
 3658   /* Used when we pop values we don't care about.  */
 3659 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
 3660   const char **reg_dummy;
 3661   register_info_type *reg_info_dummy;
 3662 #endif
 3663 
 3664 #ifdef DEBUG
 3665   /* Counts the total number of registers pushed.  */
 3666   unsigned num_regs_pushed = 0;
 3667 #endif
 3668 
 3669   DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
 3670 
 3671   INIT_FAIL_STACK ();
 3672 
 3673 #ifdef MATCH_MAY_ALLOCATE
 3674   /* Do not bother to initialize all the register variables if there are
 3675      no groups in the pattern, as it takes a fair amount of time.  If
 3676      there are groups, we include space for register 0 (the whole
 3677      pattern), even though we never use it, since it simplifies the
 3678      array indexing.  We should fix this.  */
 3679   if (bufp->re_nsub)
 3680     {
 3681       regstart = REGEX_TALLOC (num_regs, const char *);
 3682       regend = REGEX_TALLOC (num_regs, const char *);
 3683       old_regstart = REGEX_TALLOC (num_regs, const char *);
 3684       old_regend = REGEX_TALLOC (num_regs, const char *);
 3685       best_regstart = REGEX_TALLOC (num_regs, const char *);
 3686       best_regend = REGEX_TALLOC (num_regs, const char *);
 3687       reg_info = REGEX_TALLOC (num_regs, register_info_type);
 3688       reg_dummy = REGEX_TALLOC (num_regs, const char *);
 3689       reg_info_dummy = REGEX_TALLOC (num_regs, register_info_type);
 3690 
 3691       if (!(regstart && regend && old_regstart && old_regend && reg_info
 3692             && best_regstart && best_regend && reg_dummy && reg_info_dummy))
 3693         {
 3694           FREE_VARIABLES ();
 3695           return -2;
 3696         }
 3697     }
 3698   else
 3699     {
 3700       /* We must initialize all our variables to NULL, so that
 3701          `FREE_VARIABLES' doesn't try to free them.  */
 3702       regstart = regend = old_regstart = old_regend = best_regstart
 3703         = best_regend = reg_dummy = NULL;
 3704       reg_info = reg_info_dummy = (register_info_type *) NULL;
 3705     }
 3706 #endif /* MATCH_MAY_ALLOCATE */
 3707 
 3708   /* The starting position is bogus.  */
 3709   if (pos < 0 || pos > size1 + size2)
 3710     {
 3711       FREE_VARIABLES ();
 3712       return -1;
 3713     }
 3714 
 3715   /* Initialize subexpression text positions to -1 to mark ones that no
 3716      start_memory/stop_memory has been seen for. Also initialize the
 3717      register information struct.  */
 3718   for (mcnt = 1; mcnt < num_regs; mcnt++)
 3719     {
 3720       regstart[mcnt] = regend[mcnt]
 3721         = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
 3722 
 3723       REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
 3724       IS_ACTIVE (reg_info[mcnt]) = 0;
 3725       MATCHED_SOMETHING (reg_info[mcnt]) = 0;
 3726       EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
 3727     }
 3728 
 3729   /* We move `string1' into `string2' if the latter's empty -- but not if
 3730      `string1' is null.  */
 3731   if (size2 == 0 && string1 != NULL)
 3732     {
 3733       string2 = string1;
 3734       size2 = size1;
 3735       string1 = 0;
 3736       size1 = 0;
 3737     }
 3738   end1 = string1 + size1;
 3739   end2 = string2 + size2;
 3740 
 3741   /* Compute where to stop matching, within the two strings.  */
 3742   if (stop <= size1)
 3743     {
 3744       end_match_1 = string1 + stop;
 3745       end_match_2 = string2;
 3746     }
 3747   else
 3748     {
 3749       end_match_1 = end1;
 3750       end_match_2 = string2 + stop - size1;
 3751     }
 3752 
 3753   /* `p' scans through the pattern as `d' scans through the data.
 3754      `dend' is the end of the input string that `d' points within.  `d'
 3755      is advanced into the following input string whenever necessary, but
 3756      this happens before fetching; therefore, at the beginning of the
 3757      loop, `d' can be pointing at the end of a string, but it cannot
 3758      equal `string2'.  */
 3759   if (size1 > 0 && pos <= size1)
 3760     {
 3761       d = string1 + pos;
 3762       dend = end_match_1;
 3763     }
 3764   else
 3765     {
 3766       d = string2 + pos - size1;
 3767       dend = end_match_2;
 3768     }
 3769 
 3770   DEBUG_PRINT1 ("The compiled pattern is: ");
 3771   DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
 3772   DEBUG_PRINT1 ("The string to match is: `");
 3773   DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
 3774   DEBUG_PRINT1 ("'\n");
 3775 
 3776   /* This loops over pattern commands.  It exits by returning from the
 3777      function if the match is complete, or it drops through if the match
 3778      fails at this starting point in the input data.  */
 3779   for (;;)
 3780     {
 3781       DEBUG_PRINT2 ("\n0x%x: ", p);
 3782 
 3783       if (p == pend)
 3784     { /* End of pattern means we might have succeeded.  */
 3785           DEBUG_PRINT1 ("end of pattern ... ");
 3786 
 3787       /* If we haven't matched the entire string, and we want the
 3788              longest match, try backtracking.  */
 3789           if (d != end_match_2)
 3790         {
 3791           /* 1 if this match ends in the same string (string1 or string2)
 3792          as the best previous match.  */
 3793           boolean same_str_p = (FIRST_STRING_P (match_end)
 3794                     == MATCHING_IN_FIRST_STRING);
 3795           /* 1 if this match is the best seen so far.  */
 3796           boolean best_match_p;
 3797 
 3798           /* AIX compiler got confused when this was combined
 3799          with the previous declaration.  */
 3800           if (same_str_p)
 3801         best_match_p = d > match_end;
 3802           else
 3803         best_match_p = !MATCHING_IN_FIRST_STRING;
 3804 
 3805               DEBUG_PRINT1 ("backtracking.\n");
 3806 
 3807               if (!FAIL_STACK_EMPTY ())
 3808                 { /* More failure points to try.  */
 3809 
 3810                   /* If exceeds best match so far, save it.  */
 3811                   if (!best_regs_set || best_match_p)
 3812                     {
 3813                       best_regs_set = true;
 3814                       match_end = d;
 3815 
 3816                       DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
 3817 
 3818                       for (mcnt = 1; mcnt < num_regs; mcnt++)
 3819                         {
 3820                           best_regstart[mcnt] = regstart[mcnt];
 3821                           best_regend[mcnt] = regend[mcnt];
 3822                         }
 3823                     }
 3824                   goto fail;
 3825                 }
 3826 
 3827               /* If no failure points, don't restore garbage.  And if
 3828                  last match is real best match, don't restore second
 3829                  best one. */
 3830               else if (best_regs_set && !best_match_p)
 3831                 {
 3832             restore_best_regs:
 3833                   /* Restore best match.  It may happen that `dend ==
 3834                      end_match_1' while the restored d is in string2.
 3835                      For example, the pattern `x.*y.*z' against the
 3836                      strings `x-' and `y-z-', if the two strings are
 3837                      not consecutive in memory.  */
 3838                   DEBUG_PRINT1 ("Restoring best registers.\n");
 3839 
 3840                   d = match_end;
 3841                   dend = ((d >= string1 && d <= end1)
 3842                    ? end_match_1 : end_match_2);
 3843 
 3844           for (mcnt = 1; mcnt < num_regs; mcnt++)
 3845             {
 3846               regstart[mcnt] = best_regstart[mcnt];
 3847               regend[mcnt] = best_regend[mcnt];
 3848             }
 3849                 }
 3850             } /* d != end_match_2 */
 3851 
 3852     succeed_label:
 3853           DEBUG_PRINT1 ("Accepting match.\n");
 3854 
 3855           /* If caller wants register contents data back, do it.  */
 3856           if (regs && !bufp->no_sub)
 3857         {
 3858               /* Have the register data arrays been allocated?  */
 3859               if (bufp->regs_allocated == REGS_UNALLOCATED)
 3860                 { /* No.  So allocate them with malloc.  We need one
 3861                      extra element beyond `num_regs' for the `-1' marker
 3862                      GNU code uses.  */
 3863                   regs->num_regs = MAX (RE_NREGS, num_regs + 1);
 3864                   regs->start = TALLOC (regs->num_regs, regoff_t);
 3865                   regs->end = TALLOC (regs->num_regs, regoff_t);
 3866                   if (regs->start == NULL || regs->end == NULL)
 3867             {
 3868               FREE_VARIABLES ();
 3869               return -2;
 3870             }
 3871                   bufp->regs_allocated = REGS_REALLOCATE;
 3872                 }
 3873               else if (bufp->regs_allocated == REGS_REALLOCATE)
 3874                 { /* Yes.  If we need more elements than were already
 3875                      allocated, reallocate them.  If we need fewer, just
 3876                      leave it alone.  */
 3877                   if (regs->num_regs < num_regs + 1)
 3878                     {
 3879                       regs->num_regs = num_regs + 1;
 3880                       RETALLOC (regs->start, regs->num_regs, regoff_t);
 3881                       RETALLOC (regs->end, regs->num_regs, regoff_t);
 3882                       if (regs->start == NULL || regs->end == NULL)
 3883             {
 3884               FREE_VARIABLES ();
 3885               return -2;
 3886             }
 3887                     }
 3888                 }
 3889               else
 3890         {
 3891           /* These braces fend off a "empty body in an else-statement"
 3892              warning under GCC when assert expands to nothing.  */
 3893           assert (bufp->regs_allocated == REGS_FIXED);
 3894         }
 3895 
 3896               /* Convert the pointer data in `regstart' and `regend' to
 3897                  indices.  Register zero has to be set differently,
 3898                  since we haven't kept track of any info for it.  */
 3899               if (regs->num_regs > 0)
 3900                 {
 3901                   regs->start[0] = pos;
 3902                   regs->end[0] = (MATCHING_IN_FIRST_STRING
 3903                   ? ((regoff_t) (d - string1))
 3904                       : ((regoff_t) (d - string2 + size1)));
 3905                 }
 3906 
 3907               /* Go through the first `min (num_regs, regs->num_regs)'
 3908                  registers, since that is all we initialized.  */
 3909           for (mcnt = 1; mcnt < MIN (num_regs, regs->num_regs); mcnt++)
 3910         {
 3911                   if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
 3912                     regs->start[mcnt] = regs->end[mcnt] = -1;
 3913                   else
 3914                     {
 3915               regs->start[mcnt]
 3916             = (regoff_t) POINTER_TO_OFFSET (regstart[mcnt]);
 3917                       regs->end[mcnt]
 3918             = (regoff_t) POINTER_TO_OFFSET (regend[mcnt]);
 3919                     }
 3920         }
 3921 
 3922               /* If the regs structure we return has more elements than
 3923                  were in the pattern, set the extra elements to -1.  If
 3924                  we (re)allocated the registers, this is the case,
 3925                  because we always allocate enough to have at least one
 3926                  -1 at the end.  */
 3927               for (mcnt = num_regs; mcnt < regs->num_regs; mcnt++)
 3928                 regs->start[mcnt] = regs->end[mcnt] = -1;
 3929         } /* regs && !bufp->no_sub */
 3930 
 3931           DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
 3932                         nfailure_points_pushed, nfailure_points_popped,
 3933                         nfailure_points_pushed - nfailure_points_popped);
 3934           DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
 3935 
 3936           mcnt = d - pos - (MATCHING_IN_FIRST_STRING
 3937                 ? string1
 3938                 : string2 - size1);
 3939 
 3940           DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
 3941 
 3942           FREE_VARIABLES ();
 3943           return mcnt;
 3944         }
 3945 
 3946       /* Otherwise match next pattern command.  */
 3947       switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
 3948     {
 3949         /* Ignore these.  Used to ignore the n of succeed_n's which
 3950            currently have n == 0.  */
 3951         case no_op:
 3952           DEBUG_PRINT1 ("EXECUTING no_op.\n");
 3953           break;
 3954 
 3955     case succeed:
 3956           DEBUG_PRINT1 ("EXECUTING succeed.\n");
 3957       goto succeed_label;
 3958 
 3959         /* Match the next n pattern characters exactly.  The following
 3960            byte in the pattern defines n, and the n bytes after that
 3961            are the characters to match.  */
 3962     case exactn:
 3963       mcnt = *p++;
 3964           DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
 3965 
 3966           /* This is written out as an if-else so we don't waste time
 3967              testing `translate' inside the loop.  */
 3968           if (translate)
 3969         {
 3970           do
 3971         {
 3972           PREFETCH ();
 3973           if ((unsigned char) translate[(unsigned char) *d++]
 3974               != (unsigned char) *p++)
 3975                     goto fail;
 3976         }
 3977           while (--mcnt);
 3978         }
 3979       else
 3980         {
 3981           do
 3982         {
 3983           PREFETCH ();
 3984           if (*d++ != (char) *p++) goto fail;
 3985         }
 3986           while (--mcnt);
 3987         }
 3988       SET_REGS_MATCHED ();
 3989           break;
 3990 
 3991 
 3992         /* Match any character except possibly a newline or a null.  */
 3993     case anychar:
 3994           DEBUG_PRINT1 ("EXECUTING anychar.\n");
 3995 
 3996           PREFETCH ();
 3997 
 3998           if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE (*d) == '\n')
 3999               || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE (*d) == '\000'))
 4000         goto fail;
 4001 
 4002           SET_REGS_MATCHED ();
 4003           DEBUG_PRINT2 ("  Matched `%d'.\n", *d);
 4004           d++;
 4005       break;
 4006 
 4007 
 4008     case charset:
 4009     case charset_not:
 4010       {
 4011         register unsigned char c;
 4012         boolean not = (re_opcode_t) *(p - 1) == charset_not;
 4013 
 4014             DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
 4015 
 4016         PREFETCH ();
 4017         c = TRANSLATE (*d); /* The character to match.  */
 4018 
 4019             /* Cast to `unsigned' instead of `unsigned char' in case the
 4020                bit list is a full 32 bytes long.  */
 4021         if (c < (unsigned) (*p * BYTEWIDTH)
 4022         && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
 4023           not = !not;
 4024 
 4025         p += 1 + *p;
 4026 
 4027         if (!not) goto fail;
 4028 
 4029         SET_REGS_MATCHED ();
 4030             d++;
 4031         break;
 4032       }
 4033 
 4034 
 4035         /* The beginning of a group is represented by start_memory.
 4036            The arguments are the register number in the next byte, and the
 4037            number of groups inner to this one in the next.  The text
 4038            matched within the group is recorded (in the internal
 4039            registers data structure) under the register number.  */
 4040         case start_memory:
 4041       DEBUG_PRINT3 ("EXECUTING start_memory %d (%d):\n", *p, p[1]);
 4042 
 4043           /* Find out if this group can match the empty string.  */
 4044       p1 = p;       /* To send to group_match_null_string_p.  */
 4045 
 4046           if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
 4047             REG_MATCH_NULL_STRING_P (reg_info[*p])
 4048               = group_match_null_string_p (&p1, pend, reg_info);
 4049 
 4050           /* Save the position in the string where we were the last time
 4051              we were at this open-group operator in case the group is
 4052              operated upon by a repetition operator, e.g., with `(a*)*b'
 4053              against `ab'; then we want to ignore where we are now in
 4054              the string in case this attempt to match fails.  */
 4055           old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
 4056                              ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
 4057                              : regstart[*p];
 4058       DEBUG_PRINT2 ("  old_regstart: %d\n",
 4059              POINTER_TO_OFFSET (old_regstart[*p]));
 4060 
 4061           regstart[*p] = d;
 4062       DEBUG_PRINT2 ("  regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
 4063 
 4064           IS_ACTIVE (reg_info[*p]) = 1;
 4065           MATCHED_SOMETHING (reg_info[*p]) = 0;
 4066 
 4067       /* Clear this whenever we change the register activity status.  */
 4068       set_regs_matched_done = 0;
 4069 
 4070           /* This is the new highest active register.  */
 4071           highest_active_reg = *p;
 4072 
 4073           /* If nothing was active before, this is the new lowest active
 4074              register.  */
 4075           if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
 4076             lowest_active_reg = *p;
 4077 
 4078           /* Move past the register number and inner group count.  */
 4079           p += 2;
 4080       just_past_start_mem = p;
 4081 
 4082           break;
 4083 
 4084 
 4085         /* The stop_memory opcode represents the end of a group.  Its
 4086            arguments are the same as start_memory's: the register
 4087            number, and the number of inner groups.  */
 4088     case stop_memory:
 4089       DEBUG_PRINT3 ("EXECUTING stop_memory %d (%d):\n", *p, p[1]);
 4090 
 4091           /* We need to save the string position the last time we were at
 4092              this close-group operator in case the group is operated
 4093              upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
 4094              against `aba'; then we want to ignore where we are now in
 4095              the string in case this attempt to match fails.  */
 4096           old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
 4097                            ? REG_UNSET (regend[*p]) ? d : regend[*p]
 4098                : regend[*p];
 4099       DEBUG_PRINT2 ("      old_regend: %d\n",
 4100              POINTER_TO_OFFSET (old_regend[*p]));
 4101 
 4102           regend[*p] = d;
 4103       DEBUG_PRINT2 ("      regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
 4104 
 4105           /* This register isn't active anymore.  */
 4106           IS_ACTIVE (reg_info[*p]) = 0;
 4107 
 4108       /* Clear this whenever we change the register activity status.  */
 4109       set_regs_matched_done = 0;
 4110 
 4111           /* If this was the only register active, nothing is active
 4112              anymore.  */
 4113           if (lowest_active_reg == highest_active_reg)
 4114             {
 4115               lowest_active_reg = NO_LOWEST_ACTIVE_REG;
 4116               highest_active_reg = NO_HIGHEST_ACTIVE_REG;
 4117             }
 4118           else
 4119             { /* We must scan for the new highest active register, since
 4120                  it isn't necessarily one less than now: consider
 4121                  (a(b)c(d(e)f)g).  When group 3 ends, after the f), the
 4122                  new highest active register is 1.  */
 4123               unsigned char r = *p - 1;
 4124               while (r > 0 && !IS_ACTIVE (reg_info[r]))
 4125                 r--;
 4126 
 4127               /* If we end up at register zero, that means that we saved
 4128                  the registers as the result of an `on_failure_jump', not
 4129                  a `start_memory', and we jumped to past the innermost
 4130                  `stop_memory'.  For example, in ((.)*) we save
 4131                  registers 1 and 2 as a result of the *, but when we pop
 4132                  back to the second ), we are at the stop_memory 1.
 4133                  Thus, nothing is active.  */
 4134           if (r == 0)
 4135                 {
 4136                   lowest_active_reg = NO_LOWEST_ACTIVE_REG;
 4137                   highest_active_reg = NO_HIGHEST_ACTIVE_REG;
 4138                 }
 4139               else
 4140                 highest_active_reg = r;
 4141             }
 4142 
 4143           /* If just failed to match something this time around with a
 4144              group that's operated on by a repetition operator, try to
 4145              force exit from the ``loop'', and restore the register
 4146              information for this group that we had before trying this
 4147              last match.  */
 4148           if ((!MATCHED_SOMETHING (reg_info[*p])
 4149                || just_past_start_mem == p - 1)
 4150           && (p + 2) < pend)
 4151             {
 4152               boolean is_a_jump_n = false;
 4153 
 4154               p1 = p + 2;
 4155               mcnt = 0;
 4156               switch ((re_opcode_t) *p1++)
 4157                 {
 4158                   case jump_n:
 4159             is_a_jump_n = true;
 4160                   case pop_failure_jump:
 4161           case maybe_pop_jump:
 4162           case jump:
 4163           case dummy_failure_jump:
 4164                     EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 4165             if (is_a_jump_n)
 4166               p1 += 2;
 4167                     break;
 4168 
 4169                   default:
 4170                     /* do nothing */ ;
 4171                 }
 4172           p1 += mcnt;
 4173 
 4174               /* If the next operation is a jump backwards in the pattern
 4175              to an on_failure_jump right before the start_memory
 4176                  corresponding to this stop_memory, exit from the loop
 4177                  by forcing a failure after pushing on the stack the
 4178                  on_failure_jump's jump in the pattern, and d.  */
 4179               if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
 4180                   && (re_opcode_t) p1[3] == start_memory && p1[4] == *p)
 4181         {
 4182                   /* If this group ever matched anything, then restore
 4183                      what its registers were before trying this last
 4184                      failed match, e.g., with `(a*)*b' against `ab' for
 4185                      regstart[1], and, e.g., with `((a*)*(b*)*)*'
 4186                      against `aba' for regend[3].
 4187 
 4188                      Also restore the registers for inner groups for,
 4189                      e.g., `((a*)(b*))*' against `aba' (register 3 would
 4190                      otherwise get trashed).  */
 4191 
 4192                   if (EVER_MATCHED_SOMETHING (reg_info[*p]))
 4193             {
 4194               unsigned r;
 4195 
 4196                       EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
 4197 
 4198               /* Restore this and inner groups' (if any) registers.  */
 4199                       for (r = *p; r < *p + *(p + 1); r++)
 4200                         {
 4201                           regstart[r] = old_regstart[r];
 4202 
 4203                           /* xx why this test?  */
 4204                           if (old_regend[r] >= regstart[r])
 4205                             regend[r] = old_regend[r];
 4206                         }
 4207                     }
 4208           p1++;
 4209                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 4210                   PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
 4211 
 4212                   goto fail;
 4213                 }
 4214             }
 4215 
 4216           /* Move past the register number and the inner group count.  */
 4217           p += 2;
 4218           break;
 4219 
 4220 
 4221     /* \<digit> has been turned into a `duplicate' command which is
 4222            followed by the numeric value of <digit> as the register number.  */
 4223         case duplicate:
 4224       {
 4225         register const char *d2, *dend2;
 4226         int regno = *p++;   /* Get which register to match against.  */
 4227         DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
 4228 
 4229         /* Can't back reference a group which we've never matched.  */
 4230             if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
 4231               goto fail;
 4232 
 4233             /* Where in input to try to start matching.  */
 4234             d2 = regstart[regno];
 4235 
 4236             /* Where to stop matching; if both the place to start and
 4237                the place to stop matching are in the same string, then
 4238                set to the place to stop, otherwise, for now have to use
 4239                the end of the first string.  */
 4240 
 4241             dend2 = ((FIRST_STRING_P (regstart[regno])
 4242               == FIRST_STRING_P (regend[regno]))
 4243              ? regend[regno] : end_match_1);
 4244         for (;;)
 4245           {
 4246         /* If necessary, advance to next segment in register
 4247                    contents.  */
 4248         while (d2 == dend2)
 4249           {
 4250             if (dend2 == end_match_2) break;
 4251             if (dend2 == regend[regno]) break;
 4252 
 4253                     /* End of string1 => advance to string2. */
 4254                     d2 = string2;
 4255                     dend2 = regend[regno];
 4256           }
 4257         /* At end of register contents => success */
 4258         if (d2 == dend2) break;
 4259 
 4260         /* If necessary, advance to next segment in data.  */
 4261         PREFETCH ();
 4262 
 4263         /* How many characters left in this segment to match.  */
 4264         mcnt = dend - d;
 4265 
 4266         /* Want how many consecutive characters we can match in
 4267                    one shot, so, if necessary, adjust the count.  */
 4268                 if (mcnt > dend2 - d2)
 4269           mcnt = dend2 - d2;
 4270 
 4271         /* Compare that many; failure if mismatch, else move
 4272                    past them.  */
 4273         if (translate
 4274                     ? bcmp_translate (d, d2, mcnt, translate)
 4275                     : bcmp (d, d2, mcnt))
 4276           goto fail;
 4277         d += mcnt, d2 += mcnt;
 4278 
 4279         /* Do this because we've match some characters.  */
 4280         SET_REGS_MATCHED ();
 4281           }
 4282       }
 4283       break;
 4284 
 4285 
 4286         /* begline matches the empty string at the beginning of the string
 4287            (unless `not_bol' is set in `bufp'), and, if
 4288            `newline_anchor' is set, after newlines.  */
 4289     case begline:
 4290           DEBUG_PRINT1 ("EXECUTING begline.\n");
 4291 
 4292           if (AT_STRINGS_BEG (d))
 4293             {
 4294               if (!bufp->not_bol) break;
 4295             }
 4296           else if (d[-1] == '\n' && bufp->newline_anchor)
 4297             {
 4298               break;
 4299             }
 4300           /* In all other cases, we fail.  */
 4301           goto fail;
 4302 
 4303 
 4304         /* endline is the dual of begline.  */
 4305     case endline:
 4306           DEBUG_PRINT1 ("EXECUTING endline.\n");
 4307 
 4308           if (AT_STRINGS_END (d))
 4309             {
 4310               if (!bufp->not_eol) break;
 4311             }
 4312 
 4313           /* We have to ``prefetch'' the next character.  */
 4314           else if ((d == end1 ? *string2 : *d) == '\n'
 4315                    && bufp->newline_anchor)
 4316             {
 4317               break;
 4318             }
 4319           goto fail;
 4320 
 4321 
 4322     /* Match at the very beginning of the data.  */
 4323         case begbuf:
 4324           DEBUG_PRINT1 ("EXECUTING begbuf.\n");
 4325           if (AT_STRINGS_BEG (d))
 4326             break;
 4327           goto fail;
 4328 
 4329 
 4330     /* Match at the very end of the data.  */
 4331         case endbuf:
 4332           DEBUG_PRINT1 ("EXECUTING endbuf.\n");
 4333       if (AT_STRINGS_END (d))
 4334         break;
 4335           goto fail;
 4336 
 4337 
 4338         /* on_failure_keep_string_jump is used to optimize `.*\n'.  It
 4339            pushes NULL as the value for the string on the stack.  Then
 4340            `pop_failure_point' will keep the current value for the
 4341            string, instead of restoring it.  To see why, consider
 4342            matching `foo\nbar' against `.*\n'.  The .* matches the foo;
 4343            then the . fails against the \n.  But the next thing we want
 4344            to do is match the \n against the \n; if we restored the
 4345            string value, we would be back at the foo.
 4346 
 4347            Because this is used only in specific cases, we don't need to
 4348            check all the things that `on_failure_jump' does, to make
 4349            sure the right things get saved on the stack.  Hence we don't
 4350            share its code.  The only reason to push anything on the
 4351            stack at all is that otherwise we would have to change
 4352            `anychar's code to do something besides goto fail in this
 4353            case; that seems worse than this.  */
 4354         case on_failure_keep_string_jump:
 4355           DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
 4356 
 4357           EXTRACT_NUMBER_AND_INCR (mcnt, p);
 4358           DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
 4359 
 4360           PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
 4361           break;
 4362 
 4363 
 4364     /* Uses of on_failure_jump:
 4365 
 4366            Each alternative starts with an on_failure_jump that points
 4367            to the beginning of the next alternative.  Each alternative
 4368            except the last ends with a jump that in effect jumps past
 4369            the rest of the alternatives.  (They really jump to the
 4370            ending jump of the following alternative, because tensioning
 4371            these jumps is a hassle.)
 4372 
 4373            Repeats start with an on_failure_jump that points past both
 4374            the repetition text and either the following jump or
 4375            pop_failure_jump back to this on_failure_jump.  */
 4376     case on_failure_jump:
 4377         on_failure:
 4378           DEBUG_PRINT1 ("EXECUTING on_failure_jump");
 4379 
 4380           EXTRACT_NUMBER_AND_INCR (mcnt, p);
 4381           DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
 4382 
 4383           /* If this on_failure_jump comes right before a group (i.e.,
 4384              the original * applied to a group), save the information
 4385              for that group and all inner ones, so that if we fail back
 4386              to this point, the group's information will be correct.
 4387              For example, in \(a*\)*\1, we need the preceding group,
 4388              and in \(zz\(a*\)b*\)\2, we need the inner group.  */
 4389 
 4390           /* We can't use `p' to check ahead because we push
 4391              a failure point to `p + mcnt' after we do this.  */
 4392           p1 = p;
 4393 
 4394           /* We need to skip no_op's before we look for the
 4395              start_memory in case this on_failure_jump is happening as
 4396              the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
 4397              against aba.  */
 4398           while (p1 < pend && (re_opcode_t) *p1 == no_op)
 4399             p1++;
 4400 
 4401           if (p1 < pend && (re_opcode_t) *p1 == start_memory)
 4402             {
 4403               /* We have a new highest active register now.  This will
 4404                  get reset at the start_memory we are about to get to,
 4405                  but we will have saved all the registers relevant to
 4406                  this repetition op, as described above.  */
 4407               highest_active_reg = *(p1 + 1) + *(p1 + 2);
 4408               if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
 4409                 lowest_active_reg = *(p1 + 1);
 4410             }
 4411 
 4412           DEBUG_PRINT1 (":\n");
 4413           PUSH_FAILURE_POINT (p + mcnt, d, -2);
 4414           break;
 4415 
 4416 
 4417         /* A smart repeat ends with `maybe_pop_jump'.
 4418        We change it to either `pop_failure_jump' or `jump'.  */
 4419         case maybe_pop_jump:
 4420           EXTRACT_NUMBER_AND_INCR (mcnt, p);
 4421           DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
 4422           {
 4423         register unsigned char *p2 = p;
 4424 
 4425             /* Compare the beginning of the repeat with what in the
 4426                pattern follows its end. If we can establish that there
 4427                is nothing that they would both match, i.e., that we
 4428                would have to backtrack because of (as in, e.g., `a*a')
 4429                then we can change to pop_failure_jump, because we'll
 4430                never have to backtrack.
 4431 
 4432                This is not true in the case of alternatives: in
 4433                `(a|ab)*' we do need to backtrack to the `ab' alternative
 4434                (e.g., if the string was `ab').  But instead of trying to
 4435                detect that here, the alternative has put on a dummy
 4436                failure point which is what we will end up popping.  */
 4437 
 4438         /* Skip over open/close-group commands.
 4439            If what follows this loop is a ...+ construct,
 4440            look at what begins its body, since we will have to
 4441            match at least one of that.  */
 4442         while (1)
 4443           {
 4444         if (p2 + 2 < pend
 4445             && ((re_opcode_t) *p2 == stop_memory
 4446             || (re_opcode_t) *p2 == start_memory))
 4447           p2 += 3;
 4448         else if (p2 + 6 < pend
 4449              && (re_opcode_t) *p2 == dummy_failure_jump)
 4450           p2 += 6;
 4451         else
 4452           break;
 4453           }
 4454 
 4455         p1 = p + mcnt;
 4456         /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
 4457            to the `maybe_finalize_jump' of this case.  Examine what
 4458            follows.  */
 4459 
 4460             /* If we're at the end of the pattern, we can change.  */
 4461             if (p2 == pend)
 4462           {
 4463         /* Consider what happens when matching ":\(.*\)"
 4464            against ":/".  I don't really understand this code
 4465            yet.  */
 4466             p[-3] = (unsigned char) pop_failure_jump;
 4467                 DEBUG_PRINT1
 4468                   ("  End of pattern: change to `pop_failure_jump'.\n");
 4469               }
 4470 
 4471             else if ((re_opcode_t) *p2 == exactn
 4472              || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
 4473           {
 4474         register unsigned char c
 4475                   = *p2 == (unsigned char) endline ? '\n' : p2[2];
 4476 
 4477                 if ((re_opcode_t) p1[3] == exactn && p1[5] != c)
 4478                   {
 4479             p[-3] = (unsigned char) pop_failure_jump;
 4480                     DEBUG_PRINT3 ("  %c != %c => pop_failure_jump.\n",
 4481                                   c, p1[5]);
 4482                   }
 4483 
 4484         else if ((re_opcode_t) p1[3] == charset
 4485              || (re_opcode_t) p1[3] == charset_not)
 4486           {
 4487             int not = (re_opcode_t) p1[3] == charset_not;
 4488 
 4489             if (c < (unsigned char) (p1[4] * BYTEWIDTH)
 4490             && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
 4491               not = !not;
 4492 
 4493                     /* `not' is equal to 1 if c would match, which means
 4494                         that we can't change to pop_failure_jump.  */
 4495             if (!not)
 4496                       {
 4497                 p[-3] = (unsigned char) pop_failure_jump;
 4498                         DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
 4499                       }
 4500           }
 4501           }
 4502             else if ((re_opcode_t) *p2 == charset)
 4503           {
 4504 #ifdef DEBUG
 4505         register unsigned char c
 4506                   = *p2 == (unsigned char) endline ? '\n' : p2[2];
 4507 #endif
 4508 
 4509                 if ((re_opcode_t) p1[3] == exactn
 4510             && ! ((int) p2[1] * BYTEWIDTH > (int) p1[5]
 4511               && (p2[2 + p1[5] / BYTEWIDTH]
 4512                   & (1 << (p1[5] % BYTEWIDTH)))))
 4513                   {
 4514             p[-3] = (unsigned char) pop_failure_jump;
 4515                     DEBUG_PRINT3 ("  %c != %c => pop_failure_jump.\n",
 4516                                   c, p1[5]);
 4517                   }
 4518 
 4519         else if ((re_opcode_t) p1[3] == charset_not)
 4520           {
 4521             int idx;
 4522             /* We win if the charset_not inside the loop
 4523                lists every character listed in the charset after.  */
 4524             for (idx = 0; idx < (int) p2[1]; idx++)
 4525               if (! (p2[2 + idx] == 0
 4526                  || (idx < (int) p1[4]
 4527                  && ((p2[2 + idx] & ~ p1[5 + idx]) == 0))))
 4528             break;
 4529 
 4530             if (idx == p2[1])
 4531                       {
 4532                 p[-3] = (unsigned char) pop_failure_jump;
 4533                         DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
 4534                       }
 4535           }
 4536         else if ((re_opcode_t) p1[3] == charset)
 4537           {
 4538             int idx;
 4539             /* We win if the charset inside the loop
 4540                has no overlap with the one after the loop.  */
 4541             for (idx = 0;
 4542              idx < (int) p2[1] && idx < (int) p1[4];
 4543              idx++)
 4544               if ((p2[2 + idx] & p1[5 + idx]) != 0)
 4545             break;
 4546 
 4547             if (idx == p2[1] || idx == p1[4])
 4548                       {
 4549                 p[-3] = (unsigned char) pop_failure_jump;
 4550                         DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
 4551                       }
 4552           }
 4553           }
 4554       }
 4555       p -= 2;       /* Point at relative address again.  */
 4556       if ((re_opcode_t) p[-1] != pop_failure_jump)
 4557         {
 4558           p[-1] = (unsigned char) jump;
 4559               DEBUG_PRINT1 ("  Match => jump.\n");
 4560           goto unconditional_jump;
 4561         }
 4562         /* Note fall through.  */
 4563 
 4564 
 4565     /* The end of a simple repeat has a pop_failure_jump back to
 4566            its matching on_failure_jump, where the latter will push a
 4567            failure point.  The pop_failure_jump takes off failure
 4568            points put on by this pop_failure_jump's matching
 4569            on_failure_jump; we got through the pattern to here from the
 4570            matching on_failure_jump, so didn't fail.  */
 4571         case pop_failure_jump:
 4572           {
 4573             /* We need to pass separate storage for the lowest and
 4574                highest registers, even though we don't care about the
 4575                actual values.  Otherwise, we will restore only one
 4576                register from the stack, since lowest will == highest in
 4577                `pop_failure_point'.  */
 4578             unsigned dummy_low_reg, dummy_high_reg;
 4579             unsigned char *pdummy;
 4580             const char *sdummy;
 4581 
 4582             DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
 4583             POP_FAILURE_POINT (sdummy, pdummy,
 4584                                dummy_low_reg, dummy_high_reg,
 4585                                reg_dummy, reg_dummy, reg_info_dummy);
 4586           }
 4587           /* Note fall through.  */
 4588 
 4589 
 4590         /* Unconditionally jump (without popping any failure points).  */
 4591         case jump:
 4592     unconditional_jump:
 4593       EXTRACT_NUMBER_AND_INCR (mcnt, p);    /* Get the amount to jump.  */
 4594           DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
 4595       p += mcnt;                /* Do the jump.  */
 4596           DEBUG_PRINT2 ("(to 0x%x).\n", p);
 4597       break;
 4598 
 4599 
 4600         /* We need this opcode so we can detect where alternatives end
 4601            in `group_match_null_string_p' et al.  */
 4602         case jump_past_alt:
 4603           DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
 4604           goto unconditional_jump;
 4605 
 4606 
 4607         /* Normally, the on_failure_jump pushes a failure point, which
 4608            then gets popped at pop_failure_jump.  We will end up at
 4609            pop_failure_jump, also, and with a pattern of, say, `a+', we
 4610            are skipping over the on_failure_jump, so we have to push
 4611            something meaningless for pop_failure_jump to pop.  */
 4612         case dummy_failure_jump:
 4613           DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
 4614           /* It doesn't matter what we push for the string here.  What
 4615              the code at `fail' tests is the value for the pattern.  */
 4616           PUSH_FAILURE_POINT (0, 0, -2);
 4617           goto unconditional_jump;
 4618 
 4619 
 4620         /* At the end of an alternative, we need to push a dummy failure
 4621            point in case we are followed by a `pop_failure_jump', because
 4622            we don't want the failure point for the alternative to be
 4623            popped.  For example, matching `(a|ab)*' against `aab'
 4624            requires that we match the `ab' alternative.  */
 4625         case push_dummy_failure:
 4626           DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
 4627           /* See comments just above at `dummy_failure_jump' about the
 4628              two zeroes.  */
 4629           PUSH_FAILURE_POINT (0, 0, -2);
 4630           break;
 4631 
 4632         /* Have to succeed matching what follows at least n times.
 4633            After that, handle like `on_failure_jump'.  */
 4634         case succeed_n:
 4635           EXTRACT_NUMBER (mcnt, p + 2);
 4636           DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
 4637 
 4638           assert (mcnt >= 0);
 4639           /* Originally, this is how many times we HAVE to succeed.  */
 4640           if (mcnt > 0)
 4641             {
 4642                mcnt--;
 4643            p += 2;
 4644                STORE_NUMBER_AND_INCR (p, mcnt);
 4645                DEBUG_PRINT3 ("  Setting 0x%x to %d.\n", p, mcnt);
 4646             }
 4647       else if (mcnt == 0)
 4648             {
 4649               DEBUG_PRINT2 ("  Setting two bytes from 0x%x to no_op.\n", p+2);
 4650           p[2] = (unsigned char) no_op;
 4651               p[3] = (unsigned char) no_op;
 4652               goto on_failure;
 4653             }
 4654           break;
 4655 
 4656         case jump_n:
 4657           EXTRACT_NUMBER (mcnt, p + 2);
 4658           DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
 4659 
 4660           /* Originally, this is how many times we CAN jump.  */
 4661           if (mcnt)
 4662             {
 4663                mcnt--;
 4664                STORE_NUMBER (p + 2, mcnt);
 4665            goto unconditional_jump;
 4666             }
 4667           /* If don't have to jump any more, skip over the rest of command.  */
 4668       else
 4669         p += 4;
 4670           break;
 4671 
 4672     case set_number_at:
 4673       {
 4674             DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
 4675 
 4676             EXTRACT_NUMBER_AND_INCR (mcnt, p);
 4677             p1 = p + mcnt;
 4678             EXTRACT_NUMBER_AND_INCR (mcnt, p);
 4679             DEBUG_PRINT3 ("  Setting 0x%x to %d.\n", p1, mcnt);
 4680         STORE_NUMBER (p1, mcnt);
 4681             break;
 4682           }
 4683 
 4684 #if 0
 4685     /* The DEC Alpha C compiler 3.x generates incorrect code for the
 4686        test  WORDCHAR_P (d - 1) != WORDCHAR_P (d)  in the expansion of
 4687        AT_WORD_BOUNDARY, so this code is disabled.  Expanding the
 4688        macro and introducing temporary variables works around the bug.  */
 4689 
 4690     case wordbound:
 4691       DEBUG_PRINT1 ("EXECUTING wordbound.\n");
 4692       if (AT_WORD_BOUNDARY (d))
 4693         break;
 4694       goto fail;
 4695 
 4696     case notwordbound:
 4697       DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
 4698       if (AT_WORD_BOUNDARY (d))
 4699         goto fail;
 4700       break;
 4701 #else
 4702     case wordbound:
 4703     {
 4704       boolean prevchar, thischar;
 4705 
 4706       DEBUG_PRINT1 ("EXECUTING wordbound.\n");
 4707       if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
 4708         break;
 4709 
 4710       prevchar = WORDCHAR_P (d - 1);
 4711       thischar = WORDCHAR_P (d);
 4712       if (prevchar != thischar)
 4713         break;
 4714       goto fail;
 4715     }
 4716 
 4717       case notwordbound:
 4718     {
 4719       boolean prevchar, thischar;
 4720 
 4721       DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
 4722       if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
 4723         goto fail;
 4724 
 4725       prevchar = WORDCHAR_P (d - 1);
 4726       thischar = WORDCHAR_P (d);
 4727       if (prevchar != thischar)
 4728         goto fail;
 4729       break;
 4730     }
 4731 #endif
 4732 
 4733     case wordbeg:
 4734           DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
 4735       if (WORDCHAR_P (d) && (AT_STRINGS_BEG (d) || !WORDCHAR_P (d - 1)))
 4736         break;
 4737           goto fail;
 4738 
 4739     case wordend:
 4740           DEBUG_PRINT1 ("EXECUTING wordend.\n");
 4741       if (!AT_STRINGS_BEG (d) && WORDCHAR_P (d - 1)
 4742               && (!WORDCHAR_P (d) || AT_STRINGS_END (d)))
 4743         break;
 4744           goto fail;
 4745 
 4746 #ifdef emacs
 4747     case before_dot:
 4748           DEBUG_PRINT1 ("EXECUTING before_dot.\n");
 4749       if (PTR_CHAR_POS ((unsigned char *) d) >= point)
 4750         goto fail;
 4751       break;
 4752 
 4753     case at_dot:
 4754           DEBUG_PRINT1 ("EXECUTING at_dot.\n");
 4755       if (PTR_CHAR_POS ((unsigned char *) d) != point)
 4756         goto fail;
 4757       break;
 4758 
 4759     case after_dot:
 4760           DEBUG_PRINT1 ("EXECUTING after_dot.\n");
 4761           if (PTR_CHAR_POS ((unsigned char *) d) <= point)
 4762         goto fail;
 4763       break;
 4764 
 4765     case syntaxspec:
 4766           DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
 4767       mcnt = *p++;
 4768       goto matchsyntax;
 4769 
 4770         case wordchar:
 4771           DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
 4772       mcnt = (int) Sword;
 4773         matchsyntax:
 4774       PREFETCH ();
 4775       /* Can't use *d++ here; SYNTAX may be an unsafe macro.  */
 4776       d++;
 4777       if (SYNTAX (d[-1]) != (enum syntaxcode) mcnt)
 4778         goto fail;
 4779           SET_REGS_MATCHED ();
 4780       break;
 4781 
 4782     case notsyntaxspec:
 4783           DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
 4784       mcnt = *p++;
 4785       goto matchnotsyntax;
 4786 
 4787         case notwordchar:
 4788           DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
 4789       mcnt = (int) Sword;
 4790         matchnotsyntax:
 4791       PREFETCH ();
 4792       /* Can't use *d++ here; SYNTAX may be an unsafe macro.  */
 4793       d++;
 4794       if (SYNTAX (d[-1]) == (enum syntaxcode) mcnt)
 4795         goto fail;
 4796       SET_REGS_MATCHED ();
 4797           break;
 4798 
 4799 #else /* not emacs */
 4800     case wordchar:
 4801           DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
 4802       PREFETCH ();
 4803           if (!WORDCHAR_P (d))
 4804             goto fail;
 4805       SET_REGS_MATCHED ();
 4806           d++;
 4807       break;
 4808 
 4809     case notwordchar:
 4810           DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
 4811       PREFETCH ();
 4812       if (WORDCHAR_P (d))
 4813             goto fail;
 4814           SET_REGS_MATCHED ();
 4815           d++;
 4816       break;
 4817 #endif /* not emacs */
 4818 
 4819         default:
 4820           abort ();
 4821     }
 4822       continue;  /* Successfully executed one pattern command; keep going.  */
 4823 
 4824 
 4825     /* We goto here if a matching operation fails. */
 4826     fail:
 4827       if (!FAIL_STACK_EMPTY ())
 4828     { /* A restart point is known.  Restore to that state.  */
 4829           DEBUG_PRINT1 ("\nFAIL:\n");
 4830           POP_FAILURE_POINT (d, p,
 4831                              lowest_active_reg, highest_active_reg,
 4832                              regstart, regend, reg_info);
 4833 
 4834           /* If this failure point is a dummy, try the next one.  */
 4835           if (!p)
 4836         goto fail;
 4837 
 4838           /* If we failed to the end of the pattern, don't examine *p.  */
 4839       assert (p <= pend);
 4840           if (p < pend)
 4841             {
 4842               boolean is_a_jump_n = false;
 4843 
 4844               /* If failed to a backwards jump that's part of a repetition
 4845                  loop, need to pop this failure point and use the next one.  */
 4846               switch ((re_opcode_t) *p)
 4847                 {
 4848                 case jump_n:
 4849                   is_a_jump_n = true;
 4850                 case maybe_pop_jump:
 4851                 case pop_failure_jump:
 4852                 case jump:
 4853                   p1 = p + 1;
 4854                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 4855                   p1 += mcnt;
 4856 
 4857                   if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
 4858                       || (!is_a_jump_n
 4859                           && (re_opcode_t) *p1 == on_failure_jump))
 4860                     goto fail;
 4861                   break;
 4862                 default:
 4863                   /* do nothing */ ;
 4864                 }
 4865             }
 4866 
 4867           if (d >= string1 && d <= end1)
 4868         dend = end_match_1;
 4869         }
 4870       else
 4871         break;   /* Matching at this starting point really fails.  */
 4872     } /* for (;;) */
 4873 
 4874   if (best_regs_set)
 4875     goto restore_best_regs;
 4876 
 4877   FREE_VARIABLES ();
 4878 
 4879   return -1;                    /* Failure to match.  */
 4880 } /* re_match_2 */
 4881 
 4882 /* Subroutine definitions for re_match_2.  */
 4883 
 4884 
 4885 /* We are passed P pointing to a register number after a start_memory.
 4886 
 4887    Return true if the pattern up to the corresponding stop_memory can
 4888    match the empty string, and false otherwise.
 4889 
 4890    If we find the matching stop_memory, sets P to point to one past its number.
 4891    Otherwise, sets P to an undefined byte less than or equal to END.
 4892 
 4893    We don't handle duplicates properly (yet).  */
 4894 
 4895 static boolean
 4896 group_match_null_string_p (p, end, reg_info)
 4897     unsigned char **p, *end;
 4898     register_info_type *reg_info;
 4899 {
 4900   int mcnt;
 4901   /* Point to after the args to the start_memory.  */
 4902   unsigned char *p1 = *p + 2;
 4903 
 4904   while (p1 < end)
 4905     {
 4906       /* Skip over opcodes that can match nothing, and return true or
 4907      false, as appropriate, when we get to one that can't, or to the
 4908          matching stop_memory.  */
 4909 
 4910       switch ((re_opcode_t) *p1)
 4911         {
 4912         /* Could be either a loop or a series of alternatives.  */
 4913         case on_failure_jump:
 4914           p1++;
 4915           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 4916 
 4917           /* If the next operation is not a jump backwards in the
 4918          pattern.  */
 4919 
 4920       if (mcnt >= 0)
 4921         {
 4922               /* Go through the on_failure_jumps of the alternatives,
 4923                  seeing if any of the alternatives cannot match nothing.
 4924                  The last alternative starts with only a jump,
 4925                  whereas the rest start with on_failure_jump and end
 4926                  with a jump, e.g., here is the pattern for `a|b|c':
 4927 
 4928                  /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
 4929                  /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
 4930                  /exactn/1/c
 4931 
 4932                  So, we have to first go through the first (n-1)
 4933                  alternatives and then deal with the last one separately.  */
 4934 
 4935 
 4936               /* Deal with the first (n-1) alternatives, which start
 4937                  with an on_failure_jump (see above) that jumps to right
 4938                  past a jump_past_alt.  */
 4939 
 4940               while ((re_opcode_t) p1[mcnt-3] == jump_past_alt)
 4941                 {
 4942                   /* `mcnt' holds how many bytes long the alternative
 4943                      is, including the ending `jump_past_alt' and
 4944                      its number.  */
 4945 
 4946                   if (!alt_match_null_string_p (p1, p1 + mcnt - 3,
 4947                                       reg_info))
 4948                     return false;
 4949 
 4950                   /* Move to right after this alternative, including the
 4951              jump_past_alt.  */
 4952                   p1 += mcnt;
 4953 
 4954                   /* Break if it's the beginning of an n-th alternative
 4955                      that doesn't begin with an on_failure_jump.  */
 4956                   if ((re_opcode_t) *p1 != on_failure_jump)
 4957                     break;
 4958 
 4959           /* Still have to check that it's not an n-th
 4960              alternative that starts with an on_failure_jump.  */
 4961           p1++;
 4962                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 4963                   if ((re_opcode_t) p1[mcnt-3] != jump_past_alt)
 4964                     {
 4965               /* Get to the beginning of the n-th alternative.  */
 4966                       p1 -= 3;
 4967                       break;
 4968                     }
 4969                 }
 4970 
 4971               /* Deal with the last alternative: go back and get number
 4972                  of the `jump_past_alt' just before it.  `mcnt' contains
 4973                  the length of the alternative.  */
 4974               EXTRACT_NUMBER (mcnt, p1 - 2);
 4975 
 4976               if (!alt_match_null_string_p (p1, p1 + mcnt, reg_info))
 4977                 return false;
 4978 
 4979               p1 += mcnt;   /* Get past the n-th alternative.  */
 4980             } /* if mcnt > 0 */
 4981           break;
 4982 
 4983 
 4984         case stop_memory:
 4985       assert (p1[1] == **p);
 4986           *p = p1 + 2;
 4987           return true;
 4988 
 4989 
 4990         default:
 4991           if (!common_op_match_null_string_p (&p1, end, reg_info))
 4992             return false;
 4993         }
 4994     } /* while p1 < end */
 4995 
 4996   return false;
 4997 } /* group_match_null_string_p */
 4998 
 4999 
 5000 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
 5001    It expects P to be the first byte of a single alternative and END one
 5002    byte past the last. The alternative can contain groups.  */
 5003 
 5004 static boolean
 5005 alt_match_null_string_p (p, end, reg_info)
 5006     unsigned char *p, *end;
 5007     register_info_type *reg_info;
 5008 {
 5009   int mcnt;
 5010   unsigned char *p1 = p;
 5011 
 5012   while (p1 < end)
 5013     {
 5014       /* Skip over opcodes that can match nothing, and break when we get
 5015          to one that can't.  */
 5016 
 5017       switch ((re_opcode_t) *p1)
 5018         {
 5019     /* It's a loop.  */
 5020         case on_failure_jump:
 5021           p1++;
 5022           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 5023           p1 += mcnt;
 5024           break;
 5025 
 5026     default:
 5027           if (!common_op_match_null_string_p (&p1, end, reg_info))
 5028             return false;
 5029         }
 5030     }  /* while p1 < end */
 5031 
 5032   return true;
 5033 } /* alt_match_null_string_p */
 5034 
 5035 
 5036 /* Deals with the ops common to group_match_null_string_p and
 5037    alt_match_null_string_p.
 5038 
 5039    Sets P to one after the op and its arguments, if any.  */
 5040 
 5041 static boolean
 5042 common_op_match_null_string_p (p, end, reg_info)
 5043     unsigned char **p, *end;
 5044     register_info_type *reg_info;
 5045 {
 5046   int mcnt;
 5047   boolean ret;
 5048   int reg_no;
 5049   unsigned char *p1 = *p;
 5050 
 5051   switch ((re_opcode_t) *p1++)
 5052     {
 5053     case no_op:
 5054     case begline:
 5055     case endline:
 5056     case begbuf:
 5057     case endbuf:
 5058     case wordbeg:
 5059     case wordend:
 5060     case wordbound:
 5061     case notwordbound:
 5062 #ifdef emacs
 5063     case before_dot:
 5064     case at_dot:
 5065     case after_dot:
 5066 #endif
 5067       break;
 5068 
 5069     case start_memory:
 5070       reg_no = *p1;
 5071       assert (reg_no > 0 && reg_no <= MAX_REGNUM);
 5072       ret = group_match_null_string_p (&p1, end, reg_info);
 5073 
 5074       /* Have to set this here in case we're checking a group which
 5075          contains a group and a back reference to it.  */
 5076 
 5077       if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
 5078         REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
 5079 
 5080       if (!ret)
 5081         return false;
 5082       break;
 5083 
 5084     /* If this is an optimized succeed_n for zero times, make the jump.  */
 5085     case jump:
 5086       EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 5087       if (mcnt >= 0)
 5088         p1 += mcnt;
 5089       else
 5090         return false;
 5091       break;
 5092 
 5093     case succeed_n:
 5094       /* Get to the number of times to succeed.  */
 5095       p1 += 2;
 5096       EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 5097 
 5098       if (mcnt == 0)
 5099         {
 5100           p1 -= 4;
 5101           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
 5102           p1 += mcnt;
 5103         }
 5104       else
 5105         return false;
 5106       break;
 5107 
 5108     case duplicate:
 5109       if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
 5110         return false;
 5111       break;
 5112 
 5113     case set_number_at:
 5114       p1 += 4;
 5115 
 5116     default:
 5117       /* All other opcodes mean we cannot match the empty string.  */
 5118       return false;
 5119   }
 5120 
 5121   *p = p1;
 5122   return true;
 5123 } /* common_op_match_null_string_p */
 5124 
 5125 
 5126 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
 5127    bytes; nonzero otherwise.  */
 5128 
 5129 static int
 5130 bcmp_translate (s1, s2, len, translate)
 5131      unsigned char *s1, *s2;
 5132      register int len;
 5133      RE_TRANSLATE_TYPE translate;
 5134 {
 5135   register unsigned char *p1 = s1, *p2 = s2;
 5136   while (len)
 5137     {
 5138       if (translate[*p1++] != translate[*p2++]) return 1;
 5139       len--;
 5140     }
 5141   return 0;
 5142 }
 5143 
 5144 /* Entry points for GNU code.  */
 5145 
 5146 /* re_compile_pattern is the GNU regular expression compiler: it
 5147    compiles PATTERN (of length SIZE) and puts the result in BUFP.
 5148    Returns 0 if the pattern was valid, otherwise an error string.
 5149 
 5150    Assumes the `allocated' (and perhaps `buffer') and `translate' fields
 5151    are set in BUFP on entry.
 5152 
 5153    We call regex_compile to do the actual compilation.  */
 5154 
 5155 const char *
 5156 re_compile_pattern (pattern, length, bufp)
 5157      const char *pattern;
 5158      int length;
 5159      struct re_pattern_buffer *bufp;
 5160 {
 5161   reg_errcode_t ret;
 5162 
 5163   /* GNU code is written to assume at least RE_NREGS registers will be set
 5164      (and at least one extra will be -1).  */
 5165   bufp->regs_allocated = REGS_UNALLOCATED;
 5166 
 5167   /* And GNU code determines whether or not to get register information
 5168      by passing null for the REGS argument to re_match, etc., not by
 5169      setting no_sub.  */
 5170   bufp->no_sub = 0;
 5171 
 5172   /* Match anchors at newline.  */
 5173   bufp->newline_anchor = 1;
 5174 
 5175   ret = regex_compile (pattern, length, re_syntax_options, bufp);
 5176 
 5177   if (!ret)
 5178     return NULL;
 5179   return gettext (re_error_msgid[(int) ret]);
 5180 }
 5181 
 5182 /* Entry points compatible with 4.2 BSD regex library.  We don't define
 5183    them unless specifically requested.  */
 5184 
 5185 #ifdef _REGEX_RE_COMP
 5186 
 5187 /* BSD has one and only one pattern buffer.  */
 5188 static struct re_pattern_buffer re_comp_buf;
 5189 
 5190 char *
 5191 re_comp (s)
 5192     const char *s;
 5193 {
 5194   reg_errcode_t ret;
 5195 
 5196   if (!s)
 5197     {
 5198       if (!re_comp_buf.buffer)
 5199     return gettext ("No previous regular expression");
 5200       return 0;
 5201     }
 5202 
 5203   if (!re_comp_buf.buffer)
 5204     {
 5205       re_comp_buf.buffer = (unsigned char *) malloc (200);
 5206       if (re_comp_buf.buffer == NULL)
 5207         return gettext (re_error_msgid[(int) REG_ESPACE]);
 5208       re_comp_buf.allocated = 200;
 5209 
 5210       re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH);
 5211       if (re_comp_buf.fastmap == NULL)
 5212     return gettext (re_error_msgid[(int) REG_ESPACE]);
 5213     }
 5214 
 5215   /* Since `re_exec' always passes NULL for the `regs' argument, we
 5216      don't need to initialize the pattern buffer fields which affect it.  */
 5217 
 5218   /* Match anchors at newlines.  */
 5219   re_comp_buf.newline_anchor = 1;
 5220 
 5221   ret = regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
 5222 
 5223   if (!ret)
 5224     return NULL;
 5225 
 5226   /* Yes, we're discarding `const' here if !HAVE_LIBINTL.  */
 5227   return (char *) gettext (re_error_msgid[(int) ret]);
 5228 }
 5229 
 5230 
 5231 int
 5232 re_exec (s)
 5233     const char *s;
 5234 {
 5235   const int len = strlen (s);
 5236   return
 5237     0 <= re_search (&re_comp_buf, s, len, 0, len, (struct re_registers *) 0);
 5238 }
 5239 #endif /* _REGEX_RE_COMP */
 5240 
 5241 /* POSIX.2 functions.  Don't define these for Emacs.  */
 5242 
 5243 #ifndef emacs
 5244 
 5245 /* regcomp takes a regular expression as a string and compiles it.
 5246 
 5247    PREG is a regex_t *.  We do not expect any fields to be initialized,
 5248    since POSIX says we shouldn't.  Thus, we set
 5249 
 5250      `buffer' to the compiled pattern;
 5251      `used' to the length of the compiled pattern;
 5252      `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
 5253        REG_EXTENDED bit in CFLAGS is set; otherwise, to
 5254        RE_SYNTAX_POSIX_BASIC;
 5255      `newline_anchor' to REG_NEWLINE being set in CFLAGS;
 5256      `fastmap' and `fastmap_accurate' to zero;
 5257      `re_nsub' to the number of subexpressions in PATTERN.
 5258 
 5259    PATTERN is the address of the pattern string.
 5260 
 5261    CFLAGS is a series of bits which affect compilation.
 5262 
 5263      If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
 5264      use POSIX basic syntax.
 5265 
 5266      If REG_NEWLINE is set, then . and [^...] don't match newline.
 5267      Also, regexec will try a match beginning after every newline.
 5268 
 5269      If REG_ICASE is set, then we considers upper- and lowercase
 5270      versions of letters to be equivalent when matching.
 5271 
 5272      If REG_NOSUB is set, then when PREG is passed to regexec, that
 5273      routine will report only success or failure, and nothing about the
 5274      registers.
 5275 
 5276    It returns 0 if it succeeds, nonzero if it doesn't.  (See regex.h for
 5277    the return codes and their meanings.)  */
 5278 
 5279 int
 5280 regcomp (preg, pattern, cflags)
 5281     regex_t *preg;
 5282     const char *pattern;
 5283     int cflags;
 5284 {
 5285   reg_errcode_t ret;
 5286   unsigned syntax
 5287     = (cflags & REG_EXTENDED) ?
 5288       RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
 5289 
 5290   /* regex_compile will allocate the space for the compiled pattern.  */
 5291   preg->buffer = 0;
 5292   preg->allocated = 0;
 5293   preg->used = 0;
 5294 
 5295   /* Don't bother to use a fastmap when searching.  This simplifies the
 5296      REG_NEWLINE case: if we used a fastmap, we'd have to put all the
 5297      characters after newlines into the fastmap.  This way, we just try
 5298      every character.  */
 5299   preg->fastmap = 0;
 5300 
 5301   if (cflags & REG_ICASE)
 5302     {
 5303       unsigned i;
 5304 
 5305       preg->translate
 5306     = (RE_TRANSLATE_TYPE) malloc (CHAR_SET_SIZE
 5307                       * sizeof (*(RE_TRANSLATE_TYPE)0));
 5308       if (preg->translate == NULL)
 5309         return (int) REG_ESPACE;
 5310 
 5311       /* Map uppercase characters to corresponding lowercase ones.  */
 5312       for (i = 0; i < CHAR_SET_SIZE; i++)
 5313         preg->translate[i] = ISUPPER (i) ? tolower (i) : i;
 5314     }
 5315   else
 5316     preg->translate = NULL;
 5317 
 5318   /* If REG_NEWLINE is set, newlines are treated differently.  */
 5319   if (cflags & REG_NEWLINE)
 5320     { /* REG_NEWLINE implies neither . nor [^...] match newline.  */
 5321       syntax &= ~RE_DOT_NEWLINE;
 5322       syntax |= RE_HAT_LISTS_NOT_NEWLINE;
 5323       /* It also changes the matching behavior.  */
 5324       preg->newline_anchor = 1;
 5325     }
 5326   else
 5327     preg->newline_anchor = 0;
 5328 
 5329   preg->no_sub = !!(cflags & REG_NOSUB);
 5330 
 5331   /* POSIX says a null character in the pattern terminates it, so we
 5332      can use strlen here in compiling the pattern.  */
 5333   ret = regex_compile (pattern, strlen (pattern), syntax, preg);
 5334 
 5335   /* POSIX doesn't distinguish between an unmatched open-group and an
 5336      unmatched close-group: both are REG_EPAREN.  */
 5337   if (ret == REG_ERPAREN) ret = REG_EPAREN;
 5338 
 5339   return (int) ret;
 5340 }
 5341 
 5342 
 5343 /* regexec searches for a given pattern, specified by PREG, in the
 5344    string STRING.
 5345 
 5346    If NMATCH is zero or REG_NOSUB was set in the cflags argument to
 5347    `regcomp', we ignore PMATCH.  Otherwise, we assume PMATCH has at
 5348    least NMATCH elements, and we set them to the offsets of the
 5349    corresponding matched substrings.
 5350 
 5351    EFLAGS specifies `execution flags' which affect matching: if
 5352    REG_NOTBOL is set, then ^ does not match at the beginning of the
 5353    string; if REG_NOTEOL is set, then $ does not match at the end.
 5354 
 5355    We return 0 if we find a match and REG_NOMATCH if not.  */
 5356 
 5357 int
 5358 regexec (preg, string, nmatch, pmatch, eflags)
 5359     const regex_t *preg;
 5360     const char *string;
 5361     size_t nmatch;
 5362     regmatch_t pmatch[];
 5363     int eflags;
 5364 {
 5365   int ret;
 5366   struct re_registers regs;
 5367   regex_t private_preg;
 5368   int len = strlen (string);
 5369   boolean want_reg_info = !preg->no_sub && nmatch > 0;
 5370 
 5371   private_preg = *preg;
 5372 
 5373   private_preg.not_bol = !!(eflags & REG_NOTBOL);
 5374   private_preg.not_eol = !!(eflags & REG_NOTEOL);
 5375 
 5376   /* The user has told us exactly how many registers to return
 5377      information about, via `nmatch'.  We have to pass that on to the
 5378      matching routines.  */
 5379   private_preg.regs_allocated = REGS_FIXED;
 5380 
 5381   if (want_reg_info)
 5382     {
 5383       regs.num_regs = nmatch;
 5384       regs.start = TALLOC (nmatch, regoff_t);
 5385       regs.end = TALLOC (nmatch, regoff_t);
 5386       if (regs.start == NULL || regs.end == NULL)
 5387         return (int) REG_NOMATCH;
 5388     }
 5389 
 5390   /* Perform the searching operation.  */
 5391   ret = re_search (&private_preg, string, len,
 5392                    /* start: */ 0, /* range: */ len,
 5393                    want_reg_info ? &regs : (struct re_registers *) 0);
 5394 
 5395   /* Copy the register information to the POSIX structure.  */
 5396   if (want_reg_info)
 5397     {
 5398       if (ret >= 0)
 5399         {
 5400           unsigned r;
 5401 
 5402           for (r = 0; r < nmatch; r++)
 5403             {
 5404               pmatch[r].rm_so = regs.start[r];
 5405               pmatch[r].rm_eo = regs.end[r];
 5406             }
 5407         }
 5408 
 5409       /* If we needed the temporary register info, free the space now.  */
 5410       free (regs.start);
 5411       free (regs.end);
 5412     }
 5413 
 5414   /* We want zero return to mean success, unlike `re_search'.  */
 5415   return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
 5416 }
 5417 
 5418 
 5419 /* Returns a message corresponding to an error code, ERRCODE, returned
 5420    from either regcomp or regexec.   We don't use PREG here.  */
 5421 
 5422 size_t
 5423 regerror (errcode, preg, errbuf, errbuf_size)
 5424     int errcode;
 5425     const regex_t *preg;
 5426     char *errbuf;
 5427     size_t errbuf_size;
 5428 {
 5429   const char *msg;
 5430   size_t msg_size;
 5431 
 5432   if (errcode < 0
 5433       || errcode >= (sizeof (re_error_msgid) / sizeof (re_error_msgid[0])))
 5434     /* Only error codes returned by the rest of the code should be passed
 5435        to this routine.  If we are given anything else, or if other regex
 5436        code generates an invalid error code, then the program has a bug.
 5437        Dump core so we can fix it.  */
 5438     abort ();
 5439 
 5440   msg = gettext (re_error_msgid[errcode]);
 5441 
 5442   msg_size = strlen (msg) + 1; /* Includes the null.  */
 5443 
 5444   if (errbuf_size != 0)
 5445     {
 5446       if (msg_size > errbuf_size)
 5447         {
 5448           strncpy (errbuf, msg, errbuf_size - 1);
 5449           errbuf[errbuf_size - 1] = 0;
 5450         }
 5451       else
 5452         strcpy (errbuf, msg);
 5453     }
 5454 
 5455   return msg_size;
 5456 }
 5457 
 5458 
 5459 /* Free dynamically allocated space used by PREG.  */
 5460 
 5461 void
 5462 regfree (preg)
 5463     regex_t *preg;
 5464 {
 5465   if (preg->buffer != NULL)
 5466     free (preg->buffer);
 5467   preg->buffer = NULL;
 5468 
 5469   preg->allocated = 0;
 5470   preg->used = 0;
 5471 
 5472   if (preg->fastmap != NULL)
 5473     free (preg->fastmap);
 5474   preg->fastmap = NULL;
 5475   preg->fastmap_accurate = 0;
 5476 
 5477   if (preg->translate != NULL)
 5478     free (preg->translate);
 5479   preg->translate = NULL;
 5480 }
 5481 
 5482 #endif /* not emacs  */
 5483 
 5484 /*
 5485 Local variables:
 5486 make-backup-files: t
 5487 version-control: t
 5488 trim-versions-without-asking: nil
 5489 End:
 5490 */