[GHC] #13943: Compiler infinite loop with GHC-8.2

[GHC]

#13943: Compiler infinite loop with GHC-8.2
-------------------------------------+-------------------------------------
        Reporter:  vagarenko         |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  high              |            Milestone:  8.2.2
       Component:  Compiler          |              Version:  8.2.1-rc3
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #12791            |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 I think it's basically wrong for the specializer to select a top-level
 instance that might be overlapped by one that's given. However, it would
 be very sad to lose this important optimization in the overwhelmingly more
 common no-overlap case. I think the right goal is this: neither the type
 checker nor the optimizer should have to bend over backwards to worry
 about overlapping instances in the common case that there aren't any. I
 believe that we can look at the future in a few stages:

 ==== Short term ====

 When a potential instance is given, don't specialize to a top-level
 instance if any of the following hold:

 - The instance is marked `OVERLAPPABLE` or `OVERLAPS`.
 - The instance is polymorphic, appears in a module declaring
 `OverlappingInstances`, and is not marked `INCOHERENT`.
 - There is a visible overlapping instance that might match.

 This short-term change doesn't fix the problem in all cases, because an
 instance declared in a module that doesn't mention overlapping can be
 overlapped in an importing module anyway. So we should probably add an
 option to avoid specializing to ''any'' non-`INCOHERENT` polymorphic
 instance when a given could possibly match.

 ==== Short-medium term ====

 Only allow an instance to be overlapped if it's explicitly marked
 `OVERLAPPABLE` or `OVERLAPS`. This is a breaking change, and people will
 gripe, but I don't think there's any less-invasive way to make this even
 ''moderately'' robust. Most of the rest of this comment is about trying to
 make things robust even in the more complicated context of `GADTs`,
 `RankNTypes`, and `ConstraintKinds`.

 Add a `NO_OVERLAP` class declaration pragma to allow users to decree that
 overlapping instances for a particular class are prohibited. Question:
 should the pragma be per-class or per-parameter? I think probably per-
 parameter. Given

 {{{#!hs
 class Foo a {-# NO_OVERLAP #-} b
 }}}

 a constraint like `Foo Int b` is much better behaved than one like `Foo a
 b`.

 ==== Medium-long term ====

 Only allow overlapping instances of a class if the definition of that
 class is explicitly marked with a pragma. There can be two pragmas,
 distinguishing ''semantically significant'' overlap from ''performance-
 only'' overlap. A class allowing semantically significant overlap is
 really for meta-programming only; trying to do anything fancy with it will
 ultimately lead to headaches. My guess is that only *monomorphic*
 constraints involving such a class should be allowed to instantiate
 constraint variables, appear in GADT constructor constraints, or appear in
 higher-rank types.

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