Live data from Hacker News

Text Editor Data Structures

cdacamar.github.io

51–60 of 81 posts

Re: Text Editor Data Structures

#51

Earlier quoted context omitted.

But you also read it as referring to ZWJ sequences? So the author has picked a number that is actually below average and they've worded it as up to... ? Saying a ZWJ sequence can be "up to 5 bytes" is like saying "the current generation of Intel processors run at clock speeds of up to 2 GHz". If they were referring to ZWJ sequences (I don't think they were; I think they were just misremembering the maximum encoded le…

I think you are trying to read something that wasn't meant to be technical documentation as if it was trying to be exact technical specifications. I'm not the original author, so I don't have reason to litigate this any further, and I'm not sure what you are arguing about at this point.

You've now replied to me up to 2 times.

Re: Text Editor Data Structures

#52

Earlier quoted context omitted.

I do miss the 'select and execute', and 'everything is a shell' model of MPW. Definitely one of my favorite development environments.

elsewhere on HN today is a short article on BBedit, which has a really nice shell worksheet interface similar to the old MPW. Select the text you want to execute, hit control-return, and the shell output will appear below the selected text.

[deleted]

Re: Text Editor Data Structures

#53
> Create debugging utilities for data structures very early on.

Yes, this isn't encouraged enough. I often serialize my data structures as either JSON or Graphviz DOT files for visualization. It helps save an immense amount of time. You can also use the generated files for regression testing, i.e. diff the actual output with the serialized output and if they're different, then a bug was introduced.

Re: Text Editor Data Structures

#54

Earlier quoted context omitted.

Text is usually stored as tree either way in an editor, using a DOM-like approach might work well on top of the usual datastructures. > with the DOM the selection can start from a node with node-specific subrange (e.g. character in a text node) and end with another node and both being very unrelated to each other I'd just store the range as character indices, using those the right nodes in the tree can be accessed pr…

I don't think character indices are enough, what if your selection begins at the middle of a table cell and ends on an image that is the only child of a cell in a completely different table (no text involved at all, except some text in the cells in between)? If you want to, e.g., delete those how do you find which nodes are to be deleted and updated (e.g. for merging the two tables if there are cells after the one th…

Images and table cells are just nodes within the tree holding the text, assuming all styling etc is represented in a plain text syntax similar to Markdown, of course. Looking up the nodes from char indices is quick if each node stores how many chars it contains.

Other approaches would probably require the selection to be a tree of its own, I can't really say whether that's simpler overall or not.

Re: Text Editor Data Structures

#55
post #33

This seems revisionist/ignorant. The article attributes a "piece tree" data structure to VS Code developers, however the must-read 1998 paper by Charles Crowley, Data Structures for Text Sequences , already mentions search trees as being used to enhance the naive piece table in some text editors. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48...

I think you could probably get rid of the first sentence.

Re: Text Editor Data Structures

#56

Earlier quoted context omitted.

Some "single character" emoji easily exceed 5 bytes in all encodings. You may think ZWJ sequences are cheating, but emoji isn't the only language encoded in Unicode with complex ZWJ sequences.

My question is about the phrase up to 5 . What in Unicode is up to 5? Codepoints are up to 4 in all the encodings I know. ZWJ sequences may as well be arbitrarily long. What is "up to 5"?

Codepoints themselves could technically all fit into 3 bytes (or 21 bits to be precise), but there is no standard 3-byte encoding. The highest Unicode codepoint is 0x10FFFF.

An idea for a variable width encoding of 1 to 3 bytes: Read the MSB of each byte: If it's 0, don't read any more bytes. If it's 1, read the next byte. Do the same (up to 3 times). The non MSB bits of each byte then make up the codepoint.

    0xxxxxxx                    (ASCII)
    1xxxxxxx 0xxxxxxx           (0x0080 - 0x3FFF)
    1xxxxxxx 1xxxxxxx 0xxxxxxx  (0x4000 - 0x1FFFFF)
If the Unicode range grew in future to require further bits you could use the same technique by allowing greater than 3 bytes.

    1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx (0x200000 - 0x10000000)
The obvious drawback to this approach is that it is inherently serial. You need to read each byte before considering the next, so it would perform worse than UTF-8 in most cases.

Another drawback is that it is not self-synchronizing, which is one of the benefits of UTF-8.

