bazaar 3.5.3

use crate::groupcompress::delta::{
    decode_instruction, read_base128_int, write_base128_int, write_instruction, Instruction,
    MAX_COPY_SIZE, MAX_INSERT_SIZE,
};
use std::collections::HashMap;
use std::convert::TryInto;
use std::io::Write;

/// diff-delta.rs: generate a delta between two buffers
///
/// This code was greatly inspired by parts of LibXDiff from Davide Libenzi
/// http://www.xmailserver.org/xdiff-lib.html
///
/// Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
/// Adapted for Bazaar by John Arbash Meinel <john@arbash-meinel.com> (C) 2009
///
/// Ported to Rust by Jelmer Vernooij <jelmer@jelmer.uk> and significantly rewritten.
///
/// This program is free software; you can redistribute it and/or modify
/// it under the terms of the GNU General Public License as published by
/// the Free Software Foundation; either version 2 of the License, or
/// (at your option) any later version.
///
/// NB: The version in GIT is 'version 2 of the Licence only', however Nicolas
/// has granted permission for use under 'version 2 or later' in private email
/// to Robert Collins and Karl Fogel on the 6th April 2009.

// maximum hash entry list for the same hash bucket
const RABIN_SHIFT: usize = 23;
const RABIN_WINDOW: usize = 16;

const T: &[u32; 256] = &[
    0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344, 0x508c0e37, 0xfbd5bae6,
    0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259, 0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc,
    0x18fd9e54, 0xb3a42a85, 0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2,
    0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a, 0x440f5f49, 0xef56eb98,
    0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db, 0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e,
    0x3d85f382, 0x96dc4753, 0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964,
    0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8, 0x798aaccb, 0xd2d3181a,
    0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5, 0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730,
    0x63f67950, 0xc8afcd81, 0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6,
    0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e, 0x3f04b84d, 0x945d0c9c,
    0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77, 0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2,
    0x7775282e, 0xdc2c9cff, 0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8,
    0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc, 0x02814bcf, 0xa9d8ff1e,
    0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1, 0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034,
    0x4af0dbac, 0xe1a96f7d, 0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a,
    0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2, 0x16021ab1, 0xbd5bae60,
    0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02, 0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97,
    0x60cb895b, 0xcb923d8a, 0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd,
    0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61, 0x24c4d612, 0x8f9d62c3,
    0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c, 0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9,
    0x5d4e7ad9, 0xf617ce08, 0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f,
    0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7, 0x01bcbbc4, 0xaae50f15,
    0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe, 0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b,
    0x49cd2ba7, 0xe2949f76, 0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141,
    0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65, 0x5fcf3116, 0xf49685c7,
    0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78, 0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed,
    0x17bea175, 0xbce715a4, 0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93,
    0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b, 0x4b4c6068, 0xe015d4b9,
    0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa, 0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f,
    0x32c6cca3, 0x999f7872, 0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645,
    0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99, 0x76c993ea, 0xdd90273b,
    0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84, 0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811,
];

const U: &[u32; 256] = &[
    0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a, 0x510da98c, 0x2fb88981,
    0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48, 0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f,
    0x1cf9751c, 0x624c5511, 0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d,
    0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8, 0x4388661e, 0x3d3d4613,
    0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe, 0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9,
    0x378e50b6, 0x493b70bb, 0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937,
    0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e, 0x740636a8, 0x0ab316a5,
    0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c, 0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b,
    0x73e5d470, 0x0d50f47d, 0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1,
    0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4, 0x2c94c772, 0x5221e77f,
    0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa, 0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed,
    0x61601be2, 0x1fd53bef, 0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263,
    0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302, 0x1b1a97c4, 0x65afb7c9,
    0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000, 0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47,
    0x56ee4b54, 0x285b6b59, 0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5,
    0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90, 0x099f5856, 0x772a785b,
    0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7, 0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0,
    0x42eea6bf, 0x3c5b86b2, 0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e,
    0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467, 0x0166c0a1, 0x7fd3e0ac,
    0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765, 0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22,
    0x7560f609, 0x0bd5d604, 0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88,
    0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd, 0x2a11e50b, 0x54a4c506,
    0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3, 0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94,
    0x67e5399b, 0x19501996, 0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a,
    0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b, 0x6e7a61cd, 0x10cf41c0,
    0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609, 0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e,
    0x238ebd5d, 0x5d3b9d50, 0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc,
    0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99, 0x7cffae5f, 0x024a8e52,
    0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf, 0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8,
    0x08f998f7, 0x764cb8fa, 0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176,
    0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f, 0x4b71fee9, 0x35c4dee4,
    0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d, 0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a,
];

