alpha2-extensions 0.6.1

Extension providers that supply frames of formats the host decoders do not read: SVG, animated images, Lottie, OpenEXR, image sequences, LaTeX math, PDF pages.
Documentation
//! Element nesting and entity expansion, measured from the raw text before any XML parser runs.
//!
//! The XML parser, usvg, and resvg all recurse per nesting level, so a few thousand levels
//! overflow the stack (aborting natively, trapping in wasm). This non-recursive scan refuses
//! documents deeper than [`super::MAX_NESTING`], and sums the bytes entity references expand to
//! in text and attribute values, which the parser copies or reads. It is not a validating parser;
//! it must only never count less than the parser would.

use std::collections::HashMap;

use crate::api::ExtensionError;

/// Entity reference nesting roxmltree allows; deeper is reported with its error.
const MAX_ENTITY_DEPTH: usize = 10;

/// The bytes every entity reference in `text` expands to, in text and attribute values, summed;
/// or [`ExtensionError::Budget`] once its elements nest past `limit`, entity expansions included.
pub(super) fn entity_expansion(text: &str, limit: usize) -> Result<usize, ExtensionError> {
    measure(text, limit).map(|(_, expanded)| expanded)
}

/// The deepest element nesting in `text` and the bytes its entity references expand to.
fn measure(text: &str, limit: usize) -> Result<(usize, usize), ExtensionError> {
    let mut scan = Scan {
        entities: HashMap::new(),
        measured: HashMap::new(),
        limit,
    };
    scan.content(text.as_bytes(), 0, 0)
}

struct Scan<'a> {
    /// Declared general entities; the first declaration of a name wins.
    entities: HashMap<&'a [u8], &'a [u8]>,
    /// Each measured entity's depth and the bytes one reference to it expands to; `None` while
    /// measuring, to detect loops.
    measured: HashMap<&'a [u8], Option<(usize, usize)>>,
    limit: usize,
}

impl<'a> Scan<'a> {
    /// The deepest nesting in `bytes`, starting `base` levels and `entities` references deep, and
    /// the bytes its entity references expand to.
    fn content(
        &mut self,
        bytes: &'a [u8],
        base: usize,
        entities: usize,
    ) -> Result<(usize, usize), ExtensionError> {
        let mut depth = base;
        let mut deepest = base;
        let mut expanded = 0_usize;
        let mut at = 0;
        while let Some(offset) = bytes[at..].iter().position(|&b| b == b'<' || b == b'&') {
            at += offset;
            let rest = &bytes[at..];
            if rest[0] == b'&' {
                let Some(end) = rest.iter().position(|&b| b == b';') else {
                    break;
                };
                at += end + 1;
                let Some((nested, bytes)) = self.reference(&rest[1..end], entities)? else {
                    continue;
                };
                expanded = expanded.saturating_add(bytes);
                deepest = deepest.max(self.within(depth.saturating_add(nested))?);
                continue;
            }
            let skipped = if rest.starts_with(b"<!--") {
                after(rest, 4, b"-->")
            } else if rest.starts_with(b"<![CDATA[") {
                after(rest, 9, b"]]>")
            } else if rest.starts_with(b"<?") {
                after(rest, 2, b"?>")
            } else if rest.starts_with(b"<!DOCTYPE") {
                self.doctype(rest, 9)
            } else if rest.starts_with(b"</") {
                depth = depth.saturating_sub(1);
                after(rest, 2, b">")
            } else {
                let mut values = Vec::new();
                let Some(end) = tag_end(rest, Some(&mut values)) else {
                    break;
                };
                for (start, end) in values {
                    let bytes = self.references_in_value(&rest[start..end], entities)?;
                    expanded = expanded.saturating_add(bytes);
                }
                deepest = deepest.max(self.within(depth + 1)?);
                if rest[end - 1] != b'/' {
                    depth += 1;
                }
                Some(end + 1)
            };
            let Some(skipped) = skipped else {
                break;
            };
            at += skipped;
        }
        Ok((deepest, expanded))
    }

    /// Bytes the entity references in a quoted attribute value expand to.
    fn references_in_value(
        &mut self,
        value: &'a [u8],
        entities: usize,
    ) -> Result<usize, ExtensionError> {
        let mut expanded = 0_usize;
        let mut rest = value;
        while let Some(start) = rest.iter().position(|&b| b == b'&') {
            let Some(end) = rest[start..].iter().position(|&b| b == b';') else {
                break;
            };
            let name = &rest[start + 1..start + end];
            rest = &rest[start + end + 1..];
            if let Some((_, bytes)) = self.reference(name, entities)? {
                expanded = expanded.saturating_add(bytes);
            }
        }
        Ok(expanded)
    }

