Comment by raphlinus

9 years ago

I use ropes in xi editor. I did not find the argument against ropes convincing. Yes, they're not trivial to implement, but in a proper programming language you're not dealing with the data structure directly, you're always going through the interface, so you get the logic right once in the rope library implementation and then forget about it.

In a low-level design, your editing operations would be poking at the data structure directly. There, the simplicity of a gap buffer is a pretty big win. I agree in this environment ropes are too complicated. However, I don't see any good reason to architect a text editor in this way. Use abstractions.

The linked article contains a factual error, the referenced Crowley paper does not consider ropes. Thus it cannot be used in support of the argument that piece tables outperform ropes.

There's one other important concern with piece tables I didn't see addressed. It depends on the file contents on disk not changing. If your file system supported locking or the ability to get a read-only snapshot, this would be fine, but in practice most don't. It's very common, say, to checkout a different git branch while the file is open in the editor. Thus, the editor must store its own copy to avoid corruption. In the long term, I would like to see this solved by offering read-only access to files, but that's a deeper change that can be made piecewise.

I'd add that the assumptions that the specialized data structures (gap buffer and piece table) make are easily violated—someone mentioned a search-replace further down—at which point I can imagine their performance degrading unless special measure, i.e. more complexity, are added.

So yeah, in my editor (CodeMirror) I'm also using a rope/tree style representation [1], because it's pleasantly general and easy to reason about.

[1]: http://marijnhaverbeke.nl/blog/codemirror-line-tree.html

mmap(...MAP_PRIVATE...) will protect you from changes made to the file on disk.

  • My reading of the man page[0] is the opposite; your changes won't be reflected to the file, but "It is unspecified whether changes made to the file after the mmap() call are visible in the mapped region."

    I'd love to see the other direction. One approach that I think is worth exploring is when the file contents correspond to a git hash that the editor has access to. In fact, there is a pretty relationship between "deltas" and git commits, and this could possibly be exploited usefully.

    [0]: http://man7.org/linux/man-pages/man2/mmap.2.html

    • Wow, you're right, and the Posix page indicates the same thing. I believe it used to work properly in Unix / SunOS / HP-UX / AUX (IBM) / Solaris.

      6 replies →

”I agree in this environment ropes are too complicated. However, I don't see any good reason to architect a text editor in this way. Use abstractions.”

Abstractions can cost you dearly. If your abstraction for indexing into your buffer moves from O(1) with a small constant to O(log(n)) with a larger one, that global replace using regular expressions can get a lot slower. Even a simple page down may get noticeably slow when at the end of a large file with long lines.

  • Something I have always wanted to try is use a high level abstraction like say ropes for representing some domain specific data, but for some operations, navigating the high level data structure dominates. What if one could do a linear scan through memory and then collect the "hits", and map those back to handles in the high level data structure?

    Some hits will be false positives, where by dumb luck, it looks like you have a match, all hits have to resolved against user data.

    It feels analogous to a bidirectional lens, but instead of being between high level data structures, it is using the underlying raw memory.

  • So I'm an entrepreneur, and a native-born American citizen, so I'm obviously not talking my book here. My source is simply what I've observed trying to recruit co-founders. Folks with actual tangible skills and a realistic outlook would generally rather collect a paycheck for their skills. But I also don't consider lack of venture capital or mentorship to be an important barrier to my success. When I look at what I do daily, as a founder, there is very little that more money would help with. And their advice is generally pretty cookie-cutter; if you follow it blindly, you will look like every other company they fund, which will be the death of your company. The good ones recognize this, and what they look for in a founder is someone with an independent perspective who will do the legwork to verify their hunches with data, on their own, and don't trust anybody else's ideas of reality. The bad ones, you don't want to do business with.

    https://thecedrus.com/user/TiffaniIncor/lessons/513199388727...

    https://instasafari.com/discover/ycombinator

    https://freshcalendars.com/november-2017-calendar