OSDN Git Service

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