Item — HN Reader

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.

3 comments

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.

I did a little digging, and don't think so. Being able to access a readonly snapshot is a property of the filesystem, it's a guarantee that if you overwrite file contents, the original data is still available. With btrfs and friends, you could create a "reflink", but these filesystems are not in very widespread use, and it's also not clear to me that it's an overall performance win.

No need for a fancy filesystem; when one process asks for MAP_PRIVATE (aka Copy-On-Write = COW) on a file-backed page, all other references to that page can be marked COW as well, and if anybody does a write to the page, a new copy of the page gets created by the OS, and the various processes' references get sorted out to point to one copy or the other. The OS already needs almost this much implemented to allow multiple explicit COW references to the same page, which is surely allowed in Linux and Posix.

That idea works when the page is swapped in, but I don't think you're accounting for the case where the only copy of the contents is in the file that's backing the mapped region.

I'm sure we're boring everybody, but yes, I am accounting for the case where the only copy is in the file. The OS knows that there are live references to the non-resident, file-backed page, marked as such in one or more process page tables. For any change to happen to the actual page on disk, from any program in user-space or not, and even if they think they're using write(2) rather than mmap, under the covers the OS does the moral equivalent of mapping the page, and the modification happens in memory, and the page eventually gets written back to the physical disk, but it's all unified between write() and mmap() pages, and all the wonderful semantics of mmap and sharing happen here as well. I'm not sure that this goes all the way back to the original implementation of mmap(), but as you point out, it's a pretty useless observation given the unfortunate backsliding in the Posix specification (perhaps some vendor didn't manage to get up to speed on the unified page scheme?)

”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.

Then you've chosen the wrong abstraction.

Maybe I've misinterpreted the discussion, but there's not always a perfect abstraction [1].

1. https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-a...