Undo in share.js

[Richard Davis]

 Hi Joseph,

I'm trying to build a collaborative document editor at my university, and I discovered this a few weeks ago. Thanks for doing it. I think it's awesome.

I have a crazy idea that I might be able to implement collaborative undo inside share.js. Have you ever thought about that?

-Richard

[Cryptic Swarm]

Suppose you have a document with operations A, B, C applied.

A B C

You want to undo C.  You take the inverse of C and transform across any new ops.  In this case there are no new ops.

A B C C'

Now you want to undo B.  You need to take the inverse of B and transform across any newer ops.  In this case you need to transform the inverse of B across both C and C'.

A B C C' B'

Cheers

--
You received this message because you are subscribed to the Google Groups "ShareJS" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sharejs+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Richard Davis]

Yes, that part looks fairly straightforward, but what if two people are working at the same time?

User A: A1, A2, A3
User B: B1, B2, B3
Combined: A1, B1, A2, A3, B2, B3

Now say User A wants to undo A3 (call it A3'). Presumably, we'd have to transform A3' against B3 and B2 somehow (call it A3''), wouldn't we?

Combined: A1, B1, A2, A3, B2, B3, A3''

I'm assuming share.js doesn't do this, and I'm wondering how long it would take to do it. (Is it a three-month project or a two-year project?) It seems like it might not be that hard, but I haven't thought through all the implications, and I wonder if anyone else has.

-Richard

[Joseph Gentle]

I've implemented it before and its pretty easy. It would take me a few
days to do. Its not a lot of code.

The OT type (doc.type) implements both invert() and tranform(). Well,
the new text type doesn't implement invert, but both text0 and json0
support it, and will support it forever. (Ask me why later).

You would want to do this:

undo = doc.type.invert(A3);
undo = doc.type.transform(undo, B2, 'left')
undo = doc.type.transform(undo, B3, 'left')
doc.submitOp(undo)

The 'left' is just a tie-breaker, and I don't think its really important here.

To see all the OT methods ShareJS's types provide, look here:
https://github.com/share/ottypes

You just need to hook in to the client in all the right places and
update your whole undo stack.

-J

[Richard Davis]

Awesome! Thanks.

-Richard

[Stas Sl]

Hi!

I understand how to implement undo, but I faced a problem when trying to implement undo/redo functionality.

Let's say we have operations:

A B C

Then user undoes C and B:

A B C C' B'

where C'=inverse(C), B'=transform(inverse(B), [C, C'])

Then he redoes B:

A B C C' B' B''

where B''=transform(B, [C, C', B'])

Then he tries to undo B once again:

A B C C' B' B'' B'''

where B'''=transform(inverse(B), [C, C', B', B''])

but B''' becomes [] (noop), but it should be B''' = B'

Am I doing smth wrong?

const json = require('./lib/json0')

const _ = require('lodash')

const transform = (x, ys) => {

  return _.reduce(ys, (x, y) => json.transform(x, y, 'left'), x)

}

let a = [{p: [0], li: 'a'}]

let b = [{p: [1], li: 'b'}]

let c = [{p: [2], li: 'c'}]

let c_ = json.invert(c)

let b_ = transform(json.invert(b), [c, c_])

let b__ = transform(b, [c, c_, b_])

let b___ = transform(json.invert(b), [c, c_, b_, b__])

let o = []

console.log(o)

json.apply(o, a); console.log(o)

json.apply(o, b); console.log(o)

json.apply(o, c); console.log(o)

json.apply(o, c_); console.log(o)

json.apply(o, b_); console.log(o)

json.apply(o, b__); console.log(o)

json.apply(o, b___); console.log(o)

console.log('b_ =', b_)       // [ { p: [ 1 ], ld: 'b' } ]

console.log('b___ =', b___)   // []

[John Hewson]

On Apr 11, 2017, at 03:06, Stas Sl <s.sl...@gmail.com> wrote:

Hi!

Hi Stas,

Am I doing smth wrong?

Yep, I actually implemented undo/redo in my app recently, so I'll explain :)

I understand how to implement undo, but I faced a problem when trying to implement undo/redo functionality.

Let's say we have operations:

A B C

Then user undoes C and B:

A B C C' B'

where C'=inverse(C), B'=transform(inverse(B), [C, C'])

Yes, C’ = inverse(C). However B’ is incorrect, it’s simply B’ = inverse(B). That’s because with a traditional undo stack, only the most recent operation which is at the top of the undo stack can be undone. So, ignoring any remote operations, the document is guaranteed to be in the same state as it was when the original  “do" operation was performed. All subsequent local operations which were on the undo stack must already have been undone.

In other words, a document with history A B C C’ is functionally identical to one with history A B and that’s all that matters.

Then he redoes B:

A B C C' B' B''

where B''=transform(B, [C, C', B’])

By the same logic, to redo B, simply apply B again. No transforms needed.

Then he tries to undo B once again:

A B C C' B' B'' B'''

where B'''=transform(inverse(B), [C, C', B', B'’])

The user shouldn’t be able to redo B without an immediately preceding undo of B, so this isn’t a valid case. Also note that B' cannot be applied to a document which already includes B, because when B' is applied the document must be in the same state it was immediately before B occurred, which of course it can’t be if it already includes B.

but B''' becomes [] (noop), but it should be B''' = B’

Again, B’’’ = B.

So is there anything you need to transform? Yes. Because we can’t undo remote users’ operations, those *do* need to be taken into account. When a remote operation is received you should transform the undo and redo stacks against that operation. That way, when you eventually apply the undo/redo operations, they have already been “rebased” to account for the new remote operations which the local user can’t undo.

Each time you receive a remote operation O, do the following:

For each operation U on the undo stack, U’ = O.transform(U, true) // true = left

For each operation R on the redo stack, R’ = O.transform(R, true) // true = left

Where ‘ just means the resulting op, not the inverse.

If however, you want to undo operations in an arbitrary order rather than using a traditional undo/redo stack, then the situation is far more complicated and none of what I’ve said applies any more.

Hope that makes sense,

— John

const json = require('./lib/json0')

const _ = require('lodash')

const transform = (x, ys) => {

  return _.reduce(ys, (x, y) => json.transform(x, y, 'left'), x)

}

let a = [{p: [0], li: 'a'}]

let b = [{p: [1], li: 'b'}]

let c = [{p: [2], li: 'c'}]

let c_ = json.invert(c)

let b_ = transform(json.invert(b), [c, c_])

let b__ = transform(b, [c, c_, b_])

let b___ = transform(json.invert(b), [c, c_, b_, b__])

let o = []

console.log(o)

json.apply(o, a); console.log(o)

json.apply(o, b); console.log(o)

json.apply(o, c); console.log(o)

json.apply(o, c_); console.log(o)

json.apply(o, b_); console.log(o)

json.apply(o, b__); console.log(o)

json.apply(o, b___); console.log(o)

console.log('b_ =', b_)       // [ { p: [ 1 ], ld: 'b' } ]

console.log('b___ =', b___)   // []

--
You received this message because you are subscribed to the Google Groups "ShareJS" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sharejs+u...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Stas Sl]

Hey, John, thanks a lot for the explanation!

Somehow I missed notification about your response :(( 

I had a discussion with Joseph back then https://github.com/ottypes/json0/issues/21 about this issue and also I was browsing some other implementations of undo/redo in Etherpad/Firepad. And from there I understood exactly what you are saying - that I need to rebase only on remote ops, not local.