Use a b-tree for the rope.

Now it's balanced :D

3 files changed, 352 insertions, 160 deletions

diff --git a/src/main.rs b/src/main.rs
index 6251ace..a4fe9ae 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -2,14 +2,22 @@ mod rope;
 mod term;
 
 use rope::Rope;
-use std::ffi::{OsStr, OsString};
-use std::io::{stdout, stdin, Write, Read};
 use std::error::Error;
+use std::ffi::{OsStr, OsString};
+use std::io::{stdin, stdout, Read, Write};
 use std::path::Path;
 use term::Key;
 
+#[derive(Debug, Clone, Copy)]
+enum Mode {
+    Insert,
+    Backspace,
+    Normal,
+}
+
 struct State {
     buf: Rope,
+    mode: Mode,
     row_start: usize,
     cursor_row: usize,
     cursor_col: usize,
@@ -25,25 +33,35 @@ fn parse_status_report(buf: &[u8]) -> Result<(usize, usize), Box<dyn Error>> {
             break;
         }
     }
-    if semicolon < 2 || semicolon == buf.len()-1 {
+    if semicolon < 2 || semicolon == buf.len() - 1 {
         return Err(Box::from("invalid response"));
     }
     let row_str = std::str::from_utf8(&buf[2..semicolon])?;
-    let col_str = std::str::from_utf8(&buf[semicolon+1..buf.len()-1])?;
+    let col_str = std::str::from_utf8(&buf[semicolon + 1..buf.len() - 1])?;
     let row = row_str.parse::<usize>()?;
     let col = col_str.parse::<usize>()?;
     // Yuck... 1 indexing
-    return Ok((row-1, col-1));
+    return Ok((row - 1, col - 1));
 }
 
 impl State {
     fn cursor_pos(&mut self) -> Result<(usize, usize), Box<dyn Error>> {
-        write!(stdout(), "\x1b[6n").map_err(|err| format!("cursor position: status report: {}", err))?;
-        stdout().flush().map_err(|err| format!("cursor position: status report: {}", err))?;
+        write!(stdout(), "\x1b[6n")
+            .map_err(|err| format!("cursor position: status report: {}", err))?;
+        stdout()
+            .flush()
+            .map_err(|err| format!("cursor position: status report: {}", err))?;
         let mut buf = vec![0; 20];
-        let n = stdin().read(&mut buf).map_err(|err| format!("cursor position: read status report: {}", err))?;
+        let n = stdin()
+            .read(&mut buf)
+            .map_err(|err| format!("cursor position: read status report: {}", err))?;
         buf.truncate(n);
-        let pos = parse_status_report(&buf).map_err(|_| format!("cursor position: invalid response: {}", String::from_utf8_lossy(&buf)))?;
+        let pos = parse_status_report(&buf).map_err(|_| {
+            format!(
+                "cursor position: invalid response: {}",
+                String::from_utf8_lossy(&buf)
+            )
+        })?;
         return Ok(pos);
     }
 
@@ -52,18 +70,17 @@ impl State {
         let mut stdout = stdout().lock();
 
         write!(stdout, "\x1b[H\x1b[J")?;
-        for i in self.row_start..self.row_start+usize::from(size.ws_row) {
+        for i in self.row_start..self.row_start + usize::from(size.ws_row) {
             if i > 0 {
                 write!(stdout, "\r\n")?;
             }
             if i > self.buf.lines() {
                 break;
             }
-            let line = self.buf.line(i);
-            let max_len = line.char(usize::from(size.ws_col-1));
-            line.slice(0, max_len).print(&mut stdout)?;
-            if max_len < line.len() {
-                write!(stdout, "\x1b[30m\x1b[47m>\x1b[m")?;
+            self.buf.line(i).print(&mut stdout)?;
+            let (_, col) = self.cursor_pos()?;
+            if col == usize::from(size.ws_col - 1) {
+                write!(stdout, "\x1b[{}G\x1b[30m\x1b[47m>\x1b[m ", size.ws_col - 1)?;
             }
         }
         return Ok(());
@@ -73,42 +90,31 @@ impl State {
         let term_size = term::size()?;
         let mut stdout = stdout().lock();
 
-        write!(stdout, "\x1b[{}H\x1b[K", self.cursor_row+1)?;
-        let mut line = self.buf.line(self.row_start+self.cursor_row);
-        let max_len = line.char(usize::from(term_size.ws_col-1));
-        let mut truncated = false;
-        if max_len < line.len() {
-            line = line.slice(0, max_len);
-            truncated = true;
-        }
+        write!(stdout, "\x1b[{}H\x1b[K", self.cursor_row + 1)?;
+        let line = self.buf.line(self.row_start + self.cursor_row);
 
         line.print(&mut stdout)?;
         let (_, col) = self.cursor_pos()?;
         self.line_cols = col;
+        let mut truncated = false;
+        if col == usize::from(term_size.ws_col - 1) {
+            truncated = true;
+            self.line_cols = col - 1;
+        }
         if self.cursor_col >= self.line_cols {
             self.line_offset = line.len();
             if truncated {
-                write!(stdout, "\x1b[30m\x1b[47m>\x1b[m\x1b[{}G", self.cursor_col+1)?;
-            }
-            return Ok(());
-        }
-
-        let offset_guess = line.char(self.cursor_col);
-        write!(stdout, "\x1b[G")?;
-        line.slice(0, offset_guess).print(&mut stdout)?;
-        let (_, col) = self.cursor_pos()?;
-        if col == self.cursor_col {
-            // One codepoint per column, like God intended.
-            self.line_offset = offset_guess;
-            line.slice(offset_guess, line.len()).print(&mut stdout)?;
-            if truncated {
-                write!(stdout, "\x1b[30m\x1b[47m>\x1b[m")?;
+                write!(
+                    stdout,
+                    "\x1b[{}G\x1b[30m\x1b[47m>\x1b[m \x1b[{}G",
+                    term_size.ws_col - 1,
+                    self.line_cols + 1,
+                )?;
             }
-            write!(stdout, "\x1b[{}G", self.cursor_col+1)?;
             return Ok(());
         }
 
-        let mut lo = offset_guess;
+        let mut lo = 0;
         let mut hi = line.len();
         // Binary search :D
         while hi > lo {
@@ -117,18 +123,22 @@ impl State {
             line.slice(0, x).print(&mut stdout)?;
             let (_, col) = self.cursor_pos()?;
             if col <= self.cursor_col {
-                lo = line.ceil_char_boundary(x+1);
+                lo = line.ceil_char_boundary(x + 1);
             } else {
                 hi = x;
             }
         }
-        self.line_offset = line.floor_char_boundary(lo-1);
+        self.line_offset = line.floor_char_boundary(lo - 1);
         write!(stdout, "\x1b[G")?;
         line.print(&mut stdout)?;
         if truncated {
-            write!(stdout, "\x1b[30m\x1b[47m>\x1b[m")?;
+            write!(
+                stdout,
+                "\x1b[{}G\x1b[30m\x1b[47m>\x1b[m ",
+                term_size.ws_col - 1
+            )?;
         }
-        write!(stdout, "\x1b[{}G", self.cursor_col+1)?;
+        write!(stdout, "\x1b[{}G", self.cursor_col + 1)?;
         return Ok(());
     }
 
@@ -147,7 +157,7 @@ impl State {
     }
 
     fn down(&mut self) -> Result<(), Box<dyn Error>> {
-        if self.row_start+self.cursor_row == self.buf.lines() {
+        if self.row_start + self.cursor_row == self.buf.lines() {
             return Ok(());
         }
         let size = term::size()?;
@@ -179,10 +189,6 @@ impl State {
     }
 
     fn right(&mut self) -> Result<(), Box<dyn Error>> {
-        let size = term::size()?;
-        if self.cursor_col >= self.line_cols && self.cursor_row == usize::from(size.ws_row-1) {
-            return Ok(());
-        }
         if self.cursor_col >= self.line_cols {
             self.down()?;
             self.cursor_col = 0;
@@ -192,15 +198,30 @@ impl State {
         self.repaint_line_full()?;
         return Ok(());
     }
-}
 
+    fn set_mode(&mut self, mode: Mode) {
+        match (self.mode, mode) {
+            (Mode::Insert, Mode::Insert) => (),
+            (Mode::Insert, _) => {
+                if let Ok((_, col)) = self.cursor_pos() {
+                    self.cursor_col = col;
+                }
+                let _ = self.repaint_line_full();
+            }
+            _ => (),
+        }
+        self.mode = mode;
+    }
+}
 fn edit(file: &OsStr) -> Result<(), Box<dyn Error>> {
-    let _raw_handle = term::raw().map_err(|err| format!("cannot put terminal in raw mode: {}", err))?;
+    let _raw_handle =
+        term::raw().map_err(|err| format!("cannot put terminal in raw mode: {}", err))?;
 
     let r = Rope::open(Path::new(file))?;
     let size = term::size()?;
-    let mut state = State{
+    let mut state = State {
         buf: r,
+        mode: Mode::Normal,
         row_start: 0,
         cursor_row: 0,
         cursor_col: 0,
@@ -212,38 +233,48 @@ fn edit(file: &OsStr) -> Result<(), Box<dyn Error>> {
     let _ = stdout().flush();
 
     loop {
-        let c = term::read_key(&mut stdin()).map_err(|err| format!("read key: {}", err))?;
+        let c = term::read_key().map_err(|err| format!("read key: {}", err))?;
         match c {
             Key::CtrlQ => {
                 break;
             }
             Key::CtrlS => {
+                state.set_mode(Mode::Normal);
                 let _ = state.buf.save(Path::new(file));
             }
             Key::Up => {
+                state.set_mode(Mode::Normal);
                 let _ = state.up();
                 let _ = stdout().flush();
             }
             Key::Down => {
+                state.set_mode(Mode::Normal);
                 let _ = state.down();
                 let _ = stdout().flush();
             }
             Key::Left => {
+                state.set_mode(Mode::Normal);
                 let _ = state.left();
                 let _ = stdout().flush();
             }
             Key::Right => {
+                state.set_mode(Mode::Normal);
                 let _ = state.right();
                 let _ = stdout().flush();
             }
             Key::Backspace => {
+                state.set_mode(Mode::Backspace);
                 if state.row_start == 0 && state.cursor_row == 0 && state.cursor_col == 0 {
                     continue;
                 }
-                let offset = state.buf.line_idx(state.row_start+state.cursor_row)+state.line_offset;
+                let offset =
+                    state.buf.line_idx(state.row_start + state.cursor_row) + state.line_offset;
                 let need_refresh_all = state.cursor_col == 0;
                 let _ = state.left();
-                state.buf = state.buf.slice(0, state.buf.floor_char_boundary(offset-1)).concat(&state.buf.slice(offset, state.buf.len()));
+                state.buf = state
+                    .buf
+                    .slice(0, state.buf.floor_char_boundary(offset - 1))
+                    .concat(&state.buf.slice(offset, state.buf.len()));
                 if need_refresh_all {
                     let _ = state.repaint_all();
                 }
@@ -251,7 +282,11 @@ fn edit(file: &OsStr) -> Result<(), Box<dyn Error>> {
                 let _ = stdout().flush();
             }
             Key::Char(b'\r') => {
-                state.buf = state.buf.insert(state.buf.line_idx(state.row_start+state.cursor_row)+state.line_offset, b'\n');
+                state.set_mode(Mode::Insert);
+                state.buf = state.buf.insert(
+                    state.buf.line_idx(state.row_start + state.cursor_row) + state.line_offset,
+                    b'\n',
+                );
                 if state.cursor_row == usize::from(size.ws_row - 1) {
                     state.row_start += 1;
                 } else {
@@ -263,10 +298,14 @@ fn edit(file: &OsStr) -> Result<(), Box<dyn Error>> {
                 let _ = stdout().flush();
             }
             Key::Char(c) => {
+                state.set_mode(Mode::Insert);
                 state.cursor_col = std::cmp::min(state.cursor_col, state.line_cols);
-                state.buf = state.buf.insert(state.buf.line_idx(state.row_start+state.cursor_row)+state.line_offset, c);
-                state.cursor_col += 1;
-                let _ = state.repaint_line_full();
+                state.buf = state.buf.insert(
+                    state.buf.line_idx(state.row_start + state.cursor_row) + state.line_offset,
+                    c,
+                );
+                state.line_offset += 1;
+                let _ = stdout().write_all(&vec![c]);
                 let _ = stdout().flush();
             }
         }
diff --git a/src/rope.rs b/src/rope.rs
index 34c459b..6c1cad6 100644
--- a/src/rope.rs
+++ b/src/rope.rs
@@ -1,10 +1,10 @@
+use std::error::Error;
 use std::fs::File;
 use std::io::{ErrorKind, Read, Write};
 use std::path::Path;
-use std::error::Error;
 use std::rc::Rc;
 
-const MAX_NODE_SIZE: usize = 254;
+const MAX_NODE_SIZE: usize = 255;
 
 #[derive(Debug, Clone)]
 struct Leaf {
@@ -21,32 +21,103 @@ impl Leaf {
 
 #[derive(Debug, Clone)]
 struct Branch {
-    left: Rc<Rope>,
-    right: Rc<Rope>,
     len: usize,
     // Number of newline characters under this branch.
     lines: usize,
+    height: usize,
+    child1: Rope,
+    child2: Rope,
+    child3: Option<Rope>,
+}
+
+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);
+    }
 }
 
 #[derive(Debug, Clone)]
 enum Node {
     Leaf(Leaf),
-    Branch(Branch),
+    Branch(Rc<Branch>),
 }
 
 #[derive(Debug, Clone)]
 pub struct Rope(Node);
 
-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 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"),
+    }));
+}
+
+// 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");
+    }
+    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)) => {
@@ -75,6 +146,13 @@ impl Rope {
         }
     }
 
+    pub fn height(&self) -> usize {
+        match self {
+            Rope(Node::Leaf(_)) => 0,
+            Rope(Node::Branch(b)) => b.height,
+        }
+    }
+
     pub fn print(&self, out: &mut dyn Write) -> Result<(), std::io::Error> {
         if self.len() == 0 {
             return Ok(());
@@ -86,8 +164,9 @@ impl Rope {
                 return Ok(());
             }
             Rope(Node::Branch(b)) => {
-                b.left.print(out)?;
-                b.right.print(out)?;
+                for child in b.children() {
+                    child.print(out)?;
+                }
                 return Ok(());
             }
         }
@@ -95,7 +174,7 @@ impl Rope {
 
     pub fn line_idx(&self, n: usize) -> usize {
         if n > self.lines() {
-            panic!("Index {} out of range 0..{}", n, self.lines()+1);
+            panic!("Index {} out of range 0..{}", n, self.lines() + 1);
         }
         if n == 0 {
             return 0;
@@ -115,111 +194,191 @@ impl Rope {
                 panic!("unreachable");
             }
             Rope(Node::Branch(b)) => {
-                let left_lines = b.left.lines();
-                if n <= left_lines {
-                    return b.left.line_idx(n);
+                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);
+                    }
+                    offset += child.len();
+                    n -= child_lines;
                 }
-                return b.left.len() + b.right.line_idx(n - left_lines);
+                panic!("unreachable");
             }
         }
     }
 
-    pub fn concat(&self, other: &Rope) -> Rope {
+    fn try_concat(&self, other: &Rope) -> Insert {
         if self.len() == 0 {
-            return other.clone();
+            return Insert::Node(other.clone());
         }
         if other.len() == 0 {
-            return self.clone();
+            return Insert::Node(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 {
-        return self.slice(0, pos).concat(&Rope::leaf(vec![c])).concat(&self.slice(pos, self.len()));
-    }
-
-    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 = 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 {
-                        continue;
+        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());
+                let mut buf1 = Vec::new();
+                buf1.extend_from_slice(&buf[..buf.len() / 2]);
+                let mut buf2 = Vec::new();
+                buf2.extend_from_slice(&buf[buf.len() / 2..]);
+                return Insert::Split(leaf(buf1), leaf(buf2));
+            }
+        }
+        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))
                     }
-                    return Err(Box::from(format!("read file {}: {}", path.display(), err)));
-                }
+                    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");
             };
-            if n == 0 {
-                break;
+            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))
+                    }
+                },
             }
