GitCorner

Code

ossartcraftwordcraft🌐
6ef13b2cc8a6
//! Hostile documents whose layout work or memory would otherwise grow far past their size: each
//! is bounded by a cap, and real documents stay well under it.

use crate::ctx::Outlines;
use crate::*;
use wordcraft_doc::props::HeightRule;
use wordcraft_doc::table::{MAX_COLS, Table};
use wordcraft_doc::{Block, PartKind, Pos, TextBody, para_block};

fn lay(doc: &Document) -> DocLayout {
    let mut c = LayoutCache::new();
    layout(doc, &mut c, &LayoutOptions::default())
}

/// A `w` × `h` text box showing `text`, inline at the end of body paragraph `para`; its story id.
fn text_box(d: &mut Document, para: usize, text: &str, w: f32, h: f32) -> u32 {
    let id = d.add_part(PartKind::TextBox, vec![para_block(Paragraph::with_text(text, Default::default()))]);
    if let Some(p) = d.parts.get_mut(&id) {
        p.body = TextBody::default();
    }
    let shape = InlineObject::Shape {
        kind: wordcraft_doc::para::ShapeKind::TextBox,
        w,
        h,
        fill: None,
        stroke: None,
        stroke_width: 1.0,
        float: Default::default(),
        story: Some(id),
        effects: Default::default(),
        freeform: None,
        extra: Default::default(),
    };
    let off = d.para(StoryRef::Body, &Path::top(para)).map_or(0, |p| p.len());
    d.insert_object(&Pos::body(para, off), shape, &Default::default()).unwrap();
    id
}

#[test]
fn a_linked_chain_lays_its_story_out_for_a_bounded_amount_of_work() {
    // Forty linked boxes, each a line deep and each a different width, over a long story: every
    // width would lay the whole story out again. Past the work cap, later boxes reuse the
    // nearest width already laid out, so every box still shows its share of the story.
    textbox::FLOW_WORK_CAP.with(|c| c.set(2000));
    let n = 40;
    let mut d = Document::from_text(&vec!["p"; n].join("\n"));
    let story = "Words that run on and on through every box of the chain. ".repeat(200);
    let ids: Vec<u32> = (0..n).map(|i| text_box(&mut d, i, if i == 0 { &story } else { "" }, 100.0 + 3.0 * i as f32, 28.0)).collect();
    for w in ids.windows(2) {
        d.parts.get_mut(&w[0]).unwrap().body.next = Some(w[1]);
    }
    let l = lay(&d);
    let lines: Vec<&Placed> =
        l.pages.iter().flat_map(|p| &p.items).filter(|it| matches!(it, Placed::Lines { story: StoryRef::Part(s), .. } if *s == ids[0])).collect();
    assert_eq!(lines.len(), n, "every box shows the story");
    // Each width the story was laid out at is its own paragraph layout.
    let mut widths: Vec<usize> =
        lines.iter().filter_map(|it| if let Placed::Lines { para, .. } = it { Some(Arc::as_ptr(para) as usize) } else { None }).collect();
    widths.sort_unstable();
    widths.dedup();
    textbox::FLOW_WORK_CAP.with(|c| c.set(textbox::MAX_FLOW_WORK));
    // The cap is spent after the first few layouts (each is far over 2000 / 8 work).
    assert!(widths.len() <= 8, "{} widths laid the story out", widths.len());
}

#[test]
fn twenty_distinct_widths_of_an_ordinary_story_all_keep_their_width() {
    // A real chain of 20 boxes, 100, 105, ... 195 pt wide: each is laid out at its own width.
    let n = 20;
    let mut d = Document::from_text(&vec!["p"; n].join("\n"));
    let story = "Words that run on and on through every box of the chain. ".repeat(200);
    let ids: Vec<u32> = (0..n).map(|i| text_box(&mut d, i, if i == 0 { &story } else { "" }, 100.0 + 5.0 * i as f32, 28.0)).collect();
    for w in ids.windows(2) {
        d.parts.get_mut(&w[0]).unwrap().body.next = Some(w[1]);
    }
    let mut widths = story_layouts(&lay(&d), ids[0]);
    assert_eq!(widths.len(), n, "every box shows the story");
    widths.sort_unstable();
    widths.dedup();
    assert_eq!(widths.len(), n, "every box has a layout at its own width");
}

