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