Opened 4 years ago

Closed 3 years ago

Last modified 2 years ago

#8550 closed bug (fixed)

GHC builds recursive coerctions when using recursive type families

Reported by: nomeata Owned by:
Priority: high Milestone: 8.0.1
Component: Compiler (Type checker) Version:
Keywords: Cc: goldfire
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: indexed-types/should_fail/T8550
Blocked By: Blocking:
Related Tickets: #7788 Differential Rev(s):
Wiki Page:

Description (last modified by thomie)

Consider

{-# LANGUAGE TypeFamilies, GADTs, UndecidableInstances #-}
type family F a
type instance F () = F ()
data A where
  A :: F () ~ () => A
x :: A
x = A
main = seq A (return ())

On GHC 7.6.3 it yields a context reduction stack overflow (despite F () ~ () being put into the “solved funeqs” list).

In HEAD, a recursive dictionary is built, but then detected:

[1 of 1] Compiling Foo              ( Foo.hs, Foo.o )
        ghc-stage2: panic! (the 'impossible' happened)
          (GHC version 7.7.20131108 for x86_64-unknown-linux):
        	Cycle in coercion bindings
            [[cobox_ayX{v} [lid]
                = CO main:Foo.TFCo:R:F(){tc rob}[0] ; cobox_ayZ{v} [lid],
              cobox_ayZ{v} [lid] = CO cobox_ayX{v} [lid] ; cobox_az0{v} [lid]]]
        
        Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

Either this panic needs to be turned into an error, or we need to prevent recursive dictionaries for when solving funeqs (similar to how we do it for Coercible).

Change History (13)

comment:1 Changed 4 years ago by nomeata

Version: 7.6.3

comment:2 Changed 4 years ago by monoidal

Could you check whether it works now?

comment:3 Changed 4 years ago by nomeata

Yes, same thing. What would make you think it changed since two weeks ago?

comment:4 Changed 4 years ago by monoidal

Sorry, I couldn't reproduce; now I see the panic needs compiling with DEBUG.

comment:5 Changed 4 years ago by nomeata

Ah, ok. Did not try that. What happens when you actually run the code? I assume it will just loop...

comment:6 Changed 4 years ago by monoidal

Right. main = seq A (return ()) loops.

comment:7 Changed 3 years ago by thomie

Description: modified (diff)
Milestone: 7.10.1
Priority: normalhigh

Trying to compile the example from the description with ghc-7.9.20141115 results in GHC using lots of memory, making my machine unusable until I kill the process.

This seems like a regression, setting priority to high.

comment:8 Changed 3 years ago by simonpj

Cc: goldfire added

Richard any comments?

comment:9 Changed 3 years ago by goldfire

This looks like a duplicate of #7788.

comment:10 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone.

comment:11 Changed 3 years ago by Richard Eisenberg <eir@…>

In c1edbdfd9148ad9f74bfe41e76c524f3e775aaaa/ghc:

Do proper depth checking in the flattener to avoid looping.

This implements (roughly) the plan put forward in comment:14:ticket:7788,
fixing #7788, #8550, #9554, #10139, and addressing concerns raised in #10079.
There are some regressions w.r.t. GHC 7.8, but only with pathological type
families (like F a = F a). This also (hopefully -- don't have a test case)
fixes #10158. Unsolved problems include #10184 and #10185, which are both
known deficiencies of the approach used here.

As part of this change, the plumbing around detecting infinite loops has
changed. Instead of -fcontext-stack and -ftype-function-depth, we now have
one combined -freduction-depth parameter. Setting it to 0 disbales the
check, which is now the recommended way to get (terminating) code to
typecheck in releases. (The number of reduction steps may well change between
minor GHC releases!)

This commit also introduces a new IntWithInf type in BasicTypes
that represents an integer+infinity. This type is used in a few
places throughout the code.

Tests in
  indexed-types/should_fail/T7788
  indexed-types/should_fail/T8550
  indexed-types/should_fail/T9554
  indexed-types/should_compile/T10079
  indexed-types/should_compile/T10139
  typecheck/should_compile/T10184  (expected broken)
  typecheck/should_compile/T10185  (expected broken)

This commit also changes performance testsuite numbers, for the better.

comment:12 Changed 3 years ago by goldfire

Resolution: fixed
Status: newclosed
Test Case: indexed-types/should_fail/T8550

comment:13 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

Note: See TracTickets for help on using tickets.