It also has the issue that you can represent some codepoints with more than one encoding: eg, put ASCII characters into 2 or 3 bytes. So you would need rules to use the minimal encoding for each codepoint.

As a space-saving technique, it may offer better density than UTF-8 or UTF-16 on some texts.

You could also use a fixed-width encoding of 24-bits to avoid the problem of reading it serially, but as computers typically work in powers of 2, you would align 24-bit values at 32-bit addresses and load them into 32-bit+ registers, so there's nothing to really gain in terms of performance here over UTF-32, but you could save a bit of space.

Re: Text Editor Data Structures

#57

Earlier quoted context omitted.

I don't think character indices are enough, what if your selection begins at the middle of a table cell and ends on an image that is the only child of a cell in a completely different table (no text involved at all, except some text in the cells in between)? If you want to, e.g., delete those how do you find which nodes are to be deleted and updated (e.g. for merging the two tables if there are cells after the one th…

Images and table cells are just nodes within the tree holding the text, assuming all styling etc is represented in a plain text syntax similar to Markdown, of course. Looking up the nodes from char indices is quick if each node stores how many chars it contains. Other approaches would probably require the selection to be a tree of its own, I can't really say whether that's simpler overall or not.

The syntax shouldn't matter (you may not even being using a plain text syntax - or any syntax - anyway), you could treat an image or whatever as a single "special" character. Or just assign a linearly increasing ID (increasing in the order the text, images, etc flows) to each node.

Though that is basically another way to represent what i wrote above with having a pair of node pointers and a subrange (well, an index actually, the other end of the subrange is implicit if the node pointers are different). This is basically what the old HTML editing control Microsoft had back in the 90s used and that worked with the DOM tree (also what i used in a test editor i wrote some time ago). And yeah it isn't simple.

Re: Text Editor Data Structures

#58
post #55
post #33

This seems revisionist/ignorant. The article attributes a "piece tree" data structure to VS Code developers, however the must-read 1998 paper by Charles Crowley, Data Structures for Text Sequences , already mentions search trees as being used to enhance the naive piece table in some text editors. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48...

I think you could probably get rid of the first sentence.

Yeah, I regret writing it, but it's too late to edit the comment now.

Re: Text Editor Data Structures

#59
> if the underlying buffer needs to reallocate after some edits the entire process slows to a crawl as you need to allocate a larger buffer and copy each byte into the new buffer and destroy the old one. It can turn an O(n) operation into O(n^2) randomly.

This would still only be a O(n) operation. The constant value might be higher, but the complexity is the same.

I don’t buy the argument that gap buffers “are bad for multiple cursors”. I get the argument on a theoretical level, but real hardware is not theoretical. There are several operations that are theoretical faster with a hashmap or b-tree than a vector, like insert and delete. But in reality the vector is usually faster in the real world except for very large inputs[1]. Gap buffers are basically vectors.

Another point with multiple cursors and gap buffers is that Chris Wellons animations show the gap moving back to the first cursor every time it needed to add a new character. But in reality you would just walk the cursors in reverse order each time, saving a trip.

I have actually written and benchmarked a very naive and unoptimized gap buffer, and the results showed that it was faster than highly optimized rope implementations on all real world benchmarks[2], including multiple cursors.

That being said, a gap buffer is still probably not the best data structure for a text editor because it has worse “worse case” performance than something like a rope or piece-tree. Even though it is faster overall, it’s the tail latency's that really matter for interactive programs.

Overall I enjoyed reading the post, I find the topics fascinating and this was well presented.

[1] http://www.goodmath.org/blog/2009/02/18/gap-buffers-or-dont-...

[2] https://github.com/CeleritasCelery/rune/issues/17#issuecomme...

Re: Text Editor Data Structures

#60

Can someone point me to structures/algorithms to use for text editor which could support files of unlimited lengths (including lines of unlimited length) without loading those fully in the buffer? I miss that editor so much, that I'm considering to write one some day, but I have no idea how to do so. I can invent things myself, but I guess those things were invented already back in the days computers were different.

That is essentially what VLF[1] does in Emacs. It reads in discrete chunks of the file at a time and doesn’t load the next one till you try to display it. Doesn’t require any fancy data structures, just some extra book keeping and mechanics.

[1] https://github.com/m00natic/vlfi

Post reply on HN