/// How many times story layouts ran while `doc` was laid out with the chain work cap at `cap`.
fn chain_layouts(d: &Document, cap: usize) -> usize {
    textbox::FLOW_WORK_CAP.with(|c| c.set(cap));
    textbox::FLOW_LAYOUTS.with(|c| c.set(0));
    lay(d);
    textbox::FLOW_WORK_CAP.with(|c| c.set(textbox::MAX_FLOW_WORK));
    textbox::FLOW_LAYOUTS.with(|c| c.get())
}

/// `n` linked boxes `w0`, `w0 + 0.1`, ... pt wide (each its own layout) and a line deep, the
/// first holding `blocks`; the first box's id.
fn hairline_chain(d: &mut Document, n: usize, w0: f32, blocks: Vec<Arc<Block>>) -> u32 {
    let ids: Vec<u32> = (0..n).map(|i| text_box(d, i, "", w0 + 0.1 * i as f32, 28.0)).collect();
    for w in ids.windows(2) {
        d.parts.get_mut(&w[0]).unwrap().body.next = Some(w[1]);
    }
    d.parts.get_mut(&ids[0]).unwrap().blocks = blocks;
    ids[0]
}

#[test]
fn a_chain_whose_story_shows_little_still_pays_for_its_text() {
    // All 256 boxes a hair apart in width, each showing one short visible line of a story that
    // hides about 1 MB of text between them: each layout gives some 300 lines but works through
    // the whole story. Charged by its lines alone, every width was laid out (256 times the story).
    let n = wordcraft_doc::MAX_LINKED_BOXES;
    let mut d = Document::from_text(&vec!["p"; n].join("\n"));
    let hidden = "Hidden words that never show. ".repeat(3500 / 30);
    let hide = wordcraft_doc::props::CharProps { hidden: Some(true), ..Default::default() };
    let story = (0..300)
        .map(|k| {
            let shown = format!("Line {k}.");
            let mut p = Paragraph::with_text(&format!("{shown}{hidden}"), Default::default());
            p.runs = vec![
                wordcraft_doc::para::Run { len: shown.len(), props: Default::default() },
                wordcraft_doc::para::Run { len: hidden.len(), props: hide.clone() },
            ];
            p.touch();
            para_block(p)
        })
        .collect();
    hairline_chain(&mut d, n, 300.0, story);
    // Ordinary stories of this many lines keep all 256 widths under this cap.
    let layouts = chain_layouts(&d, 100_000);
    assert!(layouts <= 8, "{layouts} layouts of a 1 MB story");
}

#[test]
fn a_chain_of_wide_boxes_pays_for_a_long_paragraph() {
    // 256 wide boxes a hair apart over one long paragraph: few lines per layout, but each
    // layout shapes all of it.
    let n = wordcraft_doc::MAX_LINKED_BOXES;
    let mut d = Document::from_text(&vec!["p"; n].join("\n"));
    let story = "Words that run on and on through every box of the chain. ".repeat(64 * 1024 / 58);
    hairline_chain(&mut d, n, 1500.0, vec![para_block(Paragraph::with_text(&story, Default::default()))]);
    let layouts = chain_layouts(&d, 2000);
    assert!(layouts <= 4, "{layouts} layouts of a 64 KB story");
}

/// The paragraph layouts (by address) showing story `head` across the document.
fn story_layouts(l: &DocLayout, head: u32) -> Vec<usize> {
    l.pages
        .iter()
        .flat_map(|p| &p.items)
        .filter_map(|it| match it {
            Placed::Lines { story: StoryRef::Part(s), para, .. } if *s == head => Some(Arc::as_ptr(para) as usize),
            _ => None,
        })
        .collect()
}

#[test]
fn stacked_boxes_of_any_width_share_a_layout() {
    // Stacked text is laid out one letter to a line whatever the box's width.
    let n = 20;
    let mut d = Document::from_text(&vec!["p"; n].join("\n"));
    let story = "Stacked letters run on through every box. ".repeat(20);
    let ids: Vec<u32> = (0..n).map(|i| text_box(&mut d, i, if i == 0 { &story } else { "" }, 100.0 + 3.0 * i as f32, 28.0)).collect();
    for id in &ids {
        d.parts.get_mut(id).unwrap().body.vert = wordcraft_doc::props::TextVert::Stacked;
    }
    for w in ids.windows(2) {
        d.parts.get_mut(&w[0]).unwrap().body.next = Some(w[1]);
    }
    let mut widths = story_layouts(&lay(&d), ids[0]);
    assert_eq!(widths.len(), n, "every box shows the story");
    widths.sort_unstable();
    widths.dedup();
    assert_eq!(widths.len(), 1, "one layout for every stacked box");
}

