aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/nvim/regexp_nfa.c100
-rw-r--r--src/nvim/testdir/test_regexp_latin.vim6
2 files changed, 78 insertions, 28 deletions
diff --git a/src/nvim/regexp_nfa.c b/src/nvim/regexp_nfa.c
index a930fe5993..425da6c055 100644
--- a/src/nvim/regexp_nfa.c
+++ b/src/nvim/regexp_nfa.c
@@ -3931,6 +3931,7 @@ state_in_list (
// Add "state" and possibly what follows to state list ".".
// Returns "subs_arg", possibly copied into temp_subs.
+// Returns NULL when recursiveness is too deep.
static regsubs_T *
addstate (
nfa_list_T *l, /* runtime state list */
@@ -3956,6 +3957,14 @@ addstate (
#ifdef REGEXP_DEBUG
int did_print = FALSE;
#endif
+ static int depth = 0;
+
+ // This function is called recursively. When the depth is too much we run
+ // out of stack and crash, limit recursiveness here.
+ if (++depth >= 10000 || subs == NULL) {
+ depth--;
+ return NULL;
+ }
if (off_arg <= -ADDSTATE_HERE_OFFSET) {
add_here = true;
@@ -4059,6 +4068,7 @@ skip_add:
abs(state->id), l->id, state->c, code,
pim == NULL ? "NULL" : "yes", l->has_pim, found);
#endif
+ depth--;
return subs;
}
}
@@ -4202,6 +4212,9 @@ skip_add:
}
subs = addstate(l, state->out, subs, pim, off_arg);
+ if (subs == NULL) {
+ break;
+ }
// "subs" may have changed, need to set "sub" again.
if (state->c >= NFA_ZOPEN && state->c <= NFA_ZOPEN9) { // -V560
sub = &subs->synt;
@@ -4223,7 +4236,7 @@ skip_add:
if (nfa_has_zend && (REG_MULTI
? subs->norm.list.multi[0].end_lnum >= 0
: subs->norm.list.line[0].end != NULL)) {
- /* Do not overwrite the position set by \ze. */
+ // Do not overwrite the position set by \ze.
subs = addstate(l, state->out, subs, pim, off_arg);
break;
}
@@ -4284,6 +4297,9 @@ skip_add:
}
subs = addstate(l, state->out, subs, pim, off_arg);
+ if (subs == NULL) {
+ break;
+ }
// "subs" may have changed, need to set "sub" again.
if (state->c >= NFA_ZCLOSE && state->c <= NFA_ZCLOSE9) { // -V560
sub = &subs->synt;
@@ -4299,6 +4315,7 @@ skip_add:
sub->in_use = save_in_use;
break;
}
+ depth--;
return subs;
}
@@ -4308,12 +4325,11 @@ skip_add:
* This makes sure the order of states to be tried does not change, which
* matters for alternatives.
*/
-static void
-addstate_here (
- nfa_list_T *l, /* runtime state list */
- nfa_state_T *state, /* state to update */
- regsubs_T *subs, /* pointers to subexpressions */
- nfa_pim_T *pim, /* postponed look-behind match */
+static regsubs_T *addstate_here(
+ nfa_list_T *l, // runtime state list
+ nfa_state_T *state, // state to update
+ regsubs_T *subs, // pointers to subexpressions
+ nfa_pim_T *pim, // postponed look-behind match
int *ip
)
{
@@ -4324,18 +4340,23 @@ addstate_here (
/* First add the state(s) at the end, so that we know how many there are.
* Pass the listidx as offset (avoids adding another argument to
* addstate(). */
- addstate(l, state, subs, pim, -listidx - ADDSTATE_HERE_OFFSET);
+ regsubs_T *r = addstate(l, state, subs, pim, -listidx - ADDSTATE_HERE_OFFSET);
+ if (r == NULL) {
+ return r;
+ }
- /* when "*ip" was at the end of the list, nothing to do */
- if (listidx + 1 == tlen)
- return;
+ // when "*ip" was at the end of the list, nothing to do
+ if (listidx + 1 == tlen) {
+ return r;
+ }
- /* re-order to put the new state at the current position */
+ // re-order to put the new state at the current position
count = l->n - tlen;
- if (count == 0)
- return; /* no state got added */
+ if (count == 0) {
+ return r; // no state got added
+ }
if (count == 1) {
- /* overwrite the current state */
+ // overwrite the current state
l->t[listidx] = l->t[l->n - 1];
} else if (count > 1) {
if (l->n + count - 1 >= l->len) {
@@ -4368,6 +4389,8 @@ addstate_here (
}
--l->n;
*ip = listidx - 1;
+
+ return r;
}
/*
@@ -4997,6 +5020,7 @@ static int nfa_regmatch(nfa_regprog_T *prog, nfa_state_T *start,
int add_count;
int add_off = 0;
int toplevel = start->c == NFA_MOPEN;
+ regsubs_T *r;
#ifdef NFA_REGEXP_DEBUG_LOG
FILE *debug = fopen(NFA_REGEXP_DEBUG_LOG, "a");
@@ -5064,9 +5088,14 @@ static int nfa_regmatch(nfa_regprog_T *prog, nfa_state_T *start,
} else
m->norm.list.line[0].start = reginput;
m->norm.in_use = 1;
- addstate(thislist, start->out, m, NULL, 0);
- } else
- addstate(thislist, start, m, NULL, 0);
+ r = addstate(thislist, start->out, m, NULL, 0);
+ } else {
+ r = addstate(thislist, start, m, NULL, 0);
+ }
+ if (r == NULL) {
+ nfa_match = NFA_TOO_EXPENSIVE;
+ goto theend;
+ }
#define ADD_STATE_IF_MATCH(state) \
if (result) { \
@@ -5333,8 +5362,11 @@ static int nfa_regmatch(nfa_regprog_T *prog, nfa_state_T *start,
// t->state->out1 is the corresponding END_INVISIBLE
// node; Add its out to the current list (zero-width
// match).
- addstate_here(thislist, t->state->out1->out, &t->subs,
- &pim, &listidx);
+ if (addstate_here(thislist, t->state->out1->out, &t->subs,
+ &pim, &listidx) == NULL) {
+ nfa_match = NFA_TOO_EXPENSIVE;
+ goto theend;
+ }
}
}
break;
@@ -6150,12 +6182,17 @@ static int nfa_regmatch(nfa_regprog_T *prog, nfa_state_T *start,
pim = &pim_copy;
}
- if (add_here)
- addstate_here(thislist, add_state, &t->subs, pim, &listidx);
- else {
- addstate(nextlist, add_state, &t->subs, pim, add_off);
- if (add_count > 0)
+ if (add_here) {
+ r = addstate_here(thislist, add_state, &t->subs, pim, &listidx);
+ } else {
+ r = addstate(nextlist, add_state, &t->subs, pim, add_off);
+ if (add_count > 0) {
nextlist->t[nextlist->n - 1].count = add_count;
+ }
+ }
+ if (r == NULL) {
+ nfa_match = NFA_TOO_EXPENSIVE;
+ goto theend;
}
}
} // for (thislist = thislist; thislist->state; thislist++)
@@ -6225,10 +6262,17 @@ static int nfa_regmatch(nfa_regprog_T *prog, nfa_state_T *start,
(colnr_T)(reginput - regline) + clen;
else
m->norm.list.line[0].start = reginput + clen;
- addstate(nextlist, start->out, m, NULL, clen);
+ if (addstate(nextlist, start->out, m, NULL, clen) == NULL) {
+ nfa_match = NFA_TOO_EXPENSIVE;
+ goto theend;
+ }
}
- } else
- addstate(nextlist, start, m, NULL, clen);
+ } else {
+ if (addstate(nextlist, start, m, NULL, clen) == NULL) {
+ nfa_match = NFA_TOO_EXPENSIVE;
+ goto theend;
+ }
+ }
}
#ifdef REGEXP_DEBUG
diff --git a/src/nvim/testdir/test_regexp_latin.vim b/src/nvim/testdir/test_regexp_latin.vim
index de209fa9ec..5fb6e78baa 100644
--- a/src/nvim/testdir/test_regexp_latin.vim
+++ b/src/nvim/testdir/test_regexp_latin.vim
@@ -85,3 +85,9 @@ func Test_multi_failure()
call assert_fails('/a\{a}', 'E870:')
set re=0
endfunc
+
+func Test_recursive_addstate()
+ " This will call addstate() recursively until it runs into the limit.
+ let lnum = search('\v((){328}){389}')
+ call assert_equal(0, lnum)
+endfunc
generated by cgit (git 2.34.1) at 2025-05-08 04:42:10 +0000