Merge pull request #4392 from benandez/fix/3866-followup

#3866 follow-up: PDF export draws items with authors and cell clips built once per page; endnote selection linear

crates/layout/src/display.rs

@@ -533,12 +533,42 @@ pub fn page_display(doc: &Document, page: &Page, opts: &DisplayOptions) -> Vec<D
     let mut out = Vec::new();
     let (ha, ba) = dimming(opts);
     let authors = Authors::new(doc);
-    stories_display(doc, &[&page.header, &page.footer], opts, &authors, ha, &mut out);
-    stories_display(doc, &[&page.items], opts, &authors, ba, &mut out);
-    body_change_bars(doc, page, opts, ba, &mut out);
+    stories_display(doc, &[&page.header[..], &page.footer[..]], None, opts, &authors, ha, &mut out);
+    stories_display(doc, &[&page.items[..]], None, opts, &authors, ba, &mut out);
+    body_change_bars(doc, page, &page.items, opts, ba, &mut out);
     out
 }
 
+/// A page's draw items one placed item at a time, for a caller that draws and tags each item on
+/// its own (the PDF export). What every item shares, the revision authors' colours and the cells
+/// cut off at their edge, is worked out once for the page, not once for every item as calling
+/// [`page_display`] with each would (#3866).
+pub struct ItemDisplay<'a> {
+    doc: &'a Document,
+    page: &'a Page,
+    authors: Authors<'a>,
+    clips: Clips,
+}
+
+impl<'a> ItemDisplay<'a> {
+    pub fn new(doc: &'a Document, page: &'a Page) -> Self {
+        let cells: Vec<Placed> =
+            page.header.iter().chain(&page.footer).chain(&page.items).filter(|c| matches!(c, Placed::Cell { clip: true, .. })).cloned().collect();
+        ItemDisplay { doc, page, authors: Authors::new(doc), clips: clipped_cells(&cells) }
+    }
+
+    /// The draw items of `it` alone, as [`page_display`] gives them for a page holding just it
+    /// (and, for a line in a clipped cell, the cell's clip).
+    pub fn draws(&self, it: &Placed, opts: &DisplayOptions) -> Vec<Draw> {
+        let mut out = Vec::new();
+        let items = std::slice::from_ref(it);
+        let (_, ba) = dimming(opts);
+        stories_display(self.doc, &[items], Some(&self.clips), opts, &self.authors, ba, &mut out);
+        body_change_bars(self.doc, self.page, items, opts, ba, &mut out);
+        out
+    }
+}
+
 /// A page's draw items as two layers, its headers and footers then its body, each at full
 /// strength with the opacity to draw it at. A dimmed layer is faded as one picture, as Word dims
 /// it: where its lines or fills overlap (a table's borders meeting) they don't darken each other.
