~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
3574 lines · 132.4 KB Raw History
//! An account's checkpoint, `repo.checkpoint`: a sorted table
//! (`pds_store::table`) of the state its log's frames before a generation
//! leave, read as it is needed, never whole; and what a store holds of the
//! log after it (`Memtable`), where each entry is, not what it holds.
//!
//! **The table's entries**, by key, each section's in order:
//!
//! - `B` and a block's CID: each block of the current tree, MST node or
//!   record: `[refs u32 LE][rev length u8][rev][bytes]`, the count of paths
//!   holding a record (`1` for a node) and the rev of the commit that put it
//!   in the tree;
//! - `C`, a space's URI, a zero byte, a blob's CID as a string, a zero
//!   byte and a record's path: a record of the account's repo in that
//!   space that references the blob: the rev of the commit or import that
//!   last wrote the record;
//! - `D` and a seq, 8 bytes big-endian: an event in the backfill window,
//!   when it was made, milliseconds since the epoch, 8 bytes big-endian;
//! - `E` and a seq: that event's frame;
//! - `H`: the table's generation, the last `seq`, and the greatest seq of
//!   an event let go, each 8 bytes big-endian: what is read of a table
//!   without the rest of its state;
//! - `O`, a space's URI, a zero byte, a commit's rev and an operation's
//!   index in that commit, 4 bytes big-endian: an operation of that space
//!   repo's log: the CID after it and the CID before it, each after its
//!   length, `0` for none, then the record's path;
//! - `P` and a record's path: `[CID length u8][CID][rev]`, the rev of the
//!   commit that last wrote it;
//! - `R`, a space's URI, a zero byte and a record's path: a record of that
//!   space repo: its CID, the rev of the commit or import that last wrote
//!   it, and the CIDs of the blobs it references, each after its length;
//! - `S`: the rest, one DAG-CBOR map (`Small`): the version, the account's
//!   DID, the latest commit's block, the counts of records and blocks of
//!   its tree, the last TID, the handle and a change in flight, the blobs
//!   held with their takedowns, the records' blob refs and how many
//!   records of its space repos reference each blob, with blobs in a
//!   bucket the objects it may keep of blobs not held (`blobstore`), the
//!   records taken down, each space repo's rev and `data`, the lanes of
//!   its LtHash and the counts of its records and operations, the spaces
//!   it is the authority of (as `exportSpaceMeta`'s archives), its write
//!   notifications, and while the log after it is unmarked, the blob
//!   references of the space records it let go (`unmarked`);
//! - `V`, keyed as `R`: that record's bytes.
//!
//! **The log after it** is replayed as the store loads, one frame at a time,
//! into a `Memtable`: each block, path and event the log changed, and of
//! the space repos, each record, commit and blob reference (`spaces`), and
//! where in the log its bytes are. A commit's entry names what it changed
//! of the tree: the nodes it made, with their bytes, those it took out,
//! each record whose count of paths changed, and each record put, with its
//! CID. Bytes are read from the log's frames, or the table, as they are
//! asked for, through the block cache all the stores share (`BlockCache`),
//! which keeps the files of the tables read last open, at most a share of
//! them (`Config::share`). What reads a store's tree after its
//! lock is let go (`Snapshot`) holds the table's file itself, and so reads
//! the table it began with to the end, though a compaction replaces it or
//! the account is deleted meanwhile.
//!
//! **Compacting** (`AccountFold`) merges the table and the sealed logs, in
//! order of key, into the next table, as it reads them: blocks taken out,
//! paths deleted, events out of the window, and what a `clearRecords`, an
//! import or a drop voided of a space repo left out. It holds the state,
//! where each entry of the sealed logs is, and of what it reads, only what
//! it reads again: the places of the frames' items and the blocks records
//! are looked up in, not the table's blocks it passes over once. Once the
//! new table is in place, under the account's lock, the store reads it, and
//! what of the memtable it holds is let go.
//!
//! A log of a server before the tree was changed in place has commits that
//! name only their records: the first load folds it, read whole in memory
//! (`pds_repo::full`), into a table, once. A table of the version before
//! has no `H` (`before`): the first load folds it, with the log after it,
//! into a table of this version, once.
//!
//! **Spaces state is this version's alone** (`unmarked`): what a log holds
//! of spaces before its mark, or a table of the format `before` reads, is
//! let go, but for what its space records reference of blobs until the
//! mark; a table written meanwhile says so, in its `S`, with what it
//! counted.

use crate::blobs::{Blobs, Held};
use crate::cache::unrecoverable;
use crate::identity::Pending;
use crate::space_authority::Authority;
use crate::space_notify::{self, Kept, Schedule};
use crate::space_repo::{self, Restore, Spaces};
use crate::{Account, Store};
use axum::body::Bytes;
use k256::ecdsa::SigningKey;
use pds_repo::data::{V, cid_of, cid_string, decode, encode};
use pds_repo::{Change, Record, Repo, Source, Tids, put_block};
use pds_store::table::{BlockCache, Key, Table, TableWriter, file_number};
use pds_store::{Fold, Layout, Pos};
use serde_json::Value as Json;
use serde_json::value::RawValue;
use spaces::{Old, SpaceMem, View};
use std::collections::{BTreeMap, HashMap, HashSet};
use std::fs::File;
use std::io::{self, Write};
use std::os::unix::fs::FileExt;
use std::path::{Path, PathBuf};
use std::sync::{Arc, Mutex, PoisonError, Weak};
use unmarked::Unmarked;

mod before;
pub(crate) mod spaces;
mod unmarked;

pub(crate) use unmarked::mark;

#[cfg(test)]
pub(crate) use before::tests::downgrade;

/// The format's version: of a table with the space repos' sections, the
/// only one this server writes. One of the version before is read once,
/// to be folded into one of this (`before`).
const VERSION: i64 = 3;

// ---- Keys and values -----------------------------------------------------------

fn key(section: u8, k: &[u8]) -> Vec<u8> {
    let mut out = Vec::with_capacity(1 + k.len());
    out.push(section);
    out.extend_from_slice(k);
    out
}

fn block_value(refs: u32, rev: &str, bytes: &[u8]) -> Vec<u8> {
    let mut out = Vec::with_capacity(5 + rev.len() + bytes.len());
    out.extend_from_slice(&refs.to_le_bytes());
    out.push(rev.len() as u8);
    out.extend_from_slice(rev.as_bytes());
    out.extend_from_slice(bytes);
    out
}

/// A `B` value: the count of paths, the rev, and where the bytes begin.
fn read_block_value(v: &[u8]) -> Option<(u32, &str, usize)> {
    let refs = u32::from_le_bytes(v.get(..4)?.try_into().ok()?);
    let n = *v.get(4)? as usize;
    let rev = std::str::from_utf8(v.get(5..5 + n)?).ok()?;
    Some((refs, rev, 5 + n))
}

fn path_value(cid: &[u8], rev: &str) -> Vec<u8> {
    let mut out = vec![cid.len() as u8];
    out.extend_from_slice(cid);
    out.extend_from_slice(rev.as_bytes());
    out
}

fn read_path_value(v: &[u8]) -> Option<(Vec<u8>, String)> {
    let n = *v.first()? as usize;
    Some((
        v.get(1..1 + n)?.to_vec(),
        String::from_utf8(v.get(1 + n..)?.to_vec()).ok()?,
    ))
}

fn hex_of(x: &Json) -> Result<Vec<u8>, String> {
    x.as_str()
        .and_then(|h| hex::decode(h).ok())
        .ok_or_else(|| format!("{x} for hex"))
}

/// The `H` value: the table's generation, the last `seq`, and the greatest
/// seq of an event let go, each 8 bytes big-endian.
fn header_value(generation: u64, last_seq: u64, let_go: u64) -> Vec<u8> {
    [generation, last_seq, let_go]
        .iter()
        .flat_map(|n| n.to_be_bytes())
        .collect()
}

fn read_header(v: &[u8]) -> Option<(u64, u64, u64)> {
    let n = |i: usize| {
        Some(u64::from_be_bytes(
            v.get(i * 8..i * 8 + 8)?.try_into().ok()?,
        ))
    };
    (v.len() == 24).then_some(())?;
    Some((n(0)?, n(1)?, n(2)?))
}

// ---- The rest of the state -------------------------------------------------------

/// What a checkpoint keeps besides the tree, the events and the space
/// repos' records and operations, in its `S` and its `H`, and what the
/// log's other entries change.
pub(crate) struct Small {
    /// The generation of the table it was read from.
    pub generation: u64,
    /// The latest commit's block; empty before the first.
    pub head: Vec<u8>,
    pub counts: (u64, u64),
    pub tids: Tids,
    pub blobs: Blobs,
    /// Its records taken down, by path, each with its takedown's reference.
    pub takedowns: BTreeMap<String, String>,
    /// Each space repo's commit, hash and counts.
    pub spaces: Spaces,
    pub authority: Authority,
    pub notify: Kept,
    /// The handle its last landed change gave it.
    pub handle: Option<String>,
    /// A handle change recorded and not settled.
    pub pending: Option<Pending>,
    /// The `seq` of its latest event, `0` if it never had one.
    pub last_seq: u64,
    /// The greatest `seq` of an event of its let go as out of the backfill
    /// window when its log was compacted, `0` if none was: the firehose
    /// tells a subscriber that missed it so, though nothing else holds it.
    pub let_go: u64,
    /// Until its spaces state is this version's, at its mark: the blob
    /// references of the space records it let go (`unmarked`).
    pub unmarked: Option<Unmarked>,
}

impl Small {
    /// The state before any of a log with no table: unmarked.
    pub(crate) fn new() -> Small {
        Small {
            generation: 0,
            head: Vec::new(),
            counts: (0, 0),
            tids: Tids::new(),
            blobs: Blobs::default(),
            takedowns: BTreeMap::new(),
            spaces: Spaces::default(),
            authority: Authority::default(),
            notify: Kept::default(),
            handle: None,
            pending: None,
            last_seq: 0,
            let_go: 0,
            unmarked: Some(Unmarked::default()),
        }
    }

    /// Its spaces state this version's from here on: the blob references
    /// of the space records it let go go too, as a drop's do, and a blob
    /// only they held is no longer held (`unmarked`).
    pub(crate) fn mark(&mut self) {
        if self.unmarked.take().is_some() {
            let delta = self
                .blobs
                .space_ref_list()
                .into_iter()
                .map(|(cid, n)| (cid.to_string(), -i64::from(n)))
                .collect();
            self.blobs.space_counted(delta);
        }
    }

    fn has_commit(&self) -> bool {
        !self.head.is_empty()
    }

    /// Replay one entry of the log but a commit's or an event's, or a space
    /// repo's while its spaces state is this version's.
    fn replay(&mut self, e: &Json, holds: impl Fn(&str) -> bool) -> Result<(), String> {
        let text = |k: &str| {
            e[k].as_str()
                .map(str::to_string)
                .ok_or_else(|| format!("a log entry with no {k}: {e}"))
        };
        match e["t"].as_str() {
            Some("handle") => {
                if self.pending.is_some() || !self.has_commit() {
                    return Err(format!("a handle change while none could be made: {e}"));
                }
                self.pending = Some(Pending {
                    handle: text("handle")?,
                    cid: text("cid")?,
                });
            }
            Some("handled") => {
                let (Some(p), Some(landed)) = (self.pending.take(), e["landed"].as_bool()) else {
                    return Err(format!("a handle change settled that was not made: {e}"));
                };
                if e["cid"] != p.cid {
                    return Err(format!(
                        "a handle change settled that was not the one made: {e}"
                    ));
                }
                if landed {
                    self.handle = Some(p.handle);
                }
            }
            Some(t) if crate::blobs::ENTRIES.contains(&t) => self.blobs.replay(e)?,
            Some(crate::lifecycle::RECORD_TAKEDOWN) => {
                let p = text("path")?;
                match &e["ref"] {
                    Json::String(r) if holds(&p) => self.takedowns.insert(p, r.clone()),
                    Json::Null => self.takedowns.remove(&p),
                    _ => {
                        return Err(format!(
                            "a takedown of a record not held, or with a ref not a string: {e}"
                        ));
                    }
                };
            }
            Some(unmarked::MARK) => {
                if e["v"] != unmarked::MARK_VERSION {
                    return Err(format!("a mark of spaces of no known version: {e}"));
                }
                self.mark();
            }
            Some(t) if unmarked::of_spaces(t) && self.unmarked.is_some() => {
                if let Some(u) = &mut self.unmarked {
                    u.replay(e, &mut self.blobs, &mut self.tids);
                }
            }
            Some(t) if crate::space_authority::ENTRIES.contains(&t) => self.authority.replay(e)?,
            Some(t) if space_notify::ENTRIES.contains(&t) => self.notify.replay(e)?,
            t => return Err(format!("a log entry of no known type: {t:?}")),
        }
        Ok(())
    }

    /// The `S` value of a table: write notifications past their horizon at
    /// `now_ms` left out.
    fn encode(&self, did: &str, now_ms: u64) -> Vec<u8> {
        let spaces = self.spaces.saved().map(|r| {
            map([
                ("space", text(r.space)),
                ("rev", text(r.rev)),
                ("data", V::Bytes(r.data.to_vec())),
                ("hash", V::Bytes(r.hash)),
                ("records", int(r.records)),
                ("ops", int(r.ops)),
            ])
        });
        let n = &self.notify;
        let queue = n
            .queue
            .iter()
            .filter(|(_, p)| p.at.until >= now_ms)
            .map(|(space, p)| {
                map([
                    ("space", text(space)),
                    ("rev", text(&p.rev)),
                    ("data", V::Bytes(p.data.clone())),
                    ("n", int(p.at.n.into())),
                    ("due", int(p.at.due)),
                    ("until", int(p.at.until)),
                ])
            });
        // Every registration, lapsed ones too: one ends only when dropped.
        let registrations = n.registered.iter().flat_map(|(space, pairs)| {
            pairs.iter().map(move |((endpoint, token), r)| {
                map([
                    ("space", text(space)),
                    ("endpoint", text(endpoint)),
                    ("token", text(token)),
                    ("expires", int(r.expires)),
                    ("noticed", V::Bool(r.noticed)),
                ])
            })
        });
        let notices = n.notices.iter().map(|((space, (endpoint, token)), x)| {
            let (update, space_rev, lapse) = match &x.owed {
                space_notify::Owed::Deleted => ("deleted", V::Null, V::Null),
                space_notify::Owed::Expired { space_rev, lapse } => {
                    ("expired", text(space_rev), int(*lapse))
                }
            };
            map([
                ("space", text(space)),
                ("endpoint", text(endpoint)),
                ("token", text(token)),
                ("update", text(update)),
                ("spaceRev", space_rev),
                ("lapse", lapse),
                ("n", int(x.at.n.into())),
                ("due", int(x.at.due)),
                ("until", int(x.at.until)),
            ])
        });
        let mut state = map([
            ("version", V::Int(VERSION)),
            ("did", text(did)),
            (
                "commit",
                if self.head.is_empty() {
                    V::Null
                } else {
                    V::Bytes(self.head.clone())
                },
            ),
            (
                "counts",
                V::Arr(vec![int(self.counts.0), int(self.counts.1)]),
            ),
            ("tid", V::Str(self.tids.last())),
            ("handle", or_null(self.handle.as_deref(), text)),
            (
                "pending",
                or_null(self.pending.as_ref(), |p| {
                    map([("handle", text(&p.handle)), ("cid", text(&p.cid))])
                }),
            ),
            (
                "blobs",
                V::Arr(
                    self.blobs
                        .held_list()
                        .map(|(cid, h, takedown)| {
                            map([
                                ("cid", text(cid)),
                                ("mimeType", text(&h.mime)),
                                ("size", int(h.size)),
                                ("at", int(h.at)),
                                ("takedown", or_null(takedown, text)),
                            ])
                        })
                        .collect(),
                ),
            ),
            (
                "blobRecords",
                V::Arr(
                    self.blobs
                        .record_list()
                        .into_iter()
                        .map(|(p, rev, cids)| {
                            V::Arr(vec![
                                text(p),
                                text(rev),
                                V::Arr(cids.iter().map(|c| text(c)).collect()),
                            ])
                        })
                        .collect(),
                ),
            ),
            (
                "spaceRefs",
                V::Arr(
                    self.blobs
                        .space_ref_list()
                        .into_iter()
                        .map(|(cid, n)| V::Arr(vec![text(cid), int(n.into())]))
                        .collect(),
                ),
            ),
            (
                "takedowns",
                V::Arr(
                    self.takedowns
                        .iter()
                        .map(|(path, r)| map([("path", text(path)), ("ref", text(r))]))
                        .collect(),
                ),
            ),
            ("spaces", V::Arr(spaces.collect())),
            (
                "authority",
                V::Arr(
                    self.authority
                        .saved()
                        .map(|(space, archive)| {
                            map([
                                ("space", text(space)),
                                ("archive", or_null(archive, V::Bytes)),
                            ])
                        })
                        .collect(),
                ),
            ),
            (
                "notify",
                map([
                    ("queue", V::Arr(queue.collect())),
                    ("registrations", V::Arr(registrations.collect())),
                    ("notices", V::Arr(notices.collect())),
                ]),
            ),
        ]);
        if let V::Map(m) = &mut state {
            // With blobs in a bucket, the objects it may keep of blobs not held.
            if let Some(objects) = self.blobs.objects_list() {
                m.push((
                    "objects".into(),
                    V::Arr(objects.into_iter().map(text).collect()),
                ));
            }
            // Unmarked: the blob references of the space records let go.
            if let Some(u) = &self.unmarked {
                let records = u.saved().map(|(space, path, cids)| {
                    V::Arr(vec![
                        text(space),
                        text(path),
                        V::Arr(cids.iter().map(|c| text(c)).collect()),
                    ])
                });
                m.push(("unmarked".into(), V::Arr(records.collect())));
            }
        }
        encode(&state)
    }

