Start tuning the performance of rope.

1 files changed, 48 insertions, 51 deletions

diff --git a/src/rope.rs b/src/rope.rs
index 8bda5af..930c88a 100644
--- a/src/rope.rs
+++ b/src/rope.rs
@@ -9,10 +9,11 @@ enum Insert {
 }
 
 #[derive(Debug, Clone)]
-pub struct Leaf {
+struct Leaf {
     unsafe_buf: Option<Rc<[u8]>>,
     start: u16,
     end: u16,
+    lines: u16,
 }
 
 impl Leaf {
@@ -25,23 +26,16 @@ impl Leaf {
 }
 
 #[derive(Debug, Clone)]
-pub struct Branch {
-    unsafe_children: [Rope; 3],
+struct Branch {
+    children: Rc<[Rope]>,
     len: usize,
     lines: usize,
-    n_children: u8,
-}
-
-impl Branch {
-    fn children(&self) -> &[Rope] {
-        &self.unsafe_children[..usize::from(self.n_children)]
-    }
 }
 
 #[derive(Debug, Clone)]
 enum Node {
     Leaf(Leaf),
-    Branch(Rc<Branch>),
+    Branch(Branch),
 }
 
 #[derive(Debug, Clone)]
@@ -57,15 +51,7 @@ impl Rope {
 
     pub fn lines(&self) -> usize {
         match self {
-            Rope(Node::Leaf(l)) => {
-                let mut lines = 0;
-                for &b in l.bytes().iter() {
-                    if b == b'\n' {
-                        lines += 1;
-                    }
-                }
-                lines
-            }
+            Rope(Node::Leaf(l)) => usize::from(l.lines),
             Rope(Node::Branch(b)) => b.lines,
         }
     }
@@ -79,12 +65,20 @@ impl Rope {
                 unsafe_buf: None,
                 start: 0,
                 end: 0,
+                lines: 0,
             }));
         }
+        let mut lines = 0;
+        for &b in buf.iter() {
+            if b == b'\n' {
+                lines += 1;
+            }
+        }
         Rope(Node::Leaf(Leaf {
             unsafe_buf: Some(Rc::from(buf)),
             start: 0,
             end: u16::try_from(buf.len()).expect("buf.len() <= MAX_NODE_SIZE"),
+            lines,
         }))
     }
 
@@ -95,17 +89,11 @@ impl Rope {
             len += c.len();
             lines += c.lines();
         }
