UndoManager and DOM Transaction

Editor's proposal — 20 October 2011

Editor:
Ryosuke Niwa <rniwa@webkit.org>
Acknowledgements
Anne van Kesteren, Annie Sullivan, Alex Russell, Ehsan Akhgari, Eric Uhrhane, Frederico Caldeira Knabben, Ian Hickson, Johan "Spocke" Sörlin, Jonas Sicking, Ojan Vafai
Latest version:
http://rniwa.com/editing/undomanager.html
Previous versions:
http://rniwa.com/editing/undomanager-2010-10-09.html
http://rniwa.com/editing/undomanager-2011-09-11.html
http://rniwa.com/editing/undomanager-2011-08-30.html
http://rniwa.com/editing/undomanager-2011-08-09.html
http://rniwa.com/editing/undomanager-2011-08-08.html
http://rniwa.com/editing/undomanager-2011-07-26.html
Use cases:
http://rniwa.com/editing/undomanager-usecases.html

Status

This document is an early proposal of the specification for Undo Manager and DOM transaction. This specification will replace the UndoManager section of the main HTML specification.

Table of Contents

  1. 1 Introduction
  2. 2 Undo Scope and Undo Manager
    1. 2.1 Definitions
    2. 2.2 Undo scope
      1. 2.2.1 Undo scope and contenteditable
      2. 2.2.2 undoScope IDL attribute
    3. 2.3 The UndoManager interface
      1. 2.3.1 undoManager IDL attribute
    4. 2.4 Undo: moving back in the undo transaction history
    5. 2.5 Redo: moving forward in the undo transaction history
  3. 3 Transaction and DOM changes
    1. 3.1 Mutations of DOM
    2. 3.2 The Transaction interface
    3. 3.3 Automatic transactions
      1. 3.3.1 Undoability and Redoability of Automatic Transactions
      2. 3.3.2 Applying, Unapplying, and Reapplying Automatic Transactions
    4. 3.4 Manual transactions
  4. 4 Transaction Event
    1. 4.1 The TransactionEvent interface

1 Introduction

This specification defines the API to manage user agent's undo transaction history (also known as undo stack) and make objects that can be managed by the undo transaction history.

Many rich text editors on the Web add editing operations that are not natively supported by execCommand and other Web APIs. For example, many editors make modifications to DOM after an user agent executed user editing actions to work-around user agent bugs and to customize for their use.

However, doing so breaks user agent's native undo and redo because the user agent cannot undo DOM modifications made by scripts. This forces the editors to re-implement undo and redo entirely from scratch, and many editors, indeed, store innerHTML as string and recreate the entire editable region whenever a user tires to undo and redo. This is very inefficient and has limited the depth of their undo stack.

Also, any Web app that tries to mix contenteditable region or text fields with canvas or other non-text editable regions will have to reimplement undo and redo of contenteditable regions as well because the user agent typically has one undo transaction history per document, and there is no easy way to add new undo entry to the user agent's native undo transaction history.

This specification tries to address above issues by providing ways to define undo scopes, add items to user agent's native undo transaction history, and create a sequence of DOM changes that can be automatically undone or redone by user agents.

2 Undo Scope and Undo Manager

2.1 Definitions

The user agent must associate an undo transaction history, a list of transaction and transaction group entries, with each UndoManager object.

The undo transaction history has an undo position. This is the position between two entries in the undo transaction history's list where the next entry represents what needs to happen when undo is done, and the previous entry represents what needs to happen when redo is done.

The undo scope is the collection of DOM nodes that are managed by the same UndoManager. A document node or an element with undoscope attribute that is either an editing host or not editable defines a new undo scope, and all descendent nodes of the element, excluding elements with and descendent nodes of elements with undoscope attribute, will be managed by a new UndoManager. An undo scope host is a document, or an element with undoscope attribute that is either an editing host or not editable.

2.2 Undo scope

