Hacker News Reader

Comment by abainbridge | Hacker News Reader

Beyond just loading, editing and saving text, how do these data structures compare when it comes to implementing other "tricky" features, such as:

1. Multi-line regular expressions. Typically the regex library is given an array of text to search in (). We have no such buffer to give.

2. Line wrap. Adding or removing a single character near the top of the file might require the entire file to be re-wrapped. You need to complete the wrapping process before you know how many lines are in the buffer and therefore can update the size and position of the vertical scroll bar's handle.

3. Column mode editing of text containing tabs.

Beyond those features, these data structures (gap buffer and piece table) don't seem well suited to operations that effect the entire buffer, such as convert-tabs-to-spaces.

At least when I used PCRE, it seemed to require this.

View on HN

1. All of them could probably easily create a bi-directional or markable stream of characters, which should be enough for the regex engine to work with.

2. That's a display issue. I would suspect that line-wrapping would want its own data structure within the display system.

3. I think this would fall under the same note as (2).

Basically, a layered approach like (display + editing mode) / (buffer) / (array or ropes or pieces or whatever). Because the editing mode would effect the edits being made to the buffer, which would then be translated into whatever underlying data structure is actually storing the file.

Reasonable points. As for (1), I couldn't find how to get PCRE to work with a stream like that. But that's either my fault or PCRE, not the text editor data structure.

As for 2, I'd just say that I think these are much harder than the problem that the linked article discusses. There have been other articles on the same topic on Hacker News recently. They all seem to focus on solving the trivial problem and ignoring the difficult ones. I mean, a std::list<std::string> is fine for the main data structure if you just want to load, edit and save and don't require (2) or (3).

I've also never seen a PCRE that actually works with such a stream, though it would be possible to construct one.

For your remaining points, sure. I don't know enough about text processing to know where the hard problems are. I do think that engineers sometimes overlook the possibility of having multiple data structures for multiple use cases for a single set of data, because it doesn't seem as elegant as one magical data structure that does it all.

PCRE's partial match[0] API allows it to be used on non-contiguous data structures. We use this feature in Atom[1] to allow for fast regex search in a background thread.

[0] http://www.pcre.org/original/doc/html/pcrepartial.html#SEC2

[1] https://github.com/atom/superstring/blob/ed57b08a74220dd33e4...

>...(gap buffer and piece table) don't seem well suited to operations that affect the entire buffer

With a gap buffer, you can just move the gap to the beginning (or end -- whichever is closer) of the buffer, and you'll have the "entire buffer" ready for one of those operations.

For (1) you can just convert your whole file to a contiguous array if necessary, then run your library, and if any changes happened, convert back.

Reply on news.ycombinator.com