diff options
| -rw-r--r-- | Cargo.lock | 44 | ||||
| -rw-r--r-- | helix-core/Cargo.toml | 4 | ||||
| -rw-r--r-- | helix-core/src/lib.rs | 2 | ||||
| -rw-r--r-- | helix-core/src/selection.rs | 16 | ||||
| -rw-r--r-- | helix-core/src/transaction.rs | 286 |
5 files changed, 330 insertions, 22 deletions
@@ -173,6 +173,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1" [[package]] +name = "futf" +version = "0.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7c9c1ce3fa9336301af935ab852c437817d14cd33690446569392e65170aac3b" +dependencies = [ + "mac", + "new_debug_unreachable", +] + +[[package]] name = "getrandom" version = "0.1.14" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -199,6 +209,7 @@ dependencies = [ "anyhow", "ropey", "smallvec 1.4.0", + "tendril", ] [[package]] @@ -233,6 +244,12 @@ dependencies = [ ] [[package]] +name = "mac" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c41e0c4fef86961ac6d6f8a82609f55f31b05e4fce149ac5710e439df7619ba4" + +[[package]] name = "maybe-uninit" version = "2.0.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -251,6 +268,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "a64a92489e2744ce060c349162be1c5f33c6969234104dbd99ddb5feb08b8c15" [[package]] +name = "new_debug_unreachable" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e4a24736216ec316047a1fc4252e27dabb04218aa4a3f37c6e7ddbf1f9782b54" + +[[package]] name = "nom" version = "5.1.1" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -458,10 +481,9 @@ checksum = "7fe5bd57d1d7414c6b5ed48563a2c855d995ff777729dcd91c369ec7fea395ae" [[package]] name = "ropey" version = "1.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "ba326a8508a4add47e7b260333aa2d896213a5f3572fde11ed6e9130241b7f71" +source = "git+https://github.com/cessen/ropey#083c34949274ef9800267e6bc64b76a45e401807" dependencies = [ - "smallvec 0.6.13", + "smallvec 1.4.0", ] [[package]] @@ -555,6 +577,16 @@ dependencies = [ ] [[package]] +name = "tendril" +version = "0.4.1" +source = "git+https://github.com/servo/tendril#08f7f292ab82c00e9cf491b5918a76e53af92c8c" +dependencies = [ + "futf", + "mac", + "utf-8", +] + +[[package]] name = "terminfo" version = "0.7.3" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -640,6 +672,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "826e7639553986605ec5979c7dd957c7895e93eabed50ab2ffa7f6128a75097c" [[package]] +name = "utf-8" +version = "0.7.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "05e42f7c18b8f902290b009cde6d651262f956c98bc51bca4cd1d511c9cd85c7" + +[[package]] name = "utf8parse" version = "0.1.1" source = "registry+https://github.com/rust-lang/crates.io-index" diff --git a/helix-core/Cargo.toml b/helix-core/Cargo.toml index f1f6264f..fc6a1b53 100644 --- a/helix-core/Cargo.toml +++ b/helix-core/Cargo.toml @@ -7,7 +7,9 @@ edition = "2018" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] -ropey = "1.1.0" +# ropey = "1.1.0" +ropey = { git = "https://github.com/cessen/ropey" } anyhow = "1.0.31" smallvec = "1.4.0" +tendril = { git = "https://github.com/servo/tendril" } # slab = "0.4.2" diff --git a/helix-core/src/lib.rs b/helix-core/src/lib.rs index ceed961f..7b584401 100644 --- a/helix-core/src/lib.rs +++ b/helix-core/src/lib.rs @@ -10,4 +10,4 @@ pub use selection::Selection; pub use state::State; -pub use transaction::{Change, Transaction}; +pub use transaction::{Change, ChangeSet, Transaction}; diff --git a/helix-core/src/selection.rs b/helix-core/src/selection.rs index 24a8be46..03d5db0e 100644 --- a/helix-core/src/selection.rs +++ b/helix-core/src/selection.rs @@ -83,7 +83,7 @@ impl Range { /// A selection consists of one or more selection ranges. pub struct Selection { // TODO: decide how many ranges to inline SmallVec<[Range; 1]> - ranges: Vec<Range>, + ranges: SmallVec<[Range; 1]>, primary_index: usize, } @@ -100,7 +100,7 @@ impl Selection { self } else { Self { - ranges: vec![self.ranges[self.primary_index]], + ranges: smallvec![self.ranges[self.primary_index]], primary_index: 0, } } @@ -112,18 +112,18 @@ impl Selection { /// Constructs a selection holding a single range. pub fn single(anchor: usize, head: usize) -> Self { Self { - ranges: vec![Range { anchor, head }], + ranges: smallvec![Range { anchor, head }], primary_index: 0, } } - pub fn new(ranges: Vec<Range>, primary_index: usize) -> Self { - fn normalize(mut ranges: Vec<Range>, primary_index: usize) -> Selection { + pub fn new(ranges: SmallVec<[Range; 1]>, primary_index: usize) -> Self { + fn normalize(mut ranges: SmallVec<[Range; 1]>, primary_index: usize) -> Selection { let primary = ranges[primary_index]; ranges.sort_unstable_by_key(|range| range.from()); let mut primary_index = ranges.iter().position(|&range| range == primary).unwrap(); - let mut result: Vec<Range> = Vec::new(); + let mut result: SmallVec<[Range; 1]> = SmallVec::new(); // TODO: we could do with one vec by removing elements as we mutate @@ -174,7 +174,7 @@ mod test { #[test] fn test_create_normalizes_and_merges() { let sel = Selection::new( - vec![ + smallvec![ Range::new(10, 12), Range::new(6, 7), Range::new(4, 5), @@ -200,7 +200,7 @@ mod test { #[test] fn test_create_merges_adjacent_points() { let sel = Selection::new( - vec![ + smallvec![ Range::new(10, 12), Range::new(12, 12), Range::new(12, 12), diff --git a/helix-core/src/transaction.rs b/helix-core/src/transaction.rs index ecbe0c50..b9824bc2 100644 --- a/helix-core/src/transaction.rs +++ b/helix-core/src/transaction.rs @@ -1,25 +1,293 @@ -pub struct Change { - from: usize, - to: usize, - insert: Option<String>, +// pub struct Change { +// from: usize, +// to: usize, +// insert: Option<String>, +// } + +// 40 bytes (8 + 24 + 8) -> strings are really big 24 as String, 16 as &str +// pub struct Change { +// /// old extent +// old_extent: usize, +// /// inserted text, new extent equal to insert length +// insert: Option<String>, +// /// distance from the previous change +// distance: usize, +// } + +use crate::{Buffer, Selection}; + +use ropey::Rope; +use tendril::StrTendril as Tendril; + +// TODO: divided into three different operations, I sort of like having just +// Splice { extent, Option<text>, distance } better. +// insert: Splice { extent: 0, text: Some("a"), distance: 2 } +// delete: Splice { extent: 2, text: None, distance: 2 } +// replace: Splice { extent: 2, text: Some("abc"), distance: 2 } +// unchanged?: Splice { extent: 0, text: None, distance: 2 } +// harder to compose though. +#[derive(Debug, Clone, PartialEq, Eq)] +pub enum Change { + /// Move cursor by n characters. + Retain(usize), + /// Delete n characters. + Delete(usize), + /// Insert text at position. + Insert(Tendril), } impl Change { - pub fn new(from: usize, to: usize, insert: Option<String>) { + pub fn new(from: usize, to: usize, insert: Option<Tendril>) { // old_extent, new_extent, insert } } -pub struct Transaction {} - // ChangeSpec = Change | ChangeSet | Vec<Change> // ChangeDesc as a ChangeSet without text: can't be applied, cheaper to store. // ChangeSet = ChangeDesc with Text +#[derive(Debug)] pub struct ChangeSet { // basically Vec<ChangeDesc> where ChangeDesc = (current len, replacement len?) // (0, n>0) for insertion, (n>0, 0) for deletion, (>0, >0) for replacement - sections: Vec<(usize, isize)>, + // sections: Vec<(usize, isize)>, + changes: Vec<Change>, + /// The required document length. Will refuse to apply changes unless it matches. + len: usize, } -// + +impl ChangeSet { + pub fn new(buf: &Buffer) -> Self { + let len = buf.contents.len_chars(); + Self { + changes: vec![Change::Retain(len)], + len, + } + } + + // TODO: from iter + + /// Combine two changesets together. + /// In other words, If `this` goes `docA` → `docB` and `other` represents `docB` → `docC`, the + /// returned value will represent the change `docA` → `docC`. + pub fn compose(self, other: ChangeSet) -> Result<Self, ()> { + if self.len != other.len { + // length mismatch + return Err(()); + } + + let len = self.changes.len(); + + let mut changes_a = self.changes.into_iter(); + let mut changes_b = other.changes.into_iter(); + + let mut head_a = changes_a.next(); + let mut head_b = changes_b.next(); + + let mut changes: Vec<Change> = Vec::with_capacity(len); // TODO: max(a, b), shrink_to_fit() afterwards + + loop { + use std::cmp::Ordering; + use Change::*; + match (head_a, head_b) { + // we are done + (None, None) => { + break; + } + // deletion in A + (Some(change @ Delete(..)), b) => { + changes.push(change); + head_a = changes_a.next(); + head_b = b; + } + // insertion in B + (a, Some(change @ Insert(..))) => { + changes.push(change); + head_a = a; + head_b = changes_b.next(); + } + (None, _) => return Err(()), + (_, None) => return Err(()), + (Some(Retain(i)), Some(Retain(j))) => match i.cmp(&j) { + Ordering::Less => { + changes.push(Retain(i)); + head_a = changes_a.next(); + head_b = Some(Retain(j - i)); + } + Ordering::Equal => { + changes.push(Retain(i)); + head_a = changes_a.next(); + head_b = changes_b.next(); + } + Ordering::Greater => { + changes.push(Retain(j)); + head_a = Some(Retain(i - j)); + head_b = changes_b.next(); + } + }, + (Some(Insert(mut s)), Some(Delete(j))) => { + let len = s.chars().count(); + match len.cmp(&j) { + Ordering::Less => { + head_a = changes_a.next(); + head_b = Some(Delete(j - len)); + } + Ordering::Equal => { + head_a = changes_a.next(); + head_b = changes_b.next(); + } + Ordering::Greater => { + // figure out the byte index of the truncated string end + let (pos, _) = s.char_indices().nth(len - j).unwrap(); + // calculate the difference + let to_drop = s.len() - pos; + s.pop_back(to_drop as u32); + head_a = Some(Insert(s)); + head_b = changes_b.next(); + } + } + } + (Some(Insert(mut s)), Some(Retain(j))) => { + let len = s.chars().count(); + match len.cmp(&j) { + Ordering::Less => { + changes.push(Insert(s)); + head_a = changes_a.next(); + head_b = Some(Retain(j - len)); + } + Ordering::Equal => { + changes.push(Insert(s)); + head_a = changes_a.next(); + head_b = changes_b.next(); + } + Ordering::Greater => { + // figure out the byte index of the truncated string end + let (pos, _) = s.char_indices().nth(j).unwrap(); + // calculate the difference + let to_drop = s.len() - pos; + s.pop_back(to_drop as u32); + head_a = Some(Insert(s)); + head_b = changes_b.next(); + } + } + } + (Some(Retain(i)), Some(Delete(j))) => match i.cmp(&j) { + Ordering::Less => { + changes.push(Delete(i)); + head_a = changes_a.next(); + head_b = Some(Delete(j - i)); + } + Ordering::Equal => { + changes.push(Delete(j)); + head_a = changes_a.next(); + head_b = changes_b.next(); + } + Ordering::Greater => { + changes.push(Delete(j)); + head_a = Some(Retain(i - j)); + head_b = changes_b.next(); + } + }, + }; + } + + Ok(Self { + len: self.len, + changes, + }) + } + + /// Given another change set starting in the same document, maps this + /// change set over the other, producing a new change set that can be + /// applied to the document produced by applying `other`. When + /// `before` is `true`, order changes as if `this` comes before + /// `other`, otherwise (the default) treat `other` as coming first. + /// + /// Given two changes `A` and `B`, `A.compose(B.map(A))` and + /// `B.compose(A.map(B, true))` will produce the same document. This + /// provides a basic form of [operational + /// transformation](https://en.wikipedia.org/wiki/Operational_transformation), + /// and can be used for collaborative editing. + pub fn map(self, other: Self) -> Self { + unimplemented!() + } + + /// Returns a new changeset that reverts this one. Useful for `undo` implementation. + pub fn invert(self) -> Self { + unimplemented!() + } + + pub fn apply(&self, text: &mut Rope) { + // TODO: validate text.chars() == self.len + + let mut pos = 0; + + for change in self.changes.iter() { + use Change::*; + match change { + Retain(n) => { + pos += n; + } + Delete(n) => { + text.remove(pos..pos + *n); + // pos += n; + } + Insert(s) => { + text.insert(pos, s); + pos += s.len(); + } + } + } + } + + // iter over changes +} + // trait Transaction // trait StrictTransaction + +/// Transaction represents a single undoable unit of changes. Several changes can be grouped into +/// a single transaction. +pub struct Transaction { + /// Changes made to the buffer. + changes: ChangeSet, + /// When set, explicitly updates the selection. + selection: Option<Selection>, + // effects, annotations + // scroll_into_view +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn composition() { + use Change::*; + + let a = ChangeSet { + changes: vec![ + Retain(5), + Insert("!".into()), + Retain(1), + Delete(2), + Insert("ab".into()), + ], + len: 7, + }; + + let b = ChangeSet { + changes: vec![Delete(5), Insert("world".into()), Retain(4)], + len: 7, + }; + + let mut text = Rope::from("hello xz"); + + // should probably return cloned text + a.compose(b).unwrap().apply(&mut text); + + unimplemented!("{:?}", text); + } + + #[test] + fn map() {} +} |