path: root/src/access/rules.rs

//! Rules by path every node judges a change by, the same way, before it applies it
//! (`judge`): who may write which part of the document. A change is judged by what it
//! touches (`document::inspect`), by who made it (its committer, the node a signature
//! proves, `document::signatures`; and the user its message names, `User:`), and by the
//! document as its writer saw it: at its dependencies (`document::at`), so a later
//! revocation doesn't refuse what was allowed when it was written, and every node,
//! whatever it holds since, judges alike.
//!
//! * A change without dependencies is an epoch's root: the genesis change, the first a
//!   document holds, or a remake's snapshot, whose hash is the epoch's ID. Nothing else
//!   is judged of it: it writes the protocol data it starts with.
//! * Any other is its committer's, a member at its dependencies, or registering itself,
//!   and not banned there (`access::bans`).
//! * Protocol data (`_continuum`, `document::meta`): a member's entry and its votes by
//!   that member only (removing an entry also by a user who may write there); epochs
//!   and the swarm ID in a root only; a remake's decision by the coordinator its
//!   proposal names, the rest of a record by any member; a user's tokens revoked by that
//!   user too (logging out); a member's forget record by that member too (cancelling it,
//!   alive); the rest by a user who may write there.
//! * User data: by a user who may write there.
//! * A map made on the way to what a change writes, where there was none: as what is
//!   written within it.
//! * Under a strict policy (`access::policy`), the values their users sign
//!   (`access::envelope`) only as they signed them (`signed_values`).
//! * Where the swarm declares values sealed (`access::sealed`), only those sealed as
//!   declared (`sealed_values`).
//!
//! In a swarm without a user registry (`access::registry`), whatever a user would need,
//! any member may. A change written while the document had no policy (at its
//! dependencies) is judged by none: the rules hold from the policy on.

use std::collections::{BTreeSet, HashMap};

use crate::access::policy::Policy;
use crate::access::registry;
use crate::access::sealed::Declared;
use crate::access::{Caps, Right};
use crate::document::at::At;
use crate::document::inspect::{Action, Op, Path};
use crate::document::meta;
use crate::document::replica::Epoch;
use crate::document::{ChangeHash, Document, ReadDoc, store};

/// A change to judge, as its bytes say.
#[derive(Debug, Clone)]
pub(crate) struct Change<'a> {
    pub(crate) hash: ChangeHash,
    pub(crate) deps: &'a [ChangeHash],
    /// The heads to judge it at: its dependencies, or, for those not applied yet, the
    /// changes of the document they build on, where nothing between changed what rules
    /// read (`access::screen`).
    pub(crate) seen: &'a [ChangeHash],
    /// The node that made it (its node ID), as its signature proves.
    pub(crate) committer: Option<&'a str>,
    /// The user it names (`User:`), if any.
    pub(crate) user: Option<&'a str>,
    /// What it touches (`inspect::Inspector`).
    pub(crate) paths: &'a BTreeSet<Path>,
    /// Its operations, where each is and what it does there (`inspect::Inspector::ops`).
    pub(crate) ops: &'a [Op],
}

/// Why a change is refused.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Refusal {
    /// Its dependencies aren't all in the document: it can't be judged yet.
    Unready,
    /// A rule refuses it: which, and what it touched.
    Rule(String),
}

impl std::fmt::Display for Refusal {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Refusal::Unready => f.write_str("its dependencies aren't all here"),
            Refusal::Rule(why) => f.write_str(why),
        }
    }
}

/// What `judge` reads at the heads a change is judged at, whatever the change: the same
/// for every change judged there, so read once (`judge_reading`). Each read at given
/// heads costs as much as working out what they cover, and screening judges most of a
/// batch at the same heads (`access::screen`). What the heads hold doesn't change as the
/// document takes more changes, so nothing here goes stale but by other heads.
#[derive(Debug, Default)]
pub(crate) struct Reads {
    seen: Vec<ChangeHash>,
    policy: Option<Policy>,
    registry: Option<bool>,
    declared: Option<Vec<Declared>>,
    /// By node: whether it is banned, and whether it is a member.
    banned: HashMap<String, bool>,
    member: HashMap<String, bool>,
    /// By user: what the registry lets it do.
    caps: HashMap<String, Caps>,
}

impl Reads {
    /// Read at `seen`: what was read at other heads forgotten.
    fn at(&mut self, seen: &[ChangeHash]) -> &mut Self {
        if self.seen != seen {
            *self = Self {
                seen: seen.to_vec(),
                ..Self::default()
            };
        }
        self
    }
}

impl Reads {
    /// Whether the policy at `seen` requires changes signed (`Policy::required`): read
    /// once for the heads, as `judge_reading` reads it. False if `doc` lacks one of them.
    pub(crate) fn required(&mut self, doc: &Document, seen: &[ChangeHash]) -> bool {
        let Some(at) = At::new(doc, seen) else {
            return false;
        };
        self.at(seen)
            .policy
            .get_or_insert_with(|| super::policy::of(&at))
            .required()
    }
}

/// Judges `change`, about to be applied to `doc` (of `epoch`).
pub(crate) fn judge(doc: &Document, epoch: Epoch, change: &Change<'_>) -> Result<(), Refusal> {
    judge_reading(doc, epoch, change, &mut Reads::default())
}