The undoscope attribute is a boolean attribute that controls the default undo scope of an element. It is to separate undo transaction histories of multiple editable regions without scripts. Using undoscope content attribute, authors can easily set text fields in a widget to have a separate undo transaction histories for example.

When the undoscope content attribute is added to an editing host or an element that is not editable, the user agent must define new undo scope for the element, and create a new UndoManager to manage any DOM changes made to all descendent nodes of the element excluding undo scope hosts and their descendents.

When the undoscope content attribute is removed from an editing host or an element that is not editable, the user agent must remove all entries in the undo transaction history of the corresponding undo scope without unapplying or reapplying them and destroy the corresponding UndoManager for the scope. After the removal, the node from which the content attribute is removed and their descendent nodes, excluding undo scope hosts and their descendents, belong to the undo scope of the closest ancestor with the undoscope content attribute or of the document.

2.2.1 Undo scope and contenteditable

contenteditable content attribute does not define a new undo scope and all editing hosts share the same UndoManager by default. And the undoscope content attribute on an editable element is ignored.

When the contenteditable content attribute is added to an element, the user agent must remove all entries in the undo transaction histories of the editable undo scope hosts that are descendent of the element and have become editable without unapplying or reapplying the entries and destroy the corresponding UndoManagers as if the undoscope content attribute was removed from all descendent nodes excluding undo scope hosts and their descendents.

Conversely, when the contenteditable content attribute is removed from an element, the user agent must define new undo scope for each descendent element with the undoscope content attribute and create a new UndoManager to manage any DOM changes made to descendents of each element, excluding undo scope hosts and their descendents, as if the undoscope content attribute was re-added to descendent elements with the undoscope content attribute.

2.2.2 undoScope IDL attribute

partial interface Element {
    attribute boolean undoScope;
};
element . undoScope

Returns true if the element is an undo scope host and false otherwise.

The undoScope IDL attribute of Element interfaces must reflect the undoscope content attribute.

2.3 The UndoManager interface

To manage transaction entries in the undo transaction history, the UndoManager interface can be used:

interface UndoManager {
    void transact(in Object transaction, in boolean merge);
    void undo();
    void redo();
    getter Transaction item(in unsigned long index);
    readonly attribute unsigned long length;
    readonly attribute unsigned long position;
    void clearUndo();
    void clearRedo();
};
document . undoManager

Returns the UndoManager object.

element . undoManager

Returns the UndoManager object.

undoManager . transact(transaction, merge)

Clears entries above the current undo position, and applies transaction, and pushes it to the undo transaction history. It also forms a transaction group if merge is set to true.

undoManager . undo()

Unapplies the transaction or all transactions in the transaction group immediately after the current position and increments position by 1 if position < length.

undoManager . redo()

Reapplies the transaction or all transactions in the transaction group immediately before the current position and decrements position by 1 if position > 0

undoManager . position

Returns the number of the current entry in the undo transaction history. (Entries at and past this point are redo entries.)

undoManager . length

Returns the number of entries in the undo transaction history.

data = undoManager . item(index)
undoManager[index]

Returns the entry with index index in the undo transaction history.

Returns null if index is out of range.

undoManager . clearUndo()

Removes entries in the undo transaction history before position and resets position to 0.

undoManager . clearRedo()

Removes entries in the undo transaction history after position.

UndoManager objects represent and manage their node's undo transaction history.

The object's supported property indices are the numbers in the range zero to length-1, unless the length is zero, in which case there are no supported property indices.

The transact(transaction, merge) will

  1. If this UndoManager is already in the process of applying, unapplying, or reapplying a transaction, then throw INVALID_ACCESS_ERR and stop.
  2. Clear all transactions or transaction groups between before the current undo position.
  3. Apply the transaction.
  4. If merge is not set to true, add transaction to the top of undo transaction history and go to step 8.
  5. Otherwise, if the first entry in the undo transaction history was a transaction group, then add transaction to the top of the array that forms the transaction group and go to step 8.
  6. Otherwise, create a new array and insert the new transaction and the first entry in undo transaction history to the array in the respective order to form a new transaction group.
  7. Replace the the first entry in undo transaction history by the new transaction group.
  8. Fire a transaction event for the transaction applied in step 3 at the undo scope host of this UndoManager if undo scope host is still in the document and UndoManager had not already been destroyed.

