~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
1629 lines · 57.5 KB Raw History
//! Write notifications, the writer set and syncers, as `spec/SPACES-SYNC.md`
//! says: the repo host telling a space's host of each commit of a space repo
//! here (`notifyRepoUpdate`, sent, and retried); the space host taking those
//! notifications into the writer set (`notifyRepoUpdate`, served), taking
//! writers out of it (`remove_writers`) and serving it (`listWriters`); and
//! syncers' registrations, made by `authorizeSpaceSync` and confirmed with
//! `confirmRegistration`, each told of every change of the writer set, of
//! its expiry and of the space's deletion (`notifySpaceUpdate`, sent; the
//! expiry and deletion notices retried).
//!
//! What this part keeps is each account's, in its `repo.log` (`ENTRIES`),
//! changed under its lock: a writer's notifications that failed for now
//! (the retry queue, at most one per space, the latest commit's), and an
//! authority's registrations and the notices it keeps to send again (the
//! notice queue, at most one per registration). A change is applied as its
//! entry says, so that replaying the log makes the same. The writer set is
//! kept with its space (`space_authority`), and changed by this part alone:
//! its entries are logged here, in the same frame as what the change owes
//! the registrations.
//!
//! Sending is in the background, at most `IN_FLIGHT` at once, with no lock
//! held across a send: an attempt is marked as being sent, made, and then
//! settled under its account's lock. One scheduler (`start`) sends retries
//! when due, from hints of when each account next has one; a hint is
//! checked against what the account keeps when it comes.

use crate::space_authority::{Space, Status, Writer, status, writer_removed, writer_tracked};
use crate::space_authz::{Lifecycle, SpaceState, endpoint, service_auth};
use crate::space_credentials::{presents_credential, verify_space_credential};
use crate::{
    Account, Call, Handler, Resp, Service, Shared, Store, XrpcError, durable, err, invalid, read,
    required, write,
};
use pds_lexicon::Method;
use pds_repo::data::{V, from_json, to_json};
use pds_repo::valid_tid;
use pds_space::{Commit, SpaceRef};
use pds_store::Wal;
use serde_json::{Value as Json, json};
use std::collections::{BTreeMap, BTreeSet, HashSet};
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
use std::time::{Duration, SystemTime, UNIX_EPOCH};
use tokio::sync::Semaphore;
use tokio::task::JoinHandle;

/// The kinds of `repo.log` entry this part keeps, each naming its space by
/// `space`.
pub(crate) const ENTRIES: &[&str] = &[
    QUEUED,
    UNQUEUED,
    REGISTERED,
    DROPPED,
    NOTICED,
    EMPTIED,
    NOTICE,
    NOTICE_DONE,
];
/// A notification kept to be sent again, replacing any of its space.
const QUEUED: &str = "notifyQueued";
/// The notification of its space taken out, if its `rev` is not later.
const UNQUEUED: &str = "notifyUnqueued";
/// A registration made or renewed, to lapse at `expires`.
const REGISTERED: &str = "syncRegistered";
/// A registration dropped.
const DROPPED: &str = "syncDropped";
/// A lapsed registration sent its expiry notice.
const NOTICED: &str = "syncNoticed";
/// Every registration of a deleted space dropped.
const EMPTIED: &str = "syncEmptied";
/// A notice kept in the notice queue, in place of any of its registration.
const NOTICE: &str = "syncNotice";
/// A registration's notice taken out of the notice queue.
const NOTICE_DONE: &str = "syncNoticeDone";

pub(crate) const NOTIFY_REPO_UPDATE: &str = "com.atproto.space.notifyRepoUpdate";
const LIST_WRITERS: &str = "com.atproto.space.listWriters";
const NOTIFY_SPACE_UPDATE: &str = "com.atproto.space.notifySpaceUpdate";
const CONFIRM: &str = "com.atproto.space.confirmRegistration";
/// The updates' and notices' types.
const REPO_WRITE: &str = "com.atproto.space.defs#repoWrite";
const REPO_REMOVED: &str = "com.atproto.space.defs#repoRemoved";
const SPACE_DELETED: &str = "com.atproto.space.notifySpaceUpdate#spaceDeleted";
const EXPIRED: &str = "com.atproto.space.notifySpaceUpdate#registrationExpired";

/// Times, in milliseconds.
const MINUTE: u64 = 60_000;
const HOUR: u64 = 60 * MINUTE;
/// A notification not delivered this long after its commit is dropped.
const HORIZON: u64 = 24 * HOUR;
/// A notice that fails for now this long after it was kept is given up.
const NOTICE_HORIZON: u64 = 72 * HOUR;
/// The delay before each retry of a notice, in seconds: the fifth's for
/// every one after.
const NOTICE_DELAYS: [u64; 5] = [60, 600, 3600, 21600, 43200];
/// The most active registrations a space has.
pub(crate) const SPACE_REGISTRATIONS: usize = 64;
/// How far ahead of now a notified `repoRev` may be.
const FUTURE: u64 = 5 * MINUTE;

/// How long an answer is waited for, and a DID document.
const ANSWER_WAIT: Duration = crate::outbound::WAIT;
const RESOLVE_WAIT: Duration = crate::outbound::WAIT;
/// The most sends at once, across every account.
const IN_FLIGHT: usize = 32;
/// The most updates waiting to be sent, across every account.
const UPDATES_WAITING: usize = 1024;
/// The longest the scheduler sleeps between looks at what is due.
const NAP: Duration = Duration::from_secs(5);
/// The statuses that fail a send for now, besides a redirect, which is as
/// no answer (`spec/SPACES-SYNC.md`, "Environment"); any other but `2xx`
/// refuses it.
const FAILING: [u16; 9] = [408, 425, 429, 500, 502, 503, 504, 522, 524];

fn lock<T>(m: &Mutex<T>) -> MutexGuard<'_, T> {
    m.lock().unwrap_or_else(PoisonError::into_inner)
}

// ---- What an account keeps ------------------------------------------------------

/// When a send is next made: `n` is which attempt it is (0 the first, then
/// each retry), `due` when, and `until` its horizon; in milliseconds since
/// the epoch.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Schedule {
    pub n: u32,
    pub due: u64,
    pub until: u64,
}

/// A write notification that failed for now: its commit's `rev` and `data`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Pending {
    pub rev: String,
    pub data: Vec<u8>,
    pub at: Schedule,
}

/// A registration's endpoint and token, each the exact string the syncer gave.
pub(crate) type Pair = (String, String);

/// A registration: when it lapses (the `exp` of the credential its latest
/// authorization was answered with), and whether it was sent its expiry
/// notice since it last lapsed.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Registration {
    pub expires: u64,
    pub noticed: bool,
}

/// What a notice tells: the space's deletion, or the registration's expiry,
/// at the change's `spaceRev`, owed it for its lapse at `lapse` (the expiry
/// it then had).
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Owed {
    Deleted,
    Expired { space_rev: String, lapse: u64 },
}

/// A notice kept to be sent again: what it tells, and when. Its `until` is
/// 72 hours after it was kept.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Notice {
    pub owed: Owed,
    pub at: Schedule,
}

