diffy 0.5.0

//! Git binary diffs support.
//!
//! This module provides parsing and decoding for Git's binary diff format,
//! as generated by `git diff --binary` or `git format-patch --binary`.
//!
//! Based on [DiffX Binary Diffs specification](https://diffx.org/spec/binary-diffs.html).

#[cfg(feature = "binary")]
mod base85;
#[cfg(feature = "binary")]
mod delta;

#[cfg(feature = "binary")]
use alloc::vec::Vec;
use core::fmt;
use core::ops::Range;

/// Cap preallocation when the size comes from untrusted input.
///
/// This prevents instant OOM from a bogus header.
/// The vec grows as needed if the actual output is larger.
#[cfg(feature = "binary")]
const MAX_PREALLOC: u64 = 64 * 1024; // 64 KiB

/// The type of a binary patch block.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinaryBlockKind {
    /// [Literal](https://diffx.org/spec/binary-diffs.html#git-literal-binary-diffs):
    /// contains the full file content, zlib-compressed and Base85-encoded.
    Literal,
    /// [Delta](https://diffx.org/spec/binary-diffs.html#git-delta-binary-diffs):
    /// contains delta instructions to transform one file into another.
    Delta,
}

/// A single block in a binary patch.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BinaryBlock<'a> {
    /// The type of this block (literal content or delta instructions).
    pub kind: BinaryBlockKind,
    /// The encoded data.
    pub data: BinaryData<'a>,
}

/// A parsed binary patch.
///
/// A binary patch contains encoded binary data that can be decoded
/// to recover the original and modified file contents.
///
/// Git may use different encodings for each direction:
///
/// - `literal`: full file content
/// - `delta`: instructions to transform one file into another
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum BinaryPatch<'a> {
    /// A full binary patch with forward and reverse data.
    ///
    /// The forward block transforms original -> modified.
    /// The reverse block transforms modified -> original.
    ///
    /// Each block can independently be either `literal` or `delta`.
    Full {
        /// Forward transformation (original -> modified).
        forward: BinaryBlock<'a>,
        /// Reverse transformation (modified -> original).
        reverse: BinaryBlock<'a>,
    },
    /// A Git binary diff marker.
    ///
    /// This represents the `Binary files a/path and b/path differ` case,
    /// where git detected a binary change but didn't include the actual data.
    ///
    /// Calling [`apply()`](Self::apply) on this variant returns an error.
    Marker,
}

impl<'a> BinaryPatch<'a> {
    /// Applies a binary patch forward: original -> modified.
    ///
    /// - If the forward block is `Literal`: returns the decoded content directly.
    /// - If the forward block is `Delta`: applies delta instructions to `original`.
    ///
    /// Unlike `git apply`, this doesn't validate the original content hash.
    ///
    /// # Examples
    ///
    /// ```
    /// use diffy::patch_set::ParseOptions;
    /// use diffy::patch_set::PatchSet;
    ///
    /// let input = b"\
    /// diff --git a/blob b/blob
    /// index e69de29..0000000 100644
    /// GIT binary patch
    /// literal 10
    /// UcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k
    ///
    /// literal 0
    /// KcmV+b0RR6000031
    ///
    /// ";
    ///
    /// let patch = PatchSet::parse_bytes(input, ParseOptions::gitdiff())
    ///     .next()
    ///     .unwrap()
    ///     .unwrap();
    /// let binary = patch.patch().as_binary().unwrap();
    ///
    /// assert_eq!(
    ///     binary.apply(&[]).unwrap(),
    ///     b"\0\x01\x02\x03\x04\x05\x06\x07\x08\t"
    /// );
    /// ```
    #[cfg(feature = "binary")]
    #[cfg_attr(docsrs, doc(cfg(feature = "binary")))]
    pub fn apply(&self, original: &[u8]) -> Result<Vec<u8>, BinaryPatchParseError> {
        match self {
            BinaryPatch::Full { forward, .. } => Self::apply_block(forward, original),
            BinaryPatch::Marker => Err(BinaryPatchParseErrorKind::NoBinaryData.into()),
        }
    }

