lib/regexec.c

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