~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
1156 lines · 40.2 KB Raw History
//! The space repos' sections of an account's table, what the memtable
//! keeps of them, and how they are read: memtable, then table.
//!
//! Every key of these sections is its section's letter, the space's URI, a
//! zero byte, and the rest: a space repo's entries are together, in the
//! order its reads go in, and no URI's are among another's, as no URI
//! holds a zero byte. The rest is, of a record (`R`, `V`), its path; of an
//! operation (`O`), its commit's rev and its index in that commit, 4 bytes
//! big-endian; of a blob reference (`C`), the blob's CID as a string, a
//! zero byte, and the referencing record's path.
//!
//! The memtable (`SpaceMem`) keeps each record the log wrote with what its
//! `R` entry holds and where its frame is, or that it is deleted; each
//! commit with operations with where its frame is; and each blob reference
//! made or taken away. A `clearRecords`, an import or a drop makes a `Void`
//! of its space repo: the table's entries of it count for nothing from then
//! on, and what the memtable kept of it before is let go.

use super::{Disk, Rows, Want, frame_item, key, read_at};
use crate::space_repo::Op;
use pds_repo::data::cid_string;
use pds_store::Pos;
use pds_store::table::{BlockCache, Table};
use serde_json::Value as Json;
use sha2::{Digest, Sha256};
use std::collections::{BTreeMap, HashMap};
use std::fs::File;
use std::io;
use std::iter::Peekable;
use std::ops::Bound;
use std::sync::Arc;

/// The sections' letters: blob references, operations, records and their bytes.
pub(super) const REFS: u8 = b'C';
pub(super) const OPS: u8 = b'O';
pub(super) const RECORDS: u8 = b'R';
pub(super) const VALUES: u8 = b'V';

/// A key after every key of these sections, less its section's letter: a
/// URI begins `at://`.
const END: &[u8] = &[0xff];

/// A key of a space repo's, less its section's letter.
pub(crate) fn space_key(uri: &str, rest: &[u8]) -> Vec<u8> {
    [uri.as_bytes(), &[0], rest].concat()
}

/// The first key after every one of a space repo's.
fn space_end(uri: &str) -> Vec<u8> {
    [uri.as_bytes(), &[1]].concat()
}

/// A key's space URI and the rest.
fn split(k: &[u8]) -> Option<(&str, &[u8])> {
    let i = k.iter().position(|b| *b == 0)?;
    Some((std::str::from_utf8(&k[..i]).ok()?, &k[i + 1..]))
}

/// The first string after every one that begins with `prefix`.
pub(crate) fn after_prefix(prefix: &str) -> Vec<u8> {
    let mut b = prefix.as_bytes().to_vec();
    while let Some(l) = b.pop() {
        if l < 0xff {
            b.push(l + 1);
            break;
        }
    }
    b
}

fn varint(out: &mut Vec<u8>, mut n: usize) {
    while n >= 0x80 {
        out.push((n as u8) | 0x80);
        n >>= 7;
    }
    out.push(n as u8);
}

fn sized(out: &mut Vec<u8>, b: &[u8]) {
    varint(out, b.len());
    out.extend_from_slice(b);
}

/// The bytes `sized` wrote at `at`, which it moves past them.
fn take<'a>(v: &'a [u8], at: &mut usize) -> Option<&'a [u8]> {
    let mut n = 0usize;
    for shift in (0..35).step_by(7) {
        let b = *v.get(*at)?;
        *at += 1;
        n |= usize::from(b & 0x7f) << shift;
        if b & 0x80 == 0 {
            let got = v.get(*at..at.checked_add(n)?)?;
            *at += n;
            return Some(got);
        }
    }
    None
}

fn text(b: &[u8]) -> Option<String> {
    String::from_utf8(b.to_vec()).ok()
}

/// What a record's `R` entry holds: its CID, the rev of the commit or
/// import that last wrote it, and the CIDs of the blobs it references, each
/// once, in order.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Meta {
    pub cid: Vec<u8>,
    pub rev: String,
    pub refs: Vec<String>,
}

impl Meta {
    /// Its `R` value: the CID, the rev and each blob's CID, each after its length.
    pub(super) fn encode(&self) -> Vec<u8> {
        let mut out = Vec::with_capacity(self.cid.len() + self.rev.len() + 2);
        sized(&mut out, &self.cid);
        sized(&mut out, self.rev.as_bytes());
        for r in &self.refs {
            sized(&mut out, r.as_bytes());
        }
        out
    }

    pub(super) fn decode(v: &[u8]) -> Option<Meta> {
        let mut at = 0;
        let cid = take(v, &mut at)?.to_vec();
        let rev = text(take(v, &mut at)?)?;
        let mut refs = Vec::new();
        while at < v.len() {
            refs.push(text(take(v, &mut at)?)?);
        }
        Some(Meta { cid, rev, refs })
    }
}

/// A blob reference's `C` key, less the letter: its space, the blob's CID
/// as a string, and the referencing record's path.
pub(super) fn ref_key(uri: &str, cid: &str, path: &str) -> Vec<u8> {
    space_key(uri, &[cid.as_bytes(), &[0], path.as_bytes()].concat())
}

