6ef13b2cc8a6
linear.rs
//! Lookups that once rescanned the page, the paragraph or the document for every item they
//! looked up (#3692, #3706): an input 8x the size must cost about 8x as much, not 64x.
//!
//! The cost is the steps the lookups' walks count ([`crate::work`]), not a timing, so a busy
//! machine can't make a linear lookup look quadratic or the other way round.
use super::SCALE;
use crate::{
Block, CharProps, DocLayout, Document, HeaderSet, HeightRule, InlineObject, LayoutCache, LayoutOptions, Page, ParaLayout, Paragraph, Path,
Placed, SectionProps, SectionStart, StoryRef, display, layout, para, work,
};
use wordcraft_doc::para::Run;
use wordcraft_doc::props::Rgb;
use wordcraft_doc::{Pos, Table};
fn lay(d: &Document, opts: &LayoutOptions) -> DocLayout {
layout(d, &mut LayoutCache::new(), opts)
}
/// The most steps 8x the input may take, against the steps of the input: linear walks take
/// about 8x (a little more where a fixed cost is shared out), quadratic ones about 64x.
const MAX_STEP_RATIO: f64 = 1.5 * SCALE as f64;
/// Asserts `f` takes about [`SCALE`] times the steps ([`crate::work`]) on `make(SCALE * n)` as on
/// `make(n)`, not [`SCALE`]² times. Making the inputs isn't counted.
pub(crate) fn assert_linear_steps<T>(what: &str, n: usize, make: impl Fn(usize) -> T, f: impl Fn(&T)) {
let (small, big) = (make(n), make(SCALE * n));
let (s, b) = (work::count(|| f(&small)), work::count(|| f(&big)));
let ratio = b as f64 / s.max(1) as f64;
eprintln!("{what}: {s} steps for n, {b} for {SCALE}n, ratio {ratio:.1}");
assert!(s > 0, "{what}: no steps counted, so the walk this test watches no longer counts them (crate::work)");
assert!(ratio <= MAX_STEP_RATIO, "{what}: {SCALE}x the input took {ratio:.1}x the steps ({s} → {b}): not linear");
}
/// [`assert_linear_steps`] for laying out `doc(n)`.
fn assert_layout_linear(what: &str, n: usize, doc: impl Fn(usize) -> Document, opts: &LayoutOptions) {
assert_linear_steps(what, n, doc, |d| drop(std::hint::black_box(lay(d, opts))));
}
/// The first laid-out body paragraph on page 0.
fn first_para(l: &DocLayout) -> Option<&ParaLayout> {
l.pages.first()?.items.iter().find_map(|it| match it {
Placed::Lines { para, story: StoryRef::Body, .. } => Some(para.as_ref()),
_ => None,
})
}
/// Finding 29: proofing text found each character's run from the paragraph's first run.
#[test]
fn proof_text_walks_the_runs_once() {
// One run per character, every other one deleted.
let para = |n: usize| {
let mut p = Paragraph::with_text(&"a".repeat(n), CharProps::default());
p.runs = (0..n).map(|i| Run { len: 1, props: CharProps { del: (i % 2 == 1).then_some(0), ..Default::default() } }).collect();
p
};
assert_eq!(para::proof_text(¶(5)), "a\u{1}a\u{1}a");
// The runs the walk looks at are counted now ([`crate::work`]), as every other walk here is,
// so this no longer depends on a timing: the ratio was creeping over its limit when the
// crate's tests ran in parallel, from cache and memory contention rather than from any
// regression (#5185). Going back to the first run for every character counts the runs once
// per character, which is the quadratic walk this watches for.
assert_linear_steps("proof_text", 50_000, para, |p| drop(std::hint::black_box(para::proof_text(p))));
}
/// A right-to-left paragraph whose one line holds `n` hidden letters: caret offsets with no width.
fn bidi_hidden(n: usize) -> Document {
let head = "سلام ";
let mut d = Document::from_text(&format!("{head}{} world", "x".repeat(n)));
let at = Pos::body(0, 0);
d.format_paragraphs(&at, &at, &|p| p.bidi = Some(true)).unwrap();
d.format_range(&Pos::body(0, head.len()), &Pos::body(0, head.len() + n), &|c| c.hidden = Some(true)).unwrap();
d
}
/// Finding 5: a click on a bidirectional line and a visual caret step measured every caret
/// offset from the line's first cluster.
#[test]
fn bidi_clicks_and_caret_steps_take_linear_time() {
let opts = LayoutOptions { show_hidden: false, ..Default::default() };
let laid = |n: usize| lay(&bidi_hidden(n), &opts);
let Some(pb) = first_para(&laid(SCALE * 5000)).map(|p| p.lines.len()) else { panic!("no paragraph") };
assert_eq!(pb, 1, "the hidden letters stay on one line");
assert_linear_steps("bidi hit test", 5000, laid, |l| {
let Some(p) = first_para(l) else { panic!("no paragraph") };
std::hint::black_box(p.off_at_x(0, 1.0));
std::hint::black_box(l.visual_step(&Pos::body(0, 0), true, 0));
});
}
/// The carets of a line walked in one pass are where `x_of` puts each of them, on bidirectional
/// and left-to-right lines alike.
#[test]
fn line_carets_match_x_of() {
let docs = [bidi_hidden(20), Document::from_text("Plain left-to-right text, long enough to wrap. ".repeat(6).as_str()), {
let mut d = Document::from_text("سلام world 123 دنیا (مرحبا) end");
let at = Pos::body(0, 0);
d.format_paragraphs(&at, &at, &|p| p.bidi = Some(true)).unwrap();
d
}];
for d in &docs {
for show_hidden in [false, true] {
let l = lay(d, &LayoutOptions { show_hidden, ..Default::default() });
let Some(p) = first_para(&l) else { panic!("no paragraph") };
for li in 0..p.lines.len() {
let want: Vec<_> = p.line_offsets(li).into_iter().map(|off| (off, p.x_of(li, off))).collect();
assert!(!want.is_empty());
assert_eq!(p.line_carets(li), want, "line {li}");
}
}
}
}
/// Finding 3: autofitting a table counted its grid's columns again for every spanning cell.
#[test]
fn autofit_tables_with_a_spanning_cell_in_every_row_lay_out_in_linear_time() {
// Rows with no cells, only a column skipped before and after them with a width: two
// spanning entries a row for next to no layout, so counting the grid per entry dominates.
let doc = |n: usize| {
let mut t = Table::new(n, 1, 468.0);
for row in t.rows.iter_mut().skip(1) {
row.cells.clear();
row.props.grid_before = 1;
row.props.w_before = Some(10.0);
row.props.grid_after = 1;
row.props.w_after = Some(10.0);
}
let mut d = Document::from_text("x");
d.insert_block(StoryRef::Body, &Path::top(0), Block::Table(t)).unwrap();
d
};
assert_layout_linear("spanning cells", 2000, doc, &LayoutOptions::default());
}
/// `n` continuous sections of an empty paragraph each, each with a different first page. The
/// first section names every header and footer; the others name them too, or (`inherit`) name
/// none and link to the previous section's.
fn sections(n: usize, inherit: bool) -> Document {
use wordcraft_doc::PartKind::{Footer, Header};
let mut d = Document::from_text(&"\n".repeat(n.saturating_sub(1)));
let mut part = |k| d.add_part(k, vec![wordcraft_doc::para_block(Paragraph::with_text("Head", CharProps::default()))]);
let ids = [part(Header), part(Header), part(Header), part(Footer), part(Footer), part(Footer)];
let named = SectionProps {
start: SectionStart::Continuous,
title_page: true,
headers: HeaderSet { default: Some(ids[0]), first: Some(ids[1]), even: Some(ids[2]) },
footers: HeaderSet { default: Some(ids[3]), first: Some(ids[4]), even: Some(ids[5]) },
..Default::default()
};
let linked = SectionProps { headers: HeaderSet::default(), footers: HeaderSet::default(), ..named.clone() };
for i in 0..n.saturating_sub(1) {
let s = if i == 0 || !inherit { named.clone() } else { linked.clone() };
d.para_mut(StoryRef::Body, &Path::top(i)).unwrap().section = Some(Box::new(s));
}
d.last_section = if inherit { linked } else { named };
d
}
/// Finding 13: each section's headers and footers were found by walking back through the
/// sections before it, for every section and again for every page. Linked to the previous
/// section's, they must cost no more to lay out than named in each section.
#[test]
fn headers_inherited_through_many_sections_lay_out_in_linear_time() {
let l = lay(§ions(200, true), &LayoutOptions::default());
assert!(l.pages.iter().all(|p| !p.header.is_empty() && !p.footer.is_empty()), "the header and footer are inherited");
let opts = LayoutOptions::default();
assert_layout_linear("inherited headers", 1000, |n| sections(n, true), &opts);
let steps = |inherit: bool| work::count(|| drop(std::hint::black_box(lay(§ions(1000, inherit), &opts))));
let (named, inherited) = (steps(false), steps(true));
assert!(inherited <= 2 * named, "1000 inheriting sections took {inherited} steps, named ones {named}");
}
/// A header of `n` short paragraphs.
fn tall_header(n: usize) -> (Document, u32) {
let mut d = Document::from_text("Body");
let paras = (0..n).map(|i| wordcraft_doc::para_block(Paragraph::with_text(&format!("h{i}"), CharProps::default()))).collect();
let id = d.add_part(wordcraft_doc::PartKind::Header, paras);
d.last_section.headers.default = Some(id);
(d, id)
}
/// Finding 28: selecting across a header looked through the whole page for each paragraph.
#[test]
fn selecting_a_long_header_takes_linear_time() {
// The header laid out, and the selection from its first paragraph to its last.
let laid = |n: usize| {
let (d, id) = tall_header(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 * 300);
assert!(l.selection_rects(&d, &a, &b, 0).len() >= SCALE * 300, "a rectangle per paragraph");
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))));
}
/// One paragraph of `n` lines (a line break after each word), so it runs over many pages.
fn many_lines(n: usize) -> Document {
let mut d = Document::from_text("");
d.body = vec![wordcraft_doc::para_block(Paragraph::with_text(&"x\n".repeat(n), CharProps::default()))];
d
}
/// The piece of a long paragraph on each page looked through every line of the paragraph for the
/// pictures and shapes to draw with it (#6757).
#[test]
fn a_paragraph_over_many_pages_lays_out_in_linear_time() {
let pages = lay(&many_lines(SCALE * 400), &LayoutOptions::default()).pages.len();
assert!(pages > 40, "the paragraph runs over many pages: {pages}");
assert_layout_linear("a paragraph over many pages", 400, many_lines, &LayoutOptions::default());
}
/// 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 {
let mut t = Table::new(n, 60, 468.0);
for row in &mut t.rows {
row.props.height = Some(0.5);
row.props.height_rule = HeightRule::Exact;
}
let mut d = Document::from_text("x");
d.insert_block(StoryRef::Body, &Path::top(0), Block::Table(t)).unwrap();
d
}
/// Finding 1: drawing a line in a clipped cell looked through every clipped cell on the page.
#[test]
fn drawing_many_clipped_cells_takes_linear_time() {
let laid = |n: usize| {
let d = clipped_table(n);
let l = lay(&d, &LayoutOptions::default());
(d, l)
};
let opts = display::DisplayOptions::default();
let draw = |(d, l): &(Document, DocLayout)| l.pages.first().map(|p| display::page_display(d, p, &opts)).unwrap_or_default();
let clips = draw(&laid(SCALE * 16)).iter().filter(|i| matches!(i, display::Draw::Clip { .. })).count();
assert_eq!(clips, SCALE * 16 * 60, "every cell's line is clipped, all on the first page");
assert_linear_steps("clipped cells", 16, laid, |dl| drop(std::hint::black_box(draw(dl))));
}
/// `n` words, each inserted by its own author, at a size that fits them all on the first page.
fn tracked_words(n: usize) -> Document {
let mut d = Document::from_text("x");
let p = Paragraph {
text: "word ".repeat(n),
runs: (0..n).map(|i| Run { len: 5, props: CharProps { ins: u32::try_from(i).ok(), size: Some(1.0), ..Default::default() } }).collect(),
..Paragraph::with_text("", CharProps::default())
};
d.body = vec![wordcraft_doc::para_block(p)];
d.revisions = (0..n).map(|i| wordcraft_doc::Revision::new(wordcraft_doc::RevisionKind::Insert, format!("Author {i}"), "")).collect();
d
}
/// Finding 30 (#3706): every tracked run ranked its author among all the document's revisions.
#[test]
fn drawing_tracked_changes_by_many_authors_takes_linear_time() {
let laid = |n: usize| {
let d = tracked_words(n);
let l = lay(&d, &LayoutOptions::default());
(d, l)
};
assert_eq!(laid(SCALE * 1000).1.pages.len(), 1);
let opts = display::DisplayOptions { markup: true, ..Default::default() };
let draw = |(d, l): &(Document, DocLayout)| l.pages.first().map(|p| display::page_display(d, p, &opts)).unwrap_or_default();
// Every run is drawn in its author's colour, so the authors are ranked at least once.
assert_linear_steps("tracked runs", 1000, laid, |dl| drop(std::hint::black_box(draw(dl))));
}
/// Each author keeps the colour of their first revision's place among the authors.
#[test]
fn tracked_changes_colour_by_author_in_order_of_appearance() {
let mut d = tracked_words(3);
// Words 0 and 2 by Ana, word 1 by Ben: Ana first, Ben second.
for (r, a) in d.revisions.iter_mut().zip(["Ana", "Ben", "Ana"]) {
r.author = a.into();
}
let l = lay(&d, &LayoutOptions::default());
let opts = display::DisplayOptions { markup: true, ..Default::default() };
let colours: Vec<_> = display::page_display(&d, &l.pages[0], &opts)
.into_iter()
.filter_map(|i| if let display::Draw::Glyphs { color, .. } = i { Some(color) } else { None })
.collect();
let (ana, ben) = (display::revision_color(0), display::revision_color(1));
assert_ne!(ana, ben);
assert_eq!(colours, [ana, ben, ana]);
}
/// Finding 30 (#3706): every comment balloon ranked its author among all the comments.
#[test]
fn balloons_for_many_authors_lay_out_in_linear_time() {
let doc = |n: usize| {
let mut d = Document::from_text(&"word ".repeat(n));
for i in (0..n).rev() {
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: format!("Author {i}"), part, ..Default::default() });
let p = CharProps::default();
d.insert_object(&Pos::body(0, 5 * i + 4), InlineObject::CommentEnd { id }, &p).unwrap();
d.insert_object(&Pos::body(0, 5 * i), InlineObject::CommentStart { id }, &p).unwrap();
}
d
};
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}");
}
/// A paragraph of a decimal tab at 200 pt followed by `text`.
fn after_decimal_tab(text: &str) -> Document {
use wordcraft_doc::props::{TabAlign, TabStop};
let mut d = Document::from_text(&format!("\t{text}"));
let at = Pos::body(0, 0);
d.format_paragraphs(&at, &at, &|p| p.tabs = Some(vec![TabStop { pos: 200.0, align: TabAlign::Decimal, leader: Default::default() }])).unwrap();
d
}
/// The text after a decimal tab was looked at again from the tab for its '.' after each of its
/// clusters, so a long run of clusters without a '.' (soft hyphens take no room, so they stay on
/// one line) took quadratic time.
#[test]
fn text_after_a_decimal_tab_is_looked_at_once() {
let opts = LayoutOptions::default();
// The text after the tab still ends at the stop, where it ended before.
let l = lay(&after_decimal_tab("12.5"), &opts);
let (Some(end), Some(start)) = (l.caret(&Pos::body(0, 5)), l.caret(&Pos::body(0, 0))) else { panic!("no carets") };
assert!((end.x - start.x - 200.0).abs() < 1.0, "the text ends at the stop: {} from {}", end.x, start.x);
assert_layout_linear("decimal tab", 2000, |n| after_decimal_tab(&format!("1{}", "\u{AD}".repeat(n))), &opts);
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.