Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Text Editor Data Structures

cdacamar.github.io

Post reply on HN
Print view View original

31–40 of 81 posts

Re: Text Editor Data Structures

#31

Post by WorldMaker »

starfreakclone wrote: post #9
KerrAvon wrote: 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.

Indeed, you could even use a piece tree just like in the blog but you store additional information in each piece which tell the renderer how to layout the associated text. My understanding is that most rich text editors represent the text as a node-based tree anyway.

Some early rich text editors never used a tree representation for formatting represented the formatting as "control character sequences". This was part of why some people loved WordPerfect so much because you could toggle a view of all the control characters and just delete/copy/paste them like any other text in the same document.

It's basically how the classic RTF format [1] works, and things like VT100/ANSI escape codes in terminals. It's kind of like the difference between imperative code and declarative code: "this character sequence means toggle the state of bold" versus "this node of characters is bold".

[1] https://docs.fileformat.com/word-processing/rtf/

Re: Text Editor Data Structures

#32

Post by cmrdporcupine »

phildenhoff wrote: post #19

Thanks to this article, I learned that the core data structure for VSCode's text is written in TypeScript[0]. I, uh, I knew VS Code was written in TypeScript but I didn't realise _all_ of it was. It's crazy to think that the editor works as well as it does! [0]: https://github.com/microsoft/vscode/tree/main/src/vs/editor/...

I used a red-black tree written in JS over 15 years ago at a job where I needed to use lower bound and range operations for nodes in a pivot-table type dashboard for telecoms metrics. I was actually blown away at the time at how it actually performed rather decently, and this is back in the pre-Chrome Firefox & IE6&IE7 days.

Now in the world of V8 and JavaScriptCore, I don't think it's crazy at all. So much work has gone into JS runtime optimization. For heavily concurrent and memory intensive workloads, I can imagine problems though.

Re: Text Editor Data Structures

#33

Post by nsajko »

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

Re: Text Editor Data Structures

#34

Post by rcoveson »

WorldMaker wrote: post #30
rcoveson wrote: post #25

Earlier quoted context omitted.

> So one Unicode character can be up to 5 bytes long and take up the same canvas space as 3 characters. 5 bytes? In what encoding?

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"?

Re: Text Editor Data Structures

#35

Post by rcoveson »

lelanthran wrote: post #28
rcoveson wrote: post #25

Earlier quoted context omitted.

> So one Unicode character can be up to 5 bytes long and take up the same canvas space as 3 characters. 5 bytes? In what encoding?

> 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"?

Re: Text Editor Data Structures

#38

Post by starfreakclone »

nsajko wrote: 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...

Thank you for the pointer! I was actually not aware of this paper at all, which is why it was not included here (not sure how I missed it). I'll be sure to push a revision to the blog which mentions this paper.

Re: Text Editor Data Structures

#40

Post by cstrahan »

rcoveson wrote: post #34
WorldMaker wrote: post #30

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"?

The original quote for reference:

> So one Unicode character can be up to 5 bytes long and take up the same canvas space as 3 characters.

FWIW, I didn't read that as suggesting an upper bound of 5 bytes, but rather as an example using arbitrary numbers: N bytes of code units could, depending on the font providing the glyph(s) for the respective grapheme(s), could be rendered at M times the size of, say, the letter A, where N != M -- despite the font otherwise being monospaced. Which is just another way of saying that you must consult the font for the character widths involved.

I think you're reading that quote as an assertion that:

    For any grapheme G, G can be encoded in at most 5 bytes.
While what I think was being said was:

    There exists a grapheme G, where G is encoded in 5 bytes, and the respective glyph happens to be displayed at 3 times a single character (e.g. the letter A), despite the font otherwise being monospaced. Therefore you *must* consult the font for each glyph to correctly determine character widths.
Post reply on HN