/// An operation's `O` key, less the letter: its space, its rev and its index.
pub(super) fn op_key(uri: &str, rev: &str, index: usize) -> Vec<u8> {
    let index = u32::try_from(index).unwrap_or(u32::MAX);
    space_key(uri, &[rev.as_bytes(), &index.to_be_bytes()].concat())
}

/// An operation's `O` value: the CID after and the CID before, each after
/// its length, `0` for none, then the path.
pub(super) fn op_value(o: &Op) -> Vec<u8> {
    let mut out = Vec::with_capacity(o.path.len() + 80);
    sized(&mut out, o.cid.as_deref().unwrap_or_default());
    sized(&mut out, o.prev.as_deref().unwrap_or_default());
    out.extend_from_slice(o.path.as_bytes());
    out
}

/// An operation, from the rest of its key and its value.
pub(super) fn read_op(rest: &[u8], v: &[u8]) -> Option<Op> {
    let (rev, index) = rest.split_at(rest.len().checked_sub(4)?);
    let mut at = 0;
    let some = |b: &[u8]| (!b.is_empty()).then(|| b.to_vec());
    let cid = some(take(v, &mut at)?);
    let prev = some(take(v, &mut at)?);
    Some(Op {
        rev: text(rev)?,
        index: u32::from_be_bytes(index.try_into().ok()?) as usize,
        path: text(&v[at..])?,
        cid,
        prev,
    })
}

fn name(parts: &[&str]) -> [u8; 32] {
    let mut h = Sha256::new();
    for p in parts {
        h.update(p.as_bytes());
        h.update([0]);
    }
    h.finalize().into()
}

/// The name a frame's index has a space record by: of its space, the rev
/// of the commit or import that wrote it, and its path.
pub(super) fn record_name(uri: &str, rev: &str, path: &str) -> [u8; 32] {
    name(&[uri, rev, path])
}

/// The name a frame's index has a space commit's operations by.
pub(super) fn ops_name(uri: &str, rev: &str) -> [u8; 32] {
    name(&[uri, rev])
}

/// A space commit's operations, from their list as its entry has it.
fn commit_ops(rev: &str, list: &[u8]) -> Result<Vec<Op>, String> {
    let list: Vec<Json> =
        serde_json::from_slice(list).map_err(|e| format!("a space commit's operations: {e}"))?;
    crate::space_repo::ops_of(rev, &list)
}

// ---- The memtable's part ----------------------------------------------------------

/// A record the log wrote: what its `R` entry holds, and where its frame is.
#[derive(Clone, Debug)]
pub(crate) struct MemRecord {
    pub meta: Meta,
    pub pos: Pos,
}

/// The table's entries of a space repo that count for nothing since an
/// entry of the log of `generation`: every operation; every blob
/// reference, if `refs`; and every record but those whose path begins with
/// one of `keep`, or none if `keep` is none.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Void {
    pub generation: u64,
    pub keep: Option<Vec<String>>,
    pub refs: bool,
}

/// What the log after the table changed of the account's space repos, each
/// map by its section's key less the letter.
#[derive(Default)]
pub(crate) struct SpaceMem {
    /// Each record written, or none once deleted, and the generation of the
    /// log that last changed it.
    pub records: BTreeMap<Vec<u8>, (Option<MemRecord>, u64)>,
    /// Each commit with operations, by its space and rev: where its frame
    /// is, and how many it has.
    pub commits: BTreeMap<Vec<u8>, (Pos, u32)>,
    /// Each blob reference: the rev of the commit that wrote the referencing
    /// record, or none once it is gone, and the generation that changed it.
    pub refs: BTreeMap<Vec<u8>, (Option<String>, u64)>,
    /// What of the table is void, by space: at most one for each generation
    /// of the log, in their order.
    pub voids: BTreeMap<String, Vec<Void>>,
    /// The bytes all of it is counted as in the cache.
    cost: u64,
}

/// About the bytes a record's entry takes: its key and its place in the
/// map, and of one written, its CID, rev and blob refs, each an allocation
/// of its own.
fn record_cost(k: &[u8], r: &Option<MemRecord>) -> u64 {
    let held = r.as_ref().map_or(0, |r| {
        160 + r.meta.cid.len()
            + r.meta.rev.len()
            + r.meta.refs.iter().map(|c| c.len() + 40).sum::<usize>()
    });
    (k.len() + 144 + held) as u64
}

fn commit_cost(k: &[u8]) -> u64 {
    (k.len() + 96) as u64
}

fn ref_cost(k: &[u8]) -> u64 {
    (k.len() + 112) as u64
}

const VOID_COST: u64 = 256;

/// The prefixes both lists keep: those of each that one of the other covers.
fn both(a: Vec<String>, b: &[String]) -> Vec<String> {
    let mut out: Vec<String> = b
        .iter()
        .filter(|q| a.iter().any(|p| q.starts_with(p.as_str()) && *q != p))
        .cloned()
        .collect();
    out.extend(
        a.into_iter()
            .filter(|p| b.iter().any(|q| p.starts_with(q.as_str()))),
    );
    out
}

