Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Documentation has great promise. Please keep going! #23

Open
jessep opened this issue Dec 6, 2013 · 2 comments
Open

Documentation has great promise. Please keep going! #23

jessep opened this issue Dec 6, 2013 · 2 comments

Comments

@jessep
Copy link

jessep commented Dec 6, 2013

I love the beginning of this description of how ot works: http://operational-transformation.github.io The promise that it isn't so hard to understand is quite alluring.

The reason I'm interested is I make workflowy.com, a fancy outliner, and ot could help us do things better. we don't use it right now, but i'd like to eventually. would like to use it for tree transformations too, not just text. seems opaque, though, and that having someone like you would explain it clearly would be really nice.

@jnbt
Copy link

jnbt commented Dec 12, 2013

I've once implemented OT for tree structures (Insert, Replace, Delete, Move). This can be further combined with OT for strings for single values inside the structure (e.g. a value of a text label). I didn't used any code from this repo but used it as an inspiration.

While developing the transformation function for tree structures it turned out that the concept is similar. Every operation only changes a subtree (in the worst-case the subtree equals the tree) and in the most cases two operations don't conflict.

My approach used a path instead of a "retain" component to define the effect of an operation. For two concurrent operations you have to check for a common part in their paths. If it doesn't exists there can't be a conflict. Otherwise a transformation must be done. If the structure also includes some kind of arrays the transformation function also changes the paths.

Assume the following scenario:

            a
         /     \                // <-- notates a parent - child relationship: node a is parent of node b. 
        b      [e1,   e2]       // <-- notates an array: [e1, e2] is an array node which parent is node a. 
        |       |     |
       ...    /   \   ...
             c     d
             |     |
            "Y"   "X"          // <-- notates leaf values: "Y" and "X" are primitive nodes

The path from node a to node b can be described as {a,b}, while the path to "Y" would be {a,0,c}.

Concurrent operations:

  • User A changes the value "Y" to"Z"which can be expressed as o1:replace({a,0,c},"Z")`
  • User B inserts a new node before e1 which can be expressed as o2: insert({a,0}, "V")

In this o1 and o2 have a common part in their paths so a transformation must be done. It's obvious that the transformation function must change the paths in the operations, so the states for both users converges to the same:

            a
         /     \                
        b      [e0     e1,   e2]       
        |       |      |     |
       ...     "V"   /   \   ...
                    c     d
                    |     |
                   "Z"   "X"          

I hope this helps in designing an OT algorithm for your problem. I cannot describe the full solution in detail, but I can state that it can be done and works pretty well.

@marcelklehr
Copy link

It works indeed, I have been writing dom-ot, which transforms and applies DOM tree changes (in conjunction with MutationSummary it can also detect dom changes, leading the way to warp).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants