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,
708 dfa);
715 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
719 /* We will log all the DFA states through which the dfa pass,
720 if nmatch > 1, or this dfa has "multibyte node", which is a
723 if (nmatch > 1 || dfa->has_mb_node)
750 sb = dfa->mb_cur_max == 1;
875 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
881 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
882 || dfa->nbackref)
923 dfa->has_plural_match && dfa->nbackref > 0);
958 if (dfa->subexp_map)
960 if (dfa->subexp_map[reg_idx] != reg_idx)
963 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
965 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
971 if (dfa->nbackref)
981 const re_dfa_t *const dfa = mctx->dfa;
1003 if (dfa->nbackref)
1037 ret = merge_state_array (dfa, sifted_states, lim_states,
1078 const re_dfa_t *const dfa = mctx->dfa;
1079 if (dfa->init_state->has_constraint)
1084 return dfa->init_state_word;
1086 return dfa->init_state;
1088 return dfa->init_state_begbuf;
1090 return dfa->init_state_nl;
1094 return re_acquire_state_context (err, dfa,
1095 dfa->init_state->entrance_nodes,
1100 return dfa->init_state;
1103 return dfa->init_state;
1120 const re_dfa_t *const dfa = mctx->dfa;
1144 if (BE (dfa->nbackref, 0))
1249 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1251 re_token_type_t type = dfa->nodes[node].type;
1252 unsigned int constraint = dfa->nodes[node].constraint;
1278 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1294 const re_dfa_t *const dfa = mctx->dfa;
1297 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1300 re_node_set *edests = &dfa->edests[node];
1337 re_token_type_t type = dfa->nodes[node].type;
1340 if (dfa->nodes[node].accept_mb)
1341 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1346 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1367 dest_node = dfa->edests[node].elems[0];
1375 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1377 Idx dest_node = dfa->nexts[node];
1442 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1464 cur_node = dfa->init_node;
1483 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1563 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1566 int type = dfa->nodes[cur_node].type;
1569 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1580 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1593 if (dfa->nodes[cur_node].opt_subexp
1696 const re_dfa_t *const dfa = mctx->dfa;
1714 re_token_type_t type = dfa->nodes[prev_node].type;
1719 if (dfa->nodes[prev_node].accept_mb)
1727 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1729 dfa->nexts[prev_node]))
1739 dfa->nexts[prev_node], to_idx,
1780 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1796 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1811 const re_dfa_t *const dfa = mctx->dfa;
1825 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1832 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1839 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1855 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1861 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1873 dfa->inveclosures + dest_nodes->elems[i]);
1884 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1889 re_node_set *inv_eclosure = dfa->inveclosures + node;
1897 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1899 Idx edst1 = dfa->edests[cur_node].elems[0];
1900 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1901 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1909 dfa->inveclosures + cur_node);
1936 const re_dfa_t *const dfa = mctx->dfa;
1946 subexp_idx = dfa->nodes[ent->node].opr.idx;
1972 const re_dfa_t *const dfa = mctx->dfa;
1973 const re_node_set *eclosures = dfa->eclosures + from_node;
1981 switch (dfa->nodes[node].type)
2006 dst = dfa->edests[node].elems[0];
2032 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2037 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2081 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2097 subexp_idx = dfa->nodes[ent->node].opr.idx;
2105 re_token_type_t type = dfa->nodes[node].type;
2107 && subexp_idx == dfa->nodes[node].opr.idx)
2110 && subexp_idx == dfa->nodes[node].opr.idx)
2118 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2129 if (!re_node_set_contains (dfa->inveclosures + node,
2131 && !re_node_set_contains (dfa->eclosures + node,
2136 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2149 re_token_type_t type = dfa->nodes[node].type;
2152 if (subexp_idx != dfa->nodes[node].opr.idx)
2156 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2172 const re_dfa_t *const dfa = mctx->dfa;
2189 type = dfa->nodes[node].type;
2210 dst_node = (subexp_len ? dfa->nexts[node]
2211 : dfa->edests[node].elems[0]);
2241 err = merge_state_array (dfa, sctx->limited_states,
2272 const re_dfa_t *const dfa = mctx->dfa;
2275 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2278 dfa->nexts[node_idx]))
2345 if (!build_trtable (mctx->dfa, state))
2361 const re_dfa_t *const dfa = mctx->dfa;
2401 = re_acquire_state_context (err, dfa, &next_nodes, context);
2409 if (BE (dfa->nbackref, 0) && next_state != NULL)
2471 const re_dfa_t *const dfa = mctx->dfa;
2483 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2484 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2485 && (dfa->used_bkref_map
2486 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2504 const re_dfa_t *const dfa = mctx->dfa;
2516 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2519 dfa->eclosures + dfa->nexts[cur_node]);
2528 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2543 const re_dfa_t *const dfa = mctx->dfa;
2556 if (!dfa->nodes[cur_node_idx].accept_mb)
2559 if (dfa->nodes[cur_node_idx].constraint)
2564 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2570 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2583 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2585 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2600 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2614 const re_dfa_t *const dfa = mctx->dfa;
2624 const re_token_t *node = dfa->nodes + node_idx;
2649 assert (dfa->nexts[node_idx] != REG_MISSING);
2661 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2662 : dfa->eclosures + dfa->nexts[node_idx]);
2674 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2692 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2728 const re_dfa_t *const dfa = mctx->dfa;
2743 subexp_num = dfa->nodes[bkref_node].opr.idx;
2753 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2836 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2905 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2912 const re_token_t *node = dfa->nodes + cls_node;
2930 const re_dfa_t *const dfa = mctx->dfa;
2938 subexp_num = dfa->nodes[top_node].opr.idx;
2972 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3003 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3039 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3054 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3092 const re_dfa_t *const dfa = mctx->dfa;
3105 re_token_type_t type = dfa->nodes[cur_node].type;
3110 if (dfa->nodes[cur_node].accept_mb)
3112 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3117 Idx next_node = dfa->nexts[cur_node];
3136 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3148 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3150 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3170 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3188 const re_node_set *eclosure = dfa->eclosures + cur_node;
3189 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3203 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3223 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3231 if (dfa->nodes[cur_node].type == type
3232 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3245 if (dfa->edests[cur_node].nelem == 0)
3247 if (dfa->edests[cur_node].nelem == 2)
3250 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3251 dfa->edests[cur_node].elems[1],
3256 cur_node = dfa->edests[cur_node].elems[0];
3271 const re_dfa_t *const dfa = mctx->dfa;
3298 next_node = dfa->edests[ent->node].elems[0];
3302 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3318 next_node = dfa->nexts[ent->node];
3341 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3357 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3400 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3459 next_node = dfa->nexts[dests_node[i].elems[j]];
3462 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3467 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3474 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3479 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3482 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3519 if (dfa->word_char[i] & mask)
3592 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3607 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3621 if (dfa->mb_cur_max > 1)
3622 bitset_merge (accepts, dfa->sb_char);
3626 if (!(dfa->syntax & RE_DOT_NEWLINE))
3628 if (dfa->syntax & RE_DOT_NOT_NULL)
3638 if (!(dfa->syntax & RE_DOT_NEWLINE))
3640 if (dfa->syntax & RE_DOT_NOT_NULL)
3675 if (dfa->mb_cur_max > 1)
3677 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3681 any_set |= (accepts[j] &= dfa->word_char[j]);
3694 if (dfa->mb_cur_max > 1)
3696 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3700 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3775 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3785 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3788 const re_token_t *node = dfa->nodes + node_idx;
3851 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3853 ((dfa->syntax & RE_DOT_NOT_NULL) &&
4114 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4115 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))