Implement a rope data structure for text editing in Rust in this directory as a library…

claude-codeclaude-opus-4-7 · 72 steps · 8m 11s · 2 filessession 9098d0e2-e46@patrick-toulme
Implement a rope data structure for text editing in Rust in this directory as a library crate: Cargo.toml, src/lib.rs. The Rope supports building from a string, char-index insert and delete of arbitrary ranges, char_at, substring extraction, concat and split, and byte-accurate conversion back to String — balanced via node weights with leaves capped at 64 bytes, handling multi-byte UTF-8 correctly. Include #[cfg(test)] unit tests plus a property test performing 10_000 random seeded edit operations mirrored against a plain String, asserting equality after every op. Run cargo test and fix failures until everything passes.
step 72 / 72
src/lib.rschange 1/1
//! Rope data structure for text editing.
//!
//! Char-indexed insert/delete/substring over UTF-8 text, backed by a binary
//! tree with leaves capped at 64 bytes. Internal nodes carry the char-count
//! of their left subtree as the routing weight; balance is maintained by
//! rebuilding whenever tree depth grows past a log-of-length threshold.
 
use std::fmt;
 
const MAX_LEAF_BYTES: usize = 64;
 
#[derive(Clone, Debug, Default)]
pub struct Rope {
    root: Option<Box<Node>>,
}
 
#[derive(Clone, Debug)]
enum Node {
    Leaf(String),
    Internal {
        left: Box<Node>,
        right: Box<Node>,
        weight: usize,
        len: usize,
        depth: usize,
    },
}
 
impl Node {
    fn len_chars(&self) -> usize {
        match self {
            Node::Leaf(s) => s.chars().count(),
            Node::Internal { len, .. } => *len,
        }
    }
 
    fn depth(&self) -> usize {
        match self {
            Node::Leaf(_) => 0,
            Node::Internal { depth, .. } => *depth,
        }
    }
 
    fn byte_len(&self) -> usize {
        match self {
            Node::Leaf(s) => s.len(),
            Node::Internal { left, right, .. } => left.byte_len() + right.byte_len(),
        }
    }
 
    fn new_internal(left: Box<Node>, right: Box<Node>) -> Box<Node> {
        let weight = left.len_chars();
        let len = weight + right.len_chars();
        let depth = 1 + left.depth().max(right.depth());
        Box::new(Node::Internal { left, right, weight, len, depth })
    }
}
 
fn char_boundary(s: &str, char_idx: usize) -> usize {
    s.char_indices()
        .nth(char_idx)
        .map(|(i, _)| i)
        .unwrap_or(s.len())
}
 
fn build_from_str(s: &str) -> Option<Box<Node>> {
    if s.is_empty() {
        return None;
    }
    let chunks = split_into_chunks(s);
    build_balanced(&chunks)
}
 
fn split_into_chunks(s: &str) -> Vec<String> {
    let mut chunks: Vec<String> = Vec::new();
    let mut current = String::new();
    for c in s.chars() {
        let clen = c.len_utf8();
        if current.len() + clen > MAX_LEAF_BYTES && !current.is_empty() {
            chunks.push(std::mem::take(&mut current));
        }
        current.push(c);
    }
    if !current.is_empty() {
        chunks.push(current);
    }
    chunks
}
 
fn build_balanced(chunks: &[String]) -> Option<Box<Node>> {
    match chunks.len() {
        0 => None,
        1 => Some(Box::new(Node::Leaf(chunks[0].clone()))),
        n => {
            let mid = n / 2;
            let left = build_balanced(&chunks[..mid]).unwrap();
            let right = build_balanced(&chunks[mid..]).unwrap();
            Some(Node::new_internal(left, right))
        }
    }
}
 
fn char_at(node: &Node, idx: usize) -> Option<char> {
    match node {
        Node::Leaf(s) => s.chars().nth(idx),
        Node::Internal { left, right, weight, .. } => {
            if idx < *weight {
                char_at(left, idx)
            } else {
                char_at(right, idx - *weight)
            }
        }
    }
}
 
