lcpfs 2026.1.102

// Copyright 2025 LunaOS Contributors
// SPDX-License-Identifier: Apache-2.0

//! Delta synchronization types.
//!
//! Core types for efficient delta-based file synchronization,
//! similar to rsync's algorithm.

use alloc::string::{String, ToString};
use alloc::vec::Vec;
use core::fmt;

// ═══════════════════════════════════════════════════════════════════════════════
// CONSTANTS
// ═══════════════════════════════════════════════════════════════════════════════

/// Default block size for signature generation (4KB).
pub const DEFAULT_BLOCK_SIZE: usize = 4096;

/// Minimum block size (512 bytes).
pub const MIN_BLOCK_SIZE: usize = 512;

/// Maximum block size (1MB).
pub const MAX_BLOCK_SIZE: usize = 1024 * 1024;

/// Adler-32 modulus.
pub const ADLER_MOD: u32 = 65521;

// ═══════════════════════════════════════════════════════════════════════════════
// ROLLING CHECKSUM (ADLER-32 STYLE)
// ═══════════════════════════════════════════════════════════════════════════════

/// Rolling checksum for efficient block matching.
///
/// Uses Adler-32 style computation that can be updated incrementally
/// as the window slides through the data.
#[derive(Debug, Clone)]
pub struct RollingChecksum {
    /// Lower component (sum of bytes).
    a: u32,
    /// Upper component (sum of a's).
    b: u32,
    /// Window of bytes currently in checksum.
    window: Vec<u8>,
    /// Window size.
    window_size: usize,
    /// Current position in window (circular).
    pos: usize,
    /// Number of bytes added.
    count: usize,
}

impl RollingChecksum {
    /// Create a new rolling checksum with specified window size.
    pub fn new(window_size: usize) -> Self {
        Self {
            a: 1,
            b: 0,
            window: alloc::vec![0u8; window_size],
            window_size,
            pos: 0,
            count: 0,
        }
    }

    /// Reset the checksum.
    pub fn reset(&mut self) {
        self.a = 1;
        self.b = 0;
        self.pos = 0;
        self.count = 0;
        for byte in &mut self.window {
            *byte = 0;
        }
    }

    /// Add a byte to the checksum (initializing the window).
    pub fn push(&mut self, byte: u8) {
        self.a = (self.a + byte as u32) % ADLER_MOD;
        self.b = (self.b + self.a) % ADLER_MOD;

        self.window[self.pos] = byte;
        self.pos = (self.pos + 1) % self.window_size;
        self.count += 1;
    }

    /// Roll the window: remove old byte, add new byte.
    pub fn roll(&mut self, new_byte: u8) {
        let old_byte = self.window[self.pos] as u32;

        // Update a: subtract old, add new
        self.a = (self.a + ADLER_MOD - old_byte + new_byte as u32) % ADLER_MOD;

        // Update b: subtract (window_size * old_byte), add a
        // b = b - window_size * old_byte + a
        let sub = (self.window_size as u32 * old_byte) % ADLER_MOD;
        self.b = (self.b + ADLER_MOD - sub + self.a) % ADLER_MOD;

        // Store new byte
        self.window[self.pos] = new_byte;
        self.pos = (self.pos + 1) % self.window_size;
    }

    /// Get the current checksum value.
    pub fn checksum(&self) -> u32 {
        (self.b << 16) | self.a
    }

    /// Get window size.
    pub fn window_size(&self) -> usize {
        self.window_size
    }

    /// Check if window is fully populated.
    pub fn is_full(&self) -> bool {
        self.count >= self.window_size
    }

