Too many & and | patterns cause Visual Studio/Ionide to use up all available memory

[brianrourkeboll]

Opening a file with too many & and nested | patterns (inside of a single match branch?) causes Visual Studio or Ionide to use up all available memory and can eventually cause Windows to crash. It will continue to use up more and more memory even if you remove enough patterns to be under the "too many" threshold or close the file. More repetitions of this type of pattern will increase the rate at which memory is consumed.

Repro steps

This is likely not a perfectly minimal repro, but maybe it's good enough to hint at what the problem might be.

1. Write code that uses a fair number of & and nested | patterns inside of a single pattern-matching branch.

   This is not enough to cause a problem¹:

   // Fine.
   let f g x =
       let (|A|_|) x = if g x then Some x else None
       let (|B|C|) x = if g x then B x else C x
       match x with
       |   A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
             -> true
       | _ -> false

   This, however, is (the number of repetitions required to trigger the behavior is not exact; it's somewhere between the examples above and below):

   💥 Be careful pasting this into VS/VS Code without being prepared to kill it before it uses all your memory. Note that closing the file is not enough—you must close or kill Visual Studio/Code.

   // 💥 Will use up all your memory.
   let f g x =
       let (|A|_|) x = if g x then Some x else None
       let (|B|C|) x = if g x then B x else C x
       match x with
       |   A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
         & A (B _ | C _)
           -> true
       | _ -> false

   You will notice faster consumption of memory if you add more repetitions.

2. Visual Studio will eventually use up all available memory without further interaction. I have not let total memory usage go beyond 99% before killing VS, but a coworker's Windows machine eventually crashed on him when he did.

   

Expected behavior

I expect Visual Studio/Code not to use up all of my computer's memory—and certainly not gradually, in the background, without additional interaction.

Actual behavior

Visual Studio/Code uses up all of my computer's memory.

Known workarounds

None.

Related information

Both Visual Studio 17.5.4 and Visual Studio Code 1.77.3 + Ionide 7.5.2 on Windows 10 and 11.

Footnotes

1. This is a simplified example. The real code where we first ran into this bug did not actually repeat identical matches. ↩

[brianrourkeboll]

...I actually think this might be a relatively recent regression.

I opened some existing code that had some sizeable pattern matches but which did not trigger this behavior before (~several months ago?), and that same code now does trigger this.

[brianrourkeboll]

Actually, @vzarytovskii, I think I'm probably wrong about this being a regression. I think the combined conjunctive and disjunctive patterns just cause absolutely massive amounts of code to be generated, e.g., ~5,000 lines for 9 instances in my example, doubling with each additional instance—so 10,000 lines for 10…20,000 lines for 11…327,680,000 lines for 25…

Part of the problem seems to be that repeated &s of the same pattern are treated independently and re-tested after each &, creating a new branch (and basically another copy of the entire nested decision tree) and preventing any collapsing of the inner patterns. That seems logically unnecessary except for parameterized patterns, where re-testing would be required...

[T-Gro]

Yep, it is not tooling issue, it is the size of the output which goes exponential with each & ... line added.

@brianrourkeboll :
Is the regular code where you observed this generated, or human-written?
I would be interested into more real-world looking pattern match exhibiting this.