posix/regexec.c

   1 /* Extended regular expression matching and search library.
   2    Copyright (C) 2002-2021 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
1359 #define DYNARRAY_STRUCT  regmatch_list
1360 #define DYNARRAY_ELEMENT regmatch_t
1361 #define DYNARRAY_PREFIX  regmatch_list_
1362 #include <malloc/dynarray-skeleton.c>
1363
1364 /* Set the positions where the subexpressions are starts/ends to registers
1365    PMATCH.
1366    Note: We assume that pmatch[0] is already set, and
1367    pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch.  */
1368
1369 static reg_errcode_t
1370 __attribute_warn_unused_result__
1371 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1372           regmatch_t *pmatch, bool fl_backtrack)
1373 {
1374   const re_dfa_t *dfa = preg->buffer;
1375   Idx idx, cur_node;
1376   re_node_set eps_via_nodes;
1377   struct re_fail_stack_t *fs;
1378   struct re_fail_stack_t fs_body = { 0, 2, NULL };
1379   struct regmatch_list prev_match;
1380   regmatch_list_init (&prev_match);
1381
1382   DEBUG_ASSERT (nmatch > 1);
1383   DEBUG_ASSERT (mctx->state_log != NULL);
1384   if (fl_backtrack)
1385     {
1386       fs = &fs_body;
1387       fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1388       if (fs->stack == NULL)
1389         return REG_ESPACE;
1390     }
1391   else
1392     fs = NULL;
1393
1394   cur_node = dfa->init_node;
1395   re_node_set_init_empty (&eps_via_nodes);
1396
1397   if (!regmatch_list_resize (&prev_match, nmatch))
1398     {
1399       regmatch_list_free (&prev_match);
1400       free_fail_stack_return (fs);
1401       return REG_ESPACE;
1402     }
1403   regmatch_t *prev_idx_match = regmatch_list_begin (&prev_match);
1404   memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1405
1406   for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1407     {
1408       update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1409
1410       if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1411         {
1412           Idx reg_idx;
1413           if (fs)
1414             {
1415               for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1416                 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1417                   break;
1418               if (reg_idx == nmatch)
1419                 {
1420                   re_node_set_free (&eps_via_nodes);
1421                   regmatch_list_free (&prev_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               regmatch_list_free (&prev_match);
1431               return REG_NOERROR;
1432             }
1433         }
1434
1435       /* Proceed to next node.  */
1436       cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1437                                     &eps_via_nodes, fs);
1438
1439       if (__glibc_unlikely (cur_node < 0))
1440         {
1441           if (__glibc_unlikely (cur_node == -2))
1442             {
1443               re_node_set_free (&eps_via_nodes);
1444               regmatch_list_free (&prev_match);
1445               free_fail_stack_return (fs);
1446               return REG_ESPACE;
1447             }
1448           if (fs)
1449             cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1450                                        &eps_via_nodes);
1451           else
1452             {
1453               re_node_set_free (&eps_via_nodes);
1454               regmatch_list_free (&prev_match);
1455               return REG_NOMATCH;
1456             }
1457         }
1458     }
1459   re_node_set_free (&eps_via_nodes);
1460   regmatch_list_free (&prev_match);
1461   return free_fail_stack_return (fs);
1462 }
1463
1464 static reg_errcode_t
1465 free_fail_stack_return (struct re_fail_stack_t *fs)
1466 {
1467   if (fs)
1468     {
1469       Idx fs_idx;
1470       for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1471         {
1472           re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1473           re_free (fs->stack[fs_idx].regs);
1474         }
1475       re_free (fs->stack);
1476     }
1477   return REG_NOERROR;
1478 }
1479
1480 static void
1481 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1482              regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1483 {
1484   int type = dfa->nodes[cur_node].type;
1485   if (type == OP_OPEN_SUBEXP)
1486     {
1487       Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1488
1489       /* We are at the first node of this sub expression.  */
1490       if (reg_num < nmatch)
1491         {
1492           pmatch[reg_num].rm_so = cur_idx;
1493           pmatch[reg_num].rm_eo = -1;
1494         }
1495     }
1496   else if (type == OP_CLOSE_SUBEXP)
1497     {
1498       Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1499       if (reg_num < nmatch)
1500         {
1501           /* We are at the last node of this sub expression.  */
1502           if (pmatch[reg_num].rm_so < cur_idx)
1503             {
1504               pmatch[reg_num].rm_eo = cur_idx;
1505               /* This is a non-empty match or we are not inside an optional
1506                  subexpression.  Accept this right away.  */
1507               memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1508             }
1509           else
1510             {
1511               if (dfa->nodes[cur_node].opt_subexp
1512                   && prev_idx_match[reg_num].rm_so != -1)
1513                 /* We transited through an empty match for an optional
1514                    subexpression, like (a?)*, and this is not the subexp's
1515                    first match.  Copy back the old content of the registers
1516                    so that matches of an inner subexpression are undone as
1517                    well, like in ((a?))*.  */
1518                 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1519               else
1520                 /* We completed a subexpression, but it may be part of
1521                    an optional one, so do not update PREV_IDX_MATCH.  */
1522                 pmatch[reg_num].rm_eo = cur_idx;
1523             }
1524         }
1525     }
1526 }
1527
1528 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1529    and sift the nodes in each states according to the following rules.
1530    Updated state_log will be wrote to STATE_LOG.
1531
1532    Rules: We throw away the Node 'a' in the STATE_LOG[STR_IDX] if...
1533      1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1534         If 'a' isn't the LAST_NODE and 'a' can't epsilon transit to
1535         the LAST_NODE, we throw away the node 'a'.
1536      2. When 0 <= STR_IDX < MATCH_LAST and 'a' accepts
1537         string 's' and transit to 'b':
1538         i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1539            away the node 'a'.
1540         ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1541             thrown away, we throw away the node 'a'.
1542      3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1543         i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1544            node 'a'.
1545         ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1546             we throw away the node 'a'.  */
1547
1548 #define STATE_NODE_CONTAINS(state,node) \
1549   ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1550
1551 static reg_errcode_t
1552 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1553 {
1554   reg_errcode_t err;
1555   int null_cnt = 0;
1556   Idx str_idx = sctx->last_str_idx;
1557   re_node_set cur_dest;
1558
1559   DEBUG_ASSERT (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1560
1561   /* Build sifted state_log[str_idx].  It has the nodes which can epsilon
1562      transit to the last_node and the last_node itself.  */
1563   err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1564   if (__glibc_unlikely (err != REG_NOERROR))
1565     return err;
1566   err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1567   if (__glibc_unlikely (err != REG_NOERROR))
1568     goto free_return;
1569
1570   /* Then check each states in the state_log.  */
1571   while (str_idx > 0)
1572     {
1573       /* Update counters.  */
1574       null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1575       if (null_cnt > mctx->max_mb_elem_len)
1576         {
1577           memset (sctx->sifted_states, '\0',
1578                   sizeof (re_dfastate_t *) * str_idx);
1579           re_node_set_free (&cur_dest);
1580           return REG_NOERROR;
1581         }
1582       re_node_set_empty (&cur_dest);
1583       --str_idx;
1584
1585       if (mctx->state_log[str_idx])
1586         {
1587           err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1588           if (__glibc_unlikely (err != REG_NOERROR))
1589             goto free_return;
1590         }
1591
1592       /* Add all the nodes which satisfy the following conditions:
1593          - It can epsilon transit to a node in CUR_DEST.
1594          - It is in CUR_SRC.
1595          And update state_log.  */
1596       err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1597       if (__glibc_unlikely (err != REG_NOERROR))
1598         goto free_return;
1599     }
1600   err = REG_NOERROR;
1601  free_return:
1602   re_node_set_free (&cur_dest);
1603   return err;
1604 }
1605
1606 static reg_errcode_t
1607 __attribute_warn_unused_result__
1608 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1609                      Idx str_idx, re_node_set *cur_dest)
1610 {
1611   const re_dfa_t *const dfa = mctx->dfa;
1612   const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1613   Idx i;
1614
1615   /* Then build the next sifted state.
1616      We build the next sifted state on 'cur_dest', and update
1617      'sifted_states[str_idx]' with 'cur_dest'.
1618      Note:
1619      'cur_dest' is the sifted state from 'state_log[str_idx + 1]'.
1620      'cur_src' points the node_set of the old 'state_log[str_idx]'
1621      (with the epsilon nodes pre-filtered out).  */
1622   for (i = 0; i < cur_src->nelem; i++)
1623     {
1624       Idx prev_node = cur_src->elems[i];
1625       int naccepted = 0;
1626       bool ok;
1627       DEBUG_ASSERT (!IS_EPSILON_NODE (dfa->nodes[prev_node].type));
1628
1629 #ifdef RE_ENABLE_I18N
1630       /* If the node may accept "multi byte".  */
1631       if (dfa->nodes[prev_node].accept_mb)
1632         naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1633                                          str_idx, sctx->last_str_idx);
1634 #endif /* RE_ENABLE_I18N */
1635
1636       /* We don't check backreferences here.
1637          See update_cur_sifted_state().  */
1638       if (!naccepted
1639           && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1640           && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1641                                   dfa->nexts[prev_node]))
1642         naccepted = 1;
1643
1644       if (naccepted == 0)
1645         continue;
1646
1647       if (sctx->limits.nelem)
1648         {
1649           Idx to_idx = str_idx + naccepted;
1650           if (check_dst_limits (mctx, &sctx->limits,
1651                                 dfa->nexts[prev_node], to_idx,
1652                                 prev_node, str_idx))
1653             continue;
1654         }
1655       ok = re_node_set_insert (cur_dest, prev_node);
1656       if (__glibc_unlikely (! ok))
1657         return REG_ESPACE;
1658     }
1659
1660   return REG_NOERROR;
1661 }
1662
1663 /* Helper functions.  */
1664
1665 static reg_errcode_t
1666 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1667 {
1668   Idx top = mctx->state_log_top;
1669
1670   if ((next_state_log_idx >= mctx->input.bufs_len
1671        && mctx->input.bufs_len < mctx->input.len)
1672       || (next_state_log_idx >= mctx->input.valid_len
1673           && mctx->input.valid_len < mctx->input.len))
1674     {
1675       reg_errcode_t err;
1676       err = extend_buffers (mctx, next_state_log_idx + 1);
1677       if (__glibc_unlikely (err != REG_NOERROR))
1678         return err;
1679     }
1680
1681   if (top < next_state_log_idx)
1682     {
1683       memset (mctx->state_log + top + 1, '\0',
1684               sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1685       mctx->state_log_top = next_state_log_idx;
1686     }
1687   return REG_NOERROR;
1688 }
1689
1690 static reg_errcode_t
1691 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1692                    re_dfastate_t **src, Idx num)
1693 {
1694   Idx st_idx;
1695   reg_errcode_t err;
1696   for (st_idx = 0; st_idx < num; ++st_idx)
1697     {
1698       if (dst[st_idx] == NULL)
1699         dst[st_idx] = src[st_idx];
1700       else if (src[st_idx] != NULL)
1701         {
1702           re_node_set merged_set;
1703           err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1704                                         &src[st_idx]->nodes);
1705           if (__glibc_unlikely (err != REG_NOERROR))
1706             return err;
1707           dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1708           re_node_set_free (&merged_set);
1709           if (__glibc_unlikely (err != REG_NOERROR))
1710             return err;
1711         }
1712     }
1713   return REG_NOERROR;
1714 }
1715
1716 static reg_errcode_t
1717 update_cur_sifted_state (const re_match_context_t *mctx,
1718                          re_sift_context_t *sctx, Idx str_idx,
1719                          re_node_set *dest_nodes)
1720 {
1721   const re_dfa_t *const dfa = mctx->dfa;
1722   reg_errcode_t err = REG_NOERROR;
1723   const re_node_set *candidates;
1724   candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1725                 : &mctx->state_log[str_idx]->nodes);
1726
1727   if (dest_nodes->nelem == 0)
1728     sctx->sifted_states[str_idx] = NULL;
1729   else
1730     {
1731       if (candidates)
1732         {
1733           /* At first, add the nodes which can epsilon transit to a node in
1734              DEST_NODE.  */
1735           err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1736           if (__glibc_unlikely (err != REG_NOERROR))
1737             return err;
1738
1739           /* Then, check the limitations in the current sift_context.  */
1740           if (sctx->limits.nelem)
1741             {
1742               err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1743                                          mctx->bkref_ents, str_idx);
1744               if (__glibc_unlikely (err != REG_NOERROR))
1745                 return err;
1746             }
1747         }
1748
1749       sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1750       if (__glibc_unlikely (err != REG_NOERROR))
1751         return err;
1752     }
1753
1754   if (candidates && mctx->state_log[str_idx]->has_backref)
1755     {
1756       err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1757       if (__glibc_unlikely (err != REG_NOERROR))
1758         return err;
1759     }
1760   return REG_NOERROR;
1761 }
1762
1763 static reg_errcode_t
1764 __attribute_warn_unused_result__
1765 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1766                        const re_node_set *candidates)
1767 {
1768   reg_errcode_t err = REG_NOERROR;
1769   Idx i;
1770
1771   re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1772   if (__glibc_unlikely (err != REG_NOERROR))
1773     return err;
1774
1775   if (!state->inveclosure.alloc)
1776     {
1777       err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1778       if (__glibc_unlikely (err != REG_NOERROR))
1779         return REG_ESPACE;
1780       for (i = 0; i < dest_nodes->nelem; i++)
1781         {
1782           err = re_node_set_merge (&state->inveclosure,
1783                                    dfa->inveclosures + dest_nodes->elems[i]);
1784           if (__glibc_unlikely (err != REG_NOERROR))
1785             return REG_ESPACE;
1786         }
1787     }
1788   return re_node_set_add_intersect (dest_nodes, candidates,
1789                                     &state->inveclosure);
1790 }
1791
1792 static reg_errcode_t
1793 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1794                        const re_node_set *candidates)
1795 {
1796     Idx ecl_idx;
1797     reg_errcode_t err;
1798     re_node_set *inv_eclosure = dfa->inveclosures + node;
1799     re_node_set except_nodes;
1800     re_node_set_init_empty (&except_nodes);
1801     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1802       {
1803         Idx cur_node = inv_eclosure->elems[ecl_idx];
1804         if (cur_node == node)
1805           continue;
1806         if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1807           {
1808             Idx edst1 = dfa->edests[cur_node].elems[0];
1809             Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1810                          ? dfa->edests[cur_node].elems[1] : -1);
1811             if ((!re_node_set_contains (inv_eclosure, edst1)
1812                  && re_node_set_contains (dest_nodes, edst1))
1813                 || (edst2 > 0
1814                     && !re_node_set_contains (inv_eclosure, edst2)
1815                     && re_node_set_contains (dest_nodes, edst2)))
1816               {
1817                 err = re_node_set_add_intersect (&except_nodes, candidates,
1818                                                  dfa->inveclosures + cur_node);
1819                 if (__glibc_unlikely (err != REG_NOERROR))
1820                   {
1821                     re_node_set_free (&except_nodes);
1822                     return err;
1823                   }
1824               }
1825           }
1826       }
1827     for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1828       {
1829         Idx cur_node = inv_eclosure->elems[ecl_idx];
1830         if (!re_node_set_contains (&except_nodes, cur_node))
1831           {
1832             Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1833             re_node_set_remove_at (dest_nodes, idx);
1834           }
1835       }
1836     re_node_set_free (&except_nodes);
1837     return REG_NOERROR;
1838 }
1839
1840 static bool
1841 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1842                   Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1843 {
1844   const re_dfa_t *const dfa = mctx->dfa;
1845   Idx lim_idx, src_pos, dst_pos;
1846
1847   Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1848   Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1849   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1850     {
1851       Idx subexp_idx;
1852       struct re_backref_cache_entry *ent;
1853       ent = mctx->bkref_ents + limits->elems[lim_idx];
1854       subexp_idx = dfa->nodes[ent->node].opr.idx;
1855
1856       dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1857                                            subexp_idx, dst_node, dst_idx,
1858                                            dst_bkref_idx);
1859       src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1860                                            subexp_idx, src_node, src_idx,
1861                                            src_bkref_idx);
1862
1863       /* In case of:
1864          <src> <dst> ( <subexp> )
1865          ( <subexp> ) <src> <dst>
1866          ( <subexp1> <src> <subexp2> <dst> <subexp3> )  */
1867       if (src_pos == dst_pos)
1868         continue; /* This is unrelated limitation.  */
1869       else
1870         return true;
1871     }
1872   return false;
1873 }
1874
1875 static int
1876 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1877                              Idx subexp_idx, Idx from_node, Idx bkref_idx)
1878 {
1879   const re_dfa_t *const dfa = mctx->dfa;
1880   const re_node_set *eclosures = dfa->eclosures + from_node;
1881   Idx node_idx;
1882
1883   /* Else, we are on the boundary: examine the nodes on the epsilon
1884      closure.  */
1885   for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1886     {
1887       Idx node = eclosures->elems[node_idx];
1888       switch (dfa->nodes[node].type)
1889         {
1890         case OP_BACK_REF:
1891           if (bkref_idx != -1)
1892             {
1893               struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1894               do
1895                 {
1896                   Idx dst;
1897                   int cpos;
1898
1899                   if (ent->node != node)
1900                     continue;
1901
1902                   if (subexp_idx < BITSET_WORD_BITS
1903                       && !(ent->eps_reachable_subexps_map
1904                            & ((bitset_word_t) 1 << subexp_idx)))
1905                     continue;
1906
1907                   /* Recurse trying to reach the OP_OPEN_SUBEXP and
1908                      OP_CLOSE_SUBEXP cases below.  But, if the
1909                      destination node is the same node as the source
1910                      node, don't recurse because it would cause an
1911                      infinite loop: a regex that exhibits this behavior
1912                      is ()\1*\1*  */
1913                   dst = dfa->edests[node].elems[0];
1914                   if (dst == from_node)
1915                     {
1916                       if (boundaries & 1)
1917                         return -1;
1918                       else /* if (boundaries & 2) */
1919                         return 0;
1920                     }
1921
1922                   cpos =
1923                     check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
1924                                                  dst, bkref_idx);
1925                   if (cpos == -1 /* && (boundaries & 1) */)
1926                     return -1;
1927                   if (cpos == 0 && (boundaries & 2))
1928                     return 0;
1929
1930                   if (subexp_idx < BITSET_WORD_BITS)
1931                     ent->eps_reachable_subexps_map
1932                       &= ~((bitset_word_t) 1 << subexp_idx);
1933                 }
1934               while (ent++->more);
1935             }
1936           break;
1937
1938         case OP_OPEN_SUBEXP:
1939           if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
1940             return -1;
1941           break;
1942
1943         case OP_CLOSE_SUBEXP:
1944           if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
1945             return 0;
1946           break;
1947
1948         default:
1949             break;
1950         }
1951     }
1952
1953   return (boundaries & 2) ? 1 : 0;
1954 }
1955
1956 static int
1957 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
1958                            Idx subexp_idx, Idx from_node, Idx str_idx,
1959                            Idx bkref_idx)
1960 {
1961   struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
1962   int boundaries;
1963
1964   /* If we are outside the range of the subexpression, return -1 or 1.  */
1965   if (str_idx < lim->subexp_from)
1966     return -1;
1967
1968   if (lim->subexp_to < str_idx)
1969     return 1;
1970
1971   /* If we are within the subexpression, return 0.  */
1972   boundaries = (str_idx == lim->subexp_from);
1973   boundaries |= (str_idx == lim->subexp_to) << 1;
1974   if (boundaries == 0)
1975     return 0;
1976
1977   /* Else, examine epsilon closure.  */
1978   return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
1979                                       from_node, bkref_idx);
1980 }
1981
1982 /* Check the limitations of sub expressions LIMITS, and remove the nodes
1983    which are against limitations from DEST_NODES. */
1984
1985 static reg_errcode_t
1986 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
1987                      const re_node_set *candidates, re_node_set *limits,
1988                      struct re_backref_cache_entry *bkref_ents, Idx str_idx)
1989 {
1990   reg_errcode_t err;
1991   Idx node_idx, lim_idx;
1992
1993   for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1994     {
1995       Idx subexp_idx;
1996       struct re_backref_cache_entry *ent;
1997       ent = bkref_ents + limits->elems[lim_idx];
1998
1999       if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2000         continue; /* This is unrelated limitation.  */
2001
2002       subexp_idx = dfa->nodes[ent->node].opr.idx;
2003       if (ent->subexp_to == str_idx)
2004         {
2005           Idx ops_node = -1;
2006           Idx cls_node = -1;
2007           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2008             {
2009               Idx node = dest_nodes->elems[node_idx];
2010               re_token_type_t type = dfa->nodes[node].type;
2011               if (type == OP_OPEN_SUBEXP
2012                   && subexp_idx == dfa->nodes[node].opr.idx)
2013                 ops_node = node;
2014               else if (type == OP_CLOSE_SUBEXP
2015                        && subexp_idx == dfa->nodes[node].opr.idx)
2016                 cls_node = node;
2017             }
2018
2019           /* Check the limitation of the open subexpression.  */
2020           /* Note that (ent->subexp_to = str_idx != ent->subexp_from).  */
2021           if (ops_node >= 0)
2022             {
2023               err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2024                                            candidates);
2025               if (__glibc_unlikely (err != REG_NOERROR))
2026                 return err;
2027             }
2028
2029           /* Check the limitation of the close subexpression.  */
2030           if (cls_node >= 0)
2031             for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2032               {
2033                 Idx node = dest_nodes->elems[node_idx];
2034                 if (!re_node_set_contains (dfa->inveclosures + node,
2035                                            cls_node)
2036                     && !re_node_set_contains (dfa->eclosures + node,
2037                                               cls_node))
2038                   {
2039                     /* It is against this limitation.
2040                        Remove it form the current sifted state.  */
2041                     err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2042                                                  candidates);
2043                     if (__glibc_unlikely (err != REG_NOERROR))
2044                       return err;
2045                     --node_idx;
2046                   }
2047               }
2048         }
2049       else /* (ent->subexp_to != str_idx)  */
2050         {
2051           for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2052             {
2053               Idx node = dest_nodes->elems[node_idx];
2054               re_token_type_t type = dfa->nodes[node].type;
2055               if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2056                 {
2057                   if (subexp_idx != dfa->nodes[node].opr.idx)
2058                     continue;
2059                   /* It is against this limitation.
2060                      Remove it form the current sifted state.  */
2061                   err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2062                                                candidates);
2063                   if (__glibc_unlikely (err != REG_NOERROR))
2064                     return err;
2065                 }
2066             }
2067         }
2068     }
2069   return REG_NOERROR;
2070 }
2071
2072 static reg_errcode_t
2073 __attribute_warn_unused_result__
2074 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2075                    Idx str_idx, const re_node_set *candidates)
2076 {
2077   const re_dfa_t *const dfa = mctx->dfa;
2078   reg_errcode_t err;
2079   Idx node_idx, node;
2080   re_sift_context_t local_sctx;
2081   Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2082
2083   if (first_idx == -1)
2084     return REG_NOERROR;
2085
2086   local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized.  */
2087
2088   for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2089     {
2090       Idx enabled_idx;
2091       re_token_type_t type;
2092       struct re_backref_cache_entry *entry;
2093       node = candidates->elems[node_idx];
2094       type = dfa->nodes[node].type;
2095       /* Avoid infinite loop for the REs like "()\1+".  */
2096       if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2097         continue;
2098       if (type != OP_BACK_REF)
2099         continue;
2100
2101       entry = mctx->bkref_ents + first_idx;
2102       enabled_idx = first_idx;
2103       do
2104         {
2105           Idx subexp_len;
2106           Idx to_idx;
2107           Idx dst_node;
2108           bool ok;
2109           re_dfastate_t *cur_state;
2110
2111           if (entry->node != node)
2112             continue;
2113           subexp_len = entry->subexp_to - entry->subexp_from;
2114           to_idx = str_idx + subexp_len;
2115           dst_node = (subexp_len ? dfa->nexts[node]
2116                       : dfa->edests[node].elems[0]);
2117
2118           if (to_idx > sctx->last_str_idx
2119               || sctx->sifted_states[to_idx] == NULL
2120               || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2121               || check_dst_limits (mctx, &sctx->limits, node,
2122                                    str_idx, dst_node, to_idx))
2123             continue;
2124
2125           if (local_sctx.sifted_states == NULL)
2126             {
2127               local_sctx = *sctx;
2128               err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2129               if (__glibc_unlikely (err != REG_NOERROR))
2130                 goto free_return;
2131             }
2132           local_sctx.last_node = node;
2133           local_sctx.last_str_idx = str_idx;
2134           ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2135           if (__glibc_unlikely (! ok))
2136             {
2137               err = REG_ESPACE;
2138               goto free_return;
2139             }
2140           cur_state = local_sctx.sifted_states[str_idx];
2141           err = sift_states_backward (mctx, &local_sctx);
2142           if (__glibc_unlikely (err != REG_NOERROR))
2143             goto free_return;
2144           if (sctx->limited_states != NULL)
2145             {
2146               err = merge_state_array (dfa, sctx->limited_states,
2147                                        local_sctx.sifted_states,
2148                                        str_idx + 1);
2149               if (__glibc_unlikely (err != REG_NOERROR))
2150                 goto free_return;
2151             }
2152           local_sctx.sifted_states[str_idx] = cur_state;
2153           re_node_set_remove (&local_sctx.limits, enabled_idx);
2154
2155           /* mctx->bkref_ents may have changed, reload the pointer.  */
2156           entry = mctx->bkref_ents + enabled_idx;
2157         }
2158       while (enabled_idx++, entry++->more);
2159     }
2160   err = REG_NOERROR;
2161  free_return:
2162   if (local_sctx.sifted_states != NULL)
2163     {
2164       re_node_set_free (&local_sctx.limits);
2165     }
2166
2167   return err;
2168 }
2169
2170
2171 #ifdef RE_ENABLE_I18N
2172 static int
2173 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2174                      Idx node_idx, Idx str_idx, Idx max_str_idx)
2175 {
2176   const re_dfa_t *const dfa = mctx->dfa;
2177   int naccepted;
2178   /* Check the node can accept "multi byte".  */
2179   naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2180   if (naccepted > 0 && str_idx + naccepted <= max_str_idx
2181       && !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2182                                dfa->nexts[node_idx]))
2183     /* The node can't accept the "multi byte", or the
2184        destination was already thrown away, then the node
2185        couldn't accept the current input "multi byte".   */
2186     naccepted = 0;
2187   /* Otherwise, it is sure that the node could accept
2188      'naccepted' bytes input.  */
2189   return naccepted;
2190 }
2191 #endif /* RE_ENABLE_I18N */
2192
2193 \f
2194 /* Functions for state transition.  */
2195
2196 /* Return the next state to which the current state STATE will transit by
2197    accepting the current input byte, and update STATE_LOG if necessary.
2198    If STATE can accept a multibyte char/collating element/back reference
2199    update the destination of STATE_LOG.  */
2200
2201 static re_dfastate_t *
2202 __attribute_warn_unused_result__
2203 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2204                re_dfastate_t *state)
2205 {
2206   re_dfastate_t **trtable;
2207   unsigned char ch;
2208
2209 #ifdef RE_ENABLE_I18N
2210   /* If the current state can accept multibyte.  */
2211   if (__glibc_unlikely (state->accept_mb))
2212     {
2213       *err = transit_state_mb (mctx, state);
2214       if (__glibc_unlikely (*err != REG_NOERROR))
2215         return NULL;
2216     }
2217 #endif /* RE_ENABLE_I18N */
2218
2219   /* Then decide the next state with the single byte.  */
2220 #if 0
2221   if (0)
2222     /* don't use transition table  */
2223     return transit_state_sb (err, mctx, state);
2224 #endif
2225
2226   /* Use transition table  */
2227   ch = re_string_fetch_byte (&mctx->input);
2228   for (;;)
2229     {
2230       trtable = state->trtable;
2231       if (__glibc_likely (trtable != NULL))
2232         return trtable[ch];
2233
2234       trtable = state->word_trtable;
2235       if (__glibc_likely (trtable != NULL))
2236         {
2237           unsigned int context;
2238           context
2239             = re_string_context_at (&mctx->input,
2240                                     re_string_cur_idx (&mctx->input) - 1,
2241                                     mctx->eflags);
2242           if (IS_WORD_CONTEXT (context))
2243             return trtable[ch + SBC_MAX];
2244           else
2245             return trtable[ch];
2246         }
2247
2248       if (!build_trtable (mctx->dfa, state))
2249         {
2250           *err = REG_ESPACE;
2251           return NULL;
2252         }
2253
2254       /* Retry, we now have a transition table.  */
2255     }
2256 }
2257
2258 /* Update the state_log if we need */
2259 static re_dfastate_t *
2260 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2261                       re_dfastate_t *next_state)
2262 {
2263   const re_dfa_t *const dfa = mctx->dfa;
2264   Idx cur_idx = re_string_cur_idx (&mctx->input);
2265
2266   if (cur_idx > mctx->state_log_top)
2267     {
2268       mctx->state_log[cur_idx] = next_state;
2269       mctx->state_log_top = cur_idx;
2270     }
2271   else if (mctx->state_log[cur_idx] == 0)
2272     {
2273       mctx->state_log[cur_idx] = next_state;
2274     }
2275   else
2276     {
2277       re_dfastate_t *pstate;
2278       unsigned int context;
2279       re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2280       /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2281          the destination of a multibyte char/collating element/
2282          back reference.  Then the next state is the union set of
2283          these destinations and the results of the transition table.  */
2284       pstate = mctx->state_log[cur_idx];
2285       log_nodes = pstate->entrance_nodes;
2286       if (next_state != NULL)
2287         {
2288           table_nodes = next_state->entrance_nodes;
2289           *err = re_node_set_init_union (&next_nodes, table_nodes,
2290                                              log_nodes);
2291           if (__glibc_unlikely (*err != REG_NOERROR))
2292             return NULL;
2293         }
2294       else
2295         next_nodes = *log_nodes;
2296       /* Note: We already add the nodes of the initial state,
2297          then we don't need to add them here.  */
2298
2299       context = re_string_context_at (&mctx->input,
2300                                       re_string_cur_idx (&mctx->input) - 1,
2301                                       mctx->eflags);
2302       next_state = mctx->state_log[cur_idx]
2303         = re_acquire_state_context (err, dfa, &next_nodes, context);
2304       /* We don't need to check errors here, since the return value of
2305          this function is next_state and ERR is already set.  */
2306
2307       if (table_nodes != NULL)
2308         re_node_set_free (&next_nodes);
2309     }
2310
2311   if (__glibc_unlikely (dfa->nbackref) && next_state != NULL)
2312     {
2313       /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2314          later.  We must check them here, since the back references in the
2315          next state might use them.  */
2316       *err = check_subexp_matching_top (mctx, &next_state->nodes,
2317                                         cur_idx);
2318       if (__glibc_unlikely (*err != REG_NOERROR))
2319         return NULL;
2320
2321       /* If the next state has back references.  */
2322       if (next_state->has_backref)
2323         {
2324           *err = transit_state_bkref (mctx, &next_state->nodes);
2325           if (__glibc_unlikely (*err != REG_NOERROR))
2326             return NULL;
2327           next_state = mctx->state_log[cur_idx];
2328         }
2329     }
2330
2331   return next_state;
2332 }
2333
2334 /* Skip bytes in the input that correspond to part of a
2335    multi-byte match, then look in the log for a state
2336    from which to restart matching.  */
2337 static re_dfastate_t *
2338 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2339 {
2340   re_dfastate_t *cur_state;
2341   do
2342     {
2343       Idx max = mctx->state_log_top;
2344       Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2345
2346       do
2347         {
2348           if (++cur_str_idx > max)
2349             return NULL;
2350           re_string_skip_bytes (&mctx->input, 1);
2351         }
2352       while (mctx->state_log[cur_str_idx] == NULL);
2353
2354       cur_state = merge_state_with_log (err, mctx, NULL);
2355     }
2356   while (*err == REG_NOERROR && cur_state == NULL);
2357   return cur_state;
2358 }
2359
2360 /* Helper functions for transit_state.  */
2361
2362 /* From the node set CUR_NODES, pick up the nodes whose types are
2363    OP_OPEN_SUBEXP and which have corresponding back references in the regular
2364    expression. And register them to use them later for evaluating the
2365    corresponding back references.  */
2366
2367 static reg_errcode_t
2368 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2369                            Idx str_idx)
2370 {
2371   const re_dfa_t *const dfa = mctx->dfa;
2372   Idx node_idx;
2373   reg_errcode_t err;
2374
2375   /* TODO: This isn't efficient.
2376            Because there might be more than one nodes whose types are
2377            OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2378            nodes.
2379            E.g. RE: (a){2}  */
2380   for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2381     {
2382       Idx node = cur_nodes->elems[node_idx];
2383       if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2384           && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2385           && (dfa->used_bkref_map
2386               & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2387         {
2388           err = match_ctx_add_subtop (mctx, node, str_idx);
2389           if (__glibc_unlikely (err != REG_NOERROR))
2390             return err;
2391         }
2392     }
2393   return REG_NOERROR;
2394 }
2395
2396 #if 0
2397 /* Return the next state to which the current state STATE will transit by
2398    accepting the current input byte.  */
2399
2400 static re_dfastate_t *
2401 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2402                   re_dfastate_t *state)
2403 {
2404   const re_dfa_t *const dfa = mctx->dfa;
2405   re_node_set next_nodes;
2406   re_dfastate_t *next_state;
2407   Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2408   unsigned int context;
2409
2410   *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2411   if (__glibc_unlikely (*err != REG_NOERROR))
2412     return NULL;
2413   for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2414     {
2415       Idx cur_node = state->nodes.elems[node_cnt];
2416       if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2417         {
2418           *err = re_node_set_merge (&next_nodes,
2419                                     dfa->eclosures + dfa->nexts[cur_node]);
2420           if (__glibc_unlikely (*err != REG_NOERROR))
2421             {
2422               re_node_set_free (&next_nodes);
2423               return NULL;
2424             }
2425         }
2426     }
2427   context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2428   next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2429   /* We don't need to check errors here, since the return value of
2430      this function is next_state and ERR is already set.  */
2431
2432   re_node_set_free (&next_nodes);
2433   re_string_skip_bytes (&mctx->input, 1);
2434   return next_state;
2435 }
2436 #endif
2437
2438 #ifdef RE_ENABLE_I18N
2439 static reg_errcode_t
2440 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2441 {
2442   const re_dfa_t *const dfa = mctx->dfa;
2443   reg_errcode_t err;
2444   Idx i;
2445
2446   for (i = 0; i < pstate->nodes.nelem; ++i)
2447     {
2448       re_node_set dest_nodes, *new_nodes;
2449       Idx cur_node_idx = pstate->nodes.elems[i];
2450       int naccepted;
2451       Idx dest_idx;
2452       unsigned int context;
2453       re_dfastate_t *dest_state;
2454
2455       if (!dfa->nodes[cur_node_idx].accept_mb)
2456         continue;
2457
2458       if (dfa->nodes[cur_node_idx].constraint)
2459         {
2460           context = re_string_context_at (&mctx->input,
2461                                           re_string_cur_idx (&mctx->input),
2462                                           mctx->eflags);
2463           if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2464                                            context))
2465             continue;
2466         }
2467
2468       /* How many bytes the node can accept?  */
2469       naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2470                                            re_string_cur_idx (&mctx->input));
2471       if (naccepted == 0)
2472         continue;
2473
2474       /* The node can accepts 'naccepted' bytes.  */
2475       dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2476       mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2477                                : mctx->max_mb_elem_len);
2478       err = clean_state_log_if_needed (mctx, dest_idx);
2479       if (__glibc_unlikely (err != REG_NOERROR))
2480         return err;
2481       DEBUG_ASSERT (dfa->nexts[cur_node_idx] != -1);
2482       new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2483
2484       dest_state = mctx->state_log[dest_idx];
2485       if (dest_state == NULL)
2486         dest_nodes = *new_nodes;
2487       else
2488         {
2489           err = re_node_set_init_union (&dest_nodes,
2490                                         dest_state->entrance_nodes, new_nodes);
2491           if (__glibc_unlikely (err != REG_NOERROR))
2492             return err;
2493         }
2494       context = re_string_context_at (&mctx->input, dest_idx - 1,
2495                                       mctx->eflags);
2496       mctx->state_log[dest_idx]
2497         = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2498       if (dest_state != NULL)
2499         re_node_set_free (&dest_nodes);
2500       if (__glibc_unlikely (mctx->state_log[dest_idx] == NULL
2501                             && err != REG_NOERROR))
2502         return err;
2503     }
2504   return REG_NOERROR;
2505 }
2506 #endif /* RE_ENABLE_I18N */
2507
2508 static reg_errcode_t
2509 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2510 {
2511   const re_dfa_t *const dfa = mctx->dfa;
2512   reg_errcode_t err;
2513   Idx i;
2514   Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2515
2516   for (i = 0; i < nodes->nelem; ++i)
2517     {
2518       Idx dest_str_idx, prev_nelem, bkc_idx;
2519       Idx node_idx = nodes->elems[i];
2520       unsigned int context;
2521       const re_token_t *node = dfa->nodes + node_idx;
2522       re_node_set *new_dest_nodes;
2523
2524       /* Check whether 'node' is a backreference or not.  */
2525       if (node->type != OP_BACK_REF)
2526         continue;
2527
2528       if (node->constraint)
2529         {
2530           context = re_string_context_at (&mctx->input, cur_str_idx,
2531                                           mctx->eflags);
2532           if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2533             continue;
2534         }
2535
2536       /* 'node' is a backreference.
2537          Check the substring which the substring matched.  */
2538       bkc_idx = mctx->nbkref_ents;
2539       err = get_subexp (mctx, node_idx, cur_str_idx);
2540       if (__glibc_unlikely (err != REG_NOERROR))
2541         goto free_return;
2542
2543       /* And add the epsilon closures (which is 'new_dest_nodes') of
2544          the backreference to appropriate state_log.  */
2545       DEBUG_ASSERT (dfa->nexts[node_idx] != -1);
2546       for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2547         {
2548           Idx subexp_len;
2549           re_dfastate_t *dest_state;
2550           struct re_backref_cache_entry *bkref_ent;
2551           bkref_ent = mctx->bkref_ents + bkc_idx;
2552           if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2553             continue;
2554           subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2555           new_dest_nodes = (subexp_len == 0
2556                             ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2557                             : dfa->eclosures + dfa->nexts[node_idx]);
2558           dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2559                           - bkref_ent->subexp_from);
2560           context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2561                                           mctx->eflags);
2562           dest_state = mctx->state_log[dest_str_idx];
2563           prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2564                         : mctx->state_log[cur_str_idx]->nodes.nelem);
2565           /* Add 'new_dest_node' to state_log.  */
2566           if (dest_state == NULL)
2567             {
2568               mctx->state_log[dest_str_idx]
2569                 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2570                                             context);
2571               if (__glibc_unlikely (mctx->state_log[dest_str_idx] == NULL
2572                                     && err != REG_NOERROR))
2573                 goto free_return;
2574             }
2575           else
2576             {
2577               re_node_set dest_nodes;
2578               err = re_node_set_init_union (&dest_nodes,
2579                                             dest_state->entrance_nodes,
2580                                             new_dest_nodes);
2581               if (__glibc_unlikely (err != REG_NOERROR))
2582                 {
2583                   re_node_set_free (&dest_nodes);
2584                   goto free_return;
2585                 }
2586               mctx->state_log[dest_str_idx]
2587                 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2588               re_node_set_free (&dest_nodes);
2589               if (__glibc_unlikely (mctx->state_log[dest_str_idx] == NULL
2590                                     && err != REG_NOERROR))
2591                 goto free_return;
2592             }
2593           /* We need to check recursively if the backreference can epsilon
2594              transit.  */
2595           if (subexp_len == 0
2596               && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2597             {
2598               err = check_subexp_matching_top (mctx, new_dest_nodes,
2599                                                cur_str_idx);
2600               if (__glibc_unlikely (err != REG_NOERROR))
2601                 goto free_return;
2602               err = transit_state_bkref (mctx, new_dest_nodes);
2603               if (__glibc_unlikely (err != REG_NOERROR))
2604                 goto free_return;
2605             }
2606         }
2607     }
2608   err = REG_NOERROR;
2609  free_return:
2610   return err;
2611 }
2612
2613 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2614    at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2615    Note that we might collect inappropriate candidates here.
2616    However, the cost of checking them strictly here is too high, then we
2617    delay these checking for prune_impossible_nodes().  */
2618
2619 static reg_errcode_t
2620 __attribute_warn_unused_result__
2621 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2622 {
2623   const re_dfa_t *const dfa = mctx->dfa;
2624   Idx subexp_num, sub_top_idx;
2625   const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2626   /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX.  */
2627   Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2628   if (cache_idx != -1)
2629     {
2630       const struct re_backref_cache_entry *entry
2631         = mctx->bkref_ents + cache_idx;
2632       do
2633         if (entry->node == bkref_node)
2634           return REG_NOERROR; /* We already checked it.  */
2635       while (entry++->more);
2636     }
2637
2638   subexp_num = dfa->nodes[bkref_node].opr.idx;
2639
2640   /* For each sub expression  */
2641   for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2642     {
2643       reg_errcode_t err;
2644       re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2645       re_sub_match_last_t *sub_last;
2646       Idx sub_last_idx, sl_str, bkref_str_off;
2647
2648       if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2649         continue; /* It isn't related.  */
2650
2651       sl_str = sub_top->str_idx;
2652       bkref_str_off = bkref_str_idx;
2653       /* At first, check the last node of sub expressions we already
2654          evaluated.  */
2655       for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2656         {
2657           regoff_t sl_str_diff;
2658           sub_last = sub_top->lasts[sub_last_idx];
2659           sl_str_diff = sub_last->str_idx - sl_str;
2660           /* The matched string by the sub expression match with the substring
2661              at the back reference?  */
2662           if (sl_str_diff > 0)
2663             {
2664               if (__glibc_unlikely (bkref_str_off + sl_str_diff
2665                                     > mctx->input.valid_len))
2666                 {
2667                   /* Not enough chars for a successful match.  */
2668                   if (bkref_str_off + sl_str_diff > mctx->input.len)
2669                     break;
2670
2671                   err = clean_state_log_if_needed (mctx,
2672                                                    bkref_str_off
2673                                                    + sl_str_diff);
2674                   if (__glibc_unlikely (err != REG_NOERROR))
2675                     return err;
2676                   buf = (const char *) re_string_get_buffer (&mctx->input);
2677                 }
2678               if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2679                 /* We don't need to search this sub expression any more.  */
2680                 break;
2681             }
2682           bkref_str_off += sl_str_diff;
2683           sl_str += sl_str_diff;
2684           err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2685                                 bkref_str_idx);
2686
2687           /* Reload buf, since the preceding call might have reallocated
2688              the buffer.  */
2689           buf = (const char *) re_string_get_buffer (&mctx->input);
2690
2691           if (err == REG_NOMATCH)
2692             continue;
2693           if (__glibc_unlikely (err != REG_NOERROR))
2694             return err;
2695         }
2696
2697       if (sub_last_idx < sub_top->nlasts)
2698         continue;
2699       if (sub_last_idx > 0)
2700         ++sl_str;
2701       /* Then, search for the other last nodes of the sub expression.  */
2702       for (; sl_str <= bkref_str_idx; ++sl_str)
2703         {
2704           Idx cls_node;
2705           regoff_t sl_str_off;
2706           const re_node_set *nodes;
2707           sl_str_off = sl_str - sub_top->str_idx;
2708           /* The matched string by the sub expression match with the substring
2709              at the back reference?  */
2710           if (sl_str_off > 0)
2711             {
2712               if (__glibc_unlikely (bkref_str_off >= mctx->input.valid_len))
2713                 {
2714                   /* If we are at the end of the input, we cannot match.  */
2715                   if (bkref_str_off >= mctx->input.len)
2716                     break;
2717
2718                   err = extend_buffers (mctx, bkref_str_off + 1);
2719                   if (__glibc_unlikely (err != REG_NOERROR))
2720                     return err;
2721
2722                   buf = (const char *) re_string_get_buffer (&mctx->input);
2723                 }
2724               if (buf [bkref_str_off++] != buf[sl_str - 1])
2725                 break; /* We don't need to search this sub expression
2726                           any more.  */
2727             }
2728           if (mctx->state_log[sl_str] == NULL)
2729             continue;
2730           /* Does this state have a ')' of the sub expression?  */
2731           nodes = &mctx->state_log[sl_str]->nodes;
2732           cls_node = find_subexp_node (dfa, nodes, subexp_num,
2733                                        OP_CLOSE_SUBEXP);
2734           if (cls_node == -1)
2735             continue; /* No.  */
2736           if (sub_top->path == NULL)
2737             {
2738               sub_top->path = calloc (sizeof (state_array_t),
2739                                       sl_str - sub_top->str_idx + 1);
2740               if (sub_top->path == NULL)
2741                 return REG_ESPACE;
2742             }
2743           /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2744              in the current context?  */
2745           err = check_arrival (mctx, sub_top->path, sub_top->node,
2746                                sub_top->str_idx, cls_node, sl_str,
2747                                OP_CLOSE_SUBEXP);
2748           if (err == REG_NOMATCH)
2749               continue;
2750           if (__glibc_unlikely (err != REG_NOERROR))
2751               return err;
2752           sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2753           if (__glibc_unlikely (sub_last == NULL))
2754             return REG_ESPACE;
2755           err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2756                                 bkref_str_idx);
2757           buf = (const char *) re_string_get_buffer (&mctx->input);
2758           if (err == REG_NOMATCH)
2759             continue;
2760           if (__glibc_unlikely (err != REG_NOERROR))
2761             return err;
2762         }
2763     }
2764   return REG_NOERROR;
2765 }
2766
2767 /* Helper functions for get_subexp().  */
2768
2769 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2770    If it can arrive, register the sub expression expressed with SUB_TOP
2771    and SUB_LAST.  */
2772
2773 static reg_errcode_t
2774 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2775                 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2776 {
2777   reg_errcode_t err;
2778   Idx to_idx;
2779   /* Can the subexpression arrive the back reference?  */
2780   err = check_arrival (mctx, &sub_last->path, sub_last->node,
2781                        sub_last->str_idx, bkref_node, bkref_str,
2782                        OP_OPEN_SUBEXP);
2783   if (err != REG_NOERROR)
2784     return err;
2785   err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2786                              sub_last->str_idx);
2787   if (__glibc_unlikely (err != REG_NOERROR))
2788     return err;
2789   to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2790   return clean_state_log_if_needed (mctx, to_idx);
2791 }
2792
2793 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2794    Search '(' if FL_OPEN, or search ')' otherwise.
2795    TODO: This function isn't efficient...
2796          Because there might be more than one nodes whose types are
2797          OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2798          nodes.
2799          E.g. RE: (a){2}  */
2800
2801 static Idx
2802 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2803                   Idx subexp_idx, int type)
2804 {
2805   Idx cls_idx;
2806   for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2807     {
2808       Idx cls_node = nodes->elems[cls_idx];
2809       const re_token_t *node = dfa->nodes + cls_node;
2810       if (node->type == type
2811           && node->opr.idx == subexp_idx)
2812         return cls_node;
2813     }
2814   return -1;
2815 }
2816
2817 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2818    LAST_NODE at LAST_STR.  We record the path onto PATH since it will be
2819    heavily reused.
2820    Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise.  */
2821
2822 static reg_errcode_t
2823 __attribute_warn_unused_result__
2824 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2825                Idx top_str, Idx last_node, Idx last_str, int type)
2826 {
2827   const re_dfa_t *const dfa = mctx->dfa;
2828   reg_errcode_t err = REG_NOERROR;
2829   Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2830   re_dfastate_t *cur_state = NULL;
2831   re_node_set *cur_nodes, next_nodes;
2832   re_dfastate_t **backup_state_log;
2833   unsigned int context;
2834
2835   subexp_num = dfa->nodes[top_node].opr.idx;
2836   /* Extend the buffer if we need.  */
2837   if (__glibc_unlikely (path->alloc < last_str + mctx->max_mb_elem_len + 1))
2838     {
2839       re_dfastate_t **new_array;
2840       Idx old_alloc = path->alloc;
2841       Idx incr_alloc = last_str + mctx->max_mb_elem_len + 1;
2842       Idx new_alloc;
2843       if (__glibc_unlikely (IDX_MAX - old_alloc < incr_alloc))
2844         return REG_ESPACE;
2845       new_alloc = old_alloc + incr_alloc;
2846       if (__glibc_unlikely (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc))
2847         return REG_ESPACE;
2848       new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2849       if (__glibc_unlikely (new_array == NULL))
2850         return REG_ESPACE;
2851       path->array = new_array;
2852       path->alloc = new_alloc;
2853       memset (new_array + old_alloc, '\0',
2854               sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2855     }
2856
2857   str_idx = path->next_idx ? path->next_idx : top_str;
2858
2859   /* Temporary modify MCTX.  */
2860   backup_state_log = mctx->state_log;
2861   backup_cur_idx = mctx->input.cur_idx;
2862   mctx->state_log = path->array;
2863   mctx->input.cur_idx = str_idx;
2864
2865   /* Setup initial node set.  */
2866   context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2867   if (str_idx == top_str)
2868     {
2869       err = re_node_set_init_1 (&next_nodes, top_node);
2870       if (__glibc_unlikely (err != REG_NOERROR))
2871         return err;
2872       err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2873       if (__glibc_unlikely (err != REG_NOERROR))
2874         {
2875           re_node_set_free (&next_nodes);
2876           return err;
2877         }
2878     }
2879   else
2880     {
2881       cur_state = mctx->state_log[str_idx];
2882       if (cur_state && cur_state->has_backref)
2883         {
2884           err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2885           if (__glibc_unlikely (err != REG_NOERROR))
2886             return err;
2887         }
2888       else
2889         re_node_set_init_empty (&next_nodes);
2890     }
2891   if (str_idx == top_str || (cur_state && cur_state->has_backref))
2892     {
2893       if (next_nodes.nelem)
2894         {
2895           err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2896                                     subexp_num, type);
2897           if (__glibc_unlikely (err != REG_NOERROR))
2898             {
2899               re_node_set_free (&next_nodes);
2900               return err;
2901             }
2902         }
2903       cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2904       if (__glibc_unlikely (cur_state == NULL && err != REG_NOERROR))
2905         {
2906           re_node_set_free (&next_nodes);
2907           return err;
2908         }
2909       mctx->state_log[str_idx] = cur_state;
2910     }
2911
2912   for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
2913     {
2914       re_node_set_empty (&next_nodes);
2915       if (mctx->state_log[str_idx + 1])
2916         {
2917           err = re_node_set_merge (&next_nodes,
2918                                    &mctx->state_log[str_idx + 1]->nodes);
2919           if (__glibc_unlikely (err != REG_NOERROR))
2920             {
2921               re_node_set_free (&next_nodes);
2922               return err;
2923             }
2924         }
2925       if (cur_state)
2926         {
2927           err = check_arrival_add_next_nodes (mctx, str_idx,
2928                                               &cur_state->non_eps_nodes,
2929                                               &next_nodes);
2930           if (__glibc_unlikely (err != REG_NOERROR))
2931             {
2932               re_node_set_free (&next_nodes);
2933               return err;
2934             }
2935         }
2936       ++str_idx;
2937       if (next_nodes.nelem)
2938         {
2939           err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2940           if (__glibc_unlikely (err != REG_NOERROR))
2941             {
2942               re_node_set_free (&next_nodes);
2943               return err;
2944             }
2945           err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2946                                     subexp_num, type);
2947           if (__glibc_unlikely (err != REG_NOERROR))
2948             {
2949               re_node_set_free (&next_nodes);
2950               return err;
2951             }
2952         }
2953       context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2954       cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2955       if (__glibc_unlikely (cur_state == NULL && err != REG_NOERROR))
2956         {
2957           re_node_set_free (&next_nodes);
2958           return err;
2959         }
2960       mctx->state_log[str_idx] = cur_state;
2961       null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
2962     }
2963   re_node_set_free (&next_nodes);
2964   cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
2965                : &mctx->state_log[last_str]->nodes);
2966   path->next_idx = str_idx;
2967
2968   /* Fix MCTX.  */
2969   mctx->state_log = backup_state_log;
2970   mctx->input.cur_idx = backup_cur_idx;
2971
2972   /* Then check the current node set has the node LAST_NODE.  */
2973   if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
2974     return REG_NOERROR;
2975
2976   return REG_NOMATCH;
2977 }
2978
2979 /* Helper functions for check_arrival.  */
2980
2981 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
2982    to NEXT_NODES.
2983    TODO: This function is similar to the functions transit_state*(),
2984          however this function has many additional works.
2985          Can't we unify them?  */
2986
2987 static reg_errcode_t
2988 __attribute_warn_unused_result__
2989 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
2990                               re_node_set *cur_nodes, re_node_set *next_nodes)
2991 {
2992   const re_dfa_t *const dfa = mctx->dfa;
2993   bool ok;
2994   Idx cur_idx;
2995 #ifdef RE_ENABLE_I18N
2996   reg_errcode_t err = REG_NOERROR;
2997 #endif
2998   re_node_set union_set;
2999   re_node_set_init_empty (&union_set);
3000   for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3001     {
3002       int naccepted = 0;
3003       Idx cur_node = cur_nodes->elems[cur_idx];
3004       DEBUG_ASSERT (!IS_EPSILON_NODE (dfa->nodes[cur_node].type));
3005
3006 #ifdef RE_ENABLE_I18N
3007       /* If the node may accept "multi byte".  */
3008       if (dfa->nodes[cur_node].accept_mb)
3009         {
3010           naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3011                                                str_idx);
3012           if (naccepted > 1)
3013             {
3014               re_dfastate_t *dest_state;
3015               Idx next_node = dfa->nexts[cur_node];
3016               Idx next_idx = str_idx + naccepted;
3017               dest_state = mctx->state_log[next_idx];
3018               re_node_set_empty (&union_set);
3019               if (dest_state)
3020                 {
3021                   err = re_node_set_merge (&union_set, &dest_state->nodes);
3022                   if (__glibc_unlikely (err != REG_NOERROR))
3023                     {
3024                       re_node_set_free (&union_set);
3025                       return err;
3026                     }
3027                 }
3028               ok = re_node_set_insert (&union_set, next_node);
3029               if (__glibc_unlikely (! ok))
3030                 {
3031                   re_node_set_free (&union_set);
3032                   return REG_ESPACE;
3033                 }
3034               mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3035                                                             &union_set);
3036               if (__glibc_unlikely (mctx->state_log[next_idx] == NULL
3037                                     && err != REG_NOERROR))
3038                 {
3039                   re_node_set_free (&union_set);
3040                   return err;
3041                 }
3042             }
3043         }
3044 #endif /* RE_ENABLE_I18N */
3045       if (naccepted
3046           || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3047         {
3048           ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3049           if (__glibc_unlikely (! ok))
3050             {
3051               re_node_set_free (&union_set);
3052               return REG_ESPACE;
3053             }
3054         }
3055     }
3056   re_node_set_free (&union_set);
3057   return REG_NOERROR;
3058 }
3059
3060 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3061    CUR_NODES, however exclude the nodes which are:
3062     - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3063     - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3064 */
3065
3066 static reg_errcode_t
3067 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3068                           Idx ex_subexp, int type)
3069 {
3070   reg_errcode_t err;
3071   Idx idx, outside_node;
3072   re_node_set new_nodes;
3073   DEBUG_ASSERT (cur_nodes->nelem);
3074   err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3075   if (__glibc_unlikely (err != REG_NOERROR))
3076     return err;
3077   /* Create a new node set NEW_NODES with the nodes which are epsilon
3078      closures of the node in CUR_NODES.  */
3079
3080   for (idx = 0; idx < cur_nodes->nelem; ++idx)
3081     {
3082       Idx cur_node = cur_nodes->elems[idx];
3083       const re_node_set *eclosure = dfa->eclosures + cur_node;
3084       outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3085       if (outside_node == -1)
3086         {
3087           /* There are no problematic nodes, just merge them.  */
3088           err = re_node_set_merge (&new_nodes, eclosure);
3089           if (__glibc_unlikely (err != REG_NOERROR))
3090             {
3091               re_node_set_free (&new_nodes);
3092               return err;
3093             }
3094         }
3095       else
3096         {
3097           /* There are problematic nodes, re-calculate incrementally.  */
3098           err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3099                                               ex_subexp, type);
3100           if (__glibc_unlikely (err != REG_NOERROR))
3101             {
3102               re_node_set_free (&new_nodes);
3103               return err;
3104             }
3105         }
3106     }
3107   re_node_set_free (cur_nodes);
3108   *cur_nodes = new_nodes;
3109   return REG_NOERROR;
3110 }
3111
3112 /* Helper function for check_arrival_expand_ecl.
3113    Check incrementally the epsilon closure of TARGET, and if it isn't
3114    problematic append it to DST_NODES.  */
3115
3116 static reg_errcode_t
3117 __attribute_warn_unused_result__
3118 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3119                               Idx target, Idx ex_subexp, int type)
3120 {
3121   Idx cur_node;
3122   for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3123     {
3124       bool ok;
3125
3126       if (dfa->nodes[cur_node].type == type
3127           && dfa->nodes[cur_node].opr.idx == ex_subexp)
3128         {
3129           if (type == OP_CLOSE_SUBEXP)
3130             {
3131               ok = re_node_set_insert (dst_nodes, cur_node);
3132               if (__glibc_unlikely (! ok))
3133                 return REG_ESPACE;
3134             }
3135           break;
3136         }
3137       ok = re_node_set_insert (dst_nodes, cur_node);
3138       if (__glibc_unlikely (! ok))
3139         return REG_ESPACE;
3140       if (dfa->edests[cur_node].nelem == 0)
3141         break;
3142       if (dfa->edests[cur_node].nelem == 2)
3143         {
3144           reg_errcode_t err;
3145           err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3146                                               dfa->edests[cur_node].elems[1],
3147                                               ex_subexp, type);
3148           if (__glibc_unlikely (err != REG_NOERROR))
3149             return err;
3150         }
3151       cur_node = dfa->edests[cur_node].elems[0];
3152     }
3153   return REG_NOERROR;
3154 }
3155
3156
3157 /* For all the back references in the current state, calculate the
3158    destination of the back references by the appropriate entry
3159    in MCTX->BKREF_ENTS.  */
3160
3161 static reg_errcode_t
3162 __attribute_warn_unused_result__
3163 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3164                     Idx cur_str, Idx subexp_num, int type)
3165 {
3166   const re_dfa_t *const dfa = mctx->dfa;
3167   reg_errcode_t err;
3168   Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3169   struct re_backref_cache_entry *ent;
3170
3171   if (cache_idx_start == -1)
3172     return REG_NOERROR;
3173
3174  restart:
3175   ent = mctx->bkref_ents + cache_idx_start;
3176   do
3177     {
3178       Idx to_idx, next_node;
3179
3180       /* Is this entry ENT is appropriate?  */
3181       if (!re_node_set_contains (cur_nodes, ent->node))
3182         continue; /* No.  */
3183
3184       to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3185       /* Calculate the destination of the back reference, and append it
3186          to MCTX->STATE_LOG.  */
3187       if (to_idx == cur_str)
3188         {
3189           /* The backreference did epsilon transit, we must re-check all the
3190              node in the current state.  */
3191           re_node_set new_dests;
3192           reg_errcode_t err2, err3;
3193           next_node = dfa->edests[ent->node].elems[0];
3194           if (re_node_set_contains (cur_nodes, next_node))
3195             continue;
3196           err = re_node_set_init_1 (&new_dests, next_node);
3197           err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3198           err3 = re_node_set_merge (cur_nodes, &new_dests);
3199           re_node_set_free (&new_dests);
3200           if (__glibc_unlikely (err != REG_NOERROR || err2 != REG_NOERROR
3201                                 || err3 != REG_NOERROR))
3202             {
3203               err = (err != REG_NOERROR ? err
3204                      : (err2 != REG_NOERROR ? err2 : err3));
3205               return err;
3206             }
3207           /* TODO: It is still inefficient...  */
3208           goto restart;
3209         }
3210       else
3211         {
3212           re_node_set union_set;
3213           next_node = dfa->nexts[ent->node];
3214           if (mctx->state_log[to_idx])
3215             {
3216               bool ok;
3217               if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3218                                         next_node))
3219                 continue;
3220               err = re_node_set_init_copy (&union_set,
3221                                            &mctx->state_log[to_idx]->nodes);
3222               ok = re_node_set_insert (&union_set, next_node);
3223               if (__glibc_unlikely (err != REG_NOERROR || ! ok))
3224                 {
3225                   re_node_set_free (&union_set);
3226                   err = err != REG_NOERROR ? err : REG_ESPACE;
3227                   return err;
3228                 }
3229             }
3230           else
3231             {
3232               err = re_node_set_init_1 (&union_set, next_node);
3233               if (__glibc_unlikely (err != REG_NOERROR))
3234                 return err;
3235             }
3236           mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3237           re_node_set_free (&union_set);
3238           if (__glibc_unlikely (mctx->state_log[to_idx] == NULL
3239                                 && err != REG_NOERROR))
3240             return err;
3241         }
3242     }
3243   while (ent++->more);
3244   return REG_NOERROR;
3245 }
3246
3247 /* Build transition table for the state.
3248    Return true if successful.  */
3249
3250 static bool __attribute_noinline__
3251 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3252 {
3253   reg_errcode_t err;
3254   Idx i, j;
3255   int ch;
3256   bool need_word_trtable = false;
3257   bitset_word_t elem, mask;
3258   Idx ndests; /* Number of the destination states from 'state'.  */
3259   re_dfastate_t **trtable;
3260   re_dfastate_t *dest_states[SBC_MAX];
3261   re_dfastate_t *dest_states_word[SBC_MAX];
3262   re_dfastate_t *dest_states_nl[SBC_MAX];
3263   re_node_set follows;
3264   bitset_t acceptable;
3265
3266   /* We build DFA states which corresponds to the destination nodes
3267      from 'state'.  'dests_node[i]' represents the nodes which i-th
3268      destination state contains, and 'dests_ch[i]' represents the
3269      characters which i-th destination state accepts.  */
3270   re_node_set dests_node[SBC_MAX];
3271   bitset_t dests_ch[SBC_MAX];
3272
3273   /* Initialize transition table.  */
3274   state->word_trtable = state->trtable = NULL;
3275
3276   /* At first, group all nodes belonging to 'state' into several
3277      destinations.  */
3278   ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3279   if (__glibc_unlikely (ndests <= 0))
3280     {
3281       /* Return false in case of an error, true otherwise.  */
3282       if (ndests == 0)
3283         {
3284           state->trtable = (re_dfastate_t **)
3285             calloc (sizeof (re_dfastate_t *), SBC_MAX);
3286           if (__glibc_unlikely (state->trtable == NULL))
3287             return false;
3288           return true;
3289         }
3290       return false;
3291     }
3292
3293   err = re_node_set_alloc (&follows, ndests + 1);
3294   if (__glibc_unlikely (err != REG_NOERROR))
3295     {
3296     out_free:
3297       re_node_set_free (&follows);
3298       for (i = 0; i < ndests; ++i)
3299         re_node_set_free (dests_node + i);
3300       return false;
3301     }
3302
3303   bitset_empty (acceptable);
3304
3305   /* Then build the states for all destinations.  */
3306   for (i = 0; i < ndests; ++i)
3307     {
3308       Idx next_node;
3309       re_node_set_empty (&follows);
3310       /* Merge the follows of this destination states.  */
3311       for (j = 0; j < dests_node[i].nelem; ++j)
3312         {
3313           next_node = dfa->nexts[dests_node[i].elems[j]];
3314           if (next_node != -1)
3315             {
3316               err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3317               if (__glibc_unlikely (err != REG_NOERROR))
3318                 goto out_free;
3319             }
3320         }
3321       dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3322       if (__glibc_unlikely (dest_states[i] == NULL && err != REG_NOERROR))
3323         goto out_free;
3324       /* If the new state has context constraint,
3325          build appropriate states for these contexts.  */
3326       if (dest_states[i]->has_constraint)
3327         {
3328           dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3329                                                           CONTEXT_WORD);
3330           if (__glibc_unlikely (dest_states_word[i] == NULL
3331                                 && err != REG_NOERROR))
3332             goto out_free;
3333
3334           if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3335             need_word_trtable = true;
3336
3337           dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3338                                                         CONTEXT_NEWLINE);
3339           if (__glibc_unlikely (dest_states_nl[i] == NULL && err != REG_NOERROR))
3340             goto out_free;
3341         }
3342       else
3343         {
3344           dest_states_word[i] = dest_states[i];
3345           dest_states_nl[i] = dest_states[i];
3346         }
3347       bitset_merge (acceptable, dests_ch[i]);
3348     }
3349
3350   if (!__glibc_unlikely (need_word_trtable))
3351     {
3352       /* We don't care about whether the following character is a word
3353          character, or we are in a single-byte character set so we can
3354          discern by looking at the character code: allocate a
3355          256-entry transition table.  */
3356       trtable = state->trtable =
3357         (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3358       if (__glibc_unlikely (trtable == NULL))
3359         goto out_free;
3360
3361       /* For all characters ch...:  */
3362       for (i = 0; i < BITSET_WORDS; ++i)
3363         for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3364              elem;
3365              mask <<= 1, elem >>= 1, ++ch)
3366           if (__glibc_unlikely (elem & 1))
3367             {
3368               /* There must be exactly one destination which accepts
3369                  character ch.  See group_nodes_into_DFAstates.  */
3370               for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3371                 ;
3372
3373               /* j-th destination accepts the word character ch.  */
3374               if (dfa->word_char[i] & mask)
3375                 trtable[ch] = dest_states_word[j];
3376               else
3377                 trtable[ch] = dest_states[j];
3378             }
3379     }
3380   else
3381     {
3382       /* We care about whether the following character is a word
3383          character, and we are in a multi-byte character set: discern
3384          by looking at the character code: build two 256-entry
3385          transition tables, one starting at trtable[0] and one
3386          starting at trtable[SBC_MAX].  */
3387       trtable = state->word_trtable =
3388         (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3389       if (__glibc_unlikely (trtable == NULL))
3390         goto out_free;
3391
3392       /* For all characters ch...:  */
3393       for (i = 0; i < BITSET_WORDS; ++i)
3394         for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3395              elem;
3396              mask <<= 1, elem >>= 1, ++ch)
3397           if (__glibc_unlikely (elem & 1))
3398             {
3399               /* There must be exactly one destination which accepts
3400                  character ch.  See group_nodes_into_DFAstates.  */
3401               for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3402                 ;
3403
3404               /* j-th destination accepts the word character ch.  */
3405               trtable[ch] = dest_states[j];
3406               trtable[ch + SBC_MAX] = dest_states_word[j];
3407             }
3408     }
3409
3410   /* new line */
3411   if (bitset_contain (acceptable, NEWLINE_CHAR))
3412     {
3413       /* The current state accepts newline character.  */
3414       for (j = 0; j < ndests; ++j)
3415         if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3416           {
3417             /* k-th destination accepts newline character.  */
3418             trtable[NEWLINE_CHAR] = dest_states_nl[j];
3419             if (need_word_trtable)
3420               trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3421             /* There must be only one destination which accepts
3422                newline.  See group_nodes_into_DFAstates.  */
3423             break;
3424           }
3425     }
3426
3427   re_node_set_free (&follows);
3428   for (i = 0; i < ndests; ++i)
3429     re_node_set_free (dests_node + i);
3430   return true;
3431 }
3432
3433 /* Group all nodes belonging to STATE into several destinations.
3434    Then for all destinations, set the nodes belonging to the destination
3435    to DESTS_NODE[i] and set the characters accepted by the destination
3436    to DEST_CH[i].  This function return the number of destinations.  */
3437
3438 static Idx
3439 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3440                             re_node_set *dests_node, bitset_t *dests_ch)
3441 {
3442   reg_errcode_t err;
3443   bool ok;
3444   Idx i, j, k;
3445   Idx ndests; /* Number of the destinations from 'state'.  */
3446   bitset_t accepts; /* Characters a node can accept.  */
3447   const re_node_set *cur_nodes = &state->nodes;
3448   bitset_empty (accepts);
3449   ndests = 0;
3450
3451   /* For all the nodes belonging to 'state',  */
3452   for (i = 0; i < cur_nodes->nelem; ++i)
3453     {
3454       re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3455       re_token_type_t type = node->type;
3456       unsigned int constraint = node->constraint;
3457
3458       /* Enumerate all single byte character this node can accept.  */
3459       if (type == CHARACTER)
3460         bitset_set (accepts, node->opr.c);
3461       else if (type == SIMPLE_BRACKET)
3462         {
3463           bitset_merge (accepts, node->opr.sbcset);
3464         }
3465       else if (type == OP_PERIOD)
3466         {
3467 #ifdef RE_ENABLE_I18N
3468           if (dfa->mb_cur_max > 1)
3469             bitset_merge (accepts, dfa->sb_char);
3470           else
3471 #endif
3472             bitset_set_all (accepts);
3473           if (!(dfa->syntax & RE_DOT_NEWLINE))
3474             bitset_clear (accepts, '\n');
3475           if (dfa->syntax & RE_DOT_NOT_NULL)
3476             bitset_clear (accepts, '\0');
3477         }
3478 #ifdef RE_ENABLE_I18N
3479       else if (type == OP_UTF8_PERIOD)
3480         {
3481           if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3482             memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3483           else
3484             bitset_merge (accepts, utf8_sb_map);
3485           if (!(dfa->syntax & RE_DOT_NEWLINE))
3486             bitset_clear (accepts, '\n');
3487           if (dfa->syntax & RE_DOT_NOT_NULL)
3488             bitset_clear (accepts, '\0');
3489         }
3490 #endif
3491       else
3492         continue;
3493
3494       /* Check the 'accepts' and sift the characters which are not
3495          match it the context.  */
3496       if (constraint)
3497         {
3498           if (constraint & NEXT_NEWLINE_CONSTRAINT)
3499             {
3500               bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3501               bitset_empty (accepts);
3502               if (accepts_newline)
3503                 bitset_set (accepts, NEWLINE_CHAR);
3504               else
3505                 continue;
3506             }
3507           if (constraint & NEXT_ENDBUF_CONSTRAINT)
3508             {
3509               bitset_empty (accepts);
3510               continue;
3511             }
3512
3513           if (constraint & NEXT_WORD_CONSTRAINT)
3514             {
3515               bitset_word_t any_set = 0;
3516               if (type == CHARACTER && !node->word_char)
3517                 {
3518                   bitset_empty (accepts);
3519                   continue;
3520                 }
3521 #ifdef RE_ENABLE_I18N
3522               if (dfa->mb_cur_max > 1)
3523                 for (j = 0; j < BITSET_WORDS; ++j)
3524                   any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3525               else
3526 #endif
3527                 for (j = 0; j < BITSET_WORDS; ++j)
3528                   any_set |= (accepts[j] &= dfa->word_char[j]);
3529               if (!any_set)
3530                 continue;
3531             }
3532           if (constraint & NEXT_NOTWORD_CONSTRAINT)
3533             {
3534               bitset_word_t any_set = 0;
3535               if (type == CHARACTER && node->word_char)
3536                 {
3537                   bitset_empty (accepts);
3538                   continue;
3539                 }
3540 #ifdef RE_ENABLE_I18N
3541               if (dfa->mb_cur_max > 1)
3542                 for (j = 0; j < BITSET_WORDS; ++j)
3543                   any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3544               else
3545 #endif
3546                 for (j = 0; j < BITSET_WORDS; ++j)
3547                   any_set |= (accepts[j] &= ~dfa->word_char[j]);
3548               if (!any_set)
3549                 continue;
3550             }
3551         }
3552
3553       /* Then divide 'accepts' into DFA states, or create a new
3554          state.  Above, we make sure that accepts is not empty.  */
3555       for (j = 0; j < ndests; ++j)
3556         {
3557           bitset_t intersec; /* Intersection sets, see below.  */
3558           bitset_t remains;
3559           /* Flags, see below.  */
3560           bitset_word_t has_intersec, not_subset, not_consumed;
3561
3562           /* Optimization, skip if this state doesn't accept the character.  */
3563           if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3564             continue;
3565
3566           /* Enumerate the intersection set of this state and 'accepts'.  */
3567           has_intersec = 0;
3568           for (k = 0; k < BITSET_WORDS; ++k)
3569             has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3570           /* And skip if the intersection set is empty.  */
3571           if (!has_intersec)
3572             continue;
3573
3574           /* Then check if this state is a subset of 'accepts'.  */
3575           not_subset = not_consumed = 0;
3576           for (k = 0; k < BITSET_WORDS; ++k)
3577             {
3578               not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3579               not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3580             }
3581
3582           /* If this state isn't a subset of 'accepts', create a
3583              new group state, which has the 'remains'. */
3584           if (not_subset)
3585             {
3586               bitset_copy (dests_ch[ndests], remains);
3587               bitset_copy (dests_ch[j], intersec);
3588               err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3589               if (__glibc_unlikely (err != REG_NOERROR))
3590                 goto error_return;
3591               ++ndests;
3592             }
3593
3594           /* Put the position in the current group. */
3595           ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3596           if (__glibc_unlikely (! ok))
3597             goto error_return;
3598
3599           /* If all characters are consumed, go to next node. */
3600           if (!not_consumed)
3601             break;
3602         }
3603       /* Some characters remain, create a new group. */
3604       if (j == ndests)
3605         {
3606           bitset_copy (dests_ch[ndests], accepts);
3607           err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3608           if (__glibc_unlikely (err != REG_NOERROR))
3609             goto error_return;
3610           ++ndests;
3611           bitset_empty (accepts);
3612         }
3613     }
3614   assume (ndests <= SBC_MAX);
3615   return ndests;
3616  error_return:
3617   for (j = 0; j < ndests; ++j)
3618     re_node_set_free (dests_node + j);
3619   return -1;
3620 }
3621
3622 #ifdef RE_ENABLE_I18N
3623 /* Check how many bytes the node 'dfa->nodes[node_idx]' accepts.
3624    Return the number of the bytes the node accepts.
3625    STR_IDX is the current index of the input string.
3626
3627    This function handles the nodes which can accept one character, or
3628    one collating element like '.', '[a-z]', opposite to the other nodes
3629    can only accept one byte.  */
3630
3631 # ifdef _LIBC
3632 #  include <locale/weight.h>
3633 # endif
3634
3635 static int
3636 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3637                          const re_string_t *input, Idx str_idx)
3638 {
3639   const re_token_t *node = dfa->nodes + node_idx;
3640   int char_len, elem_len;
3641   Idx i;
3642
3643   if (__glibc_unlikely (node->type == OP_UTF8_PERIOD))
3644     {
3645       unsigned char c = re_string_byte_at (input, str_idx), d;
3646       if (__glibc_likely (c < 0xc2))
3647         return 0;
3648
3649       if (str_idx + 2 > input->len)
3650         return 0;
3651
3652       d = re_string_byte_at (input, str_idx + 1);
3653       if (c < 0xe0)
3654         return (d < 0x80 || d > 0xbf) ? 0 : 2;
3655       else if (c < 0xf0)
3656         {
3657           char_len = 3;
3658           if (c == 0xe0 && d < 0xa0)
3659             return 0;
3660         }
3661       else if (c < 0xf8)
3662         {
3663           char_len = 4;
3664           if (c == 0xf0 && d < 0x90)
3665             return 0;
3666         }
3667       else if (c < 0xfc)
3668         {
3669           char_len = 5;
3670           if (c == 0xf8 && d < 0x88)
3671             return 0;
3672         }
3673       else if (c < 0xfe)
3674         {
3675           char_len = 6;
3676           if (c == 0xfc && d < 0x84)
3677             return 0;
3678         }
3679       else
3680         return 0;
3681
3682       if (str_idx + char_len > input->len)
3683         return 0;
3684
3685       for (i = 1; i < char_len; ++i)
3686         {
3687           d = re_string_byte_at (input, str_idx + i);
3688           if (d < 0x80 || d > 0xbf)
3689             return 0;
3690         }
3691       return char_len;
3692     }
3693
3694   char_len = re_string_char_size_at (input, str_idx);
3695   if (node->type == OP_PERIOD)
3696     {
3697       if (char_len <= 1)
3698         return 0;
3699       /* FIXME: I don't think this if is needed, as both '\n'
3700          and '\0' are char_len == 1.  */
3701       /* '.' accepts any one character except the following two cases.  */
3702       if ((!(dfa->syntax & RE_DOT_NEWLINE)
3703            && re_string_byte_at (input, str_idx) == '\n')
3704           || ((dfa->syntax & RE_DOT_NOT_NULL)
3705               && re_string_byte_at (input, str_idx) == '\0'))
3706         return 0;
3707       return char_len;
3708     }
3709
3710   elem_len = re_string_elem_size_at (input, str_idx);
3711   if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3712     return 0;
3713
3714   if (node->type == COMPLEX_BRACKET)
3715     {
3716       const re_charset_t *cset = node->opr.mbcset;
3717 # ifdef _LIBC
3718       const unsigned char *pin
3719         = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3720       Idx j;
3721       uint32_t nrules;
3722 # endif /* _LIBC */
3723       int match_len = 0;
3724       wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3725                     ? re_string_wchar_at (input, str_idx) : 0);
3726
3727       /* match with multibyte character?  */
3728       for (i = 0; i < cset->nmbchars; ++i)
3729         if (wc == cset->mbchars[i])
3730           {
3731             match_len = char_len;
3732             goto check_node_accept_bytes_match;
3733           }
3734       /* match with character_class?  */
3735       for (i = 0; i < cset->nchar_classes; ++i)
3736         {
3737           wctype_t wt = cset->char_classes[i];
3738           if (__iswctype (wc, wt))
3739             {
3740               match_len = char_len;
3741               goto check_node_accept_bytes_match;
3742             }
3743         }
3744
3745 # ifdef _LIBC
3746       nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3747       if (nrules != 0)
3748         {
3749           unsigned int in_collseq = 0;
3750           const int32_t *table, *indirect;
3751           const unsigned char *weights, *extra;
3752           const char *collseqwc;
3753
3754           /* match with collating_symbol?  */
3755           if (cset->ncoll_syms)
3756             extra = (const unsigned char *)
3757               _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3758           for (i = 0; i < cset->ncoll_syms; ++i)
3759             {
3760               const unsigned char *coll_sym = extra + cset->coll_syms[i];
3761               /* Compare the length of input collating element and
3762                  the length of current collating element.  */
3763               if (*coll_sym != elem_len)
3764                 continue;
3765               /* Compare each bytes.  */
3766               for (j = 0; j < *coll_sym; j++)
3767                 if (pin[j] != coll_sym[1 + j])
3768                   break;
3769               if (j == *coll_sym)
3770                 {
3771                   /* Match if every bytes is equal.  */
3772                   match_len = j;
3773                   goto check_node_accept_bytes_match;
3774                 }
3775             }
3776
3777           if (cset->nranges)
3778             {
3779               if (elem_len <= char_len)
3780                 {
3781                   collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3782                   in_collseq = __collseq_table_lookup (collseqwc, wc);
3783                 }
3784               else
3785                 in_collseq = find_collation_sequence_value (pin, elem_len);
3786             }
3787           /* match with range expression?  */
3788           /* FIXME: Implement rational ranges here, too.  */
3789           for (i = 0; i < cset->nranges; ++i)
3790             if (cset->range_starts[i] <= in_collseq
3791                 && in_collseq <= cset->range_ends[i])
3792               {
3793                 match_len = elem_len;
3794                 goto check_node_accept_bytes_match;
3795               }
3796
3797           /* match with equivalence_class?  */
3798           if (cset->nequiv_classes)
3799             {
3800               const unsigned char *cp = pin;
3801               table = (const int32_t *)
3802                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3803               weights = (const unsigned char *)
3804                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3805               extra = (const unsigned char *)
3806                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3807               indirect = (const int32_t *)
3808                 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3809               int32_t idx = findidx (table, indirect, extra, &cp, elem_len);
3810               int32_t rule = idx >> 24;
3811               idx &= 0xffffff;
3812               if (idx > 0)
3813                 {
3814                   size_t weight_len = weights[idx];
3815                   for (i = 0; i < cset->nequiv_classes; ++i)
3816                     {
3817                       int32_t equiv_class_idx = cset->equiv_classes[i];
3818                       int32_t equiv_class_rule = equiv_class_idx >> 24;
3819                       equiv_class_idx &= 0xffffff;
3820                       if (weights[equiv_class_idx] == weight_len
3821                           && equiv_class_rule == rule
3822                           && memcmp (weights + idx + 1,
3823                                      weights + equiv_class_idx + 1,
3824                                      weight_len) == 0)
3825                         {
3826                           match_len = elem_len;
3827                           goto check_node_accept_bytes_match;
3828                         }
3829                     }
3830                 }
3831             }
3832         }
3833       else
3834 # endif /* _LIBC */
3835         {
3836           /* match with range expression?  */
3837           for (i = 0; i < cset->nranges; ++i)
3838             {
3839               if (cset->range_starts[i] <= wc && wc <= cset->range_ends[i])
3840                 {
3841                   match_len = char_len;
3842                   goto check_node_accept_bytes_match;
3843                 }
3844             }
3845         }
3846     check_node_accept_bytes_match:
3847       if (!cset->non_match)
3848         return match_len;
3849       else
3850         {
3851           if (match_len > 0)
3852             return 0;
3853           else
3854             return (elem_len > char_len) ? elem_len : char_len;
3855         }
3856     }
3857   return 0;
3858 }
3859
3860 # ifdef _LIBC
3861 static unsigned int
3862 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
3863 {
3864   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3865   if (nrules == 0)
3866     {
3867       if (mbs_len == 1)
3868         {
3869           /* No valid character.  Match it as a single byte character.  */
3870           const unsigned char *collseq = (const unsigned char *)
3871             _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3872           return collseq[mbs[0]];
3873         }
3874       return UINT_MAX;
3875     }
3876   else
3877     {
3878       int32_t idx;
3879       const unsigned char *extra = (const unsigned char *)
3880         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3881       int32_t extrasize = (const unsigned char *)
3882         _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
3883
3884       for (idx = 0; idx < extrasize;)
3885         {
3886           int mbs_cnt;
3887           bool found = false;
3888           int32_t elem_mbs_len;
3889           /* Skip the name of collating element name.  */
3890           idx = idx + extra[idx] + 1;
3891           elem_mbs_len = extra[idx++];
3892           if (mbs_len == elem_mbs_len)
3893             {
3894               for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
3895                 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
3896                   break;
3897               if (mbs_cnt == elem_mbs_len)
3898                 /* Found the entry.  */
3899                 found = true;
3900             }
3901           /* Skip the byte sequence of the collating element.  */
3902           idx += elem_mbs_len;
3903           /* Adjust for the alignment.  */
3904           idx = (idx + 3) & ~3;
3905           /* Skip the collation sequence value.  */
3906           idx += sizeof (uint32_t);
3907           /* Skip the wide char sequence of the collating element.  */
3908           idx = idx + sizeof (uint32_t) * (*(int32_t *) (extra + idx) + 1);
3909           /* If we found the entry, return the sequence value.  */
3910           if (found)
3911             return *(uint32_t *) (extra + idx);
3912           /* Skip the collation sequence value.  */
3913           idx += sizeof (uint32_t);
3914         }
3915       return UINT_MAX;
3916     }
3917 }
3918 # endif /* _LIBC */
3919 #endif /* RE_ENABLE_I18N */
3920
3921 /* Check whether the node accepts the byte which is IDX-th
3922    byte of the INPUT.  */
3923
3924 static bool
3925 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
3926                    Idx idx)
3927 {
3928   unsigned char ch;
3929   ch = re_string_byte_at (&mctx->input, idx);
3930   switch (node->type)
3931     {
3932     case CHARACTER:
3933       if (node->opr.c != ch)
3934         return false;
3935       break;
3936
3937     case SIMPLE_BRACKET:
3938       if (!bitset_contain (node->opr.sbcset, ch))
3939         return false;
3940       break;
3941
3942 #ifdef RE_ENABLE_I18N
3943     case OP_UTF8_PERIOD:
3944       if (ch >= ASCII_CHARS)
3945         return false;
3946       FALLTHROUGH;
3947 #endif
3948     case OP_PERIOD:
3949       if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
3950           || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
3951         return false;
3952       break;
3953
3954     default:
3955       return false;
3956     }
3957
3958   if (node->constraint)
3959     {
3960       /* The node has constraints.  Check whether the current context
3961          satisfies the constraints.  */
3962       unsigned int context = re_string_context_at (&mctx->input, idx,
3963                                                    mctx->eflags);
3964       if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
3965         return false;
3966     }
3967
3968   return true;
3969 }
3970
3971 /* Extend the buffers, if the buffers have run out.  */
3972
3973 static reg_errcode_t
3974 __attribute_warn_unused_result__
3975 extend_buffers (re_match_context_t *mctx, int min_len)
3976 {
3977   reg_errcode_t ret;
3978   re_string_t *pstr = &mctx->input;
3979
3980   /* Avoid overflow.  */
3981   if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) / 2
3982                         <= pstr->bufs_len))
3983     return REG_ESPACE;
3984
3985   /* Double the lengths of the buffers, but allocate at least MIN_LEN.  */
3986   ret = re_string_realloc_buffers (pstr,
3987                                    MAX (min_len,
3988                                         MIN (pstr->len, pstr->bufs_len * 2)));
3989   if (__glibc_unlikely (ret != REG_NOERROR))
3990     return ret;
3991
3992   if (mctx->state_log != NULL)
3993     {
3994       /* And double the length of state_log.  */
3995       /* XXX We have no indication of the size of this buffer.  If this
3996          allocation fail we have no indication that the state_log array
3997          does not have the right size.  */
3998       re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
3999                                               pstr->bufs_len + 1);
4000       if (__glibc_unlikely (new_array == NULL))
4001         return REG_ESPACE;
4002       mctx->state_log = new_array;
4003     }
4004
4005   /* Then reconstruct the buffers.  */
4006   if (pstr->icase)
4007     {
4008 #ifdef RE_ENABLE_I18N
4009       if (pstr->mb_cur_max > 1)
4010         {
4011           ret = build_wcs_upper_buffer (pstr);
4012           if (__glibc_unlikely (ret != REG_NOERROR))
4013             return ret;
4014         }
4015       else
4016 #endif /* RE_ENABLE_I18N  */
4017         build_upper_buffer (pstr);
4018     }
4019   else
4020     {
4021 #ifdef RE_ENABLE_I18N
4022       if (pstr->mb_cur_max > 1)
4023         build_wcs_buffer (pstr);
4024       else
4025 #endif /* RE_ENABLE_I18N  */
4026         {
4027           if (pstr->trans != NULL)
4028             re_string_translate_buffer (pstr);
4029         }
4030     }
4031   return REG_NOERROR;
4032 }
4033
4034 \f
4035 /* Functions for matching context.  */
4036
4037 /* Initialize MCTX.  */
4038
4039 static reg_errcode_t
4040 __attribute_warn_unused_result__
4041 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4042 {
4043   mctx->eflags = eflags;
4044   mctx->match_last = -1;
4045   if (n > 0)
4046     {
4047       /* Avoid overflow.  */
4048       size_t max_object_size =
4049         MAX (sizeof (struct re_backref_cache_entry),
4050              sizeof (re_sub_match_top_t *));
4051       if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / max_object_size) < n))
4052         return REG_ESPACE;
4053
4054       mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4055       mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4056       if (__glibc_unlikely (mctx->bkref_ents == NULL || mctx->sub_tops == NULL))
4057         return REG_ESPACE;
4058     }
4059   /* Already zero-ed by the caller.
4060      else
4061        mctx->bkref_ents = NULL;
4062      mctx->nbkref_ents = 0;
4063      mctx->nsub_tops = 0;  */
4064   mctx->abkref_ents = n;
4065   mctx->max_mb_elem_len = 1;
4066   mctx->asub_tops = n;
4067   return REG_NOERROR;
4068 }
4069
4070 /* Clean the entries which depend on the current input in MCTX.
4071    This function must be invoked when the matcher changes the start index
4072    of the input, or changes the input string.  */
4073
4074 static void
4075 match_ctx_clean (re_match_context_t *mctx)
4076 {
4077   Idx st_idx;
4078   for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4079     {
4080       Idx sl_idx;
4081       re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4082       for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4083         {
4084           re_sub_match_last_t *last = top->lasts[sl_idx];
4085           re_free (last->path.array);
4086           re_free (last);
4087         }
4088       re_free (top->lasts);
4089       if (top->path)
4090         {
4091           re_free (top->path->array);
4092           re_free (top->path);
4093         }
4094       re_free (top);
4095     }
4096
4097   mctx->nsub_tops = 0;
4098   mctx->nbkref_ents = 0;
4099 }
4100
4101 /* Free all the memory associated with MCTX.  */
4102
4103 static void
4104 match_ctx_free (re_match_context_t *mctx)
4105 {
4106   /* First, free all the memory associated with MCTX->SUB_TOPS.  */
4107   match_ctx_clean (mctx);
4108   re_free (mctx->sub_tops);
4109   re_free (mctx->bkref_ents);
4110 }
4111
4112 /* Add a new backreference entry to MCTX.
4113    Note that we assume that caller never call this function with duplicate
4114    entry, and call with STR_IDX which isn't smaller than any existing entry.
4115 */
4116
4117 static reg_errcode_t
4118 __attribute_warn_unused_result__
4119 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4120                      Idx to)
4121 {
4122   if (mctx->nbkref_ents >= mctx->abkref_ents)
4123     {
4124       struct re_backref_cache_entry* new_entry;
4125       new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4126                               mctx->abkref_ents * 2);
4127       if (__glibc_unlikely (new_entry == NULL))
4128         {
4129           re_free (mctx->bkref_ents);
4130           return REG_ESPACE;
4131         }
4132       mctx->bkref_ents = new_entry;
4133       memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4134               sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4135       mctx->abkref_ents *= 2;
4136     }
4137   if (mctx->nbkref_ents > 0
4138       && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4139     mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4140
4141   mctx->bkref_ents[mctx->nbkref_ents].node = node;
4142   mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4143   mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4144   mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4145
4146   /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4147      If bit N is clear, means that this entry won't epsilon-transition to
4148      an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression.  If
4149      it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4150      such node.
4151
4152      A backreference does not epsilon-transition unless it is empty, so set
4153      to all zeros if FROM != TO.  */
4154   mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4155     = (from == to ? -1 : 0);
4156
4157   mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4158   if (mctx->max_mb_elem_len < to - from)
4159     mctx->max_mb_elem_len = to - from;
4160   return REG_NOERROR;
4161 }
4162
4163 /* Return the first entry with the same str_idx, or -1 if none is
4164    found.  Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX.  */
4165
4166 static Idx
4167 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4168 {
4169   Idx left, right, mid, last;
4170   last = right = mctx->nbkref_ents;
4171   for (left = 0; left < right;)
4172     {
4173       mid = (left + right) / 2;
4174       if (mctx->bkref_ents[mid].str_idx < str_idx)
4175         left = mid + 1;
4176       else
4177         right = mid;
4178     }
4179   if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4180     return left;
4181   else
4182     return -1;
4183 }
4184
4185 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4186    at STR_IDX.  */
4187
4188 static reg_errcode_t
4189 __attribute_warn_unused_result__
4190 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4191 {
4192   DEBUG_ASSERT (mctx->sub_tops != NULL);
4193   DEBUG_ASSERT (mctx->asub_tops > 0);
4194   if (__glibc_unlikely (mctx->nsub_tops == mctx->asub_tops))
4195     {
4196       Idx new_asub_tops = mctx->asub_tops * 2;
4197       re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4198                                                    re_sub_match_top_t *,
4199                                                    new_asub_tops);
4200       if (__glibc_unlikely (new_array == NULL))
4201         return REG_ESPACE;
4202       mctx->sub_tops = new_array;
4203       mctx->asub_tops = new_asub_tops;
4204     }
4205   mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4206   if (__glibc_unlikely (mctx->sub_tops[mctx->nsub_tops] == NULL))
4207     return REG_ESPACE;
4208   mctx->sub_tops[mctx->nsub_tops]->node = node;
4209   mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4210   return REG_NOERROR;
4211 }
4212
4213 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4214    at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP.  */
4215
4216 static re_sub_match_last_t *
4217 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4218 {
4219   re_sub_match_last_t *new_entry;
4220   if (__glibc_unlikely (subtop->nlasts == subtop->alasts))
4221     {
4222       Idx new_alasts = 2 * subtop->alasts + 1;
4223       re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4224                                                     re_sub_match_last_t *,
4225                                                     new_alasts);
4226       if (__glibc_unlikely (new_array == NULL))
4227         return NULL;
4228       subtop->lasts = new_array;
4229       subtop->alasts = new_alasts;
4230     }
4231   new_entry = calloc (1, sizeof (re_sub_match_last_t));
4232   if (__glibc_likely (new_entry != NULL))
4233     {
4234       subtop->lasts[subtop->nlasts] = new_entry;
4235       new_entry->node = node;
4236       new_entry->str_idx = str_idx;
4237       ++subtop->nlasts;
4238     }
4239   return new_entry;
4240 }
4241
4242 static void
4243 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4244                re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4245 {
4246   sctx->sifted_states = sifted_sts;
4247   sctx->limited_states = limited_sts;
4248   sctx->last_node = last_node;
4249   sctx->last_str_idx = last_str_idx;
4250   re_node_set_init_empty (&sctx->limits);
4251 }