/// The prefixes of the records' paths every one of `voids` keeps: none if
/// none of them voids records.
fn kept(voids: &[Void]) -> Option<Vec<String>> {
    voids
        .iter()
        .filter_map(|v| v.keep.as_ref())
        .fold(None, |all, k| {
            Some(match all {
                None => k.clone(),
                Some(a) => both(a, k),
            })
        })
}

impl SpaceMem {
    /// The bytes it is counted as in the cache.
    pub fn cost(&self) -> u64 {
        self.cost
    }

    /// A record of the space `uri` written at `path`, or deleted, by an
    /// entry of the log of `generation`.
    pub fn record(&mut self, uri: &str, path: &str, r: Option<MemRecord>, generation: u64) {
        let k = space_key(uri, path.as_bytes());
        self.cost += record_cost(&k, &r);
        if let Some((k, (old, _))) = self.records.remove_entry(&k) {
            self.cost -= record_cost(&k, &old);
        }
        self.records.insert(k, (r, generation));
    }

    /// A commit of the space `uri` at `rev`, of `n` operations, in the frame at `pos`.
    pub fn commit(&mut self, uri: &str, rev: &str, pos: Pos, n: u32) {
        let k = space_key(uri, rev.as_bytes());
        let cost = commit_cost(&k);
        if self.commits.insert(k, (pos, n)).is_none() {
            self.cost += cost;
        }
    }

    /// The reference of the record at `path` of the space `uri` to the blob
    /// `cid`: made by a commit at `rev`, or with none, gone.
    pub fn reference(
        &mut self,
        uri: &str,
        cid: &str,
        path: &str,
        rev: Option<String>,
        generation: u64,
    ) {
        let k = ref_key(uri, cid, path);
        let cost = ref_cost(&k);
        if self.refs.insert(k, (rev, generation)).is_none() {
            self.cost += cost;
        }
    }

    /// Void the table's entries of the space `uri`, as `v` says, and let go
    /// of what the memtable kept of them.
    pub fn void(&mut self, uri: &str, v: Void) {
        let (lo, hi) = (space_key(uri, b""), space_end(uri));
        let within = |k: &&Vec<u8>| k.as_slice() < hi.as_slice();
        let commits: Vec<Vec<u8>> = self
            .commits
            .range(lo.clone()..)
            .map(|(k, _)| k)
            .take_while(within)
            .cloned()
            .collect();
        for k in commits {
            self.commits.remove(&k);
            self.cost -= commit_cost(&k);
        }
        if v.refs {
            let refs: Vec<Vec<u8>> = self
                .refs
                .range(lo.clone()..)
                .map(|(k, _)| k)
                .take_while(within)
                .cloned()
                .collect();
            for k in refs {
                self.refs.remove(&k);
                self.cost -= ref_cost(&k);
            }
        }
        if let Some(keep) = &v.keep {
            let stays = |k: &[u8]| keep.iter().any(|p| k[lo.len()..].starts_with(p.as_bytes()));
            let records: Vec<Vec<u8>> = self
                .records
                .range(lo.clone()..)
                .map(|(k, _)| k)
                .take_while(within)
                .filter(|k| !stays(k))
                .cloned()
                .collect();
            for k in records {
                if let Some((old, _)) = self.records.remove(&k) {
                    self.cost -= record_cost(&k, &old);
                }
            }
        }
        let list = self.voids.entry(uri.to_string()).or_default();
        match list.last_mut() {
            Some(last) if last.generation == v.generation => {
                last.refs |= v.refs;
                last.keep = match (last.keep.take(), v.keep) {
                    (Some(a), Some(b)) => Some(both(a, &b)),
                    (a, b) => a.or(b),
                };
            }
            _ => {
                list.push(v);
                self.cost += VOID_COST;
            }
        }
    }

    /// Let go of what the log's generations before `generation` changed,
    /// which a table of that generation holds.
    pub(super) fn folded(&mut self, generation: u64) {
        self.records.retain(|_, r| r.1 >= generation);
        self.commits.retain(|_, c| c.0.generation >= generation);
        self.refs.retain(|_, r| r.1 >= generation);
        self.voids.retain(|_, list| {
            list.retain(|v| v.generation >= generation);
            !list.is_empty()
        });
        let records: u64 = self
            .records
            .iter()
            .map(|(k, (r, _))| record_cost(k, r))
            .sum();
        let commits: u64 = self.commits.keys().map(|k| commit_cost(k)).sum();
        let refs: u64 = self.refs.keys().map(|k| ref_cost(k)).sum();
        let voids = self.voids.values().map(|l| l.len() as u64).sum::<u64>() * VOID_COST;
        self.cost = records + commits + refs + voids;
    }

