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.)

[laughinghan]

... and so I'll need to add conflict markers. ... 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.

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

Super against this. My fundamental understanding of OT is based on my understanding of distributed version control systems like git. In the version control world, there's a distinction drawn between "textual" merge conflicts, and "semantic" merge conflicts: textual conflicts are when there's a conflict in the literal changes to the text, such as two people modifying the same line in the same file; whereas semantic conflicts are when two valid changes combine into an invalid merge, such as if one person renames a function and all its call sites, but another person adds a new call to the function in a new file, which is not a conflict at the changes-to-text-files-level, but is an important kind of conflict because it won't compile/run since the new function call uses the old name from before the other person renamed it. git is oblivious to semantic conflicts, of course, but with textual conflicts it will stop and demand you fix the conflict before proceeding, ideally so that your manually merged result will be a valid working state.

My fundamental understanding of OT is that it guarantees there are never textual conflicts, or equivalently, that everything that would be a textual conflict is automatically resolved identically by all parties; while also promising that changes that clearly, unambiguously don't semantically conflict will definitely be resolved as expected, but this promise is "best effort": it's meant for like, two changes to totally separate parts of a document; not, two changes to the same part of a document that a human could tell what the "expected" merge of is, but the algorithm isn't sophisticated enough to. The whole reason that textual conflicts need to be resolved automatically is that lots of tiny changes are being exchanged in real-time, but conversely this means that semantic conflicts that happen can be resolved interactively in real-time; for example if two people start typing in the same place at the same time, and are dissatisfied with whose insertion was automatically chosen to be first, they can switch it around.

Which is why I'm a little befuddled why this is that big of a problem in the first place. Okay, I understand now, conflicts involving a move can't be resolved by ignoring a move because other stuff may have happened in the place that the move vacated from; but then just resolve such conflicts as drops and move on, and if that's not what the user wanted, that's what Ctrl-Z is for, right?

(Ctrl-Z would add back the value to the place that the move vacated from; if something else had been added there, it gets dropped, and if you want to keep both values, you gotta copy the tried-to-move-but-instead-dropped value and then Ctrl-Y to add back the something else, and past the dropped value somewhere else. Which is maybe kinda annoying but strictly better than stuff lost to insertion conflicts, which you can't even recover via Ctrl-Z because that's for your own actions not counterparties.)

[josephg]

@laughinghan:

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?

I'm imagining it being explicitly named inside each operation:

[
  [descend 'a', {pick up item 0}],
  [descend 'b', {drop item 0}],
  [descend 'lostandfound', {push to this list on conflict, marked with this metadata}]
]

... Which is a bit wordy, but it means the OT code doesn't have to make any assumptions about how your data is structured. Of course, if you always put your lost and found data in the same place, you could just insert the lost and found rules into every operation on the client, before calling transform. Another option is to store the lost and found path with the document snapsnot - though that'd make the whole thing less pure in a sense. Or I could just add another argument to transform?

The nice thing about that is that If there's no lost&found path specified, the conflicting item gets discarded.

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.)

Nooo.... I don't like that at all.

The nice thing about a lostandfound list is that the changes will resolve in the same way on every peer. So, every peer will end up with the same item in the same place in the lost and found list. The stream would have the same property - it would emit the same sequence of items. But I'm not really sure what clients should do with a stream like that - maybe if the system did first-writer-wins, the server could ignore the stream entirely and then on clients the only objects that would pop out of the stream would be items that you displaced. Then the client could re-insert the newly displaced orphan somewhere in the document. The problem is that by the time that happens the server has already accepted the operation. If the cilent sends a conflicting change then gets disconnected / crashes / closes the app, the orphaned object will be unexpectedly lost forever.

---

So how about something like this:

• Do the thing I just said above with the capacity to elect a lost and found list
• Add two functions to the OT code:
  • withLostAndFound(op, path): Sets the lost and found path in op, which is a helper method so if all operations in your app put the lost and found path in the same place you don't have to store that path in every operation over the wire / on disk.
  • getConflicts(op1, op2): Returns a list of all potential (detectable) conflicts between concurrent ops op1 and op2. Each conflict will specify a conflict type, location, and conflicting data. We can put anything we want in here, and its entirely up to the application whether it calls this function at all, and which conflicting edits it cares about. Would that keep you happy @jhurliman ?

[jhurliman]

Yes :)

[laughinghan]

