Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'helix-core/src/transaction.rs')
| -rw-r--r-- | helix-core/src/transaction.rs | 416 |
1 files changed, 59 insertions, 357 deletions
diff --git a/helix-core/src/transaction.rs b/helix-core/src/transaction.rs index 37be2e2e..daf4a77e 100644 --- a/helix-core/src/transaction.rs +++ b/helix-core/src/transaction.rs @@ -1,12 +1,8 @@ -use ropey::RopeSlice; -use smallvec::SmallVec; - -use crate::{chars::char_is_word, Range, Rope, Selection, Tendril}; -use std::{borrow::Cow, iter::once}; +use crate::{Range, Rope, Selection, Tendril}; +use std::borrow::Cow; /// (from, to, replacement) pub type Change = (usize, usize, Option<Tendril>); -pub type Deletion = (usize, usize); // TODO: pub(crate) #[derive(Debug, Clone, PartialEq, Eq)] @@ -19,54 +15,10 @@ pub enum Operation { Insert(Tendril), } -impl Operation { - /// The number of characters affected by the operation. - pub fn len_chars(&self) -> usize { - match self { - Self::Retain(n) | Self::Delete(n) => *n, - Self::Insert(s) => s.chars().count(), - } - } -} - #[derive(Debug, Copy, Clone, PartialEq, Eq)] pub enum Assoc { Before, After, - /// Acts like `After` if a word character is inserted - /// after the position, otherwise acts like `Before` - AfterWord, - /// Acts like `Before` if a word character is inserted - /// before the position, otherwise acts like `After` - BeforeWord, - /// Acts like `Before` but if the position is within an exact replacement - /// (exact size) the offset to the start of the replacement is kept - BeforeSticky, - /// Acts like `After` but if the position is within an exact replacement - /// (exact size) the offset to the start of the replacement is kept - AfterSticky, -} - -impl Assoc { - /// Whether to stick to gaps - fn stay_at_gaps(self) -> bool { - !matches!(self, Self::BeforeWord | Self::AfterWord) - } - - fn insert_offset(self, s: &str) -> usize { - let chars = s.chars().count(); - match self { - Assoc::After | Assoc::AfterSticky => chars, - Assoc::AfterWord => s.chars().take_while(|&c| char_is_word(c)).count(), - // return position before inserted text - Assoc::Before | Assoc::BeforeSticky => 0, - Assoc::BeforeWord => chars - s.chars().rev().take_while(|&c| char_is_word(c)).count(), - } - } - - pub fn sticky(self) -> bool { - matches!(self, Assoc::BeforeSticky | Assoc::AfterSticky) - } } #[derive(Debug, Default, Clone, PartialEq, Eq)] @@ -87,7 +39,7 @@ impl ChangeSet { } #[must_use] - pub fn new(doc: RopeSlice) -> Self { + pub fn new(doc: &Rope) -> Self { let len = doc.len_chars(); Self { changes: Vec::new(), @@ -104,7 +56,7 @@ impl ChangeSet { } // Changeset builder operations: delete/insert/retain - pub(crate) fn delete(&mut self, n: usize) { + fn delete(&mut self, n: usize) { use Operation::*; if n == 0 { return; @@ -119,7 +71,7 @@ impl ChangeSet { } } - pub(crate) fn insert(&mut self, fragment: Tendril) { + fn insert(&mut self, fragment: Tendril) { use Operation::*; if fragment.is_empty() { @@ -141,7 +93,7 @@ impl ChangeSet { self.changes.push(new_last); } - pub(crate) fn retain(&mut self, n: usize) { + fn retain(&mut self, n: usize) { use Operation::*; if n == 0 { return; @@ -361,7 +313,6 @@ impl ChangeSet { pos += s.chars().count(); } } - println!("=>\n{text}"); } true } @@ -372,80 +323,20 @@ impl ChangeSet { self.changes.is_empty() || self.changes == [Operation::Retain(self.len)] } - /// Map a (mostly) *sorted* list of positions through the changes. - /// - /// This is equivalent to updating each position with `map_pos`: + /// Map a position through the changes. /// - /// ``` no-compile - /// for (pos, assoc) in positions { - /// *pos = changes.map_pos(*pos, assoc); - /// } - /// ``` - /// However this function is significantly faster for sorted lists running - /// in `O(N+M)` instead of `O(NM)`. This function also handles unsorted/ - /// partially sorted lists. However, in that case worst case complexity is - /// again `O(MN)`. For lists that are often/mostly sorted (like the end of diagnostic ranges) - /// performance is usally close to `O(N + M)` - pub fn update_positions<'a>(&self, positions: impl Iterator<Item = (&'a mut usize, Assoc)>) { + /// `assoc` indicates which size to associate the position with. `Before` will keep the + /// position close to the character before, and will place it before insertions over that + /// range, or at that point. `After` will move it forward, placing it at the end of such + /// insertions. + pub fn map_pos(&self, pos: usize, assoc: Assoc) -> usize { use Operation::*; - - let mut positions = positions.peekable(); - let mut old_pos = 0; let mut new_pos = 0; - let mut iter = self.changes.iter().enumerate().peekable(); - - 'outer: loop { - macro_rules! map { - ($map: expr, $i: expr) => { - loop { - let Some((pos, assoc)) = positions.peek_mut() else { - return; - }; - if **pos < old_pos { - // Positions are not sorted, revert to the last Operation that - // contains this position and continue iterating from there. - // We can unwrap here since `pos` can not be negative - // (unsigned integer) and iterating backwards to the start - // should always move us back to the start - for (i, change) in self.changes[..$i].iter().enumerate().rev() { - match change { - Retain(i) => { - old_pos -= i; - new_pos -= i; - } - Delete(i) => { - old_pos -= i; - } - Insert(ins) => { - new_pos -= ins.chars().count(); - } - } - if old_pos <= **pos { - iter = self.changes[i..].iter().enumerate().peekable(); - } - } - debug_assert!(old_pos <= **pos, "Reverse Iter across changeset works"); - continue 'outer; - } - #[allow(clippy::redundant_closure_call)] - let Some(new_pos) = $map(**pos, *assoc) else { - break; - }; - **pos = new_pos; - positions.next(); - } - }; - } - let Some((i, change)) = iter.next() else { - map!( - |pos, _| (old_pos == pos).then_some(new_pos), - self.changes.len() - ); - break; - }; + let mut iter = self.changes.iter().peekable(); + while let Some(change) = iter.next() { let len = match change { Delete(i) | Retain(i) => *i, Insert(_) => 0, @@ -454,74 +345,64 @@ impl ChangeSet { match change { Retain(_) => { - map!( - |pos, _| (old_end > pos).then_some(new_pos + (pos - old_pos)), - i - ); + if old_end > pos { + return new_pos + (pos - old_pos); + } new_pos += len; } Delete(_) => { // in range - map!(|pos, _| (old_end > pos).then_some(new_pos), i); + if old_end > pos { + return new_pos; + } } Insert(s) => { + let ins = s.chars().count(); + // a subsequent delete means a replace, consume it - if let Some((_, Delete(len))) = iter.peek() { + if let Some(Delete(len)) = iter.peek() { iter.next(); old_end = old_pos + len; // in range of replaced text - map!( - |pos, assoc: Assoc| (old_end > pos).then(|| { - // at point or tracking before - if pos == old_pos && assoc.stay_at_gaps() { - new_pos - } else { - let ins = assoc.insert_offset(s); - // if the deleted and inserted text have the exact same size - // keep the relative offset into the new text - if *len == ins && assoc.sticky() { - new_pos + (pos - old_pos) - } else { - new_pos + assoc.insert_offset(s) - } - } - }), - i - ); + if old_end > pos { + // at point or tracking before + if pos == old_pos || assoc == Assoc::Before { + return new_pos; + } else { + // place to end of insert + return new_pos + ins; + } + } } else { // at insert point - map!( - |pos, assoc: Assoc| (old_pos == pos).then(|| { - // return position before inserted text - new_pos + assoc.insert_offset(s) - }), - i - ); + if old_pos == pos { + // return position before inserted text + if assoc == Assoc::Before { + return new_pos; + } else { + // after text + return new_pos + ins; + } + } } - new_pos += s.chars().count(); + new_pos += ins; } } old_pos = old_end; } - let out_of_bounds: Vec<_> = positions.collect(); - - panic!("Positions {out_of_bounds:?} are out of range for changeset len {old_pos}!",) - } - /// Map a position through the changes. - /// - /// `assoc` indicates which side to associate the position with. `Before` will keep the - /// position close to the character before, and will place it before insertions over that - /// range, or at that point. `After` will move it forward, placing it at the end of such - /// insertions. - pub fn map_pos(&self, mut pos: usize, assoc: Assoc) -> usize { - self.update_positions(once((&mut pos, assoc))); - pos + if pos > old_pos { + panic!( + "Position {} is out of range for changeset len {}!", + pos, old_pos + ) + } + new_pos } - pub fn changes_iter(&self) -> ChangeIterator<'_> { + pub fn changes_iter(&self) -> ChangeIterator { ChangeIterator::new(self) } } @@ -538,7 +419,7 @@ impl Transaction { /// Create a new, empty transaction. pub fn new(doc: &Rope) -> Self { Self { - changes: ChangeSet::new(doc.slice(..)), + changes: ChangeSet::new(doc), selection: None, } } @@ -585,33 +466,6 @@ impl Transaction { self } - /// Generate a transaction from a set of potentially overlapping changes. The `change_ranges` - /// iterator yield the range (of removed text) in the old document for each edit. If any change - /// overlaps with a range overlaps with a previous range then that range is ignored. - /// - /// The `process_change` callback is called for each edit that is not ignored (in the order - /// yielded by `changes`) and should return the new text that the associated range will be - /// replaced with. - /// - /// To make this function more flexible the iterator can yield additional data for each change - /// that is passed to `process_change` - pub fn change_ignore_overlapping<T>( - doc: &Rope, - change_ranges: impl Iterator<Item = (usize, usize, T)>, - mut process_change: impl FnMut(usize, usize, T) -> Option<Tendril>, - ) -> Self { - let mut last = 0; - let changes = change_ranges.filter_map(|(from, to, data)| { - if from < last { - return None; - } - let tendril = process_change(from, to, data); - last = to; - Some((from, to, tendril)) - }); - Self::change(doc, changes) - } - /// Generate a transaction from a set of changes. pub fn change<I>(doc: &Rope, changes: I) -> Self where @@ -627,11 +481,6 @@ impl Transaction { for (from, to, tendril) in changes { // Verify ranges are ordered and not overlapping debug_assert!(last <= from); - // Verify ranges are correct - debug_assert!( - from <= to, - "Edit end must end before it starts (should {from} <= {to})" - ); // Retain from last "to" to current "from" changeset.retain(from - last); @@ -651,46 +500,6 @@ impl Transaction { Self::from(changeset) } - /// Generate a transaction from a set of potentially overlapping deletions - /// by merging overlapping deletions together. - pub fn delete<I>(doc: &Rope, deletions: I) -> Self - where - I: Iterator<Item = Deletion>, - { - let len = doc.len_chars(); - - let (lower, upper) = deletions.size_hint(); - let size = upper.unwrap_or(lower); - let mut changeset = ChangeSet::with_capacity(2 * size + 1); // rough estimate - - let mut last = 0; - for (mut from, to) in deletions { - if last > to { - continue; - } - if last > from { - from = last - } - debug_assert!( - from <= to, - "Edit end must end before it starts (should {from} <= {to})" - ); - // Retain from last "to" to current "from" - changeset.retain(from - last); - changeset.delete(to - from); - last = to; - } - - changeset.retain(len - last); - - Self::from(changeset) - } - - pub fn insert_at_eof(mut self, text: Tendril) -> Transaction { - self.changes.insert(text); - self - } - /// Generate a transaction with a change per selection range. pub fn change_by_selection<F>(doc: &Rope, selection: &Selection, f: F) -> Self where @@ -699,54 +508,6 @@ impl Transaction { Self::change(doc, selection.iter().map(f)) } - pub fn change_by_selection_ignore_overlapping( - doc: &Rope, - selection: &Selection, - mut change_range: impl FnMut(&Range) -> (usize, usize), - mut create_tendril: impl FnMut(usize, usize) -> Option<Tendril>, - ) -> (Transaction, Selection) { - let mut last_selection_idx = None; - let mut new_primary_idx = None; - let mut ranges: SmallVec<[Range; 1]> = SmallVec::new(); - let process_change = |change_start, change_end, (idx, range): (usize, &Range)| { - // update the primary idx - if idx == selection.primary_index() { - new_primary_idx = Some(idx); - } else if new_primary_idx.is_none() { - if idx > selection.primary_index() { - new_primary_idx = last_selection_idx; - } else { - last_selection_idx = Some(idx); - } - } - ranges.push(*range); - create_tendril(change_start, change_end) - }; - let transaction = Self::change_ignore_overlapping( - doc, - selection.iter().enumerate().map(|range| { - let (change_start, change_end) = change_range(range.1); - (change_start, change_end, range) - }), - process_change, - ); - - ( - transaction, - Selection::new(ranges, new_primary_idx.unwrap_or(0)), - ) - } - - /// Generate a transaction with a deletion per selection range. - /// Compared to using `change_by_selection` directly these ranges may overlap. - /// In that case they are merged - pub fn delete_by_selection<F>(doc: &Rope, selection: &Selection, f: F) -> Self - where - F: FnMut(&Range) -> Deletion, - { - Self::delete(doc, selection.iter().map(f)) - } - /// Insert text at each selection head. pub fn insert(doc: &Rope, selection: &Selection, text: Tendril) -> Self { Self::change_by_selection(doc, selection, |range| { @@ -754,7 +515,7 @@ impl Transaction { }) } - pub fn changes_iter(&self) -> ChangeIterator<'_> { + pub fn changes_iter(&self) -> ChangeIterator { self.changes.changes_iter() } } @@ -780,7 +541,7 @@ impl<'a> ChangeIterator<'a> { } } -impl Iterator for ChangeIterator<'_> { +impl<'a> Iterator for ChangeIterator<'a> { type Item = Change; fn next(&mut self) -> Option<Self::Item> { @@ -816,7 +577,7 @@ impl Iterator for ChangeIterator<'_> { #[cfg(test)] mod test { use super::*; - use crate::history::State; + use crate::State; #[test] fn composition() { @@ -919,62 +680,6 @@ mod test { }; assert_eq!(cs.map_pos(2, Assoc::Before), 2); assert_eq!(cs.map_pos(2, Assoc::After), 2); - // unsorted selection - let cs = ChangeSet { - changes: vec![ - Insert("ab".into()), - Delete(2), - Insert("cd".into()), - Delete(2), - ], - len: 4, - len_after: 4, - }; - let mut positions = [4, 2]; - cs.update_positions(positions.iter_mut().map(|pos| (pos, Assoc::After))); - assert_eq!(positions, [4, 2]); - // stays at word boundary - let cs = ChangeSet { - changes: vec![ - Retain(2), // <space><space> - Insert(" ab".into()), - Retain(2), // cd - Insert("de ".into()), - ], - len: 4, - len_after: 10, - }; - assert_eq!(cs.map_pos(2, Assoc::BeforeWord), 3); - assert_eq!(cs.map_pos(4, Assoc::AfterWord), 9); - let cs = ChangeSet { - changes: vec![ - Retain(1), // <space> - Insert(" b".into()), - Delete(1), // c - Retain(1), // d - Insert("e ".into()), - Delete(1), // <space> - ], - len: 5, - len_after: 7, - }; - assert_eq!(cs.map_pos(1, Assoc::BeforeWord), 2); - assert_eq!(cs.map_pos(3, Assoc::AfterWord), 5); - let cs = ChangeSet { - changes: vec![ - Retain(1), // <space> - Insert("a".into()), - Delete(2), // <space>b - Retain(1), // d - Insert("e".into()), - Delete(1), // f - Retain(1), // <space> - ], - len: 5, - len_after: 7, - }; - assert_eq!(cs.map_pos(2, Assoc::BeforeWord), 1); - assert_eq!(cs.map_pos(4, Assoc::AfterWord), 4); } #[test] @@ -999,10 +704,7 @@ mod test { #[test] fn optimized_composition() { - let mut state = State { - doc: "".into(), - selection: Selection::point(0), - }; + let mut state = State::new("".into()); let t1 = Transaction::insert(&state.doc, &state.selection, Tendril::from("h")); t1.apply(&mut state.doc); state.selection = state.selection.clone().map(t1.changes()); @@ -1041,9 +743,9 @@ mod test { #[test] fn combine_with_empty() { let empty = Rope::from(""); - let a = ChangeSet::new(empty.slice(..)); + let a = ChangeSet::new(&empty); - let mut b = ChangeSet::new(empty.slice(..)); + let mut b = ChangeSet::new(&empty); b.insert("a".into()); let changes = a.compose(b); @@ -1057,9 +759,9 @@ mod test { const TEST_CASE: &str = "Hello, これはヘリックスエディターです！"; let empty = Rope::from(""); - let a = ChangeSet::new(empty.slice(..)); + let a = ChangeSet::new(&empty); - let mut b = ChangeSet::new(empty.slice(..)); + let mut b = ChangeSet::new(&empty); b.insert(TEST_CASE.into()); let changes = a.compose(b); |