    /// Read an `S` value and its table's `H`: everything checked, as
    /// `encode` and `header_value` write them, and that it is of the
    /// account `did`.
    fn decode(bytes: &[u8], header: &[u8], did: &str) -> Result<Small, String> {
        let state = decode(bytes).map_err(|e| format!("the state: {e}"))?;
        let header = read_header(header).ok_or("a header that does not parse")?;
        Small::of(state, header, did)
    }

    /// The state an `S` value holds, decoded, with what its table's `H`
    /// holds: the table's generation, the last `seq`, and the greatest seq
    /// let go.
    fn of(
        mut state: V,
        (generation, last_seq, let_go): (u64, u64, u64),
        did: &str,
    ) -> Result<Small, String> {
        let mut optional = |k: &str| match &mut state {
            V::Map(m) => m
                .iter()
                .position(|(n, _)| n == k)
                .map(|i| m.swap_remove(i).1),
            _ => None,
        };
        let (objects, unmarked) = (optional("objects"), optional("unmarked"));
        let objects = or_none(objects.unwrap_or(V::Null), |v| {
            as_list(v, "objects")?
                .into_iter()
                .map(|c| as_text(c, "an object"))
                .collect::<Result<Vec<_>, _>>()
        })?;
        let unmarked = or_none(unmarked.unwrap_or(V::Null), |v| {
            let mut u = Unmarked::default();
            for x in as_list(v, "unmarked")? {
                let [space, path, cids] = as_list(x, "an unmarked record")?
                    .try_into()
                    .map_err(|_| "an unmarked record not three")?;
                let cids = as_list(cids, "an unmarked record's blob refs")?
                    .into_iter()
                    .map(|c| as_text(c, "a blob ref"))
                    .collect::<Result<Vec<_>, _>>()?;
                u.restore(
                    as_text(space, "an unmarked record's space")?,
                    as_text(path, "an unmarked record's path")?,
                    cids,
                )?;
            }
            Ok(u)
        })?;
        let [
            version,
            state_did,
            commit,
            counts,
            tid,
            handle,
            pending,
            blobs,
            blob_records,
            space_refs,
            takedowns,
            spaces,
            authority,
            notify,
        ] = fields(
            state,
            [
                "version",
                "did",
                "commit",
                "counts",
                "tid",
                "handle",
                "pending",
                "blobs",
                "blobRecords",
                "spaceRefs",
                "takedowns",
                "spaces",
                "authority",
                "notify",
            ],
            "the state",
        )?;
        if version != V::Int(VERSION) {
            return Err(format!(
                "a checkpoint of version {version:?}, which this server does not know"
            ));
        }
        if as_text(state_did, "did")? != did {
            return Err("a checkpoint of another account".into());
        }
        let mut s = Small::new();
        (s.generation, s.last_seq, s.let_go) = (generation, last_seq, let_go);
        s.head = or_none(commit, |v| as_bytes(v, "commit"))?.unwrap_or_default();
        let (records, blocks) = as_pair(counts, "counts")?;
        s.counts = (as_uint(records, "a count")?, as_uint(blocks, "a count")?);
        s.tids.after(&as_text(tid, "tid")?);
        s.handle = or_none(handle, |v| as_text(v, "handle"))?;
        s.pending = or_none(pending, |v| {
            let [handle, cid] = fields(v, ["handle", "cid"], "pending")?;
            Ok(Pending {
                handle: as_text(handle, "pending's handle")?,
                cid: as_text(cid, "pending's cid")?,
            })
        })?;
        let mut held = Vec::new();
        for x in as_list(blobs, "blobs")? {
            let [cid, mime, size, at, takedown] =
                fields(x, ["cid", "mimeType", "size", "at", "takedown"], "a blob")?;
            let h = Held {
                mime: as_text(mime, "a blob's mimeType")?,
                size: as_uint(size, "a blob's size")?,
                at: as_uint(at, "a blob's at")?,
            };
            held.push((
                as_text(cid, "a blob's cid")?,
                h,
                or_none(takedown, |v| as_text(v, "a blob's takedown"))?,
            ));
        }
        if !ascending(held.iter().map(|(cid, _, _)| cid.as_str())) {
            return Err("blobs out of order".into());
        }
        let mut records = Vec::new();
        for x in as_list(blob_records, "blobRecords")? {
            let [path, rev, cids] = as_list(x, "a record's blob refs")?
                .try_into()
                .map_err(|_| "a record's blob refs not three")?;
            let cids = as_list(cids, "a record's blob refs")?
                .into_iter()
                .map(|c| as_text(c, "a blob ref"))
                .collect::<Result<Vec<_>, _>>()?;
            records.push((
                as_text(path, "a record's path")?,
                as_text(rev, "a record's rev")?,
                cids,
            ));
        }
        if !ascending(records.iter().map(|(p, _, _)| p.as_str())) {
            return Err("blob refs out of order".into());
        }
        let mut counted = Vec::new();
        for x in as_list(space_refs, "spaceRefs")? {
            let (cid, n) = as_pair(x, "a space blob ref")?;
            let n = u32::try_from(as_uint(n, "a space blob ref's count")?)
                .ok()
                .filter(|n| *n > 0)
                .ok_or("a space blob ref's count out of range")?;
            counted.push((as_text(cid, "a space blob ref's cid")?, n));
        }
        if !ascending(counted.iter().map(|(cid, _)| cid.as_str())) {
            return Err("space blob refs out of order".into());
        }
        s.blobs = Blobs::restore(records, held, objects, counted)?;
        let mut last: Option<String> = None;
        for x in as_list(takedowns, "takedowns")? {
            let [path, r] = fields(x, ["path", "ref"], "a takedown")?;
            let path = as_text(path, "a takedown's path")?;
            if last.as_ref().is_some_and(|l| *l >= path) {
                return Err("takedowns out of order".into());
            }
            last = Some(path.clone());
            s.takedowns.insert(path, as_text(r, "a takedown's ref")?);
        }
        let mut last: Option<String> = None;
        for x in as_list(spaces, "spaces")? {
            let [space, rev, data, hash, records, ops] = fields(
                x,
                ["space", "rev", "data", "hash", "records", "ops"],
                "a space",
            )?;
            let space = as_text(space, "a space's space")?;
            if last.as_ref().is_some_and(|l| *l >= space) {
                return Err("spaces out of order".into());
            }
            last = Some(space.clone());
            let data: [u8; 32] = as_bytes(data, "a space's data")?
                .try_into()
                .map_err(|_| format!("space {space}'s data, not 32 bytes"))?;
            let restore = Restore {
                rev: as_text(rev, "a space's rev")?,
                data,
                hash: as_bytes(hash, "a space's hash")?,
                records: as_uint(records, "a space's records")?,
                ops: as_uint(ops, "a space's ops")?,
                space,
            };
            s.spaces.restore(restore, &mut s.tids)?;
        }
        let mut spaces_held = Vec::new();
        for x in as_list(authority, "authority")? {
            let [space, archive] = fields(x, ["space", "archive"], "an authority's space")?;
            spaces_held.push((
                as_text(space, "an authority's space")?,
                or_none(archive, |v| as_bytes(v, "an archive"))?,
            ));
        }
        if !ascending(spaces_held.iter().map(|(s, _)| s.as_str())) {
            return Err("authority out of order".into());
        }
        for (space, archive) in spaces_held {
            s.authority.restore(did, &space, archive.as_deref())?;
        }
        s.notify = read_notify(notify)?;
        s.unmarked = unmarked;
        Ok(s)
    }
}

fn int(n: u64) -> V {
    V::Int(i64::try_from(n).unwrap_or(i64::MAX))
}

fn text(s: &str) -> V {
    V::Str(s.to_string())
}

fn or_null<T>(x: Option<T>, f: impl FnOnce(T) -> V) -> V {
    x.map_or(V::Null, f)
}

fn map<const N: usize>(fields: [(&str, V); N]) -> V {
    V::Map(
        fields
            .into_iter()
            .map(|(k, v)| (k.to_string(), v))
            .collect(),
    )
}

/// A map's values of exactly these keys, in their order.
fn fields<const N: usize>(v: V, names: [&str; N], what: &str) -> Result<[V; N], String> {
    let V::Map(mut m) = v else {
        return Err(format!("{what} is not a map"));
    };
    let got = names.map(|k| {
        m.iter()
            .position(|(n, _)| n == k)
            .map(|i| m.swap_remove(i).1)
    });
    if !m.is_empty() || got.iter().any(Option::is_none) {
        return Err(format!(
            "{what} is not a map of exactly {}",
            names.join(", ")
        ));
    }
    Ok(got.map(|x| x.unwrap_or(V::Null)))
}

fn as_text(v: V, what: &str) -> Result<String, String> {
    if let V::Str(s) = v {
        Ok(s)
    } else {
        Err(format!("{what} is not a string"))
    }
}

fn as_uint(v: V, what: &str) -> Result<u64, String> {
    match v {
        V::Int(n) if n >= 0 => Ok(n as u64),
        _ => Err(format!("{what} is not a number of 0 or more")),
    }
}

fn as_bytes(v: V, what: &str) -> Result<Vec<u8>, String> {
    if let V::Bytes(b) = v {
        Ok(b)
    } else {
        Err(format!("{what} is not bytes"))
    }
}

fn as_list(v: V, what: &str) -> Result<Vec<V>, String> {
    if let V::Arr(a) = v {
        Ok(a)
    } else {
        Err(format!("{what} is not a list"))
    }
}

fn as_pair(v: V, what: &str) -> Result<(V, V), String> {
    match as_list(v, what)?.try_into() {
        Ok::<[V; 2], _>([a, b]) => Ok((a, b)),
        Err(_) => Err(format!("{what} is not a pair")),
    }
}

fn or_none<T>(v: V, f: impl FnOnce(V) -> Result<T, String>) -> Result<Option<T>, String> {
    if v == V::Null {
        Ok(None)
    } else {
        f(v).map(Some)
    }
}

/// Whether keys are in strictly ascending order.
fn ascending<K: PartialOrd>(keys: impl IntoIterator<Item = K>) -> bool {
    let mut last: Option<K> = None;
    for k in keys {
        if last.as_ref().is_some_and(|l| *l >= k) {
            return false;
        }
        last = Some(k);
    }
    true
}

/// The notifications' state (`space_notify::Kept`), as `Small::encode`
/// writes it.
fn read_notify(v: V) -> Result<Kept, String> {
    let [queue, registrations, notices] =
        fields(v, ["queue", "registrations", "notices"], "notify")?;
    let schedule = |n: V, due: V, until: V, what: &str| -> Result<Schedule, String> {
        let n =
            u32::try_from(as_uint(n, what)?).map_err(|_| format!("{what}: an attempt too many"))?;
        Ok(Schedule {
            n,
            due: as_uint(due, what)?,
            until: as_uint(until, what)?,
        })
    };
    let mut kept = Kept::default();
    for x in as_list(queue, "notify's queue")? {
        let [space, rev, data, n, due, until] = fields(
            x,
            ["space", "rev", "data", "n", "due", "until"],
            "a queue entry",
        )?;
        let space = as_text(space, "a queue entry's space")?;
        if kept
            .queue
            .last_key_value()
            .is_some_and(|(l, _)| *l >= space)
        {
            return Err("notify's queue out of order".into());
        }
        let at = schedule(n, due, until, "a queue entry")?;
        let p = space_notify::Pending {
            rev: as_text(rev, "a queue entry's rev")?,
            data: as_bytes(data, "a queue entry's data")?,
            at,
        };
        kept.queue.insert(space, p);
    }
    let mut last: Option<(String, String, String)> = None;
    for x in as_list(registrations, "notify's registrations")? {
        let [space, endpoint, token, expires, noticed] = fields(
            x,
            ["space", "endpoint", "token", "expires", "noticed"],
            "a registration",
        )?;
        let key = (
            as_text(space, "a registration's space")?,
            as_text(endpoint, "a registration's endpoint")?,
            as_text(token, "a registration's token")?,
        );
        if last.as_ref().is_some_and(|l| *l >= key) {
            return Err("notify's registrations out of order".into());
        }
        last = Some(key.clone());
        let V::Bool(noticed) = noticed else {
            return Err("a registration's noticed is not a boolean".into());
        };
        let r = space_notify::Registration {
            expires: as_uint(expires, "a registration's expiry")?,
            noticed,
        };
        kept.register(key.0, (key.1, key.2), r);
    }
    for x in as_list(notices, "notify's notices")? {
        let [
            space,
            endpoint,
            token,
            update,
            space_rev,
            lapse,
            n,
            due,
            until,
        ] = fields(
            x,
            [
                "space", "endpoint", "token", "update", "spaceRev", "lapse", "n", "due", "until",
            ],
            "a notice",
        )?;
        let key = (
            as_text(space, "a notice's space")?,
            (
                as_text(endpoint, "a notice's endpoint")?,
                as_text(token, "a notice's token")?,
            ),
        );
        if kept
            .notices
            .last_key_value()
            .is_some_and(|(l, _)| *l >= key)
        {
            return Err("notify's notices out of order".into());
        }
        let owed = match as_text(update, "a notice's update")?.as_str() {
            "deleted" => space_notify::Owed::Deleted,
            "expired" => space_notify::Owed::Expired {
                space_rev: as_text(space_rev, "a notice's spaceRev")?,
                lapse: as_uint(lapse, "a notice's lapse")?,
            },
            u => return Err(format!("a notice of no known kind {u}")),
        };
        let at = schedule(n, due, until, "a notice")?;
        kept.notices.insert(key, space_notify::Notice { owed, at });
    }
    Ok(kept)
}