fn collect_substring(node: &Node, start: usize, end: usize, out: &mut String) {
    if start >= end {
        return;
    }
    match node {
        Node::Leaf(s) => {
            for (i, c) in s.chars().enumerate() {
                if i >= end {
                    break;
                }
                if i >= start {
                    out.push(c);
                }
            }
        }
        Node::Internal { left, right, weight, .. } => {
            if start < *weight {
                collect_substring(left, start, end.min(*weight), out);
            }
            if end > *weight {
                let rs = start.saturating_sub(*weight);
                let re = end - *weight;
                collect_substring(right, rs, re, out);
            }
        }
    }
}
 
fn append_to_string(node: &Node, out: &mut String) {
    match node {
        Node::Leaf(s) => out.push_str(s),
        Node::Internal { left, right, .. } => {
            append_to_string(left, out);
            append_to_string(right, out);
        }
    }
}
 
fn split_node(node: Box<Node>, idx: usize) -> (Option<Box<Node>>, Option<Box<Node>>) {
    let len = node.len_chars();
    if idx == 0 {
        return (None, Some(node));
    }
    if idx >= len {
        return (Some(node), None);
    }
    match *node {
        Node::Leaf(s) => {
            let byte_idx = char_boundary(&s, idx);
            let (left, right) = s.split_at(byte_idx);
            (
                Some(Box::new(Node::Leaf(left.to_string()))),
                Some(Box::new(Node::Leaf(right.to_string()))),
            )
        }
        Node::Internal { left, right, weight, .. } => {
            use std::cmp::Ordering;
            match idx.cmp(&weight) {
                Ordering::Less => {
                    let (ll, lr) = split_node(left, idx);
                    let right_combined = concat_nodes(lr, Some(right));
                    (ll, right_combined)
                }
                Ordering::Greater => {
                    let (rl, rr) = split_node(right, idx - weight);
                    let left_combined = concat_nodes(Some(left), rl);
                    (left_combined, rr)
                }
                Ordering::Equal => (Some(left), Some(right)),
            }
        }
    }
}
 
fn concat_nodes(left: Option<Box<Node>>, right: Option<Box<Node>>) -> Option<Box<Node>> {
    match (left, right) {
        (None, r) => r,
        (l, None) => l,
        (Some(l), Some(r)) => {
            if let (Node::Leaf(ls), Node::Leaf(rs)) = (l.as_ref(), r.as_ref()) {
                if ls.len() + rs.len() <= MAX_LEAF_BYTES {
                    let mut s = String::with_capacity(ls.len() + rs.len());
                    s.push_str(ls);
                    s.push_str(rs);
                    return Some(Box::new(Node::Leaf(s)));
                }
            }
            Some(Node::new_internal(l, r))
        }
    }
}
 
fn should_rebalance(node: &Node) -> bool {
    let d = node.depth();
    let len = node.len_chars();
    if len == 0 {
        return false;
    }
    // ceil(log2(len + 1))
    let log = (usize::BITS - len.leading_zeros()) as usize;
    d > 2 * log + 4
}
 
fn collect_leaves(node: Box<Node>, out: &mut Vec<String>) {
    match *node {
        Node::Leaf(s) => {
            if !s.is_empty() {
                out.push(s);
            }
        }
        Node::Internal { left, right, .. } => {
            collect_leaves(left, out);
            collect_leaves(right, out);
        }
    }
}
 
fn coalesce_leaves(leaves: Vec<String>) -> Vec<String> {
    let mut result: Vec<String> = Vec::new();
    let mut current = String::new();
    for leaf in leaves {
        for c in leaf.chars() {
            let clen = c.len_utf8();
            if current.len() + clen > MAX_LEAF_BYTES && !current.is_empty() {
                result.push(std::mem::take(&mut current));
            }
            current.push(c);
        }
    }
    if !current.is_empty() {
        result.push(current);
    }
    result
}
 
