An idea of Rich-Text editor implementation

[Anton Paramonov]

Hi Joseph!

I'm Anton Paramonov from Project Volna team. I'm one of the developers
of the Odessa Project (http://odessa.projectvolna.com:8010/wave/) with
functionality similar to Google Wave. Perhaps you remember a message
about us (http://groups.google.com/group/sharejs/browse_thread/thread/
f08241d87c16e9b2) not long time ago. Now we're starting the
development of our Rich-Text editor based on sharejs. Sharejs is an
excellent tool that helped us to implement all the necessary
functionality quickly. And we're watching the development of your
project with a great interest and attention.


I'd appreciate if you could give us some directions or comment on our
idea of designing Rich-Text editor. I suppose that you know how Rich-
Text editor is implemented in Google Wave, but let me outline some
details of its architecture.


Very simplified it looks like this data model - every blip contains:

1. A single text string with all text of the blip
2. An array of style annotations (markers), where each annotation
defines a region (substring) and some visual style (text color, bold
typeface, font size etc.) that should be applied to the text region.


Here is a JSON "illustration" :)

Google_Wave_Blip_Model = {
blip_text: "the whole text of blip",
blip_annotations: [
{
start: 4,
end: 9,

style: "bold"
},
{
start: 10,
end: 14,
style: "italic"
}
]
}

The client part of Google Wave according to the user input generates
OT operations over that model. Then client sends operations to the
server, applies operations received from server to that model and
correct blip's html that is shown to the user in editor.


To implement this approach we have all required tools, thanks to
Sharejs :)

But as we see there are complications in this architecture related to
maintaining of style annotations. Each server or user produced OT
operation (even typing of a single letter) requires checks of all
recently defined annotations to maintain them according the current OT
operation. This can result into shifting annotation left or right,
enlarging annotation text region, complete deletion of the annotation
from the blip and so on... This maintenance is required both on server
and client side and as it turns out, it's not so simple and obvious
task at all.


Our idea allows us to avoid all that maintenance of style annotations
and simplifies the implementation of rich-text editor. The idea is to
use a data of different model - for each blip we define:

1. A plain array of objects, let's call it array of TextFragment
objects

2. Each TextFragment contains:
a) A single text string that contains a part of blip's text.
b) A set of styles (bold typeface, italic, text color etc.) that is
assigned to this part of text.

Initially blip will be represented with a single item array with a
TextFragment object. That object contains users text input until
someone applies some styling to it. Let's consider a simple case when
user selects the second half of the blip's text and applies bold
typeface to the selection. One more "picture" before applying of
style:


Our_Blip_Model = {
text_fragments: [
{
text_part: "the text of blip",
styles: []
}
]
}

And after applying of style:

Our_Blip_Model = {

text_fragments: [
{
text_part: "the text ",
styles: []
},
{
text_part: "of blip",
styles: ["bold"]

}
]
}

This case should produce the following list of operations:

