[WebODF] Undo/redo actions

[Philip Peitsch]

Hi everybody,

I've been considering the following thought experiment for undo/redo:

1. Doc state = A
2. Op A is performed by Mandy, Doc state = B
3. Op B is performed by Fred, Doc state = C
4. Mandy hits undo on her local editor
5. Doc state = ??

What does Mandy expect to have happen? Does this undo Op A or Op B?

Etherepad's timeline view is a global undo stack, i.e., you can undo changes from
any person to revert the document back to a previous state.

In contrast, when typing on a collaborative document, does the user expect undo
to revert *their* most recent change, or the *document's* most recent change?

This leads directly into the next question. Does undo either:

a) revert the document to a previous state, resulting in a document in an identical
state as before the operation was originally performed
e.g.,
1. Doc state = A
2. Op A is performed, Doc state = B
3. Op A is undone via magic, Doc state = A

OR
b) undo a previous action, resulting in a document that is *similar* but not 
identical to before the operation was performed
1. Doc state = A
2. Op A is performed, Doc state = B
3. Op A is undone via magic, Doc state = C

What is the difference you ask?
Undo for direct formatting, range removal, etc. is really tricky because in the
current implementations data is irretreviably lost as part of execution. The
interactions are also far more complex than most other operations.

E.g., 
What should happen if Fred inserts new text into the middle of a block Mandy is removing?
What should happen if Fred inserts new text into the middle of a block Mandy is formatting?

To implement undo option A with these types of operations the ops must be re-written
to do less, pushing the complexity out into what generates the op. E.g., OpRemoveText
is only allowed to remove text nodes, and SessionController (or a helper) is
responsible for coming up with the exact list of text nodes to be removed, and
generating an OpRemoveText for each of these.

If however Option B is acceptable (i.e., the document should be visually
indistinguishable, but is allowed to be different at the DOM level) there is another
potential solution. 

Assuming option B and local undo stack:
* Each client will generate their own local undo stack as each local operation is
 executed.
* This local undo stack is rebased on every external change using the standard OT
 behaviours, and is not shared.
* At the point the user undoes their recent change, the undo operations are forwarded
 from their local client as if it was a normal change.
 
 Thoughts, criticisms, concerns or shouting are all welcome :)
  
 Philip