Stack-safety issues in Kleisli instances

[catostrophe]

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_.

[johnynek]

I think an issue there is a deep, cats3-level issue that Eval[A] was used in early cats where we really wanted to use Defer[F] but we had yet to understand that. Calling .value on an Eval is code smell and doing so in a loop is reasonably likely to break stack safety.

I could fix this issue with this diff:

+trait KleisliDeferApplicative[F[_], A] extends KleisliApplicative[F, A] {
+  implicit def deferF: Defer[F]
+
+  override def map2Eval[B, C, Z](fa: Kleisli[F, A, B], fb: Eval[Kleisli[F, A, C]])(
+    f: (B, C) => Z
+  ): Eval[Kleisli[F, A, Z]] = {
+    
+    val kb = Defer[Kleisli[F, A, *]].defer(fb.value)
+
+    Eval.now(Kleisli { a =>
+      val ec: Eval[F[C]] = Eval.always(kb.run(a))
+      val efz: Eval[F[Z]] = F.map2Eval(fa.run(a), ec)(f)
+      deferF.defer(efz.value)
+    })
+  }
+}
+

diff --git a/tests/src/test/scala/cats/tests/KleisliSuite.scala b/tests/src/test/scala/cats/tests/KleisliSuite.scala
index 0879b4a02..dd031a249 100644
--- a/tests/src/test/scala/cats/tests/KleisliSuite.scala
+++ b/tests/src/test/scala/cats/tests/KleisliSuite.scala
@@ -354,6 +354,16 @@ class KleisliSuite extends CatsSuite {
     assertEquals(program.run(A123), List((1, "2", true)))
   }
 
+  test("traverse_ doesn't stack overflow") {
+    // see: https://github.com/typelevel/cats/issues/3947
+    implicit val lazyKleisli = new cats.data.KleisliDeferApplicative[Eval, String] {
+      val deferF = Eval.catsDeferForEval
+      val F = Eval.catsBimonadForEval
+    }
+    val res2 = (1 to 10000).toList.traverse_(_ => Kleisli.liftF[Eval, String, Unit](Eval.now(()))).run("").value // fails with SO
+    assert(res2 == ())
+  }
+
   /**
    * Testing that implicit resolution works. If it compiles, the "test" passes.
    */

but requiring a Defer[F] to make an Applicative for Kleisli would be a breaking change.

Note, we did something pretty unprincipled before: #2185 to address a related issue. If instead of doing the reflection hack there, we had used Defer[F].defer(run(a)) I think we could have solved the stack safety issues there.

This is related to how Defer[F] was used to implement ContT: #2506

We could add a higher priority implicit to provide the Apply/Applicative/Monad/... etc I wrote above if a Defer is available for F, but that does complicate the implicit search for Kleisi and it is already quite complex.

Also, we need to work to remove all internal calls to Eval.value for which there is no way to be sure we are at constant stack depth.

[johnynek]

basically, look at all the internal calls to run in Kleisi. Those should pretty much all be Defer[F].defer(run(a)) in order to be stack safe, otherwise we are increasing stack depth constantly.

[armanbilge]

but requiring a Defer[F] to make an Applicative for Kleisli would be a breaking change.

Source-breaking for sure, but theoretically we could do this in a binary-compatible way? e.g. taking your idea

We could add a higher priority implicit to provide the Apply/Applicative/Monad/... etc I wrote above if a Defer is available for F, but that does complicate the implicit search for Kleisi and it is already quite complex.

But instead of making it a higher-priority implicit, making the old way no longer an implicit.

[johnynek]

Yeah, I guess that's true.

But, also note how many internal methods to Kleisli call run(a) and those are not type classes and they could not require Defer[F] without breaking binary compatibility.

Honestly, I wonder if a whole new implementation is worth it. DKleisli[F[_], A, B] where we always require Defer[F] before calling run.

[johnynek]

I've updated the PR.

One work around is to make collections have safe traverse_ rather than expecting the foldRight implementation to work (which is fundamentally linear depth).

[johnynek]

see #3962 for some related work.