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
|