[WebODF] Undo & Operation groups

[Friedrich W. H. Kossebau]

Am Freitag, 17. Januar 2014, 22:39:37 schrieb Philip Peitsch:
> Greetings webodfers,
> 
> I'm spending some time in the next 3 weeks improving the behaviour of
> undo slightly. I am specifically looking at fixing how undo states
> are created to group things more intuitively for the user.

Currently I see two places for grouping operations together (just stating, 
guess everyone sees the same):

a) when creating a set of operations based on a single state of the document, 
where the parameters of the (n+1)-th op could depend on the effects of the n-
th op. The set needs to be passed as one group, to be also applied in the same 
order. Once they are serialized, the grouping has no more meaning.

b) in the UI logic, because UI actions are often not directly mapped to a 
single operation, but multiple ones (UI actions could be seen as CISC, 
translated to operations which could be seen as RISC). To stay consistent in 
the UI, possible listings of what actions different users did and also the 
option to undo/redo those actions would be always described in the UI action 
terms. So this grouping (info) has to stay also when serialized, because it 
will be used later. User-defined macros could be seen similar to UI actions, 
just that they extend the "CISC" set.

Any c) etc.?

<snip content="example"/>

> I have two ideas for how to do this cleanly.
> 
> Option 1)
> Add an argument to the signalOperationStart & signalOperationEnd that
> specify the group being started. The group id can simply be an
> incrementing number or similar.
> 
> Pros -
> * Easy to implement
> * Group id only needs to be locally unique
> * Definitely not over-engineered :)
> * Very transient. Can't be accidentally leaked to other clients etc.
> * Maximum flexibility to how the server batches up operations
>   e.g., the server can choose to group multiple text inputs in the
>   same region into a single operation
> 
> Cons -
> * Very transient! No way to regain the group after the signal has
>   fired
> * No remote client will ever known how a batch of operations are
>   divided up
> 
> Option 2)
> Add a groupid (or transactionid) to each operation. Have the session
> assign a guid as the groupid so it is generally likely to be globally
> unique across all clients.
> 
> Pros -
> * Clean extension of current system. Easy to implement
> * Allows remote clients to reconstruct sensible undo states similar
>   to the local client (not that we support collab-undo yet)
> * Accessible to the local undo, or other consumers that might want to
>   be aware of this (e.g., save points?)
> 
> Cons -
> * Increases amount of data sent
> * No firm decisions as to how remote undo should work yet, so this
>   may not have any bearing on the "right" solution
> * Server cannot group operations from multiple clients or groups
>   (note, this doesn't stop LOCAL clients from performing clever
>   optimizations however)
> 
> There are other variations on the theme, but the thoughts are:
> * Are groups permanent or temporary?
> * Can groups be modified after being added to the session? (e.g.,
>   similar to how SQL transactions work)
> * How widely known is a group (local or remote)?
> * If groups are transmitted remotely, how do other clients know
>   when they have received all operations in a single group?
> * Again, if remotely received, can remote clients interleave ops
>   from multiple groups?

>From above use-cases for groups I would think:
* UI-action groups are permanent
* UI-action groups cannot be modified after being streamed (ignoring OT-
modification here)
* UI-action groups should be known remotely as well, ideally by a defined 
action set (but not required). A known UI action set would help with display 
(think action name translation). But custom macro names have translation 
issues in any case. Being known e.g. allows users do see in UI action terms 
what other users are doing (and undo that)
* a group start/end could be marked by setting start/end tag in the specs. If 
we also support nested groups (e.g. created by macros calling other macros) 
those tags would need to support that. Another option would be to have a tree 
structure in the serialization to express that, but I do not see a real gain, 
as some clients might just not care.
* at least with the idea of UI-action groups I see no reason to support 
interleaving, also no sense. Hm, comes the need e.g. from grouping consecutive 
insert operations by one user?

Related thought:
Grouped actions possibly need some kind of local lock, to make sure all 
operations belonging to the same UI action end up being applied/routed without 
other ops sneaking in. E.g. some UI action could be done in an interactive 
way, with intermediate steps already applied. That could also be useful for 
grouping related operations into one, like the consecutive inserting. Because 
in the timespan where one is quickly typing a word updates from other users 
might be not wanted as well, so such a lock could be synced with the timeout 
for when inserts will no longer be auto-grouped?

Open problem:
Given that at least with the OT approach different clients have different 
(groups of) operations applied, and usually not only in a different order. So 
they would also have different Undo stacks.
So should the history be normalized somehow?
What to do about groups whose operations are transformed completely into noops 
so would be currently just be forgotten?

So somehow I prefer option 1) for now, until there is a grand plan compiled. 
Unless we are quick enough with compiling one now.

Cheers
Friedrich
-- 
Friedrich W. H. Kossebau // KO GmbH
http://kogmbh.com/legal/