X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Fcompiler%2Ftypecheck%2FTcSimplify.lhs;h=dd4d2158e8d9d854345171f88f8a349db0dd688c;hb=8e67f5502e2e316245806ee3735a2f41a844b611;hp=90fcb9c5406ab99c5f865b4565cd91f993de0ea7;hpb=8edd38dc3555b851ef2a724e69cf997b35bb16c1;p=ghc-hetmet.git diff --git a/ghc/compiler/typecheck/TcSimplify.lhs b/ghc/compiler/typecheck/TcSimplify.lhs index 90fcb9c..dd4d215 100644 --- a/ghc/compiler/typecheck/TcSimplify.lhs +++ b/ghc/compiler/typecheck/TcSimplify.lhs @@ -9,7 +9,8 @@ module TcSimplify ( tcSimplifyInfer, tcSimplifyInferCheck, tcSimplifyCheck, tcSimplifyRestricted, - tcSimplifyToDicts, tcSimplifyIPs, tcSimplifyTop, + tcSimplifyToDicts, tcSimplifyIPs, + tcSimplifyTop, tcSimplifyInteractive, tcSimplifyBracket, tcSimplifyDeriv, tcSimplifyDefault, @@ -20,51 +21,52 @@ module TcSimplify ( import {-# SOURCE #-} TcUnify( unifyTauTy ) import TcEnv -- temp -import HsSyn ( MonoBinds(..), HsExpr(..), andMonoBinds, andMonoBindList ) -import TcHsSyn ( TcExpr, TcId, - TcMonoBinds, TcDictBinds - ) +import HsSyn ( HsBind(..), HsExpr(..), LHsExpr, emptyLHsBinds ) +import TcHsSyn ( TcId, TcDictBinds, mkHsApp, mkHsTyApp, mkHsDictApp ) import TcRnMonad import Inst ( lookupInst, LookupInstResult(..), - tyVarsOfInst, fdPredsOfInsts, fdPredsOfInst, newDicts, + tyVarsOfInst, fdPredsOfInsts, newDicts, isDict, isClassDict, isLinearInst, linearInstType, isStdClassTyVarDict, isMethodFor, isMethod, instToId, tyVarsOfInsts, cloneDict, ipNamesOfInsts, ipNamesOfInst, dictPred, - instBindingRequired, instCanBeGeneralised, + instBindingRequired, fdPredsOfInst, newDictsFromOld, tcInstClassOp, getDictClassTys, isTyVarDict, instLoc, zonkInst, tidyInsts, tidyMoreInsts, - Inst, pprInsts, pprInstsInFull, - isIPDict, isInheritableInst + Inst, pprInsts, pprDictsInFull, pprInstInFull, tcGetInstEnvs, + isInheritableInst, pprDFuns, pprDictsTheta ) -import TcEnv ( tcGetGlobalTyVars, tcGetInstEnv, tcLookupId, findGlobals ) -import InstEnv ( lookupInstEnv, classInstEnv, InstLookupResult(..) ) +import TcEnv ( tcGetGlobalTyVars, tcLookupId, findGlobals, pprBinders ) +import InstEnv ( lookupInstEnv, classInstances ) import TcMType ( zonkTcTyVarsAndFV, tcInstTyVars, checkAmbiguity ) -import TcType ( TcTyVar, TcTyVarSet, ThetaType, TyVarDetails(VanillaTv), - mkClassPred, isOverloadedTy, mkTyConApp, +import TcType ( TcTyVar, TcTyVarSet, ThetaType, + mkClassPred, isOverloadedTy, mkTyConApp, mkTyVarTy, tcGetTyVar, isTyVarClassPred, mkTyVarTys, - tyVarsOfPred ) + tyVarsOfPred, tcEqType, pprPred ) import Id ( idType, mkUserLocal ) import Var ( TyVar ) -import Name ( getOccName, getSrcLoc ) +import Name ( Name, getOccName, getSrcLoc ) import NameSet ( NameSet, mkNameSet, elemNameSet ) -import Class ( classBigSig ) +import Class ( classBigSig, classKey ) import FunDeps ( oclose, grow, improve, pprEquationDoc ) -import PrelInfo ( isNumericClass, isCreturnableClass, isCcallishClass ) -import PrelNames ( splitName, fstName, sndName ) - -import Subst ( mkTopTyVarSubst, substTheta, substTy ) -import TysWiredIn ( unitTy, pairTyCon ) +import PrelInfo ( isNumericClass ) +import PrelNames ( splitName, fstName, sndName, integerTyConName, + showClassKey, eqClassKey, ordClassKey ) +import Type ( zipTopTvSubst, substTheta, substTy ) +import TysWiredIn ( pairTyCon, doubleTy ) import ErrUtils ( Message ) +import BasicTypes ( TopLevelFlag, isNotTopLevel ) import VarSet import VarEnv ( TidyEnv ) import FiniteMap +import Bag import Outputable import ListSetOps ( equivClasses ) -import Util ( zipEqual ) +import Util ( zipEqual, isSingleton ) import List ( partition ) +import SrcLoc ( Located(..) ) import CmdLineOpts \end{code} @@ -76,6 +78,60 @@ import CmdLineOpts %************************************************************************ -------------------------------------- + Notes on functional dependencies (a bug) + -------------------------------------- + +| > class Foo a b | a->b +| > +| > class Bar a b | a->b +| > +| > data Obj = Obj +| > +| > instance Bar Obj Obj +| > +| > instance (Bar a b) => Foo a b +| > +| > foo:: (Foo a b) => a -> String +| > foo _ = "works" +| > +| > runFoo:: (forall a b. (Foo a b) => a -> w) -> w +| > runFoo f = f Obj +| +| *Test> runFoo foo +| +| :1: +| Could not deduce (Bar a b) from the context (Foo a b) +| arising from use of `foo' at :1 +| Probable fix: +| Add (Bar a b) to the expected type of an expression +| In the first argument of `runFoo', namely `foo' +| In the definition of `it': it = runFoo foo +| +| Why all of the sudden does GHC need the constraint Bar a b? The +| function foo didn't ask for that... + +The trouble is that to type (runFoo foo), GHC has to solve the problem: + + Given constraint Foo a b + Solve constraint Foo a b' + +Notice that b and b' aren't the same. To solve this, just do +improvement and then they are the same. But GHC currently does + simplify constraints + apply improvement + and loop + +That is usually fine, but it isn't here, because it sees that Foo a b is +not the same as Foo a b', and so instead applies the instance decl for +instance Bar a b => Foo a b. And that's where the Bar constraint comes +from. + +The Right Thing is to improve whenever the constraint set changes at +all. Not hard in principle, but it'll take a bit of fiddling to do. + + + + -------------------------------------- Notes on quantification -------------------------------------- @@ -305,6 +361,36 @@ but we'll produce the non-principal type -------------------------------------- + The need for forall's in constraints + -------------------------------------- + +[Exchange on Haskell Cafe 5/6 Dec 2000] + + class C t where op :: t -> Bool + instance C [t] where op x = True + + p y = (let f :: c -> Bool; f x = op (y >> return x) in f, y ++ []) + q y = (y ++ [], let f :: c -> Bool; f x = op (y >> return x) in f) + +The definitions of p and q differ only in the order of the components in +the pair on their right-hand sides. And yet: + + ghc and "Typing Haskell in Haskell" reject p, but accept q; + Hugs rejects q, but accepts p; + hbc rejects both p and q; + nhc98 ... (Malcolm, can you fill in the blank for us!). + +The type signature for f forces context reduction to take place, and +the results of this depend on whether or not the type of y is known, +which in turn depends on which component of the pair the type checker +analyzes first. + +Solution: if y::m a, float out the constraints + Monad m, forall c. C (m c) +When m is later unified with [], we can solve both constraints. + + + -------------------------------------- Notes on implicit parameters -------------------------------------- @@ -423,6 +509,21 @@ you might not expect the addition to be done twice --- but it will if we follow the argument of Question 2 and generalise over ?y. +Question 4: top level +~~~~~~~~~~~~~~~~~~~~~ +At the top level, monomorhism makes no sense at all. + + module Main where + main = let ?x = 5 in print foo + + foo = woggle 3 + + woggle :: (?x :: Int) => Int -> Int + woggle y = ?x + y + +We definitely don't want (foo :: Int) with a top-level implicit parameter +(?x::Int) becuase there is no way to bind it. + Possible choices ~~~~~~~~~~~~~~~~ @@ -549,9 +650,6 @@ tcSimplifyInfer doc tau_tvs wanted_lie = inferLoop doc (varSetElems tau_tvs) wanted_lie `thenM` \ (qtvs, frees, binds, irreds) -> - -- Check for non-generalisable insts - mappM_ addCantGenErr (filter (not . instCanBeGeneralised) irreds) `thenM_` - extendLIEs frees `thenM_` returnM (qtvs, binds, map instToId irreds) @@ -569,6 +667,8 @@ inferLoop doc tau_tvs wanteds | isClassDict inst = DontReduceUnlessConstant -- Dicts | otherwise = ReduceMe -- Lits and Methods in + traceTc (text "infloop" <+> vcat [ppr tau_tvs', ppr wanteds', ppr preds, + ppr (grow preds tau_tvs'), ppr qtvs]) `thenM_` -- Step 2 reduceContext doc try_me [] wanteds' `thenM` \ (no_improvement, frees, binds, irreds) -> @@ -592,7 +692,7 @@ inferLoop doc tau_tvs wanteds -- the final qtvs might be empty. See [NO TYVARS] below. inferLoop doc tau_tvs (irreds ++ frees) `thenM` \ (qtvs1, frees1, binds1, irreds1) -> - returnM (qtvs1, frees1, binds `AndMonoBinds` binds1, irreds1) + returnM (qtvs1, frees1, binds `unionBags` binds1, irreds1) \end{code} Example [LOOP] @@ -682,7 +782,8 @@ tcSimplifyCheck doc qtvs givens wanted_lie givens wanted_lie `thenM` \ (qtvs', binds) -> returnM binds where - get_qtvs = zonkTcTyVarsAndFV qtvs +-- get_qtvs = zonkTcTyVarsAndFV qtvs + get_qtvs = return (mkVarSet qtvs) -- tcSimplifyInferCheck is used when we know the constraints we are to simplify @@ -728,20 +829,25 @@ tcSimplCheck doc get_qtvs givens wanted_lie = check_loop givens wanted_lie `thenM` \ (qtvs, frees, binds, irreds) -> -- Complain about any irreducible ones - complainCheck doc givens irreds `thenM_` + mappM zonkInst given_dicts_and_ips `thenM` \ givens' -> + groupErrs (addNoInstanceErrs (Just doc) givens') irreds `thenM_` -- Done - extendLIEs frees `thenM_` + extendLIEs frees `thenM_` returnM (qtvs, binds) where + given_dicts_and_ips = filter (not . isMethod) givens + -- For error reporting, filter out methods, which are + -- only added to the given set as an optimisation + ip_set = mkNameSet (ipNamesOfInsts givens) check_loop givens wanteds = -- Step 1 mappM zonkInst givens `thenM` \ givens' -> mappM zonkInst wanteds `thenM` \ wanteds' -> - get_qtvs `thenM` \ qtvs' -> + get_qtvs `thenM` \ qtvs' -> -- Step 2 let @@ -757,7 +863,7 @@ tcSimplCheck doc get_qtvs givens wanted_lie returnM (varSetElems qtvs', frees, binds, irreds) else check_loop givens' (irreds ++ frees) `thenM` \ (qtvs', frees1, binds1, irreds1) -> - returnM (qtvs', frees1, binds `AndMonoBinds` binds1, irreds1) + returnM (qtvs', frees1, binds `unionBags` binds1, irreds1) \end{code} @@ -767,44 +873,143 @@ tcSimplCheck doc get_qtvs givens wanted_lie %* * %************************************************************************ +tcSimplifyRestricted infers which type variables to quantify for a +group of restricted bindings. This isn't trivial. + +Eg1: id = \x -> x + We want to quantify over a to get id :: forall a. a->a + +Eg2: eq = (==) + We do not want to quantify over a, because there's an Eq a + constraint, so we get eq :: a->a->Bool (notice no forall) + +So, assume: + RHS has type 'tau', whose free tyvars are tau_tvs + RHS has constraints 'wanteds' + +Plan A (simple) + Quantify over (tau_tvs \ ftvs(wanteds)) + This is bad. The constraints may contain (Monad (ST s)) + where we have instance Monad (ST s) where... + so there's no need to be monomorphic in s! + + Also the constraint might be a method constraint, + whose type mentions a perfectly innocent tyvar: + op :: Num a => a -> b -> a + Here, b is unconstrained. A good example would be + foo = op (3::Int) + We want to infer the polymorphic type + foo :: forall b. b -> b + + +Plan B (cunning, used for a long time up to and including GHC 6.2) + Step 1: Simplify the constraints as much as possible (to deal + with Plan A's problem). Then set + qtvs = tau_tvs \ ftvs( simplify( wanteds ) ) + + Step 2: Now simplify again, treating the constraint as 'free' if + it does not mention qtvs, and trying to reduce it otherwise. + The reasons for this is to maximise sharing. + + This fails for a very subtle reason. Suppose that in the Step 2 + a constraint (Foo (Succ Zero) (Succ Zero) b) gets thrown upstairs as 'free'. + In the Step 1 this constraint might have been simplified, perhaps to + (Foo Zero Zero b), AND THEN THAT MIGHT BE IMPROVED, to bind 'b' to 'T'. + This won't happen in Step 2... but that in turn might prevent some other + constraint (Baz [a] b) being simplified (e.g. via instance Baz [a] T where {..}) + and that in turn breaks the invariant that no constraints are quantified over. + + Test typecheck/should_compile/tc177 (which failed in GHC 6.2) demonstrates + the problem. + + +Plan C (brutal) + Step 1: Simplify the constraints as much as possible (to deal + with Plan A's problem). Then set + qtvs = tau_tvs \ ftvs( simplify( wanteds ) ) + Return the bindings from Step 1. + + +A note about Plan C (arising from "bug" reported by George Russel March 2004) +Consider this: + + instance (HasBinary ty IO) => HasCodedValue ty + + foo :: HasCodedValue a => String -> IO a + + doDecodeIO :: HasCodedValue a => () -> () -> IO a + doDecodeIO codedValue view + = let { act = foo "foo" } in act + +You might think this should work becuase the call to foo gives rise to a constraint +(HasCodedValue t), which can be satisfied by the type sig for doDecodeIO. But the +restricted binding act = ... calls tcSimplifyRestricted, and PlanC simplifies the +constraint using the (rather bogus) instance declaration, and now we are stuffed. + +I claim this is not really a bug -- but it bit Sergey as well as George. So here's +plan D + + +Plan D (a variant of plan B) + Step 1: Simplify the constraints as much as possible (to deal + with Plan A's problem), BUT DO NO IMPROVEMENT. Then set + qtvs = tau_tvs \ ftvs( simplify( wanteds ) ) + + Step 2: Now simplify again, treating the constraint as 'free' if + it does not mention qtvs, and trying to reduce it otherwise. + + The point here is that it's generally OK to have too few qtvs; that is, + to make the thing more monomorphic than it could be. We don't want to + do that in the common cases, but in wierd cases it's ok: the programmer + can always add a signature. + + Too few qtvs => too many wanteds, which is what happens if you do less + improvement. + + \begin{code} tcSimplifyRestricted -- Used for restricted binding groups -- i.e. ones subject to the monomorphism restriction :: SDoc + -> TopLevelFlag + -> [Name] -- Things bound in this group -> TcTyVarSet -- Free in the type of the RHSs -> [Inst] -- Free in the RHSs -> TcM ([TcTyVar], -- Tyvars to quantify (zonked) TcDictBinds) -- Bindings + -- tcSimpifyRestricted returns no constraints to + -- quantify over; by definition there are none. + -- They are all thrown back in the LIE -tcSimplifyRestricted doc tau_tvs wanteds - = -- First squash out all methods, to find the constrained tyvars - -- We can't just take the free vars of wanted_lie because that'll - -- have methods that may incidentally mention entirely unconstrained variables - -- e.g. a call to f :: Eq a => a -> b -> b - -- Here, b is unconstrained. A good example would be - -- foo = f (3::Int) - -- We want to infer the polymorphic type - -- foo :: forall b. b -> b - let - try_me inst = ReduceMe -- Reduce as far as we can. Don't stop at - -- dicts; the idea is to get rid of as many type - -- variables as possible, and we don't want to stop - -- at (say) Monad (ST s), because that reduces - -- immediately, with no constraint on s. - in - simpleReduceLoop doc try_me wanteds `thenM` \ (_, _, constrained_dicts) -> +tcSimplifyRestricted doc top_lvl bndrs tau_tvs wanteds + -- Zonk everything in sight + = mappM zonkInst wanteds `thenM` \ wanteds' -> + zonkTcTyVarsAndFV (varSetElems tau_tvs) `thenM` \ tau_tvs' -> + tcGetGlobalTyVars `thenM` \ gbl_tvs' -> + + -- 'reduceMe': Reduce as far as we can. Don't stop at + -- dicts; the idea is to get rid of as many type + -- variables as possible, and we don't want to stop + -- at (say) Monad (ST s), because that reduces + -- immediately, with no constraint on s. + -- + -- BUT do no improvement! See Plan D above + reduceContextWithoutImprovement + doc reduceMe wanteds' `thenM` \ (_frees, _binds, constrained_dicts) -> -- Next, figure out the tyvars we will quantify over - zonkTcTyVarsAndFV (varSetElems tau_tvs) `thenM` \ tau_tvs' -> - tcGetGlobalTyVars `thenM` \ gbl_tvs -> let constrained_tvs = tyVarsOfInsts constrained_dicts - qtvs = (tau_tvs' `minusVarSet` oclose (fdPredsOfInsts constrained_dicts) gbl_tvs) + qtvs = (tau_tvs' `minusVarSet` oclose (fdPredsOfInsts constrained_dicts) gbl_tvs') `minusVarSet` constrained_tvs in + traceTc (text "tcSimplifyRestricted" <+> vcat [ + pprInsts wanteds, pprInsts _frees, pprInsts constrained_dicts, + ppr _binds, + ppr constrained_tvs, ppr tau_tvs', ppr qtvs ]) `thenM_` -- The first step may have squashed more methods than - -- necessary, so try again, this time knowing the exact + -- necessary, so try again, this time more gently, knowing the exact -- set of type variables to quantify over. -- -- We quantify only over constraints that are captured by qtvs; @@ -816,19 +1021,30 @@ tcSimplifyRestricted doc tau_tvs wanteds -- Remember that we may need to do *some* simplification, to -- (for example) squash {Monad (ST s)} into {}. It's not enough -- just to float all constraints - mappM zonkInst wanteds `thenM` \ wanteds' -> + -- + -- At top level, we *do* squash methods becuase we want to + -- expose implicit parameters to the test that follows let - try_me inst | isFreeWrtTyVars qtvs inst = Free - | otherwise = ReduceMe + is_nested_group = isNotTopLevel top_lvl + try_me inst | isFreeWrtTyVars qtvs inst, + (is_nested_group || isDict inst) = Free + | otherwise = ReduceMe in - reduceContext doc try_me [] wanteds' `thenM` \ (no_improvement, frees, binds, irreds) -> - ASSERT( no_improvement ) + reduceContextWithoutImprovement + doc try_me wanteds' `thenM` \ (frees, binds, irreds) -> ASSERT( null irreds ) - -- No need to loop because simpleReduceLoop will have - -- already done any improvement necessary - extendLIEs frees `thenM_` - returnM (varSetElems qtvs, binds) + -- See "Notes on implicit parameters, Question 4: top level" + if is_nested_group then + extendLIEs frees `thenM_` + returnM (varSetElems qtvs, binds) + else + let + (non_ips, bad_ips) = partition isClassDict frees + in + addTopIPErrs bndrs bad_ips `thenM_` + extendLIEs non_ips `thenM_` + returnM (varSetElems qtvs, binds) \end{code} @@ -875,7 +1091,7 @@ because the scsel will mess up matching. Instead we want forall dIntegralInt, dNumInt. fromIntegral Int Int dIntegralInt dNumInt = id Int -Hence "DontReduce NoSCs" +Hence "WithoutSCs" \begin{code} tcSimplifyToDicts :: [Inst] -> TcM (TcDictBinds) @@ -891,7 +1107,7 @@ tcSimplifyToDicts wanteds doc = text "tcSimplifyToDicts" -- Reduce methods and lits only; stop as soon as we get a dictionary - try_me inst | isDict inst = DontReduce NoSCs + try_me inst | isDict inst = KeepDictWithoutSCs -- See notes above re "WithoutSCs" | otherwise = ReduceMe \end{code} @@ -907,12 +1123,10 @@ this bracket again at its usage site. \begin{code} tcSimplifyBracket :: [Inst] -> TcM () tcSimplifyBracket wanteds - = simpleReduceLoop doc try_me wanteds `thenM_` + = simpleReduceLoop doc reduceMe wanteds `thenM_` returnM () - where - doc = text "tcSimplifyBracket" - try_me inst = ReduceMe + doc = text "tcSimplifyBracket" \end{code} @@ -963,7 +1177,7 @@ tcSimplifyIPs given_ips wanteds returnM (frees, binds) else simpl_loop givens' (irreds ++ frees) `thenM` \ (frees1, binds1) -> - returnM (frees1, binds `AndMonoBinds` binds1) + returnM (frees1, binds `unionBags` binds1) \end{code} @@ -993,30 +1207,37 @@ For each method @Inst@ in the @init_lie@ that mentions one of the @LIE@), as well as the @HsBinds@ generated. \begin{code} -bindInstsOfLocalFuns :: [Inst] -> [TcId] -> TcM TcMonoBinds +bindInstsOfLocalFuns :: [Inst] -> [TcId] -> TcM TcDictBinds +-- Simlifies only MethodInsts, and generate only bindings of form +-- fm = f tys dicts +-- We're careful not to even generate bindings of the form +-- d1 = d2 +-- You'd think that'd be fine, but it interacts with what is +-- arguably a bug in Match.tidyEqnInfo (see notes there) bindInstsOfLocalFuns wanteds local_ids | null overloaded_ids -- Common case = extendLIEs wanteds `thenM_` - returnM EmptyMonoBinds + returnM emptyLHsBinds | otherwise - = simpleReduceLoop doc try_me wanteds `thenM` \ (frees, binds, irreds) -> + = simpleReduceLoop doc try_me for_me `thenM` \ (frees, binds, irreds) -> ASSERT( null irreds ) + extendLIEs not_for_me `thenM_` extendLIEs frees `thenM_` returnM binds where doc = text "bindInsts" <+> ppr local_ids overloaded_ids = filter is_overloaded local_ids is_overloaded id = isOverloadedTy (idType id) + (for_me, not_for_me) = partition (isMethodFor overloaded_set) wanteds overloaded_set = mkVarSet overloaded_ids -- There can occasionally be a lot of them -- so it's worth building a set, so that -- lookup (in isMethodFor) is faster - - try_me inst | isMethodFor overloaded_set inst = ReduceMe - | otherwise = Free + try_me inst | isMethod inst = ReduceMe + | otherwise = Free \end{code} @@ -1037,7 +1258,8 @@ data WhatToDo -- produce an error message of any kind. -- It might be quite legitimate such as (Eq a)! - | DontReduce WantSCs -- Return as irreducible + | KeepDictWithoutSCs -- Return as irreducible; don't add its superclasses + -- Rather specialised: see notes with tcSimplifyToDicts | DontReduceUnlessConstant -- Return as irreducible unless it can -- be reduced to a constant in one step @@ -1055,6 +1277,7 @@ data WantSCs = NoSCs | AddSCs -- Tells whether we should add the superclasses \begin{code} type Avails = FiniteMap Inst Avail +emptyAvails = emptyFM data Avail = IsFree -- Used for free Insts @@ -1067,9 +1290,10 @@ data Avail | NoRhs -- Used for Insts like (CCallable f) -- where no witness is required. + -- ToDo: remove? | Rhs -- Used when there is a RHS - TcExpr -- The RHS + (LHsExpr TcId) -- The RHS [Inst] -- Insts free in the RHS; we need these too | Linear -- Splittable Insts only. @@ -1081,7 +1305,7 @@ data Avail | LinRhss -- Splittable Insts only; this is used only internally -- by extractResults, where a Linear -- is turned into an LinRhss - [TcExpr] -- A supply of suitable RHSs + [LHsExpr TcId] -- A supply of suitable RHSs pprAvails avails = vcat [sep [ppr inst, nest 2 (equals <+> pprAvail avail)] | (inst,avail) <- fmToList avails ] @@ -1109,11 +1333,11 @@ The loop startes extractResults :: Avails -> [Inst] -- Wanted -> TcM (TcDictBinds, -- Bindings - [Inst], -- Irreducible ones - [Inst]) -- Free ones + [Inst], -- Irreducible ones + [Inst]) -- Free ones extractResults avails wanteds - = go avails EmptyMonoBinds [] [] wanteds + = go avails emptyBag [] [] wanteds where go avails binds irreds frees [] = returnM (binds, irreds, frees) @@ -1130,7 +1354,7 @@ extractResults avails wanteds Just (Given id _) -> go avails new_binds irreds frees ws where new_binds | id == instToId w = binds - | otherwise = addBind binds w (HsVar id) + | otherwise = addBind binds w (L (instSpan w) (HsVar id)) -- The sought Id can be one of the givens, via a superclass chain -- and then we definitely don't want to generate an x=x binding! @@ -1142,7 +1366,7 @@ extractResults avails wanteds -> get_root irreds frees avail w `thenM` \ (irreds', frees', root_id) -> split n (instToId split_inst) root_id w `thenM` \ (binds', rhss) -> go (addToFM avails w (LinRhss rhss)) - (binds `AndMonoBinds` binds') + (binds `unionBags` binds') irreds' frees' (split_inst : w : ws) Just (LinRhss (rhs:rhss)) -- Consume one of the Rhss @@ -1184,7 +1408,7 @@ extractResults avails wanteds split :: Int -> TcId -> TcId -> Inst - -> TcM (TcDictBinds, [TcExpr]) + -> TcM (TcDictBinds, [LHsExpr TcId]) -- (split n split_id root_id wanted) returns -- * a list of 'n' expressions, all of which witness 'avail' -- * a bunch of auxiliary bindings to support these expressions @@ -1201,12 +1425,13 @@ split n split_id root_id wanted id = instToId wanted occ = getOccName id loc = getSrcLoc id + span = instSpan wanted - go 1 = returnM (EmptyMonoBinds, [HsVar root_id]) + go 1 = returnM (emptyBag, [L span $ HsVar root_id]) go n = go ((n+1) `div` 2) `thenM` \ (binds1, rhss) -> expand n rhss `thenM` \ (binds2, rhss') -> - returnM (binds1 `AndMonoBinds` binds2, rhss') + returnM (binds1 `unionBags` binds2, rhss') -- (expand n rhss) -- Given ((n+1)/2) rhss, make n rhss, using auxiliary bindings @@ -1219,7 +1444,7 @@ split n split_id root_id wanted returnM (binds', head rhss : rhss') where go rhss = mapAndUnzipM do_one rhss `thenM` \ (binds', rhss') -> - returnM (andMonoBindList binds', concat rhss') + returnM (listToBag binds', concat rhss') do_one rhs = newUnique `thenM` \ uniq -> tcLookupId fstName `thenM` \ fst_id -> @@ -1227,14 +1452,16 @@ split n split_id root_id wanted let x = mkUserLocal occ uniq pair_ty loc in - returnM (VarMonoBind x (mk_app split_id rhs), - [mk_fs_app fst_id ty x, mk_fs_app snd_id ty x]) + returnM (L span (VarBind x (mk_app span split_id rhs)), + [mk_fs_app span fst_id ty x, mk_fs_app span snd_id ty x]) -mk_fs_app id ty var = HsVar id `TyApp` [ty,ty] `HsApp` HsVar var +mk_fs_app span id ty var = L span (HsVar id) `mkHsTyApp` [ty,ty] `mkHsApp` (L span (HsVar var)) -mk_app id rhs = HsApp (HsVar id) rhs +mk_app span id rhs = L span (HsApp (L span (HsVar id)) rhs) -addBind binds inst rhs = binds `AndMonoBinds` VarMonoBind (instToId inst) rhs +addBind binds inst rhs = binds `unionBags` unitBag (L (instLocSrcSpan (instLoc inst)) + (VarBind (instToId inst) rhs)) +instSpan wanted = instLocSrcSpan (instLoc wanted) \end{code} @@ -1265,7 +1492,7 @@ simpleReduceLoop doc try_me wanteds returnM (frees, binds, irreds) else simpleReduceLoop doc try_me (irreds ++ frees) `thenM` \ (frees1, binds1, irreds1) -> - returnM (frees1, binds `AndMonoBinds` binds1, irreds1) + returnM (frees1, binds `unionBags` binds1, irreds1) \end{code} @@ -1291,7 +1518,7 @@ reduceContext doc try_me givens wanteds ])) `thenM_` -- Build the Avail mapping from "givens" - foldlM addGiven emptyFM givens `thenM` \ init_state -> + foldlM addGiven emptyAvails givens `thenM` \ init_state -> -- Do the real work reduceList (0,[]) try_me wanteds init_state `thenM` \ avails -> @@ -1316,20 +1543,60 @@ reduceContext doc try_me givens wanteds returnM (no_improvement, frees, binds, irreds) +-- reduceContextWithoutImprovement differs from reduceContext +-- (a) no improvement +-- (b) 'givens' is assumed empty +reduceContextWithoutImprovement doc try_me wanteds + = + traceTc (text "reduceContextWithoutImprovement" <+> (vcat [ + text "----------------------", + doc, + text "wanted" <+> ppr wanteds, + text "----------------------" + ])) `thenM_` + + -- Do the real work + reduceList (0,[]) try_me wanteds emptyAvails `thenM` \ avails -> + extractResults avails wanteds `thenM` \ (binds, irreds, frees) -> + + traceTc (text "reduceContextWithoutImprovement end" <+> (vcat [ + text "----------------------", + doc, + text "wanted" <+> ppr wanteds, + text "----", + text "avails" <+> pprAvails avails, + text "frees" <+> ppr frees, + text "----------------------" + ])) `thenM_` + + returnM (frees, binds, irreds) + +tcImprove :: Avails -> TcM Bool -- False <=> no change +-- Perform improvement using all the predicates in Avails tcImprove avails - = tcGetInstEnv `thenM` \ inst_env -> + = tcGetInstEnvs `thenM` \ inst_envs -> let preds = [ (pred, pp_loc) - | inst <- keysFM avails, - let pp_loc = pprInstLoc (instLoc inst), - pred <- fdPredsOfInst inst + | (inst, avail) <- fmToList avails, + pred <- get_preds inst avail, + let pp_loc = pprInstLoc (instLoc inst) ] -- 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 - eqns = improve (classInstEnv inst_env) preds + + -- For free Methods, we want to take predicates from their context, + -- but for Methods that have been squished their context will already + -- be in Avails, and we don't want duplicates. Hence this rather + -- horrid get_preds function + get_preds inst IsFree = fdPredsOfInst inst + get_preds inst other | isDict inst = [dictPred inst] + | otherwise = [] + + eqns = improve get_insts preds + get_insts clas = classInstances inst_envs clas in if null eqns then returnM True @@ -1338,10 +1605,11 @@ tcImprove avails mappM_ unify eqns `thenM_` returnM False where - unify ((qtvs, t1, t2), doc) - = addErrCtxt doc $ - tcInstTyVars VanillaTv (varSetElems qtvs) `thenM` \ (_, _, tenv) -> - unifyTauTy (substTy tenv t1) (substTy tenv t2) + unify ((qtvs, pairs), doc) + = addErrCtxt doc $ + tcInstTyVars (varSetElems qtvs) `thenM` \ (_, _, tenv) -> + mapM_ (unif_pr tenv) pairs + unif_pr tenv (ty1,ty2) = unifyTauTy (substTy tenv ty1) (substTy tenv ty2) \end{code} The main context-reduction function is @reduce@. Here's its game plan. @@ -1381,7 +1649,8 @@ reduceList (n,stack) try_me wanteds state = #ifdef DEBUG (if n > 8 then - pprTrace "Jeepers! ReduceContext:" (reduceDepthMsg n stack) + pprTrace "Interesting! Context reduction stack deeper than 8:" + (nest 2 (pprStack stack)) else (\x->x)) #endif go wanteds state @@ -1391,19 +1660,19 @@ reduceList (n,stack) try_me wanteds state go ws state' -- Base case: we're done! -reduce stack try_me wanted state +reduce stack try_me wanted avails -- It's the same as an existing inst, or a superclass thereof - | Just avail <- isAvailable state wanted + | Just avail <- isAvailable avails wanted = if isLinearInst wanted then - addLinearAvailable state avail wanted `thenM` \ (state', wanteds') -> - reduceList stack try_me wanteds' state' + addLinearAvailable avails avail wanted `thenM` \ (avails', wanteds') -> + reduceList stack try_me wanteds' avails' else - returnM state -- No op for non-linear things + returnM avails -- No op for non-linear things | otherwise = case try_me wanted of { - DontReduce want_scs -> addIrred want_scs state wanted + KeepDictWithoutSCs -> addIrred NoSCs avails wanted ; DontReduceUnlessConstant -> -- It's irreducible (or at least should not be reduced) -- First, see if the inst can be reduced to a constant in one step @@ -1416,21 +1685,30 @@ reduce stack try_me wanted state ; ReduceMe -> -- It should be reduced lookupInst wanted `thenM` \ lookup_result -> case lookup_result of - GenInst wanteds' rhs -> reduceList stack try_me wanteds' state `thenM` \ state' -> - addWanted state' wanted rhs wanteds' - SimpleInst rhs -> addWanted state wanted rhs [] + GenInst wanteds' rhs -> addIrred NoSCs avails wanted `thenM` \ avails1 -> + reduceList stack try_me wanteds' avails1 `thenM` \ avails2 -> + addWanted avails2 wanted rhs wanteds' + -- Experiment with temporarily doing addIrred *before* the reduceList, + -- which has the effect of adding the thing we are trying + -- to prove to the database before trying to prove the things it + -- needs. See note [RECURSIVE DICTIONARIES] + -- NB: we must not do an addWanted before, because that adds the + -- superclasses too, and thaat can lead to a spurious loop; see + -- the examples in [SUPERCLASS-LOOP] + -- So we do an addIrred before, and then overwrite it afterwards with addWanted + + SimpleInst rhs -> addWanted avails wanted rhs [] NoInstance -> -- No such instance! -- Add it and its superclasses - addIrred AddSCs state wanted - + addIrred AddSCs avails wanted } where try_simple do_this_otherwise = lookupInst wanted `thenM` \ lookup_result -> case lookup_result of - SimpleInst rhs -> addWanted state wanted rhs [] - other -> do_this_otherwise state wanted + SimpleInst rhs -> addWanted avails wanted rhs [] + other -> do_this_otherwise avails wanted \end{code} @@ -1484,16 +1762,15 @@ addFree :: Avails -> Inst -> TcM Avails -- addFree avails free = returnM (addToFM avails free IsFree) -addWanted :: Avails -> Inst -> TcExpr -> [Inst] -> TcM Avails +addWanted :: Avails -> Inst -> LHsExpr TcId -> [Inst] -> TcM Avails addWanted avails wanted rhs_expr wanteds - = ASSERT2( not (wanted `elemFM` avails), ppr wanted $$ ppr avails ) - addAvailAndSCs avails wanted avail + = addAvailAndSCs avails wanted avail where avail | instBindingRequired wanted = Rhs rhs_expr wanteds | otherwise = ASSERT( null wanteds ) NoRhs addGiven :: Avails -> Inst -> TcM Avails -addGiven state given = addAvailAndSCs state given (Given (instToId given) False) +addGiven avails given = addAvailAndSCs avails given (Given (instToId given) False) -- No ASSERT( not (given `elemFM` avails) ) because in an instance -- decl for Ord t we can add both Ord t and Eq t as 'givens', -- so the assert isn't true @@ -1506,23 +1783,31 @@ addIrred AddSCs avails irred = ASSERT2( not (irred `elemFM` avails), ppr irred $ addAvailAndSCs :: Avails -> Inst -> Avail -> TcM Avails addAvailAndSCs avails inst avail | not (isClassDict inst) = returnM avails1 - | otherwise = addSCs is_loop avails1 inst + | otherwise = traceTc (text "addAvailAndSCs" <+> vcat [ppr inst, ppr deps]) `thenM_` + addSCs is_loop avails1 inst where - avails1 = addToFM avails inst avail - is_loop inst = inst `elem` deps -- Note: this compares by *type*, not by Unique - deps = findAllDeps avails avail - -findAllDeps :: Avails -> Avail -> [Inst] --- Find all the Insts that this one depends on --- See Note [SUPERCLASS-LOOP] -findAllDeps avails (Rhs _ kids) = kids ++ concat (map (find_all_deps_help avails) kids) -findAllDeps avails other = [] - -find_all_deps_help :: Avails -> Inst -> [Inst] -find_all_deps_help avails inst - = case lookupFM avails inst of - Just avail -> findAllDeps avails avail - Nothing -> [] + avails1 = addToFM avails inst avail + is_loop inst = any (`tcEqType` idType (instToId inst)) dep_tys + -- Note: this compares by *type*, not by Unique + deps = findAllDeps (unitVarSet (instToId inst)) avail + dep_tys = map idType (varSetElems deps) + + findAllDeps :: IdSet -> Avail -> IdSet + -- Find all the Insts that this one depends on + -- See Note [SUPERCLASS-LOOP] + -- Watch out, though. Since the avails may contain loops + -- (see Note [RECURSIVE DICTIONARIES]), so we need to track the ones we've seen so far + findAllDeps so_far (Rhs _ kids) = foldl find_all so_far kids + findAllDeps so_far other = so_far + + find_all :: IdSet -> Inst -> IdSet + find_all so_far kid + | kid_id `elemVarSet` so_far = so_far + | Just avail <- lookupFM avails kid = findAllDeps so_far' avail + | otherwise = so_far' + where + so_far' = extendVarSet so_far kid_id -- Add the new kid to so_far + kid_id = instToId kid addSCs :: (Inst -> Bool) -> Avails -> Inst -> TcM Avails -- Add all the superclasses of the Inst to Avails @@ -1536,20 +1821,21 @@ addSCs is_loop avails dict where (clas, tys) = getDictClassTys dict (tyvars, sc_theta, sc_sels, _) = classBigSig clas - sc_theta' = substTheta (mkTopTyVarSubst tyvars tys) sc_theta + sc_theta' = substTheta (zipTopTvSubst tyvars tys) sc_theta add_sc avails (sc_dict, sc_sel) -- Add it, and its superclasses - = case lookupFM avails sc_dict of - Just (Given _ _) -> returnM avails -- Given is cheaper than - -- a superclass selection - Just other | is_loop sc_dict -> returnM avails -- See Note [SUPERCLASS-LOOP] - | otherwise -> returnM avails' -- SCs already added - - Nothing -> addSCs is_loop avails' sc_dict + | add_me sc_dict = addSCs is_loop avails' sc_dict + | otherwise = returnM avails where - sc_sel_rhs = DictApp (TyApp (HsVar sc_sel) tys) [instToId dict] - avail = Rhs sc_sel_rhs [dict] - avails' = addToFM avails sc_dict avail + sc_sel_rhs = mkHsDictApp (mkHsTyApp (L (instSpan dict) (HsVar sc_sel)) tys) [instToId dict] + avails' = addToFM avails sc_dict (Rhs sc_sel_rhs [dict]) + + add_me :: Inst -> Bool + add_me sc_dict + | is_loop sc_dict = False -- See Note [SUPERCLASS-LOOP] + | otherwise = case lookupFM avails sc_dict of + Just (Given _ _) -> False -- Given is cheaper than superclass selection + other -> True \end{code} Note [SUPERCLASS-LOOP]: Checking for loops @@ -1558,13 +1844,21 @@ We have to be careful here. If we are *given* d1:Ord a, and want to deduce (d2:C [a]) where class Ord a => C a where - instance Ord a => C [a] where ... + instance Ord [a] => C [a] where ... -Then we'll use the instance decl to deduce C [a] and then add the +Then we'll use the instance decl to deduce C [a] from Ord [a], and then add the superclasses of C [a] to avails. But we must not overwrite the binding -for d1:Ord a (which is given) with a superclass selection or we'll just +for Ord [a] (which is obtained from Ord a) with a superclass selection or we'll just build a loop! +Here's another variant, immortalised in tcrun020 + class Monad m => C1 m + class C1 m => C2 m x + instance C2 Maybe Bool +For the instance decl we need to build (C1 Maybe), and it's no good if +we run around and add (C2 Maybe Bool) and its superclasses to the avails +before we search for C1 Maybe. + Here's another example class Eq b => Foo a b instance Eq a => Foo [a] a @@ -1585,6 +1879,42 @@ Now we implement the Right Solution, which is to check for loops directly when adding superclasses. It's a bit like the occurs check in unification. +Note [RECURSIVE DICTIONARIES] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Consider + data D r = ZeroD | SuccD (r (D r)); + + instance (Eq (r (D r))) => Eq (D r) where + ZeroD == ZeroD = True + (SuccD a) == (SuccD b) = a == b + _ == _ = False; + + equalDC :: D [] -> D [] -> Bool; + equalDC = (==); + +We need to prove (Eq (D [])). Here's how we go: + + d1 : Eq (D []) + +by instance decl, holds if + d2 : Eq [D []] + where d1 = dfEqD d2 + +by instance decl of Eq, holds if + d3 : D [] + where d2 = dfEqList d3 + d1 = dfEqD d2 + +But now we can "tie the knot" to give + + d3 = d1 + d2 = dfEqList d3 + d1 = dfEqD d2 + +and it'll even run! The trick is to put the thing we are trying to prove +(in this case Eq (D []) into the database before trying to prove its +contributing clauses. + %************************************************************************ %* * @@ -1607,8 +1937,14 @@ It's OK: the final zonking stage should zap y to (), which is fine. \begin{code} -tcSimplifyTop :: [Inst] -> TcM TcDictBinds -tcSimplifyTop wanteds +tcSimplifyTop, tcSimplifyInteractive :: [Inst] -> TcM TcDictBinds +tcSimplifyTop wanteds = tc_simplify_top False {- Not interactive loop -} wanteds +tcSimplifyInteractive wanteds = tc_simplify_top True {- Interactive loop -} wanteds + + +-- The TcLclEnv should be valid here, solely to improve +-- error message generation for the monomorphism restriction +tc_simplify_top is_interactive wanteds = getLclEnv `thenM` \ lcl_env -> traceTc (text "tcSimplifyTop" <+> ppr (lclEnvElts lcl_env)) `thenM_` simpleReduceLoop (text "tcSimplTop") reduceMe wanteds `thenM` \ (frees, binds, irreds) -> @@ -1629,21 +1965,36 @@ tcSimplifyTop wanteds non_std_tyvars = unionVarSets (map tyVarsOfInst non_stds) -- Collect together all the bad guys - bad_guys = non_stds ++ concat std_bads - (tidy_env, tidy_dicts) = tidyInsts bad_guys - (bad_ips, non_ips) = partition isIPDict tidy_dicts - (no_insts, ambigs) = partition no_inst non_ips - no_inst d = not (isTyVarDict d) || tyVarsOfInst d `subVarSet` fixed_tvs - fixed_tvs = oclose (fdPredsOfInsts tidy_dicts) emptyVarSet + bad_guys = non_stds ++ concat std_bads + (non_ips, bad_ips) = partition isClassDict bad_guys + (ambigs, no_insts) = partition is_ambig non_ips + is_ambig d = not (tyVarsOfInst d `subVarSet` fixed_tvs) + fixed_tvs = oclose (fdPredsOfInsts irreds) emptyVarSet + -- If the dict has free type variables, it's almost certainly ambiguous, + -- and that's the first thing to fix. + -- Otherwise, addNoInstanceErrs does the right thing + -- I say "almost certain" because we might have + -- class C a b | a -> B where ... + -- plus an Inst (C Int x). Then the 'x' isn't ambiguous; it's just that + -- there's no instance decl for (C Int ...). Hence the oclose. in -- Report definite errors - addTopInstanceErrs tidy_env no_insts `thenM_` - addTopIPErrs tidy_env bad_ips `thenM_` + groupErrs (addNoInstanceErrs Nothing []) no_insts `thenM_` + strangeTopIPErrs bad_ips `thenM_` -- Deal with ambiguity errors, but only if - -- if there has not been an error so far; errors often - -- give rise to spurious ambiguous Insts + -- if there has not been an error so far: + -- errors often give rise to spurious ambiguous Insts. + -- For example: + -- f = (*) -- Monomorphic + -- g :: Num a => a -> a + -- g x = f x x + -- Here, we get a complaint when checking the type signature for g, + -- that g isn't polymorphic enough; but then we get another one when + -- dealing with the (Num a) context arising from f's definition; + -- we try to unify a with Int (to default it), but find that it's + -- already been unified with the rigid variable from g's type sig ifErrsM (returnM []) ( -- Complain about the ones that don't fall under @@ -1652,13 +2003,13 @@ tcSimplifyTop wanteds -- e.g. Num (IO a) and Eq (Int -> Int) -- and ambiguous dictionaries -- e.g. Num a - addTopAmbigErrs (tidy_env, ambigs) `thenM_` + addTopAmbigErrs ambigs `thenM_` -- Disambiguate the ones that look feasible - mappM disambigGroup std_oks + mappM (disambigGroup is_interactive) std_oks ) `thenM` \ binds_ambig -> - returnM (binds `andMonoBinds` andMonoBindList binds_ambig) + returnM (binds `unionBags` unionManyBags binds_ambig) ---------------------------------- d1 `cmp_by_tyvar` d2 = get_tv d1 `compare` get_tv d2 @@ -1702,15 +2053,12 @@ Since we're not using the result of @foo@, the result if (presumably) @void@. \begin{code} -disambigGroup :: [Inst] -- All standard classes of form (C a) +disambigGroup :: Bool -- True <=> simplifying at top-level interactive loop + -> [Inst] -- All standard classes of form (C a) -> TcM TcDictBinds -disambigGroup dicts - | any isNumericClass classes -- Guaranteed all standard classes - -- see comment at the end of function for reasons as to - -- why the defaulting mechanism doesn't apply to groups that - -- include CCallable or CReturnable dicts. - && not (any isCcallishClass classes) +disambigGroup is_interactive dicts + | any std_default_class classes -- Guaranteed all standard classes = -- THE DICTS OBEY THE DEFAULTABLE CONSTRAINT -- SO, TRY DEFAULT TYPES IN ORDER @@ -1718,7 +2066,7 @@ disambigGroup dicts -- default list which can satisfy all the ambiguous classes. -- For example, if Real a is reqd, but the only type in the -- default list is Int. - getDefaultTys `thenM` \ default_tys -> + get_default_tys `thenM` \ default_tys -> let try_default [] -- No defaults work, so fail = failM @@ -1733,35 +2081,45 @@ disambigGroup dicts in -- See if any default works tryM (try_default default_tys) `thenM` \ mb_ty -> - case mb_ty of { - Left _ -> -- If not, add an AmbigErr - addTopAmbigErrs (tidyInsts dicts) `thenM_` - returnM EmptyMonoBinds ; + case mb_ty of + Left _ -> bomb_out + Right chosen_default_ty -> choose_default chosen_default_ty - Right chosen_default_ty -> + | otherwise -- No defaults + = bomb_out - -- If so, bind the type variable + where + tyvar = get_tv (head dicts) -- Should be non-empty + classes = map get_clas dicts + + std_default_class cls + = isNumericClass cls + || (is_interactive && + classKey cls `elem` [showClassKey, eqClassKey, ordClassKey]) + -- In interactive mode, we default Show a to Show () + -- to avoid graututious errors on "show []" + + choose_default default_ty -- Commit to tyvar = default_ty + = -- Bind the type variable + unifyTauTy default_ty (mkTyVarTy tyvar) `thenM_` -- and reduce the context, for real this time - unifyTauTy chosen_default_ty (mkTyVarTy tyvar) `thenM_` - simpleReduceLoop (text "disambig" <+> ppr dicts) + simpleReduceLoop (text "disambig" <+> ppr dicts) reduceMe dicts `thenM` \ (frees, binds, ambigs) -> - WARN( not (null frees && null ambigs), ppr frees $$ ppr ambigs ) - warnDefault dicts chosen_default_ty `thenM_` - returnM binds } - - | all isCreturnableClass classes - = -- Default CCall stuff to (); we don't even both to check that () is an - -- instance of CReturnable, because we know it is. - unifyTauTy (mkTyVarTy tyvar) unitTy `thenM_` - returnM EmptyMonoBinds - - | otherwise -- No defaults - = addTopAmbigErrs (tidyInsts dicts) `thenM_` - returnM EmptyMonoBinds - - where - tyvar = get_tv (head dicts) -- Should be non-empty - classes = map get_clas dicts + WARN( not (null frees && null ambigs), ppr frees $$ ppr ambigs ) + warnDefault dicts default_ty `thenM_` + returnM binds + + bomb_out = addTopAmbigErrs dicts `thenM_` + returnM emptyBag + +get_default_tys + = do { mb_defaults <- getDefaultTys + ; case mb_defaults of + Just tys -> return tys + Nothing -> -- No use-supplied default; + -- use [Integer, Double] + do { integer_ty <- tcMetaTy integerTyConName + ; return [integer_ty, doubleTy] } } \end{code} [Aside - why the defaulting mechanism is turned off when @@ -1819,54 +2177,50 @@ tcSimplifyDeriv :: [TyVar] -> TcM ThetaType -- Needed tcSimplifyDeriv tyvars theta - = tcInstTyVars VanillaTv tyvars `thenM` \ (tvs, _, tenv) -> + = tcInstTyVars tyvars `thenM` \ (tvs, _, tenv) -> -- The main loop may do unification, and that may crash if -- it doesn't see a TcTyVar, so we have to instantiate. Sigh -- ToDo: what if two of them do get unified? - newDicts DataDeclOrigin (substTheta tenv theta) `thenM` \ wanteds -> + newDicts DerivOrigin (substTheta tenv theta) `thenM` \ wanteds -> simpleReduceLoop doc reduceMe wanteds `thenM` \ (frees, _, irreds) -> ASSERT( null frees ) -- reduceMe never returns Free doptM Opt_AllowUndecidableInstances `thenM` \ undecidable_ok -> let tv_set = mkVarSet tvs - simpl_theta = map dictPred irreds -- reduceMe squashes all non-dicts - - check_pred pred - | isEmptyVarSet pred_tyvars -- Things like (Eq T) should be rejected - = addErrTc (noInstErr pred) - - | not undecidable_ok && not (isTyVarClassPred pred) - -- Check that the returned dictionaries are all of form (C a b) - -- (where a, b are type variables). - -- We allow this if we had -fallow-undecidable-instances, - -- but note that risks non-termination in the 'deriving' context-inference - -- fixpoint loop. It is useful for situations like - -- data Min h a = E | M a (h a) - -- which gives the instance decl - -- instance (Eq a, Eq (h a)) => Eq (Min h a) - = addErrTc (noInstErr pred) + + (bad_insts, ok_insts) = partition is_bad_inst irreds + is_bad_inst dict + = let pred = dictPred dict -- reduceMe squashes all non-dicts + in isEmptyVarSet (tyVarsOfPred pred) + -- Things like (Eq T) are bad + || (not undecidable_ok && not (isTyVarClassPred pred)) + -- The returned dictionaries should be of form (C a b) + -- (where a, b are type variables). + -- We allow non-tyvar dicts if we had -fallow-undecidable-instances, + -- but note that risks non-termination in the 'deriving' context-inference + -- fixpoint loop. It is useful for situations like + -- data Min h a = E | M a (h a) + -- which gives the instance decl + -- instance (Eq a, Eq (h a)) => Eq (Min h a) - | not (pred_tyvars `subVarSet` tv_set) + simpl_theta = map dictPred ok_insts + weird_preds = [pred | pred <- simpl_theta + , not (tyVarsOfPred pred `subVarSet` tv_set)] -- Check for a bizarre corner case, when the derived instance decl should -- have form instance C a b => D (T a) where ... -- Note that 'b' isn't a parameter of T. This gives rise to all sorts -- of problems; in particular, it's hard to compare solutions for -- equality when finding the fixpoint. So I just rule it out for now. - = addErrTc (badDerivedPred pred) - | otherwise - = returnM () - where - pred_tyvars = tyVarsOfPred pred - - rev_env = mkTopTyVarSubst tvs (mkTyVarTys tyvars) + rev_env = zipTopTvSubst tvs (mkTyVarTys tyvars) -- This reverse-mapping is a Royal Pain, -- but the result should mention TyVars not TcTyVars in - mappM check_pred simpl_theta `thenM_` - checkAmbiguity tvs simpl_theta tv_set `thenM_` + addNoInstanceErrs Nothing [] bad_insts `thenM_` + mapM_ (addErrTc . badDerivedPred) weird_preds `thenM_` + checkAmbiguity tvs simpl_theta tv_set `thenM_` returnM (substTheta rev_env simpl_theta) where doc = ptext SLIT("deriving classes for a data type") @@ -1881,10 +2235,10 @@ tcSimplifyDefault :: ThetaType -- Wanted; has no type variables in it -> TcM () tcSimplifyDefault theta - = newDicts DataDeclOrigin theta `thenM` \ wanteds -> + = newDicts DefaultOrigin theta `thenM` \ wanteds -> simpleReduceLoop doc reduceMe wanteds `thenM` \ (frees, _, irreds) -> ASSERT( null frees ) -- try_me never returns Free - mappM (addErrTc . noInstErr) irreds `thenM_` + addNoInstanceErrs Nothing [] irreds `thenM_` if null irreds then returnM () else @@ -1934,64 +2288,160 @@ addInstLoc insts msg = msg $$ nest 2 (pprInstLoc (instLoc (head insts))) plural [x] = empty plural xs = char 's' - -addTopIPErrs tidy_env tidy_dicts +addTopIPErrs :: [Name] -> [Inst] -> TcM () +addTopIPErrs bndrs [] + = return () +addTopIPErrs bndrs ips + = addErrTcM (tidy_env, mk_msg tidy_ips) + where + (tidy_env, tidy_ips) = tidyInsts ips + mk_msg ips = vcat [sep [ptext SLIT("Implicit parameters escape from the monomorphic top-level binding(s) of"), + pprBinders bndrs <> colon], + nest 2 (vcat (map ppr_ip ips)), + monomorphism_fix] + ppr_ip ip = pprPred (dictPred ip) <+> pprInstLoc (instLoc ip) + +strangeTopIPErrs :: [Inst] -> TcM () +strangeTopIPErrs dicts -- Strange, becuase addTopIPErrs should have caught them all = groupErrs report tidy_dicts where + (tidy_env, tidy_dicts) = tidyInsts dicts report dicts = addErrTcM (tidy_env, mk_msg dicts) mk_msg dicts = addInstLoc dicts (ptext SLIT("Unbound implicit parameter") <> - plural tidy_dicts <+> pprInsts tidy_dicts) + plural tidy_dicts <+> pprDictsTheta tidy_dicts) + +addNoInstanceErrs :: Maybe SDoc -- Nothing => top level + -- Just d => d describes the construct + -> [Inst] -- What is given by the context or type sig + -> [Inst] -- What is wanted + -> TcM () +addNoInstanceErrs mb_what givens [] + = returnM () +addNoInstanceErrs mb_what givens dicts + = -- Some of the dicts are here because there is no instances + -- and some because there are too many instances (overlap) + getDOpts `thenM` \ dflags -> + tcGetInstEnvs `thenM` \ inst_envs -> + let + (tidy_env1, tidy_givens) = tidyInsts givens + (tidy_env2, tidy_dicts) = tidyMoreInsts tidy_env1 dicts --- Used for top-level irreducibles -addTopInstanceErrs tidy_env tidy_dicts - = groupErrs report tidy_dicts + -- Run through the dicts, generating a message for each + -- overlapping one, but simply accumulating all the + -- no-instance ones so they can be reported as a group + (overlap_doc, no_inst_dicts) = foldl check_overlap (empty, []) tidy_dicts + check_overlap (overlap_doc, no_inst_dicts) dict + | not (isClassDict dict) = (overlap_doc, dict : no_inst_dicts) + | otherwise + = case lookupInstEnv dflags inst_envs clas tys of + -- The case of exactly one match and no unifiers means + -- a successful lookup. That can't happen here, becuase + -- dicts only end up here if they didn't match in Inst.lookupInst +#ifdef DEBUG + ([m],[]) -> pprPanic "addNoInstanceErrs" (ppr dict) +#endif + ([], _) -> (overlap_doc, dict : no_inst_dicts) -- No match + res -> (mk_overlap_msg dict res $$ overlap_doc, no_inst_dicts) + where + (clas,tys) = getDictClassTys dict + in + + -- Now generate a good message for the no-instance bunch + mk_probable_fix tidy_env2 no_inst_dicts `thenM` \ (tidy_env3, probable_fix) -> + let + no_inst_doc | null no_inst_dicts = empty + | otherwise = vcat [addInstLoc no_inst_dicts heading, probable_fix] + heading | null givens = ptext SLIT("No instance") <> plural no_inst_dicts <+> + ptext SLIT("for") <+> pprDictsTheta no_inst_dicts + | otherwise = sep [ptext SLIT("Could not deduce") <+> pprDictsTheta no_inst_dicts, + nest 2 $ ptext SLIT("from the context") <+> pprDictsTheta tidy_givens] + in + -- And emit both the non-instance and overlap messages + addErrTcM (tidy_env3, no_inst_doc $$ overlap_doc) where - report dicts = mkMonomorphismMsg tidy_env dicts `thenM` \ (tidy_env, mono_msg) -> - addErrTcM (tidy_env, mk_msg dicts $$ mono_msg) - mk_msg dicts = addInstLoc dicts (ptext SLIT("No instance") <> plural tidy_dicts <+> - ptext SLIT("for") <+> pprInsts tidy_dicts) - + mk_overlap_msg dict (matches, unifiers) + = vcat [ addInstLoc [dict] ((ptext SLIT("Overlapping instances for") + <+> pprPred (dictPred dict))), + sep [ptext SLIT("Matching instances") <> colon, + nest 2 (vcat [pprDFuns dfuns, pprDFuns unifiers])], + ASSERT( not (null matches) ) + if not (isSingleton matches) + then -- Two or more matches + empty + else -- One match, plus some unifiers + ASSERT( not (null unifiers) ) + parens (vcat [ptext SLIT("The choice depends on the instantiation of") <+> + quotes (pprWithCommas ppr (varSetElems (tyVarsOfInst dict))), + ptext SLIT("Use -fallow-incoherent-instances to use the first choice above")])] + where + dfuns = [df | (_, (_,_,df)) <- matches] -addTopAmbigErrs (tidy_env, tidy_dicts) + mk_probable_fix tidy_env dicts + = returnM (tidy_env, sep [ptext SLIT("Probable fix:"), nest 2 (vcat fixes)]) + where + fixes = add_ors (fix1 ++ fix2) + + fix1 = case mb_what of + Nothing -> [] -- Top level + Just what -> -- Nested (type signatures, instance decls) + [ sep [ ptext SLIT("add") <+> pprDictsTheta dicts, + ptext SLIT("to the") <+> what] ] + + fix2 | null instance_dicts = [] + | otherwise = [ ptext SLIT("add an instance declaration for") + <+> pprDictsTheta instance_dicts ] + instance_dicts = [d | d <- dicts, isClassDict d, not (isTyVarDict d)] + -- Insts for which it is worth suggesting an adding an instance declaration + -- Exclude implicit parameters, and tyvar dicts + + add_ors :: [SDoc] -> [SDoc] + add_ors (f1:fs) = f1 : map (ptext SLIT("or") <+>) fs + +addTopAmbigErrs dicts -- Divide into groups that share a common set of ambiguous tyvars = mapM report (equivClasses cmp [(d, tvs_of d) | d <- tidy_dicts]) where + (tidy_env, tidy_dicts) = tidyInsts dicts + tvs_of :: Inst -> [TcTyVar] tvs_of d = varSetElems (tyVarsOfInst d) cmp (_,tvs1) (_,tvs2) = tvs1 `compare` tvs2 report :: [(Inst,[TcTyVar])] -> TcM () - report pairs@((_,tvs) : _) -- The pairs share a common set of ambiguous tyvars - = mkMonomorphismMsg tidy_env dicts `thenM` \ (tidy_env, mono_msg) -> + report pairs@((inst,tvs) : _) -- The pairs share a common set of ambiguous tyvars + = mkMonomorphismMsg tidy_env tvs `thenM` \ (tidy_env, mono_msg) -> + setSrcSpan (instLocSrcSpan (instLoc inst)) $ + -- the location of the first one will do for the err message addErrTcM (tidy_env, msg $$ mono_msg) where dicts = map fst pairs msg = sep [text "Ambiguous type variable" <> plural tvs <+> - pprQuotedList tvs <+> text "in these top-level constraint" <> plural dicts, - nest 2 (pprInstsInFull dicts)] + pprQuotedList tvs <+> in_msg, + nest 2 (pprDictsInFull dicts)] + in_msg = text "in the constraint" <> plural dicts <> colon -mkMonomorphismMsg :: TidyEnv -> [Inst] -> TcM (TidyEnv, Message) +mkMonomorphismMsg :: TidyEnv -> [TcTyVar] -> TcM (TidyEnv, Message) -- There's an error with these Insts; if they have free type variables -- it's probably caused by the monomorphism restriction. -- Try to identify the offending variable -- ASSUMPTION: the Insts are fully zonked -mkMonomorphismMsg tidy_env insts - | isEmptyVarSet inst_tvs - = returnM (tidy_env, empty) - | otherwise - = findGlobals inst_tvs tidy_env `thenM` \ (tidy_env, docs) -> +mkMonomorphismMsg tidy_env inst_tvs + = findGlobals (mkVarSet inst_tvs) tidy_env `thenM` \ (tidy_env, docs) -> returnM (tidy_env, mk_msg docs) - where - inst_tvs = tyVarsOfInsts insts - - mk_msg [] = empty -- This happens in things like - -- f x = show (read "foo") - -- whre monomorphism doesn't play any role + mk_msg [] = ptext SLIT("Probable fix: add a type signature that fixes these type variable(s)") + -- This happens in things like + -- f x = show (read "foo") + -- whre monomorphism doesn't play any role mk_msg docs = vcat [ptext SLIT("Possible cause: the monomorphism restriction applied to the following:"), nest 2 (vcat docs), - ptext SLIT("Probable fix: give these definition(s) an explicit type signature")] + monomorphism_fix + ] +monomorphism_fix :: SDoc +monomorphism_fix = ptext SLIT("Probable fix:") <+> + (ptext SLIT("give these definition(s) an explicit type signature") + $$ ptext SLIT("or use -fno-monomorphism-restriction")) warnDefault dicts default_ty = doptM Opt_WarnTypeDefaults `thenM` \ warn_flag -> @@ -2001,77 +2451,9 @@ warnDefault dicts default_ty (_, tidy_dicts) = tidyInsts dicts warn_msg = vcat [ptext SLIT("Defaulting the following constraint(s) to type") <+> quotes (ppr default_ty), - pprInstsInFull tidy_dicts] - -complainCheck doc givens irreds - = mappM zonkInst given_dicts_and_ips `thenM` \ givens' -> - groupErrs (addNoInstanceErrs doc givens') irreds `thenM_` - returnM () - where - given_dicts_and_ips = filter (not . isMethod) givens - -- Filter out methods, which are only added to - -- the given set as an optimisation - -addNoInstanceErrs what_doc givens dicts - = getDOpts `thenM` \ dflags -> - tcGetInstEnv `thenM` \ inst_env -> - let - (tidy_env1, tidy_givens) = tidyInsts givens - (tidy_env2, tidy_dicts) = tidyMoreInsts tidy_env1 dicts - - doc = vcat [addInstLoc dicts $ - sep [herald <+> pprInsts tidy_dicts, - nest 4 $ ptext SLIT("from the context") <+> pprInsts tidy_givens], - ambig_doc, - ptext SLIT("Probable fix:"), - nest 4 fix1, - nest 4 fix2] - - herald = ptext SLIT("Could not") <+> unambig_doc <+> ptext SLIT("deduce") - unambig_doc | ambig_overlap = ptext SLIT("unambiguously") - | otherwise = empty - - -- The error message when we don't find a suitable instance - -- is complicated by the fact that sometimes this is because - -- there is no instance, and sometimes it's because there are - -- too many instances (overlap). See the comments in TcEnv.lhs - -- with the InstEnv stuff. - - ambig_doc - | not ambig_overlap = empty - | otherwise - = vcat [ptext SLIT("The choice of (overlapping) instance declaration"), - nest 4 (ptext SLIT("depends on the instantiation of") <+> - quotes (pprWithCommas ppr (varSetElems (tyVarsOfInsts tidy_dicts))))] - - fix1 = sep [ptext SLIT("Add") <+> pprInsts tidy_dicts, - ptext SLIT("to the") <+> what_doc] - - fix2 | null instance_dicts - = empty - | otherwise - = ptext SLIT("Or add an instance declaration for") <+> pprInsts instance_dicts - - instance_dicts = [d | d <- tidy_dicts, isClassDict d, not (isTyVarDict d)] - -- Insts for which it is worth suggesting an adding an instance declaration - -- Exclude implicit parameters, and tyvar dicts - - -- Checks for the ambiguous case when we have overlapping instances - ambig_overlap = any ambig_overlap1 dicts - ambig_overlap1 dict - | isClassDict dict - = case lookupInstEnv dflags inst_env clas tys of - NoMatch ambig -> ambig - other -> False - | otherwise = False - where - (clas,tys) = getDictClassTys dict - in - addErrTcM (tidy_env2, doc) + pprDictsInFull tidy_dicts] -- Used for the ...Thetas variants; all top level -noInstErr pred = ptext SLIT("No instance for") <+> quotes (ppr pred) - badDerivedPred pred = vcat [ptext SLIT("Can't derive instances where the instance context mentions"), ptext SLIT("type variables that are not data type parameters"), @@ -2080,12 +2462,7 @@ badDerivedPred pred reduceDepthErr n stack = vcat [ptext SLIT("Context reduction stack overflow; size =") <+> int n, ptext SLIT("Use -fcontext-stack20 to increase stack size to (e.g.) 20"), - nest 4 (pprInstsInFull stack)] - -reduceDepthMsg n stack = nest 4 (pprInstsInFull stack) + nest 4 (pprStack stack)] ------------------------------------------------ -addCantGenErr inst - = addErrTc (sep [ptext SLIT("Cannot generalise these overloadings (in a _ccall_):"), - nest 4 (ppr inst <+> pprInstLoc (instLoc inst))]) +pprStack stack = vcat (map pprInstInFull stack) \end{code}