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

crates/geom/src/warp.rs

@@ -928,25 +928,11 @@ impl Warp {
             k_fill = 1.0;
         }
         zoom = zoom.max(k_fill);
-        // Per band, measured once: its widest line and its first and last lines' baselines.
-        let mut stats: Vec<Option<(f64, f64, f64)>> = vec![None; nb];
-        for (l, &b) in lines.iter().zip(&band_of) {
-            let w = l.extent.1 - l.extent.0;
-            if let Some(slot) = stats.get_mut(b) {
-                match slot {
-                    Some((widest, _, last)) => {
-                        *widest = widest.max(w);
-                        *last = l.ref_y;
-                    }
-                    None => *slot = Some((0.0f64.max(w), l.ref_y, l.ref_y)),
-                }
-            }
-        }
         let mut maps = Vec::with_capacity(n);
         let mut offsets = Vec::new();
         for (i, l) in lines.iter().enumerate() {
             let b = band_of.get(i).copied().unwrap_or(0);
-            let band = stats.get(b).copied().flatten();
+            let in_band = |j: &usize| band_of.get(*j) == Some(&b);
             match self.bands.get(b) {
                 Some(Band::Fill { .. }) | None => {
                     let (y0, y1) = band_y.get(b).copied().flatten().unwrap_or((0.0, 1.0));
@@ -955,12 +941,16 @@ impl Warp {
                 }
                 Some(Band::Follow { path, anchor }) => {
                     let len = path.length();
-                    let widest = band.map_or(0.0, |s| s.0);
+                    let widest = (0..n).filter(in_band).filter_map(|j| lines.get(j)).map(|l| l.extent.1 - l.extent.0).fold(0.0, f64::max);
                     let k = if widest > len && widest > 1e-9 { len / widest } else { 1.0 };
+                    let members: Vec<&WarpLine> = (0..n).filter(in_band).filter_map(|j| lines.get(j)).collect();
                     let ref_y = match anchor {
-                        LineAnchor::Last => band.map(|s| s.2),
-                        LineAnchor::First => band.map(|s| s.1),
-                        LineAnchor::Middle => band.map(|s| (s.1 + s.2) / 2.0),
+                        LineAnchor::Last => members.last().map(|l| l.ref_y),
+                        LineAnchor::First => members.first().map(|l| l.ref_y),
+                        LineAnchor::Middle => match (members.first(), members.last()) {
+                            (Some(a), Some(z)) => Some((a.ref_y + z.ref_y) / 2.0),
+                            _ => None,
+                        },
                     }
                     .unwrap_or(l.ref_y);
                     // Lines off the guide run on a parallel curve at their natural length.

crates/geom/src/warp/tests.rs

@@ -319,20 +319,3 @@ fn arch_and_inflate_handles_follow_the_pointer() {
     assert!(more > adjust_defaults("textInflate")[0], "{more}");
     assert!((more - 20_000.0).abs() < 1.0, "{more}");
 }
-
-#[test]
-fn many_lines_on_a_follow_band_are_mapped_from_one_measurement() {
-    // 50,000 lines on an arch: each line's scale and anchor come from the band measured once.
-    let w = warp("textArchUp", &[], rect()).unwrap();
-    let inner = Rect::new(7.2, 3.6, W - 7.2, H - 3.6);
-    let lines: Vec<WarpLine> = (0..50_000)
-        .map(|i| {
-            let y = i as f64 * 0.01;
-            WarpLine { ink: Some(Rect::new(190.0, y, 230.0, y + 1.0)), extent: (190.0, 230.0), ref_y: y + 1.0 }
-        })
-        .collect();
-    let m = w.mapper(&lines, inner);
-    // The last line sits on the arc, as with two lines.
-    let last = lines.len() - 1;
-    assert!(m.map(last, Point::new(210.0, lines[last].ref_y)).y.abs() < 0.05);
-}

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