Collaborative Editing in ProseMirror
marijnhaverbeke.nl
marijnhaverbeke.nl
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.
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.
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?
[2] https://github.com/ottypes/rich-text
[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?
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!
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'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.
did you end up using https://github.com/markdown-it/markdown-it for the AST pass?