~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
1878 lines · 68.8 KB Raw History
//! The service log's checkpoint (`spec/STORE.md`, "Bounds" and "Scale"):
//! what the service log holds now, folded from the checkpoint before and the
//! sealed logs after it into a sorted table (`pds_store::table`), read as it
//! is needed through the block cache the accounts' tables share, never
//! whole. Its entries, by key:
//!
//! - `A` + DID: the account's **row**, `[ordinal, u64 big-endian][a JSON
//!   array]`: the entries that make the account again (`One::entries`), its
//!   `account` entry with the handle, email and password it has now, its
//!   app passwords and the sessions it keeps, what is known of its email
//!   and the tokens mailed for it, its state, and its preferences as last
//!   put. The ordinal is its place in the order accounts were made, given
//!   once: a deleted account's is never given again;
//! - `H` + handle + NUL + DID, `M` + email + NUL + DID and `T` + password
//!   reset token + NUL + DID, each with no value: **hints**, the accounts
//!   that may have that handle, email or token. What an account has is what
//!   its row says, so whoever follows a hint loads the account and looks;
//! - `O` + ordinal, u64 big-endian: the DID, every account's, which
//!   `listRepos` reads in order;
//! - `R` + index, u64 big-endian: a JSON array of at most `ROW_ENTRIES`
//!   entries that are not one account's, in the order they are replayed:
//!   the invite codes and their uses, the single-use values still held,
//!   each deletion whose event is in the backfill window and the firehose
//!   events the log holds in it, OAuth's entries with only each session's
//!   latest refresh and what each device's last entries leave, the marks
//!   standing (`cache`), and with blobs in a bucket, the objects of deleted
//!   accounts not yet deleted (`blobstore`);
//! - `S`: one JSON object, the `Summary`: its generation, the last event's
//!   seq and the greatest reserved, the next ordinal, and how many accounts
//!   there are, and of them deactivated and taken down.
//!
//! The fold reads the logs, not memory, so that it is exactly what replay
//! would make of them: a frame at a time, keeping what is not one account's
//! as it is replayed, and of the accounts only the entries the logs hold,
//! as text, by DID. Then one pass over the rows before in order of DID: a
//! row no log touched is copied as it is, unparsed; one a log touched is
//! its entries and the logs' folded (`One`) and written; a deleted
//! account's is left out. The hints and ordinals before are copied but
//! those of the accounts the logs touched, which are written as their rows
//! now say. So what a fold holds follows the logs it folds, not the
//! accounts there are (`spec/STORE.md`, "Scale"). It leaves out sessions
//! that expired more than `MARGIN` ago, and single-use values held no
//! longer than that: none of those can be named by an entry still to come.
//!
//! A checkpoint of the format before this one, a log of frames whose first
//! names its generation, is folded alone into a table of the same
//! generation when a start finds it (`convert`).

use crate::email::Mail;
use crate::lifecycle::State;
use crate::log::AccountEntry;
use crate::sessions::{self, Keep};
use pds_store::Layout;
use pds_store::table::{BlockCache, Table, TableWriter};
use serde_json::{Value as Json, json};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::fs::File;
use std::io::{self, Write};
use std::path::{Path, PathBuf};
use std::sync::Arc;

/// How long past its expiry a session is kept on disk.
pub(crate) const MARGIN: u64 = 60 * 60;

/// How many entries go in one `R` row: few, so that a start, which parses a
/// row whole before it replays it, holds little of it at once
/// (`spec/STORE.md`, "Scale").
const ROW_ENTRIES: usize = 32;

/// The format's version, the only one this server knows.
const VERSION: u64 = 1;

/// The kind of the first entry of a service checkpoint of the format before.
const HEADER: &str = "checkpoint";

/// The bytes of the table before a fold holds as it reads it.
const FOLD_CACHE: u64 = 4 << 20;

const ROW: u8 = b'A';
pub(crate) const HANDLE: u8 = b'H';
pub(crate) const EMAIL: u8 = b'M';
const ORDER: u8 = b'O';
const REST: u8 = b'R';
const SUMMARY: &[u8] = b"S";
pub(crate) const TOKEN: u8 = b'T';

fn row_key(did: &str) -> Vec<u8> {
    [&[ROW], did.as_bytes()].concat()
}

/// The start of every hint of `name` in `section`.
fn hint_prefix(section: u8, name: &str) -> Vec<u8> {
    [&[section], name.as_bytes(), &[0]].concat()
}

/// The hint that `did` may have `name`: no name holds a NUL.
fn hint_key(section: u8, name: &str, did: &str) -> Result<Vec<u8>, String> {
    if name.contains('\0') || did.contains('\0') {
        return Err(format!("{did}: {name:?} holds a NUL"));
    }
    Ok([&hint_prefix(section, name), did.as_bytes()].concat())
}

fn numbered(section: u8, n: u64) -> Vec<u8> {
    [&[section][..], &n.to_be_bytes()].concat()
}

fn number_of(key: &[u8]) -> Option<u64> {
    Some(u64::from_be_bytes(key.get(1..)?.try_into().ok()?))
}

/// The DID a hint or an ordinal names.
fn named_did<'a>(section: u8, key: &'a [u8], value: &'a [u8]) -> Option<&'a str> {
    let did = if section == ORDER {
        value
    } else {
        let nul = key.iter().position(|b| *b == 0)?;
        &key[nul + 1..]
    };
    std::str::from_utf8(did).ok()
}

fn row_value(ordinal: u64, entries: &[Json]) -> Vec<u8> {
    let mut out = ordinal.to_be_bytes().to_vec();
    serde_json::to_writer(&mut out, entries).expect("entries serialize");
    out
}

/// A row's ordinal and entries.
fn parse_row(v: &[u8]) -> Result<(u64, Vec<Json>), String> {
    let ordinal = v
        .get(..8)
        .and_then(|n| n.try_into().ok())
        .map(u64::from_be_bytes)
        .ok_or("a row with no ordinal")?;
    let entries = serde_json::from_slice(&v[8..]).map_err(|e| format!("a row: {e}"))?;
    Ok((ordinal, entries))
}

/// The `S` entry: what a start reads of a table before anything else.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct Summary {
    pub generation: u64,
    /// The greatest seq of the events the service log has held.
    pub last_seq: u64,
    /// The greatest seq reserved (`events::SEQS`), if any was.
    pub ceiling: Option<u64>,
    /// The ordinal the next account made is given.
    pub next_ordinal: u64,
    /// How many accounts there are, and of them deactivated, and taken down.
    pub accounts: u64,
    pub deactivated: u64,
    pub takendown: u64,
}

impl Summary {
    fn encode(&self) -> Vec<u8> {
        let mut s = json!({
            "version": VERSION, "generation": self.generation, "lastSeq": self.last_seq,
            "nextOrdinal": self.next_ordinal,
            "accounts": { "count": self.accounts, "deactivated": self.deactivated, "takendown": self.takendown },
        });
        if let Some(c) = self.ceiling {
            s["ceiling"] = json!(c);
        }
        s.to_string().into_bytes()
    }

    fn decode(bytes: &[u8]) -> Result<Summary, String> {
        let s: Json = serde_json::from_slice(bytes).map_err(|e| format!("its summary: {e}"))?;
        if s["version"].as_u64() != Some(VERSION) {
            return Err(format!("a checkpoint of version {}", s["version"]));
        }
        let number = |v: &Json, what: &str| {
            v.as_u64()
                .ok_or_else(|| format!("a summary with no {what}: {s}"))
        };
        let ceiling = match s.get("ceiling") {
            None => None,
            Some(c) => Some(number(c, "ceiling that is a number")?),
        };
        Ok(Summary {
            generation: number(&s["generation"], "generation")?,
            last_seq: number(&s["lastSeq"], "lastSeq")?,
            ceiling,
            next_ordinal: number(&s["nextOrdinal"], "nextOrdinal")?,
            accounts: number(&s["accounts"]["count"], "count of accounts")?,
            deactivated: number(
                &s["accounts"]["deactivated"],
                "count of accounts deactivated",
            )?,
            takendown: number(&s["accounts"]["takendown"], "count of accounts taken down")?,
        })
    }

    /// Count an account in, or out as its row before had it.
    fn count(&mut self, one: &One, add: bool) {
        let (deactivated, takendown) = (
            u64::from(one.state.deactivated),
            u64::from(one.state.takedown.is_some()),
        );
        if add {
            self.accounts += 1;
            self.deactivated += deactivated;
            self.takendown += takendown;
        } else {
            self.accounts = self.accounts.saturating_sub(1);
            self.deactivated = self.deactivated.saturating_sub(deactivated);
            self.takendown = self.takendown.saturating_sub(takendown);
        }
    }
}

