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