bearout 0.1.0

// SPDX-License-Identifier: Apache-2.0

//! Staged, confined output generation.
//!
//! 1. The generated-state manifest is parsed strictly. It is absent, valid,
//!    or invalid; an invalid manifest stops the run before anything else.
//! 2. Every plan entry is validated: the output lies beneath a declared
//!    output root, no two entries collide after normalization and case
//!    folding, and the template name is normalized.
//! 3. Every artifact is rendered into memory with `MiniJinja` in strict mode,
//!    under a fuel limit and an output size limit, and digested with BLAKE3.
//! 4. Check mode compares artifacts and the manifest against the tree and
//!    reports missing, stale, unowned, orphaned, and re-owned outputs.
//! 5. Write mode first verifies that every existing planned output is owned
//!    by the manifest and that every orphan is removable, then runs one
//!    journaled transaction: write changed outputs, remove owned orphans,
//!    write the manifest. If any step fails, every completed step is undone
//!    from the journal where possible, the failure and any restoration
//!    failure are reported, and the manifest is never written.
//!
//! What is atomic: each file replacement, through an exclusively created
//! temporary file and a rename. What is not: the multi-file sequence, which
//! is journaled and restored on failure rather than committed as one unit.
//!
//! Ownership is proven only by the state manifest. An existing file at a
//! planned path that the manifest does not own is never overwritten, even
//! when its bytes already equal the rendered bytes; generation must begin
//! with the path absent for ownership to be established. Untracked or
//! modified files are never deleted.

use std::collections::BTreeMap;
use std::io;
use std::sync::Arc;

use cap_std::fs::Dir;
use minijinja::{Environment, UndefinedBehavior};
use serde_json::{Value, json};
use toml_edit::{ArrayOfTables, DocumentMut, Item, Table, value};

use crate::bootstrap::{Bootstrap, Limits, STATE_NAME};
use crate::fs::ProjectDir;
use crate::identity;
use crate::paths::ProjectPath;
use crate::report::{Code, Diagnostic};

/// Whether generation writes files or only verifies them.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Mode {
    /// Deliver every changed output and remove owned orphans.
    Write,
    /// Report differences; write nothing.
    Check,
}

/// A validated plan entry with its provenance.
pub(crate) struct Planned {
    pub generator: String,
    /// Module that produced the entry, for diagnostics.
    pub script: String,
    pub template: ProjectPath,
    pub output: ProjectPath,
    pub context: Value,
}

/// What generation produced besides diagnostics.
#[derive(Default)]
pub(crate) struct Outcome {
    /// Outputs delivered or verified, only when generation succeeded.
    pub outputs: Vec<String>,
    /// Highest fuel consumed by one render.
    pub max_fuel: u64,
    /// Largest rendered output in bytes.
    pub max_output_bytes: u64,
}

/// One rendered artifact.
struct Artifact {
    planned: Planned,
    content: Vec<u8>,
    digest: String,
    inputs: String,
}

/// One entry of the generated-state manifest.
#[derive(Debug, Clone, PartialEq, Eq)]
struct StateEntry {
    generator: String,
    template: String,
    digest: String,
    inputs: String,
}

type State = BTreeMap<String, StateEntry>;

/// Extensions whose files can carry a comment header, and therefore must
/// carry the provenance header.
const COMMENTABLE: [&str; 12] = [
    "md", "rs", "py", "ts", "js", "toml", "star", "yaml", "yml", "html", "txt", "sh",
];

/// The marker every provenance header contains.
pub const PROVENANCE_MARKER: &str = "Generated by Bearout";

fn digest(bytes: &[u8]) -> String {
    format!("blake3:{}", blake3::hash(bytes).to_hex())
}