    /// Applies a binary patch in reverse: modified -> original.
    ///
    /// - If the reverse block is `Literal`: returns the decoded content directly.
    /// - If the reverse block is `Delta`: applies delta instructions to `modified`.
    ///
    /// Unlike `git apply`, this doesn't validate the modified content hash.
    ///
    /// # Examples
    ///
    /// ```
    /// use diffy::patch_set::ParseOptions;
    /// use diffy::patch_set::PatchSet;
    ///
    /// let input = b"\
    /// diff --git a/blob b/blob
    /// index e69de29..0000000 100644
    /// GIT binary patch
    /// literal 10
    /// UcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k
    ///
    /// literal 0
    /// KcmV+b0RR6000031
    ///
    /// ";
    ///
    /// let patch = PatchSet::parse_bytes(input, ParseOptions::gitdiff())
    ///     .next()
    ///     .unwrap()
    ///     .unwrap();
    /// let binary = patch.patch().as_binary().unwrap();
    ///
    /// assert_eq!(binary.apply_reverse(&[]).unwrap(), b"");
    /// ```
    #[cfg(feature = "binary")]
    #[cfg_attr(docsrs, doc(cfg(feature = "binary")))]
    pub fn apply_reverse(&self, modified: &[u8]) -> Result<Vec<u8>, BinaryPatchParseError> {
        match self {
            BinaryPatch::Full { reverse, .. } => Self::apply_block(reverse, modified),
            BinaryPatch::Marker => Err(BinaryPatchParseErrorKind::NoBinaryData.into()),
        }
    }

    /// Applies a single block (either literal or delta).
    #[cfg(feature = "binary")]
    fn apply_block(block: &BinaryBlock<'_>, base: &[u8]) -> Result<Vec<u8>, BinaryPatchParseError> {
        match block.kind {
            BinaryBlockKind::Literal => Self::decode_data(&block.data),
            BinaryBlockKind::Delta => {
                let delta_instructions = Self::decode_data(&block.data)?;
                delta::apply(base, &delta_instructions).map_err(BinaryPatchParseError::from)
            }
        }
    }

    /// See [Decoding Logic](https://diffx.org/spec/binary-diffs.html#decoding-logic)
    #[cfg(feature = "binary")]
    fn decode_data(binary_data: &BinaryData<'_>) -> Result<Vec<u8>, BinaryPatchParseError> {
        use alloc::vec;
        use zlib_rs::Inflate;
        use zlib_rs::InflateFlush;
        use zlib_rs::Status;

        let compressed = decode_base85_lines(binary_data.data)?;

        // Bound the initial allocation so a bogus header can't request
        // gigabytes upfront. The output grows as inflation produces data.
        let initial_len = binary_data.size.clamp(1, MAX_PREALLOC) as usize;
        let mut output: Vec<u8> = vec![0; initial_len];

        let mut inflate = Inflate::new(true, 15);
        let mut in_pos = 0usize;
        let mut out_pos = 0usize;

        loop {
            let prev_in = inflate.total_in();
            let prev_out = inflate.total_out();

            let status = inflate
                .decompress(
                    &compressed[in_pos..],
                    &mut output[out_pos..],
                    InflateFlush::Finish,
                )
                .map_err(|e| BinaryPatchParseErrorKind::DecompressionFailed(e.as_str()))?;

            in_pos += (inflate.total_in() - prev_in) as usize;
            out_pos += (inflate.total_out() - prev_out) as usize;

            match status {
                Status::StreamEnd => {
                    output.truncate(out_pos);
                    break;
                }
                Status::Ok | Status::BufError => {
                    if out_pos == output.len() {
                        // Output buffer is full: grow and keep inflating.
                        let new_len = output.len().saturating_mul(2);
                        output.resize(new_len, 0);
                    }
                }
            }
        }

        if output.len() as u64 != binary_data.size {
            return Err(BinaryPatchParseErrorKind::DecompressedSizeMismatch {
                expected: binary_data.size,
                actual: output.len() as u64,
            }
            .into());
        }

        Ok(output)
    }
}

