git.iko.soy/Idris-dev
on 3cb1f21 help sign in
Idris-dev/src/Idris/Core/CaseTree.hs
636 lines 26 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) where
7import Idris.Core.TT
9import Control.Monad.State
10import Data.Maybe
11import Data.List hiding (partition)
12import Debug.Trace
14data CaseDef = CaseDef [Name] !SC [Term]
15 deriving Show
17data SC' t = Case Name [CaseAlt' t] -- ^ invariant: lowest tags first
18 | ProjCase t [CaseAlt' t] -- ^ special case for projections
19 | STerm !t
20 | UnmatchedCase String -- ^ error message
21 | ImpossibleCase -- ^ already checked to be impossible
22 deriving (Eq, Ord, Functor)
23{-!
24deriving instance Binary SC'
25deriving instance NFData SC'
26!-}
28type SC = SC' Term
30data CaseAlt' t = ConCase Name Int [Name] !(SC' t)
31 | FnCase Name [Name] !(SC' t) -- ^ reflection function
32 | ConstCase Const !(SC' t)
33 | SucCase Name !(SC' t)
34 | DefaultCase !(SC' t)
35 deriving (Show, Eq, Ord, Functor)
36{-!
37deriving instance Binary CaseAlt'
38deriving instance NFData CaseAlt'
39!-}
41type CaseAlt = CaseAlt' Term
43instance Show t => Show (SC' t) where
44 show sc = show' 1 sc
45 where
46 show' i (Case n alts) = "case " ++ show n ++ " of\n" ++ indent i ++
47 showSep ("\n" ++ indent i) (map (showA i) alts)
48 show' i (ProjCase tm alts) = "case " ++ show tm ++ " of " ++
49 showSep ("\n" ++ indent i) (map (showA i) alts)
50 show' i (STerm tm) = show tm
51 show' i (UnmatchedCase str) = "error " ++ show str
52 show' i ImpossibleCase = "impossible"
54 indent i = concat $ take i (repeat " ")
56 showA i (ConCase n t args sc)
57 = show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
58 ++ show' (i+1) sc
59 showA i (FnCase n args sc)
60 = "FN " ++ show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
61 ++ show' (i+1) sc
62 showA i (ConstCase t sc)
63 = show t ++ " => " ++ show' (i+1) sc
64 showA i (SucCase n sc)
65 = show n ++ "+1 => " ++ show' (i+1) sc
66 showA i (DefaultCase sc)
67 = "_ => " ++ show' (i+1) sc
70type CaseTree = SC
71type Clause = ([Pat], (Term, Term))
72type CS = ([Term], Int, [(Name, Type)])
74instance TermSize SC where
75 termsize n (Case n' as) = termsize n as
76 termsize n (ProjCase n' as) = termsize n as
77 termsize n (STerm t) = termsize n t
78 termsize n _ = 1
80instance TermSize CaseAlt where
81 termsize n (ConCase _ _ _ s) = termsize n s
82 termsize n (FnCase _ _ s) = termsize n s
83 termsize n (ConstCase _ s) = termsize n s
84 termsize n (SucCase _ s) = termsize n s
85 termsize n (DefaultCase s) = termsize n s
87-- simple terms can be inlined trivially - good for primitives in particular
88-- To avoid duplicating work, don't inline something which uses one
89-- of its arguments in more than one place
91small :: Name -> [Name] -> SC -> Bool
92small n args t = let as = findAllUsedArgs t args in
93 length as == length (nub as) &&
94 termsize n t < 10
96namesUsed :: SC -> [Name]
97namesUsed sc = nub $ nu' [] sc where
98 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
99 nu' ps (ProjCase t alts) = nub $ (nut ps t ++
100 (concatMap (nua ps) alts))
101 nu' ps (STerm t) = nub $ nut ps t
102 nu' ps _ = []
104 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
105 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc) \\ args
106 nua ps (ConstCase _ sc) = nu' ps sc
107 nua ps (SucCase _ sc) = nu' ps sc
108 nua ps (DefaultCase sc) = nu' ps sc
110 nut ps (P _ n _) | n `elem` ps = []
111 | otherwise = [n]
112 nut ps (App f a) = nut ps f ++ nut ps a
113 nut ps (Proj t _) = nut ps t
114 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
115 nut ps (Bind n b sc) = nut (n:ps) sc
116 nut ps _ = []
118-- Return all called functions, and which arguments are used in each argument position
119-- for the call, in order to help reduce compilation time, and trace all unused
120-- arguments
122findCalls :: SC -> [Name] -> [(Name, [[Name]])]
123findCalls sc topargs = nub $ nu' topargs sc where
124 nu' ps (Case n alts) = nub (concatMap (nua (n : ps)) alts)
125 nu' ps (ProjCase t alts) = nub (nut ps t ++ concatMap (nua ps) alts)
126 nu' ps (STerm t) = nub $ nut ps t
127 nu' ps _ = []
129 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc)
130 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc)
131 nua ps (ConstCase _ sc) = nu' ps sc
132 nua ps (SucCase _ sc) = nu' ps sc
133 nua ps (DefaultCase sc) = nu' ps sc
135 nut ps (P Ref n _) | n `elem` ps = []
136 | otherwise = [(n, [])] -- tmp
137 nut ps fn@(App f a)
138 | (P Ref n _, args) <- unApply fn
139 = if n `elem` ps then nut ps f ++ nut ps a
140 else [(n, map argNames args)] ++ concatMap (nut ps) args
141 | (P (TCon _ _) n _, _) <- unApply fn = []
142 | otherwise = nut ps f ++ nut ps a
143 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
144 nut ps (Proj t _) = nut ps t
145 nut ps (Bind n b sc) = nut (n:ps) sc
146 nut ps _ = []
148 argNames tm = let ns = directUse tm in
149 filter (\x -> x `elem` ns) topargs
151-- Find names which are used directly (i.e. not in a function call) in a term
153directUse :: Eq n => TT n -> [n]
154directUse (P _ n _) = [n]
155directUse (Bind n (Let t v) sc) = nub $ directUse v ++ (directUse sc \\ [n])
156 ++ directUse t
157directUse (Bind n b sc) = nub $ directUse (binderTy b) ++ (directUse sc \\ [n])
158directUse fn@(App f a)
159 | (P Ref n _, args) <- unApply fn = [] -- need to know what n does with them
160 | (P (TCon _ _) n _, args) <- unApply fn = [] -- type constructors not used at runtime
161 | otherwise = nub $ directUse f ++ directUse a
162directUse (Proj x i) = nub $ directUse x
163directUse _ = []
165-- Find all directly used arguments (i.e. used but not in function calls)
167findUsedArgs :: SC -> [Name] -> [Name]
168findUsedArgs sc topargs = nub (findAllUsedArgs sc topargs)
170findAllUsedArgs sc topargs = filter (\x -> x `elem` topargs) (nu' sc) where
171 nu' (Case n alts) = n : concatMap nua alts
172 nu' (ProjCase t alts) = directUse t ++ concatMap nua alts
173 nu' (STerm t) = directUse t
174 nu' _ = []
176 nua (ConCase n i args sc) = nu' sc
177 nua (FnCase n args sc) = nu' sc
178 nua (ConstCase _ sc) = nu' sc
179 nua (SucCase _ sc) = nu' sc
180 nua (DefaultCase sc) = nu' sc
182data Phase = CompileTime | RunTime
183 deriving (Show, Eq)
185-- Generate a simple case tree
186-- Work Right to Left
188simpleCase :: Bool -> Bool -> Bool ->
189 Phase -> FC -> [Type] ->
190 [([Name], Term, Term)] ->
191 TC CaseDef
192simpleCase tc cover reflect phase fc argtys cs
193 = sc' tc cover phase fc (filter (\(_, _, r) ->
194 case r of
195 Impossible -> False
196 _ -> True) cs)
197 where
198 sc' tc cover phase fc []
199 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
200 sc' tc cover phase fc cs
201 = let proj = phase == RunTime
202 vnames = fstT (head cs)
203 pats = map (\ (avs, l, r) ->
204 (avs, toPats reflect tc l, (l, r))) cs
205 chkPats = mapM chkAccessible pats in
206 case chkPats of
207 OK pats ->
208 let numargs = length (fst (head pats))
209 ns = take numargs args
210 (ns', ps') = order ns pats
211 (tree, st) = runState
212 (match ns' ps' (defaultCase cover))
213 ([], numargs, [])
214 t = CaseDef ns (prune proj (depatt ns' tree)) (fstT st) in
215 if proj then return (stripLambdas t)
216 else if checkSameTypes (lstT st) tree
217 then return t
218 else Error (At fc (Msg "Typecase is not allowed"))
219 Error err -> Error (At fc err)
220 where args = map (\i -> sMN i "e") [0..]
221 defaultCase True = STerm Erased
222 defaultCase False = UnmatchedCase "Error"
223 fstT (x, _, _) = x
224 lstT (_, _, x) = x
226 chkAccessible (avs, l, c)
227 | phase == RunTime || reflect = return (l, c)
228 | otherwise = do mapM_ (acc l) avs
229 return (l, c)
231 acc [] n = Error (Inaccessible n)
232 acc (PV x t : xs) n | x == n = OK ()
233 acc (PCon _ _ ps : xs) n = acc (ps ++ xs) n
234 acc (PSuc p : xs) n = acc (p : xs) n
235 acc (_ : xs) n = acc xs n
237-- For each 'Case', make sure every choice is in the same type family,
238-- as directed by the variable type (i.e. there is no implicit type casing
239-- going on).
241checkSameTypes :: [(Name, Type)] -> SC -> Bool
242checkSameTypes tys (Case n alts)
243 = case lookup n tys of
244 Just t -> and (map (checkAlts t) alts)
245 _ -> and (map ((checkSameTypes tys).getSC) alts)
246 where
247 checkAlts t (ConCase n _ _ sc) = isType n t && checkSameTypes tys sc
248 checkAlts (Constant t) (ConstCase c sc) = isConstType c t && checkSameTypes tys sc
249 checkAlts _ (ConstCase c sc) = False
250 checkAlts _ _ = True
252 getSC (ConCase _ _ _ sc) = sc
253 getSC (FnCase _ _ sc) = sc
254 getSC (ConstCase _ sc) = sc
255 getSC (SucCase _ sc) = sc
256 getSC (DefaultCase sc) = sc
257checkSameTypes _ _ = True
259-- FIXME: All we're actually doing here is checking that we haven't arrived
260-- at a specific constructor for a polymorphic argument. I *think* this
261-- is sufficient, but if it turns out not to be, fix it!
262isType n t | (P (TCon _ _) _ _, _) <- unApply t = True
263isType n t | (P Ref _ _, _) <- unApply t = True
264isType n t = False
266isConstType (I _) (AType (ATInt ITNative)) = True
267isConstType (BI _) (AType (ATInt ITBig)) = True
268isConstType (Fl _) (AType ATFloat) = True
269isConstType (Ch _) (AType (ATInt ITChar)) = True
270isConstType (Str _) StrType = True
271isConstType (B8 _) (AType (ATInt _)) = True
272isConstType (B16 _) (AType (ATInt _)) = True
273isConstType (B32 _) (AType (ATInt _)) = True
274isConstType (B64 _) (AType (ATInt _)) = True
275isConstType (B8V _) (AType (ATInt _)) = True
276isConstType (B16V _) (AType (ATInt _)) = True
277isConstType (B32V _) (AType (ATInt _)) = True
278isConstType (B64V _) (AType (ATInt _)) = True
279isConstType _ _ = False
281data Pat = PCon Name Int [Pat]
282 | PConst Const
283 | PV Name Type
284 | PSuc Pat -- special case for n+1 on Integer
285 | PReflected Name [Pat]
286 | PAny
287 | PTyPat -- typecase, not allowed, inspect last
288 deriving Show
290-- If there are repeated variables, take the *last* one (could be name shadowing
291-- in a where clause, so take the most recent).
293toPats :: Bool -> Bool -> Term -> [Pat]
294toPats reflect tc f = reverse (toPat reflect tc (getArgs f)) where
295 getArgs (App f a) = a : getArgs f
296 getArgs _ = []
298toPat :: Bool -> Bool -> [Term] -> [Pat]
299toPat reflect tc tms = evalState (mapM (\x -> toPat' x []) tms) []
300 where
301 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
302 return $ PCon n t args'
303 -- n + 1
304 toPat' (P _ (UN pabi) _)
305 [p, Constant (BI 1)] | pabi == txt "prim__addBigInt"
306 = do p' <- toPat' p []
307 return $ PSuc p'
308 -- Typecase
309-- toPat' (P (TCon t a) n _) args | tc
310-- = do args' <- mapM (\x -> toPat' x []) args
311-- return $ PCon n t args'
312-- toPat' (Constant (AType (ATInt ITNative))) []
313-- | tc = return $ PCon (UN "Int") 1 []
314-- toPat' (Constant (AType ATFloat)) [] | tc = return $ PCon (UN "Float") 2 []
315-- toPat' (Constant (AType (ATInt ITChar))) [] | tc = return $ PCon (UN "Char") 3 []
316-- toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
317-- toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
318-- toPat' (Constant (AType (ATInt ITBig))) []
319-- | tc = return $ PCon (UN "Integer") 6 []
320-- toPat' (Constant (AType (ATInt (ITFixed n)))) []
321-- | tc = return $ PCon (UN (fixedN n)) (7 + fromEnum n) [] -- 7-10 inclusive
322 toPat' (P Bound n ty) [] = -- trace (show (n, ty)) $
323 do ns <- get
324 if n `elem` ns
325 then return PAny
326 else do put (n : ns)
327 return (PV n ty)
328 toPat' (App f a) args = toPat' f (a : args)
329 toPat' (Constant (AType _)) [] = return PTyPat
330 toPat' (Constant StrType) [] = return PTyPat
331 toPat' (Constant PtrType) [] = return PTyPat
332 toPat' (Constant VoidType) [] = return PTyPat
333 toPat' (Constant x) [] = return $ PConst x
334 toPat' (Bind n (Pi t) sc) [] | reflect && noOccurrence n sc
335 = do t' <- toPat' t []
336 sc' <- toPat' sc []
337 return $ PReflected (sUN "->") (t':sc':[])
338 toPat' (P _ n _) args | reflect
339 = do args' <- mapM (\x -> toPat' x []) args
340 return $ PReflected n args'
341 toPat' t _ = return PAny
343 fixedN IT8 = "Bits8"
344 fixedN IT16 = "Bits16"
345 fixedN IT32 = "Bits32"
346 fixedN IT64 = "Bits64"
349data Partition = Cons [Clause]
350 | Vars [Clause]
351 deriving Show
353isVarPat (PV _ _ : ps , _) = True
354isVarPat (PAny : ps , _) = True
355isVarPat (PTyPat : ps , _) = True
356isVarPat _ = False
358isConPat (PCon _ _ _ : ps, _) = True
359isConPat (PReflected _ _ : ps, _) = True
360isConPat (PSuc _ : ps, _) = True
361isConPat (PConst _ : ps, _) = True
362isConPat _ = False
364partition :: [Clause] -> [Partition]
365partition [] = []
366partition ms@(m : _)
367 | isVarPat m = let (vars, rest) = span isVarPat ms in
368 Vars vars : partition rest
369 | isConPat m = let (cons, rest) = span isConPat ms in
370 Cons cons : partition rest
371partition xs = error $ "Partition " ++ show xs
373-- reorder the patterns so that the one with most distinct names
374-- comes next. Take rightmost first, otherwise (i.e. pick value rather
375-- than dependency)
377order :: [Name] -> [Clause] -> ([Name], [Clause])
378order [] cs = ([], cs)
379order ns [] = (ns, [])
380order ns cs = let patnames = transpose (map (zip ns) (map fst cs))
381 pats' = transpose (sortBy moreDistinct (reverse patnames)) in
382 (getNOrder pats', zipWith rebuild pats' cs)
383 where
384 getNOrder [] = error $ "Failed order on " ++ show (ns, cs)
385 getNOrder (c : _) = map fst c
387 rebuild patnames clause = (map snd patnames, snd clause)
389 moreDistinct xs ys = compare (numNames [] (map snd ys))
390 (numNames [] (map snd xs))
392 numNames xs (PCon n _ _ : ps)
393 | not (Left n `elem` xs) = numNames (Left n : xs) ps
394 numNames xs (PConst c : ps)
395 | not (Right c `elem` xs) = numNames (Right c : xs) ps
396 numNames xs (_ : ps) = numNames xs ps
397 numNames xs [] = length xs
399match :: [Name] -> [Clause] -> SC -- error case
400 -> State CS SC
401match [] (([], ret) : xs) err
402 = do (ts, v, ntys) <- get
403 put (ts ++ (map (fst.snd) xs), v, ntys)
404 case snd ret of
405 Impossible -> return ImpossibleCase
406 tm -> return $ STerm tm -- run out of arguments
407match vs cs err = do let ps = partition cs
408 mixture vs ps err
410mixture :: [Name] -> [Partition] -> SC -> State CS SC
411mixture vs [] err = return err
412mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
413 conRule vs ms fallthrough
414mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
415 varRule vs ms fallthrough
417data ConType = CName Name Int -- named constructor
418 | CFn Name -- reflected function name
419 | CSuc -- n+1
420 | CConst Const -- constant, not implemented yet
421 deriving (Show, Eq)
423data Group = ConGroup ConType -- Constructor
424 [([Pat], Clause)] -- arguments and rest of alternative
425 deriving Show
427conRule :: [Name] -> [Clause] -> SC -> State CS SC
428conRule (v:vs) cs err = do groups <- groupCons cs
429 caseGroups (v:vs) groups err
431caseGroups :: [Name] -> [Group] -> SC -> State CS SC
432caseGroups (v:vs) gs err = do g <- altGroups gs
433 return $ Case v (sort g)
434 where
435 altGroups [] = return [DefaultCase err]
436 altGroups (ConGroup (CName n i) args : cs)
437 = do g <- altGroup n i args
438 rest <- altGroups cs
439 return (g : rest)
440 altGroups (ConGroup (CFn n) args : cs)
441 = do g <- altFnGroup n args
442 rest <- altGroups cs
443 return (g : rest)
444 altGroups (ConGroup CSuc args : cs)
445 = do g <- altSucGroup args
446 rest <- altGroups cs
447 return (g : rest)
448 altGroups (ConGroup (CConst c) args : cs)
449 = do g <- altConstGroup c args
450 rest <- altGroups cs
451 return (g : rest)
453 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
454 matchCs <- match (newArgs ++ vs) nextCs err
455 return $ ConCase n i newArgs matchCs
456 altFnGroup n gs = do (newArgs, nextCs) <- argsToAlt gs
457 matchCs <- match (newArgs ++ vs) nextCs err
458 return $ FnCase n newArgs matchCs
459 altSucGroup gs = do ([newArg], nextCs) <- argsToAlt gs
460 matchCs <- match (newArg:vs) nextCs err
461 return $ SucCase newArg matchCs
462 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
463 matchCs <- match vs nextCs err
464 return $ ConstCase n matchCs
466argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
467argsToAlt [] = return ([], [])
468argsToAlt rs@((r, m) : rest)
469 = do newArgs <- getNewVars r
470 return (newArgs, addRs rs)
471 where
472 getNewVars [] = return []
473 getNewVars ((PV n t) : ns) = do v <- getVar "e"
474 (cs, i, ntys) <- get
475 put (cs, i, (v, t) : ntys)
476 nsv <- getNewVars ns
477 return (v : nsv)
478 getNewVars (PAny : ns) = do v <- getVar "i"
479 nsv <- getNewVars ns
480 return (v : nsv)
481 getNewVars (PTyPat : ns) = do v <- getVar "t"
482 nsv <- getNewVars ns
483 return (v : nsv)
484 getNewVars (_ : ns) = do v <- getVar "e"
485 nsv <- getNewVars ns
486 return (v : nsv)
487 addRs [] = []
488 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
490 uniq i (UN n) = MN i n
491 uniq i n = n
493getVar :: String -> State CS Name
494getVar b = do (t, v, ntys) <- get; put (t, v+1, ntys); return (sMN v b)
496groupCons :: [Clause] -> State CS [Group]
497groupCons cs = gc [] cs
498 where
499 gc acc [] = return acc
500 gc acc ((p : ps, res) : cs) =
501 do acc' <- addGroup p ps res acc
502 gc acc' cs
503 addGroup p ps res acc = case p of
504 PCon con i args -> return $ addg (CName con i) args (ps, res) acc
505 PConst cval -> return $ addConG cval (ps, res) acc
506 PSuc n -> return $ addg CSuc [n] (ps, res) acc
507 PReflected fn args -> return $ addg (CFn fn) args (ps, res) acc
508 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
510 addg c conargs res []
511 = [ConGroup c [(conargs, res)]]
512 addg c conargs res (g@(ConGroup c' cs):gs)
513 | c == c' = ConGroup c (cs ++ [(conargs, res)]) : gs
514 | otherwise = g : addg c conargs res gs
516 addConG con res [] = [ConGroup (CConst con) [([], res)]]
517 addConG con res (g@(ConGroup (CConst n) cs) : gs)
518 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
519-- | otherwise = g : addConG con res gs
520 addConG con res (g : gs) = g : addConG con res gs
522varRule :: [Name] -> [Clause] -> SC -> State CS SC
523varRule (v : vs) alts err =
524 do alts' <- mapM (repVar v) alts
525 match vs alts' err
526 where
527 repVar v (PV p ty : ps , (lhs, res))
528 = do (cs, i, ntys) <- get
529 put (cs, i, (v, ty) : ntys)
530 return (ps, (lhs, subst p (P Bound v ty) res))
531 repVar v (PAny : ps , res) = return (ps, res)
532 repVar v (PTyPat : ps , res) = return (ps, res)
534-- fix: case e of S k -> f (S k) ==> case e of S k -> f e
536depatt :: [Name] -> SC -> SC
537depatt ns tm = dp [] tm
538 where
539 dp ms (STerm tm) = STerm (applyMaps ms tm)
540 dp ms (Case x alts) = Case x (map (dpa ms x) alts)
541 dp ms sc = sc
543 dpa ms x (ConCase n i args sc)
544 = ConCase n i args (dp ((x, (n, args)) : ms) sc)
545 dpa ms x (FnCase n args sc)
546 = FnCase n args (dp ((x, (n, args)) : ms) sc)
547 dpa ms x (ConstCase c sc) = ConstCase c (dp ms sc)
548 dpa ms x (SucCase n sc) = SucCase n (dp ms sc)
549 dpa ms x (DefaultCase sc) = DefaultCase (dp ms sc)
551 applyMaps ms f@(App _ _)
552 | (P nt cn pty, args) <- unApply f
553 = let args' = map (applyMaps ms) args in
554 applyMap ms nt cn pty args'
555 where
556 applyMap [] nt cn pty args' = mkApp (P nt cn pty) args'
557 applyMap ((x, (n, args)) : ms) nt cn pty args'
558 | and ((length args == length args') :
559 (n == cn) : zipWith same args args') = P Ref x Erased
560 | otherwise = applyMap ms nt cn pty args'
561 same n (P _ n' _) = n == n'
562 same _ _ = False
564 applyMaps ms (App f a) = App (applyMaps ms f) (applyMaps ms a)
565 applyMaps ms t = t
567-- FIXME: Do this for SucCase too
568prune :: Bool -- ^ Convert single branches to projections (only useful at runtime)
569 -> SC -> SC
570prune proj (Case n alts)
571 = let alts' = filter notErased (map pruneAlt alts) in
572 case alts' of
573 [] -> ImpossibleCase
574 as@[ConCase cn i args sc] -> if proj then mkProj n 0 args sc
575 else Case n as
576 as@[SucCase cn sc] -> if proj then mkProj n (-1) [cn] sc
577 else Case n as
578 as@[ConstCase _ sc] -> prune proj sc
579 -- Bit of a hack here! The default case will always be 0, make sure
580 -- it gets caught first.
581 [s@(SucCase _ _), DefaultCase dc]
582 -> Case n [ConstCase (BI 0) dc, s]
583 as -> Case n as
584 where pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune proj sc)
585 pruneAlt (FnCase cn ns sc) = FnCase cn ns (prune proj sc)
586 pruneAlt (ConstCase c sc) = ConstCase c (prune proj sc)
587 pruneAlt (SucCase n sc) = SucCase n (prune proj sc)
588 pruneAlt (DefaultCase sc) = DefaultCase (prune proj sc)
590 notErased (DefaultCase (STerm Erased)) = False
591 notErased (DefaultCase ImpossibleCase) = False
592 notErased _ = True
594 mkProj n i [] sc = prune proj sc
595 mkProj n i (x : xs) sc = mkProj n (i + 1) xs (projRep x n i sc)
597 -- Change every 'n' in sc to 'n-1'
598-- mkProjS n cn sc = prune proj (fmap projn sc) where
599-- projn pn@(P _ n' _)
600-- | cn == n' = App (App (P Ref (UN "prim__subBigInt") Erased)
601-- (P Bound n Erased)) (Constant (BI 1))
602-- projn t = t
604 projRep :: Name -> Name -> Int -> SC -> SC
605 projRep arg n i (Case x alts)
606 | x == arg = ProjCase (Proj (P Bound n Erased) i)
607 (map (projRepAlt arg n i) alts)
608 | otherwise = Case x (map (projRepAlt arg n i) alts)
609 projRep arg n i (ProjCase t alts)
610 = ProjCase (projRepTm arg n i t) (map (projRepAlt arg n i) alts)
611 projRep arg n i (STerm t) = STerm (projRepTm arg n i t)
612 projRep arg n i c = c -- unmatched
614 projRepAlt arg n i (ConCase cn t args rhs)
615 = ConCase cn t args (projRep arg n i rhs)
616 projRepAlt arg n i (FnCase cn args rhs)
617 = FnCase cn args (projRep arg n i rhs)
618 projRepAlt arg n i (ConstCase t rhs)
619 = ConstCase t (projRep arg n i rhs)
620 projRepAlt arg n i (SucCase sn rhs)
621 = SucCase sn (projRep arg n i rhs)
622 projRepAlt arg n i (DefaultCase rhs)
623 = DefaultCase (projRep arg n i rhs)
625 projRepTm arg n i t = subst arg (Proj (P Bound n Erased) i) t
627prune _ t = t
629stripLambdas :: CaseDef -> CaseDef
630stripLambdas (CaseDef ns (STerm (Bind x (Lam _) sc)) tm)
631 = stripLambdas (CaseDef (ns ++ [x]) (STerm (instantiate (P Bound x Erased) sc)) tm)
632stripLambdas x = x