4 ms·

I agree with the sentiments on OT. It really ought to be baked into everything. It has features you want, such as undo/redo, collaborative editing and optimisti

by collint 15y ago

I agree with the sentiments on OT. It really ought to be baked into everything. It has features you want, such as undo/redo, collaborative editing and optimistic locking. I've been working on an OT implementation for the past few weeks. It really is some brain wrinkling stuff. The adoption of data-bining we're seeing in the newer JavaScript client frameworks/libraries could be paving the way for something like OT to go mainstream. OT is a bit like pulling your brain through a wormhole#. I think it's going to take a really easy to plug-in library to have something like OT get any traction. # That is, OT is fairly straightforward if you're editing a document. It gets weird when you have to map a graph of objects onto/from a stream of operations.

raganwald 15y ago
OT is fairly straightforward if you're editing a document Even with a “plain text” document, there is much nerd sniping to be done when you consider that OT works best at a semantic level, not a character level. A trivial example is that conflicting edits to words and numbers should often be treated differently. This may not generalize very well, a domain-specific editor for one application may want to use slightly different transformation semantics than another.
- collint 15y ago
  I try not spend too much time on semantics at the transformation level. There are already hundreds of cases that must be understood transformed just to handle concurrent operations on an XML document. If you want the transformer to handle semantics I fear you're going to balloon in complexity to the point of deep sadness. ( What do we do if I'm typing a number inside your word? Word inside a number? Delete a number inside a word? What if you word is the name of city? etc. forever ) I think there is a better ROI on making the intent of your collaborators clear, such as with cursor/mouse indicators. If I can see you're editing a number, I can know to steer clear, or at least be ready for the consequences.
  - josephg 15y ago
    I've written ShareJS, which performs OT over generic JSON objects. Getting OT-for-JSON working involved a lot of cases, but it was certainly tractable. The tricky algorithmic code is 440 lines long. XML would be much more complicated to get right, but certainly possible if you're mad keen on XML.
    - beza1e1 15y ago
      Did you really need it on the JSON level? It goes over the wire, hence it is essentially just a string.
      - josephg 15y ago
        Yes, you do. Say you have an object: {x:1} Two people try and add a y:2 to the object. If you treat the object as a string, you can end up with: {y:2,x:1,y:2} ... which is invalid JSON. If you do string-level operations, there's heaps of ways the JSON can end up invalid or just plain wrong. In comparison, using OT if two people apply a "Insert y:2 into the object" operation, the object will be edited correctly at all sites.
      - raganwald 15y ago
        Joesph's reply is absolutely correct. I just wanted to add that JSON is a special case of what I noted above: OT is more of a protocol than an algorithm, it takes in operations and performs a transformation on them. It's up to you to decide what those operations are and how to transform them. The canonical example of a text document with operations consisting of inserting or deleting strings of characters is a little error-prone, but in the context of humans editing text in real time, there's an assumption that they will correct any visible artefacts. However, when you have structured data created and consumed by algorithms, your tolerance for artefacts goes down to nothing, and you need to choose a different set of operations and carefully design the transformation function. In between structured data and unstructured text there is also text with semantics. As noted above, you can ignore that and leave it up to humans to fix it, or you can bake some smarts about the text in. There are existing products that treat numbers as a special case, for example. It may not be worth the effort, that's a design choice. Anyhow, this is a lot of blowhardiness just to say that OT isn't an error-free way to synchonize strings, nor is it just one algorithm, it's a protocol and part of the design process is deciding when and how to go beyond plain text and the obvious transformations on the operations.
ilaksh 15y ago
I always thought that Google Wave was about baking OT into everything.
ilaksh 15y ago
"The adoption of data-bining we're seeing in the newer JavaScript client frameworks/libraries could be paving the way for something like OT to go mainstream." Socket.IO plus some kind of generic data framework with a collection type.. you can get pretty far with most CRUD type applications if you just have a way (something OT algorithms handle) to resolve issues related to positioning in a list I think, and that could be generalized to take care of everything from sequences of characters in text to items in a spreadsheet. When you are talking about graphs.. what sort of issues are you having?
josephg 15y ago
I'm working on the same thing for node.js. Come help me write ShareJS: http://sharejs.org/ http://sharejs.org/ Also, plaintext and JSON data types are generic and pluggable into other systems. I'm not sure what you're trying to do, but they might be useful.
- jmcqk6 15y ago
  Thanks for this. I came across your project a few months ago and bookmarked for when I have more time. Now I'm getting to that point.

