From 4f954112b8c8cf266a8338cc86166f912c2da88c Mon Sep 17 00:00:00 2001 From: Mel Date: Tue, 21 Sep 2021 22:43:20 +0200 Subject: Byte differ --- src/actions/shift.rs | 4 +- src/actions/update.rs | 14 +++--- src/diff.rs | 127 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/history.rs | 10 ++-- src/lib.rs | 2 +- src/text_diff.rs | 52 --------------------- 6 files changed, 142 insertions(+), 67 deletions(-) create mode 100644 src/diff.rs delete mode 100644 src/text_diff.rs (limited to 'src') diff --git a/src/actions/shift.rs b/src/actions/shift.rs index 437fcb4..6880c20 100644 --- a/src/actions/shift.rs +++ b/src/actions/shift.rs @@ -32,7 +32,7 @@ pub fn shift(command_options: ActionOptions, path: &str, new_cursor: usize) -> R working_file.rewind()?; working_file.set_len(0)?; - working_file.write_all(new_content.as_bytes())?; + working_file.write_all(&new_content)?; } file_history.write_to_file(&mut history_file)?; @@ -47,7 +47,7 @@ pub fn shift(command_options: ActionOptions, path: &str, new_cursor: usize) -> R let mut new_working_file = deleted.create_working_file(&locations)?; let new_content = file_history.get_content(); - new_working_file.write_all(new_content.as_bytes())?; + new_working_file.write_all(&new_content)?; } } FileState::Untracked(_) => panic!("File is not tracked with Ka."), diff --git a/src/actions/update.rs b/src/actions/update.rs index 73a9222..aa9c3a4 100644 --- a/src/actions/update.rs +++ b/src/actions/update.rs @@ -5,7 +5,7 @@ use anyhow::{Context, Result}; use crate::{ files::{Locations, FileState}, history::{FileChange, FileHistory}, - text_diff::TextChange, + diff::ContentChange, }; use super::ActionOptions; @@ -40,10 +40,10 @@ fn update_file(file_state: FileState, locations: &Locations) -> Result<()> { FileState::Untracked(untracked) => { let mut file = untracked.load_file()?; - let mut file_content = String::new(); - file.read_to_string(&mut file_content)?; + let mut file_content = Vec::new(); + file.read_to_end(&mut file_content)?; - let change = FileChange::Updated(vec![TextChange::Inserted { + let change = FileChange::Updated(vec![ContentChange::Inserted { at: 0, new_content: file_content, }]); @@ -59,12 +59,12 @@ fn update_file(file_state: FileState, locations: &Locations) -> Result<()> { let file_history = FileHistory::from_file(&mut history_file)?; - let mut new_content = String::new(); - working_file.read_to_string(&mut new_content)?; + let mut new_content = Vec::new(); + working_file.read_to_end(&mut new_content)?; let old_content = file_history.get_content(); - let changes = TextChange::diff(&old_content, &new_content); + let changes = ContentChange::diff(&old_content, &new_content); let mut new_history = file_history; new_history.add_change(FileChange::Updated(changes)); diff --git a/src/diff.rs b/src/diff.rs new file mode 100644 index 0000000..4e3531c --- /dev/null +++ b/src/diff.rs @@ -0,0 +1,127 @@ +use std::time::{Duration, Instant}; + +use serde::{Deserialize, Serialize}; +use similar::{Algorithm, DiffOp}; + +#[derive(Serialize, Deserialize, Debug, PartialEq, Eq)] +pub enum ContentChange { + Inserted { at: usize, new_content: Vec }, + Deleted { at: usize, upto: usize }, +} + +impl ContentChange { + pub fn diff(old: &[u8], new: &[u8]) -> Vec { + let deadline = Instant::now() + Duration::from_millis(100); + let change_set = + similar::capture_diff_slices_deadline(Algorithm::Myers, old, new, Some(deadline)); + + let mut at = 0; + let mut changes = Vec::new(); + + for diff in change_set { + match diff { + DiffOp::Delete { old_len, .. } => { + changes.push(ContentChange::Deleted { + at, + upto: at + old_len, + }); + } + DiffOp::Insert { + new_index, new_len, .. + } => { + let new_content = &new[new_index..new_index + new_len]; + let change = ContentChange::Inserted { + at, + new_content: new_content.to_vec(), + }; + at += new_len; + changes.push(change); + } + DiffOp::Replace { + old_len, + new_index, + new_len, + .. + } => { + let new_content = &new[new_index..new_index + new_len]; + + let removed_change = ContentChange::Deleted { + at, + upto: at + old_len, + }; + let added_change = ContentChange::Inserted { + at, + new_content: new_content.to_vec(), + }; + + changes.push(removed_change); + changes.push(added_change); + + at += new_len; + } + DiffOp::Equal { len, .. } => { + at += len; + } + } + } + + changes + } + + pub fn apply(&self, buffer: &mut Vec) { + match self { + ContentChange::Deleted { at, upto } => { + buffer.drain(at..upto); + } + ContentChange::Inserted { at, new_content } => { + buffer.splice(at..at, new_content.clone()); + } + } + } +} + +#[cfg(test)] +mod tests { + use super::{ContentChange::*, *}; + + #[test] + fn test_diff() { + let old = "This is an old string..."; + let new = "This is a new string...!"; + + let changes = ContentChange::diff(old.as_bytes(), new.as_bytes()); + assert_eq!( + changes.as_slice(), + [ + Inserted { + at: 9, + new_content: " ".into() + }, + Deleted { at: 11, upto: 15 }, + Inserted { + at: 11, + new_content: "ew".into() + }, + Inserted { + at: 23, + new_content: "!".into() + } + ], + ); + } + + #[test] + fn test_apply() { + let old = "This is an old string..."; + let new = "This is a new text...!"; + + let changes = ContentChange::diff(old.as_bytes(), new.as_bytes()); + + let mut buffer = old.as_bytes().to_vec(); + for change in changes { + change.apply(&mut buffer); + } + + assert_eq!(&buffer, new.as_bytes()); + } +} diff --git a/src/history.rs b/src/history.rs index 13b2838..a032eaa 100644 --- a/src/history.rs +++ b/src/history.rs @@ -7,7 +7,7 @@ use serde::{Deserialize, Serialize}; use anyhow::{Context, Result}; -use crate::text_diff::TextChange; +use crate::diff::ContentChange; #[derive(Serialize, Deserialize, Debug)] pub struct FileHistory { @@ -39,15 +39,15 @@ impl FileHistory { } } - pub fn get_content(&self) -> String { - let mut buffer = String::new(); + pub fn get_content(&self) -> Vec { + let mut buffer = Vec::new(); for file_change in self.changes.iter().take(self.cursor) { if let FileChange::Updated(ref updated) = file_change { for change in updated.iter() { change.apply(&mut buffer) } } else { - buffer = String::new(); + buffer.drain(0..); } } buffer @@ -89,6 +89,6 @@ impl Default for FileHistory { #[derive(Serialize, Deserialize, Debug)] pub enum FileChange { - Updated(Vec), + Updated(Vec), Deleted, } diff --git a/src/lib.rs b/src/lib.rs index 467ffe7..152219e 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,5 +1,5 @@ pub mod actions; mod history; -mod text_diff; +mod diff; mod files; diff --git a/src/text_diff.rs b/src/text_diff.rs deleted file mode 100644 index bab8799..0000000 --- a/src/text_diff.rs +++ /dev/null @@ -1,52 +0,0 @@ -use difference::{Changeset, Difference}; -use serde::{Deserialize, Serialize}; - -#[derive(Serialize, Deserialize, Debug)] -pub enum TextChange { - Inserted { at: usize, new_content: String }, - Deleted { at: usize, upto: usize }, -} - -impl TextChange { - pub fn diff(old: &str, new: &str) -> Vec { - let change_set = Changeset::new(old, new, ""); - - let mut changes = Vec::new(); - let mut at: usize = 0; - - for diff in change_set.diffs.iter() { - match diff { - Difference::Add(new_content) => { - let change = TextChange::Inserted { - at, - new_content: new_content.to_owned(), - }; - at += new_content.len(); - changes.push(change); - } - Difference::Rem(removed_content) => { - changes.push(TextChange::Deleted { - at, - upto: removed_content.len(), - }); - } - Difference::Same(same_content) => { - at += same_content.len(); - } - } - } - - changes - } - - pub fn apply(&self, buffer: &mut String) { - match self { - TextChange::Deleted { at, upto } => { - buffer.replace_range(at..upto, ""); - } - TextChange::Inserted { at, new_content } => { - buffer.insert_str(*at, new_content); - } - } - } -} -- cgit 1.4.1