0 | module Core.Termination.CallGraph
2 | import Core.Case.CaseTree
3 | import Core.Context.Log
5 | import Core.Normalise
9 | import Libraries.Data.List.SizeOf
10 | import Libraries.Data.SparseMatrix
16 | data Guardedness = Toplevel | Unguarded | Guarded | InDelay
18 | Show Guardedness where
19 | show Toplevel = "Toplevel"
20 | show Unguarded = "Unguarded"
21 | show Guarded = "Guarded"
22 | show InDelay = "InDelay"
24 | sizeEq : {auto 0 cv : CompatibleVars rhsVars lhsVars} ->
28 | sizeEq (Local _ _ idx _) (Local _ _ idx' _) = idx == idx'
29 | sizeEq (Ref _ _ n) (Ref _ _ n') = n == n'
30 | sizeEq (Meta _ _ i args) (Meta _ _ i' args')
31 | = i == i' && assert_total (all (uncurry sizeEq) (zip args args'))
32 | sizeEq (Bind _ _ b sc) (Bind _ _ b' sc') = eqBinderBy sizeEq b b' && sizeEq sc sc'
33 | sizeEq (App _ f a) (App _ f' a') = sizeEq f f' && sizeEq a a'
34 | sizeEq (As _ _ a p) p' = sizeEq p p'
35 | sizeEq p (As _ _ a p') = sizeEq p a || sizeEq p p'
36 | sizeEq (TDelayed _ _ t) (TDelayed _ _ t') = sizeEq t t'
37 | sizeEq (TDelay _ _ t x) (TDelay _ _ t' x') = sizeEq t t' && sizeEq x x'
38 | sizeEq (TForce _ _ t) (TForce _ _ t') = sizeEq t t'
39 | sizeEq (PrimVal _ c) (PrimVal _ c') = c == c'
41 | sizeEq t (Erased _ (Dotted t')) = eqTerm t t'
42 | sizeEq (TType {}) (TType {}) = True
47 | delazy : Defs -> Term vars -> Term vars
48 | delazy defs (TDelayed fc r tm)
49 | = let tm' = delazy defs tm in
51 | LInf => TDelayed fc r tm'
53 | delazy defs (TDelay fc r ty tm)
54 | = let ty' = delazy defs ty
55 | tm' = delazy defs tm in
57 | LInf => TDelay fc r ty' tm'
59 | delazy defs (TForce fc r t)
61 | LInf => TForce fc r (delazy defs t)
63 | delazy defs (Meta fc n i args) = Meta fc n i (map (delazy defs) args)
64 | delazy defs (Bind fc x b sc)
65 | = Bind fc x (map (delazy defs) b) (delazy defs sc)
66 | delazy defs (App fc f a) = App fc (delazy defs f) (delazy defs a)
67 | delazy defs (As fc s a p) = As fc s (delazy defs a) (delazy defs p)
71 | findSC : {vars : _} ->
72 | {auto c : Ref Ctxt Defs} ->
73 | Defs -> Env Term vars -> Guardedness ->
77 | findSC {vars} defs env g pats (Bind fc n b sc)
78 | = [| findSCbinder b ++ findSC defs (b :: env) g (map weaken pats) sc |]
80 | findSCPiInfo : PiInfo (Term vars) -> Core (List SCCall)
81 | findSCPiInfo (DefImplicit def) = findSC defs env g pats def
82 | findSCPiInfo _ = pure []
84 | findSCbinder : Binder (Term vars) -> Core (List SCCall)
85 | findSCbinder (Let _ _ val ty) = [| findSC defs env g pats val ++ findSC defs env g pats ty |]
86 | findSCbinder (Pi _ _ p ty) = [| findSCPiInfo p ++ findSC defs env g pats ty |]
87 | findSCbinder (Lam _ _ p ty) = [| findSCPiInfo p ++ findSC defs env g pats ty |]
88 | findSCbinder b = pure []
90 | findSC defs env Guarded pats (TDelay _ _ _ tm)
91 | = findSC defs env InDelay pats tm
92 | findSC defs env g pats (TDelay _ _ _ tm)
93 | = findSC defs env g pats tm
94 | findSC defs env g pats (TForce _ _ tm)
95 | = findSC defs env Unguarded pats tm
96 | findSC defs env g pats tm
97 | = do let (fn, args) = getFnArgs tm
98 | False <- isAssertTotal fn
101 | Nothing <- handleCase fn args
102 | | Just res => pure res
103 | fn' <- conIfGuarded fn
105 | case (g, fn', args) of
108 | (InDelay, Ref fc (DataCon {}) cn, args) =>
109 | do scs <- traverse (findSC defs env InDelay pats) args
113 | (InDelay, _, args) =>
114 | do scs <- traverse (findSC defs env Unguarded pats) args
116 | (Guarded, Ref fc (DataCon {}) cn, args) =>
117 | findSCcall defs env Guarded pats fc cn args
118 | (Toplevel, Ref fc (DataCon {}) cn, args) =>
119 | findSCcall defs env Guarded pats fc cn args
120 | (_, Ref fc Func fn, args) =>
121 | do logC "totality" 50 $
122 | pure $
"Looking up type of " ++ show !(toFullNames fn)
123 | findSCcall defs env Unguarded pats fc fn args
125 | do scs <- traverse (findSC defs env Unguarded pats) args
128 | handleCase : Term vars -> List (Term vars) -> Core (Maybe (List SCCall))
129 | handleCase (Ref fc nt n) args
130 | = do n' <- toFullNames n
132 | then Just <$> findSCcall defs env g pats fc n args
134 | handleCase _ _ = pure Nothing
136 | isAssertTotal : Term vars -> Core Bool
137 | isAssertTotal (Ref fc Func fn)
138 | = pure $
!(toFullNames fn) == NS builtinNS (UN $
Basic "assert_total")
139 | isAssertTotal tm = pure False
141 | conIfGuarded : Term vars -> Core (Term vars)
142 | conIfGuarded (Ref fc Func n)
143 | = do defs <- get Ctxt
144 | Just gdef <- lookupCtxtExact n (gamma defs)
145 | | Nothing => pure $
Ref fc Func n
146 | if AllGuarded `elem` flags gdef
147 | then pure $
Ref fc (DataCon 0 0) n
148 | else pure $
Ref fc Func n
149 | conIfGuarded tm = pure tm
151 | knownOr : Core SizeChange -> Core SizeChange -> Core SizeChange
152 | knownOr x y = case !x of Unknown => y;
_ => x
154 | plusLazy : Core SizeChange -> Core SizeChange -> Core SizeChange
155 | plusLazy x y = case !x of Smaller => pure Smaller;
x => pure $
x |+| !y
158 | sizeCompare : {auto defs : Defs} ->
164 | sizeCompareCon : {auto defs : Defs} -> Nat -> Term vars -> Term vars -> Core Bool
165 | sizeCompareTyCon : {auto defs : Defs} -> Nat -> Term vars -> Term vars -> Core Bool
166 | sizeCompareConArgs : {auto defs : Defs} -> Nat -> Term vars -> List (Term vars) -> Core Bool
167 | sizeCompareApp : {auto defs : Defs} -> Nat -> Term vars -> Term vars -> Core SizeChange
169 | sizeCompare fuel s (Erased _ (Dotted t)) = sizeCompare fuel s t
170 | sizeCompare fuel _ (Erased {}) = pure Unknown
172 | sizeCompare fuel s (As _ _ p t)
173 | = knownOr (sizeCompare fuel s p) (sizeCompare fuel s t)
174 | sizeCompare fuel (As _ _ p s) t
175 | = knownOr (sizeCompare fuel p t) (sizeCompare fuel s t)
177 | sizeCompare fuel s@(Meta {}) t@(Meta {}) = pure (if sizeEq s t then Same else Unknown)
179 | sizeCompare fuel s@(Meta n _ i args) t = do
180 | Just gdef <- lookupCtxtExact (Resolved i) (gamma defs) | _ => pure Unknown
181 | let (PMDef _ [] (STerm _ tm) _ _) = definition gdef | _ => pure Unknown
182 | tm <- substMeta (embed tm) args zero Subst.empty
183 | sizeCompare fuel tm t
185 | substMeta : {0 drop, vs : _} ->
186 | Term (drop ++ vs) -> List (Term vs) ->
187 | SizeOf drop -> SubstEnv drop vs ->
189 | substMeta (Bind bfc n (Lam _ c e ty) sc) (a :: as) drop env
190 | = substMeta sc as (suc drop) (a :: env)
191 | substMeta (Bind bfc n (Let _ c val ty) sc) as drop env
192 | = substMeta (subst val sc) as drop env
193 | substMeta rhs [] drop env = pure (substs drop env rhs)
194 | substMeta rhs _ _ _ = throw (InternalError ("Badly formed metavar solution \{show n}"))
196 | sizeCompare fuel s t
197 | = if !(sizeCompareTyCon fuel s t) then pure Same
198 | else if !(sizeCompareCon fuel s t)
200 | else sizeCompareApp fuel s t
202 | sizeCompareProdConArgs : {auto defs : Defs} -> Nat -> List (Term vars) -> List (Term vars) -> Core SizeChange
203 | sizeCompareProdConArgs _ [] [] = pure Same
204 | sizeCompareProdConArgs fuel (x :: xs) (y :: ys) =
205 | case !(sizeCompare fuel x y) of
206 | Unknown => pure Unknown
207 | t => (t |*|) <$> sizeCompareProdConArgs fuel xs ys
208 | sizeCompareProdConArgs _ _ _ = pure Unknown
210 | sizeCompareTyCon fuel s t =
211 | let (f, args) = getFnArgs t in
212 | let (g, args') = getFnArgs s in
214 | Ref _ (TyCon {}) cn => case g of
215 | Ref _ (TyCon {}) cn' => if cn == cn'
216 | then (Unknown /=) <$> sizeCompareProdConArgs fuel args' args
221 | sizeCompareCon fuel s t
222 | = let (f, args) = getFnArgs t in
224 | Ref _ (DataCon t a) cn =>
226 | if !(sizeCompareConArgs (minus fuel 1) s args) then pure True
227 | else let (g, args') = getFnArgs s in
229 | (S k, Ref _ (DataCon t' a') cn') => do
232 | if cn == cn' && length args == length args'
233 | then (Smaller ==) <$> sizeCompareProdConArgs k args' args
238 | sizeCompareConArgs _ s [] = pure False
239 | sizeCompareConArgs fuel s (t :: ts)
240 | = case !(sizeCompare fuel s t) of
241 | Unknown => sizeCompareConArgs fuel s ts
244 | sizeCompareApp fuel f t =
245 | let (f,args) = getFnArgs f
246 | (t,args') = getFnArgs t
247 | in if sizeEq f t then checkArgs args args' else pure Unknown
249 | checkArgs : List (Term vars) -> List (Term vars) -> Core SizeChange
250 | checkArgs Nil Nil = pure Same
251 | checkArgs (s :: ss) Nil = pure Same
252 | checkArgs (s :: ss) (t :: ts) = if sizeEq s t then checkArgs ss ts else pure Unknown
253 | checkArgs _ (t :: ts) = pure Unknown
255 | sizeCompareAsserted : {auto defs : Defs} -> Nat -> Maybe (Term vars) -> Term vars -> Core SizeChange
256 | sizeCompareAsserted fuel (Just s) t
257 | = pure $
case !(sizeCompare fuel s t) of
260 | sizeCompareAsserted _ Nothing _ = pure Unknown
263 | asserted : Name -> Term vars -> Maybe (Term vars)
264 | asserted aSmaller tm
265 | = case getFnArgs tm of
266 | (Ref _ nt fn, [_, _, b, _])
267 | => if fn == aSmaller
274 | mkChange : Defs -> Name ->
275 | (pats : List (Term vars)) ->
276 | (arg : Term vars) ->
277 | Core (List SizeChange)
278 | mkChange defs aSmaller pats arg
279 | = let fuel = defs.options.elabDirectives.totalLimit
280 | in traverse (\p => plusLazy (sizeCompareAsserted fuel (asserted aSmaller arg) p) (sizeCompare fuel arg p)) pats
288 | getCasePats : {auto c : Ref Ctxt Defs} ->
290 | Defs -> Name -> List (Term vars) ->
291 | List (Term vars) ->
292 | Core (Maybe (List (
vs ** (Env Term vs,
293 | List (Term vs), Term vs))
))
295 | getCasePats {vars} defs n pats args
296 | = do Just (PMDef _ _ _ _ pdefs) <- lookupDefExact n (gamma defs)
297 | | _ => pure Nothing
298 | log "totality" 20 $
299 | unwords ["Looking at the", show (length pdefs), "cases of", show n]
300 | let pdefs' = map matchArgs pdefs
301 | logC "totality" 20 $
do
302 | old <- for pdefs $
\ (_ ** (_, lhs, rhs)) => do
303 | lhs <- toFullNames lhs
304 | rhs <- toFullNames rhs
305 | pure $
" " ++ show lhs ++ " => " ++ show rhs
306 | new <- for pdefs' $
\ (_ ** (_, lhs, rhs)) => do
307 | lhs <- traverse toFullNames lhs
308 | rhs <- toFullNames rhs
309 | pure $
" " ++ show lhs ++ " => " ++ show rhs
310 | pure $
unlines $
"Updated" :: old ++ " to:" :: new
314 | updateRHS : {vs, vs' : _} ->
315 | List (Term vs, Term vs') -> Term vs -> Term vs'
316 | updateRHS {vs} {vs'} ms tm
317 | = case lookupTm tm ms of
321 | urhs : Term vs -> Term vs'
322 | urhs (Local fc _ _ _) = Erased fc Placeholder
323 | urhs (Ref fc nt n) = Ref fc nt n
324 | urhs (Meta fc m i margs) = Meta fc m i (map (updateRHS ms) margs)
325 | urhs (App fc f a) = App fc (updateRHS ms f) (updateRHS ms a)
326 | urhs (As fc s a p) = As fc s (updateRHS ms a) (updateRHS ms p)
327 | urhs (TDelayed fc r ty) = TDelayed fc r (updateRHS ms ty)
328 | urhs (TDelay fc r ty tm)
329 | = TDelay fc r (updateRHS ms ty) (updateRHS ms tm)
330 | urhs (TForce fc r tm) = TForce fc r (updateRHS ms tm)
331 | urhs (Bind fc x b sc)
332 | = Bind fc x (map (updateRHS ms) b)
333 | (updateRHS (map (\vt => (weaken (fst vt), weaken (snd vt))) ms) sc)
334 | urhs (PrimVal fc c) = PrimVal fc c
335 | urhs (Erased fc Impossible) = Erased fc Impossible
336 | urhs (Erased fc Placeholder) = Erased fc Placeholder
337 | urhs (Erased fc (Dotted t)) = Erased fc (Dotted (updateRHS ms t))
338 | urhs (TType fc u) = TType fc u
340 | lookupTm : Term vs -> List (Term vs, Term vs') -> Maybe (Term vs')
341 | lookupTm tm [] = Nothing
342 | lookupTm (As fc s p tm) tms
344 | = do tm' <- lookupTm tm tms
345 | Just $
As fc s tm' (urhs tm)
346 | lookupTm tm ((As fc s p tm', v) :: tms)
349 | else do tm' <- lookupTm tm ((tm', v) :: tms)
350 | Just $
As fc s (urhs p) tm'
351 | lookupTm tm ((tm', v) :: tms)
354 | else lookupTm tm tms
356 | updatePat : {vs, vs' : _} ->
357 | List (Term vs, Term vs') -> Term vs -> Term vs'
358 | updatePat ms tm = updateRHS ms tm
360 | matchArgs : (
vs ** (Env Term vs, Term vs, Term vs))
->
361 | (
vs ** (Env Term vs, List (Term vs), Term vs))
362 | matchArgs (
_ ** (env', lhs, rhs))
363 | = let patMatch = reverse (zip args (getArgs lhs)) in
364 | (
_ ** (env', map (updatePat patMatch) pats, rhs))
366 | findSCcall : {vars : _} ->
367 | {auto c : Ref Ctxt Defs} ->
368 | Defs -> Env Term vars -> Guardedness ->
369 | List (Term vars) ->
370 | FC -> Name -> List (Term vars) ->
372 | findSCcall defs env g pats fc fn_in args
375 | = do fn <- getFullName fn_in
376 | logC "totality.termination.sizechange" 10 $
do pure $
"Looking under " ++ show !(toFullNames fn)
377 | aSmaller <- resolved (gamma defs) (NS builtinNS (UN $
Basic "assert_smaller"))
379 | then do scs1 <- traverse (findSC defs env g pats) args
380 | mps <- getCasePats defs fn pats args
381 | scs2 <- traverse (findInCase defs g) $
fromMaybe [] mps
382 | pure (concat (scs1 ++ scs2))
383 | else do scs <- traverse (findSC defs env g pats) args
384 | pure $
[MkSCCall fn
386 | !(traverse (mkChange defs aSmaller pats) args))
390 | findInCase : {auto c : Ref Ctxt Defs} ->
391 | Defs -> Guardedness ->
392 | (
vs ** (Env Term vs, List (Term vs), Term vs))
->
394 | findInCase defs g (
_ ** (env, pats, tm))
395 | = do logC "totality" 10 $
396 | do ps <- traverse toFullNames pats
397 | pure ("Looking in case args " ++ show ps)
398 | logTermNF "totality" 10 " =" env tm
399 | rhs <- normaliseOpts tcOnly defs env tm
400 | findSC defs env g pats (delazy defs rhs)
402 | findCalls : {auto c : Ref Ctxt Defs} ->
403 | Defs -> (
vars ** (Env Term vars, Term vars, Term vars))
->
405 | findCalls defs (
_ ** (env, lhs, rhs_in))
406 | = do let pargs = getArgs (delazy defs lhs)
407 | rhs <- normaliseOpts tcOnly defs env rhs_in
408 | findSC defs env Toplevel pargs (delazy defs rhs)
410 | getSC : {auto c : Ref Ctxt Defs} ->
411 | Defs -> Def -> Core (List SCCall)
412 | getSC defs (PMDef _ args _ _ pats)
413 | = do sc <- traverse (findCalls defs) pats
414 | pure $
nub (concat sc)
415 | getSC defs _ = pure []
418 | calculateSizeChange : {auto c : Ref Ctxt Defs} ->
419 | FC -> Name -> Core (List SCCall)
420 | calculateSizeChange loc n
421 | = do logC "totality.termination.sizechange" 5 $
do pure $
"Calculating Size Change: " ++ show !(toFullNames n)
423 | Just def <- lookupCtxtExact n (gamma defs)
424 | | Nothing => undefinedName loc n
425 | getSC defs (definition def)