4 ms·

Can’t find a download link of that article on that page nor another article explaining what “ropes” are. Can somebody tell me what a rope is?

josephg 5y ago
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.
- brundolf 5y ago
  When you think about it, keeping editor text in a naive array-based string would be absolutely nutty
- celeritascelery 5y ago
  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#issuecomment-491973483 https://github.com/xi-editor/xi-editor/issues/1192#issuecomm...
  - a1369209993 5y ago
    > 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.
    - celeritascelery 5y ago
      Search is pretty fundamental to text editors. Getting fast insertion with slow search is not always a desirable trade-off.
      - a1369209993 5y ago
        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
  - archseer 5y ago
    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-706804461 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.
  - psykotic 5y ago
    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).
banana_giraffe 5y ago
It's a b-tree for strings, optimizing for editor tasks that are traditionally inefficient if you keep a text document as a simple string. https://iq.opengenus.org/rope-data-structure/ https://iq.opengenus.org/rope-data-structure/

josephg 5y ago

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.

brundolf 5y ago
When you think about it, keeping editor text in a naive array-based string would be absolutely nutty
celeritascelery 5y ago
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#issuecomment-491973483 https://github.com/xi-editor/xi-editor/issues/1192#issuecomm...
- a1369209993 5y ago
  > 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.
  - celeritascelery 5y ago
    Search is pretty fundamental to text editors. Getting fast insertion with slow search is not always a desirable trade-off.
    - a1369209993 5y ago
      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
- archseer 5y ago
  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-706804461 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.
- psykotic 5y ago
  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).

banana_giraffe 5y ago

It's a b-tree for strings, optimizing for editor tasks that are traditionally inefficient if you keep a text document as a simple string. https://iq.opengenus.org/rope-data-structure/ https://iq.opengenus.org/rope-data-structure/