[GHC] #11303: Pattern matching against sets of strings sharing a prefix blows up pattern checker

[GHC]

#11303: Pattern matching against sets of strings sharing a prefix blows up pattern
checker
-------------------------------------+-------------------------------------
        Reporter:  bgamari           |                Owner:
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.2.1
       Component:  Compiler          |              Version:  7.11
      Resolution:                    |             Keywords:
                                     |  PatternMatchWarnings
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:  T11303
      Blocked By:                    |             Blocking:
 Related Tickets:  #11276, #11302    |  Differential Rev(s):  Phab:D1716,
       Wiki Page:                    |  Phab:D1719
-------------------------------------+-------------------------------------

Comment (by Ben Gamari <ben@…>):

 In [changeset:"28f951edfe50ea5182065144340061ec326781f5/ghc" 28f951e/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="28f951edfe50ea5182065144340061ec326781f5"
 Overhaul the Overhauled Pattern Match Checker

 Overhaul the Overhauled Pattern Match Checker

 * Changed the representation of Value Set Abstractions. Instead of
 using a prefix tree, we now use a list of Value Vector Abstractions.
 The set of constraints Delta for every Value Vector Abstraction is the
 oracle state so that we solve everything only once.

 * Instead of doing everything lazily, we prune at once (and in general
 everything is much stricter). Hence, an example written with pattern
 guards is checked in almost the same time as the equivalent with
 pattern matching.

 * Do not store the covered and the divergent sets at all. Since what we
 only need is a yes/no (does this clause cover anything? Does it force
 any thunk?) We just keep a boolean for each.

 * Removed flags `-Wtoo-many-guards` and `-ffull-guard-reasoning`.
 Replaced with `fmax-pmcheck-iterations=n`. Still debatable what should
 the default `n` be.

 * When a guard is for sure not going to contribute anything, we treat
 it as such: The oracle is not called and cases `CGuard`, `UGuard` and
 `DGuard` from the paper are not happening at all (the generation of a
 fresh variable, the unfolding of the pattern list etc.). his combined
 with the above seems to be enough to drop the memory increase for test
 T783 down to 18.7%.

 * Do not export function `dsPmWarn` (it is now called directly from
 within `checkSingle` and `checkMatches`).

 * Make `PmExprVar` hold a `Name` instead of an `Id`. The term oracle
 does not handle type information so using `Id` was a waste of
 time/space.

 * Added testcases T11195, T11303b (data families) and T11374

 The patch addresses at least the following:
 Trac #11195, #11276, #11303, #11374, #11162

 Test Plan: validate

 Reviewers: goldfire, bgamari, hvr, austin

 Subscribers: simonpj, thomie

 Differential Revision: https://phabricator.haskell.org/D1795
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11303#comment:21>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler