Rope, in depth: weighted trees for big mutable text, split and concat, Fibonacci balancing, B-tree ropes with line and UTF-16 metrics, and structural sharing for undo

The model: leaves, concatenation nodes and weights

Every rope node is either a leaf, holding a short immutable string, or a concatenation node with a left and right child. The text a node represents is the in-order concatenation of its leaves. Each internal node also stores a weight: the total length of its left subtree. That one integer is what turns a tree of fragments into a searchable sequence.

Take the 19-character string The_quick_brown_fox split into four leaves of lengths 4, 6, 6 and 3. The left internal node A covers The_quick_ and stores weight 4; the right node B covers brown_fox and stores weight 6; the root stores weight 10 because its left subtree holds 10 characters. To find character 12, start at the root: 12 is not less than 10, so subtract 10 and go right with i = 2. At B, 2 is less than 6, so go left into the leaf brown_ and read position 2, which is o. Counting directly in The_quick_brown_fox confirms index 12 is the o of brown.

Leaves are kept small but not tiny: a few hundred bytes to a few kilobytes amortises per-node overhead and keeps the tree shallow. One-character leaves waste memory; megabyte leaves bring back the O(n) insertion cost.

Split and concat: the two primitives

Two primitives carry the whole data structure. concat(a, b) makes a new node with weight len(a): constant time, and nothing is copied. split(r, i) walks the same path as indexing and, at each level, peels off the side that lies wholly before or after position i, reattaching it to one of the two results. Everything else is a composition: insert is split, then two concats; delete is two splits and one concat; substring is two splits.

from dataclasses import dataclass

LEAF_MAX = 64          # real ropes use hundreds to thousands of bytes

@dataclass(frozen=True)
class Leaf:
    s: str
    def __len__(self): return len(self.s)

@dataclass(frozen=True)
class Node:
    left: object
    right: object
    weight: int        # len(left)
    length: int        # len(left) + len(right)
    depth: int
    def __len__(self): return self.length

def depth(r): return r.depth if isinstance(r, Node) else 0

def concat(a, b):
    if len(a) == 0: return b
    if len(b) == 0: return a
    if isinstance(a, Leaf) and isinstance(b, Leaf) and len(a) + len(b) <= LEAF_MAX:
        return Leaf(a.s + b.s)                      # merge small neighbours
    return Node(a, b, len(a), len(a) + len(b), 1 + max(depth(a), depth(b)))

def index(r, i):
    while isinstance(r, Node):
        if i < r.weight: r = r.left
        else: i -= r.weight; r = r.right
    return r.s[i]

def split(r, i):
    """Return (r[:i], r[i:]); untouched subtrees are shared, not copied."""
    if isinstance(r, Leaf):
        return Leaf(r.s[:i]), Leaf(r.s[i:])
    if i < r.weight:
        a, b = split(r.left, i)
        return a, concat(b, r.right)
    a, b = split(r.right, i - r.weight)
    return concat(r.left, a), b

def insert(r, i, s):
    a, b = split(r, i)
    return concat(concat(a, Leaf(s)), b)

def delete(r, i, j):
    a, rest = split(r, i)
    _, c = split(rest, j - i)
    return concat(a, c)

def to_str(r):
    out, stack = [], [r]
    while stack:
        n = stack.pop()
        if isinstance(n, Leaf): out.append(n.s)
        else: stack += [n.right, n.left]
    return "".join(out)

Nodes are immutable: split builds new nodes along one path and reuses every untouched subtree, which makes old versions free to keep. And concat merges small neighbouring leaves, so typing does not create thousands of one-character leaves.

Walk through the example (build it with LEAF_MAX = 4 so the four short leaves stay separate instead of being merged). split(rope, 7) on The_quick_brown_fox: 7 is less than the root weight 10, so recurse left; at A, 7 is not less than 4, so recurse right into the leaf quick_ at offset 3, giving qui and ck_. Unwinding, the left result is The_qui and the right is ck_ concatenated with the untouched node B, i.e. ck_brown_fox. insert(rope, 4, "very_") splits at 4 (exactly at a leaf boundary, so one side of the split leaf is empty) and produces The_very_quick_brown_fox.

Cost model against a flat string

A rope trades slower reads and scans for asymptotic wins on middle edits and cheap snapshots; for small, mostly-read or append-only text, a plain string wins.

Keeping it balanced

All of those O(log n) bounds assume the tree stays shallow, and nothing in concat guarantees that. Appending one character at a time to the end makes the tree degenerate into a long chain; a long run of such appends can degrade indexing to O(n). Boehm, Atkinson and Plass used a balance criterion based on Fibonacci numbers: with F(1) = F(2) = 1, a rope of depth d is balanced if its length is at least F(d + 2). The depth of a balanced rope is therefore logarithmic in its length, because Fibonacci numbers grow exponentially.

Rebalancing is lazy. Operations check depth against a threshold and, only when it is exceeded, rebuild. The rebuild walks the leaves left to right and inserts each into an array of slots, where slot k holds a balanced rope whose length lies in [F(k), F(k+1)). Inserting a leaf concatenates it with the contents of lower slots until its length fits a free slot; at the end, the slots are concatenated from smallest to largest. The result is balanced and the work is linear in the number of leaves, which amortises well because rebuilds are rare.

def rebalance(r):
    leaves = []
    stack = [r]
    while stack:
        n = stack.pop()
        if isinstance(n, Leaf):
            if len(n): leaves.append(n)
        else:
            stack += [n.right, n.left]
    # simplest correct version: build a perfectly balanced tree from the leaf list
    def build(lo, hi):
        if hi - lo == 1: return leaves[lo]
        mid = (lo + hi) // 2
        return concat(build(lo, mid), build(mid, hi))
    return build(0, len(leaves)) if leaves else Leaf("")

