blue_lang_proc/

receipt.rs

//! What an actor or a run is held to, what it did through the host, and the
//! receipt that says so.
//!
//! Four pieces a node shares with the runtime that builds it:
//!
//! - [`Frame`]: the hold as its artifacts name it: the host capabilities
//!   granted from the host, those a pure provider stands in for, and those
//!   withheld (a breach). Written into a crash trace and into a receipt.
//! - [`HostIo`]: one ledger of host calls per node. The runtime's counting
//!   shim (`blue_lang_runtime::Hold::bind`) tallies a call through a granted
//!   host name; the node says whose call it is by switching the ledger's
//!   current process with every slice. A name the hold withholds or provides
//!   gets no shim, so a pure frame counts nothing by construction.
//! - [`Identities`]: each definition key's `def_hash`, computed only when an
//!   artifact asks for one.
//! - [`Places`]: each definition key's file and text, read only when a crash
//!   asks where its breaching call is.
//!
//! ## Format `blue-receipt`, versions 1, 2 and 3
//!
//! One canonical JSON object (keys sorted, no whitespace), named by the
//! BLAKE3 hash of its bytes (`blue_lang_runtime::receipt` writes and
//! verifies it):
//!
//! ```text
//! { "def_hash": "b3:…" | null, "definition": "%root/reader" | "%run" | null,
//!   "exit": { "kind": "normal" | "crashed" | "runaway" | "killed" | "fatal" | "refused", "text": "…" },
//!   "format": "blue-receipt",
//!   "frame": { "granted": [LABEL…], "host_io": n, "withheld": [LABEL…] },
//!   "incarnation": n, "pid": n,
//!   "provided": [{ "provider": "deterministic-stepped", …, "for": [PACKAGE…] }…],
//!   "subject": "actor" | "run", "version": 1 }
//! ```
//!
//! Version 2 is version 1 with two more keys, written only for a
//! `spawn_server` incarnation, whose state the node holds:
//!
//! ```text
//! { …, "input_root": "b3:…", "output_root": "b3:…", …, "version": 2 }
//! ```
//!
//! `input_root` is the [`StateRoot`] of the state the incarnation began
//! with, before its first message; `output_root` that of the state after
//! the last message its handler returned from. A receipt without roots is
//! version 1, byte for byte as before version 2 existed, so the name of
//! every receipt a run wrote before stays the name it has.
//!
//! Version 3 is version 1 or 2 with `steps`, written only when the run asks
//! for the count (`blue run --receipt-steps`): the steps the incarnation's
//! VM charged, or the evaluation steps the run's own interpreter spent.
//!
//! ```text
//! { …, "steps": n, …, "version": 3 }
//! ```
//!
//! A count moves with the compiler's instruction count, so a receipt that
//! carries one is renamed by any change to the code blue emits; one that
//! does not ask keeps its version 1 or 2 bytes.
//!
//! Version 4 is version 1 or 3 with `carried`, written only for a plain
//! process that arrived from a held node with its host-call count: the
//! calls it made before the move, which `frame.host_io` includes, and the
//! `blue-image` they came in. A count smaller than what came is refused.
//!
//! ```text
//! { …, "carried": { "host_io": n, "image": "b3:…" }, …, "version": 4 }
//! ```
//!
//! Version 5 is version 2 or 3 with `carried`, written only for a
//! `spawn_server` incarnation that arrived from a held node with its
//! host-call count and the root of the state it began with there: its
//! `input_root` is that root, which `carried.input_root` names again, so the
//! receipt covers the incarnation from its first message on the first node
//! to its last on the node it ended on. A carried root that is not the
//! receipt's `input_root` is refused, as is a count smaller than what came.
//!
//! ```text
//! { …, "carried": { "host_io": n, "image": "b3:…", "input_root": "b3:…" },
//!   "input_root": "b3:…", "output_root": "b3:…", …, "version": 5 }
//! ```

use std::collections::BTreeMap;
use std::sync::{Arc, Mutex, MutexGuard};

use blue_lang_waku::{Capability, Provided};
use serde_json::{json, Value as Json};

use crate::Pid;

/// The format name every receipt carries.
pub const FORMAT: &str = "blue-receipt";
/// The version a receipt with state roots carries.
pub const VERSION: u64 = 2;
/// The version a receipt without state roots carries.
pub const VERSION_UNROOTED: u64 = 1;
pub const VERSION_STEPPED: u64 = 3;
pub const VERSION_CARRIED: u64 = 4;
pub const VERSION_CARRIED_ROOTED: u64 = 5;
/// Every version [`check`] accepts.
pub const READS: [u64; 5] = [
    VERSION_UNROOTED,
    VERSION,
    VERSION_STEPPED,
    VERSION_CARRIED,
    VERSION_CARRIED_ROOTED,
];
/// The keys a server's receipt has from version 2 on.
pub const ROOT_KEYS: [&str; 2] = ["input_root", "output_root"];
pub const STEPS_KEY: &str = "steps";
pub const CARRIED_KEY: &str = "carried";

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CarriedIo {
    pub image: String,
    pub host_io: u64,
    pub input_root: Option<String>,
}

impl CarriedIo {
    fn to_json(&self) -> Json {
        let mut j = json!({"host_io": self.host_io, "image": self.image});
        if let Some(root) = &self.input_root {
            j["input_root"] = json!(root);
        }
        j
    }
}