/// What an account keeps of this part.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct Kept {
    /// Its notifications that failed for now, by space: the retry queue.
    pub queue: BTreeMap<String, Pending>,
    /// The registrations of the spaces it is the authority of: by space,
    /// each pair and its registration.
    pub registered: BTreeMap<String, BTreeMap<Pair, Registration>>,
    /// The notices it keeps to send again, by space and pair: the notice queue.
    pub notices: BTreeMap<(String, Pair), Notice>,
    /// How many registrations `registered` holds, of every space.
    registrations: usize,
}

impl Kept {
    /// Replay an entry of `repo.log` of the kinds in `ENTRIES`.
    pub fn replay(&mut self, e: &Json) -> Result<(), String> {
        self.apply(e).map_err(|why| format!("{why}: {e}"))
    }

    /// About the bytes it holds in memory: its queues and registrations,
    /// each by how many there are.
    pub(crate) fn cost(&self) -> u64 {
        ((self.queue.len() + self.notices.len()) * 224
            + self.registered.len() * 120
            + self.registrations * 200) as u64
    }

    /// Hold `pair`'s registration for `space`, in place of any it had.
    pub(crate) fn register(&mut self, space: String, pair: Pair, r: Registration) {
        if self
            .registered
            .entry(space)
            .or_default()
            .insert(pair, r)
            .is_none()
        {
            self.registrations += 1;
        }
    }

    fn drop_registration(&mut self, space: &str, pair: &Pair) {
        if let Some(r) = self.registered.get_mut(space) {
            if r.remove(pair).is_some() {
                self.registrations -= 1;
            }
            if r.is_empty() {
                self.registered.remove(space);
            }
        }
    }

    /// Make the change an entry records.
    pub(crate) fn apply(&mut self, e: &Json) -> Result<(), String> {
        let text = |k: &str| e[k].as_str().ok_or_else(|| format!("no {k}"));
        let number = |k: &str| e[k].as_u64().ok_or_else(|| format!("no {k}"));
        let space = text("space")?;
        if SpaceRef::parse(space).is_none() {
            return Err("a space that is no space-ref".into());
        }
        let schedule = || -> Result<Schedule, String> {
            let n = u32::try_from(number("n")?).map_err(|_| "an attempt too many")?;
            Ok(Schedule {
                n,
                due: number("due")?,
                until: number("until")?,
            })
        };
        let pair = || Ok::<_, String>((text("endpoint")?.to_string(), text("token")?.to_string()));
        match text("t")? {
            QUEUED => {
                let rev = text("rev")?;
                if !valid_tid(rev) {
                    return Err("a rev that is no TID".into());
                }
                let data = hex::decode(text("data")?).map_err(|_| "data that is no hex")?;
                self.queue.insert(
                    space.to_string(),
                    Pending {
                        rev: rev.to_string(),
                        data,
                        at: schedule()?,
                    },
                );
            }
            UNQUEUED => {
                let rev = text("rev")?;
                if self.queue.get(space).is_some_and(|p| p.rev.as_str() <= rev) {
                    self.queue.remove(space);
                }
            }
            REGISTERED => {
                let r = Registration {
                    expires: number("expires")?,
                    noticed: false,
                };
                self.register(space.to_string(), pair()?, r);
            }
            DROPPED => self.drop_registration(space, &pair()?),
            NOTICED => {
                let pair = pair()?;
                let r = self
                    .registered
                    .get_mut(space)
                    .and_then(|r| r.get_mut(&pair))
                    .ok_or("an expiry notice of no registration")?;
                r.noticed = true;
            }
            EMPTIED => {
                if let Some(r) = self.registered.remove(space) {
                    self.registrations -= r.len();
                }
            }
            NOTICE => {
                let owed = match text("update")? {
                    "deleted" => Owed::Deleted,
                    "expired" => Owed::Expired {
                        space_rev: text("spaceRev")?.to_string(),
                        lapse: number("lapse")?,
                    },
                    u => return Err(format!("a notice of no known kind {u}")),
                };
                let at = schedule()?;
                self.notices
                    .insert((space.to_string(), pair()?), Notice { owed, at });
            }
            NOTICE_DONE => {
                self.notices.remove(&(space.to_string(), pair()?));
            }
            t => return Err(format!("an entry of no known type {t}")),
        }
        Ok(())
    }

    /// When the first of its sends is due.
    pub(crate) fn next_due(&self) -> Option<u64> {
        self.dues().min()
    }

    /// When the first of its sends due after `now` is due: those due
    /// already are being sent, and hint again when settled.
    fn next_due_after(&self, now: u64) -> Option<u64> {
        self.dues().filter(|due| *due > now).min()
    }

    fn dues(&self) -> impl Iterator<Item = u64> + '_ {
        self.queue
            .values()
            .map(|p| p.at.due)
            .chain(self.notices.values().map(|n| n.at.due))
    }

    /// Where `pair` stands for `space` at `now`, as `authorizeSpaceSync`'s
    /// step 10 asks (`spec/SPACES-SYNC.md`, "Registering").
    pub(crate) fn standing(&self, space: &str, endpoint: &str, token: &str, now: u64) -> Standing {
        let Some(registered) = self.registered.get(space) else {
            return Standing::New;
        };
        let mine = registered
            .iter()
            .find(|((e, t), _)| e == endpoint && t == token)
            .map(|(_, r)| r);
        if mine.is_some_and(|r| r.expires > now) {
            return Standing::Active;
        }
        if registered.values().filter(|r| r.expires > now).count() >= SPACE_REGISTRATIONS {
            return Standing::Full;
        }
        if mine.is_some() {
            Standing::Lapsed
        } else {
            Standing::New
        }
    }
}

/// Where a pair stands for a space: registered and active; registered and
/// lapsed; or not registered, with room for it or not.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Standing {
    Active,
    Lapsed,
    New,
    Full,
}

fn registered(space: &str, pair: (&str, &str), expires: u64) -> Json {
    json!({ "t": REGISTERED, "space": space, "endpoint": pair.0, "token": pair.1, "expires": expires })
}

fn dropped(space: &str, pair: &Pair) -> Json {
    json!({ "t": DROPPED, "space": space, "endpoint": pair.0, "token": pair.1 })
}

fn noticed(space: &str, pair: &Pair) -> Json {
    json!({ "t": NOTICED, "space": space, "endpoint": pair.0, "token": pair.1 })
}

fn queued(space: &str, rev: &str, data: &[u8], at: Schedule) -> Json {
    json!({ "t": QUEUED, "space": space, "rev": rev, "data": hex::encode(data), "n": at.n, "due": at.due, "until": at.until })
}

fn unqueued(space: &str, rev: &str) -> Json {
    json!({ "t": UNQUEUED, "space": space, "rev": rev })
}