// ---- The log after the table -------------------------------------------------------

/// Where a block's bytes are: in the table, or in a frame of the log.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum At {
    Table,
    Log(Pos),
}

/// A block the log changed: the rev that put it in the tree, its count of
/// paths, where its bytes are, `None` once it left the tree, and the
/// generation of the log that last changed it.
#[derive(Clone, Debug)]
pub(crate) struct MemBlock {
    pub rev: Arc<str>,
    pub refs: u32,
    pub at: Option<At>,
    pub generation: u64,
}

/// A record as a path has it: its CID and the rev that wrote it.
pub(crate) type Written = (Vec<u8>, Arc<str>);

/// The rows of a table or what stands for them, in order of key, each read
/// as it is reached.
type Rows<'a, E> = Box<dyn Iterator<Item = Result<(Vec<u8>, Vec<u8>), E>> + 'a>;

/// What `events_on_disk` answers: each event's seq and when it was made, the
/// greatest seq any event has had, and the greatest of those let go.
pub(crate) type EventsOnDisk = (Vec<(u64, u64)>, u64, u64);

/// What the log after the table changed, and where in it: of the tree's
/// blocks and paths, of the events, and of the space repos.
#[derive(Default)]
pub(crate) struct Memtable {
    pub blocks: HashMap<Vec<u8>, MemBlock>,
    /// Each path: its record's CID and the rev that wrote it, or none once
    /// deleted, and the generation that last changed it.
    pub paths: BTreeMap<String, (Option<Written>, u64)>,
    /// Each event: when it was made, and its frame's place.
    pub events: BTreeMap<u64, (u64, Pos)>,
    /// What it changed of the space repos' records, operations and blob
    /// references.
    pub spaces: SpaceMem,
    /// Whether the log holds a commit of the kind before the tree was
    /// changed in place, which names only its records.
    pub legacy: bool,
    /// The bytes its blocks and paths are counted as in the cache.
    keys: u64,
}

/// A commit entry's parts the memtable keeps.
struct Commit<'a> {
    rev: &'a str,
    puts: Vec<(String, Vec<u8>)>,
    dels: Vec<String>,
    tree: Vec<Vec<u8>>,
    gone: Vec<Vec<u8>>,
    refs: Vec<(Vec<u8>, u32, String)>,
}

impl Memtable {
    /// The bytes it is counted as in the cache.
    pub fn cost(&self) -> u64 {
        self.keys + self.events.len() as u64 * 64 + self.spaces.cost()
    }

    fn block(&mut self, cid: Vec<u8>, b: MemBlock) {
        let cost = cid.len() as u64 + 120;
        if self.blocks.insert(cid, b).is_none() {
            self.keys += cost;
        }
    }

    fn path(&mut self, path: String, written: Option<Written>, generation: u64) {
        let cost = path.len() as u64 * 2 + 120;
        if self.paths.insert(path, (written, generation)).is_none() {
            self.keys += cost;
        }
    }

    fn put_commit(&mut self, pos: Pos, c: Commit) {
        let g = pos.generation;
        let rev: Arc<str> = Arc::from(c.rev);
        let gone = |rev: &Arc<str>| MemBlock {
            rev: rev.clone(),
            refs: 0,
            at: None,
            generation: g,
        };
        for cid in c.tree {
            let b = MemBlock {
                rev: rev.clone(),
                refs: 1,
                at: Some(At::Log(pos)),
                generation: g,
            };
            self.block(cid, b);
        }
        for cid in c.gone {
            self.block(cid, gone(&rev));
        }
        // An import puts every record in one commit: each looked up, not
        // searched for among the others.
        let put: HashSet<&[u8]> = c.puts.iter().map(|(_, p)| p.as_slice()).collect();
        for (cid, n, added) in c.refs {
            if n == 0 {
                self.block(cid, gone(&rev));
                continue;
            }
            let here = put.contains(cid.as_slice());
            let at = match self.blocks.get(&cid) {
                _ if here => At::Log(pos),
                Some(MemBlock { at: Some(at), .. }) => *at,
                _ => At::Table,
            };
            let b = MemBlock {
                rev: Arc::from(added.as_str()),
                refs: n,
                at: Some(at),
                generation: g,
            };
            self.block(cid, b);
        }
        for (path, cid) in c.puts {
            self.path(path, Some((cid, rev.clone())), g);
        }
        for path in c.dels {
            self.path(path, None, g);
        }
    }

    /// A commit made and logged in the frame at `pos`.
    pub fn commit(&mut self, pos: Pos, c: &Change) {
        let puts = c
            .puts
            .iter()
            .map(|(p, _)| p.clone())
            .zip(c.put_cids.iter().cloned())
            .collect();
        let refs = c.refs.clone();
        self.put_commit(
            pos,
            Commit {
                rev: &c.rev,
                puts,
                dels: c.dels.clone(),
                tree: c.tree.iter().map(|(cid, _)| cid.clone()).collect(),
                gone: c.gone.clone(),
                refs,
            },
        );
    }

    /// An event logged in the frame at `pos`, made at `time`.
    pub fn event(&mut self, seq: u64, time: u64, pos: Pos) {
        self.events.insert(seq, (time, pos));
    }

    /// Let go of what the log's generations before `generation` changed,
    /// which a table of that generation holds; a block a later log changed
    /// but whose bytes are in one of those is read from the table now.
    fn folded(&mut self, generation: u64) {
        self.blocks.retain(|_, b| b.generation >= generation);
        for b in self.blocks.values_mut() {
            if matches!(b.at, Some(At::Log(p)) if p.generation < generation) {
                b.at = Some(At::Table);
            }
        }
        self.paths.retain(|_, p| p.1 >= generation);
        self.events.retain(|_, e| e.1.generation >= generation);
        let blocks: usize = self.blocks.keys().map(|k| k.len() + 120).sum();
        let paths: usize = self.paths.keys().map(|k| k.len() * 2 + 120).sum();
        self.keys = (blocks + paths) as u64;
        self.spaces.folded(generation);
    }

    /// Replay an entry of the frame at `pos`: a commit's, an event's, a
    /// space repo's, or one of `small`'s; `holds` says whether a path holds
    /// a record, and `old` is the table's entries of the space repos.
    fn apply(
        &mut self,
        small: &mut Small,
        pos: Pos,
        e: &Json,
        holds: &dyn Fn(&Memtable, &str) -> bool,
        old: Old<'_>,
        cache: &BlockCache,
    ) -> Result<(), String> {
        let text = |k: &str| {
            e[k].as_str()
                .ok_or_else(|| format!("a log entry with no {k}: {e}"))
        };
        let list = |k: &str| {
            e[k].as_array()
                .ok_or_else(|| format!("a commit with no {k}"))
        };
        match e["t"].as_str() {
            Some("event") => {
                let Some(seq) = e["seq"].as_u64() else {
                    return Err(format!("an event with no seq: {e}"));
                };
                if self
                    .events
                    .last_key_value()
                    .is_some_and(|(last, _)| *last >= seq)
                    || seq <= small.last_seq
                    || !small.has_commit()
                {
                    return Err(format!("event {seq} out of order"));
                }
                let time = match e["time"].as_u64() {
                    Some(t) => t,
                    None => crate::events::event_time(&hex_of(&e["frame"])?).unwrap_or(0),
                };
                self.events.insert(seq, (time, pos));
                small.last_seq = seq;
            }
            Some("commit") => {
                let rev = text("rev")?;
                let head = hex_of(&e["head"])?;
                let path = |p: &Json| {
                    p.as_str()
                        .map(str::to_string)
                        .ok_or_else(|| format!("a commit with {p} for a path"))
                };
                let dels: Vec<String> = list("dels")?.iter().map(path).collect::<Result<_, _>>()?;
                let mut puts: Vec<(String, Json)> = Vec::new();
                let mut put_cids = Vec::new();
                for p in list("puts")? {
                    puts.push((path(&p[0])?, p[1].clone()));
                    if !p[2].is_null() {
                        put_cids.push(hex_of(&p[2])?);
                    }
                }
                let change = Change {
                    rev: rev.to_string(),
                    puts,
                    dels: dels.clone(),
                    ..Default::default()
                };
                small.blobs.committed(&change);
                small.blobs.take_doomed();
                for p in &dels {
                    small.takedowns.remove(p);
                }
                small.tids.after(rev);
                small.head = head;
                if e.get("tree").is_none() {
                    self.legacy = true;
                    return Ok(());
                }
                if put_cids.len() != change.puts.len() {
                    return Err(format!("a commit whose puts name no CID: {rev}"));
                }
                // What the log holds is what its commits signed.
                for ((p, value), cid) in change.puts.iter().zip(&put_cids) {
                    let bytes = put_block(value).map_err(|why| format!("record {p}: {why}"))?;
                    if cid_of(0x71, &bytes) != *cid {
                        return Err(format!("record {p}, which the commit {rev} does not sign"));
                    }
                }
                let counts = list("counts")?;
                small.counts = (
                    counts
                        .first()
                        .and_then(Json::as_u64)
                        .ok_or("a commit with no counts")?,
                    counts
                        .get(1)
                        .and_then(Json::as_u64)
                        .ok_or("a commit with no counts")?,
                );
                let mut tree = Vec::new();
                for x in list("tree")? {
                    let cid = hex_of(&x[0])?;
                    if cid_of(0x71, &hex_of(&x[1])?) != cid {
                        return Err(format!(
                            "a tree node {}, which the commit {rev} does not sign",
                            cid_string(&cid)
                        ));
                    }
                    tree.push(cid);
                }
                let gone = list("gone")?
                    .iter()
                    .map(hex_of)
                    .collect::<Result<Vec<_>, _>>()?;
                let mut refs = Vec::new();
                for r in list("refs")? {
                    let n = r[1]
                        .as_u64()
                        .and_then(|n| u32::try_from(n).ok())
                        .ok_or_else(|| format!("a commit with a bad count: {r}"))?;
                    refs.push((
                        hex_of(&r[0])?,
                        n,
                        r[2].as_str().ok_or("a count with no rev")?.to_string(),
                    ));
                }
                let puts = change
                    .puts
                    .into_iter()
                    .map(|(p, _)| p)
                    .zip(put_cids)
                    .collect();
                self.put_commit(
                    pos,
                    Commit {
                        rev,
                        puts,
                        dels,
                        tree,
                        gone,
                        refs,
                    },
                );
            }
            Some(space_repo::ENTRY | space_repo::IMPORT | space_repo::DROP)
                if small.unmarked.is_none() =>
            {
                small.spaces.replay(
                    e,
                    pos,
                    &mut self.spaces,
                    old,
                    cache,
                    &mut small.tids,
                    &mut small.blobs,
                )?
            }
            _ => small.replay(e, |p| holds(self, p))?,
        }
        Ok(())
    }
}