    /// The levels and bytes a reference to `name` adds; `None` for a character reference or a
    /// predefined entity, which expand to one character.
    fn reference(
        &mut self,
        name: &'a [u8],
        entities: usize,
    ) -> Result<Option<(usize, usize)>, ExtensionError> {
        if name.first() == Some(&b'#') || matches!(name, b"lt" | b"gt" | b"amp" | b"apos" | b"quot")
        {
            return Ok(None);
        }
        self.entity(name, entities).map(Some)
    }

    fn within(&self, depth: usize) -> Result<usize, ExtensionError> {
        if depth > self.limit {
            return Err(ExtensionError::Budget(format!(
                "the SVG's elements nest more than {} deep",
                self.limit
            )));
        }
        Ok(depth)
    }

    /// Levels a reference to entity `name` adds (one plus its replacement text's depth) and the
    /// bytes it expands to (its replacement text plus what the references in it expand to).
    fn entity(
        &mut self,
        name: &'a [u8],
        entities: usize,
    ) -> Result<(usize, usize), ExtensionError> {
        let loop_error = || {
            ExtensionError::Malformed(
                "SVG data parsing failed cause a possible entity reference loop is detected".into(),
            )
        };
        match self.measured.get(name) {
            Some(Some(measured)) => return Ok(*measured),
            Some(None) => return Err(loop_error()),
            None => {}
        }
        if entities >= MAX_ENTITY_DEPTH {
            return Err(loop_error());
        }
        // An unknown entity is the parser's error.
        let Some(&value) = self.entities.get(name) else {
            return Ok((0, 0));
        };
        self.measured.insert(name, None);
        let (depth, expanded) = self.content(value, 0, entities + 1)?;
        let measured = (depth + 1, value.len().saturating_add(expanded));
        self.measured.insert(name, Some(measured));
        Ok(measured)
    }

    /// The end of a doctype declaration in `rest`, recording its general entities.
    fn doctype(&mut self, rest: &'a [u8], mut at: usize) -> Option<usize> {
        // The name and external identifier, up to the internal subset or the end.
        loop {
            match *rest.get(at)? {
                quote @ (b'"' | b'\'') => at += 1 + find(&rest[at + 1..], &[quote])? + 1,
                b'[' => break,
                b'>' => return Some(at + 1),
                _ => at += 1,
            }
        }
        at += 1;
        loop {
            let subset = &rest[at..];
            let next = subset.iter().position(|b| !b.is_ascii_whitespace())?;
            at += next;
            let subset = &rest[at..];
            at += if subset.starts_with(b"]") {
                return Some(at + after(subset, 1, b">")?);
            } else if subset.starts_with(b"<!--") {
                after(subset, 4, b"-->")?
            } else if subset.starts_with(b"<?") {
                after(subset, 2, b"?>")?
            } else if subset.starts_with(b"<!ENTITY") {
                self.entity_declaration(subset)?
            } else if subset.starts_with(b"<") {
                tag_end(subset, None)? + 1
            } else {
                // A parameter entity reference, or what the parser refuses.
                1
            };
        }
    }

    /// The end of an entity declaration, recording a general entity's replacement text.
    fn entity_declaration(&mut self, decl: &'a [u8]) -> Option<usize> {
        let end = tag_end(decl, None)?;
        let mut words = decl[8..end].trim_ascii_start();
        let general = !words.starts_with(b"%");
        if !general {
            words = words[1..].trim_ascii_start();
        }
        let name_end = words
            .iter()
            .position(|b| b.is_ascii_whitespace() || matches!(b, b'"' | b'\''))?;
        let name = &words[..name_end];
        let definition = words[name_end..].trim_ascii_start();
        if general
            && let Some(&quote) = definition.first()
            && matches!(quote, b'"' | b'\'')
            && let Some(close) = find(&definition[1..], &[quote])
        {
            self.entities.entry(name).or_insert(&definition[1..=close]);
        }
        Some(end + 1)
    }
}

fn find(bytes: &[u8], needle: &[u8]) -> Option<usize> {
    bytes
        .windows(needle.len())
        .position(|window| window == needle)
}

/// The offset just past the first `closing` after `from`.
fn after(bytes: &[u8], from: usize, closing: &[u8]) -> Option<usize> {
    Some(from + find(bytes.get(from..)?, closing)? + closing.len())
}