#[test]
fn past_the_cap_a_box_takes_a_layout_in_its_own_direction() {
    // The cap is full of horizontal widths when a vertical box comes: it lays the story out
    // its own way rather than showing a horizontal layout.
    textbox::FLOW_WORK_CAP.with(|c| c.set(2000));
    let n = 17;
    let mut d = Document::from_text(&vec!["p"; n].join("\n"));
    let story = "Words that run on and on through every box of the chain. ".repeat(200);
    let ids: Vec<u32> = (0..n).map(|i| text_box(&mut d, i, if i == 0 { &story } else { "" }, 100.0 + 3.0 * i as f32, 28.0)).collect();
    if let Some(last) = ids.last() {
        d.parts.get_mut(last).unwrap().body.vert = wordcraft_doc::props::TextVert::Vert;
    }
    for w in ids.windows(2) {
        d.parts.get_mut(&w[0]).unwrap().body.next = Some(w[1]);
    }
    let mut widths = story_layouts(&lay(&d), ids[0]);
    assert_eq!(widths.len(), n, "every box shows the story");
    widths.sort_unstable();
    widths.dedup();
    assert!(widths.len() > 1 && widths.len() < n, "{} layouts: the vertical box has its own, the rest are shared", widths.len());
    // The vertical box's layout is none of the horizontal boxes', still past the cap.
    let mut all = story_layouts(&lay(&d), ids[0]);
    textbox::FLOW_WORK_CAP.with(|c| c.set(textbox::MAX_FLOW_WORK));
    let vertical = all.pop();
    assert!(vertical.is_some_and(|v| !all.contains(&v)), "the vertical box shares a horizontal layout");
}

#[test]
fn boxes_a_hair_apart_in_width_share_a_layout() {
    // Resized boxes differ by fractions of a point; those within a twentieth of a point of each
    // other share one layout of the story.
    let n = 30;
    let mut d = Document::from_text(&vec!["p"; n].join("\n"));
    let story = "Words that run on and on through every box of the chain. ".repeat(100);
    let ids: Vec<u32> = (0..n).map(|i| text_box(&mut d, i, if i == 0 { &story } else { "" }, 150.0 + 0.0005 * i as f32, 28.0)).collect();
    for w in ids.windows(2) {
        d.parts.get_mut(&w[0]).unwrap().body.next = Some(w[1]);
    }
    let l = lay(&d);
    let mut widths: Vec<usize> = l
        .pages
        .iter()
        .flat_map(|p| &p.items)
        .filter_map(|it| match it {
            Placed::Lines { story: StoryRef::Part(s), para, .. } if *s == ids[0] => Some(Arc::as_ptr(para) as usize),
            _ => None,
        })
        .collect();
    assert_eq!(widths.len(), n, "every box shows the story");
    widths.sort_unstable();
    widths.dedup();
    assert_eq!(widths.len(), 1, "one layout for every box");
}

#[test]
fn repeated_header_items_are_capped_across_the_table() {
    // An exact-height header row keeps thousands of overflowing paragraphs without growing, and
    // repeats on each of hundreds of pages: every page would copy all of them.
    let mut t = Table::new(201, 1, 468.0);
    t.rows[0].props.header = true;
    t.rows[0].props.height = Some(20.0);
    t.rows[0].props.height_rule = HeightRule::Exact;
    t.rows[0].cells[0].blocks = (0..3000).map(|_| para_block(Paragraph::with_text("x", Default::default()))).collect();
    for row in t.rows.iter_mut().skip(1) {
        row.props.height = Some(600.0);
        row.props.height_rule = HeightRule::Exact;
    }
    let mut d = Document::from_text("");
    d.insert_block(StoryRef::Body, &Path::top(1), Block::Table(t)).unwrap();
    let l = lay(&d);
    assert!(l.pages.len() >= 200, "{} pages", l.pages.len());
    let items: usize = l.pages.iter().map(|p| p.items.len()).sum();
    // The first page's header and each page's body row come on top of the repeats.
    assert!(items <= MAX_HEADER_ITEMS + 3000 + 50 * l.pages.len(), "{items} items placed");
    // An ordinary table's header still repeats on every page.
    let mut t = Table::new(80, 2, 468.0);
    t.rows[0].props.header = true;
    let mut d = Document::from_text("");
    d.insert_block(StoryRef::Body, &Path::top(1), Block::Table(t)).unwrap();
    let l = lay(&d);
    assert!(l.pages.len() >= 2);
    for p in &l.pages {
        assert!(p.items.iter().any(|i| matches!(i, Placed::Cell { row: 0, .. })), "the header repeats");
    }
}

