Mercurial
diff .cms/lib/codemirror/src/model/chunk.js @ 0:78edf6b517a0 draft
24.10
author | Coffee CMS <info@coffee-cms.ru> |
---|---|
date | Fri, 11 Oct 2024 22:40:23 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/.cms/lib/codemirror/src/model/chunk.js Fri Oct 11 22:40:23 2024 +0000 @@ -0,0 +1,167 @@ +import { cleanUpLine } from "../line/line_data.js" +import { indexOf } from "../util/misc.js" +import { signalLater } from "../util/operation_group.js" + +// The document is represented as a BTree consisting of leaves, with +// chunk of lines in them, and branches, with up to ten leaves or +// other branch nodes below them. The top node is always a branch +// node, and is the document object itself (meaning it has +// additional methods and properties). +// +// All nodes have parent links. The tree is used both to go from +// line numbers to line objects, and to go from objects to numbers. +// It also indexes by height, and is used to convert between height +// and line object, and to find the total height of the document. +// +// See also http://marijnhaverbeke.nl/blog/codemirror-line-tree.html + +export function LeafChunk(lines) { + this.lines = lines + this.parent = null + let height = 0 + for (let i = 0; i < lines.length; ++i) { + lines[i].parent = this + height += lines[i].height + } + this.height = height +} + +LeafChunk.prototype = { + chunkSize() { return this.lines.length }, + + // Remove the n lines at offset 'at'. + removeInner(at, n) { + for (let i = at, e = at + n; i < e; ++i) { + let line = this.lines[i] + this.height -= line.height + cleanUpLine(line) + signalLater(line, "delete") + } + this.lines.splice(at, n) + }, + + // Helper used to collapse a small branch into a single leaf. + collapse(lines) { + lines.push.apply(lines, this.lines) + }, + + // Insert the given array of lines at offset 'at', count them as + // having the given height. + insertInner(at, lines, height) { + this.height += height + this.lines = this.lines.slice(0, at).concat(lines).concat(this.lines.slice(at)) + for (let i = 0; i < lines.length; ++i) lines[i].parent = this + }, + + // Used to iterate over a part of the tree. + iterN(at, n, op) { + for (let e = at + n; at < e; ++at) + if (op(this.lines[at])) return true + } +} + +export function BranchChunk(children) { + this.children = children + let size = 0, height = 0 + for (let i = 0; i < children.length; ++i) { + let ch = children[i] + size += ch.chunkSize(); height += ch.height + ch.parent = this + } + this.size = size + this.height = height + this.parent = null +} + +BranchChunk.prototype = { + chunkSize() { return this.size }, + + removeInner(at, n) { + this.size -= n + for (let i = 0; i < this.children.length; ++i) { + let child = this.children[i], sz = child.chunkSize() + if (at < sz) { + let rm = Math.min(n, sz - at), oldHeight = child.height + child.removeInner(at, rm) + this.height -= oldHeight - child.height + if (sz == rm) { this.children.splice(i--, 1); child.parent = null } + if ((n -= rm) == 0) break + at = 0 + } else at -= sz + } + // If the result is smaller than 25 lines, ensure that it is a + // single leaf node. + if (this.size - n < 25 && + (this.children.length > 1 || !(this.children[0] instanceof LeafChunk))) { + let lines = [] + this.collapse(lines) + this.children = [new LeafChunk(lines)] + this.children[0].parent = this + } + }, + + collapse(lines) { + for (let i = 0; i < this.children.length; ++i) this.children[i].collapse(lines) + }, + + insertInner(at, lines, height) { + this.size += lines.length + this.height += height + for (let i = 0; i < this.children.length; ++i) { + let child = this.children[i], sz = child.chunkSize() + if (at <= sz) { + child.insertInner(at, lines, height) + if (child.lines && child.lines.length > 50) { + // To avoid memory thrashing when child.lines is huge (e.g. first view of a large file), it's never spliced. + // Instead, small slices are taken. They're taken in order because sequential memory accesses are fastest. + let remaining = child.lines.length % 25 + 25 + for (let pos = remaining; pos < child.lines.length;) { + let 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() { + if (this.children.length <= 10) return + let me = this + do { + let spilled = me.children.splice(me.children.length - 5, 5) + let sibling = new BranchChunk(spilled) + if (!me.parent) { // Become the parent node + let copy = new BranchChunk(me.children) + copy.parent = me + me.children = [copy, sibling] + me = copy + } else { + me.size -= sibling.size + me.height -= sibling.height + let 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(at, n, op) { + for (let i = 0; i < this.children.length; ++i) { + let child = this.children[i], sz = child.chunkSize() + if (at < sz) { + let used = Math.min(n, sz - at) + if (child.iterN(at, used, op)) return true + if ((n -= used) == 0) break + at = 0 + } else at -= sz + } + } +}