diffdown.com
Diffdown is a real-time collaborative Markdown editor/previewer built on the AT Protocol
diffdown.com
1import {Tree, TreeFragment} from "@lezer/common"
2import ist from "ist"
3import {parser} from "../dist/index.js"
4import {compareTree} from "./compare-tree.js"
5
6let doc1 = `
7Header
8---
9One **two**
10three *four*
11five.
12
13> Start of quote
14>
15> 1. Nested list
16>
17> 2. More content
18> inside the [list][link]
19>
20> Continued item
21>
22> ~~~
23> Block of code
24> ~~~
25>
26> 3. And so on
27
28[link]: /ref
29[another]: /one
30And a final paragraph.
31 ***
32The end.
33`
34
35type ChangeSpec = {from: number, to?: number, insert?: string}[]
36
37class State {
38 constructor(readonly doc: string,
39 readonly tree: Tree,
40 readonly fragments: readonly TreeFragment[]) {}
41
42 static start(doc: string) {
43 let tree = parser.parse(doc)
44 return new State(doc, tree, TreeFragment.addTree(tree))
45 }
46
47 update(changes: ChangeSpec, reparse = true) {
48 let changed = [], doc = this.doc, off = 0
49 for (let {from, to = from, insert = ""} of changes) {
50 doc = doc.slice(0, from) + insert + doc.slice(to)
51 changed.push({fromA: from - off, toA: to - off, fromB: from, toB: from + insert.length})
52 off += insert.length - (to - from)
53 }
54 let fragments = TreeFragment.applyChanges(this.fragments, changed, 2)
55 if (!reparse) return new State(doc, Tree.empty, fragments)
56 let tree = parser.parse(doc, fragments)
57 return new State(doc, tree, TreeFragment.addTree(tree, fragments))
58 }
59}
60
61let _state1: State | null = null, state1 = () => _state1 || (_state1 = State.start(doc1))
62
63function overlap(a: Tree, b: Tree) {
64 let inA = new Set<Tree>(), shared = 0, sharingTo = 0
65 for (let cur = a.cursor(); cur.next();) if (cur.tree) inA.add(cur.tree)
66 for (let cur = b.cursor(); cur.next();) if (cur.tree && inA.has(cur.tree) && cur.type.is("Block") && cur.from >= sharingTo) {
67 shared += cur.to - cur.from
68 sharingTo = cur.to
69 }
70 return Math.round(shared * 100 / b.length)
71}
72
73function testChange(change: ChangeSpec, reuse = 10) {
74 let state = state1().update(change)
75 compareTree(state.tree, parser.parse(state.doc))
76 if (reuse) ist(overlap(state.tree, state1().tree), reuse, ">")
77}
78
79describe("Markdown incremental parsing", () => {
80 it("can produce the proper tree", () => {
81 // Replace 'three' with 'bears'
82 let state = state1().update([{from: 24, to: 29, insert: "bears"}])
83 compareTree(state.tree, state1().tree)
84 })
85
86 it("reuses nodes from the previous parse", () => {
87 // Replace 'three' with 'bears'
88 let state = state1().update([{from: 24, to: 29, insert: "bears"}])
89 ist(overlap(state1().tree, state.tree), 80, ">")
90 })
91
92 it("can reuse content for a change in a block context", () => {
93 // Replace 'content' with 'monkeys'
94 let state = state1().update([{from: 92, to: 99, insert: "monkeys"}])
95 compareTree(state.tree, state1().tree)
96 ist(overlap(state1().tree, state.tree), 20, ">")
97 })
98
99 it("can handle deleting a quote mark", () => testChange([{from: 82, to: 83}]))
100
101 it("can handle adding to a quoted block", () => testChange([{from: 37, insert: "> "}, {from: 45, insert: "> "}]))
102
103 it("can handle a change in a post-linkref paragraph", () => testChange([{from: 249, to: 251}]))
104
105 it("can handle a change in a paragraph-adjacent linkrefs", () => testChange([{from: 230, to: 231}]))
106
107 it("can deal with multiple changes applied separately", () => {
108 let state = state1().update([{from: 190, to: 191}], false).update([{from: 30, insert: "hi\n\nyou"}])
109 compareTree(state.tree, parser.parse(state.doc))
110 ist(overlap(state.tree, state1().tree), 20, ">")
111 })
112
113 it("works when a change happens directly after a block", () => testChange([{from: 150, to: 167}]))
114
115 it("works when a change deletes a blank line after a paragraph", () => testChange([{from: 207, to: 213}]))
116
117 it("doesn't get confused by removing paragraph-breaking markup", () => testChange([{from: 264, to: 265}]))
118
119 function r(n: number) { return Math.floor(Math.random() * n) }
120 function rStr(len: number) {
121 let result = "", chars = "\n>x-"
122 while (result.length < len) result += chars[r(chars.length)]
123 return result
124 }
125
126 it("survives random changes", () => {
127 for (let i = 0, l = doc1.length; i < 20; i++) {
128 let c = 1 + r(4), changes = []
129 for (let i = 0, rFrom = 0; i < c; i++) {
130 let rTo = rFrom + Math.floor((l - rFrom) / (c - i))
131 let from = rFrom + r(rTo - rFrom - 1), to = r(2) == 1 ? from : from + r(Math.min(rTo - from, 20))
132 let iR = r(3), insert = iR == 0 && from != to ? "" : iR == 1 ? "\n\n" : rStr(r(5) + 1)
133 changes.push({from, to, insert})
134 l += insert.length - (to - from)
135 rFrom = to + insert.length
136 }
137 testChange(changes, 0)
138 }
139 })
140
141 it("can handle large documents", () => {
142 let doc = doc1.repeat(50)
143 let state = State.start(doc)
144 let newState = state.update([{from: doc.length >> 1, insert: "a\n\nb"}])
145 ist(overlap(state.tree, newState.tree), 90, ">")
146 })
147
148 it("properly re-parses a continued indented code block", () => {
149 let state = State.start(`
150One paragraph to create a bit of string length here
151
152 Code
153 Block
154
155
156
157Another paragraph that is long enough to create a fragment
158`).update([{from: 76, insert: " "}])
159 compareTree(state.tree, parser.parse(state.doc))
160 })
161
162 it("properly re-parses a continued list", () => {
163 let state = State.start(`
164One paragraph to create a bit of string length here
165
166 * List
167
168
169
170More content
171
172Another paragraph that is long enough to create a fragment
173`).update([{from: 65, insert: " * "}])
174 compareTree(state.tree, parser.parse(state.doc))
175 })
176
177 it("can recover from incremental parses that stop in the middle of a list", () => {
178 let doc = `
1791. I am a list item with ***some* emphasized
180 content inside** and the parser hopefully stops
181 parsing after me.
182
1832. Oh no the list continues.
184`
185 let parse = parser.startParse(doc), tree
186 parse.advance()
187 ist(parse.parsedPos, doc.length, "<")
188 parse.stopAt(parse.parsedPos)
189 while (!(tree = parse.advance())) {}
190 let state = new State(doc, tree, TreeFragment.addTree(tree)).update([])
191 ist(state.tree.topNode.lastChild!.from, 1)
192 })
193
194 it("can reuse list items", () => {
195 let start = State.start(" - List item\n".repeat(100))
196 let state = start.update([{from: 18, to: 19}])
197 ist(overlap(start.tree, state.tree), 80, ">")
198 })
199
200 it("can reuse regular blocks before a continuable block", () => {
201 let start = State.start("A reusable paragraph\n\n".repeat(50) + "- etc\n\n")
202 let state = start.update([{from: start.doc.length, insert: "x"}])
203 ist(overlap(start.tree, state.tree), 85, ">")
204 })
205
206 it("returns a tree starting at the first range", () => {
207 let result = parser.parse("foo\n\nbar", [], [{from: 5, to: 8}])
208 ist(result.toString(), "Document(Paragraph)")
209 ist(result.length, 3)
210 ist(result.positions[0], 0)
211 })
212
213 it("Allows gaps in the input", () => {
214 let doc = `
215The first X *y* X<
216
217>X paragraph.
218
219 - And *a X<*>X list*
220`
221 let tree = parser.parse(doc, [], [{from: 0, to: 11}, {from: 12, to: 17}, {from: 23, to: 46}, {from: 51, to: 58}])
222 ist(tree.toString(),
223 "Document(Paragraph(Emphasis(EmphasisMark,EmphasisMark)),BulletList(ListItem(ListMark,Paragraph(Emphasis(EmphasisMark,EmphasisMark)))))")
224 ist(tree.length, doc.length)
225 let top = tree.topNode, first = top.firstChild!
226 ist(first.name, "Paragraph")
227 ist(first.from, 1)
228 ist(first.to, 34)
229 let last = top.lastChild!.lastChild!.lastChild!, em = last.lastChild!
230 ist(last.name, "Paragraph")
231 ist(last.from, 39)
232 ist(last.to, 57)
233 ist(em.name, "Emphasis")
234 ist(em.from, 43)
235 ist(em.to, 57)
236 })
237
238 it("can reuse nodes at the end of the document", () => {
239 let doc = `* List item
240
241~~~js
242function foo() {
243 return false
244}
245~~~
246`
247 let tree = parser.parse(doc)
248 let ins = 11
249 let doc2 = doc.slice(0, ins) + "\n* " + doc.slice(ins)
250 let fragments = TreeFragment.applyChanges(TreeFragment.addTree(tree), [{fromA: ins, toA: ins, fromB: ins, toB: ins + 3}])
251 let tree2 = parser.parse(doc2, fragments)
252 ist(tree2.topNode.lastChild!.tree, tree.topNode.lastChild!.tree)
253 })
254
255 it("places reused nodes at the right position when there are gaps before them", () => {
256 let doc = " {{}}\nb\n{{}}"
257 let ast1 = parser.parse(doc, undefined, [{from: 0, to: 1}, {from: 5, to: 8}])
258 let frag = TreeFragment.applyChanges(TreeFragment.addTree(ast1), [{fromA: 0, toA: 0, fromB: 0, toB: 1}])
259 let ast2 = parser.parse(" " + doc, frag, [{from: 0, to: 2}, {from: 6, to: 9}])
260 ist(ast2.toString(), "Document(Paragraph)")
261 let p = ast2.topNode.firstChild!
262 ist(p.from, 7)
263 ist(p.to, 8)
264 })
265})