~/bend-docscommunity

src/MemTable.bend fails

raw source on the hub · import 0x05fa0e42448e8e221df592b204de523d/src/MemTable.bend as MemTable

2 imports
import Base
import ./Keys.bend as Keys

Types

type Entry source · line 10 · raw

Data

type MemTable source · line 13 · raw

Data

Definitions

def empty source · line 16 · raw

MemTable

def put source · line 19 · raw

@t:MemTable -> @k:String -> @v:String -> MemTable

def del source · line 24 · raw

@t:MemTable -> @k:String -> MemTable

def count source · line 29 · raw

@t:MemTable -> Nat

def scan_step source · line 37 · raw

@done:Bool -> @eq:Bool -> @hv:Maybe<&2, String> -> @ans:Maybe<&2, String> -> Pair(Bool, Maybe<&2, String>)

Scan state machine (Base List.merge pattern): the driver matches fuel + structural state only; the leaf folds one entry (done-flag freezes the answer — including tombstone None, which hides older versions).

def scan_go source · line 48 · raw

@fuel:Nat -> @+k:String -> @st:Pair(Bool, Maybe<&2, String>) -> @entries:List<&2, Entry> -> Maybe<&2, String>

def get source · line 61 · raw

@t:MemTable -> @+k:String -> Maybe<&2, String>

def frozen_lemma source · line 67 · raw

@fuel:Nat -> @k:String -> @ans:Maybe<&2, String> -> @entries:List<&2, Entry> -> {scan_go(fuel, k, (True{}, ans), entries) == ans : Maybe<&2, String>}

Lemma: a frozen (done) scan always answers ans.

def ryw_core source · line 80 · raw

@+entries:List<&2, Entry> -> @+k:String -> @v:String -> {scan_go(List.length(&2, Entry, Entry{k, Some{v}} <> entries), k, (False{}, None{}), Entry{k, Some{v}} <> entries) == Some{v} : Maybe<&2, String>}

Lemma: reading a freshly-put key answers its value.

def ryw_bridge source · line 85 · raw

@t:MemTable -> @+k:String -> @+v:String -> {get(put(t, k, v), k) == Some{v} : Maybe<&2, String>}

def del_core source · line 91 · raw

@+entries:List<&2, Entry> -> @+k:String -> {scan_go(List.length(&2, Entry, Entry{k, None{}} <> entries), k, (False{}, None{}), Entry{k, None{}} <> entries) == None{} : Maybe<&2, String>}

Lemma: reading a freshly-deleted key answers None (tombstone freezes).

def del_bridge source · line 96 · raw

@t:MemTable -> @+k:String -> @v:String -> {get(del(put(t, k, v), k), k) == None{} : Maybe<&2, String>}