re taken. They're taken in order because sequential memory accesses are fastest. var remaining = child.lines.length % 25 + 25 for (var pos = remaining; pos < child.lines.length;) { var leaf = new LeafChunk(child.lines.slice(pos, pos += 25)); child.height -= leaf.height; this.children.splice(++i, 0, leaf); leaf.parent = this; } child.lines = child.lines.slice(0, remaining); this.maybeSpill(); } break; } at -= sz; } }, // When a node has grown, check whether it should be split. maybeSpill: function() { if (this.children.length <= 10) return; var me = this; do { var spilled = me.children.splice(me.children.length - 5, 5); var sibling = new BranchChunk(spilled); if (!me.parent) { // Become the parent node var copy = new BranchChunk(me.children); copy.parent = me; me.children = [copy, sibling]; me = copy; } else { me.size -= sibling.size; me.height -= sibling.height; var myIndex = indexOf(me.parent.children, me); me.parent.children.splice(myIndex + 1, 0, sibling); } sibling.parent = me.parent; } while (me.children.length > 10); me.parent.maybeSpill(); }, iterN: function(at, n, op) { for (var i = 0; i < this.children.length; ++i) { var child = this.children[i], sz = child.chunkSize(); if (at < sz) { var used = Math.min(n, sz - at); if (child.iterN(at, used, op)) return true; if ((n -= used) == 0) break; at = 0; } else at -= sz; } } }; var nextDocId = 0; var Doc = CodeMirror.Doc = function(text, mode, firstLine, lineSep) { if (!(this instanceof Doc)) return new Doc(text, mode, firstLine, lineSep); if (firstLine == null) firstLine = 0; BranchChunk.call(this, [new LeafChunk([new Line("", null)])]); this.first = firstLine; this.scrollTop = this.scrollLeft = 0; this.cantEdit = false; this.cleanGeneration = 1; this.frontier = firstLine; var start = Pos(firstLine, 0); this.sel = simpleSelection(start); this.history = new History(null); this.id = ++nextDocId; this.modeOption = mode; this.lineSep = lineSep; this.extend = false; if (typeof text == "string") text = this.splitLines(text); updateDoc(this, {from: start, to: start, text: text}); setSelection(this, simpleSelection(start), sel_dontScroll); }; Doc.prototype = createObj(BranchChunk.prototype, { constructor: Doc, // Iterate over the document. Supports two forms -- with only one // argument, it calls that for each line in the document. With // three, it iterates over the range given by the first two (with // the second being non-inclusive). iter: function(from, to, op) { if (op) this.iterN(from - this.first, to - from, op); else this.iterN(this.first, this.first + this.size, from); }, // Non-public interface for adding and removing lines. insert: function(at, lines) { var height = 0; for (var i = 0; i < lines.length; ++i) height += lines[i].height; this.insertInner(at - this.first, lines, height); }, remove: function(at, n) { this.removeInner(at - this.first, n); }, // From here, the methods are part of the public interface. Most // are also available from CodeMirror (editor) instances. getValue: function(lineSep) { var lines = getLines(this, this.first, this.first + this.size); if (lineSep === false) return lines; return lines.join(lineSep || this.lineSeparator()); }, setValue: docMethodOp(function(code) { var top = Pos(this.first, 0), last = this.first + this.size - 1; makeChange(this, {from: top, to: Pos(last, getLine(this, last).text.length), text: this.splitLines(code), origin: "setValue", full: true}, true); setSelection(this, simpleSelection(top)); }), replaceRange: function(code, from, to, origin) { from = clipPos(this, from); to = to ? clipPos(this, to) : from; replaceRange(this, code, from, to, origin); }, getRange: function(from, to, lineSep) { var lines = getBetween(this, clipPos(this, from), clipPos(this, to)); if (lineSep === false) return lines; return lines.join(lineSep || this.lineSeparator()); }, getLine: function(line) {var l = this.getLineHandle(line); return l && l.text;}, getLineHandle: function(line) {if (isLine(this, line)) return getLine(this, line);}, getLineNumber: function(line) {return lineNo(line);}, getLineHandleVisualStart: function(line) { if (typeof line == "number") line = getLine(this, line); return visualLine(line); }, lineCount: function() {return this.size;}, firstLine: function() {return this.first;}, lastLine: function() {return this.first + this.size - 1;}, clipPos: function(pos) {return clipPos(this, pos);}, getCursor: function(start) { var range = this.sel.primary(), pos; if (start == null || start == "head") pos = range.head; else if (start == "anchor") pos = range.anchor; else if (start == "end" || start == "to" || start === false) pos = range.to(); else pos = range.from(); return pos; }, listSelections: function() { return this.sel.ranges; }, somethingSelected: function() {return this.sel.somethingSelected();}, setCursor: docMethodOp(function(line, ch, options) { setSimpleSelection(this, clipPos(this, typeof line == "number" ? Pos(line, ch || 0) : line), null, options); }), setSelection: docMethodOp(function(anchor, head, options) { setSimpleSelection(this, clipPos(this, anchor), clipPos(this, head || anchor), options); }), extendSelection: docMethodOp(function(head, other, options) { extendSelection(this, clipPos(this, head), other && clipPos(this, other), options); }), extendSelections: docMethodOp(function(heads, options) { extendSelections(this, clipPosArray(this, heads), options); }), extendSelectionsBy: docMethodOp(function(f, options) { var heads = map(this.sel.ranges, f); extendSelections(this, clipPosArray(this, heads), options); }), setSelections: docMethodOp(function(ranges, primary, options) { if (!ranges.length) return; for (var i = 0, out = []; i < ranges.length; i++) out[i] = new Range(clipPos(this, ranges[i].anchor), clipPos(this, ranges[i].head)); if (primary == null) primary = Math.min(ranges.length - 1, this.sel.primIndex); setSelection(this, normalizeSelection(out, primary), options); }), addSelection: docMethodOp(function(anchor, head, options) { var ranges = this.sel.ranges.slice(0); ranges.push(new Range(clipPos(this, anchor), clipPos(this, head || anchor))); setSelection(this, normalizeSelection(ranges, ranges.length - 1), options); }), getSelection: function(lineSep) { var ranges = this.sel.ranges, lines; for (var i = 0; i < ranges.length; i++) { var sel = getBetween(this, ranges[i].from(), ranges[i].to()); lines = lines ? lines.concat(sel) : sel; } if (lineSep === false) return lines; else return lines.join(lineSep || this.lineSeparator()); }, getSelections: function(lineSep) { var parts = [], ranges = this.sel.ranges; for (var i = 0; i < ranges.length; i++) { var sel = getBetween(this, ranges[i].from(), ranges[i].to()); if (lineSep !== false) sel = sel.join(lineSep || this.lineSeparator()); parts[i] = sel; } return parts; }, replaceSelection: function(code, collapse, origin) { var dup = []; for (var i = 0; i < this.sel.ranges.length; i++) dup[i] = code; this.replaceSelections(dup, collapse, origin || "+input"); }, replaceSelections: docMethodOp(function(code, collapse, origin) { var changes = [], sel = this.sel; for (var i = 0; i < sel.ranges.length; i++) { var range = sel.ranges[i]; changes[i] = {from: range.from(), to: range.to(), text: this.splitLines(code[i]), origin: origin}; } var newSel = collapse && collapse != "end" && computeReplacedSel(this, changes, collapse); for (var i = changes.length - 1; i >= 0; i--) makeChange(this, changes[i]); if (newSel) setSelectionReplaceHistory(this, newSel); else if (this.cm) ensureCursorVisible(this.cm); }), undo: docMethodOp(function() {makeChangeFromHistory(this, "undo");}), redo: docMethodOp(function() {makeChangeFromHistory(this, "redo");}), undoSelection: docMethodOp(function() {makeChangeFromHistory(this, "undo", true);}), redoSelection: docMethodOp(function() {makeChangeFromHistory(this, "redo", true);}), setExtending: function(val) {this.extend = val;}, getExtending: function() {return this.extend;}, historySize: function() { var hist = this.history, done = 0, undone = 0; for (var i = 0; i < hist.done.length; i++) if (!hist.done[i].ranges) ++done; for (var i = 0; i < hist.undone.length; i++) if (!hist.undone[i].ranges) ++undone; return {undo: done, redo: undone}; }, clearHistory: function() {this.history = new History(this.history.maxGeneration);}, markClean: function() { this.cleanGeneration = this.changeGeneration(true); }, changeGeneration: function(forceSplit) { if (forceSplit) this.history.lastOp = this.history.lastSelOp = this.history.lastOrigin = null; return this.history.generation; }, isClean: function (gen) { return this.history.generation == (gen || this.cleanGeneration); }, getHistory: function() { return {done: copyHistoryArray(this.history.done), undone: copyHistoryArray(this.history.undone)}; }, setHistory: function(histData) { var hist = this.history = new History(this.history.maxGeneration); hist.done = copyHistoryArray(histData.done.slice(0), null, true); hist.undone = copyHistoryArray(histData.undone.slice(0), null, true); }, addLineClass: docMethodOp(function(handle, where, cls) { return changeLine(this, handle, where == "gutter" ? "gutter" : "class", function(line) { var prop = where == "text" ? "textClass" : where == "background" ? "bgClass" : where == "gutter" ? "gutterClass" : "wrapClass"; if (!line[prop]) line[prop] = cls; else if (classTest(cls).test(line[prop])) return false; else line[prop] += " " + cls; return true; }); }), removeLineClass: docMethodOp(function(handle, where, cls) { return changeLine(this, handle, where == "gutter" ? "gutter" : "class", function(line) { var prop = where == "text" ? "textClass" : where == "background" ? "bgClass" : where == "gutter" ? "gutterClass" : "wrapClass"; var cur = line[prop]; if (!cur) return false; else if (cls == null) line[prop] = null; else { var found = cur.match(classTest(cls)); if (!found) return false; var end = found.index + found[0].length; line[prop] = cur.slice(0, found.index) + (!found.index || end == cur.length ? "" : " ") + cur.slice(end) || null; } return true; }); }), addLineWidget: docMethodOp(function(handle, node, options) { return addLineWidget(this, handle, node, options); }), removeLineWidget: function(widget) { widget.clear(); }, markText: function(from, to, options) { return markText(this, clipPos(this, from), clipPos(this, to), options, options && options.type || "range"); }, setBookmark: function(pos, options) { var realOpts = {replacedWith: options && (options.nodeType == null ? options.widget : options), insertLeft: options && options.insertLeft, clearWhenEmpty: false, shared: options && options.shared, handleMouseEvents: options && options.handleMouseEvents}; pos = clipPos(this, pos); return markText(this, pos, pos, realOpts, "bookmark"); }, findMarksAt: function(pos) { pos = clipPos(this, pos); var markers = [], spans = getLine(this, pos.line).markedSpans; if (spans) for (var i = 0; i < spans.length; ++i) { var span = spans[i]; if ((span.from == null || span.from <= pos.ch) && (span.to == null || span.to >= pos.ch)) markers.push(span.marker.parent || span.marker); } return markers; }, findMarks: function(from, to, filter) { from = clipPos(this, from); to = clipPos(this, to); var found = [], lineNo = from.line; this.iter(from.line, to.line + 1, function(line) { var spans = line.markedSpans; if (spans) for (var i = 0; i < spans.length; i++) { var span = spans[i]; if (!(span.to != null && lineNo == from.line && from.ch >= span.to || span.from == null && lineNo != from.line || span.from != null && lineNo == to.line && span.from >= to.ch) && (!filter || filter(span.marker))) found.push(span.marker.parent || span.marker); } ++lineNo; }); return found; }, getAllMarks: function() { var markers = []; this.iter(function(line) { var sps = line.markedSpans; if (sps) for (var i = 0; i < sps.length; ++i) if (sps[i].from != null) markers.push(sps[i].marker); }); return markers; }, posFromIndex: function(off) { var ch, lineNo = this.first, sepSize = this.lineSeparator().length; this.iter(function(line) { var sz = line.text.length + sepSize; if (sz > off) { ch = off; return true; } off -= sz; ++lineNo; }); return clipPos(this, Pos(lineNo, ch)); }, indexFromPos: function (coords) { coords = clipPos(this, coords); var index = coords.ch; if (coords.line < this.first || coords.ch < 0) return 0; var sepSize = this.lineSeparator().length; this.iter(this.first, coords.line, function (line) { index += line.text.length + sepSize; }); return index; }, copy: function(copyHistory) { var doc = new Doc(getLines(this, this.first, this.first + this.size), this.modeOption, this.first, this.lineSep); doc.scrollTop = this.scrollTop; doc.scrollLeft = this.scrollLeft; doc.sel = this.sel; doc.extend = false; if (copyHistory) { doc.history.undoDepth = this.history.undoDepth; doc.setHistory(this.getHistory()); } return doc; }, linkedDoc: function(options) { if (!options) options = {}; var from = this.first, to = this.first + this.size; if (options.from != null && options.from > from) from = options.from; if (options.to != null && options.to < to) to = options.to; var copy = new Doc(getLines(this, from, to), options.mode || this.modeOption, from, this.lineSep); if (options.sharedHist) copy.history = this.history; (this.linked || (this.linked = [])).push({doc: copy, sharedHist: options.sharedHist}); copy.linked = [{doc: this, isParent: true, sharedHist: options.sharedHist}]; copySharedMarkers(copy, findSharedMarkers(this)); return copy; }, unlinkDoc: function(other) { if (other instanceof CodeMirror) other = other.doc; if (this.linked) for (var i = 0; i < this.linked.length; ++i) { var link = this.linked[i]; if (link.doc != other) continue; this.linked.splice(i, 1); other.unlinkDoc(this); detachSharedMarkers(findSharedMarkers(this)); break; } // If the histories were shared, split them again if (other.history == this.history) { var splitIds = [other.id]; linkedDocs(other, function(doc) {splitIds.push(doc.id);}, true); other.history = new History(null); other.history.done = copyHistoryArray(this.history.done, splitIds); other.history.undone = copyHistoryArray(this.history.undone, splitIds); } }, iterLinkedDocs: function(f) {linkedDocs(this, f);}, getMode: function() {return this.mode;}, getEditor: function() {return this.cm;}, splitLines: function(str) { if (this.lineSep) return str.split(this.lineSep); return splitLinesAuto(str); }, lineSeparator: function() { return this.lineSep || "\n"; } }); // Public alias. Doc.prototype.eachLine = Doc.prototype.iter; // Set up methods on CodeMirror's prototype to redirect to the editor's document. var dontDelegate = "iter insert remove copy getEditor constructor".split(" "); for (var prop in Doc.prototype) if (Doc.prototype.hasOwnProperty(prop) && indexOf(dontDelegate, prop) < 0) CodeMirror.prototype[prop] = (function(method) { return function() {return method.apply(this.doc, arguments);}; })(Doc.prototype[prop]); eventMixin(Doc); // Call f for all linked documents. function linkedDocs(doc, f, sharedHistOnly) { function propagate(doc, skip, sharedHist) { if (doc.linked) for (var i = 0; i < doc.linked.length; ++i) { var rel = doc.linked[i]; if (rel.doc == skip) continue; var shared = sharedHist && rel.sharedHist; if (sharedHistOnly && !shared) continue; f(rel.doc, shared); propagate(rel.doc, doc, shared); } } propagate(doc, null, true); } // Attach a document to an editor. function attachDoc(cm, doc) { if (doc.cm) throw new Error("This document is already in use."); cm.doc = doc; doc.cm = cm; estimateLineHeights(cm); loadMode(cm); if (!cm.options.lineWrapping) findMaxLine(cm); cm.options.mode = doc.modeOption; regChange(cm); } // LINE UTILITIES // Find the line object corresponding to the given line number. function getLine(doc, n) { n -= doc.first; if (n < 0 || n >= doc.size) throw new Error("There is no line " + (n + doc.first) + " in the document."); for (var chunk = doc; !chunk.lines;) { for (var i = 0;; ++i) { var child = chunk.children[i], sz = child.chunkSize(); if (n < sz) { chunk = child; break; } n -= sz; } } return chunk.lines[n]; } // Get the part of a document between two positions, as an array of // strings. function getBetween(doc, start, end) { var out = [], n = start.line; doc.iter(start.line, end.line + 1, function(line) { var text = line.text; if (n == end.line) text = text.slice(0, end.ch); if (n == start.line) text = text.slice(start.ch); out.push(text); ++n; }); return out; } // Get the lines between from and to, as array of strings. function getLines(doc, from, to) { var out = []; doc.iter(from, to, function(line) { out.push(line.text); }); return out; } // Update the height of a line, propagating the height change // upwards to parent nodes. function updateLineHeight(line, height) { var diff = height - line.height; if (diff) for (var n = line; n; n = n.parent) n.height += diff; } // Given a line object, find its line number by walking up through // its parent links. function lineNo(line) { if (line.parent == null) return null; var cur = line.parent, no = indexOf(cur.lines, line); for (var chunk = cur.parent; chunk; cur = chunk, chunk = chunk.parent) { for (var i = 0;; ++i) { if (chunk.children[i] == cur) break; no += chunk.children[i].chunkSize(); } } return no + cur.first; } // Find the line at the given vertical position, using the height // information in the document tree. function lineAtHeight(chunk, h) { var n = chunk.first; outer: do { for (var i = 0; i < chunk.children.length; ++i) { var child = chunk.children[i], ch = child.height; if (h < ch) { chunk = child; continue outer; } h -= ch; n += child.chunkSize(); } return n; } while (!chunk.lines); for (var i = 0; i < chunk.lines.length; ++i) { var line = chunk.lines[i], lh = line.height; if (h < lh) break; h -= lh; } return n + i; } // Find the height above the given line. function heightAtLine(lineObj) { lineObj = visualLine(lineObj); var h = 0, chunk = lineObj.parent; for (var i = 0; i < chunk.lines.length; ++i) { var line = chunk.lines[i]; if (line == lineObj) break; else h += line.height; } for (var p = chunk.parent; p; chunk = p, p = chunk.parent) { for (var i = 0; i < p.children.length; ++i) { var cur = p.children[i]; if (cur == chunk) break; else h += cur.height; } } return h; } // Get the bidi ordering for the given line (and cache it). Returns // false for lines that are fully left-to-right, and an array of // BidiSpan objects otherwise. function getOrder(line) { var order = line.order; if (order == null) order = line.order = bidiOrdering(line.text); return order; } // HISTORY function History(startGen) { // Arrays of change events and selections. Doing something adds an // event to done and clears undo. Undoing moves events from done // to undone, redoing moves them in the other direction. this.done = []; this.undone = []; this.undoDepth = Infinity; // Used to track when changes can be merged into a single undo // event this.lastModTime = this.lastSelTime = 0; this.lastOp = this.lastSelOp = null; this.lastOrigin = this.lastSelOrigin = null; // Used by the isClean() method this.generation = this.maxGeneration = startGen || 1; } // Create a history change event from an updateDoc-style change // object. function historyChangeFromChange(doc, change) { var histChange = {from: copyPos(change.from), to: changeEnd(change), text: getBetween(doc, change.from, change.to)}; attachLocalSpans(doc, histChange, change.from.line, change.to.line + 1); linkedDocs(doc, function(doc) {attachLocalSpans(doc, histChange, change.from.line, change.to.line + 1);}, true); return histChange; } // Pop all selection events off the end of a history array. Stop at // a change event. function clearSelectionEvents(array) { while (array.length) { var last = lst(array); if (last.ranges) array.pop(); else break; } } // Find the top change event in the history. Pop off selection // events that are in the way. function lastChangeEvent(hist, force) { if (force) { clearSelectionEvents(hist.done); return lst(hist.done); } else if (hist.done.length && !lst(hist.done).ranges) { return lst(hist.done); } else if (hist.done.length > 1 && !hist.done[hist.done.length - 2].ranges) { hist.done.pop(); return lst(hist.done); } } // Register a change in the history. Merges changes that are within // a single operation, or are close together with an origin that // allows merging (starting with "+") into a single event. function addChangeToHistory(doc, change, selAfter, opId) { var hist = doc.history; hist.undone.length = 0; var time = +new Date, cur; if ((hist.lastOp == opId || hist.lastOrigin == change.origin && change.origin && ((change.origin.charAt(0) == "+" && doc.cm && hist.lastModTime > time - doc.cm.options.historyEventDelay) || change.origin.charAt(0) == "*")) && (cur = lastChangeEvent(hist, hist.lastOp == opId))) { // Merge this change into the last event var last = lst(cur.changes); if (cmp(change.from, change.to) == 0 && cmp(change.from, last.to) == 0) { // Optimized case for simple insertion -- don't want to add // new changesets for every character typed last.to = changeEnd(change); } else { // Add new sub-event cur.changes.push(historyChangeFromChange(doc, change)); } } else { // Can not be merged, start a new event. var before = lst(hist.done); if (!before || !before.ranges) pushSelectionToHistory(doc.sel, hist.done); cur = {changes: [historyChangeFromChange(doc, change)], generation: hist.generation}; hist.done.push(cur); while (hist.done.length > hist.undoDepth) { hist.done.shift(); if (!hist.done[0].ranges) hist.done.shift(); } } hist.done.push(selAfter); hist.generation = ++hist.maxGeneration; hist.lastModTime = hist.lastSelTime = time; hist.lastOp = hist.lastSelOp = opId; hist.lastOrigin = hist.lastSelOrigin = change.origin; if (!last) signal(doc, "historyAdded"); } function selectionEventCanBeMerged(doc, origin, prev, sel) { var ch = origin.charAt(0); return ch == "*" || ch == "+" && prev.ranges.length == sel.ranges.length && prev.somethingSelected() == sel.somethingSelected() && new Date - doc.history.lastSelTime <= (doc.cm ? doc.cm.options.historyEventDelay : 500); } // Called whenever the selection changes, sets the new selection as // the pending selection in the history, and pushes the old pending // selection into the 'done' array when it was significantly // different (in number of selected ranges, emptiness, or time). function addSelectionToHistory(doc, sel, opId, options) { var hist = doc.history, origin = options && options.origin; // A new event is started when the previous origin does not match // the current, or the origins don't allow matching. Origins // starting with * are always merged, those starting with + are // merged when similar and close together in time. if (opId == hist.lastSelOp || (origin && hist.lastSelOrigin == origin && (hist.lastModTime == hist.lastSelTime && hist.lastOrigin == origin || selectionEventCanBeMerged(doc, origin, lst(hist.done), sel)))) hist.done[hist.done.length - 1] = sel; else pushSelectionToHistory(sel, hist.done); hist.lastSelTime = +new Date; hist.lastSelOrigin = origin; hist.lastSelOp = opId; if (options && options.clearRedo !== false) clearSelectionEvents(hist.undone); } function pushSelectionToHistory(sel, dest) { var top = lst(dest); if (!(top && top.ranges && top.equals(sel))) dest.push(sel); } // Used to store marked span information in the history. function attachLocalSpans(doc, change, from, to) { var existing = change["spans_" + doc.id], n = 0; doc.iter(Math.max(doc.first, from), Math.min(doc.first + doc.size, to), function(line) { if (line.markedSpans) (existing || (existing = change["spans_" + doc.id] = {}))[n] = line.markedSpans;