Reduce non-determinism in ABI hashes with RULES and instance decls
[ghc.git] / compiler / types / InstEnv.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4
5 \section[InstEnv]{Utilities for typechecking instance declarations}
6
7 The bits common to TcInstDcls and TcDeriv.
8 -}
9
10 {-# LANGUAGE CPP, DeriveDataTypeable #-}
11
12 module InstEnv (
13 DFunId, InstMatch, ClsInstLookupResult,
14 OverlapFlag(..), OverlapMode(..), setOverlapModeMaybe,
15 ClsInst(..), DFunInstType, pprInstance, pprInstanceHdr, pprInstances,
16 instanceHead, instanceSig, mkLocalInstance, mkImportedInstance,
17 instanceDFunId, tidyClsInstDFun, instanceRoughTcs,
18 fuzzyClsInstCmp,
19
20 IsOrphan(..), isOrphan, notOrphan,
21
22 InstEnvs(..), VisibleOrphanModules, InstEnv,
23 emptyInstEnv, extendInstEnv, deleteFromInstEnv, identicalClsInstHead,
24 extendInstEnvList, lookupUniqueInstEnv, lookupInstEnv', lookupInstEnv, instEnvElts,
25 memberInstEnv, instIsVisible,
26 classInstances, orphNamesOfClsInst, instanceBindFun,
27 instanceCantMatch, roughMatchTcs
28 ) where
29
30 #include "HsVersions.h"
31
32 import CoreSyn (IsOrphan(..), isOrphan, notOrphan)
33 import Module
34 import Class
35 import Var
36 import VarSet
37 import Name
38 import NameSet
39 import TcType
40 import TyCon
41 import Unify
42 import Outputable
43 import ErrUtils
44 import BasicTypes
45 import UniqFM
46 import Util
47 import Id
48 import FastString
49 import Data.Data ( Data, Typeable )
50 import Data.Maybe ( isJust, isNothing )
51 #if __GLASGOW_HASKELL__ < 709
52 import Data.Monoid
53 #endif
54
55 {-
56 ************************************************************************
57 * *
58 ClsInst: the data type for type-class instances
59 * *
60 ************************************************************************
61 -}
62
63 data ClsInst
64 = ClsInst { -- Used for "rough matching"; see Note [Rough-match field]
65 -- INVARIANT: is_tcs = roughMatchTcs is_tys
66 is_cls_nm :: Name -- Class name
67 , is_tcs :: [Maybe Name] -- Top of type args
68
69 -- Used for "proper matching"; see Note [Proper-match fields]
70 , is_tvs :: [TyVar] -- Fresh template tyvars for full match
71 -- See Note [Template tyvars are fresh]
72 , is_cls :: Class -- The real class
73 , is_tys :: [Type] -- Full arg types (mentioning is_tvs)
74 -- INVARIANT: is_dfun Id has type
75 -- forall is_tvs. (...) => is_cls is_tys
76 -- (modulo alpha conversion)
77
78 , is_dfun :: DFunId -- See Note [Haddock assumptions]
79
80 , is_flag :: OverlapFlag -- See detailed comments with
81 -- the decl of BasicTypes.OverlapFlag
82 , is_orphan :: IsOrphan
83 }
84 deriving (Data, Typeable)
85
86 -- | A fuzzy comparison function for class instances, intended for sorting
87 -- instances before displaying them to the user.
88 fuzzyClsInstCmp :: ClsInst -> ClsInst -> Ordering
89 fuzzyClsInstCmp x y =
90 stableNameCmp (is_cls_nm x) (is_cls_nm y) `mappend`
91 mconcat (map cmp (zip (is_tcs x) (is_tcs y)))
92 where
93 cmp (Nothing, Nothing) = EQ
94 cmp (Nothing, Just _) = LT
95 cmp (Just _, Nothing) = GT
96 cmp (Just x, Just y) = stableNameCmp x y
97
98 {-
99 Note [Template tyvars are fresh]
100 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
101 The is_tvs field of a ClsInst has *completely fresh* tyvars.
102 That is, they are
103 * distinct from any other ClsInst
104 * distinct from any tyvars free in predicates that may
105 be looked up in the class instance environment
106 Reason for freshness: we use unification when checking for overlap
107 etc, and that requires the tyvars to be distinct.
108
109 The invariant is checked by the ASSERT in lookupInstEnv'.
110
111 Note [Rough-match field]
112 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
113 The is_cls_nm, is_tcs fields allow a "rough match" to be done
114 *without* poking inside the DFunId. Poking the DFunId forces
115 us to suck in all the type constructors etc it involves,
116 which is a total waste of time if it has no chance of matching
117 So the Name, [Maybe Name] fields allow us to say "definitely
118 does not match", based only on the Name.
119
120 In is_tcs,
121 Nothing means that this type arg is a type variable
122
123 (Just n) means that this type arg is a
124 TyConApp with a type constructor of n.
125 This is always a real tycon, never a synonym!
126 (Two different synonyms might match, but two
127 different real tycons can't.)
128 NB: newtypes are not transparent, though!
129
130 Note [Proper-match fields]
131 ~~~~~~~~~~~~~~~~~~~~~~~~~
132 The is_tvs, is_cls, is_tys fields are simply cached values, pulled
133 out (lazily) from the dfun id. They are cached here simply so
134 that we don't need to decompose the DFunId each time we want
135 to match it. The hope is that the fast-match fields mean
136 that we often never poke the proper-match fields.
137
138 However, note that:
139 * is_tvs must be a superset of the free vars of is_tys
140
141 * is_tvs, is_tys may be alpha-renamed compared to the ones in
142 the dfun Id
143
144 Note [Haddock assumptions]
145 ~~~~~~~~~~~~~~~~~~~~~~~~~~
146 For normal user-written instances, Haddock relies on
147
148 * the SrcSpan of
149 * the Name of
150 * the is_dfun of
151 * an Instance
152
153 being equal to
154
155 * the SrcSpan of
156 * the instance head type of
157 * the InstDecl used to construct the Instance.
158 -}
159
160 instanceDFunId :: ClsInst -> DFunId
161 instanceDFunId = is_dfun
162
163 tidyClsInstDFun :: (DFunId -> DFunId) -> ClsInst -> ClsInst
164 tidyClsInstDFun tidy_dfun ispec
165 = ispec { is_dfun = tidy_dfun (is_dfun ispec) }
166
167 instanceRoughTcs :: ClsInst -> [Maybe Name]
168 instanceRoughTcs = is_tcs
169
170 instance NamedThing ClsInst where
171 getName ispec = getName (is_dfun ispec)
172
173 instance Outputable ClsInst where
174 ppr = pprInstance
175
176 pprInstance :: ClsInst -> SDoc
177 -- Prints the ClsInst as an instance declaration
178 pprInstance ispec
179 = hang (pprInstanceHdr ispec)
180 2 (vcat [ ptext (sLit "--") <+> pprDefinedAt (getName ispec)
181 , ifPprDebug (ppr (is_dfun ispec)) ])
182
183 -- * pprInstanceHdr is used in VStudio to populate the ClassView tree
184 pprInstanceHdr :: ClsInst -> SDoc
185 -- Prints the ClsInst as an instance declaration
186 pprInstanceHdr (ClsInst { is_flag = flag, is_dfun = dfun })
187 = ptext (sLit "instance") <+> ppr flag <+> pprSigmaType (idType dfun)
188
189 pprInstances :: [ClsInst] -> SDoc
190 pprInstances ispecs = vcat (map pprInstance ispecs)
191
192 instanceHead :: ClsInst -> ([TyVar], Class, [Type])
193 -- Returns the head, using the fresh tyavs from the ClsInst
194 instanceHead (ClsInst { is_tvs = tvs, is_tys = tys, is_dfun = dfun })
195 = (tvs, cls, tys)
196 where
197 (_, _, cls, _) = tcSplitDFunTy (idType dfun)
198
199 instanceSig :: ClsInst -> ([TyVar], [Type], Class, [Type])
200 -- Decomposes the DFunId
201 instanceSig ispec = tcSplitDFunTy (idType (is_dfun ispec))
202
203 mkLocalInstance :: DFunId -> OverlapFlag
204 -> [TyVar] -> Class -> [Type]
205 -> ClsInst
206 -- Used for local instances, where we can safely pull on the DFunId
207 mkLocalInstance dfun oflag tvs cls tys
208 = ClsInst { is_flag = oflag, is_dfun = dfun
209 , is_tvs = tvs
210 , is_cls = cls, is_cls_nm = cls_name
211 , is_tys = tys, is_tcs = roughMatchTcs tys
212 , is_orphan = orph
213 }
214 where
215 cls_name = className cls
216 dfun_name = idName dfun
217 this_mod = ASSERT( isExternalName dfun_name ) nameModule dfun_name
218 is_local name = nameIsLocalOrFrom this_mod name
219
220 -- Compute orphanhood. See Note [Orphans] in InstEnv
221 (cls_tvs, fds) = classTvsFds cls
222 arg_names = [filterNameSet is_local (orphNamesOfType ty) | ty <- tys]
223
224 -- See Note [When exactly is an instance decl an orphan?]
225 orph | is_local cls_name = NotOrphan (nameOccName cls_name)
226 | all notOrphan mb_ns = ASSERT( not (null mb_ns) ) head mb_ns
227 | otherwise = IsOrphan
228
229 notOrphan NotOrphan{} = True
230 notOrphan _ = False
231
232 mb_ns :: [IsOrphan] -- One for each fundep; a locally-defined name
233 -- that is not in the "determined" arguments
234 mb_ns | null fds = [choose_one arg_names]
235 | otherwise = map do_one fds
236 do_one (_ltvs, rtvs) = choose_one [ns | (tv,ns) <- cls_tvs `zip` arg_names
237 , not (tv `elem` rtvs)]
238
239 -- Since instance declarations get eventually attached to one of the types
240 -- from the definition when compiling the ABI hash, we should make
241 -- it deterministic. This chooses the one with minimal OccName
242 -- as opposed to uniq value.
243 choose_one :: [NameSet] -> IsOrphan
244 choose_one nss = case local_names of
245 [] -> IsOrphan
246 (_ : _) -> NotOrphan anchor
247 where
248 local_names = nameSetElems (unionNameSets nss)
249 anchor = minimum $ map nameOccName local_names
250
251 mkImportedInstance :: Name
252 -> [Maybe Name]
253 -> DFunId
254 -> OverlapFlag
255 -> IsOrphan
256 -> ClsInst
257 -- Used for imported instances, where we get the rough-match stuff
258 -- from the interface file
259 -- The bound tyvars of the dfun are guaranteed fresh, because
260 -- the dfun has been typechecked out of the same interface file
261 mkImportedInstance cls_nm mb_tcs dfun oflag orphan
262 = ClsInst { is_flag = oflag, is_dfun = dfun
263 , is_tvs = tvs, is_tys = tys
264 , is_cls_nm = cls_nm, is_cls = cls, is_tcs = mb_tcs
265 , is_orphan = orphan }
266 where
267 (tvs, _, cls, tys) = tcSplitDFunTy (idType dfun)
268
269 roughMatchTcs :: [Type] -> [Maybe Name]
270 roughMatchTcs tys = map rough tys
271 where
272 rough ty = case tcSplitTyConApp_maybe ty of
273 Just (tc,_) -> Just (tyConName tc)
274 Nothing -> Nothing
275
276 instanceCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool
277 -- (instanceCantMatch tcs1 tcs2) returns True if tcs1 cannot
278 -- possibly be instantiated to actual, nor vice versa;
279 -- False is non-committal
280 instanceCantMatch (Just t : ts) (Just a : as) = t/=a || instanceCantMatch ts as
281 instanceCantMatch _ _ = False -- Safe
282
283 {-
284 Note [When exactly is an instance decl an orphan?]
285 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
286 (see MkIface.instanceToIfaceInst, which implements this)
287 Roughly speaking, an instance is an orphan if its head (after the =>)
288 mentions nothing defined in this module.
289
290 Functional dependencies complicate the situation though. Consider
291
292 module M where { class C a b | a -> b }
293
294 and suppose we are compiling module X:
295
296 module X where
297 import M
298 data T = ...
299 instance C Int T where ...
300
301 This instance is an orphan, because when compiling a third module Y we
302 might get a constraint (C Int v), and we'd want to improve v to T. So
303 we must make sure X's instances are loaded, even if we do not directly
304 use anything from X.
305
306 More precisely, an instance is an orphan iff
307
308 If there are no fundeps, then at least of the names in
309 the instance head is locally defined.
310
311 If there are fundeps, then for every fundep, at least one of the
312 names free in a *non-determined* part of the instance head is
313 defined in this module.
314
315 (Note that these conditions hold trivially if the class is locally
316 defined.)
317
318
319 ************************************************************************
320 * *
321 InstEnv, ClsInstEnv
322 * *
323 ************************************************************************
324
325 A @ClsInstEnv@ all the instances of that class. The @Id@ inside a
326 ClsInstEnv mapping is the dfun for that instance.
327
328 If class C maps to a list containing the item ([a,b], [t1,t2,t3], dfun), then
329
330 forall a b, C t1 t2 t3 can be constructed by dfun
331
332 or, to put it another way, we have
333
334 instance (...) => C t1 t2 t3, witnessed by dfun
335 -}
336
337 ---------------------------------------------------
338 type InstEnv = UniqFM ClsInstEnv -- Maps Class to instances for that class
339
340 -- | 'InstEnvs' represents the combination of the global type class instance
341 -- environment, the local type class instance environment, and the set of
342 -- transitively reachable orphan modules (according to what modules have been
343 -- directly imported) used to test orphan instance visibility.
344 data InstEnvs = InstEnvs {
345 ie_global :: InstEnv, -- External-package instances
346 ie_local :: InstEnv, -- Home-package instances
347 ie_visible :: VisibleOrphanModules -- Set of all orphan modules transitively
348 -- reachable from the module being compiled
349 -- See Note [Instance lookup and orphan instances]
350 }
351
352 -- | Set of visible orphan modules, according to what modules have been directly
353 -- imported. This is based off of the dep_orphs field, which records
354 -- transitively reachable orphan modules (modules that define orphan instances).
355 type VisibleOrphanModules = ModuleSet
356
357 newtype ClsInstEnv
358 = ClsIE [ClsInst] -- The instances for a particular class, in any order
359
360 instance Outputable ClsInstEnv where
361 ppr (ClsIE is) = pprInstances is
362
363 -- INVARIANTS:
364 -- * The is_tvs are distinct in each ClsInst
365 -- of a ClsInstEnv (so we can safely unify them)
366
367 -- Thus, the @ClassInstEnv@ for @Eq@ might contain the following entry:
368 -- [a] ===> dfun_Eq_List :: forall a. Eq a => Eq [a]
369 -- The "a" in the pattern must be one of the forall'd variables in
370 -- the dfun type.
371
372 emptyInstEnv :: InstEnv
373 emptyInstEnv = emptyUFM
374
375 instEnvElts :: InstEnv -> [ClsInst]
376 instEnvElts ie = [elt | ClsIE elts <- eltsUFM ie, elt <- elts]
377
378 -- | Test if an instance is visible, by checking that its origin module
379 -- is in 'VisibleOrphanModules'.
380 -- See Note [Instance lookup and orphan instances]
381 instIsVisible :: VisibleOrphanModules -> ClsInst -> Bool
382 instIsVisible vis_mods ispec
383 -- NB: Instances from the interactive package always are visible. We can't
384 -- add interactive modules to the set since we keep creating new ones
385 -- as a GHCi session progresses.
386 | isInteractiveModule mod = True
387 | IsOrphan <- is_orphan ispec = mod `elemModuleSet` vis_mods
388 | otherwise = True
389 where
390 mod = nameModule (idName (is_dfun ispec))
391
392 classInstances :: InstEnvs -> Class -> [ClsInst]
393 classInstances (InstEnvs { ie_global = pkg_ie, ie_local = home_ie, ie_visible = vis_mods }) cls
394 = get home_ie ++ get pkg_ie
395 where
396 get env = case lookupUFM env cls of
397 Just (ClsIE insts) -> filter (instIsVisible vis_mods) insts
398 Nothing -> []
399
400 -- | Collects the names of concrete types and type constructors that make
401 -- up the head of a class instance. For instance, given `class Foo a b`:
402 --
403 -- `instance Foo (Either (Maybe Int) a) Bool` would yield
404 -- [Either, Maybe, Int, Bool]
405 --
406 -- Used in the implementation of ":info" in GHCi.
407 orphNamesOfClsInst :: ClsInst -> NameSet
408 orphNamesOfClsInst = orphNamesOfDFunHead . idType . instanceDFunId
409
410 -- | Checks for an exact match of ClsInst in the instance environment.
411 -- We use this when we do signature checking in TcRnDriver
412 memberInstEnv :: InstEnv -> ClsInst -> Bool
413 memberInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm } ) =
414 maybe False (\(ClsIE items) -> any (identicalClsInstHead ins_item) items)
415 (lookupUFM inst_env cls_nm)
416
417 extendInstEnvList :: InstEnv -> [ClsInst] -> InstEnv
418 extendInstEnvList inst_env ispecs = foldl extendInstEnv inst_env ispecs
419
420 extendInstEnv :: InstEnv -> ClsInst -> InstEnv
421 extendInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
422 = addToUFM_C add inst_env cls_nm (ClsIE [ins_item])
423 where
424 add (ClsIE cur_insts) _ = ClsIE (ins_item : cur_insts)
425
426 deleteFromInstEnv :: InstEnv -> ClsInst -> InstEnv
427 deleteFromInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
428 = adjustUFM adjust inst_env cls_nm
429 where
430 adjust (ClsIE items) = ClsIE (filterOut (identicalClsInstHead ins_item) items)
431
432 identicalClsInstHead :: ClsInst -> ClsInst -> Bool
433 -- ^ True when when the instance heads are the same
434 -- e.g. both are Eq [(a,b)]
435 -- Used for overriding in GHCi
436 -- Obviously should be insenstive to alpha-renaming
437 identicalClsInstHead (ClsInst { is_cls_nm = cls_nm1, is_tcs = rough1, is_tvs = tvs1, is_tys = tys1 })
438 (ClsInst { is_cls_nm = cls_nm2, is_tcs = rough2, is_tvs = tvs2, is_tys = tys2 })
439 = cls_nm1 == cls_nm2
440 && not (instanceCantMatch rough1 rough2) -- Fast check for no match, uses the "rough match" fields
441 && isJust (tcMatchTys (mkVarSet tvs1) tys1 tys2)
442 && isJust (tcMatchTys (mkVarSet tvs2) tys2 tys1)
443
444 {-
445 ************************************************************************
446 * *
447 Looking up an instance
448 * *
449 ************************************************************************
450
451 @lookupInstEnv@ looks up in a @InstEnv@, using a one-way match. Since
452 the env is kept ordered, the first match must be the only one. The
453 thing we are looking up can have an arbitrary "flexi" part.
454
455 Note [Instance lookup and orphan instances]
456 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
457 Suppose we are compiling a module M, and we have a zillion packages
458 loaded, and we are looking up an instance for C (T W). If we find a
459 match in module 'X' from package 'p', should be "in scope"; that is,
460
461 is p:X in the transitive closure of modules imported from M?
462
463 The difficulty is that the "zillion packages" might include ones loaded
464 through earlier invocations of the GHC API, or earlier module loads in GHCi.
465 They might not be in the dependencies of M itself; and if not, the instances
466 in them should not be visible. Trac #2182, #8427.
467
468 There are two cases:
469 * If the instance is *not an orphan*, then module X defines C, T, or W.
470 And in order for those types to be involved in typechecking M, it
471 must be that X is in the transitive closure of M's imports. So we
472 can use the instance.
473
474 * If the instance *is an orphan*, the above reasoning does not apply.
475 So we keep track of the set of orphan modules transitively below M;
476 this is the ie_visible field of InstEnvs, of type VisibleOrphanModules.
477
478 If module p:X is in this set, then we can use the instance, otherwise
479 we can't.
480
481 Note [Rules for instance lookup]
482 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
483 These functions implement the carefully-written rules in the user
484 manual section on "overlapping instances". At risk of duplication,
485 here are the rules. If the rules change, change this text and the
486 user manual simultaneously. The link may be this:
487 http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#instance-overlap
488
489 The willingness to be overlapped or incoherent is a property of the
490 instance declaration itself, controlled as follows:
491
492 * An instance is "incoherent"
493 if it has an INCOHERENT pragma, or
494 if it appears in a module compiled with -XIncoherentInstances.
495
496 * An instance is "overlappable"
497 if it has an OVERLAPPABLE or OVERLAPS pragma, or
498 if it appears in a module compiled with -XOverlappingInstances, or
499 if the instance is incoherent.
500
501 * An instance is "overlapping"
502 if it has an OVERLAPPING or OVERLAPS pragma, or
503 if it appears in a module compiled with -XOverlappingInstances, or
504 if the instance is incoherent.
505 compiled with -XOverlappingInstances.
506
507 Now suppose that, in some client module, we are searching for an instance
508 of the target constraint (C ty1 .. tyn). The search works like this.
509
510 * Find all instances I that match the target constraint; that is, the
511 target constraint is a substitution instance of I. These instance
512 declarations are the candidates.
513
514 * Find all non-candidate instances that unify with the target
515 constraint. Such non-candidates instances might match when the
516 target constraint is further instantiated. If all of them are
517 incoherent, proceed; if not, the search fails.
518
519 * Eliminate any candidate IX for which both of the following hold:
520 * There is another candidate IY that is strictly more specific;
521 that is, IY is a substitution instance of IX but not vice versa.
522
523 * Either IX is overlappable or IY is overlapping.
524
525 * If only one candidate remains, pick it. Otherwise if all remaining
526 candidates are incoherent, pick an arbitrary candidate. Otherwise fail.
527
528 Note [Overlapping instances] (NB: these notes are quite old)
529 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
530 Overlap is permitted, but only in such a way that one can make
531 a unique choice when looking up. That is, overlap is only permitted if
532 one template matches the other, or vice versa. So this is ok:
533
534 [a] [Int]
535
536 but this is not
537
538 (Int,a) (b,Int)
539
540 If overlap is permitted, the list is kept most specific first, so that
541 the first lookup is the right choice.
542
543
544 For now we just use association lists.
545
546 \subsection{Avoiding a problem with overlapping}
547
548 Consider this little program:
549
550 \begin{pseudocode}
551 class C a where c :: a
552 class C a => D a where d :: a
553
554 instance C Int where c = 17
555 instance D Int where d = 13
556
557 instance C a => C [a] where c = [c]
558 instance ({- C [a], -} D a) => D [a] where d = c
559
560 instance C [Int] where c = [37]
561
562 main = print (d :: [Int])
563 \end{pseudocode}
564
565 What do you think `main' prints (assuming we have overlapping instances, and
566 all that turned on)? Well, the instance for `D' at type `[a]' is defined to
567 be `c' at the same type, and we've got an instance of `C' at `[Int]', so the
568 answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because
569 the `C [Int]' instance is more specific).
570
571 Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong. That
572 was easy ;-) Let's just consult hugs for good measure. Wait - if I use old
573 hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it
574 doesn't even compile! What's going on!?
575
576 What hugs complains about is the `D [a]' instance decl.
577
578 \begin{pseudocode}
579 ERROR "mj.hs" (line 10): Cannot build superclass instance
580 *** Instance : D [a]
581 *** Context supplied : D a
582 *** Required superclass : C [a]
583 \end{pseudocode}
584
585 You might wonder what hugs is complaining about. It's saying that you
586 need to add `C [a]' to the context of the `D [a]' instance (as appears
587 in comments). But there's that `C [a]' instance decl one line above
588 that says that I can reduce the need for a `C [a]' instance to the
589 need for a `C a' instance, and in this case, I already have the
590 necessary `C a' instance (since we have `D a' explicitly in the
591 context, and `C' is a superclass of `D').
592
593 Unfortunately, the above reasoning indicates a premature commitment to the
594 generic `C [a]' instance. I.e., it prematurely rules out the more specific
595 instance `C [Int]'. This is the mistake that ghc-4.06 makes. The fix is to
596 add the context that hugs suggests (uncomment the `C [a]'), effectively
597 deferring the decision about which instance to use.
598
599 Now, interestingly enough, 4.04 has this same bug, but it's covered up
600 in this case by a little known `optimization' that was disabled in
601 4.06. Ghc-4.04 silently inserts any missing superclass context into
602 an instance declaration. In this case, it silently inserts the `C
603 [a]', and everything happens to work out.
604
605 (See `basicTypes/MkId:mkDictFunId' for the code in question. Search for
606 `Mark Jones', although Mark claims no credit for the `optimization' in
607 question, and would rather it stopped being called the `Mark Jones
608 optimization' ;-)
609
610 So, what's the fix? I think hugs has it right. Here's why. Let's try
611 something else out with ghc-4.04. Let's add the following line:
612
613 d' :: D a => [a]
614 d' = c
615
616 Everyone raise their hand who thinks that `d :: [Int]' should give a
617 different answer from `d' :: [Int]'. Well, in ghc-4.04, it does. The
618 `optimization' only applies to instance decls, not to regular
619 bindings, giving inconsistent behavior.
620
621 Old hugs had this same bug. Here's how we fixed it: like GHC, the
622 list of instances for a given class is ordered, so that more specific
623 instances come before more generic ones. For example, the instance
624 list for C might contain:
625 ..., C Int, ..., C a, ...
626 When we go to look for a `C Int' instance we'll get that one first.
627 But what if we go looking for a `C b' (`b' is unconstrained)? We'll
628 pass the `C Int' instance, and keep going. But if `b' is
629 unconstrained, then we don't know yet if the more specific instance
630 will eventually apply. GHC keeps going, and matches on the generic `C
631 a'. The fix is to, at each step, check to see if there's a reverse
632 match, and if so, abort the search. This prevents hugs from
633 prematurely chosing a generic instance when a more specific one
634 exists.
635
636 --Jeff
637 v
638 BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in
639 this test. Suppose the instance envt had
640 ..., forall a b. C a a b, ..., forall a b c. C a b c, ...
641 (still most specific first)
642 Now suppose we are looking for (C x y Int), where x and y are unconstrained.
643 C x y Int doesn't match the template {a,b} C a a b
644 but neither does
645 C a a b match the template {x,y} C x y Int
646 But still x and y might subsequently be unified so they *do* match.
647
648 Simple story: unify, don't match.
649 -}
650
651 type DFunInstType = Maybe Type
652 -- Just ty => Instantiate with this type
653 -- Nothing => Instantiate with any type of this tyvar's kind
654 -- See Note [DFunInstType: instantiating types]
655
656 type InstMatch = (ClsInst, [DFunInstType])
657
658 type ClsInstLookupResult
659 = ( [InstMatch] -- Successful matches
660 , [ClsInst] -- These don't match but do unify
661 , [InstMatch] ) -- Unsafe overlapped instances under Safe Haskell
662 -- (see Note [Safe Haskell Overlapping Instances] in
663 -- TcSimplify).
664
665 {-
666 Note [DFunInstType: instantiating types]
667 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
668 A successful match is a ClsInst, together with the types at which
669 the dfun_id in the ClsInst should be instantiated
670 The instantiating types are (Either TyVar Type)s because the dfun
671 might have some tyvars that *only* appear in arguments
672 dfun :: forall a b. C a b, Ord b => D [a]
673 When we match this against D [ty], we return the instantiating types
674 [Just ty, Nothing]
675 where the 'Nothing' indicates that 'b' can be freely instantiated.
676 (The caller instantiates it to a flexi type variable, which will
677 presumably later become fixed via functional dependencies.)
678 -}
679
680 -- |Look up an instance in the given instance environment. The given class application must match exactly
681 -- one instance and the match may not contain any flexi type variables. If the lookup is unsuccessful,
682 -- yield 'Left errorMessage'.
683 --
684 lookupUniqueInstEnv :: InstEnvs
685 -> Class -> [Type]
686 -> Either MsgDoc (ClsInst, [Type])
687 lookupUniqueInstEnv instEnv cls tys
688 = case lookupInstEnv False instEnv cls tys of
689 ([(inst, inst_tys)], _, _)
690 | noFlexiVar -> Right (inst, inst_tys')
691 | otherwise -> Left $ ptext (sLit "flexible type variable:") <+>
692 (ppr $ mkTyConApp (classTyCon cls) tys)
693 where
694 inst_tys' = [ty | Just ty <- inst_tys]
695 noFlexiVar = all isJust inst_tys
696 _other -> Left $ ptext (sLit "instance not found") <+> (ppr $ mkTyConApp (classTyCon cls) tys)
697
698 lookupInstEnv' :: InstEnv -- InstEnv to look in
699 -> VisibleOrphanModules -- But filter against this
700 -> Class -> [Type] -- What we are looking for
701 -> ([InstMatch], -- Successful matches
702 [ClsInst]) -- These don't match but do unify
703 -- The second component of the result pair happens when we look up
704 -- Foo [a]
705 -- in an InstEnv that has entries for
706 -- Foo [Int]
707 -- Foo [b]
708 -- Then which we choose would depend on the way in which 'a'
709 -- is instantiated. So we report that Foo [b] is a match (mapping b->a)
710 -- but Foo [Int] is a unifier. This gives the caller a better chance of
711 -- giving a suitable error message
712
713 lookupInstEnv' ie vis_mods cls tys
714 = lookup ie
715 where
716 rough_tcs = roughMatchTcs tys
717 all_tvs = all isNothing rough_tcs
718 --------------
719 lookup env = case lookupUFM env cls of
720 Nothing -> ([],[]) -- No instances for this class
721 Just (ClsIE insts) -> find [] [] insts
722
723 --------------
724 find ms us [] = (ms, us)
725 find ms us (item@(ClsInst { is_tcs = mb_tcs, is_tvs = tpl_tvs
726 , is_tys = tpl_tys, is_flag = oflag }) : rest)
727 | not (instIsVisible vis_mods item)
728 = find ms us rest -- See Note [Instance lookup and orphan instances]
729
730 -- Fast check for no match, uses the "rough match" fields
731 | instanceCantMatch rough_tcs mb_tcs
732 = find ms us rest
733
734 | Just subst <- tcMatchTys tpl_tv_set tpl_tys tys
735 = find ((item, map (lookup_tv subst) tpl_tvs) : ms) us rest
736
737 -- Does not match, so next check whether the things unify
738 -- See Note [Overlapping instances] and Note [Incoherent instances]
739 | Incoherent _ <- overlapMode oflag
740 = find ms us rest
741
742 | otherwise
743 = ASSERT2( tyVarsOfTypes tys `disjointVarSet` tpl_tv_set,
744 (ppr cls <+> ppr tys <+> ppr all_tvs) $$
745 (ppr tpl_tvs <+> ppr tpl_tys)
746 )
747 -- Unification will break badly if the variables overlap
748 -- They shouldn't because we allocate separate uniques for them
749 -- See Note [Template tyvars are fresh]
750 case tcUnifyTys instanceBindFun tpl_tys tys of
751 Just _ -> find ms (item:us) rest
752 Nothing -> find ms us rest
753 where
754 tpl_tv_set = mkVarSet tpl_tvs
755
756 ----------------
757 lookup_tv :: TvSubst -> TyVar -> DFunInstType
758 -- See Note [DFunInstType: instantiating types]
759 lookup_tv subst tv = case lookupTyVar subst tv of
760 Just ty -> Just ty
761 Nothing -> Nothing
762
763 ---------------
764 -- This is the common way to call this function.
765 lookupInstEnv :: Bool -- Check Safe Haskell overlap restrictions
766 -> InstEnvs -- External and home package inst-env
767 -> Class -> [Type] -- What we are looking for
768 -> ClsInstLookupResult
769 -- ^ See Note [Rules for instance lookup]
770 -- ^ See Note [Safe Haskell Overlapping Instances] in TcSimplify
771 -- ^ See Note [Safe Haskell Overlapping Instances Implementation] in TcSimplify
772 lookupInstEnv check_overlap_safe
773 (InstEnvs { ie_global = pkg_ie
774 , ie_local = home_ie
775 , ie_visible = vis_mods })
776 cls
777 tys
778 = (final_matches, final_unifs, unsafe_overlapped)
779 where
780 (home_matches, home_unifs) = lookupInstEnv' home_ie vis_mods cls tys
781 (pkg_matches, pkg_unifs) = lookupInstEnv' pkg_ie vis_mods cls tys
782 all_matches = home_matches ++ pkg_matches
783 all_unifs = home_unifs ++ pkg_unifs
784 final_matches = foldr insert_overlapping [] all_matches
785 -- Even if the unifs is non-empty (an error situation)
786 -- we still prune the matches, so that the error message isn't
787 -- misleading (complaining of multiple matches when some should be
788 -- overlapped away)
789
790 unsafe_overlapped
791 = case final_matches of
792 [match] -> check_safe match
793 _ -> []
794
795 -- If the selected match is incoherent, discard all unifiers
796 final_unifs = case final_matches of
797 (m:_) | is_incoherent m -> []
798 _ -> all_unifs
799
800 -- NOTE [Safe Haskell isSafeOverlap]
801 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
802 -- We restrict code compiled in 'Safe' mode from overriding code
803 -- compiled in any other mode. The rationale is that code compiled
804 -- in 'Safe' mode is code that is untrusted by the ghc user. So
805 -- we shouldn't let that code change the behaviour of code the
806 -- user didn't compile in 'Safe' mode since that's the code they
807 -- trust. So 'Safe' instances can only overlap instances from the
808 -- same module. A same instance origin policy for safe compiled
809 -- instances.
810 check_safe (inst,_)
811 = case check_overlap_safe && unsafeTopInstance inst of
812 -- make sure it only overlaps instances from the same module
813 True -> go [] all_matches
814 -- most specific is from a trusted location.
815 False -> []
816 where
817 go bad [] = bad
818 go bad (i@(x,_):unchecked) =
819 if inSameMod x || isOverlappable x
820 then go bad unchecked
821 else go (i:bad) unchecked
822
823 inSameMod b =
824 let na = getName $ getName inst
825 la = isInternalName na
826 nb = getName $ getName b
827 lb = isInternalName nb
828 in (la && lb) || (nameModule na == nameModule nb)
829
830 isOverlappable i = hasOverlappableFlag $ overlapMode $ is_flag i
831
832 -- We consider the most specific instance unsafe when it both:
833 -- (1) Comes from a module compiled as `Safe`
834 -- (2) Is an orphan instance, OR, an instance for a MPTC
835 unsafeTopInstance inst = isSafeOverlap (is_flag inst) &&
836 (isOrphan (is_orphan inst) || classArity (is_cls inst) > 1)
837
838 ---------------
839 is_incoherent :: InstMatch -> Bool
840 is_incoherent (inst, _) = case overlapMode (is_flag inst) of
841 Incoherent _ -> True
842 _ -> False
843
844 ---------------
845 insert_overlapping :: InstMatch -> [InstMatch] -> [InstMatch]
846 -- ^ Add a new solution, knocking out strictly less specific ones
847 -- See Note [Rules for instance lookup]
848 insert_overlapping new_item [] = [new_item]
849 insert_overlapping new_item (old_item : old_items)
850 | new_beats_old -- New strictly overrides old
851 , not old_beats_new
852 , new_item `can_override` old_item
853 = insert_overlapping new_item old_items
854
855 | old_beats_new -- Old strictly overrides new
856 , not new_beats_old
857 , old_item `can_override` new_item
858 = old_item : old_items
859
860 -- Discard incoherent instances; see Note [Incoherent instances]
861 | is_incoherent old_item -- Old is incoherent; discard it
862 = insert_overlapping new_item old_items
863 | is_incoherent new_item -- New is incoherent; discard it
864 = old_item : old_items
865
866 -- Equal or incomparable, and neither is incoherent; keep both
867 | otherwise
868 = old_item : insert_overlapping new_item old_items
869 where
870
871 new_beats_old = new_item `more_specific_than` old_item
872 old_beats_new = old_item `more_specific_than` new_item
873
874 -- `instB` can be instantiated to match `instA`
875 -- or the two are equal
876 (instA,_) `more_specific_than` (instB,_)
877 = isJust (tcMatchTys (mkVarSet (is_tvs instB))
878 (is_tys instB) (is_tys instA))
879
880 (instA, _) `can_override` (instB, _)
881 = hasOverlappingFlag (overlapMode (is_flag instA))
882 || hasOverlappableFlag (overlapMode (is_flag instB))
883 -- Overlap permitted if either the more specific instance
884 -- is marked as overlapping, or the more general one is
885 -- marked as overlappable.
886 -- Latest change described in: Trac #9242.
887 -- Previous change: Trac #3877, Dec 10.
888
889 {-
890 Note [Incoherent instances]
891 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
892 For some classes, the choice of a particular instance does not matter, any one
893 is good. E.g. consider
894
895 class D a b where { opD :: a -> b -> String }
896 instance D Int b where ...
897 instance D a Int where ...
898
899 g (x::Int) = opD x x -- Wanted: D Int Int
900
901 For such classes this should work (without having to add an "instance D Int
902 Int", and using -XOverlappingInstances, which would then work). This is what
903 -XIncoherentInstances is for: Telling GHC "I don't care which instance you use;
904 if you can use one, use it."
905
906 Should this logic only work when *all* candidates have the incoherent flag, or
907 even when all but one have it? The right choice is the latter, which can be
908 justified by comparing the behaviour with how -XIncoherentInstances worked when
909 it was only about the unify-check (note [Overlapping instances]):
910
911 Example:
912 class C a b c where foo :: (a,b,c)
913 instance C [a] b Int
914 instance [incoherent] [Int] b c
915 instance [incoherent] C a Int c
916 Thanks to the incoherent flags,
917 [Wanted] C [a] b Int
918 works: Only instance one matches, the others just unify, but are marked
919 incoherent.
920
921 So I can write
922 (foo :: ([a],b,Int)) :: ([Int], Int, Int).
923 but if that works then I really want to be able to write
924 foo :: ([Int], Int, Int)
925 as well. Now all three instances from above match. None is more specific than
926 another, so none is ruled out by the normal overlapping rules. One of them is
927 not incoherent, but we still want this to compile. Hence the
928 "all-but-one-logic".
929
930 The implementation is in insert_overlapping, where we remove matching
931 incoherent instances as long as there are others.
932
933
934
935 ************************************************************************
936 * *
937 Binding decisions
938 * *
939 ************************************************************************
940 -}
941
942 instanceBindFun :: TyVar -> BindFlag
943 instanceBindFun tv | isTcTyVar tv && isOverlappableTyVar tv = Skolem
944 | otherwise = BindMe
945 -- Note [Binding when looking up instances]
946
947 {-
948 Note [Binding when looking up instances]
949 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
950 When looking up in the instance environment, or family-instance environment,
951 we are careful about multiple matches, as described above in
952 Note [Overlapping instances]
953
954 The key_tys can contain skolem constants, and we can guarantee that those
955 are never going to be instantiated to anything, so we should not involve
956 them in the unification test. Example:
957 class Foo a where { op :: a -> Int }
958 instance Foo a => Foo [a] -- NB overlap
959 instance Foo [Int] -- NB overlap
960 data T = forall a. Foo a => MkT a
961 f :: T -> Int
962 f (MkT x) = op [x,x]
963 The op [x,x] means we need (Foo [a]). Without the filterVarSet we'd
964 complain, saying that the choice of instance depended on the instantiation
965 of 'a'; but of course it isn't *going* to be instantiated.
966
967 We do this only for isOverlappableTyVar skolems. For example we reject
968 g :: forall a => [a] -> Int
969 g x = op x
970 on the grounds that the correct instance depends on the instantiation of 'a'
971 -}