Rope

Deep dive

How it works

In: a byte offset or line number, plus text to insert or a byte range to delete · Out: a new rope (the old one stays valid), or the byte offset of a line · State: an immutable tree: leaves hold at most N bytes of UTF-8, inner nodes hold two children and cached len, newlines and height · Cost: O(log n) per seek, split, join, insert or delete; O(1) clone

1. Metrics: every inner node stores the sum of its children's metrics (bytes, newlines). Any associative sum works, including chars or UTF-16 units (xi's "rope science" part 2).
2. Seek by byte: at each node go left if the offset is inside the left child's len, else subtract it and go right.
3. Seek by line: same descent on the newline count: line k starts after the k-th \n; inside a leaf, scan for it.
4. Join(a, b): two small leaves merge into one; if heights differ by more than 1, descend the taller tree's near edge and rotate on the way up (AVL join); else make a new node.
5. Split(i): descend to the leaf, cut it, and re-join the siblings on the way up: two ropes.
6. Insert(i, s): join(join(a, chunk(s)), b) after split(i). Delete(i..j): split at i and at j, drop the middle, join the ends.
7. Persistence: nodes are never mutated; the new rope reuses every subtree off the path, so the old root is a snapshot or an undo state.
8. Chunking: cut new text at char boundaries (and, for CRLF-aware ropes, never between \r and \n).

Code

use std::rc::Rc;

const LEAF: usize = 1024; // max bytes per leaf chunk

pub enum Node {
    Leaf(String),
    Inner { l: Rc<Node>, r: Rc<Node>, len: usize, nl: usize, h: u32 },
}
pub type Rope = Rc<Node>;
use Node::*;

pub fn len(n: &Node) -> usize { match n { Leaf(s) => s.len(), Inner { len, .. } => *len } }
fn nl(n: &Node) -> usize { match n { Leaf(s) => s.bytes().filter(|&b| b == b'\n').count(), Inner { nl, .. } => *nl } }
fn h(n: &Node) -> u32 { match n { Leaf(_) => 0, Inner { h, .. } => *h } }
fn node(l: Rope, r: Rope) -> Rope {
    Rc::new(Inner { len: len(&l) + len(&r), nl: nl(&l) + nl(&r), h: h(&l).max(h(&r)) + 1, l, r })
}

pub fn from_str(s: &str) -> Rope {
    let mut parts = Vec::new();
    let mut i = 0;
    while i < s.len() || parts.is_empty() {
        let mut j = (i + LEAF).min(s.len());
        while !s.is_char_boundary(j) { j -= 1; } // never cut a UTF-8 code point
        parts.push(Rc::new(Leaf(s[i..j].to_string())));
        i = j;
    }
    fn build(p: &[Rope]) -> Rope {
        if p.len() == 1 { return p[0].clone(); }
        join(build(&p[..p.len() / 2]), build(&p[p.len() / 2..]))
    }
    build(&parts)
}

// Concatenate, keeping the tree AVL-balanced: O(|height difference|).
pub fn join(a: Rope, b: Rope) -> Rope {
    if len(&a) == 0 { return b; }
    if len(&b) == 0 { return a; }
    if let (Leaf(x), Leaf(y)) = (&*a, &*b) {
        if x.len() + y.len() <= LEAF { return Rc::new(Leaf(format!("{x}{y}"))); }
    }
    let (ha, hb) = (h(&a), h(&b));
    if ha > hb + 1 { grow(a, b, false) } else if hb > ha + 1 { grow(b, a, true) } else { node(a, b) }
}
// `big` is the taller side; `flip` = big is the right operand. mk(x, y) puts x on the far side.
fn grow(big: Rope, small: Rope, flip: bool) -> Rope {
    let mk = |x: Rope, y: Rope| if flip { node(y, x) } else { node(x, y) };
    let kids = |n: &Rope| match &**n { Inner { l, r, .. } => if flip { (r.clone(), l.clone()) } else { (l.clone(), r.clone()) }, _ => unreachable!() };
    let (outer, inner) = kids(&big);
    let t = if flip { join(small, inner) } else { join(inner, small) };
    if h(&t) <= h(&outer) + 1 { return mk(outer, t); }
    let (c, d) = kids(&t); // t is two taller than outer: rotate
    if h(&c) <= h(&d) { mk(mk(outer, c), d) } else { let (c1, c2) = kids(&c); mk(mk(outer, c1), mk(c2, d)) }
}

