git.cworth.org Git - tar/blob - lib/regcomp.c

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