git.iko.soy/Idris-dev
on 4e4b7df help sign in
Idris-dev/src/Idris/Core/CaseTree.hs
789 lines 31 kB history raw
1{-# LANGUAGE PatternGuards, DeriveFunctor, TypeSynonymInstances #-}
3module Idris.Core.CaseTree(CaseDef(..), SC, SC'(..), CaseAlt, CaseAlt'(..), ErasureInfo,
4 Phase(..), CaseTree, CaseType(..),
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 CaseType 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!-}
44data CaseType = Updatable | Shared
45 deriving (Eq, Ord, Show)
47type SC = SC' Term
49data CaseAlt' t = ConCase Name Int [Name] !(SC' t)
50 | FnCase Name [Name] !(SC' t) -- ^ reflection function
51 | ConstCase Const !(SC' t)
52 | SucCase Name !(SC' t)
53 | DefaultCase !(SC' t)
54 deriving (Show, Eq, Ord, Functor)
55{-!
56deriving instance Binary CaseAlt'
57deriving instance NFData CaseAlt'
58!-}
60type CaseAlt = CaseAlt' Term
62instance Show t => Show (SC' t) where
63 show sc = show' 1 sc
64 where
65 show' i (Case up n alts) = "case" ++ u ++ show n ++ " of\n" ++ indent i ++
66 showSep ("\n" ++ indent i) (map (showA i) alts)
67 where u = case up of
68 Updatable -> "! "
69 Shared -> " "
70 show' i (ProjCase tm alts) = "case " ++ show tm ++ " of " ++
71 showSep ("\n" ++ indent i) (map (showA i) alts)
72 show' i (STerm tm) = show tm
73 show' i (UnmatchedCase str) = "error " ++ show str
74 show' i ImpossibleCase = "impossible"
76 indent i = concat $ take i (repeat " ")
78 showA i (ConCase n t args sc)
79 = show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
80 ++ show' (i+1) sc
81 showA i (FnCase n args sc)
82 = "FN " ++ show n ++ "(" ++ showSep (", ") (map show args) ++ ") => "
83 ++ show' (i+1) sc
84 showA i (ConstCase t sc)
85 = show t ++ " => " ++ show' (i+1) sc
86 showA i (SucCase n sc)
87 = show n ++ "+1 => " ++ show' (i+1) sc
88 showA i (DefaultCase sc)
89 = "_ => " ++ show' (i+1) sc
92type CaseTree = SC
93type Clause = ([Pat], (Term, Term))
94type CS = ([Term], Int, [(Name, Type)])
96instance TermSize SC where
97 termsize n (Case _ n' as) = termsize n as
98 termsize n (ProjCase n' as) = termsize n as
99 termsize n (STerm t) = termsize n t
100 termsize n _ = 1
102instance TermSize CaseAlt where
103 termsize n (ConCase _ _ _ s) = termsize n s
104 termsize n (FnCase _ _ s) = termsize n s
105 termsize n (ConstCase _ s) = termsize n s
106 termsize n (SucCase _ s) = termsize n s
107 termsize n (DefaultCase s) = termsize n s
109-- simple terms can be inlined trivially - good for primitives in particular
110-- To avoid duplicating work, don't inline something which uses one
111-- of its arguments in more than one place
113small :: Name -> [Name] -> SC -> Bool
114small n args t = let as = findAllUsedArgs t args in
115 length as == length (nub as) &&
116 termsize n t < 10
118namesUsed :: SC -> [Name]
119namesUsed sc = nub $ nu' [] sc where
120 nu' ps (Case _ n alts) = nub (concatMap (nua ps) alts) \\ [n]
121 nu' ps (ProjCase t alts) = nub $ nut ps t ++ concatMap (nua ps) alts
122 nu' ps (STerm t) = nub $ nut ps t
123 nu' ps _ = []
125 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc) \\ args
126 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc) \\ args
127 nua ps (ConstCase _ sc) = nu' ps sc
128 nua ps (SucCase _ sc) = nu' ps sc
129 nua ps (DefaultCase sc) = nu' ps sc
131 nut ps (P _ n _) | n `elem` ps = []
132 | otherwise = [n]
133 nut ps (App _ f a) = nut ps f ++ nut ps a
134 nut ps (Proj t _) = nut ps t
135 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
136 nut ps (Bind n b sc) = nut (n:ps) sc
137 nut ps _ = []
139-- | Return all called functions, and which arguments are used
140-- in each argument position for the call, in order to help reduce
141-- compilation time, and trace all unused arguments
142findCalls :: SC -> [Name] -> [(Name, [[Name]])]
143findCalls sc topargs = nub $ nu' topargs sc where
144 nu' ps (Case _ n alts) = nub (concatMap (nua (n : ps)) alts)
145 nu' ps (ProjCase t alts) = nub $ nut ps t ++ concatMap (nua ps) alts
146 nu' ps (STerm t) = nub $ nut ps t
147 nu' ps _ = []
149 nua ps (ConCase n i args sc) = nub (nu' (ps ++ args) sc)
150 nua ps (FnCase n args sc) = nub (nu' (ps ++ args) sc)
151 nua ps (ConstCase _ sc) = nu' ps sc
152 nua ps (SucCase _ sc) = nu' ps sc
153 nua ps (DefaultCase sc) = nu' ps sc
155 nut ps (P _ n _) | n `elem` ps = []
156 | otherwise = [(n, [])] -- tmp
157 nut ps fn@(App _ f a)
158 | (P _ n _, args) <- unApply fn
159 = if n `elem` ps then nut ps f ++ nut ps a
160 else [(n, map argNames args)] ++ concatMap (nut ps) args
161 | (P (TCon _ _) n _, _) <- unApply fn = []
162 | otherwise = nut ps f ++ nut ps a
163 nut ps (Bind n (Let t v) sc) = nut ps v ++ nut (n:ps) sc
164 nut ps (Proj t _) = nut ps t
165 nut ps (Bind n b sc) = nut (n:ps) sc
166 nut ps _ = []
168 argNames tm = let ns = directUse tm in
169 filter (\x -> x `elem` ns) topargs
171-- Find names which are used directly (i.e. not in a function call) in a term
173directUse :: TT Name -> [Name]
174directUse (P _ n _) = [n]
175directUse (Bind n (Let t v) sc) = nub $ directUse v ++ (directUse sc \\ [n])
176 ++ directUse t
177directUse (Bind n b sc) = nub $ directUse (binderTy b) ++ (directUse sc \\ [n])
178directUse fn@(App _ f a)
179 | (P Ref (UN pfk) _, [App _ e w]) <- unApply fn,
180 pfk == txt "prim_fork"
181 = directUse e ++ directUse w -- HACK so that fork works
182 | (P Ref (UN fce) _, [_, _, a]) <- unApply fn,
183 fce == txt "Force"
184 = directUse a -- forcing a value counts as a use
185 | (P Ref n _, args) <- unApply fn = [] -- need to know what n does with them
186 | (P (TCon _ _) n _, args) <- unApply fn = [] -- type constructors not used at runtime
187 | otherwise = nub $ directUse f ++ directUse a
188directUse (Proj x i) = nub $ directUse x
189directUse _ = []
191-- Find all directly used arguments (i.e. used but not in function calls)
193findUsedArgs :: SC -> [Name] -> [Name]
194findUsedArgs sc topargs = nub (findAllUsedArgs sc topargs)
196findAllUsedArgs sc topargs = filter (\x -> x `elem` topargs) (nu' sc) where
197 nu' (Case _ n alts) = n : concatMap nua alts
198 nu' (ProjCase t alts) = directUse t ++ concatMap nua alts
199 nu' (STerm t) = directUse t
200 nu' _ = []
202 nua (ConCase n i args sc) = nu' sc
203 nua (FnCase n args sc) = nu' sc
204 nua (ConstCase _ sc) = nu' sc
205 nua (SucCase _ sc) = nu' sc
206 nua (DefaultCase sc) = nu' sc
208-- Return whether name is used anywhere in a case tree
209isUsed :: SC -> Name -> Bool
210isUsed sc n = used sc where
212 used (Case _ n' alts) = n == n' || any usedA alts
213 used (ProjCase t alts) = n `elem` freeNames t || any usedA alts
214 used (STerm t) = n `elem` freeNames t
215 used _ = False
217 usedA (ConCase _ _ args sc) = used sc
218 usedA (FnCase _ args sc) = used sc
219 usedA (ConstCase _ sc) = used sc
220 usedA (SucCase _ sc) = used sc
221 usedA (DefaultCase sc) = used sc
223type ErasureInfo = Name -> [Int] -- name to list of inaccessible arguments; empty list if name not found
224type CaseBuilder a = ReaderT ErasureInfo (State CS) a
226runCaseBuilder :: ErasureInfo -> CaseBuilder a -> (CS -> (a, CS))
227runCaseBuilder ei bld = runState $ runReaderT bld ei
229data Phase = CompileTime | RunTime
230 deriving (Show, Eq)
232-- Generate a simple case tree
233-- Work Right to Left
235simpleCase :: Bool -> SC -> Bool ->
236 Phase -> FC -> [Int] -> [Type] ->
237 [([Name], Term, Term)] ->
238 ErasureInfo ->
239 TC CaseDef
240simpleCase tc defcase reflect phase fc inacc argtys cs erInfo
241 = sc' tc defcase phase fc (filter (\(_, _, r) ->
242 case r of
243 Impossible -> False
244 _ -> True) cs)
245 where
246 sc' tc defcase phase fc []
247 = return $ CaseDef [] (UnmatchedCase "No pattern clauses") []
248 sc' tc defcase phase fc cs
249 = let proj = phase == RunTime
250 vnames = fstT (head cs)
251 pats = map (\ (avs, l, r) ->
252 (avs, toPats reflect tc l, (l, r))) cs
253 chkPats = mapM chkAccessible pats in
254 case chkPats of
255 OK pats ->
256 let numargs = length (fst (head pats))
257 ns = take numargs args
258 (ns', ps') = order [(n, i `elem` inacc) | (i,n) <- zip [0..] ns] pats
259 (tree, st) = runCaseBuilder erInfo
260 (match ns' ps' defcase)
261 ([], numargs, [])
262 t = CaseDef ns (prune proj (depatt ns' tree)) (fstT st) in
263 if proj then return (stripLambdas t)
264 else return t
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 -- Check that all pattern variables are reachable by a case split
273 -- Otherwise, they won't make sense on the RHS.
274 chkAccessible (avs, l, c)
275 | phase == RunTime || reflect = return (l, c)
276 | otherwise = do mapM_ (acc l) avs
277 return (l, c)
279 acc [] n = Error (Inaccessible n)
280 acc (PV x t : xs) n | x == n = OK ()
281 acc (PCon _ _ _ ps : xs) n = acc (ps ++ xs) n
282 acc (PSuc p : xs) n = acc (p : xs) n
283 acc (_ : xs) n = acc xs n
285-- For each 'Case', make sure every choice is in the same type family,
286-- as directed by the variable type (i.e. there is no implicit type casing
287-- going on).
289checkSameTypes :: [(Name, Type)] -> SC -> Bool
290checkSameTypes tys (Case _ n alts)
291 = case lookup n tys of
292 Just t -> and (map (checkAlts t) alts)
293 _ -> and (map ((checkSameTypes tys).getSC) alts)
294 where
295 checkAlts t (ConCase n _ _ sc) = isType n t && checkSameTypes tys sc
296 checkAlts (Constant t) (ConstCase c sc) = isConstType c t && checkSameTypes tys sc
297 checkAlts _ (ConstCase c sc) = False
298 checkAlts _ _ = True
300 getSC (ConCase _ _ _ sc) = sc
301 getSC (FnCase _ _ sc) = sc
302 getSC (ConstCase _ sc) = sc
303 getSC (SucCase _ sc) = sc
304 getSC (DefaultCase sc) = sc
305checkSameTypes _ _ = True
307-- FIXME: All we're actually doing here is checking that we haven't arrived
308-- at a specific constructor for a polymorphic argument. I *think* this
309-- is sufficient, but if it turns out not to be, fix it!
310--
311-- Issue #1718 on the issue tracker: https://github.com/idris-lang/Idris-dev/issues/1718
312isType n t | (P (TCon _ _) _ _, _) <- unApply t = True
313isType n t | (P Ref _ _, _) <- unApply t = True
314isType n t = False
316isConstType (I _) (AType (ATInt ITNative)) = True
317isConstType (BI _) (AType (ATInt ITBig)) = True
318isConstType (Fl _) (AType ATFloat) = True
319isConstType (Ch _) (AType (ATInt ITChar)) = True
320isConstType (Str _) StrType = True
321isConstType (B8 _) (AType (ATInt _)) = True
322isConstType (B16 _) (AType (ATInt _)) = True
323isConstType (B32 _) (AType (ATInt _)) = True
324isConstType (B64 _) (AType (ATInt _)) = True
325isConstType _ _ = False
327data Pat = PCon Bool 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 uniq) nm@(UN n) _)
348 | n == txt "Delay"
349 = PCon uniq nm t [PAny, PAny, toPat' [] arg]
351 toPat' args (P (DCon t a uniq) nm@(NS (UN n) [own]) _)
352 | n == txt "Read" && own == txt "Ownership"
353 = PCon False nm t (map shareCons (map (toPat' []) args))
354 where shareCons (PCon _ n i ps) = PCon False n i (map shareCons ps)
355 shareCons p = p
357 toPat' args (P (DCon t a uniq) n _)
358 = PCon uniq n t $ map (toPat' []) args
360 -- n + 1
361 toPat' [p, Constant (BI 1)] (P _ (UN pabi) _)
362 | pabi == txt "prim__addBigInt"
363 = PSuc $ toPat' [] p
365 toPat' [] (P Bound n ty) = PV n ty
366 toPat' args (App _ f a) = toPat' (a : args) f
367 toPat' [] (Constant x) | isTypeConst x = PTyPat
368 | otherwise = PConst x
370 toPat' [] (Bind n (Pi _ t _) sc)
371 | reflect && noOccurrence n sc
372 = PReflected (sUN "->") [toPat' [] t, toPat' [] sc]
374 toPat' args (P _ n _)
375 | reflect
376 = PReflected n $ map (toPat' []) args
378 toPat' _ t = PAny
380 fixedN IT8 = "Bits8"
381 fixedN IT16 = "Bits16"
382 fixedN IT32 = "Bits32"
383 fixedN IT64 = "Bits64"
386data Partition = Cons [Clause]
387 | Vars [Clause]
388 deriving Show
390isVarPat (PV _ _ : ps , _) = True
391isVarPat (PAny : ps , _) = True
392isVarPat (PTyPat : ps , _) = True
393isVarPat _ = False
395isConPat (PCon _ _ _ _ : ps, _) = True
396isConPat (PReflected _ _ : ps, _) = True
397isConPat (PSuc _ : ps, _) = True
398isConPat (PConst _ : ps, _) = True
399isConPat _ = False
401partition :: [Clause] -> [Partition]
402partition [] = []
403partition ms@(m : _)
404 | isVarPat m = let (vars, rest) = span isVarPat ms in
405 Vars vars : partition rest
406 | isConPat m = let (cons, rest) = span isConPat ms in
407 Cons cons : partition rest
408partition xs = error $ "Partition " ++ show xs
410-- reorder the patterns so that the one with most distinct names
411-- comes next. Take rightmost first, otherwise (i.e. pick value rather
412-- than dependency)
413--
414-- The first argument means [(Name, IsInaccessible)].
416order :: [(Name, Bool)] -> [Clause] -> ([Name], [Clause])
417order [] cs = ([], cs)
418order ns' [] = (map fst ns', [])
419order ns' cs = let patnames = transpose (map (zip ns') (map fst cs))
420 -- only sort the arguments where there is no clash in
421 -- constructor tags between families, and no constructor/constant
422 -- clash, because otherwise we can't reliable make the
423 -- case distinction on evaluation
424 (patnames_ord, patnames_rest)
425 = Data.List.partition (noClash . map snd) patnames
426 -- note: sortBy . reverse is not nonsense because sortBy is stable
427 pats' = transpose (sortBy moreDistinct (reverse patnames_ord)
428 ++ patnames_rest) in
429 (getNOrder pats', zipWith rebuild pats' cs)
430 where
431 getNOrder [] = error $ "Failed order on " ++ show (map fst ns', cs)
432 getNOrder (c : _) = map (fst . fst) c
434 rebuild patnames clause = (map snd patnames, snd clause)
436 noClash [] = True
437 noClash (p : ps) = not (any (clashPat p) ps) && noClash ps
439 clashPat (PCon _ _ _ _) (PConst _) = True
440 clashPat (PConst _) (PCon _ _ _ _) = True
441 clashPat (PCon _ _ _ _) (PSuc _) = True
442 clashPat (PSuc _) (PCon _ _ _ _) = True
443 clashPat (PCon _ n i _) (PCon _ n' i' _) | i == i' = n /= n'
444 clashPat _ _ = False
446 -- this compares (+isInaccessible, -numberOfCases)
447 moreDistinct xs ys = compare (snd . fst . head $ xs, numNames [] (map snd ys))
448 (snd . fst . head $ ys, numNames [] (map snd xs))
450 numNames xs (PCon _ n _ _ : ps)
451 | not (Left n `elem` xs) = numNames (Left n : xs) ps
452 numNames xs (PConst c : ps)
453 | not (Right c `elem` xs) = numNames (Right c : xs) ps
454 numNames xs (_ : ps) = numNames xs ps
455 numNames xs [] = length xs
457match :: [Name] -> [Clause] -> SC -- error case
458 -> CaseBuilder SC
459match [] (([], ret) : xs) err
460 = do (ts, v, ntys) <- get
461 put (ts ++ (map (fst.snd) xs), v, ntys)
462 case snd ret of
463 Impossible -> return ImpossibleCase
464 tm -> return $ STerm tm -- run out of arguments
465match vs cs err = do let ps = partition cs
466 mixture vs ps err
468mixture :: [Name] -> [Partition] -> SC -> CaseBuilder SC
469mixture vs [] err = return err
470mixture vs (Cons ms : ps) err = do fallthrough <- mixture vs ps err
471 conRule vs ms fallthrough
472mixture vs (Vars ms : ps) err = do fallthrough <- mixture vs ps err
473 varRule vs ms fallthrough
475-- Return the list of inaccessible arguments of a data constructor.
476inaccessibleArgs :: Name -> CaseBuilder [Int]
477inaccessibleArgs n = do
478 getInaccessiblePositions <- ask -- this function is the only thing in the environment
479 return $ getInaccessiblePositions n
481data ConType = CName Name Int -- named constructor
482 | CFn Name -- reflected function name
483 | CSuc -- n+1
484 | CConst Const -- constant, not implemented yet
485 deriving (Show, Eq)
487data Group = ConGroup Bool -- Uniqueness flag
488 ConType -- Constructor
489 [([Pat], Clause)] -- arguments and rest of alternative
490 deriving Show
492conRule :: [Name] -> [Clause] -> SC -> CaseBuilder SC
493conRule (v:vs) cs err = do groups <- groupCons cs
494 caseGroups (v:vs) groups err
496caseGroups :: [Name] -> [Group] -> SC -> CaseBuilder SC
497caseGroups (v:vs) gs err = do g <- altGroups gs
498 return $ Case (getShared gs) v (sort g)
499 where
500 getShared (ConGroup True _ _ : _) = Updatable
501 getShared _ = Shared
503 altGroups [] = return [DefaultCase err]
505 altGroups (ConGroup _ (CName n i) args : cs)
506 = (:) <$> altGroup n i args <*> altGroups cs
508 altGroups (ConGroup _ (CFn n) args : cs)
509 = (:) <$> altFnGroup n args <*> altGroups cs
511 altGroups (ConGroup _ CSuc args : cs)
512 = (:) <$> altSucGroup args <*> altGroups cs
514 altGroups (ConGroup _ (CConst c) args : cs)
515 = (:) <$> altConstGroup c args <*> altGroups cs
517 altGroup n i args
518 = do inacc <- inaccessibleArgs n
519 (newVars, accVars, inaccVars, nextCs) <- argsToAlt inacc args
520 matchCs <- match (accVars ++ vs ++ inaccVars) nextCs err
521 return $ ConCase n i newVars matchCs
523 altFnGroup n args = do (newVars, _, [], nextCs) <- argsToAlt [] args
524 matchCs <- match (newVars ++ vs) nextCs err
525 return $ FnCase n newVars matchCs
527 altSucGroup args = do ([newVar], _, [], nextCs) <- argsToAlt [] args
528 matchCs <- match (newVar:vs) nextCs err
529 return $ SucCase newVar matchCs
531 altConstGroup n args = do (_, _, [], nextCs) <- argsToAlt [] args
532 matchCs <- match vs nextCs err
533 return $ ConstCase n matchCs
535-- Returns:
536-- * names of all variables arising from match
537-- * names of accessible variables (subset of all variables)
538-- * names of inaccessible variables (subset of all variables)
539-- * clauses corresponding to (accVars ++ origVars ++ inaccVars)
540argsToAlt :: [Int] -> [([Pat], Clause)] -> CaseBuilder ([Name], [Name], [Name], [Clause])
541argsToAlt _ [] = return ([], [], [], [])
542argsToAlt inacc rs@((r, m) : rest) = do
543 newVars <- getNewVars r
544 let (accVars, inaccVars) = partitionAcc newVars
545 return (newVars, accVars, inaccVars, addRs rs)
546 where
547 -- Create names for new variables arising from the given patterns.
548 getNewVars :: [Pat] -> CaseBuilder [Name]
549 getNewVars [] = return []
550 getNewVars ((PV n t) : ns) = do v <- getVar "e"
551 nsv <- getNewVars ns
553 -- Record the type of the variable.
554 --
555 -- It seems that the ordering is not important
556 -- and we can put (v,t) always in front of "ntys"
557 -- (the varName-type pairs seem to represent a mapping).
558 --
559 -- The code that reads this is currently
560 -- commented out, anyway.
561 (cs, i, ntys) <- get
562 put (cs, i, (v, t) : ntys)
564 return (v : nsv)
566 getNewVars (PAny : ns) = (:) <$> getVar "i" <*> getNewVars ns
567 getNewVars (PTyPat : ns) = (:) <$> getVar "t" <*> getNewVars ns
568 getNewVars (_ : ns) = (:) <$> getVar "e" <*> getNewVars ns
570 -- Partition a list of things into (accessible, inaccessible) things,
571 -- according to the list of inaccessible indices.
572 partitionAcc xs =
573 ( [x | (i,x) <- zip [0..] xs, i `notElem` inacc]
574 , [x | (i,x) <- zip [0..] xs, i `elem` inacc]
575 )
577 addRs [] = []
578 addRs ((r, (ps, res)) : rs) = ((acc++ps++inacc, res) : addRs rs)
579 where
580 (acc, inacc) = partitionAcc r
582 uniq i (UN n) = MN i n
583 uniq i n = n
585getVar :: String -> CaseBuilder Name
586getVar b = do (t, v, ntys) <- get; put (t, v+1, ntys); return (sMN v b)
588groupCons :: [Clause] -> CaseBuilder [Group]
589groupCons cs = gc [] cs
590 where
591 gc acc [] = return acc
592 gc acc ((p : ps, res) : cs) =
593 do acc' <- addGroup p ps res acc
594 gc acc' cs
595 addGroup p ps res acc = case p of
596 PCon uniq con i args -> return $ addg uniq (CName con i) args (ps, res) acc
597 PConst cval -> return $ addConG cval (ps, res) acc
598 PSuc n -> return $ addg False CSuc [n] (ps, res) acc
599 PReflected fn args -> return $ addg False (CFn fn) args (ps, res) acc
600 pat -> fail $ show pat ++ " is not a constructor or constant (can't happen)"
602 addg uniq c conargs res []
603 = [ConGroup uniq c [(conargs, res)]]
604 addg uniq c conargs res (g@(ConGroup _ c' cs):gs)
605 | c == c' = ConGroup uniq c (cs ++ [(conargs, res)]) : gs
606 | otherwise = g : addg uniq c conargs res gs
608 addConG con res [] = [ConGroup False (CConst con) [([], res)]]
609 addConG con res (g@(ConGroup False (CConst n) cs) : gs)
610 | con == n = ConGroup False (CConst n) (cs ++ [([], res)]) : gs
611-- | otherwise = g : addConG con res gs
612 addConG con res (g : gs) = g : addConG con res gs
614varRule :: [Name] -> [Clause] -> SC -> CaseBuilder SC
615varRule (v : vs) alts err =
616 do alts' <- mapM (repVar v) alts
617 match vs alts' err
618 where
619 repVar v (PV p ty : ps , (lhs, res))
620 = do (cs, i, ntys) <- get
621 put (cs, i, (v, ty) : ntys)
622 return (ps, (lhs, subst p (P Bound v ty) res))
623 repVar v (PAny : ps , res) = return (ps, res)
624 repVar v (PTyPat : ps , res) = return (ps, res)
626-- fix: case e of S k -> f (S k) ==> case e of S k -> f e
628depatt :: [Name] -> SC -> SC
629depatt ns tm = dp [] tm
630 where
631 dp ms (STerm tm) = STerm (applyMaps ms tm)
632 dp ms (Case up x alts) = Case up x (map (dpa ms x) alts)
633 dp ms sc = sc
635 dpa ms x (ConCase n i args sc)
636 = ConCase n i args (dp ((x, (n, args)) : ms) sc)
637 dpa ms x (FnCase n args sc)
638 = FnCase n args (dp ((x, (n, args)) : ms) sc)
639 dpa ms x (ConstCase c sc) = ConstCase c (dp ms sc)
640 dpa ms x (SucCase n sc) = SucCase n (dp ms sc)
641 dpa ms x (DefaultCase sc) = DefaultCase (dp ms sc)
643 applyMaps ms f@(App _ _ _)
644 | (P nt cn pty, args) <- unApply f
645 = let args' = map (applyMaps ms) args in
646 applyMap ms nt cn pty args'
647 where
648 applyMap [] nt cn pty args' = mkApp (P nt cn pty) args'
649 applyMap ((x, (n, args)) : ms) nt cn pty args'
650 | and ((length args == length args') :
651 (n == cn) : zipWith same args args') = P Ref x Erased
652 | otherwise = applyMap ms nt cn pty args'
653 same n (P _ n' _) = n == n'
654 same _ _ = False
656 applyMaps ms (App s f a) = App s (applyMaps ms f) (applyMaps ms a)
657 applyMaps ms t = t
659-- FIXME: Do this for SucCase too
660-- Issue #1719 on the issue tracker: https://github.com/idris-lang/Idris-dev/issues/1719
661prune :: Bool -- ^ Convert single branches to projections (only useful at runtime)
662 -> SC -> SC
663prune proj (Case up n alts) = case alts' of
664 [] -> ImpossibleCase
666 -- Projection transformations prevent us from seeing some uses of ctor fields
667 -- because they delete information about which ctor is being used.
668 -- Consider:
669 -- f (X x) = ... x ...
670 -- vs.
671 -- f x = ... x!0 ...
672 --
673 -- Hence, we disable this step.
674 -- TODO: re-enable this in toIR
675 --
676 -- as@[ConCase cn i args sc]
677 -- | proj -> mkProj n 0 args (prune proj sc)
678 -- mkProj n i xs sc = foldr (\x -> projRep x n i) sc xs
680 -- If none of the args are used in the sc, however, we can just replace it
681 -- with sc
682 as@[ConCase cn i args sc]
683 | proj -> let sc' = prune proj sc in
684 if any (isUsed sc') args
685 then Case up n [ConCase cn i args sc']
686 else sc'
688 [SucCase cn sc]
689 | proj
690 -> projRep cn n (-1) $ prune proj sc
692 [ConstCase _ sc]
693 -> prune proj sc
695 -- Bit of a hack here! The default case will always be 0, make sure
696 -- it gets caught first.
697 [s@(SucCase _ _), DefaultCase dc]
698 -> Case up n [ConstCase (BI 0) dc, s]
700 as -> Case up n as
701 where
702 alts' = filter (not . erased) $ map pruneAlt alts
704 pruneAlt (ConCase cn i ns sc) = ConCase cn i ns (prune proj sc)
705 pruneAlt (FnCase cn ns sc) = FnCase cn ns (prune proj sc)
706 pruneAlt (ConstCase c sc) = ConstCase c (prune proj sc)
707 pruneAlt (SucCase n sc) = SucCase n (prune proj sc)
708 pruneAlt (DefaultCase sc) = DefaultCase (prune proj sc)
710 erased (DefaultCase (STerm Erased)) = True
711 erased (DefaultCase ImpossibleCase) = True
712 erased _ = False
714 projRep :: Name -> Name -> Int -> SC -> SC
715 projRep arg n i (Case up x alts) | x == arg
716 = ProjCase (Proj (P Bound n Erased) i) $ map (projRepAlt arg n i) alts
717 projRep arg n i (Case up x alts)
718 = Case up x (map (projRepAlt arg n i) alts)
719 projRep arg n i (ProjCase t alts)
720 = ProjCase (projRepTm arg n i t) $ map (projRepAlt arg n i) alts
721 projRep arg n i (STerm t) = STerm (projRepTm arg n i t)
722 projRep arg n i c = c
724 projRepAlt arg n i (ConCase cn t args rhs)
725 = ConCase cn t args (projRep arg n i rhs)
726 projRepAlt arg n i (FnCase cn args rhs)
727 = FnCase cn args (projRep arg n i rhs)
728 projRepAlt arg n i (ConstCase t rhs)
729 = ConstCase t (projRep arg n i rhs)
730 projRepAlt arg n i (SucCase sn rhs)
731 = SucCase sn (projRep arg n i rhs)
732 projRepAlt arg n i (DefaultCase rhs)
733 = DefaultCase (projRep arg n i rhs)
735 projRepTm arg n i t = subst arg (Proj (P Bound n Erased) i) t
737prune _ t = t
739stripLambdas :: CaseDef -> CaseDef
740stripLambdas (CaseDef ns (STerm (Bind x (Lam _) sc)) tm)
741 = stripLambdas (CaseDef (ns ++ [x]) (STerm (instantiate (P Bound x Erased) sc)) tm)
742stripLambdas x = x
744substSC :: Name -> Name -> SC -> SC
745substSC n repl (Case up n' alts)
746 | n == n' = Case up repl (map (substAlt n repl) alts)
747 | otherwise = Case up n' (map (substAlt n repl) alts)
748substSC n repl (STerm t) = STerm $ subst n (P Bound repl Erased) t
749substSC n repl (UnmatchedCase errmsg) = UnmatchedCase errmsg
750substSC n repl ImpossibleCase = ImpossibleCase
751substSC n repl sc = error $ "unsupported in substSC: " ++ show sc
753substAlt :: Name -> Name -> CaseAlt -> CaseAlt
754substAlt n repl (ConCase cn a ns sc) = ConCase cn a ns (substSC n repl sc)
755substAlt n repl (FnCase fn ns sc) = FnCase fn ns (substSC n repl sc)
756substAlt n repl (ConstCase c sc) = ConstCase c (substSC n repl sc)
757substAlt n repl (SucCase n' sc)
758 | n == n' = SucCase n (substSC n repl sc)
759 | otherwise = SucCase n' (substSC n repl sc)
760substAlt n repl (DefaultCase sc) = DefaultCase (substSC n repl sc)
762-- mkForce n' n t updates the tree t under the assumption that
763-- n' = force n (so basically updating n to n')
764mkForce :: Name -> Name -> SC -> SC
765mkForce = mkForceSC
766 where
767 mkForceSC n arg (Case up x alts) | x == arg
768 = Case up n $ map (mkForceAlt n arg) alts
770 mkForceSC n arg (Case up x alts)
771 = Case up x (map (mkForceAlt n arg) alts)
773 mkForceSC n arg (ProjCase t alts)
774 = ProjCase t $ map (mkForceAlt n arg) alts
776 mkForceSC n arg c = c
778 mkForceAlt n arg (ConCase cn t args rhs)
779 = ConCase cn t args (mkForceSC n arg rhs)
780 mkForceAlt n arg (FnCase cn args rhs)
781 = FnCase cn args (mkForceSC n arg rhs)
782 mkForceAlt n arg (ConstCase t rhs)
783 = ConstCase t (mkForceSC n arg rhs)
784 mkForceAlt n arg (SucCase sn rhs)
785 = SucCase sn (mkForceSC n arg rhs)
786 mkForceAlt n arg (DefaultCase rhs)
787 = DefaultCase (mkForceSC n arg rhs)
789 forceTm n arg t = subst n arg t