// Result type for functions that have multiple failure modes
#[derive(Debug)]
pub enum DeltaError {
    Io(std::io::Error), // An IO error occurred
    DeltaTooLarge,      // The delta is too large to be encoded
}

impl std::fmt::Display for DeltaError {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            DeltaError::Io(err) => write!(f, "IO error: {}", err),
            DeltaError::DeltaTooLarge => write!(f, "Delta too large"),
        }
    }
}

impl From<std::io::Error> for DeltaError {
    fn from(err: std::io::Error) -> DeltaError {
        DeltaError::Io(err)
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RabinHash(u32);

impl RabinHash {
    pub fn pushright(&mut self, c: u8) {
        self.0 = ((self.0 << 8) | c as u32) ^ T[(self.0 >> RABIN_SHIFT) as usize];
    }

    pub fn popleft(&mut self, c: u8) {
        self.0 ^= U[c as usize];
    }

    pub fn finish(&self) -> u32 {
        self.0
    }
}

impl From<RabinHash> for u32 {
    fn from(val: RabinHash) -> u32 {
        val.0
    }
}

pub fn rabin_hash(data: [u8; RABIN_WINDOW]) -> RabinHash {
    assert_eq!(data.len(), RABIN_WINDOW);
    let mut val = RabinHash(0);
    for c in data.iter().take(RABIN_WINDOW) {
        val.pushright(*c);
    }
    val
}

pub struct RabinWindow {
    data: [u8; RABIN_WINDOW],
    pos: usize,
    hash: RabinHash,
}

impl RabinWindow {
    pub fn new(data: [u8; RABIN_WINDOW]) -> Self {
        let hash = rabin_hash(data);
        RabinWindow { data, hash, pos: 0 }
    }

    pub fn push(&mut self, c: u8) {
        // Cancel the byte that has just aged out of the window, then mix in the
        // new byte -- the same order git's diff-delta uses, which keeps the
        // rolled value equal to a fresh `rabin_hash` of the shifted window.
        self.hash.popleft(self.data[self.pos]);
        self.hash.pushright(c);
        self.data[self.pos] = c;
        self.pos = (self.pos + 1) % RABIN_WINDOW;
    }

    pub fn hash(&self) -> RabinHash {
        self.hash
    }
}

/// A persistent index over one or more source buffers.
///
/// The index keeps every indexed source byte in a single owned `buffer`
/// laid out at its absolute offset in the logical concatenated chunk
/// stream (mini-header bytes between sources become never-indexed gaps).
/// Hash entries therefore only need to store that absolute offset: the
/// content slice for an entry is `&buffer[offset..]`. This lets sources be
/// added incrementally with `add_fulltext`/`add_delta` and keeps
/// `make_delta` linear in the target size instead of rebuilding the whole
/// index on every call.
#[derive(Debug, Clone, Default)]
pub struct DeltaIndex {
    entries: HashMap<u32, Vec<IndexEntry>>,
    /// Concatenated source bytes positioned at their absolute stream
    /// offset. Always the same length as `last_offset`.
    buffer: Vec<u8>,
    last_offset: usize,
}

#[derive(Debug, Clone, Copy, Default)]
pub struct IndexEntry {
    /// Absolute offset into the logical chunk stream (and into `buffer`).
    pub offset: usize,
}

/// Length of the common byte prefix of `a` and `b`.
///
/// Compares a machine word at a time and locates the first differing byte
/// with `trailing_zeros`, which is markedly faster than a byte-at-a-time
/// scan for the long matches that dominate delta generation.
fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
    let n = a.len().min(b.len());
    let mut i = 0;
    const W: usize = std::mem::size_of::<usize>();
    while i + W <= n {
        // Read unaligned native-endian words; equality and the index of the
        // first mismatching byte are endianness-independent because we locate
        // it via the count of matching low-order *bytes*.
        let wa = usize::from_ne_bytes(a[i..i + W].try_into().unwrap());
        let wb = usize::from_ne_bytes(b[i..i + W].try_into().unwrap());
        let diff = wa ^ wb;
        if diff != 0 {
            // Number of equal bytes before the first differing one. On
            // little-endian the first byte is in the low bits; on big-endian
            // it is in the high bits, so pick the matching intrinsic.
            let eq_bytes = if cfg!(target_endian = "little") {
                diff.trailing_zeros() / 8
            } else {
                diff.leading_zeros() / 8
            };
            return i + eq_bytes as usize;
        }
        i += W;
    }
    while i < n && a[i] == b[i] {
        i += 1;
    }
    i
}

impl DeltaIndex {
    fn iter_matches(&self, val: &RabinHash) -> impl Iterator<Item = &IndexEntry> + '_ {
        self.entries
            .get(&val.finish())
            .into_iter()
            .flat_map(|v| v.iter())
    }

