Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allows to make the parser fail before hitting a stack overflow error #282

Open
Tpt opened this issue Jan 13, 2022 · 5 comments · May be fixed by #308
Open

Allows to make the parser fail before hitting a stack overflow error #282

Tpt opened this issue Jan 13, 2022 · 5 comments · May be fixed by #308
Labels
feature Something not supported that perhaps should be requires-breaking-change

Comments

@Tpt
Copy link
Contributor

Tpt commented Jan 13, 2022

First, thank you so much for peg. I am an happy user since 2018.

I have one feature request, would it be possible to limit the recursion depth of parsers and return a nice error instead of having the currently parsing thread crashing on too nested inputs with a stack overflow error?

For example if I write the grammar:

pub rule arithmetic() -> i64 = precedence!{
  x:(@) "+" y:@ { x + y }
  x:(@) "-" y:@ { x - y }
  --
  n:number() { n }
  "(" e:arithmetic() ")" { e }
}

and give for input ((((((((((((((((1)))))))))))))))) the parser generated by peg will recuse 16 times to parse the content. An ill intentioned user can give for input to the parser a nested enough input to trigger a stack overflow.

A possible nice way to circumvent this problem in a generic manner might be to give to the parser generator a maximal allowed stack size and, if this parameter is provided, increment/decrement a counter at all rules entry/exit and return an error if the content reaches the threshold. But there is maybe a nicer solution I don't see.

What do you think about it?

@kevinmehall kevinmehall added the feature Something not supported that perhaps should be label Jan 14, 2022
@kevinmehall
Copy link
Owner

I think this is a good idea.

Some specifics to think about:

  • How the error is exposed in the API when limit is exceeded
  • Syntax for specifying the limit

@zsol
Copy link
Contributor

zsol commented Jun 29, 2022

Syntax for specifying the limit

How about adding this in the parser! macro?

parser!(stack_limit = 200) {
...
}

How the error is exposed in the API when limit is exceeded

I don't think there's a good way to expose this error at the moment. Maybe it's worth introducing a new kind of error that shuts parsing down entirely (without considering further alternatives)? In any case, I think that should be considered as a separate issue.

So for now we're left with two poor choices:

  • panic immediately
  • treat the limit breach as a rule failure (without attempting to match the rule), and add a special string to the list of expected symbols to help the end-user diagnose

@zsol zsol linked a pull request Jun 29, 2022 that will close this issue
3 tasks
@zsol
Copy link
Contributor

zsol commented Jun 29, 2022

I quickly changed my mind on the syntax I proposed above after trying to implement it :) #308 is my first stab at this problem.

@chrysn
Copy link

chrysn commented Jun 14, 2024

Is there an established workaround that can be used until there is an automated solution?

In my (and I suspect, may) case, of all the rules there is just one on which recusion happens, so I could envision something like this to work:

    rule item(n: usize) -> InnerItem<'input>
        = map(n-1) / array(n-1) / tagged(n-1) /
          number() / simple() / ...

that'd need some prefix (possibly a manually created rule) added around that recursion point that fails if n == 0.

Is there some reference implementation of such a fail-depending-on-argument rule, or some project that uses such a workaround to look at for a template before re-engineering this, or (just as appreciated) a description of how it has been tried and failed?

@kevinmehall
Copy link
Owner

The check for n == 0 could be written like {? if n == 0 { Err("too deeply nested") } else { Ok(()) }}.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature Something not supported that perhaps should be requires-breaking-change
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants