7 | import Core.Name.Scoped
9 | import Libraries.Data.SnocList.HasLength
10 | import Libraries.Data.SnocList.SizeOf
12 | import Data.List.HasLength
15 | import Libraries.Data.List.SizeOf
17 | import Libraries.Data.Erased
31 | data IsVar : a -> Nat -> List a -> Type where
32 | First : IsVar n Z (n :: ns)
33 | Later : IsVar n i ns -> IsVar n (S i) (m :: ns)
39 | 0 Last : HasLength (S n) vs -> Exists (\ nm => IsVar nm n vs)
40 | Last {vs = .(_)} (S Z) = Evidence _ First
41 | Last {vs = .(_)} (S (S p)) = bimap id Later (Last (S p))
44 | finIdx : {idx : _} -> (0 prf : IsVar x idx vars) ->
47 | finIdx (Later l) = FS (finIdx l)
52 | nameAt : {vars : List a} -> {idx : Nat} -> (0 p : IsVar n idx vars) -> a
53 | nameAt {vars = n :: _} First = n
54 | nameAt (Later p) = nameAt p
58 | dropLater : IsVar nm (S idx) (n :: ns) -> IsVar nm idx ns
59 | dropLater (Later p) = p
62 | 0 mkIsVar : HasLength m inner -> IsVar nm m (inner ++ nm :: outer)
64 | mkIsVar (S x) = Later (mkIsVar x)
67 | 0 mkIsVarChiply : HasLength m inner -> IsVar nm m (inner <>> nm :: outer)
69 | = rewrite chipsAsListAppend inner (nm :: outer) in
70 | rewrite sym $
plusZeroRightNeutral m in
71 | mkIsVar (hlChips hl Z)
77 | {idx : Nat} -> (0 p : IsVar name idx ns) ->
79 | dropIsVar (_ :: xs) First = xs
80 | dropIsVar (n :: xs) (Later p) = n :: dropIsVar xs p
86 | 0 embedIsVar : IsVar x idx xs -> IsVar x idx (xs ++ outer)
87 | embedIsVar First = First
88 | embedIsVar (Later p) = Later (embedIsVar p)
93 | 0 weakenIsVar : (s : SizeOf ns) -> IsVar x idx xs -> IsVar x (size s + idx) (ns ++ xs)
94 | weakenIsVar (MkSizeOf Z Z) p = p
95 | weakenIsVar (MkSizeOf (S k) (S l)) p = Later (weakenIsVar (MkSizeOf k l) p)
98 | (s : SizeOf local) ->
99 | So (idx < size s) ->
100 | IsVar x idx (local ++ outer) ->
102 | locateIsVarLT (MkSizeOf Z Z) so v = case v of
105 | locateIsVarLT (MkSizeOf (S k) (S l)) so v = case v of
107 | Later v => Later (locateIsVarLT (MkSizeOf k l) so v)
110 | (s : SizeOf local) ->
111 | So (idx >= size s) ->
112 | IsVar x idx (local ++ outer) ->
113 | IsVar x (idx `minus` size s) outer
114 | locateIsVarGE (MkSizeOf Z Z) so v = rewrite minusZeroRight idx in v
115 | locateIsVarGE (MkSizeOf (S k) (S l)) so v = case v of
116 | Later v => locateIsVarGE (MkSizeOf k l) so v
119 | locateIsVar : {idx : Nat} -> (s : SizeOf local) ->
120 | (0 p : IsVar x idx (local ++ outer)) ->
121 | Either (Erased (IsVar x idx local))
122 | (Erased (IsVar x (idx `minus` size s) outer))
123 | locateIsVar s p = case choose (idx < size s) of
124 | Left so => Left (MkErased (locateIsVarLT s so p))
125 | Right so => Right (MkErased (locateIsVarGE s so p))
134 | record Var {0 a : Type} (vars : List a) where
138 | 0 varPrf : IsVar varNm varIdx vars
143 | first : Var (n :: ns)
144 | first = MkVar First
147 | later : Var ns -> Var (n :: ns)
148 | later (MkVar p) = MkVar (Later p)
151 | isLater : Var (n :: vs) -> Maybe (Var vs)
152 | isLater (MkVar First) = Nothing
153 | isLater (MkVar (Later p)) = Just (MkVar p)
156 | last : SizeOf vs -> Maybe (Var vs)
157 | last (MkSizeOf Z p) = Nothing
158 | last (MkSizeOf (S n) p) = Just (MkVar (snd $
Last p))
161 | mkVar : SizeOf inner -> Var (inner ++ nm :: outer)
162 | mkVar (MkSizeOf s p) = MkVar (mkIsVar p)
165 | mkVarChiply : SizeOf inner -> Var (inner <>> nm :: outer)
166 | mkVarChiply (MkSizeOf s p) = MkVar (mkIsVarChiply p)
170 | allVars : (vars : Scope) -> List (Var vars)
171 | allVars = go [<] where
173 | go : SizeOf local -> (vs : Scope) -> List (Var (local <>> vs))
175 | go s (v :: vs) = mkVarChiply s :: go (s :< v) vs
179 | v == w = varIdx v == varIdx w
182 | Show (Var ns) where
183 | show v = show (varIdx v)
189 | record NVar {0 a : Type} (nm : a) (vars : List a) where
192 | 0 nvarPrf : IsVar nm nvarIdx vars
197 | first : NVar n (n :: ns)
198 | first = MkNVar First
201 | later : NVar nm ns -> NVar nm (n :: ns)
202 | later (MkNVar p) = MkNVar (Later p)
205 | isLater : NVar nm (n :: ns) -> Maybe (NVar nm ns)
206 | isLater (MkNVar First) = Nothing
207 | isLater (MkNVar (Later p)) = Just (MkNVar p)
210 | forgetName : NVar nm vars -> Var vars
211 | forgetName (MkNVar p) = MkVar p
214 | recoverName : (v : Var vars) -> NVar (varNm v) vars
215 | recoverName (MkVar p) = MkNVar p
218 | mkNVar : SizeOf inner -> NVar nm (inner ++ nm :: outer)
219 | mkNVar (MkSizeOf s p) = MkNVar (mkIsVar p)
222 | mkNVarChiply : SizeOf inner -> NVar nm (inner <>> nm :: outer)
223 | mkNVarChiply (MkSizeOf s p) = MkNVar (mkIsVarChiply p)
226 | locateNVar : SizeOf local -> NVar nm (local ++ outer) ->
227 | Either (NVar nm local) (NVar nm outer)
228 | locateNVar s (MkNVar p) = case locateIsVar s p of
229 | Left p => Left (MkNVar (runErased p))
230 | Right p => Right (MkNVar (runErased p))
233 | dropNVar : {ns : List a} -> NVar nm ns -> List a
234 | dropNVar (MkNVar p) = dropIsVar ns p
240 | isDeBruijn : Nat -> (vars : List Name) -> Maybe (Var vars)
241 | isDeBruijn Z (_ :: _) = pure first
242 | isDeBruijn (S k) (_ :: vs) = later <$> isDeBruijn k vs
243 | isDeBruijn _ _ = Nothing
246 | isNVar : (n : Name) -> (ns : List Name) -> Maybe (NVar n ns)
247 | isNVar n [] = Nothing
249 | = case nameEq n m of
250 | Nothing => map later (isNVar n ms)
251 | Just Refl => pure (MkNVar First)
254 | isVar : (n : Name) -> (ns : List Name) -> Maybe (Var ns)
255 | isVar n ns = forgetName <$> isNVar n ns
258 | locateVar : SizeOf local -> Var (local ++ outer) ->
259 | Either (Var local) (Var outer)
260 | locateVar s v = bimap forgetName forgetName
261 | $
locateNVar s (recoverName v)
267 | weakenNVar : SizeOf ns -> NVar name outer -> NVar name (ns ++ outer)
268 | weakenNVar s (MkNVar {nvarIdx} p)
269 | = MkNVar {nvarIdx = plus (size s) nvarIdx} (weakenIsVar s p)
272 | embedNVar : NVar name ns -> NVar name (ns ++ outer)
273 | embedNVar (MkNVar p) = MkNVar (embedIsVar p)
276 | insertNVar : SizeOf local ->
277 | NVar nm (local ++ outer) ->
278 | NVar nm (local ++ n :: outer)
279 | insertNVar p v = case locateNVar p v of
280 | Left v => embedNVar v
281 | Right v => weakenNVar p (later v)
284 | insertNVarChiply : SizeOf local ->
285 | NVar nm (local <>> outer) ->
286 | NVar nm (local <>> n :: outer)
287 | insertNVarChiply p v
288 | = rewrite chipsAsListAppend local (n :: outer) in
289 | insertNVar (p <>> zero)
290 | $
replace {p = NVar nm} (chipsAsListAppend local outer) v
293 | insertNVarNames : GenWeakenable (NVar name)
294 | insertNVarNames p q v = case locateNVar p v of
295 | Left v => embedNVar v
297 | rewrite appendAssociative local ns outer in
298 | weakenNVar (p + q) v
302 | removeNVar : SizeOf local ->
303 | NVar nm (local ++ n :: outer) ->
304 | Maybe (NVar nm (local ++ outer))
305 | removeNVar s var = case locateNVar s var of
306 | Left v => pure (embedNVar v)
307 | Right v => weakenNVar s <$> isLater v
310 | insertVar : SizeOf local ->
311 | Var (local ++ outer) ->
312 | Var (local ++ n :: outer)
313 | insertVar p v = forgetName $
insertNVar p (recoverName v)
315 | weakenVar : SizeOf ns -> Var outer -> Var (ns ++ outer)
316 | weakenVar p v = forgetName $
weakenNVar p (recoverName v)
318 | insertVarNames : GenWeakenable Var
319 | insertVarNames p q v = forgetName $
insertNVarNames p q (recoverName v)
323 | removeVar : SizeOf local ->
324 | Var (local ++ n :: outer) ->
325 | Maybe (Var (local ++ outer))
326 | removeVar s var = forgetName <$> removeNVar s (recoverName var)
332 | strengthenIsVar : {n : Nat} -> (s : SizeOf inner) ->
333 | (0 p : IsVar x n (inner ++ vars)) ->
334 | Maybe (Erased (IsVar x (n `minus` size s) vars))
335 | strengthenIsVar s p = case locateIsVar s p of
339 | strengthenVar : SizeOf inner ->
340 | Var (inner ++ vars) -> Maybe (Var vars)
341 | strengthenVar s (MkVar p)
342 | = do MkErased p <- strengthenIsVar s p
345 | strengthenNVar : SizeOf inner ->
346 | NVar x (inner ++ vars) -> Maybe (NVar x vars)
347 | strengthenNVar s (MkNVar p)
348 | = do MkErased p <- strengthenIsVar s p
355 | CompatibleVars xs ys ->
357 | (0 p : IsVar {a} name idx xs) ->
359 | lookup Pre p = name
360 | lookup (Ext {m} x) First = m
361 | lookup (Ext x) (Later p) = lookup x p
364 | (ns : CompatibleVars xs ys) ->
365 | {idx : Nat} -> (0 p : IsVar name idx xs) ->
366 | IsVar (lookup ns p) idx ys
367 | compatIsVar Pre p = p
368 | compatIsVar (Ext {n} x) First = First
369 | compatIsVar (Ext {n} x) (Later p) = Later (compatIsVar x p)
371 | compatVar : CompatibleVars xs ys -> Var xs -> Var ys
372 | compatVar prf (MkVar p) = MkVar (compatIsVar prf p)
378 | thinIsVar : {idx : Nat} -> (0 p : IsVar name idx xs) ->
379 | Thin xs ys -> Var ys
380 | thinIsVar p Refl = MkVar p
381 | thinIsVar p (Drop th) = later (thinIsVar p th)
382 | thinIsVar First (Keep th) = first
383 | thinIsVar (Later p) (Keep th) = later (thinIsVar p th)
386 | shrinkIsVar : {idx : Nat} -> (0 p : IsVar name idx xs) ->
387 | Thin ys xs -> Maybe (Var ys)
388 | shrinkIsVar prf Refl = Just (MkVar prf)
389 | shrinkIsVar First (Drop p) = Nothing
390 | shrinkIsVar (Later x) (Drop p) = shrinkIsVar x p
391 | shrinkIsVar First (Keep p) = Just first
392 | shrinkIsVar (Later x) (Keep p) = later <$> shrinkIsVar x p
399 | 0 FreelyEmbeddableIsVar : FreelyEmbeddable (IsVar x k)
400 | FreelyEmbeddableIsVar = MkFreelyEmbeddable embedIsVar
403 | GenWeaken (Var {a = Name}) where
404 | genWeakenNs = insertVarNames
408 | WeakenVar : Weaken (Var {a = Name})
409 | WeakenVar = GenWeakenWeakens
412 | Strengthen (Var {a = Name}) where
413 | strengthenNs = strengthenVar
416 | FreelyEmbeddable (Var {a = Name}) where
417 | embed (MkVar p) = MkVar (embedIsVar p)
420 | IsScoped (Var {a = Name}) where
421 | compatNs = compatVar
423 | thin (MkVar p) = thinIsVar p
424 | shrink (MkVar p) = shrinkIsVar p
427 | GenWeaken (NVar {a = Name} nm) where
428 | genWeakenNs = insertNVarNames
432 | WeakenNVar : Weaken (NVar {a = Name} nm)
433 | WeakenNVar = GenWeakenWeakens
436 | Strengthen (NVar {a = Name} nm) where
437 | strengthenNs = strengthenNVar
440 | FreelyEmbeddable (NVar {a = Name} nm) where
441 | embed (MkNVar p) = MkNVar (embedIsVar p)
448 | shiftUnderNs : SizeOf {a = Name} inner ->
450 | (0 p : IsVar n idx (x :: inner ++ outer)) ->
451 | NVar n (inner ++ x :: outer)
452 | shiftUnderNs s First = weakenNs s (MkNVar First)
453 | shiftUnderNs s (Later p) = insertNVar s (MkNVar p)