git.cworth.org Git - tar/blob - lib/regexec.c

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