    /// Whether the table's entry at `k` of `section` is void; if it is,
    /// the key its entries not void go on from, or with `reverse`, are before.
    fn skip(&self, section: u8, k: &[u8], reverse: bool) -> Option<Vec<u8>> {
        if self.voids.is_empty() {
            return None;
        }
        let (uri, rest) = split(k)?;
        let voids = self.voids.get(uri)?;
        let all = || {
            Some(if reverse {
                space_key(uri, b"")
            } else {
                space_end(uri)
            })
        };
        match section {
            OPS => all(),
            REFS if voids.iter().any(|v| v.refs) => all(),
            REFS => None,
            _ => {
                let keep = kept(voids)?;
                if keep.iter().any(|p| rest.starts_with(p.as_bytes())) {
                    return None;
                }
                let next = if reverse {
                    keep.iter()
                        .map(|p| after_prefix(p))
                        .filter(|e| e.as_slice() <= rest)
                        .max()
                } else {
                    keep.iter()
                        .map(|p| p.as_bytes().to_vec())
                        .filter(|p| p.as_slice() > rest)
                        .min()
                };
                next.map(|p| space_key(uri, &p)).or_else(all)
            }
        }
    }
}

// ---- Reading: memtable, then table ---------------------------------------------------

/// The table's entries of these sections, if it has one, read from its
/// file opened if given.
#[derive(Clone, Copy)]
pub(crate) enum Old<'a> {
    None,
    Table(&'a Table, Option<&'a File>),
}

/// What the memtable keeps of a section, in the order a scan reads it.
type MemRows<'a, M> = Peekable<Box<dyn Iterator<Item = (&'a Vec<u8>, &'a M)> + 'a>>;

/// What reads an item of the frame at a place, for a fold.
pub(super) type Items<'a> = dyn FnMut(Pos, Want) -> Result<Option<Vec<u8>>, String> + 'a;

/// What takes each entry of the table a fold makes, in order of key.
pub(super) type Put<'a> = dyn FnMut(&[u8], &[u8]) -> Result<(), String> + 'a;

impl<'a> Old<'a> {
    fn get(&self, k: &[u8], cache: &BlockCache) -> Result<Option<Vec<u8>>, String> {
        match self {
            Old::None => Ok(None),
            Old::Table(t, file) => {
                #[cfg(test)]
                tests::READS.with(|n| n.set(n.get() + 1));
                t.get_in(k, *file, cache).map_err(|e| e.to_string())
            }
        }
    }

    /// Its entries from `from` on, or with `reverse`, before it, the last first.
    fn iter(&self, from: &[u8], reverse: bool, cache: &'a BlockCache) -> Rows<'a, String> {
        match *self {
            Old::None => Box::new(std::iter::empty()),
            Old::Table(t, file) => {
                let it = if reverse {
                    t.iter_back(from, file, cache)
                } else {
                    t.iter(from, file, cache)
                };
                Box::new(it.map(|r| {
                    #[cfg(test)]
                    tests::READS.with(|n| n.set(n.get() + 1));
                    r.map_err(|e| e.to_string())
                }))
            }
        }
    }
}

/// An entry as a scan meets it: what the memtable keeps of it, or the table's value.
pub(crate) enum Row<'a, M> {
    Mem(&'a M),
    Old(Vec<u8>),
}

/// The entries of a section between two keys, in order or the last first:
/// the memtable's, and the table's that the memtable neither has nor
/// voids, each read as it is reached. Each is given with its key less the
/// section's letter.
pub(crate) struct Scan<'a, M> {
    view: View<'a>,
    section: u8,
    mem: MemRows<'a, M>,
    rows: Peekable<Rows<'a, String>>,
    lo: Vec<u8>,
    hi: Vec<u8>,
    reverse: bool,
}

impl<'a, M> Scan<'a, M> {
    /// The table's entries within the bounds, on from `at`.
    fn old(&self, at: &[u8]) -> Peekable<Rows<'a, String>> {
        let section = self.section;
        let rows = self
            .view
            .old
            .iter(&key(section, at), self.reverse, self.view.cache);
        let bound = if self.reverse {
            self.lo.clone()
        } else {
            self.hi.clone()
        };
        let reverse = self.reverse;
        let within = move |r: &Result<(Vec<u8>, Vec<u8>), String>| {
            r.as_ref().map_or(true, |(k, _)| {
                k.first() == Some(&section)
                    && if reverse {
                        k[1..] >= bound[..]
                    } else {
                        k[1..] < bound[..]
                    }
            })
        };
        (Box::new(rows.take_while(within)) as Rows<'a, String>).peekable()
    }
}

impl<'a, M> Iterator for Scan<'a, M> {
    type Item = Result<(Vec<u8>, Row<'a, M>), String>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            // A table's entry the memtable voids: on from where it voids none.
            if let Some(Ok((k, _))) = self.rows.peek()
                && let Some(to) = self.view.mem.skip(self.section, &k[1..], self.reverse)
            {
                self.rows = self.old(&to);
                continue;
            }
            let mine = match (self.mem.peek(), self.rows.peek()) {
                (None, None) => return None,
                (_, Some(Err(_))) => false,
                (Some(_), None) => true,
                (None, Some(_)) => false,
                (Some((m, _)), Some(Ok((k, _)))) => match m.as_slice().cmp(&k[1..]) {
                    std::cmp::Ordering::Equal => {
                        self.rows.next();
                        true
                    }
                    order => (order == std::cmp::Ordering::Greater) == self.reverse,
                },
            };
            return Some(if mine {
                let (k, m) = self.mem.next()?;
                Ok((k.clone(), Row::Mem(m)))
            } else {
                self.rows
                    .next()?
                    .map(|(k, v)| (k[1..].to_vec(), Row::Old(v)))
            });
        }
    }
}

