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

crates/engine/src/cmd/file.rs

@@ -390,7 +390,6 @@ pub fn pdf_options(p: &Value, count: usize) -> Result<deckcraft_pdf::PdfOptions>
 pub fn parse_slide_range(text: &str, count: usize) -> Result<Vec<usize>> {
     let invalid = || bad("file.export", format!("“{text}” isn't a valid slide range: use numbers and ranges such as 1-3, 5"));
     let mut out: Vec<usize> = vec![];
-    let mut seen: std::collections::HashSet<usize> = std::collections::HashSet::new();
     for part in text.split([',', ';']).map(str::trim).filter(|p| !p.is_empty()) {
         let (a, b) = match part.split_once('-') {
             Some((a, b)) => (a.trim(), b.trim()),
@@ -406,7 +405,7 @@ pub fn parse_slide_range(text: &str, count: usize) -> Result<Vec<usize>> {
             return Err(bad("file.export", format!("the presentation has {count} slides; “{part}” is outside them")));
         }
         for i in lo - 1..hi {
-            if seen.insert(i) {
+            if !out.contains(&i) {
                 out.push(i);
             }
         }
@@ -770,16 +769,6 @@ mod tests {
 
     use super::{parse_slide_range, write_file};
 
-    #[test]
-    fn broad_and_repeated_slide_ranges_expand_once() {
-        // 200 copies of a 100,000-slide range: each index once, in order, without a scan per index.
-        let text = vec!["1-100000"; 200].join(",");
-        let v = parse_slide_range(&text, 100_000).unwrap();
-        assert_eq!(v.len(), 100_000);
-        assert!(v.windows(2).all(|w| w[0] < w[1]));
-        assert_eq!(parse_slide_range("3, 1-3, 2", 3).unwrap(), vec![2, 0, 1]);
-    }
-
     #[test]
     fn slide_range_rejects_plus_sign() {
         assert!(parse_slide_range("+2", 3).is_err());

crates/engine/src/cmd/review.rs

@@ -367,7 +367,7 @@ fn spelling(s: &mut Session, p: &Value) -> Result<Value> {
             }
             out.push(v);
         }
-        let rep: std::collections::HashSet<usize> = crate::spell::repeated(para, &default).iter().map(|w| w.start).collect();
+        let rep: Vec<usize> = crate::spell::repeated(para, &default).iter().map(|w| w.start).collect();
         for w in crate::spell::paragraph_words(para, &default) {
             if ignore.contains(&w.text.to_lowercase()) || rep.contains(&w.start) {
                 continue;

crates/engine/src/cmd/slide.rs

@@ -405,9 +405,8 @@ fn select_slides(s: &mut Session, p: &Value) -> Result<Value> {
     };
     s.select(|doc, sel| {
         if add {
-            let mut have: std::collections::HashSet<_> = sel.slides.iter().copied().collect();
             for i in &ids {
-                if have.insert(*i) {
+                if !sel.slides.contains(i) {
                     sel.slides.push(*i);
                 }
             }

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");