The nice thing about a lostandfound list is that the changes will resolve in the same way on every peer. So, every peer will end up with the same item in the same place in the lost and found list.

Ohhhhh I forgot that such a lost-and-found list would be shared, which is pretty different from my event emitting/trapping idea.

on clients the only objects that would pop out of the stream would be items that you displaced

Yes that's what I was imagining. The client/application would be welcome to reserve (at the application layer, not the OT layer), root.lostandfound as a list, and push emitted/trapped lost-and-found values into that (shared) list. How well/poorly would that work for you use case, @green-coder?

Another option is to store the lost and found path with the document snapsnot - though that'd make the whole thing less pure in a sense.

Agreed 👎

Or I could just add another argument to transform?

The nice thing about that is that If there's no lost&found path specified, the conflicting item gets discarded.

:+1: Seems fine to me. The use case I have in mind avoids these conflicts at the application layer (moves are only between arrays), so no reserved path and the path being optional are my main concerns here, though the emitting/trapping still feels more pure to me.

Question: Will the value be discarded if undoing the move doesn't conflict? I.e.:

• doc: {a:1, b:2}
• client 1: move a->x
• client 2: move b->x

If client 1 wins, do they end up with {x:1, b:2} or just {x:1}? I'm worried that like, in order to keep b:2 we'd have to somehow see into the future that there's no forthcoming insert at b, but maybe such a future insert would simply override b:2 so it's no problem?

[green-coder]

I like the approach chosen by @josephg as it is flexible and generic data structure.

I think that "first-writer-wins" used in addition with the "lost-and-found" for the loser of the conflict would work fine for my use case.

[josephg]

@laughinghan:

the emitting/trapping still feels more pure to me.

Yeah I like the emitting / trapping for that reason, but relying on the client to do something in response to a mutation confirmation is unreliable. If the system works by:

1. Client1 sends op1, client2 sends op2
2. Server receives conflicting ops. Transform removes conflicting part of op2.
3. Server sends acknowledgements to client1, client2.
4. Client2 notices that part of its op was removed, resubmits

... Then the question is, what happens if client2 disconnects between steps 2 and 4? Is the document in a consistent state? Have we lost data?

In any case, you can always re-create that behaviour if you want it using the conflict detection function. If you don't configure the lostandfound list, concurrent edits will be deleted. Then when the client finds out about the concurrent edits, run the conflict check in the client and emit an event stream.

As for your question, those operations do conflict. By default, the resulting document would be {x:1}. If you want to keep b under the system I proposed, you'll need to run the conflict checker on the server and reject / trim op2, or set a lostandfound list (so the result would be {x:1, lnf:[2]})

Stuff that would conflict:

• Mutually blackholed moves (a->b.x vs b->a.x)
• Move-into-deleted item (a->b.x vs delete b)
• Drop into the same location (a->x vs b->x)

And we could also detect and report on:

• Moving the same item to different places (a->x vs a->y)
• A drop inside a destination that has moved (a->b.x vs b->c)
• Attempt to move an item that was deleted by op2 (a->x vs delete a)

---

Also in other news, I've gotten back to the codebase. I haven't added the blackhole detection yet, but I've fixed a bunch of bugs. The fuzzer makes it through 280 iterations before crashing now (up from 20 iterations a few days ago).

[green-coder]

@josephg Please let us know if we can help you with the testing or code review.

I personally would like to assist, although I am not familiar with coffee-script so I may need some time to get started.

[josephg]

@green-coder thanks... its all javascript now (I finished converting it a couple of days ago). But ... I'm not sure if there's room for more people to plug away at it. Its the sort of thing that takes me days to ramp up on, and I wrote it.

Do you mind updating the spec based on what we've been talking about above?

[green-coder]

@josephg That seems a little difficult for me at the moment but I can give it a try, that seems like a good start.

I suggest you to create a 'ot-json1' chatroom using https://gitter.im for discussing with people willing to contribute, and put a link to it on your readme file.

[laughinghan]

... Then the question is, what happens if client2 disconnects between steps 2 and 4? Is the document in a consistent state? Have we lost data?

Ohhhh right we can't rely on any one client to do anything, every client/server needs to independently arrive at the same result; but if we emitted the event on every client/server and the application pushed it into the lost-and-found list, there'd be tons of duplicates.

As for your question, those operations do conflict.

