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