Ropes: share text chunks across immutable revisions

Last updated: 3 Oct 20269 min read

tutorial

A rope stores text in leaf chunks and stores the length of the left subtree at each internal node. An indexed lookup compares its offset with that left weight and descends to one leaf. Split divides a tree at an offset; joining the resulting parts with new nodes makes an edited root while unchanged subtrees remain shared with earlier roots. The example constructs a roughly balanced initial tree from short chunks, then implements insert and delete by split and join. It deliberately does not rebalance after edits. That omission matters: a run of joins can make the height proportional to the number of edits, and recursive split can eventually exhaust Python's call stack. The structure stores code-point lengths, not byte lengths or display columns.

Operational case

A saved maintenance note says Pump offline at bay 6. A revised root inserts the equipment number after Pump and removes offline, producing Pump-47 at bay 6. The saved root still renders the earlier wording because no leaf or internal node is changed in place. For a review tool that compares prior and current notes, retained roots are useful. They also retain memory: an old version remains reachable until its root is released. This small example shows the ownership contract, not a balanced production text engine with bounded height under arbitrary edits.

Working Python program

class RopeNode:
    def __init__(self, text=None, left=None, right=None):
        self.text = text
        self.left = left
        self.right = right
        self.weight = left.length if left else 0
        self.length = len(text) if text is not None else self.weight + right.length


def join(left, right):
    if left is None:
        return right
    if right is None:
        return left
    return RopeNode(left=left, right=right)


def build_rope(text, chunk_size=5):
    if chunk_size < 1:
        raise ValueError("chunk size must be positive")
    nodes = [RopeNode(text=text[offset:offset + chunk_size])
             for offset in range(0, len(text), chunk_size)]
    while len(nodes) > 1:
        nodes = [join(nodes[index], nodes[index + 1])
                 if index + 1 < len(nodes) else nodes[index]
                 for index in range(0, len(nodes), 2)]
    return nodes[0] if nodes else None


def split(node, index):
    if node is None:
        if index != 0:
            raise IndexError("split outside note")
        return None, None
    if not 0 <= index <= node.length:
        raise IndexError("split outside note")
    if index == 0:
        return None, node
    if index == node.length:
        return node, None
    if node.text is not None:
        return build_rope(node.text[:index]), build_rope(node.text[index:])
    if index < node.weight:
        prefix, suffix = split(node.left, index)
        return prefix, join(suffix, node.right)
    prefix, suffix = split(node.right, index - node.weight)
    return join(node.left, prefix), suffix


def insert(node, index, text):
    left, right = split(node, index)
    return join(join(left, build_rope(text)), right)


def delete(node, start, end):
    if node is None or not 0 <= start <= end <= node.length:
        raise IndexError("delete outside note")
    left, remainder = split(node, start)
    _, right = split(remainder, end - start)
    return join(left, right)


def character_at(node, index):
    if node is None or not 0 <= index < node.length:
        raise IndexError("character outside note")
    while node.text is None:
        if index < node.weight:
            node = node.left
        else:
            index -= node.weight
            node = node.right
    return node.text[index]


def flatten(node):
    if node is None:
        return ""
    chunks = []
    pending = [node]
    while pending:
        current = pending.pop()
        if current.text is not None:
            chunks.append(current.text)
        else:
            pending.extend((current.right, current.left))
    return "".join(chunks)


saved = build_rope("Pump offline at bay 6")
revised = insert(saved, 4, "-47")
revised = delete(revised, 8, 16)
print("saved=", flatten(saved), sep="")
print("revised=", flatten(revised), " first=", character_at(revised, 0), sep="")

Output

saved=Pump offline at bay 6
revised=Pump-47 at bay 6 first=P

Time, space, and tradeoff

A join allocates one internal node in O(1) time. Indexed character lookup follows tree height H and costs O(H). Split and edits visit O(H) nodes and may copy up to L characters when splitting a leaf of length L; inserting M new characters also creates O(M) character data. A fresh build of N characters costs O(N) time and space for chunking and tree nodes. Flattening any root costs O(N) time and output space. With no post-edit balancing, H can become O(E) after E repeated edits, so no logarithmic edit guarantee is claimed. Shared subtrees lower new allocation but retained snapshots keep their referenced chunks alive.

Common Mistakes

Do not mutate shared leaves after publishing a revision.
Do not claim constant-time arbitrary insertion from constant-time join.
Do not assume a balanced initial tree stays balanced after edits.
Do not confuse code-point offsets with byte offsets or grapheme boundaries.

Connected lessons

Compare its edit and lookup costs with Gap buffers: pay when the edit cursor crosses text, Unrolled lists: link small blocks instead of single items, Segmented arrays: locate blocks through cumulative lengths, then run the sequence audit and contract quiz.

data structures

range-query-structures