4ea23859be5c4fa2d3e14d4085323ff4999a1655
[redakcja.git] / src / redakcja / static / js / lib / codemirror-0.8 / undo.js
1 /**
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.
10  *
11  * In short, the editor 'touches' BR elements as it parses them, and
12  * the UndoHistory 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
21  * document.
22  */
23
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 UndoHistory(container, maxDepth, commitDelay, editor) {
30   this.container = container;
31   this.maxDepth = maxDepth; this.commitDelay = commitDelay;
32   this.editor = editor; this.parent = editor.parent;
33   // This line object represents the initial, empty editor.
34   var initial = {text: "", from: null, to: null};
35   // As the borders between lines are represented by BR elements, the
36   // start of the first line and the end of the last one are
37   // represented by null. Since you can not store any properties
38   // (links to line objects) in null, these properties are used in
39   // those cases.
40   this.first = initial; this.last = initial;
41   // Similarly, a 'historyTouched' property is added to the BR in
42   // front of lines that have already been touched, and 'firstTouched'
43   // is used for the first line.
44   this.firstTouched = false;
45   // History is the set of committed changes, touched is the set of
46   // nodes touched since the last commit.
47   this.history = []; this.redoHistory = []; this.touched = [];
48 }
49
50 UndoHistory.prototype = {
51   // Schedule a commit (if no other touches come in for commitDelay
52   // milliseconds).
53   scheduleCommit: function() {
54     var self = this;
55     this.parent.clearTimeout(this.commitTimeout);
56     this.commitTimeout = this.parent.setTimeout(function(){self.tryCommit();}, this.commitDelay);
57   },
58
59   // Mark a node as touched. Null is a valid argument.
60   touch: function(node) {
61     this.setTouched(node);
62     this.scheduleCommit();
63   },
64
65   // Undo the last change.
66   undo: function() {
67     // Make sure pending changes have been committed.
68     this.commit();
69
70     if (this.history.length) {
71       // Take the top diff from the history, apply it, and store its
72       // shadow in the redo history.
73       var item = this.history.pop();
74       this.redoHistory.push(this.updateTo(item, "applyChain"));
75       this.notifyEnvironment();
76       return this.chainNode(item);
77     }
78   },
79
80   // Redo the last undone change.
81   redo: function() {
82     this.commit();
83     if (this.redoHistory.length) {
84       // The inverse of undo, basically.
85       var item = this.redoHistory.pop();
86       this.addUndoLevel(this.updateTo(item, "applyChain"));
87       this.notifyEnvironment();
88       return this.chainNode(item);
89     }
90   },
91
92   clear: function() {
93     this.history = [];
94     this.redoHistory = [];
95   },
96
97   // Ask for the size of the un/redo histories.
98   historySize: function() {
99     return {undo: this.history.length, redo: this.redoHistory.length};
100   },
101
102   // Push a changeset into the document.
103   push: function(from, to, lines) {
104     var chain = [];
105     for (var i = 0; i < lines.length; i++) {
106       var end = (i == lines.length - 1) ? to : this.container.ownerDocument.createElement("BR");
107       chain.push({from: from, to: end, text: cleanText(lines[i])});
108       from = end;
109     }
110     this.pushChains([chain], from == null && to == null);
111     this.notifyEnvironment();
112   },
113
114   pushChains: function(chains, doNotHighlight) {
115     this.commit(doNotHighlight);
116     this.addUndoLevel(this.updateTo(chains, "applyChain"));
117     this.redoHistory = [];
118   },
119
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;
125     }
126   },
127
128   // Clear the undo history, make the current document the start
129   // position.
130   reset: function() {
131     this.history = []; this.redoHistory = [];
132   },
133
134   textAfter: function(br) {
135     return this.after(br).text;
136   },
137
138   nodeAfter: function(br) {
139     return this.after(br).to;
140   },
141
142   nodeBefore: function(br) {
143     return this.before(br).from;
144   },
145
146   // Commit unless there are pending dirty nodes.
147   tryCommit: function() {
148     if (!window.UndoHistory) return; // Stop when frame has been unloaded
149     if (this.editor.highlightDirty()) this.commit(true);
150     else this.scheduleCommit();
151   },
152
153   // Check whether the touched nodes hold any changes, if so, commit
154   // them.
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;
161
162     if (chains.length) {
163       this.addUndoLevel(this.updateTo(chains, "linkChain"));
164       this.redoHistory = [];
165       this.notifyEnvironment();
166     }
167   },
168
169   // [ end of public interface ]
170
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
176   // document.
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]));
182     }
183     if (updateFunc == "applyChain")
184       this.notifyDirty(dirty);
185     return shadows;
186   },
187
188   // Notify the editor that some nodes have changed.
189   notifyDirty: function(nodes) {
190     forEach(nodes, method(this.editor, "addDirtyNode"))
191     this.editor.scheduleHighlight();
192   },
193
194   notifyEnvironment: function() {
195     if (this.onChange) this.onChange();
196     // Used by the line-wrapping line-numbering code.
197     if (window.frameElement && window.frameElement.CodeMirror.updateNumbers)
198       window.frameElement.CodeMirror.updateNumbers();
199   },
200
201   // Link a chain into the DOM nodes (or the first/last links for null
202   // nodes).
203   linkChain: function(chain) {
204     for (var i = 0; i < chain.length; i++) {
205       var line = chain[i];
206       if (line.from) line.from.historyAfter = line;
207       else this.first = line;
208       if (line.to) line.to.historyBefore = line;
209       else this.last = line;
210     }
211   },
212
213   // Get the line object after/before a given node.
214   after: function(node) {
215     return node ? node.historyAfter : this.first;
216   },
217   before: function(node) {
218     return node ? node.historyBefore : this.last;
219   },
220
221   // Mark a node as touched if it has not already been marked.
222   setTouched: function(node) {
223     if (node) {
224       if (!node.historyTouched) {
225         this.touched.push(node);
226         node.historyTouched = true;
227       }
228     }
229     else {
230       this.firstTouched = true;
231     }
232   },
233
234   // Store a new set of undo info, throw away info if there is more of
235   // it than allowed.
236   addUndoLevel: function(diffs) {
237     this.history.push(diffs);
238     if (this.history.length > this.maxDepth)
239       this.history.shift();
240   },
241
242   // Build chains from a set of touched nodes.
243   touchedChains: function() {
244     var self = this;
245
246     // The temp system is a crummy hack to speed up determining
247     // whether a (currently touched) node has a line object associated
248     // with it. nullTemp is used to store the object for the first
249     // line, other nodes get it stored in their historyTemp property.
250     var nullTemp = null;
251     function temp(node) {return node ? node.historyTemp : nullTemp;}
252     function setTemp(node, line) {
253       if (node) node.historyTemp = line;
254       else nullTemp = line;
255     }
256
257     function buildLine(node) {
258       var text = [];
259       for (var cur = node ? node.nextSibling : self.container.firstChild;
260            cur && !isBR(cur); cur = cur.nextSibling)
261         if (cur.currentText) text.push(cur.currentText);
262       return {from: node, to: cur, text: cleanText(text.join(""))};
263     }
264
265     // Filter out unchanged lines and nodes that are no longer in the
266     // document. Build up line objects for remaining nodes.
267     var lines = [];
268     if (self.firstTouched) self.touched.push(null);
269     forEach(self.touched, function(node) {
270       if (node && node.parentNode != self.container) return;
271
272       if (node) node.historyTouched = false;
273       else self.firstTouched = false;
274
275       var line = buildLine(node), shadow = self.after(node);
276       if (!shadow || shadow.text != line.text || shadow.to != line.to) {
277         lines.push(line);
278         setTemp(node, line);
279       }
280     });
281
282     // Get the BR element after/before the given node.
283     function nextBR(node, dir) {
284       var link = dir + "Sibling", search = node[link];
285       while (search && !isBR(search))
286         search = search[link];
287       return search;
288     }
289
290     // Assemble line objects into chains by scanning the DOM tree
291     // around them.
292     var chains = []; self.touched = [];
293     forEach(lines, function(line) {
294       // Note that this makes the loop skip line objects that have
295       // been pulled into chains by lines before them.
296       if (!temp(line.from)) return;
297
298       var chain = [], curNode = line.from, safe = true;
299       // Put any line objects (referred to by temp info) before this
300       // one on the front of the array.
301       while (true) {
302         var curLine = temp(curNode);
303         if (!curLine) {
304           if (safe) break;
305           else curLine = buildLine(curNode);
306         }
307         chain.unshift(curLine);
308         setTemp(curNode, null);
309         if (!curNode) break;
310         safe = self.after(curNode);
311         curNode = nextBR(curNode, "previous");
312       }
313       curNode = line.to; safe = self.before(line.from);
314       // Add lines after this one at end of array.
315       while (true) {
316         if (!curNode) break;
317         var curLine = temp(curNode);
318         if (!curLine) {
319           if (safe) break;
320           else curLine = buildLine(curNode);
321         }
322         chain.push(curLine);
323         setTemp(curNode, null);
324         safe = self.before(curNode);
325         curNode = nextBR(curNode, "next");
326       }
327       chains.push(chain);
328     });
329
330     return chains;
331   },
332
333   // Find the 'shadow' of a given chain by following the links in the
334   // DOM nodes at its start and end.
335   shadowChain: function(chain) {
336     var shadows = [], next = this.after(chain[0].from), end = chain[chain.length - 1].to;
337     while (true) {
338       shadows.push(next);
339       var nextNode = next.to;
340       if (!nextNode || nextNode == end)
341         break;
342       else
343         next = nextNode.historyAfter || this.before(end);
344       // (The this.before(end) is a hack -- FF sometimes removes
345       // properties from BR nodes, in which case the best we can hope
346       // for is to not break.)
347     }
348     return shadows;
349   },
350
351   // Update the DOM tree to contain the lines specified in a given
352   // chain, link this chain into the DOM nodes.
353   applyChain: function(chain) {
354     // Some attempt is made to prevent the cursor from jumping
355     // randomly when an undo or redo happens. It still behaves a bit
356     // strange sometimes.
357     var cursor = select.cursorPos(this.container, false), self = this;
358
359     // Remove all nodes in the DOM tree between from and to (null for
360     // start/end of container).
361     function removeRange(from, to) {
362       var pos = from ? from.nextSibling : self.container.firstChild;
363       while (pos != to) {
364         var temp = pos.nextSibling;
365         removeElement(pos);
366         pos = temp;
367       }
368     }
369
370     var start = chain[0].from, end = chain[chain.length - 1].to;
371     // Clear the space where this change has to be made.
372     removeRange(start, end);
373
374     // Insert the content specified by the chain into the DOM tree.
375     for (var i = 0; i < chain.length; i++) {
376       var line = chain[i];
377       // The start and end of the space are already correct, but BR
378       // tags inside it have to be put back.
379       if (i > 0)
380         self.container.insertBefore(line.from, end);
381
382       // Add the text.
383       var node = makePartSpan(fixSpaces(line.text), this.container.ownerDocument);
384       self.container.insertBefore(node, end);
385       // See if the cursor was on this line. Put it back, adjusting
386       // for changed line length, if it was.
387       if (cursor && cursor.node == line.from) {
388         var cursordiff = 0;
389         var prev = this.after(line.from);
390         if (prev && i == chain.length - 1) {
391           // Only adjust if the cursor is after the unchanged part of
392           // the line.
393           for (var match = 0; match < cursor.offset &&
394                line.text.charAt(match) == prev.text.charAt(match); match++);
395           if (cursor.offset > match)
396             cursordiff = line.text.length - prev.text.length;
397         }
398         select.setCursorPos(this.container, {node: line.from, offset: Math.max(0, cursor.offset + cursordiff)});
399       }
400       // Cursor was in removed line, this is last new line.
401       else if (cursor && (i == chain.length - 1) && cursor.node && cursor.node.parentNode != this.container) {
402         select.setCursorPos(this.container, {node: line.from, offset: line.text.length});
403       }
404     }
405
406     // Anchor the chain in the DOM tree.
407     this.linkChain(chain);
408     return start;
409   }
410 };