by collint 15y ago

raganwald 15y ago

OT is fairly straightforward if you're editing a document Even with a “plain text” document, there is much nerd sniping to be done when you consider that OT works best at a semantic level, not a character level. A trivial example is that conflicting edits to words and numbers should often be treated differently. This may not generalize very well, a domain-specific editor for one application may want to use slightly different transformation semantics than another.

collint 15y ago
I try not spend too much time on semantics at the transformation level. There are already hundreds of cases that must be understood transformed just to handle concurrent operations on an XML document. If you want the transformer to handle semantics I fear you're going to balloon in complexity to the point of deep sadness. ( What do we do if I'm typing a number inside your word? Word inside a number? Delete a number inside a word? What if you word is the name of city? etc. forever ) I think there is a better ROI on making the intent of your collaborators clear, such as with cursor/mouse indicators. If I can see you're editing a number, I can know to steer clear, or at least be ready for the consequences.
- josephg 15y ago
  I've written ShareJS, which performs OT over generic JSON objects. Getting OT-for-JSON working involved a lot of cases, but it was certainly tractable. The tricky algorithmic code is 440 lines long. XML would be much more complicated to get right, but certainly possible if you're mad keen on XML.
  - beza1e1 15y ago
    Did you really need it on the JSON level? It goes over the wire, hence it is essentially just a string.
    - josephg 15y ago
      Yes, you do. Say you have an object: {x:1} Two people try and add a y:2 to the object. If you treat the object as a string, you can end up with: {y:2,x:1,y:2} ... which is invalid JSON. If you do string-level operations, there's heaps of ways the JSON can end up invalid or just plain wrong. In comparison, using OT if two people apply a "Insert y:2 into the object" operation, the object will be edited correctly at all sites.
    - raganwald 15y ago
      Joesph's reply is absolutely correct. I just wanted to add that JSON is a special case of what I noted above: OT is more of a protocol than an algorithm, it takes in operations and performs a transformation on them. It's up to you to decide what those operations are and how to transform them. The canonical example of a text document with operations consisting of inserting or deleting strings of characters is a little error-prone, but in the context of humans editing text in real time, there's an assumption that they will correct any visible artefacts. However, when you have structured data created and consumed by algorithms, your tolerance for artefacts goes down to nothing, and you need to choose a different set of operations and carefully design the transformation function. In between structured data and unstructured text there is also text with semantics. As noted above, you can ignore that and leave it up to humans to fix it, or you can bake some smarts about the text in. There are existing products that treat numbers as a special case, for example. It may not be worth the effort, that's a design choice. Anyhow, this is a lot of blowhardiness just to say that OT isn't an error-free way to synchonize strings, nor is it just one algorithm, it's a protocol and part of the design process is deciding when and how to go beyond plain text and the obvious transformations on the operations.

ilaksh 15y ago

I always thought that Google Wave was about baking OT into everything.

ilaksh 15y ago

"The adoption of data-bining we're seeing in the newer JavaScript client frameworks/libraries could be paving the way for something like OT to go mainstream." Socket.IO plus some kind of generic data framework with a collection type.. you can get pretty far with most CRUD type applications if you just have a way (something OT algorithms handle) to resolve issues related to positioning in a list I think, and that could be generalized to take care of everything from sequences of characters in text to items in a spreadsheet. When you are talking about graphs.. what sort of issues are you having?

josephg 15y ago

I'm working on the same thing for node.js. Come help me write ShareJS: http://sharejs.org/ http://sharejs.org/ Also, plaintext and JSON data types are generic and pluggable into other systems. I'm not sure what you're trying to do, but they might be useful.

jmcqk6 15y ago
Thanks for this. I came across your project a few months ago and bookmarked for when I have more time. Now I'm getting to that point.