#[test]
fn a_huge_grid_after_is_bounded_like_the_docx_readers() {
    // A native document can say a row leaves four billion columns empty after its cells.
    let mut t = Table::new(1, 2, 468.0);
    t.rows[0].props.grid_after = u32::MAX;
    t.grid.clear();
    assert!(t.cols() <= 2 + MAX_COLS, "{} columns", t.cols());
    let mut d = Document::from_text("");
    d.insert_block(StoryRef::Body, &Path::top(1), Block::Table(t)).unwrap();
    let l = lay(&d);
    assert!(l.pages[0].items.iter().any(|i| matches!(i, Placed::Cell { row: 0, cell: 1, .. })));
}

/// A `size` × `size` PNG, transparent but for an opaque disc in the middle.
fn disc_png(size: u32) -> Vec<u8> {
    let c = size as f32 / 2.0;
    let img = image::RgbaImage::from_fn(size, size, |x, y| {
        let (dx, dy) = (x as f32 + 0.5 - c, y as f32 + 0.5 - c);
        image::Rgba([0, 0, 0, if dx * dx + dy * dy < c * c * 0.5 { 255 } else { 0 }])
    });
    wordcraft_geom::picture::encode_format(&image::DynamicImage::from(img), image::ImageFormat::Png).unwrap()
}

#[test]
fn a_picture_cropped_many_ways_is_decoded_once() {
    let png = disc_png(64);
    let mut alphas = contour::Alphas::default();
    for i in 0..300 {
        let f = i as f32 / 1000.0;
        assert!(alphas.outline(&png, [f, f, 0.0, 0.0]).is_ok_and(|o| o.is_some()), "crop {i} follows the disc");
    }
    assert_eq!(alphas.decoded, 64 * 64, "one decode for every crop");
    // A crop's outline is the one the picture alone gives.
    let mut fresh = contour::Alphas::default();
    assert_eq!(alphas.outline(&png, [0.1, 0.0, 0.2, 0.0]), fresh.outline(&png, [0.1, 0.0, 0.2, 0.0]));
}

#[test]
fn pictures_cropped_in_turn_are_each_decoded_once() {
    // Crops alternating between two pictures don't decode either again: enough of them would
    // otherwise spend the budget on pictures that fit in it.
    let (a, b) = (disc_png(64), disc_png(32));
    let mut alphas = contour::Alphas::default();
    for i in 0..300 {
        let f = i as f32 / 1000.0;
        assert!(alphas.outline(&a, [f, 0.0, 0.0, 0.0]).is_ok_and(|o| o.is_some()), "crop {i} of a");
        assert!(alphas.outline(&b, [0.0, f, 0.0, 0.0]).is_ok_and(|o| o.is_some()), "crop {i} of b");
    }
    assert_eq!(alphas.decoded, 64 * 64 + 32 * 32, "one decode per picture");
}

#[test]
fn decoding_pictures_stops_at_the_layouts_budget() {
    let (a, b) = (disc_png(64), disc_png(32));
    let mut alphas = contour::Alphas::default();
    alphas.decoded = contour::MAX_DECODED_PIXELS - 64 * 64 + 1;
    // Too many pixels left to decode: the picture wraps as its rectangle, and says why.
    assert_eq!(alphas.outline(&a, [0.0; 4]), Err(contour::OverBudget));
    // A smaller one still fits.
    assert!(alphas.outline(&b, [0.0; 4]).is_ok_and(|o| o.is_some()));
    assert!(alphas.decoded <= contour::MAX_DECODED_PIXELS);
    // Pictures alternating past the budget aren't decoded again.
    for _ in 0..10 {
        assert_eq!(alphas.outline(&a, [0.0; 4]), Err(contour::OverBudget));
        let _ = alphas.outline(&b, [0.0; 4]);
    }
    assert!(alphas.decoded <= contour::MAX_DECODED_PIXELS);
}

