2 | import Core.Case.CaseTree
3 | import Core.Case.Util
4 | import Core.Context.Log
6 | import Core.Normalise
12 | import Libraries.Data.NameMap
13 | import Libraries.Data.NatSet
14 | import Libraries.Data.String.Extra
15 | import Libraries.Data.List.SizeOf
16 | import Libraries.Text.PrettyPrint.Prettyprinter
21 | conflictMatch : List (Name, Term vars) -> Bool
22 | conflictMatch [] = False
23 | conflictMatch ((x, tm) :: ms) = conflictArgs x tm ms || conflictMatch ms
25 | data ClashResult = Distinct | Same | Incomparable
27 | clash : Term vars -> Term vars -> ClashResult
28 | clash (Ref _ (DataCon t _) _) (Ref _ (DataCon t' _) _)
29 | = if t /= t' then Distinct else Same
30 | clash (Ref _ (TyCon _) n) (Ref _ (TyCon _) n')
31 | = if n /= n' then Distinct else Same
32 | clash (PrimVal _ c) (PrimVal _ c') = if c /= c' then Distinct else Same
33 | clash (Ref _ t _) (PrimVal {}) = if isJust (isCon t) then Distinct else Incomparable
34 | clash (PrimVal {}) (Ref _ t _) = if isJust (isCon t) then Distinct else Incomparable
35 | clash (Ref _ t _) (TType {}) = if isJust (isCon t) then Distinct else Incomparable
36 | clash (TType {}) (Ref _ t _) = if isJust (isCon t) then Distinct else Incomparable
37 | clash (Ref _ t _) (Bind _ _ (Pi {}) _) = if isJust (isCon t) then Distinct else Incomparable
38 | clash (Bind _ _ (Pi {}) _) (Ref _ t _) = if isJust (isCon t) then Distinct else Incomparable
39 | clash (TType {}) (PrimVal {}) = Distinct
40 | clash (PrimVal {}) (TType {}) = Distinct
41 | clash (Bind _ _ (Pi {}) _) (PrimVal {}) = Distinct
42 | clash (PrimVal {}) (Bind _ _ (Pi {}) _) = Distinct
43 | clash (TType {}) (Bind _ _ (Pi {}) _) = Distinct
44 | clash (Bind _ _ (Pi {}) _) (TType {}) = Distinct
45 | clash _ _ = Incomparable
47 | findN : Nat -> Term vars -> Bool
48 | findN i (Local _ _ i' _) = i == i'
50 | = let (Ref _ (DataCon {}) _, args) = getFnArgs tm
56 | conflictTm : Term vars -> Term vars -> Bool
57 | conflictTm (Local _ _ i _) tm
58 | = let (Ref _ (DataCon {}) _, args) = getFnArgs tm
61 | conflictTm tm (Local _ _ i _)
62 | = let (Ref _ (DataCon {}) _, args) = getFnArgs tm
66 | = let (f, args) = getFnArgs tm
67 | (f', args') = getFnArgs tm' in
70 | Incomparable => False
71 | Same => (any (uncurry conflictTm) (zip args args'))
73 | conflictArgs : Name -> Term vars -> List (Name, Term vars) -> Bool
74 | conflictArgs n tm [] = False
75 | conflictArgs n tm ((x, tm') :: ms)
76 | = (n == x && conflictTm tm tm') || conflictArgs n tm ms
80 | conflict : {vars : _} ->
81 | {auto c : Ref Ctxt Defs} ->
82 | Defs -> Env Term vars -> NF vars -> Name -> Core Bool
83 | conflict defs env nfty n
84 | = do Just gdef <- lookupCtxtExact n (gamma defs)
85 | | Nothing => pure False
86 | case (definition gdef, type gdef) of
87 | (DCon t arity _, dty)
88 | => do Nothing <- conflictNF 0 nfty !(nf defs Env.empty dty)
89 | | Just ms => pure $
conflictMatch ms
94 | conflictArgs : Int -> List (Closure vars) -> List ClosedClosure ->
95 | Core (Maybe (List (Name, Term vars)))
96 | conflictArgs _ [] [] = pure (Just [])
97 | conflictArgs i (c :: cs) (c' :: cs')
98 | = do cnf <- evalClosure defs c
99 | cnf' <- evalClosure defs c'
100 | Just ms <- conflictNF i cnf cnf'
101 | | Nothing => pure Nothing
102 | Just ms' <- conflictArgs i cs cs'
103 | | Nothing => pure Nothing
104 | pure (Just (ms ++ ms'))
105 | conflictArgs _ _ _ = pure (Just [])
113 | conflictNF : Int -> NF vars -> ClosedNF ->
114 | Core (Maybe (List (Name, Term vars)))
115 | conflictNF i t (NBind fc x b sc)
119 | = let x' = MN (show x) i in
120 | conflictNF (i + 1) t
121 | !(sc defs (toClosure defaultOpts Env.empty (Ref fc Bound x')))
122 | conflictNF i nf (NApp _ (NRef Bound n) [])
123 | = pure (Just [(n, !(quote defs env nf))])
124 | conflictNF i (NDCon _ n t a args) (NDCon _ n' t' a' args')
126 | then conflictArgs i (map snd args) (map snd args')
128 | conflictNF i (NTCon _ n a args) (NTCon _ n' a' args')
130 | then conflictArgs i (map snd args) (map snd args')
132 | conflictNF i (NPrimVal _ c) (NPrimVal _ c')
134 | then pure (Just [])
136 | conflictNF _ _ _ = pure (Just [])
141 | isEmpty : {vars : _} ->
142 | {auto c : Ref Ctxt Defs} ->
143 | Defs -> Env Term vars -> NF vars -> Core Bool
144 | isEmpty defs env (NTCon fc n a args)
145 | = do Just nty <- lookupDefExact n (gamma defs)
148 | TCon _ _ _ flags _ Nothing _ => pure False
149 | TCon _ _ _ flags _ (Just cons) _
150 | => if not (external flags)
151 | then allM (conflict defs env (NTCon fc n a args)) cons
154 | isEmpty defs env _ = pure False
156 | altMatch : CaseAlt vars -> CaseAlt vars -> Bool
157 | altMatch _ (DefaultCase _) = True
158 | altMatch (DelayCase _ _ t) (DelayCase _ _ t') = True
159 | altMatch (ConCase n t _ _) (ConCase n' t' _ _) = t == t'
160 | altMatch (ConstCase c _) (ConstCase c' _) = c == c'
161 | altMatch _ _ = False
165 | getMissingAlts : {auto c : Ref Ctxt Defs} ->
167 | FC -> Defs -> NF vars -> List (CaseAlt vars) ->
168 | Core (List (CaseAlt vars))
171 | getMissingAlts fc defs (NPrimVal _ $
PrT WorldType) alts
173 | then pure [DefaultCase (Unmatched "Coverage check")]
175 | getMissingAlts fc defs (NPrimVal _ c) alts
176 | = do log "coverage.missing" 50 $
"Looking for missing alts at type " ++ show c
177 | if any isDefault alts
178 | then do log "coverage.missing" 20 "Found default"
180 | else pure [DefaultCase (Unmatched "Coverage check")]
182 | getMissingAlts fc defs (NType {}) alts
183 | = do log "coverage.missing" 50 "Looking for missing alts at type Type"
184 | if any isDefault alts
185 | then do log "coverage.missing" 20 "Found default"
187 | else pure [DefaultCase (Unmatched "Coverage check")]
188 | getMissingAlts fc defs nfty alts
189 | = do log "coverage.missing" 50 $
"Getting constructors for: " ++ show nfty
190 | logNF "coverage.missing" 20 "Getting constructors for" (mkEnv fc _) nfty
191 | allCons <- getCons defs nfty
192 | pure (filter (noneOf alts)
193 | (map (mkAlt fc (Unmatched "Coverage check")) allCons))
196 | noneOf : List (CaseAlt vars) -> CaseAlt vars -> Bool
197 | noneOf alts c = not $
any (altMatch c) alts
200 | KnownVars : Scope -> Type -> Type
201 | KnownVars vars a = List (Var vars, a)
203 | showK : {ns : _} ->
204 | Show a => KnownVars ns a -> String
205 | showK {a} xs = show (map aString xs)
207 | aString : {vars : Scope} ->
208 | (Var vars, a) -> (Name, a)
209 | aString (MkVar v, t) = (nameAt v, t)
212 | weakenNs : SizeOf args -> KnownVars vars a -> KnownVars (args ++ vars) a
213 | weakenNs args [] = []
214 | weakenNs args ((v, t) :: xs)
215 | = (weakenNs args v, t) :: weakenNs args xs
217 | findTag : {idx, vars : _} ->
218 | (0 p : IsVar n idx vars) -> KnownVars vars a -> Maybe a
219 | findTag v [] = Nothing
220 | findTag v ((v', t) :: xs)
225 | addNot : {idx, vars : _} ->
226 | (0 p : IsVar n idx vars) -> Int -> KnownVars vars (List Int) ->
227 | KnownVars vars (List Int)
228 | addNot v t [] = [(MkVar v, [t])]
229 | addNot v t ((v', ts) :: xs)
231 | then ((v', t :: ts) :: xs)
232 | else ((v', ts) :: addNot v t xs)
234 | tagIsNot : List Int -> CaseAlt vars -> Bool
235 | tagIsNot ts (ConCase _ t' _ _) = not (t' `elem` ts)
236 | tagIsNot ts (ConstCase {}) = True
237 | tagIsNot ts (DelayCase {}) = True
238 | tagIsNot ts (DefaultCase _) = False
243 | replaceDefaults : {auto c : Ref Ctxt Defs} ->
245 | FC -> Defs -> NF vars -> List (CaseAlt vars) ->
246 | Core (List (CaseAlt vars))
249 | replaceDefaults fc defs (NPrimVal {}) cs = pure cs
250 | replaceDefaults fc defs (NType {}) cs = pure cs
251 | replaceDefaults fc defs nfty cs
252 | = do cs' <- traverse rep cs
253 | pure (dropRep (concat cs'))
255 | rep : CaseAlt vars -> Core (List (CaseAlt vars))
256 | rep (DefaultCase sc)
257 | = do allCons <- getCons defs nfty
258 | pure (map (mkAlt fc sc) allCons)
261 | dropRep : List (CaseAlt vars) -> List (CaseAlt vars)
263 | dropRep (c@(ConCase n t args sc) :: rest)
266 | = c :: dropRep (filter (not . tagIs t) rest)
267 | dropRep (c :: rest) = c :: dropRep rest
273 | buildArgs : {auto c : Ref Ctxt Defs} ->
276 | KnownVars vars Int ->
277 | KnownVars vars (List Int) ->
280 | CaseTree vars -> Core (List (List ClosedTerm))
281 | buildArgs fc defs known not ps cs@(Case {name = var} idx el ty altsIn)
286 | = do let fenv = mkEnv fc _
287 | nfty <- nf defs fenv ty
288 | alts <- replaceDefaults fc defs nfty altsIn
289 | let alts' = alts ++ !(getMissingAlts fc defs nfty alts)
290 | let altsK = maybe alts' (\t => filter (tagIs t) alts')
292 | let altsN = maybe altsK (\ts => filter (tagIsNot ts) altsK)
294 | buildArgsAlt not altsN
296 | buildArgAlt : KnownVars vars (List Int) ->
297 | CaseAlt vars -> Core (List (List ClosedTerm))
298 | buildArgAlt not' (ConCase n t args sc)
299 | = do let l = mkSizeOf args
300 | let con = Ref fc (DataCon t (size l)) n
301 | let ps' = map (substName var
303 | con (map (Ref fc Bound) args))) ps
304 | buildArgs fc defs (weakenNs l ((MkVar el, t) :: known))
305 | (weakenNs l not') ps' sc
306 | buildArgAlt not' (DelayCase t a sc)
307 | = let l = mkSizeOf [t, a]
308 | ps' = map (substName var (TDelay fc LUnknown
310 | (Ref fc Bound a))) ps in
311 | buildArgs fc defs (weakenNs l known) (weakenNs l not')
313 | buildArgAlt not' (ConstCase c sc)
314 | = do let ps' = map (substName var (PrimVal fc c)) ps
315 | buildArgs fc defs known not' ps' sc
316 | buildArgAlt not' (DefaultCase sc)
317 | = buildArgs fc defs known not' ps sc
319 | buildArgsAlt : KnownVars vars (List Int) -> List (CaseAlt vars) ->
320 | Core (List (List ClosedTerm))
321 | buildArgsAlt not' [] = pure []
322 | buildArgsAlt not' (c@(ConCase _ t _ _) :: cs)
323 | = pure $
!(buildArgAlt not' c) ++
324 | !(buildArgsAlt (addNot el t not') cs)
325 | buildArgsAlt not' (c :: cs)
326 | = pure $
!(buildArgAlt not' c) ++ !(buildArgsAlt not' cs)
328 | buildArgs fc defs known not ps (STerm _ vs)
330 | buildArgs fc defs known not ps (Unmatched msg)
332 | buildArgs fc defs known not ps Impossible
340 | getMissing : {vars : _} ->
341 | {auto c : Ref Ctxt Defs} ->
342 | FC -> Name -> ClosedTerm ->
344 | Core (List ClosedTerm)
345 | getMissing fc n ty ctree
346 | = do defs <- get Ctxt
347 | let psIn = map (Ref fc Bound) vars
348 | pats <- buildArgs fc defs [] [] psIn ctree
349 | pats <- for pats $
trimArgs defs [<] !(nf defs Env.empty ty)
350 | unless (null pats) $
351 | logC "coverage.missing" 20 $
map unlines $
352 | for pats $
map show . traverse toFullNames
353 | pure (map (apply fc (Ref fc Func n)) pats)
356 | SnocList ClosedTerm -> ClosedNF ->
357 | List ClosedTerm -> Core (List ClosedTerm)
358 | trimArgs defs acc (NBind _ n (Pi {}) sc) (x :: xs)
359 | = trimArgs defs (acc :< x) !(sc defs $
toClosure defaultOpts Env.empty x) xs
360 | trimArgs _ acc _ _ = pure $
toList acc
367 | getNonCoveringRefs : {auto c : Ref Ctxt Defs} ->
368 | FC -> Name -> Core (List Name)
369 | getNonCoveringRefs fc n
370 | = do defs <- get Ctxt
371 | Just d <- lookupCtxtExact n (gamma defs)
372 | | Nothing => undefinedName fc n
373 | let ds = mapMaybe noAssert (toList (refersTo d))
374 | let cases = filter isCase !(traverse toFullNames ds)
377 | cbad <- traverse (getNonCoveringRefs fc) cases
378 | topbad <- filterM (notCovering defs) ds
379 | pure (topbad ++ concat cbad)
381 | isCase : Name -> Bool
382 | isCase (NS _ n) = isCase n
383 | isCase (CaseBlock {}) = True
386 | noAssert : (Name, Bool) -> Maybe Name
387 | noAssert (n, True) = Nothing
388 | noAssert (n, False) = Just n
390 | notCovering : Defs -> Name -> Core Bool
392 | = case !(lookupCtxtExact n (gamma defs)) of
393 | Just def => case isCovering (totality def) of
394 | IsCovering => pure False
401 | match : Term vs -> Term vs -> Bool
402 | match (Local _ _ i _) _ = True
403 | match (Ref _ Bound n) _ = True
404 | match (Ref _ _ n) (Ref _ _ n') = n == n'
405 | match (App _ f a) (App _ f' a') = match f f' && match a a'
406 | match (As _ _ _ p) (As _ _ _ p') = match p p'
407 | match (As _ _ _ p) p' = match p p'
408 | match (TDelayed _ _ t) (TDelayed _ _ t') = match t t'
409 | match (TDelay _ _ _ t) (TDelay _ _ _ t') = match t t'
410 | match (TForce _ _ t) (TForce _ _ t') = match t t'
411 | match (PrimVal _ c) (PrimVal _ c') = c == c'
412 | match (Erased _ (Dotted t)) u = match t u
413 | match t (Erased _ (Dotted u)) = match t u
414 | match (Erased {}) _ = True
415 | match _ (Erased {}) = True
416 | match (TType {}) (TType {}) = True
420 | eraseApps : {auto c : Ref Ctxt Defs} ->
421 | Term vs -> Core (Term vs)
423 | = case getFnArgs tm of
424 | (Ref fc Bound n, args) =>
425 | do args' <- traverse eraseApps args
426 | pure (apply fc (Ref fc Bound n) args')
427 | (Ref fc nt n, args) =>
428 | do defs <- get Ctxt
429 | mgdef <- lookupCtxtExact n (gamma defs)
430 | let eargs = maybe NatSet.empty eraseArgs mgdef
431 | args' <- traverse eraseApps (NatSet.overwrite (Erased fc Placeholder) eargs args)
432 | pure (apply fc (Ref fc nt n) args')
434 | do args' <- traverse eraseApps args
435 | pure (apply (getLoc tm) tm args')
439 | clauseMatches : {vars : _} ->
440 | {auto c : Ref Ctxt Defs} ->
441 | (erase : Bool) -> Env Term vars -> Term vars ->
442 | ClosedTerm -> Core Bool
443 | clauseMatches erase env tm trylhs
444 | = do let lhs = close (getLoc tm) "cov" env tm
448 | pure $
match !(toResolvedNames lhs) !(toResolvedNames trylhs)
451 | checkMatched : {auto c : Ref Ctxt Defs} ->
452 | (erase : Bool) -> List Clause -> ClosedTerm -> Core (Maybe ClosedTerm)
453 | checkMatched erase cs ulhs
454 | = do logTerm "coverage" 5 "Checking coverage for" ulhs
455 | logC "coverage" 10 $
pure $
"(raw term: " ++ show !(toFullNames ulhs) ++ ")"
457 | then do ulhs <- eraseApps ulhs
458 | logTerm "coverage" 5 "Erased to" ulhs
461 | logC "coverage" 5 $
do
462 | cs <- traverse toFullNames cs
463 | pure $
"Against clauses:\n" ++
464 | (show $
indent 2 $
vcat $
map (pretty . show) cs)
467 | tryClauses : List Clause -> ClosedTerm -> Core (Maybe ClosedTerm)
469 | = do logTermNF "coverage" 10 "Nothing matches" Env.empty ulhs
471 | tryClauses (MkClause env lhs _ :: cs) ulhs
472 | = if !(clauseMatches erase env lhs ulhs)
473 | then do logTermNF "coverage" 10 "Yes" env lhs
475 | else do logTermNF "coverage" 10 "No match" env lhs