0 | module Core.Termination.CallGraph
  1 |
  2 | import Core.Case.CaseTree
  3 | import Core.Context.Log
  4 | import Core.Env
  5 | import Core.Normalise
  6 | import Core.Options
  7 | import Core.Value
  8 |
  9 | import Libraries.Data.List.SizeOf
 10 | import Libraries.Data.SparseMatrix
 11 |
 12 | import Data.String
 13 |
 14 | %default covering
 15 |
 16 | data Guardedness = Toplevel | Unguarded | Guarded | InDelay
 17 |
 18 | Show Guardedness where
 19 |   show Toplevel = "Toplevel"
 20 |   show Unguarded = "Unguarded"
 21 |   show Guarded = "Guarded"
 22 |   show InDelay = "InDelay"
 23 |
 24 | sizeEq : {auto 0 cv : CompatibleVars rhsVars lhsVars} ->
 25 |          Term rhsVars -> -- RHS
 26 |          Term lhsVars -> -- LHS: may contain dot-patterns, try both sides of as patterns
 27 |          Bool
 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'
 40 | -- traverse dotted LHS terms
 41 | sizeEq t (Erased _ (Dotted t')) = eqTerm t t' -- t' is no longer a pattern
 42 | sizeEq (TType {}) (TType {}) = True
 43 | sizeEq _ _ = False
 44 |
 45 | -- Remove all force and delay annotations which are nothing to do with
 46 | -- coinduction meaning that all Delays left guard coinductive calls.
 47 | delazy : Defs -> Term vars -> Term vars
 48 | delazy defs (TDelayed fc r tm)
 49 |     = let tm' = delazy defs tm in
 50 |           case r of
 51 |                LInf => TDelayed fc r tm'
 52 |                _ => tm'
 53 | delazy defs (TDelay fc r ty tm)
 54 |     = let ty' = delazy defs ty
 55 |           tm' = delazy defs tm in
 56 |           case r of
 57 |                LInf => TDelay fc r ty' tm'
 58 |                _ => tm'
 59 | delazy defs (TForce fc r t)
 60 |     = case r of
 61 |            LInf => TForce fc r (delazy defs t)
 62 |            _ => 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)
 68 | delazy defs tm = tm
 69 |
 70 | mutual
 71 |   findSC : {vars : _} ->
 72 |            {auto c : Ref Ctxt Defs} ->
 73 |            Defs -> Env Term vars -> Guardedness ->
 74 |            List (Term vars) -> -- LHS args
 75 |            Term vars -> -- RHS
 76 |            Core (List SCCall)
 77 |   findSC {vars} defs env g pats (Bind fc n b sc)
 78 |        = [| findSCbinder b ++ findSC defs (b :: env) g (map weaken pats) sc |]
 79 |     where
 80 |       findSCPiInfo : PiInfo (Term vars) -> Core (List SCCall)
 81 |       findSCPiInfo (DefImplicit def) = findSC defs env g pats def
 82 |       findSCPiInfo _ = pure []
 83 |
 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 [] -- other binders shouldn't appear in the RHS of a definition
 89 |   -- If we're Guarded and find a Delay, continue with the argument as InDelay
 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
 99 |                | True => pure []
100 |            -- if it's a 'case' or 'if' just go straight into the arguments
101 |            Nothing <- handleCase fn args
102 |                | Just res => pure res
103 |            fn' <- conIfGuarded fn -- pretend it's a data constructor if
104 |                                   -- it has the AllGuarded flag
105 |            case (g, fn', args) of
106 |     -- If we're InDelay and find a constructor (or a function call which is
107 |     -- guaranteed to return a constructor; AllGuarded set), continue as InDelay
108 |              (InDelay, Ref fc (DataCon {}) cn, args) =>
109 |                  do scs <- traverse (findSC defs env InDelay pats) args
110 |                     pure (concat scs)
111 |              -- If we're InDelay otherwise, just check the arguments, the
112 |              -- function call is okay
113 |              (InDelay, _, args) =>
114 |                  do scs <- traverse (findSC defs env Unguarded pats) args
115 |                     pure (concat scs)
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
124 |              (_, f, args) =>
125 |                  do scs <- traverse (findSC defs env Unguarded pats) args
126 |                     pure (concat scs)
127 |       where
128 |         handleCase : Term vars -> List (Term vars) -> Core (Maybe (List SCCall))
129 |         handleCase (Ref fc nt n) args
130 |             = do n' <- toFullNames n
131 |                  if caseFn n'
132 |                     then Just <$> findSCcall defs env g pats fc n args
133 |                     else pure Nothing
134 |         handleCase _ _ = pure Nothing
135 |
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
140 |
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
150 |
151 |   knownOr : Core SizeChange -> Core SizeChange -> Core SizeChange
152 |   knownOr x y = case !x of Unknown => y; _ => x
153 |
154 |   plusLazy : Core SizeChange -> Core SizeChange -> Core SizeChange
155 |   plusLazy x y = case !x of Smaller => pure Smaller; x => pure $ x |+| !y
156 |
157 |   -- Return whether first argument is structurally smaller than the second.
158 |   sizeCompare : {auto defs : Defs} ->
159 |                 Nat -> -- backtracking fuel
160 |                 Term vars -> -- RHS: term we're checking
161 |                 Term vars -> -- LHS: argument it might be smaller than
162 |                 Core SizeChange
163 |
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
168 |
169 |   sizeCompare fuel s (Erased _ (Dotted t)) = sizeCompare fuel s t
170 |   sizeCompare fuel _ (Erased {}) = pure Unknown -- incomparable!
171 |   -- for an as pattern, it's smaller if it's smaller than either part
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)
176 |   -- if they're both metas, let sizeEq check if they're the same
177 |   sizeCompare fuel s@(Meta {}) t@(Meta {}) = pure (if sizeEq s t then Same else Unknown)
178 |   -- otherwise try to expand RHS meta
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
184 |     where
185 |       substMeta : {0 drop, vs : _} ->
186 |                   Term (drop ++ vs) -> List (Term vs) ->
187 |                   SizeOf drop -> SubstEnv drop vs ->
188 |                   Core (Term 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}"))
195 |
196 |   sizeCompare fuel s t
197 |      = if !(sizeCompareTyCon fuel s t) then pure Same
198 |        else if !(sizeCompareCon fuel s t)
199 |           then pure Smaller
200 |           else sizeCompareApp fuel s t
201 |
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
209 |
210 |   sizeCompareTyCon fuel s t =
211 |     let (f, args) = getFnArgs t in
212 |     let (g, args') = getFnArgs s in
213 |     case f of
214 |       Ref _ (TyCon {}) cn => case g of
215 |         Ref _ (TyCon {}) cn' => if cn == cn'
216 |             then (Unknown /=) <$> sizeCompareProdConArgs fuel args' args
217 |             else pure False
218 |         _ => pure False
219 |       _ => pure False
220 |
221 |   sizeCompareCon fuel s t
222 |       = let (f, args) = getFnArgs t in
223 |         case f of
224 |              Ref _ (DataCon t a) cn =>
225 |                 -- if s is smaller or equal to an arg, then it is smaller than t
226 |                 if !(sizeCompareConArgs (minus fuel 1) s args) then pure True
227 |                 else let (g, args') = getFnArgs s in
228 |                     case (fuel, g) of
229 |                         (S k, Ref _ (DataCon t' a') cn') => do
230 |                                 -- if s is a matching DataCon, applied to same number of args,
231 |                                 -- no Unknown args, and at least one Smaller
232 |                                 if cn == cn' && length args == length args'
233 |                                   then (Smaller ==) <$> sizeCompareProdConArgs k args' args
234 |                                   else pure False
235 |                         _ => pure $ False
236 |              _ => pure False
237 |
238 |   sizeCompareConArgs _ s [] = pure False
239 |   sizeCompareConArgs fuel s (t :: ts)
240 |       = case !(sizeCompare fuel s t) of
241 |           Unknown => sizeCompareConArgs fuel s ts
242 |           _ => pure True
243 |
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
248 |     where
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
254 |
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
258 |           Unknown => Unknown
259 |           _ => Smaller
260 |   sizeCompareAsserted _ Nothing _ = pure Unknown
261 |
262 |   -- if the argument is an 'assert_smaller', return the thing it's smaller than
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
268 |                          then Just b
269 |                          else Nothing
270 |               _ => Nothing
271 |
272 |   -- Calculate the size change for the given argument.  i.e., return the
273 |   -- relative size of the given argument to each entry in 'pats'.
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
281 |
282 |   -- Given a name of a case function, and a list of the arguments being
283 |   -- passed to it, update the pattern list so that it's referring to the LHS
284 |   -- of the case block function and return the corresponding RHS.
285 |
286 |   -- This way, we can build case blocks directly into the size change graph
287 |   -- rather than treating the definitions separately.
288 |   getCasePats : {auto c : Ref Ctxt Defs} ->
289 |                 {vars : _} ->
290 |                 Defs -> Name -> List (Term vars) ->
291 |                 List (Term vars) ->
292 |                 Core (Maybe (List (vs ** (Env Term vs,
293 |                                          List (Term vs), Term vs))))
294 |
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
311 |            pure $ Just pdefs'
312 |
313 |     where
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
318 |                  Nothing => urhs tm
319 |                  Just t => t
320 |         where
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
339 |
340 |           lookupTm : Term vs -> List (Term vs, Term vs') -> Maybe (Term vs')
341 |           lookupTm tm [] = Nothing
342 |           lookupTm (As fc s p tm) tms -- Want to keep the pattern and the variable,
343 |                                       -- if there was an @ in the parent
344 |               = do tm' <- lookupTm tm tms
345 |                    Just $ As fc s tm' (urhs tm)
346 |           lookupTm tm ((As fc s p tm', v) :: tms)
347 |               = if tm == p
348 |                    then Just v
349 |                    else do tm' <- lookupTm tm ((tm', v) :: tms)
350 |                            Just $ As fc s (urhs p) tm'
351 |           lookupTm tm ((tm', v) :: tms)
352 |               = if tm == tm'
353 |                    then Just v
354 |                    else lookupTm tm tms
355 |
356 |       updatePat : {vs, vs' : _} ->
357 |                   List (Term vs, Term vs') -> Term vs -> Term vs'
358 |       updatePat ms tm = updateRHS ms tm
359 |
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))
365 |
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) ->
371 |                Core (List SCCall)
372 |   findSCcall defs env g pats fc fn_in args
373 |         -- Under 'assert_total' we assume that all calls are fine, so leave
374 |         -- the size change list empty
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"))
378 |            if caseFn fn
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
385 |                                (fromListList
386 |                                     !(traverse (mkChange defs aSmaller pats) args))
387 |                                fc]
388 |                                ++ concat scs
389 |
390 |   findInCase : {auto c : Ref Ctxt Defs} ->
391 |                Defs -> Guardedness ->
392 |                (vs ** (Env Term vs, List (Term vs), Term vs)) ->
393 |                Core (List SCCall)
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)
401 |
402 | findCalls : {auto c : Ref Ctxt Defs} ->
403 |             Defs -> (vars ** (Env Term vars, Term vars, Term vars)) ->
404 |             Core (List SCCall)
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)
409 |
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 []
416 |
417 | export
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)
422 |          defs <- get Ctxt
423 |          Just def <- lookupCtxtExact n (gamma defs)
424 |               | Nothing => undefinedName loc n
425 |          getSC defs (definition def)
426 |