Interest

[eukreign]

I've been following this project since last year and am really excited about the possibilities this brings to general purpose OT.

It seems that there hasn't been much activity on this and I was wondering if you are still working on it in private or if you have lost interest and moved on to other things?

[josephg]

Hey! Great question.

I still want to go forward with it at some point. The primary blocker when I stopped working on it is that I realised there are some operations that simply can't be transformed, and so I'll need to add conflict markers.

For example:

• Doc: {a:{}, b:{}}
• User 1: Move a inside b
• User 2: Move b inside a

.. In this case, the only sensible result from transforming those operations would be to delete both a and b, but thats super surprising from the user's point of view. So I think the operations should conflict instead. If they can do that I'm going to have to rethink the semantics of all the other operations to see if it makes sense to allow them to conflict as well. I think the API I want is for applications to specify a spec of which operations (/ paths?) should generate conflicts, and which should simply transform automatically.

When I realised all that I put it down until I have more time to come at it fresh. If someone paid me to work on it it might be a different story.

[laughinghan]

In this case, the only sensible result from transforming those operations would be to delete both a and b, but thats super surprising from the user's point of view.

Why doesn't one of them win and the other get discarded, like I assume happens with object insertion conflicts? Meaning two people trying to insert the same key in an object:

• Doc: {}
• User 1: Transform to {a:1}
• User 2: Transform to {a:2}

Result: both users end up with {a:1}.

(Or {a:2}, doesn't matter as long as they end up with the same thing, right?)

I may be missing something but that makes way more sense to me. By the way this project is super cool and you're super cool!

[josephg]

Aw thanks!

Um, its a worse than that because changes can back up.

• Doc: {a:123, x:{}, y:{}}
• User 1: Move x inside y, add 1 to doc.a and move a->x
• User 2: Move y inside x

If we make user 2's change win, what do we transform user 1's operation to? doc.x won't have moved away. So what happens to doc.a? (It could be much worse, too - they could have moved a -> b, b -> c, c ->d, .... and finally w -> x and set a = "hi". Do we have to undo all of those changes? Do we discard user 1's insert as well?

Its a red hot mess.

[laughinghan]

Woah you responded really fast! I'm gonna submit a PR with a bunch of typo fixes to the Spec then.

If we make user 2's change win, what do we transform user 1's operation to? doc.x won't have moved away. So what happens to doc.a?

Hmmmmmm. My intuition is that the move a->x conflict should resolve similarly to an insert; that is, this is a similar problem to:

• Doc: {x:{}, y:{}}
• User 1: Move x inside y, insert doc.x = 1
• User 1: Move y inside x

The problem here is that user 1 got rid of doc.x and expects to be able to insert there. In JSON0, was it possible for deletion of a key to be discarded? If so, how did we transform subsequent inserts of that key? Or was deletion in JSON0 impossible to conflict, only insertions, and now the problem is that a deletion is being atomically coupled to an insertion (i.e. a move)?

[laughinghan]

Hmmmmmm it's always been possible (that is, it's also possible in JSON0) to lose huge insertions, right? (User 1 inserts huge thing into object; User 2 replaces the object with a number.) Maybe losing mass moves isn't worse?

[josephg]

In JSON0, is it possible for deletion of a key to be discarded? If so, how do we transform subsequent inserts of that key? Or was deletion in JSON0 impossible to conflict, only insertions, and now the problem is that a deletion is being atomically coupled to an insertion (i.e. a move)?

In JSON0 the only operations on objects are insert and delete. You can't move something inside an object (or rename a key or anything like that). So delete vs delete always just deletes it. Insert vs insert will pick one winner, but from the point of view of the loser - well, they know the content they just tried to insert. Worst case they can re-insert it or something. And you can't have an insert operation vs a delete operation.

But moves are different in two ways:

• The content you're moving might change between when you create the op and when the move gets executed on the server.
• Your changes are sort of internally conflicting if the move gets punted. Its different from two inserts to the same location, where you're conflicting with another person.

Oh and we can run into a similar problem with moves to the same location:

• Doc: {a:1, b:2}
• Client 1: Move a -> x, insert a:10
• Client 2: Move b -> x, insert b:10

I'm tempted to support something like an op saying move a -> x, but if that would conflict, move a -> end of doc.lostandfound list. Its impossible for a list push to conflict, and then we can guarantee that the following insert of a:10 will succeed.

[josephg]

(But yeah you can have big overwrites like that. And they are actually super rare in practice)

[green-coder]

The doc.lostandfound list is a viable solution (the expected solution, to be precise) for my use case (a collaborative Scratch-like) where it costs a lot to the users (typically young students) to create tree elements while it is easy and fast for them to move them around, parent/deparent them.

[josephg]

Great. Well maybe we should do that then. The other problem is simply that we'll probably want to bundle the lost and found entry with some application-specific metadata (which users conflicted, author, timestamp). That information will need to be passed through somehow - but maybe I can just have transform get passed an optional options object with a wrapLostEntry(op) method that does the work if it's needed. And I'm also tempted to make the behaviour configurable - so you can make it conflict instead if you want.

[josephg]

From memory I think figuring out this behaviour is pretty much all that's left btw. The code is tight though - it's probably going to be a small change but not a simple change.

[jhurliman]

Allowing for a conflict instead of the lost and found behavior would help this generalize out to my use case and presumably others.

[green-coder]

@jhurliman Please let us know about your use case and why you think it would be better to have a conflict. Also, please describe what means a conflict for you, to make sure that we are all talking about the same thing.

Let's all try to make a verbosity effort to make it simpler for @josephg to make his design decisions.

[jhurliman]

This is for a multivariate testing framework where you have one base JSON document and lots of diffs to that base document organized into separate "experiments". The goal is to be able to independently create experiments but apply multiple experiments at runtime. For many of the edits this just requires a way to cleanly merge the changes, but what if one experiment modifies a property of object a but another experiment deletes object a entirely? The best outcome here would be to generate a "conflict" which is logged somewhere and choose not to apply one or both of the experiments entirely.

EDIT: In this non-interactive context, the idea of a lost and found list doesn't make sense because 1) the changes are stored outside of the base document so nothing would be "lost" by a failed merge, and 2) there is no human in the process that would be able to pluck things out of lost and found and manually reapply them.

[laughinghan]

The doc.lostandfound list is a viable solution (the expected solution, to be precise) for my use case

huh, really? My biggest problem with that is doc.lostandfound becoming like, a reserved path. What if someone sets doc.lostandfound to 1 or anything other than a list? If we're gonna do this, the "lost and found" list should be out-of-band. What if instead of a literal list, we emit an event that can optionally be ignored, kinda like how you can trap arithmetic overflow in assembly?

You're welcome to assemble such emitted/trapped events into a list of lost-and-found, moved-but-failed values, but you're also welcome to just ignore them. (Contrast if a list was pushed to, if you ignore that list you get a memory leak.)