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