[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:  gkaracha
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.0.1
       Component:  Compiler          |              Version:  7.11
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #11302            |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by gkaracha):

 Ahhhh, I see. This has been noticed before. Actually, I have added a note
 in `deSugar/Check.hs`
 about it: `Note [Literals in PmPat]`. My primary test case for this
 problem has been
 function `mkTextEncoding'` from `libraries/base/GHC/IO/Encoding.hs` until
 now but I guess your
 example stresses the same problem even more.

 The source of the problem lies in the way we translate literals:
  * In the paper, we treat them as guards: literal `l` gets translated to
 `x (True <- x == l)`.
    This allows the algorithm to work uniformly on everything but is too
 expensive, even for
    `mkTextEncoding'`. Essentially, the covered set contains `x |> {True ~
 (x == l)}` and the
    uncovered contains `x |> {False ~ (x == l)}`. Hence, we explode first
 (everything is a
    guard) and then prune (use the term oracle to check the constraints)
 which is really
    exponential.

  * Hence, I changed the implementation and added literals in the pattern
 language. This means
    that for literal `l` the covered set contains `l |> {}` and the
 uncovered set contains
    `x |> {False ~ (x == l)}` like before. Since literals are patterns,
 more things can be
    checked eagerly, like with constructors where we can see immediately
 that e.g. `True` can
    not match `False`. Hence, we generate less from the start.

 The last thing to do (and I think this will address all performance issues
 concerning literals)
 is to completely add literals in the pattern language, that is, use a
 variant of Sestoft's
 negative patterns:
 {{{#!hs
 data PmPat :: PatTy -> * where
   PmCon  :: { ... }        -> PmPat t
   PmVar  :: Id             -> PmPat t
   PmLit  :: PmLit          -> PmPat t
   PmNLit :: Id -> [PmLit] -> PmPat VA -- add this constructor
   PmGrd  :: { ... }        -> PmPat PAT
 }}}
 The idea is that `PmNLit x lits` represents in a compact way __all
 literals `x` that are **not
 equal** to any of `lits`__. Hence, we generate much less and there is
 significantly less need
 for pruning.

 There is a slight possibility that this change will affect #322 and also I
 expect the size of
 the checker to increase 5-10% (LoC) but I have no better solution at the
 moment. Any ideas on
 this approach?

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