/// Represents a single binary payload in a Git binary diff.
///
/// For example, the following patch block
///
/// * is parsed as `BinaryData { size: 10, data: b"UcmV+l0QLU>0RjUA1qKHQ2>\`DEE&u=k" }`
/// * The line starts with a length indicator (`U` = 21 decoded bytes)
///
///
/// ```text
/// literal 10
/// UcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BinaryData<'a> {
    /// Uncompressed size in bytes.
    pub size: u64,
    /// Raw Base85 lines with length indicators.
    pub data: &'a [u8],
}

/// Error type for binary patch operations.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BinaryPatchParseError {
    pub(crate) kind: BinaryPatchParseErrorKind,
    span: Option<Range<usize>>,
}

impl BinaryPatchParseError {
    /// Creates a new error with the given kind and span.
    pub(crate) fn new(kind: BinaryPatchParseErrorKind, span: Range<usize>) -> Self {
        Self {
            kind,
            span: Some(span),
        }
    }

    /// Returns the byte range in the input where the error occurred.
    #[expect(unused)]
    pub(crate) fn span(&self) -> Option<Range<usize>> {
        self.span.clone()
    }
}

impl fmt::Display for BinaryPatchParseError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some(span) = &self.span {
            write!(
                f,
                "error parsing binary patch at byte {}: {}",
                span.start, self.kind
            )
        } else {
            write!(f, "error parsing binary patch: {}", self.kind)
        }
    }
}

impl core::error::Error for BinaryPatchParseError {}

#[cfg(feature = "binary")]
impl From<base85::Base85Error> for BinaryPatchParseError {
    fn from(e: base85::Base85Error) -> Self {
        BinaryPatchParseErrorKind::Base85(e).into()
    }
}

#[cfg(feature = "binary")]
impl From<delta::DeltaError> for BinaryPatchParseError {
    fn from(e: delta::DeltaError) -> Self {
        BinaryPatchParseErrorKind::Delta(e).into()
    }
}

impl From<BinaryPatchParseErrorKind> for BinaryPatchParseError {
    fn from(kind: BinaryPatchParseErrorKind) -> Self {
        Self { kind, span: None }
    }
}

/// The kind of error that occurred when parsing a binary patch.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub(crate) enum BinaryPatchParseErrorKind {
    /// Missing or invalid "GIT binary patch" header.
    InvalidHeader,

    /// First binary block (forward) not found.
    MissingForwardBlock,

    /// Second binary block (reverse) not found.
    MissingReverseBlock,

    /// No binary data available (marker-only patch).
    #[cfg_attr(not(feature = "binary"), expect(dead_code))]
    NoBinaryData,

    /// Invalid line length indicator in Base85 data.
    #[cfg_attr(not(feature = "binary"), expect(dead_code))]
    InvalidLineLengthIndicator,

    /// Base85 decoding failed.
    #[cfg(feature = "binary")]
    Base85(base85::Base85Error),

    /// Delta application failed.
    #[cfg(feature = "binary")]
    Delta(delta::DeltaError),

    /// Zlib decompression failed.
    #[cfg(feature = "binary")]
    DecompressionFailed(&'static str),

    /// Decompressed size doesn't match declared size.
    #[cfg(feature = "binary")]
    DecompressedSizeMismatch { expected: u64, actual: u64 },
}