/// The root of a server's state: `b3:` and the BLAKE3 hash of its canonical
/// JSON. The runtime computes it (`blue_lang_runtime::json::state_root`); a
/// node only calls it.
pub type StateRoot = fn(&tatara_lisp_eval::Value) -> String;

/// A server incarnation's state roots: before its first message, and after
/// the last one its handler returned from.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Roots {
    pub input: String,
    pub output: String,
}

pub(crate) fn is_hash(text: &str) -> bool {
    text.strip_prefix("b3:").is_some_and(|hex| {
        hex.len() == 64
            && hex
                .bytes()
                .all(|b| b.is_ascii_digit() || (b'a'..=b'f').contains(&b))
    })
}

/// Whether `receipt` has the form its `version` names: version 1 carries no
/// state root, version 2 carries both, each `b3:` and 64 lowercase hex
/// digits, version 3 carries `steps`, a count, with both roots or neither,
/// version 4 carries `carried`, no root, and `steps` or not, and version 5
/// carries both roots and `carried` with the `input_root` the receipt names,
/// and `steps` or not.
///
/// # Errors
///
/// Naming a version this blue does not read, or the root, count or carried
/// block that is missing, present where it may not be, not a hash or a
/// count, or more than the receipt's own count.
pub fn check(receipt: &Json) -> Result<(), String> {
    let version = receipt.get("version").and_then(Json::as_u64);
    let (rooted, stepped, carried) = match version {
        Some(VERSION_UNROOTED) => (false, false, false),
        Some(VERSION) => (true, false, false),
        Some(VERSION_STEPPED) => (
            ROOT_KEYS.iter().any(|k| receipt.get(*k).is_some()),
            true,
            false,
        ),
        Some(VERSION_CARRIED) => (false, receipt.get(STEPS_KEY).is_some(), true),
        Some(VERSION_CARRIED_ROOTED) => (true, receipt.get(STEPS_KEY).is_some(), true),
        _ => {
            return Err(format!(
                "{FORMAT} version {}; this blue reads versions {} to {VERSION_CARRIED_ROOTED}",
                receipt.get("version").unwrap_or(&Json::Null),
                READS[0]
            ))
        }
    };
    let v = version.unwrap_or_default();
    for key in ROOT_KEYS {
        match (rooted, receipt.get(key)) {
            (false, None) => {}
            (false, Some(_)) => {
                return Err(format!(
                    "a version {v} receipt carries `{key}`, which only a server's receipt of version {VERSION}, {VERSION_STEPPED} or {VERSION_CARRIED_ROOTED} has"
                ))
            }
            (true, None) => return Err(format!("a version {v} receipt without `{key}`")),
            (true, Some(root)) if !root.as_str().is_some_and(is_hash) => {
                return Err(format!("`{key}` is {root}, not b3: and 64 hex digits"))
            }
            (true, Some(_)) => {}
        }
    }
    check_carried(receipt, v, carried, rooted && carried)?;
    match (stepped, receipt.get(STEPS_KEY)) {
        (false, Some(_)) => Err(format!(
            "a version {v} receipt carries `{STEPS_KEY}`, which only version {VERSION_STEPPED}, {VERSION_CARRIED} or {VERSION_CARRIED_ROOTED} has"
        )),
        (true, None) => Err(format!("a version {v} receipt without `{STEPS_KEY}`")),
        (true, Some(n)) if n.as_u64().is_none() => {
            Err(format!("`{STEPS_KEY}` is {n}, not a count"))
        }
        _ => Ok(()),
    }
}

fn check_carried(receipt: &Json, v: u64, carried: bool, rooted: bool) -> Result<(), String> {
    let c = match (carried, receipt.get(CARRIED_KEY)) {
        (false, None) => return Ok(()),
        (false, Some(_)) => {
            return Err(format!(
                "a version {v} receipt carries `{CARRIED_KEY}`, which only version {VERSION_CARRIED} or {VERSION_CARRIED_ROOTED} has"
            ))
        }
        (true, None) => return Err(format!("a version {v} receipt without `{CARRIED_KEY}`")),
        (true, Some(c)) => c,
    };
    let field = |k: &str| c.get(k).unwrap_or(&Json::Null);
    let image = field("image")
        .as_str()
        .filter(|h| is_hash(h))
        .ok_or_else(|| {
            format!(
                "`{CARRIED_KEY}.image` is {}, not b3: and 64 hex digits",
                field("image")
            )
        })?;
    let came = field("host_io").as_u64().ok_or_else(|| {
        format!(
            "`{CARRIED_KEY}.host_io` is {}, not a count",
            field("host_io")
        )
    })?;
    let counted = receipt
        .get("frame")
        .and_then(|f| f.get("host_io"))
        .and_then(Json::as_u64)
        .unwrap_or(0);
    let pid = receipt.get("pid").unwrap_or(&Json::Null);
    if counted < came {
        return Err(format!(
            "its host-call count is cut: process {pid} brought a count of {came} in image {image}, and the receipt counts {counted}"
        ));
    }
    let brought = match (rooted, c.get("input_root")) {
        (false, None) => return Ok(()),
        (false, Some(_)) => {
            return Err(format!(
                "a version {v} receipt's `{CARRIED_KEY}` names an `input_root`, which only version {VERSION_CARRIED_ROOTED} has"
            ))
        }
        (true, None) => {
            return Err(format!(
                "a version {v} receipt whose `{CARRIED_KEY}` names no `input_root`"
            ))
        }
        (true, Some(r)) => r.as_str().filter(|h| is_hash(h)).ok_or_else(|| {
            format!("`{CARRIED_KEY}.input_root` is {r}, not b3: and 64 hex digits")
        })?,
    };
    let named = receipt.get("input_root").unwrap_or(&Json::Null);
    if named.as_str() != Some(brought) {
        return Err(format!(
            "its input root is not the one it brought: process {pid} brought {brought} in image {image}, and the receipt names {named}"
        ));
    }
    Ok(())
}

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

