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