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 merge_err
1025                   = re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
1026                 if (merge_err != REG_NOERROR)
1027                   return merge_err;
1028                 i = 0;
1029               }
1030           }
1031       }
1032
1033   /* It must be the first time to invoke acquire_state.  */
1034   dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);
1035   /* We don't check ERR here, since the initial state must not be NULL.  */
1036   if (BE (dfa->init_state == NULL, 0))
1037     return err;
1038   if (dfa->init_state->has_constraint)
1039     {
1040       dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
1041                                                        CONTEXT_WORD);
1042       dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
1043                                                      CONTEXT_NEWLINE);
1044       dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
1045                                                          &init_nodes,
1046                                                          CONTEXT_NEWLINE
1047                                                          | CONTEXT_BEGBUF);
1048       if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL
1049               || dfa->init_state_begbuf == NULL, 0))
1050         return err;
1051     }
1052   else
1053     dfa->init_state_word = dfa->init_state_nl
1054       = dfa->init_state_begbuf = dfa->init_state;
1055
1056   re_node_set_free (&init_nodes);
1057   return REG_NOERROR;
1058 }
1059 \f
1060 #ifdef RE_ENABLE_I18N
1061 /* If it is possible to do searching in single byte encoding instead of UTF-8
1062    to speed things up, set dfa->mb_cur_max to 1, clear is_utf8 and change
1063    DFA nodes where needed.  */
1064
1065 static void
1066 optimize_utf8 (re_dfa_t *dfa)
1067 {
1068   Idx node;
1069   int i;
1070   bool mb_chars = false;
1071   bool has_period = false;
1072
1073   for (node = 0; node < dfa->nodes_len; ++node)
1074     switch (dfa->nodes[node].type)
1075       {
1076       case CHARACTER:
1077         if (dfa->nodes[node].opr.c >= ASCII_CHARS)
1078           mb_chars = true;
1079         break;
1080       case ANCHOR:
1081         switch (dfa->nodes[node].opr.ctx_type)
1082           {
1083           case LINE_FIRST:
1084           case LINE_LAST:
1085           case BUF_FIRST:
1086           case BUF_LAST:
1087             break;
1088           default:
1089             /* Word anchors etc. cannot be handled.  It's okay to test
1090                opr.ctx_type since constraints (for all DFA nodes) are
1091                created by ORing one or more opr.ctx_type values.  */
1092             return;
1093           }
1094         break;
1095       case OP_PERIOD:
1096         has_period = true;
1097         break;
1098       case OP_BACK_REF:
1099       case OP_ALT:
1100       case END_OF_RE:
1101       case OP_DUP_ASTERISK:
1102       case OP_OPEN_SUBEXP:
1103       case OP_CLOSE_SUBEXP:
1104         break;
1105       case COMPLEX_BRACKET:
1106         return;
1107       case SIMPLE_BRACKET:
1108         /* Just double check.  */
1109         {
1110           int rshift = (ASCII_CHARS % BITSET_WORD_BITS == 0
1111                         ? 0
1112                         : BITSET_WORD_BITS - ASCII_CHARS % BITSET_WORD_BITS);
1113           for (i = ASCII_CHARS / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
1114             {
1115               if (dfa->nodes[node].opr.sbcset[i] >> rshift != 0)
1116                 return;
1117               rshift = 0;
1118             }
1119         }
1120         break;
1121       default:
1122         abort ();
1123       }
1124
1125   if (mb_chars || has_period)
1126     for (node = 0; node < dfa->nodes_len; ++node)
1127       {
1128         if (dfa->nodes[node].type == CHARACTER
1129             && dfa->nodes[node].opr.c >= ASCII_CHARS)
1130           dfa->nodes[node].mb_partial = 0;
1131         else if (dfa->nodes[node].type == OP_PERIOD)
1132           dfa->nodes[node].type = OP_UTF8_PERIOD;
1133       }
1134
1135   /* The search can be in single byte locale.  */
1136   dfa->mb_cur_max = 1;
1137   dfa->is_utf8 = 0;
1138   dfa->has_mb_node = dfa->nbackref > 0 || has_period;
1139 }
1140 #endif
1141 \f
1142 /* Analyze the structure tree, and calculate "first", "next", "edest",
1143    "eclosure", and "inveclosure".  */
1144
1145 static reg_errcode_t
1146 analyze (regex_t *preg)
1147 {
1148   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1149   reg_errcode_t ret;
1150
1151   /* Allocate arrays.  */
1152   dfa->nexts = re_malloc (Idx, dfa->nodes_alloc);
1153   dfa->org_indices = re_malloc (Idx, dfa->nodes_alloc);
1154   dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
1155   dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
1156   if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
1157           || dfa->eclosures == NULL, 0))
1158     return REG_ESPACE;
1159
1160   dfa->subexp_map = re_malloc (Idx, preg->re_nsub);
1161   if (dfa->subexp_map != NULL)
1162     {
1163       Idx i;
1164       for (i = 0; i < preg->re_nsub; i++)
1165         dfa->subexp_map[i] = i;
1166       preorder (dfa->str_tree, optimize_subexps, dfa);
1167       for (i = 0; i < preg->re_nsub; i++)
1168         if (dfa->subexp_map[i] != i)
1169           break;
1170       if (i == preg->re_nsub)
1171         {
1172           free (dfa->subexp_map);
1173           dfa->subexp_map = NULL;
1174         }
1175     }
1176
1177   ret = postorder (dfa->str_tree, lower_subexps, preg);
1178   if (BE (ret != REG_NOERROR, 0))
1179     return ret;
1180   ret = postorder (dfa->str_tree, calc_first, dfa);
1181   if (BE (ret != REG_NOERROR, 0))
1182     return ret;
1183   preorder (dfa->str_tree, calc_next, dfa);
1184   ret = preorder (dfa->str_tree, link_nfa_nodes, dfa);
1185   if (BE (ret != REG_NOERROR, 0))
1186     return ret;
1187   ret = calc_eclosure (dfa);
1188   if (BE (ret != REG_NOERROR, 0))
1189     return ret;
1190
1191   /* We only need this during the prune_impossible_nodes pass in regexec.c;
1192      skip it if p_i_n will not run, as calc_inveclosure can be quadratic.  */
1193   if ((!preg->no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
1194       || dfa->nbackref)
1195     {
1196       dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len);
1197       if (BE (dfa->inveclosures == NULL, 0))
1198         return REG_ESPACE;
1199       ret = calc_inveclosure (dfa);
1200     }
1201
1202   return ret;
1203 }
1204
1205 /* Our parse trees are very unbalanced, so we cannot use a stack to
1206    implement parse tree visits.  Instead, we use parent pointers and
1207    some hairy code in these two functions.  */
1208 static reg_errcode_t
1209 postorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1210            void *extra)
1211 {
1212   bin_tree_t *node, *prev;
1213
1214   for (node = root; ; )
1215     {
1216       /* Descend down the tree, preferably to the left (or to the right
1217          if that's the only child).  */
1218       while (node->left || node->right)
1219         if (node->left)
1220           node = node->left;
1221         else
1222           node = node->right;
1223
1224       do
1225         {
1226           reg_errcode_t err = fn (extra, node);
1227           if (BE (err != REG_NOERROR, 0))
1228             return err;
1229           if (node->parent == NULL)
1230             return REG_NOERROR;
1231           prev = node;
1232           node = node->parent;
1233         }
1234       /* Go up while we have a node that is reached from the right.  */
1235       while (node->right == prev || node->right == NULL);
1236       node = node->right;
1237     }
1238 }
1239
1240 static reg_errcode_t
1241 preorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1242           void *extra)
1243 {
1244   bin_tree_t *node;
1245
1246   for (node = root; ; )
1247     {
1248       reg_errcode_t err = fn (extra, node);
1249       if (BE (err != REG_NOERROR, 0))
1250         return err;
1251
1252       /* Go to the left node, or up and to the right.  */
1253       if (node->left)
1254         node = node->left;
1255       else
1256         {
1257           bin_tree_t *prev = NULL;
1258           while (node->right == prev || node->right == NULL)
1259             {
1260               prev = node;
1261               node = node->parent;
1262               if (!node)
1263                 return REG_NOERROR;
1264             }
1265           node = node->right;
1266         }
1267     }
1268 }
1269
1270 /* Optimization pass: if a SUBEXP is entirely contained, strip it and tell
1271    re_search_internal to map the inner one's opr.idx to this one's.  Adjust
1272    backreferences as well.  Requires a preorder visit.  */
1273 static reg_errcode_t
1274 optimize_subexps (void *extra, bin_tree_t *node)
1275 {
1276   re_dfa_t *dfa = (re_dfa_t *) extra;
1277
1278   if (node->token.type == OP_BACK_REF && dfa->subexp_map)
1279     {
1280       int idx = node->token.opr.idx;
1281       node->token.opr.idx = dfa->subexp_map[idx];
1282       dfa->used_bkref_map |= 1 << node->token.opr.idx;
1283     }
1284
1285   else if (node->token.type == SUBEXP
1286            && node->left && node->left->token.type == SUBEXP)
1287     {
1288       Idx other_idx = node->left->token.opr.idx;
1289
1290       node->left = node->left->left;
1291       if (node->left)
1292         node->left->parent = node;
1293
1294       dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
1295       if (other_idx < BITSET_WORD_BITS)
1296         dfa->used_bkref_map &= ~((bitset_word_t) 1 << other_idx);
1297     }
1298
1299   return REG_NOERROR;
1300 }
1301
1302 /* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
1303    of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP.  */
1304 static reg_errcode_t
1305 lower_subexps (void *extra, bin_tree_t *node)
1306 {
1307   regex_t *preg = (regex_t *) extra;
1308   reg_errcode_t err = REG_NOERROR;
1309
1310   if (node->left && node->left->token.type == SUBEXP)
1311     {
1312       node->left = lower_subexp (&err, preg, node->left);
1313       if (node->left)
1314         node->left->parent = node;
1315     }
1316   if (node->right && node->right->token.type == SUBEXP)
1317     {
1318       node->right = lower_subexp (&err, preg, node->right);
1319       if (node->right)
1320         node->right->parent = node;
1321     }
1322
1323   return err;
1324 }
1325
1326 static bin_tree_t *
1327 lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
1328 {
1329   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1330   bin_tree_t *body = node->left;
1331   bin_tree_t *op, *cls, *tree1, *tree;
1332
1333   if (preg->no_sub
1334       /* We do not optimize empty subexpressions, because otherwise we may
1335          have bad CONCAT nodes with NULL children.  This is obviously not
1336          very common, so we do not lose much.  An example that triggers
1337          this case is the sed "script" /\(\)/x.  */
1338       && node->left != NULL
1339       && (node->token.opr.idx >= BITSET_WORD_BITS
1340           || !(dfa->used_bkref_map
1341                & ((bitset_word_t) 1 << node->token.opr.idx))))
1342     return node->left;
1343
1344   /* Convert the SUBEXP node to the concatenation of an
1345      OP_OPEN_SUBEXP, the contents, and an OP_CLOSE_SUBEXP.  */
1346   op = create_tree (dfa, NULL, NULL, OP_OPEN_SUBEXP);
1347   cls = create_tree (dfa, NULL, NULL, OP_CLOSE_SUBEXP);
1348   tree1 = body ? create_tree (dfa, body, cls, CONCAT) : cls;
1349   tree = create_tree (dfa, op, tree1, CONCAT);
1350   if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
1351     {
1352       *err = REG_ESPACE;
1353       return NULL;
1354     }
1355
1356   op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
1357   op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
1358   return tree;
1359 }
1360
1361 /* Pass 1 in building the NFA: compute FIRST and create unlinked automaton
1362    nodes.  Requires a postorder visit.  */
1363 static reg_errcode_t
1364 calc_first (void *extra, bin_tree_t *node)
1365 {
1366   re_dfa_t *dfa = (re_dfa_t *) extra;
1367   if (node->token.type == CONCAT)
1368     {
1369       node->first = node->left->first;
1370       node->node_idx = node->left->node_idx;
1371     }
1372   else
1373     {
1374       node->first = node;
1375       node->node_idx = re_dfa_add_node (dfa, node->token);
1376       if (BE (node->node_idx == REG_MISSING, 0))
1377         return REG_ESPACE;
1378       if (node->token.type == ANCHOR)
1379         dfa->nodes[node->node_idx].constraint = node->token.opr.ctx_type;
1380     }
1381   return REG_NOERROR;
1382 }
1383
1384 /* Pass 2: compute NEXT on the tree.  Preorder visit.  */
1385 static reg_errcode_t
1386 calc_next (void *extra, bin_tree_t *node)
1387 {
1388   switch (node->token.type)
1389     {
1390     case OP_DUP_ASTERISK:
1391       node->left->next = node;
1392       break;
1393     case CONCAT:
1394       node->left->next = node->right->first;
1395       node->right->next = node->next;
1396       break;
1397     default:
1398       if (node->left)
1399         node->left->next = node->next;
1400       if (node->right)
1401         node->right->next = node->next;
1402       break;
1403     }
1404   return REG_NOERROR;
1405 }
1406
1407 /* Pass 3: link all DFA nodes to their NEXT node (any order will do).  */
1408 static reg_errcode_t
1409 link_nfa_nodes (void *extra, bin_tree_t *node)
1410 {
1411   re_dfa_t *dfa = (re_dfa_t *) extra;
1412   Idx idx = node->node_idx;
1413   reg_errcode_t err = REG_NOERROR;
1414
1415   switch (node->token.type)
1416     {
1417     case CONCAT:
1418       break;
1419
1420     case END_OF_RE:
1421       assert (node->next == NULL);
1422       break;
1423
1424     case OP_DUP_ASTERISK:
1425     case OP_ALT:
1426       {
1427         Idx left, right;
1428         dfa->has_plural_match = 1;
1429         if (node->left != NULL)
1430           left = node->left->first->node_idx;
1431         else
1432           left = node->next->node_idx;
1433         if (node->right != NULL)
1434           right = node->right->first->node_idx;
1435         else
1436           right = node->next->node_idx;
1437         assert (REG_VALID_INDEX (left));
1438         assert (REG_VALID_INDEX (right));
1439         err = re_node_set_init_2 (dfa->edests + idx, left, right);
1440       }
1441       break;
1442
1443     case ANCHOR:
1444     case OP_OPEN_SUBEXP:
1445     case OP_CLOSE_SUBEXP:
1446       err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
1447       break;
1448
1449     case OP_BACK_REF:
1450       dfa->nexts[idx] = node->next->node_idx;
1451       if (node->token.type == OP_BACK_REF)
1452         err = re_node_set_init_1 (dfa->edests + idx, dfa->nexts[idx]);
1453       break;
1454
1455     default:
1456       assert (!IS_EPSILON_NODE (node->token.type));
1457       dfa->nexts[idx] = node->next->node_idx;
1458       break;
1459     }
1460
1461   return err;
1462 }
1463
1464 /* Duplicate the epsilon closure of the node ROOT_NODE.
1465    Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
1466    to their own constraint.  */
1467
1468 static reg_errcode_t
1469 internal_function
1470 duplicate_node_closure (re_dfa_t *dfa, Idx top_org_node, Idx top_clone_node,
1471                         Idx root_node, unsigned int init_constraint)
1472 {
1473   Idx org_node, clone_node;
1474   bool ok;
1475   unsigned int constraint = init_constraint;
1476   for (org_node = top_org_node, clone_node = top_clone_node;;)
1477     {
1478       Idx org_dest, clone_dest;
1479       if (dfa->nodes[org_node].type == OP_BACK_REF)
1480         {
1481           /* If the back reference epsilon-transit, its destination must
1482              also have the constraint.  Then duplicate the epsilon closure
1483              of the destination of the back reference, and store it in
1484              edests of the back reference.  */
1485           org_dest = dfa->nexts[org_node];
1486           re_node_set_empty (dfa->edests + clone_node);
1487           clone_dest = duplicate_node (dfa, org_dest, constraint);
1488           if (BE (clone_dest == REG_MISSING, 0))
1489             return REG_ESPACE;
1490           dfa->nexts[clone_node] = dfa->nexts[org_node];
1491           ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1492           if (BE (! ok, 0))
1493             return REG_ESPACE;
1494         }
1495       else if (dfa->edests[org_node].nelem == 0)
1496         {
1497           /* In case of the node can't epsilon-transit, don't duplicate the
1498              destination and store the original destination as the
1499              destination of the node.  */
1500           dfa->nexts[clone_node] = dfa->nexts[org_node];
1501           break;
1502         }
1503       else if (dfa->edests[org_node].nelem == 1)
1504         {
1505           /* In case of the node can epsilon-transit, and it has only one
1506              destination.  */
1507           org_dest = dfa->edests[org_node].elems[0];
1508           re_node_set_empty (dfa->edests + clone_node);
1509           /* If the node is root_node itself, it means the epsilon closure
1510              has a loop.  Then tie it to the destination of the root_node.  */
1511           if (org_node == root_node && clone_node != org_node)
1512             {
1513               ok = re_node_set_insert (dfa->edests + clone_node, org_dest);
1514               if (BE (! ok, 0))
1515                 return REG_ESPACE;
1516               break;
1517             }
1518           /* In case the node has another constraint, append it.  */
1519           constraint |= dfa->nodes[org_node].constraint;
1520           clone_dest = duplicate_node (dfa, org_dest, constraint);
1521           if (BE (clone_dest == REG_MISSING, 0))
1522             return REG_ESPACE;
1523           ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1524           if (BE (! ok, 0))
1525             return REG_ESPACE;
1526         }
1527       else /* dfa->edests[org_node].nelem == 2 */
1528         {
1529           /* In case of the node can epsilon-transit, and it has two
1530              destinations. In the bin_tree_t and DFA, that's '|' and '*'.   */
1531           org_dest = dfa->edests[org_node].elems[0];
1532           re_node_set_empty (dfa->edests + clone_node);
1533           /* Search for a duplicated node which satisfies the constraint.  */
1534           clone_dest = search_duplicated_node (dfa, org_dest, constraint);
1535           if (clone_dest == REG_MISSING)
1536             {
1537               /* There is no such duplicated node, create a new one.  */
1538               reg_errcode_t err;
1539               clone_dest = duplicate_node (dfa, org_dest, constraint);
1540               if (BE (clone_dest == REG_MISSING, 0))
1541                 return REG_ESPACE;
1542               ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1543               if (BE (! ok, 0))
1544                 return REG_ESPACE;
1545               err = duplicate_node_closure (dfa, org_dest, clone_dest,
1546                                             root_node, constraint);
1547               if (BE (err != REG_NOERROR, 0))
1548                 return err;
1549             }
1550           else
1551             {
1552               /* There is a duplicated node which satisfies the constraint,
1553                  use it to avoid infinite loop.  */
1554               ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1555               if (BE (! ok, 0))
1556                 return REG_ESPACE;
1557             }
1558
1559           org_dest = dfa->edests[org_node].elems[1];
1560           clone_dest = duplicate_node (dfa, org_dest, constraint);
1561           if (BE (clone_dest == REG_MISSING, 0))
1562             return REG_ESPACE;
1563           ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1564           if (BE (! ok, 0))
1565             return REG_ESPACE;
1566         }
1567       org_node = org_dest;
1568       clone_node = clone_dest;
1569     }
1570   return REG_NOERROR;
1571 }
1572
1573 /* Search for a node which is duplicated from the node ORG_NODE, and
1574    satisfies the constraint CONSTRAINT.  */
1575
1576 static Idx
1577 search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
1578                         unsigned int constraint)
1579 {
1580   Idx idx;
1581   for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
1582     {
1583       if (org_node == dfa->org_indices[idx]
1584           && constraint == dfa->nodes[idx].constraint)
1585         return idx; /* Found.  */
1586     }
1587   return REG_MISSING; /* Not found.  */
1588 }
1589
1590 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1591    Return the index of the new node, or REG_MISSING if insufficient storage is
1592    available.  */
1593
1594 static Idx
1595 duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint)
1596 {
1597   Idx dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
1598   if (BE (dup_idx != REG_MISSING, 1))
1599     {
1600       dfa->nodes[dup_idx].constraint = constraint;
1601       dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].constraint;
1602       dfa->nodes[dup_idx].duplicated = 1;
1603
1604       /* Store the index of the original node.  */
1605       dfa->org_indices[dup_idx] = org_idx;
1606     }
1607   return dup_idx;
1608 }
1609
1610 static reg_errcode_t
1611 calc_inveclosure (re_dfa_t *dfa)
1612 {
1613   Idx src, idx;
1614   bool ok;
1615   for (idx = 0; idx < dfa->nodes_len; ++idx)
1616     re_node_set_init_empty (dfa->inveclosures + idx);
1617
1618   for (src = 0; src < dfa->nodes_len; ++src)
1619     {
1620       Idx *elems = dfa->eclosures[src].elems;
1621       for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
1622         {
1623           ok = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
1624           if (BE (! ok, 0))
1625             return REG_ESPACE;
1626         }
1627     }
1628
1629   return REG_NOERROR;
1630 }
1631
1632 /* Calculate "eclosure" for all the node in DFA.  */
1633
1634 static reg_errcode_t
1635 calc_eclosure (re_dfa_t *dfa)
1636 {
1637   Idx node_idx;
1638   bool incomplete;
1639 #ifdef DEBUG
1640   assert (dfa->nodes_len > 0);
1641 #endif
1642   incomplete = false;
1643   /* For each nodes, calculate epsilon closure.  */
1644   for (node_idx = 0; ; ++node_idx)
1645     {
1646       reg_errcode_t err;
1647       re_node_set eclosure_elem;
1648       if (node_idx == dfa->nodes_len)
1649         {
1650           if (!incomplete)
1651             break;
1652           incomplete = false;
1653           node_idx = 0;
1654         }
1655
1656 #ifdef DEBUG
1657       assert (dfa->eclosures[node_idx].nelem != REG_MISSING);
1658 #endif
1659
1660       /* If we have already calculated, skip it.  */
1661       if (dfa->eclosures[node_idx].nelem != 0)
1662         continue;
1663       /* Calculate epsilon closure of `node_idx'.  */
1664       err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, true);
1665       if (BE (err != REG_NOERROR, 0))
1666         return err;
1667
1668       if (dfa->eclosures[node_idx].nelem == 0)
1669         {
1670           incomplete = true;
1671           re_node_set_free (&eclosure_elem);
1672         }
1673     }
1674   return REG_NOERROR;
1675 }
1676
1677 /* Calculate epsilon closure of NODE.  */
1678
1679 static reg_errcode_t
1680 calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, Idx node, bool root)
1681 {
1682   reg_errcode_t err;
1683   Idx i;
1684   re_node_set eclosure;
1685   bool ok;
1686   bool incomplete = false;
1687   err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1688   if (BE (err != REG_NOERROR, 0))
1689     return err;
1690
1691   /* This indicates that we are calculating this node now.
1692      We reference this value to avoid infinite loop.  */
1693   dfa->eclosures[node].nelem = REG_MISSING;
1694
1695   /* If the current node has constraints, duplicate all nodes
1696      since they must inherit the constraints.  */
1697   if (dfa->nodes[node].constraint
1698       && dfa->edests[node].nelem
1699       && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1700     {
1701       err = duplicate_node_closure (dfa, node, node, node,
1702                                     dfa->nodes[node].constraint);
1703       if (BE (err != REG_NOERROR, 0))
1704         return err;
1705     }
1706
1707   /* Expand each epsilon destination nodes.  */
1708   if (IS_EPSILON_NODE(dfa->nodes[node].type))
1709     for (i = 0; i < dfa->edests[node].nelem; ++i)
1710       {
1711         re_node_set eclosure_elem;
1712         Idx edest = dfa->edests[node].elems[i];
1713         /* If calculating the epsilon closure of `edest' is in progress,
1714            return intermediate result.  */
1715         if (dfa->eclosures[edest].nelem == REG_MISSING)
1716           {
1717             incomplete = true;
1718             continue;
1719           }
1720         /* If we haven't calculated the epsilon closure of `edest' yet,
1721            calculate now. Otherwise use calculated epsilon closure.  */
1722         if (dfa->eclosures[edest].nelem == 0)
1723           {
1724             err = calc_eclosure_iter (&eclosure_elem, dfa, edest, false);
1725             if (BE (err != REG_NOERROR, 0))
1726               return err;
1727           }
1728         else
1729           eclosure_elem = dfa->eclosures[edest];
1730         /* Merge the epsilon closure of `edest'.  */
1731         err = re_node_set_merge (&eclosure, &eclosure_elem);
1732         if (BE (err != REG_NOERROR, 0))
1733           return err;
1734         /* If the epsilon closure of `edest' is incomplete,
1735            the epsilon closure of this node is also incomplete.  */
1736         if (dfa->eclosures[edest].nelem == 0)
1737           {
1738             incomplete = true;
1739             re_node_set_free (&eclosure_elem);
1740           }
1741       }
1742
1743   /* An epsilon closure includes itself.  */
1744   ok = re_node_set_insert (&eclosure, node);
1745   if (BE (! ok, 0))
1746     return REG_ESPACE;
1747   if (incomplete && !root)
1748     dfa->eclosures[node].nelem = 0;
1749   else
1750     dfa->eclosures[node] = eclosure;
1751   *new_set = eclosure;
1752   return REG_NOERROR;
1753 }
1754 \f
1755 /* Functions for token which are used in the parser.  */
1756
1757 /* Fetch a token from INPUT.
1758    We must not use this function inside bracket expressions.  */
1759
1760 static void
1761 internal_function
1762 fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
1763 {
1764   re_string_skip_bytes (input, peek_token (result, input, syntax));
1765 }
1766
1767 /* Peek a token from INPUT, and return the length of the token.
1768    We must not use this function inside bracket expressions.  */
1769
1770 static int
1771 internal_function
1772 peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
1773 {
1774   unsigned char c;
1775
1776   if (re_string_eoi (input))
1777     {
1778       token->type = END_OF_RE;
1779       return 0;
1780     }
1781
1782   c = re_string_peek_byte (input, 0);
1783   token->opr.c = c;
1784
1785   token->word_char = 0;
1786 #ifdef RE_ENABLE_I18N
1787   token->mb_partial = 0;
1788   if (input->mb_cur_max > 1 &&
1789       !re_string_first_byte (input, re_string_cur_idx (input)))
1790     {
1791       token->type = CHARACTER;
1792       token->mb_partial = 1;
1793       return 1;
1794     }
1795 #endif
1796   if (c == '\\')
1797     {
1798       unsigned char c2;
1799       if (re_string_cur_idx (input) + 1 >= re_string_length (input))
1800         {
1801           token->type = BACK_SLASH;
1802           return 1;
1803         }
1804
1805       c2 = re_string_peek_byte_case (input, 1);
1806       token->opr.c = c2;
1807       token->type = CHARACTER;
1808 #ifdef RE_ENABLE_I18N
1809       if (input->mb_cur_max > 1)
1810         {
1811           wint_t wc = re_string_wchar_at (input,
1812                                           re_string_cur_idx (input) + 1);
1813           token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1814         }
1815       else
1816 #endif
1817         token->word_char = IS_WORD_CHAR (c2) != 0;
1818
1819       switch (c2)
1820         {
1821         case '|':
1822           if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))
1823             token->type = OP_ALT;
1824           break;
1825         case '1': case '2': case '3': case '4': case '5':
1826         case '6': case '7': case '8': case '9':
1827           if (!(syntax & RE_NO_BK_REFS))
1828             {
1829               token->type = OP_BACK_REF;
1830               token->opr.idx = c2 - '1';
1831             }
1832           break;
1833         case '<':
1834           if (!(syntax & RE_NO_GNU_OPS))
1835             {
1836               token->type = ANCHOR;
1837               token->opr.ctx_type = WORD_FIRST;
1838             }
1839           break;
1840         case '>':
1841           if (!(syntax & RE_NO_GNU_OPS))
1842             {
1843               token->type = ANCHOR;
1844               token->opr.ctx_type = WORD_LAST;
1845             }
1846           break;
1847         case 'b':
1848           if (!(syntax & RE_NO_GNU_OPS))
1849             {
1850               token->type = ANCHOR;
1851               token->opr.ctx_type = WORD_DELIM;
1852             }
1853           break;
1854         case 'B':
1855           if (!(syntax & RE_NO_GNU_OPS))
1856             {
1857               token->type = ANCHOR;
1858               token->opr.ctx_type = NOT_WORD_DELIM;
1859             }
1860           break;
1861         case 'w':
1862           if (!(syntax & RE_NO_GNU_OPS))
1863             token->type = OP_WORD;
1864           break;
1865         case 'W':
1866           if (!(syntax & RE_NO_GNU_OPS))
1867             token->type = OP_NOTWORD;
1868           break;
1869         case 's':
1870           if (!(syntax & RE_NO_GNU_OPS))
1871             token->type = OP_SPACE;
1872           break;
1873         case 'S':
1874           if (!(syntax & RE_NO_GNU_OPS))
1875             token->type = OP_NOTSPACE;
1876           break;
1877         case '`':
1878           if (!(syntax & RE_NO_GNU_OPS))
1879             {
1880               token->type = ANCHOR;
1881               token->opr.ctx_type = BUF_FIRST;
1882             }
1883           break;
1884         case '\'':
1885           if (!(syntax & RE_NO_GNU_OPS))
1886             {
1887               token->type = ANCHOR;
1888               token->opr.ctx_type = BUF_LAST;
1889             }
1890           break;
1891         case '(':
1892           if (!(syntax & RE_NO_BK_PARENS))
1893             token->type = OP_OPEN_SUBEXP;
1894           break;
1895         case ')':
1896           if (!(syntax & RE_NO_BK_PARENS))
1897             token->type = OP_CLOSE_SUBEXP;
1898           break;
1899         case '+':
1900           if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1901             token->type = OP_DUP_PLUS;
1902           break;
1903         case '?':
1904           if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1905             token->type = OP_DUP_QUESTION;
1906           break;
1907         case '{':
1908           if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1909             token->type = OP_OPEN_DUP_NUM;
1910           break;
1911         case '}':
1912           if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1913             token->type = OP_CLOSE_DUP_NUM;
1914           break;
1915         default:
1916           break;
1917         }
1918       return 2;
1919     }
1920
1921   token->type = CHARACTER;
1922 #ifdef RE_ENABLE_I18N
1923   if (input->mb_cur_max > 1)
1924     {
1925       wint_t wc = re_string_wchar_at (input, re_string_cur_idx (input));
1926       token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1927     }
1928   else
1929 #endif
1930     token->word_char = IS_WORD_CHAR (token->opr.c);
1931
1932   switch (c)
1933     {
1934     case '\n':
1935       if (syntax & RE_NEWLINE_ALT)
1936         token->type = OP_ALT;
1937       break;
1938     case '|':
1939       if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))
1940         token->type = OP_ALT;
1941       break;
1942     case '*':
1943       token->type = OP_DUP_ASTERISK;
1944       break;
1945     case '+':
1946       if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1947         token->type = OP_DUP_PLUS;
1948       break;
1949     case '?':
1950       if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1951         token->type = OP_DUP_QUESTION;
1952       break;
1953     case '{':
1954       if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1955         token->type = OP_OPEN_DUP_NUM;
1956       break;
1957     case '}':
1958       if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1959         token->type = OP_CLOSE_DUP_NUM;
1960       break;
1961     case '(':
1962       if (syntax & RE_NO_BK_PARENS)
1963         token->type = OP_OPEN_SUBEXP;
1964       break;
1965     case ')':
1966       if (syntax & RE_NO_BK_PARENS)
1967         token->type = OP_CLOSE_SUBEXP;
1968       break;
1969     case '[':
1970       token->type = OP_OPEN_BRACKET;
1971       break;
1972     case '.':
1973       token->type = OP_PERIOD;
1974       break;
1975     case '^':
1976       if (!(syntax & (RE_CONTEXT_INDEP_ANCHORS | RE_CARET_ANCHORS_HERE)) &&
1977           re_string_cur_idx (input) != 0)
1978         {
1979           char prev = re_string_peek_byte (input, -1);
1980           if (!(syntax & RE_NEWLINE_ALT) || prev != '\n')
1981             break;
1982         }
1983       token->type = ANCHOR;
1984       token->opr.ctx_type = LINE_FIRST;
1985       break;
1986     case '$':
1987       if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
1988           re_string_cur_idx (input) + 1 != re_string_length (input))
1989         {
1990           re_token_t next;
1991           re_string_skip_bytes (input, 1);
1992           peek_token (&next, input, syntax);
1993           re_string_skip_bytes (input, -1);
1994           if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
1995             break;
1996         }
1997       token->type = ANCHOR;
1998       token->opr.ctx_type = LINE_LAST;
1999       break;
2000     default:
2001       break;
2002     }
2003   return 1;
2004 }
2005
2006 /* Peek a token from INPUT, and return the length of the token.
2007    We must not use this function out of bracket expressions.  */
2008
2009 static int
2010 internal_function
2011 peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
2012 {
2013   unsigned char c;
2014   if (re_string_eoi (input))
2015     {
2016       token->type = END_OF_RE;
2017       return 0;
2018     }
2019   c = re_string_peek_byte (input, 0);
2020   token->opr.c = c;
2021
2022 #ifdef RE_ENABLE_I18N
2023   if (input->mb_cur_max > 1 &&
2024       !re_string_first_byte (input, re_string_cur_idx (input)))
2025     {
2026       token->type = CHARACTER;
2027       return 1;
2028     }
2029 #endif /* RE_ENABLE_I18N */
2030
2031   if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS)
2032       && re_string_cur_idx (input) + 1 < re_string_length (input))
2033     {
2034       /* In this case, '\' escape a character.  */
2035       unsigned char c2;
2036       re_string_skip_bytes (input, 1);
2037       c2 = re_string_peek_byte (input, 0);
2038       token->opr.c = c2;
2039       token->type = CHARACTER;
2040       return 1;
2041     }
2042   if (c == '[') /* '[' is a special char in a bracket exps.  */
2043     {
2044       unsigned char c2;
2045       int token_len;
2046       if (re_string_cur_idx (input) + 1 < re_string_length (input))
2047         c2 = re_string_peek_byte (input, 1);
2048       else
2049         c2 = 0;
2050       token->opr.c = c2;
2051       token_len = 2;
2052       switch (c2)
2053         {
2054         case '.':
2055           token->type = OP_OPEN_COLL_ELEM;
2056           break;
2057         case '=':
2058           token->type = OP_OPEN_EQUIV_CLASS;
2059           break;
2060         case ':':
2061           if (syntax & RE_CHAR_CLASSES)
2062             {
2063               token->type = OP_OPEN_CHAR_CLASS;
2064               break;
2065             }
2066           /* else fall through.  */
2067         default:
2068           token->type = CHARACTER;
2069           token->opr.c = c;
2070           token_len = 1;
2071           break;
2072         }
2073       return token_len;
2074     }
2075   switch (c)
2076     {
2077     case '-':
2078       token->type = OP_CHARSET_RANGE;
2079       break;
2080     case ']':
2081       token->type = OP_CLOSE_BRACKET;
2082       break;
2083     case '^':
2084       token->type = OP_NON_MATCH_LIST;
2085       break;
2086     default:
2087       token->type = CHARACTER;
2088     }
2089   return 1;
2090 }
2091 \f
2092 /* Functions for parser.  */
2093
2094 /* Entry point of the parser.
2095    Parse the regular expression REGEXP and return the structure tree.
2096    If an error is occured, ERR is set by error code, and return NULL.
2097    This function build the following tree, from regular expression <reg_exp>:
2098            CAT
2099            / \
2100           /   \
2101    <reg_exp>  EOR
2102
2103    CAT means concatenation.
2104    EOR means end of regular expression.  */
2105
2106 static bin_tree_t *
2107 parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
2108        reg_errcode_t *err)
2109 {
2110   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2111   bin_tree_t *tree, *eor, *root;
2112   re_token_t current_token;
2113   dfa->syntax = syntax;
2114   fetch_token (&current_token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2115   tree = parse_reg_exp (regexp, preg, &current_token, syntax, 0, err);
2116   if (BE (*err != REG_NOERROR && tree == NULL, 0))
2117     return NULL;
2118   eor = create_tree (dfa, NULL, NULL, END_OF_RE);
2119   if (tree != NULL)
2120     root = create_tree (dfa, tree, eor, CONCAT);
2121   else
2122     root = eor;
2123   if (BE (eor == NULL || root == NULL, 0))
2124     {
2125       *err = REG_ESPACE;
2126       return NULL;
2127     }
2128   return root;
2129 }
2130
2131 /* This function build the following tree, from regular expression
2132    <branch1>|<branch2>:
2133            ALT
2134            / \
2135           /   \
2136    <branch1> <branch2>
2137
2138    ALT means alternative, which represents the operator `|'.  */
2139
2140 static bin_tree_t *
2141 parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2142                reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2143 {
2144   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2145   bin_tree_t *tree, *branch = NULL;
2146   tree = parse_branch (regexp, preg, token, syntax, nest, err);
2147   if (BE (*err != REG_NOERROR && tree == NULL, 0))
2148     return NULL;
2149
2150   while (token->type == OP_ALT)
2151     {
2152       fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2153       if (token->type != OP_ALT && token->type != END_OF_RE
2154           && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2155         {
2156           branch = parse_branch (regexp, preg, token, syntax, nest, err);
2157           if (BE (*err != REG_NOERROR && branch == NULL, 0))
2158             return NULL;
2159         }
2160       else
2161         branch = NULL;
2162       tree = create_tree (dfa, tree, branch, OP_ALT);
2163       if (BE (tree == NULL, 0))
2164         {
2165           *err = REG_ESPACE;
2166           return NULL;
2167         }
2168     }
2169   return tree;
2170 }
2171
2172 /* This function build the following tree, from regular expression
2173    <exp1><exp2>:
2174         CAT
2175         / \
2176        /   \
2177    <exp1> <exp2>
2178
2179    CAT means concatenation.  */
2180
2181 static bin_tree_t *
2182 parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
2183               reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2184 {
2185   bin_tree_t *tree, *expr;
2186   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2187   tree = parse_expression (regexp, preg, token, syntax, nest, err);
2188   if (BE (*err != REG_NOERROR && tree == NULL, 0))
2189     return NULL;
2190
2191   while (token->type != OP_ALT && token->type != END_OF_RE
2192          && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2193     {
2194       expr = parse_expression (regexp, preg, token, syntax, nest, err);
2195       if (BE (*err != REG_NOERROR && expr == NULL, 0))
2196         {
2197           return NULL;
2198         }
2199       if (tree != NULL && expr != NULL)
2200         {
2201           tree = create_tree (dfa, tree, expr, CONCAT);
2202           if (tree == NULL)
2203             {
2204               *err = REG_ESPACE;
2205               return NULL;
2206             }
2207         }
2208       else if (tree == NULL)
2209         tree = expr;
2210       /* Otherwise expr == NULL, we don't need to create new tree.  */
2211     }
2212   return tree;
2213 }
2214
2215 /* This function build the following tree, from regular expression a*:
2216          *
2217          |
2218          a
2219 */
2220
2221 static bin_tree_t *
2222 parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
2223                   reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2224 {
2225   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2226   bin_tree_t *tree;
2227   switch (token->type)
2228     {
2229     case CHARACTER:
2230       tree = create_token_tree (dfa, NULL, NULL, token);
2231       if (BE (tree == NULL, 0))
2232         {
2233           *err = REG_ESPACE;
2234           return NULL;
2235         }
2236 #ifdef RE_ENABLE_I18N
2237       if (dfa->mb_cur_max > 1)
2238         {
2239           while (!re_string_eoi (regexp)
2240                  && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
2241             {
2242               bin_tree_t *mbc_remain;
2243               fetch_token (token, regexp, syntax);
2244               mbc_remain = create_token_tree (dfa, NULL, NULL, token);
2245               tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2246               if (BE (mbc_remain == NULL || tree == NULL, 0))
2247                 {
2248                   *err = REG_ESPACE;
2249                   return NULL;
2250                 }
2251             }
2252         }
2253 #endif
2254       break;
2255     case OP_OPEN_SUBEXP:
2256       tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2257       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2258         return NULL;
2259       break;
2260     case OP_OPEN_BRACKET:
2261       tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2262       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2263         return NULL;
2264       break;
2265     case OP_BACK_REF:
2266       if (!BE (dfa->completed_bkref_map & (1 << token->opr.idx), 1))
2267         {
2268           *err = REG_ESUBREG;
2269           return NULL;
2270         }
2271       dfa->used_bkref_map |= 1 << token->opr.idx;
2272       tree = create_token_tree (dfa, NULL, NULL, token);
2273       if (BE (tree == NULL, 0))
2274         {
2275           *err = REG_ESPACE;
2276           return NULL;
2277         }
2278       ++dfa->nbackref;
2279       dfa->has_mb_node = 1;
2280       break;
2281     case OP_OPEN_DUP_NUM:
2282       if (syntax & RE_CONTEXT_INVALID_DUP)
2283         {
2284           *err = REG_BADRPT;
2285           return NULL;
2286         }
2287       /* FALLTHROUGH */
2288     case OP_DUP_ASTERISK:
2289     case OP_DUP_PLUS:
2290     case OP_DUP_QUESTION:
2291       if (syntax & RE_CONTEXT_INVALID_OPS)
2292         {
2293           *err = REG_BADRPT;
2294           return NULL;
2295         }
2296       else if (syntax & RE_CONTEXT_INDEP_OPS)
2297         {
2298           fetch_token (token, regexp, syntax);
2299           return parse_expression (regexp, preg, token, syntax, nest, err);
2300         }
2301       /* else fall through  */
2302     case OP_CLOSE_SUBEXP:
2303       if ((token->type == OP_CLOSE_SUBEXP) &&
2304           !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))
2305         {
2306           *err = REG_ERPAREN;
2307           return NULL;
2308         }
2309       /* else fall through  */
2310     case OP_CLOSE_DUP_NUM:
2311       /* We treat it as a normal character.  */
2312
2313       /* Then we can these characters as normal characters.  */
2314       token->type = CHARACTER;
2315       /* mb_partial and word_char bits should be initialized already
2316          by peek_token.  */
2317       tree = create_token_tree (dfa, NULL, NULL, token);
2318       if (BE (tree == NULL, 0))
2319         {
2320           *err = REG_ESPACE;
2321           return NULL;
2322         }
2323       break;
2324     case ANCHOR:
2325       if ((token->opr.ctx_type
2326            & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST))
2327           && dfa->word_ops_used == 0)
2328         init_word_char (dfa);
2329       if (token->opr.ctx_type == WORD_DELIM
2330           || token->opr.ctx_type == NOT_WORD_DELIM)
2331         {
2332           bin_tree_t *tree_first, *tree_last;
2333           if (token->opr.ctx_type == WORD_DELIM)
2334             {
2335               token->opr.ctx_type = WORD_FIRST;
2336               tree_first = create_token_tree (dfa, NULL, NULL, token);
2337               token->opr.ctx_type = WORD_LAST;
2338             }
2339           else
2340             {
2341               token->opr.ctx_type = INSIDE_WORD;
2342               tree_first = create_token_tree (dfa, NULL, NULL, token);
2343               token->opr.ctx_type = INSIDE_NOTWORD;
2344             }
2345           tree_last = create_token_tree (dfa, NULL, NULL, token);
2346           tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2347           if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
2348             {
2349               *err = REG_ESPACE;
2350               return NULL;
2351             }
2352         }
2353       else
2354         {
2355           tree = create_token_tree (dfa, NULL, NULL, token);
2356           if (BE (tree == NULL, 0))
2357             {
2358               *err = REG_ESPACE;
2359               return NULL;
2360             }
2361         }
2362       /* We must return here, since ANCHORs can't be followed
2363          by repetition operators.
2364          eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
2365              it must not be "<ANCHOR(^)><REPEAT(*)>".  */
2366       fetch_token (token, regexp, syntax);
2367       return tree;
2368     case OP_PERIOD:
2369       tree = create_token_tree (dfa, NULL, NULL, token);
2370       if (BE (tree == NULL, 0))
2371         {
2372           *err = REG_ESPACE;
2373           return NULL;
2374         }
2375       if (dfa->mb_cur_max > 1)
2376         dfa->has_mb_node = 1;
2377       break;
2378     case OP_WORD:
2379     case OP_NOTWORD:
2380       tree = build_charclass_op (dfa, regexp->trans,
2381                                  (const unsigned char *) "alnum",
2382                                  (const unsigned char *) "_",
2383                                  token->type == OP_NOTWORD, err);
2384       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2385         return NULL;
2386       break;
2387     case OP_SPACE:
2388     case OP_NOTSPACE:
2389       tree = build_charclass_op (dfa, regexp->trans,
2390                                  (const unsigned char *) "space",
2391                                  (const unsigned char *) "",
2392                                  token->type == OP_NOTSPACE, err);
2393       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2394         return NULL;
2395       break;
2396     case OP_ALT:
2397     case END_OF_RE:
2398       return NULL;
2399     case BACK_SLASH:
2400       *err = REG_EESCAPE;
2401       return NULL;
2402     default:
2403       /* Must not happen?  */
2404 #ifdef DEBUG
2405       assert (0);
2406 #endif
2407       return NULL;
2408     }
2409   fetch_token (token, regexp, syntax);
2410
2411   while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
2412          || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
2413     {
2414       tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2415       if (BE (*err != REG_NOERROR && tree == NULL, 0))
2416         return NULL;
2417       /* In BRE consecutive duplications are not allowed.  */
2418       if ((syntax & RE_CONTEXT_INVALID_DUP)
2419           && (token->type == OP_DUP_ASTERISK
2420               || token->type == OP_OPEN_DUP_NUM))
2421         {
2422           *err = REG_BADRPT;
2423           return NULL;
2424         }
2425     }
2426
2427   return tree;
2428 }
2429
2430 /* This function build the following tree, from regular expression
2431    (<reg_exp>):
2432          SUBEXP
2433             |
2434         <reg_exp>
2435 */
2436
2437 static bin_tree_t *
2438 parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2439                reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2440 {
2441   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2442   bin_tree_t *tree;
2443   size_t cur_nsub;
2444   cur_nsub = preg->re_nsub++;
2445
2446   fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2447
2448   /* The subexpression may be a null string.  */
2449   if (token->type == OP_CLOSE_SUBEXP)
2450     tree = NULL;
2451   else
2452     {
2453       tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2454       if (BE (*err == REG_NOERROR && token->type != OP_CLOSE_SUBEXP, 0))
2455         *err = REG_EPAREN;
2456       if (BE (*err != REG_NOERROR, 0))
2457         return NULL;
2458     }
2459
2460   if (cur_nsub <= '9' - '1')
2461     dfa->completed_bkref_map |= 1 << cur_nsub;
2462
2463   tree = create_tree (dfa, tree, NULL, SUBEXP);
2464   if (BE (tree == NULL, 0))
2465     {
2466       *err = REG_ESPACE;
2467       return NULL;
2468     }
2469   tree->token.opr.idx = cur_nsub;
2470   return tree;
2471 }
2472
2473 /* This function parse repetition operators like "*", "+", "{1,3}" etc.  */
2474
2475 static bin_tree_t *
2476 parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
2477               re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
2478 {
2479   bin_tree_t *tree = NULL, *old_tree = NULL;
2480   Idx i, start, end, start_idx = re_string_cur_idx (regexp);
2481   re_token_t start_token = *token;
2482
2483   if (token->type == OP_OPEN_DUP_NUM)
2484     {
2485       end = 0;
2486       start = fetch_number (regexp, token, syntax);
2487       if (start == REG_MISSING)
2488         {
2489           if (token->type == CHARACTER && token->opr.c == ',')
2490             start = 0; /* We treat "{,m}" as "{0,m}".  */
2491           else
2492             {
2493               *err = REG_BADBR; /* <re>{} is invalid.  */
2494               return NULL;
2495             }
2496         }
2497       if (BE (start != REG_ERROR, 1))
2498         {
2499           /* We treat "{n}" as "{n,n}".  */
2500           end = ((token->type == OP_CLOSE_DUP_NUM) ? start
2501                  : ((token->type == CHARACTER && token->opr.c == ',')
2502                     ? fetch_number (regexp, token, syntax) : REG_ERROR));
2503         }
2504       if (BE (start == REG_ERROR || end == REG_ERROR, 0))
2505         {
2506           /* Invalid sequence.  */
2507           if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
2508             {
2509               if (token->type == END_OF_RE)
2510                 *err = REG_EBRACE;
2511               else
2512                 *err = REG_BADBR;
2513
2514               return NULL;
2515             }
2516
2517           /* If the syntax bit is set, rollback.  */
2518           re_string_set_index (regexp, start_idx);
2519           *token = start_token;
2520           token->type = CHARACTER;
2521           /* mb_partial and word_char bits should be already initialized by
2522              peek_token.  */
2523           return elem;
2524         }
2525
2526       if (BE ((end != REG_MISSING && start > end)
2527               || token->type != OP_CLOSE_DUP_NUM, 0))
2528         {
2529           /* First number greater than second.  */
2530           *err = REG_BADBR;
2531           return NULL;
2532         }
2533     }
2534   else
2535     {
2536       start = (token->type == OP_DUP_PLUS) ? 1 : 0;
2537       end = (token->type == OP_DUP_QUESTION) ? 1 : REG_MISSING;
2538     }
2539
2540   fetch_token (token, regexp, syntax);
2541
2542   if (BE (elem == NULL, 0))
2543     return NULL;
2544   if (BE (start == 0 && end == 0, 0))
2545     {
2546       postorder (elem, free_tree, NULL);
2547       return NULL;
2548     }
2549
2550   /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}".  */
2551   if (BE (start > 0, 0))
2552     {
2553       tree = elem;
2554       for (i = 2; i <= start; ++i)
2555         {
2556           elem = duplicate_tree (elem, dfa);
2557           tree = create_tree (dfa, tree, elem, CONCAT);
2558           if (BE (elem == NULL || tree == NULL, 0))
2559             goto parse_dup_op_espace;
2560         }
2561
2562       if (start == end)
2563         return tree;
2564
2565       /* Duplicate ELEM before it is marked optional.  */
2566       elem = duplicate_tree (elem, dfa);
2567       old_tree = tree;
2568     }
2569   else
2570     old_tree = NULL;
2571
2572   if (elem->token.type == SUBEXP)
2573     postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
2574
2575   tree = create_tree (dfa, elem, NULL,
2576                       (end == REG_MISSING ? OP_DUP_ASTERISK : OP_ALT));
2577   if (BE (tree == NULL, 0))
2578     goto parse_dup_op_espace;
2579
2580   /* This loop is actually executed only when end != REG_MISSING,
2581      to rewrite <re>{0,n} as (<re>(<re>...<re>?)?)?...  We have
2582      already created the start+1-th copy.  */
2583   if ((Idx) -1 < 0 || end != REG_MISSING)
2584     for (i = start + 2; i <= end; ++i)
2585       {
2586         elem = duplicate_tree (elem, dfa);
2587         tree = create_tree (dfa, tree, elem, CONCAT);
2588         if (BE (elem == NULL || tree == NULL, 0))
2589           goto parse_dup_op_espace;
2590
2591         tree = create_tree (dfa, tree, NULL, OP_ALT);
2592         if (BE (tree == NULL, 0))
2593           goto parse_dup_op_espace;
2594       }
2595
2596   if (old_tree)
2597     tree = create_tree (dfa, old_tree, tree, CONCAT);
2598
2599   return tree;
2600
2601  parse_dup_op_espace:
2602   *err = REG_ESPACE;
2603   return NULL;
2604 }
2605
2606 /* Size of the names for collating symbol/equivalence_class/character_class.
2607    I'm not sure, but maybe enough.  */
2608 #define BRACKET_NAME_BUF_SIZE 32
2609
2610 #ifndef _LIBC
2611   /* Local function for parse_bracket_exp only used in case of NOT _LIBC.
2612      Build the range expression which starts from START_ELEM, and ends
2613      at END_ELEM.  The result are written to MBCSET and SBCSET.
2614      RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2615      mbcset->range_ends, is a pointer argument sinse we may
2616      update it.  */
2617
2618 static reg_errcode_t
2619 internal_function
2620 # ifdef RE_ENABLE_I18N
2621 build_range_exp (bitset_t sbcset, re_charset_t *mbcset, Idx *range_alloc,
2622                  bracket_elem_t *start_elem, bracket_elem_t *end_elem)
2623 # else /* not RE_ENABLE_I18N */
2624 build_range_exp (bitset_t sbcset, bracket_elem_t *start_elem,
2625                  bracket_elem_t *end_elem)
2626 # endif /* not RE_ENABLE_I18N */
2627 {
2628   unsigned int start_ch, end_ch;
2629   /* Equivalence Classes and Character Classes can't be a range start/end.  */
2630   if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2631           || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2632           0))
2633     return REG_ERANGE;
2634
2635   /* We can handle no multi character collating elements without libc
2636      support.  */
2637   if (BE ((start_elem->type == COLL_SYM
2638            && strlen ((char *) start_elem->opr.name) > 1)
2639           || (end_elem->type == COLL_SYM
2640               && strlen ((char *) end_elem->opr.name) > 1), 0))
2641     return REG_ECOLLATE;
2642
2643 # ifdef RE_ENABLE_I18N
2644   {
2645     wchar_t wc;
2646     wint_t start_wc;
2647     wint_t end_wc;
2648     wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
2649
2650     start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
2651                 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2652                    : 0));
2653     end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
2654               : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2655                  : 0));
2656     start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
2657                 ? __btowc (start_ch) : start_elem->opr.wch);
2658     end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
2659               ? __btowc (end_ch) : end_elem->opr.wch);
2660     if (start_wc == WEOF || end_wc == WEOF)
2661       return REG_ECOLLATE;
2662     cmp_buf[0] = start_wc;
2663     cmp_buf[4] = end_wc;
2664     if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
2665       return REG_ERANGE;
2666
2667     /* Got valid collation sequence values, add them as a new entry.
2668        However, for !_LIBC we have no collation elements: if the
2669        character set is single byte, the single byte character set
2670        that we build below suffices.  parse_bracket_exp passes
2671        no MBCSET if dfa->mb_cur_max == 1.  */
2672     if (mbcset)
2673       {
2674         /* Check the space of the arrays.  */
2675         if (BE (*range_alloc == mbcset->nranges, 0))
2676           {
2677             /* There is not enough space, need realloc.  */
2678             wchar_t *new_array_start, *new_array_end;
2679             Idx new_nranges;
2680
2681             /* +1 in case of mbcset->nranges is 0.  */
2682             new_nranges = 2 * mbcset->nranges + 1;
2683             /* Use realloc since mbcset->range_starts and mbcset->range_ends
2684                are NULL if *range_alloc == 0.  */
2685             new_array_start = re_realloc (mbcset->range_starts, wchar_t,
2686                                           new_nranges);
2687             new_array_end = re_realloc (mbcset->range_ends, wchar_t,
2688                                         new_nranges);
2689
2690             if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2691               return REG_ESPACE;
2692
2693             mbcset->range_starts = new_array_start;
2694             mbcset->range_ends = new_array_end;
2695             *range_alloc = new_nranges;
2696           }
2697
2698         mbcset->range_starts[mbcset->nranges] = start_wc;
2699         mbcset->range_ends[mbcset->nranges++] = end_wc;
2700       }
2701
2702     /* Build the table for single byte characters.  */
2703     for (wc = 0; wc < SBC_MAX; ++wc)
2704       {
2705         cmp_buf[2] = wc;
2706         if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
2707             && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
2708           bitset_set (sbcset, wc);
2709       }
2710   }
2711 # else /* not RE_ENABLE_I18N */
2712   {
2713     unsigned int ch;
2714     start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch
2715                 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2716                    : 0));
2717     end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch
2718               : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2719                  : 0));
2720     if (start_ch > end_ch)
2721       return REG_ERANGE;
2722     /* Build the table for single byte characters.  */
2723     for (ch = 0; ch < SBC_MAX; ++ch)
2724       if (start_ch <= ch  && ch <= end_ch)
2725         bitset_set (sbcset, ch);
2726   }
2727 # endif /* not RE_ENABLE_I18N */
2728   return REG_NOERROR;
2729 }
2730 #endif /* not _LIBC */
2731
2732 #ifndef _LIBC
2733 /* Helper function for parse_bracket_exp only used in case of NOT _LIBC..
2734    Build the collating element which is represented by NAME.
2735    The result are written to MBCSET and SBCSET.
2736    COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2737    pointer argument since we may update it.  */
2738
2739 static reg_errcode_t
2740 internal_function
2741 build_collating_symbol (bitset_t sbcset,
2742 # ifdef RE_ENABLE_I18N
2743                         re_charset_t *mbcset, Idx *coll_sym_alloc,
2744 # endif
2745                         const unsigned char *name)
2746 {
2747   size_t name_len = strlen ((const char *) name);
2748   if (BE (name_len != 1, 0))
2749     return REG_ECOLLATE;
2750   else
2751     {
2752       bitset_set (sbcset, name[0]);
2753       return REG_NOERROR;
2754     }
2755 }
2756 #endif /* not _LIBC */
2757
2758 /* This function parse bracket expression like "[abc]", "[a-c]",
2759    "[[.a-a.]]" etc.  */
2760
2761 static bin_tree_t *
2762 parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
2763                    reg_syntax_t syntax, reg_errcode_t *err)
2764 {
2765 #ifdef _LIBC
2766   const unsigned char *collseqmb;
2767   const char *collseqwc;
2768   uint32_t nrules;
2769   int32_t table_size;
2770   const int32_t *symb_table;
2771   const unsigned char *extra;
2772
2773   /* Local function for parse_bracket_exp used in _LIBC environement.
2774      Seek the collating symbol entry correspondings to NAME.
2775      Return the index of the symbol in the SYMB_TABLE.  */
2776
2777   auto inline int32_t
2778   __attribute ((always_inline))
2779   seek_collating_symbol_entry (name, name_len)
2780          const unsigned char *name;
2781          size_t name_len;
2782     {
2783       int32_t hash = elem_hash ((const char *) name, name_len);
2784       int32_t elem = hash % table_size;
2785       if (symb_table[2 * elem] != 0)
2786         {
2787           int32_t second = hash % (table_size - 2) + 1;
2788
2789           do
2790             {
2791               /* First compare the hashing value.  */
2792               if (symb_table[2 * elem] == hash
2793                   /* Compare the length of the name.  */
2794                   && name_len == extra[symb_table[2 * elem + 1]]
2795                   /* Compare the name.  */
2796                   && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
2797                              name_len) == 0)
2798                 {
2799                   /* Yep, this is the entry.  */
2800                   break;
2801                 }
2802
2803               /* Next entry.  */
2804               elem += second;
2805             }
2806           while (symb_table[2 * elem] != 0);
2807         }
2808       return elem;
2809     }
2810
2811   /* Local function for parse_bracket_exp used in _LIBC environment.
2812      Look up the collation sequence value of BR_ELEM.
2813      Return the value if succeeded, UINT_MAX otherwise.  */
2814
2815   auto inline unsigned int
2816   __attribute ((always_inline))
2817   lookup_collation_sequence_value (br_elem)
2818          bracket_elem_t *br_elem;
2819     {
2820       if (br_elem->type == SB_CHAR)
2821         {
2822           /*
2823           if (MB_CUR_MAX == 1)
2824           */
2825           if (nrules == 0)
2826             return collseqmb[br_elem->opr.ch];
2827           else
2828             {
2829               wint_t wc = __btowc (br_elem->opr.ch);
2830               return __collseq_table_lookup (collseqwc, wc);
2831             }
2832         }
2833       else if (br_elem->type == MB_CHAR)
2834         {
2835           if (nrules != 0)
2836             return __collseq_table_lookup (collseqwc, br_elem->opr.wch);
2837         }
2838       else if (br_elem->type == COLL_SYM)
2839         {
2840           size_t sym_name_len = strlen ((char *) br_elem->opr.name);
2841           if (nrules != 0)
2842             {
2843               int32_t elem, idx;
2844               elem = seek_collating_symbol_entry (br_elem->opr.name,
2845                                                   sym_name_len);
2846               if (symb_table[2 * elem] != 0)
2847                 {
2848                   /* We found the entry.  */
2849                   idx = symb_table[2 * elem + 1];
2850                   /* Skip the name of collating element name.  */
2851                   idx += 1 + extra[idx];
2852                   /* Skip the byte sequence of the collating element.  */
2853                   idx += 1 + extra[idx];
2854                   /* Adjust for the alignment.  */
2855                   idx = (idx + 3) & ~3;
2856                   /* Skip the multibyte collation sequence value.  */
2857                   idx += sizeof (unsigned int);
2858                   /* Skip the wide char sequence of the collating element.  */
2859                   idx += sizeof (unsigned int) *
2860                     (1 + *(unsigned int *) (extra + idx));
2861                   /* Return the collation sequence value.  */
2862                   return *(unsigned int *) (extra + idx);
2863                 }
2864               else if (symb_table[2 * elem] == 0 && sym_name_len == 1)
2865                 {
2866                   /* No valid character.  Match it as a single byte
2867                      character.  */
2868                   return collseqmb[br_elem->opr.name[0]];
2869                 }
2870             }
2871           else if (sym_name_len == 1)
2872             return collseqmb[br_elem->opr.name[0]];
2873         }
2874       return UINT_MAX;
2875     }
2876
2877   /* Local function for parse_bracket_exp used in _LIBC environement.
2878      Build the range expression which starts from START_ELEM, and ends
2879      at END_ELEM.  The result are written to MBCSET and SBCSET.
2880      RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2881      mbcset->range_ends, is a pointer argument sinse we may
2882      update it.  */
2883
2884   auto inline reg_errcode_t
2885   __attribute ((always_inline))
2886   build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
2887          re_charset_t *mbcset;
2888          Idx *range_alloc;
2889          bitset_t sbcset;
2890          bracket_elem_t *start_elem, *end_elem;
2891     {
2892       unsigned int ch;
2893       uint32_t start_collseq;
2894       uint32_t end_collseq;
2895
2896       /* Equivalence Classes and Character Classes can't be a range
2897          start/end.  */
2898       if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2899               || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2900               0))
2901         return REG_ERANGE;
2902
2903       start_collseq = lookup_collation_sequence_value (start_elem);
2904       end_collseq = lookup_collation_sequence_value (end_elem);
2905       /* Check start/end collation sequence values.  */
2906       if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))
2907         return REG_ECOLLATE;
2908       if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))
2909         return REG_ERANGE;
2910
2911       /* Got valid collation sequence values, add them as a new entry.
2912          However, if we have no collation elements, and the character set
2913          is single byte, the single byte character set that we
2914          build below suffices. */
2915       if (nrules > 0 || dfa->mb_cur_max > 1)
2916         {
2917           /* Check the space of the arrays.  */
2918           if (BE (*range_alloc == mbcset->nranges, 0))
2919             {
2920               /* There is not enough space, need realloc.  */
2921               uint32_t *new_array_start;
2922               uint32_t *new_array_end;
2923               Idx new_nranges;
2924
2925               /* +1 in case of mbcset->nranges is 0.  */
2926               new_nranges = 2 * mbcset->nranges + 1;
2927               new_array_start = re_realloc (mbcset->range_starts, uint32_t,
2928                                             new_nranges);
2929               new_array_end = re_realloc (mbcset->range_ends, uint32_t,
2930                                           new_nranges);
2931
2932               if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2933                 return REG_ESPACE;
2934
2935               mbcset->range_starts = new_array_start;
2936               mbcset->range_ends = new_array_end;
2937               *range_alloc = new_nranges;
2938             }
2939
2940           mbcset->range_starts[mbcset->nranges] = start_collseq;
2941           mbcset->range_ends[mbcset->nranges++] = end_collseq;
2942         }
2943
2944       /* Build the table for single byte characters.  */
2945       for (ch = 0; ch < SBC_MAX; ch++)
2946         {
2947           uint32_t ch_collseq;
2948           /*
2949           if (MB_CUR_MAX == 1)
2950           */
2951           if (nrules == 0)
2952             ch_collseq = collseqmb[ch];
2953           else
2954             ch_collseq = __collseq_table_lookup (collseqwc, __btowc (ch));
2955           if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
2956             bitset_set (sbcset, ch);
2957         }
2958       return REG_NOERROR;
2959     }
2960
2961   /* Local function for parse_bracket_exp used in _LIBC environement.
2962      Build the collating element which is represented by NAME.
2963      The result are written to MBCSET and SBCSET.
2964      COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2965      pointer argument sinse we may update it.  */
2966
2967   auto inline reg_errcode_t
2968   __attribute ((always_inline))
2969   build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
2970          re_charset_t *mbcset;
2971          Idx *coll_sym_alloc;
2972          bitset_t sbcset;
2973          const unsigned char *name;
2974     {
2975       int32_t elem, idx;
2976       size_t name_len = strlen ((const char *) name);
2977       if (nrules != 0)
2978         {
2979           elem = seek_collating_symbol_entry (name, name_len);
2980           if (symb_table[2 * elem] != 0)
2981             {
2982               /* We found the entry.  */
2983               idx = symb_table[2 * elem + 1];
2984               /* Skip the name of collating element name.  */
2985               idx += 1 + extra[idx];
2986             }
2987           else if (symb_table[2 * elem] == 0 && name_len == 1)
2988             {
2989               /* No valid character, treat it as a normal
2990                  character.  */
2991               bitset_set (sbcset, name[0]);
2992               return REG_NOERROR;
2993             }
2994           else
2995             return REG_ECOLLATE;
2996
2997           /* Got valid collation sequence, add it as a new entry.  */
2998           /* Check the space of the arrays.  */
2999           if (BE (*coll_sym_alloc == mbcset->ncoll_syms, 0))
3000             {
3001               /* Not enough, realloc it.  */
3002               /* +1 in case of mbcset->ncoll_syms is 0.  */
3003               Idx new_coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
3004               /* Use realloc since mbcset->coll_syms is NULL
3005                  if *alloc == 0.  */
3006               int32_t *new_coll_syms = re_realloc (mbcset->coll_syms, int32_t,
3007                                                    new_coll_sym_alloc);
3008               if (BE (new_coll_syms == NULL, 0))
3009                 return REG_ESPACE;
3010               mbcset->coll_syms = new_coll_syms;
3011               *coll_sym_alloc = new_coll_sym_alloc;
3012             }
3013           mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
3014           return REG_NOERROR;
3015         }
3016       else
3017         {
3018           if (BE (name_len != 1, 0))
3019             return REG_ECOLLATE;
3020           else
3021             {
3022               bitset_set (sbcset, name[0]);
3023               return REG_NOERROR;
3024             }
3025         }
3026     }
3027 #endif
3028
3029   re_token_t br_token;
3030   re_bitset_ptr_t sbcset;
3031 #ifdef RE_ENABLE_I18N
3032   re_charset_t *mbcset;
3033   Idx coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
3034   Idx equiv_class_alloc = 0, char_class_alloc = 0;
3035 #endif /* not RE_ENABLE_I18N */
3036   bool non_match = false;
3037   bin_tree_t *work_tree;
3038   int token_len;
3039   bool first_round = true;
3040 #ifdef _LIBC
3041   collseqmb = (const unsigned char *)
3042     _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3043   nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3044   if (nrules)
3045     {
3046       /*
3047       if (MB_CUR_MAX > 1)
3048       */
3049       collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3050       table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
3051       symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3052                                                   _NL_COLLATE_SYMB_TABLEMB);
3053       extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3054                                                    _NL_COLLATE_SYMB_EXTRAMB);
3055     }
3056 #endif
3057   sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
3058 #ifdef RE_ENABLE_I18N
3059   mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3060 #endif /* RE_ENABLE_I18N */
3061 #ifdef RE_ENABLE_I18N
3062   if (BE (sbcset == NULL || mbcset == NULL, 0))
3063 #else
3064   if (BE (sbcset == NULL, 0))
3065 #endif /* RE_ENABLE_I18N */
3066     {
3067       *err = REG_ESPACE;
3068       return NULL;
3069     }
3070
3071   token_len = peek_token_bracket (token, regexp, syntax);
3072   if (BE (token->type == END_OF_RE, 0))
3073     {
3074       *err = REG_BADPAT;
3075       goto parse_bracket_exp_free_return;
3076     }
3077   if (token->type == OP_NON_MATCH_LIST)
3078     {
3079 #ifdef RE_ENABLE_I18N
3080       mbcset->non_match = 1;
3081 #endif /* not RE_ENABLE_I18N */
3082       non_match = true;
3083       if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
3084         bitset_set (sbcset, '\n');
3085       re_string_skip_bytes (regexp, token_len); /* Skip a token.  */
3086       token_len = peek_token_bracket (token, regexp, syntax);
3087       if (BE (token->type == END_OF_RE, 0))
3088         {
3089           *err = REG_BADPAT;
3090           goto parse_bracket_exp_free_return;
3091         }
3092     }
3093
3094   /* We treat the first ']' as a normal character.  */
3095   if (token->type == OP_CLOSE_BRACKET)
3096     token->type = CHARACTER;
3097
3098   while (1)
3099     {
3100       bracket_elem_t start_elem, end_elem;
3101       unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
3102       unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
3103       reg_errcode_t ret;
3104       int token_len2 = 0;
3105       bool is_range_exp = false;
3106       re_token_t token2;
3107
3108       start_elem.opr.name = start_name_buf;
3109       ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
3110                                    syntax, first_round);
3111       if (BE (ret != REG_NOERROR, 0))
3112         {
3113           *err = ret;
3114           goto parse_bracket_exp_free_return;
3115         }
3116       first_round = false;
3117
3118       /* Get information about the next token.  We need it in any case.  */
3119       token_len = peek_token_bracket (token, regexp, syntax);
3120
3121       /* Do not check for ranges if we know they are not allowed.  */
3122       if (start_elem.type != CHAR_CLASS && start_elem.type != EQUIV_CLASS)
3123         {
3124           if (BE (token->type == END_OF_RE, 0))
3125             {
3126               *err = REG_EBRACK;
3127               goto parse_bracket_exp_free_return;
3128             }
3129           if (token->type == OP_CHARSET_RANGE)
3130             {
3131               re_string_skip_bytes (regexp, token_len); /* Skip '-'.  */
3132               token_len2 = peek_token_bracket (&token2, regexp, syntax);
3133               if (BE (token2.type == END_OF_RE, 0))
3134                 {
3135                   *err = REG_EBRACK;
3136                   goto parse_bracket_exp_free_return;
3137                 }
3138               if (token2.type == OP_CLOSE_BRACKET)
3139                 {
3140                   /* We treat the last '-' as a normal character.  */
3141                   re_string_skip_bytes (regexp, -token_len);
3142                   token->type = CHARACTER;
3143                 }
3144               else
3145                 is_range_exp = true;
3146             }
3147         }
3148
3149       if (is_range_exp == true)
3150         {
3151           end_elem.opr.name = end_name_buf;
3152           ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
3153                                        dfa, syntax, true);
3154           if (BE (ret != REG_NOERROR, 0))
3155             {
3156               *err = ret;
3157               goto parse_bracket_exp_free_return;
3158             }
3159
3160           token_len = peek_token_bracket (token, regexp, syntax);
3161
3162 #ifdef _LIBC
3163           *err = build_range_exp (sbcset, mbcset, &range_alloc,
3164                                   &start_elem, &end_elem);
3165 #else
3166 # ifdef RE_ENABLE_I18N
3167           *err = build_range_exp (sbcset,
3168                                   dfa->mb_cur_max > 1 ? mbcset : NULL,
3169                                   &range_alloc, &start_elem, &end_elem);
3170 # else
3171           *err = build_range_exp (sbcset, &start_elem, &end_elem);
3172 # endif
3173 #endif /* RE_ENABLE_I18N */
3174           if (BE (*err != REG_NOERROR, 0))
3175             goto parse_bracket_exp_free_return;
3176         }
3177       else
3178         {
3179           switch (start_elem.type)
3180             {
3181             case SB_CHAR:
3182               bitset_set (sbcset, start_elem.opr.ch);
3183               break;
3184 #ifdef RE_ENABLE_I18N
3185             case MB_CHAR:
3186               /* Check whether the array has enough space.  */
3187               if (BE (mbchar_alloc == mbcset->nmbchars, 0))
3188                 {
3189                   wchar_t *new_mbchars;
3190                   /* Not enough, realloc it.  */
3191                   /* +1 in case of mbcset->nmbchars is 0.  */
3192                   mbchar_alloc = 2 * mbcset->nmbchars + 1;
3193                   /* Use realloc since array is NULL if *alloc == 0.  */
3194                   new_mbchars = re_realloc (mbcset->mbchars, wchar_t,
3195                                             mbchar_alloc);
3196                   if (BE (new_mbchars == NULL, 0))
3197                     goto parse_bracket_exp_espace;
3198                   mbcset->mbchars = new_mbchars;
3199                 }
3200               mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
3201               break;
3202 #endif /* RE_ENABLE_I18N */
3203             case EQUIV_CLASS:
3204               *err = build_equiv_class (sbcset,
3205 #ifdef RE_ENABLE_I18N
3206                                         mbcset, &equiv_class_alloc,
3207 #endif /* RE_ENABLE_I18N */
3208                                         start_elem.opr.name);
3209               if (BE (*err != REG_NOERROR, 0))
3210                 goto parse_bracket_exp_free_return;
3211               break;
3212             case COLL_SYM:
3213               *err = build_collating_symbol (sbcset,
3214 #ifdef RE_ENABLE_I18N
3215                                              mbcset, &coll_sym_alloc,
3216 #endif /* RE_ENABLE_I18N */
3217                                              start_elem.opr.name);
3218               if (BE (*err != REG_NOERROR, 0))
3219                 goto parse_bracket_exp_free_return;
3220               break;
3221             case CHAR_CLASS:
3222               *err = build_charclass (regexp->trans, sbcset,
3223 #ifdef RE_ENABLE_I18N
3224                                       mbcset, &char_class_alloc,
3225 #endif /* RE_ENABLE_I18N */
3226                                       start_elem.opr.name, syntax);
3227               if (BE (*err != REG_NOERROR, 0))
3228                goto parse_bracket_exp_free_return;
3229               break;
3230             default:
3231               assert (0);
3232               break;
3233             }
3234         }
3235       if (BE (token->type == END_OF_RE, 0))
3236         {
3237           *err = REG_EBRACK;
3238           goto parse_bracket_exp_free_return;
3239         }
3240       if (token->type == OP_CLOSE_BRACKET)
3241         break;
3242     }
3243
3244   re_string_skip_bytes (regexp, token_len); /* Skip a token.  */
3245
3246   /* If it is non-matching list.  */
3247   if (non_match)
3248     bitset_not (sbcset);
3249
3250 #ifdef RE_ENABLE_I18N
3251   /* Ensure only single byte characters are set.  */
3252   if (dfa->mb_cur_max > 1)
3253     bitset_mask (sbcset, dfa->sb_char);
3254
3255   if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
3256       || mbcset->nranges || (dfa->mb_cur_max > 1 && (mbcset->nchar_classes
3257                                                      || mbcset->non_match)))
3258     {
3259       bin_tree_t *mbc_tree;
3260       int sbc_idx;
3261       /* Build a tree for complex bracket.  */
3262       dfa->has_mb_node = 1;
3263       br_token.type = COMPLEX_BRACKET;
3264       br_token.opr.mbcset = mbcset;
3265       mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3266       if (BE (mbc_tree == NULL, 0))
3267         goto parse_bracket_exp_espace;
3268       for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
3269         if (sbcset[sbc_idx])
3270           break;
3271       /* If there are no bits set in sbcset, there is no point
3272          of having both SIMPLE_BRACKET and COMPLEX_BRACKET.  */
3273       if (sbc_idx < BITSET_WORDS)
3274         {
3275           /* Build a tree for simple bracket.  */
3276           br_token.type = SIMPLE_BRACKET;
3277           br_token.opr.sbcset = sbcset;
3278           work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3279           if (BE (work_tree == NULL, 0))
3280             goto parse_bracket_exp_espace;
3281
3282           /* Then join them by ALT node.  */
3283           work_tree = create_tree (dfa, work_tree, mbc_tree, OP_ALT);
3284           if (BE (work_tree == NULL, 0))
3285             goto parse_bracket_exp_espace;
3286         }
3287       else
3288         {
3289           re_free (sbcset);
3290           work_tree = mbc_tree;
3291         }
3292     }
3293   else
3294 #endif /* not RE_ENABLE_I18N */
3295     {
3296 #ifdef RE_ENABLE_I18N
3297       free_charset (mbcset);
3298 #endif
3299       /* Build a tree for simple bracket.  */
3300       br_token.type = SIMPLE_BRACKET;
3301       br_token.opr.sbcset = sbcset;
3302       work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3303       if (BE (work_tree == NULL, 0))
3304         goto parse_bracket_exp_espace;
3305     }
3306   return work_tree;
3307
3308  parse_bracket_exp_espace:
3309   *err = REG_ESPACE;
3310  parse_bracket_exp_free_return:
3311   re_free (sbcset);
3312 #ifdef RE_ENABLE_I18N
3313   free_charset (mbcset);
3314 #endif /* RE_ENABLE_I18N */
3315   return NULL;
3316 }
3317
3318 /* Parse an element in the bracket expression.  */
3319
3320 static reg_errcode_t
3321 parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp,
3322                        re_token_t *token, int token_len, re_dfa_t *dfa,
3323                        reg_syntax_t syntax, bool accept_hyphen)
3324 {
3325 #ifdef RE_ENABLE_I18N
3326   int cur_char_size;
3327   cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
3328   if (cur_char_size > 1)
3329     {
3330       elem->type = MB_CHAR;
3331       elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
3332       re_string_skip_bytes (regexp, cur_char_size);
3333       return REG_NOERROR;
3334     }
3335 #endif /* RE_ENABLE_I18N */
3336   re_string_skip_bytes (regexp, token_len); /* Skip a token.  */
3337   if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
3338       || token->type == OP_OPEN_EQUIV_CLASS)
3339     return parse_bracket_symbol (elem, regexp, token);
3340   if (BE (token->type == OP_CHARSET_RANGE, 0) && !accept_hyphen)
3341     {
3342       /* A '-' must only appear as anything but a range indicator before
3343          the closing bracket.  Everything else is an error.  */
3344       re_token_t token2;
3345       (void) peek_token_bracket (&token2, regexp, syntax);
3346       if (token2.type != OP_CLOSE_BRACKET)
3347         /* The actual error value is not standardized since this whole
3348            case is undefined.  But ERANGE makes good sense.  */
3349         return REG_ERANGE;
3350     }
3351   elem->type = SB_CHAR;
3352   elem->opr.ch = token->opr.c;
3353   return REG_NOERROR;
3354 }
3355
3356 /* Parse a bracket symbol in the bracket expression.  Bracket symbols are
3357    such as [:<character_class>:], [.<collating_element>.], and
3358    [=<equivalent_class>=].  */
3359
3360 static reg_errcode_t
3361 parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
3362                       re_token_t *token)
3363 {
3364   unsigned char ch, delim = token->opr.c;
3365   int i = 0;
3366   if (re_string_eoi(regexp))
3367     return REG_EBRACK;
3368   for (;; ++i)
3369     {
3370       if (i >= BRACKET_NAME_BUF_SIZE)
3371         return REG_EBRACK;
3372       if (token->type == OP_OPEN_CHAR_CLASS)
3373         ch = re_string_fetch_byte_case (regexp);
3374       else
3375         ch = re_string_fetch_byte (regexp);
3376       if (re_string_eoi(regexp))
3377         return REG_EBRACK;
3378       if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
3379         break;
3380       elem->opr.name[i] = ch;
3381     }
3382   re_string_skip_bytes (regexp, 1);
3383   elem->opr.name[i] = '\0';
3384   switch (token->type)
3385     {
3386     case OP_OPEN_COLL_ELEM:
3387       elem->type = COLL_SYM;
3388       break;
3389     case OP_OPEN_EQUIV_CLASS:
3390       elem->type = EQUIV_CLASS;
3391       break;
3392     case OP_OPEN_CHAR_CLASS:
3393       elem->type = CHAR_CLASS;
3394       break;
3395     default:
3396       break;
3397     }
3398   return REG_NOERROR;
3399 }
3400
3401   /* Helper function for parse_bracket_exp.
3402      Build the equivalence class which is represented by NAME.
3403      The result are written to MBCSET and SBCSET.
3404      EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,
3405      is a pointer argument sinse we may update it.  */
3406
3407 static reg_errcode_t
3408 #ifdef RE_ENABLE_I18N
3409 build_equiv_class (bitset_t sbcset, re_charset_t *mbcset,
3410                    Idx *equiv_class_alloc, const unsigned char *name)
3411 #else /* not RE_ENABLE_I18N */
3412 build_equiv_class (bitset_t sbcset, const unsigned char *name)
3413 #endif /* not RE_ENABLE_I18N */
3414 {
3415 #ifdef _LIBC
3416   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3417   if (nrules != 0)
3418     {
3419       const int32_t *table, *indirect;
3420       const unsigned char *weights, *extra, *cp;
3421       unsigned char char_buf[2];
3422       int32_t idx1, idx2;
3423       unsigned int ch;
3424       size_t len;
3425       /* This #include defines a local function!  */
3426 # include <locale/weight.h>
3427       /* Calculate the index for equivalence class.  */
3428       cp = name;
3429       table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3430       weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3431                                                _NL_COLLATE_WEIGHTMB);
3432       extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3433                                                    _NL_COLLATE_EXTRAMB);
3434       indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3435                                                 _NL_COLLATE_INDIRECTMB);
3436       idx1 = findidx (&cp);
3437       if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0))
3438         /* This isn't a valid character.  */
3439         return REG_ECOLLATE;
3440
3441       /* Build single byte matcing table for this equivalence class.  */
3442       char_buf[1] = (unsigned char) '\0';
3443       len = weights[idx1 & 0xffffff];
3444       for (ch = 0; ch < SBC_MAX; ++ch)
3445         {
3446           char_buf[0] = ch;
3447           cp = char_buf;
3448           idx2 = findidx (&cp);
3449 /*
3450           idx2 = table[ch];
3451 */
3452           if (idx2 == 0)
3453             /* This isn't a valid character.  */
3454             continue;
3455           /* Compare only if the length matches and the collation rule
3456              index is the same.  */
3457           if (len == weights[idx2 & 0xffffff] && (idx1 >> 24) == (idx2 >> 24))
3458             {
3459               int cnt = 0;
3460
3461               while (cnt <= len &&
3462                      weights[(idx1 & 0xffffff) + 1 + cnt]
3463                      == weights[(idx2 & 0xffffff) + 1 + cnt])
3464                 ++cnt;
3465
3466               if (cnt > len)
3467                 bitset_set (sbcset, ch);
3468             }
3469         }
3470       /* Check whether the array has enough space.  */
3471       if (BE (*equiv_class_alloc == mbcset->nequiv_classes, 0))
3472         {
3473           /* Not enough, realloc it.  */
3474           /* +1 in case of mbcset->nequiv_classes is 0.  */
3475           Idx new_equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
3476           /* Use realloc since the array is NULL if *alloc == 0.  */
3477           int32_t *new_equiv_classes = re_realloc (mbcset->equiv_classes,
3478                                                    int32_t,
3479                                                    new_equiv_class_alloc);
3480           if (BE (new_equiv_classes == NULL, 0))
3481             return REG_ESPACE;
3482           mbcset->equiv_classes = new_equiv_classes;
3483           *equiv_class_alloc = new_equiv_class_alloc;
3484         }
3485       mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;
3486     }
3487   else
3488 #endif /* _LIBC */
3489     {
3490       if (BE (strlen ((const char *) name) != 1, 0))
3491         return REG_ECOLLATE;
3492       bitset_set (sbcset, *name);
3493     }
3494   return REG_NOERROR;
3495 }
3496
3497   /* Helper function for parse_bracket_exp.
3498      Build the character class which is represented by NAME.
3499      The result are written to MBCSET and SBCSET.
3500      CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,
3501      is a pointer argument sinse we may update it.  */
3502
3503 static reg_errcode_t
3504 #ifdef RE_ENABLE_I18N
3505 build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
3506                  re_charset_t *mbcset, Idx *char_class_alloc,
3507                  const unsigned char *class_name, reg_syntax_t syntax)
3508 #else /* not RE_ENABLE_I18N */
3509 build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
3510                  const unsigned char *class_name, reg_syntax_t syntax)
3511 #endif /* not RE_ENABLE_I18N */
3512 {
3513   int i;
3514   const char *name = (const char *) class_name;
3515
3516   /* In case of REG_ICASE "upper" and "lower" match the both of
3517      upper and lower cases.  */
3518   if ((syntax & RE_ICASE)
3519       && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))
3520     name = "alpha";
3521
3522 #ifdef RE_ENABLE_I18N
3523   /* Check the space of the arrays.  */
3524   if (BE (*char_class_alloc == mbcset->nchar_classes, 0))
3525     {
3526       /* Not enough, realloc it.  */
3527       /* +1 in case of mbcset->nchar_classes is 0.  */
3528       Idx new_char_class_alloc = 2 * mbcset->nchar_classes + 1;
3529       /* Use realloc since array is NULL if *alloc == 0.  */
3530       wctype_t *new_char_classes = re_realloc (mbcset->char_classes, wctype_t,
3531                                                new_char_class_alloc);
3532       if (BE (new_char_classes == NULL, 0))
3533         return REG_ESPACE;
3534       mbcset->char_classes = new_char_classes;
3535       *char_class_alloc = new_char_class_alloc;
3536     }
3537   mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);
3538 #endif /* RE_ENABLE_I18N */
3539
3540 #define BUILD_CHARCLASS_LOOP(ctype_func)        \
3541   do {                                          \
3542     if (BE (trans != NULL, 0))                  \
3543       {                                         \
3544         for (i = 0; i < SBC_MAX; ++i)           \
3545           if (ctype_func (i))                   \
3546             bitset_set (sbcset, trans[i]);      \
3547       }                                         \
3548     else                                        \
3549       {                                         \
3550         for (i = 0; i < SBC_MAX; ++i)           \
3551           if (ctype_func (i))                   \
3552             bitset_set (sbcset, i);             \
3553       }                                         \
3554   } while (0)
3555
3556   if (strcmp (name, "alnum") == 0)
3557     BUILD_CHARCLASS_LOOP (isalnum);
3558   else if (strcmp (name, "cntrl") == 0)
3559     BUILD_CHARCLASS_LOOP (iscntrl);
3560   else if (strcmp (name, "lower") == 0)
3561     BUILD_CHARCLASS_LOOP (islower);
3562   else if (strcmp (name, "space") == 0)
3563     BUILD_CHARCLASS_LOOP (isspace);
3564   else if (strcmp (name, "alpha") == 0)
3565     BUILD_CHARCLASS_LOOP (isalpha);
3566   else if (strcmp (name, "digit") == 0)
3567     BUILD_CHARCLASS_LOOP (isdigit);
3568   else if (strcmp (name, "print") == 0)
3569     BUILD_CHARCLASS_LOOP (isprint);
3570   else if (strcmp (name, "upper") == 0)
3571     BUILD_CHARCLASS_LOOP (isupper);
3572   else if (strcmp (name, "blank") == 0)
3573     BUILD_CHARCLASS_LOOP (isblank);
3574   else if (strcmp (name, "graph") == 0)
3575     BUILD_CHARCLASS_LOOP (isgraph);
3576   else if (strcmp (name, "punct") == 0)
3577     BUILD_CHARCLASS_LOOP (ispunct);
3578   else if (strcmp (name, "xdigit") == 0)
3579     BUILD_CHARCLASS_LOOP (isxdigit);
3580   else
3581     return REG_ECTYPE;
3582
3583   return REG_NOERROR;
3584 }
3585
3586 static bin_tree_t *
3587 build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
3588                     const unsigned char *class_name,
3589                     const unsigned char *extra, bool non_match,
3590                     reg_errcode_t *err)
3591 {
3592   re_bitset_ptr_t sbcset;
3593 #ifdef RE_ENABLE_I18N
3594   re_charset_t *mbcset;
3595   Idx alloc = 0;
3596 #endif /* not RE_ENABLE_I18N */
3597   reg_errcode_t ret;
3598   re_token_t br_token;
3599   bin_tree_t *tree;
3600
3601   sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
3602 #ifdef RE_ENABLE_I18N
3603   mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3604 #endif /* RE_ENABLE_I18N */
3605
3606 #ifdef RE_ENABLE_I18N
3607   if (BE (sbcset == NULL || mbcset == NULL, 0))
3608 #else /* not RE_ENABLE_I18N */
3609   if (BE (sbcset == NULL, 0))
3610 #endif /* not RE_ENABLE_I18N */
3611     {
3612       *err = REG_ESPACE;
3613       return NULL;
3614     }
3615
3616   if (non_match)
3617     {
3618 #ifdef RE_ENABLE_I18N
3619       mbcset->non_match = 1;
3620 #endif /* not RE_ENABLE_I18N */
3621     }
3622
3623   /* We don't care the syntax in this case.  */
3624   ret = build_charclass (trans, sbcset,
3625 #ifdef RE_ENABLE_I18N
3626                          mbcset, &alloc,
3627 #endif /* RE_ENABLE_I18N */
3628                          class_name, 0);
3629
3630   if (BE (ret != REG_NOERROR, 0))
3631     {
3632       re_free (sbcset);
3633 #ifdef RE_ENABLE_I18N
3634       free_charset (mbcset);
3635 #endif /* RE_ENABLE_I18N */
3636       *err = ret;
3637       return NULL;
3638     }
3639   /* \w match '_' also.  */
3640   for (; *extra; extra++)
3641     bitset_set (sbcset, *extra);
3642
3643   /* If it is non-matching list.  */
3644   if (non_match)
3645     bitset_not (sbcset);
3646
3647 #ifdef RE_ENABLE_I18N
3648   /* Ensure only single byte characters are set.  */
3649   if (dfa->mb_cur_max > 1)
3650     bitset_mask (sbcset, dfa->sb_char);
3651 #endif
3652
3653   /* Build a tree for simple bracket.  */
3654   br_token.type = SIMPLE_BRACKET;
3655   br_token.opr.sbcset = sbcset;
3656   tree = create_token_tree (dfa, NULL, NULL, &br_token);
3657   if (BE (tree == NULL, 0))
3658     goto build_word_op_espace;
3659
3660 #ifdef RE_ENABLE_I18N
3661   if (dfa->mb_cur_max > 1)
3662     {
3663       bin_tree_t *mbc_tree;
3664       /* Build a tree for complex bracket.  */
3665       br_token.type = COMPLEX_BRACKET;
3666       br_token.opr.mbcset = mbcset;
3667       dfa->has_mb_node = 1;
3668       mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3669       if (BE (mbc_tree == NULL, 0))
3670         goto build_word_op_espace;
3671       /* Then join them by ALT node.  */
3672       tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
3673       if (BE (mbc_tree != NULL, 1))
3674         return tree;
3675     }
3676   else
3677     {
3678       free_charset (mbcset);
3679       return tree;
3680     }
3681 #else /* not RE_ENABLE_I18N */
3682   return tree;
3683 #endif /* not RE_ENABLE_I18N */
3684
3685  build_word_op_espace:
3686   re_free (sbcset);
3687 #ifdef RE_ENABLE_I18N
3688   free_charset (mbcset);
3689 #endif /* RE_ENABLE_I18N */
3690   *err = REG_ESPACE;
3691   return NULL;
3692 }
3693
3694 /* This is intended for the expressions like "a{1,3}".
3695    Fetch a number from `input', and return the number.
3696    Return REG_MISSING if the number field is empty like "{,1}".
3697    Return REG_ERROR if an error occurred.  */
3698
3699 static Idx
3700 fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
3701 {
3702   Idx num = REG_MISSING;
3703   unsigned char c;
3704   while (1)
3705     {
3706       fetch_token (token, input, syntax);
3707       c = token->opr.c;
3708       if (BE (token->type == END_OF_RE, 0))
3709         return REG_ERROR;
3710       if (token->type == OP_CLOSE_DUP_NUM || c == ',')
3711         break;
3712       num = ((token->type != CHARACTER || c < '0' || '9' < c
3713               || num == REG_ERROR)
3714              ? REG_ERROR
3715              : ((num == REG_MISSING) ? c - '0' : num * 10 + c - '0'));
3716       num = (num > RE_DUP_MAX) ? REG_ERROR : num;
3717     }
3718   return num;
3719 }
3720 \f
3721 #ifdef RE_ENABLE_I18N
3722 static void
3723 free_charset (re_charset_t *cset)
3724 {
3725   re_free (cset->mbchars);
3726 # ifdef _LIBC
3727   re_free (cset->coll_syms);
3728   re_free (cset->equiv_classes);
3729   re_free (cset->range_starts);
3730   re_free (cset->range_ends);
3731 # endif
3732   re_free (cset->char_classes);
3733   re_free (cset);
3734 }
3735 #endif /* RE_ENABLE_I18N */
3736 \f
3737 /* Functions for binary tree operation.  */
3738
3739 /* Create a tree node.  */
3740
3741 static bin_tree_t *
3742 create_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3743              re_token_type_t type)
3744 {
3745   re_token_t t;
3746   t.type = type;
3747   return create_token_tree (dfa, left, right, &t);
3748 }
3749
3750 static bin_tree_t *
3751 create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3752                    const re_token_t *token)
3753 {
3754   bin_tree_t *tree;
3755   if (BE (dfa->str_tree_storage_idx == BIN_TREE_STORAGE_SIZE, 0))
3756     {
3757       bin_tree_storage_t *storage = re_malloc (bin_tree_storage_t, 1);
3758
3759       if (storage == NULL)
3760         return NULL;
3761       storage->next = dfa->str_tree_storage;
3762       dfa->str_tree_storage = storage;
3763       dfa->str_tree_storage_idx = 0;
3764     }
3765   tree = &dfa->str_tree_storage->data[dfa->str_tree_storage_idx++];
3766
3767   tree->parent = NULL;
3768   tree->left = left;
3769   tree->right = right;
3770   tree->token = *token;
3771   tree->token.duplicated = 0;
3772   tree->token.opt_subexp = 0;
3773   tree->first = NULL;
3774   tree->next = NULL;
3775   tree->node_idx = REG_MISSING;
3776
3777   if (left != NULL)
3778     left->parent = tree;
3779   if (right != NULL)
3780     right->parent = tree;
3781   return tree;
3782 }
3783
3784 /* Mark the tree SRC as an optional subexpression.
3785    To be called from preorder or postorder.  */
3786
3787 static reg_errcode_t
3788 mark_opt_subexp (void *extra, bin_tree_t *node)
3789 {
3790   Idx idx = (Idx) (long) extra;
3791   if (node->token.type == SUBEXP && node->token.opr.idx == idx)
3792     node->token.opt_subexp = 1;
3793
3794   return REG_NOERROR;
3795 }
3796
3797 /* Free the allocated memory inside NODE. */
3798
3799 static void
3800 free_token (re_token_t *node)
3801 {
3802 #ifdef RE_ENABLE_I18N
3803   if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
3804     free_charset (node->opr.mbcset);
3805   else
3806 #endif /* RE_ENABLE_I18N */
3807     if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
3808       re_free (node->opr.sbcset);
3809 }
3810
3811 /* Worker function for tree walking.  Free the allocated memory inside NODE
3812    and its children. */
3813
3814 static reg_errcode_t
3815 free_tree (void *extra, bin_tree_t *node)
3816 {
3817   free_token (&node->token);
3818   return REG_NOERROR;
3819 }
3820
3821
3822 /* Duplicate the node SRC, and return new node.  This is a preorder
3823    visit similar to the one implemented by the generic visitor, but
3824    we need more infrastructure to maintain two parallel trees --- so,
3825    it's easier to duplicate.  */
3826
3827 static bin_tree_t *
3828 duplicate_tree (const bin_tree_t *root, re_dfa_t *dfa)
3829 {
3830   const bin_tree_t *node;
3831   bin_tree_t *dup_root;
3832   bin_tree_t **p_new = &dup_root, *dup_node = root->parent;
3833
3834   for (node = root; ; )
3835     {
3836       /* Create a new tree and link it back to the current parent.  */
3837       *p_new = create_token_tree (dfa, NULL, NULL, &node->token);
3838       if (*p_new == NULL)
3839         return NULL;
3840       (*p_new)->parent = dup_node;
3841       (*p_new)->token.duplicated = 1;
3842       dup_node = *p_new;
3843
3844       /* Go to the left node, or up and to the right.  */
3845       if (node->left)
3846         {
3847           node = node->left;
3848           p_new = &dup_node->left;
3849         }
3850       else
3851         {
3852           const bin_tree_t *prev = NULL;
3853           while (node->right == prev || node->right == NULL)
3854             {
3855               prev = node;
3856               node = node->parent;
3857               dup_node = dup_node->parent;
3858               if (!node)
3859                 return dup_root;
3860             }
3861           node = node->right;
3862           p_new = &dup_node->right;
3863         }
3864     }
3865 }