fn rebalance(node: Box<Node>) -> Box<Node> {
    let mut leaves = Vec::new();
    collect_leaves(node, &mut leaves);
    let merged = coalesce_leaves(leaves);
    build_balanced(&merged).expect("non-empty tree yields non-empty leaves")
}
 
fn maybe_rebalance(node: Box<Node>) -> Box<Node> {
    if should_rebalance(&node) {
        rebalance(node)
    } else {
        node
    }
}
 
impl Rope {
    pub fn new() -> Self {
        Rope { root: None }
    }
 
    pub fn from_str(s: &str) -> Self {
        Rope { root: build_from_str(s) }
    }
 
    pub fn len(&self) -> usize {
        self.root.as_ref().map(|n| n.len_chars()).unwrap_or(0)
    }
 
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }
 
    pub fn byte_len(&self) -> usize {
        self.root.as_ref().map(|n| n.byte_len()).unwrap_or(0)
    }
 
    pub fn char_at(&self, idx: usize) -> Option<char> {
        self.root.as_ref().and_then(|n| char_at(n, idx))
    }
 
    pub fn substring(&self, start: usize, end: usize) -> String {
        let len = self.len();
        assert!(start <= end, "start > end");
        assert!(end <= len, "end > len");
        let mut out = String::new();
        if let Some(ref r) = self.root {
            collect_substring(r, start, end, &mut out);
        }
        out
    }
 
    pub fn insert(&mut self, idx: usize, s: &str) {
        assert!(idx <= self.len(), "insert index out of bounds");
        if s.is_empty() {
            return;
        }
        let root = self.root.take();
        let (left, right) = match root {
            Some(r) => split_node(r, idx),
            None => (None, None),
        };
        let middle = build_from_str(s);
        let combined = concat_nodes(concat_nodes(left, middle), right);
        self.root = combined.map(maybe_rebalance);
    }
 
    pub fn delete(&mut self, start: usize, end: usize) {
        let len = self.len();
        assert!(start <= end, "start > end");
        assert!(end <= len, "end > len");
        if start == end {
            return;
        }
        let root = match self.root.take() {
            Some(r) => r,
            None => return,
        };
        let (left, rest) = split_node(root, start);
        let (_middle, right) = match rest {
            Some(r) => split_node(r, end - start),
            None => (None, None),
        };
        let combined = concat_nodes(left, right);
        self.root = combined.map(maybe_rebalance);
    }
 
    /// Consume `self` and `other`, returning a rope of their concatenation.
    pub fn concat(self, other: Rope) -> Rope {
        let combined = concat_nodes(self.root, other.root);
        Rope { root: combined.map(maybe_rebalance) }
    }
 
    /// Consume `self` and return two ropes: `[0, idx)` and `[idx, len)`.
    pub fn split(self, idx: usize) -> (Rope, Rope) {
        let len = self.len();
        assert!(idx <= len, "split index out of bounds");
        match self.root {
            None => (Rope::new(), Rope::new()),
            Some(r) => {
                let (l, rt) = split_node(r, idx);
                (Rope { root: l }, Rope { root: rt })
            }
        }
    }
 
    pub fn to_string(&self) -> String {
        let mut out = String::with_capacity(self.byte_len());
        if let Some(ref r) = self.root {
            append_to_string(r, &mut out);
        }
        out
    }
}
 
impl fmt::Display for Rope {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some(ref r) = self.root {
            fmt_node(r, f)?;
        }
        Ok(())
    }
}
 
fn fmt_node(node: &Node, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    match node {
        Node::Leaf(s) => f.write_str(s),
        Node::Internal { left, right, .. } => {
            fmt_node(left, f)?;
            fmt_node(right, f)
        }
    }
}
 
