Skip to main content

ferromark_transforms/
toc.rs

1//! Caller-placed table-of-contents nodes built from a Ferromark outline.
2
3use std::error::Error;
4use std::fmt;
5
6use ferromark::ast::{Link, List, ListItem, Node, Paragraph, Span, Text};
7use ferromark::{Allocator, OutlineEntry};
8
9/// Builds a nested unordered-list AST node from one document outline.
10///
11/// The returned node is allocated in `allocator`; every generated AST span is
12/// [`Span::empty`]. The caller chooses where to insert the node and should
13/// build it from the same document and heading-ID settings used by the
14/// renderer. Transforms should finish before the outline is computed and this
15/// node is added. The result has no shared state across committed or
16/// provisional fragments.
17///
18/// An empty outline returns `Ok(None)`. If any entry has no heading ID, this
19/// returns an error before allocating AST nodes. The helper does not parse a
20/// marker, mutate a document, or render HTML.
21pub fn build_table_of_contents<'arena>(
22    allocator: &'arena Allocator,
23    entries: &[OutlineEntry],
24) -> Result<Option<Node<'arena>>, TableOfContentsError> {
25    if entries.is_empty() {
26        return Ok(None);
27    }
28
29    let ids = entries
30        .iter()
31        .enumerate()
32        .map(|(entry_index, entry)| {
33            entry
34                .id
35                .as_deref()
36                .ok_or(TableOfContentsError { entry_index })
37        })
38        .collect::<Result<Vec<_>, _>>()?;
39
40    let items = build_items(entries);
41    let list = build_list(allocator, entries, &ids, &items);
42    Ok(Some(Node::List(allocator.boxed(list))))
43}
44
45/// Error returned when an outline entry cannot become a TOC link.
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub struct TableOfContentsError {
48    entry_index: usize,
49}
50
51impl TableOfContentsError {
52    /// Returns the zero-based outline entry without a heading ID.
53    #[must_use]
54    pub const fn entry_index(&self) -> usize {
55        self.entry_index
56    }
57}
58
59impl fmt::Display for TableOfContentsError {
60    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
61        write!(
62            formatter,
63            "outline entry {} has no heading ID; enable heading IDs when building the outline",
64            self.entry_index
65        )
66    }
67}
68
69impl Error for TableOfContentsError {}
70
71struct TocItem {
72    entry_index: usize,
73    children: Vec<TocItem>,
74}
75
76fn build_items(entries: &[OutlineEntry]) -> Vec<TocItem> {
77    let mut roots = Vec::new();
78    let mut path = Vec::<(u8, usize)>::new();
79
80    for (entry_index, entry) in entries.iter().enumerate() {
81        while path.last().is_some_and(|(level, _)| *level >= entry.level) {
82            path.pop();
83        }
84
85        let siblings = children_at_path(&mut roots, &path);
86        let item_index = siblings.len();
87        siblings.push(TocItem {
88            entry_index,
89            children: Vec::new(),
90        });
91        path.push((entry.level, item_index));
92    }
93
94    roots
95}
96
97fn children_at_path<'items>(
98    items: &'items mut Vec<TocItem>,
99    path: &[(u8, usize)],
100) -> &'items mut Vec<TocItem> {
101    let Some(((_, item_index), remaining)) = path.split_first() else {
102        return items;
103    };
104    children_at_path(&mut items[*item_index].children, remaining)
105}
106
107fn build_list<'arena>(
108    allocator: &'arena Allocator,
109    entries: &[OutlineEntry],
110    ids: &[&str],
111    items: &[TocItem],
112) -> List<'arena> {
113    let mut children = allocator.new_vec_with_capacity(items.len());
114
115    for item in items {
116        let entry = &entries[item.entry_index];
117        let id = ids[item.entry_index];
118
119        let mut url = String::from("#");
120        url.push_str(id);
121        let url = allocator.alloc_str(&url);
122
123        let mut link_children = allocator.new_vec_with_capacity(1);
124        link_children.push(Node::Text(Text {
125            value: allocator.alloc_str(&entry.text),
126            span: Span::empty(),
127        }));
128        let link = Node::Link(allocator.boxed(Link {
129            url,
130            title: None,
131            attributes: None,
132            children: link_children,
133            span: Span::empty(),
134        }));
135
136        let mut paragraph_children = allocator.new_vec_with_capacity(1);
137        paragraph_children.push(link);
138        let paragraph = Node::Paragraph(allocator.boxed(Paragraph {
139            children: paragraph_children,
140            span: Span::empty(),
141        }));
142
143        let nested = !item.children.is_empty();
144        let mut item_children = allocator.new_vec_with_capacity(if nested { 2 } else { 1 });
145        item_children.push(paragraph);
146        if nested {
147            let nested_list = build_list(allocator, entries, ids, &item.children);
148            item_children.push(Node::List(allocator.boxed(nested_list)));
149        }
150
151        children.push(ListItem {
152            spread: false,
153            checked: None,
154            children: item_children,
155            span: Span::empty(),
156        });
157    }
158
159    List {
160        ordered: false,
161        start: None,
162        spread: false,
163        children,
164        span: Span::empty(),
165    }
166}
167
168#[cfg(test)]
169mod tests {
170    use ferromark::ast::Span;
171
172    use super::{TableOfContentsError, build_items};
173    use ferromark::OutlineEntry;
174
175    fn entry(level: u8) -> OutlineEntry {
176        OutlineEntry {
177            level,
178            text: String::new(),
179            id: Some(String::new()),
180            span: Span::empty(),
181        }
182    }
183
184    #[test]
185    fn skipped_levels_nest_under_the_nearest_shallower_heading() {
186        let entries = [entry(1), entry(4), entry(2), entry(2), entry(1)];
187        let items = build_items(&entries);
188
189        assert_eq!(items.len(), 2);
190        assert_eq!(items[0].children.len(), 3);
191        assert_eq!(items[0].children[0].children.len(), 0);
192        assert_eq!(items[0].children[1].children.len(), 0);
193        assert_eq!(items[0].children[2].children.len(), 0);
194        assert_eq!(items[1].children.len(), 0);
195    }
196
197    #[test]
198    fn missing_heading_id_error_reports_the_entry_index() {
199        let error = TableOfContentsError { entry_index: 3 };
200        assert_eq!(error.entry_index(), 3);
201    }
202}