Ropes: An Alternative to Strings🔗ℹ

1 Introduction🔗ℹ

Racket strings are immutable, fixed-length vectors of characters. That makes them cheap to read and share, but expensive to edit. Inserting a character in the middle of a string of length n means allocating and copying a new string of length n, because substring and string-append both have to walk the whole thing. A text editor that repeatedly inserts and deletes characters in a large buffer this way pays O(n) per keystroke, and O(n2) (or worse) over the course of editing the whole document.

Ropes solve this by representing a long sequence as a balanced binary tree of short chunks rather than as a flat array. Each leaf holds a chunk small enough to slice or copy cheaply. Each internal node caches the combined length of its subtrees, so that length queries are O(1) and a split or concatenation only has to touch O(log n) nodes along a single root-to-leaf path. Hence, splicing new content into a rope costs O(log n) to find the split points plus the cost of building a subtree for the inserted text, rather than O(n) to rebuild the whole sequence.

Asymptotic complexity is only half the story—real-world performance matters, too. On the benchmark suite bundled with this package (see Measured Performance), a splice or slice into a rope of 32,768 characters completes in microseconds, regardless of where in the rope it happens. Appending two ropes typically costs about 100 nanoseconds. Because ropes compare whole chunks at once rather than one element at a time, equal? on two content-identical ropes completes in a few hundred microseconds. Recomputing equal-hash-code on a rope that has already been hashed costs under 60 nanoseconds independent of its size, because hashes are memoized as a composable polynomial hash.

This library separates the tree structure from what it holds. The rope type itself only knows about leaves and nodes—it has no idea whether a leaf’s payload is a string, a byte string, or something else entirely. A generic interface, gen:ropeable, describes the handful of operations a chunk type needs to support (slice, append, count, and so on), and the define-rope-type macro turns any such description into a complete, efficient, type-specific rope implementation. The library includes support for string ropes and byte string ropes out of the box, and Defining New Rope Types walks through building a new rope type from scratch.

2 Quick Start🔗ℹ

The most common way to use this library is through rope/string, which treats a rope as a persistent, efficiently editable stand-in for a string. You can build one with string->rope and get an ordinary string back with rope->string:

> (define greeting (string->rope "Hello!"))

> (rope-length greeting)

6

> (rope->string greeting)

"Hello!"

Editing a rope never touches its argument; every operation returns a new rope that shares structure with the old one. string-rope-splice replaces a run of characters with a new string, and inserting text is just the special case where nothing is replaced:

> (define with-name (string-rope-splice greeting 5 0 " World"))

> (rope->string with-name)

"Hello World!"

; the original is untouched

> (rope->string greeting)

"Hello!"

Deleting text is just splicing in the empty string.

> (define bare (string-rope-splice with-name 5 7 ""))

> (rope->string bare)

"Hello"

Building up a large document out of pieces is a matter of appending ropes, which is also O(log n):

> (define doc     (string-rope-append      (string->rope "It was the best of times, ")      (string->rope "it was the worst of times.")))

> (rope->string doc)

"It was the best of times, it was the worst of times."

Ropes are also sequences of their elements, so a rope of characters works with the various for forms via in-string-rope:

> (for/list ([ch (in-string-rope doc)]              #:when (char-upper-case? ch))     ch)

'(#\I)

Everything above works identically for byte strings with rope/bytes in place of rope/string.

3 Concepts🔗ℹ

4 Generic Rope Operations🔗ℹ

This module defines the rope tree structure, the cursor type, and the gen:ropeable interface that connects the two to a particular chunk representation. Most programs will use a type-specific module such as rope/string instead of calling these generic operations directly; this reference is here for readers implementing a new chunk type, and to document what the type-specific operations reduce to underneath.

5 String Ropes🔗ℹ

A rope specialized for string? chunks, generated by define-rope-type (Defining New Rope Types). Every operation below behaves exactly like its generic counterpart in rope/rope, specialized to strings and with no need to supply a ropeable instance explicitly.

6 Byte Ropes🔗ℹ

A rope specialized for bytes? chunks, generated by define-rope-type in exactly the same way as rope/string. Every operation below is the byte-string version of the corresponding string-rope operation described in the previous section.