8 ms·

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

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/images/objects wrap, etc. What would be the data structures for that? I can only think of trying to replicate something like the HTML DOM but i have a feeling something like Write for Windows 3.1 used a simpler data structure.

KerrAvon 3y ago
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.
- starfreakclone 3y ago
  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.
  - WorldMaker 3y ago
    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/ https://docs.fileformat.com/word-processing/rtf/
- badsectoracula 3y ago
  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).
  - b33j0r 3y ago
    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.
    - badsectoracula 3y ago
      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 https://i.imgur.com/jLlyNSS.png
- z3t4 3y ago
  You don't need any fancy data structures. 95% of the performance goes into glyph rendering. And with Unicode the performance gain from monospace fonts goes out the window as some Unicode characters are very large, and not only that they also take up many bytes. So one Unicode character can be up to 5 bytes long and take up the same canvas space as 3 characters. You also need to read ahead as there are combination characters, for example a smiley combined with the color brow becomes a brown smiley. I've blogged about implement support for Unicode in an editor here: https://zäta.com//en/blog/editor10.htm https://xn--zta-qla.com//en/blog/editor10.htm
  - rcoveson 3y ago
    > 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?
    - dredmorbius 3y ago
      There was an emoji example of length seven posted to HN recently: <https://news.ycombinator.com/item?id=36159443 https://news.ycombinator.com/item?id=36159443>
    - jychang 3y ago
      Emojis with skin color, mostly
      - rcoveson 3y ago
        No, that's a ZWJ sequence. Those can be arbitrarily long. Doesn't explain where "5 bytes" comes from.
        throwaway2037 3y ago
        Is there a maximum number of "zero-width joiner" (ZWJ) sequences that can be combined to create a single-width emoji? (Yes, I know the term "single-width" is a loaded term.) I cannot find a precise answer.
coldpie 3y ago
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/riched20 https://source.winehq.org/git/wine.git/tree/HEAD:/dlls/riche...
- badsectoracula 3y ago
  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.
convolvatron 3y ago
its probably instructive to look at elisp text properties. not so much that its a great system - but it raises some messy questions about how to operate on substrings that have different sets of properties
samwillis 3y ago
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 <font> 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://prosemirror.net https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/
macrael 3y ago
Checkout the cocoa class for this: https://developer.apple.com/documentation/foundation/nsattributedstring https://developer.apple.com/documentation/foundation/nsattri...
legulere 3y ago
It seems like also Bravo, the first WYSIWYG-Editor, abiword and word used/use piece tables: https://en.wikipedia.org/wiki/Piece_table#Usage https://en.wikipedia.org/wiki/Piece_table#Usage
kjs3 3y ago
Perhaps look at how (Open,Libre)Office does it to support ODT format (e.g. OASIS Open Document Format)?
thangalin 3y ago
RichTeXtFX[1] has these abilities[2] along with demo code[3] that provides an entry point for sleuthing. My text editor, KeenWrite[4], uses RichTeXtFX, but takes a different approach due to its usage of inline variable references. Rather than edit the document in a WYSIWYG-like fashion, users edit the Markdown document as plain text then export as PDF by selecting a theme to apply for typesetting. This cleanly separates content from presentation. The "themes" video tutorial demonstrates how theme selection works.[5] [1]: https://github.com/FXMisc/RichTextFX/tree/master/richtextfx/src/main/java/org/fxmisc/richtext https://github.com/FXMisc/RichTextFX/tree/master/richtextfx/... [2]: https://gluonhq.com/presenting-a-new-richtextarea-control/ https://gluonhq.com/presenting-a-new-richtextarea-control/ [3]: https://github.com/gluonhq/rich-text-area/blob/master/samples/src/main/java/com/gluonhq/richtextarea/samples/RichTextEditorDemo.java https://github.com/gluonhq/rich-text-area/blob/master/sample... [4]: https://github.com/DaveJarvis/keenwrite https://github.com/DaveJarvis/keenwrite [5]: https://www.youtube.com/watch?v=3QpX70O5S30&list=PLB-WIt1cZYLm1MMx2FBG9KWzPIoWZMKu_&index=9 https://www.youtube.com/watch?v=3QpX70O5S30&list=PLB-WIt1cZY...
eludwig 3y ago
Many older word processors (the only ones I'm familiar with) used style "runs", which are simply an array of structs that contain startPosition, endPosition (or length) and then a bunch of style info in whatever way makes sense to them. I worked on Ready,Set,Go! back in the day and also wrote my own styled editor for the Mac in the 90's. One interesting thing about this is that you could use a lazy "adjustor" to remove duplicate or overlapping styles. No need to worry about it during typing or selecting. A low priority task could analyze the runs and fix them up as needed and no one was the wiser. IMO, the hardest part about writing a word processor back then was font management. You had to construct width tables to be able to compose lines properly. This generally involved a bunch of poorly documented APIs and peering into opaque data structures.
chaoz_ 3y ago
You can always check Qt TextEdit source code ;)
throwaway2037 3y ago
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/rich-edit-controls 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 Win7/10/11 install. Read more here: https://devblogs.microsoft.com/math-in-office/using-richedit-for-text-processing/ https://devblogs.microsoft.com/math-in-office/using-richedit... Rich Edit control also supports the Text Object Model, which is very powerful. Read more here: https://learn.microsoft.com/en-us/windows/win32/api/tom/nn-tom-itextdocument https://learn.microsoft.com/en-us/windows/win32/api/tom/nn-t...
- badsectoracula 3y ago
  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/word2rtf/formats/write.txt https://web.archive.org/web/20130831064118/http://msxnet.org...
  - throwaway2037 3y ago
    You are right! I had Write mixed up with Wordpad.
