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