cadmpeg-ir 0.4.0

// SPDX-License-Identifier: Apache-2.0
//! Content hashing helpers shared by codecs.

use std::collections::BTreeMap;
use std::fmt::Write as _;
use std::io::Write as _;

use serde::Serialize;
use sha2::{Digest, Sha256};

use crate::document::{CadIr, SortedModel, SourceMeta};
use crate::native::{Native, NativeNamespace, NativeRecord};
use crate::units::{Tolerances, Units};

/// Returns the lowercase hexadecimal SHA-256 digest of `bytes`.
pub fn sha256_hex(bytes: &[u8]) -> String {
    encode_hex(&Sha256::digest(bytes))
}

/// Returns the lowercase hexadecimal SHA-256 digest of `value`'s canonical
/// pretty JSON.
///
/// The JSON is streamed into the digest, so hashing a document costs a fixed
/// buffer rather than a serialized copy of it. The bytes hashed are the ones
/// `serde_json::to_string_pretty` produces, which is what
/// [`CadIr::to_canonical_json`] returns.
pub fn canonical_json_sha256<T: Serialize>(value: &T) -> String {
    let mut hasher = Sha256::new();
    let mut writer = std::io::BufWriter::new(DigestWriter(&mut hasher));
    serde_json::to_writer_pretty(&mut writer, value).expect("canonical JSON serialization");
    writer.flush().expect("a digest accepts every byte");
    drop(writer);
    encode_hex(&hasher.finalize())
}

/// The source-attribute key under which a codec records
/// [`document_local_sha256`].
///
/// This one key gates the whole-document write decision: an encoder that finds
/// the recorded value still equal to a freshly computed one replays its retained
/// bytes, and otherwise runs its writer. Other `_local_sha256` attributes answer
/// narrower questions — which lane changed, and how — so they are not
/// interchangeable with this one and removing them does not move the same
/// branch.
pub const DOCUMENT_LOCAL_DIGEST_ATTRIBUTE: &str = "document_local_sha256";

/// Returns the machine-local content digest of `ir` as seen by the `format`
/// codec, for recording as the `document_local_sha256` source attribute.
///
/// The digest covers the document in canonical arena order with two
/// normalizations: the recorded `document_local_sha256` attribute is dropped so a
/// document carrying its own digest hashes the same as one that does not, and
/// the `format` unknown arena is reduced to record identities and links with
/// `source_image_id` — the retained copy of the source container — excluded.
/// Retained source bytes therefore never reach the digest, and the digest is
/// stable across a decode that stores it.
///
/// # What this digest is, and is not
///
/// It is a bitwise SHA-256 over the decoded neutral content. Its one job is the
/// write path's "was this document edited since it was decoded?" oracle: a
/// writer that finds the recorded digest still equal to a freshly computed one
/// replays the retained source bytes, and otherwise writes the document out
/// through its own encoder.
///
/// It is not a portable identity. The decoded content includes values a codec
/// derives through libm transcendentals, and glibc, MSVC, and Apple's libm
/// disagree on those by one or two units in the last place, so the same file
/// decoded on two platforms yields two different digests. It is equally not
/// stable across a change to this function, to the serialized shape of any
/// hashed type, or to a codec's arithmetic.
///
/// It is intentionally not tolerance-aware, and no amount of work can make it
/// so. Tolerant equality — what [`cadmpeg_core::compare`] and
/// [`crate::diff`] implement — is not transitive, and a hash imposes an
/// equivalence relation, so no digest can ever agree with an epsilon comparison.
/// The digest therefore stays bitwise and states its limits, rather than
/// pretending to a semantic identity it cannot deliver.
///
/// Every attribute holding a digest with these properties carries the
/// [`cadmpeg_core::compare::LOCAL_DIGEST_SUFFIX`] suffix; see
/// [`crate::document::SourceMeta`] for the convention and for who relies on it.
pub fn document_local_sha256(ir: &CadIr, format: &str, source_image_id: &str) -> String {
    let unknowns = reduced_unknowns(ir, format, source_image_id);
    canonical_json_sha256(&NormalizedDocument {
        ir_version: &ir.ir_version,
        source: ir.source.as_ref().map(|source| {
            let mut source = source.clone();
            source.attributes.remove("document_local_sha256");
            source
        }),
        units: &ir.units,
        tolerances: &ir.tolerances,
        model: ir.model.sorted(),
        native: normalized_native(&ir.native, format, &unknowns),
    })
}

