lib/regcomp.c

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