/// An item of a frame, as its payload has it: unparsed, borrowed from it.
enum Raw<'a> {
    /// A tree node: its CID in hex, and its bytes.
    Node(&'a str, Data<'a>),
    /// A record put: its CID in hex, and its value as JSON.
    Record(&'a str, &'a RawValue),
    /// An event: its seq, and its frame.
    Event(u64, Data<'a>),
    /// A space record put, or a space commit's operations: its class in an
    /// index, its name there (`spaces::record_name`, `spaces::ops_name`),
    /// how it is written, and its text.
    Space(u8, [u8; 32], u8, &'a str),
}

/// A tree node's or an event's bytes, as a frame's payload has them: in
/// hex in its JSON text, or in a hole of it, as they are (`pds_store`).
#[derive(Clone, Copy)]
enum Data<'a> {
    Hex(&'a str),
    Bytes(&'a [u8]),
}

impl<'a> Data<'a> {
    /// How an index says it is written, and where it is in the payload.
    fn written(self) -> (u8, &'a [u8]) {
        match self {
            Data::Hex(h) => (HEX, h.as_bytes()),
            Data::Bytes(b) => (BYTES, b),
        }
    }

    fn decode(self) -> Result<Vec<u8>, String> {
        match self {
            Data::Hex(h) => unhex(h),
            Data::Bytes(b) => Ok(b.to_vec()),
        }
    }
}

/// Give `f` each item of a frame's payload, of either kind, skimming the
/// rest, until it says to stop: a frame of one large commit is not held
/// parsed whole, nor any item of it but the one wanted. Of a payload with
/// holes, its JSON text is skimmed as it is, and a node's or an event's
/// bytes that are an empty string at a hole are that hole's.
fn skim<'a>(
    payload: &'a [u8],
    mut f: impl FnMut(Raw<'a>) -> Result<bool, String>,
) -> Result<(), String> {
    fn parse<'a, T: serde::Deserialize<'a>>(s: &'a str) -> Result<T, String> {
        serde_json::from_str(s).map_err(|e| format!("a log entry: {e}"))
    }
    let read = pds_store::text(payload)?;
    let text = std::str::from_utf8(read.json()).map_err(|e| format!("a frame: {e}"))?;
    let data = |s: &'a str| {
        let at = s.as_ptr() as usize - text.as_ptr() as usize;
        if s.is_empty()
            && let Some(b) = read.hole(at)
        {
            Data::Bytes(b)
        } else {
            Data::Hex(s)
        }
    };
    for e in parse::<Vec<&RawValue>>(text)? {
        let fields: HashMap<&str, &RawValue> = parse(e.get())?;
        let field = |k: &str| fields.get(k).map(|r| r.get());
        match field("t").map(parse::<&str>).transpose()? {
            Some("commit") => {
                if let Some(tree) = field("tree") {
                    for (cid, bytes) in parse::<Vec<(&str, &str)>>(tree)? {
                        if !f(Raw::Node(cid, data(bytes)))? {
                            return Ok(());
                        }
                    }
                }
                for p in parse::<Vec<Vec<&RawValue>>>(field("puts").unwrap_or("[]"))? {
                    let (Some(value), Some(cid)) = (p.get(1), p.get(2)) else {
                        continue;
                    };
                    let Some(cid) = parse::<Option<&str>>(cid.get())? else {
                        continue;
                    };
                    if !f(Raw::Record(cid, value))? {
                        return Ok(());
                    }
                }
            }
            Some("event") => {
                let (Some(seq), Some(frame)) = (field("seq"), field("frame")) else {
                    continue;
                };
                if !f(Raw::Event(parse(seq)?, data(parse(frame)?)))? {
                    return Ok(());
                }
            }
            Some(t @ (space_repo::ENTRY | space_repo::IMPORT)) => {
                let (Some(space), Some(rev)) = (field("space"), field("rev")) else {
                    continue;
                };
                // One not of this version's, before its log's mark
                // (`unmarked`), is passed over where it does not read.
                let (Ok(space), Ok(rev)) = (parse::<String>(space), parse::<String>(rev)) else {
                    continue;
                };
                if let Some(ops) = field("ops")
                    && !f(Raw::Space(
                        SPACE_OPS,
                        spaces::ops_name(&space, &rev),
                        RAW,
                        ops,
                    ))?
                {
                    return Ok(());
                }
                let records = if t == space_repo::ENTRY {
                    "puts"
                } else {
                    "records"
                };
                let records = field(records).unwrap_or("[]");
                let Ok(records) = parse::<Vec<(String, &RawValue)>>(records) else {
                    continue;
                };
                for (path, value) in records {
                    let name = spaces::record_name(&space, &rev, &path);
                    if !f(Raw::Space(SPACE_RECORD, name, RECORD, value.get()))? {
                        return Ok(());
                    }
                }
            }
            _ => {}
        }
    }
    Ok(())
}

/// A record's block, from its value as a put has it (`put_value`).
fn record_block(value: &str) -> Result<Vec<u8>, String> {
    let json: Json = serde_json::from_str(value).map_err(|e| format!("a record: {e}"))?;
    put_block(&json).map_err(|why| format!("a record: {why}"))
}

fn unhex(h: &str) -> Result<Vec<u8>, String> {
    hex::decode(h).map_err(|_| format!("{h} for hex"))
}

/// How an item of a frame is written: a tree node or an event, in hex, a
/// record, as JSON, a space commit's operations, as they are, or a tree
/// node or an event in a hole of a payload with holes, as they are.
const HEX: u8 = 0;
const RECORD: u8 = 1;
const RAW: u8 = 2;
const BYTES: u8 = 3;
/// The classes of an index's items: a block, an event, a space record, and
/// a space commit's operations.
const BLOCK: u8 = 0;
const EVENT: u8 = 1;
const SPACE_RECORD: u8 = 2;
const SPACE_OPS: u8 = 3;
/// The longest name an index holds: a CID's bytes, an event's seq, or a
/// space item's name.
const NAME: usize = 40;
/// An index entry: its item's class, its name's length and its name,
/// padded; how it is written, and where it is in the payload, its start
/// and length.
const ENTRY: usize = 2 + NAME + 1 + 8;
const SORT: usize = 2 + NAME;

/// The item a reader wants of a frame: a block by CID, an event by seq, a
/// space record by its name, checked to be of a CID, or a space commit's
/// operations by their name.
#[derive(Clone, Copy)]
enum Want<'a> {
    Block(&'a [u8]),
    Event(u64),
    SpaceRecord(&'a [u8; 32], &'a [u8]),
    SpaceOps(&'a [u8; 32]),
}

/// An item's place in an index's order, if a name that long fits one.
fn sort_key(class: u8, name: &[u8]) -> Option<[u8; SORT]> {
    if name.len() > NAME {
        return None;
    }
    let mut k = [0u8; SORT];
    k[0] = class;
    k[1] = name.len() as u8;
    k[2..2 + name.len()].copy_from_slice(name);
    Some(k)
}

impl Want<'_> {
    /// Its class in an index, and its name there.
    fn name(&self) -> (u8, Vec<u8>) {
        match self {
            Want::Block(cid) => (BLOCK, cid.to_vec()),
            Want::Event(seq) => (EVENT, seq.to_be_bytes().to_vec()),
            Want::SpaceRecord(name, _) => (SPACE_RECORD, name.to_vec()),
            Want::SpaceOps(name) => (SPACE_OPS, name.to_vec()),
        }
    }

    /// Its place in an index's order, if a name that long fits one.
    fn sort_key(&self) -> Option<[u8; SORT]> {
        let (class, name) = self.name();
        sort_key(class, &name)
    }
}

/// Where each item of a frame's payload is in it, sorted, so that one is
/// read alone, not the frame: none if a name is too long for it.
fn index(payload: &[u8]) -> Result<Option<Vec<u8>>, String> {
    let base = payload.as_ptr() as usize;
    let mut entries: Vec<[u8; ENTRY]> = Vec::new();
    let mut fits = true;
    skim(payload, |item| {
        let (class, name, (how, text)) = match item {
            Raw::Node(cid, data) => (BLOCK, unhex(cid)?, data.written()),
            Raw::Record(cid, value) => (BLOCK, unhex(cid)?, (RECORD, value.get().as_bytes())),
            Raw::Event(seq, data) => (EVENT, seq.to_be_bytes().to_vec(), data.written()),
            Raw::Space(class, name, how, text) => (class, name.to_vec(), (how, text.as_bytes())),
        };
        let Some(k) = sort_key(class, &name) else {
            fits = false;
            return Ok(false);
        };
        let mut e = [0u8; ENTRY];
        e[..SORT].copy_from_slice(&k);
        e[SORT] = how;
        e[SORT + 1..SORT + 5]
            .copy_from_slice(&((text.as_ptr() as usize - base) as u32).to_le_bytes());
        e[SORT + 5..].copy_from_slice(&(text.len() as u32).to_le_bytes());
        entries.push(e);
        Ok(true)
    })?;
    if !fits {
        return Ok(None);
    }
    entries.sort_by(|a, b| a[..SORT].cmp(&b[..SORT]));
    entries.dedup_by(|a, b| a[..SORT] == b[..SORT]);
    Ok(Some(entries.concat()))
}

/// Where `want` is in the frame `index` is of: how it is written, its
/// start and its length.
fn find(index: &[u8], want: Want) -> Option<(u8, usize, usize)> {
    let k = want.sort_key()?;
    let entry = |i: usize| &index[i * ENTRY..(i + 1) * ENTRY];
    let (mut lo, mut hi) = (0, index.len() / ENTRY);
    while lo < hi {
        let mid = (lo + hi) / 2;
        match entry(mid)[..SORT].cmp(&k[..]) {
            std::cmp::Ordering::Less => lo = mid + 1,
            std::cmp::Ordering::Greater => hi = mid,
            std::cmp::Ordering::Equal => {
                let e = entry(mid);
                let n = |at: usize| {
                    u32::from_le_bytes(e[at..at + 4].try_into().expect("four bytes")) as usize
                };
                return Some((e[SORT], n(SORT + 1), n(SORT + 5)));
            }
        }
    }
    None
}

/// An item, as its frame writes it.
fn decode_item(how: u8, text: &[u8]) -> Result<Vec<u8>, String> {
    if how == BYTES {
        return Ok(text.to_vec());
    }
    let text = std::str::from_utf8(text).map_err(|e| format!("an item: {e}"))?;
    match how {
        RECORD => record_block(text),
        RAW => Ok(text.as_bytes().to_vec()),
        _ => unhex(text),
    }
}

/// One item of a frame's payload, found by skimming it.
fn item(payload: &[u8], want: Want) -> Result<Option<Vec<u8>>, String> {
    let cid = match want {
        Want::Block(c) => Some(hex::encode(c)),
        _ => None,
    };
    let mut found = None;
    skim(payload, |item| {
        found = match (item, want) {
            (Raw::Node(c, data), _) if cid.as_deref() == Some(c) => Some(data.decode()?),
            (Raw::Record(c, value), _) if cid.as_deref() == Some(c) => {
                Some(record_block(value.get())?)
            }
            (Raw::Event(s, data), Want::Event(seq)) if s == seq => Some(data.decode()?),
            (Raw::Space(SPACE_RECORD, n, how, text), Want::SpaceRecord(name, _))
            | (Raw::Space(SPACE_OPS, n, how, text), Want::SpaceOps(name))
                if n == *name =>
            {
                Some(decode_item(how, text.as_bytes())?)
            }
            _ => return Ok(true),
        };
        Ok(false)
    })?;
    Ok(found)
}

/// The key a frame's index is kept by in the block cache: its file's
/// number and its offset, and no name, which no item has.
fn index_key(number: u64, pos: Pos) -> Key {
    Key::Item(number, pos.offset, Box::default())
}

/// An item of the frame at `pos` of the log numbered `number` in `cache`,
/// whose bytes `read` reads, by offset and length. Its index, kept in the
/// cache, says where it is, so that only it is read; the frame is read
/// whole, and checked, only to make the index. A block, and a space
/// record, is checked to be what its CID says.
fn frame_item(
    cache: &BlockCache,
    number: u64,
    pos: Pos,
    read: &dyn Fn(u64, usize) -> io::Result<Vec<u8>>,
    want: Want,
) -> Result<Option<Vec<u8>>, String> {
    let key = index_key(number, pos);
    let found = match cache.get(&key) {
        Some(ix) => indexed_item(&ix, pos, read, want)?,
        None => {
            let (ix, found) = whole_frame_item(pos, read, want)?;
            if let Some(ix) = ix {
                cache.put(key, ix.into());
            }
            found
        }
    };
    checked(want, found)
}

/// An item of the frame at `pos`, by the frame's index `ix`: its bytes
/// alone, which `read` reads.
fn indexed_item(
    ix: &[u8],
    pos: Pos,
    read: &dyn Fn(u64, usize) -> io::Result<Vec<u8>>,
    want: Want,
) -> Result<Option<Vec<u8>>, String> {
    let Some((how, start, len)) = find(ix, want) else {
        return Ok(None);
    };
    let text =
        read(pos.offset + (pds_store::HEADER + start) as u64, len).map_err(|e| e.to_string())?;
    decode_item(how, &text).map(Some)
}

/// A frame's index, if a name fits one (`index`), and an item found in it.
type Indexed = (Option<Vec<u8>>, Option<Vec<u8>>);

/// An item of the frame at `pos`, read whole by `read`, and the frame's
/// index, made of it.
fn whole_frame_item(
    pos: Pos,
    read: &dyn Fn(u64, usize) -> io::Result<Vec<u8>>,
    want: Want,
) -> Result<Indexed, String> {
    let payload =
        pds_store::payload(read(pos.offset, pos.len as usize).map_err(|e| e.to_string())?)
            .ok_or_else(|| format!("no whole frame at {}", pos.offset))?;
    let Some(ix) = index(&payload)? else {
        return Ok((None, item(&payload, want)?));
    };
    let found = match find(&ix, want) {
        None => None,
        Some((how, start, len)) => Some(decode_item(
            how,
            payload
                .get(start..start + len)
                .ok_or("an index past its frame")?,
        )?),
    };
    Ok((Some(ix), found))
}

/// An item found, checked: a block, and a space record, is what its CID
/// says it is.
fn checked(want: Want, found: Option<Vec<u8>>) -> Result<Option<Vec<u8>>, String> {
    if let (Want::Block(c) | Want::SpaceRecord(_, c), Some(b)) = (want, &found)
        && cid_of(0x71, b) != c
    {
        return Err(format!(
            "block {} is not what its frame holds",
            cid_string(c)
        ));
    }
    Ok(found)
}

/// The indexes of the frames a fold reads the items of, by each frame's
/// generation and offset, and their bytes. Each is made once, when an item
/// of its frame is first read, and kept until the fold ends, whatever its
/// size: the block cache keeps no entry larger than an eighth of it, and
/// one commit of a whole repository, as an import is, has an index larger
/// than the fold's cache would keep, which would otherwise be made again,
/// the whole frame read, for each of its items.
#[derive(Default)]
struct Indexes {
    of: HashMap<(u64, u64), Vec<u8>>,
    bytes: u64,
}

impl Indexes {
    /// An item of the frame at `pos`, whose bytes `read` reads, as
    /// `frame_item` reads one.
    fn item(
        &mut self,
        pos: Pos,
        read: &dyn Fn(u64, usize) -> io::Result<Vec<u8>>,
        want: Want,
    ) -> Result<Option<Vec<u8>>, String> {
        let found = match self.of.get(&(pos.generation, pos.offset)) {
            Some(ix) => indexed_item(ix, pos, read, want)?,
            None => {
                let (ix, found) = whole_frame_item(pos, read, want)?;
                if let Some(ix) = ix {
                    self.bytes += ix.len() as u64;
                    self.of.insert((pos.generation, pos.offset), ix);
                }
                found
            }
        };
        checked(want, found)
    }
}

/// Read `len` bytes of `file` at `offset`.
fn read_at(file: &File, offset: u64, len: usize) -> io::Result<Vec<u8>> {
    let mut buf = vec![0u8; len];
    file.read_exact_at(&mut buf, offset)?;
    Ok(buf)
}

// ---- A store's files ---------------------------------------------------------------

/// What a store reads its tree, its events and its space repos from: its
/// table, if it has one, and its log, by the memtable.
pub(crate) struct Disk {
    pub layout: Layout,
    pub table: Option<Arc<Table>>,
    pub mem: Memtable,
    /// The greatest seq of an event of its let go when its log was
    /// compacted, as its table's `H` has it: `0` with no table.
    pub let_go: u64,
    /// The bytes its table's index and bloom filter are counted as in the
    /// cache: `0` with no table.
    table_cost: u64,
    /// The number each log's generation is held by in the block cache.
    numbers: Mutex<HashMap<u64, u64>>,
}

/// What a store's blocks and paths are read through: its files and the cache.
pub(crate) struct Src<'a> {
    disk: &'a Disk,
    cache: &'a BlockCache,
}

impl Source for Src<'_> {
    fn block(&self, cid: &[u8]) -> Option<Arc<[u8]>> {
        self.disk.block(self.cache, cid)
    }
    fn path(&self, path: &str) -> Option<(Vec<u8>, String)> {
        self.disk.path(self.cache, path)
    }
    fn refs(&self, cid: &[u8]) -> Option<(u32, String)> {
        self.disk.refs(self.cache, cid)
    }
}

impl Disk {
    fn new(layout: Layout, table: Option<Arc<Table>>) -> Disk {
        Disk {
            layout,
            table_cost: table.as_ref().map_or(0, |t| t.cost()),
            table,
            mem: Memtable::default(),
            let_go: 0,
            numbers: Mutex::default(),
        }
    }

    /// A new account's: no table, its log empty.
    pub fn empty(layout: Layout) -> Disk {
        Disk::new(layout, None)
    }

    pub fn source<'a>(&'a self, cache: &'a BlockCache) -> Src<'a> {
        Src { disk: self, cache }
    }

    /// The bytes it is counted as in the cache: its table's index, and
    /// what the memtable keeps, each a total kept as it changes.
    pub fn cost(&self) -> u64 {
        self.table_cost + self.mem.cost()
    }

    /// What it holds cannot be read: the server stops (`unrecoverable`).
    pub(crate) fn fail(&self, why: impl std::fmt::Display) -> ! {
        unrecoverable(&self.layout.dir, &why.to_string())
    }

    fn number(&self, generation: u64) -> u64 {
        *self
            .numbers
            .lock()
            .unwrap_or_else(PoisonError::into_inner)
            .entry(generation)
            .or_insert_with(file_number)
    }

    /// Keep in `cache` the index of the frame just appended at `pos`, its
    /// payload `payload`: its items are read alone from then on.
    pub fn indexed(&self, cache: &BlockCache, pos: Pos, payload: &[u8]) {
        if let Ok(Some(ix)) = index(payload) {
            cache.put(index_key(self.number(pos.generation), pos), ix.into());
        }
    }

    /// An item of the frame at `pos`, read and kept in the cache.
    fn log_item(&self, cache: &BlockCache, pos: Pos, want: Want) -> Option<Arc<[u8]>> {
        let number = self.number(pos.generation);
        let (class, name) = want.name();
        let name = [&[class][..], &name].concat();
        let key = Key::Item(number, pos.offset, name.into_boxed_slice());
        if let Some(b) = cache.get(&key) {
            return Some(b);
        }
        let path = self.layout.log(pos.generation);
        let read = |offset: u64, len: usize| read_at(&File::open(&path)?, offset, len);
        let found: Arc<[u8]> = frame_item(cache, number, pos, &read, want)
            .unwrap_or_else(|e| self.fail(format!("{}: {e}", path.display())))?
            .into();
        cache.put(key, found.clone());
        Some(found)
    }

    fn table_get(&self, cache: &BlockCache, k: &[u8]) -> Option<Vec<u8>> {
        let t = self.table.as_ref()?;
        t.get(k, cache).unwrap_or_else(|e| self.fail(e))
    }