impl From<&str> for Rope {
    fn from(s: &str) -> Self {
        Rope::from_str(s)
    }
}
 
impl From<String> for Rope {
    fn from(s: String) -> Self {
        Rope::from_str(&s)
    }
}
 
// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------
 
#[cfg(test)]
mod tests {
    use super::*;
 
    fn char_byte_index(s: &str, char_idx: usize) -> usize {
        s.char_indices()
            .nth(char_idx)
            .map(|(i, _)| i)
            .unwrap_or(s.len())
    }
 
    #[test]
    fn empty_rope() {
        let r = Rope::new();
        assert_eq!(r.len(), 0);
        assert_eq!(r.byte_len(), 0);
        assert!(r.is_empty());
        assert_eq!(r.to_string(), "");
        assert_eq!(r.char_at(0), None);
        assert_eq!(r.substring(0, 0), "");
    }
 
    #[test]
    fn from_short_str() {
        let r = Rope::from_str("Hello, world!");
        assert_eq!(r.len(), 13);
        assert_eq!(r.byte_len(), 13);
        assert_eq!(r.to_string(), "Hello, world!");
        assert_eq!(r.char_at(0), Some('H'));
        assert_eq!(r.char_at(12), Some('!'));
        assert_eq!(r.char_at(13), None);
    }
 
    #[test]
    fn from_long_str_splits_into_leaves() {
        let s: String = "abcdefghij".repeat(50); // 500 bytes
        let r = Rope::from_str(&s);
        assert_eq!(r.len(), 500);
        assert_eq!(r.byte_len(), 500);
        assert_eq!(r.to_string(), s);
        // The tree should have multiple leaves — verify by checking a mid char.
        assert_eq!(r.char_at(250), Some('a'));
    }
 
    #[test]
    fn multibyte_utf8_roundtrip() {
        let s = "日本語テキスト🎉🎊 Hello — привет — مرحبا";
        let r = Rope::from_str(s);
        assert_eq!(r.len(), s.chars().count());
        assert_eq!(r.byte_len(), s.len());
        assert_eq!(r.to_string(), s);
        for (i, c) in s.chars().enumerate() {
            assert_eq!(r.char_at(i), Some(c), "mismatch at {}", i);
        }
    }
 
    #[test]
    fn insert_at_positions() {
        let mut r = Rope::from_str("Hello world");
        r.insert(5, ",");
        assert_eq!(r.to_string(), "Hello, world");
        r.insert(0, ">> ");
        assert_eq!(r.to_string(), ">> Hello, world");
        let end = r.len();
        r.insert(end, "!");
        assert_eq!(r.to_string(), ">> Hello, world!");
    }
 
    #[test]
    fn insert_multibyte() {
        let mut r = Rope::from_str("Hello!");
        r.insert(5, " 世界");
        assert_eq!(r.to_string(), "Hello 世界!");
        assert_eq!(r.len(), "Hello 世界!".chars().count());
    }
 
    #[test]
    fn delete_ranges() {
        let mut r = Rope::from_str("Hello, world!");
        r.delete(5, 7); // remove ", "
        assert_eq!(r.to_string(), "Helloworld!");
        r.delete(0, 5); // remove "Hello"
        assert_eq!(r.to_string(), "world!");
        let n = r.len();
        r.delete(n, n); // no-op
        assert_eq!(r.to_string(), "world!");
        r.delete(0, r.len());
        assert_eq!(r.to_string(), "");
        assert!(r.is_empty());
    }
 
    #[test]
    fn delete_across_leaves() {
        let s: String = "0123456789".repeat(20); // 200 chars, spans multiple leaves
        let mut r = Rope::from_str(&s);
        r.delete(30, 170);
        let mut expected = s.clone();
        expected.replace_range(30..170, "");
        assert_eq!(r.to_string(), expected);
        assert_eq!(r.len(), expected.chars().count());
    }
 
