Patch megaparsec package to avoid StackOverflowException's

jneira commented 6 years ago

Testing the new version of dhall with eta a StackOverflowException is thrown:

PS C:\Users\Javier\dev\lang\eta\dhall\dhall-haskell> echo True | etlas run exe:dhall -- --e
xplain
Up to date
Exception in thread "main" java.lang.StackOverflowError
    at dhall.dhall.Parser.$fApplicative_Parser4(Parser.hs)
    at dhall.dhall.Parser$$fApplicative_Parser4.apply6(Parser.hs)
    at eta.runtime.apply.PAPSlow.apply(PAPSlow.java:50)
    at eta.runtime.apply.PAPSlow.apply5(PAPSlow.java:342)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at megaparsec.text.Megaparsec$sat_s3SRE.apply2(Megaparsec.hs)
    at dhall.dhall.Parser.$wa1(Parser.hs)
    at dhall.dhall.Parser.$wa(Parser.hs)
    at dhall.dhall.Parser.$fCharParsing_Parser1(Parser.hs)
    at dhall.dhall.Parser.$Lr8RHRa173(Parser.hs)
    at dhall.dhall.Parser$$Lr8RHRa173.apply5(Parser.hs)
    at dhall.dhall.Parser.$fParsing_Parser6(Parser.hs)
    at dhall.dhall.Parser.$Lr8RTOa361(Parser.hs)
    at dhall.dhall.Parser$$Lr8RTOa361.apply5(Parser.hs)
    at dhall.dhall.Parser$sat_s92UQ.apply5(Parser.hs)
    at megaparsec.text.Megaparsec.$Lr3OP9a7(Megaparsec.hs)
    at megaparsec.text.Megaparsec.pMap(Megaparsec.hs:381)
    at megaparsec.text.Megaparsec$pMap.enter(Megaparsec.hs:381)
    at eta.runtime.apply.PAPSlow.apply(PAPSlow.java:104)
    at eta.runtime.apply.PAPSlow.apply5(PAPSlow.java:342)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at dhall.dhall.Parser.$fApplicative_Parser3(Parser.hs)
    at dhall.dhall.Parser$$fApplicative_Parser3.enter(Parser.hs)
    at eta.runtime.apply.PAPSlow.apply(PAPSlow.java:104)
    at eta.runtime.apply.PAPSlow.apply5(PAPSlow.java:342)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at megaparsec.text.Megaparsec$a29_s3SPR.apply5(Megaparsec.hs)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at dhall.dhall.Parser.$fParsing_Parser6(Parser.hs)
    at dhall.dhall.Parser$sat_s92VG.apply6(Parser.hs)
    at dhall.dhall.Parser$sat_s915D.apply3(Parser.hs)
    at megaparsec.text.Megaparsec.accHints(Megaparsec.hs:323)
    at dhall.dhall.Parser$sat_s915B.apply3(Parser.hs)
    at megaparsec.text.Megaparsec.accHints(Megaparsec.hs:323)
    at dhall.dhall.Parser$sat_s915H.apply3(Parser.hs)
    at dhall.dhall.Parser$sat_s9189.apply6(Parser.hs)
    at dhall.dhall.Parser$sat_s915J.apply3(Parser.hs)
    at dhall.dhall.Parser.$Lr8RFDa120(Parser.hs)
    at dhall.dhall.Parser$$Lr8RFDa120.apply5(Parser.hs)
    at dhall.dhall.Parser.$fParsing_Parser6(Parser.hs)
    at dhall.dhall.Parser$sat_s918A.apply6(Parser.hs)
    at dhall.dhall.Parser$sat_s915D.apply3(Parser.hs)
    at megaparsec.text.Megaparsec.accHints(Megaparsec.hs:323)
    at dhall.dhall.Parser$sat_s915B.apply3(Parser.hs)
    at megaparsec.text.Megaparsec.accHints(Megaparsec.hs:323)
    at dhall.dhall.Parser$sat_s915H.apply3(Parser.hs)
    at dhall.dhall.Parser$sat_s917B.apply6(Parser.hs)
    at dhall.dhall.Parser$sat_s915J.apply3(Parser.hs)
    at dhall.dhall.Parser.$smatch3(Parser.hs)
    at dhall.dhall.Parser$$smatch3.apply5(Parser.hs)
    at dhall.dhall.Parser.$fParsing_Parser6(Parser.hs)
    at dhall.dhall.Parser$sat_s917C.apply6(Parser.hs)
    at dhall.dhall.Parser$sat_s915D.apply3(Parser.hs)
    at megaparsec.text.Megaparsec.accHints(Megaparsec.hs:323)
    at dhall.dhall.Parser$sat_s915B.apply3(Parser.hs)
    at megaparsec.text.Megaparsec.accHints(Megaparsec.hs:323)

As commented by @rahulmutt, the cause should be that megaparsec is continuation based, like aeson or binary so the steps could be:

