You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
258 lines
6.5 KiB
258 lines
6.5 KiB
//! Deltas and applying them
|
|
use super::*;
|
|
use difference::{
|
|
Changeset,
|
|
Difference,
|
|
};
|
|
|
|
const MAX_SINGLE_DELTA_SIZE: usize = 14;
|
|
const DELTA_BREAK: &str = "";
|
|
|
|
/// Infer all deltas needed to be sequentially applied to `orig` to transform it to `new`, return the number inserted into `output`.
|
|
pub fn infer_deltas<T: BackInserter<Delta> + ?Sized>(output: &mut T, orig: &str, new: &str) -> usize
|
|
{
|
|
let set = Changeset::new(orig, new, DELTA_BREAK);
|
|
|
|
let mut done=0;
|
|
let mut position =0;
|
|
for diff in set.diffs.into_iter() {
|
|
match diff {
|
|
Difference::Same(string) => {
|
|
position += string.len();
|
|
},
|
|
Difference::Rem(string) => {
|
|
output.push_back(Delta {
|
|
location: position,
|
|
kind: DeltaKind::RemoveAhead{span_len: string.len()},
|
|
});
|
|
done+=1;
|
|
},
|
|
Difference::Add(string) => {
|
|
let mut passer = BackInsertPass::new(|(span, span_len)| {
|
|
output.push_back(Delta {
|
|
location: position,
|
|
kind: DeltaKind::Insert {
|
|
span, span_len,
|
|
},
|
|
});
|
|
position+= usize::from(span_len);
|
|
done+=1;
|
|
});
|
|
delta_span_many(&mut passer, string.chars());
|
|
},
|
|
}
|
|
}
|
|
done
|
|
}
|
|
|
|
/// Create a delta span from an input iterator.
|
|
///
|
|
/// This function can take no more than `min(255, MAX_SINGLE_DELTA_SIZE)` chars from the input. The number of chars inserted is also returned as `u8`.
|
|
pub(super) fn delta_span<I>(from: I) -> ([char; MAX_SINGLE_DELTA_SIZE], u8)
|
|
where I: IntoIterator<Item = char>
|
|
{
|
|
let mut output: [char; MAX_SINGLE_DELTA_SIZE] = Default::default();
|
|
let mut sz: u8 = 0;
|
|
|
|
for (d, s) in output.iter_mut().zip(from.into_iter().take(usize::from(u8::MAX)))
|
|
{
|
|
*d = s;
|
|
sz += 1;
|
|
}
|
|
|
|
(output, sz)
|
|
}
|
|
|
|
/// Create as many delta spans needed from an input iterator.
|
|
///
|
|
/// This function can take as many inputs as needed, and outputs the needed amount of spans into `into`, and then returns the number added.
|
|
pub(super) fn delta_span_many<T: BackInserter<([char; MAX_SINGLE_DELTA_SIZE], u8)> + ?Sized, I>(into: &mut T, from: I) -> usize
|
|
where I: IntoIterator<Item = char>
|
|
{
|
|
let mut iter = from.into_iter();
|
|
let mut added=0;
|
|
loop {
|
|
match delta_span(&mut iter) {
|
|
(_, 0) => break,
|
|
other => into.push_back(other),
|
|
}
|
|
added+=1;
|
|
}
|
|
added
|
|
}
|
|
|
|
/// Information about the delta to be applied in `Delta`.
|
|
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Hash)]
|
|
pub enum DeltaKind
|
|
{
|
|
/// Append to the end of body. Equivilant to `Insert` with a location at `karada.scape.len()` (the end of the buffer).
|
|
Append{
|
|
span: [char; MAX_SINGLE_DELTA_SIZE],
|
|
span_len: u8,
|
|
},
|
|
/// Insert `span_len` chars from `span` into body starting *at* `location` and moving ahead
|
|
Insert{
|
|
span: [char; MAX_SINGLE_DELTA_SIZE],
|
|
span_len: u8,
|
|
},
|
|
/// Remove `span_len` chars from `location`.
|
|
RemoveAhead{
|
|
span_len: usize,
|
|
},
|
|
/// Remove `span_len` chars up to but not including `location`.
|
|
RemoveBehind{
|
|
span_len: usize,
|
|
},
|
|
/// Remove everything from `location` to the end.
|
|
Truncate,
|
|
/// Remove everything from 0 to `location`.
|
|
Shift,
|
|
/// Remove char at `location`
|
|
RemoveSingle,
|
|
/// Remove entire post body
|
|
Clear,
|
|
}
|
|
|
|
/// A delta to apply to `Karada`.
|
|
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, Hash)]
|
|
pub struct Delta
|
|
{
|
|
/// Location to insert into. This is the INclusive range of: 0..=(karada.scape.len()).
|
|
///
|
|
/// Insertions off the end of the buffer are to be appened instead.
|
|
location: usize,
|
|
/// The kind of delta to insert
|
|
kind: DeltaKind,
|
|
}
|
|
|
|
/// Static assertion: `MAX_SINGLE_DELTA_SIZE` can fit into `u8`.
|
|
const _: [u8;(MAX_SINGLE_DELTA_SIZE < (!0u8 as usize)) as usize] = [0];
|
|
|
|
impl Delta
|
|
{
|
|
/// Apply this delta to a message
|
|
pub fn insert<T: ?Sized+AsMut<Vec<char>>>(&self, inserter: &mut T)
|
|
{
|
|
let inserter = inserter.as_mut();
|
|
match self.kind {
|
|
DeltaKind::Append{span, span_len} => {
|
|
inserter.extend_from_slice(&span[..usize::from(span_len)]);
|
|
},
|
|
DeltaKind::Insert{span, span_len} => {
|
|
let span = &span[..usize::from(span_len)];
|
|
if self.location == inserter.len() {
|
|
inserter.extend_from_slice(span);
|
|
} else if span.len() == 1 {
|
|
inserter.insert(self.location, span[0]);
|
|
} else if span.len() > 1 {
|
|
inserter.insert_exact(self.location, span.iter().copied());
|
|
}
|
|
},
|
|
DeltaKind::RemoveAhead{span_len} => {
|
|
inserter.drain(self.location..(self.location+span_len));
|
|
},
|
|
DeltaKind::RemoveBehind{span_len} => {
|
|
let span_st = self.location.checked_sub(span_len).unwrap_or(0);
|
|
inserter.drain(span_st..self.location);
|
|
},
|
|
DeltaKind::RemoveSingle => {
|
|
inserter.remove(self.location);
|
|
},
|
|
DeltaKind::Clear => inserter.clear(),
|
|
DeltaKind::Truncate => inserter.truncate(self.location),
|
|
DeltaKind::Shift => drop(inserter.drain(..self.location)),
|
|
}
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests
|
|
{
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn infer_and_insert()
|
|
{
|
|
let orig = "the quick brown fox jumped over the lazy dog !!!!";
|
|
let new = "the quick brown dog jumped over the lazy fox twice";
|
|
|
|
let mut deltas = Vec::new();
|
|
infer_deltas(&mut deltas, orig, new);
|
|
|
|
println!("{:#?}", deltas);
|
|
let output: String = {
|
|
let mut scape: Vec<_> = orig.chars().collect();
|
|
for delta in deltas.into_iter() {
|
|
delta.insert(&mut scape);
|
|
}
|
|
scape.into_iter().collect()
|
|
};
|
|
|
|
assert_eq!(&output[..], &new[..]);
|
|
}
|
|
|
|
macro_rules! insert {
|
|
($expects:literal; $start:literal, $ins:literal, $where:expr) => {
|
|
{
|
|
|
|
let mut message: Vec<char> = $start.chars().collect();
|
|
|
|
let delta = {
|
|
let (span, span_len) = delta_span($ins.chars());
|
|
Delta {
|
|
location: $where,
|
|
kind: DeltaKind::Insert{span, span_len},
|
|
}
|
|
};
|
|
|
|
println!("from: {:?}", message);
|
|
println!("delta: {:?}", delta);
|
|
delta.insert(&mut message);
|
|
|
|
assert_eq!(&message.into_iter().collect::<String>()[..], $expects);
|
|
}
|
|
};
|
|
}
|
|
|
|
#[test]
|
|
fn insert_body()
|
|
{
|
|
insert!("123456789"; "126789", "345", 2);
|
|
}
|
|
#[test]
|
|
fn insert_end()
|
|
{
|
|
insert!("123456789"; "1289", "34567", 2);
|
|
}
|
|
#[test]
|
|
fn insert_end_rev()
|
|
{
|
|
insert!("123456789"; "1234569", "78", 6);
|
|
}
|
|
#[test]
|
|
fn insert_begin_rev()
|
|
{
|
|
insert!("123456789"; "1456789", "23", 1);
|
|
}
|
|
#[test]
|
|
fn insert_begin()
|
|
{
|
|
insert!("123456789"; "789", "123456", 0);
|
|
}
|
|
#[test]
|
|
fn insert_end_f()
|
|
{
|
|
insert!("123456789"; "123", "456789", 3);
|
|
}
|
|
#[test]
|
|
fn insert_end_f_rev()
|
|
{
|
|
insert!("123456789"; "1234567", "89", 7);
|
|
}
|
|
#[test]
|
|
fn insert_single()
|
|
{
|
|
insert!("123456789"; "12346789", "5",4);
|
|
}
|
|
}
|