git.iko.soy/Idris-dev
on 5fbca2a help sign in
Idris-dev/src/Core/CaseTree.hs
198 lines 7.0 kB history raw
1module Core.CaseTree(CaseDef(..), SC(..), CaseAlt(..), CaseTree,
2 simpleCase) 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
26simpleCase :: [(Term, Term)] -> CaseDef
27simpleCase [] = CaseDef [] (UnmatchedCase "No pattern clauses")
28simpleCase cs = let pats = map (\ (l, r) -> (toPats l, r)) cs
29 numargs = length (fst (head pats))
30 ns = take numargs args in
31 CaseDef ns (evalState (match ns pats (UnmatchedCase "Error")) numargs)
32 where args = map (\i -> MN i "e") [0..]
34data Pat = PCon Name Int [Pat]
35 | PConst Const
36 | PV Name
37 | PAny
38 deriving Show
40-- If there are repeated variables, take the *last* one (could be name shadowing
41-- in a where clause, so take the most recent).
43toPats :: Term -> [Pat]
44toPats f = reverse (toPat (getArgs f)) where
45 getArgs (App f a) = a : getArgs f
46 getArgs _ = []
48toPat :: [Term] -> [Pat]
49toPat tms = evalState (mapM (\x -> toPat' x []) tms) []
50 where
51 toPat' (P (DCon t a) n _) args = do args' <- mapM (\x -> toPat' x []) args
52 return $ PCon n t args'
53 toPat' (P Bound n _) [] = do ns <- get
54 if n `elem` ns
55 then return PAny
56 else do put (n : ns)
57 return (PV n)
58 toPat' (App f a) args = toPat' f (a : args)
59 toPat' (Constant c) args
60 | isType c = return PAny
61 | otherwise = return $ PConst c
62 toPat' _ _ = return PAny
64 isType (I _) = False
65 isType (Fl _) = False
66 isType (Str _) = False
67 isType (Ch _) = False
68 isType _ = True
70data Partition = Cons [Clause]
71 | Vars [Clause]
73isVarPat (PV _ : ps , _) = True
74isVarPat (PAny : ps , _) = True
75isVarPat _ = False
77isConPat (PCon _ _ _ : ps, _) = True
78isConPat (PConst _ : ps, _) = True
79isConPat _ = False
81partition :: [Clause] -> [Partition]
82partition [] = []
83partition ms@(m : _)
84 | isVarPat m = let (vars, rest) = span isVarPat ms in
85 Vars vars : partition rest
86 | isConPat m = let (cons, rest) = span isConPat ms in
87 Cons cons : partition rest
88partition xs = error $ "Partition " ++ show xs
90match :: [Name] -> [Clause] -> SC -- error case
91 -> State CS SC
92match [] (([], ret) : _) err = return $ STerm ret -- run out of arguments
93match vs cs err = mixture vs (partition cs) err
95mixture :: [Name] -> [Partition] -> SC -> State CS SC
96mixture vs [] err = return err
97mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
98 conRule vs ms fallthrough
99mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
100 varRule vs ms fallthrough
102data ConType = CName Name Int -- named constructor
103 | CConst Const -- constant, not implemented yet
105data Group = ConGroup ConType -- Constructor
106 [([Pat], Clause)] -- arguments and rest of alternative
108conRule :: [Name] -> [Clause] -> SC -> State CS SC
109conRule (v:vs) cs err = do groups <- groupCons cs
110 caseGroups (v:vs) groups err
112caseGroups :: [Name] -> [Group] -> SC -> State CS SC
113caseGroups (v:vs) gs err = do g <- altGroups gs
114 return $ Case v g
115 where
116 altGroups [] = return [DefaultCase err]
117 altGroups (ConGroup (CName n i) args : cs)
118 = do g <- altGroup n i args
119 rest <- altGroups cs
120 return (g : rest)
121 altGroups (ConGroup (CConst c) args : cs)
122 = do g <- altConstGroup c args
123 rest <- altGroups cs
124 return (g : rest)
126 altGroup n i gs = do (newArgs, nextCs) <- argsToAlt gs
127 matchCs <- match (newArgs ++ vs) nextCs err
128 return $ ConCase n i newArgs matchCs
129 altConstGroup n gs = do (_, nextCs) <- argsToAlt gs
130 matchCs <- match vs nextCs err
131 return $ ConstCase n matchCs
133argsToAlt :: [([Pat], Clause)] -> State CS ([Name], [Clause])
134argsToAlt [] = return ([], [])
135argsToAlt rs@((r, m) : _)
136 = do newArgs <- getNewVars r
137 return (newArgs, addRs rs)
138 where
139 getNewVars [] = return []
140 getNewVars ((PV n) : ns) = do nsv <- getNewVars ns
141 return (n : nsv)
142 getNewVars (_ : ns) = do v <- getVar
143 nsv <- getNewVars ns
144 return (v : nsv)
145 addRs [] = []
146 addRs ((r, (ps, res)) : rs) = ((r++ps, res) : addRs rs)
148getVar :: State CS Name
149getVar = do v <- get; put (v+1); return (MN v "e")
151groupCons :: [Clause] -> State CS [Group]
152groupCons cs = gc [] cs
153 where
154 gc acc [] = return acc
155 gc acc ((p : ps, res) : cs) =
156 do acc' <- addGroup p ps res acc
157 gc acc' cs
158 addGroup p ps res acc = case p of
159 PCon con i args -> return $ addg con i args (ps, res) acc
160 PConst cval -> return $ addConG cval (ps, res) acc
161 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
163 addg con i conargs res [] = [ConGroup (CName con i) [(conargs, res)]]
164 addg con i conargs res (g@(ConGroup (CName n j) cs):gs)
165 | i == j = ConGroup (CName n i) (cs ++ [(conargs, res)]) : gs
166 | otherwise = g : addg con i conargs res gs
168 addConG con res [] = [ConGroup (CConst con) [([], res)]]
169 addConG con res (g@(ConGroup (CConst n) cs) : gs)
170 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
171 | otherwise = g : addConG con res gs
173varRule :: [Name] -> [Clause] -> SC -> State CS SC
174varRule (v : vs) alts err =
175 do let alts' = map (repVar v) alts
176 match vs alts' err
177 where
178 repVar v (PV p : ps , res) = (ps, subst p (P Bound v undefined) res)
179 repVar v (PAny : ps , res) = (ps, res)
181{-
182mkOperator :: CaseDef -> [Value] -> Maybe Value
183mkOperator (CaseDef ns casetree) args
184 | length args /= length ns = Nothing
185 | otherwise = evalArgs (zip ns args) casetree
186 where
187 evalArgs map (Case n alts) =
188 do v <- lookup n map
189 (altmap, tm) <- findAlt (getValArgs v) alts map
190 evalArgs altmap tm
191 evalArgs map (STerm tm) =
192 evalArgs map (UnmatchedCase _) = Nothing
194 getValArgs tm = getValArgs' tm []
195 getValArgs' (VApp f a) as = getValArgs' f (a:as)
196 getValArgs' f as = (f, as)
198-}