    /// A block of the current tree.
    pub fn block(&self, cache: &BlockCache, cid: &[u8]) -> Option<Arc<[u8]>> {
        match self.mem.blocks.get(cid) {
            Some(MemBlock { at: None, .. }) => None,
            Some(MemBlock {
                at: Some(At::Log(pos)),
                ..
            }) => Some(
                self.log_item(cache, *pos, Want::Block(cid))
                    .unwrap_or_else(|| {
                        self.fail(format!("block {} missing from its frame", cid_string(cid)))
                    }),
            ),
            _ => {
                let v = self.table_get(cache, &key(b'B', cid))?;
                let (_, _, at) = read_block_value(&v)
                    .unwrap_or_else(|| self.fail("a block's entry that does not parse"));
                Some(v[at..].into())
            }
        }
    }

    pub fn path(&self, cache: &BlockCache, path: &str) -> Option<(Vec<u8>, String)> {
        match self.mem.paths.get(path) {
            Some((p, _)) => p.as_ref().map(|(c, r)| (c.clone(), r.to_string())),
            None => {
                let v = self.table_get(cache, &key(b'P', path.as_bytes()))?;
                Some(
                    read_path_value(&v)
                        .unwrap_or_else(|| self.fail("a path's entry that does not parse")),
                )
            }
        }
    }

    pub fn refs(&self, cache: &BlockCache, cid: &[u8]) -> Option<(u32, String)> {
        match self.mem.blocks.get(cid) {
            Some(b) => (b.refs > 0).then(|| (b.refs, b.rev.to_string())),
            None => {
                let v = self.table_get(cache, &key(b'B', cid))?;
                let (refs, rev, _) = read_block_value(&v)
                    .unwrap_or_else(|| self.fail("a block's entry that does not parse"));
                Some((refs, rev.to_string()))
            }
        }
    }

    /// The records' paths and CIDs from `from` (or, `reverse`, before
    /// `from`, the last first) while they begin with `prefix`, at most `limit`.
    pub fn records(
        &self,
        cache: &BlockCache,
        prefix: &str,
        from: &str,
        reverse: bool,
        limit: usize,
    ) -> Vec<(String, Vec<u8>)> {
        let mut out: Vec<(String, Vec<u8>)> = Vec::new();
        let in_range = |p: &str| p.starts_with(prefix);
        // The memtable's, in order.
        use std::ops::Bound::{Excluded, Included, Unbounded};
        let mem: Vec<(&String, &Option<Written>)> = if reverse {
            self.mem
                .paths
                .range::<str, _>((Unbounded, Excluded(from)))
                .rev()
                .take_while(|(p, _)| in_range(p))
                .map(|(p, v)| (p, &v.0))
                .collect()
        } else {
            self.mem
                .paths
                .range::<str, _>((Included(from), Unbounded))
                .take_while(|(p, _)| in_range(p))
                .map(|(p, v)| (p, &v.0))
                .collect()
        };
        let mut mi = mem.into_iter().peekable();
        let table: Box<dyn Iterator<Item = (String, Vec<u8>)>> = match &self.table {
            None => Box::new(std::iter::empty()),
            Some(t) => {
                let start = key(b'P', from.as_bytes());
                let it = if reverse {
                    t.iter_back(&start, None, cache)
                } else {
                    t.iter(&start, None, cache)
                };
                Box::new(
                    it.map(|r| r.unwrap_or_else(|e| self.fail(e)))
                        .take_while(|(k, _)| k.first() == Some(&b'P'))
                        .map(|(k, v)| (String::from_utf8_lossy(&k[1..]).into_owned(), v))
                        .take_while(|(p, _)| in_range(p)),
                )
            }
        };
        let mut ti = table.peekable();
        let before = |a: &str, b: &str| if reverse { a > b } else { a < b };
        while out.len() < limit {
            let next = match (mi.peek(), ti.peek()) {
                (None, None) => break,
                (Some(_), None) => 0,
                (None, Some(_)) => 1,
                (Some((m, _)), Some((t, _))) if *m == t => 2,
                (Some((m, _)), Some((t, _))) => {
                    if before(m, t) {
                        0
                    } else {
                        1
                    }
                }
            };
            match next {
                1 => {
                    let (p, v) = ti.next().expect("peeked");
                    let (cid, _) = read_path_value(&v)
                        .unwrap_or_else(|| self.fail("a path's entry that does not parse"));
                    out.push((p, cid));
                }
                _ => {
                    if next == 2 {
                        ti.next();
                    }
                    let (p, v) = mi.next().expect("peeked");
                    if let Some((cid, _)) = v {
                        out.push((p.clone(), cid.clone()));
                    }
                }
            }
        }
        out
    }

    /// Give `f` every record's path, CID and the rev that last wrote it, in
    /// order of path, read as it goes.
    pub fn each_path(&self, cache: &BlockCache, mut f: impl FnMut(&str, &[u8], &str)) {
        let mut mi = self.mem.paths.iter().peekable();
        let table: Box<dyn Iterator<Item = (Vec<u8>, Vec<u8>)>> = match &self.table {
            None => Box::new(std::iter::empty()),
            Some(t) => Box::new(
                t.iter(b"P", None, cache)
                    .map(|r| r.unwrap_or_else(|e| self.fail(e)))
                    .take_while(|(k, _)| k.first() == Some(&b'P')),
            ),
        };
        let mut ti = table.peekable();
        loop {
            let take_mem = match (mi.peek(), ti.peek()) {
                (None, None) => return,
                (Some(_), None) => true,
                (None, Some(_)) => false,
                (Some((p, _)), Some((k, _))) => p.as_bytes() <= &k[1..],
            };
            if take_mem {
                let (p, (x, _)) = mi.next().expect("peeked");
                if ti.peek().is_some_and(|(k, _)| k[1..] == *p.as_bytes()) {
                    ti.next();
                }
                if let Some((cid, rev)) = x {
                    f(p, cid, rev);
                }
            } else {
                let (k, v) = ti.next().expect("peeked");
                let (cid, rev) = read_path_value(&v)
                    .unwrap_or_else(|| self.fail("a path's entry that does not parse"));
                f(&String::from_utf8_lossy(&k[1..]), &cid, &rev);
            }
        }
    }

    /// Every event it holds: its seq and when it was made, in order of seq.
    pub fn event_seqs(&self, cache: &BlockCache) -> Vec<(u64, u64)> {
        let mut out: BTreeMap<u64, u64> = BTreeMap::new();
        if let Some(t) = &self.table {
            table_events(t, cache, &mut out).unwrap_or_else(|e| self.fail(e));
        }
        out.extend(self.mem.events.iter().map(|(seq, (time, _))| (*seq, *time)));
        out.into_iter().collect()
    }

    /// An event's frame, if it holds it.
    pub fn event_frame(&self, cache: &BlockCache, seq: u64) -> Option<Bytes> {
        if let Some((_, pos)) = self.mem.events.get(&seq) {
            return self
                .log_item(cache, *pos, Want::Event(seq))
                .map(|b| Bytes::copy_from_slice(&b));
        }
        self.table_get(cache, &key(b'E', &seq.to_be_bytes()))
            .map(Bytes::from)
    }

    /// What reads its tree's blocks while it changes: its files open, and
    /// the memtable's blocks as they are now.
    pub fn snapshot(&self, head: (Vec<u8>, Vec<u8>)) -> io::Result<Snapshot> {
        let table = match &self.table {
            Some(t) => Some((t.clone(), t.file()?)),
            None => None,
        };
        let mut blocks: Vec<(Vec<u8>, MemBlock)> = self
            .mem
            .blocks
            .iter()
            .map(|(c, b)| (c.clone(), b.clone()))
            .collect();
        blocks.sort_by(|a, b| a.0.cmp(&b.0));
        let mut logs = HashMap::new();
        for (_, b) in &blocks {
            if let Some(At::Log(p)) = b.at
                && let std::collections::hash_map::Entry::Vacant(v) = logs.entry(p.generation)
            {
                v.insert((
                    File::open(self.layout.log(p.generation))?,
                    self.number(p.generation),
                ));
            }
        }
        Ok(Snapshot {
            head,
            table,
            blocks,
            logs,
        })
    }
}

/// A store's tree as it was when taken, read as it is sent.
pub(crate) struct Snapshot {
    head: (Vec<u8>, Vec<u8>),
    table: Option<(Arc<Table>, Arc<File>)>,
    blocks: Vec<(Vec<u8>, MemBlock)>,
    /// Each log it reads, by generation, and the number the cache holds it by.
    logs: HashMap<u64, (File, u64)>,
}

impl Snapshot {
    /// Give `emit` the commit, then each block of the tree that a commit
    /// after rev `since` put in it (every one with none), in order of CID,
    /// each read as it is reached; stop when `emit` says to.
    pub fn run(
        self,
        cache: &BlockCache,
        since: Option<&str>,
        mut emit: impl FnMut(&[u8], &[u8]) -> bool,
    ) -> io::Result<()> {
        let after = |rev: &str| since.is_none_or(|s| rev > s);
        let commit_rev = match pds_repo::data::decode(&self.head.1) {
            Ok(V::Map(m)) => m
                .into_iter()
                .find(|(k, _)| k == "rev")
                .and_then(|(_, v)| if let V::Str(s) = v { Some(s) } else { None })
                .unwrap_or_default(),
            _ => String::new(),
        };
        if after(&commit_rev) && !emit(&self.head.0, &self.head.1) {
            return Ok(());
        }
        let from_log = |pos: Pos, cid: &[u8]| -> io::Result<Vec<u8>> {
            let (file, number) = self
                .logs
                .get(&pos.generation)
                .ok_or_else(|| io::Error::other("a log not open"))?;
            let read = |offset: u64, len: usize| read_at(file, offset, len);
            frame_item(cache, *number, pos, &read, Want::Block(cid))
                .map_err(|e| io::Error::new(io::ErrorKind::InvalidData, e))?
                .ok_or_else(|| {
                    io::Error::new(io::ErrorKind::InvalidData, "a block missing from its frame")
                })
        };
        let mut mem = self.blocks.into_iter().peekable();
        let mut table: Rows<'_, io::Error> = match &self.table {
            None => Box::new(std::iter::empty()),
            Some((t, f)) => Box::new(
                t.iter(b"B", Some(&**f), cache)
                    .take_while(|r| r.as_ref().map_or(true, |(k, _)| k.first() == Some(&b'B'))),
            ),
        };
        let mut next_table = table.next().transpose()?;
        loop {
            let take_mem = match (mem.peek(), &next_table) {
                (None, None) => return Ok(()),
                (Some(_), None) => true,
                (None, Some(_)) => false,
                (Some((c, _)), Some((k, _))) => c.as_slice() <= &k[1..],
            };
            if take_mem {
                let (cid, b) = mem.next().expect("peeked");
                let same = next_table.as_ref().is_some_and(|(k, _)| k[1..] == cid[..]);
                let table_value = if same { next_table.take() } else { None };
                if same {
                    next_table = table.next().transpose()?;
                }
                let Some(at) = b.at else { continue };
                if !after(&b.rev) {
                    continue;
                }
                let bytes = match at {
                    At::Log(pos) => from_log(pos, &cid)?,
                    At::Table => {
                        let (_, v) = table_value.ok_or_else(|| {
                            io::Error::new(
                                io::ErrorKind::InvalidData,
                                "a block the table should hold",
                            )
                        })?;
                        let (_, _, at) = read_block_value(&v).ok_or_else(|| {
                            io::Error::new(io::ErrorKind::InvalidData, "a block's entry")
                        })?;
                        v[at..].to_vec()
                    }
                };
                if !emit(&cid, &bytes) {
                    return Ok(());
                }
            } else {
                let (k, v) = next_table.take().expect("peeked");
                next_table = table.next().transpose()?;
                let (_, rev, at) = read_block_value(&v)
                    .ok_or_else(|| io::Error::new(io::ErrorKind::InvalidData, "a block's entry"))?;
                if after(rev) && !emit(&k[1..], &v[at..]) {
                    return Ok(());
                }
            }
        }
    }
}

/// The events a table holds, each one's seq and when it was made, into `out`.
fn table_events(t: &Table, cache: &BlockCache, out: &mut BTreeMap<u64, u64>) -> Result<(), String> {
    for r in t.iter(b"D", None, cache) {
        let (k, v) = r.map_err(|e| e.to_string())?;
        if k.first() != Some(&b'D') {
            break;
        }
        let (Ok(seq), Ok(time)) = (<[u8; 8]>::try_from(&k[1..]), <[u8; 8]>::try_from(&v[..]))
        else {
            return Err("an event's entry that does not parse".into());
        };
        out.insert(u64::from_be_bytes(seq), u64::from_be_bytes(time));
    }
    Ok(())
}

/// Every event an account's files hold, its seq and when it was made, in
/// order of seq, the greatest seq any event of its has had, and the
/// greatest of those its log's compaction let go: what its store would
/// answer once loaded (`Disk::event_seqs`, `Store::last_seq`, `let_go`),
/// read without loading it. Its table's header and events and its
/// log's entries of them are read, as a load replays the log, and nothing
/// else of it is checked; nothing is deleted, cut back or made durable, no
/// log is left open and nothing is kept in memory. For the firehose, which
/// makes its index of every account's files where a data directory has
/// none, and looks into an account's events for void ones. The caller
/// sees that the store is not loaded meanwhile (`cache::Slot::events`, or
/// of an account not loaded, `events::Firehose::adopt`).
pub(crate) fn events_on_disk(ctx: &crate::cache::Ctx, did: &str) -> Result<EventsOnDisk, String> {
    let layout = crate::store::account_layout(&ctx.dir, did);
    let mut out: BTreeMap<u64, u64> = BTreeMap::new();
    let (generation, mut last, let_go) = match Table::open(&layout.checkpoint(), &ctx.blocks) {
        Ok(t) => {
            let read = (|| {
                // A table of the version before has none: a load folds it.
                let header = t
                    .get(b"H", &ctx.blocks)
                    .map_err(|e| e.to_string())?
                    .ok_or("a checkpoint of the version before")?;
                table_events(&t, &ctx.blocks, &mut out)?;
                read_header(&header).ok_or_else(|| "a header that does not parse".to_string())
            })();
            ctx.blocks.forget(t.id());
            read?
        }
        Err(e) if e.kind() == io::ErrorKind::NotFound => (0, 0, 0),
        Err(e) => return Err(e.to_string()),
    };
    pds_store::read_log(&layout, generation, &mut |_, entries| {
        for e in entries.iter().filter(|e| e["t"] == "event") {
            let seq = e["seq"]
                .as_u64()
                .ok_or_else(|| "an event with no seq".to_string())?;
            let time = match e["time"].as_u64() {
                Some(t) => t,
                None => crate::events::event_time(&hex_of(&e["frame"])?).unwrap_or(0),
            };
            out.insert(seq, time);
            last = last.max(seq);
        }
        Ok(())
    })
    .map_err(|e| e.to_string())?;
    Ok((out.into_iter().collect(), last, let_go))
}

// ---- Loading ------------------------------------------------------------------------

/// A store read from its files: its repository, log, files and the rest.
pub(crate) struct Loaded {
    pub repo: Repo,
    pub wal: pds_store::Wal,
    pub disk: Disk,
    pub small: Small,
}

