--- /dev/null
+/**
+ * Storage and control for undo information within a CodeMirror
+ * editor. 'Why on earth is such a complicated mess required for
+ * that?', I hear you ask. The goal, in implementing this, was to make
+ * the complexity of storing and reverting undo information depend
+ * only on the size of the edited or restored content, not on the size
+ * of the whole document. This makes it necessary to use a kind of
+ * 'diff' system, which, when applied to a DOM tree, causes some
+ * complexity and hackery.
+ *
+ * In short, the editor 'touches' BR elements as it parses them, and
+ * the History stores these. When nothing is touched in commitDelay
+ * milliseconds, the changes are committed: It goes over all touched
+ * nodes, throws out the ones that did not change since last commit or
+ * are no longer in the document, and assembles the rest into zero or
+ * more 'chains' -- arrays of adjacent lines. Links back to these
+ * chains are added to the BR nodes, while the chain that previously
+ * spanned these nodes is added to the undo history. Undoing a change
+ * means taking such a chain off the undo history, restoring its
+ * content (text is saved per line) and linking it back into the
+ * document.
+ */
+
+// A history object needs to know about the DOM container holding the
+// document, the maximum amount of undo levels it should store, the
+// delay (of no input) after which it commits a set of changes, and,
+// unfortunately, the 'parent' window -- a window that is not in
+// designMode, and on which setTimeout works in every browser.
+function History(container, maxDepth, commitDelay, editor, onChange) {
+ this.container = container;
+ this.maxDepth = maxDepth; this.commitDelay = commitDelay;
+ this.editor = editor; this.parent = editor.parent;
+ this.onChange = onChange;
+ // This line object represents the initial, empty editor.
+ var initial = {text: "", from: null, to: null};
+ // As the borders between lines are represented by BR elements, the
+ // start of the first line and the end of the last one are
+ // represented by null. Since you can not store any properties
+ // (links to line objects) in null, these properties are used in
+ // those cases.
+ this.first = initial; this.last = initial;
+ // Similarly, a 'historyTouched' property is added to the BR in
+ // front of lines that have already been touched, and 'firstTouched'
+ // is used for the first line.
+ this.firstTouched = false;
+ // History is the set of committed changes, touched is the set of
+ // nodes touched since the last commit.
+ this.history = []; this.redoHistory = []; this.touched = [];
+}
+
+History.prototype = {
+ // Schedule a commit (if no other touches come in for commitDelay
+ // milliseconds).
+ scheduleCommit: function() {
+ var self = this;
+ this.parent.clearTimeout(this.commitTimeout);
+ this.commitTimeout = this.parent.setTimeout(function(){self.tryCommit();}, this.commitDelay);
+ },
+
+ // Mark a node as touched. Null is a valid argument.
+ touch: function(node) {
+ this.setTouched(node);
+ this.scheduleCommit();
+ },
+
+ // Undo the last change.
+ undo: function() {
+ // Make sure pending changes have been committed.
+ this.commit();
+
+ if (this.history.length) {
+ // Take the top diff from the history, apply it, and store its
+ // shadow in the redo history.
+ var item = this.history.pop();
+ this.redoHistory.push(this.updateTo(item, "applyChain"));
+ if (this.onChange) this.onChange();
+ return this.chainNode(item);
+ }
+ },
+
+ // Redo the last undone change.
+ redo: function() {
+ this.commit();
+ if (this.redoHistory.length) {
+ // The inverse of undo, basically.
+ var item = this.redoHistory.pop();
+ this.addUndoLevel(this.updateTo(item, "applyChain"));
+ if (this.onChange) this.onChange();
+ return this.chainNode(item);
+ }
+ },
+
+ clear: function() {
+ this.history = [];
+ this.redoHistory = [];
+ },
+
+ // Ask for the size of the un/redo histories.
+ historySize: function() {
+ return {undo: this.history.length, redo: this.redoHistory.length};
+ },
+
+ // Push a changeset into the document.
+ push: function(from, to, lines) {
+ var chain = [];
+ for (var i = 0; i < lines.length; i++) {
+ var end = (i == lines.length - 1) ? to : this.container.ownerDocument.createElement("BR");
+ chain.push({from: from, to: end, text: cleanText(lines[i])});
+ from = end;
+ }
+ this.pushChains([chain], from == null && to == null);
+ },
+
+ pushChains: function(chains, doNotHighlight) {
+ this.commit(doNotHighlight);
+ this.addUndoLevel(this.updateTo(chains, "applyChain"));
+ this.redoHistory = [];
+ },
+
+ // Retrieve a DOM node from a chain (for scrolling to it after undo/redo).
+ chainNode: function(chains) {
+ for (var i = 0; i < chains.length; i++) {
+ var start = chains[i][0], node = start && (start.from || start.to);
+ if (node) return node;
+ }
+ },
+
+ // Clear the undo history, make the current document the start
+ // position.
+ reset: function() {
+ this.history = []; this.redoHistory = [];
+ },
+
+ textAfter: function(br) {
+ return this.after(br).text;
+ },
+
+ nodeAfter: function(br) {
+ return this.after(br).to;
+ },
+
+ nodeBefore: function(br) {
+ return this.before(br).from;
+ },
+
+ // Commit unless there are pending dirty nodes.
+ tryCommit: function() {
+ if (!window.History) return; // Stop when frame has been unloaded
+ if (this.editor.highlightDirty()) this.commit(true);
+ else this.scheduleCommit();
+ },
+
+ // Check whether the touched nodes hold any changes, if so, commit
+ // them.
+ commit: function(doNotHighlight) {
+ this.parent.clearTimeout(this.commitTimeout);
+ // Make sure there are no pending dirty nodes.
+ if (!doNotHighlight) this.editor.highlightDirty(true);
+ // Build set of chains.
+ var chains = this.touchedChains(), self = this;
+
+ if (chains.length) {
+ this.addUndoLevel(this.updateTo(chains, "linkChain"));
+ this.redoHistory = [];
+ if (this.onChange) this.onChange();
+ }
+ },
+
+ // [ end of public interface ]
+
+ // Update the document with a given set of chains, return its
+ // shadow. updateFunc should be "applyChain" or "linkChain". In the
+ // second case, the chains are taken to correspond the the current
+ // document, and only the state of the line data is updated. In the
+ // first case, the content of the chains is also pushed iinto the
+ // document.
+ updateTo: function(chains, updateFunc) {
+ var shadows = [], dirty = [];
+ for (var i = 0; i < chains.length; i++) {
+ shadows.push(this.shadowChain(chains[i]));
+ dirty.push(this[updateFunc](chains[i]));
+ }
+ if (updateFunc == "applyChain")
+ this.notifyDirty(dirty);
+ return shadows;
+ },
+
+ // Notify the editor that some nodes have changed.
+ notifyDirty: function(nodes) {
+ forEach(nodes, method(this.editor, "addDirtyNode"))
+ this.editor.scheduleHighlight();
+ },
+
+ // Link a chain into the DOM nodes (or the first/last links for null
+ // nodes).
+ linkChain: function(chain) {
+ for (var i = 0; i < chain.length; i++) {
+ var line = chain[i];
+ if (line.from) line.from.historyAfter = line;
+ else this.first = line;
+ if (line.to) line.to.historyBefore = line;
+ else this.last = line;
+ }
+ },
+
+ // Get the line object after/before a given node.
+ after: function(node) {
+ return node ? node.historyAfter : this.first;
+ },
+ before: function(node) {
+ return node ? node.historyBefore : this.last;
+ },
+
+ // Mark a node as touched if it has not already been marked.
+ setTouched: function(node) {
+ if (node) {
+ if (!node.historyTouched) {
+ this.touched.push(node);
+ node.historyTouched = true;
+ }
+ }
+ else {
+ this.firstTouched = true;
+ }
+ },
+
+ // Store a new set of undo info, throw away info if there is more of
+ // it than allowed.
+ addUndoLevel: function(diffs) {
+ this.history.push(diffs);
+ if (this.history.length > this.maxDepth)
+ this.history.shift();
+ },
+
+ // Build chains from a set of touched nodes.
+ touchedChains: function() {
+ var self = this;
+
+ // The temp system is a crummy hack to speed up determining
+ // whether a (currently touched) node has a line object associated
+ // with it. nullTemp is used to store the object for the first
+ // line, other nodes get it stored in their historyTemp property.
+ var nullTemp = null;
+ function temp(node) {return node ? node.historyTemp : nullTemp;}
+ function setTemp(node, line) {
+ if (node) node.historyTemp = line;
+ else nullTemp = line;
+ }
+
+ function buildLine(node) {
+ var text = [];
+ for (var cur = node ? node.nextSibling : self.container.firstChild;
+ cur && cur.nodeName != "BR"; cur = cur.nextSibling)
+ if (cur.currentText) text.push(cur.currentText);
+ return {from: node, to: cur, text: cleanText(text.join(""))};
+ }
+
+ // Filter out unchanged lines and nodes that are no longer in the
+ // document. Build up line objects for remaining nodes.
+ var lines = [];
+ if (self.firstTouched) self.touched.push(null);
+ forEach(self.touched, function(node) {
+ if (node && node.parentNode != self.container) return;
+
+ if (node) node.historyTouched = false;
+ else self.firstTouched = false;
+
+ var line = buildLine(node), shadow = self.after(node);
+ if (!shadow || shadow.text != line.text || shadow.to != line.to) {
+ lines.push(line);
+ setTemp(node, line);
+ }
+ });
+
+ // Get the BR element after/before the given node.
+ function nextBR(node, dir) {
+ var link = dir + "Sibling", search = node[link];
+ while (search && search.nodeName != "BR")
+ search = search[link];
+ return search;
+ }
+
+ // Assemble line objects into chains by scanning the DOM tree
+ // around them.
+ var chains = []; self.touched = [];
+ forEach(lines, function(line) {
+ // Note that this makes the loop skip line objects that have
+ // been pulled into chains by lines before them.
+ if (!temp(line.from)) return;
+
+ var chain = [], curNode = line.from, safe = true;
+ // Put any line objects (referred to by temp info) before this
+ // one on the front of the array.
+ while (true) {
+ var curLine = temp(curNode);
+ if (!curLine) {
+ if (safe) break;
+ else curLine = buildLine(curNode);
+ }
+ chain.unshift(curLine);
+ setTemp(curNode, null);
+ if (!curNode) break;
+ safe = self.after(curNode);
+ curNode = nextBR(curNode, "previous");
+ }
+ curNode = line.to; safe = self.before(line.from);
+ // Add lines after this one at end of array.
+ while (true) {
+ if (!curNode) break;
+ var curLine = temp(curNode);
+ if (!curLine) {
+ if (safe) break;
+ else curLine = buildLine(curNode);
+ }
+ chain.push(curLine);
+ setTemp(curNode, null);
+ safe = self.before(curNode);
+ curNode = nextBR(curNode, "next");
+ }
+ chains.push(chain);
+ });
+
+ return chains;
+ },
+
+ // Find the 'shadow' of a given chain by following the links in the
+ // DOM nodes at its start and end.
+ shadowChain: function(chain) {
+ var shadows = [], next = this.after(chain[0].from), end = chain[chain.length - 1].to;
+ while (true) {
+ shadows.push(next);
+ var nextNode = next.to;
+ if (!nextNode || nextNode == end)
+ break;
+ else
+ next = nextNode.historyAfter || this.before(end);
+ // (The this.before(end) is a hack -- FF sometimes removes
+ // properties from BR nodes, in which case the best we can hope
+ // for is to not break.)
+ }
+ return shadows;
+ },
+
+ // Update the DOM tree to contain the lines specified in a given
+ // chain, link this chain into the DOM nodes.
+ applyChain: function(chain) {
+ // Some attempt is made to prevent the cursor from jumping
+ // randomly when an undo or redo happens. It still behaves a bit
+ // strange sometimes.
+ var cursor = select.cursorPos(this.container, false), self = this;
+
+ // Remove all nodes in the DOM tree between from and to (null for
+ // start/end of container).
+ function removeRange(from, to) {
+ var pos = from ? from.nextSibling : self.container.firstChild;
+ while (pos != to) {
+ var temp = pos.nextSibling;
+ removeElement(pos);
+ pos = temp;
+ }
+ }
+
+ var start = chain[0].from, end = chain[chain.length - 1].to;
+ // Clear the space where this change has to be made.
+ removeRange(start, end);
+
+ // Insert the content specified by the chain into the DOM tree.
+ for (var i = 0; i < chain.length; i++) {
+ var line = chain[i];
+ // The start and end of the space are already correct, but BR
+ // tags inside it have to be put back.
+ if (i > 0)
+ self.container.insertBefore(line.from, end);
+
+ // Add the text.
+ var node = makePartSpan(fixSpaces(line.text), this.container.ownerDocument);
+ self.container.insertBefore(node, end);
+ // See if the cursor was on this line. Put it back, adjusting
+ // for changed line length, if it was.
+ if (cursor && cursor.node == line.from) {
+ var cursordiff = 0;
+ var prev = this.after(line.from);
+ if (prev && i == chain.length - 1) {
+ // Only adjust if the cursor is after the unchanged part of
+ // the line.
+ for (var match = 0; match < cursor.offset &&
+ line.text.charAt(match) == prev.text.charAt(match); match++);
+ if (cursor.offset > match)
+ cursordiff = line.text.length - prev.text.length;
+ }
+ select.setCursorPos(this.container, {node: line.from, offset: Math.max(0, cursor.offset + cursordiff)});
+ }
+ // Cursor was in removed line, this is last new line.
+ else if (cursor && (i == chain.length - 1) && cursor.node && cursor.node.parentNode != this.container) {
+ select.setCursorPos(this.container, {node: line.from, offset: line.text.length});
+ }
+ }
+
+ // Anchor the chain in the DOM tree.
+ this.linkChain(chain);
+ return start;
+ }
+};