OSDN Git Service

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