I know, what I meant was, undoing the move (which leaves b:2) doesn't conflict with anything. If it later turns out to conflict, it can still be overwritten, right? By which I mean:

• doc: {a:1, b:2}
• client 1: move a->x
• client 2: move b->x
• server resolves conflict with client 1 winning, doc is now {x:1, b:2}
• client 2 hasn't gotten the memo yet, now does set b:3 (doc: {a:1, x:2, b:3})

When client 2 and the server now sync up, they'll resolve to {x:1, b:3}; the b:3 must win over undoing the move (b:2) to avoid the undoing-a-whole-musical-chairs-chain-of-moves scenario. (Remind me why undoing a whole musical chairs chain of moves is bad, again?)

Maybe that's still bad because it won't be added to the lost-and-found list consistently by all clients?

By the way, thanks for taking the time to answer all my questions. I'm excited that you've gotten back into the codebase!

[josephg]

Wait, slow down.

• doc: {a:1, b:2}, version 1 (tracking versions is the responsibility of the caller)
• client 1: move a->x, version 1
• client 2: move b->x, version 1
• Server receives client 1's op. Doc now {b:2, x:1}, version 2
• Server receives client 2's op. transform(op2, op1, 'left', {lostandfound:'lnf'}) -> move b->lostandfound.
• doc now {x:1, lnf:[2]}, version: 3

client 2 hasn't gotten the memo yet, now does set b:3 (doc: {a:1, x:2, b:3})

• client sends insert b:3
• Doc is now {b:3, x:1, lnf:[2]}

... Easy.

[josephg]

I don't have a good place to update the status of this project - I keep a project journal, but its not online anywhere.

Anyway, good news: A week or so ago the tests passed, but the fuzzer would get through about 10 iterations before finding bad input. I've been busy fixing behaviour, and its running right now, having passed more than 400 000 iterations successfully. There might still be a bug or two, but the transform function is basically finished now. (Whew, what a ride.)

The ot type itself isn't finished yet though - compose still hasn't been written, and once its written I expect the randomizer will start finding some new bugs. But compose is way easier to write than transform, so its all downhill from here.

I also haven't implemented the conflict checker or lost and found list, but both of those should be reasonably straightforward. (The transform function has probably taken about 1-2 months of time to write over the last 3 years. I expect each of those to take about 1-2 days each. The checker itself will just internally call transform with different arguments, creating & returning a list of conflicts instead of returning the transformed object itself.)

... > 1 million iterations and still going strong ...

[green-coder]

Hi @josephg, I tried hard to find a way to contribute to the project and modify the spec.md file, but I found it difficult to impersonate your ideas, experience and writing style without fearing to be somehow wrong.

Also, a few details are bothering me as I would personally do things in a different way, developing first a reference version where algorithm complexity would not matter at all, make it work in the whole system, and then optimize the algorithm. One of the difficulties you have with json1 is that you made yourself facing all the problems at the same time : usability issues, conflict resolution policies, implementation, validation, optimizations, Coffeescript<->JS waltz.

I am sure that there are people like me who would love to contribute, but they also have to face all of that at the same time, that's a pretty steep learning curve. I believe that it is the reason why much of the activity happen inside the issue tracking conversation rather than within PRs. I hope you can finish the project, I am sure people will be ready when it will be the time to test it.

[josephg]

Also, a few details are bothering me as I would personally do things in a different way, developing first a reference version where algorithm complexity would not matter at all, make it work in the whole system, and then optimize the algorithm.

Well thats what I'm doing. The code at the moment is a bit of a mess - there's a lot of code duplication and code written out explicitly that would be better off tidied away behind some simple abstractions. But the fuzzer is a great teacher - it keeps showing me new test cases I didn't consider. Many of the abstractions I have come up with have turned out to be wrong, or badly designed. I've also had to adjust some of my test cases. Once the code is working I want to do a cleanup pass - which is much easier once I know the complete set of behaviour. (As it is each new failing test case found by the fuzzer gets simplified and added to the standard set of tests)

Progress update: I got compose working - it took about a day to write. Up until this point the fuzzer was only generating simple operations (usually just one edit). Now that compose is working the fuzzer is finding some new bugs in transform that I hadn't seen before.d

My current sticking point is bugs of this form:

• op1: Move a->x, insert x[0] = 5
• op2: Move a->y

Expected result of transform(op1, op2, 'left' / 'right')

• left: Move y->x, insert x[0] = 5
• right: Insert y[0] = 5

