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