git.iko.soy/Idris-dev
on b0cb4e2 help sign in
Idris-dev/src/Idris/Core/CaseTree.hs
761 lines 30 kB history raw
1{-# LANGUAGE PatternGuards, DeriveFunctor, TypeSynonymInstances #-}
3module Idris.Core.CaseTree(CaseDef(..), SC, SC'(..), CaseAlt, CaseAlt'(..),
4 Phase(..), CaseTree,
5 simpleCase, small, namesUsed, findCalls, findUsedArgs,
6 substSC, substAlt, mkForce) where
8import Idris.Core.TT
10import Control.Monad.State
11import Data.Maybe
12import Data.List hiding (partition)
13import qualified Data.List(partition)
14import Debug.Trace
16data CaseDef = CaseDef [Name] !SC [Term]
17 deriving Show
19-- Note: The case-tree elaborator only produces (Case n alts)-cases;
20-- in other words, it never inspects anything else than variables.
21--
22-- ProjCase is a special powerful case construct that allows inspection
23-- of compound terms. Occurrences of ProjCase arise no earlier than
24-- in the function `prune` as a means of optimisation
25-- of already built case trees.
26--
27-- While the intermediate representation (follows in the pipeline)
28-- allows casing on arbitrary terms, here we choose to maintain the distinction
29-- in order to allow for better optimisation opportunities.
30--
31data SC' t = Case Name [CaseAlt' t] -- ^ invariant: lowest tags first
32 | ProjCase t [CaseAlt' t] -- ^ special case for projections/thunk-forcing before inspection
33 | STerm !t
34 | UnmatchedCase String -- ^ error message
35 | ImpossibleCase -- ^ already checked to be impossible
36 deriving (Eq, Ord, Functor)
37{-!
38deriving instance Binary SC'
39deriving instance NFData SC'
40!-}
42type SC = SC' Term
44data CaseAlt' t = ConCase Name Int [Name] !(SC' t)
45 | FnCase Name [Name] !(SC' t) -- ^ reflection function
46 | ConstCase Const !(SC' t)
47 | SucCase Name !(SC' t)
48 | DefaultCase !(SC' t)
49 deriving (Show, Eq, Ord, Functor)
50{-!
51deriving instance Binary CaseAlt'
52deriving instance NFData CaseAlt'
53!-}
55type CaseAlt = CaseAlt' Term
57instance Show t => Show (SC' t) where
58 show sc = show' 1 sc
59 where
60 show' i (Case n alts) = "case " ++ show n ++ " of\n" ++ indent i ++
61 showSep ("\n" ++ indent i) (map (showA i) alts)
62 show' i (ProjCase tm alts) = "case " ++ show tm ++ " of " ++
63 showSep ("\n" ++ indent i) (map (showA i) alts)
64 show' i (STerm tm) = show tm
65 show' i (UnmatchedCase str) = "error " ++ show str
66 show' i ImpossibleCase = "impossible"
68 indent i = concat $ take i (repeat " ")
70 showA i (ConCase n t args sc)
71 = show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
72 ++ show' (i+1) sc
73 showA i (FnCase n args sc)
74 = "FN " ++ show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
75 ++ show' (i+1) sc
76 showA i (ConstCase t sc)
77 = show t ++ " => " ++ show' (i+1) sc
78 showA i (SucCase n sc)
79 = show n ++ "+1 => " ++ show' (i+1) sc
80 showA i (DefaultCase sc)
81 = "_ => " ++ show' (i+1) sc
84type CaseTree = SC
85type Clause = ([Pat], (Term, Term))
86type CS = ([Term], Int, [(Name, Type)])
88instance TermSize SC where
89 termsize n (Case n' as) = termsize n as
90 termsize n (ProjCase n' as) = termsize n as
91 termsize n (STerm t) = termsize n t
92 termsize n _ = 1
94instance TermSize CaseAlt where
95 termsize n (ConCase _ _ _ s) = termsize n s
96 termsize n (FnCase _ _ s) = termsize n s
97 termsize n (ConstCase _ s) = termsize n s
98 termsize n (SucCase _ s) = termsize n s
99 termsize n (DefaultCase s) = termsize n s
101-- simple terms can be inlined trivially - good for primitives in particular
102-- To avoid duplicating work, don't inline something which uses one
103-- of its arguments in more than one place
105small :: Name -> [Name] -> SC -> Bool
106small n args t = let as = findAllUsedArgs t args in
107 length as == length (nub as) &&
108 termsize n t < 10
110namesUsed :: SC -> [Name]
111namesUsed sc = nub $ nu' [] sc where
112 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
113 nu' ps (ProjCase t alts) = nub $ nut ps t ++ concatMap (nua ps) alts
114 nu' ps (STerm t) = nub $ nut ps t
115 nu' ps _ = []
117 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
118 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc) \\ args
119 nua ps (ConstCase _ sc) = nu' ps sc
120 nua ps (SucCase _ sc) = nu' ps sc
121 nua ps (DefaultCase sc) = nu' ps sc
123 nut ps (P _ n _) | n `elem` ps = []
124 | otherwise = [n]
125 nut ps (App f a) = nut ps f ++ nut ps a
126 nut ps (Proj t _) = nut ps t
127 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
128 nut ps (Bind n b sc) = nut (n:ps) sc
129 nut ps _ = []
131-- Return all called functions, and which arguments are used in each argument position
132-- for the call, in order to help reduce compilation time, and trace all unused
133-- arguments
135findCalls :: SC -> [Name] -> [(Name, [[Name]])]
136findCalls sc topargs = nub $ nu' topargs sc where
137 nu' ps (Case n alts) = nub (concatMap (nua (n : ps)) alts)
138 nu' ps (ProjCase t alts) = nub $ nut ps t ++ concatMap (nua ps) alts
139 nu' ps (STerm t) = nub $ nut ps t
140 nu' ps _ = []
142 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc)
143 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc)
144 nua ps (ConstCase _ sc) = nu' ps sc
145 nua ps (SucCase _ sc) = nu' ps sc
146 nua ps (DefaultCase sc) = nu' ps sc
148 nut ps (P Ref n _) | n `elem` ps = []
149 | otherwise = [(n, [])] -- tmp
150 nut ps fn@(App f a)
151 | (P Ref n _, args) <- unApply fn
152 = if n `elem` ps then nut ps f ++ nut ps a
153 else [(n, map argNames args)] ++ concatMap (nut ps) args
154 | (P (TCon _ _) n _, _) <- unApply fn = []
155 | otherwise = nut ps f ++ nut ps a
156 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
157 nut ps (Proj t _) = nut ps t
158 nut ps (Bind n b sc) = nut (n:ps) sc
159 nut ps _ = []
161 argNames tm = let ns = directUse tm in
162 filter (\x -> x `elem` ns) topargs
164-- Find names which are used directly (i.e. not in a function call) in a term
166directUse :: TT Name -> [Name]
167directUse (P _ n _) = [n]
168directUse (Bind n (Let t v) sc) = nub $ directUse v ++ (directUse sc \\ [n])
169 ++ directUse t
170directUse (Bind n b sc) = nub $ directUse (binderTy b) ++ (directUse sc \\ [n])
171directUse fn@(App f a)
172 | (P Ref (UN pfk) _, [App e w]) <- unApply fn,
173 pfk == txt "prim_fork"
174 = directUse e ++ directUse w -- HACK so that fork works
175 | (P Ref (UN fce) _, [_, _, a]) <- unApply fn,
176 fce == txt "Force"
177 = directUse a -- forcing a value counts as a use
178 | (P Ref n _, args) <- unApply fn = [] -- need to know what n does with them
179 | (P (TCon _ _) n _, args) <- unApply fn = [] -- type constructors not used at runtime
180 | otherwise = nub $ directUse f ++ directUse a
181directUse (Proj x i) = nub $ directUse x
182directUse _ = []
184-- Find all directly used arguments (i.e. used but not in function calls)
186findUsedArgs :: SC -> [Name] -> [Name]
187findUsedArgs sc topargs = nub (findAllUsedArgs sc topargs)
189findAllUsedArgs sc topargs = filter (\x -> x `elem` topargs) (nu' sc) where
190 nu' (Case n alts) = n : concatMap nua alts
191 nu' (ProjCase t alts) = directUse t ++ concatMap nua alts
192 nu' (STerm t) = directUse t
193 nu' _ = []
195 nua (ConCase n i args sc) = nu' sc
196 nua (FnCase n args sc) = nu' sc
197 nua (ConstCase _ sc) = nu' sc
198 nua (SucCase _ sc) = nu' sc
199 nua (DefaultCase sc) = nu' sc
201-- Return whether name is used anywhere in a case tree
202isUsed :: SC -> Name -> Bool
203isUsed sc n = used sc where
205 used (Case n' alts) = n == n' || or (map usedA alts)
206 used (ProjCase t alts) = n `elem` freeNames t || or (map usedA alts)
207 used (STerm t) = n `elem` freeNames t
208 used _ = False
210 usedA (ConCase _ _ args sc) = used sc
211 usedA (FnCase _ args sc) = used sc
212 usedA (ConstCase _ sc) = used sc
213 usedA (SucCase _ sc) = used sc
214 usedA (DefaultCase sc) = used sc
216type CaseBuilder a = State CS a
218data Phase = CompileTime | RunTime
219 deriving (Show, Eq)
221-- Generate a simple case tree
222-- Work Right to Left
224simpleCase :: Bool -> Bool -> Bool ->
225 Phase -> FC -> [Int] -> [Type] ->
226 [([Name], Term, Term)] ->
227 TC CaseDef
228simpleCase tc cover reflect phase fc inacc argtys cs
229 = sc' tc cover phase fc (filter (\(_, _, r) ->
230 case r of
231 Impossible -> False
232 _ -> True) cs)
233 where
234 sc' tc cover phase fc []
235 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
236 sc' tc cover phase fc cs
237 = let proj = phase == RunTime
238 vnames = fstT (head cs)
239 pats = map (\ (avs, l, r) ->
240 (avs, toPats reflect tc l, (l, r))) cs
241 chkPats = mapM chkAccessible pats in
242 case chkPats of
243 OK pats ->
244 let numargs = length (fst (head pats))
245 ns = take numargs args
246 (ns', ps') = order [(n, i `elem` inacc) | (i,n) <- zip [0..] ns] pats
247 (tree, st) = runState
248 (match ns' ps' (defaultCase cover))
249 ([], numargs, [])
250 t = CaseDef ns (prune proj (depatt ns' tree)) (fstT st) in
251 if proj then return (stripLambdas t)
252 else return t
253-- FIXME: This check is not quite right in some cases, and is breaking
254-- perfectly valid code!
255-- if checkSameTypes (lstT st) tree
256-- then return t
257-- else Error (At fc (Msg "Typecase is not allowed"))
258 Error err -> Error (At fc err)
259 where args = map (\i -> sMN i "e") [0..]
260 defaultCase True = STerm Erased
261 defaultCase False = UnmatchedCase "Error"
262 fstT (x, _, _) = x
263 lstT (_, _, x) = x
265 chkAccessible (avs, l, c)
266 | phase == RunTime || reflect = return (l, c)
267 | otherwise = do mapM_ (acc l) avs
268 return (l, c)
270 acc [] n = Error (Inaccessible n)
271 acc (PV x t : xs) n | x == n = OK ()
272 acc (PCon _ _ ps : xs) n = acc (ps ++ xs) n
273 acc (PSuc p : xs) n = acc (p : xs) n
274 acc (_ : xs) n = acc xs n
276-- For each 'Case', make sure every choice is in the same type family,
277-- as directed by the variable type (i.e. there is no implicit type casing
278-- going on).
280checkSameTypes :: [(Name, Type)] -> SC -> Bool
281checkSameTypes tys (Case n alts)
282 = case lookup n tys of
283 Just t -> and (map (checkAlts t) alts)
284 _ -> and (map ((checkSameTypes tys).getSC) alts)
285 where
286 checkAlts t (ConCase n _ _ sc) = isType n t && checkSameTypes tys sc
287 checkAlts (Constant t) (ConstCase c sc) = isConstType c t && checkSameTypes tys sc
288 checkAlts _ (ConstCase c sc) = False
289 checkAlts _ _ = True
291 getSC (ConCase _ _ _ sc) = sc
292 getSC (FnCase _ _ sc) = sc
293 getSC (ConstCase _ sc) = sc
294 getSC (SucCase _ sc) = sc
295 getSC (DefaultCase sc) = sc
296checkSameTypes _ _ = True
298-- FIXME: All we're actually doing here is checking that we haven't arrived
299-- at a specific constructor for a polymorphic argument. I *think* this
300-- is sufficient, but if it turns out not to be, fix it!
301isType n t | (P (TCon _ _) _ _, _) <- unApply t = True
302isType n t | (P Ref _ _, _) <- unApply t = True
303isType n t = False
305isConstType (I _) (AType (ATInt ITNative)) = True
306isConstType (BI _) (AType (ATInt ITBig)) = True
307isConstType (Fl _) (AType ATFloat) = True
308isConstType (Ch _) (AType (ATInt ITChar)) = True
309isConstType (Str _) StrType = True
310isConstType (B8 _) (AType (ATInt _)) = True
311isConstType (B16 _) (AType (ATInt _)) = True
312isConstType (B32 _) (AType (ATInt _)) = True
313isConstType (B64 _) (AType (ATInt _)) = True
314isConstType (B8V _) (AType (ATInt _)) = True
315isConstType (B16V _) (AType (ATInt _)) = True
316isConstType (B32V _) (AType (ATInt _)) = True
317isConstType (B64V _) (AType (ATInt _)) = True
318isConstType _ _ = False
320data Pat = PCon Name Int [Pat]
321 | PConst Const
322 | PV Name Type
323 | PSuc Pat -- special case for n+1 on Integer
324 | PReflected Name [Pat]
325 | PAny
326 | PTyPat -- typecase, not allowed, inspect last
327 deriving Show
329-- If there are repeated variables, take the *last* one (could be name shadowing
330-- in a where clause, so take the most recent).
332toPats :: Bool -> Bool -> Term -> [Pat]
333toPats reflect tc f = reverse (toPat reflect tc (getArgs f)) where
334 getArgs (App f a) = a : getArgs f
335 getArgs _ = []
337toPat :: Bool -> Bool -> [Term] -> [Pat]
338toPat reflect tc tms = evalState (mapM (\x -> toPat' x []) tms) []
339 where
340 toPat' (P (DCon t a) nm@(UN n) _) [_,_,arg]
341 | n == txt "Delay" = do arg' <- toPat' arg []
342 return $ PCon nm t [PAny, PAny, arg']
343 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
344 return $ PCon n t args'
345 -- n + 1
346 toPat' (P _ (UN pabi) _)
347 [p, Constant (BI 1)] | pabi == txt "prim__addBigInt"
348 = do p' <- toPat' p []
349 return $ PSuc p'
350 -- Typecase
351-- toPat' (P (TCon t a) n _) args | tc
352-- = do args' <- mapM (\x -> toPat' x []) args
353-- return $ PCon n t args'
354-- toPat' (Constant (AType (ATInt ITNative))) []
355-- | tc = return $ PCon (UN "Int") 1 []
356-- toPat' (Constant (AType ATFloat)) [] | tc = return $ PCon (UN "Float") 2 []
357-- toPat' (Constant (AType (ATInt ITChar))) [] | tc = return $ PCon (UN "Char") 3 []
358-- toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
359-- toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
360-- toPat' (Constant (AType (ATInt ITBig))) []
361-- | tc = return $ PCon (UN "Integer") 6 []
362-- toPat' (Constant (AType (ATInt (ITFixed n)))) []
363-- | tc = return $ PCon (UN (fixedN n)) (7 + fromEnum n) [] -- 7-10 inclusive
364 toPat' (P Bound n ty) [] = -- trace (show (n, ty)) $
365 do ns <- get
366 if n `elem` ns
367 then return PAny
368 else do put (n : ns)
369 return (PV n ty)
370 toPat' (App f a) args = toPat' f (a : args)
371 toPat' (Constant (AType _)) [] = return PTyPat
372 toPat' (Constant StrType) [] = return PTyPat
373 toPat' (Constant PtrType) [] = return PTyPat
374 toPat' (Constant VoidType) [] = return PTyPat
375 toPat' (Constant x) [] = return $ PConst x
376 toPat' (Bind n (Pi t) sc) [] | reflect && noOccurrence n sc
377 = do t' <- toPat' t []
378 sc' <- toPat' sc []
379 return $ PReflected (sUN "->") (t':sc':[])
380 toPat' (P _ n _) args | reflect
381 = do args' <- mapM (\x -> toPat' x []) args
382 return $ PReflected n args'
383 toPat' t _ = return PAny
385 fixedN IT8 = "Bits8"
386 fixedN IT16 = "Bits16"
387 fixedN IT32 = "Bits32"
388 fixedN IT64 = "Bits64"
391data Partition = Cons [Clause]
392 | Vars [Clause]
393 deriving Show
395isVarPat (PV _ _ : ps , _) = True
396isVarPat (PAny : ps , _) = True
397isVarPat (PTyPat : ps , _) = True
398isVarPat _ = False
400isConPat (PCon _ _ _ : ps, _) = True
401isConPat (PReflected _ _ : ps, _) = True
402isConPat (PSuc _ : ps, _) = True
403isConPat (PConst _ : ps, _) = True
404isConPat _ = False
406partition :: [Clause] -> [Partition]
407partition [] = []
408partition ms@(m : _)
409 | isVarPat m = let (vars, rest) = span isVarPat ms in
410 Vars vars : partition rest
411 | isConPat m = let (cons, rest) = span isConPat ms in
412 Cons cons : partition rest
413partition xs = error $ "Partition " ++ show xs
415-- reorder the patterns so that the one with most distinct names
416-- comes next. Take rightmost first, otherwise (i.e. pick value rather
417-- than dependency)
418--
419-- The first argument means [(Name, IsInaccessible)].
421order :: [(Name, Bool)] -> [Clause] -> ([Name], [Clause])
422order [] cs = ([], cs)
423order ns' [] = (map fst ns', [])
424order ns' cs = let patnames = transpose (map (zip ns') (map fst cs))
425 -- only sort the arguments where there is no clash in
426 -- constructor tags between families, and no constructor/constant
427 -- clash, because otherwise we can't reliable make the
428 -- case distinction on evaluation
429 (patnames_ord, patnames_rest)
430 = Data.List.partition (noClash . map snd) patnames
431 -- note: sortBy . reverse is not nonsense because sortBy is stable
432 pats' = transpose (sortBy moreDistinct (reverse patnames_ord)
433 ++ patnames_rest) in
434 (getNOrder pats', zipWith rebuild pats' cs)
435 where
436 getNOrder [] = error $ "Failed order on " ++ show (map fst ns', cs)
437 getNOrder (c : _) = map (fst . fst) c
439 rebuild patnames clause = (map snd patnames, snd clause)
441 noClash [] = True
442 noClash (p : ps) = not (any (clashPat p) ps) && noClash ps
444 clashPat (PCon _ _ _) (PConst _) = True
445 clashPat (PConst _) (PCon _ _ _) = True
446 clashPat (PCon _ _ _) (PSuc _) = True
447 clashPat (PSuc _) (PCon _ _ _) = True
448 clashPat (PCon n i _) (PCon n' i' _) | i == i' = n /= n'
449 clashPat _ _ = False
451 -- this compares (+isInaccessible, -numberOfCases)
452 moreDistinct xs ys = compare (snd . fst . head $ xs, numNames [] (map snd ys))
453 (snd . fst . head $ ys, numNames [] (map snd xs))
455 numNames xs (PCon n _ _ : ps)
456 | not (Left n `elem` xs) = numNames (Left n : xs) ps
457 numNames xs (PConst c : ps)
458 | not (Right c `elem` xs) = numNames (Right c : xs) ps
459 numNames xs (_ : ps) = numNames xs ps
460 numNames xs [] = length xs
462match :: [Name] -> [Clause] -> SC -- error case
463 -> CaseBuilder SC
464match [] (([], ret) : xs) err
465 = do (ts, v, ntys) <- get
466 put (ts ++ (map (fst.snd) xs), v, ntys)
467 case snd ret of
468 Impossible -> return ImpossibleCase
469 tm -> return $ STerm tm -- run out of arguments
470match vs cs err = do let ps = partition cs
471 mixture vs ps err
473mixture :: [Name] -> [Partition] -> SC -> CaseBuilder SC
474mixture vs [] err = return err
475mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
476 conRule vs ms fallthrough
477mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
478 varRule vs ms fallthrough
480data ConType = CName Name Int -- named constructor
481 | CFn Name -- reflected function name
482 | CSuc -- n+1
483 | CConst Const -- constant, not implemented yet
484 deriving (Show, Eq)
486data Group = ConGroup ConType -- Constructor
487 [([Pat], Clause)] -- arguments and rest of alternative
488 deriving Show
490conRule :: [Name] -> [Clause] -> SC -> CaseBuilder SC
491conRule (v:vs) cs err = do groups <- groupCons cs
492 caseGroups (v:vs) groups err
494caseGroups :: [Name] -> [Group] -> SC -> CaseBuilder SC
495caseGroups (v:vs) gs err = do g <- altGroups gs
496 return $ Case v (sort g)
497 where
498 altGroups [] = return [DefaultCase err]
499 altGroups (ConGroup (CName n i) args : cs)
500 = do g <- altGroup n i args
501 rest <- altGroups cs
502 return (g : rest)
503 altGroups (ConGroup (CFn n) args : cs)
504 = do g <- altFnGroup n args
505 rest <- altGroups cs
506 return (g : rest)
507 altGroups (ConGroup CSuc args : cs)
508 = do g <- altSucGroup args
509 rest <- altGroups cs
510 return (g : rest)
511 altGroups (ConGroup (CConst c) args : cs)
512 = do g <- altConstGroup c args
513 rest <- altGroups cs
514 return (g : rest)
516 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
517 matchCs <- match (newArgs ++ vs) nextCs err
518 return $ ConCase n i newArgs matchCs
519 altFnGroup n gs = do (newArgs, nextCs) <- argsToAlt gs
520 matchCs <- match (newArgs ++ vs) nextCs err
521 return $ FnCase n newArgs matchCs
522 altSucGroup gs = do ([newArg], nextCs) <- argsToAlt gs
523 matchCs <- match (newArg:vs) nextCs err
524 return $ SucCase newArg matchCs
525 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
526 matchCs <- match vs nextCs err
527 return $ ConstCase n matchCs
529argsToAlt :: [([Pat], Clause)] -> CaseBuilder ([Name], [Clause])
530argsToAlt [] = return ([], [])
531argsToAlt rs@((r, m) : rest)
532 = do newArgs <- getNewVars r
533 return (newArgs, addRs rs)
534 where
535 getNewVars [] = return []
536 getNewVars ((PV n t) : ns) = do v <- getVar "e"
537 (cs, i, ntys) <- get
538 put (cs, i, (v, t) : ntys)
539 nsv <- getNewVars ns
540 return (v : nsv)
541 getNewVars (PAny : ns) = do v <- getVar "i"
542 nsv <- getNewVars ns
543 return (v : nsv)
544 getNewVars (PTyPat : ns) = do v <- getVar "t"
545 nsv <- getNewVars ns
546 return (v : nsv)
547 getNewVars (_ : ns) = do v <- getVar "e"
548 nsv <- getNewVars ns
549 return (v : nsv)
550 addRs [] = []
551 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
553 uniq i (UN n) = MN i n
554 uniq i n = n
556getVar :: String -> CaseBuilder Name
557getVar b = do (t, v, ntys) <- get; put (t, v+1, ntys); return (sMN v b)
559groupCons :: [Clause] -> CaseBuilder [Group]
560groupCons cs = gc [] cs
561 where
562 gc acc [] = return acc
563 gc acc ((p : ps, res) : cs) =
564 do acc' <- addGroup p ps res acc
565 gc acc' cs
566 addGroup p ps res acc = case p of
567 PCon con i args -> return $ addg (CName con i) args (ps, res) acc
568 PConst cval -> return $ addConG cval (ps, res) acc
569 PSuc n -> return $ addg CSuc [n] (ps, res) acc
570 PReflected fn args -> return $ addg (CFn fn) args (ps, res) acc
571 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
573 addg c conargs res []
574 = [ConGroup c [(conargs, res)]]
575 addg c conargs res (g@(ConGroup c' cs):gs)
576 | c == c' = ConGroup c (cs ++ [(conargs, res)]) : gs
577 | otherwise = g : addg c conargs res gs
579 addConG con res [] = [ConGroup (CConst con) [([], res)]]
580 addConG con res (g@(ConGroup (CConst n) cs) : gs)
581 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
582-- | otherwise = g : addConG con res gs
583 addConG con res (g : gs) = g : addConG con res gs
585varRule :: [Name] -> [Clause] -> SC -> CaseBuilder SC
586varRule (v : vs) alts err =
587 do alts' <- mapM (repVar v) alts
588 match vs alts' err
589 where
590 repVar v (PV p ty : ps , (lhs, res))
591 = do (cs, i, ntys) <- get
592 put (cs, i, (v, ty) : ntys)
593 return (ps, (lhs, subst p (P Bound v ty) res))
594 repVar v (PAny : ps , res) = return (ps, res)
595 repVar v (PTyPat : ps , res) = return (ps, res)
597-- fix: case e of S k -> f (S k) ==> case e of S k -> f e
599depatt :: [Name] -> SC -> SC
600depatt ns tm = dp [] tm
601 where
602 dp ms (STerm tm) = STerm (applyMaps ms tm)
603 dp ms (Case x alts) = Case x (map (dpa ms x) alts)
604 dp ms sc = sc
606 dpa ms x (ConCase n i args sc)
607 = ConCase n i args (dp ((x, (n, args)) : ms) sc)
608 dpa ms x (FnCase n args sc)
609 = FnCase n args (dp ((x, (n, args)) : ms) sc)
610 dpa ms x (ConstCase c sc) = ConstCase c (dp ms sc)
611 dpa ms x (SucCase n sc) = SucCase n (dp ms sc)
612 dpa ms x (DefaultCase sc) = DefaultCase (dp ms sc)
614 applyMaps ms f@(App _ _)
615 | (P nt cn pty, args) <- unApply f
616 = let args' = map (applyMaps ms) args in
617 applyMap ms nt cn pty args'
618 where
619 applyMap [] nt cn pty args' = mkApp (P nt cn pty) args'
620 applyMap ((x, (n, args)) : ms) nt cn pty args'
621 | and ((length args == length args') :
622 (n == cn) : zipWith same args args') = P Ref x Erased
623 | otherwise = applyMap ms nt cn pty args'
624 same n (P _ n' _) = n == n'
625 same _ _ = False
627 applyMaps ms (App f a) = App (applyMaps ms f) (applyMaps ms a)
628 applyMaps ms t = t
630-- FIXME: Do this for SucCase too
631prune :: Bool -- ^ Convert single branches to projections (only useful at runtime)
632 -> SC -> SC
633prune proj (Case n alts) = case alts' of
634 [] -> ImpossibleCase
636 -- Projection transformations prevent us from seeing some uses of ctor fields
637 -- because they delete information about which ctor is being used.
638 -- Consider:
639 -- f (X x) = ... x ...
640 -- vs.
641 -- f x = ... x!0 ...
642 --
643 -- Hence, we disable this step.
644 -- TODO: re-enable this in toIR
645 --
646 -- as@[ConCase cn i args sc]
647 -- | proj -> mkProj n 0 args (prune proj sc)
648 -- mkProj n i xs sc = foldr (\x -> projRep x n i) sc xs
650 -- If none of the args are used in the sc, however, we can just replace it
651 -- with sc
652 as@[ConCase cn i args sc]
653 | proj -> let sc' = prune proj sc in
654 if any (isUsed sc') args
655 then Case n [ConCase cn i args sc']
656 else sc'
658 [SucCase cn sc]
659 | proj
660 -> projRep cn n (-1) $ prune proj sc
662 [ConstCase _ sc]
663 -> prune proj sc
665 -- Bit of a hack here! The default case will always be 0, make sure
666 -- it gets caught first.
667 [s@(SucCase _ _), DefaultCase dc]
668 -> Case n [ConstCase (BI 0) dc, s]
670 as -> Case n as
671 where
672 alts' = filter (not . erased) $ map pruneAlt alts
674 pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune proj sc)
675 pruneAlt (FnCase cn ns sc) = FnCase cn ns (prune proj sc)
676 pruneAlt (ConstCase c sc) = ConstCase c (prune proj sc)
677 pruneAlt (SucCase n sc) = SucCase n (prune proj sc)
678 pruneAlt (DefaultCase sc) = DefaultCase (prune proj sc)
680 erased (DefaultCase (STerm Erased)) = True
681 erased (DefaultCase ImpossibleCase) = True
682 erased _ = False
684 projRep :: Name -> Name -> Int -> SC -> SC
685 projRep arg n i (Case x alts) | x == arg
686 = ProjCase (Proj (P Bound n Erased) i) $ map (projRepAlt arg n i) alts
687 projRep arg n i (Case x alts)
688 = Case x (map (projRepAlt arg n i) alts)
689 projRep arg n i (ProjCase t alts)
690 = ProjCase (projRepTm arg n i t) $ map (projRepAlt arg n i) alts
691 projRep arg n i (STerm t) = STerm (projRepTm arg n i t)
692 projRep arg n i c = c
694 projRepAlt arg n i (ConCase cn t args rhs)
695 = ConCase cn t args (projRep arg n i rhs)
696 projRepAlt arg n i (FnCase cn args rhs)
697 = FnCase cn args (projRep arg n i rhs)
698 projRepAlt arg n i (ConstCase t rhs)
699 = ConstCase t (projRep arg n i rhs)
700 projRepAlt arg n i (SucCase sn rhs)
701 = SucCase sn (projRep arg n i rhs)
702 projRepAlt arg n i (DefaultCase rhs)
703 = DefaultCase (projRep arg n i rhs)
705 projRepTm arg n i t = subst arg (Proj (P Bound n Erased) i) t
707prune _ t = t
709stripLambdas :: CaseDef -> CaseDef
710stripLambdas (CaseDef ns (STerm (Bind x (Lam _) sc)) tm)
711 = stripLambdas (CaseDef (ns ++ [x]) (STerm (instantiate (P Bound x Erased) sc)) tm)
712stripLambdas x = x
714substSC :: Name -> Name -> SC -> SC
715substSC n repl (Case n' alts)
716 | n == n' = Case repl (map (substAlt n repl) alts)
717 | otherwise = Case n' (map (substAlt n repl) alts)
718substSC n repl (STerm t) = STerm $ subst n (P Bound repl Erased) t
719substSC n repl (UnmatchedCase errmsg) = UnmatchedCase errmsg
720substSC n repl ImpossibleCase = ImpossibleCase
721substSC n repl sc = error $ "unsupported in substSC: " ++ show sc
723substAlt :: Name -> Name -> CaseAlt -> CaseAlt
724substAlt n repl (ConCase cn a ns sc) = ConCase cn a ns (substSC n repl sc)
725substAlt n repl (FnCase fn ns sc) = FnCase fn ns (substSC n repl sc)
726substAlt n repl (ConstCase c sc) = ConstCase c (substSC n repl sc)
727substAlt n repl (SucCase n' sc)
728 | n == n' = SucCase n (substSC n repl sc)
729 | otherwise = SucCase n' (substSC n repl sc)
730substAlt n repl (DefaultCase sc) = DefaultCase (substSC n repl sc)
732mkForce :: Name -> Name -> SC -> SC
733mkForce = mkForceSC
734 where
735 mkForceSC n arg (Case x alts) | x == arg
736 = ProjCase (forceArg n) $ map (mkForceAlt n arg) alts
738 mkForceSC n arg (Case x alts)
739 = Case x (map (mkForceAlt n arg) alts)
741 mkForceSC n arg (ProjCase t alts)
742 = ProjCase (forceTm n arg t) $ map (mkForceAlt n arg) alts
744 mkForceSC n arg (STerm t) = STerm (forceTm n arg t)
745 mkForceSC n arg c = c
747 mkForceAlt n arg (ConCase cn t args rhs)
748 = ConCase cn t args (mkForceSC n arg rhs)
749 mkForceAlt n arg (FnCase cn args rhs)
750 = FnCase cn args (mkForceSC n arg rhs)
751 mkForceAlt n arg (ConstCase t rhs)
752 = ConstCase t (mkForceSC n arg rhs)
753 mkForceAlt n arg (SucCase sn rhs)
754 = SucCase sn (mkForceSC n arg rhs)
755 mkForceAlt n arg (DefaultCase rhs)
756 = DefaultCase (mkForceSC n arg rhs)
758 forceTm n arg t = subst arg (forceArg n) t
760 forceArg n = App (App (App (P Ref (sUN "Force") Erased) Erased) Erased)
761 (P Bound n Erased)