/// Validate, render, compare, and deliver.
pub(crate) fn run(
    fs: &ProjectDir,
    bootstrap: &Bootstrap,
    entries: Vec<Planned>,
    mode: Mode,
    version: &str,
    diagnostics: &mut Vec<Diagnostic>,
) -> Outcome {
    let before = diagnostics.len();
    let mut outcome = Outcome::default();

    let previous = match read_state(fs, bootstrap) {
        Ok(state) => state.unwrap_or_default(),
        Err(problems) => {
            diagnostics.extend(problems);
            return outcome;
        }
    };
    let entries = validate(bootstrap, entries, diagnostics);
    let artifacts = if entries.is_empty() {
        Vec::new()
    } else {
        let Some(renderer) = Renderer::new(fs, bootstrap, diagnostics) else {
            return outcome;
        };
        render(
            &renderer,
            bootstrap,
            entries,
            version,
            diagnostics,
            &mut outcome,
        )
    };
    if diagnostics.len() > before {
        return outcome;
    }

    let next: State = artifacts
        .iter()
        .map(|artifact| {
            (
                artifact.planned.output.as_str().to_owned(),
                StateEntry {
                    generator: artifact.planned.generator.clone(),
                    template: artifact.planned.template.as_str().to_owned(),
                    digest: artifact.digest.clone(),
                    inputs: artifact.inputs.clone(),
                },
            )
        })
        .collect();
    let state_text = state_text(&next, version);

    match mode {
        Mode::Check => check(fs, &artifacts, &previous, &next, &state_text, diagnostics),
        Mode::Write => deliver(
            fs,
            bootstrap,
            &artifacts,
            &previous,
            &next,
            &state_text,
            diagnostics,
        ),
    }
    if diagnostics.len() == before {
        outcome.outputs = artifacts
            .iter()
            .map(|artifact| artifact.planned.output.as_str().to_owned())
            .collect();
    }
    outcome
}

fn validate(
    bootstrap: &Bootstrap,
    entries: Vec<Planned>,
    diagnostics: &mut Vec<Diagnostic>,
) -> Vec<Planned> {
    let mut seen: BTreeMap<String, (String, String)> = BTreeMap::new();
    let mut accepted = Vec::new();
    for entry in entries {
        let report = |message: String| {
            Diagnostic::new(
                Code::PlanInvalid,
                entry.script.as_str(),
                format!("generator `{}`: {message}", entry.generator),
            )
        };
        if !beneath_output_root(bootstrap, &entry.output) {
            diagnostics.push(report(format!(
                "output `{}` is not beneath a declared output root {:?}",
                entry.output,
                bootstrap
                    .output_roots
                    .iter()
                    .map(ToString::to_string)
                    .collect::<Vec<_>>()
            )));
            continue;
        }
        let key = entry.output.fold_key();
        if let Some((owner, other)) = seen.get(&key) {
            diagnostics.push(report(format!(
                "output `{}` collides with `{other}` from generator `{owner}` (paths are compared after Unicode lowercasing)",
                entry.output
            )));
            continue;
        }
        seen.insert(
            key,
            (entry.generator.clone(), entry.output.as_str().to_owned()),
        );
        accepted.push(entry);
    }
    accepted.sort_by(|a, b| a.output.cmp(&b.output));
    accepted
}

fn beneath_output_root(bootstrap: &Bootstrap, path: &ProjectPath) -> bool {
    bootstrap
        .output_roots
        .iter()
        .any(|root| path.is_within(root) && path != root)
}

struct Renderer {
    env: Environment<'static>,
    templates: Arc<Dir>,
    limits: Limits,
}

/// An `io::Write` that refuses to grow beyond a byte limit, so a runaway
/// template is stopped before an unbounded buffer is allocated.
struct BoundedWriter {
    buffer: Vec<u8>,
    limit: u64,
    exceeded: bool,
}

impl io::Write for BoundedWriter {
    fn write(&mut self, data: &[u8]) -> io::Result<usize> {
        let projected = self.buffer.len() as u64 + data.len() as u64;
        if projected > self.limit {
            self.exceeded = true;
            return Err(io::Error::other("output limit exceeded"));
        }
        self.buffer.extend_from_slice(data);
        Ok(data.len())
    }

    fn flush(&mut self) -> io::Result<()> {
        Ok(())
    }
}

impl Renderer {
    fn new(
        fs: &ProjectDir,
        bootstrap: &Bootstrap,
        diagnostics: &mut Vec<Diagnostic>,
    ) -> Option<Self> {
        let Some(root) = &bootstrap.templates_root else {
            diagnostics.push(Diagnostic::new(
                Code::PlanInvalid,
                crate::bootstrap::MANIFEST_NAME,
                "generators need a `[templates]` root",
            ));
            return None;
        };
        let templates = match fs.subdir(root) {
            Ok(dir) => Arc::new(dir),
            Err(error) => {
                diagnostics.push(Diagnostic::new(
                    Code::PlanInvalid,
                    root.as_str(),
                    format!("cannot open templates root: {error}"),
                ));
                return None;
            }
        };
        let mut env = Environment::new();
        let loader_dir = Arc::clone(&templates);
        env.set_loader(move |name: &str| {
            let Ok(path) = ProjectPath::parse(name) else {
                return Ok(None);
            };
            match loader_dir.read_to_string(path.to_native()) {
                Ok(text) => Ok(Some(text)),
                Err(error) if error.kind() == io::ErrorKind::NotFound => Ok(None),
                Err(error) => Err(minijinja::Error::new(
                    minijinja::ErrorKind::TemplateNotFound,
                    error.to_string(),
                )),
            }
        });
        env.set_undefined_behavior(UndefinedBehavior::Strict);
        env.set_trim_blocks(true);
        env.set_lstrip_blocks(true);
        env.set_keep_trailing_newline(true);
        env.set_fuel(Some(bootstrap.limits.template_fuel));
        env.add_filter("snake_case", |s: String| join_words(&s, "_"));
        env.add_filter("kebab_case", |s: String| join_words(&s, "-"));
        env.add_filter("screaming_case", |s: String| {
            join_words(&s, "_").to_uppercase()
        });
        env.add_filter("pascal_case", |s: String| pascal(&s, true));
        env.add_filter("camel_case", |s: String| pascal(&s, false));
        env.add_filter("quote", |s: String| {
            serde_json::to_string(&s).unwrap_or_default()
        });
        Some(Self {
            env,
            templates,
            limits: bootstrap.limits,
        })
    }

    fn source(&self, template: &ProjectPath) -> Option<String> {
        self.templates.read_to_string(template.to_native()).ok()
    }

    /// Render into a bounded buffer. Returns the bytes and the fuel consumed.
    fn render(&self, template: &ProjectPath, context: &Value) -> Result<(Vec<u8>, u64), String> {
        let template = self
            .env
            .get_template(template.as_str())
            .map_err(|error| error.to_string())?;
        let mut writer = BoundedWriter {
            buffer: Vec::new(),
            limit: self.limits.output_bytes,
            exceeded: false,
        };
        let captured = match template.render_captured_to(to_template_value(context), &mut writer) {
            Ok(captured) => captured,
            Err(_) if writer.exceeded => {
                return Err(format!(
                    "rendered output exceeds `limits.output_bytes` = {}",
                    self.limits.output_bytes
                ));
            }
            Err(error) => return Err(format!("{error:#}")),
        };
        let consumed = captured
            .state()
            .fuel_levels()
            .map_or(0, |(consumed, _)| consumed);
        Ok((writer.buffer, consumed))
    }
}

/// Convert JSON to a template value explicitly. Going through serde would
/// let `serde_json`'s arbitrary-precision number representation leak into
/// templates as an internal struct.
fn to_template_value(value: &Value) -> minijinja::Value {
    match value {
        Value::Null => minijinja::Value::from(()),
        Value::Bool(b) => minijinja::Value::from(*b),
        Value::Number(n) => n.as_i64().map_or_else(
            || minijinja::Value::from(n.as_f64().unwrap_or(0.0)),
            minijinja::Value::from,
        ),
        Value::String(s) => minijinja::Value::from(s.as_str()),
        Value::Array(items) => minijinja::Value::from_iter(items.iter().map(to_template_value)),
        Value::Object(map) => minijinja::Value::from_iter(
            map.iter()
                .map(|(key, item)| (key.clone(), to_template_value(item))),
        ),
    }
}