/// An operation log's entries as a scan meets them: a commit of the log's,
/// its rev and where its frame is, or an operation of the table's.
pub(crate) enum Ops {
    Commit(String, Pos),
    Row(Op),
}

/// The space repos' sections as they are now: what the memtable keeps,
/// over the table's entries.
#[derive(Clone, Copy)]
pub(crate) struct View<'a> {
    pub mem: &'a SpaceMem,
    pub old: Old<'a>,
    pub cache: &'a BlockCache,
}

impl<'a> View<'a> {
    /// The entries of `section` from `lo` and before `hi`, `map` the
    /// memtable's of them, the last first if `reverse`.
    fn scan<M>(
        self,
        map: &'a BTreeMap<Vec<u8>, M>,
        section: u8,
        lo: Vec<u8>,
        hi: Vec<u8>,
        reverse: bool,
    ) -> Scan<'a, M> {
        let within = (Bound::Included(&lo[..]), Bound::Excluded(&hi[..]));
        let mem: Box<dyn Iterator<Item = (&'a Vec<u8>, &'a M)> + 'a> = if lo >= hi {
            Box::new(std::iter::empty())
        } else if reverse {
            Box::new(map.range::<[u8], _>(within).rev())
        } else {
            Box::new(map.range::<[u8], _>(within))
        };
        let mut scan = Scan {
            view: self,
            section,
            mem: mem.peekable(),
            rows: (Box::new(std::iter::empty()) as Rows<'a, String>).peekable(),
            lo,
            hi,
            reverse,
        };
        if scan.lo < scan.hi {
            scan.rows = scan.old(if reverse { &scan.hi } else { &scan.lo });
        }
        scan
    }

    /// Every entry of `section`, of every space repo, in order of key.
    pub(super) fn all<M>(self, map: &'a BTreeMap<Vec<u8>, M>, section: u8) -> Scan<'a, M> {
        self.scan(map, section, Vec::new(), END.to_vec(), false)
    }

    /// The record at `path` of the space `uri`: what its `R` entry holds,
    /// and where its frame is, if its bytes are in the log.
    pub fn record(self, uri: &str, path: &str) -> Result<Option<(Meta, Option<Pos>)>, String> {
        let k = space_key(uri, path.as_bytes());
        match self.mem.records.get(&k) {
            Some((r, _)) => Ok(r.as_ref().map(|r| (r.meta.clone(), Some(r.pos)))),
            None if self.mem.skip(RECORDS, &k, false).is_some() => Ok(None),
            None => match self.old.get(&key(RECORDS, &k), self.cache)? {
                None => Ok(None),
                Some(v) => Meta::decode(&v)
                    .map(|m| Some((m, None)))
                    .ok_or_else(|| "a space record's entry that does not parse".into()),
            },
        }
    }

    /// The records of the space `uri` whose paths are within the bounds, in
    /// order of path or the last first: each one's path, what its `R` entry
    /// holds, and where its frame is, if its bytes are in the log.
    pub fn records(
        self,
        uri: &str,
        lo: Bound<&[u8]>,
        hi: Bound<&[u8]>,
        reverse: bool,
    ) -> impl Iterator<Item = Result<(String, Meta, Option<Pos>), String>> + use<'a> {
        let lo = match lo {
            Bound::Unbounded => space_key(uri, b""),
            Bound::Included(x) => space_key(uri, x),
            Bound::Excluded(x) => space_key(uri, &[x, &[0]].concat()),
        };
        let hi = match hi {
            Bound::Unbounded => space_end(uri),
            Bound::Excluded(x) => space_key(uri, x),
            Bound::Included(x) => space_key(uri, &[x, &[0]].concat()),
        };
        let at = uri.len() + 1;
        self.scan(&self.mem.records, RECORDS, lo, hi, reverse)
            .filter_map(move |r| {
                let (k, row) = match r {
                    Ok(x) => x,
                    Err(e) => return Some(Err(e)),
                };
                let found = match row {
                    Row::Mem((None, _)) => return None,
                    Row::Mem((Some(r), _)) => Some((r.meta.clone(), Some(r.pos))),
                    Row::Old(v) => Meta::decode(&v).map(|m| (m, None)),
                };
                Some(match (text(&k[at..]), found) {
                    (Some(path), Some((meta, pos))) => Ok((path, meta, pos)),
                    _ => Err("a space record's entry that does not parse".into()),
                })
            })
    }

    /// The blob references of the records of the space `uri`, from the
    /// blob `from` on, in order of the blob's CID and then the record's
    /// path: each one's CID, path, and the rev that wrote the record.
    pub fn refs(
        self,
        uri: &str,
        from: &[u8],
    ) -> impl Iterator<Item = Result<(String, String, String), String>> + use<'a> {
        let at = uri.len() + 1;
        self.scan(
            &self.mem.refs,
            REFS,
            space_key(uri, from),
            space_end(uri),
            false,
        )
        .filter_map(move |r| {
            let (k, row) = match r {
                Ok(x) => x,
                Err(e) => return Some(Err(e)),
            };
            let rev = match row {
                Row::Mem((None, _)) => return None,
                Row::Mem((Some(rev), _)) => Some(rev.clone()),
                Row::Old(v) => text(&v),
            };
            let parts =
                split(&k[at..]).and_then(|(cid, path)| Some((cid.to_string(), text(path)?)));
            Some(match (parts, rev) {
                (Some((cid, path)), Some(rev)) => Ok((cid, path, rev)),
                _ => Err("a blob reference's entry that does not parse".into()),
            })
        })
    }

    /// Whether a record of the space `uri` references the blob `cid`.
    pub fn refers(self, uri: &str, cid: &str) -> Result<bool, String> {
        let from = [cid.as_bytes(), &[0]].concat();
        match self.refs(uri, &from).next() {
            Some(r) => Ok(r?.0 == cid),
            None => Ok(false),
        }
    }

    /// The operation log of the space `uri` from `from` on, the rest of an
    /// `O` key: each operation of the table's, and each commit of the log's.
    pub fn ops(
        self,
        uri: &str,
        from: &[u8],
    ) -> impl Iterator<Item = Result<Ops, String>> + use<'a> {
        let at = uri.len() + 1;
        self.scan(
            &self.mem.commits,
            OPS,
            space_key(uri, from),
            space_end(uri),
            false,
        )
        .map(move |r| {
            let (k, row) = r?;
            let found = match row {
                Row::Mem((pos, _)) => text(&k[at..]).map(|rev| Ops::Commit(rev, *pos)),
                Row::Old(v) => read_op(&k[at..], &v).map(Ops::Row),
            };
            found.ok_or_else(|| "an operation's entry that does not parse".into())
        })
    }
}

