From db087d43659f0760a02d6c32dc7dc0baf2f914f0 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Thu, 11 Jan 2024 00:20:11 -0800 Subject: Rewrite the entire thing. They say you can always do a better job on the rewrite, and to a certain extent that was true here. I kept a lot of it the same though, since there was a lot I liked from the original design. The main improvements are in efficiency and code clarity. --- src/rope.rs | 559 +++++++++++++++++++++++++++--------------------------------- 1 file changed, 250 insertions(+), 309 deletions(-) (limited to 'src/rope.rs') diff --git a/src/rope.rs b/src/rope.rs index 60a3fe8..31c3296 100644 --- a/src/rope.rs +++ b/src/rope.rs @@ -1,66 +1,40 @@ -use std::error::Error; -use std::fs::File; -use std::io::{ErrorKind, Read, Write}; -use std::path::Path; +use std::io::{Read, Write}; use std::rc::Rc; -const MAX_NODE_SIZE: usize = 255; +const MAX_NODE_SIZE: usize = 1024; + +enum Insert { + Node(Rope), + Split(Rope, Rope), +} #[derive(Debug, Clone)] -struct Leaf { - buf: Rc<[u8]>, - start: u8, - end: u8, +pub struct Leaf { + unsafe_buf: Option>, + start: u16, + end: u16, } impl Leaf { fn bytes(&self) -> &[u8] { - return &self.buf[usize::from(self.start)..usize::from(self.end)]; + match &self.unsafe_buf { + None => &[], + Some(buf) => &buf[usize::from(self.start)..usize::from(self.end)], + } } } #[derive(Debug, Clone)] -struct Branch { +pub struct Branch { + unsafe_children: [Rope; 3], len: usize, - // Number of newline characters under this branch. lines: usize, - height: usize, - child1: Rope, - child2: Rope, - child3: Option, + n_children: u8, } impl Branch { - fn children(&self) -> Children { - return Children { b: self, i: 0 }; - } -} - -#[derive(Debug, Clone, Copy)] -struct Children<'a> { - b: &'a Branch, - i: u8, -} - -impl<'a> Iterator for Children<'a> { - type Item = Rope; - - fn next(&mut self) -> Option { - let c = match self.i { - 0 => self.b.child1.clone(), - 1 => self.b.child2.clone(), - 2 => match &self.b.child3 { - Some(child3) => child3.clone(), - None => { - return None; - } - }, - _ => { - return None; - } - }; - self.i += 1; - return Some(c); + fn children(&self) -> &[Rope] { + &self.unsafe_children[..usize::from(self.n_children)] } } @@ -73,345 +47,312 @@ enum Node { #[derive(Debug, Clone)] pub struct Rope(Node); -fn leaf(buf: &[u8]) -> Rope { - let len = buf.len(); - return Rope(Node::Leaf(Leaf { - buf: Rc::from(buf), - start: 0, - end: u8::try_from(len).expect("buffer too long"), - })); -} - -// The two and three constructors maintain the size of the tree. -fn two(l: &Rope, r: &Rope) -> Rope { - if l.height() != r.height() { - panic!("Joining trees of different height"); - } - return Rope(Node::Branch(Rc::new(Branch { - len: l.len() + r.len(), - lines: l.lines() + r.lines(), - height: l.height() + 1, - child1: l.clone(), - child2: r.clone(), - child3: None, - }))); -} - -fn three(a: &Rope, b: &Rope, c: &Rope) -> Rope { - if a.height() != b.height() || b.height() != c.height() { - panic!("Joining trees of different height"); +impl Rope { + pub fn len(&self) -> usize { + match self { + Rope(Node::Leaf(l)) => l.bytes().len(), + Rope(Node::Branch(b)) => b.len, + } } - return Rope(Node::Branch(Rc::new(Branch { - len: a.len() + b.len() + c.len(), - lines: a.lines() + b.lines() + c.lines(), - height: a.height() + 1, - child1: a.clone(), - child2: b.clone(), - child3: Some(c.clone()), - }))); -} -#[derive(Debug)] -enum Insert { - Node(Rope), - Split(Rope, Rope), -} - -impl Rope { pub fn lines(&self) -> usize { match self { Rope(Node::Leaf(l)) => { - let mut count = 0; - for &c in l.bytes().iter() { - if c == b'\n' { - count += 1; + let mut lines = 0; + for &b in l.bytes().iter() { + if b == b'\n' { + lines += 1; } } - return count; - } - Rope(Node::Branch(b)) => { - return b.lines; + lines } + Rope(Node::Branch(b)) => b.lines, } } - pub fn len(&self) -> usize { - match self { - Rope(Node::Leaf(l)) => { - return usize::from(l.end - l.start); + 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, + })); + } + Rope(Node::Leaf(Leaf { + unsafe_buf: Some(Rc::from(buf)), + start: 0, + end: u16::try_from(buf.len()).expect("I just checked the length, it should be ok"), + })) + } + + fn branch(children: &[Rope]) -> Rope { + let mut len = 0; + let mut lines = 0; + for c in children.iter() { + 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, + 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 { + 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)); } - Rope(Node::Branch(b)) => { - return b.len; + 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..]), + ); + } + return Insert::Split(self.clone(), other.clone()); + } + if self_height == other_height { + return Insert::Split(self.clone(), other.clone()); + } + if self_height > other_height { + 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( + 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; + return Insert::Node(Rope::branch(&new_children)); + } + Insert::Split(child1, child2) => { + if b.children().len() == 2 { + return Insert::Node(Rope::branch(&[ + b.children()[0].clone(), + child1, + child2, + ])); + } + return Insert::Split( + Rope::branch(&[b.children()[0].clone(), b.children()[1].clone()]), + Rope::branch(&[child1, child2]), + ); + } + } + } + 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) { + Insert::Node(new_child) => { + 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()])); + } + Insert::Split( + Rope::branch(&[child1, child2]), + Rope::branch(&[b.children()[1].clone(), b.children()[2].clone()]), + ) } } } - pub fn height(&self) -> usize { + fn height(&self) -> usize { match self { Rope(Node::Leaf(_)) => 0, - Rope(Node::Branch(b)) => b.height, + Rope(Node::Branch(b)) => 1 + b.children()[0].height(), } } - pub fn print(&self, out: &mut dyn Write) -> Result<(), std::io::Error> { + pub fn concat(&self, other: &Rope) -> Rope { if self.len() == 0 { - return Ok(()); + return other.clone(); + } + if other.len() == 0 { + return self.clone(); } - // TODO: escape unprintable characters + match self.concat_height(self.height(), other, other.height()) { + Insert::Node(r) => r, + Insert::Split(l, r) => Rope::branch(&[l, r]), + } + } + + pub fn read(r: &mut dyn Read) -> Result { + let mut buf = vec![0; MAX_NODE_SIZE]; + let mut rope = Rope::leaf(&[]); + loop { + let n = r.read(&mut buf)?; + if n == 0 { + break; + } + rope = rope.concat(&Rope::leaf(&buf[..n])); + } + Ok(rope) + } + + pub fn new(buf: &[u8]) -> Rope { + let mut buf = buf; + Rope::read(&mut buf).expect("reading from a slice should never fail") + } + + fn is_char_boundary(&self, i: usize) -> bool { match self { Rope(Node::Leaf(l)) => { - out.write_all(l.bytes())?; - return Ok(()); + return i < l.bytes().len() && l.bytes()[i] & 0xc0 != 0x80; } Rope(Node::Branch(b)) => { - for child in b.children() { - child.print(out)?; + let mut i = i; + for c in b.children().iter() { + if i < c.len() { + return c.is_char_boundary(i); + } + i -= c.len(); } - return Ok(()); + false } } } - pub fn line_idx(&self, n: usize) -> usize { - if n > self.lines() { - panic!("Index {} out of range 0..{}", n, self.lines() + 1); + pub fn floor_char_boundary(&self, i: usize) -> usize { + for i in (0..i + 1).rev() { + if self.is_char_boundary(i) { + return i; + } } - if n == 0 { - return 0; + 0 + } + + pub fn ceil_char_boundary(&self, i: usize) -> usize { + for i in i..self.len() { + if self.is_char_boundary(i) { + return i; + } } + self.len() + } + + fn line_end(&self, n: usize) -> usize { match self { Rope(Node::Leaf(l)) => { - let mut nl_count = 0; + let mut count = 0; for (i, &c) in l.bytes().iter().enumerate() { if c != b'\n' { continue; } - nl_count += 1; - if nl_count == n { - return i + 1; + if count == n { + return i; } + count += 1; } - panic!("unreachable"); } Rope(Node::Branch(b)) => { - let mut offset = 0; let mut n = n; - for child in b.children() { - let child_lines = child.lines(); - if n <= child_lines { - return offset + child.line_idx(n); + let mut offset = 0; + for c in b.children().iter() { + if n < c.lines() { + return offset + c.line_end(n); } - offset += child.len(); - n -= child_lines; + n -= c.lines(); + offset += c.len(); } - panic!("unreachable"); } } + self.len() } - fn try_concat(&self, other: &Rope) -> Insert { - if self.len() == 0 { - return Insert::Node(other.clone()); - } - if other.len() == 0 { - return Insert::Node(self.clone()); - } - if let (Rope(Node::Leaf(l)), Rope(Node::Leaf(r))) = (self, other) { - if self.len() <= MAX_NODE_SIZE - other.len() { - let mut buf = Vec::new(); - buf.extend_from_slice(&l.bytes()); - buf.extend_from_slice(&r.bytes()); - return Insert::Node(leaf(&buf)); - } - if self.len() < MAX_NODE_SIZE / 2 || other.len() < MAX_NODE_SIZE / 2 { - let mut buf = Vec::new(); - buf.extend_from_slice(&l.bytes()); - buf.extend_from_slice(&r.bytes()); - return Insert::Split(leaf(&buf[..buf.len() / 2]), leaf(&buf[buf.len() / 2..])); - } - } - if self.height() == other.height() { - return Insert::Split(self.clone(), other.clone()); - } - if self.height() > other.height() { - let Rope(Node::Branch(selfb)) = self else { - panic!("self should have height at least one, which means it's a branch"); - }; - match &selfb.child3 { - Some(child3) => match child3.try_concat(other) { - Insert::Node(new_child) => { - Insert::Node(three(&selfb.child1, &selfb.child2, &new_child)) - } - Insert::Split(child1, child2) => { - Insert::Split(two(&selfb.child1, &selfb.child2), two(&child1, &child2)) - } - }, - None => match selfb.child2.try_concat(other) { - Insert::Node(new_child) => Insert::Node(two(&selfb.child1, &new_child)), - Insert::Split(child1, child2) => { - Insert::Node(three(&selfb.child1, &child1, &child2)) - } - }, - } - } else { - let Rope(Node::Branch(otherb)) = other else { - panic!("other should have height at least one, which means it's a branch"); - }; - match &otherb.child3 { - Some(child3) => match self.try_concat(&otherb.child1) { - Insert::Node(new_child) => { - Insert::Node(three(&new_child, &otherb.child2, &child3)) - } - Insert::Split(child1, child2) => { - Insert::Split(two(&child1, &child2), two(&otherb.child2, &child3)) - } - }, - None => match self.try_concat(&otherb.child1) { - Insert::Node(new_child) => Insert::Node(two(&new_child, &otherb.child2)), - Insert::Split(child1, child2) => { - Insert::Node(three(&child1, &child2, &otherb.child2)) - } - }, - } + pub fn line_start(&self, n: usize) -> usize { + if n == 0 { + return 0; } + self.line_end(n - 1) + 1 } - pub fn concat(&self, other: &Rope) -> Rope { - match self.try_concat(other) { - Insert::Node(r) => r, - Insert::Split(l, r) => two(&l, &r), - } + pub fn line(&self, n: usize) -> Rope { + self.slice(self.line_start(n), self.line_end(n)).clone() } - pub fn insert(&self, pos: usize, c: u8) -> Rope { - let res = self - .slice(0, pos) - .concat(&leaf(&vec![c])) - .concat(&self.slice(pos, self.len())); - return res; + pub fn print(&self, w: &mut dyn Write) -> Result<(), std::io::Error> { + match self { + Rope(Node::Leaf(l)) => { + w.write_all(l.bytes())?; + Ok(()) + } + Rope(Node::Branch(b)) => { + for c in b.children().iter() { + c.print(w)?; + } + Ok(()) + } + } } pub fn slice(&self, start: usize, end: usize) -> Rope { if start > self.len() { - panic!("Index {} out of range 0..{}", start, self.len() + 1); + panic!( + "Slice start index {} out of range 0..={}", + start, + self.len() + ); } if end > self.len() { - panic!("Index {} out of range 0..{}", end, self.len()); + panic!("Slice end index {} out of range 0..={}", end, self.len()); } if start > end { - panic!( - "Slice start index {} is greater than end index {}", - start, end - ); + panic!("Slice start index {} greater than end index {}", start, end); + } + if start == 0 && end == self.len() { + return self.clone(); } match self { Rope(Node::Leaf(l)) => { - return Rope(Node::Leaf(Leaf { - buf: l.buf.clone(), - start: l.start + u8::try_from(start).expect("buffer too long"), - end: l.start + u8::try_from(end).expect("buffer too long"), - })); + Rope(Node::Leaf(Leaf{ + unsafe_buf: l.unsafe_buf.clone(), + start: l.start+u16::try_from(start).expect("index.start should be less than MAX_NODE_SIZE since self is a leaf"), + end: l.start+u16::try_from(end).expect("index.end should be less than or equal to MAX_NODE_SIZE since self is a leaf"), + })) } Rope(Node::Branch(b)) => { + let mut s = Rope::new(&[]); let mut start = start; let mut end = end; - let mut slice = leaf(&Vec::new()); - for child in b.children() { - if start < child.len() { - slice = slice.concat(&child.slice(start, std::cmp::min(end, child.len()))); - if end < child.len() { - break; - } - start = 0; - } else { - start -= child.len(); - } - end -= child.len(); - } - return slice; - } - } - } - - pub fn open(path: &Path) -> Result> { - let mut f = - File::open(path).map_err(|err| format!("open file {}: {}", path.display(), err))?; - let mut rope = leaf(&Vec::new()); - loop { - let mut buf = vec![0; MAX_NODE_SIZE]; - let n = match f.read(&mut buf) { - Ok(n) => n, - Err(err) => { - if err.kind() == ErrorKind::Interrupted { + for c in b.children().iter() { + if start >= c.len() { + start -= c.len(); + end -= c.len(); continue; } - return Err(Box::from(format!("read file {}: {}", path.display(), err))); - } - }; - if n == 0 { - break; - } - buf.truncate(n); - rope = rope.concat(&leaf(&buf)); - } - return Ok(rope); - } - - pub fn save(&self, path: &Path) -> Result<(), Box> { - let mut f = File::create(path) - .map_err(|err| format!("save: create file {}: {}", path.display(), err))?; - self.print(&mut f) - .map_err(|err| format!("save: write file {}: {}", path.display(), err))?; - f.sync_all() - .map_err(|err| format!("save: write file {}: {}", path.display(), err))?; - return Ok(()); - } - - pub fn line(&self, n: usize) -> Rope { - if n > self.lines() { - panic!("Index {} out of range 0..{}", n, self.lines() + 1); - } - let start = self.line_idx(n); - let mut end = self.len(); - if n < self.lines() { - end = self.line_idx(n + 1) - 1; - } - return self.slice(start, end); - } - - fn is_char_boundary(&self, index: usize) -> bool { - match self { - Rope(Node::Leaf(l)) => { - return l.bytes()[index] & 0xc0 != 0x80; - } - Rope(Node::Branch(b)) => { - let mut index = index; - for child in b.children() { - if index < child.len() { - return child.is_char_boundary(index); + s = s.concat(&c.slice(start, std::cmp::min(end, c.len()))); + if end <= c.len() { + break; } - index -= child.len(); + start = 0; + end -= c.len(); } - return false; - } - } - } - - pub fn floor_char_boundary(&self, index: usize) -> usize { - for i in (0..index + 1).rev() { - if self.is_char_boundary(i) { - return i; - } - } - panic!("I'm not valid UTF-8: {:?}", self); - } - - pub fn ceil_char_boundary(&self, index: usize) -> usize { - for i in index..self.len() { - if self.is_char_boundary(i) { - return i; + s } } - return self.len(); } } -- cgit v1.3.1