proofs/containers/lru/dellink.bend checks
raw source on the hub · import bend-collections-laws-containers@1.0.0.0/proofs/containers/lru/dellink.bend as Dellink
23 imports
import Base import ../../lib/logic.bend as L import ../../lib/nat.bend as N import ../../lib/array.bend as AR import ../../../spec/lib/common.bend as SC import ../../lib/u32div.bend as UD import ../../lib/word.bend as WD import ../../../src/math/hash.bend as HS import ../../../src/containers/hash_table.bend as H import ../../../src/containers/lru.bend as LR import ../hash_table/table.bend as TB import ../hash_table/buckets.bend as B import ../hash_table/cyc.bend as CY import ../hash_table/modn.bend as M import ../hash_table/arr.bend as AX import ../hash_table/inv.bend as IV import ../hash_table/insm.bend as IM import ../hash_table/tools.bend as TL import ../hash_table/probe_impl.bend as PI import ../hash_table/probe_all.bend as PA import ../hash_table/delw.bend as DW import ../../lib/u32.bend as UW import ../../lib/words32.bend as W32
Definitions
def lnk_c source · line 30 · raw
@+x:U32 -> @+y:U32 -> @+kl:List<&2, String> -> @+e:Bool -> @+ho:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.dec_c(x, y, kl, e)) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.dec_c(x, y, kl, e)) == y : U32}a full bucket's link is the raw link word
def lnk_raw source · line 37 · raw
@+tb:List<&2, U32> -> @+kl:List<&2, String> -> @+n:Nat -> @+p:Nat -> @+hp:{Nat.is_lt(p, n) == True{} : Bool} -> @+ho:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(tb, kl, n), p)) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(tb, kl, n), p)) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/words32.nth0(tb, 1n+Nat.double(p)) : U32}
def op_c source · line 42 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+n:Nat -> @+h:Nat -> @+q:Nat -> @+hp:{Bool.and(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(n, h, q))), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occpath(bs, n, h, q)) == True{} : Bool} -> @+j:Nat -> @+hj:{Nat.is_lt(j, 1n+q) == True{} : Bool} -> @+c:Bool -> @+hc:{Nat.is_eq(j, q) == c : Bool} -> @rec:(@hq:{Nat.is_lt(j, q) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(n, h, j))) == True{} : Bool}) -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(n, h, j))) == True{} : Bool}
def op_inst source · line 50 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+n:Nat -> @+h:Nat -> @+d:Nat -> @+hp:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occpath(bs, n, h, d) == True{} : Bool} -> @+j:Nat -> @+hj:{Nat.is_lt(j, d) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(n, h, j))) == True{} : Bool}the buckets before position d of a full path are full
def dstep_ok source · line 58 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+k:Nat -> @+hk31:{Nat.is_lt(k, 31n) == True{} : Bool} -> @+bp:Nat -> @+hN:{1n+bp == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k) : Nat} -> @+tabT:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<U32> -> @+pt:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.perfect(U32, 1n+k, tabT) == True{} : Bool} -> @+kl:List<&2, String> -> @+i:U32 -> @+p:Nat -> @+hi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(i) == p : Nat} -> @+hp:{Nat.is_lt(p, 1n+bp) == True{} : Bool} -> @+l:U32 -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.dstep(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), i, l) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.ds_if(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), U32.is_eq(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/words32.nth0(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), 1n+Nat.double(p)), l)) : 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.DStep}one step reads bucket p's raw link
def next_ok source · line 68 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+k:Nat -> @+hk31:{Nat.is_lt(k, 31n) == True{} : Bool} -> @+bp:Nat -> @+hN:{1n+bp == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k) : Nat} -> @+i:U32 -> @+hi:{Nat.is_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(i), 1n+bp) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.bnext(i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k))) == Nat.mod(1n+0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(i), 1n+bp) : Nat}
def pe_ne source · line 75 · raw
@+bp:Nat -> @+h:Nat -> @+hh:{Nat.is_lt(h, 1n+bp) == True{} : Bool} -> @+e:Nat -> @+he:{Nat.is_lt(e, 1n+bp) == True{} : Bool} -> @+j:Nat -> @+hj:{Nat.is_lt(j, 1n+bp) == True{} : Bool} -> @+hjd:{Nat.is_eq(j, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e)) == False{} : Bool} -> @+c:Bool -> @+hc:{Nat.is_eq(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(1n+bp, h, j), e) == c : Bool} -> {c == False{} : Bool}
def dl_c source · line 84 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+k:Nat -> @+hk31:{Nat.is_lt(k, 31n) == True{} : Bool} -> @+bp:Nat -> @+hN:{1n+bp == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k) : Nat} -> @+tabT:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<U32> -> @+pt:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.perfect(U32, 1n+k, tabT) == True{} : Bool} -> @+kl:List<&2, String> -> @+huq:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PUniq{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 1n+bp)}, 1n+bp) == True{} : Bool} -> @+e:Nat -> @+he:{Nat.is_lt(e, 1n+bp) == True{} : Bool} -> @+w:U32 -> @+l:U32 -> @+kk:String -> @+hbe:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 1n+bp), e) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BF{w, l, kk} : 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk} -> @+h:Nat -> @+hh:{Nat.is_lt(h, 1n+bp) == True{} : Bool} -> @+hop:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occpath(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 1n+bp), 1n+bp, h, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e)) == True{} : Bool} -> @+p:Nat -> @+j:Nat -> @+iu:U32 -> @+hiu:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(iu) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(1n+bp, h, j) : Nat} -> @+hjd:{Nat.is_le(j, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e)) == True{} : Bool} -> @+hf:{Nat.is_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e), Nat.add(j, 1n+p)) == True{} : Bool} -> @+c:Bool -> @+hc:{Nat.is_eq(j, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e)) == c : Bool} -> @rec:(@iu2:U32 -> @hiu2:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(iu2) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(1n+bp, h, 1n+j) : Nat} -> @hjd2:{Nat.is_le(1n+j, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e)) == True{} : Bool} -> @hf2:{Nat.is_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e), Nat.add(1n+j, p)) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.dfind(p, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.dstep(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), iu2, l), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), l, iu2) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.del_at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), U32.from_nat(e)) : Array<U32>}) -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.dfind(1n+p, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.dstep(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), iu, l), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), l, iu) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.del_at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), U32.from_nat(e)) : Array<U32>}
def dl_go source · line 118 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+k:Nat -> @+hk31:{Nat.is_lt(k, 31n) == True{} : Bool} -> @+bp:Nat -> @+hN:{1n+bp == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k) : Nat} -> @+tabT:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<U32> -> @+pt:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.perfect(U32, 1n+k, tabT) == True{} : Bool} -> @+kl:List<&2, String> -> @+huq:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PUniq{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 1n+bp)}, 1n+bp) == True{} : Bool} -> @+e:Nat -> @+he:{Nat.is_lt(e, 1n+bp) == True{} : Bool} -> @+w:U32 -> @+l:U32 -> @+kk:String -> @+hbe:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 1n+bp), e) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BF{w, l, kk} : 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk} -> @+h:Nat -> @+hh:{Nat.is_lt(h, 1n+bp) == True{} : Bool} -> @+hop:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occpath(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 1n+bp), 1n+bp, h, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e)) == True{} : Bool} -> @+f:Nat -> @+j:Nat -> @+iu:U32 -> @+hiu:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(iu) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.pos(1n+bp, h, j) : Nat} -> @+hjd:{Nat.is_le(j, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e)) == True{} : Bool} -> @+hf:{Nat.is_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/modn.dist(1n+bp, h, e), Nat.add(j, f)) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.dfind(f, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.dstep(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), iu, l), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), l, iu) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.del_at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), U32.from_nat(e)) : Array<U32>}
def del_link_ok source · line 129 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+k:Nat -> @+hk31:{Nat.is_lt(k, 31n) == True{} : Bool} -> @+tabT:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.Tree<U32> -> @+pt:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.perfect(U32, 1n+k, tabT) == True{} : Bool} -> @+kl:List<&2, String> -> @+cl:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.cluster(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k)), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k)) == True{} : Bool} -> @+huq:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PUniq{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k))}, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k)) == True{} : Bool} -> @+e:Nat -> @+he:{Nat.is_lt(e, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k)) == True{} : Bool} -> @+w:U32 -> @+l:U32 -> @+kk:String -> @+hbe:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/table.buckets(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.slots(U32, tabT), kl, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(k)), e) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BF{w, l, kk} : 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/lru.del_link(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), w, l) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.del_at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/array.thaw(U32, tabT), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/cyc.msk(k), U32.from_nat(e)) : Array<U32>}THEOREM (del_link): with bucket e holding word w and link l in a clustered table of unique links, del_link deletes bucket e