Lines Matching defs:dfa
62 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
95 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
111 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
121 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
159 static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
170 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
174 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
182 static int build_trtable (const re_dfa_t *dfa,
185 static int check_node_accept_bytes (const re_dfa_t *dfa, int node_idx,
194 static int group_nodes_into_DFAstates (const re_dfa_t *dfa,
231 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
247 __libc_lock_lock (dfa->lock);
254 __libc_lock_unlock (dfa->lock);
422 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
432 __libc_lock_lock (dfa->lock);
496 __libc_lock_unlock (dfa->lock);
632 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
638 re_match_context_t mctx = { .dfa = dfa };
648 mctx.dfa = dfa;
655 if (BE (preg->used == 0 || dfa->init_state == NULL
656 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
657 || dfa->init_state_begbuf == NULL, 0))
668 if (dfa->init_state->nodes.nelem == 0
669 && dfa->init_state_word->nodes.nelem == 0
670 && (dfa->init_state_nl->nodes.nelem == 0
679 fl_longest_match = (nmatch != 0 || dfa->nbackref);
681 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
682 preg->translate, preg->syntax & RE_ICASE, dfa);
689 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
693 /* We will log all the DFA states through which the dfa pass,
694 if nmatch > 1, or this dfa has "multibyte node", which is a
697 if (nmatch > 1 || dfa->has_mb_node)
717 sb = dfa->mb_cur_max == 1;
842 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
848 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
849 || dfa->nbackref)
887 dfa->has_plural_match && dfa->nbackref > 0);
922 if (dfa->subexp_map)
924 if (dfa->subexp_map[reg_idx] != reg_idx)
927 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
929 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
935 if (dfa->nbackref)
945 const re_dfa_t *const dfa = mctx->dfa;
962 if (dfa->nbackref)
996 ret = merge_state_array (dfa, sifted_states, lim_states,
1037 const re_dfa_t *const dfa = mctx->dfa;
1038 if (dfa->init_state->has_constraint)
1043 return dfa->init_state_word;
1045 return dfa->init_state;
1047 return dfa->init_state_begbuf;
1049 return dfa->init_state_nl;
1053 return re_acquire_state_context (err, dfa,
1054 dfa->init_state->entrance_nodes,
1059 return dfa->init_state;
1062 return dfa->init_state;
1079 const re_dfa_t *const dfa = mctx->dfa;
1103 if (BE (dfa->nbackref, 0))
1208 check_halt_node_context (const re_dfa_t *dfa, int node, unsigned int context)
1210 re_token_type_t type = dfa->nodes[node].type;
1211 unsigned int constraint = dfa->nodes[node].constraint;
1237 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1253 const re_dfa_t *const dfa = mctx->dfa;
1255 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1258 re_node_set *edests = &dfa->edests[node];
1294 re_token_type_t type = dfa->nodes[node].type;
1297 if (dfa->nodes[node].accept_mb)
1298 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1303 int subexp_idx = dfa->nodes[node].opr.idx + 1;
1324 dest_node = dfa->edests[node].elems[0];
1332 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1334 int dest_node = dfa->nexts[node];
1399 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1421 cur_node = dfa->init_node;
1440 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1520 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1523 int type = dfa->nodes[cur_node].type;
1526 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1537 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1550 if (dfa->nodes[cur_node].opt_subexp
1653 const re_dfa_t *const dfa = mctx->dfa;
1671 re_token_type_t type = dfa->nodes[prev_node].type;
1676 if (dfa->nodes[prev_node].accept_mb)
1684 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1686 dfa->nexts[prev_node]))
1696 dfa->nexts[prev_node], to_idx,
1737 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1753 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1768 const re_dfa_t *const dfa = mctx->dfa;
1782 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1789 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1796 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1812 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1818 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1829 dfa->inveclosures + dest_nodes->elems[i]);
1837 sub_epsilon_src_nodes (const re_dfa_t *dfa, int node, re_node_set *dest_nodes,
1842 re_node_set *inv_eclosure = dfa->inveclosures + node;
1850 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1852 int edst1 = dfa->edests[cur_node].elems[0];
1853 int edst2 = ((dfa->edests[cur_node].nelem > 1)
1854 ? dfa->edests[cur_node].elems[1] : -1);
1862 dfa->inveclosures + cur_node);
1889 const re_dfa_t *const dfa = mctx->dfa;
1899 subexp_idx = dfa->nodes[ent->node].opr.idx;
1925 const re_dfa_t *const dfa = mctx->dfa;
1926 const re_node_set *eclosures = dfa->eclosures + from_node;
1934 switch (dfa->nodes[node].type)
1958 dst = dfa->edests[node].elems[0];
1984 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
1989 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2033 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2049 subexp_idx = dfa->nodes[ent->node].opr.idx;
2057 re_token_type_t type = dfa->nodes[node].type;
2059 && subexp_idx == dfa->nodes[node].opr.idx)
2062 && subexp_idx == dfa->nodes[node].opr.idx)
2070 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2081 if (!re_node_set_contains (dfa->inveclosures + node,
2083 && !re_node_set_contains (dfa->eclosures + node,
2088 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2101 re_token_type_t type = dfa->nodes[node].type;
2104 if (subexp_idx != dfa->nodes[node].opr.idx)
2108 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2124 const re_dfa_t *const dfa = mctx->dfa;
2141 type = dfa->nodes[node].type;
2162 dst_node = (subexp_len ? dfa->nexts[node]
2163 : dfa->edests[node].elems[0]);
2193 err = merge_state_array (dfa, sctx->limited_states,
2224 const re_dfa_t *const dfa = mctx->dfa;
2227 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2230 dfa->nexts[node_idx]))
2297 if (!build_trtable (mctx->dfa, state))
2313 const re_dfa_t *const dfa = mctx->dfa;
2353 = re_acquire_state_context (err, dfa, &next_nodes, context);
2361 if (BE (dfa->nbackref, 0) && next_state != NULL)
2423 const re_dfa_t *const dfa = mctx->dfa;
2435 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2436 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2437 && (dfa->used_bkref_map
2438 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2456 const re_dfa_t *const dfa = mctx->dfa;
2468 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2471 dfa->eclosures + dfa->nexts[cur_node]);
2480 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2495 const re_dfa_t *const dfa = mctx->dfa;
2507 if (!dfa->nodes[cur_node_idx].accept_mb)
2510 if (dfa->nodes[cur_node_idx].constraint)
2515 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2521 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2534 assert (dfa->nexts[cur_node_idx] != -1);
2536 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2551 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2565 const re_dfa_t *const dfa = mctx->dfa;
2575 const re_token_t *node = dfa->nodes + node_idx;
2600 assert (dfa->nexts[node_idx] != -1);
2612 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2613 : dfa->eclosures + dfa->nexts[node_idx]);
2625 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2643 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2679 const re_dfa_t *const dfa = mctx->dfa;
2694 subexp_num = dfa->nodes[bkref_node].opr.idx;
2704 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2786 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2855 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2862 const re_token_t *node = dfa->nodes + cls_node;
2880 const re_dfa_t *const dfa = mctx->dfa;
2888 subexp_num = dfa->nodes[top_node].opr.idx;
2921 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2952 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2988 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3003 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3041 const re_dfa_t *const dfa = mctx->dfa;
3052 re_token_type_t type = dfa->nodes[cur_node].type;
3057 if (dfa->nodes[cur_node].accept_mb)
3059 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3064 int next_node = dfa->nexts[cur_node];
3083 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3095 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3097 result = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3117 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3135 const re_node_set *eclosure = dfa->eclosures + cur_node;
3136 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3150 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3170 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3178 if (dfa->nodes[cur_node].type == type
3179 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3192 if (dfa->edests[cur_node].nelem == 0)
3194 if (dfa->edests[cur_node].nelem == 2)
3196 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3197 dfa->edests[cur_node].elems[1],
3202 cur_node = dfa->edests[cur_node].elems[0];
3217 const re_dfa_t *const dfa = mctx->dfa;
3244 next_node = dfa->edests[ent->node].elems[0];
3248 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3264 next_node = dfa->nexts[ent->node];
3287 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3303 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3344 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3397 next_node = dfa->nexts[dests_node[i].elems[j]];
3400 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3405 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3412 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3417 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3420 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3457 if (dfa->word_char[i] & mask)
3530 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3545 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3559 if (dfa->mb_cur_max > 1)
3560 bitset_merge (accepts, dfa->sb_char);
3564 if (!(dfa->syntax & RE_DOT_NEWLINE))
3566 if (dfa->syntax & RE_DOT_NOT_NULL)
3573 if (!(dfa->syntax & RE_DOT_NEWLINE))
3575 if (dfa->syntax & RE_DOT_NOT_NULL)
3610 if (dfa->mb_cur_max > 1)
3612 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3616 any_set |= (accepts[j] &= dfa->word_char[j]);
3629 if (dfa->mb_cur_max > 1)
3631 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3635 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3710 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3720 check_node_accept_bytes (const re_dfa_t *dfa, int node_idx,
3723 const re_token_t *node = dfa->nodes + node_idx;
3786 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3788 ((dfa->syntax & RE_DOT_NOT_NULL) &&
4047 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4048 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))