    #[test]
    fn substring_across_leaves() {
        let s: String = "0123456789".repeat(20);
        let r = Rope::from_str(&s);
        assert_eq!(r.substring(0, 0), "");
        assert_eq!(r.substring(5, 15), &s[5..15]);
        assert_eq!(r.substring(0, r.len()), s);
    }
 
    #[test]
    fn substring_multibyte() {
        let s = "αβγδε日本語🎉テスト";
        let r = Rope::from_str(s);
        let n = s.chars().count();
        for i in 0..=n {
            for j in i..=n {
                let bi = char_byte_index(s, i);
                let bj = char_byte_index(s, j);
                assert_eq!(r.substring(i, j), &s[bi..bj], "substring({}, {})", i, j);
            }
        }
    }
 
    #[test]
    fn concat_two_ropes() {
        let a = Rope::from_str("Hello, ");
        let b = Rope::from_str("world!");
        let c = a.concat(b);
        assert_eq!(c.to_string(), "Hello, world!");
        assert_eq!(c.len(), 13);
    }
 
    #[test]
    fn concat_with_empty() {
        let a = Rope::from_str("foo");
        let empty = Rope::new();
        let c = a.concat(empty);
        assert_eq!(c.to_string(), "foo");
 
        let empty2 = Rope::new();
        let b = Rope::from_str("bar");
        let c2 = empty2.concat(b);
        assert_eq!(c2.to_string(), "bar");
    }
 
    #[test]
    fn split_two_ropes() {
        let r = Rope::from_str("Hello, world!");
        let (a, b) = r.split(7);
        assert_eq!(a.to_string(), "Hello, ");
        assert_eq!(b.to_string(), "world!");
    }
 
    #[test]
    fn split_at_boundaries() {
        let r = Rope::from_str("abcdef");
        let (a, b) = r.clone().split(0);
        assert_eq!(a.to_string(), "");
        assert_eq!(b.to_string(), "abcdef");
        let (a, b) = r.split(6);
        assert_eq!(a.to_string(), "abcdef");
        assert_eq!(b.to_string(), "");
    }
 
    #[test]
    fn split_and_reconcat_multibyte() {
        let s = "abc日本語🎉ghi";
        let r = Rope::from_str(s);
        let n = r.len();
        for i in 0..=n {
            let (l, r2) = r.clone().split(i);
            let combined = l.concat(r2);
            assert_eq!(combined.to_string(), s, "split at {}", i);
        }
    }
 
    #[test]
    fn insert_and_delete_grow_and_shrink() {
        let mut r = Rope::new();
        for i in 0..200 {
            r.insert(r.len(), &format!("{} ", i));
        }
        let s = r.to_string();
        assert!(s.starts_with("0 1 2 3"));
        assert!(s.ends_with("198 199 "));
        assert_eq!(r.len(), s.chars().count());
        r.delete(0, r.len());
        assert_eq!(r.to_string(), "");
    }
 
    #[test]
    fn leaves_stay_within_cap() {
        // Build a rope and inspect that every leaf is at most MAX_LEAF_BYTES.
        let s: String = "The quick brown fox jumps over the lazy dog. ".repeat(30);
        let r = Rope::from_str(&s);
        check_leaf_cap(r.root.as_deref().unwrap());
    }
 
    fn check_leaf_cap(node: &Node) {
        match node {
            Node::Leaf(s) => assert!(s.len() <= MAX_LEAF_BYTES, "leaf too big: {}", s.len()),
            Node::Internal { left, right, .. } => {
                check_leaf_cap(left);
                check_leaf_cap(right);
            }
        }
    }
 
    // ---- Property test: random operations mirrored against String ------
 