-            buf.truncate(n);
-            rope = rope.concat(&Rope::leaf(buf));
         }
-        // TODO: rebalance
-        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 concat(&self, other: &Rope) -> Rope {
+        match self.try_concat(other) {
+            Insert::Node(r) => r,
+            Insert::Split(l, r) => two(&l, &r),
+        }
+    }
+
+    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 slice(&self, start: usize, end: usize) -> Rope {
         if start > self.len() {
-            panic!("Index {} out of range 0..{}", start, self.len()+1);
+            panic!("Index {} out of range 0..{}", start, self.len() + 1);
         }
         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);
+            panic!(
+                "Slice start index {} is greater than end index {}",
+                start, end
+            );
         }
         match self {
             Rope(Node::Leaf(l)) => {
-                return Rope(Node::Leaf(Leaf{
+                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::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 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();
                 }
-                let mut right = Rope::leaf(Vec::new());
-                if end > b.left.len() {
-                    let mut right_start = 0;
-                    if start > b.left.len() {
-                        right_start = start - b.left.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 {
+                        continue;
                     }
-                    right = b.right.slice(right_start, end - b.left.len());
+                    return Err(Box::from(format!("read file {}: {}", path.display(), err)));
                 }
-                return left.concat(&right);
+            };
+            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);
+            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;
+            end = self.line_idx(n + 1) - 1;
         }
         return self.slice(start, end);
     }
@@ -230,16 +389,20 @@ impl Rope {
                 return l.bytes()[index] & 0xc0 != 0x80;
             }
             Rope(Node::Branch(b)) => {
-                if index < b.left.len() {
-                    return b.left.is_char_boundary(index);
+                let mut index = index;
+                for child in b.children() {
+                    if index < child.len() {
+                        return child.is_char_boundary(index);
+                    }
+                    index -= child.len();
                 }
-                return b.right.is_char_boundary(index - b.left.len());
+                return false;
             }
         }
     }
 
     pub fn floor_char_boundary(&self, index: usize) -> usize {
-        for i in (0..index+1).rev() {
+        for i in (0..index + 1).rev() {
             if self.is_char_boundary(i) {
                 return i;
             }
@@ -255,21 +418,4 @@ impl Rope {
         }
         return self.len();
     }
-
-    pub fn char(&self, index: usize) -> usize {
-        if index == 0 {
-            return 0;
-        }
-        let mut count = 1;
-        for i in 1..self.len() {
-            if !self.is_char_boundary(i) {
-                continue;
-            }
-            if count == index {
-                return i;
-            }
-            count += 1;
-        }
-        return self.len();
-    }
 }
diff --git a/src/term.rs b/src/term.rs
index 8f44b23..9c7e2cc 100644
--- a/src/term.rs
+++ b/src/term.rs
@@ -1,13 +1,16 @@
 use libc::{termios, winsize};
 use std::error::Error;
-use std::io::{Read, Stdin};
+use std::io::{stdin, stdout, Read, Write};
 
 pub fn size() -> Result<winsize, Box<dyn Error>> {
     unsafe {
         let mut window: winsize = std::mem::zeroed();
         let status = libc::ioctl(1, libc::TIOCGWINSZ, &mut window);
         if status < 0 {
-            return Err(Box::from(format!("terminal size: ioctl failed with code {}", status)));
+            return Err(Box::from(format!(
+                "terminal size: ioctl failed with code {}",
+                status
+            )));
         }
         return Ok(window);
     }
@@ -48,11 +51,15 @@ pub struct RawHandle {
 
 impl Drop for RawHandle {
     fn drop(&mut self) {
+        let _ = write!(stdout(), "\x1b[?7h");
+        let _ = stdout().flush();
         let _ = set_attr(&self.old);
     }
 }
 
 pub fn raw() -> Result<RawHandle, Box<dyn Error>> {
+    write!(stdout(), "\x1b[?7l")?;
+    stdout().flush()?;
     let old = get_attr()?;
     set_attr(&make_raw())?;
     return Ok(RawHandle { old: old });
@@ -69,7 +76,7 @@ pub enum Key {
     Char(u8),
 }
 
-pub fn read_key(stdin: &mut Stdin) -> Result<Key, Box<dyn Error>> {
+pub fn read_key() -> Result<Key, Box<dyn Error>> {
     const CTRL_Q: u8 = 17;
     const CTRL_S: u8 = 19;
     const BACKSPACE: u8 = 127;
@@ -77,7 +84,7 @@ pub fn read_key(stdin: &mut Stdin) -> Result<Key, Box<dyn Error>> {
 
     loop {
         let mut buf = vec![0; 1];
-        stdin.read_exact(&mut buf)?;
+        stdin().read_exact(&mut buf)?;
         if buf[0] == CTRL_Q {
             return Ok(Key::CtrlQ);
         }
@@ -92,7 +99,7 @@ pub fn read_key(stdin: &mut Stdin) -> Result<Key, Box<dyn Error>> {
         }
         // Try to handle an escape sequence.
         let mut buf = vec![0; 2];
-        stdin.read_exact(&mut buf)?;
+        stdin().read_exact(&mut buf)?;
         if buf[0] != b'[' {
             // Unknown escape sequence, just read another key.
             continue;