Declare wcs functions only if compiling with MBS_SUPPORT.
[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       consumed = mbrtowc (pdest, psrc, mb_remain, &mbs);
1288
1289       if (consumed <= 0)
1290         /* failed to convert. maybe src contains binary data.
1291            So we consume 1 byte manualy.  */
1292         {
1293           *pdest = *psrc;
1294           consumed = 1;
1295           is_binary[wc_count] = TRUE;
1296         }
1297       else
1298         is_binary[wc_count] = FALSE;
1299       /* In sjis encoding, we use yen sign as escape character in
1300          place of reverse solidus. So we convert 0x5c(yen sign in
1301          sjis) to not 0xa5(yen sign in UCS2) but 0x5c(reverse
1302          solidus in UCS2).  */
1303       if (consumed == 1 && (int) *psrc == 0x5c && (int) *pdest == 0xa5)
1304         *pdest = (wchar_t) *psrc;
1305
1306       offset_buffer[wc_count + 1] = mb_count += consumed;
1307     }
1308
1309   /* Fill remain of the buffer with sentinel.  */
1310   for (i = wc_count + 1 ; i <= len ; i++)
1311     offset_buffer[i] = mb_count + 1;
1312
1313   return wc_count;
1314 }
1315
1316 # endif /* WCHAR */
1317
1318 #else /* not INSIDE_RECURSION */
1319
1320 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
1321    also be assigned to arbitrarily: each pattern buffer stores its own
1322    syntax, so it can be changed between regex compilations.  */
1323 /* This has no initializer because initialized variables in Emacs
1324    become read-only after dumping.  */
1325 reg_syntax_t re_syntax_options;
1326
1327
1328 /* Specify the precise syntax of regexps for compilation.  This provides
1329    for compatibility for various utilities which historically have
1330    different, incompatible syntaxes.
1331
1332    The argument SYNTAX is a bit mask comprised of the various bits
1333    defined in regex.h.  We return the old syntax.  */
1334
1335 reg_syntax_t
1336 re_set_syntax (syntax)
1337     reg_syntax_t syntax;
1338 {
1339   reg_syntax_t ret = re_syntax_options;
1340
1341   re_syntax_options = syntax;
1342 # ifdef DEBUG
1343   if (syntax & RE_DEBUG)
1344     debug = 1;
1345   else if (debug) /* was on but now is not */
1346     debug = 0;
1347 # endif /* DEBUG */
1348   return ret;
1349 }
1350 # ifdef _LIBC
1351 weak_alias (__re_set_syntax, re_set_syntax)
1352 # endif
1353 \f
1354 /* This table gives an error message for each of the error codes listed
1355    in regex.h.  Obviously the order here has to be same as there.
1356    POSIX doesn't require that we do anything for REG_NOERROR,
1357    but why not be nice?  */
1358
1359 static const char re_error_msgid[] =
1360   {
1361 # define REG_NOERROR_IDX        0
1362     gettext_noop ("Success")    /* REG_NOERROR */
1363     "\0"
1364 # define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
1365     gettext_noop ("No match")   /* REG_NOMATCH */
1366     "\0"
1367 # define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
1368     gettext_noop ("Invalid regular expression") /* REG_BADPAT */
1369     "\0"
1370 # define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
1371     gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
1372     "\0"
1373 # define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
1374     gettext_noop ("Invalid character class name") /* REG_ECTYPE */
1375     "\0"
1376 # define REG_EESCAPE_IDX        (REG_ECTYPE_IDX + sizeof "Invalid character class name")
1377     gettext_noop ("Trailing backslash") /* REG_EESCAPE */
1378     "\0"
1379 # define REG_ESUBREG_IDX        (REG_EESCAPE_IDX + sizeof "Trailing backslash")
1380     gettext_noop ("Invalid back reference") /* REG_ESUBREG */
1381     "\0"
1382 # define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
1383     gettext_noop ("Unmatched [ or [^")  /* REG_EBRACK */
1384     "\0"
1385 # define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
1386     gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
1387     "\0"
1388 # define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
1389     gettext_noop ("Unmatched \\{") /* REG_EBRACE */
1390     "\0"
1391 # define REG_BADBR_IDX  (REG_EBRACE_IDX + sizeof "Unmatched \\{")
1392     gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
1393     "\0"
1394 # define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
1395     gettext_noop ("Invalid range end")  /* REG_ERANGE */
1396     "\0"
1397 # define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
1398     gettext_noop ("Memory exhausted") /* REG_ESPACE */
1399     "\0"
1400 # define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
1401     gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
1402     "\0"
1403 # define REG_EEND_IDX   (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
1404     gettext_noop ("Premature end of regular expression") /* REG_EEND */
1405     "\0"
1406 # define REG_ESIZE_IDX  (REG_EEND_IDX + sizeof "Premature end of regular expression")
1407     gettext_noop ("Regular expression too big") /* REG_ESIZE */
1408     "\0"
1409 # define REG_ERPAREN_IDX        (REG_ESIZE_IDX + sizeof "Regular expression too big")
1410     gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
1411   };
1412
1413 static const size_t re_error_msgid_idx[] =
1414   {
1415     REG_NOERROR_IDX,
1416     REG_NOMATCH_IDX,
1417     REG_BADPAT_IDX,
1418     REG_ECOLLATE_IDX,
1419     REG_ECTYPE_IDX,
1420     REG_EESCAPE_IDX,
1421     REG_ESUBREG_IDX,
1422     REG_EBRACK_IDX,
1423     REG_EPAREN_IDX,
1424     REG_EBRACE_IDX,
1425     REG_BADBR_IDX,
1426     REG_ERANGE_IDX,
1427     REG_ESPACE_IDX,
1428     REG_BADRPT_IDX,
1429     REG_EEND_IDX,
1430     REG_ESIZE_IDX,
1431     REG_ERPAREN_IDX
1432   };
1433 \f
1434 #endif /* INSIDE_RECURSION */
1435
1436 #ifndef DEFINED_ONCE
1437 /* Avoiding alloca during matching, to placate r_alloc.  */
1438
1439 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1440    searching and matching functions should not call alloca.  On some
1441    systems, alloca is implemented in terms of malloc, and if we're
1442    using the relocating allocator routines, then malloc could cause a
1443    relocation, which might (if the strings being searched are in the
1444    ralloc heap) shift the data out from underneath the regexp
1445    routines.
1446
1447    Here's another reason to avoid allocation: Emacs
1448    processes input from X in a signal handler; processing X input may
1449    call malloc; if input arrives while a matching routine is calling
1450    malloc, then we're scrod.  But Emacs can't just block input while
1451    calling matching routines; then we don't notice interrupts when
1452    they come in.  So, Emacs blocks input around all regexp calls
1453    except the matching calls, which it leaves unprotected, in the
1454    faith that they will not malloc.  */
1455
1456 /* Normally, this is fine.  */
1457 # define MATCH_MAY_ALLOCATE
1458
1459 /* When using GNU C, we are not REALLY using the C alloca, no matter
1460    what config.h may say.  So don't take precautions for it.  */
1461 # ifdef __GNUC__
1462 #  undef C_ALLOCA
1463 # endif
1464
1465 /* The match routines may not allocate if (1) they would do it with malloc
1466    and (2) it's not safe for them to use malloc.
1467    Note that if REL_ALLOC is defined, matching would not use malloc for the
1468    failure stack, but we would still use it for the register vectors;
1469    so REL_ALLOC should not affect this.  */
1470 # if (defined C_ALLOCA || defined REGEX_MALLOC) && defined emacs
1471 #  undef MATCH_MAY_ALLOCATE
1472 # endif
1473 #endif /* not DEFINED_ONCE */
1474 \f
1475 #ifdef INSIDE_RECURSION
1476 /* Failure stack declarations and macros; both re_compile_fastmap and
1477    re_match_2 use a failure stack.  These have to be macros because of
1478    REGEX_ALLOCATE_STACK.  */
1479
1480
1481 /* Number of failure points for which to initially allocate space
1482    when matching.  If this number is exceeded, we allocate more
1483    space, so it is not a hard limit.  */
1484 # ifndef INIT_FAILURE_ALLOC
1485 #  define INIT_FAILURE_ALLOC 5
1486 # endif
1487
1488 /* Roughly the maximum number of failure points on the stack.  Would be
1489    exactly that if always used MAX_FAILURE_ITEMS items each time we failed.
1490    This is a variable only so users of regex can assign to it; we never
1491    change it ourselves.  */
1492
1493 # ifdef INT_IS_16BIT
1494
1495 #  ifndef DEFINED_ONCE
1496 #   if defined MATCH_MAY_ALLOCATE
1497 /* 4400 was enough to cause a crash on Alpha OSF/1,
1498    whose default stack limit is 2mb.  */
1499 long int re_max_failures = 4000;
1500 #   else
1501 long int re_max_failures = 2000;
1502 #   endif
1503 #  endif
1504
1505 union PREFIX(fail_stack_elt)
1506 {
1507   UCHAR_T *pointer;
1508   long int integer;
1509 };
1510
1511 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1512
1513 typedef struct
1514 {
1515   PREFIX(fail_stack_elt_t) *stack;
1516   unsigned long int size;
1517   unsigned long int avail;              /* Offset of next open position.  */
1518 } PREFIX(fail_stack_type);
1519
1520 # else /* not INT_IS_16BIT */
1521
1522 #  ifndef DEFINED_ONCE
1523 #   if defined MATCH_MAY_ALLOCATE
1524 /* 4400 was enough to cause a crash on Alpha OSF/1,
1525    whose default stack limit is 2mb.  */
1526 int re_max_failures = 4000;
1527 #   else
1528 int re_max_failures = 2000;
1529 #   endif
1530 #  endif
1531
1532 union PREFIX(fail_stack_elt)
1533 {
1534   UCHAR_T *pointer;
1535   int integer;
1536 };
1537
1538 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1539
1540 typedef struct
1541 {
1542   PREFIX(fail_stack_elt_t) *stack;
1543   unsigned size;
1544   unsigned avail;                       /* Offset of next open position.  */
1545 } PREFIX(fail_stack_type);
1546
1547 # endif /* INT_IS_16BIT */
1548
1549 # ifndef DEFINED_ONCE
1550 #  define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
1551 #  define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1552 #  define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
1553 # endif
1554
1555
1556 /* Define macros to initialize and free the failure stack.
1557    Do `return -2' if the alloc fails.  */
1558
1559 # ifdef MATCH_MAY_ALLOCATE
1560 #  define INIT_FAIL_STACK()                                             \
1561   do {                                                                  \
1562     fail_stack.stack = (PREFIX(fail_stack_elt_t) *)             \
1563       REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (PREFIX(fail_stack_elt_t))); \
1564                                                                         \
1565     if (fail_stack.stack == NULL)                               \
1566       return -2;                                                        \
1567                                                                         \
1568     fail_stack.size = INIT_FAILURE_ALLOC;                       \
1569     fail_stack.avail = 0;                                       \
1570   } while (0)
1571
1572 #  define RESET_FAIL_STACK()  REGEX_FREE_STACK (fail_stack.stack)
1573 # else
1574 #  define INIT_FAIL_STACK()                                             \
1575   do {                                                                  \
1576     fail_stack.avail = 0;                                       \
1577   } while (0)
1578
1579 #  define RESET_FAIL_STACK()
1580 # endif
1581
1582
1583 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1584
1585    Return 1 if succeeds, and 0 if either ran out of memory
1586    allocating space for it or it was already too large.
1587
1588    REGEX_REALLOCATE_STACK requires `destination' be declared.   */
1589
1590 # define DOUBLE_FAIL_STACK(fail_stack)                                  \
1591   ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1592    ? 0                                                                  \
1593    : ((fail_stack).stack = (PREFIX(fail_stack_elt_t) *)                 \
1594         REGEX_REALLOCATE_STACK ((fail_stack).stack,                     \
1595           (fail_stack).size * sizeof (PREFIX(fail_stack_elt_t)),        \
1596           ((fail_stack).size << 1) * sizeof (PREFIX(fail_stack_elt_t))),\
1597                                                                         \
1598       (fail_stack).stack == NULL                                        \
1599       ? 0                                                               \
1600       : ((fail_stack).size <<= 1,                                       \
1601          1)))
1602
1603
1604 /* Push pointer POINTER on FAIL_STACK.
1605    Return 1 if was able to do so and 0 if ran out of memory allocating
1606    space to do so.  */
1607 # define PUSH_PATTERN_OP(POINTER, FAIL_STACK)                           \
1608   ((FAIL_STACK_FULL ()                                                  \
1609     && !DOUBLE_FAIL_STACK (FAIL_STACK))                                 \
1610    ? 0                                                                  \
1611    : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER,       \
1612       1))
1613
1614 /* Push a pointer value onto the failure stack.
1615    Assumes the variable `fail_stack'.  Probably should only
1616    be called from within `PUSH_FAILURE_POINT'.  */
1617 # define PUSH_FAILURE_POINTER(item)                                     \
1618   fail_stack.stack[fail_stack.avail++].pointer = (UCHAR_T *) (item)
1619
1620 /* This pushes an integer-valued item onto the failure stack.
1621    Assumes the variable `fail_stack'.  Probably should only
1622    be called from within `PUSH_FAILURE_POINT'.  */
1623 # define PUSH_FAILURE_INT(item)                                 \
1624   fail_stack.stack[fail_stack.avail++].integer = (item)
1625
1626 /* Push a fail_stack_elt_t value onto the failure stack.
1627    Assumes the variable `fail_stack'.  Probably should only
1628    be called from within `PUSH_FAILURE_POINT'.  */
1629 # define PUSH_FAILURE_ELT(item)                                 \
1630   fail_stack.stack[fail_stack.avail++] =  (item)
1631
1632 /* These three POP... operations complement the three PUSH... operations.
1633    All assume that `fail_stack' is nonempty.  */
1634 # define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1635 # define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1636 # define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1637
1638 /* Used to omit pushing failure point id's when we're not debugging.  */
1639 # ifdef DEBUG
1640 #  define DEBUG_PUSH PUSH_FAILURE_INT
1641 #  define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1642 # else
1643 #  define DEBUG_PUSH(item)
1644 #  define DEBUG_POP(item_addr)
1645 # endif
1646
1647
1648 /* Push the information about the state we will need
1649    if we ever fail back to it.
1650
1651    Requires variables fail_stack, regstart, regend, reg_info, and
1652    num_regs_pushed be declared.  DOUBLE_FAIL_STACK requires `destination'
1653    be declared.
1654
1655    Does `return FAILURE_CODE' if runs out of memory.  */
1656
1657 # define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)  \
1658   do {                                                                  \
1659     char *destination;                                                  \
1660     /* Must be int, so when we don't save any registers, the arithmetic \
1661        of 0 + -1 isn't done as unsigned.  */                            \
1662     /* Can't be int, since there is not a shred of a guarantee that int \
1663        is wide enough to hold a value of something to which pointer can \
1664        be assigned */                                                   \
1665     active_reg_t this_reg;                                              \
1666                                                                         \
1667     DEBUG_STATEMENT (failure_id++);                                     \
1668     DEBUG_STATEMENT (nfailure_points_pushed++);                         \
1669     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);           \
1670     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
1671     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
1672                                                                         \
1673     DEBUG_PRINT2 ("  slots needed: %ld\n", NUM_FAILURE_ITEMS);          \
1674     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);       \
1675                                                                         \
1676     /* Ensure we have enough space allocated for what we will push.  */ \
1677     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)                   \
1678       {                                                                 \
1679         if (!DOUBLE_FAIL_STACK (fail_stack))                            \
1680           return failure_code;                                          \
1681                                                                         \
1682         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",              \
1683                        (fail_stack).size);                              \
1684         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1685       }                                                                 \
1686                                                                         \
1687     /* Push the info, starting with the registers.  */                  \
1688     DEBUG_PRINT1 ("\n");                                                \
1689                                                                         \
1690     if (1)                                                              \
1691       for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1692            this_reg++)                                                  \
1693         {                                                               \
1694           DEBUG_PRINT2 ("  Pushing reg: %lu\n", this_reg);              \
1695           DEBUG_STATEMENT (num_regs_pushed++);                          \
1696                                                                         \
1697           DEBUG_PRINT2 ("    start: %p\n", regstart[this_reg]);         \
1698           PUSH_FAILURE_POINTER (regstart[this_reg]);                    \
1699                                                                         \
1700           DEBUG_PRINT2 ("    end: %p\n", regend[this_reg]);             \
1701           PUSH_FAILURE_POINTER (regend[this_reg]);                      \
1702                                                                         \
1703           DEBUG_PRINT2 ("    info: %p\n      ",                         \
1704                         reg_info[this_reg].word.pointer);               \
1705           DEBUG_PRINT2 (" match_null=%d",                               \
1706                         REG_MATCH_NULL_STRING_P (reg_info[this_reg]));  \
1707           DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));  \
1708           DEBUG_PRINT2 (" matched_something=%d",                        \
1709                         MATCHED_SOMETHING (reg_info[this_reg]));        \
1710           DEBUG_PRINT2 (" ever_matched=%d",                             \
1711                         EVER_MATCHED_SOMETHING (reg_info[this_reg]));   \
1712           DEBUG_PRINT1 ("\n");                                          \
1713           PUSH_FAILURE_ELT (reg_info[this_reg].word);                   \
1714         }                                                               \
1715                                                                         \
1716     DEBUG_PRINT2 ("  Pushing  low active reg: %ld\n", lowest_active_reg);\
1717     PUSH_FAILURE_INT (lowest_active_reg);                               \
1718                                                                         \
1719     DEBUG_PRINT2 ("  Pushing high active reg: %ld\n", highest_active_reg);\
1720     PUSH_FAILURE_INT (highest_active_reg);                              \
1721                                                                         \
1722     DEBUG_PRINT2 ("  Pushing pattern %p:\n", pattern_place);            \
1723     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);           \
1724     PUSH_FAILURE_POINTER (pattern_place);                               \
1725                                                                         \
1726     DEBUG_PRINT2 ("  Pushing string %p: `", string_place);              \
1727     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
1728                                  size2);                                \
1729     DEBUG_PRINT1 ("'\n");                                               \
1730     PUSH_FAILURE_POINTER (string_place);                                \
1731                                                                         \
1732     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);            \
1733     DEBUG_PUSH (failure_id);                                            \
1734   } while (0)
1735
1736 # ifndef DEFINED_ONCE
1737 /* This is the number of items that are pushed and popped on the stack
1738    for each register.  */
1739 #  define NUM_REG_ITEMS  3
1740
1741 /* Individual items aside from the registers.  */
1742 #  ifdef DEBUG
1743 #   define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
1744 #  else
1745 #   define NUM_NONREG_ITEMS 4
1746 #  endif
1747
1748 /* We push at most this many items on the stack.  */
1749 /* We used to use (num_regs - 1), which is the number of registers
1750    this regexp will save; but that was changed to 5
1751    to avoid stack overflow for a regexp with lots of parens.  */
1752 #  define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1753
1754 /* We actually push this many items.  */
1755 #  define NUM_FAILURE_ITEMS                             \
1756   (((0                                                  \
1757      ? 0 : highest_active_reg - lowest_active_reg + 1)  \
1758     * NUM_REG_ITEMS)                                    \
1759    + NUM_NONREG_ITEMS)
1760
1761 /* How many items can still be added to the stack without overflowing it.  */
1762 #  define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1763 # endif /* not DEFINED_ONCE */
1764
1765
1766 /* Pops what PUSH_FAIL_STACK pushes.
1767
1768    We restore into the parameters, all of which should be lvalues:
1769      STR -- the saved data position.
1770      PAT -- the saved pattern position.
1771      LOW_REG, HIGH_REG -- the highest and lowest active registers.
1772      REGSTART, REGEND -- arrays of string positions.
1773      REG_INFO -- array of information about each subexpression.
1774
1775    Also assumes the variables `fail_stack' and (if debugging), `bufp',
1776    `pend', `string1', `size1', `string2', and `size2'.  */
1777 # define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1778 {                                                                       \
1779   DEBUG_STATEMENT (unsigned failure_id;)                                \
1780   active_reg_t this_reg;                                                \
1781   const UCHAR_T *string_temp;                                           \
1782                                                                         \
1783   assert (!FAIL_STACK_EMPTY ());                                        \
1784                                                                         \
1785   /* Remove failure points and point to how many regs pushed.  */       \
1786   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                                \
1787   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
1788   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size);     \
1789                                                                         \
1790   assert (fail_stack.avail >= NUM_NONREG_ITEMS);                        \
1791                                                                         \
1792   DEBUG_POP (&failure_id);                                              \
1793   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);              \
1794                                                                         \
1795   /* If the saved string location is NULL, it came from an              \
1796      on_failure_keep_string_jump opcode, and we want to throw away the  \
1797      saved NULL, thus retaining our current position in the string.  */ \
1798   string_temp = POP_FAILURE_POINTER ();                                 \
1799   if (string_temp != NULL)                                              \
1800     str = (const CHAR_T *) string_temp;                                 \
1801                                                                         \
1802   DEBUG_PRINT2 ("  Popping string %p: `", str);                         \
1803   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);      \
1804   DEBUG_PRINT1 ("'\n");                                                 \
1805                                                                         \
1806   pat = (UCHAR_T *) POP_FAILURE_POINTER ();                             \
1807   DEBUG_PRINT2 ("  Popping pattern %p:\n", pat);                        \
1808   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);                       \
1809                                                                         \
1810   /* Restore register info.  */                                         \
1811   high_reg = (active_reg_t) POP_FAILURE_INT ();                         \
1812   DEBUG_PRINT2 ("  Popping high active reg: %ld\n", high_reg);          \
1813                                                                         \
1814   low_reg = (active_reg_t) POP_FAILURE_INT ();                          \
1815   DEBUG_PRINT2 ("  Popping  low active reg: %ld\n", low_reg);           \
1816                                                                         \
1817   if (1)                                                                \
1818     for (this_reg = high_reg; this_reg >= low_reg; this_reg--)          \
1819       {                                                                 \
1820         DEBUG_PRINT2 ("    Popping reg: %ld\n", this_reg);              \
1821                                                                         \
1822         reg_info[this_reg].word = POP_FAILURE_ELT ();                   \
1823         DEBUG_PRINT2 ("      info: %p\n",                               \
1824                       reg_info[this_reg].word.pointer);                 \
1825                                                                         \
1826         regend[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER ();     \
1827         DEBUG_PRINT2 ("      end: %p\n", regend[this_reg]);             \
1828                                                                         \
1829         regstart[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER ();   \
1830         DEBUG_PRINT2 ("      start: %p\n", regstart[this_reg]);         \
1831       }                                                                 \
1832   else                                                                  \
1833     {                                                                   \
1834       for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1835         {                                                               \
1836           reg_info[this_reg].word.integer = 0;                          \
1837           regend[this_reg] = 0;                                         \
1838           regstart[this_reg] = 0;                                       \
1839         }                                                               \
1840       highest_active_reg = high_reg;                                    \
1841     }                                                                   \
1842                                                                         \
1843   set_regs_matched_done = 0;                                            \
1844   DEBUG_STATEMENT (nfailure_points_popped++);                           \
1845 } /* POP_FAILURE_POINT */
1846 \f
1847 /* Structure for per-register (a.k.a. per-group) information.
1848    Other register information, such as the
1849    starting and ending positions (which are addresses), and the list of
1850    inner groups (which is a bits list) are maintained in separate
1851    variables.
1852
1853    We are making a (strictly speaking) nonportable assumption here: that
1854    the compiler will pack our bit fields into something that fits into
1855    the type of `word', i.e., is something that fits into one item on the
1856    failure stack.  */
1857
1858
1859 /* Declarations and macros for re_match_2.  */
1860
1861 typedef union
1862 {
1863   PREFIX(fail_stack_elt_t) word;
1864   struct
1865   {
1866       /* This field is one if this group can match the empty string,
1867          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
1868 # define MATCH_NULL_UNSET_VALUE 3
1869     unsigned match_null_string_p : 2;
1870     unsigned is_active : 1;
1871     unsigned matched_something : 1;
1872     unsigned ever_matched_something : 1;
1873   } bits;
1874 } PREFIX(register_info_type);
1875
1876 # ifndef DEFINED_ONCE
1877 #  define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
1878 #  define IS_ACTIVE(R)  ((R).bits.is_active)
1879 #  define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
1880 #  define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
1881
1882
1883 /* Call this when have matched a real character; it sets `matched' flags
1884    for the subexpressions which we are currently inside.  Also records
1885    that those subexprs have matched.  */
1886 #  define SET_REGS_MATCHED()                                            \
1887   do                                                                    \
1888     {                                                                   \
1889       if (!set_regs_matched_done)                                       \
1890         {                                                               \
1891           active_reg_t r;                                               \
1892           set_regs_matched_done = 1;                                    \
1893           for (r = lowest_active_reg; r <= highest_active_reg; r++)     \
1894             {                                                           \
1895               MATCHED_SOMETHING (reg_info[r])                           \
1896                 = EVER_MATCHED_SOMETHING (reg_info[r])                  \
1897                 = 1;                                                    \
1898             }                                                           \
1899         }                                                               \
1900     }                                                                   \
1901   while (0)
1902 # endif /* not DEFINED_ONCE */
1903
1904 /* Registers are set to a sentinel when they haven't yet matched.  */
1905 static CHAR_T PREFIX(reg_unset_dummy);
1906 # define REG_UNSET_VALUE (&PREFIX(reg_unset_dummy))
1907 # define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1908
1909 /* Subroutine declarations and macros for regex_compile.  */
1910 static void PREFIX(store_op1) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc, int arg));
1911 static void PREFIX(store_op2) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1912                                  int arg1, int arg2));
1913 static void PREFIX(insert_op1) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1914                                   int arg, UCHAR_T *end));
1915 static void PREFIX(insert_op2) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1916                                   int arg1, int arg2, UCHAR_T *end));
1917 static boolean PREFIX(at_begline_loc_p) _RE_ARGS ((const CHAR_T *pattern,
1918                                            const CHAR_T *p,
1919                                            reg_syntax_t syntax));
1920 static boolean PREFIX(at_endline_loc_p) _RE_ARGS ((const CHAR_T *p,
1921                                            const CHAR_T *pend,
1922                                            reg_syntax_t syntax));
1923 # ifdef WCHAR
1924 static reg_errcode_t wcs_compile_range _RE_ARGS ((CHAR_T range_start,
1925                                                   const CHAR_T **p_ptr,
1926                                                   const CHAR_T *pend,
1927                                                   char *translate,
1928                                                   reg_syntax_t syntax,
1929                                                   UCHAR_T *b,
1930                                                   CHAR_T *char_set));
1931 static void insert_space _RE_ARGS ((int num, CHAR_T *loc, CHAR_T *end));
1932 # else /* BYTE */
1933 static reg_errcode_t byte_compile_range _RE_ARGS ((unsigned int range_start,
1934                                                    const char **p_ptr,
1935                                                    const char *pend,
1936                                                    char *translate,
1937                                                    reg_syntax_t syntax,
1938                                                    unsigned char *b));
1939 # endif /* WCHAR */
1940
1941 /* Fetch the next character in the uncompiled pattern---translating it
1942    if necessary.  Also cast from a signed character in the constant
1943    string passed to us by the user to an unsigned char that we can use
1944    as an array index (in, e.g., `translate').  */
1945 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1946    because it is impossible to allocate 4GB array for some encodings
1947    which have 4 byte character_set like UCS4.  */
1948 # ifndef PATFETCH
1949 #  ifdef WCHAR
1950 #   define PATFETCH(c)                                                  \
1951   do {if (p == pend) return REG_EEND;                                   \
1952     c = (UCHAR_T) *p++;                                                 \
1953     if (translate && (c <= 0xff)) c = (UCHAR_T) translate[c];           \
1954   } while (0)
1955 #  else /* BYTE */
1956 #   define PATFETCH(c)                                                  \
1957   do {if (p == pend) return REG_EEND;                                   \
1958     c = (unsigned char) *p++;                                           \
1959     if (translate) c = (unsigned char) translate[c];                    \
1960   } while (0)
1961 #  endif /* WCHAR */
1962 # endif
1963
1964 /* Fetch the next character in the uncompiled pattern, with no
1965    translation.  */
1966 # define PATFETCH_RAW(c)                                                \
1967   do {if (p == pend) return REG_EEND;                                   \
1968     c = (UCHAR_T) *p++;                                                 \
1969   } while (0)
1970
1971 /* Go backwards one character in the pattern.  */
1972 # define PATUNFETCH p--
1973
1974
1975 /* If `translate' is non-null, return translate[D], else just D.  We
1976    cast the subscript to translate because some data is declared as
1977    `char *', to avoid warnings when a string constant is passed.  But
1978    when we use a character as a subscript we must make it unsigned.  */
1979 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1980    because it is impossible to allocate 4GB array for some encodings
1981    which have 4 byte character_set like UCS4.  */
1982
1983 # ifndef TRANSLATE
1984 #  ifdef WCHAR
1985 #   define TRANSLATE(d) \
1986   ((translate && ((UCHAR_T) (d)) <= 0xff) \
1987    ? (char) translate[(unsigned char) (d)] : (d))
1988 # else /* BYTE */
1989 #   define TRANSLATE(d) \
1990   (translate ? (char) translate[(unsigned char) (d)] : (d))
1991 #  endif /* WCHAR */
1992 # endif
1993
1994
1995 /* Macros for outputting the compiled pattern into `buffer'.  */
1996
1997 /* If the buffer isn't allocated when it comes in, use this.  */
1998 # define INIT_BUF_SIZE  (32 * sizeof(UCHAR_T))
1999
2000 /* Make sure we have at least N more bytes of space in buffer.  */
2001 # ifdef WCHAR
2002 #  define GET_BUFFER_SPACE(n)                                           \
2003     while (((unsigned long)b - (unsigned long)COMPILED_BUFFER_VAR       \
2004             + (n)*sizeof(CHAR_T)) > bufp->allocated)                    \
2005       EXTEND_BUFFER ()
2006 # else /* BYTE */
2007 #  define GET_BUFFER_SPACE(n)                                           \
2008     while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated)  \
2009       EXTEND_BUFFER ()
2010 # endif /* WCHAR */
2011
2012 /* Make sure we have one more byte of buffer space and then add C to it.  */
2013 # define BUF_PUSH(c)                                                    \
2014   do {                                                                  \
2015     GET_BUFFER_SPACE (1);                                               \
2016     *b++ = (UCHAR_T) (c);                                               \
2017   } while (0)
2018
2019
2020 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
2021 # define BUF_PUSH_2(c1, c2)                                             \
2022   do {                                                                  \
2023     GET_BUFFER_SPACE (2);                                               \
2024     *b++ = (UCHAR_T) (c1);                                              \
2025     *b++ = (UCHAR_T) (c2);                                              \
2026   } while (0)
2027
2028
2029 /* As with BUF_PUSH_2, except for three bytes.  */
2030 # define BUF_PUSH_3(c1, c2, c3)                                         \
2031   do {                                                                  \
2032     GET_BUFFER_SPACE (3);                                               \
2033     *b++ = (UCHAR_T) (c1);                                              \
2034     *b++ = (UCHAR_T) (c2);                                              \
2035     *b++ = (UCHAR_T) (c3);                                              \
2036   } while (0)
2037
2038 /* Store a jump with opcode OP at LOC to location TO.  We store a
2039    relative address offset by the three bytes the jump itself occupies.  */
2040 # define STORE_JUMP(op, loc, to) \
2041  PREFIX(store_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)))
2042
2043 /* Likewise, for a two-argument jump.  */
2044 # define STORE_JUMP2(op, loc, to, arg) \
2045   PREFIX(store_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), arg)
2046
2047 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
2048 # define INSERT_JUMP(op, loc, to) \
2049   PREFIX(insert_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), b)
2050
2051 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
2052 # define INSERT_JUMP2(op, loc, to, arg) \
2053   PREFIX(insert_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)),\
2054               arg, b)
2055
2056 /* This is not an arbitrary limit: the arguments which represent offsets
2057    into the pattern are two bytes long.  So if 2^16 bytes turns out to
2058    be too small, many things would have to change.  */
2059 /* Any other compiler which, like MSC, has allocation limit below 2^16
2060    bytes will have to use approach similar to what was done below for
2061    MSC and drop MAX_BUF_SIZE a bit.  Otherwise you may end up
2062    reallocating to 0 bytes.  Such thing is not going to work too well.
2063    You have been warned!!  */
2064 # ifndef DEFINED_ONCE
2065 #  if defined _MSC_VER  && !defined WIN32
2066 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
2067    The REALLOC define eliminates a flurry of conversion warnings,
2068    but is not required. */
2069 #   define MAX_BUF_SIZE  65500L
2070 #   define REALLOC(p,s) realloc ((p), (size_t) (s))
2071 #  else
2072 #   define MAX_BUF_SIZE (1L << 16)
2073 #   define REALLOC(p,s) realloc ((p), (s))
2074 #  endif
2075
2076 /* Extend the buffer by twice its current size via realloc and
2077    reset the pointers that pointed into the old block to point to the
2078    correct places in the new one.  If extending the buffer results in it
2079    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
2080 #  if __BOUNDED_POINTERS__
2081 #   define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
2082 #   define MOVE_BUFFER_POINTER(P) \
2083   (__ptrlow (P) += incr, SET_HIGH_BOUND (P), __ptrvalue (P) += incr)
2084 #   define ELSE_EXTEND_BUFFER_HIGH_BOUND        \
2085   else                                          \
2086     {                                           \
2087       SET_HIGH_BOUND (b);                       \
2088       SET_HIGH_BOUND (begalt);                  \
2089       if (fixup_alt_jump)                       \
2090         SET_HIGH_BOUND (fixup_alt_jump);        \
2091       if (laststart)                            \
2092         SET_HIGH_BOUND (laststart);             \
2093       if (pending_exact)                        \
2094         SET_HIGH_BOUND (pending_exact);         \
2095     }
2096 #  else
2097 #   define MOVE_BUFFER_POINTER(P) (P) += incr
2098 #   define ELSE_EXTEND_BUFFER_HIGH_BOUND
2099 #  endif
2100 # endif /* not DEFINED_ONCE */
2101
2102 # ifdef WCHAR
2103 #  define EXTEND_BUFFER()                                               \
2104   do {                                                                  \
2105     UCHAR_T *old_buffer = COMPILED_BUFFER_VAR;                          \
2106     int wchar_count;                                                    \
2107     if (bufp->allocated + sizeof(UCHAR_T) > MAX_BUF_SIZE)               \
2108       return REG_ESIZE;                                                 \
2109     bufp->allocated <<= 1;                                              \
2110     if (bufp->allocated > MAX_BUF_SIZE)                                 \
2111       bufp->allocated = MAX_BUF_SIZE;                                   \
2112     /* How many characters the new buffer can have?  */                 \
2113     wchar_count = bufp->allocated / sizeof(UCHAR_T);                    \
2114     if (wchar_count == 0) wchar_count = 1;                              \
2115     /* Truncate the buffer to CHAR_T align.  */                 \
2116     bufp->allocated = wchar_count * sizeof(UCHAR_T);                    \
2117     RETALLOC (COMPILED_BUFFER_VAR, wchar_count, UCHAR_T);               \
2118     bufp->buffer = (char*)COMPILED_BUFFER_VAR;                          \
2119     if (COMPILED_BUFFER_VAR == NULL)                                    \
2120       return REG_ESPACE;                                                \
2121     /* If the buffer moved, move all the pointers into it.  */          \
2122     if (old_buffer != COMPILED_BUFFER_VAR)                              \
2123       {                                                                 \
2124         int incr = COMPILED_BUFFER_VAR - old_buffer;                    \
2125         MOVE_BUFFER_POINTER (b);                                        \
2126         MOVE_BUFFER_POINTER (begalt);                                   \
2127         if (fixup_alt_jump)                                             \
2128           MOVE_BUFFER_POINTER (fixup_alt_jump);                         \
2129         if (laststart)                                                  \
2130           MOVE_BUFFER_POINTER (laststart);                              \
2131         if (pending_exact)                                              \
2132           MOVE_BUFFER_POINTER (pending_exact);                          \
2133       }                                                                 \
2134     ELSE_EXTEND_BUFFER_HIGH_BOUND                                       \
2135   } while (0)
2136 # else /* BYTE */
2137 #  define EXTEND_BUFFER()                                               \
2138   do {                                                                  \
2139     UCHAR_T *old_buffer = COMPILED_BUFFER_VAR;                          \
2140     if (bufp->allocated == MAX_BUF_SIZE)                                \
2141       return REG_ESIZE;                                                 \
2142     bufp->allocated <<= 1;                                              \
2143     if (bufp->allocated > MAX_BUF_SIZE)                                 \
2144       bufp->allocated = MAX_BUF_SIZE;                                   \
2145     bufp->buffer = (UCHAR_T *) REALLOC (COMPILED_BUFFER_VAR,            \
2146                                                 bufp->allocated);       \
2147     if (COMPILED_BUFFER_VAR == NULL)                                    \
2148       return REG_ESPACE;                                                \
2149     /* If the buffer moved, move all the pointers into it.  */          \
2150     if (old_buffer != COMPILED_BUFFER_VAR)                              \
2151       {                                                                 \
2152         int incr = COMPILED_BUFFER_VAR - old_buffer;                    \
2153         MOVE_BUFFER_POINTER (b);                                        \
2154         MOVE_BUFFER_POINTER (begalt);                                   \
2155         if (fixup_alt_jump)                                             \
2156           MOVE_BUFFER_POINTER (fixup_alt_jump);                         \
2157         if (laststart)                                                  \
2158           MOVE_BUFFER_POINTER (laststart);                              \
2159         if (pending_exact)                                              \
2160           MOVE_BUFFER_POINTER (pending_exact);                          \
2161       }                                                                 \
2162     ELSE_EXTEND_BUFFER_HIGH_BOUND                                       \
2163   } while (0)
2164 # endif /* WCHAR */
2165
2166 # ifndef DEFINED_ONCE
2167 /* Since we have one byte reserved for the register number argument to
2168    {start,stop}_memory, the maximum number of groups we can report
2169    things about is what fits in that byte.  */
2170 #  define MAX_REGNUM 255
2171
2172 /* But patterns can have more than `MAX_REGNUM' registers.  We just
2173    ignore the excess.  */
2174 typedef unsigned regnum_t;
2175
2176
2177 /* Macros for the compile stack.  */
2178
2179 /* Since offsets can go either forwards or backwards, this type needs to
2180    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
2181 /* int may be not enough when sizeof(int) == 2.  */
2182 typedef long pattern_offset_t;
2183
2184 typedef struct
2185 {
2186   pattern_offset_t begalt_offset;
2187   pattern_offset_t fixup_alt_jump;
2188   pattern_offset_t inner_group_offset;
2189   pattern_offset_t laststart_offset;
2190   regnum_t regnum;
2191 } compile_stack_elt_t;
2192
2193
2194 typedef struct
2195 {
2196   compile_stack_elt_t *stack;
2197   unsigned size;
2198   unsigned avail;                       /* Offset of next open position.  */
2199 } compile_stack_type;
2200
2201
2202 #  define INIT_COMPILE_STACK_SIZE 32
2203
2204 #  define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
2205 #  define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
2206
2207 /* The next available element.  */
2208 #  define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
2209
2210 # endif /* not DEFINED_ONCE */
2211
2212 /* Set the bit for character C in a list.  */
2213 # ifndef DEFINED_ONCE
2214 #  define SET_LIST_BIT(c)                               \
2215   (b[((unsigned char) (c)) / BYTEWIDTH]               \
2216    |= 1 << (((unsigned char) c) % BYTEWIDTH))
2217 # endif /* DEFINED_ONCE */
2218
2219 /* Get the next unsigned number in the uncompiled pattern.  */
2220 # define GET_UNSIGNED_NUMBER(num) \
2221   {                                                                     \
2222     while (p != pend)                                                   \
2223       {                                                                 \
2224         PATFETCH (c);                                                   \
2225         if (c < '0' || c > '9')                                         \
2226           break;                                                        \
2227         if (num <= RE_DUP_MAX)                                          \
2228           {                                                             \
2229             if (num < 0)                                                \
2230               num = 0;                                                  \
2231             num = num * 10 + c - '0';                                   \
2232           }                                                             \
2233       }                                                                 \
2234   }
2235
2236 # ifndef DEFINED_ONCE
2237 #  if defined _LIBC || WIDE_CHAR_SUPPORT
2238 /* The GNU C library provides support for user-defined character classes
2239    and the functions from ISO C amendement 1.  */
2240 #   ifdef CHARCLASS_NAME_MAX
2241 #    define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
2242 #   else
2243 /* This shouldn't happen but some implementation might still have this
2244    problem.  Use a reasonable default value.  */
2245 #    define CHAR_CLASS_MAX_LENGTH 256
2246 #   endif
2247
2248 #   ifdef _LIBC
2249 #    define IS_CHAR_CLASS(string) __wctype (string)
2250 #   else
2251 #    define IS_CHAR_CLASS(string) wctype (string)
2252 #   endif
2253 #  else
2254 #   define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
2255
2256 #   define IS_CHAR_CLASS(string)                                        \
2257    (STREQ (string, "alpha") || STREQ (string, "upper")                  \
2258     || STREQ (string, "lower") || STREQ (string, "digit")               \
2259     || STREQ (string, "alnum") || STREQ (string, "xdigit")              \
2260     || STREQ (string, "space") || STREQ (string, "print")               \
2261     || STREQ (string, "punct") || STREQ (string, "graph")               \
2262     || STREQ (string, "cntrl") || STREQ (string, "blank"))
2263 #  endif
2264 # endif /* DEFINED_ONCE */
2265 \f
2266 # ifndef MATCH_MAY_ALLOCATE
2267
2268 /* If we cannot allocate large objects within re_match_2_internal,
2269    we make the fail stack and register vectors global.
2270    The fail stack, we grow to the maximum size when a regexp
2271    is compiled.
2272    The register vectors, we adjust in size each time we
2273    compile a regexp, according to the number of registers it needs.  */
2274
2275 static PREFIX(fail_stack_type) fail_stack;
2276
2277 /* Size with which the following vectors are currently allocated.
2278    That is so we can make them bigger as needed,
2279    but never make them smaller.  */
2280 #  ifdef DEFINED_ONCE
2281 static int regs_allocated_size;
2282
2283 static const char **     regstart, **     regend;
2284 static const char ** old_regstart, ** old_regend;
2285 static const char **best_regstart, **best_regend;
2286 static const char **reg_dummy;
2287 #  endif /* DEFINED_ONCE */
2288
2289 static PREFIX(register_info_type) *PREFIX(reg_info);
2290 static PREFIX(register_info_type) *PREFIX(reg_info_dummy);
2291
2292 /* Make the register vectors big enough for NUM_REGS registers,
2293    but don't make them smaller.  */
2294
2295 static void
2296 PREFIX(regex_grow_registers) (num_regs)
2297      int num_regs;
2298 {
2299   if (num_regs > regs_allocated_size)
2300     {
2301       RETALLOC_IF (regstart,     num_regs, const char *);
2302       RETALLOC_IF (regend,       num_regs, const char *);
2303       RETALLOC_IF (old_regstart, num_regs, const char *);
2304       RETALLOC_IF (old_regend,   num_regs, const char *);
2305       RETALLOC_IF (best_regstart, num_regs, const char *);
2306       RETALLOC_IF (best_regend,  num_regs, const char *);
2307       RETALLOC_IF (PREFIX(reg_info), num_regs, PREFIX(register_info_type));
2308       RETALLOC_IF (reg_dummy,    num_regs, const char *);
2309       RETALLOC_IF (PREFIX(reg_info_dummy), num_regs, PREFIX(register_info_type));
2310
2311       regs_allocated_size = num_regs;
2312     }
2313 }
2314
2315 # endif /* not MATCH_MAY_ALLOCATE */
2316 \f
2317 # ifndef DEFINED_ONCE
2318 static boolean group_in_compile_stack _RE_ARGS ((compile_stack_type
2319                                                  compile_stack,
2320                                                  regnum_t regnum));
2321 # endif /* not DEFINED_ONCE */
2322
2323 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2324    Returns one of error codes defined in `regex.h', or zero for success.
2325
2326    Assumes the `allocated' (and perhaps `buffer') and `translate'
2327    fields are set in BUFP on entry.
2328
2329    If it succeeds, results are put in BUFP (if it returns an error, the
2330    contents of BUFP are undefined):
2331      `buffer' is the compiled pattern;
2332      `syntax' is set to SYNTAX;
2333      `used' is set to the length of the compiled pattern;
2334      `fastmap_accurate' is zero;
2335      `re_nsub' is the number of subexpressions in PATTERN;
2336      `not_bol' and `not_eol' are zero;
2337
2338    The `fastmap' and `newline_anchor' fields are neither
2339    examined nor set.  */
2340
2341 /* Return, freeing storage we allocated.  */
2342 # ifdef WCHAR
2343 #  define FREE_STACK_RETURN(value)              \
2344   return (free(pattern), free(mbs_offset), free(is_binary), free (compile_stack.stack), value)
2345 # else
2346 #  define FREE_STACK_RETURN(value)              \
2347   return (free (compile_stack.stack), value)
2348 # endif /* WCHAR */
2349
2350 static reg_errcode_t
2351 PREFIX(regex_compile) (ARG_PREFIX(pattern), ARG_PREFIX(size), syntax, bufp)
2352      const char *ARG_PREFIX(pattern);
2353      size_t ARG_PREFIX(size);
2354      reg_syntax_t syntax;
2355      struct re_pattern_buffer *bufp;
2356 {
2357   /* We fetch characters from PATTERN here.  Even though PATTERN is
2358      `char *' (i.e., signed), we declare these variables as unsigned, so
2359      they can be reliably used as array indices.  */
2360   register UCHAR_T c, c1;
2361
2362 #ifdef WCHAR
2363   /* A temporary space to keep wchar_t pattern and compiled pattern.  */
2364   CHAR_T *pattern, *COMPILED_BUFFER_VAR;
2365   size_t size;
2366   /* offset buffer for optimization. See convert_mbs_to_wc.  */
2367   int *mbs_offset = NULL;
2368   /* It hold whether each wchar_t is binary data or not.  */
2369   char *is_binary = NULL;
2370   /* A flag whether exactn is handling binary data or not.  */
2371   char is_exactn_bin = FALSE;
2372 #endif /* WCHAR */
2373
2374   /* A random temporary spot in PATTERN.  */
2375   const CHAR_T *p1;
2376
2377   /* Points to the end of the buffer, where we should append.  */
2378   register UCHAR_T *b;
2379
2380   /* Keeps track of unclosed groups.  */
2381   compile_stack_type compile_stack;
2382
2383   /* Points to the current (ending) position in the pattern.  */
2384 #ifdef WCHAR
2385   const CHAR_T *p;
2386   const CHAR_T *pend;
2387 #else /* BYTE */
2388   const CHAR_T *p = pattern;
2389   const CHAR_T *pend = pattern + size;
2390 #endif /* WCHAR */
2391
2392   /* How to translate the characters in the pattern.  */
2393   RE_TRANSLATE_TYPE translate = bufp->translate;
2394
2395   /* Address of the count-byte of the most recently inserted `exactn'
2396      command.  This makes it possible to tell if a new exact-match
2397      character can be added to that command or if the character requires
2398      a new `exactn' command.  */
2399   UCHAR_T *pending_exact = 0;
2400
2401   /* Address of start of the most recently finished expression.
2402      This tells, e.g., postfix * where to find the start of its
2403      operand.  Reset at the beginning of groups and alternatives.  */
2404   UCHAR_T *laststart = 0;
2405
2406   /* Address of beginning of regexp, or inside of last group.  */
2407   UCHAR_T *begalt;
2408
2409   /* Address of the place where a forward jump should go to the end of
2410      the containing expression.  Each alternative of an `or' -- except the
2411      last -- ends with a forward jump of this sort.  */
2412   UCHAR_T *fixup_alt_jump = 0;
2413
2414   /* Counts open-groups as they are encountered.  Remembered for the
2415      matching close-group on the compile stack, so the same register
2416      number is put in the stop_memory as the start_memory.  */
2417   regnum_t regnum = 0;
2418
2419 #ifdef WCHAR
2420   /* Initialize the wchar_t PATTERN and offset_buffer.  */
2421   p = pend = pattern = TALLOC(csize + 1, CHAR_T);
2422   mbs_offset = TALLOC(csize + 1, int);
2423   is_binary = TALLOC(csize + 1, char);
2424   if (pattern == NULL || mbs_offset == NULL || is_binary == NULL)
2425     {
2426       free(pattern);
2427       free(mbs_offset);
2428       free(is_binary);
2429       return REG_ESPACE;
2430     }
2431   pattern[csize] = L'\0';       /* sentinel */
2432   size = convert_mbs_to_wcs(pattern, cpattern, csize, mbs_offset, is_binary);
2433   pend = p + size;
2434   if (size < 0)
2435     {
2436       free(pattern);
2437       free(mbs_offset);
2438       free(is_binary);
2439       return REG_BADPAT;
2440     }
2441 #endif
2442
2443 #ifdef DEBUG
2444   DEBUG_PRINT1 ("\nCompiling pattern: ");
2445   if (debug)
2446     {
2447       unsigned debug_count;
2448
2449       for (debug_count = 0; debug_count < size; debug_count++)
2450         PUT_CHAR (pattern[debug_count]);
2451       putchar ('\n');
2452     }
2453 #endif /* DEBUG */
2454
2455   /* Initialize the compile stack.  */
2456   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
2457   if (compile_stack.stack == NULL)
2458     {
2459 #ifdef WCHAR
2460       free(pattern);
2461       free(mbs_offset);
2462       free(is_binary);
2463 #endif
2464       return REG_ESPACE;
2465     }
2466
2467   compile_stack.size = INIT_COMPILE_STACK_SIZE;
2468   compile_stack.avail = 0;
2469
2470   /* Initialize the pattern buffer.  */
2471   bufp->syntax = syntax;
2472   bufp->fastmap_accurate = 0;
2473   bufp->not_bol = bufp->not_eol = 0;
2474
2475   /* Set `used' to zero, so that if we return an error, the pattern
2476      printer (for debugging) will think there's no pattern.  We reset it
2477      at the end.  */
2478   bufp->used = 0;
2479
2480   /* Always count groups, whether or not bufp->no_sub is set.  */
2481   bufp->re_nsub = 0;
2482
2483 #if !defined emacs && !defined SYNTAX_TABLE
2484   /* Initialize the syntax table.  */
2485    init_syntax_once ();
2486 #endif
2487
2488   if (bufp->allocated == 0)
2489     {
2490       if (bufp->buffer)
2491         { /* If zero allocated, but buffer is non-null, try to realloc
2492              enough space.  This loses if buffer's address is bogus, but
2493              that is the user's responsibility.  */
2494 #ifdef WCHAR
2495           /* Free bufp->buffer and allocate an array for wchar_t pattern
2496              buffer.  */
2497           free(bufp->buffer);
2498           COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE/sizeof(UCHAR_T),
2499                                         UCHAR_T);
2500 #else
2501           RETALLOC (COMPILED_BUFFER_VAR, INIT_BUF_SIZE, UCHAR_T);
2502 #endif /* WCHAR */
2503         }
2504       else
2505         { /* Caller did not allocate a buffer.  Do it for them.  */
2506           COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE / sizeof(UCHAR_T),
2507                                         UCHAR_T);
2508         }
2509
2510       if (!COMPILED_BUFFER_VAR) FREE_STACK_RETURN (REG_ESPACE);
2511 #ifdef WCHAR
2512       bufp->buffer = (char*)COMPILED_BUFFER_VAR;
2513 #endif /* WCHAR */
2514       bufp->allocated = INIT_BUF_SIZE;
2515     }
2516 #ifdef WCHAR
2517   else
2518     COMPILED_BUFFER_VAR = (UCHAR_T*) bufp->buffer;
2519 #endif
2520
2521   begalt = b = COMPILED_BUFFER_VAR;
2522
2523   /* Loop through the uncompiled pattern until we're at the end.  */
2524   while (p != pend)
2525     {
2526       PATFETCH (c);
2527
2528       switch (c)
2529         {
2530         case '^':
2531           {
2532             if (   /* If at start of pattern, it's an operator.  */
2533                    p == pattern + 1
2534                    /* If context independent, it's an operator.  */
2535                 || syntax & RE_CONTEXT_INDEP_ANCHORS
2536                    /* Otherwise, depends on what's come before.  */
2537                 || PREFIX(at_begline_loc_p) (pattern, p, syntax))
2538               BUF_PUSH (begline);
2539             else
2540               goto normal_char;
2541           }
2542           break;
2543
2544
2545         case '$':
2546           {
2547             if (   /* If at end of pattern, it's an operator.  */
2548                    p == pend
2549                    /* If context independent, it's an operator.  */
2550                 || syntax & RE_CONTEXT_INDEP_ANCHORS
2551                    /* Otherwise, depends on what's next.  */
2552                 || PREFIX(at_endline_loc_p) (p, pend, syntax))
2553                BUF_PUSH (endline);
2554              else
2555                goto normal_char;
2556            }
2557            break;
2558
2559
2560         case '+':
2561         case '?':
2562           if ((syntax & RE_BK_PLUS_QM)
2563               || (syntax & RE_LIMITED_OPS))
2564             goto normal_char;
2565         handle_plus:
2566         case '*':
2567           /* If there is no previous pattern... */
2568           if (!laststart)
2569             {
2570               if (syntax & RE_CONTEXT_INVALID_OPS)
2571                 FREE_STACK_RETURN (REG_BADRPT);
2572               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
2573                 goto normal_char;
2574             }
2575
2576           {
2577             /* Are we optimizing this jump?  */
2578             boolean keep_string_p = false;
2579
2580             /* 1 means zero (many) matches is allowed.  */
2581             char zero_times_ok = 0, many_times_ok = 0;
2582
2583             /* If there is a sequence of repetition chars, collapse it
2584                down to just one (the right one).  We can't combine
2585                interval operators with these because of, e.g., `a{2}*',
2586                which should only match an even number of `a's.  */
2587
2588             for (;;)
2589               {
2590                 zero_times_ok |= c != '+';
2591                 many_times_ok |= c != '?';
2592
2593                 if (p == pend)
2594                   break;
2595
2596                 PATFETCH (c);
2597
2598                 if (c == '*'
2599                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
2600                   ;
2601
2602                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
2603                   {
2604                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2605
2606                     PATFETCH (c1);
2607                     if (!(c1 == '+' || c1 == '?'))
2608                       {
2609                         PATUNFETCH;
2610                         PATUNFETCH;
2611                         break;
2612                       }
2613
2614                     c = c1;
2615                   }
2616                 else
2617                   {
2618                     PATUNFETCH;
2619                     break;
2620                   }
2621
2622                 /* If we get here, we found another repeat character.  */
2623                }
2624
2625             /* Star, etc. applied to an empty pattern is equivalent
2626                to an empty pattern.  */
2627             if (!laststart)
2628               break;
2629
2630             /* Now we know whether or not zero matches is allowed
2631                and also whether or not two or more matches is allowed.  */
2632             if (many_times_ok)
2633               { /* More than one repetition is allowed, so put in at the
2634                    end a backward relative jump from `b' to before the next
2635                    jump we're going to put in below (which jumps from
2636                    laststart to after this jump).
2637
2638                    But if we are at the `*' in the exact sequence `.*\n',
2639                    insert an unconditional jump backwards to the .,
2640                    instead of the beginning of the loop.  This way we only
2641                    push a failure point once, instead of every time
2642                    through the loop.  */
2643                 assert (p - 1 > pattern);
2644
2645                 /* Allocate the space for the jump.  */
2646                 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2647
2648                 /* We know we are not at the first character of the pattern,
2649                    because laststart was nonzero.  And we've already
2650                    incremented `p', by the way, to be the character after
2651                    the `*'.  Do we have to do something analogous here
2652                    for null bytes, because of RE_DOT_NOT_NULL?  */
2653                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
2654                     && zero_times_ok
2655                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
2656                     && !(syntax & RE_DOT_NEWLINE))
2657                   { /* We have .*\n.  */
2658                     STORE_JUMP (jump, b, laststart);
2659                     keep_string_p = true;
2660                   }
2661                 else
2662                   /* Anything else.  */
2663                   STORE_JUMP (maybe_pop_jump, b, laststart -
2664                               (1 + OFFSET_ADDRESS_SIZE));
2665
2666                 /* We've added more stuff to the buffer.  */
2667                 b += 1 + OFFSET_ADDRESS_SIZE;
2668               }
2669
2670             /* On failure, jump from laststart to b + 3, which will be the
2671                end of the buffer after this jump is inserted.  */
2672             /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE' instead of
2673                'b + 3'.  */
2674             GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2675             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
2676                                        : on_failure_jump,
2677                          laststart, b + 1 + OFFSET_ADDRESS_SIZE);
2678             pending_exact = 0;
2679             b += 1 + OFFSET_ADDRESS_SIZE;
2680
2681             if (!zero_times_ok)
2682               {
2683                 /* At least one repetition is required, so insert a
2684                    `dummy_failure_jump' before the initial
2685                    `on_failure_jump' instruction of the loop. This
2686                    effects a skip over that instruction the first time
2687                    we hit that loop.  */
2688                 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2689                 INSERT_JUMP (dummy_failure_jump, laststart, laststart +
2690                              2 + 2 * OFFSET_ADDRESS_SIZE);
2691                 b += 1 + OFFSET_ADDRESS_SIZE;
2692               }
2693             }
2694           break;
2695
2696
2697         case '.':
2698           laststart = b;
2699           BUF_PUSH (anychar);
2700           break;
2701
2702
2703         case '[':
2704           {
2705             boolean had_char_class = false;
2706 #ifdef WCHAR
2707             CHAR_T range_start = 0xffffffff;
2708 #else
2709             unsigned int range_start = 0xffffffff;
2710 #endif
2711             if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2712
2713 #ifdef WCHAR
2714             /* We assume a charset(_not) structure as a wchar_t array.
2715                charset[0] = (re_opcode_t) charset(_not)
2716                charset[1] = l (= length of char_classes)
2717                charset[2] = m (= length of collating_symbols)
2718                charset[3] = n (= length of equivalence_classes)
2719                charset[4] = o (= length of char_ranges)
2720                charset[5] = p (= length of chars)
2721
2722                charset[6] = char_class (wctype_t)
2723                charset[6+CHAR_CLASS_SIZE] = char_class (wctype_t)
2724                          ...
2725                charset[l+5]  = char_class (wctype_t)
2726
2727                charset[l+6]  = collating_symbol (wchar_t)
2728                             ...
2729                charset[l+m+5]  = collating_symbol (wchar_t)
2730                                         ifdef _LIBC we use the index if
2731                                         _NL_COLLATE_SYMB_EXTRAMB instead of
2732                                         wchar_t string.
2733
2734                charset[l+m+6]  = equivalence_classes (wchar_t)
2735                               ...
2736                charset[l+m+n+5]  = equivalence_classes (wchar_t)
2737                                         ifdef _LIBC we use the index in
2738                                         _NL_COLLATE_WEIGHT instead of
2739                                         wchar_t string.
2740
2741                charset[l+m+n+6] = range_start
2742                charset[l+m+n+7] = range_end
2743                                ...
2744                charset[l+m+n+2o+4] = range_start
2745                charset[l+m+n+2o+5] = range_end
2746                                         ifdef _LIBC we use the value looked up
2747                                         in _NL_COLLATE_COLLSEQ instead of
2748                                         wchar_t character.
2749
2750                charset[l+m+n+2o+6] = char
2751                                   ...
2752                charset[l+m+n+2o+p+5] = char
2753
2754              */
2755
2756             /* We need at least 6 spaces: the opcode, the length of
2757                char_classes, the length of collating_symbols, the length of
2758                equivalence_classes, the length of char_ranges, the length of
2759                chars.  */
2760             GET_BUFFER_SPACE (6);
2761
2762             /* Save b as laststart. And We use laststart as the pointer
2763                to the first element of the charset here.
2764                In other words, laststart[i] indicates charset[i].  */
2765             laststart = b;
2766
2767             /* We test `*p == '^' twice, instead of using an if
2768                statement, so we only need one BUF_PUSH.  */
2769             BUF_PUSH (*p == '^' ? charset_not : charset);
2770             if (*p == '^')
2771               p++;
2772
2773             /* Push the length of char_classes, the length of
2774                collating_symbols, the length of equivalence_classes, the
2775                length of char_ranges and the length of chars.  */
2776             BUF_PUSH_3 (0, 0, 0);
2777             BUF_PUSH_2 (0, 0);
2778
2779             /* Remember the first position in the bracket expression.  */
2780             p1 = p;
2781
2782             /* charset_not matches newline according to a syntax bit.  */
2783             if ((re_opcode_t) b[-6] == charset_not
2784                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
2785               {
2786                 BUF_PUSH('\n');
2787                 laststart[5]++; /* Update the length of characters  */
2788               }
2789
2790             /* Read in characters and ranges, setting map bits.  */
2791             for (;;)
2792               {
2793                 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2794
2795                 PATFETCH (c);
2796
2797                 /* \ might escape characters inside [...] and [^...].  */
2798                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2799                   {
2800                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2801
2802                     PATFETCH (c1);
2803                     BUF_PUSH(c1);
2804                     laststart[5]++; /* Update the length of chars  */
2805                     range_start = c1;
2806                     continue;
2807                   }
2808
2809                 /* Could be the end of the bracket expression.  If it's
2810                    not (i.e., when the bracket expression is `[]' so
2811                    far), the ']' character bit gets set way below.  */
2812                 if (c == ']' && p != p1 + 1)
2813                   break;
2814
2815                 /* Look ahead to see if it's a range when the last thing
2816                    was a character class.  */
2817                 if (had_char_class && c == '-' && *p != ']')
2818                   FREE_STACK_RETURN (REG_ERANGE);
2819
2820                 /* Look ahead to see if it's a range when the last thing
2821                    was a character: if this is a hyphen not at the
2822                    beginning or the end of a list, then it's the range
2823                    operator.  */
2824                 if (c == '-'
2825                     && !(p - 2 >= pattern && p[-2] == '[')
2826                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2827                     && *p != ']')
2828                   {
2829                     reg_errcode_t ret;
2830                     /* Allocate the space for range_start and range_end.  */
2831                     GET_BUFFER_SPACE (2);
2832                     /* Update the pointer to indicate end of buffer.  */
2833                     b += 2;
2834                     ret = wcs_compile_range (range_start, &p, pend, translate,
2835                                          syntax, b, laststart);
2836                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2837                     range_start = 0xffffffff;
2838                   }
2839                 else if (p[0] == '-' && p[1] != ']')
2840                   { /* This handles ranges made up of characters only.  */
2841                     reg_errcode_t ret;
2842
2843                     /* Move past the `-'.  */
2844                     PATFETCH (c1);
2845                     /* Allocate the space for range_start and range_end.  */
2846                     GET_BUFFER_SPACE (2);
2847                     /* Update the pointer to indicate end of buffer.  */
2848                     b += 2;
2849                     ret = wcs_compile_range (c, &p, pend, translate, syntax, b,
2850                                          laststart);
2851                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2852                     range_start = 0xffffffff;
2853                   }
2854
2855                 /* See if we're at the beginning of a possible character
2856                    class.  */
2857                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2858                   { /* Leave room for the null.  */
2859                     char str[CHAR_CLASS_MAX_LENGTH + 1];
2860
2861                     PATFETCH (c);
2862                     c1 = 0;
2863
2864                     /* If pattern is `[[:'.  */
2865                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2866
2867                     for (;;)
2868                       {
2869                         PATFETCH (c);
2870                         if ((c == ':' && *p == ']') || p == pend)
2871                           break;
2872                         if (c1 < CHAR_CLASS_MAX_LENGTH)
2873                           str[c1++] = c;
2874                         else
2875                           /* This is in any case an invalid class name.  */
2876                           str[0] = '\0';
2877                       }
2878                     str[c1] = '\0';
2879
2880                     /* If isn't a word bracketed by `[:' and `:]':
2881                        undo the ending character, the letters, and leave
2882                        the leading `:' and `[' (but store them as character).  */
2883                     if (c == ':' && *p == ']')
2884                       {
2885                         wctype_t wt;
2886                         uintptr_t alignedp;
2887
2888                         /* Query the character class as wctype_t.  */
2889                         wt = IS_CHAR_CLASS (str);
2890                         if (wt == 0)
2891                           FREE_STACK_RETURN (REG_ECTYPE);
2892
2893                         /* Throw away the ] at the end of the character
2894                            class.  */
2895                         PATFETCH (c);
2896
2897                         if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2898
2899                         /* Allocate the space for character class.  */
2900                         GET_BUFFER_SPACE(CHAR_CLASS_SIZE);
2901                         /* Update the pointer to indicate end of buffer.  */
2902                         b += CHAR_CLASS_SIZE;
2903                         /* Move data which follow character classes
2904                             not to violate the data.  */
2905                         insert_space(CHAR_CLASS_SIZE,
2906                                      laststart + 6 + laststart[1],
2907                                      b - 1);
2908                         alignedp = ((uintptr_t)(laststart + 6 + laststart[1])
2909                                     + __alignof__(wctype_t) - 1)
2910                                     & ~(uintptr_t)(__alignof__(wctype_t) - 1);
2911                         /* Store the character class.  */
2912                         *((wctype_t*)alignedp) = wt;
2913                         /* Update length of char_classes */
2914                         laststart[1] += CHAR_CLASS_SIZE;
2915
2916                         had_char_class = true;
2917                       }
2918                     else
2919                       {
2920                         c1++;
2921                         while (c1--)
2922                           PATUNFETCH;
2923                         BUF_PUSH ('[');
2924                         BUF_PUSH (':');
2925                         laststart[5] += 2; /* Update the length of characters  */
2926                         range_start = ':';
2927                         had_char_class = false;
2928                       }
2929                   }
2930                 else if (syntax & RE_CHAR_CLASSES && c == '[' && (*p == '='
2931                                                           || *p == '.'))
2932                   {
2933                     CHAR_T str[128];    /* Should be large enough.  */
2934                     CHAR_T delim = *p; /* '=' or '.'  */
2935 # ifdef _LIBC
2936                     uint32_t nrules =
2937                       _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2938 # endif
2939                     PATFETCH (c);
2940                     c1 = 0;
2941
2942                     /* If pattern is `[[=' or '[[.'.  */
2943                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2944
2945                     for (;;)
2946                       {
2947                         PATFETCH (c);
2948                         if ((c == delim && *p == ']') || p == pend)
2949                           break;
2950                         if (c1 < sizeof (str) - 1)
2951                           str[c1++] = c;
2952                         else
2953                           /* This is in any case an invalid class name.  */
2954                           str[0] = '\0';
2955                       }
2956                     str[c1] = '\0';
2957
2958                     if (c == delim && *p == ']' && str[0] != '\0')
2959                       {
2960                         unsigned int i, offset;
2961                         /* If we have no collation data we use the default
2962                            collation in which each character is in a class
2963                            by itself.  It also means that ASCII is the
2964                            character set and therefore we cannot have character
2965                            with more than one byte in the multibyte
2966                            representation.  */
2967
2968                         /* If not defined _LIBC, we push the name and
2969                            `\0' for the sake of matching performance.  */
2970                         int datasize = c1 + 1;
2971
2972 # ifdef _LIBC
2973                         int32_t idx = 0;
2974                         if (nrules == 0)
2975 # endif
2976                           {
2977                             if (c1 != 1)
2978                               FREE_STACK_RETURN (REG_ECOLLATE);
2979                           }
2980 # ifdef _LIBC
2981                         else
2982                           {
2983                             const int32_t *table;
2984                             const int32_t *weights;
2985                             const int32_t *extra;
2986                             const int32_t *indirect;
2987                             wint_t *cp;
2988
2989                             /* This #include defines a local function!  */
2990 #  include <locale/weightwc.h>
2991
2992                             if(delim == '=')
2993                               {
2994                                 /* We push the index for equivalence class.  */
2995                                 cp = (wint_t*)str;
2996
2997                                 table = (const int32_t *)
2998                                   _NL_CURRENT (LC_COLLATE,
2999                                                _NL_COLLATE_TABLEWC);
3000                                 weights = (const int32_t *)
3001                                   _NL_CURRENT (LC_COLLATE,
3002                                                _NL_COLLATE_WEIGHTWC);
3003                                 extra = (const int32_t *)
3004                                   _NL_CURRENT (LC_COLLATE,
3005                                                _NL_COLLATE_EXTRAWC);
3006                                 indirect = (const int32_t *)
3007                                   _NL_CURRENT (LC_COLLATE,
3008                                                _NL_COLLATE_INDIRECTWC);
3009
3010                                 idx = findidx ((const wint_t**)&cp);
3011                                 if (idx == 0 || cp < (wint_t*) str + c1)
3012                                   /* This is no valid character.  */
3013                                   FREE_STACK_RETURN (REG_ECOLLATE);
3014
3015                                 str[0] = (wchar_t)idx;
3016                               }
3017                             else /* delim == '.' */
3018                               {
3019                                 /* We push collation sequence value
3020                                    for collating symbol.  */
3021                                 int32_t table_size;
3022                                 const int32_t *symb_table;
3023                                 const unsigned char *extra;
3024                                 int32_t idx;
3025                                 int32_t elem;
3026                                 int32_t second;
3027                                 int32_t hash;
3028                                 char char_str[c1];
3029
3030                                 /* We have to convert the name to a single-byte
3031                                    string.  This is possible since the names
3032                                    consist of ASCII characters and the internal
3033                                    representation is UCS4.  */
3034                                 for (i = 0; i < c1; ++i)
3035                                   char_str[i] = str[i];
3036
3037                                 table_size =
3038                                   _NL_CURRENT_WORD (LC_COLLATE,
3039                                                     _NL_COLLATE_SYMB_HASH_SIZEMB);
3040                                 symb_table = (const int32_t *)
3041                                   _NL_CURRENT (LC_COLLATE,
3042                                                _NL_COLLATE_SYMB_TABLEMB);
3043                                 extra = (const unsigned char *)
3044                                   _NL_CURRENT (LC_COLLATE,
3045                                                _NL_COLLATE_SYMB_EXTRAMB);
3046
3047                                 /* Locate the character in the hashing table.  */
3048                                 hash = elem_hash (char_str, c1);
3049
3050                                 idx = 0;
3051                                 elem = hash % table_size;
3052                                 second = hash % (table_size - 2);
3053                                 while (symb_table[2 * elem] != 0)
3054                                   {
3055                                     /* First compare the hashing value.  */
3056                                     if (symb_table[2 * elem] == hash
3057                                         && c1 == extra[symb_table[2 * elem + 1]]
3058                                         && memcmp (str,
3059                                                    &extra[symb_table[2 * elem + 1]
3060                                                          + 1], c1) == 0)
3061                                       {
3062                                         /* Yep, this is the entry.  */
3063                                         idx = symb_table[2 * elem + 1];
3064                                         idx += 1 + extra[idx];
3065                                         break;
3066                                       }
3067
3068                                     /* Next entry.  */
3069                                     elem += second;
3070                                   }
3071
3072                                 if (symb_table[2 * elem] != 0)
3073                                   {
3074                                     /* Compute the index of the byte sequence
3075                                        in the table.  */
3076                                     idx += 1 + extra[idx];
3077                                     /* Adjust for the alignment.  */
3078                                     idx = (idx + 3) & ~4;
3079
3080                                     str[0] = (wchar_t) idx + 4;
3081                                   }
3082                                 else if (symb_table[2 * elem] == 0 && c1 == 1)
3083                                   {
3084                                     /* No valid character.  Match it as a
3085                                        single byte character.  */
3086                                     had_char_class = false;
3087                                     BUF_PUSH(str[0]);
3088                                     /* Update the length of characters  */
3089                                     laststart[5]++;
3090                                     range_start = str[0];
3091
3092                                     /* Throw away the ] at the end of the
3093                                        collating symbol.  */
3094                                     PATFETCH (c);
3095                                     /* exit from the switch block.  */
3096                                     continue;
3097                                   }
3098                                 else
3099                                   FREE_STACK_RETURN (REG_ECOLLATE);
3100                               }
3101                             datasize = 1;
3102                           }
3103 # endif
3104                         /* Throw away the ] at the end of the equivalence
3105                            class (or collating symbol).  */
3106                         PATFETCH (c);
3107
3108                         /* Allocate the space for the equivalence class
3109                            (or collating symbol) (and '\0' if needed).  */
3110                         GET_BUFFER_SPACE(datasize);
3111                         /* Update the pointer to indicate end of buffer.  */
3112                         b += datasize;
3113
3114                         if (delim == '=')
3115                           { /* equivalence class  */
3116                             /* Calculate the offset of char_ranges,
3117                                which is next to equivalence_classes.  */
3118                             offset = laststart[1] + laststart[2]
3119                               + laststart[3] +6;
3120                             /* Insert space.  */
3121                             insert_space(datasize, laststart + offset, b - 1);
3122
3123                             /* Write the equivalence_class and \0.  */
3124                             for (i = 0 ; i < datasize ; i++)
3125                               laststart[offset + i] = str[i];
3126
3127                             /* Update the length of equivalence_classes.  */
3128                             laststart[3] += datasize;
3129                             had_char_class = true;
3130                           }
3131                         else /* delim == '.' */
3132                           { /* collating symbol  */
3133                             /* Calculate the offset of the equivalence_classes,
3134                                which is next to collating_symbols.  */
3135                             offset = laststart[1] + laststart[2] + 6;
3136                             /* Insert space and write the collationg_symbol
3137                                and \0.  */
3138                             insert_space(datasize, laststart + offset, b-1);
3139                             for (i = 0 ; i < datasize ; i++)
3140                               laststart[offset + i] = str[i];
3141
3142                             /* In re_match_2_internal if range_start < -1, we
3143                                assume -range_start is the offset of the
3144                                collating symbol which is specified as
3145                                the character of the range start.  So we assign
3146                                -(laststart[1] + laststart[2] + 6) to
3147                                range_start.  */
3148                             range_start = -(laststart[1] + laststart[2] + 6);
3149                             /* Update the length of collating_symbol.  */
3150                             laststart[2] += datasize;
3151                             had_char_class = false;
3152                           }
3153                       }
3154                     else
3155                       {
3156                         c1++;
3157                         while (c1--)
3158                           PATUNFETCH;
3159                         BUF_PUSH ('[');
3160                         BUF_PUSH (delim);
3161                         laststart[5] += 2; /* Update the length of characters  */
3162                         range_start = delim;
3163                         had_char_class = false;
3164                       }
3165                   }
3166                 else
3167                   {
3168                     had_char_class = false;
3169                     BUF_PUSH(c);
3170                     laststart[5]++;  /* Update the length of characters  */
3171                     range_start = c;
3172                   }
3173               }
3174
3175 #else /* BYTE */
3176             /* Ensure that we have enough space to push a charset: the
3177                opcode, the length count, and the bitset; 34 bytes in all.  */
3178             GET_BUFFER_SPACE (34);
3179
3180             laststart = b;
3181
3182             /* We test `*p == '^' twice, instead of using an if
3183                statement, so we only need one BUF_PUSH.  */
<