- canucker2016 3y ago
  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.

KerrAvon 3y ago

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.

starfreakclone 3y ago
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.
- WorldMaker 3y ago
  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/ https://docs.fileformat.com/word-processing/rtf/
badsectoracula 3y ago
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).
- b33j0r 3y ago
  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.
  - badsectoracula 3y ago
    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 https://i.imgur.com/jLlyNSS.png
z3t4 3y ago
You don't need any fancy data structures. 95% of the performance goes into glyph rendering. And with Unicode the performance gain from monospace fonts goes out the window as some Unicode characters are very large, and not only that they also take up many bytes. So one Unicode character can be up to 5 bytes long and take up the same canvas space as 3 characters. You also need to read ahead as there are combination characters, for example a smiley combined with the color brow becomes a brown smiley. I've blogged about implement support for Unicode in an editor here: https://zäta.com//en/blog/editor10.htm https://xn--zta-qla.com//en/blog/editor10.htm
- rcoveson 3y ago
  > 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?
  - dredmorbius 3y ago
    There was an emoji example of length seven posted to HN recently: <https://news.ycombinator.com/item?id=36159443 https://news.ycombinator.com/item?id=36159443>
  - jychang 3y ago
    Emojis with skin color, mostly
    - rcoveson 3y ago
      No, that's a ZWJ sequence. Those can be arbitrarily long. Doesn't explain where "5 bytes" comes from.
      - throwaway2037 3y ago
        Is there a maximum number of "zero-width joiner" (ZWJ) sequences that can be combined to create a single-width emoji? (Yes, I know the term "single-width" is a loaded term.) I cannot find a precise answer.

coldpie 3y ago

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/riched20 https://source.winehq.org/git/wine.git/tree/HEAD:/dlls/riche...

badsectoracula 3y ago
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.

convolvatron 3y ago

its probably instructive to look at elisp text properties. not so much that its a great system - but it raises some messy questions about how to operate on substrings that have different sets of properties

samwillis 3y ago

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 <font> 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://prosemirror.net https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/

macrael 3y ago

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

legulere 3y ago

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

kjs3 3y ago

Perhaps look at how (Open,Libre)Office does it to support ODT format (e.g. OASIS Open Document Format)?

thangalin 3y ago

RichTeXtFX[1] has these abilities[2] along with demo code[3] that provides an entry point for sleuthing. My text editor, KeenWrite[4], uses RichTeXtFX, but takes a different approach due to its usage of inline variable references. Rather than edit the document in a WYSIWYG-like fashion, users edit the Markdown document as plain text then export as PDF by selecting a theme to apply for typesetting. This cleanly separates content from presentation. The "themes" video tutorial demonstrates how theme selection works.[5] [1]: https://github.com/FXMisc/RichTextFX/tree/master/richtextfx/src/main/java/org/fxmisc/richtext https://github.com/FXMisc/RichTextFX/tree/master/richtextfx/... [2]: https://gluonhq.com/presenting-a-new-richtextarea-control/ https://gluonhq.com/presenting-a-new-richtextarea-control/ [3]: https://github.com/gluonhq/rich-text-area/blob/master/samples/src/main/java/com/gluonhq/richtextarea/samples/RichTextEditorDemo.java https://github.com/gluonhq/rich-text-area/blob/master/sample... [4]: https://github.com/DaveJarvis/keenwrite https://github.com/DaveJarvis/keenwrite [5]: https://www.youtube.com/watch?v=3QpX70O5S30&list=PLB-WIt1cZYLm1MMx2FBG9KWzPIoWZMKu_&index=9 https://www.youtube.com/watch?v=3QpX70O5S30&list=PLB-WIt1cZY...

eludwig 3y ago

Many older word processors (the only ones I'm familiar with) used style "runs", which are simply an array of structs that contain startPosition, endPosition (or length) and then a bunch of style info in whatever way makes sense to them. I worked on Ready,Set,Go! back in the day and also wrote my own styled editor for the Mac in the 90's. One interesting thing about this is that you could use a lazy "adjustor" to remove duplicate or overlapping styles. No need to worry about it during typing or selecting. A low priority task could analyze the runs and fix them up as needed and no one was the wiser. IMO, the hardest part about writing a word processor back then was font management. You had to construct width tables to be able to compose lines properly. This generally involved a bunch of poorly documented APIs and peering into opaque data structures.

chaoz_ 3y ago

You can always check Qt TextEdit source code ;)

throwaway2037 3y ago

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/rich-edit-controls 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 Win7/10/11 install. Read more here: https://devblogs.microsoft.com/math-in-office/using-richedit-for-text-processing/ https://devblogs.microsoft.com/math-in-office/using-richedit... Rich Edit control also supports the Text Object Model, which is very powerful. Read more here: https://learn.microsoft.com/en-us/windows/win32/api/tom/nn-tom-itextdocument https://learn.microsoft.com/en-us/windows/win32/api/tom/nn-t...

badsectoracula 3y ago
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/word2rtf/formats/write.txt https://web.archive.org/web/20130831064118/http://msxnet.org...
- throwaway2037 3y ago
  You are right! I had Write mixed up with Wordpad.
canucker2016 3y ago
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.