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