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