/// A hold as an artifact names it.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Frame {
    /// Host capabilities granted from the host.
    pub granted: Vec<Capability>,
    /// The pure providers standing in for host capabilities, each for the
    /// whole program or, under `for`, for the packages it names.
    pub provided: Vec<Provided>,
    /// Host capabilities neither granted nor provided: a call is a breach.
    pub withheld: Vec<Capability>,
}

fn labels(caps: &[Capability]) -> Json {
    Json::Array(caps.iter().map(|c| json!(c.label())).collect())
}

fn capability(label: &str) -> Option<Capability> {
    Capability::host_effects()
        .into_iter()
        .find(|c| c.label() == label)
}

fn capabilities(j: Option<&Json>, what: &str) -> Result<Vec<Capability>, String> {
    j.and_then(Json::as_array)
        .ok_or_else(|| format!("a hold without `{what}`"))?
        .iter()
        .map(|l| {
            l.as_str()
                .and_then(capability)
                .ok_or_else(|| format!("`{l}` in `{what}` is not a host capability"))
        })
        .collect()
}

impl Frame {
    /// The receipt's frame block: `{"granted":[…],"withheld":[…],"host_io":n}`.
    #[must_use]
    pub fn block(&self, host_io: u64) -> Json {
        json!({
            "granted": labels(&self.granted),
            "withheld": labels(&self.withheld),
            "host_io": host_io,
        })
    }

    /// The providers as the lock records them: the provider, its settings,
    /// and `for` with the packages it serves when it is scoped.
    #[must_use]
    pub fn provided_json(&self) -> Json {
        Json::Array(
            self.provided
                .iter()
                .map(|p| serde_json::to_value(p).unwrap_or(Json::Null))
                .collect(),
        )
    }

    /// The hold as a crash trace writes it.
    #[must_use]
    pub fn to_json(&self) -> Json {
        json!({
            "granted": labels(&self.granted),
            "provided": self.provided_json(),
            "withheld": labels(&self.withheld),
        })
    }

    /// Read a hold back.
    ///
    /// # Errors
    ///
    /// When a list is missing, a label names no host capability, or a
    /// provider does not parse.
    pub fn from_json(j: &Json) -> Result<Self, String> {
        let provided = j
            .get("provided")
            .and_then(Json::as_array)
            .ok_or("a hold without `provided`")?
            .iter()
            .map(|p| serde_json::from_value(p.clone()).map_err(|e| format!("a provider: {e}")))
            .collect::<Result<_, _>>()?;
        Ok(Self {
            granted: capabilities(j.get("granted"), "granted")?,
            provided,
            withheld: capabilities(j.get("withheld"), "withheld")?,
        })
    }

    /// Every host name the hold withholds, with its capability.
    #[must_use]
    pub fn withheld_names(&self) -> Vec<(&'static str, Capability)> {
        self.withheld
            .iter()
            .flat_map(|c| c.names().into_iter().map(move |n| (n, *c)))
            .collect()
    }
}

#[derive(Debug, Default)]
struct Ledger {
    current: Pid,
    total: u64,
    by_pid: BTreeMap<Pid, u64>,
}

/// Host calls made through granted host names, per process of one node.
#[derive(Clone, Debug, Default)]
pub struct HostIo(Arc<Mutex<Ledger>>);

impl HostIo {
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// One host call, by the process running now.
    pub fn tally(&self) {
        let mut l = locked(&self.0);
        l.total += 1;
        let pid = crate::scheduling::lane().unwrap_or(l.current);
        *l.by_pid.entry(pid).or_default() += 1;
    }

    /// Every call tallied, by every process.
    #[must_use]
    pub fn total(&self) -> u64 {
        locked(&self.0).total
    }

    /// The calls `pid` made since its incarnation began.
    #[must_use]
    pub fn of(&self, pid: Pid) -> u64 {
        locked(&self.0).by_pid.get(&pid).copied().unwrap_or(0)
    }

    /// `pid` runs now: what is tallied is its.
    pub fn enter(&self, pid: Pid) {
        locked(&self.0).current = pid;
    }

    /// `pid`'s count, which starts again at zero.
    pub fn take(&self, pid: Pid) -> u64 {
        locked(&self.0).by_pid.remove(&pid).unwrap_or(0)
    }

    pub fn carry(&self, pid: Pid, calls: u64) {
        *locked(&self.0).by_pid.entry(pid).or_default() += calls;
    }
}

