Check large switches for unused cases without comparing every pair
Why
The unused-case check compared each case with every earlier one and retyped part of each case, and its usefulness checks grouped rows by scanning all groups, so a switch with n constant or polymorphic variant cases cost O(n²) in several places: 6,000 int cases took 1.65 s and allocated 430M words, 1,600 polymorphic variant cases 1.31 s and 242M. They now take 0.56 s with 74M words, and 0.74 s with 128M.
Rows are indexed by the constant or tag at their head, which a row can only share with rows of the same head or of a head without one, such as a wildcard or a range: the earlier rows compatible with a case, the groups of filter_all and the most general rows of get_mins_pats are found through that index. A case is retyped to find GADT cases that can't match only when its pattern has a GADT constructor, as no other pattern can fail to type. Warnings are the same for the test suites and 2,600 generated switches.
Review
- What remains superlinear? The match compiler (
Matching.divideand the switch clustering) for constant switches: 6,000 int cases allocate 69M words with the warnings off, 3.4× the words for 3,000.