lib/regexec.c

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