0 | module Core.Case.CaseBuilder
2 | import Core.Case.CaseTree
3 | import Core.Case.Util
4 | import Core.Context.Log
6 | import Core.Normalise
10 | import Idris.Pretty.Annotations
13 | import Data.List.Quantifiers
14 | import Data.SortedSet
17 | import Libraries.Data.IMaybe
18 | import Libraries.Data.List.SizeOf
19 | import Libraries.Data.List.LengthMatch
20 | import Libraries.Data.List01
21 | import Libraries.Data.List01.Quantifiers
23 | import Decidable.Equality
25 | import Libraries.Text.PrettyPrint.Prettyprinter
29 | %hide Symbols.equals
32 | data Phase = CompileTime RigCount | RunTime
35 | CompileTime r == CompileTime r' = r == r'
36 | RunTime == RunTime = True
39 | data ArgType : Scoped where
40 | Known : RigCount -> (ty : Term vars) -> ArgType vars
41 | Stuck : (fty : Term vars) -> ArgType vars
44 | Unknown : ArgType vars
47 | HasNames (ArgType vars) where
48 | full gam (Known c ty) = Known c <$> full gam ty
49 | full gam (Stuck ty) = Stuck <$> full gam ty
50 | full gam Unknown = pure Unknown
52 | resolved gam (Known c ty) = Known c <$> resolved gam ty
53 | resolved gam (Stuck ty) = Stuck <$> resolved gam ty
54 | resolved gam Unknown = pure Unknown
57 | {ns : _} -> Show (ArgType ns) where
58 | show (Known c t) = "Known " ++ show c ++ " " ++ show t
59 | show (Stuck t) = "Stuck " ++ show t
60 | show Unknown = "Unknown"
62 | record PatInfo (pvar : Name) (vars : Scope) where
67 | 0 loc : IsVar name idx vars
68 | argType : ArgType vars
72 | {vars : _} -> Show (PatInfo n vars) where
73 | show pi = show (pat pi) ++ " : " ++ show (argType pi)
75 | HasNames (PatInfo n vars) where
76 | full gam (MkInfo pat loc argType)
77 | = do pat <- full gam pat
78 | argType <- full gam argType
79 | pure $
MkInfo pat loc argType
81 | resolved gam (MkInfo pat loc argType)
82 | = do pat <- resolved gam pat
83 | argType <- resolved gam argType
84 | pure $
MkInfo pat loc argType
97 | data NamedPats : List Name ->
99 | Nil : NamedPats [] vars
100 | (::) : PatInfo pvar vars ->
104 | NamedPats ns vars -> NamedPats (pvar :: ns) vars
106 | getPatInfo : NamedPats todo vars -> List Pat
108 | getPatInfo (x :: xs) = pat x :: getPatInfo xs
110 | updatePats : {vars, todo : _} ->
111 | {auto c : Ref Ctxt Defs} ->
113 | NF vars -> NamedPats todo vars -> Core (NamedPats todo vars)
114 | updatePats env nf [] = pure []
115 | updatePats {todo = pvar :: ns} env (NBind fc _ (Pi _ c _ farg) fsc) (p :: ps)
116 | = case argType p of
118 | do defs <- get Ctxt
119 | empty <- clearDefs defs
120 | pure ({ argType := Known c !(quote empty env farg) } p
121 | :: !(updatePats env !(fsc defs (toClosure defaultOpts env (Ref fc Bound pvar))) ps))
122 | _ => pure (p :: ps)
123 | updatePats env nf (p :: ps)
124 | = case argType p of
126 | do defs <- get Ctxt
127 | empty <- clearDefs defs
128 | pure ({ argType := Stuck !(quote empty env nf) } p :: ps)
129 | _ => pure (p :: ps)
131 | substInPatInfo : {pvar, vars, todo : _} ->
132 | {auto c : Ref Ctxt Defs} ->
133 | FC -> Name -> Term vars -> PatInfo pvar vars ->
134 | NamedPats todo vars ->
135 | Core (PatInfo pvar vars, NamedPats todo vars)
136 | substInPatInfo fc n tm p ps
137 | = case argType p of
139 | do defs <- get Ctxt
140 | tynf <- nf defs (mkEnv fc vars) ty
143 | pure ({ argType := Known c (substName n tm ty) } p, ps)
147 | do defs <- get Ctxt
148 | empty <- clearDefs defs
149 | let env = mkEnv fc vars
150 | case !(nf defs env (substName n tm fty)) of
151 | NBind pfc _ (Pi _ c _ farg) fsc =>
152 | pure ({ argType := Known c !(quote empty env farg) } p,
154 | !(fsc defs (toClosure defaultOpts env
155 | (Ref pfc Bound pvar))) ps))
157 | Unknown => pure (p, ps)
161 | substInPats : {vars, todo : _} ->
162 | {auto c : Ref Ctxt Defs} ->
163 | FC -> Name -> Term vars -> NamedPats todo vars ->
164 | Core (NamedPats todo vars)
165 | substInPats fc n tm [] = pure []
166 | substInPats fc n tm (p :: ps)
167 | = do (p', ps') <- substInPatInfo fc n tm p ps
168 | pure (p' :: !(substInPats fc n tm ps'))
170 | getPat : {idx : Nat} ->
171 | (0 el : IsVar nm idx ps) -> NamedPats ps ns -> PatInfo nm ns
172 | getPat First (x :: xs) = x
173 | getPat (Later p) (x :: xs) = getPat p xs
175 | dropPat : {idx : Nat} ->
176 | (0 el : IsVar nm idx ps) ->
177 | NamedPats ps ns -> NamedPats (dropIsVar ps el) ns
178 | dropPat First (x :: xs) = xs
179 | dropPat (Later p) (x :: xs) = x :: dropPat p xs
181 | HasNames (NamedPats todo vars) where
182 | full gam [] = pure []
183 | full gam (x::xs) = [| (::) (full gam x) (full gam xs) |]
185 | resolved gam [] = pure []
186 | resolved gam (x::xs) = [| (::) (resolved gam x) (resolved gam xs) |]
189 | {vars : _} -> {todo : _} -> Show (NamedPats todo vars) where
190 | show xs = "[" ++ showAll xs ++ "]"
192 | showAll : {vs, ts : _} -> NamedPats ts vs -> String
194 | showAll {ts = t :: _} [x]
195 | = show t ++ " " ++ show (pat x) ++ " [" ++ show (argType x) ++ "]"
196 | showAll {ts = t :: _} (x :: xs)
197 | = show t ++ " " ++ show (pat x) ++ " [" ++ show (argType x) ++ "]"
198 | ++ ", " ++ showAll xs
200 | {vars : _} -> {todo : _} -> Pretty IdrisSyntax (NamedPats todo vars) where
201 | pretty xs = hsep $
prettyAll xs
203 | prettyAll : {vs, ts : _} -> NamedPats ts vs -> List (Doc IdrisSyntax)
205 | prettyAll {ts = t :: _} (x :: xs)
206 | = parens (pretty0 t <++> equals <++> pretty (pat x))
209 | Weaken ArgType where
210 | weaken (Known c ty) = Known c (weaken ty)
211 | weaken (Stuck fty) = Stuck (weaken fty)
212 | weaken Unknown = Unknown
214 | weakenNs s (Known c ty) = Known c (weakenNs s ty)
215 | weakenNs s (Stuck fty) = Stuck (weakenNs s fty)
216 | weakenNs s Unknown = Unknown
218 | Weaken (PatInfo p) where
219 | weakenNs s (MkInfo p el fty) = MkInfo p (weakenIsVar s el) (weakenNs s fty)
221 | Weaken (NamedPats todo) where
223 | weaken (p :: ps) = weaken p :: weaken ps
225 | weakenNs ns [] = []
226 | weakenNs ns (p :: ps) = weakenNs ns p :: weakenNs ns ps
228 | (++) : NamedPats ms vars -> NamedPats ns vars -> NamedPats (ms ++ ns) vars
230 | (++) (x :: xs) ys = x :: xs ++ ys
232 | tail : NamedPats (p :: ps) vars -> NamedPats ps vars
233 | tail (x :: xs) = xs
235 | data PatClause : (todo : List Name) -> Scoped where
236 | MkPatClause : List Name ->
237 | NamedPats todo vars ->
238 | Int -> (rhs : Term vars) -> PatClause todo vars
240 | getNPs : PatClause todo vars -> NamedPats todo vars
241 | getNPs (MkPatClause _ lhs pid rhs) = lhs
244 | {vars : _} -> {todo : _} -> Show (PatClause todo vars) where
245 | show (MkPatClause _ ps pid rhs)
246 | = show ps ++ " => " ++ show rhs
248 | {vars : _} -> {todo : _} -> Pretty IdrisSyntax (PatClause todo vars) where
249 | pretty (MkPatClause _ ps _ rhs)
250 | = pretty ps <++> fatArrow <++> byShow rhs
252 | HasNames (PatClause todo vars) where
253 | full gam (MkPatClause ns nps i rhs)
254 | = [| MkPatClause (traverse (full gam) ns) (full gam nps) (pure i) (full gam rhs) |]
256 | resolved gam (MkPatClause ns nps i rhs)
257 | = [| MkPatClause (traverse (resolved gam) ns) (resolved gam nps) (pure i) (resolved gam rhs) |]
259 | 0 IsConClause : PatClause (a :: todo) vars -> Type
260 | IsConClause (MkPatClause _ (MkInfo pat _ _ :: _) _ _) = IsConPat pat
262 | substInClause : {a, vars, todo : _} ->
263 | {auto c : Ref Ctxt Defs} ->
264 | FC -> Subset (PatClause (a :: todo) vars) IsConClause ->
265 | Core (Subset (PatClause (a :: todo) vars) IsConClause)
266 | substInClause fc (Element (MkPatClause pvars (MkInfo pat pprf fty :: pats) pid rhs) isCons)
267 | = do pats' <- substInPats fc a (mkTerm vars pat) pats
268 | pure $
Element (MkPatClause pvars (MkInfo pat pprf fty :: pats') pid rhs) isCons
270 | data Partitions : List01 ne (PatClause (a :: todo) vars) -> Type where
271 | ConClauses : {a, todo, vars : _} ->
272 | {ps : List01 ne (PatClause (a :: todo) vars)} ->
273 | (cs : List01 True (PatClause (a :: todo) vars )) ->
274 | (0 isCons : All IsConClause cs) =>
275 | Partitions ps -> Partitions (cs ++ ps)
276 | VarClauses : {a, todo, vars : _} ->
277 | {ps : List01 ne (PatClause (a :: todo) vars)} ->
278 | (vs : List01 True (PatClause (a :: todo) vars)) ->
279 | Partitions ps -> Partitions (vs ++ ps)
280 | NoClauses : Partitions []
283 | {ps : _} -> Show (Partitions ps) where
284 | show (ConClauses cs rest)
285 | = unlines ("CON" :: map ((" " ++) . show) (forget cs))
286 | ++ "\n, " ++ show rest
287 | show (VarClauses vs rest)
288 | = unlines ("VAR" :: map ((" " ++) . show) (forget vs))
289 | ++ "\n, " ++ show rest
290 | show NoClauses = "NONE"
292 | data ClauseType : PatClause (a :: todo) vars -> Type where
293 | ConClause : (0 isCon : IsConClause p) => ClauseType p
294 | VarClause : ClauseType p
296 | namesIn : List Name -> Pat -> Bool
297 | namesIn pvars (PAs _ n p) = (n `elem` pvars) && namesIn pvars p
298 | namesIn pvars (PCon _ _ _ _ ps) = all (namesIn pvars) ps
299 | namesIn pvars (PTyCon _ _ _ ps) = all (namesIn pvars) ps
300 | namesIn pvars (PArrow _ _ s t) = namesIn pvars s && namesIn pvars t
301 | namesIn pvars (PDelay _ _ t p) = namesIn pvars t && namesIn pvars p
302 | namesIn pvars (PLoc _ n) = n `elem` pvars
303 | namesIn pvars _ = True
305 | namesFrom : Pat -> List Name
306 | namesFrom (PAs _ n p) = n :: namesFrom p
307 | namesFrom (PCon _ _ _ _ ps) = concatMap namesFrom ps
308 | namesFrom (PTyCon _ _ _ ps) = concatMap namesFrom ps
309 | namesFrom (PArrow _ _ s t) = namesFrom s ++ namesFrom t
310 | namesFrom (PDelay _ _ t p) = namesFrom t ++ namesFrom p
311 | namesFrom (PLoc _ n) = [n]
314 | clauseType : Phase -> (p : PatClause (a :: as) vars) -> ClauseType p
320 | clauseType phase (MkPatClause pvars (MkInfo arg _ ty :: rest) pid rhs)
321 | = maybe VarClause (\isCon => ConClause @{isCon}) $
getClauseType phase arg ty
325 | splitCon : Nat -> List Pat -> Maybe (So True)
326 | splitCon arity xs = toMaybe (arity == length xs) Oh
329 | clauseType' : (p : Pat) -> Maybe (IsConPat p)
330 | clauseType' (PCon _ _ _ a xs) = splitCon a xs
331 | clauseType' (PTyCon _ _ a xs) = splitCon a xs
332 | clauseType' (PConst _ x) = Just Oh
333 | clauseType' (PArrow _ _ s t) = Just Oh
334 | clauseType' (PDelay {}) = Just Oh
335 | clauseType' _ = Nothing
337 | getClauseType : Phase -> (p : Pat) -> ArgType vars -> Maybe (IsConPat p)
338 | getClauseType (CompileTime cr) (PCon _ _ _ a xs) (Known r t)
339 | = if (isErased r && not (isErased cr) &&
340 | all (namesIn (pvars ++ concatMap namesFrom (getPatInfo rest))) xs)
343 | getClauseType phase (PAs _ _ p) t = getClauseType phase p t
344 | getClauseType (CompileTime cr) l (Known r t)
345 | = if isErased r && not (isErased cr)
348 | getClauseType phase l (Known r t)
352 | getClauseType phase l _ = clauseType' l
354 | partition : {a, as, vars : _} ->
355 | Phase -> (ps : List01 ne (PatClause (a :: as) vars)) -> Partitions ps
356 | partition phase [] = NoClauses
357 | partition phase (x :: xs) with (partition phase xs)
358 | partition phase (x :: .(cs ++ ps)) | (ConClauses cs rest)
359 | = case clauseType phase x of
360 | ConClause => ConClauses (x :: cs) rest
361 | VarClause => VarClauses [x] (ConClauses cs rest)
362 | partition phase (x :: .(vs ++ ps)) | (VarClauses vs rest)
363 | = case clauseType phase x of
364 | ConClause => ConClauses [x] (VarClauses vs rest)
365 | VarClause => VarClauses (x :: vs) rest
366 | partition phase [x] | NoClauses
367 | = case clauseType phase x of
368 | ConClause => ConClauses [x] NoClauses
369 | VarClause => VarClauses [x] NoClauses
371 | data ConType : Type where
372 | CName : Name -> (tag : Int) -> ConType
374 | CConst : Constant -> ConType
376 | data Group : List Name ->
378 | ConGroup : {newargs : _} ->
379 | Name -> (tag : Int) ->
380 | List01 True (PatClause (newargs ++ todo) (newargs ++ vars)) ->
382 | DelayGroup : {tyarg, valarg : _} ->
383 | List01 True (PatClause (tyarg :: valarg :: todo)
384 | (tyarg :: valarg :: vars)) ->
386 | ConstGroup : Constant -> List01 True (PatClause todo vars) ->
390 | {vars : _} -> {todo : _} -> Show (Group todo vars) where
391 | show (ConGroup c t cs) = "Con " ++ show c ++ ": " ++ show cs
392 | show (DelayGroup cs) = "Delay: " ++ show cs
393 | show (ConstGroup c cs) = "Const " ++ show c ++ ": " ++ show cs
395 | data GroupMatch : ConType -> List Pat -> Group todo vars -> Type where
396 | ConMatch : {tag : Int} -> LengthMatch ps newargs ->
397 | GroupMatch (CName n tag) ps
398 | (ConGroup {newargs} n tag (MkPatClause pvs pats pid rhs :: rest))
399 | DelayMatch : GroupMatch CDelay []
400 | (DelayGroup {tyarg} {valarg} (MkPatClause pvs pats pid rhs :: rest))
401 | ConstMatch : GroupMatch (CConst c) []
402 | (ConstGroup c (MkPatClause pvs pats pid rhs :: rest))
403 | NoMatch : GroupMatch ct ps g
405 | checkGroupMatch : (c : ConType) -> (ps : List Pat) -> (g : Group todo vars) ->
407 | checkGroupMatch (CName x tag) ps (ConGroup {newargs} x' tag' (MkPatClause pvs pats pid rhs :: rest))
408 | = case checkLengthMatch ps newargs of
410 | Just prf => case (nameEq x x', decEq tag tag') of
411 | (Just Refl, Yes Refl) => ConMatch prf
413 | checkGroupMatch (CName x tag) ps _ = NoMatch
414 | checkGroupMatch CDelay [] (DelayGroup (MkPatClause pvs pats pid rhs :: rest))
416 | checkGroupMatch (CConst c) [] (ConstGroup c' (MkPatClause pvs pats pid rhs :: rest))
417 | = case constantEq c c' of
419 | Just Refl => ConstMatch
420 | checkGroupMatch _ _ _ = NoMatch
422 | data PName : Type where
424 | nextName : {auto i : Ref PName Int} ->
425 | String -> Core Name
427 | = do x <- get PName
431 | nextNames : {vars : _} ->
432 | {auto i : Ref PName Int} ->
433 | {auto c : Ref Ctxt Defs} ->
434 | FC -> String -> List Pat -> Maybe (NF vars) ->
435 | Core (
args ** (SizeOf args, NamedPats args (args ++ vars)))
436 | nextNames fc root [] fty = pure (
[] ** (zero, []))
437 | nextNames fc root (p :: pats) fty
438 | = do defs <- get Ctxt
439 | empty <- clearDefs defs
441 | let env = mkEnv fc vars
442 | fa_tys <- the (Core (Maybe (NF vars), ArgType vars)) $
444 | Nothing => pure (Nothing, Unknown)
445 | Just (NBind pfc _ (Pi _ c _ fargc) fsc) =>
446 | do farg <- evalClosure defs fargc
449 | pure (Just !(fsc defs (toClosure defaultOpts env (Ref pfc Bound n))),
451 | _ => pure (Just !(fsc defs (toClosure defaultOpts env (Ref pfc Bound n))),
452 | Known c !(quote empty env farg))
454 | pure (Nothing, Stuck !(quote empty env t))
455 | (
args ** (l, ps))
<- nextNames fc root pats (fst fa_tys)
456 | let argTy = case snd fa_tys of
458 | Known rig t => Known rig (weakenNs (suc l) t)
459 | Stuck t => Stuck (weakenNs (suc l) t)
460 | pure (
n :: args ** (suc l, MkInfo p First argTy :: weaken ps))
463 | newPats : (pargs : List Pat) -> LengthMatch pargs ns ->
464 | NamedPats (ns ++ todo) vars ->
466 | newPats [] NilMatch rest = []
467 | newPats (newpat :: xs) (ConsMatch w) (pi :: rest)
468 | = { pat := newpat } pi :: newPats xs w rest
470 | updateNames : List (Name, Pat) -> List (Name, Name)
471 | updateNames = mapMaybe update
473 | update : (Name, Pat) -> Maybe (Name, Name)
474 | update (n, PLoc fc p) = Just (p, n)
477 | updatePatNames : List (Name, Name) -> NamedPats todo vars -> NamedPats todo vars
478 | updatePatNames _ [] = []
479 | updatePatNames ns (pi :: ps)
480 | = { pat $= update } pi :: updatePatNames ns ps
482 | update : Pat -> Pat
483 | update (PAs fc n p)
484 | = case lookup n ns of
485 | Nothing => PAs fc n (update p)
486 | Just n' => PAs fc n' (update p)
487 | update (PCon fc n i a ps) = PCon fc n i a (map update ps)
488 | update (PTyCon fc n a ps) = PTyCon fc n a (map update ps)
489 | update (PArrow fc x s t) = PArrow fc x (update s) (update t)
490 | update (PDelay fc r t p) = PDelay fc r (update t) (update p)
492 | = case lookup n ns of
493 | Nothing => PLoc fc n
494 | Just n' => PLoc fc n'
497 | groupCons : {a, vars, todo : _} ->
498 | {auto i : Ref PName Int} ->
499 | {auto ct : Ref Ctxt Defs} ->
502 | (cs : List01 True (PatClause (a :: todo) vars)) ->
503 | (0 isCons : All IsConClause cs) =>
504 | Core (List01 True (Group todo vars))
505 | groupCons fc fn pvars (x :: xs) {isCons = p :: ps}
506 | = foldlC (uncurry . gc) !(gc [] x p) $
pushIn xs ps
508 | addConG : {vars', todo' : _} ->
509 | Name -> (tag : Int) ->
510 | List Pat -> NamedPats todo' vars' ->
511 | Int -> (rhs : Term vars') ->
512 | (acc : List01 ne (Group todo' vars')) ->
513 | Core (List01 True (Group todo' vars'))
518 | addConG n tag pargs pats pid rhs []
519 | = do cty <- if n == UN (Basic "->")
520 | then pure $
NBind fc (MN "_" 0) (Pi fc top Explicit (MkNFClosure defaultOpts (mkEnv fc vars') (NType fc (MN "top" 0)))) $
521 | (\d, a => pure $
NBind fc (MN "_" 1) (Pi fc top Explicit (MkNFClosure defaultOpts (mkEnv fc vars') (NErased fc Placeholder)))
522 | (\d, a => pure $
NType fc (MN "top" 0)))
523 | else do defs <- get Ctxt
524 | Just t <- lookupTyExact n (gamma defs)
525 | | Nothing => pure (NErased fc Placeholder)
526 | nf defs (mkEnv fc vars') (embed t)
527 | (
patnames ** (l, newargs))
<- nextNames fc "e" pargs (Just cty)
530 | let pats' = updatePatNames (updateNames (zip patnames pargs))
532 | let clause = MkPatClause pvars (newargs ++ pats') pid (weakenNs l rhs)
533 | pure [ConGroup n tag [clause]]
534 | addConG n tag pargs pats pid rhs (g :: gs) with (checkGroupMatch (CName n tag) pargs g)
535 | addConG n tag pargs pats pid rhs
536 | (ConGroup n tag (MkPatClause pvars ps tid tm :: rest) :: gs) | ConMatch {newargs} lprf
537 | = do let newps = newPats pargs lprf ps
538 | let l = mkSizeOf newargs
539 | let pats' = updatePatNames (updateNames (zip newargs pargs))
541 | let newclause = MkPatClause pvars (newps ++ pats') pid (weakenNs l rhs)
544 | pure $
ConGroup n tag (MkPatClause pvars ps tid tm :: rest ++ [newclause]) :: gs
545 | addConG n tag pargs pats pid rhs (g :: gs) | NoMatch
546 | = (g ::) <$> addConG n tag pargs pats pid rhs gs
552 | addDelayG : {vars', todo' : _} ->
553 | Pat -> Pat -> NamedPats todo' vars' ->
554 | Int -> (rhs : Term vars') ->
555 | (acc : List01 ne (Group todo' vars')) ->
556 | Core (List01 True (Group todo' vars'))
557 | addDelayG pty parg pats pid rhs []
558 | = do let dty = NBind fc (MN "a" 0) (Pi fc erased Explicit (MkNFClosure defaultOpts (mkEnv fc vars') (NType fc (MN "top" 0)))) $
560 | do a' <- evalClosure d a
561 | pure (NBind fc (MN "x" 0) (Pi fc top Explicit a)
562 | (\dv, av => pure (NDelayed fc LUnknown a'))))
563 | (
[tyname, argname] ** (l, newargs))
<- nextNames fc "e" [pty, parg]
565 | | _ => throw (InternalError "Error compiling Delay pattern match")
566 | let pats' = updatePatNames (updateNames [(tyname, pty),
569 | let clause = MkPatClause pvars (newargs ++ pats') pid (weakenNs l rhs)
570 | pure [DelayGroup [clause]]
571 | addDelayG pty parg pats pid rhs (g :: gs) with (checkGroupMatch CDelay [] g)
572 | addDelayG pty parg pats pid rhs
573 | (DelayGroup (MkPatClause pvars ps tid tm :: rest) :: gs) | DelayMatch {tyarg} {valarg}
574 | = do let l = mkSizeOf [tyarg, valarg]
575 | let newps = newPats [pty, parg] (ConsMatch (ConsMatch NilMatch)) ps
576 | let pats' = updatePatNames (updateNames [(tyarg, pty),
579 | let newclause = MkPatClause pvars (newps ++ pats') pid (weakenNs l rhs)
580 | pure $
DelayGroup (MkPatClause pvars ps tid tm :: rest ++ [newclause]) :: gs
581 | addDelayG pty parg pats pid rhs (g :: gs) | NoMatch
582 | = (g ::) <$> addDelayG pty parg pats pid rhs gs
584 | addConstG : {vars', todo' : _} ->
585 | Constant -> NamedPats todo' vars' ->
586 | Int -> (rhs : Term vars') ->
587 | (acc : List01 ne (Group todo' vars')) ->
588 | Core (List01 True (Group todo' vars'))
589 | addConstG c pats pid rhs []
590 | = pure [ConstGroup c [MkPatClause pvars pats pid rhs]]
591 | addConstG c pats pid rhs (g :: gs) with (checkGroupMatch (CConst c) [] g)
592 | addConstG c pats pid rhs
593 | (ConstGroup c (MkPatClause pvars ps tid tm :: rest) :: gs) | ConstMatch
594 | = do let newclause = MkPatClause pvars pats pid rhs
595 | pure $
ConstGroup c (MkPatClause pvars ps tid tm :: rest ++ [newclause]) :: gs
596 | addConstG c pats pid rhs (g :: gs) | NoMatch
597 | = (g ::) <$> addConstG c pats pid rhs gs
599 | addGroup : {vars, todo, idx : _} ->
600 | (pat : Pat) -> (0 _ : IsConPat pat) =>
601 | (0 p : IsVar nm idx vars) ->
602 | NamedPats todo vars -> Int -> Term vars ->
603 | List01 ne (Group todo vars) ->
604 | Core (List01 True (Group todo vars))
607 | addGroup (PAs fc n p) pprf pats pid rhs acc
608 | = addGroup p pprf pats pid (substName n (Local fc (Just True) idx pprf) rhs) acc
609 | addGroup (PCon cfc n t a pargs) pprf pats pid rhs acc
610 | = if a == length pargs
611 | then addConG n t pargs pats pid rhs acc
612 | else throw (CaseCompile cfc fn (NotFullyApplied n))
613 | addGroup (PTyCon cfc n a pargs) pprf pats pid rhs acc
614 | = if a == length pargs
615 | then addConG n 0 pargs pats pid rhs acc
616 | else throw (CaseCompile cfc fn (NotFullyApplied n))
617 | addGroup (PArrow _ _ s t) pprf pats pid rhs acc
618 | = addConG (UN $
Basic "->") 0 [s, t] pats pid rhs acc
621 | addGroup (PDelay _ _ pty parg) pprf pats pid rhs acc
622 | = addDelayG pty parg pats pid rhs acc
623 | addGroup (PConst _ c) pprf pats pid rhs acc
624 | = addConstG c pats pid rhs acc
626 | gc : {a, vars, todo : _} ->
627 | List01 ne (Group todo vars) ->
628 | (p : PatClause (a :: todo) vars) ->
629 | (0 _ : IsConClause p) ->
630 | Core (List01 True (Group todo vars))
631 | gc acc (MkPatClause _ (MkInfo pat pprf _ :: pats) pid rhs) isCon
632 | = addGroup pat pprf pats pid rhs acc
634 | getFirstPat : NamedPats (p :: ps) ns -> Pat
635 | getFirstPat (p :: _) = pat p
637 | getFirstArgType : NamedPats (p :: ps) ns -> ArgType ns
638 | getFirstArgType (p :: _) = argType p
642 | data ScoredPats : List Name -> Scoped where
643 | Scored : List01 True (NamedPats (p :: ps) ns) -> Vect (length (p :: ps)) Int -> ScoredPats (p :: ps) ns
645 | {ps : _} -> Show (ScoredPats ps ns) where
646 | show (Scored xs ys) = (show ps) ++ "//" ++ (show ys)
648 | zeroedScore : {ps : _} -> List01 True (NamedPats (p :: ps) ns) -> ScoredPats (p :: ps) ns
649 | zeroedScore nps = Scored nps (replicate (S $
length ps) 0)
653 | highScore : {prev : List Name} ->
655 | (scores : Vect (length names) Int) ->
657 | (highIdx : (
n ** NVar n (prev ++ names))
) ->
659 | Maybe (
n ** NVar n (prev ++ names))
660 | highScore [] [] high idx True = Nothing
661 | highScore [] [] high idx False = Just idx
662 | highScore (x :: xs) (y :: ys) high idx duped =
663 | let next = highScore {prev = prev `snoc` x} xs ys
664 | prf = appendAssociative prev [x] xs
666 | case compare y high of
667 | LT => next high (rewrite sym $
prf in idx) duped
668 | EQ => next high (rewrite sym $
prf in idx) True
669 | GT => next y (
x ** rewrite sym $
prf in weakenNVar (mkSizeOf prev) (MkNVar First))
False
676 | highScoreIdx : {p : _} -> {ps : _} -> ScoredPats (p :: ps) ns -> Maybe (
n ** NVar n (p :: ps))
677 | highScoreIdx (Scored xs (y :: ys)) = highScore {prev = []} (p :: ps) (y :: ys) (y - 1) (
p ** MkNVar First)
False
681 | headConsPenalty : (penality : Nat -> Int) -> Pat -> Int
682 | headConsPenalty p (PAs _ _ w) = headConsPenalty p w
683 | headConsPenalty p (PCon _ n _ arity pats) = p arity
684 | headConsPenalty p (PTyCon _ _ arity _) = p arity
685 | headConsPenalty _ (PConst {}) = 0
686 | headConsPenalty _ (PArrow {}) = 0
687 | headConsPenalty p (PDelay _ _ _ w) = headConsPenalty p w
688 | headConsPenalty _ (PLoc {}) = 0
689 | headConsPenalty _ (PUnmatchable {}) = 0
691 | splitColumn : (nps : List01 True (NamedPats (p :: ps) ns)) -> (Vect (length nps) (PatInfo p ns), List01 True (NamedPats ps ns))
692 | splitColumn [(w :: ws)] = ([w], [ws])
693 | splitColumn ((w :: ws) :: nps@(_ :: _)) = bimap (w ::) (ws ::) $
splitColumn nps
697 | consScoreHeuristic : {ps : _} -> (scorePat : Pat -> Int) -> ScoredPats ps ns -> ScoredPats ps ns
698 | consScoreHeuristic scorePat (Scored xs ys) =
699 | let columnScores = scoreColumns xs
700 | ys' = zipWith (+) ys columnScores
703 | scoreColumns : {ps' : _} -> (nps : List01 True (NamedPats ps' ns)) -> Vect (length ps') Int
704 | scoreColumns {ps' = []} nps = []
705 | scoreColumns {ps' = w :: ws} nps =
706 | let (col, nps') = splitColumn nps
707 | in sum (scorePat . pat <$> col) :: scoreColumns nps'
711 | heuristicF : {ps : _} -> ScoredPats (p :: ps) ns -> ScoredPats (p :: ps) ns
712 | heuristicF (Scored (x :: xs) ys) =
713 | let columnScores = scores x
714 | ys' = zipWith (+) ys columnScores
715 | in Scored (x :: xs) ys'
717 | isBlank : Pat -> Bool
718 | isBlank (PLoc {}) = True
721 | scores : NamedPats ps' ns' -> Vect (length ps') Int
723 | scores (y :: ys) = let score : Int = if isBlank (pat y) then 0 else 1
724 | in score :: scores ys
728 | heuristicB : {ps : _} -> ScoredPats ps ns -> ScoredPats ps ns
729 | heuristicB = consScoreHeuristic (headConsPenalty (\arity => if arity == 0 then 0 else -
1))
732 | heuristicA : {ps : _} -> ScoredPats ps ns -> ScoredPats ps ns
733 | heuristicA = consScoreHeuristic (headConsPenalty (negate . cast))
735 | applyHeuristics : {p : _} ->
737 | ScoredPats (p :: ps) ns ->
738 | List (ScoredPats (p :: ps) ns -> ScoredPats (p :: ps) ns) ->
739 | Maybe (
n ** NVar n (p :: ps))
740 | applyHeuristics x [] = highScoreIdx x
741 | applyHeuristics x (f :: fs) = highScoreIdx x <|> applyHeuristics (f x) fs
748 | nextIdxByScore : {p : _} ->
750 | (useHeuristics : Bool) ->
752 | List01 True (NamedPats (p :: ps) ns) ->
753 | (
n ** NVar n (p :: ps))
754 | nextIdxByScore False _ _ = (
_ ** (MkNVar First))
755 | nextIdxByScore _ (CompileTime _) _ = (
_ ** (MkNVar First))
756 | nextIdxByScore True RunTime xs =
757 | fromMaybe (
_ ** (MkNVar First)) $
758 | applyHeuristics (zeroedScore xs) [heuristicF, heuristicB, heuristicA]
763 | sameType : {ns : _} ->
764 | {auto c : Ref Ctxt Defs} ->
765 | FC -> Phase -> Name ->
766 | Env Term ns -> List01 ne (NamedPats (p :: ps) ns) ->
768 | sameType fc phase fn env [] = pure ()
769 | sameType {ns} fc phase fn env (p :: xs)
770 | = do defs <- get Ctxt
771 | case getFirstArgType p of
772 | Known _ t => sameTypeAs phase
774 | (map getFirstArgType xs)
775 | ty => throw (CaseCompile fc fn DifferingTypes)
777 | firstPat : NamedPats (np :: nps) ns -> Pat
778 | firstPat (pinf :: _) = pat pinf
780 | headEq : NF ns -> NF ns -> Phase -> Bool
781 | headEq (NBind _ _ (Pi {}) _) (NBind _ _ (Pi {}) _) _ = True
782 | headEq (NTCon _ n _ _) (NTCon _ n' _ _) _ = n == n'
783 | headEq (NPrimVal _ c) (NPrimVal _ c') _ = c == c'
784 | headEq (NType {}) (NType {}) _ = True
785 | headEq (NApp _ (NRef _ n) _) (NApp _ (NRef _ n') _) RunTime = n == n'
786 | headEq (NErased _ (Dotted x)) y ph = headEq x y ph
787 | headEq x (NErased _ (Dotted y)) ph = headEq x y ph
788 | headEq (NErased {}) _ RunTime = True
789 | headEq _ (NErased {}) RunTime = True
790 | headEq _ _ _ = False
792 | sameTypeAs : forall ne. Phase -> NF ns -> List01 ne (ArgType ns) -> Core ()
793 | sameTypeAs _ ty [] = pure ()
794 | sameTypeAs ph ty (Known r t :: xs) =
795 | do defs <- get Ctxt
796 | if headEq ty !(nf defs env t) phase
797 | then sameTypeAs ph ty xs
798 | else throw (CaseCompile fc fn DifferingTypes)
799 | sameTypeAs p ty _ = throw (CaseCompile fc fn DifferingTypes)
803 | samePat : List01 True (NamedPats (p :: ps) ns) -> Bool
805 | = samePatAs (dropAs (getFirstPat pi))
806 | (map (dropAs . getFirstPat) xs)
808 | dropAs : Pat -> Pat
809 | dropAs (PAs _ _ p) = p
812 | samePatAs : Pat -> List01 ne Pat -> Bool
813 | samePatAs p [] = True
814 | samePatAs (PTyCon fc n a args) (PTyCon _ n' _ _ :: ps)
815 | = n == n' && samePatAs (PTyCon fc n a args) ps
816 | samePatAs (PCon fc n t a args) (PCon _ n' t' _ _ :: ps)
817 | = n == n' && t == t' && samePatAs (PCon fc n t a args) ps
818 | samePatAs (PConst fc c) (PConst _ c' :: ps)
819 | = c == c' && samePatAs (PConst fc c) ps
820 | samePatAs (PArrow fc x s t) (PArrow _ _ s' t' :: ps)
821 | = samePatAs (PArrow fc x s t) ps
822 | samePatAs (PDelay fc r t p) (PDelay _ _ _ _ :: ps)
823 | = samePatAs (PDelay fc r t p) ps
824 | samePatAs (PLoc fc n) (PLoc _ _ :: ps) = samePatAs (PLoc fc n) ps
825 | samePatAs x y = False
827 | getScore : {ns : _} ->
828 | {auto c : Ref Ctxt Defs} ->
829 | FC -> Phase -> Name ->
830 | List01 True (NamedPats (p :: ps) ns) ->
831 | Core (Either CaseError ())
832 | getScore fc phase name npss
833 | = catch (Right () <$ sameType fc phase name (mkEnv fc ns) npss)
835 | CaseCompile _ _ err => pure $
Left err
840 | pickNextViable : {p, ns, ps : _} ->
841 | {auto c : Ref Ctxt Defs} ->
842 | FC -> Phase -> Name -> List01 True (NamedPats (p :: ps) ns) ->
843 | Core (
n ** NVar n (p :: ps))
845 | pickNextViable {ps = []} fc phase fn npss
847 | then pure (
_ ** MkNVar First)
848 | else do Right () <- getScore fc phase fn npss
849 | | Left err => throw (CaseCompile fc fn err)
850 | pure (
_ ** MkNVar First)
851 | pickNextViable {ps = q :: qs} fc phase fn npss
853 | then pure (
_ ** MkNVar First)
854 | else case !(getScore fc phase fn npss) of
855 | Right () => pure (
_ ** MkNVar First)
856 | _ => do (
_ ** MkNVar var)
<- pickNextViable fc phase fn (map tail npss)
857 | pure (
_ ** MkNVar (Later var))
859 | moveFirst : {idx : Nat} -> (0 el : IsVar nm idx ps) -> NamedPats ps ns ->
860 | NamedPats (nm :: dropIsVar ps el) ns
861 | moveFirst el nps = getPat el nps :: dropPat el nps
863 | shuffleVars : {idx : Nat} -> (0 el : IsVar nm idx todo) -> PatClause todo vars ->
864 | PatClause (nm :: dropIsVar todo el) vars
865 | shuffleVars First orig@(MkPatClause pvars lhs pid rhs) = orig
866 | shuffleVars el (MkPatClause pvars lhs pid rhs)
867 | = MkPatClause pvars (moveFirst el lhs) pid rhs
876 | match : {vars, todo : _} ->
877 | {auto i : Ref PName Int} ->
878 | {auto c : Ref Ctxt Defs} ->
879 | FC -> Name -> Phase ->
880 | List01 True (PatClause todo vars) ->
881 | IMaybe ne (CaseTree vars) ->
882 | Core (CaseTree vars)
886 | match {todo = _ :: _} fc fn phase clauses err
887 | = do let nps = getNPs <$> clauses
888 | let (
_ ** (MkNVar next))
= nextIdxByScore (caseTreeHeuristics !getSession) phase nps
889 | let prioritizedClauses = shuffleVars next <$> clauses
890 | (
n ** MkNVar next')
<- pickNextViable fc phase fn (getNPs <$> prioritizedClauses)
891 | log "compile.casetree.pick" 25 $
"Picked " ++ show n ++ " as the next split"
892 | let clauses' = shuffleVars next' <$> prioritizedClauses
893 | log "compile.casetree.clauses" 25 $
894 | unlines ("Using clauses:" :: map ((" " ++) . show) (forget clauses'))
895 | let ps = partition phase clauses'
896 | log "compile.casetree.partition" 25 $
"Got Partition:\n" ++ show ps
897 | Just mix <- mixture fc fn phase ps err
898 | log "compile.casetree.intermediate" 25 $
"match: new case tree " ++ show mix
900 | match {todo = []} fc fn phase (MkPatClause pvars [] pid (Erased _ Impossible) :: _) err
902 | match {todo = []} fc fn phase (MkPatClause pvars [] pid rhs :: _) err
903 | = pure $
STerm pid rhs
905 | caseGroups : {pvar, vars, todo : _} ->
906 | {auto i : Ref PName Int} ->
907 | {auto c : Ref Ctxt Defs} ->
908 | FC -> Name -> Phase ->
909 | {idx : Nat} -> (0 p : IsVar pvar idx vars) -> Term vars ->
910 | List01 True (Group todo vars) -> IMaybe ne (CaseTree vars) ->
911 | Core (CaseTree vars)
912 | caseGroups fc fn phase el ty gs errorCase
913 | = Case idx el (resolveNames vars ty) <$> altGroups gs
915 | altGroups : forall ne. List01 ne (Group todo vars) -> Core (List (CaseAlt vars))
916 | altGroups [] = pure $
toList $
DefaultCase <$> errorCase
917 | altGroups (ConGroup {newargs} cn tag rest :: cs)
918 | = do crest <- match fc fn phase rest (map (weakenNs (mkSizeOf newargs)) errorCase)
919 | cs' <- altGroups cs
920 | pure (ConCase cn tag newargs crest :: cs')
921 | altGroups (DelayGroup {tyarg} {valarg} rest :: cs)
922 | = do crest <- match fc fn phase rest (map (weakenNs (mkSizeOf [tyarg, valarg])) errorCase)
923 | cs' <- altGroups cs
924 | pure (DelayCase tyarg valarg crest :: cs')
925 | altGroups (ConstGroup c rest :: cs)
926 | = do crest <- match fc fn phase rest errorCase
927 | cs' <- altGroups cs
928 | pure (ConstCase c crest :: cs')
930 | conRule : {a, vars, todo : _} ->
931 | {auto i : Ref PName Int} ->
932 | {auto c : Ref Ctxt Defs} ->
933 | FC -> Name -> Phase ->
934 | (cs : List01 True (PatClause (a :: todo) vars)) ->
935 | (0 isCons : All IsConClause cs) =>
936 | IMaybe ne (CaseTree vars) ->
937 | Core (CaseTree vars)
942 | conRule {a} fc fn phase cs@(MkPatClause pvars (MkInfo pat pprf fty :: pats) pid rhs :: rest) err
943 | = do Element refinedcs _ <- pullOut <$> traverseList01 (substInClause fc) (pushIn cs isCons)
944 | groups <- groupCons fc fn pvars refinedcs
946 | Known _ t => pure t
947 | _ => throw (CaseCompile fc fn UnknownType)
948 | caseGroups fc fn phase pprf ty groups err
950 | varRule : {a, vars, todo : _} ->
951 | {auto i : Ref PName Int} ->
952 | {auto c : Ref Ctxt Defs} ->
953 | FC -> Name -> Phase ->
954 | List01 True (PatClause (a :: todo) vars) ->
955 | IMaybe ne (CaseTree vars) ->
956 | Core (CaseTree vars)
957 | varRule fc fn phase cs err
958 | = do alts' <- traverseList01 updateVar cs
959 | match fc fn phase alts' err
961 | updateVar : PatClause (a :: todo) vars -> Core (PatClause todo vars)
963 | updateVar (MkPatClause pvars (MkInfo (PLoc pfc n) prf fty :: pats) pid rhs)
964 | = pure $
MkPatClause (n :: pvars)
965 | !(substInPats fc a (Local pfc (Just False) _ prf) pats)
966 | pid (substName n (Local pfc (Just False) _ prf) rhs)
969 | updateVar (MkPatClause pvars (MkInfo (PAs pfc n pat) prf fty :: pats) pid rhs)
970 | = do pats' <- substInPats fc a (mkTerm _ pat) pats
971 | let rhs' = substName n (Local pfc (Just True) _ prf) rhs
972 | updateVar (MkPatClause pvars (MkInfo pat prf fty :: pats') pid rhs')
975 | updateVar (MkPatClause pvars (MkInfo pat prf fty :: pats) pid rhs)
976 | = pure $
MkPatClause pvars
977 | !(substInPats fc a (mkTerm vars pat) pats) pid rhs
979 | mixture : {a, vars, todo : _} ->
980 | {auto i : Ref PName Int} ->
981 | {auto c : Ref Ctxt Defs} ->
982 | {ps : List01 ne (PatClause (a :: todo) vars)} ->
983 | FC -> Name -> Phase ->
985 | IMaybe neErr (CaseTree vars) ->
986 | Core (IMaybe (ne || neErr) (CaseTree vars))
987 | mixture fc fn phase (ConClauses cs rest) err
988 | = do fallthrough <- mixture fc fn phase rest err
989 | Just <$> conRule fc fn phase cs fallthrough
990 | mixture fc fn phase (VarClauses vs rest) err
991 | = do fallthrough <- mixture fc fn phase rest err
992 | Just <$> varRule fc fn phase vs fallthrough
993 | mixture fc fn phase NoClauses err
997 | mkPat : {auto c : Ref Ctxt Defs} ->
998 | (matchable : Bool) -> List Pat -> ClosedTerm -> ClosedTerm -> Core Pat
999 | mkPat _ [] orig (Ref fc Bound n) = pure $
PLoc fc n
1000 | mkPat True args orig (Ref fc (DataCon t a) n) = pure $
PCon fc n t a args
1001 | mkPat True args orig (Ref fc (TyCon a) n) = pure $
PTyCon fc n a args
1002 | mkPat True args orig (Ref fc Func n)
1003 | = do prims <- getPrimitiveNames
1004 | mtm <- normalisePrims (const True) isPConst True prims n args orig Env.empty
1006 | Just tm => if tm /= orig
1009 | then mkPat True [] tm tm
1011 | pure $
PUnmatchable (getLoc orig) orig
1013 | do log "compile.casetree" 10 $
1014 | "Unmatchable function: " ++ show n
1015 | pure $
PUnmatchable (getLoc orig) orig
1016 | mkPat True args orig (Bind fc x (Pi _ _ _ s) t)
1018 | = case subst (Erased fc Placeholder) t of
1019 | App _ t'@(Ref fc Bound n) (Erased {}) => pure $
PArrow fc x !(mkPat True [] s s) !(mkPat False [] t' t')
1020 | t' => pure $
PArrow fc x !(mkPat True [] s s) !(mkPat False [] t' t')
1021 | mkPat True args orig (App fc fn arg)
1022 | = do parg <- mkPat True [] arg arg
1023 | mkPat True (parg :: args) orig fn
1024 | mkPat True args orig (As fc _ (Ref _ Bound n) ptm)
1025 | = pure $
PAs fc n !(mkPat True [] ptm ptm)
1026 | mkPat True args orig (As fc _ _ ptm)
1027 | = mkPat True [] orig ptm
1028 | mkPat True args orig (TDelay fc r ty p)
1029 | = pure $
PDelay fc r !(mkPat True [] orig ty) !(mkPat True [] orig p)
1030 | mkPat True args orig (PrimVal fc $
PrT c)
1031 | = pure $
PTyCon fc (UN (Basic $
show c)) 0 []
1032 | mkPat True args orig (PrimVal fc c) = pure $
PConst fc c
1033 | mkPat True args orig (TType fc _) = pure $
PTyCon fc (UN $
Basic "Type") 0 []
1035 | = do log "compile.casetree" 10 $
1036 | "Catchall: marking " ++ show tm ++ " as unmatchable"
1037 | pure $
PUnmatchable (getLoc orig) orig
1040 | argToPat : {auto c : Ref Ctxt Defs} -> ClosedTerm -> Core Pat
1041 | argToPat tm = mkPat True [] tm tm
1043 | mkPatClause : {auto c : Ref Ctxt Defs} ->
1045 | (args : Scope) -> ClosedTerm ->
1046 | Int -> (List Pat, ClosedTerm) ->
1047 | Core (PatClause args args)
1048 | mkPatClause fc fn args ty pid (ps, rhs)
1049 | = maybe (throw (CaseCompile fc fn DifferingArgNumbers))
1052 | nty <- nf defs Env.empty ty
1053 | ns <- mkNames args ps eq (Just nty)
1054 | log "compile.casetree" 20 $
1055 | "Make pat clause for names " ++ show ns
1056 | ++ " in LHS " ++ show ps
1057 | pure (MkPatClause [] ns pid
1058 | (rewrite sym (appendNilRightNeutral args) in
1059 | (weakenNs (mkSizeOf args) rhs))))
1060 | (checkLengthMatch args ps)
1062 | mkNames : (vars : Scope) -> (ps : List Pat) ->
1063 | LengthMatch vars ps -> Maybe (NF []) ->
1064 | Core (NamedPats vars vars)
1065 | mkNames [] [] NilMatch fty = pure []
1066 | mkNames (arg :: args) (p :: ps) (ConsMatch eq) fty
1068 | empty <- clearDefs defs
1069 | fa_tys <- the (Core (Maybe _, ArgType _)) $
1071 | Nothing => pure (Nothing, CaseBuilder.Unknown)
1072 | Just (NBind pfc _ (Pi _ c _ farg) fsc) =>
1073 | pure (Just !(fsc defs (toClosure defaultOpts [] (Ref pfc Bound arg))),
1074 | Known c (embed !(quote empty [] farg)))
1076 | pure (Nothing, Stuck (embed !(quote empty [] t)))
1077 | pure (MkInfo p First (Builtin.snd fa_tys)
1078 | :: weaken !(mkNames args ps eq (Builtin.fst fa_tys)))
1081 | patCompile : {auto c : Ref Ctxt Defs} ->
1083 | ClosedTerm -> List01 True (List Pat, ClosedTerm) ->
1084 | Core (
args ** CaseTree args)
1085 | patCompile fc fn phase ty (p :: ps)
1086 | = do let (
ns ** n)
= getNames 0 (fst p)
1087 | pats <- mkPatClausesFrom 0 ns (p :: ps)
1089 | logC "compile.casetree" 5 $
do
1090 | pats <- traverse toFullNames $
forget pats
1091 | pure $
"Pattern clauses:\n"
1092 | ++ show (indent 2 $
vcat $
pretty <$> pats)
1094 | log "compile.casetree" 10 $
show pats
1095 | i <- newRef PName (the Int 0)
1096 | cases <- match fc fn phase pats Nothing
1099 | mkPatClausesFrom : Int -> (args : Scope) ->
1100 | List01 ne (List Pat, ClosedTerm) ->
1101 | Core (List01 ne (PatClause args args))
1102 | mkPatClausesFrom i ns [] = pure []
1103 | mkPatClausesFrom i ns (p :: ps)
1104 | = do p' <- mkPatClause fc fn ns ty i p
1105 | ps' <- mkPatClausesFrom (i + 1) ns ps
1108 | getNames : Int -> List Pat -> (ns : Scope ** SizeOf ns)
1109 | getNames i [] = (
[] ** zero)
1111 | let (
ns ** n)
= getNames (i + 1) xs
1112 | in (
MN "arg" i :: ns ** suc n)
1114 | toPatClause : {auto c : Ref Ctxt Defs} ->
1115 | FC -> Name -> (ClosedTerm, ClosedTerm) ->
1116 | Core (List Pat, ClosedTerm)
1117 | toPatClause fc n (lhs, rhs)
1118 | = case getFnArgs lhs of
1119 | (Ref ffc Func fn, args)
1121 | (np, _) <- getPosition n (gamma defs)
1122 | (fnp, _) <- getPosition fn (gamma defs)
1124 | then pure (!(traverse argToPat args), rhs)
1125 | else throw (GenericMsg ffc ("Wrong function name in pattern LHS " ++ show (n, fn)))
1126 | (f, args) => throw (GenericMsg fc "Not a function name in pattern LHS")
1132 | simpleCase : {auto c : Ref Ctxt Defs} ->
1133 | FC -> Phase -> Name -> ClosedTerm ->
1134 | (clauses : List01 True (ClosedTerm, ClosedTerm)) ->
1135 | Core (
args ** CaseTree args)
1136 | simpleCase fc phase fn ty clauses
1137 | = do logC "compile.casetree" 5 $
1138 | do cs <- traverse (\ (c,d) => [| MkPair (toFullNames c) (toFullNames d) |]) (forget clauses)
1139 | pure $
"simpleCase: Clauses:\n" ++ show (
1140 | indent 2 $
vcat $
flip map cs $
\ lrhs =>
1141 | byShow (fst lrhs) <++> pretty "=" <++> byShow (snd lrhs))
1142 | ps <- traverseList01 (toPatClause fc fn) clauses
1144 | patCompile fc fn phase ty ps
1147 | findReachedAlts : CaseAlt ns' -> List Int
1148 | findReachedAlts (ConCase _ _ _ t) = findReached t
1149 | findReachedAlts (DelayCase _ _ t) = findReached t
1150 | findReachedAlts (ConstCase _ t) = findReached t
1151 | findReachedAlts (DefaultCase t) = findReached t
1153 | findReached : CaseTree ns -> List Int
1154 | findReached (Case _ _ _ alts) = concatMap findReachedAlts alts
1155 | findReached (STerm i _) = [i]
1163 | identifyUnreachableDefaults : {auto c : Ref Ctxt Defs} ->
1165 | FC -> Defs -> NF vars -> List (CaseAlt vars) ->
1169 | identifyUnreachableDefaults fc defs (NPrimVal {}) cs = pure empty
1170 | identifyUnreachableDefaults fc defs (NType {}) cs = pure empty
1171 | identifyUnreachableDefaults fc defs nfty cs
1172 | = do cs' <- traverse rep cs
1173 | let (cs'', extraClauseIdxs) = dropRep (concat cs') empty
1175 | if (length cs == (length cs'' + 1))
1180 | when (not $
null extraClauseIdxs') $
1181 | log "compile.casetree.clauses" 25 $
1182 | "Marking the following clause indices as unreachable under the current branch of the tree: " ++ (show extraClauseIdxs')
1185 | rep : CaseAlt vars -> Core (List (CaseAlt vars))
1187 | = do allCons <- getCons defs nfty
1188 | pure (map (mkAlt fc sc) allCons)
1191 | dropRep : List (CaseAlt vars) -> SortedSet Int -> (List (CaseAlt vars), SortedSet Int)
1192 | dropRep [] extra = ([], extra)
1193 | dropRep (c@(ConCase n t args sc) :: rest) extra
1196 | = let (filteredClauses, extraCases) = partition (not . tagIs t) rest
1197 | extraClauses = extraCases >>= findReachedAlts
1198 | (rest', extra') = dropRep filteredClauses $
fromList extraClauses
1199 | in (c :: rest', extra `union` extra')
1200 | dropRep (c :: rest) extra
1201 | = let (rest', extra') = dropRep rest extra
1202 | in (c :: rest', extra')
1211 | findExtraDefaults : {auto c : Ref Ctxt Defs} ->
1213 | FC -> Defs -> CaseTree vars ->
1215 | findExtraDefaults fc defs (Case idx el ty altsIn)
1216 | = do let fenv = mkEnv fc vars
1217 | nfty <- nf defs fenv ty
1218 | extraCases <- identifyUnreachableDefaults fc defs nfty altsIn
1219 | extraCases' <- concat <$> traverse findExtraAlts altsIn
1220 | pure (Prelude.toList extraCases ++ extraCases')
1222 | findExtraAlts : CaseAlt vars -> Core (List Int)
1223 | findExtraAlts (ConCase x tag args ctree) = findExtraDefaults fc defs ctree
1224 | findExtraAlts (DelayCase x arg ctree) = findExtraDefaults fc defs ctree
1225 | findExtraAlts (ConstCase x ctree) = findExtraDefaults fc defs ctree
1227 | findExtraAlts (DefaultCase ctree) = pure []
1229 | findExtraDefaults fc defs ctree = pure []
1233 | getPMDef : {auto c : Ref Ctxt Defs} ->
1234 | FC -> Phase -> Name -> ClosedTerm -> List Clause ->
1235 | Core (
args ** (CaseTree args, List Clause))
1239 | getPMDef fc phase fn ty []
1240 | = do log "compile.casetree.getpmdef" 20 "getPMDef: No clauses!"
1242 | pure (
!(getArgs 0 !(nf defs Env.empty ty)) ** (Unmatched "No clauses in \{show fn}", []))
1244 | getArgs : Int -> ClosedNF -> Core (List Name)
1245 | getArgs i (NBind fc x (Pi {}) sc)
1247 | sc' <- sc defs (toClosure defaultOpts Env.empty (Erased fc Placeholder))
1248 | pure (MN "arg" i :: !(getArgs i sc'))
1250 | getPMDef fc phase fn ty clauses@(_ :: _)
1252 | let cs = map (toClosed defs) (labelPat 0 $
fromList clauses)
1253 | (
_ ** t)
<- simpleCase fc phase fn ty cs
1254 | logC "compile.casetree.getpmdef" 20 $
1255 | pure $
"Compiled to: " ++ show !(toFullNames t)
1256 | let reached = findReached t
1257 | log "compile.casetree.clauses" 25 $
1258 | "Reached clauses: " ++ (show reached)
1259 | extraDefaults <- findExtraDefaults fc defs t
1260 | let unreachable = getUnreachable 0 (reached \\ extraDefaults) clauses
1261 | pure (
_ ** (t, unreachable))
1263 | getUnreachable : Int -> List Int -> List Clause -> List Clause
1264 | getUnreachable i is [] = []
1265 | getUnreachable i is (c :: cs)
1267 | then getUnreachable (i + 1) is cs
1268 | else c :: getUnreachable (i + 1) is cs
1270 | labelPat : Int -> List01 ne a -> List01 ne (String, a)
1272 | labelPat i (x :: xs) = ("pat" ++ show i ++ ":", x) :: labelPat (i + 1) xs
1274 | toClosed : Defs -> (String, Clause) -> (ClosedTerm, ClosedTerm)
1275 | toClosed defs (pname, MkClause env lhs rhs)
1276 | = (close fc pname env lhs, close fc pname env rhs)