2
* Storage and control for undo information within a CodeMirror
3
* editor. 'Why on earth is such a complicated mess required for
4
* that?', I hear you ask. The goal, in implementing this, was to make
5
* the complexity of storing and reverting undo information depend
6
* only on the size of the edited or restored content, not on the size
7
* of the whole document. This makes it necessary to use a kind of
8
* 'diff' system, which, when applied to a DOM tree, causes some
9
* complexity and hackery.
11
* In short, the editor 'touches' BR elements as it parses them, and
12
* the History stores these. When nothing is touched in commitDelay
13
* milliseconds, the changes are committed: It goes over all touched
14
* nodes, throws out the ones that did not change since last commit or
15
* are no longer in the document, and assembles the rest into zero or
16
* more 'chains' -- arrays of adjacent lines. Links back to these
17
* chains are added to the BR nodes, while the chain that previously
18
* spanned these nodes is added to the undo history. Undoing a change
19
* means taking such a chain off the undo history, restoring its
20
* content (text is saved per line) and linking it back into the
24
// A history object needs to know about the DOM container holding the
25
// document, the maximum amount of undo levels it should store, the
26
// delay (of no input) after which it commits a set of changes, and,
27
// unfortunately, the 'parent' window -- a window that is not in
28
// designMode, and on which setTimeout works in every browser.
29
function History(container, maxDepth, commitDelay, editor, onChange) {
30
this.container = container;
31
this.maxDepth = maxDepth; this.commitDelay = commitDelay;
32
this.editor = editor; this.parent = editor.parent;
33
this.onChange = onChange;
34
// This line object represents the initial, empty editor.
35
var initial = {text: "", from: null, to: null};
36
// As the borders between lines are represented by BR elements, the
37
// start of the first line and the end of the last one are
38
// represented by null. Since you can not store any properties
39
// (links to line objects) in null, these properties are used in
41
this.first = initial; this.last = initial;
42
// Similarly, a 'historyTouched' property is added to the BR in
43
// front of lines that have already been touched, and 'firstTouched'
44
// is used for the first line.
45
this.firstTouched = false;
46
// History is the set of committed changes, touched is the set of
47
// nodes touched since the last commit.
48
this.history = []; this.redoHistory = []; this.touched = [];
52
// Schedule a commit (if no other touches come in for commitDelay
54
scheduleCommit: function() {
56
this.parent.clearTimeout(this.commitTimeout);
57
this.commitTimeout = this.parent.setTimeout(function(){self.tryCommit();}, this.commitDelay);
60
// Mark a node as touched. Null is a valid argument.
61
touch: function(node) {
62
this.setTouched(node);
63
this.scheduleCommit();
66
// Undo the last change.
68
// Make sure pending changes have been committed.
71
if (this.history.length) {
72
// Take the top diff from the history, apply it, and store its
73
// shadow in the redo history.
74
var item = this.history.pop();
75
this.redoHistory.push(this.updateTo(item, "applyChain"));
76
if (this.onChange) this.onChange();
77
return this.chainNode(item);
81
// Redo the last undone change.
84
if (this.redoHistory.length) {
85
// The inverse of undo, basically.
86
var item = this.redoHistory.pop();
87
this.addUndoLevel(this.updateTo(item, "applyChain"));
88
if (this.onChange) this.onChange();
89
return this.chainNode(item);
95
this.redoHistory = [];
98
// Ask for the size of the un/redo histories.
99
historySize: function() {
100
return {undo: this.history.length, redo: this.redoHistory.length};
103
// Push a changeset into the document.
104
push: function(from, to, lines) {
106
for (var i = 0; i < lines.length; i++) {
107
var end = (i == lines.length - 1) ? to : this.container.ownerDocument.createElement("BR");
108
chain.push({from: from, to: end, text: cleanText(lines[i])});
111
this.pushChains([chain], from == null && to == null);
114
pushChains: function(chains, doNotHighlight) {
115
this.commit(doNotHighlight);
116
this.addUndoLevel(this.updateTo(chains, "applyChain"));
117
this.redoHistory = [];
120
// Retrieve a DOM node from a chain (for scrolling to it after undo/redo).
121
chainNode: function(chains) {
122
for (var i = 0; i < chains.length; i++) {
123
var start = chains[i][0], node = start && (start.from || start.to);
124
if (node) return node;
128
// Clear the undo history, make the current document the start
131
this.history = []; this.redoHistory = [];
134
textAfter: function(br) {
135
return this.after(br).text;
138
nodeAfter: function(br) {
139
return this.after(br).to;
142
nodeBefore: function(br) {
143
return this.before(br).from;
146
// Commit unless there are pending dirty nodes.
147
tryCommit: function() {
148
if (!window.History) return; // Stop when frame has been unloaded
149
if (this.editor.highlightDirty()) this.commit(true);
150
else this.scheduleCommit();
153
// Check whether the touched nodes hold any changes, if so, commit
155
commit: function(doNotHighlight) {
156
this.parent.clearTimeout(this.commitTimeout);
157
// Make sure there are no pending dirty nodes.
158
if (!doNotHighlight) this.editor.highlightDirty(true);
159
// Build set of chains.
160
var chains = this.touchedChains(), self = this;
163
this.addUndoLevel(this.updateTo(chains, "linkChain"));
164
this.redoHistory = [];
165
if (this.onChange) this.onChange();
169
// [ end of public interface ]
171
// Update the document with a given set of chains, return its
172
// shadow. updateFunc should be "applyChain" or "linkChain". In the
173
// second case, the chains are taken to correspond the the current
174
// document, and only the state of the line data is updated. In the
175
// first case, the content of the chains is also pushed iinto the
177
updateTo: function(chains, updateFunc) {
178
var shadows = [], dirty = [];
179
for (var i = 0; i < chains.length; i++) {
180
shadows.push(this.shadowChain(chains[i]));
181
dirty.push(this[updateFunc](chains[i]));
183
if (updateFunc == "applyChain")
184
this.notifyDirty(dirty);
188
// Notify the editor that some nodes have changed.
189
notifyDirty: function(nodes) {
190
forEach(nodes, method(this.editor, "addDirtyNode"))
191
this.editor.scheduleHighlight();
194
// Link a chain into the DOM nodes (or the first/last links for null
196
linkChain: function(chain) {
197
for (var i = 0; i < chain.length; i++) {
199
if (line.from) line.from.historyAfter = line;
200
else this.first = line;
201
if (line.to) line.to.historyBefore = line;
202
else this.last = line;
206
// Get the line object after/before a given node.
207
after: function(node) {
208
return node ? node.historyAfter : this.first;
210
before: function(node) {
211
return node ? node.historyBefore : this.last;
214
// Mark a node as touched if it has not already been marked.
215
setTouched: function(node) {
217
if (!node.historyTouched) {
218
this.touched.push(node);
219
node.historyTouched = true;
223
this.firstTouched = true;
227
// Store a new set of undo info, throw away info if there is more of
229
addUndoLevel: function(diffs) {
230
this.history.push(diffs);
231
if (this.history.length > this.maxDepth)
232
this.history.shift();
235
// Build chains from a set of touched nodes.
236
touchedChains: function() {
239
// The temp system is a crummy hack to speed up determining
240
// whether a (currently touched) node has a line object associated
241
// with it. nullTemp is used to store the object for the first
242
// line, other nodes get it stored in their historyTemp property.
244
function temp(node) {return node ? node.historyTemp : nullTemp;}
245
function setTemp(node, line) {
246
if (node) node.historyTemp = line;
247
else nullTemp = line;
250
function buildLine(node) {
252
for (var cur = node ? node.nextSibling : self.container.firstChild;
253
cur && cur.nodeName != "BR"; cur = cur.nextSibling)
254
if (cur.currentText) text.push(cur.currentText);
255
return {from: node, to: cur, text: cleanText(text.join(""))};
258
// Filter out unchanged lines and nodes that are no longer in the
259
// document. Build up line objects for remaining nodes.
261
if (self.firstTouched) self.touched.push(null);
262
forEach(self.touched, function(node) {
263
if (node && node.parentNode != self.container) return;
265
if (node) node.historyTouched = false;
266
else self.firstTouched = false;
268
var line = buildLine(node), shadow = self.after(node);
269
if (!shadow || shadow.text != line.text || shadow.to != line.to) {
275
// Get the BR element after/before the given node.
276
function nextBR(node, dir) {
277
var link = dir + "Sibling", search = node[link];
278
while (search && search.nodeName != "BR")
279
search = search[link];
283
// Assemble line objects into chains by scanning the DOM tree
285
var chains = []; self.touched = [];
286
forEach(lines, function(line) {
287
// Note that this makes the loop skip line objects that have
288
// been pulled into chains by lines before them.
289
if (!temp(line.from)) return;
291
var chain = [], curNode = line.from, safe = true;
292
// Put any line objects (referred to by temp info) before this
293
// one on the front of the array.
295
var curLine = temp(curNode);
298
else curLine = buildLine(curNode);
300
chain.unshift(curLine);
301
setTemp(curNode, null);
303
safe = self.after(curNode);
304
curNode = nextBR(curNode, "previous");
306
curNode = line.to; safe = self.before(line.from);
307
// Add lines after this one at end of array.
310
var curLine = temp(curNode);
313
else curLine = buildLine(curNode);
316
setTemp(curNode, null);
317
safe = self.before(curNode);
318
curNode = nextBR(curNode, "next");
326
// Find the 'shadow' of a given chain by following the links in the
327
// DOM nodes at its start and end.
328
shadowChain: function(chain) {
329
var shadows = [], next = this.after(chain[0].from), end = chain[chain.length - 1].to;
332
var nextNode = next.to;
333
if (!nextNode || nextNode == end)
336
next = nextNode.historyAfter || this.before(end);
337
// (The this.before(end) is a hack -- FF sometimes removes
338
// properties from BR nodes, in which case the best we can hope
339
// for is to not break.)
344
// Update the DOM tree to contain the lines specified in a given
345
// chain, link this chain into the DOM nodes.
346
applyChain: function(chain) {
347
// Some attempt is made to prevent the cursor from jumping
348
// randomly when an undo or redo happens. It still behaves a bit
349
// strange sometimes.
350
var cursor = select.cursorPos(this.container, false), self = this;
352
// Remove all nodes in the DOM tree between from and to (null for
353
// start/end of container).
354
function removeRange(from, to) {
355
var pos = from ? from.nextSibling : self.container.firstChild;
357
var temp = pos.nextSibling;
363
var start = chain[0].from, end = chain[chain.length - 1].to;
364
// Clear the space where this change has to be made.
365
removeRange(start, end);
367
// Insert the content specified by the chain into the DOM tree.
368
for (var i = 0; i < chain.length; i++) {
370
// The start and end of the space are already correct, but BR
371
// tags inside it have to be put back.
373
self.container.insertBefore(line.from, end);
376
var node = makePartSpan(fixSpaces(line.text), this.container.ownerDocument);
377
self.container.insertBefore(node, end);
378
// See if the cursor was on this line. Put it back, adjusting
379
// for changed line length, if it was.
380
if (cursor && cursor.node == line.from) {
382
var prev = this.after(line.from);
383
if (prev && i == chain.length - 1) {
384
// Only adjust if the cursor is after the unchanged part of
386
for (var match = 0; match < cursor.offset &&
387
line.text.charAt(match) == prev.text.charAt(match); match++);
388
if (cursor.offset > match)
389
cursordiff = line.text.length - prev.text.length;
391
select.setCursorPos(this.container, {node: line.from, offset: Math.max(0, cursor.offset + cursordiff)});
393
// Cursor was in removed line, this is last new line.
394
else if (cursor && (i == chain.length - 1) && cursor.node && cursor.node.parentNode != this.container) {
395
select.setCursorPos(this.container, {node: line.from, offset: line.text.length});
399
// Anchor the chain in the DOM tree.
400
this.linkChain(chain);