Annotation of embedaddon/smartmontools/regex/regexec.c, revision 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>