~/bend-docscommunity

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>}