/// The most bytes the first frame of a service checkpoint of the format
/// before takes: its header's, a few numbers.
const LEGACY_HEADER: u64 = 1024;

/// What the header of the file at `path` says, if the file is a service
/// checkpoint of the format before: a log whose first frame is its header.
/// Told by that frame, whose check no table's first bytes pass, not by how
/// the file ends, which is entries an account wrote.
fn legacy_header(path: &Path) -> io::Result<Option<(u64, u64, Option<u64>)>> {
    use std::os::unix::fs::FileExt;
    let file = File::open(path)?;
    let mut len = [0u8; 4];
    if file.read_exact_at(&mut len, 0).is_err() {
        return Ok(None);
    }
    let len = (pds_store::HEADER + u32::from_le_bytes(len) as usize) as u64;
    if len > LEGACY_HEADER.min(file.metadata()?.len()) {
        return Ok(None);
    }
    Ok(pds_store::read_frame(path, 0, len)
        .ok()
        .and_then(|first| header_of(&first).ok()))
}

/// A service checkpoint, read: its summary held, its rows, hints and
/// ordinals read as they are asked for, through `blocks`.
pub(crate) struct ServiceTable {
    table: Table,
    file: File,
    blocks: Arc<BlockCache>,
    pub summary: Summary,
}

impl Drop for ServiceTable {
    fn drop(&mut self) {
        self.blocks.forget(self.table.id());
    }
}

impl ServiceTable {
    /// The table at `path`, if there is a file there.
    pub fn open(path: &Path, blocks: Arc<BlockCache>) -> Result<Option<ServiceTable>, String> {
        match File::open(path) {
            Ok(file) => ServiceTable::open_file(path, file, blocks).map(Some),
            Err(e) if e.kind() == io::ErrorKind::NotFound => Ok(None),
            Err(e) => Err(format!("{}: {e}", path.display())),
        }
    }

    /// The table `file` holds, which is, or is about to be, at `path`.
    pub fn open_file(
        path: &Path,
        file: File,
        blocks: Arc<BlockCache>,
    ) -> Result<ServiceTable, String> {
        let at = |why: String| format!("{}: {why}", path.display());
        let table = Table::open_file(path, &file).map_err(|e| e.to_string())?;
        let summary = table
            .get_in(SUMMARY, Some(&file), &blocks)
            .map_err(|e| e.to_string())?
            .ok_or_else(|| at("a checkpoint with no summary".into()))?;
        let summary = Summary::decode(&summary).map_err(at)?;
        Ok(ServiceTable {
            table,
            file,
            blocks,
            summary,
        })
    }

    /// Its file's bytes.
    pub fn size(&self) -> u64 {
        self.table.size()
    }

    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>, String> {
        self.table
            .get_in(key, Some(&self.file), &self.blocks)
            .map_err(|e| e.to_string())
    }

    /// The entries of `section` from the first whose key is `from` or after.
    fn section<'a>(
        &'a self,
        section: u8,
        from: &[u8],
    ) -> impl Iterator<Item = Result<(Vec<u8>, Vec<u8>), String>> + use<'a> {
        self.table
            .iter(from, Some(&self.file), &self.blocks)
            .map(|r| r.map_err(|e| e.to_string()))
            .take_while(move |r| {
                r.as_ref()
                    .map_or(true, |(k, _)| k.first() == Some(&section))
            })
    }

    /// Whether it may hold a row of `did`: false only if it holds none.
    /// Reads nothing.
    pub fn may_hold(&self, did: &str) -> bool {
        self.table.may_hold(&row_key(did))
    }

    /// Whether it holds a row of `did`.
    pub fn has(&self, did: &str) -> Result<bool, String> {
        Ok(self.get(&row_key(did))?.is_some())
    }

    /// The row of `did`: its ordinal and entries.
    pub fn row(&self, did: &str) -> Result<Option<(u64, Vec<Json>)>, String> {
        match self.get(&row_key(did))? {
            Some(v) => parse_row(&v)
                .map(Some)
                .map_err(|why| format!("{}: {did}: {why}", self.table.path().display())),
            None => Ok(None),
        }
    }

    /// The accounts hinted to have `name`, a handle (`HANDLE`), an email
    /// (`EMAIL`) or a password reset token (`TOKEN`).
    pub fn hints(&self, section: u8, name: &str) -> Result<Vec<String>, String> {
        let prefix = hint_prefix(section, name);
        let mut out = Vec::new();
        for r in self.section(section, &prefix) {
            let (k, _) = r?;
            let Some(did) = k.strip_prefix(prefix.as_slice()) else {
                break;
            };
            out.push(String::from_utf8_lossy(did).into_owned());
        }
        Ok(out)
    }

    /// Each account's ordinal and DID, in order, from ordinal `from` on.
    pub fn order(&self, from: u64) -> impl Iterator<Item = Result<(u64, String), String>> + '_ {
        self.section(ORDER, &numbered(ORDER, from)).map(|r| {
            let (k, v) = r?;
            let n = number_of(&k).ok_or("an ordinal that does not parse")?;
            Ok((n, String::from_utf8_lossy(&v).into_owned()))
        })
    }

    /// Give `f` each `R` row's entries, in order.
    pub fn rest(&self, mut f: impl FnMut(Vec<Json>) -> Result<(), String>) -> Result<(), String> {
        for r in self.section(REST, &[REST]) {
            let (_, v) = r?;
            f(serde_json::from_slice(&v).map_err(|e| format!("a row of entries: {e}"))?)?;
        }
        Ok(())
    }
}

/// The DID of the account an entry of the service log is of, if it is one
/// account's, kept in its row: its `account` entry, a change to its
/// sessions and app passwords, to its email, password and mailed tokens, to
/// its state or its preferences, or a mark that gives its handle.
pub(crate) fn of_account(e: &Json) -> Result<Option<&str>, String> {
    let Some(t) = e["t"].as_str() else {
        return Ok(None);
    };
    let one = t == "account"
        || sessions::ENTRIES.contains(&t)
        || crate::email::ENTRIES.contains(&t)
        || crate::lifecycle::STATES.contains(&t)
        || t == crate::preferences::ENTRY
        || (t == crate::cache::DIR && e.get("handle").is_some());
    if !one {
        return Ok(None);
    }
    e["did"]
        .as_str()
        .map(Some)
        .ok_or_else(|| format!("an entry with no did: {e}"))
}

/// One account, as the entries of its row and of the logs after leave it.
#[derive(Default)]
pub(crate) struct One {
    /// Its `account` entry, as logged.
    account: Option<Json>,
    /// Its email and password, and what is known of the email: of an account made.
    mail: Option<Mail>,
    keep: Keep,
    state: State,
    /// Its preferences as last put: the entry.
    prefs: Option<Json>,
    /// The handle its marks last gave it, if any did.
    handle: Option<String>,
}

/// What an account is made of, parsed: what `One` leaves of it.
pub(crate) struct Parts {
    pub entry: AccountEntry,
    pub mail: Mail,
    pub keep: Keep,
    pub state: State,
    pub prefs: Option<Vec<Json>>,
}

impl One {
    /// Make the change an entry of the account's says (`of_account`).
    pub fn apply(&mut self, e: Json) -> Result<(), String> {
        let t = e["t"].as_str().unwrap_or_default();
        if t == "account" {
            if self.account.is_some() {
                return Err(format!("a second account with the DID of {}", e["did"]));
            }
            let text = |k: &str| e[k].as_str().map(str::to_string);
            self.mail = Some(Mail::new(text("email"), text("password")));
            self.account = Some(e);
            return Ok(());
        }
        let Some(mail) = &mut self.mail else {
            return Err(format!("a {t} entry of {}, which no account has", e["did"]));
        };
        if sessions::ENTRIES.contains(&t) {
            self.keep.apply(&e)
        } else if crate::email::ENTRIES.contains(&t) {
            mail.apply(&e)
        } else if crate::lifecycle::STATES.contains(&t) {
            self.state.apply(&e)
        } else if t == crate::preferences::ENTRY {
            crate::preferences::parse(&e)?;
            self.prefs = Some(e);
            Ok(())
        } else if t == crate::cache::DIR {
            if let Some(h) = e.get("handle") {
                let h = h
                    .as_str()
                    .ok_or_else(|| format!("a mark whose handle is not a string: {e}"))?;
                self.handle = Some(h.to_string());
            }
            Ok(())
        } else {
            Err(format!("a log entry that is not one account's: {t:?}"))
        }
    }