/// `judge`, with what was read at the same heads before (`Reads`).
pub(crate) fn judge_reading(
    doc: &Document,
    epoch: Epoch,
    change: &Change<'_>,
    reads: &mut Reads,
) -> Result<(), Refusal> {
    if change.deps.is_empty() {
        // The first epoch's: the first change a document holds, as it comes to an empty
        // one, or as it is in one (judged again, `swarm::refusals`).
        let root = if epoch.generation == 0 {
            doc.get_heads().is_empty() || crate::document::changes::holds(doc, &change.hash)
        } else {
            change.hash.0 == epoch.id
        };
        return if root {
            Ok(())
        } else {
            Err(Refusal::Rule(
                "a change without dependencies that isn't the epoch's root".to_owned(),
            ))
        };
    }
    let at = At::new(doc, change.seen).ok_or(Refusal::Unready)?;
    let reads = reads.at(change.seen);
    // Written while the document had no policy (or one this node doesn't know): judged
    // as it was then, by none. History from before the policy stays as it is.
    let policy = reads
        .policy
        .get_or_insert_with(|| super::policy::of(&at))
        .clone();
    if !policy.enforced() {
        return Ok(());
    }
    let refuse = |why: String| Err(Refusal::Rule(why));
    let Some(node) = change.committer else {
        return refuse("it names no node".to_owned());
    };
    let banned = *reads
        .banned
        .entry(node.to_owned())
        .or_insert_with(|| super::bans::banned(&at, node));
    if banned {
        return refuse(format!("{node} is banned"));
    }
    let own_entry = meta::path(&[meta::MEMBERS, node]);
    let member = *reads
        .member
        .entry(node.to_owned())
        .or_insert_with(|| store::read_path(&at, &own_entry).ok().flatten().is_some());
    let registering = change
        .paths
        .iter()
        .all(|path| path.starts_with(&own_entry) || *path == meta::path(&[meta::MEMBERS]));
    if !member && !registering {
        return refuse(format!("{node} isn't a member"));
    }
    let registry = *reads.registry.get_or_insert_with(|| registry::exists(&at));
    if registry && let Some(user) = change.user {
        reads
            .caps
            .entry(user.to_owned())
            .or_insert_with(|| registry::caps_of(&at, user));
    }
    reads
        .declared
        .get_or_insert_with(|| super::sealed::declared(&at));
    let reads = &*reads;
    // Whether the user may write `path`: as the registry at its dependencies says, or,
    // without one, any member.
    let user_may = |path: &Path| match (registry, change.user) {
        (false, _) => true,
        (true, Some(user)) => reads
            .caps
            .get(user)
            .is_some_and(|caps| caps.allows(Right::Write, path)),
        (true, None) => false,
    };
    // Maps made on the way to what the change writes, where there were none
    // (`store::write_path` makes them): judged by what is written within them.
    let on_the_way: BTreeSet<&Path> = change
        .paths
        .iter()
        .filter(|path| {
            let mut here = change.ops.iter().filter(|op| op.path == **path).peekable();
            here.peek().is_some()
                && here.all(|op| op.action == Action::MakeMap)
                && change
                    .paths
                    .iter()
                    .any(|other| other.len() > path.len() && other.starts_with(path))
                && store::read_path(&at, path).ok().flatten().is_none()
        })
        .collect();
    // Whether the change only makes a map at `path`, where there is none.
    let made = |path: &Path| {
        change
            .ops
            .iter()
            .filter(|op| op.path == *path)
            .all(|op| op.action == Action::MakeMap)
            && store::read_path(&at, path).ok().flatten().is_none()
    };
    for path in change.paths {
        if on_the_way.contains(path) {
            continue;
        }
        if !meta::is_protocol(path) {
            if !user_may(path) {
                return refuse(format!("{} may not write {}", who(change), shown(path)));
            }
            continue;
        }
        let part = path.get(1).map(String::as_str);
        let owner = path.get(2).map(String::as_str);
        let allowed = match (part, owner) {
            // A member's entry, its votes: its own. Removing an entry, also a user's: one
            // who may write it, or forgets the member in the same change
            // (`DELETE /peers/{pk}`, which needs `_continuum/forgotten` alone).
            (Some(meta::MEMBERS), Some(owner)) => {
                let forgetting = meta::path(&[meta::FORGOTTEN, owner]);
                owner == node
                    || user_may(path)
                    || (change
                        .paths
                        .iter()
                        .any(|other| other.starts_with(&forgetting))
                        && user_may(&forgetting))
            }
            (Some(meta::VOTES), Some(owner)) => owner == node,
            // What holds them: made by whichever member first writes in it, where there
            // is none; replaced or removed by one who may write it.
            (Some(meta::MEMBERS | meta::VOTES | meta::REMAKES), None) => {
                made(path) || user_may(path)
            }
            // Written by a root only.
            (Some(meta::EPOCHS | meta::SWARM), _) => false,
            // Logging out: a user revokes its own tokens (`POST /auth/logout`); one who
            // manages users, anyone's (`DELETE /admin/users/{name}/tokens`).
            (Some(meta::LOGOUTS), Some(owner)) => {
                change.user == Some(owner)
                    || user_may(path)
                    || user_may(&meta::path(&[meta::USERS]))
            }
            // Under a strict policy, a user's own entry, as an envelope: signed by the user
            // with only its keys changed (`envelope::check`, run by `signed_values`).
            (Some(meta::USERS), Some(owner))
                if path.len() == 3 && change.user == Some(owner) && policy.strict() =>
            {
                true
            }
            // A user's own keys (`/auth/keys`), whatever else it may do; its last too
            // (the node it asks keeps that from one without a password there, which no
            // other node can tell).
            (Some(meta::USERS), Some(owner))
                if path.get(3).map(String::as_str) == Some("keys")
                    && change.user == Some(owner) =>
            {
                true
            }
            // A node forgotten while alive cancels its own record (`swarm::peer::forget`).
            (Some(meta::FORGOTTEN), Some(owner)) => owner == node || user_may(path),
            (Some(meta::REMAKES), Some(id)) => match path.get(3).map(String::as_str) {
                // Its coordinator's; or the record of the remake that made the epoch,
                // carried into it whole (its proposal written with it) by the coordinator
                // its snapshot names (`remake::switch`), where there is none.
                // Also by one who may write it (an operator aborting an expired remake,
                // or superseding it, `remake::api`).
                Some("decision") => match coordinator(&at, id) {
                    Some(coordinator) => coordinator == node || user_may(path),
                    None if user_may(path) => true,
                    None => {
                        change
                            .paths
                            .iter()
                            .any(|other| other == &meta::path(&[meta::REMAKES, id, "proposal"]))
                            && store::read_path(&at, &meta::path(&[meta::REMAKES, id]))
                                .ok()
                                .flatten()
                                .is_none()
                            && made_the_epoch(&at, epoch, id, node)
                    }
                },
                // The record, made where there is none, and its proposal, written where
                // there is none: by whichever member proposes. Replaced or removed by
                // one who may write them.
                None => made(path) || user_may(path),
                Some("proposal") => {
                    store::read_path(&at, &meta::path(&[meta::REMAKES, id, "proposal"]))
                        .ok()
                        .flatten()
                        .is_none()
                        || user_may(path)
                }
                // The rest (an abort asked for), any member's.
                _ => true,
            },
            _ => user_may(path),
        };
        if !allowed {
            return refuse(format!("{} may not write {}", who(change), shown(path)));
        }
    }
    if policy.strict() {
        signed_values(&at, change.ops).or_else(refuse)?;
    }
    let declared = reads.declared.as_deref().unwrap_or_default();
    if !declared.is_empty() {
        sealed_values(&at, declared, change.ops).or_else(refuse)?;
    }
    Ok(())
}

