yuurei/src/delta.rs

//! 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);
    }
}