    /// Whether its `account` entry made it.
    pub fn is_made(&self) -> bool {
        self.account.is_some()
    }

    /// Its handle: the last its marks gave it, or else its entry's.
    fn handle(&self) -> Option<&str> {
        self.handle
            .as_deref()
            .or_else(|| self.account.as_ref()?.get("handle")?.as_str())
    }

    /// The entries that make it again, for its row: its `account` entry
    /// with the handle, email and password it has now, then its sessions
    /// and app passwords but the sessions that expired before `before`, its
    /// mail, its state, and its preferences.
    fn entries(&self, did: &str, before: u64) -> Result<Vec<Json>, String> {
        let (Some(account), Some(mail)) = (&self.account, &self.mail) else {
            return Err(format!("{did}: no account entry made it"));
        };
        let mut a = account.clone();
        a["email"] = json!(mail.email);
        a["password"] = json!(mail.password);
        if let Some(h) = &self.handle {
            a["handle"] = json!(h);
        }
        let mut out = vec![a];
        out.extend(self.keep.entries(did, before));
        out.extend(mail.entries(did));
        out.extend(self.state.entries(did));
        out.extend(self.prefs.clone());
        Ok(out)
    }

    /// The account, parsed: an error if what made it does not parse.
    pub fn parts(self) -> Result<Parts, String> {
        let (Some(account), Some(mail)) = (self.account, self.mail) else {
            return Err("no account entry made it".into());
        };
        let mut entry = AccountEntry::parse(&account)?;
        if let Some(h) = self.handle {
            entry.handle = h;
        }
        let prefs = match &self.prefs {
            Some(e) => Some(crate::preferences::parse(e)?),
            None => None,
        };
        Ok(Parts {
            entry,
            mail,
            keep: self.keep,
            state: self.state,
            prefs,
        })
    }
}

/// The service checkpoint of `generation`, written to `out` as it is made:
/// the checkpoint before, the file at `checkpoint` if there is one, a table
/// or of the format before, and the sealed logs after it, `logs` in order,
/// read a frame at a time and folded, at `now` in seconds, keeping the
/// events `keep` keeps.
pub(crate) fn fold_files(
    checkpoint: Option<&Path>,
    logs: &[PathBuf],
    generation: u64,
    now: u64,
    keep: impl Fn(u64, &[u8]) -> bool,
    out: &mut dyn Write,
) -> Result<(), String> {
    let mut folder = Folder::new(now.saturating_sub(MARGIN), now);
    let mut before = Summary::default();
    let mut old = None;
    if let Some(path) = checkpoint {
        let at = |why: String| format!("{}: {why}", path.display());
        if legacy_header(path)
            .map_err(|e| at(e.to_string()))?
            .is_some()
        {
            let mut first = true;
            let (whole, size) = pds_store::scan_file(path, |_, _, entries| {
                if std::mem::take(&mut first) {
                    (_, before.last_seq, before.ceiling) = header_of(&entries)?;
                    return Ok(());
                }
                entries.into_iter().try_for_each(|e| folder.apply(e))
            })
            .map_err(|e| at(e.to_string()))?
            .map_err(at)?;
            if first || whole != size {
                return Err(at("a checkpoint that is not whole".into()));
            }
        } else {
            let table = ServiceTable::open(path, Arc::new(BlockCache::new(FOLD_CACHE)))?
                .ok_or_else(|| at("no longer there".into()))?;
            before = table.summary.clone();
            table.rest(|entries| entries.into_iter().try_for_each(|e| folder.apply(e)))?;
            old = Some(table);
        }
    }
    for log in logs {
        pds_store::read_sealed(log, |_, _, entries| {
            entries.into_iter().try_for_each(|e| folder.apply(e))
        })?;
    }
    folder.finish(keep, old.as_ref(), &before, generation, out)
}

/// Make a service checkpoint of the format before a table of the same
/// generation, folded alone at `now` in seconds, keeping the events `keep`
/// keeps; one that is a table already, or none, is left as it is. The table
/// is written beside it, made durable and renamed over it, so that a kill
/// at any point leaves one or the other whole.
pub(crate) fn convert(
    layout: &Layout,
    now: u64,
    keep: impl Fn(u64, &[u8]) -> bool,
) -> Result<(), String> {
    let path = layout.checkpoint();
    let at = |p: &Path, e: io::Error| format!("{}: {e}", p.display());
    let generation = match legacy_header(&path) {
        Ok(Some((generation, _, _))) => generation,
        Ok(None) => return Ok(()),
        Err(e) if e.kind() == io::ErrorKind::NotFound => return Ok(()),
        Err(e) => return Err(at(&path, e)),
    };
    let tmp = layout.tmp();
    let mut out = io::BufWriter::new(
        pds_store::open_private(
            &tmp,
            std::fs::OpenOptions::new()
                .create(true)
                .write(true)
                .truncate(true),
        )
        .map_err(|e| at(&tmp, e))?,
    );
    fold_files(Some(&path), &[], generation, now, keep, &mut out)?;
    let file = out.into_inner().map_err(|e| at(&tmp, e.into_error()))?;
    pds_store::sync_file(&file).map_err(|e| at(&tmp, e))?;
    drop(file);
    std::fs::rename(&tmp, &path).map_err(|e| at(&tmp, e))?;
    pds_store::sync_dir(&layout.dir).map_err(|e| at(&layout.dir, e))
}

/// What the first frame of a service checkpoint of the format before says:
/// its generation, the last seq it names, and the greatest seq reserved, if
/// any was.
fn header_of(first: &[Json]) -> Result<(u64, u64, Option<u64>), String> {
    let h = match first {
        [h] if h["t"] == HEADER => h,
        _ => return Err("a checkpoint whose first frame is not its header".into()),
    };
    let (Some(generation), Some(last_seq)) = (h["generation"].as_u64(), h["lastSeq"].as_u64())
    else {
        return Err(format!(
            "a checkpoint header with no generation or lastSeq: {h}"
        ));
    };
    let ceiling = match h.get("ceiling") {
        None => None,
        Some(c) => Some(
            c.as_u64()
                .ok_or_else(|| format!("a checkpoint header whose ceiling is not a number: {h}"))?,
        ),
    };
    Ok((generation, last_seq, ceiling))
}

/// What the logs folded hold of one account.
#[derive(Default)]
struct Touched {
    /// Its entries, as JSON text, one after another with commas between:
    /// less than they take parsed.
    text: String,
    /// Its place among the accounts the logs made, if they made it.
    made: Option<u64>,
    /// Whether the logs deleted it: its row before, if it had one, does not count.
    void: bool,
    /// Whether it is deleted now: not made again since.
    deleted: bool,
}

impl Touched {
    fn push(&mut self, e: &Json) {
        if !self.text.is_empty() {
            self.text.push(',');
        }
        self.text.push_str(&e.to_string());
    }
}

/// What the entries given so far hold now. Of what is not one account's:
/// without anything of the accounts deleted but their deletions whose
/// events are kept, nor single-use values and revocations whose `until` is
/// not after `now`; the marks kept are those standing (`cache`). Of each
/// account an entry names, its entries.
struct Folder {
    /// Sessions that expired before this are left out.
    before: u64,
    now: u64,
    marked: BTreeSet<String>,
    ceiling: Option<u64>,
    /// Each account the entries name, by DID.
    touched: BTreeMap<String, Touched>,
    /// How many accounts the entries made: each is given the next ordinal.
    made: u64,
    held: Vec<Json>,
    invites: crate::invites::Invites,
    lifecycle: crate::lifecycle::Replayed,
    oauth: Vec<Json>,
    spent: Vec<Json>,
    /// Deleted accounts' objects in a bucket not yet deleted, kept apart from
    /// what the fold drops of the accounts deleted.
    doomed: crate::blobstore::Doomed,
}

impl Folder {
    fn new(before: u64, now: u64) -> Folder {
        Folder {
            before,
            now,
            marked: Default::default(),
            ceiling: None,
            touched: BTreeMap::new(),
            made: 0,
            held: Vec::new(),
            invites: Default::default(),
            lifecycle: Default::default(),
            oauth: Vec::new(),
            spent: Vec::new(),
            doomed: Default::default(),
        }
    }

    /// Keep an entry of the account `did`, unless it is deleted.
    fn touch(&mut self, did: &str, e: &Json) {
        let t = self.touched.entry(did.to_string()).or_default();
        if !t.deleted {
            t.push(e);
        }
    }

