proofs/containers/lru/tabsl.bend checks
raw source on the hub · import bend-collections-laws-containers@1.0.0.0/proofs/containers/lru/tabsl.bend as Tabsl
17 imports
import Base import ../../lib/logic.bend as L import ../../lib/nat.bend as N import ../../lib/u32alg.bend as A import ../../../spec/lib/common.bend as SC import ../../lib/u32div.bend as UD import ../../../src/containers/hash_table.bend as H import ../hash_table/buckets.bend as B import ../hash_table/insm.bend as IM import ../hash_table/rehash.bend as RH import ../hash_table/tools.bend as TL import ../hash_table/words.bend as WR import ./state.bend as ST import ./tfind.bend as TF import ./unlink.bend as UL import ../../lib/nat_list.bend as NL import ../../lib/links.bend as LK
Definitions
def AnybAt source · line 25 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+m:Nat -> @+l:U32 -> @+w:U32 -> Type
def ab_up source · line 28 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+q:Nat -> @+l:U32 -> @+w:U32 -> @e:AnybAt(bs, q, l, w) -> AnybAt(bs, 1n+q, l, w)
def ab_c source · line 33 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+q:Nat -> @+l:U32 -> @+w:U32 -> @+c:Bool -> @+hc:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, q), w, l) == c : Bool} -> @+h:{Bool.or(c, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(bs, q, l, w)) == True{} : Bool} -> @rec:(@h2:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(bs, q, l, w) == True{} : Bool} -> AnybAt(bs, q, l, w)) -> AnybAt(bs, 1n+q, l, w)
def find_anyb source · line 42 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+m:Nat -> @+l:U32 -> @+w:U32 -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(bs, m, l, w) == True{} : Bool} -> AnybAt(bs, m, l, w)some bucket below m has word w and link l: one is found
def ai_c source · line 49 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+q:Nat -> @+l:U32 -> @+w:U32 -> @+j:Nat -> @+hj:{Nat.is_lt(j, 1n+q) == True{} : Bool} -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, j), w, l) == True{} : Bool} -> @+c:Bool -> @+hc:{Nat.is_eq(j, q) == c : Bool} -> @rec:(@hq:{Nat.is_lt(j, q) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(bs, q, l, w) == True{} : Bool}) -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(bs, 1n+q, l, w) == True{} : Bool}
def anyb_intro source · line 56 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+m:Nat -> @+l:U32 -> @+w:U32 -> @+j:Nat -> @+hj:{Nat.is_lt(j, m) == True{} : Bool} -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, j), w, l) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(bs, m, l, w) == True{} : Bool}
def isbf_occ source · line 63 · raw
@+b:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk -> @+w:U32 -> @+l:U32 -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(b, w, l) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(b) == True{} : Bool}
def ht1 source · line 72 · raw
@+nw:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+n2:Nat -> @+l:U32 -> @+w:U32 -> @+b:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk -> @+hb:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(b, w, l) == True{} : Bool} -> @e:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/rehash.EqAt(nw, n2, b) -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(nw, n2, l, w) == True{} : Bool}
def ht0 source · line 77 · raw
@+od:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+nw:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+n2:Nat -> @+hto:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PTo{od, nw, n2}, no) == True{} : Bool} -> @+l:U32 -> @+w:U32 -> @e:AnybAt(od, no, l, w) -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(nw, n2, l, w) == True{} : Bool}
def bf1 source · line 95 · raw
@+od:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+sl:List<&2, Nat> -> @+ll:List<&2, U32> -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bsl(od, sl, ll, no) == True{} : Bool} -> @+b:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk -> @e:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/rehash.EqAt(od, no, b) -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bslb(sl, ll, b) == True{} : Bool}
def bf0 source · line 100 · raw
@+od:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+sl:List<&2, Nat> -> @+ll:List<&2, U32> -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bsl(od, sl, ll, no) == True{} : Bool} -> @+b:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk -> @+hq:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.implies(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(b), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.anyeq(od, no, b)) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bslb(sl, ll, b) == True{} : Bool}
def bsl_from source · line 108 · raw
@+nw:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+od:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+n2:Nat -> @+hf:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PFrom{nw, od, no}, n2) == True{} : Bool} -> @+sl:List<&2, Nat> -> @+ll:List<&2, U32> -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bsl(od, sl, ll, no) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bsl(nw, sl, ll, n2) == True{} : Bool}THEOREM: a table of copies of old buckets keeps the slot correspondence
def ib_c source · line 117 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+i:Nat -> @+hlen:{Nat.is_lt(i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk, bs)) == True{} : Bool} -> @+q:Nat -> @+l:U32 -> @+w:U32 -> @+hne:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i), w, l) == False{} : Bool} -> @+c:Bool -> @+hc:{Nat.is_eq(i, q) == c : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/insm.bupd(bs, i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BE{}), q), w, l) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, q), w, l) : Bool}
def anyb_rm source · line 126 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+i:Nat -> @+hlen:{Nat.is_lt(i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk, bs)) == True{} : Bool} -> @+l:U32 -> @+w:U32 -> @+hne:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i), w, l) == False{} : Bool} -> @+m:Nat -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/insm.bupd(bs, i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BE{}), m, l, w) == 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.anyb(bs, m, l, w) : Bool}emptying a bucket that does not have word w and link l keeps any other
def isbf_ne_c source · line 134 · raw
@+w0:U32 -> @+l0:U32 -> @+w:U32 -> @+lx:U32 -> @+s:Nat -> @+x:Nat -> @+hsi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(l0)) == s : Nat} -> @+hx:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(lx)) == x : Nat} -> @+hne:{Nat.is_eq(x, s) == False{} : Bool} -> @+c:Bool -> @+hc:{U32.is_eq(l0, lx) == c : Bool} -> {Bool.and(U32.is_eq(w0, w), c) == False{} : Bool}
def isbf_ne source · line 144 · raw
@+b:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk -> @+w:U32 -> @+lx:U32 -> @+s:Nat -> @+x:Nat -> @+hsi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(b))) == s : Nat} -> @+hx:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(lx)) == x : Nat} -> @+hne:{Nat.is_eq(x, s) == False{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.isbf(b, w, lx) == False{} : Bool}the emptied bucket (slot s) is not the bucket of another slot x
def brm_b source · line 164 · raw
@+a:List<&2, Nat> -> @+s:Nat -> @+b:List<&2, Nat> -> @+ll:List<&2, U32> -> @+b0:0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk -> @+hb:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bslb(0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.append(Nat, a, s <> b), ll, b0) == True{} : Bool} -> @+hne:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.implies(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(b0), Bool.not(Nat.is_eq(s, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(b0)))))) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bslb(0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.append(Nat, a, b), ll, b0) == True{} : Bool}
def imp_ne source · line 176 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+huq:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PUniq{bs}, no) == True{} : Bool} -> @+i:Nat -> @+q:Nat -> @+hi:{Nat.is_lt(i, no) == True{} : Bool} -> @+hq:{Nat.is_lt(q, no) == True{} : Bool} -> @+hqi:{Nat.is_eq(q, i) == False{} : Bool} -> @+hoi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i)) == True{} : Bool} -> @+s:Nat -> @+hsi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i)))) == s : Nat} -> @+c:Bool -> @+hc:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, q)) == c : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.implies(c, Bool.not(Nat.is_eq(s, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, q))))))) == True{} : Bool}
def br_c source · line 185 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+huq:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PUniq{bs}, no) == True{} : Bool} -> @+i:Nat -> @+hi:{Nat.is_lt(i, no) == True{} : Bool} -> @+hlen:{Nat.is_lt(i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk, bs)) == True{} : Bool} -> @+hoi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i)) == True{} : Bool} -> @+a:List<&2, Nat> -> @+s:Nat -> @+b:List<&2, Nat> -> @+hsi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i)))) == s : Nat} -> @+ll:List<&2, U32> -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bsl(bs, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.append(Nat, a, s <> b), ll, no) == True{} : Bool} -> @+q:Nat -> @+hq:{Nat.is_lt(q, no) == True{} : Bool} -> @+c:Bool -> @+hc:{Nat.is_eq(i, q) == c : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bslb(0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.append(Nat, a, b), ll, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/insm.bupd(bs, i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BE{}), q)) == True{} : Bool}
def bsl_rm source · line 195 · raw
@+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+huq:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PUniq{bs}, no) == True{} : Bool} -> @+i:Nat -> @+hi:{Nat.is_lt(i, no) == True{} : Bool} -> @+hlen:{Nat.is_lt(i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk, bs)) == True{} : Bool} -> @+hoi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.occ(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i)) == True{} : Bool} -> @+a:List<&2, Nat> -> @+s:Nat -> @+b:List<&2, Nat> -> @+hsi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i)))) == s : Nat} -> @+ll:List<&2, U32> -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bsl(bs, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.append(Nat, a, s <> b), ll, no) == True{} : Bool} -> @+m:Nat -> @+hm:{Nat.is_le(m, no) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.bsl(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/insm.bupd(bs, i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BE{}), 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.append(Nat, a, b), ll, m) == True{} : Bool}THEOREM: emptying slot s's bucket: every full bucket's slot is listed once s is taken off the list
Templates
template has_to source · line 85 · raw
@-V:Data -> @+od:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+nw:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+n2:Nat -> @+hto:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.all_lt(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.PTo{od, nw, n2}, no) == True{} : Bool} -> @+ll:List<&2, U32> -> @+sl:List<&2, Nat> -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.hasall(V, od, no, ll, sl) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.hasall(V, nw, n2, ll, sl) == True{} : Bool}THEOREM: a table holding copies of all old buckets has a bucket for every slot
template has_rm source · line 152 · raw
@-V:Data -> @+one:Nat -> @+h1:{one == 1n : Nat} -> @+sd:Nat -> @+hsd:{Nat.is_lt(3n+sd, 32n) == True{} : Bool} -> @+fr:Nat -> @+el:List<&2, Maybe<&2, V>> -> @+hfr:{Nat.is_le(fr, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.pow2(sd)) == True{} : Bool} -> @+bs:List<&2, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk> -> @+no:Nat -> @+i:Nat -> @+hlen:{Nat.is_lt(i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/spec/lib/common.length(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.Bk, bs)) == True{} : Bool} -> @+s:Nat -> @+hsi:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/u32div.v(0x5c489f5d9646d7cc9aa3dd8137e9dc07/src/containers/hash_table.slot(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.lnk(0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.at(bs, i)))) == s : Nat} -> @+ll:List<&2, U32> -> @+xs:List<&2, Nat> -> @+hs:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/lib/nat_list.memn(s, xs) == False{} : Bool} -> @+hb:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.sall(V, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.PLive{fr, el}, xs) == True{} : Bool} -> @+h:{0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.hasall(V, bs, no, ll, xs) == True{} : Bool} -> {0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/lru/state.hasall(V, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/insm.bupd(bs, i, 0x5c489f5d9646d7cc9aa3dd8137e9dc07/proofs/containers/hash_table/buckets.BE{}), no, ll, xs) == True{} : Bool}THEOREM: emptying slot s's bucket leaves a bucket for every other slot