1use crate::document::{
2 LineIndex, MarkdownBlock, MarkdownBlockKind, MarkdownCodeBlock, MarkdownDocument,
3 MarkdownSourceStyle, MarkdownTarget, MarkdownTargetId, MarkdownTargetKind, assign_targets,
4 collect_source_styles, event_tree, fence_marker, fenced_code_line, fenced_code_lines,
5 fenced_content_bounds, parse_block, parser_options, source_range,
6};
7use pulldown_cmark::Parser;
8use std::{borrow::Cow, collections::BTreeMap, ops::Range};
9
10#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
11pub struct MarkdownParseStats {
12 pub parsed_bytes: usize,
13 pub scanned_bytes: usize,
14 pub source_bytes_copied: usize,
15 pub prefix_bytes_copied: usize,
16 pub parses: u64,
17 pub unsettled_blocks: u64,
18}
19
20#[derive(Debug, Clone, PartialEq, Eq)]
21struct Definition {
22 destination: String,
23 title: Option<String>,
24}
25
26#[derive(Debug, Clone, Default)]
27struct Settled {
28 blocks: usize,
29 targets: usize,
30 outline: usize,
31 styles: usize,
32 source_end: usize,
33 brackets: Vec<bool>,
34 definitions: Vec<Range<usize>>,
35 prefix: String,
36}
37
38#[derive(Debug, Clone, Copy, PartialEq, Eq)]
39enum FenceLine {
40 Indent(usize),
41 Marker(usize),
42 Trailing,
43 Content,
44}
45
46impl FenceLine {
47 fn feed(self, byte: u8, marker: u8, count: usize) -> Self {
48 match self {
49 Self::Indent(columns) => match byte {
50 b' ' if columns < 3 => Self::Indent(columns + 1),
51 byte if byte == marker => Self::Marker(1),
52 _ => Self::Content,
53 },
54 Self::Marker(run) => {
55 if byte == marker {
56 Self::Marker(run + 1)
57 } else if byte == b' ' && run >= count {
58 Self::Trailing
59 } else {
60 Self::Content
61 }
62 }
63 Self::Trailing => {
64 if byte == b' ' {
65 Self::Trailing
66 } else {
67 Self::Content
68 }
69 }
70 Self::Content => Self::Content,
71 }
72 }
73
74 fn closes(self, count: usize) -> bool {
75 match self {
76 Self::Marker(run) => run >= count,
77 Self::Trailing => true,
78 Self::Indent(_) | Self::Content => false,
79 }
80 }
81}
82
83#[derive(Debug, Clone)]
84struct OpenFence {
85 block: usize,
86 marker: u8,
87 count: usize,
88 start: usize,
89 content_start: usize,
90 line_start: usize,
91 complete: usize,
92 state: FenceLine,
93}
94
95struct TailParse {
96 blocks: Vec<MarkdownBlock>,
97 styles: Vec<MarkdownSourceStyle>,
98 definitions: BTreeMap<String, Definition>,
99 tail_definitions: Vec<Range<usize>>,
100 parsed_bytes: usize,
101 copied_bytes: usize,
102 prefix_bytes: usize,
103}
104
105#[derive(Debug, Clone, Default)]
106pub(crate) struct IncrementalDocument {
107 document: MarkdownDocument,
108 index: LineIndex,
109 settled: Settled,
110 definitions: BTreeMap<String, Definition>,
111 tail_definitions: Vec<Range<usize>>,
112 fence: Option<OpenFence>,
113 stats: MarkdownParseStats,
114}
115
116impl IncrementalDocument {
117 pub(crate) const fn document(&self) -> &MarkdownDocument {
118 &self.document
119 }
120
121 pub(crate) const fn stats(&self) -> MarkdownParseStats {
122 self.stats
123 }
124
125 pub(crate) const fn settled_blocks(&self) -> usize {
126 self.settled.blocks
127 }
128
129 pub(crate) fn open_code_block(&self) -> Option<usize> {
130 self.fence.as_ref().map(|fence| fence.block)
131 }
132
133 pub(crate) fn replace(&mut self, source: &str) -> usize {
134 let stats = self.stats;
135 *self = Self {
136 stats,
137 ..Self::default()
138 };
139 self.append(source);
140 0
141 }
142
143 pub(crate) fn append(&mut self, chunk: &str) -> usize {
144 let start = self.document.source.len();
145 self.document.source.push_str(chunk);
146 self.stats.source_bytes_copied += chunk.len();
147 self.stats.scanned_bytes += chunk.len();
148 self.index.extend(&self.document.source, start);
149 if self.fence.is_some() {
150 let block = self.fence.as_ref().map_or(0, |fence| fence.block);
151 if let Some(resume) = self.extend_fence(start) {
152 self.settle_to(block + 1, resume);
153 self.fence = None;
154 if resume < self.document.source.len() {
155 self.parse_tail();
156 }
157 }
158 return block;
159 }
160 self.parse_tail()
161 }
162
163 fn parse_tail(&mut self) -> usize {
164 let mut first_changed = self.settled.blocks;
165 loop {
166 first_changed = first_changed.min(self.settled.blocks);
167 let parsed = parse_from(
168 &self.document.source,
169 &self.index,
170 self.settled.source_end,
171 &self.settled.prefix,
172 );
173 self.stats.parsed_bytes += parsed.parsed_bytes;
174 self.stats.source_bytes_copied += parsed.copied_bytes;
175 self.stats.prefix_bytes_copied += parsed.prefix_bytes;
176 self.stats.parses += 1;
177 self.install(parsed.blocks, parsed.styles);
178 if parsed.definitions != self.definitions {
179 self.definitions = parsed.definitions;
180 if let Some(block) = self.settled.brackets.iter().position(|bracket| *bracket) {
181 self.unsettle(block);
182 self.stats.unsettled_blocks += 1;
183 continue;
184 }
185 }
186 self.tail_definitions = parsed.tail_definitions;
187 break;
188 }
189 self.settle_tail();
190 self.detect_fence();
191 first_changed
192 }
193
194 fn install(&mut self, blocks: Vec<MarkdownBlock>, styles: Vec<MarkdownSourceStyle>) {
195 let settled = &self.settled;
196 let document = &mut self.document;
197 document.blocks.truncate(settled.blocks);
198 document.blocks.extend(blocks);
199 document.source_styles.truncate(settled.styles);
200 document.source_styles.extend(styles);
201 document.targets.truncate(settled.targets);
202 document.outline.truncate(settled.outline);
203 assign_targets(
204 &mut document.blocks[settled.blocks..],
205 &mut document.targets,
206 &mut document.outline,
207 );
208 }
209
210 fn unsettle(&mut self, block: usize) {
211 let blocks = &self.document.blocks;
212 let gap_start = block
213 .checked_sub(1)
214 .map_or(0, |previous| blocks[previous].source.bytes.end);
215 let end = self.attached_start(blocks[block].source.bytes.start, gap_start);
216 self.settled.blocks = block;
217 self.settled.source_end = end;
218 self.settled.brackets.truncate(block);
219 self.settled.definitions.retain(|span| span.end <= end);
220 self.settled.prefix.clear();
221 for span in &self.settled.definitions {
222 self.stats.prefix_bytes_copied += span.len() + 1;
223 self.stats.source_bytes_copied += span.len() + 1;
224 self.settled
225 .prefix
226 .push_str(&self.document.source[span.clone()]);
227 self.settled.prefix.push('\n');
228 }
229 self.sync_settled_counts();
230 self.fence = None;
231 }
232
233 fn sync_settled_counts(&mut self) {
234 let end = self.settled.source_end;
235 let document = &self.document;
236 self.settled.targets = document
237 .targets
238 .partition_point(|target| target.source.bytes.start < end);
239 self.settled.outline = document
240 .outline
241 .partition_point(|heading| heading.source.bytes.start < end);
242 self.settled.styles = document
243 .source_styles
244 .partition_point(|style| style.source.bytes.start < end);
245 }
246
247 fn settle_tail(&mut self) {
248 let blocks = &self.document.blocks;
249 let mut settled = self.settled.blocks;
250 let mut end = self.settled.source_end;
251 while settled < blocks.len() {
252 let Some(boundary) = self.settle_boundary(&blocks[settled], blocks.get(settled + 1))
253 else {
254 break;
255 };
256 end = boundary;
257 settled += 1;
258 }
259 if settled > self.settled.blocks {
260 self.settle_to(settled, end);
261 }
262 }
263
264 fn settle_to(&mut self, blocks: usize, end: usize) {
265 let source = &self.document.source;
266 for block in &self.document.blocks[self.settled.blocks..blocks] {
267 let bracket = !matches!(block.kind, MarkdownBlockKind::CodeBlock(_)) && {
268 let bytes = &source[block.source.bytes.clone()];
269 self.stats.scanned_bytes += bytes.len();
270 bytes.contains('[')
271 };
272 self.settled.brackets.push(bracket);
273 }
274 self.settled.blocks = blocks;
275 self.settled.source_end = end;
276 self.sync_settled_counts();
277 let mut remaining = Vec::new();
278 for span in std::mem::take(&mut self.tail_definitions) {
279 if span.end <= end {
280 self.stats.prefix_bytes_copied += span.len() + 1;
281 self.stats.source_bytes_copied += span.len() + 1;
282 self.settled
283 .prefix
284 .push_str(&self.document.source[span.clone()]);
285 self.settled.prefix.push('\n');
286 self.settled.definitions.push(span);
287 } else {
288 remaining.push(span);
289 }
290 }
291 self.tail_definitions = remaining;
292 }
293
294 fn settle_boundary(
295 &self,
296 block: &MarkdownBlock,
297 next: Option<&MarkdownBlock>,
298 ) -> Option<usize> {
299 let source = self.document.source.as_str();
300 if let Some(next) = next {
301 let start = next.source.bytes.start;
302 return self
303 .index
304 .line_complete(start)
305 .then(|| self.attached_start(start, block.source.bytes.end))
306 .filter(|boundary| *boundary >= block.source.bytes.end);
307 }
308 let end = block.source.bytes.end;
309 match &block.kind {
310 MarkdownBlockKind::Heading { .. } | MarkdownBlockKind::Rule => {
311 source[..end].ends_with('\n').then_some(end)
312 }
313 MarkdownBlockKind::Paragraph { .. }
314 | MarkdownBlockKind::Table(_)
315 | MarkdownBlockKind::BlockQuote { .. } => blank_line_at(source, end).then_some(end),
316 MarkdownBlockKind::CodeBlock(code) => {
317 (code.info.is_some() && end < source.len()).then(|| after_eol(source, end))
318 }
319 MarkdownBlockKind::List { .. } | MarkdownBlockKind::HtmlFallback { .. } => None,
320 }
321 }
322
323 fn attached_start(&self, start: usize, gap_start: usize) -> usize {
324 let source = self.document.source.as_str();
325 let mut start = self.index.line_start_of(start);
326 while start > gap_start {
327 let previous = self.index.line_start_of(start - 1);
328 if previous < gap_start || blank_line_at(source, previous) {
329 break;
330 }
331 start = previous;
332 }
333 start
334 }
335
336 fn detect_fence(&mut self) {
337 let source = self.document.source.as_str();
338 let len = source.len();
339 let index = self.document.blocks.len().checked_sub(1);
340 let Some(index) = index.filter(|index| *index >= self.settled.blocks) else {
341 return;
342 };
343 let block = &self.document.blocks[index];
344 let MarkdownBlockKind::CodeBlock(code) = &block.kind else {
345 return;
346 };
347 let start = block.source.bytes.start;
348 if code.info.is_none() || block.source.bytes.end != len || !self.index.line_complete(start)
349 {
350 return;
351 }
352 let opening_end = source[start..]
353 .find('\n')
354 .map_or(len, |offset| start + offset + 1);
355 let (marker, count) = fence_marker(&source[start..opening_end]);
356 let line_start = self.index.line_start_of(len).max(opening_end);
357 let mut state = FenceLine::Indent(0);
358 for byte in source[line_start..].bytes() {
359 state = state.feed(byte, marker, count);
360 }
361 self.stats.scanned_bytes += len - line_start;
362 self.fence = Some(OpenFence {
363 block: index,
364 marker,
365 count,
366 start,
367 content_start: opening_end,
368 line_start,
369 complete: self.index.line_breaks_after(opening_end),
370 state,
371 });
372 }
373
374 fn extend_fence(&mut self, start: usize) -> Option<usize> {
375 let mut fence = self.fence.take()?;
376 let MarkdownDocument {
377 source,
378 blocks,
379 targets,
380 ..
381 } = &mut self.document;
382 let bytes = source.as_bytes();
383 let len = bytes.len();
384 let MarkdownBlockKind::CodeBlock(code) = &mut blocks[fence.block].kind else {
385 return None;
386 };
387 let previous_lines = code.lines.len();
388 code.lines.truncate(fence.complete);
389 let mut close = None;
390 let mut position = start;
391 while position < len {
392 let byte = bytes[position];
393 match byte {
394 b'\n' | b'\r' if fence.state.closes(fence.count) => {
395 let resume = position
396 + 1
397 + usize::from(byte == b'\r' && bytes.get(position + 1) == Some(&b'\n'));
398 close = Some((position, resume));
399 break;
400 }
401 b'\n' => {
402 code.lines.push(fenced_code_line(
403 fence.complete,
404 fence.line_start,
405 &source[fence.line_start..position],
406 &self.index,
407 ));
408 fence.complete += 1;
409 fence.line_start = position + 1;
410 fence.state = FenceLine::Indent(0);
411 }
412 _ => fence.state = fence.state.feed(byte, fence.marker, fence.count),
413 }
414 position += 1;
415 }
416 self.stats.scanned_bytes += len - start;
417 let block_end = close.map_or(len, |(end, _)| end);
418 let closing_start = (close.is_some() || fence.state.closes(fence.count))
419 .then_some(fence.line_start.max(fence.content_start));
420 let content = fenced_content_bounds(fence.content_start, closing_start, block_end, source);
421 let first_changed_line = if closing_start.is_some() || code.lines.len() < fence.complete {
422 self.stats.scanned_bytes += content.len();
423 code.lines = fenced_code_lines(content.clone(), source, &self.index);
424 0
425 } else {
426 if let Some(last) = code.lines.last_mut() {
427 last.source =
428 source_range(last.source.bytes.start..fence.line_start - 1, &self.index);
429 }
430 if len > fence.content_start {
431 self.stats.scanned_bytes += len - fence.line_start;
432 code.lines.push(fenced_code_line(
433 fence.complete,
434 fence.line_start,
435 &source[fence.line_start..],
436 &self.index,
437 ));
438 }
439 previous_lines.saturating_sub(1).min(fence.complete)
440 };
441 code.content = source_range(content, &self.index);
442 code.source = source_range(fence.start..block_end, &self.index);
443 let block_source = code.source.clone();
444 sync_code_targets(code, targets, first_changed_line);
445 blocks[fence.block].source = block_source;
446 let resume = close.map(|(_, resume)| resume);
447 if resume.is_none() {
448 self.fence = Some(fence);
449 }
450 resume
451 }
452}
453
454fn sync_code_targets(code: &mut MarkdownCodeBlock, targets: &mut Vec<MarkdownTarget>, from: usize) {
455 let Some(base) = code.target_id.map(MarkdownTargetId::index) else {
456 return;
457 };
458 if let Some(target) = targets.get_mut(base) {
459 target.source = code.source.clone();
460 }
461 targets.truncate(base + 1 + from);
462 for line in &mut code.lines[from..] {
463 let id = MarkdownTargetId::new(targets.len());
464 line.target_id = Some(id);
465 targets.push(MarkdownTarget {
466 id,
467 kind: MarkdownTargetKind::CodeLine,
468 source: line.source.clone(),
469 display_label: format!("Code line {}", line.index + 1),
470 });
471 }
472}
473
474fn parse_from(source: &str, index: &LineIndex, tail_start: usize, prefix: &str) -> TailParse {
475 let tail = &source[tail_start..];
476 let (text, shift) = if prefix.is_empty() {
477 (Cow::Borrowed(tail), 0)
478 } else {
479 (Cow::Owned(format!("{prefix}\n{tail}")), prefix.len() + 1)
480 };
481 let parser = Parser::new_ext(&text, parser_options());
482 let mut definitions = BTreeMap::new();
483 let mut tail_definitions = Vec::new();
484 for (label, definition) in parser.reference_definitions().iter() {
485 definitions.insert(
486 label.to_owned(),
487 Definition {
488 destination: definition.dest.to_string(),
489 title: definition.title.as_ref().map(ToString::to_string),
490 },
491 );
492 if definition.span.start >= shift {
493 tail_definitions.push(
494 definition.span.start - shift + tail_start
495 ..definition.span.end - shift + tail_start,
496 );
497 }
498 }
499 tail_definitions.sort_by_key(|span| span.start);
500 let events = parser
501 .into_offset_iter()
502 .filter(|(_, range)| range.start >= shift)
503 .map(|(event, range)| {
504 (
505 event.into_static(),
506 range.start - shift + tail_start..range.end - shift + tail_start,
507 )
508 })
509 .collect::<Vec<_>>();
510 let roots = event_tree(&events);
511 let mut styles = Vec::new();
512 collect_source_styles(&roots, index, &mut styles);
513 let blocks = roots
514 .iter()
515 .filter_map(|node| parse_block(node, 0, source, index))
516 .collect();
517 TailParse {
518 blocks,
519 styles,
520 definitions,
521 tail_definitions,
522 parsed_bytes: text.len(),
523 copied_bytes: if matches!(text, Cow::Owned(_)) {
524 text.len()
525 } else {
526 0
527 },
528 prefix_bytes: if prefix.is_empty() {
529 0
530 } else {
531 prefix.len() + 1
532 },
533 }
534}
535
536fn blank_line_at(source: &str, position: usize) -> bool {
537 let mut cursor = position;
538 let bytes = source.as_bytes();
539 while let Some(byte) = bytes.get(cursor) {
540 match byte {
541 b' ' | b'\t' | 0x0b | 0x0c => cursor += 1,
542 b'\n' | b'\r' => return true,
543 _ => return false,
544 }
545 }
546 false
547}
548
549fn after_eol(source: &str, position: usize) -> usize {
550 let bytes = source.as_bytes();
551 match (bytes.get(position), bytes.get(position + 1)) {
552 (Some(b'\r'), Some(b'\n')) => position + 2,
553 (Some(b'\n' | b'\r'), _) => position + 1,
554 _ => position,
555 }
556}