UndoManager and DOM Transaction

Editor's proposal — 29 November 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-2010-10-27.html
http://rniwa.com/editing/undomanager-2010-10-20.html
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 forward in the undo transaction history
    5. 2.5 Redo: moving backward in the undo transaction history
  3. 3 Transaction and DOM changes
    1. 3.1 Mutations of DOM
      1. 3.1.1 Reverting 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 DOM transaction and DOM 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 Object 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 the DOM transaction or all transactions in the DOM transaction group immediately after the current position and increments position by 1 if position < length.

undoManager . redo()

Reapplies the DOM transaction or all transactions in the DOM 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 DOM transaction, then throw INVALID_ACCESS_ERR and stop.
  2. Clear all DOM transactions or DOM transaction groups between before the current undo position.
  3. Apply the transaction.
  4. If merge is not set to true or there are no entries in the undo transaction history, add transaction to the top of undo transaction history and go to step 7.
  5. Otherwise, if the first entry in the undo transaction history was a DOM transaction group, then add transaction to the top of the array that forms the DOM transaction group and go to step 7.
  6. Otherwise, create a new array, insert the first entry in the undo transaction history andtransaction in the respective order to form a new DOM transaction group, and insert it to the top of undo transaction history.
  7. 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 position >= length, stop.
  3. Otherwise, unapply the DOM transaction or the DOM transaction group 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 the DOM transaction or the DOM transaction group 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 the nth entry, a DOM transaction or an array reprensenting a DOM transaction group, 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 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.

A DOM transaction group is an array of consecutive DOM 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 DOM transaction group is formed when a DOM transaction is applied via UndoManager's transact() method with merge set to true and the UndoManager already has a DOM transaction group or a DOM transaction.

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

When DOM transactions in a DOM transaction group are unapplied, the user agent must unapply each DOM transaction in the array that forms the DOM transaction group in the ascending order from the first entry to the last entry. When transactions in a DOM transaction group are reapplied, the user agent must reapply each DOM 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 DOM transactions that form one DOM transaction group. A br element and string "hi" are then inserted by other two automatic DOM transactions to form another DOM 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 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 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 of a node, 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, remove the attribute.

To revert removing an attribute whose namespace is namespace and local name is localName from a node, let oldValue be the content attribute value before the removal, oldPrefix be the namespace prefix 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, let oldvalue be the raw value of the element before the setting, and run these steps:

  1. Set element's value IDL attribute to oldValue.

To revert setting input elment's value IDL attribute, let oldvalue be the value of the element before the setting, and run these steps:

  1. Set element's value IDL attribute to oldValue.

3.2 The DOMTransaction interface

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

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.

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

Any changes made to the value of apply, unapply, or reapply attributes will take effect immediately. In the following example, apply and unapply attributes are modified:

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

isAutomatic attribute must return true if the transaction is a automatic DOM transaction, and false if it is a manual DOM transaction immediately before the transaction is applied. Any changes made to the value of the isAutomatic 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 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.

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 transation, and call the function returned by the unapply attribute if the attribute returns a valid function object.

When an automatic DOM transaction is reapplied, the user agent must revert DOM changes made inside the undo scope of the the UndoManager while unapplying the transation. The user agent must then call the function returned by the reapply attribute if the attribute returns a valid function object. If the reapply attribute returned null or undefined, then the function returned by apply attribute must be called with isReapply set to true instead if the attribute returns a valid function object.

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.

TODO: Need to restore selection as well.

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 function returned by the apply attribute is invoked with isReapply set to false if the attribute returns a valid function object.

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

When a manual DOM 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 DOM transactions may be incompatible with automatic DOM transactions, in particular, with user editing actions if manual DOM transaction mutates descendant nodes of the highest node affecting automatic DOM transactions and do not restore the DOM state of the highest node affecting automatic DOM transactions prior to unapplying or reapplying 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.