Zed Decoded: Rope and SumTree(zed.dev)
zed.dev
Zed Decoded: Rope and SumTree
https://zed.dev/blog/zed-decoded-rope-sumtree
44 comments
I first learned of the rope data structure and piece table [1] from the Tree Sitter docs:
https://tree-sitter.github.io/tree-sitter/using-parsers#prov...
1: https://en.wikipedia.org/wiki/Piece_table
1: https://en.wikipedia.org/wiki/Piece_table
In particular, the "summary" from the SumTree in this Zed article reminded me of the "metric" abstraction described in Raph's Rope Science.
I’ve tried Zed and it’s really nice but there is a very high bar for switching to a new editor - it has to be sufficiently better than alternatives and also have widespread adoption. There are so many man hours that went into things like undo-tree and magit. And thanks to the sheer popularity of mainstream editors, I can get language support for languages that aren’t even publicly available like Jai.
I want to use it, but I don’t think I am going to be able to justify investing in new editors at this point unless there is something extremely compelling about it.
I want to use it, but I don’t think I am going to be able to justify investing in new editors at this point unless there is something extremely compelling about it.
I tried Zed a few weeks ago and was extremely impressed. I was expecting it to be another half baked 'Rewrite it in Rust' hobby project, but it's actually very much usable for the kind of development I'm doing. Since then I've completely swapped it out with VSCode and loving it so far. There's only one or two small issues which I'm hoping will be ironed out soon. Zed is also really really fast. I can feel the input latency is significantly lower than VSCode and faster feedback helps me write code more fluently.
Ditto! The only thing that occasionally bumps me is a few missing features in vim-mode (marks & recording). But it feels so much faster than VS Code, I'm willing to put up with it so far.
I tried Zed a while ago, not long after they first launched. It was pretty interesting (gpu+rust+tree-sitter+lsp), but not enough to draw me from neovim. After they went open source (and launched extensions!) I looked at it again and actually I'm really impressed with the progress (incl. vim keybindings ftw!).
I'm at the point of using it for some new projects and continuing with neovim for my existing ones -- there's a lot of community input e.g. nvim-surround functionality was just added. I think at this point it does everything that I have in my (somewhat minimal) nvim config (and much of that is tree-sitter/LSP).
The one big feature I'm interested in is dap support so I can finally give up on gdb cli.
I'm at the point of using it for some new projects and continuing with neovim for my existing ones -- there's a lot of community input e.g. nvim-surround functionality was just added. I think at this point it does everything that I have in my (somewhat minimal) nvim config (and much of that is tree-sitter/LSP).
The one big feature I'm interested in is dap support so I can finally give up on gdb cli.
I really want to love Zed.
And truly believe they are onto something big with multiplayer coding, chat, collab.
But I’ve run into so many bugs I’ve had to stop using Zed.
The amount of time I’ve spent filing bugs, troubleshooting, documenting errors etc - is counter productive.
It makes me realize that I’m old enough now to just want things to work.
I’ll give it another go once it hits 1.0
Until then, wishing them the best and for them to make the developer world better for us all.
And truly believe they are onto something big with multiplayer coding, chat, collab.
But I’ve run into so many bugs I’ve had to stop using Zed.
The amount of time I’ve spent filing bugs, troubleshooting, documenting errors etc - is counter productive.
It makes me realize that I’m old enough now to just want things to work.
I’ll give it another go once it hits 1.0
Until then, wishing them the best and for them to make the developer world better for us all.
This is how I've been feeling about neovim recently.
I'm curious as to why. I finally went all in on neovim about two years ago and have been having an amazingly stable experience.
are you referring to the actual editor or to the plugins you used?
the editor itself has been very stable for me (daily usage) and the plugin ecosystem definitely offers so many choices that most of the time I can find stable/well-working ones for my use case.
the editor itself has been very stable for me (daily usage) and the plugin ecosystem definitely offers so many choices that most of the time I can find stable/well-working ones for my use case.
Neovim core has lots of bugs.
[deleted]
> The amount of time I've spent troubling shoot...
Conveys a lovely element of gardening: new bits of code appear like shoots in the garden, often troubling if they aren't what one planted, taking time to weed giving nutritious shoots room to grow.
Conveys a lovely element of gardening: new bits of code appear like shoots in the garden, often troubling if they aren't what one planted, taking time to weed giving nutritious shoots room to grow.
Zed? More like Zen.
Similar to a SumTree, if all you need is incrementally computed values without data persistence, a heap makes for a more efficient data structure. I remember learning about this from the following blog: https://timvieira.github.io/blog/post/2016/11/21/heaps-for-i...
I’ve seen the SumTree pattern show up a bunch recently. As I understand it, VSCode has something similar for syntax highlighting. And I’ve both seen and written several implementations of this pattern in the various text CRDTs I’ve interacted with. - though in each case the structure is given a different name. (Eg RangeTree, ContentTree, G-Tree, etc).
It’s nice to see the idea is catching on. It’s a good one.
It’s nice to see the idea is catching on. It’s a good one.
Ropes remind me of Haskell's
I've survived in math partly by attempting to catalog how others think. I sense a divide in Haskell, between people who prefer to view the compiler as a hermetically sealed abstraction, and those of us who try exploit what we think the compiler is doing. To view `ShowS` as a rope one needs to consider how the compiler handles lazy evaluation.
type ShowS = String -> String
I've survived in math partly by attempting to catalog how others think. I sense a divide in Haskell, between people who prefer to view the compiler as a hermetically sealed abstraction, and those of us who try exploit what we think the compiler is doing. To view `ShowS` as a rope one needs to consider how the compiler handles lazy evaluation.
You don't need to anything about the compiler internals to know that a String is a linked list, and that concatenating a linked list is expensive, and that ShowS is a function interface that enables optimized contatenation.
Rope is a data structure, not a function.
https://hackage.haskell.org/package/base-4.19.1.0/docs/GHC-S...
https://hackage.haskell.org/package/base-4.19.1.0/docs/Data-...
Rope is a data structure, not a function.
https://hackage.haskell.org/package/base-4.19.1.0/docs/GHC-S...
https://hackage.haskell.org/package/base-4.19.1.0/docs/Data-...
Data structures are useless without functions, and functions are useless without data structures. In use, ropes are like `ShowS`. It feels to me like you're making a grammatical distinction, of a kind I try to avoid so I can think more abstractly. Our categories are historical accident.
I've been trying Zed today and am thoroughly impressed. Everything feels incredibly well considered, even for edge cases.
A niche example I tried on a whim that just worked: You can multi-select lines (say, the start of every other line, or arbitrary points in the file) and then use Vim commands to apply changes only at those locations.
I'm kind of blown away.
A niche example I tried on a whim that just worked: You can multi-select lines (say, the start of every other line, or arbitrary points in the file) and then use Vim commands to apply changes only at those locations.
I'm kind of blown away.
Btw this is how kakoune works all around. Multiple selections are first class citizens
Also since there is no extra visual mode it is very easy to select something and then operate on it.
Also since there is no extra visual mode it is very easy to select something and then operate on it.
> Btw this is how kakoune works all around. Multiple selections are first class citizens
And Helix too. It's like a middle ground between Vim and Kakoune
And Helix too. It's like a middle ground between Vim and Kakoune
Since it's for a code editor and using trees, I wonder if directly using an AST would be a good idea. You don't need to store strings for keywords like "function" or "while", and you get syntax highlight and formatting basically for free.
An AST is dependent on the Language Server though and thus not available for every file by default.
Great explanation. If anyone has good references for learning this by making a minimal editor like sed from scratch, please share. Wait, now that I think about it, does the name “Zed” draw inspiration from “sed”? If yes, that’s rad.
It draws from the original UNIX text editor called "ed".
https://zed.dev/faq#why-zed
https://zed.dev/faq#why-zed
I have a simple (well, simple by my standards because I've spent a long time with it) implementation of a rope in Standard ML [0], OCaml [1] and F# [2]. (See tiny_rope.sml, brolib.fs or lib/tiny_rope.ml for implementation if you can read any of those languages; the F# implementation is probably easiest to read.)
[0] https://github.com/hummy123/brolib-sml
[1] https://github.com/hummy123/brolib
[2] https://github.com/hummy123/brolib-fs
The essence of a data structure is a binary tree where the internal nodes (the N2 case) contains a pointer to the left subtree, an integer containing the total length of the strings in the left subtree and a pointer to the right subtree. Then there are leaf nodes (the N0 case) which contain simply strings. (There are some other cases in the type like N1, N3 and L2, but those are solely for balancing because I built my ropes on top of 1-2 Brother Trees as described by Ralf Hinze, and those aren't essential to the rope data structure.)
When indexing (which is necessary for the insertion and deletion operations), you have a simple recursive algorithm which can be best seen in the recursive "ins" function. In the internal N2 nodes, the algorithm is to compare the index (given as an argument) with the left metadata. If the index argument is less than the left metadata, recurse to the left subtree passing the same index; otherwise, recurse to the right subtree, subtracting the index argument with the left metadata.
By the end, when you eventually reach the leaf case, the index argument is equal to the position you want to insert into in the current node. (I haven't tried to understand the maths behind this but it's how the data structure works.) At that point, all you do is insert into the leaf node's string (this is the same as inserting at an arbitrary index in any normal string) if you can without exceeding the maximum limit, or else you can insert another node.
Then you unroll the recursion. Unrolling the recursion involves updating the left subtree metadata when you reach the parent, and it also involves balancing. (I'm using 1-2 Brother Trees for balancing but ropes don't really care which balancing you use or if you use one at all.)
That's pretty much all there is to ropes. The deletion and substring algorithms just require minor modifications (the user might specify a range that includes more than one subtree, so you might need to recurse on both subtrees).
You can extend the idea behind ropes to hold more metadata too. For example, rope.sml (Standard ML) also tracks line metadata to allow indexing by line number. The changes required for this are: store an array at the leaf nodes containing indices of line breaks in the string also at this node, and at internal N2 nodes you should also store an additional integer indicating the number of lines in the left subtree.
There is an idea I haven't found too useful which is, if two leaf nodes have strings that can be joined without reaching the maximum limit, then join them. I haven't found this idea to improve performance much although it theoretically should.
I want to give a shout out to the MLton compiler for Standard ML here - the two rope implementations compiled with it handily beat the fastest ropes in Rust which is surprising. (My code performs well with F# and OCaml, but MLton takes it a level beyond that.)
[0] https://github.com/hummy123/brolib-sml
[1] https://github.com/hummy123/brolib
[2] https://github.com/hummy123/brolib-fs
The essence of a data structure is a binary tree where the internal nodes (the N2 case) contains a pointer to the left subtree, an integer containing the total length of the strings in the left subtree and a pointer to the right subtree. Then there are leaf nodes (the N0 case) which contain simply strings. (There are some other cases in the type like N1, N3 and L2, but those are solely for balancing because I built my ropes on top of 1-2 Brother Trees as described by Ralf Hinze, and those aren't essential to the rope data structure.)
When indexing (which is necessary for the insertion and deletion operations), you have a simple recursive algorithm which can be best seen in the recursive "ins" function. In the internal N2 nodes, the algorithm is to compare the index (given as an argument) with the left metadata. If the index argument is less than the left metadata, recurse to the left subtree passing the same index; otherwise, recurse to the right subtree, subtracting the index argument with the left metadata.
By the end, when you eventually reach the leaf case, the index argument is equal to the position you want to insert into in the current node. (I haven't tried to understand the maths behind this but it's how the data structure works.) At that point, all you do is insert into the leaf node's string (this is the same as inserting at an arbitrary index in any normal string) if you can without exceeding the maximum limit, or else you can insert another node.
Then you unroll the recursion. Unrolling the recursion involves updating the left subtree metadata when you reach the parent, and it also involves balancing. (I'm using 1-2 Brother Trees for balancing but ropes don't really care which balancing you use or if you use one at all.)
That's pretty much all there is to ropes. The deletion and substring algorithms just require minor modifications (the user might specify a range that includes more than one subtree, so you might need to recurse on both subtrees).
You can extend the idea behind ropes to hold more metadata too. For example, rope.sml (Standard ML) also tracks line metadata to allow indexing by line number. The changes required for this are: store an array at the leaf nodes containing indices of line breaks in the string also at this node, and at internal N2 nodes you should also store an additional integer indicating the number of lines in the left subtree.
There is an idea I haven't found too useful which is, if two leaf nodes have strings that can be joined without reaching the maximum limit, then join them. I haven't found this idea to improve performance much although it theoretically should.
I want to give a shout out to the MLton compiler for Standard ML here - the two rope implementations compiled with it handily beat the fastest ropes in Rust which is surprising. (My code performs well with F# and OCaml, but MLton takes it a level beyond that.)
Max line length can be aggregated by using a 1-2-3 element type, for example, using scalar, 2-tuple and 3-tuple:
The maxline ops are (obviously) non-commutative, but are associative, so you can apply them in any grouping, left-to-right, right-to-left, and even in parallel if you feel the need.
At the root of the tree, the left and right open lengths become actual lines (beginning and end of buffer are virtual line delimiters), so to get the global maximum line length, just max the 1, 2, or 3 values in the root maxline summary.
I like to separate newlines from other substrings as leaves in the tree. So the leaf maxlines are just:
The Zed blog claims to have such a thing, but didn't explain it. Apologies if it's in one of the repos. I didn't check.
open length |
{ open left length, open right length } |
{ open left length, max contained line, open right length }
0 newlines: open length
1 newline: { open left length, open right length }
2+ newlines: { open left length, max contained line, open right length }
The maxline ops are (obviously) non-commutative, but are associative, so you can apply them in any grouping, left-to-right, right-to-left, and even in parallel if you feel the need.
At the root of the tree, the left and right open lengths become actual lines (beginning and end of buffer are virtual line delimiters), so to get the global maximum line length, just max the 1, 2, or 3 values in the root maxline summary.
I like to separate newlines from other substrings as leaves in the tree. So the leaf maxlines are just:
substring: length
newline: {0,0}
The Zed blog claims to have such a thing, but didn't explain it. Apologies if it's in one of the repos. I didn't check.
I assume you know this from your reference to Hinze, but just to make the point clear:
In a pointer-to-mutable-memory language, a rope becomes a lot of recursive pointer-chasing inside a tree structure, typically referenced from the root down.
In a functional language, a rope may be built as a tree (or several subtree edits), but is processed from local cursors that have a bottom-up view from a concrete leaf position in the buffer.
A rope in a purely functional language is better described as a Finger Tree (Hinze, Paterson) [1] or Zipper (Huet) [2]:
[1] https://www.staff.city.ac.uk/~ross/papers/FingerTree.html
[2] https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced...
In a pointer-to-mutable-memory language, a rope becomes a lot of recursive pointer-chasing inside a tree structure, typically referenced from the root down.
In a functional language, a rope may be built as a tree (or several subtree edits), but is processed from local cursors that have a bottom-up view from a concrete leaf position in the buffer.
A rope in a purely functional language is better described as a Finger Tree (Hinze, Paterson) [1] or Zipper (Huet) [2]:
[1] https://www.staff.city.ac.uk/~ross/papers/FingerTree.html
[2] https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced...
Zed looks nice, but I didn't find extension settings. Are they accessible somewhere? By default, autofix is not enabled in zls, which is why I had to immediately go back to VSCode.
[deleted]
There are so many high performance editors that are just lists of strings. It's evidently false they are not high performance.
From the article:
If you really love strings, you might now
be thinking "better than a string? easy:
multiple strings." And you wouldn't be
that far off! Some editors do represent
text as an array-of-lines with each line
being a string. VS Code's Monaco editor
worked that way for quite a while, but an
array of strings can still be plagued by
the same problems as a single string.
Excessive memory consumption and
performance issues made the VS Code team
look for something better.Like what? Vim, Emacs, Helix, VSCode, Zed, Xi, Lapce, and Monaco all do not.
Kakoune does, and I found it (without extensions) to perform excellent even with multicursor.
Not saying that array of lines is more performant than ropes, but just adding a datapoint here.
Not saying that array of lines is more performant than ropes, but just adding a datapoint here.
What is Vim's internal data structure nowadays? I thought it was essentially a list (array) of strings.
Any chance for Helix keybinds eventually?
There is an open issue about helix keybinds:
https://github.com/zed-industries/zed/issues/4642
https://github.com/zed-industries/zed/issues/4642
And a WIP PR even: https://github.com/zed-industries/zed/pull/11130
pylint yells at me when my modules are more than 1500 lines. maybe it assumes the module is stored as string and not a rope.
=> https://xi-editor.io/docs/rope_science_00.html