Live data from Hacker News

Text Editor Data Structures

cdacamar.github.io

71–80 of 81 posts

Re: Text Editor Data Structures

#71

Earlier quoted context omitted.

> 5 bytes? In what encoding? I believe UTF-8 reserved up to six bytes for a single character.

Yes, UTF-8 was up to 6 bytes per character early on. Some broken implementations like MySQL's limit it to up to 3 bytes per character. The actual number is 4. So what is "up to 5"?

I think with decomposed Hangul, you can end up with 6 or more bytes per character, due to each part of it being two bytes, and 2-4(?) parts per character.

Re: Text Editor Data Structures

#72

Earlier quoted context omitted.

I read this as colloquial English for "around" or "approximately". Not setting a bound limit, but setting an example size.

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…

Sorry I meant codepoint/characters, but it would not suprise me if there existed an encoding or language where my wording would be technically correct, but I do not know of any such encoding. I also did not know that there exist more then 5 combinations in Unicode, but I'm not supprised and my implementation is probably buggy. But I do challange you to test how well your favourite editor (terminal emulator cough) handles Unicode emojis.

Re: Text Editor Data Structures

#73

There are tons of articles about plain text editor data structures, but what about rich text editor data structures? Let's say i want to implement a text editor that can have bold, italic, underline, etc text but also be able to do automatic word breaking, align paragraph text to left/middle/right, insert images and/or other objects, have floating images and/or other objects around which the other (non floating) text…

I am pretty sure that Write for Win3.1 used the Rich Edit control, or an early, non-public pre-cursor. Here are the Win32 docs: https://learn.microsoft.com/en-us/windows/win32/controls/ric... The more I read about this control, the more I learn about its insane feature set! Microsoft continues to make significant improvements to a version that is only shipped with Microsoft Office -- not available from a barebones Wi…

Write is actually quite barebones, paragraph and text styling with paragraphs being "images" (Win3.0) or OLE objects (Win3.1, images were OLE objects). Tables, etc were done manually with tabstops.

There is a text file describing the reverse engineered file format here:

https://web.archive.org/web/20130831064118/http://msxnet.org...

Re: Text Editor Data Structures

#74

Earlier quoted context omitted.

I am pretty sure that Write for Win3.1 used the Rich Edit control, or an early, non-public pre-cursor. Here are the Win32 docs: https://learn.microsoft.com/en-us/windows/win32/controls/ric... The more I read about this control, the more I learn about its insane feature set! Microsoft continues to make significant improvements to a version that is only shipped with Microsoft Office -- not available from a barebones Wi…

Write is actually quite barebones, paragraph and text styling with paragraphs being "images" (Win3.0) or OLE objects (Win3.1, images were OLE objects). Tables, etc were done manually with tabstops. There is a text file describing the reverse engineered file format here: https://web.archive.org/web/20130831064118/http://msxnet.org...

You are right! I had Write mixed up with Wordpad.

Re: Text Editor Data Structures

#75
post #72

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…

Sorry I meant codepoint/characters, but it would not suprise me if there existed an encoding or language where my wording would be technically correct, but I do not know of any such encoding. I also did not know that there exist more then 5 combinations in Unicode, but I'm not supprised and my implementation is probably buggy. But I do challange you to test how well your favourite editor (terminal emulator cough ) ha…

UTF-8's original specification included 5-byte and 6-byte encodings to cover the complete astral plane (31-bit code points), but later specifications have marked those "invalid" today due to the current 21-bit limit of UTF-16 and to align both specifications for now rather than fix the bugs in UTF-16 (or scratch UTF-16 altogether). In theory, UTF-8 can even extend beyond 6-byte encodings (and UTF-32 into 8-byte encodings and beyond) if the next plane (63-bit code points) or the one after that ever needed to open up. (No one expects that any time soon, of course. Today Unicode is nowhere close to in danger of filling 21-bits much less 31. That would be a massive shock and the compatibility headache would be terrible with UTF-16 breaking or today's software breaking that hard codes the assumption that UTF-8 should never go past 4-byte encodings.)

