GitCorner

Code

ossartcraftdeckcraft🌐
e4f86d11fe8a
//! DrawingML custom geometry (`a:custGeom`): guide formula evaluation and conversion of
//! `a:pathLst` to our `M L C Q Z` path syntax, and back.
//!
//! Formulas follow the ECMA-376 shape guide semantics (§20.1.9.11): angles are in 1/60 000 degree,
//! and every operand is a guide name, a built-in variable or an integer literal.

use std::collections::HashMap;
use std::f64::consts::PI;
use std::fmt::Write as _;

use deckcraft_geom::preset::FillMode;
use deckcraft_model::CustomPath;

use crate::xml::{A, El, W};

const DEG: f64 = 60_000.0;

/// Distinct path coordinate spaces whose guides are evaluated for one custom geometry; paths in
/// further spaces are left out.
const MAX_SPACES: usize = 16;

/// Guide-name bytes all cached spaces may hold between them; the first space counts towards it but is always kept.
/// Every space copies the names, which the XML limits bound only once.
const MAX_SPACE_NAME_BYTES: usize = 4 << 20;

/// Guide variables for one shape.
pub struct Guides {
    vars: HashMap<String, f64>,
}

fn to_rad(a: f64) -> f64 {
    a / DEG * PI / 180.0
}

fn to_ang(r: f64) -> f64 {
    r * 180.0 / PI * DEG
}

fn finite(v: f64) -> f64 {
    if v.is_finite() { v.clamp(-1.0e15, 1.0e15) } else { 0.0 }
}

impl Guides {
    /// Built-in variables for a shape `w` × `h` (in the shape's coordinate units).
    pub fn new(w: f64, h: f64) -> Self {
        let (w, h) = (finite(w), finite(h));
        let ss = w.min(h);
        let ls = w.max(h);
        let mut v = HashMap::new();
        let mut set = |k: &str, x: f64| {
            v.insert(k.to_string(), x);
        };
        set("w", w);
        set("h", h);
        set("l", 0.0);
        set("t", 0.0);
        set("r", w);
        set("b", h);
        set("hc", w / 2.0);
        set("vc", h / 2.0);
        set("ss", ss);
        set("ls", ls);
        for d in [2.0, 3.0, 4.0, 5.0, 6.0, 8.0, 10.0, 12.0, 16.0, 32.0] {
            set(&format!("wd{d}"), w / d);
            set(&format!("hd{d}"), h / d);
            set(&format!("ssd{d}"), ss / d);
        }
        set("cd2", 10_800_000.0);
        set("cd4", 5_400_000.0);
        set("cd8", 2_700_000.0);
        set("3cd4", 16_200_000.0);
        set("3cd8", 8_100_000.0);
        set("5cd8", 13_500_000.0);
        set("7cd8", 18_900_000.0);
        Guides { vars: v }
    }
    /// Bytes of the guide names held.
    fn name_bytes(&self) -> usize {
        self.vars.keys().map(String::len).sum()
    }
    pub fn get(&self, name: &str) -> f64 {
        let name = name.trim();
        if let Some(v) = self.vars.get(name) {
            return *v;
        }
        name.parse::<f64>().ok().map(finite).unwrap_or(0.0)
    }
    pub fn set(&mut self, name: &str, v: f64) {
        if self.vars.len() < 10_000 {
            self.vars.insert(name.to_string(), finite(v));
        }
    }
    /// Evaluate one formula (`*/ w 1 2`).
    pub fn eval(&self, fmla: &str) -> f64 {
        let mut it = fmla.split_whitespace();
        let op = it.next().unwrap_or("");
        let args: Vec<f64> = it.take(3).map(|a| self.get(a)).collect();
        let a = |i: usize| args.get(i).copied().unwrap_or(0.0);
        let div = |n: f64, d: f64| if d == 0.0 { 0.0 } else { n / d };
        let r = match op {
            "*/" => div(a(0) * a(1), a(2)),
            "+-" => a(0) + a(1) - a(2),
            "+/" => div(a(0) + a(1), a(2)),
            "?:" => {
                if a(0) > 0.0 {
                    a(1)
                } else {
                    a(2)
                }
            }
            "abs" => a(0).abs(),
            "at2" => to_ang(a(1).atan2(a(0))),
            "cat2" => a(0) * a(2).atan2(a(1)).cos(),
            "sat2" => a(0) * a(2).atan2(a(1)).sin(),
            "cos" => a(0) * to_rad(a(1)).cos(),
            "sin" => a(0) * to_rad(a(1)).sin(),
            "tan" => a(0) * to_rad(a(1)).tan(),
            "max" => a(0).max(a(1)),
            "min" => a(0).min(a(1)),
            "mod" => (a(0) * a(0) + a(1) * a(1) + a(2) * a(2)).sqrt(),
            "pin" => {
                if a(1) < a(0) {
                    a(0)
                } else if a(1) > a(2) {
                    a(2)
                } else {
                    a(1)
                }
            }
            "sqrt" => a(0).max(0.0).sqrt(),
            "val" => a(0),
            _ => 0.0,
        };
        finite(r)
    }
    /// Evaluate a list of `a:gd` elements in order.
    pub fn eval_list(&mut self, list: Option<&El>) {
        let Some(list) = list else { return };
        for gd in list.children_named("gd").take(5000) {
            let (Some(name), Some(f)) = (gd.attr("name"), gd.attr("fmla")) else { continue };
            let v = self.eval(f);
            self.set(name, v);
        }
    }
}

