rune

Any connection to https://github.com/CeleritasCelery/rune ?

Two projects that may be of interest, related to this topic: - Rune (https://github.com/CeleritasCelery/rune) - A re-implementation of Emacs but in Rust (like Remacs, but actively developed) - Pimacs (https://github.com/federicotdn/pimacs) - Same, but using Go (created by me, but developed in a very slow pace)

It is actually not very novel. It is just a Fenwick tree[1]. And a Fenwick tree is basically a rope where the leafs don't store any text. basically every leaf holds some metrics (say bytes and line endings) for some chunk of text. By just looking at the leaf we don't know which chunk it points to. But since the leafs are all in order, we can calculate their byte position and line ending by adding them up. If we add all the leaf we should get the total number of bytes and lines in the text. In order to avoid O(n) cost of summing every leaf, we store them in a tree, where each parent holds the sums of it's children. So when we want to find the byte position[2] of a particular line ending we can just walk down the tree and see if the line ending we are searching for is greater then the left child or not. If it is, we add the left child's sum

> if the underlying buffer needs to reallocate after some edits the entire process slows to a crawl as you need to allocate a larger buffer and copy each byte into the new buffer and destroy the old one. It can turn an O(n) operation into O(n^2) randomly. This would still only be a O(n) operation. The constant value might be higher, but the complexity is the same. I don’t buy the argument that gap buffers “are bad for multiple cursors”. I get the argument on a theoretical level, but real hardware is not theoretical. There are several operations that are theoretical faster with a hashmap or b-tree than a vector, like insert and delete. But in reality the vector is usually faster in the real world except for very large inputs[1]. Gap buffers are basically vectors. Another point with multiple cursors and gap buffers is that Chris Wellons ani

> How is anything rooted here? The lifetime changed from 'arena to 'root but I don't see a root being created. In this example, the Vec has been rooted previously. So pushing an object into the Vec will make it "transitively" rooted (accessible from the root). You would root a struct with the root_struct![1] macro, which works very similar to the root! macro shown in the post. However you made you realize one error; The rooted `Vec` in the example you pointed is a by value type, but in the implementation you can only get references to rooted structs, so that example needs to be updated. > But later we see roots not obeying a LIFO order, under "Preventing escapes" where roots are dynamically created and destroyed in an arbitrary order. Objects are just a copyable wrapper around a pointer, so they are not the part that has the LIFO semantic