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