1. Split the initial TextFragment object in two objects (so our blips'
array will be contains two items where first TextFragment will contain
the first half of the blip's text and the second object will have the
second half of text.

2. Assign a bold typeface style to second TextFragment object.

More complex cases of text and style manipulation we can decompose and
reduce to some combination of described 2 points. Hence implementation
of those points will let us avoid maintenance of a set of style
annotation.


Point 2 is quite obvious and can be easily done with one of sharejs
JSON-Operations. But point 1 brings us some troubles. Splitting of
TextFragment object must be performed in a single OT operation. And
other OT operations must be correctly transformed against this
splitting operation. Otherwise, OT operations created before splitting
could be applied to the wrong part of text then it's expected. So we
have to implement new OT operation that can be applied to array of our
TextFragment objects and extend the set of supported sharejs
operations.


Joseph, your opinion or maybe some piece of advice is very valuable
for us, since you are a very experienced specialist in area of OT then
any of us. Possible that I'm missing some less complicated way of
editor implementation or my idea has some conflicts or complications.
It would be absolutely magnificent if we could communicate in Google
Wave, I'm convinced that would be very useful for us.


Sincerely,
Anton Paramonov
Project Volna
anton.pa...@gmail.com

[Joseph Gentle]

Thats cool!

Um, yeah - I know what you mean. I had a good chat with Jeremy awhile
ago about this exact problem (Jeremy wrote the JSON OT type). We came
up with the same problems you did. My opinion is that the JSON OT type
is insufficient for rich text editing. I think we need another OT
type, separate from JSON, specifically to express rich text. - and
which correctly captures the semantics of rich text documents.

I've written the whole architecture in such a way that adding types is
'easy' - basically, you just add more types into src/types/. Types
define a few functions (transform, apply, etc). Once you've defined a
type you can register it in src/types/index.coffee for nodejs and add
it to the cakefile to include it in the browser javascripts.

I would be super happy if you're keen to take a stab at this - I <3
pull requests.

The equivalent of the google wave rich text type looks like this:

['some normal text', [{bold:true}], 'some bold text', [{bold:null,
italics:true}], 'some italicised text']

Operations can be similar to normal text operations:

[{position:100, insert:'hi there'}]

I don't know what the behaviour should be if you insert text at the
end of an annotated region. Like, if you insert text after a bolded
region should it get bolded automatically? Maybe operations have to
specify all the annotations on text they're inserting. Unfortunately,
that means that as you type in a bolded region, every operation needs
to specify that the text is bold. Google wave inherits annotations,
but the logic for that is really complicated.

What do you think?

-Joseph

[Anton Paramonov]

Thanks!
more below...

On 24 окт, 10:52, Joseph Gentle <jose...@gmail.com> wrote:
> Thats cool!
>
> Um, yeah - I know what you mean. I had a good chat with Jeremy awhile
> ago about this exact problem (Jeremy wrote the JSON OT type). We came
> up with the same problems you did. My opinion is that the JSON OT type
> is insufficient for rich text editing. I think we need another OT
> type, separate from JSON, specifically to express rich text. - and
> which correctly captures the semantics of rich text documents.

Joseph may I read that chat with Jeremy somewhere? I'm eager to learn
your ideas about OT for Rich-Text.

>
> I've written the whole architecture in such a way that adding types is
> 'easy' - basically, you just add more types into src/types/. Types
> define a few functions (transform, apply, etc). Once you've defined a
> type you can register it in src/types/index.coffee for nodejs and add
> it to the cakefile to include it in the browser javascripts.

ok, digging there!

>
> I would be super happy if you're keen to take a stab at this - I <3
> pull requests.
>
> The equivalent of the google wave rich text type looks like this:
>
> ['some normal text', [{bold:true}], 'some bold text', [{bold:null,
> italics:true}], 'some italicised text']
>
> Operations can be similar to normal text operations:
>
> [{position:100, insert:'hi there'}]
>
> I don't know what the behaviour should be if you insert text at the
> end of an annotated region. Like, if you insert text after a bolded
> region should it get bolded automatically? Maybe operations have to
> specify all the annotations on text they're inserting. Unfortunately,
> that means that as you type in a bolded region, every operation needs
> to specify that the text is bold. Google wave inherits annotations,
> but the logic for that is really complicated.
>
> What do you think?

That's a good question. As I see we should be able to realize both
variants - insert text at the end of 'some normal text' and at the
beginning of 'some bold text'. The decision on where to put the new
text should be made by editor before any OT processing depending on
user behavior. I can imagine a couple of cases how to put text right
at the border of different style blocks:

1. Always put text in the left style block. In case when user first
selects some different style (than in the left style block) and then
types some text, we have to create a new third block. Something like
that: ['some normal text', [{bold:null, underlined: true}], new text,

[{bold:true}], 'some bold text', [{bold:null, italics:true}], 'some

italicised text']. And we need a little optimization (also in editor):
do not create new block if the style of new text matches style to the
left or right of the border.

2. A bit more advanced variant: to take in account position of the
cursor before user started to type text. So if user moved cursor on
the left of the border of styles (user continues to type text), then
we put new text in the left block of styles. If user returns cursor
back from the right side (possibly to type one more word or correct
the beginning of the style block), then we put new text in the right
block. That would be quite easy for user to control that behavior. In
case when user places cursor at the border with mouse click or screen
touch we can follow point 1.

To submit text insertion with this approach we need some more
complicated API than just [{position:100, insert:'hi there'}]. Or it
could be that API will remain as JSON operations, but for Rich-Text
document should be represented with more complex model then just a
string of text. For example an array of objects of some type like I
described TextFragments before, or like your array of object of
different types: annotation and text. And for those models we need
some OT operations not only to create, but also to mutate (split and
merge) objects used in the Rich-Text document model.

Does it make sense?
- Anton

> > anton.paramon...@gmail.com

[Joseph Gentle]

2011/10/27 Anton Paramonov <anton.pa...@gmail.com>:

> On 24 окт, 10:52, Joseph Gentle <jose...@gmail.com> wrote:
>> Um, yeah - I know what you mean. I had a good chat with Jeremy awhile
>> ago about this exact problem (Jeremy wrote the JSON OT type). We came
>> up with the same problems you did. My opinion is that the JSON OT type
>> is insufficient for rich text editing. I think we need another OT
>> type, separate from JSON, specifically to express rich text. - and
>> which correctly captures the semantics of rich text documents.
>
> Joseph may I read that chat with Jeremy somewhere? I'm eager to learn
> your ideas about OT for Rich-Text.

Unfortunately, I think a lot of the juicy stuff happened in person.

This is a pretty good intro to how the OT stuff works in general
(might be too basic):
http://www.youtube.com/watch?v=3ykZYKCK7AM

But - definitely watch this. This is Christian talking about how he
thinks wave could have done OT better:
http://www.youtube.com/watch?v=zo8uGlqQaCo - start at about 15 minutes.

>> I've written the whole architecture in such a way that adding types is
>> 'easy' - basically, you just add more types into src/types/. Types
>> define a few functions (transform, apply, etc). Once you've defined a
>> type you can register it in src/types/index.coffee for nodejs and add
>> it to the cakefile to include it in the browser javascripts.
>
> ok, digging there!

Cool.

Yep, though this optimisation shouldn't go in the editor. In general,
if you're describing text in blocks and you have to explicitly split /
join blocks, the OT stuff gets really hairy. You're much better off
having that stuff be automatic.

Wave did this by making annotation boundaries not take up space, so to
speak. So like, say you have this document:

<bold>abcde</bold><bold>fghij</bold>

... Thats an identical document to this:

<bold>abcdefghij</bold>

If you want to insert in the middle of that text, your operation says:

{Insert:'hi' position: 5}

The text doesn't take up space in the sense that when you specify a
position, the number just says how many characters to skip. Annotation
boundaries don't need to be skipped.

Of course, the downside of this is that you have to be clever if you
want to insert characters between tags or something. So, something
like:

{insert:[</bold>hi<bold>], position: 5} to insert unbolded text in the
middle of the document.

> 2. A bit more advanced variant: to take in account position of the
> cursor before user started to type text.  So if user moved cursor on
> the left of the border of styles (user continues to type text), then
> we put new text in the left block of styles. If user returns cursor
> back from the right side (possibly to type one more word or correct
> the beginning of the style block), then we put new text in the right
> block. That would be quite easy for user to control that behavior. In
> case when user places cursor at the border with mouse click or screen
> touch we can follow point 1.
>
> To submit text insertion with this approach we need some more
> complicated API than just [{position:100, insert:'hi there'}]. Or it
> could be that API will remain as JSON operations, but for Rich-Text
> document should be represented with more complex model then just a
> string of text. For example an array of objects of some type like I
> described TextFragments before, or like your array of object of
> different types: annotation and text. And for those models we need
> some OT operations not only to create, but also to mutate (split and
> merge) objects used in the Rich-Text document model.

I think we need something different from the text API (so we can
describe style annotations and stuff), and different from the JSON
API. (Using the JSON API we'll need to split and join annotation
regions, and that'll get confusing fast).

Does that make sense?

Joseph

[Anton Paramonov]

Hi Joseph!

I've got a sequel of our story about implementation of Rich-Text Editor with OT and ShareJS. Let me remind where we started from. Initially we decided to use a special model for our editor. It looks like that: 

Editor_Model = [
  {
    text: "This is the ",
    format: {
      bold: false
    }
  },
  {
    text: "bold text",
    format: {
      bold: true
    }
  },
  {
    text: " in editor",
    format: {
      bold: false
    }
  }
]

With this model we supposed to use JSON OT operations already implemented in ShareJS... plus one more OT operations for splitting elements of the model array.

However that approach didn't solved all the problems. In some situations of concurrent work if one user deletes an item in model array the other users could lose their OT operations sent to to the same item. And splitting OT operation gave no help with that. If we would not delete empty model items (with no text in "text" field) then in a short period of time we could collect a lot of items that use resources but do not contain any valuable info. And there is no evident way how we should finally drop them.

And here we've got the meaning of your idea Joseph, that rich-text editor needs some special API and operation then just JSON oriented. Actually, problems with use of JSON operations where caused by the fact that we addressed our operations by the index in model array. So we need optations that will not explicitly point to an item in model array - hence we get OT operations for rich-text very similar to plain text.

Now we've got the following - the editor model remained the same array with the same type objects and 4 new special OT operations for rich-text formatting: 

1. Operation to insert text with formatting. This operation should be used when user types some text in editor. Operation arguments:
1. Position in model text (where to insert new text. Note please, that this position could point, for example, in text of second item of model array if the value of position is greater then text length of the first item)
2. Text that should be inserted
3. Text formatting. This is the object of the following structure: { bold: true; italic: true; height: 12px}. This matches the objects in model array items in field "format".
   
   
2. Operation to delete text. This operation is used when user deletes something in the editor. Operation arguments:
1. Position in text
2. The text that we delete
3. The format of the deleted text. A similar structure that is used in text inserting operation.
   
   
3. Applying formatting. If the user selects some part of the text and makes text bold or italic, then this operation should be used. Operation arguments:
1. Position in the text
2. Length in symbols of the selected text region
3. The format of the text that should be applied. Same structure as in previous operations.
   
   
4. Formatting clearing. Reverse operation to the previous one. Arguments are also the same. 

The arguments of that operations where made excessive intentionally. Using only that arguments we can simply generate reverse operations and hence we can implement undo/redo operations for the editor.

Now we can maintain our model in the most efficient way, and hide implementation in methods for applying our OT operations to the document's snapshot. ShareJS has everything for realization of such functionality. Let's for example take the following situation: in the editor we have the text equal to the model which is given above, that is:

This is the bold text in editor

And the user deletes the text " bold text in" while editor generates appropriate text delete operation. Being applied this operation completely deletes the second item from the model array and merges the first and the third items. Finally, we receive the following model: 

Editor_Model = [
  {
    text: "This is the editor",
    format: {
      bold: false
    }
  }
]

That's what needed to achieve. I'll be glad to answer any questions concerning this idea and ways of its implementation, there are some trick & traps. With some luck and after some experiments I'll publish our editor for your testing ;) 

Cheers!

Anton

[Joseph Gentle]

Awesome :D

Looking forward to it.

-J

[Anton Paramonov]

Here is a fork from ShareJS 0.5.0-pre with our OT operatios:
https://github.com/rizzoma/ShareJS There are no Rich-Text editor yet,
but watch for next updates!

[Joseph Gentle]

I noticed that - though all the documentation is in russian.
https://github.com/rizzoma/ShareJS/blob/master/src/types/text-formatted.coffee

It also looks like you guys don't have any tests. I highly recommend
adding some at some stage - I found an enormous number of bugs in all
of sharejs's other OT types using unit tests & a random op generator.

-J

[Anton Paramonov]

Yes, that's right, Joseph, it's not an "official" release actually... Google translator copes with that comments pretty well so we decided to show something right now, then everything but later...

About tests - we've got them but they heavily depend on our infrastructure... so they can't be run without our server framework that is intensively developed right now and I think hardly would be interesting to open source community. But there are also good news - we've started to separate our editor into a new "clean" project that will be simply plugged in ShareJS. So... stay tuned :)

2012/2/14 Joseph Gentle <jos...@gmail.com>

[Anton Paramonov]

Hi guys!

Here is a new update of rich-text editor: https://github.com/rizzoma/ShareJS
Now there is a simple server that allows run one instance of editor
for multiple users.

Installation is very simple - just get the project from GitHub,
execute "npm install ." in project directory (or install node modules
mentioned in /package.json file) and run server with bin/exampleserver
script. After server start open that page with editor in your
browser(s) - http://localhost:8000/hello-rizzoma.html

Few more words about this sample: that code was stripped out from our
current rizzoma.com project. So it's far from being laconic, optimal,
cross-browser and suitable for immediate usage. And comments are not
in English yet, sorry. However we'd like to push and support that
project to become something much more, if community will accept that.

Hope you'd like it,
Anton

P.S. Nodejs version 0.4.* required
P.P.S Kudos to Joseph! :)

[SlNPacifist]

Pushed cucumber tests into repo.

[Henri Bergius]

Hi!

On Wednesday, 22 February 2012 09:12:43 UTC+1, Anton Paramonov wrote:

Here is a new update of rich-text editor: https://github.com/rizzoma/ShareJS
Now there is a simple server that allows run one instance of editor
for multiple users.

Looks very nice, we just had a little editing session here :-)

I wonder how difficult it would be to make this work with a standard contentEditable (like my Hallo Editor http://bergie.github.com/hallo/) instead of the custom Chrome-only editor implementation used now.
 

Anton

/Henri

[Anton Paramonov]

Well, that wouldn't be a problem, ShareJS is developed in a consistent and clear way. Just catch the idea of how to apply OT based interaction :)