fn notice(space: &str, pair: &Pair, owed: &Owed, at: Schedule) -> Json {
    let mut e = json!({ "t": NOTICE, "space": space, "endpoint": pair.0, "token": pair.1, "n": at.n, "due": at.due, "until": at.until });
    match owed {
        Owed::Deleted => e["update"] = json!("deleted"),
        Owed::Expired { space_rev, lapse } => {
            e["update"] = json!("expired");
            e["spaceRev"] = json!(space_rev);
            e["lapse"] = json!(lapse);
        }
    }
    e
}

fn notice_done(space: &str, pair: &Pair) -> Json {
    json!({ "t": NOTICE_DONE, "space": space, "endpoint": pair.0, "token": pair.1 })
}

/// Log `changes` to the writer set (`space_authority`) and `entries` of
/// this part's in one frame, then make the changes they record: a frame the
/// log could not take changes nothing (`spec/LIMITS.md`, "Disk"). Answers
/// whether it was taken. An account left with sends due is marked for a
/// start to load first, and one left with none unmarked (`cache`).
fn log_with(st: &mut Store, changes: &[Json], entries: &[Json]) -> bool {
    if changes.is_empty() && entries.is_empty() {
        return true;
    }
    let mut after = st.notify.clone();
    for e in entries {
        after.apply(e).expect("an entry made to apply");
    }
    let did = st.repo.did.clone();
    if after.next_due().is_some()
        && let Err(e) = st.ctx.eager.mark(&did)
    {
        crate::ops::failed_for(
            crate::ops::Level::Error,
            "marking an account failed",
            &did,
            e,
        );
        return false;
    }
    let frame: Vec<Json> = changes.iter().chain(entries).cloned().collect();
    if let Err(e) = st.wal.append(&frame) {
        crate::ops::failed("logging write notifications failed", e);
        return false;
    }
    for c in changes {
        st.authority
            .apply(c)
            .expect("a change checked before it is logged");
    }
    st.notify = after;
    if !st.needs_start() && st.ctx.eager.is_marked(&did) {
        st.ctx.eager.relax(&did, None);
    }
    true
}

fn log(st: &mut Store, entries: &[Json]) -> bool {
    log_with(st, &[], entries)
}

/// The schedule after attempt `tried` of a notification failed at `now`:
/// retry `n` is due `min(60 · 2^(n−1), 3600)` seconds, times a random
/// factor from 0.5 to 1, after it; None if that is past `until`.
fn retry(now: u64, tried: u32, until: u64) -> Option<Schedule> {
    let n = tried + 1;
    let full = (60_000u64 << (n - 1).min(6)).min(3_600_000);
    let due = now + full / 2 + rand::random::<u64>() % (full / 2 + 1);
    (due <= until).then_some(Schedule { n, due, until })
}

/// The schedule after attempt `tried` of a notice failed at `now`: retry
/// `n` is due `NOTICE_DELAYS[n − 1]` seconds (the last for every one
/// after), times a random factor from 0.5 to 1, after it; None, given up,
/// once `until` has come.
fn notice_retry(now: u64, tried: u32, until: u64) -> Option<Schedule> {
    if now >= until {
        return None;
    }
    let n = tried + 1;
    let full = NOTICE_DELAYS[(n as usize - 1).min(NOTICE_DELAYS.len() - 1)] * 1000;
    let due = now + full / 2 + rand::random::<u64>() % (full / 2 + 1);
    Some(Schedule { n, due, until })
}

/// A notice given up, kept or not: an expiry notice drops its
/// registration, unless that was renewed since (or dropped already).
fn given_up(kept: &Kept, space: &str, pair: &Pair, owed: &Owed) -> Option<Json> {
    let Owed::Expired { lapse, .. } = owed else {
        return None;
    };
    kept.registered
        .get(space)
        .and_then(|r| r.get(pair))
        .filter(|r| r.expires == *lapse)
        .map(|_| dropped(space, pair))
}

// ---- TIDs ---------------------------------------------------------------------------

const TID_CHARS: &[u8; 32] = b"234567abcdefghijklmnopqrstuvwxyz";

fn tid_value(tid: &str) -> u64 {
    tid.bytes().fold(0u64, |n, c| {
        (n << 5) | TID_CHARS.iter().position(|&x| x == c).unwrap_or(0) as u64
    })
}

fn tid_of(value: u64) -> String {
    (0..13)
        .rev()
        .map(|i| TID_CHARS[((value >> (i * 5)) & 31) as usize] as char)
        .collect()
}

/// A new `spaceRev`: the TID of `now`, or, if that is not later than the
/// space's revision `prev`, the TID one microsecond after it.
fn next_space_rev(now: u64, prev: Option<&str>) -> String {
    let at = (now * 1000) << 10;
    tid_of(match prev.map(tid_value) {
        Some(p) if at <= p => ((p >> 10) + 1) << 10,
        _ => at,
    })
}

/// A space's revision: the greatest `spaceRev` of its writer set, removed
/// entries included; none while the set is empty.
pub(crate) fn revision(space: &Space) -> Option<&str> {
    space.writers.values().map(|w| w.space_rev.as_str()).max()
}

// ---- The server's part ----------------------------------------------------------------

/// What is being sent, for an account: a commit's notification, a kept
/// notice, or a notice's first attempt, kept only if it fails for now.
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
enum Sending {
    Write { space: String, rev: String },
    Notice { space: String, pair: Pair },
    Once(u64),
}

/// What this part shares across accounts.
pub(crate) struct Notify {
    /// When each account next has a send due, and its DID: a hint, which
    /// may be stale, checked against what the account keeps when it comes.
    hints: Mutex<BTreeSet<(u64, String)>>,
    /// The sends being made, by account, so that none is made twice at once.
    sending: Mutex<HashSet<(String, Sending)>>,
    /// Wakes the scheduler when a hint is given.
    wake: tokio::sync::Notify,
    slots: Semaphore,
    /// The updates waiting to be sent, or being sent.
    updates: Waiting,
    /// Names each notice's first attempt.
    attempts: AtomicU64,
    /// Milliseconds added to the clock, for tests to see retries come due.
    #[cfg(test)]
    pub skew: AtomicU64,
}

/// How many of something wait, up to a bound: a place is had while one is
/// free, and given back when it is dropped.
pub(crate) struct Waiting {
    n: Arc<AtomicUsize>,
    max: usize,
}

/// A place among those waiting, given back when dropped.
pub(crate) struct Place(Arc<AtomicUsize>);

impl Waiting {
    pub fn new(max: usize) -> Waiting {
        Waiting {
            n: Arc::default(),
            max,
        }
    }

    /// A place, if fewer than its bound wait.
    pub fn enter(&self) -> Option<Place> {
        self.n
            .fetch_update(Ordering::SeqCst, Ordering::SeqCst, |n| {
                (n < self.max).then_some(n + 1)
            })
            .ok()?;
        Some(Place(self.n.clone()))
    }
}

impl Drop for Place {
    fn drop(&mut self) {
        self.0.fetch_sub(1, Ordering::SeqCst);
    }
}

impl Notify {
    pub fn new() -> Notify {
        Notify {
            hints: Mutex::default(),
            sending: Mutex::default(),
            wake: tokio::sync::Notify::new(),
            slots: Semaphore::new(IN_FLIGHT),
            updates: Waiting::new(UPDATES_WAITING),
            attempts: AtomicU64::new(0),
            #[cfg(test)]
            skew: Default::default(),
        }
    }

