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