Lines Matching defs:dfa
65 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
98 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
114 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
124 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
162 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
173 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
177 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
185 static bool build_trtable (const re_dfa_t *dfa,
188 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
197 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
235 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
252 __libc_lock_lock (dfa->lock);
259 __libc_lock_unlock (dfa->lock);
430 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
442 __libc_lock_lock (dfa->lock);
506 __libc_lock_unlock (dfa->lock);
651 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
662 re_match_context_t mctx = { .dfa = dfa };
673 mctx.dfa = dfa;
680 if (BE (preg->used == 0 || dfa->init_state == NULL
681 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
682 || dfa->init_state_begbuf == NULL, 0))
693 if (dfa->init_state->nodes.nelem == 0
694 && dfa->init_state_word->nodes.nelem == 0
695 && (dfa->init_state_nl->nodes.nelem == 0
704 fl_longest_match = (nmatch != 0 || dfa->nbackref);
706 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
707 preg->translate, preg->syntax & RE_ICASE, dfa);
714 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
718 /* We will log all the DFA states through which the dfa pass,
719 if nmatch > 1, or this dfa has "multibyte node", which is a
722 if (nmatch > 1 || dfa->has_mb_node)
749 sb = dfa->mb_cur_max == 1;
874 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
880 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
881 || dfa->nbackref)
922 dfa->has_plural_match && dfa->nbackref > 0);
957 if (dfa->subexp_map)
959 if (dfa->subexp_map[reg_idx] != reg_idx)
962 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
964 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
970 if (dfa->nbackref)
980 const re_dfa_t *const dfa = mctx->dfa;
1002 if (dfa->nbackref)
1036 ret = merge_state_array (dfa, sifted_states, lim_states,
1072 const re_dfa_t *const dfa = mctx->dfa;
1073 if (dfa->init_state->has_constraint)
1078 return dfa->init_state_word;
1080 return dfa->init_state;
1082 return dfa->init_state_begbuf;
1084 return dfa->init_state_nl;
1088 return re_acquire_state_context (err, dfa,
1089 dfa->init_state->entrance_nodes,
1094 return dfa->init_state;
1097 return dfa->init_state;
1114 const re_dfa_t *const dfa = mctx->dfa;
1138 if (BE (dfa->nbackref, 0))
1243 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1245 re_token_type_t type = dfa->nodes[node].type;
1246 unsigned int constraint = dfa->nodes[node].constraint;
1272 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1288 const re_dfa_t *const dfa = mctx->dfa;
1291 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1294 re_node_set *edests = &dfa->edests[node];
1331 re_token_type_t type = dfa->nodes[node].type;
1334 if (dfa->nodes[node].accept_mb)
1335 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1340 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1361 dest_node = dfa->edests[node].elems[0];
1369 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1371 Idx dest_node = dfa->nexts[node];
1436 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1458 cur_node = dfa->init_node;
1477 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1557 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1560 int type = dfa->nodes[cur_node].type;
1563 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1574 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1587 if (dfa->nodes[cur_node].opt_subexp
1690 const re_dfa_t *const dfa = mctx->dfa;
1708 re_token_type_t type = dfa->nodes[prev_node].type;
1713 if (dfa->nodes[prev_node].accept_mb)
1721 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1723 dfa->nexts[prev_node]))
1733 dfa->nexts[prev_node], to_idx,
1774 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1790 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1805 const re_dfa_t *const dfa = mctx->dfa;
1819 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1826 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1833 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1849 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1855 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1866 dfa->inveclosures + dest_nodes->elems[i]);
1874 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1879 re_node_set *inv_eclosure = dfa->inveclosures + node;
1887 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1889 Idx edst1 = dfa->edests[cur_node].elems[0];
1890 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1891 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1899 dfa->inveclosures + cur_node);
1926 const re_dfa_t *const dfa = mctx->dfa;
1936 subexp_idx = dfa->nodes[ent->node].opr.idx;
1962 const re_dfa_t *const dfa = mctx->dfa;
1963 const re_node_set *eclosures = dfa->eclosures + from_node;
1971 switch (dfa->nodes[node].type)
1996 dst = dfa->edests[node].elems[0];
2022 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2027 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2071 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2087 subexp_idx = dfa->nodes[ent->node].opr.idx;
2095 re_token_type_t type = dfa->nodes[node].type;
2097 && subexp_idx == dfa->nodes[node].opr.idx)
2100 && subexp_idx == dfa->nodes[node].opr.idx)
2108 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2119 if (!re_node_set_contains (dfa->inveclosures + node,
2121 && !re_node_set_contains (dfa->eclosures + node,
2126 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2139 re_token_type_t type = dfa->nodes[node].type;
2142 if (subexp_idx != dfa->nodes[node].opr.idx)
2146 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2162 const re_dfa_t *const dfa = mctx->dfa;
2179 type = dfa->nodes[node].type;
2200 dst_node = (subexp_len ? dfa->nexts[node]
2201 : dfa->edests[node].elems[0]);
2231 err = merge_state_array (dfa, sctx->limited_states,
2262 const re_dfa_t *const dfa = mctx->dfa;
2265 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2268 dfa->nexts[node_idx]))
2335 if (!build_trtable (mctx->dfa, state))
2351 const re_dfa_t *const dfa = mctx->dfa;
2391 = re_acquire_state_context (err, dfa, &next_nodes, context);
2399 if (BE (dfa->nbackref, 0) && next_state != NULL)
2461 const re_dfa_t *const dfa = mctx->dfa;
2473 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2474 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2475 && (dfa->used_bkref_map
2476 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2494 const re_dfa_t *const dfa = mctx->dfa;
2506 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2509 dfa->eclosures + dfa->nexts[cur_node]);
2518 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2533 const re_dfa_t *const dfa = mctx->dfa;
2546 if (!dfa->nodes[cur_node_idx].accept_mb)
2549 if (dfa->nodes[cur_node_idx].constraint)
2554 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2560 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2573 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2575 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2590 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2604 const re_dfa_t *const dfa = mctx->dfa;
2614 const re_token_t *node = dfa->nodes + node_idx;
2639 assert (dfa->nexts[node_idx] != REG_MISSING);
2651 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2652 : dfa->eclosures + dfa->nexts[node_idx]);
2664 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2682 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2718 const re_dfa_t *const dfa = mctx->dfa;
2733 subexp_num = dfa->nodes[bkref_node].opr.idx;
2743 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2826 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2895 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2902 const re_token_t *node = dfa->nodes + cls_node;
2920 const re_dfa_t *const dfa = mctx->dfa;
2928 subexp_num = dfa->nodes[top_node].opr.idx;
2962 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2993 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3029 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3044 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3082 const re_dfa_t *const dfa = mctx->dfa;
3093 re_token_type_t type = dfa->nodes[cur_node].type;
3098 if (dfa->nodes[cur_node].accept_mb)
3100 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3105 Idx next_node = dfa->nexts[cur_node];
3124 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3136 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3138 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3158 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3176 const re_node_set *eclosure = dfa->eclosures + cur_node;
3177 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3191 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3211 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3219 if (dfa->nodes[cur_node].type == type
3220 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3233 if (dfa->edests[cur_node].nelem == 0)
3235 if (dfa->edests[cur_node].nelem == 2)
3238 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3239 dfa->edests[cur_node].elems[1],
3244 cur_node = dfa->edests[cur_node].elems[0];
3259 const re_dfa_t *const dfa = mctx->dfa;
3286 next_node = dfa->edests[ent->node].elems[0];
3290 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3306 next_node = dfa->nexts[ent->node];
3329 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3345 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3388 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3447 next_node = dfa->nexts[dests_node[i].elems[j]];
3450 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3455 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3462 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3467 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3470 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3507 if (dfa->word_char[i] & mask)
3580 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3595 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3609 if (dfa->mb_cur_max > 1)
3610 bitset_merge (accepts, dfa->sb_char);
3614 if (!(dfa->syntax & RE_DOT_NEWLINE))
3616 if (dfa->syntax & RE_DOT_NOT_NULL)
3626 if (!(dfa->syntax & RE_DOT_NEWLINE))
3628 if (dfa->syntax & RE_DOT_NOT_NULL)
3663 if (dfa->mb_cur_max > 1)
3665 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3669 any_set |= (accepts[j] &= dfa->word_char[j]);
3682 if (dfa->mb_cur_max > 1)
3684 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3688 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3763 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3773 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3776 const re_token_t *node = dfa->nodes + node_idx;
3839 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3841 ((dfa->syntax & RE_DOT_NOT_NULL) &&
4097 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4098 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))