Annotation of embedaddon/smartmontools/regex/regexec.c, revision 1.1.1.1

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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>