git.iko.soy/Idris-dev
on ccda94e help sign in
Idris-dev/src/Idris/Core/CaseTree.hs
797 lines 31 kB history raw
1{-# LANGUAGE PatternGuards, DeriveFunctor, TypeSynonymInstances #-}
3module Idris.Core.CaseTree(CaseDef(..), SC, SC'(..), CaseAlt, CaseAlt'(..), ErasureInfo,
4 Phase(..), CaseTree,
5 simpleCase, small, namesUsed, findCalls, findUsedArgs,
6 substSC, substAlt, mkForce) where
8import Idris.Core.TT
10import Control.Applicative hiding (Const)
11import Control.Monad.State
12import Control.Monad.Reader
13import Data.Maybe
14import Data.List hiding (partition)
15import qualified Data.List(partition)
16import Debug.Trace
18data CaseDef = CaseDef [Name] !SC [Term]
19 deriving Show
21-- Note: The case-tree elaborator only produces (Case n alts)-cases;
22-- in other words, it never inspects anything else than variables.
23--
24-- ProjCase is a special powerful case construct that allows inspection
25-- of compound terms. Occurrences of ProjCase arise no earlier than
26-- in the function `prune` as a means of optimisation
27-- of already built case trees.
28--
29-- While the intermediate representation (follows in the pipeline, named LExp)
30-- allows casing on arbitrary terms, here we choose to maintain the distinction
31-- in order to allow for better optimisation opportunities.
32--
33data SC' t = Case Name [CaseAlt' t] -- ^ invariant: lowest tags first
34 | ProjCase t [CaseAlt' t] -- ^ special case for projections/thunk-forcing before inspection
35 | STerm !t
36 | UnmatchedCase String -- ^ error message
37 | ImpossibleCase -- ^ already checked to be impossible
38 deriving (Eq, Ord, Functor)
39{-!
40deriving instance Binary SC'
41deriving instance NFData SC'
42!-}
44type SC = SC' Term
46data CaseAlt' t = ConCase Name Int [Name] !(SC' t)
47 | FnCase Name [Name] !(SC' t) -- ^ reflection function
48 | ConstCase Const !(SC' t)
49 | SucCase Name !(SC' t)
50 | DefaultCase !(SC' t)
51 deriving (Show, Eq, Ord, Functor)
52{-!
53deriving instance Binary CaseAlt'
54deriving instance NFData CaseAlt'
55!-}
57type CaseAlt = CaseAlt' Term
59instance Show t => Show (SC' t) where
60 show sc = show' 1 sc
61 where
62 show' i (Case n alts) = "case " ++ show n ++ " of\n" ++ indent i ++
63 showSep ("\n" ++ indent i) (map (showA i) alts)
64 show' i (ProjCase tm alts) = "case " ++ show tm ++ " of " ++
65 showSep ("\n" ++ indent i) (map (showA i) alts)
66 show' i (STerm tm) = show tm
67 show' i (UnmatchedCase str) = "error " ++ show str
68 show' i ImpossibleCase = "impossible"
70 indent i = concat $ take i (repeat " ")
72 showA i (ConCase n t args sc)
73 = show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
74 ++ show' (i+1) sc
75 showA i (FnCase n args sc)
76 = "FN " ++ show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
77 ++ show' (i+1) sc
78 showA i (ConstCase t sc)
79 = show t ++ " => " ++ show' (i+1) sc
80 showA i (SucCase n sc)
81 = show n ++ "+1 => " ++ show' (i+1) sc
82 showA i (DefaultCase sc)
83 = "_ => " ++ show' (i+1) sc
86type CaseTree = SC
87type Clause = ([Pat], (Term, Term))
88type CS = ([Term], Int, [(Name, Type)])
90instance TermSize SC where
91 termsize n (Case n' as) = termsize n as
92 termsize n (ProjCase n' as) = termsize n as
93 termsize n (STerm t) = termsize n t
94 termsize n _ = 1
96instance TermSize CaseAlt where
97 termsize n (ConCase _ _ _ s) = termsize n s
98 termsize n (FnCase _ _ s) = termsize n s
99 termsize n (ConstCase _ s) = termsize n s
100 termsize n (SucCase _ s) = termsize n s
101 termsize n (DefaultCase s) = termsize n s
103-- simple terms can be inlined trivially - good for primitives in particular
104-- To avoid duplicating work, don't inline something which uses one
105-- of its arguments in more than one place
107small :: Name -> [Name] -> SC -> Bool
108small n args t = let as = findAllUsedArgs t args in
109 length as == length (nub as) &&
110 termsize n t < 10
112namesUsed :: SC -> [Name]
113namesUsed sc = nub $ nu' [] sc where
114 nu' ps (Case n alts) = nub (concatMap (nua ps) alts) \\ [n]
115 nu' ps (ProjCase t alts) = nub $ nut ps t ++ concatMap (nua ps) alts
116 nu' ps (STerm t) = nub $ nut ps t
117 nu' ps _ = []
119 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
120 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc) \\ args
121 nua ps (ConstCase _ sc) = nu' ps sc
122 nua ps (SucCase _ sc) = nu' ps sc
123 nua ps (DefaultCase sc) = nu' ps sc
125 nut ps (P _ n _) | n `elem` ps = []
126 | otherwise = [n]
127 nut ps (App f a) = nut ps f ++ nut ps a
128 nut ps (Proj t _) = nut ps t
129 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
130 nut ps (Bind n b sc) = nut (n:ps) sc
131 nut ps _ = []
133-- Return all called functions, and which arguments are used in each argument position
134-- for the call, in order to help reduce compilation time, and trace all unused
135-- arguments
137findCalls :: SC -> [Name] -> [(Name, [[Name]])]
138findCalls sc topargs = nub $ nu' topargs sc where
139 nu' ps (Case n alts) = nub (concatMap (nua (n : ps)) alts)
140 nu' ps (ProjCase t alts) = nub $ nut ps t ++ concatMap (nua ps) alts
141 nu' ps (STerm t) = nub $ nut ps t
142 nu' ps _ = []
144 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc)
145 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc)
146 nua ps (ConstCase _ sc) = nu' ps sc
147 nua ps (SucCase _ sc) = nu' ps sc
148 nua ps (DefaultCase sc) = nu' ps sc
150 nut ps (P Ref n _) | n `elem` ps = []
151 | otherwise = [(n, [])] -- tmp
152 nut ps fn@(App f a)
153 | (P Ref n _, args) <- unApply fn
154 = if n `elem` ps then nut ps f ++ nut ps a
155 else [(n, map argNames args)] ++ concatMap (nut ps) args
156 | (P (TCon _ _) n _, _) <- unApply fn = []
157 | otherwise = nut ps f ++ nut ps a
158 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
159 nut ps (Proj t _) = nut ps t
160 nut ps (Bind n b sc) = nut (n:ps) sc
161 nut ps _ = []
163 argNames tm = let ns = directUse tm in
164 filter (\x -> x `elem` ns) topargs
166-- Find names which are used directly (i.e. not in a function call) in a term
168directUse :: TT Name -> [Name]
169directUse (P _ n _) = [n]
170directUse (Bind n (Let t v) sc) = nub $ directUse v ++ (directUse sc \\ [n])
171 ++ directUse t
172directUse (Bind n b sc) = nub $ directUse (binderTy b) ++ (directUse sc \\ [n])
173directUse fn@(App f a)
174 | (P Ref (UN pfk) _, [App e w]) <- unApply fn,
175 pfk == txt "prim_fork"
176 = directUse e ++ directUse w -- HACK so that fork works
177 | (P Ref (UN fce) _, [_, _, a]) <- unApply fn,
178 fce == txt "Force"
179 = directUse a -- forcing a value counts as a use
180 | (P Ref n _, args) <- unApply fn = [] -- need to know what n does with them
181 | (P (TCon _ _) n _, args) <- unApply fn = [] -- type constructors not used at runtime
182 | otherwise = nub $ directUse f ++ directUse a
183directUse (Proj x i) = nub $ directUse x
184directUse _ = []
186-- Find all directly used arguments (i.e. used but not in function calls)
188findUsedArgs :: SC -> [Name] -> [Name]
189findUsedArgs sc topargs = nub (findAllUsedArgs sc topargs)
191findAllUsedArgs sc topargs = filter (\x -> x `elem` topargs) (nu' sc) where
192 nu' (Case n alts) = n : concatMap nua alts
193 nu' (ProjCase t alts) = directUse t ++ concatMap nua alts
194 nu' (STerm t) = directUse t
195 nu' _ = []
197 nua (ConCase n i args sc) = nu' sc
198 nua (FnCase n args sc) = nu' sc
199 nua (ConstCase _ sc) = nu' sc
200 nua (SucCase _ sc) = nu' sc
201 nua (DefaultCase sc) = nu' sc
203-- Return whether name is used anywhere in a case tree
204isUsed :: SC -> Name -> Bool
205isUsed sc n = used sc where
207 used (Case n' alts) = n == n' || or (map usedA alts)
208 used (ProjCase t alts) = n `elem` freeNames t || or (map usedA alts)
209 used (STerm t) = n `elem` freeNames t
210 used _ = False
212 usedA (ConCase _ _ args sc) = used sc
213 usedA (FnCase _ args sc) = used sc
214 usedA (ConstCase _ sc) = used sc
215 usedA (SucCase _ sc) = used sc
216 usedA (DefaultCase sc) = used sc
218type ErasureInfo = Name -> [Int] -- name to list of inaccessible arguments; empty list if name not found
219type CaseBuilder a = ReaderT ErasureInfo (State CS) a
221runCaseBuilder :: ErasureInfo -> CaseBuilder a -> (CS -> (a, CS))
222runCaseBuilder ei bld = runState $ runReaderT bld ei
224data Phase = CompileTime | RunTime
225 deriving (Show, Eq)
227-- Generate a simple case tree
228-- Work Right to Left
230simpleCase :: Bool -> Bool -> Bool ->
231 Phase -> FC -> [Int] -> [Type] ->
232 [([Name], Term, Term)] ->
233 ErasureInfo ->
234 TC CaseDef
235simpleCase tc cover reflect phase fc inacc argtys cs erInfo
236 = sc' tc cover phase fc (filter (\(_, _, r) ->
237 case r of
238 Impossible -> False
239 _ -> True) cs)
240 where
241 sc' tc cover phase fc []
242 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
243 sc' tc cover phase fc cs
244 = let proj = phase == RunTime
245 vnames = fstT (head cs)
246 pats = map (\ (avs, l, r) ->
247 (avs, toPats reflect tc l, (l, r))) cs
248 chkPats = mapM chkAccessible pats in
249 case chkPats of
250 OK pats ->
251 let numargs = length (fst (head pats))
252 ns = take numargs args
253 (ns', ps') = order [(n, i `elem` inacc) | (i,n) <- zip [0..] ns] pats
254 (tree, st) = runCaseBuilder erInfo
255 (match ns' ps' (defaultCase cover))
256 ([], numargs, [])
257 t = CaseDef ns (prune proj (depatt ns' tree)) (fstT st) in
258 if proj then return (stripLambdas t)
259 else return t
260-- FIXME: This check is not quite right in some cases, and is breaking
261-- perfectly valid code!
262-- if checkSameTypes (lstT st) tree
263-- then return t
264-- else Error (At fc (Msg "Typecase is not allowed"))
265 Error err -> Error (At fc err)
266 where args = map (\i -> sMN i "e") [0..]
267 defaultCase True = STerm Erased
268 defaultCase False = UnmatchedCase "Error"
269 fstT (x, _, _) = x
270 lstT (_, _, x) = x
272 chkAccessible (avs, l, c)
273 | phase == RunTime || reflect = return (l, c)
274 | otherwise = do mapM_ (acc l) avs
275 return (l, c)
277 acc [] n = Error (Inaccessible n)
278 acc (PV x t : xs) n | x == n = OK ()
279 acc (PCon _ _ ps : xs) n = acc (ps ++ xs) n
280 acc (PSuc p : xs) n = acc (p : xs) n
281 acc (_ : xs) n = acc xs n
283-- For each 'Case', make sure every choice is in the same type family,
284-- as directed by the variable type (i.e. there is no implicit type casing
285-- going on).
287checkSameTypes :: [(Name, Type)] -> SC -> Bool
288checkSameTypes tys (Case n alts)
289 = case lookup n tys of
290 Just t -> and (map (checkAlts t) alts)
291 _ -> and (map ((checkSameTypes tys).getSC) alts)
292 where
293 checkAlts t (ConCase n _ _ sc) = isType n t && checkSameTypes tys sc
294 checkAlts (Constant t) (ConstCase c sc) = isConstType c t && checkSameTypes tys sc
295 checkAlts _ (ConstCase c sc) = False
296 checkAlts _ _ = True
298 getSC (ConCase _ _ _ sc) = sc
299 getSC (FnCase _ _ sc) = sc
300 getSC (ConstCase _ sc) = sc
301 getSC (SucCase _ sc) = sc
302 getSC (DefaultCase sc) = sc
303checkSameTypes _ _ = True
305-- FIXME: All we're actually doing here is checking that we haven't arrived
306-- at a specific constructor for a polymorphic argument. I *think* this
307-- is sufficient, but if it turns out not to be, fix it!
308isType n t | (P (TCon _ _) _ _, _) <- unApply t = True
309isType n t | (P Ref _ _, _) <- unApply t = True
310isType n t = False
312isConstType (I _) (AType (ATInt ITNative)) = True
313isConstType (BI _) (AType (ATInt ITBig)) = True
314isConstType (Fl _) (AType ATFloat) = True
315isConstType (Ch _) (AType (ATInt ITChar)) = True
316isConstType (Str _) StrType = True
317isConstType (B8 _) (AType (ATInt _)) = True
318isConstType (B16 _) (AType (ATInt _)) = True
319isConstType (B32 _) (AType (ATInt _)) = True
320isConstType (B64 _) (AType (ATInt _)) = True
321isConstType (B8V _) (AType (ATInt _)) = True
322isConstType (B16V _) (AType (ATInt _)) = True
323isConstType (B32V _) (AType (ATInt _)) = True
324isConstType (B64V _) (AType (ATInt _)) = True
325isConstType _ _ = False
327data Pat = PCon Name Int [Pat]
328 | PConst Const
329 | PV Name Type
330 | PSuc Pat -- special case for n+1 on Integer
331 | PReflected Name [Pat]
332 | PAny
333 | PTyPat -- typecase, not allowed, inspect last
334 deriving Show
336-- If there are repeated variables, take the *last* one (could be name shadowing
337-- in a where clause, so take the most recent).
339toPats :: Bool -> Bool -> Term -> [Pat]
340toPats reflect tc f = reverse (toPat reflect tc (getArgs f)) where
341 getArgs (App f a) = a : getArgs f
342 getArgs _ = []
344toPat :: Bool -> Bool -> [Term] -> [Pat]
345toPat reflect tc = map $ toPat' []
346 where
347 toPat' [_,_,arg](P (DCon t a) nm@(UN n) _)
348 | n == txt "Delay"
349 = PCon nm t [PAny, PAny, toPat' [] arg]
351 toPat' args (P (DCon t a) n _)
352 = PCon n t $ map (toPat' []) args
354 -- n + 1
355 toPat' [p, Constant (BI 1)] (P _ (UN pabi) _)
356 | pabi == txt "prim__addBigInt"
357 = PSuc $ toPat' [] p
359 -- Typecase
360-- toPat' (P (TCon t a) n _) args | tc
361-- = do args' <- mapM (\x -> toPat' x []) args
362-- return $ PCon n t args'
363-- toPat' (Constant (AType (ATInt ITNative))) []
364-- | tc = return $ PCon (UN "Int") 1 []
365-- toPat' (Constant (AType ATFloat)) [] | tc = return $ PCon (UN "Float") 2 []
366-- toPat' (Constant (AType (ATInt ITChar))) [] | tc = return $ PCon (UN "Char") 3 []
367-- toPat' (Constant StrType) [] | tc = return $ PCon (UN "String") 4 []
368-- toPat' (Constant PtrType) [] | tc = return $ PCon (UN "Ptr") 5 []
369-- toPat' (Constant (AType (ATInt ITBig))) []
370-- | tc = return $ PCon (UN "Integer") 6 []
371-- toPat' (Constant (AType (ATInt (ITFixed n)))) []
372-- | tc = return $ PCon (UN (fixedN n)) (7 + fromEnum n) [] -- 7-10 inclusive
373--
375 toPat' [] (P Bound n ty) = PV n ty
376 toPat' args (App f a) = toPat' (a : args) f
377 toPat' [] (Constant (AType _)) = PTyPat
378 toPat' [] (Constant StrType) = PTyPat
379 toPat' [] (Constant PtrType) = PTyPat
380 toPat' [] (Constant VoidType) = PTyPat
381 toPat' [] (Constant x) = PConst x
383 toPat' [] (Bind n (Pi t) sc)
384 | reflect && noOccurrence n sc
385 = PReflected (sUN "->") [toPat' [] t, toPat' [] sc]
387 toPat' args (P _ n _)
388 | reflect
389 = PReflected n $ map (toPat' []) args
391 toPat' _ t = PAny
393 fixedN IT8 = "Bits8"
394 fixedN IT16 = "Bits16"
395 fixedN IT32 = "Bits32"
396 fixedN IT64 = "Bits64"
399data Partition = Cons [Clause]
400 | Vars [Clause]
401 deriving Show
403isVarPat (PV _ _ : ps , _) = True
404isVarPat (PAny : ps , _) = True
405isVarPat (PTyPat : ps , _) = True
406isVarPat _ = False
408isConPat (PCon _ _ _ : ps, _) = True
409isConPat (PReflected _ _ : ps, _) = True
410isConPat (PSuc _ : ps, _) = True
411isConPat (PConst _ : ps, _) = True
412isConPat _ = False
414partition :: [Clause] -> [Partition]
415partition [] = []
416partition ms@(m : _)
417 | isVarPat m = let (vars, rest) = span isVarPat ms in
418 Vars vars : partition rest
419 | isConPat m = let (cons, rest) = span isConPat ms in
420 Cons cons : partition rest
421partition xs = error $ "Partition " ++ show xs
423-- reorder the patterns so that the one with most distinct names
424-- comes next. Take rightmost first, otherwise (i.e. pick value rather
425-- than dependency)
426--
427-- The first argument means [(Name, IsInaccessible)].
429order :: [(Name, Bool)] -> [Clause] -> ([Name], [Clause])
430order [] cs = ([], cs)
431order ns' [] = (map fst ns', [])
432order ns' cs = let patnames = transpose (map (zip ns') (map fst cs))
433 -- only sort the arguments where there is no clash in
434 -- constructor tags between families, and no constructor/constant
435 -- clash, because otherwise we can't reliable make the
436 -- case distinction on evaluation
437 (patnames_ord, patnames_rest)
438 = Data.List.partition (noClash . map snd) patnames
439 -- note: sortBy . reverse is not nonsense because sortBy is stable
440 pats' = transpose (sortBy moreDistinct (reverse patnames_ord)
441 ++ patnames_rest) in
442 (getNOrder pats', zipWith rebuild pats' cs)
443 where
444 getNOrder [] = error $ "Failed order on " ++ show (map fst ns', cs)
445 getNOrder (c : _) = map (fst . fst) c
447 rebuild patnames clause = (map snd patnames, snd clause)
449 noClash [] = True
450 noClash (p : ps) = not (any (clashPat p) ps) && noClash ps
452 clashPat (PCon _ _ _) (PConst _) = True
453 clashPat (PConst _) (PCon _ _ _) = True
454 clashPat (PCon _ _ _) (PSuc _) = True
455 clashPat (PSuc _) (PCon _ _ _) = True
456 clashPat (PCon n i _) (PCon n' i' _) | i == i' = n /= n'
457 clashPat _ _ = False
459 -- this compares (+isInaccessible, -numberOfCases)
460 moreDistinct xs ys = compare (snd . fst . head $ xs, numNames [] (map snd ys))
461 (snd . fst . head $ ys, numNames [] (map snd xs))
463 numNames xs (PCon n _ _ : ps)
464 | not (Left n `elem` xs) = numNames (Left n : xs) ps
465 numNames xs (PConst c : ps)
466 | not (Right c `elem` xs) = numNames (Right c : xs) ps
467 numNames xs (_ : ps) = numNames xs ps
468 numNames xs [] = length xs
470match :: [Name] -> [Clause] -> SC -- error case
471 -> CaseBuilder SC
472match [] (([], ret) : xs) err
473 = do (ts, v, ntys) <- get
474 put (ts ++ (map (fst.snd) xs), v, ntys)
475 case snd ret of
476 Impossible -> return ImpossibleCase
477 tm -> return $ STerm tm -- run out of arguments
478match vs cs err = do let ps = partition cs
479 mixture vs ps err
481mixture :: [Name] -> [Partition] -> SC -> CaseBuilder SC
482mixture vs [] err = return err
483mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
484 conRule vs ms fallthrough
485mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
486 varRule vs ms fallthrough
488-- Return the list of inaccessible arguments of a data constructor.
489inaccessibleArgs :: Name -> CaseBuilder [Int]
490inaccessibleArgs n = do
491 getInaccessiblePositions <- ask -- this function is the only thing in the environment
492 return $ getInaccessiblePositions n
494data ConType = CName Name Int -- named constructor
495 | CFn Name -- reflected function name
496 | CSuc -- n+1
497 | CConst Const -- constant, not implemented yet
498 deriving (Show, Eq)
500data Group = ConGroup ConType -- Constructor
501 [([Pat], Clause)] -- arguments and rest of alternative
502 deriving Show
504conRule :: [Name] -> [Clause] -> SC -> CaseBuilder SC
505conRule (v:vs) cs err = do groups <- groupCons cs
506 caseGroups (v:vs) groups err
508caseGroups :: [Name] -> [Group] -> SC -> CaseBuilder SC
509caseGroups (v:vs) gs err = do g <- altGroups gs
510 return $ Case v (sort g)
511 where
512 altGroups [] = return [DefaultCase err]
514 altGroups (ConGroup (CName n i) args : cs)
515 = (:) <$> altGroup n i args <*> altGroups cs
517 altGroups (ConGroup (CFn n) args : cs)
518 = (:) <$> altFnGroup n args <*> altGroups cs
520 altGroups (ConGroup CSuc args : cs)
521 = (:) <$> altSucGroup args <*> altGroups cs
523 altGroups (ConGroup (CConst c) args : cs)
524 = (:) <$> altConstGroup c args <*> altGroups cs
526 altGroup n i args = do inacc <- inaccessibleArgs n
527 (newVars, accVars, inaccVars, nextCs) <- argsToAlt inacc args
528 matchCs <- match (accVars ++ vs ++ inaccVars) nextCs err
529 return $ ConCase n i newVars matchCs
531 altFnGroup n args = do (newVars, _, [], nextCs) <- argsToAlt [] args
532 matchCs <- match (newVars ++ vs) nextCs err
533 return $ FnCase n newVars matchCs
535 altSucGroup args = do ([newVar], _, [], nextCs) <- argsToAlt [] args
536 matchCs <- match (newVar:vs) nextCs err
537 return $ SucCase newVar matchCs
539 altConstGroup n args = do (_, _, [], nextCs) <- argsToAlt [] args
540 matchCs <- match vs nextCs err
541 return $ ConstCase n matchCs
543-- Returns:
544-- * names of all variables arising from match
545-- * names of accessible variables (subset of all variables)
546-- * names of inaccessible variables (subset of all variables)
547-- * clauses corresponding to (accVars ++ origVars ++ inaccVars)
548argsToAlt :: [Int] -> [([Pat], Clause)] -> CaseBuilder ([Name], [Name], [Name], [Clause])
549argsToAlt _ [] = return ([], [], [], [])
550argsToAlt inacc rs@((r, m) : rest) = do
551 newVars <- getNewVars r
552 let (accVars, inaccVars) = partitionAcc newVars
553 return (newVars, accVars, inaccVars, addRs rs)
554 where
555 -- Create names for new variables arising from the given patterns.
556 getNewVars :: [Pat] -> CaseBuilder [Name]
557 getNewVars [] = return []
558 getNewVars ((PV n t) : ns) = do v <- getVar "e"
559 nsv <- getNewVars ns
561 -- Record the type of the variable.
562 --
563 -- It seems that the ordering is not important
564 -- and we can put (v,t) always in front of "ntys"
565 -- (the varName-type pairs seem to represent a mapping).
566 --
567 -- The code that reads this is currently
568 -- commented out, anyway.
569 (cs, i, ntys) <- get
570 put (cs, i, (v, t) : ntys)
572 return (v : nsv)
574 getNewVars (PAny : ns) = (:) <$> getVar "i" <*> getNewVars ns
575 getNewVars (PTyPat : ns) = (:) <$> getVar "t" <*> getNewVars ns
576 getNewVars (_ : ns) = (:) <$> getVar "e" <*> getNewVars ns
578 -- Partition a list of things into (accessible, inaccessible) things,
579 -- according to the list of inaccessible indices.
580 partitionAcc xs =
581 ( [x | (i,x) <- zip [0..] xs, i `notElem` inacc]
582 , [x | (i,x) <- zip [0..] xs, i `elem` inacc]
583 )
585 addRs [] = []
586 addRs ((r, (ps, res)) : rs) = ((acc++ps++inacc, res) : addRs rs)
587 where
588 (acc, inacc) = partitionAcc r
590 uniq i (UN n) = MN i n
591 uniq i n = n
593getVar :: String -> CaseBuilder Name
594getVar b = do (t, v, ntys) <- get; put (t, v+1, ntys); return (sMN v b)
596groupCons :: [Clause] -> CaseBuilder [Group]
597groupCons cs = gc [] cs
598 where
599 gc acc [] = return acc
600 gc acc ((p : ps, res) : cs) =
601 do acc' <- addGroup p ps res acc
602 gc acc' cs
603 addGroup p ps res acc = case p of
604 PCon con i args -> return $ addg (CName con i) args (ps, res) acc
605 PConst cval -> return $ addConG cval (ps, res) acc
606 PSuc n -> return $ addg CSuc [n] (ps, res) acc
607 PReflected fn args -> return $ addg (CFn fn) args (ps, res) acc
608 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
610 addg c conargs res []
611 = [ConGroup c [(conargs, res)]]
612 addg c conargs res (g@(ConGroup c' cs):gs)
613 | c == c' = ConGroup c (cs ++ [(conargs, res)]) : gs
614 | otherwise = g : addg c conargs res gs
616 addConG con res [] = [ConGroup (CConst con) [([], res)]]
617 addConG con res (g@(ConGroup (CConst n) cs) : gs)
618 | con == n = ConGroup (CConst n) (cs ++ [([], res)]) : gs
619-- | otherwise = g : addConG con res gs
620 addConG con res (g : gs) = g : addConG con res gs
622varRule :: [Name] -> [Clause] -> SC -> CaseBuilder SC
623varRule (v : vs) alts err =
624 do alts' <- mapM (repVar v) alts
625 match vs alts' err
626 where
627 repVar v (PV p ty : ps , (lhs, res))
628 = do (cs, i, ntys) <- get
629 put (cs, i, (v, ty) : ntys)
630 return (ps, (lhs, subst p (P Bound v ty) res))
631 repVar v (PAny : ps , res) = return (ps, res)
632 repVar v (PTyPat : ps , res) = return (ps, res)
634-- fix: case e of S k -> f (S k) ==> case e of S k -> f e
636depatt :: [Name] -> SC -> SC
637depatt ns tm = dp [] tm
638 where
639 dp ms (STerm tm) = STerm (applyMaps ms tm)
640 dp ms (Case x alts) = Case x (map (dpa ms x) alts)
641 dp ms sc = sc
643 dpa ms x (ConCase n i args sc)
644 = ConCase n i args (dp ((x, (n, args)) : ms) sc)
645 dpa ms x (FnCase n args sc)
646 = FnCase n args (dp ((x, (n, args)) : ms) sc)
647 dpa ms x (ConstCase c sc) = ConstCase c (dp ms sc)
648 dpa ms x (SucCase n sc) = SucCase n (dp ms sc)
649 dpa ms x (DefaultCase sc) = DefaultCase (dp ms sc)
651 applyMaps ms f@(App _ _)
652 | (P nt cn pty, args) <- unApply f
653 = let args' = map (applyMaps ms) args in
654 applyMap ms nt cn pty args'
655 where
656 applyMap [] nt cn pty args' = mkApp (P nt cn pty) args'
657 applyMap ((x, (n, args)) : ms) nt cn pty args'
658 | and ((length args == length args') :
659 (n == cn) : zipWith same args args') = P Ref x Erased
660 | otherwise = applyMap ms nt cn pty args'
661 same n (P _ n' _) = n == n'
662 same _ _ = False
664 applyMaps ms (App f a) = App (applyMaps ms f) (applyMaps ms a)
665 applyMaps ms t = t
667-- FIXME: Do this for SucCase too
668prune :: Bool -- ^ Convert single branches to projections (only useful at runtime)
669 -> SC -> SC
670prune proj (Case n alts) = case alts' of
671 [] -> ImpossibleCase
673 -- Projection transformations prevent us from seeing some uses of ctor fields
674 -- because they delete information about which ctor is being used.
675 -- Consider:
676 -- f (X x) = ... x ...
677 -- vs.
678 -- f x = ... x!0 ...
679 --
680 -- Hence, we disable this step.
681 -- TODO: re-enable this in toIR
682 --
683 -- as@[ConCase cn i args sc]
684 -- | proj -> mkProj n 0 args (prune proj sc)
685 -- mkProj n i xs sc = foldr (\x -> projRep x n i) sc xs
687 -- If none of the args are used in the sc, however, we can just replace it
688 -- with sc
689 as@[ConCase cn i args sc]
690 | proj -> let sc' = prune proj sc in
691 if any (isUsed sc') args
692 then Case n [ConCase cn i args sc']
693 else sc'
695 [SucCase cn sc]
696 | proj
697 -> projRep cn n (-1) $ prune proj sc
699 [ConstCase _ sc]
700 -> prune proj sc
702 -- Bit of a hack here! The default case will always be 0, make sure
703 -- it gets caught first.
704 [s@(SucCase _ _), DefaultCase dc]
705 -> Case n [ConstCase (BI 0) dc, s]
707 as -> Case n as
708 where
709 alts' = filter (not . erased) $ map pruneAlt alts
711 pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune proj sc)
712 pruneAlt (FnCase cn ns sc) = FnCase cn ns (prune proj sc)
713 pruneAlt (ConstCase c sc) = ConstCase c (prune proj sc)
714 pruneAlt (SucCase n sc) = SucCase n (prune proj sc)
715 pruneAlt (DefaultCase sc) = DefaultCase (prune proj sc)
717 erased (DefaultCase (STerm Erased)) = True
718 erased (DefaultCase ImpossibleCase) = True
719 erased _ = False
721 projRep :: Name -> Name -> Int -> SC -> SC
722 projRep arg n i (Case x alts) | x == arg
723 = ProjCase (Proj (P Bound n Erased) i) $ map (projRepAlt arg n i) alts
724 projRep arg n i (Case x alts)
725 = Case x (map (projRepAlt arg n i) alts)
726 projRep arg n i (ProjCase t alts)
727 = ProjCase (projRepTm arg n i t) $ map (projRepAlt arg n i) alts
728 projRep arg n i (STerm t) = STerm (projRepTm arg n i t)
729 projRep arg n i c = c
731 projRepAlt arg n i (ConCase cn t args rhs)
732 = ConCase cn t args (projRep arg n i rhs)
733 projRepAlt arg n i (FnCase cn args rhs)
734 = FnCase cn args (projRep arg n i rhs)
735 projRepAlt arg n i (ConstCase t rhs)
736 = ConstCase t (projRep arg n i rhs)
737 projRepAlt arg n i (SucCase sn rhs)
738 = SucCase sn (projRep arg n i rhs)
739 projRepAlt arg n i (DefaultCase rhs)
740 = DefaultCase (projRep arg n i rhs)
742 projRepTm arg n i t = subst arg (Proj (P Bound n Erased) i) t
744prune _ t = t
746stripLambdas :: CaseDef -> CaseDef
747stripLambdas (CaseDef ns (STerm (Bind x (Lam _) sc)) tm)
748 = stripLambdas (CaseDef (ns ++ [x]) (STerm (instantiate (P Bound x Erased) sc)) tm)
749stripLambdas x = x
751substSC :: Name -> Name -> SC -> SC
752substSC n repl (Case n' alts)
753 | n == n' = Case repl (map (substAlt n repl) alts)
754 | otherwise = Case n' (map (substAlt n repl) alts)
755substSC n repl (STerm t) = STerm $ subst n (P Bound repl Erased) t
756substSC n repl (UnmatchedCase errmsg) = UnmatchedCase errmsg
757substSC n repl ImpossibleCase = ImpossibleCase
758substSC n repl sc = error $ "unsupported in substSC: " ++ show sc
760substAlt :: Name -> Name -> CaseAlt -> CaseAlt
761substAlt n repl (ConCase cn a ns sc) = ConCase cn a ns (substSC n repl sc)
762substAlt n repl (FnCase fn ns sc) = FnCase fn ns (substSC n repl sc)
763substAlt n repl (ConstCase c sc) = ConstCase c (substSC n repl sc)
764substAlt n repl (SucCase n' sc)
765 | n == n' = SucCase n (substSC n repl sc)
766 | otherwise = SucCase n' (substSC n repl sc)
767substAlt n repl (DefaultCase sc) = DefaultCase (substSC n repl sc)
769-- mkForce n' n t updates the tree t under the assumption that
770-- n' = force n (so basically updating n to n')
771mkForce :: Name -> Name -> SC -> SC
772mkForce = mkForceSC
773 where
774 mkForceSC n arg (Case x alts) | x == arg
775 = Case n $ map (mkForceAlt n arg) alts
777 mkForceSC n arg (Case x alts)
778 = Case x (map (mkForceAlt n arg) alts)
780 mkForceSC n arg (ProjCase t alts)
781 = ProjCase t $ map (mkForceAlt n arg) alts
783 mkForceSC n arg c = c
785 mkForceAlt n arg (ConCase cn t args rhs)
786 = ConCase cn t args (mkForceSC n arg rhs)
787 mkForceAlt n arg (FnCase cn args rhs)
788 = FnCase cn args (mkForceSC n arg rhs)
789 mkForceAlt n arg (ConstCase t rhs)
790 = ConstCase t (mkForceSC n arg rhs)
791 mkForceAlt n arg (SucCase sn rhs)
792 = SucCase sn (mkForceSC n arg rhs)
793 mkForceAlt n arg (DefaultCase rhs)
794 = DefaultCase (mkForceSC n arg rhs)
796 forceTm n arg t = subst n arg t