Try to avoid copies.

1 files changed, 72 insertions, 42 deletions

diff --git a/src/rope.rs b/src/rope.rs
index 930c88a..62c6a89 100644
--- a/src/rope.rs
+++ b/src/rope.rs
@@ -56,33 +56,39 @@ impl Rope {
         }
     }
 
-    fn leaf(buf: &[u8]) -> Rope {
-        if buf.len() > MAX_NODE_SIZE {
-            panic!("buffer too long for leaf!");
-        }
-        if buf.is_empty() {
-            return Rope(Node::Leaf(Leaf {
-                unsafe_buf: None,
-                start: 0,
-                end: 0,
-                lines: 0,
-            }));
+    fn empty() -> Rope {
+        Rope(Node::Leaf(Leaf {
+            unsafe_buf: None,
+            start: 0,
+            end: 0,
+            lines: 0,
+        }))
+    }
+
+    fn from_slice(buf: Rc<[u8]>, start: usize, end: usize) -> Rope {
+        if buf.len() > MAX_NODE_SIZE || start > buf.len() || end > buf.len() || start > end {
+            panic!("Invalid leaf!");
         }
         let mut lines = 0;
-        for &b in buf.iter() {
+        for &b in buf[start..end].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"),
+            unsafe_buf: Some(buf),
+            start: u16::try_from(start).expect("buffer too long"),
+            end: u16::try_from(end).expect("buffer too long"),
             lines,
         }))
     }
 
