Opened 6 months ago

Closed 5 months ago

#15473 closed bug (fixed)

GHC 8.6+ loops infinitely on an UndecidableInstances error message

Reported by: RyanGlScott Owned by:
Priority: highest Milestone: 8.6.1
Component: Compiler (Type checker) Version: 8.5
Keywords: Cc: simonpj
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case: typecheck/should_compile/T15473
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


This regression was introduced in commit e1b5a1174e42e390855b153015ce5227b3251d89 (Fix a nasty bug in piResultTys), which is present in the ghc-8.6 and master branches. To observe the issue, try compiling the following program:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
-- {-# LANGUAGE UndecidableInstances #-}
module Bug where

type family Undefined :: k where {}

type family LetInterleave xs t ts is (a_ahkO :: [a]) (a_ahkP :: [[a]]) :: [[a]] where
  LetInterleave xs t ts is y z = Undefined y z

You'll get this far:

$ ~/Software/ghc4/inplace/bin/ghc-stage2 Bug.hs
[1 of 1] Compiling Bug              ( Bug.hs, Bug.o )

Bug.hs:11:3: error:
    • Variables ‘a, a’ occur more often
        in the type family application

Before GHC hangs. (I was unable to kill this with Ctrl+C; I had to resort to kill -9.)

Interestingly, the commit f8618a9b15177ee8c84771b927cb3583c9cd8408 (Remove the type-checking knot.) does not appear to have an effect on this.

Change History (6)

comment:2 Changed 5 months ago by Ben Gamari <ben@…>

In 5487f305/ghc:

testsuite: Add (broken) test for #15473

comment:3 Changed 5 months ago by Simon Peyton Jones <simonpj@…>

In db6f1d9/ghc:

Turn infinite loop into a panic

In these two functions
  * TcIface.toIfaceAppTyArgsX
  * Type.piResultTys
we take a type application (f t1 .. tn) and try to find
its kind. It turned out that, if (f t1 .. tn) was ill-kinded
the function would go into an infinite loop.

That's not good: it caused the loop in Trac #15473.

This patch doesn't fix the bug in #15473, but it does turn the
loop into a decent panic, which is a step forward.

comment:4 Changed 5 months ago by Simon Peyton Jones <simonpj@…>

In 8c7f90a/ghc:

Fix a typo in TcValidity.checkFamInstRhs

In error message generation we were using the wrong
type constructor in inst_head.  Result: the type became
ill-kinded, and that sent the compiler into a loop.

A separate patch fixes the loop. This patch fixes the
actual bug -- Trac #15473.

I also improved the "occurs more often" error message
a bit.  But it's still pretty terrible:

    * Variable ‘a’ occurs more often
      in the type family application ‘Undefined’
      than in the instance head ‘LetInterleave xs t ts is y z’

It looks like nonsense, but all becomes clear if you use
-fprint-explicit-kinds.  Really we should fix this by spotting
when invisible arguments are involved and at least suggesting

comment:5 Changed 5 months ago by simonpj

Resolution: fixed
Status: newclosed
Test Case: typecheck/should_compile/T15473

comment:6 Changed 5 months ago by RyanGlScott

Status: closedmerge

I'll be optimistic and mark commits db6f1d9cfc74690798645a7cc5b25040c36bb35d and 8c7f90abcc1e8f9f29b751f23174e8db89ba6983 as merge candidates, since they're both fairly small.

comment:7 Changed 5 months ago by bgamari

Status: mergeclosed

All merged.

Note: See TracTickets for help on using tickets.