Stack Overflow in Alt.choose

[Szer]

Description

Adding Alt.choose or <|> in code somehow breaks tail calling and everything fails with SO

Rerpo

run good code

let rec good() = 
    Alt.unit() ^=> good
good() |> run

It will block forever which is good.

run bad code

let rec bad() = 
    (Alt.unit() <|> Alt.never()) ^=> bad
bad() |> run

It fail with SO almost instantly

Expected

adding <|> Alt.never shouldn't break tail calling.
Both examples should block forever.

Known workaround

None

Notes

• Call stack is crawling with (<|>).DoJob calls. It means it never returns or not in tail position.
  

• Alt.tryIn which calling everything from tail position (said so in description) doesn't help:

let rec tryIn() = 
    Alt.tryIn
        <| (Alt.unit() <|> Alt.never())
        <| tryIn
        <| Alt.raises

tryIn() |> run

[Szer]

@haf I've made a research. It has to be linked with the compiler

(<|>) operator code is on F# side, but FSC generates nop call after void calls, which breaks JIT optimizations.

I've created issue here:
dotnet/fsharp#6026

[charlieturndorf]

Amazingly enough, when I try to repro this I get the exact opposite result: good fails with stack overflow, but bad and tryIn block forever. So confusing.

I built the repro samples into a release mode console app:

• Hopac 0.5.1
• dotnet sdk 6.0.101 installed
• release console app targeting netcoreapp3.1
• Windows 10

[charlieturndorf]

@Szer thanks so much for putting in effort to research this issue. I think similar overflows affect a fair number of people using Hopac.

I see that for this type of scenario, there is:

Hopac/Docs/Internals.md

Line 376 in 657a73d

*trampolining* that allows Hopac code to work even without any tail call

For each recursive construct where overflow occurs on some platform or runtime, the questions for me are:

1. Is the trampoline being used? Internal calls to static Job.Do, Cont.Do, and Work.Do should be trampolining when TRAMPOLINE is defined.
2. If the trampoline is used but there is still a stack overflow, is Worker.StackLimit or Unsafe.GetStackPtr() < wr.StackLimit ever estimating safe stack space wrong?

I think the solutions would be:

1. If the trampoline just isn't used, either:
   a. Change the existing construct (such as <|> or Alt.choose) to use Job.Do and other trampolining internals. Con: adds overhead even when not needed.
   b. Or add an equivalent construct (maybe <|>@ or Alt.chooseRec) that uses Job.Do etc. without adding any overhead to the original construct. Con: more API surface.
2. If the trampoline is used but not working, do the hard work of improving the trampoline.

Let's hope the overflows are all caused by 1 and not 2. (Or something else I missed that isn't so bad to fix.)