Skip to main content

carve/render/
render_depth.rs

1//! The typed refusal a renderer owes its caller at the depth ceiling (PART 9
2//! §25).
3//!
4//! §25 gives every renderer a bound above the parser's and says what happens AT
5//! it: the render MUST fail with a typed, documented error naming the bound -
6//! the same rule PART 12 §9(b) already applies to ingest, at the other end of
7//! the same pipe. Returning empty output instead is the failure the clause was
8//! written against: the caller gets a string that looks complete and has had its
9//! body deleted (carve-rs#511 item 5). carve-js raises `RenderDepthError` and
10//! carve-php `RenderDepthExceededException`; a `Result` is the same statement in
11//! this language.
12//!
13//! It costs nothing on any path a document travels. The ceiling exceeds
14//! `parse::MAX_NESTING_DEPTH` by construction, so a tree that came from the
15//! parser cannot reach it - which is why the source-level `to_*` entry points
16//! keep returning `String`. What is left is a tree built through the API or read
17//! by `from_json`, where the caller is the one who can act on the error.
18//!
19//! The bound is recorded through a thread-local rather than by threading a
20//! `Result` through every recursive renderer function, following
21//! [`crate::abbr_budget`]: the guard is installed for one render and unwinds on
22//! drop, so a nested render (a block extension rendering sub-blocks) stacks
23//! correctly instead of reporting its parent's state.
24//!
25//! [`refuse_if_too_deep`] is why any of that is reachable. The recording guards
26//! bound the renderer's OWN descent, but every entry point touches the tree
27//! structurally before that descent starts, and none of those touches has a
28//! ceiling to consult. See that function for the list and for the measurement
29//! that replaces it.
30
31use std::cell::Cell;
32use std::fmt;
33
34use crate::ast::{BlockNode, Document, FigureTarget, InlineNode};
35use crate::render::MAX_RENDER_DEPTH;
36
37/// A render refused because the tree is deeper than the renderer's ceiling.
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct RenderDepthError {
40    renderer: &'static str,
41    limit: usize,
42}
43
44impl RenderDepthError {
45    pub(crate) fn new(renderer: &'static str, limit: usize) -> Self {
46        Self { renderer, limit }
47    }
48
49    /// Which target refused: `"html"`, `"markdown"`, `"plain"`, `"ansi"` or
50    /// `"carve"`.
51    pub fn renderer(&self) -> &'static str {
52        self.renderer
53    }
54
55    /// The bound that was reached, in AST levels.
56    pub fn limit(&self) -> usize {
57        self.limit
58    }
59}
60
61impl fmt::Display for RenderDepthError {
62    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
63        write!(
64            f,
65            "the {} renderer refused: the tree is deeper than its ceiling of {} levels",
66            self.renderer, self.limit
67        )
68    }
69}
70
71impl std::error::Error for RenderDepthError {}
72
73thread_local! {
74    /// The renderer that reached the ceiling during the render currently running
75    /// on this thread, if any. `None` outside a render, and while one is running
76    /// until a guard site records.
77    static REACHED: Cell<Option<&'static str>> = const { Cell::new(None) };
78}
79
80/// Record that this renderer reached the ceiling.
81///
82/// Called at each depth guard, beside the early return that keeps the recursion
83/// bounded. The guard still returns - the bound is what stops the stack from
84/// growing - and the top-level entry point turns the record into the error.
85pub(crate) fn record(renderer: &'static str) {
86    REACHED.with(|cell| {
87        if cell.get().is_none() {
88            cell.set(Some(renderer));
89        }
90    });
91}
92
93/// RAII watch installed for one render, restoring the previous value on drop so
94/// nested renders stack and unwind (the reason spelled out in the module note).
95pub(crate) struct RenderDepthWatch {
96    previous: Option<&'static str>,
97}
98
99impl RenderDepthWatch {
100    pub(crate) fn new() -> Self {
101        let previous = REACHED.with(|cell| cell.replace(None));
102        RenderDepthWatch { previous }
103    }
104
105    /// The render's output, or the refusal if any guard recorded one.
106    pub(crate) fn into_result(self, output: String) -> Result<String, RenderDepthError> {
107        match REACHED.with(|cell| cell.get()) {
108            Some(renderer) => Err(RenderDepthError::new(
109                renderer,
110                crate::render::MAX_RENDER_DEPTH,
111            )),
112            None => Ok(output),
113        }
114    }
115}
116
117impl Drop for RenderDepthWatch {
118    fn drop(&mut self) {
119        REACHED.with(|cell| cell.set(self.previous));
120    }
121}
122
123/// The refusal a renderer owes a tree it must not walk at all, or `Ok(())`.
124///
125/// Called FIRST at every entry point that accepts a tree from outside the
126/// parser, before anything reads the tree's shape.
127///
128/// The recording guards above cannot carry this on their own, because they sit
129/// inside the renderer's own recursion and several things recurse over the tree
130/// before it starts: the defensive `doc.clone()` in the borrowed-AST entry
131/// points and prepasses
132/// such as `parse::crossref_index_for_document`. Derived `Clone` has no ceiling
133/// to consult at all, so a tree deeper than the C stack aborted the process -
134/// SIGABRT, no exit code a caller can branch on, no diagnostic, and in a server a
135/// dropped request - and the typed error above was never reached
136/// (carve-rs#1877).
137///
138/// Guarding those prepasses one at a time only moves the cliff: the markdown
139/// importer aborted at 2,000 levels through the writer's clone and at 100,000 it
140/// reached `collect_caption_titles` instead. Refusing here, before any of them
141/// run, is what removes it.
142pub(crate) fn refuse_if_too_deep(
143    doc: &Document,
144    renderer: &'static str,
145) -> Result<(), RenderDepthError> {
146    if exceeds_ceiling(doc) {
147        return Err(RenderDepthError::new(renderer, MAX_RENDER_DEPTH));
148    }
149    Ok(())
150}
151
152/// Returns an error past the depth ceiling, otherwise whether HTML preparation is required.
153pub(crate) fn html_preparation_needed(doc: &Document) -> Result<bool, RenderDepthError> {
154    let (exceeds, preparation) = inspect::<true>(doc);
155    if exceeds {
156        Err(RenderDepthError::new("html", MAX_RENDER_DEPTH))
157    } else {
158        Ok(preparation)
159    }
160}
161
162fn exceeds_ceiling(doc: &Document) -> bool {
163    inspect::<false>(doc).0
164}
165
166/// Whether the tree nests deeper than [`MAX_RENDER_DEPTH`], measured on an
167/// EXPLICIT STACK.
168///
169/// Iterative because the whole point is to answer before anything recursive
170/// touches the tree; a recursive depth check would abort on the input it exists
171/// to refuse.
172///
173/// Block and inline depth are counted SEPARATELY against the same bound, which
174/// is exactly what the guards inside the renderers do (`block_depth` and
175/// `inline_depth` are two counters there). Summing them would refuse trees that
176/// render today.
177///
178/// A root sequence is depth 0, which is the index the renderers' own counters
179/// carry - `render_blocks` tests the depth it was ENTERED at, before
180/// incrementing. Seeding at 1 instead refused one tree that renders on main: 432
181/// nested quotes, the deepest document the ceiling admits.
182///
183/// Stops at the first node past the ceiling, so a deep document costs the depth
184/// rather than the tree. A document under the ceiling pays one pointer walk.
185fn inspect<const HTML: bool>(doc: &Document) -> (bool, bool) {
186    let mut preparation = HTML && !doc.footnote_defs.is_empty();
187    let mut blocks: Vec<(&BlockNode, usize)> = Vec::new();
188    let mut inlines: Vec<(&InlineNode, usize)> = Vec::new();
189    push_blocks(&mut blocks, &doc.children, 0);
190    for body in doc.footnote_defs.values() {
191        push_blocks(&mut blocks, body, 0);
192    }
193    while let Some((block, depth)) = blocks.pop() {
194        if depth > MAX_RENDER_DEPTH {
195            return (true, preparation);
196        }
197        push_block_children(block, depth, &mut blocks, &mut inlines);
198        while let Some((inline, depth)) = inlines.pop() {
199            if depth > MAX_RENDER_DEPTH {
200                return (true, preparation);
201            }
202            if HTML && matches!(inline, InlineNode::Image(_) | InlineNode::Footnote(_)) {
203                preparation = true;
204            }
205            push_inline_children(inline, depth, &mut inlines);
206        }
207    }
208    (false, preparation)
209}
210
211/// Whether a list item reaches the parser's nesting cap.
212///
213/// This gate is specific to the list writer's over-cap marker handling. Other
214/// deep containers can remain writable even when their AST exceeds the parser's
215/// cap, as happens with imported Markdown block quotes.
216pub(crate) fn reaches_list_nesting_cap(doc: &Document) -> bool {
217    let cap = crate::parse::MAX_NESTING_DEPTH;
218    let mut blocks: Vec<(&BlockNode, usize)> = Vec::new();
219    let mut inlines: Vec<(&InlineNode, usize)> = Vec::new();
220    push_blocks(&mut blocks, &doc.children, 0);
221    for body in doc.footnote_defs.values() {
222        push_blocks(&mut blocks, body, 0);
223    }
224    while let Some((block, depth)) = blocks.pop() {
225        if matches!(block, BlockNode::List(_)) && depth + 1 >= cap {
226            return true;
227        }
228        push_block_children(block, depth, &mut blocks, &mut inlines);
229        inlines.clear();
230    }
231    false
232}
233
234fn push_blocks<'a>(out: &mut Vec<(&'a BlockNode, usize)>, children: &'a [BlockNode], depth: usize) {
235    out.extend(children.iter().map(|child| (child, depth)));
236}
237
238fn push_inlines<'a>(
239    out: &mut Vec<(&'a InlineNode, usize)>,
240    children: &'a [InlineNode],
241    depth: usize,
242) {
243    out.extend(children.iter().map(|child| (child, depth)));
244}
245
246/// The sequences one block holds directly, mirroring
247/// [`crate::include_walk::visit_block_children`].
248///
249/// EXHAUSTIVE for the reason that one is: a `_ => {}` arm would leave a
250/// container added later out of the measurement, and the abort this refusal
251/// exists to prevent would come back through it with nothing to say why.
252pub(crate) fn push_block_children<'a>(
253    block: &'a BlockNode,
254    depth: usize,
255    blocks: &mut Vec<(&'a BlockNode, usize)>,
256    inlines: &mut Vec<(&'a InlineNode, usize)>,
257) {
258    let deeper = depth + 1;
259    match block {
260        BlockNode::Heading(h) => push_inlines(inlines, &h.children, 0),
261        BlockNode::Paragraph(p) => push_inlines(inlines, &p.children, 0),
262        BlockNode::LineBlock(b) => push_blocks(blocks, &b.children, deeper),
263        BlockNode::BlockQuote(b) => push_blocks(blocks, &b.children, deeper),
264        BlockNode::Admonition(a) => {
265            if let Some(title) = &a.title {
266                push_inlines(inlines, title, 0);
267            }
268            push_blocks(blocks, &a.children, deeper);
269        }
270        BlockNode::Directive(d) => {
271            if let Some(title) = &d.title {
272                push_inlines(inlines, title, 0);
273            }
274            push_blocks(blocks, &d.children, deeper);
275        }
276        BlockNode::Div(d) => push_blocks(blocks, &d.children, deeper),
277        BlockNode::Section(d) => push_blocks(blocks, &d.children, deeper),
278        BlockNode::List(l) => {
279            for item in &l.items {
280                push_blocks(blocks, &item.children, deeper);
281            }
282        }
283        BlockNode::DefinitionList(d) => {
284            for item in &d.items {
285                for term in &item.terms {
286                    push_inlines(inlines, &term.children, 0);
287                }
288                for def in &item.definitions {
289                    push_blocks(blocks, &def.children, deeper);
290                }
291            }
292        }
293        BlockNode::Table(t) => {
294            if let Some(caption) = &t.short_caption {
295                push_inlines(inlines, caption, 0);
296            }
297            if let Some(caption) = &t.caption {
298                push_inlines(inlines, caption, 0);
299            }
300            for row in &t.rows {
301                for cell in &row.cells {
302                    push_inlines(inlines, &cell.children, 0);
303                    if let Some(content) = &cell.blocks {
304                        push_blocks(blocks, content, deeper);
305                    }
306                }
307            }
308        }
309        BlockNode::FigureGroup(g) => {
310            push_blocks(blocks, &g.children, deeper);
311            if let Some(caption) = &g.caption {
312                push_inlines(inlines, caption, 0);
313            }
314        }
315        BlockNode::Figure(f) => {
316            if let Some(caption) = &f.short_caption {
317                push_inlines(inlines, caption, 0);
318            }
319            push_inlines(inlines, &f.caption, 0);
320            match &*f.target {
321                FigureTarget::BlockQuote(b) => push_blocks(blocks, &b.children, deeper),
322                FigureTarget::Paragraph(p) => push_inlines(inlines, &p.children, 0),
323                FigureTarget::Table(t) => {
324                    if let Some(caption) = &t.caption {
325                        push_inlines(inlines, caption, 0);
326                    }
327                    if let Some(caption) = &t.short_caption {
328                        push_inlines(inlines, caption, 0);
329                    }
330                    for row in &t.rows {
331                        for cell in &row.cells {
332                            push_inlines(inlines, &cell.children, 0);
333                            if let Some(content) = &cell.blocks {
334                                push_blocks(blocks, content, deeper);
335                            }
336                        }
337                    }
338                }
339                FigureTarget::Image(_) | FigureTarget::CodeBlock(_) => {}
340            }
341        }
342        // The fallback is ONE node, and it is a block: a level of its own, the
343        // same as any other child.
344        BlockNode::BlockExtension(e) => blocks.push((&e.fallback, deeper)),
345        BlockNode::ExtensionCarrier(e) => {
346            if let Some(summary) = &e.summary {
347                push_inlines(inlines, summary, 0);
348            }
349            push_blocks(blocks, &e.children, deeper);
350        }
351        BlockNode::CitationDefinition(c) => push_inlines(inlines, &c.children, 0),
352        BlockNode::CodeBlock(_)
353        | BlockNode::RawBlock(_)
354        | BlockNode::Comment(_)
355        | BlockNode::AbbreviationDef(_)
356        | BlockNode::LinkReferenceDefinition(_)
357        | BlockNode::BlockImage(_)
358        | BlockNode::ThematicBreak(_) => {}
359    }
360}
361
362/// The sequences one inline node holds, mirroring
363/// [`crate::include_walk::visit_inline_children`], and exhaustive for the same
364/// reason as above.
365pub(crate) fn push_inline_children<'a>(
366    node: &'a InlineNode,
367    depth: usize,
368    inlines: &mut Vec<(&'a InlineNode, usize)>,
369) {
370    let deeper = depth + 1;
371    match node {
372        InlineNode::Emphasis(e) => push_inlines(inlines, &e.children, deeper),
373        InlineNode::Link(l) => push_inlines(inlines, &l.children, deeper),
374        InlineNode::Span(s) => push_inlines(inlines, &s.children, deeper),
375        InlineNode::Ruby(r) => {
376            for pair in &r.pairs {
377                push_inlines(inlines, &pair.base, deeper);
378                push_inlines(inlines, &pair.annotation, deeper);
379            }
380        }
381        InlineNode::CriticInsert(c) => push_inlines(inlines, &c.children, deeper),
382        InlineNode::CriticDelete(c) => push_inlines(inlines, &c.children, deeper),
383        InlineNode::CriticSubstitute(c) => {
384            push_inlines(inlines, &c.old, deeper);
385            push_inlines(inlines, &c.new, deeper);
386        }
387        InlineNode::Extension(e) => push_inlines(inlines, &e.children, deeper),
388        InlineNode::Footnote(f) => {
389            if let Some(inline) = &f.inline {
390                push_inlines(inlines, inline, deeper);
391            }
392        }
393        InlineNode::CitationGroup(g) => {
394            for item in &g.items {
395                if let Some(prefix) = &item.prefix {
396                    push_inlines(inlines, prefix, deeper);
397                }
398                if let Some(locator) = &item.locator {
399                    push_inlines(inlines, locator, deeper);
400                }
401                if let Some(suffix) = &item.suffix {
402                    push_inlines(inlines, suffix, deeper);
403                }
404            }
405        }
406        InlineNode::Text(_)
407        | InlineNode::EscapedText(_)
408        | InlineNode::SmartPunctuation(_)
409        | InlineNode::Code(_)
410        | InlineNode::Image(_)
411        | InlineNode::Math(_)
412        | InlineNode::RawInline(_)
413        | InlineNode::LiteralInline(_)
414        | InlineNode::Symbol(_)
415        | InlineNode::AutoLink(_)
416        | InlineNode::CrossRef(_)
417        | InlineNode::CaptionNumber(_)
418        | InlineNode::Mention(_)
419        | InlineNode::Tag(_)
420        | InlineNode::Abbreviation(_)
421        | InlineNode::NonBreakingSpace(_)
422        | InlineNode::SoftBreak(_)
423        | InlineNode::CellWrap(_)
424        | InlineNode::HardBreak(_)
425        | InlineNode::CriticComment(_)
426        | InlineNode::Comment(_) => {}
427    }
428}