%
-% (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
+% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
\section[MatchLit]{Pattern-matching literal patterns}
\begin{code}
-#include "HsVersions.h"
-
-module MatchLit ( matchLiterals ) where
+module MatchLit ( dsLit, dsOverLit,
+ tidyLitPat, tidyNPat,
+ matchLiterals, matchNPlusKPats, matchNPats ) where
-IMP_Ubiq()
-IMPORT_DELOOPER(DsLoop) -- break match-ish and dsExpr-ish loops
+#include "HsVersions.h"
-import HsSyn ( HsLit(..), OutPat(..), HsExpr(..),
- Match, HsBinds, Stmt, Qual, PolyType, ArithSeqInfo )
-import TcHsSyn ( TypecheckedHsExpr(..), TypecheckedHsBinds(..),
- TypecheckedPat(..)
- )
-import CoreSyn ( CoreExpr(..), CoreBinding(..) )
+import {-# SOURCE #-} Match ( match )
+import {-# SOURCE #-} DsExpr ( dsExpr )
import DsMonad
import DsUtils
+import HsSyn
+import Id ( Id, idType )
+import CoreSyn
+import TyCon ( tyConDataCons )
+import TcType ( tcSplitTyConApp, isIntegerTy, isIntTy,
+ isFloatTy, isDoubleTy, isStringTy )
+import Type ( Type )
+import PrelNames ( ratioTyConKey )
+import TysWiredIn ( stringTy, consDataCon, intDataCon, floatDataCon, doubleDataCon )
+import PrelNames ( eqStringName )
+import Unique ( hasKey )
import Literal ( mkMachInt, Literal(..) )
-import Maybes ( catMaybes )
-import Type ( isPrimType )
-import Util ( panic, assertPanic )
+import SrcLoc ( noLoc )
+import ListSetOps ( equivClasses, runs )
+import Ratio ( numerator, denominator )
+import SrcLoc ( Located(..) )
+import Outputable
+import FastString ( lengthFS, unpackFS )
\end{code}
+%************************************************************************
+%* *
+ Desugaring literals
+ [used to be in DsExpr, but DsMeta needs it,
+ and it's nice to avoid a loop]
+%* *
+%************************************************************************
+
+We give int/float literals type @Integer@ and @Rational@, respectively.
+The typechecker will (presumably) have put \tr{from{Integer,Rational}s}
+around them.
+
+ToDo: put in range checks for when converting ``@i@''
+(or should that be in the typechecker?)
+
+For numeric literals, we try to detect there use at a standard type
+(@Int@, @Float@, etc.) are directly put in the right constructor.
+[NB: down with the @App@ conversion.]
+
+See also below where we look for @DictApps@ for \tr{plusInt}, etc.
+
+\begin{code}
+dsLit :: HsLit -> DsM CoreExpr
+dsLit (HsChar c) = returnDs (mkCharExpr c)
+dsLit (HsCharPrim c) = returnDs (mkLit (MachChar c))
+dsLit (HsString str) = mkStringExprFS str
+dsLit (HsStringPrim s) = returnDs (mkLit (MachStr s))
+dsLit (HsInteger i _) = mkIntegerExpr i
+dsLit (HsInt i) = returnDs (mkIntExpr i)
+dsLit (HsIntPrim i) = returnDs (mkIntLit i)
+dsLit (HsFloatPrim f) = returnDs (mkLit (MachFloat f))
+dsLit (HsDoublePrim d) = returnDs (mkLit (MachDouble d))
+
+dsLit (HsRat r ty)
+ = mkIntegerExpr (numerator r) `thenDs` \ num ->
+ mkIntegerExpr (denominator r) `thenDs` \ denom ->
+ returnDs (mkConApp ratio_data_con [Type integer_ty, num, denom])
+ where
+ (ratio_data_con, integer_ty)
+ = case tcSplitTyConApp ty of
+ (tycon, [i_ty]) -> ASSERT(isIntegerTy i_ty && tycon `hasKey` ratioTyConKey)
+ (head (tyConDataCons tycon), i_ty)
+
+dsOverLit :: HsOverLit Id -> DsM CoreExpr
+-- Post-typechecker, the SyntaxExpr field of an OverLit contains
+-- (an expression for) the literal value itself
+dsOverLit (HsIntegral _ lit) = dsExpr lit
+dsOverLit (HsFractional _ lit) = dsExpr lit
+\end{code}
+
+%************************************************************************
+%* *
+ Tidying lit pats
+%* *
+%************************************************************************
+
+\begin{code}
+tidyLitPat :: HsLit -> LPat Id -> LPat Id
+-- Result has only the following HsLits:
+-- HsIntPrim, HsCharPrim, HsFloatPrim
+-- HsDoublePrim, HsStringPrim, HsString
+-- * HsInteger, HsRat, HsInt can't show up in LitPats
+-- * We get rid of HsChar right here
+tidyLitPat (HsChar c) pat = mkCharLitPat c
+tidyLitPat (HsString s) pat
+ | lengthFS s <= 1 -- Short string literals only
+ = foldr (\c pat -> mkPrefixConPat consDataCon [mkCharLitPat c,pat] stringTy)
+ (mkNilPat stringTy) (unpackFS s)
+ -- The stringTy is the type of the whole pattern, not
+ -- the type to instantiate (:) or [] with!
+tidyLitPat lit pat = pat
+
+----------------
+tidyNPat :: HsOverLit Id -> Maybe (SyntaxExpr Id) -> Type -> LPat Id -> LPat Id
+tidyNPat over_lit mb_neg lit_ty default_pat
+ | isIntTy lit_ty = mk_con_pat intDataCon (HsIntPrim int_val)
+ | isFloatTy lit_ty = mk_con_pat floatDataCon (HsFloatPrim rat_val)
+ | isDoubleTy lit_ty = mk_con_pat doubleDataCon (HsDoublePrim rat_val)
+ | otherwise = default_pat
+ where
+ mk_con_pat con lit = mkPrefixConPat con [noLoc $ LitPat lit] lit_ty
+ neg_lit = case (mb_neg, over_lit) of
+ (Nothing, _) -> over_lit
+ (Just _, HsIntegral i s) -> HsIntegral (-i) s
+ (Just _, HsFractional f s) -> HsFractional (-f) s
+
+ int_val :: Integer
+ int_val = case neg_lit of
+ HsIntegral i _ -> i
+ HsFractional f _ -> panic "tidyNPat"
+
+ rat_val :: Rational
+ rat_val = case neg_lit of
+ HsIntegral i _ -> fromInteger i
+ HsFractional f _ -> f
+\end{code}
+
+
+%************************************************************************
+%* *
+ Pattern matching on LitPat
+%* *
+%************************************************************************
+
\begin{code}
matchLiterals :: [Id]
+ -> Type -- Type of the whole case expression
-> [EquationInfo]
- -> [EquationInfo] -- Shadows
-> DsM MatchResult
-\end{code}
+-- All the EquationInfos have LitPats at the front
-This first one is a {\em special case} where the literal patterns are
-unboxed numbers (NB: the fiddling introduced by @tidyEqnInfo@). We
-want to avoid using the ``equality'' stuff provided by the
-typechecker, and do a real ``case'' instead. In that sense, the code
-is much like @matchConFamily@, which uses @match_cons_used@ to create
-the alts---here we use @match_prims_used@.
+matchLiterals (var:vars) ty eqns
+ = do { -- Group by literal
+ let groups :: [[(Literal, EquationInfo)]]
+ groups = equivClasses cmpTaggedEqn (tagLitEqns eqns)
-\begin{code}
-matchLiterals all_vars@(var:vars) eqns_info@(EqnInfo (LitPat literal lit_ty : ps1) _ : eqns) shadows
- = -- GENERATE THE ALTS
- match_prims_used vars eqns_info shadows `thenDs` \ prim_alts ->
+ -- Deal with each group
+ ; alts <- mapM match_group groups
- -- MAKE THE PRIMITIVE CASE
- mkCoPrimCaseMatchResult var prim_alts
+ -- Combine results. For everything except String
+ -- we can use a case expression; for String we need
+ -- a chain of if-then-else
+ ; if isStringTy (idType var) then
+ do { mrs <- mapM wrap_str_guard alts
+ ; return (foldr1 combineMatchResults mrs) }
+ else
+ return (mkCoPrimCaseMatchResult var ty alts)
+ }
where
- match_prims_used _ [{-no more eqns-}] _ = returnDs []
-
- match_prims_used vars eqns_info@(EqnInfo ((LitPat literal lit_ty):ps1) _ : eqns) shadows
- = let
- (shifted_eqns_for_this_lit, eqns_not_for_this_lit)
- = partitionEqnsByLit literal eqns_info
- (shifted_shadows_for_this_lit, shadows_not_for_this_lit)
- = partitionEqnsByLit literal shadows
- in
- -- recursive call to make other alts...
- match_prims_used vars eqns_not_for_this_lit shadows_not_for_this_lit `thenDs` \ rest_of_alts ->
-
- -- (prim pats have no args; no selectMatchVars as in match_cons_used)
- -- now do the business to make the alt for _this_ LitPat ...
- match vars shifted_eqns_for_this_lit shifted_shadows_for_this_lit `thenDs` \ match_result ->
- returnDs (
- (mk_core_lit lit_ty literal, match_result)
- : rest_of_alts
- )
- where
- mk_core_lit :: Type -> HsLit -> Literal
-
- mk_core_lit ty (HsIntPrim i) = mkMachInt i
- mk_core_lit ty (HsCharPrim c) = MachChar c
- mk_core_lit ty (HsStringPrim s) = MachStr s
- mk_core_lit ty (HsFloatPrim f) = MachFloat f
- mk_core_lit ty (HsDoublePrim d) = MachDouble d
- mk_core_lit ty (HsLitLit s) = ASSERT(isPrimType ty)
- MachLitLit s (panic "MatchLit.matchLiterals:mk_core_lit:HsLitLit; typePrimRep???")
- mk_core_lit ty other = panic "matchLiterals:mk_core_lit:unhandled"
+ match_group :: [(Literal, EquationInfo)] -> DsM (Literal, MatchResult)
+ match_group group
+ = do { let (lits, eqns) = unzip group
+ ; match_result <- match vars ty (shiftEqns eqns)
+ ; return (head lits, match_result) }
+
+ wrap_str_guard :: (Literal,MatchResult) -> DsM MatchResult
+ -- Equality check for string literals
+ wrap_str_guard (MachStr s, mr)
+ = do { eq_str <- dsLookupGlobalId eqStringName
+ ; lit <- mkStringExprFS s
+ ; let pred = mkApps (Var eq_str) [Var var, lit]
+ ; return (mkGuardedMatchResult pred mr) }
\end{code}
+%************************************************************************
+%* *
+ Pattern matching on NPat
+%* *
+%************************************************************************
+
\begin{code}
-matchLiterals all_vars@(var:vars) eqns_info@(EqnInfo ((NPat literal lit_ty eq_chk):ps1) _ : eqns) shadows
- = let
- (shifted_eqns_for_this_lit, eqns_not_for_this_lit)
- = partitionEqnsByLit literal eqns_info
- (shifted_shadows_for_this_lit, shadows_not_for_this_lit)
- = partitionEqnsByLit literal shadows
- in
- dsExpr (HsApp eq_chk (HsVar var)) `thenDs` \ pred_expr ->
- match vars shifted_eqns_for_this_lit shifted_shadows_for_this_lit `thenDs` \ inner_match_result ->
- mkGuardedMatchResult pred_expr inner_match_result `thenDs` \ match_result1 ->
-
- if (null eqns_not_for_this_lit)
- then
- returnDs match_result1
- else
- matchLiterals all_vars eqns_not_for_this_lit shadows_not_for_this_lit `thenDs` \ match_result2 ->
- combineMatchResults match_result1 match_result2
+matchNPats :: [Id] -> Type -> [EquationInfo] -> DsM MatchResult
+-- All the EquationInfos have NPat at the front
+
+matchNPats (var:vars) ty eqns
+ = do { let groups :: [[(Literal, EquationInfo)]]
+ groups = equivClasses cmpTaggedEqn (tagLitEqns eqns)
+
+ ; match_results <- mapM (match_group . map snd) groups
+
+ ; ASSERT( not (null match_results) )
+ return (foldr1 combineMatchResults match_results) }
+ where
+ match_group :: [EquationInfo] -> DsM MatchResult
+ match_group (eqn1:eqns)
+ = do { lit_expr <- dsOverLit lit
+ ; neg_lit <- case mb_neg of
+ Nothing -> return lit_expr
+ Just neg -> do { neg_expr <- dsExpr neg
+ ; return (App neg_expr lit_expr) }
+ ; eq_expr <- dsExpr eq_chk
+ ; let pred_expr = mkApps eq_expr [Var var, neg_lit]
+ ; match_result <- match vars ty (eqn1' : shiftEqns eqns)
+ ; return (adjustMatchResult (eqn_wrap eqn1) $
+ -- Bring the eqn1 wrapper stuff into scope because
+ -- it may be used in pred_expr
+ mkGuardedMatchResult pred_expr match_result) }
+ where
+ NPat lit mb_neg eq_chk _ : pats1 = eqn_pats eqn1
+ eqn1' = eqn1 { eqn_wrap = idWrapper, eqn_pats = pats1 }
\end{code}
+
+%************************************************************************
+%* *
+ Pattern matching on n+k patterns
+%* *
+%************************************************************************
+
For an n+k pattern, we use the various magic expressions we've been given.
We generate:
\begin{verbatim}
<try-next-pattern-or-whatever>
\end{verbatim}
-Given a blob of LitPats/NPats, we want to split them into those
-that are ``same''/different as one we are looking at. We need to know
-whether we're looking at a LitPat/NPat, and what literal we're after.
+WATCH OUT! Consider
+
+ f (n+1) = ...
+ f (n+2) = ...
+ f (n+1) = ...
+
+We can't group the first and third together, because the second may match
+the same thing as the first. Contrast
+ f 1 = ...
+ f 2 = ...
+ f 1 = ...
+where we can group the first and third. Hence 'runs' rather than 'equivClasses'
\begin{code}
-partitionEqnsByLit :: HsLit
- -> [EquationInfo]
- -> ([EquationInfo], -- These ones are for this lit, AND
- -- they've been "shifted" by stripping
- -- off the first pattern
- [EquationInfo] -- These are not for this lit; they
- -- are exactly as fed in.
- )
-
-partitionEqnsByLit lit eqns
- = ( \ (xs,ys) -> (catMaybes xs, catMaybes ys))
- (unzip (map (partition_eqn lit) eqns))
+matchNPlusKPats all_vars@(var:vars) ty eqns
+ = do { let groups :: [[(Literal, EquationInfo)]]
+ groups = runs eqTaggedEqn (tagLitEqns eqns)
+
+ ; match_results <- mapM (match_group . map snd) groups
+
+ ; ASSERT( not (null match_results) )
+ return (foldr1 combineMatchResults match_results) }
where
- partition_eqn :: HsLit -> EquationInfo ->
- (Maybe EquationInfo, Maybe EquationInfo)
-
- partition_eqn lit (EqnInfo (LitPat k _ : remaining_pats) match_result)
- | lit `eq_lit` k = (Just (EqnInfo remaining_pats match_result), Nothing)
- -- NB the pattern is stripped off thhe EquationInfo
-
- partition_eqn lit (EqnInfo (NPat k _ _ : remaining_pats) match_result)
- | lit `eq_lit` k = (Just (EqnInfo remaining_pats match_result), Nothing)
- -- NB the pattern is stripped off thhe EquationInfo
-
- -- Wild-card patterns, which will only show up in the shadows, go into both groups
- partition_eqn lit eqn@(EqnInfo (WildPat _ : remaining_pats) match_result)
- = (Just (EqnInfo remaining_pats match_result), Just eqn)
-
- -- Default case; not for this pattern
- partition_eqn lit eqn = (Nothing, Just eqn)
-
--- ToDo: meditate about this equality business...
-
-eq_lit (HsInt i1) (HsInt i2) = i1 == i2
-eq_lit (HsFrac f1) (HsFrac f2) = f1 == f2
-
-eq_lit (HsIntPrim i1) (HsIntPrim i2) = i1 == i2
-eq_lit (HsFloatPrim f1) (HsFloatPrim f2) = f1 == f2
-eq_lit (HsDoublePrim d1) (HsDoublePrim d2) = d1 == d2
-eq_lit (HsChar c1) (HsChar c2) = c1 == c2
-eq_lit (HsCharPrim c1) (HsCharPrim c2) = c1 == c2
-eq_lit (HsString s1) (HsString s2) = s1 == s2
-eq_lit (HsStringPrim s1) (HsStringPrim s2) = s1 == s2
-eq_lit (HsLitLit s1) (HsLitLit s2) = s1 == s2 -- ToDo: ??? (dubious)
-eq_lit other1 other2 = panic "matchLiterals:eq_lit"
+ match_group :: [EquationInfo] -> DsM MatchResult
+ match_group (eqn1:eqns)
+ = do { ge_expr <- dsExpr ge
+ ; minus_expr <- dsExpr minus
+ ; lit_expr <- dsOverLit lit
+ ; let pred_expr = mkApps ge_expr [Var var, lit_expr]
+ minusk_expr = mkApps minus_expr [Var var, lit_expr]
+ ; match_result <- match vars ty (eqn1' : map shift eqns)
+ ; return (adjustMatchResult (eqn_wrap eqn1) $
+ -- Bring the eqn1 wrapper stuff into scope because
+ -- it may be used in ge_expr, minusk_expr
+ mkGuardedMatchResult pred_expr $
+ mkCoLetMatchResult (NonRec n1 minusk_expr) $
+ match_result) }
+ where
+ NPlusKPat (L _ n1) lit ge minus : pats1 = eqn_pats eqn1
+ eqn1' = eqn1 { eqn_wrap = idWrapper, eqn_pats = pats1 }
+
+ shift eqn@(EqnInfo { eqn_wrap = wrap,
+ eqn_pats = NPlusKPat (L _ n) _ _ _ : pats })
+ = eqn { eqn_wrap = wrap . wrapBind n n1, eqn_pats = pats }
+\end{code}
+
+
+%************************************************************************
+%* *
+ Grouping functions
+%* *
+%************************************************************************
+
+Given a blob of @LitPat@s/@NPat@s, we want to split them into those
+that are ``same''/different as one we are looking at. We need to know
+whether we're looking at a @LitPat@/@NPat@, and what literal we're after.
+
+\begin{code}
+-- Tag equations by the leading literal
+-- NB: we have ordering on Core Literals, but not on HsLits
+cmpTaggedEqn :: (Literal,EquationInfo) -> (Literal,EquationInfo) -> Ordering
+cmpTaggedEqn (lit1,_) (lit2,_) = lit1 `compare` lit2
+
+eqTaggedEqn :: (Literal,EquationInfo) -> (Literal,EquationInfo) -> Bool
+eqTaggedEqn (lit1,_) (lit2,_) = lit1 == lit2
+
+tagLitEqns :: [EquationInfo] -> [(Literal, EquationInfo)]
+tagLitEqns eqns = [(get_lit (firstPat eqn), eqn) | eqn <- eqns]
+
+get_lit :: Pat Id -> Literal
+-- Get a Core literal to use (only) a grouping key
+-- Hence its type doesn't need to match the type of the original literal
+get_lit (LitPat (HsIntPrim i)) = mkMachInt i
+get_lit (LitPat (HsCharPrim c)) = MachChar c
+get_lit (LitPat (HsStringPrim s)) = MachStr s
+get_lit (LitPat (HsFloatPrim f)) = MachFloat f
+get_lit (LitPat (HsDoublePrim d)) = MachDouble d
+get_lit (LitPat (HsString s)) = MachStr s
+
+get_lit (NPat (HsIntegral i _) Nothing _ _) = MachInt i
+get_lit (NPat (HsIntegral i _) (Just _) _ _) = MachInt (-i)
+get_lit (NPat (HsFractional r _) Nothing _ _) = MachFloat r
+get_lit (NPat (HsFractional r _) (Just _) _ _) = MachFloat (-r)
+
+get_lit (NPlusKPat _ (HsIntegral i _) _ _) = MachInt i
+
+-- These ones can't happen
+-- get_lit (LitPat (HsChar c))
+-- get_lit (LitPat (HsInt i))
+get_lit other = pprPanic "get_lit:bad pattern" (ppr other)
\end{code}
+