/// Reduce the `format` unknown arena to record identities and links, dropping
/// `source_image_id`, in canonical order.
///
/// Each record is deserialized, filtered, and converted back before the next is
/// read, so the retained population — hundreds of thousands of records — is
/// never resident in typed and reduced form at once. A scratch namespace puts
/// the records through the same conversion and ordering a stored arena goes
/// through, which is what keeps the digest equal to the one a normalized copy of
/// the document produces.
fn reduced_unknowns(ir: &CadIr, format: &str, source_image_id: &str) -> Vec<NativeRecord> {
    let mut unreadable = false;
    let mut projected = NativeNamespace::default();
    projected
        .set_arena_from(
            "unknowns",
            ir.native_unknowns_iter(format)
                .map_while(|record| record.inspect_err(|_| unreadable = true).ok())
                .filter(|record| record.id.0 != source_image_id),
        )
        .expect("unknown records serialize");
    if unreadable {
        // An arena the reduction cannot read reduces to nothing, which is what
        // it did back when the whole arena was read in one fallible step.
        return Vec::new();
    }
    projected
        .arenas
        .remove("unknowns")
        .expect("the unknown arena was just set")
}

/// A document as the semantic digest sees it.
///
/// Mirrors [`CadIr`]'s serialized shape field for field, borrowing what it can
/// so that normalizing a document for hashing does not copy it. A field added
/// to [`CadIr`] must be added here too; the equivalence test that hashes a
/// normalized copy of a document fails when the two shapes drift.
#[derive(Serialize)]
struct NormalizedDocument<'a> {
    ir_version: &'a str,
    #[serde(skip_serializing_if = "Option::is_none")]
    source: Option<SourceMeta>,
    units: &'a Units,
    tolerances: &'a Tolerances,
    model: SortedModel<'a>,
    native: NormalizedNative<'a>,
}

/// Native namespaces in canonical order, with one arena substituted.
#[derive(Serialize)]
#[serde(transparent)]
struct NormalizedNative<'a> {
    namespaces: BTreeMap<&'a str, NormalizedNamespace<'a>>,
}

/// One native namespace whose arenas are borrowed in canonical record order.
#[derive(Serialize)]
struct NormalizedNamespace<'a> {
    version: u32,
    arenas: BTreeMap<&'a str, Vec<&'a NativeRecord>>,
}

/// Borrow every native namespace in canonical order, replacing the `format`
/// unknown arena with `unknowns` and creating that namespace when the document
/// has none.
fn normalized_native<'a>(
    native: &'a Native,
    format: &'a str,
    unknowns: &'a [NativeRecord],
) -> NormalizedNative<'a> {
    let mut namespaces = native
        .0
        .iter()
        .map(|(name, namespace)| {
            let arenas = namespace
                .arenas
                .iter()
                .map(|(arena, records)| (arena.as_str(), sorted_records(records)))
                .collect();
            (
                name.as_str(),
                NormalizedNamespace {
                    version: namespace.version,
                    arenas,
                },
            )
        })
        .collect::<BTreeMap<_, _>>();
    let namespace = namespaces
        .entry(format)
        .or_insert_with(|| NormalizedNamespace {
            version: 0,
            arenas: BTreeMap::new(),
        });
    if namespace.version == 0 {
        namespace.version = 1;
    }
    namespace
        .arenas
        .insert("unknowns", unknowns.iter().collect());
    NormalizedNative { namespaces }
}

/// Borrow `records` in canonical identity order.
fn sorted_records(records: &[NativeRecord]) -> Vec<&NativeRecord> {
    let mut refs = records.iter().collect::<Vec<_>>();
    refs.sort_by(|left, right| left.id().cmp(right.id()));
    refs
}

/// A sink that feeds every written byte to a digest.
struct DigestWriter<'a>(&'a mut Sha256);

impl std::io::Write for DigestWriter<'_> {
    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
        self.0.update(buf);
        Ok(buf.len())
    }

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

