fxcp_core/

chunk_delta.rs

// SPDX-License-Identifier: GPL-2.0-or-later
// Copyright (C) 2025 Joel Wirāmu Pauling <aenertia@aenertia.net>
//
//! Content-defined chunk diff algorithm.

use std::collections::HashSet;

/// A reference to a content-addressed chunk with its size.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct ChunkRef {
    /// BLAKE3 hex hash of the chunk content (content-addressed identity).
    pub hash: String,
    /// Uncompressed size of the chunk in bytes.
    pub size: u64,
}

/// Result of diffing two ordered chunk lists.
///
/// Efficiency semantics:
/// - `0.0` when `new` is empty (no chunks = no efficiency to measure).
/// - `1.0` when all new chunks already exist in old (perfect dedup).
#[derive(Debug, Clone)]
pub struct ChunkDelta {
    /// Chunks in `new` not present in `old`  --  must be uploaded.
    pub added: Vec<ChunkRef>,
    /// Chunks in `old` not present in `new`  --  become orphans (handled by compact()).
    pub removed: Vec<ChunkRef>,
    /// Number of chunks shared between old and new (reused, no upload needed).
    pub unchanged: usize,
    /// Fraction of new chunks that are reused: `unchanged / new.len()`.
    /// 1.0 = no change. 0.0 = all new (or empty).
    pub efficiency: f64,
    /// If true, >80% of old chunks changed  --  full re-upload is more efficient than delta.
    pub full_upload_recommended: bool,
}

