Simon Peyton Jones pushed to branch wip/T27994 at Glasgow Haskell Compiler / GHC
Commits:
-
1d55c7c2
by Simon Peyton Jones at 2026-10-21T11:28:06+01:00
-
2f218858
by Simon Peyton Jones at 2026-10-21T11:28:39+01:00
8 changed files:
- compiler/GHC/Core/Predicate.hs
- compiler/GHC/Core/TyCo/FVs.hs
- compiler/GHC/Core/Unify.hs
- compiler/GHC/Tc/Solver/FunDeps.hs
- compiler/GHC/Tc/Utils/Unify.hs
- + testsuite/tests/typecheck/should_compile/T27994.hs
- + testsuite/tests/typecheck/should_compile/T27994a.hs
- testsuite/tests/typecheck/should_compile/all.T
Changes:
| ... | ... | @@ -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
|
| ... | ... | @@ -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 | * *
|
| ... | ... | @@ -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 | ************************************************************************
|
| ... | ... | @@ -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
|
| ... | ... | @@ -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 |
| 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 |
| 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 | + |
| ... | ... | @@ -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 |