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