    fn find_match(
        &self,
        hash: RabinHash,
        data: &[u8],
        mut min_size: usize,
        good_enough_size: Option<usize>,
    ) -> Option<(IndexEntry, usize)> {
        let mut msource = None;

        for entry in self.iter_matches(&hash) {
            // The target can't be matched beyond its own length, so once a
            // match already covers all of `data` no candidate can improve on
            // it and the byte-at-min_size probe below would also be out of
            // range.
            if min_size >= data.len() {
                break;
            }
            let entry_data = &self.buffer[entry.offset..];
            if entry_data.len() <= min_size {
                // no point in checking this one
                continue;
            }
            // A candidate can only beat the current best if it matches at
            // least one byte further, i.e. the byte at min_size matches. The
            // hash only guarantees the window matched, not this position, so
            // this is a cheap O(1) rejection that lets us skip the full
            // prefix scan for the common case of a non-improving candidate.
            // (Both slices are known to be longer than min_size here: data
            // because it contained the hashed window, entry_data by the check
            // above.)
            if entry_data[min_size] != data[min_size] {
                continue;
            }
            let overlap = common_prefix_len(entry_data, data);
            if overlap > min_size {
                /* this is our best match so far */
                min_size = overlap;
                msource = Some(*entry);
                if let Some(good_enough_size) = good_enough_size {
                    if min_size >= good_enough_size {
                        /* good enough */
                        return Some((msource.unwrap(), min_size));
                    }
                }
            }
        }

        msource.map(|s| (s, min_size))
    }

    pub fn new() -> Self {
        Self::default()
    }

    /// Reserve `unused_bytes` of header gap then append `content` to the
    /// owned buffer so it sits at its absolute stream offset.
    fn append_to_buffer(&mut self, unused_bytes: usize, content: &[u8]) {
        self.buffer.resize(self.buffer.len() + unused_bytes, 0);
        self.buffer.extend_from_slice(content);
    }

    pub fn add_delta(&mut self, delta: &[u8], unused_bytes: usize) -> std::io::Result<()> {
        self.append_to_buffer(unused_bytes, delta);
        self.last_offset += unused_bytes;
        let original_len = delta.len();
        let mut remaining = delta;
        read_base128_int(&mut remaining)?;
        let header_len = original_len - remaining.len();
        let mut pos = 0;
        while pos < remaining.len() {
            let (instruction, newpos) = decode_instruction(remaining, pos)
                .map_err(|e| std::io::Error::new(std::io::ErrorKind::InvalidData, e))?;
            match instruction {
                Instruction::Copy { .. } => {}
                Instruction::Insert(data) => {
                    // The create_delta code requires a match at least 4 characters
                    // (including only the last char of the RABIN_WINDOW) before it
                    // will consider it something worth copying rather than inserting.
                    // So we don't want to index anything that we know won't ever be a
                    // match.
                    // pos points to the instruction byte; data starts at pos+1
                    let data_offset = self.last_offset + header_len + pos + 1;
                    for i in 0..data.len().saturating_sub(RABIN_WINDOW) {
                        let val = rabin_hash(data[i..i + RABIN_WINDOW].try_into().unwrap());
                        self.entries
                            .entry(val.into())
                            .or_default()
                            .push(IndexEntry {
                                offset: data_offset + i,
                            })
                    }
                }
            }
            pos = newpos;
        }
        self.last_offset += original_len;
        debug_assert_eq!(self.buffer.len(), self.last_offset);
        Ok(())
    }