The undo() unapplies the transaction immediately after the undo position and moves the undo position forward (position is incremented by 1) if position < length and UndoManager is not already in the process of applying, unapplying, or reapplying a transaction. If UndoManager is already in the process of applying, unapplying, or reapplying, then it must throw INVALID_ACCESS_ERR and stop. Otherwise, it must do nothing.

The redo() reapplies the transaction immediately before the undo position and moves the undo position backward (position is incremented by 1) if position > 0 and UndoManager is not already in the process of applying, unapplying, or reapplying a transaction. If UndoManager is already in the process of applying, unapplying, or reapplying, then it must throw INVALID_ACCESS_ERR and stop. Otherwise, it must do nothing.

The item(n) method must return the nth transaction's associated data in the undo transaction history, if there is one, or null otherwise.

Being able to access an arbitrary element in the undo transaction history is needed to allow scripts to determine whether new transaction and the last transaction should form a transaction group.

The position attribute must return the index of the undo position in the undo transaction history. If there are no transactions to redo, then the value must be same as length attribute. If there are no transactions to do, then the value must be zero.

The length attribute must return the number of entries in the undo transaction history. This is the length.

The clearUndo() method must remove all entries in the undo transaction history before the undo position. It also moves the undo position to the top (position is set to zero).

The clearRedo() method must remove all entries in the undo transaction history after the undo position.

The active undo manager is the UndoManager of the focused node in the document. If no node has focus, then it's assumed to be of the document.

A transaction group is an array of consecutive transactions that belong to the same UndoManager such that all transactions in the array are unapplied and reapplied together in one undo or redo. A transaction group is formed when a transaction is applied via UndoManager's transact() method with merge set to true and the UndoManager already has a transaction group or a transaction.

A typical use case for a transaction group is typing where insertions of multiple letters, spaces, and new lines can be undone or redone in one step.

When transactions in a transaction group are unapplied, the user agent must unapply each transaction in the array that forms the transaction group in the ascending order from the first entry to the last entry. When transactions in a transaction group are reapplied, the user agent must reapply each transaction in the array in descending order from the last entry to the first entry.

In the following example, letters "o" and "k" are inserted by two automatic transactions that form one transaction group. A br element and string "hi" are then inserted by other two automatic transactions to form another transaction group. All transactions have the label "Typing".

// Assume myEditor is some element that has undoscope attribute, and insert(node) is a function that inserts the specified node at where the caret is.
myEditor.undoManager.transact({apply: function () { insert(document.createTextNode('o')) }, label: 'Typing'});
myEditor.undoManager.transact({apply: function () { insert(document.createTextNode('k')) }, label: 'Typing'}, true);
myEditor.undoManager.transact({apply: function () { insert(document.createElement('br')) }, label: 'Typing'});
myEditor.undoManager.transact({apply: function () { insert(document.createTextNode('hi')) }, label: 'Typing'}), true);

When the first undo is executed immediately after this code is ran, the last two transactions are unapplied, and the br element and string "hi" will be removed from the DOM. The second undo will unapply the first two transactions and remove "o" and "k".

Because Mac OS X and other frameworks expect applications to provide an array of undo items, simply dispatching undo and redo events and having scripts manage undo transaction history would not let the user agent populate the native UI properly.

2.3.1 undoManager IDL attribute

partial interface Element {
    attribute UndoManager undoManager;
};
element . undoManager

Returns the UndoManager object associated with the element's undo scope if the element is an undo scope host, or null otherwise.

