gl/regexec.c

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