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