SoE on pure stream with recursion

[pchlupacek]

This produces SoE:

def p : Stream[IO, Int] = 
(1 until 10000).map(Stream.emit)
.foldLeft(Stream.emit(0).covary[IO])((acc,a) => 
  acc flatMap { _ => Stream.eval(IO{()}).flatMap { _ =>  a } 
})

p.runLog.unsafeRunSync

java.lang.StackOverflowError
  at fs2.internal.Algebra$$$Lambda$3171/1646380420.apply(Unknown Source)
  at fs2.internal.FreeC$.$anonfun$mkViewL$1(FreeC.scala:90)
  at fs2.internal.FreeC$$$Lambda$3172/1984616342.apply(Unknown Source)
  at fs2.internal.Algebra$.$anonfun$uncons$7(Algebra.scala:91)
  at fs2.internal.Algebra$$$Lambda$3171/1646380420.apply(Unknown Source)
  at fs2.internal.FreeC$.$anonfun$mkViewL$1(FreeC.scala:90)
  at fs2.internal.FreeC$$$Lambda$3172/1984616342.apply(Unknown Source)
  at fs2.internal.Algebra$.$anonfun$uncons$7(Algebra.scala:91)
  at fs2.internal.Algebra$$$Lambda$3171/1646380420.apply(Unknown Source)
  at fs2.internal.FreeC$.$anonfun$mkViewL$1(FreeC.scala:90)
  at fs2.internal.FreeC$$$Lambda$3172/1984616342.apply(Unknown Source)
  at fs2.internal.Algebra$.$anonfun$uncons$7(Algebra.scala:91)
  at fs2.internal.Algebra$$$Lambda$3171/1646380420.apply(Unknown Source)
  at fs2.internal.FreeC$.$anonfun$mkViewL$1(FreeC.scala:90)
  at fs2.internal.FreeC$$$Lambda$3172/1984616342.apply(Unknown Source)
  at fs2.internal.Algebra$.$anonfun$uncons$7(Algebra.scala:91)
  at fs2.internal.Algebra$$$Lambda$3171/1646380420.apply(Unknown Source)
  at fs2.internal.FreeC$.$anonfun$mkViewL$1(FreeC.scala:90)
 ....

My gut it is related to special case of implementation in flatMap + this counters stack safety of FreeC through two consecutive viewL's in runFoldScope and uncons.

@mpilquist, @SystemFw this was discovered when implementing interruption, and I was not able to fix it in terms of current algebra and runFoldScope//uncons implementation.

[mpilquist]

Can you try commenting out the special case in flatMap for emitting a singleton stream? Removing the special case will reintroduce a memory leak but it will at least confirm your hunch.

[pchlupacek]

@mpilquist I have tried that just now, and as I have suspected this is unrelated. That means we do have SoE whether the special case for single element streams is there or not.

[pchlupacek]

As I was tracing this down I thin the problem is definition of ViewL, which in fact escapes the tail position in streams that jump between uncons and runFoldScope.

[mpilquist]

@pchlupacek Yeah I agree the issue is the non-tail position recursive call in Algebra.uncons. I'm not sure how to fix though. Maybe @pchiusano has some ideas.

[pchlupacek]

@mpilquist I may be on the track to resolve this. I have introduced Algebra.Uncons, and modified runXXX that seems to work nicely and no more SoE. The approach is in interrupt branch, and changes to Algebra are here. https://github.com/functional-streams-for-scala/fs2/pull/1019/files#diff-91195044dae5827508d46a79e123c46aR19

The tests are not yet all passing, but I think the issues there are fixable.

I would appreciate your feedback. Thanks

[mpilquist]

Looks good - let me know how it goes

…

On Dec 30, 2017, at 12:20 AM, Pavel Chlupacek ***@***.***> wrote: @mpilquist I may be on the track to resolve this. I have introduced Algebra.Uncons, and modified runXXX that seems to work nicely and no more SoE. The approach is in interrupt branch, and changes to Algebra are here. https://github.com/functional-streams-for-scala/fs2/pull/1019/files#diff-91195044dae5827508d46a79e123c46aR19 The tests are not yet all passing, but I think the issues there are fixable. I would appreciate your feedback. Thanks — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.