view rust/hg-core/src/revlog/patch.rs @ 51725:bbe59cc5d2e1

rust-changelog: accessing the index

The `Index` object is currently the one providing all DAG related
algorithms, starting with simple ancestors iteration up to more
advanced ones (ranges, common ancestors…).

From pure Rust code, there was no way to access the changelog index for
a given `Repository`, probably because `rhg` does not use any such algorithm
yet.

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]);
    }
}