Hi Marijn, I'm curious if you've taken note of substance.io, and what you think of their composer and viewer, which similarly keeps the structure and views separate.
I'm not related to substance.io, just someone curious about editors on the web, and so have kept track of various options. Prosemirror looks very promising.
I've been working on a similar project based on the quill editor [1], which is in turn based on the rich-text OT library [2]. Initially, I thought to wire this all up using the sharejs project [3], but never could quite grok that codebase.
Instead, I've been working on a similar system to one you describe, with changes applied in order based on sequential version number, and concurrent updates forced to "rebase" against earlier changes (not yet open-sourced).
A question:
> Because applying changes in a different order might create a different document, rebasing isn't quite as easy as transforming all of our own changes through all of the remotely made changes.
Can you explain more about how you arrived this conclusion? From my understanding, a correct transform function should allow exactly this, according to transformation property 1 [4]. Perhaps your algorithm doesn't exactly satisfy this property; what characteristics does it have instead?
> From my understanding, a correct transform function should allow exactly this
A correct OT transform, yes. But I'm not using OT's invariants, so this is not something my transforms do. For example, in my system, if you have "insert X at pos 5" and "insert Y at pos 5", the document will contain "XY" or "YX", depending on which arrived first.
Sorry ShareJS is such a mess right now. I did a bunch of work to make it into a kind of OT-backed database to power derbyjs. Its very much straddling two worlds at the moment and I think its doing a bad job of both.
How well does this approach scale to high-concurrency situations? The more active participants there are, the more often you'd be rejecting client changes and ask them to rebase, causing extra round-trips. It sounds like when a critical number of participants is reached, you'll create change requests more quickly than you can handle them. If each participant has a latency of 100ms to your server, and say you have 10 participants making 2 changes per second each, will you experience some sort of congestion?
On a similar note, what happens if you have two active clients, one with say 100ms latency and another with 500ms? If the 100ms client will be typing continously with 4 characters per second, the changes of the 500ms client won't get through until the 100ms one stops typing, right?
I realize these might not be much of a real issues in practise, but did you consider such cases? In particular, is there something in your machinery that prevents the server from doing the rebase, as opposed to sending it back to the client to do it?
As for references, I went all the way and implemented distributed OT in Gobby (https://github.com/gobby/gobby). It's somewhat doable for plain text editing, but going beyond that inflates the complexity very quickly. It gives you some nice properties like authorship tracking even across undo operations. However, the complexity goes with at least n^2 with the number of participants, so there is also an upper limit in the number of active participants that's reached rather sooner than later (even though I never actually found out where it is in practise).
I did consider such cases. My current theory is that it is unlikely that clients will keep up a torrent of updates so constant that there'll be a lag of more than, say, a second before any given change gets through. But if this would turn out to be an issue, you could have the server implement some kind of fairness algorithm by slightly delaying clients that recently got their changes through and prioritizing those that made a few unsuccessful tries.
This looks extremely interesting. I have looked at several JS-based text editors, and so far none have matched my requirements. ProseMirror sounds like something I have thought about as a possible approach. Well, not so much the collaboration part. I've had hard time just trying to reason about DOM vs document tree, contenteditable vs trying to match writer's intentions, and so on.
This pattern matching of user's intentions and using DOM diffing to find out what actually happened feels right to me, especially using persistent data structures. Handling parts of the document as a tree and others as a list seems like decision that could probably make development much easier as you'd know, I imagine. I have been wondering about how to do structured inline element annotations, and lists inside block level elements certainly looks it could work.
Also, this relates to what LightTable folk's talked about in IDE as a value [1].
I'm definitely going to back this. That said, I'd like to know more about what is actually going to (hopefully) be open sourced.
Is this a stand alone app with plugins, a collection of components, or a library to build your own editor?
Is it written in purely JavaScript version 5, 6, or something else?
What about the persistent data structure implementation?
How are user intent patterns modeled, ie. what would it entail to build your own?
Have you thought about intermixing document tree with editors for other types of content, like tables and media?
This is a library providing the client-side editor component, with a bunch of modules (UI, collaboration), and a well-documented API through which to connect it to surrounding code.
It is written in ES6. The persistent data structures are not very involved, just objects that never get mutated after their initial construction.
First of all, this looks truly awesome! I've spent a lot of time recently looking at the available open source editors, and with the exception of specifically 'code editors' there isn't much out there that supports markdown.
I have been reading about the recently announced content-kit: http://madhatted.com/2015/7/31/announcing-content-kit-and-mo... and am wondering if you have considered the 'card' style concept for ProseMirror? I see ProseMirror has an interface for adding images, and says that it will support different document models in future and I'm wondering how extensible that will be.
What sort of APIs are going to be available, will it be possible to create custom 'blocks' or 'cards' of data - e.g. defining a block for adding a table / spreadsheet - similar to what you see in things like Quip or readme.io?
Basically, yes, the document object is designed to be extended by user code, so you could add your own kinds of nodes (even allowing them to contain existing node types, as in a table), but for some nodes (like tables) the impact will probably be big enough to require some specific UI-related code in the core.
Looks great. CodeMirror (http://codemirror.net/) is an amazing code editor OSS project by the same author. It powers Firefox and Chrome's devtools and is used in hundreds of other sites and apps (including the one I'm working on :)).
Direct link to ProseMirror's home page with live collaborative demo at the bottom: http://prosemirror.net/ (click "Change" to select a room)
And here's a link to the just-launched campaign to open source it (MIT license): https://www.indiegogo.com/projects/prosemirror/ . It's an all-or-nothing ("fixed") type indiegogo campaign, not the flexible kind where the funds are kept even if the goal isn't reached.
Sounds like the same problems that have been encountered (and mostly solved) in many different online videogames. Might be worth investigating how they solved these problems as well, since their solutions will be much more practical than theoretical.
Very interesting to see the approach, especially his critique of OT, which virtually every other system seems to be based on. His alternative seems to make sense, but I'm not sure if the end result for the user will be better, or if it's mainly that the implementation is easier/less bug prone?
I've actually been playing around with "translating" the server backend for share.js to Elixir, to be able to host it as part of a Phoenix app. Playing with ways of integrating with erlnode to run the actual test cases (including a fuzzer) from JS directly on my Elixir code.
If this gets opensourced, I wonder how complex the backend will be (I'm assuming it will be written in Node?), given that it seems like the front-end is doing most of the work.
A minimal backend can be extremely simple, just relaying changes, but if you want it to keep a running snapshot of the current document, you'll need the capacity to apply those changes to document, so you'd need to use the module used by the client, or a port of that.
Hi! Joseph Gentle here, author of ShareJS. You quoted me in your article.
You're right about OT - it gets crazy complicated if you implement it in a distributed fashion. But implementing it in a centralized fashion is actually not so bad. Its the perfect choice for google docs.
Here is my implementation of OT for plain text:
https://github.com/ottypes/text
Note that its only 400 lines of javascript, with liberal comments. To actually use OT code like that, you need to do a little bookkeeping. Its nowhere near as bad as you suggest.
In this tiny source-only demo I do all the bookkeeping, and implement a working network protocol on websockets. The result? I can sync an object between the server & client all in about 150 lines of code total:
https://github.com/josephg/appstate
This code has no external dependancies except for the ot type itself (ottypes/json0 in this case - although it could be changed to text or rich text or something with barely any code change).
Nice work making a cool demo - but I think you're using the wrong algorithm ;)
Does Sharejs currently support distributed synchronization?
My appreciation of OT (having tried to implement it myself) is that proving that the code preserves the transform constraint is very hard (and the proof one makes is easily wrong).
I believe that the OT proof is equally hard for centralized and distributed versions of OT (I was only ever focused on centralized).
Proving that operations commute is way easier. Defining a global total order for operations is way easier.
Working with an OT base seems more difficult as a result; adding offline or new operations requires more proofs and gets harder.
ProseMirror doesn't support distributed synchronisation so why do you ask?
Implementing OT consists of copying algorithms from academic papers, there's no need to prove anything yourself. Commutativity and global ordering are prerequisites to any OT proof.
Offline support falls naturally out of OT, it's effectively free. New operations can be defined in terms of the primitives of insert, update, and delete, given the ability create a batch operations.
Distributed OT, where there is no central server is seriously tricky and algorithms with proofs of correctness can be hard to come by. But centralised OT is readily implementable, albeit with considerable background reading of the necessary papers.
Personally I think it's good to see approaches other than OT being explored. There's space for more than one solution.
> ProseMirror doesn't support distributed synchronisation so why do you ask?
I wondered whether his quote from the article related to the implementation of distributed OT in ShareJS, or just centralized OT. I always assumed he had said that of centralized OT.
> Implementing OT consists of copying algorithms from academic papers
If you extend them, you need to extend the proof as well.
> New operations can be defined in terms of the primitives of insert, update, and delete
Similar to vector spaces, adding a vector to the base that is orthogonal to all others can give you a much larger space. While in OT, every new primitive requires an exponentially growing number of proofs, you can avoid that with a simpler algorithm.
Sure, OT has text figured out (although it took some time to fix the details). However, I am personally interested in more complex data structures such as matrices (bitmap) and trees (vector graphics, rich text), where you want to maintain the meaning of, say, the rotation of a layer. Even with sound, which can be kind of seen like a list, using the same primitives as with text would yield strange results.
It is harder to tweak an OT algorithm to go closer to the intention of the user (which I do heavily in Canop for text) as it is completely independent from the proof that is needed to maintain convergence.
To me, adding collaboration to an operation-based editor should be as simple as adding an undo/redo system.
I absolutely think that OT was a phenomenal achievement, but in a couple of years, I hope it won't be the go-to choice.
> in OT, every new primitive requires an exponentially growing number of proofs, you can avoid that with a simpler algorithm.
Its not actually necessary to add any new primitives though. Most of the time, composite operations can represent higher-level operations. I'll expand on this below.
> I am personally interested in more complex data structures such as matrices and trees
Trees can be modelled in OT using only the primitives of insert, update, and delete, providing that you support linear addresses (i.e. paths). We know from Lisp that everything else can be modelled from trees, so you effectively get a general-purpose system from just three primitives. CoPowerPoint was implemented using this approach and allows arbitrary graphical editing.
Yes, but that implementation deals only with plain text. The complexity seems to ramp up pretty quickly as you support more types of operations, and since extendability is an important concern for my project, I decided to avoid OT.
If you have insert, update, and delete then you can build any other operation from those primitives as long as you have the ability to batch a composite operation. So there's no need to extend the OT algorithm to support other kinds of primitive operation. For nested structures, addressing via ids or linear addresses has to be taken into account but that doesn't affect the OT transforms, it's one layer above. So it's possible (though not easy) to have an extensible OT system without exponential complexity.
Still, avoiding OT has led to some interesting new ideas and I look forward to seeing how things progress.
Sounds very interesting to me. This is an editor I have been looking for so long. Google's Kix generates a lot of DOM elements. Medium's sounds good in theory, but I haven't been able to try it due to the requirement of Twitter, and its clones just mimic the interface, not the functionality (still using contentEditable).
The closest one I saw was Aloha Editor v2. A little bit buggy and lack of document.
But I realize I don't need collaborative editing. Hopefully this will be separated into a component instead of built-in. Not all rich text editors need collaboration.
I spent 7 months of my life dedicated to solving this problem and let me say, it is not easy because I failed. But I learned something really important, we are all doing it wrong.
An index/offset based approach isn't the best solution, even with OT. Instead, we should have been looking at this problem as a linked list, where every character has a unique ID that can be pointed to. Doing operations this way is safe and becomes idempotent.
I'm busy building a database to back this type of data, but will be implementing a solution using this approach soon. Great work to everybody else hitting this problem, keep it up!
34 comments
[ 2.6 ms ] story [ 84.4 ms ] threadI'm not related to substance.io, just someone curious about editors on the web, and so have kept track of various options. Prosemirror looks very promising.
I've been working on a similar project based on the quill editor [1], which is in turn based on the rich-text OT library [2]. Initially, I thought to wire this all up using the sharejs project [3], but never could quite grok that codebase.
Instead, I've been working on a similar system to one you describe, with changes applied in order based on sequential version number, and concurrent updates forced to "rebase" against earlier changes (not yet open-sourced).
A question:
> Because applying changes in a different order might create a different document, rebasing isn't quite as easy as transforming all of our own changes through all of the remotely made changes.
Can you explain more about how you arrived this conclusion? From my understanding, a correct transform function should allow exactly this, according to transformation property 1 [4]. Perhaps your algorithm doesn't exactly satisfy this property; what characteristics does it have instead?
[1] http://quilljs.com/
[2] https://github.com/ottypes/rich-text
[3] http://sharejs.org/
[4] https://en.wikipedia.org/wiki/Operational_transformation#Con...
A correct OT transform, yes. But I'm not using OT's invariants, so this is not something my transforms do. For example, in my system, if you have "insert X at pos 5" and "insert Y at pos 5", the document will contain "XY" or "YX", depending on which arrived first.
Sorry ShareJS is such a mess right now. I did a bunch of work to make it into a kind of OT-backed database to power derbyjs. Its very much straddling two worlds at the moment and I think its doing a bad job of both.
It'll get cleaned up eventually.
How well does this approach scale to high-concurrency situations? The more active participants there are, the more often you'd be rejecting client changes and ask them to rebase, causing extra round-trips. It sounds like when a critical number of participants is reached, you'll create change requests more quickly than you can handle them. If each participant has a latency of 100ms to your server, and say you have 10 participants making 2 changes per second each, will you experience some sort of congestion?
On a similar note, what happens if you have two active clients, one with say 100ms latency and another with 500ms? If the 100ms client will be typing continously with 4 characters per second, the changes of the 500ms client won't get through until the 100ms one stops typing, right?
I realize these might not be much of a real issues in practise, but did you consider such cases? In particular, is there something in your machinery that prevents the server from doing the rebase, as opposed to sending it back to the client to do it?
As for references, I went all the way and implemented distributed OT in Gobby (https://github.com/gobby/gobby). It's somewhat doable for plain text editing, but going beyond that inflates the complexity very quickly. It gives you some nice properties like authorship tracking even across undo operations. However, the complexity goes with at least n^2 with the number of participants, so there is also an upper limit in the number of active participants that's reached rather sooner than later (even though I never actually found out where it is in practise).
This pattern matching of user's intentions and using DOM diffing to find out what actually happened feels right to me, especially using persistent data structures. Handling parts of the document as a tree and others as a list seems like decision that could probably make development much easier as you'd know, I imagine. I have been wondering about how to do structured inline element annotations, and lists inside block level elements certainly looks it could work.
Also, this relates to what LightTable folk's talked about in IDE as a value [1].
I'm definitely going to back this. That said, I'd like to know more about what is actually going to (hopefully) be open sourced.
Is this a stand alone app with plugins, a collection of components, or a library to build your own editor?
Is it written in purely JavaScript version 5, 6, or something else?
What about the persistent data structure implementation?
How are user intent patterns modeled, ie. what would it entail to build your own?
Have you thought about intermixing document tree with editors for other types of content, like tables and media?
[1] http://www.chris-granger.com/2013/01/24/the-ide-as-data/
It is written in ES6. The persistent data structures are not very involved, just objects that never get mutated after their initial construction.
I have been reading about the recently announced content-kit: http://madhatted.com/2015/7/31/announcing-content-kit-and-mo... and am wondering if you have considered the 'card' style concept for ProseMirror? I see ProseMirror has an interface for adding images, and says that it will support different document models in future and I'm wondering how extensible that will be.
What sort of APIs are going to be available, will it be possible to create custom 'blocks' or 'cards' of data - e.g. defining a block for adding a table / spreadsheet - similar to what you see in things like Quip or readme.io?
Direct link to ProseMirror's home page with live collaborative demo at the bottom: http://prosemirror.net/ (click "Change" to select a room)
And here's a link to the just-launched campaign to open source it (MIT license): https://www.indiegogo.com/projects/prosemirror/ . It's an all-or-nothing ("fixed") type indiegogo campaign, not the flexible kind where the funds are kept even if the goal isn't reached.
http://gafferongames.com/networking-for-game-programmers/
I've actually been playing around with "translating" the server backend for share.js to Elixir, to be able to host it as part of a Phoenix app. Playing with ways of integrating with erlnode to run the actual test cases (including a fuzzer) from JS directly on my Elixir code.
If this gets opensourced, I wonder how complex the backend will be (I'm assuming it will be written in Node?), given that it seems like the front-end is doing most of the work.
You're right about OT - it gets crazy complicated if you implement it in a distributed fashion. But implementing it in a centralized fashion is actually not so bad. Its the perfect choice for google docs.
Here is my implementation of OT for plain text: https://github.com/ottypes/text Note that its only 400 lines of javascript, with liberal comments. To actually use OT code like that, you need to do a little bookkeeping. Its nowhere near as bad as you suggest.
In this tiny source-only demo I do all the bookkeeping, and implement a working network protocol on websockets. The result? I can sync an object between the server & client all in about 150 lines of code total: https://github.com/josephg/appstate
This code has no external dependancies except for the ot type itself (ottypes/json0 in this case - although it could be changed to text or rich text or something with barely any code change).
Nice work making a cool demo - but I think you're using the wrong algorithm ;)
My appreciation of OT (having tried to implement it myself) is that proving that the code preserves the transform constraint is very hard (and the proof one makes is easily wrong).
I believe that the OT proof is equally hard for centralized and distributed versions of OT (I was only ever focused on centralized).
Proving that operations commute is way easier. Defining a global total order for operations is way easier.
Working with an OT base seems more difficult as a result; adding offline or new operations requires more proofs and gets harder.
I too turned towards simpler synchronization algorithms: https://github.com/espadrine/canop/blob/master/doc/paper.md
Implementing OT consists of copying algorithms from academic papers, there's no need to prove anything yourself. Commutativity and global ordering are prerequisites to any OT proof.
Offline support falls naturally out of OT, it's effectively free. New operations can be defined in terms of the primitives of insert, update, and delete, given the ability create a batch operations.
Distributed OT, where there is no central server is seriously tricky and algorithms with proofs of correctness can be hard to come by. But centralised OT is readily implementable, albeit with considerable background reading of the necessary papers.
Personally I think it's good to see approaches other than OT being explored. There's space for more than one solution.
I wondered whether his quote from the article related to the implementation of distributed OT in ShareJS, or just centralized OT. I always assumed he had said that of centralized OT.
> Implementing OT consists of copying algorithms from academic papers
If you extend them, you need to extend the proof as well.
> New operations can be defined in terms of the primitives of insert, update, and delete
Similar to vector spaces, adding a vector to the base that is orthogonal to all others can give you a much larger space. While in OT, every new primitive requires an exponentially growing number of proofs, you can avoid that with a simpler algorithm.
Sure, OT has text figured out (although it took some time to fix the details). However, I am personally interested in more complex data structures such as matrices (bitmap) and trees (vector graphics, rich text), where you want to maintain the meaning of, say, the rotation of a layer. Even with sound, which can be kind of seen like a list, using the same primitives as with text would yield strange results.
It is harder to tweak an OT algorithm to go closer to the intention of the user (which I do heavily in Canop for text) as it is completely independent from the proof that is needed to maintain convergence.
To me, adding collaboration to an operation-based editor should be as simple as adding an undo/redo system.
I absolutely think that OT was a phenomenal achievement, but in a couple of years, I hope it won't be the go-to choice.
Its not actually necessary to add any new primitives though. Most of the time, composite operations can represent higher-level operations. I'll expand on this below.
> I am personally interested in more complex data structures such as matrices and trees
Trees can be modelled in OT using only the primitives of insert, update, and delete, providing that you support linear addresses (i.e. paths). We know from Lisp that everything else can be modelled from trees, so you effectively get a general-purpose system from just three primitives. CoPowerPoint was implemented using this approach and allows arbitrary graphical editing.
Still, avoiding OT has led to some interesting new ideas and I look forward to seeing how things progress.
did you end up using https://github.com/markdown-it/markdown-it for the AST pass?
Sounds very interesting to me. This is an editor I have been looking for so long. Google's Kix generates a lot of DOM elements. Medium's sounds good in theory, but I haven't been able to try it due to the requirement of Twitter, and its clones just mimic the interface, not the functionality (still using contentEditable).
The closest one I saw was Aloha Editor v2. A little bit buggy and lack of document.
But I realize I don't need collaborative editing. Hopefully this will be separated into a component instead of built-in. Not all rich text editors need collaboration.
https://www.indiegogo.com/projects/prosemirror/#/story
An index/offset based approach isn't the best solution, even with OT. Instead, we should have been looking at this problem as a linked list, where every character has a unique ID that can be pointed to. Doing operations this way is safe and becomes idempotent.
I'm busy building a database to back this type of data, but will be implementing a solution using this approach soon. Great work to everybody else hitting this problem, keep it up!