@@ -546,9 +576,9 @@ pub fn page_layers(doc: &Document, page: &Page, opts: &DisplayOptions) -> [(f32,
     let (ha, ba) = dimming(opts);
     let (mut hf, mut body) = (Vec::new(), Vec::new());
     let authors = Authors::new(doc);
-    stories_display(doc, &[&page.header, &page.footer], opts, &authors, 1.0, &mut hf);
-    stories_display(doc, &[&page.items], opts, &authors, 1.0, &mut body);
-    body_change_bars(doc, page, opts, 1.0, &mut body);
+    stories_display(doc, &[&page.header[..], &page.footer[..]], None, opts, &authors, 1.0, &mut hf);
+    stories_display(doc, &[&page.items[..]], None, opts, &authors, 1.0, &mut body);
+    body_change_bars(doc, page, &page.items, opts, 1.0, &mut body);
     [(ha, hf), (ba, body)]
 }
 
@@ -558,18 +588,34 @@ fn dimming(opts: &DisplayOptions) -> (f32, f32) {
     (a(opts.dim_header), a(opts.dim_body))
 }
 
-fn body_change_bars(doc: &Document, page: &Page, opts: &DisplayOptions, alpha: f32, out: &mut Vec<Draw>) {
+fn body_change_bars(doc: &Document, page: &Page, items: &[Placed], opts: &DisplayOptions, alpha: f32, out: &mut Vec<Draw>) {
     if opts.markup && (opts.revisions.insertions_deletions || opts.revisions.formatting) && opts.revisions.changed_lines != ChangeBar::None {
-        change_bars(doc, page, &opts.revisions, alpha, out);
+        change_bars(doc, page, items, &opts.revisions, alpha, out);
     }
 }
 
 /// Draw items for the placed items of `stories`, faded by `a`.
-fn stories_display(doc: &Document, stories: &[&Vec<Placed>], opts: &DisplayOptions, authors: &Authors, a: f32, out: &mut Vec<Draw>) {
+/// `shared` gives the page's clipped cells when the caller worked them out already.
+fn stories_display(
+    doc: &Document,
+    stories: &[&[Placed]],
+    shared: Option<&Clips>,
+    opts: &DisplayOptions,
+    authors: &Authors,
+    a: f32,
+    out: &mut Vec<Draw>,
+) {
     let hidden = opts.hide_object.as_ref().map(|p| Hidden::new(doc, p));
     for items in stories {
         let warps = warped_boxes(doc, items);
-        let clips = clipped_cells(items);
+        let own;
+        let clips = match shared {
+            Some(c) => c,
+            None => {
+                own = clipped_cells(items);
+                &own
+            }
+        };
         let mut done: Vec<u32> = Vec::new();
         for it in items.iter() {
             // The object being dragged is drawn by its preview instead: leave it out here.
@@ -577,7 +623,7 @@ fn stories_display(doc: &Document, stories: &[&Vec<Placed>], opts: &DisplayOptio
                 continue;
             }
             if let Placed::Lines { story, path, .. } = it
-                && let Some(rect) = cell_clip(&clips, *story, &path.0)
+                && let Some(rect) = cell_clip(clips, *story, &path.0)
             {
                 let mut inner = Vec::new();
                 item(doc, it, opts, authors, a, &mut inner);
@@ -726,7 +772,7 @@ pub const CHANGE_BAR: Rgb = Rgb(0x50, 0x50, 0x50);
 
 /// Bars in the margin beside body lines with tracked insertions or deletions, or (when shown)
 /// tracked formatting changes of their text, paragraph or paragraph mark.
-fn change_bars(doc: &Document, page: &Page, m: &MarkupOptions, alpha: f32, out: &mut Vec<Draw>) {
+fn change_bars(doc: &Document, page: &Page, items: &[Placed], m: &MarkupOptions, alpha: f32, out: &mut Vec<Draw>) {
     // Outside: the left margin, or the outer one of a right-hand page with mirrored margins.
     let right = match m.changed_lines {
         ChangeBar::Right => true,
@@ -735,7 +781,7 @@ fn change_bars(doc: &Document, page: &Page, m: &MarkupOptions, alpha: f32, out:
     };
     let bx = if right { page.body.right() + 9.0 } else { page.body.x - 9.0 };
     let color = m.changed_lines_color.unwrap_or(CHANGE_BAR);
-    for it in &page.items {
+    for it in items {
         let Placed::Lines { story, path, para: pl, l0, l1, y, turn, .. } = it else { continue };
         if turn.is_turned() {
             continue;
@@ -2142,3 +2188,53 @@ fn upright_east_asian(items: Vec<Draw>) -> Vec<Draw> {
     }
     out
 }
+
+#[cfg(test)]
+mod tests_clips {
+    use super::*;
+    use wordcraft_doc::Path as DocPath;
+
+    /// A cell whose area is told apart by `x`.
+    fn cell(story: StoryRef, table: Vec<u32>, row: usize, cell: usize, clip: bool, x: f32) -> Placed {
+        Placed::Cell { rect: Rect::new(x, 0.0, 1.0, 1.0), covered: false, table: DocPath(table), row, cell, story, clip }
+    }
+
+    /// Which cell (by its `x`) clips a line at `path` of `story`.
+    fn found(clips: &Clips, story: StoryRef, path: &[u32]) -> Option<f32> {
+        cell_clip(clips, story, path).map(|r| r.x)
+    }
+
+    /// A line in a cell cut off at its edge is drawn with that cell's clip, found by path in an
+    /// index built once per page: every line used to look through every clipped cell on the page,
+    /// so a page of exact-height rows cost lines x cells.
+    #[test]
+    fn a_line_finds_its_clipped_cell_by_path() {
+        let mut page = Page {
+            items: vec![cell(StoryRef::Body, vec![0], 0, 1, false, 1.0), cell(StoryRef::Body, vec![2], 1, 0, true, 2.0)],
+            ..Default::default()
+        };
+        // A nested clipped cell inside the second one; the outer one comes first in the page.
+        page.items.push(cell(StoryRef::Body, vec![2, 1, 0, 3], 0, 0, true, 3.0));
+        page.footer.push(cell(StoryRef::Part(7), vec![0], 0, 0, true, 4.0));
+        // The page's cells in header, footer, items order, as the PDF export and layout see them.
+        let all: Vec<Placed> = page.header.iter().chain(&page.footer).chain(&page.items).cloned().collect();
+        let clips = clipped_cells(&all);
+        assert_eq!(found(&clips, StoryRef::Body, &[2, 1, 0, 0]), Some(2.0));
+        assert_eq!(found(&clips, StoryRef::Body, &[2, 1, 0, 3, 0, 0, 1]), Some(2.0), "the first cell in page order wins, as in layout");
+        assert_eq!(found(&clips, StoryRef::Body, &[0, 0, 1, 0]), None, "that cell isn't clipped");
+        assert_eq!(found(&clips, StoryRef::Body, &[2, 0, 0, 0]), None, "another row");
+        assert_eq!(found(&clips, StoryRef::Part(7), &[0, 0, 0, 2]), Some(4.0));
+        assert_eq!(found(&clips, StoryRef::Body, &[0, 0, 0, 2]), None, "another story");
+    }
+
+    /// Thousands of clipped cells and as many lines: a lookup each, not a pass over the cells each.
+    #[test]
+    fn looking_up_many_clipped_cells_takes_linear_time() {
+        let make = |n: usize| (0..n).map(|r| cell(StoryRef::Body, vec![0], r, 0, true, r as f32)).collect::<Vec<_>>();
+        crate::tests_linear::assert_linear_steps("clip lookups", 1000, make, |cells| {
+            let clips = clipped_cells(cells);
+            let hits = (0..cells.len() as u32).filter(|r| cell_clip(&clips, StoryRef::Body, &[0, *r, 0, 0]).is_some()).count();
+            assert_eq!(hits, cells.len());
+        });
+    }
+}

crates/layout/src/hit.rs

@@ -147,17 +147,41 @@ fn text_at(p: &Page, index: usize, x: f32, y: f32) -> Option<StoryRef> {
 struct PartPages<'a> {
     story: StoryRef,
     pages: HashMap<usize, HashMap<&'a Path, Vec<&'a Placed>>>,
+    /// The first page that shows each paragraph, made the first time one is asked for, in one
+    /// walk of the pages (not one walk of them for every paragraph).
+    first: Option<HashMap<&'a Path, usize>>,
 }
 
 impl<'a> PartPages<'a> {
     fn new(story: StoryRef) -> Self {
-        PartPages { story, pages: HashMap::new() }
+        PartPages { story, pages: HashMap::new(), first: None }
+    }
+
+    /// The first page of `lay` that shows a piece of the paragraph at `path`.
+    fn first_page(&mut self, lay: &'a DocLayout, path: &Path) -> Option<usize> {
+        let story = self.story;
+        let first = self.first.get_or_insert_with(|| {
+            let mut first: HashMap<&'a Path, usize> = HashMap::new();
+            for (pi, p) in lay.pages.iter().enumerate() {
+                crate::work::steps(1);
+                for it in items_of(p, story) {
+                    if let Placed::Lines { story: s, path, .. } = it
+                        && *s == story
+                    {
+                        first.entry(path).or_insert(pi);
+                    }
+                }
+            }
+            first
+        });
+        first.get(path).copied()
     }
 
     /// The pieces of the paragraph at `path` on page `pi` of `lay`, as [`DocLayout::pieces_on`]
     /// gives them.
     fn on(&mut self, lay: &'a DocLayout, pi: usize, path: &Path) -> Vec<(usize, &'a Placed)> {
         let Some(p) = lay.pages.get(pi) else { return Vec::new() };
+        crate::work::steps(1);
         let story = self.story;
         let index = self.pages.entry(pi).or_insert_with(|| {
             let mut index: HashMap<&'a Path, Vec<&'a Placed>> = HashMap::new();
@@ -460,21 +484,24 @@ impl DocLayout {
                 .map(|v| v.iter().filter_map(|(pi, ii)| self.pages.get(*pi).and_then(|p| p.items.get(*ii)).map(|it| (*pi, it))).collect())
                 .unwrap_or_default();
         }
-        self.part_pieces(page_hint, &mut |pi| self.pieces_on(pi, story, path))
+        let mut first = || (0..self.pages.len()).find(|pi| !self.pieces_on(*pi, story, path).is_empty());
+        self.part_pieces(page_hint, &mut first, &mut |pi| self.pieces_on(pi, story, path))
     }
 
     /// Pieces of a paragraph of a story part (see [`Self::pieces`]), `on` giving those on a page.
-    fn part_pieces<'a>(&'a self, page_hint: usize, on: &mut dyn FnMut(usize) -> Vec<(usize, &'a Placed)>) -> Vec<(usize, &'a Placed)> {
+    fn part_pieces<'a>(
+        &'a self,
+        page_hint: usize,
+        first: &mut dyn FnMut() -> Option<usize>,
+        on: &mut dyn FnMut(usize) -> Vec<(usize, &'a Placed)>,
+    ) -> Vec<(usize, &'a Placed)> {
         // Headers/footers repeat: prefer the hinted page, else the first that shows the part.
-        let mut order: Vec<usize> = (0..self.pages.len()).collect();
-        if page_hint < order.len() {
-            order.retain(|p| *p != page_hint);
-            order.insert(0, page_hint);
-        }
-        for pi in order {
-            let mut found = on(pi);
+        let hinted = if page_hint < self.pages.len() { on(page_hint) } else { Vec::new() };
+        let start = if hinted.is_empty() { first() } else { Some(page_hint) };
+        if let Some(pi) = start {
+            let mut found = if hinted.is_empty() { on(pi) } else { hinted };
             if found.is_empty() {
-                continue;
+                return found;
             }
             // A note continued over pages has the rest of the paragraph on the pages before or
             // after (a repeated header shows all of it on every page: one page is enough).
@@ -517,7 +544,9 @@ impl DocLayout {
         if pages.story == StoryRef::Body {
             return self.pieces(StoryRef::Body, path, page_hint);
         }
-        self.part_pieces(page_hint, &mut |pi| pages.on(self, pi, path))
+        // The first-page index is made only when the hinted page doesn't show the paragraph.
+        let pages = std::cell::RefCell::new(pages);
+        self.part_pieces(page_hint, &mut || pages.borrow_mut().first_page(self, path), &mut |pi| pages.borrow_mut().on(self, pi, path))
     }
 
     /// Pieces of a paragraph of story part `story` on page `pi`.

crates/layout/src/table.rs

@@ -1129,7 +1129,9 @@ fn region_text(st: &TableStyleProps, region: Region) -> CellText {
 /// with their own. `None` when every cell is empty.
 fn column_content(ctx: &mut Ctx, t: &Table, style: Option<&TableStyleProps>, depth: usize) -> Option<Vec<(f32, f32)>> {
     let margins_def = default_margins(t, style);
-    let mut cols = vec![(0.0f32, 0.0f32); grid_cols(t).max(1)];
+    // The grid's width once: counting it walks every row.
+    let ncols = grid_cols(t);
+    let mut cols = vec![(0.0f32, 0.0f32); ncols.max(1)];
     let mut spanning = Vec::new();
     let mut any = false;
     for (ri, row) in t.rows.iter().enumerate() {
@@ -1151,8 +1153,6 @@ fn column_content(ctx: &mut Ctx, t: &Table, style: Option<&TableStyleProps>, dep
         }
         spanning.extend(row_gaps(row, g).map(|(g, span, w)| (g, span, (w, w))));
     }
-    // The grid's width once: counting it walks every row, and there can be a spanning cell in each.
-    let ncols = grid_cols(t);
     for (g, span, need) in spanning {
         let Some(cs) = cols.get_mut(g..g.saturating_add(span).min(ncols)) else { continue };
         let n = cs.len().max(1) as f32;

crates/layout/src/tests_linear.rs

@@ -204,6 +204,35 @@ fn selecting_a_long_header_takes_linear_time() {
     assert_linear_steps("header selection", 300, laid, |(d, l, (a, b))| drop(std::hint::black_box(l.selection_rects(d, a, b, 0))));
 }
 
+/// An endnote of `n` paragraphs, a few lines each, continued over many pages.
+fn long_endnote(n: usize) -> (Document, u32) {
+    let mut d = Document::from_text("Body");
+    // One huge letter to a paragraph, one line high enough for a page, so the pages are as many as
+    // the paragraphs and each paragraph costs next to nothing.
+    let huge = CharProps { size: Some(400.0), ..Default::default() };
+    let paras = (0..n).map(|_| wordcraft_doc::para_block(Paragraph::with_text("n", huge.clone()))).collect();
+    let id = d.add_part(wordcraft_doc::PartKind::Endnote, paras);
+    let r = InlineObject::NoteRef { kind: wordcraft_doc::para::NoteKind::Endnote, id, custom: String::new() };
+    d.insert_object(&Pos::body(0, 4), r, &Default::default()).unwrap();
+    (d, id)
+}
+
+/// #3866: selecting across an endnote over many pages probed the pages from the first for each
+/// paragraph (paragraphs x pages).
+#[test]
+fn selecting_a_long_endnote_takes_linear_time() {
+    let laid = |n: usize| {
+        let (d, id) = long_endnote(n);
+        let l = lay(&d, &LayoutOptions::default());
+        let ends = (Pos::new(StoryRef::Part(id), Path::top(0), 0), Pos::new(StoryRef::Part(id), Path::top(n - 1), 2));
+        (d, l, ends)
+    };
+    let (d, l, (a, b)) = laid(SCALE * 20);
+    assert!(l.pages.len() >= SCALE * 20 / 2, "the endnote runs over many pages: {}", l.pages.len());
+    assert!(l.selection_rects(&d, &a, &b, 0).len() >= SCALE * 20, "a rectangle per paragraph");
+    assert_linear_steps("endnote selection", 20, laid, |(d, l, (a, b))| drop(std::hint::black_box(l.selection_rects(d, a, b, 0))));
+}
+
 /// A table of `n` rows of 60 cells, each row exactly half a point high, so every cell clips its
 /// (empty) paragraph and the whole table fits on the first page.
 fn clipped_table(n: usize) -> Document {
@@ -297,3 +326,169 @@ fn balloons_for_many_authors_lay_out_in_linear_time() {
     let opts = LayoutOptions { comment_balloons: true, ..Default::default() };
     assert_layout_linear("comment balloons", 120, doc, &opts);
 }
+
+/// `n` one-word paragraphs, each inserted by its own author, small enough for one page.
+fn tracked_paras(n: usize) -> Document {
+    let mut d = Document::from_text("x");
+    d.body = (0..n)
+        .map(|i| {
+            let run = Run { len: 1, props: CharProps { ins: u32::try_from(i).ok(), size: Some(1.0), ..Default::default() } };
+            let mut p = Paragraph { runs: vec![run], ..Paragraph::with_text("w", CharProps::default()) };
+            p.mark.size = Some(1.0);
+            p.props.space_before = Some(0.0);
+            p.props.space_after = Some(0.0);
+            wordcraft_doc::para_block(p)
+        })
+        .collect();
+    d.revisions = (0..n).map(|i| wordcraft_doc::Revision::new(wordcraft_doc::RevisionKind::Insert, format!("Author {i}"), "")).collect();
+    d
+}
+
+/// Draws every item of the first page on its own, as the PDF export does.
+fn draw_items((d, l): &(Document, DocLayout), opts: &display::DisplayOptions) {
+    let Some(p) = l.pages.first() else { return };
+    let shown = display::ItemDisplay::new(d, p);
+    for it in p.header.iter().chain(&p.footer).chain(&p.items) {
+        std::hint::black_box(shown.draws(it, opts));
+    }
+}
+
+/// #3866: the PDF export drew each item with a `page_display` of its own, which ranked the revision
+/// authors again for every item with a tracked change (lines x revisions).
+#[test]
+fn drawing_items_one_by_one_ranks_the_authors_once() {
+    let laid = |n: usize| {
+        let d = tracked_paras(n);
+        let l = lay(&d, &LayoutOptions::default());
+        (d, l)
+    };
+    assert_eq!(laid(SCALE * 40).1.pages.len(), 1);
+    let opts = display::DisplayOptions { markup: true, ..Default::default() };
+    assert_linear_steps("items drawn one by one", 40, laid, |dl| draw_items(dl, &opts));
+}
+
+/// #3866: the same for the clipped cells, which each item's `page_display` collected again
+/// (lines x clipped cells).
+#[test]
+fn drawing_items_one_by_one_collects_the_clipped_cells_once() {
+    let laid = |n: usize| {
+        let d = clipped_table(n);
+        let l = lay(&d, &LayoutOptions::default());
+        (d, l)
+    };
+    let opts = display::DisplayOptions::default();
+    assert_linear_steps("clipped cells, items one by one", 16, laid, |dl| draw_items(dl, &opts));
+}
+
+/// #3866: a comment's balloon is in its author's colour, authors numbered in order of appearance.
+#[test]
+fn balloons_are_in_their_authors_colours() {
+    let mut d = Document::from_text("one two three");
+    for (i, a) in ["Ana", "Ben", "Ana"].into_iter().enumerate() {
+        let part = d.add_part(wordcraft_doc::PartKind::Comment, vec![wordcraft_doc::para_block(Paragraph::with_text("c", CharProps::default()))]);
+        let id = u32::try_from(i).unwrap();
+        d.comments.insert(id, wordcraft_doc::Comment { author: a.into(), part, ..Default::default() });
+        let p = CharProps::default();
+        d.insert_object(&Pos::body(0, 0), InlineObject::CommentEnd { id }, &p).unwrap();
+        d.insert_object(&Pos::body(0, 0), InlineObject::CommentStart { id }, &p).unwrap();
+    }
+    let l = lay(&d, &LayoutOptions { comment_balloons: true, ..Default::default() });
+    // Each card's stripe is a 3 pt wide fill in the author's colour; the cards run down the page.
+    let mut stripes: Vec<_> = l.pages[0]
+        .items
+        .iter()
+        .filter_map(|it| match it {
+            Placed::Fill { rect, color } if rect.w == 3.0 => Some((rect.y, *color)),
+            _ => None,
+        })
+        .collect();
+    stripes.sort_by(|a, b| a.0.total_cmp(&b.0));
+    let (ana, ben) = (display::revision_color(0), display::revision_color(1));
+    assert_ne!(ana, ben);
+    assert_eq!(stripes.iter().map(|s| s.1).collect::<Vec<_>>(), [ana, ben, ana]);
+}
+
+/// A page with tracked changes by several authors in its body and header, and exact-height
+/// tables, one nested in a cell of another, whose cells clip their lines.
+fn mixed_page() -> (Document, DocLayout) {
+    let mut d = tracked_paras(6);
+    let mut hp = Paragraph::with_text("head", CharProps::default());
+    hp.runs = vec![Run { len: 4, props: CharProps { ins: Some(2), ..Default::default() } }];
+    let id = d.add_part(wordcraft_doc::PartKind::Header, vec![wordcraft_doc::para_block(hp)]);
+    d.last_section.headers.default = Some(id);
+    let exact = |rows, cols| {
+        let mut t = Table::new(rows, cols, 200.0);
+        for row in &mut t.rows {
+            row.props.height = Some(0.5);
+            row.props.height_rule = HeightRule::Exact;
+        }
+        t
+    };
+    // A cell with text in it holds a nested table.
+    let mut outer = exact(2, 2);
+    outer.rows[0].cells[0].blocks.push(std::sync::Arc::new(Block::Table(exact(2, 2))));
+    d.insert_block(StoryRef::Body, &Path::top(1), Block::Table(outer)).unwrap();
+    d.insert_block(StoryRef::Body, &Path::top(0), Block::Table(exact(2, 3))).unwrap();
+    let l = lay(&d, &LayoutOptions::default());
+    (d, l)
+}
+
+/// What drawing `it` on a page of just it (and every clipped cell, for a line) gave before the
+/// page's authors and clipped cells were shared: a `page_display` of its own.
+fn drawn_alone(d: &Document, page: &Page, it: &Placed, opts: &display::DisplayOptions) -> Vec<display::Draw> {
+    let mut items = vec![it.clone()];
+    if matches!(it, Placed::Lines { .. }) {
+        let cells = page.header.iter().chain(&page.footer).chain(&page.items).filter(|c| matches!(c, Placed::Cell { clip: true, .. }));
+        items.extend(cells.cloned());
+    }
+    let one = Page { w: page.w, h: page.h, section: page.section, number: page.number, items, body: page.body, ..Default::default() };
+    display::page_display(d, &one, opts)
+}
+
+/// #3866: drawing the items of a page one by one with the page's shared authors and clipped
+/// cells gives what a `page_display` of each alone gave.
+#[test]
+fn drawing_items_one_by_one_matches_a_page_display_of_each() {
+    let (d, l) = mixed_page();
+    let page = &l.pages[0];
+    let clipped = page.items.iter().filter(|c| matches!(c, Placed::Cell { clip: true, .. })).count();
+    assert!(clipped >= 8, "clipped cells, nested ones among them: {clipped}");
+    assert!(!page.header.is_empty(), "a header on the page");
+    for markup in [true, false] {
+        let opts = display::DisplayOptions { markup, ..Default::default() };
+        let shown = display::ItemDisplay::new(&d, page);
+        let (mut clips, mut coloured) = (0, 0);
+        for it in page.header.iter().chain(&page.footer).chain(&page.items) {
+            let (got, want) = (shown.draws(it, &opts), drawn_alone(&d, page, it, &opts));
+            assert_eq!(format!("{got:?}"), format!("{want:?}"), "markup {markup}: {it:?}");
+            clips += got.iter().filter(|x| matches!(x, display::Draw::Clip { .. })).count();
+            coloured += got.iter().filter(|x| matches!(x, display::Draw::Glyphs { color, .. } if *color != Rgb(0, 0, 0))).count();
+        }
+        assert!(clips > 0, "some lines are clipped");
+        assert!(!markup || coloured > 0, "some tracked text is in an author's colour");
+    }
+}
+
+/// #3866: a header paragraph on the hinted page is found there, without a walk of every page of a
+/// long document to find the first page that shows it.
+#[test]
+fn selecting_a_header_on_the_hinted_page_does_not_walk_every_page() {
+    let laid = |n: usize| {
+        let mut d = Document::from_text("n");
+        let huge = CharProps { size: Some(400.0), ..Default::default() };
+        d.body = (0..n).map(|_| wordcraft_doc::para_block(Paragraph::with_text("n", huge.clone()))).collect();
+        let id = d.add_part(wordcraft_doc::PartKind::Header, vec![wordcraft_doc::para_block(Paragraph::with_text("head", CharProps::default()))]);
+        d.last_section.headers.default = Some(id);
+        let l = lay(&d, &LayoutOptions::default());
+        let ends = (Pos::new(StoryRef::Part(id), Path::top(0), 0), Pos::new(StoryRef::Part(id), Path::top(0), 2));
+        (d, l, ends)
+    };
+    let steps = |n: usize| {
+        let (d, l, (a, b)) = laid(n);
+        assert!(l.pages.len() >= n, "a page to each paragraph: {}", l.pages.len());
+        work::count(|| drop(std::hint::black_box(l.selection_rects(&d, &a, &b, 0))))
+    };
+    let (small, big) = (steps(20), steps(160));
+    eprintln!("hinted header: {small} steps for 20 pages, {big} for 160");
+    assert!(small > 0 && big <= small + 8, "the pages aren't walked: {small} → {big}");
+}

crates/pdf/src/lib.rs

@@ -47,7 +47,7 @@ use wordcraft_doc::{Document, Path as DocPath, Rgb, StoryRef};
 use wordcraft_fonts::FaceRef;
 use wordcraft_geom::Rect;
 use wordcraft_layout::display::Paint;
-use wordcraft_layout::display::{DisplayOptions, Draw, Stroke as LineStyle, page_display};
+use wordcraft_layout::display::{DisplayOptions, Draw, ItemDisplay, Stroke as LineStyle};
 use wordcraft_layout::para::{ClKind, LineEnd};
 use wordcraft_layout::{DocLayout, LayoutCache, LayoutOptions, NumeralMode, Page, Placed, layout};
 use wordcraft_metafile::{Picture, PlacedItem};
@@ -920,9 +920,10 @@ impl Exporter<'_> {
             placeholders: false,
             ..Default::default()
         };
-        let clips = clipped_cells(page);
+        // What the items share (the authors' colours, the clipped cells) is worked out once per page.
+        let shown = ItemDisplay::new(self.doc, page);
         for it in page.header.iter().chain(page.footer.iter()) {
-            let draws = self.draws(page, it, &clips, &dopts);
+            let draws = shown.draws(it, &dopts);
             self.tagged(s, Role::Artifact(ArtifactType::Other), None, |me, s| {
                 for d in &draws {
                     me.draw(s, d);
@@ -930,7 +931,7 @@ impl Exporter<'_> {
             });
         }
         for it in &page.items {
-            let draws = self.draws(page, it, &clips, &dopts);
+            let draws = shown.draws(it, &dopts);
             match it {
                 Placed::Lines { story, path, para, .. } => {
                     let idx = self.entry(*story, path, para);
@@ -992,20 +993,6 @@ impl Exporter<'_> {
         }
     }
 
-    /// Display items for one placed item.
-    fn draws(&self, page: &Page, it: &Placed, clips: &CellClips, dopts: &DisplayOptions) -> Vec<Draw> {
-        let mut items = vec![it.clone()];
-        // Lines in a cell cut off at its edge are drawn inside its clip: `page_display` finds the
-        // cell among the items (cells themselves draw nothing). Only that line's cell goes along.
-        if let Placed::Lines { story, path, .. } = it
-            && let Some(cell) = clip_cell(clips, *story, &path.0)
-        {
-            items.push(cell.clone());
-        }
-        let one = Page { w: page.w, h: page.h, section: page.section, number: page.number, items, body: page.body, ..Default::default() };
-        page_display(self.doc, &one, dopts)
-    }
-
     /// A heading's text for bookmarks and tags: what the pages show. That leaves out what its
     /// layout `pl` left out (hidden text, resolved as laid out, so table formatting counts too) and,
     /// without markup, tracked deletions.
@@ -1898,31 +1885,6 @@ fn path_from(b: &kurbo::BezPath) -> Option<Path> {
     pb.finish()
 }
 
-/// A page's cells whose content is cut off at their edge, by story and content path (table,
-/// row, cell), with their place in header, footer, items order (the first wins, as in layout).
-type CellClips<'a> = HashMap<StoryRef, HashMap<Vec<u32>, (usize, &'a Placed)>>;
-
-fn clipped_cells(page: &Page) -> CellClips<'_> {
-    let mut clips: CellClips = HashMap::new();
-    for (order, it) in page.header.iter().chain(&page.footer).chain(&page.items).enumerate() {
-        if let Placed::Cell { table, row, cell, story, clip: true, .. } = it
-            && let (Ok(row), Ok(cell)) = (u32::try_from(*row), u32::try_from(*cell))
-        {
-            let mut prefix = table.0.clone();
-            prefix.extend([row, cell]);
-            clips.entry(*story).or_default().entry(prefix).or_insert((order, it));
-        }
-    }
-    clips
-}
-
-/// The clipped cell a line at `path` of `story` is in: the first one whose path starts it. A
-/// lookup per prefix of the (short) path instead of passing every clipped cell with every line.
-fn clip_cell<'a>(clips: &CellClips<'a>, story: StoryRef, path: &[u32]) -> Option<&'a Placed> {
-    let cells = clips.get(&story)?;
-    (0..=path.len()).filter_map(|k| cells.get(path.get(..k)?)).min_by_key(|(order, _)| *order).map(|(_, it)| *it)
-}
-
 /// Where each glyph's text ends: the cluster (byte offset) of the first later glyph whose cluster
 /// is past the glyph's own, else `len`. One backward pass keeping the later clusters that can
 /// still be an answer, so a long run of glyphs sharing a cluster (combining marks) stays linear.

crates/pdf/src/tests.rs

@@ -2039,7 +2039,7 @@ fn bundled_unicode_glyphs_are_visible_and_extractable() {
     let lay = layout(&d, &mut LayoutCache::new(), &LayoutOptions::default());
     let mut drawn = String::new();
     for page in &lay.pages {
-        for draw in page_display(&d, page, &DisplayOptions::default()) {
+        for draw in wordcraft_layout::display::page_display(&d, page, &DisplayOptions::default()) {
             if let Draw::Glyphs { face, glyphs, text, .. } = draw {
                 assert_eq!(face.data(), bundled.data(), "page glyphs must use the bundled face without system fallback");
                 assert!(glyphs.iter().all(|(id, _, _)| *id != 0), "page glyphs must not use .notdef");
@@ -2450,43 +2450,3 @@ fn cluster_ends_match_the_next_larger_cluster_in_linear_time() {
     assert!(ends[..=n].iter().all(|e| *e == 2 * n + 2));
     assert_eq!(ends.last(), Some(&(2 * n + 4)));
 }
-
-/// A line in a cell cut off at its edge is drawn with that cell's clip, found by path in an index
-/// built once per page: every line used to carry a clone of every clipped cell on the page, so a
-/// page of exact-height rows cost lines × cells.
-#[test]
-fn a_line_finds_its_clipped_cell_by_path() {
-    let cell = |story, table: Vec<u32>, row, cell, clip| Placed::Cell {
-        rect: Rect::default(),
-        covered: false,
-        table: DocPath(table),
-        row,
-        cell,
-        story,
-        clip,
-    };
-    let mut page = Page { items: vec![cell(StoryRef::Body, vec![0], 0, 1, false), cell(StoryRef::Body, vec![2], 1, 0, true)], ..Default::default() };
-    // A nested clipped cell inside the first one; the outer one comes first in the page.
-    page.items.push(cell(StoryRef::Body, vec![2, 1, 0, 3], 0, 0, true));
-    page.footer.push(cell(StoryRef::Part(7), vec![0], 0, 0, true));
-    let clips = clipped_cells(&page);
-    let found = |story, path: &[u32]| {
-        clip_cell(&clips, story, path).and_then(|c| if let Placed::Cell { table, .. } = c { Some(table.0.clone()) } else { None })
-    };
-    assert_eq!(found(StoryRef::Body, &[2, 1, 0, 0]), Some(vec![2]));
-    assert_eq!(found(StoryRef::Body, &[2, 1, 0, 3, 0, 0, 1]), Some(vec![2]), "the first cell in page order wins, as in layout");
-    assert_eq!(found(StoryRef::Body, &[0, 0, 1, 0]), None, "that cell isn't clipped");
-    assert_eq!(found(StoryRef::Body, &[2, 0, 0, 0]), None, "another row");
-    assert_eq!(found(StoryRef::Part(7), &[0, 0, 0, 2]), Some(vec![0]));
-    assert_eq!(found(StoryRef::Body, &[0, 0, 0, 2]), None, "another story");
-
-    // 100 000 clipped cells and as many lines: a lookup each, not a pass over the cells each
-    // (10^10 steps, minutes; the lookups take well under a second on a loaded machine).
-    let n = 100_000;
-    let big = Page { items: (0..n).map(|r| cell(StoryRef::Body, vec![0], r, 0, true)).collect(), ..Default::default() };
-    let start = std::time::Instant::now();
-    let clips = clipped_cells(&big);
-    let hits = (0..n as u32).filter(|r| clip_cell(&clips, StoryRef::Body, &[0, *r, 0, 0]).is_some()).count();
-    assert_eq!(hits, n);
-    assert!(start.elapsed() < std::time::Duration::from_secs(10), "{:?}", start.elapsed());
-}