impl fmt::Display for BinaryPatchParseErrorKind {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidHeader => write!(f, "invalid binary patch header"),
            Self::MissingForwardBlock => write!(f, "first binary block not found"),
            Self::MissingReverseBlock => write!(f, "second binary block not found"),
            Self::NoBinaryData => write!(f, "no binary data available"),
            Self::InvalidLineLengthIndicator => write!(f, "invalid line length indicator"),
            #[cfg(feature = "binary")]
            Self::Base85(e) => write!(f, "{e}"),
            #[cfg(feature = "binary")]
            Self::Delta(e) => write!(f, "{e}"),
            #[cfg(feature = "binary")]
            Self::DecompressionFailed(msg) => write!(f, "decompression failed: {msg}"),
            #[cfg(feature = "binary")]
            Self::DecompressedSizeMismatch { expected, actual } => {
                write!(
                    f,
                    "decompressed size mismatch: expected {expected}, got {actual}"
                )
            }
        }
    }
}

/// Simple streaming parser for binary patches.
struct BinaryParser<'a> {
    input: &'a [u8],
    offset: usize,
}

impl<'a> BinaryParser<'a> {
    fn new(input: &'a [u8]) -> Self {
        Self { input, offset: 0 }
    }

    /// Creates an error with the current offset as span.
    fn error(&self, kind: BinaryPatchParseErrorKind) -> BinaryPatchParseError {
        BinaryPatchParseError::new(kind, self.offset..self.offset)
    }

    fn next_line(&mut self) -> Option<&'a [u8]> {
        let rest = &self.input[self.offset..];
        if rest.is_empty() {
            return None;
        }
        let (line, skip) = match rest.iter().position(|&b| b == b'\n') {
            Some(pos) => (&rest[..pos], pos + 1),
            None => (rest, rest.len()),
        };
        self.offset += skip;
        Some(line.strip_suffix(b"\r").unwrap_or(line))
    }
}

/// Parses binary patch content after git extended headers.
///
/// Expects input starting with "GIT binary patch" line.
/// Returns the parsed patch and the number of bytes consumed.
///
/// Format:
///
/// ```text
/// GIT binary patch
/// <literal|delta> <modified_size>
/// <base85_lines>
///
/// <literal|delta> <original_size>
/// <base85_lines>
/// ```
pub(crate) fn parse_binary_patch(
    input: &[u8],
) -> Result<(BinaryPatch<'_>, usize), BinaryPatchParseError> {
    let mut parser = BinaryParser::new(input);

    // Expect "GIT binary patch" marker
    if parser.next_line() != Some(b"GIT binary patch".as_slice()) {
        return Err(parser.error(BinaryPatchParseErrorKind::InvalidHeader));
    }

    // Parse first block (forward: original -> modified)
    let Some(forward) = parse_binary_block(&mut parser) else {
        return Err(parser.error(BinaryPatchParseErrorKind::MissingForwardBlock));
    };

    // Parse second block (reverse: modified -> original)
    let Some(reverse) = parse_binary_block(&mut parser) else {
        return Err(parser.error(BinaryPatchParseErrorKind::MissingReverseBlock));
    };

    Ok((BinaryPatch::Full { forward, reverse }, parser.offset))
}

/// Parses a single binary block.
///
/// Returns a `BinaryBlock` with kind (literal/delta) and data.
fn parse_binary_block<'a>(parser: &mut BinaryParser<'a>) -> Option<BinaryBlock<'a>> {
    // Parse "literal 10" or "delta 18"
    let format_line = parser.next_line()?;
    let space = format_line.iter().position(|&b| b == b' ')?;
    let (patch_type, rest) = format_line.split_at(space);
    let size_str = core::str::from_utf8(&rest[1..]).ok()?;
    let size: u64 = size_str.parse().ok()?;

    let kind = match patch_type {
        b"literal" => BinaryBlockKind::Literal,
        b"delta" => BinaryBlockKind::Delta,
        _ => return None,
    };

    // Consume Base85 lines until blank line, tracking the end of actual data.
    let data_start = parser.offset;
    let mut data_end = data_start;
    while let Some(line) = parser.next_line() {
        if line.is_empty() {
            break;
        }
        data_end = parser.offset;
    }

    // Slice the data lines, stripping the final line ending.
    let data = &parser.input[data_start..data_end];
    let data = data
        .strip_suffix(b"\r\n".as_slice())
        .or_else(|| data.strip_suffix(b"\n".as_slice()))
        .unwrap_or(data);

    Some(BinaryBlock {
        kind,
        data: BinaryData { size, data },
    })
}