... Which require adding some more tracking code. But I've been pulled off this project for now to do things which result in my rent being paid. I hope to get back and finish it soon. Its so close!

[logixworx]

What is the status of this project as of today? Last update was 5 months ago

[eukreign]

Do you mean 5 days ago? Seems like @josephg is making progress on things.

[logixworx]

I guess he is :) How close to being production ready is ot-json1?

[eukreign]

I don't know what @josephg position is on this but generally speaking (open source software development) the standard response to a question like that is "patches welcome" :-D

If json1 already does everything you need and does it well, then you can probably use it in production. If it does not do everything you need then you'd be better off by asking specific questions like: When will json1 support feature X? And unless X feature is actively being worked on the response to that will also probably be "patches welcome".

I apologize in advance if my response is too abrasive.

[jacwright]

I believe the question is valid. @josephg is working out some bugs in the core algorithms and it is likely not production ready until there is a higher confidence around edge-cases here which the fuzzer is helping with. Using it now, even if it works in your testing, might not be wise as edge-cases will pop up in production.

I'm excited for this project and cheering on @josephg and anyone else working on it. 😄

[josephg]

Thanks everyone. I've been keeping a project journal for the last 2.5 years. To add visibility I've put it on the wiki here. It was mostly written to rubber-duck my thoughts, so its mostly unedited and raw.

The current state is:

• The spec is mostly complete. I don't expect the spec to change at this point.
• Apply works. To the best of my knowledge the apply function is complete and correct.
• Transform is ... mostly correct. Using single isolated operations the fuzzer finds bugs, but only after trying millions of combinations (more below).
• Compose mostly works, but the fuzzer finds bugs in transform almost immediately when transforming multi-part operations (operations that move two things, or move something and edit something else, etc). The transform tests are probably also hiding some bugs in compose. (This is something I could investigate pretty easily though, by just disabling those tests and running the fuzzer).

The bugs in transform are awful edge cases that I didn't consider at all when designing transform. I took a break in May after realising that I'd need to redesign chunks of how the transform function works because its missing important metadata that it needs to correctly respond to some situations. The canonical place for the list of known transform bugs is skipped tests in the test suite. I'm sad to say that fixing these bugs is not new-contributor friendly.

And speaking of responding to some situations, the other thing thats missing in transform is the stuff we were discussing earlier in this thread. I want a way to test for conflicts and return a list of potentially conflicting operations. Eg, if two operations both try to move different items to the same location in the tree, by default one of those items will be removed. This is pretty bad behaviour for a lot of use cases. I want a function that you can call before transforming that will tell you if that will happen and tell you the path of the items involved so you can decide what to do. (Do you do it anyway? Move the item somewhere else? Error to the user? Its your application.) Internally this will be implemented using the same logic as transform, but instead of returning the result we'll return a list of conflicts. (Or maybe both.)

My original plan for this behaviour was to just move otherwise-deleted items to a lost and found list, but thats not good enough because you often want to attach metadata to the lost and found items. Then I thought I could do both (have a lost and found list and a conflict detection list depending on arguments) but thats sort of redundant. The getTransformConflicts(op1, op2, side) function should give you enough information on to be able to implement the behaviour of the lost and found list if thats what you want anyway. I could provide said function out of the box, just implemented on top of the other functions in the public API.

The other things that still need to be done:

• There's some general cleanup stuff. For example, the logging code at the moment transitively pulls in many times its own weight in javascript when bundling for the browser. I can turn that off really easily, but I'm going to leave it there until transform and compose are working. There's also some unused junk files in this repo that I want to delete.
• I've started trying to use it myself, and I've found that I want a function for transforming a path by an operation. This should be pretty easy to write, and there's a precedent for it in text OT code.
• I want functions to convert between json0 operations and json1 operations. At the very least, I want to run the test cases @nornagon wrote for json0 here. It will also be useful for anyone porting code from the old json type to the new one. Converting from json0 to json1 will be really easy (~20loc) - each component of a json0 operation will cleanly convert to a json1 operation and then compose can merge them all together. But going the other way is way more tricky - probably 200loc or so. And not all json1 operations have a json0 counterpart.

I still can't escape the feeling that there exist some nice abstractions that would make implementing all this stuff way easier. After years of looking, they still elude me and I'm left playing whack-a-mole with test cases while trying to fit hundreds of lines of transform function in my head. I think I'm really close to making it correct, but there's still at least one more hill before its right. Once transform is correct, it'll be downhill the rest of the way.