// ---- The store's reads -----------------------------------------------------------------

impl Disk {
    /// Its space repos' sections as they are now.
    pub fn spaces<'a>(&'a self, cache: &'a BlockCache) -> View<'a> {
        View {
            mem: &self.mem.spaces,
            old: match &self.table {
                Some(t) => Old::Table(t, None),
                None => Old::None,
            },
            cache,
        }
    }

    /// The bytes of the record at `path` of the space `uri`, which `meta`
    /// is of: from its frame at `pos`, or with none, from the table.
    pub fn space_bytes(
        &self,
        cache: &BlockCache,
        uri: &str,
        path: &str,
        meta: &Meta,
        pos: Option<Pos>,
    ) -> Arc<[u8]> {
        let found = match pos {
            Some(pos) => {
                let name = record_name(uri, &meta.rev, path);
                self.log_item(cache, pos, Want::SpaceRecord(&name, &meta.cid))
            }
            None => self
                .table_get(cache, &key(VALUES, &space_key(uri, path.as_bytes())))
                .map(Arc::from),
        };
        found.unwrap_or_else(|| self.fail(format!("space record {uri} {path} is not held")))
    }

    /// The operations of the commit at `rev` of the space `uri`, in the frame at `pos`.
    pub fn space_commit(&self, cache: &BlockCache, uri: &str, rev: &str, pos: Pos) -> Vec<Op> {
        let name = ops_name(uri, rev);
        let list = self
            .log_item(cache, pos, Want::SpaceOps(&name))
            .unwrap_or_else(|| self.fail(format!("space commit {uri} {rev} is not held")));
        commit_ops(rev, &list).unwrap_or_else(|e| self.fail(e))
    }

    /// What reads the records of the space `uri` while they change: its
    /// files open, and what the memtable keeps of them now.
    pub fn space_snapshot(&self, uri: &str) -> io::Result<SpaceSnapshot> {
        let table = match &self.table {
            Some(t) => Some((t.clone(), t.file()?)),
            None => None,
        };
        let m = &self.mem.spaces;
        let mem = SpaceMem {
            records: m
                .records
                .range(space_key(uri, b"")..space_end(uri))
                .map(|(k, r)| (k.clone(), r.clone()))
                .collect(),
            voids: m
                .voids
                .get_key_value(uri)
                .map(|(k, v)| (k.clone(), v.clone()))
                .into_iter()
                .collect(),
            ..Default::default()
        };
        let mut logs = HashMap::new();
        for (r, _) in mem.records.values() {
            if let Some(r) = r
                && let std::collections::hash_map::Entry::Vacant(v) = logs.entry(r.pos.generation)
            {
                v.insert((
                    File::open(self.layout.log(r.pos.generation))?,
                    self.number(r.pos.generation),
                ));
            }
        }
        Ok(SpaceSnapshot {
            uri: uri.to_string(),
            table,
            mem,
            logs,
        })
    }
}

/// A space repo's records as they were when taken, read as they are sent.
pub(crate) struct SpaceSnapshot {
    uri: String,
    table: Option<(Arc<Table>, Arc<File>)>,
    /// What the memtable kept of its records, and voided of the table's.
    mem: SpaceMem,
    /// Each log it reads, by generation, and the number the cache holds it by.
    logs: HashMap<u64, (File, u64)>,
}

