2bc41aeb8602
budget.rs
//! What usvg makes of an SVG, measured in the XML before usvg runs: how many elements it makes,
//! and how many bytes of style values it copies into them.
//!
//! usvg makes an element of each SVG element, and of each element a `<use>` shows a copy of, by
//! copying what the `<use>` refers to. Each copy gets its own copy of every declaration the style
//! sheets and the `style` attribute give the element, so a long style on an element that `<use>`s
//! copy, again and again in a chain, or that a style sheet rule gives to many elements, takes more
//! memory than the file holds many times over. usvg stops past 1,000,000 elements, but only after
//! it has made them and copied their styles. An SVG past [`MAX_SVG_ELEMENTS`] elements or
//! [`MAX_COPIED_STYLES`] bytes of copied styles is refused here instead.
//!
//! The copies are counted, never made: each element's count is worked out once and added up, so a
//! `<use>` of an element costs one addition, however many elements its copy holds. References
//! follow usvg 0.48.1 (`parser/svgtree/parse.rs`): an id names the first element that has it, an
//! unprefixed `href` wins over `xlink:href`, and a `<use>` of itself, of the `<use>` its own copy
//! starts from, or of an element holding a `<use>` of the element or of the `<use>`, is left out.
//! Any other loop of references makes usvg copy without end, so an SVG with one is refused. usvg
//! looks for those `<use>`s inside an element only in the SVG namespace: in an SVG without one, a
//! `<use>` that leads back to the `<use>` its copy starts from is refused here too, though usvg
//! would leave it out.
//!
//! The style sheets' rules are matched against each element once, as usvg matches them against
//! each copy. usvg tests a selector against an element without keeping what it found, so a
//! selector whose leftmost part matches nothing can test every set of ancestors in turn: the tests
//! usvg makes for each copy are counted, and an SVG past [`MAX_SELECTOR_TESTS`] of them is refused.
//! A look at an attribute counts one test for every 16 attributes of the element it scans, and one
//! for every 16 bytes of the value it compares. Matching stops once the tests pass what is left of
//! the limit.
//!
//! The import's own style cascade (`css::Styles`) keeps the declarations of the rules that match
//! each element, once per element, and reads selectors usvg drops (`:not()`). What it keeps and the
//! tests it makes count toward the same limits, measured before it runs.
use std::cell::Cell;
use std::collections::{HashMap, HashSet};
use usvg::roxmltree;
use super::{MAX_NODES, SVG_NS, XNode, css};
use crate::{MAX_ELEMENT_DEPTH, SvgError};
/// Most elements usvg may make of an SVG: [`MAX_NODES`], and below the 1,000,000 elements past
/// which usvg stops (its count includes a root of its own).
pub(crate) const MAX_SVG_ELEMENTS: usize = if MAX_NODES < 999_999 { MAX_NODES } else { 999_999 };
/// Most bytes of style values usvg may copy into the elements of an SVG and the SVG images it
/// shows, all together: VectorCraft's own limit.
pub(crate) const MAX_COPIED_STYLES: u64 = 64 << 20;
/// Most tests of a style sheet selector's parts against elements an SVG and the SVG images it
/// shows may take, all together: VectorCraft's own limit.
pub(crate) const MAX_SELECTOR_TESTS: u64 = 50_000_000;
/// What usvg keeps for each value it copies besides its bytes (the count and length of a shared
/// string).
const COPY: u64 = 16;
/// The longhands a `font` shorthand resets before setting the ones it gives, and the most bytes of
/// each reset value (`normal`).
const FONT_RESETS: u64 = 12;
const RESET_VALUE: u64 = 6;
/// The longhands a `font` shorthand sets from its own text.
const FONT_PARTS: u64 = 6;
const XLINK_NS: &str = "http://www.w3.org/1999/xlink";
/// The elements usvg reads (`EId` in usvg's `parser/svgtree/names.rs`); it skips the others with
/// everything inside them.
const ELEMENTS: [&str; 53] = [
"a",
"circle",
"clipPath",
"defs",
"ellipse",
"feBlend",
"feColorMatrix",
"feComponentTransfer",
"feComposite",
"feConvolveMatrix",
"feDiffuseLighting",
"feDisplacementMap",
"feDistantLight",
"feDropShadow",
"feFlood",
"feFuncA",
"feFuncB",
"feFuncG",
"feFuncR",
"feGaussianBlur",
"feImage",
"feMerge",
"feMergeNode",
"feMorphology",
"feOffset",
"fePointLight",
"feSpecularLighting",
"feSpotLight",
"feTile",
"feTurbulence",
"filter",
"g",
"image",
"line",
"linearGradient",
"marker",
"mask",
"path",
"pattern",
"polygon",
"polyline",
"radialGradient",
"rect",
"stop",
"style",
"svg",
"switch",
"symbol",
"text",
"textPath",
"tref",
"tspan",
"use",
];
/// The name of element `n` when usvg reads it: in the SVG namespace or none, and one of
/// [`ELEMENTS`].
fn svg_name<'a>(n: XNode<'a, '_>) -> Option<&'a str> {
let name = n.tag_name();
(n.is_element() && matches!(name.namespace(), None | Some(SVG_NS)) && ELEMENTS.contains(&name.name())).then(|| name.name())
}
#[cfg(test)]
thread_local! {
/// The selector tests the last measurement on this thread made as usvg matches the style
/// sheets, as far as it got.
static USVG_TESTS: Cell<u64> = const { Cell::new(0) };
}
/// An element as the style sheets' selectors see it, as usvg matches them. Each look at it counts
/// as tests in `tests`; past `most` it has no parent or sibling and matches nothing, so the
/// matching ends.
struct Element<'a, 'i, 't> {
node: XNode<'a, 'i>,
tests: &'t Cell<u64>,
most: u64,
}
impl<'a, 'i, 't> Element<'a, 'i, 't> {
/// Counts `n` tests: false past `most`.
fn test(&self, n: u64) -> bool {
let tests = self.tests.get().saturating_add(n);
self.tests.set(tests);
#[cfg(test)]
USVG_TESTS.set(tests);
tests <= self.most
}
fn of(&self, node: Option<XNode<'a, 'i>>) -> Option<Self> {
node.filter(|_| self.test(1)).map(|node| Element { node, tests: self.tests, most: self.most })
}
}
impl simplecss::Element for Element<'_, '_, '_> {
fn parent_element(&self) -> Option<Self> {
self.of(self.node.parent_element())
}
fn prev_sibling_element(&self) -> Option<Self> {
self.of(self.node.prev_sibling_element())
}
fn has_local_name(&self, name: &str) -> bool {
self.test(1) && self.node.tag_name().name() == name
}
fn attribute_matches(&self, name: &str, operator: simplecss::AttributeOperator<'_>) -> bool {
// The lookup scans the element's attributes, and the match the value.
let value = self.node.attribute(name);
let scanned = css::scan_tests(self.node.attributes().len()).saturating_add(value.map_or(0, |v| css::scan_tests(v.len())));
self.test(scanned) && value.is_some_and(|value| operator.matches(value))
}
fn pseudo_class_matches(&self, class: simplecss::PseudoClass<'_>) -> bool {
self.test(1) && matches!(class, simplecss::PseudoClass::FirstChild) && self.node.prev_sibling_element().is_none()
}
}
/// The bytes usvg copies for one declaration: three markers for `marker`, the resets and longhands
/// for `font`, its value for any other. Counted for every declaration, the ones usvg then drops (a
/// property it doesn't read, a value an earlier one overrides) too.
fn copied(declaration: &simplecss::Declaration) -> u64 {
let len = declaration.value.len() as u64;
match declaration.name {
"marker" => 3 * (COPY + len),
"font" => (FONT_RESETS + FONT_PARTS) * COPY + FONT_RESETS * RESET_VALUE + len,
_ => COPY + len,
}
}
/// What usvg makes of an element or an SVG: elements (text nodes included), bytes of copied
/// styles and selector tests.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub(crate) struct Cost {
pub(crate) elements: u64,
pub(crate) bytes: u64,
pub(crate) tests: u64,
}
impl Cost {
/// The most an SVG and the SVG images it shows may cost together.
pub(crate) const LIMITS: Cost = Cost { elements: MAX_SVG_ELEMENTS as u64, bytes: MAX_COPIED_STYLES, tests: MAX_SELECTOR_TESTS };
pub(crate) fn add(self, other: Cost) -> Cost {
Cost {
elements: self.elements.saturating_add(other.elements),
bytes: self.bytes.saturating_add(other.bytes),
tests: self.tests.saturating_add(other.tests),
}
}
/// What is left of `self` after `spent`.
pub(crate) fn less(self, spent: Cost) -> Cost {
Cost {
elements: self.elements.saturating_sub(spent.elements),
bytes: self.bytes.saturating_sub(spent.bytes),
tests: self.tests.saturating_sub(spent.tests),
}
}
}
/// What a `<use>` shows: nothing, the element it refers to with all it holds, or only that
/// element (a `<use>` whose own reference leads back to the `<use>` showing it).
enum Shows<'a, 'i> {
Nothing,
All(XNode<'a, 'i>),
Bare(XNode<'a, 'i>),
}
struct Measure<'a, 'i> {
/// The first element of each id.
ids: HashMap<&'a str, XNode<'a, 'i>>,
sheet: simplecss::StyleSheet<'a>,
/// The selector tests made of `sheet` so far, each element once.
tests: Cell<u64>,
/// The most selector tests of `sheet` that are left: matching stops past them.
most_tests: u64,
/// The selector tests the import's own cascade made ([`Measure::cascade`]).
cascade_tests: Cell<u64>,
/// The import's own style cascade of the same style sheets.
cascade: css::Styles,
/// The elements that hold a `<use>` of themselves.
holds_use_of_itself: HashSet<roxmltree::NodeId>,
/// The `<use>`s of each element, by the element.
used_by: HashMap<roxmltree::NodeId, Vec<XNode<'a, 'i>>>,
/// The bytes of text in each element a `<tref>` shows.
tref_text: HashMap<roxmltree::NodeId, u64>,
}
impl<'a, 'i> Measure<'a, 'i> {
fn new(xml: &'a roxmltree::Document<'i>) -> Self {
let mut ids = HashMap::new();
for n in xml.descendants() {
if let Some(id) = n.attribute("id") {
ids.entry(id).or_insert(n);
}
}
// The style sheets usvg reads: `<style>` elements of no type or of `text/css`, the first
// text of each.
let mut sheet = simplecss::StyleSheet::new();
for n in xml.descendants().filter(|n| n.has_tag_name("style")) {
if n.attribute("type").is_none_or(|t| t == "text/css")
&& let Some(text) = n.text()
{
sheet.parse_more(text);
}
}
let mut m = Measure {
ids,
sheet,
tests: Cell::new(0),
most_tests: MAX_SELECTOR_TESTS,
cascade_tests: Cell::new(0),
cascade: css::Styles::new(xml),
holds_use_of_itself: HashSet::new(),
used_by: HashMap::new(),
tref_text: HashMap::new(),
};
for u in xml.descendants().filter(|n| n.has_tag_name((SVG_NS, "use"))) {
let Some(target) = m.target(u) else { continue };
if u.ancestors().skip(1).any(|a| a == target) {
m.holds_use_of_itself.insert(target.id());
}
m.used_by.entry(target.id()).or_default().push(u);
}
m
}
/// The element `<use>` `u` refers to, as usvg resolves it.
fn target(&self, u: XNode<'a, 'i>) -> Option<XNode<'a, 'i>> {
let link = u
.attributes()
.find(|a| a.name() == "href" && a.namespace().is_none())
.or_else(|| u.attributes().find(|a| a.name() == "href" && a.namespace() == Some(XLINK_NS)))?;
let id = svgtypes::IRI::from_str(link.value()).ok()?.0;
self.ids.get(id).copied()
}
/// What `<use>` `u` shows: see the module docs.
fn shows(&self, u: XNode<'a, 'i>) -> Shows<'a, 'i> {
let Some(link) = self.target(u) else { return Shows::Nothing };
if link == u || svg_name(link).is_none() {
return Shows::Nothing;
}
let inside = |v: &XNode| v.ancestors().skip(1).any(|a| a == link);
if self.holds_use_of_itself.contains(&link.id()) || self.used_by.get(&u.id()).is_some_and(|uses| uses.iter().any(inside)) {
return Shows::Nothing;
}
if svg_name(link) == Some("use") && self.target(link) == Some(u) {
return Shows::Bare(link);
}
Shows::All(link)
}
/// Element `n` alone, as usvg makes one copy of it: the bytes of style values it copies into
/// it, and the selector tests usvg makes to find them (each rule tested counts as one too).
fn own(&self, n: XNode) -> Cost {
let before = self.tests.get();
let mut bytes = 0u64;
for rule in &self.sheet.rules {
self.tests.set(self.tests.get().saturating_add(1));
if rule.selector.matches(&Element { node: n, tests: &self.tests, most: self.most_tests }) {
bytes = rule.declarations.iter().map(copied).fold(bytes, u64::saturating_add);
}
}
if let Some(style) = n.attribute("style") {
bytes = simplecss::DeclarationTokenizer::from(style).map(|d| copied(&d)).fold(bytes, u64::saturating_add);
}
Cost { elements: 1, bytes, tests: self.tests.get().saturating_sub(before) }
}
/// Have the selector tests made so far passed what is left of them?
fn tests_past(&self) -> bool {
self.tests.get() > self.most_tests
}
/// What the import's own style cascade keeps for the elements of `xml`, each once, up to
/// `left`: the bytes of the declarations of the rules that match it, and the tests it makes to
/// find them.
/// The tests it makes are kept in `cascade_tests`, as far as it gets.
fn cascade(&self, xml: &roxmltree::Document, left: Cost) -> Result<Cost, Past> {
let mut cost = Cost::default();
if !self.cascade.has_rules() {
return Ok(cost);
}
let mut result = Ok(());
for n in xml.descendants().filter(XNode::is_element) {
let Some(bytes) = self.cascade.matched_bytes(n, COPY, &mut cost.tests, left.tests) else {
result = Err(Past::Tests);
break;
};
cost.bytes = cost.bytes.saturating_add(bytes);
if cost.bytes > left.bytes {
result = Err(Past::Bytes);
break;
}
}
self.cascade_tests.set(cost.tests);
result.map(|()| cost)
}
/// `<text>` `t` and what usvg makes of what it holds: at most an element of each element, and
/// a copy of each run of text and of the text each `<tref>` shows.
fn text(&mut self, t: XNode<'a, 'i>) -> Cost {
let mut cost = self.own(t);
for d in t.descendants().skip(1) {
if d.is_text() {
let len = d.text().map_or(0, str::len) as u64;
cost = cost.add(Cost { elements: 1, bytes: COPY + len, tests: 0 });
} else if svg_name(d).is_some() {
cost = cost.add(self.own(d));
if svg_name(d) == Some("tref") {
cost = cost.add(Cost { elements: 1, bytes: COPY + self.tref(d), tests: 0 });
}
}
}
cost
}
/// The bytes of text `<tref>` `r` shows.
fn tref(&mut self, r: XNode<'a, 'i>) -> u64 {
let link = r.attribute((XLINK_NS, "href")).or_else(|| r.attribute("href"));
let Some(target) = link.and_then(|l| svgtypes::IRI::from_str(l).ok()).and_then(|iri| self.ids.get(iri.0).copied()) else { return 0 };
*self.tref_text.entry(target.id()).or_insert_with(|| {
target.descendants().filter(|n| n.is_text()).filter_map(|n| n.text()).map(|t| t.len() as u64).fold(0, u64::saturating_add)
})
}
}
/// What usvg would make of `xml`, with what the import's own style cascade keeps of it and the
/// selector tests it makes, when that is no more than `left` and nested no deeper than `depth`
/// (counted as `depth::height` counts, which finds at least as much).
pub(super) fn check(xml: &roxmltree::Document, left: Cost, depth: usize) -> Result<Cost, SvgError> {
check_spending(xml, left, depth).0
}
/// [`check`], with the selector tests it made, as far as it got.
pub(super) fn check_spending(xml: &roxmltree::Document, left: Cost, depth: usize) -> (Result<Cost, SvgError>, u64) {
let (result, tests) = measure_spending(xml, left, depth);
let result = result.map_err(|past| match past {
Past::Elements => SvgError::TooLarge(MAX_SVG_ELEMENTS),
Past::Bytes => SvgError::StylesTooLarge((MAX_COPIED_STYLES >> 20) as usize),
Past::Tests => SvgError::StylesTooComplex,
Past::Depth => SvgError::TooDeep(MAX_ELEMENT_DEPTH),
});
(result, tests)
}
/// The limit [`measure`] stopped at.
#[derive(Debug, PartialEq)]
enum Past {
Elements,
Bytes,
Tests,
Depth,
}
/// What usvg makes of `xml` with what the import's own style cascade keeps of it and its tests,
/// up to `left`, its elements and the copies `<use>`s show nested up to `depth` deep. Without
/// recursion; each element is measured once.
#[cfg(test)]
fn measure(xml: &roxmltree::Document, left: Cost, depth: usize) -> Result<Cost, Past> {
measure_spending(xml, left, depth).0
}
/// [`measure`], with the selector tests it made, as far as it got.
fn measure_spending(xml: &roxmltree::Document, left: Cost, depth: usize) -> (Result<Cost, Past>, u64) {
let mut m = Measure::new(xml);
let result = walk(&mut m, xml, left, depth);
(result, m.cascade_tests.get().saturating_add(m.tests.get()))
}
/// [`measure`] with `m`, made of `xml`.
fn walk<'a, 'i>(m: &mut Measure<'a, 'i>, xml: &'a roxmltree::Document<'i>, left: Cost, depth: usize) -> Result<Cost, Past> {
// First: its tests are bounded by what it finds, usvg's are not.
let cascade = m.cascade(xml, left)?;
let left = left.less(cascade);
m.most_tests = left.tests;
let (elements, bytes) = (left.elements, left.bytes);
let mut costs: HashMap<roxmltree::NodeId, Cost> = HashMap::new();
// The elements entered and not yet left: one entered again is a loop.
let mut open: HashSet<roxmltree::NodeId> = HashSet::new();
enum Step<'a, 'i> {
Enter(XNode<'a, 'i>),
/// An element, what its cost adds up (its children, or what a `<use>` shows), and the one
/// element a `<use>` shows alone.
Leave(XNode<'a, 'i>, Vec<XNode<'a, 'i>>, Option<XNode<'a, 'i>>),
}
let root = xml.root_element();
let mut stack = vec![Step::Enter(root)];
while let Some(step) = stack.pop() {
match step {
Step::Enter(n) => {
if costs.contains_key(&n.id()) || svg_name(n).is_none_or(|name| name == "style") {
continue;
}
if !open.insert(n.id()) {
// usvg copies a loop until it nests past what it reads.
return Err(Past::Depth);
}
// The elements entered and not yet left are the ones it is nested in.
if open.len() > depth {
return Err(Past::Depth);
}
let (parts, bare) = match svg_name(n) {
Some("text") => (vec![], None),
Some("use") => match m.shows(n) {
Shows::All(link) => (vec![link], None),
Shows::Bare(link) => (vec![], Some(link)),
Shows::Nothing => (vec![], None),
},
_ => (n.children().filter(|c| svg_name(*c).is_some_and(|name| name != "style")).collect(), None),
};
stack.push(Step::Leave(n, parts.clone(), bare));
stack.extend(parts.into_iter().map(Step::Enter));
}
Step::Leave(n, parts, bare) => {
open.remove(&n.id());
let mut cost = match svg_name(n) {
Some("text") => m.text(n),
_ => m.own(n),
};
if let Some(link) = bare {
cost = cost.add(m.own(link));
}
for part in parts {
cost = cost.add(costs.get(&part.id()).copied().unwrap_or_default());
}
if cost.elements > elements {
return Err(Past::Elements);
}
if cost.bytes > bytes {
return Err(Past::Bytes);
}
if m.tests_past() || cost.tests > left.tests {
return Err(Past::Tests);
}
costs.insert(n.id(), cost);
}
}
}
let usvg = costs.get(&root.id()).copied().unwrap_or_default();
Ok(usvg.add(cascade))
}
#[cfg(test)]
mod tests {
use super::*;
fn svg(body: &str) -> String {
format!(r#"<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="10" height="10">{body}</svg>"#)
}
const NO_LIMITS: Cost = Cost { elements: u64::MAX, bytes: u64::MAX, tests: u64::MAX };
/// What [`measure`] makes of `text` with no limits, as (elements, bytes).
fn cost(text: &str) -> (u64, u64) {
let xml = roxmltree::Document::parse(text).unwrap();
let c = measure(&xml, NO_LIMITS, usize::MAX).unwrap_or_else(|p| panic!("{p:?}"));
(c.elements, c.bytes)
}
fn past(text: &str, elements: u64, bytes: u64) -> Option<Past> {
measure(&roxmltree::Document::parse(text).unwrap(), Cost { elements, bytes, tests: u64::MAX }, usize::MAX).err()
}
/// Groups `g0` to `g{levels}`: `g0` a rectangle styled `style`, each other two `<use>`s of the
/// one before; one `<use>` of the last shown.
fn chain(levels: usize, style: &str) -> String {
let links: String = (1..=levels).map(|i| format!("<g id='g{i}'><use href='#g{0}'/><use xlink:href='#g{0}'/></g>", i - 1)).collect();
svg(&format!("<defs><g id='g0'><rect width='1' height='1' style='{style}'/></g>{links}</defs><use href='#g{levels}'/>"))
}
#[test]
fn copies_are_counted_with_their_styles_up_to_each_limit() {
// svg, defs, g0 and its rect (2), g1 with two uses of g0 (1 + 2 × 3), the shown use (1 + 7).
// Five rects, each copying `red` (3 bytes and a copy's 16).
let one = chain(1, "fill:red");
assert_eq!(cost(&one), (19, 5 * 19));
assert_eq!(past(&one, 19, 95), None);
assert_eq!(past(&one, 18, 95), Some(Past::Elements));
assert_eq!(past(&one, 19, 94), Some(Past::Bytes));
// Each level doubles what the shown use holds, without making any of it.
let (elements, _) = cost(&chain(60, ""));
assert!(elements > 1 << 60, "{elements}");
assert_eq!(past(&chain(60, ""), MAX_SVG_ELEMENTS as u64, u64::MAX), Some(Past::Elements));
assert_eq!(past(&chain(40, "font-family:a"), u64::MAX, MAX_COPIED_STYLES), Some(Past::Bytes));
}
#[test]
fn the_element_limit_stays_below_where_usvg_stops() {
assert_eq!(MAX_SVG_ELEMENTS, if cfg!(target_arch = "wasm32") { 500_000 } else { 999_999 });
}
#[test]
fn style_sheet_rules_count_where_they_match() {
let groups = "<g class='a'/>".repeat(4);
// `g` matches the four groups (16 + 3 each), `.b` none, `svg` the root (16 + 4); the
// import's own cascade keeps the same, names included (16 + 4 + 3 and 16 + 4 + 4).
let (_, bytes) = cost(&svg(&format!("<style>g{{fill:red}} .b{{fill:blue}} svg{{fill:none}}</style>{groups}")));
assert_eq!(bytes, 4 * 19 + 20 + 4 * 23 + 24);
// usvg drops a `:not()` rule; the cascade keeps it for each group it matches.
assert_eq!(cost(&svg(&format!("<style>g:not(.x){{fill:red}}</style>{groups}"))).1, 4 * 23);
// A style sheet of another type is not read; the style element itself makes nothing.
assert_eq!(cost(&svg(&format!("<style type='text/x'>g{{fill:red}}</style>{groups}"))), (5, 0));
// `marker` sets three properties; `font` resets twelve and sets six from its text.
let (_, marker) = cost(&svg("<path style='marker:url(#m)'/>"));
let (_, font) = cost(&svg("<path style='font:12px a'/>"));
assert_eq!((marker, font), (3 * (16 + 7), 18 * 16 + 12 * 6 + 6));
}
#[test]
fn references_usvg_leaves_out_copy_nothing() {
// A use of itself, of a group holding it, of what isn't there or isn't SVG.
let (n, _) = cost(&svg("<use id='u' href='#u'/><g id='a'><g><use href='#a'/></g></g><use href='#none'/><x id='x'/><use href='#x'/>"));
assert_eq!(n, 1 + 1 + 3 + 1 + 1);
// Two uses of each other: each shows the other alone.
assert_eq!(cost(&svg("<use id='u1' href='#u2'/><use id='u2' href='#u1'/>")).0, 1 + 2 + 2);
// A group holding a use of the use that shows it: that use shows nothing, and the one the
// group holds shows it alone.
let back = svg("<g id='g'><use id='inner' href='#outer'/></g><use id='outer' href='#g'/>");
assert_eq!(cost(&back).0, 1 + 3 + 1);
// The unprefixed href wins, and an id names its first element.
let first = svg("<g id='a'><rect/><rect/></g><g id='a'/><rect id='b'/><use xlink:href='#a' href='#b'/><use href='#a'/>");
assert_eq!(cost(&first).0, 1 + 3 + 1 + 1 + 2 + 4);
}
#[test]
fn a_loop_usvg_copies_without_end_is_refused_as_usvg_refuses_it() {
let looped = svg("<g id='a'><use href='#b'/></g><g id='b'><use href='#a'/></g>");
assert_eq!(past(&looped, u64::MAX, u64::MAX), Some(Past::Depth));
assert!(usvg::Tree::from_str(&looped, &usvg::Options::default()).is_err());
// Without the loop, usvg reads it.
let open = svg("<g id='a'><use href='#b'/></g><g id='b'><rect width='1' height='1'/></g>");
assert!(past(&open, u64::MAX, u64::MAX).is_none() && usvg::Tree::from_str(&open, &usvg::Options::default()).is_ok());
}
/// A chain of `<use>`s nested past the depth is too deep, as `depth::height` finds it, before
/// what the chain makes is added up; one within the depth `depth::height` gives is not.
#[test]
fn copies_nested_past_the_depth_are_too_deep() {
let links: String = (0..3000).map(|i| format!("<g id='u{i}'><use href='#u{}'/></g>", i + 1)).collect();
let deep = svg(&format!("<defs>{links}<rect id='u3000' width='1' height='1'/></defs><use href='#u0'/>"));
let xml = roxmltree::Document::parse(&deep).unwrap();
assert_eq!(measure(&xml, NO_LIMITS, MAX_ELEMENT_DEPTH).err(), Some(Past::Depth));
assert!(super::super::depth::height(&xml, MAX_ELEMENT_DEPTH).is_none());
assert!(matches!(check(&xml, Cost::LIMITS, MAX_ELEMENT_DEPTH), Err(SvgError::TooDeep(_))));
for text in [chain(5, ""), svg("<g><g><use href='#r'/></g></g><rect id='r'/>")] {
let xml = roxmltree::Document::parse(&text).unwrap();
let height = super::super::depth::height(&xml, usize::MAX).unwrap_or(0);
assert!(measure(&xml, NO_LIMITS, height).is_ok(), "{height} {text}");
}
}
#[test]
fn text_counts_its_runs_and_what_trefs_show() {
let (n, bytes) = cost(&svg("<g id='t'>abcd</g><text>xy<tspan>z</tspan><tref href='#t'/></text>"));
// svg, g (its text is not counted outside a text), text, its runs "xy" and "z", tspan, tref and its text.
assert_eq!(n, 1 + 1 + 1 + 2 + 1 + 1 + 1);
assert_eq!(bytes, (16 + 2) + (16 + 1) + (16 + 4));
}
/// A long style sheet rule that matches many elements is refused before the import's own style
/// cascade (which keeps the declarations of each element) reads them, in an SVG and in an SVG
/// image it shows.
#[test]
fn a_long_rule_on_many_elements_is_refused_before_the_cascade_reads_it() {
let groups = svg(&format!("<style>g{{font-family:{}}}</style>{}", "a".repeat(100_000), "<g/>".repeat(1000)));
let image = svg(&format!(r#"<image href="data:image/svg+xml;base64,{}" width="10" height="10"/>"#, crate::base64_encode(groups.as_bytes())));
// usvg drops a `:not()` rule, which the import's own cascade reads.
let not = svg(&format!("<style>g:not(.x){{font-family:{}}}</style>{}", "a".repeat(100_000), "<g/>".repeat(1000)));
for text in [groups, image, not] {
let before = super::super::css::selector_tests();
let err = super::super::import(&text, &crate::ImportOptions::default(), MAX_NODES).err();
assert!(matches!(err, Some(SvgError::StylesTooLarge(64))), "{err:?}");
assert_eq!(super::super::css::selector_tests(), before);
}
}
/// A linked SVG file with such a rule, and an `<image>` of its own whose link the import reads,
/// is refused before the cascade reads it too.
#[test]
fn a_linked_svg_with_a_long_rule_is_refused_before_the_cascade_reads_it() {
let linked =
svg(&format!("<style>g{{font-family:{}}}</style>{}<image href='b.png' width='1' height='1'/>", "a".repeat(100_000), "<g/>".repeat(1000)));
let read = |path: &str| path.ends_with("a.svg").then(|| (linked.clone().into_bytes(), vectorcraft_doc::LinkInfo::new(path)));
let folder = std::env::temp_dir().join("vectorcraft-svg-budget");
let folder = folder.to_string_lossy();
let opts = crate::ImportOptions { folder: Some(&folder), read: Some(&read) };
let before = super::super::css::selector_tests();
let err = super::super::import(&svg("<image href='a.svg' width='10' height='10'/>"), &opts, MAX_NODES).err();
assert!(matches!(err, Some(SvgError::StylesTooLarge(64))), "{err:?}");
assert_eq!(super::super::css::selector_tests(), before);
}
/// `depth` groups in one another, each of class `a`, around a rectangle, with `sheet`.
fn nested(depth: usize, sheet: &str) -> String {
svg(&format!("<style>{sheet}</style>{}<rect width='1' height='1'/>{}", "<g class='a'>".repeat(depth), "</g>".repeat(depth)))
}
/// A selector whose leftmost part matches nothing makes usvg test every set of ancestors in
/// turn: the tests stop at the limit and the SVG is refused, before usvg or the cascade runs.
#[test]
fn a_selector_that_never_matches_stops_at_the_test_limit() {
let never = nested(60, &format!(".missing{} {{fill:red}}", " g".repeat(20)));
let xml = roxmltree::Document::parse(&never).unwrap();
assert_eq!(measure(&xml, Cost::LIMITS, usize::MAX).err(), Some(Past::Tests));
let before = super::super::css::selector_tests();
let err = super::super::import(&never, &crate::ImportOptions::default(), MAX_NODES).err();
assert!(matches!(err, Some(SvgError::StylesTooComplex)), "{err:?}");
assert_eq!(super::super::css::selector_tests(), before);
// The same selector without its leftmost part matches at once, and imports.
let matching = nested(60, &format!("g{} {{fill:red}}", " g".repeat(19)));
assert!(super::super::import(&matching, &crate::ImportOptions::default(), MAX_NODES).is_ok());
}
/// usvg tests the rules against each copy a `<use>` shows: the tests add up as the copies do,
/// and the cascade's tests count once for each element.
#[test]
fn selector_tests_count_for_each_copy() {
let tests = |levels: usize| {
let text = chain(levels, "").replacen("<defs>", "<style>.b rect{fill:red}</style><defs>", 1);
let xml = roxmltree::Document::parse(&text).unwrap();
measure(&xml, NO_LIMITS, usize::MAX).unwrap_or_else(|p| panic!("{p:?}")).tests
};
let (ten, eleven) = (tests(10), tests(11));
assert!(eleven > 2 * ten - 100, "{ten} {eleven}");
let text = chain(11, "").replacen("<defs>", "<style>.b rect{fill:red}</style><defs>", 1);
let xml = roxmltree::Document::parse(&text).unwrap();
assert_eq!(measure(&xml, Cost { tests: eleven - 1, ..NO_LIMITS }, usize::MAX).err(), Some(Past::Tests));
assert!(measure(&xml, Cost { tests: eleven, ..NO_LIMITS }, usize::MAX).is_ok());
}
/// Each alternative of a `:not()` counts as a test of the cascade, for each element.
#[test]
fn not_alternatives_count_as_tests() {
let alternatives: Vec<String> = (0..1000).map(|i| format!(".m{i}")).collect();
let text = svg(&format!("<style>g:not({}){{fill:red}}</style>{}", alternatives.join(","), "<g/>".repeat(1000)));
let xml = roxmltree::Document::parse(&text).unwrap();
let tests = measure(&xml, NO_LIMITS, usize::MAX).unwrap_or_else(|p| panic!("{p:?}")).tests;
assert!(tests > 1000 * 1000, "{tests}");
assert_eq!(measure(&xml, Cost { tests: 1000 * 1000, ..NO_LIMITS }, usize::MAX).err(), Some(Past::Tests));
}
/// Matching as usvg matches stops once its tests pass what the limits have left, as when an
/// SVG image gets what the SVG showing it left.
#[test]
fn usvg_matching_stops_at_what_is_left() {
let never = nested(60, &format!(".missing{} {{fill:red}}", " g".repeat(20)));
let xml = roxmltree::Document::parse(&never).unwrap();
let cascade = Measure::new(&xml).cascade(&xml, NO_LIMITS).unwrap_or_else(|p| panic!("{p:?}")).tests;
assert_eq!(measure(&xml, Cost { tests: cascade + 1000, ..NO_LIMITS }, usize::MAX).err(), Some(Past::Tests));
let made = USVG_TESTS.get();
assert!((1000..1100).contains(&made), "{made}");
}
/// Each class of a compound is looked for in the element's class list, so the tests grow with
/// the list's length: in the import's own cascade (a `:not()` rule, which usvg drops) and as
/// usvg matches.
#[test]
fn class_tests_grow_with_the_class_list() {
let list = (0..1000).map(|i| format!("c{i}")).collect::<Vec<_>>().join(" ");
let classes: String = (0..100).map(|i| format!(".c{i}")).collect();
let scans = 100 * css::scan_tests(list.len());
let tests = |rule: &str| {
let text = svg(&format!("<style>{rule}{{fill:red}}</style><g class='{list}'/>"));
let xml = roxmltree::Document::parse(&text).unwrap();
measure(&xml, NO_LIMITS, usize::MAX).unwrap_or_else(|p| panic!("{p:?}")).tests
};
let cascade = tests(&format!("g:not(.x{classes})"));
assert!(cascade >= scans, "{cascade} {scans}");
tests(&format!("g{classes}"));
let usvg = USVG_TESTS.get();
assert!(usvg >= scans, "{usvg} {scans}");
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.