Add Luke Maranget's series in "Warnings for Pattern Matching"
In his paper, Luke Maranget came up with a series of pattern match matrices that apparently elicited exponential behavior in GHC's pattern match checker in 2007. This was still true until !1752 (closed)! Therefore we should add regression tests that make sure we aren't fallible to that anymore.
Here's S_12, for example:
module S where
data T = A | B
s :: T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> T -> ()
s A A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _= ()
s _ _ A A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _= ()
s _ _ _ _ A A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _= ()
s _ _ _ _ _ _ A A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _= ()
s _ _ _ _ _ _ _ _ A A _ _ _ _ _ _ _ _ _ _ _ _ _ _= ()
s _ _ _ _ _ _ _ _ _ _ A A _ _ _ _ _ _ _ _ _ _ _ _= ()
s _ _ _ _ _ _ _ _ _ _ _ _ A A _ _ _ _ _ _ _ _ _ _= ()
s _ _ _ _ _ _ _ _ _ _ _ _ _ _ A A _ _ _ _ _ _ _ _= ()
s _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ A A _ _ _ _ _ _= ()
s _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ A A _ _ _ _= ()
s _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ A A _ _= ()
s _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ A A= ()
s A B A B A B A B A B A B A B A B A B A B A B A B= ()
With -fmax-pmcheck-models=9999999999
(to emulate behavior prior to !1752 (closed)), this takes 2.6s to check and allocates 2.6GB. With -fmax-pmcheck-models=100
(which is the default), this reduces to 0.47s and 422MB.
S_13 takes 5s with -fmax-pmcheck-models=9999999999
and 0.51s with the default, and so on. S_20 doesn't finish without the delta limit, whereas with the limit in place it takes 0.845s.
Similarly with the T
and V
series. We should be sure that we don't regress on these.