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