8d1c855b1643ffa7c079da96b641455a4582a2b9
[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 , Bool) -- True if error condition caused by
731 -- SafeHaskell condition.
732
733 {-
734 Note [DFunInstType: instantiating types]
735 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
736 A successful match is a ClsInst, together with the types at which
737 the dfun_id in the ClsInst should be instantiated
738 The instantiating types are (Either TyVar Type)s because the dfun
739 might have some tyvars that *only* appear in arguments
740 dfun :: forall a b. C a b, Ord b => D [a]
741 When we match this against D [ty], we return the instantiating types
742 [Just ty, Nothing]
743 where the 'Nothing' indicates that 'b' can be freely instantiated.
744 (The caller instantiates it to a flexi type variable, which will
745 presumably later become fixed via functional dependencies.)
746 -}
747
748 -- |Look up an instance in the given instance environment. The given class application must match exactly
749 -- one instance and the match may not contain any flexi type variables. If the lookup is unsuccessful,
750 -- yield 'Left errorMessage'.
751 --
752 lookupUniqueInstEnv :: InstEnvs
753 -> Class -> [Type]
754 -> Either MsgDoc (ClsInst, [Type])
755 lookupUniqueInstEnv instEnv cls tys
756 = case lookupInstEnv instEnv cls tys of
757 ([(inst, inst_tys)], _, _)
758 | noFlexiVar -> Right (inst, inst_tys')
759 | otherwise -> Left $ ptext (sLit "flexible type variable:") <+>
760 (ppr $ mkTyConApp (classTyCon cls) tys)
761 where
762 inst_tys' = [ty | Just ty <- inst_tys]
763 noFlexiVar = all isJust inst_tys
764 _other -> Left $ ptext (sLit "instance not found") <+> (ppr $ mkTyConApp (classTyCon cls) tys)
765
766 lookupInstEnv' :: InstEnv -- InstEnv to look in
767 -> VisibleOrphanModules -- But filter against this
768 -> Class -> [Type] -- What we are looking for
769 -> ([InstMatch], -- Successful matches
770 [ClsInst]) -- These don't match but do unify
771 -- The second component of the result pair happens when we look up
772 -- Foo [a]
773 -- in an InstEnv that has entries for
774 -- Foo [Int]
775 -- Foo [b]
776 -- Then which we choose would depend on the way in which 'a'
777 -- is instantiated. So we report that Foo [b] is a match (mapping b->a)
778 -- but Foo [Int] is a unifier. This gives the caller a better chance of
779 -- giving a suitable error message
780
781 lookupInstEnv' ie vis_mods cls tys
782 = lookup ie
783 where
784 rough_tcs = roughMatchTcs tys
785 all_tvs = all isNothing rough_tcs
786 --------------
787 lookup env = case lookupUFM env cls of
788 Nothing -> ([],[]) -- No instances for this class
789 Just (ClsIE insts) -> find [] [] insts
790
791 --------------
792 find ms us [] = (ms, us)
793 find ms us (item@(ClsInst { is_tcs = mb_tcs, is_tvs = tpl_tvs
794 , is_tys = tpl_tys, is_flag = oflag }) : rest)
795 | not (instIsVisible vis_mods item)
796 = find ms us rest -- See Note [Instance lookup and orphan instances]
797
798 -- Fast check for no match, uses the "rough match" fields
799 | instanceCantMatch rough_tcs mb_tcs
800 = find ms us rest
801
802 | Just subst <- tcMatchTys tpl_tv_set tpl_tys tys
803 = find ((item, map (lookup_tv subst) tpl_tvs) : ms) us rest
804
805 -- Does not match, so next check whether the things unify
806 -- See Note [Overlapping instances] and Note [Incoherent instances]
807 | Incoherent _ <- overlapMode oflag
808 = find ms us rest
809
810 | otherwise
811 = ASSERT2( tyVarsOfTypes tys `disjointVarSet` tpl_tv_set,
812 (ppr cls <+> ppr tys <+> ppr all_tvs) $$
813 (ppr tpl_tvs <+> ppr tpl_tys)
814 )
815 -- Unification will break badly if the variables overlap
816 -- They shouldn't because we allocate separate uniques for them
817 -- See Note [Template tyvars are fresh]
818 case tcUnifyTys instanceBindFun tpl_tys tys of
819 Just _ -> find ms (item:us) rest
820 Nothing -> find ms us rest
821 where
822 tpl_tv_set = mkVarSet tpl_tvs
823
824 ----------------
825 lookup_tv :: TvSubst -> TyVar -> DFunInstType
826 -- See Note [DFunInstType: instantiating types]
827 lookup_tv subst tv = case lookupTyVar subst tv of
828 Just ty -> Just ty
829 Nothing -> Nothing
830
831 ---------------
832 -- This is the common way to call this function.
833 lookupInstEnv :: InstEnvs -- External and home package inst-env
834 -> Class -> [Type] -- What we are looking for
835 -> ClsInstLookupResult
836 -- ^ See Note [Rules for instance lookup]
837 lookupInstEnv (InstEnvs { ie_global = pkg_ie, ie_local = home_ie, ie_visible = vis_mods }) cls tys
838 = (final_matches, final_unifs, safe_fail)
839 where
840 (home_matches, home_unifs) = lookupInstEnv' home_ie vis_mods cls tys
841 (pkg_matches, pkg_unifs) = lookupInstEnv' pkg_ie vis_mods cls tys
842 all_matches = home_matches ++ pkg_matches
843 all_unifs = home_unifs ++ pkg_unifs
844 pruned_matches = foldr insert_overlapping [] all_matches
845 -- Even if the unifs is non-empty (an error situation)
846 -- we still prune the matches, so that the error message isn't
847 -- misleading (complaining of multiple matches when some should be
848 -- overlapped away)
849
850 (final_matches, safe_fail)
851 = case pruned_matches of
852 [match] -> check_safe match all_matches
853 _ -> (pruned_matches, False)
854
855 -- If the selected match is incoherent, discard all unifiers
856 final_unifs = case final_matches of
857 (m:_) | is_incoherent m -> []
858 _ -> all_unifs
859
860 -- NOTE [Safe Haskell isSafeOverlap]
861 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
862 -- We restrict code compiled in 'Safe' mode from overriding code
863 -- compiled in any other mode. The rationale is that code compiled
864 -- in 'Safe' mode is code that is untrusted by the ghc user. So
865 -- we shouldn't let that code change the behaviour of code the
866 -- user didn't compile in 'Safe' mode since that's the code they
867 -- trust. So 'Safe' instances can only overlap instances from the
868 -- same module. A same instance origin policy for safe compiled
869 -- instances.
870 check_safe match@(inst,_) others
871 = case isSafeOverlap (is_flag inst) of
872 -- most specific isn't from a Safe module so OK
873 False -> ([match], False)
874 -- otherwise we make sure it only overlaps instances from
875 -- the same module
876 True -> (go [] others, True)
877 where
878 go bad [] = match:bad
879 go bad (i@(x,_):unchecked) =
880 if inSameMod x
881 then go bad unchecked
882 else go (i:bad) unchecked
883
884 inSameMod b =
885 let na = getName $ getName inst
886 la = isInternalName na
887 nb = getName $ getName b
888 lb = isInternalName nb
889 in (la && lb) || (nameModule na == nameModule nb)
890
891 ---------------
892 is_incoherent :: InstMatch -> Bool
893 is_incoherent (inst, _) = case overlapMode (is_flag inst) of
894 Incoherent _ -> True
895 _ -> False
896
897 ---------------
898 insert_overlapping :: InstMatch -> [InstMatch] -> [InstMatch]
899 -- ^ Add a new solution, knocking out strictly less specific ones
900 -- See Note [Rules for instance lookup]
901 insert_overlapping new_item [] = [new_item]
902 insert_overlapping new_item (old_item : old_items)
903 | new_beats_old -- New strictly overrides old
904 , not old_beats_new
905 , new_item `can_override` old_item
906 = insert_overlapping new_item old_items
907
908 | old_beats_new -- Old strictly overrides new
909 , not new_beats_old
910 , old_item `can_override` new_item
911 = old_item : old_items
912
913 -- Discard incoherent instances; see Note [Incoherent instances]
914 | is_incoherent old_item -- Old is incoherent; discard it
915 = insert_overlapping new_item old_items
916 | is_incoherent new_item -- New is incoherent; discard it
917 = old_item : old_items
918
919 -- Equal or incomparable, and neither is incoherent; keep both
920 | otherwise
921 = old_item : insert_overlapping new_item old_items
922 where
923
924 new_beats_old = new_item `more_specific_than` old_item
925 old_beats_new = old_item `more_specific_than` new_item
926
927 -- `instB` can be instantiated to match `instA`
928 -- or the two are equal
929 (instA,_) `more_specific_than` (instB,_)
930 = isJust (tcMatchTys (mkVarSet (is_tvs instB))
931 (is_tys instB) (is_tys instA))
932
933 (instA, _) `can_override` (instB, _)
934 = hasOverlappingFlag (overlapMode (is_flag instA))
935 || hasOverlappableFlag (overlapMode (is_flag instB))
936 -- Overlap permitted if either the more specific instance
937 -- is marked as overlapping, or the more general one is
938 -- marked as overlappable.
939 -- Latest change described in: Trac #9242.
940 -- Previous change: Trac #3877, Dec 10.
941
942 {-
943 Note [Incoherent instances]
944 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
945 For some classes, the choice of a particular instance does not matter, any one
946 is good. E.g. consider
947
948 class D a b where { opD :: a -> b -> String }
949 instance D Int b where ...
950 instance D a Int where ...
951
952 g (x::Int) = opD x x -- Wanted: D Int Int
953
954 For such classes this should work (without having to add an "instance D Int
955 Int", and using -XOverlappingInstances, which would then work). This is what
956 -XIncoherentInstances is for: Telling GHC "I don't care which instance you use;
957 if you can use one, use it."
958
959 Should this logic only work when *all* candidates have the incoherent flag, or
960 even when all but one have it? The right choice is the latter, which can be
961 justified by comparing the behaviour with how -XIncoherentInstances worked when
962 it was only about the unify-check (note [Overlapping instances]):
963
964 Example:
965 class C a b c where foo :: (a,b,c)
966 instance C [a] b Int
967 instance [incoherent] [Int] b c
968 instance [incoherent] C a Int c
969 Thanks to the incoherent flags,
970 [Wanted] C [a] b Int
971 works: Only instance one matches, the others just unify, but are marked
972 incoherent.
973
974 So I can write
975 (foo :: ([a],b,Int)) :: ([Int], Int, Int).
976 but if that works then I really want to be able to write
977 foo :: ([Int], Int, Int)
978 as well. Now all three instances from above match. None is more specific than
979 another, so none is ruled out by the normal overlapping rules. One of them is
980 not incoherent, but we still want this to compile. Hence the
981 "all-but-one-logic".
982
983 The implementation is in insert_overlapping, where we remove matching
984 incoherent instances as long as there are others.
985
986
987
988 ************************************************************************
989 * *
990 Binding decisions
991 * *
992 ************************************************************************
993 -}
994
995 instanceBindFun :: TyVar -> BindFlag
996 instanceBindFun tv | isTcTyVar tv && isOverlappableTyVar tv = Skolem
997 | otherwise = BindMe
998 -- Note [Binding when looking up instances]
999
1000 {-
1001 Note [Binding when looking up instances]
1002 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1003 When looking up in the instance environment, or family-instance environment,
1004 we are careful about multiple matches, as described above in
1005 Note [Overlapping instances]
1006
1007 The key_tys can contain skolem constants, and we can guarantee that those
1008 are never going to be instantiated to anything, so we should not involve
1009 them in the unification test. Example:
1010 class Foo a where { op :: a -> Int }
1011 instance Foo a => Foo [a] -- NB overlap
1012 instance Foo [Int] -- NB overlap
1013 data T = forall a. Foo a => MkT a
1014 f :: T -> Int
1015 f (MkT x) = op [x,x]
1016 The op [x,x] means we need (Foo [a]). Without the filterVarSet we'd
1017 complain, saying that the choice of instance depended on the instantiation
1018 of 'a'; but of course it isn't *going* to be instantiated.
1019
1020 We do this only for isOverlappableTyVar skolems. For example we reject
1021 g :: forall a => [a] -> Int
1022 g x = op x
1023 on the grounds that the correct instance depends on the instantiation of 'a'
1024 -}