Ropes: Twining Together Strings for Editors

It's been a while since I've written about any data structures. But it just so happens that I'm actually really working on implementing a really interesting and broadly useful data structure now, called a Rope.

A bit of background, to lead in. I've got this love-hate relationship with
some of the development tools that Rob Pike has built. (Rob is one of the Unix
guys from Bell labs, and was one of the principal people involved in both the
Plan9 and Inferno operating systems.) Rob has implemented some amazing
development tools. The two that fascinate me were called Sam and Acme. The
best and worst features of both are a sort of extreme elegant minimalism.
There's no bloat in Rob's tools, no eye-candy, no redundancy. They're built to
do a job, and do it well - but not to do any more than their intended job.
(This can be contrasted against Emacs, which is a text editor that's grown
into a virtual operating system.) The positive side of this is that they're
incredibly effect, and they demonstrate just how simple a programmers text
editor should be. I've never used another tool that is more effective than
Acme or Sam. In all seriousness, I can do more of my work more easily in Sam
than I can in Emacs (which is my everyday editor). But on the other hand, that
extreme minimalist aesthetic has the effect of strictly eliminating any
overlaps: there's one way to do things, and if you don't like it, tough. In
the case of Acme and Sam, that meant that you used the mouse for damn-near
everything. You couldn't even use the up and down arrows to move the cursor!

This is a non-starter for me. As I've mentioned once or twice, I've got terrible
RSI in my wrists. I can't use the mouse that much. I like to keep my hands on my
keyboard. I don't mind using the mouse when it's appropriate, but moving my hand from
the keyboard to the mouse every time I want to move the cursor?. No. No
damned way. Just writing this much of this post, I would have had to go back and
forth between the keyboard and mouse over 50 times. (I was counting, but gave up when
I it 50.) A full day of that, and I'd be in serious pain.

I recently got reminded of Acme, because my new project at work involves using a
programming language developed by Rob Pike. And Acme would really be incredibly
useful for my new project. But I can't use it. So I decided to bite the bullet, and
use my free time to put together an Acme-like tool. (Most of the pieces that you need
for a prototype of a tool like that are available as open-source components, so it's
just a matter of assembling them. Still a very non-trivial task, but a
possible one.)

Which finally, leads us back to today's data structure. The fundamental piece of
a text editor is the data structure that you use to represent the text that you're
editing. For simplicity, I'm going to use Emacs terminology, and refer to the
editable contents of a file as a Buffer.

How do you represent a buffer?

As usual with data structures, you start by asking: What do I need it to do? What performance characteristics are important?

In the case of a text buffer, you can get by with a fairly small set
of basic operations:

• Fast concatenation: concatenating blocks of text needs to be
  really fast.
• Fast insert: given a point in a block
  of text, you need to be able to quickly insert text
  at that point.
• Fast delete: given two points in a block of
  text, you need to be able to quickly remove the text between those points.
• Reasonably fast traversal: Lots of algorithms,
  ranging from printing out the text to searching it are based
  on linear traversals of the contents. This doesn't have to be
  incredibly fast - it is an intrinsically linear process, and it's
  usually done in the context of something with a non-trivial cost
  (I/O, regular-expression scanning). But you can't afford to make it
  expensive.
• Size: you need to be able to store effectively unlimited
  amounts of text, without significant performance degradation in the
  operations described above.

Considering those requirements, you can eliminate a number of obvious
alternatives:

• Simple character array: Inserts and deletes
  are very expensive for large documents.
• Lists of lines: if you use a linked list, the memory cost
  for pointers becomes very expensive. If you use an array of
  lines, copy-insert costs of new lines becomes very expensive
  for large documents.
• Gap buffers: a neat variation on character arrays; they have
  the same problem on large documents.

Hybrids of the above can work nicely. Linked lists of character arrays
can work very nicely. In fact, the structure that I'm going to describe
is really a variation on the list of character arrays.

What works extremely well is to take the basic idea of a list of
mini-buffers (that is, smallish character arrays), and tweaking it,
so that instead of keeping a list of sub-buffers, you put
the sub-buffers into a binary tree. The result is a structure called
a rope. To the best of my knowledge, ropes were invented by
Hans Boehm (of garbage collection fame), and described in
this paper. Ropes are
a simple, elegant data structure that's excellent for representing large string-like
data structures. (The name is a pun: a real-world rope is made by twining together lots of smaller strings. A data-structure rope tangles together data-structure strings.)

