6 | import Core.Name.Scoped
7 | import Core.TT.Binder
8 | import Core.TT.Primitive
13 | import Libraries.Data.List.SizeOf
23 | data NameType : Type where
26 | DataCon : (tag : Int) -> (arity : Nat) -> NameType
27 | TyCon : (arity : Nat) -> NameType
34 | showPrec d Bound = "Bound"
35 | showPrec d Func = "Func"
36 | showPrec d (DataCon tag ar) = showCon d "DataCon" $
showArg tag ++ showArg ar
37 | showPrec d (TyCon ar) = showCon d "TyCon" $
showArg ar
40 | isCon : NameType -> Maybe Nat
41 | isCon (DataCon t a) = Just a
42 | isCon (TyCon a) = Just a
49 | data LazyReason = LInf | LLazy | LUnknown
56 | data UseSide = UseLeft | UseRight
67 | Show a => Show (WhyErased a) where
68 | show Placeholder = "placeholder"
69 | show Impossible = "impossible"
70 | show (Dotted x) = "dotted \{show x}"
75 | Functor WhyErased where
76 | map f Placeholder = Placeholder
77 | map f Impossible = Impossible
78 | map f (Dotted x) = Dotted (f x)
81 | Foldable WhyErased where
82 | foldr c n (Dotted x) = c x n
86 | Traversable WhyErased where
87 | traverse f Placeholder = pure Placeholder
88 | traverse f Impossible = pure Impossible
89 | traverse f (Dotted x) = Dotted <$> f x
96 | data Term : Scoped where
97 | Local : FC -> (isLet : Maybe Bool) ->
98 | (idx : Nat) -> (0 p : IsVar name idx vars) -> Term vars
99 | Ref : FC -> NameType -> (name : Name) -> Term vars
101 | Meta : FC -> Name -> Int -> List (Term vars) -> Term vars
102 | Bind : FC -> (x : Name) ->
103 | (b : Binder (Term vars)) ->
104 | (scope : Term (Scope.bind vars x)) -> Term vars
105 | App : FC -> (fn : Term vars) -> (arg : Term vars) -> Term vars
113 | As : FC -> UseSide -> (as : Term vars) -> (pat : Term vars) -> Term vars
115 | TDelayed : FC -> LazyReason -> Term vars -> Term vars
116 | TDelay : FC -> LazyReason -> (ty : Term vars) -> (arg : Term vars) -> Term vars
117 | TForce : FC -> LazyReason -> Term vars -> Term vars
118 | PrimVal : FC -> (c : Constant) -> Term vars
119 | Erased : FC -> WhyErased (Term vars) -> Term vars
120 | TType : FC -> Name ->
127 | ClosedTerm = Term []
133 | insertNames : GenWeakenable Term
134 | insertNames out ns (Local fc r idx prf)
135 | = let MkNVar prf' = insertNVarNames out ns (MkNVar prf) in
137 | insertNames out ns (Ref fc nt name) = Ref fc nt name
138 | insertNames out ns (Meta fc name idx args)
139 | = Meta fc name idx (map (insertNames out ns) args)
140 | insertNames out ns (Bind fc x b scope)
141 | = Bind fc x (assert_total (map (insertNames out ns) b))
142 | (insertNames (suc out) ns scope)
143 | insertNames out ns (App fc fn arg)
144 | = App fc (insertNames out ns fn) (insertNames out ns arg)
145 | insertNames out ns (As fc s as tm)
146 | = As fc s (insertNames out ns as) (insertNames out ns tm)
147 | insertNames out ns (TDelayed fc r ty) = TDelayed fc r (insertNames out ns ty)
148 | insertNames out ns (TDelay fc r ty tm)
149 | = TDelay fc r (insertNames out ns ty) (insertNames out ns tm)
150 | insertNames out ns (TForce fc r tm) = TForce fc r (insertNames out ns tm)
151 | insertNames out ns (PrimVal fc c) = PrimVal fc c
152 | insertNames out ns (Erased fc Impossible) = Erased fc Impossible
153 | insertNames out ns (Erased fc Placeholder) = Erased fc Placeholder
154 | insertNames out ns (Erased fc (Dotted t)) = Erased fc (Dotted (insertNames out ns t))
155 | insertNames out ns (TType fc u) = TType fc u
158 | compatTerm : CompatibleVars xs ys -> Term xs -> Term ys
159 | compatTerm compat tm = believe_me tm
185 | shrinkPi : Shrinkable (PiInfo . Term)
188 | $
traverse (\ t => shrinkTerm t th) pinfo
191 | shrinkBinder : Shrinkable (Binder . Term)
192 | shrinkBinder binder th
194 | $
traverse (\ t => shrinkTerm t th) binder
197 | shrinkTerms : Shrinkable (List . Term)
200 | $
traverse (\ t => shrinkTerm t th) ts
202 | shrinkTerm : Shrinkable Term
203 | shrinkTerm (Local fc r idx loc) prf
204 | = do MkVar loc' <- shrinkIsVar loc prf
205 | pure (Local fc r _ loc')
206 | shrinkTerm (Ref fc x name) prf = Just (Ref fc x name)
207 | shrinkTerm (Meta fc x y xs) prf
208 | = do Just (Meta fc x y !(shrinkTerms xs prf))
209 | shrinkTerm (Bind fc x b scope) prf
210 | = Just (Bind fc x !(shrinkBinder b prf) !(shrinkTerm scope (Keep prf)))
211 | shrinkTerm (App fc fn arg) prf
212 | = Just (App fc !(shrinkTerm fn prf) !(shrinkTerm arg prf))
213 | shrinkTerm (As fc s as tm) prf
214 | = Just (As fc s !(shrinkTerm as prf) !(shrinkTerm tm prf))
215 | shrinkTerm (TDelayed fc x y) prf
216 | = Just (TDelayed fc x !(shrinkTerm y prf))
217 | shrinkTerm (TDelay fc x t y) prf
218 | = Just (TDelay fc x !(shrinkTerm t prf) !(shrinkTerm y prf))
219 | shrinkTerm (TForce fc r x) prf
220 | = Just (TForce fc r !(shrinkTerm x prf))
221 | shrinkTerm (PrimVal fc c) prf = Just (PrimVal fc c)
222 | shrinkTerm (Erased fc Placeholder) prf = Just (Erased fc Placeholder)
223 | shrinkTerm (Erased fc Impossible) prf = Just (Erased fc Impossible)
224 | shrinkTerm (Erased fc (Dotted t)) prf = Erased fc . Dotted <$> shrinkTerm t prf
225 | shrinkTerm (TType fc u) prf = Just (TType fc u)
230 | thinPi : Thinnable (PiInfo . Term)
231 | thinPi pinfo th = assert_total $
map (\ t => thinTerm t th) pinfo
234 | thinBinder : Thinnable (Binder . Term)
235 | thinBinder binder th = assert_total $
map (\ t => thinTerm t th) binder
238 | thinTerms : Thinnable (List . Term)
239 | thinTerms ts th = assert_total $
map (\ t => thinTerm t th) ts
241 | thinTerm : Thinnable Term
242 | thinTerm (Local fc x idx y) th
243 | = let MkVar y' = thinIsVar y th in Local fc x _ y'
244 | thinTerm (Ref fc x name) th = Ref fc x name
245 | thinTerm (Meta fc x y xs) th
246 | = Meta fc x y (thinTerms xs th)
247 | thinTerm (Bind fc x b scope) th
248 | = Bind fc x (thinBinder b th) (thinTerm scope (Keep th))
249 | thinTerm (App fc fn arg) th
250 | = App fc (thinTerm fn th) (thinTerm arg th)
251 | thinTerm (As fc s nm pat) th
252 | = As fc s (thinTerm nm th) (thinTerm pat th)
253 | thinTerm (TDelayed fc x y) th = TDelayed fc x (thinTerm y th)
254 | thinTerm (TDelay fc x t y) th
255 | = TDelay fc x (thinTerm t th) (thinTerm y th)
256 | thinTerm (TForce fc r x) th = TForce fc r (thinTerm x th)
257 | thinTerm (PrimVal fc c) th = PrimVal fc c
258 | thinTerm (Erased fc Impossible) th = Erased fc Impossible
259 | thinTerm (Erased fc Placeholder) th = Erased fc Placeholder
260 | thinTerm (Erased fc (Dotted t)) th = Erased fc (Dotted (thinTerm t th))
261 | thinTerm (TType fc u) th = TType fc u
264 | GenWeaken Term where
265 | genWeakenNs = assert_total $
insertNames
269 | WeakenTerm : Weaken Term
270 | WeakenTerm = GenWeakenWeakens
273 | FreelyEmbeddable Term where
276 | IsScoped Term where
277 | shrink = shrinkTerm
279 | compatNs = compatTerm
285 | apply : FC -> Term vars -> List (Term vars) -> Term vars
286 | apply loc fn [] = fn
287 | apply loc fn (a :: args) = apply loc (App loc fn a) args
291 | applySpineWithFC : Term vars -> SnocList (FC, Term vars) -> Term vars
292 | applySpineWithFC fn [<] = fn
293 | applySpineWithFC fn (args :< (fc, arg)) = App fc (applySpineWithFC fn args) arg
297 | applyStackWithFC : Term vars -> List (FC, Term vars) -> Term vars
298 | applyStackWithFC fn [] = fn
299 | applyStackWithFC fn ((fc, arg) :: args) = applyStackWithFC (App fc fn arg) args
303 | fnType : FC -> Term vars -> Term vars -> Term vars
304 | fnType fc arg scope = Bind emptyFC (MN "_" 0) (Pi fc top Explicit arg) (weaken scope)
307 | linFnType : FC -> Term vars -> Term vars -> Term vars
308 | linFnType fc arg scope = Bind emptyFC (MN "_" 0) (Pi fc linear Explicit arg) (weaken scope)
311 | getFnArgs : Term vars -> (Term vars, List (Term vars))
312 | getFnArgs tm = getFA [] tm
314 | getFA : List (Term vars) -> Term vars ->
315 | (Term vars, List (Term vars))
316 | getFA args (App _ f a) = getFA (a :: args) f
317 | getFA args tm = (tm, args)
320 | getFnArgsWithFC : Term vars -> (Term vars, List (FC, Term vars))
321 | getFnArgsWithFC tm = getFA [] tm
323 | getFA : List (FC, Term vars) -> Term vars ->
324 | (Term vars, List (FC, Term vars))
325 | getFA args (App fc f a) = getFA ((fc, a) :: args) f
326 | getFA args tm = (tm, args)
329 | getFn : Term vars -> Term vars
330 | getFn (App _ f a) = getFn f
334 | getArgs : Term vars -> (List (Term vars))
335 | getArgs = snd . getFnArgs
345 | interface StripNamespace a where
346 | trimNS : Namespace -> a -> a
347 | restoreNS : Namespace -> a -> a
350 | StripNamespace Name where
351 | trimNS ns nm@(NS tns n)
352 | = if ns == tns then NS emptyNS n else nm
357 | restoreNS ns nm@(NS tns n)
358 | = if isNil (unsafeUnfoldNamespace tns)
361 | restoreNS ns nm = nm
364 | StripNamespace (Term vars) where
365 | trimNS ns (Ref fc x nm)
366 | = Ref fc x (trimNS ns nm)
367 | trimNS ns (Meta fc x y xs)
368 | = Meta fc x y (map (trimNS ns) xs)
369 | trimNS ns (Bind fc x b scope)
370 | = Bind fc x (map (trimNS ns) b) (trimNS ns scope)
371 | trimNS ns (App fc fn arg)
372 | = App fc (trimNS ns fn) (trimNS ns arg)
373 | trimNS ns (As fc s p tm)
374 | = As fc s (trimNS ns p) (trimNS ns tm)
375 | trimNS ns (TDelayed fc x y)
376 | = TDelayed fc x (trimNS ns y)
377 | trimNS ns (TDelay fc x t y)
378 | = TDelay fc x (trimNS ns t) (trimNS ns y)
379 | trimNS ns (TForce fc r y)
380 | = TForce fc r (trimNS ns y)
383 | restoreNS ns (Ref fc x nm)
384 | = Ref fc x (restoreNS ns nm)
385 | restoreNS ns (Meta fc x y xs)
386 | = Meta fc x y (map (restoreNS ns) xs)
387 | restoreNS ns (Bind fc x b scope)
388 | = Bind fc x (map (restoreNS ns) b) (restoreNS ns scope)
389 | restoreNS ns (App fc fn arg)
390 | = App fc (restoreNS ns fn) (restoreNS ns arg)
391 | restoreNS ns (As fc s p tm)
392 | = As fc s (restoreNS ns p) (restoreNS ns tm)
393 | restoreNS ns (TDelayed fc x y)
394 | = TDelayed fc x (restoreNS ns y)
395 | restoreNS ns (TDelay fc x t y)
396 | = TDelay fc x (restoreNS ns t) (restoreNS ns y)
397 | restoreNS ns (TForce fc r y)
398 | = TForce fc r (restoreNS ns y)
399 | restoreNS ns tm = tm
403 | isErased : Term vars -> Bool
404 | isErased (Erased {}) = True
408 | getLoc : Term vars -> FC
409 | getLoc (Local fc _ _ _) = fc
410 | getLoc (Ref fc _ _) = fc
411 | getLoc (Meta fc _ _ _) = fc
412 | getLoc (Bind fc _ _ _) = fc
413 | getLoc (App fc _ _) = fc
414 | getLoc (As fc _ _ _) = fc
415 | getLoc (TDelayed fc _ _) = fc
416 | getLoc (TDelay fc _ _ _) = fc
417 | getLoc (TForce fc _ _) = fc
418 | getLoc (PrimVal fc _) = fc
419 | getLoc (Erased fc i) = fc
420 | getLoc (TType fc _) = fc
423 | Eq LazyReason where
424 | (==) LInf LInf = True
425 | (==) LLazy LLazy = True
426 | (==) LUnknown LUnknown = True
430 | Show LazyReason where
432 | show LLazy = "Lazy"
433 | show LUnknown = "Unkown"
436 | compatible : LazyReason -> LazyReason -> Bool
437 | compatible LUnknown _ = True
438 | compatible _ LUnknown = True
439 | compatible x y = x == y
443 | Eq a => Eq (WhyErased a) where
444 | Placeholder == Placeholder = True
445 | Impossible == Impossible = True
446 | Dotted t == Dotted u = t == u
450 | eqWhyErasedBy : (a -> b -> Bool) -> WhyErased a -> WhyErased b -> Bool
451 | eqWhyErasedBy eq Impossible Impossible = True
452 | eqWhyErasedBy eq Placeholder Placeholder = True
453 | eqWhyErasedBy eq (Dotted t) (Dotted u) = eq t u
454 | eqWhyErasedBy eq _ _ = False
458 | eqTerm : Term vs -> Term vs' -> Bool
459 | eqTerm (Local _ _ idx _) (Local _ _ idx' _) = idx == idx'
460 | eqTerm (Ref _ _ n) (Ref _ _ n') = n == n'
461 | eqTerm (Meta _ _ i args) (Meta _ _ i' args')
462 | = i == i' && assert_total (all (uncurry eqTerm) (zip args args'))
463 | eqTerm (Bind _ _ b sc) (Bind _ _ b' sc')
464 | = assert_total (eqBinderBy eqTerm b b') && eqTerm sc sc'
465 | eqTerm (App _ f a) (App _ f' a') = eqTerm f f' && eqTerm a a'
466 | eqTerm (As _ _ a p) (As _ _ a' p') = eqTerm a a' && eqTerm p p'
467 | eqTerm (TDelayed _ _ t) (TDelayed _ _ t') = eqTerm t t'
468 | eqTerm (TDelay _ _ t x) (TDelay _ _ t' x') = eqTerm t t' && eqTerm x x'
469 | eqTerm (TForce _ _ t) (TForce _ _ t') = eqTerm t t'
470 | eqTerm (PrimVal _ c) (PrimVal _ c') = c == c'
471 | eqTerm (Erased _ i) (Erased _ i') = assert_total (eqWhyErasedBy eqTerm i i')
472 | eqTerm (TType {}) (TType {}) = True
477 | Eq (Term vars) where
485 | resolveNamesBinder : (vars : Scope) -> Binder (Term vars) -> Binder (Term vars)
486 | resolveNamesBinder vars b = assert_total $
map (resolveNames vars) b
488 | resolveNamesTerms : (vars : Scope) -> List (Term vars) -> List (Term vars)
489 | resolveNamesTerms vars ts = assert_total $
map (resolveNames vars) ts
493 | resolveNames : (vars : Scope) -> Term vars -> Term vars
494 | resolveNames vars (Ref fc Bound name)
495 | = case isNVar name vars of
496 | Just (MkNVar prf) => Local fc (Just False) _ prf
497 | _ => Ref fc Bound name
498 | resolveNames vars (Meta fc n i xs)
499 | = Meta fc n i (resolveNamesTerms vars xs)
500 | resolveNames vars (Bind fc x b scope)
501 | = Bind fc x (resolveNamesBinder vars b) (resolveNames (x :: vars) scope)
502 | resolveNames vars (App fc fn arg)
503 | = App fc (resolveNames vars fn) (resolveNames vars arg)
504 | resolveNames vars (As fc s as pat)
505 | = As fc s (resolveNames vars as) (resolveNames vars pat)
506 | resolveNames vars (TDelayed fc x y)
507 | = TDelayed fc x (resolveNames vars y)
508 | resolveNames vars (TDelay fc x t y)
509 | = TDelay fc x (resolveNames vars t) (resolveNames vars y)
510 | resolveNames vars (TForce fc r x)
511 | = TForce fc r (resolveNames vars x)
512 | resolveNames vars tm = tm
518 | withPiInfo : Show t => PiInfo t -> String -> String
519 | withPiInfo Explicit tm = "(" ++ tm ++ ")"
520 | withPiInfo Implicit tm = "{" ++ tm ++ "}"
521 | withPiInfo AutoImplicit tm = "{auto " ++ tm ++ "}"
522 | withPiInfo (DefImplicit t) tm = "{default " ++ show t ++ " " ++ tm ++ "}"
526 | {vars : _} -> Show (Term vars) where
527 | show tm = let (fn, args) = getFnArgs tm in showApp fn args
529 | showApp : {vars : _} -> Term vars -> List (Term vars) -> String
530 | showApp (Local _ c idx p) []
531 | = show (nameAt p) ++ "[" ++ show idx ++ "]"
533 | showApp (Ref _ _ n) [] = show n
534 | showApp (Meta _ n _ args) []
535 | = "?" ++ show n ++ "_" ++ show args
536 | showApp (Bind _ x (Lam _ c info ty) sc) []
537 | = "\\" ++ withPiInfo info (showCount c ++ show x ++ " : " ++ show ty) ++
539 | showApp (Bind _ x (Let _ c val ty) sc) []
540 | = "let " ++ showCount c ++ show x ++ " : " ++ show ty ++
541 | " = " ++ show val ++ " in " ++ show sc
542 | showApp (Bind _ x (Pi _ c info ty) sc) []
543 | = withPiInfo info (showCount c ++ show x ++ " : " ++ show ty) ++
545 | showApp (Bind _ x (PVar _ c info ty) sc) []
546 | = withPiInfo info ("pat " ++ showCount c ++ show x ++ " : " ++ show ty) ++
548 | showApp (Bind _ x (PLet _ c val ty) sc) []
549 | = "plet " ++ showCount c ++ show x ++ " : " ++ show ty ++
550 | " = " ++ show val ++ " in " ++ show sc
551 | showApp (Bind _ x (PVTy _ c ty) sc) []
552 | = "pty " ++ showCount c ++ show x ++ " : " ++ show ty ++
554 | showApp (App {}) [] = "[can't happen]"
555 | showApp (As _ _ n tm) [] = show n ++ "@" ++ show tm
556 | showApp (TDelayed _ _ tm) [] = "%Delayed " ++ show tm
557 | showApp (TDelay _ _ _ tm) [] = "%Delay " ++ show tm
558 | showApp (TForce _ _ tm) [] = "%Force " ++ show tm
559 | showApp (PrimVal _ c) [] = show c
560 | showApp (Erased _ (Dotted t)) [] = ".(" ++ show t ++ ")"
561 | showApp (Erased {}) [] = "[__]"
562 | showApp (TType _ u) [] = "Type"
563 | showApp _ [] = "???"
564 | showApp f args = "(" ++ assert_total (show f) ++ " " ++
565 | assert_total (showSep " " (map show args))