/// Render a digest as lowercase hexadecimal.
fn encode_hex(digest: &[u8]) -> String {
    let mut encoded = String::with_capacity(digest.len() * 2);
    for byte in digest {
        write!(encoded, "{byte:02x}").expect("writing to a String cannot fail");
    }
    encoded
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used)]

    use super::{canonical_json_sha256, document_local_sha256, sha256_hex};
    use crate::document::CadIr;
    use crate::native::{Native, NativeRecord};
    use crate::units::Units;

    #[test]
    fn encodes_sha256_as_lowercase_hexadecimal() {
        assert_eq!(
            sha256_hex(b"abc"),
            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
        );
    }

    /// A record exercising every JSON shape whose rendering could drift:
    /// nested objects and arrays, escaped and non-ASCII strings, and integers,
    /// negative integers, fractions, integral floats, and exponent-form floats.
    fn pinned_record() -> NativeRecord {
        let serde_json::Value::Object(fields) = serde_json::json!({
            "zeta": null,
            "alpha": [-1, 0, 1.5, 2.0, 1e10, 1e-7],
            "beta": {
                "nested": {"deep": [true, false]},
                "empty_array": [],
                "empty_object": {}
            },
            "escaped": "quote\" backslash\\ slash/ newline\n tab\t bell\u{7} accent é",
            "gamma": 9_007_199_254_740_993_u64,
            "delta": -9_007_199_254_740_993_i64
        }) else {
            panic!("the pinned record literal is a JSON object");
        };
        NativeRecord::new("pin:record#0", fields)
    }

    fn pinned_native() -> Native {
        let mut native = Native::default();
        let namespace = native.namespace_mut("pin");
        namespace.version = 3;
        namespace
            .arenas
            .insert("records".into(), vec![pinned_record()]);
        native
    }

    /// A `NativeRecord` renders `id` first and then its codec-owned fields in
    /// key order, honouring the caller's pretty formatting at every depth. The
    /// bytes below are the ones the document digest covers, so any change to
    /// how a record reaches a serializer changes every stored semantic hash.
    #[test]
    fn pins_pretty_printed_native_record_bytes() {
        let expected = r#"{
  "id": "pin:record#0",
  "alpha": [
    -1,
    0,
    1.5,
    2.0,
    10000000000.0,
    1e-7
  ],
  "beta": {
    "empty_array": [],
    "empty_object": {},
    "nested": {
      "deep": [
        true,
        false
      ]
    }
  },
  "delta": -9007199254740993,
  "escaped": "quote\" backslash\\ slash/ newline\n tab\t bell\u0007 accent é",
  "gamma": 9007199254740993,
  "zeta": null
}"#;
        assert_eq!(
            serde_json::to_string_pretty(&pinned_record()).unwrap(),
            expected
        );
    }

    /// The same bytes indented inside the enclosing namespace and arena, which
    /// is how a record actually reaches `to_writer_pretty` during hashing.
    #[test]
    fn pins_pretty_printed_native_arena_bytes() {
        let expected = r#"{
  "pin": {
    "version": 3,
    "arenas": {
      "records": [
        {
          "id": "pin:record#0",
          "alpha": [
            -1,
            0,
            1.5,
            2.0,
            10000000000.0,
            1e-7
          ],
          "beta": {
            "empty_array": [],
            "empty_object": {},
            "nested": {
              "deep": [
                true,
                false
              ]
            }
          },
          "delta": -9007199254740993,
          "escaped": "quote\" backslash\\ slash/ newline\n tab\t bell\u0007 accent é",
          "gamma": 9007199254740993,
          "zeta": null
        }
      ]
    }
  }
}"#;
        assert_eq!(
            serde_json::to_string_pretty(&pinned_native()).unwrap(),
            expected
        );
    }

    /// A digest over the arena above, pinned so that formatting drift anywhere
    /// under `canonical_json_sha256` fails here rather than silently
    /// invalidating every recorded document digest.
    #[test]
    fn pins_native_arena_digest() {
        assert_eq!(
            canonical_json_sha256(&pinned_native()),
            "acc1d88751dcb143ca47618c3f7a8ce14865edff0a26ab95748d2a0314ee8df0"
        );
    }

    /// A record carrying the members the unknown reduction keeps (`id`,
    /// `links`) alongside ones it drops.
    fn pinned_unknown(id: &str, links: &[&str]) -> NativeRecord {
        let serde_json::Value::Object(fields) = serde_json::json!({
            "links": links,
            "offset": 4096,
            "byte_len": 12,
            "sha256": "0000000000000000000000000000000000000000000000000000000000000000",
            "data": "AQID"
        }) else {
            panic!("the pinned unknown literal is a JSON object");
        };
        NativeRecord::new(id, fields)
    }

    fn pinned_document() -> CadIr {
        let mut ir = CadIr::empty(Units::default());
        ir.native = pinned_native();
        let namespace = ir.native.namespace_mut("pin");
        namespace.arenas.insert(
            "unknowns".into(),
            vec![
                pinned_unknown("pin:source-image#0", &[]),
                pinned_unknown("pin:unknown#0", &["pin:record#0", "pin:unknown#1"]),
            ],
        );
        ir.finalize();
        ir
    }

    /// Both digest entry points over one fixed document. `document_local_sha256`
    /// reduces the named format's unknown arena to identities and links and
    /// drops the retained source image, so it is pinned alongside the plain
    /// document digest.
    ///
    /// # Why two hex literals are pasted here
    ///
    /// This repository's rule is that an expectation comes from a specification
    /// or an approximate comparison, never from a failing run. These two
    /// literals are the sanctioned exception, and they must be read as such: a
    /// digest algorithm has no specification outside its own output, so the only
    /// possible source for the expected value is the algorithm as it stands. The
    /// values below were captured once, deliberately, from the algorithm being
    /// pinned.
    ///
    /// What this pins is the algorithm, not a correctness property. It says
    /// nothing about whether either digest covers the right fields; the tests
    /// above and beside it do that. The document it hashes is built from integer
    /// and fractional literals only, with no transcendental anywhere in its
    /// construction, so it is platform-independent by construction and these
    /// literals hold on glibc, MSVC, and Apple's libm alike.
    ///
    /// A failure here means the digest algorithm changed: this function, the
    /// serialized shape of any hashed type, the unknown reduction, or the
    /// canonical JSON rendering underneath. Every baseline recorded in every
    /// existing document is then stale, so every such document loses its
    /// write-path fast path and takes the no-baseline branch. That is a decision
    /// to state and accept out loud, never a side effect of an unrelated edit.
    /// To make it deliberately: change the algorithm, run
    /// `cargo test -p cadmpeg-ir --lib pins_document_digests` to read the two new
    /// digests out of the failure, paste them here, and say in the commit body
    /// that stored baselines are invalidated.
    #[test]
    fn pins_document_digests() {
        let ir = pinned_document();
        assert_eq!(
            canonical_json_sha256(&ir),
            "00ac254ce62cf446f1d1dcea56ded050bd9a1ef2a53c846a8e7c588cd99bb071"
        );
        assert_eq!(
            document_local_sha256(&ir, "pin", "pin:source-image#0"),
            "83fa753fb39360b9e51859c9c07ddac6ff23ec17b179fa548cf33c4331170180"
        );
    }

    /// The pinned document with the source metadata a decoded document carries:
    /// one recorded baseline the digest must drop, and one ordinary attribute it
    /// must keep.
    fn pinned_document_with_source() -> CadIr {
        let mut ir = pinned_document();
        ir.source = Some(crate::document::SourceMeta {
            format: "pin".into(),
            attributes: [
                ("document_local_sha256".to_owned(), "stale".to_owned()),
                ("file_size".to_owned(), "4096".to_owned()),
            ]
            .into_iter()
            .collect(),
        });
        ir
    }

    /// The digest over a document that carries source metadata, pinned for the
    /// same reason and under the same rules as [`pins_document_digests`] — which
    /// states why a pasted literal is legitimate here and what a failure means.
    ///
    /// This one additionally pins the normalization: the recorded baseline
    /// attribute is dropped before hashing and every other attribute is kept, so
    /// changing which attribute the digest ignores fails here.
    #[test]
    fn pins_document_digest_over_source_metadata() {
        let ir = pinned_document_with_source();
        assert_eq!(
            document_local_sha256(&ir, "pin", "pin:source-image#0"),
            "3750864814cc4d83c355df4e8c6942c3b7c682dc15c193b5c836540ad8c07d64"
        );
    }

    /// Nothing about a record's rendering may depend on how it was built: a
    /// record parsed back out of a document must hash exactly as the one that
    /// produced it.
    #[test]
    fn round_tripped_document_hashes_identically() {
        let ir = pinned_document();
        let json = ir.to_canonical_json().unwrap();
        let mut reparsed = CadIr::from_json(&json).unwrap();
        reparsed.finalize();
        assert_eq!(canonical_json_sha256(&ir), canonical_json_sha256(&reparsed));
        assert_eq!(ir.to_canonical_json().unwrap(), json);
    }
}