/// A `size` × `size` PNG with no transparency.
fn opaque_png(size: u32) -> Vec<u8> {
    let img = image::RgbImage::from_pixel(size, size, image::Rgb([0, 0, 0]));
    wordcraft_geom::picture::encode_format(&image::DynamicImage::from(img), image::ImageFormat::Png).unwrap()
}

#[test]
fn opaque_pictures_take_none_of_the_decoding_budget() {
    // Pictures whose header says they have no transparency have no outline to find: decoding
    // them would only spend the budget a transparent picture after them needs.
    let (opaque, disc) = (opaque_png(64), disc_png(64));
    let mut alphas = contour::Alphas::default();
    alphas.decoded = contour::MAX_DECODED_PIXELS - 64 * 64;
    for _ in 0..3 {
        assert_eq!(alphas.outline(&opaque, [0.0; 4]), Ok(None));
    }
    assert!(alphas.outline(&disc, [0.0; 4]).is_ok_and(|o| o.is_some()), "the transparent picture still has its outline");
    assert_eq!(alphas.decoded, contour::MAX_DECODED_PIXELS);
}

#[test]
fn a_picture_refused_for_the_budget_is_not_cached_across_layouts() {
    // One layout ran out of budget before this picture; the next has a budget of its own.
    let disc = Arc::new(disc_png(64));
    let mut outlines = HashMap::new();
    let key = ("p".to_string(), 1, 2, [0; 4]);
    let mut spent = contour::Alphas::default();
    spent.decoded = contour::MAX_DECODED_PIXELS;
    assert!(picture_outline(&mut outlines, &mut spent, key.clone(), &disc, [0.0; 4]).is_none());
    assert!(outlines.is_empty(), "the refusal isn't kept");
    let mut fresh = contour::Alphas::default();
    assert!(picture_outline(&mut outlines, &mut fresh, key.clone(), &disc, [0.0; 4]).is_some());
    assert!(outlines.get(&key).is_some_and(|(_, o, _)| o.is_some()), "the outline is kept");
}

/// The outline cache outlives the documents it is used with and tells pictures apart by their
/// bytes' address: each entry keeps that allocation (a weak reference, not the bytes' owner), so
/// it can't be freed and the address given to another picture's bytes while the entry is kept.
#[test]
fn a_kept_outline_holds_on_to_its_pictures_allocation() {
    let disc = Arc::new(disc_png(64));
    let mut outlines = HashMap::new();
    let key = ("p".to_string(), Arc::as_ptr(&disc) as usize, disc.len(), [0; 4]);
    assert!(picture_outline(&mut outlines, &mut contour::Alphas::default(), key.clone(), &disc, [0.0; 4]).is_some());
    let Some((weak, ..)) = outlines.get(&key) else { panic!("the outline is kept") };
    assert!(std::ptr::eq(weak.as_ptr(), Arc::as_ptr(&disc)), "the entry refers to its own picture's bytes");
    assert_eq!((Arc::strong_count(&disc), Arc::weak_count(&disc)), (1, 1), "a weak reference: the document still owns the bytes");
    drop(disc);
    assert!(weak.upgrade().is_none(), "the bytes are freed with the document; only their allocation is kept");
}

/// A floating Drawing Canvas in a header cell is one `Clip` holding its members, and re-placing
/// the header clones every one of them: they all count against the repeat budget.
#[test]
fn a_clipped_group_costs_its_members_when_a_header_repeats() {
    let rule = || Placed::Rule { x0: 0.0, y0: 0.0, x1: 1.0, y1: 0.0, border: Default::default() };
    let clip = |items: Vec<Placed>| Placed::Clip { rect: Rect::new(0.0, 0.0, 10.0, 10.0), spin: Default::default(), items };
    let big = usize::MAX;
    assert_eq!(placed_cost(&rule(), big), 1);
    assert_eq!(placed_cost(&clip((0..1000).map(|_| rule()).collect()), big), 1001);
    // Nested groups count too, however deep: every descendant is charged.
    assert_eq!(placed_cost(&clip(vec![clip(vec![rule(), rule()]), rule()]), big), 5);
    let mut deep = clip((0..1000).map(|_| rule()).collect());
    for _ in 0..20 {
        deep = clip(vec![deep]);
    }
    assert_eq!(placed_cost(&deep, big), 1021, "members below the eighth level still cost one each");
    // Counting stops once past the limit, so a huge or very deep group is cheap to count.
    assert_eq!(placed_cost(&deep, 10), 11);
    let mut deeper = rule();
    for _ in 0..100_000 {
        deeper = clip(vec![deeper]);
    }
    assert_eq!(placed_cost(&deeper, 50), 51);
    assert_eq!(placed_cost(&deeper, big), 100_001);
    std::mem::forget(deeper);
}

