lib/regexec.c

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