Hacker News Reader

Comment by josephg | Hacker News Reader

A rope is a data structure for big strings. Its a string where instead of storing the characters in an array, the characters are stored in a different data structure to make common operations faster. Ropey stores a string where the characters are kept in a b-tree. This allows log(n) time complexity for inserts or deletes anywhere in the string.

So you can have a string with millions of characters (a loaded document) and you can edit it efficiently.

View on HN

It seems the biggest issue with ropes is search. The rust regex engine (which this editor uses) expects an array. In the worst case scenario you forced to copy the entire document into an array to run search on it. Only to throw that away when you are done. That offsets a lot of performance gains ropes are supposed to provide.

https://github.com/xi-editor/xi-editor/issues/1192#issuecomm...

Yeah, the search implementation right now is kind of thrown in there just to get out of the way of my editing.

There's a way to search through rope chunks by using the low level regex-automata: https://github.com/rust-lang/regex/issues/425#issuecomment-7...

Alacritty currently does that to search over it's cells, I'd like to look into it.

> That offsets a lot of performance gains ropes are supposed to provide.

It sounds like that offsets lot of performance gains the rust regex engine is supposed to provide, actually.

Search is pretty fundamental to text editors. Getting fast insertion with slow search is not always a desirable trade-off.

If the regex engine doesn't support indexing into a arbitrary (indexable) data structure, that's a deficiency in the regex engine, not in one particular such data structure. You can tell this isn't a deficiency of ropes, because the exact same thing would happen if you used[0] hash tables or b-trees.

Search might be slower with a more complicated lookup (versus a probably-inlined-and-otherwise-optimized pointer-plus-index addition), but that wasn't the problem described; the problem decribed was that non-array lookups weren't supported at all, and search required copying the data over to a array before the regex engine would deign to touch it.

0: for a example, not a suggestion that they would be a good fit for a text editor

It's not widely known but PCRE (which I assume is still the most widely used regex library) supports partial matching which you can use to interoperate with any piecewise linear string representation (ropes, gap buffers, etc).

When you think about it, keeping editor text in a naive array-based string would be absolutely nutty

Reply on news.ycombinator.com