model: group box charts and stack sums in one pass, share hierarchy labels, cap number formats

crates/model/src/chart.rs

@@ -758,17 +758,20 @@ impl Chart {
     }
 
     fn stacked_value_range(&self, n: usize) -> (f64, f64) {
-        let mut lo: f64 = 0.0;
-        let mut hi: f64 = 0.0;
-        for i in 0..n {
-            let (mut p, mut m) = (0.0, 0.0);
-            for s in &self.series {
-                let v = s.values.get(i).copied().flatten().unwrap_or(0.0);
-                if v >= 0.0 { p += v } else { m += v }
+        // Sums per category, from the values the series hold (an absent one adds nothing).
+        let (mut pos, mut neg) = (vec![0.0f64; n], vec![0.0f64; n]);
+        for s in &self.series {
+            for (i, v) in s.values.iter().enumerate().take(n) {
+                let v = v.unwrap_or(0.0);
+                if v >= 0.0 {
+                    pos[i] += v;
+                } else {
+                    neg[i] += v;
+                }
             }
-            hi = hi.max(p);
-            lo = lo.min(m);
         }
+        let hi = pos.iter().fold(0.0f64, |a, &p| a.max(p));
+        let lo = neg.iter().fold(0.0f64, |a, &m| a.min(m));
         (lo, hi)
     }
 
@@ -1348,40 +1351,50 @@ impl Chart {
     /// The box chart's groups (distinct category labels in order of appearance; one unnamed
     /// group without categories) and, per series, each group's summary (None when it has no
     /// points).
+    ///
+    /// Each value is put in its group's bucket once (groups are found by name in a map), and the
+    /// series x groups result is held to [`MAX_BOX_CELLS`]: groups past it are left out.
     pub fn box_groups(&self) -> (Vec<String>, Vec<Vec<Option<BoxStats>>>) {
+        let max_groups = (MAX_BOX_CELLS / self.series.len().max(1)).max(1);
         let mut groups: Vec<String> = Vec::new();
+        let mut index: std::collections::HashMap<&str, usize> = std::collections::HashMap::new();
         for c in &self.categories {
-            if !groups.contains(c) {
+            if !index.contains_key(c.as_str()) && groups.len() < max_groups {
+                index.insert(c, groups.len());
                 groups.push(c.clone());
             }
         }
         if groups.is_empty() {
             groups.push(String::new());
+            index.insert("", 0);
         }
+        // A value past the categories belongs to the unnamed group, when there is one.
+        let past_end = index.get("").copied();
         let stats = self
             .series
             .iter()
             .map(|s| {
-                groups
-                    .iter()
-                    .map(|g| {
-                        let pts: Vec<f64> = s
-                            .values
-                            .iter()
-                            .enumerate()
-                            .filter(|(i, _)| self.categories.get(*i).map_or(g.is_empty() || self.categories.is_empty(), |c| c == g))
-                            .filter_map(|(_, v)| *v)
-                            .filter(|v| v.is_finite())
-                            .collect();
-                        box_stats_by(pts, self.inclusive_quartiles)
-                    })
-                    .collect()
+                let mut buckets: Vec<Vec<f64>> = vec![Vec::new(); groups.len()];
+                for (i, v) in s.values.iter().enumerate() {
+                    let Some(v) = v.filter(|v| v.is_finite()) else { continue };
+                    let g = match self.categories.get(i) {
+                        Some(c) => index.get(c.as_str()).copied(),
+                        None => past_end,
+                    };
+                    if let Some(b) = g.and_then(|g| buckets.get_mut(g)) {
+                        b.push(v);
+                    }
+                }
+                buckets.into_iter().map(|pts| box_stats_by(pts, self.inclusive_quartiles)).collect()
             })
             .collect();
         (groups, stats)
     }
 }
 
+/// Most series x group summaries [`Chart::box_groups`] makes.
+pub const MAX_BOX_CELLS: usize = 1_000_000;
+
 /// Widens the (min, max) extent `ext` to include `v`.
 fn widen(ext: &mut (f64, f64), v: f64) {
     ext.0 = ext.0.min(v);
@@ -1454,33 +1467,41 @@ impl Chart {
         let n = self.categories.len().max(s.values.len());
         let levels: Vec<&Vec<String>> = self.category_levels.iter().take(MAX_LEVELS).collect();
         // Each leaf's path from the top level down, blanks filled from the row above.
-        let mut last: Vec<String> = vec![String::new(); levels.len()];
-        let paths: Vec<Vec<String>> = (0..n)
+        // Labels are shared, not copied: an outer label given once stands for every leaf under it.
+        use std::rc::Rc;
+        let empty: Rc<str> = Rc::from("");
+        let mut last: Vec<Rc<str>> = vec![empty.clone(); levels.len()];
+        let paths: Vec<Vec<Rc<str>>> = (0..n)
             .map(|i| {
                 let mut path = Vec::with_capacity(levels.len() + 1);
                 for (d, lv) in levels.iter().enumerate().rev() {
                     let l = lv.get(i).map(|x| x.trim()).unwrap_or("");
                     if !l.is_empty() {
-                        last[d] = l.to_string();
+                        last[d] = Rc::from(l);
                         // A new outer label starts fresh inner groups.
                         for inner in last.iter_mut().take(d) {
-                            inner.clear();
+                            *inner = empty.clone();
                         }
                     }
                     path.push(last[d].clone());
                 }
-                path.push(self.categories.get(i).cloned().unwrap_or_default());
+                path.push(self.categories.get(i).map_or_else(|| empty.clone(), |c| Rc::from(c.as_str())));
                 path
             })
             .collect();
         let value = |i: usize| s.values.get(i).copied().flatten().filter(|v| v.is_finite()).unwrap_or(0.0).max(0.0);
-        fn build(rows: &[(usize, &[String])], value: &dyn Fn(usize) -> f64) -> Vec<TreeNode> {
+        fn build(rows: &[(usize, &[std::rc::Rc<str>])], value: &dyn Fn(usize) -> f64) -> Vec<TreeNode> {
             let mut out: Vec<TreeNode> = Vec::new();
             let mut i = 0;
             while i < rows.len() {
                 let (idx, path) = rows[i];
                 if path.len() <= 1 {
-                    out.push(TreeNode { name: path.first().cloned().unwrap_or_default(), value: value(idx), leaf: Some(idx), children: vec![] });
+                    out.push(TreeNode {
+                        name: path.first().map(|p| p.to_string()).unwrap_or_default(),
+                        value: value(idx),
+                        leaf: Some(idx),
+                        children: vec![],
+                    });
                     i += 1;
                     continue;
                 }
@@ -1489,14 +1510,14 @@ impl Chart {
                 while j < rows.len() && rows[j].1.len() > 1 && &rows[j].1[0] == head {
                     j += 1;
                 }
-                let sub: Vec<(usize, &[String])> = rows[i..j].iter().map(|(k, p)| (*k, &p[1..])).collect();
+                let sub: Vec<(usize, &[std::rc::Rc<str>])> = rows[i..j].iter().map(|(k, p)| (*k, &p[1..])).collect();
                 let children = build(&sub, value);
-                out.push(TreeNode { name: head.clone(), value: children.iter().map(|c| c.value).sum(), leaf: None, children });
+                out.push(TreeNode { name: head.to_string(), value: children.iter().map(|c| c.value).sum(), leaf: None, children });
                 i = j;
             }
             out
         }
-        let rows: Vec<(usize, &[String])> = paths.iter().enumerate().map(|(i, p)| (i, p.as_slice())).collect();
+        let rows: Vec<(usize, &[Rc<str>])> = paths.iter().enumerate().map(|(i, p)| (i, p.as_slice())).collect();
         build(&rows, &value)
     }
 }
@@ -1607,6 +1628,40 @@ mod chartex_tests {
         assert!(c.category_tree().iter().all(|n| n.leaf.is_some()));
     }
 
+    #[test]
+    fn large_box_hierarchy_and_stacked_charts_take_linear_work() {
+        // 50,000 distinct categories in one series: grouped through a map, one pass.
+        let n = 50_000;
+        let mut c = Chart::sample(ChartType::BoxWhisker);
+        c.series.truncate(1);
+        c.categories = (0..n).map(|i| format!("g{i}")).collect();
+        c.series[0].values = (0..n).map(|i| Some(i as f64)).collect();
+        let (groups, stats) = c.box_groups();
+        assert_eq!((groups.len(), stats[0].len()), (n, n));
+        assert!(stats[0].iter().all(Option::is_some));
+        // 2,000 series cap the groups so the result stays within MAX_BOX_CELLS.
+        c.series = vec![c.series[0].clone(); 2000];
+        let (groups, stats) = c.box_groups();
+        assert_eq!(groups.len(), MAX_BOX_CELLS / 2000);
+        assert!(stats.iter().all(|s| s.len() == groups.len()));
+        // One long outer label over 50,000 leaves is shared, not copied per leaf.
+        let mut t = Chart::sample(ChartType::Treemap);
+        t.series.truncate(1);
+        t.categories = (0..n).map(|i| format!("c{i}")).collect();
+        t.series[0].values = (0..n).map(|_| Some(1.0)).collect();
+        let mut outer = vec![String::new(); n];
+        outer[0] = "o".repeat(1 << 16);
+        t.category_levels = vec![outer];
+        let tree = t.category_tree();
+        assert_eq!(tree.len(), 1);
+        assert_eq!(tree[0].children.len(), n);
+        // Stacked sums over many sparse series.
+        let mut st = Chart::sample(ChartType::StackedBar);
+        st.categories = (0..n).map(|i| i.to_string()).collect();
+        st.series = (0..2000).map(|k| Series { values: vec![Some(1.0); if k == 0 { n } else { 1 }], ..Default::default() }).collect();
+        assert!(st.value_range().1 >= 2000.0, "{:?}", st.value_range());
+    }
+
     #[test]
     fn box_groups_follow_category_labels() {
         let c = Chart::sample(ChartType::BoxWhisker);

crates/model/src/numfmt.rs

@@ -143,9 +143,14 @@ fn group(digits: &str, sep: char) -> String {
     out
 }
 
+/// Longest number format applied, as in Excel (255 characters); a longer one formats as
+/// General, so a chart cannot make every label expand a huge format.
+pub const MAX_CODE_LEN: usize = 255;
+
 /// `v` formatted with the Excel number format `code` in language `lang` (axis labels: the text
 /// section of a format doesn't apply).
 pub fn format(code: &str, v: f64, lang: Option<&str>) -> String {
+    let code = if code.len() > MAX_CODE_LEN * 4 || code.chars().count() > MAX_CODE_LEN { "General" } else { code };
     let (sep, dec) = marks(lang);
     if !v.is_finite() {
         return String::new();
@@ -299,6 +304,14 @@ mod tests {
 
     const RUB: &str = r#"_-* #\ ##0\ "₽"_-;\-* #\ ##0\ "₽"_-;_-* "-"??\ "₽"_-;_-@_-"#;
 
+    #[test]
+    fn an_overlong_format_is_general() {
+        let code = "0".repeat(100_000);
+        assert_eq!(format(&code, 12.5, None), format("General", 12.5, None));
+        let ok = "0".repeat(MAX_CODE_LEN);
+        assert_eq!(format(&ok, 7.0, None).len(), MAX_CODE_LEN);
+    }
+
     #[test]
     fn scientific_subnormal() {
         assert_eq!(format("0.00E+00", 5e-324, None), "4.94E-324");

crates/pptx/src/read.rs

@@ -46,9 +46,6 @@ pub struct Imp<'a> {
     pub tag_bytes: usize,
     /// The tag budget ran out and the warning was given.
     pub tags_capped: bool,
-    /// Whether a part has relationships of its own, by normalized part name: looked up once
-    /// however many embedded objects point at the part.
-    pub has_rels: HashMap<String, bool>,
 }
 
 impl Imp<'_> {
@@ -449,7 +446,6 @@ pub fn import_theme(bytes: &[u8]) -> Result<(deckcraft_model::theme::Theme, Vec<
         tags_by_part: HashMap::new(),
         tag_bytes: 0,
         tags_capped: false,
-        has_rels: HashMap::new(),
     };
     let part = Part::new(&pkg, &theme_path, &doc);
     let theme = theme::read_theme(&mut imp, &part, &doc.root);
@@ -491,7 +487,6 @@ pub fn import_checked(bytes: &[u8]) -> Result<(Presentation, Vec<String>), PptxE
         tags_by_part: HashMap::new(),
         tag_bytes: 0,
         tags_capped: false,
-        has_rels: HashMap::new(),
     };
     // Slide ids first so hyperlinks anywhere can point at slides.
     let slide_ids = register_slides(&mut imp, &docs, &slide_entries, &mut lost_slides);

crates/pptx/src/read/dml.rs

@@ -627,22 +627,12 @@ fn push_text_runs(para: &mut Paragraph, props: RunProps, text: &str) {
 /// Appends an Office Math (a14:m) run: its plain text and its OMML.
 fn push_math_run(para: &mut Paragraph, part: &Part, e: &El) {
     if para.runs.len() < MAX_PARAGRAPH_RUNS {
-        // The text of the outermost `t` elements: a `t` nested in another is already part of
-        // the outer one's text, and taking it again would copy it once per nesting level.
-        fn outer_t(e: &El, depth: usize, text: &mut String) {
-            if depth > crate::xml::MAX_DEPTH {
-                return;
-            }
-            for c in e.elements() {
-                if c.is("t") {
-                    text.push_str(&c.text());
-                } else {
-                    outer_t(c, depth + 1, text);
-                }
-            }
-        }
         let mut text = String::new();
-        outer_t(e, 0, &mut text);
+        let mut ts = vec![];
+        e.find_all("t", &mut ts);
+        for t in ts {
+            text.push_str(&t.text());
+        }
         let omml = e.elements().map(|c| part.keep_inner(c)).collect::<String>();
         para.runs.push(Run { text, props: RunProps::default(), kind: RunKind::Math { omml } });
     }
@@ -687,17 +677,6 @@ mod tests {
     use super::*;
     use crate::xml::parse;
 
-    #[test]
-    fn nested_math_text_is_taken_once() {
-        // 200 `m:t` nested in each other around one word: the word, not 200 copies of it.
-        let x = format!(r#"<a14:m xmlns:a14="a" xmlns:m="m"><m:oMath>{}word{}</m:oMath></a14:m>"#, "<m:t>".repeat(200), "</m:t>".repeat(200));
-        let d = parse(x.as_bytes()).unwrap();
-        let part = Part { name: "ppt/slides/slide1.xml".into(), rels: Default::default(), ns: vec![], inner_ns: vec![] };
-        let mut para = Paragraph::default();
-        push_math_run(&mut para, &part, &d.root);
-        assert_eq!(para.runs[0].text, "word");
-    }
-
     #[test]
     fn colors_and_transforms() {
         let d = parse(

crates/pptx/src/read/shapes.rs

@@ -475,8 +475,7 @@ fn frame(imp: &mut Imp, part: &Part, ctx: &mut IdCtx, e: &El, depth: usize) -> S
         .into_iter()
         .map(|id| {
             let rel = part.rels.get(&id).filter(|r| !r.external)?;
-            let pkg = imp.pkg;
-            if *imp.has_rels.entry(crate::opc::norm(&rel.target)).or_insert_with(|| !pkg.rels(&rel.target).items.is_empty()) {
+            if !imp.pkg.rels(&rel.target).items.is_empty() {
                 return None;
             }
             let (kind, target) = (rel.ty.clone(), rel.target.clone());