New handling of overlapping inst in Safe Haskell
[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 Module
33 import Class
34 import Var
35 import VarSet
36 import Name
37 import NameSet
38 import TcType
39 import TyCon
40 import Unify
41 import Outputable
42 import ErrUtils
43 import BasicTypes
44 import UniqFM
45 import Util
46 import Id
47 import Binary
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 choose_one :: [NameSet] -> IsOrphan
240 choose_one nss = case nameSetElems (unionNameSets nss) of
241 [] -> IsOrphan
242 (n : _) -> NotOrphan (nameOccName n)
243
244 mkImportedInstance :: Name
245 -> [Maybe Name]
246 -> DFunId
247 -> OverlapFlag
248 -> IsOrphan
249 -> ClsInst
250 -- Used for imported instances, where we get the rough-match stuff
251 -- from the interface file
252 -- The bound tyvars of the dfun are guaranteed fresh, because
253 -- the dfun has been typechecked out of the same interface file
254 mkImportedInstance cls_nm mb_tcs dfun oflag orphan
255 = ClsInst { is_flag = oflag, is_dfun = dfun
256 , is_tvs = tvs, is_tys = tys
257 , is_cls_nm = cls_nm, is_cls = cls, is_tcs = mb_tcs
258 , is_orphan = orphan }
259 where
260 (tvs, _, cls, tys) = tcSplitDFunTy (idType dfun)
261
262 roughMatchTcs :: [Type] -> [Maybe Name]
263 roughMatchTcs tys = map rough tys
264 where
265 rough ty = case tcSplitTyConApp_maybe ty of
266 Just (tc,_) -> Just (tyConName tc)
267 Nothing -> Nothing
268
269 instanceCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool
270 -- (instanceCantMatch tcs1 tcs2) returns True if tcs1 cannot
271 -- possibly be instantiated to actual, nor vice versa;
272 -- False is non-committal
273 instanceCantMatch (Just t : ts) (Just a : as) = t/=a || instanceCantMatch ts as
274 instanceCantMatch _ _ = False -- Safe
275
276 {-
277 ************************************************************************
278 * *
279 Orphans
280 * *
281 ************************************************************************
282 -}
283
284 -- | Is this instance an orphan? If it is not an orphan, contains an 'OccName'
285 -- witnessing the instance's non-orphanhood.
286 -- See Note [Orphans]
287 data IsOrphan
288 = IsOrphan
289 | NotOrphan OccName -- The OccName 'n' witnesses the instance's non-orphanhood
290 -- In that case, the instance is fingerprinted as part
291 -- of the definition of 'n's definition
292 deriving (Data, Typeable)
293
294 -- | Returns true if 'IsOrphan' is orphan.
295 isOrphan :: IsOrphan -> Bool
296 isOrphan IsOrphan = True
297 isOrphan _ = False
298
299 -- | Returns true if 'IsOrphan' is not an orphan.
300 notOrphan :: IsOrphan -> Bool
301 notOrphan NotOrphan{} = True
302 notOrphan _ = False
303
304 instance Binary IsOrphan where
305 put_ bh IsOrphan = putByte bh 0
306 put_ bh (NotOrphan n) = do
307 putByte bh 1
308 put_ bh n
309 get bh = do
310 h <- getByte bh
311 case h of
312 0 -> return IsOrphan
313 _ -> do
314 n <- get bh
315 return $ NotOrphan n
316
317 {-
318 Note [Orphans]
319 ~~~~~~~~~~~~~~
320 Class instances, rules, and family instances are divided into orphans
321 and non-orphans. Roughly speaking, an instance/rule is an orphan if
322 its left hand side mentions nothing defined in this module. Orphan-hood
323 has two major consequences
324
325 * A module that contains orphans is called an "orphan module". If
326 the module being compiled depends (transitively) on an oprhan
327 module M, then M.hi is read in regardless of whether M is oherwise
328 needed. This is to ensure that we don't miss any instance decls in
329 M. But it's painful, because it means we need to keep track of all
330 the orphan modules below us.
331
332 * A non-orphan is not finger-printed separately. Instead, for
333 fingerprinting purposes it is treated as part of the entity it
334 mentions on the LHS. For example
335 data T = T1 | T2
336 instance Eq T where ....
337 The instance (Eq T) is incorprated as part of T's fingerprint.
338
339 In constrast, orphans are all fingerprinted together in the
340 mi_orph_hash field of the ModIface.
341
342 See MkIface.addFingerprints.
343
344 Orphan-hood is computed
345 * For class instances:
346 when we make a ClsInst
347 (because it is needed during instance lookup)
348
349 * For rules and family instances:
350 when we generate an IfaceRule (MkIface.coreRuleToIfaceRule)
351 or IfaceFamInst (MkIface.instanceToIfaceInst)
352
353 Note [When exactly is an instance decl an orphan?]
354 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
355 (see MkIface.instanceToIfaceInst, which implements this)
356 Roughly speaking, an instance is an orphan if its head (after the =>)
357 mentions nothing defined in this module.
358
359 Functional dependencies complicate the situation though. Consider
360
361 module M where { class C a b | a -> b }
362
363 and suppose we are compiling module X:
364
365 module X where
366 import M
367 data T = ...
368 instance C Int T where ...
369
370 This instance is an orphan, because when compiling a third module Y we
371 might get a constraint (C Int v), and we'd want to improve v to T. So
372 we must make sure X's instances are loaded, even if we do not directly
373 use anything from X.
374
375 More precisely, an instance is an orphan iff
376
377 If there are no fundeps, then at least of the names in
378 the instance head is locally defined.
379
380 If there are fundeps, then for every fundep, at least one of the
381 names free in a *non-determined* part of the instance head is
382 defined in this module.
383
384 (Note that these conditions hold trivially if the class is locally
385 defined.)
386
387
388 ************************************************************************
389 * *
390 InstEnv, ClsInstEnv
391 * *
392 ************************************************************************
393
394 A @ClsInstEnv@ all the instances of that class. The @Id@ inside a
395 ClsInstEnv mapping is the dfun for that instance.
396
397 If class C maps to a list containing the item ([a,b], [t1,t2,t3], dfun), then
398
399 forall a b, C t1 t2 t3 can be constructed by dfun
400
401 or, to put it another way, we have
402
403 instance (...) => C t1 t2 t3, witnessed by dfun
404 -}
405
406 ---------------------------------------------------
407 type InstEnv = UniqFM ClsInstEnv -- Maps Class to instances for that class
408
409 -- | 'InstEnvs' represents the combination of the global type class instance
410 -- environment, the local type class instance environment, and the set of
411 -- transitively reachable orphan modules (according to what modules have been
412 -- directly imported) used to test orphan instance visibility.
413 data InstEnvs = InstEnvs {
414 ie_global :: InstEnv, -- External-package instances
415 ie_local :: InstEnv, -- Home-package instances
416 ie_visible :: VisibleOrphanModules -- Set of all orphan modules transitively
417 -- reachable from the module being compiled
418 -- See Note [Instance lookup and orphan instances]
419 }
420
421 -- | Set of visible orphan modules, according to what modules have been directly
422 -- imported. This is based off of the dep_orphs field, which records
423 -- transitively reachable orphan modules (modules that define orphan instances).
424 type VisibleOrphanModules = ModuleSet
425
426 newtype ClsInstEnv
427 = ClsIE [ClsInst] -- The instances for a particular class, in any order
428
429 instance Outputable ClsInstEnv where
430 ppr (ClsIE is) = pprInstances is
431
432 -- INVARIANTS:
433 -- * The is_tvs are distinct in each ClsInst
434 -- of a ClsInstEnv (so we can safely unify them)
435
436 -- Thus, the @ClassInstEnv@ for @Eq@ might contain the following entry:
437 -- [a] ===> dfun_Eq_List :: forall a. Eq a => Eq [a]
438 -- The "a" in the pattern must be one of the forall'd variables in
439 -- the dfun type.
440
441 emptyInstEnv :: InstEnv
442 emptyInstEnv = emptyUFM
443
444 instEnvElts :: InstEnv -> [ClsInst]
445 instEnvElts ie = [elt | ClsIE elts <- eltsUFM ie, elt <- elts]
446
447 -- | Test if an instance is visible, by checking that its origin module
448 -- is in 'VisibleOrphanModules'.
449 -- See Note [Instance lookup and orphan instances]
450 instIsVisible :: VisibleOrphanModules -> ClsInst -> Bool
451 instIsVisible vis_mods ispec
452 -- NB: Instances from the interactive package always are visible. We can't
453 -- add interactive modules to the set since we keep creating new ones
454 -- as a GHCi session progresses.
455 | isInteractiveModule mod = True
456 | IsOrphan <- is_orphan ispec = mod `elemModuleSet` vis_mods
457 | otherwise = True
458 where
459 mod = nameModule (idName (is_dfun ispec))
460
461 classInstances :: InstEnvs -> Class -> [ClsInst]
462 classInstances (InstEnvs { ie_global = pkg_ie, ie_local = home_ie, ie_visible = vis_mods }) cls
463 = get home_ie ++ get pkg_ie
464 where
465 get env = case lookupUFM env cls of
466 Just (ClsIE insts) -> filter (instIsVisible vis_mods) insts
467 Nothing -> []
468
469 -- | Collects the names of concrete types and type constructors that make
470 -- up the head of a class instance. For instance, given `class Foo a b`:
471 --
472 -- `instance Foo (Either (Maybe Int) a) Bool` would yield
473 -- [Either, Maybe, Int, Bool]
474 --
475 -- Used in the implementation of ":info" in GHCi.
476 orphNamesOfClsInst :: ClsInst -> NameSet
477 orphNamesOfClsInst = orphNamesOfDFunHead . idType . instanceDFunId
478
479 -- | Checks for an exact match of ClsInst in the instance environment.
480 -- We use this when we do signature checking in TcRnDriver
481 memberInstEnv :: InstEnv -> ClsInst -> Bool
482 memberInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm } ) =
483 maybe False (\(ClsIE items) -> any (identicalClsInstHead ins_item) items)
484 (lookupUFM inst_env cls_nm)
485
486 extendInstEnvList :: InstEnv -> [ClsInst] -> InstEnv
487 extendInstEnvList inst_env ispecs = foldl extendInstEnv inst_env ispecs
488
489 extendInstEnv :: InstEnv -> ClsInst -> InstEnv
490 extendInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
491 = addToUFM_C add inst_env cls_nm (ClsIE [ins_item])
492 where
493 add (ClsIE cur_insts) _ = ClsIE (ins_item : cur_insts)
494
495 deleteFromInstEnv :: InstEnv -> ClsInst -> InstEnv
496 deleteFromInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
497 = adjustUFM adjust inst_env cls_nm
498 where
499 adjust (ClsIE items) = ClsIE (filterOut (identicalClsInstHead ins_item) items)
500
501 identicalClsInstHead :: ClsInst -> ClsInst -> Bool
502 -- ^ True when when the instance heads are the same
503 -- e.g. both are Eq [(a,b)]
504 -- Used for overriding in GHCi
505 -- Obviously should be insenstive to alpha-renaming
506 identicalClsInstHead (ClsInst { is_cls_nm = cls_nm1, is_tcs = rough1, is_tvs = tvs1, is_tys = tys1 })
507 (ClsInst { is_cls_nm = cls_nm2, is_tcs = rough2, is_tvs = tvs2, is_tys = tys2 })
508 = cls_nm1 == cls_nm2
509 && not (instanceCantMatch rough1 rough2) -- Fast check for no match, uses the "rough match" fields
510 && isJust (tcMatchTys (mkVarSet tvs1) tys1 tys2)
511 && isJust (tcMatchTys (mkVarSet tvs2) tys2 tys1)
512
513 {-
514 ************************************************************************
515 * *
516 Looking up an instance
517 * *
518 ************************************************************************
519
520 @lookupInstEnv@ looks up in a @InstEnv@, using a one-way match. Since
521 the env is kept ordered, the first match must be the only one. The
522 thing we are looking up can have an arbitrary "flexi" part.
523
524 Note [Instance lookup and orphan instances]
525 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
526 Suppose we are compiling a module M, and we have a zillion packages
527 loaded, and we are looking up an instance for C (T W). If we find a
528 match in module 'X' from package 'p', should be "in scope"; that is,
529
530 is p:X in the transitive closure of modules imported from M?
531
532 The difficulty is that the "zillion packages" might include ones loaded
533 through earlier invocations of the GHC API, or earlier module loads in GHCi.
534 They might not be in the dependencies of M itself; and if not, the instances
535 in them should not be visible. Trac #2182, #8427.
536
537 There are two cases:
538 * If the instance is *not an orphan*, then module X defines C, T, or W.
539 And in order for those types to be involved in typechecking M, it
540 must be that X is in the transitive closure of M's imports. So we
541 can use the instance.
542
543 * If the instance *is an orphan*, the above reasoning does not apply.
544 So we keep track of the set of orphan modules transitively below M;
545 this is the ie_visible field of InstEnvs, of type VisibleOrphanModules.
546
547 If module p:X is in this set, then we can use the instance, otherwise
548 we can't.
549
550 Note [Rules for instance lookup]
551 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
552 These functions implement the carefully-written rules in the user
553 manual section on "overlapping instances". At risk of duplication,
554 here are the rules. If the rules change, change this text and the
555 user manual simultaneously. The link may be this:
556 http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#instance-overlap
557
558 The willingness to be overlapped or incoherent is a property of the
559 instance declaration itself, controlled as follows:
560
561 * An instance is "incoherent"
562 if it has an INCOHERENT pragma, or
563 if it appears in a module compiled with -XIncoherentInstances.
564
565 * An instance is "overlappable"
566 if it has an OVERLAPPABLE or OVERLAPS pragma, or
567 if it appears in a module compiled with -XOverlappingInstances, or
568 if the instance is incoherent.
569
570 * An instance is "overlapping"
571 if it has an OVERLAPPING or OVERLAPS pragma, or
572 if it appears in a module compiled with -XOverlappingInstances, or
573 if the instance is incoherent.
574 compiled with -XOverlappingInstances.
575
576 Now suppose that, in some client module, we are searching for an instance
577 of the target constraint (C ty1 .. tyn). The search works like this.
578
579 * Find all instances I that match the target constraint; that is, the
580 target constraint is a substitution instance of I. These instance
581 declarations are the candidates.
582
583 * Find all non-candidate instances that unify with the target
584 constraint. Such non-candidates instances might match when the
585 target constraint is further instantiated. If all of them are
586 incoherent, proceed; if not, the search fails.
587
588 * Eliminate any candidate IX for which both of the following hold:
589 * There is another candidate IY that is strictly more specific;
590 that is, IY is a substitution instance of IX but not vice versa.
591
592 * Either IX is overlappable or IY is overlapping.
593
594 * If only one candidate remains, pick it. Otherwise if all remaining
595 candidates are incoherent, pick an arbitrary candidate. Otherwise fail.
596
597 Note [Overlapping instances] (NB: these notes are quite old)
598 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
599 Overlap is permitted, but only in such a way that one can make
600 a unique choice when looking up. That is, overlap is only permitted if
601 one template matches the other, or vice versa. So this is ok:
602
603 [a] [Int]
604
605 but this is not
606
607 (Int,a) (b,Int)
608
609 If overlap is permitted, the list is kept most specific first, so that
610 the first lookup is the right choice.
611
612
613 For now we just use association lists.
614
615 \subsection{Avoiding a problem with overlapping}
616
617 Consider this little program:
618
619 \begin{pseudocode}
620 class C a where c :: a
621 class C a => D a where d :: a
622
623 instance C Int where c = 17
624 instance D Int where d = 13
625
626 instance C a => C [a] where c = [c]
627 instance ({- C [a], -} D a) => D [a] where d = c
628
629 instance C [Int] where c = [37]
630
631 main = print (d :: [Int])
632 \end{pseudocode}
633
634 What do you think `main' prints (assuming we have overlapping instances, and
635 all that turned on)? Well, the instance for `D' at type `[a]' is defined to
636 be `c' at the same type, and we've got an instance of `C' at `[Int]', so the
637 answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because
638 the `C [Int]' instance is more specific).
639
640 Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong. That
641 was easy ;-) Let's just consult hugs for good measure. Wait - if I use old
642 hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it
643 doesn't even compile! What's going on!?
644
645 What hugs complains about is the `D [a]' instance decl.
646
647 \begin{pseudocode}
648 ERROR "mj.hs" (line 10): Cannot build superclass instance
649 *** Instance : D [a]
650 *** Context supplied : D a
651 *** Required superclass : C [a]
652 \end{pseudocode}
653
654 You might wonder what hugs is complaining about. It's saying that you
655 need to add `C [a]' to the context of the `D [a]' instance (as appears
656 in comments). But there's that `C [a]' instance decl one line above
657 that says that I can reduce the need for a `C [a]' instance to the
658 need for a `C a' instance, and in this case, I already have the
659 necessary `C a' instance (since we have `D a' explicitly in the
660 context, and `C' is a superclass of `D').
661
662 Unfortunately, the above reasoning indicates a premature commitment to the
663 generic `C [a]' instance. I.e., it prematurely rules out the more specific
664 instance `C [Int]'. This is the mistake that ghc-4.06 makes. The fix is to
665 add the context that hugs suggests (uncomment the `C [a]'), effectively
666 deferring the decision about which instance to use.
667
668 Now, interestingly enough, 4.04 has this same bug, but it's covered up
669 in this case by a little known `optimization' that was disabled in
670 4.06. Ghc-4.04 silently inserts any missing superclass context into
671 an instance declaration. In this case, it silently inserts the `C
672 [a]', and everything happens to work out.
673
674 (See `basicTypes/MkId:mkDictFunId' for the code in question. Search for
675 `Mark Jones', although Mark claims no credit for the `optimization' in
676 question, and would rather it stopped being called the `Mark Jones
677 optimization' ;-)
678
679 So, what's the fix? I think hugs has it right. Here's why. Let's try
680 something else out with ghc-4.04. Let's add the following line:
681
682 d' :: D a => [a]
683 d' = c
684
685 Everyone raise their hand who thinks that `d :: [Int]' should give a
686 different answer from `d' :: [Int]'. Well, in ghc-4.04, it does. The
687 `optimization' only applies to instance decls, not to regular
688 bindings, giving inconsistent behavior.
689
690 Old hugs had this same bug. Here's how we fixed it: like GHC, the
691 list of instances for a given class is ordered, so that more specific
692 instances come before more generic ones. For example, the instance
693 list for C might contain:
694 ..., C Int, ..., C a, ...
695 When we go to look for a `C Int' instance we'll get that one first.
696 But what if we go looking for a `C b' (`b' is unconstrained)? We'll
697 pass the `C Int' instance, and keep going. But if `b' is
698 unconstrained, then we don't know yet if the more specific instance
699 will eventually apply. GHC keeps going, and matches on the generic `C
700 a'. The fix is to, at each step, check to see if there's a reverse
701 match, and if so, abort the search. This prevents hugs from
702 prematurely chosing a generic instance when a more specific one
703 exists.
704
705 --Jeff
706 v
707 BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in
708 this test. Suppose the instance envt had
709 ..., forall a b. C a a b, ..., forall a b c. C a b c, ...
710 (still most specific first)
711 Now suppose we are looking for (C x y Int), where x and y are unconstrained.
712 C x y Int doesn't match the template {a,b} C a a b
713 but neither does
714 C a a b match the template {x,y} C x y Int
715 But still x and y might subsequently be unified so they *do* match.
716
717 Simple story: unify, don't match.
718 -}
719
720 type DFunInstType = Maybe Type
721 -- Just ty => Instantiate with this type
722 -- Nothing => Instantiate with any type of this tyvar's kind
723 -- See Note [DFunInstType: instantiating types]
724
725 type InstMatch = (ClsInst, [DFunInstType])
726
727 type ClsInstLookupResult
728 = ( [InstMatch] -- Successful matches
729 , [ClsInst] -- These don't match but do unify
730 , [InstMatch] ) -- Unsafe overlapped instances under Safe Haskell
731 -- (see Note [Safe Haskell Overlapping Instances] in
732 -- TcSimplify).
733
734 {-
735 Note [DFunInstType: instantiating types]
736 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
737 A successful match is a ClsInst, together with the types at which
738 the dfun_id in the ClsInst should be instantiated
739 The instantiating types are (Either TyVar Type)s because the dfun
740 might have some tyvars that *only* appear in arguments
741 dfun :: forall a b. C a b, Ord b => D [a]
742 When we match this against D [ty], we return the instantiating types
743 [Just ty, Nothing]
744 where the 'Nothing' indicates that 'b' can be freely instantiated.
745 (The caller instantiates it to a flexi type variable, which will
746 presumably later become fixed via functional dependencies.)
747 -}
748
749 -- |Look up an instance in the given instance environment. The given class application must match exactly
750 -- one instance and the match may not contain any flexi type variables. If the lookup is unsuccessful,
751 -- yield 'Left errorMessage'.
752 --
753 lookupUniqueInstEnv :: InstEnvs
754 -> Class -> [Type]
755 -> Either MsgDoc (ClsInst, [Type])
756 lookupUniqueInstEnv instEnv cls tys
757 = case lookupInstEnv False instEnv cls tys of
758 ([(inst, inst_tys)], _, _)
759 | noFlexiVar -> Right (inst, inst_tys')
760 | otherwise -> Left $ ptext (sLit "flexible type variable:") <+>
761 (ppr $ mkTyConApp (classTyCon cls) tys)
762 where
763 inst_tys' = [ty | Just ty <- inst_tys]
764 noFlexiVar = all isJust inst_tys
765 _other -> Left $ ptext (sLit "instance not found") <+> (ppr $ mkTyConApp (classTyCon cls) tys)
766
767 lookupInstEnv' :: InstEnv -- InstEnv to look in
768 -> VisibleOrphanModules -- But filter against this
769 -> Class -> [Type] -- What we are looking for
770 -> ([InstMatch], -- Successful matches
771 [ClsInst]) -- These don't match but do unify
772 -- The second component of the result pair happens when we look up
773 -- Foo [a]
774 -- in an InstEnv that has entries for
775 -- Foo [Int]
776 -- Foo [b]
777 -- Then which we choose would depend on the way in which 'a'
778 -- is instantiated. So we report that Foo [b] is a match (mapping b->a)
779 -- but Foo [Int] is a unifier. This gives the caller a better chance of
780 -- giving a suitable error message
781
782 lookupInstEnv' ie vis_mods cls tys
783 = lookup ie
784 where
785 rough_tcs = roughMatchTcs tys
786 all_tvs = all isNothing rough_tcs
787 --------------
788 lookup env = case lookupUFM env cls of
789 Nothing -> ([],[]) -- No instances for this class
790 Just (ClsIE insts) -> find [] [] insts
791
792 --------------
793 find ms us [] = (ms, us)
794 find ms us (item@(ClsInst { is_tcs = mb_tcs, is_tvs = tpl_tvs
795 , is_tys = tpl_tys, is_flag = oflag }) : rest)
796 | not (instIsVisible vis_mods item)
797 = find ms us rest -- See Note [Instance lookup and orphan instances]
798
799 -- Fast check for no match, uses the "rough match" fields
800 | instanceCantMatch rough_tcs mb_tcs
801 = find ms us rest
802
803 | Just subst <- tcMatchTys tpl_tv_set tpl_tys tys
804 = find ((item, map (lookup_tv subst) tpl_tvs) : ms) us rest
805
806 -- Does not match, so next check whether the things unify
807 -- See Note [Overlapping instances] and Note [Incoherent instances]
808 | Incoherent _ <- overlapMode oflag
809 = find ms us rest
810
811 | otherwise
812 = ASSERT2( tyVarsOfTypes tys `disjointVarSet` tpl_tv_set,
813 (ppr cls <+> ppr tys <+> ppr all_tvs) $$
814 (ppr tpl_tvs <+> ppr tpl_tys)
815 )
816 -- Unification will break badly if the variables overlap
817 -- They shouldn't because we allocate separate uniques for them
818 -- See Note [Template tyvars are fresh]
819 case tcUnifyTys instanceBindFun tpl_tys tys of
820 Just _ -> find ms (item:us) rest
821 Nothing -> find ms us rest
822 where
823 tpl_tv_set = mkVarSet tpl_tvs
824
825 ----------------
826 lookup_tv :: TvSubst -> TyVar -> DFunInstType
827 -- See Note [DFunInstType: instantiating types]
828 lookup_tv subst tv = case lookupTyVar subst tv of
829 Just ty -> Just ty
830 Nothing -> Nothing
831
832 ---------------
833 -- This is the common way to call this function.
834 lookupInstEnv :: Bool -- Check Safe Haskell overlap restrictions
835 -> InstEnvs -- External and home package inst-env
836 -> Class -> [Type] -- What we are looking for
837 -> ClsInstLookupResult
838 -- ^ See Note [Rules for instance lookup]
839 -- ^ See Note [Safe Haskell Overlapping Instances] in TcSimplify
840 -- ^ See Note [Safe Haskell Overlapping Instances Implementation] in TcSimplify
841 lookupInstEnv check_overlap_safe
842 (InstEnvs { ie_global = pkg_ie
843 , ie_local = home_ie
844 , ie_visible = vis_mods })
845 cls
846 tys
847 = (final_matches, final_unifs, unsafe_overlapped)
848 where
849 (home_matches, home_unifs) = lookupInstEnv' home_ie vis_mods cls tys
850 (pkg_matches, pkg_unifs) = lookupInstEnv' pkg_ie vis_mods cls tys
851 all_matches = home_matches ++ pkg_matches
852 all_unifs = home_unifs ++ pkg_unifs
853 final_matches = foldr insert_overlapping [] all_matches
854 -- Even if the unifs is non-empty (an error situation)
855 -- we still prune the matches, so that the error message isn't
856 -- misleading (complaining of multiple matches when some should be
857 -- overlapped away)
858
859 unsafe_overlapped
860 = case final_matches of
861 [match] -> check_safe match
862 _ -> []
863
864 -- If the selected match is incoherent, discard all unifiers
865 final_unifs = case final_matches of
866 (m:_) | is_incoherent m -> []
867 _ -> all_unifs
868
869 -- NOTE [Safe Haskell isSafeOverlap]
870 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
871 -- We restrict code compiled in 'Safe' mode from overriding code
872 -- compiled in any other mode. The rationale is that code compiled
873 -- in 'Safe' mode is code that is untrusted by the ghc user. So
874 -- we shouldn't let that code change the behaviour of code the
875 -- user didn't compile in 'Safe' mode since that's the code they
876 -- trust. So 'Safe' instances can only overlap instances from the
877 -- same module. A same instance origin policy for safe compiled
878 -- instances.
879 check_safe (inst,_)
880 = case check_overlap_safe && unsafeTopInstance inst of
881 -- make sure it only overlaps instances from the same module
882 True -> go [] all_matches
883 -- most specific is from a trusted location.
884 False -> []
885 where
886 go bad [] = bad
887 go bad (i@(x,_):unchecked) =
888 if inSameMod x || isOverlappable x
889 then go bad unchecked
890 else go (i:bad) unchecked
891
892 inSameMod b =
893 let na = getName $ getName inst
894 la = isInternalName na
895 nb = getName $ getName b
896 lb = isInternalName nb
897 in (la && lb) || (nameModule na == nameModule nb)
898
899 isOverlappable i = hasOverlappableFlag $ overlapMode $ is_flag i
900
901 -- We consider the most specific instance unsafe when it both:
902 -- (1) Comes from a module compiled as `Safe`
903 -- (2) Is an orphan instance, OR, an instance for a MPTC
904 unsafeTopInstance inst = isSafeOverlap (is_flag inst) &&
905 (isOrphan (is_orphan inst) || classArity (is_cls inst) > 1)
906
907 ---------------
908 is_incoherent :: InstMatch -> Bool
909 is_incoherent (inst, _) = case overlapMode (is_flag inst) of
910 Incoherent _ -> True
911 _ -> False
912
913 ---------------
914 insert_overlapping :: InstMatch -> [InstMatch] -> [InstMatch]
915 -- ^ Add a new solution, knocking out strictly less specific ones
916 -- See Note [Rules for instance lookup]
917 insert_overlapping new_item [] = [new_item]
918 insert_overlapping new_item (old_item : old_items)
919 | new_beats_old -- New strictly overrides old
920 , not old_beats_new
921 , new_item `can_override` old_item
922 = insert_overlapping new_item old_items
923
924 | old_beats_new -- Old strictly overrides new
925 , not new_beats_old
926 , old_item `can_override` new_item
927 = old_item : old_items
928
929 -- Discard incoherent instances; see Note [Incoherent instances]
930 | is_incoherent old_item -- Old is incoherent; discard it
931 = insert_overlapping new_item old_items
932 | is_incoherent new_item -- New is incoherent; discard it
933 = old_item : old_items
934
935 -- Equal or incomparable, and neither is incoherent; keep both
936 | otherwise
937 = old_item : insert_overlapping new_item old_items
938 where
939
940 new_beats_old = new_item `more_specific_than` old_item
941 old_beats_new = old_item `more_specific_than` new_item
942
943 -- `instB` can be instantiated to match `instA`
944 -- or the two are equal
945 (instA,_) `more_specific_than` (instB,_)
946 = isJust (tcMatchTys (mkVarSet (is_tvs instB))
947 (is_tys instB) (is_tys instA))
948
949 (instA, _) `can_override` (instB, _)
950 = hasOverlappingFlag (overlapMode (is_flag instA))
951 || hasOverlappableFlag (overlapMode (is_flag instB))
952 -- Overlap permitted if either the more specific instance
953 -- is marked as overlapping, or the more general one is
954 -- marked as overlappable.
955 -- Latest change described in: Trac #9242.
956 -- Previous change: Trac #3877, Dec 10.
957
958 {-
959 Note [Incoherent instances]
960 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
961 For some classes, the choice of a particular instance does not matter, any one
962 is good. E.g. consider
963
964 class D a b where { opD :: a -> b -> String }
965 instance D Int b where ...
966 instance D a Int where ...
967
968 g (x::Int) = opD x x -- Wanted: D Int Int
969
970 For such classes this should work (without having to add an "instance D Int
971 Int", and using -XOverlappingInstances, which would then work). This is what
972 -XIncoherentInstances is for: Telling GHC "I don't care which instance you use;
973 if you can use one, use it."
974
975 Should this logic only work when *all* candidates have the incoherent flag, or
976 even when all but one have it? The right choice is the latter, which can be
977 justified by comparing the behaviour with how -XIncoherentInstances worked when
978 it was only about the unify-check (note [Overlapping instances]):
979
980 Example:
981 class C a b c where foo :: (a,b,c)
982 instance C [a] b Int
983 instance [incoherent] [Int] b c
984 instance [incoherent] C a Int c
985 Thanks to the incoherent flags,
986 [Wanted] C [a] b Int
987 works: Only instance one matches, the others just unify, but are marked
988 incoherent.
989
990 So I can write
991 (foo :: ([a],b,Int)) :: ([Int], Int, Int).
992 but if that works then I really want to be able to write
993 foo :: ([Int], Int, Int)
994 as well. Now all three instances from above match. None is more specific than
995 another, so none is ruled out by the normal overlapping rules. One of them is
996 not incoherent, but we still want this to compile. Hence the
997 "all-but-one-logic".
998
999 The implementation is in insert_overlapping, where we remove matching
1000 incoherent instances as long as there are others.
1001
1002
1003
1004 ************************************************************************
1005 * *
1006 Binding decisions
1007 * *
1008 ************************************************************************
1009 -}
1010
1011 instanceBindFun :: TyVar -> BindFlag
1012 instanceBindFun tv | isTcTyVar tv && isOverlappableTyVar tv = Skolem
1013 | otherwise = BindMe
1014 -- Note [Binding when looking up instances]
1015
1016 {-
1017 Note [Binding when looking up instances]
1018 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1019 When looking up in the instance environment, or family-instance environment,
1020 we are careful about multiple matches, as described above in
1021 Note [Overlapping instances]
1022
1023 The key_tys can contain skolem constants, and we can guarantee that those
1024 are never going to be instantiated to anything, so we should not involve
1025 them in the unification test. Example:
1026 class Foo a where { op :: a -> Int }
1027 instance Foo a => Foo [a] -- NB overlap
1028 instance Foo [Int] -- NB overlap
1029 data T = forall a. Foo a => MkT a
1030 f :: T -> Int
1031 f (MkT x) = op [x,x]
1032 The op [x,x] means we need (Foo [a]). Without the filterVarSet we'd
1033 complain, saying that the choice of instance depended on the instantiation
1034 of 'a'; but of course it isn't *going* to be instantiated.
1035
1036 We do this only for isOverlappableTyVar skolems. For example we reject
1037 g :: forall a => [a] -> Int
1038 g x = op x
1039 on the grounds that the correct instance depends on the instantiation of 'a'
1040 -}