Compare commits

..
9 changed files with 123 additions and 119 deletions
+89 -34
View File
@@ -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);
+13
View File
@@ -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");
+6 -13
View File
@@ -210,20 +210,13 @@ pub fn table_styles_xml(used: &[String], defs: &[deckcraft_model::table::TableSt
let mut w = W::new();
w.open("a:tblStyleLst", A::new().a("xmlns:a", NS_A).a("def", "{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}"));
let names = deckcraft_model::table::table_styles();
// Indexes instead of scans: written ids (as given and ASCII lower-case), and the file's
// definitions by lower-case id (the first wins).
let mut done: std::collections::HashSet<&str> = std::collections::HashSet::new();
let mut done_lower: std::collections::HashSet<String> = std::collections::HashSet::new();
let mut def_of: std::collections::HashMap<String, &deckcraft_model::table::TableStyleDef> = std::collections::HashMap::new();
for d in defs {
def_of.entry(d.id.to_ascii_lowercase()).or_insert(d);
}
let mut done: Vec<&str> = vec![];
for s in used {
if !done.insert(s.as_str()) {
if done.contains(&s.as_str()) {
continue;
}
done_lower.insert(s.to_ascii_lowercase());
if let Some(d) = def_of.get(&s.to_ascii_lowercase())
done.push(s);
if let Some(d) = defs.iter().find(|d| d.id.eq_ignore_ascii_case(s))
&& crate::xml::parse(d.raw.as_bytes()).is_ok_and(|x| x.root.is("tblStyle"))
{
w.raw(&d.raw);
@@ -238,11 +231,11 @@ pub fn table_styles_xml(used: &[String], defs: &[deckcraft_model::table::TableSt
}
// Styles the file defined but no table uses still belong to the deck.
for d in defs {
if done_lower.contains(&d.id.to_ascii_lowercase()) {
if done.iter().any(|s| s.eq_ignore_ascii_case(&d.id)) {
continue;
}
if crate::xml::parse(d.raw.as_bytes()).is_ok_and(|x| x.root.is("tblStyle")) {
done_lower.insert(d.id.to_ascii_lowercase());
done.push(&d.id);
w.raw(&d.raw);
}
}
+7 -32
View File
@@ -53,8 +53,6 @@ pub struct Exp<'a> {
pub p: &'a Presentation,
pub pkg: PackageOut,
media_parts: HashMap<MediaId, String>,
/// Each media id's item in `p.media` (the first with the id, as `Presentation::media`).
media_at: HashMap<MediaId, usize>,
n_image: u32,
n_media: u32,
n_chart: u32,
@@ -65,8 +63,6 @@ pub struct Exp<'a> {
n_kept: u32,
pub slide_parts: HashMap<SlideId, String>,
pub table_styles: Vec<String>,
/// The ids in `table_styles`, for checking membership without a scan.
pub table_style_set: std::collections::HashSet<String>,
placeholder: Option<String>,
}
@@ -123,17 +119,12 @@ fn ext_for(content_type: &str, name: &str, data: &[u8]) -> String {
if !e.is_empty() && e.len() <= 5 && e.chars().all(|c| c.is_ascii_alphanumeric()) { e } else { "bin".into() }
}
impl<'a> Exp<'a> {
/// The media item `id`, found through the index rather than a scan of every item.
pub fn media(&self, id: MediaId) -> Option<&'a deckcraft_model::MediaItem> {
let p: &'a Presentation = self.p;
self.media_at.get(&id).and_then(|&i| p.media.get(i))
}
impl Exp<'_> {
fn media_part(&mut self, id: MediaId) -> Option<String> {
if let Some(p) = self.media_parts.get(&id) {
return Some(p.clone());
}
let m = self.media(id)?;
let m = self.p.media(id)?;
if m.data.is_empty() {
return None;
}
@@ -156,7 +147,7 @@ impl<'a> Exp<'a> {
}
/// A relationship from `o` to a media item (embedded part, or external link).
pub fn media_rel(&mut self, o: &mut Out, id: MediaId, kind: &str) -> Option<String> {
let m = self.media(id)?;
let m = self.p.media(id)?;
if m.data.is_empty() {
let link = m.link.clone()?;
return Some(o.rels.add(kind, &link, true));
@@ -165,7 +156,7 @@ impl<'a> Exp<'a> {
Some(o.rels.add(kind, &opc::relative(&o.name, &part), false))
}
pub fn media_rel_new(&mut self, o: &mut Out, id: MediaId, kind: &str) -> Option<String> {
let m = self.media(id)?;
let m = self.p.media(id)?;
if m.data.is_empty() {
return None;
}
@@ -498,8 +489,7 @@ fn valid_date(s: &str) -> bool {
/// A copy of the presentation with every slide pointing at a layout that exists.
fn sanitized(p: &Presentation) -> std::borrow::Cow<'_, Presentation> {
let mut need = p.masters.is_empty() || p.masters.iter().any(|m| m.layouts.is_empty());
let layouts: std::collections::HashSet<_> = p.masters.iter().flat_map(|m| m.layouts.iter().map(|l| l.id)).collect();
need |= p.slides.iter().any(|s| !layouts.contains(&s.layout));
need |= p.slides.iter().any(|s| p.layout(s.layout).is_none());
if !need {
return std::borrow::Cow::Borrowed(p);
}
@@ -542,13 +532,6 @@ pub fn export(p: &Presentation, main_ct: &str) -> Result<Vec<u8>, PptxError> {
p,
pkg: PackageOut::default(),
media_parts: HashMap::new(),
media_at: {
let mut m = HashMap::new();
for (i, item) in p.media.iter().enumerate() {
m.entry(item.id).or_insert(i);
}
m
},
n_image: 0,
n_media: 0,
n_chart: 0,
@@ -558,7 +541,6 @@ pub fn export(p: &Presentation, main_ct: &str) -> Result<Vec<u8>, PptxError> {
n_kept: 0,
slide_parts: HashMap::new(),
table_styles: vec![],
table_style_set: Default::default(),
placeholder: None,
};
for (i, s) in p.slides.iter().enumerate() {
@@ -977,16 +959,9 @@ fn section_slides(p: &Presentation) -> Vec<(String, Vec<usize>)> {
if out.is_empty() {
return out;
}
// Each slide's first section, found once: a section may name a slide many times.
let mut first: HashMap<SlideId, usize> = HashMap::new();
for (k, sec) in p.sections.iter().enumerate() {
for id in &sec.slides {
first.entry(*id).or_insert(k);
}
}
let mut cur = 0usize;
for (i, s) in p.slides.iter().enumerate() {
if let Some(&k) = first.get(&s.id)
if let Some(k) = p.sections.iter().position(|sec| sec.slides.contains(&s.id))
&& k >= cur
{
cur = k;
@@ -1052,7 +1027,7 @@ fn write_embedded_fonts(x: &mut Exp, o: &mut Out) -> Vec<WrittenFont> {
if let Some(rid) = seen_part.get(&id) {
return Some(rid.clone());
}
let m = x.media(id)?;
let m = x.p.media(id)?;
if m.data.is_empty() || m.data.len() > 32 * 1024 * 1024 {
return None;
}
+3 -3
View File
@@ -100,7 +100,7 @@ pub fn fill(w: &mut W, x: &mut Exp, o: &mut Out, f: &Fill) {
pub fn blip_fill(w: &mut W, x: &mut Exp, o: &mut Out, tag: &str, pf: &PictureFill) {
// An image that lives outside the package is a linked picture: `a:blip` names it through
// `r:link`; `r:embed` may only reference a part inside the package.
let linked = x.media(pf.media).is_some_and(|m| m.data.is_empty() && m.link.is_some());
let linked = x.p.media(pf.media).is_some_and(|m| m.data.is_empty() && m.link.is_some());
let rid = x.media_rel(o, pf.media, "image").unwrap_or_else(|| x.placeholder_rel(o));
w.open(tag, A::new().a("rotWithShape", if pf.upright { "0" } else { "1" }));
let adj = &pf.adjust;
@@ -441,7 +441,7 @@ pub fn hyperlink(w: &mut W, x: &mut Exp, o: &mut Out, tag: &str, h: &Hyperlink)
return;
};
w.open(tag, attrs);
let name = x.media(sound_id).map(|m| sound_label(&m.name)).unwrap_or_else(|| "sound.wav".into());
let name = x.p.media(sound_id).map(|m| sound_label(&m.name)).unwrap_or_else(|| "sound.wav".into());
w.empty("a:snd", A::new().a("r:embed", sound_rid).a("name", name));
w.close(tag);
}
@@ -587,7 +587,7 @@ pub fn ppr(w: &mut W, x: &mut Exp, o: &mut Out, tag: &str, level: Option<u8>, p:
Some(Bullet::Picture { media }) => match x.media_rel(o, *media, "image") {
Some(rid) => {
w.open0("a:buBlip");
let a = if x.media(*media).is_some_and(|m| m.data.is_empty() && m.link.is_some()) {
let a = if x.p.media(*media).is_some_and(|m| m.data.is_empty() && m.link.is_some()) {
A::new().a("r:link", &rid)
} else {
A::new().a("r:embed", &rid)
+4 -4
View File
@@ -446,7 +446,7 @@ pub fn shape(w: &mut W, x: &mut Exp, o: &mut Out, cx: &mut Ctx, s: &Shape, depth
}
fn model_rel(x: &mut Exp, o: &mut Out, media: deckcraft_model::MediaId) -> Option<String> {
if x.media(media).is_none_or(|m| m.data.is_empty()) {
if x.p.media(media).is_none_or(|m| m.data.is_empty()) {
return None;
}
x.media_rel(o, media, crate::opc::RT_MODEL3D)
@@ -479,7 +479,7 @@ fn write_model(
return;
};
let id = cx.id_for(s);
let poster = poster.filter(|p| x.media(*p).is_some_and(|m| !m.data.is_empty()));
let poster = poster.filter(|p| x.p.media(*p).is_some_and(|m| !m.data.is_empty()));
let Some(poster) = poster else {
write_model_part(w, x, o, id, s, &rid);
return;
@@ -700,7 +700,7 @@ fn table(w: &mut W, x: &mut Exp, o: &mut Out, t: &Table) {
t.normalize();
w.open0("a:tbl");
let (guid, _) = crate::tables::guid_for_style(&t.style);
if x.table_style_set.insert(t.style.clone()) {
if !x.table_styles.contains(&t.style) {
x.table_styles.push(t.style.clone());
}
w.open(
@@ -881,7 +881,7 @@ fn opaque(
p.name = label.to_string();
}
match preview {
Some(m) if x.media(m).is_some() => {
Some(m) if x.p.media(m).is_some() => {
p.kind = ShapeKind::Picture { fill: deckcraft_model::style::PictureFill { media: m, ..Default::default() } };
p.ph = None;
shape_with_id(w, x, o, cx, &p, id);
+1 -1
View File
@@ -16,7 +16,7 @@ pub fn transition(w: &mut W, x: &mut Exp, o: &mut Out, t: &Transition) {
601..=900 => "med",
_ => "slow",
};
let sound = t.sound.and_then(|m| x.media_rel(o, m, "audio").map(|r| (r, x.media(m).map(|i| i.name.clone()).unwrap_or_default())));
let sound = t.sound.and_then(|m| x.media_rel(o, m, "audio").map(|r| (r, x.p.media(m).map(|i| i.name.clone()).unwrap_or_default())));
let snd = |w: &mut W| {
if let Some((r, name)) = &sound {
w.open0("p:sndAc");
-31
View File
@@ -1,31 +0,0 @@
//! Export looks media, layouts, sections and table styles up by id: a deck with many of each and
//! many references to the last ones exports in time linear in its size.
use std::sync::Arc;
use deckcraft_model::style::PictureFill;
use deckcraft_model::{Section, Shape, ShapeId, ShapeKind, defaults};
#[test]
fn many_media_sections_and_table_styles_export() {
let mut p = defaults::new_presentation(None);
// 5,000 media items; 5,000 pictures of the last one.
let mut last = None;
for i in 0..5_000u32 {
last = p.add_media(&format!("m{i}.png"), "image/png", i.to_le_bytes().to_vec());
}
let last = last.unwrap();
let pic = |k: u32| Shape {
id: ShapeId(100_000 + k),
kind: ShapeKind::Picture { fill: PictureFill { media: last, ..Default::default() } },
..Default::default()
};
Arc::make_mut(&mut p.slides[0]).shapes = (0..5_000).map(pic).collect();
// A section naming the slide 50,000 times, after 2,000 empty sections.
let id = p.slides[0].id;
p.sections = (0..2_000).map(|i| Section { name: format!("s{i}"), slides: vec![] }).collect();
p.sections.push(Section { name: "last".into(), slides: vec![id; 50_000] });
let bytes = deckcraft_pptx::export(&p).expect("export");
let q = deckcraft_pptx::import(&bytes).expect("import");
assert_eq!(q.slides[0].shapes.iter().filter(|s| matches!(s.kind, ShapeKind::Picture { .. })).count(), 5_000);
}
-1
View File
@@ -9,7 +9,6 @@ mod corpus_kinds;
mod corpus_media;
mod corpus_style;
mod corpus_themes;
mod export_scale;
mod fills;
mod kept_parts;
mod locks;