1 files changed, 48 insertions, 29 deletions

diff --git a/helix-core/src/transaction.rs b/helix-core/src/transaction.rs
index f4f94b54..53e53c23 100644
--- a/helix-core/src/transaction.rs
+++ b/helix-core/src/transaction.rs
@@ -1,7 +1,7 @@
 use smallvec::SmallVec;
 
 use crate::{Range, Rope, Selection, Tendril};
-use std::borrow::Cow;
+use std::{borrow::Cow, iter::once};
 
 /// (from, to, replacement)
 pub type Change = (usize, usize, Option<Tendril>);
@@ -326,17 +326,33 @@ impl ChangeSet {
         self.changes.is_empty() || self.changes == [Operation::Retain(self.len)]
     }
 
-    /// Map a position through the changes.
+    /// Map a *sorted* list of positions through the changes.
     ///
-    /// `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 {
+    /// This is equivalent to updating each position with `map_pos`:
+    ///
+    /// ``` no-compile
+    /// for (pos, assoc) in positions {
+    ///     *pos = changes.map_pos(*pos, assoc);
+    /// }
+    /// ```
+    /// However this function is significantly faster running in `O(N+M)` instead of `O(NM)`
+    pub fn update_positions<'a>(&self, positions: impl Iterator<Item = (&'a mut usize, Assoc)>) {
         use Operation::*;
+
+        let mut positions = positions.peekable();
+        macro_rules! map {
+            ($map: expr) => {
+                loop {
+                    let Some((pos, assoc)) = positions.peek_mut() else { return; };
+                    let Some(new_pos) = $map(**pos, *assoc) else { break; };
+                    **pos = new_pos;
+                    positions.next();
+                }
+            };
+        }
+
         let mut old_pos = 0;
         let mut new_pos = 0;
-
         let mut iter = self.changes.iter().peekable();
 
         while let Some(change) = iter.next() {
@@ -348,16 +364,12 @@ impl ChangeSet {
 
             match change {
                 Retain(_) => {
-                    if old_end > pos {
-                        return new_pos + (pos - old_pos);
-                    }
+                    map!(|pos, _| (old_end > pos).then_some(new_pos + (pos - old_pos)));
                     new_pos += len;
                 }
                 Delete(_) => {
                     // in range
-                    if old_end > pos {
-                        return new_pos;
-                    }
+                    map!(|pos, _| (old_end > pos).then_some(new_pos));
                 }
                 Insert(s) => {
                     let ins = s.chars().count();
@@ -368,26 +380,26 @@ impl ChangeSet {
 
                         old_end = old_pos + len;
                         // in range of replaced text
-                        if old_end > pos {
+                        map!(|pos, assoc| (old_end > pos).then(|| {
                             // at point or tracking before
                             if pos == old_pos || assoc == Assoc::Before {
-                                return new_pos;
+                                new_pos
                             } else {
                                 // place to end of insert
-                                return new_pos + ins;
+                                new_pos + ins
                             }
-                        }
+                        }));
                     } else {
                         // at insert point
-                        if old_pos == pos {
+                        map!(|pos, assoc| (old_pos == pos).then(|| {
                             // return position before inserted text
                             if assoc == Assoc::Before {
-                                return new_pos;
+                                new_pos
                             } else {
                                 // after text
-                                return new_pos + ins;
+                                new_pos + ins
                             }
-                        }
+                        }));
                     }
 
                     new_pos += ins;
@@ -395,14 +407,21 @@ impl ChangeSet {
             }
             old_pos = old_end;
         }
+        map!(|pos, _| (old_pos == pos).then_some(new_pos));
+        let out_of_bounds: Vec<_> = positions.collect();
 
-        if pos > old_pos {
-            panic!(
-                "Position {} is out of range for changeset len {}!",
-                pos, old_pos
-            )
-        }
-        new_pos
+        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
     }
 
     pub fn changes_iter(&self) -> ChangeIterator {