aboutsummaryrefslogtreecommitdiff
path: root/posix/regexec.c
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2004-03-04 23:28:06 +0000
committerUlrich Drepper <drepper@redhat.com>2004-03-04 23:28:06 +0000
commit4c595adb603a70901433026153e1ff34979ed173 (patch)
tree633a67374b3d023b08f949b4156ca75893089bc6 /posix/regexec.c
parentf2fcb018ad4fe9a6cdb7b984d9ace36c39a67882 (diff)
downloadglibc-4c595adb603a70901433026153e1ff34979ed173.zip
glibc-4c595adb603a70901433026153e1ff34979ed173.tar.gz
glibc-4c595adb603a70901433026153e1ff34979ed173.tar.bz2
Update.
2004-02-29 Paolo Bonzini <bonzini@gnu.org> * posix/regexec.c (transit_state): Don't handle state == NULL. Move state log and backreference management... (merge_state_with_log): ... to this function. (find_recover_state): New function. (check_matching): Use find_recover_state to get a non-NULL state when an invalid state is reached. Compute the amount of initial characters to be skipped less conservatively when multi-byte character sets are in use. Do not check dfa->nbackref if the state log is NULL. Initialize err. (acquire_init_state_context): Expect err to be initialized. Fix spacing. 2004-03-05 Jakub Jelinek <jakub@redhat.com> * sysdeps/sparc/sparc32/elf/start.S: Handle PIEs. * sysdeps/sparc/sparc64/elf/start.S: Likewise.
Diffstat (limited to 'posix/regexec.c')
-rw-r--r--posix/regexec.c295
1 files changed, 161 insertions, 134 deletions
diff --git a/posix/regexec.c b/posix/regexec.c
index be361cf..cad676c 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -123,9 +123,14 @@ static reg_errcode_t clean_state_log_if_needed (re_match_context_t *mctx,
int next_state_log_idx) internal_function;
static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst,
re_dfastate_t **src, int num) internal_function;
+static re_dfastate_t *find_recover_state (reg_errcode_t *err,
+ re_match_context_t *mctx) internal_function;
static re_dfastate_t *transit_state (reg_errcode_t *err,
re_match_context_t *mctx,
re_dfastate_t *state) internal_function;
+static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
+ re_match_context_t *mctx,
+ re_dfastate_t *next_state) internal_function;
static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
re_node_set *cur_nodes,
int str_idx) internal_function;
@@ -936,7 +941,6 @@ acquire_init_state_context (err, mctx, idx)
int idx;
{
re_dfa_t *const dfa = mctx->dfa;
- *err = REG_NOERROR;
if (dfa->init_state->has_constraint)
{
unsigned int context;
@@ -952,9 +956,9 @@ acquire_init_state_context (err, mctx, idx)
else if (IS_BEGBUF_CONTEXT (context))
{
/* It is relatively rare case, then calculate on demand. */
- return re_acquire_state_context (err, dfa,
- dfa->init_state->entrance_nodes,
- context);
+ return re_acquire_state_context (err, dfa,
+ dfa->init_state->entrance_nodes,
+ context);
}
else
/* Must not happen? */
@@ -985,29 +989,37 @@ check_matching (mctx, fl_longest_match, p_match_first)
int match_last = -1;
int cur_str_idx = re_string_cur_idx (&mctx->input);
re_dfastate_t *cur_state;
- int at_init_state = p_match_first != NULL, skipped = 0;
+ int at_init_state = p_match_first != NULL;
+ int next_start_idx = cur_str_idx;
+ err = REG_NOERROR;
cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
- /* An initial state must not be NULL(invalid state). */
+ /* An initial state must not be NULL (invalid). */
if (BE (cur_state == NULL, 0))
- return -2;
- if (mctx->state_log != NULL)
- mctx->state_log[cur_str_idx] = cur_state;
+ {
+ assert (err == REG_ESPACE);
+ return -2;
+ }
- /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
- later. E.g. Processing back references. */
- if (BE (dfa->nbackref, 0))
+ if (mctx->state_log != NULL)
{
- at_init_state = 0;
- err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
- if (BE (err != REG_NOERROR, 0))
- return err;
+ mctx->state_log[cur_str_idx] = cur_state;
- if (cur_state->has_backref)
+ /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
+ later. E.g. Processing back references. */
+ if (BE (dfa->nbackref, 0))
{
- err = transit_state_bkref (mctx, &cur_state->nodes);
+ at_init_state = 0;
+ err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
if (BE (err != REG_NOERROR, 0))
return err;
+
+ if (cur_state->has_backref)
+ {
+ err = transit_state_bkref (mctx, &cur_state->nodes);
+ if (BE (err != REG_NOERROR, 0))
+ return err;
+ }
}
}
@@ -1031,40 +1043,34 @@ check_matching (mctx, fl_longest_match, p_match_first)
{
re_dfastate_t *old_state = cur_state;
cur_state = transit_state (&err, mctx, cur_state);
- if (at_init_state)
- {
- if (old_state == cur_state)
- skipped++;
- else
- at_init_state = 0;
- }
+ if (mctx->state_log != NULL)
+ cur_state = merge_state_with_log (&err, mctx, cur_state);
- if (cur_state == NULL) /* Reached at the invalid state or an error. */
+ if (cur_state == NULL)
{
- cur_str_idx = re_string_cur_idx (&mctx->input);
+ /* Reached the invalid state or an error. Try to recover a valid
+ state using the state log, if available and if we have not
+ already found a valid (even if not the longest) match. */
if (BE (err != REG_NOERROR, 0))
return -2;
- if (!fl_longest_match && match)
+
+ if (mctx->state_log == NULL
+ || (match && !fl_longest_match)
+ || (cur_state = find_recover_state (&err, mctx)) == NULL)
break;
+ }
+
+ if (at_init_state)
+ {
+ if (old_state == cur_state)
+ next_start_idx = re_string_cur_idx (&mctx->input);
else
- {
- if (mctx->state_log == NULL)
- break;
- else
- {
- int max = mctx->state_log_top;
- for (; cur_str_idx <= max; ++cur_str_idx)
- if (mctx->state_log[cur_str_idx] != NULL)
- break;
- if (cur_str_idx > max)
- break;
- }
- }
+ at_init_state = 0;
}
- if (cur_state != NULL && cur_state->halt)
+ if (cur_state->halt)
{
- /* Reached at a halt state.
+ /* Reached a halt state.
Check the halt state can satisfy the current context. */
if (!cur_state->has_constraint
|| check_halt_state_context (mctx, cur_state,
@@ -1079,8 +1085,8 @@ check_matching (mctx, fl_longest_match, p_match_first)
}
}
- if (match_last == -1 && skipped)
- *p_match_first += skipped;
+ if (match_last == -1 && p_match_first)
+ *p_match_first += next_start_idx;
return match_last;
}
@@ -2134,7 +2140,6 @@ transit_state (err, mctx, state)
re_dfa_t *const dfa = mctx->dfa;
re_dfastate_t **trtable, *next_state;
unsigned char ch;
- int cur_idx;
if (re_string_cur_idx (&mctx->input) + 1 >= mctx->input.bufs_len
|| (re_string_cur_idx (&mctx->input) + 1 >= mctx->input.valid_len
@@ -2145,14 +2150,6 @@ transit_state (err, mctx, state)
return NULL;
}
- *err = REG_NOERROR;
- if (state == NULL)
- {
- next_state = state;
- re_string_skip_bytes (&mctx->input, 1);
- }
- else
- {
#ifdef RE_ENABLE_I18N
/* If the current state can accept multibyte. */
if (state->accept_mb)
@@ -2163,95 +2160,96 @@ transit_state (err, mctx, state)
}
#endif /* RE_ENABLE_I18N */
- /* Then decide the next state with the single byte. */
- if (1)
- {
- /* Use transition table */
- ch = re_string_fetch_byte (&mctx->input);
- trtable = state->trtable;
- if (trtable == NULL)
- {
- trtable = build_trtable (dfa, state);
- if (trtable == NULL)
- {
- *err = REG_ESPACE;
- return NULL;
- }
- }
- if (BE (state->word_trtable, 0))
+ /* Then decide the next state with the single byte. */
+ if (1)
+ {
+ /* Use transition table */
+ ch = re_string_fetch_byte (&mctx->input);
+ trtable = state->trtable;
+ if (trtable == NULL)
+ {
+ trtable = build_trtable (dfa, state);
+ if (trtable == NULL)
{
- unsigned int context;
- context
- = re_string_context_at (&mctx->input,
- re_string_cur_idx (&mctx->input) - 1,
- mctx->eflags);
- if (IS_WORD_CONTEXT (context))
- next_state = trtable[ch + SBC_MAX];
- else
- next_state = trtable[ch];
+ *err = REG_ESPACE;
+ return NULL;
}
+ }
+ if (BE (state->word_trtable, 0))
+ {
+ unsigned int context;
+ context
+ = re_string_context_at (&mctx->input,
+ re_string_cur_idx (&mctx->input) - 1,
+ mctx->eflags);
+ if (IS_WORD_CONTEXT (context))
+ return trtable[ch + SBC_MAX];
else
- next_state = trtable[ch];
+ return trtable[ch];
}
-#if 0
else
- {
- /* don't use transition table */
- next_state = transit_state_sb (err, mctx, state);
- if (BE (next_state == NULL && *err != REG_NOERROR, 0))
- return NULL;
- }
-#endif
+ return trtable[ch];
}
+#if 0
+ else
+ /* don't use transition table */
+ return transit_state_sb (err, mctx, state);
+#endif
+}
- cur_idx = re_string_cur_idx (&mctx->input);
- /* Update the state_log if we need. */
- if (mctx->state_log != NULL)
+/* Update the state_log if we need */
+re_dfastate_t *
+merge_state_with_log (err, mctx, next_state)
+ reg_errcode_t *err;
+ re_match_context_t *mctx;
+ re_dfastate_t *next_state;
+{
+ re_dfa_t *const dfa = mctx->dfa;
+ int cur_idx = re_string_cur_idx (&mctx->input);
+
+ if (cur_idx > mctx->state_log_top)
{
- if (cur_idx > mctx->state_log_top)
- {
- mctx->state_log[cur_idx] = next_state;
- mctx->state_log_top = cur_idx;
- }
- else if (mctx->state_log[cur_idx] == 0)
- {
- mctx->state_log[cur_idx] = next_state;
- }
- else
- {
- re_dfastate_t *pstate;
- unsigned int context;
- re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
- /* If (state_log[cur_idx] != 0), it implies that cur_idx is
- the destination of a multibyte char/collating element/
- back reference. Then the next state is the union set of
- these destinations and the results of the transition table. */
- pstate = mctx->state_log[cur_idx];
- log_nodes = pstate->entrance_nodes;
- if (next_state != NULL)
- {
- table_nodes = next_state->entrance_nodes;
- *err = re_node_set_init_union (&next_nodes, table_nodes,
+ mctx->state_log[cur_idx] = next_state;
+ mctx->state_log_top = cur_idx;
+ }
+ else if (mctx->state_log[cur_idx] == 0)
+ {
+ mctx->state_log[cur_idx] = next_state;
+ }
+ else
+ {
+ re_dfastate_t *pstate;
+ unsigned int context;
+ re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
+ /* If (state_log[cur_idx] != 0), it implies that cur_idx is
+ the destination of a multibyte char/collating element/
+ back reference. Then the next state is the union set of
+ these destinations and the results of the transition table. */
+ pstate = mctx->state_log[cur_idx];
+ log_nodes = pstate->entrance_nodes;
+ if (next_state != NULL)
+ {
+ table_nodes = next_state->entrance_nodes;
+ *err = re_node_set_init_union (&next_nodes, table_nodes,
log_nodes);
- if (BE (*err != REG_NOERROR, 0))
- return NULL;
- }
- else
- next_nodes = *log_nodes;
- /* Note: We already add the nodes of the initial state,
- then we don't need to add them here. */
-
- context = re_string_context_at (&mctx->input,
- re_string_cur_idx (&mctx->input) - 1,
- mctx->eflags);
- next_state = mctx->state_log[cur_idx]
- = re_acquire_state_context (err, dfa, &next_nodes, context);
- /* We don't need to check errors here, since the return value of
- this function is next_state and ERR is already set. */
-
- if (table_nodes != NULL)
- re_node_set_free (&next_nodes);
- }
+ if (BE (*err != REG_NOERROR, 0))
+ return NULL;
+ }
+ else
+ next_nodes = *log_nodes;
+ /* Note: We already add the nodes of the initial state,
+ then we don't need to add them here. */
+
+ context = re_string_context_at (&mctx->input,
+ re_string_cur_idx (&mctx->input) - 1,
+ mctx->eflags);
+ next_state = mctx->state_log[cur_idx]
+ = re_acquire_state_context (err, dfa, &next_nodes, context);
+ /* We don't need to check errors here, since the return value of
+ this function is next_state and ERR is already set. */
+
+ if (table_nodes != NULL)
+ re_node_set_free (&next_nodes);
}
if (BE (dfa->nbackref, 0) && next_state != NULL)
@@ -2273,9 +2271,38 @@ transit_state (err, mctx, state)
next_state = mctx->state_log[cur_idx];
}
}
+
return next_state;
}
+/* Skip bytes in the input that correspond to part of a
+ multi-byte match, then look in the log for a state
+ from which to restart matching. */
+re_dfastate_t *
+find_recover_state (err, mctx)
+ reg_errcode_t *err;
+ re_match_context_t *mctx;
+{
+ re_dfastate_t *cur_state = NULL;
+ do
+ {
+ int max = mctx->state_log_top;
+ int cur_str_idx = re_string_cur_idx (&mctx->input);
+
+ do
+ {
+ if (++cur_str_idx > max)
+ return NULL;
+ re_string_skip_bytes (&mctx->input, 1);
+ }
+ while (mctx->state_log[cur_str_idx] == NULL);
+
+ cur_state = merge_state_with_log (err, mctx, NULL);
+ }
+ while (err == REG_NOERROR && cur_state == NULL);
+ return cur_state;
+}
+
/* Helper functions for transit_state. */
/* From the node set CUR_NODES, pick up the nodes whose types are