/// Read an account's store: its table, if it has one, then its log after,
/// replayed into the memtable one frame at a time. A log of commits of the
/// kind before the tree was changed in place, and a table of the version
/// before with the log after it, are folded into a table first.
///
/// `durable` says that every frame the log's files hold is on disk
/// (`cache::Slot::durable`): the log is then opened with no sync, unless
/// there is something of it to mend (`pds_store::Wal::open_log_with`). A
/// fold writes, and syncs what it writes: the log read again after one is
/// durable whatever it was.
pub(crate) fn load(
    ctx: &crate::cache::Ctx,
    did: &str,
    signing: &SigningKey,
    mut durable: bool,
) -> Result<Loaded, String> {
    for _ in 0..2 {
        // Said of the first try alone: one tried again for want of a file
        // descriptor may have mended what it then no longer finds.
        let mut told = durable;
        let layout = crate::store::account_layout(&ctx.dir, did);
        let at = |why: String| format!("{}: {why}", layout.dir.display());
        let named = |why: String| format!("{}: {why}", layout.checkpoint().display());
        let table = match Table::open(&layout.checkpoint(), &ctx.blocks) {
            Ok(t) => Some(Arc::new(t)),
            Err(e) if e.kind() == io::ErrorKind::NotFound => None,
            Err(e) => return Err(at(e.to_string())),
        };
        // Fold a log into a table of this version, once.
        let fold = |wal: pds_store::Wal| {
            wal.set_fold(Arc::new(AccountFold {
                did: did.to_string(),
                key: signing.clone(),
                window: ctx.window,
                blocks: ctx.cache.fold_blocks(),
                account: Weak::new(),
            }));
            wal.compact()
        };
        let mut small = match &table {
            Some(t) => {
                let s = t
                    .get(b"S", &ctx.blocks)
                    .map_err(|e| at(e.to_string()))?
                    .ok_or_else(|| at("a checkpoint with no state".into()))?;
                match t.get(b"H", &ctx.blocks).map_err(|e| at(e.to_string()))? {
                    Some(h) => Small::decode(&s, &h, did).map_err(named)?,
                    None => {
                        // A table of the version before: folded, with the
                        // log after it, into one of this version; then
                        // read again.
                        let generation = before::generation(&s).map_err(named)?;
                        drop(s);
                        let wal = crate::log::retrying(|| {
                            pds_store::Wal::open_log_with(
                                &layout,
                                generation,
                                t.size(),
                                Some(ctx.files.clone()),
                                ctx.policy,
                                std::mem::take(&mut told),
                                &mut |_, _| Ok(()),
                            )
                        })
                        .map_err(|e| at(e.to_string()))?;
                        ctx.blocks.forget(t.id());
                        fold(wal).map_err(at)?;
                        durable = true;
                        continue;
                    }
                }
            }
            None => Small::new(),
        };
        let mut disk = Disk::new(layout.clone(), table);
        disk.let_go = small.let_go;
        let size = disk.table.as_ref().map_or(0, |t| t.size());
        let generation = small.generation;
        let old = match &disk.table {
            Some(t) => Old::Table(t, None),
            None => Old::None,
        };
        let holds = |m: &Memtable, p: &str| match m.paths.get(p) {
            Some((x, _)) => x.is_some(),
            None => disk.table.as_ref().is_some_and(|t| {
                t.get(&key(b'P', p.as_bytes()), &ctx.blocks)
                    .ok()
                    .flatten()
                    .is_some()
            }),
        };
        let mut mem = Memtable::default();
        let wal = crate::log::retrying(|| {
            mem = Memtable::default();
            pds_store::Wal::open_log_with(
                &layout,
                generation,
                size,
                Some(ctx.files.clone()),
                ctx.policy,
                std::mem::take(&mut told),
                &mut |pos, entries| {
                    for e in &entries {
                        mem.apply(&mut small, pos, e, &holds, old, &ctx.blocks)?;
                    }
                    Ok(())
                },
            )
        })
        .map_err(|e| at(e.to_string()))?;
        if mem.legacy {
            if disk.table.is_some() {
                return Err(at(
                    "a commit of the kind before the tree was changed in place, after a checkpoint"
                        .into(),
                ));
            }
            // Folded into a table, once; then read again.
            fold(wal).map_err(at)?;
            durable = true;
            continue;
        }
        disk.mem = mem;
        let mut repo = Repo::new(did.to_string(), signing.clone());
        if small.has_commit() {
            repo.restore(small.head.clone(), small.counts, &small.tids.last())
                .map_err(at)?;
            // The tree the latest commit names is the store's.
            if disk.block(&ctx.blocks, &repo.root).is_none() {
                return Err(at(format!(
                    "the tree {}, which the latest commit signs, is not held",
                    cid_string(&repo.root)
                )));
            }
        }
        repo.tids.after(&small.tids.last());
        return Ok(Loaded {
            repo,
            wal,
            disk,
            small,
        });
    }
    Err(format!(
        "{did}: its log folded is still of the kind or the version before"
    ))
}

// ---- Compacting ---------------------------------------------------------------------

/// An account's log's fold: the table of a generation, merged from the one
/// before and the sealed logs after it; put in place under the account's
/// lock, if its store is held, which reads it from then on.
pub(crate) struct AccountFold {
    pub did: String,
    pub key: SigningKey,
    /// The backfill window, in milliseconds.
    pub window: u64,
    /// The bytes it may keep of what it reads to read it again
    /// (`cache::Cache::fold_blocks`).
    pub blocks: u64,
    /// The account, whose store reads the table once it is in place.
    pub account: Weak<Account>,
}

/// What a fold holds in memory while it merges, counted with its account's
/// store until it ends (`cache::Slot::folding`): what it holds from the
/// start, and the frames' indexes it makes as it goes (`Indexes`).
struct Holding {
    account: Option<Arc<Account>>,
    bytes: std::cell::Cell<u64>,
}

impl Holding {
    fn new(account: &Weak<Account>, bytes: u64) -> Holding {
        let account = account.upgrade();
        if let Some(a) = &account {
            a.store.folding(bytes);
        }
        Holding {
            account,
            bytes: bytes.into(),
        }
    }

    /// Count `bytes` more.
    fn more(&self, bytes: u64) {
        let n = self.bytes.get() + bytes;
        self.bytes.set(n);
        if let Some(a) = &self.account {
            a.store.folding(n);
        }
    }
}

impl Drop for Holding {
    fn drop(&mut self) {
        if let Some(a) = &self.account {
            a.store.folding(0);
        }
    }
}

/// Reads the items of the sealed logs' frames as the merge reaches them,
/// each alone, through its frame's index (`Indexes`), whose bytes count
/// with what the fold holds, if anything counts it.
struct Frames<'a> {
    layout: &'a Layout,
    files: HashMap<u64, File>,
    indexes: Indexes,
    holding: Option<&'a Holding>,
}

impl Frames<'_> {
    fn item(&mut self, pos: Pos, want: Want) -> Result<Option<Vec<u8>>, String> {
        let file = match self.files.entry(pos.generation) {
            std::collections::hash_map::Entry::Occupied(f) => f.into_mut(),
            std::collections::hash_map::Entry::Vacant(v) => {
                v.insert(File::open(self.layout.log(pos.generation)).map_err(|e| e.to_string())?)
            }
        };
        let read = |offset: u64, len: usize| read_at(file, offset, len);
        let before = self.indexes.bytes;
        let found = self.indexes.item(pos, &read, want);
        if let Some(h) = self.holding
            && self.indexes.bytes > before
        {
            h.more(self.indexes.bytes - before);
        }
        found
    }
}

impl Fold for AccountFold {
    fn fold_files(
        &self,
        checkpoint: Option<&Path>,
        logs: &[PathBuf],
        generation: u64,
        out: &mut dyn Write,
    ) -> Result<(), String> {
        // What is read again is kept: the table's blocks records are looked
        // up in as the logs are replayed, and the places of the frames'
        // items (`Frames`). What the merge reads once, in order, is not.
        let cache = BlockCache::new(self.blocks);
        let passing = BlockCache::new(0);
        let table = match checkpoint {
            Some(p) => Some(Table::open(p, &cache).map_err(|e| e.to_string())?),
            None => None,
        };
        let mut small = match &table {
            Some(t) => {
                let state = t
                    .get(b"S", &cache)
                    .map_err(|e| e.to_string())?
                    .ok_or("a checkpoint with no state")?;
                match t.get(b"H", &cache).map_err(|e| e.to_string())? {
                    Some(h) => Small::decode(&state, &h, &self.did)?,
                    None => before::read(&state, &self.did)?,
                }
            }
            None => Small::new(),
        };
        let spaces_old = match &table {
            Some(t) => Old::Table(t, None),
            None => Old::None,
        };
        let layout = Layout::new(
            logs.first()
                .and_then(|p| p.parent())
                .map_or_else(PathBuf::new, Path::to_path_buf),
            "repo",
        );
        let first = generation - logs.len() as u64;
        let mut mem = Memtable::default();
        let holds = |m: &Memtable, p: &str| match m.paths.get(p) {
            Some((x, _)) => x.is_some(),
            None => table.as_ref().is_some_and(|t| {
                t.get(&key(b'P', p.as_bytes()), &cache)
                    .ok()
                    .flatten()
                    .is_some()
            }),
        };
        for (i, p) in logs.iter().enumerate() {
            let g = first + i as u64;
            pds_store::read_sealed(p, |offset, len, entries| {
                for e in &entries {
                    mem.apply(
                        &mut small,
                        Pos {
                            generation: g,
                            offset,
                            len,
                        },
                        e,
                        &holds,
                        spaces_old,
                        &cache,
                    )?;
                }
                Ok(())
            })?;
        }
        if !small.has_commit() {
            return Err("an account with no commit yet".into());
        }
        let now = crate::events::now_ms();
        if mem.legacy {
            return legacy_fold(
                &self.did,
                &self.key,
                logs,
                generation,
                self.window,
                now,
                out,
            );
        }
        let mut w = TableWriter::new(
            io::BufWriter::new(out),
            table.as_ref().map_or(0, |t| t.len())
                + (mem.blocks.len() + mem.paths.len() + mem.events.len() * 2) as u64
                + spaces::entries(&mem.spaces)
                + 2,
        );
        // What it holds from here on: the state, where each entry of the
        // sealed logs is, and the blocks it keeps; and the frames' indexes,
        // as it makes them.
        let held = small.blobs.cost()
            + small.spaces.cost()
            + small.authority.cost()
            + small.notify.cost()
            + mem.cost()
            + self.blocks;
        let holding = Holding::new(&self.account, held);
        let view = View {
            mem: &mem.spaces,
            old: spaces_old,
            cache: &passing,
        };
        let mut frames = Frames {
            layout: &layout,
            files: HashMap::new(),
            indexes: Indexes::default(),
            holding: Some(&holding),
        };
        let werr = |e: io::Error| e.to_string();
        let old = |prefix: u8| -> Rows<'_, String> {
            match &table {
                None => Box::new(std::iter::empty()),
                Some(t) => Box::new(
                    t.iter(&[prefix], None, &passing)
                        .map(|r| r.map_err(|e| e.to_string()))
                        .take_while(move |r| {
                            r.as_ref().map_or(true, |(k, _)| k.first() == Some(&prefix))
                        }),
                ),
            }
        };
        // The tree's blocks.
        let mut mine: Vec<(&Vec<u8>, &MemBlock)> = mem.blocks.iter().collect();
        mine.sort_by(|a, b| a.0.cmp(b.0));
        let mut mi = mine.into_iter().peekable();
        let mut ti = old(b'B').peekable();
        loop {
            let take_mem = match (mi.peek(), ti.peek()) {
                (None, None) => break,
                (Some(_), None) => true,
                (None, Some(_)) => false,
                (Some((c, _)), Some(Ok((k, _)))) => c.as_slice() <= &k[1..],
                (_, Some(Err(e))) => return Err(e.clone()),
            };
            if take_mem {
                let (cid, b) = mi.next().expect("peeked");
                let same = matches!(ti.peek(), Some(Ok((k, _))) if k[1..] == cid[..]);
                let table_value = if same { ti.next().transpose()? } else { None };
                let Some(at) = b.at else { continue };
                let bytes = match at {
                    At::Log(pos) => frames.item(pos, Want::Block(cid))?.ok_or_else(|| {
                        format!("block {} missing from its frame", cid_string(cid))
                    })?,
                    At::Table => {
                        let (_, v) = table_value
                            .ok_or_else(|| format!("block {} not in the table", cid_string(cid)))?;
                        let (_, _, at) =
                            read_block_value(&v).ok_or("a block's entry that does not parse")?;
                        v[at..].to_vec()
                    }
                };
                w.add(&key(b'B', cid), &block_value(b.refs, &b.rev, &bytes))
                    .map_err(werr)?;
            } else {
                let (k, v) = ti.next().expect("peeked")?;
                w.add(&k, &v).map_err(werr)?;
            }
        }
        // The space repos' blob references.
        spaces::fold(
            spaces::REFS,
            view,
            &mut |pos, want| frames.item(pos, want),
            &mut |k, v| w.add(k, v).map_err(werr),
        )?;
        // The events in the window: when each was made, then its frame.
        // Of those let go, the greatest seq is kept (`Small::let_go`).
        let keep = |time: u64| time + 1000 + self.window >= now;
        let mut kept: BTreeMap<u64, (u64, Option<Pos>)> = BTreeMap::new();
        for r in old(b'D') {
            let (k, v) = r?;
            let (Ok(seq), Ok(time)) = (<[u8; 8]>::try_from(&k[1..]), <[u8; 8]>::try_from(&v[..]))
            else {
                return Err("an event's entry that does not parse".into());
            };
            let (seq, time) = (u64::from_be_bytes(seq), u64::from_be_bytes(time));
            if keep(time) {
                kept.insert(seq, (time, None));
            } else {
                small.let_go = small.let_go.max(seq);
            }
        }
        for (seq, (time, pos)) in &mem.events {
            if keep(*time) {
                kept.insert(*seq, (*time, Some(*pos)));
            } else {
                small.let_go = small.let_go.max(*seq);
            }
        }
        for (seq, (time, _)) in &kept {
            w.add(&key(b'D', &seq.to_be_bytes()), &time.to_be_bytes())
                .map_err(werr)?;
        }
        let mut ei = old(b'E').peekable();
        for (seq, (_, pos)) in &kept {
            let k = key(b'E', &seq.to_be_bytes());
            let frame = match pos {
                Some(pos) => frames
                    .item(*pos, Want::Event(*seq))?
                    .ok_or_else(|| format!("event {seq} missing from its frame"))?,
                None => loop {
                    match ei.next() {
                        Some(Ok((tk, v))) if tk == k => break v,
                        Some(Ok((tk, _))) if tk < k => continue,
                        Some(Err(e)) => return Err(e),
                        _ => return Err(format!("event {seq} not in the table")),
                    }
                },
            };
            w.add(&k, &frame).map_err(werr)?;
        }
        w.add(
            b"H",
            &header_value(generation, small.last_seq, small.let_go),
        )
        .map_err(werr)?;
        // The space repos' operations.
        spaces::fold(
            spaces::OPS,
            view,
            &mut |pos, want| frames.item(pos, want),
            &mut |k, v| w.add(k, v).map_err(werr),
        )?;
        // The paths.
        let mut mi = mem.paths.iter().peekable();
        let mut ti = old(b'P').peekable();
        loop {
            let take_mem = match (mi.peek(), ti.peek()) {
                (None, None) => break,
                (Some(_), None) => true,
                (None, Some(_)) => false,
                (Some((p, _)), Some(Ok((k, _)))) => p.as_bytes() <= &k[1..],
                (_, Some(Err(e))) => return Err(e.clone()),
            };
            if take_mem {
                let (p, (x, _)) = mi.next().expect("peeked");
                if matches!(ti.peek(), Some(Ok((k, _))) if k[1..] == *p.as_bytes()) {
                    ti.next();
                }
                if let Some((cid, rev)) = x {
                    w.add(&key(b'P', p.as_bytes()), &path_value(cid, rev))
                        .map_err(werr)?;
                }
            } else {
                let (k, v) = ti.next().expect("peeked")?;
                w.add(&k, &v).map_err(werr)?;
            }
        }
        // The space repos' records, the rest of the state, and the records' bytes.
        spaces::fold(
            spaces::RECORDS,
            view,
            &mut |pos, want| frames.item(pos, want),
            &mut |k, v| w.add(k, v).map_err(werr),
        )?;
        w.add(b"S", &small.encode(&self.did, now)).map_err(werr)?;
        spaces::fold(
            spaces::VALUES,
            view,
            &mut |pos, want| frames.item(pos, want),
            &mut |k, v| w.add(k, v).map_err(werr),
        )?;
        let (mut out, _) = w.finish().map_err(werr)?;
        out.flush().map_err(werr)
    }

    fn install(
        &self,
        generation: u64,
        rename: &mut dyn FnMut() -> Result<(), String>,
    ) -> Result<(), String> {
        let Some(a) = self.account.upgrade() else {
            return rename();
        };
        a.store.installing(|st| {
            rename()?;
            let Some(st) = st else { return Ok(()) };
            let table = Table::open(&st.disk.layout.checkpoint(), &st.ctx.blocks)
                .map_err(|e| e.to_string())?;
            let (_, _, let_go) = table
                .get(b"H", &st.ctx.blocks)
                .map_err(|e| e.to_string())?
                .and_then(|h| read_header(&h))
                .ok_or("a checkpoint with no header")?;
            (st.disk.let_go, st.disk.table_cost) = (let_go, table.cost());
            if let Some(old) = st.disk.table.replace(Arc::new(table)) {
                st.ctx.blocks.forget(old.id());
            }
            st.disk.mem.folded(generation);
            let numbers: Vec<u64> = {
                let mut n = st
                    .disk
                    .numbers
                    .lock()
                    .unwrap_or_else(PoisonError::into_inner);
                let gone: Vec<u64> = n.keys().filter(|g| **g < generation).copied().collect();
                gone.into_iter().filter_map(|g| n.remove(&g)).collect()
            };
            for n in numbers {
                st.ctx.blocks.forget(n);
            }
            Ok(())
        })
    }
}

