0 | module TTImp.Impossible
  1 |
  2 | import Core.Env
  3 | import Core.Value
  4 |
  5 | import TTImp.TTImp
  6 | import TTImp.TTImp.Functor
  7 | import TTImp.Elab.App
  8 |
  9 | import Idris.Syntax
 10 | import Idris.Resugar
 11 |
 12 | %default covering
 13 |
 14 | -- This file contains support for building a guess at the term on the LHS of an
 15 | -- 'impossible' case, in order to help build a tree of covered cases for
 16 | -- coverage checking. Since the LHS by definition won't be well typed, we are
 17 | -- only guessing! But we can still do some type-directed disambiguation of
 18 | -- names.
 19 | -- Constants (fromInteger/fromString etc) won't be supported, because in general
 20 | -- they involve resolving interfaces - they'll just become unmatchable patterns.
 21 |
 22 | match : {auto c : Ref Ctxt Defs} ->
 23 |         ClosedNF -> (Name, Int, ClosedTerm) -> Core Bool
 24 | match nty (n, i, rty)
 25 |     = do defs <- get Ctxt
 26 |          rtynf <- nf defs Env.empty rty
 27 |          sameRet nty rtynf
 28 |   where
 29 |     sameRet : ClosedNF -> ClosedNF -> Core Bool
 30 |     sameRet _ (NApp {}) = pure True
 31 |     sameRet _ (NErased {}) = pure True
 32 |     sameRet (NApp {}) _ = pure True
 33 |     sameRet (NErased {}) _ = pure True
 34 |     sameRet (NTCon _ n _ _) (NTCon _ n' _ _) = pure (n == n')
 35 |     sameRet (NPrimVal _ c) (NPrimVal _ c') = pure (c == c')
 36 |     sameRet (NType {}) (NType {}) = pure True
 37 |     sameRet nf (NBind fc _ (Pi {}) sc)
 38 |         = do defs <- get Ctxt
 39 |              sc' <- sc defs (toClosure defaultOpts Env.empty (Erased fc Placeholder))
 40 |              sameRet nf sc'
 41 |     sameRet _ _ = pure False
 42 |
 43 | dropNoMatch : {auto c : Ref Ctxt Defs} ->
 44 |               Maybe ClosedNF -> List (Name, Int, GlobalDef) ->
 45 |               Core (List (Name, Int, GlobalDef))
 46 | dropNoMatch Nothing ts = pure ts
 47 | dropNoMatch (Just nty) ts
 48 |     = -- if the return type of a thing in ts doesn't match nty, drop it
 49 |       filterM (match nty . map (map type)) ts
 50 |
 51 | nextVar : {auto q : Ref QVar Int} ->
 52 |           FC -> Core ClosedTerm
 53 | nextVar fc
 54 |     = do i <- get QVar
 55 |          put QVar (i + 1)
 56 |          pure (Ref fc Bound (MN "imp" i))
 57 |
 58 | badClause : {auto c : Ref Ctxt Defs} ->
 59 |             ClosedTerm ->
 60 |             List (WithFC RawImp) ->
 61 |             List (WithFC RawImp) ->
 62 |             List (Name, WithFC RawImp) ->
 63 |             Core a
 64 | badClause fn exps autos named
 65 |    = throw (GenericMsg (getLoc fn)
 66 |             ("Badly formed impossible clause "
 67 |                ++ show (!(toFullNames fn),
 68 |                         (.val) <$> exps,
 69 |                         (.val) <$> autos,
 70 |                         mapSnd (.val) <$> named)))
 71 |
 72 | mutual
 73 |   processArgs : {auto c : Ref Ctxt Defs} ->
 74 |                 {auto s : Ref Syn SyntaxInfo} ->
 75 |                 {auto q : Ref QVar Int} ->
 76 |                 Bool -> -- should be fully applied
 77 |                 ClosedTerm -> ClosedNF ->
 78 |                 (expargs : List (WithFC RawImp)) ->
 79 |                 (autoargs : List (WithFC RawImp)) ->
 80 |                 (namedargs : List (Name, WithFC RawImp)) ->
 81 |                 Core ClosedTerm
 82 |   -- unnamed takes priority
 83 |   processArgs con fn (NBind _ x (Pi _ _ Explicit ty) sc) (e :: exps) autos named
 84 |      = do e' <- mkTerm e.val (Just ty)
 85 |           defs <- get Ctxt
 86 |           processArgs con (App e.fc fn e')
 87 |                       !(sc defs (toClosure defaultOpts Env.empty e'))
 88 |                       exps autos named
 89 |   processArgs con fn (NBind _ x (Pi _ _ Explicit ty) sc) [] autos named
 90 |      = do defs <- get Ctxt
 91 |           case findNamed x named of
 92 |             Just ((_, e), named') =>
 93 |                do e' <- mkTerm e.val (Just ty)
 94 |                   processArgs con (App e.fc fn e')
 95 |                               !(sc defs (toClosure defaultOpts Env.empty e'))
 96 |                               [] autos named'
 97 |             Nothing =>
 98 |               case findBindAllExpPattern named of
 99 |                 Just e => -- Found a bind-all pattern: {}
100 |                   do e' <- mkTerm e.val (Just ty)
101 |                      processArgs con (App e.fc fn e')
102 |                                  !(sc defs (toClosure defaultOpts Env.empty e'))
103 |                                  [] autos named
104 |                 Nothing => -- Expected an explicit argument, but only implicits left
105 |                        do let False = con
106 |                             | True => throw $ GenericMsg (getLoc fn) $
107 |                                                 "Cannot match on a partially applied constructor: "
108 |                                                 ++ show !(toFullNames fn)
109 |                           let True = null autos && null (filterBindAllExpPattern named)
110 |                             | False => badClause fn [] autos named -- unexpected arguments
111 |                           pure fn
112 |   processArgs con fn (NBind _ x (Pi _ _ Implicit ty) sc) exps autos named
113 |      = do defs <- get Ctxt
114 |           case findNamed x named of
115 |             Nothing => do let fc = getLoc fn
116 |                           e' <- nextVar fc
117 |                           processArgs con (App fc fn e')
118 |                                       !(sc defs (toClosure defaultOpts Env.empty e'))
119 |                                       exps autos named
120 |             Just ((_, e), named') =>
121 |                do e' <- mkTerm e.val (Just ty)
122 |                   processArgs con (App e.fc fn e')
123 |                               !(sc defs (toClosure defaultOpts Env.empty e'))
124 |                               exps autos named'
125 |   processArgs con fn (NBind _ x (Pi _ _ AutoImplicit ty) sc) exps autos named
126 |      = do defs <- get Ctxt
127 |           case autos of
128 |                (e :: autos') => -- unnamed takes priority
129 |                    do e' <- mkTerm e.val (Just ty)
130 |                       processArgs con (App e.fc fn e')
131 |                                   !(sc defs (toClosure defaultOpts Env.empty e'))
132 |                                   exps autos' named
133 |                [] =>
134 |                   case findNamed x named of
135 |                      Nothing =>
136 |                         do let fc = getLoc fn
137 |                            e' <- nextVar fc
138 |                            processArgs con (App fc fn e')
139 |                                        !(sc defs (toClosure defaultOpts Env.empty e'))
140 |                                        exps [] named
141 |                      Just ((_, e), named') =>
142 |                         do e' <- mkTerm e.val (Just ty)
143 |                            processArgs con (App e.fc fn e')
144 |                                        !(sc defs (toClosure defaultOpts Env.empty e'))
145 |                                        exps [] named'
146 |   processArgs _ fn _ (x :: _) autos named
147 |      = throw $ GenericMsg x.fc "Too many arguments"
148 |   processArgs _ fn _ exps autos named
149 |      = if null exps && null autos && null (filterBindAllExpPattern named)
150 |           then pure fn
151 |           else badClause fn exps autos named
152 |
153 |   buildApp : {auto c : Ref Ctxt Defs} ->
154 |              {auto s : Ref Syn SyntaxInfo} ->
155 |              {auto q : Ref QVar Int} ->
156 |              FC -> Name -> Maybe ClosedClosure ->
157 |              (expargs : List (WithFC RawImp)) ->
158 |              (autoargs : List (WithFC RawImp)) ->
159 |              (namedargs : List (Name, WithFC RawImp)) ->
160 |              Core ClosedTerm
161 |   buildApp fc n mty exps autos named
162 |       = do defs <- get Ctxt
163 |            prims <- getPrimitiveNames
164 |            when (n `elem` prims) $
165 |                throw (GenericMsg fc "Can't deal with \{show n} in impossible clauses yet")
166 |
167 |            gdefs <- lookupNameBy id n (gamma defs)
168 |            mty' <- traverseOpt (evalClosure defs) mty
169 |            [(n', i, gdef)] <- dropNoMatch mty' gdefs
170 |               | [] => if length gdefs == 0
171 |                         then undefinedName fc n
172 |                         else throw $ GenericMsg fc "\{show n} does not match expected type"
173 |               | ts => throw $ AmbiguousName fc (map fst ts)
174 |            tynf <- nf defs Env.empty (type gdef)
175 |            -- #899 we need to make sure that type & data constructors are marked
176 |            -- as such so that the coverage checker actually uses the matches in
177 |            -- `impossible` branches to generate parts of the case tree.
178 |            -- When `head` is `Func`, the pattern will be marked as forced and
179 |            -- the coverage checker will considers that all the cases have been
180 |            -- covered!
181 |            let nameType = getDefNameType gdef
182 |            processArgs (isJust $ isCon nameType)
183 |                        (Ref fc nameType (Resolved i))
184 |                        tynf exps autos named
185 |
186 |   mkTerm : {auto c : Ref Ctxt Defs} ->
187 |            {auto s : Ref Syn SyntaxInfo} ->
188 |            {auto q : Ref QVar Int} ->
189 |            RawImp -> Maybe ClosedClosure ->
190 |            Core ClosedTerm
191 |   mkTerm tm mty = go tm [] [] []
192 |     where
193 |       go : RawImp ->
194 |           (expargs : List (WithFC RawImp)) ->
195 |           (autoargs : List (WithFC RawImp)) ->
196 |           (namedargs : List (Name, WithFC RawImp)) ->
197 |           Core ClosedTerm
198 |       go (IVar fc n) exps autos named
199 |         = buildApp fc n mty exps autos named
200 |       go (IAs fc fc' u n pat) exps autos named
201 |         = go pat exps autos named
202 |       go (IApp fc fn arg) exps autos named
203 |         = go fn (MkFCVal fc arg :: exps) autos named
204 |       go (IWithApp fc fn arg) exps autos named
205 |         = go fn (MkFCVal fc arg :: exps) autos named
206 |       go (IAutoApp fc fn arg) exps autos named
207 |         = go fn exps (MkFCVal fc arg :: autos) named
208 |       go (INamedApp fc fn nm arg) exps autos named
209 |         = go fn exps autos ((nm, MkFCVal fc arg) :: named)
210 |       go (IMustUnify fc r tm) exps autos named
211 |         = Erased fc . Dotted <$> go tm exps autos named
212 |       go (IPrimVal fc c) _ _ _
213 |           = do let tm = PrimVal fc c
214 |                True <- isValidPrimType
215 |                  | _ => throw $ GenericMsg fc "\{show tm} does not match expected type"
216 |                pure tm
217 |         where
218 |           isValidPrimType : Core Bool
219 |           isValidPrimType
220 |             = do defs <- get Ctxt
221 |                  Just ty <- traverseOpt (evalClosure defs) mty
222 |                    | _ => pure False
223 |                  case (primType c, ty) of
224 |                       (Nothing, NType {}) => pure True
225 |                       (Just t1, NPrimVal _ (PrT t2)) => pure (t1 == t2)
226 |                       _ => pure False
227 |       go (IType fc) _ _ _
228 |           = do defs <- get Ctxt
229 |                Just (NType {}) <- traverseOpt (evalClosure defs) mty
230 |                  | _ => throw $ GenericMsg fc "Type does not match expected type"
231 |                pure (TType fc $ MN "top" 0)
232 |       -- We're taking UniqueDefault here, _and_ we're falling through to error otherwise, which is sketchy.
233 |       -- One option is to try each and emit an AmbiguousElab? We maybe should respect `UniqueDefault` if there
234 |       -- is no evidence (mty), but we should _try_ to resolve here if there is an mty.
235 |       go (IAlternative _ (UniqueDefault tm) _) exps autos named
236 |         = go tm exps autos named
237 |       go (Implicit fc _) _ _ _ = nextVar fc
238 |       go (IBindVar fc _) _ _ _ = nextVar fc
239 |       go tm _ _ _
240 |         = do tm' <- pterm (map defaultKindedName tm) -- hack
241 |              throw $ GenericMsg (getFC tm) "Unsupported term in impossible clause: \{show tm'}"
242 |
243 | -- Given an LHS that is declared 'impossible', build a term to match from,
244 | -- so that when we build the case tree for checking coverage, we take into
245 | -- account the impossible clauses
246 | export
247 | getImpossibleTerm : {vars : _} ->
248 |                     {auto c : Ref Ctxt Defs} ->
249 |                     {auto s : Ref Syn SyntaxInfo} ->
250 |                     Env Term vars -> NestedNames vars -> RawImp -> Core ClosedTerm
251 | getImpossibleTerm env nest tm
252 |     = do q <- newRef QVar (the Int 0)
253 |          mkTerm (applyEnv tm) Nothing
254 |   where
255 |     addEnv : {vars : _} ->
256 |              FC -> Env Term vars -> List RawImp
257 |     addEnv fc [] = []
258 |     addEnv fc (b :: env) =
259 |        if isLet b
260 |           then addEnv fc env
261 |           else Implicit fc False :: addEnv fc env
262 |
263 |     expandNest : RawImp -> RawImp
264 |     expandNest (IVar fc n)
265 |         = case lookup n (names nest) of
266 |                Just (Just n', _, _) => IVar fc n'
267 |                _ => IVar fc n
268 |     expandNest tm = tm
269 |
270 |     -- Need to apply the function to the surrounding environment, and update
271 |     -- the name to the proper one from the nested names map
272 |     applyEnv : RawImp -> RawImp
273 |     applyEnv (IApp fc fn arg) = IApp fc (applyEnv fn) arg
274 |     applyEnv (IWithApp fc fn arg) = IWithApp fc (applyEnv fn) arg
275 |     applyEnv (IAutoApp fc fn arg) = IAutoApp fc (applyEnv fn) arg
276 |     applyEnv (INamedApp fc fn n arg)
277 |         = INamedApp fc (applyEnv fn) n arg
278 |     applyEnv tm = apply (expandNest tm) (addEnv (getFC tm) env)
279 |