/// `hash`, which `doc` (of `epoch`) holds, judged by its rules now, as received: why
/// they refuse it, if they do; None if `doc` doesn't hold it. A change this node just
/// made, before it leaves (`AppState::mutate_doc_for`), or one a peer says it refused
/// (`swarm::refusals`).
pub(crate) fn judge_held(
    doc: &crate::document::Document,
    epoch: Epoch,
    hash: &ChangeHash,
) -> Option<Result<(), String>> {
    let change = doc.get_change_by_hash(hash)?;
    // An epoch's root is what the document is: never refused, whatever a peer says.
    if change.deps().is_empty() {
        return Some(Ok(()));
    }
    let decoded = change.decode();
    let ops = crate::document::inspect::Inspector::new(doc)
        .ops(std::slice::from_ref(&decoded))
        .pop()
        .unwrap_or_default();
    let paths = ops.iter().map(|op| op.path.clone()).collect();
    let committer = doc
        .get_author_for_actor(change.actor_id())
        .and_then(|author| {
            std::str::from_utf8(author.as_bytes())
                .ok()
                .map(str::to_owned)
        });
    let user = change
        .message()
        .and_then(crate::document::replica::user_of)
        .map(str::to_owned);
    let deps = change.deps().to_vec();
    let judged = judge(
        doc,
        epoch,
        &Change {
            hash: *hash,
            deps: &deps,
            seen: &deps,
            committer: committer.as_deref(),
            user: user.as_deref(),
            paths: &paths,
            ops: &ops,
        },
    );
    Some(match judged {
        Ok(()) => Ok(()),
        Err(Refusal::Rule(why)) => Err(why),
        // Its dependencies are in the document: it is.
        Err(Refusal::Unready) => Ok(()),
    })
}

/// Where values are declared sealed (`declared`), `ops` write only sealed values as
/// declared, judged at `at`, as their writer saw it (`sealed::check`): at such a place, a
/// string put there that is one (or deleting what is there); nothing within one; nothing
/// in an object nowhere to be found, which might be one.
fn sealed_values(
    at: &At<'_>,
    declared: &[super::sealed::Declared],
    ops: &[Op],
) -> Result<(), String> {
    for op in ops {
        let path = &op.path;
        if op.action == Action::Nowhere {
            return Err("it writes in an object nowhere to be found".to_owned());
        }
        if let Some(place) = super::sealed::place(declared, path) {
            match &op.action {
                Action::PutString(text) => {
                    super::sealed::check(at, place, &serde_json::Value::String(text.clone()))
                        .map_err(|why| format!("{}: {why}", shown(path)))?;
                }
                Action::Delete => {}
                _ => return Err(format!("{} holds a sealed value", shown(path))),
            }
        } else if super::sealed::within(declared, path) {
            return Err(format!("{} is within a sealed value", shown(path)));
        }
    }
    Ok(())
}

