git.iko.soy/Idris-dev
on 449bb27 help sign in
Idris-dev/src/Core/CaseTree.hs
427 lines 16 kB history raw
1{-# LANGUAGE PatternGuards, DeriveFunctor #-}
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 | ConstCase Const (SC' t)
31 | DefaultCase (SC' t)
32 deriving (Show, Eq, Ord, Functor)
33{-!
34deriving instance Binary CaseAlt
35!-}
37type CaseAlt = CaseAlt' Term
39instance Show t => Show (SC' t) where
40 show sc = show' 1 sc
41 where
42 show' i (Case n alts) = "case " ++ show n ++ " of\n" ++ indent i ++
43 showSep ("\n" ++ indent i) (map (showA i) alts)
44 show' i (ProjCase tm alts) = "case " ++ show tm ++ " of " ++
45 showSep ("\n" ++ indent i) (map (showA i) alts)
46 show' i (STerm tm) = show tm
47 show' i (UnmatchedCase str) = "error " ++ show str
48 show' i ImpossibleCase = "impossible"
50 indent i = concat $ take i (repeat " ")
52 showA i (ConCase n t args sc)
53 = show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
54 ++ show' (i+1) sc
55 showA i (ConstCase t sc)
56 = show t ++ " => " ++ show' (i+1) sc
57 showA i (DefaultCase sc)
58 = "_ => " ++ show' (i+1) sc
61type CaseTree = SC
62type Clause = ([Pat], (Term, Term))
63type CS = ([Term], Int)
65instance TermSize SC where
66 termsize n (Case n' as) = termsize n as
67 termsize n (STerm t) = termsize n t
68 termsize n _ = 1
70instance TermSize CaseAlt where
71 termsize n (ConCase _ _ _ s) = termsize n s
72 termsize n (ConstCase _ s) = termsize n s
73 termsize n (DefaultCase s) = termsize n s
75-- simple terms can be inlined trivially - good for primitives in particular
76small :: Name -> SC -> Bool
77small n t = termsize n t < 50
79namesUsed :: SC -> [Name]
80namesUsed sc = nub $ nu' [] sc where
81 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
82 nu' ps (STerm t) = nub $ nut ps t
83 nu' ps _ = []
85 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
86 nua ps (ConstCase _ sc) = nu' ps sc
87 nua ps (DefaultCase sc) = nu' ps sc
89 nut ps (P _ n _) | n `elem` ps = []
90 | otherwise = [n]
91 nut ps (App f a) = nut ps f ++ nut ps a
92 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
93 nut ps (Bind n b sc) = nut (n:ps) sc
94 nut ps _ = []
96-- Return all called functions, and which arguments are used in each argument position
97-- for the call, in order to help reduce compilation time, and trace all unused
98-- arguments
100findCalls :: SC -> [Name] -> [(Name, [[Name]])]
101findCalls sc topargs = nub $ nu' topargs sc where
102 nu' ps (Case n alts) = nub (concatMap (nua (n : ps)) alts)
103 nu' ps (STerm t) = nub $ nut ps t
104 nu' ps _ = []
106 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc)
107 nua ps (ConstCase _ sc) = nu' ps sc
108 nua ps (DefaultCase sc) = nu' ps sc
110 nut ps (P Ref n _) | n `elem` ps = []
111 | otherwise = [(n, [])] -- tmp
112 nut ps fn@(App f a)
113 | (P Ref n _, args) <- unApply fn
114 = if n `elem` ps then nut ps f ++ nut ps a
115 else [(n, map argNames args)] ++ concatMap (nut ps) args
116 | otherwise = nut ps f ++ nut ps a
117 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
118 nut ps (Bind n b sc) = nut (n:ps) sc
119 nut ps _ = []
121 argNames tm = let ns = directUse tm in
122 filter (\x -> x `elem` ns) topargs
124-- Find names which are used directly (i.e. not in a function call) in a term
126directUse :: Eq n => TT n -> [n]
127directUse (P _ n _) = [n]
128directUse (Bind n (Let t v) sc) = nub $ directUse v ++ (directUse sc \\ [n])
129 ++ directUse t
130directUse (Bind n b sc) = nub $ directUse (binderTy b) ++ (directUse sc \\ [n])
131directUse fn@(App f a)
132 | (P Ref n _, args) <- unApply fn = [] -- need to know what n does with them
133 | otherwise = nub $ directUse f ++ directUse a
134directUse (Proj x i) = nub $ directUse x
135directUse _ = []
137-- Find all directly used arguments (i.e. used but not in function calls)
139findUsedArgs :: SC -> [Name] -> [Name]
140findUsedArgs sc topargs = filter (\x -> x `elem` topargs) (nub $ nu' sc) where
141 nu' (Case n alts) = n : concatMap nua alts
142 nu' (STerm t) = directUse t
143 nu' _ = []
145 nua (ConCase n i args sc) = nu' sc
146 nua (ConstCase _ sc) = nu' sc
147 nua (DefaultCase sc) = nu' sc
149data Phase = CompileTime | RunTime
150 deriving (Show, Eq)
152-- Generate a simple case tree
153-- Work Left to Right at Compile Time
155simpleCase :: Bool -> Bool -> Phase -> FC -> [([Name], Term, Term)] -> TC CaseDef
156simpleCase tc cover phase fc []
157 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
158simpleCase tc cover phase fc cs
159 = let proj = phase == RunTime
160 pats = map (\ (avs, l, r) ->
161 (avs, rev phase (toPats tc l), (l, r))) cs
162 chkPats = mapM chkAccessible pats in
163 case chkPats of
164 OK pats ->
165 let numargs = length (fst (head pats))
166 ns = take numargs args
167 (tree, st) = runState
168 (match (rev phase ns) pats (defaultCase cover)) ([], numargs)
169 t = CaseDef ns (prune proj (depatt ns tree)) (fst st) in
170 if proj then return (stripLambdas t) else return t
171 Error err -> Error (At fc err)
172 where args = map (\i -> MN i "e") [0..]
173 defaultCase True = STerm Erased
174 defaultCase False = UnmatchedCase "Error"
176 chkAccessible (avs, l, c)
177 | phase == RunTime = return (l, c)
178 | otherwise = do mapM_ (acc l) avs
179 return (l, c)
181 acc [] n = Error (Inaccessible n)
182 acc (PV x : xs) n | x == n = OK ()
183 acc (PCon _ _ ps : xs) n = acc (ps ++ xs) n
184 acc (_ : xs) n = acc xs n
186rev CompileTime = id
187rev _ = reverse
189data Pat = PCon Name Int [Pat]
190 | PConst Const
191 | PV Name
192 | PAny
193 deriving Show
195-- If there are repeated variables, take the *last* one (could be name shadowing
196-- in a where clause, so take the most recent).
198toPats :: Bool -> Term -> [Pat]
199toPats tc f = reverse (toPat tc (getArgs f)) where
200 getArgs (App f a) = a : getArgs f
201 getArgs _ = []
203toPat :: Bool -> [Term] -> [Pat]
204toPat tc tms = evalState (mapM (\x -> toPat' x []) tms) []
205 where
206 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
207 return $ PCon n t args'
208 -- Typecase
209 toPat' (P (TCon t a) n _) args | tc
210 = do args' <- mapM (\x -> toPat' x []) args
211 return $ PCon n t args'
212 toPat' (Constant IType) [] | tc = return $ PCon (UN "Int") 1 []
213 toPat' (Constant FlType) [] | tc = return $ PCon (UN "Float") 2 []
214 toPat' (Constant ChType) [] | tc = return $ PCon (UN "Char") 3 []
215 toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
216 toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
217 toPat' (Constant BIType) [] | tc = return $ PCon (UN "Integer") 6 []
219 toPat' (P Bound n _) [] = do ns <- get
220 if n `elem` ns
221 then return PAny
222 else do put (n : ns)
223 return (PV n)
224 toPat' (App f a) args = toPat' f (a : args)
225 toPat' (Constant x) [] = return $ PConst x
226 toPat' _ _ = return PAny
229data Partition = Cons [Clause]
230 | Vars [Clause]
231 deriving Show
233isVarPat (PV _ : ps , _) = True
234isVarPat (PAny : ps , _) = True
235isVarPat _ = False
237isConPat (PCon _ _ _ : ps, _) = True
238isConPat (PConst _ : ps, _) = True
239isConPat _ = False
241partition :: [Clause] -> [Partition]
242partition [] = []
243partition ms@(m : _)
244 | isVarPat m = let (vars, rest) = span isVarPat ms in
245 Vars vars : partition rest
246 | isConPat m = let (cons, rest) = span isConPat ms in
247 Cons cons : partition rest
248partition xs = error $ "Partition " ++ show xs
250match :: [Name] -> [Clause] -> SC -- error case
251 -> State CS SC
252match [] (([], ret) : xs) err
253 = do (ts, v) <- get
254 put (ts ++ (map (fst.snd) xs), v)
255 case snd ret of
256 Impossible -> return ImpossibleCase
257 tm -> return $ STerm tm -- run out of arguments
258match vs cs err = do let ps = partition cs
259 cs <- mixture vs ps err
260 return cs
262mixture :: [Name] -> [Partition] -> SC -> State CS SC
263mixture vs [] err = return err
264mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
265 conRule vs ms fallthrough
266mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
267 varRule vs ms fallthrough
269data ConType = CName Name Int -- named constructor
270 | CConst Const -- constant, not implemented yet
272data Group = ConGroup ConType -- Constructor
273 [([Pat], Clause)] -- arguments and rest of alternative
275conRule :: [Name] -> [Clause] -> SC -> State CS SC
276conRule (v:vs) cs err = do groups <- groupCons cs
277 caseGroups (v:vs) groups err
279caseGroups :: [Name] -> [Group] -> SC -> State CS SC
280caseGroups (v:vs) gs err = do g <- altGroups gs
281 return $ Case v (sort g)
282 where
283 altGroups [] = return [DefaultCase err]
284 altGroups (ConGroup (CName n i) args : cs)
285 = do g <- altGroup n i args
286 rest <- altGroups cs
287 return (g : rest)
288 altGroups (ConGroup (CConst c) args : cs)
289 = do g <- altConstGroup c args
290 rest <- altGroups cs
291 return (g : rest)
293 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
294 matchCs <- match (newArgs ++ vs) nextCs err
295 return $ ConCase n i newArgs matchCs
296 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
297 matchCs <- match vs nextCs err
298 return $ ConstCase n matchCs
300argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
301argsToAlt [] = return ([], [])
302argsToAlt rs@((r, m) : rest)
303 = do newArgs <- getNewVars r
304 return (newArgs, addRs rs)
305 where
306 getNewVars [] = return []
307 getNewVars ((PV n) : ns) = do v <- getVar
308 nsv <- getNewVars ns
309 return (v : nsv)
310 getNewVars (_ : ns) = do v <- getVar
311 nsv <- getNewVars ns
312 return (v : nsv)
313 addRs [] = []
314 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
316 uniq i (UN n) = MN i n
317 uniq i n = n
319getVar :: State CS Name
320getVar = do (t, v) <- get; put (t, v+1); return (MN v "e")
322groupCons :: [Clause] -> State CS [Group]
323groupCons cs = gc [] cs
324 where
325 gc acc [] = return acc
326 gc acc ((p : ps, res) : cs) =
327 do acc' <- addGroup p ps res acc
328 gc acc' cs
329 addGroup p ps res acc = case p of
330 PCon con i args -> return $ addg con i args (ps, res) acc
331 PConst cval -> return $ addConG cval (ps, res) acc
332 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
334 addg con i conargs res [] = [ConGroup (CName con i) [(conargs, res)]]
335 addg con i conargs res (g@(ConGroup (CName n j) cs):gs)
336 | i == j = ConGroup (CName n i) (cs ++ [(conargs, res)]) : gs
337 | otherwise = g : addg con i conargs res gs
339 addConG con res [] = [ConGroup (CConst con) [([], res)]]
340 addConG con res (g@(ConGroup (CConst n) cs) : gs)
341 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
342 | otherwise = g : addConG con res gs
344varRule :: [Name] -> [Clause] -> SC -> State CS SC
345varRule (v : vs) alts err =
346 do let alts' = map (repVar v) alts
347 match vs alts' err
348 where
349 repVar v (PV p : ps , (lhs, res)) = (ps, (lhs, subst p (P Bound v Erased) res))
350 repVar v (PAny : ps , res) = (ps, res)
352-- fix: case e of S k -> f (S k) ==> case e of S k -. f e
353depatt :: [Name] -> SC -> SC
354depatt ns tm = dp [] tm
355 where
356 dp ms (STerm tm) = STerm (applyMaps ms tm)
357 dp ms (Case x alts) = Case x (map (dpa ms x) alts)
358 dp ms sc = sc
360 dpa ms x (ConCase n i args sc)
361 = ConCase n i args (dp ((x, (n, args)) : ms) sc)
362 dpa ms x (ConstCase c sc) = ConstCase c (dp ms sc)
363 dpa ms x (DefaultCase sc) = DefaultCase (dp ms sc)
365 applyMaps ms f@(App _ _)
366 | (P nt cn pty, args) <- unApply f
367 = let args' = map (applyMaps ms) args in
368 applyMap ms nt cn pty args'
369 where
370 applyMap [] nt cn pty args' = mkApp (P nt cn pty) args'
371 applyMap ((x, (n, args)) : ms) nt cn pty args'
372 | and ((n == cn) : zipWith same args args') = P Ref x Erased
373 | otherwise = applyMap ms nt cn pty args'
374 same n (P _ n' _) = n == n'
375 same _ _ = False
376 applyMaps ms (App f a) = App (applyMaps ms f) (applyMaps ms a)
377 applyMaps ms t = t
379prune :: Bool -> -- ^ Convert single branches to projections (only useful at runtime)
380 SC -> SC
381prune proj (Case n alts)
382 = let alts' = filter notErased (map pruneAlt alts) in
383 case alts' of
384 [] -> ImpossibleCase
385 as@[ConCase cn i args sc] -> if proj then mkProj n 0 args sc
386 else Case n as
387 as -> Case n as
388 where pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune proj sc)
389 pruneAlt (ConstCase c sc) = ConstCase c (prune proj sc)
390 pruneAlt (DefaultCase sc) = DefaultCase (prune proj sc)
392 notErased (DefaultCase (STerm Erased)) = False
393 notErased (DefaultCase ImpossibleCase) = False
394 notErased _ = True
396 mkProj n i [] sc = sc
397 mkProj n i (x : xs) sc = mkProj n (i + 1) xs (projRep x n i sc)
399 projRep :: Name -> Name -> Int -> SC -> SC
400 projRep arg n i (Case x alts)
401 | x == arg = ProjCase (Proj (P Bound n Erased) i)
402 (map (projRepAlt arg n i) alts)
403 | otherwise = Case x (map (projRepAlt arg n i) alts)
404 projRep arg n i (ProjCase t alts)
405 = ProjCase (projRepTm arg n i t) (map (projRepAlt arg n i) alts)
406 projRep arg n i (STerm t) = STerm (projRepTm arg n i t)
407 projRep arg n i c = c -- unmatched
409 projRepAlt arg n i (ConCase cn t args rhs)
410 = ConCase cn t args (projRep arg n i rhs)
411 projRepAlt arg n i (ConstCase t rhs)
412 = ConstCase t (projRep arg n i rhs)
413 projRepAlt arg n i (DefaultCase rhs)
414 = DefaultCase (projRep arg n i rhs)
416 projRepTm arg n i t = subst arg (Proj (P Bound n Erased) i) t
418prune _ t = t
420stripLambdas :: CaseDef -> CaseDef
421stripLambdas (CaseDef ns (STerm (Bind x (Lam _) sc)) tm)
422 = stripLambdas (CaseDef (ns ++ [x]) (STerm (instantiate (P Bound x Erased) sc)) tm)
423stripLambdas x = x