lib/regcomp.c

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