/// Under a strict policy, `ops` change the values their users sign (`access::envelope`)
/// only as they signed them, judged at `at`, as their writer saw it: at such a place, a
/// string put there that is an envelope by a user who may write there, replacing the
/// one there (`envelope::check`), and nothing else (but deleting what is there first,
/// as a write replacing it does); nothing within one; above one,
/// nothing replacing or deleting what holds one (a map made where there is none yet,
/// what is inside a list or text, which holds none).
fn signed_values(at: &At<'_>, ops: &[Op]) -> Result<(), String> {
    let signed = super::envelope::signed_paths(at);
    for op in ops {
        let path = &op.path;
        if op.action == Action::Nowhere {
            return Err("it writes in an object nowhere to be found".to_owned());
        }
        if super::envelope::is_signed(&signed, path) {
            let replaced = || {
                ops.iter().any(|other| {
                    other.path == *path && matches!(other.action, Action::PutString(_))
                })
            };
            let envelope = match &op.action {
                Action::PutString(envelope) => envelope,
                // Cleared for the string put there, which is checked.
                Action::Delete if replaced() => continue,
                _ => return Err(format!("{} holds a value its user signs", shown(path))),
            };
            let previous = match store::read_path(at, path) {
                Ok(Some(serde_json::Value::String(text)))
                    if super::envelope::read(&text).is_ok() =>
                {
                    Some(text)
                }
                _ => None,
            };
            super::envelope::check(at, envelope, path, previous.as_deref())
                .map_err(|why| format!("{}: {why}", shown(path)))?;
        } else if super::envelope::signed_path(&signed, path).is_some() {
            return Err(format!("{} is within a value its user signs", shown(path)));
        } else if op.action != Action::Within
            && super::envelope::above_signed(&signed, path)
            && holds_signed(at, path, &signed)
        {
            return Err(format!("{} holds values their users sign", shown(path)));
        }
    }
    Ok(())
}

/// Whether what is at `path` in `at` holds a value at a place for one its user signs,
/// of `signed` (`envelope::signed_paths`), signed or from before the policy; one that
/// doesn't read, as if it did.
fn holds_signed(at: &At<'_>, path: &[String], signed: &[Vec<String>]) -> bool {
    fn within(value: &serde_json::Value, place: &mut Vec<String>, signed: &[Vec<String>]) -> bool {
        if super::envelope::is_signed(signed, place) {
            return true;
        }
        match value {
            serde_json::Value::Object(entries) if super::envelope::above_signed(signed, place) => {
                entries.iter().any(|(key, value)| {
                    place.push(key.clone());
                    let holds = within(value, place, signed);
                    place.pop();
                    holds
                })
            }
            _ => false,
        }
    }
    match store::read_path(at, path) {
        Ok(Some(value)) => within(&value, &mut path.to_vec(), signed),
        Ok(None) => false,
        Err(_) => true,
    }
}

/// Who wrote it, for a refusal.
fn who(change: &Change<'_>) -> String {
    match (change.committer, change.user) {
        (Some(node), Some(user)) => format!("{user} at {node}"),
        (Some(node), None) => node.to_owned(),
        (None, _) => "nobody".to_owned(),
    }
}

fn shown(path: &Path) -> String {
    format!("/{}", path.join("/"))
}

/// Whether remake `id`, coordinated by `node`, made `epoch`: as its snapshot's metadata
/// says (`remake::snapshot`), at `at`. Never genesis.
fn made_the_epoch(at: &At<'_>, epoch: Epoch, id: &str, node: &str) -> bool {
    if epoch.generation == 0 {
        return false;
    }
    let generation = epoch.generation.to_string();
    let Some(metadata) = store::read_path(at, &meta::path(&[meta::EPOCHS, &generation]))
        .ok()
        .flatten()
    else {
        return false;
    };
    metadata.get("remakeId").and_then(serde_json::Value::as_str) == Some(id)
        && metadata
            .get("coordinator")
            .and_then(serde_json::Value::as_str)
            == Some(node)
}

