chunk.js (5356B)
1 import { cleanUpLine } from "../line/line_data.js" 2 import { indexOf } from "../util/misc.js" 3 import { signalLater } from "../util/operation_group.js" 4 5 // The document is represented as a BTree consisting of leaves, with 6 // chunk of lines in them, and branches, with up to ten leaves or 7 // other branch nodes below them. The top node is always a branch 8 // node, and is the document object itself (meaning it has 9 // additional methods and properties). 10 // 11 // All nodes have parent links. The tree is used both to go from 12 // line numbers to line objects, and to go from objects to numbers. 13 // It also indexes by height, and is used to convert between height 14 // and line object, and to find the total height of the document. 15 // 16 // See also http://marijnhaverbeke.nl/blog/codemirror-line-tree.html 17 18 export function LeafChunk(lines) { 19 this.lines = lines 20 this.parent = null 21 let height = 0 22 for (let i = 0; i < lines.length; ++i) { 23 lines[i].parent = this 24 height += lines[i].height 25 } 26 this.height = height 27 } 28 29 LeafChunk.prototype = { 30 chunkSize() { return this.lines.length }, 31 32 // Remove the n lines at offset 'at'. 33 removeInner(at, n) { 34 for (let i = at, e = at + n; i < e; ++i) { 35 let line = this.lines[i] 36 this.height -= line.height 37 cleanUpLine(line) 38 signalLater(line, "delete") 39 } 40 this.lines.splice(at, n) 41 }, 42 43 // Helper used to collapse a small branch into a single leaf. 44 collapse(lines) { 45 lines.push.apply(lines, this.lines) 46 }, 47 48 // Insert the given array of lines at offset 'at', count them as 49 // having the given height. 50 insertInner(at, lines, height) { 51 this.height += height 52 this.lines = this.lines.slice(0, at).concat(lines).concat(this.lines.slice(at)) 53 for (let i = 0; i < lines.length; ++i) lines[i].parent = this 54 }, 55 56 // Used to iterate over a part of the tree. 57 iterN(at, n, op) { 58 for (let e = at + n; at < e; ++at) 59 if (op(this.lines[at])) return true 60 } 61 } 62 63 export function BranchChunk(children) { 64 this.children = children 65 let size = 0, height = 0 66 for (let i = 0; i < children.length; ++i) { 67 let ch = children[i] 68 size += ch.chunkSize(); height += ch.height 69 ch.parent = this 70 } 71 this.size = size 72 this.height = height 73 this.parent = null 74 } 75 76 BranchChunk.prototype = { 77 chunkSize() { return this.size }, 78 79 removeInner(at, n) { 80 this.size -= n 81 for (let i = 0; i < this.children.length; ++i) { 82 let child = this.children[i], sz = child.chunkSize() 83 if (at < sz) { 84 let rm = Math.min(n, sz - at), oldHeight = child.height 85 child.removeInner(at, rm) 86 this.height -= oldHeight - child.height 87 if (sz == rm) { this.children.splice(i--, 1); child.parent = null } 88 if ((n -= rm) == 0) break 89 at = 0 90 } else at -= sz 91 } 92 // If the result is smaller than 25 lines, ensure that it is a 93 // single leaf node. 94 if (this.size - n < 25 && 95 (this.children.length > 1 || !(this.children[0] instanceof LeafChunk))) { 96 let lines = [] 97 this.collapse(lines) 98 this.children = [new LeafChunk(lines)] 99 this.children[0].parent = this 100 } 101 }, 102 103 collapse(lines) { 104 for (let i = 0; i < this.children.length; ++i) this.children[i].collapse(lines) 105 }, 106 107 insertInner(at, lines, height) { 108 this.size += lines.length 109 this.height += height 110 for (let i = 0; i < this.children.length; ++i) { 111 let child = this.children[i], sz = child.chunkSize() 112 if (at <= sz) { 113 child.insertInner(at, lines, height) 114 if (child.lines && child.lines.length > 50) { 115 // To avoid memory thrashing when child.lines is huge (e.g. first view of a large file), it's never spliced. 116 // Instead, small slices are taken. They're taken in order because sequential memory accesses are fastest. 117 let remaining = child.lines.length % 25 + 25 118 for (let pos = remaining; pos < child.lines.length;) { 119 let leaf = new LeafChunk(child.lines.slice(pos, pos += 25)) 120 child.height -= leaf.height 121 this.children.splice(++i, 0, leaf) 122 leaf.parent = this 123 } 124 child.lines = child.lines.slice(0, remaining) 125 this.maybeSpill() 126 } 127 break 128 } 129 at -= sz 130 } 131 }, 132 133 // When a node has grown, check whether it should be split. 134 maybeSpill() { 135 if (this.children.length <= 10) return 136 let me = this 137 do { 138 let spilled = me.children.splice(me.children.length - 5, 5) 139 let sibling = new BranchChunk(spilled) 140 if (!me.parent) { // Become the parent node 141 let copy = new BranchChunk(me.children) 142 copy.parent = me 143 me.children = [copy, sibling] 144 me = copy 145 } else { 146 me.size -= sibling.size 147 me.height -= sibling.height 148 let myIndex = indexOf(me.parent.children, me) 149 me.parent.children.splice(myIndex + 1, 0, sibling) 150 } 151 sibling.parent = me.parent 152 } while (me.children.length > 10) 153 me.parent.maybeSpill() 154 }, 155 156 iterN(at, n, op) { 157 for (let i = 0; i < this.children.length; ++i) { 158 let child = this.children[i], sz = child.chunkSize() 159 if (at < sz) { 160 let used = Math.min(n, sz - at) 161 if (child.iterN(at, used, op)) return true 162 if ((n -= used) == 0) break 163 at = 0 164 } else at -= sz 165 } 166 } 167 }