/// The `>` ending the tag at the start of `bytes`, skipping quoted values, whose ranges go to
/// `values` when given.
fn tag_end(bytes: &[u8], mut values: Option<&mut Vec<(usize, usize)>>) -> Option<usize> {
    let mut at = 1;
    loop {
        match *bytes.get(at)? {
            quote @ (b'"' | b'\'') => {
                let close = at + 1 + find(&bytes[at + 1..], &[quote])?;
                if let Some(values) = values.as_mut() {
                    values.push((at + 1, close));
                }
                at = close + 1;
            }
            b'>' => return Some(at),
            _ => at += 1,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::{entity_expansion, measure};

    fn nesting(text: &str, limit: usize) -> Result<usize, crate::ExtensionError> {
        measure(text, limit).map(|(depth, _)| depth)
    }

    fn depth(text: &str) -> usize {
        nesting(text, usize::MAX).expect("measured")
    }

    fn expanded(text: &str) -> usize {
        entity_expansion(text, usize::MAX).expect("measured")
    }

    #[test]
    fn elements_nest_as_they_open_and_close() {
        assert_eq!(depth("<svg/>"), 1);
        assert_eq!(depth("<svg><g><rect/></g><g/></svg>"), 3);
        assert_eq!(
            depth(r#"<svg a="<g>" b='>'><!-- <g><g> --><![CDATA[<g><g>]]><?pi <g>?><g></g></svg>"#),
            2
        );
        let deep = format!("<svg>{}{}</svg>", "<g>".repeat(40), "</g>".repeat(40));
        assert_eq!(depth(&deep), 41);
        assert!(nesting(&deep, 40).is_err());
        assert_eq!(nesting(&deep, 41).ok(), Some(41));
    }

    #[test]
    fn an_entity_nests_as_deep_as_its_replacement_text_where_it_is_used() {
        let text = r#"<?xml version="1.0"?>
<!DOCTYPE svg [
  <!ENTITY ns "http://www.w3.org/2000/svg">
  <!ENTITY one "<g><g/></g>">
  <!ENTITY two '<g>&one;&one;</g>'>
  <!ENTITY % parameter "<g><g><g><g></g></g></g></g>">
  <!-- <!ENTITY three "<g><g><g></g></g></g>"> -->
]>
<svg xmlns="&ns;"><g>&two;</g></svg>"#;
        // svg, g, then two: its entity level, g, one's entity level, g, g.
        assert_eq!(depth(text), 7);
    }

    #[test]
    fn entities_inside_one_another_too_deep_or_in_a_loop_are_refused() {
        let declarations: String = std::iter::once(r#"<!ENTITY e0 "<g/>">"#.to_owned())
            .chain((1..=11).map(|level| format!(r#"<!ENTITY e{level} "&e{};">"#, level - 1)))
            .collect();
        let text = |entity: usize| format!("<!DOCTYPE svg [{declarations}]><svg>&e{entity};</svg>");
        assert_eq!(depth(&text(9)), 12);
        assert!(nesting(&text(10), usize::MAX).is_err());
        let looping = r#"<!DOCTYPE svg [<!ENTITY a "&b;"><!ENTITY b "&a;">]><svg>&a;</svg>"#;
        assert!(nesting(looping, usize::MAX).is_err());
    }

    #[test]
    fn an_entity_expands_to_its_text_and_the_entities_it_names() {
        // b is 4 bytes; a is 10 bytes plus three b; the body names a twice.
        let text = r#"<!DOCTYPE svg [<!ENTITY b "<g/>"><!ENTITY a "x&b;&b;&b;">]><svg>&a;&a;&amp;&#65;</svg>"#;
        assert_eq!(expanded(text), 2 * (10 + 3 * 4));
        let unknown = "<svg>&nothing;</svg>";
        assert_eq!(expanded(unknown), 0);
    }

    #[test]
    fn an_entity_in_an_attribute_value_counts_as_it_expands() {
        let text = |references: usize| {
            format!(
                r#"<!DOCTYPE svg [<!ENTITY t "{}"><!ENTITY m "{}">]><svg id='{}' class="&t;"/>"#,
                "x".repeat(1000),
                "&t;".repeat(255),
                "&m;".repeat(references)
            )
        };
        let one = 255 * 3 + 255 * 1000;
        assert_eq!(expanded(&text(1)), one + 1000);
        assert_eq!(expanded(&text(100)), 100 * one + 1000);
        assert_eq!(nesting(&text(100), usize::MAX).expect("measured"), 1);
    }
}