    struct Rng {
        state: u64,
    }
    impl Rng {
        fn new(seed: u64) -> Self {
            Rng { state: seed | 1 } // avoid zero state
        }
        fn next_u64(&mut self) -> u64 {
            // splitmix64
            self.state = self.state.wrapping_add(0x9E3779B97F4A7C15);
            let mut z = self.state;
            z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
            z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
            z ^ (z >> 31)
        }
        fn range(&mut self, max_exclusive: usize) -> usize {
            if max_exclusive == 0 {
                return 0;
            }
            (self.next_u64() as usize) % max_exclusive
        }
        fn range_inclusive(&mut self, max_inclusive: usize) -> usize {
            self.range(max_inclusive + 1)
        }
    }
 
    #[test]
    fn property_random_edits_match_string() {
        let charset: &[char] = &[
            'a', 'b', 'c', 'd', 'e', ' ', '!', '\n', '日', '本', '🎉', 'ñ', 'ß',
        ];
        let mut rng = Rng::new(0xC0FFEE_BABE_1234);
        let mut rope = Rope::from_str("start");
        let mut expected = String::from("start");
 
        for iter in 0..10_000 {
            let len = expected.chars().count();
            // Bias so string self-regulates: prefer insert when short, delete when long.
            let op_pick = rng.range(100);
            let op = if len < 32 {
                // heavily favor insert
                match op_pick {
                    0..=59 => 0, // insert
                    60..=74 => 1, // delete
                    75..=87 => 2, // char_at
                    _ => 3,       // substring
                }
            } else if len > 512 {
                // favor delete
                match op_pick {
                    0..=19 => 0,
                    20..=74 => 1,
                    75..=87 => 2,
                    _ => 3,
                }
            } else {
                match op_pick {
                    0..=39 => 0,
                    40..=74 => 1,
                    75..=87 => 2,
                    _ => 3,
                }
            };
 
            match op {
                0 => {
                    let idx = rng.range_inclusive(len);
                    let n = 1 + rng.range(6);
                    let mut s = String::new();
                    for _ in 0..n {
                        s.push(charset[rng.range(charset.len())]);
                    }
                    rope.insert(idx, &s);
                    let bi = char_byte_index(&expected, idx);
                    expected.insert_str(bi, &s);
                }
                1 => {
                    if len == 0 {
                        continue;
                    }
                    let start = rng.range(len);
                    let end = start + rng.range_inclusive(len - start);
                    rope.delete(start, end);
                    let bs = char_byte_index(&expected, start);
                    let be = char_byte_index(&expected, end);
                    expected.replace_range(bs..be, "");
                }
                2 => {
                    if len == 0 {
                        assert_eq!(rope.char_at(0), None);
                    } else {
                        let idx = rng.range(len);
                        assert_eq!(
                            rope.char_at(idx),
                            expected.chars().nth(idx),
                            "char_at mismatch iter {} idx {}",
                            iter,
                            idx
                        );
                    }
                }
                3 => {
                    let start = rng.range_inclusive(len);
                    let end = start + rng.range_inclusive(len - start);
                    let got = rope.substring(start, end);
                    let bs = char_byte_index(&expected, start);
                    let be = char_byte_index(&expected, end);
                    let want = &expected[bs..be];
                    assert_eq!(got, want, "substring mismatch iter {} [{},{})", iter, start, end);
                }
                _ => unreachable!(),
            }
 
            // Assert full equality after every op.
            let rope_str = rope.to_string();
            assert_eq!(rope_str, expected, "roundtrip mismatch iter {}", iter);
            assert_eq!(
                rope.len(),
                expected.chars().count(),
                "len mismatch iter {}",
                iter
            );
            assert_eq!(
                rope.byte_len(),
                expected.len(),
                "byte_len mismatch iter {}",
                iter
            );
        }
    }
}
 
743 linesrs
I've completed the implementation but cannot run `cargo test` — every attempt is blocked wi…
Files at this step
drag the rail to scrub
Discussion

No comments yet. Start the discussion. Recorded by @patrick-toulme.
#claude #claude-code #claude-opus-4-7 #quick #rust #subagents #testing
s6-rope
← all sessions