UndoManager and DOM Transaction

Editor's proposal — 1 December 2011

Editor:
Ryosuke Niwa <rniwa@webkit.org>
Acknowledgements
Anne van Kesteren, Annie Sullivan, Alex Russell, Aryeh Gregor, 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-2011-11-29.html
http://rniwa.com/editing/undomanager-2011-10-27.html
http://rniwa.com/editing/undomanager-2011-10-20.html
http://rniwa.com/editing/undomanager-2011-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://wiki.whatwg.org/wiki/UndoManager_Problem_Descriptions

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 Scoping Undo Transaction History
      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 forward in the undo transaction history
    5. 2.5 Redo: moving backward in the undo transaction history
  3. 3 DOM Transaction and DOM changes
    1. 3.1 Mutations of DOM
      1. 3.1.1 Reverting DOM changes
      2. 3.1.2 Reapplying DOM changes
    2. 3.2 The DOMTransaction interface
    3. 3.3 Automatic DOM transactions
    4. 3.4 Manual DOM transactions
  4. 4 Transaction, Undo, and Redo Events
    1. 4.1 The DOMTransactionEvent 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 sequences of DOM transactions, 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 Scoping Undo Transaction History

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 DOMTransaction[] 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 DOM transaction group if merge is set to true.

undoManager . undo()

Unapplies all DOM transactions in the entry immediately after the current position in the reverse order and increments position by 1 if position < length.

undoManager . redo()

Reapplies all DOM transactions in the entry 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 DOM transaction, then throw INVALID_ACCESS_ERR and stop.
  2. Clear all entries between before the current undo position without unapplying or reapplying the transactions in the entires.
  3. Apply the transaction.
  4. If merge is not set to true or there are no entries in the undo transaction history, create a new entry with exactly one transaction transaction and add it to the top of the undo transaction history and go to step 6.
  5. Otherwise, add transaction to the first entry in the undo transaction history.
  6. Fire a DOM 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() will

  1. If UndoManager is already in the process of applying, unapplying, or reapplying, then throw INVALID_ACCESS_ERR and stop.
  2. If positionlength, stop.
  3. Otherwise, unapply transactions tn, tn-1, ... t1 where t1, t2, ... tn is the sequence of DOM transactions for the entry immediately after the undo position and increment position by 1.
  4. Fire an undo event for the transaction unapplied 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 redo() will

  1. If UndoManager is already in the process of applying, unapplying, or reapplying, then throw INVALID_ACCESS_ERR and stop.
  2. If position ≤ 0, stop.
  3. Otherwise, reapply transactions t1, t2, ... tn where t1, t2, ... tn is the sequence of DOM transactions for the entry immediately before the undo position and decrement position by 1.
  4. Fire a redo event for the transaction unapplied 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 item(n) method must return a new array representing the nth entry in the undo transaction history if 0 ≤ nlength, or null otherwise.

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

The position attribute must return the index of the undo position in the undo transaction history. If there are no DOM transactions to undo, then the value must be same as length attribute. If there are no DOM transactions to redo, 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 after the undo position.

The clearRedo() method must remove all entries in the undo transaction history before the undo position, and move the undo position to the top (set position to zero).

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.

Each entry in the UndoManager consists of one or more DOM transactions, all of which are unapplied and reapplied togehter in one undo or redo.

Because item() returns new array on each call, modifying the array does not have any effect on the sequence of DOM transactions of the entry, and two return values of item() are alwys different objects.

document.undoManager.transact(...);
document.undoManager.transact(..., true);
document.undoManager.transact(..., true);
alert(document.undoManager.item(0).length); // Alerts 3
document.undoManager.item(0).pop();
alert(document.undoManager.item(0).length); // Still alerts 3
alert(document.undoManager.item(0) === document.undoManager.item(0)); // Alerts false

A typical use case for having multiple DOM transactions in one entry is for typing multiple letters, spaces, and new lines that must be undone or redone in one step.

In the following example, letters "o" and "k" are inserted by two automatic DOM transactions that form one entry in the undo transaction history of the UndoManager. A br element and string "hi" are then inserted by another two automatic DOM transactions to form entry in the undo transaction history. 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({executeAutomatic: function () {
    insert(document.createTextNode('o')); }, label: 'Typing'});