    /// Fold one entry in.
    fn apply(&mut self, e: Json) -> Result<(), String> {
        let did_of = |e: &Json, what: &str| {
            e["did"]
                .as_str()
                .map(str::to_string)
                .ok_or_else(|| format!("{what} with no did: {e}"))
        };
        match e["t"].as_str() {
            Some("account") => {
                let did = did_of(&e, "an account")?;
                let t = self.touched.entry(did).or_default();
                t.deleted = false;
                t.made.get_or_insert(self.made);
                t.push(&e);
                self.made += 1;
            }
            Some(crate::cache::DIR) => {
                let did = did_of(&e, "a mark")?;
                if self.touched.get(&did).is_some_and(|t| t.deleted) {
                    return Ok(());
                }
                if e.get("handle").is_some() {
                    self.touch(&did, &e);
                }
                if e["eager"].as_bool() == Some(true) {
                    self.marked.insert(did);
                } else {
                    self.marked.remove(&did);
                }
            }
            Some(t)
                if crate::lifecycle::ENTRIES.contains(&t)
                    && !crate::lifecycle::STATES.contains(&t) =>
            {
                if let Some(did) = self.lifecycle.replay(&e)? {
                    let t = self.touched.entry(did.clone()).or_default();
                    *t = Touched {
                        void: true,
                        deleted: true,
                        ..Touched::default()
                    };
                    self.marked.remove(&did);
                    // OAuth forgets the account as it is deleted: what it
                    // logs of one made again with the DID after is kept.
                    self.oauth = crate::oauth::without_accounts(
                        std::mem::take(&mut self.oauth),
                        &HashSet::from([did]),
                    );
                }
            }
            Some(crate::events::SEQS) => {
                let upto = e["upto"]
                    .as_u64()
                    .ok_or_else(|| format!("seqs with no upto: {e}"))?;
                self.ceiling = Some(self.ceiling.unwrap_or(0).max(upto));
            }
            Some(t) if crate::invites::ENTRIES.contains(&t) => self.invites.replay(&e)?,
            Some(t) if crate::oauth::ENTRIES.contains(&t) => self.oauth.push(e),
            Some(crate::replay::ENTRY) => {
                if e["until"].as_u64().is_none_or(|u| u > self.before) {
                    self.spent.push(e);
                }
            }
            Some(t) if t == crate::single_use::ENTRY || t == crate::space_credentials::ENTRY => {
                let until = e["until"]
                    .as_u64()
                    .ok_or_else(|| format!("a {t} entry with no until: {e}"))?;
                if until > self.now {
                    self.held.push(e);
                }
            }
            Some(t) if crate::blobstore::ENTRIES.contains(&t) => self.doomed.replay(&e)?,
            t => match of_account(&e)? {
                Some(did) => {
                    let did = did.to_string();
                    self.touch(&did, &e);
                }
                None => return Err(format!("a log entry of no known type: {t:?}")),
            },
        }
        Ok(())
    }

    /// Write the table of `generation` to `out`: the rows of `old`, the
    /// table before, whose summary is `before`, merged with what the
    /// entries given hold of each account; then the hints and ordinals, the
    /// entries that are not one account's, the events those `keep` keeps,
    /// and the summary.
    fn finish(
        self,
        keep: impl Fn(u64, &[u8]) -> bool,
        old: Option<&ServiceTable>,
        before: &Summary,
        generation: u64,
        out: &mut dyn Write,
    ) -> Result<(), String> {
        let werr = |e: io::Error| e.to_string();
        let mut summary = Summary {
            generation,
            last_seq: self.lifecycle.last_seq().max(before.last_seq),
            ceiling: self.ceiling.max(before.ceiling),
            next_ordinal: before.next_ordinal + self.made,
            ..before.clone()
        };
        let mut w = TableWriter::new(
            out,
            old.map_or(0, |t| t.table.len()) + self.touched.len() as u64 * 5 + 64,
        );
        let mut hints = Hints::default();
        // The accounts marked that are accounts still, in order of DID.
        let mut standing: Vec<&str> = Vec::new();
        let mut rows = old
            .into_iter()
            .flat_map(|t| t.section(ROW, &[ROW]))
            .peekable();
        let mut touched = self.touched.iter().peekable();
        loop {
            let (row, t) = match (rows.peek(), touched.peek()) {
                (None, None) => break,
                (Some(Err(_)), _) | (Some(Ok(_)), None) => (rows.next(), None),
                (None, Some(_)) => (None, touched.next()),
                (Some(Ok((k, _))), Some((did, _))) => match k[1..].cmp(did.as_bytes()) {
                    std::cmp::Ordering::Less => (rows.next(), None),
                    std::cmp::Ordering::Equal => (rows.next(), touched.next()),
                    std::cmp::Ordering::Greater => (None, touched.next()),
                },
            };
            let row = row.transpose()?;
            let Some((did, t)) = t else {
                // A row no log touched: as it is.
                let (k, v) = row.expect("a row, where no account is touched");
                if let Some(did) = std::str::from_utf8(&k[1..])
                    .ok()
                    .and_then(|did| self.marked.get(did))
                {
                    standing.push(did);
                }
                w.add(&k, &v).map_err(werr)?;
                continue;
            };
            let row = row.as_ref().map(|(_, v)| v.as_slice());
            let Some((ordinal, one)) = settle(did, row, t, before.next_ordinal, &mut summary)?
            else {
                continue;
            };
            w.add(
                &row_key(did),
                &row_value(ordinal, &one.entries(did, self.before)?),
            )
            .map_err(werr)?;
            hints.note(did, ordinal, &one)?;
            if self.marked.contains(did) {
                standing.push(did);
            }
        }
        drop(rows);
        let Hints {
            handles,
            emails,
            order,
            tokens,
        } = hints;
        merge(&mut w, old, HANDLE, &self.touched, handles)?;
        merge(&mut w, old, EMAIL, &self.touched, emails)?;
        merge(&mut w, old, ORDER, &self.touched, order)?;
        let mut rest: Vec<Json> = self.invites.entries();
        rest.extend(self.held);
        rest.extend(self.lifecycle.entries(keep));
        rest.extend(latest_devices(latest_refreshes(latest_passkey_uses(
            self.oauth,
        ))));
        rest.extend(self.spent);
        rest.extend(
            standing
                .iter()
                .map(|did| crate::cache::dir_entry(did, None, true)),
        );
        rest.extend(self.doomed.entries());
        for (i, entries) in rest.chunks(ROW_ENTRIES).enumerate() {
            let row = serde_json::to_vec(entries).expect("entries serialize");
            w.add(&numbered(REST, i as u64), &row).map_err(werr)?;
        }
        w.add(SUMMARY, &summary.encode()).map_err(werr)?;
        merge(&mut w, old, TOKEN, &self.touched, tokens)?;
        let (out, _) = w.finish().map_err(werr)?;
        out.flush().map_err(werr)
    }
}

/// An account the logs touched, as its row before, `row`, and their
/// entries leave it, with its ordinal: the one its row has, or for one the
/// logs made, its place among those after `base`. None for one deleted.
/// It is counted in `summary`, in place of what its row before counted.
fn settle(
    did: &str,
    row: Option<&[u8]>,
    t: &Touched,
    base: u64,
    summary: &mut Summary,
) -> Result<Option<(u64, One)>, String> {
    let at = |why: String| format!("{did}: {why}");
    let mut one = One::default();
    let mut ordinal = None;
    if let Some(v) = row {
        let (n, entries) = parse_row(v).map_err(at)?;
        for e in entries {
            one.apply(e).map_err(at)?;
        }
        summary.count(&one, false);
        if t.void {
            one = One::default();
        } else {
            ordinal = Some(n);
        }
    }
    if !t.text.is_empty() {
        let entries: Vec<Json> = serde_json::from_str(&format!("[{}]", t.text))
            .map_err(|e| at(format!("an entry kept as text: {e}")))?;
        for e in entries {
            one.apply(e).map_err(at)?;
        }
    }
    if t.deleted {
        return Ok(None);
    }
    if let Some(n) = t.made {
        ordinal = Some(base + n);
    }
    let (true, Some(ordinal)) = (one.is_made(), ordinal) else {
        return Err(at("entries of an account no account entry made".into()));
    };
    summary.count(&one, true);
    Ok(Some((ordinal, one)))
}