/// The linked-box work budget counts a clipped group's members, nested groups included.
#[test]
fn flow_work_counts_clip_members() {
    let rule = || Placed::Rule { x0: 0.0, y0: 0.0, x1: 1.0, y1: 0.0, border: Default::default() };
    let clip = |items: Vec<Placed>| Placed::Clip { rect: Rect::new(0.0, 0.0, 10.0, 10.0), spin: Default::default(), items };
    let mut deep = clip((0..100).map(|_| rule()).collect());
    for _ in 0..12 {
        deep = clip(vec![deep, rule()]);
    }
    assert_eq!(textbox::flow_work(&[rule(), deep]), 1 + 100 + 1 + 12 * 2);
}

/// Lines inside a clipped group (a text box on a canvas) cost each line, as they do outside one.
#[test]
fn flow_work_counts_each_line_in_a_clip() {
    let l = lay(&Document::from_text(&"Words that run on and on. ".repeat(200)));
    let lines = l.pages.iter().flat_map(|p| &p.items).find(|it| matches!(it, Placed::Lines { .. })).cloned().unwrap();
    let (l0, l1) = match &lines {
        Placed::Lines { l0, l1, .. } => (*l0, *l1),
        _ => (0, 0),
    };
    assert!(l1 - l0 > 1);
    let clip = Placed::Clip { rect: Rect::new(0.0, 0.0, 10.0, 10.0), spin: Default::default(), items: vec![lines] };
    assert_eq!(textbox::flow_work(&[clip]), 1 + (l1 - l0));
}

#[test]
fn repeated_header_items_are_capped_across_all_the_tables_of_a_layout() {
    // Each table's repeats used to have a budget of their own: a hundred tables, a hundred times
    // the cap.
    let table = || {
        let mut t = Table::new(201, 1, 468.0);
        t.rows[0].props.header = true;
        t.rows[0].props.height = Some(20.0);
        t.rows[0].props.height_rule = HeightRule::Exact;
        t.rows[0].cells[0].blocks = (0..3000).map(|_| para_block(Paragraph::with_text("x", Default::default()))).collect();
        for row in t.rows.iter_mut().skip(1) {
            row.props.height = Some(600.0);
            row.props.height_rule = HeightRule::Exact;
        }
        t
    };
    let mut d = Document::from_text("");
    d.insert_block(StoryRef::Body, &Path::top(1), Block::Table(table())).unwrap();
    d.insert_block(StoryRef::Body, &Path::top(2), Block::Table(table())).unwrap();
    d.insert_block(StoryRef::Body, &Path::top(3), Block::Table(table())).unwrap();
    let l = lay(&d);
    let items: usize = l.pages.iter().map(|p| p.items.len()).sum();
    assert!(items <= MAX_HEADER_ITEMS + 3 * 3000 + 50 * l.pages.len(), "{items} items placed");
}

/// Which pictures wrap by their outline must not depend on what the cache already holds: a
/// picture's outline kept from an earlier layout is charged to the budget like a decoded one.
#[test]
fn cold_and_warm_caches_give_the_same_outlines() {
    let (a, b) = (Arc::new(disc_png(64)), Arc::new(disc_png(64)));
    let key = |bytes: &Arc<Vec<u8>>, n: &str| (n.to_string(), Arc::as_ptr(bytes) as usize, bytes.len(), [0; 4]);
    // Room for one of the two pictures.
    let pass = |outlines: &mut Outlines| {
        let mut alphas = contour::Alphas::default();
        alphas.decoded = contour::MAX_DECODED_PIXELS - 64 * 64;
        let got = [(&a, "a"), (&b, "b")].map(|(p, n)| picture_outline(outlines, &mut alphas, key(p, n), p, [0.0; 4]).is_some());
        (got, alphas.decoded)
    };
    let mut roomy = contour::Alphas::default();
    let mut warm = Outlines::new();
    for (p, n) in [(&a, "a"), (&b, "b")] {
        assert!(picture_outline(&mut warm, &mut roomy, key(p, n), p, [0.0; 4]).is_some());
    }
    assert_eq!(warm.len(), 2, "both outlines are kept");
    let (cold, cold_spent) = pass(&mut Outlines::new());
    assert_eq!(cold, [true, false], "the first picture fits, the second wraps as its rectangle");
    let (warmed, warm_spent) = pass(&mut warm);
    assert_eq!(warmed, cold, "the same pictures get outlines with the cache warm");
    assert_eq!(warm_spent, cold_spent);
    // And again: a layout after a layout.
    assert_eq!(pass(&mut warm).0, cold);
}

