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