Rope

A rope is a representation of a long string as a binary tree whose leaves are ordinary strings and whose internal nodes stand for the concatenation of their two children. Each node caches the length of its left subtree, its weight, so a position in the text can be found by descending the tree. Concatenating two ropes creates a single node and copies no characters, and indexing, splitting, inserting and deleting at any position take time logarithmic in the length of a balanced rope, where a flat string needs time linear in its length for all but indexing. Ropes are usually immutable, so versions of a text share all unchanged parts, which gives cheap undo. Boehm, Atkinson and Plass described them in 1995, after their use in the Cedar environment at Xerox PARC^[1].

§ 01

Structure

A leaf holds a string. An internal node holds two ropes and the length of the left one; the text of a node is the text of its left child followed by that of its right child. The text of the whole rope is read from the leaves left to right:

A rope for "Hello_my_name_is_Simon". Each internal node shows its weight, the length of the text in its left subtree.

To find the character at position $i$ , start at the root: if $i$ is less than the weight go left, otherwise subtract the weight and go right. At a leaf, index the string directly. The time is proportional to the depth of the tree.

§ 02

Operations

Concatenation makes a new node with the two ropes as children. Splitting at position $i$ descends to the leaf containing $i$ , splits that leaf, and on the way back up combines the pieces to the left of the path into one rope and those to the right into another. Insertion and deletion are two splits and concatenations:

insert (r, i, s) = left (r, i) \cdot s \cdot right (r, i) delete (r, i, k) = left (r, i) \cdot right (r, i + k)

For a balanced rope of length $n$ , indexing, splitting, insertion and deletion take $O (lo g n)$ time, and concatenation $O (1)$ , or $O (lo g n)$ if the result is rebalanced. A flat string needs $O (n)$ for each of these except indexing.

A persistent rope in OCaml, tested against a flat string under 20,000 random insertions and deletions.

(* A rope: a binary tree whose leaves are strings. Each node caches the
   length of its left subtree (its weight), its total length and depth. *)
type t = Leaf of string | Node of { left : t; right : t; weight : int; len : int; depth : int }
 
let length = function Leaf s -> String.length s | Node n -> n.len
let depth = function Leaf _ -> 0 | Node n -> n.depth
 
let short = 64 (* leaves shorter than this are merged when concatenated *)
 
let node l r = Node { left = l; right = r; weight = length l; len = length l + length r; depth = 1 + max (depth l) (depth r) }
 
let concat a b =
  match (a, b) with
  | Leaf "", x | x, Leaf "" -> x
  | Leaf x, Leaf y when String.length x + String.length y <= short -> Leaf (x ^ y)
  | Node { left; right = Leaf y; _ }, Leaf z when String.length y + String.length z <= short -> node left (Leaf (y ^ z))
  | _ -> node a b
 
(* The character at position i: go left if i is below the weight. *)
let rec get r i = match r with Leaf s -> s.[i] | Node n -> if i < n.weight then get n.left i else get n.right (i - n.weight)
 
(* Split into the first i characters and the rest. *)
let rec split r i =
  match r with
  | Leaf s -> (Leaf (String.sub s 0 i), Leaf (String.sub s i (String.length s - i)))
  | Node n ->
      if i < n.weight then let a, b = split n.left i in (a, concat b n.right)
      else if i > n.weight then let a, b = split n.right (i - n.weight) in (concat n.left a, b)
      else (n.left, n.right)
 
let insert r i s = let a, b = split r i in concat (concat a (Leaf s)) b
let delete r i k = let a, b = split r i in let _, c = split b k in concat a c
 
let rec leaves r acc = match r with Leaf "" -> acc | Leaf s -> s :: acc | Node n -> leaves n.left (leaves n.right acc)
let to_string r = String.concat "" (leaves r [])
 
(* Rebuild as a balanced tree from the leaves. *)
let balance r =
  let a = Array.of_list (leaves r []) in
  let rec build lo hi = if hi - lo = 1 then Leaf a.(lo) else let mid = (lo + hi) / 2 in node (build lo mid) (build mid hi) in
  if Array.length a = 0 then Leaf "" else build 0 (Array.length a)
 
(* Boehm, Atkinson and Plass: a rope of depth d is balanced if its length
   is at least Fib (d + 2). *)
