Simon Peyton Jones pushed to branch wip/T25440 at Glasgow Haskell Compiler / GHC

Commits:

5 changed files:

Changes:

  • compiler/GHC/Tc/Solver/Equality.hs
    ... ... @@ -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
    

  • compiler/GHC/Tc/Solver/Monad.hs
    ... ... @@ -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
    

  • compiler/GHC/Tc/Types/Constraint.hs
    ... ... @@ -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
    

  • compiler/GHC/Tc/Utils/TcMType.hs
    ... ... @@ -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)
    

  • compiler/GHC/Tc/Zonk/TcType.hs
    ... ... @@ -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