/// The hints and ordinals of the accounts a fold wrote rows of, each as
/// its key and value.
#[derive(Default)]
struct Hints {
    handles: Vec<(Vec<u8>, Vec<u8>)>,
    emails: Vec<(Vec<u8>, Vec<u8>)>,
    order: Vec<(Vec<u8>, Vec<u8>)>,
    tokens: Vec<(Vec<u8>, Vec<u8>)>,
}

impl Hints {
    fn note(&mut self, did: &str, ordinal: u64, one: &One) -> Result<(), String> {
        let mail = one.mail.as_ref();
        for (section, name, into) in [
            (HANDLE, one.handle(), &mut self.handles),
            (
                EMAIL,
                mail.and_then(|m| m.email.as_deref()),
                &mut self.emails,
            ),
            (TOKEN, mail.and_then(Mail::reset_token), &mut self.tokens),
        ] {
            if let Some(name) = name {
                into.push((hint_key(section, name, did)?, Vec::new()));
            }
        }
        self.order
            .push((numbered(ORDER, ordinal), did.as_bytes().to_vec()));
        Ok(())
    }
}

/// Write a section of hints or ordinals: those of `old`, the table before,
/// but of the accounts `touched`, merged in order of key with `new`, theirs
/// as they are now.
fn merge<W: Write>(
    w: &mut TableWriter<W>,
    old: Option<&ServiceTable>,
    section: u8,
    touched: &BTreeMap<String, Touched>,
    mut new: Vec<(Vec<u8>, Vec<u8>)>,
) -> Result<(), String> {
    new.sort();
    new.dedup();
    let mut new = new.into_iter().peekable();
    let mut kept = old
        .into_iter()
        .flat_map(|t| t.section(section, &[section]))
        .filter(|r| {
            r.as_ref().map_or(true, |(k, v)| {
                !named_did(section, k, v).is_some_and(|did| touched.contains_key(did))
            })
        })
        .peekable();
    loop {
        let take_new = match (kept.peek(), new.peek()) {
            (None, None) => break,
            (Some(_), None) => false,
            (None, Some(_)) => true,
            (Some(Err(_)), Some(_)) => false,
            (Some(Ok((k, _))), Some((n, _))) => n < k,
        };
        let (k, v) = if take_new {
            new.next().expect("peeked")
        } else {
            kept.next().expect("peeked")?
        };
        w.add(&k, &v).map_err(|e| e.to_string())?;
    }
    Ok(())
}

/// What `fold` answers: the entries kept, in the frames a checkpoint has
/// them in, the greatest seq of the events they hold, and of the seqs
/// reserved, if any were.
#[cfg(test)]
type Folded = (Vec<Vec<Json>>, u64, Option<u64>);

/// What `frames` hold now, as a table folded from them has it: each
/// account's row, in the order the accounts were made, then the entries
/// that are not one account's.
#[cfg(test)]
fn fold(
    frames: Vec<Vec<Json>>,
    before: u64,
    now: u64,
    keep: impl Fn(u64, &[u8]) -> bool,
) -> Result<Folded, String> {
    let mut folder = Folder::new(before, now);
    for e in frames.into_iter().flatten() {
        folder.apply(e)?;
    }
    let mut out = Vec::new();
    folder.finish(keep, None, &Summary::default(), 1, &mut out)?;
    static N: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
    let path = std::env::temp_dir().join(format!(
        "pds-test-{}-fold-{}",
        std::process::id(),
        N.fetch_add(1, std::sync::atomic::Ordering::Relaxed)
    ));
    std::fs::write(&path, out).map_err(|e| e.to_string())?;
    let table = ServiceTable::open(&path, Arc::new(BlockCache::new(FOLD_CACHE)))?
        .ok_or("a table just written")?;
    let _ = std::fs::remove_file(&path);
    let mut entries = Vec::new();
    for r in table.order(0) {
        let (ordinal, did) = r?;
        let (n, row) = table.row(&did)?.ok_or("an ordinal of no row")?;
        assert_eq!(n, ordinal);
        entries.extend(row);
    }
    table.rest(|row| {
        entries.extend(row);
        Ok(())
    })?;
    Ok((
        entries.chunks(ROW_ENTRIES).map(<[Json]>::to_vec).collect(),
        table.summary.last_seq,
        table.summary.ceiling,
    ))
}

/// OAuth's entries, in order, but each session's refreshes before its last:
/// a refresh sets all a session's tokens and its last token answer, so only
/// the last counts in a replay.
fn latest_refreshes(oauth: Vec<Json>) -> Vec<Json> {
    let is_refresh = |e: &Json| e["t"] == "oauthRefresh";
    let mut last: HashMap<String, usize> = HashMap::new();
    for (i, e) in oauth.iter().enumerate() {
        if is_refresh(e)
            && let Some(sid) = e["sid"].as_str()
        {
            last.insert(sid.to_string(), i);
        }
    }
    oauth
        .into_iter()
        .enumerate()
        .filter(|(i, e)| {
            !is_refresh(e) || e["sid"].as_str().is_none_or(|sid| last.get(sid) == Some(i))
        })
        .map(|(_, e)| e)
        .collect()
}

/// OAuth's entries, in order, but each passkey's sign-ins before its last:
/// a sign-in sets all that one keeps of a passkey's (its count, BS and last
/// use), so only the last counts in a replay, and however often a passkey
/// signs in, what is kept of it stays the same.
fn latest_passkey_uses(oauth: Vec<Json>) -> Vec<Json> {
    let is_use = |e: &Json| e["t"] == "oauthPasskeyUse";
    let mut last: HashMap<String, usize> = HashMap::new();
    for (i, e) in oauth.iter().enumerate() {
        if is_use(e)
            && let Some(id) = e["id"].as_str()
        {
            last.insert(id.to_string(), i);
        }
    }
    oauth
        .into_iter()
        .enumerate()
        .filter(|(i, e)| !is_use(e) || e["id"].as_str().is_none_or(|id| last.get(id) == Some(i)))
        .map(|(_, e)| e)
        .collect()
}