    /// Compute checksum directly from data (non-rolling).
    pub fn compute(data: &[u8]) -> u32 {
        let mut a: u32 = 1;
        let mut b: u32 = 0;

        for &byte in data {
            a = (a + byte as u32) % ADLER_MOD;
            b = (b + a) % ADLER_MOD;
        }

        (b << 16) | a
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// BLOCK SIGNATURE
// ═══════════════════════════════════════════════════════════════════════════════

/// Signature for a single block.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BlockSignature {
    /// Block index.
    pub index: u32,
    /// Offset in source file.
    pub offset: u64,
    /// Block length.
    pub length: u32,
    /// Rolling (weak) checksum for fast matching.
    pub rolling: u32,
    /// Strong checksum (truncated BLAKE3 or similar).
    pub strong: [u8; 16],
}

impl BlockSignature {
    /// Create a new block signature.
    pub fn new(index: u32, offset: u64, length: u32, rolling: u32, strong: [u8; 16]) -> Self {
        Self {
            index,
            offset,
            length,
            rolling,
            strong,
        }
    }
}

/// Collection of block signatures for a file.
#[derive(Debug, Clone)]
pub struct SignatureSet {
    /// File checksum (full file).
    pub file_checksum: [u64; 4],
    /// File size in bytes.
    pub file_size: u64,
    /// Block size used.
    pub block_size: u32,
    /// Block signatures.
    pub blocks: Vec<BlockSignature>,
}

impl SignatureSet {
    /// Create a new signature set.
    pub fn new(file_checksum: [u64; 4], file_size: u64, block_size: u32) -> Self {
        Self {
            file_checksum,
            file_size,
            block_size,
            blocks: Vec::new(),
        }
    }

    /// Add a block signature.
    pub fn add_block(&mut self, sig: BlockSignature) {
        self.blocks.push(sig);
    }

    /// Number of blocks.
    pub fn block_count(&self) -> usize {
        self.blocks.len()
    }

    /// Get block by index.
    pub fn get_block(&self, index: u32) -> Option<&BlockSignature> {
        self.blocks.get(index as usize)
    }

    /// Find blocks by rolling checksum.
    pub fn find_by_rolling(&self, rolling: u32) -> Vec<&BlockSignature> {
        self.blocks
            .iter()
            .filter(|b| b.rolling == rolling)
            .collect()
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// DELTA OPERATIONS
// ═══════════════════════════════════════════════════════════════════════════════

/// A single delta operation.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DeltaOp {
    /// Copy from source file.
    Copy {
        /// Source offset.
        src_offset: u64,
        /// Length to copy.
        length: u64,
    },
    /// Insert literal data.
    Insert {
        /// Data to insert.
        data: Vec<u8>,
    },
}

impl DeltaOp {
    /// Create a copy operation.
    pub fn copy(src_offset: u64, length: u64) -> Self {
        Self::Copy { src_offset, length }
    }

    /// Create an insert operation.
    pub fn insert(data: Vec<u8>) -> Self {
        Self::Insert { data }
    }

    /// Get the output size of this operation.
    pub fn output_size(&self) -> u64 {
        match self {
            Self::Copy { length, .. } => *length,
            Self::Insert { data } => data.len() as u64,
        }
    }

    /// Get the transfer size (bytes over the wire).
    pub fn transfer_size(&self) -> u64 {
        match self {
            Self::Copy { .. } => 16,                        // Just offset + length
            Self::Insert { data } => data.len() as u64 + 8, // Data + length header
        }
    }

    /// Check if this is a copy operation.
    pub fn is_copy(&self) -> bool {
        matches!(self, Self::Copy { .. })
    }

