git.iko.soy/Idris-dev
on 067f4fa help sign in
Idris-dev/src/Core/CaseTree.hs
239 lines 8.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]
15 | STerm Term
16 | UnmatchedCase String -- error message
17 deriving Show
18{-!
19deriving instance Binary SC
20!-}
22data CaseAlt = ConCase Name Int [Name] SC
23 | ConstCase Const SC
24 | DefaultCase SC
25 deriving Show
26{-!
27deriving instance Binary CaseAlt
28!-}
30type CaseTree = SC
31type Clause = ([Pat], (Term, Term))
32type CS = ([Term], Int)
34-- simple terms can be inlined trivially - good for primitives in particular
35small :: SC -> Bool
36-- small (STerm t) = True
37small _ = False
39namesUsed :: SC -> [Name]
40namesUsed sc = nub $ nu' [] sc where
41 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
42 nu' ps (STerm t) = nub $ nut ps t
43 nu' ps _ = []
45 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
46 nua ps (ConstCase _ sc) = nu' ps sc
47 nua ps (DefaultCase sc) = nu' ps sc
49 nut ps (P _ n _) | n `elem` ps = []
50 | otherwise = [n]
51 nut ps (App f a) = nut ps f ++ nut ps a
52 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
53 nut ps (Bind n b sc) = nut (n:ps) sc
54 nut ps _ = []
56simpleCase :: Bool -> Bool -> [(Term, Term)] -> CaseDef
57simpleCase tc cover []
58 = CaseDef [] (UnmatchedCase "No pattern clauses") []
59simpleCase tc cover cs
60 = let pats = map (\ (l, r) -> (toPats tc l, (l, r))) cs
61 numargs = length (fst (head pats))
62 ns = take numargs args
63 (tree, st) = runState (match ns pats (defaultCase cover)) ([], numargs) in
64 CaseDef ns (prune tree) (fst st)
65 where args = map (\i -> MN i "e") [0..]
66 defaultCase True = STerm Erased
67 defaultCase False = UnmatchedCase "Error"
69data Pat = PCon Name Int [Pat]
70 | PConst Const
71 | PV Name
72 | PAny
73 deriving Show
75-- If there are repeated variables, take the *last* one (could be name shadowing
76-- in a where clause, so take the most recent).
78toPats :: Bool -> Term -> [Pat]
79toPats tc f = reverse (toPat tc (getArgs f)) where
80 getArgs (App f a) = a : getArgs f
81 getArgs _ = []
83toPat :: Bool -> [Term] -> [Pat]
84toPat tc tms = evalState (mapM (\x -> toPat' x []) tms) []
85 where
86 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
87 return $ PCon n t args'
88 -- Typecase
89 toPat' (P (TCon t a) n _) args | tc
90 = do args' <- mapM (\x -> toPat' x []) args
91 return $ PCon n t args'
92 toPat' (Constant IType) [] | tc = return $ PCon (UN "Int") 1 []
93 toPat' (Constant FlType) [] | tc = return $ PCon (UN "Float") 2 []
94 toPat' (Constant ChType) [] | tc = return $ PCon (UN "Char") 3 []
95 toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
96 toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
97 toPat' (Constant BIType) [] | tc = return $ PCon (UN "Integer") 6 []
99 toPat' (P Bound n _) [] = do ns <- get
100 if n `elem` ns
101 then return PAny
102 else do put (n : ns)
103 return (PV n)
104 toPat' (App f a) args = toPat' f (a : args)
105 toPat' (Constant (I c)) [] = return $ PConst (I c)
106 toPat' _ _ = return PAny
109data Partition = Cons [Clause]
110 | Vars [Clause]
112isVarPat (PV _ : ps , _) = True
113isVarPat (PAny : ps , _) = True
114isVarPat _ = False
116isConPat (PCon _ _ _ : ps, _) = True
117isConPat (PConst _ : ps, _) = True
118isConPat _ = False
120partition :: [Clause] -> [Partition]
121partition [] = []
122partition ms@(m : _)
123 | isVarPat m = let (vars, rest) = span isVarPat ms in
124 Vars vars : partition rest
125 | isConPat m = let (cons, rest) = span isConPat ms in
126 Cons cons : partition rest
127partition xs = error $ "Partition " ++ show xs
129match :: [Name] -> [Clause] -> SC -- error case
130 -> State CS SC
131match [] (([], ret) : xs) err
132 = do (ts, v) <- get
133 put (ts ++ (map (fst.snd) xs), v)
134 return $ STerm (snd ret) -- run out of arguments
135match vs cs err = do cs <- mixture vs (partition cs) err
136 return cs
138mixture :: [Name] -> [Partition] -> SC -> State CS SC
139mixture vs [] err = return err
140mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
141 conRule vs ms fallthrough
142mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
143 varRule vs ms fallthrough
145data ConType = CName Name Int -- named constructor
146 | CConst Const -- constant, not implemented yet
148data Group = ConGroup ConType -- Constructor
149 [([Pat], Clause)] -- arguments and rest of alternative
151conRule :: [Name] -> [Clause] -> SC -> State CS SC
152conRule (v:vs) cs err = do groups <- groupCons cs
153 caseGroups (v:vs) groups err
155caseGroups :: [Name] -> [Group] -> SC -> State CS SC
156caseGroups (v:vs) gs err = do g <- altGroups gs
157 return $ Case v g
158 where
159 altGroups [] = return [DefaultCase err]
160 altGroups (ConGroup (CName n i) args : cs)
161 = do g <- altGroup n i args
162 rest <- altGroups cs
163 return (g : rest)
164 altGroups (ConGroup (CConst c) args : cs)
165 = do g <- altConstGroup c args
166 rest <- altGroups cs
167 return (g : rest)
169 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
170 matchCs <- match (newArgs ++ vs) nextCs err
171 return $ ConCase n i newArgs matchCs
172 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
173 matchCs <- match vs nextCs err
174 return $ ConstCase n matchCs
176argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
177argsToAlt [] = return ([], [])
178argsToAlt rs@((r, m) : _)
179 = do newArgs <- getNewVars r
180 return (newArgs, addRs rs)
181 where
182 getNewVars [] = return []
183 getNewVars ((PV n) : ns) = do nsv <- getNewVars ns
184 return (n : nsv)
185 getNewVars (_ : ns) = do v <- getVar
186 nsv <- getNewVars ns
187 return (v : nsv)
188 addRs [] = []
189 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
191getVar :: State CS Name
192getVar = do (t, v) <- get; put (t, v+1); return (MN v "e")
194groupCons :: [Clause] -> State CS [Group]
195groupCons cs = gc [] cs
196 where
197 gc acc [] = return acc
198 gc acc ((p : ps, res) : cs) =
199 do acc' <- addGroup p ps res acc
200 gc acc' cs
201 addGroup p ps res acc = case p of
202 PCon con i args -> return $ addg con i args (ps, res) acc
203 PConst cval -> return $ addConG cval (ps, res) acc
204 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
206 addg con i conargs res [] = [ConGroup (CName con i) [(conargs, res)]]
207 addg con i conargs res (g@(ConGroup (CName n j) cs):gs)
208 | i == j = ConGroup (CName n i) (cs ++ [(conargs, res)]) : gs
209 | otherwise = g : addg con i conargs res gs
211 addConG con res [] = [ConGroup (CConst con) [([], res)]]
212 addConG con res (g@(ConGroup (CConst n) cs) : gs)
213 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
214 | otherwise = g : addConG con res gs
216varRule :: [Name] -> [Clause] -> SC -> State CS SC
217varRule (v : vs) alts err =
218 do let alts' = map (repVar v) alts
219 match vs alts' err
220 where
221 repVar v (PV p : ps , (lhs, res)) = (ps, (lhs, subst p (P Bound v (V 0)) res))
222 repVar v (PAny : ps , res) = (ps, res)
224prune :: SC -> SC
225prune (Case n alts)
226 = let alts' = map pruneAlt $
227 filter notErased alts in
228 case alts' of
229 [] -> STerm Erased
230 as -> Case n as
231 where pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune sc)
232 pruneAlt (ConstCase c sc) = ConstCase c (prune sc)
233 pruneAlt (DefaultCase sc) = DefaultCase (prune sc)
235 notErased (DefaultCase (STerm Erased)) = False
236 notErased _ = True
237prune t = t