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