Merge commit '5229c43ccf77bcbffeced01dccb27398d017fa34'
[ghc.git] / compiler / types / OptCoercion.hs
1 -- (c) The University of Glasgow 2006
2
3 {-# LANGUAGE CPP #-}
4
5 -- The default iteration limit is a bit too low for the definitions
6 -- in this module.
7 {-# OPTIONS_GHC -fmax-pmcheck-iterations=10000000 #-}
8
9 module OptCoercion ( optCoercion, checkAxInstCo ) where
10
11 #include "HsVersions.h"
12
13 import GhcPrelude
14
15 import DynFlags
16 import TyCoRep
17 import Coercion
18 import Type hiding( substTyVarBndr, substTy )
19 import TcType ( exactTyCoVarsOfType )
20 import TyCon
21 import CoAxiom
22 import VarSet
23 import VarEnv
24 import Outputable
25 import FamInstEnv ( flattenTys )
26 import Pair
27 import ListSetOps ( getNth )
28 import Util
29 import Unify
30 import InstEnv
31 import Control.Monad ( zipWithM )
32
33 {-
34 %************************************************************************
35 %* *
36 Optimising coercions
37 %* *
38 %************************************************************************
39
40 Note [Optimising coercion optimisation]
41 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
42 Looking up a coercion's role or kind is linear in the size of the
43 coercion. Thus, doing this repeatedly during the recursive descent
44 of coercion optimisation is disastrous. We must be careful to avoid
45 doing this if at all possible.
46
47 Because it is generally easy to know a coercion's components' roles
48 from the role of the outer coercion, we pass down the known role of
49 the input in the algorithm below. We also keep functions opt_co2
50 and opt_co3 separate from opt_co4, so that the former two do Phantom
51 checks that opt_co4 can avoid. This is a big win because Phantom coercions
52 rarely appear within non-phantom coercions -- only in some TyConAppCos
53 and some AxiomInstCos. We handle these cases specially by calling
54 opt_co2.
55
56 Note [Optimising InstCo]
57 ~~~~~~~~~~~~~~~~~~~~~~~~
58 When we have (InstCo (ForAllCo tv h g) g2), we want to optimise.
59
60 Let's look at the typing rules.
61
62 h : k1 ~ k2
63 tv:k1 |- g : t1 ~ t2
64 -----------------------------
65 ForAllCo tv h g : (all tv:k1.t1) ~ (all tv:k2.t2[tv |-> tv |> sym h])
66
67 g1 : (all tv:k1.t1') ~ (all tv:k2.t2')
68 g2 : s1 ~ s2
69 --------------------
70 InstCo g1 g2 : t1'[tv |-> s1] ~ t2'[tv |-> s2]
71
72 We thus want some coercion proving this:
73
74 (t1[tv |-> s1]) ~ (t2[tv |-> s2 |> sym h])
75
76 If we substitute the *type* tv for the *coercion*
77 (g2 `mkCoherenceRightCo` sym h) in g, we'll get this result exactly.
78 This is bizarre,
79 though, because we're substituting a type variable with a coercion. However,
80 this operation already exists: it's called *lifting*, and defined in Coercion.
81 We just need to enhance the lifting operation to be able to deal with
82 an ambient substitution, which is why a LiftingContext stores a TCvSubst.
83
84 -}
85
86 optCoercion :: TCvSubst -> Coercion -> NormalCo
87 -- ^ optCoercion applies a substitution to a coercion,
88 -- *and* optimises it to reduce its size
89 optCoercion env co
90 | hasNoOptCoercion unsafeGlobalDynFlags = substCo env co
91 | debugIsOn
92 = let out_co = opt_co1 lc False co
93 (Pair in_ty1 in_ty2, in_role) = coercionKindRole co
94 (Pair out_ty1 out_ty2, out_role) = coercionKindRole out_co
95 in
96 ASSERT2( substTyUnchecked env in_ty1 `eqType` out_ty1 &&
97 substTyUnchecked env in_ty2 `eqType` out_ty2 &&
98 in_role == out_role
99 , text "optCoercion changed types!"
100 $$ hang (text "in_co:") 2 (ppr co)
101 $$ hang (text "in_ty1:") 2 (ppr in_ty1)
102 $$ hang (text "in_ty2:") 2 (ppr in_ty2)
103 $$ hang (text "out_co:") 2 (ppr out_co)
104 $$ hang (text "out_ty1:") 2 (ppr out_ty1)
105 $$ hang (text "out_ty2:") 2 (ppr out_ty2)
106 $$ hang (text "subst:") 2 (ppr env) )
107 out_co
108
109 | otherwise = opt_co1 lc False co
110 where
111 lc = mkSubstLiftingContext env
112
113 type NormalCo = Coercion
114 -- Invariants:
115 -- * The substitution has been fully applied
116 -- * For trans coercions (co1 `trans` co2)
117 -- co1 is not a trans, and neither co1 nor co2 is identity
118
119 type NormalNonIdCo = NormalCo -- Extra invariant: not the identity
120
121 -- | Do we apply a @sym@ to the result?
122 type SymFlag = Bool
123
124 -- | Do we force the result to be representational?
125 type ReprFlag = Bool
126
127 -- | Optimize a coercion, making no assumptions. All coercions in
128 -- the lifting context are already optimized (and sym'd if nec'y)
129 opt_co1 :: LiftingContext
130 -> SymFlag
131 -> Coercion -> NormalCo
132 opt_co1 env sym co = opt_co2 env sym (coercionRole co) co
133
134 -- See Note [Optimising coercion optimisation]
135 -- | Optimize a coercion, knowing the coercion's role. No other assumptions.
136 opt_co2 :: LiftingContext
137 -> SymFlag
138 -> Role -- ^ The role of the input coercion
139 -> Coercion -> NormalCo
140 opt_co2 env sym Phantom co = opt_phantom env sym co
141 opt_co2 env sym r co = opt_co3 env sym Nothing r co
142
143 -- See Note [Optimising coercion optimisation]
144 -- | Optimize a coercion, knowing the coercion's non-Phantom role.
145 opt_co3 :: LiftingContext -> SymFlag -> Maybe Role -> Role -> Coercion -> NormalCo
146 opt_co3 env sym (Just Phantom) _ co = opt_phantom env sym co
147 opt_co3 env sym (Just Representational) r co = opt_co4_wrap env sym True r co
148 -- if mrole is Just Nominal, that can't be a downgrade, so we can ignore
149 opt_co3 env sym _ r co = opt_co4_wrap env sym False r co
150
151 -- See Note [Optimising coercion optimisation]
152 -- | Optimize a non-phantom coercion.
153 opt_co4, opt_co4_wrap :: LiftingContext -> SymFlag -> ReprFlag -> Role -> Coercion -> NormalCo
154
155 opt_co4_wrap = opt_co4
156 {-
157 opt_co4_wrap env sym rep r co
158 = pprTrace "opt_co4_wrap {"
159 ( vcat [ text "Sym:" <+> ppr sym
160 , text "Rep:" <+> ppr rep
161 , text "Role:" <+> ppr r
162 , text "Co:" <+> ppr co ]) $
163 ASSERT( r == coercionRole co )
164 let result = opt_co4 env sym rep r co in
165 pprTrace "opt_co4_wrap }" (ppr co $$ text "---" $$ ppr result) $
166 result
167 -}
168
169 opt_co4 env _ rep r (Refl _r ty)
170 = ASSERT2( r == _r, text "Expected role:" <+> ppr r $$
171 text "Found role:" <+> ppr _r $$
172 text "Type:" <+> ppr ty )
173 liftCoSubst (chooseRole rep r) env ty
174
175 opt_co4 env sym rep r (SymCo co) = opt_co4_wrap env (not sym) rep r co
176 -- surprisingly, we don't have to do anything to the env here. This is
177 -- because any "lifting" substitutions in the env are tied to ForAllCos,
178 -- which treat their left and right sides differently. We don't want to
179 -- exchange them.
180
181 opt_co4 env sym rep r g@(TyConAppCo _r tc cos)
182 = ASSERT( r == _r )
183 case (rep, r) of
184 (True, Nominal) ->
185 mkTyConAppCo Representational tc
186 (zipWith3 (opt_co3 env sym)
187 (map Just (tyConRolesRepresentational tc))
188 (repeat Nominal)
189 cos)
190 (False, Nominal) ->
191 mkTyConAppCo Nominal tc (map (opt_co4_wrap env sym False Nominal) cos)
192 (_, Representational) ->
193 -- must use opt_co2 here, because some roles may be P
194 -- See Note [Optimising coercion optimisation]
195 mkTyConAppCo r tc (zipWith (opt_co2 env sym)
196 (tyConRolesRepresentational tc) -- the current roles
197 cos)
198 (_, Phantom) -> pprPanic "opt_co4 sees a phantom!" (ppr g)
199
200 opt_co4 env sym rep r (AppCo co1 co2)
201 = mkAppCo (opt_co4_wrap env sym rep r co1)
202 (opt_co4_wrap env sym False Nominal co2)
203
204 opt_co4 env sym rep r (ForAllCo tv k_co co)
205 = case optForAllCoBndr env sym tv k_co of
206 (env', tv', k_co') -> mkForAllCo tv' k_co' $
207 opt_co4_wrap env' sym rep r co
208 -- Use the "mk" functions to check for nested Refls
209
210 opt_co4 env sym rep r (FunCo _r co1 co2)
211 = ASSERT( r == _r )
212 if rep
213 then mkFunCo Representational co1' co2'
214 else mkFunCo r co1' co2'
215 where
216 co1' = opt_co4_wrap env sym rep r co1
217 co2' = opt_co4_wrap env sym rep r co2
218
219 opt_co4 env sym rep r (CoVarCo cv)
220 | Just co <- lookupCoVar (lcTCvSubst env) cv
221 = opt_co4_wrap (zapLiftingContext env) sym rep r co
222
223 | ty1 `eqType` ty2 -- See Note [Optimise CoVarCo to Refl]
224 = Refl (chooseRole rep r) ty1
225
226 | otherwise
227 = ASSERT( isCoVar cv1 )
228 wrapRole rep r $ wrapSym sym $
229 CoVarCo cv1
230
231 where
232 Pair ty1 ty2 = coVarTypes cv1
233
234 cv1 = case lookupInScope (lcInScopeSet env) cv of
235 Just cv1 -> cv1
236 Nothing -> WARN( True, text "opt_co: not in scope:"
237 <+> ppr cv $$ ppr env)
238 cv
239 -- cv1 might have a substituted kind!
240
241
242 opt_co4 env sym rep r (AxiomInstCo con ind cos)
243 -- Do *not* push sym inside top-level axioms
244 -- e.g. if g is a top-level axiom
245 -- g a : f a ~ a
246 -- then (sym (g ty)) /= g (sym ty) !!
247 = ASSERT( r == coAxiomRole con )
248 wrapRole rep (coAxiomRole con) $
249 wrapSym sym $
250 -- some sub-cos might be P: use opt_co2
251 -- See Note [Optimising coercion optimisation]
252 AxiomInstCo con ind (zipWith (opt_co2 env False)
253 (coAxBranchRoles (coAxiomNthBranch con ind))
254 cos)
255 -- Note that the_co does *not* have sym pushed into it
256
257 opt_co4 env sym rep r (UnivCo prov _r t1 t2)
258 = ASSERT( r == _r )
259 opt_univ env sym prov (chooseRole rep r) t1 t2
260
261 opt_co4 env sym rep r (TransCo co1 co2)
262 -- sym (g `o` h) = sym h `o` sym g
263 | sym = opt_trans in_scope co2' co1'
264 | otherwise = opt_trans in_scope co1' co2'
265 where
266 co1' = opt_co4_wrap env sym rep r co1
267 co2' = opt_co4_wrap env sym rep r co2
268 in_scope = lcInScopeSet env
269
270
271 opt_co4 env sym rep r co@(NthCo {}) = opt_nth_co env sym rep r co
272
273 opt_co4 env sym rep r (LRCo lr co)
274 | Just pr_co <- splitAppCo_maybe co
275 = ASSERT( r == Nominal )
276 opt_co4_wrap env sym rep Nominal (pick_lr lr pr_co)
277 | Just pr_co <- splitAppCo_maybe co'
278 = ASSERT( r == Nominal )
279 if rep
280 then opt_co4_wrap (zapLiftingContext env) False True Nominal (pick_lr lr pr_co)
281 else pick_lr lr pr_co
282 | otherwise
283 = wrapRole rep Nominal $ LRCo lr co'
284 where
285 co' = opt_co4_wrap env sym False Nominal co
286
287 pick_lr CLeft (l, _) = l
288 pick_lr CRight (_, r) = r
289
290 -- See Note [Optimising InstCo]
291 opt_co4 env sym rep r (InstCo co1 arg)
292 -- forall over type...
293 | Just (tv, kind_co, co_body) <- splitForAllCo_maybe co1
294 = opt_co4_wrap (extendLiftingContext env tv
295 (arg' `mkCoherenceRightCo` mkSymCo kind_co))
296 sym rep r co_body
297
298 -- See if it is a forall after optimization
299 -- If so, do an inefficient one-variable substitution, then re-optimize
300
301 -- forall over type...
302 | Just (tv', kind_co', co_body') <- splitForAllCo_maybe co1'
303 = opt_co4_wrap (extendLiftingContext (zapLiftingContext env) tv'
304 (arg' `mkCoherenceRightCo` mkSymCo kind_co'))
305 False False r' co_body'
306
307 | otherwise = InstCo co1' arg'
308 where
309 co1' = opt_co4_wrap env sym rep r co1
310 r' = chooseRole rep r
311 arg' = opt_co4_wrap env sym False Nominal arg
312
313 opt_co4 env sym rep r (CoherenceCo co1 co2)
314 | TransCo col1 cor1 <- co1
315 = opt_co4_wrap env sym rep r (mkTransCo (mkCoherenceCo col1 co2) cor1)
316
317 | TransCo col1' cor1' <- co1'
318 = if sym then opt_trans in_scope col1'
319 (optCoercion (zapTCvSubst (lcTCvSubst env))
320 (mkCoherenceRightCo cor1' co2'))
321 else opt_trans in_scope (mkCoherenceCo col1' co2') cor1'
322
323 | otherwise
324 = wrapSym sym $ mkCoherenceCo (opt_co4_wrap env False rep r co1) co2'
325 where co1' = opt_co4_wrap env sym rep r co1
326 co2' = opt_co4_wrap env False False Nominal co2
327 in_scope = lcInScopeSet env
328
329 opt_co4 env sym _rep r (KindCo co)
330 = ASSERT( r == Nominal )
331 let kco' = promoteCoercion co in
332 case kco' of
333 KindCo co' -> promoteCoercion (opt_co1 env sym co')
334 _ -> opt_co4_wrap env sym False Nominal kco'
335 -- This might be able to be optimized more to do the promotion
336 -- and substitution/optimization at the same time
337
338 opt_co4 env sym _ r (SubCo co)
339 = ASSERT( r == Representational )
340 opt_co4_wrap env sym True Nominal co
341
342 -- This could perhaps be optimized more.
343 opt_co4 env sym rep r (AxiomRuleCo co cs)
344 = ASSERT( r == coaxrRole co )
345 wrapRole rep r $
346 wrapSym sym $
347 AxiomRuleCo co (zipWith (opt_co2 env False) (coaxrAsmpRoles co) cs)
348
349 {- Note [Optimise CoVarCo to Refl]
350 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
351 If we have (c :: t~t) we can optimise it to Refl. That increases the
352 chances of floating the Refl upwards; e.g. Maybe c --> Refl (Maybe t)
353
354 We do so here in optCoercion, not in mkCoVarCo; see Note [mkCoVarCo]
355 in Coercion.
356 -}
357
358 -------------
359 -- | Optimize a phantom coercion. The input coercion may not necessarily
360 -- be a phantom, but the output sure will be.
361 opt_phantom :: LiftingContext -> SymFlag -> Coercion -> NormalCo
362 opt_phantom env sym co
363 = opt_univ env sym (PhantomProv (mkKindCo co)) Phantom ty1 ty2
364 where
365 Pair ty1 ty2 = coercionKind co
366
367 {- Note [Differing kinds]
368 ~~~~~~~~~~~~~~~~~~~~~~
369 The two types may not have the same kind (although that would be very unusual).
370 But even if they have the same kind, and the same type constructor, the number
371 of arguments in a `CoTyConApp` can differ. Consider
372
373 Any :: forall k. k
374
375 Any * Int :: *
376 Any (*->*) Maybe Int :: *
377
378 Hence the need to compare argument lengths; see Trac #13658
379 -}
380
381 opt_univ :: LiftingContext -> SymFlag -> UnivCoProvenance -> Role
382 -> Type -> Type -> Coercion
383 opt_univ env sym (PhantomProv h) _r ty1 ty2
384 | sym = mkPhantomCo h' ty2' ty1'
385 | otherwise = mkPhantomCo h' ty1' ty2'
386 where
387 h' = opt_co4 env sym False Nominal h
388 ty1' = substTy (lcSubstLeft env) ty1
389 ty2' = substTy (lcSubstRight env) ty2
390
391 opt_univ env sym prov role oty1 oty2
392 | Just (tc1, tys1) <- splitTyConApp_maybe oty1
393 , Just (tc2, tys2) <- splitTyConApp_maybe oty2
394 , tc1 == tc2
395 , equalLength tys1 tys2 -- see Note [Differing kinds]
396 -- NB: prov must not be the two interesting ones (ProofIrrel & Phantom);
397 -- Phantom is already taken care of, and ProofIrrel doesn't relate tyconapps
398 = let roles = tyConRolesX role tc1
399 arg_cos = zipWith3 (mkUnivCo prov) roles tys1 tys2
400 arg_cos' = zipWith (opt_co4 env sym False) roles arg_cos
401 in
402 mkTyConAppCo role tc1 arg_cos'
403
404 -- can't optimize the AppTy case because we can't build the kind coercions.
405
406 | Just (tv1, ty1) <- splitForAllTy_maybe oty1
407 , Just (tv2, ty2) <- splitForAllTy_maybe oty2
408 -- NB: prov isn't interesting here either
409 = let k1 = tyVarKind tv1
410 k2 = tyVarKind tv2
411 eta = mkUnivCo prov Nominal k1 k2
412 -- eta gets opt'ed soon, but not yet.
413 ty2' = substTyWith [tv2] [TyVarTy tv1 `mkCastTy` eta] ty2
414
415 (env', tv1', eta') = optForAllCoBndr env sym tv1 eta
416 in
417 mkForAllCo tv1' eta' (opt_univ env' sym prov role ty1 ty2')
418
419 | otherwise
420 = let ty1 = substTyUnchecked (lcSubstLeft env) oty1
421 ty2 = substTyUnchecked (lcSubstRight env) oty2
422 (a, b) | sym = (ty2, ty1)
423 | otherwise = (ty1, ty2)
424 in
425 mkUnivCo prov' role a b
426
427 where
428 prov' = case prov of
429 UnsafeCoerceProv -> prov
430 PhantomProv kco -> PhantomProv $ opt_co4_wrap env sym False Nominal kco
431 ProofIrrelProv kco -> ProofIrrelProv $ opt_co4_wrap env sym False Nominal kco
432 PluginProv _ -> prov
433 HoleProv h -> pprPanic "opt_univ fell into a hole" (ppr h)
434
435
436 -------------
437 -- NthCo must be handled separately, because it's the one case where we can't
438 -- tell quickly what the component coercion's role is from the containing
439 -- coercion. To avoid repeated coercionRole calls as opt_co1 calls opt_co2,
440 -- we just look for nested NthCo's, which can happen in practice.
441 opt_nth_co :: LiftingContext -> SymFlag -> ReprFlag -> Role -> Coercion -> NormalCo
442 opt_nth_co env sym rep r = go []
443 where
444 go ns (NthCo n co) = go (n:ns) co
445 -- previous versions checked if the tycon is decomposable. This
446 -- is redundant, because a non-decomposable tycon under an NthCo
447 -- is entirely bogus. See docs/core-spec/core-spec.pdf.
448 go ns co
449 = opt_nths ns co
450
451 -- try to resolve 1 Nth
452 push_nth n (Refl r1 ty)
453 | Just (tc, args) <- splitTyConApp_maybe ty
454 = Just (Refl (nthRole r1 tc n) (args `getNth` n))
455 | n == 0
456 , Just (tv, _) <- splitForAllTy_maybe ty
457 = Just (Refl Nominal (tyVarKind tv))
458 push_nth n (TyConAppCo _ _ cos)
459 = Just (cos `getNth` n)
460 push_nth 0 (ForAllCo _ eta _)
461 = Just eta
462 push_nth _ _ = Nothing
463
464 -- input coercion is *not* yet sym'd or opt'd
465 opt_nths [] co = opt_co4_wrap env sym rep r co
466 opt_nths (n:ns) co
467 | Just co' <- push_nth n co
468 = opt_nths ns co'
469
470 -- here, the co isn't a TyConAppCo, so we opt it, hoping to get
471 -- a TyConAppCo as output. We don't know the role, so we use
472 -- opt_co1. This is slightly annoying, because opt_co1 will call
473 -- coercionRole, but as long as we don't have a long chain of
474 -- NthCo's interspersed with some other coercion former, we should
475 -- be OK.
476 opt_nths ns co = opt_nths' ns (opt_co1 env sym co)
477
478 -- input coercion *is* sym'd and opt'd
479 opt_nths' [] co
480 = if rep && (r == Nominal)
481 -- propagate the SubCo:
482 then opt_co4_wrap (zapLiftingContext env) False True r co
483 else co
484 opt_nths' (n:ns) co
485 | Just co' <- push_nth n co
486 = opt_nths' ns co'
487 opt_nths' ns co = wrapRole rep r (mk_nths ns co)
488
489 mk_nths [] co = co
490 mk_nths (n:ns) co = mk_nths ns (mkNthCo n co)
491
492 -------------
493 opt_transList :: InScopeSet -> [NormalCo] -> [NormalCo] -> [NormalCo]
494 opt_transList is = zipWith (opt_trans is)
495
496 opt_trans :: InScopeSet -> NormalCo -> NormalCo -> NormalCo
497 opt_trans is co1 co2
498 | isReflCo co1 = co2
499 | otherwise = opt_trans1 is co1 co2
500
501 opt_trans1 :: InScopeSet -> NormalNonIdCo -> NormalCo -> NormalCo
502 -- First arg is not the identity
503 opt_trans1 is co1 co2
504 | isReflCo co2 = co1
505 | otherwise = opt_trans2 is co1 co2
506
507 opt_trans2 :: InScopeSet -> NormalNonIdCo -> NormalNonIdCo -> NormalCo
508 -- Neither arg is the identity
509 opt_trans2 is (TransCo co1a co1b) co2
510 -- Don't know whether the sub-coercions are the identity
511 = opt_trans is co1a (opt_trans is co1b co2)
512
513 opt_trans2 is co1 co2
514 | Just co <- opt_trans_rule is co1 co2
515 = co
516
517 opt_trans2 is co1 (TransCo co2a co2b)
518 | Just co1_2a <- opt_trans_rule is co1 co2a
519 = if isReflCo co1_2a
520 then co2b
521 else opt_trans1 is co1_2a co2b
522
523 opt_trans2 _ co1 co2
524 = mkTransCo co1 co2
525
526 ------
527 -- Optimize coercions with a top-level use of transitivity.
528 opt_trans_rule :: InScopeSet -> NormalNonIdCo -> NormalNonIdCo -> Maybe NormalCo
529
530 -- Push transitivity through matching destructors
531 opt_trans_rule is in_co1@(NthCo d1 co1) in_co2@(NthCo d2 co2)
532 | d1 == d2
533 , co1 `compatible_co` co2
534 = fireTransRule "PushNth" in_co1 in_co2 $
535 mkNthCo d1 (opt_trans is co1 co2)
536
537 opt_trans_rule is in_co1@(LRCo d1 co1) in_co2@(LRCo d2 co2)
538 | d1 == d2
539 , co1 `compatible_co` co2
540 = fireTransRule "PushLR" in_co1 in_co2 $
541 mkLRCo d1 (opt_trans is co1 co2)
542
543 -- Push transitivity inside instantiation
544 opt_trans_rule is in_co1@(InstCo co1 ty1) in_co2@(InstCo co2 ty2)
545 | ty1 `eqCoercion` ty2
546 , co1 `compatible_co` co2
547 = fireTransRule "TrPushInst" in_co1 in_co2 $
548 mkInstCo (opt_trans is co1 co2) ty1
549
550 opt_trans_rule is in_co1@(UnivCo p1 r1 tyl1 _tyr1)
551 in_co2@(UnivCo p2 r2 _tyl2 tyr2)
552 | Just prov' <- opt_trans_prov p1 p2
553 = ASSERT( r1 == r2 )
554 fireTransRule "UnivCo" in_co1 in_co2 $
555 mkUnivCo prov' r1 tyl1 tyr2
556 where
557 -- if the provenances are different, opt'ing will be very confusing
558 opt_trans_prov UnsafeCoerceProv UnsafeCoerceProv = Just UnsafeCoerceProv
559 opt_trans_prov (PhantomProv kco1) (PhantomProv kco2)
560 = Just $ PhantomProv $ opt_trans is kco1 kco2
561 opt_trans_prov (ProofIrrelProv kco1) (ProofIrrelProv kco2)
562 = Just $ ProofIrrelProv $ opt_trans is kco1 kco2
563 opt_trans_prov (PluginProv str1) (PluginProv str2) | str1 == str2 = Just p1
564 opt_trans_prov _ _ = Nothing
565
566 -- Push transitivity down through matching top-level constructors.
567 opt_trans_rule is in_co1@(TyConAppCo r1 tc1 cos1) in_co2@(TyConAppCo r2 tc2 cos2)
568 | tc1 == tc2
569 = ASSERT( r1 == r2 )
570 fireTransRule "PushTyConApp" in_co1 in_co2 $
571 mkTyConAppCo r1 tc1 (opt_transList is cos1 cos2)
572
573 opt_trans_rule is in_co1@(FunCo r1 co1a co1b) in_co2@(FunCo r2 co2a co2b)
574 = ASSERT( r1 == r2 ) -- Just like the TyConAppCo/TyConAppCo case
575 fireTransRule "PushFun" in_co1 in_co2 $
576 mkFunCo r1 (opt_trans is co1a co2a) (opt_trans is co1b co2b)
577
578 opt_trans_rule is in_co1@(AppCo co1a co1b) in_co2@(AppCo co2a co2b)
579 = fireTransRule "TrPushApp" in_co1 in_co2 $
580 mkAppCo (opt_trans is co1a co2a)
581 (opt_trans is co1b co2b)
582
583 -- Eta rules
584 opt_trans_rule is co1@(TyConAppCo r tc cos1) co2
585 | Just cos2 <- etaTyConAppCo_maybe tc co2
586 = ASSERT( cos1 `equalLength` cos2 )
587 fireTransRule "EtaCompL" co1 co2 $
588 mkTyConAppCo r tc (opt_transList is cos1 cos2)
589
590 opt_trans_rule is co1 co2@(TyConAppCo r tc cos2)
591 | Just cos1 <- etaTyConAppCo_maybe tc co1
592 = ASSERT( cos1 `equalLength` cos2 )
593 fireTransRule "EtaCompR" co1 co2 $
594 mkTyConAppCo r tc (opt_transList is cos1 cos2)
595
596 opt_trans_rule is co1@(AppCo co1a co1b) co2
597 | Just (co2a,co2b) <- etaAppCo_maybe co2
598 = fireTransRule "EtaAppL" co1 co2 $
599 mkAppCo (opt_trans is co1a co2a)
600 (opt_trans is co1b co2b)
601
602 opt_trans_rule is co1 co2@(AppCo co2a co2b)
603 | Just (co1a,co1b) <- etaAppCo_maybe co1
604 = fireTransRule "EtaAppR" co1 co2 $
605 mkAppCo (opt_trans is co1a co2a)
606 (opt_trans is co1b co2b)
607
608 -- Push transitivity inside forall
609 opt_trans_rule is co1 co2
610 | ForAllCo tv1 eta1 r1 <- co1
611 , Just (tv2,eta2,r2) <- etaForAllCo_maybe co2
612 = push_trans tv1 eta1 r1 tv2 eta2 r2
613
614 | ForAllCo tv2 eta2 r2 <- co2
615 , Just (tv1,eta1,r1) <- etaForAllCo_maybe co1
616 = push_trans tv1 eta1 r1 tv2 eta2 r2
617
618 where
619 push_trans tv1 eta1 r1 tv2 eta2 r2
620 = fireTransRule "EtaAllTy" co1 co2 $
621 mkForAllCo tv1 (opt_trans is eta1 eta2) (opt_trans is' r1 r2')
622 where
623 is' = is `extendInScopeSet` tv1
624 r2' = substCoWithUnchecked [tv2] [TyVarTy tv1] r2
625
626 -- Push transitivity inside axioms
627 opt_trans_rule is co1 co2
628
629 -- See Note [Why call checkAxInstCo during optimisation]
630 -- TrPushSymAxR
631 | Just (sym, con, ind, cos1) <- co1_is_axiom_maybe
632 , True <- sym
633 , Just cos2 <- matchAxiom sym con ind co2
634 , let newAxInst = AxiomInstCo con ind (opt_transList is (map mkSymCo cos2) cos1)
635 , Nothing <- checkAxInstCo newAxInst
636 = fireTransRule "TrPushSymAxR" co1 co2 $ SymCo newAxInst
637
638 -- TrPushAxR
639 | Just (sym, con, ind, cos1) <- co1_is_axiom_maybe
640 , False <- sym
641 , Just cos2 <- matchAxiom sym con ind co2
642 , let newAxInst = AxiomInstCo con ind (opt_transList is cos1 cos2)
643 , Nothing <- checkAxInstCo newAxInst
644 = fireTransRule "TrPushAxR" co1 co2 newAxInst
645
646 -- TrPushSymAxL
647 | Just (sym, con, ind, cos2) <- co2_is_axiom_maybe
648 , True <- sym
649 , Just cos1 <- matchAxiom (not sym) con ind co1
650 , let newAxInst = AxiomInstCo con ind (opt_transList is cos2 (map mkSymCo cos1))
651 , Nothing <- checkAxInstCo newAxInst
652 = fireTransRule "TrPushSymAxL" co1 co2 $ SymCo newAxInst
653
654 -- TrPushAxL
655 | Just (sym, con, ind, cos2) <- co2_is_axiom_maybe
656 , False <- sym
657 , Just cos1 <- matchAxiom (not sym) con ind co1
658 , let newAxInst = AxiomInstCo con ind (opt_transList is cos1 cos2)
659 , Nothing <- checkAxInstCo newAxInst
660 = fireTransRule "TrPushAxL" co1 co2 newAxInst
661
662 -- TrPushAxSym/TrPushSymAx
663 | Just (sym1, con1, ind1, cos1) <- co1_is_axiom_maybe
664 , Just (sym2, con2, ind2, cos2) <- co2_is_axiom_maybe
665 , con1 == con2
666 , ind1 == ind2
667 , sym1 == not sym2
668 , let branch = coAxiomNthBranch con1 ind1
669 qtvs = coAxBranchTyVars branch ++ coAxBranchCoVars branch
670 lhs = coAxNthLHS con1 ind1
671 rhs = coAxBranchRHS branch
672 pivot_tvs = exactTyCoVarsOfType (if sym2 then rhs else lhs)
673 , all (`elemVarSet` pivot_tvs) qtvs
674 = fireTransRule "TrPushAxSym" co1 co2 $
675 if sym2
676 -- TrPushAxSym
677 then liftCoSubstWith role qtvs (opt_transList is cos1 (map mkSymCo cos2)) lhs
678 -- TrPushSymAx
679 else liftCoSubstWith role qtvs (opt_transList is (map mkSymCo cos1) cos2) rhs
680 where
681 co1_is_axiom_maybe = isAxiom_maybe co1
682 co2_is_axiom_maybe = isAxiom_maybe co2
683 role = coercionRole co1 -- should be the same as coercionRole co2!
684
685 opt_trans_rule is co1 co2
686 | Just (lco, lh) <- isCohRight_maybe co1
687 , Just (rco, rh) <- isCohLeft_maybe co2
688 , (coercionType lh) `eqType` (coercionType rh)
689 = opt_trans_rule is lco rco
690
691 opt_trans_rule _ co1 co2 -- Identity rule
692 | (Pair ty1 _, r) <- coercionKindRole co1
693 , Pair _ ty2 <- coercionKind co2
694 , ty1 `eqType` ty2
695 = fireTransRule "RedTypeDirRefl" co1 co2 $
696 Refl r ty2
697
698 opt_trans_rule _ _ _ = Nothing
699
700 fireTransRule :: String -> Coercion -> Coercion -> Coercion -> Maybe Coercion
701 fireTransRule _rule _co1 _co2 res
702 = -- pprTrace ("Trans rule fired: " ++ _rule) (vcat [ppr _co1, ppr _co2, ppr res]) $
703 Just res
704
705 {-
706 Note [Conflict checking with AxiomInstCo]
707 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
708 Consider the following type family and axiom:
709
710 type family Equal (a :: k) (b :: k) :: Bool
711 type instance where
712 Equal a a = True
713 Equal a b = False
714 --
715 Equal :: forall k::*. k -> k -> Bool
716 axEqual :: { forall k::*. forall a::k. Equal k a a ~ True
717 ; forall k::*. forall a::k. forall b::k. Equal k a b ~ False }
718
719 We wish to disallow (axEqual[1] <*> <Int> <Int). (Recall that the index is
720 0-based, so this is the second branch of the axiom.) The problem is that, on
721 the surface, it seems that (axEqual[1] <*> <Int> <Int>) :: (Equal * Int Int ~
722 False) and that all is OK. But, all is not OK: we want to use the first branch
723 of the axiom in this case, not the second. The problem is that the parameters
724 of the first branch can unify with the supplied coercions, thus meaning that
725 the first branch should be taken. See also Note [Apartness] in
726 types/FamInstEnv.hs.
727
728 Note [Why call checkAxInstCo during optimisation]
729 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
730 It is possible that otherwise-good-looking optimisations meet with disaster
731 in the presence of axioms with multiple equations. Consider
732
733 type family Equal (a :: *) (b :: *) :: Bool where
734 Equal a a = True
735 Equal a b = False
736 type family Id (a :: *) :: * where
737 Id a = a
738
739 axEq :: { [a::*]. Equal a a ~ True
740 ; [a::*, b::*]. Equal a b ~ False }
741 axId :: [a::*]. Id a ~ a
742
743 co1 = Equal (axId[0] Int) (axId[0] Bool)
744 :: Equal (Id Int) (Id Bool) ~ Equal Int Bool
745 co2 = axEq[1] <Int> <Bool>
746 :: Equal Int Bool ~ False
747
748 We wish to optimise (co1 ; co2). We end up in rule TrPushAxL, noting that
749 co2 is an axiom and that matchAxiom succeeds when looking at co1. But, what
750 happens when we push the coercions inside? We get
751
752 co3 = axEq[1] (axId[0] Int) (axId[0] Bool)
753 :: Equal (Id Int) (Id Bool) ~ False
754
755 which is bogus! This is because the type system isn't smart enough to know
756 that (Id Int) and (Id Bool) are Surely Apart, as they're headed by type
757 families. At the time of writing, I (Richard Eisenberg) couldn't think of
758 a way of detecting this any more efficient than just building the optimised
759 coercion and checking.
760 -}
761
762 -- | Check to make sure that an AxInstCo is internally consistent.
763 -- Returns the conflicting branch, if it exists
764 -- See Note [Conflict checking with AxiomInstCo]
765 checkAxInstCo :: Coercion -> Maybe CoAxBranch
766 -- defined here to avoid dependencies in Coercion
767 -- If you edit this function, you may need to update the GHC formalism
768 -- See Note [GHC Formalism] in CoreLint
769 checkAxInstCo (AxiomInstCo ax ind cos)
770 = let branch = coAxiomNthBranch ax ind
771 tvs = coAxBranchTyVars branch
772 cvs = coAxBranchCoVars branch
773 incomps = coAxBranchIncomps branch
774 (tys, cotys) = splitAtList tvs (map (pFst . coercionKind) cos)
775 co_args = map stripCoercionTy cotys
776 subst = zipTvSubst tvs tys `composeTCvSubst`
777 zipCvSubst cvs co_args
778 target = Type.substTys subst (coAxBranchLHS branch)
779 in_scope = mkInScopeSet $
780 unionVarSets (map (tyCoVarsOfTypes . coAxBranchLHS) incomps)
781 flattened_target = flattenTys in_scope target in
782 check_no_conflict flattened_target incomps
783 where
784 check_no_conflict :: [Type] -> [CoAxBranch] -> Maybe CoAxBranch
785 check_no_conflict _ [] = Nothing
786 check_no_conflict flat (b@CoAxBranch { cab_lhs = lhs_incomp } : rest)
787 -- See Note [Apartness] in FamInstEnv
788 | SurelyApart <- tcUnifyTysFG instanceBindFun flat lhs_incomp
789 = check_no_conflict flat rest
790 | otherwise
791 = Just b
792 checkAxInstCo _ = Nothing
793
794
795 -----------
796 wrapSym :: SymFlag -> Coercion -> Coercion
797 wrapSym sym co | sym = mkSymCo co
798 | otherwise = co
799
800 -- | Conditionally set a role to be representational
801 wrapRole :: ReprFlag
802 -> Role -- ^ current role
803 -> Coercion -> Coercion
804 wrapRole False _ = id
805 wrapRole True current = downgradeRole Representational current
806
807 -- | If we require a representational role, return that. Otherwise,
808 -- return the "default" role provided.
809 chooseRole :: ReprFlag
810 -> Role -- ^ "default" role
811 -> Role
812 chooseRole True _ = Representational
813 chooseRole _ r = r
814
815 -----------
816 isAxiom_maybe :: Coercion -> Maybe (Bool, CoAxiom Branched, Int, [Coercion])
817 isAxiom_maybe (SymCo co)
818 | Just (sym, con, ind, cos) <- isAxiom_maybe co
819 = Just (not sym, con, ind, cos)
820 isAxiom_maybe (AxiomInstCo con ind cos)
821 = Just (False, con, ind, cos)
822 isAxiom_maybe _ = Nothing
823
824 matchAxiom :: Bool -- True = match LHS, False = match RHS
825 -> CoAxiom br -> Int -> Coercion -> Maybe [Coercion]
826 matchAxiom sym ax@(CoAxiom { co_ax_tc = tc }) ind co
827 | CoAxBranch { cab_tvs = qtvs
828 , cab_cvs = [] -- can't infer these, so fail if there are any
829 , cab_roles = roles
830 , cab_lhs = lhs
831 , cab_rhs = rhs } <- coAxiomNthBranch ax ind
832 , Just subst <- liftCoMatch (mkVarSet qtvs)
833 (if sym then (mkTyConApp tc lhs) else rhs)
834 co
835 , all (`isMappedByLC` subst) qtvs
836 = zipWithM (liftCoSubstTyVar subst) roles qtvs
837
838 | otherwise
839 = Nothing
840
841 -------------
842 -- destruct a CoherenceCo
843 isCohLeft_maybe :: Coercion -> Maybe (Coercion, Coercion)
844 isCohLeft_maybe (CoherenceCo co1 co2) = Just (co1, co2)
845 isCohLeft_maybe _ = Nothing
846
847 -- destruct a (sym (co1 |> co2)).
848 -- if isCohRight_maybe co = Just (co1, co2), then (sym co1) `mkCohRightCo` co2 = co
849 isCohRight_maybe :: Coercion -> Maybe (Coercion, Coercion)
850 isCohRight_maybe (SymCo (CoherenceCo co1 co2)) = Just (mkSymCo co1, co2)
851 isCohRight_maybe _ = Nothing
852
853 -------------
854 compatible_co :: Coercion -> Coercion -> Bool
855 -- Check whether (co1 . co2) will be well-kinded
856 compatible_co co1 co2
857 = x1 `eqType` x2
858 where
859 Pair _ x1 = coercionKind co1
860 Pair x2 _ = coercionKind co2
861
862 -------------
863 {-
864 etaForAllCo_maybe
865 ~~~~~~~~~~~~~~~~~
866 Suppose we have
867
868 g : all a1:k1.t1 ~ all a2:k2.t2
869
870 but g is *not* a ForAllCo. We want to eta-expand it. So, we do this:
871
872 g' = all a1:(ForAllKindCo g).(InstCo g (a1 `mkCoherenceRightCo` ForAllKindCo g))
873
874 Call the kind coercion h1 and the body coercion h2. We can see that
875
876 h2 : t1 ~ t2[a2 |-> (a1 |> h2)]
877
878 According to the typing rule for ForAllCo, we get that
879
880 g' : all a1:k1.t1 ~ all a1:k2.(t2[a2 |-> (a1 |> h2)][a1 |-> a1 |> sym h2])
881
882 or
883
884 g' : all a1:k1.t1 ~ all a1:k2.(t2[a2 |-> a1])
885
886 as desired.
887 -}
888 etaForAllCo_maybe :: Coercion -> Maybe (TyVar, Coercion, Coercion)
889 -- Try to make the coercion be of form (forall tv:kind_co. co)
890 etaForAllCo_maybe co
891 | ForAllCo tv kind_co r <- co
892 = Just (tv, kind_co, r)
893
894 | Pair ty1 ty2 <- coercionKind co
895 , Just (tv1, _) <- splitForAllTy_maybe ty1
896 , isForAllTy ty2
897 , let kind_co = mkNthCo 0 co
898 = Just ( tv1, kind_co
899 , mkInstCo co (mkNomReflCo (TyVarTy tv1) `mkCoherenceRightCo` kind_co) )
900
901 | otherwise
902 = Nothing
903
904 etaAppCo_maybe :: Coercion -> Maybe (Coercion,Coercion)
905 -- If possible, split a coercion
906 -- g :: t1a t1b ~ t2a t2b
907 -- into a pair of coercions (left g, right g)
908 etaAppCo_maybe co
909 | Just (co1,co2) <- splitAppCo_maybe co
910 = Just (co1,co2)
911 | (Pair ty1 ty2, Nominal) <- coercionKindRole co
912 , Just (_,t1) <- splitAppTy_maybe ty1
913 , Just (_,t2) <- splitAppTy_maybe ty2
914 , let isco1 = isCoercionTy t1
915 , let isco2 = isCoercionTy t2
916 , isco1 == isco2
917 = Just (LRCo CLeft co, LRCo CRight co)
918 | otherwise
919 = Nothing
920
921 etaTyConAppCo_maybe :: TyCon -> Coercion -> Maybe [Coercion]
922 -- If possible, split a coercion
923 -- g :: T s1 .. sn ~ T t1 .. tn
924 -- into [ Nth 0 g :: s1~t1, ..., Nth (n-1) g :: sn~tn ]
925 etaTyConAppCo_maybe tc (TyConAppCo _ tc2 cos2)
926 = ASSERT( tc == tc2 ) Just cos2
927
928 etaTyConAppCo_maybe tc co
929 | mightBeUnsaturatedTyCon tc
930 , (Pair ty1 ty2, r) <- coercionKindRole co
931 , Just (tc1, tys1) <- splitTyConApp_maybe ty1
932 , Just (tc2, tys2) <- splitTyConApp_maybe ty2
933 , tc1 == tc2
934 , isInjectiveTyCon tc r -- See Note [NthCo and newtypes] in TyCoRep
935 , let n = length tys1
936 = ASSERT( tc == tc1 )
937 ASSERT( tys2 `lengthIs` n )
938 Just (decomposeCo n co)
939 -- NB: n might be <> tyConArity tc
940 -- e.g. data family T a :: * -> *
941 -- g :: T a b ~ T c d
942
943 | otherwise
944 = Nothing
945
946 {-
947 Note [Eta for AppCo]
948 ~~~~~~~~~~~~~~~~~~~~
949 Suppose we have
950 g :: s1 t1 ~ s2 t2
951
952 Then we can't necessarily make
953 left g :: s1 ~ s2
954 right g :: t1 ~ t2
955 because it's possible that
956 s1 :: * -> * t1 :: *
957 s2 :: (*->*) -> * t2 :: * -> *
958 and in that case (left g) does not have the same
959 kind on either side.
960
961 It's enough to check that
962 kind t1 = kind t2
963 because if g is well-kinded then
964 kind (s1 t2) = kind (s2 t2)
965 and these two imply
966 kind s1 = kind s2
967
968 -}
969
970 optForAllCoBndr :: LiftingContext -> Bool
971 -> TyVar -> Coercion -> (LiftingContext, TyVar, Coercion)
972 optForAllCoBndr env sym
973 = substForAllCoBndrCallbackLC sym (opt_co4_wrap env sym False Nominal) env