/// The coordinator remake `id`'s proposal names, at `at`.
fn coordinator(at: &At<'_>, id: &str) -> Option<String> {
    let proposal = store::read_path(at, &meta::path(&[meta::REMAKES, id, "proposal"]))
        .ok()
        .flatten()?;
    proposal
        .get("coordinator")
        .and_then(serde_json::Value::as_str)
        .map(str::to_owned)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::clock::UnixMillis;
    use crate::document::replica::{Writer, transact};
    use serde_json::json;

    fn path(text: &str) -> Path {
        text.split('/').map(str::to_owned).collect()
    }

    fn paths(texts: &[&str]) -> BTreeSet<Path> {
        texts.iter().map(|text| path(text)).collect()
    }

    fn write(doc: &mut Document, at: &str, value: serde_json::Value) {
        let writer = Writer {
            node: "genesis",
            user: None,
        };
        let at = path(at);
        transact(doc, UnixMillis(1), &writer, |doc| {
            store::write_path(doc, &at, &value)
        })
        .unwrap();
    }

    /// A swarm with members `a` and `b`, a remake proposed by `a`, and, if `users`,
    /// user `alice` who may write `notes` and `bob` who may not write at all.
    fn swarm(users: bool) -> Document {
        let mut doc = Document::new();
        write(&mut doc, "_continuum/swarm", json!("s"));
        write(&mut doc, "_continuum/access/policy", json!({"version": 1}));
        write(&mut doc, "_continuum/members/a", json!({"since": 1}));
        write(&mut doc, "_continuum/members/b", json!({"since": 1}));
        write(
            &mut doc,
            "_continuum/remakes/r1/proposal",
            json!({"coordinator": "a"}),
        );
        if users {
            let alice = registry::entry("a", 1, &[(path("notes"), &[Right::Write][..])]);
            write(&mut doc, "_continuum/users/alice", alice);
            write(
                &mut doc,
                "_continuum/users/bob",
                registry::entry("a", 1, &[]),
            );
        }
        doc
    }

    fn judged(
        doc: &Document,
        committer: &str,
        user: Option<&str>,
        touched: &[&str],
    ) -> Result<(), Refusal> {
        let deps = doc.get_heads();
        let touched = paths(touched);
        judge(
            doc,
            Epoch::GENESIS,
            &Change {
                hash: ChangeHash([9; 32]),
                deps: &deps,
                seen: &deps,
                committer: Some(committer),
                user,
                paths: &touched,
                ops: &[],
            },
        )
    }

    fn refused(result: Result<(), Refusal>) -> bool {
        matches!(result, Err(Refusal::Rule(_)))
    }

    /// A member's entry and votes are its own; epochs and the swarm ID a root's.
    #[test]
    fn protocol_data() {
        let doc = swarm(true);
        assert!(judged(&doc, "a", None, &["_continuum/members/a/alive"]).is_ok());
        assert!(refused(judged(
            &doc,
            "a",
            None,
            &["_continuum/members/b/alive"]
        )));
        assert!(judged(&doc, "b", None, &["_continuum/votes/b"]).is_ok());
        assert!(refused(judged(&doc, "a", None, &["_continuum/votes/b"])));
        assert!(refused(judged(&doc, "a", None, &["_continuum/swarm"])));
        assert!(refused(judged(&doc, "a", None, &["_continuum/epochs/1"])));
        // A remake's decision: its coordinator's; the rest of the record, any member's.
        assert!(judged(&doc, "a", None, &["_continuum/remakes/r1/decision"]).is_ok());
        assert!(refused(judged(
            &doc,
            "b",
            None,
            &["_continuum/remakes/r1/decision"]
        )));
        assert!(judged(&doc, "b", None, &["_continuum/remakes/r1/abortRequested"]).is_ok());
        // Its proposal: written where there is none; another's replaced, by one who may.
        assert!(judged(&doc, "b", None, &["_continuum/remakes/r3/proposal"]).is_ok());
        assert!(refused(judged(
            &doc,
            "b",
            None,
            &["_continuum/remakes/r1/proposal"]
        )));
        assert!(refused(judged(
            &doc,
            "b",
            None,
            &["_continuum/remakes/r1/proposal/coordinator"]
        )));
        // What holds the records, a member's entries, votes: made where there are none,
        // never replaced or removed by a member.
        assert!(refused(judged(&doc, "b", None, &["_continuum/remakes"])));
        assert!(refused(judged(&doc, "b", None, &["_continuum/members"])));
        assert!(refused(judged(&doc, "b", None, &["_continuum/remakes/r1"])));
        assert!(judged(&doc, "b", None, &["_continuum/votes"]).is_ok());
        // A record carried into a new epoch whole, its proposal with its decision: only
        // the record of the remake that made the epoch, by its coordinator, where there
        // is none.
        let whole = [
            "_continuum/remakes/r2",
            "_continuum/remakes/r2/proposal",
            "_continuum/remakes/r2/decision",
        ];
        assert!(refused(judged(&doc, "b", None, &whole)));
        let mut later = doc.fork();
        write(
            &mut later,
            "_continuum/epochs/1",
            json!({"generation": 1, "remakeId": "r2", "coordinator": "b"}),
        );
        let in_epoch_one = |doc: &Document, committer: &str, touched: &[&str]| {
            let deps = doc.get_heads();
            let touched = paths(touched);
            judge(
                doc,
                Epoch {
                    generation: 1,
                    id: [7; 32],
                },
                &Change {
                    hash: ChangeHash([9; 32]),
                    deps: &deps,
                    seen: &deps,
                    committer: Some(committer),
                    user: None,
                    paths: &touched,
                    ops: &[],
                },
            )
        };
        assert!(in_epoch_one(&later, "b", &whole).is_ok());
        assert!(refused(in_epoch_one(&later, "a", &whole)));
        assert!(refused(in_epoch_one(
            &later,
            "b",
            &[
                "_continuum/remakes/r3",
                "_continuum/remakes/r3/proposal",
                "_continuum/remakes/r3/decision"
            ]
        )));
        assert!(refused(in_epoch_one(
            &later,
            "b",
            &["_continuum/remakes/r2/decision"]
        )));
        // The rest: a user's who may write there.
        assert!(refused(judged(&doc, "a", None, &["_continuum/neighbours"])));
        assert!(refused(judged(
            &doc,
            "a",
            Some("alice"),
            &["_continuum/neighbours"]
        )));
        // Logging out: its own tokens only.
        let tokens = "_continuum/logouts/bob";
        assert!(judged(&doc, "a", Some("bob"), &[tokens]).is_ok());
        assert!(refused(judged(&doc, "a", Some("alice"), &[tokens])));
        // Revoked by one who manages users.
        let mut managed = swarm(true);
        write(
            &mut managed,
            "_continuum/users/carol",
            registry::entry("a", 2, &[(path("_continuum/users"), &[Right::Write][..])]),
        );
        assert!(judged(&managed, "a", Some("carol"), &[tokens]).is_ok());
        // A member forgotten, its entry removed with it, by one who may forget only.
        write(
            &mut managed,
            "_continuum/users/dave",
            registry::entry(
                "a",
                3,
                &[(path("_continuum/forgotten"), &[Right::Write][..])],
            ),
        );
        let forgetting = ["_continuum/forgotten/b", "_continuum/members/b"];
        assert!(judged(&managed, "a", Some("dave"), &forgetting).is_ok());
        assert!(refused(judged(
            &managed,
            "a",
            Some("dave"),
            &["_continuum/members/b"]
        )));
        // A forget record: cancelled by the node it names, not by another.
        let forgotten = "_continuum/forgotten/a";
        assert!(judged(&doc, "a", None, &[forgotten]).is_ok());
        assert!(refused(judged(&doc, "b", None, &[forgotten])));
    }

    /// A banned node's changes: refused, as the ban stood when they were made.
    #[test]
    fn banned_nodes() {
        let mut doc = swarm(true);
        let before = doc.get_heads();
        write(&mut doc, "_continuum/banned/b", json!({"by": "alice"}));
        assert!(refused(judged(
            &doc,
            "b",
            None,
            &["_continuum/members/b/alive"]
        )));
        let touched = paths(&["_continuum/members/b/alive"]);
        let earlier = judge(
            &doc,
            Epoch::GENESIS,
            &Change {
                hash: ChangeHash([9; 32]),
                deps: &before,
                seen: &before,
                committer: Some("b"),
                user: None,
                paths: &touched,
                ops: &[],
            },
        );
        assert!(earlier.is_ok());
    }

    /// What was read at some heads, kept (`Reads`): read again at others, a ban since
    /// counts; read at the first again, it doesn't.
    #[test]
    fn reads_kept_by_heads() {
        let mut doc = swarm(true);
        let before = doc.get_heads();
        write(&mut doc, "_continuum/banned/b", json!({"by": "alice"}));
        let after = doc.get_heads();
        let touched = paths(&["_continuum/members/b/alive"]);
        let mut reads = Reads::default();
        let mut at = |heads: &[ChangeHash]| {
            judge_reading(
                &doc,
                Epoch::GENESIS,
                &Change {
                    hash: ChangeHash([9; 32]),
                    deps: heads,
                    seen: heads,
                    committer: Some("b"),
                    user: None,
                    paths: &touched,
                    ops: &[],
                },
                &mut reads,
            )
        };
        assert!(at(&before).is_ok());
        assert!(at(&before).is_ok());
        assert!(refused(at(&after)));
        assert!(refused(at(&after)));
        assert!(at(&before).is_ok());
    }

    /// A remake's decision: its coordinator's, or one who may write it; no other
    /// member's, whatever its time.
    #[test]
    fn decisions_by_the_coordinator_or_who_may() {
        let mut doc = swarm(true);
        write(
            &mut doc,
            "_continuum/users/carol",
            registry::entry("a", 2, &[(path("_continuum"), &[Right::Write][..])]),
        );
        let decision = "_continuum/remakes/r1/decision";
        assert!(judged(&doc, "a", None, &[decision]).is_ok());
        assert!(refused(judged(&doc, "b", None, &[decision])));
        assert!(refused(judged(&doc, "b", Some("bob"), &[decision])));
        assert!(judged(&doc, "b", Some("carol"), &[decision]).is_ok());
    }

    /// Under a strict policy, a user's own entry is its own to write (what it may sign
    /// there, `envelope::check` says); not another's; without strict, not its own either.
    #[test]
    fn users_write_their_own_entry_under_strict() {
        let mut doc = swarm(true);
        let own = "_continuum/users/bob";
        assert!(refused(judged(&doc, "a", Some("bob"), &[own])));
        write(
            &mut doc,
            "_continuum/access/policy",
            json!({"version": 1, "values": "signed"}),
        );
        assert!(judged(&doc, "a", Some("bob"), &[own]).is_ok());
        assert!(refused(judged(
            &doc,
            "a",
            Some("bob"),
            &["_continuum/users/alice"]
        )));
    }

    /// A node that isn't a member may only register itself.
    #[test]
    fn strangers_register_themselves_only() {
        let doc = swarm(false);
        assert!(
            judged(
                &doc,
                "c",
                None,
                &[
                    "_continuum/members",
                    "_continuum/members/c",
                    "_continuum/members/c/alive"
                ]
            )
            .is_ok()
        );
        assert!(refused(judged(&doc, "c", None, &["notes/x"])));
        assert!(refused(judged(&doc, "c", None, &["_continuum/members/a"])));
    }

    /// User data: as the registry at the change's dependencies says; without one, any
    /// member's.
    #[test]
    fn user_data() {
        let doc = swarm(true);
        assert!(judged(&doc, "a", Some("alice"), &["notes/x"]).is_ok());
        assert!(refused(judged(&doc, "a", Some("alice"), &["config"])));
        assert!(refused(judged(&doc, "a", Some("bob"), &["notes/x"])));
        assert!(refused(judged(&doc, "a", None, &["notes/x"])));
        assert!(refused(judged(&doc, "a", Some("nobody"), &["notes/x"])));
        let legacy = swarm(false);
        assert!(judged(&legacy, "a", None, &["notes/x"]).is_ok());
        assert!(judged(&legacy, "a", None, &["_continuum/neighbours"]).is_ok());
    }

    /// Judged by the registry its writer saw: a revocation since refuses nothing it
    /// allowed then.
    #[test]
    fn judged_as_its_writer_saw_it() {
        let mut doc = swarm(true);
        let then = doc.get_heads();
        write(
            &mut doc,
            "_continuum/users/alice",
            registry::entry("a", 2, &[]),
        );
        let touched = paths(&["notes/x"]);
        let change = |deps: &[ChangeHash]| {
            judge(
                &doc,
                Epoch::GENESIS,
                &Change {
                    hash: ChangeHash([9; 32]),
                    deps,
                    seen: deps,
                    committer: Some("a"),
                    user: Some("alice"),
                    paths: &touched,
                    ops: &[],
                },
            )
        };
        assert!(change(&then).is_ok());
        assert!(refused(change(&doc.get_heads())));
        // Unknown dependencies: not judged yet.
        assert_eq!(change(&[ChangeHash([7; 32])]), Err(Refusal::Unready));
    }

    /// Under a strict policy, a value its user signs only as signed: an envelope that
    /// checks, replacing the one there; nothing else there, nothing within one, nothing
    /// above replacing what holds one.
    #[test]
    fn signed_values_as_signed() {
        use crate::access::{envelope, sshsig};
        let key = ed25519_dalek::SigningKey::from_bytes(&[3; 32]);
        let mut doc = swarm(false);
        let mut alice = registry::entry(
            "a",
            1,
            &[
                (Vec::new(), &[Right::Write][..]),
                (path("_continuum"), &[Right::Write][..]),
            ],
        );
        alice["keys"] = json!({ "k": sshsig::PublicKey(key.verifying_key().to_bytes()).line() });
        write(&mut doc, "_continuum/users/alice", alice);
        write(
            &mut doc,
            "_continuum/access/userSigned",
            json!([["config"], ["a", "b"]]),
        );
        write(
            &mut doc,
            "_continuum/access/policy",
            json!({"version": 1, "values": "signed"}),
        );
        let sealed = |at: &str, prev: &str| {
            let payload = envelope::Payload {
                swarm: "s".to_owned(),
                path: path(at),
                value: json!({"mode": "fast"}),
                user: "alice".to_owned(),
                at: 1,
                prev: prev.to_owned(),
            };
            let bytes = serde_json::to_vec(&payload).unwrap();
            envelope::seal(&bytes, &sshsig::sign(&key, envelope::NAMESPACE, &bytes)).unwrap()
        };
        let judged = |doc: &Document, ops: Vec<Op>| {
            let deps = doc.get_heads();
            let touched: BTreeSet<Path> = ops.iter().map(|op| op.path.clone()).collect();
            judge(
                doc,
                Epoch::GENESIS,
                &Change {
                    hash: ChangeHash([9; 32]),
                    deps: &deps,
                    seen: &deps,
                    committer: Some("a"),
                    user: Some("alice"),
                    paths: &touched,
                    ops: &ops,
                },
            )
        };
        let op = |at: &str, action: Action| Op {
            path: path(at),
            action,
        };
        let first = sealed("config", "");
        assert!(judged(&doc, vec![op("config", Action::PutString(first.clone()))]).is_ok());
        assert!(refused(judged(
            &doc,
            vec![op("config", Action::PutString("plain".to_owned()))]
        )));
        assert!(refused(judged(
            &doc,
            vec![op("config", Action::PutString(sealed("other", "")))]
        )));
        assert!(refused(judged(&doc, vec![op("config", Action::Delete)])));
        assert!(refused(judged(
            &doc,
            vec![
                op("config", Action::Delete),
                op("config", Action::PutString("plain".to_owned()))
            ]
        )));
        assert!(refused(judged(&doc, vec![op("config/x", Action::Other)])));
        // Replacing: only the one there.
        write(&mut doc, "config", json!(first));
        let second = sealed("config", &envelope::digest(Some(&first)));
        assert!(judged(&doc, vec![op("config", Action::PutString(second.clone()))]).is_ok());
        // As a write replacing it makes it: what is there deleted, then the string put.
        assert!(
            judged(
                &doc,
                vec![
                    op("config", Action::Delete),
                    op("config", Action::PutString(second))
                ]
            )
            .is_ok()
        );
        assert!(refused(judged(
            &doc,
            vec![op("config", Action::PutString(sealed("config", "")))]
        )));
        // Above: a map made where there is none, not what holds a signed value.
        assert!(judged(&doc, vec![op("a", Action::MakeMap)]).is_ok());
        assert!(refused(judged(
            &doc,
            vec![op("_continuum/users", Action::Delete)]
        )));
        assert!(refused(judged(
            &doc,
            vec![op("_continuum/users/alice/caps", Action::Other)]
        )));
        // Elsewhere: as without the policy.
        assert!(judged(&doc, vec![op("notes/x", Action::PutString("x".to_owned()))]).is_ok());
        assert!(refused(judged(&doc, vec![op("", Action::Nowhere)])));
    }

    /// Where values are declared sealed: only sealed ones, as declared, with or without
    /// a strict policy.
    #[test]
    fn sealed_values_as_declared() {
        use crate::access::sealed::testing::sealed_for;
        use crate::access::sshsig::PublicKey;
        let key = PublicKey([8; 32]);
        let mut doc = swarm(true);
        let mut alice = registry::entry("a", 2, &[(Vec::new(), &[Right::Write][..])]);
        alice["keys"] = json!({ "k": key.line() });
        write(&mut doc, "_continuum/users/alice", alice);
        write(
            &mut doc,
            "_continuum/access/sealed",
            json!([{"path": ["secrets", "*"], "readers": ["alice"]}]),
        );
        let judged = |ops: Vec<Op>| {
            let deps = doc.get_heads();
            let touched: BTreeSet<Path> = ops.iter().map(|op| op.path.clone()).collect();
            judge(
                &doc,
                Epoch::GENESIS,
                &Change {
                    hash: ChangeHash([9; 32]),
                    deps: &deps,
                    seen: &deps,
                    committer: Some("a"),
                    user: Some("alice"),
                    paths: &touched,
                    ops: &ops,
                },
            )
        };
        let op = |at: &str, action: Action| Op {
            path: path(at),
            action,
        };
        let sealed = sealed_for(&[key]);
        assert!(judged(vec![op("secrets/db", Action::PutString(sealed))]).is_ok());
        assert!(judged(vec![op("secrets/db", Action::Delete)]).is_ok());
        assert!(refused(judged(vec![op(
            "secrets/db",
            Action::PutString("hunter2".to_owned())
        )])));
        let stray = sealed_for(&[key, PublicKey([9; 32])]);
        assert!(refused(judged(vec![op(
            "secrets/db",
            Action::PutString(stray)
        )])));
        assert!(refused(judged(vec![op("secrets/db", Action::MakeMap)])));
        assert!(refused(judged(vec![op(
            "secrets/db/password",
            Action::Other
        )])));
        assert!(judged(vec![op("notes/x", Action::PutString("plain".to_owned()))]).is_ok());
    }

    /// Written before the policy: judged by none, whatever it does; from the policy on,
    /// by the rules.
    #[test]
    fn before_the_policy() {
        let mut doc = Document::new();
        write(&mut doc, "_continuum/swarm", json!("s"));
        write(&mut doc, "_continuum/members/a", json!({"since": 1}));
        write(
            &mut doc,
            "_continuum/users/alice",
            registry::entry("a", 1, &[]),
        );
        assert!(judged(&doc, "stranger", Some("mallory"), &["notes/x"]).is_ok());
        write(&mut doc, "_continuum/access/policy", json!({"version": 1}));
        assert!(refused(judged(
            &doc,
            "stranger",
            Some("mallory"),
            &["notes/x"]
        )));
        // A policy this node doesn't know: judged by none either.
        write(&mut doc, "_continuum/access/policy", json!({"version": 9}));
        assert!(judged(&doc, "stranger", Some("mallory"), &["notes/x"]).is_ok());
    }

    /// A map made on the way to what is written, where there was none: judged by what is
    /// written within it; one made where there is one, or holding nothing written, as
    /// any write there.
    #[test]
    fn maps_made_on_the_way() {
        let mut doc = swarm(true);
        write(
            &mut doc,
            "_continuum/users/bob",
            registry::entry("a", 2, &[(path("servers/eu"), &[Right::Write][..])]),
        );
        let judged_ops = |doc: &Document, ops: Vec<Op>| {
            let deps = doc.get_heads();
            let touched: BTreeSet<Path> = ops.iter().map(|op| op.path.clone()).collect();
            judge(
                doc,
                Epoch::GENESIS,
                &Change {
                    hash: ChangeHash([9; 32]),
                    deps: &deps,
                    seen: &deps,
                    committer: Some("a"),
                    user: Some("bob"),
                    paths: &touched,
                    ops: &ops,
                },
            )
        };
        let op = |at: &str, action: Action| Op {
            path: path(at),
            action,
        };
        let first = vec![
            op("servers", Action::MakeMap),
            op("servers/eu", Action::MakeMap),
            op("servers/eu/0", Action::Other),
        ];
        assert!(judged_ops(&doc, first).is_ok());
        // Nothing written within: a map bob may not make.
        assert!(refused(judged_ops(
            &doc,
            vec![op("servers", Action::MakeMap)]
        )));
        // Within it, where bob may not write.
        assert!(refused(judged_ops(
            &doc,
            vec![
                op("servers", Action::MakeMap),
                op("servers/us", Action::Other)
            ]
        )));
        // Where there is one already: replacing it.
        write(&mut doc, "servers", json!({"us": 1}));
        assert!(refused(judged_ops(
            &doc,
            vec![
                op("servers", Action::MakeMap),
                op("servers/eu", Action::MakeMap),
                op("servers/eu/0", Action::Other)
            ]
        )));
    }

    /// Roots: the first change of a swarm's first epoch, a later epoch's snapshot.
    #[test]
    fn roots() {
        let root = |doc: &Document, epoch: Epoch, hash: [u8; 32]| {
            let touched = paths(&["_continuum/swarm"]);
            judge(
                doc,
                epoch,
                &Change {
                    hash: ChangeHash(hash),
                    deps: &[],
                    seen: &[],
                    committer: None,
                    user: None,
                    paths: &touched,
                    ops: &[],
                },
            )
        };
        assert!(root(&Document::new(), Epoch::GENESIS, [1; 32]).is_ok());
        assert!(refused(root(&swarm(false), Epoch::GENESIS, [1; 32])));
        // The first epoch's, judged again in a document that holds it: its root.
        let held = swarm(false);
        let first = held.get_changes(&[])[0].hash();
        assert!(root(&held, Epoch::GENESIS, first.0).is_ok());
        let epoch = Epoch {
            generation: 3,
            id: [5; 32],
        };
        assert!(root(&swarm(false), epoch, [5; 32]).is_ok());
        assert!(refused(root(&swarm(false), epoch, [6; 32])));
    }
}