fn render(
    renderer: &Renderer,
    bootstrap: &Bootstrap,
    entries: Vec<Planned>,
    version: &str,
    diagnostics: &mut Vec<Diagnostic>,
    outcome: &mut Outcome,
) -> Vec<Artifact> {
    let mut artifacts = Vec::new();
    for planned in entries {
        let report = |message: String| {
            Diagnostic::new(
                Code::PlanInvalid,
                planned.script.as_str(),
                format!("generator `{}`: {message}", planned.generator),
            )
        };
        let Some(source) = renderer.source(&planned.template) else {
            diagnostics.push(report(format!(
                "template `{}` does not exist beneath the templates root",
                planned.template
            )));
            continue;
        };
        let mut header = vec![format!(
            "{PROVENANCE_MARKER} {version}: generator `{}`, template `{}`. Do not edit.",
            planned.generator, planned.template
        )];
        if let Some(license) = &bootstrap.license {
            header.insert(0, format!("SPDX-License-Identifier: {license}"));
        }
        let mut context = planned.context.clone();
        context["bearout"] = json!({
            "version": version,
            "generator": planned.generator,
            "template": planned.template.as_str(),
            "output": planned.output.as_str(),
            "license": bootstrap.license,
            "header": header,
        });
        let (content, fuel) = match renderer.render(&planned.template, &context) {
            Ok(rendered) => rendered,
            Err(error) => {
                diagnostics.push(report(format!("template `{}`: {error}", planned.template)));
                continue;
            }
        };
        outcome.max_fuel = outcome.max_fuel.max(fuel);
        outcome.max_output_bytes = outcome.max_output_bytes.max(content.len() as u64);
        if planned
            .output
            .extension()
            .is_some_and(|ext| COMMENTABLE.contains(&ext))
        {
            let text = String::from_utf8_lossy(&content);
            let head: Vec<&str> = text.lines().take(5).collect();
            if !head.iter().any(|line| line.contains(PROVENANCE_MARKER)) {
                diagnostics.push(report(format!(
                    "output `{}` must carry the provenance header from `bearout.header` within its first five lines",
                    planned.output
                )));
                continue;
            }
            if bootstrap.license.is_some()
                && !head
                    .iter()
                    .any(|line| line.contains("SPDX-License-Identifier"))
            {
                diagnostics.push(report(format!(
                    "output `{}` must carry the SPDX header from `bearout.header`",
                    planned.output
                )));
                continue;
            }
        }
        let mut hasher = blake3::Hasher::new();
        hasher.update(version.as_bytes());
        hasher.update(b"\0");
        hasher.update(source.as_bytes());
        hasher.update(b"\0");
        hasher.update(context.to_string().as_bytes());
        artifacts.push(Artifact {
            digest: digest(&content),
            inputs: format!("blake3:{}", hasher.finalize().to_hex()),
            planned,
            content,
        });
    }
    artifacts
}