pub fn split_at(n: &Rope, i: usize) -> (Rope, Rope) {
    match &**n {
        Leaf(s) => (Rc::new(Leaf(s[..i].to_string())), Rc::new(Leaf(s[i..].to_string()))),
        Inner { l, r, .. } if i <= len(l) => { let (a, b) = split_at(l, i); (a, join(b, r.clone())) }
        Inner { l, r, .. } => { let (a, b) = split_at(r, i - len(l)); (join(l.clone(), a), b) }
    }
}
pub fn insert(n: &Rope, at: usize, s: &str) -> Rope {
    let (a, b) = split_at(n, at);
    join(join(a, from_str(s)), b)
}
pub fn delete(n: &Rope, from: usize, to: usize) -> Rope {
    let (a, rest) = split_at(n, from);
    join(a, split_at(&rest, to - from).1)
}
// Byte offset where line `k` (0-based) starts: descend by cached newline counts.
pub fn line_to_byte(n: &Node, mut k: usize) -> Option<usize> {
    let (mut n, mut off) = (n, 0);
    while k > 0 {
        match n {
            Inner { l, .. } if nl(l) >= k => n = l,
            Inner { l, r, .. } => { k -= nl(l); off += len(l); n = r }
            Leaf(s) => return s.match_indices('\n').nth(k - 1).map(|(p, _)| off + p + 1),
        }
    }
    Some(off)
}
pub fn to_string(n: &Node, out: &mut String) {
    match n { Leaf(s) => out.push_str(s), Inner { l, r, .. } => { to_string(l, out); to_string(r, out) } }
}

fn main() {
    let mut x = 0x9E3779B97F4A7C15u64; // xorshift64
    let mut rnd = move |n: usize| { x ^= x << 13; x ^= x >> 7; x ^= x << 17; (x % n as u64) as usize };
    let alpha: Vec<char> = "ab \n\u{e9}\u{20ac}\u{1f600}".chars().collect();
    let mut model: String = (0..3000).map(|_| alpha[rnd(alpha.len())]).collect();
    let mut rp = from_str(&model);
    let (snap, snap_s) = (rp.clone(), model.clone()); // O(1) snapshot
    for _ in 0..600 {
        let mut at = rnd(model.len() + 1);
        while !model.is_char_boundary(at) { at -= 1; }
        if rnd(3) > 0 {
            let w: String = (0..rnd(2000)).map(|_| alpha[rnd(alpha.len())]).collect();
            model.insert_str(at, &w); rp = insert(&rp, at, &w);
        } else {
            let mut to = (at + rnd(2000)).min(model.len());
            while !model.is_char_boundary(to) { to -= 1; }
            model.replace_range(at..to, ""); rp = delete(&rp, at, to);
        }
        let mut s = String::new(); to_string(&rp, &mut s);
        assert_eq!(s, model);
    }
    let mut old = String::new(); to_string(&snap, &mut old);
    assert_eq!(old, snap_s); // the snapshot never changed
    let starts: Vec<usize> = std::iter::once(0).chain(model.match_indices('\n').map(|(p, _)| p + 1)).collect();
    for (k, &p) in starts.iter().enumerate() { assert_eq!(line_to_byte(&rp, k), Some(p)); }
    assert_eq!(line_to_byte(&rp, starts.len()), None);
    println!("ok: {} bytes, {} lines", model.len(), starts.len());
}

The test checks 600 random edits (1-4 byte characters) against a String, an early snapshot, and every line start. It counts only \n.

Complexity and constants