type Deferred<T> = Box<dyn FnOnce() -> T + Send>;

enum Table<T> {
    Unknown,
    Deferred(Deferred<T>),
    Known(T),
}

/// A table the runtime hands a node unfinished: computed the first time an
/// artifact asks, and never when none does.
struct Lazy<T>(Arc<Mutex<Table<T>>>);

impl<T> Clone for Lazy<T> {
    fn clone(&self) -> Self {
        Self(Arc::clone(&self.0))
    }
}

impl<T> Default for Lazy<T> {
    fn default() -> Self {
        Self(Arc::new(Mutex::new(Table::Unknown)))
    }
}

impl<T> Lazy<T> {
    fn defer(&self, compute: impl FnOnce() -> T + Send + 'static) {
        *locked(&self.0) = Table::Deferred(Box::new(compute));
    }

    fn read<R>(&self, f: impl FnOnce(&T) -> Option<R>) -> Option<R> {
        let mut state = locked(&self.0);
        if let Table::Deferred(_) = &*state {
            if let Table::Deferred(compute) = std::mem::replace(&mut *state, Table::Unknown) {
                *state = Table::Known(compute());
            }
        }
        match &*state {
            Table::Known(table) => f(table),
            Table::Unknown | Table::Deferred(_) => None,
        }
    }

    fn state(&self) -> &'static str {
        match &*locked(&self.0) {
            Table::Unknown => "unknown",
            Table::Deferred(_) => "deferred",
            Table::Known(_) => "known",
        }
    }
}

/// Each definition key's `def_hash` (`b3:<hex>`), computed on first ask.
#[derive(Clone, Default)]
pub struct Identities(Lazy<BTreeMap<String, String>>);

impl std::fmt::Debug for Identities {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "Identities({})", self.0.state())
    }
}

impl Identities {
    /// Compute the table with `hash` when the first identity is asked for.
    pub fn defer(&self, hash: impl FnOnce() -> BTreeMap<String, String> + Send + 'static) {
        self.0.defer(hash);
    }

    /// The `def_hash` of the definition bound to `key`, if it has one.
    #[must_use]
    pub fn of(&self, key: &str) -> Option<String> {
        self.0.read(|table| table.get(key).cloned())
    }
}

/// The file a definition was read from: the name a reader opens it by, and
/// the text its spans index.
#[derive(Clone, Debug)]
pub struct Source {
    pub file: String,
    pub text: Arc<str>,
}

/// A position a reader can open: a file, and a 1-based line and column.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Place {
    pub file: String,
    pub line: usize,
    pub column: usize,
}

impl std::fmt::Display for Place {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}:{}:{}", self.file, self.line, self.column)
    }
}

/// Each definition key's [`Source`], computed on first ask: what turns a
/// span in a crashed process's code into a [`Place`].
#[derive(Clone, Default)]
pub struct Places(Lazy<BTreeMap<String, Source>>);

impl std::fmt::Debug for Places {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "Places({})", self.0.state())
    }
}

impl Places {
    /// Compute the table with `read` when the first place is asked for.
    pub fn defer(&self, read: impl FnOnce() -> BTreeMap<String, Source> + Send + 'static) {
        self.0.defer(read);
    }

    /// Where `span` is, inside the definition bound to `key`. `None` for a
    /// synthetic span, a key with no source, or a span past the end of the
    /// key's file: an offset outside the file is proof it indexes another
    /// one, and answering it anyway would name a line that is not the place.
    #[must_use]
    pub fn locate(&self, key: &str, span: tatara_lisp::Span) -> Option<Place> {
        if span.is_synthetic() {
            return None;
        }
        self.0.read(|table| {
            let source = table.get(key)?;
            (span.end <= source.text.len()).then(|| {
                let (line, column) = tatara_lisp::Span::line_col(&source.text, span.start);
                Place {
                    file: source.file.clone(),
                    line,
                    column,
                }
            })
        })
    }
}

/// What a receipt attests about.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Subject {
    /// One incarnation of a process.
    Actor { pid: Pid, incarnation: usize },
    /// A whole run, its root and every process it started.
    Run,
}

/// One actor's or one run's account of itself.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Receipt {
    pub subject: Subject,
    /// The definition key it ran.
    pub definition: Option<String>,
    /// That definition's `def_hash`.
    pub def_hash: Option<String>,
    pub frame: Frame,
    /// Calls through granted host names.
    pub host_io: u64,
    pub exit_kind: String,
    pub exit_text: String,
    /// A server incarnation's state roots; `None` for any other subject,
    /// and then the receipt is version 1.
    pub roots: Option<Roots>,
    pub steps: Option<u64>,
    pub carried: Option<CarriedIo>,
}