/// Compute the delta between two ordered chunk lists.
///
/// Uses content-addressed identity: same BLAKE3 hash = same content = no upload needed.
/// GearChunker content-defined boundaries ensure most chunks survive edits, so diffs
/// are typically sparse.
///
/// # Arguments
/// * `old` - Chunk list from the existing stored version (from manifest).
/// * `new` - Chunk list from the new version (freshly chunked).
///
/// # Returns
/// [`ChunkDelta`] with added/removed/unchanged counts and efficiency metric.
pub fn compute_chunk_delta(old: &[ChunkRef], new: &[ChunkRef]) -> ChunkDelta {
    let old_set: HashSet<&str> = old.iter().map(|c| c.hash.as_str()).collect();
    let new_set: HashSet<&str> = new.iter().map(|c| c.hash.as_str()).collect();

    let added: Vec<ChunkRef> = new.iter()
        .filter(|c| !old_set.contains(c.hash.as_str()))
        .cloned()
        .collect();

    let removed: Vec<ChunkRef> = old.iter()
        .filter(|c| !new_set.contains(c.hash.as_str()))
        .cloned()
        .collect();

    let unchanged = new.len().saturating_sub(added.len());

    let efficiency = if new.is_empty() {
        0.0
    } else {
        unchanged as f64 / new.len() as f64
    };

    let full_upload_recommended = if old.is_empty() {
        false
    } else {
        removed.len() as f64 / old.len() as f64 > 0.80
    };

    ChunkDelta { added, removed, unchanged, efficiency, full_upload_recommended }
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
    use super::*;

    fn chunk(hash: &str, size: u64) -> ChunkRef {
        ChunkRef { hash: hash.to_string(), size }
    }

    #[test]
    fn test_empty_old_empty_new() {
        let d = compute_chunk_delta(&[], &[]);
        assert_eq!(d.added.len(), 0);
        assert_eq!(d.removed.len(), 0);
        assert_eq!(d.unchanged, 0);
        assert_eq!(d.efficiency, 0.0);
        assert!(!d.full_upload_recommended);
    }

    #[test]
    fn test_empty_old_five_new() {
        let new = vec![chunk("a",100), chunk("b",100), chunk("c",100), chunk("d",100), chunk("e",100)];
        let d = compute_chunk_delta(&[], &new);
        assert_eq!(d.added.len(), 5);
        assert_eq!(d.removed.len(), 0);
        assert_eq!(d.unchanged, 0);
        assert_eq!(d.efficiency, 0.0);
        assert!(!d.full_upload_recommended); // empty old -> first upload
    }

    #[test]
    fn test_five_old_empty_new() {
        let old = vec![chunk("a",100), chunk("b",100), chunk("c",100), chunk("d",100), chunk("e",100)];
        let d = compute_chunk_delta(&old, &[]);
        assert_eq!(d.added.len(), 0);
        assert_eq!(d.removed.len(), 5);
        assert_eq!(d.unchanged, 0);
        assert_eq!(d.efficiency, 0.0);
        // 5/5 = 100% removed > 80% -> true
        assert!(d.full_upload_recommended);
    }

    #[test]
    fn test_identical_chunks() {
        let chunks = vec![chunk("a",100), chunk("b",200), chunk("c",300)];
        let d = compute_chunk_delta(&chunks, &chunks);
        assert_eq!(d.added.len(), 0);
        assert_eq!(d.removed.len(), 0);
        assert_eq!(d.unchanged, 3);
        assert!((d.efficiency - 1.0).abs() < f64::EPSILON);
        assert!(!d.full_upload_recommended);
    }

    #[test]
    fn test_one_chunk_changed_out_of_ten() {
        let old: Vec<ChunkRef> = (0..10).map(|i| chunk(&format!("old_{i}"), 100)).collect();
        // new = same 9 + one replacement
        let mut new_chunks = old.clone();
        new_chunks[5] = chunk("new_5", 100);
        let d = compute_chunk_delta(&old, &new_chunks);
        assert_eq!(d.added.len(), 1);
        assert_eq!(d.removed.len(), 1);
        assert_eq!(d.unchanged, 9);
        assert!((d.efficiency - 0.9).abs() < 1e-10);
        assert!(!d.full_upload_recommended); // 1/10 = 10% removed
    }

    #[test]
    fn test_all_chunks_changed() {
        let old: Vec<ChunkRef> = (0..10).map(|i| chunk(&format!("old_{i}"), 100)).collect();
        let new: Vec<ChunkRef> = (0..10).map(|i| chunk(&format!("new_{i}"), 100)).collect();
        let d = compute_chunk_delta(&old, &new);
        assert_eq!(d.added.len(), 10);
        assert_eq!(d.removed.len(), 10);
        assert_eq!(d.unchanged, 0);
        assert_eq!(d.efficiency, 0.0);
        assert!(d.full_upload_recommended); // 100% changed
    }

    #[test]
    fn test_append_two_new_chunks() {
        let old = vec![chunk("a",100), chunk("b",100)];
        let new_chunks = vec![chunk("a",100), chunk("b",100), chunk("c",100), chunk("d",100)];
        let d = compute_chunk_delta(&old, &new_chunks);
        assert_eq!(d.added.len(), 2);
        assert_eq!(d.removed.len(), 0);
        assert_eq!(d.unchanged, 2);
        assert!((d.efficiency - 0.5).abs() < f64::EPSILON);
        assert!(!d.full_upload_recommended); // 0 removed from old
    }

    #[test]
    fn test_remove_three_chunks_from_tail() {
        let old: Vec<ChunkRef> = (0..5).map(|i| chunk(&format!("c{i}"), 100)).collect();
        let new_chunks = old[..2].to_vec(); // keep first 2
        let d = compute_chunk_delta(&old, &new_chunks);
        assert_eq!(d.added.len(), 0);
        assert_eq!(d.removed.len(), 3);
        assert_eq!(d.unchanged, 2);
        // 3/5 = 60% removed  --  below 80% threshold
        assert!(!d.full_upload_recommended);
    }

    #[test]
    fn test_full_upload_threshold_exactly_80_percent() {
        // 8 of 10 old chunks replaced -> exactly 80% -> NOT above threshold
        let old: Vec<ChunkRef> = (0..10).map(|i| chunk(&format!("old_{i}"), 100)).collect();
        let mut new_chunks = old.clone();
        for i in 0..8 {
            new_chunks[i] = chunk(&format!("new_{i}"), 100);
        }
        let d = compute_chunk_delta(&old, &new_chunks);
        // 8/10 = 80.0%  --  NOT strictly greater than 80%
        assert!(!d.full_upload_recommended);

        // 9 of 10 -> 90% -> IS above threshold
        let mut new2 = old.clone();
        for i in 0..9 {
            new2[i] = chunk(&format!("newx_{i}"), 100);
        }
        let d2 = compute_chunk_delta(&old, &new2);
        assert!(d2.full_upload_recommended);
    }

    #[test]
    fn test_single_chunk_change() {
        let old = vec![chunk("only_chunk", 512)];
        let new_chunks = vec![chunk("new_chunk", 512)];
        let d = compute_chunk_delta(&old, &new_chunks);
        assert_eq!(d.added.len(), 1);
        assert_eq!(d.removed.len(), 1);
        assert_eq!(d.unchanged, 0);
        // 1/1 = 100% removed -> full_upload_recommended
        assert!(d.full_upload_recommended);
    }

    #[test]
    fn test_order_does_not_matter_for_identity() {
        // Same hashes in different order still recognized as unchanged
        let old = vec![chunk("a",100), chunk("b",100), chunk("c",100)];
        let new_chunks = vec![chunk("c",100), chunk("a",100), chunk("b",100)];
        let d = compute_chunk_delta(&old, &new_chunks);
        assert_eq!(d.added.len(), 0);
        assert_eq!(d.removed.len(), 0);
        assert_eq!(d.unchanged, 3);
        assert!(!d.full_upload_recommended);
    }
}