git.iko.soy/Idris-dev
on ef93607 help sign in
Idris-dev/src/Core/CaseTree.hs
520 lines 20 kB history raw
1{-# LANGUAGE PatternGuards, DeriveFunctor, TypeSynonymInstances #-}
3module Core.CaseTree(CaseDef(..), SC, SC'(..), CaseAlt, CaseAlt'(..),
4 Phase(..), CaseTree,
5 simpleCase, small, namesUsed, findCalls, findUsedArgs) where
7import 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
25!-}
27type SC = SC' Term
29data CaseAlt' t = ConCase Name Int [Name] (SC' t)
30 | FnCase Name [Name] (SC' t) -- ^ reflection function
31 | ConstCase Const (SC' t)
32 | DefaultCase (SC' t)
33 deriving (Show, Eq, Ord, Functor)
34{-!
35deriving instance Binary CaseAlt
36!-}
38type CaseAlt = CaseAlt' Term
40instance Show t => Show (SC' t) where
41 show sc = show' 1 sc
42 where
43 show' i (Case n alts) = "case " ++ show n ++ " of\n" ++ indent i ++
44 showSep ("\n" ++ indent i) (map (showA i) alts)
45 show' i (ProjCase tm alts) = "case " ++ show tm ++ " of " ++
46 showSep ("\n" ++ indent i) (map (showA i) alts)
47 show' i (STerm tm) = show tm
48 show' i (UnmatchedCase str) = "error " ++ show str
49 show' i ImpossibleCase = "impossible"
51 indent i = concat $ take i (repeat " ")
53 showA i (ConCase n t args sc)
54 = show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
55 ++ show' (i+1) sc
56 showA i (FnCase n args sc)
57 = "FN " ++ show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
58 ++ show' (i+1) sc
59 showA i (ConstCase t sc)
60 = show t ++ " => " ++ show' (i+1) sc
61 showA i (DefaultCase sc)
62 = "_ => " ++ show' (i+1) sc
65type CaseTree = SC
66type Clause = ([Pat], (Term, Term))
67type CS = ([Term], Int)
69instance TermSize SC where
70 termsize n (Case n' as) = termsize n as
71 termsize n (ProjCase n' as) = termsize n as
72 termsize n (STerm t) = termsize n t
73 termsize n _ = 1
75instance TermSize CaseAlt where
76 termsize n (ConCase _ _ _ s) = termsize n s
77 termsize n (FnCase _ _ s) = termsize n s
78 termsize n (ConstCase _ s) = termsize n s
79 termsize n (DefaultCase s) = termsize n s
81-- simple terms can be inlined trivially - good for primitives in particular
82-- To avoid duplicating work, don't inline something which uses one
83-- of its arguments in more than one place
85small :: Name -> [Name] -> SC -> Bool
86small n args t = let as = findAllUsedArgs t args in
87 length as == length (nub as) &&
88 termsize n t < 10
90namesUsed :: SC -> [Name]
91namesUsed sc = nub $ nu' [] sc where
92 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
93 nu' ps (ProjCase t alts) = nub $ (nut ps t ++
94 (concatMap (nua ps) alts))
95 nu' ps (STerm t) = nub $ nut ps t
96 nu' ps _ = []
98 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
99 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc) \\ args
100 nua ps (ConstCase _ sc) = nu' ps sc
101 nua ps (DefaultCase sc) = nu' ps sc
103 nut ps (P _ n _) | n `elem` ps = []
104 | otherwise = [n]
105 nut ps (App f a) = nut ps f ++ nut ps a
106 nut ps (Proj t _) = nut ps t
107 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
108 nut ps (Bind n b sc) = nut (n:ps) sc
109 nut ps _ = []
111-- Return all called functions, and which arguments are used in each argument position
112-- for the call, in order to help reduce compilation time, and trace all unused
113-- arguments
115findCalls :: SC -> [Name] -> [(Name, [[Name]])]
116findCalls sc topargs = nub $ nu' topargs sc where
117 nu' ps (Case n alts) = nub (concatMap (nua (n : ps)) alts)
118 nu' ps (ProjCase t alts) = nub (nut ps t ++ concatMap (nua ps) alts)
119 nu' ps (STerm t) = nub $ nut ps t
120 nu' ps _ = []
122 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc)
123 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc)
124 nua ps (ConstCase _ sc) = nu' ps sc
125 nua ps (DefaultCase sc) = nu' ps sc
127 nut ps (P Ref n _) | n `elem` ps = []
128 | otherwise = [(n, [])] -- tmp
129 nut ps fn@(App f a)
130 | (P Ref n _, args) <- unApply fn
131 = if n `elem` ps then nut ps f ++ nut ps a
132 else [(n, map argNames args)] ++ concatMap (nut ps) args
133 | otherwise = nut ps f ++ nut ps a
134 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
135 nut ps (Proj t _) = nut ps t
136 nut ps (Bind n b sc) = nut (n:ps) sc
137 nut ps _ = []
139 argNames tm = let ns = directUse tm in
140 filter (\x -> x `elem` ns) topargs
142-- Find names which are used directly (i.e. not in a function call) in a term
144directUse :: Eq n => TT n -> [n]
145directUse (P _ n _) = [n]
146directUse (Bind n (Let t v) sc) = nub $ directUse v ++ (directUse sc \\ [n])
147 ++ directUse t
148directUse (Bind n b sc) = nub $ directUse (binderTy b) ++ (directUse sc \\ [n])
149directUse fn@(App f a)
150 | (P Ref n _, args) <- unApply fn = [] -- need to know what n does with them
151 | otherwise = nub $ directUse f ++ directUse a
152directUse (Proj x i) = nub $ directUse x
153directUse _ = []
155-- Find all directly used arguments (i.e. used but not in function calls)
157findUsedArgs :: SC -> [Name] -> [Name]
158findUsedArgs sc topargs = nub (findAllUsedArgs sc topargs)
160findAllUsedArgs sc topargs = filter (\x -> x `elem` topargs) (nu' sc) where
161 nu' (Case n alts) = n : concatMap nua alts
162 nu' (ProjCase t alts) = directUse t ++ concatMap nua alts
163 nu' (STerm t) = directUse t
164 nu' _ = []
166 nua (ConCase n i args sc) = nu' sc
167 nua (FnCase n args sc) = nu' sc
168 nua (ConstCase _ sc) = nu' sc
169 nua (DefaultCase sc) = nu' sc
171data Phase = CompileTime | RunTime
172 deriving (Show, Eq)
174-- Generate a simple case tree
175-- Work Right to Left
177simpleCase :: Bool -> Bool -> Bool ->
178 Phase -> FC -> [([Name], Term, Term)] ->
179 TC CaseDef
180simpleCase tc cover reflect phase fc cs
181 = sc' tc cover phase fc (filter (\(_, _, r) ->
182 case r of
183 Impossible -> False
184 _ -> True) cs)
185 where
186 sc' tc cover phase fc []
187 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
188 sc' tc cover phase fc cs
189 = let proj = phase == RunTime
190 pats = map (\ (avs, l, r) ->
191 (avs, toPats reflect tc l, (l, r))) cs
192 chkPats = mapM chkAccessible pats in
193 case chkPats of
194 OK pats ->
195 let numargs = length (fst (head pats))
196 ns = take numargs args
197 (ns', ps') = order ns pats
198 (tree, st) = runState
199 (match ns' ps' (defaultCase cover)) ([], numargs)
200 t = CaseDef ns (prune proj (depatt ns' tree)) (fst st) in
201 if proj then return (stripLambdas t) else return t
202 Error err -> Error (At fc err)
203 where args = map (\i -> MN i "e") [0..]
204 defaultCase True = STerm Erased
205 defaultCase False = UnmatchedCase "Error"
207 chkAccessible (avs, l, c)
208 | phase == RunTime || reflect = return (l, c)
209 | otherwise = do mapM_ (acc l) avs
210 return (l, c)
212 acc [] n = Error (Inaccessible n)
213 acc (PV x : xs) n | x == n = OK ()
214 acc (PCon _ _ ps : xs) n = acc (ps ++ xs) n
215 acc (_ : xs) n = acc xs n
217data Pat = PCon Name Int [Pat]
218 | PConst Const
219 | PV Name
220 | PReflected Name [Pat]
221 | PAny
222 deriving Show
224-- If there are repeated variables, take the *last* one (could be name shadowing
225-- in a where clause, so take the most recent).
227toPats :: Bool -> Bool -> Term -> [Pat]
228toPats reflect tc f = reverse (toPat reflect tc (getArgs f)) where
229 getArgs (App f a) = a : getArgs f
230 getArgs _ = []
232toPat :: Bool -> Bool -> [Term] -> [Pat]
233toPat reflect tc tms = evalState (mapM (\x -> toPat' x []) tms) []
234 where
235 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
236 return $ PCon n t args'
237 -- Typecase
238 toPat' (P (TCon t a) n _) args | tc
239 = do args' <- mapM (\x -> toPat' x []) args
240 return $ PCon n t args'
241 toPat' (Constant (AType (ATInt ITNative))) []
242 | tc = return $ PCon (UN "Int") 1 []
243 toPat' (Constant (AType ATFloat)) [] | tc = return $ PCon (UN "Float") 2 []
244 toPat' (Constant (AType (ATInt ITChar))) [] | tc = return $ PCon (UN "Char") 3 []
245 toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
246 toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
247 toPat' (Constant (AType (ATInt ITBig))) []
248 | tc = return $ PCon (UN "Integer") 6 []
249 toPat' (Constant (AType (ATInt (ITFixed n)))) []
250 | tc = return $ PCon (UN (fixedN n)) (7 + fromEnum n) [] -- 7-10 inclusive
251 toPat' (P Bound n _) [] = do ns <- get
252 if n `elem` ns
253 then return PAny
254 else do put (n : ns)
255 return (PV n)
256 toPat' (App f a) args = toPat' f (a : args)
257 toPat' (Constant x) [] = return $ PConst x
258 toPat' (Bind n (Pi t) sc) [] | reflect && noOccurrence n sc
259 = do t' <- toPat' t []
260 sc' <- toPat' sc []
261 return $ PReflected (UN "->") (t':sc':[])
262 toPat' (P _ n _) args | reflect
263 = do args' <- mapM (\x -> toPat' x []) args
264 return $ PReflected n args'
265 toPat' _ _ = return PAny
267 fixedN IT8 = "Bits8"
268 fixedN IT16 = "Bits16"
269 fixedN IT32 = "Bits32"
270 fixedN IT64 = "Bits64"
273data Partition = Cons [Clause]
274 | Vars [Clause]
275 deriving Show
277isVarPat (PV _ : ps , _) = True
278isVarPat (PAny : ps , _) = True
279isVarPat _ = False
281isConPat (PCon _ _ _ : ps, _) = True
282isConPat (PReflected _ _ : ps, _) = True
283isConPat (PConst _ : ps, _) = True
284isConPat _ = False
286partition :: [Clause] -> [Partition]
287partition [] = []
288partition ms@(m : _)
289 | isVarPat m = let (vars, rest) = span isVarPat ms in
290 Vars vars : partition rest
291 | isConPat m = let (cons, rest) = span isConPat ms in
292 Cons cons : partition rest
293partition xs = error $ "Partition " ++ show xs
295-- reorder the patterns so that the one with most distinct names
296-- comes next. Take rightmost first, otherwise (i.e. pick value rather
297-- than dependency)
299order :: [Name] -> [Clause] -> ([Name], [Clause])
300order [] cs = ([], cs)
301order ns [] = (ns, [])
302order ns cs = let patnames = transpose (map (zip ns) (map fst cs))
303 pats' = transpose (sortBy moreDistinct (reverse patnames)) in
304 (getNOrder pats', zipWith rebuild pats' cs)
305 where
306 getNOrder [] = error $ "Failed order on " ++ show (ns, cs)
307 getNOrder (c : _) = map fst c
309 rebuild patnames clause = (map snd patnames, snd clause)
311 moreDistinct xs ys = compare (numNames [] (map snd ys))
312 (numNames [] (map snd xs))
314 numNames xs (PCon n _ _ : ps)
315 | not (Left n `elem` xs) = numNames (Left n : xs) ps
316 numNames xs (PConst c : ps)
317 | not (Right c `elem` xs) = numNames (Right c : xs) ps
318 numNames xs (_ : ps) = numNames xs ps
319 numNames xs [] = length xs
321match :: [Name] -> [Clause] -> SC -- error case
322 -> State CS SC
323match [] (([], ret) : xs) err
324 = do (ts, v) <- get
325 put (ts ++ (map (fst.snd) xs), v)
326 case snd ret of
327 Impossible -> return ImpossibleCase
328 tm -> return $ STerm tm -- run out of arguments
329match vs cs err = do let ps = partition cs
330 mixture vs ps err
332mixture :: [Name] -> [Partition] -> SC -> State CS SC
333mixture vs [] err = return err
334mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
335 conRule vs ms fallthrough
336mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
337 varRule vs ms fallthrough
339data ConType = CName Name Int -- named constructor
340 | CFn Name -- reflected function name
341 | CConst Const -- constant, not implemented yet
342 deriving Eq
344data Group = ConGroup ConType -- Constructor
345 [([Pat], Clause)] -- arguments and rest of alternative
347conRule :: [Name] -> [Clause] -> SC -> State CS SC
348conRule (v:vs) cs err = do groups <- groupCons cs
349 caseGroups (v:vs) groups err
351caseGroups :: [Name] -> [Group] -> SC -> State CS SC
352caseGroups (v:vs) gs err = do g <- altGroups gs
353 return $ Case v (sort g)
354 where
355 altGroups [] = return [DefaultCase err]
356 altGroups (ConGroup (CName n i) args : cs)
357 = do g <- altGroup n i args
358 rest <- altGroups cs
359 return (g : rest)
360 altGroups (ConGroup (CFn n) args : cs)
361 = do g <- altFnGroup n args
362 rest <- altGroups cs
363 return (g : rest)
364 altGroups (ConGroup (CConst c) args : cs)
365 = do g <- altConstGroup c args
366 rest <- altGroups cs
367 return (g : rest)
369 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
370 matchCs <- match (newArgs ++ vs) nextCs err
371 return $ ConCase n i newArgs matchCs
372 altFnGroup n gs = do (newArgs, nextCs) <- argsToAlt gs
373 matchCs <- match (newArgs ++ vs) nextCs err
374 return $ FnCase n newArgs matchCs
375 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
376 matchCs <- match vs nextCs err
377 return $ ConstCase n matchCs
379argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
380argsToAlt [] = return ([], [])
381argsToAlt rs@((r, m) : rest)
382 = do newArgs <- getNewVars r
383 return (newArgs, addRs rs)
384 where
385 getNewVars [] = return []
386 getNewVars ((PV n) : ns) = do v <- getVar "e"
387 nsv <- getNewVars ns
388 return (v : nsv)
389 getNewVars (PAny : ns) = do v <- getVar "i"
390 nsv <- getNewVars ns
391 return (v : nsv)
392 getNewVars (_ : ns) = do v <- getVar "e"
393 nsv <- getNewVars ns
394 return (v : nsv)
395 addRs [] = []
396 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
398 uniq i (UN n) = MN i n
399 uniq i n = n
401getVar :: String -> State CS Name
402getVar b = do (t, v) <- get; put (t, v+1); return (MN v b)
404groupCons :: [Clause] -> State CS [Group]
405groupCons cs = gc [] cs
406 where
407 gc acc [] = return acc
408 gc acc ((p : ps, res) : cs) =
409 do acc' <- addGroup p ps res acc
410 gc acc' cs
411 addGroup p ps res acc = case p of
412 PCon con i args -> return $ addg (CName con i) args (ps, res) acc
413 PConst cval -> return $ addConG cval (ps, res) acc
414 PReflected fn args -> return $ addg (CFn fn) args (ps, res) acc
415 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
417 addg c conargs res []
418 = [ConGroup c [(conargs, res)]]
419 addg c conargs res (g@(ConGroup c' cs):gs)
420 | c == c' = ConGroup c (cs ++ [(conargs, res)]) : gs
421 | otherwise = g : addg c conargs res gs
423 addConG con res [] = [ConGroup (CConst con) [([], res)]]
424 addConG con res (g@(ConGroup (CConst n) cs) : gs)
425 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
426 | otherwise = g : addConG con res gs
428varRule :: [Name] -> [Clause] -> SC -> State CS SC
429varRule (v : vs) alts err =
430 do let alts' = map (repVar v) alts
431 match vs alts' err
432 where
433 repVar v (PV p : ps , (lhs, res))
434 = (ps, (lhs, subst p (P Bound v Erased) res))
435 repVar v (PAny : ps , res) = (ps, res)
437-- fix: case e of S k -> f (S k) ==> case e of S k -> f e
439depatt :: [Name] -> SC -> SC
440depatt ns tm = dp [] tm
441 where
442 dp ms (STerm tm) = STerm (applyMaps ms tm)
443 dp ms (Case x alts) = Case x (map (dpa ms x) alts)
444 dp ms sc = sc
446 dpa ms x (ConCase n i args sc)
447 = ConCase n i args (dp ((x, (n, args)) : ms) sc)
448 dpa ms x (FnCase n args sc)
449 = FnCase n args (dp ((x, (n, args)) : ms) sc)
450 dpa ms x (ConstCase c sc) = ConstCase c (dp ms sc)
451 dpa ms x (DefaultCase sc) = DefaultCase (dp ms sc)
453 applyMaps ms f@(App _ _)
454 | (P nt cn pty, args) <- unApply f
455 = let args' = map (applyMaps ms) args in
456 applyMap ms nt cn pty args'
457 where
458 applyMap [] nt cn pty args' = mkApp (P nt cn pty) args'
459 applyMap ((x, (n, args)) : ms) nt cn pty args'
460 | and ((length args == length args') :
461 (n == cn) : zipWith same args args') = P Ref x Erased
462 | otherwise = applyMap ms nt cn pty args'
463 same n (P _ n' _) = n == n'
464 same _ _ = False
466 applyMaps ms (App f a) = App (applyMaps ms f) (applyMaps ms a)
467 applyMaps ms t = t
469prune :: Bool -- ^ Convert single branches to projections (only useful at runtime)
470 -> SC -> SC
471prune proj (Case n alts)
472 = let alts' = filter notErased (map pruneAlt alts) in
473 case alts' of
474 [] -> ImpossibleCase
475 as@[ConCase cn i args sc] -> if proj then mkProj n 0 args sc
476 else Case n as
477 as -> Case n as
478 where pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune proj sc)
479 pruneAlt (FnCase cn ns sc) = FnCase cn ns (prune proj sc)
480 pruneAlt (ConstCase c sc) = ConstCase c (prune proj sc)
481 pruneAlt (DefaultCase sc) = DefaultCase (prune proj sc)
483 notErased (DefaultCase (STerm Erased)) = False
484 notErased (DefaultCase ImpossibleCase) = False
485 notErased _ = True
487 mkProj n i [] sc = sc
488 mkProj n i (x : xs) sc = mkProj n (i + 1) xs (projRep x n i sc)
490 projRep :: Name -> Name -> Int -> SC -> SC
491 projRep arg n i (Case x alts)
492 | x == arg = ProjCase (Proj (P Bound n Erased) i)
493 (map (projRepAlt arg n i) alts)
494 | otherwise = Case x (map (projRepAlt arg n i) alts)
495 projRep arg n i (ProjCase t alts)
496 = ProjCase (projRepTm arg n i t) (map (projRepAlt arg n i) alts)
497 projRep arg n i (STerm t) = STerm (projRepTm arg n i t)
498 projRep arg n i c = c -- unmatched
500 projRepAlt arg n i (ConCase cn t args rhs)
501 = ConCase cn t args (projRep arg n i rhs)
502 projRepAlt arg n i (FnCase cn args rhs)
503 = FnCase cn args (projRep arg n i rhs)
504 projRepAlt arg n i (ConstCase t rhs)
505 = ConstCase t (projRep arg n i rhs)
506 projRepAlt arg n i (DefaultCase rhs)
507 = DefaultCase (projRep arg n i rhs)
509 projRepTm arg n i t = subst arg (Proj (P Bound n Erased) i) t
511prune _ t = t
513stripLambdas :: CaseDef -> CaseDef
514stripLambdas (CaseDef ns (STerm (Bind x (Lam _) sc)) tm)
515 = stripLambdas (CaseDef (ns ++ [x]) (STerm (instantiate (P Bound x Erased) sc)) tm)
516stripLambdas x = x