Add GHCi :instances command
[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, instEnvClasses,
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 instEnvClasses :: InstEnv -> [Class]
431 instEnvClasses ie = [is_cls e | ClsIE (e : _) <- eltsUDFM ie]
432
433 -- | Test if an instance is visible, by checking that its origin module
434 -- is in 'VisibleOrphanModules'.
435 -- See Note [Instance lookup and orphan instances]
436 instIsVisible :: VisibleOrphanModules -> ClsInst -> Bool
437 instIsVisible vis_mods ispec
438 -- NB: Instances from the interactive package always are visible. We can't
439 -- add interactive modules to the set since we keep creating new ones
440 -- as a GHCi session progresses.
441 = case nameModule_maybe (is_dfun_name ispec) of
442 Nothing -> True
443 Just mod | isInteractiveModule mod -> True
444 | IsOrphan <- is_orphan ispec -> mod `elemModuleSet` vis_mods
445 | otherwise -> True
446
447 classInstances :: InstEnvs -> Class -> [ClsInst]
448 classInstances (InstEnvs { ie_global = pkg_ie, ie_local = home_ie, ie_visible = vis_mods }) cls
449 = get home_ie ++ get pkg_ie
450 where
451 get env = case lookupUDFM env cls of
452 Just (ClsIE insts) -> filter (instIsVisible vis_mods) insts
453 Nothing -> []
454
455 -- | Checks for an exact match of ClsInst in the instance environment.
456 -- We use this when we do signature checking in TcRnDriver
457 memberInstEnv :: InstEnv -> ClsInst -> Bool
458 memberInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm } ) =
459 maybe False (\(ClsIE items) -> any (identicalDFunType ins_item) items)
460 (lookupUDFM inst_env cls_nm)
461 where
462 identicalDFunType cls1 cls2 =
463 eqType (varType (is_dfun cls1)) (varType (is_dfun cls2))
464
465 extendInstEnvList :: InstEnv -> [ClsInst] -> InstEnv
466 extendInstEnvList inst_env ispecs = foldl' extendInstEnv inst_env ispecs
467
468 extendInstEnv :: InstEnv -> ClsInst -> InstEnv
469 extendInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
470 = addToUDFM_C add inst_env cls_nm (ClsIE [ins_item])
471 where
472 add (ClsIE cur_insts) _ = ClsIE (ins_item : cur_insts)
473
474 deleteFromInstEnv :: InstEnv -> ClsInst -> InstEnv
475 deleteFromInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
476 = adjustUDFM adjust inst_env cls_nm
477 where
478 adjust (ClsIE items) = ClsIE (filterOut (identicalClsInstHead ins_item) items)
479
480 deleteDFunFromInstEnv :: InstEnv -> DFunId -> InstEnv
481 -- Delete a specific instance fron an InstEnv
482 deleteDFunFromInstEnv inst_env dfun
483 = adjustUDFM adjust inst_env cls
484 where
485 (_, _, cls, _) = tcSplitDFunTy (idType dfun)
486 adjust (ClsIE items) = ClsIE (filterOut same_dfun items)
487 same_dfun (ClsInst { is_dfun = dfun' }) = dfun == dfun'
488
489 identicalClsInstHead :: ClsInst -> ClsInst -> Bool
490 -- ^ True when when the instance heads are the same
491 -- e.g. both are Eq [(a,b)]
492 -- Used for overriding in GHCi
493 -- Obviously should be insenstive to alpha-renaming
494 identicalClsInstHead (ClsInst { is_cls_nm = cls_nm1, is_tcs = rough1, is_tys = tys1 })
495 (ClsInst { is_cls_nm = cls_nm2, is_tcs = rough2, is_tys = tys2 })
496 = cls_nm1 == cls_nm2
497 && not (instanceCantMatch rough1 rough2) -- Fast check for no match, uses the "rough match" fields
498 && isJust (tcMatchTys tys1 tys2)
499 && isJust (tcMatchTys tys2 tys1)
500
501 {-
502 ************************************************************************
503 * *
504 Looking up an instance
505 * *
506 ************************************************************************
507
508 @lookupInstEnv@ looks up in a @InstEnv@, using a one-way match. Since
509 the env is kept ordered, the first match must be the only one. The
510 thing we are looking up can have an arbitrary "flexi" part.
511
512 Note [Instance lookup and orphan instances]
513 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
514 Suppose we are compiling a module M, and we have a zillion packages
515 loaded, and we are looking up an instance for C (T W). If we find a
516 match in module 'X' from package 'p', should be "in scope"; that is,
517
518 is p:X in the transitive closure of modules imported from M?
519
520 The difficulty is that the "zillion packages" might include ones loaded
521 through earlier invocations of the GHC API, or earlier module loads in GHCi.
522 They might not be in the dependencies of M itself; and if not, the instances
523 in them should not be visible. #2182, #8427.
524
525 There are two cases:
526 * If the instance is *not an orphan*, then module X defines C, T, or W.
527 And in order for those types to be involved in typechecking M, it
528 must be that X is in the transitive closure of M's imports. So we
529 can use the instance.
530
531 * If the instance *is an orphan*, the above reasoning does not apply.
532 So we keep track of the set of orphan modules transitively below M;
533 this is the ie_visible field of InstEnvs, of type VisibleOrphanModules.
534
535 If module p:X is in this set, then we can use the instance, otherwise
536 we can't.
537
538 Note [Rules for instance lookup]
539 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
540 These functions implement the carefully-written rules in the user
541 manual section on "overlapping instances". At risk of duplication,
542 here are the rules. If the rules change, change this text and the
543 user manual simultaneously. The link may be this:
544 http://www.haskell.org/ghc/docs/latest/html/users_guide/glasgow_exts.html#instance-overlap
545
546 The willingness to be overlapped or incoherent is a property of the
547 instance declaration itself, controlled as follows:
548
549 * An instance is "incoherent"
550 if it has an INCOHERENT pragma, or
551 if it appears in a module compiled with -XIncoherentInstances.
552
553 * An instance is "overlappable"
554 if it has an OVERLAPPABLE or OVERLAPS pragma, or
555 if it appears in a module compiled with -XOverlappingInstances, or
556 if the instance is incoherent.
557
558 * An instance is "overlapping"
559 if it has an OVERLAPPING or OVERLAPS pragma, or
560 if it appears in a module compiled with -XOverlappingInstances, or
561 if the instance is incoherent.
562 compiled with -XOverlappingInstances.
563
564 Now suppose that, in some client module, we are searching for an instance
565 of the target constraint (C ty1 .. tyn). The search works like this.
566
567 * Find all instances `I` that *match* the target constraint; that is, the
568 target constraint is a substitution instance of `I`. These instance
569 declarations are the *candidates*.
570
571 * Eliminate any candidate `IX` for which both of the following hold:
572
573 - There is another candidate `IY` that is strictly more specific; that
574 is, `IY` is a substitution instance of `IX` but not vice versa.
575
576 - Either `IX` is *overlappable*, or `IY` is *overlapping*. (This
577 "either/or" design, rather than a "both/and" design, allow a
578 client to deliberately override an instance from a library,
579 without requiring a change to the library.)
580
581 - If exactly one non-incoherent candidate remains, select it. If all
582 remaining candidates are incoherent, select an arbitrary one.
583 Otherwise the search fails (i.e. when more than one surviving
584 candidate is not incoherent).
585
586 - If the selected candidate (from the previous step) is incoherent, the
587 search succeeds, returning that candidate.
588
589 - If not, find all instances that *unify* with the target constraint,
590 but do not *match* it. Such non-candidate instances might match when
591 the target constraint is further instantiated. If all of them are
592 incoherent, the search succeeds, returning the selected candidate; if
593 not, the search fails.
594
595 Notice that these rules are not influenced by flag settings in the
596 client module, where the instances are *used*. These rules make it
597 possible for a library author to design a library that relies on
598 overlapping instances without the client having to know.
599
600 Note [Overlapping instances] (NB: these notes are quite old)
601 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
602 Overlap is permitted, but only in such a way that one can make
603 a unique choice when looking up. That is, overlap is only permitted if
604 one template matches the other, or vice versa. So this is ok:
605
606 [a] [Int]
607
608 but this is not
609
610 (Int,a) (b,Int)
611
612 If overlap is permitted, the list is kept most specific first, so that
613 the first lookup is the right choice.
614
615
616 For now we just use association lists.
617
618 \subsection{Avoiding a problem with overlapping}
619
620 Consider this little program:
621
622 \begin{pseudocode}
623 class C a where c :: a
624 class C a => D a where d :: a
625
626 instance C Int where c = 17
627 instance D Int where d = 13
628
629 instance C a => C [a] where c = [c]
630 instance ({- C [a], -} D a) => D [a] where d = c
631
632 instance C [Int] where c = [37]
633
634 main = print (d :: [Int])
635 \end{pseudocode}
636
637 What do you think `main' prints (assuming we have overlapping instances, and
638 all that turned on)? Well, the instance for `D' at type `[a]' is defined to
639 be `c' at the same type, and we've got an instance of `C' at `[Int]', so the
640 answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because
641 the `C [Int]' instance is more specific).
642
643 Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong. That
644 was easy ;-) Let's just consult hugs for good measure. Wait - if I use old
645 hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it
646 doesn't even compile! What's going on!?
647
648 What hugs complains about is the `D [a]' instance decl.
649
650 \begin{pseudocode}
651 ERROR "mj.hs" (line 10): Cannot build superclass instance
652 *** Instance : D [a]
653 *** Context supplied : D a
654 *** Required superclass : C [a]
655 \end{pseudocode}
656
657 You might wonder what hugs is complaining about. It's saying that you
658 need to add `C [a]' to the context of the `D [a]' instance (as appears
659 in comments). But there's that `C [a]' instance decl one line above
660 that says that I can reduce the need for a `C [a]' instance to the
661 need for a `C a' instance, and in this case, I already have the
662 necessary `C a' instance (since we have `D a' explicitly in the
663 context, and `C' is a superclass of `D').
664
665 Unfortunately, the above reasoning indicates a premature commitment to the
666 generic `C [a]' instance. I.e., it prematurely rules out the more specific
667 instance `C [Int]'. This is the mistake that ghc-4.06 makes. The fix is to
668 add the context that hugs suggests (uncomment the `C [a]'), effectively
669 deferring the decision about which instance to use.
670
671 Now, interestingly enough, 4.04 has this same bug, but it's covered up
672 in this case by a little known `optimization' that was disabled in
673 4.06. Ghc-4.04 silently inserts any missing superclass context into
674 an instance declaration. In this case, it silently inserts the `C
675 [a]', and everything happens to work out.
676
677 (See `basicTypes/MkId:mkDictFunId' for the code in question. Search for
678 `Mark Jones', although Mark claims no credit for the `optimization' in
679 question, and would rather it stopped being called the `Mark Jones
680 optimization' ;-)
681
682 So, what's the fix? I think hugs has it right. Here's why. Let's try
683 something else out with ghc-4.04. Let's add the following line:
684
685 d' :: D a => [a]
686 d' = c
687
688 Everyone raise their hand who thinks that `d :: [Int]' should give a
689 different answer from `d' :: [Int]'. Well, in ghc-4.04, it does. The
690 `optimization' only applies to instance decls, not to regular
691 bindings, giving inconsistent behavior.
692
693 Old hugs had this same bug. Here's how we fixed it: like GHC, the
694 list of instances for a given class is ordered, so that more specific
695 instances come before more generic ones. For example, the instance
696 list for C might contain:
697 ..., C Int, ..., C a, ...
698 When we go to look for a `C Int' instance we'll get that one first.
699 But what if we go looking for a `C b' (`b' is unconstrained)? We'll
700 pass the `C Int' instance, and keep going. But if `b' is
701 unconstrained, then we don't know yet if the more specific instance
702 will eventually apply. GHC keeps going, and matches on the generic `C
703 a'. The fix is to, at each step, check to see if there's a reverse
704 match, and if so, abort the search. This prevents hugs from
705 prematurely chosing a generic instance when a more specific one
706 exists.
707
708 --Jeff
709
710 BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in
711 this test. Suppose the instance envt had
712 ..., forall a b. C a a b, ..., forall a b c. C a b c, ...
713 (still most specific first)
714 Now suppose we are looking for (C x y Int), where x and y are unconstrained.
715 C x y Int doesn't match the template {a,b} C a a b
716 but neither does
717 C a a b match the template {x,y} C x y Int
718 But still x and y might subsequently be unified so they *do* match.
719
720 Simple story: unify, don't match.
721 -}
722
723 type DFunInstType = Maybe Type
724 -- Just ty => Instantiate with this type
725 -- Nothing => Instantiate with any type of this tyvar's kind
726 -- See Note [DFunInstType: instantiating types]
727
728 type InstMatch = (ClsInst, [DFunInstType])
729
730 type ClsInstLookupResult
731 = ( [InstMatch] -- Successful matches
732 , [ClsInst] -- These don't match but do unify
733 , [InstMatch] ) -- Unsafe overlapped instances under Safe Haskell
734 -- (see Note [Safe Haskell Overlapping Instances] in
735 -- TcSimplify).
736
737 {-
738 Note [DFunInstType: instantiating types]
739 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
740 A successful match is a ClsInst, together with the types at which
741 the dfun_id in the ClsInst should be instantiated
742 The instantiating types are (Either TyVar Type)s because the dfun
743 might have some tyvars that *only* appear in arguments
744 dfun :: forall a b. C a b, Ord b => D [a]
745 When we match this against D [ty], we return the instantiating types
746 [Just ty, Nothing]
747 where the 'Nothing' indicates that 'b' can be freely instantiated.
748 (The caller instantiates it to a flexi type variable, which will
749 presumably later become fixed via functional dependencies.)
750 -}
751
752 -- |Look up an instance in the given instance environment. The given class application must match exactly
753 -- one instance and the match may not contain any flexi type variables. If the lookup is unsuccessful,
754 -- yield 'Left errorMessage'.
755 lookupUniqueInstEnv :: InstEnvs
756 -> Class -> [Type]
757 -> Either MsgDoc (ClsInst, [Type])
758 lookupUniqueInstEnv instEnv cls tys
759 = case lookupInstEnv False instEnv cls tys of
760 ([(inst, inst_tys)], _, _)
761 | noFlexiVar -> Right (inst, inst_tys')
762 | otherwise -> Left $ text "flexible type variable:" <+>
763 (ppr $ mkTyConApp (classTyCon cls) tys)
764 where
765 inst_tys' = [ty | Just ty <- inst_tys]
766 noFlexiVar = all isJust inst_tys
767 _other -> Left $ text "instance not found" <+>
768 (ppr $ mkTyConApp (classTyCon cls) tys)
769
770 lookupInstEnv' :: InstEnv -- InstEnv to look in
771 -> VisibleOrphanModules -- But filter against this
772 -> Class -> [Type] -- What we are looking for
773 -> ([InstMatch], -- Successful matches
774 [ClsInst]) -- These don't match but do unify
775 -- (no incoherent ones in here)
776 -- The second component of the result pair happens when we look up
777 -- Foo [a]
778 -- in an InstEnv that has entries for
779 -- Foo [Int]
780 -- Foo [b]
781 -- Then which we choose would depend on the way in which 'a'
782 -- is instantiated. So we report that Foo [b] is a match (mapping b->a)
783 -- but Foo [Int] is a unifier. This gives the caller a better chance of
784 -- giving a suitable error message
785
786 lookupInstEnv' ie vis_mods cls tys
787 = lookup ie
788 where
789 rough_tcs = roughMatchTcs tys
790 all_tvs = all isNothing rough_tcs
791
792 --------------
793 lookup env = case lookupUDFM env cls of
794 Nothing -> ([],[]) -- No instances for this class
795 Just (ClsIE insts) -> find [] [] insts
796
797 --------------
798 find ms us [] = (ms, us)
799 find ms us (item@(ClsInst { is_tcs = mb_tcs, is_tvs = tpl_tvs
800 , is_tys = tpl_tys }) : rest)
801 | not (instIsVisible vis_mods item)
802 = find ms us rest -- See Note [Instance lookup and orphan instances]
803
804 -- Fast check for no match, uses the "rough match" fields
805 | instanceCantMatch rough_tcs mb_tcs
806 = find ms us rest
807
808 | Just subst <- tcMatchTys tpl_tys tys
809 = find ((item, map (lookupTyVar subst) tpl_tvs) : ms) us rest
810
811 -- Does not match, so next check whether the things unify
812 -- See Note [Overlapping instances]
813 -- Ignore ones that are incoherent: Note [Incoherent instances]
814 | isIncoherent item
815 = find ms us rest
816
817 | otherwise
818 = ASSERT2( tyCoVarsOfTypes tys `disjointVarSet` tpl_tv_set,
819 (ppr cls <+> ppr tys <+> ppr all_tvs) $$
820 (ppr tpl_tvs <+> ppr tpl_tys)
821 )
822 -- Unification will break badly if the variables overlap
823 -- They shouldn't because we allocate separate uniques for them
824 -- See Note [Template tyvars are fresh]
825 case tcUnifyTys instanceBindFun tpl_tys tys of
826 Just _ -> find ms (item:us) rest
827 Nothing -> find ms us rest
828 where
829 tpl_tv_set = mkVarSet tpl_tvs
830
831 ---------------
832 -- This is the common way to call this function.
833 lookupInstEnv :: Bool -- Check Safe Haskell overlap restrictions
834 -> InstEnvs -- External and home package inst-env
835 -> Class -> [Type] -- What we are looking for
836 -> ClsInstLookupResult
837 -- ^ See Note [Rules for instance lookup]
838 -- ^ See Note [Safe Haskell Overlapping Instances] in TcSimplify
839 -- ^ See Note [Safe Haskell Overlapping Instances Implementation] in TcSimplify
840 lookupInstEnv check_overlap_safe
841 (InstEnvs { ie_global = pkg_ie
842 , ie_local = home_ie
843 , ie_visible = vis_mods })
844 cls
845 tys
846 = -- pprTrace "lookupInstEnv" (ppr cls <+> ppr tys $$ ppr home_ie) $
847 (final_matches, final_unifs, unsafe_overlapped)
848 where
849 (home_matches, home_unifs) = lookupInstEnv' home_ie vis_mods cls tys
850 (pkg_matches, pkg_unifs) = lookupInstEnv' pkg_ie vis_mods cls tys
851 all_matches = home_matches ++ pkg_matches
852 all_unifs = home_unifs ++ pkg_unifs
853 final_matches = foldr insert_overlapping [] all_matches
854 -- Even if the unifs is non-empty (an error situation)
855 -- we still prune the matches, so that the error message isn't
856 -- misleading (complaining of multiple matches when some should be
857 -- overlapped away)
858
859 unsafe_overlapped
860 = case final_matches of
861 [match] -> check_safe match
862 _ -> []
863
864 -- If the selected match is incoherent, discard all unifiers
865 final_unifs = case final_matches of
866 (m:_) | isIncoherent (fst m) -> []
867 _ -> all_unifs
868
869 -- NOTE [Safe Haskell isSafeOverlap]
870 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
871 -- We restrict code compiled in 'Safe' mode from overriding code
872 -- compiled in any other mode. The rationale is that code compiled
873 -- in 'Safe' mode is code that is untrusted by the ghc user. So
874 -- we shouldn't let that code change the behaviour of code the
875 -- user didn't compile in 'Safe' mode since that's the code they
876 -- trust. So 'Safe' instances can only overlap instances from the
877 -- same module. A same instance origin policy for safe compiled
878 -- instances.
879 check_safe (inst,_)
880 = case check_overlap_safe && unsafeTopInstance inst of
881 -- make sure it only overlaps instances from the same module
882 True -> go [] all_matches
883 -- most specific is from a trusted location.
884 False -> []
885 where
886 go bad [] = bad
887 go bad (i@(x,_):unchecked) =
888 if inSameMod x || isOverlappable x
889 then go bad unchecked
890 else go (i:bad) unchecked
891
892 inSameMod b =
893 let na = getName $ getName inst
894 la = isInternalName na
895 nb = getName $ getName b
896 lb = isInternalName nb
897 in (la && lb) || (nameModule na == nameModule nb)
898
899 -- We consider the most specific instance unsafe when it both:
900 -- (1) Comes from a module compiled as `Safe`
901 -- (2) Is an orphan instance, OR, an instance for a MPTC
902 unsafeTopInstance inst = isSafeOverlap (is_flag inst) &&
903 (isOrphan (is_orphan inst) || classArity (is_cls inst) > 1)
904
905 ---------------
906 insert_overlapping :: InstMatch -> [InstMatch] -> [InstMatch]
907 -- ^ Add a new solution, knocking out strictly less specific ones
908 -- See Note [Rules for instance lookup]
909 insert_overlapping new_item [] = [new_item]
910 insert_overlapping new_item@(new_inst,_) (old_item@(old_inst,_) : old_items)
911 | new_beats_old -- New strictly overrides old
912 , not old_beats_new
913 , new_inst `can_override` old_inst
914 = insert_overlapping new_item old_items
915
916 | old_beats_new -- Old strictly overrides new
917 , not new_beats_old
918 , old_inst `can_override` new_inst
919 = old_item : old_items
920
921 -- Discard incoherent instances; see Note [Incoherent instances]
922 | isIncoherent old_inst -- Old is incoherent; discard it
923 = insert_overlapping new_item old_items
924 | isIncoherent new_inst -- New is incoherent; discard it
925 = old_item : old_items
926
927 -- Equal or incomparable, and neither is incoherent; keep both
928 | otherwise
929 = old_item : insert_overlapping new_item old_items
930 where
931
932 new_beats_old = new_inst `more_specific_than` old_inst
933 old_beats_new = old_inst `more_specific_than` new_inst
934
935 -- `instB` can be instantiated to match `instA`
936 -- or the two are equal
937 instA `more_specific_than` instB
938 = isJust (tcMatchTys (is_tys instB) (is_tys instA))
939
940 instA `can_override` instB
941 = isOverlapping instA || isOverlappable instB
942 -- Overlap permitted if either the more specific instance
943 -- is marked as overlapping, or the more general one is
944 -- marked as overlappable.
945 -- Latest change described in: #9242.
946 -- Previous change: #3877, Dec 10.
947
948 {-
949 Note [Incoherent instances]
950 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
951 For some classes, the choice of a particular instance does not matter, any one
952 is good. E.g. consider
953
954 class D a b where { opD :: a -> b -> String }
955 instance D Int b where ...
956 instance D a Int where ...
957
958 g (x::Int) = opD x x -- Wanted: D Int Int
959
960 For such classes this should work (without having to add an "instance D Int
961 Int", and using -XOverlappingInstances, which would then work). This is what
962 -XIncoherentInstances is for: Telling GHC "I don't care which instance you use;
963 if you can use one, use it."
964
965 Should this logic only work when *all* candidates have the incoherent flag, or
966 even when all but one have it? The right choice is the latter, which can be
967 justified by comparing the behaviour with how -XIncoherentInstances worked when
968 it was only about the unify-check (note [Overlapping instances]):
969
970 Example:
971 class C a b c where foo :: (a,b,c)
972 instance C [a] b Int
973 instance [incoherent] [Int] b c
974 instance [incoherent] C a Int c
975 Thanks to the incoherent flags,
976 [Wanted] C [a] b Int
977 works: Only instance one matches, the others just unify, but are marked
978 incoherent.
979
980 So I can write
981 (foo :: ([a],b,Int)) :: ([Int], Int, Int).
982 but if that works then I really want to be able to write
983 foo :: ([Int], Int, Int)
984 as well. Now all three instances from above match. None is more specific than
985 another, so none is ruled out by the normal overlapping rules. One of them is
986 not incoherent, but we still want this to compile. Hence the
987 "all-but-one-logic".
988
989 The implementation is in insert_overlapping, where we remove matching
990 incoherent instances as long as there are others.
991
992
993
994 ************************************************************************
995 * *
996 Binding decisions
997 * *
998 ************************************************************************
999 -}
1000
1001 instanceBindFun :: TyCoVar -> BindFlag
1002 instanceBindFun tv | isOverlappableTyVar tv = Skolem
1003 | otherwise = BindMe
1004 -- Note [Binding when looking up instances]
1005
1006 {-
1007 Note [Binding when looking up instances]
1008 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1009 When looking up in the instance environment, or family-instance environment,
1010 we are careful about multiple matches, as described above in
1011 Note [Overlapping instances]
1012
1013 The key_tys can contain skolem constants, and we can guarantee that those
1014 are never going to be instantiated to anything, so we should not involve
1015 them in the unification test. Example:
1016 class Foo a where { op :: a -> Int }
1017 instance Foo a => Foo [a] -- NB overlap
1018 instance Foo [Int] -- NB overlap
1019 data T = forall a. Foo a => MkT a
1020 f :: T -> Int
1021 f (MkT x) = op [x,x]
1022 The op [x,x] means we need (Foo [a]). Without the filterVarSet we'd
1023 complain, saying that the choice of instance depended on the instantiation
1024 of 'a'; but of course it isn't *going* to be instantiated.
1025
1026 We do this only for isOverlappableTyVar skolems. For example we reject
1027 g :: forall a => [a] -> Int
1028 g x = op x
1029 on the grounds that the correct instance depends on the instantiation of 'a'
1030 -}