    // Compute index data from given buffer
    //
    // # Arguments
    //
    // * `max_bytes_to_index`: Limit the number of regions to sample to this
    //      amount of text. We will store at most max_bytes_to_index / RABIN_WINDOW
    //      pointers into the source text.  Useful if src can be unbounded in size,
    //      and you are willing to trade match accuracy for peak memory.
    pub fn add_fulltext(
        &mut self,
        src: &[u8],
        unused_bytes: usize,
        max_bytes_to_index: Option<usize>,
    ) {
        self.append_to_buffer(unused_bytes, src);
        self.last_offset += unused_bytes;

        let stride = if let Some(max_bytes_to_index) = max_bytes_to_index {
            (std::cmp::min(max_bytes_to_index, src.len()) / RABIN_WINDOW).max(1)
        } else {
            RABIN_WINDOW
        };

        let mut prev_val = None;
        for i in (0..(src.len().max(RABIN_WINDOW) - RABIN_WINDOW)).step_by(stride) {
            let val = rabin_hash(src[i..i + RABIN_WINDOW].try_into().unwrap());
            if Some(val) == prev_val {
                // keep the lowest of consecutive identical hashes
            } else {
                prev_val = Some(val);
                self.entries
                    .entry(val.into())
                    .or_default()
                    .push(IndexEntry {
                        offset: self.last_offset + i,
                    })
            }
        }

        self.last_offset += src.len();
        debug_assert_eq!(self.buffer.len(), self.last_offset);
    }
}

pub fn iter_delta_instructions<'a>(
    index: &'a DeltaIndex,
    target: &'a [u8],
) -> impl Iterator<Item = Instruction<&'a [u8]>> + 'a {
    // Position in target we're currently scanning
    let mut scan_pos: usize = 0;
    // Start of the current insert block (if any)
    let mut insert_start: usize = 0;
    let mut done = false;
    // Rolling hash over `target[scan_pos..scan_pos + RABIN_WINDOW]`, kept in
    // sync with `scan_pos`. `window_pos` is the position the window currently
    // covers; when we only advanced by one byte (the common no-match case) we
    // roll, otherwise (first window, or after a copy jumped scan_pos) we
    // re-seed from scratch.
    let mut window: Option<RabinWindow> = None;
    let mut window_pos: usize = 0;

    std::iter::from_fn(move || -> Option<Instruction<&'a [u8]>> {
        if done {
            return None;
        }

        loop {
            if scan_pos + RABIN_WINDOW > target.len() {
                // Not enough data left for a hash window
                // Emit any remaining data as an insert
                if insert_start < target.len() {
                    let ins = &target[insert_start..];
                    insert_start = target.len();
                    done = true;
                    return Some(Instruction::Insert(ins));
                }
                done = true;
                return None;
            }

            let hash = match window {
                Some(ref mut w) if window_pos + 1 == scan_pos => {
                    // Single-byte advance: roll the entering byte in.
                    w.push(target[scan_pos + RABIN_WINDOW - 1]);
                    window_pos = scan_pos;
                    w.hash()
                }
                _ => {
                    let w = RabinWindow::new(
                        target[scan_pos..scan_pos + RABIN_WINDOW]
                            .try_into()
                            .unwrap(),
                    );
                    let h = w.hash();
                    window = Some(w);
                    window_pos = scan_pos;
                    h
                }
            };
            if let Some((entry, msize)) = index.find_match(hash, &target[scan_pos..], 4, Some(4096))
            {
                // Found a match of at least 4 bytes

                // First, emit any pending insert data before this match
                if scan_pos > insert_start {
                    let ins = &target[insert_start..scan_pos];
                    // Set up state for the copy instruction to be emitted next
                    insert_start = scan_pos;
                    return Some(Instruction::Insert(ins));
                }

                // Emit copy instruction(s) for this match
                let copy_len = msize.min(MAX_COPY_SIZE);
                scan_pos += copy_len;
                insert_start = scan_pos;
                return Some(Instruction::Copy {
                    offset: entry.offset,
                    length: copy_len,
                });
            }

            // No match, advance by one byte
            scan_pos += 1;

            // Check if the current insert block is getting too large
            if scan_pos - insert_start >= MAX_INSERT_SIZE {
                let ins = &target[insert_start..scan_pos];
                insert_start = scan_pos;
                return Some(Instruction::Insert(ins));
            }
        }
    })
}

