From 27759873a8bd45c487a6e636f7a12c37e87f616f Mon Sep 17 00:00:00 2001
From: "simonpj@microsoft.com" <unknown>
Date: Wed, 14 Jan 2009 14:01:17 +0000
Subject: [PATCH] Robustify lookupFamInstEnv

Suppose we have
        type family T a :: * -> *
        type instance T Int = []

and now we encounter the type (T Int Bool).  That is perfectly
fine, even though T is over-saturated here.

This patch makes lookupFamInstEnv robust to such over-saturation.
Previously one caller (TcTyFuns.tcUnfoldSynFamInst) dealt with
the over-saturation case, but the others did not. It's better
to desl with the issue at the root, in lookupFamInstEnv itself.
---
 compiler/typecheck/TcTyFuns.lhs |   13 ++++---------
 compiler/types/FamInstEnv.lhs   |   33 ++++++++++++++++++++++++++++++---
 2 files changed, 34 insertions(+), 12 deletions(-)

diff --git a/compiler/typecheck/TcTyFuns.lhs b/compiler/typecheck/TcTyFuns.lhs
index 2237e3f..0066d2f 100644
--- a/compiler/typecheck/TcTyFuns.lhs
+++ b/compiler/typecheck/TcTyFuns.lhs
@@ -69,21 +69,16 @@ tcUnfoldSynFamInst (TyConApp tycon tys)
   | not (isOpenSynTyCon tycon)     -- unfold *only* _synonym_ family instances
   = return Nothing
   | otherwise
-  = do { -- we only use the indexing arguments for matching, 
-         -- not the additional ones
-       ; maybeFamInst <- tcLookupFamInst tycon idxTys
+  = do { -- The TyCon might be over-saturated, but that's ok for tcLookupFamInst
+       ; maybeFamInst <- tcLookupFamInst tycon tys
        ; case maybeFamInst of
            Nothing                -> return Nothing
-           Just (rep_tc, rep_tys) -> return $ Just (mkTyConApp rep_tc tys',
-		                                    mkTyConApp coe_tc tys')
+           Just (rep_tc, rep_tys) -> return $ Just (mkTyConApp rep_tc rep_tys,
+		                                    mkTyConApp coe_tc rep_tys)
              where
-               tys'   = rep_tys ++ restTys
                coe_tc = expectJust "TcTyFuns.tcUnfoldSynFamInst" 
                                    (tyConFamilyCoercion_maybe rep_tc)
        }
-    where
-        n                = tyConArity tycon
-        (idxTys, restTys) = splitAt n tys
 tcUnfoldSynFamInst _other = return Nothing
 \end{code}
 
diff --git a/compiler/types/FamInstEnv.lhs b/compiler/types/FamInstEnv.lhs
index ba96a55..65c2539 100644
--- a/compiler/types/FamInstEnv.lhs
+++ b/compiler/types/FamInstEnv.lhs
@@ -218,8 +218,25 @@ desugared to
 
 we return the matching instance '(FamInst{.., fi_tycon = :R42T}, Int)'.
 
+Note [Over-saturated matches]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+It's ok to look up an over-saturated type constructor.  E.g.
+     type family F a :: * -> *
+     type instance F (a,b) = Either (a->b)
+
+The type instance gives rise to a newtype TyCon (at a higher kind
+which you can't do in Haskell!):
+     newtype FPair a b = FP (Either (a->b))
+
+Then looking up (F (Int,Bool) Char) will return a FamInstMatch 
+     (FPair, [Int,Bool,Char])
+
+The "extra" type argument [Char] just stays on the end.
+
+
 \begin{code}
 type FamInstMatch = (FamInst, [Type])           -- Matching type instance
+  -- See Note [Over-saturated matches]
 
 lookupFamInstEnv :: FamInstEnvs
 	         -> TyCon -> [Type]		-- What we are looking for
@@ -228,13 +245,23 @@ lookupFamInstEnv (pkg_ie, home_ie) fam tys
   | not (isOpenTyCon fam) 
   = []
   | otherwise
-  = home_matches ++ pkg_matches
+  = ASSERT( n_tys >= arity )	-- Family type applications must be saturated
+    home_matches ++ pkg_matches
   where
     rough_tcs    = roughMatchTcs tys
     all_tvs      = all isNothing rough_tcs
     home_matches = lookup home_ie 
     pkg_matches  = lookup pkg_ie  
 
+    -- See Note [Over-saturated matches]
+    arity = tyConArity fam
+    n_tys = length tys
+    extra_tys = drop arity tys
+    (match_tys, add_extra_tys) 
+       | arity > n_tys = (take arity tys, \res_tys -> res_tys ++ extra_tys)
+       | otherwise     = (tys,            \res_tys -> res_tys)
+       	 -- The second case is the common one, hence functional representation
+
     --------------
     lookup env = case lookupUFM env fam of
 		   Nothing -> []	-- No instances for this class
@@ -255,8 +282,8 @@ lookupFamInstEnv (pkg_ie, home_ie) fam tys
       = find rest
 
         -- Proper check
-      | Just subst <- tcMatchTys tpl_tvs tpl_tys tys
-      = (item, substTyVars subst (tyConTyVars tycon)) : find rest
+      | Just subst <- tcMatchTys tpl_tvs tpl_tys match_tys
+      = (item, add_extra_tys $ substTyVars subst (tyConTyVars tycon)) : find rest
 
         -- No match => try next
       | otherwise
-- 
1.7.10.4