~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
3346 lines · 125.4 KB Raw History
//! The firehose: `com.atproto.sync.subscribeRepos` events, the one sequence
//! they are numbered in across all accounts, and the WebSocket that serves
//! them, as `spec/SYNC.md` says.

use crate::{Account, Shared, limits};
use axum::body::Bytes;
use axum::extract::ws::rejection::WebSocketUpgradeRejection;
use axum::extract::ws::{CloseFrame, Message, WebSocket, WebSocketUpgrade, close_code};
use axum::extract::{Extension, Query, State};
use axum::http::{HeaderMap, StatusCode};
use axum::response::{IntoResponse, Response};
use pds_repo::data::*;
use pds_repo::{Change, car_file};
use pds_store::Wal;
use std::collections::{HashMap, HashSet, VecDeque};
#[cfg(test)]
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, OnceLock, PoisonError, Weak};
use std::time::{Duration, Instant, SystemTime, UNIX_EPOCH};

pub(crate) mod index;

/// The firehose's events, numbered across all accounts. A write takes its
/// events' numbers under its account's lock, so each account's events are in
/// the order of its commits; writes to different accounts take them side by
/// side and reach the disk in any order. Subscribers are sent an event only
/// once it and every event before it are on disk, or will never be.
///
/// A number is given out once, and kept: an event whose write failed, or
/// that never reached the disk before a restart, leaves a hole in the
/// numbers, as a deleted account's events do (`spec/LIFECYCLE.md`), and no
/// event is numbered again. Numbers are reserved in the service log
/// `RESERVE` at a time (`SEQS`), on disk before one is given out: a start
/// goes on after the last reserved, reading no account's log for it. A
/// deleted account's events are dropped: served only to the subscriptions
/// that began before. Events go out of the backfill window
/// (`spec/STORE.md`) as time passes, and are let go.
///
/// Which events were made, and whose, is kept apart from the accounts' own
/// files as they are numbered, in the index (`index`): its entry of an
/// event is appended, under this lock, before the frame that holds the
/// event is appended to its log, and both are on disk before anything is
/// made of the event (`Landing`). A start reads no account's files to learn
/// the events made before it: it reads the index after it, while the
/// server serves, or first where something needs it (`find_old`), and so
/// before any event is numbered.
///
/// What it holds of each event in the window is its seq, its account and
/// when it was made; its frame only for the latest, up to `TAIL` bytes, and
/// those of the service log's own (`kept`). Every other frame is read from
/// its account's store as it is sent (`batch`).
///
/// After a power cut, an account's log may hold the whole frame of a write
/// never answered whose entry the index lost. Nothing of the write is
/// undone: its event is void, never sent, and as its account is next used,
/// if it is active, the events an activation makes are made for it, once
/// (`loaded`, `voided`, `announce`).
pub(crate) struct Firehose {
    /// Itself, for the work it leaves to threads of their own.
    me: Weak<Firehose>,
    seq: Mutex<Seq>,
    /// The seq up to which subscribers may be sent events.
    published: tokio::sync::watch::Sender<u64>,
    /// The subscriptions held, by client address, and in all.
    subscribers: Mutex<(HashMap<String, usize>, usize)>,
    /// Set once the server shuts down: every subscription closes.
    closing: tokio::sync::watch::Sender<bool>,
    /// The backfill window, in milliseconds.
    window: u64,
    /// The service log, where seqs are reserved.
    log: Arc<Wal>,
    /// Where the index is kept.
    at: index::At,
    /// The index's log, once it is read.
    index: OnceLock<Arc<Wal>>,
    /// Held while the index is read.
    reading: Mutex<()>,
    /// The accounts whose stores were loaded before the index was read: to
    /// look into for void events once it is. None from then on.
    unchecked: Mutex<Option<Vec<Weak<Account>>>>,
    /// The accounts with void events whose announcement is not yet on disk.
    owed: AtomicU64,
    /// How many accounts' stores were read for the events before the start.
    #[cfg(test)]
    scanned: AtomicUsize,
    /// The greatest seq an event made before this start is known to have
    /// been given: the service log's, and once the index is read, its.
    /// Seqs are reserved past it (`SEQS`), and given to no event before the
    /// start.
    made: AtomicU64,
}

/// The service log's entry reserving seqs up to `upto`.
pub(crate) const SEQS: &str = "seqs";

/// How many seqs are reserved at once.
const RESERVE: u64 = 1024;

/// The bytes of the latest events' frames held for subscribers.
const TAIL: usize = 4 << 20;

/// The most entries let go as out of the window that are kept to be found
/// to have no frame: by the firehose (`Seq::unsure`), and by the index's
/// compaction (`index::IndexFold`).
const UNSURE: usize = 16;

/// The most bytes of frames read for a subscriber at once, past one event.
const BATCH: usize = 1 << 20;

/// How long frames are read for a subscriber before those read are sent:
/// a cold account's store is loaded to read its events, and the subscriber
/// is not kept waiting for many of them.
const BATCH_TIME: std::time::Duration = std::time::Duration::from_millis(50);

/// The most accounts' stores read at once to find the events before the
/// start where there is no index (`adopt`).
const FIND_AT_ONCE: usize = 8;

/// How long a shutdown waits for the events on their way to the disk.
const SETTLE: Duration = Duration::from_secs(1);

/// How long a shutdown sleeps between looks at what it waits for.
const POLL: Duration = Duration::from_millis(5);

/// An event: its seq, its account, when it was made, whether it is on
/// disk, and its frame if held.
struct Slot {
    seq: u64,
    did: Arc<str>,
    /// When it was made, in milliseconds since the epoch.
    at: u64,
    landed: bool,
    frame: Option<Bytes>,
    /// Whether its frame is held for good: the service log's events, and a
    /// deleted account's while subscribers may yet be sent them.
    kept: bool,
    /// When it was dropped, by the count of drops.
    dropped: Option<u64>,
}

struct Seq {
    /// In order of seq, with holes.
    events: VecDeque<Slot>,
    /// The seq the next event takes.
    next: u64,
    /// The greatest seq reserved in the service log.
    ceiling: u64,
    /// Every event up to this seq is on disk, or will never be.
    published: u64,
    /// How many times events have been dropped.
    drops: u64,
    /// The greatest seq of an event let go as out of the window: the
    /// greater of `sure` and the last of `unsure`.
    gone: u64,
    /// Of the entries let go as out of the window that were made before
    /// this start and not known to have a frame, the latest, up to
    /// `UNSURE`, in order of seq: one found to have none was no event, and
    /// is let go as one no more (`Firehose::settle_after`).
    unsure: VecDeque<(u64, Arc<str>)>,
    /// The greatest seq let go as out of the window, but those in `unsure`.
    sure: u64,
    /// The first seq this start may give out: the events before it are in
    /// the index, and the logs.
    boot: u64,
    /// The seqs of the frames held of the latest events, oldest first, and their bytes.
    tail: VecDeque<u64>,
    tail_bytes: usize,
    /// The seqs of the deleted accounts' events.
    gaps: HashSet<u64>,
    /// The seqs of the void events: those the index has a void entry of,
    /// and those found since.
    voids: HashSet<u64>,
    /// Set as the server shuts down: no event is numbered any more.
    sealed: bool,
}

/// Events numbered, from `seq`, made at `at`, with their entry in the index.
pub(crate) struct Reserved {
    pub seq: u64,
    /// When they were made, in milliseconds since the epoch: their frames'
    /// `time`, their index entries' and their account's log's.
    pub at: u64,
    index: Arc<Wal>,
    entry: u64,
}

impl Reserved {
    /// When they were made, as their frames say.
    pub fn time(&self) -> String {
        datetime_string(self.at as i64)
    }

    /// Their frames, to land once these and their entry are on disk.
    pub fn landing(&self, frames: Vec<Bytes>) -> Landing {
        Landing {
            seq: self.seq,
            times: vec![self.at; frames.len()],
            frames,
            entry: Some((self.index.clone(), self.entry)),
        }
    }
}

/// Events on their way to the disk, numbered from `seq`, to `land` once
/// they are there or `fail` if they never will be.
pub(crate) struct Landing {
    pub seq: u64,
    pub frames: Vec<Bytes>,
    /// When each was made.
    pub times: Vec<u64>,
    /// The index's log and the frame of their entry there.
    entry: Option<(Arc<Wal>, u64)>,
}

impl Landing {
    /// The index's log and the frame of their entry, which is on disk
    /// before anything is made of them, and is waited for before the
    /// frame that holds them.
    pub fn entry(&self) -> Option<(Arc<Wal>, u64)> {
        self.entry.clone()
    }

    /// Return once their entry is on disk.
    pub fn wait_entry(&self) -> std::io::Result<()> {
        match &self.entry {
            Some((wal, n)) => wal.wait(*n),
            None => Ok(()),
        }
    }
}

/// An event as the service log recovered it.
pub(crate) struct Recovered {
    pub seq: u64,
    pub did: Arc<str>,
    pub frame: Bytes,
}

/// Now, in milliseconds since the epoch.
pub(crate) fn now_ms() -> u64 {
    SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .unwrap_or_default()
        .as_millis() as u64
}

impl Seq {
    /// Where the event with this seq is, or would be.
    fn at(&self, seq: u64) -> usize {
        self.events.partition_point(|s| s.seq < seq)
    }

    /// Publish every event from the last published on that subscribers may pass.
    fn advance(&mut self) {
        let mut i = self.at(self.published + 1);
        let mut upto = self.next - 1;
        while let Some(s) = self.events.get(i) {
            if !s.landed && s.dropped.is_none() {
                upto = s.seq - 1;
                break;
            }
            i += 1;
        }
        self.published = self.published.max(upto);
    }

    /// Let go of the events out of the window that every subscriber may pass.
    fn prune(&mut self, before: u64) {
        while self
            .events
            .front()
            .is_some_and(|s| s.at < before && s.seq <= self.published)
        {
            if let Some(s) = self.events.pop_front() {
                self.let_go(s);
            }
        }
    }

    /// Let go of an event as out of the window, after every one let go before.
    fn let_go(&mut self, s: Slot) {
        self.gone = self.gone.max(s.seq);
        if s.seq < self.boot && !s.kept && s.frame.is_none() && s.dropped.is_none() {
            self.unsure.push_back((s.seq, s.did));
            while self.unsure.len() > UNSURE {
                if let Some((seq, _)) = self.unsure.pop_front() {
                    self.sure = self.sure.max(seq);
                }
            }
        } else {
            self.sure = self.sure.max(s.seq);
        }
    }

    /// Hold the frame of a latest event, made at `at` if its account's log
    /// says when, letting go of the oldest held past `TAIL`.
    fn hold(&mut self, seq: u64, frame: Bytes, at: Option<u64>) {
        let i = self.at(seq);
        let Some(slot) = self.events.get_mut(i).filter(|x| x.seq == seq) else {
            return;
        };
        slot.landed = true;
        slot.at = at.unwrap_or(slot.at);
        if slot.kept {
            slot.frame = Some(frame);
            return;
        }
        self.tail_bytes += frame.len();
        slot.frame = Some(frame);
        self.tail.push_back(seq);
        while self.tail_bytes > TAIL && self.tail.len() > 1 {
            let Some(old) = self.tail.pop_front() else {
                break;
            };
            let at = self.at(old);
            if let Some(s) = self.events.get_mut(at).filter(|x| x.seq == old && !x.kept) {
                self.tail_bytes -= s.frame.take().map_or(0, |f| f.len());
            }
        }
    }

    /// Hold the events made before the start, `found`, with those it holds
    /// of before it, the service log's: those before the window's start,
    /// `since`, let go, `made` the seqs of events made that may be held no
    /// more.
    fn merge(&mut self, found: Vec<Slot>, made: Vec<u64>, since: u64) {
        let split = self.at(self.boot);
        let mut before: Vec<Slot> = self.events.drain(..split).collect();
        before.retain(|e| found.binary_search_by_key(&e.seq, |f| f.seq).is_err());
        before.extend(found);
        let window = in_window(before, made, self.boot, since, &self.gaps);
        // Let go in order of seq with those let go before.
        let mut gone: Vec<Slot> = window.let_go;
        let unsure = std::mem::take(&mut self.unsure);
        gone.extend(unsure.into_iter().map(|(seq, did)| Slot {
            seq,
            did,
            at: 0,
            landed: true,
            frame: None,
            kept: false,
            dropped: None,
        }));
        gone.sort_by_key(|e| e.seq);
        for e in gone {
            self.let_go(e);
        }
        self.sure = self.sure.max(window.made);
        self.gone = self.gone.max(window.made);
        self.events.reserve(window.kept.len());
        for e in window.kept.into_iter().rev() {
            self.events.push_front(e);
        }
    }
}

/// The events made before a start, as the window takes them.
struct Window {
    /// Those from its start on, in order of seq.
    kept: Vec<Slot>,
    /// Those before its start, in order of seq: let go.
    let_go: Vec<Slot>,
    /// The greatest of the seqs of events made that may be held no more
    /// and are before its start; 0 if none is.
    made: u64,
}

/// Of the events made before the start `boot`, a deleted account's left
/// out, those from the window's start, `since`, on, and those before it,
/// let go; and of `made`, the seqs of events made that may be held no
/// more, the greatest let go. The events let go as out of the window are
/// those made before the first kept, a deleted account's apart: the last
/// of them is the greatest seq such an event is known to have had, not the
/// seq before the first kept, as the seqs a start reserved and gave no
/// event are of none.
fn in_window(
    mut before: Vec<Slot>,
    made: Vec<u64>,
    boot: u64,
    since: u64,
    gaps: &HashSet<u64>,
) -> Window {
    before.retain(|e| !gaps.contains(&e.seq));
    before.sort_by_key(|e| e.seq);
    let start = before
        .iter()
        .position(|e| e.at >= since)
        .unwrap_or(before.len());
    let first = before.get(start).map(|e| e.seq);
    let let_go = |seq: &u64| *seq < boot && first.is_none_or(|f| *seq < f) && !gaps.contains(seq);
    let made = made.into_iter().filter(let_go).max().unwrap_or(0);
    let kept = before.split_off(start);
    Window {
        kept,
        let_go: before,
        made,
    }
}

