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