view rust/hg-core/src/revlog/patch.rs @ 48495:e293ff808a05

rhg: Use binary search in manifest lookup

… instead of linear scan, when looking for a single entry based on its path.
Manifest entries are sorted by path, but are variable-size so we can’t use
the standard library’s `[T]::binary_search`. We can still jump to a byte
index and then look around for entry boundaries.

Differential Revision: https://phab.mercurial-scm.org/D11932

use byteorder::{BigEndian, ByteOrder};

/// A chunk of data to insert, delete or replace in a patch
///
/// A chunk is:
/// - an insertion when `!data.is_empty() && start == end`
/// - an deletion when `data.is_empty() && start < end`
/// - a replacement when `!data.is_empty() && start < end`
/// - not doing anything when `data.is_empty() && start == end`
#[derive(Debug, Clone)]
struct Chunk<'a> {
    /// The start position of the chunk of data to replace
    start: u32,
    /// The end position of the chunk of data to replace (open end interval)
    end: u32,
    /// The data replacing the chunk
    data: &'a [u8],
}

impl Chunk<'_> {
    /// Adjusted start of the chunk to replace.
    ///
    /// The offset, taking into account the growth/shrinkage of data
    /// induced by previously applied chunks.
    fn start_offset_by(&self, offset: i32) -> u32 {
        let start = self.start as i32 + offset;
        assert!(start >= 0, "negative chunk start should never happen");
        start as u32
    }

    /// Adjusted end of the chunk to replace.
    ///
    /// The offset, taking into account the growth/shrinkage of data
    /// induced by previously applied chunks.
    fn end_offset_by(&self, offset: i32) -> u32 {
        self.start_offset_by(offset) + self.data.len() as u32
    }

    /// Length of the replaced chunk.
    fn replaced_len(&self) -> u32 {
        self.end - self.start
    }

    /// Length difference between the replacing data and the replaced data.
    fn len_diff(&self) -> i32 {
        self.data.len() as i32 - self.replaced_len() as i32
    }
}

/// The delta between two revisions data.
#[derive(Debug, Clone)]
pub struct PatchList<'a> {
    /// A collection of chunks to apply.
    ///
    /// Those chunks are:
    /// - ordered from the left-most replacement to the right-most replacement
    /// - non-overlapping, meaning that two chucks can not change the same
    ///   chunk of the patched data
    chunks: Vec<Chunk<'a>>,
}

impl<'a> PatchList<'a> {
    /// Create a `PatchList` from bytes.
    pub fn new(data: &'a [u8]) -> Self {
        let mut chunks = vec![];
        let mut data = data;
        while !data.is_empty() {
            let start = BigEndian::read_u32(&data[0..]);
            let end = BigEndian::read_u32(&data[4..]);
            let len = BigEndian::read_u32(&data[8..]);
            assert!(start <= end);
            chunks.push(Chunk {
                start,
                end,
                data: &data[12..12 + (len as usize)],
            });
            data = &data[12 + (len as usize)..];
        }
        PatchList { chunks }
    }

    /// Return the final length of data after patching
    /// given its initial length .
    fn size(&self, initial_size: i32) -> i32 {
        self.chunks
            .iter()
            .fold(initial_size, |acc, chunk| acc + chunk.len_diff())
    }

    /// Apply the patch to some data.
    pub fn apply(&self, initial: &[u8]) -> Vec<u8> {
        let mut last: usize = 0;
        let mut vec =
            Vec::with_capacity(self.size(initial.len() as i32) as usize);
        for Chunk { start, end, data } in self.chunks.iter() {
            vec.extend(&initial[last..(*start as usize)]);
            vec.extend(data.iter());
            last = *end as usize;
        }
        vec.extend(&initial[last..]);
        vec
    }

