From 7894ec75a7070591c3499fce1f409563c4edc7d7 Mon Sep 17 00:00:00 2001
From: Titus Wormer <tituswormer@gmail.com>
Date: Wed, 20 Jul 2022 12:34:06 +0200
Subject: Refactor to use less vecs for events

---
 src/util/edit_map.rs | 70 +++++++++++++++++++++-------------------------------
 1 file changed, 28 insertions(+), 42 deletions(-)

(limited to 'src/util/edit_map.rs')

diff --git a/src/util/edit_map.rs b/src/util/edit_map.rs
index 1f43a3a..b1b5064 100644
--- a/src/util/edit_map.rs
+++ b/src/util/edit_map.rs
@@ -13,26 +13,23 @@ use crate::tokenizer::Event;
 /// Shift `previous` and `next` links according to `jumps`.
 ///
 /// This fixes links in case there are events removed or added between them.
-fn shift_links(events: &mut [Event], jumps: &[(usize, isize)]) {
+fn shift_links(events: &mut [Event], jumps: &[(usize, usize, usize)]) {
     let map = |before| {
+        // To do: this theoretically gets slow, investigate how to improve it.
         let mut jump_index = 0;
-        let mut jump = 0;
+        let mut remove = 0;
+        let mut add = 0;
 
         while jump_index < jumps.len() {
             if jumps[jump_index].0 > before {
                 break;
             }
 
-            jump = jumps[jump_index].1;
+            (_, remove, add) = jumps[jump_index];
             jump_index += 1;
         }
 
-        #[allow(clippy::pedantic)]
-        let next_i = (before as isize) + jump;
-        assert!(next_i >= 0, "cannot shift before `0`");
-        #[allow(clippy::pedantic)]
-        let next = next_i as usize;
-        next
+        before + add - remove
     };
 
     let mut index = 0;
@@ -72,59 +69,46 @@ impl EditMap {
         add_impl(self, index, remove, add, true);
     }
     /// Done, change the events.
-    pub fn consume(&mut self, mut events: Vec<Event>) -> Vec<Event> {
+    pub fn consume(&mut self, events: &mut Vec<Event>) {
         self.map
             .sort_unstable_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
 
         assert!(!self.consumed, "cannot consume after consuming");
         self.consumed = true;
 
-        let mut jumps: Vec<(usize, isize)> = vec![];
+        // Calculate jumps: where items in the current list move to.
+        let mut jumps = Vec::with_capacity(self.map.len());
         let mut index = 0;
-        let mut shift = 0;
+        let mut add_acc = 0;
+        let mut remove_acc = 0;
         while index < self.map.len() {
             let (at, remove, add) = &self.map[index];
-
-            #[allow(clippy::pedantic)]
-            let next = shift + (add.len() as isize) - (*remove as isize);
-            shift = next;
-            jumps.push((*at, shift));
+            add_acc += add.len();
+            remove_acc += remove;
+            jumps.push((*at, remove_acc, add_acc));
             index += 1;
         }
 
+        let len_before = events.len();
         let mut index = self.map.len();
-        let mut vecs: Vec<Vec<Event>> = vec![];
-        let mut capacity = 0;
-
+        let mut vecs: Vec<Vec<Event>> = Vec::with_capacity(index * 2 + 1);
         while index > 0 {
             index -= 1;
-            let at = self.map[index].0;
-
-            let mut keep = events.split_off(at + self.map[index].1);
+            let (at, remove, _) = self.map[index];
+            let mut keep = events.split_off(at + remove);
             shift_links(&mut keep, &jumps);
-            capacity += keep.len();
             vecs.push(keep);
-
-            let add = self.map[index].2.split_off(0);
-            capacity += add.len();
-            vecs.push(add);
-
+            vecs.push(self.map[index].2.split_off(0));
             events.truncate(at);
         }
+        shift_links(events, &jumps);
+        vecs.push(events.split_off(0));
 
-        shift_links(&mut events, &jumps);
-        capacity += events.len();
-        vecs.push(events);
+        events.reserve(len_before + add_acc - remove_acc);
 
-        let mut next_events: Vec<Event> = Vec::with_capacity(capacity);
-        let mut slice = vecs.pop();
-
-        while let Some(mut x) = slice {
-            next_events.append(&mut x);
-            slice = vecs.pop();
+        while let Some(mut slice) = vecs.pop() {
+            events.append(&mut slice);
         }
-
-        next_events
     }
 }
 
@@ -133,12 +117,14 @@ fn add_impl(edit_map: &mut EditMap, at: usize, remove: usize, mut add: Vec<Event
     assert!(!edit_map.consumed, "cannot add after consuming");
     let mut index = 0;
 
+    if remove == 0 && add.is_empty() {
+        return;
+    }
+
     while index < edit_map.map.len() {
         if edit_map.map[index].0 == at {
             edit_map.map[index].1 += remove;
 
-            // To do: these might have to be split into several chunks instead
-            // of one, if links in `curr_add` are supported.
             if before {
                 add.append(&mut edit_map.map[index].2);
                 edit_map.map[index].2 = add;
-- 
cgit