Substantial improvements to coercion optimisation
[ghc.git] / compiler / types / Unify.lhs
index d13a32b..a9586b6 100644 (file)
@@ -3,13 +3,6 @@
 %
 
 \begin{code}
-{-# OPTIONS -w #-}
--- The above warning supression flag is a temporary kludge.
--- While working on this module you are encouraged to remove it and fix
--- any warnings in the module. See
---     http://hackage.haskell.org/trac/ghc/wiki/CodingStyle#Warnings
--- for details
-
 module Unify ( 
        -- Matching of types: 
        --      the "tc" prefix indicates that matching always
@@ -17,7 +10,15 @@ module Unify (
        tcMatchTy, tcMatchTys, tcMatchTyX, 
        ruleMatchTyX, tcMatchPreds, MatchEnv(..),
        
-       dataConCannotMatch
+       dataConCannotMatch,
+
+        -- GADT type refinement
+       Refinement, emptyRefinement, isEmptyRefinement, 
+       matchRefine, refineType, refinePred, refineResType,
+
+        -- Side-effect free unification
+        tcUnifyTys, BindFlag(..)
+
    ) where
 
 #include "HsVersions.h"
@@ -26,12 +27,16 @@ import Var
 import VarEnv
 import VarSet
 import Type
+import Coercion
 import TyCon
 import DataCon
 import TypeRep
 import Outputable
+import ErrUtils
 import Util
 import Maybes
+import UniqFM
+import FastString
 \end{code}
 
 
@@ -145,35 +150,32 @@ match :: MatchEnv -- For the most part this is pushed downwards
                        --      in-scope set of the RnEnv2
       -> Type -> Type  -- Template and target respectively
       -> Maybe TvSubstEnv
--- This matcher works on source types; that is, 
--- it respects NewTypes and PredType
+-- This matcher works on core types; that is, it ignores PredTypes
+-- Watch out if newtypes become transparent agin!
+--     this matcher must respect newtypes
 
-match menv subst ty1 ty2 | Just ty1' <- tcView ty1 = match menv subst ty1' ty2
-                         | Just ty2' <- tcView ty2 = match menv subst ty1 ty2'
+match menv subst ty1 ty2 | Just ty1' <- coreView ty1 = match menv subst ty1' ty2
+                        | Just ty2' <- coreView ty2 = match menv subst ty1 ty2'
 
 match menv subst (TyVarTy tv1) ty2
+  | Just ty1' <- lookupVarEnv subst tv1'       -- tv1' is already bound
+  = if tcEqTypeX (nukeRnEnvL rn_env) ty1' ty2
+       -- ty1 has no locally-bound variables, hence nukeRnEnvL
+       -- Note tcEqType...we are doing source-type matching here
+    then Just subst
+    else Nothing       -- ty2 doesn't match
+
   | tv1' `elemVarSet` me_tmpls menv
-  = case lookupVarEnv subst tv1' of
-       Nothing         -- No existing binding
-           | any (inRnEnvR rn_env) (varSetElems (tyVarsOfType ty2))
-           -> Nothing  -- Occurs check
-           | not (typeKind ty2 `isSubKind` tyVarKind tv1)
-           -> Nothing  -- Kind mis-match
-           | otherwise
-           -> Just (extendVarEnv subst tv1' ty2)
-
-       Just ty1'       -- There is an existing binding; check whether ty2 matches it
-           | tcEqTypeX (nukeRnEnvL rn_env) ty1' ty2
-               -- ty1 has no locally-bound variables, hence nukeRnEnvL
-               -- Note tcEqType...we are doing source-type matching here
-           -> Just subst
-           | otherwise -> Nothing      -- ty2 doesn't match
-           
+  = if any (inRnEnvR rn_env) (varSetElems (tyVarsOfType ty2))
+    then Nothing       -- Occurs check
+    else do { subst1 <- match_kind menv subst tv1 ty2
+                       -- Note [Matching kinds]
+           ; return (extendVarEnv subst1 tv1' ty2) }
 
    | otherwise -- tv1 is not a template tyvar
    = case ty2 of
        TyVarTy tv2 | tv1' == rnOccR rn_env tv2 -> Just subst
-       other                                   -> Nothing
+       _                                       -> Nothing
   where
     rn_env = me_env menv
     tv1' = rnOccL rn_env tv1
@@ -196,26 +198,55 @@ match menv subst (AppTy ty1a ty1b) ty2
   = do { subst' <- match menv subst ty1a ty2a
        ; match menv subst' ty1b ty2b }
 
-match menv subst ty1 ty2
+match _ _ _ _
   = Nothing
 
 --------------
+match_kind :: MatchEnv -> TvSubstEnv -> TyVar -> Type -> Maybe TvSubstEnv
+-- Match the kind of the template tyvar with the kind of Type
+-- Note [Matching kinds]
+match_kind menv subst tv ty
+  | isCoVar tv = do { let (ty1,ty2) = coVarKind tv
+                         (ty3,ty4) = coercionKind ty
+                   ; subst1 <- match menv subst ty1 ty3
+                   ; match menv subst1 ty2 ty4 }
+  | otherwise  = if typeKind ty `isSubKind` tyVarKind tv
+                then Just subst
+                else Nothing
+
+-- Note [Matching kinds]
+-- ~~~~~~~~~~~~~~~~~~~~~
+-- For ordinary type variables, we don't want (m a) to match (n b) 
+-- if say (a::*) and (b::*->*).  This is just a yes/no issue. 
+--
+-- For coercion kinds matters are more complicated.  If we have a 
+-- coercion template variable co::a~[b], where a,b are presumably also
+-- template type variables, then we must match co's kind against the 
+-- kind of the actual argument, so as to give bindings to a,b.  
+--
+-- In fact I have no example in mind that *requires* this kind-matching
+-- to instantiate template type variables, but it seems like the right
+-- thing to do.  C.f. Note [Matching variable types] in Rules.lhs
+
+--------------
+match_tys :: MatchEnv -> TvSubstEnv -> [Type] -> [Type] -> Maybe TvSubstEnv
 match_tys menv subst tys1 tys2 = match_list (match menv) subst tys1 tys2
 
 --------------
 match_list :: (TvSubstEnv -> a -> a -> Maybe TvSubstEnv)
           -> TvSubstEnv -> [a] -> [a] -> Maybe TvSubstEnv
-match_list fn subst []         []        = Just subst
+match_list _  subst []         []         = Just subst
 match_list fn subst (ty1:tys1) (ty2:tys2) = do { subst' <- fn subst ty1 ty2
                                                ; match_list fn subst' tys1 tys2 }
-match_list fn subst tys1       tys2      = Nothing     
+match_list _  _     _          _          = Nothing
 
 --------------
+match_pred :: MatchEnv -> TvSubstEnv -> PredType -> PredType -> Maybe TvSubstEnv
 match_pred menv subst (ClassP c1 tys1) (ClassP c2 tys2)
   | c1 == c2 = match_tys menv subst tys1 tys2
 match_pred menv subst (IParam n1 t1) (IParam n2 t2)
   | n1 == n2 = match menv subst t1 t2
-match_pred menv subst p1 p2 = Nothing
+match_pred _    _     _ _ = Nothing
 \end{code}
 
 
@@ -334,10 +365,417 @@ dataConCannotMatch tys con
        | Just (f1, a1) <- repSplitAppTy_maybe ty1
        = cant_match f1 f2 || cant_match a1 a2
 
-    cant_match ty1 ty2 = False -- Safe!
+    cant_match _ _ = False      -- Safe!
 
 -- Things we could add;
 --     foralls
 --     look through newtypes
 --     take account of tyvar bindings (EQ example above)
-\end{code}
\ No newline at end of file
+\end{code}
+
+
+%************************************************************************
+%*                                                                     *
+               What a refinement is
+%*                                                                     *
+%************************************************************************
+
+\begin{code}
+data Refinement = Reft InScopeSet InternalReft 
+
+type InternalReft = TyVarEnv (Coercion, Type)
+-- INVARIANT:   a->(co,ty)   then   co :: (a~ty)
+-- Not necessarily idemopotent
+
+instance Outputable Refinement where
+  ppr (Reft _in_scope env)
+    = ptext (sLit "Refinement") <+>
+        braces (ppr env)
+
+emptyRefinement :: Refinement
+emptyRefinement = (Reft emptyInScopeSet emptyVarEnv)
+
+isEmptyRefinement :: Refinement -> Bool
+isEmptyRefinement (Reft _ env) = isEmptyVarEnv env
+
+refineType :: Refinement -> Type -> Maybe (Coercion, Type)
+-- Apply the refinement to the type.
+-- If (refineType r ty) = (co, ty')
+-- Then co :: ty~ty'
+-- Nothing => the refinement does nothing to this type
+refineType (Reft in_scope env) ty
+  | not (isEmptyVarEnv env),           -- Common case
+    any (`elemVarEnv` env) (varSetElems (tyVarsOfType ty))
+  = Just (substTy co_subst ty, substTy tv_subst ty)
+  | otherwise
+  = Nothing    -- The type doesn't mention any refined type variables
+  where
+    tv_subst = mkTvSubst in_scope (mapVarEnv snd env)
+    co_subst = mkTvSubst in_scope (mapVarEnv fst env)
+refinePred :: Refinement -> PredType -> Maybe (Coercion, PredType)
+refinePred (Reft in_scope env) pred
+  | not (isEmptyVarEnv env),           -- Common case
+    any (`elemVarEnv` env) (varSetElems (tyVarsOfPred pred))
+  = Just (mkPredTy (substPred co_subst pred), substPred tv_subst pred)
+  | otherwise
+  = Nothing    -- The type doesn't mention any refined type variables
+  where
+    tv_subst = mkTvSubst in_scope (mapVarEnv snd env)
+    co_subst = mkTvSubst in_scope (mapVarEnv fst env)
+refineResType :: Refinement -> Type -> Maybe (Coercion, Type)
+-- Like refineType, but returns the 'sym' coercion
+-- If (refineResType r ty) = (co, ty')
+-- Then co :: ty'~ty
+refineResType reft ty
+  = case refineType reft ty of
+      Just (co, ty1) -> Just (mkSymCoercion co, ty1)
+      Nothing       -> Nothing
+\end{code}
+
+
+%************************************************************************
+%*                                                                     *
+               Simple generation of a type refinement
+%*                                                                     *
+%************************************************************************
+
+\begin{code}
+matchRefine :: [TyVar] -> [Coercion] -> Refinement
+\end{code}
+
+Given a list of coercions, where for each coercion c::(ty1~ty2), the type ty2
+is a specialisation of ty1, produce a type refinement that maps the variables
+of ty1 to the corresponding sub-terms of ty2 using appropriate coercions; eg,
+
+  matchRefine (co :: [(a, b)] ~ [(c, Maybe d)])
+    = { right (left (right co)) :: a ~ c
+      , right (right co)        :: b ~ Maybe d
+      }
+
+Precondition: The rhs types must indeed be a specialisation of the lhs types;
+  i.e., some free variables of the lhs are replaced with either distinct free 
+  variables or proper type terms to obtain the rhs.  (We don't perform full
+  unification or type matching here!)
+
+NB: matchRefine does *not* expand the type synonyms.
+
+\begin{code}
+matchRefine in_scope_tvs cos 
+  = Reft in_scope (foldr plusVarEnv emptyVarEnv (map refineOne cos))
+  where
+    in_scope = mkInScopeSet (mkVarSet in_scope_tvs)
+       -- NB: in_scope_tvs include both coercion variables
+       --     *and* the tyvars in their kinds
+
+    refineOne co = refine co ty1 ty2
+      where
+        (ty1, ty2) = coercionKind co
+
+    refine co (TyVarTy tv) ty                     = unitVarEnv tv (co, ty)
+    refine co (TyConApp _ tys) (TyConApp _ tys')  = refineArgs co tys tys'
+    refine _  (PredTy _) (PredTy _)               = 
+      error "Unify.matchRefine: PredTy"
+    refine co (FunTy arg res) (FunTy arg' res')   =
+      refine (mkRightCoercion (mkLeftCoercion co)) arg arg' 
+      `plusVarEnv` 
+      refine (mkRightCoercion co) res res'
+    refine co (AppTy fun arg) (AppTy fun' arg')   = 
+      refine (mkLeftCoercion co) fun fun' 
+      `plusVarEnv`
+      refine (mkRightCoercion co) arg arg'
+    refine co (ForAllTy tv ty) (ForAllTy _tv ty') =
+      refine (mkForAllCoercion tv co) ty ty' `delVarEnv` tv
+    refine _ _ _ = error "RcGadt.matchRefine: mismatch"
+
+    refineArgs :: Coercion -> [Type] -> [Type] -> InternalReft
+    refineArgs co tys tys' = 
+      fst $ foldr refineArg (emptyVarEnv, id) (zip tys tys')
+      where
+        refineArg (ty, ty') (reft, coWrapper) 
+          = (refine (mkRightCoercion (coWrapper co)) ty ty' `plusVarEnv` reft, 
+             mkLeftCoercion . coWrapper)
+\end{code}
+
+
+%************************************************************************
+%*                                                                     *
+               Unification
+%*                                                                     *
+%************************************************************************
+
+\begin{code}
+tcUnifyTys :: (TyVar -> BindFlag)
+          -> [Type] -> [Type]
+          -> Maybe TvSubst     -- A regular one-shot substitution
+-- The two types may have common type variables, and indeed do so in the
+-- second call to tcUnifyTys in FunDeps.checkClsFD
+--
+tcUnifyTys bind_fn tys1 tys2
+  = maybeErrToMaybe $ initUM bind_fn $
+    do { subst <- unifyList emptyTvSubstEnv tys1 tys2
+
+       -- Find the fixed point of the resulting non-idempotent substitution
+       ; let in_scope = mkInScopeSet (tvs1 `unionVarSet` tvs2)
+             tv_env   = fixTvSubstEnv in_scope subst
+
+       ; return (mkTvSubst in_scope tv_env) }
+  where
+    tvs1 = tyVarsOfTypes tys1
+    tvs2 = tyVarsOfTypes tys2
+
+----------------------------
+-- XXX Can we do this more nicely, by exploiting laziness?
+-- Or avoid needing it in the first place?
+fixTvSubstEnv :: InScopeSet -> TvSubstEnv -> TvSubstEnv
+fixTvSubstEnv in_scope env = f env
+  where
+    f e = let e' = mapUFM (substTy (mkTvSubst in_scope e)) e
+          in if and $ eltsUFM $ intersectUFM_C tcEqType e e'
+             then e
+             else f e'
+
+\end{code}
+
+
+%************************************************************************
+%*                                                                     *
+               The workhorse
+%*                                                                     *
+%************************************************************************
+
+\begin{code}
+unify :: TvSubstEnv    -- An existing substitution to extend
+      -> Type -> Type  -- Types to be unified, and witness of their equality
+      -> UM TvSubstEnv         -- Just the extended substitution, 
+                               -- Nothing if unification failed
+-- We do not require the incoming substitution to be idempotent,
+-- nor guarantee that the outgoing one is.  That's fixed up by
+-- the wrappers.
+
+-- Respects newtypes, PredTypes
+
+-- in unify, any NewTcApps/Preds should be taken at face value
+unify subst (TyVarTy tv1) ty2  = uVar subst tv1 ty2
+unify subst ty1 (TyVarTy tv2)  = uVar subst tv2 ty1
+
+unify subst ty1 ty2 | Just ty1' <- tcView ty1 = unify subst ty1' ty2
+unify subst ty1 ty2 | Just ty2' <- tcView ty2 = unify subst ty1 ty2'
+
+unify subst (PredTy p1) (PredTy p2) = unify_pred subst p1 p2
+
+unify subst (TyConApp tyc1 tys1) (TyConApp tyc2 tys2) 
+  | tyc1 == tyc2 = unify_tys subst tys1 tys2
+
+unify subst (FunTy ty1a ty1b) (FunTy ty2a ty2b) 
+  = do { subst' <- unify subst ty1a ty2a
+       ; unify subst' ty1b ty2b }
+
+       -- Applications need a bit of care!
+       -- They can match FunTy and TyConApp, so use splitAppTy_maybe
+       -- NB: we've already dealt with type variables and Notes,
+       -- so if one type is an App the other one jolly well better be too
+unify subst (AppTy ty1a ty1b) ty2
+  | Just (ty2a, ty2b) <- repSplitAppTy_maybe ty2
+  = do { subst' <- unify subst ty1a ty2a
+        ; unify subst' ty1b ty2b }
+
+unify subst ty1 (AppTy ty2a ty2b)
+  | Just (ty1a, ty1b) <- repSplitAppTy_maybe ty1
+  = do { subst' <- unify subst ty1a ty2a
+        ; unify subst' ty1b ty2b }
+
+unify _ ty1 ty2 = failWith (misMatch ty1 ty2)
+       -- ForAlls??
+
+------------------------------
+unify_pred :: TvSubstEnv -> PredType -> PredType -> UM TvSubstEnv
+unify_pred subst (ClassP c1 tys1) (ClassP c2 tys2)
+  | c1 == c2 = unify_tys subst tys1 tys2
+unify_pred subst (IParam n1 t1) (IParam n2 t2)
+  | n1 == n2 = unify subst t1 t2
+unify_pred _ p1 p2 = failWith (misMatch (PredTy p1) (PredTy p2))
+------------------------------
+unify_tys :: TvSubstEnv -> [Type] -> [Type] -> UM TvSubstEnv
+unify_tys subst xs ys = unifyList subst xs ys
+
+unifyList :: TvSubstEnv -> [Type] -> [Type] -> UM TvSubstEnv
+unifyList subst orig_xs orig_ys
+  = go subst orig_xs orig_ys
+  where
+    go subst []     []     = return subst
+    go subst (x:xs) (y:ys) = do { subst' <- unify subst x y
+                               ; go subst' xs ys }
+    go _ _ _ = failWith (lengthMisMatch orig_xs orig_ys)
+
+---------------------------------
+uVar :: TvSubstEnv     -- An existing substitution to extend
+     -> TyVar           -- Type variable to be unified
+     -> Type            -- with this type
+     -> UM TvSubstEnv
+
+-- PRE-CONDITION: in the call (uVar swap r tv1 ty), we know that
+--     if swap=False   (tv1~ty)
+--     if swap=True    (ty~tv1)
+
+uVar subst tv1 ty
+ = -- Check to see whether tv1 is refined by the substitution
+   case (lookupVarEnv subst tv1) of
+     Just ty' -> unify subst ty' ty     -- Yes, call back into unify'
+     Nothing  -> uUnrefined subst       -- No, continue
+                           tv1 ty ty
+
+uUnrefined :: TvSubstEnv          -- An existing substitution to extend
+           -> TyVar               -- Type variable to be unified
+           -> Type                -- with this type
+           -> Type                -- (version w/ expanded synonyms)
+           -> UM TvSubstEnv
+
+-- We know that tv1 isn't refined
+
+uUnrefined subst tv1 ty2 ty2'
+  | Just ty2'' <- tcView ty2'
+  = uUnrefined subst tv1 ty2 ty2''     -- Unwrap synonyms
+               -- This is essential, in case we have
+               --      type Foo a = a
+               -- and then unify a ~ Foo a
+
+uUnrefined subst tv1 ty2 (TyVarTy tv2)
+  | tv1 == tv2         -- Same type variable
+  = return subst
+
+    -- Check to see whether tv2 is refined
+  | Just ty' <- lookupVarEnv subst tv2
+  = uUnrefined subst tv1 ty' ty'
+
+  -- So both are unrefined; next, see if the kinds force the direction
+  | eqKind k1 k2       -- Can update either; so check the bind-flags
+  = do { b1 <- tvBindFlag tv1
+       ; b2 <- tvBindFlag tv2
+       ; case (b1,b2) of
+           (BindMe, _)          -> bind tv1 ty2
+           (Skolem, Skolem)     -> failWith (misMatch ty1 ty2)
+           (Skolem, _)          -> bind tv2 ty1
+       }
+
+  | k1 `isSubKind` k2 = bindTv subst tv2 ty1  -- Must update tv2
+  | k2 `isSubKind` k1 = bindTv subst tv1 ty2  -- Must update tv1
+
+  | otherwise = failWith (kindMisMatch tv1 ty2)
+  where
+    ty1 = TyVarTy tv1
+    k1 = tyVarKind tv1
+    k2 = tyVarKind tv2
+    bind tv ty = return $ extendVarEnv subst tv ty
+
+uUnrefined subst tv1 ty2 ty2'  -- ty2 is not a type variable
+  | tv1 `elemVarSet` substTvSet subst (tyVarsOfType ty2')
+  = failWith (occursCheck tv1 ty2)     -- Occurs check
+  | not (k2 `isSubKind` k1)
+  = failWith (kindMisMatch tv1 ty2)    -- Kind check
+  | otherwise
+  = bindTv subst tv1 ty2               -- Bind tyvar to the synonym if poss
+  where
+    k1 = tyVarKind tv1
+    k2 = typeKind ty2'
+
+substTvSet :: TvSubstEnv -> TyVarSet -> TyVarSet
+-- Apply the non-idempotent substitution to a set of type variables,
+-- remembering that the substitution isn't necessarily idempotent
+substTvSet subst tvs
+  = foldVarSet (unionVarSet . get) emptyVarSet tvs
+  where
+    get tv = case lookupVarEnv subst tv of
+              Nothing -> unitVarSet tv
+              Just ty -> substTvSet subst (tyVarsOfType ty)
+
+bindTv :: TvSubstEnv -> TyVar -> Type -> UM TvSubstEnv
+bindTv subst tv ty     -- ty is not a type variable
+  = do  { b <- tvBindFlag tv
+       ; case b of
+           Skolem -> failWith (misMatch (TyVarTy tv) ty)
+           BindMe -> return $ extendVarEnv subst tv ty
+       }
+\end{code}
+
+%************************************************************************
+%*                                                                     *
+               Binding decisions
+%*                                                                     *
+%************************************************************************
+
+\begin{code}
+data BindFlag 
+  = BindMe     -- A regular type variable
+
+  | Skolem     -- This type variable is a skolem constant
+               -- Don't bind it; it only matches itself
+\end{code}
+
+
+%************************************************************************
+%*                                                                     *
+               Unification monad
+%*                                                                     *
+%************************************************************************
+
+\begin{code}
+newtype UM a = UM { unUM :: (TyVar -> BindFlag)
+                        -> MaybeErr Message a }
+
+instance Monad UM where
+  return a = UM (\_tvs -> Succeeded a)
+  fail s   = UM (\_tvs -> Failed (text s))
+  m >>= k  = UM (\tvs -> case unUM m tvs of
+                          Failed err -> Failed err
+                          Succeeded v  -> unUM (k v) tvs)
+
+initUM :: (TyVar -> BindFlag) -> UM a -> MaybeErr Message a
+initUM badtvs um = unUM um badtvs
+
+tvBindFlag :: TyVar -> UM BindFlag
+tvBindFlag tv = UM (\tv_fn -> Succeeded (tv_fn tv))
+
+failWith :: Message -> UM a
+failWith msg = UM (\_tv_fn -> Failed msg)
+
+maybeErrToMaybe :: MaybeErr fail succ -> Maybe succ
+maybeErrToMaybe (Succeeded a) = Just a
+maybeErrToMaybe (Failed _)    = Nothing
+\end{code}
+
+
+%************************************************************************
+%*                                                                     *
+               Error reporting
+       We go to a lot more trouble to tidy the types
+       in TcUnify.  Maybe we'll end up having to do that
+       here too, but I'll leave it for now.
+%*                                                                     *
+%************************************************************************
+
+\begin{code}
+misMatch :: Type -> Type -> SDoc
+misMatch t1 t2
+  = ptext (sLit "Can't match types") <+> quotes (ppr t1) <+> 
+    ptext (sLit "and") <+> quotes (ppr t2)
+
+lengthMisMatch :: [Type] -> [Type] -> SDoc
+lengthMisMatch tys1 tys2
+  = sep [ptext (sLit "Can't match unequal length lists"), 
+        nest 2 (ppr tys1), nest 2 (ppr tys2) ]
+
+kindMisMatch :: TyVar -> Type -> SDoc
+kindMisMatch tv1 t2
+  = vcat [ptext (sLit "Can't match kinds") <+> quotes (ppr (tyVarKind tv1)) <+> 
+           ptext (sLit "and") <+> quotes (ppr (typeKind t2)),
+         ptext (sLit "when matching") <+> quotes (ppr tv1) <+> 
+               ptext (sLit "with") <+> quotes (ppr t2)]
+
+occursCheck :: TyVar -> Type -> SDoc
+occursCheck tv ty
+  = hang (ptext (sLit "Can't construct the infinite type"))
+       2 (ppr tv <+> equals <+> ppr ty)
+\end{code}