    /// Check if this is an insert operation.
    pub fn is_insert(&self) -> bool {
        matches!(self, Self::Insert { .. })
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// DELTA
// ═══════════════════════════════════════════════════════════════════════════════

/// Complete delta between source and target files.
#[derive(Debug, Clone)]
pub struct Delta {
    /// Source file checksum.
    pub source_checksum: [u64; 4],
    /// Target file checksum.
    pub target_checksum: [u64; 4],
    /// Source file size.
    pub source_size: u64,
    /// Target file size.
    pub target_size: u64,
    /// Block size used.
    pub block_size: u32,
    /// Delta operations.
    pub ops: Vec<DeltaOp>,
}

impl Delta {
    /// Create a new delta.
    pub fn new(
        source_checksum: [u64; 4],
        target_checksum: [u64; 4],
        source_size: u64,
        target_size: u64,
        block_size: u32,
    ) -> Self {
        Self {
            source_checksum,
            target_checksum,
            source_size,
            target_size,
            block_size,
            ops: Vec::new(),
        }
    }

    /// Add an operation.
    pub fn add_op(&mut self, op: DeltaOp) {
        self.ops.push(op);
    }

    /// Add a copy operation.
    pub fn add_copy(&mut self, src_offset: u64, length: u64) {
        // Try to merge with previous copy if contiguous
        if let Some(DeltaOp::Copy {
            src_offset: prev_off,
            length: prev_len,
        }) = self.ops.last_mut()
        {
            if *prev_off + *prev_len == src_offset {
                *prev_len += length;
                return;
            }
        }
        self.ops.push(DeltaOp::Copy { src_offset, length });
    }

    /// Add literal data.
    pub fn add_insert(&mut self, data: &[u8]) {
        // Try to merge with previous insert
        if let Some(DeltaOp::Insert { data: prev_data }) = self.ops.last_mut() {
            prev_data.extend_from_slice(data);
            return;
        }
        self.ops.push(DeltaOp::Insert {
            data: data.to_vec(),
        });
    }

    /// Number of operations.
    pub fn op_count(&self) -> usize {
        self.ops.len()
    }

    /// Calculate total transfer size.
    pub fn transfer_size(&self) -> u64 {
        self.ops.iter().map(|op| op.transfer_size()).sum()
    }

    /// Calculate compression ratio (transfer_size / target_size).
    pub fn compression_ratio(&self) -> f64 {
        if self.target_size == 0 {
            return 0.0;
        }
        self.transfer_size() as f64 / self.target_size as f64
    }

    /// Calculate copy percentage.
    pub fn copy_percentage(&self) -> f64 {
        let copy_bytes: u64 = self
            .ops
            .iter()
            .filter_map(|op| match op {
                DeltaOp::Copy { length, .. } => Some(*length),
                _ => None,
            })
            .sum();
        if self.target_size == 0 {
            return 0.0;
        }
        (copy_bytes as f64 / self.target_size as f64) * 100.0
    }

    /// Check if this is an identity delta (no changes).
    pub fn is_identity(&self) -> bool {
        self.source_checksum == self.target_checksum
    }

    /// Check if files are completely different (no copies).
    pub fn is_full_replace(&self) -> bool {
        self.ops.iter().all(|op| op.is_insert())
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// SYNC TYPES
// ═══════════════════════════════════════════════════════════════════════════════

/// Status of a file in sync operation.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SyncStatus {
    /// File is unchanged.
    Unchanged,
    /// File is new (not in source).
    New,
    /// File is modified.
    Modified,
    /// File should be deleted.
    Deleted,
    /// File was renamed.
    Renamed,
}

impl fmt::Display for SyncStatus {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Unchanged => write!(f, "unchanged"),
            Self::New => write!(f, "new"),
            Self::Modified => write!(f, "modified"),
            Self::Deleted => write!(f, "deleted"),
            Self::Renamed => write!(f, "renamed"),
        }
    }
}

/// File entry in sync plan.
#[derive(Debug, Clone)]
pub struct SyncEntry {
    /// File path.
    pub path: String,
    /// File size.
    pub size: u64,
    /// Modification time.
    pub mtime: u64,
    /// Checksum.
    pub checksum: [u64; 4],
    /// Sync status.
    pub status: SyncStatus,
    /// Delta (if modified).
    pub delta: Option<Delta>,
    /// Original path (if renamed).
    pub original_path: Option<String>,
}

impl SyncEntry {
    /// Create a new sync entry.
    pub fn new(path: &str, size: u64, mtime: u64, checksum: [u64; 4], status: SyncStatus) -> Self {
        Self {
            path: path.to_string(),
            size,
            mtime,
            checksum,
            status,
            delta: None,
            original_path: None,
        }
    }

    /// Set delta.
    pub fn with_delta(mut self, delta: Delta) -> Self {
        self.delta = Some(delta);
        self
    }

