Skip to main content

treesearch/parser/
markdown.rs

1//! Parses Markdown headings, body text, front matter, and exact line ranges.
2
3use crate::document::{Document, Node, SourceType};
4use anyhow::Result;
5use pulldown_cmark::{Event, HeadingLevel, Options, Parser as CmarkParser, Tag, TagEnd};
6use std::path::Path;
7
8/// Parser for Markdown (`.md`, `.mdx`, `.markdown`) files.
9///
10/// Builds a hierarchical tree from headings: h2 nests under h1, h3 under h2, etc.
11/// Text between headings becomes the parent heading's body text.
12/// Front-matter (YAML between `---` fences) is captured in the root node's summary.
13/// Code blocks are stored verbatim as part of the enclosing node's text.
14pub struct MarkdownParser;
15
16impl super::Parser for MarkdownParser {
17    fn extensions(&self) -> &[&str] {
18        &["md", "mdx", "markdown"]
19    }
20
21    fn source_type(&self) -> SourceType {
22        SourceType::Markdown
23    }
24
25    fn parse(&self, path: &Path, content: &str) -> Result<Document> {
26        let file_name = path
27            .file_name()
28            .map(|n| n.to_string_lossy().to_string())
29            .unwrap_or_default();
30        let doc_id = path.to_string_lossy().to_string();
31        let mut doc = Document::new(&doc_id, &file_name, SourceType::Markdown);
32
33        if content.trim().is_empty() {
34            doc.assign_node_ids();
35            return Ok(doc);
36        }
37
38        // --- Extract front-matter ---
39        let (front_matter, body) = extract_front_matter(content);
40
41        // --- Parse markdown body ---
42        let opts =
43            Options::ENABLE_TABLES | Options::ENABLE_STRIKETHROUGH | Options::ENABLE_TASKLISTS;
44        let parser = CmarkParser::new_ext(body, opts).into_offset_iter();
45        let line_starts = line_start_offsets(body);
46        let body_byte_offset = content.len().saturating_sub(body.len());
47        let body_line_offset = content[..body_byte_offset]
48            .bytes()
49            .filter(|byte| *byte == b'\n')
50            .count() as u32;
51
52        // Stack of (heading_level, Node).
53        let mut stack: Vec<(u8, Node)> = Vec::new();
54        let mut roots: Vec<Node> = Vec::new();
55
56        let mut in_heading = false;
57        let mut saw_heading = false;
58        let mut heading_title = String::new();
59        let mut heading_line = None;
60        let mut current_text = String::new();
61        let mut current_line_start = None;
62        let mut current_line_end = None;
63        let mut in_code_block = false;
64        let mut code_lang;
65
66        for (event, range) in parser {
67            let event_line_start = body_line_offset + line_number(&line_starts, range.start);
68            let event_line_end = body_line_offset
69                + line_number(&line_starts, range.end.saturating_sub(1).max(range.start));
70            match event {
71                Event::Start(Tag::Heading { level, .. }) => {
72                    flush_text(
73                        &mut stack,
74                        &mut roots,
75                        &mut current_text,
76                        &mut current_line_start,
77                        &mut current_line_end,
78                    );
79                    in_heading = true;
80                    saw_heading = true;
81                    heading_title.clear();
82                    heading_line = Some(event_line_start);
83
84                    let level_num = heading_level_to_u8(level);
85                    collapse_stack(&mut stack, &mut roots, level_num);
86                }
87                Event::End(TagEnd::Heading(level)) => {
88                    in_heading = false;
89                    let level_num = heading_level_to_u8(level);
90                    let mut node = Node::new("", heading_title.trim());
91                    node.line_start = heading_line;
92                    node.line_end = Some(event_line_end);
93                    stack.push((level_num, node));
94                }
95                Event::Start(Tag::CodeBlock(kind)) => {
96                    touch_lines(
97                        &mut current_line_start,
98                        &mut current_line_end,
99                        event_line_start,
100                        event_line_end,
101                    );
102                    in_code_block = true;
103                    code_lang = match kind {
104                        pulldown_cmark::CodeBlockKind::Fenced(lang) => lang.to_string(),
105                        pulldown_cmark::CodeBlockKind::Indented => String::new(),
106                    };
107                    if !code_lang.is_empty() {
108                        current_text.push_str(&format!("\n```{}\n", code_lang));
109                    } else {
110                        current_text.push_str("\n```\n");
111                    }
112                }
113                Event::End(TagEnd::CodeBlock) => {
114                    touch_lines(
115                        &mut current_line_start,
116                        &mut current_line_end,
117                        event_line_start,
118                        event_line_end,
119                    );
120                    in_code_block = false;
121                    current_text.push_str("```\n");
122                }
123                Event::Text(text) => {
124                    if in_heading {
125                        heading_title.push_str(&text);
126                    } else {
127                        touch_lines(
128                            &mut current_line_start,
129                            &mut current_line_end,
130                            event_line_start,
131                            event_line_end,
132                        );
133                        current_text.push_str(&text);
134                    }
135                }
136                Event::Code(code) => {
137                    if in_heading {
138                        heading_title.push('`');
139                        heading_title.push_str(&code);
140                        heading_title.push('`');
141                    } else {
142                        touch_lines(
143                            &mut current_line_start,
144                            &mut current_line_end,
145                            event_line_start,
146                            event_line_end,
147                        );
148                        current_text.push('`');
149                        current_text.push_str(&code);
150                        current_text.push('`');
151                    }
152                }
153                Event::SoftBreak | Event::HardBreak => {
154                    if in_heading {
155                        heading_title.push(' ');
156                    } else {
157                        touch_lines(
158                            &mut current_line_start,
159                            &mut current_line_end,
160                            event_line_start,
161                            event_line_end,
162                        );
163                        current_text.push('\n');
164                    }
165                }
166                Event::End(TagEnd::Paragraph) if !in_code_block => {
167                    current_text.push_str("\n\n");
168                }
169                _ => {}
170            }
171        }
172
173        // Flush remaining text.
174        flush_text(
175            &mut stack,
176            &mut roots,
177            &mut current_text,
178            &mut current_line_start,
179            &mut current_line_end,
180        );
181        // Collapse entire stack.
182        collapse_stack(&mut stack, &mut roots, 0);
183
184        if !saw_heading {
185            if let Some(root) = roots.first_mut() {
186                root.title = file_name.clone();
187            }
188        }
189
190        // Attach front-matter as summary on the first root node.
191        if let Some(fm) = front_matter {
192            if let Some(first) = roots.first_mut() {
193                first.summary = fm;
194            } else {
195                let mut meta = Node::new("", &file_name);
196                meta.summary = fm;
197                roots.push(meta);
198            }
199        }
200
201        // If no headings were found, create a single root from the entire content.
202        if roots.is_empty() && !body.trim().is_empty() {
203            let mut node = Node::new("", &file_name);
204            node.text = body.trim().to_string();
205            node.line_start = Some(1);
206            roots.push(node);
207        }
208
209        doc.structure = roots;
210        doc.assign_node_ids();
211        Ok(doc)
212    }
213}
214
215// ---------------------------------------------------------------------------
216// Helpers
217// ---------------------------------------------------------------------------
218
219/// Pop all stack entries with level >= `target_level`, attaching them as children
220/// of the entry below. If the stack is exhausted, push to roots.
221fn collapse_stack(stack: &mut Vec<(u8, Node)>, roots: &mut Vec<Node>, target_level: u8) {
222    while let Some(&(lvl, _)) = stack.last() {
223        if lvl >= target_level {
224            let (_, node) = stack.pop().unwrap();
225            if let Some(parent) = stack.last_mut() {
226                parent.1.children.push(node);
227            } else {
228                roots.push(node);
229            }
230        } else {
231            break;
232        }
233    }
234}
235
236/// Flush accumulated body text into the top-of-stack node or into roots.
237fn flush_text(
238    stack: &mut [(u8, Node)],
239    roots: &mut Vec<Node>,
240    text: &mut String,
241    line_start: &mut Option<u32>,
242    line_end: &mut Option<u32>,
243) {
244    let trimmed = text.trim().to_string();
245    if trimmed.is_empty() {
246        text.clear();
247        *line_start = None;
248        *line_end = None;
249        return;
250    }
251    if let Some(top) = stack.last_mut() {
252        if top.1.text.is_empty() {
253            top.1.text = trimmed;
254        } else {
255            top.1.text.push_str("\n\n");
256            top.1.text.push_str(&trimmed);
257        }
258        top.1.line_start = top.1.line_start.or(*line_start);
259        top.1.line_end = (*line_end).or(top.1.line_end);
260    } else {
261        // Text before any heading — create an anonymous root node.
262        let mut node = Node::new("", "");
263        node.text = trimmed;
264        node.line_start = *line_start;
265        node.line_end = *line_end;
266        roots.push(node);
267    }
268    text.clear();
269    *line_start = None;
270    *line_end = None;
271}
272
273/// Expands the current direct-text source range with one Markdown event.
274fn touch_lines(
275    current_start: &mut Option<u32>,
276    current_end: &mut Option<u32>,
277    event_start: u32,
278    event_end: u32,
279) {
280    current_start.get_or_insert(event_start);
281    *current_end = Some(event_end.max(current_end.unwrap_or(event_end)));
282}
283
284/// Returns byte offsets for every one-based source line in a UTF-8 body.
285fn line_start_offsets(content: &str) -> Vec<usize> {
286    std::iter::once(0)
287        .chain(
288            content
289                .bytes()
290                .enumerate()
291                .filter_map(|(index, byte)| (byte == b'\n').then_some(index + 1)),
292        )
293        .collect()
294}
295
296/// Maps a byte offset to a one-based source line using binary search.
297fn line_number(line_starts: &[usize], offset: usize) -> u32 {
298    u32::try_from(line_starts.partition_point(|start| *start <= offset)).unwrap_or(u32::MAX)
299}
300
301fn heading_level_to_u8(level: HeadingLevel) -> u8 {
302    match level {
303        HeadingLevel::H1 => 1,
304        HeadingLevel::H2 => 2,
305        HeadingLevel::H3 => 3,
306        HeadingLevel::H4 => 4,
307        HeadingLevel::H5 => 5,
308        HeadingLevel::H6 => 6,
309    }
310}
311
312/// Extract YAML front-matter delimited by `---` at the start of the file.
313/// Returns `(Some(front_matter_content), remaining_body)` or `(None, full_content)`.
314fn extract_front_matter(content: &str) -> (Option<String>, &str) {
315    let trimmed = content.trim_start();
316    let Some(opening_end) = trimmed.find('\n') else {
317        return (None, content);
318    };
319    if trimmed[..opening_end].trim() != "---" {
320        return (None, content);
321    }
322    let rest = &trimmed[opening_end + 1..];
323    let mut offset = 0;
324    for line in rest.split_inclusive('\n') {
325        let raw_line = line.strip_suffix('\n').unwrap_or(line);
326        if raw_line.trim() == "---" {
327            let fm = rest[..offset].trim().to_string();
328            let body = rest[offset + line.len()..].trim_start_matches(['\r', '\n']);
329            return (Some(fm), body);
330        }
331        offset += line.len();
332    }
333    // No exact closing fence — treat entire content as body.
334    (None, content)
335}
336
337#[cfg(test)]
338mod tests {
339    use super::*;
340    use crate::parser::Parser;
341
342    fn parse(content: &str) -> Document {
343        let parser = MarkdownParser;
344        parser
345            .parse(Path::new("test.md"), content)
346            .expect("parse failed")
347    }
348
349    #[test]
350    fn test_empty() {
351        let doc = parse("");
352        assert!(doc.structure.is_empty());
353    }
354
355    #[test]
356    fn test_whitespace_only() {
357        let doc = parse("   \n\n  ");
358        assert!(doc.structure.is_empty());
359    }
360
361    #[test]
362    fn test_single_heading() {
363        let doc = parse("# Hello\n\nWorld paragraph.");
364        assert_eq!(doc.structure.len(), 1);
365        assert_eq!(doc.structure[0].title, "Hello");
366        assert!(doc.structure[0].text.contains("World paragraph"));
367    }
368
369    #[test]
370    fn test_nested_headings() {
371        let content = "# Top\n\nIntro\n\n## Section A\n\nText A\n\n### Sub A1\n\nDeep\n\n## Section B\n\nText B";
372        let doc = parse(content);
373
374        // Should have 1 root (h1).
375        assert_eq!(doc.structure.len(), 1);
376        let root = &doc.structure[0];
377        assert_eq!(root.title, "Top");
378        assert!(root.text.contains("Intro"));
379
380        // Two h2 children.
381        assert_eq!(root.children.len(), 2);
382        assert_eq!(root.children[0].title, "Section A");
383        assert_eq!(root.children[1].title, "Section B");
384
385        // h3 nested under first h2.
386        assert_eq!(root.children[0].children.len(), 1);
387        assert_eq!(root.children[0].children[0].title, "Sub A1");
388    }
389
390    #[test]
391    fn test_front_matter() {
392        let content = "---\ntitle: My Doc\nauthor: Alice\n---\n\n# Hello\n\nBody text";
393        let doc = parse(content);
394        assert_eq!(doc.structure.len(), 1);
395        assert!(doc.structure[0].summary.contains("title: My Doc"));
396        assert!(doc.structure[0].summary.contains("author: Alice"));
397    }
398
399    #[test]
400    fn test_code_block_in_text() {
401        let content = "# Code Example\n\nSome text\n\n```rust\nfn main() {}\n```\n\nMore text";
402        let doc = parse(content);
403        assert_eq!(doc.structure[0].title, "Code Example");
404        assert!(doc.structure[0].text.contains("fn main()"));
405        assert!(doc.structure[0].text.contains("```rust"));
406    }
407
408    #[test]
409    fn test_no_headings() {
410        let content = "Just a plain paragraph.\n\nAnother paragraph.";
411        let doc = parse(content);
412        assert_eq!(doc.structure.len(), 1);
413        assert_eq!(doc.structure[0].title, "test.md");
414        assert!(doc.structure[0].text.contains("Just a plain paragraph"));
415        assert_eq!(doc.structure[0].line_start, Some(1));
416        assert_eq!(doc.structure[0].line_end, Some(3));
417    }
418
419    #[test]
420    fn test_node_ids_assigned() {
421        let content = "# A\n\n## B\n\n## C";
422        let doc = parse(content);
423        assert_eq!(doc.structure[0].node_id, "0");
424        assert_eq!(doc.structure[0].children[0].node_id, "1");
425        assert_eq!(doc.structure[0].children[1].node_id, "2");
426    }
427
428    #[test]
429    fn test_doc_id_and_source_type() {
430        let doc = parse("# Hi");
431        assert_eq!(doc.doc_id, "test.md");
432        assert_eq!(doc.source_type, SourceType::Markdown);
433    }
434
435    #[test]
436    fn test_multiple_h1() {
437        let content = "# First\n\nText1\n\n# Second\n\nText2";
438        let doc = parse(content);
439        assert_eq!(doc.structure.len(), 2);
440        assert_eq!(doc.structure[0].title, "First");
441        assert_eq!(doc.structure[1].title, "Second");
442    }
443
444    #[test]
445    fn test_text_before_heading() {
446        let content = "Some intro text.\n\n# Title\n\nBody";
447        let doc = parse(content);
448        // Should have 2 roots: anonymous text node + heading node.
449        assert_eq!(doc.structure.len(), 2);
450        assert!(doc.structure[0].text.contains("Some intro text"));
451        assert_eq!(doc.structure[1].title, "Title");
452    }
453
454    #[test]
455    fn test_inline_code_in_heading() {
456        let content = "# The `foo` function\n\nDetails here.";
457        let doc = parse(content);
458        assert_eq!(doc.structure[0].title, "The `foo` function");
459    }
460
461    #[test]
462    fn test_extract_front_matter_no_fence() {
463        let (fm, body) = extract_front_matter("Hello world");
464        assert!(fm.is_none());
465        assert_eq!(body, "Hello world");
466    }
467
468    #[test]
469    fn test_extract_front_matter_unclosed() {
470        let (fm, body) = extract_front_matter("---\ntitle: x\nno close");
471        assert!(fm.is_none());
472        assert_eq!(body, "---\ntitle: x\nno close");
473    }
474
475    #[test]
476    fn test_deep_nesting_h1_to_h4() {
477        let content = "# H1\n\n## H2\n\n### H3\n\n#### H4\n\nDeep";
478        let doc = parse(content);
479        let h1 = &doc.structure[0];
480        assert_eq!(h1.children.len(), 1);
481        let h2 = &h1.children[0];
482        assert_eq!(h2.children.len(), 1);
483        let h3 = &h2.children[0];
484        assert_eq!(h3.children.len(), 1);
485        let h4 = &h3.children[0];
486        assert_eq!(h4.title, "H4");
487        assert!(h4.text.contains("Deep"));
488    }
489
490    #[test]
491    fn test_heading_and_body_line_ranges_include_front_matter_offset() {
492        let content = "---\ntitle: Test\n---\n\n# 第一章\n正文\n\n## 小节\n详情";
493        let doc = parse(content);
494        assert_eq!(doc.structure[0].line_start, Some(5));
495        assert_eq!(doc.structure[0].line_end, Some(6));
496        assert_eq!(doc.structure[0].children[0].line_start, Some(8));
497        assert_eq!(doc.structure[0].children[0].line_end, Some(9));
498    }
499
500    #[test]
501    fn test_front_matter_requires_an_exact_closing_fence() {
502        let content = "---\ntitle: Test\n---not-a-fence\n# Heading";
503        let (front_matter, body) = extract_front_matter(content);
504        assert!(front_matter.is_none());
505        assert_eq!(body, content);
506    }
507}