pub fn create_delta<'a, W: Write>(
    mut writer: W,
    index: &'a DeltaIndex,
    target: &'a [u8],
    max_delta_size: Option<usize>,
) -> Result<(), DeltaError> {
    let mut size = 0;
    // store target buffer size
    size += write_base128_int(&mut writer, target.len() as u128)?;

    if target.len() < RABIN_WINDOW {
        // If the target is smaller than the Rabin window, we can't do any
        // matching, so just write out the whole target as an insert instruction.
        size += write_instruction(&mut writer, &Instruction::Insert(target))?;
        if let Some(max_delta_size) = max_delta_size {
            if size > max_delta_size {
                return Err(DeltaError::DeltaTooLarge);
            }
        }
    } else {
        for instruction in iter_delta_instructions(index, target) {
            size += write_instruction(&mut writer, &instruction)?;
            if let Some(max_delta_size) = max_delta_size {
                if size > max_delta_size {
                    return Err(DeltaError::DeltaTooLarge);
                }
            }
        }
    }

    Ok(())
}

/// Create a delta, this is a wrapper around DeltaIndex.make_delta.
pub fn make_delta(source_bytes: &[u8], target_bytes: &[u8]) -> Vec<u8> {
    let mut out = Vec::new();
    let mut di = DeltaIndex::new();
    di.add_fulltext(source_bytes, 0, None);
    create_delta(&mut out, &di, target_bytes, None).unwrap();
    out
}

/// A `DeltaIndex` that owns its source buffers and indexes them
/// incrementally.
///
/// Each `add_source`/`add_delta_source` call folds the new source into a
/// single persistent [`DeltaIndex`], so `make_delta` only has to scan the
/// target against the already-built index. This is what keeps group
/// compression linear in the total source size — rebuilding the index on
/// every `make_delta` call made it quadratic. The retained source `Vec`s
/// are kept only so callers can read them back (e.g. the PyO3 `_sources`
/// accessor); the index itself owns the bytes it needs.
pub struct OwningDeltaIndex {
    sources: Vec<Vec<u8>>,
    source_offset: usize,
    max_bytes_to_index: Option<usize>,
    index: DeltaIndex,
}

impl OwningDeltaIndex {
    pub fn new(max_bytes_to_index: Option<usize>) -> Self {
        Self {
            sources: Vec::new(),
            source_offset: 0,
            max_bytes_to_index,
            index: DeltaIndex::new(),
        }
    }

    pub fn num_sources(&self) -> usize {
        self.sources.len()
    }

    pub fn is_empty(&self) -> bool {
        self.sources.is_empty()
    }

    pub fn sources(&self) -> &[Vec<u8>] {
        &self.sources
    }

    pub fn source_offset(&self) -> usize {
        self.source_offset
    }

    pub fn set_source_offset(&mut self, value: usize) {
        self.source_offset = value;
    }

    pub fn max_bytes_to_index(&self) -> Option<usize> {
        self.max_bytes_to_index
    }

    pub fn set_max_bytes_to_index(&mut self, value: Option<usize>) {
        self.max_bytes_to_index = value;
    }

    pub fn add_source(&mut self, source: Vec<u8>, unadded_bytes: usize) {
        self.source_offset += unadded_bytes;
        self.source_offset += source.len();
        self.index
            .add_fulltext(&source, unadded_bytes, self.max_bytes_to_index);
        self.sources.push(source);
    }

