Skip to main content

markdown_model/
parse.rs

1use crate::model::*;
2use pulldown_cmark::{CodeBlockKind as ParsedCodeBlockKind, Event, Options, Parser, Tag};
3use std::{collections::HashSet, fmt, ops::Range};
4
5/// Resource bounds checked while parsing a document.
6///
7/// All limits are inclusive: a source whose byte length equals the byte limit
8/// is accepted, as is a parser stream with exactly the event limit. A zero
9/// value rejects any input that consumes that resource. Nesting values above
10/// [`ParseLimits::MAX_NESTING_DEPTH`] are capped during construction.
11#[derive(Clone, Copy, Debug, PartialEq, Eq)]
12pub struct ParseLimits {
13    max_source_bytes: usize,
14    max_nesting_depth: usize,
15    max_events: usize,
16}
17impl ParseLimits {
18    /// The parser's absolute nesting ceiling.
19    pub const MAX_NESTING_DEPTH: usize = 128;
20
21    /// Creates a complete resource budget.
22    pub const fn new(max_source_bytes: usize, max_nesting_depth: usize, max_events: usize) -> Self {
23        Self {
24            max_source_bytes,
25            max_nesting_depth: if max_nesting_depth > Self::MAX_NESTING_DEPTH {
26                Self::MAX_NESTING_DEPTH
27            } else {
28                max_nesting_depth
29            },
30            max_events,
31        }
32    }
33
34    /// Returns the maximum accepted UTF-8 source size in bytes.
35    pub const fn max_source_bytes(self) -> usize {
36        self.max_source_bytes
37    }
38
39    /// Returns the effective maximum parser-container depth.
40    pub const fn max_nesting_depth(self) -> usize {
41        self.max_nesting_depth
42    }
43
44    /// Returns the maximum accepted parser-event count.
45    pub const fn max_events(self) -> usize {
46        self.max_events
47    }
48
49    /// Replaces the source byte limit.
50    pub const fn with_max_source_bytes(mut self, bytes: usize) -> Self {
51        self.max_source_bytes = bytes;
52        self
53    }
54
55    /// Replaces the nesting limit, capped at
56    /// [`ParseLimits::MAX_NESTING_DEPTH`].
57    pub const fn with_max_nesting_depth(mut self, depth: usize) -> Self {
58        self.max_nesting_depth = if depth > Self::MAX_NESTING_DEPTH {
59            Self::MAX_NESTING_DEPTH
60        } else {
61            depth
62        };
63        self
64    }
65
66    /// Replaces the parser-event limit.
67    pub const fn with_max_events(mut self, events: usize) -> Self {
68        self.max_events = events;
69        self
70    }
71}
72impl Default for ParseLimits {
73    fn default() -> Self {
74        Self::new(2 * 1024 * 1024, 64, 200_000)
75    }
76}
77/// Resource exhaustion, rather than incomplete Markdown syntax, makes parsing fail.
78#[derive(Clone, Debug, PartialEq, Eq)]
79pub enum ParseError {
80    /// Source exceeded the configured byte limit.
81    TooLarge {
82        /// Actual UTF-8 byte length of the source.
83        bytes: usize,
84        /// Configured byte limit.
85        limit: usize,
86    },
87    /// Nested containers exceeded the effective depth limit.
88    TooDeep {
89        /// Effective nesting limit, including the hard cap of 128.
90        limit: usize,
91    },
92    /// Too many parser events for the configured budget.
93    TooComplex {
94        /// Configured parser-event limit.
95        limit: usize,
96    },
97}
98impl fmt::Display for ParseError {
99    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
100        match self {
101            Self::TooLarge { bytes, limit } => {
102                write!(f, "document is {bytes} bytes; limit is {limit}")
103            }
104            Self::TooDeep { limit } => write!(f, "document nesting exceeds {limit}"),
105            Self::TooComplex { limit } => write!(f, "document exceeds {limit} parser events"),
106        }
107    }
108}
109impl std::error::Error for ParseError {}
110
111struct Node<'a> {
112    event: Event<'a>,
113    range: Range<usize>,
114    children: Vec<Node<'a>>,
115}
116struct Builder {
117    document: Document,
118    anchors: HashSet<String>,
119}
120
121impl Document {
122    /// Parses CommonMark with tables, task lists, and strikethrough enabled.
123    ///
124    /// Parsing is synchronous, performs no I/O, and returns an owned document
125    /// that does not borrow `source`. Incomplete syntax follows
126    /// pulldown-cmark's literal fallback rules.
127    ///
128    /// # Errors
129    /// Returns [`ParseError`] if the default resource limits are exceeded.
130    pub fn parse(source: &str) -> Result<Self, ParseError> {
131        Self::parse_with_limits(source, ParseLimits::default())
132    }
133    /// Parses with caller-supplied resource bounds.
134    ///
135    /// The same Markdown extensions and ownership rules as [`Document::parse`]
136    /// apply. See [`ParseLimits`] for boundary semantics.
137    ///
138    /// # Errors
139    /// Returns [`ParseError`] when any bound is exceeded.
140    pub fn parse_with_limits(source: &str, limits: ParseLimits) -> Result<Self, ParseError> {
141        if source.len() > limits.max_source_bytes() {
142            return Err(ParseError::TooLarge {
143                bytes: source.len(),
144                limit: limits.max_source_bytes(),
145            });
146        }
147        let options =
148            Options::ENABLE_TABLES | Options::ENABLE_TASKLISTS | Options::ENABLE_STRIKETHROUGH;
149        let mut stack: Vec<Node<'_>> = Vec::new();
150        let mut nodes = Vec::new();
151        for (count, (event, range)) in Parser::new_ext(source, options)
152            .into_offset_iter()
153            .enumerate()
154        {
155            if count >= limits.max_events() {
156                return Err(ParseError::TooComplex {
157                    limit: limits.max_events(),
158                });
159            }
160            if matches!(event, Event::Start(_)) {
161                if stack.len() >= limits.max_nesting_depth() {
162                    return Err(ParseError::TooDeep {
163                        limit: limits.max_nesting_depth(),
164                    });
165                }
166                stack.push(Node {
167                    event,
168                    range,
169                    children: Vec::new(),
170                });
171                continue;
172            }
173            let node = if matches!(event, Event::End(_)) {
174                let mut node = stack.pop().expect("parser start/end events are balanced");
175                node.range.end = node.range.end.max(range.end);
176                node
177            } else {
178                Node {
179                    event,
180                    range,
181                    children: Vec::new(),
182                }
183            };
184            if let Some(parent) = stack.last_mut() {
185                parent.children.push(node);
186            } else {
187                nodes.push(node);
188            }
189        }
190        let mut builder = Builder {
191            document: Document {
192                blocks: Vec::new(),
193                headings: Vec::new(),
194                links: Vec::new(),
195            },
196            anchors: HashSet::new(),
197        };
198        builder.document.blocks = builder.blocks(&nodes);
199        Ok(builder.document)
200    }
201}
202
203impl Builder {
204    fn blocks(&mut self, nodes: &[Node<'_>]) -> Vec<Block> {
205        let mut out = Vec::new();
206        let mut pending = Vec::new();
207        for node in nodes {
208            let kind = match &node.event {
209                Event::Start(Tag::Paragraph) => {
210                    Some(BlockKind::Paragraph(self.inlines(&node.children)))
211                }
212                Event::Start(Tag::Heading { level, .. }) => {
213                    let content = self.inlines(&node.children);
214                    let text = plain_text(&content);
215                    let slug = slug(&text);
216                    let mut id = slug.clone();
217                    let mut suffix = 0;
218                    while !self.anchors.insert(id.clone()) {
219                        suffix += 1;
220                        id = format!("{slug}-{suffix}");
221                    }
222                    let id = HeadingId::from_generated(id);
223                    let level = heading_level(*level);
224                    self.document.headings.push(Heading {
225                        id: id.clone(),
226                        level,
227                        text,
228                        span: SourceSpan::from_range(node.range.clone()),
229                    });
230                    Some(BlockKind::Heading { level, id, content })
231                }
232                Event::Start(Tag::BlockQuote(_)) => {
233                    Some(BlockKind::Quote(self.blocks(&node.children)))
234                }
235                Event::Start(Tag::List(start)) => Some(BlockKind::List {
236                    kind: start.map_or(ListKind::Unordered, |start| ListKind::Ordered { start }),
237                    items: node
238                        .children
239                        .iter()
240                        .map(|item| ListItem {
241                            task: task_marker(item),
242                            blocks: self.blocks(&item.children),
243                        })
244                        .collect(),
245                }),
246                Event::Start(Tag::CodeBlock(kind)) => Some(BlockKind::Code {
247                    kind: match kind {
248                        ParsedCodeBlockKind::Fenced(info) => {
249                            CodeBlockKind::Fenced(info.to_string())
250                        }
251                        ParsedCodeBlockKind::Indented => CodeBlockKind::Indented,
252                    },
253                    text: literal(node),
254                }),
255                Event::Start(Tag::HtmlBlock) => Some(BlockKind::Literal(literal(node))),
256                Event::Start(Tag::Table(align)) => {
257                    let mut header = TableRow::from_cells(Vec::new());
258                    let mut rows = Vec::new();
259                    for row in &node.children {
260                        let cells = TableRow::from_cells(
261                            row.children
262                                .iter()
263                                .map(|cell| TableCell::from_inlines(self.inlines(&cell.children)))
264                                .collect(),
265                        );
266                        if matches!(row.event, Event::Start(Tag::TableHead)) {
267                            header = cells;
268                        } else {
269                            rows.push(cells);
270                        }
271                    }
272                    Some(BlockKind::Table(Table::new(
273                        align
274                            .iter()
275                            .map(|a| match a {
276                                pulldown_cmark::Alignment::None => Alignment::None,
277                                pulldown_cmark::Alignment::Left => Alignment::Left,
278                                pulldown_cmark::Alignment::Center => Alignment::Center,
279                                pulldown_cmark::Alignment::Right => Alignment::Right,
280                            })
281                            .collect(),
282                        header,
283                        rows,
284                    )))
285                }
286                Event::Rule => Some(BlockKind::Rule),
287                _ => None,
288            };
289            if let Some(kind) = kind {
290                flush(&mut pending, &mut out);
291                out.push(Block {
292                    kind,
293                    span: SourceSpan::from_range(node.range.clone()),
294                });
295            } else {
296                pending.extend(self.inlines(std::slice::from_ref(node)));
297            }
298        }
299        flush(&mut pending, &mut out);
300        out
301    }
302    fn inlines(&mut self, nodes: &[Node<'_>]) -> Vec<Inline> {
303        nodes
304            .iter()
305            .filter_map(|node| {
306                let kind = match &node.event {
307                    Event::Text(s) | Event::Html(s) | Event::InlineHtml(s) => {
308                        InlineKind::Text(s.to_string())
309                    }
310                    Event::Code(s) => InlineKind::Code(s.to_string()),
311                    Event::SoftBreak => InlineKind::SoftBreak,
312                    Event::HardBreak => InlineKind::HardBreak,
313                    Event::Start(Tag::Emphasis) => {
314                        InlineKind::Emphasis(self.inlines(&node.children))
315                    }
316                    Event::Start(Tag::Strong) => InlineKind::Strong(self.inlines(&node.children)),
317                    Event::Start(Tag::Strikethrough) => {
318                        InlineKind::Strikethrough(self.inlines(&node.children))
319                    }
320                    Event::Start(Tag::Link {
321                        dest_url, title, ..
322                    }) => {
323                        let content = self.inlines(&node.children);
324                        let id = LinkId::from_index(self.document.links.len());
325                        self.document.links.push(Link {
326                            id,
327                            destination: LinkDestination::from_parser(dest_url.to_string()),
328                            title: (!title.is_empty()).then(|| title.to_string()),
329                            text: plain_text(&content),
330                            span: SourceSpan::from_range(node.range.clone()),
331                        });
332                        InlineKind::Link { id, content }
333                    }
334                    Event::Start(Tag::Image {
335                        dest_url, title, ..
336                    }) => InlineKind::Image {
337                        destination: LinkDestination::from_parser(dest_url.to_string()),
338                        title: (!title.is_empty()).then(|| title.to_string()),
339                        alt: self.inlines(&node.children),
340                    },
341                    Event::TaskListMarker(_) => return None,
342                    // Extensions not enabled above stay literal in the parser. Retain
343                    // content if a future parser introduces another event/container.
344                    _ => InlineKind::Text(literal(node)),
345                };
346                Some(Inline {
347                    kind,
348                    span: SourceSpan::from_range(node.range.clone()),
349                })
350            })
351            .collect()
352    }
353}
354fn flush(pending: &mut Vec<Inline>, blocks: &mut Vec<Block>) {
355    if let (Some(first), Some(last)) = (pending.first(), pending.last()) {
356        let range = first.span.start()..last.span.end();
357        blocks.push(Block {
358            kind: BlockKind::Paragraph(std::mem::take(pending)),
359            span: SourceSpan::from_range(range),
360        });
361    }
362}
363fn literal(node: &Node<'_>) -> String {
364    match &node.event {
365        Event::Text(s)
366        | Event::Code(s)
367        | Event::Html(s)
368        | Event::InlineHtml(s)
369        | Event::InlineMath(s)
370        | Event::DisplayMath(s)
371        | Event::FootnoteReference(s) => s.to_string(),
372        Event::SoftBreak | Event::HardBreak => "\n".to_owned(),
373        _ => node.children.iter().map(literal).collect(),
374    }
375}
376fn task_marker(node: &Node<'_>) -> TaskState {
377    // A nested task belongs to its own item, never to its parent.
378    for child in &node.children {
379        match child.event {
380            Event::TaskListMarker(true) => return TaskState::Checked,
381            Event::TaskListMarker(false) => return TaskState::Unchecked,
382            Event::Start(Tag::Paragraph) => {
383                let task = task_marker(child);
384                if task != TaskState::Plain {
385                    return task;
386                }
387            }
388            _ => {}
389        }
390    }
391    TaskState::Plain
392}
393fn heading_level(level: pulldown_cmark::HeadingLevel) -> HeadingLevel {
394    match level {
395        pulldown_cmark::HeadingLevel::H1 => HeadingLevel::H1,
396        pulldown_cmark::HeadingLevel::H2 => HeadingLevel::H2,
397        pulldown_cmark::HeadingLevel::H3 => HeadingLevel::H3,
398        pulldown_cmark::HeadingLevel::H4 => HeadingLevel::H4,
399        pulldown_cmark::HeadingLevel::H5 => HeadingLevel::H5,
400        pulldown_cmark::HeadingLevel::H6 => HeadingLevel::H6,
401    }
402}
403fn slug(text: &str) -> String {
404    let mut out = String::new();
405    for c in text.to_lowercase().chars() {
406        if c.is_alphanumeric() || c == '-' || c == '_' {
407            out.push(c);
408        } else if c.is_whitespace() && !out.ends_with('-') {
409            out.push('-');
410        }
411    }
412    let out = out.trim_matches('-');
413    if out.is_empty() {
414        "section".to_owned()
415    } else {
416        out.to_owned()
417    }
418}