-    fn branch(children: &[Rope]) -> Rope {
+    fn leaf(buf: Rc<[u8]>) -> Rope {
+        let n = buf.len();
+        Rope::from_slice(buf, 0, n)
+    }
+
+    fn branch(children: Rc<[Rope]>) -> Rope {
         let mut len = 0;
         let mut lines = 0;
         for c in children.iter() {
@@ -90,7 +96,7 @@ impl Rope {
             lines += c.lines();
         }
         Rope(Node::Branch(Branch {
-            children: Rc::from(children),
+            children,
             len,
             lines,
         }))
@@ -99,18 +105,20 @@ impl Rope {
     fn concat_height(&self, self_height: usize, other: &Rope, other_height: usize) -> Insert {
         if let (Rope(Node::Leaf(l)), Rope(Node::Leaf(r))) = (self, other) {
             if self.len() + other.len() <= MAX_NODE_SIZE {
-                let mut buf = vec![0; self.len() + other.len()];
-                buf[..self.len()].copy_from_slice(l.bytes());
-                buf[self.len()..].copy_from_slice(r.bytes());
-                return Insert::Node(Rope::leaf(&buf));
+                let mut buf: Rc<[u8]> = Rc::from(vec![0; self.len() + other.len()]);
+                let buf_m = Rc::get_mut(&mut buf)
+                    .expect("r was just created, so there can't be any other references");
+                buf_m[..self.len()].copy_from_slice(l.bytes());
+                buf_m[self.len()..].copy_from_slice(r.bytes());
+                return Insert::Node(Rope::leaf(buf));
             }
             if self.len() < MAX_NODE_SIZE / 2 || other.len() < MAX_NODE_SIZE / 2 {
                 let mut buf = vec![0; self.len() + other.len()];
                 buf[..self.len()].copy_from_slice(l.bytes());
                 buf[self.len()..].copy_from_slice(r.bytes());
                 return Insert::Split(
-                    Rope::leaf(&buf[..buf.len() / 2]),
-                    Rope::leaf(&buf[buf.len() / 2..]),
+                    Rope::leaf(Rc::from(&buf[..buf.len() / 2])),
+                    Rope::leaf(Rc::from(&buf[buf.len() / 2..])),
                 );
             }
             return Insert::Split(self.clone(), other.clone());
@@ -128,21 +136,29 @@ impl Rope {
                 other_height,
             ) {
                 Insert::Node(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));
+                    if b.children.len() == 2 {
+                        return Insert::Node(Rope::branch(Rc::new([
+                            b.children[0].clone(),
+                            new_child,
+                        ])));
+                    }
+                    return Insert::Node(Rope::branch(Rc::new([
+                        b.children[0].clone(),
+                        b.children[1].clone(),
+                        new_child,
+                    ])));
                 }
                 Insert::Split(child1, child2) => {
                     if b.children.len() == 2 {
-                        return Insert::Node(Rope::branch(&[
+                        return Insert::Node(Rope::branch(Rc::new([
                             b.children[0].clone(),
                             child1,
                             child2,
-                        ]));
+                        ])));
                     }
                     return Insert::Split(
-                        Rope::branch(&[b.children[0].clone(), b.children[1].clone()]),
-                        Rope::branch(&[child1, child2]),
+                        Rope::branch(Rc::new([b.children[0].clone(), b.children[1].clone()])),
+                        Rope::branch(Rc::new([child1, child2])),
                     );
                 }
             }
@@ -152,17 +168,26 @@ impl Rope {
         };
         match self.concat_height(self_height, &b.children[0], other_height - 1) {
             Insert::Node(new_child) => {
-                let mut new_children = b.children.to_vec();
-                new_children[0] = new_child;
-                Insert::Node(Rope::branch(&new_children))
+                if b.children.len() == 2 {
+                    return Insert::Node(Rope::branch(Rc::new([new_child, b.children[1].clone()])));
+                }
+                Insert::Node(Rope::branch(Rc::new([
+                    new_child,
+                    b.children[1].clone(),
+                    b.children[2].clone(),
+                ])))
             }
             Insert::Split(child1, child2) => {
                 if b.children.len() == 2 {
-                    return Insert::Node(Rope::branch(&[child1, child2, b.children[1].clone()]));
+                    return Insert::Node(Rope::branch(Rc::new([
+                        child1,
+                        child2,
+                        b.children[1].clone(),
+                    ])));
                 }
                 Insert::Split(
-                    Rope::branch(&[child1, child2]),
-                    Rope::branch(&[b.children[1].clone(), b.children[2].clone()]),
+                    Rope::branch(Rc::new([child1, child2])),
+                    Rope::branch(Rc::new([b.children[1].clone(), b.children[2].clone()])),
                 )
             }
         }
@@ -184,24 +209,29 @@ impl Rope {
         }
         match self.concat_height(self.height(), other, other.height()) {
             Insert::Node(r) => r,
-            Insert::Split(l, r) => Rope::branch(&[l, r]),
+            Insert::Split(l, r) => Rope::branch(Rc::new([l, r])),
         }
     }
 
     pub fn read(r: &mut dyn Read) -> Result<Rope, std::io::Error> {
-        let mut buf = vec![0; MAX_NODE_SIZE];
-        let mut rope = Rope::leaf(&[]);
+        let mut rope = Rope::empty();
         loop {
-            let n = r.read(&mut buf)?;
+            let mut buf = Rc::new([0; MAX_NODE_SIZE]);
+            let buf_m = Rc::get_mut(&mut buf)
+                .expect("buf was just created, so there should be no other references");
+            let n = r.read(buf_m)?;
             if n == 0 {
                 break;
             }
-            rope = rope.concat(&Rope::leaf(&buf[..n]));
+            rope = rope.concat(&Rope::from_slice(buf, 0, n));
         }
         Ok(rope)
     }
 
     pub fn new(buf: &[u8]) -> Rope {
+        if buf.len() <= MAX_NODE_SIZE {
+            return Rope::leaf(Rc::from(buf));
+        }
         let mut buf = buf;
         Rope::read(&mut buf).expect("reading from a slice should never fail")
     }
@@ -333,7 +363,7 @@ impl Rope {
                 }))
             }
             Rope(Node::Branch(b)) => {
-                let mut s = Rope::new(&[]);
+                let mut s = Rope::empty();
                 let mut start = start;
                 let mut end = end;
                 for c in b.children.iter() {