/// Decodes multi-line Base85 data with length indicators.
///
/// Each line has the format: `<len_c><data>`
///
/// From [5.1.1. Binary Payloads](https://diffx.org/spec/binary-diffs.html#binary-payloads):
///
/// > Each line represents up to 52 bytes of pre-encoded data.
/// > There may be an unlimited number of lines.
/// > They contain the following fields:
/// >
/// >  * `len_c` is a line length character.
/// >     This encodes the length of the (pre-encoded) data written on this line.
/// >  * `data` is Base85-encoded data for this line.
#[cfg(feature = "binary")]
fn decode_base85_lines(data: &[u8]) -> Result<Vec<u8>, BinaryPatchParseError> {
    // A rough estimate: In Base85, 5 chars -> 4 bytes
    let mut result = Vec::with_capacity(data.len() * 4 / 5);

    for line in data.split(|&b| b == b'\n') {
        let line = line.strip_suffix(b"\r".as_slice()).unwrap_or(line);
        if line.is_empty() {
            continue;
        }

        let length = decode_line_length(line[0])
            .ok_or(BinaryPatchParseErrorKind::InvalidLineLengthIndicator)?;
        let encoded = &line[1..];
        let start = result.len();
        base85::decode_into(encoded, &mut result)?;
        result.truncate(start + length);
    }

    Ok(result)
}

/// Decodes a line length character to its numeric value.
///
/// From [Line Length Characters](https://diffx.org/spec/binary-diffs.html#line-length-characters):
///
/// > Each encoded line in a binary diff payload is prefixed by a line length character.
/// > This encodes the length of the compressed (but not encoded) data for the line.
/// >
/// > Line length characters always represent a value between 1 and 52:
/// >
/// > * A value of A-Z represents a number between 1..26.
/// > * A value of a-z represents a number between 27..52.
#[cfg(feature = "binary")]
fn decode_line_length(c: u8) -> Option<usize> {
    match c {
        b'A'..=b'Z' => Some((c - b'A' + 1) as usize),
        b'a'..=b'z' => Some((c - b'a' + 27) as usize),
        _ => None,
    }
}

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

    #[test]
    fn parse_literal_format_simple() {
        let input = b"GIT binary patch\nliteral 10\nUcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k\n\nliteral 0\nKcmV+b0RR6000031\n\n";
        let (patch, consumed) = parse_binary_patch(input).unwrap();

        assert_eq!(consumed, input.len());
        match &patch {
            BinaryPatch::Full { forward, reverse } => {
                assert_eq!(forward.kind, BinaryBlockKind::Literal);
                assert_eq!(forward.data.size, 10);
                assert_eq!(reverse.kind, BinaryBlockKind::Literal);
                assert_eq!(reverse.data.size, 0);
            }
            _ => panic!("expected Full variant"),
        }
    }

    #[test]
    fn parse_delta_format() {
        let input = b"GIT binary patch\ndelta 18\nccmV+t0PX*P2!IH%^Z^9`00000v-trB0x!=5aR2}S\n\ndelta 18\nccmV+t0PX*P2!IH%^Z^BFm9#}av-trB0zxAOrvLx|\n\n";
        let (patch, _) = parse_binary_patch(input).unwrap();

        match &patch {
            BinaryPatch::Full { forward, reverse } => {
                assert_eq!(forward.kind, BinaryBlockKind::Delta);
                assert_eq!(forward.data.size, 18);
                assert_eq!(reverse.kind, BinaryBlockKind::Delta);
                assert_eq!(reverse.data.size, 18);
            }
            _ => panic!("expected Full variant"),
        }
    }

    #[test]
    fn parse_invalid_header() {
        // Without "GIT binary patch" marker, parse_binary_patch returns error
        let input = b"literal 10\nUcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k\n\n";
        let err = parse_binary_patch(input).unwrap_err();
        assert_eq!(err.kind, BinaryPatchParseErrorKind::InvalidHeader);
    }

    #[test]
    fn parse_with_crlf_line_endings() {
        let input = b"GIT binary patch\r\nliteral 10\r\nUcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k\r\n\r\nliteral 0\r\nKcmV+b0RR6000031\r\n\r\n";
        let (patch, consumed) = parse_binary_patch(input).unwrap();

        assert_eq!(consumed, input.len());
        match &patch {
            BinaryPatch::Full { forward, reverse } => {
                assert_eq!(forward.kind, BinaryBlockKind::Literal);
                assert_eq!(forward.data.size, 10);
                assert_eq!(reverse.kind, BinaryBlockKind::Literal);
                assert_eq!(reverse.data.size, 0);
            }
            _ => panic!("expected Full variant"),
        }
    }

    #[test]
    fn parse_mixed_format() {
        // Git can use different encoding for each direction
        let input = b"GIT binary patch\nliteral 10\nUcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k\n\ndelta 18\nccmV+t0PX*P2!IH%^Z^9`00000v-trB0x!=5aR2}S\n\n";
        let (patch, _) = parse_binary_patch(input).unwrap();

        match &patch {
            BinaryPatch::Full { forward, reverse } => {
                assert_eq!(forward.kind, BinaryBlockKind::Literal);
                assert_eq!(reverse.kind, BinaryBlockKind::Delta);
            }
            _ => panic!("expected Full variant"),
        }
    }
}

