• Zed Decoded Series: This is a blog & video series by Zed, where they look at how Zed is built. In this second post, the focus is on the data structure at the heart of Zed - the rope.
• Companion Video: It comes with a 1-hour companion video where Thorsten, Nathan, Antonio, and Max use Zed to look at how Zed uses the Rope and SumTree types. It's a loose conversation with code writing and reading to understand the rope's work and implementation. Watch the video here →
• Why Not a String: Strings are usually allocated as a continuous block of memory, making edits inefficient. For example, inserting or deleting a word in a large string requires moving a lot of text. Strings also have problems with navigation, like finding a specific line or knowing the length of the longest line. These issues become more significant with large files and multiple edits.
• What's Better than a String: Other data structures like gap buffers, piece tables, and ropes are better than strings for representing text in a text editor. Each has its pros and cons, and different editors make different decisions based on their trade-offs. Zed uses a rope.
• Ropes: A rope is a type of binary tree where each leaf holds a string and a length. Instead of modifying strings, you modify the tree. This makes operations like deleting and concatenating words more efficient, especially with large texts.
• Zed's Rope Implementation: Zed has its own rope implementation in the rope crate. The main type is Rope, and operations like concatenating and replacing text are very quick even with large amounts of text. The leaf nodes in Zed's rope implementation are not fully immutable; they can be mutated if the new text fits within the node.
• Why Use a Rope in Zed: Zed's goal is to be a high-performance code editor. Ropes are "not amazing at anything, but they're always solidly good" and have advantages like support for concurrent access from multiple threads. This is important for Zed as it allows for asynchronous saves, backups, and multi-user edits.
• It's not a Rope, it's a SumTree: Zed's rope is a SumTree, which is a B+ tree. Each leaf node contains a Chunk, and internal nodes contain summaries of their child nodes. The summaries in the SumTree allow for efficient traversal of the tree in O(log n) time and indexing of the data.
• Traversing a SumTree: The SumTree allows for traversal based on the values in the summaries. You can seek along a single dimension of a summary and find items in the tree quickly. For example, converting an absolute offset to a row and column in a rope is done by traversing the SumTree.
• Using the SumTree: You can traverse the SumTree in both directions and seek along different dimensions. It can also be used to convert between UTF8 and UTF16 rows/columns. The SumTree is used in many places in Zed, not just for the rope.
• Everything's a SumTree: There are over 20 uses of the SumTree in Zed. The SumTree is at the core of Zed and is used in various data structures like DisplayMap, which contains information about how a buffer of text should be displayed. The rope is built on top of the SumTree.