we'll have to add a trampoline function to get rid of the SO export ETA_JAVA_ARGS=“-XX:MaxJavaStackTraceDepth=-1” Then, in the stack trace, go all the way to beginning and figure out where the (somewhat) repeating pattern of apply*’s starts See the aeson and binary patches for some examples Typically, the function that triggers the CPS computation by supplying an argument is a good canditate (functions like these will have the word run in their names)

rahulmutt commented 6 years ago

@jneira I also think the new-build system defaults to -O1, I wonder if -O2 will help in this case? To test this, add a cabal.project into dhall and add the following lines:

packages: .
all-packages
  optimization: 2

jneira commented 6 years ago

No luck changing the optimization level but trampoline worked!

jneira commented 6 years ago

As reported by @f-f in https://github.com/typelead/eta/issues/704#issuecomment-387220326, last version of dhall-haskell failed again with simple inputs due to StackOverflowException's involving megaparsec, so it seems the patch doesnt work now. I've tried to add trampolining in more call sites without luck:

In all calls to unParser that seems to be the function that potentially initiates the CPS: in this case the stacktrace continue referencing Megaparsec.hs lines 354 (pmap) and 292 (accHints)
- stacktrace
Remove inlining ({# INLINE x} directive) for all funtions with trampoline: in this case the references of megaparsec in te stacktrace move to the Applicative instance
- stacktrace
Add trampoline to the <*> method of Applicative instance for Parser: it thows another error [Eta v0.7.2b2] Cannot apply 5 closures to..
- stacktrace

In all cases the tests had been trying to evaluate 1 by dhall program. I am afraid that my understanding of the trampoline function and how to apply it is not enough to do it correctly.

jneira commented 6 years ago

@rahulmutt do you have any clue about how to apply trampoline?

rahulmutt commented 6 years ago

@jneira I think the main problem here is the polymorphism in unParser. It works on a transformer parametrized on m. Libraries like binary, aeson, etc. use a monomorphic parser type so it's easy to decide which trampoline function to use.

I think we need to introduce a trampolineM function when dealing with higher-kinded types:

class MonadTrampoline m where
  trampolineM :: m a -> m a

The reason for this is that in a pure, lazy language, there's a distinction between evaluation and execution. For pure values, evaluation coincides with execution and the default trampoline can be used and will work as intended. For (say IO values), evaluating an IO value is distinct from execution. Hence, you need a separate trampolineIO function for the IO monad and any monad transformer on top of it.

@agocorona had to define trampolineIO when working on the trampoline-based implementation of Fibers and it worked well. Note that any custom trampoline* functions will be built upon the low-level trampoline# primitive.

One idea here is to trampoline at the call site inside of dhall itself instead of inside of megaparsec since dhall will have to monomorphize the type in order to use it. If you can link me to the concrete parser type used in dhall, I can help you write the trampoline function for that type.

In the future though, we may have to go with the MonadTrampoline solution I mentioned above. We'll have to see whether updating the call site becomes an issue.

f-f commented 6 years ago

@rahulmutt the Parser type in Dhall should be this one

rahulmutt commented 6 years ago

@f-f Looked through the code and it seems dhall uses the simple parser, not the general transformer variant. In that case, adding a trampoline call in front of the implementation of runParser inside of megaparsec should do the trick. @jneira Can you try this out and update your current PR on eta-hackage if it works?

jneira commented 6 years ago

@rahulmutt @f-f thanks for the helpful comments I am afraid that the actual patch already adds trampoline in the lower function called by runParser The chain call is Dhall.Parser.exprAndHeaderFromText -> Text.Megaparsec.parse -> T.M.runParser -> T.M.runParser' -> T.M.runParserT -> T.M.runParserT' -> Text.Megaparsec.Internal.runParsecT' and the trampoline is in the last one. From the stacktraces i think the problematic chain call is Text.Megaparsec.Internal.pAp -> T.M.I.accHints -> T.M.I.pmap, i think dhall calls through the Applicative instance for ParsecT. I've tried to add trampoline in those points without luck

rahulmutt commented 6 years ago

@jneira Sorry about that! Didn't realize that was what you were already doing. I'll take a closer look.

Can you give me a minimal set of reproduction steps - if possible maybe even setup a github repo that I can simply clone and run to reproduce the error? Thanks!

Also, regarding the Applicative instance, can you show us the exact change you made?

jneira commented 6 years ago

@rahulmutt the steps would be:

checkout the branch eta of eta-lang/dhall-haskell
checkout my branch of eta-hackage in ~/etlas/patches with the patch including the trampoline in the <*> method of the applicative instance. The relevant code in Text.Megaparsec.Internal is:
```
instance Stream s => Applicative (ParsecT e s m) where
pure     = pPure
(<*>)    = trampoline $ pAp
p1 *> p2 = p1 `pBind` const p2
p1 <* p2 = do { x1 <- p1 ; void p2 ; return x1 }
```
build dhall-haskell with etlas
run echo True | etlas run exe:dhall in win or the equivalente in *nix

In my env it throws this exception:

Exception in thread "main" eta.runtime.exception.RuntimeInternalError: 
[Eta v0.7.2b2] Cannot apply 5 closures to Empty
Please report this as a bug: https://github.com/typelead/eta/issues
    at eta.runtime.RuntimeLogging.barf(RuntimeLogging.java:15)
    at eta.runtime.stg.Closure.apply5(Closure.java:94)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at dhall.dhall.Parser.$Lr8UTMa253(Parser.hs)
    at dhall.dhall.Parser.$fAlternative_Parser_$spAp(Parser.hs)
    at dhall.dhall.Parser$$fAlternative_Parser_$spAp.enter(Parser.hs)
    at eta.runtime.stg.Stg.trampoline(Stg.java:92)
    at dhall.dhall.Parser$$Lr8UWLp.thunkEnter(Parser.hs)
    at eta.runtime.thunk.CAF.evaluate(CAF.java:30)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at dhall.dhall.Parser$sat_s96V7.apply5(Parser.hs)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at megaparsec.text.megaparsec.Internal$sat_s3O6I.apply5(Internal.hs)
    at eta.runtime.thunk.Thunk.apply5(Thunk.java:182)
    at dhall.dhall.Parser.$fParsing_Parser6(Parser.hs)

rahulmutt commented 6 years ago

Thanks for the reproduction steps! Can you try trampoline . pAp and see if that fixes it? If not, I'll investigate further locally.

On Mon, May 28, 2018, 12:47 PM Javier Neira notifications@github.com wrote:

@rahulmutt https://github.com/rahulmutt the steps would be:

checkout the branch eta of eta-lang/dhall-haskell https://github.com/eta-lang/dhall-haskell/tree/eta

checkout my branch of eta-hackage https://github.com/jneira/eta-hackage/tree/megaparsec in ~/etlas/patches with the patch including the trampoline in the <*> method of the applicative instance. The relevant code in Text.Megaparsec.Internal is:

instance Stream s => Applicative (ParsecT e s m) where pure = pPure (<>) = trampoline $ pAp p1 > p2 = p1 pBind const p2 p1 <* p2 = do { x1 <- p1 ; void p2 ; return x1 }

build dhall-haskell with etlas

run echo True | etlas run exe:dhall in win or the equivalente in *nix

In my env it throws this exception:

Exception in thread "main" eta.runtime.exception.RuntimeInternalError: [Eta v0.7.2b2] Cannot apply 5 closures to Empty Please report this as a bug: https://github.com/typelead/eta/issues at eta.runtime.RuntimeLogging.barf(RuntimeLogging.java:15) at eta.runtime.stg.Closure.apply5(Closure.java:94) at eta.runtime.thunk.Thunk.apply5(Thunk.java:182) at dhall.dhall.Parser.$Lr8UTMa253(Parser.hs) at dhall.dhall.Parser.$fAlternativeParser$spAp(Parser.hs) at dhall.dhall.Parser$$fAlternativeParser$spAp.enter(Parser.hs) at eta.runtime.stg.Stg.trampoline(Stg.java:92) at dhall.dhall.Parser$$Lr8UWLp.thunkEnter(Parser.hs) at eta.runtime.thunk.CAF.evaluate(CAF.java:30) at eta.runtime.thunk.Thunk.apply5(Thunk.java:182) at dhall.dhall.Parser$sat_s96V7.apply5(Parser.hs) at eta.runtime.thunk.Thunk.apply5(Thunk.java:182) at megaparsec.text.megaparsec.Internal$sat_s3O6I.apply5(Internal.hs) at eta.runtime.thunk.Thunk.apply5(Thunk.java:182) at dhall.dhall.Parser.$fParsing_Parser6(Parser.hs)

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/typelead/eta-hackage/issues/85#issuecomment-392441034, or mute the thread https://github.com/notifications/unsubscribe-auth/AHqbHJMw2KSvXg8j6tU4A5vvaAEC-qzXks5t26SCgaJpZM4TMsZR .

jneira commented 6 years ago

With trampoline . pApthe error is:

JException java.lang.ClassCastException: dhall.dhall.Parser$sat_s9BFP cannot be cast to megaparsec.text.megaparsec.state.datacons.State

rahulmutt commented 6 years ago

@jneira Hmm so it looks like with the version of Eta on master we get a different behavior: it hangs regardless of what input you send it. That may be a separate issue relating to input handling, so let's fix one thing at a time. In the meantime, it would be great if you can construct a test case that uses dhall the library to parse an string literal to a dhall expression and that causes a StackOverflowError.

jneira commented 6 years ago

After fixing the input handling there is no more StackOverflow's errors with last versions od dhall and eta , but i am not sure why. Nevertheless i am gonna clode the issue, keeping the actual patch to megaparsec

typelead / eta-hackage

Patch megaparsec package to avoid StackOverflowException's #85