typelevel / typelevel/cats

Stack-safety issues in `Kleisli` instances

Open
#3,947 6 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Scala
Stars
5.5k
Forks
1.2k
Avg merge
2d 10h
Merged PRs (30d)
5

Description

Repro 1:

import cats._
import cats.data._
import cats.implicits._

val res1 = (1 to 10000).toList.traverse_[Id, Unit](_ => ())  // ok

val res2 = (1 to 1000).toList.traverse_(_ => Kleisli.liftF[Id, String, Unit](())).run("") // fails with SO

traverse_ relies on List'sfoldRight and Kleisli'smap2Eval under the hood, which in turn relies on F.map2Eval

Repro 2 (involves Cats Effect):

import cats._
import cats.data._
import cats.implicits._
import cats.effect._

val res3 = (1 to 10000).toList.traverse_[IO, Unit](_ => IO.unit) // ok
val res4 = (1 to 10000).toList.traverse_(_ => Kleisli.liftF[IO, String, Unit](IO.unit)).run("") // ok

val res5 = (1 to 1000).toList.parTraverse_(_ => Kleisli.liftF[IO, String, Unit](IO.unit)).run("") // fails with SO

Thus, using Kleisli[IO, R, A] may result in SO at runtime if operations involving IO.Par are used, e.g. parTraverse_.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the two reported reproductions, then inspect Kleisli's map2Eval and the F.map2Eval path used by List.traverse_ and parTraverse_. Reproduce the stack overflows and verify that the affected Kleisli operations are stack-safe, including the Cats Effect IO.Par case.

Written by the indexing model from the issue text.

Assessment

Tech stack
scala
Domain
backend-api-design
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.