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

Commits:

8 changed files:

Changes:

  • compiler/GHC/Core/Predicate.hs
    ... ... @@ -700,7 +700,9 @@ types/kinds are fully settled and zonked.
    700 700
     -- See also Note [Ordering of implicit variables] in "GHC.Rename.HsType"
    
    701 701
     
    
    702 702
     scopedSort :: [Var] -> [Var]
    
    703
    -scopedSort = go [] []
    
    703
    +scopedSort xs
    
    704
    +  | null xs   = []
    
    705
    +  | otherwise = go [] [] xs
    
    704 706
       where
    
    705 707
         go :: [Var] -- already sorted, in reverse order
    
    706 708
            -> [TyCoVarSet] -- each set contains all the variables which must be placed
    

  • compiler/GHC/Core/TyCo/FVs.hs
    ... ... @@ -49,6 +49,7 @@ module GHC.Core.TyCo.FVs
    49 49
             -- Any and No Free vars
    
    50 50
             anyFreeVarsOfType, anyFreeVarsOfTypes, anyFreeVarsOfCo,
    
    51 51
             noFreeVarsOfType, noFreeVarsOfTypes, noFreeVarsOfCo,
    
    52
    +        anyShallowFreeVarsOfType,
    
    52 53
     
    
    53 54
             -- * Free type constructors
    
    54 55
             tyConsOfType, tyConsOfTypes,
    
    ... ... @@ -1159,10 +1160,12 @@ nice tight loops.
    1159 1160
     {-# INLINE afvFolder #-}   -- See Note [Any-free-var folder]
    
    1160 1161
     afvFolder :: TyCoFolder (FV (BoundVars, TyCoVar -> Bool) DM.Any)
    
    1161 1162
     -- 'afvFolder' is short for "any-free-var folder", good for checking
    
    1162
    ---   if any /deep/ free var of a type satisfies a predicate `check_fv`
    
    1163
    +--   if any /shallow/ free var of a type satisfies a predicate `check_fv`
    
    1163 1164
     -- The "env" of the (FV env Any) is a pair (bvs,pred) of
    
    1164 1165
     --    the bound variables (which are definitely not free), and
    
    1165 1166
     --    an "interesting var" predicate which the client supplies
    
    1167
    +--
    
    1168
    +-- You can get "deep" by supplying a predicte that also looks in the kind
    
    1166 1169
     afvFolder = TyCoFolder { tcf_view = noView  -- See Note [Free vars and synonyms]
    
    1167 1170
                            , tcf_tyvar = do_tcv
    
    1168 1171
                            , tcf_covar = do_tcv
    
    ... ... @@ -1173,8 +1176,7 @@ afvFolder = TyCoFolder { tcf_view = noView -- See Note [Free vars and synonyms]
    1173 1176
         -- Check the variable itself with check_fv,
    
    1174 1177
         -- and check its kind (this is a deep folder)
    
    1175 1178
         do_tcv tcv = MkFV $ \ (bvs,check_fv) ->
    
    1176
    -                 Any (not (tcv `elemVarSet` bvs) &&
    
    1177
    -                      (check_fv tcv || runAny check_fv (afv_type (varType tcv))))
    
    1179
    +                 Any (not (tcv `elemVarSet` bvs) && check_fv tcv)
    
    1178 1180
         do_hole hole = do_tcv (coHoleCoVar hole)
    
    1179 1181
     
    
    1180 1182
     afv_type  :: Type     -> FV (BoundVars, TyVar -> Bool) DM.Any
    
    ... ... @@ -1186,16 +1188,34 @@ runAny :: (TyVar -> Bool) -> FV (BoundVars, TyCoVar -> Bool) DM.Any -> Bool
    1186 1188
     {-# INLINE runAny #-}
    
    1187 1189
     runAny check_fv fvs = DM.getAny (runFV fvs (emptyVarSet, check_fv))
    
    1188 1190
     
    
    1191
    +---------------------------------------------
    
    1192
    +-- anyShallowFreeVarsOfType and friends look only for shallow free vars
    
    1193
    +
    
    1194
    +anyShallowFreeVarsOfType :: (TyCoVar -> Bool) -> Type -> Bool
    
    1195
    +{-# INLINE anyShallowFreeVarsOfType #-}
    
    1196
    +-- Shallow only
    
    1197
    +anyShallowFreeVarsOfType check_fv ty = runAny check_fv (afv_type ty)
    
    1198
    +
    
    1199
    +
    
    1200
    +---------------------------------------------
    
    1201
    +-- anyFreeVarsOfType and friends look for deep free vars
    
    1202
    +
    
    1203
    +deep_check :: (TyCoVar -> Bool) -> TyCoVar -> Bool
    
    1204
    +-- This is inefficient because if one tyvar occurs many times
    
    1205
    +-- in a type, it'll look in its kind at each occurrence. Boo.
    
    1206
    +deep_check check_fv tcv = check_fv tcv || anyFreeVarsOfType check_fv (varType tcv)
    
    1207
    +
    
    1189 1208
     anyFreeVarsOfType :: (TyCoVar -> Bool) -> Type -> Bool
    
    1190 1209
     {-# INLINE anyFreeVarsOfType #-}
    
    1191
    -anyFreeVarsOfType check_fv ty = runAny check_fv (afv_type ty)
    
    1210
    +-- Looks deeply, into the kinds of the free vars
    
    1211
    +anyFreeVarsOfType check_fv ty = runAny (deep_check check_fv) (afv_type ty)
    
    1192 1212
     
    
    1193 1213
     anyFreeVarsOfTypes :: (TyCoVar -> Bool) -> [Type] -> Bool
    
    1194 1214
     {-# INLINE anyFreeVarsOfTypes #-}
    
    1195
    -anyFreeVarsOfTypes check_fv tys = runAny check_fv (afv_types tys)
    
    1215
    +anyFreeVarsOfTypes check_fv tys = runAny (deep_check check_fv) (afv_types tys)
    
    1196 1216
     
    
    1197 1217
     anyFreeVarsOfCo :: (TyCoVar -> Bool) -> Coercion -> Bool
    
    1198
    -anyFreeVarsOfCo check_fv co = runAny check_fv (afv_co co)
    
    1218
    +anyFreeVarsOfCo check_fv co = runAny (deep_check check_fv) (afv_co co)
    
    1199 1219
     
    
    1200 1220
     noFreeVarsOfType :: Type -> Bool
    
    1201 1221
     noFreeVarsOfType ty = not $ runAny (const True) (afv_type ty)
    
    ... ... @@ -1206,6 +1226,7 @@ noFreeVarsOfTypes tys = not $ runAny (const True) (afv_types tys)
    1206 1226
     noFreeVarsOfCo :: Coercion -> Bool
    
    1207 1227
     noFreeVarsOfCo co = not $ runAny (const True) (afv_co co)
    
    1208 1228
     
    
    1229
    +
    
    1209 1230
     {-
    
    1210 1231
     ************************************************************************
    
    1211 1232
     *                                                                      *
    

  • compiler/GHC/Core/Unify.hs
    ... ... @@ -33,7 +33,9 @@ import GHC.Core.TyCon
    33 33
     import GHC.Core.Predicate( CanEqLHS(..), canEqLHS_maybe )
    
    34 34
     import GHC.Core.TyCon.Env
    
    35 35
     import GHC.Core.TyCo.Rep
    
    36
    +import GHC.Core.TyCo.FVs
    
    36 37
     import GHC.Core.TyCo.Compare ( eqType, tcEqType, tcEqTyConAppArgs )
    
    38
    +import qualified GHC.Core.TyCo.Subst as S
    
    37 39
     import GHC.Core.TyCo.Subst   ( mkTvSubst )
    
    38 40
     import GHC.Core.Map.Type
    
    39 41
     import GHC.Core.Multiplicity
    
    ... ... @@ -1090,43 +1092,37 @@ the invocation of F! We don't have a function that recursively
    1090 1092
     applies substitutions inside the kinds of variable occurrences (and
    
    1091 1093
     probably rightly so).
    
    1092 1094
     
    
    1093
    -So, we work as follows:
    
    1095
    +Ugh!  This whole thing is pretty horrible. We work as follows:
    
    1094 1096
     
    
    1095 1097
      1. Start with the current substitution (which we are
    
    1096 1098
         trying to fixpoint
    
    1097 1099
            [ xs :-> F a (z :: a) (rest :: G a (z :: a))
    
    1098 1100
            , a  :-> b ]
    
    1099 1101
     
    
    1100
    - 2. Take all the free vars of the range of the substitution:
    
    1101
    -       {a, z, rest, b}
    
    1102
    -    NB: the free variable finder closes over
    
    1103
    -        the kinds of variable occurrences
    
    1102
    + 2. Find its fixed point.  Remember, substitution is shallow. That gives:
    
    1103
    +       [ xs :-> F b (z :: a) (rest :: G a (z :: a))
    
    1104
    +       , a  :-> b ]
    
    1105
    +    Note the 'a' lurking inside (z::a)
    
    1104 1106
     
    
    1105
    - 3. If none are in the domain of the substitution, stop.
    
    1106
    -    We have found a fixpoint.
    
    1107
    + 3. Take all the deep free vars of the range of the substitution:
    
    1108
    +       {a, (z::a), (rest::G a z), b}
    
    1107 1109
     
    
    1108 1110
      4. Remove the variables that are bound by the substitution, leaving
    
    1109 1111
            {z, rest, b}
    
    1110 1112
     
    
    1111
    - 5. Do a topo-sort to put them in dependency order:
    
    1113
    + 5. Do a `scopedSort` to put them in dependency order:
    
    1112 1114
            [ b :: *, z :: a, rest :: G a z ]
    
    1113 1115
     
    
    1114
    - 6. Apply the substitution left-to-right to the kinds of these
    
    1115
    -    tyvars, extending it each time with a new binding, so we
    
    1116
    -    finish up with
    
    1117
    -       [ xs   :-> ..as before..
    
    1118
    -       , a    :-> b
    
    1119
    -       , b    :-> b    :: *
    
    1116
    + 6. Make a "re-kinding substitution" by applying the fixpoint from (2)
    
    1117
    +    to the kind of each tyvar in this list -- and then applying the
    
    1118
    +    re-kinding from earlier variables.
    
    1119
    +       [ b    :-> b    :: *
    
    1120 1120
            , z    :-> z    :: b
    
    1121 1121
            , rest :-> rest :: G b (z :: b) ]
    
    1122 1122
         Note that rest now has the right kind
    
    1123 1123
     
    
    1124 1124
      7. Apply this extended substitution (once) to the range of the
    
    1125
    -    /original/ substitution.  (Note that the extended substitution
    
    1126
    -    would go on forever if you tried to find its fixpoint, because it
    
    1127
    -    maps z to z.)
    
    1128
    -
    
    1129
    - 8. And go back to step 1
    
    1125
    +    fixpoint substitution from (2).
    
    1130 1126
     
    
    1131 1127
     In Step 6 we use the free vars from Step 2 as the initial
    
    1132 1128
     in-scope set, because all of those variables appear in the
    
    ... ... @@ -1136,13 +1132,59 @@ variables in the in-scope set; it is used only to ensure no
    1136 1132
     shadowing.
    
    1137 1133
     -}
    
    1138 1134
     
    
    1139
    -niFixSubst :: InScopeSet -> TvSubstEnv -> Subst
    
    1135
    +niFixSubst, niFixSubst' :: InScopeSet -> TvSubstEnv -> Subst
    
    1140 1136
     -- Find the idempotent fixed point of the non-idempotent substitution
    
    1141 1137
     -- This is surprisingly tricky:
    
    1142 1138
     --   see Note [Finding the substitution fixpoint]
    
    1143 1139
     -- ToDo: use laziness instead of iteration?
    
    1144 1140
     niFixSubst in_scope tenv
    
    1145
    -  | not_fixpoint = niFixSubst in_scope (mapVarEnv (substTy subst) tenv)
    
    1141
    +  =  pprTrace "niFixSubst" (vcat [ text "In: " <+> ppr tenv
    
    1142
    +                                 , text "Out:" <+> ppr (S.getTvSubstEnv subst) ])
    
    1143
    +     subst
    
    1144
    +  where
    
    1145
    +     subst = niFixSubst' in_scope tenv
    
    1146
    +
    
    1147
    +niFixSubst' in_scope orig_tenv
    
    1148
    +  = mkTvSubst in_scope (mapVarEnv (subst_tenv rekinding_tenv) fix_tenv)
    
    1149
    +  where
    
    1150
    +    in_dom tv = tv `elemVarEnv` orig_tenv
    
    1151
    +
    
    1152
    +    fix_tenv :: TvSubstEnv
    
    1153
    +    fix_tenv = go_fix orig_tenv  -- Repeatedly apply tenv until we get a fixpoint
    
    1154
    +
    
    1155
    +    go_fix tenv_so_far
    
    1156
    +       | anyVarEnv (anyShallowFreeVarsOfType in_dom) tenv_so_far
    
    1157
    +       = go_fix (mapVarEnv (subst_tenv tenv_so_far) tenv_so_far)
    
    1158
    +       | otherwise
    
    1159
    +       = tenv_so_far
    
    1160
    +
    
    1161
    +    free_tvs :: [TyVar]
    
    1162
    +    free_tvs = scopedSort        $
    
    1163
    +               filterOut in_dom  $
    
    1164
    +               nonDetVarSetElems $
    
    1165
    +               tyCoVarsOfTypes   $
    
    1166
    +               nonDetEltsUFM orig_tenv
    
    1167
    +          -- It's OK to use nonDetEltsUFM (twice) here because
    
    1168
    +          -- the order of range_tvs is immaterial
    
    1169
    +
    
    1170
    +    rekinding_tenv = foldl' add_free_tv emptyTvSubstEnv free_tvs
    
    1171
    +
    
    1172
    +    add_free_tv :: TvSubstEnv -> TyVar -> TvSubstEnv
    
    1173
    +    add_free_tv rke_so_far tv
    
    1174
    +      | isTyVar tv
    
    1175
    +      , let k' = subst_tenv rke_so_far $
    
    1176
    +                 subst_tenv fix_tenv   $
    
    1177
    +                 tyVarKind tv
    
    1178
    +      = extendVarEnv rke_so_far tv (mkTyVarTy (setTyVarKind tv k'))
    
    1179
    +      | otherwise
    
    1180
    +      = rke_so_far
    
    1181
    +
    
    1182
    +    subst_tenv :: TvSubstEnv -> Type -> Type
    
    1183
    +    subst_tenv tenv = substTy (mkTvSubst in_scope tenv)
    
    1184
    +
    
    1185
    +{-
    
    1186
    +--  | not_fixpoint = niFixSubst' in_scope (mapVarEnv (substTy subst) tenv)
    
    1187
    +  | not_fixpoint = niFixSubst' in_scope (mapVarEnv (substTy subst) tenv)
    
    1146 1188
       | otherwise    = tenv_subst
    
    1147 1189
       where
    
    1148 1190
         tenv_subst = mkTvSubst in_scope tenv   -- This is our starting point
    
    ... ... @@ -1154,12 +1196,26 @@ niFixSubst in_scope tenv
    1154 1196
               -- It's OK to use nonDetEltsUFM (twice) here because
    
    1155 1197
               -- the order of range_tvs is immaterial
    
    1156 1198
     
    
    1157
    -    not_fixpoint  = any in_domain range_tvs
    
    1158
    -    in_domain tv  = tv `elemVarEnv` tenv
    
    1159
    -
    
    1160
    -    free_tvs = scopedSort (filterOut in_domain range_tvs)
    
    1199
    +    not_fixpoint = any in_domain range_tvs
    
    1200
    +    in_domain tv = tv `elemVarEnv` tenv
    
    1201
    +    free_tvs     = scopedSort (filterOut in_domain range_tvs)
    
    1161 1202
     
    
    1162 1203
         -- See Note [Finding the substitution fixpoint], Step 6
    
    1204
    +    rekinding_tenv = foldl' add_free_tv emptyTvSubstEnv free_tvs
    
    1205
    +    add_free_tv :: TvSubstEnv -> TyVar -> TvSubstEnv
    
    1206
    +    add_free_tv rke tv
    
    1207
    +      | isTyVar tv, anyFreeVarsOfType in_domain (varType tv)
    
    1208
    +      , let tv' = updateTyVarKind (substTy tenv_subst) tv
    
    1209
    +      = extendVarEnv rke tv (mkTyVarTy tv')
    
    1210
    +      | otherwise
    
    1211
    +      = rke
    
    1212
    +
    
    1213
    +    rekinding_subst = mkTvSubst in_scope rekinding_tenv
    
    1214
    +
    
    1215
    +    subst = mkTvSubst in_scope (rekinding_tenv `plusVarEnv`
    
    1216
    +                                mapVarEnv (substTy rekinding_subst) tenv)
    
    1217
    +
    
    1218
    +{-
    
    1163 1219
         subst = foldl' add_free_tv tenv_subst free_tvs
    
    1164 1220
     
    
    1165 1221
         add_free_tv :: Subst -> TyVar -> Subst
    
    ... ... @@ -1168,6 +1224,8 @@ niFixSubst in_scope tenv
    1168 1224
           | otherwise  = subst  -- Ignore free coercion variables
    
    1169 1225
          where
    
    1170 1226
             tv' = updateTyVarKind (substTy subst) tv
    
    1227
    +-}
    
    1228
    +-}
    
    1171 1229
     
    
    1172 1230
     {-
    
    1173 1231
     ************************************************************************
    

  • compiler/GHC/Tc/Solver/FunDeps.hs
    ... ... @@ -29,13 +29,10 @@ import GHC.Core.TyCon
    29 29
     import GHC.Core.Unify( AmIUnifying(..)
    
    30 30
                          , tcUnifyTysForInjectivity, typeListsAreApart )
    
    31 31
     import GHC.Core.Coercion.Axiom
    
    32
    -import GHC.Core.TyCo.Subst( elemSubst, extendTvSubstWithClone )
    
    33 32
     
    
    34 33
     import GHC.Builtin.WiredIn.TypeLits( tryInteractTopFam, tryInteractInertFam )
    
    35 34
     
    
    36
    -import GHC.Types.Var( TyVar, tyVarKind, setTyVarKind )
    
    37 35
     import GHC.Types.Var.Set
    
    38
    -import GHC.Types.Var.Env( mkInScopeSet )
    
    39 36
     
    
    40 37
     import GHC.Utils.Outputable
    
    41 38
     import GHC.Utils.Panic
    
    ... ... @@ -57,7 +54,6 @@ Here is our plan for dealing with functional dependencies
    57 54
            * send the current constraint back to the start of the pipeline;
    
    58 55
              it might now be soluble, and it probably isn't inert
    
    59 56
     
    
    60
    -
    
    61 57
     * Once a unification is done, it can't be un-done.  So we must be very careful
    
    62 58
       not to threaten completeness by doing a unification when there might be
    
    63 59
       another way to solve the constraint.
    
    ... ... @@ -709,18 +705,16 @@ getRelevantBranches ax work_args work_rhs
    709 705
                                             , cab_lhs = lhs_tys
    
    710 706
                                             , cab_rhs = rhs_ty })
    
    711 707
                 | Just subst <- tcUnifyTysForInjectivity Unifying (rhs_ty:lhs_tys) work_tys
    
    712
    -              -- See (RW1)-(RW3) in Note [Relevance]
    
    713
    -              -- This is a pre-/unification/ check (not matching)
    
    714
    -              -- so `subst` can bind both `qtvs` and fvs(work_tys)
    
    715
    -            , let (subst',qtvs') = trim_qtvs subst qtvs
    
    716
    -                  lhs_tys'       = substTys subst' lhs_tys
    
    717
    -                  rhs_ty'        = substTy  subst' rhs_ty
    
    718
    -                  branch_tys'    = rhs_ty' : lhs_tys'
    
    708
    +                            -- See (RW1)-(RW3) in Note [Relevance]
    
    709
    +            , let lhs_tys' = substTys subst lhs_tys
    
    719 710
                 , noEarlierMatchCheck lhs_tys' branch  -- See (RW4) in Note [Relevance]
    
    720
    -            = Just (FDEqns { fd_qtvs = qtvs'
    
    721
    -                           , fd_eqs  = zipWith Pair branch_tys' work_tys })
    
    722
    -                              -- Do not apply the substition to `work_tys`;
    
    723
    -                              -- See (CF7) in Note [Exploiting closed type families]
    
    711
    +            = -- Ignore the substitution, except for `noEarlierMatchCheck`
    
    712
    +              -- See (CF7) in Note [Exploiting closed type families]
    
    713
    +                Just (FDEqns { fd_qtvs = qtvs
    
    714
    +                           , fd_eqs  = zipWith Pair (rhs_ty:lhs_tys) work_tys })
    
    715
    +              -- Do not apply the substitution to `work_tys`;
    
    716
    +              -- See (CF8) in Note [Exploiting closed type families]
    
    717
    +
    
    724 718
                 | otherwise
    
    725 719
                 = Nothing
    
    726 720
     
    
    ... ... @@ -738,12 +732,10 @@ mkTopOpenFamEqFDs fam_tc inj_flags work_args (EqCt { eq_rhs = work_rhs })
    738 732
         do_one (CoAxBranch { cab_tvs = branch_qtvs
    
    739 733
                            , cab_lhs = branch_lhs_tys
    
    740 734
                            , cab_rhs = branch_rhs })
    
    741
    -      | Just subst <- tcUnifyTysForInjectivity Matching [branch_rhs] [work_rhs]
    
    742
    -      , let (subst', qtvs') = trim_qtvs subst branch_qtvs
    
    743
    -            branch_lhs_tys' = substTys subst' branch_lhs_tys
    
    744
    -        -- No need for an apartness check here; for open type families
    
    745
    -        -- there are no "preceding" equations
    
    746
    -      = Just (mkInjectivityFDEqn inj_flags qtvs' branch_lhs_tys' work_args)
    
    735
    +      | Just {} <- tcUnifyTysForInjectivity Matching [branch_rhs] [work_rhs]
    
    736
    +        -- No need for an apartness check here;
    
    737
    +        -- for open type families there are no "preceding" equations
    
    738
    +      = Just (mkInjectivityFDEqn inj_flags branch_qtvs branch_lhs_tys work_args)
    
    747 739
     
    
    748 740
           | otherwise
    
    749 741
           = Nothing
    
    ... ... @@ -770,6 +762,9 @@ mkLocalFamEqFDs eqs_for_me fam_tc inj_flags work_args work_rhs
    770 762
     
    
    771 763
         mk_eqn iargs = mkInjectivityFDEqn inj_flags [] work_args iargs
    
    772 764
     
    
    765
    +
    
    766
    +{- See Historical Note [trim_qtvs]
    
    767
    +
    
    773 768
     trim_qtvs :: Subst -> [TyVar] -> (Subst, [TyVar])
    
    774 769
     -- Tricky stuff: see (OF1) in Note [Exploiting open type families]
    
    775 770
     trim_qtvs unif_subst qtvs
    
    ... ... @@ -790,7 +785,7 @@ trim_qtvs unif_subst qtvs
    790 785
             subst' = extendTvSubstWithClone subst tv tv'
    
    791 786
                      -- extendTvSubstWithClone: see (OF1b) in
    
    792 787
                      -- Note [Exploiting open type families]
    
    793
    -
    
    788
    +-}
    
    794 789
     
    
    795 790
     -----------------------------------------
    
    796 791
     --  Built-in type families
    
    ... ... @@ -1104,7 +1099,7 @@ the Injective Type Families paper. For open type families, suppose we have
    1104 1099
     
    
    1105 1100
        [W] F alpha ~ Int->Int
    
    1106 1101
     
    
    1107
    -Then, since F has been checked as injective, and the RHS `a->a` (pre-)unifies
    
    1102
    +Then, since F has been checked as injective, and the RHS `a->a` (pre-)matches
    
    1108 1103
     with the `Int->Int` in the Wanted with substitution [a :-> Int], we can
    
    1109 1104
     add a derived FunDepEqns
    
    1110 1105
        FDEqns{ fd_qtvs = [], fd_eqs = [ [Int] ~ alpha ] }
    
    ... ... @@ -1133,36 +1128,44 @@ In general we have:
    1133 1128
       type instance forall qs. F t1 ... tn = rhs
    
    1134 1129
       [W] F a1 ... an ~ b
    
    1135 1130
     
    
    1136
    -Suppose `b` pre-unifies with `rhs`, with substitution `S` that binds
    
    1137
    -some (but perhaps not all) of the `qs`.  Lets say
    
    1138
    -   unbound_qs = qs \ dom(S)
    
    1139
    -
    
    1140
    -Then we generate the FunDepEqs
    
    1141
    -   FDEqns{ fd_qtvs = unbound_qs
    
    1142
    -         , fd_eqs = [ S(t1) ~ S(a1), S(t3) ~ S(a3) ]
    
    1143
    -
    
    1144
    -These 'fd_qtvs' are subsequently instantiated to fresh metavariables by
    
    1145
    -'instantiateFunDepEqns'.
    
    1146
    -
    
    1147
    -(OF1) The computation of `unbound_qs` is done by `trim_qtvs`, but we
    
    1148
    -   have to be careful.   Suppose (OF1a)
    
    1149
    -       qs = [ k::*, a::k ]
    
    1150
    -       S  = [ k :-> UnliftedType ]
    
    1151
    -   Then we want
    
    1152
    -       unbound_qs = [ a::UnliftedType ]    -- Must apply S to q's kind!!
    
    1153
    -
    
    1154
    -   And (OF1b), although I'm not sure if this can acutally happen:
    
    1155
    -        qs = [ k::*, a::(k::*), b::(a::k) ]
    
    1156
    -        S  = [ k :-> UnliftedType ]
    
    1157
    -   We want
    
    1158
    -        unbound_qs = [ a::UnliftedType, b::(a::UnliftedType) ]
    
    1159
    -   Note that the occurrence of `a` in b's kind should be replaced by the
    
    1160
    -   newly-kinded `a` not the original `a::k`.
    
    1161
    -
    
    1162
    -   This fancy footwork for `fd_qtvs` is done by `trim_qtvs`.  It
    
    1163
    -    * Drops a quantified tyvar that /is/ matched
    
    1164
    -    * Substitutes in the kind of a quantified tyvar `a` that is /not/ matched
    
    1165
    -    * Adds the substitution [a::k :-> a::S(k)] to the substitution
    
    1131
    +Suppose `b` pre-matches with `rhs`, with substitution `S`.  We /ignore/
    
    1132
    +`S` and simply generate the FunDepEqs
    
    1133
    +   FDEqns{ fd_qtvs = qs, fd_eqs = [ t1 ~ a1, t3 ~ a3 ]
    
    1134
    +These 'fd_qtvs' are subsequently instantiated to fresh meta-variables by
    
    1135
    +'instantiateFunDepEqns'.  See Historial Note [trim_qtvs].
    
    1136
    +
    
    1137
    +Historial Note [trim_qtvs]
    
    1138
    +~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    1139
    +In Note [Exploiting open type families], we previously tried to make use of
    
    1140
    +the matching substitution `S`, by defining
    
    1141
    +     unbound_qs = qs \ dom(S)
    
    1142
    +so that we could make fresh meta-variables for only the unbound `qs`.
    
    1143
    +But it turned out to be tricky.  Suppose (TQ1)
    
    1144
    +    qs = [ k::*, a::k ]
    
    1145
    +    S  = [ k :-> UnliftedType ]
    
    1146
    +Then we want
    
    1147
    +    unbound_qs = [ a::UnliftedType ]    -- Must apply S to q's kind!!
    
    1148
    +
    
    1149
    +And (TQ2), although I'm not sure if this can acutally happen:
    
    1150
    +     qs = [ k::*, a::(k::*), b::(a::k) ]
    
    1151
    +     S  = [ k :-> UnliftedType ]
    
    1152
    +We want
    
    1153
    +     unbound_qs = [ a::UnliftedType, b::(a::UnliftedType) ]
    
    1154
    +Note that the occurrence of `a` in b's kind should be replaced by the
    
    1155
    +newly-kinded `a` not the original `a::k`.
    
    1156
    +
    
    1157
    +This fancy footwork for `fd_qtvs` used to be done by `trim_qtvs`.  It
    
    1158
    + * Drops a quantified tyvar that /is/ matched
    
    1159
    + * Substitutes in the kind of a quantified tyvar `a` that is /not/ matched
    
    1160
    + * Adds the substitution [a::k :-> a::S(k)] to the substitution
    
    1161
    +
    
    1162
    +(TQ3) This was hard enough for open type type families, which use matching.
    
    1163
    +But it was ridiculously hard for /closed/ type families which use pre-/unification/
    
    1164
    +so that the substitution `S` has both meta-tyvars and instance-head tyvars in
    
    1165
    +the range.
    
    1166
    +
    
    1167
    +It's much easier to drop all this and just make fresh meta-tyvars for
    
    1168
    +all the quantified type variables.
    
    1166 1169
     
    
    1167 1170
     Note [Exploiting closed type families] see `mkTopClosedFamEqFDs`
    
    1168 1171
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    ... ... @@ -1194,9 +1197,6 @@ More precisely, here is the very clever Closed Family Fundep Algorithm (CFFA)
    1194 1197
         with fresh unification vars in lhs and rhs for the quantified variables of the
    
    1195 1198
         equation.
    
    1196 1199
     
    
    1197
    -    Actually we take advantage of the substitution generated by the relevance
    
    1198
    -    check, see (CF7) below.
    
    1199
    -
    
    1200 1200
     See Note [Relevance] for what "relevant" means.
    
    1201 1201
     We need to take care about non-termination; see (CF3).
    
    1202 1202
     
    
    ... ... @@ -1391,13 +1391,29 @@ Key point: equations that are not relevant do not need to be considered for fund
    1391 1391
     (CF7) Relevance.  When computing relevance in the Closed Family Fundep Algorithm,
    
    1392 1392
       for [W] F wlhs1 wlhs2 ~ wrhs, against an equation   F lhs1 lhs2 ~ rhs
    
    1393 1393
       we get back a pre-unifying substitution S that makes the two as equal as poss.
    
    1394
    -  Then we use `trim_qtvs` in exactly the same way as in
    
    1395
    -       (OF1) of Note [Exploiting open type families], to generate qtvs' and S'
    
    1396
    -  Then we generate
    
    1397
    -      FDEqns { fd_qtvs = qtvs', fd_eqs [ S'(lhs1) ~ wlhs1
    
    1398
    -                                       , S'(lhs2) ~ wlhs2
    
    1399
    -                                       , S'(rhs)  ~ wrhs ] }
    
    1400
    -  Notice that we do /not/ apply S' to wlhs/wrhs.  These type contain unification
    
    1394
    +  This substitution can bind both /quantified/ type variables from the instance,
    
    1395
    +  and /unification variables/ from the solver. Moreover, both kind of type variable
    
    1396
    +  can appear in the range of the substitution.
    
    1397
    +
    
    1398
    +  That's pretty complicated, so we are very cautious about using the returned
    
    1399
    +  substitution.  I had a long stuggle (#27994) when we were previously trying to
    
    1400
    +  apply that returned substitution as an optimisation.  But because type variables
    
    1401
    +  can occur in kinds, it was a losing battle -- I ended up with TyVars from the
    
    1402
    +  instance head escaping into the solver.   Consider
    
    1403
    +
    
    1404
    +      type F :: forall k. k -> *
    
    1405
    +      type instance F k a where
    
    1406
    +         F (k->*) (b::k->*) = Int
    
    1407
    +
    
    1408
    +      [W] F kappa (alpha::kappa) ~ Int
    
    1409
    +
    
    1410
    +  We unify the Wanted with the equation to get the subsitution
    
    1411
    +      [ kappa :-> k->*,  b :-> alpha ]
    
    1412
    +  I tried using `trim_qtvs` (see Historical Note [trim_qtvs]) but my head hurt
    
    1413
    +  FAR too much: #27994 is an excellent example.  I gave up and now just ignore
    
    1414
    +  the substitution, making a fresh meta-var for each quantified variable.
    
    1415
    +
    
    1416
    +(CF8)  Notice that we do /not/ apply S' to wlhs/wrhs.  These type contain unification
    
    1401 1417
       variables that we must actually unify! Example
    
    1402 1418
          type family F a b where
    
    1403 1419
            F [a] (Maybe b) = (a,  G b)
    
    ... ... @@ -1408,7 +1424,6 @@ Key point: equations that are not relevant do not need to be considered for fund
    1408 1424
          FDEqns { fd_qtvs = [b], fd_eqs [ [Int] ~ alpha
    
    1409 1425
                                         , Maybe b ~ beta
    
    1410 1426
                                         , (Int,G b) ~ (Int, [gamma]) ] }
    
    1411
    -
    
    1412 1427
       Notice also that by applying the substitution to the template but not to the
    
    1413 1428
       Wanted, we uphold the `fd_eqs` invariant in `FDEqns` (see its data type decl)
    
    1414 1429
     
    
    ... ... @@ -1517,10 +1532,12 @@ instantiateFunDepEqns (FDEqns { fd_qtvs = qtvs, fd_eqs = eqs })
    1517 1532
         rev_eqs = reverse eqs
    
    1518 1533
            -- (reverse eqs): See Note [Reverse order of fundep equations]
    
    1519 1534
     
    
    1535
    +    empty_subst = emptySubst
    
    1536
    +    -- If you re-instate `trim_qtvs`, take care here:
    
    1520 1537
         -- The kinds of `qtvs` can have free variables, because of `trim_qtvs`
    
    1521 1538
         -- Example: T27828b
    
    1522
    -    empty_subst = mkEmptySubst $ mkInScopeSet $
    
    1523
    -                  tyCoVarsOfTypes (map tyVarKind qtvs)
    
    1539
    +    -- empty_subst = mkEmptySubst $ mkInScopeSet $
    
    1540
    +    --              tyCoVarsOfTypes (map tyVarKind qtvs)
    
    1524 1541
     
    
    1525 1542
         subst_pair subst (Pair ty1 ty2)
    
    1526 1543
            = Pair (substTy subst' ty1) ty2
    

  • compiler/GHC/Tc/Utils/Unify.hs
    ... ... @@ -61,7 +61,6 @@ import GHC.Prelude
    61 61
     
    
    62 62
     import GHC.Hs
    
    63 63
     import GHC.Tc.Errors.Types ( HsCtxt(..) )
    
    64
    -import GHC.Tc.Errors.Ppr   ( pprHsCtxt )
    
    65 64
     import GHC.Tc.Utils.Concrete
    
    66 65
     import GHC.Tc.Utils.Env
    
    67 66
     import GHC.Tc.Utils.Instantiate
    
    ... ... @@ -2801,17 +2800,15 @@ uType_defer (UE { u_loc = loc, u_defer = ref
    2801 2800
              -- snocBag: see Note [Work-list ordering] in GHC.Tc.Solver.Equality
    
    2802 2801
     
    
    2803 2802
            -- Error trace only
    
    2804
    -       -- NB. do *not* call tidyErrCtxt unless tracing is on,
    
    2805
    -       --     because it is hugely expensive (#5631)
    
    2803
    +       -- NB. do *not* call tidyErrCtxt because
    
    2804
    +       -- (a) it is hugely expensive (#5631) and
    
    2805
    +       -- (b) it crashes in some cases because because it reads
    
    2806
    +       --     res_ty too early via FunResCtxt and getCheckExpType
    
    2806 2807
            ; whenDOptM Opt_D_dump_tc_trace $
    
    2807
    -         do { ctxt     <- getErrCtxt
    
    2808
    -            ; err_ctxt <- tidyErrCtxt emptyTidyEnv ctxt
    
    2809
    -            ; traceTc "utype_defer" $
    
    2810
    -                vcat ( ppr role
    
    2811
    -                     : debugPprType ty1
    
    2812
    -                     : debugPprType ty2
    
    2813
    -                     : map pprHsCtxt err_ctxt )
    
    2814
    -            ; traceTc "utype_defer2" (ppr co) }
    
    2808
    +         traceTc "utype_defer" $
    
    2809
    +                vcat [ text "role:" <+> ppr role
    
    2810
    +                     , text "ty1:" <+> debugPprType ty1
    
    2811
    +                     , text "ty2:" <+> debugPprType ty2 ]
    
    2815 2812
     
    
    2816 2813
            ; return co }
    
    2817 2814
     
    

  • testsuite/tests/typecheck/should_compile/T27994.hs
    1
    +{-# LANGUAGE AllowAmbiguousTypes #-}
    
    2
    +{-# LANGUAGE DataKinds #-}
    
    3
    +{-# LANGUAGE FunctionalDependencies #-}
    
    4
    +{-# LANGUAGE GADTs #-}
    
    5
    +{-# LANGUAGE TypeFamilies #-}
    
    6
    +module  T27994 (l2) where
    
    7
    +
    
    8
    +import Data.Kind (Constraint, Type)
    
    9
    +
    
    10
    +l1 :: [String]
    
    11
    +l1 = ["hello", "world!"]
    
    12
    +
    
    13
    +l2 :: [Int]
    
    14
    +l2 = gmap (HCons length HNil) l1
    
    15
    +
    
    16
    +-----
    
    17
    +
    
    18
    +type HList :: [Type] -> Type
    
    19
    +data HList p where
    
    20
    +  HNil :: HList '[]
    
    21
    +  HCons :: x -> HList xs -> HList (x:xs)
    
    22
    +
    
    23
    +type ($$) :: k -> [Type] -> Type
    
    24
    +type family s $$ p where
    
    25
    +  (s :: Type)      $$ '[]   = s
    
    26
    +  (s :: Type -> k) $$ (a:b) = s a $$ b
    
    27
    +
    
    28
    +type Doms :: [Type] -> [Type]
    
    29
    +type family Doms t where
    
    30
    +  Doms '[]            = '[]
    
    31
    +  Doms ((a -> b) : t) = a : Doms t
    
    32
    +
    
    33
    +type Codoms :: [Type] -> [Type]
    
    34
    +type family Codoms t where
    
    35
    +  Codoms '[]            = '[]
    
    36
    +  Codoms ((a -> b) : t) = b : Codoms t
    
    37
    +
    
    38
    +type GMap :: k -> [Type] -> Constraint
    
    39
    +class GMap (s :: k) t | t -> k where
    
    40
    +  gmap :: HList t -> s $$ Doms t -> s $$ Codoms t
    
    41
    +
    
    42
    +instance GMap [] '[a -> b] where
    
    43
    +  gmap :: HList '[a -> b] -> [a] -> [b]
    
    44
    +  gmap (HCons f HNil) = go
    
    45
    +    where
    
    46
    +      go :: [a] -> [b]
    
    47
    +      go []     = []
    
    48
    +      go (x:xs) = f x : go xs

  • testsuite/tests/typecheck/should_compile/T27994a.hs
    1
    +{-# LANGUAGE DataKinds, TypeFamilies, PolyKinds, GADTs, AllowAmbiguousTypes #-}
    
    2
    +module T27994 where
    
    3
    +
    
    4
    +import Data.Kind (Type)
    
    5
    +import Data.Proxy (Proxy)
    
    6
    +
    
    7
    +type F :: forall{k}. k -> Type -> Type
    
    8
    +type family F s x where
    
    9
    +   F (s :: Type -> k) (Proxy s) = Int
    
    10
    +
    
    11
    +f :: forall k (s :: k) x. F s x -> x
    
    12
    +f _ = undefined
    
    13
    +
    
    14
    +g :: Proxy Maybe -> ()
    
    15
    +g _ = ()
    
    16
    +
    
    17
    +data T a where
    
    18
    +  MkT :: T Int
    
    19
    +
    
    20
    +test :: T a -> ()
    
    21
    +test t = (\y -> case t of MkT -> g y) (f (3 :: Int))
    
    22
    +
    
    23
    +{- [W] F @k_azX (s_azY::k_azX) p_azN ~ Int
    
    24
    +
    
    25
    +unify   [*->k,      s::*->k,  Proxy @(*->k) (s::*->k), Int]
    
    26
    +          ~ [k_azX, s_azY::k_azX, p_azN,                   Int]
    
    27
    +
    
    28
    +  -->   [ k_azX :-> (* -> k)
    
    29
    +        , s     :-> s_azY::k_azX
    
    30
    +        , p_azN :-> Proxy @(*->k) (s::*->k) ]
    
    31
    +
    
    32
    +  fixpt -->   [ k_azX :-> Type -> k
    
    33
    +              , s     :-> s_azY::(Type -> k)
    
    34
    +              , p_azN :-> Proxy @(Type->k) (s::k_azX) ]
    
    35
    +
    
    36
    +Generate a [W] for each pair
    
    37
    +    [W] k ~ k_azX
    
    38
    +    [W] s ~ s_azY
    
    39
    +    [W] Proxy s ~ p_azN
    
    40
    +    [W] Int ~ Int
    
    41
    +As an opt (claim) apply subst first
    
    42
    +    [W] k_azX ~ k_azX
    
    43
    +    [W] s_azY ~ s_azY
    
    44
    +    [W] Proxy s_azY ~ p_azN
    
    45
    +    [W] Int ~ Int
    
    46
    +
    
    47
    +-- [W] F @k_azX s_azY[tau] p_azN ~ Int
    
    48
    +-- Want: fresh k' s'
    
    49
    +-- [W] k' ~ k_azX
    
    50
    +-- [W] s':k' ~ s_azY:k_azX
    
    51
    +-- [W] Proxy s' ~ x
    
    52
    +-}
    
    53
    +

  • testsuite/tests/typecheck/should_compile/all.T
    ... ... @@ -972,4 +972,6 @@ test('T27557', normal, compile, [''])
    972 972
     test('T27664', normal, compile, [''])
    
    973 973
     test('T27916', normal, compile, [''])
    
    974 974
     test('T26543_orig', normal, compile, [''])
    
    975
    +test('T7994', normal, compile, [''])
    
    976
    +test('T7994a', normal, compile, [''])
    
    975 977