    /// The time, in milliseconds since the epoch.
    pub fn now(&self) -> u64 {
        let now = SystemTime::now()
            .duration_since(UNIX_EPOCH)
            .unwrap_or_default()
            .as_millis() as u64;
        #[cfg(test)]
        let now = now + self.skew.load(Ordering::SeqCst);
        now
    }

    /// Note when `did` next has a send due, and wake the scheduler.
    fn hint(&self, did: &str, due: Option<u64>) {
        if let Some(due) = due {
            lock(&self.hints).insert((due, did.to_string()));
            self.wake.notify_one();
        }
    }
}

/// Join the space repo, and take up the sends kept when the server stopped:
/// those of the accounts loaded, which a start loads every one with sends
/// due of (`cache`).
pub(crate) fn resume(svc: &Service) {
    svc.space_hooks.on_commit(Box::new(on_commit));
    for (did, a) in &read(&svc.directory).by_did {
        if a.store.is_loaded() {
            lock(&svc.space_notify.hints).extend(
                read(&a.store)
                    .notify
                    .next_due()
                    .map(|due| (due, did.clone())),
            );
        }
    }
}

/// Send what comes due, from now until the server stops.
pub(crate) fn start(svc: &Shared) {
    let svc = svc.clone();
    tokio::spawn(async move {
        loop {
            let (_, next) = run_due(&svc);
            let now = svc.space_notify.now();
            let nap = next.map_or(NAP, |due| {
                Duration::from_millis(due.saturating_sub(now)).min(NAP)
            });
            tokio::select! {
                () = tokio::time::sleep(nap) => {}
                () = svc.space_notify.wake.notified() => {}
            }
        }
    });
}

/// Look now at what `did` has due, as after a space of its is deleted.
pub(crate) fn poke(svc: &Service, did: &str) {
    svc.space_notify.hint(did, Some(svc.space_notify.now()));
}

/// One send: a write notification's attempt, or a notice's. A notice with
/// `once`, which names the attempt, is an expiry notice's first attempt,
/// not kept in the notice queue.
#[derive(Clone, Debug)]
enum Job {
    Write {
        did: String,
        space: String,
        rev: String,
        data: Vec<u8>,
        n: u32,
        until: u64,
    },
    Notice {
        did: String,
        space: String,
        pair: Pair,
        owed: Owed,
        n: u32,
        until: u64,
        once: Option<u64>,
    },
}

impl Job {
    fn key(&self) -> (String, Sending) {
        match self {
            Job::Write {
                did, space, rev, ..
            } => (
                did.clone(),
                Sending::Write {
                    space: space.clone(),
                    rev: rev.clone(),
                },
            ),
            Job::Notice {
                did,
                once: Some(attempt),
                ..
            } => (did.clone(), Sending::Once(*attempt)),
            Job::Notice {
                did, space, pair, ..
            } => (
                did.clone(),
                Sending::Notice {
                    space: space.clone(),
                    pair: pair.clone(),
                },
            ),
        }
    }
}

/// Start every send due now, of each account hinted as having one: a
/// notification past its horizon is dropped instead; a notice whose
/// registration was renewed or dropped, or whose space is live again, is
/// dropped; and one whose authority is not active is rescheduled unsent.
/// Answers the sends started, and when the next is due.
fn run_due(svc: &Shared) -> (Vec<JoinHandle<()>>, Option<u64>) {
    let n = &svc.space_notify;
    let now = n.now();
    let dids: BTreeSet<String> = {
        let mut hints = lock(&n.hints);
        let later = hints.split_off(&(now + 1, String::new()));
        std::mem::replace(&mut *hints, later)
            .into_iter()
            .map(|(_, did)| did)
            .collect()
    };
    let mut sends = Vec::new();
    for did in dids {
        let Some(a) = svc.account(&did) else { continue };
        let active = status(&a) == Status::Active;
        let (jobs, wal, written) = {
            let mut guard = write(&a.store);
            let st = &mut *guard;
            let mut sending = lock(&n.sending);
            let (mut jobs, mut done) = (Vec::new(), Vec::new());
            for (space, p) in &st.notify.queue {
                let key = (
                    did.clone(),
                    Sending::Write {
                        space: space.clone(),
                        rev: p.rev.clone(),
                    },
                );
                if sending.contains(&key) || p.at.due > now {
                } else if now >= p.at.until {
                    done.push(unqueued(space, &p.rev));
                } else {
                    sending.insert(key);
                    jobs.push(Job::Write {
                        did: did.clone(),
                        space: space.clone(),
                        rev: p.rev.clone(),
                        data: p.data.clone(),
                        n: p.at.n,
                        until: p.at.until,
                    });
                }
            }
            for ((space, pair), kept) in &st.notify.notices {
                let key = (
                    did.clone(),
                    Sending::Notice {
                        space: space.clone(),
                        pair: pair.clone(),
                    },
                );
                let stale = match &kept.owed {
                    Owed::Deleted => st.authority.state(space) == SpaceState::Live,
                    Owed::Expired { lapse, .. } => st
                        .notify
                        .registered
                        .get(space)
                        .and_then(|r| r.get(pair))
                        .is_none_or(|r| r.expires != *lapse || r.expires > now),
                };
                if sending.contains(&key) || kept.at.due > now {
                } else if stale {
                    done.push(notice_done(space, pair));
                } else if !active {
                    match notice_retry(now, kept.at.n, kept.at.until) {
                        Some(at) => done.push(notice(space, pair, &kept.owed, at)),
                        None => {
                            done.push(notice_done(space, pair));
                            done.extend(given_up(&st.notify, space, pair, &kept.owed));
                        }
                    }
                } else {
                    sending.insert(key);
                    jobs.push(Job::Notice {
                        did: did.clone(),
                        space: space.clone(),
                        pair: pair.clone(),
                        owed: kept.owed.clone(),
                        n: kept.at.n,
                        until: kept.at.until,
                        once: None,
                    });
                }
            }
            drop(sending);
            log(st, &done);
            (jobs, st.wal.clone(), st.wal.written())
        };
        n.hint(&did, read(&a.store).notify.next_due_after(now));
        // What a send rests on is on disk before it goes.
        sends
            .extend(jobs.into_iter().map(|job| {
                crate::ops::spawn(send(svc.clone(), job, Some((wal.clone(), written))))
            }));
    }
    let next = lock(&n.hints).first().map(|(due, _)| *due);
    (sends, next)
}

/// How a send ended.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Outcome {
    /// A `2xx`.
    Delivered,
    /// No answer, or a status worth trying again.
    Failed,
    /// Any other answer: not sent again.
    Refused,
}

