ParseContext#parse() throws StackOverflowError on tiny stack Android devices #1525
Closed
2 tasks done
Labels
Comments
|
HI,
One could argue that the issue lies in Android, which ignores stackSize.
But more broadly, there is no guarantee that ANTLR will operate under tight resource constraints.
There has been some exploration to move from recursive code to loop based algorithm. This may affect the stack, but less likely the heap, which is essential to performance. And there is no ETA.
In short, you may want to reconsider the objective of delivering a rather complex parser for tiny devices.
Eric
Envoyé de mon iPhone
… Le 18 déc. 2016 à 12:03, FUJI Goro ***@***.***> a écrit :
Before submitting an issue to ANTLR, please check off these boxes:
I am not submitting a question on how to use ANTLR; instead, go to antlr4-discussion google group or ask at stackoverflow
I have done a search of the existing issues to make sure I'm not sending in a duplicate
This issue is alike to #744, but with some extra information.
I have found this issue on my Android library project Android-Orma, which parses SQLite DDL with an ANTLR4-based SQL parser.
How can I avoid this issue?
new Thread(group, runnable, name, stackSize) does not affect this issue. In fact, stackSize seems to be ignored on Android (at least in older versions like Android 4.x).
Environment
Android with a tiny stack size (older Android, or Android emulators with heapSize=16MB)
The grammar: https://github.com/bkiers/sqlite-parser/blob/master/src/main/antlr4/nl/bigo/sqliteparser/SQLite.g4
The program to parse: CREATE TABLE foo (title TEXT DEFAULT (''))
Stacktrace
Copied from maskarade/Android-Orma#352 (comment)
org.antlr.v4.runtime.misc.ParseCancellationException: SQL is too complex to parse: CREATE TABLE foo (title TEXT DEFAULT (''))
at com.github.gfx.android.orma.migration.sqliteparser.SQLiteParserUtils.parseIntoCreateTableStatement(SQLiteParserUtils.java:64)
at com.github.gfx.android.orma.migration.test.sqliteparser_test.SQLiteParserUtilsTest.testComplexTable(SQLiteParserUtilsTest.java:161)
at java.lang.reflect.Method.invokeNative(Native Method)
at java.lang.reflect.Method.invoke(Method.java:511)
at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
at org.junit.runners.Suite.runChild(Suite.java:128)
at org.junit.runners.Suite.runChild(Suite.java:27)
at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
at org.junit.runner.JUnitCore.run(JUnitCore.java:115)
at android.support.test.internal.runner.TestExecutor.execute(TestExecutor.java:59)
at android.support.test.runner.AndroidJUnitRunner.onStart(AndroidJUnitRunner.java:262)
at android.app.Instrumentation$InstrumentationThread.run(Instrumentation.java:1584)
Caused by: java.lang.StackOverflowError
at java.util.Arrays.equals(Arrays.java:1582)
at org.antlr.v4.runtime.atn.ArrayPredictionContext.equals(ArrayPredictionContext.java:78)
at java.util.LinkedHashMap.get(LinkedHashMap.java:259)
at org.antlr.v4.runtime.misc.DoubleKeyMap.get(DoubleKeyMap.java:38)
at org.antlr.v4.runtime.atn.PredictionContext.mergeArrays(PredictionContext.java:363)
at org.antlr.v4.runtime.atn.PredictionContext.merge(PredictionContext.java:174)
at org.antlr.v4.runtime.atn.ATNConfigSet.add(ATNConfigSet.java:155)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1529)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closure_(ParserATNSimulator.java:1583)
at org.antlr.v4.runtime.atn.ParserATNSimulator.closureCheckingStopState(ParserATNSimulator.java:1513)
(snip)
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or mute the thread.
|
|
@ericvergnaud is this exploration something that can publicly be seen? I've been thinking for a while about changing the highly recursive ATN simulator closure code to a loop based one, as it can exhaust the stack even on a a full desktop machine with increased stack size (e.g. for complex expression rules with left recursion). |
|
I believe someone submitted a PR a while ago, at least there was some discussion
Envoyé de mon iPhone
… Le 20 déc. 2016 à 18:22, Mike Lischke ***@***.***> a écrit :
@ericvergnaud is this exploration something that can publicly be seen? I've been thinking for a while about changing the highly recursive ATN simulator closure code to a loop based one, as it can exhaust the stack even on a a full desktop machine with increased stack size (e.g. for complex expression rules with left recursion).
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or mute the thread.
|
|
Hmm, I believe you mean the iterative walker, which meanwhile made it into the runtime. |
|
No I was actually referring to the discussion in #744, which didn’t go very far.
… Le 20 déc. 2016 à 18:54, Mike Lischke ***@***.***> a écrit :
Hmm, I believe you mean the iterative walker, which meanwhile made it into the runtime.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub <#1525 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADLYJLFSP_xgoM3CR-q8btmf9mAZ7cD7ks5rJ7QAgaJpZM4LQCzT>.
|
|
Yeah, not sure we can do anything about wanting to parse a complex language on a tiny device. |
|
Hmm, if Anyway, now I got it. Thanks. |
|
@gfx the recursive overflow is actually a function of the deeply nested SQL grammar not the input. A few tokens could easily push recursion into the hundreds of invocations. :) |
|
@parrt Whenever I've seen a stack overflow due to deep recursion it was during ATN execution, never in the parser itself (have frequently seen stack depths of 1000+). The closure code does a roundtrip per ATN state (not per rule as the parser), so it is much more sensitive to the parsed language. By converting this to a loop we will probably get a much better behavior. |
|
Yes, but the ATN is a version of the grammar 1-to-1. Analysis during parsing must traverse the ATN (grammar) to answer prediction questions. The ALL(*) is extremely complex particularly when you consider optimizations. Converting such a recursion process to a loop would be nigh on impossible. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Before submitting an issue to ANTLR, please check off these boxes:
This issue is alike to #744, but with some extra information.
I have found this issue on my Android library project Android-Orma, which parses SQLite DDL with an ANTLR4-based SQL parser.
How can I avoid this issue?
new Thread(group, runnable, name, stackSize)does not affect this issue. In fact,stackSizeseems to be ignored on Android (at least in older versions like Android 4.x).Environment
CREATE TABLE foo (title TEXT DEFAULT (''))Stacktrace
Copied from maskarade/Android-Orma#352 (comment)
The text was updated successfully, but these errors were encountered: