lib/regexec.c

   1 /* Extended regular expression matching and search library.
   2    Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License along
  17    with this program; if not, write to the Free Software Foundation,
  18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
  19
  20 #ifndef __GNUC_PREREQ
  21 # if defined __GNUC__ && defined __GNUC_MINOR__
  22 #  define __GNUC_PREREQ(maj, min) \
  23         ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
  24 # else
  25 #  define __GNUC_PREREQ(maj, min) 0
  26 # endif
  27 #endif
  28
  29 #if !__GNUC_PREREQ (3, 1)
  30 # define always_inline
  31 #endif
  32
  33 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
  34                                      Idx n) internal_function;
  35 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
  36 static void match_ctx_free (re_match_context_t *cache) internal_function;
  37 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
  38                                           Idx str_idx, Idx from, Idx to)
  39      internal_function;
  40 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
  41      internal_function;
  42 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
  43                                            Idx str_idx) internal_function;
  44 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
  45                                                     Idx node, Idx str_idx)
  46      internal_function;
  47 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
  48                            re_dfastate_t **limited_sts, Idx last_node,
  49                            Idx last_str_idx)
  50      internal_function;
  51 static reg_errcode_t re_search_internal (const regex_t *preg,
  52                                          const char *string, Idx length,
  53                                          Idx start, Idx last_start, Idx stop,
  54                                          size_t nmatch, regmatch_t pmatch[],
  55                                          int eflags) internal_function;
  56 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
  57                                   const char *string1, Idx length1,
  58                                   const char *string2, Idx length2,
  59                                   Idx start, regoff_t range,
  60                                   struct re_registers *regs,
  61                                   Idx stop, bool ret_len) internal_function;
  62 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
  63                                 const char *string, Idx length, Idx start,
  64                                 regoff_t range, Idx stop,
  65                                 struct re_registers *regs,
  66                                 bool ret_len) internal_function;
  67 static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
  68                               Idx nregs, int regs_allocated) internal_function;
  69 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
  70      internal_function;
  71 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
  72                            Idx *p_match_first)
  73      internal_function;
  74 static Idx check_halt_state_context (const re_match_context_t *mctx,
  75                                      const re_dfastate_t *state, Idx idx)
  76      internal_function;
  77 static void update_regs (re_dfa_t *dfa, regmatch_t *pmatch,
  78                          regmatch_t *prev_idx_match, Idx cur_node,
  79                          Idx cur_idx, Idx nmatch) internal_function;
  80 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
  81                                       Idx str_idx, Idx dest_node, Idx nregs,
  82                                       regmatch_t *regs,
  83                                       re_node_set *eps_via_nodes) internal_function;
  84 static reg_errcode_t set_regs (const regex_t *preg,
  85                                const re_match_context_t *mctx,
  86                                size_t nmatch, regmatch_t *pmatch,
  87                                bool fl_backtrack) internal_function;
  88 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs) internal_function;
  89
  90 #ifdef RE_ENABLE_I18N
  91 static int sift_states_iter_mb (const re_match_context_t *mctx,
  92                                 re_sift_context_t *sctx,
  93                                 Idx node_idx, Idx str_idx, Idx max_str_idx) internal_function;
  94 #endif /* RE_ENABLE_I18N */
  95 static reg_errcode_t sift_states_backward (re_match_context_t *mctx,
  96                                            re_sift_context_t *sctx) internal_function;
  97 static reg_errcode_t build_sifted_states (re_match_context_t *mctx,
  98                                           re_sift_context_t *sctx, Idx str_idx,
  99                                           re_node_set *cur_dest) internal_function;
 100 static reg_errcode_t update_cur_sifted_state (re_match_context_t *mctx,
 101                                               re_sift_context_t *sctx,
 102                                               Idx str_idx,
 103                                               re_node_set *dest_nodes) internal_function;
 104 static reg_errcode_t add_epsilon_src_nodes (re_dfa_t *dfa,
 105                                             re_node_set *dest_nodes,
 106                                             const re_node_set *candidates) internal_function;
 107 static bool check_dst_limits (const re_match_context_t *mctx,
 108                               const re_node_set *limits,
 109                               Idx dst_node, Idx dst_idx, Idx src_node,
 110                               Idx src_idx) internal_function;
 111 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
 112                                         int boundaries, Idx subexp_idx,
 113                                         Idx from_node, Idx bkref_idx) internal_function;
 114 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
 115                                       Idx limit, Idx subexp_idx,
 116                                       Idx node, Idx str_idx,
 117                                       Idx bkref_idx) internal_function;
 118 static reg_errcode_t check_subexp_limits (re_dfa_t *dfa,
 119                                           re_node_set *dest_nodes,
 120                                           const re_node_set *candidates,
 121                                           re_node_set *limits,
 122                                           struct re_backref_cache_entry *bkref_ents,
 123                                           Idx str_idx) internal_function;
 124 static reg_errcode_t sift_states_bkref (re_match_context_t *mctx,
 125                                         re_sift_context_t *sctx,
 126                                         Idx str_idx, const re_node_set *candidates) internal_function;
 127 static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst,
 128                                         re_dfastate_t **src, Idx num) internal_function;
 129 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
 130                                          re_match_context_t *mctx) internal_function;
 131 static re_dfastate_t *transit_state (reg_errcode_t *err,
 132                                      re_match_context_t *mctx,
 133                                      re_dfastate_t *state) internal_function;
 134 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
 135                                             re_match_context_t *mctx,
 136                                             re_dfastate_t *next_state) internal_function;
 137 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
 138                                                 re_node_set *cur_nodes,
 139                                                 Idx str_idx) internal_function;
 140 #if 0
 141 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
 142                                         re_match_context_t *mctx,
 143                                         re_dfastate_t *pstate) internal_function;
 144 #endif
 145 #ifdef RE_ENABLE_I18N
 146 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
 147                                        re_dfastate_t *pstate) internal_function;
 148 #endif /* RE_ENABLE_I18N */
 149 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
 150                                           const re_node_set *nodes) internal_function;
 151 static reg_errcode_t get_subexp (re_match_context_t *mctx,
 152                                  Idx bkref_node, Idx bkref_str_idx) internal_function;
 153 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
 154                                      const re_sub_match_top_t *sub_top,
 155                                      re_sub_match_last_t *sub_last,
 156                                      Idx bkref_node, Idx bkref_str) internal_function;
 157 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
 158                              Idx subexp_idx, int type) internal_function;
 159 static reg_errcode_t check_arrival (re_match_context_t *mctx,
 160                                     state_array_t *path, Idx top_node,
 161                                     Idx top_str, Idx last_node, Idx last_str,
 162                                     int type) internal_function;
 163 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
 164                                                    Idx str_idx,
 165                                                    re_node_set *cur_nodes,
 166                                                    re_node_set *next_nodes) internal_function;
 167 static reg_errcode_t check_arrival_expand_ecl (re_dfa_t *dfa,
 168                                                re_node_set *cur_nodes,
 169                                                Idx ex_subexp, int type) internal_function;
 170 static reg_errcode_t check_arrival_expand_ecl_sub (re_dfa_t *dfa,
 171                                                    re_node_set *dst_nodes,
 172                                                    Idx target, Idx ex_subexp,
 173                                                    int type) internal_function;
 174 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
 175                                          re_node_set *cur_nodes, Idx cur_str,
 176                                          Idx subexp_num, int type) internal_function;
 177 static bool build_trtable (re_dfa_t *dfa,
 178                            re_dfastate_t *state) internal_function;
 179 #ifdef RE_ENABLE_I18N
 180 static int check_node_accept_bytes (re_dfa_t *dfa, Idx node_idx,
 181                                     const re_string_t *input, Idx idx) internal_function;
 182 # ifdef _LIBC
 183 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
 184                                                    size_t name_len) internal_function;
 185 # endif /* _LIBC */
 186 #endif /* RE_ENABLE_I18N */
 187 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
 188                                        const re_dfastate_t *state,
 189                                        re_node_set *states_node,
 190                                        bitset *states_ch) internal_function;
 191 static bool check_node_accept (const re_match_context_t *mctx,
 192                                const re_token_t *node, Idx idx)
 193      internal_function;
 194 static reg_errcode_t extend_buffers (re_match_context_t *mctx) internal_function;
 195 \f
 196 /* Entry point for POSIX code.  */
 197
 198 /* regexec searches for a given pattern, specified by PREG, in the
 199    string STRING.
 200
 201    If NMATCH is zero or REG_NOSUB was set in the cflags argument to
 202    `regcomp', we ignore PMATCH.  Otherwise, we assume PMATCH has at
 203    least NMATCH elements, and we set them to the offsets of the
 204    corresponding matched substrings.
 205
 206    EFLAGS specifies `execution flags' which affect matching: if
 207    REG_NOTBOL is set, then ^ does not match at the beginning of the
 208    string; if REG_NOTEOL is set, then $ does not match at the end.
 209
 210    We return 0 if we find a match and REG_NOMATCH if not.  */
 211
 212 int
 213 regexec (const regex_t *__restrict preg, const char *__restrict string,
 214          size_t nmatch, regmatch_t pmatch[], int eflags)
 215 {
 216   reg_errcode_t err;
 217   Idx start, length;
 218 #ifdef _LIBC
 219   re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
 220 #endif
 221
 222   if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
 223     return REG_BADPAT;
 224
 225   if (eflags & REG_STARTEND)
 226     {
 227       start = pmatch[0].rm_so;
 228       length = pmatch[0].rm_eo;
 229     }
 230   else
 231     {
 232       start = 0;
 233       length = strlen (string);
 234     }
 235
 236   __libc_lock_lock (dfa->lock);
 237   if (preg->re_no_sub)
 238     err = re_search_internal (preg, string, length, start, length,
 239                               length, 0, NULL, eflags);
 240   else
 241     err = re_search_internal (preg, string, length, start, length,
 242                               length, nmatch, pmatch, eflags);
 243   __libc_lock_unlock (dfa->lock);
 244   return err != REG_NOERROR;
 245 }
 246
 247 #ifdef _LIBC
 248 # include <shlib-compat.h>
 249 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
 250
 251 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
 252 __typeof__ (__regexec) __compat_regexec;
 253
 254 int
 255 attribute_compat_text_section
 256 __compat_regexec (const regex_t *__restrict preg,
 257                   const char *__restrict string, size_t nmatch,
 258                   regmatch_t pmatch[], int eflags)
 259 {
 260   return regexec (preg, string, nmatch, pmatch,
 261                   eflags & (REG_NOTBOL | REG_NOTEOL));
 262 }
 263 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
 264 # endif
 265 #endif
 266
 267 /* Entry points for GNU code.  */
 268
 269 /* re_match, re_search, re_match_2, re_search_2
 270
 271    The former two functions operate on STRING with length LENGTH,
 272    while the later two operate on concatenation of STRING1 and STRING2
 273    with lengths LENGTH1 and LENGTH2, respectively.
 274
 275    re_match() matches the compiled pattern in BUFP against the string,
 276    starting at index START.
 277
 278    re_search() first tries matching at index START, then it tries to match
 279    starting from index START + 1, and so on.  The last start position tried
 280    is START + RANGE.  (Thus RANGE = 0 forces re_search to operate the same
 281    way as re_match().)
 282
 283    The parameter STOP of re_{match,search}_2 specifies that no match exceeding
 284    the first STOP characters of the concatenation of the strings should be
 285    concerned.
 286
 287    If REGS is not NULL, and BUFP->re_no_sub is not set, the offsets of the match
 288    and all groups is stroed in REGS.  (For the "_2" variants, the offsets are
 289    computed relative to the concatenation, not relative to the individual
 290    strings.)
 291
 292    On success, re_match* functions return the length of the match, re_search*
 293    return the position of the start of the match.  Return value -1 means no
 294    match was found and -2 indicates an internal error.  */
 295
 296 regoff_t
 297 re_match (struct re_pattern_buffer *bufp, const char *string,
 298           Idx length, Idx start, struct re_registers *regs)
 299 {
 300   return re_search_stub (bufp, string, length, start, 0, length, regs, true);
 301 }
 302 #ifdef _LIBC
 303 weak_alias (__re_match, re_match)
 304 #endif
 305
 306 regoff_t
 307 re_search (struct re_pattern_buffer *bufp, const char *string,
 308            Idx length, Idx start, regoff_t range, struct re_registers *regs)
 309 {
 310   return re_search_stub (bufp, string, length, start, range, length, regs,
 311                          false);
 312 }
 313 #ifdef _LIBC
 314 weak_alias (__re_search, re_search)
 315 #endif
 316
 317 regoff_t
 318 re_match_2 (struct re_pattern_buffer *bufp,
 319             const char *string1, Idx length1,
 320             const char *string2, Idx length2,
 321             Idx start, struct re_registers *regs, Idx stop)
 322 {
 323   return re_search_2_stub (bufp, string1, length1, string2, length2,
 324                            start, 0, regs, stop, true);
 325 }
 326 #ifdef _LIBC
 327 weak_alias (__re_match_2, re_match_2)
 328 #endif
 329
 330 regoff_t
 331 re_search_2 (struct re_pattern_buffer *bufp,
 332              const char *string1, Idx length1,
 333              const char *string2, Idx length2,
 334              Idx start, regoff_t range, struct re_registers *regs, Idx stop)
 335 {
 336   return re_search_2_stub (bufp, string1, length1, string2, length2,
 337                            start, range, regs, stop, false);
 338 }
 339 #ifdef _LIBC
 340 weak_alias (__re_search_2, re_search_2)
 341 #endif
 342
 343 static regoff_t
 344 internal_function
 345 re_search_2_stub (struct re_pattern_buffer *bufp,
 346                   const char *string1, Idx length1,
 347                   const char *string2, Idx length2,
 348                   Idx start, regoff_t range, struct re_registers *regs,
 349                   Idx stop, bool ret_len)
 350 {
 351   const char *str;
 352   regoff_t rval;
 353   Idx len = length1 + length2;
 354   char *s = NULL;
 355
 356   if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
 357     return -2;
 358
 359   /* Concatenate the strings.  */
 360   if (length2 > 0)
 361     if (length1 > 0)
 362       {
 363         s = re_malloc (char, len);
 364
 365         if (BE (s == NULL, 0))
 366           return -2;
 367         memcpy (s, string1, length1);
 368         memcpy (s + length1, string2, length2);
 369         str = s;
 370       }
 371     else
 372       str = string2;
 373   else
 374     str = string1;
 375
 376   rval = re_search_stub (bufp, str, len, start, range, stop, regs,
 377                          ret_len);
 378   re_free (s);
 379   return rval;
 380 }
 381
 382 /* The parameters have the same meaning as those of re_search.
 383    Additional parameters:
 384    If RET_LEN is true the length of the match is returned (re_match style);
 385    otherwise the position of the match is returned.  */
 386
 387 static regoff_t
 388 internal_function
 389 re_search_stub (struct re_pattern_buffer *bufp,
 390                 const char *string, Idx length,
 391                 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
 392                 bool ret_len)
 393 {
 394   reg_errcode_t result;
 395   regmatch_t *pmatch;
 396   Idx nregs;
 397   regoff_t rval;
 398   int eflags = 0;
 399 #ifdef _LIBC
 400   re_dfa_t *dfa = (re_dfa_t *) bufp->re_buffer;
 401 #endif
 402   Idx last_start = start + range;
 403
 404   /* Check for out-of-range.  */
 405   if (BE (start < 0 || start > length, 0))
 406     return -1;
 407   if (sizeof start < sizeof range)
 408     {
 409       regoff_t length_offset = length;
 410       regoff_t start_offset = start;
 411       if (BE (length_offset - start_offset < range, 0))
 412         last_start = length;
 413       else if (BE (range < - start_offset, 0))
 414         last_start = 0;
 415     }
 416   else
 417     {
 418       if (BE ((last_start < start) != (range < 0), 0))
 419         {
 420           /* Overflow occurred when computing last_start; substitute
 421              the extreme value.  */
 422           last_start = range < 0 ? 0 : length;
 423         }
 424       else
 425         {
 426           if (BE (length < last_start, 0))
 427             last_start = length;
 428           else if (BE (last_start < 0, 0))
 429             last_start = 0;
 430         }
 431     }
 432
 433   __libc_lock_lock (dfa->lock);
 434
 435   eflags |= (bufp->re_not_bol) ? REG_NOTBOL : 0;
 436   eflags |= (bufp->re_not_eol) ? REG_NOTEOL : 0;
 437
 438   /* Compile fastmap if we haven't yet.  */
 439   if (start < last_start && bufp->re_fastmap != NULL
 440       && !bufp->re_fastmap_accurate)
 441     re_compile_fastmap (bufp);
 442
 443   if (BE (bufp->re_no_sub, 0))
 444     regs = NULL;
 445
 446   /* We need at least 1 register.  */
 447   if (regs == NULL)
 448     nregs = 1;
 449   else if (BE (bufp->re_regs_allocated == REG_FIXED
 450                && regs->rm_num_regs <= bufp->re_nsub, 0))
 451     {
 452       nregs = regs->rm_num_regs;
 453       if (BE (nregs < 1, 0))
 454         {
 455           /* Nothing can be copied to regs.  */
 456           regs = NULL;
 457           nregs = 1;
 458         }
 459     }
 460   else
 461     nregs = bufp->re_nsub + 1;
 462   pmatch = re_xmalloc (regmatch_t, nregs);
 463   if (BE (pmatch == NULL, 0))
 464     {
 465       rval = -2;
 466       goto out;
 467     }
 468
 469   result = re_search_internal (bufp, string, length, start, last_start, stop,
 470                                nregs, pmatch, eflags);
 471
 472   rval = 0;
 473
 474   /* I hope we needn't fill ther regs with -1's when no match was found.  */
 475   if (result != REG_NOERROR)
 476     rval = -1;
 477   else if (regs != NULL)
 478     {
 479       /* If caller wants register contents data back, copy them.  */
 480       bufp->re_regs_allocated = re_copy_regs (regs, pmatch, nregs,
 481                                               bufp->re_regs_allocated);
 482       if (BE (bufp->re_regs_allocated == REG_UNALLOCATED, 0))
 483         rval = -2;
 484     }
 485
 486   if (BE (rval == 0, 1))
 487     {
 488       if (ret_len)
 489         {
 490           assert (pmatch[0].rm_so == start);
 491           rval = pmatch[0].rm_eo - start;
 492         }
 493       else
 494         rval = pmatch[0].rm_so;
 495     }
 496   re_free (pmatch);
 497  out:
 498   __libc_lock_unlock (dfa->lock);
 499   return rval;
 500 }
 501
 502 static unsigned
 503 internal_function
 504 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
 505               int regs_allocated)
 506 {
 507   int rval = REG_REALLOCATE;
 508   Idx i;
 509   Idx need_regs = nregs + 1;
 510   /* We need one extra element beyond `rm_num_regs' for the `-1' marker GNU code
 511      uses.  */
 512
 513   /* Have the register data arrays been allocated?  */
 514   if (regs_allocated == REG_UNALLOCATED)
 515     { /* No.  So allocate them with malloc.  */
 516       regs->rm_start = re_xmalloc (regoff_t, need_regs);
 517       regs->rm_end = re_malloc (regoff_t, need_regs);
 518       if (BE (regs->rm_start == NULL, 0) || BE (regs->rm_end == NULL, 0))
 519         return REG_UNALLOCATED;
 520       regs->rm_num_regs = need_regs;
 521     }
 522   else if (regs_allocated == REG_REALLOCATE)
 523     { /* Yes.  If we need more elements than were already
 524          allocated, reallocate them.  If we need fewer, just
 525          leave it alone.  */
 526       if (BE (need_regs > regs->rm_num_regs, 0))
 527         {
 528           regoff_t *new_start =
 529             re_xrealloc (regs->rm_start, regoff_t, need_regs);
 530           regoff_t *new_end = re_realloc (regs->rm_end, regoff_t, need_regs);
 531           if (BE (new_start == NULL, 0) || BE (new_end == NULL, 0))
 532             return REG_UNALLOCATED;
 533           regs->rm_start = new_start;
 534           regs->rm_end = new_end;
 535           regs->rm_num_regs = need_regs;
 536         }
 537     }
 538   else
 539     {
 540       assert (regs_allocated == REG_FIXED);
 541       /* This function may not be called with REG_FIXED and nregs too big.  */
 542       assert (regs->rm_num_regs >= nregs);
 543       rval = REG_FIXED;
 544     }
 545
 546   /* Copy the regs.  */
 547   for (i = 0; i < nregs; ++i)
 548     {
 549       regs->rm_start[i] = pmatch[i].rm_so;
 550       regs->rm_end[i] = pmatch[i].rm_eo;
 551     }
 552   for ( ; i < regs->rm_num_regs; ++i)
 553     regs->rm_start[i] = regs->rm_end[i] = -1;
 554
 555   return rval;
 556 }
 557
 558 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
 559    ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use
 560    this memory for recording register information.  STARTS and ENDS
 561    must be allocated using the malloc library routine, and must each
 562    be at least NUM_REGS * sizeof (regoff_t) bytes long.
 563
 564    If NUM_REGS == 0, then subsequent matches should allocate their own
 565    register data.
 566
 567    Unless this function is called, the first search or match using
 568    PATTERN_BUFFER will allocate its own register data, without
 569    freeing the old data.  */
 570
 571 void
 572 re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs,
 573                   __re_size_t num_regs, regoff_t *starts, regoff_t *ends)
 574 {
 575   if (num_regs)
 576     {
 577       bufp->re_regs_allocated = REG_REALLOCATE;
 578       regs->rm_num_regs = num_regs;
 579       regs->rm_start = starts;
 580       regs->rm_end = ends;
 581     }
 582   else
 583     {
 584       bufp->re_regs_allocated = REG_UNALLOCATED;
 585       regs->rm_num_regs = 0;
 586       regs->rm_start = regs->rm_end = NULL;
 587     }
 588 }
 589 #ifdef _LIBC
 590 weak_alias (__re_set_registers, re_set_registers)
 591 #endif
 592 \f
 593 /* Entry points compatible with 4.2 BSD regex library.  We don't define
 594    them unless specifically requested.  */
 595
 596 #if defined _REGEX_RE_COMP || defined _LIBC
 597 int
 598 # ifdef _LIBC
 599 weak_function
 600 # endif
 601 re_exec (const char *s)
 602 {
 603   return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
 604 }
 605 #endif /* _REGEX_RE_COMP */
 606 \f
 607 /* Internal entry point.  */
 608
 609 /* Searches for a compiled pattern PREG in the string STRING, whose
 610    length is LENGTH.  NMATCH, PMATCH, and EFLAGS have the same
 611    meaning as with regexec.  LAST_START is START + RANGE, where
 612    START and RANGE have the same meaning as with re_search.
 613    Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
 614    otherwise return the error code.
 615    Note: We assume front end functions already check ranges.
 616    (0 <= LAST_START && LAST_START <= LENGTH)  */
 617
 618 static reg_errcode_t
 619 internal_function
 620 re_search_internal (const regex_t *preg,
 621                     const char *string, Idx length,
 622                     Idx start, Idx last_start, Idx stop,
 623                     size_t nmatch, regmatch_t pmatch[],
 624                     int eflags)
 625 {
 626   reg_errcode_t err;
 627   re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
 628   Idx left_lim, right_lim;
 629   int incr;
 630   bool fl_longest_match;
 631   int match_kind;
 632   Idx match_first, match_last = REG_MISSING;
 633   Idx extra_nmatch;
 634   bool sb;
 635   int ch;
 636 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
 637   re_match_context_t mctx = { .dfa = dfa };
 638 #else
 639   re_match_context_t mctx;
 640 #endif
 641   char *fastmap = ((preg->re_fastmap != NULL && preg->re_fastmap_accurate
 642                     && start != last_start && !preg->re_can_be_null)
 643                    ? preg->re_fastmap : NULL);
 644   unsigned REG_TRANSLATE_TYPE t =
 645     (unsigned REG_TRANSLATE_TYPE) preg->re_translate;
 646
 647 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
 648   memset (&mctx, '\0', sizeof (re_match_context_t));
 649   mctx.dfa = dfa;
 650 #endif
 651
 652   extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
 653   nmatch -= extra_nmatch;
 654
 655   /* Check if the DFA haven't been compiled.  */
 656   if (BE (preg->re_used == 0 || dfa->init_state == NULL
 657           || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
 658           || dfa->init_state_begbuf == NULL, 0))
 659     return REG_NOMATCH;
 660
 661 #ifdef DEBUG
 662   /* We assume front-end functions already check them.  */
 663   assert (0 <= last_start && last_start <= length);
 664 #endif
 665
 666   /* If initial states with non-begbuf contexts have no elements,
 667      the regex must be anchored.  If preg->re_newline_anchor is set,
 668      we'll never use init_state_nl, so do not check it.  */
 669   if (dfa->init_state->nodes.nelem == 0
 670       && dfa->init_state_word->nodes.nelem == 0
 671       && (dfa->init_state_nl->nodes.nelem == 0
 672           || !preg->re_newline_anchor))
 673     {
 674       if (start != 0 && last_start != 0)
 675         return REG_NOMATCH;
 676       start = last_start = 0;
 677     }
 678
 679   /* We must check the longest matching, if nmatch > 0.  */
 680   fl_longest_match = (nmatch != 0 || dfa->nbackref);
 681
 682   err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
 683                             preg->re_translate,
 684                             preg->re_syntax & REG_IGNORE_CASE, dfa);
 685   if (BE (err != REG_NOERROR, 0))
 686     goto free_return;
 687   mctx.input.stop = stop;
 688   mctx.input.raw_stop = stop;
 689   mctx.input.newline_anchor = preg->re_newline_anchor;
 690
 691   err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
 692   if (BE (err != REG_NOERROR, 0))
 693     goto free_return;
 694
 695   /* We will log all the DFA states through which the dfa pass,
 696      if nmatch > 1, or this dfa has "multibyte node", which is a
 697      back-reference or a node which can accept multibyte character or
 698      multi character collating element.  */
 699   if (nmatch > 1 || dfa->has_mb_node)
 700     {
 701       mctx.state_log = re_xmalloc (re_dfastate_t *, mctx.input.bufs_len + 1);
 702       if (BE (mctx.state_log == NULL, 0))
 703         {
 704           err = REG_ESPACE;
 705           goto free_return;
 706         }
 707     }
 708   else
 709     mctx.state_log = NULL;
 710
 711   match_first = start;
 712   mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
 713                            : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
 714
 715   /* Check incrementally whether of not the input string match.  */
 716   incr = (last_start < start) ? -1 : 1;
 717   left_lim = (last_start < start) ? last_start : start;
 718   right_lim = (last_start < start) ? start : last_start;
 719   sb = dfa->mb_cur_max == 1;
 720   match_kind =
 721     (fastmap
 722      ? ((sb || !(preg->re_syntax & REG_IGNORE_CASE || t) ? 4 : 0)
 723         | (start <= last_start ? 2 : 0)
 724         | (t != NULL ? 1 : 0))
 725      : 8);
 726
 727   for (;; match_first += incr)
 728     {
 729       err = REG_NOMATCH;
 730       if (match_first < left_lim || right_lim < match_first)
 731         goto free_return;
 732
 733       /* Advance as rapidly as possible through the string, until we
 734          find a plausible place to start matching.  This may be done
 735          with varying efficiency, so there are various possibilities:
 736          only the most common of them are specialized, in order to
 737          save on code size.  We use a switch statement for speed.  */
 738       switch (match_kind)
 739         {
 740         case 8:
 741           /* No fastmap.  */
 742           break;
 743
 744         case 7:
 745           /* Fastmap with single-byte translation, match forward.  */
 746           while (BE (match_first < right_lim, 1)
 747                  && !fastmap[t[(unsigned char) string[match_first]]])
 748             ++match_first;
 749           goto forward_match_found_start_or_reached_end;
 750
 751         case 6:
 752           /* Fastmap without translation, match forward.  */
 753           while (BE (match_first < right_lim, 1)
 754                  && !fastmap[(unsigned char) string[match_first]])
 755             ++match_first;
 756
 757         forward_match_found_start_or_reached_end:
 758           if (BE (match_first == right_lim, 0))
 759             {
 760               ch = match_first >= length
 761                        ? 0 : (unsigned char) string[match_first];
 762               if (!fastmap[t ? t[ch] : ch])
 763                 goto free_return;
 764             }
 765           break;
 766
 767         case 4:
 768         case 5:
 769           /* Fastmap without multi-byte translation, match backwards.  */
 770           while (match_first >= left_lim)
 771             {
 772               ch = match_first >= length
 773                        ? 0 : (unsigned char) string[match_first];
 774               if (fastmap[t ? t[ch] : ch])
 775                 break;
 776               --match_first;
 777             }
 778           if (match_first < left_lim)
 779             goto free_return;
 780           break;
 781
 782         default:
 783           /* In this case, we can't determine easily the current byte,
 784              since it might be a component byte of a multibyte
 785              character.  Then we use the constructed buffer instead.  */
 786           for (;;)
 787             {
 788               /* If MATCH_FIRST is out of the valid range, reconstruct the
 789                  buffers.  */
 790               __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
 791               if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
 792                 {
 793                   err = re_string_reconstruct (&mctx.input, match_first,
 794                                                eflags);
 795                   if (BE (err != REG_NOERROR, 0))
 796                     goto free_return;
 797
 798                   offset = match_first - mctx.input.raw_mbs_idx;
 799                 }
 800               /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
 801                  Note that MATCH_FIRST must not be smaller than 0.  */
 802               ch = (match_first >= length
 803                     ? 0 : re_string_byte_at (&mctx.input, offset));
 804               if (fastmap[ch])
 805                 break;
 806               match_first += incr;
 807               if (match_first < left_lim || match_first > right_lim)
 808                 {
 809                   err = REG_NOMATCH;
 810                   goto free_return;
 811                 }
 812             }
 813           break;
 814         }
 815
 816       /* Reconstruct the buffers so that the matcher can assume that
 817          the matching starts from the beginning of the buffer.  */
 818       err = re_string_reconstruct (&mctx.input, match_first, eflags);
 819       if (BE (err != REG_NOERROR, 0))
 820         goto free_return;
 821
 822 #ifdef RE_ENABLE_I18N
 823      /* Don't consider this char as a possible match start if it part,
 824         yet isn't the head, of a multibyte character.  */
 825       if (!sb && !re_string_first_byte (&mctx.input, 0))
 826         continue;
 827 #endif
 828
 829       /* It seems to be appropriate one, then use the matcher.  */
 830       /* We assume that the matching starts from 0.  */
 831       mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
 832       match_last = check_matching (&mctx, fl_longest_match,
 833                                    start <= last_start ? &match_first : NULL);
 834       if (match_last != REG_MISSING)
 835         {
 836           if (BE (match_last == REG_ERROR, 0))
 837             {
 838               err = REG_ESPACE;
 839               goto free_return;
 840             }
 841           else
 842             {
 843               mctx.match_last = match_last;
 844               if ((!preg->re_no_sub && nmatch > 1) || dfa->nbackref)
 845                 {
 846                   re_dfastate_t *pstate = mctx.state_log[match_last];
 847                   mctx.last_node = check_halt_state_context (&mctx, pstate,
 848                                                              match_last);
 849                 }
 850               if ((!preg->re_no_sub && nmatch > 1 && dfa->has_plural_match)
 851                   || dfa->nbackref)
 852                 {
 853                   err = prune_impossible_nodes (&mctx);
 854                   if (err == REG_NOERROR)
 855                     break;
 856                   if (BE (err != REG_NOMATCH, 0))
 857                     goto free_return;
 858                   match_last = REG_MISSING;
 859                 }
 860               else
 861                 break; /* We found a match.  */
 862             }
 863         }
 864
 865       match_ctx_clean (&mctx);
 866     }
 867
 868 #ifdef DEBUG
 869   assert (match_last != REG_MISSING);
 870   assert (err == REG_NOERROR);
 871 #endif
 872
 873   /* Set pmatch[] if we need.  */
 874   if (nmatch > 0)
 875     {
 876       Idx reg_idx;
 877
 878       /* Initialize registers.  */
 879       for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
 880         pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
 881
 882       /* Set the points where matching start/end.  */
 883       pmatch[0].rm_so = 0;
 884       pmatch[0].rm_eo = mctx.match_last;
 885       /* FIXME: This function should fail if mctx.match_last exceeds
 886          the maximum possible regoff_t value.  We need a new error
 887          code REG_OVERFLOW.  */
 888
 889       if (!preg->re_no_sub && nmatch > 1)
 890         {
 891           err = set_regs (preg, &mctx, nmatch, pmatch,
 892                           dfa->has_plural_match && dfa->nbackref > 0);
 893           if (BE (err != REG_NOERROR, 0))
 894             goto free_return;
 895         }
 896
 897       /* At last, add the offset to the each registers, since we slided
 898          the buffers so that we could assume that the matching starts
 899          from 0.  */
 900       for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
 901         if (pmatch[reg_idx].rm_so != -1)
 902           {
 903 #ifdef RE_ENABLE_I18N
 904             if (BE (mctx.input.offsets_needed != 0, 0))
 905               {
 906                 pmatch[reg_idx].rm_so =
 907                   (pmatch[reg_idx].rm_so == mctx.input.valid_len
 908                    ? mctx.input.valid_raw_len
 909                    : mctx.input.offsets[pmatch[reg_idx].rm_so]);
 910                 pmatch[reg_idx].rm_eo =
 911                   (pmatch[reg_idx].rm_eo == mctx.input.valid_len
 912                    ? mctx.input.valid_raw_len
 913                    : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
 914               }
 915 #else
 916             assert (mctx.input.offsets_needed == 0);
 917 #endif
 918             pmatch[reg_idx].rm_so += match_first;
 919             pmatch[reg_idx].rm_eo += match_first;
 920           }
 921       for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
 922         {
 923           pmatch[nmatch + reg_idx].rm_so = -1;
 924           pmatch[nmatch + reg_idx].rm_eo = -1;
 925         }
 926
 927       if (dfa->subexp_map)
 928         for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
 929           if (dfa->subexp_map[reg_idx] != reg_idx)
 930             {
 931               pmatch[reg_idx + 1].rm_so
 932                 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
 933               pmatch[reg_idx + 1].rm_eo
 934                 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
 935             }
 936     }
 937
 938  free_return:
 939   re_free (mctx.state_log);
 940   if (dfa->nbackref)
 941     match_ctx_free (&mctx);
 942   re_string_destruct (&mctx.input);
 943   return err;
 944 }
 945
 946 static reg_errcode_t
 947 internal_function
 948 prune_impossible_nodes (re_match_context_t *mctx)
 949 {
 950   re_dfa_t *const dfa = mctx->dfa;
 951   Idx halt_node, match_last;
 952   reg_errcode_t ret;
 953   re_dfastate_t **sifted_states;
 954   re_dfastate_t **lim_states = NULL;
 955   re_sift_context_t sctx;
 956 #ifdef DEBUG
 957   assert (mctx->state_log != NULL);
 958 #endif
 959   match_last = mctx->match_last;
 960   halt_node = mctx->last_node;
 961   sifted_states = re_xmalloc (re_dfastate_t *, match_last + 1);
 962   if (BE (sifted_states == NULL, 0))
 963     {
 964       ret = REG_ESPACE;
 965       goto free_return;
 966     }
 967   if (dfa->nbackref)
 968     {
 969       lim_states = re_xmalloc (re_dfastate_t *, match_last + 1);
 970       if (BE (lim_states == NULL, 0))
 971         {
 972           ret = REG_ESPACE;
 973           goto free_return;
 974         }
 975       while (1)
 976         {
 977           memset (lim_states, '\0',
 978                   sizeof (re_dfastate_t *) * (match_last + 1));
 979           sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
 980                          match_last);
 981           ret = sift_states_backward (mctx, &sctx);
 982           re_node_set_free (&sctx.limits);
 983           if (BE (ret != REG_NOERROR, 0))
 984               goto free_return;
 985           if (sifted_states[0] != NULL || lim_states[0] != NULL)
 986             break;
 987           do
 988             {
 989               --match_last;
 990               if (! REG_VALID_INDEX (match_last))
 991                 {
 992                   ret = REG_NOMATCH;
 993                   goto free_return;
 994                 }
 995             } while (mctx->state_log[match_last] == NULL
 996                      || !mctx->state_log[match_last]->halt);
 997           halt_node = check_halt_state_context (mctx,
 998                                                 mctx->state_log[match_last],
 999                                                 match_last);
1000         }
1001       ret = merge_state_array (dfa, sifted_states, lim_states,
1002                                match_last + 1);
1003       re_free (lim_states);
1004       lim_states = NULL;
1005       if (BE (ret != REG_NOERROR, 0))
1006         goto free_return;
1007     }
1008   else
1009     {
1010       sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1011       ret = sift_states_backward (mctx, &sctx);
1012       re_node_set_free (&sctx.limits);
1013       if (BE (ret != REG_NOERROR, 0))
1014         goto free_return;
1015     }
1016   re_free (mctx->state_log);
1017   mctx->state_log = sifted_states;
1018   sifted_states = NULL;
1019   mctx->last_node = halt_node;
1020   mctx->match_last = match_last;
1021   ret = REG_NOERROR;
1022  free_return:
1023   re_free (sifted_states);
1024   re_free (lim_states);
1025   return ret;
1026 }
1027
1028 /* Acquire an initial state and return it.
1029    We must select appropriate initial state depending on the context,
1030    since initial states may have constraints like "\<", "^", etc..  */
1031
1032 static inline re_dfastate_t *
1033 __attribute ((always_inline)) internal_function
1034 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1035                             Idx idx)
1036 {
1037   re_dfa_t *const dfa = mctx->dfa;
1038   if (dfa->init_state->has_constraint)
1039     {
1040       unsigned int context;
1041       context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1042       if (IS_WORD_CONTEXT (context))
1043         return dfa->init_state_word;
1044       else if (IS_ORDINARY_CONTEXT (context))
1045         return dfa->init_state;
1046       else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1047         return dfa->init_state_begbuf;
1048       else if (IS_NEWLINE_CONTEXT (context))
1049         return dfa->init_state_nl;
1050       else if (IS_BEGBUF_CONTEXT (context))
1051         {
1052           /* It is relatively rare case, then calculate on demand.  */
1053           return re_acquire_state_context (err, dfa,
1054                                            dfa->init_state->entrance_nodes,
1055                                            context);
1056         }
1057       else
1058         /* Must not happen?  */
1059         return dfa->init_state;
1060     }
1061   else
1062     return dfa->init_state;
1063 }
1064
1065 /* Check whether the regular expression match input string INPUT or not,
1066    and return the index where the matching end.  Return REG_MISSING if
1067    there is no match, and return REG_ERROR in case of an error.
1068    FL_LONGEST_MATCH means we want the POSIX longest matching.
1069    If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1070    next place where we may want to try matching.
1071    Note that the matcher assume that the maching starts from the current
1072    index of the buffer.  */
1073
1074 static Idx
1075 internal_function
1076 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1077                 Idx *p_match_first)
1078 {
1079   re_dfa_t *const dfa = mctx->dfa;
1080   reg_errcode_t err;
1081   Idx match = 0;
1082   Idx match_last = REG_MISSING;
1083   Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1084   re_dfastate_t *cur_state;
1085   bool at_init_state = p_match_first != NULL;
1086   Idx next_start_idx = cur_str_idx;
1087
1088   err = REG_NOERROR;
1089   cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1090   /* An initial state must not be NULL (invalid).  */
1091   if (BE (cur_state == NULL, 0))
1092     {
1093       assert (err == REG_ESPACE);
1094       return REG_ERROR;
1095     }
1096
1097   if (mctx->state_log != NULL)
1098     {
1099       mctx->state_log[cur_str_idx] = cur_state;
1100
1101       /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1102          later.  E.g. Processing back references.  */
1103       if (BE (dfa->nbackref, 0))
1104         {
1105           at_init_state = false;
1106           err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1107           if (BE (err != REG_NOERROR, 0))
1108             return err;
1109
1110           if (cur_state->has_backref)
1111             {
1112               err = transit_state_bkref (mctx, &cur_state->nodes);
1113               if (BE (err != REG_NOERROR, 0))
1114                 return err;
1115             }
1116         }
1117     }
1118
1119   /* If the RE accepts NULL string.  */
1120   if (BE (cur_state->halt, 0))
1121     {
1122       if (!cur_state->has_constraint
1123           || check_halt_state_context (mctx, cur_state, cur_str_idx))
1124         {
1125           if (!fl_longest_match)
1126             return cur_str_idx;
1127           else
1128             {
1129               match_last = cur_str_idx;
1130               match = 1;
1131             }
1132         }
1133     }
1134
1135   while (!re_string_eoi (&mctx->input))
1136     {
1137       re_dfastate_t *old_state = cur_state;
1138       Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1139
1140       if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1141           || (BE (next_char_idx >= mctx->input.valid_len, 0)
1142               && mctx->input.valid_len < mctx->input.len))
1143         {
1144           err = extend_buffers (mctx);
1145           if (BE (err != REG_NOERROR, 0))
1146             {
1147               assert (err == REG_ESPACE);
1148               return REG_ERROR;
1149             }
1150         }
1151
1152       cur_state = transit_state (&err, mctx, cur_state);
1153       if (mctx->state_log != NULL)
1154         cur_state = merge_state_with_log (&err, mctx, cur_state);
1155
1156       if (cur_state == NULL)
1157         {
1158           /* Reached the invalid state or an error.  Try to recover a valid
1159              state using the state log, if available and if we have not
1160              already found a valid (even if not the longest) match.  */
1161           if (BE (err != REG_NOERROR, 0))
1162             return REG_ERROR;
1163
1164           if (mctx->state_log == NULL
1165               || (match && !fl_longest_match)
1166               || (cur_state = find_recover_state (&err, mctx)) == NULL)
1167             break;
1168         }
1169
1170       if (BE (at_init_state, 0))
1171         {
1172           if (old_state == cur_state)
1173             next_start_idx = next_char_idx;
1174           else
1175             at_init_state = false;
1176         }
1177
1178       if (cur_state->halt)
1179         {
1180           /* Reached a halt state.
1181              Check the halt state can satisfy the current context.  */
1182           if (!cur_state->has_constraint
1183               || check_halt_state_context (mctx, cur_state,
1184                                            re_string_cur_idx (&mctx->input)))
1185             {
1186               /* We found an appropriate halt state.  */
1187               match_last = re_string_cur_idx (&mctx->input);
1188               match = 1;
1189
1190               /* We found a match, do not modify match_first below.  */
1191               p_match_first = NULL;
1192               if (!fl_longest_match)
1193                 break;
1194             }
1195         }
1196     }
1197
1198   if (p_match_first)
1199     *p_match_first += next_start_idx;
1200
1201   return match_last;
1202 }
1203
1204 /* Check NODE match the current context.  */
1205
1206 static bool
1207 internal_function
1208 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1209 {
1210   re_token_type_t type = dfa->nodes[node].type;
1211   unsigned int constraint = dfa->nodes[node].constraint;
1212   if (type != END_OF_RE)
1213     return false;
1214   if (!constraint)
1215     return true;
1216   if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1217     return false;
1218   return true;
1219 }
1220
1221 /* Check the halt state STATE match the current context.
1222    Return 0 if not match, if the node, STATE has, is a halt node and
1223    match the context, return the node.  */
1224
1225 static Idx
1226 internal_function
1227 check_halt_state_context (const re_match_context_t *mctx,
1228                           const re_dfastate_t *state, Idx idx)
1229 {
1230   Idx i;
1231   unsigned int context;
1232 #ifdef DEBUG
1233   assert (state->halt);
1234 #endif
1235   context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1236   for (i = 0; i < state->nodes.nelem; ++i)
1237     if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1238       return state->nodes.elems[i];
1239   return 0;
1240 }
1241
1242 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1243    corresponding to the DFA).
1244    Return the destination node, and update EPS_VIA_NODES;
1245    return REG_MISSING in case of errors.  */
1246
1247 static Idx
1248 internal_function
1249 proceed_next_node (const re_match_context_t *mctx,
1250                    Idx nregs, regmatch_t *regs, Idx *pidx, Idx node,
1251                    re_node_set *eps_via_nodes, struct re_fail_stack_t *fs)
1252 {
1253   re_dfa_t *const dfa = mctx->dfa;
1254   Idx i;
1255   bool ok;
1256   if (IS_EPSILON_NODE (dfa->nodes[node].type))
1257     {
1258       re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1259       re_node_set *edests = &dfa->edests[node];
1260       Idx dest_node;
1261       ok = re_node_set_insert (eps_via_nodes, node);
1262       if (BE (! ok, 0))
1263         return REG_ERROR;
1264       /* Pick up a valid destination, or return REG_MISSING if none
1265          is found.  */
1266       for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1267         {
1268           Idx candidate = edests->elems[i];
1269           if (!re_node_set_contains (cur_nodes, candidate))
1270             continue;
1271           if (dest_node == REG_MISSING)
1272             dest_node = candidate;
1273
1274           else
1275             {
1276               /* In order to avoid infinite loop like "(a*)*", return the second
1277                  epsilon-transition if the first was already considered.  */
1278               if (re_node_set_contains (eps_via_nodes, dest_node))
1279                 return candidate;
1280
1281               /* Otherwise, push the second epsilon-transition on the fail stack.  */
1282               else if (fs != NULL
1283                        && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1284                                            eps_via_nodes))
1285                 return REG_ERROR;
1286
1287               /* We know we are going to exit.  */
1288               break;
1289             }
1290         }
1291       return dest_node;
1292     }
1293   else
1294     {
1295       Idx naccepted = 0;
1296       re_token_type_t type = dfa->nodes[node].type;
1297
1298 #ifdef RE_ENABLE_I18N
1299       if (dfa->nodes[node].accept_mb)
1300         naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1301       else
1302 #endif /* RE_ENABLE_I18N */
1303       if (type == OP_BACK_REF)
1304         {
1305           Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1306           naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1307           if (fs != NULL)
1308             {
1309               if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1310                 return REG_MISSING;
1311               else if (naccepted)
1312                 {
1313                   char *buf = (char *) re_string_get_buffer (&mctx->input);
1314                   if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1315                               naccepted) != 0)
1316                     return REG_MISSING;
1317                 }
1318             }
1319
1320           if (naccepted == 0)
1321             {
1322               Idx dest_node;
1323               ok = re_node_set_insert (eps_via_nodes, node);
1324               if (BE (! ok, 0))
1325                 return REG_ERROR;
1326               dest_node = dfa->edests[node].elems[0];
1327               if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1328                                         dest_node))
1329                 return dest_node;
1330             }
1331         }
1332
1333       if (naccepted != 0
1334           || check_node_accept (mctx, dfa->nodes + node, *pidx))
1335         {
1336           Idx dest_node = dfa->nexts[node];
1337           *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1338           if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1339                      || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1340                                                dest_node)))
1341             return REG_MISSING;
1342           re_node_set_empty (eps_via_nodes);
1343           return dest_node;
1344         }
1345     }
1346   return REG_MISSING;
1347 }
1348
1349 static reg_errcode_t
1350 internal_function
1351 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1352                  Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1353 {
1354   reg_errcode_t err;
1355   Idx num = fs->num++;
1356   if (fs->num == fs->alloc)
1357     {
1358       struct re_fail_stack_ent_t *new_array =
1359         re_x2realloc (fs->stack, struct re_fail_stack_ent_t, &fs->alloc);
1360       if (new_array == NULL)
1361         return REG_ESPACE;
1362       fs->stack = new_array;
1363     }
1364   fs->stack[num].idx = str_idx;
1365   fs->stack[num].node = dest_node;
1366   fs->stack[num].regs = re_xmalloc (regmatch_t, nregs);
1367   if (fs->stack[num].regs == NULL)
1368     return REG_ESPACE;
1369   memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1370   err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1371   return err;
1372 }
1373
1374 static Idx
1375 internal_function
1376 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx,
1377                 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1378 {
1379   Idx num = --fs->num;
1380   assert (REG_VALID_INDEX (num));
1381   *pidx = fs->stack[num].idx;
1382   memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1383   re_node_set_free (eps_via_nodes);
1384   re_free (fs->stack[num].regs);
1385   *eps_via_nodes = fs->stack[num].eps_via_nodes;
1386   return fs->stack[num].node;
1387 }
1388
1389 /* Set the positions where the subexpressions are starts/ends to registers
1390    PMATCH.
1391    Note: We assume that pmatch[0] is already set, and
1392    pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch.  */
1393
1394 static reg_errcode_t
1395 internal_function
1396 set_regs (const regex_t *preg, const re_match_context_t *mctx,
1397           size_t nmatch, regmatch_t *pmatch, bool fl_backtrack)
1398 {
1399   re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
1400   Idx idx, cur_node;
1401   re_node_set eps_via_nodes;
1402   struct re_fail_stack_t *fs;
1403   struct re_fail_stack_t fs_body = { 0, 2, NULL };
1404   regmatch_t *prev_idx_match;
1405   bool prev_idx_match_malloced = false;
1406
1407 #ifdef DEBUG
1408   assert (nmatch > 1);
1409   assert (mctx->state_log != NULL);
1410 #endif
1411   if (fl_backtrack)
1412     {
1413       fs = &fs_body;
1414       fs->stack = re_xmalloc (struct re_fail_stack_ent_t, fs->alloc);
1415       if (fs->stack == NULL)
1416         return REG_ESPACE;
1417     }
1418   else
1419     fs = NULL;
1420
1421   cur_node = dfa->init_node;
1422   re_node_set_init_empty (&eps_via_nodes);
1423
1424   if (re_alloc_oversized (nmatch, sizeof (regmatch_t)))
1425     {
1426       free_fail_stack_return (fs);
1427       return REG_ESPACE;
1428     }
1429   if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1430     prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1431   else
1432     {
1433       prev_idx_match = re_malloc (regmatch_t, nmatch);
1434       if (prev_idx_match == NULL)
1435         {
1436           free_fail_stack_return (fs);
1437           return REG_ESPACE;
1438         }
1439       prev_idx_match_malloced = true;
1440     }
1441   memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1442
1443   for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1444     {
1445       update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1446
1447       if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1448         {
1449           Idx reg_idx;
1450           if (fs)
1451             {
1452               for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1453                 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1454                   break;
1455               if (reg_idx == nmatch)
1456                 {
1457                   re_node_set_free (&eps_via_nodes);
1458                   if (prev_idx_match_malloced)
1459                     re_free (prev_idx_match);
1460                   return free_fail_stack_return (fs);
1461                 }
1462               cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1463                                          &eps_via_nodes);
1464             }
1465           else
1466             {
1467               re_node_set_free (&eps_via_nodes);
1468               if (prev_idx_match_malloced)
1469                 re_free (prev_idx_match);
1470               return REG_NOERROR;
1471             }
1472         }
1473
1474       /* Proceed to next node.  */
1475       cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1476                                     &eps_via_nodes, fs);
1477
1478       if (BE (! REG_VALID_INDEX (cur_node), 0))
1479         {
1480           if (BE (cur_node == REG_ERROR, 0))
1481             {
1482               re_node_set_free (&eps_via_nodes);
1483               if (prev_idx_match_malloced)
1484                 re_free (prev_idx_match);
1485               free_fail_stack_return (fs);
1486               return REG_ESPACE;
1487             }
1488           if (fs)
1489             cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1490                                        &eps_via_nodes);
1491           else
1492             {
1493               re_node_set_free (&eps_via_nodes);
1494               if (prev_idx_match_malloced)
1495                 re_free (prev_idx_match);
1496               return REG_NOMATCH;
1497             }
1498         }
1499     }
1500   re_node_set_free (&eps_via_nodes);
1501   if (prev_idx_match_malloced)
1502     re_free (prev_idx_match);
1503   return free_fail_stack_return (fs);
1504 }
1505
1506 static reg_errcode_t
1507 internal_function
1508 free_fail_stack_return (struct re_fail_stack_t *fs)
1509 {
1510   if (fs)
1511     {
1512       Idx fs_idx;
1513       for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1514         {
1515           re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1516           re_free (fs->stack[fs_idx].regs);
1517         }
1518       re_free (fs->stack);
1519     }
1520   return REG_NOERROR;
1521 }
1522
1523 static void
1524 internal_function
1525 update_regs (re_dfa_t *dfa, regmatch_t *pmatch, regmatch_t *prev_idx_match,
1526              Idx cur_node, Idx cur_idx, Idx nmatch)
1527 {
1528   int type = dfa->nodes[cur_node].type;
1529   if (type == OP_OPEN_SUBEXP)
1530     {
1531       Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1532
1533       /* We are at the first node of this sub expression.  */
1534       if (reg_num < nmatch)
1535         {
1536           pmatch[reg_num].rm_so = cur_idx;
1537           pmatch[reg_num].rm_eo = -1;
1538         }
1539     }
1540   else if (type == OP_CLOSE_SUBEXP)
1541     {
1542       Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1543       if (reg_num < nmatch)
1544         {
1545           /* We are at the last node of this sub expression.  */
1546           if (pmatch[reg_num].rm_so < cur_idx)
1547             {
1548               pmatch[reg_num].rm_eo = cur_idx;
1549               /* This is a non-empty match or we are not inside an optional
1550                  subexpression.  Accept this right away.  */
1551               memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1552             }
1553           else
1554             {
1555               if (dfa->nodes[cur_node].opt_subexp
1556                   && prev_idx_match[reg_num].rm_so != -1)
1557                 /* We transited through an empty match for an optional
1558                    subexpression, like (a?)*, and this is not the subexp's
1559                    first match.  Copy back the old content of the registers
1560                    so that matches of an inner subexpression are undone as
1561                    well, like in ((a?))*.  */
1562                 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1563               else
1564                 /* We completed a subexpression, but it may be part of
1565                    an optional one, so do not update PREV_IDX_MATCH.  */
1566                 pmatch[reg_num].rm_eo = cur_idx;
1567             }
1568         }
1569     }
1570 }
1571
1572 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1573    and sift the nodes in each states according to the following rules.
1574    Updated state_log will be wrote to STATE_LOG.
1575
1576    Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1577      1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1578         If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1579         the LAST_NODE, we throw away the node `a'.
1580      2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1581         string `s' and transit to `b':
1582         i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1583            away the node `a'.
1584         ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1585             thrown away, we throw away the node `a'.
1586      3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1587         i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1588            node `a'.
1589         ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1590             we throw away the node `a'.  */
1591
1592 #define STATE_NODE_CONTAINS(state,node) \
1593   ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1594
1595 static reg_errcode_t
1596 internal_function
1597 sift_states_backward (re_match_context_t *mctx, re_sift_context_t *sctx)
1598 {
1599   reg_errcode_t err;
1600   int null_cnt = 0;
1601   Idx str_idx = sctx->last_str_idx;
1602   re_node_set cur_dest;
1603
1604 #ifdef DEBUG
1605   assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1606 #endif
1607
1608   /* Build sifted state_log[str_idx].  It has the nodes which can epsilon
1609      transit to the last_node and the last_node itself.  */
1610   err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1611   if (BE (err != REG_NOERROR, 0))
1612     return err;
1613   err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1614   if (BE (err != REG_NOERROR, 0))
1615     goto free_return;
1616
1617   /* Then check each states in the state_log.  */
1618   while (str_idx > 0)
1619     {
1620       /* Update counters.  */
1621       null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1622       if (null_cnt > mctx->max_mb_elem_len)
1623         {
1624           memset (sctx->sifted_states, '\0',
1625                   sizeof (re_dfastate_t *) * str_idx);
1626           re_node_set_free (&cur_dest);
1627           return REG_NOERROR;
1628         }
1629       re_node_set_empty (&cur_dest);
1630       --str_idx;
1631
1632       if (mctx->state_log[str_idx])
1633         {
1634           err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1635           if (BE (err != REG_NOERROR, 0))
1636             goto free_return;
1637         }
1638
1639       /* Add all the nodes which satisfy the following conditions:
1640          - It can epsilon transit to a node in CUR_DEST.
1641          - It is in CUR_SRC.
1642          And update state_log.  */
1643       err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1644       if (BE (err != REG_NOERROR, 0))
1645         goto free_return;
1646     }
1647   err = REG_NOERROR;
1648  free_return:
1649   re_node_set_free (&cur_dest);
1650   return err;
1651 }
1652
1653 static reg_errcode_t
1654 internal_function
1655 build_sifted_states (re_match_context_t *mctx, re_sift_context_t *sctx,
1656                      Idx str_idx, re_node_set *cur_dest)
1657 {
1658   re_dfa_t *const dfa = mctx->dfa;
1659   re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1660   Idx i;
1661
1662   /* Then build the next sifted state.
1663      We build the next sifted state on `cur_dest', and update
1664      `sifted_states[str_idx]' with `cur_dest'.
1665      Note:
1666      `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1667      `cur_src' points the node_set of the old `state_log[str_idx]'
1668      (with the epsilon nodes pre-filtered out).  */
1669   for (i = 0; i < cur_src->nelem; i++)
1670     {
1671       Idx prev_node = cur_src->elems[i];
1672       int naccepted = 0;
1673       bool ok;
1674
1675 #ifdef DEBUG
1676       re_token_type_t type = dfa->nodes[prev_node].type;
1677       assert (!IS_EPSILON_NODE (type));
1678 #endif
1679 #ifdef RE_ENABLE_I18N
1680       /* If the node may accept `multi byte'.  */
1681       if (dfa->nodes[prev_node].accept_mb)
1682         naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1683                                          str_idx, sctx->last_str_idx);
1684 #endif /* RE_ENABLE_I18N */
1685
1686       /* We don't check backreferences here.
1687          See update_cur_sifted_state().  */
1688       if (!naccepted
1689           && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1690           && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1691                                   dfa->nexts[prev_node]))
1692         naccepted = 1;
1693
1694       if (naccepted == 0)
1695         continue;
1696
1697       if (sctx->limits.nelem)
1698         {
1699           Idx to_idx = str_idx + naccepted;
1700           if (check_dst_limits (mctx, &sctx->limits,
1701                                 dfa->nexts[prev_node], to_idx,
1702                                 prev_node, str_idx))
1703             continue;
1704         }
1705       ok = re_node_set_insert (cur_dest, prev_node);
1706       if (BE (! ok, 0))
1707         return REG_ESPACE;
1708     }
1709
1710   return REG_NOERROR;
1711 }
1712
1713 /* Helper functions.  */
1714
1715 static reg_errcode_t
1716 internal_function
1717 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1718 {
1719   Idx top = mctx->state_log_top;
1720
1721   if (next_state_log_idx >= mctx->input.bufs_len
1722       || (next_state_log_idx >= mctx->input.valid_len
1723           && mctx->input.valid_len < mctx->input.len))
1724     {
1725       reg_errcode_t err;
1726       err = extend_buffers (mctx);
1727       if (BE (err != REG_NOERROR, 0))
1728         return err;
1729     }
1730
1731   if (top < next_state_log_idx)
1732     {
1733       memset (mctx->state_log + top + 1, '\0',
1734               sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1735       mctx->state_log_top = next_state_log_idx;
1736     }
1737   return REG_NOERROR;
1738 }
1739
1740 static reg_errcode_t
1741 internal_function
1742 merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst, re_dfastate_t **src,
1743                    Idx num)
1744 {
1745   Idx st_idx;
1746   reg_errcode_t err;
1747   for (st_idx = 0; st_idx < num; ++st_idx)
1748     {
1749       if (dst[st_idx] == NULL)
1750         dst[st_idx] = src[st_idx];
1751       else if (src[st_idx] != NULL)
1752         {
1753           re_node_set merged_set;
1754           err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1755                                         &src[st_idx]->nodes);
1756           if (BE (err != REG_NOERROR, 0))
1757             return err;
1758           dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1759           re_node_set_free (&merged_set);
1760           if (BE (err != REG_NOERROR, 0))
1761             return err;
1762         }
1763     }
1764   return REG_NOERROR;
1765 }
1766
1767 static reg_errcode_t
1768 internal_function
1769 update_cur_sifted_state (re_match_context_t *mctx, re_sift_context_t *sctx,
1770                          Idx str_idx, re_node_set *dest_nodes)
1771 {
1772   re_dfa_t *const dfa = mctx->dfa;
1773   reg_errcode_t err;
1774   const re_node_set *candidates;
1775   candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1776                 : &mctx->state_log[str_idx]->nodes);
1777
1778   if (dest_nodes->nelem == 0)
1779     sctx->sifted_states[str_idx] = NULL;
1780   else
1781     {
1782       if (candidates)
1783         {
1784           /* At first, add the nodes which can epsilon transit to a node in
1785              DEST_NODE.  */
1786           err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1787           if (BE (err != REG_NOERROR, 0))
1788             return err;
1789
1790           /* Then, check the limitations in the current sift_context.  */
1791           if (sctx->limits.nelem)
1792             {
1793               err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1794                                          mctx->bkref_ents, str_idx);
1795               if (BE (err != REG_NOERROR, 0))
1796                 return err;
1797             }
1798         }
1799
1800       sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1801       if (BE (err != REG_NOERROR, 0))
1802         return err;
1803     }
1804
1805   if (candidates && mctx->state_log[str_idx]->has_backref)
1806     {
1807       err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1808       if (BE (err != REG_NOERROR, 0))
1809         return err;
1810     }
1811   return REG_NOERROR;
1812 }
1813
1814 static reg_errcode_t
1815 internal_function
1816 add_epsilon_src_nodes (re_dfa_t *dfa, re_node_set *dest_nodes,
1817                        const re_node_set *candidates)
1818 {
1819   reg_errcode_t err = REG_NOERROR;
1820   Idx i;
1821
1822   re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1823   if (BE (err != REG_NOERROR, 0))
1824     return err;
1825
1826   if (!state->inveclosure.alloc)
1827     {
1828       err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1829       if (BE (err != REG_NOERROR, 0))
1830         return REG_ESPACE;
1831       for (i = 0; i < dest_nodes->nelem; i++)
1832         re_node_set_merge (&state->inveclosure,
1833                            dfa->inveclosures + dest_nodes->elems[i]);
1834     }
1835   return re_node_set_add_intersect (dest_nodes, candidates,
1836                                     &state->inveclosure);
1837 }
1838
1839 static reg_errcode_t
1840 internal_function
1841 sub_epsilon_src_nodes (re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1842                        const re_node_set *candidates)
1843 {
1844     Idx ecl_idx;
1845     reg_errcode_t err;
1846     re_node_set *inv_eclosure = dfa->inveclosures + node;
1847     re_node_set except_nodes;
1848     re_node_set_init_empty (&except_nodes);
1849     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1850       {
1851         Idx cur_node = inv_eclosure->elems[ecl_idx];
1852         if (cur_node == node)
1853           continue;
1854         if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1855           {
1856             Idx edst1 = dfa->edests[cur_node].elems[0];
1857             Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1858                          ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1859             if ((!re_node_set_contains (inv_eclosure, edst1)
1860                  && re_node_set_contains (dest_nodes, edst1))
1861                 || (REG_VALID_NONZERO_INDEX (edst2)
1862                     && !re_node_set_contains (inv_eclosure, edst2)
1863                     && re_node_set_contains (dest_nodes, edst2)))
1864               {
1865                 err = re_node_set_add_intersect (&except_nodes, candidates,
1866                                                  dfa->inveclosures + cur_node);
1867                 if (BE (err != REG_NOERROR, 0))
1868                   {
1869                     re_node_set_free (&except_nodes);
1870                     return err;
1871                   }
1872               }
1873           }
1874       }
1875     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1876       {
1877         Idx cur_node = inv_eclosure->elems[ecl_idx];
1878         if (!re_node_set_contains (&except_nodes, cur_node))
1879           {
1880             Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1881             re_node_set_remove_at (dest_nodes, idx);
1882           }
1883       }
1884     re_node_set_free (&except_nodes);
1885     return REG_NOERROR;
1886 }
1887
1888 static bool
1889 internal_function
1890 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1891                   Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1892 {
1893   re_dfa_t *const dfa = mctx->dfa;
1894   Idx lim_idx, src_pos, dst_pos;
1895
1896   Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1897   Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1898   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1899     {
1900       Idx subexp_idx;
1901       struct re_backref_cache_entry *ent;
1902       ent = mctx->bkref_ents + limits->elems[lim_idx];
1903       subexp_idx = dfa->nodes[ent->node].opr.idx;
1904
1905       dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1906                                            subexp_idx, dst_node, dst_idx,
1907                                            dst_bkref_idx);
1908       src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1909                                            subexp_idx, src_node, src_idx,
1910                                            src_bkref_idx);
1911
1912       /* In case of:
1913          <src> <dst> ( <subexp> )
1914          ( <subexp> ) <src> <dst>
1915          ( <subexp1> <src> <subexp2> <dst> <subexp3> )  */
1916       if (src_pos == dst_pos)
1917         continue; /* This is unrelated limitation.  */
1918       else
1919         return true;
1920     }
1921   return false;
1922 }
1923
1924 static int
1925 internal_function
1926 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1927                              Idx subexp_idx, Idx from_node, Idx bkref_idx)
1928 {
1929   re_dfa_t *const dfa = mctx->dfa;
1930   re_node_set *eclosures = dfa->eclosures + from_node;
1931   Idx node_idx;
1932
1933   /* Else, we are on the boundary: examine the nodes on the epsilon
1934      closure.  */
1935   for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1936     {
1937       Idx node = eclosures->elems[node_idx];
1938       switch (dfa->nodes[node].type)
1939         {
1940         case OP_BACK_REF:
1941           if (bkref_idx != REG_MISSING)
1942             {
1943               struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1944               do
1945                 {
1946                   Idx dst;
1947                   int cpos;
1948
1949                   if (ent->node != node)
1950                     continue;
1951
1952                   if (subexp_idx < BITSET_WORD_BITS
1953                       && !(ent->eps_reachable_subexps_map
1954                            & ((bitset_word) 1 << subexp_idx)))
1955                     continue;
1956
1957                   /* Recurse trying to reach the OP_OPEN_SUBEXP and
1958                      OP_CLOSE_SUBEXP cases below.  But, if the
1959                      destination node is the same node as the source
1960                      node, don't recurse because it would cause an
1961                      infinite loop: a regex that exhibits this behavior
1962                      is ()\1*\1*  */
1963                   dst = dfa->edests[node].elems[0];
1964                   if (dst == from_node)
1965                     {
1966                       if (boundaries & 1)
1967                         return -1;
1968                       else /* if (boundaries & 2) */
1969                         return 0;
1970                     }
1971
1972                   cpos =
1973                     check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
1974                                                  dst, bkref_idx);
1975                   if (cpos == -1 /* && (boundaries & 1) */)
1976                     return -1;
1977                   if (cpos == 0 && (boundaries & 2))
1978                     return 0;
1979
1980                   if (subexp_idx < BITSET_WORD_BITS)
1981                     ent->eps_reachable_subexps_map &=
1982                       ~ ((bitset_word) 1 << subexp_idx);
1983                 }
1984               while (ent++->more);
1985             }
1986           break;
1987
1988         case OP_OPEN_SUBEXP:
1989           if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
1990             return -1;
1991           break;
1992
1993         case OP_CLOSE_SUBEXP:
1994           if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
1995             return 0;
1996           break;
1997
1998         default:
1999             break;
2000         }
2001     }
2002
2003   return (boundaries & 2) ? 1 : 0;
2004 }
2005
2006 static int
2007 internal_function
2008 check_dst_limits_calc_pos (const re_match_context_t *mctx,
2009                            Idx limit, Idx subexp_idx,
2010                            Idx from_node, Idx str_idx, Idx bkref_idx)
2011 {
2012   struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2013   int boundaries;
2014
2015   /* If we are outside the range of the subexpression, return -1 or 1.  */
2016   if (str_idx < lim->subexp_from)
2017     return -1;
2018
2019   if (lim->subexp_to < str_idx)
2020     return 1;
2021
2022   /* If we are within the subexpression, return 0.  */
2023   boundaries = (str_idx == lim->subexp_from);
2024   boundaries |= (str_idx == lim->subexp_to) << 1;
2025   if (boundaries == 0)
2026     return 0;
2027
2028   /* Else, examine epsilon closure.  */
2029   return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2030                                       from_node, bkref_idx);
2031 }
2032
2033 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2034    which are against limitations from DEST_NODES. */
2035
2036 static reg_errcode_t
2037 internal_function
2038 check_subexp_limits (re_dfa_t *dfa, re_node_set *dest_nodes,
2039                      const re_node_set *candidates, re_node_set *limits,
2040                      struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2041 {
2042   reg_errcode_t err;
2043   Idx node_idx, lim_idx;
2044
2045   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2046     {
2047       Idx subexp_idx;
2048       struct re_backref_cache_entry *ent;
2049       ent = bkref_ents + limits->elems[lim_idx];
2050
2051       if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2052         continue; /* This is unrelated limitation.  */
2053
2054       subexp_idx = dfa->nodes[ent->node].opr.idx;
2055       if (ent->subexp_to == str_idx)
2056         {
2057           Idx ops_node = REG_MISSING;
2058           Idx cls_node = REG_MISSING;
2059           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2060             {
2061               Idx node = dest_nodes->elems[node_idx];
2062               re_token_type_t type = dfa->nodes[node].type;
2063               if (type == OP_OPEN_SUBEXP
2064                   && subexp_idx == dfa->nodes[node].opr.idx)
2065                 ops_node = node;
2066               else if (type == OP_CLOSE_SUBEXP
2067                        && subexp_idx == dfa->nodes[node].opr.idx)
2068                 cls_node = node;
2069             }
2070
2071           /* Check the limitation of the open subexpression.  */
2072           /* Note that (ent->subexp_to = str_idx != ent->subexp_from).  */
2073           if (REG_VALID_INDEX (ops_node))
2074             {
2075               err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2076                                            candidates);
2077               if (BE (err != REG_NOERROR, 0))
2078                 return err;
2079             }
2080
2081           /* Check the limitation of the close subexpression.  */
2082           if (REG_VALID_INDEX (cls_node))
2083             for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2084               {
2085                 Idx node = dest_nodes->elems[node_idx];
2086                 if (!re_node_set_contains (dfa->inveclosures + node,
2087                                            cls_node)
2088                     && !re_node_set_contains (dfa->eclosures + node,
2089                                               cls_node))
2090                   {
2091                     /* It is against this limitation.
2092                        Remove it form the current sifted state.  */
2093                     err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2094                                                  candidates);
2095                     if (BE (err != REG_NOERROR, 0))
2096                       return err;
2097                     --node_idx;
2098                   }
2099               }
2100         }
2101       else /* (ent->subexp_to != str_idx)  */
2102         {
2103           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2104             {
2105               Idx node = dest_nodes->elems[node_idx];
2106               re_token_type_t type = dfa->nodes[node].type;
2107               if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2108                 {
2109                   if (subexp_idx != dfa->nodes[node].opr.idx)
2110                     continue;
2111                   /* It is against this limitation.
2112                      Remove it form the current sifted state.  */
2113                   err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2114                                                candidates);
2115                   if (BE (err != REG_NOERROR, 0))
2116                     return err;
2117                 }
2118             }
2119         }
2120     }
2121   return REG_NOERROR;
2122 }
2123
2124 static reg_errcode_t
2125 internal_function
2126 sift_states_bkref (re_match_context_t *mctx, re_sift_context_t *sctx,
2127                    Idx str_idx, const re_node_set *candidates)
2128 {
2129   re_dfa_t *const dfa = mctx->dfa;
2130   reg_errcode_t err;
2131   Idx node_idx, node;
2132   re_sift_context_t local_sctx;
2133   Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2134
2135   if (first_idx == REG_MISSING)
2136     return REG_NOERROR;
2137
2138   local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized.  */
2139
2140   for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2141     {
2142       Idx enabled_idx;
2143       re_token_type_t type;
2144       struct re_backref_cache_entry *entry;
2145       node = candidates->elems[node_idx];
2146       type = dfa->nodes[node].type;
2147       /* Avoid infinite loop for the REs like "()\1+".  */
2148       if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2149         continue;
2150       if (type != OP_BACK_REF)
2151         continue;
2152
2153       entry = mctx->bkref_ents + first_idx;
2154       enabled_idx = first_idx;
2155       do
2156         {
2157           bool ok;
2158           Idx subexp_len, to_idx, dst_node;
2159           re_dfastate_t *cur_state;
2160
2161           if (entry->node != node)
2162             continue;
2163           subexp_len = entry->subexp_to - entry->subexp_from;
2164           to_idx = str_idx + subexp_len;
2165           dst_node = (subexp_len ? dfa->nexts[node]
2166                       : dfa->edests[node].elems[0]);
2167
2168           if (to_idx > sctx->last_str_idx
2169               || sctx->sifted_states[to_idx] == NULL
2170               || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2171               || check_dst_limits (mctx, &sctx->limits, node,
2172                                    str_idx, dst_node, to_idx))
2173             continue;
2174
2175           if (local_sctx.sifted_states == NULL)
2176             {
2177               local_sctx = *sctx;
2178               err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2179               if (BE (err != REG_NOERROR, 0))
2180                 goto free_return;
2181             }
2182           local_sctx.last_node = node;
2183           local_sctx.last_str_idx = str_idx;
2184           ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2185           if (BE (! ok, 0))
2186             {
2187               err = REG_ESPACE;
2188               goto free_return;
2189             }
2190           cur_state = local_sctx.sifted_states[str_idx];
2191           err = sift_states_backward (mctx, &local_sctx);
2192           if (BE (err != REG_NOERROR, 0))
2193             goto free_return;
2194           if (sctx->limited_states != NULL)
2195             {
2196               err = merge_state_array (dfa, sctx->limited_states,
2197                                        local_sctx.sifted_states,
2198                                        str_idx + 1);
2199               if (BE (err != REG_NOERROR, 0))
2200                 goto free_return;
2201             }
2202           local_sctx.sifted_states[str_idx] = cur_state;
2203           re_node_set_remove (&local_sctx.limits, enabled_idx);
2204
2205           /* mctx->bkref_ents may have changed, reload the pointer.  */
2206           entry = mctx->bkref_ents + enabled_idx;
2207         }
2208       while (enabled_idx++, entry++->more);
2209     }
2210   err = REG_NOERROR;
2211  free_return:
2212   if (local_sctx.sifted_states != NULL)
2213     {
2214       re_node_set_free (&local_sctx.limits);
2215     }
2216
2217   return err;
2218 }
2219
2220
2221 #ifdef RE_ENABLE_I18N
2222 static int
2223 internal_function
2224 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2225                      Idx node_idx, Idx str_idx, Idx max_str_idx)
2226 {
2227   re_dfa_t *const dfa = mctx->dfa;
2228   int naccepted;
2229   /* Check the node can accept `multi byte'.  */
2230   naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2231   if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2232       !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2233                             dfa->nexts[node_idx]))
2234     /* The node can't accept the `multi byte', or the
2235        destination was already thrown away, then the node
2236        could't accept the current input `multi byte'.   */
2237     naccepted = 0;
2238   /* Otherwise, it is sure that the node could accept
2239      `naccepted' bytes input.  */
2240   return naccepted;
2241 }
2242 #endif /* RE_ENABLE_I18N */
2243
2244 \f
2245 /* Functions for state transition.  */
2246
2247 /* Return the next state to which the current state STATE will transit by
2248    accepting the current input byte, and update STATE_LOG if necessary.
2249    If STATE can accept a multibyte char/collating element/back reference
2250    update the destination of STATE_LOG.  */
2251
2252 static re_dfastate_t *
2253 internal_function
2254 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2255                re_dfastate_t *state)
2256 {
2257   re_dfastate_t **trtable;
2258   unsigned char ch;
2259
2260 #ifdef RE_ENABLE_I18N
2261   /* If the current state can accept multibyte.  */
2262   if (BE (state->accept_mb, 0))
2263     {
2264       *err = transit_state_mb (mctx, state);
2265       if (BE (*err != REG_NOERROR, 0))
2266         return NULL;
2267     }
2268 #endif /* RE_ENABLE_I18N */
2269
2270   /* Then decide the next state with the single byte.  */
2271 #if 0
2272   if (0)
2273     /* don't use transition table  */
2274     return transit_state_sb (err, mctx, state);
2275 #endif
2276
2277   /* Use transition table  */
2278   ch = re_string_fetch_byte (&mctx->input);
2279   for (;;)
2280     {
2281       trtable = state->trtable;
2282       if (BE (trtable != NULL, 1))
2283         return trtable[ch];
2284
2285       trtable = state->word_trtable;
2286       if (BE (trtable != NULL, 1))
2287         {
2288           unsigned int context;
2289           context
2290             = re_string_context_at (&mctx->input,
2291                                     re_string_cur_idx (&mctx->input) - 1,
2292                                     mctx->eflags);
2293           if (IS_WORD_CONTEXT (context))
2294             return trtable[ch + SBC_MAX];
2295           else
2296             return trtable[ch];
2297         }
2298
2299       if (!build_trtable (mctx->dfa, state))
2300         {
2301           *err = REG_ESPACE;
2302           return NULL;
2303         }
2304
2305       /* Retry, we now have a transition table.  */
2306     }
2307 }
2308
2309 /* Update the state_log if we need */
2310 re_dfastate_t *
2311 internal_function
2312 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2313                       re_dfastate_t *next_state)
2314 {
2315   re_dfa_t *const dfa = mctx->dfa;
2316   Idx cur_idx = re_string_cur_idx (&mctx->input);
2317
2318   if (cur_idx > mctx->state_log_top)
2319     {
2320       mctx->state_log[cur_idx] = next_state;
2321       mctx->state_log_top = cur_idx;
2322     }
2323   else if (mctx->state_log[cur_idx] == 0)
2324     {
2325       mctx->state_log[cur_idx] = next_state;
2326     }
2327   else
2328     {
2329       re_dfastate_t *pstate;
2330       unsigned int context;
2331       re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2332       /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2333          the destination of a multibyte char/collating element/
2334          back reference.  Then the next state is the union set of
2335          these destinations and the results of the transition table.  */
2336       pstate = mctx->state_log[cur_idx];
2337       log_nodes = pstate->entrance_nodes;
2338       if (next_state != NULL)
2339         {
2340           table_nodes = next_state->entrance_nodes;
2341           *err = re_node_set_init_union (&next_nodes, table_nodes,
2342                                              log_nodes);
2343           if (BE (*err != REG_NOERROR, 0))
2344             return NULL;
2345         }
2346       else
2347         next_nodes = *log_nodes;
2348       /* Note: We already add the nodes of the initial state,
2349          then we don't need to add them here.  */
2350
2351       context = re_string_context_at (&mctx->input,
2352                                       re_string_cur_idx (&mctx->input) - 1,
2353                                       mctx->eflags);
2354       next_state = mctx->state_log[cur_idx]
2355         = re_acquire_state_context (err, dfa, &next_nodes, context);
2356       /* We don't need to check errors here, since the return value of
2357          this function is next_state and ERR is already set.  */
2358
2359       if (table_nodes != NULL)
2360         re_node_set_free (&next_nodes);
2361     }
2362
2363   if (BE (dfa->nbackref, 0) && next_state != NULL)
2364     {
2365       /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2366          later.  We must check them here, since the back references in the
2367          next state might use them.  */
2368       *err = check_subexp_matching_top (mctx, &next_state->nodes,
2369                                         cur_idx);
2370       if (BE (*err != REG_NOERROR, 0))
2371         return NULL;
2372
2373       /* If the next state has back references.  */
2374       if (next_state->has_backref)
2375         {
2376           *err = transit_state_bkref (mctx, &next_state->nodes);
2377           if (BE (*err != REG_NOERROR, 0))
2378             return NULL;
2379           next_state = mctx->state_log[cur_idx];
2380         }
2381     }
2382
2383   return next_state;
2384 }
2385
2386 /* Skip bytes in the input that correspond to part of a
2387    multi-byte match, then look in the log for a state
2388    from which to restart matching.  */
2389 static re_dfastate_t *
2390 internal_function
2391 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2392 {
2393   re_dfastate_t *cur_state = NULL;
2394   do
2395     {
2396       Idx max = mctx->state_log_top;
2397       Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2398
2399       do
2400         {
2401           if (++cur_str_idx > max)
2402             return NULL;
2403           re_string_skip_bytes (&mctx->input, 1);
2404         }
2405       while (mctx->state_log[cur_str_idx] == NULL);
2406
2407       cur_state = merge_state_with_log (err, mctx, NULL);
2408     }
2409   while (*err == REG_NOERROR && cur_state == NULL);
2410   return cur_state;
2411 }
2412
2413 /* Helper functions for transit_state.  */
2414
2415 /* From the node set CUR_NODES, pick up the nodes whose types are
2416    OP_OPEN_SUBEXP and which have corresponding back references in the regular
2417    expression. And register them to use them later for evaluating the
2418    correspoding back references.  */
2419
2420 static reg_errcode_t
2421 internal_function
2422 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2423                            Idx str_idx)
2424 {
2425   re_dfa_t *const dfa = mctx->dfa;
2426   Idx node_idx;
2427   reg_errcode_t err;
2428
2429   /* TODO: This isn't efficient.
2430            Because there might be more than one nodes whose types are
2431            OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2432            nodes.
2433            E.g. RE: (a){2}  */
2434   for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2435     {
2436       Idx node = cur_nodes->elems[node_idx];
2437       if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2438           && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2439           && (dfa->used_bkref_map
2440               & ((bitset_word) 1 << dfa->nodes[node].opr.idx)))
2441         {
2442           err = match_ctx_add_subtop (mctx, node, str_idx);
2443           if (BE (err != REG_NOERROR, 0))
2444             return err;
2445         }
2446     }
2447   return REG_NOERROR;
2448 }
2449
2450 #if 0
2451 /* Return the next state to which the current state STATE will transit by
2452    accepting the current input byte.  */
2453
2454 static re_dfastate_t *
2455 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2456                   re_dfastate_t *state)
2457 {
2458   re_dfa_t *const dfa = mctx->dfa;
2459   re_node_set next_nodes;
2460   re_dfastate_t *next_state;
2461   Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2462   unsigned int context;
2463
2464   *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2465   if (BE (*err != REG_NOERROR, 0))
2466     return NULL;
2467   for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2468     {
2469       Idx cur_node = state->nodes.elems[node_cnt];
2470       if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2471         {
2472           *err = re_node_set_merge (&next_nodes,
2473                                     dfa->eclosures + dfa->nexts[cur_node]);
2474           if (BE (*err != REG_NOERROR, 0))
2475             {
2476               re_node_set_free (&next_nodes);
2477               return NULL;
2478             }
2479         }
2480     }
2481   context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2482   next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2483   /* We don't need to check errors here, since the return value of
2484      this function is next_state and ERR is already set.  */
2485
2486   re_node_set_free (&next_nodes);
2487   re_string_skip_bytes (&mctx->input, 1);
2488   return next_state;
2489 }
2490 #endif
2491
2492 #ifdef RE_ENABLE_I18N
2493 static reg_errcode_t
2494 internal_function
2495 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2496 {
2497   re_dfa_t *const dfa = mctx->dfa;
2498   reg_errcode_t err;
2499   Idx i;
2500
2501   for (i = 0; i < pstate->nodes.nelem; ++i)
2502     {
2503       re_node_set dest_nodes, *new_nodes;
2504       Idx cur_node_idx = pstate->nodes.elems[i];
2505       int naccepted;
2506       Idx dest_idx;
2507       unsigned int context;
2508       re_dfastate_t *dest_state;
2509
2510       if (!dfa->nodes[cur_node_idx].accept_mb)
2511         continue;
2512
2513       if (dfa->nodes[cur_node_idx].constraint)
2514         {
2515           context = re_string_context_at (&mctx->input,
2516                                           re_string_cur_idx (&mctx->input),
2517                                           mctx->eflags);
2518           if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2519                                            context))
2520             continue;
2521         }
2522
2523       /* How many bytes the node can accept?  */
2524       naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2525                                            re_string_cur_idx (&mctx->input));
2526       if (naccepted == 0)
2527         continue;
2528
2529       /* The node can accepts `naccepted' bytes.  */
2530       dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2531       mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2532                                : mctx->max_mb_elem_len);
2533       err = clean_state_log_if_needed (mctx, dest_idx);
2534       if (BE (err != REG_NOERROR, 0))
2535         return err;
2536 #ifdef DEBUG
2537       assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2538 #endif
2539       new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2540
2541       dest_state = mctx->state_log[dest_idx];
2542       if (dest_state == NULL)
2543         dest_nodes = *new_nodes;
2544       else
2545         {
2546           err = re_node_set_init_union (&dest_nodes,
2547                                         dest_state->entrance_nodes, new_nodes);
2548           if (BE (err != REG_NOERROR, 0))
2549             return err;
2550         }
2551       context = re_string_context_at (&mctx->input, dest_idx - 1, mctx->eflags);
2552       mctx->state_log[dest_idx]
2553         = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2554       if (dest_state != NULL)
2555         re_node_set_free (&dest_nodes);
2556       if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2557         return err;
2558     }
2559   return REG_NOERROR;
2560 }
2561 #endif /* RE_ENABLE_I18N */
2562
2563 static reg_errcode_t
2564 internal_function
2565 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2566 {
2567   re_dfa_t *const dfa = mctx->dfa;
2568   reg_errcode_t err;
2569   Idx i;
2570   Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2571
2572   for (i = 0; i < nodes->nelem; ++i)
2573     {
2574       Idx dest_str_idx, prev_nelem, bkc_idx;
2575       Idx node_idx = nodes->elems[i];
2576       unsigned int context;
2577       const re_token_t *node = dfa->nodes + node_idx;
2578       re_node_set *new_dest_nodes;
2579
2580       /* Check whether `node' is a backreference or not.  */
2581       if (node->type != OP_BACK_REF)
2582         continue;
2583
2584       if (node->constraint)
2585         {
2586           context = re_string_context_at (&mctx->input, cur_str_idx,
2587                                           mctx->eflags);
2588           if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2589             continue;
2590         }
2591
2592       /* `node' is a backreference.
2593          Check the substring which the substring matched.  */
2594       bkc_idx = mctx->nbkref_ents;
2595       err = get_subexp (mctx, node_idx, cur_str_idx);
2596       if (BE (err != REG_NOERROR, 0))
2597         goto free_return;
2598
2599       /* And add the epsilon closures (which is `new_dest_nodes') of
2600          the backreference to appropriate state_log.  */
2601 #ifdef DEBUG
2602       assert (dfa->nexts[node_idx] != REG_MISSING);
2603 #endif
2604       for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2605         {
2606           Idx subexp_len;
2607           re_dfastate_t *dest_state;
2608           struct re_backref_cache_entry *bkref_ent;
2609           bkref_ent = mctx->bkref_ents + bkc_idx;
2610           if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2611             continue;
2612           subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2613           new_dest_nodes = (subexp_len == 0
2614                             ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2615                             : dfa->eclosures + dfa->nexts[node_idx]);
2616           dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2617                           - bkref_ent->subexp_from);
2618           context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2619                                           mctx->eflags);
2620           dest_state = mctx->state_log[dest_str_idx];
2621           prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2622                         : mctx->state_log[cur_str_idx]->nodes.nelem);
2623           /* Add `new_dest_node' to state_log.  */
2624           if (dest_state == NULL)
2625             {
2626               mctx->state_log[dest_str_idx]
2627                 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2628                                             context);
2629               if (BE (mctx->state_log[dest_str_idx] == NULL
2630                       && err != REG_NOERROR, 0))
2631                 goto free_return;
2632             }
2633           else
2634             {
2635               re_node_set dest_nodes;
2636               err = re_node_set_init_union (&dest_nodes,
2637                                             dest_state->entrance_nodes,
2638                                             new_dest_nodes);
2639               if (BE (err != REG_NOERROR, 0))
2640                 {
2641                   re_node_set_free (&dest_nodes);
2642                   goto free_return;
2643                 }
2644               mctx->state_log[dest_str_idx]
2645                 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2646               re_node_set_free (&dest_nodes);
2647               if (BE (mctx->state_log[dest_str_idx] == NULL
2648                       && err != REG_NOERROR, 0))
2649                 goto free_return;
2650             }
2651           /* We need to check recursively if the backreference can epsilon
2652              transit.  */
2653           if (subexp_len == 0
2654               && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2655             {
2656               err = check_subexp_matching_top (mctx, new_dest_nodes,
2657                                                cur_str_idx);
2658               if (BE (err != REG_NOERROR, 0))
2659                 goto free_return;
2660               err = transit_state_bkref (mctx, new_dest_nodes);
2661               if (BE (err != REG_NOERROR, 0))
2662                 goto free_return;
2663             }
2664         }
2665     }
2666   err = REG_NOERROR;
2667  free_return:
2668   return err;
2669 }
2670
2671 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2672    at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2673    Note that we might collect inappropriate candidates here.
2674    However, the cost of checking them strictly here is too high, then we
2675    delay these checking for prune_impossible_nodes().  */
2676
2677 static reg_errcode_t
2678 internal_function
2679 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2680 {
2681   re_dfa_t *const dfa = mctx->dfa;
2682   Idx subexp_num, sub_top_idx;
2683   const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2684   /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX.  */
2685   Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2686   if (cache_idx != REG_MISSING)
2687     {
2688       const struct re_backref_cache_entry *entry = mctx->bkref_ents + cache_idx;
2689       do
2690         if (entry->node == bkref_node)
2691           return REG_NOERROR; /* We already checked it.  */
2692       while (entry++->more);
2693     }
2694
2695   subexp_num = dfa->nodes[bkref_node].opr.idx;
2696
2697   /* For each sub expression  */
2698   for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2699     {
2700       reg_errcode_t err;
2701       re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2702       re_sub_match_last_t *sub_last;
2703       Idx sub_last_idx, sl_str, bkref_str_off;
2704
2705       if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2706         continue; /* It isn't related.  */
2707
2708       sl_str = sub_top->str_idx;
2709       bkref_str_off = bkref_str_idx;
2710       /* At first, check the last node of sub expressions we already
2711          evaluated.  */
2712       for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2713         {
2714           regoff_t sl_str_diff;
2715           sub_last = sub_top->lasts[sub_last_idx];
2716           sl_str_diff = sub_last->str_idx - sl_str;
2717           /* The matched string by the sub expression match with the substring
2718              at the back reference?  */
2719           if (sl_str_diff > 0)
2720             {
2721               if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2722                 {
2723                   /* Not enough chars for a successful match.  */
2724                   if (bkref_str_off + sl_str_diff > mctx->input.len)
2725                     break;
2726
2727                   err = clean_state_log_if_needed (mctx,
2728                                                    bkref_str_off
2729                                                    + sl_str_diff);
2730                   if (BE (err != REG_NOERROR, 0))
2731                     return err;
2732                   buf = (const char *) re_string_get_buffer (&mctx->input);
2733                 }
2734               if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2735                 break; /* We don't need to search this sub expression any more.  */
2736             }
2737           bkref_str_off += sl_str_diff;
2738           sl_str += sl_str_diff;
2739           err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2740                                 bkref_str_idx);
2741
2742           /* Reload buf, since the preceding call might have reallocated
2743              the buffer.  */
2744           buf = (const char *) re_string_get_buffer (&mctx->input);
2745
2746           if (err == REG_NOMATCH)
2747             continue;
2748           if (BE (err != REG_NOERROR, 0))
2749             return err;
2750         }
2751
2752       if (sub_last_idx < sub_top->nlasts)
2753         continue;
2754       if (sub_last_idx > 0)
2755         ++sl_str;
2756       /* Then, search for the other last nodes of the sub expression.  */
2757       for (; sl_str <= bkref_str_idx; ++sl_str)
2758         {
2759           Idx cls_node;
2760           regoff_t sl_str_off;
2761           const re_node_set *nodes;
2762           sl_str_off = sl_str - sub_top->str_idx;
2763           /* The matched string by the sub expression match with the substring
2764              at the back reference?  */
2765           if (sl_str_off > 0)
2766             {
2767               if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2768                 {
2769                   /* If we are at the end of the input, we cannot match.  */
2770                   if (bkref_str_off >= mctx->input.len)
2771                     break;
2772
2773                   err = extend_buffers (mctx);
2774                   if (BE (err != REG_NOERROR, 0))
2775                     return err;
2776
2777                   buf = (const char *) re_string_get_buffer (&mctx->input);
2778                 }
2779               if (buf [bkref_str_off++] != buf[sl_str - 1])
2780                 break; /* We don't need to search this sub expression
2781                           any more.  */
2782             }
2783           if (mctx->state_log[sl_str] == NULL)
2784             continue;
2785           /* Does this state have a ')' of the sub expression?  */
2786           nodes = &mctx->state_log[sl_str]->nodes;
2787           cls_node = find_subexp_node (dfa, nodes, subexp_num, OP_CLOSE_SUBEXP);
2788           if (cls_node == REG_MISSING)
2789             continue; /* No.  */
2790           if (sub_top->path == NULL)
2791             {
2792               sub_top->path = re_calloc (state_array_t,
2793                                          sl_str - sub_top->str_idx + 1);
2794               if (sub_top->path == NULL)
2795                 return REG_ESPACE;
2796             }
2797           /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2798              in the current context?  */
2799           err = check_arrival (mctx, sub_top->path, sub_top->node,
2800                                sub_top->str_idx, cls_node, sl_str, OP_CLOSE_SUBEXP);
2801           if (err == REG_NOMATCH)
2802               continue;
2803           if (BE (err != REG_NOERROR, 0))
2804               return err;
2805           sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2806           if (BE (sub_last == NULL, 0))
2807             return REG_ESPACE;
2808           err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2809                                 bkref_str_idx);
2810           if (err == REG_NOMATCH)
2811             continue;
2812         }
2813     }
2814   return REG_NOERROR;
2815 }
2816
2817 /* Helper functions for get_subexp().  */
2818
2819 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2820    If it can arrive, register the sub expression expressed with SUB_TOP
2821    and SUB_LAST.  */
2822
2823 static reg_errcode_t
2824 internal_function
2825 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2826                 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2827 {
2828   reg_errcode_t err;
2829   Idx to_idx;
2830   /* Can the subexpression arrive the back reference?  */
2831   err = check_arrival (mctx, &sub_last->path, sub_last->node,
2832                        sub_last->str_idx, bkref_node, bkref_str, OP_OPEN_SUBEXP);
2833   if (err != REG_NOERROR)
2834     return err;
2835   err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2836                              sub_last->str_idx);
2837   if (BE (err != REG_NOERROR, 0))
2838     return err;
2839   to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2840   return clean_state_log_if_needed (mctx, to_idx);
2841 }
2842
2843 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2844    Search '(' if FL_OPEN, or search ')' otherwise.
2845    TODO: This function isn't efficient...
2846          Because there might be more than one nodes whose types are
2847          OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2848          nodes.
2849          E.g. RE: (a){2}  */
2850
2851 static Idx
2852 internal_function
2853 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2854                   Idx subexp_idx, int type)
2855 {
2856   Idx cls_idx;
2857   for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2858     {
2859       Idx cls_node = nodes->elems[cls_idx];
2860       const re_token_t *node = dfa->nodes + cls_node;
2861       if (node->type == type
2862           && node->opr.idx == subexp_idx)
2863         return cls_node;
2864     }
2865   return REG_MISSING;
2866 }
2867
2868 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2869    LAST_NODE at LAST_STR.  We record the path onto PATH since it will be
2870    heavily reused.
2871    Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise.  */
2872
2873 static reg_errcode_t
2874 internal_function
2875 check_arrival (re_match_context_t *mctx, state_array_t *path,
2876                Idx top_node, Idx top_str, Idx last_node, Idx last_str,
2877                int type)
2878 {
2879   re_dfa_t *const dfa = mctx->dfa;
2880   reg_errcode_t err;
2881   Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2882   re_dfastate_t *cur_state = NULL;
2883   re_node_set *cur_nodes, next_nodes;
2884   re_dfastate_t **backup_state_log;
2885   unsigned int context;
2886
2887   subexp_num = dfa->nodes[top_node].opr.idx;
2888   /* Extend the buffer if we need.  */
2889   if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2890     {
2891       re_dfastate_t **new_array;
2892       Idx old_alloc = path->alloc;
2893       Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2894       if (BE (new_alloc < old_alloc, 0))
2895         return REG_ESPACE;
2896       new_array = re_xrealloc (path->array, re_dfastate_t *, new_alloc);
2897       if (BE (new_array == NULL, 0))
2898         return REG_ESPACE;
2899       path->array = new_array;
2900       path->alloc = new_alloc;
2901       memset (new_array + old_alloc, '\0',
2902               sizeof (re_dfastate_t *) * (new_alloc - old_alloc));
2903     }
2904
2905   str_idx = path->next_idx == 0 ? top_str : path->next_idx;
2906
2907   /* Temporary modify MCTX.  */
2908   backup_state_log = mctx->state_log;
2909   backup_cur_idx = mctx->input.cur_idx;
2910   mctx->state_log = path->array;
2911   mctx->input.cur_idx = str_idx;
2912
2913   /* Setup initial node set.  */
2914   context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2915   if (str_idx == top_str)
2916     {
2917       err = re_node_set_init_1 (&next_nodes, top_node);
2918       if (BE (err != REG_NOERROR, 0))
2919         return err;
2920       err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2921       if (BE (err != REG_NOERROR, 0))
2922         {
2923           re_node_set_free (&next_nodes);
2924           return err;
2925         }
2926     }
2927   else
2928     {
2929       cur_state = mctx->state_log[str_idx];
2930       if (cur_state && cur_state->has_backref)
2931         {
2932           err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2933           if (BE ( err != REG_NOERROR, 0))
2934             return err;
2935         }
2936       else
2937         re_node_set_init_empty (&next_nodes);
2938     }
2939   if (str_idx == top_str || (cur_state && cur_state->has_backref))
2940     {
2941       if (next_nodes.nelem)
2942         {
2943           err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2944                                     subexp_num, type);
2945           if (BE ( err != REG_NOERROR, 0))
2946             {
2947               re_node_set_free (&next_nodes);
2948               return err;
2949             }
2950         }
2951       cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2952       if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2953         {
2954           re_node_set_free (&next_nodes);
2955           return err;
2956         }
2957       mctx->state_log[str_idx] = cur_state;
2958     }
2959
2960   for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
2961     {
2962       re_node_set_empty (&next_nodes);
2963       if (mctx->state_log[str_idx + 1])
2964         {
2965           err = re_node_set_merge (&next_nodes,
2966                                    &mctx->state_log[str_idx + 1]->nodes);
2967           if (BE (err != REG_NOERROR, 0))
2968             {
2969               re_node_set_free (&next_nodes);
2970               return err;
2971             }
2972         }
2973       if (cur_state)
2974         {
2975           err = check_arrival_add_next_nodes (mctx, str_idx,
2976                                               &cur_state->non_eps_nodes, &next_nodes);
2977           if (BE (err != REG_NOERROR, 0))
2978             {
2979               re_node_set_free (&next_nodes);
2980               return err;
2981             }
2982         }
2983       ++str_idx;
2984       if (next_nodes.nelem)
2985         {
2986           err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2987           if (BE (err != REG_NOERROR, 0))
2988             {
2989               re_node_set_free (&next_nodes);
2990               return err;
2991             }
2992           err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2993                                     subexp_num, type);
2994           if (BE ( err != REG_NOERROR, 0))
2995             {
2996               re_node_set_free (&next_nodes);
2997               return err;
2998             }
2999         }
3000       context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3001       cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3002       if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3003         {
3004           re_node_set_free (&next_nodes);
3005           return err;
3006         }
3007       mctx->state_log[str_idx] = cur_state;
3008       null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3009     }
3010   re_node_set_free (&next_nodes);
3011   cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3012                : &mctx->state_log[last_str]->nodes);
3013   path->next_idx = str_idx;
3014
3015   /* Fix MCTX.  */
3016   mctx->state_log = backup_state_log;
3017   mctx->input.cur_idx = backup_cur_idx;
3018
3019   /* Then check the current node set has the node LAST_NODE.  */
3020   if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3021     return REG_NOERROR;
3022
3023   return REG_NOMATCH;
3024 }
3025
3026 /* Helper functions for check_arrival.  */
3027
3028 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3029    to NEXT_NODES.
3030    TODO: This function is similar to the functions transit_state*(),
3031          however this function has many additional works.
3032          Can't we unify them?  */
3033
3034 static reg_errcode_t
3035 internal_function
3036 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3037                               re_node_set *cur_nodes,
3038                               re_node_set *next_nodes)
3039 {
3040   re_dfa_t *const dfa = mctx->dfa;
3041   bool ok;
3042   Idx cur_idx;
3043   reg_errcode_t err;
3044   re_node_set union_set;
3045   re_node_set_init_empty (&union_set);
3046   for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3047     {
3048       int naccepted = 0;
3049       Idx cur_node = cur_nodes->elems[cur_idx];
3050 #ifdef DEBUG
3051       re_token_type_t type = dfa->nodes[cur_node].type;
3052       assert (!IS_EPSILON_NODE (type));
3053 #endif
3054 #ifdef RE_ENABLE_I18N
3055       /* If the node may accept `multi byte'.  */
3056       if (dfa->nodes[cur_node].accept_mb)
3057         {
3058           naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3059                                                str_idx);
3060           if (naccepted > 1)
3061             {
3062               re_dfastate_t *dest_state;
3063               Idx next_node = dfa->nexts[cur_node];
3064               Idx next_idx = str_idx + naccepted;
3065               dest_state = mctx->state_log[next_idx];
3066               re_node_set_empty (&union_set);
3067               if (dest_state)
3068                 {
3069                   err = re_node_set_merge (&union_set, &dest_state->nodes);
3070                   if (BE (err != REG_NOERROR, 0))
3071                     {
3072                       re_node_set_free (&union_set);
3073                       return err;
3074                     }
3075                 }
3076               ok = re_node_set_insert (&union_set, next_node);
3077               if (BE (! ok, 0))
3078                 {
3079                   re_node_set_free (&union_set);
3080                   return REG_ESPACE;
3081                 }
3082               mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3083                                                             &union_set);
3084               if (BE (mctx->state_log[next_idx] == NULL
3085                       && err != REG_NOERROR, 0))
3086                 {
3087                   re_node_set_free (&union_set);
3088                   return err;
3089                 }
3090             }
3091         }
3092 #endif /* RE_ENABLE_I18N */
3093       if (naccepted
3094           || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3095         {
3096           ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3097           if (BE (! ok, 0))
3098             {
3099               re_node_set_free (&union_set);
3100               return REG_ESPACE;
3101             }
3102         }
3103     }
3104   re_node_set_free (&union_set);
3105   return REG_NOERROR;
3106 }
3107
3108 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3109    CUR_NODES, however exclude the nodes which are:
3110     - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3111     - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3112 */
3113
3114 static reg_errcode_t
3115 internal_function
3116 check_arrival_expand_ecl (re_dfa_t *dfa, re_node_set *cur_nodes,
3117                           Idx ex_subexp, int type)
3118 {
3119   reg_errcode_t err;
3120   Idx idx, outside_node;
3121   re_node_set new_nodes;
3122 #ifdef DEBUG
3123   assert (cur_nodes->nelem);
3124 #endif
3125   err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3126   if (BE (err != REG_NOERROR, 0))
3127     return err;
3128   /* Create a new node set NEW_NODES with the nodes which are epsilon
3129      closures of the node in CUR_NODES.  */
3130
3131   for (idx = 0; idx < cur_nodes->nelem; ++idx)
3132     {
3133       Idx cur_node = cur_nodes->elems[idx];
3134       re_node_set *eclosure = dfa->eclosures + cur_node;
3135       outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3136       if (outside_node == REG_MISSING)
3137         {
3138           /* There are no problematic nodes, just merge them.  */
3139           err = re_node_set_merge (&new_nodes, eclosure);
3140           if (BE (err != REG_NOERROR, 0))
3141             {
3142               re_node_set_free (&new_nodes);
3143               return err;
3144             }
3145         }
3146       else
3147         {
3148           /* There are problematic nodes, re-calculate incrementally.  */
3149           err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3150                                               ex_subexp, type);
3151           if (BE (err != REG_NOERROR, 0))
3152             {
3153               re_node_set_free (&new_nodes);
3154               return err;
3155             }
3156         }
3157     }
3158   re_node_set_free (cur_nodes);
3159   *cur_nodes = new_nodes;
3160   return REG_NOERROR;
3161 }
3162
3163 /* Helper function for check_arrival_expand_ecl.
3164    Check incrementally the epsilon closure of TARGET, and if it isn't
3165    problematic append it to DST_NODES.  */
3166
3167 static reg_errcode_t
3168 internal_function
3169 check_arrival_expand_ecl_sub (re_dfa_t *dfa, re_node_set *dst_nodes,
3170                               Idx target, Idx ex_subexp, int type)
3171 {
3172   Idx cur_node;
3173   for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3174     {
3175       bool ok;
3176
3177       if (dfa->nodes[cur_node].type == type
3178           && dfa->nodes[cur_node].opr.idx == ex_subexp)
3179         {
3180           if (type == OP_CLOSE_SUBEXP)
3181             {
3182               ok = re_node_set_insert (dst_nodes, cur_node);
3183               if (BE (! ok, 0))
3184                 return REG_ESPACE;
3185             }
3186           break;
3187         }
3188       ok = re_node_set_insert (dst_nodes, cur_node);
3189       if (BE (! ok, 0))
3190         return REG_ESPACE;
3191       if (dfa->edests[cur_node].nelem == 0)
3192         break;
3193       if (dfa->edests[cur_node].nelem == 2)
3194         {
3195           reg_errcode_t ret =
3196             check_arrival_expand_ecl_sub (dfa, dst_nodes,
3197                                           dfa->edests[cur_node].elems[1],
3198                                           ex_subexp, type);
3199           if (BE (ret != REG_NOERROR, 0))
3200             return ret;
3201         }
3202       cur_node = dfa->edests[cur_node].elems[0];
3203     }
3204   return REG_NOERROR;
3205 }
3206
3207
3208 /* For all the back references in the current state, calculate the
3209    destination of the back references by the appropriate entry
3210    in MCTX->BKREF_ENTS.  */
3211
3212 static reg_errcode_t
3213 internal_function
3214 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3215                     Idx cur_str, Idx subexp_num, int type)
3216 {
3217   re_dfa_t *const dfa = mctx->dfa;
3218   reg_errcode_t err;
3219   Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3220   struct re_backref_cache_entry *ent;
3221
3222   if (cache_idx_start == REG_MISSING)
3223     return REG_NOERROR;
3224
3225  restart:
3226   ent = mctx->bkref_ents + cache_idx_start;
3227   do
3228     {
3229       Idx to_idx, next_node;
3230
3231       /* Is this entry ENT is appropriate?  */
3232       if (!re_node_set_contains (cur_nodes, ent->node))
3233         continue; /* No.  */
3234
3235       to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3236       /* Calculate the destination of the back reference, and append it
3237          to MCTX->STATE_LOG.  */
3238       if (to_idx == cur_str)
3239         {
3240           /* The backreference did epsilon transit, we must re-check all the
3241              node in the current state.  */
3242           re_node_set new_dests;
3243           reg_errcode_t err2, err3;
3244           next_node = dfa->edests[ent->node].elems[0];
3245           if (re_node_set_contains (cur_nodes, next_node))
3246             continue;
3247           err = re_node_set_init_1 (&new_dests, next_node);
3248           err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3249           err3 = re_node_set_merge (cur_nodes, &new_dests);
3250           re_node_set_free (&new_dests);
3251           if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3252                   || err3 != REG_NOERROR, 0))
3253             {
3254               err = (err != REG_NOERROR ? err
3255                      : (err2 != REG_NOERROR ? err2 : err3));
3256               return err;
3257             }
3258           /* TODO: It is still inefficient...  */
3259           goto restart;
3260         }
3261       else
3262         {
3263           re_node_set union_set;
3264           next_node = dfa->nexts[ent->node];
3265           if (mctx->state_log[to_idx])
3266             {
3267               bool ok;
3268               if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3269                                         next_node))
3270                 continue;
3271               err = re_node_set_init_copy (&union_set,
3272                                            &mctx->state_log[to_idx]->nodes);
3273               ok = re_node_set_insert (&union_set, next_node);
3274               if (BE (err != REG_NOERROR || ! ok, 0))
3275                 {
3276                   re_node_set_free (&union_set);
3277                   err = err != REG_NOERROR ? err : REG_ESPACE;
3278                   return err;
3279                 }
3280             }
3281           else
3282             {
3283               err = re_node_set_init_1 (&union_set, next_node);
3284               if (BE (err != REG_NOERROR, 0))
3285                 return err;
3286             }
3287           mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3288           re_node_set_free (&union_set);
3289           if (BE (mctx->state_log[to_idx] == NULL
3290                   && err != REG_NOERROR, 0))
3291             return err;
3292         }
3293     }
3294   while (ent++->more);
3295   return REG_NOERROR;
3296 }
3297
3298 /* Build transition table for the state.
3299    Return true if successful.  */
3300
3301 static bool
3302 internal_function
3303 build_trtable (re_dfa_t *dfa, re_dfastate_t *state)
3304 {
3305   reg_errcode_t err;
3306   Idx i, j;
3307   int ch;
3308   bool need_word_trtable = false;
3309   bitset_word elem, mask;
3310   bool dests_node_malloced = false, dest_states_malloced = false;
3311   Idx ndests; /* Number of the destination states from `state'.  */
3312   re_dfastate_t **trtable;
3313   re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3314   re_node_set follows, *dests_node;
3315   bitset *dests_ch;
3316   bitset acceptable;
3317
3318   struct dests_alloc
3319   {
3320     re_node_set dests_node[SBC_MAX];
3321     bitset dests_ch[SBC_MAX];
3322   } *dests_alloc;
3323
3324   /* We build DFA states which corresponds to the destination nodes
3325      from `state'.  `dests_node[i]' represents the nodes which i-th
3326      destination state contains, and `dests_ch[i]' represents the
3327      characters which i-th destination state accepts.  */
3328   if (__libc_use_alloca (sizeof (struct dests_alloc)))
3329     dests_alloc = (struct dests_alloc *) alloca (sizeof dests_alloc[0]);
3330   else
3331     {
3332       dests_alloc = re_malloc (struct dests_alloc, 1);
3333       if (BE (dests_alloc == NULL, 0))
3334         return false;
3335       dests_node_malloced = true;
3336     }
3337   dests_node = dests_alloc->dests_node;
3338   dests_ch = dests_alloc->dests_ch;
3339
3340   /* Initialize transiton table.  */
3341   state->word_trtable = state->trtable = NULL;
3342
3343   /* At first, group all nodes belonging to `state' into several
3344      destinations.  */
3345   ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3346   if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3347     {
3348       if (dests_node_malloced)
3349         free (dests_alloc);
3350       if (ndests == 0)
3351         {
3352           state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3353           return true;
3354         }
3355       return false;
3356     }
3357
3358   err = re_node_set_alloc (&follows, ndests + 1);
3359   if (BE (err != REG_NOERROR, 0))
3360     goto out_free;
3361
3362   /* Avoid arithmetic overflow in size calculation.  */
3363   if (BE (((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX)
3364            / (3 * sizeof (re_dfastate_t *)))
3365           < ndests, 0))
3366     goto out_free;
3367
3368   if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX
3369                          + ndests * 3 * sizeof (re_dfastate_t *)))
3370     dest_states = (re_dfastate_t **)
3371       alloca (ndests * 3 * sizeof (re_dfastate_t *));
3372   else
3373     {
3374       dest_states = (re_dfastate_t **)
3375         malloc (ndests * 3 * sizeof (re_dfastate_t *));
3376       if (BE (dest_states == NULL, 0))
3377         {
3378 out_free:
3379           if (dest_states_malloced)
3380             free (dest_states);
3381           re_node_set_free (&follows);
3382           for (i = 0; i < ndests; ++i)
3383             re_node_set_free (dests_node + i);
3384           if (dests_node_malloced)
3385             free (dests_alloc);
3386           return false;
3387         }
3388       dest_states_malloced = true;
3389     }
3390   dest_states_word = dest_states + ndests;
3391   dest_states_nl = dest_states_word + ndests;
3392   bitset_empty (acceptable);
3393
3394   /* Then build the states for all destinations.  */
3395   for (i = 0; i < ndests; ++i)
3396     {
3397       Idx next_node;
3398       re_node_set_empty (&follows);
3399       /* Merge the follows of this destination states.  */
3400       for (j = 0; j < dests_node[i].nelem; ++j)
3401         {
3402           next_node = dfa->nexts[dests_node[i].elems[j]];
3403           if (next_node != REG_MISSING)
3404             {
3405               err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3406               if (BE (err != REG_NOERROR, 0))
3407                 goto out_free;
3408             }
3409         }
3410       dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3411       if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3412         goto out_free;
3413       /* If the new state has context constraint,
3414          build appropriate states for these contexts.  */
3415       if (dest_states[i]->has_constraint)
3416         {
3417           dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3418                                                           CONTEXT_WORD);
3419           if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3420             goto out_free;
3421
3422           if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3423             need_word_trtable = true;
3424
3425           dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3426                                                         CONTEXT_NEWLINE);
3427           if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3428             goto out_free;
3429         }
3430       else
3431         {
3432           dest_states_word[i] = dest_states[i];
3433           dest_states_nl[i] = dest_states[i];
3434         }
3435       bitset_merge (acceptable, dests_ch[i]);
3436     }
3437
3438   if (!BE (need_word_trtable, 0))
3439     {
3440       /* We don't care about whether the following character is a word
3441          character, or we are in a single-byte character set so we can
3442          discern by looking at the character code: allocate a
3443          256-entry transition table.  */
3444       trtable = state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3445       if (BE (trtable == NULL, 0))
3446         goto out_free;
3447
3448       /* For all characters ch...:  */
3449       for (i = 0; i < BITSET_WORDS; ++i)
3450         for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3451              elem;
3452              mask <<= 1, elem >>= 1, ++ch)
3453           if (BE (elem & 1, 0))
3454             {
3455               /* There must be exactly one destination which accepts
3456                  character ch.  See group_nodes_into_DFAstates.  */
3457               for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3458                 ;
3459
3460               /* j-th destination accepts the word character ch.  */
3461               if (dfa->word_char[i] & mask)
3462                 trtable[ch] = dest_states_word[j];
3463               else
3464                 trtable[ch] = dest_states[j];
3465             }
3466     }
3467   else
3468     {
3469       /* We care about whether the following character is a word
3470          character, and we are in a multi-byte character set: discern
3471          by looking at the character code: build two 256-entry
3472          transition tables, one starting at trtable[0] and one
3473          starting at trtable[SBC_MAX].  */
3474       trtable = state->word_trtable = re_calloc (re_dfastate_t *, 2 * SBC_MAX);
3475       if (BE (trtable == NULL, 0))
3476         goto out_free;
3477
3478       /* For all characters ch...:  */
3479       for (i = 0; i < BITSET_WORDS; ++i)
3480         for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3481              elem;
3482              mask <<= 1, elem >>= 1, ++ch)
3483           if (BE (elem & 1, 0))
3484             {
3485               /* There must be exactly one destination which accepts
3486                  character ch.  See group_nodes_into_DFAstates.  */
3487               for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3488                 ;
3489
3490               /* j-th destination accepts the word character ch.  */
3491               trtable[ch] = dest_states[j];
3492               trtable[ch + SBC_MAX] = dest_states_word[j];
3493             }
3494     }
3495
3496   /* new line */
3497   if (bitset_contain (acceptable, NEWLINE_CHAR))
3498     {
3499       /* The current state accepts newline character.  */
3500       for (j = 0; j < ndests; ++j)
3501         if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3502           {
3503             /* k-th destination accepts newline character.  */
3504             trtable[NEWLINE_CHAR] = dest_states_nl[j];
3505             if (need_word_trtable)
3506               trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3507             /* There must be only one destination which accepts
3508                newline.  See group_nodes_into_DFAstates.  */
3509             break;
3510           }
3511     }
3512
3513   if (dest_states_malloced)
3514     free (dest_states);
3515
3516   re_node_set_free (&follows);
3517   for (i = 0; i < ndests; ++i)
3518     re_node_set_free (dests_node + i);
3519
3520   if (dests_node_malloced)
3521     free (dests_alloc);
3522
3523   return true;
3524 }
3525
3526 /* Group all nodes belonging to STATE into several destinations.
3527    Then for all destinations, set the nodes belonging to the destination
3528    to DESTS_NODE[i] and set the characters accepted by the destination
3529    to DEST_CH[i].  This function return the number of destinations.  */
3530
3531 static Idx
3532 internal_function
3533 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3534                             re_node_set *dests_node, bitset *dests_ch)
3535 {
3536   reg_errcode_t err;
3537   bool ok;
3538   Idx i, j, k;
3539   Idx ndests; /* Number of the destinations from `state'.  */
3540   bitset accepts; /* Characters a node can accept.  */
3541   const re_node_set *cur_nodes = &state->nodes;
3542   bitset_empty (accepts);
3543   ndests = 0;
3544
3545   /* For all the nodes belonging to `state',  */
3546   for (i = 0; i < cur_nodes->nelem; ++i)
3547     {
3548       re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3549       re_token_type_t type = node->type;
3550       unsigned int constraint = node->constraint;
3551
3552       /* Enumerate all single byte character this node can accept.  */
3553       if (type == CHARACTER)
3554         bitset_set (accepts, node->opr.c);
3555       else if (type == SIMPLE_BRACKET)
3556         {
3557           bitset_merge (accepts, node->opr.sbcset);
3558         }
3559       else if (type == OP_PERIOD)
3560         {
3561 #ifdef RE_ENABLE_I18N
3562           if (dfa->mb_cur_max > 1)
3563             bitset_merge (accepts, dfa->sb_char);
3564           else
3565 #endif
3566             bitset_set_all (accepts);
3567           if (!(dfa->syntax & REG_DOT_NEWLINE))
3568             bitset_clear (accepts, '\n');
3569           if (dfa->syntax & REG_DOT_NOT_NULL)
3570             bitset_clear (accepts, '\0');
3571         }
3572 #ifdef RE_ENABLE_I18N
3573       else if (type == OP_UTF8_PERIOD)
3574         {
3575           if (SBC_MAX / 2 % BITSET_WORD_BITS == 0)
3576             memset (accepts, -1, sizeof accepts / 2);
3577           else
3578             bitset_merge (accepts, utf8_sb_map);
3579           if (!(dfa->syntax & REG_DOT_NEWLINE))
3580             bitset_clear (accepts, '\n');
3581           if (dfa->syntax & REG_DOT_NOT_NULL)
3582             bitset_clear (accepts, '\0');
3583         }
3584 #endif
3585       else
3586         continue;
3587
3588       /* Check the `accepts' and sift the characters which are not
3589          match it the context.  */
3590       if (constraint)
3591         {
3592           if (constraint & NEXT_NEWLINE_CONSTRAINT)
3593             {
3594               bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3595               bitset_empty (accepts);
3596               if (accepts_newline)
3597                 bitset_set (accepts, NEWLINE_CHAR);
3598               else
3599                 continue;
3600             }
3601           if (constraint & NEXT_ENDBUF_CONSTRAINT)
3602             {
3603               bitset_empty (accepts);
3604               continue;
3605             }
3606
3607           if (constraint & NEXT_WORD_CONSTRAINT)
3608             {
3609               bitset_word any_set = 0;
3610               if (type == CHARACTER && !node->word_char)
3611                 {
3612                   bitset_empty (accepts);
3613                   continue;
3614                 }
3615 #ifdef RE_ENABLE_I18N
3616               if (dfa->mb_cur_max > 1)
3617                 for (j = 0; j < BITSET_WORDS; ++j)
3618                   any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3619               else
3620 #endif
3621                 for (j = 0; j < BITSET_WORDS; ++j)
3622                   any_set |= (accepts[j] &= dfa->word_char[j]);
3623               if (!any_set)
3624                 continue;
3625             }
3626           if (constraint & NEXT_NOTWORD_CONSTRAINT)
3627             {
3628               bitset_word any_set = 0;
3629               if (type == CHARACTER && node->word_char)
3630                 {
3631                   bitset_empty (accepts);
3632                   continue;
3633                 }
3634 #ifdef RE_ENABLE_I18N
3635               if (dfa->mb_cur_max > 1)
3636                 for (j = 0; j < BITSET_WORDS; ++j)
3637                   any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3638               else
3639 #endif
3640                 for (j = 0; j < BITSET_WORDS; ++j)
3641                   any_set |= (accepts[j] &= ~dfa->word_char[j]);
3642               if (!any_set)
3643                 continue;
3644             }
3645         }
3646
3647       /* Then divide `accepts' into DFA states, or create a new
3648          state.  Above, we make sure that accepts is not empty.  */
3649       for (j = 0; j < ndests; ++j)
3650         {
3651           bitset intersec; /* Intersection sets, see below.  */
3652           bitset remains;
3653           /* Flags, see below.  */
3654           bitset_word has_intersec, not_subset, not_consumed;
3655
3656           /* Optimization, skip if this state doesn't accept the character.  */
3657           if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3658             continue;
3659
3660           /* Enumerate the intersection set of this state and `accepts'.  */
3661           has_intersec = 0;
3662           for (k = 0; k < BITSET_WORDS; ++k)
3663             has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3664           /* And skip if the intersection set is empty.  */
3665           if (!has_intersec)
3666             continue;
3667
3668           /* Then check if this state is a subset of `accepts'.  */
3669           not_subset = not_consumed = 0;
3670           for (k = 0; k < BITSET_WORDS; ++k)
3671             {
3672               not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3673               not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3674             }
3675
3676           /* If this state isn't a subset of `accepts', create a
3677              new group state, which has the `remains'. */
3678           if (not_subset)
3679             {
3680               bitset_copy (dests_ch[ndests], remains);
3681               bitset_copy (dests_ch[j], intersec);
3682               err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3683               if (BE (err != REG_NOERROR, 0))
3684                 goto error_return;
3685               ++ndests;
3686             }
3687
3688           /* Put the position in the current group. */
3689           ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3690           if (BE (! ok, 0))
3691             goto error_return;
3692
3693           /* If all characters are consumed, go to next node. */
3694           if (!not_consumed)
3695             break;
3696         }
3697       /* Some characters remain, create a new group. */
3698       if (j == ndests)
3699         {
3700           bitset_copy (dests_ch[ndests], accepts);
3701           err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3702           if (BE (err != REG_NOERROR, 0))
3703             goto error_return;
3704           ++ndests;
3705           bitset_empty (accepts);
3706         }
3707     }
3708   return ndests;
3709  error_return:
3710   for (j = 0; j < ndests; ++j)
3711     re_node_set_free (dests_node + j);
3712   return REG_MISSING;
3713 }
3714
3715 #ifdef RE_ENABLE_I18N
3716 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3717    Return the number of the bytes the node accepts.
3718    STR_IDX is the current index of the input string.
3719
3720    This function handles the nodes which can accept one character, or
3721    one collating element like '.', '[a-z]', opposite to the other nodes
3722    can only accept one byte.  */
3723
3724 static int
3725 internal_function
3726 check_node_accept_bytes (re_dfa_t *dfa, Idx node_idx,
3727                          const re_string_t *input, Idx str_idx)
3728 {
3729   const re_token_t *node = dfa->nodes + node_idx;
3730   int char_len, elem_len;
3731   Idx i;
3732
3733   if (BE (node->type == OP_UTF8_PERIOD, 0))
3734     {
3735       unsigned char c = re_string_byte_at (input, str_idx), d;
3736       if (BE (c < 0xc2, 1))
3737         return 0;
3738
3739       if (str_idx + 2 > input->len)
3740         return 0;
3741
3742       d = re_string_byte_at (input, str_idx + 1);
3743       if (c < 0xe0)
3744         return (d < 0x80 || d > 0xbf) ? 0 : 2;
3745       else if (c < 0xf0)
3746         {
3747           char_len = 3;
3748           if (c == 0xe0 && d < 0xa0)
3749             return 0;
3750         }
3751       else if (c < 0xf8)
3752         {
3753           char_len = 4;
3754           if (c == 0xf0 && d < 0x90)
3755             return 0;
3756         }
3757       else if (c < 0xfc)
3758         {
3759           char_len = 5;
3760           if (c == 0xf8 && d < 0x88)
3761             return 0;
3762         }
3763       else if (c < 0xfe)
3764         {
3765           char_len = 6;
3766           if (c == 0xfc && d < 0x84)
3767             return 0;
3768         }
3769       else
3770         return 0;
3771
3772       if (str_idx + char_len > input->len)
3773         return 0;
3774
3775       for (i = 1; i < char_len; ++i)
3776         {
3777           d = re_string_byte_at (input, str_idx + i);
3778           if (d < 0x80 || d > 0xbf)
3779             return 0;
3780         }
3781       return char_len;
3782     }
3783
3784   char_len = re_string_char_size_at (input, str_idx);
3785   if (node->type == OP_PERIOD)
3786     {
3787       if (char_len <= 1)
3788         return 0;
3789       /* FIXME: I don't think this if is needed, as both '\n'
3790          and '\0' are char_len == 1.  */
3791       /* '.' accepts any one character except the following two cases.  */
3792       if ((!(dfa->syntax & REG_DOT_NEWLINE) &&
3793            re_string_byte_at (input, str_idx) == '\n') ||
3794           ((dfa->syntax & REG_DOT_NOT_NULL) &&
3795            re_string_byte_at (input, str_idx) == '\0'))
3796         return 0;
3797       return char_len;
3798     }
3799
3800   elem_len = re_string_elem_size_at (input, str_idx);
3801   if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3802     return 0;
3803
3804   if (node->type == COMPLEX_BRACKET)
3805     {
3806       const re_charset_t *cset = node->opr.mbcset;
3807 # ifdef _LIBC
3808       const unsigned char *pin
3809         = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3810       Idx j;
3811       uint32_t nrules;
3812 # endif /* _LIBC */
3813       int match_len = 0;
3814       wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3815                     ? re_string_wchar_at (input, str_idx) : 0);
3816
3817       /* match with multibyte character?  */
3818       for (i = 0; i < cset->nmbchars; ++i)
3819         if (wc == cset->mbchars[i])
3820           {
3821             match_len = char_len;
3822             goto check_node_accept_bytes_match;
3823           }
3824       /* match with character_class?  */
3825       for (i = 0; i < cset->nchar_classes; ++i)
3826         {
3827           wctype_t wt = cset->char_classes[i];
3828           if (__iswctype (wc, wt))
3829             {
3830               match_len = char_len;
3831               goto check_node_accept_bytes_match;
3832             }
3833         }
3834
3835 # ifdef _LIBC
3836       nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3837       if (nrules != 0)
3838         {
3839           unsigned int in_collseq = 0;
3840           const int32_t *table, *indirect;
3841           const unsigned char *weights, *extra;
3842           const char *collseqwc;
3843           int32_t idx;
3844           /* This #include defines a local function!  */
3845 #  include <locale/weight.h>
3846
3847           /* match with collating_symbol?  */
3848           if (cset->ncoll_syms)
3849             extra = (const unsigned char *)
3850               _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3851           for (i = 0; i < cset->ncoll_syms; ++i)
3852             {
3853               const unsigned char *coll_sym = extra + cset->coll_syms[i];
3854               /* Compare the length of input collating element and
3855                  the length of current collating element.  */
3856               if (*coll_sym != elem_len)
3857                 continue;
3858               /* Compare each bytes.  */
3859               for (j = 0; j < *coll_sym; j++)
3860                 if (pin[j] != coll_sym[1 + j])
3861                   break;
3862               if (j == *coll_sym)
3863                 {
3864                   /* Match if every bytes is equal.  */
3865                   match_len = j;
3866                   goto check_node_accept_bytes_match;
3867                 }
3868             }
3869
3870           if (cset->nranges)
3871             {
3872               if (elem_len <= char_len)
3873                 {
3874                   collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3875                   in_collseq = __collseq_table_lookup (collseqwc, wc);
3876                 }
3877               else
3878                 in_collseq = find_collation_sequence_value (pin, elem_len);
3879             }
3880           /* match with range expression?  */
3881           for (i = 0; i < cset->nranges; ++i)
3882             if (cset->range_starts[i] <= in_collseq
3883                 && in_collseq <= cset->range_ends[i])
3884               {
3885                 match_len = elem_len;
3886                 goto check_node_accept_bytes_match;
3887               }
3888
3889           /* match with equivalence_class?  */
3890           if (cset->nequiv_classes)
3891             {
3892               const unsigned char *cp = pin;
3893               table = (const int32_t *)
3894                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3895               weights = (const unsigned char *)
3896                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3897               extra = (const unsigned char *)
3898                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3899               indirect = (const int32_t *)
3900                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3901               idx = findidx (&cp);
3902               if (idx > 0)
3903                 for (i = 0; i < cset->nequiv_classes; ++i)
3904                   {
3905                     int32_t equiv_class_idx = cset->equiv_classes[i];
3906                     size_t weight_len = weights[idx];
3907                     if (weight_len == weights[equiv_class_idx])
3908                       {
3909                         Idx cnt = 0;
3910                         while (cnt <= weight_len
3911                                && (weights[equiv_class_idx + 1 + cnt]
3912                                    == weights[idx + 1 + cnt]))
3913                           ++cnt;
3914                         if (cnt > weight_len)
3915                           {
3916                             match_len = elem_len;
3917                             goto check_node_accept_bytes_match;
3918                           }
3919                       }
3920                   }
3921             }
3922         }
3923       else
3924 # endif /* _LIBC */
3925         {
3926           /* match with range expression?  */
3927 #if __GNUC__ >= 2
3928           wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3929 #else
3930           wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3931           cmp_buf[2] = wc;
3932 #endif
3933           for (i = 0; i < cset->nranges; ++i)
3934             {
3935               cmp_buf[0] = cset->range_starts[i];
3936               cmp_buf[4] = cset->range_ends[i];
3937               if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3938                   && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3939                 {
3940                   match_len = char_len;
3941                   goto check_node_accept_bytes_match;
3942                 }
3943             }
3944         }
3945     check_node_accept_bytes_match:
3946       if (!cset->non_match)
3947         return match_len;
3948       else
3949         {
3950           if (match_len > 0)
3951             return 0;
3952           else
3953             return (elem_len > char_len) ? elem_len : char_len;
3954         }
3955     }
3956   return 0;
3957 }
3958
3959 # ifdef _LIBC
3960 static unsigned int
3961 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
3962 {
3963   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3964   if (nrules == 0)
3965     {
3966       if (mbs_len == 1)
3967         {
3968           /* No valid character.  Match it as a single byte character.  */
3969           const unsigned char *collseq = (const unsigned char *)
3970             _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3971           return collseq[mbs[0]];
3972         }
3973       return UINT_MAX;
3974     }
3975   else
3976     {
3977       int32_t idx;
3978       const unsigned char *extra = (const unsigned char *)
3979         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3980       int32_t extrasize = (const unsigned char *)
3981         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
3982
3983       for (idx = 0; idx < extrasize;)
3984         {
3985           int mbs_cnt;
3986           bool found = false;
3987           int32_t elem_mbs_len;
3988           /* Skip the name of collating element name.  */
3989           idx = idx + extra[idx] + 1;
3990           elem_mbs_len = extra[idx++];
3991           if (mbs_len == elem_mbs_len)
3992             {
3993               for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
3994                 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
3995                   break;
3996               if (mbs_cnt == elem_mbs_len)
3997                 /* Found the entry.  */
3998                 found = true;
3999             }
4000           /* Skip the byte sequence of the collating element.  */
4001           idx += elem_mbs_len;
4002           /* Adjust for the alignment.  */
4003           idx = (idx + 3) & ~3;
4004           /* Skip the collation sequence value.  */
4005           idx += sizeof (uint32_t);
4006           /* Skip the wide char sequence of the collating element.  */
4007           idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4008           /* If we found the entry, return the sequence value.  */
4009           if (found)
4010             return *(uint32_t *) (extra + idx);
4011           /* Skip the collation sequence value.  */
4012           idx += sizeof (uint32_t);
4013         }
4014       return UINT_MAX;
4015     }
4016 }
4017 # endif /* _LIBC */
4018 #endif /* RE_ENABLE_I18N */
4019
4020 /* Check whether the node accepts the byte which is IDX-th
4021    byte of the INPUT.  */
4022
4023 static bool
4024 internal_function
4025 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4026                    Idx idx)
4027 {
4028   unsigned char ch;
4029   ch = re_string_byte_at (&mctx->input, idx);
4030   switch (node->type)
4031     {
4032     case CHARACTER:
4033       if (node->opr.c != ch)
4034         return false;
4035       break;
4036
4037     case SIMPLE_BRACKET:
4038       if (!bitset_contain (node->opr.sbcset, ch))
4039         return false;
4040       break;
4041
4042 #ifdef RE_ENABLE_I18N
4043     case OP_UTF8_PERIOD:
4044       if (ch >= 0x80)
4045         return false;
4046       /* FALLTHROUGH */
4047 #endif
4048     case OP_PERIOD:
4049       if ((ch == '\n' && !(mctx->dfa->syntax & REG_DOT_NEWLINE))
4050           || (ch == '\0' && (mctx->dfa->syntax & REG_DOT_NOT_NULL)))
4051         return false;
4052       break;
4053
4054     default:
4055       return false;
4056     }
4057
4058   if (node->constraint)
4059     {
4060       /* The node has constraints.  Check whether the current context
4061          satisfies the constraints.  */
4062       unsigned int context = re_string_context_at (&mctx->input, idx,
4063                                                    mctx->eflags);
4064       if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4065         return false;
4066     }
4067
4068   return true;
4069 }
4070
4071 /* Extend the buffers, if the buffers have run out.  */
4072
4073 static reg_errcode_t
4074 internal_function
4075 extend_buffers (re_match_context_t *mctx)
4076 {
4077   reg_errcode_t ret;
4078   re_string_t *pstr = &mctx->input;
4079
4080   /* Double the lengthes of the buffers.  */
4081   ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4082   if (BE (ret != REG_NOERROR, 0))
4083     return ret;
4084
4085   if (mctx->state_log != NULL)
4086     {
4087       /* And double the length of state_log.  */
4088       /* XXX We have no indication of the size of this buffer.  If this
4089          allocation fail we have no indication that the state_log array
4090          does not have the right size.  */
4091       re_dfastate_t **new_array = re_xrealloc (mctx->state_log, re_dfastate_t *,
4092                                                pstr->bufs_len + 1);
4093       if (BE (new_array == NULL, 0))
4094         return REG_ESPACE;
4095       mctx->state_log = new_array;
4096     }
4097
4098   /* Then reconstruct the buffers.  */
4099   if (pstr->icase)
4100     {
4101 #ifdef RE_ENABLE_I18N
4102       if (pstr->mb_cur_max > 1)
4103         {
4104           ret = build_wcs_upper_buffer (pstr);
4105           if (BE (ret != REG_NOERROR, 0))
4106             return ret;
4107         }
4108       else
4109 #endif /* RE_ENABLE_I18N  */
4110         build_upper_buffer (pstr);
4111     }
4112   else
4113     {
4114 #ifdef RE_ENABLE_I18N
4115       if (pstr->mb_cur_max > 1)
4116         build_wcs_buffer (pstr);
4117       else
4118 #endif /* RE_ENABLE_I18N  */
4119         {
4120           if (pstr->trans != NULL)
4121             re_string_translate_buffer (pstr);
4122         }
4123     }
4124   return REG_NOERROR;
4125 }
4126
4127 \f
4128 /* Functions for matching context.  */
4129
4130 /* Initialize MCTX.  */
4131
4132 static reg_errcode_t
4133 internal_function
4134 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4135 {
4136   mctx->eflags = eflags;
4137   mctx->match_last = REG_MISSING;
4138   if (n > 0)
4139     {
4140       mctx->bkref_ents = re_xmalloc (struct re_backref_cache_entry, n);
4141       mctx->sub_tops = re_xmalloc (re_sub_match_top_t *, n);
4142       if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4143         return REG_ESPACE;
4144     }
4145   /* Already zero-ed by the caller.
4146      else
4147        mctx->bkref_ents = NULL;
4148      mctx->nbkref_ents = 0;
4149      mctx->nsub_tops = 0;  */
4150   mctx->abkref_ents = n;
4151   mctx->max_mb_elem_len = 1;
4152   mctx->asub_tops = n;
4153   return REG_NOERROR;
4154 }
4155
4156 /* Clean the entries which depend on the current input in MCTX.
4157    This function must be invoked when the matcher changes the start index
4158    of the input, or changes the input string.  */
4159
4160 static void
4161 internal_function
4162 match_ctx_clean (re_match_context_t *mctx)
4163 {
4164   Idx st_idx;
4165   for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4166     {
4167       Idx sl_idx;
4168       re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4169       for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4170         {
4171           re_sub_match_last_t *last = top->lasts[sl_idx];
4172           re_free (last->path.array);
4173           re_free (last);
4174         }
4175       re_free (top->lasts);
4176       if (top->path)
4177         {
4178           re_free (top->path->array);
4179           re_free (top->path);
4180         }
4181       free (top);
4182     }
4183
4184   mctx->nsub_tops = 0;
4185   mctx->nbkref_ents = 0;
4186 }
4187
4188 /* Free all the memory associated with MCTX.  */
4189
4190 static void
4191 internal_function
4192 match_ctx_free (re_match_context_t *mctx)
4193 {
4194   /* First, free all the memory associated with MCTX->SUB_TOPS.  */
4195   match_ctx_clean (mctx);
4196   re_free (mctx->sub_tops);
4197   re_free (mctx->bkref_ents);
4198 }
4199
4200 /* Add a new backreference entry to MCTX.
4201    Note that we assume that caller never call this function with duplicate
4202    entry, and call with STR_IDX which isn't smaller than any existing entry.
4203 */
4204
4205 static reg_errcode_t
4206 internal_function
4207 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx,
4208                      Idx from, Idx to)
4209 {
4210   if (mctx->nbkref_ents >= mctx->abkref_ents)
4211     {
4212       struct re_backref_cache_entry* new_entry;
4213       new_entry = re_x2realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4214                                 &mctx->abkref_ents);
4215       if (BE (new_entry == NULL, 0))
4216         {
4217           re_free (mctx->bkref_ents);
4218           return REG_ESPACE;
4219         }
4220       mctx->bkref_ents = new_entry;
4221       memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4222               (sizeof (struct re_backref_cache_entry)
4223                * (mctx->abkref_ents - mctx->nbkref_ents)));
4224     }
4225   if (mctx->nbkref_ents > 0
4226       && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4227     mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4228
4229   mctx->bkref_ents[mctx->nbkref_ents].node = node;
4230   mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4231   mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4232   mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4233
4234   /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4235      If bit N is clear, means that this entry won't epsilon-transition to
4236      an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression.  If
4237      it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4238      such node.
4239
4240      A backreference does not epsilon-transition unless it is empty, so set
4241      to all zeros if FROM != TO.  */
4242   mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4243     = (from == to ? -1 : 0);
4244
4245   mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4246   if (mctx->max_mb_elem_len < to - from)
4247     mctx->max_mb_elem_len = to - from;
4248   return REG_NOERROR;
4249 }
4250
4251 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4252    found.  Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX.  */
4253
4254 static Idx
4255 internal_function
4256 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4257 {
4258   Idx left, right, mid, last;
4259   last = right = mctx->nbkref_ents;
4260   for (left = 0; left < right;)
4261     {
4262       mid = (left + right) / 2;
4263       if (mctx->bkref_ents[mid].str_idx < str_idx)
4264         left = mid + 1;
4265       else
4266         right = mid;
4267     }
4268   if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4269     return left;
4270   else
4271     return REG_MISSING;
4272 }
4273
4274 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4275    at STR_IDX.  */
4276
4277 static reg_errcode_t
4278 internal_function
4279 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4280 {
4281 #ifdef DEBUG
4282   assert (mctx->sub_tops != NULL);
4283   assert (mctx->asub_tops > 0);
4284 #endif
4285   if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4286     {
4287       Idx new_asub_tops = mctx->asub_tops;
4288       re_sub_match_top_t **new_array = re_x2realloc (mctx->sub_tops,
4289                                                      re_sub_match_top_t *,
4290                                                      &new_asub_tops);
4291       if (BE (new_array == NULL, 0))
4292         return REG_ESPACE;
4293       mctx->sub_tops = new_array;
4294       mctx->asub_tops = new_asub_tops;
4295     }
4296   mctx->sub_tops[mctx->nsub_tops] = re_calloc (re_sub_match_top_t, 1);
4297   if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4298     return REG_ESPACE;
4299   mctx->sub_tops[mctx->nsub_tops]->node = node;
4300   mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4301   return REG_NOERROR;
4302 }
4303
4304 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4305    at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP.  */
4306
4307 static re_sub_match_last_t *
4308 internal_function
4309 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4310 {
4311   re_sub_match_last_t *new_entry;
4312   if (BE (subtop->nlasts == subtop->alasts, 0))
4313     {
4314       Idx new_alasts = subtop->alasts;
4315       re_sub_match_last_t **new_array = re_x2realloc (subtop->lasts,
4316                                                       re_sub_match_last_t *,
4317                                                       &new_alasts);
4318       if (BE (new_array == NULL, 0))
4319         return NULL;
4320       subtop->lasts = new_array;
4321       subtop->alasts = new_alasts;
4322     }
4323   new_entry = re_calloc (re_sub_match_last_t, 1);
4324   if (BE (new_entry != NULL, 1))
4325     {
4326       subtop->lasts[subtop->nlasts] = new_entry;
4327       new_entry->node = node;
4328       new_entry->str_idx = str_idx;
4329       ++subtop->nlasts;
4330     }
4331   return new_entry;
4332 }
4333
4334 static void
4335 internal_function
4336 sift_ctx_init (re_sift_context_t *sctx,
4337                re_dfastate_t **sifted_sts,
4338                re_dfastate_t **limited_sts,
4339                Idx last_node, Idx last_str_idx)
4340 {
4341   sctx->sifted_states = sifted_sts;
4342   sctx->limited_states = limited_sts;
4343   sctx->last_node = last_node;
4344   sctx->last_str_idx = last_str_idx;
4345   re_node_set_init_empty (&sctx->limits);
4346 }