cadmpeg 0.6.2

// SPDX-License-Identifier: Apache-2.0
//! Positional byte diff between two files.
//!
//! The comparison is positional, not an edit script: byte `n` of the first file
//! is compared with byte `n` of the second. Probe variants of one exporter keep
//! their field offsets, so a positional diff points straight at the changed
//! fields. An inserted byte shifts everything after it and shows up as one long
//! run, which is itself the signal that the files are not positional variants.

use std::num::NonZeroU64;

/// A maximal span of differing bytes, after gap coalescing.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(super) struct DiffRun {
    start: u64,
    len: NonZeroU64,
}

impl DiffRun {
    /// Returns a run covering the single byte at `start`.
    const fn single(start: u64) -> Self {
        Self {
            start,
            len: NonZeroU64::MIN,
        }
    }

    /// Returns the offset of the first differing byte in the run.
    pub(super) const fn start(self) -> u64 {
        self.start
    }

    /// Returns the number of bytes the run covers, including coalesced equal bytes.
    pub(super) const fn len(self) -> NonZeroU64 {
        self.len
    }

    /// Returns the exclusive end offset of the run.
    pub(super) const fn end(self) -> u64 {
        self.start + self.len.get()
    }

    /// Grows the run so that it covers the byte at `offset`, and does nothing
    /// for an offset the run already covers.
    fn extend_to(&mut self, offset: u64) {
        let Some(covered) = offset
            .checked_sub(self.start)
            .and_then(|distance| distance.checked_add(1))
            .and_then(NonZeroU64::new)
        else {
            return;
        };
        self.len = self.len.max(covered);
    }
}

/// A positional comparison of two byte strings.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(in crate::inspect) struct DiffSummary {
    /// Length of the first input.
    len_a: u64,
    /// Length of the second input.
    len_b: u64,
    /// Count of differing bytes inside the compared prefix.
    differing: u64,
    /// Differing spans after coalescing, in offset order.
    runs: Vec<DiffRun>,
}

impl DiffSummary {
    /// Returns the first differing offset.
    pub(super) fn first(&self) -> Option<u64> {
        self.runs.first().map(|run| run.start)
    }

    /// Returns `len_a` for the compared inputs.
    pub(super) const fn len_a(&self) -> u64 {
        self.len_a
    }

    /// Returns `len_b` for the compared inputs.
    pub(super) const fn len_b(&self) -> u64 {
        self.len_b
    }

    /// Returns `compared` for the compared inputs.
    pub(super) fn compared(&self) -> u64 {
        self.len_a.min(self.len_b)
    }

    /// Returns `differing` for the compared inputs.
    pub(super) const fn differing(&self) -> u64 {
        self.differing
    }

    /// Returns the coalesced differing spans.
    pub(super) fn runs(&self) -> &[DiffRun] {
        &self.runs
    }

    /// Returns true when the inputs are byte identical.
    pub(super) const fn identical(&self) -> bool {
        self.len_a == self.len_b && self.differing == 0
    }
}

/// Compares `a` and `b` positionally over their common prefix.
///
/// Two differing spans separated by `gap` or fewer equal bytes are reported as
/// one run, so a changed multi-field record reads as a single region instead of
/// one run per byte.
pub(super) fn compare(a: &[u8], b: &[u8], gap: u64) -> DiffSummary {
    let compared = a.len().min(b.len());
    let mut runs: Vec<DiffRun> = Vec::new();
    let mut differing = 0u64;
    for offset in 0..compared {
        if a[offset] == b[offset] {
            continue;
        }
        differing += 1;
        let offset = cadmpeg_core::decode::u64_from_index(offset);
        match runs.last_mut() {
            Some(last) => match last.end().checked_add(gap) {
                Some(end) if offset <= end => last.extend_to(offset),
                None => last.extend_to(offset),
                Some(_) => runs.push(DiffRun::single(offset)),
            },
            None => runs.push(DiffRun::single(offset)),
        }
    }
    DiffSummary {
        len_a: cadmpeg_core::decode::u64_from_index(a.len()),
        len_b: cadmpeg_core::decode::u64_from_index(b.len()),
        differing,
        runs,
    }
}

#[cfg(test)]
mod tests {
    use super::{compare, DiffRun};

    fn run(start: u64, len: u64) -> DiffRun {
        let mut run = DiffRun::single(start);
        run.extend_to(start + len - 1);
        run
    }

    #[test]
    fn unrepresentable_diff_span_does_not_extend_a_run() {
        let mut run = DiffRun::single(0);
        run.extend_to(u64::MAX);
        assert_eq!(run.len().get(), 1);
    }

    #[test]
    fn identical_inputs_produce_no_runs() {
        let summary = compare(b"abcd", b"abcd", 0);
        assert!(summary.identical());
        assert_eq!(summary.differing, 0);
        assert_eq!(summary.first(), None);
        assert!(summary.runs.is_empty());
    }

    #[test]
    fn a_length_difference_alone_is_not_identical() {
        let summary = compare(b"abcd", b"abcdef", 0);
        assert!(!summary.identical());
        assert_eq!(summary.compared(), 4);
        assert_eq!(summary.differing, 0);
        assert_eq!(summary.first(), None);
        assert_eq!((summary.len_a, summary.len_b), (4, 6));
    }

    #[test]
    fn reports_the_first_difference_and_each_byte_at_gap_zero() {
        // Differ at offsets 1 and 3 only.
        let summary = compare(b"abcde", b"aXcYe", 0);
        assert_eq!(summary.first(), Some(1));
        assert_eq!(summary.differing, 2);
        assert_eq!(summary.runs, [DiffRun::single(1), DiffRun::single(3),]);
    }

    #[test]
    fn coalesces_spans_separated_by_at_most_the_gap() {
        // Differ at 1 and 3, so one equal byte lies between them.
        let summary = compare(b"abcde", b"aXcYe", 1);
        assert_eq!(summary.differing, 2);
        assert_eq!(summary.runs, [run(1, 3)]);

        // Differ at 0 and 4, so three equal bytes lie between them.
        let wide = compare(b"abcde", b"XbcdY", 1);
        assert_eq!(wide.runs, [DiffRun::single(0), DiffRun::single(4),]);
        let merged = compare(b"abcde", b"XbcdY", 3);
        assert_eq!(merged.runs, [run(0, 5)]);
    }

    #[test]
    fn a_run_of_adjacent_differences_merges_at_any_gap() {
        let summary = compare(&[0, 0, 0, 0], &[0, 1, 2, 3], 0);
        assert_eq!(summary.runs, [run(1, 3)]);
        assert_eq!(summary.differing, 3);
    }

    #[test]
    fn only_the_common_prefix_is_compared() {
        let summary = compare(b"abc", b"abcZZZZ", 0);
        assert_eq!(summary.compared(), 3);
        assert_eq!(summary.differing, 0);
        assert_eq!(summary.runs, []);
    }

    #[test]
    fn empty_inputs_compare_cleanly() {
        let summary = compare(&[], &[], 0);
        assert!(summary.identical());
        assert_eq!(summary.compared(), 0);
    }
}