git.iko.soy/Idris-dev
on 7ada264 help sign in
Idris-dev/src/Idris/Core/CaseTree.hs
704 lines 29 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) where
8import Idris.Core.TT
10import Control.Monad.State
11import Data.Maybe
12import Data.List hiding (partition)
13import Debug.Trace
15data CaseDef = CaseDef [Name] !SC [Term]
16 deriving Show
18data SC' t = Case Name [CaseAlt' t] -- ^ invariant: lowest tags first
19 | ProjCase t (CaseAlt' t) -- ^ special case for projections
20 | STerm !t
21 | UnmatchedCase String -- ^ error message
22 | ImpossibleCase -- ^ already checked to be impossible
23 deriving (Eq, Ord, Functor)
24{-!
25deriving instance Binary SC'
26deriving instance NFData SC'
27!-}
29type SC = SC' Term
31data CaseAlt' t = ConCase Name Int [Name] !(SC' t)
32 | FnCase Name [Name] !(SC' t) -- ^ reflection function
33 | ConstCase Const !(SC' t)
34 | SucCase Name !(SC' t)
35 | DefaultCase !(SC' t)
36 deriving (Show, Eq, Ord, Functor)
37{-!
38deriving instance Binary CaseAlt'
39deriving instance NFData CaseAlt'
40!-}
42type CaseAlt = CaseAlt' Term
44instance Show t => Show (SC' t) where
45 show sc = show' 1 sc
46 where
47 show' i (Case n alts) = "case " ++ show n ++ " of\n" ++ indent i ++
48 showSep ("\n" ++ indent i) (map (showA i) alts)
49 show' i (ProjCase tm alt) = "case " ++ show tm ++ " of " ++
50 showSep ("\n" ++ indent i) (map (showA i) [alt])
51 show' i (STerm tm) = show tm
52 show' i (UnmatchedCase str) = "error " ++ show str
53 show' i ImpossibleCase = "impossible"
55 indent i = concat $ take i (repeat " ")
57 showA i (ConCase n t args sc)
58 = show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
59 ++ show' (i+1) sc
60 showA i (FnCase n args sc)
61 = "FN " ++ show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
62 ++ show' (i+1) sc
63 showA i (ConstCase t sc)
64 = show t ++ " => " ++ show' (i+1) sc
65 showA i (SucCase n sc)
66 = show n ++ "+1 => " ++ show' (i+1) sc
67 showA i (DefaultCase sc)
68 = "_ => " ++ show' (i+1) sc
71type CaseTree = SC
72type Clause = ([Pat], (Term, Term))
73type CS = ([Term], Int, [(Name, Type)])
75instance TermSize SC where
76 termsize n (Case n' as) = termsize n as
77 termsize n (ProjCase n' as) = termsize n as
78 termsize n (STerm t) = termsize n t
79 termsize n _ = 1
81instance TermSize CaseAlt where
82 termsize n (ConCase _ _ _ s) = termsize n s
83 termsize n (FnCase _ _ s) = termsize n s
84 termsize n (ConstCase _ s) = termsize n s
85 termsize n (SucCase _ s) = termsize n s
86 termsize n (DefaultCase s) = termsize n s
88-- simple terms can be inlined trivially - good for primitives in particular
89-- To avoid duplicating work, don't inline something which uses one
90-- of its arguments in more than one place
92small :: Name -> [Name] -> SC -> Bool
93small n args t = let as = findAllUsedArgs t args in
94 length as == length (nub as) &&
95 termsize n t < 10
97namesUsed :: SC -> [Name]
98namesUsed sc = nub $ nu' [] sc where
99 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
100 nu' ps (ProjCase t alt) = nub $ nut ps t ++ nua ps alt
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 alt) = nub (nut ps t ++ nua ps alt)
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 :: TT Name -> [Name]
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 (UN pfk) _, [App e w]) <- unApply fn,
160 pfk == txt "prim_fork"
161 = directUse e ++ directUse w -- HACK so that fork works
162 | (P Ref (UN fce) _, [_, _, a]) <- unApply fn,
163 fce == txt "Force"
164 = directUse a -- forcing a value counts as a use
165 | (P Ref n _, args) <- unApply fn = [] -- need to know what n does with them
166 | (P (TCon _ _) n _, args) <- unApply fn = [] -- type constructors not used at runtime
167 | otherwise = nub $ directUse f ++ directUse a
168directUse (Proj x i) = nub $ directUse x
169directUse _ = []
171-- Find all directly used arguments (i.e. used but not in function calls)
173findUsedArgs :: SC -> [Name] -> [Name]
174findUsedArgs sc topargs = nub (findAllUsedArgs sc topargs)
176findAllUsedArgs sc topargs = filter (\x -> x `elem` topargs) (nu' sc) where
177 nu' (Case n alts) = n : concatMap nua alts
178 nu' (ProjCase t alt) = directUse t ++ nua alt
179 nu' (STerm t) = directUse t
180 nu' _ = []
182 nua (ConCase n i args sc) = nu' sc
183 nua (FnCase n args sc) = nu' sc
184 nua (ConstCase _ sc) = nu' sc
185 nua (SucCase _ sc) = nu' sc
186 nua (DefaultCase sc) = nu' sc
188data Phase = CompileTime | RunTime
189 deriving (Show, Eq)
191-- Generate a simple case tree
192-- Work Right to Left
194simpleCase :: Bool -> Bool -> Bool ->
195 Phase -> FC -> [Int] -> [Type] ->
196 [([Name], Term, Term)] ->
197 TC CaseDef
198simpleCase tc cover reflect phase fc inacc argtys cs
199 = sc' tc cover phase fc (filter (\(_, _, r) ->
200 case r of
201 Impossible -> False
202 _ -> True) cs)
203 where
204 sc' tc cover phase fc []
205 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
206 sc' tc cover phase fc cs
207 = let proj = phase == RunTime
208 vnames = fstT (head cs)
209 pats = map (\ (avs, l, r) ->
210 (avs, toPats reflect tc l, (l, r))) cs
211 chkPats = mapM chkAccessible pats in
212 case chkPats of
213 OK pats ->
214 let numargs = length (fst (head pats))
215 ns = take numargs args
216 (ns', ps') = order [(n, i `elem` inacc) | (i,n) <- zip [0..] ns] pats
217 (tree, st) = runState
218 (match ns' ps' (defaultCase cover))
219 ([], numargs, [])
220 t = CaseDef ns (prune proj (depatt ns' tree)) (fstT st) in
221 if proj then return (stripLambdas t)
222 else return t
223-- FIXME: This check is not quite right in some cases, and is breaking
224-- perfectly valid code!
225-- if checkSameTypes (lstT st) tree
226-- then return t
227-- else Error (At fc (Msg "Typecase is not allowed"))
228 Error err -> Error (At fc err)
229 where args = map (\i -> sMN i "e") [0..]
230 defaultCase True = STerm Erased
231 defaultCase False = UnmatchedCase "Error"
232 fstT (x, _, _) = x
233 lstT (_, _, x) = x
235 chkAccessible (avs, l, c)
236 | phase == RunTime || reflect = return (l, c)
237 | otherwise = do mapM_ (acc l) avs
238 return (l, c)
240 acc [] n = Error (Inaccessible n)
241 acc (PV x t : xs) n | x == n = OK ()
242 acc (PCon _ _ ps : xs) n = acc (ps ++ xs) n
243 acc (PSuc p : xs) n = acc (p : xs) n
244 acc (_ : xs) n = acc xs n
246-- For each 'Case', make sure every choice is in the same type family,
247-- as directed by the variable type (i.e. there is no implicit type casing
248-- going on).
250checkSameTypes :: [(Name, Type)] -> SC -> Bool
251checkSameTypes tys (Case n alts)
252 = case lookup n tys of
253 Just t -> and (map (checkAlts t) alts)
254 _ -> and (map ((checkSameTypes tys).getSC) alts)
255 where
256 checkAlts t (ConCase n _ _ sc) = isType n t && checkSameTypes tys sc
257 checkAlts (Constant t) (ConstCase c sc) = isConstType c t && checkSameTypes tys sc
258 checkAlts _ (ConstCase c sc) = False
259 checkAlts _ _ = True
261 getSC (ConCase _ _ _ sc) = sc
262 getSC (FnCase _ _ sc) = sc
263 getSC (ConstCase _ sc) = sc
264 getSC (SucCase _ sc) = sc
265 getSC (DefaultCase sc) = sc
266checkSameTypes _ _ = True
268-- FIXME: All we're actually doing here is checking that we haven't arrived
269-- at a specific constructor for a polymorphic argument. I *think* this
270-- is sufficient, but if it turns out not to be, fix it!
271isType n t | (P (TCon _ _) _ _, _) <- unApply t = True
272isType n t | (P Ref _ _, _) <- unApply t = True
273isType n t = False
275isConstType (I _) (AType (ATInt ITNative)) = True
276isConstType (BI _) (AType (ATInt ITBig)) = True
277isConstType (Fl _) (AType ATFloat) = True
278isConstType (Ch _) (AType (ATInt ITChar)) = True
279isConstType (Str _) StrType = True
280isConstType (B8 _) (AType (ATInt _)) = True
281isConstType (B16 _) (AType (ATInt _)) = True
282isConstType (B32 _) (AType (ATInt _)) = True
283isConstType (B64 _) (AType (ATInt _)) = True
284isConstType (B8V _) (AType (ATInt _)) = True
285isConstType (B16V _) (AType (ATInt _)) = True
286isConstType (B32V _) (AType (ATInt _)) = True
287isConstType (B64V _) (AType (ATInt _)) = True
288isConstType _ _ = False
290data Pat = PCon Name Int [Pat]
291 | PConst Const
292 | PV Name Type
293 | PSuc Pat -- special case for n+1 on Integer
294 | PReflected Name [Pat]
295 | PAny
296 | PTyPat -- typecase, not allowed, inspect last
297 deriving Show
299-- If there are repeated variables, take the *last* one (could be name shadowing
300-- in a where clause, so take the most recent).
302toPats :: Bool -> Bool -> Term -> [Pat]
303toPats reflect tc f = reverse (toPat reflect tc (getArgs f)) where
304 getArgs (App f a) = a : getArgs f
305 getArgs _ = []
307toPat :: Bool -> Bool -> [Term] -> [Pat]
308toPat reflect tc tms = evalState (mapM (\x -> toPat' x []) tms) []
309 where
310 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
311 return $ PCon n t args'
312 -- n + 1
313 toPat' (P _ (UN pabi) _)
314 [p, Constant (BI 1)] | pabi == txt "prim__addBigInt"
315 = do p' <- toPat' p []
316 return $ PSuc p'
317 -- Typecase
318-- toPat' (P (TCon t a) n _) args | tc
319-- = do args' <- mapM (\x -> toPat' x []) args
320-- return $ PCon n t args'
321-- toPat' (Constant (AType (ATInt ITNative))) []
322-- | tc = return $ PCon (UN "Int") 1 []
323-- toPat' (Constant (AType ATFloat)) [] | tc = return $ PCon (UN "Float") 2 []
324-- toPat' (Constant (AType (ATInt ITChar))) [] | tc = return $ PCon (UN "Char") 3 []
325-- toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
326-- toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
327-- toPat' (Constant (AType (ATInt ITBig))) []
328-- | tc = return $ PCon (UN "Integer") 6 []
329-- toPat' (Constant (AType (ATInt (ITFixed n)))) []
330-- | tc = return $ PCon (UN (fixedN n)) (7 + fromEnum n) [] -- 7-10 inclusive
331 toPat' (P Bound n ty) [] = -- trace (show (n, ty)) $
332 do ns <- get
333 if n `elem` ns
334 then return PAny
335 else do put (n : ns)
336 return (PV n ty)
337 toPat' (App f a) args = toPat' f (a : args)
338 toPat' (Constant (AType _)) [] = return PTyPat
339 toPat' (Constant StrType) [] = return PTyPat
340 toPat' (Constant PtrType) [] = return PTyPat
341 toPat' (Constant VoidType) [] = return PTyPat
342 toPat' (Constant x) [] = return $ PConst x
343 toPat' (Bind n (Pi t) sc) [] | reflect && noOccurrence n sc
344 = do t' <- toPat' t []
345 sc' <- toPat' sc []
346 return $ PReflected (sUN "->") (t':sc':[])
347 toPat' (P _ n _) args | reflect
348 = do args' <- mapM (\x -> toPat' x []) args
349 return $ PReflected n args'
350 toPat' t _ = return PAny
352 fixedN IT8 = "Bits8"
353 fixedN IT16 = "Bits16"
354 fixedN IT32 = "Bits32"
355 fixedN IT64 = "Bits64"
358data Partition = Cons [Clause]
359 | Vars [Clause]
360 deriving Show
362isVarPat (PV _ _ : ps , _) = True
363isVarPat (PAny : ps , _) = True
364isVarPat (PTyPat : ps , _) = True
365isVarPat _ = False
367isConPat (PCon _ _ _ : ps, _) = True
368isConPat (PReflected _ _ : ps, _) = True
369isConPat (PSuc _ : ps, _) = True
370isConPat (PConst _ : ps, _) = True
371isConPat _ = False
373partition :: [Clause] -> [Partition]
374partition [] = []
375partition ms@(m : _)
376 | isVarPat m = let (vars, rest) = span isVarPat ms in
377 Vars vars : partition rest
378 | isConPat m = let (cons, rest) = span isConPat ms in
379 Cons cons : partition rest
380partition xs = error $ "Partition " ++ show xs
382-- reorder the patterns so that the one with most distinct names
383-- comes next. Take rightmost first, otherwise (i.e. pick value rather
384-- than dependency)
385--
386-- The first argument means [(Name, IsInaccessible)].
388order :: [(Name, Bool)] -> [Clause] -> ([Name], [Clause])
389order [] cs = ([], cs)
390order ns' [] = (map fst ns', [])
391order ns' cs = let patnames = transpose (map (zip ns') (map fst cs))
392 -- note: sortBy . reverse is not nonsense because sortBy is stable
393 pats' = transpose (sortBy moreDistinct (reverse patnames)) in
394 (getNOrder pats', zipWith rebuild pats' cs)
395 where
396 getNOrder [] = error $ "Failed order on " ++ show (map fst ns', cs)
397 getNOrder (c : _) = map (fst . fst) c
399 rebuild patnames clause = (map snd patnames, snd clause)
401 -- this compares (+isInaccessible, -numberOfCases)
402 moreDistinct xs ys = compare (snd . fst . head $ xs, numNames [] (map snd ys))
403 (snd . fst . head $ ys, numNames [] (map snd xs))
405 numNames xs (PCon n _ _ : ps)
406 | not (Left n `elem` xs) = numNames (Left n : xs) ps
407 numNames xs (PConst c : ps)
408 | not (Right c `elem` xs) = numNames (Right c : xs) ps
409 numNames xs (_ : ps) = numNames xs ps
410 numNames xs [] = length xs
412match :: [Name] -> [Clause] -> SC -- error case
413 -> State CS SC
414match [] (([], ret) : xs) err
415 = do (ts, v, ntys) <- get
416 put (ts ++ (map (fst.snd) xs), v, ntys)
417 case snd ret of
418 Impossible -> return ImpossibleCase
419 tm -> return $ STerm tm -- run out of arguments
420match vs cs err = do let ps = partition cs
421 mixture vs ps err
423mixture :: [Name] -> [Partition] -> SC -> State CS SC
424mixture vs [] err = return err
425mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
426 conRule vs ms fallthrough
427mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
428 varRule vs ms fallthrough
430data ConType = CName Name Int -- named constructor
431 | CFn Name -- reflected function name
432 | CSuc -- n+1
433 | CConst Const -- constant, not implemented yet
434 deriving (Show, Eq)
436data Group = ConGroup ConType -- Constructor
437 [([Pat], Clause)] -- arguments and rest of alternative
438 deriving Show
440conRule :: [Name] -> [Clause] -> SC -> State CS SC
441conRule (v:vs) cs err = do groups <- groupCons cs
442 caseGroups (v:vs) groups err
444caseGroups :: [Name] -> [Group] -> SC -> State CS SC
445caseGroups (v:vs) gs err = do g <- altGroups gs
446 return $ Case v (sort g)
447 where
448 altGroups [] = return [DefaultCase err]
449 altGroups (ConGroup (CName n i) args : cs)
450 = do g <- altGroup n i args
451 rest <- altGroups cs
452 return (g : rest)
453 altGroups (ConGroup (CFn n) args : cs)
454 = do g <- altFnGroup n args
455 rest <- altGroups cs
456 return (g : rest)
457 altGroups (ConGroup CSuc args : cs)
458 = do g <- altSucGroup args
459 rest <- altGroups cs
460 return (g : rest)
461 altGroups (ConGroup (CConst c) args : cs)
462 = do g <- altConstGroup c args
463 rest <- altGroups cs
464 return (g : rest)
466 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
467 matchCs <- match (newArgs ++ vs) nextCs err
468 return $ ConCase n i newArgs matchCs
469 altFnGroup n gs = do (newArgs, nextCs) <- argsToAlt gs
470 matchCs <- match (newArgs ++ vs) nextCs err
471 return $ FnCase n newArgs matchCs
472 altSucGroup gs = do ([newArg], nextCs) <- argsToAlt gs
473 matchCs <- match (newArg:vs) nextCs err
474 return $ SucCase newArg matchCs
475 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
476 matchCs <- match vs nextCs err
477 return $ ConstCase n matchCs
479argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
480argsToAlt [] = return ([], [])
481argsToAlt rs@((r, m) : rest)
482 = do newArgs <- getNewVars r
483 return (newArgs, addRs rs)
484 where
485 getNewVars [] = return []
486 getNewVars ((PV n t) : ns) = do v <- getVar "e"
487 (cs, i, ntys) <- get
488 put (cs, i, (v, t) : ntys)
489 nsv <- getNewVars ns
490 return (v : nsv)
491 getNewVars (PAny : ns) = do v <- getVar "i"
492 nsv <- getNewVars ns
493 return (v : nsv)
494 getNewVars (PTyPat : ns) = do v <- getVar "t"
495 nsv <- getNewVars ns
496 return (v : nsv)
497 getNewVars (_ : ns) = do v <- getVar "e"
498 nsv <- getNewVars ns
499 return (v : nsv)
500 addRs [] = []
501 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
503 uniq i (UN n) = MN i n
504 uniq i n = n
506getVar :: String -> State CS Name
507getVar b = do (t, v, ntys) <- get; put (t, v+1, ntys); return (sMN v b)
509groupCons :: [Clause] -> State CS [Group]
510groupCons cs = gc [] cs
511 where
512 gc acc [] = return acc
513 gc acc ((p : ps, res) : cs) =
514 do acc' <- addGroup p ps res acc
515 gc acc' cs
516 addGroup p ps res acc = case p of
517 PCon con i args -> return $ addg (CName con i) args (ps, res) acc
518 PConst cval -> return $ addConG cval (ps, res) acc
519 PSuc n -> return $ addg CSuc [n] (ps, res) acc
520 PReflected fn args -> return $ addg (CFn fn) args (ps, res) acc
521 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
523 addg c conargs res []
524 = [ConGroup c [(conargs, res)]]
525 addg c conargs res (g@(ConGroup c' cs):gs)
526 | c == c' = ConGroup c (cs ++ [(conargs, res)]) : gs
527 | otherwise = g : addg c conargs res gs
529 addConG con res [] = [ConGroup (CConst con) [([], res)]]
530 addConG con res (g@(ConGroup (CConst n) cs) : gs)
531 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
532-- | otherwise = g : addConG con res gs
533 addConG con res (g : gs) = g : addConG con res gs
535varRule :: [Name] -> [Clause] -> SC -> State CS SC
536varRule (v : vs) alts err =
537 do alts' <- mapM (repVar v) alts
538 match vs alts' err
539 where
540 repVar v (PV p ty : ps , (lhs, res))
541 = do (cs, i, ntys) <- get
542 put (cs, i, (v, ty) : ntys)
543 return (ps, (lhs, subst p (P Bound v ty) res))
544 repVar v (PAny : ps , res) = return (ps, res)
545 repVar v (PTyPat : ps , res) = return (ps, res)
547-- fix: case e of S k -> f (S k) ==> case e of S k -> f e
549depatt :: [Name] -> SC -> SC
550depatt ns tm = dp [] tm
551 where
552 dp ms (STerm tm) = STerm (applyMaps ms tm)
553 dp ms (Case x alts) = Case x (map (dpa ms x) alts)
554 dp ms sc = sc
556 dpa ms x (ConCase n i args sc)
557 = ConCase n i args (dp ((x, (n, args)) : ms) sc)
558 dpa ms x (FnCase n args sc)
559 = FnCase n args (dp ((x, (n, args)) : ms) sc)
560 dpa ms x (ConstCase c sc) = ConstCase c (dp ms sc)
561 dpa ms x (SucCase n sc) = SucCase n (dp ms sc)
562 dpa ms x (DefaultCase sc) = DefaultCase (dp ms sc)
564 applyMaps ms f@(App _ _)
565 | (P nt cn pty, args) <- unApply f
566 = let args' = map (applyMaps ms) args in
567 applyMap ms nt cn pty args'
568 where
569 applyMap [] nt cn pty args' = mkApp (P nt cn pty) args'
570 applyMap ((x, (n, args)) : ms) nt cn pty args'
571 | and ((length args == length args') :
572 (n == cn) : zipWith same args args') = P Ref x Erased
573 | otherwise = applyMap ms nt cn pty args'
574 same n (P _ n' _) = n == n'
575 same _ _ = False
577 applyMaps ms (App f a) = App (applyMaps ms f) (applyMaps ms a)
578 applyMaps ms t = t
580-- FIXME: Do this for SucCase too
581prune :: Bool -- ^ Convert single branches to projections (only useful at runtime)
582 -> SC -> SC
583prune proj (Case n alts)
584 = let alts' = filter notErased (map pruneAlt alts) in
585 case alts' of
586 [] -> ImpossibleCase
587 as@(ConCase (UN delay) i [arg] sc : _)
588 | delay == txt "Delay"
589 -> if proj then mkForce n arg sc
590 else Case n as
592 -- Projection transformations prevent us from seeing some uses of ctor fields
593 -- because they delete information about which ctor is being used.
594 -- Consider:
595 -- f (X x) = ... x ...
596 -- vs.
597 -- f x = ... x!0 ...
598 -- There's currently no code to handle this stuff. (TODO)
599 --
600 --as@[ConCase cn i args sc]
601 -- | proj -> mkProj n 0 args (prune proj sc)
603 as@[SucCase cn sc]
604 | proj -> mkProj n (-1) [cn] (prune proj sc)
606 as@[ConstCase _ sc]
607 -> prune proj sc
609 -- Bit of a hack here! The default case will always be 0, make sure
610 -- it gets caught first.
611 [s@(SucCase _ _), DefaultCase dc]
612 -> Case n [ConstCase (BI 0) dc, s]
614 as -> Case n as
615 where pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune proj sc)
616 pruneAlt (FnCase cn ns sc) = FnCase cn ns (prune proj sc)
617 pruneAlt (ConstCase c sc) = ConstCase c (prune proj sc)
618 pruneAlt (SucCase n sc) = SucCase n (prune proj sc)
619 pruneAlt (DefaultCase sc) = DefaultCase (prune proj sc)
621 notErased (DefaultCase (STerm Erased)) = False
622 notErased (DefaultCase ImpossibleCase) = False
623 notErased _ = True
625 mkForce n arg (Case x [alt])
626 | x == arg = ProjCase (forceArg n) (mkForceAlt n arg alt)
627 mkForce n arg (Case x alts)
628 = Case x (map (mkForceAlt n arg) alts)
629 mkForce n arg (ProjCase t alt)
630 = ProjCase (forceTm n arg t) (mkForceAlt n arg alt)
631 mkForce n arg (STerm t) = STerm (forceTm n arg t)
632 mkForce n arg c = c
634 mkForceAlt n arg (ConCase cn t args rhs)
635 = ConCase cn t args (mkForce n arg rhs)
636 mkForceAlt n arg (FnCase cn args rhs)
637 = FnCase cn args (mkForce n arg rhs)
638 mkForceAlt n arg (ConstCase t rhs)
639 = ConstCase t (mkForce n arg rhs)
640 mkForceAlt n arg (SucCase sn rhs)
641 = SucCase sn (mkForce n arg rhs)
642 mkForceAlt n arg (DefaultCase rhs)
643 = DefaultCase (mkForce n arg rhs)
645 forceTm n arg t = subst arg (forceArg n) t
647 forceArg n = App (App (App (P Ref (sUN "Force") Erased) Erased) Erased)
648 (P Bound n Erased)
650 mkProj n i xs sc = foldr (\x -> projRep x n i) sc xs
652 -- Change every 'n' in sc to 'n-1'
653-- mkProjS n cn sc = prune proj (fmap projn sc) where
654-- projn pn@(P _ n' _)
655-- | cn == n' = App (App (P Ref (UN "prim__subBigInt") Erased)
656-- (P Bound n Erased)) (Constant (BI 1))
657-- projn t = t
659 projRep :: Name -> Name -> Int -> SC -> SC
660 projRep arg n i (Case x [alt]) | x == arg
661 = ProjCase (Proj (P Bound n Erased) i) (projRepAlt arg n i alt)
662 projRep arg n i (Case x alts)
663 = Case x (map (projRepAlt arg n i) alts)
664 projRep arg n i (ProjCase t alt)
665 = ProjCase (projRepTm arg n i t) (projRepAlt arg n i alt)
666 projRep arg n i (STerm t) = STerm (projRepTm arg n i t)
667 projRep arg n i c = c -- unmatched
669 projRepAlt arg n i (ConCase cn t args rhs)
670 = ConCase cn t args (projRep arg n i rhs)
671 projRepAlt arg n i (FnCase cn args rhs)
672 = FnCase cn args (projRep arg n i rhs)
673 projRepAlt arg n i (ConstCase t rhs)
674 = ConstCase t (projRep arg n i rhs)
675 projRepAlt arg n i (SucCase sn rhs)
676 = SucCase sn (projRep arg n i rhs)
677 projRepAlt arg n i (DefaultCase rhs)
678 = DefaultCase (projRep arg n i rhs)
680 projRepTm arg n i t = subst arg (Proj (P Bound n Erased) i) t
682prune _ t = t
684stripLambdas :: CaseDef -> CaseDef
685stripLambdas (CaseDef ns (STerm (Bind x (Lam _) sc)) tm)
686 = stripLambdas (CaseDef (ns ++ [x]) (STerm (instantiate (P Bound x Erased) sc)) tm)
687stripLambdas x = x
690substSC :: Name -> Name -> SC -> SC
691substSC n repl (Case n' alts)
692 | n == n' = Case repl (map (substAlt n repl) alts)
693 | otherwise = Case n' (map (substAlt n repl) alts)
694substSC n repl (STerm t) = STerm $ subst n (P Bound repl Erased) t
695substSC n repl sc = error $ "unsupported in substSC: " ++ show sc
697substAlt :: Name -> Name -> CaseAlt -> CaseAlt
698substAlt n repl (ConCase cn a ns sc) = ConCase cn a ns (substSC n repl sc)
699substAlt n repl (FnCase fn ns sc) = FnCase fn ns (substSC n repl sc)
700substAlt n repl (ConstCase c sc) = ConstCase c (substSC n repl sc)
701substAlt n repl (SucCase n' sc)
702 | n == n' = SucCase n (substSC n repl sc)
703 | otherwise = SucCase n' (substSC n repl sc)
704substAlt n repl (DefaultCase sc) = DefaultCase (substSC n repl sc)