    /// Set original path for renamed files.
    pub fn with_original(mut self, path: &str) -> Self {
        self.original_path = Some(path.to_string());
        self
    }

    /// Get transfer size for this entry.
    pub fn transfer_size(&self) -> u64 {
        match self.status {
            SyncStatus::New => self.size,
            SyncStatus::Modified => self.delta.as_ref().map_or(self.size, |d| d.transfer_size()),
            SyncStatus::Renamed => 0, // Just metadata
            _ => 0,
        }
    }
}

/// Complete sync plan.
#[derive(Debug, Clone)]
pub struct SyncPlan {
    /// Source identifier.
    pub source: String,
    /// Destination identifier.
    pub destination: String,
    /// Timestamp when plan was created.
    pub created: u64,
    /// Files to sync.
    pub entries: Vec<SyncEntry>,
}

impl SyncPlan {
    /// Create a new sync plan.
    pub fn new(source: &str, destination: &str, created: u64) -> Self {
        Self {
            source: source.to_string(),
            destination: destination.to_string(),
            created,
            entries: Vec::new(),
        }
    }

    /// Add an entry.
    pub fn add_entry(&mut self, entry: SyncEntry) {
        self.entries.push(entry);
    }

    /// Get new files.
    pub fn new_files(&self) -> Vec<&SyncEntry> {
        self.entries
            .iter()
            .filter(|e| e.status == SyncStatus::New)
            .collect()
    }

    /// Get modified files.
    pub fn modified_files(&self) -> Vec<&SyncEntry> {
        self.entries
            .iter()
            .filter(|e| e.status == SyncStatus::Modified)
            .collect()
    }

    /// Get deleted files.
    pub fn deleted_files(&self) -> Vec<&SyncEntry> {
        self.entries
            .iter()
            .filter(|e| e.status == SyncStatus::Deleted)
            .collect()
    }

    /// Get renamed files.
    pub fn renamed_files(&self) -> Vec<&SyncEntry> {
        self.entries
            .iter()
            .filter(|e| e.status == SyncStatus::Renamed)
            .collect()
    }

    /// Total transfer size.
    pub fn transfer_bytes(&self) -> u64 {
        self.entries.iter().map(|e| e.transfer_size()).sum()
    }

    /// Total file count.
    pub fn file_count(&self) -> usize {
        self.entries.len()
    }

    /// Count by status.
    pub fn count_by_status(&self, status: SyncStatus) -> usize {
        self.entries.iter().filter(|e| e.status == status).count()
    }

    /// Check if sync is a no-op.
    pub fn is_empty(&self) -> bool {
        self.entries
            .iter()
            .all(|e| e.status == SyncStatus::Unchanged)
    }
}

/// Sync progress information.
#[derive(Debug, Clone)]
pub struct SyncProgress {
    /// Total files to process.
    pub total_files: u64,
    /// Files processed so far.
    pub files_done: u64,
    /// Total bytes to transfer.
    pub total_bytes: u64,
    /// Bytes transferred so far.
    pub bytes_done: u64,
    /// Current file being processed.
    pub current_file: Option<String>,
    /// Start time.
    pub started: u64,
    /// Estimated completion time.
    pub estimated_completion: Option<u64>,
}

impl SyncProgress {
    /// Create new progress tracker.
    pub fn new(total_files: u64, total_bytes: u64, started: u64) -> Self {
        Self {
            total_files,
            files_done: 0,
            total_bytes,
            bytes_done: 0,
            current_file: None,
            started,
            estimated_completion: None,
        }
    }

    /// Update progress.
    pub fn update(&mut self, file: &str, bytes: u64, current_time: u64) {
        self.current_file = Some(file.to_string());
        self.bytes_done += bytes;
        self.files_done += 1;

        // Estimate completion
        if self.bytes_done > 0 {
            let elapsed = current_time.saturating_sub(self.started);
            let rate = self.bytes_done as f64 / elapsed.max(1) as f64;
            let remaining = self.total_bytes.saturating_sub(self.bytes_done);
            let eta = (remaining as f64 / rate) as u64;
            self.estimated_completion = Some(current_time + eta);
        }
    }

