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

Commits:

1 changed file:

Changes:

  • compiler/GHC/Core/Unify.hs
    ... ... @@ -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
     ************************************************************************