fn num(s: &mut String, v: f64) {
    let v = finite(v);
    let r = (v * 1000.0).round() / 1000.0;
    if r == r.trunc() {
        let _ = write!(s, "{}", r as i64);
    } else {
        let _ = write!(s, "{r}");
    }
}

fn pt(g: &Guides, e: &El) -> (f64, f64) {
    (g.get(e.attr("x").unwrap_or("0")), g.get(e.attr("y").unwrap_or("0")))
}

/// Convert `a:custGeom` to custom paths. `w`/`h` is the shape size in EMU (used for guides and for
/// paths that don't give their own coordinate space).
pub fn read_cust_geom(cg: &El, w_emu: f64, h_emu: f64) -> Vec<CustomPath> {
    read_cust_geom_counting(cg, w_emu, h_emu).0
}

/// [`read_cust_geom`], and how many paths were left out for lack of room in the guide caches
/// (`(too many coordinate spaces, too many guide-name bytes)`); each cause is also logged once.
fn read_cust_geom_counting(cg: &El, w_emu: f64, h_emu: f64) -> (Vec<CustomPath>, (usize, usize)) {
    let mut out = vec![];
    let mut dropped = (0usize, 0usize);
    let Some(pl) = cg.child("pathLst") else { return (out, dropped) };
    let mut spaces: HashMap<(u64, u64), Guides> = HashMap::new();
    let mut name_bytes = 0usize;
    let mut budget_full = false;
    // The cap on cached spaces saves guide evaluation: a geometry without guides has none to save.
    let guided = ["avLst", "gdLst"].iter().any(|n| cg.child(n).is_some_and(|l| l.elements().next().is_some()));
    for p in pl.children_named("path").take(1000) {
        let pw = p.f64("w").unwrap_or(0.0);
        let ph = p.f64("h").unwrap_or(0.0);
        // Guides are evaluated in the path's own space when it has one.
        let (gw, gh) = if pw > 0.0 || ph > 0.0 { (pw, ph) } else { (w_emu, h_emu) };
        // The guide lists are evaluated once per coordinate space, not once per path.
        let key = (gw.to_bits(), gh.to_bits());
        if !spaces.contains_key(&key) {
            if guided && (budget_full || spaces.len() >= MAX_SPACES) {
                if budget_full {
                    dropped.1 += 1;
                } else {
                    dropped.0 += 1;
                }
                continue;
            }
            let mut g = Guides::new(gw, gh);
            g.eval_list(cg.child("avLst"));
            g.eval_list(cg.child("gdLst"));
            // The first space is always kept; later ones only while the cache stays within budget.
            let bytes = g.name_bytes();
            if guided && !spaces.is_empty() && name_bytes.saturating_add(bytes) > MAX_SPACE_NAME_BYTES {
                // Every space holds the same names, so no later space fits either.
                budget_full = true;
                dropped.1 += 1;
                continue;
            }
            name_bytes = name_bytes.saturating_add(bytes);
            spaces.insert(key, g);
        }
        let Some(g) = spaces.get(&key) else { continue };
        let mut d = String::new();
        let mut cur = (0.0, 0.0);
        let mut start = (0.0, 0.0);
        for c in p.elements().take(100_000) {
            match c.local() {
                "moveTo" => {
                    if let Some(q) = c.child("pt") {
                        cur = pt(g, q);
                        start = cur;
                        d.push_str("M ");
                        num(&mut d, cur.0);
                        d.push(' ');
                        num(&mut d, cur.1);
                        d.push(' ');
                    }
                }
                "lnTo" => {
                    if let Some(q) = c.child("pt") {
                        cur = pt(g, q);
                        d.push_str("L ");
                        num(&mut d, cur.0);
                        d.push(' ');
                        num(&mut d, cur.1);
                        d.push(' ');
                    }
                }
                "cubicBezTo" => {
                    let pts: Vec<(f64, f64)> = c.children_named("pt").map(|q| pt(g, q)).collect();
                    if let [a, b, e] = pts.as_slice() {
                        d.push_str("C ");
                        for (x, y) in [a, b, e] {
                            num(&mut d, *x);
                            d.push(' ');
                            num(&mut d, *y);
                            d.push(' ');
                        }
                        cur = *e;
                    }
                }
                "quadBezTo" => {
                    let pts: Vec<(f64, f64)> = c.children_named("pt").map(|q| pt(g, q)).collect();
                    if let [a, e] = pts.as_slice() {
                        d.push_str("Q ");
                        for (x, y) in [a, e] {
                            num(&mut d, *x);
                            d.push(' ');
                            num(&mut d, *y);
                            d.push(' ');
                        }
                        cur = *e;
                    }
                }
                "arcTo" => {
                    let wr = g.get(c.attr("wR").unwrap_or("0"));
                    let hr = g.get(c.attr("hR").unwrap_or("0"));
                    let st = g.get(c.attr("stAng").unwrap_or("0"));
                    let sw = g.get(c.attr("swAng").unwrap_or("0"));
                    cur = arc_to(&mut d, cur, wr, hr, st, sw);
                }
                "close" => {
                    d.push_str("Z ");
                    cur = start;
                }
                _ => {}
            }
        }
        let fill = match p.attr("fill").unwrap_or("norm") {
            "none" => FillMode::None,
            "lighten" => FillMode::Lighten,
            "lightenLess" => FillMode::LightenLess,
            "darken" => FillMode::Darken,
            "darkenLess" => FillMode::DarkenLess,
            _ => FillMode::Norm,
        };
        let (ow, oh) = if pw > 0.0 || ph > 0.0 { (pw, ph) } else { (w_emu.max(1.0), h_emu.max(1.0)) };
        out.push(CustomPath { w: ow, h: oh, d: d.trim_end().to_string(), fill, stroke: p.bool("stroke").unwrap_or(true) });
    }
    if dropped.0 > 0 {
        log::warn!("pptx: a custom geometry uses more than {MAX_SPACES} distinct path coordinate spaces; {} later path(s) are not kept", dropped.0);
    }
    if dropped.1 > 0 {
        log::warn!(
            "pptx: a custom geometry's guide names pass {MAX_SPACE_NAME_BYTES} bytes across its coordinate spaces; {} later path(s) are not kept",
            dropped.1
        );
    }
    (out, dropped)
}

