Quantcast

Infinite recursion or deadlock and trying to cancel the parser

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Infinite recursion or deadlock and trying to cancel the parser

Thibaut Colar
I have an issue with my parser where as with some particular (broken) input it seem to get stuck in inifinite recursion and/or deadlock (Recovering parser).

In that scenario it uses 100% cpu and I can't seem to kill it short of killing the VM. I have put some "cancel" checks to make it throw a runtimeexception in some very often use rules of my grammar, but it still never hit them or ended.

I'm not sure if it's something wrong with my grammar or a parboiled but due to the use of bytecode manipulation I've had a very hard time to pinpoint it.

Questions:
1) Can't there be a way to cancel a parser built-in parboiled ?
2) Is there a good way to find at least what rules it's stuck on, assuming it's a grammar issue (i've tried to print out the matcher path when i cancel, but it seem to not always be i the same place). I mean a good way to profile the parser.

See screenshots and threaddump / profiling here:
http://www.colar.net/pb/

and this is the parser
https://bitbucket.org/tcolar/fantomidemodule/src/5551dbdfedc9/src/net/colar/netbeans/fan/parboiled/FantomParser.java

There seem to be a very very  long recursion of
org.parboiled.parserunners.RecoveringParseRunner$Handler.match(RecoveringParseRunner.java:315)
        at org.parboiled.parserunners.ErrorLocatingParseRunner.match(ErrorLocatingParseRunner.java:76)
        at org.parboiled.MatcherContext.runMatcher(MatcherContext.java:338)
        at org.parboiled.matchers.SequenceMatcher.match(SequenceMatcher.java:46)

Not sure if that's "normal" or not.



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Infinite recursion or deadlock and trying to cancel the parser

mathias
Administrator
Thibaut,

what you are seeing is probably not a deadlock or an infinite recursion, but an immensely deep backtracking search that parboiled performs in order figure out how to overcome a certain syntax error in the input. There are edge cases were the parser can exhibit in exponential runtime behavior, which will be perceived as deadlocks/infinite recursions.

> Questions:
> 1) Can't there be a way to cancel a parser built-in parboiled ?

Yes, there can.
My solution would be to allow you to specify a timeout period that the RecoveringParseRunner has to finish in. If it doesn't the complete unmatched rest of the input is considered illegal. I have created an issue for this (https://github.com/sirthias/pegdown/issues/42).

