Stack overflow on macOS for long pipelines

[lydell]

Repro repo: https://github.com/lydell/fantomas-stack-overflow-demo

Issue created from fantomas-online

Code

// Learn more about F# at http://docs.microsoft.com/dotnet/fsharp

open System

// Define a function to construct a message to print
let from whom = sprintf "from %s" whom

[<EntryPoint>]
let main argv =
    let message = from "F#" // Call the function

    printfn "Hello world %s" message
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id

    0 // return an integer exit code

Result

Online and in GitHub Actions (we run on ubuntu-latest):

// Learn more about F# at http://docs.microsoft.com/dotnet/fsharp

open System

// Define a function to construct a message to print
let from whom = sprintf "from %s" whom

[<EntryPoint>]
let main argv =
    let message = from "F#" // Call the function

    printfn "Hello world %s" message
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id
    |> id

    0 // return an integer exit code

On macOS:

Processing src/MyApp/Program.fs
Stack overflow.
Repeat 86 times:
--------------------------------
   at Fantomas.AstTransformer+Ast.visitSynExpr(SynExpr)
   at Fantomas.AstTransformer+Ast+visitSynExpr@331-72.GenerateNext(System.Collections.Generic.IEnumerable`1<Node> ByRef)
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNextImpl()
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].System.Collections.IEnumerator.MoveNext()
   at Microsoft.FSharp.Collections.SeqModule.ToList[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](System.Collections.Generic.IEnumerable`1<System.__Canon>)