/// Parse the state manifest strictly: absent (`Ok(None)`), valid
/// (`Ok(Some)`), or invalid (`Err` with every problem found).
fn read_state(fs: &ProjectDir, bootstrap: &Bootstrap) -> Result<Option<State>, Vec<Diagnostic>> {
    let path = ProjectPath::parse(STATE_NAME).expect("constant path");
    if !fs.exists(&path) {
        return Ok(None);
    }
    let problem = |message: String| vec![Diagnostic::new(Code::OutputState, STATE_NAME, message)];
    let text = fs
        .read_text(&path)
        .map_err(|error| problem(format!("cannot read state manifest: {error}")))?;
    let doc: DocumentMut = text.parse().map_err(|error: toml_edit::TomlError| {
        problem(format!(
            "state manifest is not valid TOML: {}",
            error.message()
        ))
    })?;
    let mut problems = Vec::new();
    let mut fail =
        |message: String| problems.push(Diagnostic::new(Code::OutputState, STATE_NAME, message));

    for (key, _) in doc.as_table() {
        if !["version", "bearout", "outputs"].contains(&key) {
            fail(format!("state manifest has unknown key `{key}`"));
        }
    }
    match doc.get("version").and_then(Item::as_integer) {
        Some(1) => {}
        Some(other) => fail(format!(
            "state manifest version {other} is not supported; this build reads version 1"
        )),
        None => fail("state manifest must declare `version = 1`".to_owned()),
    }
    match doc.get("bearout").and_then(Item::as_str) {
        Some(text) if is_version(text) => {}
        Some(text) => fail(format!(
            "state manifest `bearout` is not a version string: {text:?}"
        )),
        None => fail("state manifest must declare the `bearout` version string".to_owned()),
    }

    let mut entries = State::new();
    match doc.get("outputs") {
        None => {}
        Some(Item::ArrayOfTables(outputs)) => {
            for (index, table) in outputs.iter().enumerate() {
                let label = format!("outputs[{index}]");
                match parse_entry(table, bootstrap) {
                    Ok((path, entry)) => {
                        if entries.insert(path.clone(), entry).is_some() {
                            fail(format!("{label}: path `{path}` is listed more than once"));
                        }
                    }
                    Err(message) => fail(format!("{label}: {message}")),
                }
            }
        }
        Some(_) => fail("state manifest `outputs` must be an array of tables".to_owned()),
    }
    if problems.is_empty() {
        Ok(Some(entries))
    } else {
        Err(problems)
    }
}

fn is_version(text: &str) -> bool {
    let core = text.split(['-', '+']).next().unwrap_or_default();
    let numeric = core
        .split('.')
        .filter(|part| !part.is_empty() && part.bytes().all(|b| b.is_ascii_digit()));
    !text.is_empty()
        && text.bytes().all(|b| b.is_ascii_graphic())
        && numeric.count() == 3
        && core.split('.').count() == 3
}

fn parse_entry(table: &Table, bootstrap: &Bootstrap) -> Result<(String, StateEntry), String> {
    const KEYS: [&str; 5] = ["path", "generator", "template", "digest", "inputs"];
    for (key, _) in table {
        if !KEYS.contains(&key) {
            return Err(format!("unknown key `{key}`"));
        }
    }
    let text = |key: &str| -> Result<&str, String> {
        table
            .get(key)
            .ok_or_else(|| format!("missing `{key}`"))?
            .as_str()
            .ok_or_else(|| format!("`{key}` must be a string"))
    };
    let path = ProjectPath::parse(text("path")?).map_err(|error| format!("`path` {error}"))?;
    if path.as_str().is_empty() {
        return Err("`path` must not be empty".to_owned());
    }
    if !beneath_output_root(bootstrap, &path) {
        return Err(format!(
            "`path` `{path}` is not beneath a declared output root"
        ));
    }
    let generator = text("generator")?;
    identity::check_kind(generator).map_err(|error| format!("`generator`: {error}"))?;
    let template =
        ProjectPath::parse(text("template")?).map_err(|error| format!("`template` {error}"))?;
    if template.as_str().is_empty() {
        return Err("`template` must not be empty".to_owned());
    }
    let digest_text = text("digest")?;
    let inputs_text = text("inputs")?;
    for (key, value) in [("digest", digest_text), ("inputs", inputs_text)] {
        if !is_digest(value) {
            return Err(format!(
                "`{key}` must be `blake3:` followed by 64 lowercase hexadecimal characters"
            ));
        }
    }
    Ok((
        path.as_str().to_owned(),
        StateEntry {
            generator: generator.to_owned(),
            template: template.as_str().to_owned(),
            digest: digest_text.to_owned(),
            inputs: inputs_text.to_owned(),
        },
    ))
}

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

