bob/
element.rs

1/// An owned XML element: enough of the DOM to read `.bob` properties.
2#[derive(Clone, Debug, Default, PartialEq)]
3pub struct Element {
4    pub name: String,
5    pub attrs: Vec<(String, String)>,
6    /// Text content, trimmed, when the element has no child elements.
7    pub text: String,
8    pub children: Vec<Element>,
9}
10
11/// Deepest element nesting accepted. Everything that walks the tree
12/// (`from_node`, `split_widgets`, `Drop`) recurses once per level.
13/// The deepest real display nests about 8 levels; a small cap also bounds the
14/// stack used when displays are embedded in one another.
15pub const MAX_DEPTH: usize = 64;
16
17/// The deepest element nesting in `xml`, found by a quick scan without
18/// recursion, so it can run before the (recursive) XML parser.
19///
20/// It only has to be right for documents the parser (roxmltree) accepts, but
21/// it fails closed: markup it does not understand counts as infinitely deep.
22/// Comments, CDATA and processing instructions are skipped and quotes in tags
23/// are honoured. A `<!DOCTYPE>` (which usvg accepts) is skipped the way
24/// roxmltree reads it, but entities can expand to markup the scan never sees,
25/// so a DTD declaring any entity value with markup or references in it, or
26/// one roxmltree may read differently, counts as infinitely deep. Plain
27/// entities, such as the namespace URLs Adobe Illustrator declares, are fine.
28pub fn depth(xml: &str) -> usize {
29    let b = xml.as_bytes();
30    let (mut i, mut open, mut deepest) = (0, 0usize, 0usize);
31    while let Some(p) = b[i..].iter().position(|&c| c == b'<') {
32        i += p;
33        let rest = &b[i..];
34        let next = if rest.starts_with(b"<!--") {
35            skip_past(b, i + 4, b"-->")
36        } else if rest.starts_with(b"<![CDATA[") {
37            skip_past(b, i + 9, b"]]>")
38        } else if rest.starts_with(b"<?") {
39            skip_past(b, i + 2, b"?>")
40        } else if rest.starts_with(b"<!DOCTYPE") {
41            doctype_end(b, i + 9)
42        } else if rest.starts_with(b"<!") {
43            None
44        } else if rest.starts_with(b"</") {
45            open = open.saturating_sub(1);
46            skip_past(b, i + 2, b">")
47        } else {
48            // A start tag: find its closing `>`, outside any quoted value.
49            let mut j = i + 1;
50            let mut quote = None;
51            while j < b.len() {
52                match (quote, b[j]) {
53                    (None, b'>') => break,
54                    (None, q @ (b'"' | b'\'')) => quote = Some(q),
55                    (Some(q), c) if c == q => quote = None,
56                    _ => {}
57                }
58                j += 1;
59            }
60            deepest = deepest.max(open + 1);
61            if b[j - 1] != b'/' {
62                open += 1;
63            }
64            Some(j + 1)
65        };
66        match next {
67            Some(next) if next < b.len() => i = next,
68            Some(_) => break,
69            None => return usize::MAX,
70        }
71    }
72    deepest
73}
74
75/// Where the first `end` at or after `i` ends, or `None` if there is none.
76fn skip_past(b: &[u8], i: usize, end: &[u8]) -> Option<usize> {
77    let p = b.get(i..)?.windows(end.len()).position(|w| w == end)?;
78    Some(i + p + end.len())
79}
80
81/// Where the `<!DOCTYPE` whose name starts at `i` ends, read as roxmltree
82/// reads it (`tokenizer.rs`, `parse_doctype`). `None` if it declares
83/// something that could expand to markup (an entity value holding `<`, `&`
84/// or `%`, a parameter or external entity), or holds anything else roxmltree
85/// would not skip in the same way.
86fn doctype_end(b: &[u8], mut i: usize) -> Option<usize> {
87    let spaces = |mut i: usize| {
88        while b
89            .get(i)
90            .is_some_and(|c| matches!(c, b' ' | b'\t' | b'\n' | b'\r'))
91        {
92            i += 1;
93        }
94        i
95    };
96    let name = |mut i: usize| {
97        while b.get(i).is_some_and(|c| {
98            !matches!(
99                c,
100                b' ' | b'\t' | b'\n' | b'\r' | b'[' | b'>' | b'"' | b'\'' | b'%'
101            )
102        }) {
103            i += 1;
104        }
105        i
106    };
107    // A quoted literal starting at `i`: where it ends, and its value.
108    let quoted = |i: usize| -> Option<(usize, &[u8])> {
109        let q = *b.get(i).filter(|q| matches!(q, b'"' | b'\''))?;
110        let len = b[i + 1..].iter().position(|&c| c == q)?;
111        Some((i + len + 2, &b[i + 1..i + 1 + len]))
112    };
113    i = name(spaces(i));
114    i = spaces(i);
115    if b[i..].starts_with(b"SYSTEM") {
116        i = quoted(spaces(i + 6))?.0;
117    } else if b[i..].starts_with(b"PUBLIC") {
118        i = quoted(spaces(i + 6))?.0;
119        i = quoted(spaces(i))?.0;
120    }
121    i = spaces(i);
122    match b.get(i)? {
123        b'>' => return Some(i + 1),
124        b'[' => i += 1,
125        _ => return None,
126    }
127    // The internal subset.
128    loop {
129        i = spaces(i);
130        let rest = b.get(i..)?;
131        i = if rest.starts_with(b"<!ENTITY") {
132            // Only `<!ENTITY name "value">`, with a value free of markup and
133            // references: no parameter or external entities.
134            let (end, value) = quoted(spaces(name(spaces(i + 8))))?;
135            if value.iter().any(|c| matches!(c, b'<' | b'&' | b'%')) {
136                return None;
137            }
138            let end = spaces(end);
139            (b.get(end) == Some(&b'>')).then_some(end + 1)?
140        } else if rest.starts_with(b"<!--") {
141            skip_past(b, i + 4, b"-->")?
142        } else if rest.starts_with(b"<?") {
143            skip_past(b, i + 2, b"?>")?
144        } else if rest.starts_with(b"]") {
145            let end = spaces(i + 1);
146            return (b.get(end) == Some(&b'>')).then_some(end + 1);
147        } else if rest.starts_with(b"<!ELEMENT")
148            || rest.starts_with(b"<!ATTLIST")
149            || rest.starts_with(b"<!NOTATION")
150        {
151            // roxmltree skips these to the next `>`, quoted or not.
152            skip_past(b, i, b">")?
153        } else {
154            return None;
155        };
156    }
157}
158
159impl Element {
160    pub(crate) fn from_node(node: roxmltree::Node) -> Self {
161        let children: Vec<Element> = node
162            .children()
163            .filter(|c| c.is_element())
164            .map(Element::from_node)
165            .collect();
166        let text = if children.is_empty() {
167            node.children()
168                .filter_map(|c| c.text())
169                .collect::<String>()
170                .trim()
171                .to_string()
172        } else {
173            String::new()
174        };
175        Self {
176            name: node.tag_name().name().to_string(),
177            attrs: node
178                .attributes()
179                .map(|a| (a.name().to_string(), a.value().to_string()))
180                .collect(),
181            text,
182            children,
183        }
184    }
185
186    pub fn attr(&self, name: &str) -> Option<&str> {
187        self.attrs
188            .iter()
189            .find(|(k, _)| k == name)
190            .map(|(_, v)| v.as_str())
191    }
192
193    pub fn child(&self, name: &str) -> Option<&Element> {
194        self.children.iter().find(|c| c.name == name)
195    }
196
197    pub fn child_text(&self, name: &str) -> Option<&str> {
198        self.child(name).map(|c| c.text.as_str())
199    }
200}
201
202/// Builders and edits, used to translate `.opi` files.
203impl Element {
204    pub(crate) fn new(name: &str) -> Self {
205        Self {
206            name: name.to_string(),
207            ..Default::default()
208        }
209    }
210
211    pub(crate) fn with_text(name: &str, text: impl Into<String>) -> Self {
212        Self {
213            text: text.into(),
214            ..Self::new(name)
215        }
216    }
217
218    pub(crate) fn with_attr(mut self, name: &str, value: impl Into<String>) -> Self {
219        self.set_attr(name, value);
220        self
221    }
222
223    pub(crate) fn with_child(mut self, child: Element) -> Self {
224        self.children.push(child);
225        self
226    }
227
228    pub(crate) fn set_attr(&mut self, name: &str, value: impl Into<String>) {
229        let value = value.into();
230        match self.attrs.iter_mut().find(|(k, _)| k == name) {
231            Some((_, v)) => *v = value,
232            None => self.attrs.push((name.to_string(), value)),
233        }
234    }
235
236    pub(crate) fn child_mut(&mut self, name: &str) -> Option<&mut Element> {
237        self.children.iter_mut().find(|c| c.name == name)
238    }
239
240    /// Remove and return the first child called `name`.
241    pub(crate) fn take_child(&mut self, name: &str) -> Option<Element> {
242        let i = self.children.iter().position(|c| c.name == name)?;
243        Some(self.children.remove(i))
244    }
245
246    /// Replace the child called `child.name`, or add it.
247    pub(crate) fn set_child(&mut self, child: Element) {
248        match self.child_mut(&child.name) {
249            Some(c) => *c = child,
250            None => self.children.push(child),
251        }
252    }
253}
254
255#[cfg(test)]
256mod depth_tests {
257    use super::depth;
258
259    #[test]
260    fn counts_nesting_ignoring_markup_that_is_not_elements() {
261        assert_eq!(depth("<a/>"), 1);
262        assert_eq!(depth("<a><b/><b><c x='>'/></b></a>"), 3);
263        assert_eq!(
264            depth("<a><!-- <b><b><b> --><![CDATA[<c><c>]]><?pi <d> ?></a>"),
265            1
266        );
267        assert_eq!(depth("<a x=\"<\"><b></b><b></b></a>"), 2);
268        assert_eq!(depth(""), 0);
269        assert_eq!(depth("<a><b"), 2);
270    }
271
272    #[test]
273    fn doctypes_are_skipped_but_markup_entities_are_too_deep() {
274        let nest = format!("<svg>{}{}</svg>", "<g>".repeat(50), "</g>".repeat(50));
275        let dt = |dtd: &str| depth(&format!("<?xml version=\"1.0\"?>\n{dtd}\n{nest}"));
276        assert_eq!(dt("<!DOCTYPE svg>"), 51);
277        assert_eq!(
278            dt(
279                r#"<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">"#
280            ),
281            51
282        );
283        // As Adobe Illustrator writes them.
284        let illustrator = r#"<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "x.dtd" [
285            <!ENTITY ns_extend "http://ns.adobe.com/Extensibility/1.0/">
286            <!-- a ] comment > with "quotes -->
287            <!ENTITY ns_svg "http://www.w3.org/2000/svg">
288        ]>"#;
289        assert_eq!(dt(illustrator), 51);
290        for dtd in [
291            r#"<!DOCTYPE svg [<!ENTITY e "<g><g></g></g>">]>"#,
292            r#"<!DOCTYPE svg [<!ENTITY e '&#60;g>'>]>"#,
293            r#"<!DOCTYPE svg [<!ENTITY e "&f;">]>"#,
294            r#"<!DOCTYPE svg [<!ENTITY % p "x"> %p;]>"#,
295            r#"<!DOCTYPE svg [<!ENTITY e "x"#,
296            r#"<!DOCTYPE svg [<!ENTITY e SYSTEM "x.xml">]>"#,
297            // roxmltree skips declarations to the next `>`, so this `]`
298            // does not end the subset and the entity is still declared.
299            r#"<!DOCTYPE svg [<!ELEMENT x ]><!ENTITY e "<g>">]>"#,
300            r#"<!DOCTYPE svg [<!ATTLIST x y CDATA "]>"><!ENTITY e "<g>">]>"#,
301            // Anything the scan does not know.
302            r#"<!DOCTYPE svg [<!FOO>]>"#,
303            r#"<!DOCTYPE svg [] x>"#,
304        ] {
305            assert_eq!(dt(dtd), usize::MAX, "{dtd}");
306        }
307        // Declarations roxmltree skips are skipped.
308        assert_eq!(
309            dt(
310                r#"<!DOCTYPE svg [<!ELEMENT x ]><!ATTLIST a b CDATA "x"><!NOTATION n SYSTEM "n">]>"#
311            ),
312            51
313        );
314        // Markup the parser would reject is too deep, not the end of the scan.
315        assert_eq!(depth("<a><!FOO><b><c/></b></a>"), usize::MAX);
316    }
317
318    /// The deepest element nesting roxmltree finds in `xml`, if it parses.
319    fn parsed_depth(xml: &str) -> Option<usize> {
320        let options = roxmltree::ParsingOptions {
321            allow_dtd: true,
322            ..Default::default()
323        };
324        let doc = roxmltree::Document::parse_with_options(xml, options).ok()?;
325        doc.descendants()
326            .filter(|n| n.is_element())
327            .map(|n| n.ancestors().filter(|a| a.is_element()).count())
328            .max()
329    }
330
331    /// Random documents made of the pieces that matter to the scan: it never
332    /// finds a document roxmltree parses shallower than roxmltree does.
333    #[test]
334    fn never_shallower_than_roxmltree() {
335        const DTD: &[&str] = &[
336            " ",
337            "<!ELEMENT x ]>",
338            "<!ELEMENT x (a|b)*>",
339            r#"<!ATTLIST a b CDATA "]>">"#,
340            r#"<!ATTLIST a b CDATA ']'>"#,
341            "<!NOTATION n SYSTEM 'n'>",
342            r#"<!ENTITY p "v">"#,
343            r#"<!ENTITY m "<a><a></a></a>">"#,
344            r#"<!ENTITY r "&p;">"#,
345            r#"<!ENTITY q ']>'>"#,
346            "<!-- ] > -->",
347            "<?p ]> ?>",
348            "]",
349            ">",
350            "]>",
351            "\"",
352            "'",
353            "<!ENTITY",
354            "<!",
355            "<a>",
356            "</a>",
357            "&m;",
358        ];
359        const BODY: &[&str] = &[
360            "<a>",
361            "</a>",
362            "<a/>",
363            "<b x='>'/>",
364            "<b x=\"/\">",
365            "</b>",
366            "<!--<a>-->",
367            "<![CDATA[<a>]]>",
368            "<?p <a> ?>",
369            "t",
370            "&p;",
371            "&m;",
372            "&q;",
373            "&r;",
374            "<!",
375            ">",
376            "]]>",
377            "&lt;a>",
378            "\"",
379            "<!DOCTYPE a>",
380            "<b x=\"/\"></b>",
381        ];
382        let mut seed = 0x9E37_79B9_7F4A_7C15u64;
383        let mut rand = |n: usize| {
384            seed ^= seed << 13;
385            seed ^= seed >> 7;
386            seed ^= seed << 17;
387            (seed % n as u64) as usize
388        };
389        let (mut parsed, mut deep) = (0, 0);
390        for _ in 0..200_000 {
391            let mut xml = String::new();
392            if rand(4) > 0 {
393                xml += "<!DOCTYPE r [";
394                for _ in 0..rand(5) {
395                    xml += DTD[rand(DTD.len())];
396                }
397                xml += "]>";
398            }
399            // Mostly balanced, so that many parse.
400            xml += "<r>";
401            let mut open = 0;
402            for _ in 0..rand(12) {
403                let token = BODY[rand(BODY.len())];
404                match token {
405                    "<a>" => open += 1,
406                    "</a>" if open == 0 => continue,
407                    "</a>" => open -= 1,
408                    _ => {}
409                }
410                xml += token;
411            }
412            xml += &"</a>".repeat(open);
413            xml += "</r>";
414            if let Some(real) = parsed_depth(&xml) {
415                parsed += 1;
416                deep += usize::from(real > 2);
417                assert!(depth(&xml) >= real, "{xml}: scan {} < {real}", depth(&xml));
418            }
419        }
420        // The generator does reach documents worth checking.
421        assert!(parsed > 1000 && deep > 100, "{parsed} parsed, {deep} deep");
422    }
423}
bob/element.rs

bob/
element.rs