/// A PNG whose header says `side` × `side` RGBA and whose body is missing: it has transparency
/// to look at, costs its pixels, and then fails to decode.
fn truncated_png(side: u32) -> Vec<u8> {
    fn crc(data: &[u8]) -> u32 {
        let mut c = !0u32;
        for b in data {
            c ^= u32::from(*b);
            for _ in 0..8 {
                c = if c & 1 != 0 { 0xEDB8_8320 ^ (c >> 1) } else { c >> 1 };
            }
        }
        !c
    }
    let mut ihdr = b"IHDR".to_vec();
    ihdr.extend(side.to_be_bytes());
    ihdr.extend(side.to_be_bytes());
    ihdr.extend([8, 6, 0, 0, 0]);
    let mut png = vec![0x89, b'P', b'N', b'G', 0x0D, 0x0A, 0x1A, 0x0A, 0, 0, 0, 13];
    png.extend(&ihdr);
    png.extend(crc(&ihdr).to_be_bytes());
    // An image data chunk of junk: the header is read, the pixels aren't there.
    let mut idat = b"IDAT".to_vec();
    idat.extend([0x78, 0x9c, 1, 2, 3, 4]);
    png.extend(6u32.to_be_bytes());
    png.extend(&idat);
    png.extend(crc(&idat).to_be_bytes());
    png
}

#[test]
fn a_truncated_picture_costs_the_same_cold_and_warm() {
    // Its header promises transparency, so a layout spends its pixels before the body fails to
    // decode; a layout finding its (empty) outline kept spends them too, or pictures after it
    // would get outlines only with the cache warm.
    let (big, disc) = (Arc::new(truncated_png(8000)), Arc::new(disc_png(64)));
    let key = |bytes: &Arc<Vec<u8>>, n: &str| (n.to_string(), Arc::as_ptr(bytes) as usize, bytes.len(), [0; 4]);
    let pass = |outlines: &mut Outlines| {
        let mut alphas = contour::Alphas::default();
        alphas.decoded = contour::MAX_DECODED_PIXELS - 8000 * 8000;
        let got = [(&big, "big"), (&disc, "disc")].map(|(p, n)| picture_outline(outlines, &mut alphas, key(p, n), p, [0.0; 4]).is_some());
        (got, alphas.decoded)
    };
    let mut warm = Outlines::new();
    let (cold, spent) = pass(&mut warm);
    assert_eq!(spent, contour::MAX_DECODED_PIXELS, "the truncated picture spent its pixels");
    assert_eq!(cold, [false, false], "no budget is left for the disc");
    assert_eq!(warm.get(&key(&big, "big")).map(|e| e.2), Some(8000 * 8000), "the entry holds the cost");
    // Also with a roomy first layout filling the cache, then a tight one.
    let mut roomy_cache = Outlines::new();
    let mut roomy = contour::Alphas::default();
    for (p, n) in [(&big, "big"), (&disc, "disc")] {
        let _ = picture_outline(&mut roomy_cache, &mut roomy, key(p, n), p, [0.0; 4]);
    }
    assert_eq!(pass(&mut roomy_cache), (cold, spent), "warm matches cold");
}