fn state_text(entries: &State, version: &str) -> String {
    let mut doc = DocumentMut::new();
    doc["version"] = value(1);
    doc["bearout"] = value(version);
    let mut outputs = ArrayOfTables::new();
    for (path, entry) in entries {
        let mut table = Table::new();
        table["path"] = value(path);
        table["generator"] = value(&entry.generator);
        table["template"] = value(&entry.template);
        table["digest"] = value(&entry.digest);
        table["inputs"] = value(&entry.inputs);
        outputs.push(table);
    }
    doc["outputs"] = Item::ArrayOfTables(outputs);
    format!(
        "# {PROVENANCE_MARKER}. Records the outputs Bearout owns and their provenance. Do not edit.\n{doc}"
    )
}

fn check(
    fs: &ProjectDir,
    artifacts: &[Artifact],
    previous: &State,
    next: &State,
    state_text: &str,
    diagnostics: &mut Vec<Diagnostic>,
) {
    for artifact in artifacts {
        let path = artifact.planned.output.as_str();
        match fs.read(&artifact.planned.output) {
            Ok(bytes) => {
                if !previous.contains_key(path) {
                    diagnostics.push(Diagnostic::new(
                        Code::OutputState,
                        path,
                        "output exists but is not owned by the state manifest; remove it so that generation can establish ownership",
                    ));
                } else if bytes != artifact.content {
                    diagnostics.push(Diagnostic::new(
                        Code::OutputState,
                        path,
                        "generated file is stale; run `bearout generate`",
                    ));
                }
            }
            Err(error) if error.kind() == io::ErrorKind::NotFound => {
                diagnostics.push(Diagnostic::new(
                    Code::OutputState,
                    path,
                    "generated file is missing; run `bearout generate`",
                ));
            }
            Err(error) => diagnostics.push(Diagnostic::new(
                Code::OutputState,
                path,
                format!("cannot read generated file: {error}"),
            )),
        }
        if let Some(old) = previous.get(path)
            && (old.generator != artifact.planned.generator
                || old.template != artifact.planned.template.as_str())
        {
            diagnostics.push(Diagnostic::new(
                Code::OutputState,
                path,
                format!(
                    "ownership changed: previously generator `{}` with template `{}`, now generator `{}` with template `{}`",
                    old.generator, old.template, artifact.planned.generator, artifact.planned.template
                ),
            ));
        }
    }
    for path in previous.keys().filter(|path| !next.contains_key(*path)) {
        diagnostics.push(Diagnostic::new(
            Code::OutputState,
            path.as_str(),
            "orphaned output: previously generated by Bearout but no longer planned; run `bearout generate`",
        ));
    }
    let state_path = ProjectPath::parse(STATE_NAME).expect("constant path");
    match fs.read_text(&state_path) {
        Ok(text) if text == state_text => {}
        Ok(_) => diagnostics.push(Diagnostic::new(
            Code::OutputState,
            STATE_NAME,
            "state manifest is stale; run `bearout generate`",
        )),
        Err(_) if artifacts.is_empty() && previous.is_empty() => {}
        Err(_) => diagnostics.push(Diagnostic::new(
            Code::OutputState,
            STATE_NAME,
            "state manifest is missing; run `bearout generate`",
        )),
    }
}

/// A pending output write: target, new bytes, and prior bytes if the file existed.
type PendingWrite<'a> = (&'a ProjectPath, &'a [u8], Option<Vec<u8>>);

/// One journaled step of a delivery, with what it takes to undo it.
enum Step<'a> {
    /// A file written; `prior` is the content it replaced, if any.
    Written {
        path: &'a ProjectPath,
        prior: Option<Vec<u8>>,
    },
    /// An orphan removed; `prior` is its content.
    Removed { path: ProjectPath, prior: Vec<u8> },
}

