aboutsummaryrefslogtreecommitdiffstats
path: root/src/rope.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/rope.rs')
-rw-r--r--src/rope.rs559
1 files changed, 250 insertions, 309 deletions
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<Rc<[u8]>>,
+ 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<Rope>,
+ 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<Self::Item> {
- 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<Rope, std::io::Error> {
+ 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<Rope, Box<dyn Error>> {
- 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<dyn Error>> {
- 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();
}
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 14:48:15 +0000