impl Receipt {
    /// This receipt as `blue-receipt` JSON: version 2 with its roots, version
    /// 1 without.
    #[must_use]
    pub fn to_json(&self) -> Json {
        let (subject, pid, incarnation) = match self.subject {
            Subject::Actor { pid, incarnation } => ("actor", pid.0, incarnation),
            Subject::Run => ("run", crate::ROOT.0, 0),
        };
        let mut j = json!({
            "format": FORMAT,
            "version": VERSION_UNROOTED,
            "subject": subject,
            "pid": pid,
            "incarnation": incarnation,
            "definition": self.definition,
            "def_hash": self.def_hash,
            "exit": { "kind": self.exit_kind, "text": self.exit_text },
            "frame": self.frame.block(self.host_io),
            "provided": self.frame.provided_json(),
        });
        if let Some(roots) = &self.roots {
            j["version"] = json!(VERSION);
            j["input_root"] = json!(roots.input);
            j["output_root"] = json!(roots.output);
        }
        if let Some(steps) = self.steps {
            j["version"] = json!(VERSION_STEPPED);
            j[STEPS_KEY] = json!(steps);
        }
        if let Some(c) = &self.carried {
            j["version"] = json!(if c.input_root.is_some() {
                VERSION_CARRIED_ROOTED
            } else {
                VERSION_CARRIED
            });
            j[CARRIED_KEY] = c.to_json();
        }
        j
    }

    /// The bytes a receipt is: its JSON, canonical.
    #[must_use]
    pub fn bytes(&self) -> Vec<u8> {
        canonical(&self.to_json()).into_bytes()
    }
}

/// Where a node hands each actor's receipt.
pub type ReceiptSink = Arc<dyn Fn(&Receipt) + Send + Sync>;

/// `j` with every object's keys sorted and no whitespace: one text per value.
#[must_use]
pub fn canonical(j: &Json) -> String {
    let mut out = String::new();
    write_canonical(j, &mut out);
    out
}