impl SpaceSnapshot {
    /// Give `emit` each record's path and bytes, in order of path, each
    /// read as it is reached; stop when `emit` says to.
    pub fn run(
        self,
        cache: &BlockCache,
        mut emit: impl FnMut(&[u8], &[u8]) -> bool,
    ) -> io::Result<()> {
        let invalid = |e: String| io::Error::new(io::ErrorKind::InvalidData, e);
        let view = View {
            mem: &self.mem,
            old: match &self.table {
                Some((t, f)) => Old::Table(t, Some(&**f)),
                None => Old::None,
            },
            cache,
        };
        let at = self.uri.len() + 1;
        let (lo, hi) = (space_key(&self.uri, b""), space_end(&self.uri));
        for r in view.scan(&self.mem.records, VALUES, lo, hi, false) {
            let (k, row) = r.map_err(invalid)?;
            let path = &k[at..];
            let bytes = match row {
                Row::Mem((None, _)) => continue,
                Row::Old(v) => v,
                Row::Mem((Some(r), _)) => {
                    let (file, number) = self
                        .logs
                        .get(&r.pos.generation)
                        .ok_or_else(|| io::Error::other("a log not open"))?;
                    let read = |offset: u64, len: usize| read_at(file, offset, len);
                    let path = std::str::from_utf8(path).map_err(|e| invalid(e.to_string()))?;
                    let name = record_name(&self.uri, &r.meta.rev, path);
                    let want = Want::SpaceRecord(&name, &r.meta.cid);
                    frame_item(cache, *number, r.pos, &read, want)
                        .map_err(invalid)?
                        .ok_or_else(|| invalid("a space record missing from its frame".into()))?
                }
            };
            if !emit(path, &bytes) {
                return Ok(());
            }
        }
        Ok(())
    }
}

// ---- Folding -----------------------------------------------------------------------------

/// Give `out` the entries of the space repos' section `section` of the
/// table a fold makes, in order of key: the table's before, but those
/// `mem` voids or changed, and `mem`'s, their bytes read by `item` from the
/// frames they are in.
pub(super) fn fold(
    section: u8,
    view: View<'_>,
    item: &mut Items<'_>,
    out: &mut Put<'_>,
) -> Result<(), String> {
    let mem = view.mem;
    let parts = |k: &[u8]| {
        split(k)
            .and_then(|(uri, rest)| Some((uri.to_string(), text(rest)?)))
            .ok_or_else(|| "a key of the memtable's that does not parse".to_string())
    };
    match section {
        REFS => {
            for r in view.all(&mem.refs, REFS) {
                match r? {
                    (k, Row::Mem((Some(rev), _))) => out(&key(REFS, &k), rev.as_bytes())?,
                    (_, Row::Mem((None, _))) => {}
                    (k, Row::Old(v)) => out(&key(REFS, &k), &v)?,
                }
            }
        }
        OPS => {
            for r in view.all(&mem.commits, OPS) {
                match r? {
                    (k, Row::Old(v)) => out(&key(OPS, &k), &v)?,
                    (k, Row::Mem((pos, _))) => {
                        let (uri, rev) = parts(&k)?;
                        let list = item(*pos, Want::SpaceOps(&ops_name(&uri, &rev)))?.ok_or_else(
                            || format!("space commit {uri} {rev} missing from its frame"),
                        )?;
                        for o in commit_ops(&rev, &list)? {
                            out(&key(OPS, &op_key(&uri, &rev, o.index)), &op_value(&o))?;
                        }
                    }
                }
            }
        }
        _ => {
            for r in view.all(&mem.records, section) {
                match r? {
                    (_, Row::Mem((None, _))) => {}
                    (k, Row::Old(v)) => out(&key(section, &k), &v)?,
                    (k, Row::Mem((Some(r), _))) if section == RECORDS => {
                        out(&key(RECORDS, &k), &r.meta.encode())?
                    }
                    (k, Row::Mem((Some(r), _))) => {
                        let (uri, path) = parts(&k)?;
                        let name = record_name(&uri, &r.meta.rev, &path);
                        let bytes = item(r.pos, Want::SpaceRecord(&name, &r.meta.cid))?
                            .ok_or_else(|| {
                                format!(
                                    "space record {uri} {path} ({}) missing from its frame",
                                    cid_string(&r.meta.cid)
                                )
                            })?;
                        out(&key(VALUES, &k), &bytes)?;
                    }
                }
            }
        }
    }
    Ok(())
}

/// How many entries of the sections `mem` holds, for a table's bloom filter.
pub(super) fn entries(mem: &SpaceMem) -> u64 {
    let ops: u64 = mem.commits.values().map(|(_, n)| u64::from(*n)).sum();
    (mem.records.len() * 2 + mem.refs.len()) as u64 + ops
}

#[cfg(test)]
pub(crate) mod tests {
    use super::*;

    thread_local! {
        /// The table's entries of these sections this thread read: each
        /// one looked up by key, and each one a scan reached.
        pub(crate) static READS: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
    }

    fn void(generation: u64, keep: Option<&[&str]>, refs: bool) -> Void {
        Void {
            generation,
            keep: keep.map(|k| k.iter().map(|p| p.to_string()).collect()),
            refs,
        }
    }

