Simon Peyton Jones pushed to branch wip/T23162-part2 at Glasgow Haskell Compiler / GHC

Commits:

5 changed files:

Changes:

  • compiler/GHC/Core/TyCon.hs
    ... ... @@ -64,7 +64,7 @@ module GHC.Core.TyCon(
    64 64
             isTypeDataTyCon,
    
    65 65
             isEnumerationTyCon,
    
    66 66
             isNewTyCon, isAbstractTyCon,
    
    67
    -        isFamilyTyCon, isOpenFamilyTyCon,
    
    67
    +        isFamilyTyCon, isOpenFamilyTyCon, famTyConHasInjectivity,
    
    68 68
             isTypeFamilyTyCon, isDataFamilyTyCon,
    
    69 69
             isOpenTypeFamilyTyCon, isClosedFamilyTyCon_maybe,
    
    70 70
             tyConInjectivityInfo,
    
    ... ... @@ -2524,6 +2524,19 @@ isBuiltInSynFamTyCon_maybe (TyCon { tyConDetails = details })
    2524 2524
       | FamilyTyCon {famTcFlav = BuiltInSynFamTyCon ops} <- details = Just ops
    
    2525 2525
       | otherwise                                                   = Nothing
    
    2526 2526
     
    
    2527
    +famTyConHasInjectivity :: TyCon -> Bool
    
    2528
    +-- True if knowing something about the result may tell us
    
    2529
    +-- something (not necessarily everything) about the arguments
    
    2530
    +famTyConHasInjectivity (TyCon { tyConDetails = details })
    
    2531
    +  | FamilyTyCon { famTcFlav = flav, famTcInj = inj } <- details
    
    2532
    +  = case (flav, inj) of
    
    2533
    +       (ClosedSynFamilyTyCon (Just {}), _) -> True
    
    2534
    +       (BuiltInSynFamTyCon {},          _) -> True
    
    2535
    +       (_, Injective {})                   -> True
    
    2536
    +       _                                   -> False
    
    2537
    +  | otherwise
    
    2538
    +  = False
    
    2539
    +
    
    2527 2540
     -- | Extract type variable naming the result of injective type family
    
    2528 2541
     tyConFamilyResVar_maybe :: TyCon -> Maybe Name
    
    2529 2542
     tyConFamilyResVar_maybe (TyCon { tyConDetails = details })
    

  • compiler/GHC/Tc/Solver/FunDeps.hs
    ... ... @@ -36,6 +36,7 @@ import GHC.Types.Var.Set
    36 36
     import GHC.Utils.Outputable
    
    37 37
     import GHC.Utils.Panic
    
    38 38
     
    
    39
    +import Control.Monad( unless )
    
    39 40
     import GHC.Data.Pair
    
    40 41
     import Data.Maybe( isNothing, isJust, mapMaybe )
    
    41 42
     
    
    ... ... @@ -350,9 +351,9 @@ tryDictFunDepsLocal dict_ct@(DictCt { di_cls = cls, di_ev = work_ev })
    350 351
           | otherwise
    
    351 352
           = improveFromAnother (ctEvPred inert_ev) work_pred
    
    352 353
     
    
    353
    -insolubleFunDep :: CtEvidence -> TcS (StopOrContinue ())
    
    354
    +insolubleFunDep :: CtEvidence -> TcS (StopOrContinue a)
    
    354 355
     -- The fundeps generated an insoluble constraint.
    
    355
    --- Stop solving with an (insoluble) CIrredCan
    
    356
    +-- Stop solving with an (insoluble) CIrredCan -- a bit like thowing an exception
    
    356 357
     -- It's valuable to flag such constraints as insoluble becuase that improves
    
    357 358
     -- pattern-match overlap checking
    
    358 359
     insolubleFunDep ev
    
    ... ... @@ -495,16 +496,16 @@ tryFamEqFunDeps eqs_for_me fam_tc work_args
    495 496
       = if isGiven ev
    
    496 497
         then tryGivenBuiltinFamEqFDs eqs_for_me fam_tc ops work_args work_item
    
    497 498
         else do { -- Note [Do local fundeps before top-level instances]
    
    498
    -              tryFDEqns fam_tc work_args work_item $
    
    499
    -              mkLocalBuiltinFamEqFDs eqs_for_me fam_tc ops work_args work_rhs
    
    499
    +              eqns <- mkLocalBuiltinFamEqFDs eqs_for_me fam_tc ops work_args work_rhs
    
    500
    +            ; tryFDEqns fam_tc work_args work_item eqns
    
    500 501
     
    
    501
    -            ; if hasRelevantGiven eqs_for_me work_args work_item
    
    502
    -            ; then nopStage ()
    
    503
    -              else tryFDEqns fam_tc work_args work_item $
    
    504
    -                   mkTopBuiltinFamEqFDs fam_tc ops work_args work_rhs }
    
    502
    +            ; unless (hasRelevantGiven eqs_for_me work_args work_item) $
    
    503
    +              do { eqns <- mkTopBuiltinFamEqFDs fam_tc ops work_args work_rhs
    
    504
    +                 ; tryFDEqns fam_tc work_args work_item eqns } }
    
    505 505
     
    
    506
    -  | isGiven ev    -- See (INJFAM:Given)
    
    507
    -  = nopStage ()
    
    506
    +--  | isGiven ev    -- See (INJFAM:Given)
    
    507
    +--  = nopStage ()
    
    508
    +-- Continue even for Givens in the hope of discovering insolubility
    
    508 509
     
    
    509 510
       -- Only Wanted constraints below here
    
    510 511
     
    
    ... ... @@ -512,24 +513,23 @@ tryFamEqFunDeps eqs_for_me fam_tc work_args
    512 513
       = do { -- Note [Do local fundeps before top-level instances]
    
    513 514
              case tyConInjectivityInfo fam_tc of
    
    514 515
                NotInjective  -> nopStage ()
    
    515
    -           Injective inj -> tryFDEqns fam_tc work_args work_item $
    
    516
    -                            mkLocalFamEqFDs eqs_for_me fam_tc inj work_args work_rhs
    
    516
    +           Injective inj -> do { eqns <- mkLocalFamEqFDs eqs_for_me fam_tc inj work_args work_rhs
    
    517
    +                               ; tryFDEqns fam_tc work_args work_item eqns }
    
    517 518
     
    
    518
    -       ; if hasRelevantGiven eqs_for_me work_args work_item
    
    519
    -         then nopStage ()
    
    520
    -         else tryFDEqns fam_tc work_args work_item $
    
    521
    -              mkTopFamEqFDs fam_tc work_args work_rhs }
    
    519
    +       ; unless (hasRelevantGiven eqs_for_me work_args work_item) $
    
    520
    +         do { eqns <- mkTopFamEqFDs fam_tc work_args work_item
    
    521
    +            ; tryFDEqns fam_tc work_args work_item eqns } }
    
    522 522
     
    
    523
    -mkTopFamEqFDs :: TyCon -> [TcType] -> Xi -> TcS [FunDepEqns]
    
    524
    -mkTopFamEqFDs fam_tc work_args work_rhs
    
    523
    +mkTopFamEqFDs :: TyCon -> [TcType] -> EqCt -> SolverStage [FunDepEqns]
    
    524
    +mkTopFamEqFDs fam_tc work_args work_item
    
    525 525
       | isOpenTypeFamilyTyCon fam_tc
    
    526 526
       , Injective inj_flags <- tyConInjectivityInfo fam_tc
    
    527 527
       = -- Open, injective type families
    
    528
    -    mkTopOpenFamEqFDs fam_tc inj_flags work_args work_rhs
    
    528
    +    simpleStage (mkTopOpenFamEqFDs fam_tc inj_flags work_args work_item)
    
    529 529
     
    
    530 530
       | Just ax <- isClosedFamilyTyCon_maybe fam_tc
    
    531 531
       = -- Closed type families
    
    532
    -    mkTopClosedFamEqFDs ax work_args work_rhs
    
    532
    +    mkTopClosedFamEqFDs ax work_args work_item
    
    533 533
     
    
    534 534
       | otherwise
    
    535 535
       = -- Data families, abstract families,
    
    ... ... @@ -537,13 +537,13 @@ mkTopFamEqFDs fam_tc work_args work_rhs
    537 537
         -- closed type families with no equations (isClosedFamilyTyCon_maybe returns Nothing)
    
    538 538
         return []
    
    539 539
     
    
    540
    -tryFDEqns :: TyCon -> [TcType] -> EqCt -> TcS [FunDepEqns] -> SolverStage ()
    
    541
    -tryFDEqns fam_tc work_args work_item@(EqCt { eq_ev = ev, eq_rhs= rhs }) mk_fd_eqns
    
    540
    +tryFDEqns :: TyCon -> [TcType] -> EqCt -> [FunDepEqns] -> SolverStage ()
    
    541
    +tryFDEqns fam_tc work_args work_item@(EqCt { eq_ev = ev, eq_rhs= rhs }) fd_eqns
    
    542 542
       = Stage $
    
    543
    -    do { fd_eqns <- mk_fd_eqns
    
    544
    -       ; traceTcS "tryFDEqns" (vcat [ text "lhs:" <+> ppr fam_tc <+> ppr work_args
    
    543
    +    do { traceTcS "tryFDEqns" (vcat [ text "lhs:" <+> ppr fam_tc <+> ppr work_args
    
    545 544
                                         , text "rhs:" <+> ppr rhs
    
    546 545
                                         , text "eqns:" <+> ppr fd_eqns ])
    
    546
    +
    
    547 547
            ; (insoluble, unif_happened) <- solveFunDeps ev fd_eqns
    
    548 548
     
    
    549 549
            ; if | unif_happened -> startAgainWith (CEqCan work_item)
    
    ... ... @@ -553,17 +553,19 @@ tryFDEqns fam_tc work_args work_item@(EqCt { eq_ev = ev, eq_rhs= rhs }) mk_fd_eq
    553 553
     -----------------------------------------
    
    554 554
     --  User-defined type families
    
    555 555
     -----------------------------------------
    
    556
    -mkTopClosedFamEqFDs :: CoAxiom Branched -> [TcType] -> Xi -> TcS [FunDepEqns]
    
    556
    +mkTopClosedFamEqFDs :: CoAxiom Branched -> [TcType] -> EqCt -> SolverStage [FunDepEqns]
    
    557 557
     -- Look at the top-level axioms; we effectively infer injectivity,
    
    558 558
     -- so we don't need tyConInjectivtyInfo.  This works fine for closed
    
    559 559
     -- type families without injectivity info
    
    560 560
     -- See Note [Exploiting closed type families]
    
    561
    -mkTopClosedFamEqFDs ax work_args work_rhs
    
    562
    -  = do { let branches = fromBranches (coAxiomBranches ax)
    
    561
    +mkTopClosedFamEqFDs ax work_args (EqCt { eq_ev = ev, eq_rhs = work_rhs })
    
    562
    +  = Stage $
    
    563
    +    do { let branches = fromBranches (coAxiomBranches ax)
    
    563 564
            ; traceTcS "mkTopClosed" (ppr branches $$ ppr work_args $$ ppr work_rhs)
    
    564 565
            ; case getRelevantBranches ax work_args work_rhs of
    
    565
    -           [eqn] -> return [eqn]  -- If there is just one relevant equation, use it
    
    566
    -           _     -> return [] }
    
    566
    +           []    -> insolubleFunDep ev
    
    567
    +           [eqn] -> continueWith [eqn]  -- If there is just one relevant equation, use it
    
    568
    +           _     -> continueWith [] }
    
    567 569
     
    
    568 570
     hasRelevantGiven :: [EqCt] -> [TcType] -> EqCt -> Bool
    
    569 571
     -- A Given is relevant if it is not apart from the Wanted
    
    ... ... @@ -606,9 +608,9 @@ getRelevantBranches ax work_args work_rhs
    606 608
              no_match lhs_tys (CoAxBranch { cab_lhs = lhs_tys1 })
    
    607 609
                 = isNothing (tcUnifyTysForInjectivity False lhs_tys1 lhs_tys)
    
    608 610
     
    
    609
    -mkTopOpenFamEqFDs :: TyCon -> [Bool] -> [TcType] -> Xi -> TcS [FunDepEqns]
    
    611
    +mkTopOpenFamEqFDs :: TyCon -> [Bool] -> [TcType] -> EqCt -> TcS [FunDepEqns]
    
    610 612
     -- Implements (INJFAM:Wanted/top)
    
    611
    -mkTopOpenFamEqFDs fam_tc inj_flags work_args work_rhs
    
    613
    +mkTopOpenFamEqFDs fam_tc inj_flags work_args (EqCt { eq_rhs = work_rhs })
    
    612 614
       = do { fam_envs <- getFamInstEnvs
    
    613 615
            ; let branches :: [CoAxBranch]
    
    614 616
                  branches = concatMap (fromBranches . coAxiomBranches . fi_axiom) $
    
    ... ... @@ -629,7 +631,7 @@ mkTopOpenFamEqFDs fam_tc inj_flags work_args work_rhs
    629 631
           | otherwise
    
    630 632
           = Nothing
    
    631 633
     
    
    632
    -mkLocalFamEqFDs :: [EqCt] -> TyCon -> [Bool] -> [TcType] -> Xi -> TcS [FunDepEqns]
    
    634
    +mkLocalFamEqFDs :: [EqCt] -> TyCon -> [Bool] -> [TcType] -> Xi -> SolverStage [FunDepEqns]
    
    633 635
     mkLocalFamEqFDs eqs_for_me fam_tc inj_flags work_args work_rhs
    
    634 636
       = do { let -- eqns_from_inerts: see (INJFAM:Wanted/other)
    
    635 637
                  eqns_from_inerts = mapMaybe do_one eqs_for_me
    
    ... ... @@ -723,13 +725,13 @@ tryGivenBuiltinFamEqFDs eqs_for_me fam_tc ops work_args
    723 725
     
    
    724 726
         do_one _ = return ()
    
    725 727
     
    
    726
    -mkTopBuiltinFamEqFDs :: TyCon -> BuiltInSynFamily -> [TcType] -> Xi -> TcS [FunDepEqns]
    
    728
    +mkTopBuiltinFamEqFDs :: TyCon -> BuiltInSynFamily -> [TcType] -> Xi -> SolverStage [FunDepEqns]
    
    727 729
     mkTopBuiltinFamEqFDs fam_tc ops work_args work_rhs
    
    728 730
       = return [FDEqns { fd_qtvs = []
    
    729 731
                        , fd_eqs = map snd $ tryInteractTopFam ops fam_tc work_args work_rhs }]
    
    730 732
     
    
    731 733
     mkLocalBuiltinFamEqFDs :: [EqCt] -> TyCon -> BuiltInSynFamily
    
    732
    -                       -> [TcType] -> Xi -> TcS [FunDepEqns]
    
    734
    +                       -> [TcType] -> Xi -> SolverStage [FunDepEqns]
    
    733 735
     mkLocalBuiltinFamEqFDs eqs_for_me fam_tc ops work_args work_rhs
    
    734 736
       = do { let do_one :: EqCt -> [FunDepEqns]
    
    735 737
                  do_one (EqCt { eq_lhs = TyFamLHS _ inert_args, eq_rhs = inert_rhs })
    

  • compiler/GHC/Tc/Solver/InertSet.hs
    ... ... @@ -1050,6 +1050,10 @@ Here are the KickOut Criteria:
    1050 1050
           * (KK3b) If the role of `fs` is Representational:
    
    1051 1051
                kick out if `rhs_s` is of form `(lhs_w t1 .. tn)`
    
    1052 1052
     
    
    1053
    +    * (KK4: completeness) Kick out if
    
    1054
    +      * lhs_s = F lhs_tys, and
    
    1055
    +      * lhs_w is rewritable (anywhere) in rhs_s
    
    1056
    +
    
    1053 1057
     Rationale
    
    1054 1058
     
    
    1055 1059
     * (KK0) kick out only if `fw` can rewrite `fs`.
    
    ... ... @@ -1063,6 +1067,13 @@ Rationale
    1063 1067
     
    
    1064 1068
     * (KK3) see Note [KK3: completeness of solving]
    
    1065 1069
     
    
    1070
    +* (KK4) is about completeness.  If we have
    
    1071
    +     Inert:  F alpha ~ beta
    
    1072
    +     Work:   beta ~ Int
    
    1073
    +  and F is closed or injective, then we want to kick out the inert item, in
    
    1074
    +  case we get injectivity information from `F alpha ~ Int` that allows us to
    
    1075
    +  solve it.
    
    1076
    +
    
    1066 1077
     The above story is a bit vague wrt roles, but the code is not.
    
    1067 1078
     See Note [Flavours with roles]
    
    1068 1079
     
    
    ... ... @@ -1187,7 +1198,7 @@ Wrinkles:
    1187 1198
       by the inert item.  And too much kick-out is positively harmful.
    
    1188 1199
       (Historical example #14363.)
    
    1189 1200
     
    
    1190
    -* (KK3b) addresses teh main example above for KK3. Another way to understand
    
    1201
    +* (KK3b) addresses the main example above for KK3. Another way to understand
    
    1191 1202
       (KK3b) is that we treat an inert item
    
    1192 1203
             a -f-> b
    
    1193 1204
       in the same way as
    
    ... ... @@ -1732,6 +1743,12 @@ kickOutRewritableLHS ko_spec new_fr@(_, new_role)
    1732 1743
              -- The above check redundantly checks the role & flavour,
    
    1733 1744
              -- but it's very convenient
    
    1734 1745
     
    
    1746
    +      -- (KK4)
    
    1747
    +      | TyFamLHS tc _ <- lhs
    
    1748
    +      , famTyConHasInjectivity tc
    
    1749
    +      , fr_can_rewrite_ty LookEverywhere eq_rel rhs_ty
    
    1750
    +      = True
    
    1751
    +
    
    1735 1752
           -- (KK2)
    
    1736 1753
           | let where_to_look | fs_can_rewrite_fr = LookOnlyUnderFamApps
    
    1737 1754
                               | otherwise         = LookEverywhere
    

  • compiler/GHC/Tc/Solver/Monad.hs
    ... ... @@ -479,6 +479,7 @@ kickOutRewritable ko_spec new_fr
    479 479
                  n_kicked = lengthBag kicked_out
    
    480 480
            ; setInertCans ics'
    
    481 481
     
    
    482
    +       ; traceTcS "kickOutRewritable" (ppr ko_spec $$ ppr new_fr $$ ppr kicked_out)
    
    482 483
            ; unless (isEmptyBag kicked_out) $
    
    483 484
              do { emitWork kicked_out
    
    484 485
     
    

  • testsuite/tests/typecheck/should_fail/T15767.stderr
    1 1
     
    
    2 2
     T15767.hs:7:5: error: [GHC-39999]
    
    3
    -    • No instance for ‘C () b0’ arising from a use of ‘x’
    
    3
    +    • No instance for ‘C () b’ arising from a use of ‘x’
    
    4 4
         • In the expression: x
    
    5 5
           In an equation for ‘y’:
    
    6 6
               y = x