zipatch-rs 1.5.0

//! Sorted-vec interval map for one target file's [`Region`]s.
//!
//! The builder maintains a `Vec<Region>` sorted by `target_offset`, with no two
//! regions ever overlapping. Inserting a new region displaces (truncates,
//! removes, or splits) any overlap so the invariant holds at every step.
//!
//! # Truncation semantics for [`PartSource::Patch`]
//!
//! - **[`PatchSourceKind::Raw`]**: truncation rewrites both `offset` (on
//!   `truncate_left`) and the kind's `len` so the invariant
//!   `region.length == kind.Raw.len` always holds.
//! - **[`PatchSourceKind::Deflated`]**: truncation never rewrites
//!   `(offset, compressed_len, decompressed_len)` — those describe the whole
//!   DEFLATE block, which the applier must still decompress in full before
//!   slicing. The surviving half tracks its byte position inside the
//!   decompressed output via [`PartSource::Patch::decoded_skip`]. Two halves
//!   of a split DEFLATE block therefore share `(patch_idx, offset, kind)` and
//!   slice the decompressed bytes differently.

use super::plan::{PartSource, PatchSourceKind, Region};

/// Insert `incoming` into the sorted, non-overlapping `regions` slice,
/// displacing any existing region that intersects `[incoming.target_offset,
/// incoming.target_offset + incoming.length)`. See the [module-level
/// docs](self) for the per-kind truncation rules.
pub(crate) fn insert(regions: &mut Vec<Region>, incoming: Region) {
    let start = incoming.target_offset;
    let end = start.saturating_add(u64::from(incoming.length));
    debug_assert!(end > start, "zero-length region must not be inserted");

    let first = regions.partition_point(|r| region_end(r) <= start);
    let last = regions.partition_point(|r| r.target_offset < end);

    if first == last {
        regions.insert(first, incoming);
        return;
    }

    let head = {
        let r = &regions[first];
        if r.target_offset < start {
            let head_len = u32::try_from(start - r.target_offset)
                .expect("head split fits in u32 because the original region.length did");
            Some(truncate_right(r, head_len))
        } else {
            None
        }
    };
    let tail = {
        let r = &regions[last - 1];
        if region_end(r) > end {
            let tail_skip = u32::try_from(end - r.target_offset)
                .expect("tail split offset fits in u32 because the original region.length did");
            Some(truncate_left(r, tail_skip))
        } else {
            None
        }
    };

    // Fixed-size array splices avoid the per-insert `Vec::with_capacity(3)`
    // allocation. `Vec::splice` with an array `IntoIterator` knows the exact
    // size up front, matching the original behaviour byte-for-byte.
    match (head, tail) {
        (None, None) => {
            regions.splice(first..last, std::iter::once(incoming));
        }
        (Some(h), None) => {
            regions.splice(first..last, [h, incoming]);
        }
        (None, Some(t)) => {
            regions.splice(first..last, [incoming, t]);
        }
        (Some(h), Some(t)) => {
            regions.splice(first..last, [h, incoming, t]);
        }
    }
}

#[inline]
fn region_end(r: &Region) -> u64 {
    r.target_offset + u64::from(r.length)
}

fn truncate_right(r: &Region, new_len: u32) -> Region {
    let source = match &r.source {
        PartSource::Patch {
            patch_idx,
            offset,
            kind,
            decoded_skip,
        } => {
            let new_kind = match *kind {
                PatchSourceKind::Raw { .. } => PatchSourceKind::Raw { len: new_len },
                PatchSourceKind::Deflated {
                    compressed_len,
                    decompressed_len,
                } => PatchSourceKind::Deflated {
                    compressed_len,
                    decompressed_len,
                },
            };
            PartSource::Patch {
                patch_idx: *patch_idx,
                offset: *offset,
                kind: new_kind,
                decoded_skip: *decoded_skip,
            }
        }
        other => other.clone(),
    };
    Region {
        target_offset: r.target_offset,
        length: new_len,
        source,
        expected: r.expected.clone(),
    }
}

