From f50c6f210a353d8b12552f6a20bf58c2a7bdd3df Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Fri, 5 Jan 2024 19:13:48 -0800 Subject: Clean up the rope code. --- src/main.rs | 22 ++-- src/rope.rs | 333 ++++++++++++++++++++++++------------------------------------ 2 files changed, 139 insertions(+), 216 deletions(-) diff --git a/src/main.rs b/src/main.rs index d376c2d..2b359f8 100644 --- a/src/main.rs +++ b/src/main.rs @@ -38,12 +38,10 @@ fn edit(file: &OsStr) -> Result<(), String> { if i > 0 { let _ = stdout.write(b"\r\n"); } - let line = match r.line(i) { - Some(line) => line, - None => { - break; - } - }; + if i > r.lines() { + break; + } + let line = r.line(i); // TODO: handle line-wrapping. let _ = line.print(&mut stdout); } @@ -78,7 +76,6 @@ fn edit(file: &OsStr) -> Result<(), String> { let len = r .line(cursor_row) - .expect("cursor_row should always be valid") .len(); if cursor_col > len { move_cursor(&mut stdout, cursor_row, len); @@ -94,7 +91,6 @@ fn edit(file: &OsStr) -> Result<(), String> { let len = r .line(cursor_row) - .expect("cursor_row should always be valid") .len(); if cursor_col > len { move_cursor(&mut stdout, cursor_row, len); @@ -105,7 +101,6 @@ fn edit(file: &OsStr) -> Result<(), String> { Key::Left => { let len = r .line(cursor_row) - .expect("cursor_row should always be valid") .len(); cursor_col = std::cmp::min(cursor_col, len); if cursor_col == 0 { @@ -117,7 +112,6 @@ fn edit(file: &OsStr) -> Result<(), String> { Key::Right => { let len = r .line(cursor_row) - .expect("cursor_row should always be valid") .len(); if cursor_col >= len { continue; @@ -126,15 +120,11 @@ fn edit(file: &OsStr) -> Result<(), String> { move_cursor(&mut stdout, cursor_row, cursor_col); } Key::Char(c) => { - let line = r - .line(cursor_row) - .expect("cursor_row should always be valid"); - cursor_col = std::cmp::min(cursor_col, line.len()); - r = line.insert(cursor_col, c); + cursor_col = std::cmp::min(cursor_col, r.line(cursor_row).len()); + r = r.insert(r.line_idx(cursor_row)+cursor_col, c); move_cursor(&mut stdout, cursor_row, 0); let _ = r .line(cursor_row) - .expect("cursor_row should always be valid") .print(&mut stdout); cursor_col += 1; move_cursor(&mut stdout, cursor_row, cursor_col); 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, - right: Rc, + left: Rc, + right: Rc, len: usize, // Number of newline characters under this branch. lines: usize, } +#[derive(Debug, Clone)] enum Node { - Leaf(Vec), + Leaf(Leaf), Branch(Branch), } -impl Node { - fn write(&self, out: &mut Vec) { - 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) -> 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 { + 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); - -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 { 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 { - 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); } } -- cgit v1.3.1