    /// Combine two patch lists into a single patch list.
    ///
    /// Applying consecutive patches can lead to waste of time and memory
    /// as the changes introduced by one patch can be overridden by the next.
    /// Combining patches optimizes the whole patching sequence.
    fn combine(&mut self, other: &mut Self) -> Self {
        let mut chunks = vec![];

        // Keep track of each growth/shrinkage resulting from applying a chunk
        // in order to adjust the start/end of subsequent chunks.
        let mut offset = 0i32;

        // Keep track of the chunk of self.chunks to process.
        let mut pos = 0;

        // For each chunk of `other`, chunks of `self` are processed
        // until they start after the end of the current chunk.
        for Chunk { start, end, data } in other.chunks.iter() {
            // Add chunks of `self` that start before this chunk of `other`
            // without overlap.
            while pos < self.chunks.len()
                && self.chunks[pos].end_offset_by(offset) <= *start
            {
                let first = self.chunks[pos].clone();
                offset += first.len_diff();
                chunks.push(first);
                pos += 1;
            }

            // The current chunk of `self` starts before this chunk of `other`
            // with overlap.
            // The left-most part of data is added as an insertion chunk.
            // The right-most part data is kept in the chunk.
            if pos < self.chunks.len()
                && self.chunks[pos].start_offset_by(offset) < *start
            {
                let first = &mut self.chunks[pos];

                let (data_left, data_right) = first.data.split_at(
                    (*start - first.start_offset_by(offset)) as usize,
                );
                let left = Chunk {
                    start: first.start,
                    end: first.start,
                    data: data_left,
                };

                first.data = data_right;

                offset += left.len_diff();

                chunks.push(left);

                // There is no index incrementation because the right-most part
                // needs further examination.
            }

            // At this point remaining chunks of `self` starts after
            // the current chunk of `other`.

            // `start_offset` will be used to adjust the start of the current
            // chunk of `other`.
            // Offset tracking continues with `end_offset` to adjust the end
            // of the current chunk of `other`.
            let mut next_offset = offset;

            // Discard the chunks of `self` that are totally overridden
            // by the current chunk of `other`
            while pos < self.chunks.len()
                && self.chunks[pos].end_offset_by(next_offset) <= *end
            {
                let first = &self.chunks[pos];
                next_offset += first.len_diff();
                pos += 1;
            }

            // Truncate the left-most part of chunk of `self` that overlaps
            // the current chunk of `other`.
            if pos < self.chunks.len()
                && self.chunks[pos].start_offset_by(next_offset) < *end
            {
                let first = &mut self.chunks[pos];

                let how_much_to_discard =
                    *end - first.start_offset_by(next_offset);

                first.data = &first.data[(how_much_to_discard as usize)..];

                next_offset += how_much_to_discard as i32;
            }

            // Add the chunk of `other` with adjusted position.
            chunks.push(Chunk {
                start: (*start as i32 - offset) as u32,
                end: (*end as i32 - next_offset) as u32,
                data,
            });

            // Go back to normal offset tracking for the next `o` chunk
            offset = next_offset;
        }

        // Add remaining chunks of `self`.
        for elt in &self.chunks[pos..] {
            chunks.push(elt.clone());
        }
        PatchList { chunks }
    }
}

