lib/regexec.c

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