Skip to main content

gpui_kit/content/markdown/
parse.rs

1//! Markdown source turned into an owned tree, before anything is drawn.
2//!
3//! Rendering straight from the event stream would mean deciding a block's
4//! layout before its contents are known, and would leave nothing for a test to
5//! assert against but pixels. The tree is the seam: parsing is pure and
6//! testable on its own, truncation is arithmetic over it, and the renderer
7//! only ever walks a finished structure.
8//!
9//! Raw HTML survives parsing as [`Block::Html`] and [`Inline::Html`]. It is
10//! never interpreted and never discarded, because a document that could delete
11//! its own content from the reader's view by wrapping it in a tag would be a
12//! document nobody could trust.
13
14use gpui::SharedString;
15use pulldown_cmark::{CodeBlockKind, Event, HeadingLevel, Options, Parser, Tag, TagEnd};
16
17/// Which way a table column's cells are set.
18#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
19pub enum CellAlign {
20    #[default]
21    Start,
22    Center,
23    End,
24}
25
26/// A run of content inside one line of prose.
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub enum Inline {
29    Text(SharedString),
30    /// Backticked text, set in the mono face and never highlighted.
31    Code(SharedString),
32    Emphasis(Vec<Inline>),
33    Strong(Vec<Inline>),
34    Struck(Vec<Inline>),
35    Link {
36        href: SharedString,
37        title: Option<SharedString>,
38        content: Vec<Inline>,
39    },
40    Image {
41        src: SharedString,
42        alt: SharedString,
43        title: Option<SharedString>,
44    },
45    /// HTML written inside a line, kept verbatim and never interpreted.
46    Html(SharedString),
47    SoftBreak,
48    HardBreak,
49}
50
51/// One entry of a bulleted or numbered list.
52#[derive(Debug, Clone, PartialEq, Eq, Default)]
53pub struct ListEntry {
54    /// `Some` when the entry carried a task marker, and whether it was ticked.
55    pub task: Option<bool>,
56    pub blocks: Vec<Block>,
57}
58
59/// One block of a document.
60#[derive(Debug, Clone, PartialEq, Eq)]
61pub enum Block {
62    Heading {
63        level: u8,
64        content: Vec<Inline>,
65    },
66    Paragraph(Vec<Inline>),
67    Code {
68        /// The fence's info string, exactly as it was written.
69        language: Option<SharedString>,
70        text: SharedString,
71    },
72    Quote(Vec<Block>),
73    List {
74        ordered: bool,
75        start: u64,
76        entries: Vec<ListEntry>,
77    },
78    Rule,
79    Table {
80        alignment: Vec<CellAlign>,
81        head: Vec<Vec<Inline>>,
82        rows: Vec<Vec<Vec<Inline>>>,
83    },
84    /// An HTML block, kept verbatim and never interpreted.
85    Html(SharedString),
86}
87
88impl Block {
89    /// How many lines this block occupies, counted the way truncation counts.
90    ///
91    /// A line here is a line of the document's own structure — a heading, a
92    /// paragraph, one line of a code fence, one list entry — not a line of
93    /// wrapped text, whose count only layout knows.
94    pub fn lines(&self) -> usize {
95        match self {
96            Self::Heading { .. } | Self::Paragraph(_) | Self::Rule => 1,
97            Self::Code { text, .. } | Self::Html(text) => text.lines().count().max(1),
98            Self::Quote(blocks) => blocks.iter().map(Block::lines).sum::<usize>().max(1),
99            Self::List { entries, .. } => entries.iter().map(ListEntry::lines).sum(),
100            Self::Table { rows, .. } => 1 + rows.len(),
101        }
102    }
103
104    /// The first `room` lines of this block, when it can be cut at all.
105    ///
106    /// Only blocks that are lists of lines can be cut. A table split across
107    /// its header, or a paragraph split mid-sentence, would say something the
108    /// document does not.
109    fn head(&self, room: usize) -> Option<Self> {
110        if room == 0 {
111            return None;
112        }
113        match self {
114            Self::Code { language, text } => {
115                let kept: Vec<&str> = text.lines().take(room).collect();
116                Some(Self::Code {
117                    language: language.clone(),
118                    text: SharedString::from(kept.join("\n")),
119                })
120            }
121            Self::Html(text) => {
122                let kept: Vec<&str> = text.lines().take(room).collect();
123                Some(Self::Html(SharedString::from(kept.join("\n"))))
124            }
125            Self::List {
126                ordered,
127                start,
128                entries,
129            } => {
130                let mut kept = Vec::new();
131                let mut used = 0;
132                for entry in entries {
133                    let lines = entry.lines();
134                    if used + lines > room {
135                        break;
136                    }
137                    used += lines;
138                    kept.push(entry.clone());
139                }
140                if kept.is_empty() {
141                    None
142                } else {
143                    Some(Self::List {
144                        ordered: *ordered,
145                        start: *start,
146                        entries: kept,
147                    })
148                }
149            }
150            _ => None,
151        }
152    }
153}
154
155impl ListEntry {
156    fn lines(&self) -> usize {
157        self.blocks.iter().map(Block::lines).sum::<usize>().max(1)
158    }
159}
160
161/// A parsed document.
162#[derive(Debug, Clone, PartialEq, Eq, Default)]
163pub struct Document {
164    pub blocks: Vec<Block>,
165}
166
167impl Document {
168    /// Parses `source` with tables, strikethrough, and task lists enabled.
169    ///
170    /// Nothing else is enabled: footnotes, smart punctuation, and math would
171    /// each change what a plain document means, and a reader who wrote three
172    /// dots did not ask for an ellipsis.
173    pub fn parse(source: &str) -> Self {
174        let mut options = Options::empty();
175        options.insert(Options::ENABLE_TABLES);
176        options.insert(Options::ENABLE_STRIKETHROUGH);
177        options.insert(Options::ENABLE_TASKLISTS);
178        build(Parser::new_ext(source, options))
179    }
180
181    pub fn lines(&self) -> usize {
182        self.blocks.iter().map(Block::lines).sum()
183    }
184
185    /// The first `max` lines, and how many lines were left behind.
186    ///
187    /// The count is the point. A document cut to fit says how much was cut, so
188    /// a reader knows there is more rather than having to notice a fade.
189    pub fn truncate(&self, max: usize) -> (Self, usize) {
190        let total = self.lines();
191        if total <= max {
192            return (self.clone(), 0);
193        }
194        let mut blocks = Vec::new();
195        let mut kept = 0;
196        for block in &self.blocks {
197            let lines = block.lines();
198            if kept + lines <= max {
199                kept += lines;
200                blocks.push(block.clone());
201                continue;
202            }
203            if let Some(part) = block.head(max - kept) {
204                kept += part.lines();
205                blocks.push(part);
206            }
207            break;
208        }
209        (Self { blocks }, total.saturating_sub(kept))
210    }
211}
212
213/// What the walker is currently inside.
214#[derive(Debug)]
215enum Frame {
216    Root,
217    Paragraph,
218    Heading(u8),
219    Quote,
220    List {
221        ordered: bool,
222        start: u64,
223        entries: Vec<ListEntry>,
224    },
225    Entry {
226        task: Option<bool>,
227    },
228    Code {
229        language: Option<SharedString>,
230    },
231    Html,
232    Table {
233        alignment: Vec<CellAlign>,
234        head: Vec<Vec<Inline>>,
235        rows: Vec<Vec<Vec<Inline>>>,
236    },
237    /// A row, and whether it is the header row.
238    Row {
239        heading: bool,
240        cells: Vec<Vec<Inline>>,
241    },
242    Cell,
243    Emphasis,
244    Strong,
245    Struck,
246    Link {
247        href: SharedString,
248        title: Option<SharedString>,
249    },
250    Image {
251        src: SharedString,
252        title: Option<SharedString>,
253    },
254    /// A container this renderer has no separate shape for, whose contents
255    /// still belong in the document.
256    Transparent,
257}
258
259/// What has accumulated inside one frame.
260#[derive(Debug, Default)]
261struct Level {
262    blocks: Vec<Block>,
263    inlines: Vec<Inline>,
264    text: String,
265}
266
267fn build<'a>(events: impl Iterator<Item = Event<'a>>) -> Document {
268    let mut stack: Vec<(Frame, Level)> = vec![(Frame::Root, Level::default())];
269
270    for event in events {
271        match event {
272            Event::Start(tag) => stack.push((frame(tag), Level::default())),
273            Event::End(end) => close(&mut stack, end),
274            Event::Text(text) => push_text(&mut stack, text.as_ref()),
275            Event::Code(code) => push_inline(&mut stack, Inline::Code(code.as_ref().into())),
276            Event::Html(html) | Event::InlineHtml(html) => push_html(&mut stack, html.as_ref()),
277            Event::SoftBreak => push_inline(&mut stack, Inline::SoftBreak),
278            Event::HardBreak => push_inline(&mut stack, Inline::HardBreak),
279            Event::Rule => push_block(&mut stack, Block::Rule),
280            Event::TaskListMarker(checked) => mark_task(&mut stack, checked),
281            // Footnotes and math are not enabled, so they never arrive; a
282            // reference in the source stays the literal text it was written as.
283            _ => {}
284        }
285    }
286
287    let mut root = stack.remove(0).1;
288    flush_paragraph(&mut root);
289    Document {
290        blocks: root.blocks,
291    }
292}
293
294fn frame(tag: Tag<'_>) -> Frame {
295    match tag {
296        Tag::Paragraph => Frame::Paragraph,
297        Tag::Heading { level, .. } => Frame::Heading(match level {
298            HeadingLevel::H1 => 1,
299            HeadingLevel::H2 => 2,
300            HeadingLevel::H3 => 3,
301            HeadingLevel::H4 => 4,
302            HeadingLevel::H5 => 5,
303            HeadingLevel::H6 => 6,
304        }),
305        Tag::BlockQuote(_) => Frame::Quote,
306        Tag::CodeBlock(kind) => Frame::Code {
307            language: match kind {
308                CodeBlockKind::Fenced(info) => {
309                    let info = info.trim();
310                    (!info.is_empty()).then(|| SharedString::from(info.to_string()))
311                }
312                CodeBlockKind::Indented => None,
313            },
314        },
315        Tag::HtmlBlock => Frame::Html,
316        Tag::List(start) => Frame::List {
317            ordered: start.is_some(),
318            start: start.unwrap_or(1),
319            entries: Vec::new(),
320        },
321        Tag::Item => Frame::Entry { task: None },
322        Tag::Table(alignment) => Frame::Table {
323            alignment: alignment
324                .into_iter()
325                .map(|align| match align {
326                    pulldown_cmark::Alignment::Center => CellAlign::Center,
327                    pulldown_cmark::Alignment::Right => CellAlign::End,
328                    _ => CellAlign::Start,
329                })
330                .collect(),
331            head: Vec::new(),
332            rows: Vec::new(),
333        },
334        Tag::TableHead => Frame::Row {
335            heading: true,
336            cells: Vec::new(),
337        },
338        Tag::TableRow => Frame::Row {
339            heading: false,
340            cells: Vec::new(),
341        },
342        Tag::TableCell => Frame::Cell,
343        Tag::Emphasis => Frame::Emphasis,
344        Tag::Strong => Frame::Strong,
345        Tag::Strikethrough => Frame::Struck,
346        Tag::Link {
347            dest_url, title, ..
348        } => Frame::Link {
349            href: dest_url.as_ref().into(),
350            title: optional(title.as_ref()),
351        },
352        Tag::Image {
353            dest_url, title, ..
354        } => Frame::Image {
355            src: dest_url.as_ref().into(),
356            title: optional(title.as_ref()),
357        },
358        _ => Frame::Transparent,
359    }
360}
361
362fn optional(text: &str) -> Option<SharedString> {
363    (!text.is_empty()).then(|| SharedString::from(text.to_string()))
364}
365
366/// Closes the innermost frame and folds it into the one around it.
367///
368/// The stream is well formed, so the popped frame decides the fold; `end` only
369/// guards against unwinding past the root.
370fn close(stack: &mut Vec<(Frame, Level)>, end: TagEnd) {
371    if stack.len() < 2 {
372        debug_assert!(false, "markdown stream closed `{end:?}` past its root");
373        return;
374    }
375    let Some((frame, mut level)) = stack.pop() else {
376        return;
377    };
378    let Some((parent_frame, parent)) = stack.last_mut() else {
379        return;
380    };
381
382    match frame {
383        Frame::Paragraph => {
384            if !level.inlines.is_empty() {
385                add_block(parent, Block::Paragraph(level.inlines));
386            }
387        }
388        Frame::Heading(heading) => add_block(
389            parent,
390            Block::Heading {
391                level: heading,
392                content: level.inlines,
393            },
394        ),
395        Frame::Quote => add_block(parent, Block::Quote(level.blocks)),
396        Frame::Code { language } => add_block(
397            parent,
398            Block::Code {
399                language,
400                text: SharedString::from(level.text.trim_end_matches('\n').to_string()),
401            },
402        ),
403        Frame::Html => {
404            let text = level.text.trim_end_matches('\n').to_string();
405            if !text.is_empty() {
406                add_block(parent, Block::Html(SharedString::from(text)));
407            }
408        }
409        Frame::List {
410            ordered,
411            start,
412            entries,
413        } => add_block(
414            parent,
415            Block::List {
416                ordered,
417                start,
418                entries,
419            },
420        ),
421        Frame::Entry { task } => {
422            flush_paragraph(&mut level);
423            if let Frame::List { entries, .. } = parent_frame {
424                entries.push(ListEntry {
425                    task,
426                    blocks: level.blocks,
427                });
428            }
429        }
430        Frame::Table {
431            alignment,
432            head,
433            rows,
434        } => add_block(
435            parent,
436            Block::Table {
437                alignment,
438                head,
439                rows,
440            },
441        ),
442        Frame::Row { heading, cells } => {
443            if let Frame::Table { head, rows, .. } = parent_frame {
444                if heading {
445                    *head = cells;
446                } else {
447                    rows.push(cells);
448                }
449            }
450        }
451        Frame::Cell => {
452            if let Frame::Row { cells, .. } = parent_frame {
453                cells.push(level.inlines);
454            }
455        }
456        Frame::Emphasis => parent.inlines.push(Inline::Emphasis(level.inlines)),
457        Frame::Strong => parent.inlines.push(Inline::Strong(level.inlines)),
458        Frame::Struck => parent.inlines.push(Inline::Struck(level.inlines)),
459        Frame::Link { href, title } => parent.inlines.push(Inline::Link {
460            href,
461            title,
462            content: level.inlines,
463        }),
464        Frame::Image { src, title } => parent.inlines.push(Inline::Image {
465            src,
466            alt: SharedString::from(level.text),
467            title,
468        }),
469        Frame::Root | Frame::Transparent => {
470            if !level.blocks.is_empty() {
471                flush_paragraph(parent);
472            }
473            parent.blocks.append(&mut level.blocks);
474            parent.inlines.append(&mut level.inlines);
475        }
476    }
477}
478
479/// Adds a block to a level, closing whatever prose was already open there.
480///
481/// A tight list entry's own text arrives as bare inlines, and a nested list
482/// arrives as a block, so a level can hold both at once. Flushing first keeps
483/// them in the order they were written; flushing at the end of the entry would
484/// print the entry's text after its own sublist.
485fn add_block(level: &mut Level, block: Block) {
486    flush_paragraph(level);
487    level.blocks.push(block);
488}
489
490/// Turns inlines stranded outside a paragraph — a loose list entry — into one.
491fn flush_paragraph(level: &mut Level) {
492    if !level.inlines.is_empty() {
493        let inlines = std::mem::take(&mut level.inlines);
494        level.blocks.push(Block::Paragraph(inlines));
495    }
496}
497
498fn push_text(stack: &mut [(Frame, Level)], text: &str) {
499    let Some((frame, level)) = stack.last_mut() else {
500        return;
501    };
502    match frame {
503        // A code fence's body and an image's alt text are strings, not prose.
504        Frame::Code { .. } | Frame::Html | Frame::Image { .. } => level.text.push_str(text),
505        _ => level.inlines.push(Inline::Text(text.into())),
506    }
507}
508
509fn push_html(stack: &mut [(Frame, Level)], html: &str) {
510    let Some((frame, level)) = stack.last_mut() else {
511        return;
512    };
513    match frame {
514        Frame::Html => level.text.push_str(html),
515        // Outside an HTML block the fragment sits in a line of prose, so it
516        // stays in that line rather than breaking the paragraph in two.
517        Frame::Paragraph
518        | Frame::Heading(_)
519        | Frame::Emphasis
520        | Frame::Strong
521        | Frame::Struck
522        | Frame::Link { .. }
523        | Frame::Cell => level.inlines.push(Inline::Html(html.into())),
524        _ => level
525            .blocks
526            .push(Block::Html(SharedString::from(html.trim_end().to_string()))),
527    }
528}
529
530fn push_inline(stack: &mut [(Frame, Level)], inline: Inline) {
531    if let Some((_, level)) = stack.last_mut() {
532        level.inlines.push(inline);
533    }
534}
535
536fn push_block(stack: &mut [(Frame, Level)], block: Block) {
537    if let Some((_, level)) = stack.last_mut() {
538        add_block(level, block);
539    }
540}
541
542fn mark_task(stack: &mut [(Frame, Level)], checked: bool) {
543    for (frame, _) in stack.iter_mut().rev() {
544        if let Frame::Entry { task } = frame {
545            *task = Some(checked);
546            return;
547        }
548    }
549}
550
551#[cfg(test)]
552mod tests {
553    use super::*;
554
555    fn blocks(source: &str) -> Vec<Block> {
556        Document::parse(source).blocks
557    }
558
559    fn plain(inlines: &[Inline]) -> String {
560        inlines
561            .iter()
562            .map(|inline| match inline {
563                Inline::Text(text) | Inline::Code(text) | Inline::Html(text) => text.to_string(),
564                Inline::Emphasis(inner) | Inline::Strong(inner) | Inline::Struck(inner) => {
565                    plain(inner)
566                }
567                Inline::Link { content, .. } => plain(content),
568                Inline::Image { alt, .. } => alt.to_string(),
569                Inline::SoftBreak | Inline::HardBreak => " ".into(),
570            })
571            .collect()
572    }
573
574    #[test]
575    fn every_block_kind_reaches_the_tree() {
576        let document = Document::parse(
577            "# Title\n\nA paragraph.\n\n> Quoted\n\n```rust\nfn main() {}\n```\n\n\
578             - one\n- two\n\n1. first\n\n---\n\n| a | b |\n|---|---|\n| 1 | 2 |\n",
579        );
580        let kinds: Vec<&str> = document
581            .blocks
582            .iter()
583            .map(|block| match block {
584                Block::Heading { .. } => "heading",
585                Block::Paragraph(_) => "paragraph",
586                Block::Code { .. } => "code",
587                Block::Quote(_) => "quote",
588                Block::List { ordered: true, .. } => "ordered",
589                Block::List { .. } => "bullets",
590                Block::Rule => "rule",
591                Block::Table { .. } => "table",
592                Block::Html(_) => "html",
593            })
594            .collect();
595        assert_eq!(
596            kinds,
597            vec![
598                "heading",
599                "paragraph",
600                "quote",
601                "code",
602                "bullets",
603                "ordered",
604                "rule",
605                "table"
606            ]
607        );
608    }
609
610    #[test]
611    fn a_fences_info_string_is_kept_as_written() {
612        let Some(Block::Code { language, text }) = blocks("```rust,no_run\nlet x = 1;\n```").pop()
613        else {
614            panic!("expected a code block");
615        };
616        assert_eq!(language.as_deref(), Some("rust,no_run"));
617        assert_eq!(text.as_ref(), "let x = 1;");
618    }
619
620    #[test]
621    fn an_indented_block_claims_no_language() {
622        let Some(Block::Code { language, .. }) = blocks("    indented\n").pop() else {
623            panic!("expected a code block");
624        };
625        assert_eq!(language, None);
626    }
627
628    #[test]
629    fn raw_html_survives_parsing_as_literal_text() {
630        let document = Document::parse("<div onclick=\"go()\">hidden</div>\n");
631        assert_eq!(
632            document.blocks,
633            vec![Block::Html("<div onclick=\"go()\">hidden</div>".into())]
634        );
635    }
636
637    #[test]
638    fn inline_html_stays_inside_its_line() {
639        let Some(Block::Paragraph(inlines)) = blocks("before <b>bold</b> after").pop() else {
640            panic!("expected a paragraph");
641        };
642        assert!(
643            inlines
644                .iter()
645                .any(|inline| matches!(inline, Inline::Html(html) if html.as_ref() == "<b>")),
646            "the tag itself must survive: {inlines:?}"
647        );
648        assert!(plain(&inlines).contains("bold"));
649    }
650
651    #[test]
652    fn nested_lists_keep_their_nesting() {
653        let Some(Block::List { entries, .. }) = blocks("- outer\n  - inner\n").pop() else {
654            panic!("expected a list");
655        };
656        assert_eq!(entries.len(), 1);
657        assert!(
658            entries[0]
659                .blocks
660                .iter()
661                .any(|block| matches!(block, Block::List { .. })),
662            "the inner list must stay inside its entry"
663        );
664    }
665
666    #[test]
667    fn a_list_entry_is_read_before_the_list_beneath_it() {
668        let Some(Block::List { entries, .. }) = blocks("- outer\n  - inner\n").pop() else {
669            panic!("expected a list");
670        };
671        let Some(Block::Paragraph(inlines)) = entries[0].blocks.first() else {
672            panic!("the entry's own words come first: {:?}", entries[0].blocks);
673        };
674        assert_eq!(plain(inlines).trim(), "outer");
675        assert!(matches!(entries[0].blocks.get(1), Some(Block::List { .. })));
676    }
677
678    #[test]
679    fn a_task_marker_is_carried_by_its_entry() {
680        let Some(Block::List { entries, .. }) = blocks("- [x] done\n- [ ] open\n").pop() else {
681            panic!("expected a list");
682        };
683        assert_eq!(
684            entries.iter().map(|entry| entry.task).collect::<Vec<_>>(),
685            vec![Some(true), Some(false)]
686        );
687    }
688
689    #[test]
690    fn a_links_destination_and_an_images_source_are_kept_apart() {
691        let Some(Block::Paragraph(inlines)) =
692            blocks("[docs](https://example.test/a) ![a cat](cat.png)").pop()
693        else {
694            panic!("expected a paragraph");
695        };
696        assert!(inlines.iter().any(|inline| matches!(
697            inline,
698            Inline::Link { href, .. } if href.as_ref() == "https://example.test/a"
699        )));
700        assert!(inlines.iter().any(|inline| matches!(
701            inline,
702            Inline::Image { src, alt, .. } if src.as_ref() == "cat.png" && alt.as_ref() == "a cat"
703        )));
704    }
705
706    #[test]
707    fn a_table_keeps_its_header_apart_from_its_rows() {
708        let Some(Block::Table {
709            alignment,
710            head,
711            rows,
712        }) = blocks("| a | b |\n|:--|--:|\n| 1 | 2 |\n| 3 | 4 |\n").pop()
713        else {
714            panic!("expected a table");
715        };
716        assert_eq!(alignment, vec![CellAlign::Start, CellAlign::End]);
717        assert_eq!(head.len(), 2);
718        assert_eq!(rows.len(), 2);
719        assert_eq!(plain(&rows[1][1]), "4");
720    }
721
722    #[test]
723    fn lines_count_the_documents_own_structure() {
724        let document = Document::parse("# Title\n\n```\na\nb\nc\n```\n\n- one\n- two\n");
725        assert_eq!(document.lines(), 1 + 3 + 2);
726    }
727
728    #[test]
729    fn truncation_reports_exactly_what_it_left_behind() {
730        let document = Document::parse("# Title\n\n```\na\nb\nc\nd\n```\n");
731        let (short, hidden) = document.truncate(3);
732        assert_eq!(hidden, 2);
733        assert_eq!(short.lines(), 3);
734        let Some(Block::Code { text, .. }) = short.blocks.last() else {
735            panic!("the code block must survive, shortened");
736        };
737        assert_eq!(text.as_ref(), "a\nb");
738    }
739
740    #[test]
741    fn a_document_that_fits_is_not_truncated_and_hides_nothing() {
742        let document = Document::parse("one\n\ntwo\n");
743        let (kept, hidden) = document.truncate(10);
744        assert_eq!(hidden, 0);
745        assert_eq!(kept, document);
746    }
747
748    #[test]
749    fn an_uncuttable_block_is_left_out_whole_rather_than_split() {
750        let document = Document::parse("| a |\n|---|\n| 1 |\n| 2 |\n\ntail\n");
751        let (short, hidden) = document.truncate(1);
752        assert!(short.blocks.is_empty(), "{short:?}");
753        assert_eq!(hidden, document.lines());
754    }
755}