#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Yikes that is really bad. At ''least'' we should get a context-stack overflow. But there is more, as I found when investigating: * At the moment if we have {{{ inert: [D] a ~ ty work item [D] a ~ ty }}} we rewrite the work item with the inert to get `[D] ty ~ ty` and then take a series steps to decompose it. It'd be fast to use `unifyDerived` for this case. * The reason we generate two duplicate Derived constraints is also a bit stupid. Suppose we have `[W] C T a`, where class C has some fundeps, and `a` is a skolem of some kind. From this we might generate a derived `[D] a ~ ty`. This kicks out a derived shadow `[D] C T a` from the inerts. We rewrite it to `[D] C T ty`. ''But then we interact it with the `[W] C T a` in the inert set, to make another derived `[D] a ~ ty`. What a waste of effort. But underlying all this is the question of what ''should'' happen here. The problem is: {{{ [W] C a b --> [D] b ~ Foo beta1 (by fundeps, beta1 fresh unification variable) --> [D] C a (Foo beta1) (rewrite) --> [D] C a beta1 (use instance C a b => C a (Foo b)) }}} and now the cycle repeats. With a hand-written instance decl {{{ instance C a b => C a (Foo b) }}} you rightly need `UndecidableInstances`, but it's less clear what to do when trying to guess the instance context; fail in some way I guess. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"eb55ec2941239dee05afc6be818b129efe51660e/ghc" eb55ec2/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="eb55ec2941239dee05afc6be818b129efe51660e" Refactor functional dependencies a bit * Rename CoAxiom.Eqn = Pair Type to TypeEqn, and use it for fundeps * Use the FunDepEqn for injectivity, which lets us share a bit more code, and (more important) brain cells * When generating fundeps, take the max depth of the two constraints. This aimed at tackling the strange loop in Trac #12860, but there is more to come for that. * Improve pretty-printing with -ddump-tc-trace }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Well my efforts thus far have at least succeeded in getting an error message very promptly {{{ T12860.hs:12:13: error: • Reduction stack overflow; size = 201 When simplifying the following type: C y (Foo x) Use -freduction-depth=0 to disable this check (any upper bound you could choose might fail unpredictably with minor updates to GHC, so disabling the check is recommended if you're sure that type checking should terminate) • When deriving the instance for (C y (Foo x)) }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Resolution: | Keywords: FunDeps Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => FunDeps -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Based on rwbarton's comment:1, it seems that GND should probably reject deriving ''any'' class whose last parameter is determined by a fundep. Is there something wrong with such a rule? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): Well, maybe. The original program and the program in comment:11 have another key difference. The latter uses `UndecidableInstances`, so I suppose it's entirely reasonable that we get a stack overflow error on that one. The former program, on the other hand, does not use `UndecidableInstances`. Really, we ought to reject the former program outright with an error message similar to the one that we get if we leave off `UndecidableInstances` from the latter program: {{{#!hs {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE MultiParamTypeClasses #-} module Bug where class C a b | a -> b where c :: a -> Int newtype Foo a = Foo a instance C b a => C b (Foo a) where c (Foo a) = c a }}} {{{ Bug.hs:12:10: error: • Illegal instance declaration for ‘C b (Foo a)’ The coverage condition fails in class ‘C’ for functional dependency: ‘a -> b’ Reason: lhs type ‘b’ does not determine rhs type ‘Foo a’ Un-determined variable: a Using UndecidableInstances might help • In the instance declaration for ‘C b (Foo a)’ | 12 | instance C b a => C b (Foo a) where | ^^^^^^^^^^^^^^^^^^^^ }}} If we did this, then I would consider this issue resolved. This coverage condition check is performed in `checkValidInstance`. Curiously, we don't call `checkValidInstance` on derived instances at the comment. There are relevant comments [http://git.haskell.org/ghc.git/blob/b14c03737574895718eed786a60dfdfd42ab49ce... here]: {{{#!hs -- checkValidInstance tyvars theta clas inst_tys -- Not necessary; see Note [Exotic derived instance contexts] ; traceTc "TcDeriv" (ppr deriv_rhs $$ ppr theta) -- Claim: the result instance declaration is guaranteed valid -- Hence no need to call: -- checkValidInstance tyvars theta clas inst_tys }}} As this ticket shows, this isn't quite right. So perhaps we need to carve out the bit that checks the coverage condition and just check that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): Another thing I'm unclear on is: should we be calling `checkValidInstance` after //every// iteration of `simplifyDeriv`? Or should we only do it once, after the final inferred context has been found? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): Hm. I tried to use `checkValidInstance`, but there's a big problem: its type signature is not very amenable to being put into `simplifyInstanceContexts`. It is [http://git.haskell.org/ghc.git/blob/fea04defa64871caab6339ff3fc5511a272f37c7... currently]: {{{#!hs checkValidInstance :: UserTypeCtxt -> LHsSigType GhcRn -> Type -> TcM ([TyVar], ThetaType, Class, [Type]) }}} There are two awkward things about this: 1. It expects an `LHsSigType GhcRn` argument, but this isn't available in `simplifyInstanceContexts`. (However, `checkValidInstance` only uses this to get a `SrcSpan`, so perhaps this can be changed to just be a `SrcSpan` argument.) 2. A more awkward sticking point is that `checkValidInstance` expects a `Type` as an argument. This is because it then proceeds to split it with `tcSplitSigmaTy` (and returns the resulting tyvars and theta). However, in `simplifyInstanceContexts`, our instance type is already "pre-split" (that is, we already have the tyvars, theta, class, and class argument types lying around). What's worse, I can't just change the `Type` argument and replace it with the constituent `[TyVar]`, `ThetaType`, etc., since `checkValidInstance` passes that `Type` wholesale to `checkAmbiguity`. So I don't know what to do here. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): I've hit another snag, related to comment:15. I tried putting the call to `checkValidInstance` after `simplifyDeriv` has finished iterating, but that doesn't work for the original program in this ticket. Why? Because during the second iteration of `simplifyDeriv`, we pass the context `C b a` (the result of the first iteration of `simplifyDeriv`) to `solveWantedsAndDrop`. But that leads to the infinite loop described in comment:2, so it's already too late by that point. Naturally, I thought to instead try calling `checkValidInstance` after //every// iteration of `simplifyDeriv`. This does fix the original program, but it causes `T4809.hs` to fail instead. The reason is because of this derived instance: {{{#!hs newtype XMLGenT m a = XMLGenT (m a) deriving (MonadRWS r w s) }}} After the first iteration of `simplifyDeriv`, it produces the context `Monoid w`. We then pass the following instance to `checkValidInstance`: {{{#!hs instance Monoid w => MonadRWS r w s (XMLGenT m) }}} But this doesn't satisfy the coverage condition for `MonadRWS`'s fundeps! (We need `m -> r`, `m -> w`, and `m -> s`.) The final context for this instance, `(MonadReader r m, MonadWriter w m, MonadState s m)`, //does// satisfy the coverage condition, but we don't get this until after a later iteration of `simplifyDeriv`. To sum it up: I can't call `checkValidInstance` at the end, since an intermediate context might throw the simplifier into a loop, but I can't call `checkValidInstance` in the middle either, since an intermediate context might not satisfy the coverage condition. I don't know how to proceed from here. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): I'm afraid that won't work either. `checkInstTermination` only checks the Paterson termination conditions, not the fundep coverage conditions (which are checked separately in `checkInstCoverage`). Indeed, I just tried calling `checkInstTermination` after every iteration of `simplifyDeriv`, but the original program still loops even with that, since `C b a` passes the Paterson termination conditions. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: diatchki (added) Comment: Indeed, I suspect we need a more permissive check than `checkInstCoverage` which would reject `C b a` but not `Monoid w` in the `XMLGenT` example. Alas, I have no idea what that check would be. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12860: GeneralizedNewtypeDeriving + MultiParamTypeClasses sends typechecker into an infinite loop -------------------------------------+------------------------------------- Reporter: RyanGlScott | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.0.1 checker) | Keywords: FunDeps, Resolution: | deriving Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: dfeuer (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12860#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler