-- Postcondition: returned Insts are zonked
checkLoop env wanteds
- = go env wanteds (return ())
- where go env wanteds elim_skolems
+ = go env wanteds
+ where go env wanteds
= do { -- We do need to zonk the givens; cf Note [Zonking RedEnv]
; env' <- zonkRedEnv env
; wanteds' <- zonkInsts wanteds
- ; (improved, binds, irreds, elim_more_skolems)
- <- reduceContext env' wanteds'
- ; let elim_skolems' = elim_skolems >> elim_more_skolems
+ ; (improved, binds, irreds) <- reduceContext env' wanteds'
- ; if not improved then
- elim_skolems' >> return (irreds, binds)
+ ; if null irreds || not improved then
+ return (irreds, binds)
else do
-- If improvement did some unification, we go round again.
-- variable which might have been unified, so we'd get an
-- infinite loop if we started again with wanteds!
-- See Note [LOOP]
- { (irreds1, binds1) <- go env' irreds elim_skolems'
+ { (irreds1, binds1) <- go env' irreds
; return (irreds1, binds `unionBags` binds1) } }
\end{code}
-- HOWEVER, some unification may take place, if we instantiate
-- a method Inst with an equality constraint
; let env = mkNoImproveRedEnv doc (\_ -> ReduceMe AddSCs)
- ; (_imp, _binds, constrained_dicts, elim_skolems)
- <- reduceContext env wanteds'
- ; elim_skolems
+ ; (_imp, _binds, constrained_dicts) <- reduceContext env wanteds'
-- Next, figure out the tyvars we will quantify over
; tau_tvs' <- zonkTcTyVarsAndFV (varSetElems tau_tvs)
(is_nested_group || isDict inst) = Stop
| otherwise = ReduceMe AddSCs
env = mkNoImproveRedEnv doc try_me
- ; (_imp, binds, irreds, elim_skolems) <- reduceContext env wanteds'
- ; elim_skolems
+ ; (_imp, binds, irreds) <- reduceContext env wanteds'
-- See "Notes on implicit parameters, Question 4: top level"
; ASSERT( all (isFreeWrtTyVars qtvs) irreds ) -- None should be captured
-- Unusually for checking, we *must* zonk the given_ips
; let env = mkRedEnv doc try_me given_ips'
- ; (improved, binds, irreds, elim_skolems) <- reduceContext env wanteds'
- ; elim_skolems
+ ; (improved, binds, irreds) <- reduceContext env wanteds'
; if not improved then
ASSERT( all is_free irreds )
, red_try_me :: Inst -> WhatToDo
, red_improve :: Bool -- True <=> do improvement
, red_givens :: [Inst] -- All guaranteed rigid
- -- Always dicts
+ -- Always dicts & equalities
-- but see Note [Rigidity]
, red_stack :: (Int, [Inst]) -- Recursion stack (for err msg)
-- See Note [RedStack]
-> [Inst] -- Wanted
-> TcM (ImprovementDone,
TcDictBinds, -- Dictionary bindings
- [Inst], -- Irreducible
- TcM ()) -- Undo skolems from SkolemOccurs
+ [Inst]) -- Irreducible
-reduceContext env wanteds
+reduceContext env wanteds0
= do { traceTc (text "reduceContext" <+> (vcat [
text "----------------------",
red_doc env,
text "given" <+> ppr (red_givens env),
- text "wanted" <+> ppr wanteds,
+ text "wanted" <+> ppr wanteds0,
text "----------------------"
]))
-
- ; let givens = red_givens env
- (given_eqs0, given_dicts0) = partition isEqInst givens
- (wanted_eqs0, wanted_non_eqs) = partition isEqInst wanteds
- (wanted_implics0, wanted_dicts) = partition isImplicInst wanted_non_eqs
-
-- We want to add as wanted equalities those that (transitively)
-- occur in superclass contexts of wanted class constraints.
-- See Note [Ancestor Equalities]
- ; ancestor_eqs <- ancestorEqualities wanted_dicts
- ; let wanted_eqs = wanted_eqs0 ++ ancestor_eqs
+ ; ancestor_eqs <- ancestorEqualities wanteds0
; traceTc $ text "reduceContext: ancestor eqs" <+> ppr ancestor_eqs
- -- 1. Normalise the *given* *equality* constraints
- ; (given_eqs, eliminate_skolems) <- normaliseGivenEqs given_eqs0
-
- -- 2. Normalise the *given* *dictionary* constraints
- -- wrt. the toplevel and given equations
- ; (given_dicts, given_binds) <- normaliseGivenDicts given_eqs
- given_dicts0
-
- -- 5. Build the Avail mapping from "given_dicts"
+ -- Normalise and solve all equality constraints as far as possible
+ -- and normalise all dictionary constraints wrt to the reduced
+ -- equalities. The returned wanted constraints include the
+ -- irreducible wanted equalities.
+ ; let wanteds = wanteds0 ++ ancestor_eqs
+ givens = red_givens env
+ ; (givens',
+ wanteds',
+ normalise_binds,
+ eq_improved) <- tcReduceEqs givens wanteds
+ ; traceTc $ text "reduceContext: tcReduceEqs result" <+> vcat
+ [ppr givens', ppr wanteds', ppr normalise_binds]
+
+ -- Build the Avail mapping from "given_dicts"
; (init_state, _) <- getLIE $ do
- { init_state <- foldlM addGiven emptyAvails given_dicts
+ { init_state <- foldlM addGiven emptyAvails givens'
; return init_state
}
- -- !!! ToDo: what to do with the "extra_givens"? For the
- -- moment I'm simply discarding them, which is probably wrong
-
- -- 6. Solve the *wanted* *dictionary* constraints (not implications)
- -- This may expose some further equational constraints...
+ -- Solve the *wanted* *dictionary* constraints (not implications)
+ -- This may expose some further equational constraints...
+ ; let (wanted_implics, wanted_dicts) = partition isImplicInst wanteds'
; (avails, extra_eqs) <- getLIE (reduceList env wanted_dicts init_state)
- ; (dict_binds, bound_dicts, dict_irreds)
- <- extractResults avails wanted_dicts
- ; traceTc $ text "reduceContext extractresults" <+> vcat
+ ; (dict_binds,
+ bound_dicts,
+ dict_irreds) <- extractResults avails wanted_dicts
+ ; traceTc $ text "reduceContext: extractResults" <+> vcat
[ppr avails, ppr wanted_dicts, ppr dict_binds]
-- Solve the wanted *implications*. In doing so, we can provide
-- as "given" all the dicts that were originally given,
-- *or* for which we now have bindings,
-- *or* which are now irreds
- ; let implic_env = env { red_givens = givens ++ bound_dicts
- ++ dict_irreds }
+ -- NB: Equality irreds need to be converted, as the recursive
+ -- invocation of the solver will still treat them as wanteds
+ -- otherwise.
+ ; let implic_env = env { red_givens
+ = givens ++ bound_dicts ++
+ map wantedToLocalEqInst dict_irreds }
; (implic_binds_s, implic_irreds_s)
- <- mapAndUnzipM (reduceImplication implic_env) wanted_implics0
+ <- mapAndUnzipM (reduceImplication implic_env) wanted_implics
; let implic_binds = unionManyBags implic_binds_s
implic_irreds = concat implic_irreds_s
- -- Normalise the wanted equality constraints
- ; eq_irreds <- normaliseWantedEqs given_eqs (wanted_eqs ++ extra_eqs)
-
- -- Normalise the wanted dictionaries
- ; let irreds = dict_irreds ++ implic_irreds
- eqs = eq_irreds ++ given_eqs
- ; (norm_irreds, normalise_binds) <- normaliseWantedDicts eqs irreds
-
- -- Figure out whether we should go round again. We do so in either
- -- two cases:
- -- (1) If any of the mutable tyvars in givens or irreds has been
- -- filled in by improvement, there is merit in going around
- -- again, because we may make further progress.
- -- (2) If we managed to normalise any dicts, there is merit in going
- -- around gain, because reduceList may be able to get further.
- --
- -- ToDo: We may have exposed new
- -- equality constraints and should probably go round again
- -- then as well. But currently we are dropping them on the
- -- floor anyway.
-
- ; let all_irreds = norm_irreds ++ eq_irreds
- ; improvedMetaTy <- anyM isFilledMetaTyVar $ varSetElems $
- tyVarsOfInsts (givens ++ all_irreds)
- ; let improvedDicts = not $ isEmptyBag normalise_binds
- improved = improvedMetaTy || improvedDicts
-
- -- The old plan (fragile)
- -- improveed = availsImproved avails
- -- || (not $ isEmptyBag normalise_binds1)
- -- || (not $ isEmptyBag normalise_binds2)
- -- || (any isEqInst irreds)
+ -- Collect all irreducible instances, and determine whether we should
+ -- go round again. We do so in either of two cases:
+ -- (1) If dictionary reduction or equality solving led to
+ -- improvement (i.e., instantiated type variables).
+ -- (2) If we uncovered extra equalities. We will try to solve them
+ -- in the next iteration.
+
+ ; let all_irreds = dict_irreds ++ implic_irreds ++ extra_eqs
+ avails_improved = availsImproved avails
+ improvedFlexible = avails_improved || eq_improved
+ extraEqs = (not . null) extra_eqs
+ improved = improvedFlexible || extraEqs
+ --
+ improvedHint = (if avails_improved then " [AVAILS]" else "") ++
+ (if eq_improved then " [EQ]" else "") ++
+ (if extraEqs then " [EXTRA EQS]" else "")
; traceTc (text "reduceContext end" <+> (vcat [
text "----------------------",
red_doc env,
text "given" <+> ppr givens,
- text "given_eqs" <+> ppr given_eqs,
- text "wanted" <+> ppr wanteds,
- text "wanted_dicts" <+> ppr wanted_dicts,
+ text "wanted" <+> ppr wanteds0,
text "----",
text "avails" <+> pprAvails avails,
- text "improved =" <+> ppr improved,
+ text "improved =" <+> ppr improved <+> text improvedHint,
text "(all) irreds = " <+> ppr all_irreds,
text "dict-binds = " <+> ppr dict_binds,
text "implic-binds = " <+> ppr implic_binds,
]))
; return (improved,
- given_binds `unionBags` normalise_binds
- `unionBags` dict_binds
- `unionBags` implic_binds,
- all_irreds,
- eliminate_skolems)
+ normalise_binds `unionBags` dict_binds
+ `unionBags` implic_binds,
+ all_irreds)
}
tcImproveOne :: Avails -> Inst -> TcM ImprovementDone
-- Avails has all the superclasses etc (good)
-- It also has all the intermediates of the deduction (good)
-- It does not have duplicates (good)
- -- NB that (?x::t1) and (?x::t2) will be held separately in avails
- -- so that improve will see them separate
+ -- NB that (?x::t1) and (?x::t2) will be held separately in
+ -- avails so that improve will see them separate
; traceTc (text "improveOne" <+> ppr inst)
; unifyEqns eqns }
-unifyEqns :: [(Equation,(PredType,SDoc),(PredType,SDoc))]
+unifyEqns :: [(Equation, (PredType, SDoc), (PredType, SDoc))]
-> TcM ImprovementDone
unifyEqns [] = return False
unifyEqns eqns
= do { traceTc (ptext (sLit "Improve:") <+> vcat (map pprEquationDoc eqns))
- ; mapM_ unify eqns
- ; return True }
+ ; improved <- mapM unify eqns
+ ; return $ or improved
+ }
where
unify ((qtvs, pairs), what1, what2)
- = addErrCtxtM (mkEqnMsg what1 what2) $ do
- (_, _, tenv) <- tcInstTyVars (varSetElems qtvs)
- mapM_ (unif_pr tenv) pairs
- unif_pr tenv (ty1,ty2) = unifyType (substTy tenv ty1) (substTy tenv ty2)
+ = addErrCtxtM (mkEqnMsg what1 what2) $
+ do { let freeTyVars = unionVarSets (map tvs_pr pairs)
+ `minusVarSet` qtvs
+ ; (_, _, tenv) <- tcInstTyVars (varSetElems qtvs)
+ ; mapM_ (unif_pr tenv) pairs
+ ; anyM isFilledMetaTyVar $ varSetElems freeTyVars
+ }
+
+ unif_pr tenv (ty1, ty2) = unifyType (substTy tenv ty1) (substTy tenv ty2)
+
+ tvs_pr (ty1, ty2) = tyVarsOfType ty1 `unionVarSet` tyVarsOfType ty2
pprEquationDoc :: (Equation, (PredType, SDoc), (PredType, SDoc)) -> SDoc
-pprEquationDoc (eqn, (p1, _), (p2, _)) = vcat [pprEquation eqn, nest 2 (ppr p1), nest 2 (ppr p2)]
+pprEquationDoc (eqn, (p1, _), (p2, _))
+ = vcat [pprEquation eqn, nest 2 (ppr p1), nest 2 (ppr p2)]
mkEqnMsg :: (TcPredType, SDoc) -> (TcPredType, SDoc) -> TidyEnv
-> TcM (TidyEnv, SDoc)
mkEqnMsg (pred1,from1) (pred2,from2) tidy_env
- = do { pred1' <- zonkTcPredType pred1; pred2' <- zonkTcPredType pred2
- ; let { pred1'' = tidyPred tidy_env pred1'; pred2'' = tidyPred tidy_env pred2' }
+ = do { pred1' <- zonkTcPredType pred1
+ ; pred2' <- zonkTcPredType pred2
+ ; let { pred1'' = tidyPred tidy_env pred1'
+ ; pred2'' = tidyPred tidy_env pred2' }
; let msg = vcat [ptext (sLit "When using functional dependencies to combine"),
nest 2 (sep [ppr pred1'' <> comma, nest 2 from1]),
nest 2 (sep [ppr pred2'' <> comma, nest 2 from2])]
-- Base case: we're done!
reduce :: RedEnv -> Inst -> Avails -> TcM Avails
reduce env wanted avails
+
+ -- We don't reduce equalities here (and they must not end up as irreds
+ -- in the Avails!)
+ | isEqInst wanted
+ = return avails
+
-- It's the same as an existing inst, or a superclass thereof
| Just _ <- findAvail avails wanted
= do { traceTc (text "reduce: found " <+> ppr wanted)
-- SLPJ Sept 07: what if improvement happened inside the checkLoop?
-- Then we must iterate the outer loop too!
- ; traceTc (text "reduceImplication condition" <+> ppr ((isEmptyLHsBinds binds) || (null irreds)))
+ ; let backOff = isEmptyLHsBinds binds && -- no new bindings
+ (not $ null irreds) && -- but still some irreds
+ all (not . isEqInst) wanteds
+ -- we may have instantiated a cotv
+ -- => must make a new implication constraint!
+
+ ; traceTc $ text "reduceImplication condition" <+> ppr backOff
--- Progress is no longer measered by the number of bindings
- ; if (isEmptyLHsBinds binds) && (not $ null irreds) then -- No progress
+ -- Progress is no longer measered by the number of bindings
+ ; if backOff then -- No progress
-- If there are any irreds, we back off and do nothing
return (emptyBag, [orig_implic])
else do
availsInsts :: Avails -> [Inst]
availsInsts (Avails _ avails) = keysFM avails
-_availsImproved :: Avails -> ImprovementDone
-_availsImproved (Avails imp _) = imp
+availsImproved :: Avails -> ImprovementDone
+availsImproved (Avails imp _) = imp
\end{code}
Extracting the bindings from a bunch of Avails.
= return (binds, bound_dicts, irreds)
go binds bound_dicts irreds done (w:ws)
+ | isEqInst w
+ = go binds bound_dicts (w:irreds) done' ws
+
| Just done_ids@(done_id : rest_done_ids) <- lookupFM done w
= if w_id `elem` done_ids then
go binds bound_dicts irreds done ws