Stack Overflow when using curried interface member, no stack overflow with tupled version #87393
Description
Description
The following program causes a stack overflow in release build. If you follow the comments and use the tupled version of ApplyEval the stack overflow doesn't happen and the program runs till exit.
As far as I understand the dump of the IL, there are tail. prefixes in both versions but it seems that the runtime doesn't obey them for the curried version.
In the diff between the curried and the tupled IL, I see a big differences in the stack of
.override method instance !1 class Bar.ApplyEval`2<!a,!b>::Eval<[3]>
Maybe that's a hint that can help?
Please tell me if I can help in any way or if this should be raised in another repository.
namespace Bar
type Foo<'a> =
| Pure of 'a
| Apply of ApplyCrate<'a>
// This curried version of "ApplyEval" causes a stack overflow in Release compilation
and ApplyEval<'a, 'ret> = abstract Eval<'b,'c,'d> : 'b Foo -> 'c Foo -> 'd Foo -> ('b -> 'c -> 'd -> 'a) Foo -> 'ret
// This tupled version of "ApplyEval" does not cause a stack overflow in Release compilation
// and ApplyEval<'a, 'ret> = abstract Eval<'b,'c,'d> : ('b Foo * 'c Foo * 'd Foo * ('b -> 'c -> 'd -> 'a) Foo) -> 'ret
and ApplyCrate<'a> = abstract Apply : ApplyEval<'a, 'ret> -> 'ret
module Foo =
let apply2 (b : Foo<'b>) (c : Foo<'c>) (d : Foo<'d>) (f : Foo<'b -> 'c -> 'd -> 'a>) : Foo<'a> =
{ new ApplyCrate<'a> with
member _.Apply<'ret> (eval : ApplyEval<'a,'ret>) =
// eval.Eval(b, c, d, f) // uncomment for tupled version
eval.Eval b c d f // uncomment for curried version
}
|> Apply
let lift a = Pure a
let rec evaluateCps<'a, 'b> (f : 'a Foo) (cont : 'a -> 'b) : 'b =
match f with
| Pure a -> cont a
| Apply crate ->
crate.Apply
{ new ApplyEval<_,_> with
// member _.Eval((b, c, d, f)) = // uncomment for tupled version
member _.Eval b c d f = // uncomment for curried version
evaluateCps f (fun f ->
evaluateCps b (fun b ->
evaluateCps c (fun c ->
evaluateCps d (fun d -> cont (f b c d))
)
)
)
}
module TailRecBug =
let overflowtest () =
let rec makeChain (height : int) (k : int Foo -> 'r) : 'r =
if height <= 0 then
k (Foo.lift 0)
else
makeChain (height - 1)
(fun b ->
let c = Foo.lift height
let f = Foo.lift (fun a b c -> a + b + c)
Foo.apply2 b c c f |> k)
let chain = makeChain 10000 id
Foo.evaluateCps chain id
module Main =
[<EntryPoint>]
let main _argv =
let r = TailRecBug.overflowtest()
printfn "%A" r
0
IL of curried version
.method private hidebysig newslot virtual final
instance !b 'Bar.ApplyEval<\'a, \'b>.Eval'<c,d,e>(class Bar.Foo`1<!!c> b,
class Bar.Foo`1<!!d> c,
class Bar.Foo`1<!!e> d,
class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!a>>>> f) cil managed
{
.override method instance !1 class Bar.ApplyEval`2<!a,!b>::Eval<[3]>(class Bar.Foo`1<!!c>,
class Bar.Foo`1<!!d>,
class Bar.Foo`1<!!e>,
class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!0>>>>)
// Code size 24 (0x18)
.maxstack 9
IL_0000: ldarg.s f
IL_0002: ldarg.0
IL_0003: ldfld class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!0,!1> class Bar.Foo/evaluateCps@36<!a,!b>::cont
IL_0008: ldarg.1
IL_0009: ldarg.2
IL_000a: ldarg.3
IL_000b: newobj instance void class Bar.Foo/'evaluateCps@39-1'<!a,!b,!!c,!!d,!!e>::.ctor(class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!0,!1>,
class Bar.Foo`1<!2>,
class Bar.Foo`1<!3>,
class Bar.Foo`1<!4>)
IL_0010: tail.
IL_0012: call !!1 Bar.Foo::evaluateCps<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!1,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!2,!a>>>,!b>(class Bar.Foo`1<!!0>,
class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0,!!1>)
IL_0017: ret
} // end of method evaluateCps@36::'Bar.ApplyEval<\'a, \'b>.Eval'
IL of tupled version
.method private hidebysig newslot virtual final
instance !b 'Bar.ApplyEval<\'a, \'b>.Eval'<c,d,e>(class [System.Runtime]System.Tuple`4<class Bar.Foo`1<!!c>,class Bar.Foo`1<!!d>,class Bar.Foo`1<!!e>,class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!a>>>>> _arg1) cil managed
{
.override method instance !1 class Bar.ApplyEval`2<!a,!b>::Eval<[3]>(class [System.Runtime]System.Tuple`4<class Bar.Foo`1<!!c>,class Bar.Foo`1<!!d>,class Bar.Foo`1<!!e>,class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!0>>>>>)
// Code size 51 (0x33)
.maxstack 9
.locals init (class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!a>>>> V_0,
class Bar.Foo`1<!!e> V_1,
class Bar.Foo`1<!!d> V_2,
class Bar.Foo`1<!!c> V_3)
IL_0000: ldarg.1
IL_0001: call instance !3 class [System.Runtime]System.Tuple`4<class Bar.Foo`1<!!c>,class Bar.Foo`1<!!d>,class Bar.Foo`1<!!e>,class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!a>>>>>::get_Item4()
IL_0006: stloc.0
IL_0007: ldarg.1
IL_0008: call instance !2 class [System.Runtime]System.Tuple`4<class Bar.Foo`1<!!c>,class Bar.Foo`1<!!d>,class Bar.Foo`1<!!e>,class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!a>>>>>::get_Item3()
IL_000d: stloc.1
IL_000e: ldarg.1
IL_000f: call instance !1 class [System.Runtime]System.Tuple`4<class Bar.Foo`1<!!c>,class Bar.Foo`1<!!d>,class Bar.Foo`1<!!e>,class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!a>>>>>::get_Item2()
IL_0014: stloc.2
IL_0015: ldarg.1
IL_0016: call instance !0 class [System.Runtime]System.Tuple`4<class Bar.Foo`1<!!c>,class Bar.Foo`1<!!d>,class Bar.Foo`1<!!e>,class Bar.Foo`1<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!c,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!d,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!e,!a>>>>>::get_Item1()
IL_001b: stloc.3
IL_001c: ldloc.0
IL_001d: ldarg.0
IL_001e: ldfld class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!0,!1> class Bar.Foo/evaluateCps@36<!a,!b>::cont
IL_0023: ldloc.1
IL_0024: ldloc.2
IL_0025: ldloc.3
IL_0026: newobj instance void class Bar.Foo/'evaluateCps@39-1'<!a,!b,!!c,!!d,!!e>::.ctor(class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!0,!1>,
class Bar.Foo`1<!4>,
class Bar.Foo`1<!3>,
class Bar.Foo`1<!2>)
IL_002b: tail.
IL_002d: call !!1 Bar.Foo::evaluateCps<class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!1,class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!2,!a>>>,!b>(class Bar.Foo`1<!!0>,
class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0,!!1>)
IL_0032: ret
} // end of method evaluateCps@36::'Bar.ApplyEval<\'a, \'b>.Eval'
Reproduction Steps
-
compile the provided .fs file in Release mode
-
run the exe
-
stackoverflow happens
-
follow the comments to switch to the tupled version
-
compile the provided .fs file in Release mode
-
run the exe
-
stackoverflow doesn't happen
Expected behavior
The runtime obeys the tail. prefix for both version and no stack overflow happens in Release mode
Actual behavior
A stack overflow happens:
Stack overflow.
Repeat 5349 times:
--------------------------------
at Bar.Foo+apply2@17[[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Bar.ApplyCrate<'a>.Apply[[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Bar.ApplyEval`2<Int32,Int32>)
at System.Runtime.CompilerServices.RuntimeHelpers.DispatchTailCalls(IntPtr, Void (IntPtr, Byte ByRef, System.Runtime.CompilerServices.PortableTailCallFrame*), Byte ByRef)
--------------------------------
at Bar.Foo+apply2@17[[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Bar.ApplyCrate<'a>.Apply[[System.Int32, System.Private.CoreLib, Version=7.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Bar.ApplyEval`2<Int32,Int32>)
at Bar.Main.main(System.String[])
Regression?
As far as I know, this is not a regression.
Known Workarounds
Use the tupled version
Configuration
.NET 7 on x64 Win11
Other information
No response