OSDN Git Service

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