impl Firehose {
    /// The service log's events recovered, all on disk, in order of seq;
    /// the seqs of the deleted accounts' events; `last` the greatest seq the
    /// logs say was given out or reserved, which the next follows, and
    /// `made` the greatest the service log says an event was made with;
    /// seqs reserved in `log`; the index kept `at`.
    pub fn new(
        events: Vec<Recovered>,
        gaps: HashSet<u64>,
        last: u64,
        made: u64,
        window: std::time::Duration,
        log: Arc<Wal>,
        at: index::At,
    ) -> Arc<Firehose> {
        let made = events.last().map_or(made, |e| e.seq.max(made));
        let last = last.max(made);
        let events = events
            .into_iter()
            .map(|e| Slot {
                at: event_time(&e.frame).unwrap_or(0),
                seq: e.seq,
                did: e.did,
                landed: true,
                frame: Some(e.frame),
                kept: true,
                dropped: None,
            })
            .collect();
        let seq = Seq {
            events,
            next: last + 1,
            ceiling: last,
            published: last,
            drops: 0,
            gone: 0,
            unsure: VecDeque::new(),
            sure: 0,
            boot: last + 1,
            tail: VecDeque::new(),
            tail_bytes: 0,
            gaps,
            voids: HashSet::new(),
            sealed: false,
        };
        Arc::new_cyclic(|me| Firehose {
            me: me.clone(),
            seq: Mutex::new(seq),
            published: tokio::sync::watch::channel(last).0,
            subscribers: Mutex::default(),
            closing: tokio::sync::watch::channel(false).0,
            window: window.as_millis() as u64,
            log,
            at,
            index: OnceLock::new(),
            reading: Mutex::new(()),
            unchecked: Mutex::new(Some(Vec::new())),
            owed: AtomicU64::new(0),
            #[cfg(test)]
            scanned: AtomicUsize::new(0),
            made: AtomicU64::new(made),
        })
    }