/// Make a send, once `after` is on disk, then settle it.
async fn send(svc: Shared, job: Job, after: Option<(Arc<Wal>, u64)>) {
    if let Some((wal, n)) = after
        && durable(wal, n).await.is_err()
    {
        return settle(&svc, &job, Outcome::Failed);
    }
    let outcome = match &job {
        Job::Write {
            did,
            space,
            rev,
            data,
            ..
        } => {
            let Some(sr) = SpaceRef::parse(space) else {
                return settle(&svc, &job, Outcome::Refused);
            };
            let body = json!({ "space": space, "repo": did, "repoRev": rev, "data": to_json(&V::Bytes(data.clone())) });
            post_write(&svc, &sr.authority, did, &body).await
        }
        Job::Notice {
            space, pair, owed, ..
        } => {
            let update = match owed {
                Owed::Deleted => json!({ "$type": SPACE_DELETED }),
                Owed::Expired { space_rev, .. } => {
                    json!({ "$type": EXPIRED, "spaceRev": space_rev })
                }
            };
            let body = json!({ "space": space, "token": pair.1, "update": update });
            post_to(&svc, &pair.0, NOTIFY_SPACE_UPDATE, &body).await
        }
    };
    settle(&svc, &job, outcome);
}

/// Settle a send under its account's lock. A write notification delivered
/// or refused takes out the entry of its space if that entry's `rev` is
/// not later; one failed for now is kept, rescheduled, if it is the latest
/// commit's, until its horizon. A kept notice delivered is taken out; one
/// refused, or failed for now once 72 hours have passed since it was kept,
/// is given up; another failed for now is rescheduled. A notice's first
/// attempt failed for now is kept, unless a notice is kept for its
/// registration already; refused, it is given up.
fn settle(svc: &Service, job: &Job, outcome: Outcome) {
    let n = &svc.space_notify;
    let now = n.now();
    let (did, key) = job.key();
    let next = svc.account(&did).map(|a| {
        let mut guard = write(&a.store);
        let st = &mut *guard;
        let entries: Vec<Json> = match (job, outcome) {
            (Job::Write { space, rev, .. }, Outcome::Delivered | Outcome::Refused) => st
                .notify
                .queue
                .get(space)
                .filter(|p| p.rev <= *rev)
                .map(|_| unqueued(space, rev))
                .into_iter()
                .collect(),
            (
                Job::Write {
                    space,
                    rev,
                    data,
                    n: tried,
                    until,
                    ..
                },
                Outcome::Failed,
            ) => {
                let kept = st.notify.queue.get(space).map(|p| p.rev.as_str());
                let head = st.spaces.get(space).map(|r| r.commit(&did, space).rev);
                let latest = kept == Some(rev.as_str())
                    || (kept.is_none_or(|k| k < rev.as_str())
                        && head.as_deref() == Some(rev.as_str()));
                let e = match retry(now, *tried, *until) {
                    _ if !latest => None,
                    Some(at) => Some(queued(space, rev, data, at)),
                    None => kept.map(|_| unqueued(space, rev)),
                };
                e.into_iter().collect()
            }
            (
                Job::Notice {
                    space,
                    pair,
                    owed,
                    n: tried,
                    until,
                    once,
                    ..
                },
                outcome,
            ) => {
                let held = st.notify.notices.get(&(space.clone(), pair.clone()));
                let mut entries = Vec::new();
                if once.is_none() {
                    // A kept notice replaced since is the other's to settle.
                    if held.is_some_and(|h| h.owed == *owed && h.at.until == *until) {
                        let retried = (outcome == Outcome::Failed)
                            .then(|| notice_retry(now, *tried, *until))
                            .flatten();
                        match retried {
                            Some(at) => entries.push(notice(space, pair, owed, at)),
                            None => {
                                entries.push(notice_done(space, pair));
                                if outcome != Outcome::Delivered {
                                    entries.extend(given_up(&st.notify, space, pair, owed));
                                }
                            }
                        }
                    }
                } else {
                    match outcome {
                        Outcome::Delivered => {}
                        Outcome::Refused => entries.extend(given_up(&st.notify, space, pair, owed)),
                        // One kept for its registration already: this one is dropped.
                        Outcome::Failed if held.is_some() => {}
                        Outcome::Failed => {
                            let at = notice_retry(now, 0, now + NOTICE_HORIZON)
                                .expect("a horizon ahead");
                            entries.push(notice(space, pair, owed, at));
                        }
                    }
                }
                entries
            }
        };
        log(st, &entries);
        st.notify.next_due()
    });
    lock(&n.sending).remove(&(did.clone(), key));
    n.hint(&did, next.flatten());
}

/// POST `body`, a write notification, to the space host of `authority`:
/// at the origin of the endpoint of its `#atproto_pds`, with service auth
/// from `iss`, as SSRF protection allows (`spec/SPACES-SYNC.md`,
/// "Environment"). No document, no endpoint, one with a user name or
/// password, a URL it will not send to, no connection, a redirect, or no
/// answer within `ANSWER_WAIT`, each fail it for now.
async fn post_write(svc: &Service, authority: &str, iss: &str, body: &Json) -> Outcome {
    let Ok(_slot) = svc.space_notify.slots.acquire().await else {
        return Outcome::Failed;
    };
    let Ok(Some(endpoint)) = tokio::time::timeout(RESOLVE_WAIT, endpoint(svc, authority)).await
    else {
        return Outcome::Failed;
    };
    let Some(url) = xrpc_url(&endpoint, NOTIFY_REPO_UPDATE) else {
        return Outcome::Failed;
    };
    // An account gone can sign nothing again.
    let Some(jwt) = service_auth(
        svc,
        iss,
        &format!("{authority}#atproto_pds"),
        NOTIFY_REPO_UPDATE,
    ) else {
        return Outcome::Refused;
    };
    let request = svc
        .outbound
        .client()
        .post(url)
        .bearer_auth(jwt)
        .header(reqwest::header::CONTENT_TYPE, "application/json")
        .body(body.to_string());
    match svc
        .outbound
        .send(crate::ops::Target::Space, request, ANSWER_WAIT)
        .await
    {
        Ok(status) => outcome(status),
        Err(_) => Outcome::Failed,
    }
}

/// POST `body` to method `nsid` at a syncer's endpoint, with no
/// `Authorization`, as `post_write` sends: an endpoint that is no
/// endpoint fails it for now, as getting no answer.
async fn post_to(svc: &Service, endpoint: &str, nsid: &str, body: &Json) -> Outcome {
    let Ok(_slot) = svc.space_notify.slots.acquire().await else {
        return Outcome::Failed;
    };
    let Some(url) = xrpc_url(&Json::from(endpoint), nsid) else {
        return Outcome::Failed;
    };
    let request = svc
        .outbound
        .client()
        .post(url)
        .header(reqwest::header::CONTENT_TYPE, "application/json")
        .body(body.to_string());
    match svc
        .outbound
        .send(crate::ops::Target::Space, request, ANSWER_WAIT)
        .await
    {
        Ok(status) => outcome(status),
        Err(_) => Outcome::Failed,
    }
}

/// `<origin>/xrpc/<nsid>` of an endpoint (`outbound::origin`); None for
/// one that is no endpoint, or has a user name or password.
fn xrpc_url(endpoint: &Json, nsid: &str) -> Option<url::Url> {
    crate::outbound::origin(endpoint).and_then(|o| o.join(&format!("/xrpc/{nsid}")).ok())
}

