lib/regexec.c

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