diff options
Diffstat (limited to 'posix/regexec.c')
| -rw-r--r-- | posix/regexec.c | 101 |
1 files changed, 57 insertions, 44 deletions
diff --git a/posix/regexec.c b/posix/regexec.c index f7b4f9c..83e9aaf 100644 --- a/posix/regexec.c +++ b/posix/regexec.c @@ -59,7 +59,7 @@ static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch, Idx cur_idx, Idx nmatch); static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node, Idx nregs, - regmatch_t *regs, + regmatch_t *regs, regmatch_t *prevregs, re_node_set *eps_via_nodes); static reg_errcode_t set_regs (const regex_t *preg, const re_match_context_t *mctx, @@ -186,11 +186,12 @@ static reg_errcode_t extend_buffers (re_match_context_t *mctx, int min_len); REG_NOTBOL is set, then ^ does not match at the beginning of the string; if REG_NOTEOL is set, then $ does not match at the end. - We return 0 if we find a match and REG_NOMATCH if not. */ + Return 0 if a match is found, REG_NOMATCH if not, REG_BADPAT if + EFLAGS is invalid. */ int regexec (const regex_t *__restrict preg, const char *__restrict string, - size_t nmatch, regmatch_t pmatch[], int eflags) + size_t nmatch, regmatch_t pmatch[_REGEX_NELTS (nmatch)], int eflags) { reg_errcode_t err; Idx start, length; @@ -234,7 +235,7 @@ int attribute_compat_text_section __compat_regexec (const regex_t *__restrict preg, const char *__restrict string, size_t nmatch, - regmatch_t pmatch[], int eflags) + regmatch_t pmatch[_REGEX_NELTS (nmatch)], int eflags) { return regexec (preg, string, nmatch, pmatch, eflags & (REG_NOTBOL | REG_NOTEOL)); @@ -269,8 +270,8 @@ compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0); strings.) On success, re_match* functions return the length of the match, re_search* - return the position of the start of the match. Return value -1 means no - match was found and -2 indicates an internal error. */ + return the position of the start of the match. They return -1 on + match failure, -2 on error. */ regoff_t re_match (struct re_pattern_buffer *bufp, const char *string, Idx length, @@ -1206,27 +1207,30 @@ check_halt_state_context (const re_match_context_t *mctx, /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA corresponding to the DFA). Return the destination node, and update EPS_VIA_NODES; - return -1 in case of errors. */ + return -1 on match failure, -2 on error. */ static Idx proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs, + regmatch_t *prevregs, Idx *pidx, Idx node, re_node_set *eps_via_nodes, struct re_fail_stack_t *fs) { const re_dfa_t *const dfa = mctx->dfa; - Idx i; - bool ok; if (IS_EPSILON_NODE (dfa->nodes[node].type)) { re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes; re_node_set *edests = &dfa->edests[node]; - Idx dest_node; - ok = re_node_set_insert (eps_via_nodes, node); - if (__glibc_unlikely (! ok)) - return -2; - /* Pick up a valid destination, or return -1 if none - is found. */ - for (dest_node = -1, i = 0; i < edests->nelem; ++i) + + if (! re_node_set_contains (eps_via_nodes, node)) + { + bool ok = re_node_set_insert (eps_via_nodes, node); + if (__glibc_unlikely (! ok)) + return -2; + } + + /* Pick a valid destination, or return -1 if none is found. */ + Idx dest_node = -1; + for (Idx i = 0; i < edests->nelem; i++) { Idx candidate = edests->elems[i]; if (!re_node_set_contains (cur_nodes, candidate)) @@ -1244,7 +1248,7 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs, /* 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)) + prevregs, eps_via_nodes)) return -2; /* We know we are going to exit. */ @@ -1288,7 +1292,7 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs, if (naccepted == 0) { Idx dest_node; - ok = re_node_set_insert (eps_via_nodes, node); + bool ok = re_node_set_insert (eps_via_nodes, node); if (__glibc_unlikely (! ok)) return -2; dest_node = dfa->edests[node].elems[0]; @@ -1317,7 +1321,8 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs, static reg_errcode_t __attribute_warn_unused_result__ push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node, - Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes) + Idx nregs, regmatch_t *regs, regmatch_t *prevregs, + re_node_set *eps_via_nodes) { reg_errcode_t err; Idx num = fs->num++; @@ -1333,25 +1338,30 @@ push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node, } fs->stack[num].idx = str_idx; fs->stack[num].node = dest_node; - fs->stack[num].regs = re_malloc (regmatch_t, nregs); + fs->stack[num].regs = re_malloc (regmatch_t, 2 * nregs); if (fs->stack[num].regs == NULL) return REG_ESPACE; memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs); + memcpy (fs->stack[num].regs + nregs, prevregs, sizeof (regmatch_t) * nregs); err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes); return err; } static Idx pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs, - regmatch_t *regs, re_node_set *eps_via_nodes) + regmatch_t *regs, regmatch_t *prevregs, + re_node_set *eps_via_nodes) { + if (fs == NULL || fs->num == 0) + return -1; Idx num = --fs->num; - DEBUG_ASSERT (num >= 0); *pidx = fs->stack[num].idx; memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs); + memcpy (prevregs, fs->stack[num].regs + nregs, sizeof (regmatch_t) * nregs); re_node_set_free (eps_via_nodes); re_free (fs->stack[num].regs); *eps_via_nodes = fs->stack[num].eps_via_nodes; + DEBUG_ASSERT (0 <= fs->stack[num].node); return fs->stack[num].node; } @@ -1407,33 +1417,32 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch, { update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch); - if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node) + if ((idx == pmatch[0].rm_eo && cur_node == mctx->last_node) + || (fs && re_node_set_contains (&eps_via_nodes, cur_node))) { Idx reg_idx; + cur_node = -1; if (fs) { for (reg_idx = 0; reg_idx < nmatch; ++reg_idx) if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1) - break; - if (reg_idx == nmatch) - { - re_node_set_free (&eps_via_nodes); - regmatch_list_free (&prev_match); - return free_fail_stack_return (fs); - } - cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, - &eps_via_nodes); + { + cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, + prev_idx_match, &eps_via_nodes); + break; + } } - else + if (cur_node < 0) { re_node_set_free (&eps_via_nodes); regmatch_list_free (&prev_match); - return REG_NOERROR; + return free_fail_stack_return (fs); } } /* Proceed to next node. */ - cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node, + cur_node = proceed_next_node (mctx, nmatch, pmatch, prev_idx_match, + &idx, cur_node, &eps_via_nodes, fs); if (__glibc_unlikely (cur_node < 0)) @@ -1445,13 +1454,13 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch, free_fail_stack_return (fs); return REG_ESPACE; } - if (fs) - cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, - &eps_via_nodes); - else + cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, + prev_idx_match, &eps_via_nodes); + if (cur_node < 0) { re_node_set_free (&eps_via_nodes); regmatch_list_free (&prev_match); + free_fail_stack_return (fs); return REG_NOMATCH; } } @@ -1495,10 +1504,10 @@ update_regs (const re_dfa_t *dfa, regmatch_t *pmatch, } else if (type == OP_CLOSE_SUBEXP) { + /* We are at the last node of this sub expression. */ Idx reg_num = dfa->nodes[cur_node].opr.idx + 1; if (reg_num < nmatch) { - /* We are at the last node of this sub expression. */ if (pmatch[reg_num].rm_so < cur_idx) { pmatch[reg_num].rm_eo = cur_idx; @@ -2195,6 +2204,7 @@ sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx, /* Return the next state to which the current state STATE will transit by accepting the current input byte, and update STATE_LOG if necessary. + Return NULL on failure. If STATE can accept a multibyte char/collating element/back reference update the destination of STATE_LOG. */ @@ -2395,7 +2405,7 @@ check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes, #if 0 /* Return the next state to which the current state STATE will transit by - accepting the current input byte. */ + accepting the current input byte. Return NULL on failure. */ static re_dfastate_t * transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx, @@ -2817,7 +2827,8 @@ find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes, /* Check whether the node TOP_NODE at TOP_STR can arrive to the node LAST_NODE at LAST_STR. We record the path onto PATH since it will be heavily reused. - Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */ + Return REG_NOERROR if it can arrive, REG_NOMATCH if it cannot, + REG_ESPACE if memory is exhausted. */ static reg_errcode_t __attribute_warn_unused_result__ @@ -3433,7 +3444,8 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state) /* Group all nodes belonging to STATE into several destinations. Then for all destinations, set the nodes belonging to the destination to DESTS_NODE[i] and set the characters accepted by the destination - to DEST_CH[i]. This function return the number of destinations. */ + to DEST_CH[i]. Return the number of destinations if successful, + -1 on internal error. */ static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state, @@ -4211,7 +4223,8 @@ match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx) } /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches - at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */ + at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. + Return the new entry if successful, NULL if memory is exhausted. */ static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx) |