There's probably a concentrated month left of work to get to that point, but I can't justify spending thousands in living expenses right now to do it. The biggest way to help would be to help me find a sponsor for the project.

[serle]

Any updates yet, or is the project in permanent stasis

[Jocs]

@josephg Hi, excuse me, what is the current status of this project? Has the status been available?

[josephg]

Hi everyone!

I've been taking another look at this over the last couple days, mostly just playing whack-a-mole with bugs. The fuzzer is particularly apt at finding corner cases I didn't think of. I'm pretty convinced that apply and compose are completely correct now, given that the fuzzer happily thrashes them for 100k+ iterations now. When the fuzzer thrashes my transform function, it takes ~3.8k iterations before crashing now. This is up from 30 iterations yesterday. I suspect that there's no more than a dozen or so more obscure bugs hiding out. Most of the bugs are 1-2 hours work to find the right 1-5 line fix. Fingers crossed there's no surprises in the remaining bugs.

I'm still convinced that there's a nice implementation hiding amongst the weeds here that I'm not clever enough to find, but it might not matter - the code is converging toward becoming correct anyway. If anyone feels keen to make a compatible implementation in another langage, I'd love to see your work once you get all the test cases passing. For myself, once the fuzzer tells me the code is correct, I intend to leave the messy code as-is. Correct is correct.

Speaking of the code, its definitely usable at this point. I think you'd be very unlucky to run into any of the remaining bugs. After this spike I want to strip the debugging code, I plan to clean it up a little and publish the module on npm. Expect that to happen in the next week or two.

What I wrote last year in this issue tracker above still stands. There's still a few things I still have open question marks about:

• There are certain unfortunate operation pairs for which there is no good transform result. Things like "move a inside b" vs "move b inside a". Currently the code responds by emitting operations that delete both a and b in this case. I think it makes more sense whenever user data will be deleted to have transform instead throw an error or somehow return a conflict marker. These situations should be rare, but its still not great when they happen. (A rare exception is bad too, but I think its less bad.)
• Currently the ot-text type uses UCS2 character offset locations. This is efficient in javascript but its a bit dangerous, and a hassle to translate in other languages. If you're using the JS library everywhere you won't have any problems, but if you want to interoperate with rust or C you'll run into problems as soon as you throw some emoji on the screen. I'd like to standardize on UTF8 across the board - although the problem is that applying a UTF8 text operation naively in JS will require scanning the codepoints in the string with every operation. And thats O(n) with the size of the string. There are solutions to that (namely, use a fancy data structure instead of a JS string). But that'll all require a bit of thought.
• There's a bunch of utility methods which json1 needs. At a minimum, conversion to and from JSON0 operations and a transform-path function. JSON0 compatibility would also be good to provide people with an upgrade path - JSON1 has a superset of features, and running the JSON0 test suite and fuzzer on the new codebase will be quite satisfying. But that said, this stuff can be slowly added once the core logic is working.

[Jocs]

It’s great to see you start updating this project, and with new developments, when json1 is available, I will use it as the core logic is working. thank you!

[josephg]

Thanks for saying so! Knowing other people care about this stuff too is very motivating ☺️

[joeleaver]

I care too! I'm very excited for this.

On Fri, Nov 30, 2018, 1:27 PM Seph Gentle <notifications@github.com wrote:

Thanks for saying so! Knowing other people care about this stuff too is very motivating ☺️

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/josephg/json1/issues/4#issuecomment-443344663, or mute the thread https://github.com/notifications/unsubscribe-auth/AAEkz9HvzsuI2zF9Ou36bgwyDCYArELcks5u0aKmgaJpZM4JKnB_ .

[michael-brade]

So am I!

[josephg]

Awesome :)

Since you're all keen.. I want some feedback on something. Sometimes two operations try to mutually destroy one another's contents. Eg, op1 moves doc.a -> doc.b.x and op2 moves doc.b -> doc.a.x.

There's two ways transform could respond:

• Option 1: Detect this and make the operations delete the contents of both doc.a and doc.b
• Option 2: Detect this and throw an exception when it happens

