gl/regexec.c

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