UndecidableSuperClasses causes the compiler to spin with UndecidableInstances

Looks like I spoke too soon when I said all my examples worked in #10318 (closed) -- 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 (closed).

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.

Trac metadata

Trac field	Value
Version	7.10.3
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler (Type checker)
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tbug Trac import typechecker labels

Trac metadata

Trac field	Value
Version	7.10.3 → 8.0.1-rc1

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.

changed milestone to %8.0.1

changed weight to 7

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

Trac metadata

Trac field	Value
Priority	normal → high

changed weight to 5

ticket:11480#comment:114645 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.

Trac metadata

Trac field	Value
Priority	high → normal

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

With that turned on it spins.

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

I've been bit by this

mentioned in commit ff21795a

mentioned in commit 42c6263f

OK I've fixed both the original report (with the commit in #11480 (closed)) and ticket:11480#comment:114645 (the commit in #11480 (closed)). Pls merge both.

Trac metadata

Trac field	Value
Test case	- → typecheck/should_compile/T11480, polykinds/T11480a

added 1 deleted label

closed

Cherry-picked to ghc-8.0 as 6217147e and e37b571b.

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

removed 1 deleted label

Attached file Categories.hs ($1172).

full test case

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.

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

Trac metadata

Trac field	Value
Test case	typecheck/should_compile/T11480, polykinds/T11480a → typecheck/should_compile/T11480, polykinds/T11480a, polykinds/T11480b

mentioned in issue #11523

mentioned in issue #12131

added PolyKinds UndecidableSuperClasses labels

added Pnormal label