Note that its a pretty rare thing to happen by accident. If we throw, lots of applications won't expect an exception and that could cause problems. But silently deleting user data is generally a Really Bad Thing and in my own applications I'll probably want this behaviour. (I'm considering making transform optionally throw on all instances of deleted user data.)

My question is this: I'm going to implement option 2. But is it worth also implementing option 1? Recovering here is tricky, and I'm not sure if its worth doing the work.

[joeleaver]

I think Option 2 is correct. Nothing should delete that isn't explicitly a delete.

On Sat, Dec 1, 2018, 4:07 PM Seph Gentle <notifications@github.com wrote:

Awesome :)

Since you're all keen.. I want some feedback on something. Sometimes two operations try to mutually destroy one another's contents. Eg, op1 moves doc.a -> doc.b.x and op2 moves doc.b -> doc.a.x.

There's two reasonable responses that transform could have:

• Option 1: Detect this and make the operations delete the contents of both doc.a and doc.b
• Option 2: Detect this and throw an exception when it happens

Note that its a pretty rare thing to happen by accident. If we throw, lots of applications won't expect an exception and that could cause problems. But silently deleting user data is generally a Really Bad Thing and in my own applications I'll probably want this behaviour. (I'm considering making transform optionally throw on all instances of deleted user data.)

My question is this: I'm going to implement option 2. But is it worth also implementing option 1? Recovering here is tricky, and I'm not sure if its worth doing the work.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/josephg/json1/issues/4#issuecomment-443469299, or mute the thread https://github.com/notifications/unsubscribe-auth/AAEkz4C_J94rDu97yzVyXGtzkdoKD6HIks5u0xmzgaJpZM4JKnB_ .

[michael-brade]

Yeah, I agree, Option 2 seems to be correct. Actually, I don't quite understand why this scenario should result in a complete delete (technically, yes, but not intentionally). Apparently the authors of those operations just wanted to move their stuff to another node and created a conflict. Since with trees actual unresolvable conflicts are possible (which is not the case for OT on a string/list), an exception seems ok to me.

[josephg]

OT and CRDT traditionally are conflict-free. Thats part of the point of them. But yeah; I think thats probably the wrong baggage to carry here. Mostly conflict free seems more correct.

Deleting arguably makes sense in some situations - like, if I move a file into a directory at the same time as you delete the directory, its reasonable that my file gets deleted too. Although I can also see the argument that this should generate a conflict instead. And if the operations are live user interactions, deleting is not a big deal because you'll see the delete immediately. In a 3d modelling program, I add a primitive to a car and you delete the car. The primitive gets deleted too. So long as its clear to me that you deleted the car I was working on, thats not a big correctness problem.

I've been thinking about the APIs internally. I've been trying to avoid transform having different modes because of the complexity burden. I think I know how I want to do it now. I think I'm going to change how the transform function itself works so it either returns {ok:true, result:<transformed output>} or {ok:false, conflicts:[... {path:[...], conflictType:'insertInRemovedTree' / 'blackhole' / ...}]}.

Then the standard transform function will call that and throw if there are conflicts. And I can also add a no-conflict wrapper which calls transformRaw, and if there are errors it would delete everything at all the paths which conflict and try again.

[michael-brade]

I agree with your examples, but in those cases that you mention, one operation is a true "delete", so there is no surprise and I wouldn't want a conflict or an exception here. In case of two conflicting moves, I'm not so sure I'd call that "delete"...

I've been thinking about the APIs internally. I've been trying to avoid transform having different modes because of the complexity burden. I think I know how I want to do it now. I think I'm going to change how the transform function itself works so it either returns {ok:true, result:<transformed output>} or {ok:false, conflicts:[... {path:[...], conflictType:'insertInRemovedTree' / 'blackhole' / ...}]}.

Then the standard transform function will call that and throw if there are conflicts. And I can also add a no-conflict wrapper which calls transformRaw, and if there are errors it would delete everything at all the paths which conflict and try again.

YES!! This is awesome. I really like this idea :)

[josephg]

Yes true! The different times we get conflicts are:

• op1 moves or inserts into a location that has been deleted by op2
• op1 and op2 both try to insert different values at the same place in an object
• blackhole - op1 and op2 try to move objects inside one another
• An embedded edit throws / generates a conflict in the same way

I'm probably forgetting a few cases - I'll make a proper list as I write the code.

There's also some things that I think shouldn't conflict. (What do you think?)

• op1 moves something out of a location deleted by op2. The object you're moving out has already been deleted, and I think op2's intent is clearly to delete all of op2.
• op1 moves or edits something entirely within an object that was deleted by op2. Again, op2 deleted it so your edits turn into noops.

