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