nordisk/edda

crates/gunnar-delta/tests/determinism.rs

//! The same input and options give the same bytes at 1 thread and at 32.
//!
//! This is a property of the design, not a coincidence to be hoped for: an
//! object's candidate set is `[i - window, i)` in the sorted order and nothing
//! else, no worker reads another's result, and chain depth is resolved
//! afterwards in one serial pass. Chunking decides *who* computes an answer,
//! never *what* it is.
//!
//! It is asserted rather than argued because the argument has one weak point —
//! if a future change ever let a worker see a neighbour's chosen base, the
//! output would still look correct and would silently stop being reproducible.
//! Byte-for-byte equality across thread counts is the only check that fails when
//! that happens.

use std::sync::atomic::AtomicBool;

use gix_object::Kind;
use gunnar_delta::{deltify, Deltified, Object, Options};

fn corpus() -> Vec<Vec<u8>> {
    let mut seed: Vec<u8> = (0..90_000u32)
        .map(|i| (i.wrapping_mul(2654435761) >> 11) as u8)
        .collect();
    let mut out = Vec::new();
    for rev in 0..120 {
        let stamp = format!("[rev {rev:04}]").into_bytes();
        for at in (rev * 13..seed.len() - 32).step_by(4_099) {
            seed.splice(at..at + stamp.len(), stamp.iter().copied());
        }
        let mut c = seed.clone();
        c.truncate(c.len() - rev * 7);
        out.push(c);
    }
    out
}

fn run(contents: &[Vec<u8>], threads: Option<usize>) -> Vec<Deltified> {
    let objects: Vec<Object<'_>> = contents
        .iter()
        .enumerate()
        .map(|(i, c)| {
            let mut id = [0u8; 20];
            id[..8].copy_from_slice(&(i as u64).to_be_bytes());
            Object {
                id: gix_hash::ObjectId::from(id),
                kind: Kind::Blob,
                name_hash: 0,
                epoch: 0,
                data: c.as_slice(),
            }
        })
        .collect();
    let opts = Options {
        thread_limit: threads,
        ..Options::default()
    };
    deltify(
        &objects,
        &opts,
        &mut gix_utils::progress::Discard,
        &AtomicBool::default(),
    )
    .expect("deltify")
}

#[test]
fn one_thread_and_many_threads_produce_identical_bytes() {
    let contents = corpus();
    let serial = run(&contents, Some(1));

    // The corpus must actually exercise the window, or "identical" is trivial.
    let deltas = serial.iter().filter(|d| d.is_delta()).count();
    assert!(
        deltas > contents.len() / 2,
        "only {deltas} of {} objects deltified, so this corpus proves nothing about \
         determinism because there is nothing to be non-deterministic about",
        contents.len()
    );
    assert!(
        serial.iter().any(|d| d.depth > 1),
        "no chain deeper than 1 was built, so the serial depth pass is untested"
    );

    for threads in [2usize, 4, 8, 32] {
        let parallel = run(&contents, Some(threads));
        assert_eq!(
            serial.len(),
            parallel.len(),
            "{threads} threads returned a different number of entries"
        );
        for (i, (a, b)) in serial.iter().zip(&parallel).enumerate() {
            assert_eq!(
                a.source, b.source,
                "entry {i} order changed at {threads} threads"
            );
            assert_eq!(
                a.base, b.base,
                "entry {i} chose a different base at {threads} threads"
            );
            assert_eq!(
                a.depth, b.depth,
                "entry {i} got a different depth at {threads} threads"
            );
            assert_eq!(
                a.data, b.data,
                "entry {i} produced different delta bytes at {threads} threads"
            );
        }
    }
}

#[test]
fn the_default_thread_limit_agrees_with_one_thread() {
    // `None` means the machine's core count, which is the configuration a repack
    // actually runs in and the one a fixed thread count would not cover.
    let contents = corpus();
    assert_eq!(run(&contents, Some(1)), run(&contents, None));
}

#[test]
fn no_delta_chain_exceeds_the_configured_depth() {
    let contents = corpus();
    for depth in [1usize, 2, 5, 50] {
        let objects: Vec<Object<'_>> = contents
            .iter()
            .enumerate()
            .map(|(i, c)| {
                let mut id = [0u8; 20];
                id[..8].copy_from_slice(&(i as u64).to_be_bytes());
                Object {
                    id: gix_hash::ObjectId::from(id),
                    kind: Kind::Blob,
                    name_hash: 0,
                    epoch: 0,
                    data: c.as_slice(),
                }
            })
            .collect();
        let out = deltify(
            &objects,
            &Options {
                depth,
                ..Options::default()
            },
            &mut gix_utils::progress::Discard,
            &AtomicBool::default(),
        )
        .expect("deltify");

        let deepest = out.iter().map(|d| d.depth).max().unwrap_or(0);
        assert!(
            deepest as usize <= depth,
            "a chain reached depth {deepest} with the limit set to {depth}"
        );
        assert_eq!(
            deepest as usize, depth,
            "the limit of {depth} was never reached, so this assertion could not have failed"
        );

        // And the graph really is acyclic and backwards-pointing.
        for (i, d) in out.iter().enumerate() {
            if let Some(b) = d.base {
                assert!(b < i, "entry {i} points forward at {b}");
                assert_eq!(
                    d.depth,
                    out[b].depth + 1,
                    "entry {i} depth disagrees with its base"
                );
            } else {
                assert_eq!(d.depth, 0, "a base object at {i} has depth {}", d.depth);
            }
        }
    }
}