fn outcome(status: u16) -> Outcome {
    match status {
        200..=299 => Outcome::Delivered,
        300..=399 => Outcome::Failed,
        s if FAILING.contains(&s) => Outcome::Failed,
        _ => Outcome::Refused,
    }
}

// ---- Telling the space host ----------------------------------------------------------

/// A commit of a space repo here, durable: its space's host is told at
/// once, in the background. An authority here takes it directly; any
/// other is sent it, and kept in the retry queue if that fails for now.
fn on_commit(svc: &Shared, c: &Commit) {
    let Some(sr) = SpaceRef::parse(&c.space) else {
        return;
    };
    let (svc, c) = (svc.clone(), c.clone());
    if svc.account(&sr.authority).is_some() {
        // A refusal changes nothing, and is not retried.
        crate::ops::spawn(async move {
            let _ = take(&svc, &sr, &c.repo, &c.rev, &c.data).await;
        });
        return;
    }
    let Some(a) = svc.account(&c.repo) else {
        return;
    };
    let n = &svc.space_notify;
    let until = n.now() + HORIZON;
    {
        let mut st = write(&a.store);
        // A later commit replaces the entry kept, whatever its schedule:
        // only the latest state is sent again, after a restart too.
        if let Some(at) = retry(n.now(), 0, until)
            .filter(|_| st.notify.queue.get(&c.space).is_some_and(|p| p.rev < c.rev))
        {
            log(&mut st, &[queued(&c.space, &c.rev, &c.data, at)]);
        }
        lock(&n.sending).insert((
            c.repo.clone(),
            Sending::Write {
                space: c.space.clone(),
                rev: c.rev.clone(),
            },
        ));
    }
    let job = Job::Write {
        did: c.repo,
        space: c.space,
        rev: c.rev,
        data: c.data.to_vec(),
        n: 0,
        until,
    };
    crate::ops::spawn(send(svc.clone(), job, None));
}

// ---- Taking a notification -----------------------------------------------------------

pub(crate) fn handler(nsid: &str) -> Option<Handler> {
    Some(match nsid {
        NOTIFY_REPO_UPDATE => Handler::Call(|s, c, m| Box::pin(notify_repo_update(s, c, m))),
        LIST_WRITERS => Handler::Call(|s, c, m| Box::pin(list_writers(s, c, m))),
        _ => return None,
    })
}

fn not_found<T>() -> Result<T, XrpcError> {
    err(400, "SpaceNotFound", "Space not found")
}

fn forbidden<T>(message: &str) -> Result<T, XrpcError> {
    err(403, "Forbidden", message)
}

/// `notifyRepoUpdate`: its service auth, its input, who sent it and to
/// whom, then the notification taken.
async fn notify_repo_update(
    s: &Shared,
    call: &Call<'_>,
    m: &'static Method,
) -> Result<Resp, XrpcError> {
    let (iss, aud) = crate::space_credentials::service_auth(s, call, NOTIFY_REPO_UPDATE).await?;
    let b = crate::input(call, m)?;
    crate::limits::guard(s, call, None, Some(&b))?;
    let (space, repo, rev) = (
        required(&b, "space")?,
        required(&b, "repo")?,
        required(&b, "repoRev")?,
    );
    let Some(sr) = SpaceRef::parse(space) else {
        return invalid("space must be a valid space-ref");
    };
    let Ok(V::Bytes(data)) = from_json(&b["data"]) else {
        return invalid("data must be bytes");
    };
    if iss != repo {
        return forbidden("The token's issuer is not the repo notified of");
    }
    let authority = sr.authority.as_str();
    if !aud
        .is_some_and(|aud| aud == authority || aud.strip_suffix("#atproto_pds") == Some(authority))
    {
        return forbidden("The token is not addressed to the space's authority");
    }
    take(s, &sr, repo, rev, &data).await?;
    Ok(Resp::Nothing)
}

/// Take a notification of `repo`'s commit `rev` in `sr`, from the
/// authority's account on: refused if that is not here, if `rev` is too far
/// ahead, if the space is not live, or if its policy does not authorize the
/// writer. Then a `rev` not later than the writer's entry's, removed or
/// not, changes nothing; a later one becomes its entry, not removed, with a
/// new `spaceRev`, and is sent to the space's registrations. Answers once
/// the change is on disk.
async fn take(
    svc: &Shared,
    sr: &SpaceRef,
    repo: &str,
    rev: &str,
    data: &[u8],
) -> Result<(), XrpcError> {
    let Some(a) = svc.account(&sr.authority) else {
        return not_found();
    };
    let now = svc.space_notify.now();
    if (tid_value(rev) >> 10) / 1000 > now + FUTURE {
        return err(400, "FutureRev", "The repo rev is too far in the future");
    }
    if svc.space_state(sr) != SpaceState::Live {
        return not_found();
    }
    if !svc
        .authorize_write(sr, repo)
        .await
        .or_else(crate::space_authz::Undecided::answer)?
    {
        return forbidden("The writer may not write to the space");
    }
    let uri = sr.uri();
    let (sends, wal, written) = {
        let mut guard = write(&a.store);
        let st = &mut *guard;
        let Some(space) = st.authority.live(&uri) else {
            return not_found();
        };
        let sends = if space
            .writers
            .get(repo)
            .is_some_and(|w| w.rev.as_str() >= rev)
        {
            None
        } else {
            let prev = revision(space).map(str::to_string);
            let space_rev = next_space_rev(now, prev.as_deref());
            let w = Writer {
                rev: rev.to_string(),
                data: data.to_vec(),
                space_rev: space_rev.clone(),
                removed: false,
            };
            let change = writer_tracked(&uri, repo, &w);
            let mut update = json!({ "$type": REPO_WRITE, "repo": repo, "repoRev": rev, "data": to_json(&V::Bytes(data.to_vec())), "spaceRev": space_rev });
            if let Some(p) = prev {
                update["prevSpaceRev"] = json!(p);
            }
            let mut sends = Sends::new(&sr.authority, &uri);
            let mut entries = Vec::new();
            sends.tell(&st.notify, update, &space_rev, now, &mut entries);
            if !log_with(st, &[change], &entries) {
                return crate::internal();
            }
            Some(sends)
        };
        (sends, st.wal.clone(), st.wal.written())
    };
    // The change is in the log: the rest happens even if the caller goes away.
    let svc = svc.clone();
    let finish = crate::ops::spawn(async move {
        let synced = durable(wal, written).await;
        if let (Ok(()), Some(sends)) = (&synced, sends) {
            sends.go(&svc);
        }
        synced
    });
    finish.await.unwrap_or_else(|_| crate::internal())
}

// ---- Sending updates --------------------------------------------------------------------

/// What changes of a space's writer set owe its registrations, to send
/// once the changes are on disk: an update to each active registration,
/// and an expiry notice to each lapsed one not told since it lapsed.
pub(crate) struct Sends {
    authority: String,
    space: String,
    updates: Vec<(String, Json)>,
    notices: Vec<(Pair, Owed)>,
}