    fn rows(view: View<'_>, uri: &str, reverse: bool) -> Vec<String> {
        view.records(uri, Bound::Unbounded, Bound::Unbounded, reverse)
            .map(|r| r.unwrap().0)
            .collect()
    }

    /// A void keeps what every void of its space keeps, of the table's
    /// entries and of the memtable's before it, in either order of reading,
    /// and no other space's entries are voided; once a table holds a
    /// generation, its voids and entries are let go.
    #[test]
    fn voids_keep_only_what_each_keeps() {
        let (a, b) = ("at://did:plc:a/space/x.y/k", "at://did:plc:a/space/x.y/k2");
        let meta = Meta {
            cid: vec![1; 36],
            rev: "3l3s4fxs7ft22".into(),
            refs: vec![],
        };
        let mut table = BTreeMap::new();
        for (uri, path) in [
            (a, "a.b/1"),
            (a, "keep.it/1"),
            (a, "keep.it/2"),
            (a, "z.z/1"),
            (b, "a.b/1"),
        ] {
            table.insert(
                key(RECORDS, &space_key(uri, path.as_bytes())),
                meta.encode(),
            );
        }
        let dir = crate::testing::scratch("spaces-voids");
        std::fs::create_dir_all(&dir).unwrap();
        let file = dir.join("table");
        let mut w =
            pds_store::table::TableWriter::new(File::create(&file).unwrap(), table.len() as u64);
        for (k, v) in &table {
            w.add(k, v).unwrap();
        }
        w.finish().unwrap();
        let cache = BlockCache::new(1 << 20);
        let table = Table::open(&file, &cache).unwrap();
        let pos = Pos {
            generation: 3,
            offset: 0,
            len: 0,
        };
        let mut mem = SpaceMem::default();
        let put = |mem: &mut SpaceMem, path: &str, g: u64| {
            let r = MemRecord {
                meta: meta.clone(),
                pos: Pos {
                    generation: g,
                    ..pos
                },
            };
            mem.record(a, path, Some(r), g);
        };
        put(&mut mem, "a.b/2", 3);
        put(&mut mem, "keep.it/3", 3);
        mem.record(a, "keep.it/1", None, 3);
        let view = |mem: &'_ SpaceMem| -> Vec<String> {
            let v = View {
                mem,
                old: Old::Table(&table, None),
                cache: &cache,
            };
            let all = rows(v, a, false);
            let mut back = rows(v, a, true);
            back.reverse();
            assert_eq!(all, back);
            for p in [
                "a.b/1",
                "a.b/2",
                "keep.it/1",
                "keep.it/2",
                "keep.it/3",
                "z.z/1",
            ] {
                assert_eq!(
                    v.record(a, p).unwrap().is_some(),
                    all.iter().any(|x| x == p),
                    "{p}"
                );
            }
            assert_eq!(rows(v, b, false), ["a.b/1"]);
            all
        };
        assert_eq!(
            view(&mem),
            ["a.b/1", "a.b/2", "keep.it/2", "keep.it/3", "z.z/1"]
        );
        // Operations alone are void: the records stay.
        mem.void(a, void(3, None, false));
        assert_eq!(view(&mem).len(), 5);
        mem.void(a, void(3, Some(&["keep.it/"]), true));
        assert_eq!(view(&mem), ["keep.it/2", "keep.it/3"]);
        put(&mut mem, "a.b/1", 4);
        assert_eq!(view(&mem), ["a.b/1", "keep.it/2", "keep.it/3"]);
        // A later void that keeps nothing voids what the first kept.
        mem.void(a, void(4, Some(&[]), true));
        assert!(view(&mem).is_empty());
        put(&mut mem, "z.z/9", 4);
        assert_eq!(view(&mem), ["z.z/9"]);
        // A table of generation 4 holds what the logs before it left: what
        // generation 4 voided of it is void still.
        mem.folded(4);
        assert_eq!(mem.voids[a], [void(4, Some(&[]), true)]);
        assert_eq!(view(&mem), ["z.z/9"]);
        mem.folded(5);
        assert!(mem.voids.is_empty() && mem.records.is_empty());
        assert_eq!(mem.cost(), 0);
        assert_eq!(view(&mem), ["a.b/1", "keep.it/1", "keep.it/2", "z.z/1"]);
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// What an entry's value holds is read back as it was written.
    #[test]
    fn values_round_trip() {
        for refs in [vec![], vec!["bafkrei".to_string(), "x".repeat(300)]] {
            let m = Meta {
                cid: vec![7; 36],
                rev: "3l3s4fxs7ft22".into(),
                refs,
            };
            assert_eq!(Meta::decode(&m.encode()), Some(m));
        }
        let uri = "at://did:plc:a/space/x.y/k";
        for (cid, prev) in [(None, Some(vec![2; 36])), (Some(vec![1; 36]), None)] {
            let o = Op {
                rev: "3l3s4fxs7ft22".into(),
                index: 258,
                path: "a.b.c/k".into(),
                cid,
                prev,
            };
            let k = op_key(uri, &o.rev, o.index);
            assert_eq!(read_op(&k[uri.len() + 1..], &op_value(&o)), Some(o));
        }
        assert_eq!(after_prefix("a.b/"), b"a.b0");
    }
}