summaryrefslogtreecommitdiff
path: root/posix/regexec.c
diff options
context:
space:
mode:
Diffstat (limited to 'posix/regexec.c')
-rw-r--r--posix/regexec.c138
1 files changed, 81 insertions, 57 deletions
diff --git a/posix/regexec.c b/posix/regexec.c
index 22b806439b..91b48dd4a2 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -73,7 +73,7 @@ static int proceed_next_node (const re_match_context_t *mctx,
int *pidx, int node, re_node_set *eps_via_nodes,
struct re_fail_stack_t *fs) internal_function;
static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
- int str_idx, int *dests, int nregs,
+ int str_idx, int dest_node, int nregs,
regmatch_t *regs,
re_node_set *eps_via_nodes) internal_function;
static int pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs,
@@ -1223,30 +1223,38 @@ proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs)
if (IS_EPSILON_NODE (dfa->nodes[node].type))
{
re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
- int ndest, dest_nodes[2];
+ re_node_set *edests = &dfa->edests[node];
+ int dest_node;
err = re_node_set_insert (eps_via_nodes, node);
if (BE (err < 0, 0))
return -2;
- /* Pick up valid destinations. */
- for (ndest = 0, i = 0; i < dfa->edests[node].nelem; ++i)
+ /* Pick up a valid destination, or return -1 if none is found. */
+ for (dest_node = -1, i = 0; i < edests->nelem; ++i)
{
- int candidate = dfa->edests[node].elems[i];
+ int candidate = edests->elems[i];
if (!re_node_set_contains (cur_nodes, candidate))
continue;
- dest_nodes[0] = (ndest == 0) ? candidate : dest_nodes[0];
- dest_nodes[1] = (ndest == 1) ? candidate : dest_nodes[1];
- ++ndest;
+ if (dest_node == -1)
+ dest_node = candidate;
+
+ else
+ {
+ /* In order to avoid infinite loop like "(a*)*", return the second
+ epsilon-transition if the first was already considered. */
+ if (re_node_set_contains (eps_via_nodes, dest_node))
+ return candidate;
+
+ /* Otherwise, push the second epsilon-transition on the fail stack. */
+ else if (fs != NULL
+ && push_fail_stack (fs, *pidx, candidate, nregs, regs,
+ eps_via_nodes))
+ return -2;
+
+ /* We know we are going to exit. */
+ break;
+ }
}
- if (ndest <= 1)
- return ndest == 0 ? -1 : (ndest == 1 ? dest_nodes[0] : 0);
- /* In order to avoid infinite loop like "(a*)*". */
- if (re_node_set_contains (eps_via_nodes, dest_nodes[0]))
- return dest_nodes[1];
- if (fs != NULL
- && push_fail_stack (fs, *pidx, dest_nodes, nregs, regs,
- eps_via_nodes))
- return -2;
- return dest_nodes[0];
+ return dest_node;
}
else
{
@@ -1304,9 +1312,9 @@ proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs)
}
static reg_errcode_t
-push_fail_stack (fs, str_idx, dests, nregs, regs, eps_via_nodes)
+push_fail_stack (fs, str_idx, dest_node, nregs, regs, eps_via_nodes)
struct re_fail_stack_t *fs;
- int str_idx, *dests, nregs;
+ int str_idx, dest_node, nregs;
regmatch_t *regs;
re_node_set *eps_via_nodes;
{
@@ -1323,7 +1331,7 @@ push_fail_stack (fs, str_idx, dests, nregs, regs, eps_via_nodes)
fs->stack = new_array;
}
fs->stack[num].idx = str_idx;
- fs->stack[num].node = dests[1];
+ fs->stack[num].node = dest_node;
fs->stack[num].regs = re_malloc (regmatch_t, nregs);
if (fs->stack[num].regs == NULL)
return REG_ESPACE;
@@ -1600,7 +1608,7 @@ build_sifted_states (mctx, sctx, str_idx, cur_dest)
re_node_set *cur_dest;
{
re_dfa_t *const dfa = mctx->dfa;
- re_node_set *cur_src = &mctx->state_log[str_idx]->nodes;
+ re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
int i;
/* Then build the next sifted state.
@@ -1608,16 +1616,20 @@ build_sifted_states (mctx, sctx, str_idx, cur_dest)
`sifted_states[str_idx]' with `cur_dest'.
Note:
`cur_dest' is the sifted state from `state_log[str_idx + 1]'.
- `cur_src' points the node_set of the old `state_log[str_idx]'. */
+ `cur_src' points the node_set of the old `state_log[str_idx]'
+ (with the epsilon nodes pre-filtered out). */
for (i = 0; i < cur_src->nelem; i++)
{
int prev_node = cur_src->elems[i];
int naccepted = 0;
- re_token_type_t type = dfa->nodes[prev_node].type;
int ret;
- if (IS_EPSILON_NODE (type))
- continue;
+#if defined DEBUG || defined RE_ENABLE_I18N
+ re_token_type_t type = dfa->nodes[prev_node].type;
+#endif
+#ifdef DEBUG
+ assert (!IS_EPSILON_NODE (type));
+#endif
#ifdef RE_ENABLE_I18N
/* If the node may accept `multi byte'. */
if (ACCEPT_MB_NODE (type))
@@ -1764,26 +1776,24 @@ add_epsilon_src_nodes (dfa, dest_nodes, candidates)
re_node_set *dest_nodes;
const re_node_set *candidates;
{
- reg_errcode_t err;
- int src_idx;
- re_node_set src_copy;
+ reg_errcode_t err = REG_NOERROR;
+ int i;
- err = re_node_set_init_copy (&src_copy, dest_nodes);
+ re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
if (BE (err != REG_NOERROR, 0))
return err;
- for (src_idx = 0; src_idx < src_copy.nelem; ++src_idx)
+
+ if (!state->inveclosure.alloc)
{
- err = re_node_set_add_intersect (dest_nodes, candidates,
- dfa->inveclosures
- + src_copy.elems[src_idx]);
+ err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
if (BE (err != REG_NOERROR, 0))
- {
- re_node_set_free (&src_copy);
- return err;
- }
+ return REG_ESPACE;
+ for (i = 0; i < dest_nodes->nelem; i++)
+ re_node_set_merge (&state->inveclosure,
+ dfa->inveclosures + dest_nodes->elems[i]);
}
- re_node_set_free (&src_copy);
- return REG_NOERROR;
+ return re_node_set_add_intersect (dest_nodes, candidates,
+ &state->inveclosure);
}
static reg_errcode_t
@@ -2935,7 +2945,7 @@ check_arrival (mctx, path, top_node, top_str, last_node, last_str,
if (cur_state)
{
err = check_arrival_add_next_nodes (mctx, str_idx,
- &cur_state->nodes, &next_nodes);
+ &cur_state->non_eps_nodes, &next_nodes);
if (BE (err != REG_NOERROR, 0))
{
re_node_set_free (&next_nodes);
@@ -3009,9 +3019,12 @@ check_arrival_add_next_nodes (mctx, str_idx, cur_nodes, next_nodes)
{
int naccepted = 0;
int cur_node = cur_nodes->elems[cur_idx];
+#if defined DEBUG || defined RE_ENABLE_I18N
re_token_type_t type = dfa->nodes[cur_node].type;
- if (IS_EPSILON_NODE (type))
- continue;
+#endif
+#ifdef DEBUG
+ assert (!IS_EPSILON_NODE (type));
+#endif
#ifdef RE_ENABLE_I18N
/* If the node may accept `multi byte'. */
if (ACCEPT_MB_NODE (type))
@@ -3988,24 +4001,20 @@ check_node_accept (mctx, node, idx)
const re_token_t *node;
int idx;
{
- re_dfa_t *const dfa = mctx->dfa;
unsigned char ch;
- if (node->constraint)
- {
- /* The node has constraints. Check whether the current context
- satisfies the constraints. */
- unsigned int context = re_string_context_at (&mctx->input, idx,
- mctx->eflags);
- if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
- return 0;
- }
ch = re_string_byte_at (&mctx->input, idx);
switch (node->type)
{
case CHARACTER:
- return node->opr.c == ch;
+ if (node->opr.c != ch)
+ return 0;
+ break;
+
case SIMPLE_BRACKET:
- return bitset_contain (node->opr.sbcset, ch);
+ if (!bitset_contain (node->opr.sbcset, ch))
+ return 0;
+ break;
+
#ifdef RE_ENABLE_I18N
case OP_UTF8_PERIOD:
if (ch >= 0x80)
@@ -4013,11 +4022,26 @@ check_node_accept (mctx, node, idx)
/* FALLTHROUGH */
#endif
case OP_PERIOD:
- return !((ch == '\n' && !(dfa->syntax & RE_DOT_NEWLINE))
- || (ch == '\0' && (dfa->syntax & RE_DOT_NOT_NULL)));
+ if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
+ || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
+ return 0;
+ break;
+
default:
return 0;
}
+
+ if (node->constraint)
+ {
+ /* The node has constraints. Check whether the current context
+ satisfies the constraints. */
+ unsigned int context = re_string_context_at (&mctx->input, idx,
+ mctx->eflags);
+ if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
+ return 0;
+ }
+
+ return 1;
}
/* Extend the buffers, if the buffers have run out. */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-14 23:26:51 +0000