    fn lock(&self) -> std::sync::MutexGuard<'_, Seq> {
        self.seq.lock().unwrap_or_else(PoisonError::into_inner)
    }

    fn boot(&self) -> u64 {
        self.lock().boot
    }

    /// Every seq up to `last` was given out before, as reading the
    /// accounts' logs found: the next follows it.
    pub fn raise(&self, last: u64) -> std::io::Result<()> {
        let mut s = self.lock();
        if last >= s.next {
            s.next = last + 1;
            s.ceiling = s.ceiling.max(last);
            s.published = s.published.max(last);
            s.boot = last + 1;
        }
        let published = s.published;
        drop(s);
        self.published.send_replace(published);
        Ok(())
    }

    /// Every seq given out before is `last` or before, as reading every
    /// account's log found, with what the service log and the index say
    /// was made: the next follows it, whatever was reserved.
    pub fn exact(&self, last: u64) {
        let last = last.max(self.made.load(Ordering::SeqCst));
        let mut s = self.lock();
        s.next = last + 1;
        s.ceiling = s.ceiling.max(last);
        s.published = last;
        s.boot = last + 1;
        self.made.fetch_max(last, Ordering::SeqCst);
        drop(s);
        self.published.send_replace(last);
    }

    /// The seq of the last event numbered, `published` the seq subscribers
    /// may be sent events up to: that, once an event has been numbered since
    /// the start; until then, the greatest an event made before it was
    /// given, which the seqs reserved are past, known once the index is
    /// read (`find_old`). A cursor after it is in the future.
    pub fn last_made(&self, published: u64) -> u64 {
        if published >= self.boot() {
            published
        } else {
            self.made.load(Ordering::SeqCst).min(published)
        }
    }

    /// The seq of the last event a subscriber may be sent: none of an
    /// entry found to have no frame, nor of a seq reserved and given no
    /// event; 0 before any.
    pub fn last_event(&self) -> u64 {
        let published = self.published();
        let s = self.lock();
        s.events
            .iter()
            .rev()
            .filter(|e| e.seq <= published)
            .find(|e| e.landed && e.dropped.is_none())
            .map_or(s.gone, |e| e.seq.max(s.gone))
    }

    /// Number `n` new events of an account, with their entry in the index:
    /// once their seqs are reserved on disk.
    pub fn reserve(&self, did: &str, n: usize) -> std::io::Result<Reserved> {
        self.reserve_as(did, n, false)
    }

    /// Number `n` new events of an account that the service log holds,
    /// whose frames are held for as long as they are in the window.
    pub fn reserve_kept(&self, did: &str, n: usize) -> std::io::Result<Reserved> {
        self.reserve_as(did, n, true)
    }

    fn reserve_as(&self, did: &str, n: usize, kept: bool) -> std::io::Result<Reserved> {
        let index = self.index()?;
        let mut s = self.lock();
        if s.sealed {
            return Err(std::io::Error::other("the server is shutting down"));
        }
        let seq = s.next;
        let end = seq + n as u64 - 1;
        if end > s.ceiling {
            let upto = end + RESERVE;
            let k = self
                .log
                .append(&[serde_json::json!({ "t": SEQS, "upto": upto })])?;
            self.log.wait(k)?;
            s.ceiling = upto;
        }
        let at = now_ms();
        let entry = index.append(&index::entries(seq, n, at, did, kept))?;
        let did: Arc<str> = Arc::from(did);
        s.events.extend((0..n as u64).map(|i| Slot {
            seq: seq + i,
            did: did.clone(),
            at,
            landed: false,
            frame: None,
            kept,
            dropped: None,
        }));
        s.next += n as u64;
        Ok(Reserved {
            seq,
            at,
            index,
            entry,
        })
    }

    fn publish(&self, mut s: std::sync::MutexGuard<'_, Seq>) {
        s.advance();
        s.prune(now_ms().saturating_sub(self.window));
        let published = s.published;
        drop(s);
        self.published.send_if_modified(|n| {
            let more = *n < published;
            *n = (*n).max(published);
            more
        });
    }

    /// Events are on disk: send them, and any after them already there, to subscribers.
    pub fn land(&self, l: Landing) {
        let mut s = self.lock();
        for (i, f) in l.frames.into_iter().enumerate() {
            s.hold(l.seq + i as u64, f, l.times.get(i).copied());
        }
        self.publish(s);
    }

    /// The `n` events from `seq` on will never reach the disk: their numbers
    /// stay unused.
    pub fn fail(&self, seq: u64, n: usize) {
        let mut s = self.lock();
        let at = s.at(seq);
        let end = s.at(seq + n as u64);
        s.events.drain(at..end);
        self.publish(s);
    }

    /// The seq of every event of an account's it holds, not dropped.
    pub fn seqs_of(&self, did: &str) -> Vec<u64> {
        self.lock()
            .events
            .iter()
            .filter(|e| e.dropped.is_none() && &*e.did == did)
            .map(|e| e.seq)
            .collect()
    }

    /// Drop the events with these seqs: from now on they are served only to
    /// the subscriptions that began before, which are sent the frames
    /// `frame` gives, held from now on, as their account's store goes.
    pub fn drop_events(&self, seqs: &[u64], frame: impl Fn(u64) -> Option<Bytes>) {
        let subscribed = self
            .subscribers
            .lock()
            .unwrap_or_else(PoisonError::into_inner)
            .1
            > 0;
        let mut s = self.lock();
        s.drops += 1;
        let drops = s.drops;
        for seq in seqs {
            s.gaps.insert(*seq);
            let at = s.at(*seq);
            if let Some(e) = s.events.get_mut(at).filter(|e| e.seq == *seq) {
                e.dropped = Some(drops);
                if subscribed && e.frame.is_none() {
                    e.frame = frame(*seq);
                }
                e.kept = true;
            }
        }
        self.publish(s);
    }

    /// How many times events have been dropped: what a subscription begun
    /// now passes over.
    pub fn drops(&self) -> u64 {
        self.lock().drops
    }

    /// The seq of the window's start: the first event, up to `upto`, made no
    /// more than the window before now; none if there is none.
    pub fn window_start(&self, upto: u64) -> Option<u64> {
        let since = now_ms().saturating_sub(self.window);
        let s = self.lock();
        s.events
            .iter()
            .take_while(|e| e.seq <= upto)
            .find(|e| e.dropped.is_none() && e.landed && e.at >= since)
            .map(|e| e.seq)
    }

    /// The seq of the last event subscribers may be sent; 0 before any.
    pub fn published(&self) -> u64 {
        *self.published.borrow()
    }

    /// The subscriptions open.
    pub fn subscribers(&self) -> usize {
        self.subscribers
            .lock()
            .unwrap_or_else(PoisonError::into_inner)
            .1
    }

    /// Close every subscription, as the server shuts down.
    pub fn close(&self) {
        self.closing.send_replace(true);
    }

    /// Number no event from now on, as the server shuts down: `reserve`
    /// fails. Waits, up to `SETTLE`, for the events on their way to the
    /// disk to land or fail: whether all have.
    pub fn seal(&self) -> bool {
        let until = Instant::now() + SETTLE;
        loop {
            {
                let mut s = self.lock();
                s.sealed = true;
                if s.published == s.next - 1 {
                    return true;
                }
            }
            if Instant::now() >= until {
                return false;
            }
            std::thread::sleep(POLL);
        }
    }

    /// Close the index's log, if it was read, as the server shuts down,
    /// last of the logs: every frame it took is on disk once this answers.
    pub fn close_index(&self) -> std::io::Result<()> {
        match self.index.get() {
            Some(wal) => wal.close(),
            None => Ok(()),
        }
    }

    /// Whether an account with void events is yet to have its announcement
    /// on disk: a shutdown then leaves no word in its mark, so that the next
    /// start looks for them again (`ops::mark`).
    pub fn owes(&self) -> bool {
        self.owed.load(Ordering::SeqCst) > 0
    }

    /// Whether the next event after `cursor`, up to `upto`, is out of the
    /// window: one let go as out of it, or the first after it there is, not
    /// dropped, made more than the window before now. A deleted account's
    /// events are no events: they are passed over.
    pub fn outdated(&self, cursor: u64, upto: u64) -> bool {
        let since = now_ms().saturating_sub(self.window);
        let s = self.lock();
        if cursor < s.gone {
            return true;
        }
        let at = s.at(cursor + 1);
        s.events
            .range(at..)
            .take_while(|e| e.seq <= upto)
            .find(|e| e.dropped.is_none() && e.landed)
            .is_some_and(|e| e.at < since)
    }

    /// The index's log, read first if it is not.
    fn index(&self) -> std::io::Result<Arc<Wal>> {
        if let Some(wal) = self.index.get() {
            return Ok(wal.clone());
        }
        self.find_old();
        self.index
            .get()
            .cloned()
            .ok_or_else(|| std::io::Error::other("the firehose's index is not read"))
    }

    /// Find the events made before this start, unless they are found
    /// already: read the index, its entries in the window held, those out
    /// of it let go, and the seqs of its void entries noted; seqs given out
    /// from then on are past every one it holds. No account's files are
    /// read. Then the accounts loaded before are looked into for void
    /// events, on a thread of its own. Data that cannot be recovered stops
    /// the server (`cache::unrecoverable`).
    pub fn find_old(&self) {
        if self.index.get().is_some() {
            return;
        }
        let reading = self.reading.lock().unwrap_or_else(PoisonError::into_inner);
        if self.index.get().is_some() {
            return;
        }
        let opened = index::open(&self.at)
            .unwrap_or_else(|why| crate::cache::unrecoverable(&self.at.dir, &why));
        opened.wal.set_fold(Arc::new(index::IndexFold {
            window: self.window,
        }));
        let wal = crate::log::held(&self.at.dir, opened.wal);
        {
            let mut s = self.lock();
            // Nothing is numbered before the index is read: every seq it
            // holds was given out before this start.
            if opened.made >= s.next {
                s.next = opened.made + 1;
                s.ceiling = s.ceiling.max(opened.made);
                s.published = s.published.max(opened.made);
                s.boot = opened.made + 1;
            }
            let boot = s.boot;
            let logged = self.made.fetch_max(opened.made, Ordering::SeqCst);
            s.voids.extend(opened.voids);
            let found: Vec<Slot> = opened
                .entries
                .into_iter()
                .filter(|e| e.kind == index::Kind::Account && e.seq < boot)
                .map(|e| Slot {
                    seq: e.seq,
                    did: e.did,
                    at: e.at,
                    landed: true,
                    frame: None,
                    kept: false,
                    dropped: None,
                })
                .collect();
            let since = now_ms().saturating_sub(self.window);
            s.merge(found, vec![opened.gone, logged], since);
            let published = s.published;
            drop(s);
            self.published.send_if_modified(|n| {
                let more = *n < published;
                *n = (*n).max(published);
                more
            });
        }
        let _ = self.index.set(wal);
        drop(reading);
        let unchecked = self
            .unchecked
            .lock()
            .unwrap_or_else(PoisonError::into_inner)
            .take()
            .unwrap_or_default();
        if !unchecked.is_empty()
            && let Some(me) = self.me.upgrade()
        {
            std::thread::spawn(move || {
                for account in unchecked {
                    let Some(a) = account.upgrade() else { continue };
                    let voids = me.voided(&a.store.events().0);
                    if !voids.is_empty() {
                        me.announce(account, voids);
                    }
                }
            });
        }
    }

    /// An account's store was loaded for the first time in this run,
    /// holding the events `held` gives: looked into for void events now,
    /// if the index is read, or once it is. Nothing the load answers waits
    /// for what is made of them.
    pub fn loaded(&self, account: &Weak<Account>, held: impl FnOnce() -> Vec<(u64, u64)>) {
        {
            let mut unchecked = self
                .unchecked
                .lock()
                .unwrap_or_else(PoisonError::into_inner);
            if let Some(accounts) = unchecked.as_mut() {
                accounts.push(account.clone());
                return;
            }
        }
        let voids = self.voided(&held());
        if !voids.is_empty() {
            self.announce(account.clone(), voids);
        }
    }

    /// Of an account's events, each one's seq and when it was made, those
    /// void and not known to be: made before this start, in the window's
    /// range of seqs, and of which the index holds no entry, void or not. A
    /// slot is made for none of them, so that no replay sends them; they
    /// are void from now on.
    fn voided(&self, held: &[(u64, u64)]) -> Vec<(u64, u64)> {
        let boot = self.boot();
        let mut s = self.lock();
        let mut found = Vec::new();
        for &(seq, at) in held {
            if seq <= s.gone || seq >= boot || s.gaps.contains(&seq) || s.voids.contains(&seq) {
                continue;
            }
            let i = s.at(seq);
            if s.events.get(i).is_some_and(|e| e.seq == seq) {
                continue;
            }
            s.voids.insert(seq);
            found.push((seq, at));
        }
        found
    }

    /// Make, of an account with void events `voids`, the events an
    /// activation makes, if it is active (`lifecycle::announce_found`),
    /// then the index's void entries of them: on a thread of its own, the
    /// account's store held while its events are numbered, so that they
    /// are in order with its others, and nothing else. Each waits for its
    /// frames, the announcement's entries and frame then the void entries,
    /// to be on disk; a kill before them leaves the events to be found
    /// void again, and announced, by the next start.
    fn announce(&self, account: Weak<Account>, voids: Vec<(u64, u64)>) {
        let Some(me) = self.me.upgrade() else { return };
        me.owed.fetch_add(1, Ordering::SeqCst);
        let made = std::thread::Builder::new()
            .name("pds-announce".into())
            .spawn(move || {
                let Some(a) = account.upgrade() else { return };
                let done = (|| -> std::io::Result<()> {
                    if let Some((n, landing)) = crate::lifecycle::announce_found(&me, &me.log, &a)?
                    {
                        let entry = landing.wait_entry();
                        let logged = me.log.wait(n);
                        me.land(landing);
                        entry.and(logged)?;
                    }
                    let index = me.index()?;
                    let entries: Vec<serde_json::Value> = voids
                        .iter()
                        .map(|(seq, at)| index::entry(*seq, *at, &a.did, index::Kind::Void))
                        .collect();
                    let k = index.append(&entries)?;
                    index.wait(k)
                })();
                match done {
                    Ok(()) => {
                        me.owed.fetch_sub(1, Ordering::SeqCst);
                    }
                    Err(e) => crate::ops::failed_for(
                        crate::ops::Level::Error,
                        "announcing an account with void events failed",
                        &a.did,
                        e,
                    ),
                }
            });
        if made.is_err() {
            crate::ops::failed("announcing an account with void events failed", "no thread");
        }
    }

    /// Where the data directory has no index, as the version before this
    /// left it, make the index of the events made before this start,
    /// `boot` its first seq, before the server serves (`spec/STORE.md`,
    /// "Upgrades"): of every account's files, or of none where it holds no
    /// account, so that every later start finds one; its checkpoint,
    /// written whole and durable. The file that version left of the events
    /// at a shutdown is removed, never read.
    pub fn adopt(&self, svc: &crate::Service) -> std::io::Result<()> {
        index::forget_legacy(&self.at.dir)?;
        if index::exists(&self.at.dir) {
            return Ok(());
        }
        {
            let d = crate::read(&svc.directory);
            if d.count() == 0 && d.dids().is_empty() {
                return index::write_whole(&self.at.dir, &[], 0, 0);
            }
        }
        let boot = self.boot();
        let (mut found, made) = self.scan(svc, boot);
        let last = found
            .iter()
            .map(|e| e.seq)
            .chain(made.iter().copied())
            .max();
        let since = now_ms().saturating_sub(self.window);
        let window = {
            let s = self.lock();
            found.extend(s.events.range(..s.at(boot)).map(|e| Slot {
                seq: e.seq,
                did: e.did.clone(),
                at: e.at,
                landed: true,
                frame: None,
                kept: true,
                dropped: None,
            }));
            in_window(found, made, boot, since, &s.gaps)
        };
        let gone = window
            .let_go
            .iter()
            .map(|e| e.seq)
            .fold(window.made, u64::max);
        let events: Vec<(u64, Arc<str>, u64)> = window
            .kept
            .into_iter()
            .filter(|e| !e.kept)
            .map(|e| (e.seq, e.did, e.at))
            .collect();
        index::write_whole(&self.at.dir, &events, gone, last.unwrap_or(0))
    }

    /// The events made before this start, `boot` its first seq, as every
    /// account's store holds them, and the seqs of events made that no
    /// store may hold any more. The accounts are read several at once, and
    /// neither an account not loaded nor a store not held is loaded for
    /// it: its files are read (`checkpoint::events_on_disk`).
    fn scan(&self, svc: &crate::Service, boot: u64) -> (Vec<Slot>, Vec<u64>) {
        let accounts: Vec<String> = crate::read(&svc.directory).dids();
        let next = std::sync::atomic::AtomicUsize::new(0);
        let readers = std::thread::available_parallelism()
            .map_or(1, |n| n.get())
            .min(FIND_AT_ONCE);
        // An account's events, the greatest seq any had, and the greatest
        // let go: none of an account deleted.
        let events_of = |did: &str| {
            #[cfg(test)]
            self.scanned.fetch_add(1, Ordering::SeqCst);
            let loaded = {
                let d = crate::read(&svc.directory);
                match d.by_did.get(did) {
                    Some(a) => Some(a.clone()),
                    None if d.deleted.contains(did) => return None,
                    // The directory is held while its files are read: no
                    // account is loaded meanwhile, so nothing loads its
                    // store, appends to its log or compacts it.
                    None => match crate::checkpoint::events_on_disk(&svc.ctx, did) {
                        Ok(found) => return Some(found),
                        // Files a start must mend, or the server stop for: as a load finds them.
                        Err(_) => None,
                    },
                }
            };
            let a = loaded.or_else(|| svc.by_did(did))?;
            Some(a.store.events())
        };
        // The seqs of events made that no store may hold any more: the last
        // the service log tells of, each account's last, and the last its
        // log's compaction let go.
        let logged = self.made.load(Ordering::SeqCst);
        let read =
            || {
                let (mut found, mut made): (Vec<Slot>, Vec<u64>) = (Vec::new(), Vec::new());
                while let Some(did) = accounts.get(next.fetch_add(1, Ordering::Relaxed)) {
                    let Some((events, last, let_go)) = events_of(did) else {
                        continue;
                    };
                    let did: Arc<str> = Arc::from(did.as_str());
                    // The last it had before the start, one let go too.
                    let before = if last < boot {
                        last
                    } else {
                        events
                            .iter()
                            .map(|e| e.0)
                            .filter(|seq| *seq < boot)
                            .max()
                            .unwrap_or(0)
                    };
                    self.made.fetch_max(before, Ordering::SeqCst);
                    made.extend([before, let_go]);
                    found.extend(events.into_iter().filter(|(seq, _)| *seq < boot).map(
                        |(seq, at)| Slot {
                            seq,
                            did: did.clone(),
                            at,
                            landed: true,
                            frame: None,
                            kept: false,
                            dropped: None,
                        },
                    ));
                }
                (found, made)
            };
        let (found, mut made) = std::thread::scope(|scope| {
            let others: Vec<_> = (1..readers).map(|_| scope.spawn(read)).collect();
            let (mut found, mut made) = read();
            for other in others {
                let (f, m) = other
                    .join()
                    .unwrap_or_else(|panic| std::panic::resume_unwind(panic));
                found.extend(f);
                made.extend(m);
            }
            (found, made)
        });
        made.push(logged);
        (found, made)
    }

    /// Whether the event `seq` of `did`, made before this start, has no
    /// frame and never will: its entry was kept and its write not, or its
    /// account is gone. One its account's log let go as out of the window
    /// is an event all the same.
    fn never(&self, svc: &crate::Service, seq: u64, did: &str) -> bool {
        match svc.account(did) {
            None => true,
            Some(a) => {
                let st = crate::read(&a.store);
                seq > st.let_go() && st.event_frame(seq).is_none()
            }
        }
    }

    /// Let go of the events of these seqs, made before this start, that
    /// have no frame: never to be sent, nor to raise what is let go as out
    /// of the window.
    fn forget(&self, seqs: &[u64]) {
        if seqs.is_empty() {
            return;
        }
        let boot = self.boot();
        let mut s = self.lock();
        for &seq in seqs {
            let i = s.at(seq);
            if s.events.get(i).is_some_and(|e| {
                e.seq == seq && seq < boot && !e.kept && e.dropped.is_none() && e.frame.is_none()
            }) {
                s.events.remove(i);
            }
        }
    }

    /// Of the events after `cursor`, up to `upto`, made before this start,
    /// let go of those that have no frame, up to the first that has one:
    /// so that the next event after the cursor, whose time says whether it
    /// is out of the window (`outdated`), is one. Those let go as out of
    /// the window first, the latest first, then those held.
    pub fn settle_after(&self, svc: &crate::Service, cursor: u64, upto: u64) {
        loop {
            let next = {
                let s = self.lock();
                match s.unsure.back() {
                    Some((seq, did)) if *seq > cursor && *seq > s.sure => (*seq, did.clone()),
                    _ => break,
                }
            };
            let never = self.never(svc, next.0, &next.1);
            let mut s = self.lock();
            if s.unsure.back().is_some_and(|(seq, _)| *seq == next.0) {
                s.unsure.pop_back();
                if !never {
                    s.sure = s.sure.max(next.0);
                }
                s.gone = s.sure.max(s.unsure.back().map_or(0, |e| e.0));
            }
            if !never {
                break;
            }
        }
        let boot = self.boot();
        loop {
            let next = {
                let s = self.lock();
                let i = s.at(cursor + 1);
                match s
                    .events
                    .range(i..)
                    .take_while(|e| e.seq <= upto)
                    .find(|e| e.dropped.is_none() && e.landed)
                {
                    Some(e) if !e.kept && e.frame.is_none() && e.seq < boot => {
                        (e.seq, e.did.clone())
                    }
                    _ => return,
                }
            };
            if !self.never(svc, next.0, &next.1) {
                return;
            }
            self.forget(&[next.0]);
        }
    }

    /// The frames of the events after `from` up to `to`, all of which are
    /// on disk, for a subscription begun after `drops` drops: as many as
    /// make `BATCH` bytes or are read in `BATCH_TIME`, at least one, each
    /// read from its account's store if not held. Answers them and the seq
    /// they reach. An event with no frame, which never will have one, is
    /// let go.
    pub fn batch(&self, svc: &crate::Service, from: u64, to: u64, drops: u64) -> (Vec<Bytes>, u64) {
        const MOST: usize = 4096;
        let boot = self.boot();
        let (wanted, mut reached): (Vec<_>, u64) = {
            let s = self.lock();
            let (a, b) = (s.at(from + 1), s.at(to + 1));
            let w: Vec<_> = s
                .events
                .range(a..b)
                .take(MOST)
                .map(|e| {
                    (
                        e.seq,
                        e.did.clone(),
                        e.frame.clone(),
                        e.dropped.is_none_or(|d| d > drops),
                    )
                })
                .collect();
            let reached = if w.len() == MOST {
                w.last().map_or(to, |e| e.0)
            } else {
                to
            };
            (w, reached)
        };
        let mut out = Vec::new();
        let mut never = Vec::new();
        let mut bytes = 0;
        let began = std::time::Instant::now();
        for (seq, did, frame, sent) in wanted {
            if bytes >= BATCH || (!out.is_empty() && began.elapsed() >= BATCH_TIME) {
                reached = seq - 1;
                break;
            }
            if !sent {
                continue;
            }
            // An event whose account's store no longer holds it went out of
            // the window meanwhile, or its account was deleted; or, made
            // before the start, it never reached its account's log.
            let Some(f) = frame.or_else(|| match svc.account(&did) {
                Some(a) => {
                    let st = crate::read(&a.store);
                    let f = st.event_frame(seq);
                    if f.is_none() && seq < boot && seq > st.let_go() {
                        never.push(seq);
                    }
                    f
                }
                None => None,
            }) else {
                continue;
            };
            bytes += f.len();
            out.push(f);
        }
        self.forget(&never);
        (out, reached)
    }

    pub fn subscribe(&self) -> tokio::sync::watch::Receiver<u64> {
        self.published.subscribe()
    }

    /// Every frame after `from` up to `to`, the events before the start found.
    #[cfg(test)]
    pub fn get(&self, svc: &crate::Service, from: u64, to: u64, drops: u64) -> Vec<Bytes> {
        self.find_old();
        let mut out = Vec::new();
        let mut pos = from;
        let to = to.min(*self.published.borrow());
        while pos < to {
            let (batch, next) = self.batch(svc, pos, to, drops);
            out.extend(batch);
            pos = next;
        }
        out
    }

    /// How many events it holds, on disk or not, those before the start found.
    #[cfg(test)]
    pub fn len(&self) -> usize {
        self.find_old();
        self.lock().events.len()
    }

    /// The frames it holds of the events after `from` up to `to`, for a
    /// subscription begun after `drops` drops.
    #[cfg(test)]
    pub fn held(&self, from: u64, to: u64, drops: u64) -> Vec<Bytes> {
        let s = self.lock();
        let (a, b) = (s.at(from + 1), s.at(to + 1));
        s.events
            .range(a..b)
            .filter(|e| e.dropped.is_none_or(|d| d > drops))
            .filter_map(|e| e.frame.clone())
            .collect()
    }

    /// How many events it holds, on disk or not.
    #[cfg(test)]
    pub fn held_len(&self) -> usize {
        self.lock().events.len()
    }

    /// How many accounts' stores were read for the events before the start.
    #[cfg(test)]
    pub fn scanned(&self) -> usize {
        self.scanned.load(Ordering::SeqCst)
    }

    /// What it holds: its events; the greatest seq let go as out of the
    /// window; and the greatest an event before the start is known to have.
    #[cfg(test)]
    pub fn holds(&self) -> (Vec<Held>, u64, u64) {
        let s = self.lock();
        let events = s
            .events
            .iter()
            .map(|e| (e.seq, e.did.to_string(), e.at, e.frame.is_some()))
            .collect();
        (events, s.gone, self.made.load(Ordering::SeqCst))
    }
}

/// An event as the firehose holds it: its seq, its account, when it was
/// made, and whether its frame is held.
#[cfg(test)]
type Held = (u64, String, u64, bool);

/// Read the index while the server serves (`Firehose::find_old`): neither
/// the start nor a request waits for it, but what needs it first.
pub(crate) fn find_soon(svc: &Shared) {
    let svc = svc.clone();
    tokio::task::spawn_blocking(move || svc.events.find_old());
}

/// When an event was made: its `time`, in milliseconds since the epoch.
pub fn event_time(frame: &[u8]) -> Option<u64> {
    let (_, n) = decode_prefix(frame).ok()?;
    let V::Map(body) = decode(&frame[n..]).ok()? else {
        return None;
    };
    let Some((_, V::Str(t))) = body.iter().find(|(k, _)| k == "time") else {
        return None;
    };
    pds_repo::data::datetime_millis(t).and_then(|ms| u64::try_from(ms).ok())
}

/// An event's frame with its seq changed.
pub fn renumber(frame: &[u8], seq: u64) -> Result<Vec<u8>, String> {
    let (header, n) = decode_prefix(frame)?;
    let mut body = decode(&frame[n..])?;
    let V::Map(fields) = &mut body else {
        return Err("an event whose body is not a map".into());
    };
    let Some((_, at)) = fields.iter_mut().find(|(k, _)| k == "seq") else {
        return Err("an event with no seq".into());
    };
    *at = V::Int(seq as i64);
    let mut out = encode(&header);
    out.extend(encode(&body));
    Ok(out)
}