/// Ellipse parametric angle for a visual angle `a` (radians).
fn param(a: f64, wr: f64, hr: f64) -> f64 {
    (wr * a.sin()).atan2(hr * a.cos())
}

/// Append an elliptical arc as cubic Béziers; returns the end point.
fn arc_to(d: &mut String, cur: (f64, f64), wr: f64, hr: f64, st: f64, sw: f64) -> (f64, f64) {
    if wr.abs() < 1e-9 || hr.abs() < 1e-9 || sw == 0.0 {
        return cur;
    }
    let st_r = to_rad(st);
    let sw_r = to_rad(sw).clamp(-4.0 * PI, 4.0 * PI);
    let t0 = param(st_r, wr, hr);
    let mut t1 = param(st_r + sw_r, wr, hr);
    // Keep the sweep direction and size of the visual angle.
    let full = sw_r.abs() >= 2.0 * PI - 1e-9;
    if full {
        t1 = t0 + sw_r.signum() * 2.0 * PI;
    } else {
        while sw_r > 0.0 && t1 < t0 {
            t1 += 2.0 * PI;
        }
        while sw_r < 0.0 && t1 > t0 {
            t1 -= 2.0 * PI;
        }
    }
    let cx = cur.0 - wr * t0.cos();
    let cy = cur.1 - hr * t0.sin();
    let total = t1 - t0;
    let n = ((total.abs() / (PI / 2.0)).ceil() as usize).clamp(1, 16);
    let step = total / n as f64;
    let k = 4.0 / 3.0 * (step / 4.0).tan();
    let mut a = t0;
    let mut end = cur;
    for _ in 0..n {
        let b = a + step;
        let (ca, sa, cb, sb) = (a.cos(), a.sin(), b.cos(), b.sin());
        let p1 = (cx + wr * (ca - k * sa), cy + hr * (sa + k * ca));
        let p2 = (cx + wr * (cb + k * sb), cy + hr * (sb - k * cb));
        end = (cx + wr * cb, cy + hr * sb);
        d.push_str("C ");
        for (x, y) in [p1, p2, end] {
            num(d, x);
            d.push(' ');
            num(d, y);
            d.push(' ');
        }
        a = b;
    }
    end
}

