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