I'm not going to present the full-blown version of ropes in this post; instead, I'm going to work up to that. In this post, I'm going to start by showing you a simplified version that illustrates the basic ideas. In later posts,
I'll work up to full-blown ropes, including things like sub-rope sharing, copy-avoidance via copy-on-write, and so on.

The basic idea of a rope is amazingly simple. A rope is binary tree
with strings in the leaves. An internal node in a rope tree doesn't contain any text - just pointers to its left and right children. The text value of a rope is the concatenation of its leaves, in left to right order. (This basic structure is also called a concatenation tree.) An example of a rope is shown to the side.

So - if you've got two huge strings of text that you want to concatenate, you just create a new root node, and put the two strings in as children. Presto! You've got a new rope containing the concatenation! For example, below are two rope-trees - one for the text "abcdefghijkl", and one for the text "zyxwv". Beneath them is the result of concatenating the two ropes.

Concatenation is therefore constant time, regardless of the length of the strings
being concatented. - you can't ask for better than that! Traversing the text is also
really easy - you just do an in-order traversal of the rope-tree. In the worst case -
a degenerate tree with one character per node - that gets very expensive. But it's
easy to avoid the degenerate case, as we'll see in a later post. In the typical case,
where each leaf node has a reasonable amount of text, and the tree is reasonably
balanced, the additional cost of traversing the tree is negligible in comparison to
the cost of traversing the characters in the nodes. (Each pointer in the tree needs
to be traversed once, which makes the total cost O(n) in the length of the text. But
since there's typically a lot of text per leaf, that ends up meaning that the
increase in traversal cost is minimal.)

For string-mutation operations, we can define almost anything we want in terms of
two primitives: concatenate, and subrope. For example, we can define how to
do insert and deletion of chunks of text from a rope as follows:

• Remove text: to remove a chunk of text that runs from point P1 to point
  P2 in a rope, we take the subropes (0, P1) and (P2+1,end), and then
  we concatenate them. The result is the rope with the chunk removed.
• Insert text: to insert a chunk of text C into a rope at a particular
  point p, we take the pre-subrope from 0 to P, and the post-subrope
  from P+1 to the end. Then we concatenate pre-subrope, C, and
  post-subrope.

So to provide those operations, we just need to figure out how to do substring in
an efficient way.

Substring isn't trivial in ropes. But it's not awful either. The main trick is
that there are a lot of cases to consider to get an implementation correct.

The basic idea is fairly simple. You traverse the tree, keeping track
of your position in the traversal. When you get to the substring you
want, you start copying - usually just copying the pointers to nodes. You
keep copying until you get to the end of the desired substring. The catch,
as I said above, is keeping track of all of the cases.

An outline of substring is:

• Inputs:
  • A rope, R.
  • The start position of the desired sub-rope, Start.
  • The length of the desired sub-rope, L.