/// Combine a list of patch list into a single patch optimized patch list.
pub fn fold_patch_lists<'a>(lists: &[PatchList<'a>]) -> PatchList<'a> {
    if lists.len() <= 1 {
        if lists.is_empty() {
            PatchList { chunks: vec![] }
        } else {
            lists[0].clone()
        }
    } else {
        let (left, right) = lists.split_at(lists.len() / 2);
        let mut left_res = fold_patch_lists(left);
        let mut right_res = fold_patch_lists(right);
        left_res.combine(&mut right_res)
    }
}

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

    struct PatchDataBuilder {
        data: Vec<u8>,
    }

    impl PatchDataBuilder {
        pub fn new() -> Self {
            Self { data: vec![] }
        }

        pub fn replace(
            &mut self,
            start: usize,
            end: usize,
            data: &[u8],
        ) -> &mut Self {
            assert!(start <= end);
            self.data.extend(&(start as i32).to_be_bytes());
            self.data.extend(&(end as i32).to_be_bytes());
            self.data.extend(&(data.len() as i32).to_be_bytes());
            self.data.extend(data.iter());
            self
        }

        pub fn get(&mut self) -> &[u8] {
            &self.data
        }
    }

    #[test]
    fn test_ends_before() {
        let data = vec![0u8, 0u8, 0u8];
        let mut patch1_data = PatchDataBuilder::new();
        patch1_data.replace(0, 1, &[1, 2]);
        let mut patch1 = PatchList::new(patch1_data.get());

        let mut patch2_data = PatchDataBuilder::new();
        patch2_data.replace(2, 4, &[3, 4]);
        let mut patch2 = PatchList::new(patch2_data.get());

        let patch = patch1.combine(&mut patch2);

        let result = patch.apply(&data);

        assert_eq!(result, vec![1u8, 2, 3, 4]);
    }

    #[test]
    fn test_starts_after() {
        let data = vec![0u8, 0u8, 0u8];
        let mut patch1_data = PatchDataBuilder::new();
        patch1_data.replace(2, 3, &[3]);
        let mut patch1 = PatchList::new(patch1_data.get());

        let mut patch2_data = PatchDataBuilder::new();
        patch2_data.replace(1, 2, &[1, 2]);
        let mut patch2 = PatchList::new(patch2_data.get());

        let patch = patch1.combine(&mut patch2);

        let result = patch.apply(&data);

        assert_eq!(result, vec![0u8, 1, 2, 3]);
    }

    #[test]
    fn test_overridden() {
        let data = vec![0u8, 0, 0];
        let mut patch1_data = PatchDataBuilder::new();
        patch1_data.replace(1, 2, &[3, 4]);
        let mut patch1 = PatchList::new(patch1_data.get());

        let mut patch2_data = PatchDataBuilder::new();
        patch2_data.replace(1, 4, &[1, 2, 3]);
        let mut patch2 = PatchList::new(patch2_data.get());

        let patch = patch1.combine(&mut patch2);

        let result = patch.apply(&data);

        assert_eq!(result, vec![0u8, 1, 2, 3]);
    }

    #[test]
    fn test_right_most_part_is_overridden() {
        let data = vec![0u8, 0, 0];
        let mut patch1_data = PatchDataBuilder::new();
        patch1_data.replace(0, 1, &[1, 3]);
        let mut patch1 = PatchList::new(patch1_data.get());

        let mut patch2_data = PatchDataBuilder::new();
        patch2_data.replace(1, 4, &[2, 3, 4]);
        let mut patch2 = PatchList::new(patch2_data.get());

        let patch = patch1.combine(&mut patch2);

        let result = patch.apply(&data);

        assert_eq!(result, vec![1u8, 2, 3, 4]);
    }

    #[test]
    fn test_left_most_part_is_overridden() {
        let data = vec![0u8, 0, 0];
        let mut patch1_data = PatchDataBuilder::new();
        patch1_data.replace(1, 3, &[1, 3, 4]);
        let mut patch1 = PatchList::new(patch1_data.get());

        let mut patch2_data = PatchDataBuilder::new();
        patch2_data.replace(0, 2, &[1, 2]);
        let mut patch2 = PatchList::new(patch2_data.get());

        let patch = patch1.combine(&mut patch2);

        let result = patch.apply(&data);

        assert_eq!(result, vec![1u8, 2, 3, 4]);
    }

    #[test]
    fn test_mid_is_overridden() {
        let data = vec![0u8, 0, 0];
        let mut patch1_data = PatchDataBuilder::new();
        patch1_data.replace(0, 3, &[1, 3, 3, 4]);
        let mut patch1 = PatchList::new(patch1_data.get());

        let mut patch2_data = PatchDataBuilder::new();
        patch2_data.replace(1, 3, &[2, 3]);
        let mut patch2 = PatchList::new(patch2_data.get());

        let patch = patch1.combine(&mut patch2);

        let result = patch.apply(&data);

        assert_eq!(result, vec![1u8, 2, 3, 4]);
    }
}