Ropey – A UTF8 text rope for manipulating and editing large texts. in Rust
28 comments
·January 15, 2025ComputerGuru
deathanatos
Hmm. It's similar to, but not fully, a `BufRead`? Maybe a `BufRead + Seek`. The slicing ability isn't really covered by those traits, though, but I think you could wrap a BufRead+Seek in something that effectively slices it.
A `BufRead + Seek` need not be backed by memory, though, except in the midst of being read. (A buffered normal file implements `BufRead + Seek`, for example.)
I feel like either Iterator or in some rare case of requiring generic indexing, Index, are more important than "it is composed of some number of linked memory allocations"?
A ReadOnlySequence seems to imply a linked-list of memory sections though; I'm not sure a good rope is going to be able to non-trivially interface with that, since the rope is a tree; walking the nodes in sequence is possible, but it's a tree walk, and something like ReadOnlySequenceSegment::Next() is then a bit tricky. (You could gather the set of nodes into an array ahead of time, but now merely turning it into that is O(nodes) which is sad.)
(And while it might be tempting to say "have the leaf nodes be a LL", I don't think you want to, as it means that inserts need to adjust those links, and I think you would rather have mutations produce a cheaply made but entirely new tree, which I don't think permits a LL of the leafs. You want this to make undo/redo cheap: it's just "go back to the last rope", and then all the ropes share the underlying character data that's not changing rope to rope. The rope in the OP seems to support this: "Cloning ropes is extremely cheap. Rope clones share data,")
gpm
I think you might be looking for the bytes crate, which is pretty widely used in networking code: https://docs.rs/bytes/latest/bytes/index.html
In general this sort of structure is the sort of thing I'd expect to see in an external crate in rust, not the standard library. So it's unlikely there's any RFCs, and more likely there's a few competing implementations lying around.
null
jzelinskie
Is buf-list[0] what you're describing?
rdimartino
I hadn't heard of rope data structures until I read about the xi editor (also written in Rust) a few years ago, but it looks like that's been discontinued.
kibwen
The authors of Xi are currently working on Xilem, an experimental reactive UI framework for Rust: https://github.com/linebender/xilem
In the announcement post, they mention that work on Xi is considered "on hold" rather than strictly discontinued: https://raphlinus.github.io/rust/gui/2022/05/07/ui-architect...
infogulch
Legendary-tier yak shaving.
"I want to build an editor, but first I must solve rendering 2D graphics purely on the GPU, invent a parallelizable path solver, and code a human perception-based color value manipulation library."
PoignardAzur
You have no idea.
I think we're at five or six levels of yaks by now.
(xi -> xilem -> masonry -> vello -> peniko -> color)
itishappy
Zed uses something similar to ropes as well:
infogulch
Zed's Sum Tree is my favorite datastructure ever and is the future of database indexes.
PittleyDunkin
Zed seems to be a gui-oriented editor here: https://zed.dev/
supriyo-biswas
You still need a backing data structure that holds the contents of your editor, and that's where you'd use a rope.
neilv
How would you associate non-character data with ranges of characters, such as for syntax coloring, semantic links, and references to points in the text?
(I couldn't find a mention of this in the README, design.md, or examples.)
In Emacs buffers, the concepts include text properties, overlays, and markers.
filcuk
That would depend on your editor's implementation.
neilv
But, within this API, is there any support for the associations with non-character data?
For example, if you delete some text these Ropey data structure, does Ropey have facilities to update the associated non-character data (such as deleting all or part of one or more chunks of the non-character data, and/or updating positional information)? Or do you have to do that separately outside of Ropey?
zaphar
A rope is only concerned with manipulating a string with very low cpu overhead while maintaining the illusion of a sequence of characters or bytes. It doesn't really care or maintain any other text decoration you might be maintaining. That is the concern of the consumer of the rope and I'm not sure there is a good common interface for that.
pixelpoet
Author is perhaps better known for his really great path tracer (and attendant blog), Psychopath: https://github.com/cessen/psychopath
Also, I have to wonder when this fad of loudly announcing when something is written in Rust will finally come to pass. Maybe software written in other languages should loudly announce it in every second sentence? To me at least it's become as self-aggrandizingly cringe as "Sent from my iPhone" at the end of every email...
mattdw
When it’s a library of code, the language it is written in is pretty pertinent information as that’s the language it has to be consumed from…
uecker
Maybe it is already considered an achievement if someone manages to write a program in Rust.
javier2
Any editors using this?
cschmidt
It seems like Helix is using it https://github.com/helix-editor/helix/blob/master/docs/archi...
abound
FWIW, I use Helix as my main editor and every time it has crashed (probably a few dozen times over a year or two, I've filed issues), it's related to bad text position stuff, where it effectively goes "out of bounds" on the text data structure.
I think its mostly due to multiple buffers showing the same content, as opposed to this Ropey library directly.
recov
Not that library in particular, but https://zed.dev/blog/zed-decoded-rope-sumtree
null
Rust is missing an abstraction over non-contiguous chunks of contiguous allocations of data that would make handling ropes seamless and more natural even for smaller sizes.
C# has the concept of “Sequences” which is basically a generalization of a deque with associated classes and apis such as ReadOnlySequence and SequenceReader to encourage reduced allocations, reuse of existing buffers/slices even for composition, etc
Knowing the rust community, I wouldn’t be surprised if there’s already an RFC for something like this.