Re: Text Editor Data Structures

#76
post #72

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…

Sorry I meant codepoint/characters, but it would not suprise me if there existed an encoding or language where my wording would be technically correct, but I do not know of any such encoding. I also did not know that there exist more then 5 combinations in Unicode, but I'm not supprised and my implementation is probably buggy. But I do challange you to test how well your favourite editor (terminal emulator cough ) ha…

If it wouldn't surprise you then I think you should recalibrate your feelings about how surprising Unicode encodings are. There aren't very many of them, they haven't changed in a very long time, and they don't deal with any of the stuff that makes Unicode very complicated (collation, combination characters, etc). They just encode 21-bit integers, albiet sometimes in a highly convoluted way for backwards-compatibility reasons (UTF-16). It's not the kind of thing that needs to be estimated, or where a layer of FUD is warranted (as it kind of is with combination characters). When talking of codepoints, it's just "up to 4 bytes", high confidence, nothing more to it.

Re: Text Editor Data Structures

#77

There are tons of articles about plain text editor data structures, but what about rich text editor data structures? Let's say i want to implement a text editor that can have bold, italic, underline, etc text but also be able to do automatic word breaking, align paragraph text to left/middle/right, insert images and/or other objects, have floating images and/or other objects around which the other (non floating) text…

I am pretty sure that Write for Win3.1 used the Rich Edit control, or an early, non-public pre-cursor. Here are the Win32 docs: https://learn.microsoft.com/en-us/windows/win32/controls/ric... The more I read about this control, the more I learn about its insane feature set! Microsoft continues to make significant improvements to a version that is only shipped with Microsoft Office -- not available from a barebones Wi…

RichEdit appeared in Win95. It was written for the Win95 Email app.

The TOM stuff was added later when the MSWord people took over ownership.

Re: Text Editor Data Structures

#78
post #6

Earlier quoted context omitted.

It's not actually that different or complicated if you're already doing proportional plaintext rendering -- you need to store style attributes for a range of text, and you need to support different heights per line. The real complexity is rendering all of unicode properly, and supporting international fonts, bidi layout, vertical text, etc.

I think unicode, fonts, etc would be an issue even with a plain text editor anyway. The "styling a range of text" is something i thought but you still need to somehow associate the text with the range - and vice versa - and this doesn't handle things like inserting images and other types of objects since these aren't text. You could have a document be a series of "paragraphs", each being a series of "elements" with e…

Start and end of a selection would be nodes in the tree. The algorithm to find all the selected nodes is already part of the renderer, as the renderer has to implement traversal of nodes in text order as well.

Re: Text Editor Data Structures

#79
post #56

Earlier quoted context omitted.

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…

Isn't this just utf8 without information on how many of the following bytes belong to the glyph?

Re: Text Editor Data Structures

#80
post #79
post #56

Earlier quoted context omitted.

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…

Isn't this just utf8 without information on how many of the following bytes belong to the glyph?

It's more compact than UTF-8 because fewer bits are used for the encoding itself. There are 24 bits, and only 3 bits are used as part of the encoding, with the other 21 bits representing the code-point. (Precisely the number we need to represent all Unicode).

In UTF-8, a 3-byte encoding uses 8-bits as part of the encoding, a full byte worth of bits for the encoding itself, leaving only 16-bits for the codepoint. If you need higher code-points you need to use 4 bytes, where 11 bytes are the encoding and 21 bytes are the codepoint.

So UTF-8 is space efficient for ASCII, but ~1/3 of the bits are used for the encoding in for non-ASCII, versus a fixed 1/8 of the bits used for the encoding above for all 1-3 bytes. The above has a fixed 12.5% space overhead over raw codepoints. UTF-8 has 12.5% only for ASCII, and ~33% overhead for everything else.

Although it is not self-synchronizing like UTF-8, you can synchronize a reliable stream by holding a buffer of the previous byte. If the previous byte's value is >=0x80, the current byte is part of the same character. If it's That said, most sane protocols will prefix a string with a length (in bytes), so self-synchronization is not always an issue.

Post reply on HN