impl Sends {
    pub(crate) fn new(authority: &str, space: &str) -> Sends {
        Sends {
            authority: authority.to_string(),
            space: space.to_string(),
            updates: Vec::new(),
            notices: Vec::new(),
        }
    }

    /// What a change whose new `spaceRev` is `space_rev` owes each
    /// registration of `kept` at `now`, `update` to the active ones; the
    /// entries noting each expiry notice owed go in `entries`, to log with
    /// the change.
    fn tell(
        &mut self,
        kept: &Kept,
        update: Json,
        space_rev: &str,
        now: u64,
        entries: &mut Vec<Json>,
    ) {
        for (pair, r) in kept.registered.get(&self.space).into_iter().flatten() {
            if r.expires > now {
                let body = json!({ "space": self.space, "token": pair.1, "update": update });
                self.updates.push((pair.0.clone(), body));
            } else if !r.noticed && !self.notices.iter().any(|(p, _)| p == pair) {
                entries.push(noticed(&self.space, pair));
                let owed = Owed::Expired {
                    space_rev: space_rev.to_string(),
                    lapse: r.expires,
                };
                self.notices.push((pair.clone(), owed));
            }
        }
    }

    /// Send them, in the background: each update one attempt, given up
    /// after `ANSWER_WAIT`, or at once if `UPDATES_WAITING` wait already;
    /// each expiry notice as "Notices" says.
    pub(crate) fn go(self, svc: &Shared) {
        for (endpoint, body) in self.updates {
            let Some(place) = svc.space_notify.updates.enter() else {
                continue;
            };
            let svc = svc.clone();
            crate::ops::spawn(async move {
                let _place = place;
                let _ = tokio::time::timeout(
                    ANSWER_WAIT,
                    post_to(&svc, &endpoint, NOTIFY_SPACE_UPDATE, &body),
                )
                .await;
            });
        }
        for (pair, owed) in self.notices {
            let attempt = svc.space_notify.attempts.fetch_add(1, Ordering::SeqCst);
            let job = Job::Notice {
                did: self.authority.clone(),
                space: self.space.clone(),
                pair,
                owed,
                n: 0,
                until: 0,
                once: Some(attempt),
            };
            lock(&svc.space_notify.sending).insert(job.key());
            crate::ops::spawn(send(svc.clone(), job, None));
        }
    }
}

// ---- Removing a writer ------------------------------------------------------------------

/// Writers taken out of a space's writer set: the entries of the writer
/// set (`space_authority`'s) and of this part's to log in the change's
/// frame, in order, and what to send once it is on disk.
pub(crate) struct Removal {
    pub changes: Vec<Json>,
    pub entries: Vec<Json>,
    pub sends: Sends,
}

/// `remove_writer(space, did)` for each of `dids`, as `st` holds the space
/// `uri` (`spec/SPACES-SYNC.md`, "Removing a writer"): an entry there and
/// not removed is marked removed with a new `spaceRev`, each after the one
/// before, and the removal is sent to the space's registrations; an
/// account with no entry, or one removed already, changes nothing.
pub(crate) fn remove_writers<'a>(
    svc: &Service,
    st: &Store,
    uri: &str,
    dids: impl IntoIterator<Item = &'a str>,
) -> Removal {
    let now = svc.space_notify.now();
    let mut r = Removal {
        changes: Vec::new(),
        entries: Vec::new(),
        sends: Sends::new(&st.repo.did, uri),
    };
    let Some(space) = st.authority.live(uri) else {
        return r;
    };
    let mut prev = revision(space).map(str::to_string);
    let mut taken = HashSet::new();
    for did in dids {
        if !space.writers.get(did).is_some_and(|w| !w.removed) || !taken.insert(did) {
            continue;
        }
        let space_rev = next_space_rev(now, prev.as_deref());
        r.changes.push(writer_removed(uri, did, &space_rev));
        let mut update = json!({ "$type": REPO_REMOVED, "repo": did, "spaceRev": space_rev });
        if let Some(p) = &prev {
            update["prevSpaceRev"] = json!(p);
        }
        r.sends
            .tell(&st.notify, update, &space_rev, now, &mut r.entries);
        prev = Some(space_rev);
    }
    r
}

// ---- Registrations ----------------------------------------------------------------------

/// A challenge: 16 random bytes in base32, RFC 4648's alphabet in lower
/// case, unpadded: 26 characters.
fn challenge() -> String {
    const ALPHABET: &[u8; 32] = b"abcdefghijklmnopqrstuvwxyz234567";
    let bytes: [u8; 16] = rand::random();
    let mut out = String::with_capacity(26);
    let (mut acc, mut bits) = (0u32, 0u32);
    for b in bytes {
        acc = (acc << 8) | u32::from(b);
        bits += 8;
        while bits >= 5 {
            bits -= 5;
            out.push(ALPHABET[((acc >> bits) & 31) as usize] as char);
        }
        acc &= (1 << bits) - 1;
    }
    if bits > 0 {
        out.push(ALPHABET[((acc << (5 - bits)) & 31) as usize] as char);
    }
    out
}

/// Ask `endpoint` to confirm the registration of `token` for `space`
/// (`spec/SPACES-SYNC.md`, "Registering"): confirmed by a `2xx` of
/// `application/json`, a JSON object whose `challenge` is the one sent.
/// Nothing is sent to an endpoint that is no endpoint, has a user name or
/// password, or that the guard will not send to; a redirect is not
/// followed, an answer is read up to `JSON_DOC_MAX` bytes, and given up
/// after `ANSWER_WAIT`.
pub(crate) async fn confirm(svc: &Service, space: &str, endpoint: &str, token: &str) -> bool {
    let Some(url) = xrpc_url(&Json::from(endpoint), CONFIRM) else {
        return false;
    };
    let challenge = challenge();
    let body = json!({ "space": space, "token": token, "challenge": challenge });
    let request = svc
        .outbound
        .client()
        .post(url)
        .header(reqwest::header::CONTENT_TYPE, "application/json")
        .body(body.to_string());
    let Ok(got) = svc
        .outbound
        .fetch_limited(
            crate::ops::Target::Space,
            request,
            crate::outbound::JSON_DOC_MAX,
            ANSWER_WAIT,
        )
        .await
    else {
        return false;
    };
    let json_typed = got
        .headers
        .get(reqwest::header::CONTENT_TYPE)
        .and_then(|v| v.to_str().ok())
        .is_some_and(|t| {
            t.split(';')
                .next()
                .unwrap_or_default()
                .trim()
                .eq_ignore_ascii_case("application/json")
        });
    (200..300).contains(&got.status)
        && json_typed
        && serde_json::from_slice::<Json>(&got.body)
            .ok()
            .is_some_and(|v| v.get("challenge").and_then(Json::as_str) == Some(challenge.as_str()))
}