• Algorithm:
  1. Let currentPosition = 0
  2. Let remainingLengthToCopy = L
  3. Let result = EmptyRope
  4. For each node N in the tree:
  5. If N is an internal node: traverse the left subtree, and then the right
     subtree.
  6. If N is a leaf, then:
     1. The start position of this node is currentPosition;
        the end position of this node is currentPosition plus the
        length of the string in this node.
     2. If the start position of the desired subrope is
        beyond the end of this leaf, then just increment
        currentPosition by the size of the string in this leaf.
     3. If the start position of the desired subrope is inside
        of this leaf, then start copying - produce a new
        rope node containing the substring (There are sub-cases
        here for "subrope also ends in this node", and "subrope"
        doesn't end in this node.) Increment currentPosition by
        the size of the string in this node, and decrement
        remainingLengthToCopy by the size of the copied substring.
     4. If the start position of the desired subrope is before this
        node, and the end position of the desired subrope is after
        this node, then insert this node into the result rope,
        increment the position by the size of the string in this node,
        and decrement remainingLengthToCopy by the length of the string
        in this node.
     5. If the start position of the subrope is before this node,
        and the end position is in the node, then copy the appropriate
        substring to a new leaf, and concatenate with result. Then
        return result.
     6. If the start position of this node is after the end of the desired
        sub-rope, return result.

An example implementation is below. It's a quick one that I whipped together in
Haskell. (I actually wrote versions in Haskell, OCaml, Python, and Java, but in
the end, I think that the Haskell is the easiest to follow.)

module Ropes where

-- A rope is either an internal node with two children and no text,
-- or a leaf node with text and no children.
data Rope = InternalRopeNode Rope Rope
         | LeafRopeNode String
   deriving (Show)

concatRope :: Rope -> Rope -> Rope
concatRope (LeafRopeNode "") r = r
concatRope r (LeafRopeNode "") = r
concatRope r1 r2 =
InternalRopeNode r1 r2

-- Subrope implemented using a fairly standard translation
-- of iteration to recursion. The state of each iteration is
-- represented by a triple consisting of the current position in
-- the rope, the number of characters still to be copied, and
-- the current subrope.
subRopeIter :: Rope -> Int -> Int -> (Int, Int, Rope) -> (Int, Int, Rope)

-- For an internal node, call subRope of the left child on the input
-- state, and then take the state resulting from the left-child invocation,
-- and use it as the input to the right child. There is a nice Haskell
-- syntax for this, but I think the let is clearer for non-Haskell
-- people.
subRopeIter (InternalRopeNode left right) start len (pos, remaining, result) =
    let (leftPos, leftRemaining, leftResult) = 
       subRopeIter left start len (pos, remaining, result)
    in subRopeIter right start len (leftPos, leftRemaining, leftResult)

-- The real work happens on leaf nodes. We define it by cases:
subRopeIter rope@(LeafRopeNode s) start len state@(pos, remaining, result) 
  -- (1) node_start + len(s) < start: node content comes before the start point.
  --        Just increment the position past the node and continue.
  | remaining == 0  = state

  -- (2) node_start < start and node_start + len(s) > start:
  --        Copy substring, decrement remaining, increment position.
  --       (2a) node_start + len(s) > pos + remaining
  --       (2b) node_start + len(s) < pos + remaining
  | pos + length(s) < start = (pos + (length s), remaining, result)
  | pos < start && pos + (length s) > start =
     let startPosInNode = (start - pos)
         substr = (drop startPosInNode s)
     in if (length substr) < remaining
          then (pos + (length s),
                remaining - (length substr),
                (concatRope result LeafRopeNode substr)))
          else (pos + (length s),
                0,
                (concatRope result (LeafRopeNode (take remaining substr))))

  
  -- (3) node_start > start and cur_remaining > 0 and cur_remaining > len(s): 
  --        Node lies entirely within the copy range. Copy entire node into
  --        result, decrement remaining, increment position.
  | pos > start && length(s) <= remaining =
       (pos + (length s), remaining - length(s), (concatRope result rope))

  -- (4) node_start > start + len (aka remaining == 0):
  --        Increment pos.    
  | pos > start && length(s) > remaining =
       (pos + length(s), 0, (concatRope result (LeafRopeNode (take remaining s))))
  | otherwise = state

subRope :: Rope -> Int -> Int -> Rope
subRope r start len =
   let (_, _, result) = subRopeIter r start len (0, len, LeafRopeNode(""))
   in result

For example, we can define a non-trivial rope as follows:

let r = InternalRopeNode 
         (InternalRopeNode 
           (LeafRopeNode "abc") 
           (InternalRopeNode 
             (LeafRopeNode "def") 
             (LeafRopeNode "ghi"))) 
         (InternalRopeNode 
            (LeafRopeNode "jkl")
            (LeafRopeNode "mno"))

That's a fairly complicated rope-tree of "abcdefghijklmno". In a real rope application, a string that short would really just be one node. But for illustration,
it'll do. To get the sub-rope of length 7 starting from position 5, we'd run:
subRope r 5 7. When I do that in GHCI, I get the following:


InternalRopeNode (InternalRopeNode (LeafRopeNode "f") (LeafRopeNode "ghi")) (LeafRopeNode "jkl")


Or "fghijkl" - exactly right. And to do the substring operation, we needed
to traverse the rope tree, copy two pointers (to the "ghi" and "jkl" nodes),
create one new leaf node (for "f"), and create two new internal nodes for
the concatenations.