partial interface Document {
    attribute UndoManager undoManager;
};
document . undoManager

Returns the UndoManager object associated with the document.

The undoManager IDL attribute of Document and Element interfaces must return the object implementing the UndoManager interface for the undo scope if the node is an undo scope host. If the node is not an undo scope host, it must return null.

2.4 Undo: moving back in the undo transaction history

When the user invokes an undo operation, or when the execCommand() method is called with the undo command, the user agent must perform an undo operation on the active undo manager.

If the undo position is at the end of the undo transaction history (position is equal to length), then the user agent must do nothing.

Otherwise, the user agent must unapply the transaction immediately after the undo position and move the undo position forward (increment position by 1).

2.5 Redo: moving forward in the undo transaction history

When the user invokes a redo operation, or when the execCommand() method is called with the redo command, the user agent must perform an redo operation on the active undo manager.

If the undo position is at the beginning of the undo transaction history (position is zero), then the user agent must do nothing.

Otherwise, the user agent must reapply the transaction immediately before the undo position and move the undo position backward (decrement position by 1).

3 Transaction and DOM changes

A transaction is an ordered set of DOM changes associated with a unique undo scope host that can be applied, unapplied, or reapplied.

To apply a transaction means to make the associated DOM changes under the associated undo scope host. And to unapply and to reapply a transaction means, respectively, to revert and to remake the associated DOM changes under the associated undo scope host.

A transaction can be unapplied or reapplied if it appears, respectively, immediately after or immediately before the undo position in the associated UndoManager's undo transaction history.

3.1 Mutations of DOM

DOM changes of an element are any changes to the element and its descendent nodes that may trigger DOM level 3's DOM mutation events. This includes but not limited to the following mutations:

HTML5 spec says that internal state changes should be considered as DOM changes but in practice, it's infeasible to store all document states.

The DOM state of an element is the state of all descendent elements and their attributes that are transient under DOM changes of the element.

To restore DOM state of a node means to undo DOM changes made to the node by means of inserting, removing, or moving descendent nodes or attributes of the node.

3.2 The Transaction interface

[NoInterfaceObject]
interface Transaction {
    attribute DOMString label;
    attribute Function? apply(in boolean isReapply);
    attribute Function? unapply;
    attribute Function? reapply;
    attribute boolean isAutomatic;
};

The Transaction interface is to be implemented by content scripts that implement a transaction.

label attribute must return null or a string that describes the semantics of the transaction such as "Inserting text" or "Deleting selection". The user agent may expose this string or a part of this string through its native UI such as menu bar or context menu.

apply, unapply, and reapply are attributes that must be supported, as IDL attributes, by objects implementing the Transaction interface.

isAutomatic attribute must return true if the transaction is a automatic transaction, and false if it is a manual transaction while the transaction is being applied. Any changes made to the value of the isAutomatic attribute after the transaction had been applied should not change the type of the transaction.

3.3 Automatic transactions

An automatic transaction is a transaction where DOM changes are tracked by the user agent and the logic to unapply or reapply the transaction is implicitly created by the user agent.

3.3.1 Undoability and Redoability of Automatic Transactions

The highest node affecting an automatic transaction of an automatic transaction is the highest node whose DOM state is modified in unapplying or reapplying the transaction.

It is the editing host of the lowest common ancestor of nodes, inside the undo scope associated with the UndoManager to which the transaction is added, mutated while applying the transaction. Otherwise, it is the lowest common ancestor of nodes, inside the undo scope associated with the UndoManager to which the transaction is added, mutated by the transaction. For the purpose of determining a whether a transaction mutates a node or not, inserting, removing, or replacing a child node is considered to be modifying the node.

For example, if an automatic transaction mutates a node inside a contenteditable div, then the highest node affecting this automatic transaction is the div. If the transaction also temporarily removes the div and inserts back to where it was, then the highest node affecting it is the parent of the div.

