contrib/grep/lib/regexec.c

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