1	import Base
2	import ./Keys.bend as Keys
3	import ./MemTable.bend as MemTable
4	import ./BitTree.bend as BitTree
5	import ./SortedRun.bend as SortedRun
6	
7	# SSTables (Task 4): immutable strict sorted runs with BitTree Bloom filters.
8	# `build` canonicalizes newest-first raw entries; `from_sorted_unique` trusts an
9	# already strict, unique run and deliberately performs no sorting.
10	
11	type Bloom is Data:
12	  Blm{bits: BitTree.BitTree, size: Nat}
13	
14	type Table is Data:
15	  Tbl{
16	    entries: List<&2, MemTable.Entry>,
17	    filter: Bloom,
18	    nbits: Nat,
19	    smallest: Maybe<&2, String>,
20	    largest: Maybe<&2, String>,
21	    count: Nat,
22	    chunks: List<&2, List<&2, MemTable.Entry>>,
23	    blocks: List<&2, String>
24	  }
25	
26	def block_entries() -> Nat:
27	  64n
28	
29	def chunk_go(fuel: Nat, +entries: List<&2, MemTable.Entry>, +cur: List<&2, MemTable.Entry>, room: Nat, acc: List<&2, List<&2, MemTable.Entry>>) -> List<&2, List<&2, MemTable.Entry>>:
30	  match fuel:
31	    case 0n:
32	      List.reverse(&2, List<&2, MemTable.Entry>, Con{List.reverse(&2, MemTable.Entry, cur), acc})
33	    case 1n+f:
34	      match entries:
35	        case Nil{}:
36	          List.reverse(&2, List<&2, MemTable.Entry>, Con{List.reverse(&2, MemTable.Entry, cur), acc})
37	        case Con{e, t}:
38	          match room:
39	            case 0n:
40	              chunk_go(f, t, Con{e, Nil{}}, Nat.sub(block_entries(), 1n), Con{List.reverse(&2, MemTable.Entry, cur), acc})
41	            case 1n+r:
42	              chunk_go(f, t, Con{e, cur}, r, acc)
43	
44	def chunk(+entries: List<&2, MemTable.Entry>) -> List<&2, List<&2, MemTable.Entry>>:
45	  match entries:
46	    case Nil{}:
47	      Nil{}
48	    case Con{e, t}:
49	      chunk_go(List.length(&2, MemTable.Entry, entries), t, Con{e, Nil{}}, Nat.sub(block_entries(), 1n), Nil{})
50	
51	def chunk_head_key(+xs: List<&2, MemTable.Entry>) -> Maybe<&2, String>:
52	  match xs:
53	    case Nil{}:
54	      None{}
55	    case Con{MemTable.Entry{key, val}, t}:
56	      Some{key}
57	
58	def block_cons_acc(head: Maybe<&2, String>, acc: List<&2, String>) -> List<&2, String>:
59	  match head:
60	    case None{}:
61	      acc
62	    case Some{k}:
63	      Con{k, acc}
64	
65	def block_keys(+chunks: List<&2, List<&2, MemTable.Entry>>, acc: List<&2, String>) -> List<&2, String>:
66	  match chunks:
67	    case Nil{}:
68	      List.reverse(&2, String, acc)
69	    case Con{c, t}:
70	      block_keys(t, block_cons_acc(chunk_head_key(c), acc))
71	
72	type Metadata is Data:
73	  Meta{smallest: Maybe<&2, String>, largest: Maybe<&2, String>, count: Nat}
74	
75	# --- Bloom allocator (Monkey-style: smaller/upper levels get more bits) ---
76	# Closed form pinned here; Dayan-exact coefficients are tuning follow-up.
77	def bloom_bits(level: Nat, est_keys: Nat) -> Nat:
78	  match level:
79	    case 0n:
80	      Nat.mul(est_keys, 20n)
81	    case 1n+m:
82	      match m:
83	        case 0n:
84	          Nat.mul(est_keys, 10n)
85	        case 1n+p:
86	          Nat.mul(est_keys, 5n)
87	
88	# --- Local byte hash (kept stable for on-disk/rebuild compatibility) ---
89	def bhash(str: String, acc: U32) -> U32:
90	  match str:
91	    case SNil{}:
92	      acc
93	    case SCon{c, t}:
94	      bhash(t, U32.add(U32.mul(acc, 31), Char.to_u32(c)))
95	
96	# --- U32->Nat bridges that stay checker-tractable ---
97	# The Bend checker does not share across sequentially-chained U32.mul terms:
98	# `U32.to_nat` applied to a hash accumulated over 4+ bytes diverges in
99	# `{==}` elaboration (runtime is unaffected). The bridges below therefore
100	# never materialize a chained U32 as a Nat: each `to_nat` covers at most two
101	# U32 ops (shift+mask on the ORIGINAL word — parallel, shared), and all
102	# accumulation happens in small-Nat land. Both are EXACT (no semantic
103	# change): bytes are the base-256 digits of the word (Horner), so
104	# u32_to_nat_exact(w) == U32.to_nat(w) and bhash_n computes the same mod.
105	def u32_byte(+word: U32, shift: Nat) -> Nat:
106	  U32.to_nat(U32.and(U32.shrn(word, shift), 255))
107	
108	def u32_to_nat_exact(+word: U32) -> Nat:
109	  +b0 = u32_byte(word, 24n)
110	  +b1 = u32_byte(word, 16n)
111	  +b2 = u32_byte(word, 8n)
112	  +b3 = u32_byte(word, 0n)
113	  Nat.add(Nat.mul(b0, Nat.mul(Nat.mul(256n, 256n), 256n)), Nat.add(Nat.mul(b1, Nat.mul(256n, 256n)), Nat.add(Nat.mul(b2, 256n), b3)))
114	
115	def bhash_n_pos(+str: String, +seed: U32, +mod: Nat) -> Nat:
116	  +w = bhash(str, seed)
117	  +a0 = Nat.mod(u32_byte(w, 24n), mod)
118	  +a1 = Nat.mod(Nat.add(Nat.mul(a0, 256n), u32_byte(w, 16n)), mod)
119	  +a2 = Nat.mod(Nat.add(Nat.mul(a1, 256n), u32_byte(w, 8n)), mod)
120	  Nat.mod(Nat.add(Nat.mul(a2, 256n), u32_byte(w, 0n)), mod)
121	
122	def bhash_n(str: String, seed: U32, mod: Nat) -> Nat:
123	  match mod:
124	    case 0n:
125	      0n
126	    case 1n+p:
127	      bhash_n_pos(str, seed, mod)
128	
129	# BitTree stores whole U32 words while Bloom.size preserves the exact logical
130	# bit count selected by bloom_bits.
131	def bit_words(num: Nat) -> Nat:
132	  match num:
133	    case 0n:
134	      0n
135	    case 1n+m:
136	      Nat.add(1n, Nat.div(m, 32n))
137	
138	def bits_new(+num: Nat) -> BitTree.BitTree:
139	  BitTree.new(bit_words(num))
140	
141	def bit_set(idx: Nat, bits: BitTree.BitTree) -> BitTree.BitTree:
142	  BitTree.set(bits, idx)
143	
144	def bit_get(idx: Nat, bits: BitTree.BitTree) -> Bool:
145	  BitTree.test(bits, idx)
146	
147	def bloom_new(+num: Nat) -> Bloom:
148	  Blm{bits_new(num), num}
149	
150	def bloom_well_formed(bloom: Bloom) -> Bool:
151	  match bloom:
152	    case Blm{+bits, +size}:
153	      Bool.and(
154	        BitTree.well_formed(bits),
155	        Bool.and(
156	          Nat.is_eq(BitTree.word_count(bits), bit_words(size)),
157	          Nat.is_le(size, BitTree.bit_count(bits))))
158	
159	def bloom_add(bloom: Bloom, +key: String) -> Bloom:
160	  match bloom:
161	    case Blm{bits, +size}:
162	      Blm{bit_set(bhash_n(key, 17, size), bit_set(bhash_n(key, 257, size), bits)), size}
163	
164	def both(lhs: Bool, rhs: Bool) -> Bool:
165	  match lhs:
166	    case True{}:
167	      rhs
168	    case False{}:
169	      False{}
170	
171	def bloom_test(bloom: Bloom, +key: String) -> Bool:
172	  match bloom:
173	    case Blm{+bits, +size}:
174	      both(bit_get(bhash_n(key, 17, size), bits), bit_get(bhash_n(key, 257, size), bits))
175	
176	def table_bits(tab: Table) -> Nat:
177	  match tab:
178	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
179	      nbits
180	
181	def maybe_present(tab: Table, +key: String) -> Bool:
182	  match tab:
183	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
184	      bloom_test(filter, key)
185	
186	# --- Parallel probe counters (Task 1): sequential leaf, two-way fork, `!` gate ---
187	# Single probe as 0/1 for counting.
188	def probe_hit_if(present: Bool) -> Nat:
189	  match present:
190	    case True{}:
191	      1n
192	    case False{}:
193	      0n
194	
195	# Count matching probes sequentially.
196	def probe_hit(+tab: Table, +key: String) -> Nat:
197	  probe_hit_if(maybe_present(tab, key))
198	
199	# Sequential probe count over a probe list.
200	def probe_count_seq(+probes: List<&2, String>, +tab: Table) -> Nat:
201	  match probes:
202	    case Nil{}:
203	      0n
204	    case Con{+q, t}:
205	      Nat.add(probe_count_seq(t, tab), probe_hit(tab, q))
206	
207	# Two-way parallel probe count; halves share no state.
208	def probe_count_par(+probes: List<&2, String>, +tab: Table) -> Nat:
209	  +half = Nat.div(List.length(&2, String, probes), 2n)
210	  left right = probe_count_seq(List.take(&2, String, probes, half), tab) probe_count_seq(List.drop(&2, String, probes, half), tab)
211	  Nat.add(left, right)
212	
213	# Bang gate: GPU pays only with enough probes to fill lanes.
214	def probe_count_bang_gate(+num: Nat) -> Bool:
215	  Nat.is_le(16384n, num)
216	
217	# Pick CPU-pool or GPU execution for the same fork tree.
218	def probe_count_pick(gate: Bool, +probes: List<&2, String>, +tab: Table) -> Nat:
219	  match gate:
220	    case False{}:
221	      probe_count_par(probes, tab)
222	    case True{}:
223	      probe_count_par!(probes, tab)
224	
225	# Size-gated entry point for parallel probe counting.
226	def probe_count_auto(+probes: List<&2, String>, +tab: Table) -> Nat:
227	  probe_count_pick(probe_count_bang_gate(List.length(&2, String, probes)), probes, tab)
228	
229	# --- Canonicalization and construction ---
230	def bloom_of(entries: List<&2, MemTable.Entry>, +blm: Bloom) -> Bloom:
231	  match entries:
232	    case Nil{}:
233	      blm
234	    case Con{e, t}:
235	      match e:
236	        case MemTable.Entry{key, val}:
237	          bloom_of(t, bloom_add(blm, key))
238	
239	def bloom_union_trees(+abits: BitTree.BitTree, +bbits: BitTree.BitTree, size: Nat) -> Bloom:
240	  match abits:
241	    case BitTree.BT{aroot, awords, acap, aheight}:
242	      match bbits:
243	        case BitTree.BT{broot, bwords, bcap, bheight}:
244	          Blm{BitTree.BT{BitTree.union_bits(aroot, broot), awords, acap, aheight}, size}
245	
246	def bloom_union(ba: Bloom, bb: Bloom) -> Bloom:
247	  match ba:
248	    case Blm{abits, asize}:
249	      match bb:
250	        case Blm{bbits, bsize}:
251	          bloom_union_trees(abits, bbits, Nat.max(asize, bsize))
252	
253	def bloom_of_chunk(+chunk: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
254	  bloom_of(chunk, bloom_new(nb))
255	
256	# Two-half parallel build (spike 1): one spawn, one union. Sequential below.
257	def bloom_of_par(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
258	  +half = Nat.div(List.length(&2, MemTable.Entry, entries), 2n)
259	  left right = bloom_of_chunk(List.take(&2, MemTable.Entry, entries, half), nb) bloom_of_chunk(List.drop(&2, MemTable.Entry, entries, half), nb)
260	  bloom_union(left, right)
261	
262	# --- Four-chunk parallel build (Task 2): two-level fork, three unions ---
263	# Third chunk slice as take-after-drop.
264	def chunk_third(+entries: List<&2, MemTable.Entry>, +skip: Nat, +take: Nat) -> List<&2, MemTable.Entry>:
265	  List.take(&2, MemTable.Entry, List.drop(&2, MemTable.Entry, entries, skip), take)
266	
267	# Four-way chunk build with a two-level fork tree.
268	def bloom_of_chunks(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
269	  +num = List.length(&2, MemTable.Entry, entries)
270	  +q = Nat.div(num, 4n)
271	  a b = bloom_of_chunk(List.take(&2, MemTable.Entry, entries, q), nb) bloom_of_chunk(chunk_third(entries, q, q), nb)
272	  c d = bloom_of_chunk(chunk_third(entries, Nat.mul(q, 2n), q), nb) bloom_of_chunk(List.drop(&2, MemTable.Entry, entries, Nat.mul(q, 3n)), nb)
273	  bloom_union(bloom_union(a, b), bloom_union(c, d))
274	
275	# Bang gate: GPU pays only with enough entries to feed lanes.
276	def bloom_bang_gate(+num: Nat) -> Bool:
277	  Nat.is_le(8192n, num)
278	
279	# Pick CPU-pool or GPU execution for the same chunk tree.
280	def bloom_of_pick(gate: Bool, +entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
281	  match gate:
282	    case False{}:
283	      bloom_of_chunks(entries, nb)
284	    case True{}:
285	      bloom_of_chunks!(entries, nb)
286	
287	# Size-gated `!` entry point: the bang fires only at >= 8192 entries, where
288	# every flush in the durable write path lands (frozen merge of 4096 + 4096).
289	def bloom_of_bang(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
290	  bloom_of_pick(bloom_bang_gate(List.length(&2, MemTable.Entry, entries)), entries, nb)
291	
292	# --- Hybrid bloom (spike): parallel index collection, sequential assembly ---
293	# Phase 1 emits a flat index list (two per key); joins concatenate, so no
294	# chunk tree or union is ever built. Phase 2 folds the indexes into ONE tree
295	# on the CPU. This removes the tree-allocation amplification that costs ~10%
296	# at 1M scale in the chunk+union design, while keeping a fork tree that a
297	# future `!` can ship once the GPU recovery crash is fixed upstream.
298	# Both bit positions of one key as a flat two-element list.
299	def key_idxs(+key: String, +size: Nat) -> List<&2, Nat>:
300	  Con{bhash_n(key, 17, size), Con{bhash_n(key, 257, size), Nil{}}}
301	
302	# Sequential index collection over entries.
303	def hash_idxs_seq(+entries: List<&2, MemTable.Entry>, +size: Nat) -> List<&2, Nat>:
304	  match entries:
305	    case Nil{}:
306	      Nil{}
307	    case Con{MemTable.Entry{key, val}, t}:
308	      List.append(&2, Nat, key_idxs(key, size), hash_idxs_seq(t, size))
309	
310	# Balanced parallel index collection; reusable fuel bounds the fork depth.
311	def hash_idxs_par_go(+fuel: Nat, +entries: List<&2, MemTable.Entry>, +size: Nat) -> List<&2, Nat>:
312	  match fuel:
313	    case 0n:
314	      hash_idxs_seq(entries, size)
315	    case 1n+f:
316	      match entries:
317	        case Nil{}:
318	          Nil{}
319	        case Con{MemTable.Entry{key, val}, Nil{}}:
320	          key_idxs(key, size)
321	        case Con{_, Con{_, _}}:
322	          +half = Nat.div(List.length(&2, MemTable.Entry, entries), 2n)
323	          left right = hash_idxs_par_go(f, List.take(&2, MemTable.Entry, entries, half), size) hash_idxs_par_go(f, List.drop(&2, MemTable.Entry, entries, half), size)
324	          List.append(&2, Nat, left, right)
325	
326	# Parallel entry point; fuel covers the fork depth.
327	def hash_idxs_par(+entries: List<&2, MemTable.Entry>, +size: Nat) -> List<&2, Nat>:
328	  +fuel = List.length(&2, MemTable.Entry, entries)
329	  hash_idxs_par_go(fuel, entries, size)
330	
331	# Sequential assembly of one filter from a flat index list.
332	def bloom_set_all(+idxs: List<&2, Nat>, +blm: Bloom) -> Bloom:
333	  match idxs:
334	    case Nil{}:
335	      blm
336	    case Con{+i, t}:
337	      match blm:
338	        case Blm{bits, +size}:
339	          bloom_set_all(t, Blm{bit_set(i, bits), size})
340	
341	# Hybrid build: parallel hashing, single-tree assembly.
342	def bloom_of_hybrid(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
343	  bloom_set_all(hash_idxs_par(entries, nb), bloom_new(nb))
344	
345	# Size-gated entry point: sequential on both sides of the gate.
346	# MEASURED VERDICT (2026-09-26, 1M interleaved A/B, Darwin arm64, Bend 2.0.28):
347	# sequential median 225105 ms (4442 ops/s) vs 4-chunk 249150 ms (4014 ops/s)
348	# vs hybrid 261746 ms — the parallel builds cost ~10% (fork/join plus
349	# allocation overhead dominates; invisible at 100k, compounds over 244
350	# flushes). Confirmed under two machine states (all arms shifted +15k ms on
351	# the slow day; relative order unchanged). The parallel builds stay as
352	# law-covered spikes; the `!` variants stay opt-in behind the GPU recovery
353	# crash documented below.
354	def bloom_pick(small: Bool, +entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
355	  match small:
356	    case True{}:
357	      bloom_of(entries, bloom_new(nb))
358	    case False{}:
359	      bloom_of(entries, bloom_new(nb))
360	
361	def bloom_of_auto(+entries: List<&2, MemTable.Entry>, +nb: Nat) -> Bloom:
362	  bloom_pick(Nat.is_lt(List.length(&2, MemTable.Entry, entries), 2048n), entries, nb)
363	
364	def metadata_tail(entries: List<&2, MemTable.Entry>, +first: String, last: String, +count: Nat) -> Metadata:
365	  match entries:
366	    case Nil{}:
367	      Meta{Some{first}, Some{last}, count}
368	    case Con{MemTable.Entry{key, val}, rest}:
369	      metadata_tail(rest, first, key, Nat.add(count, 1n))
370	
371	def metadata(entries: List<&2, MemTable.Entry>) -> Metadata:
372	  match entries:
373	    case Nil{}:
374	      Meta{None{}, None{}, 0n}
375	    case Con{MemTable.Entry{+key, val}, rest}:
376	      metadata_tail(rest, key, key, 1n)
377	
378	def from_sorted_unique_est_meta(+entries: List<&2, MemTable.Entry>, level: Nat, est_keys: Nat, meta: Metadata) -> Table:
379	  match meta:
380	    case Meta{smallest, largest, count}:
381	      +nb = bloom_bits(level, est_keys)
382	      Tbl{entries, bloom_of_auto(entries, nb), nb, smallest, largest, count, chunk(entries), block_keys(chunk(entries), Nil{})}
383	
384	def from_sorted_unique_meta(+entries: List<&2, MemTable.Entry>, level: Nat, meta: Metadata) -> Table:
385	  match meta:
386	    case Meta{smallest, largest, +count}:
387	      +nb = bloom_bits(level, count)
388	      Tbl{entries, bloom_of_auto(entries, nb), nb, smallest, largest, count, chunk(entries), block_keys(chunk(entries), Nil{})}
389	
390	def from_sorted_unique(+entries: List<&2, MemTable.Entry>, level: Nat) -> Table:
391	  from_sorted_unique_meta(entries, level, metadata(entries))
392	
393	def build_sorted(+entries: List<&2, MemTable.Entry>, level: Nat, est_keys: Nat) -> Table:
394	  from_sorted_unique_est_meta(entries, level, est_keys, metadata(entries))
395	
396	def build(+entries: List<&2, MemTable.Entry>, level: Nat, est_keys: Nat) -> Table:
397	  +effective = Nat.max(est_keys, List.length(&2, MemTable.Entry, entries))
398	  build_sorted(SortedRun.sort_newest(entries), level, effective)
399	
400	# Metadata accessors keep clients independent of the Tbl field layout.
401	def table_smallest(tab: Table) -> Maybe<&2, String>:
402	  match tab:
403	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
404	      smallest
405	
406	def table_largest(tab: Table) -> Maybe<&2, String>:
407	  match tab:
408	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
409	      largest
410	
411	def table_count(tab: Table) -> Nat:
412	  match tab:
413	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
414	      count
415	
416	# Total table identity for the read cache: smallest|largest|count.
417	def opt_name(+opt: Maybe<&2, String>) -> String:
418	  match opt:
419	    case None{}:
420	      "<none>"
421	    case Some{s}:
422	      s
423	
424	def table_id(tab: Table) -> String:
425	  match tab:
426	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
427	      opt_name(smallest) ++ "|" ++ opt_name(largest) ++ "|" ++ Nat.show(count)
428	
429	# Open bridge: metadata is matched explicitly so the Bloom schedule projects
430	# through `build` without relying on reduction of an open entry list.
431	def table_bits_from_meta(
432	  +entries: List<&2, MemTable.Entry>,
433	  level: Nat,
434	  est_keys: Nat,
435	  meta: Metadata,
436	) -> {table_bits(from_sorted_unique_est_meta(entries, level, est_keys, meta)) == bloom_bits(level, est_keys) : Nat}:
437	  match meta:
438	    case Meta{smallest, largest, count}:
439	      {==}
440	
441	def table_bits_build(
442	  +entries: List<&2, MemTable.Entry>,
443	  level: Nat,
444	  est_keys: Nat,
445	) -> {table_bits(build(entries, level, est_keys)) == bloom_bits(level, Nat.max(est_keys, List.length(&2, MemTable.Entry, entries))) : Nat}:
446	  +effective = Nat.max(est_keys, List.length(&2, MemTable.Entry, entries))
447	  table_bits_from_meta(SortedRun.sort_newest(entries), level, effective, metadata(SortedRun.sort_newest(entries)))
448	
449	
450	def ranges_disjoint(+ta: Table, +tb: Table) -> Bool:
451	  SortedRun.range_disjoint_bounds(table_smallest(ta), table_largest(ta), table_smallest(tb), table_largest(tb))
452	
453	def size_of(bloom: Bloom) -> Nat:
454	  match bloom:
455	    case Blm{bits, size}:
456	      size
457	
458	# Bloom insertions only set tree bits and preserve the exact logical size.
459	def bloom_size_stable(entries: List<&2, MemTable.Entry>, bits: BitTree.BitTree, +size: Nat) -> {size_of(bloom_of(entries, Blm{bits, size})) == size : Nat}:
460	  match entries:
461	    case Nil{}:
462	      {==}
463	    case Con{e, t}:
464	      match e:
465	        case MemTable.Entry{+key, val}:
466	          bloom_size_stable(t, bit_set(bhash_n(key, 17, size), bit_set(bhash_n(key, 257, size), bits)), size)
467	
468	# Block-scoped lookup. Checker constraints (proven by scratch experiments):
469	# multi-scrutinee matches follow declaration order, and only Nat answers flow
470	# through match arms — so selection returns an index, picked up by chunk_at_go.
471	def pick_ix(bt: List<&2, String>, ct: List<&2, List<&2, MemTable.Entry>>, ix: Nat, +key: String, order: Cmp) -> Nat:
472	  match bt ct order:
473	    case _ _ GT{}:
474	      Nat.sub(ix, 1n)
475	    case Nil{} _ _:
476	      ix
477	    case _ Nil{} _:
478	      ix
479	    case Con{b2, bt2} Con{d2, ct2} LT{}:
480	      pick_ix(bt2, ct2, Nat.add(ix, 1n), key, Keys.cmp(b2, key))
481	    case Con{b2, bt2} Con{d2, ct2} EQ{}:
482	      ix
483	
484	def chunk_at_go(fuel: Nat, +chunks: List<&2, List<&2, MemTable.Entry>>, ix: Nat) -> List<&2, MemTable.Entry>:
485	  match fuel chunks:
486	    case 0n _:
487	      Nil{}
488	    case 1n+f Nil{}:
489	      Nil{}
490	    case 1n+f Con{c, t}:
491	      match ix:
492	        case 0n:
493	          c
494	        case 1n+p:
495	          chunk_at_go(f, t, p)
496	
497	def chunk_at(+chunks: List<&2, List<&2, MemTable.Entry>>, ix: Nat) -> List<&2, MemTable.Entry>:
498	  chunk_at_go(List.length(&2, List<&2, MemTable.Entry>, chunks), chunks, ix)
499	
500	def block_scan(+chunk: List<&2, MemTable.Entry>, +key: String) -> Maybe<&2, String>:
501	  MemTable.get(MemTable.MT{chunk}, key)
502	
503	def block_pick(+chunks: List<&2, List<&2, MemTable.Entry>>, +blocks: List<&2, String>, +key: String) -> List<&2, MemTable.Entry>:
504	  match chunks blocks:
505	    case Nil{} _:
506	      Nil{}
507	    case _ Nil{}:
508	      Nil{}
509	    case Con{c, ct} Con{b, bt}:
510	      chunk_at(chunks, pick_ix(bt, ct, 0n, key, Keys.cmp(b, key)))
511	
512	def block_finish(picked: List<&2, MemTable.Entry>, +entries: List<&2, MemTable.Entry>, +key: String) -> Maybe<&2, String>:
513	  match picked:
514	    case Nil{}:
515	      MemTable.get(MemTable.MT{entries}, key)
516	    case Con{e, t}:
517	      block_scan(Con{e, t}, key)
518	
519	def hit_finish(picked: List<&2, MemTable.Entry>, +entries: List<&2, MemTable.Entry>, +key: String) -> Maybe<&2, Maybe<&2, String>>:
520	  match picked:
521	    case Nil{}:
522	      MemTable.get_hit(MemTable.MT{entries}, key)
523	    case Con{e, t}:
524	      MemTable.get_hit(MemTable.MT{Con{e, t}}, key)
525	
526	def block_get_hit(tab: Table, +key: String) -> Maybe<&2, Maybe<&2, String>>:
527	  match tab:
528	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
529	      hit_finish(block_pick(chunks, blocks, key), entries, key)
530	
531	def block_get(tab: Table, +key: String) -> Maybe<&2, String>:
532	  match tab:
533	    case Tbl{entries, filter, nbits, smallest, largest, count, chunks, blocks}:
534	      block_finish(block_pick(chunks, blocks, key), entries, key)
535	
536	def lookup(tab: Table, +key: String) -> Maybe<&2, String>:
537	  block_get(tab, key)