/// The current time as an atproto datetime, in UTC to the millisecond.
pub fn timestamp() -> String {
    let ms = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .unwrap_or_default()
        .as_millis() as i64;
    pds_repo::data::datetime_string(ms)
}

fn message(t: &str, body: Vec<(&str, V)>) -> Vec<u8> {
    let mut out = encode(&V::Map(vec![
        ("op".into(), V::Int(1)),
        ("t".into(), V::Str(t.into())),
    ]));
    out.extend(encode(&V::Map(
        body.into_iter().map(|(k, v)| (k.to_string(), v)).collect(),
    )));
    out
}

fn error_frame(name: &str, text: &str) -> Vec<u8> {
    let mut out = encode(&V::Map(vec![("op".into(), V::Int(-1))]));
    out.extend(encode(&V::Map(vec![
        ("error".into(), V::Str(name.into())),
        ("message".into(), V::Str(text.into())),
    ])));
    out
}

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

/// The `#commit` event for a commit, made at `time`.
pub fn commit_event(did: &str, seq: u64, time: &str, c: &Change) -> Vec<u8> {
    let head = cid_of(0x71, &c.head_bytes);
    let mut blocks: Vec<(&[u8], &[u8])> = vec![(&head, &c.head_bytes)];
    blocks.extend(c.blocks.iter().map(|(k, d)| (k.as_slice(), d.as_slice())));
    let ops = c
        .ops
        .iter()
        .map(|o| {
            let mut m = vec![
                ("action".to_string(), s(o.action)),
                ("path".to_string(), s(&o.path)),
                ("cid".to_string(), o.cid.clone().map_or(V::Null, V::Link)),
            ];
            if let Some(p) = &o.prev {
                m.push(("prev".to_string(), V::Link(p.clone())));
            }
            V::Map(m)
        })
        .collect();
    let mut body = vec![
        ("seq", V::Int(seq as i64)),
        ("rebase", V::Bool(false)),
        ("tooBig", V::Bool(false)),
        ("repo", s(did)),
        ("commit", V::Link(head.clone())),
        ("rev", s(&c.rev)),
        ("since", c.since.as_deref().map_or(V::Null, s)),
        ("blocks", V::Bytes(car_file(&head, blocks))),
        ("ops", V::Arr(ops)),
        ("blobs", V::Arr(vec![])),
        ("time", s(time)),
    ];
    if let Some(p) = &c.prev_data {
        body.push(("prevData", V::Link(p.clone())));
    }
    message("#commit", body)
}

/// The `#identity` event of an account's handle.
pub fn identity_event(did: &str, handle: &str, seq: u64, time: &str) -> Vec<u8> {
    message(
        "#identity",
        vec![
            ("seq", V::Int(seq as i64)),
            ("did", s(did)),
            ("time", s(time)),
            ("handle", s(handle)),
        ],
    )
}

/// The `#identity` event of a DID whose document changed, with no handle:
/// a PLC operation submitted for it (`spec/MIGRATION.md`).
pub fn did_event(did: &str, seq: u64, time: &str) -> Vec<u8> {
    message(
        "#identity",
        vec![
            ("seq", V::Int(seq as i64)),
            ("did", s(did)),
            ("time", s(time)),
        ],
    )
}

/// The `#account` event of an account's state: `active`, or not and why.
pub fn account_event(did: &str, seq: u64, time: &str, status: Option<&str>) -> Vec<u8> {
    let mut body = vec![
        ("seq", V::Int(seq as i64)),
        ("did", s(did)),
        ("time", s(time)),
        ("active", V::Bool(status.is_none())),
    ];
    if let Some(st) = status {
        body.push(("status", s(st)));
    }
    message("#account", body)
}

/// The `#sync` event of a commit, by its block and rev.
pub fn sync_event(did: &str, seq: u64, time: &str, head_bytes: &[u8], rev: &str) -> Vec<u8> {
    let head = cid_of(0x71, head_bytes);
    message(
        "#sync",
        vec![
            ("seq", V::Int(seq as i64)),
            ("did", s(did)),
            (
                "blocks",
                V::Bytes(car_file(&head, [(head.as_slice(), head_bytes)])),
            ),
            ("rev", s(rev)),
            ("time", s(time)),
        ],
    )
}

/// What a new account's stream starts with, from `#identity` to `#sync`,
/// numbered from `seq`, made at `time`.
pub fn initial_events(did: &str, handle: &str, seq: u64, time: &str, c: &Change) -> Vec<Vec<u8>> {
    vec![
        identity_event(did, handle, seq, time),
        account_event(did, seq + 1, time, None),
        commit_event(did, seq + 2, time, c),
        sync_event(did, seq + 3, time, &c.head_bytes, &c.rev),
    ]
}

/// A subscription held, by its client: let go when its connection ends.
struct Subscription {
    st: Shared,
    client: String,
}

impl Subscription {
    /// Hold one for `client`, unless it holds `MAX_SUBSCRIPTIONS_PER_CLIENT`
    /// already, or the server `MAX_SUBSCRIPTIONS`.
    fn hold(st: &Shared, client: String) -> Option<Subscription> {
        let mut subs = st
            .events
            .subscribers
            .lock()
            .unwrap_or_else(PoisonError::into_inner);
        let (by_client, all) = &mut *subs;
        let held = by_client.entry(client.clone()).or_default();
        if *held >= limits::MAX_SUBSCRIPTIONS_PER_CLIENT || *all >= limits::MAX_SUBSCRIPTIONS {
            if *held == 0 {
                by_client.remove(&client);
            }
            return None;
        }
        *held += 1;
        *all += 1;
        Some(Subscription {
            st: st.clone(),
            client,
        })
    }
}

impl Drop for Subscription {
    fn drop(&mut self) {
        let mut subs = self
            .st
            .events
            .subscribers
            .lock()
            .unwrap_or_else(PoisonError::into_inner);
        let (by_client, all) = &mut *subs;
        *all -= 1;
        if let Some(n) = by_client.get_mut(&self.client) {
            *n -= 1;
            if *n == 0 {
                by_client.remove(&self.client);
            }
        }
    }
}

/// `subscribeRepos`: refused as XRPC refuses a call past its rate limits for
/// a client, or a server, holding all the subscriptions it may, and taking
/// no message from the client longer than `MAX_CLIENT_MESSAGE`.
pub async fn subscribe(
    State(st): State<Shared>,
    Query(params): Query<Vec<(String, String)>>,
    headers: HeaderMap,
    peer: Option<Extension<limits::Peer>>,
    ws: Result<WebSocketUpgrade, WebSocketUpgradeRejection>,
) -> Response {
    let Ok(ws) = ws else {
        return (StatusCode::UPGRADE_REQUIRED, "Upgrade Required").into_response();
    };
    let client = limits::client(
        &st.config.trusted_proxies,
        &headers,
        peer.map(|Extension(p)| p.0),
    );
    let Some(held) = Subscription::hold(&st, client) else {
        return crate::respond(
            crate::err(429, "RateLimitExceeded", "Too many subscriptions"),
            None,
        );
    };
    let cursor = params
        .iter()
        .find(|(k, _)| k == "cursor")
        .map(|(_, v)| v.parse::<u64>());
    ws.max_message_size(limits::MAX_CLIENT_MESSAGE)
        .max_frame_size(limits::MAX_CLIENT_MESSAGE)
        .on_upgrade(move |socket| async move {
            stream(st, cursor, socket).await;
            drop(held);
        })
}

/// Send the events after `cursor` (or none, without one), or those of the
/// backfill window (`begin`), then each new event as it reaches the disk. What the client sends is read and thrown away; a
/// message too long closes the connection with `1009`.
async fn stream(
    st: Shared,
    cursor: Option<Result<u64, std::num::ParseIntError>>,
    mut socket: WebSocket,
) {
    // The events dropped before it begins, it never gets.
    let drops = st.events.drops();
    let mut rx = st.events.subscribe();
    let last = *rx.borrow();
    // A cursor not past the last seq numbered needs the events before the
    // start found: to be sent them, and to be refused if it is past the
    // last of them; and the first after it to be an event.
    if let Some(Ok(c)) = cursor
        && c <= last
    {
        let svc = st.clone();
        if tokio::task::spawn_blocking(move || {
            svc.events.find_old();
            svc.events.settle_after(&svc, c, last);
        })
        .await
        .is_err()
        {
            return;
        }
    }
    let made = st.events.last_made(last);
    let mut pos = match begin(cursor, last, made, |c| {
        st.events
            .outdated(c, last)
            .then(|| st.events.window_start(last))
    }) {
        Ok((pos, false)) => pos,
        Ok((pos, true)) => {
            let info = message(
                "#info",
                vec![
                    ("name", s("OutdatedCursor")),
                    (
                        "message",
                        s("Requested cursor exceeded limit. Possibly missing events"),
                    ),
                ],
            );
            if socket.send(Message::Binary(info.into())).await.is_err() {
                return;
            }
            pos
        }
        Err((name, text)) => return refuse(socket, name, text).await,
    };
    let mut closing = st.events.closing.subscribe();
    loop {
        let upto = *rx.borrow_and_update();
        // Read from disk as they are sent: a batch at a time.
        while pos < upto {
            let svc = st.clone();
            let Ok((batch, reached)) =
                tokio::task::spawn_blocking(move || svc.events.batch(&svc, pos, upto, drops)).await
            else {
                return;
            };
            pos = reached;
            for frame in batch {
                if socket.send(Message::Binary(frame)).await.is_err() {
                    return;
                }
            }
        }
        tokio::select! {
            changed = rx.changed() => if changed.is_err() { return },
            () = async { let _ = closing.wait_for(|c| *c).await; } => {
                let close = CloseFrame { code: close_code::AWAY, reason: "Server shutting down".into() };
                let _ = socket.send(Message::Close(Some(close))).await;
                return;
            }
            incoming = socket.recv() => match incoming {
                None | Some(Ok(Message::Close(_))) => return,
                Some(Err(_)) => {
                    // Most likely a message past the limit: the connection
                    // ends, saying so if it still can.
                    let close = CloseFrame { code: close_code::SIZE, reason: "Message too big".into() };
                    let _ = socket.send(Message::Close(Some(close))).await;
                    return;
                }
                Some(Ok(_)) => {}
            },
        }
    }
}

/// Where a subscription from `cursor` begins, `last` the seq events may be
/// sent up to and `made` the last event's, no later: the seq it sends
/// events after, and whether an `#info` `OutdatedCursor` goes first; or why
/// it is refused. `outdated` answers, of a cursor whose
/// next event is out of the backfill window, the window's start, and of
/// any other, none (`spec/STORE.md`).
fn begin(
    cursor: Option<Result<u64, std::num::ParseIntError>>,
    last: u64,
    made: u64,
    outdated: impl FnOnce(u64) -> Option<Option<u64>>,
) -> Result<(u64, bool), (&'static str, &'static str)> {
    match cursor {
        None => Ok((last, false)),
        Some(Err(_)) => Err(("InvalidRequest", "Invalid cursor")),
        Some(Ok(c)) if c > made => Err(("FutureCursor", "Cursor in the future")),
        Some(Ok(c)) if c == last => Ok((c, false)),
        Some(Ok(c)) => match outdated(c) {
            None => Ok((c, false)),
            Some(start) => Ok((start.map_or(last, |s| s - 1), true)),
        },
    }
}

