contrib/cvs-1.12/lib/regexec.c

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