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