    pub fn add_delta_source(&mut self, delta: Vec<u8>, unadded_bytes: usize) -> Result<(), String> {
        self.source_offset += unadded_bytes;
        self.source_offset += delta.len();
        self.index
            .add_delta(&delta, unadded_bytes)
            .map_err(|e| e.to_string())?;
        self.sources.push(delta);
        Ok(())
    }

    pub fn make_delta(
        &self,
        target: &[u8],
        max_delta_size: usize,
    ) -> Result<Option<Vec<u8>>, String> {
        if self.sources.is_empty() {
            return Ok(None);
        }

        let max_delta_size = if max_delta_size == 0 {
            None
        } else {
            Some(max_delta_size)
        };

        let mut out = Vec::new();
        match create_delta(&mut out, &self.index, target, max_delta_size) {
            Ok(()) => Ok(Some(out)),
            Err(DeltaError::DeltaTooLarge) => Ok(None),
            Err(e) => Err(e.to_string()),
        }
    }
}

#[cfg(test)]
mod tests {
    const TEXT1: &[u8] = b"This is a bit
of source text
which is meant to be matched
against other text
";

    const TEXT2: &[u8] = b"This is a bit
of source text
which is meant to differ from
against other text
";

    const TEXT3: &[u8] = b"This is a bit
of source text
which is meant to be matched
against other text
except it also
has a lot more data
at the end of the file
";

    #[test]
    fn common_prefix_len_boundaries() {
        use super::common_prefix_len;
        assert_eq!(common_prefix_len(b"", b""), 0);
        assert_eq!(common_prefix_len(b"abc", b"abc"), 3);
        assert_eq!(common_prefix_len(b"abc", b"abd"), 2);
        assert_eq!(common_prefix_len(b"abc", b"xyz"), 0);
        // shorter slice bounds the result
        assert_eq!(common_prefix_len(b"abcdef", b"abc"), 3);
        assert_eq!(common_prefix_len(b"abc", b"abcdef"), 3);
        // mismatches at, just before, and just after a word boundary
        for n in [7usize, 8, 9, 15, 16, 17, 31, 32, 33] {
            let a = vec![0x5au8; n + 4];
            let mut b = a.clone();
            b[n] ^= 0xff;
            assert_eq!(common_prefix_len(&a, &b), n, "mismatch position {n}");
        }
        // full match longer than a word
        let a = vec![0x11u8; 40];
        assert_eq!(common_prefix_len(&a, &a), 40);
    }

    fn apply_delta_test(source: &[u8], delta: &[u8]) -> Vec<u8> {
        use crate::groupcompress::delta::{decode_instruction, Instruction};
        let mut remaining = &delta[..];
        crate::groupcompress::delta::read_base128_int(&mut remaining).unwrap();
        let mut result = Vec::new();
        let mut pos = 0;
        while pos < remaining.len() {
            let (instr, newpos) = decode_instruction(remaining, pos).unwrap();
            match instr {
                Instruction::Copy { offset, length } => {
                    result.extend_from_slice(&source[offset..offset + length]);
                }
                Instruction::Insert(data) => {
                    result.extend_from_slice(data);
                }
            }
            pos = newpos;
        }
        result
    }

    fn assert_delta(source: &[u8], target: &[u8], _expected_delta: &[u8]) {
        let mut di = super::DeltaIndex::new();
        di.add_fulltext(source, 0, None);
        let mut out = Vec::new();
        super::create_delta(&mut out, &di, target, None).unwrap();
        // Verify the delta round-trips correctly
        let result = apply_delta_test(source, &out);
        assert_eq!(target, &result[..], "delta did not round-trip correctly");
    }

