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