Simon Peyton Jones pushed to branch wip/T25440 at Glasgow Haskell Compiler / GHC
Commits:
-
4d2a3dbc
by Simon Peyton Jones at 2025-04-21T23:42:54+01:00
5 changed files:
- compiler/GHC/Tc/Solver/Equality.hs
- compiler/GHC/Tc/Solver/Monad.hs
- compiler/GHC/Tc/Types/Constraint.hs
- compiler/GHC/Tc/Utils/TcMType.hs
- compiler/GHC/Tc/Zonk/TcType.hs
Changes:
... | ... | @@ -1604,7 +1604,7 @@ canEqCanLHSHetero :: CtEvidence -- :: (xi1 :: ki1) ~ (xi2 :: ki2) |
1604 | 1604 | -> TcType -> TcType -- xi2
|
1605 | 1605 | -> TcKind -- ki2
|
1606 | 1606 | -> TcS (StopOrContinue (Either IrredCt EqCt))
|
1607 | -canEqCanLHSHetero ev eq_rel swapped lhs1 ps_xi1 ki1 xi2 ps_xi2 ki2
|
|
1607 | +canEqCanLHSHetero ev eq_rel swapped lhs1 ps_xi1 ki1 xi2 _ps_xi2 ki2
|
|
1608 | 1608 | -- See Note [Equalities with incompatible kinds]
|
1609 | 1609 | -- See Note [Kind Equality Orientation]
|
1610 | 1610 | |
... | ... | @@ -1625,6 +1625,9 @@ canEqCanLHSHetero ev eq_rel swapped lhs1 ps_xi1 ki1 xi2 ps_xi2 ki2 |
1625 | 1625 | -- Otherwise we might put something in the inert set that isn't inert
|
1626 | 1626 | then startAgainWith (mkNonCanonical ev)
|
1627 | 1627 | else
|
1628 | + assertPpr (not (isEmptyRewriterSet rewriters)) (ppr ev) $
|
|
1629 | + -- The rewriter set won't be empty because the two kinds differ, and there
|
|
1630 | + -- are no unifications, so we must have emitted one or more constraints
|
|
1628 | 1631 | do { let lhs_redn = mkReflRedn role ps_xi1
|
1629 | 1632 | rhs_redn = mkGReflRightRedn role xi2 mb_sym_kind_co
|
1630 | 1633 | mb_sym_kind_co = case swapped of
|
... | ... | @@ -1636,8 +1639,11 @@ canEqCanLHSHetero ev eq_rel swapped lhs1 ps_xi1 ki1 xi2 ps_xi2 ki2 |
1636 | 1639 | ppr kind_co <+> dcolon <+> sep [ ppr ki1, text "~#", ppr ki2 ])
|
1637 | 1640 | ; type_ev <- rewriteEqEvidence rewriters ev swapped lhs_redn rhs_redn
|
1638 | 1641 | |
1639 | - ; let new_xi2 = mkCastTy ps_xi2 mb_sym_kind_co
|
|
1640 | - ; canEqCanLHSHomo type_ev eq_rel NotSwapped lhs1 ps_xi1 new_xi2 new_xi2 }}
|
|
1642 | + -- The rewritten equality is non-canonical, so put it straight in the Irreds
|
|
1643 | + ; finishCanWithIrred (NonCanonicalReason (cteProblem cteCoercionHole)) type_ev } }
|
|
1644 | + |
|
1645 | +-- ; let new_xi2 = mkCastTy ps_xi2 mb_sym_kind_co
|
|
1646 | +-- ; canEqCanLHSHomo type_ev eq_rel NotSwapped lhs1 ps_xi1 new_xi2 new_xi2 }}
|
|
1641 | 1647 | |
1642 | 1648 | where
|
1643 | 1649 | mk_kind_eq :: TcS (CoercionN, RewriterSet, Bool)
|
... | ... | @@ -2044,19 +2050,20 @@ What do we do when we have an equality |
2044 | 2050 | where k1 and k2 differ? Easy: we create a coercion that relates k1 and
|
2045 | 2051 | k2 and use this to cast. To wit, from
|
2046 | 2052 | |
2047 | - [X] (tv :: k1) ~ (rhs :: k2)
|
|
2053 | + [X] co1 :: (tv :: k1) ~ (rhs :: k2)
|
|
2048 | 2054 | |
2049 | 2055 | (where [X] is [G] or [W]), we go to
|
2050 | 2056 | |
2051 | - [X] co :: k1 ~ k2
|
|
2052 | - [X] (tv :: k1) ~ ((rhs |> sym co) :: k1)
|
|
2057 | + co1 = co2 ; sym (GRefl kco)
|
|
2058 | + [X] co2 :: (tv :: k1) ~ ((rhs |> sym kco) :: k1)
|
|
2059 | + [X] kco :: k1 ~ k2
|
|
2053 | 2060 | |
2054 | 2061 | Wrinkles:
|
2055 | 2062 | |
2056 | -(EIK1) When X is W, the new type-level wanted is effectively rewritten by the
|
|
2057 | - kind-level one. We thus include the kind-level wanted in the RewriterSet
|
|
2058 | - for the type-level one. See Note [Wanteds rewrite Wanteds] in GHC.Tc.Types.Constraint.
|
|
2059 | - This is done in canEqCanLHSHetero.
|
|
2063 | +(EIK1) When X=Wanted, the new type-level wanted for `co` is effectively rewritten by
|
|
2064 | + the kind-level one. We thus include the kind-level wanted in the RewriterSet
|
|
2065 | + for the type-level one. See Note [Wanteds rewrite Wanteds] in
|
|
2066 | + GHC.Tc.Types.Constraint. This is done in canEqCanLHSHetero.
|
|
2060 | 2067 | |
2061 | 2068 | (EIK2) Suppose we have [W] (a::Type) ~ (b::Type->Type). The above rewrite will produce
|
2062 | 2069 | [W] w : a ~ (b |> kw)
|
... | ... | @@ -2076,7 +2083,7 @@ Wrinkles: |
2076 | 2083 | Instead, it lands in the inert_irreds in the inert set, awaiting solution of
|
2077 | 2084 | that `kw`.
|
2078 | 2085 | |
2079 | - (EIK2a) We must later indeed unify if/when the kind-level wanted, `kw` gets
|
|
2086 | + (EIK2a) We must later indeed unify if/when the kind-level wanted, `kw` gets
|
|
2080 | 2087 | solved. This is done in `kickOutAfterFillingCoercionHole`, which kicks out
|
2081 | 2088 | all equalities whose RHS mentions the filled-in coercion hole. Note that
|
2082 | 2089 | it looks for type family equalities, too, because of the use of unifyTest
|
... | ... | @@ -2086,7 +2093,7 @@ Wrinkles: |
2086 | 2093 | which records that `w` has been rewritten by `kw`.
|
2087 | 2094 | See (WRW3) in Note [Wanteds rewrite Wanteds] in GHC.Tc.Types.Constraint.
|
2088 | 2095 | |
2089 | - (EIK2b) What if the RHS mentions /other/ coercion holes? How can that happen? The
|
|
2096 | + (EIK2b) What if the RHS mentions /other/ coercion holes? How can that happen? The
|
|
2090 | 2097 | main way is like this. Assume F :: forall k. k -> Type
|
2091 | 2098 | [W] kw : k ~ Type
|
2092 | 2099 | [W] w : a ~ F k t
|
... | ... | @@ -2097,15 +2104,32 @@ Wrinkles: |
2097 | 2104 | rewriting. Indeed tests JuanLopez only typechecks if we do. So we'd like to treat
|
2098 | 2105 | this kind of equality as canonical.
|
2099 | 2106 | |
2100 | - Hence the ch_hetero_kind field in CoercionHole: it is True of constraints
|
|
2101 | - created by `canEqCanLHSHetero` to fix up hetero-kinded equalities; and False otherwise:
|
|
2107 | + So here is our implementation:
|
|
2108 | + * The `ch_hetero_kind` field in CoercionHole identifies a coercion hole created
|
|
2109 | + by `canEqCanLHSHetero` to fix up hetero-kinded equalities.
|
|
2102 | 2110 | |
2103 | 2111 | * An equality constraint is non-canonical if it mentions a hetero-kind
|
2104 | - CoercionHole on the RHS. See the `hasCoercionHoleCo` test in GHC.Tc.Utils.checkCo.
|
|
2112 | + CoercionHole on the RHS. This (and only this) is the (TyEq:CH) invariant
|
|
2113 | + for canonical equalities (see Note [Canonical equalities])
|
|
2114 | + |
|
2115 | + * The invariant is checked by See the `hasCoercionHoleCo` test in
|
|
2116 | + GHC.Tc.Utils.Unify.checkCo. , and is what `cteCoercionHole` reason in
|
|
2117 | + `CheckTyEqResult` means.
|
|
2118 | + |
|
2119 | + * These special hetero-kind CoercionHoles are created by the `uType` unifier when
|
|
2120 | + the parent's CtOrigin is KindEqOrigin: see GHC.Tc.Utils.TcMType.newCoercionHole
|
|
2121 | + and friends.
|
|
2122 | + |
|
2123 | + We set this origin, via `updUEnvLoc`, in `mk_kind_eq` in `canEqCanLHSHetero`.
|
|
2124 | + |
|
2125 | + * We /also/ add the coercion hole to the `RewriterSet` of the constraint,
|
|
2126 | + in `canEqCanLHSHetero`
|
|
2127 | + |
|
2128 | + * When filling one of these special hetero-kind coercion holes, we kick out
|
|
2129 | + any IrredCt's that mention this hole; maybe it is now canonical.
|
|
2130 | + See `kickOutAfterFillingCoercionHole`.
|
|
2105 | 2131 | |
2106 | - * Hetero-kind CoercionHoles are created when the parent's CtOrigin is
|
|
2107 | - KindEqOrigin: see GHC.Tc.Utils.TcMType.newCoercionHole and friends. We
|
|
2108 | - set this origin, via `mkKindLoc`, in `mk_kind_eq` in `canEqCanLHSHetero`.
|
|
2132 | + Gah! This is bizarrely complicated.
|
|
2109 | 2133 | |
2110 | 2134 | (EIK3) Suppose we have [W] (a :: k1) ~ (rhs :: k2). We duly follow the
|
2111 | 2135 | algorithm detailed here, producing [W] co :: k1 ~ k2, and adding
|
... | ... | @@ -466,10 +466,13 @@ kickOutAfterUnification tv_list = case nonEmpty tv_list of |
466 | 466 | ; return n_kicked }
|
467 | 467 | |
468 | 468 | kickOutAfterFillingCoercionHole :: CoercionHole -> TcS ()
|
469 | --- See Wrinkle (EIK2a) in Note [Equalities with incompatible kinds] in GHC.Tc.Solver.Equality
|
|
469 | +-- See Wrinkle (EIK2) in Note [Equalities with incompatible kinds] in GHC.Tc.Solver.Equality
|
|
470 | 470 | -- It's possible that this could just go ahead and unify, but could there be occurs-check
|
471 | 471 | -- problems? Seems simpler just to kick out.
|
472 | 472 | kickOutAfterFillingCoercionHole hole
|
473 | + | not (isHeteroKindCoHole hole)
|
|
474 | + = return () -- Only hetero-kind coeercion holes provoke kick-out
|
|
475 | + | otherwise
|
|
473 | 476 | = do { ics <- getInertCans
|
474 | 477 | ; let (kicked_out, ics') = kick_out ics
|
475 | 478 | n_kicked = lengthBag kicked_out
|
... | ... | @@ -493,9 +496,9 @@ kickOutAfterFillingCoercionHole hole |
493 | 496 | where
|
494 | 497 | (irreds_to_kick, irreds_to_keep) = partitionBag kick_ct irreds
|
495 | 498 | |
496 | - kick_ct :: IrredCt -> Bool
|
|
497 | - -- True: kick out; False: keep.
|
|
498 | - kick_ct ct
|
|
499 | + kick_ct :: IrredCt -> Bool -- True: kick out; False: keep.
|
|
500 | + kick_ct ct -- See (EIK2) in Note [Equalities with incompatible kinds]
|
|
501 | + -- for this very specific kick-ot stuff
|
|
499 | 502 | | IrredCt { ir_ev = ev, ir_reason = reason } <- ct
|
500 | 503 | , CtWanted (WantedCt { ctev_rewriters = RewriterSet rewriters }) <- ev
|
501 | 504 | , NonCanonicalReason ctyeq <- reason
|
... | ... | @@ -241,17 +241,23 @@ instance Outputable DictCt where |
241 | 241 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
242 | 242 | An EqCt is a canonical equality constraint, one that can live in the inert set,
|
243 | 243 | and that can be used to rewrite other constraints. It satisfies these invariants:
|
244 | + |
|
244 | 245 | * (TyEq:OC) lhs does not occur in rhs (occurs check)
|
245 | 246 | Note [EqCt occurs check]
|
247 | + |
|
246 | 248 | * (TyEq:F) rhs has no foralls
|
247 | 249 | (this avoids substituting a forall for the tyvar in other types)
|
250 | + |
|
248 | 251 | * (TyEq:K) typeKind lhs `tcEqKind` typeKind rhs; Note [Ct kind invariant]
|
252 | + |
|
249 | 253 | * (TyEq:N) If the equality is representational, rhs is not headed by a saturated
|
250 | 254 | application of a newtype TyCon. See GHC.Tc.Solver.Equality
|
251 | 255 | Note [No top-level newtypes on RHS of representational equalities].
|
252 | 256 | (Applies only when constructor of newtype is in scope.)
|
257 | + |
|
253 | 258 | * (TyEq:U) An EqCt is not immediately unifiable. If we can unify a:=ty, we
|
254 | 259 | will not form an EqCt (a ~ ty).
|
260 | + |
|
255 | 261 | * (TyEq:CH) rhs does not mention any coercion holes that resulted from fixing up
|
256 | 262 | a hetero-kinded equality. See Note [Equalities with incompatible kinds] in
|
257 | 263 | GHC.Tc.Solver.Equality, wrinkle (EIK2)
|
... | ... | @@ -534,9 +540,12 @@ cteSolubleOccurs = CTEP (bit 3) -- Occurs-check under a type function, or in |
534 | 540 | -- cteSolubleOccurs must be one bit to the left of cteInsolubleOccurs
|
535 | 541 | -- See also Note [Insoluble mis-match] in GHC.Tc.Errors
|
536 | 542 | |
537 | -cteCoercionHole = CTEP (bit 4) -- Coercion hole encountered
|
|
543 | +cteCoercionHole = CTEP (bit 4) -- Kind-equality coercion hole encountered
|
|
544 | + -- See (EIK2) in Note [Equalities with incompatible kinds]
|
|
545 | + |
|
538 | 546 | cteConcrete = CTEP (bit 5) -- Type variable that can't be made concrete
|
539 | 547 | -- e.g. alpha[conc] ~ Maybe beta[tv]
|
548 | + |
|
540 | 549 | cteSkolemEscape = CTEP (bit 6) -- Skolem escape e.g. alpha[2] ~ b[sk,4]
|
541 | 550 | |
542 | 551 | cteProblem :: CheckTyEqProblem -> CheckTyEqResult
|
... | ... | @@ -369,6 +369,7 @@ newCoercionHoleO (KindEqOrigin {}) pty = new_coercion_hole True pty |
369 | 369 | newCoercionHoleO _ pty = new_coercion_hole False pty
|
370 | 370 | |
371 | 371 | new_coercion_hole :: Bool -> TcPredType -> TcM CoercionHole
|
372 | +-- For the Bool, see (EIK2) in Note [Equalities with incompatible kinds]
|
|
372 | 373 | new_coercion_hole hetero_kind pred_ty
|
373 | 374 | = do { co_var <- newEvVar pred_ty
|
374 | 375 | ; traceTc "New coercion hole:" (ppr co_var <+> dcolon <+> ppr pred_ty)
|
... | ... | @@ -578,13 +578,12 @@ zonkCtEvRewriterSet ev@(CtWanted wtd) |
578 | 578 | = do { rewriters' <- zonkRewriterSet (ctEvRewriters ev)
|
579 | 579 | ; return (CtWanted $ setWantedCtEvRewriters wtd rewriters') }
|
580 | 580 | |
581 | --- | Check whether any coercion hole in a RewriterSet is still unsolved.
|
|
582 | --- Does this by recursively looking through filled coercion holes until
|
|
583 | --- one is found that is not yet filled in, at which point this aborts.
|
|
581 | +-- | Zonk a rewriter set; if a coercion hole in the set has been filled,
|
|
582 | +-- find all the free un-filled coercion holes in the coercion that fills it
|
|
584 | 583 | zonkRewriterSet :: RewriterSet -> ZonkM RewriterSet
|
585 | 584 | zonkRewriterSet (RewriterSet set)
|
586 | 585 | = nonDetStrictFoldUniqSet go (return emptyRewriterSet) set
|
587 | - -- this does not introduce non-determinism, because the only
|
|
586 | + -- This does not introduce non-determinism, because the only
|
|
588 | 587 | -- monadic action is to read, and the combining function is
|
589 | 588 | -- commutative
|
590 | 589 | where
|
... | ... | @@ -592,10 +591,11 @@ zonkRewriterSet (RewriterSet set) |
592 | 591 | go hole m_acc = unionRewriterSet <$> check_hole hole <*> m_acc
|
593 | 592 | |
594 | 593 | check_hole :: CoercionHole -> ZonkM RewriterSet
|
595 | - check_hole hole = do { m_co <- unpackCoercionHole_maybe hole
|
|
596 | - ; case m_co of
|
|
597 | - Nothing -> return (unitRewriterSet hole)
|
|
598 | - Just co -> unUCHM (check_co co) }
|
|
594 | + check_hole hole
|
|
595 | + = do { m_co <- unpackCoercionHole_maybe hole
|
|
596 | + ; case m_co of
|
|
597 | + Nothing -> return (unitRewriterSet hole) -- Not filled
|
|
598 | + Just co -> unUCHM (check_co co) } -- Filled: look inside
|
|
599 | 599 | |
600 | 600 | check_ty :: Type -> UnfilledCoercionHoleMonoid
|
601 | 601 | check_co :: Coercion -> UnfilledCoercionHoleMonoid
|