    #[test]
    fn randomized_delta_round_trips() {
        // Exercise find_match across many source/target pairs with repetition
        // and edits, so matches of varied lengths (including across word
        // boundaries) are produced and applied back.
        let mut seed = 0x9e37_79b9_7f4a_7c15u64;
        let mut next = || {
            seed = seed
                .wrapping_mul(6364136223846793005)
                .wrapping_add(1442695040888963407);
            (seed >> 33) as u32
        };
        for _ in 0..50 {
            let pool_lines = 4 + (next() % 12) as usize;
            let pool: Vec<Vec<u8>> = (0..pool_lines)
                .map(|_| {
                    let len = 8 + (next() % 60) as usize;
                    (0..len).map(|_| next() as u8).collect()
                })
                .collect();
            let mut source = Vec::new();
            for _ in 0..(20 + next() % 60) {
                source.extend_from_slice(&pool[next() as usize % pool.len()]);
            }
            // target reuses the pool with a few mutations
            let mut target = Vec::new();
            for _ in 0..(20 + next() % 60) {
                let mut line = pool[next() as usize % pool.len()].clone();
                if next() % 4 == 0 && !line.is_empty() {
                    let idx = next() as usize % line.len();
                    line[idx] ^= 0xff;
                }
                target.extend_from_slice(&line);
            }
            assert_delta(&source, &target, &[]);
        }
    }

    #[test]
    fn test_make_noop_delta() {
        assert_delta(TEXT1, TEXT1, b"M\x90M");
        assert_delta(TEXT2, TEXT2, b"N\x90N");
        assert_delta(TEXT3, TEXT3, b"\x87\x01\x90\x87");
    }

    #[test]
    fn test_make_delta() {
        assert_delta(TEXT1, TEXT2, b"N\x90/\x1fdiffer from\nagainst other text\n");
        assert_delta(TEXT2, TEXT1, b"M\x90/\x1ebe matched\nagainst other text\n");
        assert_delta(TEXT3, TEXT1, b"M\x90M");
        assert_delta(TEXT3, TEXT2, b"N\x90/\x1fdiffer from\nagainst other text\n");
    }

    #[test]
    fn test_make_delta_with_large_copies() {
        // We want to have a copy that is larger than 64kB, which forces us to
        // issue multiple copy instructions.
        let big_text = TEXT3.repeat(1220);
        assert_delta(
            big_text.as_slice(),
            big_text.as_slice(),
            vec![
                &b"\xdc\x86\x0a"[..],     // Encoding the length of the uncompressed text
                &b"\x80"[..],             // Copy 64kB, starting at byte 0
                &b"\x84\x01"[..],         // and another 64kB starting at 64kB
                &b"\xb4\x02\x5c\x83"[..], // And the bit of tail.
            ]
            .concat()
            .as_slice(),
        )
    }

    #[test]
    fn owning_index_empty_returns_none() {
        let idx = super::OwningDeltaIndex::new(None);
        assert!(idx.is_empty());
        assert_eq!(idx.num_sources(), 0);
        assert_eq!(idx.source_offset(), 0);
        assert_eq!(idx.make_delta(b"anything", 0).unwrap(), None);
    }

    #[test]
    fn owning_index_round_trip() {
        let mut idx = super::OwningDeltaIndex::new(None);
        idx.add_source(TEXT1.to_vec(), 0);
        assert_eq!(idx.num_sources(), 1);
        assert_eq!(idx.source_offset(), TEXT1.len());

        // A target identical to the source should produce a delta that
        // applies cleanly back to TEXT1.
        let delta = idx.make_delta(TEXT1, 0).unwrap().expect("delta produced");
        let reconstructed = super::super::delta::apply_delta(TEXT1, &delta).unwrap();
        assert_eq!(reconstructed.as_slice(), TEXT1);
    }

    #[test]
    fn owning_index_max_bytes_to_index_setter() {
        let mut idx = super::OwningDeltaIndex::new(Some(1024));
        assert_eq!(idx.max_bytes_to_index(), Some(1024));
        idx.set_max_bytes_to_index(None);
        assert_eq!(idx.max_bytes_to_index(), None);
        idx.set_max_bytes_to_index(Some(2048));
        assert_eq!(idx.max_bytes_to_index(), Some(2048));
    }

    #[test]
    fn owning_index_set_source_offset() {
        // The PyO3 wrapper exposes a setter for source_offset that pokes
        // straight at this field — exercise it directly.
        let mut idx = super::OwningDeltaIndex::new(None);
        assert_eq!(idx.source_offset(), 0);
        idx.set_source_offset(42);
        assert_eq!(idx.source_offset(), 42);
        idx.set_source_offset(0);
        assert_eq!(idx.source_offset(), 0);
    }