let fib = let a = Array.make 90 1 in for i = 2 to 89 do a.(i) <- a.(i - 1) + a.(i - 2) done; a
let is_balanced r = length r >= fib.(depth r + 2)

Running it.

after  5000 edits: length   9711, depth 13,  471 leaves, equal to the string: true, get agrees: true
after 10000 edits: length  18561, depth 18,  950 leaves, equal to the string: true, get agrees: true
after 15000 edits: length  27244, depth 19, 1303 leaves, equal to the string: true, get agrees: true
after 20000 edits: length  36543, depth 18, 1918 leaves, equal to the string: true, get agrees: true

Concatenating two short leaves copies them into one leaf, which keeps the tree from filling up with single characters: a rope's leaves should be short enough that copying one is cheap, and long enough that most of the text is in contiguous memory. Every edit copies only the nodes on the paths it touches, so the version before an edit remains intact, and an editor can keep every previous version for undo at a cost proportional to the edits^[7].

Balance

Repeated concatenation at one end produces a tree as deep as it is long. Boehm, Atkinson and Plass call a rope of depth $d$ balanced if its length is at least the Fibonacci number $F_{d + 2}$ , which bounds the depth by about $lo g_{φ} n \approx 1.44 lo g_{2} n$ , and rebuild a rope when an operation leaves it unbalanced^[1]:

balanced (r) ⟺ ∣ r ∣ \geq F_{depth (r) + 2}, F_{1} = F_{2} = 1

Their rebalancing inserts the leaves into an array of slots indexed by Fibonacci length, concatenating as it goes; the implementation above rebuilds a perfectly balanced tree from the leaves instead, which is simpler and has the same bound. Alternatively, a rope can be kept balanced at all times by storing it in a balanced tree such as a red-black tree or a B-tree, as most modern implementations do.

§ 03

Building strings

Building a long text by repeated appending is quadratic with immutable strings, since every append copies the text so far. A rope appends by creating a node:

Appending 100-byte pieces to a flat string and to a rope.

(* Building a text by appending pieces. With flat strings every append
   copies the whole text so far; with a rope an append creates one node. *)
let copied = ref 0
let string_append a b = copied := !copied + String.length a + String.length b; a ^ b
 
type t = Leaf of string | Node of t * t * int
let len = function Leaf s -> String.length s | Node (_, _, n) -> n
let rope_append a b = Node (a, b, len a + len b)

Running it.

  pieces    text size bytes copied (string)   nodes (rope)
    1000       100000             50050000           1000
    2000       200000            200100000           2000
    4000       400000            800200000           4000
    8000       800000           3200400000           8000

Doubling the number of pieces quadruples the bytes copied into strings, which reach 3.2 GB for an 800 kB text, while the rope creates one node per piece. Mutable buffers that grow by doubling, such as OCaml's Buffer and Java's StringBuilder, also make appending linear, but they do not help with insertions in the middle, and the result is not persistent. The appended rope here is a list leaning to one side and would need rebalancing before indexing.

§ 04

Text editors

An editor needs fast insertion and deletion at the cursor, fast access to any line, and, for undo, access to earlier versions. Three structures are common. A gap buffer keeps the text in one array with a gap at the cursor, so edits at the cursor are constant time and moving the cursor far costs a copy proportional to the distance; Emacs uses one^[3]. A piece table keeps the original file unchanged and a log of added text, and represents the document as a sequence of pieces pointing into the two^[4]; Visual Studio Code stores its pieces in a balanced tree^[8]. A rope stores the text itself in a balanced tree, and caches in each node not only lengths but other monoidal summaries such as the number of line breaks, so that the position of the $k$ th line is found by the same descent; the xi editor was built on this^[5].

A rope whose nodes cache a monoidal summary of their subtree is an instance of the same idea as the finger tree, which is parameterized by the monoid of measures^[6].

§ 05

History

Ropes were used in the Cedar programming environment at Xerox PARC in the 1980s, where the string type of the Cedar language was implemented as a tree of immutable pieces^[1]. Boehm, Atkinson and Plass described the data structure, its balance condition and its implementation, including a C version called cords, in 1995^[1]. A rope class was included in the SGI implementation of the C++ Standard Template Library^[2]. Ropes became common again in the 2010s as the text representation of editors, where their persistence suits undo and concurrent access to the text^[5].