oxedyne/fe2o3 — fe2o3_austenite/src/driver.rs

oxedyne/fe2o3/fe2o3_austenite/src/driver.rs

62.6 KiB, 252 runs

created by r1870400018:35659, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1	//! The two-pass streaming driver, and its convergence loop.
2	//!
3	//! This is the heart of Phase 0. A pass composes the document: it runs the box-glue-penalty stream
4	//! through a greedy vertical page breaker, places each line, records every anchor it meets, and
5	//! resolves a forward reference against the width reserved for it. Pass A sees an empty ledger, so
6	//! backward-looking anchors resolve but forward references show nothing yet. Pass B re-composes with
7	//! Pass A's ledger loaded, so a forward reference now reads the value it points at.
8	//!
9	//! The loop terminates two ways, and only two, and it is honest about which:
10	//!
11	//! * Converged. From the second pass on, if the new ledger is stable against the last -- same page
12	//! count, and no anchor changed page -- the document has stopped moving. The current pages are
13	//! final. This is the normal outcome, and by construction it is two passes when every forward
14	//! reference fits the width reserved for it.
15	//! * Did not converge. If the pass cap is reached with the ledger still moving, the driver does
16	//! not guess. It differences the last two ledgers and returns an error naming the anchor that
17	//! moved, the pages it moved between, and any reference whose realised value overflowed its
18	//! reservation -- which is the thing that broke the two-pass guarantee.
19
20	use crate::{
21	ir::{
22	BoxNode,
23	ColumnsNode,
24	Dims,
25	FloatNode,
26	FloatPlacement,
27	FloatScope,
28	Footnote,
29	Leaf,
30	LeafKind,
31	Metrics,
32	Node,
33	PageColumns,
34	Sp,
35	},
36	ledger::{
37	Anchor,
38	Ledger,
39	Position,
40	},
41	page::{
42	Frame,
43	Page,
44	PageGeometry,
45	Placed,
46	PlacedKind,
47	Region,
48	},
49	};
50
51	use oxedyne_fe2o3_core::prelude::*;
52
53	use std::collections::HashSet;
54
55	/// The spacing that frames the footnotes at the foot of a page: the gap above the separator rule, the
56	/// rule itself and how wide it runs, the gap below it before the first note, and the gap between one
57	/// note and the next. Every length is scaled points, so the foot never leaves the integer domain the
58	/// driver breaks on. The note lines themselves carry their own leading; this is only the furniture
59	/// around them.
60	#[derive(Clone, Copy, Debug)]
61	pub struct FootStyle {
62	pub gap_above_rule: Sp,
63	pub rule_thick: Sp,
64	pub rule_width: Sp,
65	pub gap_below_rule: Sp,
66	pub gap_between: Sp,
67	}
68
69	impl Default for FootStyle {
70	fn default() -> Self {
71	Self {
72	gap_above_rule: Sp::from_pt(8.0),
73	rule_thick: Sp::from_pt(0.4),
74	rule_width: Sp::from_pt(120.0), // a short rule, about a third of a text block
75	gap_below_rule: Sp::from_pt(4.0),
76	gap_between: Sp::from_pt(3.0),
77	}
78	}
79	}
80
81	/// A trivial in-memory document: a vertical box-glue-penalty stream, the geometry every page takes, and
82	/// the foot spacing its footnotes are framed with. Phase 0 has one geometry for the whole document;
83	/// per-chapter geometry is later.
84	#[derive(Clone, Debug)]
85	pub struct Document {
86	pub nodes: Vec<Node>,
87	pub geom: PageGeometry,
88	pub foot: FootStyle,
89	}
90
91	impl Document {
92	pub fn new(nodes: Vec<Node>, geom: PageGeometry) -> Self {
93	Self { nodes, geom, foot: FootStyle::default() }
94	}
95	}
96
97	/// How hard the driver tries to converge. `max_passes` caps the loop; when it is reached with the
98	/// ledger still moving, the driver reports a non-convergence rather than looping forever. Three is
99	/// the architecture's stated worst case (two passes, plus one when a reservation is exceeded); a
100	/// little headroom above that catches a genuine oscillation without hiding it.
101	#[derive(Clone, Copy, Debug)]
102	pub struct Config {
103	pub max_passes: u32,
104	}
105
106	impl Default for Config {
107	fn default() -> Self {
108	Self { max_passes: 4 }
109	}
110	}
111
112	/// The result of a converged compile: the final pages, the ledger that fixed them, and how many
113	/// passes it took -- the last being the number the flat-memory claim is proved against.
114	#[derive(Debug)]
115	pub struct CompileOutput {
116	pub pages: Vec<Page>,
117	pub ledger: Ledger,
118	pub passes: u32,
119	}
120
121	/// Runs the document to a fixed point, or reports why it would not settle.
122	pub fn run<M: Metrics>(
123	doc: &Document,
124	metrics: &M,
125	cfg: Config,
126	)
127	-> Outcome<CompileOutput>
128	{
129	if cfg.max_passes < 2 {
130	return Err(err!(
131	"The driver needs at least two passes to resolve a forward reference, but max_passes \
132	is {}.", cfg.max_passes; Input, Invalid, Configuration));
133	}
134	let mut prev = Ledger::new(); // Pass A sees no resolved forward references.
135	let mut pass = 0u32;
136	loop {
137	pass += 1;
138	let (pages, ledger) = res!(compose(doc, metrics, &prev));
139
140	// A ledger is only meaningfully stable once a second pass has had the first pass's ledger to
141	// read; comparing Pass A against the empty ledger it started from would converge falsely.
142	if pass >= 2 && ledger.is_stable_against(&prev) {
143	return Ok(CompileOutput { pages, ledger, passes: pass });
144	}
145
146	if pass >= cfg.max_passes {
147	return Err(non_convergence(pass, &ledger, &prev));
148	}
149	prev = ledger;
150	}
151	}
152
153	/// One composition pass over the whole document: material is stacked into the current column until the
154	/// next atom would overflow it, then the flow hops to the next column, or -- from the last column, or on a
155	/// page of one column -- breaks the page. The column layout in force is set by the stream's
156	/// [`Node::PageColumns`] markers (Typst's `set page(columns:)`); a document carrying none flows one column
157	/// to the page throughout, which is the ordinary page.
158	///
159	/// The break is atom-aware, not line-by-line. A run of boxes with no legal breakpoint between them -- a
160	/// paragraph's first two lines welded by the orphan penalty, its last two by the widow penalty (see
161	/// [`doc::guard_widows`](crate::doc)) -- is an atom, weighed and placed whole: if the atom will not fit,
162	/// the column breaks before it rather than splitting a single line off, leaving the column a line short.
163	/// This is the page-bottom slack Typst leaves for widow and orphan avoidance.
164	///
165	/// Footnotes couple to the break: a footnote's note is set at the foot of the column its mark lands on
166	/// (the page's foot, on a page of one column), so the effective bottom shrinks by the note's height as
167	/// marks accumulate, and a line is judged against a bottom already charged for its own note. This does
168	/// not threaten convergence: a note's height is fixed at author time, so the reservation a column pays is
169	/// a pure function of which marks fell in it. What footnotes can do is push a heading or an anchor to a
170	/// later page than a footnote-free fill would -- exactly the movement the ledger already reconciles.
171	///
172	/// Floats come in two scopes (Typst's `place.scope`). A column-scoped float settles at the top or foot of
173	/// the column it is met in, or of the next column with room; a parent-scoped float spans every column, at
174	/// the top or foot of the page. On a page of one column the two coincide. A parent-scoped float met on a
175	/// page whose columns already carry material is seated by relayout, as Typst seats it: the page is
176	/// re-flowed from where it opened with the float already in its band, so the columns shorten beneath it
177	/// rather than the float waiting for a later page.
178	fn compose<M: Metrics>(
179	doc: &Document,
180	metrics: &M,
181	incoming: &Ledger,
182	)
183	-> Outcome<(Vec<Page>, Ledger)>
184	{
185	let mut flow = Flow::new(doc, metrics, incoming);
186	let nodes = &doc.nodes;
187	let mut idx = 0usize;
188	while idx < nodes.len() {
189	idx = res!(flow.step(nodes, idx));
190	}
191	flow.finish()
192	}
193
194	/// Where a page opened: everything a parent-scoped float's relayout rewinds to. It is taken when a page
195	/// (or a column layout) opens, after the waiting page floats are flushed into its bands but before its
196	/// first column opens, and refreshed each time a relayout seats another float, so a second relayout keeps
197	/// the first float's band. Footnotes need no record: a page opens with none.
198	#[derive(Clone)]
199	struct Checkpoint {
200	idx: usize,
201	frame: Frame,
202	y: Sp,
203	col: usize,
204	col_top: Sp,
205	col_start: usize,
206	bands: FloatBands,
207	cbands: FloatBands,
208	pending: Vec<FloatNode>,
209	cpending: Vec<FloatNode>,
210	repeat: Option<BoxNode>,
211	strong_open: bool,
212	stamp: bool, // the page opened on an overflow, so its first column restamps a repeated header
213	marks: (u32, u32), // the ledger's first-heading and back-matter pages when the page opened
214	}
215
216	/// The state one composition pass threads through the stream: the page under construction and the column
217	/// being filled, the float and footnote queues, and the checkpoint a relayout rewinds to. See [`compose`].
218	struct Flow<'a, M: Metrics> {
219	doc: &'a Document,
220	metrics: &'a M,
221	incoming: &'a Ledger,
222	geom: PageGeometry,
223	top: Sp,
224	bottom: Sp,
225	ledger: Ledger,
226	pages: Vec<Page>,
227	frame: Frame,
228	page_no: u32,
229	cols: PageColumns, // the column layout in force
230	col: usize, // the column being filled, from 0
231	col_top: Sp, // the y every column of this page starts at, below the page's top floats
232	col_start: usize, // the frame index the current column's material starts at
233	y: Sp,
234	// Just after a break, leading glue and penalties are discarded.
235	at_top: bool,
236	// A break is permitted at the cursor: a legal breakpoint has just passed, or the column is fresh.
237	at_break: bool,
238	// The last non-marker node was a box, so glue after it is a legal breakpoint (the TeX rule that makes
239	// the glue a forbidden penalty leaves in front illegal too, welding the atom).
240	prev_box: bool,
241	// A strong `#pagebreak()` opened a page no flow content has yet filled, so it is emitted even if it stays
242	// empty (a trailing or consecutive strong break's blank page).
243	strong_open: bool,
244	// The footnotes whose marks landed in the current column; set at its foot when it closes.
245	notes: Vec<Footnote>,
246	// The page's parent-scoped float bands, and the current column's own.
247	bands: FloatBands,
248	cbands: FloatBands,
249	// The floats deferred out of the flow, in document order, awaiting room: parent-scoped ones a page,
250	// column-scoped ones a column. The heights are fixed at author time, so each queue is a pure function
251	// of the stream and the geometry and does not threaten convergence.
252	pending: Vec<FloatNode>,
253	cpending: Vec<FloatNode>,
254	// The header a breakable table asks repeated, armed by a `Node::RepeatHead(Some(..))` and cleared by
255	// `RepeatHead(None)`; stamped at the top of every column the rows spill onto.
256	repeat: Option<BoxNode>,
257	check: Checkpoint,
258	seated: HashSet<usize>, // the parent-scoped floats a relayout seated, by stream index, skipped on replay
259	}
260
261	impl<'a, M: Metrics> Flow<'a, M> {
262	fn new(doc: &'a Document, metrics: &'a M, incoming: &'a Ledger) -> Self {
263	let geom = doc.geom;
264	let top = geom.content_top();
265	let bottom = geom.content_top() + geom.content_height();
266	let ledger = Ledger::new();
267	let marks = (ledger.body_start_page, ledger.back_matter_start_page);
268	Self {
269	doc,
270	metrics,
271	incoming,
272	geom,
273	top,
274	bottom,
275	ledger,
276	pages: Vec::new(),
277	frame: Frame::new(),
278	page_no: 1,
279	cols: PageColumns::ONE,
280	col: 0,
281	col_top: top,
282	col_start: 0,
283	y: top,
284	at_top: true,
285	at_break: true,
286	prev_box: false,
287	strong_open: false,
288	notes: Vec::new(),
289	bands: FloatBands::empty(),
290	cbands: FloatBands::empty(),
291	pending: Vec::new(),
292	cpending: Vec::new(),
293	repeat: None,
294	check: Checkpoint {
295	idx: 0,
296	frame: Frame::new(),
297	y: top,
298	col: 0,
299	col_top: top,
300	col_start: 0,
301	bands: FloatBands::empty(),
302	cbands: FloatBands::empty(),
303	pending: Vec::new(),
304	cpending: Vec::new(),
305	repeat: None,
306	strong_open: false,
307	stamp: false,
308	marks,
309	},
310	seated: HashSet::new(),
311	}
312	}
313
314	/// Does the layout in force set more than one column?
315	fn multi(&self) -> bool {
316	self.cols.count > 1
317	}
318
319	/// The geometry of the column being filled: the page's own on a page of one column.
320	fn col_geom(&self) -> PageGeometry {
321	if self.multi() {
322	self.geom.column_slice(self.col, self.cols.count, self.cols.gutter)
323	} else {
324	self.geom
325	}
326	}
327
328	/// The lowest y the current column's material may reach: the page foot less the page's and the column's
329	/// foot floats. Footnotes are charged against this separately, as they accumulate.
330	fn col_bottom(&self) -> Sp {
331	self.bottom - self.bands.bot_reserve - self.cbands.bot_reserve
332	}
333
334	/// Records where the page opened, for a relayout to rewind to: `idx` is the stream index the page's
335	/// flow starts from. Only a layout of several columns ever rewinds, so a page of one column takes no
336	/// copy of its frame.
337	fn mark(&mut self, idx: usize, stamp: bool) {
338	if !self.multi() {
339	return;
340	}
341	self.check = Checkpoint {
342	idx,
343	frame: self.frame.clone(),
344	y: self.y,
345	col: self.col,
346	col_top: self.col_top,
347	col_start: self.col_start,
348	bands: self.bands,
349	cbands: self.cbands,
350	pending: self.pending.clone(),
351	cpending: self.cpending.clone(),
352	repeat: self.repeat.clone(),
353	strong_open: self.strong_open,
354	stamp,
355	marks: (self.ledger.body_start_page, self.ledger.back_matter_start_page),
356	};
357	}
358
359	/// Rewinds to where the page opened, its first column not yet open, and returns the stream index to
360	/// replay from. The anchors laid since are simply re-recorded as the replay lays them again -- the ledger
361	/// keeps the last placement of each identity -- so only its first-heading and back-matter marks, which
362	/// a rewound anchor may have fixed, need restoring.
363	fn rewind(&mut self) -> usize {
364	let c = self.check.clone();
365	self.frame = c.frame;
366	self.y = c.y;
367	self.col = c.col;
368	self.col_top = c.col_top;
369	self.col_start = c.col_start;
370	self.bands = c.bands;
371	self.cbands = c.cbands;
372	self.pending = c.pending;
373	self.cpending = c.cpending;
374	self.notes = Vec::new();
375	self.repeat = c.repeat;
376	self.strong_open = c.strong_open;
377	self.at_top = true;
378	self.at_break = true;
379	self.prev_box = false;
380	self.ledger.body_start_page = c.marks.0;
381	self.ledger.back_matter_start_page = c.marks.1;
382	c.idx
383	}
384
385	/// Sets the current column's footnotes at its foot, above its foot floats, and clears them.
386	fn lay_notes(&mut self) -> Outcome<()> {
387	let g = self.col_geom();
388	let foot = self.col_bottom();
389	res!(lay_footnotes(
390	&mut self.frame, &self.notes, self.page_no, g, &self.doc.foot, foot, self.metrics, self.incoming,
391	&mut self.ledger));
392	self.notes.clear();
393	Ok(())
394	}
395
396	/// Closes the page -- its last column's footnotes set, the page stored -- and opens the next: the page
397	/// floats that were waiting flushed into its bands, the page marked for a relayout, then its first column
398	/// opened below them. `idx` is the stream index the new page's flow starts from; `stamp` restamps a
399	/// repeated table header, for a page opened by rows overflowing the last.
400	fn next_page(&mut self, idx: usize, stamp: bool) -> Outcome<()> {
401	res!(self.lay_notes());
402	self.pages.push(Page::new(self.page_no, self.geom, std::mem::take(&mut self.frame)));
403	self.page_no += 1;
404	self.y = self.top;
405	self.bands = FloatBands::empty();
406	res!(flush_floats(
407	&mut self.pending, &mut self.frame, &mut self.y, &mut self.bands, Sp::ZERO, self.page_no, self.geom,
408	self.top, self.bottom, self.metrics, self.incoming, &mut self.ledger));
409	self.mark(idx, stamp);
410	self.open_columns(stamp)
411	}
412
413	/// Opens the page's first column below its top floats, with its leading collapsed, restamping a
414	/// repeated table header when the page opened on rows that overflowed the last.
415	fn open_columns(&mut self, stamp: bool) -> Outcome<()> {
416	res!(self.open_column(0));
417	self.at_top = true;
418	if stamp {
419	res!(self.stamp_repeat());
420	}
421	Ok(())
422	}
423
424	/// Opens column `col` of the current page: the first at the cursor (below the page's top floats), a
425	/// later one at the same top as the first. The column floats that were waiting are flushed into it.
426	fn open_column(&mut self, col: usize) -> Outcome<()> {
427	self.col = col;
428	if col == 0 {
429	self.col_top = self.y;
430	}
431	self.y = self.col_top;
432	self.col_start = self.frame.len();
433	self.cbands = FloatBands::empty();
434	if self.multi() {
435	res!(self.flush_col_floats());
436	}
437	Ok(())
438	}
439
440	/// Stamps the armed repeated table header at the cursor, in the current column. The rows that broke
441	/// onto this region are placed just below it; the header makes the region non-empty, so no leading is
442	/// discarded under it.
443	fn stamp_repeat(&mut self) -> Outcome<()> {
444	if let Some(head) = self.repeat.clone() {
445	let g = self.col_geom();
446	res!(place_vbox(&head, self.y, self.page_no, g, self.metrics, self.incoming, &mut self.frame, &mut self.ledger));
447	self.y += head.dims.vextent();
448	}
449	Ok(())
450	}
451
452	/// Moves the flow on: to the next column, or from the last column (or a page of one) to a fresh page
453	/// whose flow starts at stream index `idx`. An overflow break stamps a repeated table header at the top
454	/// of the region the rows spill onto, below any floats; a forced break does not, since no row broke
455	/// across it.
456	fn hop(&mut self, idx: usize, overflow: bool) -> Outcome<()> {
457	if self.multi() && self.col + 1 < self.cols.count {
458	res!(self.lay_notes());
459	res!(self.open_column(self.col + 1));
460	self.at_top = true;
461	if overflow {
462	res!(self.stamp_repeat());
463	}
464	Ok(())
465	} else {
466	self.next_page(idx, overflow)
467	}
468	}
469
470	/// Seats the waiting column floats that fit in the current column, in document order, stopping at the
471	/// first that will not. The front float of an empty column is seated even when it will not fit, so the
472	/// queue always drains.
473	fn flush_col_floats(&mut self) -> Outcome<()> {
474	let mut placed_any = false;
475	while !self.cpending.is_empty() {
476	let force = self.frame.len() == self.col_start && !placed_any;
477	let f = self.cpending[0].clone();
478	if res!(self.try_insert_col_float(&f, false, force)) {
479	self.cpending.remove(0);
480	placed_any = true;
481	} else {
482	break;
483	}
484	}
485	Ok(())
486	}
487
488	/// Inserts one column-scoped float into the current column's top or foot band by Typst's rule -- the
489	/// midpoint rule for `auto` -- shifting that column's material (and only that column's) to make room, as
490	/// [`try_insert_float`] does for a page band. `clearance_flag` is whether the clearance counts in the fit,
491	/// `force` seats the float even when it will not fit. Returns whether it was seated.
492	fn try_insert_col_float(&mut self, f: &FloatNode, clearance_flag: bool, force: bool) -> Outcome<bool> {
493	let g = self.col_geom();
494	let x0 = g.content_left();
495	let x1 = g.content_left() + g.content_width();
496	let foot_now = foot_reserve(&self.notes, &[], &self.doc.foot);
497	let base = (self.bottom - self.bands.bot_reserve) - self.col_top; // the column's own height
498	let band = f.height + f.clearance;
499	let need_fit = f.height + if clearance_flag { f.clearance } else { Sp::ZERO };
500	let remaining = (self.col_bottom() - foot_now) - self.y;
501	if need_fit > remaining && !force {
502	return Ok(false);
503	}
504	let used = base - remaining;
505	let side = match f.placement {
506	FloatPlacement::Top => FloatPlacement::Top,
507	FloatPlacement::Bottom => FloatPlacement::Bottom,
508	FloatPlacement::Auto => auto_side(used, need_fit, base),
509	};
510	let start = self.frame.len();
511	match side {
512	FloatPlacement::Bottom => {
513	// The column's existing foot floats rise by this float's band, and it takes the very foot of
514	// the column, just above the page's own foot band.
515	self.frame.shift_region_from(self.col_start, -band, Region::Foot);
516	self.ledger.shift_region_anchors_within(self.page_no, -band, Region::Foot, x0, x1);
517	let at = (self.bottom - self.bands.bot_reserve) - f.height;
518	res!(place_float(f, at, self.page_no, g, self.metrics, self.incoming, &mut self.frame, &mut self.ledger, Region::Foot));
519	self.frame.stamp_region(start, Region::Foot);
520	self.cbands.bot_reserve = self.cbands.bot_reserve + band;
521	},
522	_ => {
523	// Seated below the column's top floats already stacked, the column's body shifting down.
524	let at = self.col_top + self.cbands.top_used;
525	self.frame.shift_region_from(self.col_start, band, Region::Body);
526	self.ledger.shift_region_anchors_within(self.page_no, band, Region::Body, x0, x1);
527	res!(place_float(f, at, self.page_no, g, self.metrics, self.incoming, &mut self.frame, &mut self.ledger, Region::Top));
528	self.frame.stamp_region(start, Region::Top);
529	self.cbands.top_used = self.cbands.top_used + band;
530	self.y += band;
531	},
532	}
533	Ok(true)
534	}
535
536	/// Seats a parent-scoped float met at stream index `idx` on a page of several columns, spanning them all
537	/// in the page's top or foot band. Its side is chosen where it stands in the flow; then, if the page's
538	/// bands have room, the page is rewound to where it opened, the float seated in its band, and the page's
539	/// flow replayed beneath it -- Typst's relayout. The replay skips this float, already seated. A float the
540	/// page has no room for waits for the next page. Returns the stream index to continue from.
541	fn seat_parent_float(&mut self, f: &FloatNode, idx: usize) -> Outcome<usize> {
542	if !self.pending.is_empty() {
543	self.pending.push(f.clone());
544	return Ok(idx + 1);
545	}
546	let free = (self.bottom - self.bands.bot_reserve) - (self.top + self.bands.top_used);
547	let base = self.geom.content_height();
548	let fresh = self.check.frame.is_empty(); // the page opened with nothing on it
549	if f.height > free && !fresh {
550	self.pending.push(f.clone());
551	return Ok(idx + 1);
552	}
553	// The side `auto` takes is decided where the float stands, by the midpoint rule over the page region.
554	let used = self.y - self.top;
555	let side = match f.placement {
556	FloatPlacement::Top => FloatPlacement::Top,
557	FloatPlacement::Bottom => FloatPlacement::Bottom,
558	FloatPlacement::Auto => auto_side(used, f.height, base),
559	};
560	let mut seat = f.clone();
561	seat.placement = side;
562	let resume = self.rewind();
563	let stamp = self.check.stamp;
564	// The rewound page carries no flow content, so the clearance does not count in the fit (as a re-queued
565	// float's does not); the fit was checked above, so the float is seated even should it overflow.
566	res!(try_insert_float(
567	&seat, false, true, &mut self.y, &mut self.bands, Sp::ZERO, self.page_no, self.geom, self.top,
568	self.bottom, self.metrics, self.incoming, &mut self.frame, &mut self.ledger));
569	self.seated.insert(idx);
570	self.mark(resume, stamp);
571	res!(self.open_columns(stamp));
572	Ok(resume)
573	}
574
575	/// Processes the node at `idx` and returns the index to continue from: the next node, or -- after a
576	/// relayout -- the node the page's flow opened at.
577	fn step(&mut self, nodes: &[Node], idx: usize) -> Outcome<usize> {
578	let node = &nodes[idx];
579	match node {
580	Node::Glue(g) => {
581	// Glue at the very top of a column is discarded, as TeX discards it, so a column does not open
582	// with blank space left over from the break.
583	if !self.at_top {
584	self.y += g.natural;
585	}
586	// Glue after a box is a legal breakpoint, so the next box opens a fresh atom; glue after a
587	// penalty or glue is not, and leaves `at_break` as it stands.
588	if self.prev_box {
589	self.at_break = true;
590	}
591	self.prev_box = false;
592	},
593	Node::Penalty(p) => {
594	if p.is_forced() {
595	if p.is_column() && self.multi() {
596	// A column break (`#colbreak()`): the next column, or the next page from the last. A weak one
597	// is dropped in a column that holds nothing yet.
598	if p.is_strong() \|\| self.frame.len() > self.col_start {
599	res!(self.hop(idx + 1, false));
600	self.strong_open = false;
601	}
602	} else {
603	// A strong eject (the default `#pagebreak()`, or a column break on a page of one column)
604	// ejects unconditionally; a weak one (a chapter end, section furniture,
605	// `#pagebreak(weak: true)`) only a page carrying content, and is dropped on an empty page.
606	// A strong break on an empty page materialises that blank page and opens another -- Typst's
607	// trailing/consecutive-strong-break behaviour.
608	let strong = p.is_strong();
609	if !self.frame.is_empty() \|\| strong {
610	res!(self.next_page(idx + 1, false));
611	// The page just opened is owed by this break only if the break was strong.
612	self.strong_open = strong;
613	self.check.strong_open = strong;
614	}
615	}
616	self.at_break = true;
617	} else if p.is_forbidden() {
618	// A forbidden penalty (the widow/orphan weld) blocks a break here, and blocks the glue that
619	// follows it from being one, so the lines either side of it stay in one atom.
620	self.at_break = false;
621	} else {
622	self.at_break = true;
623	}
624	self.prev_box = false;
625	},
626	Node::Anchor(id) => {
627	// The body-start and back-matter markers are noticed by `Ledger::record` as the anchor is
628	// recorded. An anchor is transparent to breakability.
629	let x = self.col_geom().content_left();
630	self.ledger.record(Anchor::new(id.clone(), Position::new(self.page_no, x, self.y)));
631	},
632	Node::Float(f) if self.multi() => {
633	match f.scope {
634	FloatScope::Parent => {
635	if self.seated.contains(&idx) {
636	return Ok(idx + 1); // seated by the relayout that is replaying this page
637	}
638	return self.seat_parent_float(f, idx);
639	},
640	FloatScope::Column => {
641	// A column float settles in the current column's bands, or waits for the next column
642	// with room; an earlier waiting float holds it back, so document order is kept.
643	if !self.cpending.is_empty() {
644	self.cpending.push(f.clone());
645	} else {
646	let force = self.frame.len() == self.col_start;
647	if !res!(self.try_insert_col_float(f, !self.at_top, force)) {
648	self.cpending.push(f.clone());
649	}
650	}
651	},
652	}
653	},
654	Node::Float(f) => {
655	// On a page of one column the two scopes coincide: the float is inserted into the page's top or
656	// foot band and the body already on the page shifts to make room (Typst's relayout). An earlier
657	// queued float holds this one back so document order is kept; a float that will not fit defers.
658	if !self.pending.is_empty() {
659	self.pending.push(f.clone());
660	} else {
661	let was_empty = self.frame.is_empty();
662	let foot_now = foot_reserve(&self.notes, &[], &self.doc.foot);
663	// Clearance counts in the fit only when the page already carries FLOW content -- `at_top`
664	// tracks its absence. An empty page seats the float regardless and overflows rather than
665	// deferring forever.
666	let ok = res!(try_insert_float(
667	f, !self.at_top, was_empty, &mut self.y, &mut self.bands, foot_now, self.page_no, self.geom,
668	self.top, self.bottom, self.metrics, self.incoming, &mut self.frame, &mut self.ledger));
669	if !ok {
670	self.pending.push(f.clone());
671	}
672	}
673	},
674	Node::Columns(c) => {
675	if self.multi() {
676	return Err(err!(
677	"A columns block was met on a page already set in {} columns; nested column layouts are \
678	not lowered by the author, so this is a construction bug in the stream's builder.",
679	self.cols.count; Invalid, Bug));
680	}
681	// A columns block on a page of one column flows its own material through the multi-column
682	// pass, which starts at the cursor and resumes the flow below its tallest column.
683	res!(flow_columns(
684	c, &mut self.pages, &mut self.frame, &mut self.page_no, &mut self.y, self.top, self.bottom,
685	self.geom, &mut self.notes, &self.doc.foot, &mut self.bands, &mut self.pending, &mut self.at_top,
686	self.metrics, self.incoming, &mut self.ledger));
687	self.at_break = true;
688	self.prev_box = false;
689	self.strong_open = false;
690	},
691	Node::PageColumns(pc) => {
692	// A new column layout takes effect on a fresh page, as Typst's `set page` does: a page carrying
693	// content is closed first; an empty one simply takes the new layout.
694	if *pc != self.cols {
695	if !self.frame.is_empty() {
696	res!(self.lay_notes());
697	self.pages.push(Page::new(self.page_no, self.geom, std::mem::take(&mut self.frame)));
698	self.page_no += 1;
699	self.y = self.top;
700	self.bands = FloatBands::empty();
701	self.strong_open = false;
702	}
703	// Column floats still waiting join the page queue when the layout drops to one column.
704	if pc.count <= 1 && !self.cpending.is_empty() {
705	let mut queue = std::mem::take(&mut self.cpending);
706	queue.append(&mut self.pending);
707	self.pending = queue;
708	}
709	self.cols = *pc;
710	if self.frame.is_empty() {
711	res!(flush_floats(
712	&mut self.pending, &mut self.frame, &mut self.y, &mut self.bands, Sp::ZERO, self.page_no,
713	self.geom, self.top, self.bottom, self.metrics, self.incoming, &mut self.ledger));
714	}
715	self.mark(idx + 1, false);
716	res!(self.open_columns(false));
717	self.at_break = true;
718	self.prev_box = false;
719	}
720	},
721	Node::RepeatHead(head) => {
722	// Arm or disarm the repeated header. Transparent to breakability, like an anchor.
723	self.repeat = head.as_ref().map(\|b\| (**b).clone());
724	},
725	Node::HBox(_) \| Node::VBox(_) \| Node::Leaf(_) => {
726	// At an atom start, weigh the whole atom -- every box up to the next legal breakpoint, with the
727	// footnotes they introduce reserved from the foot -- and break before it if it will not fit. A box
728	// in mid-atom is placed unconditionally: the atom was found to fit when it opened.
729	if self.at_break {
730	let (atom_ext, atom_reserve) = atom_measure(nodes, idx, &self.notes, &self.doc.foot);
731	// A page of one column breaks whenever it carries anything; a column breaks unless it is the
732	// empty first column of an empty page, so an over-tall atom is seated (overflowing) only there
733	// and never spins from column to column.
734	let may_break = if self.multi() {
735	!(self.at_top && self.frame.is_empty())
736	} else {
737	!self.frame.is_empty()
738	};
739	if may_break && self.y + atom_ext > self.col_bottom() - atom_reserve {
740	res!(self.hop(idx, true));
741	}
742	}
743	let v = node.vextent();
744	let mut marks: Vec<Footnote> = Vec::new();
745	collect_marks(node, &mut marks);
746	let g = self.col_geom();
747	res!(place_node(node, self.y, self.page_no, g, self.metrics, self.incoming, &mut self.frame, &mut self.ledger));
748	self.notes.append(&mut marks); // its marks now belong to the column the node landed in
749	self.y += v;
750	self.at_top = false;
751	self.at_break = false;
752	self.prev_box = true;
753	self.strong_open = false;
754	},
755	}
756	Ok(idx + 1)
757	}
758
759	/// Drains the floats still waiting at the end of the stream -- column floats into the columns that
760	/// follow, then page floats onto the current page and fresh ones -- and closes the last page, returning
761	/// every page and the ledger that fixed them.
762	fn finish(mut self) -> Outcome<(Vec<Page>, Ledger)> {
763	let end = self.doc.nodes.len();
764	// A fresh column seats at least its front float, so each hop shrinks the queue and the loop ends.
765	while self.multi() && !self.cpending.is_empty() {
766	res!(self.flush_col_floats());
767	if self.cpending.is_empty() {
768	break;
769	}
770	res!(self.hop(end, false));
771	self.strong_open = false;
772	}
773	// The page floats: as many as fit on the current page (respecting the bands and footnotes it already
774	// carries), then a fresh page per remaining batch. A fresh, empty page seats at least its front float,
775	// so `pending` shrinks by at least one per fresh page and the loop terminates.
776	loop {
777	let foot_now = foot_reserve(&self.notes, &[], &self.doc.foot);
778	res!(flush_floats(
779	&mut self.pending, &mut self.frame, &mut self.y, &mut self.bands, foot_now, self.page_no, self.geom,
780	self.top, self.bottom, self.metrics, self.incoming, &mut self.ledger));
781	if self.pending.is_empty() {
782	break;
783	}
784	res!(self.next_page(end, false));
785	self.strong_open = false;
786	}
787
788	// The last page holds whatever is left, unless nothing is; its footnotes are set at its foot first.
789	if !self.frame.is_empty() {
790	res!(self.lay_notes());
791	self.pages.push(Page::new(self.page_no, self.geom, std::mem::take(&mut self.frame)));
792	} else if self.strong_open {
793	// A trailing strong `#pagebreak()` opened a fresh page that nothing filled: it is emitted rather than
794	// dropped (Typst 0.15.1 lays a trailing strong break as a blank page).
795	self.pages.push(Page::new(self.page_no, self.geom, Frame::new()));
796	} else if self.pages.is_empty() {
797	// A document with no material is still one blank page, so a page count is always at least one.
798	self.pages.push(Page::new(self.page_no, self.geom, Frame::new()));
799	}
800	self.ledger.total_pages = self.pages.len() as u32;
801	Ok((self.pages, self.ledger))
802	}
803	}
804
805	/// Flows a columns block's material into `count` equal side-by-side columns, filling each top to bottom
806	/// before hopping to the next, and breaking to a fresh page's first column when the last column fills.
807	/// This is the same greedy, atom-aware breaker the page body uses (see [`compose`]) run once per column:
808	/// a page is a one-column flow, and this is its generalisation, so the two share the page-close and
809	/// float-flush helpers ([`finish_page`], [`flush_floats`]) rather than re-implementing the page break.
810	/// Sequential fill, never balancing, matches Typst's `columns(n)` -- the last column of the last page
811	/// simply ends where the material runs out.
812	///
813	/// The block begins at the incoming cursor `*y` (below whatever body already sits on the page) and every
814	/// column of that first page starts at the same top; a fresh page opened mid-block starts its columns at
815	/// the region top below any top floats a flush seats. On return `*y` sits at the foot of the tallest
816	/// column of the block's last page, so the ordinary flow resumes there. Two-pass resolution is untouched:
817	/// an anchor -- an index entry's reserved folio slot, or a `Node::Anchor` -- records its x at the column
818	/// left, and the reserved slot resolves against the incoming ledger exactly as it does in the body flow.
819	#[allow(clippy::too_many_arguments)]
820	fn flow_columns<M: Metrics>(
821	cols: &ColumnsNode,
822	pages: &mut Vec<Page>,
823	frame: &mut Frame,
824	page_no: &mut u32,
825	y: &mut Sp,
826	top: Sp,
827	bottom: Sp,
828	geom: PageGeometry,
829	notes: &mut Vec<Footnote>,
830	foot: &FootStyle,
831	bands: &mut FloatBands,
832	pending: &mut Vec<FloatNode>,
833	at_top: &mut bool,
834	metrics: &M,
835	incoming: &Ledger,
836	ledger: &mut Ledger,
837	)
838	-> Outcome<()>
839	{
840	let n = cols.count.max(1);
841	let list = &cols.list;
842
843	let mut col = 0usize; // the column being filled
844	let mut col_top = *y; // the y every column of the current page starts at
845	let mut yy = col_top; // the cursor within the current column
846	let mut deepest = col_top; // the deepest column foot reached on the current page, for the resume
847	let mut at_col_top = true; // just after a column or page break, leading glue is discarded
848	let mut at_break = true; // a break (a column or page hop) is permitted at the cursor
849	let mut prev_box = false; // the last non-marker node was a box, so glue after it may break
850
851	let mut idx = 0usize;
852	while idx < list.len() {
853	match &list[idx] {
854	Node::Glue(g) => {
855	if !at_col_top {
856	yy += g.natural;
857	}
858	if prev_box {
859	at_break = true;
860	}
861	prev_box = false;
862	},
863	Node::Penalty(p) => {
864	// A forced penalty breaks the column here (Typst's `colbreak`): hop to the next column, or to a
865	// fresh page's first column when the last column is full. A forbidden penalty welds across the
866	// break; any other penalty is an ordinary breakpoint.
867	if p.is_forced() {
868	res!(column_hop(
869	&mut col, n, &mut yy, &mut col_top, &mut deepest, &mut at_col_top, pages, frame, page_no,
870	y, top, bottom, geom, notes, foot, bands, pending, metrics, incoming, ledger));
871	at_break = true;
872	} else if p.is_forbidden() {
873	at_break = false;
874	} else {
875	at_break = true;
876	}
877	prev_box = false;
878	},
879	Node::Anchor(id) => {
880	let col_geom = geom.column_slice(col, n, cols.gutter);
881	ledger.record(Anchor::new(id.clone(), Position::new(*page_no, col_geom.content_left(), yy)));
882	},
883	node @ (Node::HBox(_) \| Node::VBox(_) \| Node::Leaf(_)) => {
884	if at_break {
885	let (atom_ext, atom_reserve) = atom_measure(list, idx, notes, foot);
886	let col_bottom = bottom - bands.bot_reserve - atom_reserve;
887	// Guard on `!(at_col_top && frame.is_empty())`, not `!at_col_top`: the body breaks whenever the
888	// frame is non-empty, and keying only on the column top diverged -- at a page foot the first atom
889	// of column 0 and then of column 1 both seated below the bottom before any page break, since each
890	// fresh column reads `at_col_top` true. This seats an over-tall atom only on a genuinely empty page
891	// (no spin), and otherwise hops or page-breaks so nothing lands past the foot.
892	if !(at_col_top && frame.is_empty()) && yy + atom_ext > col_bottom {
893	res!(column_hop(
894	&mut col, n, &mut yy, &mut col_top, &mut deepest, &mut at_col_top, pages, frame, page_no,
895	y, top, bottom, geom, notes, foot, bands, pending, metrics, incoming, ledger));
896	continue; // weigh the same atom against the fresh column, without advancing idx
897	}
898	}
899	let col_geom = geom.column_slice(col, n, cols.gutter);
900	let v = node.vextent();
901	let mut marks: Vec<Footnote> = Vec::new();
902	collect_marks(node, &mut marks);
903	res!(place_node(node, yy, *page_no, col_geom, metrics, incoming, frame, ledger));
904	notes.append(&mut marks); // a note introduced in a column belongs to the page the column is on
905	yy += v;
906	if yy > deepest {
907	deepest = yy;
908	}
909	at_col_top = false;
910	at_break = false;
911	prev_box = true;
912	},
913	// A repeated-header marker never carries vertical extent and never opens or closes an atom, so a
914	// columns block that happened to enclose one just passes it through untouched.
915	Node::RepeatHead(_) => (),
916	// A float or a nested columns block inside a columns block is a construction error the parser never
917	// builds. It is refused loudly rather than silently dropped, keeping the project's loud-refusal
918	// stance: reaching here means the lowering built an impossible shape, which is a bug to surface.
919	Node::Float(_) \| Node::Columns(_) \| Node::PageColumns(_) => return Err(err!(
920	"A float, a nested columns block or a page-column marker was found inside a columns block's \
921	list, which the lowering never builds; this is a construction bug in the caller that assembled \
922	the columns node."; Invalid, Bug)),
923	}
924	idx += 1;
925	}
926
927	// The flow resumes below the tallest column of the block's last page. A block that placed nothing leaves
928	// the cursor and the page's `at_top` where they were.
929	*y = deepest;
930	if deepest > col_top {
931	*at_top = false;
932	}
933	Ok(())
934	}
935
936	/// Advances a columns flow to the next column, or -- when the last column is full -- closes the page,
937	/// flushes any pending floats onto the fresh page, and restarts at its first column. The flow's cursors
938	/// (`col`, `yy`, `col_top`, `deepest`, `at_col_top`) are reset in place for the column or page just
939	/// opened; on a page break the page-body state (`pages`, `frame`, `page_no`, `y`, `bands`, `notes`) is
940	/// carried through the same [`finish_page`]/[`flush_floats`] helpers the body flow uses, and the new
941	/// column top is taken from the shared cursor below any top band the flush stacked.
942	#[allow(clippy::too_many_arguments)]
943	fn column_hop<M: Metrics>(
944	col: &mut usize,
945	n: usize,
946	yy: &mut Sp,
947	col_top: &mut Sp,
948	deepest: &mut Sp,
949	at_col_top: &mut bool,
950	pages: &mut Vec<Page>,
951	frame: &mut Frame,
952	page_no: &mut u32,
953	y: &mut Sp,
954	top: Sp,
955	bottom: Sp,
956	geom: PageGeometry,
957	notes: &mut Vec<Footnote>,
958	foot: &FootStyle,
959	bands: &mut FloatBands,
960	pending: &mut Vec<FloatNode>,
961	metrics: &M,
962	incoming: &Ledger,
963	ledger: &mut Ledger,
964	)
965	-> Outcome<()>
966	{
967	if *col + 1 < n {
968	// Another column on this page: the same top, a fresh cursor.
969	*col += 1;
970	yy = col_top;
971	*at_col_top = true;
972	} else {
973	// The last column is full: close the page (its footnotes set at the foot), reset the float bands, and
974	// flush any deferred floats onto the fresh page, then restart at column 0 below whatever top band the
975	// flush stacked. The resume tracker restarts from the new page's column top.
976	res!(finish_page(
977	pages, frame, page_no, y, top, geom, notes, foot, bottom, bands.bot_reserve, metrics, incoming, ledger));
978	*bands = FloatBands::empty();
979	res!(flush_floats(
980	pending, frame, y, bands, Sp::ZERO, *page_no, geom, top, bottom, metrics, incoming, ledger));
981	*col = 0;
982	col_top = y; // finish_page reset y to the region top; flush_floats advanced it past any top floats
983	yy = col_top;
984	deepest = col_top;
985	*at_col_top = true;
986	}
987	Ok(())
988	}
989
990	/// Closes the current page: sets its footnotes at the foot, stores it, clears the note accumulator, and
991	/// resets the frame and cursor before advancing the folio.
992	#[allow(clippy::too_many_arguments)]
993	fn finish_page<M: Metrics>(
994	pages: &mut Vec<Page>,
995	frame: &mut Frame,
996	page_no: &mut u32,
997	y: &mut Sp,
998	top: Sp,
999	geom: PageGeometry,
1000	notes: &mut Vec<Footnote>,
1001	foot: &FootStyle,
1002	bottom: Sp,
1003	bot_reserve: Sp, // height a foot float claimed on this page; footnotes sit above it
1004	metrics: &M,
1005	incoming: &Ledger,
1006	ledger: &mut Ledger,
1007	)
1008	-> Outcome<()>
1009	{
1010	res!(lay_footnotes(frame, notes, *page_no, geom, foot, bottom - bot_reserve, metrics, incoming, ledger));
1011	pages.push(Page::new(*page_no, geom, std::mem::take(frame)));
1012	notes.clear();
1013	*page_no += 1;
1014	*y = top;
1015	Ok(())
1016	}
1017
1018	/// The side an `auto` float settles on: Typst's midpoint rule. `used` is the region height already
1019	/// consumed, `need` the float's height plus its clearance, `base` the full page-text height. The float
1020	/// goes to the top when its own midpoint (`used + need/2`) would fall in the upper half of the page were
1021	/// it set in the flow, and to the foot otherwise. Computed in i64 so a full page's scaled points cannot
1022	/// overflow the doubling.
1023	fn auto_side(used: Sp, need: Sp, base: Sp) -> FloatPlacement {
1024	let lhs = (used.raw() as i64) * 2 + (need.raw() as i64);
1025	if lhs <= base.raw() as i64 {
1026	FloatPlacement::Top
1027	} else {
1028	FloatPlacement::Bottom
1029	}
1030	}
1031
1032	/// Sets a float's material as a small vertical list from `y_top`: each child placed like a keep box's, and
1033	/// the float's own [`Float`](crate::ledger::AnchorKind::Float) anchor recorded at the y it reaches, so a
1034	/// cross-reference resolves the page and position it settled on. The material carries no framing glue --
1035	/// the caller lays the clearance around it -- so this places the list as it stands.
1036	fn place_float<M: Metrics>(
1037	f: &FloatNode,
1038	y_top: Sp,
1039	page_no: u32,
1040	geom: PageGeometry,
1041	metrics: &M,
1042	incoming: &Ledger,
1043	frame: &mut Frame,
1044	ledger: &mut Ledger,
1045	region: Region, // the band the float lands in; every anchor recorded while its material is laid inherits it
1046	)
1047	-> Outcome<()>
1048	{
1049	// Every anchor recorded from here on -- the float's own direct `Node::Anchor`, and any nested through
1050	// `place_line`, `place_vbox` or `place_leaf` (a margin note, claim label, ref or index entry inside the
1051	// float's body) -- claims this float's band, restored once its material is laid. Membership is decided
1052	// here, at the one place that knows a float's material is being laid, rather than at each helper that
1053	// happens to record an anchor.
1054	let prev_region = ledger.enter_region(region);
1055	let mut yy = y_top;
1056	for child in &f.list {
1057	match child {
1058	Node::Glue(g) => {
1059	yy += g.natural;
1060	},
1061	Node::HBox(b) => {
1062	res!(place_line(b, yy, page_no, geom, metrics, incoming, frame, ledger));
1063	yy += b.dims.vextent();
1064	},
1065	Node::VBox(b) => {
1066	res!(place_vbox(b, yy, page_no, geom, metrics, incoming, frame, ledger));
1067	yy += b.dims.vextent();
1068	},
1069	Node::Leaf(l) => {
1070	res!(place_leaf(l, geom.content_left(), yy, page_no, metrics, incoming, frame, ledger));
1071	yy += l.dims.vextent();
1072	},
1073	Node::Anchor(id) => {
1074	ledger.record(Anchor::new(id.clone(), Position::new(page_no, geom.content_left(), yy)));
1075	},
1076	Node::Penalty(_) => (),
1077	// A float never nests inside another float; a nested one would be a construction error, so it is
1078	// left unplaced rather than silently flattened.
1079	Node::Float(_) => (),
1080	// A columns block is only ever a top-level document node; one nested in a float's body would be a
1081	// construction error, so it draws nothing rather than being flattened here.
1082	Node::Columns(_) => (),
1083	// A repeated-header marker and a page-column marker are top-level control nodes; one in a float's
1084	// body is a construction error the lowering never builds, so it is passed over rather than flattened.
1085	Node::RepeatHead(_) \| Node::PageColumns(_) => (),
1086	}
1087	}
1088	ledger.leave_region(prev_region);
1089	Ok(())
1090	}
1091
1092	/// A page's float bands: the top band already stacked (top floats plus their clearances) and the foot band
1093	/// already reserved (foot floats plus their clearances). The body fills what is left between them.
1094	#[derive(Clone, Copy, Debug)]
1095	struct FloatBands {
1096	top_used: Sp,
1097	bot_reserve: Sp,
1098	}
1099
1100	impl FloatBands {
1101	fn empty() -> Self { Self { top_used: Sp::ZERO, bot_reserve: Sp::ZERO } }
1102	}
1103
1104	/// Inserts one float into the current page's top or foot region by Typst's rule, shifting the body (a top
1105	/// float) or the existing foot band (a foot float) to make room -- Typst re-flows the region on a float
1106	/// insertion; this shifts only what moved. `clearance_flag` is whether the clearance counts in the FIT and
1107	/// midpoint budget: Typst sets it only when the page already carries flow content, and a re-queued float is
1108	/// re-processed with it false. The clearance is ALWAYS laid in the band, per Typst's finalize. `force`
1109	/// seats the float even when it will not fit (an empty page's front float, which overflows rather than
1110	/// deferring forever). `foot_now` is the footnote furniture already reserved, so a float never lands over
1111	/// the notes. Returns `true` when placed, `false` when it does not fit and `force` is unset.
1112	#[allow(clippy::too_many_arguments)]
1113	fn try_insert_float<M: Metrics>(
1114	f: &FloatNode,
1115	clearance_flag: bool,
1116	force: bool,
1117	y: &mut Sp,
1118	bands: &mut FloatBands,
1119	foot_now: Sp,
1120	page_no: u32,
1121	geom: PageGeometry,
1122	top: Sp,
1123	bottom: Sp,
1124	metrics: &M,
1125	incoming: &Ledger,
1126	frame: &mut Frame,
1127	ledger: &mut Ledger,
1128	)
1129	-> Outcome<bool>
1130	{
1131	let base = geom.content_height();
1132	let band = f.height + f.clearance; // finalize always lays the clearance
1133	let need_fit = f.height + if clearance_flag { f.clearance } else { Sp::ZERO };
1134	let remaining = (bottom - bands.bot_reserve - foot_now) - *y;
1135	if need_fit > remaining && !force {
1136	return Ok(false);
1137	}
1138	let used = base - remaining;
1139	let side = match f.placement {
1140	FloatPlacement::Top => FloatPlacement::Top,
1141	FloatPlacement::Bottom => FloatPlacement::Bottom,
1142	FloatPlacement::Auto => auto_side(used, need_fit, base),
1143	};
1144	match side {
1145	FloatPlacement::Bottom => {
1146	// Shift the existing foot band up by this float's band and seat the new float at the very foot,
1147	// so document order runs top-to-bottom down the foot region (the earliest foot float highest). The
1148	// body and top regions stay put; the float's own material is stamped into the foot band after it is
1149	// placed (`place_float` lays it as ordinary body material first).
1150	let start = frame.len();
1151	frame.shift_region(-band, Region::Foot);
1152	ledger.shift_region_anchors(page_no, -band, Region::Foot);
1153	res!(place_float(f, bottom - f.height, page_no, geom, metrics, incoming, frame, ledger, Region::Foot));
1154	frame.stamp_region(start, Region::Foot);
1155	bands.bot_reserve = bands.bot_reserve + band;
1156	},
1157	// Top (auto resolved to top or bottom above, so this arm is top).
1158	_ => {
1159	// Seat the float below the top band already stacked and shift the whole body region down, so
1160	// document order runs top-to-bottom down the top region (the earliest top float highest). Shifting
1161	// by region, not by a y window, moves a first body line that cap-height seating raised above the
1162	// band edge along with the rest of its body -- keying on the raised glyph y would strand it under
1163	// the float. The float's own material is stamped into the top band after it is placed.
1164	let at = top + bands.top_used;
1165	let start = frame.len();
1166	frame.shift_region(band, Region::Body);
1167	ledger.shift_region_anchors(page_no, band, Region::Body);
1168	res!(place_float(f, at, page_no, geom, metrics, incoming, frame, ledger, Region::Top));
1169	frame.stamp_region(start, Region::Top);
1170	bands.top_used = bands.top_used + band;
1171	*y += band;
1172	},
1173	}
1174	Ok(true)
1175	}
1176
1177	/// Sets the queued floats that fit on the current page, in document order, updating its [`FloatBands`].
1178	/// A queued float is re-processed with `clearance_flag` false (Typst's relayout does the same); the front
1179	/// float of an empty page is seated even when it will not fit, so the queue always drains, and flushing
1180	/// stops at the first float that will not fit so a float never jumps ahead of an earlier one. `foot_now` is
1181	/// the footnote furniture already on the page (zero on a freshly opened one), so a float never lands over
1182	/// the notes -- the end-of-document drain calls this on a part-filled page and must respect them.
1183	#[allow(clippy::too_many_arguments)]
1184	fn flush_floats<M: Metrics>(
1185	pending: &mut Vec<FloatNode>,
1186	frame: &mut Frame,
1187	y: &mut Sp,
1188	bands: &mut FloatBands,
1189	foot_now: Sp,
1190	page_no: u32,
1191	geom: PageGeometry,
1192	top: Sp,
1193	bottom: Sp,
1194	metrics: &M,
1195	incoming: &Ledger,
1196	ledger: &mut Ledger,
1197	)
1198	-> Outcome<()>
1199	{
1200	let mut placed_any = false;
1201	while !pending.is_empty() {
1202	let force = frame.is_empty() && !placed_any;
1203	let f = pending[0].clone();
1204	let ok = res!(try_insert_float(
1205	&f, false, force, y, bands, foot_now, page_no, geom, top, bottom, metrics, incoming, frame, ledger));
1206	if ok {
1207	pending.remove(0);
1208	placed_any = true;
1209	} else {
1210	break;
1211	}
1212	}
1213	Ok(())
1214	}
1215
1216	/// Dispatches a node to the placement helper for its shape. The break decision is the caller's; this
1217	/// only lays the node's ink at `y` on `page_no`.
1218	fn place_node<M: Metrics>(
1219	node: &Node,
1220	y: Sp,
1221	page_no: u32,
1222	geom: PageGeometry,
1223	metrics: &M,
1224	incoming: &Ledger,
1225	frame: &mut Frame,
1226	ledger: &mut Ledger,
1227	)
1228	-> Outcome<()>
1229	{
1230	match node {
1231	// A keep box (a heading bound to the first line of its paragraph) is placed whole, so the greedy
1232	// breaker moves it entire rather than splitting it.
1233	Node::VBox(b) => place_vbox(b, y, page_no, geom, metrics, incoming, frame, ledger),
1234	Node::HBox(b) => place_line(b, y, page_no, geom, metrics, incoming, frame, ledger),
1235	Node::Leaf(l) => place_leaf(l, geom.content_left(), y, page_no, metrics, incoming, frame, ledger).map(\|_\| ()),
1236	_ => Ok(()),
1237	}
1238	}
1239
1240	/// Weighs the atom beginning at `start`: the boxes from there up to the next legal page breakpoint, their
1241	/// stacked vertical extent, and the footnotes they introduce (as a foot reservation, `notes` being the
1242	/// page's existing notes). A break is legal at glue that follows a box, and at a non-forbidden penalty; a
1243	/// forbidden penalty (the widow/orphan weld set by [`doc::guard_widows`](crate::doc)) blocks the break and
1244	/// welds the boxes either side of it into the one atom. Anchors and floats are transparent, taking no
1245	/// extent and neither opening nor closing the atom. The caller checks this extent against the room left on
1246	/// the page and breaks before the atom rather than splitting a line off it.
1247	fn atom_measure(nodes: &[Node], start: usize, notes: &[Footnote], foot: &FootStyle) -> (Sp, Sp) {
1248	let mut ext = Sp::ZERO;
1249	let mut marks: Vec<Footnote> = Vec::new();
1250	let mut prev_box = false;
1251	let mut j = start;
1252	while j < nodes.len() {
1253	match &nodes[j] {
1254	Node::Glue(g) => {
1255	if prev_box {
1256	break; // glue after a box: the atom's first legal breakpoint
1257	}
1258	ext += g.natural; // interior glue (after a forbidden penalty) is part of the atom
1259	prev_box = false;
1260	},
1261	Node::Penalty(p) => {
1262	if p.is_forced() {
1263	break;
1264	}
1265	if p.is_forbidden() {
1266	prev_box = false; // the weld: the atom continues across it
1267	} else {
1268	break; // a non-forbidden penalty is a legal breakpoint
1269	}
1270	},
1271	Node::HBox(_) \| Node::VBox(_) \| Node::Leaf(_) => {
1272	ext += nodes[j].vextent();
1273	collect_marks(&nodes[j], &mut marks);
1274	prev_box = true;
1275	},
1276	// Transparent to the atom: none opens or closes it, and a repeated-header marker carries no extent.
1277	Node::Anchor(_) \| Node::Float(_) \| Node::Columns(_) \| Node::RepeatHead(_) \| Node::PageColumns(_) => (),
1278	}
1279	j += 1;
1280	}
1281	(ext, foot_reserve(notes, &marks, foot))
1282	}
1283
1284	/// Gathers the footnotes whose marks fall anywhere within `node`, in the document order they were set,
1285	/// by walking its boxes. A mark is a [`LeafKind::Mark`] leaf; the note it carries is what the page
1286	/// breaker reserves foot space for and what the closing page sets at its foot.
1287	fn collect_marks(node: &Node, out: &mut Vec<Footnote>) {
1288	match node {
1289	Node::HBox(b) \| Node::VBox(b) => for child in &b.list { collect_marks(child, out); },
1290	Node::Leaf(l) => if let LeafKind::Mark(f) = &l.kind { out.push(f.clone()); },
1291	_ => (),
1292	}
1293	}
1294
1295	/// The height a set of footnotes takes at the foot: the separator furniture, the notes' own stacked
1296	/// heights, and the gaps between them. Zero when there are none, so a page with no footnote keeps the
1297	/// whole body height. `existing` are the page's notes already; `extra` are a candidate line's, weighed
1298	/// in so a line and its own note are judged against the same page together.
1299	fn foot_reserve(existing: &[Footnote], extra: &[Footnote], foot: &FootStyle) -> Sp {
1300	let n = existing.len() + extra.len();
1301	if n == 0 {
1302	return Sp::ZERO;
1303	}
1304	let mut h = Sp::ZERO;
1305	for f in existing.iter().chain(extra.iter()) {
1306	h += f.height;
1307	}
1308	foot.gap_above_rule + foot.rule_thick + foot.gap_below_rule + h + foot.gap_between * (n as i32 - 1)
1309	}
1310
1311	/// Sets a page's accumulated footnotes at its foot: a short separator rule, then each note as the small
1312	/// paragraph it was set into, seated so the whole block's foot meets the bottom of the text block, above
1313	/// the folio. The block's height is exactly [`foot_reserve`]'s, so the body above it -- placed against a
1314	/// bottom shrunk by that same amount -- never collides with it.
1315	#[allow(clippy::too_many_arguments)]
1316	fn lay_footnotes<M: Metrics>(
1317	frame: &mut Frame,
1318	notes: &[Footnote],
1319	page_no: u32,
1320	geom: PageGeometry,
1321	foot: &FootStyle,
1322	bottom: Sp,
1323	metrics: &M,
1324	incoming: &Ledger,
1325	ledger: &mut Ledger,
1326	)
1327	-> Outcome<()>
1328	{
1329	if notes.is_empty() {
1330	return Ok(());
1331	}
1332	let total = foot_reserve(notes, &[], foot);
1333	let mut yy = bottom - total;
1334
1335	yy += foot.gap_above_rule;
1336	frame.push(Placed::new(
1337	geom.content_left(), yy, Dims::new(foot.rule_width, foot.rule_thick, Sp::ZERO), PlacedKind::Rule));
1338	yy = yy + foot.rule_thick + foot.gap_below_rule;
1339
1340	for (i, f) in notes.iter().enumerate() {
1341	for child in &f.note {
1342	match child {
1343	Node::HBox(b) => {
1344	res!(place_line(b, yy, page_no, geom, metrics, incoming, frame, ledger));
1345	yy += b.dims.vextent();
1346	},
1347	Node::Glue(g) => {
1348	yy += g.natural;
1349	},
1350	_ => (),
1351	}
1352	}
1353	if i + 1 < notes.len() {
1354	yy += foot.gap_between;
1355	}
1356	}
1357	Ok(())
1358	}
1359
1360	/// Lays one horizontal box -- a line -- left to right, placing each child and recording any anchor
1361	/// or forward reference it carries. Nested boxes are placed as their own rectangle in Phase 0;
1362	/// shaping their contents is Phase 1.
1363	fn place_line<M: Metrics>(
1364	line: &BoxNode,
1365	y: Sp,
1366	page_no: u32,
1367	geom: PageGeometry,
1368	metrics: &M,
1369	incoming: &Ledger,
1370	frame: &mut Frame,
1371	ledger: &mut Ledger,
1372	)
1373	-> Outcome<()>
1374	{
1375	let mut x = geom.content_left();
1376	for child in &line.list {
1377	match child {
1378	Node::Leaf(l) => {
1379	x = res!(place_leaf(l, x, y, page_no, metrics, incoming, frame, ledger));
1380	},
1381	Node::Glue(g) => {
1382	x += g.natural;
1383	},
1384	Node::Anchor(id) => {
1385	ledger.record(Anchor::new(id.clone(), Position::new(page_no, x, y)));
1386	},
1387	Node::Penalty(_) => {
1388	// A line arrives here already broken: `linebreak::break_paragraph` runs the Knuth-Plass
1389	// optimiser upstream and hands the driver finished HBox lines of words and justified
1390	// glue. A penalty inside such a line would be a later intra-line refinement (a kept
1391	// discretionary break), which Phase 1 does not yet place, so there is nothing to weigh.
1392	},
1393	Node::HBox(b) \| Node::VBox(b) => {
1394	frame.push(Placed::new(x, y, b.dims, PlacedKind::Rule));
1395	x += b.dims.width;
1396	},
1397	// A float is a block-level node the driver handles before it ever reaches a line; one woven into a
1398	// line would be a construction error, so it draws nothing rather than being flattened here.
1399	Node::Float(_) => (),
1400	// A columns block is a top-level node; one woven into a line would be a construction error, so it
1401	// draws nothing rather than being flattened here.
1402	Node::Columns(_) => (),
1403	// A repeated-header or page-column marker is a top-level control node; nested here it is a
1404	// construction error the lowering never builds, so it is passed over rather than flattened.
1405	Node::RepeatHead(_) \| Node::PageColumns(_) => (),
1406	}
1407	}
1408	Ok(())
1409	}
1410
1411	/// Sets a vertical keep box: its children stacked from the box top, each at the content left. Lines
1412	/// are placed, glue advances the cursor, and an anchor is recorded at the y it reaches -- so a
1413	/// heading's anchor takes the page and position the box settled on, never a provisional one from
1414	/// before the box was moved to fit.
1415	fn place_vbox<M: Metrics>(
1416	vbox: &BoxNode,
1417	y_top: Sp,
1418	page_no: u32,
1419	geom: PageGeometry,
1420	metrics: &M,
1421	incoming: &Ledger,
1422	frame: &mut Frame,
1423	ledger: &mut Ledger,
1424	)
1425	-> Outcome<()>
1426	{
1427	let mut yy = y_top;
1428	for child in &vbox.list {
1429	match child {
1430	Node::HBox(b) => {
1431	res!(place_line(b, yy, page_no, geom, metrics, incoming, frame, ledger));
1432	yy += b.dims.vextent();
1433	},
1434	Node::VBox(b) => {
1435	res!(place_vbox(b, yy, page_no, geom, metrics, incoming, frame, ledger));
1436	yy += b.dims.vextent();
1437	},
1438	Node::Leaf(l) => {
1439	res!(place_leaf(l, geom.content_left(), yy, page_no, metrics, incoming, frame, ledger));
1440	yy += l.dims.vextent();
1441	},
1442	Node::Glue(g) => {
1443	yy += g.natural;
1444	},
1445	Node::Anchor(id) => {
1446	ledger.record(Anchor::new(id.clone(), Position::new(page_no, geom.content_left(), yy)));
1447	},
1448	Node::Penalty(_) => (),
1449	// A float never nests inside a keep box; one that did would be a construction error, so it draws
1450	// nothing rather than being flattened into the box.
1451	Node::Float(_) => (),
1452	// A columns block never nests inside a keep box; one that did would be a construction error, so it
1453	// draws nothing rather than being flattened into the box.
1454	Node::Columns(_) => (),
1455	// A repeated-header or page-column marker is a top-level control node; nested here it is a
1456	// construction error the lowering never builds, so it is passed over rather than flattened.
1457	Node::RepeatHead(_) \| Node::PageColumns(_) => (),
1458	}
1459	}
1460	Ok(())
1461	}
1462
1463	/// Places one leaf at `(x, y)` and returns the x the next child starts at. A rule is drawn as it
1464	/// stands. A forward reference reserves a slot: the width it needs for the value resolved from the
1465	/// previous pass, never less than the width the author declared. When the resolved value outgrows
1466	/// the declared reservation the slot grows to fit it, which shifts everything after it -- the honest
1467	/// cause of a further pass, recorded on the anchor as an overflow.
1468	fn place_leaf<M: Metrics>(
1469	leaf: &Leaf,
1470	x: Sp,
1471	y: Sp,
1472	page_no: u32,
1473	metrics: &M,
1474	incoming: &Ledger,
1475	frame: &mut Frame,
1476	ledger: &mut Ledger,
1477	)
1478	-> Outcome<Sp>
1479	{
1480	// The leaf's own vertical shift moves its ink off the line's baseline without a nested box -- a
1481	// maths script raised, a fraction's numerator lifted and its bar seated on the axis. The x advance
1482	// is unaffected, so the horizontal cursor the caller tracks is untouched.
1483	let y = y + leaf.shift;
1484	match &leaf.kind {
1485	LeafKind::Rule => {
1486	frame.push(Placed::new(x, y, leaf.dims, PlacedKind::Rule));
1487	Ok(x + leaf.dims.width)
1488	},
1489	LeafKind::Text(shaped) => {
1490	// Already shaped and measured; place it and advance by its width. The writer reads the run
1491	// back out of the frame to draw the glyphs.
1492	frame.push(Placed::new(x, y, leaf.dims, PlacedKind::Text(shaped.clone())));
1493	Ok(x + leaf.dims.width)
1494	},
1495	LeafKind::Mark(footnote) => {
1496	// The superscript number is drawn like any run; its raised dims put the baseline above the
1497	// line's. The note it carries is set at the page foot by the breaker, not here.
1498	frame.push(Placed::new(x, y, leaf.dims, PlacedKind::Text(footnote.mark.clone())));
1499	Ok(x + leaf.dims.width)
1500	},
1501	LeafKind::Graphic(g) => {
1502	// A figure placed whole: its ops are translated to this position and drawn by the emitter.
1503	frame.push(Placed::new(x, y, leaf.dims, PlacedKind::Graphic(g.clone())));
1504	Ok(x + leaf.dims.width)
1505	},
1506	LeafKind::Reserved(id, refr, hold, bold) => {
1507	// A forward reference. What it resolves to is the reference's own business (a total count, a
1508	// cross-referenced page); the driver only asks the previous pass's ledger for the value and
1509	// holds the declared width open until it has one.
1510	let reserved = leaf.dims.width;
1511	let (realised, resolved) = match refr.resolve_text(incoming) {
1512	Some(text) => {
1513	// The previous pass fixed the value. Shape it as real text when a font backs the
1514	// metric, or keep the reservation box under the fontless stub; either way its realised
1515	// width is recorded so the overflow logic still governs a further pass. A main index
1516	// reference's folio (`bold`) shapes in the bold face, reproducing in-dexter's strong-set
1517	// main page number.
1518	let shaped = if *bold { res!(metrics.shape_bold(&text)) } else { res!(metrics.shape(&text)) };
1519	match shaped {
1520	Some(shaped) => {
1521	let w = shaped.dims().width;
1522	let dims = Dims::new(w, leaf.dims.height, leaf.dims.depth);
1523	frame.push(Placed::new(x, y, dims, PlacedKind::Text(shaped)));
1524	(w, true)
1525	},
1526	None => {
1527	frame.push(Placed::new(x, y, leaf.dims, PlacedKind::Reserved));
1528	(res!(metrics.measure(&text)).width, true)
1529	},
1530	}
1531	},
1532	None => {
1533	// Pass A: no value yet. Hold the reservation open and realise nothing, so no overflow
1534	// is charged before there is a value that could exceed the width.
1535	frame.push(Placed::new(x, y, leaf.dims, PlacedKind::Reserved));
1536	(Sp::ZERO, false)
1537	},
1538	};
1539
1540	// A value wider than its reservation always grows the slot -- the honest cause of a further
1541	// pass, charged as the anchor's overflow. Within the reservation, furniture (`hold`) keeps the
1542	// declared width so a right-aligned column stays put, while an inline reference shrinks to the
1543	// resolved value so it reads without a gap; a still-unresolved slot keeps its reservation.
1544	let slot = if realised > reserved {
1545	realised
1546	} else if *hold \|\| !resolved {
1547	reserved
1548	} else {
1549	realised
1550	};
1551	let mut anchor = Anchor::new(id.clone(), Position::new(page_no, x, y));
1552	anchor.reserved = reserved;
1553	anchor.realised = realised;
1554	ledger.record(anchor);
1555	Ok(x + slot)
1556	},
1557	}
1558	}
1559
1560	/// Builds the non-convergence error: the ledger difference the architecture promises, naming the
1561	/// anchor that moved and the pages it moved between, plus any reference that overflowed its
1562	/// reservation.
1563	fn non_convergence(
1564	pass: u32,
1565	ledger: &Ledger,
1566	prev: &Ledger,
1567	)
1568	-> Error<ErrTag>
1569	{
1570	let deltas = ledger.diff(prev);
1571	let overflows = ledger.overflowed();
1572
1573	let mut moved = String::new();
1574	for d in &deltas {
1575	moved.push_str(&fmt!(" [{:?} {} moved p{}->p{}]", d.id.kind, d.id.key, d.from, d.to));
1576	}
1577	let mut over = String::new();
1578	for id in &overflows {
1579	over.push_str(&fmt!(" [{:?} {} overflowed its reservation]", id.kind, id.key));
1580	}
1581	err!(
1582	"Composition did not converge after {} passes; the ledger is still moving. Moved anchors:{}. \
1583	Reservations exceeded:{}.", pass, moved, over;
1584	Data, Excessive, LimitReached)
1585	}