cc_fundeps does not really work
@abel reports here: Here might be a case in the wild from some 2010/11 Haskell legacy code. Compilation succeeds with GHC <= 9.2.3, but breaks with GHC 9.4:
$ cabal install helf-0.2021.8.12 -w ghc-9.4.0.20220523 --allow-newer
[33 of 35] Compiling Closures ( src/Closures.hs, dist/build/helf/helf-tmp/Closures.o )
src/Closures.hs:101:13: error:
• No instance for (MonadCheckExpr
fvar0 Val Env EvalM (ReaderT SigCxt Err))
arising from a use of ‘doEval’
• In the first argument of ‘(.)’, namely ‘doEval’
In the expression: doEval . prettyM
In an equation for ‘prettyM’: prettyM = doEval . prettyM
|
101 | prettyM = doEval . prettyM
| ^^^^^^
The fix is to insert a type application doEval @Head
to resolve fvar0
: https://github.com/andreasabel/helf/commit/ee86c0b47a6db40930ae0f2f4b7ee0a6b5b001c1
Diagnosis
I investigated. Sadly it is a real bug, concerning fundeps, arising from the fix for #19415 (closed). Note [Fundeps with instances]
in GHC.Tc.Solver.Interact says:
Note [Fundeps with instances]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
...
* There is a flag in CDictCan (cc_fundeps :: Bool)
* cc_fundeps = True means
a) The class has fundeps
b) We have not had a successful hit against instances yet
* In doTopFundepImprovement, if we emit some constraints we flip the flag
to False, so that we won't try again with the same CDictCan. In our
example, dwrk will have its flag set to False.
...
Easy! What could go wrong?
* Maybe the class has multiple fundeps, and we get hit with one but not
the other. Per-fundep flags?
* Maybe we get a hit against one instance with one fundep but, after
the work-item is instantiated a bit more, we get a second hit
against a second instance. (This is a pretty strange and
undesirable thing anyway, and can only happen with overlapping
instances; one example is in Note [Weird fundeps].)
But both of these seem extremely exotic, and ignoring them threatens
completeness (fixable with some type signature), but not termination
(not fixable). So for now we are just doing the simplest thing.
Alas, this program tickles the first of these "what could go wrong" bullets. Specifically, we have
class ... => MonadEval head val env m | val -> head, m -> val, m -> env where
instance ... => MonadEval Head Val Env m where
This is pretty bizarre. The fundeps say that in the constraint MonadEval h v e m
, then
for any m
*, we must have v~Val
, and e~Env
; and hence, transitively h~Head
.
Bonkers. But there it is.
(UndecidableInstances
etc are all on.)
Now we are trying to solve
[W] MonadEval h0 v0 e0 EvalM
where h0
, v0
, e0
are all unification variables. So GHC generates v0~Val
and e0~Env
.
But it does not generate h0~Head
because the second parameter is not (yet) Val
.
Now we unify, but alas because of Note [Fundeps with instances]
we no longer look
at fundeps for this constraint, and thereby never emit h0~Head
.
Workaround
Simple fix: make the class decl make explicit the depdency of head
from m
:
class ... => MonadEval head val env m | val -> head, m -> val, m -> env, m -> head where
It's a bit silly, because it's implied, but it solves the problem.
What to do
I am unsure if it's worth losing sleep over this one, given that
- the example is pretty bizarre
- the fix is very easy
Still, I dislike the solver not taking advantage of a useful fundep. One alternative
would be to elaborate cc_fundeps
to a [Bool]
, one for each fundep. Not really hard,
and maybe easier than debugging this next time!
Better ideas welcome.