How do I determine why ghc is looking for a particular type class instance?

Question

When conditional type class instances run deep, it can be difficult to figure out why ghc is complaining about a missing type class instance. For instance:

class MyClass1 c
class MyClass2 c
class MyClass3 c

data MyType1 a
data MyType2 a

instance MyClass1 a => MyClass2 (MyType1 a)
instance MyClass2 a => MyClass3 (MyType2 a)

foo :: (MyClass3 c) => c
foo = undefined

bar :: MyType2 (MyType1 Int)
bar = foo

GHC gives the following error:

Example.hs:149:7-9: error:
    • No instance for (MyClass1 Int) arising from a use of ‘foo’
    • In the expression: foo
      In an equation for ‘bar’: bar = foo
    |
149 | bar = foo
    |       ^^^

Supposing I only wrote the definitions for foo and bar, and everything else was imported code which I did not write, I may be very confused as to why ghc is attempting to find a MyClass1 instance for Int. This might even be the first time I've ever heard of the MyClass1 class, if so far I've been relying on imported instances. It would be nice if ghc could give me a "stack trace" of the type class instance chain, e.g.

Sought (MyClass2 (MyType1 Int)) to satisfy (MyClass3 (MyType2 (MyType1 Int))) from conditional type class instance OtherModule.hs:37:1-18
Sought (MyClass1 Int) to satisfy (MyClass2 (MyType1 Int)) from conditional type class instance OtherModule.hs:36:1-18

Does ghc have a command line option for this? If not, how do I debug this?

Keep in mind that my real problem is much more complicated than this simple example. e.g.

Search.hs:110:31-36: error:
    • Could not deduce (Ord
                          (Vars (DedupingMap (Rep (Index gc)) (IndexedProblem ac))))
        arising from a use of ‘search’
      from the context: (PP gc (IndexedProblem ac),
                         Show (Vars (DedupingMap (Rep (Index gc)) (IndexedProblem ac))),
                         Foldable f, MonadNotify m)
        bound by the type signature for:
                   searchIndexedReplicaProblem :: forall gc ac (f :: * -> *) (m :: *
                                                                                   -> *).
                                                  (PP gc (IndexedProblem ac),
                                                   Show
                                                     (Vars
                                                        (DedupingMap
                                                           (Rep (Index gc)) (IndexedProblem ac))),
                                                   Foldable f, MonadNotify m) =>
                                                  f (Index
                                                       (Clzs
                                                          (PartitionedProblem
                                                             gc (IndexedProblem ac))))
                                                  -> m (Maybe
                                                          (Vars
                                                             (PartitionedProblem
                                                                gc (IndexedProblem ac))))
        at Search.hs:(103,1)-(109,131)
    • In the expression: search
      In an equation for ‘searchIndexedReplicaProblem’:
          searchIndexedReplicaProblem = search
    |
110 | searchIndexedReplicaProblem = search
    |                               ^^^^^^

There are five coverage conditions for PP, and I'm using type families and undecidable instances, so it's extremely not obvious why ghc is giving me its error. What tools can I use to track down the problem?

Yuras Yuras · Accepted Answer · 2018-06-13T11:48:17

You can try -ddump-cs-trace option, though it is aimed to help GHC devs when debugging constrains solving code, but it could be useful for you too. Here is the output for your example:

Step 1[l:2,d:0] Kept as inert:
    [G] $dMyClass3_a1rt {0}:: MyClass3 c_a1rs[sk:2]
Step 2[l:2,d:0] Dict equal (keep):
    [WD] $dMyClass3_a1rv {0}:: MyClass3 c_a1rs[sk:2]
Constraint solver steps = 2
Step 1[l:1,d:0] Top react: Dict/Top (solved wanted):
    [WD] $dMyClass3_a2uc {0}:: MyClass3 (MyType2 (MyType1 Int))
Step 2[l:1,d:1] Top react: Dict/Top (solved wanted):
    [WD] $dMyClass2_a2up {1}:: MyClass2 (MyType1 Int)
Step 3[l:1,d:2] Kept as inert:
    [WD] $dMyClass1_a2uq {2}:: MyClass1 Int
Step 4[l:2,d:0] Kept as inert:
    [G] $dMyClass3_a1rB {0}:: MyClass3 c_a1rz[sk:2]
Step 5[l:2,d:0] Wanted CallStack IP:
    [WD] $dIP_a2u8 {0}:: ?callStack::GHC.Stack.Types.CallStack
Step 6[l:2,d:0] Kept as inert:
    [WD] $dIP_a2uA {0}:: ?callStack::GHC.Stack.Types.CallStack
Step 7[l:2,d:0] Kept as inert:
    [G] $dMyClass2_a2uh {0}:: MyClass2 a_a2ug[ssk:2]
Step 8[l:2,d:0] Kept as inert:
    [G] $dMyClass1_a2ul {0}:: MyClass1 a_a2uk[ssk:2]
Constraint solver steps = 8

It is not easy to extract useful information from this dump, but AFAIK it is the only available option right now. Few related tickets: 13443, 15044

ADDED: I'll try to explain a bit what the dump means. I'm not actually familiar with GHC internals, so it is just my (probably wrong) understanding.

The relevant bit is the next:

Step 1[l:1,d:0] Top react: Dict/Top (solved wanted):
    [WD] $dMyClass3_a2uc {0}:: MyClass3 (MyType2 (MyType1 Int))
Step 2[l:1,d:1] Top react: Dict/Top (solved wanted):
    [WD] $dMyClass2_a2up {1}:: MyClass2 (MyType1 Int)
Step 3[l:1,d:2] Kept as inert:
    [WD] $dMyClass1_a2uq {2}:: MyClass1 Int

Here d stands for "depth", WD is "wanted derived" constraint. So we have something like a stack trace of wanted constraints: initially we wanted MyClass3 (MyType2 (MyType1 Int)), then we found the MyClass3 instance for MyType2, and now we want MyClass2 (MyType1 Int) to satisfy it. Then we found the MyClass2 instance for MyType1, now we want MyClass1 Int to satisfy it. I know, the explanation is vague, but that is all I have for you, sorry.

How do I determine why ghc is looking for a particular type class instance?

1 Answers