Compare commits

..
Author SHA1 Message Date
Dylan M. Taylor 6b83c712da Animations: drop wall-clock bounds from the large morph and paragraph tests
On a loaded runner a ten-second bound can fail after every functional
assertion passed. The inputs stay large enough that a quadratic regression
hangs the test instead.
2026-11-02 20:56:50 -05:00
Dylan M. Taylor f7fe74cecd Animations: index morph matching and timeline lookups by shape
Morph pairing searched every shape of the next slide for each shape of the
current one, four times over, rebuilding shape text inside each comparison.
Timeline state looked up a shape's effects, paragraph owner and base colour
by scanning every effect, group and colour on the slide, once per shape and
paragraph drawn. Both are now indexed once, keeping the same match order.
2026-11-02 20:20:38 -05:00
8 changed files with 59 additions and 246 deletions
+38 -161
View File
@@ -37,146 +37,56 @@ pub struct ShapeParams<'a> {
pub language: Option<&'a str>,
}
/// Most bytes of text given to the shaper at once. The shaper lets one call grow its buffers to
/// 256 glyphs per character (a font's substitutions decide how many), so a long item is shaped in
/// pieces of this size, each with the rest of the paragraph as context.
const MAX_SHAPE_CHUNK: usize = 1024;
/// Most glyphs kept per character of a piece: a piece the font expands further is laid out one
/// glyph per character from the cmap instead.
const MAX_GLYPHS_PER_CHAR: usize = 32;
/// Shape `para[range]` with `face`, the rest of `para` as context. Glyphs are in visual order
/// (left to right) and clusters are byte offsets into `para`. `map` substitutes characters (All
/// Caps) without moving clusters. An empty or out-of-bounds range shapes nothing.
pub fn shape_range(face: &FontFace, para: &str, range: Range<usize>, params: &ShapeParams, map: impl Fn(char) -> char) -> Vec<ShapedGlyph> {
let (Some(_), Some(text), Some(_)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
let (Some(pre), Some(text), Some(post)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
return Vec::new();
};
let chunks = chunks(text, MAX_SHAPE_CHUNK);
let mut pieces: Vec<Vec<ShapedGlyph>> = Vec::with_capacity(chunks.len());
let mut out = Vec::with_capacity(text.len());
let shaped = face.hb().map(|hb| {
let shaper = face.shaper.shaper(&hb).instance(face.instance.as_ref()).build();
// Pieces of one item share the script the whole item would be guessed to have.
let item_script = (chunks.len() > 1 && params.script.is_none()).then(|| {
let mut probe = UnicodeBuffer::new();
for c in text.chars() {
probe.add(map(c), 0);
}
probe.guess_segment_properties();
probe.script()
});
for c in &chunks {
let r = (range.start + c.start)..(range.start + c.end);
let (Some(pre), Some(piece), Some(post)) = (para.get(..r.start), para.get(r.clone()), para.get(r.end..)) else { continue };
let mut buf = UnicodeBuffer::new();
buf.set_pre_context(pre);
buf.set_post_context(post);
for (i, c) in piece.char_indices() {
buf.add(map(c), (r.start + i) as u32);
}
buf.guess_segment_properties();
if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
buf.set_script(s);
} else if let Some(s) = item_script {
buf.set_script(s);
}
if let Some(l) =
params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
{
buf.set_language(l);
}
buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
let budget = piece.chars().count().saturating_mul(MAX_GLYPHS_PER_CHAR);
if gb.len() > budget {
// Font-controlled expansion past anything real text needs: keep it bounded.
pieces.push(cmap_glyphs(face, para, r, params.rtl, &map));
continue;
}
pieces.push(
gb.glyph_infos()
.iter()
.zip(gb.glyph_positions())
.map(|(info, pos)| ShapedGlyph {
gid: info.glyph_id,
cluster: info.cluster as usize,
x_advance: pos.x_advance,
x_offset: pos.x_offset,
y_offset: pos.y_offset,
})
.collect(),
);
let mut buf = UnicodeBuffer::new();
buf.set_pre_context(pre);
buf.set_post_context(post);
for (i, c) in text.char_indices() {
buf.add(map(c), (range.start + i) as u32);
}
buf.guess_segment_properties();
if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
buf.set_script(s);
}
if let Some(l) = params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
{
buf.set_language(l);
}
buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
for (info, pos) in gb.glyph_infos().iter().zip(gb.glyph_positions()) {
out.push(ShapedGlyph {
gid: info.glyph_id,
cluster: info.cluster as usize,
x_advance: pos.x_advance,
x_offset: pos.x_offset,
y_offset: pos.y_offset,
});
}
});
if shaped.is_none() {
if shaped.is_none()
&& let Some(f) = face.skrifa()
{
// No shaper for this face: one glyph per character from the cmap, in visual order.
return cmap_glyphs(face, para, range, params.rtl, &map);
}
// Each piece is in visual order; right to left, the later pieces come first.
if params.rtl {
pieces.reverse();
}
let mut out = Vec::with_capacity(pieces.iter().map(Vec::len).sum());
for p in pieces {
out.extend(p);
}
out
}
/// One glyph per character of `para[range]` from the cmap, in visual order.
fn cmap_glyphs(face: &FontFace, para: &str, range: Range<usize>, rtl: bool, map: &impl Fn(char) -> char) -> Vec<ShapedGlyph> {
let (Some(text), Some(f)) = (para.get(range.clone()), face.skrifa()) else { return Vec::new() };
let cmap = f.charmap();
let gm = f.glyph_metrics(Size::unscaled(), face.location());
let mut out = Vec::with_capacity(text.len());
for (i, c) in text.char_indices() {
let g = cmap.map(map(c)).unwrap_or_default();
let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
}
if rtl {
out.reverse();
}
out
}
/// `text` cut into byte ranges of at most `max` bytes (or one character, if longer), at the last
/// space of a piece where there is one, else before a character that starts a cluster (not a
/// combining mark or joiner, not after a joiner). Text that fits is one piece.
fn chunks(text: &str, max: usize) -> Vec<Range<usize>> {
use unicode_bidi::BidiClass::{BN, NSM};
let mut out = Vec::new();
let mut start = 0;
while text.len() - start > max {
let window = text.get(start..).unwrap_or_default();
let mut space = None;
let mut boundary = None;
let mut any = None;
let mut prev: Option<char> = None;
for (i, c) in window.char_indices() {
if i > max {
break;
}
if i > 0 {
any = Some(i);
let joined = prev.is_some_and(|p| matches!(unicode_bidi::bidi_class(p), BN));
if !joined && !matches!(unicode_bidi::bidi_class(c), NSM | BN) {
boundary = Some(i);
if prev.is_some_and(char::is_whitespace) {
space = Some(i);
}
}
}
prev = Some(c);
let cmap = f.charmap();
let gm = f.glyph_metrics(Size::unscaled(), face.location());
for (i, c) in text.char_indices() {
let g = cmap.map(map(c)).unwrap_or_default();
let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
}
if params.rtl {
out.reverse();
}
// A piece always moves forward by at least one character.
let first = window.chars().next().map_or(window.len(), char::len_utf8);
let cut = space.filter(|&i| i >= max / 2).or(boundary).or(any).unwrap_or(first).max(first);
out.push(start..start + cut);
start += cut;
}
if start < text.len() || out.is_empty() {
out.push(start..text.len());
}
out
}
@@ -211,37 +121,4 @@ mod tests {
// Not a char boundary.
assert!(shape_range(&face, "سنة", 1..2, &ShapeParams::default(), |c| c).is_empty());
}
#[test]
fn long_items_are_shaped_in_bounded_pieces() {
for text in ["word ".repeat(2_000), "e\u{301}".repeat(2_000), "x".repeat(5_000), "\u{1f469}\u{200d}\u{1f4bb} ".repeat(500)] {
let pieces = chunks(&text, MAX_SHAPE_CHUNK);
assert_eq!(pieces.first().map(|r| r.start), Some(0));
assert_eq!(pieces.last().map(|r| r.end), Some(text.len()));
for w in pieces.windows(2) {
assert_eq!(w[0].end, w[1].start);
}
for r in &pieces {
assert!(!r.is_empty() && r.len() <= MAX_SHAPE_CHUNK);
// Never before a combining mark, never after a joiner.
let rest = &text[r.end..];
assert!(!rest.starts_with('\u{301}'));
assert!(!text[..r.end].ends_with('\u{200d}') || rest.is_empty());
}
}
assert_eq!(chunks("short", MAX_SHAPE_CHUNK), vec![0..5]);
assert_eq!(chunks("", MAX_SHAPE_CHUNK), vec![0..0]);
}
#[test]
fn long_items_keep_every_cluster_in_visual_order() {
let face = FontDb::global().face(DEFAULT_FAMILY, "Regular");
let text = "ab cd ".repeat(1_000);
let g = shape_range(&face, &text, 0..text.len(), &ShapeParams::default(), |c| c);
assert_eq!(g.len(), text.len());
assert!(g.windows(2).all(|w| w[0].cluster < w[1].cluster));
let rtl = shape_range(&face, &text, 0..text.len(), &ShapeParams { rtl: true, ..Default::default() }, |c| c);
assert_eq!(rtl.len(), text.len());
assert!(rtl.windows(2).all(|w| w[0].cluster > w[1].cluster));
}
}
+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;