Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#11480 closed bug (fixed)

UndecidableSuperClasses causes the compiler to spin with UndecidableInstances

Reported by: ekmett Owned by:
Priority: normal Milestone: 8.0.1
Component: Compiler (Type checker) Version: 8.0.1-rc1
Keywords: PolyKinds, UndecidableSuperClasses Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: GHC rejects valid program Test Case: typecheck/should_compile/T11480, polykinds/T11480a, polykinds/T11480b
Blocked By: Blocking:
Related Tickets: #10318 Differential Rev(s):
Wiki Page:

Description

Looks like I spoke too soon when I said all my examples worked in #10318 -- it doesn't seem to work when the superclass cycle gets sufficiently interesting, possibly caused by the use of PolyKinds in the style mentioned in #9201.

I took my hask code, and removed the shimming hacks above, and the following stripped down example sends the compiler into an infinite loop, which I believe should be able to work:

{-# language KindSignatures, PolyKinds, TypeFamilies, 
  NoImplicitPrelude, FlexibleContexts,
  MultiParamTypeClasses, GADTs, 
  ConstraintKinds, FlexibleInstances, 
  FunctionalDependencies, UndecidableSuperClasses #-}

import GHC.Types (Constraint)
import qualified Prelude

data Nat (c :: i -> i -> *) (d :: j -> j -> *) (f :: i -> j) (g :: i -> j)

class Functor p (Nat p (->)) p => Category (p :: i -> i -> *)
class (Category dom, Category cod) => Functor (dom :: i -> i -> *) (cod :: j -> j -> *) (f :: i -> j) | f -> dom cod

instance (Category c, Category d) => Category (Nat c d)
instance (Category c, Category d) => Functor (Nat c d) (Nat (Nat c d) (->)) (Nat c d)
instance (Category c, Category d) => Functor (Nat c d) (->) (Nat c d f)

instance Category (->)
instance Functor (->) (->) ((->) e)
instance Functor (->) (Nat (->) (->)) (->)

Sorry for the largish example, but I don't know how to strip it down smaller than the 6 instances that remain.

One potentially telling observation is that without the instances it compiles, and produces what I expect, so the UndecidableSuperClasses part seems to be letting the classes compile, but there seems to be a bad interaction with the way the instances work.

Also, in this stripped down form, I can remove the use of UndecidableInstances and that avoids the spinning problem, but once I flesh it out further I need UndecidableInstances in the "real" version of the problem.

Attachments (1)

Categories.hs (5.3 KB) - added by ekmett 4 years ago.
full test case

Download all attachments as: .zip

Change History (14)

comment:1 Changed 4 years ago by ekmett

Version: 7.10.38.0.1-rc1

comment:2 Changed 4 years ago by ekmett

There also seems to be a bad interaction with the ?callStack machinery.

Here is a differently modified test case:

{-# language KindSignatures, PolyKinds, DataKinds, TypeFamilies, RankNTypes, NoImplicitPrelude, FlexibleContexts, MultiParamTypeClasses, GADTs, ConstraintKinds, FlexibleInstances, TypeOperators, ScopedTypeVariables, UndecidableSuperClasses, FunctionalDependencies #-}

import GHC.Types (Constraint)
import qualified Prelude

data Dict p where
  Dict :: p => Dict p

newtype p :- q = Sub (p => Dict q)

data Nat (c :: i -> i -> *) (d :: j -> j -> *) (f :: i -> j) (g :: i -> j)

class Functor p (Nat p (->)) p => Category (p :: i -> i -> *) where
  type Ob p :: i -> Constraint

class (Category dom, Category cod) => Functor (dom :: i -> i -> *) (cod :: j -> j -> *) (f :: i -> j) | f -> dom cod

bug :: Functor c d f => Ob c a :- Ob d (f a)
bug = Prelude.undefined

I attempted to place undefined there as a placeholder while I worked on the surrounding code, but compiling bug causes

    solveWanteds: too many iterations (limit = 4)
      Unsolved: WC {wc_simple =
                      [W] $dIP_a15a :: ?callStack::GHC.Stack.Types.CallStack (CDictCan)}
      New superclasses found
      Set limit with -fconstraint-solver-iterations=n; n=0 for no limit

Raising the limit gets me right back to the same unsolved constraint.

Without the class cycle, we don't spin forever trying to find a ?callStack.

It seems odd that looking for ?callStack would cause us to unroll superclasses though, as implicit parameters can't be a superclass of any class.

comment:3 Changed 4 years ago by bgamari

Milestone: 8.0.1
Priority: normalhigh

This is something we should try to sort out before the release.

comment:4 Changed 4 years ago by simonpj

Milestone: 8.0.1
Priority: highnormal

comment:2 does indeed suggest a special case. I'll implement that.

Your original example seems to work in HEAD. I'll try the current 8.0 branch.

comment:5 Changed 4 years ago by ekmett

Sorry, I pasted the first example after I removed the UndecidableInstances from the code.

With that turned on it spins.

comment:6 Changed 4 years ago by simonpj

Ah! Correct. I have nailed it. Patch coming.

comment:7 Changed 4 years ago by Iceland_jack

I've been bit by this

comment:8 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

In ff21795a/ghc:

Special-case implicit params in superclass expansion

This issue came up in Trac #11480, and is documented in
Note [When superclasses help] in TcRnTypes.

We were getting a spurious warning
  T11480.hs:1:1: warning:
     solveWanteds: too many iterations (limit = 4)

The fix is easy.  A bit of refactoring along the way.

The original bug report in Trac #11480 appears to work
fine in HEAD and the 8.0 branch but I added a regression
test in this commit as well.

comment:9 Changed 4 years ago by Simon Peyton Jones <simonpj@…>

In 42c6263f/ghc:

Avoid recursive use of immSuperClasses

In fixing Trac #11480 I had omitted to deal with FunDeps.oclose,
which was making recursive use of immSuperClasses, and hence
going into a loop in the recursive case.

Solution: use transSuperClasses, which takes care not to.

comment:10 Changed 4 years ago by simonpj

Status: newmerge
Test Case: typecheck/should_compile/T11480, polykinds/T11480a

OK I've fixed both the original report (with the commit in comment:9) and comment:2 (the commit in comment:8). Pls merge both.

comment:11 Changed 4 years ago by bgamari

Milestone: 8.0.1
Resolution: fixed
Status: mergeclosed

Changed 4 years ago by ekmett

Attachment: Categories.hs added

full test case

comment:12 Changed 4 years ago by ekmett

I've attached the full source file that I was trying to compile when I found this issue.

With the above patches merged in, it compiles clean, but it may supply you with a longer worked example for testing that uses a lot of advanced techniques together.

comment:13 Changed 4 years ago by simonpj

Test Case: typecheck/should_compile/T11480, polykinds/T11480atypecheck/should_compile/T11480, polykinds/T11480a, polykinds/T11480b

Thanks -- I've added your example to the regression suite.

Note: See TracTickets for help on using tickets.