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, 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_xmalloc (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_xmalloc (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_xrealloc (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_xmalloc (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_xmalloc (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_xmalloc (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_x2realloc (fs->stack, struct re_fail_stack_ent_t, &fs->alloc);
1347       if (new_array == NULL)
1348         return REG_ESPACE;
1349       fs->stack = new_array;
1350     }
1351   fs->stack[num].idx = str_idx;
1352   fs->stack[num].node = dest_node;
1353   fs->stack[num].regs = re_xmalloc (regmatch_t, nregs);
1354   if (fs->stack[num].regs == NULL)
1355     return REG_ESPACE;
1356   memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1357   err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1358   return err;
1359 }
1360
1361 static Idx
1362 internal_function
1363 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx,
1364                 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1365 {
1366   Idx num = --fs->num;
1367   assert (REG_VALID_INDEX (num));
1368   *pidx = fs->stack[num].idx;
1369   memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1370   re_node_set_free (eps_via_nodes);
1371   re_free (fs->stack[num].regs);
1372   *eps_via_nodes = fs->stack[num].eps_via_nodes;
1373   return fs->stack[num].node;
1374 }
1375
1376 /* Set the positions where the subexpressions are starts/ends to registers
1377    PMATCH.
1378    Note: We assume that pmatch[0] is already set, and
1379    pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch.  */
1380
1381 static reg_errcode_t
1382 internal_function
1383 set_regs (const regex_t *preg, const re_match_context_t *mctx,
1384           size_t nmatch, regmatch_t *pmatch, bool fl_backtrack)
1385 {
1386   re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
1387   Idx idx, cur_node;
1388   re_node_set eps_via_nodes;
1389   struct re_fail_stack_t *fs;
1390   struct re_fail_stack_t fs_body = { 0, 2, NULL };
1391   regmatch_t *prev_idx_match;
1392   bool prev_idx_match_malloced = false;
1393
1394 #ifdef DEBUG
1395   assert (nmatch > 1);
1396   assert (mctx->state_log != NULL);
1397 #endif
1398   if (fl_backtrack)
1399     {
1400       fs = &fs_body;
1401       fs->stack = re_xmalloc (struct re_fail_stack_ent_t, fs->alloc);
1402       if (fs->stack == NULL)
1403         return REG_ESPACE;
1404     }
1405   else
1406     fs = NULL;
1407
1408   cur_node = dfa->init_node;
1409   re_node_set_init_empty (&eps_via_nodes);
1410
1411   if (re_alloc_oversized (nmatch, sizeof (regmatch_t)))
1412     {
1413       free_fail_stack_return (fs);
1414       return REG_ESPACE;
1415     }
1416   if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1417     prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1418   else
1419     {
1420       prev_idx_match = re_malloc (regmatch_t, nmatch);
1421       if (prev_idx_match == NULL)
1422         {
1423           free_fail_stack_return (fs);
1424           return REG_ESPACE;
1425         }
1426       prev_idx_match_malloced = true;
1427     }
1428   memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1429
1430   for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1431     {
1432       update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1433
1434       if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1435         {
1436           Idx reg_idx;
1437           if (fs)
1438             {
1439               for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1440                 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1441                   break;
1442               if (reg_idx == nmatch)
1443                 {
1444                   re_node_set_free (&eps_via_nodes);
1445                   if (prev_idx_match_malloced)
1446                     re_free (prev_idx_match);
1447                   return free_fail_stack_return (fs);
1448                 }
1449               cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1450                                          &eps_via_nodes);
1451             }
1452           else
1453             {
1454               re_node_set_free (&eps_via_nodes);
1455               if (prev_idx_match_malloced)
1456                 re_free (prev_idx_match);
1457               return REG_NOERROR;
1458             }
1459         }
1460
1461       /* Proceed to next node.  */
1462       cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1463                                     &eps_via_nodes, fs);
1464
1465       if (BE (! REG_VALID_INDEX (cur_node), 0))
1466         {
1467           if (BE (cur_node == REG_ERROR, 0))
1468             {
1469               re_node_set_free (&eps_via_nodes);
1470               if (prev_idx_match_malloced)
1471                 re_free (prev_idx_match);
1472               free_fail_stack_return (fs);
1473               return REG_ESPACE;
1474             }
1475           if (fs)
1476             cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1477                                        &eps_via_nodes);
1478           else
1479             {
1480               re_node_set_free (&eps_via_nodes);
1481               if (prev_idx_match_malloced)
1482                 re_free (prev_idx_match);
1483               return REG_NOMATCH;
1484             }
1485         }
1486     }
1487   re_node_set_free (&eps_via_nodes);
1488   if (prev_idx_match_malloced)
1489     re_free (prev_idx_match);
1490   return free_fail_stack_return (fs);
1491 }
1492
1493 static reg_errcode_t
1494 internal_function
1495 free_fail_stack_return (struct re_fail_stack_t *fs)
1496 {
1497   if (fs)
1498     {
1499       Idx fs_idx;
1500       for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1501         {
1502           re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1503           re_free (fs->stack[fs_idx].regs);
1504         }
1505       re_free (fs->stack);
1506     }
1507   return REG_NOERROR;
1508 }
1509
1510 static void
1511 internal_function
1512 update_regs (re_dfa_t *dfa, regmatch_t *pmatch, regmatch_t *prev_idx_match,
1513              Idx cur_node, Idx cur_idx, Idx nmatch)
1514 {
1515   int type = dfa->nodes[cur_node].type;
1516   if (type == OP_OPEN_SUBEXP)
1517     {
1518       Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1519
1520       /* We are at the first node of this sub expression.  */
1521       if (reg_num < nmatch)
1522         {
1523           pmatch[reg_num].rm_so = cur_idx;
1524           pmatch[reg_num].rm_eo = -1;
1525         }
1526     }
1527   else if (type == OP_CLOSE_SUBEXP)
1528     {
1529       Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1530       if (reg_num < nmatch)
1531         {
1532           /* We are at the last node of this sub expression.  */
1533           if (pmatch[reg_num].rm_so < cur_idx)
1534             {
1535               pmatch[reg_num].rm_eo = cur_idx;
1536               /* This is a non-empty match or we are not inside an optional
1537                  subexpression.  Accept this right away.  */
1538               memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1539             }
1540           else
1541             {
1542               if (dfa->nodes[cur_node].opt_subexp
1543                   && prev_idx_match[reg_num].rm_so != -1)
1544                 /* We transited through an empty match for an optional
1545                    subexpression, like (a?)*, and this is not the subexp's
1546                    first match.  Copy back the old content of the registers
1547                    so that matches of an inner subexpression are undone as
1548                    well, like in ((a?))*.  */
1549                 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1550               else
1551                 /* We completed a subexpression, but it may be part of
1552                    an optional one, so do not update PREV_IDX_MATCH.  */
1553                 pmatch[reg_num].rm_eo = cur_idx;
1554             }
1555         }
1556     }
1557 }
1558
1559 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1560    and sift the nodes in each states according to the following rules.
1561    Updated state_log will be wrote to STATE_LOG.
1562
1563    Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1564      1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1565         If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1566         the LAST_NODE, we throw away the node `a'.
1567      2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1568         string `s' and transit to `b':
1569         i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1570            away the node `a'.
1571         ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1572             thrown away, we throw away the node `a'.
1573      3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1574         i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1575            node `a'.
1576         ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1577             we throw away the node `a'.  */
1578
1579 #define STATE_NODE_CONTAINS(state,node) \
1580   ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1581
1582 static reg_errcode_t
1583 internal_function
1584 sift_states_backward (re_match_context_t *mctx, re_sift_context_t *sctx)
1585 {
1586   reg_errcode_t err;
1587   int null_cnt = 0;
1588   Idx str_idx = sctx->last_str_idx;
1589   re_node_set cur_dest;
1590
1591 #ifdef DEBUG
1592   assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1593 #endif
1594
1595   /* Build sifted state_log[str_idx].  It has the nodes which can epsilon
1596      transit to the last_node and the last_node itself.  */
1597   err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1598   if (BE (err != REG_NOERROR, 0))
1599     return err;
1600   err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1601   if (BE (err != REG_NOERROR, 0))
1602     goto free_return;
1603
1604   /* Then check each states in the state_log.  */
1605   while (str_idx > 0)
1606     {
1607       /* Update counters.  */
1608       null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1609       if (null_cnt > mctx->max_mb_elem_len)
1610         {
1611           memset (sctx->sifted_states, '\0',
1612                   sizeof (re_dfastate_t *) * str_idx);
1613           re_node_set_free (&cur_dest);
1614           return REG_NOERROR;
1615         }
1616       re_node_set_empty (&cur_dest);
1617       --str_idx;
1618
1619       if (mctx->state_log[str_idx])
1620         {
1621           err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1622           if (BE (err != REG_NOERROR, 0))
1623             goto free_return;
1624         }
1625
1626       /* Add all the nodes which satisfy the following conditions:
1627          - It can epsilon transit to a node in CUR_DEST.
1628          - It is in CUR_SRC.
1629          And update state_log.  */
1630       err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1631       if (BE (err != REG_NOERROR, 0))
1632         goto free_return;
1633     }
1634   err = REG_NOERROR;
1635  free_return:
1636   re_node_set_free (&cur_dest);
1637   return err;
1638 }
1639
1640 static reg_errcode_t
1641 internal_function
1642 build_sifted_states (re_match_context_t *mctx, re_sift_context_t *sctx,
1643                      Idx str_idx, re_node_set *cur_dest)
1644 {
1645   re_dfa_t *const dfa = mctx->dfa;
1646   re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1647   Idx i;
1648
1649   /* Then build the next sifted state.
1650      We build the next sifted state on `cur_dest', and update
1651      `sifted_states[str_idx]' with `cur_dest'.
1652      Note:
1653      `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1654      `cur_src' points the node_set of the old `state_log[str_idx]'
1655      (with the epsilon nodes pre-filtered out).  */
1656   for (i = 0; i < cur_src->nelem; i++)
1657     {
1658       Idx prev_node = cur_src->elems[i];
1659       int naccepted = 0;
1660       bool ok;
1661
1662 #ifdef DEBUG
1663       re_token_type_t type = dfa->nodes[prev_node].type;
1664       assert (!IS_EPSILON_NODE (type));
1665 #endif
1666 #ifdef RE_ENABLE_I18N
1667       /* If the node may accept `multi byte'.  */
1668       if (dfa->nodes[prev_node].accept_mb)
1669         naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1670                                          str_idx, sctx->last_str_idx);
1671 #endif /* RE_ENABLE_I18N */
1672
1673       /* We don't check backreferences here.
1674          See update_cur_sifted_state().  */
1675       if (!naccepted
1676           && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1677           && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1678                                   dfa->nexts[prev_node]))
1679         naccepted = 1;
1680
1681       if (naccepted == 0)
1682         continue;
1683
1684       if (sctx->limits.nelem)
1685         {
1686           Idx to_idx = str_idx + naccepted;
1687           if (check_dst_limits (mctx, &sctx->limits,
1688                                 dfa->nexts[prev_node], to_idx,
1689                                 prev_node, str_idx))
1690             continue;
1691         }
1692       ok = re_node_set_insert (cur_dest, prev_node);
1693       if (BE (! ok, 0))
1694         return REG_ESPACE;
1695     }
1696
1697   return REG_NOERROR;
1698 }
1699
1700 /* Helper functions.  */
1701
1702 static reg_errcode_t
1703 internal_function
1704 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1705 {
1706   Idx top = mctx->state_log_top;
1707
1708   if (next_state_log_idx >= mctx->input.bufs_len
1709       || (next_state_log_idx >= mctx->input.valid_len
1710           && mctx->input.valid_len < mctx->input.len))
1711     {
1712       reg_errcode_t err;
1713       err = extend_buffers (mctx);
1714       if (BE (err != REG_NOERROR, 0))
1715         return err;
1716     }
1717
1718   if (top < next_state_log_idx)
1719     {
1720       memset (mctx->state_log + top + 1, '\0',
1721               sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1722       mctx->state_log_top = next_state_log_idx;
1723     }
1724   return REG_NOERROR;
1725 }
1726
1727 static reg_errcode_t
1728 internal_function
1729 merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst, re_dfastate_t **src,
1730                    Idx num)
1731 {
1732   Idx st_idx;
1733   reg_errcode_t err;
1734   for (st_idx = 0; st_idx < num; ++st_idx)
1735     {
1736       if (dst[st_idx] == NULL)
1737         dst[st_idx] = src[st_idx];
1738       else if (src[st_idx] != NULL)
1739         {
1740           re_node_set merged_set;
1741           err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1742                                         &src[st_idx]->nodes);
1743           if (BE (err != REG_NOERROR, 0))
1744             return err;
1745           dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1746           re_node_set_free (&merged_set);
1747           if (BE (err != REG_NOERROR, 0))
1748             return err;
1749         }
1750     }
1751   return REG_NOERROR;
1752 }
1753
1754 static reg_errcode_t
1755 internal_function
1756 update_cur_sifted_state (re_match_context_t *mctx, re_sift_context_t *sctx,
1757                          Idx str_idx, re_node_set *dest_nodes)
1758 {
1759   re_dfa_t *const dfa = mctx->dfa;
1760   reg_errcode_t err;
1761   const re_node_set *candidates;
1762   candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1763                 : &mctx->state_log[str_idx]->nodes);
1764
1765   if (dest_nodes->nelem == 0)
1766     sctx->sifted_states[str_idx] = NULL;
1767   else
1768     {
1769       if (candidates)
1770         {
1771           /* At first, add the nodes which can epsilon transit to a node in
1772              DEST_NODE.  */
1773           err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1774           if (BE (err != REG_NOERROR, 0))
1775             return err;
1776
1777           /* Then, check the limitations in the current sift_context.  */
1778           if (sctx->limits.nelem)
1779             {
1780               err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1781                                          mctx->bkref_ents, str_idx);
1782               if (BE (err != REG_NOERROR, 0))
1783                 return err;
1784             }
1785         }
1786
1787       sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1788       if (BE (err != REG_NOERROR, 0))
1789         return err;
1790     }
1791
1792   if (candidates && mctx->state_log[str_idx]->has_backref)
1793     {
1794       err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1795       if (BE (err != REG_NOERROR, 0))
1796         return err;
1797     }
1798   return REG_NOERROR;
1799 }
1800
1801 static reg_errcode_t
1802 internal_function
1803 add_epsilon_src_nodes (re_dfa_t *dfa, re_node_set *dest_nodes,
1804                        const re_node_set *candidates)
1805 {
1806   reg_errcode_t err = REG_NOERROR;
1807   Idx i;
1808
1809   re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1810   if (BE (err != REG_NOERROR, 0))
1811     return err;
1812
1813   if (!state->inveclosure.alloc)
1814     {
1815       err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1816       if (BE (err != REG_NOERROR, 0))
1817         return REG_ESPACE;
1818       for (i = 0; i < dest_nodes->nelem; i++)
1819         re_node_set_merge (&state->inveclosure,
1820                            dfa->inveclosures + dest_nodes->elems[i]);
1821     }
1822   return re_node_set_add_intersect (dest_nodes, candidates,
1823                                     &state->inveclosure);
1824 }
1825
1826 static reg_errcode_t
1827 internal_function
1828 sub_epsilon_src_nodes (re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1829                        const re_node_set *candidates)
1830 {
1831     Idx ecl_idx;
1832     reg_errcode_t err;
1833     re_node_set *inv_eclosure = dfa->inveclosures + node;
1834     re_node_set except_nodes;
1835     re_node_set_init_empty (&except_nodes);
1836     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1837       {
1838         Idx cur_node = inv_eclosure->elems[ecl_idx];
1839         if (cur_node == node)
1840           continue;
1841         if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1842           {
1843             Idx edst1 = dfa->edests[cur_node].elems[0];
1844             Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1845                          ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1846             if ((!re_node_set_contains (inv_eclosure, edst1)
1847                  && re_node_set_contains (dest_nodes, edst1))
1848                 || (REG_VALID_NONZERO_INDEX (edst2)
1849                     && !re_node_set_contains (inv_eclosure, edst2)
1850                     && re_node_set_contains (dest_nodes, edst2)))
1851               {
1852                 err = re_node_set_add_intersect (&except_nodes, candidates,
1853                                                  dfa->inveclosures + cur_node);
1854                 if (BE (err != REG_NOERROR, 0))
1855                   {
1856                     re_node_set_free (&except_nodes);
1857                     return err;
1858                   }
1859               }
1860           }
1861       }
1862     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1863       {
1864         Idx cur_node = inv_eclosure->elems[ecl_idx];
1865         if (!re_node_set_contains (&except_nodes, cur_node))
1866           {
1867             Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1868             re_node_set_remove_at (dest_nodes, idx);
1869           }
1870       }
1871     re_node_set_free (&except_nodes);
1872     return REG_NOERROR;
1873 }
1874
1875 static bool
1876 internal_function
1877 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1878                   Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1879 {
1880   re_dfa_t *const dfa = mctx->dfa;
1881   Idx lim_idx, src_pos, dst_pos;
1882
1883   Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1884   Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1885   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1886     {
1887       Idx subexp_idx;
1888       struct re_backref_cache_entry *ent;
1889       ent = mctx->bkref_ents + limits->elems[lim_idx];
1890       subexp_idx = dfa->nodes[ent->node].opr.idx;
1891
1892       dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1893                                            subexp_idx, dst_node, dst_idx,
1894                                            dst_bkref_idx);
1895       src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1896                                            subexp_idx, src_node, src_idx,
1897                                            src_bkref_idx);
1898
1899       /* In case of:
1900          <src> <dst> ( <subexp> )
1901          ( <subexp> ) <src> <dst>
1902          ( <subexp1> <src> <subexp2> <dst> <subexp3> )  */
1903       if (src_pos == dst_pos)
1904         continue; /* This is unrelated limitation.  */
1905       else
1906         return true;
1907     }
1908   return false;
1909 }
1910
1911 static int
1912 internal_function
1913 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1914                              Idx subexp_idx, Idx from_node, Idx bkref_idx)
1915 {
1916   re_dfa_t *const dfa = mctx->dfa;
1917   re_node_set *eclosures = dfa->eclosures + from_node;
1918   Idx node_idx;
1919
1920   /* Else, we are on the boundary: examine the nodes on the epsilon
1921      closure.  */
1922   for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1923     {
1924       Idx node = eclosures->elems[node_idx];
1925       switch (dfa->nodes[node].type)
1926         {
1927         case OP_BACK_REF:
1928           if (bkref_idx != REG_MISSING)
1929             {
1930               struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1931               do
1932                 {
1933                   Idx dst;
1934                   int cpos;
1935
1936                   if (ent->node != node)
1937                     continue;
1938
1939                   if (subexp_idx
1940                       < CHAR_BIT * sizeof ent->eps_reachable_subexps_map
1941                       && !(ent->eps_reachable_subexps_map & (1u << subexp_idx)))
1942                     continue;
1943
1944                   /* Recurse trying to reach the OP_OPEN_SUBEXP and
1945                      OP_CLOSE_SUBEXP cases below.  But, if the
1946                      destination node is the same node as the source
1947                      node, don't recurse because it would cause an
1948                      infinite loop: a regex that exhibits this behavior
1949                      is ()\1*\1*  */
1950                   dst = dfa->edests[node].elems[0];
1951                   if (dst == from_node)
1952                     {
1953                       if (boundaries & 1)
1954                         return -1;
1955                       else /* if (boundaries & 2) */
1956                         return 0;
1957                     }
1958
1959                   cpos =
1960                     check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
1961                                                  dst, bkref_idx);
1962                   if (cpos == -1 /* && (boundaries & 1) */)
1963                     return -1;
1964                   if (cpos == 0 && (boundaries & 2))
1965                     return 0;
1966
1967                   if (subexp_idx
1968                       < CHAR_BIT * sizeof ent->eps_reachable_subexps_map)
1969                     ent->eps_reachable_subexps_map &= ~(1u << subexp_idx);
1970                 }
1971               while (ent++->more);
1972             }
1973           break;
1974
1975         case OP_OPEN_SUBEXP:
1976           if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
1977             return -1;
1978           break;
1979
1980         case OP_CLOSE_SUBEXP:
1981           if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
1982             return 0;
1983           break;
1984
1985         default:
1986             break;
1987         }
1988     }
1989
1990   return (boundaries & 2) ? 1 : 0;
1991 }
1992
1993 static int
1994 internal_function
1995 check_dst_limits_calc_pos (const re_match_context_t *mctx,
1996                            Idx limit, Idx subexp_idx,
1997                            Idx from_node, Idx str_idx, Idx bkref_idx)
1998 {
1999   struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2000   int boundaries;
2001
2002   /* If we are outside the range of the subexpression, return -1 or 1.  */
2003   if (str_idx < lim->subexp_from)
2004     return -1;
2005
2006   if (lim->subexp_to < str_idx)
2007     return 1;
2008
2009   /* If we are within the subexpression, return 0.  */
2010   boundaries = (str_idx == lim->subexp_from);
2011   boundaries |= (str_idx == lim->subexp_to) << 1;
2012   if (boundaries == 0)
2013     return 0;
2014
2015   /* Else, examine epsilon closure.  */
2016   return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2017                                       from_node, bkref_idx);
2018 }
2019
2020 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2021    which are against limitations from DEST_NODES. */
2022
2023 static reg_errcode_t
2024 internal_function
2025 check_subexp_limits (re_dfa_t *dfa, re_node_set *dest_nodes,
2026                      const re_node_set *candidates, re_node_set *limits,
2027                      struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2028 {
2029   reg_errcode_t err;
2030   Idx node_idx, lim_idx;
2031
2032   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2033     {
2034       Idx subexp_idx;
2035       struct re_backref_cache_entry *ent;
2036       ent = bkref_ents + limits->elems[lim_idx];
2037
2038       if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2039         continue; /* This is unrelated limitation.  */
2040
2041       subexp_idx = dfa->nodes[ent->node].opr.idx;
2042       if (ent->subexp_to == str_idx)
2043         {
2044           Idx ops_node = REG_MISSING;
2045           Idx cls_node = REG_MISSING;
2046           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2047             {
2048               Idx node = dest_nodes->elems[node_idx];
2049               re_token_type_t type = dfa->nodes[node].type;
2050               if (type == OP_OPEN_SUBEXP
2051                   && subexp_idx == dfa->nodes[node].opr.idx)
2052                 ops_node = node;
2053               else if (type == OP_CLOSE_SUBEXP
2054                        && subexp_idx == dfa->nodes[node].opr.idx)
2055                 cls_node = node;
2056             }
2057
2058           /* Check the limitation of the open subexpression.  */
2059           /* Note that (ent->subexp_to = str_idx != ent->subexp_from).  */
2060           if (REG_VALID_INDEX (ops_node))
2061             {
2062               err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2063                                            candidates);
2064               if (BE (err != REG_NOERROR, 0))
2065                 return err;
2066             }
2067
2068           /* Check the limitation of the close subexpression.  */
2069           if (REG_VALID_INDEX (cls_node))
2070             for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2071               {
2072                 Idx node = dest_nodes->elems[node_idx];
2073                 if (!re_node_set_contains (dfa->inveclosures + node,
2074                                            cls_node)
2075                     && !re_node_set_contains (dfa->eclosures + node,
2076                                               cls_node))
2077                   {
2078                     /* It is against this limitation.
2079                        Remove it form the current sifted state.  */
2080                     err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2081                                                  candidates);
2082                     if (BE (err != REG_NOERROR, 0))
2083                       return err;
2084                     --node_idx;
2085                   }
2086               }
2087         }
2088       else /* (ent->subexp_to != str_idx)  */
2089         {
2090           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2091             {
2092               Idx node = dest_nodes->elems[node_idx];
2093               re_token_type_t type = dfa->nodes[node].type;
2094               if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2095                 {
2096                   if (subexp_idx != dfa->nodes[node].opr.idx)
2097                     continue;
2098                   /* It is against this limitation.
2099                      Remove it form the current sifted state.  */
2100                   err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2101                                                candidates);
2102                   if (BE (err != REG_NOERROR, 0))
2103                     return err;
2104                 }
2105             }
2106         }
2107     }
2108   return REG_NOERROR;
2109 }
2110
2111 static reg_errcode_t
2112 internal_function
2113 sift_states_bkref (re_match_context_t *mctx, re_sift_context_t *sctx,
2114                    Idx str_idx, const re_node_set *candidates)
2115 {
2116   re_dfa_t *const dfa = mctx->dfa;
2117   reg_errcode_t err;
2118   Idx node_idx, node;
2119   re_sift_context_t local_sctx;
2120   Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2121
2122   if (first_idx == REG_MISSING)
2123     return REG_NOERROR;
2124
2125   local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized.  */
2126
2127   for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2128     {
2129       Idx enabled_idx;
2130       re_token_type_t type;
2131       struct re_backref_cache_entry *entry;
2132       node = candidates->elems[node_idx];
2133       type = dfa->nodes[node].type;
2134       /* Avoid infinite loop for the REs like "()\1+".  */
2135       if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2136         continue;
2137       if (type != OP_BACK_REF)
2138         continue;
2139
2140       entry = mctx->bkref_ents + first_idx;
2141       enabled_idx = first_idx;
2142       do
2143         {
2144           bool ok;
2145           Idx subexp_len, to_idx, dst_node;
2146           re_dfastate_t *cur_state;
2147
2148           if (entry->node != node)
2149             continue;
2150           subexp_len = entry->subexp_to - entry->subexp_from;
2151           to_idx = str_idx + subexp_len;
2152           dst_node = (subexp_len ? dfa->nexts[node]
2153                       : dfa->edests[node].elems[0]);
2154
2155           if (to_idx > sctx->last_str_idx
2156               || sctx->sifted_states[to_idx] == NULL
2157               || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2158               || check_dst_limits (mctx, &sctx->limits, node,
2159                                    str_idx, dst_node, to_idx))
2160             continue;
2161
2162           if (local_sctx.sifted_states == NULL)
2163             {
2164               local_sctx = *sctx;
2165               err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2166               if (BE (err != REG_NOERROR, 0))
2167                 goto free_return;
2168             }
2169           local_sctx.last_node = node;
2170           local_sctx.last_str_idx = str_idx;
2171           ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2172           if (BE (! ok, 0))
2173             {
2174               err = REG_ESPACE;
2175               goto free_return;
2176             }
2177           cur_state = local_sctx.sifted_states[str_idx];
2178           err = sift_states_backward (mctx, &local_sctx);
2179           if (BE (err != REG_NOERROR, 0))
2180             goto free_return;
2181           if (sctx->limited_states != NULL)
2182             {
2183               err = merge_state_array (dfa, sctx->limited_states,
2184                                        local_sctx.sifted_states,
2185                                        str_idx + 1);
2186               if (BE (err != REG_NOERROR, 0))
2187                 goto free_return;
2188             }
2189           local_sctx.sifted_states[str_idx] = cur_state;
2190           re_node_set_remove (&local_sctx.limits, enabled_idx);
2191
2192           /* mctx->bkref_ents may have changed, reload the pointer.  */
2193           entry = mctx->bkref_ents + enabled_idx;
2194         }
2195       while (enabled_idx++, entry++->more);
2196     }
2197   err = REG_NOERROR;
2198  free_return:
2199   if (local_sctx.sifted_states != NULL)
2200     {
2201       re_node_set_free (&local_sctx.limits);
2202     }
2203
2204   return err;
2205 }
2206
2207
2208 #ifdef RE_ENABLE_I18N
2209 static int
2210 internal_function
2211 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2212                      Idx node_idx, Idx str_idx, Idx max_str_idx)
2213 {
2214   re_dfa_t *const dfa = mctx->dfa;
2215   int naccepted;
2216   /* Check the node can accept `multi byte'.  */
2217   naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2218   if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2219       !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2220                             dfa->nexts[node_idx]))
2221     /* The node can't accept the `multi byte', or the
2222        destination was already thrown away, then the node
2223        could't accept the current input `multi byte'.   */
2224     naccepted = 0;
2225   /* Otherwise, it is sure that the node could accept
2226      `naccepted' bytes input.  */
2227   return naccepted;
2228 }
2229 #endif /* RE_ENABLE_I18N */
2230
2231 \f
2232 /* Functions for state transition.  */
2233
2234 /* Return the next state to which the current state STATE will transit by
2235    accepting the current input byte, and update STATE_LOG if necessary.
2236    If STATE can accept a multibyte char/collating element/back reference
2237    update the destination of STATE_LOG.  */
2238
2239 static re_dfastate_t *
2240 internal_function
2241 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2242                re_dfastate_t *state)
2243 {
2244   re_dfastate_t **trtable;
2245   unsigned char ch;
2246
2247 #ifdef RE_ENABLE_I18N
2248   /* If the current state can accept multibyte.  */
2249   if (BE (state->accept_mb, 0))
2250     {
2251       *err = transit_state_mb (mctx, state);
2252       if (BE (*err != REG_NOERROR, 0))
2253         return NULL;
2254     }
2255 #endif /* RE_ENABLE_I18N */
2256
2257   /* Then decide the next state with the single byte.  */
2258 #if 0
2259   if (0)
2260     /* don't use transition table  */
2261     return transit_state_sb (err, mctx, state);
2262 #endif
2263
2264   /* Use transition table  */
2265   ch = re_string_fetch_byte (&mctx->input);
2266   for (;;)
2267     {
2268       trtable = state->trtable;
2269       if (BE (trtable != NULL, 1))
2270         return trtable[ch];
2271
2272       trtable = state->word_trtable;
2273       if (BE (trtable != NULL, 1))
2274         {
2275           unsigned int context;
2276           context
2277             = re_string_context_at (&mctx->input,
2278                                     re_string_cur_idx (&mctx->input) - 1,
2279                                     mctx->eflags);
2280           if (IS_WORD_CONTEXT (context))
2281             return trtable[ch + SBC_MAX];
2282           else
2283             return trtable[ch];
2284         }
2285
2286       if (!build_trtable (mctx->dfa, state))
2287         {
2288           *err = REG_ESPACE;
2289           return NULL;
2290         }
2291
2292       /* Retry, we now have a transition table.  */
2293     }
2294 }
2295
2296 /* Update the state_log if we need */
2297 re_dfastate_t *
2298 internal_function
2299 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2300                       re_dfastate_t *next_state)
2301 {
2302   re_dfa_t *const dfa = mctx->dfa;
2303   Idx cur_idx = re_string_cur_idx (&mctx->input);
2304
2305   if (cur_idx > mctx->state_log_top)
2306     {
2307       mctx->state_log[cur_idx] = next_state;
2308       mctx->state_log_top = cur_idx;
2309     }
2310   else if (mctx->state_log[cur_idx] == 0)
2311     {
2312       mctx->state_log[cur_idx] = next_state;
2313     }
2314   else
2315     {
2316       re_dfastate_t *pstate;
2317       unsigned int context;
2318       re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2319       /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2320          the destination of a multibyte char/collating element/
2321          back reference.  Then the next state is the union set of
2322          these destinations and the results of the transition table.  */
2323       pstate = mctx->state_log[cur_idx];
2324       log_nodes = pstate->entrance_nodes;
2325       if (next_state != NULL)
2326         {
2327           table_nodes = next_state->entrance_nodes;
2328           *err = re_node_set_init_union (&next_nodes, table_nodes,
2329                                              log_nodes);
2330           if (BE (*err != REG_NOERROR, 0))
2331             return NULL;
2332         }
2333       else
2334         next_nodes = *log_nodes;
2335       /* Note: We already add the nodes of the initial state,
2336          then we don't need to add them here.  */
2337
2338       context = re_string_context_at (&mctx->input,
2339                                       re_string_cur_idx (&mctx->input) - 1,
2340                                       mctx->eflags);
2341       next_state = mctx->state_log[cur_idx]
2342         = re_acquire_state_context (err, dfa, &next_nodes, context);
2343       /* We don't need to check errors here, since the return value of
2344          this function is next_state and ERR is already set.  */
2345
2346       if (table_nodes != NULL)
2347         re_node_set_free (&next_nodes);
2348     }
2349
2350   if (BE (dfa->nbackref, 0) && next_state != NULL)
2351     {
2352       /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2353          later.  We must check them here, since the back references in the
2354          next state might use them.  */
2355       *err = check_subexp_matching_top (mctx, &next_state->nodes,
2356                                         cur_idx);
2357       if (BE (*err != REG_NOERROR, 0))
2358         return NULL;
2359
2360       /* If the next state has back references.  */
2361       if (next_state->has_backref)
2362         {
2363           *err = transit_state_bkref (mctx, &next_state->nodes);
2364           if (BE (*err != REG_NOERROR, 0))
2365             return NULL;
2366           next_state = mctx->state_log[cur_idx];
2367         }
2368     }
2369
2370   return next_state;
2371 }
2372
2373 /* Skip bytes in the input that correspond to part of a
2374    multi-byte match, then look in the log for a state
2375    from which to restart matching.  */
2376 static re_dfastate_t *
2377 internal_function
2378 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2379 {
2380   re_dfastate_t *cur_state = NULL;
2381   do
2382     {
2383       Idx max = mctx->state_log_top;
2384       Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2385
2386       do
2387         {
2388           if (++cur_str_idx > max)
2389             return NULL;
2390           re_string_skip_bytes (&mctx->input, 1);
2391         }
2392       while (mctx->state_log[cur_str_idx] == NULL);
2393
2394       cur_state = merge_state_with_log (err, mctx, NULL);
2395     }
2396   while (*err == REG_NOERROR && cur_state == NULL);
2397   return cur_state;
2398 }
2399
2400 /* Helper functions for transit_state.  */
2401
2402 /* From the node set CUR_NODES, pick up the nodes whose types are
2403    OP_OPEN_SUBEXP and which have corresponding back references in the regular
2404    expression. And register them to use them later for evaluating the
2405    correspoding back references.  */
2406
2407 static reg_errcode_t
2408 internal_function
2409 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2410                            Idx str_idx)
2411 {
2412   re_dfa_t *const dfa = mctx->dfa;
2413   Idx node_idx;
2414   reg_errcode_t err;
2415
2416   /* TODO: This isn't efficient.
2417            Because there might be more than one nodes whose types are
2418            OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2419            nodes.
2420            E.g. RE: (a){2}  */
2421   for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2422     {
2423       Idx node = cur_nodes->elems[node_idx];
2424       if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2425           && dfa->nodes[node].opr.idx < CHAR_BIT * sizeof dfa->used_bkref_map
2426           && dfa->used_bkref_map & (1u << dfa->nodes[node].opr.idx))
2427         {
2428           err = match_ctx_add_subtop (mctx, node, str_idx);
2429           if (BE (err != REG_NOERROR, 0))
2430             return err;
2431         }
2432     }
2433   return REG_NOERROR;
2434 }
2435
2436 #if 0
2437 /* Return the next state to which the current state STATE will transit by
2438    accepting the current input byte.  */
2439
2440 static re_dfastate_t *
2441 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2442                   re_dfastate_t *state)
2443 {
2444   re_dfa_t *const dfa = mctx->dfa;
2445   re_node_set next_nodes;
2446   re_dfastate_t *next_state;
2447   Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2448   unsigned int context;
2449
2450   *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2451   if (BE (*err != REG_NOERROR, 0))
2452     return NULL;
2453   for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2454     {
2455       Idx cur_node = state->nodes.elems[node_cnt];
2456       if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2457         {
2458           *err = re_node_set_merge (&next_nodes,
2459                                     dfa->eclosures + dfa->nexts[cur_node]);
2460           if (BE (*err != REG_NOERROR, 0))
2461             {
2462               re_node_set_free (&next_nodes);
2463               return NULL;
2464             }
2465         }
2466     }
2467   context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2468   next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2469   /* We don't need to check errors here, since the return value of
2470      this function is next_state and ERR is already set.  */
2471
2472   re_node_set_free (&next_nodes);
2473   re_string_skip_bytes (&mctx->input, 1);
2474   return next_state;
2475 }
2476 #endif
2477
2478 #ifdef RE_ENABLE_I18N
2479 static reg_errcode_t
2480 internal_function
2481 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2482 {
2483   re_dfa_t *const dfa = mctx->dfa;
2484   reg_errcode_t err;
2485   Idx i;
2486
2487   for (i = 0; i < pstate->nodes.nelem; ++i)
2488     {
2489       re_node_set dest_nodes, *new_nodes;
2490       Idx cur_node_idx = pstate->nodes.elems[i];
2491       int naccepted;
2492       Idx dest_idx;
2493       unsigned int context;
2494       re_dfastate_t *dest_state;
2495
2496       if (!dfa->nodes[cur_node_idx].accept_mb)
2497         continue;
2498
2499       if (dfa->nodes[cur_node_idx].constraint)
2500         {
2501           context = re_string_context_at (&mctx->input,
2502                                           re_string_cur_idx (&mctx->input),
2503                                           mctx->eflags);
2504           if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2505                                            context))
2506             continue;
2507         }
2508
2509       /* How many bytes the node can accept?  */
2510       naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2511                                            re_string_cur_idx (&mctx->input));
2512       if (naccepted == 0)
2513         continue;
2514
2515       /* The node can accepts `naccepted' bytes.  */
2516       dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2517       mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2518                                : mctx->max_mb_elem_len);
2519       err = clean_state_log_if_needed (mctx, dest_idx);
2520       if (BE (err != REG_NOERROR, 0))
2521         return err;
2522 #ifdef DEBUG
2523       assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2524 #endif
2525       new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2526
2527       dest_state = mctx->state_log[dest_idx];
2528       if (dest_state == NULL)
2529         dest_nodes = *new_nodes;
2530       else
2531         {
2532           err = re_node_set_init_union (&dest_nodes,
2533                                         dest_state->entrance_nodes, new_nodes);
2534           if (BE (err != REG_NOERROR, 0))
2535             return err;
2536         }
2537       context = re_string_context_at (&mctx->input, dest_idx - 1, mctx->eflags);
2538       mctx->state_log[dest_idx]
2539         = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2540       if (dest_state != NULL)
2541         re_node_set_free (&dest_nodes);
2542       if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2543         return err;
2544     }
2545   return REG_NOERROR;
2546 }
2547 #endif /* RE_ENABLE_I18N */
2548
2549 static reg_errcode_t
2550 internal_function
2551 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2552 {
2553   re_dfa_t *const dfa = mctx->dfa;
2554   reg_errcode_t err;
2555   Idx i;
2556   Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2557
2558   for (i = 0; i < nodes->nelem; ++i)
2559     {
2560       Idx dest_str_idx, prev_nelem, bkc_idx;
2561       Idx node_idx = nodes->elems[i];
2562       unsigned int context;
2563       const re_token_t *node = dfa->nodes + node_idx;
2564       re_node_set *new_dest_nodes;
2565
2566       /* Check whether `node' is a backreference or not.  */
2567       if (node->type != OP_BACK_REF)
2568         continue;
2569
2570       if (node->constraint)
2571         {
2572           context = re_string_context_at (&mctx->input, cur_str_idx,
2573                                           mctx->eflags);
2574           if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2575             continue;
2576         }
2577
2578       /* `node' is a backreference.
2579          Check the substring which the substring matched.  */
2580       bkc_idx = mctx->nbkref_ents;
2581       err = get_subexp (mctx, node_idx, cur_str_idx);
2582       if (BE (err != REG_NOERROR, 0))
2583         goto free_return;
2584
2585       /* And add the epsilon closures (which is `new_dest_nodes') of
2586          the backreference to appropriate state_log.  */
2587 #ifdef DEBUG
2588       assert (dfa->nexts[node_idx] != REG_MISSING);
2589 #endif
2590       for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2591         {
2592           Idx subexp_len;
2593           re_dfastate_t *dest_state;
2594           struct re_backref_cache_entry *bkref_ent;
2595           bkref_ent = mctx->bkref_ents + bkc_idx;
2596           if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2597             continue;
2598           subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2599           new_dest_nodes = (subexp_len == 0
2600                             ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2601                             : dfa->eclosures + dfa->nexts[node_idx]);
2602           dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2603                           - bkref_ent->subexp_from);
2604           context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2605                                           mctx->eflags);
2606           dest_state = mctx->state_log[dest_str_idx];
2607           prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2608                         : mctx->state_log[cur_str_idx]->nodes.nelem);
2609           /* Add `new_dest_node' to state_log.  */
2610           if (dest_state == NULL)
2611             {
2612               mctx->state_log[dest_str_idx]
2613                 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2614                                             context);
2615               if (BE (mctx->state_log[dest_str_idx] == NULL
2616                       && err != REG_NOERROR, 0))
2617                 goto free_return;
2618             }
2619           else
2620             {
2621               re_node_set dest_nodes;
2622               err = re_node_set_init_union (&dest_nodes,
2623                                             dest_state->entrance_nodes,
2624                                             new_dest_nodes);
2625               if (BE (err != REG_NOERROR, 0))
2626                 {
2627                   re_node_set_free (&dest_nodes);
2628                   goto free_return;
2629                 }
2630               mctx->state_log[dest_str_idx]
2631                 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2632               re_node_set_free (&dest_nodes);
2633               if (BE (mctx->state_log[dest_str_idx] == NULL
2634                       && err != REG_NOERROR, 0))
2635                 goto free_return;
2636             }
2637           /* We need to check recursively if the backreference can epsilon
2638              transit.  */
2639           if (subexp_len == 0
2640               && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2641             {
2642               err = check_subexp_matching_top (mctx, new_dest_nodes,
2643                                                cur_str_idx);
2644               if (BE (err != REG_NOERROR, 0))
2645                 goto free_return;
2646               err = transit_state_bkref (mctx, new_dest_nodes);
2647               if (BE (err != REG_NOERROR, 0))
2648                 goto free_return;
2649             }
2650         }
2651     }
2652   err = REG_NOERROR;
2653  free_return:
2654   return err;
2655 }
2656
2657 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2658    at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2659    Note that we might collect inappropriate candidates here.
2660    However, the cost of checking them strictly here is too high, then we
2661    delay these checking for prune_impossible_nodes().  */
2662
2663 static reg_errcode_t
2664 internal_function
2665 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2666 {
2667   re_dfa_t *const dfa = mctx->dfa;
2668   Idx subexp_num, sub_top_idx;
2669   const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2670   /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX.  */
2671   Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2672   if (cache_idx != REG_MISSING)
2673     {
2674       const struct re_backref_cache_entry *entry = mctx->bkref_ents + cache_idx;
2675       do
2676         if (entry->node == bkref_node)
2677           return REG_NOERROR; /* We already checked it.  */
2678       while (entry++->more);
2679     }
2680
2681   subexp_num = dfa->nodes[bkref_node].opr.idx;
2682
2683   /* For each sub expression  */
2684   for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2685     {
2686       reg_errcode_t err;
2687       re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2688       re_sub_match_last_t *sub_last;
2689       Idx sub_last_idx, sl_str, bkref_str_off;
2690
2691       if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2692         continue; /* It isn't related.  */
2693
2694       sl_str = sub_top->str_idx;
2695       bkref_str_off = bkref_str_idx;
2696       /* At first, check the last node of sub expressions we already
2697          evaluated.  */
2698       for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2699         {
2700           regoff_t sl_str_diff;
2701           sub_last = sub_top->lasts[sub_last_idx];
2702           sl_str_diff = sub_last->str_idx - sl_str;
2703           /* The matched string by the sub expression match with the substring
2704              at the back reference?  */
2705           if (sl_str_diff > 0)
2706             {
2707               if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2708                 {
2709                   /* Not enough chars for a successful match.  */
2710                   if (bkref_str_off + sl_str_diff > mctx->input.len)
2711                     break;
2712
2713                   err = clean_state_log_if_needed (mctx,
2714                                                    bkref_str_off
2715                                                    + sl_str_diff);
2716                   if (BE (err != REG_NOERROR, 0))
2717                     return err;
2718                   buf = (const char *) re_string_get_buffer (&mctx->input);
2719                 }
2720               if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2721                 break; /* We don't need to search this sub expression any more.  */
2722             }
2723           bkref_str_off += sl_str_diff;
2724           sl_str += sl_str_diff;
2725           err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2726                                 bkref_str_idx);
2727
2728           /* Reload buf, since the preceding call might have reallocated
2729              the buffer.  */
2730           buf = (const char *) re_string_get_buffer (&mctx->input);
2731
2732           if (err == REG_NOMATCH)
2733             continue;
2734           if (BE (err != REG_NOERROR, 0))
2735             return err;
2736         }
2737
2738       if (sub_last_idx < sub_top->nlasts)
2739         continue;
2740       if (sub_last_idx > 0)
2741         ++sl_str;
2742       /* Then, search for the other last nodes of the sub expression.  */
2743       for (; sl_str <= bkref_str_idx; ++sl_str)
2744         {
2745           Idx cls_node;
2746           regoff_t sl_str_off;
2747           const re_node_set *nodes;
2748           sl_str_off = sl_str - sub_top->str_idx;
2749           /* The matched string by the sub expression match with the substring
2750              at the back reference?  */
2751           if (sl_str_off > 0)
2752             {
2753               if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2754                 {
2755                   /* If we are at the end of the input, we cannot match.  */
2756                   if (bkref_str_off >= mctx->input.len)
2757                     break;
2758
2759                   err = extend_buffers (mctx);
2760                   if (BE (err != REG_NOERROR, 0))
2761                     return err;
2762
2763                   buf = (const char *) re_string_get_buffer (&mctx->input);
2764                 }
2765               if (buf [bkref_str_off++] != buf[sl_str - 1])
2766                 break; /* We don't need to search this sub expression
2767                           any more.  */
2768             }
2769           if (mctx->state_log[sl_str] == NULL)
2770             continue;
2771           /* Does this state have a ')' of the sub expression?  */
2772           nodes = &mctx->state_log[sl_str]->nodes;
2773           cls_node = find_subexp_node (dfa, nodes, subexp_num, OP_CLOSE_SUBEXP);
2774           if (cls_node == REG_MISSING)
2775             continue; /* No.  */
2776           if (sub_top->path == NULL)
2777             {
2778               sub_top->path = re_calloc (state_array_t,
2779                                          sl_str - sub_top->str_idx + 1);
2780               if (sub_top->path == NULL)
2781                 return REG_ESPACE;
2782             }
2783           /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2784              in the current context?  */
2785           err = check_arrival (mctx, sub_top->path, sub_top->node,
2786                                sub_top->str_idx, cls_node, sl_str, OP_CLOSE_SUBEXP);
2787           if (err == REG_NOMATCH)
2788               continue;
2789           if (BE (err != REG_NOERROR, 0))
2790               return err;
2791           sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2792           if (BE (sub_last == NULL, 0))
2793             return REG_ESPACE;
2794           err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2795                                 bkref_str_idx);
2796           if (err == REG_NOMATCH)
2797             continue;
2798         }
2799     }
2800   return REG_NOERROR;
2801 }
2802
2803 /* Helper functions for get_subexp().  */
2804
2805 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2806    If it can arrive, register the sub expression expressed with SUB_TOP
2807    and SUB_LAST.  */
2808
2809 static reg_errcode_t
2810 internal_function
2811 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2812                 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2813 {
2814   reg_errcode_t err;
2815   Idx to_idx;
2816   /* Can the subexpression arrive the back reference?  */
2817   err = check_arrival (mctx, &sub_last->path, sub_last->node,
2818                        sub_last->str_idx, bkref_node, bkref_str, OP_OPEN_SUBEXP);
2819   if (err != REG_NOERROR)
2820     return err;
2821   err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2822                              sub_last->str_idx);
2823   if (BE (err != REG_NOERROR, 0))
2824     return err;
2825   to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2826   return clean_state_log_if_needed (mctx, to_idx);
2827 }
2828
2829 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2830    Search '(' if FL_OPEN, or search ')' otherwise.
2831    TODO: This function isn't efficient...
2832          Because there might be more than one nodes whose types are
2833          OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2834          nodes.
2835          E.g. RE: (a){2}  */
2836
2837 static Idx
2838 internal_function
2839 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2840                   Idx subexp_idx, int type)
2841 {
2842   Idx cls_idx;
2843   for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2844     {
2845       Idx cls_node = nodes->elems[cls_idx];
2846       const re_token_t *node = dfa->nodes + cls_node;
2847       if (node->type == type
2848           && node->opr.idx == subexp_idx)
2849         return cls_node;
2850     }
2851   return REG_MISSING;
2852 }
2853
2854 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2855    LAST_NODE at LAST_STR.  We record the path onto PATH since it will be
2856    heavily reused.
2857    Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise.  */
2858
2859 static reg_errcode_t
2860 internal_function
2861 check_arrival (re_match_context_t *mctx, state_array_t *path,
2862                Idx top_node, Idx top_str, Idx last_node, Idx last_str,
2863                int type)
2864 {
2865   re_dfa_t *const dfa = mctx->dfa;
2866   reg_errcode_t err;
2867   Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2868   re_dfastate_t *cur_state = NULL;
2869   re_node_set *cur_nodes, next_nodes;
2870   re_dfastate_t **backup_state_log;
2871   unsigned int context;
2872
2873   subexp_num = dfa->nodes[top_node].opr.idx;
2874   /* Extend the buffer if we need.  */
2875   if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2876     {
2877       re_dfastate_t **new_array;
2878       Idx old_alloc = path->alloc;
2879       Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2880       if (BE (new_alloc < old_alloc, 0))
2881         return REG_ESPACE;
2882       new_array = re_xrealloc (path->array, re_dfastate_t *, new_alloc);
2883       if (BE (new_array == NULL, 0))
2884         return REG_ESPACE;
2885       path->array = new_array;
2886       path->alloc = new_alloc;
2887       memset (new_array + old_alloc, '\0',
2888               sizeof (re_dfastate_t *) * (new_alloc - old_alloc));
2889     }
2890
2891   str_idx = path->next_idx == 0 ? top_str : path->next_idx;
2892
2893   /* Temporary modify MCTX.  */
2894   backup_state_log = mctx->state_log;
2895   backup_cur_idx = mctx->input.cur_idx;
2896   mctx->state_log = path->array;
2897   mctx->input.cur_idx = str_idx;
2898
2899   /* Setup initial node set.  */
2900   context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2901   if (str_idx == top_str)
2902     {
2903       err = re_node_set_init_1 (&next_nodes, top_node);
2904       if (BE (err != REG_NOERROR, 0))
2905         return err;
2906       err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2907       if (BE (err != REG_NOERROR, 0))
2908         {
2909           re_node_set_free (&next_nodes);
2910           return err;
2911         }
2912     }
2913   else
2914     {
2915       cur_state = mctx->state_log[str_idx];
2916       if (cur_state && cur_state->has_backref)
2917         {
2918           err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2919           if (BE ( err != REG_NOERROR, 0))
2920             return err;
2921         }
2922       else
2923         re_node_set_init_empty (&next_nodes);
2924     }
2925   if (str_idx == top_str || (cur_state && cur_state->has_backref))
2926     {
2927       if (next_nodes.nelem)
2928         {
2929           err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2930                                     subexp_num, type);
2931           if (BE ( err != REG_NOERROR, 0))
2932             {
2933               re_node_set_free (&next_nodes);
2934               return err;
2935             }
2936         }
2937       cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2938       if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2939         {
2940           re_node_set_free (&next_nodes);
2941           return err;
2942         }
2943       mctx->state_log[str_idx] = cur_state;
2944     }
2945
2946   for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
2947     {
2948       re_node_set_empty (&next_nodes);
2949       if (mctx->state_log[str_idx + 1])
2950         {
2951           err = re_node_set_merge (&next_nodes,
2952                                    &mctx->state_log[str_idx + 1]->nodes);
2953           if (BE (err != REG_NOERROR, 0))
2954             {
2955               re_node_set_free (&next_nodes);
2956               return err;
2957             }
2958         }
2959       if (cur_state)
2960         {
2961           err = check_arrival_add_next_nodes (mctx, str_idx,
2962                                               &cur_state->non_eps_nodes, &next_nodes);
2963           if (BE (err != REG_NOERROR, 0))
2964             {
2965               re_node_set_free (&next_nodes);
2966               return err;
2967             }
2968         }
2969       ++str_idx;
2970       if (next_nodes.nelem)
2971         {
2972           err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2973           if (BE (err != REG_NOERROR, 0))
2974             {
2975               re_node_set_free (&next_nodes);
2976               return err;
2977             }
2978           err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2979                                     subexp_num, type);
2980           if (BE ( err != REG_NOERROR, 0))
2981             {
2982               re_node_set_free (&next_nodes);
2983               return err;
2984             }
2985         }
2986       context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2987       cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2988       if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2989         {
2990           re_node_set_free (&next_nodes);
2991           return err;
2992         }
2993       mctx->state_log[str_idx] = cur_state;
2994       null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
2995     }
2996   re_node_set_free (&next_nodes);
2997   cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
2998                : &mctx->state_log[last_str]->nodes);
2999   path->next_idx = str_idx;
3000
3001   /* Fix MCTX.  */
3002   mctx->state_log = backup_state_log;
3003   mctx->input.cur_idx = backup_cur_idx;
3004
3005   /* Then check the current node set has the node LAST_NODE.  */
3006   if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3007     return REG_NOERROR;
3008
3009   return REG_NOMATCH;
3010 }
3011
3012 /* Helper functions for check_arrival.  */
3013
3014 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3015    to NEXT_NODES.
3016    TODO: This function is similar to the functions transit_state*(),
3017          however this function has many additional works.
3018          Can't we unify them?  */
3019
3020 static reg_errcode_t
3021 internal_function
3022 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3023                               re_node_set *cur_nodes,
3024                               re_node_set *next_nodes)
3025 {
3026   re_dfa_t *const dfa = mctx->dfa;
3027   bool ok;
3028   Idx cur_idx;
3029   reg_errcode_t err;
3030   re_node_set union_set;
3031   re_node_set_init_empty (&union_set);
3032   for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3033     {
3034       int naccepted = 0;
3035       Idx cur_node = cur_nodes->elems[cur_idx];
3036 #ifdef DEBUG
3037       re_token_type_t type = dfa->nodes[cur_node].type;
3038       assert (!IS_EPSILON_NODE (type));
3039 #endif
3040 #ifdef RE_ENABLE_I18N
3041       /* If the node may accept `multi byte'.  */
3042       if (dfa->nodes[cur_node].accept_mb)
3043         {
3044           naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3045                                                str_idx);
3046           if (naccepted > 1)
3047             {
3048               re_dfastate_t *dest_state;
3049               Idx next_node = dfa->nexts[cur_node];
3050               Idx next_idx = str_idx + naccepted;
3051               dest_state = mctx->state_log[next_idx];
3052               re_node_set_empty (&union_set);
3053               if (dest_state)
3054                 {
3055                   err = re_node_set_merge (&union_set, &dest_state->nodes);
3056                   if (BE (err != REG_NOERROR, 0))
3057                     {
3058                       re_node_set_free (&union_set);
3059                       return err;
3060                     }
3061                 }
3062               ok = re_node_set_insert (&union_set, next_node);
3063               if (BE (! ok, 0))
3064                 {
3065                   re_node_set_free (&union_set);
3066                   return REG_ESPACE;
3067                 }
3068               mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3069                                                             &union_set);
3070               if (BE (mctx->state_log[next_idx] == NULL
3071                       && err != REG_NOERROR, 0))
3072                 {
3073                   re_node_set_free (&union_set);
3074                   return err;
3075                 }
3076             }
3077         }
3078 #endif /* RE_ENABLE_I18N */
3079       if (naccepted
3080           || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3081         {
3082           ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3083           if (BE (! ok, 0))
3084             {
3085               re_node_set_free (&union_set);
3086               return REG_ESPACE;
3087             }
3088         }
3089     }
3090   re_node_set_free (&union_set);
3091   return REG_NOERROR;
3092 }
3093
3094 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3095    CUR_NODES, however exclude the nodes which are:
3096     - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3097     - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3098 */
3099
3100 static reg_errcode_t
3101 internal_function
3102 check_arrival_expand_ecl (re_dfa_t *dfa, re_node_set *cur_nodes,
3103                           Idx ex_subexp, int type)
3104 {
3105   reg_errcode_t err;
3106   Idx idx, outside_node;
3107   re_node_set new_nodes;
3108 #ifdef DEBUG
3109   assert (cur_nodes->nelem);
3110 #endif
3111   err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3112   if (BE (err != REG_NOERROR, 0))
3113     return err;
3114   /* Create a new node set NEW_NODES with the nodes which are epsilon
3115      closures of the node in CUR_NODES.  */
3116
3117   for (idx = 0; idx < cur_nodes->nelem; ++idx)
3118     {
3119       Idx cur_node = cur_nodes->elems[idx];
3120       re_node_set *eclosure = dfa->eclosures + cur_node;
3121       outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3122       if (outside_node == REG_MISSING)
3123         {
3124           /* There are no problematic nodes, just merge them.  */
3125           err = re_node_set_merge (&new_nodes, eclosure);
3126           if (BE (err != REG_NOERROR, 0))
3127             {
3128               re_node_set_free (&new_nodes);
3129               return err;
3130             }
3131         }
3132       else
3133         {
3134           /* There are problematic nodes, re-calculate incrementally.  */
3135           err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3136                                               ex_subexp, type);
3137           if (BE (err != REG_NOERROR, 0))
3138             {
3139               re_node_set_free (&new_nodes);
3140               return err;
3141             }
3142         }
3143     }
3144   re_node_set_free (cur_nodes);
3145   *cur_nodes = new_nodes;
3146   return REG_NOERROR;
3147 }
3148
3149 /* Helper function for check_arrival_expand_ecl.
3150    Check incrementally the epsilon closure of TARGET, and if it isn't
3151    problematic append it to DST_NODES.  */
3152
3153 static reg_errcode_t
3154 internal_function
3155 check_arrival_expand_ecl_sub (re_dfa_t *dfa, re_node_set *dst_nodes,
3156                               Idx target, Idx ex_subexp, int type)
3157 {
3158   Idx cur_node;
3159   for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3160     {
3161       bool ok;
3162
3163       if (dfa->nodes[cur_node].type == type
3164           && dfa->nodes[cur_node].opr.idx == ex_subexp)
3165         {
3166           if (type == OP_CLOSE_SUBEXP)
3167             {
3168               ok = re_node_set_insert (dst_nodes, cur_node);
3169               if (BE (! ok, 0))
3170                 return REG_ESPACE;
3171             }
3172           break;
3173         }
3174       ok = re_node_set_insert (dst_nodes, cur_node);
3175       if (BE (! ok, 0))
3176         return REG_ESPACE;
3177       if (dfa->edests[cur_node].nelem == 0)
3178         break;
3179       if (dfa->edests[cur_node].nelem == 2)
3180         {
3181           reg_errcode_t ret =
3182             check_arrival_expand_ecl_sub (dfa, dst_nodes,
3183                                           dfa->edests[cur_node].elems[1],
3184                                           ex_subexp, type);
3185           if (BE (ret != REG_NOERROR, 0))
3186             return ret;
3187         }
3188       cur_node = dfa->edests[cur_node].elems[0];
3189     }
3190   return REG_NOERROR;
3191 }
3192
3193
3194 /* For all the back references in the current state, calculate the
3195    destination of the back references by the appropriate entry
3196    in MCTX->BKREF_ENTS.  */
3197
3198 static reg_errcode_t
3199 internal_function
3200 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3201                     Idx cur_str, Idx subexp_num, int type)
3202 {
3203   re_dfa_t *const dfa = mctx->dfa;
3204   reg_errcode_t err;
3205   Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3206   struct re_backref_cache_entry *ent;
3207
3208   if (cache_idx_start == REG_MISSING)
3209     return REG_NOERROR;
3210
3211  restart:
3212   ent = mctx->bkref_ents + cache_idx_start;
3213   do
3214     {
3215       Idx to_idx, next_node;
3216
3217       /* Is this entry ENT is appropriate?  */
3218       if (!re_node_set_contains (cur_nodes, ent->node))
3219         continue; /* No.  */
3220
3221       to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3222       /* Calculate the destination of the back reference, and append it
3223          to MCTX->STATE_LOG.  */
3224       if (to_idx == cur_str)
3225         {
3226           /* The backreference did epsilon transit, we must re-check all the
3227              node in the current state.  */
3228           re_node_set new_dests;
3229           reg_errcode_t err2, err3;
3230           next_node = dfa->edests[ent->node].elems[0];
3231           if (re_node_set_contains (cur_nodes, next_node))
3232             continue;
3233           err = re_node_set_init_1 (&new_dests, next_node);
3234           err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3235           err3 = re_node_set_merge (cur_nodes, &new_dests);
3236           re_node_set_free (&new_dests);
3237           if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3238                   || err3 != REG_NOERROR, 0))
3239             {
3240               err = (err != REG_NOERROR ? err
3241                      : (err2 != REG_NOERROR ? err2 : err3));
3242               return err;
3243             }
3244           /* TODO: It is still inefficient...  */
3245           goto restart;
3246         }
3247       else
3248         {
3249           re_node_set union_set;
3250           next_node = dfa->nexts[ent->node];
3251           if (mctx->state_log[to_idx])
3252             {
3253               bool ok;
3254               if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3255                                         next_node))
3256                 continue;
3257               err = re_node_set_init_copy (&union_set,
3258                                            &mctx->state_log[to_idx]->nodes);
3259               ok = re_node_set_insert (&union_set, next_node);
3260               if (BE (err != REG_NOERROR || ! ok, 0))
3261                 {
3262                   re_node_set_free (&union_set);
3263                   err = err != REG_NOERROR ? err : REG_ESPACE;
3264                   return err;
3265                 }
3266             }
3267           else
3268             {
3269               err = re_node_set_init_1 (&union_set, next_node);
3270               if (BE (err != REG_NOERROR, 0))
3271                 return err;
3272             }
3273           mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3274           re_node_set_free (&union_set);
3275           if (BE (mctx->state_log[to_idx] == NULL
3276                   && err != REG_NOERROR, 0))
3277             return err;
3278         }
3279     }
3280   while (ent++->more);
3281   return REG_NOERROR;
3282 }
3283
3284 /* Build transition table for the state.
3285    Return true if successful.  */
3286
3287 static bool
3288 internal_function
3289 build_trtable (re_dfa_t *dfa, re_dfastate_t *state)
3290 {
3291   reg_errcode_t err;
3292   Idx i, j;
3293   int ch;
3294   bool need_word_trtable = false;
3295   unsigned int elem, mask;
3296   bool dests_node_malloced = false, dest_states_malloced = false;
3297   Idx ndests; /* Number of the destination states from `state'.  */
3298   re_dfastate_t **trtable;
3299   re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3300   re_node_set follows, *dests_node;
3301   bitset *dests_ch;
3302   bitset acceptable;
3303
3304   /* We build DFA states which corresponds to the destination nodes
3305      from `state'.  `dests_node[i]' represents the nodes which i-th
3306      destination state contains, and `dests_ch[i]' represents the
3307      characters which i-th destination state accepts.  */
3308   if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX))
3309     dests_node = (re_node_set *)
3310       alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3311   else
3312     {
3313       dests_node = (re_node_set *)
3314         malloc ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3315       if (BE (dests_node == NULL, 0))
3316         return false;
3317       dests_node_malloced = true;
3318     }
3319   dests_ch = (bitset *) (dests_node + SBC_MAX);
3320
3321   /* Initialize transiton table.  */
3322   state->word_trtable = state->trtable = NULL;
3323
3324   /* At first, group all nodes belonging to `state' into several
3325      destinations.  */
3326   ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3327   if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3328     {
3329       if (dests_node_malloced)
3330         free (dests_node);
3331       if (ndests == 0)
3332         {
3333           state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3334           return true;
3335         }
3336       return false;
3337     }
3338
3339   err = re_node_set_alloc (&follows, ndests + 1);
3340   if (BE (err != REG_NOERROR, 0))
3341     goto out_free;
3342
3343   /* Avoid arithmetic overflow in size calculation.  */
3344   if (BE (((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX)
3345            / (3 * sizeof (re_dfastate_t *)))
3346           < ndests, 0))
3347     goto out_free;
3348
3349   if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX
3350                          + ndests * 3 * sizeof (re_dfastate_t *)))
3351     dest_states = (re_dfastate_t **)
3352       alloca (ndests * 3 * sizeof (re_dfastate_t *));
3353   else
3354     {
3355       dest_states = (re_dfastate_t **)
3356         malloc (ndests * 3 * sizeof (re_dfastate_t *));
3357       if (BE (dest_states == NULL, 0))
3358         {
3359 out_free:
3360           if (dest_states_malloced)
3361             free (dest_states);
3362           re_node_set_free (&follows);
3363           for (i = 0; i < ndests; ++i)
3364             re_node_set_free (dests_node + i);
3365           if (dests_node_malloced)
3366             free (dests_node);
3367           return false;
3368         }
3369       dest_states_malloced = true;
3370     }
3371   dest_states_word = dest_states + ndests;
3372   dest_states_nl = dest_states_word + ndests;
3373   bitset_empty (acceptable);
3374
3375   /* Then build the states for all destinations.  */
3376   for (i = 0; i < ndests; ++i)
3377     {
3378       Idx next_node;
3379       re_node_set_empty (&follows);
3380       /* Merge the follows of this destination states.  */
3381       for (j = 0; j < dests_node[i].nelem; ++j)
3382         {
3383           next_node = dfa->nexts[dests_node[i].elems[j]];
3384           if (next_node != REG_MISSING)
3385             {
3386               err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3387               if (BE (err != REG_NOERROR, 0))
3388                 goto out_free;
3389             }
3390         }
3391       dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3392       if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3393         goto out_free;
3394       /* If the new state has context constraint,
3395          build appropriate states for these contexts.  */
3396       if (dest_states[i]->has_constraint)
3397         {
3398           dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3399                                                           CONTEXT_WORD);
3400           if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3401             goto out_free;
3402
3403           if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3404             need_word_trtable = true;
3405
3406           dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3407                                                         CONTEXT_NEWLINE);
3408           if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3409             goto out_free;
3410         }
3411       else
3412         {
3413           dest_states_word[i] = dest_states[i];
3414           dest_states_nl[i] = dest_states[i];
3415         }
3416       bitset_merge (acceptable, dests_ch[i]);
3417     }
3418
3419   if (!BE (need_word_trtable, 0))
3420     {
3421       /* We don't care about whether the following character is a word
3422          character, or we are in a single-byte character set so we can
3423          discern by looking at the character code: allocate a
3424          256-entry transition table.  */
3425       trtable = state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3426       if (BE (trtable == NULL, 0))
3427         goto out_free;
3428
3429       /* For all characters ch...:  */
3430       for (i = 0; i < BITSET_UINTS; ++i)
3431         for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3432              elem;
3433              mask <<= 1, elem >>= 1, ++ch)
3434           if (BE (elem & 1, 0))
3435             {
3436               /* There must be exactly one destination which accepts
3437                  character ch.  See group_nodes_into_DFAstates.  */
3438               for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3439                 ;
3440
3441               /* j-th destination accepts the word character ch.  */
3442               if (dfa->word_char[i] & mask)
3443                 trtable[ch] = dest_states_word[j];
3444               else
3445                 trtable[ch] = dest_states[j];
3446             }
3447     }
3448   else
3449     {
3450       /* We care about whether the following character is a word
3451          character, and we are in a multi-byte character set: discern
3452          by looking at the character code: build two 256-entry
3453          transition tables, one starting at trtable[0] and one
3454          starting at trtable[SBC_MAX].  */
3455       trtable = state->word_trtable = re_calloc (re_dfastate_t *, 2 * SBC_MAX);
3456       if (BE (trtable == NULL, 0))
3457         goto out_free;
3458
3459       /* For all characters ch...:  */
3460       for (i = 0; i < BITSET_UINTS; ++i)
3461         for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3462              elem;
3463              mask <<= 1, elem >>= 1, ++ch)
3464           if (BE (elem & 1, 0))
3465             {
3466               /* There must be exactly one destination which accepts
3467                  character ch.  See group_nodes_into_DFAstates.  */
3468               for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3469                 ;
3470
3471               /* j-th destination accepts the word character ch.  */
3472               trtable[ch] = dest_states[j];
3473               trtable[ch + SBC_MAX] = dest_states_word[j];
3474             }
3475     }
3476
3477   /* new line */
3478   if (bitset_contain (acceptable, NEWLINE_CHAR))
3479     {
3480       /* The current state accepts newline character.  */
3481       for (j = 0; j < ndests; ++j)
3482         if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3483           {
3484             /* k-th destination accepts newline character.  */
3485             trtable[NEWLINE_CHAR] = dest_states_nl[j];
3486             if (need_word_trtable)
3487               trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3488             /* There must be only one destination which accepts
3489                newline.  See group_nodes_into_DFAstates.  */
3490             break;
3491           }
3492     }
3493
3494   if (dest_states_malloced)
3495     free (dest_states);
3496
3497   re_node_set_free (&follows);
3498   for (i = 0; i < ndests; ++i)
3499     re_node_set_free (dests_node + i);
3500
3501   if (dests_node_malloced)
3502     free (dests_node);
3503
3504   return true;
3505 }
3506
3507 /* Group all nodes belonging to STATE into several destinations.
3508    Then for all destinations, set the nodes belonging to the destination
3509    to DESTS_NODE[i] and set the characters accepted by the destination
3510    to DEST_CH[i].  This function return the number of destinations.  */
3511
3512 static Idx
3513 internal_function
3514 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3515                             re_node_set *dests_node, bitset *dests_ch)
3516 {
3517   reg_errcode_t err;
3518   bool ok;
3519   Idx i, j, k;
3520   Idx ndests; /* Number of the destinations from `state'.  */
3521   bitset accepts; /* Characters a node can accept.  */
3522   const re_node_set *cur_nodes = &state->nodes;
3523   bitset_empty (accepts);
3524   ndests = 0;
3525
3526   /* For all the nodes belonging to `state',  */
3527   for (i = 0; i < cur_nodes->nelem; ++i)
3528     {
3529       re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3530       re_token_type_t type = node->type;
3531       unsigned int constraint = node->constraint;
3532
3533       /* Enumerate all single byte character this node can accept.  */
3534       if (type == CHARACTER)
3535         bitset_set (accepts, node->opr.c);
3536       else if (type == SIMPLE_BRACKET)
3537         {
3538           bitset_merge (accepts, node->opr.sbcset);
3539         }
3540       else if (type == OP_PERIOD)
3541         {
3542 #ifdef RE_ENABLE_I18N
3543           if (dfa->mb_cur_max > 1)
3544             bitset_merge (accepts, dfa->sb_char);
3545           else
3546 #endif
3547             bitset_set_all (accepts);
3548           if (!(dfa->syntax & REG_DOT_NEWLINE))
3549             bitset_clear (accepts, '\n');
3550           if (dfa->syntax & REG_DOT_NOT_NULL)
3551             bitset_clear (accepts, '\0');
3552         }
3553 #ifdef RE_ENABLE_I18N
3554       else if (type == OP_UTF8_PERIOD)
3555         {
3556           memset (accepts, 255, sizeof (unsigned int) * BITSET_UINTS / 2);
3557           if (!(dfa->syntax & REG_DOT_NEWLINE))
3558             bitset_clear (accepts, '\n');
3559           if (dfa->syntax & REG_DOT_NOT_NULL)
3560             bitset_clear (accepts, '\0');
3561         }
3562 #endif
3563       else
3564         continue;
3565
3566       /* Check the `accepts' and sift the characters which are not
3567          match it the context.  */
3568       if (constraint)
3569         {
3570           if (constraint & NEXT_NEWLINE_CONSTRAINT)
3571             {
3572               unsigned int accepts_newline =
3573                 bitset_contain (accepts, NEWLINE_CHAR);
3574               bitset_empty (accepts);
3575               if (accepts_newline)
3576                 bitset_set (accepts, NEWLINE_CHAR);
3577               else
3578                 continue;
3579             }
3580           if (constraint & NEXT_ENDBUF_CONSTRAINT)
3581             {
3582               bitset_empty (accepts);
3583               continue;
3584             }
3585
3586           if (constraint & NEXT_WORD_CONSTRAINT)
3587             {
3588               unsigned int any_set = 0;
3589               if (type == CHARACTER && !node->word_char)
3590                 {
3591                   bitset_empty (accepts);
3592                   continue;
3593                 }
3594 #ifdef RE_ENABLE_I18N
3595               if (dfa->mb_cur_max > 1)
3596                 for (j = 0; j < BITSET_UINTS; ++j)
3597                   any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3598               else
3599 #endif
3600                 for (j = 0; j < BITSET_UINTS; ++j)
3601                   any_set |= (accepts[j] &= dfa->word_char[j]);
3602               if (!any_set)
3603                 continue;
3604             }
3605           if (constraint & NEXT_NOTWORD_CONSTRAINT)
3606             {
3607               unsigned int any_set = 0;
3608               if (type == CHARACTER && node->word_char)
3609                 {
3610                   bitset_empty (accepts);
3611                   continue;
3612                 }
3613 #ifdef RE_ENABLE_I18N
3614               if (dfa->mb_cur_max > 1)
3615                 for (j = 0; j < BITSET_UINTS; ++j)
3616                   any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3617               else
3618 #endif
3619                 for (j = 0; j < BITSET_UINTS; ++j)
3620                   any_set |= (accepts[j] &= ~dfa->word_char[j]);
3621               if (!any_set)
3622                 continue;
3623             }
3624         }
3625
3626       /* Then divide `accepts' into DFA states, or create a new
3627          state.  Above, we make sure that accepts is not empty.  */
3628       for (j = 0; j < ndests; ++j)
3629         {
3630           bitset intersec; /* Intersection sets, see below.  */
3631           bitset remains;
3632           /* Flags, see below.  */
3633           unsigned int has_intersec, not_subset, not_consumed;
3634
3635           /* Optimization, skip if this state doesn't accept the character.  */
3636           if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3637             continue;
3638
3639           /* Enumerate the intersection set of this state and `accepts'.  */
3640           has_intersec = 0;
3641           for (k = 0; k < BITSET_UINTS; ++k)
3642             has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3643           /* And skip if the intersection set is empty.  */
3644           if (!has_intersec)
3645             continue;
3646
3647           /* Then check if this state is a subset of `accepts'.  */
3648           not_subset = not_consumed = 0;
3649           for (k = 0; k < BITSET_UINTS; ++k)
3650             {
3651               not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3652               not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3653             }
3654
3655           /* If this state isn't a subset of `accepts', create a
3656              new group state, which has the `remains'. */
3657           if (not_subset)
3658             {
3659               bitset_copy (dests_ch[ndests], remains);
3660               bitset_copy (dests_ch[j], intersec);
3661               err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3662               if (BE (err != REG_NOERROR, 0))
3663                 goto error_return;
3664               ++ndests;
3665             }
3666
3667           /* Put the position in the current group. */
3668           ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3669           if (BE (! ok, 0))
3670             goto error_return;
3671
3672           /* If all characters are consumed, go to next node. */
3673           if (!not_consumed)
3674             break;
3675         }
3676       /* Some characters remain, create a new group. */
3677       if (j == ndests)
3678         {
3679           bitset_copy (dests_ch[ndests], accepts);
3680           err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3681           if (BE (err != REG_NOERROR, 0))
3682             goto error_return;
3683           ++ndests;
3684           bitset_empty (accepts);
3685         }
3686     }
3687   return ndests;
3688  error_return:
3689   for (j = 0; j < ndests; ++j)
3690     re_node_set_free (dests_node + j);
3691   return REG_MISSING;
3692 }
3693
3694 #ifdef RE_ENABLE_I18N
3695 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3696    Return the number of the bytes the node accepts.
3697    STR_IDX is the current index of the input string.
3698
3699    This function handles the nodes which can accept one character, or
3700    one collating element like '.', '[a-z]', opposite to the other nodes
3701    can only accept one byte.  */
3702
3703 static int
3704 internal_function
3705 check_node_accept_bytes (re_dfa_t *dfa, Idx node_idx,
3706                          const re_string_t *input, Idx str_idx)
3707 {
3708   const re_token_t *node = dfa->nodes + node_idx;
3709   int char_len, elem_len;
3710   Idx i;
3711
3712   if (BE (node->type == OP_UTF8_PERIOD, 0))
3713     {
3714       unsigned char c = re_string_byte_at (input, str_idx), d;
3715       if (BE (c < 0xc2, 1))
3716         return 0;
3717
3718       if (str_idx + 2 > input->len)
3719         return 0;
3720
3721       d = re_string_byte_at (input, str_idx + 1);
3722       if (c < 0xe0)
3723         return (d < 0x80 || d > 0xbf) ? 0 : 2;
3724       else if (c < 0xf0)
3725         {
3726           char_len = 3;
3727           if (c == 0xe0 && d < 0xa0)
3728             return 0;
3729         }
3730       else if (c < 0xf8)
3731         {
3732           char_len = 4;
3733           if (c == 0xf0 && d < 0x90)
3734             return 0;
3735         }
3736       else if (c < 0xfc)
3737         {
3738           char_len = 5;
3739           if (c == 0xf8 && d < 0x88)
3740             return 0;
3741         }
3742       else if (c < 0xfe)
3743         {
3744           char_len = 6;
3745           if (c == 0xfc && d < 0x84)
3746             return 0;
3747         }
3748       else
3749         return 0;
3750
3751       if (str_idx + char_len > input->len)
3752         return 0;
3753
3754       for (i = 1; i < char_len; ++i)
3755         {
3756           d = re_string_byte_at (input, str_idx + i);
3757           if (d < 0x80 || d > 0xbf)
3758             return 0;
3759         }
3760       return char_len;
3761     }
3762
3763   char_len = re_string_char_size_at (input, str_idx);
3764   if (node->type == OP_PERIOD)
3765     {
3766       if (char_len <= 1)
3767         return 0;
3768       /* FIXME: I don't think this if is needed, as both '\n'
3769          and '\0' are char_len == 1.  */
3770       /* '.' accepts any one character except the following two cases.  */
3771       if ((!(dfa->syntax & REG_DOT_NEWLINE) &&
3772            re_string_byte_at (input, str_idx) == '\n') ||
3773           ((dfa->syntax & REG_DOT_NOT_NULL) &&
3774            re_string_byte_at (input, str_idx) == '\0'))
3775         return 0;
3776       return char_len;
3777     }
3778
3779   elem_len = re_string_elem_size_at (input, str_idx);
3780   if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3781     return 0;
3782
3783   if (node->type == COMPLEX_BRACKET)
3784     {
3785       const re_charset_t *cset = node->opr.mbcset;
3786 # ifdef _LIBC
3787       const unsigned char *pin
3788         = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3789       Idx j;
3790       uint32_t nrules;
3791 # endif /* _LIBC */
3792       int match_len = 0;
3793       wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3794                     ? re_string_wchar_at (input, str_idx) : 0);
3795
3796       /* match with multibyte character?  */
3797       for (i = 0; i < cset->nmbchars; ++i)
3798         if (wc == cset->mbchars[i])
3799           {
3800             match_len = char_len;
3801             goto check_node_accept_bytes_match;
3802           }
3803       /* match with character_class?  */
3804       for (i = 0; i < cset->nchar_classes; ++i)
3805         {
3806           wctype_t wt = cset->char_classes[i];
3807           if (__iswctype (wc, wt))
3808             {
3809               match_len = char_len;
3810               goto check_node_accept_bytes_match;
3811             }
3812         }
3813
3814 # ifdef _LIBC
3815       nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3816       if (nrules != 0)
3817         {
3818           unsigned int in_collseq = 0;
3819           const int32_t *table, *indirect;
3820           const unsigned char *weights, *extra;
3821           const char *collseqwc;
3822           int32_t idx;
3823           /* This #include defines a local function!  */
3824 #  include <locale/weight.h>
3825
3826           /* match with collating_symbol?  */
3827           if (cset->ncoll_syms)
3828             extra = (const unsigned char *)
3829               _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3830           for (i = 0; i < cset->ncoll_syms; ++i)
3831             {
3832               const unsigned char *coll_sym = extra + cset->coll_syms[i];
3833               /* Compare the length of input collating element and
3834                  the length of current collating element.  */
3835               if (*coll_sym != elem_len)
3836                 continue;
3837               /* Compare each bytes.  */
3838               for (j = 0; j < *coll_sym; j++)
3839                 if (pin[j] != coll_sym[1 + j])
3840                   break;
3841               if (j == *coll_sym)
3842                 {
3843                   /* Match if every bytes is equal.  */
3844                   match_len = j;
3845                   goto check_node_accept_bytes_match;
3846                 }
3847             }
3848
3849           if (cset->nranges)
3850             {
3851               if (elem_len <= char_len)
3852                 {
3853                   collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3854                   in_collseq = __collseq_table_lookup (collseqwc, wc);
3855                 }
3856               else
3857                 in_collseq = find_collation_sequence_value (pin, elem_len);
3858             }
3859           /* match with range expression?  */
3860           for (i = 0; i < cset->nranges; ++i)
3861             if (cset->range_starts[i] <= in_collseq
3862                 && in_collseq <= cset->range_ends[i])
3863               {
3864                 match_len = elem_len;
3865                 goto check_node_accept_bytes_match;
3866               }
3867
3868           /* match with equivalence_class?  */
3869           if (cset->nequiv_classes)
3870             {
3871               const unsigned char *cp = pin;
3872               table = (const int32_t *)
3873                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3874               weights = (const unsigned char *)
3875                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3876               extra = (const unsigned char *)
3877                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3878               indirect = (const int32_t *)
3879                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3880               idx = findidx (&cp);
3881               if (idx > 0)
3882                 for (i = 0; i < cset->nequiv_classes; ++i)
3883                   {
3884                     int32_t equiv_class_idx = cset->equiv_classes[i];
3885                     size_t weight_len = weights[idx];
3886                     if (weight_len == weights[equiv_class_idx])
3887                       {
3888                         Idx cnt = 0;
3889                         while (cnt <= weight_len
3890                                && (weights[equiv_class_idx + 1 + cnt]
3891                                    == weights[idx + 1 + cnt]))
3892                           ++cnt;
3893                         if (cnt > weight_len)
3894                           {
3895                             match_len = elem_len;
3896                             goto check_node_accept_bytes_match;
3897                           }
3898                       }
3899                   }
3900             }
3901         }
3902       else
3903 # endif /* _LIBC */
3904         {
3905           /* match with range expression?  */
3906 #if __GNUC__ >= 2
3907           wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3908 #else
3909           wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3910           cmp_buf[2] = wc;
3911 #endif
3912           for (i = 0; i < cset->nranges; ++i)
3913             {
3914               cmp_buf[0] = cset->range_starts[i];
3915               cmp_buf[4] = cset->range_ends[i];
3916               if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3917                   && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3918                 {
3919                   match_len = char_len;
3920                   goto check_node_accept_bytes_match;
3921                 }
3922             }
3923         }
3924     check_node_accept_bytes_match:
3925       if (!cset->non_match)
3926         return match_len;
3927       else
3928         {
3929           if (match_len > 0)
3930             return 0;
3931           else
3932             return (elem_len > char_len) ? elem_len : char_len;
3933         }
3934     }
3935   return 0;
3936 }
3937
3938 # ifdef _LIBC
3939 static unsigned int
3940 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
3941 {
3942   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3943   if (nrules == 0)
3944     {
3945       if (mbs_len == 1)
3946         {
3947           /* No valid character.  Match it as a single byte character.  */
3948           const unsigned char *collseq = (const unsigned char *)
3949             _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3950           return collseq[mbs[0]];
3951         }
3952       return UINT_MAX;
3953     }
3954   else
3955     {
3956       int32_t idx;
3957       const unsigned char *extra = (const unsigned char *)
3958         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3959       int32_t extrasize = (const unsigned char *)
3960         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
3961
3962       for (idx = 0; idx < extrasize;)
3963         {
3964           int mbs_cnt;
3965           bool found = false;
3966           int32_t elem_mbs_len;
3967           /* Skip the name of collating element name.  */
3968           idx = idx + extra[idx] + 1;
3969           elem_mbs_len = extra[idx++];
3970           if (mbs_len == elem_mbs_len)
3971             {
3972               for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
3973                 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
3974                   break;
3975               if (mbs_cnt == elem_mbs_len)
3976                 /* Found the entry.  */
3977                 found = true;
3978             }
3979           /* Skip the byte sequence of the collating element.  */
3980           idx += elem_mbs_len;
3981           /* Adjust for the alignment.  */
3982           idx = (idx + 3) & ~3;
3983           /* Skip the collation sequence value.  */
3984           idx += sizeof (uint32_t);
3985           /* Skip the wide char sequence of the collating element.  */
3986           idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
3987           /* If we found the entry, return the sequence value.  */
3988           if (found)
3989             return *(uint32_t *) (extra + idx);
3990           /* Skip the collation sequence value.  */
3991           idx += sizeof (uint32_t);
3992         }
3993       return UINT_MAX;
3994     }
3995 }
3996 # endif /* _LIBC */
3997 #endif /* RE_ENABLE_I18N */
3998
3999 /* Check whether the node accepts the byte which is IDX-th
4000    byte of the INPUT.  */
4001
4002 static bool
4003 internal_function
4004 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4005                    Idx idx)
4006 {
4007   unsigned char ch;
4008   ch = re_string_byte_at (&mctx->input, idx);
4009   switch (node->type)
4010     {
4011     case CHARACTER:
4012       if (node->opr.c != ch)
4013         return false;
4014       break;
4015
4016     case SIMPLE_BRACKET:
4017       if (!bitset_contain (node->opr.sbcset, ch))
4018         return false;
4019       break;
4020
4021 #ifdef RE_ENABLE_I18N
4022     case OP_UTF8_PERIOD:
4023       if (ch >= 0x80)
4024         return false;
4025       /* FALLTHROUGH */
4026 #endif
4027     case OP_PERIOD:
4028       if ((ch == '\n' && !(mctx->dfa->syntax & REG_DOT_NEWLINE))
4029           || (ch == '\0' && (mctx->dfa->syntax & REG_DOT_NOT_NULL)))
4030         return false;
4031       break;
4032
4033     default:
4034       return false;
4035     }
4036
4037   if (node->constraint)
4038     {
4039       /* The node has constraints.  Check whether the current context
4040          satisfies the constraints.  */
4041       unsigned int context = re_string_context_at (&mctx->input, idx,
4042                                                    mctx->eflags);
4043       if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4044         return false;
4045     }
4046
4047   return true;
4048 }
4049
4050 /* Extend the buffers, if the buffers have run out.  */
4051
4052 static reg_errcode_t
4053 internal_function
4054 extend_buffers (re_match_context_t *mctx)
4055 {
4056   reg_errcode_t ret;
4057   re_string_t *pstr = &mctx->input;
4058
4059   /* Double the lengthes of the buffers.  */
4060   ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4061   if (BE (ret != REG_NOERROR, 0))
4062     return ret;
4063
4064   if (mctx->state_log != NULL)
4065     {
4066       /* And double the length of state_log.  */
4067       /* XXX We have no indication of the size of this buffer.  If this
4068          allocation fail we have no indication that the state_log array
4069          does not have the right size.  */
4070       re_dfastate_t **new_array = re_xrealloc (mctx->state_log, re_dfastate_t *,
4071                                                pstr->bufs_len + 1);
4072       if (BE (new_array == NULL, 0))
4073         return REG_ESPACE;
4074       mctx->state_log = new_array;
4075     }
4076
4077   /* Then reconstruct the buffers.  */
4078   if (pstr->icase)
4079     {
4080 #ifdef RE_ENABLE_I18N
4081       if (pstr->mb_cur_max > 1)
4082         {
4083           ret = build_wcs_upper_buffer (pstr);
4084           if (BE (ret != REG_NOERROR, 0))
4085             return ret;
4086         }
4087       else
4088 #endif /* RE_ENABLE_I18N  */
4089         build_upper_buffer (pstr);
4090     }
4091   else
4092     {
4093 #ifdef RE_ENABLE_I18N
4094       if (pstr->mb_cur_max > 1)
4095         build_wcs_buffer (pstr);
4096       else
4097 #endif /* RE_ENABLE_I18N  */
4098         {
4099           if (pstr->trans != NULL)
4100             re_string_translate_buffer (pstr);
4101         }
4102     }
4103   return REG_NOERROR;
4104 }
4105
4106 \f
4107 /* Functions for matching context.  */
4108
4109 /* Initialize MCTX.  */
4110
4111 static reg_errcode_t
4112 internal_function
4113 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4114 {
4115   mctx->eflags = eflags;
4116   mctx->match_last = REG_MISSING;
4117   if (n > 0)
4118     {
4119       mctx->bkref_ents = re_xmalloc (struct re_backref_cache_entry, n);
4120       mctx->sub_tops = re_xmalloc (re_sub_match_top_t *, n);
4121       if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4122         return REG_ESPACE;
4123     }
4124   /* Already zero-ed by the caller.
4125      else
4126        mctx->bkref_ents = NULL;
4127      mctx->nbkref_ents = 0;
4128      mctx->nsub_tops = 0;  */
4129   mctx->abkref_ents = n;
4130   mctx->max_mb_elem_len = 1;
4131   mctx->asub_tops = n;
4132   return REG_NOERROR;
4133 }
4134
4135 /* Clean the entries which depend on the current input in MCTX.
4136    This function must be invoked when the matcher changes the start index
4137    of the input, or changes the input string.  */
4138
4139 static void
4140 internal_function
4141 match_ctx_clean (re_match_context_t *mctx)
4142 {
4143   Idx st_idx;
4144   for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4145     {
4146       Idx sl_idx;
4147       re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4148       for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4149         {
4150           re_sub_match_last_t *last = top->lasts[sl_idx];
4151           re_free (last->path.array);
4152           re_free (last);
4153         }
4154       re_free (top->lasts);
4155       if (top->path)
4156         {
4157           re_free (top->path->array);
4158           re_free (top->path);
4159         }
4160       free (top);
4161     }
4162
4163   mctx->nsub_tops = 0;
4164   mctx->nbkref_ents = 0;
4165 }
4166
4167 /* Free all the memory associated with MCTX.  */
4168
4169 static void
4170 internal_function
4171 match_ctx_free (re_match_context_t *mctx)
4172 {
4173   /* First, free all the memory associated with MCTX->SUB_TOPS.  */
4174   match_ctx_clean (mctx);
4175   re_free (mctx->sub_tops);
4176   re_free (mctx->bkref_ents);
4177 }
4178
4179 /* Add a new backreference entry to MCTX.
4180    Note that we assume that caller never call this function with duplicate
4181    entry, and call with STR_IDX which isn't smaller than any existing entry.
4182 */
4183
4184 static reg_errcode_t
4185 internal_function
4186 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx,
4187                      Idx from, Idx to)
4188 {
4189   if (mctx->nbkref_ents >= mctx->abkref_ents)
4190     {
4191       struct re_backref_cache_entry* new_entry;
4192       new_entry = re_x2realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4193                                 &mctx->abkref_ents);
4194       if (BE (new_entry == NULL, 0))
4195         {
4196           re_free (mctx->bkref_ents);
4197           return REG_ESPACE;
4198         }
4199       mctx->bkref_ents = new_entry;
4200       memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4201               (sizeof (struct re_backref_cache_entry)
4202                * (mctx->abkref_ents - mctx->nbkref_ents)));
4203     }
4204   if (mctx->nbkref_ents > 0
4205       && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4206     mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4207
4208   mctx->bkref_ents[mctx->nbkref_ents].node = node;
4209   mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4210   mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4211   mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4212
4213   /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4214      If bit N is clear, means that this entry won't epsilon-transition to
4215      an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression.  If
4216      it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4217      such node.
4218
4219      A backreference does not epsilon-transition unless it is empty, so set
4220      to all zeros if FROM != TO.  */
4221   mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4222     = (from == to ? -1 : 0);
4223
4224   mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4225   if (mctx->max_mb_elem_len < to - from)
4226     mctx->max_mb_elem_len = to - from;
4227   return REG_NOERROR;
4228 }
4229
4230 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4231    found.  Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX.  */
4232
4233 static Idx
4234 internal_function
4235 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4236 {
4237   Idx left, right, mid, last;
4238   last = right = mctx->nbkref_ents;
4239   for (left = 0; left < right;)
4240     {
4241       mid = (left + right) / 2;
4242       if (mctx->bkref_ents[mid].str_idx < str_idx)
4243         left = mid + 1;
4244       else
4245         right = mid;
4246     }
4247   if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4248     return left;
4249   else
4250     return REG_MISSING;
4251 }
4252
4253 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4254    at STR_IDX.  */
4255
4256 static reg_errcode_t
4257 internal_function
4258 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4259 {
4260 #ifdef DEBUG
4261   assert (mctx->sub_tops != NULL);
4262   assert (mctx->asub_tops > 0);
4263 #endif
4264   if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4265     {
4266       Idx new_asub_tops = mctx->asub_tops;
4267       re_sub_match_top_t **new_array = re_x2realloc (mctx->sub_tops,
4268                                                      re_sub_match_top_t *,
4269                                                      &new_asub_tops);
4270       if (BE (new_array == NULL, 0))
4271         return REG_ESPACE;
4272       mctx->sub_tops = new_array;
4273       mctx->asub_tops = new_asub_tops;
4274     }
4275   mctx->sub_tops[mctx->nsub_tops] = re_calloc (re_sub_match_top_t, 1);
4276   if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4277     return REG_ESPACE;
4278   mctx->sub_tops[mctx->nsub_tops]->node = node;
4279   mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4280   return REG_NOERROR;
4281 }
4282
4283 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4284    at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP.  */
4285
4286 static re_sub_match_last_t *
4287 internal_function
4288 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4289 {
4290   re_sub_match_last_t *new_entry;
4291   if (BE (subtop->nlasts == subtop->alasts, 0))
4292     {
4293       Idx new_alasts = subtop->alasts;
4294       re_sub_match_last_t **new_array = re_x2realloc (subtop->lasts,
4295                                                       re_sub_match_last_t *,
4296                                                       &new_alasts);
4297       if (BE (new_array == NULL, 0))
4298         return NULL;
4299       subtop->lasts = new_array;
4300       subtop->alasts = new_alasts;
4301     }
4302   new_entry = re_calloc (re_sub_match_last_t, 1);
4303   if (BE (new_entry != NULL, 1))
4304     {
4305       subtop->lasts[subtop->nlasts] = new_entry;
4306       new_entry->node = node;
4307       new_entry->str_idx = str_idx;
4308       ++subtop->nlasts;
4309     }
4310   return new_entry;
4311 }
4312
4313 static void
4314 internal_function
4315 sift_ctx_init (re_sift_context_t *sctx,
4316                re_dfastate_t **sifted_sts,
4317                re_dfastate_t **limited_sts,
4318                Idx last_node, Idx last_str_idx)
4319 {
4320   sctx->sifted_states = sifted_sts;
4321   sctx->limited_states = limited_sts;
4322   sctx->last_node = last_node;
4323   sctx->last_str_idx = last_str_idx;
4324   re_node_set_init_empty (&sctx->limits);
4325 }