fn write_canonical(j: &Json, out: &mut String) {
    match j {
        Json::Object(m) => {
            let mut keys: Vec<&String> = m.keys().collect();
            keys.sort();
            out.push('{');
            for (i, k) in keys.into_iter().enumerate() {
                if i > 0 {
                    out.push(',');
                }
                out.push_str(&Json::String(k.clone()).to_string());
                out.push(':');
                write_canonical(&m[k], out);
            }
            out.push('}');
        }
        Json::Array(items) => {
            out.push('[');
            for (i, v) in items.iter().enumerate() {
                if i > 0 {
                    out.push(',');
                }
                write_canonical(v, out);
            }
            out.push(']');
        }
        other => out.push_str(&other.to_string()),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn frame() -> Frame {
        Frame {
            granted: vec![Capability::FileSystem],
            provided: vec![
                blue_lang_waku::Provision::DeterministicStepped {
                    at_ms: 5,
                    step_ms: 1,
                }
                .into(),
                Provided {
                    provision: blue_lang_waku::Provision::NullSink,
                    scope: Some(std::collections::BTreeSet::from(["kazu".to_string()])),
                },
            ],
            withheld: vec![
                Capability::Process,
                Capability::Environment,
                Capability::Network,
                Capability::Entropy,
            ],
        }
    }

    #[test]
    fn the_frame_block_is_granted_withheld_and_host_io_and_nothing_else() {
        let block = frame().block(3);
        let keys: Vec<&String> = block.as_object().expect("object").keys().collect();
        let mut sorted = keys.clone();
        sorted.sort();
        assert_eq!(sorted, ["granted", "host_io", "withheld"]);
        assert_eq!(
            canonical(&block),
            r#"{"granted":["filesystem"],"host_io":3,"withheld":["process","environment","network","entropy"]}"#
        );
    }

    #[test]
    fn a_hold_survives_the_trace_format() {
        let f = frame();
        assert_eq!(Frame::from_json(&f.to_json()).expect("parse"), f);
        let mut bad = f.to_json();
        bad["withheld"] = json!(["disk"]);
        assert!(Frame::from_json(&bad).unwrap_err().contains("disk"));
        assert!(Frame::from_json(&json!({})).is_err());
    }

    #[test]
    fn withheld_names_are_every_name_of_every_withheld_capability() {
        let names = frame().withheld_names();
        assert!(names.contains(&("getenv", Capability::Environment)));
        assert!(names.iter().all(|(_, c)| *c != Capability::FileSystem));
        assert_eq!(
            names.len(),
            frame()
                .withheld
                .iter()
                .map(|c| c.names().len())
                .sum::<usize>()
        );
        assert!(Frame::default().withheld_names().is_empty());
    }

    #[test]
    fn the_ledger_tallies_to_the_process_running_and_takes_per_incarnation() {
        let io = HostIo::new();
        io.tally();
        io.enter(Pid(3));
        io.tally();
        io.tally();
        io.enter(crate::ROOT);
        io.tally();
        assert_eq!(io.total(), 4);
        assert_eq!(io.of(crate::ROOT), 2);
        assert_eq!(io.of(Pid(3)), 2);
        assert_eq!(io.take(Pid(3)), 2);
        assert_eq!(io.of(Pid(3)), 0);
        assert_eq!(io.total(), 4, "the run total keeps every call");
        assert_eq!(HostIo::new().total(), 0);
    }

    #[test]
    fn identities_are_hashed_once_and_only_when_asked() {
        let ids = Identities::default();
        assert_eq!(ids.of("%root/f"), None);
        let calls = Arc::new(Mutex::new(0));
        let c = Arc::clone(&calls);
        ids.defer(move || {
            *locked(&c) += 1;
            BTreeMap::from([("%root/f".to_string(), "b3:00".to_string())])
        });
        assert_eq!(*locked(&calls), 0);
        assert_eq!(ids.of("%root/f").as_deref(), Some("b3:00"));
        assert_eq!(ids.clone().of("%root/g"), None);
        assert_eq!(*locked(&calls), 1);
    }

    #[test]
    fn a_place_is_read_once_and_only_inside_its_own_file() {
        let places = Places::default();
        let at = tatara_lisp::Span::new(10, 14);
        assert_eq!(places.locate("%root/f", at), None);
        let calls = Arc::new(Mutex::new(0));
        let c = Arc::clone(&calls);
        places.defer(move || {
            *locked(&c) += 1;
            BTreeMap::from([(
                "%root/f".to_string(),
                Source {
                    file: "w.b".into(),
                    text: Arc::from("def f()\n  g(1)\nend\n"),
                },
            )])
        });
        assert_eq!(*locked(&calls), 0);
        let place = places.locate("%root/f", at).expect("in its file");
        assert_eq!(place.to_string(), "w.b:2:3");
        assert_eq!(
            places.locate("%root/f", tatara_lisp::Span::new(10, 99)),
            None
        );
        assert_eq!(
            places.locate("%root/f", tatara_lisp::Span::synthetic()),
            None
        );
        assert_eq!(places.clone().locate("%root/g", at), None);
        assert_eq!(*locked(&calls), 1);
    }

    #[test]
    fn canonical_text_sorts_keys_at_every_depth_and_has_no_whitespace() {
        let j = json!({"b": [ {"z": 1, "a": "x y"} ], "a": null});
        assert_eq!(canonical(&j), r#"{"a":null,"b":[{"a":"x y","z":1}]}"#);
        let r = Receipt {
            subject: Subject::Actor {
                pid: Pid(2),
                incarnation: 1,
            },
            definition: Some("%root/w".into()),
            def_hash: Some("b3:ab".into()),
            frame: frame(),
            host_io: 7,
            exit_kind: "normal".into(),
            exit_text: "normal".into(),
            roots: None,
            steps: None,
            carried: None,
        };
        let text = String::from_utf8(r.bytes()).expect("utf8");
        assert!(!text.contains(' ') && !text.contains('\n'), "{text}");
        let back: Json = serde_json::from_str(&text).expect("json");
        assert_eq!(canonical(&back), text);
        assert_eq!(back["frame"]["host_io"], 7);
        assert_eq!(back["subject"], "actor");
        assert_eq!(back["provided"][0]["provider"], "deterministic-stepped");
        assert!(
            back["provided"][0].get("for").is_none(),
            "a whole-program provider"
        );
        assert_eq!(
            back["provided"][1],
            json!({"provider": "null-sink", "for": ["kazu"]})
        );
    }

    const V1: &str = r#"{"def_hash":"b3:ab","definition":"%root/w","exit":{"kind":"normal","text":"normal"},"format":"blue-receipt","frame":{"granted":["filesystem"],"host_io":7,"withheld":["process","environment","network","entropy"]},"incarnation":1,"pid":2,"provided":[{"at_ms":5,"provider":"deterministic-stepped","step_ms":1},{"for":["kazu"],"provider":"null-sink"}],"subject":"actor","version":1}"#;

    fn actor(roots: Option<Roots>) -> Receipt {
        Receipt {
            subject: Subject::Actor {
                pid: Pid(2),
                incarnation: 1,
            },
            definition: Some("%root/w".into()),
            def_hash: Some("b3:ab".into()),
            frame: frame(),
            host_io: 7,
            exit_kind: "normal".into(),
            exit_text: "normal".into(),
            roots,
            steps: None,
            carried: None,
        }
    }

    fn root(c: char) -> String {
        format!("b3:{}", c.to_string().repeat(64))
    }

    #[test]
    fn a_receipt_without_roots_is_the_version_1_receipt_byte_for_byte() {
        let r = actor(None);
        assert_eq!(String::from_utf8(r.bytes()).expect("utf8"), V1);
        assert_eq!(check(&r.to_json()), Ok(()));
    }

    #[test]
    fn a_receipt_with_roots_is_version_2_and_without_them_is_version_1_again() {
        let r = actor(Some(Roots {
            input: root('a'),
            output: root('b'),
        }));
        let j = r.to_json();
        assert_eq!(j["version"], VERSION);
        assert_eq!(j["input_root"], root('a'));
        assert_eq!(j["output_root"], root('b'));
        assert_eq!(check(&j), Ok(()));
        let mut stripped = j.clone();
        for key in ROOT_KEYS {
            stripped.as_object_mut().expect("object").remove(key);
        }
        stripped["version"] = json!(VERSION_UNROOTED);
        assert_eq!(canonical(&stripped), V1);
    }

    #[test]
    fn check_reads_versions_1_and_2_and_refuses_a_root_out_of_place() {
        let v1 = actor(None).to_json();
        let v2 = actor(Some(Roots {
            input: root('0'),
            output: root('f'),
        }))
        .to_json();
        let edited = |base: &Json, key: &str, value: Json| {
            let mut j = base.clone();
            j[key] = value;
            j
        };
        let refused = |j: &Json, why: &str| {
            let e = check(j).expect_err(why);
            assert!(e.contains(why), "{e}");
        };
        refused(
            &edited(&v1, "input_root", json!(root('a'))),
            "carries `input_root`",
        );
        refused(&edited(&v1, "version", json!(6)), "reads versions 1 to 5");
        refused(
            &edited(&v2, "output_root", json!("b3:00")),
            "not b3: and 64 hex",
        );
        refused(
            &edited(&v2, "input_root", json!(root('A'))),
            "not b3: and 64 hex",
        );
        let mut half = v2.clone();
        half.as_object_mut().expect("object").remove("output_root");
        refused(&half, "without `output_root`");
        let mut unversioned = v1.clone();
        unversioned
            .as_object_mut()
            .expect("object")
            .remove("version");
        refused(&unversioned, "reads versions 1 to 5");
    }

    const V2: &str = r#"{"def_hash":"b3:ab","definition":"%root/w","exit":{"kind":"normal","text":"normal"},"format":"blue-receipt","frame":{"granted":["filesystem"],"host_io":7,"withheld":["process","environment","network","entropy"]},"incarnation":1,"input_root":"b3:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","output_root":"b3:bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb","pid":2,"provided":[{"at_ms":5,"provider":"deterministic-stepped","step_ms":1},{"for":["kazu"],"provider":"null-sink"}],"subject":"actor","version":2}"#;

    fn rooted() -> Option<Roots> {
        Some(Roots {
            input: root('a'),
            output: root('b'),
        })
    }

    fn counted(roots: Option<Roots>, steps: u64) -> Receipt {
        Receipt {
            steps: Some(steps),
            ..actor(roots)
        }
    }

    fn uncounted(mut j: Json, version: u64) -> String {
        j.as_object_mut().expect("object").remove(STEPS_KEY);
        j["version"] = json!(version);
        canonical(&j)
    }

    #[test]
    fn a_receipt_that_counts_no_steps_keeps_its_version_1_or_2_bytes() {
        assert_eq!(String::from_utf8(actor(None).bytes()).expect("utf8"), V1);
        assert_eq!(
            String::from_utf8(actor(rooted()).bytes()).expect("utf8"),
            V2
        );
        for text in [V1, V2] {
            let j: Json = serde_json::from_str(text).expect("json");
            assert_eq!(check(&j), Ok(()), "{text}");
        }
    }

    #[test]
    fn a_receipt_with_steps_is_version_3_and_without_them_its_old_bytes() {
        let run = counted(None, 42).to_json();
        assert_eq!(run["version"], VERSION_STEPPED);
        assert_eq!(run[STEPS_KEY], 42);
        assert!(run.get("input_root").is_none());
        assert_eq!(check(&run), Ok(()));
        assert_eq!(uncounted(run, VERSION_UNROOTED), V1);
        let server = counted(rooted(), 0).to_json();
        assert_eq!(server["version"], VERSION_STEPPED);
        assert_eq!(server[STEPS_KEY], 0);
        assert_eq!(server["input_root"], root('a'));
        assert_eq!(check(&server), Ok(()));
        assert_eq!(uncounted(server, VERSION), V2);
    }

    #[test]
    fn check_reads_version_3_and_refuses_a_count_out_of_place() {
        let refused = |j: &Json, why: &str| {
            let e = check(j).expect_err(why);
            assert!(e.contains(why), "{why}: {e}");
        };
        let with = |base: Json, key: &str, value: Json| {
            let mut j = base;
            j[key] = value;
            j
        };
        let without = |base: Json, key: &str| {
            let mut j = base;
            j.as_object_mut().expect("object").remove(key);
            j
        };
        refused(
            &with(actor(None).to_json(), STEPS_KEY, json!(3)),
            "carries `steps`",
        );
        refused(
            &with(actor(rooted()).to_json(), STEPS_KEY, json!(3)),
            "carries `steps`",
        );
        refused(
            &without(counted(None, 1).to_json(), STEPS_KEY),
            "without `steps`",
        );
        refused(
            &with(counted(None, 1).to_json(), STEPS_KEY, json!(-1)),
            "not a count",
        );
        refused(
            &with(counted(None, 1).to_json(), STEPS_KEY, json!("1")),
            "not a count",
        );
        refused(
            &with(counted(None, 1).to_json(), STEPS_KEY, json!(1.5)),
            "not a count",
        );
        refused(
            &without(counted(rooted(), 1).to_json(), "input_root"),
            "without `input_root`",
        );
        refused(
            &with(
                counted(rooted(), 1).to_json(),
                "output_root",
                json!("b3:00"),
            ),
            "not b3: and 64 hex",
        );
    }

    fn moved(host_io: u64, came: u64) -> Receipt {
        Receipt {
            host_io,
            carried: Some(CarriedIo {
                image: root('c'),
                host_io: came,
                input_root: None,
            }),
            ..actor(None)
        }
    }

    #[test]
    fn a_receipt_with_carried_calls_is_version_4_and_a_cut_or_misplaced_block_is_refused_by_name() {
        let j = moved(7, 3).to_json();
        assert_eq!(j["version"], VERSION_CARRIED);
        assert_eq!(j[CARRIED_KEY], json!({"host_io": 3, "image": root('c')}));
        assert_eq!(check(&j), Ok(()));
        assert_eq!(check(&moved(3, 3).to_json()), Ok(()));
        let stepped = Receipt {
            steps: Some(9),
            ..moved(7, 3)
        }
        .to_json();
        assert_eq!(stepped["version"], VERSION_CARRIED);
        assert_eq!(check(&stepped), Ok(()));
        let mut uncarried = j.clone();
        uncarried
            .as_object_mut()
            .expect("object")
            .remove(CARRIED_KEY);
        uncarried["version"] = json!(VERSION_UNROOTED);
        assert_eq!(
            canonical(&uncarried),
            V1,
            "without the block, the version 1 bytes"
        );
        let refused = |j: &Json, why: &str| {
            let e = check(j).expect_err(why);
            assert!(e.contains(why), "{why}: {e}");
        };
        refused(
            &moved(2, 3).to_json(),
            &format!(
                "its host-call count is cut: process 2 brought a count of 3 in image {}, and the receipt counts 2",
                root('c')
            ),
        );
        let mut lowered = j.clone();
        lowered["version"] = json!(VERSION_STEPPED);
        refused(&lowered, "which only version 4 or 5 has");
        let mut bare = j.clone();
        bare.as_object_mut().expect("object").remove(CARRIED_KEY);
        refused(&bare, "a version 4 receipt without `carried`");
        let mut rooted4 = j.clone();
        rooted4["input_root"] = json!(root('a'));
        rooted4["output_root"] = json!(root('b'));
        refused(&rooted4, "carries `input_root`");
        for (key, bad, why) in [
            (
                "image",
                json!("b3:00"),
                "`carried.image` is \"b3:00\", not b3: and 64 hex digits",
            ),
            ("host_io", json!(-1), "`carried.host_io` is -1, not a count"),
        ] {
            let mut misfit = j.clone();
            misfit[CARRIED_KEY][key] = bad;
            refused(&misfit, why);
        }
        let mut named = j.clone();
        named[CARRIED_KEY]["input_root"] = json!(root('a'));
        refused(
            &named,
            "a version 4 receipt's `carried` names an `input_root`, which only version 5 has",
        );
    }

    fn served(host_io: u64, came: u64, brought: &str) -> Receipt {
        Receipt {
            host_io,
            carried: Some(CarriedIo {
                image: root('c'),
                host_io: came,
                input_root: Some(brought.to_string()),
            }),
            ..actor(rooted())
        }
    }

    #[test]
    fn a_moved_servers_receipt_is_version_5_and_a_root_it_did_not_bring_is_refused_by_name() {
        let j = served(7, 3, &root('a')).to_json();
        assert_eq!(j["version"], VERSION_CARRIED_ROOTED);
        assert_eq!(
            j[CARRIED_KEY],
            json!({"host_io": 3, "image": root('c'), "input_root": root('a')})
        );
        assert_eq!(
            (&j["input_root"], &j["output_root"]),
            (&json!(root('a')), &json!(root('b')))
        );
        assert_eq!(check(&j), Ok(()));
        let stepped = Receipt {
            steps: Some(9),
            ..served(7, 3, &root('a'))
        }
        .to_json();
        assert_eq!(stepped["version"], VERSION_CARRIED_ROOTED);
        assert_eq!(check(&stepped), Ok(()));
        let mut uncarried = j.clone();
        uncarried
            .as_object_mut()
            .expect("object")
            .remove(CARRIED_KEY);
        uncarried["version"] = json!(VERSION);
        assert_eq!(
            canonical(&uncarried),
            V2,
            "without the block, the version 2 bytes"
        );
        let refused = |j: &Json, why: &str| {
            let e = check(j).expect_err(why);
            assert!(e.contains(why), "{why}: {e}");
        };
        refused(
            &served(7, 3, &root('d')).to_json(),
            &format!(
                "its input root is not the one it brought: process 2 brought {} in image {}, and the receipt names \"{}\"",
                root('d'),
                root('c'),
                root('a')
            ),
        );
        refused(
            &served(2, 3, &root('a')).to_json(),
            &format!(
                "its host-call count is cut: process 2 brought a count of 3 in image {}, and the receipt counts 2",
                root('c')
            ),
        );
        let mut lowered = j.clone();
        lowered["version"] = json!(VERSION_CARRIED);
        refused(
            &lowered,
            "a version 4 receipt carries `input_root`, which only a server's receipt of version 2, 3 or 5 has",
        );
        let mut plain = j.clone();
        plain["version"] = json!(VERSION);
        refused(
            &plain,
            "a version 2 receipt carries `carried`, which only version 4 or 5 has",
        );
        let mut bare = j.clone();
        bare.as_object_mut().expect("object").remove(CARRIED_KEY);
        refused(&bare, "a version 5 receipt without `carried`");
        let mut unnamed = j.clone();
        unnamed[CARRIED_KEY]
            .as_object_mut()
            .expect("object")
            .remove("input_root");
        refused(
            &unnamed,
            "a version 5 receipt whose `carried` names no `input_root`",
        );
        let mut unrooted = j.clone();
        unrooted
            .as_object_mut()
            .expect("object")
            .remove("input_root");
        refused(&unrooted, "a version 5 receipt without `input_root`");
        let mut malformed = j.clone();
        malformed[CARRIED_KEY]["input_root"] = json!("b3:00");
        refused(
            &malformed,
            "`carried.input_root` is \"b3:00\", not b3: and 64 hex digits",
        );
    }
}