| ... |
... |
@@ -33,9 +33,8 @@ 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
|
+import GHC.Core.TyCo.FVs( anyShallowFreeVarsOfType )
|
|
37
|
37
|
import GHC.Core.TyCo.Compare ( eqType, tcEqType, tcEqTyConAppArgs )
|
|
38
|
|
-import qualified GHC.Core.TyCo.Subst as S
|
|
39
|
38
|
import GHC.Core.TyCo.Subst ( mkTvSubst )
|
|
40
|
39
|
import GHC.Core.Map.Type
|
|
41
|
40
|
import GHC.Core.Multiplicity
|
| ... |
... |
@@ -1071,15 +1070,16 @@ unification is much trickier than it looks, because of kinds. Consider |
|
1071
|
1070
|
If we unify, we get the substitution
|
|
1072
|
1071
|
[ k -> *
|
|
1073
|
1072
|
, g -> H k (f:k) ]
|
|
|
1073
|
+This isn't idempotent: it mentions `k` in the range.
|
|
|
1074
|
+
|
|
1074
|
1075
|
To make it idempotent we don't want to get just
|
|
1075
|
1076
|
[ k -> *
|
|
1076
|
1077
|
, g -> H * (f:k) ]
|
|
1077
|
|
-We also want to substitute inside f's kind, to get
|
|
1078
|
|
- [ k -> *
|
|
1079
|
|
- , g -> H k (f:*) ]
|
|
1080
|
|
-If we don't do this, we may apply the substitution to something,
|
|
1081
|
|
-and get an ill-formed type, i.e. one where typeKind will fail.
|
|
|
1078
|
+because (H * (f:k)) is itself ill-kinded, and `typeKind` will fail.
|
|
1082
|
1079
|
This happened, for example, in #9106.
|
|
|
1080
|
+So (yuckily) we must also substitute inside f's kind, to get
|
|
|
1081
|
+ [ k -> *
|
|
|
1082
|
+ , g -> H * (f:*) ]
|
|
1083
|
1083
|
|
|
1084
|
1084
|
It gets worse. In #14164 we wanted to take the fixpoint of
|
|
1085
|
1085
|
this substitution
|
| ... |
... |
@@ -1094,42 +1094,41 @@ probably rightly so). |
|
1094
|
1094
|
|
|
1095
|
1095
|
Ugh! This whole thing is pretty horrible. We work as follows:
|
|
1096
|
1096
|
|
|
1097
|
|
- 1. Start with the current substitution (which we are
|
|
1098
|
|
- trying to fixpoint
|
|
1099
|
|
- [ xs :-> F a (z :: a) (rest :: G a (z :: a))
|
|
1100
|
|
- , a :-> b ]
|
|
1101
|
|
-
|
|
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 ]
|
|
|
1097
|
+ 1. Start with the current substitution S, which we are fixpointing
|
|
|
1098
|
+ S = [ xs :-> F a (z :: a) (rest :: G a (z :: a))
|
|
|
1099
|
+ , a :-> (b::*) ]
|
|
1105
|
1100
|
Note the 'a' lurking inside (z::a)
|
|
1106
|
1101
|
|
|
1107
|
|
- 3. Take all the deep free vars of the range of the substitution:
|
|
1108
|
|
- {a, (z::a), (rest::G a z), b}
|
|
|
1102
|
+ 2. Find `range_tvs`, the deep free vars of the range of the substitution:
|
|
|
1103
|
+ range_tvs = {a, (z::a), (rest::G a z), b}
|
|
1109
|
1104
|
|
|
1110
|
|
- 4. Remove the variables that are bound by the substitution, leaving
|
|
1111
|
|
- {z, rest, b}
|
|
|
1105
|
+ 3. If none of the `range_tvs` are in the domain of the substitution, stop.
|
|
1112
|
1106
|
|
|
1113
|
|
- 5. Do a `scopedSort` to put them in dependency order:
|
|
1114
|
|
- [ b :: *, z :: a, rest :: G a z ]
|
|
|
1107
|
+ 4. Find `free_tvs`, the `range_tvs` that are NOT in the substitution domain
|
|
|
1108
|
+ and used `scopedSort` to put them in dependency order:
|
|
|
1109
|
+ free_tvs = [z::a, rest::G a z, b]
|
|
1115
|
1110
|
|
|
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
|
|
- , z :-> z :: b
|
|
1121
|
|
- , rest :-> rest :: G b (z :: b) ]
|
|
1122
|
|
- Note that rest now has the right kind
|
|
|
1111
|
+ 5. Extend the substitution with "re-kinding bindings", mapping each free_tv
|
|
|
1112
|
+ to the self-same variable, but with the original substitution applied
|
|
|
1113
|
+ to its kind.
|
|
|
1114
|
+ S_plus_rekinding = S + [ z :-> z::b
|
|
|
1115
|
+ , rest :-> rest::G b (z::b)
|
|
|
1116
|
+ , b :-> b]
|
|
|
1117
|
+ Here we see the reason for putting `free_tvs` in dependency order:
|
|
|
1118
|
+ we want the new kind of `rest` to be well-kinded, not (G b (z:a)).
|
|
|
1119
|
+ S_plus_rekinding = S + [ z :-> z::b
|
|
|
1120
|
+ , rest :-> rest::G b (z::b) ]
|
|
1123
|
1121
|
|
|
1124
|
|
- 7. Apply this extended substitution (once) to the range of the
|
|
1125
|
|
- fixpoint substitution from (2).
|
|
|
1122
|
+ Optimisation: if the kind of a free_tvs is a fixpoint of the substitution,
|
|
|
1123
|
+ no need to add it to the substitution. So we get
|
|
1126
|
1124
|
|
|
1127
|
|
-In Step 6 we use the free vars from Step 2 as the initial
|
|
1128
|
|
-in-scope set, because all of those variables appear in the
|
|
1129
|
|
-range of the substitution, so they must all be in the in-scope
|
|
1130
|
|
-set. But NB that the type substitution engine does not look up
|
|
1131
|
|
-variables in the in-scope set; it is used only to ensure no
|
|
1132
|
|
-shadowing.
|
|
|
1125
|
+ 6. Apply S_plus_rekinding to the range of S
|
|
|
1126
|
+ S_new = [ xs :-> F b (z::b) (rest::G b (z::b))
|
|
|
1127
|
+ , a :-> b ]
|
|
|
1128
|
+
|
|
|
1129
|
+ 7. Loop back to (2)
|
|
|
1130
|
+
|
|
|
1131
|
+In our example, the substitution is now a fixpoint.
|
|
1133
|
1132
|
-}
|
|
1134
|
1133
|
|
|
1135
|
1134
|
niFixSubst, niFixSubst' :: InScopeSet -> TvSubstEnv -> Subst
|
| ... |
... |
@@ -1147,88 +1146,38 @@ niFixSubst in_scope tenv |
|
1147
|
1146
|
where
|
|
1148
|
1147
|
subst = niFixSubst' in_scope tenv
|
|
1149
|
1148
|
|
|
1150
|
|
-niFixSubst' in_scope orig_tenv
|
|
1151
|
|
- = mkTvSubst in_scope (mapVarEnv (subst_tenv rekinding_tenv) fix_tenv)
|
|
1152
|
|
- where
|
|
1153
|
|
- in_dom tv = tv `elemVarEnv` orig_tenv
|
|
1154
|
|
-
|
|
1155
|
|
- fix_tenv :: TvSubstEnv
|
|
1156
|
|
- fix_tenv = go_fix orig_tenv -- Repeatedly apply tenv until we get a fixpoint
|
|
1157
|
|
-
|
|
1158
|
|
- go_fix tenv_so_far
|
|
1159
|
|
- | anyVarEnv (anyShallowFreeVarsOfType in_dom) tenv_so_far
|
|
1160
|
|
- = go_fix (mapVarEnv (subst_tenv tenv_so_far) tenv_so_far)
|
|
1161
|
|
- | otherwise
|
|
1162
|
|
- = tenv_so_far
|
|
1163
|
|
-
|
|
1164
|
|
- free_tvs :: [TyVar]
|
|
1165
|
|
- free_tvs = scopedSort $
|
|
1166
|
|
- filterOut in_dom $
|
|
1167
|
|
- nonDetVarSetElems $
|
|
1168
|
|
- tyCoVarsOfTypes $
|
|
1169
|
|
- nonDetEltsUFM fix_tenv
|
|
1170
|
|
- -- It's OK to use nonDetEltsUFM (twice) here because
|
|
1171
|
|
- -- the exact order of free_tvs is immaterial
|
|
1172
|
|
-
|
|
1173
|
|
- rekinding_tenv = foldl' add_free_tv emptyTvSubstEnv free_tvs
|
|
1174
|
|
-
|
|
1175
|
|
- add_free_tv :: TvSubstEnv -> TyVar -> TvSubstEnv
|
|
1176
|
|
- add_free_tv rke_so_far tv
|
|
1177
|
|
- | isTyVar tv
|
|
1178
|
|
- , let k' = subst_tenv rke_so_far $
|
|
1179
|
|
- subst_tenv fix_tenv $
|
|
1180
|
|
- tyVarKind tv
|
|
1181
|
|
- = extendVarEnv rke_so_far tv (mkTyVarTy (setTyVarKind tv k'))
|
|
1182
|
|
- | otherwise
|
|
1183
|
|
- = rke_so_far
|
|
1184
|
|
-
|
|
1185
|
|
- subst_tenv :: TvSubstEnv -> Type -> Type
|
|
1186
|
|
- subst_tenv tenv = substTy (mkTvSubst in_scope tenv)
|
|
1187
|
|
-
|
|
1188
|
|
-{-
|
|
1189
|
|
--- | not_fixpoint = niFixSubst' in_scope (mapVarEnv (substTy subst) tenv)
|
|
1190
|
|
- | not_fixpoint = niFixSubst' in_scope (mapVarEnv (substTy subst) tenv)
|
|
1191
|
|
- | otherwise = tenv_subst
|
|
|
1149
|
+niFixSubst' in_scope tenv_orig
|
|
|
1150
|
+ | not (any in_dom range_tvs) = mkTvSubst in_scope tenv_orig
|
|
|
1151
|
+ | otherwise = niFixSubst' in_scope tenv_new
|
|
1192
|
1152
|
where
|
|
1193
|
|
- tenv_subst = mkTvSubst in_scope tenv -- This is our starting point
|
|
|
1153
|
+ in_dom tv = tv `elemVarEnv` tenv_orig
|
|
1194
|
1154
|
|
|
1195
|
1155
|
range_tvs :: [TyVar]
|
|
1196
|
1156
|
range_tvs = nonDetVarSetElems $
|
|
1197
|
1157
|
tyCoVarsOfTypes $
|
|
1198
|
|
- nonDetEltsUFM tenv
|
|
|
1158
|
+ nonDetEltsUFM tenv_orig
|
|
1199
|
1159
|
-- It's OK to use nonDetEltsUFM (twice) here because
|
|
1200
|
1160
|
-- the order of range_tvs is immaterial
|
|
1201
|
1161
|
|
|
1202
|
|
- not_fixpoint = any in_domain range_tvs
|
|
1203
|
|
- in_domain tv = tv `elemVarEnv` tenv
|
|
1204
|
|
- free_tvs = scopedSort (filterOut in_domain range_tvs)
|
|
|
1162
|
+ free_tvs = scopedSort (filterOut in_dom range_tvs)
|
|
|
1163
|
+
|
|
|
1164
|
+ tenv_plus_rekinding = foldl' add_free_tv tenv_orig free_tvs
|
|
|
1165
|
+ tenv_new = mapVarEnv (subst_tenv tenv_plus_rekinding) tenv_orig
|
|
1205
|
1166
|
|
|
1206
|
|
- -- See Note [Finding the substitution fixpoint], Step 6
|
|
1207
|
|
- rekinding_tenv = foldl' add_free_tv emptyTvSubstEnv free_tvs
|
|
1208
|
1167
|
add_free_tv :: TvSubstEnv -> TyVar -> TvSubstEnv
|
|
1209
|
|
- add_free_tv rke tv
|
|
1210
|
|
- | isTyVar tv, anyFreeVarsOfType in_domain (varType tv)
|
|
1211
|
|
- , let tv' = updateTyVarKind (substTy tenv_subst) tv
|
|
1212
|
|
- = extendVarEnv rke tv (mkTyVarTy tv')
|
|
|
1168
|
+ add_free_tv so_far tv
|
|
|
1169
|
+ | isTyVar tv
|
|
|
1170
|
+ , let kind = tyVarKind tv
|
|
|
1171
|
+ , anyShallowFreeVarsOfType (`elemVarEnv` so_far) kind
|
|
|
1172
|
+ -- Shallow free vars because substitution is shallow
|
|
|
1173
|
+ = extendVarEnv so_far tv $ mkTyVarTy $
|
|
|
1174
|
+ setTyVarKind tv $ subst_tenv so_far kind
|
|
1213
|
1175
|
| otherwise
|
|
1214
|
|
- = rke
|
|
1215
|
|
-
|
|
1216
|
|
- rekinding_subst = mkTvSubst in_scope rekinding_tenv
|
|
|
1176
|
+ = so_far
|
|
1217
|
1177
|
|
|
1218
|
|
- subst = mkTvSubst in_scope (rekinding_tenv `plusVarEnv`
|
|
1219
|
|
- mapVarEnv (substTy rekinding_subst) tenv)
|
|
1220
|
|
-
|
|
1221
|
|
-{-
|
|
1222
|
|
- subst = foldl' add_free_tv tenv_subst free_tvs
|
|
|
1178
|
+ subst_tenv :: TvSubstEnv -> Type -> Type
|
|
|
1179
|
+ subst_tenv tenv = substTy (mkTvSubst in_scope tenv)
|
|
1223
|
1180
|
|
|
1224
|
|
- add_free_tv :: Subst -> TyVar -> Subst
|
|
1225
|
|
- add_free_tv subst tv
|
|
1226
|
|
- | isTyVar tv = extendTvSubst subst tv (mkTyVarTy tv')
|
|
1227
|
|
- | otherwise = subst -- Ignore free coercion variables
|
|
1228
|
|
- where
|
|
1229
|
|
- tv' = updateTyVarKind (substTy subst) tv
|
|
1230
|
|
--}
|
|
1231
|
|
--}
|
|
1232
|
1181
|
|
|
1233
|
1182
|
{-
|
|
1234
|
1183
|
************************************************************************
|