OSDN Git Service

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