/// OAuth's entries, in order, but of each device only what its entries
/// leave: each account's last sign-in on it, unless a sign-out of that
/// account or the device's end came after, and its last cookies' key, unless
/// its end came after. What is left out sets nothing a replay keeps, and the
/// sign-outs and ends, which then end nothing, go too; so however often a
/// device signs in, what is kept of it stays the same.
fn latest_devices(oauth: Vec<Json>) -> Vec<Json> {
    let text = |e: &Json, k: &str| e[k].as_str().unwrap_or_default().to_string();
    // Each device's accounts, each with the place of its last sign-in, and its last key's place.
    let mut signed: HashMap<String, HashMap<String, usize>> = HashMap::new();
    let mut keys: HashMap<String, usize> = HashMap::new();
    for (i, e) in oauth.iter().enumerate() {
        match e["t"].as_str() {
            Some("oauthSignIn") => {
                signed
                    .entry(text(e, "device"))
                    .or_default()
                    .insert(text(e, "did"), i);
            }
            Some("oauthSignOut") => {
                if let Some(s) = signed.get_mut(&text(e, "device")) {
                    s.remove(&text(e, "did"));
                }
            }
            Some("oauthDeviceKey") => {
                keys.insert(text(e, "device"), i);
            }
            Some("oauthDeviceEnd") => {
                let device = text(e, "device");
                signed.remove(&device);
                keys.remove(&device);
            }
            _ => {}
        }
    }
    let kept: std::collections::HashSet<usize> = signed
        .into_values()
        .flat_map(HashMap::into_values)
        .chain(keys.into_values())
        .collect();
    let of_devices = |e: &Json| {
        matches!(
            e["t"].as_str(),
            Some("oauthSignIn" | "oauthSignOut" | "oauthDeviceKey" | "oauthDeviceEnd")
        )
    };
    oauth
        .into_iter()
        .enumerate()
        .filter(|(i, e)| !of_devices(e) || kept.contains(i))
        .map(|(_, e)| e)
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Service;
    use crate::testing::*;
    use serde_json::json;

    /// The bytes of the service log's files.
    fn service_files(dir: &std::path::Path) -> u64 {
        std::fs::read_dir(dir)
            .unwrap()
            .flatten()
            .filter(|e| e.file_name().to_string_lossy().starts_with("accounts."))
            .map(|e| e.metadata().unwrap().len())
            .sum()
    }

    /// Fold the table at `old`, if given, and a sealed log of `frames`,
    /// into the table of `generation`, at a `now` of 50: where it is.
    fn table_of(dir: &Path, old: Option<&Path>, frames: &[Vec<Json>], generation: u64) -> PathBuf {
        std::fs::create_dir_all(dir).unwrap();
        let log = dir.join(format!("accounts.{generation}.log"));
        let mut bytes: Vec<u8> = frames.iter().flat_map(|f| pds_store::frame(f)).collect();
        bytes.extend(pds_store::frame(&[json!({ "t": "seal" })]));
        std::fs::write(&log, bytes).unwrap();
        let path = dir.join(format!("table.{generation}"));
        let mut out = File::create(&path).unwrap();
        fold_files(old, &[log], generation, 50, |_, _| true, &mut out).unwrap();
        path
    }

    fn open_table(path: &Path) -> ServiceTable {
        ServiceTable::open(path, Arc::new(BlockCache::new(FOLD_CACHE)))
            .unwrap()
            .unwrap()
    }

    /// Every key of a section, as text, a NUL shown as a space.
    fn keys(t: &ServiceTable, section: u8) -> Vec<String> {
        t.section(section, &[section])
            .map(|r| String::from_utf8_lossy(&r.unwrap().0[1..]).replace('\0', " "))
            .collect()
    }

    fn made(did: &str) -> Json {
        json!({ "t": "account", "did": did, "handle": format!("{did}.test"), "email": format!("{did}@mail.com"), "password": "hash" })
    }

    /// A fold of a table and the log after it: a row no log touched is
    /// copied as it is, one a log touched is as its entries and the log's
    /// leave it, a deleted account's is gone, and the hints, the ordinals
    /// and the summary are those of the accounts there are now.
    #[test]
    fn fold_merges_the_table_before_with_the_logs() {
        let dir = scratch("fold-merge");
        let token = |did: &str, token: &str| json!({ "t": "mailToken", "did": did, "purpose": "reset_password", "token": token, "made": 1 });
        let first = table_of(
            &dir,
            None,
            &[
                vec![made("a")],
                vec![made("b"), made("c")],
                vec![made("d"), made("e")],
                vec![token("a", "AAAAA-AAAAA"), token("d", "DDDDD-DDDDD")],
                vec![json!({ "t": "deactivated", "did": "e", "applied": true })],
                vec![json!({ "t": "seqs", "upto": 40 })],
            ],
            1,
        );
        let t = open_table(&first);
        assert_eq!(
            t.summary,
            Summary {
                generation: 1,
                last_seq: 0,
                ceiling: Some(40),
                next_ordinal: 5,
                accounts: 5,
                deactivated: 1,
                takendown: 0,
            }
        );
        assert_eq!(keys(&t, ROW), ["a", "b", "c", "d", "e"]);
        assert_eq!(
            keys(&t, HANDLE),
            ["a.test a", "b.test b", "c.test c", "d.test d", "e.test e"]
        );
        assert_eq!(keys(&t, TOKEN), ["AAAAA-AAAAA a", "DDDDD-DDDDD d"]);
        assert_eq!(t.hints(EMAIL, "c@mail.com").unwrap(), ["c"]);
        assert_eq!(t.hints(EMAIL, "c@mail.co").unwrap(), Vec::<String>::new());
        let order = |t: &ServiceTable, from: u64| -> Vec<(u64, String)> {
            t.order(from).map(Result::unwrap).collect()
        };
        assert_eq!(order(&t, 3), [(3, "d".to_string()), (4, "e".to_string())]);
        // The log after it: an email and a handle changed, a token used,
        // an account deleted, one made, one made and deleted, a state
        // changed; `a` is not touched.
        let deleted = |did: &str, seq: u64| json!({ "t": "deleted", "did": did, "gaps": [], "seq": seq, "frame": "00" });
        let second = table_of(
            &dir,
            Some(&first),
            &[
                vec![json!({ "t": "updateEmail", "did": "b", "email": "new@mail.com" })],
                vec![crate::cache::dir_entry("e", Some("eve.test"), false)],
                vec![json!({ "t": "useToken", "did": "d", "purpose": "reset_password" })],
                vec![deleted("c", 7)],
                vec![made("f"), made("g")],
                vec![deleted("g", 9)],
                vec![json!({ "t": "takedown", "did": "b", "ref": "x" })],
                vec![json!({ "t": "deactivated", "did": "e", "applied": false })],
                // Of an account deleted: nothing is kept of it.
                vec![json!({ "t": "confirmEmail", "did": "c" })],
            ],
            2,
        );
        let u = open_table(&second);
        assert_eq!(
            u.summary,
            Summary {
                generation: 2,
                last_seq: 9,
                ceiling: Some(40),
                next_ordinal: 7,
                accounts: 5,
                deactivated: 0,
                takendown: 1,
            }
        );
        assert_eq!(keys(&u, ROW), ["a", "b", "d", "e", "f"]);
        assert_eq!(
            keys(&u, HANDLE),
            ["a.test a", "b.test b", "d.test d", "eve.test e", "f.test f"]
        );
        assert_eq!(
            keys(&u, EMAIL),
            [
                "a@mail.com a",
                "d@mail.com d",
                "e@mail.com e",
                "f@mail.com f",
                "new@mail.com b"
            ]
        );
        assert_eq!(keys(&u, TOKEN), ["AAAAA-AAAAA a"]);
        let ordered: Vec<(u64, String)> = [(0, "a"), (1, "b"), (3, "d"), (4, "e"), (5, "f")]
            .map(|(n, did)| (n, did.to_string()))
            .into();
        assert_eq!(order(&u, 0), ordered);
        // The row no log touched is the same bytes; the others say what is so now.
        assert_eq!(u.get(&row_key("a")).unwrap(), t.get(&row_key("a")).unwrap());
        let (ordinal, row) = u.row("e").unwrap().unwrap();
        assert_eq!((ordinal, &row[0]["handle"]), (4, &json!("eve.test")));
        assert_eq!(row.len(), 1);
        let (_, row) = u.row("b").unwrap().unwrap();
        assert_eq!(row[0]["email"], json!("new@mail.com"));
        assert_eq!(row[1], json!({ "t": "takedown", "did": "b", "ref": "x" }));
        assert!(u.row("c").unwrap().is_none() && !u.has("g").unwrap());
        // The deletions, whose events are kept, are among what is not one account's.
        let mut rest = Vec::new();
        u.rest(|row| {
            rest.extend(row);
            Ok(())
        })
        .unwrap();
        let kinds: Vec<&str> = rest.iter().map(|e| e["t"].as_str().unwrap()).collect();
        assert_eq!(kinds, ["deleted", "deleted"]);
        // Folded again with nothing new, it holds the same.
        let third = open_table(&table_of(&dir, Some(&second), &[], 3));
        for section in [ROW, HANDLE, EMAIL, ORDER, TOKEN] {
            assert_eq!(keys(&third, section), keys(&u, section));
        }
        assert_eq!(
            third.summary,
            Summary {
                generation: 3,
                ..u.summary.clone()
            }
        );
        // A second account entry of a DID, and an entry of no account, fail the fold.
        for bad in [made("a"), json!({ "t": "confirmEmail", "did": "nobody" })] {
            let log = dir.join("bad.log");
            let mut bytes = pds_store::frame(std::slice::from_ref(&bad));
            bytes.extend(pds_store::frame(&[json!({ "t": "seal" })]));
            std::fs::write(&log, bytes).unwrap();
            let folded = fold_files(Some(&second), &[log], 3, 50, |_, _| true, &mut Vec::new());
            assert!(folded.is_err(), "{bad}");
        }
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// A table's summary is read back as written, and one of a version
    /// this server does not know is refused.
    #[test]
    fn a_summary_round_trips() {
        let s = Summary {
            generation: 3,
            last_seq: 9,
            ceiling: None,
            next_ordinal: 12,
            accounts: 10,
            deactivated: 2,
            takendown: 1,
        };
        assert_eq!(Summary::decode(&s.encode()).unwrap(), s);
        let with = Summary {
            ceiling: Some(64),
            ..s
        };
        assert_eq!(Summary::decode(&with.encode()).unwrap(), with);
        let mut other: Json = serde_json::from_slice(&with.encode()).unwrap();
        other["version"] = json!(VERSION + 1);
        assert!(Summary::decode(other.to_string().as_bytes()).is_err());
    }

    /// Refreshing a session again and again leaves the service log's files
    /// no larger than twice its checkpoint and the floor, and a frame; a
    /// restart finds every account, session, app password, invite code,
    /// single-use value and credential revocation as before.
    #[tokio::test]
    async fn refreshing_leaves_the_log_bounded() {
        let plc = plc().await;
        let dir = scratch("compact");
        const FLOOR: u64 = 16 * 1024;
        let s: crate::Shared = std::sync::Arc::new(
            Service::open(
                &dir,
                crate::Config {
                    log_floor: FLOOR,
                    ..config(&plc)
                },
            )
            .unwrap(),
        );
        let (did, token) = create(&s, "alice").await;
        create(&s, "bob").await;
        let admin = format!(
            "Basic {}",
            base64::Engine::encode(
                &base64::engine::general_purpose::STANDARD,
                format!("admin:{ADMIN_PASSWORD}")
            )
        );
        let code = call_raw(
            &s,
            "com.atproto.server.createInviteCode",
            crate::sessions::Bearer::of(Some(&admin)),
            &[],
            r#"{"useCount":2}"#,
        )
        .await
        .unwrap();
        let app = call(
            &s,
            "com.atproto.server.createAppPassword",
            Some(&token),
            json!({ "name": "phone" }),
        )
        .await
        .unwrap();
        let login = json!({ "identifier": "alice.test", "password": app["password"] });
        let mut refresh = call(&s, "com.atproto.server.createSession", None, login)
            .await
            .unwrap()["refreshJwt"]
            .as_str()
            .unwrap()
            .to_string();
        let now = s.sessions.now();
        assert!(crate::single_use::SingleUse::check_and_record(
            &*s,
            "nonce",
            now + 3600
        ));
        s.space_credentials
            .revoke(&s.log, "at://did:plc:a/space/a.b.c/x", &["j"], now)
            .unwrap();
        let mut largest = 0;
        for _ in 0..1500 {
            let got = call(
                &s,
                "com.atproto.server.refreshSession",
                Some(&refresh),
                Json::Null,
            )
            .await
            .unwrap();
            refresh = got["refreshJwt"].as_str().unwrap().to_string();
            // Between compactions.
            s.log.wait_compacted();
            largest = largest.max(service_files(&dir).saturating_sub(2 * s.log.checkpoint_bytes()));
        }
        assert!(s.log.checkpoint_generation() > 0, "never compacted");
        assert!(
            largest <= FLOOR + 4096,
            "{largest} bytes past twice the checkpoint"
        );
        // The account keeps at most its sessions' limit, so the checkpoint stays small.
        assert!(s.sessions.count(&did) <= crate::sessions::MAX_SESSIONS);
        assert!(
            s.log.checkpoint_bytes() < 200 * 1024,
            "{}",
            s.log.checkpoint_bytes()
        );
        let held = |s: &Service| {
            (
                s.single_use.snapshot(now),
                s.space_credentials.snapshot(now),
            )
        };
        let before = (s.sessions.snapshot(), s.invites.snapshot(), held(&s));
        drop(s);
        let s = open(&dir, &plc);
        assert_eq!(
            (s.sessions.snapshot(), s.invites.snapshot(), held(&s)),
            before
        );
        assert!(!crate::single_use::SingleUse::check_and_record(
            &*s,
            "nonce",
            now + 3600
        ));
        // The latest token works, and the code can still be used.
        call(
            &s,
            "com.atproto.server.refreshSession",
            Some(&refresh),
            Json::Null,
        )
        .await
        .unwrap();
        let body = json!({ "handle": "carol.test", "email": "carol@mail.com", "password": "pw", "inviteCode": code["code"] });
        call(&s, "com.atproto.server.createAccount", None, body)
            .await
            .unwrap();
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// Sessions long expired are left out of a compacted log; those within
    /// the margin, and every other, are kept.
    #[test]
    fn fold_leaves_out_long_expired_sessions() {
        let did = "did:plc:a";
        let session = |id: &str, exp: u64| json!({ "t": "session", "did": did, "id": id, "app": null, "scope": "com.atproto.access", "exp": exp });
        let frames = vec![
            vec![json!({ "t": "account", "did": did })],
            vec![
                session("old", 10),
                session("recent", 100),
                session("live", 1000),
            ],
            vec![
                json!({ "t": "refresh", "did": did, "id": "live", "next": "after", "exp": 1000, "nextExp": 2000 }),
            ],
        ];
        let folded = fold(frames, 50, 50, |_, _| true).unwrap().0;
        let ids: Vec<&str> = folded
            .iter()
            .flatten()
            .filter(|e| e["t"] == "session")
            .map(|e| e["id"].as_str().unwrap())
            .collect();
        // In the order they were made, so that a replay orders them alike.
        assert_eq!(ids, ["recent", "live", "after"]);
        let live = folded.iter().flatten().find(|e| e["id"] == "live").unwrap();
        assert_eq!(live["next"], json!("after"));
    }

    /// OAuth's entries are kept in order but for each session's superseded
    /// refreshes, and single-use values long past their time are left out.
    #[test]
    fn fold_keeps_oauth_and_held_values() {
        let did = "did:plc:a";
        let refresh = |sid: &str, n: u64| json!({ "t": "oauthRefresh", "sid": sid, "access": format!("a{n}"), "accessExp": n, "refresh": format!("r{n}"), "at": n });
        let frames = vec![
            vec![json!({ "t": "account", "did": did })],
            vec![
                json!({ "t": "oauthSession", "sid": "s1" }),
                json!({ "t": "spent", "ns": "dpop", "v": "x", "until": 40 }),
            ],
            vec![
                refresh("s1", 1),
                json!({ "t": "oauthSession", "sid": "s2" }),
                refresh("s2", 2),
                refresh("s1", 3),
            ],
            vec![
                refresh("s1", 4),
                json!({ "t": "spent", "ns": "dpop", "v": "y", "until": 60 }),
            ],
        ];
        let folded: Vec<Json> = fold(frames, 50, 50, |_, _| true)
            .unwrap()
            .0
            .into_iter()
            .flatten()
            .collect();
        let kinds: Vec<String> = folded
            .iter()
            .map(|e| {
                format!(
                    "{} {}",
                    e["t"].as_str().unwrap(),
                    e["at"].as_u64().or(e["until"].as_u64()).unwrap_or(0)
                )
            })
            .collect();
        assert_eq!(
            kinds,
            [
                "account 0",
                "oauthSession 0",
                "oauthSession 0",
                "oauthRefresh 2",
                "oauthRefresh 4",
                "spent 60"
            ]
        );
    }

    /// Of each device, only its accounts' last sign-ins still standing and
    /// its last key not ended are kept, in order.
    #[test]
    fn fold_keeps_each_devices_last() {
        let (a, b) = ("did:plc:a", "did:plc:b");
        let sign_in = |device: &str, did: &str, at: u64| json!({ "t": "oauthSignIn", "device": device, "did": did, "at": at });
        let key = |device: &str, at: u64| json!({ "t": "oauthDeviceKey", "device": device, "key": format!("k{at}"), "at": at });
        let devices = vec![
            vec![
                sign_in("d1", a, 1),
                key("d1", 1),
                sign_in("d1", b, 2),
                key("d1", 2),
                sign_in("d1", a, 3),
                key("d1", 3),
            ],
            vec![
                sign_in("d2", a, 4),
                key("d2", 4),
                json!({ "t": "oauthSignOut", "device": "d2", "did": a }),
            ],
            vec![
                sign_in("d3", b, 5),
                key("d3", 5),
                json!({ "t": "oauthDeviceEnd", "device": "d3" }),
                key("d3", 6),
            ],
            vec![
                sign_in("d4", a, 7),
                json!({ "t": "oauthDeviceEnd", "device": "d4" }),
            ],
        ];
        let mut frames = vec![vec![
            json!({ "t": "account", "did": a }),
            json!({ "t": "account", "did": b }),
        ]];
        frames.extend(devices.clone());
        let folded: Vec<Json> = fold(frames, 0, 0, |_, _| true)
            .unwrap()
            .0
            .into_iter()
            .flatten()
            .skip(2)
            .collect();
        let kinds: Vec<String> = folded
            .iter()
            .map(|e| format!("{} {}", e["t"].as_str().unwrap(), e["at"]))
            .collect();
        assert_eq!(
            kinds,
            [
                "oauthSignIn 2",
                "oauthSignIn 3",
                "oauthDeviceKey 3",
                "oauthDeviceKey 4",
                "oauthDeviceKey 6"
            ]
        );
        // Replayed, they make what all of them make.
        let replayed = |entries: &[Json]| {
            let o = crate::oauth::OAuth::open(&scratch("fold-devices"), "https://pds.test", None)
                .unwrap();
            for e in entries {
                o.replay(e, &|_| true).unwrap();
            }
            o.snapshot()
        };
        assert_eq!(replayed(&folded), replayed(&devices.concat()));
    }

    /// Single-use values and revocations are kept until their `until` passes.
    #[test]
    fn fold_keeps_held_values_until_they_pass() {
        let frames = vec![vec![
            json!({ "t": crate::single_use::ENTRY, "v": "a", "until": 40 }),
            json!({ "t": crate::single_use::ENTRY, "v": "b", "until": 60 }),
            json!({ "t": crate::space_credentials::ENTRY, "space": "s", "credentials": ["old"], "until": 50 }),
            json!({ "t": crate::space_credentials::ENTRY, "space": "s", "credentials": ["new"], "until": 51 }),
        ]];
        let folded: Vec<Json> = fold(frames, 0, 50, |_, _| true)
            .unwrap()
            .0
            .into_iter()
            .flatten()
            .collect();
        assert_eq!(folded.len(), 2);
        assert_eq!(folded[0]["v"], json!("b"));
        assert_eq!(folded[1]["credentials"], json!(["new"]));
    }

    /// A deleted account's OAuth sessions, sign-ins and approved requests are
    /// forgotten when it is deleted, after a restart, and in a compacted log,
    /// which replays to the same; the other account's stay, and work.
    #[tokio::test]
    async fn a_deleted_accounts_oauth_is_forgotten() {
        use crate::email::testing::{last_token, open_with_sink};
        use crate::oauth::tests::{App, Browser, approved, kept, serve, text};
        let plc = plc().await;
        let dir = scratch("compact-deleted-oauth");
        let sink = scratch("compact-deleted-oauth-mail");
        let srv = serve(open_with_sink(&dir, &plc, &sink)).await;
        let (alice, _) = create(&srv.svc, "alice").await;
        let (bob, bob_token) = create(&srv.svc, "bob").await;
        let mut app = App::new(&srv, "atproto");
        let mut browser = Browser::new(&srv);
        let (pushed, code) = approved(&mut app, &mut browser, "alice").await;
        let alice_tokens = app.exchange(&code, &pushed).await.json();
        let (pushed, code) = approved(&mut app, &mut browser, "bob").await;
        let bob_tokens = app.exchange(&code, &pushed).await.json();
        app.refresh(&text(&bob_tokens, "refresh_token")).await;
        // A request approved for bob, its code not exchanged.
        let (pushed, code) = approved(&mut app, &mut browser, "bob").await;
        call(
            &srv.svc,
            "com.atproto.server.requestAccountDelete",
            Some(&bob_token),
            Json::Null,
        )
        .await
        .unwrap();
        call(
            &srv.svc,
            "com.atproto.server.deleteAccount",
            None,
            json!({ "did": bob, "password": "bob-pw", "token": last_token(&sink) }),
        )
        .await
        .unwrap();
        let after = kept(&srv.svc);
        let state = format!("{:?}", after.0);
        assert!(!state.contains(&bob) && state.contains(&alice), "{state}");
        assert_eq!(app.exchange(&code, &pushed).await.status, 400);
        let restarted = open(&crate::log::copied(&dir), &plc);
        assert_eq!(restarted.oauth.snapshot(), after.0);
        drop(restarted);
        srv.svc.log.compact().unwrap();
        assert_eq!(
            open(&crate::log::copied(&dir), &plc).oauth.snapshot(),
            after.0
        );
        // Alice's session works on.
        assert_eq!(
            app.refresh(&text(&alice_tokens, "refresh_token"))
                .await
                .status,
            200
        );
        let _ = std::fs::remove_dir_all(&dir);
        let _ = std::fs::remove_dir_all(&sink);
    }

    /// A takedown, or its lifting, and a deactivation with an OAuth token end
    /// every OAuth session of the account, after a restart too; a deactivation
    /// with a password session ends none. A deactivation with an OAuth token
    /// deletes the account's app passwords too, but not the sessions made
    /// with them, after a restart and a compaction too (`spec/LIFECYCLE.md`).
    #[tokio::test]
    async fn account_states_end_oauth_sessions() {
        use crate::oauth::tests::{App, Browser, approved, serve, text};
        let plc = plc().await;
        let dir = scratch("state-ends-oauth");
        let srv = serve(open(&dir, &plc)).await;
        let (did, token) = create(&srv.svc, "alice").await;
        let mut app = App::new(&srv, "atproto account:status?action=manage");
        let mut browser = Browser::new(&srv);
        async fn session(app: &mut App<'_>, browser: &mut Browser<'_>) -> Json {
            let (pushed, code) = approved(app, browser, "alice").await;
            app.exchange(&code, &pushed).await.json()
        }
        let admin = format!(
            "Basic {}",
            base64::Engine::encode(
                &base64::engine::general_purpose::STANDARD,
                format!("admin:{ADMIN_PASSWORD}")
            )
        );
        let takedown = |applied: bool| {
            json!({ "subject": { "$type": "com.atproto.admin.defs#repoRef", "did": did }, "takedown": { "applied": applied } }).to_string()
        };
        let sessions = |s: &Service| {
            format!("{:?}", s.oauth.snapshot())
                .matches("Session {")
                .count()
        };
        let login = |password: &str| json!({ "identifier": "alice.test", "password": password });
        let pw = call(
            &srv.svc,
            "com.atproto.server.createAppPassword",
            Some(&token),
            json!({ "name": "phone" }),
        )
        .await
        .unwrap();
        let pw = pw["password"].as_str().unwrap().to_string();
        // A password session's deactivation ends none, and keeps its app passwords.
        let kept = session(&mut app, &mut browser).await;
        call(
            &srv.svc,
            "com.atproto.server.deactivateAccount",
            Some(&token),
            json!({}),
        )
        .await
        .unwrap();
        assert_eq!(
            app.get_session(&text(&kept, "access_token")).await.status,
            200
        );
        let app_session = call(
            &srv.svc,
            "com.atproto.server.createSession",
            None,
            login(&pw),
        )
        .await
        .unwrap();
        call(
            &srv.svc,
            "com.atproto.server.activateAccount",
            Some(&token),
            Json::Null,
        )
        .await
        .unwrap();
        // An OAuth token's ends both.
        let other = session(&mut app, &mut browser).await;
        assert_eq!(sessions(&srv.svc), 2);
        assert_eq!(
            app.post(
                "com.atproto.server.deactivateAccount",
                &text(&other, "access_token"),
                json!({})
            )
            .await
            .status,
            200
        );
        assert_eq!(sessions(&srv.svc), 0);
        assert_eq!(
            app.get_session(&text(&kept, "access_token")).await.error(),
            "invalid_token"
        );
        assert_eq!(
            app.refresh(&text(&other, "refresh_token")).await.error(),
            "invalid_grant"
        );
        assert_eq!(sessions(&open(&crate::log::copied(&dir), &plc)), 0);
        // Its app password is gone; the session made with it refreshes.
        assert_eq!(
            call(
                &srv.svc,
                "com.atproto.server.createSession",
                None,
                login(&pw)
            )
            .await
            .unwrap_err(),
            "AuthenticationRequired"
        );
        assert_eq!(
            call(
                &srv.svc,
                "com.atproto.server.listAppPasswords",
                Some(&token),
                Json::Null
            )
            .await
            .unwrap(),
            json!({ "passwords": [] })
        );
        call(
            &srv.svc,
            "com.atproto.server.refreshSession",
            Some(app_session["refreshJwt"].as_str().unwrap()),
            Json::Null,
        )
        .await
        .unwrap();
        let keeps = srv.svc.sessions.snapshot();
        let restarted = || open(&crate::log::copied(&dir), &plc).sessions.snapshot();
        assert_eq!(restarted(), keeps);
        srv.svc.log.compact().unwrap();
        assert_eq!(restarted(), keeps);
        call(
            &srv.svc,
            "com.atproto.server.activateAccount",
            Some(&token),
            Json::Null,
        )
        .await
        .unwrap();
        // A lifting of a takedown that was not applied ends them too.
        for applied in [false, true] {
            session(&mut app, &mut browser).await;
            assert_eq!(sessions(&srv.svc), 1);
            call_raw(
                &srv.svc,
                "com.atproto.admin.updateSubjectStatus",
                crate::sessions::Bearer::of(Some(&admin)),
                &[],
                &takedown(applied),
            )
            .await
            .unwrap();
            assert_eq!(sessions(&srv.svc), 0);
            assert_eq!(sessions(&open(&crate::log::copied(&dir), &plc)), 0);
        }
        let _ = std::fs::remove_dir_all(&dir);
    }
}