/// Drop the registration of `endpoint` and `token` for `uri`, active or
/// lapsed, if there is one, as a refusal at `authorizeSpaceSync`'s step 8
/// or 9 does; answered once that is on disk.
pub(crate) async fn withdraw(
    a: &Account,
    uri: &str,
    endpoint: &str,
    token: &str,
) -> Result<(), XrpcError> {
    let pair = (endpoint.to_string(), token.to_string());
    change(a, |st| {
        let held = st
            .notify
            .registered
            .get(uri)
            .is_some_and(|r| r.contains_key(&pair));
        if held && !log(st, &[dropped(uri, &pair)]) {
            return crate::internal();
        }
        Ok(())
    })
    .await
}

/// Make or renew the registration of `endpoint` and `token` for `sr`, to
/// lapse at `expires` (milliseconds), as `authorizeSpaceSync`'s step 11
/// does; and answer the space's revision then, as its step 12 does.
/// Answered once on disk. Refused as step 10 refuses if the space filled
/// up since it was asked; and as the space is if it is not live.
pub(crate) async fn register(
    svc: &Service,
    a: &Account,
    sr: &SpaceRef,
    endpoint: &str,
    token: &str,
    expires: u64,
) -> Result<Option<String>, XrpcError> {
    let uri = sr.uri();
    let now = svc.space_notify.now();
    let mut rev = None;
    change(a, |st| {
        let Some(space) = st.authority.live(&uri) else {
            return match st.authority.state(&uri) {
                SpaceState::Deleted => err(400, "SpaceDeleted", "Space has been deleted"),
                _ => not_found(),
            };
        };
        rev = revision(space).map(str::to_string);
        if st.notify.standing(&uri, endpoint, token, now) == Standing::Full {
            return too_many();
        }
        if !log(st, &[registered(&uri, (endpoint, token), expires)]) {
            return crate::internal();
        }
        Ok(())
    })
    .await?;
    Ok(rev)
}

pub(crate) fn too_many<T>() -> Result<T, XrpcError> {
    err(
        400,
        "TooManyRegistrations",
        "The space has too many active registrations",
    )
}

/// Make a change under the account's lock, answered once its log is on disk.
async fn change(
    a: &Account,
    f: impl FnOnce(&mut Store) -> Result<(), XrpcError>,
) -> Result<(), XrpcError> {
    let (wal, written) = {
        let mut st = write(&a.store);
        f(&mut st)?;
        (st.wal.clone(), st.wal.written())
    };
    durable(wal, written).await?;
    Ok(())
}

// ---- The writer set: listWriters ---------------------------------------------------------

/// The space a space host's method names, and its authority's account: the
/// credential, verified for the authority, must be of this space, and the
/// authority an account here. The call pays its rate limits as the
/// credential is verified, and a write checks the free space
/// (`limits::guard`).
async fn host_of(
    s: &Shared,
    call: &Call<'_>,
    space: &str,
) -> Result<(SpaceRef, Arc<Account>), XrpcError> {
    let Some(sr) = SpaceRef::parse(space) else {
        return invalid("space must be a valid space-ref");
    };
    if !presents_credential(call.headers) {
        return err(401, "MissingJwt", "Missing jwt");
    }
    let credential = verify_space_credential(s, call, &sr.authority).await?;
    if credential.space != space {
        return err(
            400,
            "InvalidCredential",
            "The credential is for another space",
        );
    }
    crate::limits::guard(s, call, None, None)?;
    let Some(a) = s.account(&sr.authority) else {
        return not_found();
    };
    Ok((sr, a))
}

/// `listWriters`: the writer set, in ascending order of `spaceRev`, a page
/// at a time, each entry a `#repoWrite` or, removed, a `#repoRemoved`.
async fn list_writers(s: &Shared, call: &Call<'_>, m: &'static Method) -> Result<Resp, XrpcError> {
    let p = m
        .parse_params(call.params.iter().map(|(k, v)| (k.as_str(), v.as_str())))
        .or_else(|e| invalid(e.0))?;
    let (sr, a) = host_of(s, call, required(&p, "space")?).await?;
    match status(&a) {
        Status::TakenDown => return err(400, "RepoTakendown", "Repo has been takendown"),
        Status::Deactivated => return err(400, "RepoDeactivated", "Repo has been deactivated"),
        Status::Active => {}
    }
    let limit = p.get("limit").and_then(Json::as_u64).unwrap_or(100) as usize;
    let cursor = p.get("cursor").and_then(Json::as_str);
    let (repos, wal) = {
        let st = read(&a.store);
        let Some(space) = st.authority.live(&sr.uri()) else {
            return not_found();
        };
        let mut page: Vec<(&String, &Writer)> = space
            .writers
            .iter()
            .filter(|(_, w)| cursor.is_none_or(|c| w.space_rev.as_str() > c))
            .collect();
        let by_space_rev =
            |x: &(&String, &Writer), y: &(&String, &Writer)| x.1.space_rev.cmp(&y.1.space_rev);
        if page.len() > limit {
            page.select_nth_unstable_by(limit, by_space_rev);
            page.truncate(limit);
        }
        page.sort_unstable_by(by_space_rev);
        let repos: Vec<Json> = page
            .into_iter()
            .map(|(did, w)| {
                if w.removed {
                    json!({ "$type": REPO_REMOVED, "repo": did, "spaceRev": w.space_rev })
                } else {
                    json!({ "$type": REPO_WRITE, "repo": did, "repoRev": w.rev, "data": to_json(&V::Bytes(w.data.clone())), "spaceRev": w.space_rev })
                }
            })
            .collect();
        (repos, st.wal.clone())
    };
    durable(wal.clone(), wal.written()).await?;
    let cursor = repos.last().map(|r| r["spaceRev"].clone());
    let mut out = json!({ "repos": repos });
    if let Some(last) = cursor {
        out["cursor"] = last;
    }
    Ok(Resp::Json(out))
}

// ---- Deletion ---------------------------------------------------------------------------

/// A live space of `st`'s account deleted: its registrations, lapsed ones
/// too, dropped, each owed a deletion notice, kept in the notice queue in
/// place of any kept for it and sent at once once the deletion is on disk
/// (`poke`). The entries to log in the deletion's frame, which the
/// deletion makes once the frame is written (`Kept::apply`); refused if
/// the account cannot be marked for a start to load (`log_with`).
pub(crate) fn space_deleted(svc: &Service, st: &Store, uri: &str) -> Result<Vec<Json>, XrpcError> {
    let now = svc.space_notify.now();
    let Some(registered) = st.notify.registered.get(uri) else {
        return Ok(Vec::new());
    };
    if let Err(e) = st.ctx.eager.mark(&st.repo.did) {
        crate::ops::failed_for(
            crate::ops::Level::Error,
            "marking an account failed",
            &st.repo.did,
            e,
        );
        return crate::internal();
    }
    let at = Schedule {
        n: 0,
        due: now,
        until: now + NOTICE_HORIZON,
    };
    let mut entries = vec![json!({ "t": EMPTIED, "space": uri })];
    entries.extend(
        registered
            .keys()
            .map(|pair| notice(uri, pair, &Owed::Deleted, at)),
    );
    Ok(entries)
}

#[cfg(test)]
pub(crate) mod tests;