• 10 MB at 1 KB leaves is about 10^4 leaves; an AVL descent touches order of 15-20 nodes, each a possible cache miss.
• Per edit: one split (O(log n) new nodes), a few joins, one leaf copy of at most N bytes. Small leaves mean deep trees and pointer chasing; large leaves mean bigger memcpy per edit.
• Ropey reports about 10% memory overhead after loading a file.
• Measured on this Mac (Apple M4 Pro, rustc 1.99.1 -O): 10 MB built in 2-4 ms; line_to_byte 0.5-0.85 µs per lookup (1000 lookups, three runs).

Efficiency

• Cost: one 1-byte insert at a random offset of a 10 MB text, measured on this Mac (Apple M4 Pro): rope about 3.1 µs (3.2e5 inserts/s, 200,000 inserts), String::insert about 85 µs (1.2e4 inserts/s, 2,000 inserts). String pays a memmove of half the text (bandwidth-bound); the rope pays a few dozen pointer hops and a 1 KB copy (latency-bound). Snapshot: one reference-count increment.
• Levers:
  • B-tree fan-out 4-8 with child metadata stored in the parent — fewer levels and fewer cache misses than a binary tree (xi-rope uses 4-8 children; Ropey design notes) — large texts
  • build from chunks in one pass, not by repeated inserts — measured 2-4 ms for 10 MB with this code — loading a file
  • keep edits coherent (near each other) — Ropey reports 3.3 million vs 1.8 million insertions/s on its benchmark (README) — typing, multi-cursor batches
  • snapshot instead of copy — O(1) hand-off to a background thread (crop README) — analysis, saving
• Naive → standard → state of the art:
  • one contiguous String · memmove of about n/2 bytes per edit, 85 µs at 10 MB (measured)
  • gap buffer · O(1) near the gap, O(n) when the cursor jumps; weak for many cursors (Ropey design notes)
  • binary rope with AVL join (code above) · about 3 µs at 10 MB (measured)
  • B-tree rope, inline leaves (Ropey, crop, xi-rope) · edits of single-digit microseconds even on multi-gigabyte texts (Ropey README claim, not measured here)

Implementation notes

• Cache the metrics your callers seek by: bytes, newlines, and chars or UTF-16 units if APIs need them (Ropey converts between chars and UTF-16).
• Store child metrics in the parent in one array and inline leaf text in same-sized nodes, so a descent does not touch the children (Ropey design notes). The Rc-per-child layout above does the opposite, for clarity.
• Size a node plus its refcounts to a power of two (Ropey aims at 1024 bytes).
• Rebalance by a fixed rule: AVL height here, minimum B-tree fill in xi-rope (4 of 8 children) and Ropey.
• CRLF: Ropey keeps every leaf boundary off CRLF pairs, so line counting stays local to a leaf.

Pitfalls

• Splitting inside a UTF-8 sequence: panic in Rust, corrupt text elsewhere. Cut at is_char_boundary.
• A CRLF pair split across leaves breaks CR-aware line counting; VS Code's author calls CRLF in a tree "a programmer's nightmare".
• No coalescing of small leaves: after 200,000 one-byte inserts into the 10 MB text above, the rope had about 30,000 leaves, half under 256 bytes (measured), versus about 10,000 at load. Merge neighbours or rebuild occasionally.
• Reading a rope by repeated indexed lookups costs O(log n) each; iterate leaves instead.
• Rc is not Send: use Arc if snapshots cross threads (Ropey and crop do).
• An offset is valid only for the version it came from.

Variants and alternatives

In production

Zed (SumTree-based rope), Helix (Ropey, per Ropey's changelog), xi editor (xi-rope); VS Code uses a piece tree, a close relative.

Implementations

Sources

• Hans-J. Boehm, Russ Atkinson, Michael Plass, Ropes: an alternative to strings, Software: Practice and Experience 25(12), 1995, pp. 1315-1330. paper
• Raph Levien, Rope science series, parts 0-2 (xi editor docs). docs
• Ropey design document (B-tree rope, memory layout, invariants). design
• Peng Lyu, Text Buffer Reimplementation, VS Code blog, 2018. blog
• Thorsten Ball et al., Rope & SumTree, Zed blog, 2024. blog