#[test]
fn a_header_row_holding_a_canvas_repeats_within_the_budget() {
    use wordcraft_doc::para::{Anchor, CanvasStyle, Float, GroupChild, ShapeKind, Wrap};
    // A canvas of 800 members in an exact-height header row, over two thousand pages: each page
    // would clone all 800 members.
    let member = InlineObject::Shape {
        kind: ShapeKind::Rectangle,
        w: 4.0,
        h: 4.0,
        fill: None,
        stroke: None,
        stroke_width: 0.0,
        float: Float::default(),
        story: None,
        effects: Default::default(),
        freeform: None,
        extra: Default::default(),
    };
    let canvas = InlineObject::Group {
        w: 40.0,
        h: 40.0,
        float: Float { wrap: Wrap::InFrontOfText, h_rel: Anchor::Column, v_rel: Anchor::Paragraph, x: 5.0, y: 5.0, ..Default::default() },
        ch_w: 40.0,
        ch_h: 40.0,
        children: (0..800).map(|_| GroupChild { x: 1.0, y: 1.0, obj: member.clone() }).collect(),
        canvas: Some(CanvasStyle { fill: None, stroke: None, stroke_width: 0.0 }),
    };
    let mut t = Table::new(2001, 1, 468.0);
    t.rows[0].props.header = true;
    t.rows[0].props.height = Some(60.0);
    t.rows[0].props.height_rule = HeightRule::Exact;
    let mut p = Paragraph::with_text("", Default::default());
    p.insert_object(0, canvas, &Default::default()).unwrap();
    t.rows[0].cells[0].blocks = vec![para_block(p)];
    for row in t.rows.iter_mut().skip(1) {
        row.props.height = Some(600.0);
        row.props.height_rule = HeightRule::Exact;
    }
    fn count(it: &Placed) -> usize {
        match it {
            Placed::Clip { items, .. } => items.iter().map(count).fold(1, usize::saturating_add),
            _ => 1,
        }
    }
    let mut d = Document::from_text("");
    d.insert_block(StoryRef::Body, &Path::top(1), Block::Table(t)).unwrap();
    let l = lay(&d);
    assert!(l.pages.len() >= 1000, "{} pages", l.pages.len());
    let items: usize = l.pages.iter().flat_map(|p| &p.items).map(count).sum();
    assert!(items <= MAX_HEADER_ITEMS + 2000 + 50 * l.pages.len(), "{items} items placed");
    assert!(items > 100_000, "the header still repeats on early pages: {items}");
}

/// A table with a repeating header row in a two-column section ended by a continuous break, so
/// its columns are balanced: laid out once, then again from a snapshot for each balancing try.
fn balanced_header_table(rows: usize) -> Document {
    use wordcraft_doc::section::{SectionProps, SectionStart};
    let mut d = Document::from_text("Before\nEnd of the section\nAfter the break");
    let mut s = SectionProps::default();
    s.columns.count = 2;
    d.para_mut(StoryRef::Body, &Path::top(1)).unwrap().section = Some(Box::new(s));
    d.last_section.start = SectionStart::Continuous;
    let mut t = Table::new(rows, 1, 200.0);
    t.rows[0].props.header = true;
    d.insert_block(StoryRef::Body, &Path::top(1), Block::Table(t)).unwrap();
    d
}

/// Header rows placed (each repeat of the one-column header row is one cell of row 0).
fn header_cells(l: &DocLayout) -> usize {
    l.pages.iter().flat_map(|p| &p.items).filter(|i| matches!(i, Placed::Cell { row: 0, .. })).count()
}

fn with_header_cap<T>(cap: usize, f: impl FnOnce() -> T) -> T {
    headers::HEADER_ITEMS_CAP.with(|c| c.set(cap));
    let out = f();
    headers::HEADER_ITEMS_CAP.with(|c| c.set(MAX_HEADER_ITEMS));
    out
}

#[test]
fn balancing_columns_gives_back_the_header_repeats_it_throws_away() {
    // The table runs over both columns of a page and onto a second one.
    let d = balanced_header_table(120);
    let full = lay(&d);
    let shown = header_cells(&full);
    assert!(shown >= 3, "the header repeats in each later column: {shown} header rows");
    // What one repeat costs: the smallest cap at which a plain two-page table repeats its header.
    let mut plain = Table::new(80, 1, 200.0);
    plain.rows[0].props.header = true;
    let mut p = Document::from_text("");
    p.insert_block(StoryRef::Body, &Path::top(1), Block::Table(plain)).unwrap();
    let cost = (1..=200).find(|cap| with_header_cap(*cap, || header_cells(&lay(&p))) >= 2).expect("a header repeat costs a few items");
    // A budget holding exactly the repeats shown is enough: the balancing tries thrown away don't
    // spend it.
    let capped = with_header_cap((shown - 1) * cost, || lay(&d));
    assert_eq!(header_cells(&capped), shown, "the final layout repeats the header as often");
}