fn deliver(
    fs: &ProjectDir,
    bootstrap: &Bootstrap,
    artifacts: &[Artifact],
    previous: &State,
    next: &State,
    state_text: &str,
    diagnostics: &mut Vec<Diagnostic>,
) {
    let before = diagnostics.len();
    let mut writes: Vec<PendingWrite<'_>> = Vec::new();
    for artifact in artifacts {
        let path = &artifact.planned.output;
        match fs.symlink_component(path) {
            Ok(None) => {}
            Ok(Some(link)) => {
                diagnostics.push(Diagnostic::new(
                    Code::Delivery,
                    path.as_str(),
                    format!("`{link}` is a symbolic link; outputs are never written through links"),
                ));
                continue;
            }
            Err(error) => {
                diagnostics.push(Diagnostic::new(
                    Code::Delivery,
                    path.as_str(),
                    format!("cannot inspect output path: {error}"),
                ));
                continue;
            }
        }
        match fs.read(path) {
            Ok(existing) if !previous.contains_key(path.as_str()) => {
                diagnostics.push(Diagnostic::new(
                    Code::Delivery,
                    path.as_str(),
                    "refusing to overwrite a file the state manifest does not own; remove it so that generation can establish ownership from an absent path",
                ));
                drop(existing);
            }
            Ok(existing) if existing == artifact.content => {}
            Ok(existing) => {
                writes.push((path, &artifact.content, Some(existing)));
            }
            Err(error) if error.kind() == io::ErrorKind::NotFound => {
                writes.push((path, &artifact.content, None));
            }
            Err(error) => {
                diagnostics.push(Diagnostic::new(
                    Code::Delivery,
                    path.as_str(),
                    format!("cannot read existing output: {error}"),
                ));
            }
        }
    }

    let mut removals: Vec<(ProjectPath, Vec<u8>)> = Vec::new();
    for (path, entry) in previous
        .iter()
        .filter(|(path, _)| !next.contains_key(*path))
    {
        let project_path = ProjectPath::parse(path).expect("validated when the state was read");
        if !beneath_output_root(bootstrap, &project_path) {
            diagnostics.push(Diagnostic::new(
                Code::OutputState,
                path.as_str(),
                "orphaned output lies outside every declared output root; not removed",
            ));
            continue;
        }
        match fs.read(&project_path) {
            Ok(bytes) if digest(&bytes) == entry.digest => removals.push((project_path, bytes)),
            Ok(_) => diagnostics.push(Diagnostic::new(
                Code::OutputState,
                path.as_str(),
                "orphaned output was modified after Bearout wrote it; not removed, and the state manifest is left unchanged",
            )),
            Err(error) if error.kind() == io::ErrorKind::NotFound => {}
            Err(error) => diagnostics.push(Diagnostic::new(Code::OutputState, path.as_str(), format!("cannot inspect orphaned output: {error}"))),
        }
    }
    if diagnostics.len() > before {
        return;
    }

    let mut journal: Vec<Step<'_>> = Vec::new();
    let mut failure: Option<Diagnostic> = None;
    for (path, bytes, prior) in writes {
        if let Err(error) = fs.write_atomic(path, bytes) {
            failure = Some(Diagnostic::new(
                Code::Delivery,
                path.as_str(),
                format!("cannot write output: {error}"),
            ));
            break;
        }
        journal.push(Step::Written { path, prior });
    }
    if failure.is_none() {
        for (path, prior) in removals {
            if let Err(error) = fs.remove_file(&path) {
                failure = Some(Diagnostic::new(
                    Code::Delivery,
                    path.as_str(),
                    format!("cannot remove orphaned output: {error}"),
                ));
                break;
            }
            journal.push(Step::Removed { path, prior });
        }
    }
    if failure.is_none() && (!next.is_empty() || !previous.is_empty()) {
        let state_path = ProjectPath::parse(STATE_NAME).expect("constant path");
        if let Err(error) = fs.write_atomic(&state_path, state_text.as_bytes()) {
            failure = Some(Diagnostic::new(
                Code::Delivery,
                STATE_NAME,
                format!("cannot write state manifest: {error}"),
            ));
        }
    }
    if let Some(failure) = failure {
        diagnostics.push(failure);
        restore(fs, &journal, diagnostics);
    }
}

