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

IndexedStateT is stack unsafe for left associative binds #2186

Closed
alexandru opened this issue Mar 10, 2018 · 1 comment · Fixed by #2187
Closed

IndexedStateT is stack unsafe for left associative binds #2186

alexandru opened this issue Mar 10, 2018 · 1 comment · Fixed by #2187

Comments

@alexandru
Copy link
Member

This test will fail with a stack overflow:

test("flatMap is stack safe on repeated left binds when F is") {
  val unit = StateT.pure[Eval, Unit, Unit](())
  val result = (0 until 100000).foldLeft(unit) { (acc, _) =>
    acc.flatMap(_ => unit)
  }
  result.run(()).value should === (((), ()))
}

Note that the usual 10,000 iterations that we've been using for testing stack safety aren't enough, because for IndexedStateT the stack size doesn't grow that fast. But the error can be seen for 100,000.

This is a problem for projects like cats-effect that need to provide a lawful Sync[StateT[F, S, ?]] instance.

NOTE: similar with #1733

@alexandru
Copy link
Member Author

And the PR is now here: #2187

kailuowang pushed a commit that referenced this issue Mar 14, 2018
* Fix #2186: make IndexedStateT stack safe if F[_] is

* IndexedStateT flatMap based on AndThen

* Optimize AndThen for fused operations

* Cleanup

* Cleanup

* Fix style issue

* Cleanup AndThen

* Add benchmark

* Add fusionMaxStackDepth constant

* fixing trailing whitespace
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant