Better warning messages on quotations of "large" disjunctive pattern matches

[kevmal]

With
F# Interactive version 10.6.0.0 for F# 4.7 and
F# Interactive version 10.5.0.0 for F# 4.6

type MyType = 
    {
        A : bool
        B : double
        C : double
    }
let (|Q|_|) (x : double) : unit option = None
let q =
    <@@
        match None, None, Unchecked.defaultof<_> with
        | None, Some p, {A = true; B = Q; C = Q}  -> ()
        | None, Some p, {A = true; B = x; C = Q}  -> ()
        | None, Some p, {A = true; B = Q; C = x}  -> ()
        | Some o, None, {A = true; B = Q; C = Q}  -> ()
        | Some o, None, {A = true; B = x; C = Q}  -> ()
        | Some o, None, {A = true; B = x; C = Q}  -> ()
        | Some o, None, {A = true; B = Q; C = x}  -> ()
        | Some o, None, {A = true; B = Q; C = x}  -> ()
        | _ -> printfn ""
        ()    
    @@>

Produces the error:

error FS0193: internal error: Data size must be > 0 and < 0x3f0000

This also compiles fine to a 23MB release build binary. It seems the Expr expansion of a match is not feasible. Each condition is causing a full branch which includes all cases below it. For example consider:

open FSharp.Quotations

let count n q =
    let rec loop q = 
        match q with
        | Patterns.Value((:? uint64 as x),_) when x = n -> 1
        | ExprShape.ShapeCombination(a, args) -> args |> List.sumBy loop
        | ExprShape.ShapeLambda(v, body) -> loop body
        | ExprShape.ShapeVar(v) -> 0
    loop q


<@
    match None, Unchecked.defaultof<_> with
    | None, {A = true; B = Q; C = Q} -> 1UL
    | _ -> 100UL
@>
|> count 100UL

Here the 100UL branch gets counted 4 times, With

<@
    match None, Unchecked.defaultof<_> with
    | None, {A = true; B = Q; C = Q} -> 1UL
    | None, {A = true; B = Q; C = Q} -> 2UL
    | _ -> 100UL
@>

the 2UL branch now counts to 4 and the 100UL branch is now at 16. This quickly explodes with relatively simple match blocks.

[cartermp]

This could very well be related to #4691

[kevmal]

It may partially be related. With quotations the situation is much worse though, the above when compiled (not quoted) the 100UL in all cases appears exactly once since instead of expanding repeating else branches the compiled code simply returns early. Here it's just a simple value but whatever the code block is gets repeated however many times (easily thousands of times).

For example, the compiled code above translates to 128 lines of C#. The quotation translates to well over 50000 lines (actual quote takes too long to decompile, ~50000 lines is actually from a slightly simpler case)

[TIHan]

Yea, that is a bit of a problem. I will try take on both this problem and the other one posted (#4691). I've been looking at pattern matching lately anyway so I have some context.

[dsyme]

As @TIHan and I have discussed, this is to some extent intrinsic in the design of quotations - quotations are an expression form and large disjunctive pattern matches can result in arbitrarily large expressions, and require an intermediate representation that includes some forms of goto/tree/branch/local-function structure to capture the possible code paths in a non-exponential way

So as things stand this is by-design, but a warning message indicating the approach of the problem ("your quotation is getting large") would be appropriate

Fixing the problem more generally is tricky and would require significant adjustments to quotations