Byte differ

8 files changed, 150 insertions, 75 deletions

diff --git a/Cargo.lock b/Cargo.lock
index b22eca6..e51a480 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -9,12 +9,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "61604a8f862e1d5c3229fdd78f8b02c68dcf73a4c4b05fd636d12240aaa242c1"
 
 [[package]]
-name = "difference"
-version = "2.0.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "524cbf6897b527295dff137cec09ecf3a05f4fddffd7dfcd1585403449e74198"
-
-[[package]]
 name = "itoa"
 version = "0.4.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -25,9 +19,9 @@ name = "ka"
 version = "0.1.0"
 dependencies = [
  "anyhow",
- "difference",
  "serde",
  "serde_json",
+ "similar",
 ]
 
 [[package]]
@@ -93,6 +87,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "similar"
+version = "2.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6bf11003835e462f07851028082d2a1c89d956180ce4b4b50e07fb085ec4131a"
+
+[[package]]
 name = "syn"
 version = "1.0.76"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 7605ee0..9d715e6 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,7 +8,7 @@ edition = "2018"
 [dependencies]
 serde = {version = "1.0", features = ["derive"] }
 serde_json = "1.0"
-difference = "2.0.0"
+similar = "2.0.0"
 anyhow = "1.0"
 
 [workspace]
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<u8> },
+    Deleted { at: usize, upto: usize },
+}
+
+impl ContentChange {
+    pub fn diff(old: &[u8], new: &[u8]) -> Vec<Self> {
+        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<u8>) {
+        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<u8> {
+        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<TextChange>),
+    Updated(Vec<ContentChange>),
     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<Self> {
-        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);
-            }
-        }
-    }
-}