MAX_DEPTH = 48
def maybe_rebalance(r):
    return rebalance(r) if depth(r) > MAX_DEPTH else r

This version skips the Fibonacci slots and rebuilds a perfectly balanced tree from the leaf list: same asymptotic cost, easier to verify. Many production ropes sidestep the issue with a B-tree.

B-tree ropes and summarised metrics

Real editors rarely ship the binary rope from the paper. They use a B-tree rope: internal nodes have many children (often 8 to 64), leaves hold a chunk of bytes, and the tree is kept balanced by the usual B-tree split and merge rules, so depth stays tiny even for gigabyte files. The Rust crate Ropey and the rope in the xi-editor project are both B-tree ropes, and Zed's rope is built on its own B-tree-like "sum tree".

The more important change is what each node summarises. An editor does not only ask for character 1,000,000; it asks for line 4,812, for the byte offset of a cursor, for the UTF-16 column the language server reported, for the grapheme boundary before the cursor. So each node stores a small vector of metrics for its subtree instead of one weight:

• bytes - for slicing the underlying UTF-8 storage;
• chars (Unicode scalar values) - for character-indexed APIs;
• line breaks - so line-to-offset and offset-to-line are O(log n);
• UTF-16 code units - because LSP positions are expressed in UTF-16 by default and many JavaScript-facing APIs count that way.

Any query that can be expressed as "find the leaf where the running total of metric M crosses x" becomes the same descent as index, using the chosen metric instead of length. A metric qualifies if a node's summary can be computed from its children's summaries alone, with an associative combine; byte, char and line counts are sums, so they do.

One operational trap follows directly: leaf boundaries must not split a UTF-8 multi-byte sequence, and ideally not a CRLF pair, or the per-leaf counts will disagree with the counts of the concatenated text. Snap every chunk boundary to a valid position when leaves are split or merged.

Structural sharing: undo and snapshots

Because nodes are immutable, an edit returns a new root that shares almost everything with the old one. An undo stack can therefore be a list of roots. Each entry costs only the O(log n) new nodes the edit created, not a copy of the document. The same property gives you consistent snapshots for background work: a syntax highlighter, a search, or a save-to-disk thread can hold the root it started with and read it while the user keeps typing, with no locking and no torn reads.

history = [Leaf("")]                      # list of roots
def apply(edit):
    root = edit(history[-1])
    history.append(maybe_rebalance(root))

apply(lambda r: insert(r, 0, "hello world"))
apply(lambda r: delete(r, 5, 11))         # "hello"
snapshot = history[-1]                    # hand to a background thread
history.pop()                             # undo: back to "hello world"

The price: in Rust or C++ shared nodes usually mean reference counting, a measurable cost on hot paths, and unbounded history grows with total editing rather than document size, so cap it.

Failure modes

• Degenerate depth. Repeated appends or prepends without rebalancing make a linked list. Symptom: indexing slows as the session ages. Fix: depth-triggered rebalance or a B-tree.
• Leaf explosion. Every keystroke creates a one-character leaf. Symptom: memory per document many times the text size. Fix: merge small neighbours in concat and coalesce typing runs before applying them.
• Unit confusion. Mixing byte, char and UTF-16 offsets. Symptom: cursor drifts or a diagnostic underlines the wrong span only on lines containing emoji or CJK text. Fix: name each offset type distinctly and convert only through the rope's metric queries.
• Split inside a code point or CRLF. Symptom: line counts off by one, or a panic on slicing. Fix: snap chunk boundaries to valid positions.
• Slow scans. Regex search over the rope by repeated index calls is O(n log n) with terrible constants. Fix: iterate leaf chunks and feed a streaming matcher.

Testing a rope

The best test for a rope is differential: apply the same random inserts and deletes to the rope and to a plain Python string, and compare after every step. It catches off-by-one errors at leaf boundaries that hand-picked unit tests miss.

import random
def fuzz(steps=5000, seed=0):
    rng = random.Random(seed)
    r, s = Leaf(""), ""
    for _ in range(steps):
        op = rng.random()
        if op < 0.6 or not s:
            i = rng.randint(0, len(s))
            t = "".join(rng.choice("ab\n") for _ in range(rng.randint(1, 9)))
            r, s = insert(r, i, t), s[:i] + t + s[i:]
        else:
            i = rng.randint(0, len(s) - 1); j = rng.randint(i, len(s))
            r, s = delete(r, i, j), s[:i] + s[j:]
        r = maybe_rebalance(r)
        assert len(r) == len(s) and to_str(r) == s
        if s:
            k = rng.randrange(len(s)); assert index(r, k) == s[k]

Run it with several seeds and a tiny LEAF_MAX such as 4 to force boundary cases.

Choosing between rope, gap buffer and piece table

A practical rule: if your editor needs concurrent readers, line and UTF-16 lookups and multiple cursors on files of tens of megabytes, use a B-tree rope with summarised metrics. If you want the smallest change from a flat buffer for a simple single-cursor editor, a gap buffer is hard to beat. The piece table sits between them and is covered in detail in Piece Table, in depth. For the persistence idea used in the undo section, see persistent data structures; for other ways to keep a sequence tree balanced, compare splay trees and treaps, both of which can implement an implicit-key sequence with split and merge.

What to do next

1. Type in the rope code and reproduce the worked example: index 12, split at 7, insert at 4.
2. Run the differential fuzz test with LEAF_MAX = 4 and three seeds; then break split on purpose and confirm the test catches it.
3. Add a newline-count metric to Node and implement line_to_offset as a descent.
4. Measure: insert 100,000 random characters into a 10 MB text with a Python str and with the rope, and plot time per operation.
5. Before building your own, read the API of an existing B-tree rope such as Ropey and decide which metrics your application actually needs.