/// The table of a log of the kind before the tree was changed in place:
/// replayed whole in memory, as servers then did, its tree rebuilt.
fn legacy_fold(
    did: &str,
    signing: &SigningKey,
    logs: &[PathBuf],
    generation: u64,
    window: u64,
    now: u64,
    out: &mut dyn Write,
) -> Result<(), String> {
    let mut small = Small::new();
    let mut repo = pds_repo::full::Repo::new(did.to_string(), signing.clone());
    let mut events: BTreeMap<u64, (u64, Vec<u8>)> = BTreeMap::new();
    let cache = BlockCache::new(4 << 20);
    let layout = Layout::new(
        logs.first()
            .and_then(|p| p.parent())
            .map_or_else(PathBuf::new, Path::to_path_buf),
        "repo",
    );
    let first = generation - logs.len() as u64;
    let mut space_mem = SpaceMem::default();
    for (i, p) in logs.iter().enumerate() {
        pds_store::read_sealed(p, |offset, len, entries| {
            for e in &entries {
                match e["t"].as_str() {
                    Some("event") => {
                        let seq = e["seq"]
                            .as_u64()
                            .ok_or_else(|| format!("an event with no seq: {e}"))?;
                        let frame = hex_of(&e["frame"])?;
                        let time = crate::events::event_time(&frame).unwrap_or(0);
                        if events.last_key_value().is_some_and(|(l, _)| *l >= seq)
                            || repo.rev.is_empty()
                        {
                            return Err(format!("event {seq} out of order"));
                        }
                        small.last_seq = seq;
                        events.insert(seq, (time, frame));
                    }
                    Some("commit") => {
                        let path = |p: &Json| {
                            p.as_str()
                                .map(str::to_string)
                                .ok_or_else(|| format!("a commit with {p} for a path"))
                        };
                        let list = |k: &str| {
                            e[k].as_array()
                                .ok_or_else(|| format!("a commit with no {k}"))
                        };
                        let c = Change {
                            rev: e["rev"].as_str().ok_or("a commit with no rev")?.to_string(),
                            head_bytes: hex_of(&e["head"])?,
                            puts: list("puts")?
                                .iter()
                                .map(|p| Ok((path(&p[0])?, p[1].clone())))
                                .collect::<Result<_, String>>()?,
                            dels: list("dels")?.iter().map(path).collect::<Result<_, _>>()?,
                            added: match e.get("added") {
                                Some(a) => a
                                    .as_array()
                                    .ok_or("a commit whose added is not a list")?
                                    .iter()
                                    .map(hex_of)
                                    .collect::<Result<_, _>>()?,
                                None => vec![],
                            },
                            ..Default::default()
                        };
                        repo.load(&c)?;
                        small.blobs.committed(&c);
                        small.blobs.take_doomed();
                        for p in &c.dels {
                            small.takedowns.remove(p);
                        }
                        small.tids.after(&c.rev);
                        small.head = c.head_bytes.clone();
                    }
                    Some(space_repo::ENTRY | space_repo::IMPORT | space_repo::DROP)
                        if small.unmarked.is_none() =>
                    {
                        let pos = Pos {
                            generation: first + i as u64,
                            offset,
                            len,
                        };
                        small.spaces.replay(
                            e,
                            pos,
                            &mut space_mem,
                            Old::None,
                            &cache,
                            &mut small.tids,
                            &mut small.blobs,
                        )?;
                    }
                    _ => {
                        let records = &repo.records;
                        small.replay(e, |p| records.contains_key(p))?;
                    }
                }
            }
            Ok(())
        })?;
    }
    if repo.rev.is_empty() {
        return Err("an account with no commit yet".into());
    }
    repo.finish_load()?;
    let revs: HashMap<&[u8], &str> = repo.block_revs().collect();
    let mut entries: BTreeMap<Vec<u8>, Vec<u8>> = BTreeMap::new();
    for (cid, bytes) in repo.tree_nodes() {
        entries.insert(
            key(b'B', cid),
            block_value(1, revs.get(cid).copied().unwrap_or_default(), bytes),
        );
    }
    let mut refs: HashMap<&[u8], u32> = HashMap::new();
    for r in repo.records.values() {
        *refs.entry(r.cid.as_slice()).or_default() += 1;
    }
    for (path, r) in &repo.records {
        entries.insert(
            key(b'B', &r.cid),
            block_value(
                refs[r.cid.as_slice()],
                revs.get(r.cid.as_slice()).copied().unwrap_or_default(),
                &r.bytes,
            ),
        );
        entries.insert(
            key(b'P', path.as_bytes()),
            path_value(&r.cid, &repo.written[path]),
        );
    }
    for (seq, (time, frame)) in events.iter().filter(|(_, (t, _))| t + 1000 + window >= now) {
        entries.insert(key(b'D', &seq.to_be_bytes()), time.to_be_bytes().to_vec());
        entries.insert(key(b'E', &seq.to_be_bytes()), frame.clone());
    }
    small.counts = (repo.records.len() as u64, repo.block_count() as u64 - 1);
    small.tids.after(&repo.tids.last());
    small.let_go = events
        .iter()
        .filter(|(_, (t, _))| t + 1000 + window < now)
        .map(|(seq, _)| *seq)
        .max()
        .unwrap_or(0);
    entries.insert(
        b"H".to_vec(),
        header_value(generation, small.last_seq, small.let_go),
    );
    entries.insert(b"S".to_vec(), small.encode(did, now));
    let mut frames = Frames {
        layout: &layout,
        files: HashMap::new(),
        indexes: Indexes::default(),
        holding: None,
    };
    let view = View {
        mem: &space_mem,
        old: Old::None,
        cache: &cache,
    };
    for section in [spaces::REFS, spaces::OPS, spaces::RECORDS, spaces::VALUES] {
        spaces::fold(
            section,
            view,
            &mut |pos, want| frames.item(pos, want),
            &mut |k, v| {
                entries.insert(k.to_vec(), v.to_vec());
                Ok(())
            },
        )?;
    }
    let mut w = TableWriter::new(io::BufWriter::new(out), entries.len() as u64);
    for (k, v) in &entries {
        w.add(k, v).map_err(|e| e.to_string())?;
    }
    let (mut out, _) = w.finish().map_err(|e| e.to_string())?;
    out.flush().map_err(|e| e.to_string())
}

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

impl Store {
    /// What its repository's blocks are read through.
    pub(crate) fn source(&self) -> Src<'_> {
        self.disk.source(&self.ctx.blocks)
    }

    /// The record at `path`.
    pub(crate) fn record(&self, path: &str) -> Option<Record> {
        self.repo.get(&self.source(), path)
    }

    /// Whether a record is at `path`.
    pub(crate) fn holds(&self, path: &str) -> bool {
        self.disk.path(&self.ctx.blocks, path).is_some()
    }

    /// The records of a collection from `from`, or before it if `reverse`,
    /// the last first, at most `limit`: each one's path and record.
    pub(crate) fn records(
        &self,
        collection: &str,
        from: &str,
        reverse: bool,
        limit: usize,
    ) -> Vec<(String, Record)> {
        let prefix = format!("{collection}/");
        let list = self
            .disk
            .records(&self.ctx.blocks, &prefix, from, reverse, limit);
        list.into_iter()
            .map(|(p, cid)| {
                let bytes = self
                    .disk
                    .block(&self.ctx.blocks, &cid)
                    .unwrap_or_else(|| self.disk.fail(format!("record {p} missing")));
                let value =
                    decode(&bytes).unwrap_or_else(|e| self.disk.fail(format!("record {p}: {e}")));
                (
                    p,
                    Record {
                        cid,
                        bytes: bytes.to_vec(),
                        value,
                    },
                )
            })
            .collect()
    }

    /// The collections it holds records of, in order.
    pub(crate) fn collections(&self) -> Vec<String> {
        let mut out: Vec<String> = Vec::new();
        let mut from = String::new();
        while let Some((p, _)) = self
            .disk
            .records(&self.ctx.blocks, "", &from, false, 1)
            .into_iter()
            .next()
        {
            let c = p.split('/').next().unwrap_or_default().to_string();
            // Past every path of the collection: `/` is followed by nothing before `0`.
            from = format!("{c}0");
            out.push(c);
        }
        out
    }

    /// Give `f` every record's path, CID and the rev that last wrote it, in order of path.
    pub(crate) fn each_path(&self, f: impl FnMut(&str, &[u8], &str)) {
        self.disk.each_path(&self.ctx.blocks, f);
    }

    /// The greatest seq of an event of its let go when its log was compacted.
    pub(crate) fn let_go(&self) -> u64 {
        self.disk.let_go
    }

    /// Its events: each one's seq and when it was made.
    pub(crate) fn event_seqs(&self) -> Vec<(u64, u64)> {
        self.disk.event_seqs(&self.ctx.blocks)
    }

    /// An event's frame, if it holds it.
    pub(crate) fn event_frame(&self, seq: u64) -> Option<Bytes> {
        self.disk.event_frame(&self.ctx.blocks, seq)
    }

    /// Its tree as it is now, to read as it is sent.
    pub(crate) fn snapshot(&self) -> io::Result<Snapshot> {
        self.disk
            .snapshot((self.repo.head.clone(), self.repo.head_bytes().to_vec()))
    }
}

#[cfg(test)]
mod tests {
    use crate::testing::*;
    use pds_repo::data::{cid_string, decode, to_json};
    use serde_json::{Value as Json, json};
    use std::collections::BTreeMap;

    fn params(p: &[(&str, &str)]) -> Vec<(String, String)> {
        p.iter()
            .map(|(k, v)| (k.to_string(), v.to_string()))
            .collect()
    }

    /// Every record listRecords pages through, newest first or not, `limit` at a time.
    async fn listed(s: &crate::Shared, did: &str, reverse: bool) -> Vec<(String, Json)> {
        let mut out = Vec::new();
        let mut cursor: Option<String> = None;
        loop {
            let mut p = params(&[
                ("repo", did),
                ("collection", "a.b.c"),
                ("limit", "7"),
                ("reverse", if reverse { "true" } else { "false" }),
            ]);
            if let Some(c) = &cursor {
                p.push(("cursor".into(), c.clone()));
            }
            let got = call_with(s, "com.atproto.repo.listRecords", None, &p, Json::Null)
                .await
                .unwrap();
            let page = got["records"].as_array().unwrap().clone();
            out.extend(page.iter().map(|r| {
                (
                    r["uri"]
                        .as_str()
                        .unwrap()
                        .rsplit('/')
                        .next()
                        .unwrap()
                        .to_string(),
                    r["value"].clone(),
                )
            }));
            match got["cursor"].as_str() {
                Some(c) if !page.is_empty() => cursor = Some(c.to_string()),
                _ => return out,
            }
        }
    }

    /// What the server answers of `did`'s records, as `want` says it holds
    /// them: by listRecords both ways, getRecord, and getRepo whole.
    async fn check(s: &crate::Shared, did: &str, want: &BTreeMap<String, Json>) {
        let asc: Vec<(String, Json)> = want.iter().map(|(k, v)| (k.clone(), v.clone())).collect();
        assert_eq!(listed(s, did, true).await, asc);
        let mut desc = asc.clone();
        desc.reverse();
        assert_eq!(listed(s, did, false).await, desc);
        for (k, v) in want {
            let got = call_with(
                s,
                "com.atproto.repo.getRecord",
                None,
                &params(&[("repo", did), ("collection", "a.b.c"), ("rkey", k)]),
                Json::Null,
            )
            .await
            .unwrap();
            assert_eq!(&got["value"], v);
        }
        let car = store_of(s, did, |st| {
            crate::sync::CarStream::of(st, None)
                .unwrap()
                .bytes()
                .unwrap()
        });
        let (roots, blocks) = pds_repo::read_car(&car).unwrap();
        assert_eq!(roots, vec![repo_of(s, did, |r| r.head.clone())]);
        let mut records: Vec<Json> = blocks
            .iter()
            .filter_map(|(_, b)| decode(b).ok())
            .map(|v| to_json(&v))
            .filter(|v| v["$type"] == "a.b.c")
            .collect();
        records.sort_by_key(|v| v.to_string());
        let mut wanted: Vec<Json> = want.values().cloned().collect();
        wanted.sort_by_key(|v| v.to_string());
        wanted.dedup();
        assert_eq!(records, wanted);
        // Every block is held, and none twice.
        let cids: Vec<String> = blocks.iter().map(|(c, _)| cid_string(c)).collect();
        let mut unique = cids.clone();
        unique.sort();
        unique.dedup();
        assert_eq!(unique.len(), cids.len());
        assert_eq!(cids.len() as u64, repo_of(s, did, |r| r.block_count()));
    }

