git.iko.soy/Idris-dev
on 4a1324c help sign in
Idris-dev/src/Core/CaseTree.hs
213 lines 7.8 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
10 deriving Show
12data SC = Case Name [CaseAlt]
13 | STerm Term
14 | UnmatchedCase String -- error message
15 deriving Show
17data CaseAlt = ConCase Name Int [Name] SC
18 | ConstCase Const SC
19 | DefaultCase SC
20 deriving Show
22type CaseTree = SC
23type Clause = ([Pat], Term)
24type CS = Int
26-- simple terms can be inlined trivially - good for primitives in particular
27small :: SC -> Bool
28small (STerm t) = True
29small _ = False
31simpleCase :: Bool -> [(Term, Term)] -> CaseDef
32simpleCase tc [] = CaseDef [] (UnmatchedCase "No pattern clauses")
33simpleCase tc cs = let pats = map (\ (l, r) -> (toPats tc l, r)) cs
34 numargs = length (fst (head pats))
35 ns = take numargs args in
36 CaseDef ns (evalState (match ns pats (UnmatchedCase "Error")) numargs)
37 where args = map (\i -> MN i "e") [0..]
39data Pat = PCon Name Int [Pat]
40 | PConst Const
41 | PV Name
42 | PAny
43 deriving Show
45-- If there are repeated variables, take the *last* one (could be name shadowing
46-- in a where clause, so take the most recent).
48toPats :: Bool -> Term -> [Pat]
49toPats tc f = reverse (toPat tc (getArgs f)) where
50 getArgs (App f a) = a : getArgs f
51 getArgs _ = []
53toPat :: Bool -> [Term] -> [Pat]
54toPat tc tms = evalState (mapM (\x -> toPat' x []) tms) []
55 where
56 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
57 return $ PCon n t args'
58 -- Typecase
59 toPat' (P (TCon t a) n _) args | tc
60 = do args' <- mapM (\x -> toPat' x []) args
61 return $ PCon n t args'
62 toPat' (Constant IType) [] | tc = return $ PCon (UN ["Int"]) 1 []
63 toPat' (Constant FlType) [] | tc = return $ PCon (UN ["Float"]) 2 []
64 toPat' (Constant ChType) [] | tc = return $ PCon (UN ["Char"]) 3 []
65 toPat' (Constant StrType) [] | tc = return $ PCon (UN ["String"]) 4 []
66 toPat' (Constant PtrType) [] | tc = return $ PCon (UN ["Ptr"]) 5 []
68 toPat' (P Bound n _) [] = do ns <- get
69 if n `elem` ns
70 then return PAny
71 else do put (n : ns)
72 return (PV n)
73 toPat' (App f a) args = toPat' f (a : args)
74 toPat' (Constant c) args
75 | isType c = return PAny
76 | otherwise = return $ PConst c
77 toPat' _ _ = return PAny
79 isType (I _) = False
80 isType (Fl _) = False
81 isType (Str _) = False
82 isType (Ch _) = False
83 isType _ = True
85data Partition = Cons [Clause]
86 | Vars [Clause]
88isVarPat (PV _ : ps , _) = True
89isVarPat (PAny : ps , _) = True
90isVarPat _ = False
92isConPat (PCon _ _ _ : ps, _) = True
93isConPat (PConst _ : ps, _) = True
94isConPat _ = False
96partition :: [Clause] -> [Partition]
97partition [] = []
98partition ms@(m : _)
99 | isVarPat m = let (vars, rest) = span isVarPat ms in
100 Vars vars : partition rest
101 | isConPat m = let (cons, rest) = span isConPat ms in
102 Cons cons : partition rest
103partition xs = error $ "Partition " ++ show xs
105match :: [Name] -> [Clause] -> SC -- error case
106 -> State CS SC
107match [] (([], ret) : _) err = return $ STerm ret -- run out of arguments
108match vs cs err = mixture vs (partition cs) err
110mixture :: [Name] -> [Partition] -> SC -> State CS SC
111mixture vs [] err = return err
112mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
113 conRule vs ms fallthrough
114mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
115 varRule vs ms fallthrough
117data ConType = CName Name Int -- named constructor
118 | CConst Const -- constant, not implemented yet
120data Group = ConGroup ConType -- Constructor
121 [([Pat], Clause)] -- arguments and rest of alternative
123conRule :: [Name] -> [Clause] -> SC -> State CS SC
124conRule (v:vs) cs err = do groups <- groupCons cs
125 caseGroups (v:vs) groups err
127caseGroups :: [Name] -> [Group] -> SC -> State CS SC
128caseGroups (v:vs) gs err = do g <- altGroups gs
129 return $ Case v g
130 where
131 altGroups [] = return [DefaultCase err]
132 altGroups (ConGroup (CName n i) args : cs)
133 = do g <- altGroup n i args
134 rest <- altGroups cs
135 return (g : rest)
136 altGroups (ConGroup (CConst c) args : cs)
137 = do g <- altConstGroup c args
138 rest <- altGroups cs
139 return (g : rest)
141 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
142 matchCs <- match (newArgs ++ vs) nextCs err
143 return $ ConCase n i newArgs matchCs
144 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
145 matchCs <- match vs nextCs err
146 return $ ConstCase n matchCs
148argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
149argsToAlt [] = return ([], [])
150argsToAlt rs@((r, m) : _)
151 = do newArgs <- getNewVars r
152 return (newArgs, addRs rs)
153 where
154 getNewVars [] = return []
155 getNewVars ((PV n) : ns) = do nsv <- getNewVars ns
156 return (n : nsv)
157 getNewVars (_ : ns) = do v <- getVar
158 nsv <- getNewVars ns
159 return (v : nsv)
160 addRs [] = []
161 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
163getVar :: State CS Name
164getVar = do v <- get; put (v+1); return (MN v "e")
166groupCons :: [Clause] -> State CS [Group]
167groupCons cs = gc [] cs
168 where
169 gc acc [] = return acc
170 gc acc ((p : ps, res) : cs) =
171 do acc' <- addGroup p ps res acc
172 gc acc' cs
173 addGroup p ps res acc = case p of
174 PCon con i args -> return $ addg con i args (ps, res) acc
175 PConst cval -> return $ addConG cval (ps, res) acc
176 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
178 addg con i conargs res [] = [ConGroup (CName con i) [(conargs, res)]]
179 addg con i conargs res (g@(ConGroup (CName n j) cs):gs)
180 | i == j = ConGroup (CName n i) (cs ++ [(conargs, res)]) : gs
181 | otherwise = g : addg con i conargs res gs
183 addConG con res [] = [ConGroup (CConst con) [([], res)]]
184 addConG con res (g@(ConGroup (CConst n) cs) : gs)
185 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
186 | otherwise = g : addConG con res gs
188varRule :: [Name] -> [Clause] -> SC -> State CS SC
189varRule (v : vs) alts err =
190 do let alts' = map (repVar v) alts
191 match vs alts' err
192 where
193 repVar v (PV p : ps , res) = (ps, subst p (P Bound v undefined) res)
194 repVar v (PAny : ps , res) = (ps, res)
196{-
197mkOperator :: CaseDef -> [Value] -> Maybe Value
198mkOperator (CaseDef ns casetree) args
199 | length args /= length ns = Nothing
200 | otherwise = evalArgs (zip ns args) casetree
201 where
202 evalArgs map (Case n alts) =
203 do v <- lookup n map
204 (altmap, tm) <- findAlt (getValArgs v) alts map
205 evalArgs altmap tm
206 evalArgs map (STerm tm) =
207 evalArgs map (UnmatchedCase _) = Nothing
209 getValArgs tm = getValArgs' tm []
210 getValArgs' (VApp f a) as = getValArgs' f (a:as)
211 getValArgs' f as = (f, as)
213-}