myEditor.undoManager.transact({executeAutomatic: function () {
    insert(document.createTextNode('k')); }, label: 'Typing'}, true);
myEditor.undoManager.transact({executeAutomatic: function () {
    insert(document.createElement('br')); }, label: 'Typing'});
myEditor.undoManager.transact({executeAutomatic: 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 forward 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 by calling the undo() method.

2.5 Redo: moving backward 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 by calling the redo() method.

3 DOM Transaction and DOM changes

A DOM 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 DOM transaction means to make the associated DOM changes under the associated undo scope host. And to unapply and to reapply a DOM transaction means, respectively, to revert and to remake the associated DOM changes under the associated undo scope host.

A DOM 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 a node is a sequence s1, s2, ... sn where each si with 1 ≤ i ≤ n is either one of:

The DOM state of a node is the state of all descendent nodes and their attributes that are affected by DOM changes of the element. If two DOM states of a node are equal, then the node and all its descendent nodes must be identical.

3.1.1 Reverting DOM changes

To revert DOM changes of the sequence s1, s2, ... sn, revert each si with 1 ≤ i ≤ n in the reverse order sn, sn-1, ... s1 as specified below:

To revert inserting a node into a parent before a child, run these steps:

  1. If node is not null and its parent is not parent, then terminate these steps.
  2. If child is not null and its parent is not parent, then terminate these steps.
  3. If child is not null and its previous sibling is not node, then terminate these steps.
  4. Pre-remove node from parent.

To revert removing a node from a parent, let child be the next sibling of node before the removal, and run these steps:

  1. If node is not null and its parent is not null, then terminate these steps.
  2. If child is not null and its parent is not parent, then terminate these steps.
  3. Pre-insert child into parent before child.

To revert replacing data of a node with an offset, count, and data, let replacedData be the substringed data with node, offset, and count before the replacement, and run these steps:

  1. If node's length attribute is less than offset, terminate these steps.
  2. Replace data of node with offset, the length of data, and replacedData.

To revert changing an attribute whose namespace is namespace and local name is localName to value, let oldValue be the content attribute value before the change, oldPrefix be the namespace prefix before the change, and change the attribute to oldValue and set the namespace prefix to oldPrefix.

To revert appending an attribute whose namespace is namespace and local name is localName to a node and setting the namespace prefix to prefix, run these steps.

  1. If a content attribute whose namespace is namespace and local name is localName doesn't exist on the node, then terminate these steps.
  2. Otherwise, remove the attribute whose namespace is namespace and local name is localName.

To revert removing an attribute whose namespace is namespace and local name is localName from a node, let oldValue be the content attribute value and oldPrefix be the namespace prefix both before the removal, and run these steps.

  1. If a content attribute whose namespace is namespace and local name is localName exists on the node, then terminate these steps.
  2. Otherwise, create and append the attribute whose namespace is namespace and local name is localName, with oldValue as the content attribute value and set the namespace prefix to oldPrefix.

To revert setting textarea element's value IDL attribute and input element's value IDL attribute to value, set element's value IDL attribute to the raw value of the textarea element and the value of the input element before the setting respectively.

3.1.2 Reapplying DOM changes

To reapply DOM changes of the sequence s1, s2, ... sn, reapply each si with 1 ≤ i ≤ n in the same order s1, s2, ... sn as specified below:

To reapply inserting a node into a parent before a child, run these steps:

  1. If node is not null and its parent is not null, then terminate these steps.
  2. If child is not null and its parent is not parent, then terminate these steps.
  3. Pre-insert child into parent before child.

To reapply removing a node from a parent, let child be the next sibling of node before the removal, and run these steps:

  1. If node is not null and its parent is not parent, then terminate these steps.
  2. If child is not null and its parent is not parent, then terminate these steps.
  3. If child is not null and its previous sibling is not node, then terminate these steps.
  4. Pre-remove node from parent.

To reapply replacing data of a node with an offset, count, and data, and run these steps:

  1. If node's length attribute is less than offset, terminate these steps.
  2. Replace data of node with offset, count, and replacedData.

To reapply changing an attribute whose namespace is namespace and local name is localName to value, let prefix be the namespace prefix after the change, and change the attribute to value and set the namespace prefix to prefix.

To reapply appending an attribute whose namespace is namespace and local name is localName with value as the content attribute value to a node and setting the namespace prefix to prefix, run these steps:

  1. If a content attribute whose namespace is namespace and local name is localName exists on the node, then terminate these steps.
  2. Otherwise, append the attribute whose namespace is namespace and local name is localName with value as the content attribute value to the node, and set namespace prefix to prefix.

To reapply removing an attribute whose namespace is namespace and local name is localName from a node, run these steps.

  1. If a content attribute whose namespace is namespace and local name is localName doesn't exist on the node, then terminate these steps.
  2. Otherwise, remove the attribute whose namespace is namespace and local name is localName.

To reapply setting textarea element's value IDL attribute or input elment's value IDL attribute to value, set element's value IDL attribute to value.

3.2 The DOMTransaction interface

[NoInterfaceObject]
interface DOMTransaction {
    attribute DOMString label;
    attribute Function? executeAutomatic;
    attribute Function? execute;
    attribute Function? undo;
    attribute Function? redo;
};

The DOMTransaction interface is to be implemented by content scripts that implement a DOM 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. When there are multiple transactions in a single entry of the undo transaction history, the user agent that doesn't support displaying multiple labels for each entry must use the label of the first transaction in the sequence of the entry.

executeAutomatic(), execute(), undo(), and redo() are attributes that must be supported, as IDL attributes, by objects implementing the DOMTransaction interface.

Any changes made to the value of executeAutomatic, execute, undo, or redo attributes will take effect immediately. In the following example, execute and undo attributes are modified:

document.undoManager.transact({ executeAutomatic: function () {
    this.executeAutomatic = function () { alert('foo'); }
    alert('bar');
}, undo: function () { alert('baz'); } }); // alerts 'bar'
document.undoManager.item(0)[0].undo = function() { alert('foobar'); }
docuemnt.undoManager.undo(); // alerts 'foobar'

executeAutomatic attribute must return a valid function if the transaction is a automatic DOM transaction, and undefined if it is a manual DOM transaction immediately before the transaction is applied. Any changes made to the value of the executeAutomatic attribute while the transaction is being applied or after the transaction had been applied should not change the type of the DOM transaction.

3.3 Automatic DOM transactions

An automatic DOM transaction is a DOM 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.

When an automatic DOM transaction is applied, the user agent must call the function returned by the executeAutomatic attribute 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.

When an automatic DOM transaction is unapplied, the user agent must revert DOM changes made inside the undo scope of the the UndoManager while applying the transaction, and call the function returned by the undo attribute if the attribute returns a valid function object.

When an automatic DOM transaction is reapplied, the user agent must reapply DOM changes made inside the undo scope of the the UndoManager while applying the transaction. The user agent must then call the function returned by the redo attribute if the attribute returns a valid function object.

The user agent must also restore selection after unapplying or reapplying an automatic DOM transaction in accordance to user agent's platform convention.

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

In an automatic DOM transaction, execute attribute is ignored.

3.4 Manual DOM transactions

A manual DOM transaction is a DOM 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 DOM transaction is applied, the user agnet must call the function returned by the execute if the attribute returns a valid function object.

When a manual DOM transaction is unapplied, the user agnet must call the function returned by the undo attribute if the attribute returns a valid function object.

When a manual DOM transaction is reapplied, the user agnet must call the function returned by the redo attribute if the attribute returns a valid function object.

In a manual DOM transaction, executeAutomatic attribute is ignored.

Manual DOM transactions may be incompatible with automatic DOM transactions, in particular, with user editing actions if manual DOM transaction mutates nodes that are dependent on by automatic DOM transactions.

4 Transaction, Undo, and Redo Events

When a new DOM transaction is applied by transact() method to an undo transaction history of a UndoManager, the user agent must fire a DOM transaction event using the TransactionEvent interface. When a DOM transaction is unapplied or reapplied though undo() method or redo() method, of a UndoManager, the user agent must fire an undo event and a redo event respectively.

4.1 The DOMTransactionEvent interface

[Constructor(DOMString type, optional EventInit eventInitDict)]
interface DOMTransactionEvent : Event {
    readonly attribute Object transaction;
};
DOMTransactionEvent . transaction

Returns the transaction object that triggered this event.

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

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

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

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

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

The target node is always set to a undo scope host or a node that was a undo scope host immediately before t was applied, unapplied, or reapplied.