    /// Writes, rewrites and deletes across many compactions, the account's
    /// store let go and loaded again between them, and the server started
    /// again: every read answers what the writes left, from the table, the
    /// log after it, or both.
    #[tokio::test]
    async fn reads_across_compactions() {
        let plc = plc().await;
        let dir = scratch("ckpt-reads");
        let opened = |dir: &std::path::Path| {
            open_with(dir, &plc, |c| {
                c.load_all = false;
                c.log_floor = 2048;
            })
        };
        let mut s = opened(&dir);
        let (did, token) = create(&s, "alice").await;
        let mut want: BTreeMap<String, Json> = BTreeMap::new();
        let mut n = 0;
        for round in 0..6 {
            for i in 0..25 {
                n += 1;
                let k = format!("k{:02}", (i * 7 + round * 3) % 40);
                if i % 5 == 4 && want.contains_key(&k) {
                    call(
                        &s,
                        "com.atproto.repo.deleteRecord",
                        Some(&token),
                        json!({ "repo": did, "collection": "a.b.c", "rkey": k }),
                    )
                    .await
                    .unwrap();
                    want.remove(&k);
                    continue;
                }
                // Some records the same as another's, so that a block is held by two paths.
                let value = json!({ "$type": "a.b.c", "n": if i % 6 == 0 { 0 } else { n } });
                call(
                    &s,
                    "com.atproto.repo.putRecord",
                    Some(&token),
                    json!({ "repo": did, "collection": "a.b.c", "rkey": k, "record": value }),
                )
                .await
                .unwrap();
                want.insert(k, value);
            }
            let wal = store_of(&s, &did, |st| st.wal.clone());
            wal.wait_compacted();
            assert!(wal.checkpoint_generation() > 0, "never compacted");
            drop(wal);
            check(&s, &did, &want).await;
            if round % 2 == 0 {
                let a = s.account(&did).unwrap();
                assert!(a.store.evict());
                check(&s, &did, &want).await;
            } else {
                drop(s);
                s = opened(&dir);
                check(&s, &did, &want).await;
            }
        }
        let _ = std::fs::remove_dir_all(&dir);
    }

    async fn put(s: &crate::Shared, did: &str, token: &str, k: &str, value: &Json) {
        call(
            s,
            "com.atproto.repo.putRecord",
            Some(token),
            json!({ "repo": did, "collection": "a.b.c", "rkey": k, "record": value }),
        )
        .await
        .unwrap();
    }

    /// The generation of `did`'s table, once no compaction of its log runs.
    fn compacted(s: &crate::Shared, did: &str) -> u64 {
        let wal = store_of(s, did, |st| st.wal.clone());
        wal.wait_compacted();
        wal.checkpoint_generation()
    }

    /// A repository being sent is read whole from the table it began with,
    /// though a compaction replaces that table meanwhile, and the table's
    /// file is closed once it is sent. Of more accounts' tables than may be
    /// open at once, no more files are open than that, each account read
    /// from its file all the same; and a store let go closes its table's.
    #[tokio::test]
    async fn tables_replaced_and_held_open() {
        let plc = plc().await;
        let dir = scratch("ckpt-open");
        let s = open_with(&dir, &plc, |c| {
            c.load_all = false;
            c.log_floor = 2048;
        });
        let open = || s.ctx.blocks.open_files();
        let (did, token) = create(&s, "alice").await;
        let mut want: Vec<Json> = Vec::new();
        for i in 0..30 {
            let value = json!({ "$type": "a.b.c", "n": i, "t": "x".repeat(200) });
            put(&s, &did, &token, &format!("k{i:02}"), &value).await;
            want.push(value);
        }
        let first = compacted(&s, &did);
        assert!(first > 0, "never compacted");
        assert_eq!(open(), 1);
        let (head, stream) = store_of(&s, &did, |st| {
            (
                st.repo.head.clone(),
                crate::sync::CarStream::of(st, None).unwrap(),
            )
        });
        // Every record written again, until another table is in its place.
        let mut n = 0;
        while compacted(&s, &did) == first {
            let value = json!({ "$type": "a.b.c", "n": 1000 + n });
            put(&s, &did, &token, &format!("k{:02}", n % 30), &value).await;
            n += 1;
            assert!(n < 1000, "never compacted again");
        }
        assert_eq!(open(), 2);
        let (roots, blocks) = pds_repo::read_car(&stream.bytes().unwrap()).unwrap();
        assert_eq!(roots, vec![head]);
        let mut records: Vec<Json> = blocks
            .iter()
            .filter_map(|(_, b)| decode(b).ok())
            .map(|v| to_json(&v))
            .filter(|v| v["$type"] == "a.b.c")
            .collect();
        records.sort_by_key(|v| v["n"].as_u64());
        assert_eq!(records, want);
        assert_eq!(open(), 1);

        let mut dids = vec![did];
        let share = s.config.share;
        for i in 0..share + 5 {
            let (did, token) = create(&s, &format!("user{i}")).await;
            let value = json!({ "$type": "a.b.c", "t": "x".repeat(3000) });
            put(&s, &did, &token, "k00", &value).await;
            assert!(compacted(&s, &did) > 0, "never compacted");
            assert!(open() <= share);
            dids.push(did);
        }
        assert_eq!(open(), share);
        for did in &dids {
            // Nothing of its table in memory: the record is read from its file.
            store_of(&s, did, |st| {
                st.ctx.blocks.forget(st.disk.table.as_ref().unwrap().id())
            });
            let got = call_with(
                &s,
                "com.atproto.repo.getRecord",
                None,
                &params(&[("repo", did), ("collection", "a.b.c"), ("rkey", "k00")]),
                Json::Null,
            )
            .await
            .unwrap();
            assert_eq!(got["value"]["$type"], "a.b.c");
            assert_eq!(open(), share);
        }
        for (i, did) in dids.iter().enumerate() {
            assert!(s.account(did).unwrap().store.evict());
            assert!(open() < dids.len() - i);
        }
        assert_eq!(open(), 0);
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// A commit's frame is JSON with holes, and each of its tree's nodes and
    /// its event is read alone, by the frame's index, as the bytes the hole
    /// holds: only those bytes are read, as they are, nothing decoded. With
    /// no index yet, the whole frame is read once and indexed.
    #[tokio::test]
    async fn an_item_of_a_frame_with_holes_is_its_bytes_alone() {
        use super::{BYTES, Want, find, frame_item, index, read_at};
        use pds_store::table::BlockCache;
        let plc = plc().await;
        let dir = scratch("ckpt-holes");
        let s = open(&dir, &plc);
        let (did, token) = create(&s, "alice").await;
        for i in 0..40 {
            call(
                &s,
                "com.atproto.repo.createRecord",
                Some(&token),
                json!({ "repo": did, "collection": "a.b.c", "record": record(i) }),
            )
            .await
            .unwrap();
        }
        let layout = crate::store::account_layout(&dir, &did);
        let generation = store_of(&s, &did, |st| st.wal.generation());
        let path = layout.log(generation);
        // The last frame of the log: the last commit's.
        let mut last = None;
        pds_store::scan_file(&path, |offset, len, entries| {
            last = Some((offset, len, entries));
            Ok(())
        })
        .unwrap()
        .unwrap();
        let (offset, len, entries) = last.unwrap();
        let pos = pds_store::Pos {
            generation,
            offset,
            len,
        };
        let file = std::fs::File::open(&path).unwrap();
        let frame = read_at(&file, offset, len as usize).unwrap();
        assert_eq!(frame[pds_store::HEADER], pds_store::HOLES);
        let commit = entries.iter().find(|e| e["t"] == "commit").unwrap();
        let event = entries.iter().find(|e| e["t"] == "event").unwrap();
        let unhex = |v: &Json| hex::decode(v.as_str().unwrap()).unwrap();
        let nodes: Vec<(Vec<u8>, Vec<u8>)> = commit["tree"]
            .as_array()
            .unwrap()
            .iter()
            .map(|n| (unhex(&n[0]), unhex(&n[1])))
            .collect();
        assert!(!nodes.is_empty());
        let (seq, event_frame) = (event["seq"].as_u64().unwrap(), unhex(&event["frame"]));
        let reads = std::cell::RefCell::new(Vec::new());
        let read = |at: u64, n: usize| {
            reads.borrow_mut().push((at, n));
            read_at(&file, at, n)
        };
        let cache = BlockCache::new(1 << 20);
        let got = frame_item(&cache, 1, pos, &read, Want::Event(seq)).unwrap();
        assert_eq!(got, Some(event_frame.clone()));
        assert_eq!(
            reads.take(),
            [(offset, len as usize)],
            "the frame, to index it"
        );
        let ix = index(&frame[pds_store::HEADER..]).unwrap().unwrap();
        let mut wants: Vec<(Want, Vec<u8>)> = nodes
            .iter()
            .map(|(cid, node)| (Want::Block(cid), node.clone()))
            .collect();
        wants.push((Want::Event(seq), event_frame));
        for (want, bytes) in wants {
            let (how, start, n) = find(&ix, want).unwrap();
            assert_eq!((how, n), (BYTES, bytes.len()));
            let got = frame_item(&cache, 1, pos, &read, want).unwrap();
            assert_eq!(got, Some(bytes.clone()));
            let at = offset + (pds_store::HEADER + start) as u64;
            assert_eq!(reads.take(), [(at, bytes.len())], "its bytes alone");
            assert_eq!(&frame[(at - offset) as usize..][..bytes.len()], &bytes[..]);
        }
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// A fold reads each frame of its logs whole once, to index it, and
    /// then each item alone, however large the frame's index. An import's
    /// frame, one commit of a whole repository, has an index larger than the
    /// fold's block cache keeps any entry (an eighth of it, 4 MiB at most),
    /// which was made again, the whole frame read, for each of its items:
    /// so the import's log is compacted at once, as a write's is.
    #[tokio::test]
    async fn a_fold_indexes_each_frame_once() {
        use super::{ENTRY, Indexes, Want, read_at};
        use axum::http::{HeaderMap, HeaderValue, Method, header};
        const RECORDS: usize = 12_000;
        let plc = plc().await;
        let dir = scratch("ckpt-fold-index");
        // Compacted only when the test says.
        let s = open_with(&dir, &plc, |c| c.log_floor = 1 << 30);
        let (did, token) = create(&s, "alice").await;
        // A repository of its records, imported whole: one frame.
        let key = k256::ecdsa::SigningKey::from_slice(&[5u8; 32]).unwrap();
        let mut repo = pds_repo::full::Repo::new(did.clone(), key);
        repo.init();
        for batch in (0..RECORDS).collect::<Vec<_>>().chunks(200) {
            let ops = batch
                .iter()
                .map(|i| pds_repo::Op::Create {
                    collection: "a.b.c".into(),
                    rkey: Some(format!("k{i:05}")),
                    value: pds_repo::data::from_json(&record(*i as i64)).unwrap(),
                })
                .collect();
            repo.apply(ops, None).unwrap();
        }
        let car = repo.car();
        let mut headers = HeaderMap::new();
        headers.insert(
            header::CONTENT_TYPE,
            HeaderValue::from_static("application/vnd.ipld.car"),
        );
        headers.insert(
            header::AUTHORIZATION,
            HeaderValue::from_str(&format!("Bearer {token}")).unwrap(),
        );
        let authorization = crate::authorization(&headers);
        let call = crate::Call {
            nsid: "com.atproto.repo.importRepo",
            method: &Method::POST,
            params: &[],
            body: &car,
            bearer: crate::sessions::Bearer::of(authorization.as_deref()),
            headers: &headers,
            client: "127.0.0.1".into(),
            charged: std::sync::OnceLock::new(),
            http: None,
        };
        assert!(matches!(
            crate::answer(&s, &call).await,
            Ok(crate::Resp::Nothing)
        ));
        // The import's frame, and its items: its records and tree nodes.
        let layout = crate::store::account_layout(&dir, &did);
        let generation = store_of(&s, &did, |st| st.wal.generation());
        let path = layout.log(generation);
        let mut found = None;
        pds_store::scan_file(&path, |offset, len, entries| {
            if let Some(c) = entries
                .iter()
                .find(|e| e["t"] == "commit" && e["puts"].as_array().unwrap().len() == RECORDS)
            {
                found = Some((offset, len, c.clone()));
            }
            Ok(())
        })
        .unwrap()
        .unwrap();
        let (offset, len, commit) = found.unwrap();
        let unhex = |v: &Json| hex::decode(v.as_str().unwrap()).unwrap();
        let mut cids: Vec<Vec<u8>> = commit["puts"]
            .as_array()
            .unwrap()
            .iter()
            .map(|p| unhex(&p[2]))
            .collect();
        cids.extend(
            commit["tree"]
                .as_array()
                .unwrap()
                .iter()
                .map(|n| unhex(&n[0])),
        );
        assert!(
            cids.len() * ENTRY > (4 << 20) / 8,
            "an index the fold's cache would keep"
        );
        // Read as the fold reads them: the frame whole once, then each item alone.
        let pos = pds_store::Pos {
            generation,
            offset,
            len,
        };
        let file = std::fs::File::open(&path).unwrap();
        let whole = std::cell::Cell::new(0);
        let read = |at: u64, n: usize| {
            if (at, n) == (offset, len as usize) {
                whole.set(whole.get() + 1);
            }
            read_at(&file, at, n)
        };
        let mut indexes = Indexes::default();
        for cid in &cids {
            let block = indexes.item(pos, &read, Want::Block(cid)).unwrap();
            assert!(block.is_some(), "{} missing", cid_string(cid));
        }
        assert_eq!(whole.get(), 1, "the frame read whole for each of its items");
        // And so the log is compacted in a moment, not in the time it takes
        // to read the frame once for each item.
        let wal = store_of(&s, &did, |st| st.wal.clone());
        let started = std::time::Instant::now();
        wal.compact().unwrap();
        let took = started.elapsed();
        assert!(
            took < std::time::Duration::from_secs(30),
            "compacted in {took:?}"
        );
        store_of(&s, &did, |st| {
            st.ctx.blocks.forget(st.disk.table.as_ref().unwrap().id())
        });
        assert_eq!(records_of(&s, &did).len(), RECORDS);
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// The notifications' part of a table: written and read back whole,
    /// lapsed registrations and kept notices too.
    #[test]
    fn notify_state_round_trips() {
        use super::{Small, read_notify};
        use crate::space_notify::{Kept, Notice, Owed, Registration, Schedule};
        use pds_repo::data::V;
        let m = "at://did:plc:alicealicealicealicealic/space/com.example.forum/m".to_string();
        let q = "at://did:plc:elsewhereelsewhereelsewhe/space/com.example.forum/q";
        let at = Schedule {
            n: 1,
            due: 10,
            until: 20,
        };
        let mut k = Kept::default();
        k.queue.insert(
            q.to_string(),
            crate::space_notify::Pending {
                rev: "3jzfcijpj2z2a".into(),
                data: vec![1; 32],
                at,
            },
        );
        let pair = |e: &str, t: &str| (e.to_string(), t.to_string());
        k.register(
            m.clone(),
            pair("https://a.example", "a"),
            Registration {
                expires: 5,
                noticed: true,
            },
        );
        k.register(
            m.clone(),
            pair("https://b.example/", ""),
            Registration {
                expires: 9,
                noticed: false,
            },
        );
        k.notices.insert(
            (m.clone(), pair("https://a.example", "a")),
            Notice {
                owed: Owed::Expired {
                    space_rev: "3jzfcijpj2z2b".into(),
                    lapse: 5,
                },
                at,
            },
        );
        k.notices.insert(
            (m.clone(), pair("https://c.example", "c")),
            Notice {
                owed: Owed::Deleted,
                at,
            },
        );
        let mut small = Small::new();
        small.notify = k.clone();
        let state =
            pds_repo::data::decode(&small.encode("did:plc:alicealicealicealicealic", 0)).unwrap();
        let V::Map(fields) = state else {
            panic!("a state that is no map")
        };
        let notify = fields.into_iter().find(|(k, _)| k == "notify").unwrap().1;
        assert_eq!(read_notify(notify).unwrap(), k);
    }
}