Lines Matching refs:dfa
67 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
100 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
116 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
126 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
164 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
175 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
179 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
187 static bool build_trtable (const re_dfa_t *dfa,
190 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
199 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
236 re_dfa_t *dfa = (re_dfa_t *) preg->buffer; local
253 __libc_lock_lock (dfa->lock);
260 __libc_lock_unlock (dfa->lock);
431 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer; in re_search_stub() local
443 __libc_lock_lock (dfa->lock); in re_search_stub()
507 __libc_lock_unlock (dfa->lock); in re_search_stub()
650 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer; in re_search_internal() local
661 re_match_context_t mctx = { .dfa = dfa }; in re_search_internal()
672 mctx.dfa = dfa; in re_search_internal()
679 if (BE (preg->used == 0 || dfa->init_state == NULL in re_search_internal()
680 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL in re_search_internal()
681 || dfa->init_state_begbuf == NULL, 0)) in re_search_internal()
692 if (dfa->init_state->nodes.nelem == 0 in re_search_internal()
693 && dfa->init_state_word->nodes.nelem == 0 in re_search_internal()
694 && (dfa->init_state_nl->nodes.nelem == 0 in re_search_internal()
703 fl_longest_match = (nmatch != 0 || dfa->nbackref); in re_search_internal()
705 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1, in re_search_internal()
707 dfa); in re_search_internal()
714 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2); in re_search_internal()
722 if (nmatch > 1 || dfa->has_mb_node) in re_search_internal()
749 sb = dfa->mb_cur_max == 1; in re_search_internal()
874 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref) in re_search_internal()
880 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match) in re_search_internal()
881 || dfa->nbackref) in re_search_internal()
922 dfa->has_plural_match && dfa->nbackref > 0); in re_search_internal()
957 if (dfa->subexp_map) in re_search_internal()
959 if (dfa->subexp_map[reg_idx] != reg_idx) in re_search_internal()
962 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so; in re_search_internal()
964 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo; in re_search_internal()
970 if (dfa->nbackref) in re_search_internal()
980 const re_dfa_t *const dfa = mctx->dfa; in prune_impossible_nodes() local
1002 if (dfa->nbackref) in prune_impossible_nodes()
1036 ret = merge_state_array (dfa, sifted_states, lim_states, in prune_impossible_nodes()
1077 const re_dfa_t *const dfa = mctx->dfa; in acquire_init_state_context() local
1078 if (dfa->init_state->has_constraint) in acquire_init_state_context()
1083 return dfa->init_state_word; in acquire_init_state_context()
1085 return dfa->init_state; in acquire_init_state_context()
1087 return dfa->init_state_begbuf; in acquire_init_state_context()
1089 return dfa->init_state_nl; in acquire_init_state_context()
1093 return re_acquire_state_context (err, dfa, in acquire_init_state_context()
1094 dfa->init_state->entrance_nodes, in acquire_init_state_context()
1099 return dfa->init_state; in acquire_init_state_context()
1102 return dfa->init_state; in acquire_init_state_context()
1119 const re_dfa_t *const dfa = mctx->dfa; in check_matching() local
1143 if (BE (dfa->nbackref, 0)) in check_matching()
1248 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context) in check_halt_node_context() argument
1250 re_token_type_t type = dfa->nodes[node].type; in check_halt_node_context()
1251 unsigned int constraint = dfa->nodes[node].constraint; in check_halt_node_context()
1277 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context)) in check_halt_state_context()
1293 const re_dfa_t *const dfa = mctx->dfa; in proceed_next_node() local
1296 if (IS_EPSILON_NODE (dfa->nodes[node].type)) in proceed_next_node()
1299 re_node_set *edests = &dfa->edests[node]; in proceed_next_node()
1336 re_token_type_t type = dfa->nodes[node].type; in proceed_next_node()
1339 if (dfa->nodes[node].accept_mb) in proceed_next_node()
1340 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx); in proceed_next_node()
1345 Idx subexp_idx = dfa->nodes[node].opr.idx + 1; in proceed_next_node()
1366 dest_node = dfa->edests[node].elems[0]; in proceed_next_node()
1374 || check_node_accept (mctx, dfa->nodes + node, *pidx)) in proceed_next_node()
1376 Idx dest_node = dfa->nexts[node]; in proceed_next_node()
1441 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer; in set_regs() local
1463 cur_node = dfa->init_node; in set_regs()
1482 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch); in set_regs()
1562 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch, in update_regs() argument
1565 int type = dfa->nodes[cur_node].type; in update_regs()
1568 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1; in update_regs()
1579 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1; in update_regs()
1592 if (dfa->nodes[cur_node].opt_subexp in update_regs()
1695 const re_dfa_t *const dfa = mctx->dfa; in build_sifted_states() local
1713 re_token_type_t type = dfa->nodes[prev_node].type; in build_sifted_states()
1718 if (dfa->nodes[prev_node].accept_mb) in build_sifted_states()
1726 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx) in build_sifted_states()
1728 dfa->nexts[prev_node])) in build_sifted_states()
1738 dfa->nexts[prev_node], to_idx, in build_sifted_states()
1779 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst, in merge_state_array() argument
1795 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set); in merge_state_array()
1810 const re_dfa_t *const dfa = mctx->dfa; in update_cur_sifted_state() local
1824 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates); in update_cur_sifted_state()
1831 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits, in update_cur_sifted_state()
1838 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes); in update_cur_sifted_state()
1854 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes, in add_epsilon_src_nodes() argument
1860 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes); in add_epsilon_src_nodes()
1871 dfa->inveclosures + dest_nodes->elems[i]); in add_epsilon_src_nodes()
1879 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes, in sub_epsilon_src_nodes() argument
1884 re_node_set *inv_eclosure = dfa->inveclosures + node; in sub_epsilon_src_nodes()
1892 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type)) in sub_epsilon_src_nodes()
1894 Idx edst1 = dfa->edests[cur_node].elems[0]; in sub_epsilon_src_nodes()
1895 Idx edst2 = ((dfa->edests[cur_node].nelem > 1) in sub_epsilon_src_nodes()
1896 ? dfa->edests[cur_node].elems[1] : REG_MISSING); in sub_epsilon_src_nodes()
1904 dfa->inveclosures + cur_node); in sub_epsilon_src_nodes()
1931 const re_dfa_t *const dfa = mctx->dfa; in check_dst_limits() local
1941 subexp_idx = dfa->nodes[ent->node].opr.idx; in check_dst_limits()
1967 const re_dfa_t *const dfa = mctx->dfa; in check_dst_limits_calc_pos_1() local
1968 const re_node_set *eclosures = dfa->eclosures + from_node; in check_dst_limits_calc_pos_1()
1976 switch (dfa->nodes[node].type) in check_dst_limits_calc_pos_1()
2001 dst = dfa->edests[node].elems[0]; in check_dst_limits_calc_pos_1()
2027 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx) in check_dst_limits_calc_pos_1()
2032 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx) in check_dst_limits_calc_pos_1()
2076 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes, in check_subexp_limits() argument
2092 subexp_idx = dfa->nodes[ent->node].opr.idx; in check_subexp_limits()
2100 re_token_type_t type = dfa->nodes[node].type; in check_subexp_limits()
2102 && subexp_idx == dfa->nodes[node].opr.idx) in check_subexp_limits()
2105 && subexp_idx == dfa->nodes[node].opr.idx) in check_subexp_limits()
2113 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes, in check_subexp_limits()
2124 if (!re_node_set_contains (dfa->inveclosures + node, in check_subexp_limits()
2126 && !re_node_set_contains (dfa->eclosures + node, in check_subexp_limits()
2131 err = sub_epsilon_src_nodes (dfa, node, dest_nodes, in check_subexp_limits()
2144 re_token_type_t type = dfa->nodes[node].type; in check_subexp_limits()
2147 if (subexp_idx != dfa->nodes[node].opr.idx) in check_subexp_limits()
2151 err = sub_epsilon_src_nodes (dfa, node, dest_nodes, in check_subexp_limits()
2167 const re_dfa_t *const dfa = mctx->dfa; in sift_states_bkref() local
2184 type = dfa->nodes[node].type; in sift_states_bkref()
2205 dst_node = (subexp_len ? dfa->nexts[node] in sift_states_bkref()
2206 : dfa->edests[node].elems[0]); in sift_states_bkref()
2236 err = merge_state_array (dfa, sctx->limited_states, in sift_states_bkref()
2267 const re_dfa_t *const dfa = mctx->dfa; in sift_states_iter_mb() local
2270 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx); in sift_states_iter_mb()
2273 dfa->nexts[node_idx])) in sift_states_iter_mb()
2339 if (!build_trtable (mctx->dfa, state)) in transit_state()
2355 const re_dfa_t *const dfa = mctx->dfa; in merge_state_with_log() local
2395 = re_acquire_state_context (err, dfa, &next_nodes, context); in merge_state_with_log()
2403 if (BE (dfa->nbackref, 0) && next_state != NULL) in merge_state_with_log()
2465 const re_dfa_t *const dfa = mctx->dfa; in check_subexp_matching_top() local
2477 if (dfa->nodes[node].type == OP_OPEN_SUBEXP in check_subexp_matching_top()
2478 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS in check_subexp_matching_top()
2479 && (dfa->used_bkref_map in check_subexp_matching_top()
2480 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx))) in check_subexp_matching_top()
2498 const re_dfa_t *const dfa = mctx->dfa;
2510 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2513 dfa->eclosures + dfa->nexts[cur_node]);
2522 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2537 const re_dfa_t *const dfa = mctx->dfa; in transit_state_mb() local
2550 if (!dfa->nodes[cur_node_idx].accept_mb) in transit_state_mb()
2553 if (dfa->nodes[cur_node_idx].constraint) in transit_state_mb()
2558 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint, in transit_state_mb()
2564 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input, in transit_state_mb()
2577 assert (dfa->nexts[cur_node_idx] != REG_MISSING); in transit_state_mb()
2579 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx]; in transit_state_mb()
2594 = re_acquire_state_context (&err, dfa, &dest_nodes, context); in transit_state_mb()
2608 const re_dfa_t *const dfa = mctx->dfa; in transit_state_bkref() local
2618 const re_token_t *node = dfa->nodes + node_idx; in transit_state_bkref()
2643 assert (dfa->nexts[node_idx] != REG_MISSING); in transit_state_bkref()
2655 ? dfa->eclosures + dfa->edests[node_idx].elems[0] in transit_state_bkref()
2656 : dfa->eclosures + dfa->nexts[node_idx]); in transit_state_bkref()
2668 = re_acquire_state_context (&err, dfa, new_dest_nodes, in transit_state_bkref()
2686 = re_acquire_state_context (&err, dfa, &dest_nodes, context); in transit_state_bkref()
2722 const re_dfa_t *const dfa = mctx->dfa; in get_subexp() local
2737 subexp_num = dfa->nodes[bkref_node].opr.idx; in get_subexp()
2747 if (dfa->nodes[sub_top->node].opr.idx != subexp_num) in get_subexp()
2830 cls_node = find_subexp_node (dfa, nodes, subexp_num, in get_subexp()
2899 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes, in find_subexp_node() argument
2906 const re_token_t *node = dfa->nodes + cls_node; in find_subexp_node()
2924 const re_dfa_t *const dfa = mctx->dfa; in check_arrival() local
2932 subexp_num = dfa->nodes[top_node].opr.idx; in check_arrival()
2966 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type); in check_arrival()
2997 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context); in check_arrival()
3033 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type); in check_arrival()
3048 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context); in check_arrival()
3086 const re_dfa_t *const dfa = mctx->dfa; in check_arrival_add_next_nodes() local
3099 re_token_type_t type = dfa->nodes[cur_node].type; in check_arrival_add_next_nodes()
3104 if (dfa->nodes[cur_node].accept_mb) in check_arrival_add_next_nodes()
3106 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input, in check_arrival_add_next_nodes()
3111 Idx next_node = dfa->nexts[cur_node]; in check_arrival_add_next_nodes()
3130 mctx->state_log[next_idx] = re_acquire_state (&err, dfa, in check_arrival_add_next_nodes()
3142 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx)) in check_arrival_add_next_nodes()
3144 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]); in check_arrival_add_next_nodes()
3164 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes, in check_arrival_expand_ecl() argument
3182 const re_node_set *eclosure = dfa->eclosures + cur_node; in check_arrival_expand_ecl()
3183 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type); in check_arrival_expand_ecl()
3197 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node, in check_arrival_expand_ecl()
3217 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes, in check_arrival_expand_ecl_sub() argument
3225 if (dfa->nodes[cur_node].type == type in check_arrival_expand_ecl_sub()
3226 && dfa->nodes[cur_node].opr.idx == ex_subexp) in check_arrival_expand_ecl_sub()
3239 if (dfa->edests[cur_node].nelem == 0) in check_arrival_expand_ecl_sub()
3241 if (dfa->edests[cur_node].nelem == 2) in check_arrival_expand_ecl_sub()
3244 err = check_arrival_expand_ecl_sub (dfa, dst_nodes, in check_arrival_expand_ecl_sub()
3245 dfa->edests[cur_node].elems[1], in check_arrival_expand_ecl_sub()
3250 cur_node = dfa->edests[cur_node].elems[0]; in check_arrival_expand_ecl_sub()
3265 const re_dfa_t *const dfa = mctx->dfa; in expand_bkref_cache() local
3292 next_node = dfa->edests[ent->node].elems[0]; in expand_bkref_cache()
3296 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type); in expand_bkref_cache()
3312 next_node = dfa->nexts[ent->node]; in expand_bkref_cache()
3335 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set); in expand_bkref_cache()
3351 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state) in build_trtable() argument
3394 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch); in build_trtable()
3453 next_node = dfa->nexts[dests_node[i].elems[j]]; in build_trtable()
3456 err = re_node_set_merge (&follows, dfa->eclosures + next_node); in build_trtable()
3461 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0); in build_trtable()
3468 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows, in build_trtable()
3473 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1) in build_trtable()
3476 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows, in build_trtable()
3513 if (dfa->word_char[i] & mask) in build_trtable()
3586 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state, in group_nodes_into_DFAstates() argument
3601 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]]; in group_nodes_into_DFAstates()
3615 if (dfa->mb_cur_max > 1) in group_nodes_into_DFAstates()
3616 bitset_merge (accepts, dfa->sb_char); in group_nodes_into_DFAstates()
3620 if (!(dfa->syntax & RE_DOT_NEWLINE)) in group_nodes_into_DFAstates()
3622 if (dfa->syntax & RE_DOT_NOT_NULL) in group_nodes_into_DFAstates()
3632 if (!(dfa->syntax & RE_DOT_NEWLINE)) in group_nodes_into_DFAstates()
3634 if (dfa->syntax & RE_DOT_NOT_NULL) in group_nodes_into_DFAstates()
3669 if (dfa->mb_cur_max > 1) in group_nodes_into_DFAstates()
3671 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j])); in group_nodes_into_DFAstates()
3675 any_set |= (accepts[j] &= dfa->word_char[j]); in group_nodes_into_DFAstates()
3688 if (dfa->mb_cur_max > 1) in group_nodes_into_DFAstates()
3690 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j])); in group_nodes_into_DFAstates()
3694 any_set |= (accepts[j] &= ~dfa->word_char[j]); in group_nodes_into_DFAstates()
3779 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx, in check_node_accept_bytes() argument
3782 const re_token_t *node = dfa->nodes + node_idx; in check_node_accept_bytes()
3845 if ((!(dfa->syntax & RE_DOT_NEWLINE) && in check_node_accept_bytes()
3847 ((dfa->syntax & RE_DOT_NOT_NULL) && in check_node_accept_bytes()
4103 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE)) in check_node_accept()
4104 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL))) in check_node_accept()