accent_proust/ast/
node.rs

1//! The document tree.
2//!
3//! Mirrors upstream `src/ast/node.ts`. A [`Node`] is one element of a parsed
4//! document -- a paragraph, a heading, a tag, a run of text -- carrying its
5//! attributes, its children, the annotations that were written on it, the
6//! problems found in it, and where it came from.
7//!
8//! Upstream's `Node` also carries `resolve`, `findSchema`, `transformAttributes`
9//! and `transform`, which are one-line delegations to the transformer. They are
10//! not ported here: the transformer reads a `Config`, and putting a method on
11//! the AST that needs the whole configuration surface would make the leaf type
12//! depend on the stage above it. The transform stage takes `&Node` instead,
13//! which is the same call with the arrow pointing the right way.
14//!
15//! # Two shapes fixed here
16//!
17//! - **Attributes are an [`IndexMap`], in authored order.** `{% foo a=1 b=2 %}`
18//!   and `{% foo b=2 a=1 %}` are different documents and must render as
19//!   different bytes.
20//! - **A node borrows its source.** [`Node::location`] holds a
21//!   [`Location`], which borrows the text it spans. The lifetime stops at the
22//!   AST -- transform produces an owned renderable tree -- so only this layer
23//!   and the formatter carry it.
24
25use indexmap::IndexMap;
26
27use crate::ast::{AttributeLocation, Location, ValidationError, Value};
28use crate::grammar::Attribute;
29
30/// What kind of node this is.
31///
32/// Upstream's `NodeType` is a union of string literals in `types.ts`, and the
33/// spellings here are those strings exactly, because a schema is looked up by
34/// them: a host writing `nodes: { fence: ... }` is naming this enum.
35///
36/// `#[non_exhaustive]` because Markdoc gained node types across its 0.5.x line.
37/// Matching exhaustively on it in a host would turn each new one into a
38/// breaking release of this crate.
39#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, PartialOrd, Ord)]
40#[non_exhaustive]
41pub enum NodeType {
42    /// `> quoted`.
43    Blockquote,
44    /// Inline code, `` `x` ``.
45    Code,
46    /// An HTML comment, when comments are enabled.
47    Comment,
48    /// The root of a parsed document.
49    Document,
50    /// `*emphasis*`.
51    Em,
52    /// A tag whose internals did not parse. Carries the failure in
53    /// [`Node::errors`].
54    Error,
55    /// A fenced code block.
56    Fence,
57    /// A line break written as two trailing spaces or a backslash.
58    Hardbreak,
59    /// `# heading`.
60    Heading,
61    /// A thematic break.
62    Hr,
63    /// `![alt](src)`.
64    Image,
65    /// The inline content of a block.
66    ///
67    /// Not a Markdoc construct: it is the seam markdown-it puts between a block
68    /// and its inline children, and this port keeps it because the annotation
69    /// rules depend on it. An annotation is applied to the node that owns the
70    /// inline run, so `# Title {% #id %}` sets `id` on the heading rather than
71    /// on the text beside it, and an annotation with no inline run above it is
72    /// the `no-inline-annotations` error.
73    Inline,
74    /// A list item.
75    Item,
76    /// `[text](href)`.
77    Link,
78    /// An ordered or unordered list.
79    List,
80    /// The default, and what a host-constructed node is unless it says
81    /// otherwise.
82    #[default]
83    Node,
84    /// A paragraph.
85    Paragraph,
86    /// `~~strikethrough~~`.
87    S,
88    /// A newline inside a block.
89    Softbreak,
90    /// `**strong**`.
91    Strong,
92    /// A table.
93    Table,
94    /// A Markdoc tag. The tag name is in [`Node::tag`].
95    Tag,
96    /// A table body.
97    Tbody,
98    /// A table body cell.
99    Td,
100    /// A run of literal text. Its content is the `content` attribute, which may
101    /// hold a [`Value::Variable`] rather than a string.
102    Text,
103    /// A table header cell.
104    Th,
105    /// A table header.
106    Thead,
107    /// A table row.
108    Tr,
109}
110
111impl NodeType {
112    /// Upstream's spelling, which is the key a schema is registered under.
113    #[must_use]
114    pub const fn as_str(self) -> &'static str {
115        match self {
116            NodeType::Blockquote => "blockquote",
117            NodeType::Code => "code",
118            NodeType::Comment => "comment",
119            NodeType::Document => "document",
120            NodeType::Em => "em",
121            NodeType::Error => "error",
122            NodeType::Fence => "fence",
123            NodeType::Hardbreak => "hardbreak",
124            NodeType::Heading => "heading",
125            NodeType::Hr => "hr",
126            NodeType::Image => "image",
127            NodeType::Inline => "inline",
128            NodeType::Item => "item",
129            NodeType::Link => "link",
130            NodeType::List => "list",
131            NodeType::Node => "node",
132            NodeType::Paragraph => "paragraph",
133            NodeType::S => "s",
134            NodeType::Softbreak => "softbreak",
135            NodeType::Strong => "strong",
136            NodeType::Table => "table",
137            NodeType::Tag => "tag",
138            NodeType::Tbody => "tbody",
139            NodeType::Td => "td",
140            NodeType::Text => "text",
141            NodeType::Th => "th",
142            NodeType::Thead => "thead",
143            NodeType::Tr => "tr",
144        }
145    }
146
147    /// Every node type, in the order [`as_str`](NodeType::as_str) lists them.
148    ///
149    /// For a host that reads node names from text and wants to say what it
150    /// expected: the "expected one of" in its error is this list, joined. One
151    /// list here rather than a copy per host, because a copy is a second list
152    /// to keep in step with the enum. A variant added to the enum fails
153    /// `as_str` to compile until it gains an arm, and this sits beside it; the
154    /// test pins that every entry round-trips through `as_str` and
155    /// [`from_name`](NodeType::from_name) and that none repeats, not that none
156    /// is missing, so add to both.
157    pub const ALL: [NodeType; 28] = [
158        NodeType::Blockquote,
159        NodeType::Code,
160        NodeType::Comment,
161        NodeType::Document,
162        NodeType::Em,
163        NodeType::Error,
164        NodeType::Fence,
165        NodeType::Hardbreak,
166        NodeType::Heading,
167        NodeType::Hr,
168        NodeType::Image,
169        NodeType::Inline,
170        NodeType::Item,
171        NodeType::Link,
172        NodeType::List,
173        NodeType::Node,
174        NodeType::Paragraph,
175        NodeType::S,
176        NodeType::Softbreak,
177        NodeType::Strong,
178        NodeType::Table,
179        NodeType::Tag,
180        NodeType::Tbody,
181        NodeType::Td,
182        NodeType::Text,
183        NodeType::Th,
184        NodeType::Thead,
185        NodeType::Tr,
186    ];
187
188    /// The node type upstream spells `name`, or [`None`].
189    ///
190    /// The inverse of [`NodeType::as_str`]. A host keys its `nodes` schema map
191    /// by these strings -- upstream's config is a JavaScript object literal, and
192    /// anything read from a file or a manifest arrives as text -- so the mapping
193    /// has to run in both directions. Returning [`Option`] rather than defaulting
194    /// to [`NodeType::Node`] is the point: a misspelled key is a schema that
195    /// silently never applies, which is the hardest kind of schema bug to see.
196    #[must_use]
197    pub fn from_name(name: &str) -> Option<NodeType> {
198        // Written as a match on the same list `as_str` produces, so adding a
199        // variant fails to compile here too rather than quietly losing a name.
200        Some(match name {
201            "blockquote" => NodeType::Blockquote,
202            "code" => NodeType::Code,
203            "comment" => NodeType::Comment,
204            "document" => NodeType::Document,
205            "em" => NodeType::Em,
206            "error" => NodeType::Error,
207            "fence" => NodeType::Fence,
208            "hardbreak" => NodeType::Hardbreak,
209            "heading" => NodeType::Heading,
210            "hr" => NodeType::Hr,
211            "image" => NodeType::Image,
212            "inline" => NodeType::Inline,
213            "item" => NodeType::Item,
214            "link" => NodeType::Link,
215            "list" => NodeType::List,
216            "node" => NodeType::Node,
217            "paragraph" => NodeType::Paragraph,
218            "s" => NodeType::S,
219            "softbreak" => NodeType::Softbreak,
220            "strong" => NodeType::Strong,
221            "table" => NodeType::Table,
222            "tag" => NodeType::Tag,
223            "tbody" => NodeType::Tbody,
224            "td" => NodeType::Td,
225            "text" => NodeType::Text,
226            "th" => NodeType::Th,
227            "thead" => NodeType::Thead,
228            "tr" => NodeType::Tr,
229            _ => return None,
230        })
231    }
232}
233
234impl std::fmt::Display for NodeType {
235    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
236        f.write_str(self.as_str())
237    }
238}
239
240/// One node of a parsed document.
241///
242/// Constructed by [`parse`](crate::parse), and by hosts and tests that want a
243/// tree without a source document. [`Node::new`] gives the latter a node with
244/// no location, which is the same shape upstream produces when its `location`
245/// option is off.
246#[derive(Default)]
247pub struct Node<'a> {
248    /// What kind of node this is.
249    pub node_type: NodeType,
250    /// The tag name, for a [`NodeType::Tag`]. `None` for every other kind.
251    pub tag: Option<String>,
252    /// The attributes, in authored order.
253    ///
254    /// Holds both what the syntax implies -- a heading's `level`, a fence's
255    /// `content` -- and what annotations set. Values are unresolved: a
256    /// [`Value::Variable`] here is still a reference, because resolving it needs
257    /// the transform stage's configuration.
258    pub attributes: IndexMap<String, Value>,
259    /// The children, in document order.
260    pub children: Vec<Node<'a>>,
261    /// Named slots, for a tag that uses them.
262    ///
263    /// A `{% slot "name" %}` inside a tag is lifted out of `children` and put
264    /// here, so a tag's ordinary content and its named regions stay separable.
265    /// Only populated when slots are enabled.
266    pub slots: IndexMap<String, Node<'a>>,
267    /// Problems found in this node.
268    ///
269    /// Data, not a failure: a document with a broken tag still parses, because
270    /// an editor wants the rest of the file.
271    pub errors: Vec<ValidationError<'a>>,
272    /// The source lines this node spans, as upstream records them: the opening
273    /// token's `[start, end]`, extended with the closing token's pair when the
274    /// node closes.
275    pub lines: Vec<usize>,
276    /// The annotations written on this node, in authored order.
277    ///
278    /// Kept alongside [`Node::attributes`] rather than folded into it, because
279    /// the formatter reprints the annotation it was given -- `.foo` stays
280    /// `.foo`, not `class={foo: true}`.
281    pub annotations: Vec<Attribute>,
282    /// Where each annotation was written, parallel to [`Node::annotations`].
283    ///
284    /// Either empty, or one entry per annotation in the same order, so index
285    /// `i` describes `annotations[i]`. A consumer that finds the two lengths
286    /// equal can zip them; one that finds this empty has no positions and must
287    /// say so rather than guess.
288    ///
289    /// Empty in two cases. Locations switched off, as [`Node::location`] is;
290    /// and a fence annotated through its info string, because the tokenizer
291    /// reports that string's text but not where it sits, so there is no honest
292    /// offset to give. The two never mix on one node: a fence has no inline
293    /// run, so it cannot also collect a positioned annotation.
294    pub annotation_locations: Vec<AttributeLocation<'a>>,
295    /// Whether this node sits inside an inline run.
296    pub inline: bool,
297    /// Where the node came from, unless locations were switched off.
298    pub location: Option<Location<'a>>,
299}
300
301/// # Why the three traversals are written out rather than derived
302///
303/// The reasoning is on [`Scalar`](crate::renderable::Scalar), and applies here
304/// for the reason [`Drop`] applies: `{% a %}` repeated is one nesting level per
305/// line, so a derived `Clone`, `PartialEq` or `Debug` recurses once per line of
306/// an attacker-supplied document.
307///
308/// Only [`Node::children`] and [`Node::slots`] recurse. The other eight fields
309/// bottom out in types that are already safe -- [`Value`] carries its own
310/// iterative traversals, and everything else is flat -- so they are handled
311/// whole rather than walked.
312impl Clone for Node<'_> {
313    fn clone(&self) -> Self {
314        enum Step<'s, 'a> {
315            Open(&'s Node<'a>),
316            Close(&'s Node<'a>),
317        }
318
319        let mut plan = vec![Step::Open(self)];
320        let mut done: Vec<Node<'_>> = Vec::new();
321
322        while let Some(step) = plan.pop() {
323            match step {
324                Step::Open(node) => {
325                    plan.push(Step::Close(node));
326                    // Slots then children, reversed, so `done` receives
327                    // finished subtrees in the order `Close` reclaims them.
328                    for child in node.children.iter().rev() {
329                        plan.push(Step::Open(child));
330                    }
331                    for (_, slot) in node.slots.iter().rev() {
332                        plan.push(Step::Open(slot));
333                    }
334                }
335                Step::Close(node) => {
336                    let total = node.slots.len() + node.children.len();
337                    let start = done.len().saturating_sub(total);
338                    let mut finished = done.split_off(start).into_iter();
339
340                    let slots: IndexMap<String, Node<'_>> = node
341                        .slots
342                        .keys()
343                        .cloned()
344                        .zip(finished.by_ref().take(node.slots.len()))
345                        .collect();
346                    let children: Vec<Node<'_>> = finished.collect();
347
348                    done.push(Node {
349                        node_type: node.node_type,
350                        tag: node.tag.clone(),
351                        attributes: node.attributes.clone(),
352                        children,
353                        slots,
354                        errors: node.errors.clone(),
355                        lines: node.lines.clone(),
356                        annotations: node.annotations.clone(),
357                        annotation_locations: node.annotation_locations.clone(),
358                        inline: node.inline,
359                        location: node.location,
360                    });
361                }
362            }
363        }
364
365        done.pop().unwrap_or_default()
366    }
367}
368
369impl PartialEq for Node<'_> {
370    fn eq(&self, other: &Self) -> bool {
371        let mut work: Vec<(&Node<'_>, &Node<'_>)> = vec![(self, other)];
372        while let Some((left, right)) = work.pop() {
373            // Every field that cannot recurse, compared whole.
374            if left.node_type != right.node_type
375                || left.tag != right.tag
376                || left.attributes != right.attributes
377                || left.errors != right.errors
378                || left.lines != right.lines
379                || left.annotations != right.annotations
380                || left.annotation_locations != right.annotation_locations
381                || left.inline != right.inline
382                || left.location != right.location
383                || left.children.len() != right.children.len()
384                || left.slots.len() != right.slots.len()
385            {
386                return false;
387            }
388            work.extend(left.children.iter().zip(right.children.iter()));
389            // Unordered, because that is what `IndexMap::eq` does.
390            for (key, slot) in &left.slots {
391                match right.slots.get(key) {
392                    Some(other_slot) => work.push((slot, other_slot)),
393                    None => return false,
394                }
395            }
396        }
397        true
398    }
399}
400
401impl std::fmt::Debug for Node<'_> {
402    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
403        let alternate = f.alternate();
404        let mut stack: Vec<NodeTok<'_, '_>> = vec![NodeTok::Node(self, 0)];
405
406        while let Some(token) = stack.pop() {
407            match token {
408                NodeTok::Text(text) => f.write_str(text)?,
409                NodeTok::Owned(text) => f.write_str(&text)?,
410                NodeTok::Line(depth) => {
411                    f.write_str("\n")?;
412                    for _ in 0..depth {
413                        f.write_str("    ")?;
414                    }
415                }
416                NodeTok::Node(node, depth) => expand_node(f, &mut stack, node, depth, alternate)?,
417            }
418        }
419        Ok(())
420    }
421}
422
423/// One pending piece of `Debug` output for a [`Node`].
424enum NodeTok<'n, 'a> {
425    Node(&'n Node<'a>, usize),
426    Text(&'static str),
427    Owned(String),
428    Line(usize),
429}
430
431/// Re-pad every line after the first, so a block formatted at column zero can
432/// be spliced in at `depth`.
433fn indent_block(body: &str, depth: usize) -> String {
434    let pad = "    ".repeat(depth);
435    body.replace('\n', &format!("\n{pad}"))
436}
437
438/// Write a node's flat fields and queue its children and slots.
439///
440/// The eight non-recursive fields are delegated to their own `Debug`, which is
441/// what the derive would have called; only `children` and `slots` are walked.
442fn expand_node<'n, 'a>(
443    f: &mut std::fmt::Formatter<'_>,
444    stack: &mut Vec<NodeTok<'n, 'a>>,
445    node: &'n Node<'a>,
446    depth: usize,
447    alternate: bool,
448) -> std::fmt::Result {
449    /// Format a flat field the way the derive nests it.
450    fn flat(value: &dyn std::fmt::Debug, depth: usize, alternate: bool) -> String {
451        if alternate {
452            indent_block(&format!("{value:#?}"), depth)
453        } else {
454            format!("{value:?}")
455        }
456    }
457
458    let mut queued: Vec<NodeTok<'n, 'a>> = Vec::new();
459
460    if alternate {
461        let inner = depth + 1;
462        f.write_str("Node {")?;
463        for (name, rendered) in [
464            ("node_type", flat(&node.node_type, inner, true)),
465            ("tag", flat(&node.tag, inner, true)),
466            ("attributes", flat(&node.attributes, inner, true)),
467        ] {
468            queued.push(NodeTok::Line(inner));
469            queued.push(NodeTok::Owned(format!("{name}: {rendered},")));
470        }
471
472        queued.push(NodeTok::Line(inner));
473        if node.children.is_empty() {
474            queued.push(NodeTok::Text("children: [],"));
475        } else {
476            queued.push(NodeTok::Text("children: ["));
477            for child in &node.children {
478                queued.push(NodeTok::Line(inner + 1));
479                queued.push(NodeTok::Node(child, inner + 1));
480                queued.push(NodeTok::Text(","));
481            }
482            queued.push(NodeTok::Line(inner));
483            queued.push(NodeTok::Text("],"));
484        }
485
486        queued.push(NodeTok::Line(inner));
487        if node.slots.is_empty() {
488            queued.push(NodeTok::Text("slots: {},"));
489        } else {
490            queued.push(NodeTok::Text("slots: {"));
491            for (key, slot) in &node.slots {
492                queued.push(NodeTok::Line(inner + 1));
493                queued.push(NodeTok::Owned(format!("{key:?}: ")));
494                queued.push(NodeTok::Node(slot, inner + 1));
495                queued.push(NodeTok::Text(","));
496            }
497            queued.push(NodeTok::Line(inner));
498            queued.push(NodeTok::Text("},"));
499        }
500
501        for (name, rendered) in [
502            ("errors", flat(&node.errors, inner, true)),
503            ("lines", flat(&node.lines, inner, true)),
504            ("annotations", flat(&node.annotations, inner, true)),
505            (
506                "annotation_locations",
507                flat(&node.annotation_locations, inner, true),
508            ),
509            ("inline", flat(&node.inline, inner, true)),
510            ("location", flat(&node.location, inner, true)),
511        ] {
512            queued.push(NodeTok::Line(inner));
513            queued.push(NodeTok::Owned(format!("{name}: {rendered},")));
514        }
515        queued.push(NodeTok::Line(depth));
516        queued.push(NodeTok::Text("}"));
517    } else {
518        write!(
519            f,
520            "Node {{ node_type: {}, tag: {}, attributes: {}, children: [",
521            flat(&node.node_type, depth, false),
522            flat(&node.tag, depth, false),
523            flat(&node.attributes, depth, false),
524        )?;
525        for (index, child) in node.children.iter().enumerate() {
526            if index > 0 {
527                queued.push(NodeTok::Text(", "));
528            }
529            queued.push(NodeTok::Node(child, depth));
530        }
531        queued.push(NodeTok::Text("], slots: {"));
532        for (index, (key, slot)) in node.slots.iter().enumerate() {
533            if index > 0 {
534                queued.push(NodeTok::Text(", "));
535            }
536            queued.push(NodeTok::Owned(format!("{key:?}: ")));
537            queued.push(NodeTok::Node(slot, depth));
538        }
539        queued.push(NodeTok::Owned(format!(
540            "}}, errors: {}, lines: {}, annotations: {}, annotation_locations: {}, \
541             inline: {}, location: {} }}",
542            flat(&node.errors, depth, false),
543            flat(&node.lines, depth, false),
544            flat(&node.annotations, depth, false),
545            flat(&node.annotation_locations, depth, false),
546            flat(&node.inline, depth, false),
547            flat(&node.location, depth, false),
548        )));
549    }
550
551    stack.extend(queued.into_iter().rev());
552    Ok(())
553}
554
555impl<'a> Node<'a> {
556    /// A node of the given type, with no attributes, children or location.
557    ///
558    /// Every field is spelled out rather than filled from `Node::default()`:
559    /// [`Node`] has a manual [`Drop`], and struct-update syntax moves out of the
560    /// value it updates from, which a `Drop` type forbids. Naming the fields is
561    /// also the thing that fails to compile when a field is added, which is
562    /// what you want of a constructor.
563    #[must_use]
564    pub fn new(node_type: NodeType) -> Node<'a> {
565        Node {
566            node_type,
567            tag: None,
568            attributes: IndexMap::new(),
569            children: Vec::new(),
570            slots: IndexMap::new(),
571            errors: Vec::new(),
572            lines: Vec::new(),
573            annotations: Vec::new(),
574            annotation_locations: Vec::new(),
575            inline: false,
576            location: None,
577        }
578    }
579
580    /// A node with attributes, children, and an optional tag name.
581    ///
582    /// The argument order is upstream's `new Node(type, attributes, children,
583    /// tag)`, so a ported test reads next to the TypeScript it came from.
584    #[must_use]
585    pub fn with(
586        node_type: NodeType,
587        attributes: IndexMap<String, Value>,
588        children: Vec<Node<'a>>,
589        tag: Option<String>,
590    ) -> Node<'a> {
591        Node {
592            node_type,
593            tag,
594            attributes,
595            children,
596            slots: IndexMap::new(),
597            errors: Vec::new(),
598            lines: Vec::new(),
599            annotations: Vec::new(),
600            annotation_locations: Vec::new(),
601            inline: false,
602            location: None,
603        }
604    }
605
606    /// Appends a child.
607    pub fn push(&mut self, node: Node<'a>) {
608        self.children.push(node);
609    }
610
611    /// Sets an attribute, in authored order.
612    ///
613    /// A repeated name keeps its first position and takes the last value, which
614    /// is what JavaScript object assignment does and therefore what upstream's
615    /// output order is.
616    pub fn set(&mut self, name: impl Into<String>, value: Value) {
617        self.attributes.insert(name.into(), value);
618    }
619
620    /// Reads an attribute.
621    #[must_use]
622    pub fn get(&self, name: &str) -> Option<&Value> {
623        self.attributes.get(name)
624    }
625
626    /// The name a diagnostic should call this node: its tag if it has one, its
627    /// type otherwise.
628    ///
629    /// Upstream spells this `node.tag || node.type` at each site that needs it.
630    #[must_use]
631    pub fn name(&self) -> &str {
632        self.tag
633            .as_deref()
634            .unwrap_or_else(|| self.node_type.as_str())
635    }
636
637    /// Every descendant, depth first, slots before children.
638    ///
639    /// The order is upstream's `walk()` exactly, and it is load-bearing:
640    /// `ast/node.test.ts` asserts the sequence for a document with slots, and a
641    /// validator that reported errors in a different order would produce a
642    /// different diff for the same file.
643    #[must_use]
644    pub fn walk(&self) -> Walk<'_, 'a> {
645        Walk {
646            stack: self.descendants_in_order(),
647        }
648    }
649
650    /// The direct descendants in walk order, ready to be pushed onto a stack.
651    ///
652    /// Reversed, because [`Walk`] pops from the end.
653    fn descendants_in_order(&self) -> Vec<&Node<'a>> {
654        let mut out: Vec<&Node<'a>> = self.slots.values().chain(self.children.iter()).collect();
655        out.reverse();
656        out
657    }
658}
659
660/// Dropping a tree is iterative, for the same reason walking it is.
661///
662/// Nesting depth is attacker-controlled -- `{% a %}` repeated is a nesting level
663/// per line -- and the derived recursive drop turns a deep document into a stack
664/// overflow, which aborts the process rather than raising anything a caller
665/// could catch. Unlinking the tree onto the heap first bounds the recursion at
666/// one level.
667///
668/// The cost, stated because it is invisible until someone hits it: a type with a
669/// manual `Drop` cannot have a field moved out of it, so a consumer that wants
670/// to take ownership of `children` uses [`std::mem::take`] rather than a partial
671/// move. That is a small tax on the stages above, paid once, against an abort
672/// that a document can trigger.
673impl Drop for Node<'_> {
674    fn drop(&mut self) {
675        let mut pending: Vec<Node<'_>> = std::mem::take(&mut self.children);
676        pending.extend(self.slots.drain(..).map(|(_, node)| node));
677        while let Some(mut node) = pending.pop() {
678            pending.append(&mut node.children);
679            pending.extend(node.slots.drain(..).map(|(_, child)| child));
680            // `node` is dropped here already emptied, so this recurses once.
681        }
682    }
683}
684
685/// A depth-first walk over a node's descendants.
686///
687/// Iterative rather than recursive: the input is arbitrary text, nesting depth
688/// is attacker-controlled, and a recursive iterator would make tree depth a
689/// stack-overflow budget.
690pub struct Walk<'n, 'a> {
691    stack: Vec<&'n Node<'a>>,
692}
693
694impl<'n, 'a> Iterator for Walk<'n, 'a> {
695    type Item = &'n Node<'a>;
696
697    fn next(&mut self) -> Option<&'n Node<'a>> {
698        let node = self.stack.pop()?;
699        self.stack.extend(node.descendants_in_order());
700        Some(node)
701    }
702}
703
704/// `Debug` output is observable, so the hand-written emitter is pinned against
705/// the derive. Same pattern as [`Scalar`](crate::renderable::Scalar).
706#[cfg(test)]
707mod debug_parity {
708    use super::*;
709
710    mod mirror {
711        // Every field exists to be formatted by the derive and is never read
712        // otherwise -- that is the whole point of the type.
713        #![allow(dead_code, clippy::struct_field_names)]
714
715        use super::{Attribute, AttributeLocation, Location, NodeType, ValidationError, Value};
716        use indexmap::IndexMap;
717
718        #[derive(Debug)]
719        pub struct Node<'a> {
720            pub node_type: NodeType,
721            pub tag: Option<String>,
722            pub attributes: IndexMap<String, Value>,
723            pub children: Vec<Node<'a>>,
724            pub slots: IndexMap<String, Node<'a>>,
725            pub errors: Vec<ValidationError<'a>>,
726            pub lines: Vec<usize>,
727            pub annotations: Vec<Attribute>,
728            pub annotation_locations: Vec<AttributeLocation<'a>>,
729            pub inline: bool,
730            pub location: Option<Location<'a>>,
731        }
732    }
733
734    fn to_mirror<'a>(node: &Node<'a>) -> mirror::Node<'a> {
735        mirror::Node {
736            node_type: node.node_type,
737            tag: node.tag.clone(),
738            attributes: node.attributes.clone(),
739            children: node.children.iter().map(to_mirror).collect(),
740            slots: node
741                .slots
742                .iter()
743                .map(|(key, slot)| (key.clone(), to_mirror(slot)))
744                .collect(),
745            errors: node.errors.clone(),
746            lines: node.lines.clone(),
747            annotations: node.annotations.clone(),
748            annotation_locations: node.annotation_locations.clone(),
749            inline: node.inline,
750            location: node.location,
751        }
752    }
753
754    fn assert_parity(node: &Node<'_>) {
755        let reference = to_mirror(node);
756        assert_eq!(format!("{node:?}"), format!("{reference:?}"), "plain Debug");
757        assert_eq!(
758            format!("{node:#?}"),
759            format!("{reference:#?}"),
760            "alternate Debug"
761        );
762    }
763
764    #[test]
765    fn every_node_shape_formats_as_the_derive_would() {
766        let mut bare = Node::new(NodeType::Paragraph);
767        bare.lines = vec![1, 2];
768
769        let mut attributed = Node::new(NodeType::Tag);
770        attributed.tag = Some("callout".to_owned());
771        attributed.set("level", Value::Number(2.0));
772        attributed.set("title", Value::String("hi".to_owned()));
773        attributed.inline = true;
774
775        let nested = Node::with(
776            NodeType::Document,
777            IndexMap::new(),
778            vec![Node::with(
779                NodeType::Paragraph,
780                IndexMap::new(),
781                vec![Node::new(NodeType::Text)],
782                None,
783            )],
784            None,
785        );
786
787        let mut slotted = Node::new(NodeType::Tag);
788        slotted.tag = Some("card".to_owned());
789        slotted
790            .slots
791            .insert("header".to_owned(), Node::new(NodeType::Paragraph));
792
793        // A value deep enough to matter inside an attribute, which the node's
794        // own walk hands to `Value`'s.
795        let mut deep_attribute = Node::new(NodeType::Tag);
796        deep_attribute.set(
797            "data",
798            Value::Array(vec![Value::Hash(
799                [("k".to_owned(), Value::Null)].into_iter().collect(),
800            )]),
801        );
802
803        for shape in &[bare, attributed, nested, slotted, deep_attribute] {
804            assert_parity(shape);
805        }
806    }
807
808    #[test]
809    fn a_deep_node_survives_all_three_traversals() {
810        // `{% a %}` repeated is one level per line, so this depth is
811        // attacker-supplied rather than hypothetical.
812        let mut node = Node::new(NodeType::Paragraph);
813        for _ in 0..100_000 {
814            node = Node::with(NodeType::Tag, IndexMap::new(), vec![node], Some("a".into()));
815        }
816        let copy = node.clone();
817        assert!(copy == node, "an iterative clone must equal its source");
818        assert!(format!("{node:?}").starts_with("Node { node_type: Tag"));
819    }
820
821    #[test]
822    fn a_node_deep_through_slots_survives_all_three() {
823        let mut node = Node::new(NodeType::Paragraph);
824        for _ in 0..100_000 {
825            let mut outer = Node::new(NodeType::Tag);
826            outer.slots.insert("s".to_owned(), node);
827            node = outer;
828        }
829        let copy = node.clone();
830        assert_eq!(copy, node);
831    }
832
833    #[test]
834    fn cloning_preserves_child_and_slot_order() {
835        let mut node = Node::with(
836            NodeType::Document,
837            IndexMap::new(),
838            vec![Node::new(NodeType::Heading), Node::new(NodeType::Paragraph)],
839            None,
840        );
841        node.slots.insert("z".to_owned(), Node::new(NodeType::Text));
842        node.slots
843            .insert("a".to_owned(), Node::new(NodeType::Fence));
844
845        let copy = node.clone();
846        assert_eq!(copy.children.len(), 2);
847        assert_eq!(copy.children[0].node_type, NodeType::Heading);
848        assert_eq!(copy.children[1].node_type, NodeType::Paragraph);
849        assert_eq!(copy.slots.keys().collect::<Vec<_>>(), ["z", "a"]);
850        assert_eq!(copy.slots["a"].node_type, NodeType::Fence);
851        assert_eq!(copy, node);
852    }
853}
854
855#[cfg(test)]
856mod tests {
857    use super::*;
858
859    fn text(content: &str) -> Node<'static> {
860        let mut node = Node::new(NodeType::Text);
861        node.set("content", Value::String(content.to_string()));
862        node
863    }
864
865    fn block(node_type: NodeType, children: Vec<Node<'static>>) -> Node<'static> {
866        Node::with(node_type, IndexMap::new(), children, None)
867    }
868
869    /// Ported from `ast/node.test.ts`, "traversal / with a simple document".
870    #[test]
871    fn walking_a_simple_document_visits_every_descendant() {
872        let example = block(
873            NodeType::Document,
874            vec![
875                block(
876                    NodeType::Heading,
877                    vec![block(NodeType::Inline, vec![text("This is a heading")])],
878                ),
879                block(
880                    NodeType::Paragraph,
881                    vec![block(NodeType::Inline, vec![text("This is a paragraph")])],
882                ),
883            ],
884        );
885
886        assert_eq!(example.walk().count(), 6);
887    }
888
889    #[test]
890    fn walking_visits_slots_before_children() {
891        // The order upstream's `ast/node.test.ts` asserts for a parsed document
892        // with slots, built here by hand so the assertion does not also depend
893        // on the segmenter.
894        let mut tag = Node::with(
895            NodeType::Tag,
896            IndexMap::new(),
897            Vec::new(),
898            Some("example".into()),
899        );
900        tag.slots.insert(
901            "foo".to_string(),
902            block(
903                NodeType::Paragraph,
904                vec![block(NodeType::Inline, vec![text("baz")])],
905            ),
906        );
907        tag.push(block(
908            NodeType::Heading,
909            vec![block(NodeType::Inline, vec![text("bar")])],
910        ));
911        let document = block(NodeType::Document, vec![tag]);
912
913        let visited: Vec<String> = document
914            .walk()
915            .map(|node| node.name().to_string())
916            .collect();
917        assert_eq!(
918            visited,
919            [
920                "example",
921                "paragraph",
922                "inline",
923                "text",
924                "heading",
925                "inline",
926                "text"
927            ]
928        );
929    }
930
931    #[test]
932    fn walking_is_iterative_and_survives_deep_nesting() {
933        // Nesting depth is attacker-controlled. A recursive walk would make
934        // this a stack overflow rather than a count.
935        let mut node = Node::new(NodeType::Document);
936        for _ in 0..50_000 {
937            node = block(NodeType::Tag, vec![node]);
938        }
939        assert_eq!(node.walk().count(), 50_000);
940    }
941
942    #[test]
943    fn attribute_order_is_authored_order() {
944        let mut node = Node::new(NodeType::Tag);
945        node.set("z", Value::Number(1.0));
946        node.set("a", Value::Number(2.0));
947        node.set("z", Value::Number(3.0));
948        let keys: Vec<&str> = node.attributes.keys().map(String::as_str).collect();
949        assert_eq!(keys, ["z", "a"]);
950        assert_eq!(node.get("z"), Some(&Value::Number(3.0)));
951    }
952
953    #[test]
954    fn a_node_names_itself_by_tag_then_type() {
955        assert_eq!(Node::new(NodeType::Paragraph).name(), "paragraph");
956        let mut tagged = Node::new(NodeType::Tag);
957        tagged.tag = Some("callout".to_string());
958        assert_eq!(tagged.name(), "callout");
959    }
960
961    #[test]
962    fn node_types_spell_themselves_as_upstream_does() {
963        assert_eq!(NodeType::Fence.as_str(), "fence");
964        assert_eq!(NodeType::Hardbreak.to_string(), "hardbreak");
965        assert_eq!(NodeType::default(), NodeType::Node);
966    }
967}
968
969#[cfg(test)]
970mod node_type_list {
971    use super::NodeType;
972
973    #[test]
974    fn all_round_trips_through_its_names_and_repeats_none() {
975        let mut seen = std::collections::HashSet::new();
976        for node_type in NodeType::ALL {
977            assert_eq!(NodeType::from_name(node_type.as_str()), Some(node_type));
978            assert!(seen.insert(node_type), "{node_type} is listed twice");
979        }
980    }
981}
accent_proust/ast/node.rs

accent_proust/ast/
node.rs