> 2) Is there a good way to find at least what rules it's stuck on, assuming it's a grammar issue (i've tried to print out the matcher path when i cancel, but it seem to not always be i the same place). I mean a good way to profile the parser.

You can try the [TracingParseRunner](http://www.decodified.com/parboiled/api/core/org/parboiled/parserunners/TracingParseRunner.html) and tune its filtering options to only log the "interesting" bits of your grammar.
This can be a great tool to understand how the parser is behaving but it does require some time to work with.

> There seem to be a very very  long recursion ...

Yes, this is normal. The parser can recurse _very_ deeply into your grammar as part of its normal operation.
The problem is that the stack trace isn't very helpful since you cannot see the rules that the parser has "opened" in the trace.
I was planning on having the next parboiled version generate the complete parser in bytecode (at runtime and at the time parse extension is currently done). I could then have the rules be implemented as methods whose names you'd be able to see in stack traces, which would be really helpful.
Unfortunately I don't think I'll have the time to really go down that road anytime soon.

Cheers,
Mathias

---
[hidden email]
http://www.parboiled.org

On 24.06.2012, at 19:27, Thibaut Colar [via parboiled users] wrote:

> I have an issue with my parser where as with some particular (broken) input it seem to get stuck in inifinite recursion and/or deadlock (Recovering parser).
>
> In that scenario it uses 100% cpu and I can't seem to kill it short of killing the VM. I have put some "cancel" checks to make it throw a runtimeexception in some very often use rules of my grammar, but it still never hit them or ended.
>
> I'm not sure if it's something wrong with my grammar or a parboiled but due to the use of bytecode manipulation I've had a very hard time to pinpoint it.
>
> Questions:
> 1) Can't there be a way to cancel a parser built-in parboiled ?
> 2) Is there a good way to find at least what rules it's stuck on, assuming it's a grammar issue (i've tried to print out the matcher path when i cancel, but it seem to not always be i the same place). I mean a good way to profile the parser.
>
> See screenshots and threaddump / profiling here:
> http://www.colar.net/pb/
>
> and this is the parser
> https://bitbucket.org/tcolar/fantomidemodule/src/5551dbdfedc9/src/net/colar/netbeans/fan/parboiled/FantomParser.java
>
> There seem to be a very very  long recursion of
> org.parboiled.parserunners.RecoveringParseRunner$Handler.match(RecoveringParseRunner.java:315)
>         at org.parboiled.parserunners.ErrorLocatingParseRunner.match(ErrorLocatingParseRunner.java:76)
>         at org.parboiled.MatcherContext.runMatcher(MatcherContext.java:338)
>         at org.parboiled.matchers.SequenceMatcher.match(SequenceMatcher.java:46)
>
> Not sure if that's "normal" or not.
>
>
>
>
>
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/Infinite-recursion-or-deadlock-and-trying-to-cancel-the-parser-tp4024029.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.
> NAML

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Infinite recursion or deadlock and trying to cancel the parser

Thibaut Colar
Thanks Mathias.

Yeah issue 42 would really help for my case. I actually already run the parser via a thread with a timeout, after which I try to cancel the parser and even kill the thread, but n that deep backtracking scenario it does not seem o have any effect and it juts keep running and hogging the CPU ... in my scenario, used to parse source files in an IDE, that's sort of a show stopper.
I'm guessing n the way i'm using parboiled it's "likely" there will be some severly "broken" input at times causing such heavy backtrackng, so being able to say "try to recover for x amount of time" or giveup would be useful.

I had missed that TracingParserRunner, I'll give that a shot and see if that helps pinpoint the issue.



 
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Infinite recursion or deadlock and trying to cancel the parser

Thibaut Colar
I don't seem to get anything out of the TracingParseRunner ... but from teh description of the base class (ReportingParserRunner) it seem t might only start logging on a second pass if the first one failed ? (which never happens).

I see nothing in the console anyway, do i need to specify a custom logger item ?

Thanks
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Infinite recursion or deadlock and trying to cancel the parser

mathias
Administrator
In reply to this post by Thibaut Colar
Yes,
we have had similar issues with an IDE plugin of ourselves.
Which reminds me of something I totally forgot:
The pegdown/parboiled issue 42 targets the non-recovering ParseRunners.

The RecoveringParseRunner already supports a timeout!
https://github.com/sirthias/parboiled/blob/master/parboiled-core/src/main/java/org/parboiled/parserunners/RecoveringParseRunner.java#L111

This should be pretty much what you want (and it is what we have used to overcome the problem).

Cheers,
Mathias

---
[hidden email]
http://www.parboiled.org

On 25.06.2012, at 17:42, Thibaut Colar [via parboiled users] wrote:

> Thanks Mathias.
>
> Yeah issue 42 would really help for my case. I actually already run the parser via a thread with a timeout, after which I try to cancel the parser and even kill the thread, but n that deep backtracking scenario it does not seem o have any effect and it juts keep running and hogging the CPU ... in my scenario, used to parse source files in an IDE, that's sort of a show stopper.
> I'm guessing n the way i'm using parboiled it's "likely" there will be some severly "broken" input at times causing such heavy backtrackng, so being able to say "try to recover for x amount of time" or giveup would be useful.
>
> I had missed that TracingParserRunner, I'll give that a shot and see if that helps pinpoint the issue.
>
>
>
>  
>
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/Infinite-recursion-or-deadlock-and-trying-to-cancel-the-parser-tp4024029p4024032.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.
> NAML

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Infinite recursion or deadlock and trying to cancel the parser

Thibaut Colar
Doh ! How dd I miss that.

Thanks
Loading...