    /// Get completion percentage.
    pub fn percentage(&self) -> f64 {
        if self.total_bytes == 0 {
            return 100.0;
        }
        (self.bytes_done as f64 / self.total_bytes as f64) * 100.0
    }

    /// Get transfer rate (bytes per second).
    pub fn rate(&self, current_time: u64) -> f64 {
        let elapsed = current_time.saturating_sub(self.started).max(1);
        self.bytes_done as f64 / elapsed as f64
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// ERRORS
// ═══════════════════════════════════════════════════════════════════════════════

/// Delta synchronization errors.
#[derive(Debug, Clone)]
pub enum DeltaError {
    /// Invalid block size.
    InvalidBlockSize(usize),
    /// Source file not found.
    SourceNotFound(String),
    /// Target file not found.
    TargetNotFound(String),
    /// Checksum mismatch.
    ChecksumMismatch {
        /// Expected checksum value.
        expected: [u64; 4],
        /// Actual checksum value.
        actual: [u64; 4],
    },
    /// Delta application failed.
    ApplyFailed(String),
    /// I/O error.
    IoError(String),
    /// Invalid delta format.
    InvalidDelta(String),
    /// Sync cancelled.
    Cancelled,
}

impl fmt::Display for DeltaError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidBlockSize(size) => write!(f, "invalid block size: {}", size),
            Self::SourceNotFound(path) => write!(f, "source not found: {}", path),
            Self::TargetNotFound(path) => write!(f, "target not found: {}", path),
            Self::ChecksumMismatch { .. } => write!(f, "checksum mismatch"),
            Self::ApplyFailed(msg) => write!(f, "apply failed: {}", msg),
            Self::IoError(msg) => write!(f, "I/O error: {}", msg),
            Self::InvalidDelta(msg) => write!(f, "invalid delta: {}", msg),
            Self::Cancelled => write!(f, "sync cancelled"),
        }
    }
}

/// Result type for delta operations.
pub type DeltaResult<T> = Result<T, DeltaError>;

// ═══════════════════════════════════════════════════════════════════════════════
// TESTS
// ═══════════════════════════════════════════════════════════════════════════════

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

    #[test]
    fn test_rolling_checksum_basic() {
        let mut rc = RollingChecksum::new(4);

        rc.push(b'a');
        rc.push(b'b');
        rc.push(b'c');
        rc.push(b'd');

        assert!(rc.is_full());
        let checksum1 = rc.checksum();

        // Roll to bcde
        rc.roll(b'e');
        let checksum2 = rc.checksum();

        assert_ne!(checksum1, checksum2);
    }

    #[test]
    fn test_rolling_checksum_compute() {
        let data = b"hello world";
        let checksum = RollingChecksum::compute(data);
        assert!(checksum > 0);
    }

    #[test]
    fn test_rolling_checksum_consistency() {
        // Rolling should produce same result as direct compute
        let data = b"abcd";

        let direct = RollingChecksum::compute(data);

        let mut rolling = RollingChecksum::new(4);
        for &b in data {
            rolling.push(b);
        }

        assert_eq!(direct, rolling.checksum());
    }

    #[test]
    fn test_block_signature() {
        let sig = BlockSignature::new(0, 0, 4096, 0x12345678, [0u8; 16]);
        assert_eq!(sig.index, 0);
        assert_eq!(sig.offset, 0);
        assert_eq!(sig.length, 4096);
        assert_eq!(sig.rolling, 0x12345678);
    }

    #[test]
    fn test_signature_set() {
        let mut set = SignatureSet::new([0; 4], 8192, 4096);

        set.add_block(BlockSignature::new(0, 0, 4096, 0x1111, [0u8; 16]));
        set.add_block(BlockSignature::new(1, 4096, 4096, 0x2222, [0u8; 16]));

        assert_eq!(set.block_count(), 2);
        assert_eq!(set.get_block(0).unwrap().rolling, 0x1111);
    }

    #[test]
    fn test_delta_op_copy() {
        let op = DeltaOp::copy(100, 50);
        assert!(op.is_copy());
        assert!(!op.is_insert());
        assert_eq!(op.output_size(), 50);
    }