--------------------------------
   at Fantomas.AstTransformer+Ast.visitSynExpr(SynExpr)
   at Fantomas.AstTransformer+Ast+cons@390-1[[System.Boolean, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].GenerateNext(System.Collections.Generic.IEnumerable`1<Node> ByRef)
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNextImpl()
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].System.Collections.IEnumerator.MoveNext()
   at Microsoft.FSharp.Collections.SeqModule.ToList[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](System.Collections.Generic.IEnumerable`1<System.__Canon>)
   at Fantomas.AstTransformer+Ast.cons@381[[System.Boolean, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](SynExpr, Microsoft.FSharp.Collections.FSharpList`1<System.Tuple`4<Boolean,SynExpr,Microsoft.FSharp.Core.FSharpOption`1<SynExpr>,range>>)
   at Fantomas.AstTransformer+Ast.visitSynExpr(SynExpr)
   at Fantomas.AstTransformer+Ast+visitSynExpr@354-77.GenerateNext(System.Collections.Generic.IEnumerable`1<Node> ByRef)
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNextImpl()
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].System.Collections.IEnumerator.MoveNext()
   at Microsoft.FSharp.Collections.SeqModule.ToList[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](System.Collections.Generic.IEnumerable`1<System.__Canon>)
   at Fantomas.AstTransformer+Ast.visitSynExpr(SynExpr)
   at Fantomas.AstTransformer+Ast+visitSynBinding@1034-1.GenerateNext(System.Collections.Generic.IEnumerable`1<Node> ByRef)
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNextImpl()
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].System.Collections.IEnumerator.MoveNext()
   at Microsoft.FSharp.Collections.SeqModule.ToList[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](System.Collections.Generic.IEnumerable`1<System.__Canon>)
   at Fantomas.AstTransformer+Ast.visitSynBinding(SynBinding)
   at Fantomas.AstTransformer+Ast+visitSynModuleDecl@109-3.Invoke(SynBinding)
   at Microsoft.FSharp.Primitives.Basics.List.map[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,System.__Canon>, Microsoft.FSharp.Collections.FSharpList`1<System.__Canon>)
   at Microsoft.FSharp.Collections.ListModule.Map[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,System.__Canon>, Microsoft.FSharp.Collections.FSharpList`1<System.__Canon>)
   at Fantomas.AstTransformer+Ast.visitSynModuleDecl(SynModuleDecl)
   at Fantomas.AstTransformer+Ast+visitSynModuleOrNamespace@84-3.Invoke(SynModuleDecl)
   at Microsoft.FSharp.Primitives.Basics.List.mapToFreshConsTail[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Microsoft.FSharp.Collections.FSharpList`1<System.__Canon>, Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,System.__Canon>, Microsoft.FSharp.Collections.FSharpList`1<System.__Canon>)
   at Microsoft.FSharp.Primitives.Basics.List.map[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,System.__Canon>, Microsoft.FSharp.Collections.FSharpList`1<System.__Canon>)
   at Fantomas.AstTransformer+Ast+visitSynModuleOrNamespace@78-2.GenerateNext(System.Collections.Generic.IEnumerable`1<Node> ByRef)
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNextImpl()
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].System.Collections.IEnumerator.MoveNext()
   at Microsoft.FSharp.Collections.SeqModule.ToList[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](System.Collections.Generic.IEnumerable`1<System.__Canon>)
   at Fantomas.AstTransformer+Ast.visitSynModuleOrNamespace(SynModuleOrNamespace)
   at Fantomas.AstTransformer+children@1897-1.Invoke(SynModuleOrNamespace)
   at Microsoft.FSharp.Primitives.Basics.List.map[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,System.__Canon>, Microsoft.FSharp.Collections.FSharpList`1<System.__Canon>)
   at Fantomas.AstTransformer+children@1897.GenerateNext(System.Collections.Generic.IEnumerable`1<Node> ByRef)
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNextImpl()
   at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].System.Collections.IEnumerator.MoveNext()
   at Microsoft.FSharp.Collections.SeqModule.ToList[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](System.Collections.Generic.IEnumerable`1<System.__Canon>)
   at Fantomas.AstTransformer.astToNode(Microsoft.FSharp.Collections.FSharpList`1<ParsedHashDirective>, Microsoft.FSharp.Collections.FSharpList`1<SynModuleOrNamespace>)
   at Fantomas.Trivia.collectTrivia(Microsoft.FSharp.Core.FSharpFunc`2<System.Tuple`2<Int32,Int32>,Microsoft.FSharp.Core.FSharpFunc`2<System.Tuple`2<Int32,Int32>,range>>, Microsoft.FSharp.Collections.FSharpList`1<Token>, ParsedInput)
   at Fantomas.Context+Context.Create(FormatConfig, Microsoft.FSharp.Collections.FSharpList`1<System.String>, System.String, Microsoft.FSharp.Collections.FSharpList`1<Token>, System.String, Microsoft.FSharp.Core.FSharpOption`1<ParsedInput>)
   at Fantomas.CodeFormatterImpl.formatWith(ParsedInput, Microsoft.FSharp.Collections.FSharpList`1<System.String>, Microsoft.FSharp.Collections.FSharpList`1<Token>, FormatContext, FormatConfig)
   at Fantomas.CodeFormatterImpl+format@409-1.Invoke(System.Tuple`3<ParsedInput,Microsoft.FSharp.Collections.FSharpList`1<System.String>,Microsoft.FSharp.Collections.FSharpList`1<Token>>[])
   at Microsoft.FSharp.Control.AsyncPrimitives.CallThenInvokeNoHijackCheck[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e],[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Microsoft.FSharp.Control.AsyncActivation`1<System.__Canon>, Microsoft.FSharp.Core.FSharpFunc`2<System.__Canon,Microsoft.FSharp.Control.FSharpAsync`1<System.__Canon>>, System.__Canon)
   at Microsoft.FSharp.Control.Trampoline.Execute(Microsoft.FSharp.Core.FSharpFunc`2<Microsoft.FSharp.Core.Unit,Microsoft.FSharp.Control.AsyncReturn>)
   at Microsoft.FSharp.Control.TrampolineHolder.ExecuteWithTrampoline(Microsoft.FSharp.Core.FSharpFunc`2<Microsoft.FSharp.Core.Unit,Microsoft.FSharp.Control.AsyncReturn>)
   at <StartupCode$FSharp-Core>.$Async.finishTask@1186[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]](Microsoft.FSharp.Control.AsyncActivation`1<System.__Canon[]>, System.__Canon[], Microsoft.FSharp.Control.LinkedSubSource, Microsoft.FSharp.Core.FSharpRef`1<Microsoft.FSharp.Core.FSharpOption`1<Microsoft.FSharp.Core.FSharpChoice`2<System.Runtime.ExceptionServices.ExceptionDispatchInfo,System.OperationCanceledException>>>, Int32)
   at <StartupCode$FSharp-Core>.$Async+Parallel@1233-4[[System.__Canon, System.Private.CoreLib, Version=5.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Invoke(System.__Canon)
   at Fantomas.CodeFormatterImpl+parse@95-6.Invoke(Microsoft.FSharp.Control.AsyncActivation`1<System.Tuple`3<ParsedInput,Microsoft.FSharp.Collections.FSharpList`1<System.String>,Microsoft.FSharp.Collections.FSharpList`1<Token>>>)
   at Microsoft.FSharp.Control.AsyncPrimitives+unitAsync@577.Invoke(Microsoft.FSharp.Control.AsyncActivation`1<Microsoft.FSharp.Core.Unit>)
   at <StartupCode$FSharp-Compiler-Service>.$Service+ParseFile@449-3.Invoke(Microsoft.FSharp.Control.AsyncActivation`1<FSharp.Compiler.SourceCodeServices.FSharpParseFileResults>)
   at Microsoft.FSharp.Control.Trampoline.Execute(Microsoft.FSharp.Core.FSharpFunc`2<Microsoft.FSharp.Core.Unit,Microsoft.FSharp.Control.AsyncReturn>)
   at Microsoft.FSharp.Control.TrampolineHolder.ExecuteWithTrampoline(Microsoft.FSharp.Core.FSharpFunc`2<Microsoft.FSharp.Core.Unit,Microsoft.FSharp.Control.AsyncReturn>)
   at <StartupCode$FSharp-Core>.$Async+-ctor@155-1.Invoke(System.Object)
   at System.Threading.QueueUserWorkItemCallbackDefaultContext.Execute()
   at System.Threading.ThreadPoolWorkQueue.Dispatch()
   at System.Threading._ThreadPoolWaitCallback.PerformWaitCallback()

Problem description

Fantomas crashes with a stack overflow on macOS.

And yes, we do have two long enough pipelines at work to trigger this 😄 Our longest pipeline is currently over 50 pipes long. I had to break it into 3 pieces to get Fantomas to work 🙈

Workaround

Split the pipeline into two parts:

// Learn more about F# at http://docs.microsoft.com/dotnet/fsharp

open System

// Define a function to construct a message to print
let from whom = sprintf "from %s" whom

[<EntryPoint>]
let main argv =
    let message = from "F#" // Call the function

    let fantomasWorkaroundLongPiping =
        printfn "Hello world %s" message
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id
        |> id

    fantomasWorkaroundLongPiping
	|> id
	// And more pipes in the future…

    0 // return an integer exit code

Extra information

• The formatted result breaks by code.
• The formatted result gives compiler warnings.
• I or my company would be willing to help fix this.

Options

Fantomas Master at 02/12/2021 20:07:06 - e016b1c

Default Fantomas configuration

Using 4.4.0-beta-007 locally

[nojaf]

Hello @lydell, thank you for this detailed report.
I'm clueless why this occurs on Mac and not on Windows.
Perhaps this a problem in FSharp.Core or FSharp.Compiler.Service.
Would you be interested in submitting a PR?

[lydell]

Getting a stack overflow on just one OS sure is puzzling!

Would you be interested in submitting a PR?

Interested, yes. But since last time I said that I still haven’t got around to doing anything. So it might take a while depending on how much time I have and how often I bump into this issue.

Now we have an issue at least so we can see if other bump into this as well.

[knocte]

What would the PR that fixes this do? Maybe there's some recursive algorithm that needs to be converted into a proper tailcall?

[nojaf]

So, I think the problem occurs in

fantomas/src/Fantomas/AstTransformer.fs

Lines 320 to 332 in a7dd05a

	| SynExpr.App (atomicFlag, isInfix, funcExpr, argExpr, range) ->
	{ Type = SynExpr_App
	Range = r range
	Properties =
	p [ "atomicFlag"
	==> (match atomicFlag with
	| ExprAtomicFlag.Atomic -> "Atomic"
	| _ -> "Not Atomic")
	"isInfix" ==> isInfix ]
	FsAstNode = synExpr
	Childs =
	[ yield visitSynExpr funcExpr
	yield visitSynExpr argExpr ] }

The code Simon has is a deeply nested version of Syn.App and that is giving problems on Mac.
Fantomas actually does not need the tree of AST Nodes

fantomas/src/Fantomas/AstTransformer.fs

Lines 17 to 22 in a7dd05a

	type Node =
	{ Type: FsAstType
	Range: range option
	Properties: Map<string, obj>
	Childs: Node list
	FsAstNode: FsAstNode }

, it will flatten the tree later in:

fantomas/src/Fantomas/Trivia.fs

Lines 541 to 544 in a7dd05a

	let triviaNodesFromAST =
	flattenNodeToList node
	|> filterNodes
	|> List.choose mapNodeToTriviaNode

So changing the code in ASTTransformer, to return a list of nodes instead of a parent/child tree might resolve the problem.
This is speculation at this point.

[nojaf]

@lydell does this still occur in the latest alpha?
I've implemented those suggested changes a while ago.

[lydell]

@nojaf I just tested 4.5.0-alpha-011. The problem is fixed! Thank you very much! 🎉

[nojaf]

Thanks for confirming!