pptx: index media, layouts, sections and table styles on export

crates/pptx/src/tables.rs

@@ -210,13 +210,20 @@ 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();
-    let mut done: Vec<&str> = vec![];
+    // 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);
+    }
     for s in used {
-        if done.contains(&s.as_str()) {
+        if !done.insert(s.as_str()) {
             continue;
         }
-        done.push(s);
-        if let Some(d) = defs.iter().find(|d| d.id.eq_ignore_ascii_case(s))
+        done_lower.insert(s.to_ascii_lowercase());
+        if let Some(d) = def_of.get(&s.to_ascii_lowercase())
             && crate::xml::parse(d.raw.as_bytes()).is_ok_and(|x| x.root.is("tblStyle"))
         {
             w.raw(&d.raw);
@@ -231,11 +238,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.iter().any(|s| s.eq_ignore_ascii_case(&d.id)) {
+        if done_lower.contains(&d.id.to_ascii_lowercase()) {
             continue;
         }
         if crate::xml::parse(d.raw.as_bytes()).is_ok_and(|x| x.root.is("tblStyle")) {
-            done.push(&d.id);
+            done_lower.insert(d.id.to_ascii_lowercase());
             w.raw(&d.raw);
         }
     }

crates/pptx/src/write.rs

@@ -53,6 +53,8 @@ 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,
@@ -63,6 +65,8 @@ 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>,
 }
 
@@ -119,12 +123,17 @@ 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 Exp<'_> {
+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))
+    }
     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.p.media(id)?;
+        let m = self.media(id)?;
         if m.data.is_empty() {
             return None;
         }
@@ -147,7 +156,7 @@ impl Exp<'_> {
     }
     /// 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.p.media(id)?;
+        let m = self.media(id)?;
         if m.data.is_empty() {
             let link = m.link.clone()?;
             return Some(o.rels.add(kind, &link, true));
@@ -156,7 +165,7 @@ impl Exp<'_> {
         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.p.media(id)?;
+        let m = self.media(id)?;
         if m.data.is_empty() {
             return None;
         }
@@ -489,7 +498,8 @@ 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());
-    need |= p.slides.iter().any(|s| p.layout(s.layout).is_none());
+    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));
     if !need {
         return std::borrow::Cow::Borrowed(p);
     }
@@ -532,6 +542,13 @@ 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,
@@ -541,6 +558,7 @@ 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() {
@@ -959,9 +977,16 @@ 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) = p.sections.iter().position(|sec| sec.slides.contains(&s.id))
+        if let Some(&k) = first.get(&s.id)
             && k >= cur
         {
             cur = k;
@@ -1027,7 +1052,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.p.media(id)?;
+        let m = x.media(id)?;
         if m.data.is_empty() || m.data.len() > 32 * 1024 * 1024 {
             return None;
         }

crates/pptx/src/write/dml.rs

@@ -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.p.media(pf.media).is_some_and(|m| m.data.is_empty() && m.link.is_some());
+    let linked = x.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.p.media(sound_id).map(|m| sound_label(&m.name)).unwrap_or_else(|| "sound.wav".into());
+    let name = x.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.p.media(*media).is_some_and(|m| m.data.is_empty() && m.link.is_some()) {
+                let a = if x.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)

crates/pptx/src/write/shapes.rs

@@ -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.p.media(media).is_none_or(|m| m.data.is_empty()) {
+    if x.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.p.media(*p).is_some_and(|m| !m.data.is_empty()));
+    let poster = poster.filter(|p| x.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_styles.contains(&t.style) {
+    if x.table_style_set.insert(t.style.clone()) {
         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.p.media(m).is_some() => {
+        Some(m) if x.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);

crates/pptx/src/write/timing.rs

@@ -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.p.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.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");

crates/pptx/tests/it/export_scale.rs

@@ -0,0 +1,31 @@
+//! 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);
+}

crates/pptx/tests/it/main.rs

@@ -9,6 +9,7 @@ mod corpus_kinds;
 mod corpus_media;
 mod corpus_style;
 mod corpus_themes;
+mod export_scale;
 mod fills;
 mod kept_parts;
 mod locks;