Live data from Hacker News

Text Editor Data Structures

cdacamar.github.io

11–20 of 81 posts

Re: Text Editor Data Structures

#11

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 believe most do use a DOM like structure for block level elements. For inline styling however they tend to not have separate nested nodes for each style (bold, italic, underline), and are closer to the old HTML4 tag with multiple properties for each style and don't nest them. It makes for much simpler code.

The docs for ProseMirror are a brilliant insight into how many of these editors are designed. ProseMirror maintains its own document model in parallel to the html DOM and rectifies one to the other as either changes.

For realtime collaborative rich text editors take a look at PeriText, they have a brilliant article explaining the CRDT structures used.

https://prosemirror.net

https://www.inkandswitch.com/peritext/

Re: Text Editor Data Structures

#12

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…

Checkout the cocoa class for this: https://developer.apple.com/documentation/foundation/nsattri...

Re: Text Editor Data Structures

#13
post #6

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…

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 each "element" being something like "text" (with a style), "image", etc. But then once tables enter the picture, you need to expand paragraphs to be of "table" type and each table cell is itself a self-contained "series of paragraphs" - and then start thinking about nested tables or images in tables!

Generalize that enough to avoid special cases inside special cases and you end up with more of a tree-like structure representing a DOM and less with a linear structure with range-based styling.

(of course, then again, i don't remember Write for Windows 3.1 having tables in the first place :-P but i'm interested if there are alternative approaches anyway)

EDIT: one thing i forgot to mention - and why i am curious about non-DOM-based approaches - is that one problem with the DOM approach is the selection: with a linear/range-based structure the selection is just one or two indices inside the range, but 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.e. only having some distant common ancestor and not necessarily at the same level).

Re: Text Editor Data Structures

#14
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…

I might have a way to simplify this?

A plaintext document is an array of chars, a richtext document is tree, which may or may not be well-formed.

Think about someone trying to bold semi-half of_a sentence_, and how MS Frontpage was made by smart people, it’s just really hard.

The most interesting thing lately is the HTML attribute `contenteditable`, and how it almost just kinda works! You still have to be full-stack to make something good, but that was an amazing improvement to the browser.

Re: Text Editor Data Structures

#15

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…

It seems like also Bravo, the first WYSIWYG-Editor, abiword and word used/use piece tables: https://en.wikipedia.org/wiki/Piece_table#Usage

Re: Text Editor Data Structures

#16
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…

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 pretty quickly as needed.

Re: Text Editor Data Structures

#17
post #14

Earlier quoted context omitted.

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…

I might have a way to simplify this? A plaintext document is an array of chars, a richtext document is tree, which may or may not be well-formed. Think about someone trying to bold semi-half of_a sentence_, and how MS Frontpage was made by smart people, it’s just really hard. The most interesting thing lately is the HTML attribute `contenteditable`, and how it almost just kinda works! You still have to be full-stack…

Yeah, that trying to bold half of a sentence - or even better, the middle of a sentence - is why i was wondering about simpler alternatives to DOM. Some time ago i toyed around with an HTML editor[0] (that one had to use a DOM anyway, but my question is for rich text editing in general - BTW the rectangles in the shot show a selection that goes across nodes) and doing something like that involved traversing all the nodes (going both down and up the node tree, starting from the cursor's starting position), finding the closest common ancestors under the selection, creating "B" siblings to them and then reparenting them under these new "B" nodes.

You can move a lot of that stuff to reusable methods but personally i find the whole "editing" aspect to be more involved than the "drawing" side - and also the one more likely to be different than a plain text editor - when dealing with DOM-like structures. Hence why i am interested to see what alternatives there are.

[0] https://i.imgur.com/jLlyNSS.png

Re: Text Editor Data Structures

#18
post #8

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…

Yes, I think your instinct to look at win32 APIs is a good one. Many structures in riched are public in headers, and of course you could reference Wine's implementation[1]. [1] https://source.winehq.org/git/wine.git/tree/HEAD:/dlls/riche...

That is neat, thanks. I didn't check RICHED itself but when i was toying around with an HTML editor a few years ago (see my other post) i did check out an HTML editor API that Microsoft had (i don't remember its name but it was used by, e.g., Joel Spolsky's CityDesk - IIRC the control itself was documented in the MSDN CDs that came with Visual Studio 6), from where i got the idea of using a two node pointers and a subrange index to represent a selection.

Re: Text Editor Data Structures

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

Re: Text Editor Data Structures

#20

Earlier quoted context omitted.

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…

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 that contains the image)?
Post reply on HN