#[cfg(test)]
#[cfg(feature = "binary")]
mod apply_tests {
    use super::*;
    use alloc::vec;

    #[test]
    fn decode_line_length_uppercase() {
        assert_eq!(decode_line_length(b'A'), Some(1));
        assert_eq!(decode_line_length(b'B'), Some(2));
        assert_eq!(decode_line_length(b'Z'), Some(26));
    }

    #[test]
    fn decode_line_length_lowercase() {
        assert_eq!(decode_line_length(b'a'), Some(27));
        assert_eq!(decode_line_length(b'b'), Some(28));
        assert_eq!(decode_line_length(b'z'), Some(52));
    }

    #[test]
    fn decode_line_length_invalid() {
        assert_eq!(decode_line_length(b'0'), None);
        assert_eq!(decode_line_length(b'!'), None);
        assert_eq!(decode_line_length(b' '), None);
    }

    #[test]
    fn apply_literal_patch() {
        let input = b"GIT binary patch\nliteral 10\nUcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k\n\nliteral 0\nKcmV+b0RR6000031\n\n";
        let (patch, _) = parse_binary_patch(input).unwrap();

        let modified = patch.apply(&[]).unwrap();
        assert_eq!(modified.len(), 10);
        assert_eq!(modified, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

        let original = patch.apply_reverse(&[]).unwrap();
        assert_eq!(original.len(), 0);
    }

    #[test]
    fn literal_size_mismatch() {
        // Declared size 99 but actual decompressed data is 10 bytes.
        let input = b"GIT binary patch\nliteral 99\nUcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k\n\nliteral 0\nKcmV+b0RR6000031\n\n";
        let (patch, _) = parse_binary_patch(input).unwrap();

        let err = patch.apply(&[]).unwrap_err();
        assert!(matches!(
            err.kind,
            BinaryPatchParseErrorKind::DecompressedSizeMismatch {
                expected: 99,
                actual: 10
            }
        ));
    }

    #[test]
    fn apply_with_crlf_line_endings() {
        let input = b"GIT binary patch\r\nliteral 10\r\nUcmV+l0QLU>0RjUA1qKHQ2>`DEE&u=k\r\n\r\nliteral 0\r\nKcmV+b0RR6000031\r\n\r\n";
        let (patch, _) = parse_binary_patch(input).unwrap();

        let modified = patch.apply(&[]).unwrap();
        assert_eq!(modified, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
        let original = patch.apply_reverse(&[]).unwrap();
        assert_eq!(original.len(), 0);
    }
}