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