Lines Matching refs:dfa
61 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
94 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
110 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
120 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
158 static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
169 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
173 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
181 static int build_trtable (const re_dfa_t *dfa,
184 static int check_node_accept_bytes (const re_dfa_t *dfa, int node_idx,
193 static int group_nodes_into_DFAstates (const re_dfa_t *dfa,
230 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
246 __libc_lock_lock (dfa->lock);
253 __libc_lock_unlock (dfa->lock);
418 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
428 __libc_lock_lock (dfa->lock);
492 __libc_lock_unlock (dfa->lock);
640 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
646 re_match_context_t mctx = { .dfa = dfa };
656 mctx.dfa = dfa;
663 if (BE (preg->used == 0 || dfa->init_state == NULL
664 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
665 || dfa->init_state_begbuf == NULL, 0))
676 if (dfa->init_state->nodes.nelem == 0
677 && dfa->init_state_word->nodes.nelem == 0
678 && (dfa->init_state_nl->nodes.nelem == 0
687 fl_longest_match = (nmatch != 0 || dfa->nbackref);
689 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
690 preg->translate, preg->syntax & RE_ICASE, dfa);
697 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
701 /* We will log all the DFA states through which the dfa pass,
702 if nmatch > 1, or this dfa has "multibyte node", which is a
705 if (nmatch > 1 || dfa->has_mb_node)
732 sb = dfa->mb_cur_max == 1;
857 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
863 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
864 || dfa->nbackref)
902 dfa->has_plural_match && dfa->nbackref > 0);
937 if (dfa->subexp_map)
939 if (dfa->subexp_map[reg_idx] != reg_idx)
942 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
944 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
950 if (dfa->nbackref)
961 const re_dfa_t *const dfa = mctx->dfa;
983 if (dfa->nbackref)
1017 ret = merge_state_array (dfa, sifted_states, lim_states,
1058 const re_dfa_t *const dfa = mctx->dfa;
1059 if (dfa->init_state->has_constraint)
1064 return dfa->init_state_word;
1066 return dfa->init_state;
1068 return dfa->init_state_begbuf;
1070 return dfa->init_state_nl;
1074 return re_acquire_state_context (err, dfa,
1075 dfa->init_state->entrance_nodes,
1080 return dfa->init_state;
1083 return dfa->init_state;
1100 const re_dfa_t *const dfa = mctx->dfa;
1124 if (BE (dfa->nbackref, 0))
1230 check_halt_node_context (const re_dfa_t *dfa, int node, unsigned int context)
1232 re_token_type_t type = dfa->nodes[node].type;
1233 unsigned int constraint = dfa->nodes[node].constraint;
1259 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1275 const re_dfa_t *const dfa = mctx->dfa;
1277 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1280 re_node_set *edests = &dfa->edests[node];
1316 re_token_type_t type = dfa->nodes[node].type;
1319 if (dfa->nodes[node].accept_mb)
1320 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1325 int subexp_idx = dfa->nodes[node].opr.idx + 1;
1346 dest_node = dfa->edests[node].elems[0];
1354 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1356 int dest_node = dfa->nexts[node];
1421 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1443 cur_node = dfa->init_node;
1462 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1542 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1545 int type = dfa->nodes[cur_node].type;
1548 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1559 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1572 if (dfa->nodes[cur_node].opt_subexp
1675 const re_dfa_t *const dfa = mctx->dfa;
1693 re_token_type_t type = dfa->nodes[prev_node].type;
1698 if (dfa->nodes[prev_node].accept_mb)
1706 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1708 dfa->nexts[prev_node]))
1718 dfa->nexts[prev_node], to_idx,
1760 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1776 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1791 const re_dfa_t *const dfa = mctx->dfa;
1805 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1812 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1819 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1835 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1841 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1853 dfa->inveclosures + dest_nodes->elems[i]);
1864 sub_epsilon_src_nodes (const re_dfa_t *dfa, int node, re_node_set *dest_nodes,
1869 re_node_set *inv_eclosure = dfa->inveclosures + node;
1877 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1879 int edst1 = dfa->edests[cur_node].elems[0];
1880 int edst2 = ((dfa->edests[cur_node].nelem > 1)
1881 ? dfa->edests[cur_node].elems[1] : -1);
1889 dfa->inveclosures + cur_node);
1916 const re_dfa_t *const dfa = mctx->dfa;
1926 subexp_idx = dfa->nodes[ent->node].opr.idx;
1952 const re_dfa_t *const dfa = mctx->dfa;
1953 const re_node_set *eclosures = dfa->eclosures + from_node;
1961 switch (dfa->nodes[node].type)
1985 dst = dfa->edests[node].elems[0];
2011 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2016 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2060 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2076 subexp_idx = dfa->nodes[ent->node].opr.idx;
2084 re_token_type_t type = dfa->nodes[node].type;
2086 && subexp_idx == dfa->nodes[node].opr.idx)
2089 && subexp_idx == dfa->nodes[node].opr.idx)
2097 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2108 if (!re_node_set_contains (dfa->inveclosures + node,
2110 && !re_node_set_contains (dfa->eclosures + node,
2115 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2128 re_token_type_t type = dfa->nodes[node].type;
2131 if (subexp_idx != dfa->nodes[node].opr.idx)
2135 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2151 const re_dfa_t *const dfa = mctx->dfa;
2168 type = dfa->nodes[node].type;
2189 dst_node = (subexp_len ? dfa->nexts[node]
2190 : dfa->edests[node].elems[0]);
2220 err = merge_state_array (dfa, sctx->limited_states,
2251 const re_dfa_t *const dfa = mctx->dfa;
2254 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2257 dfa->nexts[node_idx]))
2324 if (!build_trtable (mctx->dfa, state))
2340 const re_dfa_t *const dfa = mctx->dfa;
2380 = re_acquire_state_context (err, dfa, &next_nodes, context);
2388 if (BE (dfa->nbackref, 0) && next_state != NULL)
2450 const re_dfa_t *const dfa = mctx->dfa;
2462 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2463 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2464 && (dfa->used_bkref_map
2465 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2483 const re_dfa_t *const dfa = mctx->dfa;
2495 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2498 dfa->eclosures + dfa->nexts[cur_node]);
2507 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2522 const re_dfa_t *const dfa = mctx->dfa;
2534 if (!dfa->nodes[cur_node_idx].accept_mb)
2537 if (dfa->nodes[cur_node_idx].constraint)
2542 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2548 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2561 assert (dfa->nexts[cur_node_idx] != -1);
2563 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2578 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2592 const re_dfa_t *const dfa = mctx->dfa;
2602 const re_token_t *node = dfa->nodes + node_idx;
2627 assert (dfa->nexts[node_idx] != -1);
2639 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2640 : dfa->eclosures + dfa->nexts[node_idx]);
2652 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2670 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2706 const re_dfa_t *const dfa = mctx->dfa;
2721 subexp_num = dfa->nodes[bkref_node].opr.idx;
2731 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2813 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2882 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2889 const re_token_t *node = dfa->nodes + cls_node;
2907 const re_dfa_t *const dfa = mctx->dfa;
2915 subexp_num = dfa->nodes[top_node].opr.idx;
2948 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2979 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3015 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3030 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3068 const re_dfa_t *const dfa = mctx->dfa;
3079 re_token_type_t type = dfa->nodes[cur_node].type;
3084 if (dfa->nodes[cur_node].accept_mb)
3086 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3091 int next_node = dfa->nexts[cur_node];
3110 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3122 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3124 result = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3144 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3162 const re_node_set *eclosure = dfa->eclosures + cur_node;
3163 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3177 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3197 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3205 if (dfa->nodes[cur_node].type == type
3206 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3219 if (dfa->edests[cur_node].nelem == 0)
3221 if (dfa->edests[cur_node].nelem == 2)
3223 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3224 dfa->edests[cur_node].elems[1],
3229 cur_node = dfa->edests[cur_node].elems[0];
3244 const re_dfa_t *const dfa = mctx->dfa;
3271 next_node = dfa->edests[ent->node].elems[0];
3275 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3291 next_node = dfa->nexts[ent->node];
3314 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3330 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3371 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3433 next_node = dfa->nexts[dests_node[i].elems[j]];
3436 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3441 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3448 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3453 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3456 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3493 if (dfa->word_char[i] & mask)
3566 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3581 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3595 if (dfa->mb_cur_max > 1)
3596 bitset_merge (accepts, dfa->sb_char);
3600 if (!(dfa->syntax & RE_DOT_NEWLINE))
3602 if (dfa->syntax & RE_DOT_NOT_NULL)
3609 if (!(dfa->syntax & RE_DOT_NEWLINE))
3611 if (dfa->syntax & RE_DOT_NOT_NULL)
3646 if (dfa->mb_cur_max > 1)
3648 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3652 any_set |= (accepts[j] &= dfa->word_char[j]);
3665 if (dfa->mb_cur_max > 1)
3667 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3671 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3746 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3756 check_node_accept_bytes (const re_dfa_t *dfa, int node_idx,
3759 const re_token_t *node = dfa->nodes + node_idx;
3822 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3824 ((dfa->syntax & RE_DOT_NOT_NULL) &&
4083 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4084 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))