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