    #[test]
    fn owning_index_add_source_with_unadded_bytes_advances_offset() {
        // unadded_bytes is the number of bytes occupied in the surrounding
        // chunk stream by the per-record mini-header that precedes the
        // payload. The index has to advance source_offset over both the
        // header and the payload to keep its internal cursor aligned with
        // the compressor's chunk endpoint.
        let mut idx = super::OwningDeltaIndex::new(None);
        let header_len = 5;
        idx.add_source(TEXT1.to_vec(), header_len);
        assert_eq!(idx.source_offset(), header_len + TEXT1.len());

        idx.add_source(TEXT2.to_vec(), header_len);
        assert_eq!(
            idx.source_offset(),
            2 * (header_len + TEXT1.len()) - TEXT1.len() + TEXT2.len()
        );
    }

    #[test]
    fn owning_index_add_delta_source_round_trip() {
        // Build an index, produce a delta against the first source, register
        // that delta as a delta-source, and check the index keeps working.
        let mut idx = super::OwningDeltaIndex::new(None);
        idx.add_source(TEXT1.to_vec(), 0);
        let initial_offset = idx.source_offset();
        let delta = idx
            .make_delta(TEXT3, 0)
            .unwrap()
            .expect("delta produced for similar text");

        // Registering the delta should advance source_offset by both the
        // mini-header length and the delta payload.
        let header_len = 4;
        idx.add_delta_source(delta.clone(), header_len).unwrap();
        assert_eq!(
            idx.source_offset(),
            initial_offset + header_len + delta.len()
        );
        assert_eq!(idx.num_sources(), 2);
        assert!(!idx.is_empty());

        // The index should still be functional after registering a delta
        // source — making another delta should not crash.
        let _further = idx.make_delta(TEXT2, 0).unwrap();
    }

    #[test]
    fn owning_index_make_delta_uses_multiple_sources() {
        // With two sources sharing similar content, the index should be able
        // to produce a delta and the result must apply cleanly back to the
        // target. We don't assert on which source the matches come from —
        // only that the delta is correct.
        let mut idx = super::OwningDeltaIndex::new(None);
        idx.add_source(TEXT1.to_vec(), 0);
        idx.add_source(TEXT3.to_vec(), 0);

        let delta = idx.make_delta(TEXT3, 0).unwrap().expect("delta");
        let basis = [TEXT1, TEXT3].concat();
        let reconstructed = super::super::delta::apply_delta(&basis, &delta).unwrap();
        assert_eq!(reconstructed.as_slice(), TEXT3);
    }

    #[test]
    fn owning_index_make_delta_respects_size_cap() {
        // A max_delta_size that is below the actual delta length forces the
        // create_delta call to bail with DeltaTooLarge, which the wrapper
        // converts to Ok(None).
        let mut idx = super::OwningDeltaIndex::new(None);
        idx.add_source(TEXT1.to_vec(), 0);
        // 1 byte cap is well below any plausible delta header, so we expect
        // None back from make_delta.
        assert_eq!(idx.make_delta(TEXT3, 1).unwrap(), None);
    }

    #[test]
    fn rolling_window_matches_fresh_hash() {
        // The scan loop rolls the rabin hash one byte at a time; every rolled
        // value must equal a fresh hash of the same window.
        use super::{rabin_hash, RabinWindow, RABIN_WINDOW};
        use std::convert::TryInto;
        let data: Vec<u8> = (0..200u32).map(|i| (i * 31 + 7) as u8).collect();
        let mut window = RabinWindow::new(data[..RABIN_WINDOW].try_into().unwrap());
        assert_eq!(
            window.hash(),
            rabin_hash(data[..RABIN_WINDOW].try_into().unwrap())
        );
        for pos in 1..=(data.len() - RABIN_WINDOW) {
            window.push(data[pos + RABIN_WINDOW - 1]);
            let fresh = rabin_hash(data[pos..pos + RABIN_WINDOW].try_into().unwrap());
            assert_eq!(window.hash(), fresh, "mismatch at pos {pos}");
        }
    }
}