Undo is a standard feature in most single-user interactive applications. The user can use undo to recover from erroneous operations, to learn system features by trial and error, and to explore alternative solutions by backtracking. The availability of undo in multi-user collaborative applications is particularly valuable because: (1) features available in single-user applications must also be available in corresponding multi-user applications to encourage users to learn, use, and adopt new collaborative applications; (2) the potential cost of an individual user's mistake is multiplied many times since it may adversely affect the work of a large number of collaborative users; and (3) the number of alternatives to be explored in a collaborative setting increases due to the presence of many users. However, supporting undo in multi-user collaborative applications is much more difficult than supporting undo in single-user interactive applications because operations performed by different users may interleave in an arbitrary way.
As an important mechanism for error recovery and exploration of alternatives in interactive and collaborative applications, an undo facility should be capable of undoing any operation at any time (or in any order). This capability is desirable since it is common for a user to detect a mistake after performing more than one operation, especially in the collaborative environment where the actions of multiple users may interfere with each other. Moreover, with the full assurance that any erroneous operation may be undone without discarding subsequent operations, users can be encouraged to learn and use group editors and to explore alternatives without fear. Various group-undo solutions have been proposed in the past, but none of them is able to undo any operation at any time. In this article, we contribute an undo solution with such a capability for group text editors. The basic idea is to interpret an undo command as a concurrent inverse operation by means of operational transformation.
The framework of the undo solution is shown in the figure above. An important strategy embedded in this framework is the separation of the undo policy that determines the scope and order of selecting operations for undo, from the undo mechanism that determines how to undo a selected operation in a given context. This strategy allows us to devise a single generic undo algorithm to support multiple undo scopes and modes. Two undo scopes are supported: the local undo scope allows a user to undo any operation performed by herself, and the global undo scope allows a user to undo any operation performed by any user. Undo modes include the single-step undo that allows a user to undo the last operation only, the chronologica l undo that allows a user to undo a sequence of operations in the reverse order of their executions, and the selective undo that allows a user to undo operations in any order. An undo scope can be combined with any undo mode. The ability to support multiple undo scopes and modes in the same group editor is highly desirable because different users may have different preference of undo scopes and modes, and different combinations of undo scopes and scopes can support different collaboration needs.
To cope with the complexity of group undo, we further divide the transformation-based undo mechanism into two layers: The high level transformation control algorithms determine which operations should be transformed against which other operations according to their causal relationships; and the low level transformation functions determine how to transform one operation against another operation according to the operation types, parameters and other relationships. The interface between these two layers is formally specified by a set of transformation properties and conditions. These transformation properties and conditions are used to guide the design of and to verify the correctness of control algorithms and transformation functions.
In this article, we discuss in detail an ANYUNDO algorithm that is capable of generating, transforming, and representing valid inverse operations in any context, and a set of transformation functions that are capable of preserving undo-related transformation conditions and properties. Formal proofs are provided to show that the undo transformation control algorithm achieves the required undo effect, undo property, and consistency properties. Solutions to all known undo puzzles are provided to show the soundness of the transformation functions. A Web-based group text editor REDUCE (REal-time Distributed Unconstrained Cooperative Editing) has been implemented to demonstrate the feasibility of the proposed undo solution and is discussed in this article as well. The proposed undo solution is generally applicable to collaborative applications that support concurrent insertion and deletion of shared documents consisting of one or multiple dimensions of linearly ordered data objects with positional references, such as XML documents with a tree-like structure.
Griffith University, Australia
©2003 ACM 1072-5220/03/0300 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2003 ACM, Inc.