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