fix panic when deleting overlapping ranges

Some deletion operations (especially those that use indentation)
can generate overlapping deletion ranges when using multiple cursors.
To fix that problem a new `Transaction::delete` and
`Transaction:delete_by_selection` function were added. These functions
merge overlapping deletion ranges instead of generating an invalid
transaction. This merging of changes is only possible for deletions
and not for other changes and therefore require its own function.

The function has been used in all commands that currently delete
text by using `Transaction::change_by_selection`.

2 files changed, 47 insertions, 1 deletions

diff --git a/helix-core/src/lib.rs b/helix-core/src/lib.rs
index b67e2c8a..14abf016 100644
--- a/helix-core/src/lib.rs
+++ b/helix-core/src/lib.rs
@@ -67,4 +67,4 @@ pub use syntax::Syntax;
 pub use diagnostic::Diagnostic;
 
 pub use line_ending::{LineEnding, DEFAULT_LINE_ENDING};
-pub use transaction::{Assoc, Change, ChangeSet, Operation, Transaction};
+pub use transaction::{Assoc, Change, ChangeSet, Deletion, Operation, Transaction};
diff --git a/helix-core/src/transaction.rs b/helix-core/src/transaction.rs
index d8e581aa..06efe259 100644
--- a/helix-core/src/transaction.rs
+++ b/helix-core/src/transaction.rs
@@ -5,6 +5,7 @@ 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)]
@@ -534,6 +535,41 @@ 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)
+    }
+
     /// Generate a transaction with a change per selection range.
     pub fn change_by_selection<F>(doc: &Rope, selection: &Selection, f: F) -> Self
     where
@@ -580,6 +616,16 @@ impl Transaction {
         )
     }
 
+    /// 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| {