/// Parse our path syntax into commands.
pub use craft_drawingml::custgeom::parse_path;

/// Write custom paths as `a:custGeom`. Coordinates are integers in the file, so small path spaces
/// are scaled up.
pub fn write_cust_geom(w: &mut W, paths: &[CustomPath]) {
    w.open0("a:custGeom");
    w.empty0("a:avLst");
    w.empty0("a:gdLst");
    w.empty0("a:ahLst");
    w.empty0("a:cxnLst");
    w.empty("a:rect", A::new().a("l", "l").a("t", "t").a("r", "r").a("b", "b"));
    w.open0("a:pathLst");
    for p in paths {
        let (pw, ph) = (finite(p.w).abs(), finite(p.h).abs());
        let m = pw.max(ph);
        let k = if m > 0.0 && m < 20_000.0 { 100_000.0 / m } else { 1.0 };
        let r = |v: f64| (finite(v) * k).round().clamp(-2.0e9, 2.0e9) as i64;
        let fill = match p.fill {
            FillMode::Norm => None,
            FillMode::None => Some("none"),
            FillMode::Lighten => Some("lighten"),
            FillMode::LightenLess => Some("lightenLess"),
            FillMode::Darken => Some("darken"),
            FillMode::DarkenLess => Some("darkenLess"),
        };
        let a = A::new().a("w", r(pw).max(0)).a("h", r(ph).max(0)).o("fill", fill).o("stroke", (!p.stroke).then_some("0"));
        w.open("a:path", a);
        for (c, v) in parse_path(&p.d) {
            let pts: Vec<(i64, i64)> = v
                .chunks(2)
                .filter_map(|c| match c {
                    [x, y] => Some((r(*x), r(*y))),
                    _ => None,
                })
                .collect();
            let tag = match c {
                'M' => "a:moveTo",
                'L' => "a:lnTo",
                'C' => "a:cubicBezTo",
                'Q' => "a:quadBezTo",
                'Z' => {
                    w.empty0("a:close");
                    continue;
                }
                _ => continue,
            };
            w.open0(tag);
            for (x, y) in pts {
                w.empty("a:pt", A::new().a("x", x).a("y", y));
            }
            w.close(tag);
        }
        w.close("a:path");
    }
    w.close("a:pathLst");
    w.close("a:custGeom");
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::xml::parse;

    #[test]
    fn formulas() {
        let mut g = Guides::new(1000.0, 500.0);
        assert_eq!(g.eval("*/ w 1 2"), 500.0);
        assert_eq!(g.eval("+- w h 100"), 1400.0);
        assert_eq!(g.eval("+/ w h 3"), 500.0);
        assert_eq!(g.eval("?: -1 5 7"), 7.0);
        assert_eq!(g.eval("?: 1 5 7"), 5.0);
        assert_eq!(g.eval("abs -42"), 42.0);
        assert_eq!(g.eval("max 3 9"), 9.0);
        assert_eq!(g.eval("min 3 9"), 3.0);
        assert_eq!(g.eval("mod 3 4 0"), 5.0);
        assert_eq!(g.eval("pin 0 150 100"), 100.0);
        assert_eq!(g.eval("pin 0 -5 100"), 0.0);
        assert_eq!(g.eval("sqrt 16"), 4.0);
        assert_eq!(g.eval("val ss"), 500.0);
        assert!((g.eval("at2 1 1") - 2_700_000.0).abs() < 1e-6);
        assert!((g.eval("cos 100 5400000")).abs() < 1e-9);
        assert!((g.eval("sin 100 5400000") - 100.0).abs() < 1e-9);
        assert!((g.eval("tan 100 2700000") - 100.0).abs() < 1e-6);
        assert!((g.eval("cat2 10 1 0") - 10.0).abs() < 1e-9);
        assert!((g.eval("sat2 10 0 1") - 10.0).abs() < 1e-9);
        assert_eq!(g.eval("*/ 1 1 0"), 0.0, "division by zero is 0");
        assert_eq!(g.eval("bogus 1 2"), 0.0);
        assert_eq!(g.eval(""), 0.0);
        g.set("x1", 7.0);
        assert_eq!(g.eval("+- x1 0 2"), 5.0);
        assert_eq!(g.get("hc"), 500.0);
        assert_eq!(g.get("cd4"), 5_400_000.0);
    }

    #[test]
    fn custgeom_with_guides_and_arc() {
        let x = br#"<a:custGeom xmlns:a="x"><a:avLst/><a:gdLst><a:gd name="mid" fmla="*/ w 1 2"/></a:gdLst>
            <a:pathLst><a:path w="200" h="100"><a:moveTo><a:pt x="0" y="0"/></a:moveTo><a:lnTo><a:pt x="mid" y="h"/></a:lnTo>
            <a:arcTo wR="50" hR="50" stAng="0" swAng="5400000"/><a:close/></a:path>
            <a:path w="10" h="10" fill="none" stroke="0"><a:moveTo><a:pt x="1" y="1"/></a:moveTo><a:quadBezTo><a:pt x="2" y="2"/><a:pt x="3" y="1"/></a:quadBezTo></a:path></a:pathLst></a:custGeom>"#;
        let d = parse(x).unwrap();
        let paths = read_cust_geom(&d.root, 1000.0, 1000.0);
        assert_eq!(paths.len(), 2);
        assert!(paths[0].d.starts_with("M 0 0 L 100 100 C"), "{}", paths[0].d);
        assert!(paths[0].d.ends_with('Z'));
        // The quarter arc from (100,100) with centre (50,100) ends at (50,150).
        assert!(paths[0].d.contains("50 150"), "{}", paths[0].d);
        assert_eq!(paths[1].fill, FillMode::None);
        assert!(!paths[1].stroke);
        assert_eq!(paths[1].d, "M 1 1 Q 2 2 3 1");
    }

    #[test]
    fn paths_share_guides_and_distinct_spaces_are_capped() {
        let path = |w: usize| format!(r#"<a:path w="{w}" h="10"><a:moveTo><a:pt x="mid" y="1"/></a:moveTo></a:path>"#);
        let paths: String = (1..=40).map(|i| path(10 * i)).collect();
        let x = format!(
            r#"<a:custGeom xmlns:a="x"><a:gdLst><a:gd name="mid" fmla="*/ w 1 2"/></a:gdLst><a:pathLst>{paths}{}</a:pathLst></a:custGeom>"#,
            path(10)
        );
        let d = parse(x.as_bytes()).unwrap();
        let (out, dropped) = read_cust_geom_counting(&d.root, 1.0, 1.0);
        assert_eq!(out.len(), MAX_SPACES + 1, "16 spaces plus the repeat of the first");
        assert_eq!(dropped, (40 - MAX_SPACES, 0), "the paths of later spaces are counted, to be warned about");
        assert!(out[0].d.starts_with("M 5 1"), "{}", out[0].d);
        assert!(out[MAX_SPACES].d.starts_with("M 5 1"), "{}", out[MAX_SPACES].d);
    }

    #[test]
    fn guide_name_bytes_across_spaces_are_budgeted() {
        let name = "n".repeat(3 << 20);
        let path = |w: usize| format!(r#"<a:path w="{w}" h="10"><a:moveTo><a:pt x="{name}" y="1"/></a:moveTo></a:path>"#);
        let x = format!(
            r#"<a:custGeom xmlns:a="x"><a:gdLst><a:gd name="{name}" fmla="*/ w 1 2"/></a:gdLst><a:pathLst>{}{}{}</a:pathLst></a:custGeom>"#,
            path(10),
            path(20),
            path(10)
        );
        let d = parse(x.as_bytes()).unwrap();
        let (out, dropped) = read_cust_geom_counting(&d.root, 1.0, 1.0);
        assert_eq!(out.len(), 2, "the second 3 MiB space is over budget and left out; the first space's repeat stays");
        assert_eq!(dropped, (0, 1), "the path left out is counted, to be warned about");
    }

    #[test]
    fn guide_free_geometries_are_not_capped_by_space() {
        let paths: String = (1..=40).map(|i| format!(r#"<a:path w="{}" h="10"><a:moveTo><a:pt x="1" y="1"/></a:moveTo></a:path>"#, 10 * i)).collect();
        let x = format!(r#"<a:custGeom xmlns:a="x"><a:avLst/><a:gdLst/><a:pathLst>{paths}</a:pathLst></a:custGeom>"#);
        let d = parse(x.as_bytes()).unwrap();
        assert_eq!(read_cust_geom(&d.root, 1.0, 1.0).len(), 40);
    }

    #[test]
    fn write_then_read_path() {
        let p = CustomPath { w: 100.0, h: 50.0, d: "M 0 0 L 100 0 C 100 10 90 50 50 50 Q 0 50 0 0 Z".into(), fill: FillMode::Norm, stroke: true };
        let mut w = W::frag();
        write_cust_geom(&mut w, std::slice::from_ref(&p));
        let d = parse(w.s.as_bytes()).unwrap();
        let back = read_cust_geom(&d.root, 1.0, 1.0);
        assert_eq!(back.len(), 1);
        // Scaled by 1000 (100 → 100000).
        assert_eq!(back[0].w, 100_000.0);
        assert_eq!(back[0].d, "M 0 0 L 100000 0 C 100000 10000 90000 50000 50000 50000 Q 0 50000 0 0 Z");
    }

    #[test]
    fn parse_path_uppercase_exponent() {
        assert_eq!(parse_path("M 1E-5 2 L 3 4"), vec![('M', vec![1e-5, 2.0]), ('L', vec![3.0, 4.0])]);
        assert_eq!(parse_path("M 1.5E3 2"), vec![('M', vec![1500.0, 2.0])]);
        assert_eq!(parse_path("M 1e-5 2"), vec![('M', vec![1e-5, 2.0])]);
        // An 'E' right after a number with no exponent digits is the end command.
        assert_eq!(parse_path("M 0 0E"), vec![('M', vec![0.0, 0.0]), ('E', vec![])]);
    }

    #[test]
    fn parse_path_tokens() {
        let v = parse_path("M0,0 L10-5 Z");
        assert_eq!(v.len(), 3);
        assert_eq!(v[1], ('L', vec![10.0, -5.0]));
        assert!(parse_path("garbage ### C 1").is_empty() || parse_path("garbage").is_empty());
    }
}

#[cfg(test)]
mod shared_path_tests {
    use super::parse_path;

    #[test]
    fn shared_path_tokens_preserve_exponents_repeats_and_dropped_tails() {
        assert_eq!(
            parse_path("M1E2 -3E-1 4 5 L6-7 Q8 9 10 11 Z"),
            vec![('M', vec![100.0, -0.3]), ('L', vec![4.0, 5.0]), ('L', vec![6.0, -7.0]), ('Q', vec![8.0, 9.0, 10.0, 11.0]), ('Z', vec![]),]
        );
        assert_eq!(parse_path("M0 0 L1"), vec![('M', vec![0.0, 0.0])]);
        assert_eq!(parse_path("MNaN 0 1 2"), vec![('M', vec![0.0, 1.0])]);
    }
}