-        let mut child_array = [Rope::leaf(&[]), Rope::leaf(&[]), Rope::leaf(&[])];
-        for (i, c) in children.iter().enumerate() {
-            child_array[i] = c.clone();
-        }
-        Rope(Node::Branch(Rc::new(Branch {
-            unsafe_children: child_array,
+        Rope(Node::Branch(Branch {
+            children: Rc::from(children),
             len,
             lines,
-            n_children: u8::try_from(children.len())
-                .expect("there should only ever be 2 or 3 children"),
-        })))
+        }))
     }
 
     fn concat_height(&self, self_height: usize, other: &Rope, other_height: usize) -> Insert {
@@ -134,26 +122,26 @@ impl Rope {
             let Rope(Node::Branch(b)) = self else {
                 panic!("self_height is at least 1, so it's a branch");
             };
-            match b.children()[b.children().len() - 1].concat_height(
+            match b.children[b.children.len() - 1].concat_height(
                 self_height - 1,
                 other,
                 other_height,
             ) {
                 Insert::Node(new_child) => {
-                    let mut new_children = b.children().to_vec();
-                    new_children[b.children().len() - 1] = new_child;
+                    let mut new_children = b.children.to_vec();
+                    new_children[b.children.len() - 1] = new_child;
                     return Insert::Node(Rope::branch(&new_children));
                 }
                 Insert::Split(child1, child2) => {
-                    if b.children().len() == 2 {
+                    if b.children.len() == 2 {
                         return Insert::Node(Rope::branch(&[
-                            b.children()[0].clone(),
+                            b.children[0].clone(),
                             child1,
                             child2,
                         ]));
                     }
                     return Insert::Split(
-                        Rope::branch(&[b.children()[0].clone(), b.children()[1].clone()]),
+                        Rope::branch(&[b.children[0].clone(), b.children[1].clone()]),
                         Rope::branch(&[child1, child2]),
                     );
                 }
@@ -162,19 +150,19 @@ impl Rope {
         let Rope(Node::Branch(b)) = other else {
             panic!("other_height is at least 1, so it's a branch");
         };
-        match self.concat_height(self_height, &b.children()[0], other_height - 1) {
+        match self.concat_height(self_height, &b.children[0], other_height - 1) {
             Insert::Node(new_child) => {
-                let mut new_children = b.children().to_vec();
+                let mut new_children = b.children.to_vec();
                 new_children[0] = new_child;
                 Insert::Node(Rope::branch(&new_children))
             }
             Insert::Split(child1, child2) => {
-                if b.children().len() == 2 {
-                    return Insert::Node(Rope::branch(&[child1, child2, b.children()[1].clone()]));
+                if b.children.len() == 2 {
+                    return Insert::Node(Rope::branch(&[child1, child2, b.children[1].clone()]));
                 }
                 Insert::Split(
                     Rope::branch(&[child1, child2]),
-                    Rope::branch(&[b.children()[1].clone(), b.children()[2].clone()]),
+                    Rope::branch(&[b.children[1].clone(), b.children[2].clone()]),
                 )
             }
         }
@@ -183,7 +171,7 @@ impl Rope {
     fn height(&self) -> usize {
         match self {
             Rope(Node::Leaf(_)) => 0,
-            Rope(Node::Branch(b)) => 1 + b.children()[0].height(),
+            Rope(Node::Branch(b)) => 1 + b.children[0].height(),
         }
     }
 
@@ -225,7 +213,7 @@ impl Rope {
             }
             Rope(Node::Branch(b)) => {
                 let mut i = i;
-                for c in b.children().iter() {
+                for c in b.children.iter() {
                     if i < c.len() {
                         return c.is_char_boundary(i);
                     }
@@ -271,7 +259,7 @@ impl Rope {
             Rope(Node::Branch(b)) => {
                 let mut n = n;
                 let mut offset = 0;
-                for c in b.children().iter() {
+                for c in b.children.iter() {
                     if n < c.lines() {
                         return offset + c.line_end(n);
                     }
@@ -304,7 +292,7 @@ impl Rope {
                 Ok(())
             }
             Rope(Node::Branch(b)) => {
-                for c in b.children().iter() {
+                for c in b.children.iter() {
                     c.print(w)?;
                 }
                 Ok(())
@@ -330,16 +318,25 @@ impl Rope {
             return self.clone();
         }
         match self {
-            Rope(Node::Leaf(l)) => Rope(Node::Leaf(Leaf {
-                unsafe_buf: l.unsafe_buf.clone(),
-                start: l.start + u16::try_from(start).expect("start <= self.len()"),
-                end: l.start + u16::try_from(end).expect("end <= self.len()"),
-            })),
+            Rope(Node::Leaf(l)) => {
+                let mut lines = 0;
+                for &b in l.bytes()[start..end].iter() {
+                    if b == b'\n' {
+                        lines += 1;
+                    }
+                }
+                Rope(Node::Leaf(Leaf {
+                    unsafe_buf: l.unsafe_buf.clone(),
+                    start: l.start + u16::try_from(start).expect("start <= self.len()"),
+                    end: l.start + u16::try_from(end).expect("end <= self.len()"),
+                    lines,
+                }))
+            }
             Rope(Node::Branch(b)) => {
                 let mut s = Rope::new(&[]);
                 let mut start = start;
                 let mut end = end;
-                for c in b.children().iter() {
+                for c in b.children.iter() {
                     if start >= c.len() {
                         start -= c.len();
                         end -= c.len();
@@ -365,7 +362,7 @@ impl Rope {
             Rope(Node::Leaf(l)) => l.bytes()[i],
             Rope(Node::Branch(b)) => {
                 let mut i = i;
-                for c in b.children().iter() {
+                for c in b.children.iter() {
                     if i < c.len() {
                         return c.byte(i);
                     }