| Alphare |
| hg-reviewers |
| Automatic diff as part of commit; lint not applicable. |
| Automatic diff as part of commit; unit tests not applicable. |
| use byteorder::{BigEndian, ByteOrder}; | use byteorder::{BigEndian, ByteOrder}; | ||||
| /// A chunk of data to insert, delete or replace in a patch | /// A chunk of data to insert, delete or replace in a patch | ||||
| /// | /// | ||||
| /// A chunk is: | /// A chunk is: | ||||
| /// - an insertion when `!data.is_empty() && start == end` | /// - an insertion when `!data.is_empty() && start == end` | ||||
| /// - an deletion when `data.is_empty() && start < end` | /// - an deletion when `data.is_empty() && start < end` | ||||
| /// - a replacement when `!data.is_empty() && start < end` | /// - a replacement when `!data.is_empty() && start < end` | ||||
| /// - not doing anything when `data.is_empty() && start == end` | /// - not doing anything when `data.is_empty() && start == end` | ||||
| #[derive(Debug, Clone)] | #[derive(Debug, Clone)] | ||||
| struct PatchFrag<'a> { | struct Chunk<'a> { | ||||
| /// The start position of the chunk of data to replace | /// The start position of the chunk of data to replace | ||||
| start: i32, | start: i32, | ||||
| /// The end position of the chunk of data to replace (open end interval) | /// The end position of the chunk of data to replace (open end interval) | ||||
| end: i32, | end: i32, | ||||
| /// The data replacing the chunk | /// The data replacing the chunk | ||||
| data: &'a [u8], | data: &'a [u8], | ||||
| } | } | ||||
| impl<'a> PatchFrag<'a> { | impl<'a> Chunk<'a> { | ||||
| /// Adjusted start of the chunk to replace. | /// Adjusted start of the chunk to replace. | ||||
| /// | /// | ||||
| /// Offset allow to take into account the growth/shrinkage of data | /// Offset allow to take into account the growth/shrinkage of data | ||||
| /// induced by previously applied chunks. | /// induced by previously applied chunks. | ||||
| fn start_offseted_by(&self, offset: i32) -> i32 { | fn start_offseted_by(&self, offset: i32) -> i32 { | ||||
| self.start + offset | self.start + offset | ||||
| } | } | ||||
| #[derive(Debug, Clone)] | #[derive(Debug, Clone)] | ||||
| pub struct PatchList<'a> { | pub struct PatchList<'a> { | ||||
| /// A collection of chunks to apply. | /// A collection of chunks to apply. | ||||
| /// | /// | ||||
| /// Those chunks are: | /// Those chunks are: | ||||
| /// - ordered from the left-most replacement to the right-most replacement | /// - ordered from the left-most replacement to the right-most replacement | ||||
| /// - non-overlapping, meaning that two chucks can not change the same | /// - non-overlapping, meaning that two chucks can not change the same | ||||
| /// chunk of the patched data | /// chunk of the patched data | ||||
| frags: Vec<PatchFrag<'a>>, | chunks: Vec<Chunk<'a>>, | ||||
| } | } | ||||
| impl<'a> PatchList<'a> { | impl<'a> PatchList<'a> { | ||||
| /// Create a `PatchList` from bytes. | /// Create a `PatchList` from bytes. | ||||
| pub fn new(data: &'a [u8]) -> Self { | pub fn new(data: &'a [u8]) -> Self { | ||||
| let mut frags = vec![]; | let mut chunks = vec![]; | ||||
| let mut data = data; | let mut data = data; | ||||
| while !data.is_empty() { | while !data.is_empty() { | ||||
| let start = BigEndian::read_i32(&data[0..]); | let start = BigEndian::read_i32(&data[0..]); | ||||
| let end = BigEndian::read_i32(&data[4..]); | let end = BigEndian::read_i32(&data[4..]); | ||||
| let len = BigEndian::read_i32(&data[8..]); | let len = BigEndian::read_i32(&data[8..]); | ||||
| assert!(0 <= start && start <= end && len >= 0); | assert!(0 <= start && start <= end && len >= 0); | ||||
| frags.push(PatchFrag { | chunks.push(Chunk { | ||||
| start, | start, | ||||
| end, | end, | ||||
| data: &data[12..12 + (len as usize)], | data: &data[12..12 + (len as usize)], | ||||
| }); | }); | ||||
| data = &data[12 + (len as usize)..]; | data = &data[12 + (len as usize)..]; | ||||
| } | } | ||||
| PatchList { frags } | PatchList { chunks } | ||||
| } | } | ||||
| /// Return the final length of data after patching | /// Return the final length of data after patching | ||||
| /// given its initial length . | /// given its initial length . | ||||
| fn size(&self, initial_size: i32) -> i32 { | fn size(&self, initial_size: i32) -> i32 { | ||||
| self.frags | self.chunks | ||||
| .iter() | .iter() | ||||
| .fold(initial_size, |acc, frag| acc + frag.len_diff()) | .fold(initial_size, |acc, chunk| acc + chunk.len_diff()) | ||||
| } | } | ||||
| /// Apply the patch to some data. | /// Apply the patch to some data. | ||||
| pub fn apply(&self, initial: &[u8]) -> Vec<u8> { | pub fn apply(&self, initial: &[u8]) -> Vec<u8> { | ||||
| let mut last: usize = 0; | let mut last: usize = 0; | ||||
| let mut vec = | let mut vec = | ||||
| Vec::with_capacity(self.size(initial.len() as i32) as usize); | Vec::with_capacity(self.size(initial.len() as i32) as usize); | ||||
| for PatchFrag { start, end, data } in self.frags.iter() { | for Chunk { start, end, data } in self.chunks.iter() { | ||||
| vec.extend(&initial[last..(*start as usize)]); | vec.extend(&initial[last..(*start as usize)]); | ||||
| vec.extend(data.iter()); | vec.extend(data.iter()); | ||||
| last = *end as usize; | last = *end as usize; | ||||
| } | } | ||||
| vec.extend(&initial[last..]); | vec.extend(&initial[last..]); | ||||
| vec | vec | ||||
| } | } | ||||
| /// Combine two patch lists into a single patch list. | /// Combine two patch lists into a single patch list. | ||||
| /// | /// | ||||
| /// Applying consecutive patches can lead to waste of time and memory | /// Applying consecutive patches can lead to waste of time and memory | ||||
| /// as the changes introduced by one patch can be overridden by the next. | /// as the changes introduced by one patch can be overridden by the next. | ||||
| /// Combining patches optimizes the whole patching sequence. | /// Combining patches optimizes the whole patching sequence. | ||||
| fn combine(&mut self, other: &mut Self) -> Self { | fn combine(&mut self, other: &mut Self) -> Self { | ||||
| let mut frags = vec![]; | let mut chunks = vec![]; | ||||
| // Keep track of each growth/shrinkage resulting from applying a chunk | // Keep track of each growth/shrinkage resulting from applying a chunk | ||||
| // in order to adjust the start/end of subsequent chunks. | // in order to adjust the start/end of subsequent chunks. | ||||
| let mut offset = 0i32; | let mut offset = 0i32; | ||||
| // Keep track of the chunk of self.chunks to process. | // Keep track of the chunk of self.chunks to process. | ||||
| let mut pos = 0; | let mut pos = 0; | ||||
| // For each chunk of `other`, chunks of `self` are processed | // For each chunk of `other`, chunks of `self` are processed | ||||
| // until they start after the end of the current chunk. | // until they start after the end of the current chunk. | ||||
| for PatchFrag { start, end, data } in other.frags.iter() { | for Chunk { start, end, data } in other.chunks.iter() { | ||||
| // Add chunks of `self` that start before this chunk of `other` | // Add chunks of `self` that start before this chunk of `other` | ||||
| // without overlap. | // without overlap. | ||||
| while pos < self.frags.len() | while pos < self.chunks.len() | ||||
| && self.frags[pos].end_offseted_by(offset) <= *start | && self.chunks[pos].end_offseted_by(offset) <= *start | ||||
| { | { | ||||
| let first = self.frags[pos].clone(); | let first = self.chunks[pos].clone(); | ||||
| offset += first.len_diff(); | offset += first.len_diff(); | ||||
| frags.push(first); | chunks.push(first); | ||||
| pos += 1; | pos += 1; | ||||
| } | } | ||||
| // The current chunk of `self` starts before this chunk of `other` | // The current chunk of `self` starts before this chunk of `other` | ||||
| // with overlap. | // with overlap. | ||||
| // The left-most part of data is added as an insertion chunk. | // The left-most part of data is added as an insertion chunk. | ||||
| // The right-most part data is kept in the chunk. | // The right-most part data is kept in the chunk. | ||||
| if pos < self.frags.len() | if pos < self.chunks.len() | ||||
| && self.frags[pos].start_offseted_by(offset) < *start | && self.chunks[pos].start_offseted_by(offset) < *start | ||||
| { | { | ||||
| let first = &mut self.frags[pos]; | let first = &mut self.chunks[pos]; | ||||
| let (data_left, data_right) = first.data.split_at( | let (data_left, data_right) = first.data.split_at( | ||||
| (*start - first.start_offseted_by(offset)) as usize, | (*start - first.start_offseted_by(offset)) as usize, | ||||
| ); | ); | ||||
| let left = PatchFrag { | let left = Chunk { | ||||
| start: first.start, | start: first.start, | ||||
| end: first.start, | end: first.start, | ||||
| data: data_left, | data: data_left, | ||||
| }; | }; | ||||
| first.data = data_right; | first.data = data_right; | ||||
| offset += left.len_diff(); | offset += left.len_diff(); | ||||
| frags.push(left); | chunks.push(left); | ||||
| // There is no index incrementation because the right-most part | // There is no index incrementation because the right-most part | ||||
| // needs further examination. | // needs further examination. | ||||
| } | } | ||||
| // At this point remaining chunks of `self` starts after | // At this point remaining chunks of `self` starts after | ||||
| // the current chunk of `other`. | // the current chunk of `other`. | ||||
| // `start_offset` will be used to adjust the start of the current | // `start_offset` will be used to adjust the start of the current | ||||
| // chunk of `other`. | // chunk of `other`. | ||||
| // Offset tracking continues with `end_offset` to adjust the end | // Offset tracking continues with `end_offset` to adjust the end | ||||
| // of the current chunk of `other`. | // of the current chunk of `other`. | ||||
| let mut next_offset = offset; | let mut next_offset = offset; | ||||
| // Discard the chunks of `self` that are totally overridden | // Discard the chunks of `self` that are totally overridden | ||||
| // by the current chunk of `other` | // by the current chunk of `other` | ||||
| while pos < self.frags.len() | while pos < self.chunks.len() | ||||
| && self.frags[pos].end_offseted_by(next_offset) <= *end | && self.chunks[pos].end_offseted_by(next_offset) <= *end | ||||
| { | { | ||||
| let first = &self.frags[pos]; | let first = &self.chunks[pos]; | ||||
| next_offset += first.len_diff(); | next_offset += first.len_diff(); | ||||
| pos += 1; | pos += 1; | ||||
| } | } | ||||
| // Truncate the left-most part of chunk of `self` that overlaps | // Truncate the left-most part of chunk of `self` that overlaps | ||||
| // the current chunk of `other`. | // the current chunk of `other`. | ||||
| if pos < self.frags.len() | if pos < self.chunks.len() | ||||
| && self.frags[pos].start_offseted_by(next_offset) < *end | && self.chunks[pos].start_offseted_by(next_offset) < *end | ||||
| { | { | ||||
| let first = &mut self.frags[pos]; | let first = &mut self.chunks[pos]; | ||||
| let how_much_to_discard = | let how_much_to_discard = | ||||
| *end - first.start_offseted_by(next_offset); | *end - first.start_offseted_by(next_offset); | ||||
| first.data = &first.data[(how_much_to_discard as usize)..]; | first.data = &first.data[(how_much_to_discard as usize)..]; | ||||
| next_offset += how_much_to_discard; | next_offset += how_much_to_discard; | ||||
| } | } | ||||
| // Add the chunk of `other` with adjusted position. | // Add the chunk of `other` with adjusted position. | ||||
| frags.push(PatchFrag { | chunks.push(Chunk { | ||||
| start: *start - offset, | start: *start - offset, | ||||
| end: *end - next_offset, | end: *end - next_offset, | ||||
| data, | data, | ||||
| }); | }); | ||||
| // Go back to normal offset tracking for the next `o` chunk | // Go back to normal offset tracking for the next `o` chunk | ||||
| offset = next_offset; | offset = next_offset; | ||||
| } | } | ||||
| // Add remaining chunks of `self`. | // Add remaining chunks of `self`. | ||||
| for elt in &self.frags[pos..] { | for elt in &self.chunks[pos..] { | ||||
| frags.push(elt.clone()); | chunks.push(elt.clone()); | ||||
| } | } | ||||
| PatchList { frags } | PatchList { chunks } | ||||
| } | } | ||||
| } | } | ||||
| /// Combine a list of patch list into a single patch optimized patch list. | /// Combine a list of patch list into a single patch optimized patch list. | ||||
| pub fn fold_patch_lists<'a>(lists: &[PatchList<'a>]) -> PatchList<'a> { | pub fn fold_patch_lists<'a>(lists: &[PatchList<'a>]) -> PatchList<'a> { | ||||
| if lists.len() <= 1 { | if lists.len() <= 1 { | ||||
| if lists.is_empty() { | if lists.is_empty() { | ||||
| PatchList { frags: vec![] } | PatchList { chunks: vec![] } | ||||
| } else { | } else { | ||||
| lists[0].clone() | lists[0].clone() | ||||
| } | } | ||||
| } else { | } else { | ||||
| let (left, right) = lists.split_at(lists.len() / 2); | let (left, right) = lists.split_at(lists.len() / 2); | ||||
| let mut left_res = fold_patch_lists(left); | let mut left_res = fold_patch_lists(left); | ||||
| let mut right_res = fold_patch_lists(right); | let mut right_res = fold_patch_lists(right); | ||||
| left_res.combine(&mut right_res) | left_res.combine(&mut right_res) | ||||