Mercurial
comparison .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 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:78edf6b517a0 |
---|---|
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 } |