fn truncate_left(r: &Region, skip: u32) -> Region {
    let source = match &r.source {
        PartSource::Patch {
            patch_idx,
            offset,
            kind,
            decoded_skip,
        } => match *kind {
            PatchSourceKind::Raw { len } => PartSource::Patch {
                patch_idx: *patch_idx,
                offset: offset + u64::from(skip),
                kind: PatchSourceKind::Raw {
                    len: len.saturating_sub(skip),
                },
                decoded_skip: *decoded_skip,
            },
            PatchSourceKind::Deflated {
                compressed_len,
                decompressed_len,
            } => PartSource::Patch {
                patch_idx: *patch_idx,
                offset: *offset,
                kind: PatchSourceKind::Deflated {
                    compressed_len,
                    decompressed_len,
                },
                // The surviving tail starts `skip` bytes later in the
                // decompressed output. u16 is plenty: SqPack DEFLATE blocks
                // top out at 16 KiB decompressed, so decoded_skip stays well
                // under u16::MAX. Saturate defensively if a caller ever feeds
                // a pathological skip.
                decoded_skip: decoded_skip.saturating_add(u16::try_from(skip).unwrap_or(u16::MAX)),
            },
        },
        other => other.clone(),
    };
    Region {
        target_offset: r.target_offset + u64::from(skip),
        length: r.length - skip,
        source,
        expected: r.expected.clone(),
    }
}

#[cfg(test)]
mod tests {
    use super::super::plan::{PartExpected, PartSource, PatchSourceKind, Region};
    use super::*;

    fn raw(offset: u64, len: u32, src_off: u64) -> Region {
        Region {
            target_offset: offset,
            length: len,
            source: PartSource::Patch {
                patch_idx: 0,
                offset: src_off,
                kind: PatchSourceKind::Raw { len },
                decoded_skip: 0,
            },
            expected: PartExpected::SizeOnly,
        }
    }

    fn deflated(
        offset: u64,
        len: u32,
        src_off: u64,
        compressed_len: u32,
        decompressed_len: u32,
    ) -> Region {
        Region {
            target_offset: offset,
            length: len,
            source: PartSource::Patch {
                patch_idx: 0,
                offset: src_off,
                kind: PatchSourceKind::Deflated {
                    compressed_len,
                    decompressed_len,
                },
                decoded_skip: 0,
            },
            expected: PartExpected::SizeOnly,
        }
    }

    fn zeros(offset: u64, len: u32) -> Region {
        Region {
            target_offset: offset,
            length: len,
            source: PartSource::Zeros,
            expected: PartExpected::Zeros,
        }
    }

    fn sorted_non_overlapping(regions: &[Region]) -> bool {
        regions
            .windows(2)
            .all(|w| w[0].target_offset + u64::from(w[0].length) <= w[1].target_offset)
            && regions.iter().all(|r| r.length > 0)
    }

