(re_compile_pattern): Don't set regs_allocated here.
[kopensolaris-gnu/glibc.git] / posix / regcomp.c
1 /* Extended regular expression matching and search library.
2    Copyright (C) 2002 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the License, or (at your option) any later version.
10
11    The GNU C Library is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with the GNU C Library; if not, write to the Free
18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19    02111-1307 USA.  */
20
21 #include <assert.h>
22 #include <ctype.h>
23 #include <limits.h>
24 #include <locale.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28
29 #if defined HAVE_WCHAR_H || defined _LIBC
30 # include <wchar.h>
31 #endif /* HAVE_WCHAR_H || _LIBC */
32 #if defined HAVE_WCTYPE_H || defined _LIBC
33 # include <wctype.h>
34 #endif /* HAVE_WCTYPE_H || _LIBC */
35
36 /* In case that the system doesn't have isblank().  */
37 #if !defined _LIBC && !defined HAVE_ISBLANK && !defined isblank
38 # define isblank(ch) ((ch) == ' ' || (ch) == '\t')
39 #endif
40
41 #ifdef _LIBC
42 # ifndef _RE_DEFINE_LOCALE_FUNCTIONS
43 #  define _RE_DEFINE_LOCALE_FUNCTIONS 1
44 #   include <locale/localeinfo.h>
45 #   include <locale/elem-hash.h>
46 #   include <locale/coll-lookup.h>
47 # endif
48 #endif
49
50 /* This is for other GNU distributions with internationalized messages.  */
51 #if HAVE_LIBINTL_H || defined _LIBC
52 # include <libintl.h>
53 # ifdef _LIBC
54 #  undef gettext
55 #  define gettext(msgid) \
56   INTUSE(__dcgettext) (INTUSE(_libc_intl_domainname), msgid, LC_MESSAGES)
57 # endif
58 #else
59 # define gettext(msgid) (msgid)
60 #endif
61
62 #ifndef gettext_noop
63 /* This define is so xgettext can find the internationalizable
64    strings.  */
65 # define gettext_noop(String) String
66 #endif
67
68 #include <regex.h>
69 #include "regex_internal.h"
70
71 static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
72                                           int length, reg_syntax_t syntax);
73 static void re_compile_fastmap_iter (regex_t *bufp,
74                                      const re_dfastate_t *init_state,
75                                      char *fastmap);
76 static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len);
77 static reg_errcode_t init_word_char (re_dfa_t *dfa);
78 #ifdef RE_ENABLE_I18N
79 static void free_charset (re_charset_t *cset);
80 #endif /* RE_ENABLE_I18N */
81 static void free_workarea_compile (regex_t *preg);
82 static reg_errcode_t create_initial_state (re_dfa_t *dfa);
83 static reg_errcode_t analyze (re_dfa_t *dfa);
84 static reg_errcode_t analyze_tree (re_dfa_t *dfa, bin_tree_t *node);
85 static void calc_first (re_dfa_t *dfa, bin_tree_t *node);
86 static void calc_next (re_dfa_t *dfa, bin_tree_t *node);
87 static void calc_epsdest (re_dfa_t *dfa, bin_tree_t *node);
88 static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,
89                                              int top_clone_node, int root_node,
90                                              unsigned int constraint);
91 static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,
92                                      unsigned int constraint);
93 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
94 static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
95                                          int node, int root);
96 static void calc_inveclosure (re_dfa_t *dfa);
97 static int fetch_number (re_string_t *input, re_token_t *token,
98                          reg_syntax_t syntax);
99 static re_token_t fetch_token (re_string_t *input, reg_syntax_t syntax);
100 static int peek_token (re_token_t *token, re_string_t *input,
101                         reg_syntax_t syntax);
102 static int peek_token_bracket (re_token_t *token, re_string_t *input,
103                                reg_syntax_t syntax);
104 static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
105                           reg_syntax_t syntax, reg_errcode_t *err);
106 static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,
107                                   re_token_t *token, reg_syntax_t syntax,
108                                   int nest, reg_errcode_t *err);
109 static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,
110                                  re_token_t *token, reg_syntax_t syntax,
111                                  int nest, reg_errcode_t *err);
112 static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,
113                                      re_token_t *token, reg_syntax_t syntax,
114                                      int nest, reg_errcode_t *err);
115 static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,
116                                   re_token_t *token, reg_syntax_t syntax,
117                                   int nest, reg_errcode_t *err);
118 static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,
119                                  re_dfa_t *dfa, re_token_t *token,
120                                  reg_syntax_t syntax, reg_errcode_t *err);
121 static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,
122                                       re_token_t *token, reg_syntax_t syntax,
123                                       reg_errcode_t *err);
124 static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
125                                             re_string_t *regexp,
126                                             re_token_t *token, int token_len,
127                                             re_dfa_t *dfa,
128                                             reg_syntax_t syntax);
129 static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
130                                           re_string_t *regexp,
131                                           re_token_t *token);
132 #ifndef _LIBC
133 # ifdef RE_ENABLE_I18N
134 static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
135                                       re_charset_t *mbcset, int *range_alloc,
136                                       bracket_elem_t *start_elem,
137                                       bracket_elem_t *end_elem);
138 static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
139                                              re_charset_t *mbcset,
140                                              int *coll_sym_alloc,
141                                              const unsigned char *name);
142 # else /* not RE_ENABLE_I18N */
143 static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
144                                       bracket_elem_t *start_elem,
145                                       bracket_elem_t *end_elem);
146 static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
147                                              const unsigned char *name);
148 # endif /* not RE_ENABLE_I18N */
149 #endif /* not _LIBC */
150 #ifdef RE_ENABLE_I18N
151 static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
152                                         re_charset_t *mbcset,
153                                         int *equiv_class_alloc,
154                                         const unsigned char *name);
155 static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,
156                                       re_charset_t *mbcset,
157                                       int *char_class_alloc,
158                                       const unsigned char *class_name,
159                                       reg_syntax_t syntax);
160 #else  /* not RE_ENABLE_I18N */
161 static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
162                                         const unsigned char *name);
163 static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,
164                                       const unsigned char *class_name,
165                                       reg_syntax_t syntax);
166 #endif /* not RE_ENABLE_I18N */
167 static bin_tree_t *build_word_op (re_dfa_t *dfa, int not, reg_errcode_t *err);
168 static void free_bin_tree (bin_tree_t *tree);
169 static bin_tree_t *create_tree (bin_tree_t *left, bin_tree_t *right,
170                                 re_token_type_t type, int index);
171 static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
172 \f
173 /* This table gives an error message for each of the error codes listed
174    in regex.h.  Obviously the order here has to be same as there.
175    POSIX doesn't require that we do anything for REG_NOERROR,
176    but why not be nice?  */
177
178 const char __re_error_msgid[] attribute_hidden =
179   {
180 #define REG_NOERROR_IDX 0
181     gettext_noop ("Success")    /* REG_NOERROR */
182     "\0"
183 #define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
184     gettext_noop ("No match")   /* REG_NOMATCH */
185     "\0"
186 #define REG_BADPAT_IDX  (REG_NOMATCH_IDX + sizeof "No match")
187     gettext_noop ("Invalid regular expression") /* REG_BADPAT */
188     "\0"
189 #define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
190     gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
191     "\0"
192 #define REG_ECTYPE_IDX  (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
193     gettext_noop ("Invalid character class name") /* REG_ECTYPE */
194     "\0"
195 #define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
196     gettext_noop ("Trailing backslash") /* REG_EESCAPE */
197     "\0"
198 #define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
199     gettext_noop ("Invalid back reference") /* REG_ESUBREG */
200     "\0"
201 #define REG_EBRACK_IDX  (REG_ESUBREG_IDX + sizeof "Invalid back reference")
202     gettext_noop ("Unmatched [ or [^")  /* REG_EBRACK */
203     "\0"
204 #define REG_EPAREN_IDX  (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
205     gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
206     "\0"
207 #define REG_EBRACE_IDX  (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
208     gettext_noop ("Unmatched \\{") /* REG_EBRACE */
209     "\0"
210 #define REG_BADBR_IDX   (REG_EBRACE_IDX + sizeof "Unmatched \\{")
211     gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
212     "\0"
213 #define REG_ERANGE_IDX  (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
214     gettext_noop ("Invalid range end")  /* REG_ERANGE */
215     "\0"
216 #define REG_ESPACE_IDX  (REG_ERANGE_IDX + sizeof "Invalid range end")
217     gettext_noop ("Memory exhausted") /* REG_ESPACE */
218     "\0"
219 #define REG_BADRPT_IDX  (REG_ESPACE_IDX + sizeof "Memory exhausted")
220     gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
221     "\0"
222 #define REG_EEND_IDX    (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
223     gettext_noop ("Premature end of regular expression") /* REG_EEND */
224     "\0"
225 #define REG_ESIZE_IDX   (REG_EEND_IDX + sizeof "Premature end of regular expression")
226     gettext_noop ("Regular expression too big") /* REG_ESIZE */
227     "\0"
228 #define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
229     gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
230   };
231
232 const size_t __re_error_msgid_idx[] attribute_hidden =
233   {
234     REG_NOERROR_IDX,
235     REG_NOMATCH_IDX,
236     REG_BADPAT_IDX,
237     REG_ECOLLATE_IDX,
238     REG_ECTYPE_IDX,
239     REG_EESCAPE_IDX,
240     REG_ESUBREG_IDX,
241     REG_EBRACK_IDX,
242     REG_EPAREN_IDX,
243     REG_EBRACE_IDX,
244     REG_BADBR_IDX,
245     REG_ERANGE_IDX,
246     REG_ESPACE_IDX,
247     REG_BADRPT_IDX,
248     REG_EEND_IDX,
249     REG_ESIZE_IDX,
250     REG_ERPAREN_IDX
251   };
252 \f
253 /* Entry points for GNU code.  */
254
255 /* re_compile_pattern is the GNU regular expression compiler: it
256    compiles PATTERN (of length LENGTH) and puts the result in BUFP.
257    Returns 0 if the pattern was valid, otherwise an error string.
258
259    Assumes the `allocated' (and perhaps `buffer') and `translate' fields
260    are set in BUFP on entry.  */
261
262 const char *
263 re_compile_pattern (pattern, length, bufp)
264     const char *pattern;
265     size_t length;
266     struct re_pattern_buffer *bufp;
267 {
268   reg_errcode_t ret;
269
270   /* And GNU code determines whether or not to get register information
271      by passing null for the REGS argument to re_match, etc., not by
272      setting no_sub.  */
273   bufp->no_sub = 0;
274
275   /* Match anchors at newline.  */
276   bufp->newline_anchor = 1;
277
278   ret = re_compile_internal (bufp, pattern, length, re_syntax_options);
279
280   if (!ret)
281     return NULL;
282   return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
283 }
284 #ifdef _LIBC
285 weak_alias (__re_compile_pattern, re_compile_pattern)
286 #endif
287
288 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
289    also be assigned to arbitrarily: each pattern buffer stores its own
290    syntax, so it can be changed between regex compilations.  */
291 /* This has no initializer because initialized variables in Emacs
292    become read-only after dumping.  */
293 reg_syntax_t re_syntax_options;
294
295
296 /* Specify the precise syntax of regexps for compilation.  This provides
297    for compatibility for various utilities which historically have
298    different, incompatible syntaxes.
299
300    The argument SYNTAX is a bit mask comprised of the various bits
301    defined in regex.h.  We return the old syntax.  */
302
303 reg_syntax_t
304 re_set_syntax (syntax)
305     reg_syntax_t syntax;
306 {
307   reg_syntax_t ret = re_syntax_options;
308
309   re_syntax_options = syntax;
310   return ret;
311 }
312 #ifdef _LIBC
313 weak_alias (__re_set_syntax, re_set_syntax)
314 #endif
315
316 int
317 re_compile_fastmap (bufp)
318     struct re_pattern_buffer *bufp;
319 {
320   re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
321   char *fastmap = bufp->fastmap;
322
323   memset (fastmap, '\0', sizeof (char) * SBC_MAX);
324   re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
325   if (dfa->init_state != dfa->init_state_word)
326     re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
327   if (dfa->init_state != dfa->init_state_nl)
328     re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
329   if (dfa->init_state != dfa->init_state_begbuf)
330     re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
331   bufp->fastmap_accurate = 1;
332   return 0;
333 }
334 #ifdef _LIBC
335 weak_alias (__re_compile_fastmap, re_compile_fastmap)
336 #endif
337
338 static inline void
339 re_set_fastmap (char *fastmap, int icase, int ch)
340 {
341   fastmap[ch] = 1;
342   if (icase)
343     fastmap[tolower (ch)] = 1;
344 }
345
346 /* Helper function for re_compile_fastmap.
347    Compile fastmap for the initial_state INIT_STATE.  */
348
349 static void
350 re_compile_fastmap_iter (bufp, init_state, fastmap)
351      regex_t *bufp;
352      const re_dfastate_t *init_state;
353      char *fastmap;
354 {
355   re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
356   int node_cnt;
357   int icase = (MB_CUR_MAX == 1 && (bufp->syntax & RE_ICASE));
358   for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
359     {
360       int node = init_state->nodes.elems[node_cnt];
361       re_token_type_t type = dfa->nodes[node].type;
362
363       if (type == CHARACTER)
364         re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
365       else if (type == SIMPLE_BRACKET)
366         {
367           int i, j, ch;
368           for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
369             for (j = 0; j < UINT_BITS; ++j, ++ch)
370               if (dfa->nodes[node].opr.sbcset[i] & (1 << j))
371                 re_set_fastmap (fastmap, icase, ch);
372         }
373 #ifdef RE_ENABLE_I18N
374       else if (type == COMPLEX_BRACKET)
375         {
376           int i;
377           re_charset_t *cset = dfa->nodes[node].opr.mbcset;
378           if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes
379               || cset->nranges || cset->nchar_classes)
380             {
381 # ifdef _LIBC
382               if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0)
383                 {
384                   /* In this case we want to catch the bytes which are
385                      the first byte of any collation elements.
386                      e.g. In da_DK, we want to catch 'a' since "aa"
387                           is a valid collation element, and don't catch
388                           'b' since 'b' is the only collation element
389                           which starts from 'b'.  */
390                   int j, ch;
391                   const int32_t *table = (const int32_t *)
392                     _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
393                   for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
394                     for (j = 0; j < UINT_BITS; ++j, ++ch)
395                       if (table[ch] < 0)
396                         re_set_fastmap (fastmap, icase, ch);
397                 }
398 # else
399               if (MB_CUR_MAX > 1)
400                 for (i = 0; i < SBC_MAX; ++i)
401                   if (__btowc (i) == WEOF)
402                     re_set_fastmap (fastmap, icase, i);
403 # endif /* not _LIBC */
404             }
405           for (i = 0; i < cset->nmbchars; ++i)
406             {
407               char buf[256];
408               wctomb (buf, cset->mbchars[i]);
409               re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
410             }
411         }
412 #endif /* RE_ENABLE_I18N */
413       else if (type == END_OF_RE || type == OP_PERIOD)
414         {
415           memset (fastmap, '\1', sizeof (char) * SBC_MAX);
416           if (type == END_OF_RE)
417             bufp->can_be_null = 1;
418           return;
419         }
420     }
421 }
422 \f
423 /* Entry point for POSIX code.  */
424 /* regcomp takes a regular expression as a string and compiles it.
425
426    PREG is a regex_t *.  We do not expect any fields to be initialized,
427    since POSIX says we shouldn't.  Thus, we set
428
429      `buffer' to the compiled pattern;
430      `used' to the length of the compiled pattern;
431      `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
432        REG_EXTENDED bit in CFLAGS is set; otherwise, to
433        RE_SYNTAX_POSIX_BASIC;
434      `newline_anchor' to REG_NEWLINE being set in CFLAGS;
435      `fastmap' to an allocated space for the fastmap;
436      `fastmap_accurate' to zero;
437      `re_nsub' to the number of subexpressions in PATTERN.
438
439    PATTERN is the address of the pattern string.
440
441    CFLAGS is a series of bits which affect compilation.
442
443      If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
444      use POSIX basic syntax.
445
446      If REG_NEWLINE is set, then . and [^...] don't match newline.
447      Also, regexec will try a match beginning after every newline.
448
449      If REG_ICASE is set, then we considers upper- and lowercase
450      versions of letters to be equivalent when matching.
451
452      If REG_NOSUB is set, then when PREG is passed to regexec, that
453      routine will report only success or failure, and nothing about the
454      registers.
455
456    It returns 0 if it succeeds, nonzero if it doesn't.  (See regex.h for
457    the return codes and their meanings.)  */
458
459 int
460 regcomp (preg, pattern, cflags)
461     regex_t *__restrict preg;
462     const char *__restrict pattern;
463     int cflags;
464 {
465   reg_errcode_t ret;
466   reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED
467                          : RE_SYNTAX_POSIX_BASIC);
468
469   preg->buffer = NULL;
470   preg->allocated = 0;
471   preg->used = 0;
472
473   /* Try to allocate space for the fastmap.  */
474   preg->fastmap = re_malloc (char, SBC_MAX);
475   if (BE (preg->fastmap == NULL, 0))
476     return REG_ESPACE;
477
478   syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;
479
480   /* If REG_NEWLINE is set, newlines are treated differently.  */
481   if (cflags & REG_NEWLINE)
482     { /* REG_NEWLINE implies neither . nor [^...] match newline.  */
483       syntax &= ~RE_DOT_NEWLINE;
484       syntax |= RE_HAT_LISTS_NOT_NEWLINE;
485       /* It also changes the matching behavior.  */
486       preg->newline_anchor = 1;
487     }
488   else
489     preg->newline_anchor = 0;
490   preg->no_sub = !!(cflags & REG_NOSUB);
491   preg->translate = NULL;
492
493   ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);
494
495   /* POSIX doesn't distinguish between an unmatched open-group and an
496      unmatched close-group: both are REG_EPAREN.  */
497   if (ret == REG_ERPAREN)
498     ret = REG_EPAREN;
499
500   /* We have already checked preg->fastmap != NULL.  */
501   if (BE (ret == REG_NOERROR, 1))
502     /* Compute the fastmap now, since regexec cannot modify the pattern
503        buffer.  This function nevers fails in this implementation.  */
504     (void) __re_compile_fastmap (preg);
505   else
506     {
507       /* Some error occurred while compiling the expression.  */
508       re_free (preg->fastmap);
509       preg->fastmap = NULL;
510     }
511
512   return (int) ret;
513 }
514 #ifdef _LIBC
515 weak_alias (__regcomp, regcomp)
516 #endif
517
518 /* Returns a message corresponding to an error code, ERRCODE, returned
519    from either regcomp or regexec.   We don't use PREG here.  */
520
521 size_t
522 regerror (errcode, preg, errbuf, errbuf_size)
523     int errcode;
524     const regex_t *preg;
525     char *errbuf;
526     size_t errbuf_size;
527 {
528   const char *msg;
529   size_t msg_size;
530
531   if (BE (errcode < 0
532           || errcode >= (int) (sizeof (__re_error_msgid_idx)
533                                / sizeof (__re_error_msgid_idx[0])), 0))
534     /* Only error codes returned by the rest of the code should be passed
535        to this routine.  If we are given anything else, or if other regex
536        code generates an invalid error code, then the program has a bug.
537        Dump core so we can fix it.  */
538     abort ();
539
540   msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);
541
542   msg_size = strlen (msg) + 1; /* Includes the null.  */
543
544   if (BE (errbuf_size != 0, 1))
545     {
546       if (BE (msg_size > errbuf_size, 0))
547         {
548 #if defined HAVE_MEMPCPY || defined _LIBC
549           *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
550 #else
551           memcpy (errbuf, msg, errbuf_size - 1);
552           errbuf[errbuf_size - 1] = 0;
553 #endif
554         }
555       else
556         memcpy (errbuf, msg, msg_size);
557     }
558
559   return msg_size;
560 }
561 #ifdef _LIBC
562 weak_alias (__regerror, regerror)
563 #endif
564
565
566 static void
567 free_dfa_content (re_dfa_t *dfa)
568 {
569   int i, j;
570
571   re_free (dfa->subexps);
572
573   for (i = 0; i < dfa->nodes_len; ++i)
574     {
575       re_token_t *node = dfa->nodes + i;
576 #ifdef RE_ENABLE_I18N
577       if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
578         free_charset (node->opr.mbcset);
579       else
580 #endif /* RE_ENABLE_I18N */
581         if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
582           re_free (node->opr.sbcset);
583     }
584   re_free (dfa->nexts);
585   for (i = 0; i < dfa->nodes_len; ++i)
586     {
587       if (dfa->eclosures != NULL)
588         re_node_set_free (dfa->eclosures + i);
589       if (dfa->inveclosures != NULL)
590         re_node_set_free (dfa->inveclosures + i);
591       if (dfa->edests != NULL)
592         re_node_set_free (dfa->edests + i);
593     }
594   re_free (dfa->edests);
595   re_free (dfa->eclosures);
596   re_free (dfa->inveclosures);
597   re_free (dfa->nodes);
598
599   for (i = 0; i <= dfa->state_hash_mask; ++i)
600     {
601       struct re_state_table_entry *entry = dfa->state_table + i;
602       for (j = 0; j < entry->num; ++j)
603         {
604           re_dfastate_t *state = entry->array[j];
605           free_state (state);
606         }
607       re_free (entry->array);
608     }
609   re_free (dfa->state_table);
610
611   if (dfa->word_char != NULL)
612     re_free (dfa->word_char);
613 #ifdef DEBUG
614   re_free (dfa->re_str);
615 #endif
616
617   re_free (dfa);
618 }
619
620
621 /* Free dynamically allocated space used by PREG.  */
622
623 void
624 regfree (preg)
625     regex_t *preg;
626 {
627   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
628   if (BE (dfa != NULL, 1))
629     free_dfa_content (dfa);
630
631   re_free (preg->fastmap);
632 }
633 #ifdef _LIBC
634 weak_alias (__regfree, regfree)
635 #endif
636 \f
637 /* Entry points compatible with 4.2 BSD regex library.  We don't define
638    them unless specifically requested.  */
639
640 #if defined _REGEX_RE_COMP || defined _LIBC
641
642 /* BSD has one and only one pattern buffer.  */
643 static struct re_pattern_buffer re_comp_buf;
644
645 char *
646 # ifdef _LIBC
647 /* Make these definitions weak in libc, so POSIX programs can redefine
648    these names if they don't use our functions, and still use
649    regcomp/regexec above without link errors.  */
650 weak_function
651 # endif
652 re_comp (s)
653      const char *s;
654 {
655   reg_errcode_t ret;
656   char *fastmap;
657
658   if (!s)
659     {
660       if (!re_comp_buf.buffer)
661         return gettext ("No previous regular expression");
662       return 0;
663     }
664
665   if (re_comp_buf.buffer)
666     {
667       fastmap = re_comp_buf.fastmap;
668       re_comp_buf.fastmap = NULL;
669       __regfree (&re_comp_buf);
670       memset (&re_comp_buf, '\0', sizeof (re_comp_buf));
671       re_comp_buf.fastmap = fastmap;
672     }
673
674   if (re_comp_buf.fastmap == NULL)
675     {
676       re_comp_buf.fastmap = (char *) malloc (SBC_MAX);
677       if (re_comp_buf.fastmap == NULL)
678         return (char *) gettext (__re_error_msgid
679                                  + __re_error_msgid_idx[(int) REG_ESPACE]);
680     }
681
682   /* Since `re_exec' always passes NULL for the `regs' argument, we
683      don't need to initialize the pattern buffer fields which affect it.  */
684
685   /* Match anchors at newlines.  */
686   re_comp_buf.newline_anchor = 1;
687
688   ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);
689
690   if (!ret)
691     return NULL;
692
693   /* Yes, we're discarding `const' here if !HAVE_LIBINTL.  */
694   return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
695 }
696
697 #ifdef _LIBC
698 libc_freeres_fn (free_mem)
699 {
700   __regfree (&re_comp_buf);
701 }
702 #endif
703
704 #endif /* _REGEX_RE_COMP */
705 \f
706 /* Internal entry point.
707    Compile the regular expression PATTERN, whose length is LENGTH.
708    SYNTAX indicate regular expression's syntax.  */
709
710 static reg_errcode_t
711 re_compile_internal (preg, pattern, length, syntax)
712      regex_t *preg;
713      const char * pattern;
714      int length;
715      reg_syntax_t syntax;
716 {
717   reg_errcode_t err = REG_NOERROR;
718   re_dfa_t *dfa;
719   re_string_t regexp;
720
721   /* Initialize the pattern buffer.  */
722   preg->fastmap_accurate = 0;
723   preg->syntax = syntax;
724   preg->not_bol = preg->not_eol = 0;
725   preg->used = 0;
726   preg->re_nsub = 0;
727   preg->can_be_null = 0;
728   preg->regs_allocated = REGS_UNALLOCATED;
729
730   /* Initialize the dfa.  */
731   dfa = (re_dfa_t *) preg->buffer;
732   if (preg->allocated < sizeof (re_dfa_t))
733     {
734       /* If zero allocated, but buffer is non-null, try to realloc
735          enough space.  This loses if buffer's address is bogus, but
736          that is the user's responsibility.  If ->buffer is NULL this
737          is a simple allocation.  */
738       dfa = re_realloc (preg->buffer, re_dfa_t, 1);
739       if (dfa == NULL)
740         return REG_ESPACE;
741       preg->allocated = sizeof (re_dfa_t);
742     }
743   preg->buffer = (unsigned char *) dfa;
744   preg->used = sizeof (re_dfa_t);
745
746   err = init_dfa (dfa, length);
747   if (BE (err != REG_NOERROR, 0))
748     {
749       re_free (dfa);
750       preg->buffer = NULL;
751       return err;
752     }
753 #ifdef DEBUG
754   dfa->re_str = re_malloc (char, length + 1);
755   strncpy (dfa->re_str, pattern, length + 1);
756 #endif
757
758   err = re_string_construct (&regexp, pattern, length, preg->translate,
759                              syntax & RE_ICASE);
760   if (BE (err != REG_NOERROR, 0))
761     {
762       re_free (dfa);
763       preg->buffer = NULL;
764       return err;
765     }
766
767   /* Parse the regular expression, and build a structure tree.  */
768   preg->re_nsub = 0;
769   dfa->str_tree = parse (&regexp, preg, syntax, &err);
770   if (BE (dfa->str_tree == NULL, 0))
771     goto re_compile_internal_free_return;
772
773   /* Analyze the tree and collect information which is necessary to
774      create the dfa.  */
775   err = analyze (dfa);
776   if (BE (err != REG_NOERROR, 0))
777     goto re_compile_internal_free_return;
778
779   /* Then create the initial state of the dfa.  */
780   err = create_initial_state (dfa);
781
782   /* Release work areas.  */
783   free_workarea_compile (preg);
784   re_string_destruct (&regexp);
785
786   if (BE (err != REG_NOERROR, 0))
787     {
788     re_compile_internal_free_return:
789       free_dfa_content (dfa);
790       preg->buffer = NULL;
791     }
792
793   return err;
794 }
795
796 /* Initialize DFA.  We use the length of the regular expression PAT_LEN
797    as the initial length of some arrays.  */
798
799 static reg_errcode_t
800 init_dfa (dfa, pat_len)
801      re_dfa_t *dfa;
802      int pat_len;
803 {
804   int table_size;
805
806   memset (dfa, '\0', sizeof (re_dfa_t));
807
808   dfa->nodes_alloc = pat_len + 1;
809   dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
810
811   dfa->states_alloc = pat_len + 1;
812
813   /*  table_size = 2 ^ ceil(log pat_len) */
814   for (table_size = 1; table_size > 0; table_size <<= 1)
815     if (table_size > pat_len)
816       break;
817
818   dfa->state_table = calloc (sizeof (struct re_state_table_entry), table_size);
819   dfa->state_hash_mask = table_size - 1;
820
821   dfa->subexps_alloc = 1;
822   dfa->subexps = re_malloc (re_subexp_t, dfa->subexps_alloc);
823   dfa->word_char = NULL;
824
825   if (BE (dfa->nodes == NULL || dfa->state_table == NULL
826           || dfa->subexps == NULL, 0))
827     {
828       /* We don't bother to free anything which was allocated.  Very
829          soon the process will go down anyway.  */
830       dfa->subexps = NULL;
831       dfa->state_table = NULL;
832       dfa->nodes = NULL;
833       return REG_ESPACE;
834     }
835   return REG_NOERROR;
836 }
837
838 /* Initialize WORD_CHAR table, which indicate which character is
839    "word".  In this case "word" means that it is the word construction
840    character used by some operators like "\<", "\>", etc.  */
841
842 static reg_errcode_t
843 init_word_char (dfa)
844      re_dfa_t *dfa;
845 {
846   int i, j, ch;
847   dfa->word_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1);
848   if (BE (dfa->word_char == NULL, 0))
849     return REG_ESPACE;
850   for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
851     for (j = 0; j < UINT_BITS; ++j, ++ch)
852       if (isalnum (ch) || ch == '_')
853         dfa->word_char[i] |= 1 << j;
854   return REG_NOERROR;
855 }
856
857 /* Free the work area which are only used while compiling.  */
858
859 static void
860 free_workarea_compile (preg)
861      regex_t *preg;
862 {
863   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
864   free_bin_tree (dfa->str_tree);
865   dfa->str_tree = NULL;
866 }
867
868 /* Create initial states for all contexts.  */
869
870 static reg_errcode_t
871 create_initial_state (dfa)
872      re_dfa_t *dfa;
873 {
874   int first, i;
875   reg_errcode_t err;
876   re_node_set init_nodes;
877
878   /* Initial states have the epsilon closure of the node which is
879      the first node of the regular expression.  */
880   first = dfa->str_tree->first;
881   dfa->init_node = first;
882   err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
883   if (BE (err != REG_NOERROR, 0))
884     return err;
885
886   /* The back-references which are in initial states can epsilon transit,
887      since in this case all of the subexpressions can be null.
888      Then we add epsilon closures of the nodes which are the next nodes of
889      the back-references.  */
890   if (dfa->nbackref > 0)
891     for (i = 0; i < init_nodes.nelem; ++i)
892       {
893         int node_idx = init_nodes.elems[i];
894         re_token_type_t type = dfa->nodes[node_idx].type;
895
896         int clexp_idx;
897         if (type != OP_BACK_REF)
898           continue;
899         for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
900           {
901             re_token_t *clexp_node;
902             clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];
903             if (clexp_node->type == OP_CLOSE_SUBEXP
904                 && clexp_node->opr.idx + 1 == dfa->nodes[node_idx].opr.idx)
905               break;
906           }
907         if (clexp_idx == init_nodes.nelem)
908           continue;
909
910         if (type == OP_BACK_REF)
911           {
912             int dest_idx = dfa->edests[node_idx].elems[0];
913             if (!re_node_set_contains (&init_nodes, dest_idx))
914               {
915                 re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
916                 i = 0;
917               }
918           }
919       }
920
921   /* It must be the first time to invoke acquire_state.  */
922   dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);
923   /* We don't check ERR here, since the initial state must not be NULL.  */
924   if (BE (dfa->init_state == NULL, 0))
925     return err;
926   if (dfa->init_state->has_constraint)
927     {
928       dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
929                                                        CONTEXT_WORD);
930       dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
931                                                      CONTEXT_NEWLINE);
932       dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
933                                                          &init_nodes,
934                                                          CONTEXT_NEWLINE
935                                                          | CONTEXT_BEGBUF);
936       if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL
937               || dfa->init_state_begbuf == NULL, 0))
938         return err;
939     }
940   else
941     dfa->init_state_word = dfa->init_state_nl
942       = dfa->init_state_begbuf = dfa->init_state;
943
944   re_node_set_free (&init_nodes);
945   return REG_NOERROR;
946 }
947 \f
948 /* Analyze the structure tree, and calculate "first", "next", "edest",
949    "eclosure", and "inveclosure".  */
950
951 static reg_errcode_t
952 analyze (dfa)
953      re_dfa_t *dfa;
954 {
955   int i;
956   reg_errcode_t ret;
957
958   /* Allocate arrays.  */
959   dfa->nexts = re_malloc (int, dfa->nodes_alloc);
960   dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
961   dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
962   dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc);
963   if (BE (dfa->nexts == NULL || dfa->edests == NULL
964           || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))
965     return REG_ESPACE;
966   /* Initialize them.  */
967   for (i = 0; i < dfa->nodes_len; ++i)
968     {
969       dfa->nexts[i] = -1;
970       re_node_set_init_empty (dfa->edests + i);
971       re_node_set_init_empty (dfa->eclosures + i);
972       re_node_set_init_empty (dfa->inveclosures + i);
973     }
974
975   ret = analyze_tree (dfa, dfa->str_tree);
976   if (BE (ret == REG_NOERROR, 1))
977     {
978       ret = calc_eclosure (dfa);
979       if (ret == REG_NOERROR)
980         calc_inveclosure (dfa);
981     }
982   return ret;
983 }
984
985 /* Helper functions for analyze.
986    This function calculate "first", "next", and "edest" for the subtree
987    whose root is NODE.  */
988
989 static reg_errcode_t
990 analyze_tree (dfa, node)
991      re_dfa_t *dfa;
992      bin_tree_t *node;
993 {
994   reg_errcode_t ret;
995   if (node->first == -1)
996     calc_first (dfa, node);
997   if (node->next == -1)
998     calc_next (dfa, node);
999   if (node->eclosure.nelem == 0)
1000     calc_epsdest (dfa, node);
1001   /* Calculate "first" etc. for the left child.  */
1002   if (node->left != NULL)
1003     {
1004       ret = analyze_tree (dfa, node->left);
1005       if (BE (ret != REG_NOERROR, 0))
1006         return ret;
1007     }
1008   /* Calculate "first" etc. for the right child.  */
1009   if (node->right != NULL)
1010     {
1011       ret = analyze_tree (dfa, node->right);
1012       if (BE (ret != REG_NOERROR, 0))
1013         return ret;
1014     }
1015   return REG_NOERROR;
1016 }
1017
1018 /* Calculate "first" for the node NODE.  */
1019 static void
1020 calc_first (dfa, node)
1021      re_dfa_t *dfa;
1022      bin_tree_t *node;
1023 {
1024   int idx, type;
1025   idx = node->node_idx;
1026   type = (node->type == 0) ? dfa->nodes[idx].type : node->type;
1027
1028   switch (type)
1029     {
1030 #ifdef DEBUG
1031     case OP_OPEN_BRACKET:
1032     case OP_CLOSE_BRACKET:
1033     case OP_OPEN_DUP_NUM:
1034     case OP_CLOSE_DUP_NUM:
1035     case OP_NON_MATCH_LIST:
1036     case OP_OPEN_COLL_ELEM:
1037     case OP_CLOSE_COLL_ELEM:
1038     case OP_OPEN_EQUIV_CLASS:
1039     case OP_CLOSE_EQUIV_CLASS:
1040     case OP_OPEN_CHAR_CLASS:
1041     case OP_CLOSE_CHAR_CLASS:
1042       /* These must not be appeared here.  */
1043       assert (0);
1044 #endif
1045     case END_OF_RE:
1046     case CHARACTER:
1047     case OP_PERIOD:
1048     case OP_DUP_ASTERISK:
1049     case OP_DUP_QUESTION:
1050 #ifdef RE_ENABLE_I18N
1051     case COMPLEX_BRACKET:
1052 #endif /* RE_ENABLE_I18N */
1053     case SIMPLE_BRACKET:
1054     case OP_BACK_REF:
1055     case ANCHOR:
1056     case OP_OPEN_SUBEXP:
1057     case OP_CLOSE_SUBEXP:
1058       node->first = idx;
1059       break;
1060     case OP_DUP_PLUS:
1061 #ifdef DEBUG
1062       assert (node->left != NULL);
1063 #endif
1064       if (node->left->first == -1)
1065         calc_first (dfa, node->left);
1066       node->first = node->left->first;
1067       break;
1068     case OP_ALT:
1069       node->first = idx;
1070       break;
1071       /* else fall through */
1072     default:
1073 #ifdef DEBUG
1074       assert (node->left != NULL);
1075 #endif
1076       if (node->left->first == -1)
1077         calc_first (dfa, node->left);
1078       node->first = node->left->first;
1079       break;
1080     }
1081 }
1082
1083 /* Calculate "next" for the node NODE.  */
1084
1085 static void
1086 calc_next (dfa, node)
1087      re_dfa_t *dfa;
1088      bin_tree_t *node;
1089 {
1090   int idx, type;
1091   bin_tree_t *parent = node->parent;
1092   if (parent == NULL)
1093     {
1094       node->next = -1;
1095       idx = node->node_idx;
1096       if (node->type == 0)
1097         dfa->nexts[idx] = node->next;
1098       return;
1099     }
1100
1101   idx = parent->node_idx;
1102   type = (parent->type == 0) ? dfa->nodes[idx].type : parent->type;
1103
1104   switch (type)
1105     {
1106     case OP_DUP_ASTERISK:
1107     case OP_DUP_PLUS:
1108       node->next = idx;
1109       break;
1110     case CONCAT:
1111       if (parent->left == node)
1112         {
1113           if (parent->right->first == -1)
1114             calc_first (dfa, parent->right);
1115           node->next = parent->right->first;
1116           break;
1117         }
1118       /* else fall through */
1119     default:
1120       if (parent->next == -1)
1121         calc_next (dfa, parent);
1122       node->next = parent->next;
1123       break;
1124     }
1125   idx = node->node_idx;
1126   if (node->type == 0)
1127     dfa->nexts[idx] = node->next;
1128 }
1129
1130 /* Calculate "edest" for the node NODE.  */
1131
1132 static void
1133 calc_epsdest (dfa, node)
1134      re_dfa_t *dfa;
1135      bin_tree_t *node;
1136 {
1137   int idx;
1138   idx = node->node_idx;
1139   if (node->type == 0)
1140     {
1141       if (dfa->nodes[idx].type == OP_DUP_ASTERISK
1142           || dfa->nodes[idx].type == OP_DUP_PLUS
1143           || dfa->nodes[idx].type == OP_DUP_QUESTION)
1144         {
1145           if (node->left->first == -1)
1146             calc_first (dfa, node->left);
1147           if (node->next == -1)
1148             calc_next (dfa, node);
1149           re_node_set_init_2 (dfa->edests + idx, node->left->first,
1150                               node->next);
1151         }
1152       else if (dfa->nodes[idx].type == OP_ALT)
1153         {
1154           int left, right;
1155           if (node->left != NULL)
1156             {
1157               if (node->left->first == -1)
1158                 calc_first (dfa, node->left);
1159               left = node->left->first;
1160             }
1161           else
1162             {
1163               if (node->next == -1)
1164                 calc_next (dfa, node);
1165               left = node->next;
1166             }
1167           if (node->right != NULL)
1168             {
1169               if (node->right->first == -1)
1170                 calc_first (dfa, node->right);
1171               right = node->right->first;
1172             }
1173           else
1174             {
1175               if (node->next == -1)
1176                 calc_next (dfa, node);
1177               right = node->next;
1178             }
1179           re_node_set_init_2 (dfa->edests + idx, left, right);
1180         }
1181       else if (dfa->nodes[idx].type == ANCHOR
1182                || dfa->nodes[idx].type == OP_OPEN_SUBEXP
1183                || dfa->nodes[idx].type == OP_CLOSE_SUBEXP
1184                || dfa->nodes[idx].type == OP_BACK_REF)
1185         re_node_set_init_1 (dfa->edests + idx, node->next);
1186     }
1187 }
1188
1189 /* Duplicate the epsilon closure of the node ROOT_NODE.
1190    Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
1191    to their own constraint.  */
1192
1193 static reg_errcode_t
1194 duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
1195                         init_constraint)
1196      re_dfa_t *dfa;
1197      int top_org_node, top_clone_node, root_node;
1198      unsigned int init_constraint;
1199 {
1200   reg_errcode_t err;
1201   int org_node, clone_node, ret;
1202   unsigned int constraint = init_constraint;
1203   for (org_node = top_org_node, clone_node = top_clone_node;;)
1204     {
1205       int org_dest, clone_dest;
1206       if (dfa->nodes[org_node].type == OP_BACK_REF)
1207         {
1208           /* If the back reference epsilon-transit, its destination must
1209              also have the constraint.  Then duplicate the epsilon closure
1210              of the destination of the back reference, and store it in
1211              edests of the back reference.  */
1212           org_dest = dfa->nexts[org_node];
1213           re_node_set_empty (dfa->edests + clone_node);
1214           err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1215           if (BE (err != REG_NOERROR, 0))
1216             return err;
1217           dfa->nexts[clone_node] = dfa->nexts[org_node];
1218           ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1219           if (BE (ret < 0, 0))
1220             return REG_ESPACE;
1221         }
1222       else if (dfa->edests[org_node].nelem == 0)
1223         {
1224           /* In case of the node can't epsilon-transit, don't duplicate the
1225              destination and store the original destination as the
1226              destination of the node.  */
1227           dfa->nexts[clone_node] = dfa->nexts[org_node];
1228           break;
1229         }
1230       else if (dfa->edests[org_node].nelem == 1)
1231         {
1232           /* In case of the node can epsilon-transit, and it has only one
1233              destination.  */
1234           org_dest = dfa->edests[org_node].elems[0];
1235           re_node_set_empty (dfa->edests + clone_node);
1236           if (dfa->nodes[org_node].type == ANCHOR)
1237             {
1238               /* In case of the node has another constraint, append it.  */
1239               if (org_node == root_node && clone_node != org_node)
1240                 {
1241                   /* ...but if the node is root_node itself, it means the
1242                      epsilon closure have a loop, then tie it to the
1243                      destination of the root_node.  */
1244                   ret = re_node_set_insert (dfa->edests + clone_node,
1245                                             org_dest);
1246                   if (BE (ret < 0, 0))
1247                     return REG_ESPACE;
1248                   break;
1249                 }
1250               constraint |= dfa->nodes[org_node].opr.ctx_type;
1251             }
1252           err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1253           if (BE (err != REG_NOERROR, 0))
1254             return err;
1255           ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1256           if (BE (ret < 0, 0))
1257             return REG_ESPACE;
1258         }
1259       else /* dfa->edests[org_node].nelem == 2 */
1260         {
1261           /* In case of the node can epsilon-transit, and it has two
1262              destinations.  */
1263           org_dest = dfa->edests[org_node].elems[0];
1264           re_node_set_empty (dfa->edests + clone_node);
1265           err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1266           if (BE (err != REG_NOERROR, 0))
1267             return err;
1268           ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1269           if (BE (ret < 0, 0))
1270             return REG_ESPACE;
1271
1272           err = duplicate_node_closure (dfa, org_dest, clone_dest, root_node,
1273                                         constraint);
1274           if (BE (err != REG_NOERROR, 0))
1275             return err;
1276
1277           org_dest = dfa->edests[org_node].elems[1];
1278           err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1279           if (BE (err != REG_NOERROR, 0))
1280             return err;
1281           ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1282           if (BE (ret < 0, 0))
1283             return REG_ESPACE;
1284         }
1285       org_node = org_dest;
1286       clone_node = clone_dest;
1287     }
1288   return REG_NOERROR;
1289 }
1290
1291 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1292    The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,
1293    otherwise return the error code.  */
1294
1295 static reg_errcode_t
1296 duplicate_node (new_idx, dfa, org_idx, constraint)
1297      re_dfa_t *dfa;
1298      int *new_idx, org_idx;
1299      unsigned int constraint;
1300 {
1301   re_token_t dup;
1302   int dup_idx;
1303
1304   dup = dfa->nodes[org_idx];
1305   dup_idx = re_dfa_add_node (dfa, dup, 1);
1306   if (BE (dup_idx == -1, 0))
1307     return REG_ESPACE;
1308   dfa->nodes[dup_idx].constraint = constraint;
1309   if (dfa->nodes[org_idx].type == ANCHOR)
1310     dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
1311   dfa->nodes[dup_idx].duplicated = 1;
1312   re_node_set_init_empty (dfa->edests + dup_idx);
1313   re_node_set_init_empty (dfa->eclosures + dup_idx);
1314   re_node_set_init_empty (dfa->inveclosures + dup_idx);
1315
1316   *new_idx = dup_idx;
1317   return REG_NOERROR;
1318 }
1319
1320 static void
1321 calc_inveclosure (dfa)
1322      re_dfa_t *dfa;
1323 {
1324   int src, idx, dest;
1325   for (src = 0; src < dfa->nodes_len; ++src)
1326     {
1327       for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
1328         {
1329           dest = dfa->eclosures[src].elems[idx];
1330           re_node_set_insert (dfa->inveclosures + dest, src);
1331         }
1332     }
1333 }
1334
1335 /* Calculate "eclosure" for all the node in DFA.  */
1336
1337 static reg_errcode_t
1338 calc_eclosure (dfa)
1339      re_dfa_t *dfa;
1340 {
1341   int node_idx, incomplete;
1342 #ifdef DEBUG
1343   assert (dfa->nodes_len > 0);
1344 #endif
1345   incomplete = 0;
1346   /* For each nodes, calculate epsilon closure.  */
1347   for (node_idx = 0; ; ++node_idx)
1348     {
1349       reg_errcode_t err;
1350       re_node_set eclosure_elem;
1351       if (node_idx == dfa->nodes_len)
1352         {
1353           if (!incomplete)
1354             break;
1355           incomplete = 0;
1356           node_idx = 0;
1357         }
1358
1359 #ifdef DEBUG
1360       assert (dfa->eclosures[node_idx].nelem != -1);
1361 #endif
1362       /* If we have already calculated, skip it.  */
1363       if (dfa->eclosures[node_idx].nelem != 0)
1364         continue;
1365       /* Calculate epsilon closure of `node_idx'.  */
1366       err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, 1);
1367       if (BE (err != REG_NOERROR, 0))
1368         return err;
1369
1370       if (dfa->eclosures[node_idx].nelem == 0)
1371         {
1372           incomplete = 1;
1373           re_node_set_free (&eclosure_elem);
1374         }
1375     }
1376   return REG_NOERROR;
1377 }
1378
1379 /* Calculate epsilon closure of NODE.  */
1380
1381 static reg_errcode_t
1382 calc_eclosure_iter (new_set, dfa, node, root)
1383      re_node_set *new_set;
1384      re_dfa_t *dfa;
1385      int node, root;
1386 {
1387   reg_errcode_t err;
1388   unsigned int constraint;
1389   int i, incomplete;
1390   re_node_set eclosure;
1391   incomplete = 0;
1392   err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1393   if (BE (err != REG_NOERROR, 0))
1394     return err;
1395
1396   /* This indicates that we are calculating this node now.
1397      We reference this value to avoid infinite loop.  */
1398   dfa->eclosures[node].nelem = -1;
1399
1400   constraint = ((dfa->nodes[node].type == ANCHOR)
1401                 ? dfa->nodes[node].opr.ctx_type : 0);
1402   /* If the current node has constraints, duplicate all nodes.
1403      Since they must inherit the constraints.  */
1404   if (constraint && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1405     {
1406       int org_node, cur_node;
1407       org_node = cur_node = node;
1408       err = duplicate_node_closure (dfa, node, node, node, constraint);
1409       if (BE (err != REG_NOERROR, 0))
1410         return err;
1411     }
1412
1413   /* Expand each epsilon destination nodes.  */
1414   if (IS_EPSILON_NODE(dfa->nodes[node].type))
1415     for (i = 0; i < dfa->edests[node].nelem; ++i)
1416       {
1417         re_node_set eclosure_elem;
1418         int edest = dfa->edests[node].elems[i];
1419         /* If calculating the epsilon closure of `edest' is in progress,
1420            return intermediate result.  */
1421         if (dfa->eclosures[edest].nelem == -1)
1422           {
1423             incomplete = 1;
1424             continue;
1425           }
1426         /* If we haven't calculated the epsilon closure of `edest' yet,
1427            calculate now. Otherwise use calculated epsilon closure.  */
1428         if (dfa->eclosures[edest].nelem == 0)
1429           {
1430             err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0);
1431             if (BE (err != REG_NOERROR, 0))
1432               return err;
1433           }
1434         else
1435           eclosure_elem = dfa->eclosures[edest];
1436         /* Merge the epsilon closure of `edest'.  */
1437         re_node_set_merge (&eclosure, &eclosure_elem);
1438         /* If the epsilon closure of `edest' is incomplete,
1439            the epsilon closure of this node is also incomplete.  */
1440         if (dfa->eclosures[edest].nelem == 0)
1441           {
1442             incomplete = 1;
1443             re_node_set_free (&eclosure_elem);
1444           }
1445       }
1446
1447   /* Epsilon closures include itself.  */
1448   re_node_set_insert (&eclosure, node);
1449   if (incomplete && !root)
1450     dfa->eclosures[node].nelem = 0;
1451   else
1452     dfa->eclosures[node] = eclosure;
1453   *new_set = eclosure;
1454   return REG_NOERROR;
1455 }
1456 \f
1457 /* Functions for token which are used in the parser.  */
1458
1459 /* Fetch a token from INPUT.
1460    We must not use this function inside bracket expressions.  */
1461
1462 static re_token_t
1463 fetch_token (input, syntax)
1464      re_string_t *input;
1465      reg_syntax_t syntax;
1466 {
1467   re_token_t token;
1468   int consumed_byte;
1469   consumed_byte = peek_token (&token, input, syntax);
1470   re_string_skip_bytes (input, consumed_byte);
1471   return token;
1472 }
1473
1474 /* Peek a token from INPUT, and return the length of the token.
1475    We must not use this function inside bracket expressions.  */
1476
1477 static int
1478 peek_token (token, input, syntax)
1479      re_token_t *token;
1480      re_string_t *input;
1481      reg_syntax_t syntax;
1482 {
1483   unsigned char c;
1484
1485   if (re_string_eoi (input))
1486     {
1487       token->type = END_OF_RE;
1488       return 0;
1489     }
1490
1491   c = re_string_peek_byte (input, 0);
1492   token->opr.c = c;
1493
1494 #ifdef RE_ENABLE_I18N
1495   token->mb_partial = 0;
1496   if (MB_CUR_MAX > 1 &&
1497       !re_string_first_byte (input, re_string_cur_idx (input)))
1498     {
1499       token->type = CHARACTER;
1500       token->mb_partial = 1;
1501       return 1;
1502     }
1503 #endif
1504   if (c == '\\')
1505     {
1506       unsigned char c2;
1507       if (re_string_cur_idx (input) + 1 >= re_string_length (input))
1508         {
1509           token->type = BACK_SLASH;
1510           return 1;
1511         }
1512
1513       c2 = re_string_peek_byte_case (input, 1);
1514       token->opr.c = c2;
1515       token->type = CHARACTER;
1516       switch (c2)
1517         {
1518         case '|':
1519           if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))
1520             token->type = OP_ALT;
1521           break;
1522         case '1': case '2': case '3': case '4': case '5':
1523         case '6': case '7': case '8': case '9':
1524           if (!(syntax & RE_NO_BK_REFS))
1525             {
1526               token->type = OP_BACK_REF;
1527               token->opr.idx = c2 - '0';
1528             }
1529           break;
1530         case '<':
1531           if (!(syntax & RE_NO_GNU_OPS))
1532             {
1533               token->type = ANCHOR;
1534               token->opr.idx = WORD_FIRST;
1535             }
1536           break;
1537         case '>':
1538           if (!(syntax & RE_NO_GNU_OPS))
1539             {
1540               token->type = ANCHOR;
1541               token->opr.idx = WORD_LAST;
1542             }
1543           break;
1544         case 'b':
1545           if (!(syntax & RE_NO_GNU_OPS))
1546             {
1547               token->type = ANCHOR;
1548               token->opr.idx = WORD_DELIM;
1549             }
1550           break;
1551         case 'B':
1552           if (!(syntax & RE_NO_GNU_OPS))
1553             {
1554               token->type = ANCHOR;
1555               token->opr.idx = INSIDE_WORD;
1556             }
1557           break;
1558         case 'w':
1559           if (!(syntax & RE_NO_GNU_OPS))
1560             token->type = OP_WORD;
1561           break;
1562         case 'W':
1563           if (!(syntax & RE_NO_GNU_OPS))
1564             token->type = OP_NOTWORD;
1565           break;
1566         case '`':
1567           if (!(syntax & RE_NO_GNU_OPS))
1568             {
1569               token->type = ANCHOR;
1570               token->opr.idx = BUF_FIRST;
1571             }
1572           break;
1573         case '\'':
1574           if (!(syntax & RE_NO_GNU_OPS))
1575             {
1576               token->type = ANCHOR;
1577               token->opr.idx = BUF_LAST;
1578             }
1579           break;
1580         case '(':
1581           if (!(syntax & RE_NO_BK_PARENS))
1582             token->type = OP_OPEN_SUBEXP;
1583           break;
1584         case ')':
1585           if (!(syntax & RE_NO_BK_PARENS))
1586             token->type = OP_CLOSE_SUBEXP;
1587           break;
1588         case '+':
1589           if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1590             token->type = OP_DUP_PLUS;
1591           break;
1592         case '?':
1593           if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1594             token->type = OP_DUP_QUESTION;
1595           break;
1596         case '{':
1597           if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1598             token->type = OP_OPEN_DUP_NUM;
1599           break;
1600         case '}':
1601           if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1602             token->type = OP_CLOSE_DUP_NUM;
1603           break;
1604         default:
1605           break;
1606         }
1607       return 2;
1608     }
1609
1610   token->type = CHARACTER;
1611   switch (c)
1612     {
1613     case '\n':
1614       if (syntax & RE_NEWLINE_ALT)
1615         token->type = OP_ALT;
1616       break;
1617     case '|':
1618       if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))
1619         token->type = OP_ALT;
1620       break;
1621     case '*':
1622       token->type = OP_DUP_ASTERISK;
1623       break;
1624     case '+':
1625       if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1626         token->type = OP_DUP_PLUS;
1627       break;
1628     case '?':
1629       if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1630         token->type = OP_DUP_QUESTION;
1631       break;
1632     case '{':
1633       if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1634         token->type = OP_OPEN_DUP_NUM;
1635       break;
1636     case '}':
1637       if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1638         token->type = OP_CLOSE_DUP_NUM;
1639       break;
1640     case '(':
1641       if (syntax & RE_NO_BK_PARENS)
1642         token->type = OP_OPEN_SUBEXP;
1643       break;
1644     case ')':
1645       if (syntax & RE_NO_BK_PARENS)
1646         token->type = OP_CLOSE_SUBEXP;
1647       break;
1648     case '[':
1649       token->type = OP_OPEN_BRACKET;
1650       break;
1651     case '.':
1652       token->type = OP_PERIOD;
1653       break;
1654     case '^':
1655       if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
1656           re_string_cur_idx (input) != 0)
1657         {
1658           char prev = re_string_peek_byte (input, -1);
1659           if (prev != '|' && prev != '(' &&
1660               (!(syntax & RE_NEWLINE_ALT) || prev != '\n'))
1661             break;
1662         }
1663       token->type = ANCHOR;
1664       token->opr.idx = LINE_FIRST;
1665       break;
1666     case '$':
1667       if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
1668           re_string_cur_idx (input) + 1 != re_string_length (input))
1669         {
1670           re_token_t next;
1671           re_string_skip_bytes (input, 1);
1672           peek_token (&next, input, syntax);
1673           re_string_skip_bytes (input, -1);
1674           if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
1675             break;
1676         }
1677       token->type = ANCHOR;
1678       token->opr.idx = LINE_LAST;
1679       break;
1680     default:
1681       break;
1682     }
1683   return 1;
1684 }
1685
1686 /* Peek a token from INPUT, and return the length of the token.
1687    We must not use this function out of bracket expressions.  */
1688
1689 static int
1690 peek_token_bracket (token, input, syntax)
1691      re_token_t *token;
1692      re_string_t *input;
1693      reg_syntax_t syntax;
1694 {
1695   unsigned char c;
1696   if (re_string_eoi (input))
1697     {
1698       token->type = END_OF_RE;
1699       return 0;
1700     }
1701   c = re_string_peek_byte (input, 0);
1702   token->opr.c = c;
1703
1704 #ifdef RE_ENABLE_I18N
1705   if (MB_CUR_MAX > 1 &&
1706       !re_string_first_byte (input, re_string_cur_idx (input)))
1707     {
1708       token->type = CHARACTER;
1709       return 1;
1710     }
1711 #endif /* RE_ENABLE_I18N */
1712
1713   if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS))
1714     {
1715       /* In this case, '\' escape a character.  */
1716       unsigned char c2;
1717       re_string_skip_bytes (input, 1);
1718       c2 = re_string_peek_byte (input, 0);
1719       token->opr.c = c2;
1720       token->type = CHARACTER;
1721       return 1;
1722     }
1723   if (c == '[') /* '[' is a special char in a bracket exps.  */
1724     {
1725       unsigned char c2;
1726       int token_len;
1727       c2 = re_string_peek_byte (input, 1);
1728       token->opr.c = c2;
1729       token_len = 2;
1730       switch (c2)
1731         {
1732         case '.':
1733           token->type = OP_OPEN_COLL_ELEM;
1734           break;
1735         case '=':
1736           token->type = OP_OPEN_EQUIV_CLASS;
1737           break;
1738         case ':':
1739           if (syntax & RE_CHAR_CLASSES)
1740             {
1741               token->type = OP_OPEN_CHAR_CLASS;
1742               break;
1743             }
1744           /* else fall through.  */
1745         default:
1746           token->type = CHARACTER;
1747           token->opr.c = c;
1748           token_len = 1;
1749           break;
1750         }
1751       return token_len;
1752     }
1753   switch (c)
1754     {
1755     case '-':
1756       token->type = OP_CHARSET_RANGE;
1757       break;
1758     case ']':
1759       token->type = OP_CLOSE_BRACKET;
1760       break;
1761     case '^':
1762       token->type = OP_NON_MATCH_LIST;
1763       break;
1764     default:
1765       token->type = CHARACTER;
1766     }
1767   return 1;
1768 }
1769 \f
1770 /* Functions for parser.  */
1771
1772 /* Entry point of the parser.
1773    Parse the regular expression REGEXP and return the structure tree.
1774    If an error is occured, ERR is set by error code, and return NULL.
1775    This function build the following tree, from regular expression <reg_exp>:
1776            CAT
1777            / \
1778           /   \
1779    <reg_exp>  EOR
1780
1781    CAT means concatenation.
1782    EOR means end of regular expression.  */
1783
1784 static bin_tree_t *
1785 parse (regexp, preg, syntax, err)
1786      re_string_t *regexp;
1787      regex_t *preg;
1788      reg_syntax_t syntax;
1789      reg_errcode_t *err;
1790 {
1791   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1792   bin_tree_t *tree, *eor, *root;
1793   re_token_t current_token;
1794   int new_idx;
1795   current_token = fetch_token (regexp, syntax);
1796   tree = parse_reg_exp (regexp, preg, &current_token, syntax, 0, err);
1797   if (BE (*err != REG_NOERROR && tree == NULL, 0))
1798     return NULL;
1799   new_idx = re_dfa_add_node (dfa, current_token, 0);
1800   eor = create_tree (NULL, NULL, 0, new_idx);
1801   if (tree != NULL)
1802     root = create_tree (tree, eor, CONCAT, 0);
1803   else
1804     root = eor;
1805   if (BE (new_idx == -1 || eor == NULL || root == NULL, 0))
1806     {
1807       *err = REG_ESPACE;
1808       return NULL;
1809     }
1810   return root;
1811 }
1812
1813 /* This function build the following tree, from regular expression
1814    <branch1>|<branch2>:
1815            ALT
1816            / \
1817           /   \
1818    <branch1> <branch2>
1819
1820    ALT means alternative, which represents the operator `|'.  */
1821
1822 static bin_tree_t *
1823 parse_reg_exp (regexp, preg, token, syntax, nest, err)
1824      re_string_t *regexp;
1825      regex_t *preg;
1826      re_token_t *token;
1827      reg_syntax_t syntax;
1828      int nest;
1829      reg_errcode_t *err;
1830 {
1831   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1832   bin_tree_t *tree, *branch = NULL;
1833   int new_idx;
1834   tree = parse_branch (regexp, preg, token, syntax, nest, err);
1835   if (BE (*err != REG_NOERROR && tree == NULL, 0))
1836     return NULL;
1837
1838   while (token->type == OP_ALT)
1839     {
1840       re_token_t alt_token = *token;
1841       new_idx = re_dfa_add_node (dfa, alt_token, 0);
1842       *token = fetch_token (regexp, syntax);
1843       if (token->type != OP_ALT && token->type != END_OF_RE
1844           && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
1845         {
1846           branch = parse_branch (regexp, preg, token, syntax, nest, err);
1847           if (BE (*err != REG_NOERROR && branch == NULL, 0))
1848             {
1849               free_bin_tree (tree);
1850               return NULL;
1851             }
1852         }
1853       else
1854         branch = NULL;
1855       tree = create_tree (tree, branch, 0, new_idx);
1856       if (BE (new_idx == -1 || tree == NULL, 0))
1857         {
1858           *err = REG_ESPACE;
1859           return NULL;
1860         }
1861       dfa->has_plural_match = 1;
1862     }
1863   return tree;
1864 }
1865
1866 /* This function build the following tree, from regular expression
1867    <exp1><exp2>:
1868         CAT
1869         / \
1870        /   \
1871    <exp1> <exp2>
1872
1873    CAT means concatenation.  */
1874
1875 static bin_tree_t *
1876 parse_branch (regexp, preg, token, syntax, nest, err)
1877      re_string_t *regexp;
1878      regex_t *preg;
1879      re_token_t *token;
1880      reg_syntax_t syntax;
1881      int nest;
1882      reg_errcode_t *err;
1883 {
1884   bin_tree_t *tree, *exp;
1885   tree = parse_expression (regexp, preg, token, syntax, nest, err);
1886   if (BE (*err != REG_NOERROR && tree == NULL, 0))
1887     return NULL;
1888
1889   while (token->type != OP_ALT && token->type != END_OF_RE
1890          && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
1891     {
1892       exp = parse_expression (regexp, preg, token, syntax, nest, err);
1893       if (BE (*err != REG_NOERROR && exp == NULL, 0))
1894         {
1895           free_bin_tree (tree);
1896           return NULL;
1897         }
1898       if (tree != NULL && exp != NULL)
1899         {
1900           tree = create_tree (tree, exp, CONCAT, 0);
1901           if (tree == NULL)
1902             {
1903               *err = REG_ESPACE;
1904               return NULL;
1905             }
1906         }
1907       else if (tree == NULL)
1908         tree = exp;
1909       /* Otherwise exp == NULL, we don't need to create new tree.  */
1910     }
1911   return tree;
1912 }
1913
1914 /* This function build the following tree, from regular expression a*:
1915          *
1916          |
1917          a
1918 */
1919
1920 static bin_tree_t *
1921 parse_expression (regexp, preg, token, syntax, nest, err)
1922      re_string_t *regexp;
1923      regex_t *preg;
1924      re_token_t *token;
1925      reg_syntax_t syntax;
1926      int nest;
1927      reg_errcode_t *err;
1928 {
1929   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1930   bin_tree_t *tree;
1931   int new_idx;
1932   switch (token->type)
1933     {
1934     case CHARACTER:
1935       new_idx = re_dfa_add_node (dfa, *token, 0);
1936       tree = create_tree (NULL, NULL, 0, new_idx);
1937       if (BE (new_idx == -1 || tree == NULL, 0))
1938         {
1939           *err = REG_ESPACE;
1940           return NULL;
1941         }
1942 #ifdef RE_ENABLE_I18N
1943       if (MB_CUR_MAX > 1)
1944         {
1945           while (!re_string_eoi (regexp)
1946                  && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
1947             {
1948               bin_tree_t *mbc_remain;
1949               *token = fetch_token (regexp, syntax);
1950               new_idx = re_dfa_add_node (dfa, *token, 0);
1951               mbc_remain = create_tree (NULL, NULL, 0, new_idx);
1952               tree = create_tree (tree, mbc_remain, CONCAT, 0);
1953               if (BE (new_idx == -1 || mbc_remain == NULL || tree == NULL, 0))
1954                 return *err = REG_ESPACE, NULL;
1955             }
1956         }
1957 #endif
1958       break;
1959     case OP_OPEN_SUBEXP:
1960       tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
1961       if (BE (*err != REG_NOERROR && tree == NULL, 0))
1962         return NULL;
1963       break;
1964     case OP_OPEN_BRACKET:
1965       tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
1966       if (BE (*err != REG_NOERROR && tree == NULL, 0))
1967         return NULL;
1968       break;
1969     case OP_BACK_REF:
1970       if (BE (preg->re_nsub < token->opr.idx
1971               || dfa->subexps[token->opr.idx - 1].end == -1, 0))
1972         {
1973           *err = REG_ESUBREG;
1974           return NULL;
1975         }
1976       new_idx = re_dfa_add_node (dfa, *token, 0);
1977       tree = create_tree (NULL, NULL, 0, new_idx);
1978       if (BE (new_idx == -1 || tree == NULL, 0))
1979         {
1980           *err = REG_ESPACE;
1981           return NULL;
1982         }
1983       ++dfa->nbackref;
1984       dfa->has_mb_node = 1;
1985       break;
1986     case OP_DUP_ASTERISK:
1987     case OP_DUP_PLUS:
1988     case OP_DUP_QUESTION:
1989     case OP_OPEN_DUP_NUM:
1990       if (syntax & RE_CONTEXT_INVALID_OPS)
1991         {
1992           *err = REG_BADRPT;
1993           return NULL;
1994         }
1995       else if (syntax & RE_CONTEXT_INDEP_OPS)
1996         {
1997           *token = fetch_token (regexp, syntax);
1998           return parse_expression (regexp, preg, token, syntax, nest, err);
1999         }
2000       /* else fall through  */
2001     case OP_CLOSE_SUBEXP:
2002       if ((token->type == OP_CLOSE_SUBEXP) &&
2003           !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))
2004         {
2005           *err = REG_ERPAREN;
2006           return NULL;
2007         }
2008       /* else fall through  */
2009     case OP_CLOSE_DUP_NUM:
2010       /* We treat it as a normal character.  */
2011
2012       /* Then we can these characters as normal characters.  */
2013       token->type = CHARACTER;
2014       new_idx = re_dfa_add_node (dfa, *token, 0);
2015       tree = create_tree (NULL, NULL, 0, new_idx);
2016       if (BE (new_idx == -1 || tree == NULL, 0))
2017         {
2018           *err = REG_ESPACE;
2019           return NULL;
2020         }
2021       break;
2022     case ANCHOR:
2023       if (dfa->word_char == NULL)
2024         {
2025           *err = init_word_char (dfa);
2026           if (BE (*err != REG_NOERROR, 0))
2027             return NULL;
2028         }
2029       if (token->opr.ctx_type == WORD_DELIM)
2030         {
2031           bin_tree_t *tree_first, *tree_last;
2032           int idx_first, idx_last;
2033           token->opr.ctx_type = WORD_FIRST;
2034           idx_first = re_dfa_add_node (dfa, *token, 0);
2035           tree_first = create_tree (NULL, NULL, 0, idx_first);
2036           token->opr.ctx_type = WORD_LAST;
2037           idx_last = re_dfa_add_node (dfa, *token, 0);
2038           tree_last = create_tree (NULL, NULL, 0, idx_last);
2039           token->type = OP_ALT;
2040           new_idx = re_dfa_add_node (dfa, *token, 0);
2041           tree = create_tree (tree_first, tree_last, 0, new_idx);
2042           if (BE (idx_first == -1 || idx_last == -1 || new_idx == -1
2043                   || tree_first == NULL || tree_last == NULL
2044                   || tree == NULL, 0))
2045             {
2046               *err = REG_ESPACE;
2047               return NULL;
2048             }
2049         }
2050       else
2051         {
2052           new_idx = re_dfa_add_node (dfa, *token, 0);
2053           tree = create_tree (NULL, NULL, 0, new_idx);
2054           if (BE (new_idx == -1 || tree == NULL, 0))
2055             return *err = REG_ESPACE, NULL;
2056         }
2057       /* We must return here, since ANCHORs can't be followed
2058          by repetition operators.
2059          eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
2060              it must not be "<ANCHOR(^)><REPEAT(*)>".  */
2061       *token = fetch_token (regexp, syntax);
2062       return tree;
2063     case OP_PERIOD:
2064       new_idx = re_dfa_add_node (dfa, *token, 0);
2065       tree = create_tree (NULL, NULL, 0, new_idx);
2066       if (BE (new_idx == -1 || tree == NULL, 0))
2067         {
2068           *err = REG_ESPACE;
2069           return NULL;
2070         }
2071       if (MB_CUR_MAX > 1)
2072         dfa->has_mb_node = 1;
2073       break;
2074     case OP_WORD:
2075       tree = build_word_op (dfa, 0, err);
2076       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2077         return NULL;
2078       break;
2079     case OP_NOTWORD:
2080       tree = build_word_op (dfa, 1, err);
2081       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2082         return NULL;
2083       break;
2084     case OP_ALT:
2085     case END_OF_RE:
2086       return NULL;
2087     case BACK_SLASH:
2088       *err = REG_EESCAPE;
2089       return NULL;
2090     default:
2091       /* Must not happen?  */
2092 #ifdef DEBUG
2093       assert (0);
2094 #endif
2095       return NULL;
2096     }
2097   *token = fetch_token (regexp, syntax);
2098
2099   while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
2100          || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
2101     {
2102       tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2103       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2104         return NULL;
2105       dfa->has_plural_match = 1;
2106     }
2107
2108   return tree;
2109 }
2110
2111 /* This function build the following tree, from regular expression
2112    (<reg_exp>):
2113          SUBEXP
2114             |
2115         <reg_exp>
2116 */
2117
2118 static bin_tree_t *
2119 parse_sub_exp (regexp, preg, token, syntax, nest, err)
2120      re_string_t *regexp;
2121      regex_t *preg;
2122      re_token_t *token;
2123      reg_syntax_t syntax;
2124      int nest;
2125      reg_errcode_t *err;
2126 {
2127   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2128   bin_tree_t *tree, *left_par, *right_par;
2129   size_t cur_nsub;
2130   int new_idx;
2131   cur_nsub = preg->re_nsub++;
2132   if (dfa->subexps_alloc < preg->re_nsub)
2133     {
2134       re_subexp_t *new_array;
2135       dfa->subexps_alloc *= 2;
2136       new_array = re_realloc (dfa->subexps, re_subexp_t, dfa->subexps_alloc);
2137       if (BE (new_array == NULL, 0))
2138         {
2139           dfa->subexps_alloc /= 2;
2140           *err = REG_ESPACE;
2141           return NULL;
2142         }
2143       dfa->subexps = new_array;
2144     }
2145   dfa->subexps[cur_nsub].start = dfa->nodes_len;
2146   dfa->subexps[cur_nsub].end = -1;
2147
2148   new_idx = re_dfa_add_node (dfa, *token, 0);
2149   left_par = create_tree (NULL, NULL, 0, new_idx);
2150   if (BE (new_idx == -1 || left_par == NULL, 0))
2151     {
2152       *err = REG_ESPACE;
2153       return NULL;
2154     }
2155   dfa->nodes[new_idx].opr.idx = cur_nsub;
2156   *token = fetch_token (regexp, syntax);
2157
2158   /* The subexpression may be a null string.  */
2159   if (token->type == OP_CLOSE_SUBEXP)
2160     tree = NULL;
2161   else
2162     {
2163       tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2164       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2165         return NULL;
2166     }
2167   if (BE (token->type != OP_CLOSE_SUBEXP, 0))
2168     {
2169       free_bin_tree (tree);
2170       *err = REG_BADPAT;
2171       return NULL;
2172     }
2173   new_idx = re_dfa_add_node (dfa, *token, 0);
2174   dfa->subexps[cur_nsub].end = dfa->nodes_len;
2175   right_par = create_tree (NULL, NULL, 0, new_idx);
2176   tree = ((tree == NULL) ? right_par
2177           : create_tree (tree, right_par, CONCAT, 0));
2178   tree = create_tree (left_par, tree, CONCAT, 0);
2179   if (BE (new_idx == -1 || right_par == NULL || tree == NULL, 0))
2180     {
2181       *err = REG_ESPACE;
2182       return NULL;
2183     }
2184   dfa->nodes[new_idx].opr.idx = cur_nsub;
2185
2186   return tree;
2187 }
2188
2189 /* This function parse repetition operators like "*", "+", "{1,3}" etc.  */
2190
2191 static bin_tree_t *
2192 parse_dup_op (dup_elem, regexp, dfa, token, syntax, err)
2193      bin_tree_t *dup_elem;
2194      re_string_t *regexp;
2195      re_dfa_t *dfa;
2196      re_token_t *token;
2197      reg_syntax_t syntax;
2198      reg_errcode_t *err;
2199 {
2200   re_token_t dup_token;
2201   bin_tree_t *tree = dup_elem, *work_tree;
2202   int new_idx, start_idx = re_string_cur_idx (regexp);
2203   re_token_t start_token = *token;
2204   if (token->type == OP_OPEN_DUP_NUM)
2205     {
2206       int i;
2207       int end = 0;
2208       int start = fetch_number (regexp, token, syntax);
2209       bin_tree_t *elem;
2210       if (start == -1)
2211         {
2212           if (token->type == CHARACTER && token->opr.c == ',')
2213             start = 0; /* We treat "{,m}" as "{0,m}".  */
2214           else
2215             {
2216               *err = REG_BADBR; /* <re>{} is invalid.  */
2217               return NULL;
2218             }
2219         }
2220       if (BE (start != -2, 1))
2221         {
2222           /* We treat "{n}" as "{n,n}".  */
2223           end = ((token->type == OP_CLOSE_DUP_NUM) ? start
2224                  : ((token->type == CHARACTER && token->opr.c == ',')
2225                     ? fetch_number (regexp, token, syntax) : -2));
2226         }
2227       if (BE (start == -2 || end == -2, 0))
2228         {
2229           /* Invalid sequence.  */
2230           if (token->type == OP_CLOSE_DUP_NUM)
2231             goto parse_dup_op_invalid_interval;
2232           else
2233             goto parse_dup_op_ebrace;
2234         }
2235       if (BE (start == 0 && end == 0, 0))
2236         {
2237           /* We treat "<re>{0}" and "<re>{0,0}" as null string.  */
2238           *token = fetch_token (regexp, syntax);
2239           free_bin_tree (dup_elem);
2240           return NULL;
2241         }
2242
2243       /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}".  */
2244       elem = tree;
2245       for (i = 0; i < start; ++i)
2246         if (i != 0)
2247           {
2248             work_tree = duplicate_tree (elem, dfa);
2249             tree = create_tree (tree, work_tree, CONCAT, 0);
2250             if (BE (work_tree == NULL || tree == NULL, 0))
2251               goto parse_dup_op_espace;
2252           }
2253
2254       if (end == -1)
2255         {
2256           /* We treat "<re>{0,}" as "<re>*".  */
2257           dup_token.type = OP_DUP_ASTERISK;
2258           if (start > 0)
2259             {
2260               elem = duplicate_tree (elem, dfa);
2261               new_idx = re_dfa_add_node (dfa, dup_token, 0);
2262               work_tree = create_tree (elem, NULL, 0, new_idx);
2263               tree = create_tree (tree, work_tree, CONCAT, 0);
2264               if (BE (elem == NULL || new_idx == -1 || work_tree == NULL
2265                       || tree == NULL, 0))
2266                 goto parse_dup_op_espace;
2267             }
2268           else
2269             {
2270               new_idx = re_dfa_add_node (dfa, dup_token, 0);
2271               tree = create_tree (elem, NULL, 0, new_idx);
2272               if (BE (new_idx == -1 || tree == NULL, 0))
2273                 goto parse_dup_op_espace;
2274             }
2275         }
2276       else if (end - start > 0)
2277         {
2278           /* Then extract "<re>{0,m}" to "<re>?<re>?...<re>?".  */
2279           dup_token.type = OP_DUP_QUESTION;
2280           if (start > 0)
2281             {
2282               elem = duplicate_tree (elem, dfa);
2283               new_idx = re_dfa_add_node (dfa, dup_token, 0);
2284               elem = create_tree (elem, NULL, 0, new_idx);
2285               tree = create_tree (tree, elem, CONCAT, 0);
2286               if (BE (elem == NULL || new_idx == -1 || tree == NULL, 0))
2287                 goto parse_dup_op_espace;
2288             }
2289           else
2290             {
2291               new_idx = re_dfa_add_node (dfa, dup_token, 0);
2292               tree = elem = create_tree (elem, NULL, 0, new_idx);
2293               if (BE (new_idx == -1 || tree == NULL, 0))
2294                 goto parse_dup_op_espace;
2295             }
2296           for (i = 1; i < end - start; ++i)
2297             {
2298               work_tree = duplicate_tree (elem, dfa);
2299               tree = create_tree (tree, work_tree, CONCAT, 0);
2300               if (BE (work_tree == NULL || tree == NULL, 0))
2301                 {
2302                   *err = REG_ESPACE;
2303                   return NULL;
2304                 }
2305             }
2306         }
2307     }
2308   else
2309     {
2310       new_idx = re_dfa_add_node (dfa, *token, 0);
2311       tree = create_tree (tree, NULL, 0, new_idx);
2312       if (BE (new_idx == -1 || tree == NULL, 0))
2313         {
2314           *err = REG_ESPACE;
2315           return NULL;
2316         }
2317     }
2318   *token = fetch_token (regexp, syntax);
2319   return tree;
2320
2321  parse_dup_op_espace:
2322   free_bin_tree (tree);
2323   *err = REG_ESPACE;
2324   return NULL;
2325
2326  parse_dup_op_ebrace:
2327   if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
2328     {
2329       *err = REG_EBRACE;
2330       return NULL;
2331     }
2332   goto parse_dup_op_rollback;
2333  parse_dup_op_invalid_interval:
2334   if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
2335     {
2336       *err = REG_BADBR;
2337       return NULL;
2338     }
2339  parse_dup_op_rollback:
2340   re_string_set_index (regexp, start_idx);
2341   *token = start_token;
2342   token->type = CHARACTER;
2343   return dup_elem;
2344 }
2345
2346 /* Size of the names for collating symbol/equivalence_class/character_class.
2347    I'm not sure, but maybe enough.  */
2348 #define BRACKET_NAME_BUF_SIZE 32
2349
2350 #ifndef _LIBC
2351   /* Local function for parse_bracket_exp only used in case of NOT _LIBC.
2352      Build the range expression which starts from START_ELEM, and ends
2353      at END_ELEM.  The result are written to MBCSET and SBCSET.
2354      RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2355      mbcset->range_ends, is a pointer argument sinse we may
2356      update it.  */
2357
2358 static reg_errcode_t
2359 # ifdef RE_ENABLE_I18N
2360 build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
2361      re_charset_t *mbcset;
2362      int *range_alloc;
2363 # else /* not RE_ENABLE_I18N */
2364 build_range_exp (sbcset, start_elem, end_elem)
2365 # endif /* not RE_ENABLE_I18N */
2366      re_bitset_ptr_t sbcset;
2367      bracket_elem_t *start_elem, *end_elem;
2368 {
2369   unsigned int start_ch, end_ch;
2370   /* Equivalence Classes and Character Classes can't be a range start/end.  */
2371   if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2372           || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2373           0))
2374     return REG_ERANGE;
2375
2376   /* We can handle no multi character collating elements without libc
2377      support.  */
2378   if (BE ((start_elem->type == COLL_SYM
2379            && strlen ((char *) start_elem->opr.name) > 1)
2380           || (end_elem->type == COLL_SYM
2381               && strlen ((char *) end_elem->opr.name) > 1), 0))
2382     return REG_ECOLLATE;
2383
2384 # ifdef RE_ENABLE_I18N
2385   {
2386     wchar_t wc, start_wc, end_wc;
2387     wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
2388
2389     start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
2390                 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2391                    : 0));
2392     end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
2393               : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2394                  : 0));
2395     start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
2396                 ? __btowc (start_ch) : start_elem->opr.wch);
2397     end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
2398               ? __btowc (end_ch) : end_elem->opr.wch);
2399     cmp_buf[0] = start_wc;
2400     cmp_buf[4] = end_wc;
2401     if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
2402       return REG_ERANGE;
2403
2404     /* Check the space of the arrays.  */
2405     if (*range_alloc == mbcset->nranges)
2406       {
2407         /* There are not enough space, need realloc.  */
2408         wchar_t *new_array_start, *new_array_end;
2409         int new_nranges;
2410
2411         /* +1 in case of mbcset->nranges is 0.  */
2412         new_nranges = 2 * mbcset->nranges + 1;
2413         /* Use realloc since mbcset->range_starts and mbcset->range_ends
2414            are NULL if *range_alloc == 0.  */
2415         new_array_start = re_realloc (mbcset->range_starts, wchar_t,
2416                                       new_nranges);
2417         new_array_end = re_realloc (mbcset->range_ends, wchar_t,
2418                                     new_nranges);
2419
2420         if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2421           return REG_ESPACE;
2422
2423         mbcset->range_starts = new_array_start;
2424         mbcset->range_ends = new_array_end;
2425         *range_alloc = new_nranges;
2426       }
2427
2428     mbcset->range_starts[mbcset->nranges] = start_wc;
2429     mbcset->range_ends[mbcset->nranges++] = end_wc;
2430
2431     /* Build the table for single byte characters.  */
2432     for (wc = 0; wc <= SBC_MAX; ++wc)
2433       {
2434         cmp_buf[2] = wc;
2435         if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
2436             && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
2437           bitset_set (sbcset, wc);
2438       }
2439   }
2440 # else /* not RE_ENABLE_I18N */
2441   {
2442     unsigned int ch;
2443     start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch
2444                 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2445                    : 0));
2446     end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch
2447               : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2448                  : 0));
2449     if (start_ch > end_ch)
2450       return REG_ERANGE;
2451     /* Build the table for single byte characters.  */
2452     for (ch = 0; ch <= SBC_MAX; ++ch)
2453       if (start_ch <= ch  && ch <= end_ch)
2454         bitset_set (sbcset, ch);
2455   }
2456 # endif /* not RE_ENABLE_I18N */
2457   return REG_NOERROR;
2458 }
2459 #endif /* not _LIBC */
2460
2461 #ifndef _LIBC
2462 /* Helper function for parse_bracket_exp only used in case of NOT _LIBC..
2463    Build the collating element which is represented by NAME.
2464    The result are written to MBCSET and SBCSET.
2465    COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2466    pointer argument since we may update it.  */
2467
2468 static reg_errcode_t
2469 # ifdef RE_ENABLE_I18N
2470 build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
2471      re_charset_t *mbcset;
2472      int *coll_sym_alloc;
2473 # else /* not RE_ENABLE_I18N */
2474 build_collating_symbol (sbcset, name)
2475 # endif /* not RE_ENABLE_I18N */
2476      re_bitset_ptr_t sbcset;
2477      const unsigned char *name;
2478 {
2479   size_t name_len = strlen ((const char *) name);
2480   if (BE (name_len != 1, 0))
2481     return REG_ECOLLATE;
2482   else
2483     {
2484       bitset_set (sbcset, name[0]);
2485       return REG_NOERROR;
2486     }
2487 }
2488 #endif /* not _LIBC */
2489
2490 /* This function parse bracket expression like "[abc]", "[a-c]",
2491    "[[.a-a.]]" etc.  */
2492
2493 static bin_tree_t *
2494 parse_bracket_exp (regexp, dfa, token, syntax, err)
2495      re_string_t *regexp;
2496      re_dfa_t *dfa;
2497      re_token_t *token;
2498      reg_syntax_t syntax;
2499      reg_errcode_t *err;
2500 {
2501 #ifdef _LIBC
2502   const unsigned char *collseqmb;
2503   const char *collseqwc;
2504   uint32_t nrules;
2505   int32_t table_size;
2506   const int32_t *symb_table;
2507   const unsigned char *extra;
2508
2509   /* Local function for parse_bracket_exp used in _LIBC environement.
2510      Seek the collating symbol entry correspondings to NAME.
2511      Return the index of the symbol in the SYMB_TABLE.  */
2512
2513   static inline int32_t
2514   seek_collating_symbol_entry (name, name_len)
2515          const unsigned char *name;
2516          size_t name_len;
2517     {
2518       int32_t hash = elem_hash ((const char *) name, name_len);
2519       int32_t elem = hash % table_size;
2520       int32_t second = hash % (table_size - 2);
2521       while (symb_table[2 * elem] != 0)
2522         {
2523           /* First compare the hashing value.  */
2524           if (symb_table[2 * elem] == hash
2525               /* Compare the length of the name.  */
2526               && name_len == extra[symb_table[2 * elem + 1]]
2527               /* Compare the name.  */
2528               && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
2529                          name_len) == 0)
2530             {
2531               /* Yep, this is the entry.  */
2532               break;
2533             }
2534
2535           /* Next entry.  */
2536           elem += second;
2537         }
2538       return elem;
2539     }
2540
2541   /* Local function for parse_bracket_exp used in _LIBC environement.
2542      Look up the collation sequence value of BR_ELEM.
2543      Return the value if succeeded, UINT_MAX otherwise.  */
2544
2545   static inline unsigned int
2546   lookup_collation_sequence_value (br_elem)
2547          bracket_elem_t *br_elem;
2548     {
2549       if (br_elem->type == SB_CHAR)
2550         {
2551           /*
2552           if (MB_CUR_MAX == 1)
2553           */
2554           if (nrules == 0)
2555             return collseqmb[br_elem->opr.ch];
2556           else
2557             {
2558               wint_t wc = __btowc (br_elem->opr.ch);
2559               return collseq_table_lookup (collseqwc, wc);
2560             }
2561         }
2562       else if (br_elem->type == MB_CHAR)
2563         {
2564           return collseq_table_lookup (collseqwc, br_elem->opr.wch);
2565         }
2566       else if (br_elem->type == COLL_SYM)
2567         {
2568           size_t sym_name_len = strlen ((char *) br_elem->opr.name);
2569           if (nrules != 0)
2570             {
2571               int32_t elem, idx;
2572               elem = seek_collating_symbol_entry (br_elem->opr.name,
2573                                                   sym_name_len);
2574               if (symb_table[2 * elem] != 0)
2575                 {
2576                   /* We found the entry.  */
2577                   idx = symb_table[2 * elem + 1];
2578                   /* Skip the name of collating element name.  */
2579                   idx += 1 + extra[idx];
2580                   /* Skip the byte sequence of the collating element.  */
2581                   idx += 1 + extra[idx];
2582                   /* Adjust for the alignment.  */
2583                   idx = (idx + 3) & ~3;
2584                   /* Skip the multibyte collation sequence value.  */
2585                   idx += sizeof (unsigned int);
2586                   /* Skip the wide char sequence of the collating element.  */
2587                   idx += sizeof (unsigned int) *
2588                     (1 + *(unsigned int *) (extra + idx));
2589                   /* Return the collation sequence value.  */
2590                   return *(unsigned int *) (extra + idx);
2591                 }
2592               else if (symb_table[2 * elem] == 0 && sym_name_len == 1)
2593                 {
2594                   /* No valid character.  Match it as a single byte
2595                      character.  */
2596                   return collseqmb[br_elem->opr.name[0]];
2597                 }
2598             }
2599           else if (sym_name_len == 1)
2600             return collseqmb[br_elem->opr.name[0]];
2601         }
2602       return UINT_MAX;
2603     }
2604
2605   /* Local function for parse_bracket_exp used in _LIBC environement.
2606      Build the range expression which starts from START_ELEM, and ends
2607      at END_ELEM.  The result are written to MBCSET and SBCSET.
2608      RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2609      mbcset->range_ends, is a pointer argument sinse we may
2610      update it.  */
2611
2612   static inline reg_errcode_t
2613 # ifdef RE_ENABLE_I18N
2614   build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
2615          re_charset_t *mbcset;
2616          int *range_alloc;
2617 # else /* not RE_ENABLE_I18N */
2618   build_range_exp (sbcset, start_elem, end_elem)
2619 # endif /* not RE_ENABLE_I18N */
2620          re_bitset_ptr_t sbcset;
2621          bracket_elem_t *start_elem, *end_elem;
2622     {
2623       unsigned int ch;
2624       uint32_t start_collseq;
2625       uint32_t end_collseq;
2626
2627 # ifdef RE_ENABLE_I18N
2628       /* Check the space of the arrays.  */
2629       if (*range_alloc == mbcset->nranges)
2630         {
2631           /* There are not enough space, need realloc.  */
2632           uint32_t *new_array_start;
2633           uint32_t *new_array_end;
2634           int new_nranges;
2635
2636           /* +1 in case of mbcset->nranges is 0.  */
2637           new_nranges = 2 * mbcset->nranges + 1;
2638           /* Use realloc since mbcset->range_starts and mbcset->range_ends
2639              are NULL if *range_alloc == 0.  */
2640           new_array_start = re_realloc (mbcset->range_starts, uint32_t,
2641                                         new_nranges);
2642           new_array_end = re_realloc (mbcset->range_ends, uint32_t,
2643                                       new_nranges);
2644
2645           if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2646             return REG_ESPACE;
2647
2648           mbcset->range_starts = new_array_start;
2649           mbcset->range_ends = new_array_end;
2650           *range_alloc = new_nranges;
2651         }
2652 # endif /* RE_ENABLE_I18N */
2653
2654       /* Equivalence Classes and Character Classes can't be a range
2655          start/end.  */
2656       if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2657               || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2658               0))
2659         return REG_ERANGE;
2660
2661       start_collseq = lookup_collation_sequence_value (start_elem);
2662       end_collseq = lookup_collation_sequence_value (end_elem);
2663       /* Check start/end collation sequence values.  */
2664       if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))
2665         return REG_ECOLLATE;
2666       if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))
2667         return REG_ERANGE;
2668
2669 # ifdef RE_ENABLE_I18N
2670       /* Got valid collation sequence values, add them as a new entry.  */
2671       mbcset->range_starts[mbcset->nranges] = start_collseq;
2672       mbcset->range_ends[mbcset->nranges++] = end_collseq;
2673 # endif /* RE_ENABLE_I18N */
2674
2675       /* Build the table for single byte characters.  */
2676       for (ch = 0; ch <= SBC_MAX; ch++)
2677         {
2678           uint32_t ch_collseq;
2679           /*
2680           if (MB_CUR_MAX == 1)
2681           */
2682           if (nrules == 0)
2683             ch_collseq = collseqmb[ch];
2684           else
2685             ch_collseq = collseq_table_lookup (collseqwc, __btowc (ch));
2686           if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
2687             bitset_set (sbcset, ch);
2688         }
2689       return REG_NOERROR;
2690     }
2691
2692   /* Local function for parse_bracket_exp used in _LIBC environement.
2693      Build the collating element which is represented by NAME.
2694      The result are written to MBCSET and SBCSET.
2695      COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2696      pointer argument sinse we may update it.  */
2697
2698   static inline reg_errcode_t
2699 # ifdef RE_ENABLE_I18N
2700   build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
2701          re_charset_t *mbcset;
2702          int *coll_sym_alloc;
2703 # else /* not RE_ENABLE_I18N */
2704   build_collating_symbol (sbcset, name)
2705 # endif /* not RE_ENABLE_I18N */
2706          re_bitset_ptr_t sbcset;
2707          const unsigned char *name;
2708     {
2709       int32_t elem, idx;
2710       size_t name_len = strlen ((const char *) name);
2711       if (nrules != 0)
2712         {
2713           elem = seek_collating_symbol_entry (name, name_len);
2714           if (symb_table[2 * elem] != 0)
2715             {
2716               /* We found the entry.  */
2717               idx = symb_table[2 * elem + 1];
2718               /* Skip the name of collating element name.  */
2719               idx += 1 + extra[idx];
2720             }
2721           else if (symb_table[2 * elem] == 0 && name_len == 1)
2722             {
2723               /* No valid character, treat it as a normal
2724                  character.  */
2725               bitset_set (sbcset, name[0]);
2726               return REG_NOERROR;
2727             }
2728           else
2729             return REG_ECOLLATE;
2730
2731 # ifdef RE_ENABLE_I18N
2732           /* Got valid collation sequence, add it as a new entry.  */
2733           /* Check the space of the arrays.  */
2734           if (*coll_sym_alloc == mbcset->ncoll_syms)
2735             {
2736               /* Not enough, realloc it.  */
2737               /* +1 in case of mbcset->ncoll_syms is 0.  */
2738               *coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
2739               /* Use realloc since mbcset->coll_syms is NULL
2740                  if *alloc == 0.  */
2741               mbcset->coll_syms = re_realloc (mbcset->coll_syms, int32_t,
2742                                               *coll_sym_alloc);
2743               if (BE (mbcset->coll_syms == NULL, 0))
2744                 return REG_ESPACE;
2745             }
2746           mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
2747 # endif /* RE_ENABLE_I18N */
2748           return REG_NOERROR;
2749         }
2750       else
2751         {
2752           if (BE (name_len != 1, 0))
2753             return REG_ECOLLATE;
2754           else
2755             {
2756               bitset_set (sbcset, name[0]);
2757               return REG_NOERROR;
2758             }
2759         }
2760     }
2761 #endif
2762
2763   re_token_t br_token;
2764   re_bitset_ptr_t sbcset;
2765 #ifdef RE_ENABLE_I18N
2766   re_charset_t *mbcset;
2767   int coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
2768   int equiv_class_alloc = 0, char_class_alloc = 0;
2769 #else /* not RE_ENABLE_I18N */
2770   int non_match = 0;
2771 #endif /* not RE_ENABLE_I18N */
2772   bin_tree_t *work_tree;
2773   int token_len, new_idx;
2774 #ifdef _LIBC
2775   collseqmb = (const unsigned char *)
2776     _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
2777   nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2778   if (nrules)
2779     {
2780       /*
2781       if (MB_CUR_MAX > 1)
2782       */
2783         collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
2784       table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
2785       symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
2786                                                   _NL_COLLATE_SYMB_TABLEMB);
2787       extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
2788                                                    _NL_COLLATE_SYMB_EXTRAMB);
2789     }
2790 #endif
2791   sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
2792 #ifdef RE_ENABLE_I18N
2793   mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
2794 #endif /* RE_ENABLE_I18N */
2795 #ifdef RE_ENABLE_I18N
2796   if (BE (sbcset == NULL || mbcset == NULL, 0))
2797 #else
2798   if (BE (sbcset == NULL, 0))
2799 #endif /* RE_ENABLE_I18N */
2800     {
2801       *err = REG_ESPACE;
2802       return NULL;
2803     }
2804
2805   token_len = peek_token_bracket (token, regexp, syntax);
2806   if (BE (token->type == END_OF_RE, 0))
2807     {
2808       *err = REG_BADPAT;
2809       goto parse_bracket_exp_free_return;
2810     }
2811   if (token->type == OP_NON_MATCH_LIST)
2812     {
2813 #ifdef RE_ENABLE_I18N
2814       int i;
2815       mbcset->non_match = 1;
2816 #else /* not RE_ENABLE_I18N */
2817       non_match = 1;
2818 #endif /* not RE_ENABLE_I18N */
2819       if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
2820         bitset_set (sbcset, '\0');
2821       re_string_skip_bytes (regexp, token_len); /* Skip a token.  */
2822       token_len = peek_token_bracket (token, regexp, syntax);
2823       if (BE (token->type == END_OF_RE, 0))
2824         {
2825           *err = REG_BADPAT;
2826           goto parse_bracket_exp_free_return;
2827         }
2828 #ifdef RE_ENABLE_I18N
2829       if (MB_CUR_MAX > 1)
2830         for (i = 0; i < SBC_MAX; ++i)
2831           if (__btowc (i) == WEOF)
2832             bitset_set (sbcset, i);
2833 #endif /* RE_ENABLE_I18N */
2834     }
2835
2836   /* We treat the first ']' as a normal character.  */
2837   if (token->type == OP_CLOSE_BRACKET)
2838     token->type = CHARACTER;
2839
2840   while (1)
2841     {
2842       bracket_elem_t start_elem, end_elem;
2843       unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
2844       unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
2845       reg_errcode_t ret;
2846       int token_len2 = 0, is_range_exp = 0;
2847       re_token_t token2;
2848
2849       start_elem.opr.name = start_name_buf;
2850       ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
2851                                    syntax);
2852       if (BE (ret != REG_NOERROR, 0))
2853         {
2854           *err = ret;
2855           goto parse_bracket_exp_free_return;
2856         }
2857
2858       token_len = peek_token_bracket (token, regexp, syntax);
2859       if (BE (token->type == END_OF_RE, 0))
2860         {
2861           *err = REG_BADPAT;
2862           goto parse_bracket_exp_free_return;
2863         }
2864       if (token->type == OP_CHARSET_RANGE)
2865         {
2866           re_string_skip_bytes (regexp, token_len); /* Skip '-'.  */
2867           token_len2 = peek_token_bracket (&token2, regexp, syntax);
2868           if (BE (token->type == END_OF_RE, 0))
2869             {
2870               *err = REG_BADPAT;
2871               goto parse_bracket_exp_free_return;
2872             }
2873           if (token2.type == OP_CLOSE_BRACKET)
2874             {
2875               /* We treat the last '-' as a normal character.  */
2876               re_string_skip_bytes (regexp, -token_len);
2877               token->type = CHARACTER;
2878             }
2879           else
2880             is_range_exp = 1;
2881         }
2882
2883       if (is_range_exp == 1)
2884         {
2885           end_elem.opr.name = end_name_buf;
2886           ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
2887                                        dfa, syntax);
2888           if (BE (ret != REG_NOERROR, 0))
2889             {
2890               *err = ret;
2891               goto parse_bracket_exp_free_return;
2892             }
2893
2894           token_len = peek_token_bracket (token, regexp, syntax);
2895           if (BE (token->type == END_OF_RE, 0))
2896             {
2897               *err = REG_BADPAT;
2898               goto parse_bracket_exp_free_return;
2899             }
2900           *err = build_range_exp (sbcset,
2901 #ifdef RE_ENABLE_I18N
2902                                   mbcset, &range_alloc,
2903 #endif /* RE_ENABLE_I18N */
2904                                   &start_elem, &end_elem);
2905           if (BE (*err != REG_NOERROR, 0))
2906             goto parse_bracket_exp_free_return;
2907         }
2908       else
2909         {
2910           switch (start_elem.type)
2911             {
2912             case SB_CHAR:
2913               bitset_set (sbcset, start_elem.opr.ch);
2914               break;
2915 #ifdef RE_ENABLE_I18N
2916             case MB_CHAR:
2917               /* Check whether the array has enough space.  */
2918               if (mbchar_alloc == mbcset->nmbchars)
2919                 {
2920                   /* Not enough, realloc it.  */
2921                   /* +1 in case of mbcset->nmbchars is 0.  */
2922                   mbchar_alloc = 2 * mbcset->nmbchars + 1;
2923                   /* Use realloc since array is NULL if *alloc == 0.  */
2924                   mbcset->mbchars = re_realloc (mbcset->mbchars, wchar_t,
2925                                                 mbchar_alloc);
2926                   if (BE (mbcset->mbchars == NULL, 0))
2927                     goto parse_bracket_exp_espace;
2928                 }
2929               mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
2930               break;
2931 #endif /* RE_ENABLE_I18N */
2932             case EQUIV_CLASS:
2933               *err = build_equiv_class (sbcset,
2934 #ifdef RE_ENABLE_I18N
2935                                         mbcset, &equiv_class_alloc,
2936 #endif /* RE_ENABLE_I18N */
2937                                         start_elem.opr.name);
2938               if (BE (*err != REG_NOERROR, 0))
2939                 goto parse_bracket_exp_free_return;
2940               break;
2941             case COLL_SYM:
2942               *err = build_collating_symbol (sbcset,
2943 #ifdef RE_ENABLE_I18N
2944                                              mbcset, &coll_sym_alloc,
2945 #endif /* RE_ENABLE_I18N */
2946                                              start_elem.opr.name);
2947               if (BE (*err != REG_NOERROR, 0))
2948                 goto parse_bracket_exp_free_return;
2949               break;
2950             case CHAR_CLASS:
2951               ret = build_charclass (sbcset,
2952 #ifdef RE_ENABLE_I18N
2953                                      mbcset, &char_class_alloc,
2954 #endif /* RE_ENABLE_I18N */
2955                                      start_elem.opr.name, syntax);
2956               if (BE (ret != REG_NOERROR, 0))
2957                goto parse_bracket_exp_espace;
2958               break;
2959             default:
2960               assert (0);
2961               break;
2962             }
2963         }
2964       if (token->type == OP_CLOSE_BRACKET)
2965         break;
2966     }
2967
2968   re_string_skip_bytes (regexp, token_len); /* Skip a token.  */
2969
2970   /* If it is non-matching list.  */
2971 #ifdef RE_ENABLE_I18N
2972   if (mbcset->non_match)
2973 #else /* not RE_ENABLE_I18N */
2974   if (non_match)
2975 #endif /* not RE_ENABLE_I18N */
2976     bitset_not (sbcset);
2977
2978   /* Build a tree for simple bracket.  */
2979   br_token.type = SIMPLE_BRACKET;
2980   br_token.opr.sbcset = sbcset;
2981   new_idx = re_dfa_add_node (dfa, br_token, 0);
2982   work_tree = create_tree (NULL, NULL, 0, new_idx);
2983   if (BE (new_idx == -1 || work_tree == NULL, 0))
2984     goto parse_bracket_exp_espace;
2985
2986 #ifdef RE_ENABLE_I18N
2987   if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
2988       || mbcset->nranges || (MB_CUR_MAX > 1 && (mbcset->nchar_classes
2989                                                 || mbcset->non_match)))
2990     {
2991       re_token_t alt_token;
2992       bin_tree_t *mbc_tree;
2993       /* Build a tree for complex bracket.  */
2994       br_token.type = COMPLEX_BRACKET;
2995       br_token.opr.mbcset = mbcset;
2996       dfa->has_mb_node = 1;
2997       new_idx = re_dfa_add_node (dfa, br_token, 0);
2998       mbc_tree = create_tree (NULL, NULL, 0, new_idx);
2999       if (BE (new_idx == -1 || mbc_tree == NULL, 0))
3000         goto parse_bracket_exp_espace;
3001       /* Then join them by ALT node.  */
3002       dfa->has_plural_match = 1;
3003       alt_token.type = OP_ALT;
3004       new_idx = re_dfa_add_node (dfa, alt_token, 0);
3005       work_tree = create_tree (work_tree, mbc_tree, 0, new_idx);
3006       if (BE (new_idx != -1 && mbc_tree != NULL, 1))
3007         return work_tree;
3008     }
3009   else
3010     {
3011       free_charset (mbcset);
3012       return work_tree;
3013     }
3014 #else /* not RE_ENABLE_I18N */
3015   return work_tree;
3016 #endif /* not RE_ENABLE_I18N */
3017
3018  parse_bracket_exp_espace:
3019   *err = REG_ESPACE;
3020  parse_bracket_exp_free_return:
3021   re_free (sbcset);
3022 #ifdef RE_ENABLE_I18N
3023   free_charset (mbcset);
3024 #endif /* RE_ENABLE_I18N */
3025   return NULL;
3026 }
3027
3028 /* Parse an element in the bracket expression.  */
3029
3030 static reg_errcode_t
3031 parse_bracket_element (elem, regexp, token, token_len, dfa, syntax)
3032      bracket_elem_t *elem;
3033      re_string_t *regexp;
3034      re_token_t *token;
3035      int token_len;
3036      re_dfa_t *dfa;
3037      reg_syntax_t syntax;
3038 {
3039 #ifdef RE_ENABLE_I18N
3040   int cur_char_size;
3041   cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
3042   if (cur_char_size > 1)
3043     {
3044       elem->type = MB_CHAR;
3045       elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
3046       re_string_skip_bytes (regexp, cur_char_size);
3047       return REG_NOERROR;
3048     }
3049 #endif /* RE_ENABLE_I18N */
3050   re_string_skip_bytes (regexp, token_len); /* Skip a token.  */
3051   if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
3052       || token->type == OP_OPEN_EQUIV_CLASS)
3053     return parse_bracket_symbol (elem, regexp, token);
3054   elem->type = SB_CHAR;
3055   elem->opr.ch = token->opr.c;
3056   return REG_NOERROR;
3057 }
3058
3059 /* Parse a bracket symbol in the bracket expression.  Bracket symbols are
3060    such as [:<character_class>:], [.<collating_element>.], and
3061    [=<equivalent_class>=].  */
3062
3063 static reg_errcode_t
3064 parse_bracket_symbol (elem, regexp, token)
3065      bracket_elem_t *elem;
3066      re_string_t *regexp;
3067      re_token_t *token;
3068 {
3069   unsigned char ch, delim = token->opr.c;
3070   int i = 0;
3071   for (;; ++i)
3072     {
3073       if (re_string_eoi(regexp) || i >= BRACKET_NAME_BUF_SIZE)
3074         return REG_EBRACK;
3075       if (token->type == OP_OPEN_CHAR_CLASS)
3076         ch = re_string_fetch_byte_case (regexp);
3077       else
3078         ch = re_string_fetch_byte (regexp);
3079       if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
3080         break;
3081       elem->opr.name[i] = ch;
3082     }
3083   re_string_skip_bytes (regexp, 1);
3084   elem->opr.name[i] = '\0';
3085   switch (token->type)
3086     {
3087     case OP_OPEN_COLL_ELEM:
3088       elem->type = COLL_SYM;
3089       break;
3090     case OP_OPEN_EQUIV_CLASS:
3091       elem->type = EQUIV_CLASS;
3092       break;
3093     case OP_OPEN_CHAR_CLASS:
3094       elem->type = CHAR_CLASS;
3095       break;
3096     default:
3097       break;
3098     }
3099   return REG_NOERROR;
3100 }
3101
3102   /* Helper function for parse_bracket_exp.
3103      Build the equivalence class which is represented by NAME.
3104      The result are written to MBCSET and SBCSET.
3105      EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,
3106      is a pointer argument sinse we may update it.  */
3107
3108 static reg_errcode_t
3109 #ifdef RE_ENABLE_I18N
3110 build_equiv_class (sbcset, mbcset, equiv_class_alloc, name)
3111      re_charset_t *mbcset;
3112      int *equiv_class_alloc;
3113 #else /* not RE_ENABLE_I18N */
3114 build_equiv_class (sbcset, name)
3115 #endif /* not RE_ENABLE_I18N */
3116      re_bitset_ptr_t sbcset;
3117      const unsigned char *name;
3118 {
3119 #if defined _LIBC && defined RE_ENABLE_I18N
3120   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3121   if (nrules != 0)
3122     {
3123       const int32_t *table, *indirect;
3124       const unsigned char *weights, *extra, *cp;
3125       unsigned char char_buf[2];
3126       int32_t idx1, idx2;
3127       unsigned int ch;
3128       size_t len;
3129       /* This #include defines a local function!  */
3130 # include <locale/weight.h>
3131       /* Calculate the index for equivalence class.  */
3132       cp = name;
3133       table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3134       weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3135                                                _NL_COLLATE_WEIGHTMB);
3136       extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3137                                                    _NL_COLLATE_EXTRAMB);
3138       indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3139                                                 _NL_COLLATE_INDIRECTMB);
3140       idx1 = findidx (&cp);
3141       if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0))
3142         /* This isn't a valid character.  */
3143         return REG_ECOLLATE;
3144
3145       /* Build single byte matcing table for this equivalence class.  */
3146       char_buf[1] = (unsigned char) '\0';
3147       len = weights[idx1];
3148       for (ch = 0; ch < SBC_MAX; ++ch)
3149         {
3150           char_buf[0] = ch;
3151           cp = char_buf;
3152           idx2 = findidx (&cp);
3153 /*
3154           idx2 = table[ch];
3155 */
3156           if (idx2 == 0)
3157             /* This isn't a valid character.  */
3158             continue;
3159           if (len == weights[idx2])
3160             {
3161               int cnt = 0;
3162               while (cnt <= len &&
3163                      weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt])
3164                 ++cnt;
3165
3166               if (cnt > len)
3167                 bitset_set (sbcset, ch);
3168             }
3169         }
3170       /* Check whether the array has enough space.  */
3171       if (*equiv_class_alloc == mbcset->nequiv_classes)
3172         {
3173           /* Not enough, realloc it.  */
3174           /* +1 in case of mbcset->nequiv_classes is 0.  */
3175           *equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
3176           /* Use realloc since the array is NULL if *alloc == 0.  */
3177           mbcset->equiv_classes = re_realloc (mbcset->equiv_classes, int32_t,
3178                                               *equiv_class_alloc);
3179           if (BE (mbcset->equiv_classes == NULL, 0))
3180             return REG_ESPACE;
3181         }
3182       mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;
3183     }
3184   else
3185 #endif /* _LIBC && RE_ENABLE_I18N */
3186     {
3187       if (BE (strlen ((const char *) name) != 1, 0))
3188         return REG_ECOLLATE;
3189       bitset_set (sbcset, *name);
3190     }
3191   return REG_NOERROR;
3192 }
3193
3194   /* Helper function for parse_bracket_exp.
3195      Build the character class which is represented by NAME.
3196      The result are written to MBCSET and SBCSET.
3197      CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,
3198      is a pointer argument sinse we may update it.  */
3199
3200 static reg_errcode_t
3201 #ifdef RE_ENABLE_I18N
3202 build_charclass (sbcset, mbcset, char_class_alloc, class_name, syntax)
3203      re_charset_t *mbcset;
3204      int *char_class_alloc;
3205 #else /* not RE_ENABLE_I18N */
3206 build_charclass (sbcset, class_name, syntax)
3207 #endif /* not RE_ENABLE_I18N */
3208      re_bitset_ptr_t sbcset;
3209      const unsigned char *class_name;
3210      reg_syntax_t syntax;
3211 {
3212   int i;
3213   const char *name = (const char *) class_name;
3214
3215   /* In case of REG_ICASE "upper" and "lower" match the both of
3216      upper and lower cases.  */
3217   if ((syntax & RE_ICASE)
3218       && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))
3219     name = "alpha";
3220
3221 #ifdef RE_ENABLE_I18N
3222   /* Check the space of the arrays.  */
3223   if (*char_class_alloc == mbcset->nchar_classes)
3224     {
3225       /* Not enough, realloc it.  */
3226       /* +1 in case of mbcset->nchar_classes is 0.  */
3227       *char_class_alloc = 2 * mbcset->nchar_classes + 1;
3228       /* Use realloc since array is NULL if *alloc == 0.  */
3229       mbcset->char_classes = re_realloc (mbcset->char_classes, wctype_t,
3230                                          *char_class_alloc);
3231       if (BE (mbcset->char_classes == NULL, 0))
3232         return REG_ESPACE;
3233     }
3234   mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);
3235 #endif /* RE_ENABLE_I18N */
3236
3237 #define BUILD_CHARCLASS_LOOP(ctype_func)\
3238     for (i = 0; i < SBC_MAX; ++i)       \
3239       {                                 \
3240         if (ctype_func (i))             \
3241           bitset_set (sbcset, i);       \
3242       }
3243
3244   if (strcmp (name, "alnum") == 0)
3245     BUILD_CHARCLASS_LOOP (isalnum)
3246   else if (strcmp (name, "cntrl") == 0)
3247     BUILD_CHARCLASS_LOOP (iscntrl)
3248   else if (strcmp (name, "lower") == 0)
3249     BUILD_CHARCLASS_LOOP (islower)
3250   else if (strcmp (name, "space") == 0)
3251     BUILD_CHARCLASS_LOOP (isspace)
3252   else if (strcmp (name, "alpha") == 0)
3253     BUILD_CHARCLASS_LOOP (isalpha)
3254   else if (strcmp (name, "digit") == 0)
3255     BUILD_CHARCLASS_LOOP (isdigit)
3256   else if (strcmp (name, "print") == 0)
3257     BUILD_CHARCLASS_LOOP (isprint)
3258   else if (strcmp (name, "upper") == 0)
3259     BUILD_CHARCLASS_LOOP (isupper)
3260   else if (strcmp (name, "blank") == 0)
3261     BUILD_CHARCLASS_LOOP (isblank)
3262   else if (strcmp (name, "graph") == 0)
3263     BUILD_CHARCLASS_LOOP (isgraph)
3264   else if (strcmp (name, "punct") == 0)
3265     BUILD_CHARCLASS_LOOP (ispunct)
3266   else if (strcmp (name, "xdigit") == 0)
3267     BUILD_CHARCLASS_LOOP (isxdigit)
3268   else
3269     return REG_ECTYPE;
3270
3271   return REG_NOERROR;
3272 }
3273
3274 static bin_tree_t *
3275 build_word_op (dfa, not, err)
3276      re_dfa_t *dfa;
3277      int not;
3278      reg_errcode_t *err;
3279 {
3280   re_bitset_ptr_t sbcset;
3281 #ifdef RE_ENABLE_I18N
3282   re_charset_t *mbcset;
3283   int alloc = 0;
3284 #else /* not RE_ENABLE_I18N */
3285   int non_match = 0;
3286 #endif /* not RE_ENABLE_I18N */
3287   reg_errcode_t ret;
3288   re_token_t br_token;
3289   bin_tree_t *tree;
3290   int new_idx;
3291
3292   sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
3293 #ifdef RE_ENABLE_I18N
3294   mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3295 #endif /* RE_ENABLE_I18N */
3296
3297 #ifdef RE_ENABLE_I18N
3298   if (BE (sbcset == NULL || mbcset == NULL, 0))
3299 #else /* not RE_ENABLE_I18N */
3300   if (BE (sbcset == NULL, 0))
3301 #endif /* not RE_ENABLE_I18N */
3302     {
3303       *err = REG_ESPACE;
3304       return NULL;
3305     }
3306
3307   if (not)
3308     {
3309 #ifdef RE_ENABLE_I18N
3310       int i;
3311       /*
3312       if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
3313         bitset_set(cset->sbcset, '\0');
3314       */
3315       mbcset->non_match = 1;
3316       if (MB_CUR_MAX > 1)
3317         for (i = 0; i < SBC_MAX; ++i)
3318           if (__btowc (i) == WEOF)
3319             bitset_set (sbcset, i);
3320 #else /* not RE_ENABLE_I18N */
3321       non_match = 1;
3322 #endif /* not RE_ENABLE_I18N */
3323     }
3324
3325   /* We don't care the syntax in this case.  */
3326   ret = build_charclass (sbcset,
3327 #ifdef RE_ENABLE_I18N
3328                          mbcset, &alloc,
3329 #endif /* RE_ENABLE_I18N */
3330                          (const unsigned char *) "alpha", 0);
3331
3332   if (BE (ret != REG_NOERROR, 0))
3333     {
3334       re_free (sbcset);
3335 #ifdef RE_ENABLE_I18N
3336       free_charset (mbcset);
3337 #endif /* RE_ENABLE_I18N */
3338       *err = REG_ESPACE;
3339       return NULL;
3340     }
3341   /* \w match '_' also.  */
3342   bitset_set (sbcset, '_');
3343
3344   /* If it is non-matching list.  */
3345 #ifdef RE_ENABLE_I18N
3346   if (mbcset->non_match)
3347 #else /* not RE_ENABLE_I18N */
3348   if (non_match)
3349 #endif /* not RE_ENABLE_I18N */
3350     bitset_not (sbcset);
3351
3352   /* Build a tree for simple bracket.  */
3353   br_token.type = SIMPLE_BRACKET;
3354   br_token.opr.sbcset = sbcset;
3355   new_idx = re_dfa_add_node (dfa, br_token, 0);
3356   tree = create_tree (NULL, NULL, 0, new_idx);
3357   if (BE (new_idx == -1 || tree == NULL, 0))
3358     goto build_word_op_espace;
3359
3360 #ifdef RE_ENABLE_I18N
3361   if (MB_CUR_MAX > 1)
3362     {
3363       re_token_t alt_token;
3364       bin_tree_t *mbc_tree;
3365       /* Build a tree for complex bracket.  */
3366       br_token.type = COMPLEX_BRACKET;
3367       br_token.opr.mbcset = mbcset;
3368       dfa->has_mb_node = 1;
3369       new_idx = re_dfa_add_node (dfa, br_token, 0);
3370       mbc_tree = create_tree (NULL, NULL, 0, new_idx);
3371       if (BE (new_idx == -1 || mbc_tree == NULL, 0))
3372         goto build_word_op_espace;
3373       /* Then join them by ALT node.  */
3374       alt_token.type = OP_ALT;
3375       new_idx = re_dfa_add_node (dfa, alt_token, 0);
3376       tree = create_tree (tree, mbc_tree, 0, new_idx);
3377       if (BE (new_idx != -1 && mbc_tree != NULL, 1))
3378         return tree;
3379     }
3380   else
3381     {
3382       free_charset (mbcset);
3383       return tree;
3384     }
3385 #else /* not RE_ENABLE_I18N */
3386   return tree;
3387 #endif /* not RE_ENABLE_I18N */
3388
3389  build_word_op_espace:
3390   re_free (sbcset);
3391 #ifdef RE_ENABLE_I18N
3392   free_charset (mbcset);
3393 #endif /* RE_ENABLE_I18N */
3394   *err = REG_ESPACE;
3395   return NULL;
3396 }
3397
3398 /* This is intended for the expressions like "a{1,3}".
3399    Fetch a number from `input', and return the number.
3400    Return -1, if the number field is empty like "{,1}".
3401    Return -2, If an error is occured.  */
3402
3403 static int
3404 fetch_number (input, token, syntax)
3405      re_string_t *input;
3406      re_token_t *token;
3407      reg_syntax_t syntax;
3408 {
3409   int num = -1;
3410   unsigned char c;
3411   while (1)
3412     {
3413       *token = fetch_token (input, syntax);
3414       c = token->opr.c;
3415       if (BE (token->type == END_OF_RE, 0))
3416         return -2;
3417       if (token->type == OP_CLOSE_DUP_NUM || c == ',')
3418         break;
3419       num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2)
3420              ? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0'));
3421       num = (num > RE_DUP_MAX) ? -2 : num;
3422     }
3423   return num;
3424 }
3425 \f
3426 #ifdef RE_ENABLE_I18N
3427 static void
3428 free_charset (re_charset_t *cset)
3429 {
3430   re_free (cset->mbchars);
3431 # ifdef _LIBC
3432   re_free (cset->coll_syms);
3433   re_free (cset->equiv_classes);
3434   re_free (cset->range_starts);
3435   re_free (cset->range_ends);
3436 # endif
3437   re_free (cset->char_classes);
3438   re_free (cset);
3439 }
3440 #endif /* RE_ENABLE_I18N */
3441 \f
3442 /* Functions for binary tree operation.  */
3443
3444 /* Create a node of tree.
3445    Note: This function automatically free left and right if malloc fails.  */
3446
3447 static bin_tree_t *
3448 create_tree (left, right, type, index)
3449      bin_tree_t *left;
3450      bin_tree_t *right;
3451      re_token_type_t type;
3452      int index;
3453 {
3454   bin_tree_t *tree;
3455   tree = re_malloc (bin_tree_t, 1);
3456   if (BE (tree == NULL, 0))
3457     {
3458       free_bin_tree (left);
3459       free_bin_tree (right);
3460       return NULL;
3461     }
3462   tree->parent = NULL;
3463   tree->left = left;
3464   tree->right = right;
3465   tree->type = type;
3466   tree->node_idx = index;
3467   tree->first = -1;
3468   tree->next = -1;
3469   re_node_set_init_empty (&tree->eclosure);
3470
3471   if (left != NULL)
3472     left->parent = tree;
3473   if (right != NULL)
3474     right->parent = tree;
3475   return tree;
3476 }
3477
3478 /* Free the sub tree pointed by TREE.  */
3479
3480 static void
3481 free_bin_tree (tree)
3482      bin_tree_t *tree;
3483 {
3484   if (tree == NULL)
3485     return;
3486   /*re_node_set_free (&tree->eclosure);*/
3487   free_bin_tree (tree->left);
3488   free_bin_tree (tree->right);
3489   re_free (tree);
3490 }
3491
3492 /* Duplicate the node SRC, and return new node.  */
3493
3494 static bin_tree_t *
3495 duplicate_tree (src, dfa)
3496      const bin_tree_t *src;
3497      re_dfa_t *dfa;
3498 {
3499   bin_tree_t *left = NULL, *right = NULL, *new_tree;
3500   int new_node_idx;
3501   /* Since node indies must be according to Post-order of the tree,
3502      we must duplicate the left at first.  */
3503   if (src->left != NULL)
3504     {
3505       left = duplicate_tree (src->left, dfa);
3506       if (left == NULL)
3507         return NULL;
3508     }
3509
3510   /* Secondaly, duplicate the right.  */
3511   if (src->right != NULL)
3512     {
3513       right = duplicate_tree (src->right, dfa);
3514       if (right == NULL)
3515         {
3516           free_bin_tree (left);
3517           return NULL;
3518         }
3519     }
3520
3521   /* At last, duplicate itself.  */
3522   if (src->type == NON_TYPE)
3523     {
3524       new_node_idx = re_dfa_add_node (dfa, dfa->nodes[src->node_idx], 0);
3525       dfa->nodes[new_node_idx].duplicated = 1;
3526       if (BE (new_node_idx == -1, 0))
3527         {
3528           free_bin_tree (left);
3529           free_bin_tree (right);
3530           return NULL;
3531         }
3532     }
3533   else
3534     new_node_idx = src->type;
3535
3536   new_tree = create_tree (left, right, src->type, new_node_idx);
3537   if (BE (new_tree == NULL, 0))
3538     {
3539       free_bin_tree (left);
3540       free_bin_tree (right);
3541     }
3542   return new_tree;
3543 }