3.3.2 Applying, Unapplying, and Reapplying Automatic Transactions

When an automatic transaction is applied, the function returned by the apply attribute is called with isReapply set to false if the attribute returns a valid function object. All DOM changes made by the method in the corresponding undo scope of the UndoManager must be tracked by the user agent.

The process of applying, unapplying, or reapplying an automatic transaction can be interfered by event listeners when event listeners, particularly of mutation events, make DOM changes to the highest node affecting the automatic transaction while the user agent is applying, unapplying, or reapplying the transaction. When an automatic transaction is interfered by event listeners, the user agents may immediately terminate or, to its best effort, continue the process of applying, unapplying, or reapplying the transaction.

When an automatic transaction is unapplied, and the DOM state of the highest node affecting the automatic transaction is identical to that of immediately after applying the transaction, the user agent must fully restore the DOM state of the highest node affecting the automatic transaction to that of immediately before applying the transaction unless interfered by event listeners. If the DOM state of the highest node affecting the automatic transaction is not identical to that of immediately after applying the transaction, then the user agent still must do its best effort to restore the DOM state.

When an automatic transaction is reapplied, and the DOM state of the highest node affecting the automatic transaction is identical to that of immediately after unapplying the transaction and immediately before applying the transaction, the user agent must fully restore the DOM state of the highest node affecting the automatic transaction to that of immediately before unapplying the transaction and immediately after applying the transaction unless interfered by event listeners. If the DOM state of the highest node affecting the automatic transaction is not identical to that of immediately after applying the transaction, then the user agent still must do its best effort to restore the DOM state of all nodes mutated by the transaction.

Any DOM changes made outside of the undo scope in applying the transaction should take effect immediately in the document but should not be undone or redone by the user agent when unapplying or reapplying the transaction.

The user agent must implement user editing actions and drag and drop as automatic transactions, and any application defined automatic transactions must be compatible with user editing actions.

TODO: Need to restore selection as well.

3.4 Manual transactions

A manual transaction is a transaction where the logic to apply, unapply, or reapply the transaction is explicitly defined by an application. It provides a way to communicate with user agent's undo transaction history, e.g. to populate user agent's undo menu.

When a manual transaction is applied, the function returned by the apply attribute is invoked with isReapply set to false if the attribute returns a valid function object.

When a manual transaction is unapplied, the function returned by the unapply attribute is invoked if the attribute returns a valid function object.

When a manual transaction is reapplied, the function returned by the reapply attribute is invoked if the attribute returns a valid function object. If the reapply attribute returned null or undefined, then the function returned by apply attribute is invoked with isReapply set to true instead if the attribute returns a valid function object.

Manual transactions may be incompatible with automatic transactions, in particular, with user editing actions if manual transaction mutates descendant nodes of the highest node affecting automatic transactions and do not restore the DOM state of the highest node affecting automatic transactions prior to unapplying or reapplying automatic transactions.

4 Transaction Event

When a new transaction is applied by transact() method to an undo transaction history of a UndoManager, the user agent must fire a transaction event using the TransactionEvent interface.

4.1 The TransactionEvent interface

interface TransactionEvent : Event {
    readonly attribute Object transaction;
    readonly attribute Node host;
    void initTransactionEvent(in DOMString typeArg, in boolean canBubbleArg, in boolean cancelableArg);
};
transactionEvent . transaction

Returns the transaction object that triggered this event.

The initTransactionEvent() method must initialize the event in a manner analogous to the similarly-named method in the DOM Events interfaces.

The transaction attribute of the TransactionEvent interface must return the object that implements the Transaction interface that triggered the event.

When the user agent is required to fire a transaction event for a transaction t at an undo scope host h, the user agent must run the following steps:

  1. Create a TransactionEvent object and initialize it to have the name "transaction", to bubble, to be cancelable, and to have the transaction attribute initialized to t.
  2. Dispatch the newly created TransactionEvent object at the node h.