    #[test]
    fn insert_into_empty_vec() {
        let mut v = Vec::new();
        insert(&mut v, raw(0, 100, 1000));
        assert_eq!(v.len(), 1);
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[0].length, 100);
    }

    #[test]
    fn append_disjoint_at_end() {
        let mut v = vec![raw(0, 10, 1000)];
        insert(&mut v, raw(20, 10, 2000));
        assert_eq!(v.len(), 2);
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[1].target_offset, 20);
        assert!(sorted_non_overlapping(&v));
    }

    #[test]
    fn append_disjoint_at_start() {
        let mut v = vec![raw(50, 10, 5000)];
        insert(&mut v, raw(0, 10, 1000));
        assert_eq!(v.len(), 2);
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[1].target_offset, 50);
        assert!(sorted_non_overlapping(&v));
    }

    #[test]
    fn touching_regions_are_disjoint() {
        // [0..10) followed by [10..20) — they touch but don't overlap.
        let mut v = vec![raw(0, 10, 1000)];
        insert(&mut v, raw(10, 10, 2000));
        assert_eq!(v.len(), 2);
        assert!(sorted_non_overlapping(&v));
    }

    #[test]
    fn exact_replace_one_region() {
        let mut v = vec![raw(100, 50, 1000)];
        insert(&mut v, zeros(100, 50));
        assert_eq!(v.len(), 1);
        assert_eq!(v[0].source, PartSource::Zeros);
        assert_eq!(v[0].length, 50);
    }

    #[test]
    fn overlap_left_truncates_existing_head_and_inserts_new() {
        // existing [50..100); new [40..70). After: [40..70) zeros, [70..100) raw.
        let mut v = vec![raw(50, 50, 1000)];
        insert(&mut v, zeros(40, 30));
        assert_eq!(v.len(), 2);
        assert_eq!(v[0].target_offset, 40);
        assert_eq!(v[0].length, 30);
        assert_eq!(v[0].source, PartSource::Zeros);
        assert_eq!(v[1].target_offset, 70);
        assert_eq!(v[1].length, 30);
        assert!(sorted_non_overlapping(&v));
    }

    #[test]
    fn overlap_right_truncates_existing_tail_and_inserts_new() {
        // existing [50..100); new [80..120). After: [50..80) raw, [80..120) zeros.
        let mut v = vec![raw(50, 50, 1000)];
        insert(&mut v, zeros(80, 40));
        assert_eq!(v.len(), 2);
        assert_eq!(v[0].target_offset, 50);
        assert_eq!(v[0].length, 30);
        assert_eq!(v[1].target_offset, 80);
        assert_eq!(v[1].length, 40);
        assert_eq!(v[1].source, PartSource::Zeros);
        assert!(sorted_non_overlapping(&v));
    }

    #[test]
    fn fully_contained_overwrite_splits_into_three() {
        // existing [0..100); new [40..60). After: [0..40) raw, [40..60) zeros, [60..100) raw.
        let mut v = vec![raw(0, 100, 1000)];
        insert(&mut v, zeros(40, 20));
        assert_eq!(v.len(), 3);
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[0].length, 40);
        assert_eq!(v[1].target_offset, 40);
        assert_eq!(v[1].length, 20);
        assert_eq!(v[1].source, PartSource::Zeros);
        assert_eq!(v[2].target_offset, 60);
        assert_eq!(v[2].length, 40);
        // Trailing raw slice's patch source advanced by `skip = 60`.
        match &v[2].source {
            PartSource::Patch {
                offset,
                kind,
                decoded_skip,
                ..
            } => {
                assert_eq!(*offset, 1060);
                assert_eq!(*kind, PatchSourceKind::Raw { len: 40 });
                assert_eq!(*decoded_skip, 0, "Raw never uses decoded_skip");
            }
            other => panic!("expected Raw Patch tail, got {other:?}"),
        }
        // The head's Raw kind length must also shrink to match the truncated
        // region length — this is the truncate_right bug PR4 fixes.
        match &v[0].source {
            PartSource::Patch { offset, kind, .. } => {
                assert_eq!(*offset, 1000);
                assert_eq!(*kind, PatchSourceKind::Raw { len: 40 });
            }
            other => panic!("expected Raw Patch head, got {other:?}"),
        }
        assert!(sorted_non_overlapping(&v));
    }

    #[test]
    fn fully_containing_overwrite_removes_contained() {
        // existing [40..60); new [0..100). After: single [0..100) zeros.
        let mut v = vec![raw(40, 20, 5000)];
        insert(&mut v, zeros(0, 100));
        assert_eq!(v.len(), 1);
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[0].length, 100);
        assert_eq!(v[0].source, PartSource::Zeros);
    }

    #[test]
    fn fully_containing_overwrite_removes_multiple() {
        // existing [10..20), [30..40), [50..60); new [0..100). After: single [0..100).
        let mut v = vec![raw(10, 10, 1000), raw(30, 10, 2000), raw(50, 10, 3000)];
        insert(&mut v, zeros(0, 100));
        assert_eq!(v.len(), 1);
        assert_eq!(v[0].length, 100);
    }

    #[test]
    fn truncate_right_raw_shrinks_kind_len() {
        // existing [0..100) Raw src=1000 len=100; new [50..100) zeros.
        // After truncate_right, the head [0..50) must report Raw len=50, not 100.
        let mut v = vec![raw(0, 100, 1000)];
        insert(&mut v, zeros(50, 50));
        assert_eq!(v.len(), 2);
        assert_eq!(v[0].length, 50);
        match &v[0].source {
            PartSource::Patch { offset, kind, .. } => {
                assert_eq!(*offset, 1000);
                assert_eq!(*kind, PatchSourceKind::Raw { len: 50 });
            }
            other => panic!("expected Raw Patch head, got {other:?}"),
        }
    }

    #[test]
    fn truncate_left_on_deflated_advances_decoded_skip_not_offset() {
        // existing [0..100) Deflated, src=2000, compressed_len=50, decompressed_len=100.
        // new [0..30) zeros displaces the head 30 bytes.
        // The surviving tail [30..100) must keep (offset=2000, compressed_len=50,
        // decompressed_len=100) so the applier can still decompress the full
        // block, with decoded_skip=30 telling it to discard the first 30
        // decompressed bytes.
        let mut v = vec![deflated(0, 100, 2000, 50, 100)];
        insert(&mut v, zeros(0, 30));
        assert_eq!(v.len(), 2);
        assert_eq!(v[1].target_offset, 30);
        assert_eq!(v[1].length, 70);
        match &v[1].source {
            PartSource::Patch {
                offset,
                kind,
                decoded_skip,
                ..
            } => {
                assert_eq!(*offset, 2000);
                assert_eq!(
                    *kind,
                    PatchSourceKind::Deflated {
                        compressed_len: 50,
                        decompressed_len: 100,
                    }
                );
                assert_eq!(*decoded_skip, 30);
            }
            other => panic!("expected Deflated Patch tail, got {other:?}"),
        }
    }

    #[test]
    fn truncate_right_on_deflated_keeps_block_metadata() {
        // existing [0..100) Deflated, new [50..100) zeros.
        // Head [0..50) keeps the full block metadata; decoded_skip stays 0;
        // the applier writes 50 bytes from the decompressed output starting at 0.
        let mut v = vec![deflated(0, 100, 2000, 50, 100)];
        insert(&mut v, zeros(50, 50));
        assert_eq!(v.len(), 2);
        assert_eq!(v[0].length, 50);
        match &v[0].source {
            PartSource::Patch {
                offset,
                kind,
                decoded_skip,
                ..
            } => {
                assert_eq!(*offset, 2000);
                assert_eq!(
                    *kind,
                    PatchSourceKind::Deflated {
                        compressed_len: 50,
                        decompressed_len: 100,
                    }
                );
                assert_eq!(*decoded_skip, 0);
            }
            other => panic!("expected Deflated Patch head, got {other:?}"),
        }
    }

    #[test]
    fn deflated_split_across_both_sides_preserves_block_metadata() {
        // existing [0..100) Deflated. new [40..60) zeros splits into 3.
        // Head [0..40) deflated, mid zeros, tail [60..100) deflated.
        // Head: decoded_skip=0, length=40. Tail: decoded_skip=60, length=40.
        let mut v = vec![deflated(0, 100, 2000, 50, 100)];
        insert(&mut v, zeros(40, 20));
        assert_eq!(v.len(), 3);
        match &v[0].source {
            PartSource::Patch {
                kind, decoded_skip, ..
            } => {
                assert_eq!(
                    *kind,
                    PatchSourceKind::Deflated {
                        compressed_len: 50,
                        decompressed_len: 100,
                    }
                );
                assert_eq!(*decoded_skip, 0);
            }
            other => panic!("expected Deflated head, got {other:?}"),
        }
        match &v[2].source {
            PartSource::Patch {
                kind, decoded_skip, ..
            } => {
                assert_eq!(
                    *kind,
                    PatchSourceKind::Deflated {
                        compressed_len: 50,
                        decompressed_len: 100,
                    }
                );
                assert_eq!(*decoded_skip, 60);
            }
            other => panic!("expected Deflated tail, got {other:?}"),
        }
    }

    fn empty_block(offset: u64, units: u32) -> Region {
        Region {
            target_offset: offset,
            length: units * 128,
            source: PartSource::EmptyBlock { units },
            expected: PartExpected::EmptyBlock { units },
        }
    }

    // ---- single-byte regions ----
    // Length-1 incoming regions stress the `region_end(r) <= start` boundary
    // comparison at the top of `insert` and force the smallest possible
    // head- and tail-truncation around a fully-contained overlay.

    #[test]
    fn single_byte_raw_fully_contained_splits_existing_into_three() {
        // existing Raw[0..100); incoming Raw [50..51); expect [0..50) raw,
        // [50..51) raw, [51..100) raw. Both head- and tail-truncation fire.
        let mut v = vec![raw(0, 100, 1000)];
        insert(&mut v, raw(50, 1, 9_000));
        assert_eq!(v.len(), 3, "1-byte overlay must split into 3 regions");
        assert!(sorted_non_overlapping(&v));
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[0].length, 50);
        assert_eq!(v[1].target_offset, 50);
        assert_eq!(v[1].length, 1);
        assert_eq!(v[2].target_offset, 51);
        assert_eq!(v[2].length, 49);
        // Tail's Raw len/offset must shrink by exactly `skip = 51`.
        match &v[2].source {
            PartSource::Patch { offset, kind, .. } => {
                assert_eq!(*offset, 1051);
                assert_eq!(*kind, PatchSourceKind::Raw { len: 49 });
            }
            other => panic!("expected Raw Patch tail, got {other:?}"),
        }
    }

    #[test]
    fn single_byte_zeros_fully_contained_splits_existing_into_three() {
        let mut v = vec![raw(0, 100, 1000)];
        insert(&mut v, zeros(50, 1));
        assert_eq!(v.len(), 3);
        assert!(sorted_non_overlapping(&v));
        assert_eq!(v[1].length, 1);
        assert_eq!(v[1].source, PartSource::Zeros);
        // Tail (raw) starts at 51 with len 49.
        assert_eq!(v[2].target_offset, 51);
        assert_eq!(v[2].length, 49);
    }

    #[test]
    fn single_byte_empty_block_fully_contained_splits_existing_into_three() {
        // 1-byte EmptyBlock isn't structurally meaningful (units * 128 == 128
        // at minimum), but the *truncation surface* still has to handle the
        // case where an incoming EmptyBlock fully covers a contained span of
        // an existing larger region. Construct an existing region long enough
        // to be split by a 128-byte EmptyBlock (the smallest valid one), with
        // the EmptyBlock landing strictly inside it.
        let mut v = vec![raw(0, 256, 1000)];
        insert(&mut v, empty_block(100, 1)); // length = 128
        assert_eq!(v.len(), 3);
        assert!(sorted_non_overlapping(&v));
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[0].length, 100);
        assert_eq!(v[1].target_offset, 100);
        assert_eq!(v[1].length, 128);
        assert!(matches!(v[1].source, PartSource::EmptyBlock { units: 1 }));
        assert_eq!(v[2].target_offset, 228);
        assert_eq!(v[2].length, 28);
    }

    #[test]
    fn overlap_spans_multiple_with_truncation_on_both_sides() {
        // existing [0..50), [60..90), [100..150); new [30..120).
        // After: [0..30) raw, [30..120) zeros, [120..150) raw.
        let mut v = vec![raw(0, 50, 1000), raw(60, 30, 2000), raw(100, 50, 3000)];
        insert(&mut v, zeros(30, 90));
        assert_eq!(v.len(), 3);
        assert_eq!(v[0].target_offset, 0);
        assert_eq!(v[0].length, 30);
        assert_eq!(v[1].target_offset, 30);
        assert_eq!(v[1].length, 90);
        assert_eq!(v[1].source, PartSource::Zeros);
        assert_eq!(v[2].target_offset, 120);
        assert_eq!(v[2].length, 30);
        // tail (was [100..150) raw src=3000) skipped 20 bytes.
        match &v[2].source {
            PartSource::Patch { offset, kind, .. } => {
                assert_eq!(*offset, 3020);
                assert_eq!(*kind, PatchSourceKind::Raw { len: 30 });
            }
            other => panic!("expected Raw Patch tail, got {other:?}"),
        }
        assert!(sorted_non_overlapping(&v));
    }
}