git.iko.soy/Idris-dev
on bb76c6c help sign in
Idris-dev/src/Core/CaseTree.hs
267 lines 9.7 kB history raw
1module Core.CaseTree(CaseDef(..), SC(..), CaseAlt(..), CaseTree,
2 simpleCase, small, namesUsed) where
4import Core.TT
6import Control.Monad.State
7import Data.Maybe
8import Data.List hiding (partition)
9import Debug.Trace
11data CaseDef = CaseDef [Name] SC [Term]
12 deriving Show
14data SC = Case Name [CaseAlt] -- invariant: lowest tags first
15 | STerm Term
16 | UnmatchedCase String -- error message
17 deriving (Show, Eq, Ord)
18{-!
19deriving instance Binary SC
20!-}
22data CaseAlt = ConCase Name Int [Name] SC
23 | ConstCase Const SC
24 | DefaultCase SC
25 deriving (Show, Eq, Ord)
26{-!
27deriving instance Binary CaseAlt
28!-}
30type CaseTree = SC
31type Clause = ([Pat], (Term, Term))
32type CS = ([Term], Int)
34instance TermSize SC where
35 termsize (Case n as) = termsize as
36 termsize (STerm t) = termsize t
37 termsize _ = 1
39instance TermSize CaseAlt where
40 termsize (ConCase _ _ _ s) = termsize s
41 termsize (ConstCase _ s) = termsize s
42 termsize (DefaultCase s) = termsize s
44-- simple terms can be inlined trivially - good for primitives in particular
45small :: SC -> Bool
46small t = termsize t < 150
48namesUsed :: SC -> [Name]
49namesUsed sc = nub $ nu' [] sc where
50 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
51 nu' ps (STerm t) = nub $ nut ps t
52 nu' ps _ = []
54 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
55 nua ps (ConstCase _ sc) = nu' ps sc
56 nua ps (DefaultCase sc) = nu' ps sc
58 nut ps (P _ n _) | n `elem` ps = []
59 | otherwise = [n]
60 nut ps (App f a) = nut ps f ++ nut ps a
61 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
62 nut ps (Bind n b sc) = nut (n:ps) sc
63 nut ps _ = []
65simpleCase :: Bool -> Bool -> FC -> [([Name], Term, Term)] -> TC CaseDef
66simpleCase tc cover fc []
67 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
68simpleCase tc cover fc cs
69 = let pats = map (\ (avs, l, r) -> (avs, toPats tc l, (l, r))) cs
70 chkPats = mapM chkAccessible pats in
71 case chkPats of
72 OK pats ->
73 let numargs = length (fst (head pats))
74 ns = take numargs args
75 (tree, st) = runState
76 (match ns pats (defaultCase cover)) ([], numargs) in
77 return $ CaseDef ns (prune tree) (fst st)
78 Error err -> Error (At fc err)
79 where args = map (\i -> MN i "e") [0..]
80 defaultCase True = STerm Erased
81 defaultCase False = UnmatchedCase "Error"
83 chkAccessible (avs, l, c) = do mapM_ (acc l) avs
84 return (l, c)
86 acc [] n = Error (Inaccessible n)
87 acc (PV x : xs) n | x == n = OK ()
88 acc (PCon _ _ ps : xs) n = acc (ps ++ xs) n
89 acc (_ : xs) n = acc xs n
91data Pat = PCon Name Int [Pat]
92 | PConst Const
93 | PV Name
94 | PAny
95 deriving Show
97-- If there are repeated variables, take the *last* one (could be name shadowing
98-- in a where clause, so take the most recent).
100toPats :: Bool -> Term -> [Pat]
101toPats tc f = reverse (toPat tc (getArgs f)) where
102 getArgs (App f a) = a : getArgs f
103 getArgs _ = []
105toPat :: Bool -> [Term] -> [Pat]
106toPat tc tms = evalState (mapM (\x -> toPat' x []) tms) []
107 where
108 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
109 return $ PCon n t args'
110 -- Typecase
111 toPat' (P (TCon t a) n _) args | tc
112 = do args' <- mapM (\x -> toPat' x []) args
113 return $ PCon n t args'
114 toPat' (Constant IType) [] | tc = return $ PCon (UN "Int") 1 []
115 toPat' (Constant FlType) [] | tc = return $ PCon (UN "Float") 2 []
116 toPat' (Constant ChType) [] | tc = return $ PCon (UN "Char") 3 []
117 toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
118 toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
119 toPat' (Constant BIType) [] | tc = return $ PCon (UN "Integer") 6 []
121 toPat' (P Bound n _) [] = do ns <- get
122 if n `elem` ns
123 then return PAny
124 else do put (n : ns)
125 return (PV n)
126 toPat' (App f a) args = toPat' f (a : args)
127 toPat' (Constant (I c)) [] = return $ PConst (I c)
128 toPat' _ _ = return PAny
131data Partition = Cons [Clause]
132 | Vars [Clause]
133 deriving Show
135isVarPat (PV _ : ps , _) = True
136isVarPat (PAny : ps , _) = True
137isVarPat _ = False
139isConPat (PCon _ _ _ : ps, _) = True
140isConPat (PConst _ : ps, _) = True
141isConPat _ = False
143partition :: [Clause] -> [Partition]
144partition [] = []
145partition ms@(m : _)
146 | isVarPat m = let (vars, rest) = span isVarPat ms in
147 Vars vars : partition rest
148 | isConPat m = let (cons, rest) = span isConPat ms in
149 Cons cons : partition rest
150partition xs = error $ "Partition " ++ show xs
152match :: [Name] -> [Clause] -> SC -- error case
153 -> State CS SC
154match [] (([], ret) : xs) err
155 = do (ts, v) <- get
156 put (ts ++ (map (fst.snd) xs), v)
157 return $ STerm (snd ret) -- run out of arguments
158match vs cs err = do let ps = partition cs
159 cs <- mixture vs ps err
160 return cs
162mixture :: [Name] -> [Partition] -> SC -> State CS SC
163mixture vs [] err = return err
164mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
165 conRule vs ms fallthrough
166mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
167 varRule vs ms fallthrough
169data ConType = CName Name Int -- named constructor
170 | CConst Const -- constant, not implemented yet
172data Group = ConGroup ConType -- Constructor
173 [([Pat], Clause)] -- arguments and rest of alternative
175conRule :: [Name] -> [Clause] -> SC -> State CS SC
176conRule (v:vs) cs err = do groups <- groupCons cs
177 caseGroups (v:vs) groups err
179caseGroups :: [Name] -> [Group] -> SC -> State CS SC
180caseGroups (v:vs) gs err = do g <- altGroups gs
181 return $ Case v (sort g)
182 where
183 altGroups [] = return [DefaultCase err]
184 altGroups (ConGroup (CName n i) args : cs)
185 = do g <- altGroup n i args
186 rest <- altGroups cs
187 return (g : rest)
188 altGroups (ConGroup (CConst c) args : cs)
189 = do g <- altConstGroup c args
190 rest <- altGroups cs
191 return (g : rest)
193 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
194 matchCs <- match (newArgs ++ vs) nextCs err
195 return $ ConCase n i newArgs matchCs
196 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
197 matchCs <- match vs nextCs err
198 return $ ConstCase n matchCs
200argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
201argsToAlt [] = return ([], [])
202argsToAlt rs@((r, m) : rest)
203 = do newArgs <- getNewVars r
204 return (newArgs, addRs rs)
205 where
206 getNewVars [] = return []
207 getNewVars ((PV n) : ns) = do v <- getVar
208 nsv <- getNewVars ns
209 return (v : nsv)
210 getNewVars (_ : ns) = do v <- getVar
211 nsv <- getNewVars ns
212 return (v : nsv)
213 addRs [] = []
214 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
216 uniq i (UN n) = MN i n
217 uniq i n = n
219getVar :: State CS Name
220getVar = do (t, v) <- get; put (t, v+1); return (MN v "e")
222groupCons :: [Clause] -> State CS [Group]
223groupCons cs = gc [] cs
224 where
225 gc acc [] = return acc
226 gc acc ((p : ps, res) : cs) =
227 do acc' <- addGroup p ps res acc
228 gc acc' cs
229 addGroup p ps res acc = case p of
230 PCon con i args -> return $ addg con i args (ps, res) acc
231 PConst cval -> return $ addConG cval (ps, res) acc
232 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
234 addg con i conargs res [] = [ConGroup (CName con i) [(conargs, res)]]
235 addg con i conargs res (g@(ConGroup (CName n j) cs):gs)
236 | i == j = ConGroup (CName n i) (cs ++ [(conargs, res)]) : gs
237 | otherwise = g : addg con i conargs res gs
239 addConG con res [] = [ConGroup (CConst con) [([], res)]]
240 addConG con res (g@(ConGroup (CConst n) cs) : gs)
241 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
242 | otherwise = g : addConG con res gs
244varRule :: [Name] -> [Clause] -> SC -> State CS SC
245varRule (v : vs) alts err =
246 do let alts' = map (repVar v) alts
247 match vs alts' err
248 where
249 repVar v (PV p : ps , (lhs, res)) = (ps, (lhs, subst p (P Bound v (V 0)) res))
250 repVar v (PAny : ps , res) = (ps, res)
252prune :: SC -> SC
253prune (Case n alts)
254 = let alts' = map pruneAlt $
255 filter notErased alts in
256 case alts' of
257 [] -> STerm Erased
258 as -> Case n as
259 where pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune sc)
260 pruneAlt (ConstCase c sc) = ConstCase c (prune sc)
261 pruneAlt (DefaultCase sc) = DefaultCase (prune sc)
263 notErased (DefaultCase (STerm Erased)) = False
264 notErased _ = True
265prune t = t