async fn refuse(mut socket: WebSocket, name: &str, text: &str) {
    let _ = socket
        .send(Message::Binary(error_frame(name, text).into()))
        .await;
    let _ = socket.send(Message::Close(None)).await;
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::testing::*;
    use serde_json::{Value as Json, json};
    use std::collections::BTreeMap;
    use std::path::{Path, PathBuf};

    fn seq_of(frame: &[u8]) -> i64 {
        let (_, at) = decode_prefix(frame).unwrap();
        match decode(&frame[at..]).unwrap() {
            V::Map(m) => match m.iter().find(|(k, _)| k == "seq") {
                Some((_, V::Int(n))) => *n,
                _ => panic!("no seq"),
            },
            _ => panic!("not a map"),
        }
    }

    /// An event's type, as `#commit`, and its body.
    fn event(frame: &[u8]) -> (String, Vec<(String, V)>) {
        let (header, at) = decode_prefix(frame).unwrap();
        let V::Map(header) = header else {
            panic!("a header not a map")
        };
        let Some((_, V::Str(t))) = header.into_iter().find(|(k, _)| k == "t") else {
            panic!("an event of no type")
        };
        let V::Map(body) = decode(&frame[at..]).unwrap() else {
            panic!("a body not a map")
        };
        (t, body)
    }

    /// A text field of an event's body.
    fn text(body: &[(String, V)], name: &str) -> Option<String> {
        body.iter()
            .find(|(k, _)| k == name)
            .and_then(|(_, v)| match v {
                V::Str(s) => Some(s.clone()),
                _ => None,
            })
    }

    fn landing(seq: u64) -> Landing {
        Landing {
            seq,
            times: Vec::new(),
            frames: vec![Bytes::from(identity_event(
                "did:plc:a",
                "a.test",
                seq,
                &timestamp(),
            ))],
            entry: None,
        }
    }

    const DAY: std::time::Duration = std::time::Duration::from_secs(86400);

    /// Where a firehose of these tests keeps its index: `dir`.
    fn at(dir: &Path) -> index::At {
        index::At {
            dir: dir.to_path_buf(),
            pool: pds_store::Files::new(8),
            policy: pds_store::Policy::default(),
            durable: false,
        }
    }

    /// A firehose of these events, `last` the greatest seq given out, its
    /// seqs reserved in a log of its own and its index in a directory of
    /// its own.
    fn firehose(events: Vec<Recovered>, last: u64) -> Arc<Firehose> {
        let dir = scratch(&format!("events-{}", rand::random::<u64>()));
        let (log, _) = pds_store::Wal::open(&dir.join("seqs.log"), None).unwrap();
        Firehose::new(
            events,
            HashSet::new(),
            last,
            last,
            DAY,
            Arc::new(log),
            at(&dir),
        )
    }

    /// The seq the next `n` events of `did` are numbered from.
    fn number(f: &Firehose, did: &str, n: usize) -> u64 {
        f.reserve(did, n).unwrap().seq
    }

    /// Events whose write failed leave their numbers unused: those after
    /// them keep theirs, and are sent once the events before them are on
    /// disk or failed.
    #[test]
    fn failed_events_leave_holes() {
        let f = firehose(vec![], 0);
        let rx = f.subscribe();
        let (a, b, c) = (
            number(&f, "did:plc:a", 1),
            number(&f, "did:plc:a", 1),
            number(&f, "did:plc:a", 1),
        );
        assert_eq!((a, b, c), (1, 2, 3));
        f.land(landing(c));
        assert_eq!(*rx.borrow(), 0);
        f.fail(a, 1);
        // The hole may be passed; the event after it is not on disk yet.
        assert_eq!(*rx.borrow(), 1);
        let d = number(&f, "did:plc:a", 1);
        assert_eq!(d, 4);
        f.land(landing(b));
        assert_eq!(*rx.borrow(), 3);
        f.land(landing(d));
        assert_eq!(*rx.borrow(), 4);
        let seqs: Vec<i64> = f.held(0, 4, 0).iter().map(|e| seq_of(e)).collect();
        assert_eq!(seqs, [2, 3, 4]);
        // Failed last, the numbers are still not given again.
        let e = number(&f, "did:plc:a", 2);
        f.fail(e, 2);
        assert_eq!(*rx.borrow(), 6);
        assert_eq!(number(&f, "did:plc:a", 1), 7);
    }

    /// A deleted account's events keep their places: a subscription begun
    /// before they were dropped gets them, one begun after does not, and a
    /// restart's holes are passed over; numbers go on after every one given
    /// out, those after the last recovered too.
    #[test]
    fn dropped_events_keep_their_places() {
        let kept = |seq| Recovered {
            seq,
            did: Arc::from("did:plc:b"),
            frame: landing(seq).frames.remove(0),
        };
        let f = firehose(vec![kept(1), kept(3)], 4);
        assert_eq!(*f.subscribe().borrow(), 4);
        let seqs = |v: Vec<Bytes>| v.iter().map(|e| seq_of(e)).collect::<Vec<_>>();
        assert_eq!(seqs(f.held(0, 4, 0)), [1, 3]);
        let live = f.drops();
        let a = number(&f, "did:plc:a", 2);
        assert_eq!(a, 5);
        let mut l = landing(a);
        l.frames.push(Bytes::from(identity_event(
            "did:plc:a",
            "a.test",
            a + 1,
            &timestamp(),
        )));
        f.land(l);
        let b = number(&f, "did:plc:b", 1);
        f.land(landing(b));
        assert_eq!(f.seqs_of("did:plc:a"), [5, 6]);
        f.drop_events(&f.seqs_of("did:plc:a"), |_| None);
        assert!(f.seqs_of("did:plc:a").is_empty());
        assert_eq!(seqs(f.held(0, 7, live)), [1, 3, 5, 6, 7]);
        assert_eq!(seqs(f.held(0, 7, f.drops())), [1, 3, 7]);
        assert_eq!(number(&f, "did:plc:b", 1), 8);
    }

    /// A cursor whose next event is at or after the window's start, or the
    /// last event's, replays from it; any other gets `#info` first, then the
    /// window's events, or none; one past the last is refused.
    #[test]
    fn where_a_subscription_begins() {
        // The window starts at 4: cursors before 3 are out of it.
        let ok = |c: u64, last, start: Option<u64>| {
            begin(Some(Ok(c)), last, last, |c| {
                start
                    .filter(|s| c + 1 < *s)
                    .map(Some)
                    .or(start.is_none().then_some(None))
            })
        };
        assert_eq!(ok(5, 10, Some(4)), Ok((5, false)));
        assert_eq!(ok(3, 10, Some(4)), Ok((3, false)));
        assert_eq!(ok(2, 10, Some(4)), Ok((3, true)));
        assert_eq!(ok(0, 10, Some(4)), Ok((3, true)));
        assert_eq!(ok(0, 10, Some(1)), Ok((0, false)));
        assert_eq!(ok(10, 10, None), Ok((10, false)));
        assert_eq!(ok(9, 10, None), Ok((10, true)));
        assert_eq!(ok(0, 0, None), Ok((0, false)));
        assert_eq!(
            ok(11, 10, Some(4)),
            Err(("FutureCursor", "Cursor in the future"))
        );
        assert_eq!(begin(None, 10, 10, |_| None), Ok((10, false)));
        assert!(begin(Some("x".parse::<u64>()), 10, 10, |_| None).is_err());
        // After a start, seqs are reserved past the last event made, 7: a
        // cursor past it is in the future, though none is numbered yet.
        assert_eq!(
            begin(Some(Ok(8)), 10, 7, |_| None),
            Err(("FutureCursor", "Cursor in the future"))
        );
        assert_eq!(begin(Some(Ok(7)), 10, 7, |_| None), Ok((7, false)));
        assert_eq!(begin(None, 10, 7, |_| None), Ok((10, false)));
    }

    /// The window's start is the first event made within the window; events
    /// out of it are let go once every subscriber may pass them.
    #[test]
    fn the_window() {
        let old = |seq| Recovered {
            seq,
            did: Arc::from("did:plc:b"),
            frame: Bytes::from(identity_event(
                "did:plc:b",
                "b.test",
                seq,
                "2000-01-01T00:00:00.000Z",
            )),
        };
        let f = firehose(vec![old(1), old(2)], 2);
        assert_eq!(f.window_start(2), None);
        assert!(f.outdated(0, 2) && !f.outdated(2, 2));
        let a = number(&f, "did:plc:a", 1);
        assert_eq!(f.window_start(2), None);
        f.land(landing(a));
        assert_eq!(f.window_start(3), Some(3));
        // The old ones are let go as events land.
        assert_eq!(f.held_len(), 1);
        assert_eq!(f.held(0, 3, 0).len(), 1);
        // Let go, they still make a cursor before them out of the window.
        assert!(f.outdated(1, 3) && !f.outdated(2, 3));
        assert_eq!(
            event_time(&landing(1).frames[0]).map(|t| t / 100_000),
            Some(now_ms() / 100_000)
        );
    }

    /// Seqs are reserved in the service log only past the greatest reserved
    /// before, `RESERVE` at a time; each numbering appends one frame to the
    /// index, its events' entries in order, made when its reservation says,
    /// those the service log holds marked.
    #[test]
    fn numbers_are_reserved_and_indexed() {
        let dir = scratch("events-reserved");
        let (log, _) = pds_store::Wal::open(&dir.join("seqs.log"), None).unwrap();
        let reserved = || -> Vec<u64> {
            pds_store::scan(&std::fs::read(dir.join("seqs.log")).unwrap())
                .unwrap()
                .0
                .iter()
                .flatten()
                .filter(|e| e["t"] == SEQS)
                .map(|e| e["upto"].as_u64().unwrap())
                .collect()
        };
        let f = Firehose::new(
            vec![],
            HashSet::new(),
            1028,
            4,
            DAY,
            Arc::new(log),
            at(&dir),
        );
        let a = f.reserve("did:plc:a", 1).unwrap();
        assert_eq!((a.seq, reserved()), (1029, vec![1029 + RESERVE]));
        let b = f.reserve_kept("did:plc:b", 2).unwrap();
        assert_eq!((b.seq, reserved()), (1030, vec![1029 + RESERVE]));
        assert_eq!(
            event_time(&identity_event("x", "y", 1, &b.time())),
            Some(b.at)
        );
        b.landing(Vec::new()).wait_entry().unwrap();
        let mut frames = Vec::new();
        pds_store::scan_file(&index::layout(&dir).log(0), |_, _, f| {
            frames.push(f);
            Ok(())
        })
        .unwrap()
        .unwrap();
        assert_eq!(
            frames,
            [
                vec![json!([1029, a.at, "did:plc:a"])],
                vec![
                    json!([1030, b.at, "did:plc:b", 1]),
                    json!([1031, b.at, "did:plc:b", 1])
                ]
            ]
        );
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// Once the server shuts down no event is numbered, the index closed
    /// last; an event is made when its reservation says.
    #[test]
    fn sealed_as_the_server_shuts_down() {
        let f = firehose(vec![], 0);
        let a = f.reserve("did:plc:a", 1).unwrap();
        assert!(!f.seal());
        assert!(f.reserve("did:plc:a", 1).is_err());
        f.land(a.landing(landing(a.seq).frames));
        assert_eq!(f.holds().0, [(a.seq, "did:plc:a".to_string(), a.at, true)]);
        assert!(f.seal());
        f.close_index().unwrap();
        assert!(f.reserve("did:plc:a", 1).is_err());
    }

    /// The server on `dir`, loading every account as it starts or each on
    /// its first use, with a backfill window.
    fn serve(dir: &Path, plc: &str, load_all: bool, window: Duration) -> Shared {
        open_with(dir, plc, |c| {
            c.load_all = load_all;
            c.backfill = window;
        })
    }

    /// Every frame a subscription from cursor 0 begun now is sent.
    fn replay(s: &Shared) -> Vec<Bytes> {
        s.events.get(s, 0, u64::MAX - 1, s.events.drops())
    }

    async fn put(s: &Shared, did: &str, token: &str, rkey: &str) -> String {
        let body = json!({ "repo": did, "collection": "a.b.c", "rkey": rkey, "record": record(1) });
        let put = call(s, "com.atproto.repo.putRecord", Some(token), body)
            .await
            .unwrap();
        put["commit"]["rev"].as_str().unwrap().to_string()
    }

    /// Every file under `dir`, by its path there, as it is now, but the
    /// journal's segments: what they hold is in the logs, as the system has
    /// them, so a test that cuts a log or the index cuts what a power cut
    /// leaves of a write no sync of the journal covered (`spec/DURABILITY.md`,
    /// "Writes waiting at once"), as `log`'s tests do.
    fn files(dir: &Path) -> BTreeMap<PathBuf, Vec<u8>> {
        let mut out = BTreeMap::new();
        let mut todo = vec![dir.to_path_buf()];
        while let Some(d) = todo.pop() {
            for e in std::fs::read_dir(&d).unwrap() {
                let p = e.unwrap().path();
                if p.is_dir() {
                    todo.push(p);
                } else {
                    let bytes = std::fs::read(&p).unwrap();
                    out.insert(p.strip_prefix(dir).unwrap().to_path_buf(), bytes);
                }
            }
        }
        out.retain(|p, _| !p.starts_with(pds_store::journal::DIR));
        out
    }

    /// Make `dir` hold `files`, and nothing else.
    fn put_files(dir: &Path, files: &BTreeMap<PathBuf, Vec<u8>>) {
        let _ = std::fs::remove_dir_all(dir);
        for (p, bytes) in files {
            let p = dir.join(p);
            std::fs::create_dir_all(p.parent().unwrap()).unwrap();
            std::fs::write(&p, bytes).unwrap();
        }
    }

    /// Whether a file of the data directory, by its path there, is the index's.
    fn of_index(p: &Path) -> bool {
        p.to_str().is_some_and(|p| p.starts_with("events."))
    }

    /// Wait until the event `seq` is known to be void and its account's
    /// announcement, if any, is on disk.
    fn announced(s: &Shared, seq: u64) {
        let until = Instant::now() + Duration::from_secs(30);
        while !(s.events.lock().voids.contains(&seq) && !s.events.owes()) {
            assert!(Instant::now() < until, "{seq} not found void");
            std::thread::sleep(POLL);
        }
    }

    /// The seqs of frames, in the order given.
    fn seqs(frames: &[Bytes]) -> Vec<u64> {
        frames.iter().map(|f| seq_of(f) as u64).collect()
    }

    /// After a kill and after a shutdown, a start learns the events made
    /// before it from the index alone: none of the accounts' files are read
    /// for it, nor any account loaded, and what it holds, and every frame a
    /// replay from cursor 0 is sent, are what the run before held and sent:
    /// an account's events in its table and in the log after it, and an
    /// event the service log holds.
    #[tokio::test]
    async fn a_start_learns_the_events_from_the_index() {
        let plc = plc().await;
        for load_all in [true, false] {
            for end in [End::Killed, End::ShutDown] {
                let what = format!("loading every account: {load_all}, {end:?}");
                let dir = scratch(&format!("index-learnt-{load_all}-{end:?}"));
                let s = serve(&dir, &plc, load_all, DAY);
                let (alice, ta) = create(&s, "alice").await;
                let (bob, tb) = create(&s, "bob").await;
                for n in 0..3 {
                    put(&s, &alice, &ta, &format!("r{n}")).await;
                    put(&s, &bob, &tb, &format!("r{n}")).await;
                }
                let wal = crate::read(&s.account(&alice).unwrap().store).wal.clone();
                wal.wait_compacted();
                wal.compact().unwrap();
                drop(wal);
                put(&s, &alice, &ta, "late").await;
                call(
                    &s,
                    "com.atproto.server.deactivateAccount",
                    Some(&tb),
                    json!({}),
                )
                .await
                .unwrap();
                let sent = replay(&s);
                assert_eq!(sent.len(), 2 * 4 + 2 * 3 + 2, "{what}");
                let held = s.events.holds().0;
                match end {
                    End::Killed => drop(s),
                    End::ShutDown => shut_down(s),
                }
                let s = serve(&dir, &plc, load_all, DAY);
                let loaded = crate::read(&s.directory).by_did.len();
                assert_eq!(loaded, if load_all { 2 } else { 0 }, "{what}");
                s.events.find_old();
                assert_eq!(crate::read(&s.directory).by_did.len(), loaded, "{what}");
                assert_eq!(s.events.scanned(), 0, "{what}");
                let found: Vec<_> = s
                    .events
                    .holds()
                    .0
                    .into_iter()
                    .map(|e| (e.0, e.1, e.2))
                    .collect();
                let want: Vec<_> = held.into_iter().map(|e| (e.0, e.1, e.2)).collect();
                assert_eq!(found, want, "{what}");
                let last = s.events.published();
                assert_eq!(s.events.last_made(last), sent.len() as u64, "{what}");
                assert_eq!(replay(&s), sent, "{what}");
                assert_eq!(s.events.scanned(), 0, "{what}");
                let _ = std::fs::remove_dir_all(&dir);
            }
        }
    }

    /// Killed once an event's entry was appended and before its frame
    /// was: a replay from before it skips it, sending the events around it
    /// in order, and no `#info` it would not otherwise have, though it is
    /// out of the window and the event after it is not, and though the
    /// index's compaction let go of the entries out of the window
    /// (`folded`), its among them, before the start; its seq is not given
    /// again. A cursor before an event the compaction let go is sent the
    /// `#info`.
    #[tokio::test]
    async fn killed_between_an_entry_and_its_frame() {
        const WINDOW: Duration = Duration::from_secs(3);
        let plc = plc().await;
        for (late, folded) in [(false, false), (true, false), (true, true)] {
            let dir = scratch(&format!("entry-alone-{late}-{folded}"));
            let window = if late { WINDOW } else { DAY };
            let s = serve(&dir, &plc, false, window);
            let (alice, ta) = create(&s, "alice").await;
            // More of alice's events than the compaction keeps of those
            // out of the window, where it lets go of them.
            let puts = if folded { UNSURE + 2 } else { 1 };
            for n in 0..puts {
                put(&s, &alice, &ta, &format!("r{n}")).await;
            }
            let before = s.events.published();
            let r = s.events.reserve(&alice, 1).unwrap();
            r.landing(Vec::new()).wait_entry().unwrap();
            let lost = r.seq;
            drop(r);
            let s = if late {
                drop(s);
                // Out of the window, and, where folded, of what a fold
                // keeps past it.
                let past = if folded { 2000 } else { 500 };
                tokio::time::sleep(WINDOW + Duration::from_millis(past)).await;
                serve(&dir, &plc, false, window)
            } else {
                s
            };
            let (bob, tb) = create(&s, "bob").await;
            put(&s, &bob, &tb, "r0").await;
            let after: Vec<u64> = s.events.seqs_of(&bob);
            assert!(after[0] > lost && after.len() == 5);
            if folded {
                let index = s.events.index().unwrap();
                assert!((0..10).any(|_| {
                    index.wait_compacted();
                    index.compact().is_ok()
                }));
                index.wait_compacted();
                let kept = index::checkpoint_seqs(&dir);
                assert!(!kept.contains(&1), "{kept:?}");
            }
            drop(s);
            let s = serve(&dir, &plc, false, window);
            let addr = serving(&s).await;
            let last = *after.last().unwrap();
            let mut sub = Sub::open(addr, lost - 1).await;
            assert_eq!(
                sub.until(last).await,
                after,
                "late: {late}, folded: {folded}"
            );
            if !late {
                let mut all = Sub::open(addr, 0).await;
                let want: Vec<u64> = (1..=before).chain(after.iter().copied()).collect();
                assert_eq!(all.until(last).await, want);
            }
            if folded {
                let mut outdated = Sub::open(addr, 1).await;
                let first = loop {
                    match outdated.message() {
                        Some((_, frame)) => break frame,
                        None => outdated.more().await,
                    }
                };
                assert_eq!(event(&first).0, "#info");
            }
            put(&s, &bob, &tb, "r1").await;
            assert!(s.events.published() > last);
            let _ = std::fs::remove_dir_all(&dir);
        }
    }

    /// A power cut that kept an account's frame of a write, as its log had
    /// it, in the log or folded into its table, and lost its entry, as the
    /// index's files were last synced, and with `together` the journal's
    /// records of the write: nothing of the account is lost, its record
    /// reads, and the write's event is never sent; once
    /// the account is used, an active one's announcement is, once, after
    /// every event before, as an activation's, its `#sync` of the
    /// repository as it is, and its next commit's event follows it, its
    /// `since` the write's rev; and so after a run that never used the
    /// account and shut down, where `between`. A second start that did not
    /// follow a shutdown announces nothing again. An account not active,
    /// nothing.
    async fn void_write(plc: &str, table: bool, active: bool, between: bool) {
        let what = format!("in its table: {table}, active: {active}, a run between: {between}");
        let dir = scratch(&format!("void-{table}-{active}-{between}"));
        let s = serve(&dir, plc, false, DAY);
        let (alice, ta) = create(&s, "alice").await;
        let (bob, tb) = create(&s, "bob").await;
        put(&s, &alice, &ta, "r0").await;
        put(&s, &bob, &tb, "r0").await;
        // Each entry so far was waited for: on disk.
        let synced: BTreeMap<PathBuf, Vec<u8>> = files(&dir)
            .into_iter()
            .filter(|(p, _)| of_index(p))
            .collect();
        let rev = put(&s, &alice, &ta, "r1").await;
        let void = s.events.published();
        if table {
            let wal = crate::read(&s.account(&alice).unwrap().store).wal.clone();
            wal.wait_compacted();
            wal.compact().unwrap();
        }
        if !active {
            call(
                &s,
                "com.atproto.server.deactivateAccount",
                Some(&ta),
                json!({}),
            )
            .await
            .unwrap();
        }
        let before = seqs(&replay(&s));
        drop(s);
        // The journal put back and let go, as a start does: the write's
        // records in it are lost with its entry, as a power cut leaves a
        // write no sync covered.
        redone(&dir);
        for p in files(&dir).keys().filter(|p| of_index(p)) {
            std::fs::remove_file(dir.join(p)).unwrap();
        }
        for (p, bytes) in &synced {
            std::fs::write(dir.join(p), bytes).unwrap();
        }
        if between {
            let s = serve(&dir, plc, false, DAY);
            crate::ops::sync_found(&s).unwrap();
            assert!(s.ctx.found.load(Ordering::SeqCst));
            shut_down(s);
        }
        let s = serve(&dir, plc, false, DAY);
        assert_eq!(s.ctx.durable, between, "{what}");
        let reads = |s: &Shared| store_of(s, &alice, |st| st.record("a.b.c/r1").is_some());
        // Loaded once the index is read, and before.
        if table {
            assert!(reads(&s), "{what}");
            s.events.find_old();
        } else {
            s.events.find_old();
            assert!(reads(&s), "{what}");
        }
        announced(&s, void);
        let sent = replay(&s);
        let got = seqs(&sent);
        let want: Vec<u64> = before.iter().copied().filter(|q| *q != void).collect();
        assert_eq!(got[..want.len()], want, "{what}");
        let made: Vec<(String, String)> = sent[want.len()..]
            .iter()
            .map(|f| {
                let (t, body) = event(f);
                assert_eq!(text(&body, "did").as_deref(), Some(alice.as_str()));
                (t, text(&body, "rev").unwrap_or_default())
            })
            .collect();
        if !active {
            assert!(made.is_empty(), "{what}: {made:?}");
        } else {
            assert_eq!(
                made,
                [
                    ("#account".to_string(), String::new()),
                    ("#identity".to_string(), String::new()),
                    ("#sync".to_string(), rev.clone())
                ],
                "{what}"
            );
            assert!(got[want.len()] > *before.last().unwrap(), "{what}");
            put(&s, &alice, &ta, "r2").await;
            let (t, body) = event(replay(&s).last().unwrap());
            assert_eq!((t.as_str(), text(&body, "since")), ("#commit", Some(rev)));
        }
        let sent = replay(&s);
        drop(s);
        let s = serve(&dir, plc, false, DAY);
        assert!(reads(&s), "{what}");
        s.events.find_old();
        std::thread::sleep(Duration::from_millis(300));
        assert!(!s.events.owes(), "{what}");
        assert_eq!(replay(&s), sent, "{what}: started again");
        let _ = std::fs::remove_dir_all(&dir);
    }

    #[tokio::test]
    async fn a_write_whose_entry_a_power_cut_lost() {
        let plc = plc().await;
        for sync in SYNCS {
            syncing(sync);
            for table in [false, true] {
                void_write(&plc, table, true, false).await;
            }
            void_write(&plc, false, false, false).await;
            void_write(&plc, false, true, true).await;
        }
    }

    /// The index's log cut short at every byte of its last entry, as a
    /// power cut may leave it: the start serves, and a replay sends every
    /// event before it; the entry's event, its frame in its account's log,
    /// only where the entry is whole.
    #[tokio::test]
    async fn the_index_cut_short_in_its_last_entry() {
        for sync in SYNCS {
            syncing(sync);
            the_index_cut_short_once().await;
        }
    }

    async fn the_index_cut_short_once() {
        let plc = plc().await;
        let dir = scratch("index-cut");
        let s = serve(&dir, &plc, false, DAY);
        let (alice, ta) = create(&s, "alice").await;
        create(&s, "bob").await;
        put(&s, &alice, &ta, "r").await;
        let sent = replay(&s);
        let last = s.events.published();
        drop(s);
        let whole = files(&dir);
        let log = index::layout(Path::new("")).log(0);
        let mut bytes = whole[&log].clone();
        bytes.truncate(bytes.iter().rposition(|&b| b != 0).unwrap() + 1);
        // Where the last frame begins.
        let mut start = 0;
        loop {
            let len = u32::from_le_bytes(bytes[start..start + 4].try_into().unwrap()) as usize;
            let end = start + pds_store::HEADER + len;
            if end == bytes.len() {
                break;
            }
            start = end;
        }
        let work = scratch("index-cut-work");
        for cut in start..=bytes.len() {
            let mut f = whole.clone();
            f.insert(log.clone(), bytes[..cut].to_vec());
            put_files(&work, &f);
            let s = serve(&work, &plc, false, DAY);
            let got = replay(&s);
            if cut == bytes.len() {
                assert_eq!(got, sent);
            } else {
                assert_eq!(
                    got[..sent.len() - 1],
                    sent[..sent.len() - 1],
                    "cut at {cut}"
                );
                assert!(!seqs(&got).contains(&last), "cut at {cut}");
                announced(&s, last);
            }
            drop(s);
        }
        let _ = std::fs::remove_dir_all(&dir);
        let _ = std::fs::remove_dir_all(&work);
    }

    /// The index compacted while events are made: every event of the
    /// window is sent, in order, after a start too, and those out of it are
    /// gone from its files, but the latest `UNSURE`.
    #[tokio::test(flavor = "multi_thread")]
    async fn the_index_compacted_as_events_are_made() {
        const WINDOW: Duration = Duration::from_secs(2);
        let plc = plc().await;
        let dir = scratch("index-compacted");
        let s = serve(&dir, &plc, false, WINDOW);
        let (alice, ta) = create(&s, "alice").await;
        for n in 0..=UNSURE {
            put(&s, &alice, &ta, &format!("old{n}")).await;
        }
        let old = s.events.published();
        // Out of the window, and of what a fold keeps past it.
        tokio::time::sleep(WINDOW + Duration::from_millis(1500)).await;
        let (bob, tb) = create(&s, "bob").await;
        let index = s.events.index().unwrap();
        let compacting = {
            let index = index.clone();
            tokio::task::spawn_blocking(move || {
                // Or one an append made due by its log's age.
                (0..10).any(|_| {
                    index.wait_compacted();
                    index.compact().is_ok()
                })
            })
        };
        for n in 0..5 {
            put(&s, &bob, &tb, &format!("r{n}")).await;
        }
        assert!(compacting.await.unwrap());
        index.wait_compacted();
        let kept = index::checkpoint_seqs(&dir);
        let unsure: Vec<u64> = kept.iter().copied().filter(|q| *q <= old).collect();
        assert!(kept.len() > unsure.len(), "{kept:?}");
        assert_eq!(
            unsure,
            (old + 1 - UNSURE as u64..=old).collect::<Vec<_>>(),
            "{kept:?}"
        );
        let made = s.events.seqs_of(&bob);
        assert_eq!(made.len(), 9);
        assert_eq!(seqs(&replay(&s)), made);
        drop(index);
        drop(s);
        let s = serve(&dir, &plc, false, WINDOW);
        assert_eq!(seqs(&replay(&s)), made, "started again");
        assert!(s.events.outdated(old - 1, s.events.published()));
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// The index's compaction killed at each step, with a write after its
    /// seal, as the generations' own are: every start recovers the events
    /// before the compaction, and the write after it where its entry is
    /// whole, its event void where it is not.
    #[tokio::test]
    async fn the_index_compaction_killed_at_every_step() {
        for sync in SYNCS {
            syncing(sync);
            the_index_compaction_killed_once().await;
        }
    }

    async fn the_index_compaction_killed_once() {
        let plc = plc().await;
        let dir = scratch("index-compaction-killed");
        let s = serve(&dir, &plc, false, DAY);
        let (alice, ta) = create(&s, "alice").await;
        let (bob, tb) = create(&s, "bob").await;
        put(&s, &alice, &ta, "r").await;
        put(&s, &bob, &tb, "r").await;
        let made = seqs(&replay(&s));
        let index = s.events.index().unwrap();
        let layout = index::layout(Path::new(""));
        index.wait_compacted();
        let g = index.generation();
        let before = files(&dir);
        index.compact().unwrap();
        assert_eq!(index.generation(), g + 1);
        let compacted = files(&dir);
        put(&s, &bob, &tb, "after").await;
        let written = s.events.published();
        let after = files(&dir);
        drop(index);
        drop(s);
        let (old_log, new_log, ckpt) = (layout.log(g), layout.log(g + 1), layout.checkpoint());
        let mut sealed = before[&old_log].clone();
        sealed.truncate(sealed.iter().rposition(|&b| b != 0).map_or(0, |e| e + 1));
        sealed.extend(pds_store::frame(&[json!({ "t": "seal" })]));
        let mut next = after[&new_log].clone();
        next.truncate(next.iter().rposition(|&b| b != 0).map_or(0, |e| e + 1));
        let base: BTreeMap<PathBuf, Vec<u8>> = after
            .iter()
            .filter(|(p, _)| ![&old_log, &new_log, &ckpt].contains(p))
            .map(|(p, b)| (p.clone(), b.clone()))
            .collect();
        let with = |logs: &[(&PathBuf, &[u8])]| {
            let mut f = base.clone();
            if let Some(c) = before.get(&ckpt) {
                f.insert(ckpt.clone(), c.clone());
            }
            for (p, b) in logs {
                f.insert((*p).clone(), b.to_vec());
            }
            f
        };
        let work = scratch("index-compaction-killed-work");
        let check = |files: BTreeMap<PathBuf, Vec<u8>>, why: String, whole: bool| {
            put_files(&work, &files);
            let s = serve(&work, &plc, false, DAY);
            let got = seqs(&replay(&s));
            assert_eq!(got[..made.len()], made, "{why}");
            assert_eq!(got.contains(&written), whole, "{why}");
            if !whole {
                announced(&s, written);
            }
        };
        for cut in 0..pds_store::frame(&[json!({ "t": "seal" })]).len() {
            let at = sealed.len() - pds_store::frame(&[json!({ "t": "seal" })]).len() + cut;
            check(
                with(&[(&old_log, &sealed[..at])]),
                format!("the seal cut at {cut}"),
                false,
            );
        }
        check(
            with(&[(&old_log, &sealed)]),
            "sealed, no next log".into(),
            false,
        );
        for cut in 0..=next.len() {
            let whole = cut == next.len();
            check(
                with(&[(&old_log, &sealed), (&new_log, &next[..cut])]),
                format!("the next log cut at {cut}"),
                whole,
            );
            if cut == 0 || whole {
                let bytes = &compacted[&ckpt];
                for at in (0..bytes.len()).step_by((bytes.len() / 7).max(1)) {
                    let mut f = with(&[(&old_log, &sealed), (&new_log, &next[..cut])]);
                    f.insert(layout.tmp(), bytes[..at].to_vec());
                    check(
                        f,
                        format!("the .tmp cut at {at}, the next log at {cut}"),
                        whole,
                    );
                }
                let mut f = with(&[(&old_log, &sealed), (&new_log, &next[..cut])]);
                f.insert(ckpt.clone(), bytes.clone());
                check(f.clone(), format!("renamed, the next log at {cut}"), whole);
                f.remove(&old_log);
                check(
                    f,
                    format!("the old log deleted, the next log at {cut}"),
                    whole,
                );
            }
        }
        let _ = std::fs::remove_dir_all(&dir);
        let _ = std::fs::remove_dir_all(&work);
    }

    /// An account deleted: after a restart, after a kill or a shutdown, a
    /// subscription is sent none of its events but its deletion's, and
    /// every other account's.
    #[tokio::test]
    async fn a_deleted_accounts_events_are_not_sent_after_a_restart() {
        let plc = plc().await;
        for end in [End::Killed, End::ShutDown] {
            let dir = scratch(&format!("index-deleted-{end:?}"));
            let sink = scratch(&format!("index-deleted-{end:?}-mail"));
            std::fs::create_dir_all(&sink).unwrap();
            let start = |dir: &Path| {
                open_with(dir, &plc, |c| {
                    c.load_all = false;
                    c.mailer = crate::email::Mailer::sink(&sink);
                })
            };
            let s = start(&dir);
            let (alice, ta) = create(&s, "alice").await;
            let (bob, tb) = create(&s, "bob").await;
            put(&s, &alice, &ta, "r").await;
            put(&s, &bob, &tb, "r").await;
            call(
                &s,
                "com.atproto.server.requestAccountDelete",
                Some(&ta),
                Json::Null,
            )
            .await
            .unwrap();
            let token = crate::email::testing::last_token(&sink);
            let body = json!({ "did": alice, "password": "alice-pw", "token": token });
            call(&s, "com.atproto.server.deleteAccount", None, body)
                .await
                .unwrap();
            put(&s, &bob, &tb, "after").await;
            // Bob's, and the deletion's.
            let sent = replay(&s);
            assert_eq!(sent.len(), 4 + 2 + 1);
            match end {
                End::Killed => drop(s),
                End::ShutDown => shut_down(s),
            }
            let s = start(&dir);
            assert_eq!(replay(&s), sent, "{end:?}");
            assert_eq!(s.events.seqs_of(&alice).len(), 1, "{end:?}");
            let (t, body) = event(&sent[sent.len() - 2]);
            assert_eq!(
                (t.as_str(), text(&body, "status")),
                ("#account", Some("deleted".to_string()))
            );
            for d in [&dir, &sink] {
                let _ = std::fs::remove_dir_all(d);
            }
        }
    }

    /// A data directory with accounts and no index, as the version before
    /// left it, with its file of the events a shutdown left, killed or shut
    /// down: the first start makes the index of every account's files before
    /// it serves, and removes that file, and serves every event; the next
    /// reads no account for them.
    #[tokio::test]
    async fn a_data_directory_with_no_index() {
        let plc = plc().await;
        for end in [End::Killed, End::ShutDown] {
            let dir = scratch(&format!("no-index-{end:?}"));
            let s = serve(&dir, &plc, false, DAY);
            let (alice, ta) = create(&s, "alice").await;
            let (bob, tb) = create(&s, "bob").await;
            put(&s, &alice, &ta, "r").await;
            put(&s, &bob, &tb, "r").await;
            call(
                &s,
                "com.atproto.server.deactivateAccount",
                Some(&tb),
                json!({}),
            )
            .await
            .unwrap();
            let sent = replay(&s);
            match end {
                End::Killed => drop(s),
                End::ShutDown => shut_down(s),
            }
            // The version before kept no journal either: what this run's
            // holds is put back and let go before its index is taken away.
            redone(&dir);
            for p in files(&dir).keys().filter(|p| of_index(p)) {
                std::fs::remove_file(dir.join(p)).unwrap();
            }
            std::fs::write(dir.join("events.index"), b"left").unwrap();
            let s = serve(&dir, &plc, false, DAY);
            assert_eq!(s.events.scanned(), 2, "{end:?}");
            assert!(!dir.join("events.index").exists() && index::exists(&dir));
            assert_eq!(replay(&s), sent, "{end:?}");
            match end {
                End::Killed => drop(s),
                End::ShutDown => shut_down(s),
            }
            let s = serve(&dir, &plc, false, DAY);
            s.events.find_old();
            assert_eq!(s.events.scanned(), 0, "{end:?}");
            assert!(crate::read(&s.directory).by_did.is_empty(), "{end:?}");
            assert_eq!(replay(&s), sent, "{end:?}");
            let _ = std::fs::remove_dir_all(&dir);
        }
    }

    /// How a run ends: killed, leaving what its logs hold, or shut down in
    /// order, leaving the index of its events too if it knows them all.
    #[derive(Clone, Copy, Debug, PartialEq)]
    enum End {
        Killed,
        ShutDown,
    }

    /// How a data directory's runs end, one after another, over and over.
    const ENDS: [[End; 2]; 4] = [
        [End::Killed, End::Killed],
        [End::ShutDown, End::ShutDown],
        [End::ShutDown, End::Killed],
        [End::Killed, End::ShutDown],
    ];

    /// A data directory over its runs, and every event made in it.
    struct History {
        dir: PathBuf,
        plc: String,
        load_all: bool,
        ends: [End; 2],
        /// How many runs have ended.
        ended: usize,
        /// The seq of every event made, in order.
        made: Vec<u64>,
        /// The accounts made, by DID, and the first one's token.
        dids: Vec<String>,
        token: String,
    }

    impl History {
        fn new(name: &str, plc: &str, load_all: bool, ends: [End; 2]) -> History {
            History {
                dir: scratch(name),
                plc: plc.to_string(),
                load_all,
                ends,
                ended: 0,
                made: Vec::new(),
                dids: Vec::new(),
                token: String::new(),
            }
        }

        fn start(&self) -> Shared {
            serve(&self.dir, &self.plc, self.load_all, DAY)
        }

        /// End a run as its turn says.
        fn end(&mut self, s: Shared) {
            match self.ends[self.ended % 2] {
                End::Killed => drop(s),
                End::ShutDown => shut_down(s),
            }
            self.ended += 1;
        }

        /// Make an account, and write a record of the first one's: five
        /// events, which take the next seqs.
        async fn write(&mut self, s: &Shared) {
            let next = s.events.lock().next;
            let (did, token) = create(s, &format!("made{}", self.dids.len())).await;
            if self.dids.is_empty() {
                self.token = token;
            }
            self.dids.push(did);
            let rkey = format!("r{}", self.made.len());
            put(s, &self.dids[0], &self.token, &rkey).await;
            self.made.extend(next..next + 5);
        }

        /// The seq of the last event made.
        fn last(&self) -> u64 {
            *self.made.last().unwrap()
        }

        /// A subscription from cursor 0 begun now is sent every event made,
        /// the run's own too, in order of seq, none twice.
        fn replays(&self, s: &Shared, what: &str) {
            assert_eq!(seqs(&replay(s)), self.made, "{what}");
        }

        /// The run having numbered an event, subscribers may be sent events
        /// up to the last made, and that is the last event's seq.
        fn published(&self, s: &Shared, what: &str) {
            let published = s.events.published();
            assert_eq!(published, self.last(), "{what}");
            assert_eq!(s.events.last_made(published), self.last(), "{what}");
        }

        /// The events made are those the accounts' stores hold.
        fn stored(&self, s: &Shared, what: &str) {
            let mut held: Vec<u64> = self
                .dids
                .iter()
                .flat_map(|did| s.account(did).unwrap().store.events().0)
                .map(|e| e.0)
                .collect();
            held.sort_unstable();
            assert_eq!(held, self.made, "{what}");
        }
    }

    /// What subscribers may be sent events up to as a run starts, and the
    /// seqs its first events take. The first start: 0, and they are numbered
    /// from 1. A start that reads no account's log, after a kill or a
    /// shutdown: the greatest seq reserved, past the last event's, and they
    /// follow it. A start that reads every account's log: the last event's
    /// seq, and they follow that, below the seqs reserved. From a run's
    /// first event on, it is the last event's seq. Seqs are reserved anew
    /// only past every seq reserved before.
    #[tokio::test]
    async fn what_a_start_publishes() {
        let plc = plc().await;
        for load_all in [true, false] {
            for (i, ends) in ENDS.into_iter().enumerate() {
                let what = format!("loading every account: {load_all}, ending {ends:?}");
                let mut h =
                    History::new(&format!("published-{load_all}-{i}"), &plc, load_all, ends);
                let s = h.start();
                assert_eq!((s.events.published(), s.events.lock().next), (0, 1));
                h.write(&s).await;
                assert_eq!(h.made, [1, 2, 3, 4, 5]);
                h.published(&s, &what);
                let mut reserved = s.events.lock().ceiling;
                assert_eq!(reserved, 4 + RESERVE);
                h.end(s);
                for _ in 0..3 {
                    let s = h.start();
                    let from = if load_all { h.last() } else { reserved };
                    let (next, ceiling) = {
                        let q = s.events.lock();
                        (q.next, q.ceiling)
                    };
                    assert_eq!(
                        (s.events.published(), next, ceiling),
                        (from, from + 1, reserved),
                        "{what}"
                    );
                    // The last event made is known once those before the
                    // start are found: no seq reserved past it is one's.
                    s.events.find_old();
                    assert_eq!(s.events.last_made(from), h.last(), "{what}");
                    assert_eq!(s.events.published(), from, "{what}");
                    h.write(&s).await;
                    h.published(&s, &what);
                    let sent = seqs(&replay(&s));
                    assert_eq!(sent, h.made, "{what}");
                    assert_eq!(
                        sent[sent.len() - 5..],
                        (from + 1..=from + 5).collect::<Vec<_>>(),
                        "{what}"
                    );
                    let q = s.events.lock();
                    let want = if from + 4 > reserved {
                        from + 4 + RESERVE
                    } else {
                        reserved
                    };
                    assert_eq!(q.ceiling, want, "{what}");
                    reserved = q.ceiling;
                    drop(q);
                    h.end(s);
                }
                let _ = std::fs::remove_dir_all(&h.dir);
            }
        }
    }

    /// When a run looks for the events made before its start.
    #[derive(Clone, Copy, Debug, PartialEq)]
    enum Find {
        /// In the index, before it numbers an event.
        IndexFirst,
        /// In the index, after its first events.
        IndexAfter,
        /// On a subscriber's need alone, after its first events.
        Needed,
        /// Never: it ends without having looked.
        Never,
    }

    /// Runs of a data directory, each ending as `ends` says and looking for
    /// the events before its start as `find` says, with `idle` runs that
    /// number no event before each that does: whenever a run looks, a
    /// subscription from cursor 0 is sent every event made, its own too, and
    /// what is published is its last event's seq.
    async fn runs(plc: String, load_all: bool, pattern: usize, idle: usize, find: Find) {
        let what = format!(
            "loading every account: {load_all}, ending {:?}, {idle} runs with no event, finding {find:?}",
            ENDS[pattern]
        );
        let name = format!("runs-{load_all}-{pattern}-{idle}-{find:?}");
        let mut h = History::new(&name, &plc, load_all, ENDS[pattern]);
        let s = h.start();
        h.write(&s).await;
        h.published(&s, &what);
        h.replays(&s, &what);
        h.end(s);
        for _ in 0..3 {
            for _ in 0..idle {
                let s = h.start();
                match find {
                    Find::IndexFirst | Find::IndexAfter => s.events.find_old(),
                    Find::Needed => h.replays(&s, &what),
                    Find::Never => {}
                }
                h.end(s);
            }
            let s = h.start();
            if find == Find::IndexFirst {
                s.events.find_old();
            }
            h.write(&s).await;
            h.published(&s, &what);
            if find == Find::IndexAfter {
                s.events.find_old();
            }
            if find != Find::Never {
                h.replays(&s, &what);
                h.published(&s, &what);
            }
            h.end(s);
        }
        let s = h.start();
        h.replays(&s, &what);
        h.stored(&s, &what);
        let _ = std::fs::remove_dir_all(&h.dir);
    }

    /// Every kind of start, after kills, shutdowns and both in turn, loading
    /// every account or none, with events numbered before the events of
    /// before the start are found or after, and after runs that numbered
    /// none: a subscription from cursor 0 is sent every event made.
    #[tokio::test(flavor = "multi_thread")]
    async fn every_start_replays_every_event() {
        let plc = plc().await;
        let mut all = Vec::new();
        for load_all in [true, false] {
            for pattern in 0..ENDS.len() {
                for idle in [0, 3] {
                    for find in [
                        Find::IndexFirst,
                        Find::IndexAfter,
                        Find::Needed,
                        Find::Never,
                    ] {
                        all.push(tokio::spawn(runs(
                            plc.clone(),
                            load_all,
                            pattern,
                            idle,
                            find,
                        )));
                    }
                }
            }
        }
        for run in all {
            run.await.unwrap();
        }
    }

    /// The index is read while the run's first events are numbered and
    /// land, whichever comes first: what is held is in order throughout,
    /// and then the events indexed and the run's own, each once; what is
    /// published is the last one's seq. As after a start that read no
    /// account's log, numbering on from the seqs reserved, and one that
    /// read every one's, numbering on from the last event.
    #[test]
    fn the_index_is_read_as_events_are_numbered() {
        let dir = scratch("events-raced");
        std::fs::create_dir_all(&dir).unwrap();
        let (log, _) = pds_store::Wal::open(&dir.join("seqs.log"), None).unwrap();
        let log = Arc::new(log);
        let event = |f: &Firehose, did: &str| {
            let r = f.reserve(did, 1).unwrap();
            f.land(r.landing(landing(r.seq).frames));
            r.seq
        };
        let held = |f: &Firehose| f.holds().0.iter().map(|e| e.0).collect::<Vec<u64>>();
        // A run that numbered six events.
        let f = Firehose::new(vec![], HashSet::new(), 0, 0, DAY, log.clone(), at(&dir));
        let mut old: Vec<u64> = (0..6)
            .map(|i| event(&f, &format!("did:plc:{}", i % 3)))
            .collect();
        assert!(f.seal());
        f.close_index().unwrap();
        let mut reserved = f.lock().ceiling;
        drop(f);
        for round in 0..150 {
            let exact = round % 2 == 1;
            let f = Firehose::new(
                vec![],
                HashSet::new(),
                reserved,
                0,
                DAY,
                log.clone(),
                at(&dir),
            );
            let last = *old.last().unwrap();
            if exact {
                f.exact(last);
            }
            let first = f.lock().next;
            assert_eq!(first, if exact { last } else { reserved } + 1);
            let go = std::sync::Barrier::new(3);
            std::thread::scope(|t| {
                t.spawn(|| {
                    go.wait();
                    f.find_old();
                });
                t.spawn(|| {
                    go.wait();
                    for _ in 0..3 {
                        event(&f, "did:plc:new");
                    }
                });
                t.spawn(|| {
                    go.wait();
                    for _ in 0..200 {
                        let seqs = held(&f);
                        assert!(seqs.windows(2).all(|w| w[0] < w[1]), "{seqs:?}");
                        assert!(f.published() >= first - 1);
                    }
                });
            });
            let new: Vec<u64> = (first..first + 3).collect();
            assert_eq!(
                held(&f),
                [old.clone(), new.clone()].concat(),
                "round {round}"
            );
            assert_eq!(f.published(), first + 2, "round {round}");
            assert_eq!(f.last_made(first + 2), first + 2, "round {round}");
            assert_eq!(f.holds().1, 0, "round {round}");
            old.extend(new);
            reserved = f.lock().ceiling;
        }
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// The events before a start are looked for, in the index as the server
    /// does once it serves and by a subscriber from cursor 0, each at once,
    /// as soon as the run has numbered an event, or as soon as one of its
    /// events has landed, while the run's first writes go on: the
    /// subscriber is sent the events made so far with none missing, and one
    /// begun once the writes are answered, every event made.
    #[tokio::test(flavor = "multi_thread")]
    async fn found_as_a_runs_first_events_are_numbered() {
        /// Wait, if `when` is 1, until the run has numbered an event, `next`
        /// the seq its first takes; if 2, until one has landed, `published`
        /// what was as it started; else not at all.
        fn until(s: &Shared, when: u64, next: u64, published: u64) {
            let give_up = Instant::now() + Duration::from_secs(30);
            while Instant::now() < give_up
                && match when {
                    1 => s.events.lock().next == next,
                    2 => s.events.published() == published,
                    _ => false,
                }
            {
                std::thread::yield_now();
            }
        }
        let plc = plc().await;
        let run = |load_all: bool, pattern: usize| {
            let plc = plc.clone();
            async move {
                let what = format!(
                    "loading every account: {load_all}, ending {:?}",
                    ENDS[pattern]
                );
                let name = format!("raced-{load_all}-{pattern}");
                let mut h = History::new(&name, &plc, load_all, ENDS[pattern]);
                let s = h.start();
                h.write(&s).await;
                h.end(s);
                for round in 0..9 {
                    let s = h.start();
                    let (next, published) = (s.events.lock().next, s.events.published());
                    let index = {
                        let s = s.clone();
                        tokio::task::spawn_blocking(move || {
                            until(&s, round % 3, next, published);
                            s.events.find_old();
                        })
                    };
                    let sent = {
                        let s = s.clone();
                        tokio::task::spawn_blocking(move || {
                            until(&s, round / 3, next, published);
                            seqs(&replay(&s))
                        })
                    };
                    h.write(&s).await;
                    index.await.unwrap();
                    let sent = sent.await.unwrap();
                    assert_eq!(sent, h.made[..sent.len()], "{what}, round {round}");
                    assert!(sent.len() + 5 >= h.made.len(), "{what}, round {round}");
                    h.published(&s, &what);
                    h.replays(&s, &what);
                    h.end(s);
                }
                let s = h.start();
                h.replays(&s, &what);
                h.stored(&s, &what);
                let _ = std::fs::remove_dir_all(&h.dir);
            }
        };
        let mut all = Vec::new();
        for load_all in [true, false] {
            for pattern in 0..ENDS.len() {
                all.push(tokio::spawn(run(load_all, pattern)));
            }
        }
        for run in all {
            run.await.unwrap();
        }
    }

    /// The server on a port of its own, as `pds serve` runs it.
    async fn serving(s: &Shared) -> std::net::SocketAddr {
        let listener = tokio::net::TcpListener::bind(("127.0.0.1", 0))
            .await
            .unwrap();
        let addr = listener.local_addr().unwrap();
        tokio::spawn(crate::limits::serve(
            listener,
            crate::router(s.clone()),
            std::future::pending::<()>(),
        ));
        addr
    }

    /// A subscription over a socket: what `subscribeRepos` sends a client.
    struct Sub {
        socket: tokio::net::TcpStream,
        /// What is read of it and not yet taken.
        read: Vec<u8>,
    }

    impl Sub {
        /// How long an event is waited for before the subscription is taken to have stopped.
        const WAIT: Duration = Duration::from_secs(30);

        /// Subscribe at `addr` from `cursor`.
        async fn open(addr: std::net::SocketAddr, cursor: u64) -> Sub {
            use tokio::io::AsyncWriteExt;
            let mut socket = tokio::net::TcpStream::connect(addr).await.unwrap();
            let request = format!(
                "GET /xrpc/com.atproto.sync.subscribeRepos?cursor={cursor} HTTP/1.1\r\nhost: x\r\nupgrade: websocket\r\nconnection: Upgrade\r\nsec-websocket-key: dGhlIHNhbXBsZSBub25jZQ==\r\nsec-websocket-version: 13\r\n\r\n"
            );
            socket.write_all(request.as_bytes()).await.unwrap();
            let mut sub = Sub {
                socket,
                read: Vec::new(),
            };
            let head = loop {
                if let Some(end) = sub.read.windows(4).position(|w| w == b"\r\n\r\n") {
                    break sub.read.drain(..end + 4).collect::<Vec<u8>>();
                }
                sub.more().await;
            };
            let head = String::from_utf8_lossy(&head);
            assert!(head.starts_with("HTTP/1.1 101"), "{head}");
            sub
        }

        async fn more(&mut self) {
            use tokio::io::AsyncReadExt;
            let n = self.socket.read_buf(&mut self.read).await.unwrap();
            assert!(n > 0, "the subscription was closed");
        }

        /// The next message read whole, taken: its opcode and what it holds.
        fn message(&mut self) -> Option<(u8, Vec<u8>)> {
            let [first, second, ..] = self.read[..] else {
                return None;
            };
            let (head, len) = match second & 0x7f {
                126 => (
                    4,
                    u16::from_be_bytes(self.read.get(2..4)?.try_into().ok()?) as usize,
                ),
                127 => (
                    10,
                    u64::from_be_bytes(self.read.get(2..10)?.try_into().ok()?) as usize,
                ),
                n => (2, n as usize),
            };
            if self.read.len() < head + len {
                return None;
            }
            let body = self.read[head..head + len].to_vec();
            self.read.drain(..head + len);
            Some((first & 0x0f, body))
        }

        /// The seq of the next event it is sent: given up while it waits,
        /// nothing read is lost.
        async fn next(&mut self) -> u64 {
            loop {
                match self.message() {
                    Some((2, frame)) => return seq_of(&frame) as u64,
                    Some((op, body)) => panic!("sent a message of opcode {op}: {body:?}"),
                    None => self.more().await,
                }
            }
        }

        /// The seqs of the events it is sent, up to the event `last`.
        async fn until(&mut self, last: u64) -> Vec<u64> {
            let mut got = Vec::new();
            while got.last() != Some(&last) {
                match tokio::time::timeout(Sub::WAIT, self.next()).await {
                    Ok(seq) => got.push(seq),
                    Err(_) => panic!("sent {got:?}, then nothing, before {last}"),
                }
            }
            got
        }

        /// Whether it is sent nothing for `time`.
        async fn quiet(&mut self, time: Duration) -> bool {
            tokio::time::timeout(time, self.next()).await.is_err()
        }
    }

    /// A relay's subscription from cursor 0, opened as soon as a run's first
    /// writes are answered, on a data directory several runs have used,
    /// while the server looks for the index as it does once it serves: it
    /// is sent every event made, the run's own last, each once and in
    /// order, and what is published is the last one's seq; then each event
    /// made from then on.
    #[tokio::test(flavor = "multi_thread")]
    async fn a_subscription_begun_as_a_runs_first_events_land() {
        let plc = plc().await;
        for load_all in [true, false] {
            for (pattern, ends) in ENDS.iter().copied().enumerate() {
                let what = format!("loading every account: {load_all}, ending {ends:?}");
                let name = format!("subscribed-{load_all}-{pattern}");
                let mut h = History::new(&name, &plc, load_all, ends);
                let s = h.start();
                for _ in 0..3 {
                    h.write(&s).await;
                }
                h.end(s);
                let s = h.start();
                h.end(s);
                let s = h.start();
                h.write(&s).await;
                h.end(s);
                let s = h.start();
                let addr = serving(&s).await;
                find_soon(&s);
                h.write(&s).await;
                let mut sub = Sub::open(addr, 0).await;
                assert_eq!(sub.until(h.last()).await, h.made, "{what}");
                h.published(&s, &what);
                assert!(sub.quiet(Duration::from_millis(200)).await, "{what}");
                let before = h.made.len();
                h.write(&s).await;
                assert_eq!(sub.until(h.last()).await, h.made[before..], "{what}");
                h.published(&s, &what);
                // One from the run's first event is sent the rest; one from
                // the last, nothing.
                let mut rest = Sub::open(addr, h.made[before - 5]).await;
                assert_eq!(rest.until(h.last()).await, h.made[before - 4..], "{what}");
                let mut none = Sub::open(addr, h.last()).await;
                assert!(none.quiet(Duration::from_millis(200)).await, "{what}");
                let _ = std::fs::remove_dir_all(&h.dir);
            }
        }
    }

    /// More accounts than logs are held open at once, made ten at a time in
    /// a run that is killed; some of them written to and more made in a
    /// second, killed too; then an account and a record in a third, and at
    /// once a subscription from cursor 0, while the server looks for the
    /// index: it is sent every event the accounts' stores hold, in order,
    /// each once, up to the last published, the record's.
    #[tokio::test(flavor = "multi_thread")]
    async fn a_subscription_over_many_accounts() {
        let plc = plc().await;
        let dir = scratch("subscribed-many");
        let start = || serve(&dir, &plc, false, DAY);
        let s = start();
        let mut accounts = Vec::new();
        for i in 0..8 {
            let made: Vec<_> = (0..10)
                .map(|j| {
                    let s = s.clone();
                    tokio::spawn(async move { create(&s, &format!("many{}", i * 10 + j)).await })
                })
                .collect();
            for m in made {
                accounts.push(m.await.unwrap());
            }
        }
        assert!(accounts.len() > s.config.share);
        drop(s);
        let s = start();
        for i in [0, 1, 78, 79] {
            put(&s, &accounts[i].0, &accounts[i].1, "r").await;
        }
        for i in 80..85 {
            accounts.push(create(&s, &format!("many{i}")).await);
        }
        drop(s);
        let s = start();
        let addr = serving(&s).await;
        find_soon(&s);
        let (did, token) = create(&s, "many85").await;
        put(&s, &did, &token, "r").await;
        accounts.push((did, token));
        let last = s.events.published();
        let mut sub = Sub::open(addr, 0).await;
        let got = sub.until(last).await;
        assert!(sub.quiet(Duration::from_millis(200)).await);
        let mut held: Vec<u64> = accounts
            .iter()
            .flat_map(|(did, _)| s.account(did).unwrap().store.events().0)
            .map(|e| e.0)
            .collect();
        held.sort_unstable();
        assert_eq!(held.len(), 86 * 4 + 5);
        assert_eq!(got, held);
        assert_eq!(held.last(), Some(&last));
        assert_eq!(
            (s.events.published(), s.events.last_made(last)),
            (last, last)
        );
        let _ = std::fs::remove_dir_all(&dir);
    }

    /// A subscription's replay sends each event in its turn, reading it
    /// from its account's store: while one store cannot be read, as while
    /// its load waits for the disk, nothing after its event is sent, the
    /// run's own events neither, though they are published. A second with
    /// nothing sent is no end of the replay: once the store is read, every
    /// event follows, in order.
    #[tokio::test(flavor = "multi_thread")]
    async fn a_replay_sends_each_event_in_its_turn() {
        let plc = plc().await;
        let mut h = History::new("replay-in-turn", &plc, false, [End::Killed; 2]);
        let s = h.start();
        h.write(&s).await;
        // The first account's events fill a batch: they are sent before the
        // next account's store is read.
        for n in 0..4 {
            let next = s.events.lock().next;
            let record = json!({ "$type": "a.b.c", "text": "x".repeat(300_000) });
            let body = json!({ "repo": h.dids[0], "collection": "a.b.c", "rkey": format!("big{n}"), "record": record });
            call(&s, "com.atproto.repo.putRecord", Some(&h.token), body)
                .await
                .unwrap();
            h.made.push(next);
        }
        let first = h.made.len();
        assert!(replay(&s).iter().map(|f| f.len()).sum::<usize>() >= BATCH);
        h.write(&s).await;
        h.end(s);
        let s = h.start();
        let addr = serving(&s).await;
        h.write(&s).await;
        s.events.find_old();
        // The second account's store, held as a load of it holds it.
        let second = s.account(&h.dids[1]).unwrap();
        let (held, holding) = std::sync::mpsc::channel();
        let (release, released) = std::sync::mpsc::channel::<()>();
        let holder = std::thread::spawn(move || {
            let store = crate::write(&second.store);
            held.send(()).unwrap();
            let _ = released.recv();
            drop(store);
        });
        holding.recv().unwrap();
        let mut sub = Sub::open(addr, 0).await;
        let mut got = sub.until(h.made[first - 1]).await;
        assert!(sub.quiet(Duration::from_secs(1)).await);
        assert_eq!(got, h.made[..first]);
        h.published(&s, "as the replay waits");
        release.send(()).unwrap();
        holder.join().unwrap();
        got.extend(sub.until(h.last()).await);
        assert_eq!(got, h.made);
        let _ = std::fs::remove_dir_all(&h.dir);
    }
}