aboutsummaryrefslogtreecommitdiffstats
path: root/src/rope.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/rope.rs')
-rw-r--r--src/rope.rs333
1 files changed, 133 insertions, 200 deletions
diff --git a/src/rope.rs b/src/rope.rs
index f78dd7f..ca057bd 100644
--- a/src/rope.rs
+++ b/src/rope.rs
@@ -1,4 +1,3 @@
-use std::fmt::{Display, Formatter};
use std::fs::File;
use std::io::{ErrorKind, Read, Write};
use std::path::Path;
@@ -7,220 +6,172 @@ use std::rc::Rc;
// Set to a small value to help identify bugs in the implementation.
const MAX_NODE_SIZE: usize = 4;
+#[derive(Debug, Clone)]
+struct Leaf {
+ buf: Rc<[u8]>,
+ start: u8,
+ end: u8,
+}
+
+impl Leaf {
+ fn bytes(&self) -> &[u8] {
+ return &self.buf[usize::from(self.start)..usize::from(self.end)];
+ }
+}
+
+#[derive(Debug, Clone)]
struct Branch {
- left: Rc<Node>,
- right: Rc<Node>,
+ left: Rc<Rope>,
+ right: Rc<Rope>,
len: usize,
// Number of newline characters under this branch.
lines: usize,
}
+#[derive(Debug, Clone)]
enum Node {
- Leaf(Vec<u8>),
+ Leaf(Leaf),
Branch(Branch),
}
-impl Node {
- fn write(&self, out: &mut Vec<u8>) {
- match self {
- Node::Leaf(v) => {
- out.extend(v);
- }
- Node::Branch(b) => {
- b.left.write(out);
- b.right.write(out);
- }
- }
- }
+#[derive(Debug, Clone)]
+pub struct Rope(Node);
- fn empty(&self) -> bool {
- return match self {
- Node::Leaf(v) => v.len() == 0,
- _ => false,
- };
+impl Rope {
+ fn leaf(buf: Vec<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"),
+ }));
}
- fn lines(&self) -> usize {
+ pub fn lines(&self) -> usize {
match self {
- Node::Leaf(v) => {
+ Rope(Node::Leaf(l)) => {
let mut count = 0;
- for &c in v {
+ for &c in l.bytes().iter() {
if c == b'\n' {
count += 1;
}
}
return count;
}
- Node::Branch(b) => {
+ Rope(Node::Branch(b)) => {
return b.lines;
}
}
}
- fn len(&self) -> usize {
+ pub fn len(&self) -> usize {
match self {
- Node::Leaf(v) => {
- return v.len();
+ Rope(Node::Leaf(l)) => {
+ return usize::from(l.end - l.start);
}
- Node::Branch(b) => {
+ Rope(Node::Branch(b)) => {
return b.len;
}
}
}
- fn print(&self, out: &mut dyn Write, start: usize, end: usize) -> Result<(), std::io::Error> {
+ pub fn print(&self, out: &mut dyn Write) -> Result<(), std::io::Error> {
// TODO: escape unprintable characters
match self {
- Node::Leaf(v) => {
- if let Err(err) = out.write_all(&v[start..end]) {
- return Err(err);
- }
+ Rope(Node::Leaf(l)) => {
+ out.write_all(l.bytes())?;
return Ok(());
}
- Node::Branch(b) => {
- let left_len = b.left.len();
- if start < left_len {
- if let Err(err) = b.left.print(out, start, std::cmp::min(left_len, end)) {
- return Err(err);
- }
- }
- if end > left_len {
- let mut right_start = 0;
- if start > left_len {
- right_start = start - left_len;
- }
- if let Err(err) = b.right.print(out, right_start, end - left_len) {
- return Err(err);
- }
- }
+ Rope(Node::Branch(b)) => {
+ b.left.print(out)?;
+ b.right.print(out)?;
return Ok(());
}
}
}
- fn line_idx(&self, n: usize) -> Option<usize> {
+ pub fn line_idx(&self, n: usize) -> usize {
+ if n > self.lines() {
+ panic!("Index {} out of range 0..{}", n, self.lines()+1);
+ }
if n == 0 {
- return Some(0);
+ return 0;
}
match self {
- Node::Leaf(v) => {
+ Rope(Node::Leaf(l)) => {
let mut nl_count = 0;
- for (i, &c) in v.iter().enumerate() {
+ for (i, &c) in l.bytes().iter().enumerate() {
if c != b'\n' {
continue;
}
nl_count += 1;
if nl_count == n {
- return Some(i + 1);
+ return i + 1;
}
}
- return None;
+ panic!("unreachable");
}
- Node::Branch(b) => {
+ Rope(Node::Branch(b)) => {
let left_lines = b.left.lines();
if n <= left_lines {
return b.left.line_idx(n);
}
- match b.right.line_idx(n - left_lines) {
- Some(i) => {
- return Some(b.left.len() + i);
- }
- None => {
- return None;
- }
- }
+ return b.left.len() + b.right.line_idx(n - left_lines);
}
}
}
- fn insert(&self, pos: usize, c: u8) -> Node {
+ fn concat(&self, other: &Rope) -> Rope {
+ if self.len() == 0 {
+ return other.clone();
+ }
+ if other.len() == 0 {
+ return self.clone();
+ }
+ let len = self.len() + other.len();
+ let lines = self.lines() + other.lines();
+ return Rope(Node::Branch(Branch {
+ left: Rc::new(self.clone()),
+ right: Rc::new(other.clone()),
+ len: len,
+ lines: lines,
+ }));
+ }
+
+ pub fn insert(&self, pos: usize, c: u8) -> Rope {
match self {
- Node::Leaf(v) => {
- if v.len() < MAX_NODE_SIZE {
- let mut new_buf = vec![0; v.len() + 1];
- new_buf[..pos].copy_from_slice(&v[..pos]);
+ Rope(Node::Leaf(l)) => {
+ if self.len() < MAX_NODE_SIZE {
+ let mut new_buf = vec![0; self.len() + 1];
+ new_buf[..pos].copy_from_slice(&l.bytes()[..pos]);
new_buf[pos] = c;
- new_buf[pos + 1..].copy_from_slice(&v[pos..]);
- return Node::Leaf(new_buf);
+ new_buf[pos + 1..].copy_from_slice(&l.bytes()[pos..]);
+ return Rope::leaf(new_buf);
}
let mut buf_left = vec![0; pos + 1];
- buf_left[..pos].copy_from_slice(&v[..pos]);
+ buf_left[..pos].copy_from_slice(&l.bytes()[..pos]);
buf_left[pos] = c;
let mut buf_right = Vec::new();
- buf_right.extend_from_slice(&v[pos..]);
- let mut lines = self.lines();
- if c == b'\n' {
- lines += 1;
- }
- return Node::Branch(Branch {
- left: Rc::new(Node::Leaf(buf_left)),
- right: Rc::new(Node::Leaf(buf_right)),
- len: v.len() + 1,
- lines: lines,
- });
+ buf_right.extend_from_slice(&l.bytes()[pos..]);
+ return Rope::leaf(buf_left).concat(&Rope::leaf(buf_right));
}
- Node::Branch(b) => {
- let mut lines = self.lines();
- if c == b'\n' {
- lines += 1;
- }
+ Rope(Node::Branch(b)) => {
if pos < b.left.len() {
- return Node::Branch(Branch {
- left: Rc::new(b.left.insert(pos, c)),
- right: b.right.clone(),
- len: b.len + 1,
- lines: lines,
- });
+ return b.left.insert(pos, c).concat(&b.right);
}
- return Node::Branch(Branch {
- left: b.left.clone(),
- right: Rc::new(b.right.insert(pos - b.left.len(), c)),
- len: b.len + 1,
- lines: lines,
- });
+ return b.left.concat(&b.right.insert(pos - b.left.len(), c));
}
}
}
-}
-
-impl Display for Node {
- fn fmt(&self, f: &mut Formatter) -> Result<(), std::fmt::Error> {
- let mut buf = Vec::new();
- self.write(&mut buf);
- return write!(f, "{}", String::from_utf8_lossy(&buf));
- }
-}
-
-#[derive(Clone)]
-pub struct Rope(Rc<Node>);
-
-impl Rope {
- fn concat(self, Rope(other): Rope) -> Rope {
- let Rope(me) = self;
- if me.empty() {
- return Rope(other);
- }
- if other.empty() {
- return Rope(me);
- }
- let len = me.len() + other.len();
- let lines = me.lines() + other.lines();
- return Rope(Rc::new(Node::Branch(Branch {
- left: me,
- right: other,
- len: len,
- lines: lines,
- })));
- }
pub fn open(path: &Path) -> Result<Rope, String> {
let mut f = match File::open(path) {
Ok(f) => f,
Err(err) => {
- return Err(format!("open: {}", err));
+ return Err(format!("open file {}: {}", path.display(), err));
}
};
- let mut rope = Rope(Rc::new(Node::Leaf(vec![])));
+ let mut rope = Rope::leaf(Vec::new());
loop {
let mut buf = vec![0; MAX_NODE_SIZE];
let n = match f.read(&mut buf) {
@@ -229,98 +180,80 @@ impl Rope {
if err.kind() == ErrorKind::Interrupted {
continue;
}
- return Err(format!("read: {}", err));
+ return Err(format!("read file {}: {}", path.display(), err));
}
};
if n == 0 {
break;
}
buf.truncate(n);
- rope = rope.concat(Rope(Rc::new(Node::Leaf(buf))));
+ rope = rope.concat(&Rope::leaf(buf));
}
// TODO: rebalance
return Ok(rope);
}
- pub fn save(&self, path: &Path) -> Result<(), std::io::Error> {
+ pub fn save(&self, path: &Path) -> Result<(), String> {
let mut f = match File::create(path) {
Ok(f) => f,
Err(err) => {
- return Err(err);
+ return Err(format!("save: create file {}: {}", path.display(), err));
}
};
- let Rope(me) = self;
- if let Err(err) = me.print(&mut f, 0, me.len()) {
- return Err(err);
+ if let Err(err) = self.print(&mut f) {
+ return Err(format!("save: write file {}: {}", path.display(), err));
}
if let Err(err) = f.sync_all() {
- return Err(err);
+ return Err(format!("save: write file {}: {}", path.display(), err));
}
return Ok(());
}
- pub fn len(&self) -> usize {
- let Rope(me) = self;
- return me.len();
- }
-
- pub fn lines(&self) -> usize {
- let Rope(me) = self;
- return me.lines();
- }
-
- pub fn line(&self, n: usize) -> Option<Slice> {
- let Rope(me) = self;
- let start = match me.line_idx(n) {
- Some(start) => start,
- None => {
- return None;
- }
- };
- match me.line_idx(n + 1) {
- Some(end) => {
- return Some(Slice {
- start: start,
- end: end - 1,
- buf: self.clone(),
- });
+ fn slice(&self, start: usize, end: usize) -> Rope {
+ if start >= self.len() {
+ panic!("Index {} out of range 0..{}", start, self.len());
+ }
+ if end > self.len() {
+ panic!("Index {} out of range 0..{}", end, self.len());
+ }
+ if start > end {
+ panic!("Slice start index {} is greater than end index {}", start, end);
+ }
+ match self {
+ Rope(Node::Leaf(l)) => {
+ return Rope(Node::Leaf(Leaf{
+ buf: l.buf.clone(),
+ start: u8::try_from(start).expect("buffer too long"),
+ end: u8::try_from(end).expect("buffer too long"),
+ }));
}
- None => {
- return Some(Slice {
- start: start,
- end: self.len(),
- buf: self.clone(),
- });
+ Rope(Node::Branch(b)) => {
+ let mut left = Rope::leaf(Vec::new());
+ if start < b.left.len() {
+ left = b.left.slice(start, std::cmp::min(end, b.left.len()));
+ }
+ let mut right = Rope::leaf(Vec::new());
+ if end > b.left.len() {
+ let mut left_start = 0;
+ if start > b.left.len() {
+ left_start = start - b.left.len();
+ }
+ right = b.right.slice(left_start, end - b.left.len());
+ }
+ return left.concat(&right);
}
}
}
-}
-
-impl Display for Rope {
- fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
- let Rope(n) = self;
- return write!(f, "{}", n);
- }
-}
-
-pub struct Slice {
- start: usize,
- end: usize,
- buf: Rope,
-}
-impl Slice {
- pub fn print(&self, out: &mut dyn Write) -> Result<(), std::io::Error> {
- let Rope(buf) = &self.buf;
- return buf.print(out, self.start, self.end);
- }
-
- pub fn len(&self) -> usize {
- return self.end - self.start;
- }
-
- pub fn insert(&self, pos: usize, c: u8) -> Rope {
- let Rope(buf) = &self.buf;
- return Rope(Rc::new(buf.insert(self.start + pos, c)));
+ 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);
+ }
+ return self.slice(start, end-1);
}
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 08:13:56 +0000