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