    #[test]
    fn test_delta_op_insert() {
        let op = DeltaOp::insert(alloc::vec![1, 2, 3, 4, 5]);
        assert!(op.is_insert());
        assert!(!op.is_copy());
        assert_eq!(op.output_size(), 5);
    }

    #[test]
    fn test_delta_merge_copies() {
        let mut delta = Delta::new([0; 4], [1; 4], 1000, 1000, 4096);

        delta.add_copy(0, 100);
        delta.add_copy(100, 100);

        // Should merge into single copy
        assert_eq!(delta.op_count(), 1);
        if let DeltaOp::Copy { length, .. } = &delta.ops[0] {
            assert_eq!(*length, 200);
        }
    }

    #[test]
    fn test_delta_merge_inserts() {
        let mut delta = Delta::new([0; 4], [1; 4], 1000, 1000, 4096);

        delta.add_insert(b"hello");
        delta.add_insert(b" world");

        // Should merge into single insert
        assert_eq!(delta.op_count(), 1);
        if let DeltaOp::Insert { data } = &delta.ops[0] {
            assert_eq!(data, b"hello world");
        }
    }

    #[test]
    fn test_delta_compression_ratio() {
        let mut delta = Delta::new([0; 4], [1; 4], 1000, 1000, 4096);
        delta.add_copy(0, 900);
        delta.add_insert(b"1234567890");

        let ratio = delta.compression_ratio();
        // Transfer size is ~16 (copy) + ~18 (insert) = ~34 for 1000 byte file
        assert!(ratio < 0.1);
    }

    #[test]
    fn test_delta_copy_percentage() {
        let mut delta = Delta::new([0; 4], [1; 4], 1000, 1000, 4096);
        delta.add_copy(0, 800);
        delta.add_insert(&[0u8; 200]);

        let pct = delta.copy_percentage();
        assert!((pct - 80.0).abs() < 0.1);
    }

    #[test]
    fn test_sync_status_display() {
        assert_eq!(format!("{}", SyncStatus::New), "new");
        assert_eq!(format!("{}", SyncStatus::Modified), "modified");
        assert_eq!(format!("{}", SyncStatus::Deleted), "deleted");
    }

    #[test]
    fn test_sync_entry() {
        let entry = SyncEntry::new("/file.txt", 1000, 12345, [0; 4], SyncStatus::New);
        assert_eq!(entry.path, "/file.txt");
        assert_eq!(entry.transfer_size(), 1000);
    }

    #[test]
    fn test_sync_plan() {
        let mut plan = SyncPlan::new("/source", "/dest", 12345);

        plan.add_entry(SyncEntry::new("/a.txt", 100, 1, [0; 4], SyncStatus::New));
        plan.add_entry(SyncEntry::new(
            "/b.txt",
            200,
            2,
            [0; 4],
            SyncStatus::Modified,
        ));
        plan.add_entry(SyncEntry::new(
            "/c.txt",
            300,
            3,
            [0; 4],
            SyncStatus::Deleted,
        ));

        assert_eq!(plan.file_count(), 3);
        assert_eq!(plan.count_by_status(SyncStatus::New), 1);
        assert_eq!(plan.new_files().len(), 1);
        assert_eq!(plan.modified_files().len(), 1);
        assert_eq!(plan.deleted_files().len(), 1);
    }

    #[test]
    fn test_sync_progress() {
        let mut progress = SyncProgress::new(10, 10000, 1000);

        progress.update("/file1.txt", 1000, 1100);

        assert_eq!(progress.files_done, 1);
        assert_eq!(progress.bytes_done, 1000);
        assert_eq!(progress.percentage(), 10.0);
    }

    #[test]
    fn test_error_display() {
        let e = DeltaError::InvalidBlockSize(100);
        assert!(format!("{}", e).contains("100"));

        let e = DeltaError::SourceNotFound("/file.txt".to_string());
        assert!(format!("{}", e).contains("/file.txt"));
    }
}