[michael-brade]

There's also some things that I think shouldn't conflict. (What do you think?)

• op1 moves something out of a location deleted by op2. The object you're moving out has already been deleted, and I think op2's intent is clearly to delete all of op2.

Hm. This one is not so obvious...

What if op1 (moving b out of x.a) happens 10 minutes before another user submits op2 (deleting x.a)? Then we should be able to move out of the (not yet deleted) x.a, right? But in OT we don't have timestamps, only versions, right? So we don't know how long the delete happened before the move.

But: even if both operations happen at the same time, or the other way around, don't you think that the intention of op2 is fulfilled by deleting the child a of x, irregardless of someone else taking something out of a and moving it elsewhere?

I'd say it this way: op2's intention is to not have a be a child of x. op2's intention is not to destroy a. (Well, it might be, but we don't know, do we? And I would interpret ops in a way that is least destructive)

So yes, this case shouldn't conflict, but neither should op1 become a noop.

• op1 moves or edits something entirely within an object that was deleted by op2. Again, op2 deleted it so your edits turn into noops.

This one is easy: yes.

[josephg]

I'm most of the way through implementing this now - I'm just finishing up fixing some tests.

At the moment the API is looking like this:

• type.tryTransform(op1, op2, side) -> {ok:true, result} or {ok:false, conflict:{...}
• type.transform(op1, op2, side) -> result. Just a wrapper for tryTransform that throws if a conflict happens
• type.transformNoConflict(op1, op2, side) -> result. Always recovers from conflicts, just like the old behaviour. May delete user data in the process.

Its a bit all or nothing like this. Given that I think most of the time you'll want to auto-recover from some conflicts but not others I might add a recoverFromConflicts:... option or something.

I've decided to make an invariant with conflicts that if transform(op1, op2, 'left') generates an error, transform(op2, op1, 'right') must generate the same error.

The current implementation has 3 different conflicts:

• RM_UNEXPECTED_CONTENT: One operation removed an object and the second operation inserted or moved something into the object that was removed, or edited something inside the removed content. Eg rm x vs ins x.a = 5 or rm x vs some embedded string op
• DROP_COLLISION: Two drops (or two inserts, or a drop and an insert) tried to insert into the same location. Eg: ins x = 5 vs ins x = 6. We don't generate a conflict if the inserts are identical.
• BLACKHOLE: The operations made an object get unparented, and instead contain itself. Eg: mv x -> y.a vs mv y -> x.a

These things don't currently conflict:

1. op1 moves an object that was removed by op2

Eg: mv x -> y vs rm x

I'm reasonably happy with 1. @michael-brade:

op2's intention is not to destroy a. (Well, it might be, but we don't know, do we? And I would interpret ops in a way that is least destructive)

We sort of do know. From op2's point of view, the document contained the x.a property when they submitted their rm operation. So I think the intent is to remove x.a, and I feel comfortable safely preserving that.

2. op1 and op2 both move the same object to different locations

Eg: mv x -> y vs mv x -> z

This is an interesting case. This is really easy for transform to detect, and there are probably cases where users will want to disallow this. Given we have all the rest of the conflict infrastructure, I'm tempted to add a conflict for this.

The API I'm expecting people to use will be something like transform(op1, op2, 'left', {autoRecoverFrom: [RM_UNEXPECTED_CONTENT, DROP_COLLISION]}). So I'd rather add this now if we decide its important. But I don't know! Thoughts? Can anyone think of any use cases where you'd explicitly want this to conflict?

3. op2 does an embedded edit on an object that op1 removed

EDIT: I've implemented this and rolled it into RM_UNEXPECTED_CONTENT.

Eg: at x, make embedded rich text edit {...} vs rm x

This one is killing me. This will come up if, for example, Alice is typing into a field and Bob deletes the entire row. The standard way to handle this is to just delete the embedded operation too. But the problem with that is that if the embedded operation inserts a whole bunch of user content, we'll be deleting their new content too. I mean, this is exactly what the RM_UNEXPECTED_CONTENT error is for.

I think I might make a conflict for this too - although you'll generally want to auto recover from this.

[dcworldwide]

This is such an important body of work thankyou. When I review the code...its mind boggling tbh to wrap your jead around. This is a clear case where typescript would add much needed self documentation, rigor / compiler checks and refactoring support