/// Undo journaled steps in reverse order after a failed delivery. The state
/// manifest was not written, so the tree returns to the previous state where
/// every restoration succeeds; each failure is reported.
fn restore(fs: &ProjectDir, journal: &[Step<'_>], diagnostics: &mut Vec<Diagnostic>) {
    for step in journal.iter().rev() {
        let (path, result) = match step {
            Step::Written {
                path,
                prior: Some(bytes),
            } => (path.as_str(), fs.write_atomic(path, bytes)),
            Step::Written { path, prior: None } => (path.as_str(), fs.remove_file(path)),
            Step::Removed { path, prior } => (path.as_str(), fs.write_atomic(path, prior)),
        };
        if let Err(error) = result {
            diagnostics.push(Diagnostic::new(
                Code::Delivery,
                path,
                format!("could not restore prior content after a failed delivery: {error}"),
            ));
        }
    }
    if !journal.is_empty() {
        diagnostics.push(Diagnostic::new(
            Code::Delivery,
            STATE_NAME,
            format!(
                "delivery failed after {} change(s); prior content was restored where possible and the state manifest was not written",
                journal.len()
            ),
        ));
    }
}

/// Split an identifier into lower-case words at non-alphanumerics, at
/// lower-to-upper boundaries, and before the last capital of an upper-case
/// run that is followed by lower case (`HTTPServer` is `http`, `server`).
fn words(text: &str) -> Vec<String> {
    let chars: Vec<char> = text.chars().collect();
    let mut words = Vec::new();
    let mut current = String::new();
    for (position, &c) in chars.iter().enumerate() {
        if !c.is_alphanumeric() {
            if !current.is_empty() {
                words.push(std::mem::take(&mut current));
            }
            continue;
        }
        let previous = position.checked_sub(1).map(|p| chars[p]);
        let next = chars.get(position + 1);
        let boundary = c.is_uppercase()
            && previous.is_some_and(|p| {
                p.is_lowercase()
                    || p.is_numeric()
                    || (p.is_uppercase() && next.is_some_and(|n| n.is_lowercase()))
            });
        if boundary && !current.is_empty() {
            words.push(std::mem::take(&mut current));
        }
        current.extend(c.to_lowercase());
    }
    if !current.is_empty() {
        words.push(current);
    }
    words
}

fn join_words(text: &str, separator: &str) -> String {
    words(text).join(separator)
}

fn pascal(text: &str, capitalize_first: bool) -> String {
    words(text)
        .iter()
        .enumerate()
        .map(|(index, word)| {
            if index == 0 && !capitalize_first {
                word.clone()
            } else {
                let mut chars = word.chars();
                chars
                    .next()
                    .map(|first| first.to_uppercase().collect::<String>() + chars.as_str())
                    .unwrap_or_default()
            }
        })
        .collect()
}

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

    #[test]
    fn converts_identifier_cases() {
        assert_eq!(join_words("tok-lparen", "_"), "tok_lparen");
        assert_eq!(join_words("HTTPServer2Go", "-"), "http-server2-go");
        assert_eq!(pascal("ch-lexical", true), "ChLexical");
        assert_eq!(pascal("some_thing here", false), "someThingHere");
    }

    #[test]
    fn state_text_is_deterministic() {
        let mut entries = BTreeMap::new();
        entries.insert(
            "generated/b.md".to_owned(),
            StateEntry {
                generator: "g".into(),
                template: "t.j2".into(),
                digest: "blake3:00".into(),
                inputs: "blake3:11".into(),
            },
        );
        let text = state_text(&entries, "0.1.0");
        assert!(text.starts_with("# Generated by Bearout"));
        assert!(text.contains("path = \"generated/b.md\""));
        assert_eq!(text, state_text(&entries, "0.1.0"));
    }

    #[test]
    fn digests_and_versions_are_checked_strictly() {
        assert!(is_digest(&digest(b"x")));
        assert!(!is_digest("blake3:00"));
        assert!(!is_digest(&digest(b"x").to_uppercase()));
        assert!(!is_digest(
            "sha256:0000000000000000000000000000000000000000000000000000000000000000"
        ));
        assert!(is_version("0.1.0"));
        assert!(is_version("1.2.3-beta.1"));
        assert!(!is_version(""));
        assert!(!is_version("1.2"));
        assert!(!is_version("a.b.c"));
    }
}