Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/flow/block.rs

119 KiB, 292 runs

created by r1870400018:63518, 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// SPDX-License-Identifier: Apache-2.0
2// Original work copyright (c) the Typst project authors (typst-layout `flow/*`, `pad.rs` and `stack.rs`, version 0.15.1).
3// Modified for Austenite: ported to Hematite's types, IR and error handling.
4// U6b owns this file: block-level flow -- block, pad, align, stack, v with fr, place (float and parent
5// scope), columns and colbreak -- dispatching inline runs to `par` and atoms to `grid`, `visual`, `math`.
6//
7// A port of Typst 0.15.1's `typst-layout` flow (`flow/{mod,collect,distribute,compose,block}.rs`, `pad.rs`,
8// `stack.rs`), Apache-2.0, (c) the Typst authors. Realised block-level pairs are collected into children
9// (spacing with a weakness, paragraph lines with their widow and orphan need, unbreakable and breakable
10// blocks, placed elements, breaks), distributed into one region at a time, and composed with the region's
11// insertions: floats at the top or foot of a column or of the whole page, and footnotes at the foot of a
12// column. A float or footnote that changes the space left relays the region out. Output is a `Frame`
13// per region, in points; `Frame::into_node` lowers it to an `ir::Node::Frame` the driver places.
14//
15// Everything Typst shows as a block -- a shape, an image, a transform, a grid, a pad, a stack, columns, a
16// block equation, `layout` -- is a block here too, whose width, spacing, fill and the rest come from the
17// `block` styles in force, as Typst's show rules make them `BlockElem`s.
18
19use crate::diag::DiagnosticKind;
20use crate::eval::content::{
21 Content,
22 ElemKind,
23 Family,
24};
25use crate::eval::lib::visual as vis;
26use crate::eval::locate::{
27 Location,
28 Locator,
29 Place,
30};
31use crate::eval::realise::{
32 self,
33 Pair,
34 Tag,
35};
36use crate::eval::styles::{
37 Property,
38 Style,
39 StyleChain,
40 Styles,
41};
42use crate::eval::value::{
43 Alignment,
44 Dict,
45 Direction,
46 HAlign,
47 Length,
48 Ratio,
49 Relative,
50 VAlign,
51 Value,
52};
53use crate::eval::{
54 Context,
55 Engine,
56};
57use crate::flow::carry;
58use crate::flow::grid::RowSplit;
59use crate::flow::inline::ParSituation;
60use crate::flow::page::Level;
61use crate::flow::text::{
62 elem_field,
63 link_target,
64};
65use crate::flow::Region;
66use crate::ir::{
67 BoxNode,
68 ClipNode,
69 Dims,
70 FrameNode,
71 Graphic,
72 Leaf,
73 LinkTarget,
74 Node,
75 Sp,
76 Transform,
77 TransformNode,
78};
79use crate::syntax::Span;
80
81use oxedyne_fe2o3_core::prelude::*;
82use oxedyne_fe2o3_graphics::path::Path;
83use oxedyne_fe2o3_hash::fingerprint::Fingerprint;
84use oxedyne_fe2o3_hash::fingerprint::Fingerprinter;
85
86use std::cell::RefCell;
87use std::collections::{
88 HashMap,
89 VecDeque,
90};
91use std::rc::Rc;
92
93// Entry points
94
95/// Lays block-level content out into one region, as Typst's `layout_frame`, and returns the frame as a
96/// one-node vertical list whose box is the frame's size.
97pub fn layout_flow(
98 engine: &mut Engine,
99 content: &Content,
100 styles: &StyleChain,
101 region: Region,
102)
103 -> Outcome<Vec<Node>>
104{
105 let frame = res!(layout_frame(engine, content, styles, Regions::from_region(region)));
106 let node = frame.into_node();
107 let dims = match &node {
108 Node::Frame(f) => Dims::new(f.dims.width, f.dims.vextent(), Sp::ZERO),
109 _ => Dims::default(),
110 };
111 Ok(vec![Node::VBox(BoxNode::new(vec![node], dims))])
112}
113
114/// `measure(content)`: the size content takes in the region, laid out and discarded. The whole height is
115/// `height` (and so `vextent`), with no depth.
116pub fn measure(
117 engine: &mut Engine,
118 content: &Content,
119 styles: &StyleChain,
120 region: Region,
121)
122 -> Outcome<Dims>
123{
124 let frame = res!(layout_frame(engine, content, styles, Regions::from_region(region)));
125 Ok(Dims::new(Sp::from_pt(frame.w), Sp::from_pt(frame.h), Sp::ZERO))
126}
127
128/// Lays content out into the first of `regions` alone, Typst's `layout_frame`.
129pub fn layout_frame(engine: &mut Engine, content: &Content, styles: &StyleChain, regions: Regions) -> Outcome<Frame> {
130 layout_frame_in(engine, None, content, styles, regions)
131}
132
133/// As [`layout_frame`], for the body of the element that holds `place`: the content is realised at that place
134/// whenever it is laid out, so a measurement and every later attempt locate what is in it alike.
135pub fn layout_frame_in(engine: &mut Engine, place: Option<Place>, content: &Content, styles: &StyleChain, regions: Regions)
136 -> Outcome<Frame>
137{
138 let one = Regions::one(regions.w, regions.h, regions.expand_x, regions.expand_y);
139 let mut frames = res!(layout_fragment_in(engine, place, content, styles, one));
140 Ok(match frames.is_empty() {
141 true => Frame::new(0.0, 0.0),
142 false => frames.swap_remove(0),
143 })
144}
145
146/// Lays content out into as many of `regions` as it needs, Typst's `layout_fragment`: realised one level,
147/// then flowed as blocks, or as the lines of one paragraph when the content is inline only.
148pub fn layout_fragment(engine: &mut Engine, content: &Content, styles: &StyleChain, regions: Regions) -> Outcome<Vec<Frame>> {
149 layout_fragment_in(engine, None, content, styles, regions)
150}
151
152/// As [`layout_fragment`], for the body of the element that holds `place`.
153pub fn layout_fragment_in(
154 engine: &mut Engine,
155 place: Option<Place>,
156 content: &Content,
157 styles: &StyleChain,
158 regions: Regions,
159)
160 -> Outcome<Vec<Frame>>
161{
162 engine.within(place, |engine| engine.descend_fragment(content.span(), |engine| {
163 let (pairs, inline) = res!(realise::realise_fragment(engine, content, styles));
164 let mode = if inline { FlowMode::Inline } else { FlowMode::Block };
165 layout_flow_pairs(engine, pairs, styles, regions, 1, Rel::zero(), mode, content.span())
166 }))
167}
168
169/// What a flow may hold: a page's root flow also hosts footnotes.
170#[derive(Clone, Copy, Debug, PartialEq, Eq)]
171pub enum FlowMode {
172 Root,
173 Block,
174 Inline,
175}
176
177/// Lays realised pairs out into regions, perhaps in columns: Typst's `layout_flow`, for a caller whose
178/// content is bounded. `regions` supplies every region the content may take, as a [`FlowCursor`] is drained
179/// through them.
180#[allow(clippy::too_many_arguments)]
181pub fn layout_flow_pairs(
182 engine: &mut Engine,
183 pairs: Vec<Pair>,
184 shared: &StyleChain,
185 mut regions: Regions,
186 columns: usize,
187 gutter: Rel,
188 mode: FlowMode,
189 span: Span,
190)
191 -> Outcome<Vec<Frame>>
192{
193 let mut cursor = res!(FlowCursor::new(engine, Feed::list(pairs), shared, &regions, columns, gutter, mode, span));
194 let mut finished = Vec::new();
195 loop {
196 finished.push(res!(cursor.region(engine, &regions)));
197 if res!(cursor.is_done(engine)) && (!regions.expand_y || regions.backlog.is_empty()) {
198 break;
199 }
200 regions.next();
201 }
202 Ok(finished)
203}
204
205// Feed
206
207/// Where a flow's realised pairs come from, in order.
208#[derive(Clone, Debug)]
209pub enum Feed {
210 List(Rc<Vec<Pair>>, usize), // pairs held whole, and the next to take
211 Run(Rc<RefCell<Level>>), // the open run of the paginator
212}
213
214impl Feed {
215 pub fn list(pairs: Vec<Pair>) -> Self { Feed::List(Rc::new(pairs), 0) }
216
217 fn next(&mut self, engine: &mut Engine) -> Outcome<Option<Pair>> {
218 match self {
219 Feed::List(pairs, at) => {
220 let p = pairs.get(*at).cloned();
221 if p.is_some() {
222 *at += 1;
223 }
224 Ok(p)
225 },
226 Feed::Run(level) => level.borrow_mut().pull(engine),
227 }
228 }
229
230 fn has_more(&mut self, engine: &mut Engine) -> Outcome<bool> {
231 match self {
232 Feed::List(pairs, at) => Ok(*at < pairs.len()),
233 Feed::Run(level) => level.borrow_mut().has_more(engine),
234 }
235 }
236}
237
238// Cursor
239
240/// What lazy collection reads from the flow's configuration: the size paragraphs are set against.
241#[derive(Clone, Copy, Debug)]
242pub(super) struct CollectCfg {
243 pub(super) width: f64,
244 pub(super) height: f64,
245 pub(super) expand: bool,
246}
247
248/// The children of a flow collected so far, and the feed they are collected from. A child is made when the
249/// composer first asks for it, so a paragraph is set into lines when the cursor reaches it; those before the
250/// first still needed are dropped.
251#[derive(Clone, Debug)]
252pub(super) struct Pull {
253 pub(super) feed: Feed,
254 pub(super) children: VecDeque<Rc<Child>>,
255 pub(super) base: usize, // the index of the first child held
256 pub(super) done: bool, // the feed has no more pairs
257 pub(super) pulled: usize, // pairs taken from the feed
258 pub(super) par: ParSituation, // where the flow stands for the next paragraph's first-line indent
259 pub(super) cfg: CollectCfg,
260 pub(super) mode: FlowMode,
261 pub(super) memo: Vec<Memo>,
262}
263
264impl Pull {
265 /// The child at `idx`, collecting from the feed as far as needed; none once the feed has run out.
266 fn get(&mut self, engine: &mut Engine, idx: usize) -> Outcome<Option<Rc<Child>>> {
267 if idx < self.base {
268 return Err(err!("Flow child {} was asked for after those before {} were dropped.", idx, self.base; Bug));
269 }
270 while idx >= self.base + self.children.len() {
271 if self.done {
272 return Ok(None);
273 }
274 let mut out = Vec::new();
275 if self.mode == FlowMode::Inline {
276 // A fragment that is inline only is one paragraph: all its pairs at once.
277 let mut pairs = Vec::new();
278 while let Some(p) = res!(self.feed.next(engine)) {
279 pairs.push(p);
280 }
281 self.done = true;
282 res!(collect_inline(engine, &pairs, self.cfg, &mut out));
283 } else {
284 let p = match res!(self.feed.next(engine)) {
285 Some(p) => p,
286 None => {
287 self.done = true;
288 return Ok(None);
289 },
290 };
291 if let Feed::Run(_) = self.feed {
292 // The root feed's pairs are what a page is made from; the probe notes each.
293 if let Some(t) = engine.timings.as_mut() {
294 t.see(carry::pair(&p));
295 }
296 }
297 let alone = self.pulled == 0 && !res!(self.feed.has_more(engine));
298 self.pulled += 1;
299 res!(collect_pair(engine, &p, alone, self.cfg, &mut self.par, &mut out));
300 }
301 self.children.extend(out.into_iter().map(Rc::new));
302 }
303 Ok(self.children.get(idx - self.base).cloned())
304 }
305
306 /// Drops the children before `idx`, which nothing will ask for again.
307 fn drop_before(&mut self, idx: usize) {
308 while self.base < idx && !self.children.is_empty() {
309 self.children.pop_front();
310 self.base += 1;
311 }
312 }
313}
314
315/// A flow laid out region by region: Typst's `layout_flow`, as a cursor. Each call to
316/// [`region`](Self::region) fills one region and keeps what remains, so a flow holds the children it has
317/// collected and not yet placed, and what waits for a later region, never its whole content.
318#[derive(Clone, Debug)]
319pub struct FlowCursor {
320 pub(super) config: Config,
321 pub(super) pull: Pull,
322 pub(super) work: Work,
323 pub(super) finished: bool,
324}
325
326impl FlowCursor {
327 /// A flow over `feed`, whose first region is `regions`. Columns, the gutter and the mode are the flow's
328 /// own; the size paragraphs are set against is taken from the first region.
329 #[allow(clippy::too_many_arguments)]
330 pub fn new(
331 engine: &mut Engine,
332 feed: Feed,
333 shared: &StyleChain,
334 regions: &Regions,
335 columns: usize,
336 gutter: Rel,
337 mode: FlowMode,
338 span: Span,
339 )
340 -> Outcome<Self>
341 {
342 if !regions.w.is_finite() && regions.expand_x {
343 return Err(engine.error(DiagnosticKind::Type, span, "cannot expand into infinite width"));
344 }
345 if !regions.h.is_finite() && regions.expand_y {
346 return Err(engine.error(DiagnosticKind::Type, span, "cannot expand into infinite height"));
347 }
348 let config = res!(configuration(shared, regions, columns, gutter, mode));
349 let cfg = CollectCfg { width: config.columns.width, height: regions.full, expand: regions.expand_x };
350 Ok(Self {
351 config,
352 pull: Pull {
353 feed, children: VecDeque::new(), base: 0, done: false, pulled: 0, par: ParSituation::First, cfg, mode,
354 memo: Vec::new(),
355 },
356 work: Work::new(),
357 finished: false,
358 })
359 }
360
361 /// The next region's frame, or none after the flow was finished by the one before.
362 pub fn next_region(&mut self, engine: &mut Engine, regions: &Regions) -> Outcome<Option<Frame>> {
363 if self.finished {
364 return Ok(None);
365 }
366 let frame = res!(self.region(engine, regions));
367 self.finished = res!(self.is_done(engine));
368 Ok(Some(frame))
369 }
370
371 /// Fills one region, whether or not anything is left: an empty frame is a region the flow spans after its
372 /// content has ended, as a block of fixed height does.
373 pub fn region(&mut self, engine: &mut Engine, regions: &Regions) -> Outcome<Frame> {
374 let frame = res!(compose(engine, &mut self.pull, &mut self.work, &self.config, regions));
375 self.pull.drop_before(self.work.idx);
376 self.pull.memo.clear();
377 self.work.prune();
378 Ok(frame)
379 }
380
381 /// Is every child placed, and nothing queued for a later region?
382 pub fn is_done(&mut self, engine: &mut Engine) -> Outcome<bool> {
383 if self.work.spill.is_some()
384 || !self.work.floats.is_empty()
385 || self.work.footnote_spill.is_some()
386 || !self.work.footnotes.is_empty()
387 {
388 return Ok(false);
389 }
390 Ok(res!(self.pull.get(engine, self.work.idx)).is_none())
391 }
392}
393
394// Units
395
396const EPS: f64 = 1e-4; // Typst's `Abs` tolerance, in points
397
398/// Does `need` fit into `avail`, with Typst's slack?
399fn fits(avail: f64, need: f64) -> bool { avail + EPS >= need }
400
401/// Is the length close to zero or negative?
402fn approx_empty(v: f64) -> bool { v <= EPS }
403
404/// A relative length with its absolute part resolved to points.
405#[derive(Clone, Copy, Debug, Default, PartialEq)]
406pub struct Rel {
407 pub ratio: f64,
408 pub abs: f64,
409}
410
411impl Rel {
412 pub fn zero() -> Self { Self::default() }
413
414 pub fn pt(abs: f64) -> Self { Self { ratio: 0.0, abs } }
415
416 /// The length against `whole`; a ratio of an infinite whole is nothing, as Typst's `Ratio::of`.
417 pub fn relative_to(&self, whole: f64) -> f64 {
418 let part = self.ratio * whole;
419 (if part.is_finite() { part } else { 0.0 }) + self.abs
420 }
421
422 pub fn is_zero(&self) -> bool { self.ratio == 0.0 && self.abs == 0.0 }
423}
424
425/// How a container is sized along an axis.
426#[derive(Clone, Copy, Debug, PartialEq)]
427pub enum Sizing {
428 Auto,
429 Rel(Rel),
430 Fr(f64),
431}
432
433/// Spacing: relative, or a share of what is left.
434#[derive(Clone, Copy, Debug, PartialEq)]
435pub enum Spacing {
436 Rel(Rel),
437 Fr(f64),
438}
439
440/// An alignment resolved against the text direction: Typst's `FixedAlignment`, ordered start to end.
441#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
442pub enum Fixed {
443 Start,
444 Center,
445 End,
446}
447
448impl Fixed {
449 /// The offset of something aligned so within `extent` of free space.
450 pub fn position(self, extent: f64) -> f64 {
451 match self {
452 Fixed::Start => 0.0,
453 Fixed::Center => extent / 2.0,
454 Fixed::End => extent,
455 }
456 }
457}
458
459/// A resolved alignment on both axes.
460#[derive(Clone, Copy, Debug, PartialEq, Eq)]
461pub struct Align2 {
462 pub x: Fixed,
463 pub y: Fixed,
464}
465
466impl Align2 {
467 pub const START: Align2 = Align2 { x: Fixed::Start, y: Fixed::Start };
468}
469
470/// A size in points, either axis possibly infinite.
471fn sp(pt: f64) -> Sp {
472 if !pt.is_finite() || pt >= Sp(1 << 30).to_pt() { Sp(i32::MAX) } else { Sp::from_pt(pt) }
473}
474
475fn pt_of(s: Sp) -> f64 {
476 if s.0 >= (1 << 30) { f64::INFINITY } else { s.to_pt() }
477}
478
479// Regions
480
481/// Typst's regions: the space left in the first region, the full height it started with, the heights of
482/// the regions to come, and the height that repeats once they run out.
483#[derive(Clone, Debug, PartialEq)]
484pub struct Regions {
485 pub w: f64,
486 pub h: f64,
487 pub full: f64,
488 pub backlog: Vec<f64>,
489 pub last: Option<f64>,
490 pub expand_x: bool,
491 pub expand_y: bool,
492}
493
494impl Regions {
495 /// One region only.
496 pub fn one(w: f64, h: f64, expand_x: bool, expand_y: bool) -> Self {
497 Self { w, h, full: h, backlog: Vec::new(), last: None, expand_x, expand_y }
498 }
499
500 /// A region repeated without end: a page run's pages.
501 pub fn repeat(w: f64, h: f64, expand_x: bool, expand_y: bool) -> Self {
502 Self { w, h, full: h, backlog: Vec::new(), last: Some(h), expand_x, expand_y }
503 }
504
505 /// The contract's region, as one region.
506 pub fn from_region(r: Region) -> Self {
507 let w = pt_of(r.width);
508 let h = pt_of(r.height);
509 let mut out = Self::one(w, h, r.expand_x, r.expand_y);
510 out.full = pt_of(r.base.1);
511 if out.full < h {
512 out.full = h;
513 }
514 out
515 }
516
517 /// The first region as the contract's region, relative lengths resolving against its full size.
518 pub fn region(&self) -> Region {
519 Region {
520 width: sp(self.w),
521 height: sp(self.h),
522 base: (sp(self.w), sp(self.full)),
523 expand_x: self.expand_x,
524 expand_y: self.expand_y,
525 }
526 }
527
528 /// The size relative lengths resolve against.
529 pub fn base(&self) -> (f64, f64) { (self.w, self.full) }
530
531 /// Is the first region full, with another one to go to?
532 pub fn is_full(&self) -> bool { fits(0.0, self.h) && self.may_progress() }
533
534 /// Is there a region after the first?
535 pub fn may_break(&self) -> bool { !self.backlog.is_empty() || self.last.is_some() }
536
537 /// Would moving to the next region give more room?
538 pub fn may_progress(&self) -> bool {
539 !self.backlog.is_empty() || self.last.map(|l| self.h != l).unwrap_or(false)
540 }
541
542 /// Moves to the next region, if there is one.
543 pub fn next(&mut self) {
544 let height = if self.backlog.is_empty() {
545 self.last
546 } else {
547 Some(self.backlog.remove(0))
548 };
549 if let Some(h) = height {
550 self.h = h;
551 self.full = h;
552 }
553 }
554
555 /// The height of the `i`th region from this one, the first being `self.h`.
556 pub fn nth(&self, i: usize) -> Option<f64> {
557 if i == 0 {
558 return Some(self.h);
559 }
560 match self.backlog.get(i - 1) {
561 Some(h) => Some(*h),
562 None => self.last,
563 }
564 }
565
566 /// A hash of everything a layout could depend on, for caching a child's layout.
567 fn key(&self) -> Fingerprint {
568 let mut h = Fingerprinter::new();
569 for v in [self.w, self.h, self.full, self.last.unwrap_or(-1.0)] {
570 h.write_f64(v);
571 }
572 for v in &self.backlog {
573 h.write_f64(*v);
574 }
575 h.write_bool(self.last.is_some());
576 h.write_bool(self.expand_x);
577 h.write_bool(self.expand_y);
578 h.finish()
579 }
580
581 /// The regions with every height shrunk by `f`, the widths likewise.
582 fn map<F: Fn(f64, f64) -> (f64, f64)>(&self, f: F) -> Regions {
583 let (w, h) = f(self.w, self.h);
584 let (_, full) = f(self.w, self.full);
585 Regions {
586 w,
587 h,
588 full,
589 backlog: self.backlog.iter().map(|y| f(self.w, *y).1).collect(),
590 last: self.last.map(|y| f(self.w, y).1),
591 expand_x: self.expand_x,
592 expand_y: self.expand_y,
593 }
594 }
595}
596
597// Frames
598
599/// Typst's frame: a sized box of items placed by their top-left, in points, y down. `baseline` is from the
600/// top; none means the bottom.
601#[derive(Clone, Debug, Default)]
602pub struct Frame {
603 pub w: f64,
604 pub h: f64,
605 pub baseline: Option<f64>,
606 pub items: Vec<(f64, f64, Item)>,
607 pub parent: Option<u64>, // the mark this frame is read at for introspection, as `FrameNode::parent`
608}
609
610/// What a frame holds.
611#[derive(Clone, Debug)]
612pub enum Item {
613 Frame(Frame), // a nested frame
614 Node(Node), // laid-out IR: a line, a leaf, a box
615 Group(Frame, Transform, Option<Path>), // a frame drawn under a transform and clipped to a path
616 Tag(Tag), // where a located element starts or ends
617}
618
619impl Frame {
620 pub fn new(w: f64, h: f64) -> Self { Self { w, h, baseline: None, items: Vec::new(), parent: None } }
621
622 /// An IR node as a frame of its size.
623 pub fn from_node(node: Node) -> Self {
624 let (w, h, base) = match node_dims(&node) {
625 Some(d) => (d.width.to_pt(), d.vextent().to_pt(), d.height.to_pt()),
626 None => (0.0, 0.0, 0.0),
627 };
628 let mut f = Frame::new(w, h);
629 f.baseline = Some(base);
630 f.items.push((0.0, 0.0, Item::Node(node)));
631 f
632 }
633
634 pub fn is_empty(&self) -> bool { self.items.is_empty() }
635
636 pub fn has_baseline(&self) -> bool { self.baseline.is_some() }
637
638 pub fn baseline(&self) -> f64 { self.baseline.unwrap_or(self.h) }
639
640 pub fn push(&mut self, x: f64, y: f64, item: Item) { self.items.push((x, y, item)); }
641
642 pub fn push_frame(&mut self, x: f64, y: f64, frame: Frame) {
643 if frame.is_empty() {
644 return;
645 }
646 self.items.push((x, y, Item::Frame(frame)));
647 }
648
649 /// Puts items behind everything the frame holds.
650 pub fn prepend(&mut self, items: Vec<(f64, f64, Item)>) {
651 let mut v = items;
652 v.append(&mut self.items);
653 self.items = v;
654 }
655
656 /// Moves the contents and the baseline.
657 pub fn translate(&mut self, dx: f64, dy: f64) {
658 if dx == 0.0 && dy == 0.0 {
659 return;
660 }
661 if let Some(b) = &mut self.baseline {
662 *b += dy;
663 }
664 for (x, y, _) in &mut self.items {
665 *x += dx;
666 *y += dy;
667 }
668 }
669
670 /// Wraps the contents in one group, as Typst does to carry a label: the frame is no longer empty, even
671 /// when it held nothing, which is what lets a labelled empty block end a run of sticky blocks.
672 pub fn label(&mut self) {
673 let inner = Frame {
674 w: self.w,
675 h: self.h,
676 baseline: None,
677 items: std::mem::take(&mut self.items),
678 parent: None,
679 };
680 self.items.push((0.0, 0.0, Item::Frame(inner)));
681 }
682
683 /// Clips the contents to `path`, in the frame's coordinates.
684 pub fn clip(&mut self, path: Path) {
685 if self.items.is_empty() {
686 return;
687 }
688 let inner = Frame { w: self.w, h: self.h, baseline: None, items: std::mem::take(&mut self.items), parent: None };
689 self.items.push((0.0, 0.0, Item::Group(inner, Transform::identity(), Some(path))));
690 }
691
692 /// Drops every visible item, keeping the tags, as Typst's `hide` modifier does.
693 pub fn hide(&mut self) {
694 let mut kept = Vec::new();
695 for (x, y, item) in std::mem::take(&mut self.items) {
696 match item {
697 Item::Tag(t) => kept.push((x, y, Item::Tag(t))),
698 Item::Frame(mut f) | Item::Group(mut f, _, _) => {
699 f.hide();
700 if !f.is_empty() {
701 kept.push((x, y, Item::Frame(f)));
702 }
703 },
704 Item::Node(n) => {
705 let mut tags = Vec::new();
706 node_tags(&n, 0.0, &mut tags);
707 for (ty, t) in tags {
708 kept.push((x, y + ty, Item::Tag(t)));
709 }
710 },
711 }
712 }
713 self.items = kept;
714 }
715
716 /// Applies what the chain asks of a laid-out frame, Typst's `modify_frame`: a link over the whole frame,
717 /// then hiding, which takes the link off again.
718 pub fn modify(&mut self, mods: &Modifiers) {
719 if let Some(target) = &mods.link {
720 let mut g = Graphic::new(Vec::new(), Dims::new(Sp::from_pt(self.w), Sp::from_pt(self.h), Sp::ZERO));
721 g.link = Some(target.clone());
722 self.items.push((0.0, 0.0, Item::Node(Node::Leaf(Leaf::graphic(g)))));
723 }
724 if mods.hidden {
725 self.hide();
726 }
727 }
728
729 /// The frame as an IR frame node, its box split at the baseline.
730 pub fn into_node(self) -> Node {
731 let base = self.baseline();
732 let dims = Dims::new(Sp::from_pt(self.w), Sp::from_pt(base), Sp::from_pt(self.h - base));
733 let mut out = FrameNode::new(dims);
734 out.parent = self.parent;
735 for (x, y, item) in self.items {
736 let node = match item {
737 Item::Frame(f) => f.into_node(),
738 Item::Node(n) => n,
739 Item::Tag(t) => Node::Tag(t),
740 Item::Group(f, t, clip) => {
741 let fd = Dims::new(Sp::from_pt(f.w), Sp::from_pt(f.h), Sp::ZERO);
742 let inner = f.into_node();
743 let clipped = match clip {
744 Some(path) => Node::Clip(ClipNode { list: vec![inner], dims: fd, path: Some(path) }),
745 None => inner,
746 };
747 if t == Transform::identity() {
748 clipped
749 } else {
750 Node::Transform(TransformNode { transform: t, list: vec![clipped], dims: fd })
751 }
752 },
753 };
754 out.items.push((Sp::from_pt(x), Sp::from_pt(y), node));
755 }
756 Node::Frame(out)
757 }
758}
759
760/// Typst's `FrameModifiers`: what the chain asks of a block's frame once it is laid out.
761#[derive(Clone, Debug, Default)]
762pub struct Modifiers {
763 pub hidden: bool,
764 pub link: Option<LinkTarget>, // `link.current`
765}
766
767impl Modifiers {
768 pub fn get(styles: &StyleChain) -> Outcome<Self> {
769 Ok(Self {
770 hidden: res!(vis::is_hidden(styles)),
771 link: res!(elem_field(styles, ElemKind::Link, "current")).as_ref().and_then(link_target),
772 })
773 }
774}
775
776/// The chain a linked frame's contents are laid out under, the link taken off, as Typst's
777/// `layout_and_modify` does: the frame carries the link, so nothing inside it is linked a second time.
778pub fn unlink(styles: &StyleChain, link: &Option<LinkTarget>) -> StyleChain {
779 match (link, ElemKind::Link.field_id("current")) {
780 (Some(_), Some(id)) => styles.chain(&Styles::from_style(Style::Property(Property::new(
781 ElemKind::Link, id, Value::None, Span::detached())))),
782 _ => styles.clone(),
783 }
784}
785
786/// A node's box, when it has one.
787pub fn node_dims(node: &Node) -> Option<Dims> {
788 match node {
789 Node::HBox(b) | Node::VBox(b) => Some(b.dims),
790 Node::Leaf(l) => Some(l.dims),
791 Node::Frame(f) => Some(f.dims),
792 Node::Transform(t) => Some(t.dims),
793 Node::Clip(c) => Some(c.dims),
794 _ => None,
795 }
796}
797
798/// The tags in a node tree, with their offsets down from its top.
799fn node_tags(node: &Node, y: f64, out: &mut Vec<(f64, Tag)>) {
800 match node {
801 Node::Tag(t) => out.push((y, t.clone())),
802 Node::VBox(b) => {
803 let mut yy = y;
804 for c in &b.list {
805 node_tags(c, yy, out);
806 yy += c.vextent().to_pt();
807 }
808 },
809 Node::HBox(b) => {
810 let base = y + b.dims.height.to_pt();
811 for c in &b.list {
812 match c {
813 Node::Tag(t) => out.push((base, t.clone())),
814 other => {
815 let top = node_dims(other).map(|d| base - d.height.to_pt()).unwrap_or(y);
816 node_tags(other, top, out);
817 },
818 }
819 }
820 },
821 Node::Frame(f) => for (_, dy, c) in &f.items { node_tags(c, y + dy.to_pt(), out); },
822 Node::Transform(t) => {
823 let mut yy = y;
824 for c in &t.list {
825 node_tags(c, yy, out);
826 yy += c.vextent().to_pt();
827 }
828 },
829 Node::Clip(c) => {
830 let mut yy = y;
831 for n in &c.list {
832 node_tags(n, yy, out);
833 yy += n.vextent().to_pt();
834 }
835 },
836 _ => (),
837 }
838}
839
840/// The footnotes whose start tags a frame holds, with their offsets down from its top.
841pub fn find_footnotes(frame: &Frame, y0: f64, out: &mut Vec<(f64, Content)>) {
842 for (_, y, item) in &frame.items {
843 let y = y0 + y;
844 match item {
845 Item::Frame(f) | Item::Group(f, _, _) => find_footnotes(f, y, out),
846 Item::Tag(Tag::Start(c)) => if c.is(ElemKind::Footnote) {
847 out.push((y, c.clone()));
848 },
849 Item::Tag(_) => (),
850 Item::Node(n) => {
851 let mut tags = Vec::new();
852 node_tags(n, y, &mut tags);
853 for (ty, t) in tags {
854 if let Tag::Start(c) = t {
855 if c.is(ElemKind::Footnote) {
856 out.push((ty, c));
857 }
858 }
859 }
860 },
861 }
862 }
863}
864
865// Style access
866
867/// A field's value in force for an element: its own (folded onto the chain's for a folding field), else
868/// the chain's, else the schema default.
869pub(super) fn field(elem: &Content, styles: &StyleChain, name: &str) -> Outcome<Option<Value>> {
870 let kind = match elem.kind() {
871 Some(k) => k,
872 None => return Ok(None),
873 };
874 match kind.field_id(name) {
875 Some(id) => styles.resolve(elem, id),
876 None => Ok(None),
877 }
878}
879
880/// A field of another element kind, as the chain has it.
881pub(super) fn chain_field(styles: &StyleChain, kind: ElemKind, name: &str) -> Outcome<Option<Value>> {
882 match kind.field_id(name) {
883 Some(id) => styles.get(kind, id),
884 None => Ok(None),
885 }
886}
887
888/// A length in points, its em part at the font size in force.
889pub(super) fn abs_of(styles: &StyleChain, l: Length) -> f64 { styles.resolve_length(l) }
890
891/// A relative length from any value Typst accepts as one.
892pub(super) fn rel_of(styles: &StyleChain, v: &Value) -> Option<Rel> {
893 match v {
894 Value::Length(l) => Some(Rel::pt(abs_of(styles, *l))),
895 Value::Ratio(r) => Some(Rel { ratio: r.0, abs: 0.0 }),
896 Value::Relative(r) => Some(Rel { ratio: r.rel.0, abs: abs_of(styles, r.abs) }),
897 Value::Int(0) => Some(Rel::zero()),
898 _ => None,
899 }
900}
901
902fn sizing_of(styles: &StyleChain, v: Option<Value>) -> Sizing {
903 match v {
904 Some(Value::Fraction(f)) => Sizing::Fr(f.0),
905 Some(other) => match rel_of(styles, &other) {
906 Some(r) => Sizing::Rel(r),
907 None => Sizing::Auto,
908 },
909 None => Sizing::Auto,
910 }
911}
912
913fn spacing_of(styles: &StyleChain, v: &Value) -> Option<Spacing> {
914 match v {
915 Value::Fraction(f) => Some(Spacing::Fr(f.0)),
916 other => rel_of(styles, other).map(Spacing::Rel),
917 }
918}
919
920fn bool_of(v: Option<Value>, default: bool) -> bool {
921 match v {
922 Some(Value::Bool(b)) => b,
923 _ => default,
924 }
925}
926
927/// Is the text direction in force right to left?
928pub(super) fn rtl(styles: &StyleChain) -> Outcome<bool> {
929 Ok(matches!(res!(chain_field(styles, ElemKind::Text, "dir")), Some(Value::Direction(Direction::Rtl))))
930}
931
932/// A horizontal alignment as a position from the left: `left` and `right` are physical, `start` and
933/// `end` follow the text direction.
934fn fix_h(h: HAlign, rtl: bool) -> Fixed {
935 match h {
936 HAlign::Left => Fixed::Start,
937 HAlign::Right => Fixed::End,
938 HAlign::Center => Fixed::Center,
939 HAlign::Start => if rtl { Fixed::End } else { Fixed::Start },
940 HAlign::End => if rtl { Fixed::Start } else { Fixed::End },
941 }
942}
943
944fn fix_v(v: VAlign) -> Fixed {
945 match v {
946 VAlign::Top => Fixed::Start,
947 VAlign::Horizon => Fixed::Center,
948 VAlign::Bottom => Fixed::End,
949 }
950}
951
952/// The alignment in force, folded axis by axis from the innermost `align` style outward, `start + top`
953/// where none says otherwise.
954pub fn alignment(styles: &StyleChain) -> Outcome<Align2> {
955 let (mut x, mut y) = (None, None);
956 if let Some(id) = ElemKind::Align.field_id("alignment") {
957 for v in styles.values(ElemKind::Align, id) {
958 if let Value::Alignment(a) = v {
959 if x.is_none() {
960 x = a.x;
961 }
962 if y.is_none() {
963 y = a.y;
964 }
965 }
966 if x.is_some() && y.is_some() {
967 break;
968 }
969 }
970 }
971 let r = res!(rtl(styles));
972 Ok(Align2 {
973 x: fix_h(x.unwrap_or(HAlign::Start), r),
974 y: fix_v(y.unwrap_or(VAlign::Top)),
975 })
976}
977
978/// The four sides of a sides value (`left, top, right, bottom`), each resolved to a relative length,
979/// zero where unset: a single value, or a dictionary by Typst's precedence of a side over its axis over
980/// `rest`.
981fn sides_rel(styles: &StyleChain, v: Option<Value>) -> [Rel; 4] {
982 let parts = sides_values(v);
983 parts.map(|p| p.and_then(|v| rel_of(styles, &v)).unwrap_or_default())
984}
985
986fn sides_values(v: Option<Value>) -> [Option<Value>; 4] {
987 match v {
988 None | Some(Value::None) | Some(Value::Auto) => [None, None, None, None],
989 Some(Value::Dict(d)) => {
990 let get = |k: &str| d.get(k).cloned();
991 let rest = get("rest");
992 let x = get("x").or_else(|| rest.clone());
993 let y = get("y").or_else(|| rest.clone());
994 [
995 get("left").or_else(|| get("inside")).or_else(|| x.clone()),
996 get("top").or_else(|| y.clone()),
997 get("right").or_else(|| get("outside")).or_else(|| x.clone()),
998 get("bottom").or_else(|| y.clone()),
999 ]
1000 },
1001 Some(other) => [Some(other.clone()), Some(other.clone()), Some(other.clone()), Some(other)],
1002 }
1003}
1004
1005fn sides_zero(s: &[Rel; 4]) -> bool { s.iter().all(|r| r.is_zero()) }
1006
1007/// Shrinks a size by an inset relative to the size itself: Typst's `pad::shrink`.
1008fn shrink(w: f64, h: f64, inset: &[Rel; 4]) -> (f64, f64) {
1009 let x = Rel { ratio: inset[0].ratio + inset[2].ratio, abs: inset[0].abs + inset[2].abs };
1010 let y = Rel { ratio: inset[1].ratio + inset[3].ratio, abs: inset[1].abs + inset[3].abs };
1011 (w - x.relative_to(w), h - y.relative_to(h))
1012}
1013
1014/// Grows a frame by an inset relative to the grown size, the inverse of [`shrink`]: Typst's `pad::grow`.
1015fn grow(frame: &mut Frame, inset: &[Rel; 4]) {
1016 let px = Rel { ratio: inset[0].ratio + inset[2].ratio, abs: inset[0].abs + inset[2].abs };
1017 let py = Rel { ratio: inset[1].ratio + inset[3].ratio, abs: inset[1].abs + inset[3].abs };
1018 let w = (frame.w + px.abs) / (1.0 - px.ratio);
1019 let h = (frame.h + py.abs) / (1.0 - py.ratio);
1020 let left = inset[0].relative_to(w);
1021 let top = inset[1].relative_to(h);
1022 frame.w = w;
1023 frame.h = h;
1024 frame.translate(left, top);
1025}
1026
1027// Children
1028
1029/// What waits to be placed with the next frame: a tag, or the mark of a float's place in the flow.
1030#[derive(Clone, Debug)]
1031pub(super) enum Pending {
1032 Tag(Tag),
1033 Mark(u64),
1034}
1035
1036impl Pending {
1037 fn item(self) -> Item {
1038 match self {
1039 Pending::Tag(t) => Item::Tag(t),
1040 Pending::Mark(m) => Item::Node(Node::Mark(m)),
1041 }
1042 }
1043}
1044
1045/// A prepared child of a flow, Typst's `Child`.
1046#[derive(Debug)]
1047pub(super) enum Child {
1048 Tag(Tag),
1049 Mark(u64), // where a float's `place` stands
1050 Rel(Rel, u8), // spacing and its weakness: 0 strong, then block (3), paragraph (4) and leading (5)
1051 Fr(f64, u8),
1052 Line(LineChild),
1053 Single(Rc<SingleChild>),
1054 Multi(Rc<MultiChild>),
1055 Placed(Rc<PlacedChild>),
1056 Flush,
1057 Break(bool), // a column break, weak or not
1058}
1059
1060/// A laid-out line of a paragraph, and the height it needs to keep with its widow or orphan partner.
1061#[derive(Debug)]
1062pub(super) struct LineChild {
1063 pub(super) frame: Frame,
1064 pub(super) align: Align2,
1065 pub(super) need: f64,
1066}
1067
1068/// What a block lays out: nothing, content, or its element by that element's own layout routine (a shape,
1069/// a grid, a pad, a stack, columns, an equation, `layout`).
1070#[derive(Clone, Debug)]
1071pub(super) enum Body {
1072 Empty,
1073 Content(Content),
1074 Layouter,
1075}
1076
1077/// A block and the styles it is laid out under. An explicit `block` reads its fields; an element Typst
1078/// shows as a block reads the `block` styles in force.
1079#[derive(Clone, Debug)]
1080pub(super) struct BlockSpec {
1081 pub(super) elem: Content,
1082 pub(super) styles: StyleChain, // with any link taken off, which `mods` carries
1083 pub(super) body: Body,
1084 pub(super) explicit: bool,
1085 pub(super) mods: Modifiers,
1086}
1087
1088impl BlockSpec {
1089 fn new(elem: Content, styles: &StyleChain, body: Body, explicit: bool) -> Outcome<Self> {
1090 let mods = res!(Modifiers::get(styles));
1091 let styles = unlink(styles, &mods.link);
1092 Ok(Self { elem, styles, body, explicit, mods })
1093 }
1094
1095 fn field(&self, name: &str) -> Outcome<Option<Value>> {
1096 if self.explicit {
1097 field(&self.elem, &self.styles, name)
1098 } else {
1099 chain_field(&self.styles, ElemKind::Block, name)
1100 }
1101 }
1102
1103 /// Width and height: an explicit block's own; an element's layout sizes itself.
1104 fn sizing(&self, name: &str) -> Outcome<Sizing> {
1105 if self.explicit {
1106 Ok(sizing_of(&self.styles, res!(self.field(name))))
1107 } else {
1108 Ok(Sizing::Auto)
1109 }
1110 }
1111
1112 fn span(&self) -> Span { self.elem.span() }
1113}
1114
1115#[derive(Debug)]
1116pub(super) struct SingleChild {
1117 pub(super) align: Align2,
1118 pub(super) sticky: bool,
1119 pub(super) alone: bool,
1120 pub(super) fr: Option<f64>,
1121 pub(super) spec: BlockSpec,
1122 pub(super) cell: RefCell<Option<(Fingerprint, Frame)>>,
1123}
1124
1125impl SingleChild {
1126 /// The block laid out in the region's base size; vertical expansion only when it is the flow's sole child.
1127 fn layout(&self, engine: &mut Engine, w: f64, h: f64, expand_x: bool, expand_y: bool) -> Outcome<Frame> {
1128 let region = Regions::one(w, h, expand_x, expand_y && self.alone);
1129 let key = region.key();
1130 if let Some((k, f)) = &*self.cell.borrow() {
1131 if *k == key {
1132 return Ok(f.clone());
1133 }
1134 }
1135 let frame = res!(engine.descend(|engine| layout_single(engine, &self.spec, &region)));
1136 *self.cell.borrow_mut() = Some((key, frame.clone()));
1137 Ok(frame)
1138 }
1139}
1140
1141/// A breakable block. It lays out one fragment per region, each from the continuation the one before
1142/// left: see [`MultiChild::fragment`].
1143#[derive(Debug)]
1144pub(super) struct MultiChild {
1145 pub(super) align: Align2,
1146 pub(super) sticky: bool,
1147 pub(super) alone: bool,
1148 pub(super) spec: BlockSpec,
1149}
1150
1151/// A fragment laid out in the region being composed, kept so a region laid out again from the same state, as
1152/// a float or a footnote asks for, takes it back instead of laying the block out again. The flow keeps them,
1153/// not the block, so that a block holds no continuation that holds the block; they go when the region is
1154/// finished.
1155#[derive(Clone, Debug)]
1156pub(super) struct Memo {
1157 child: usize, // the block, by address
1158 from: usize, // the continuation it came from, by address, or zero for the first
1159 key: Fingerprint, // the regions the fragment was laid out in
1160 out: Fragment,
1161}
1162
1163/// A breakable block's fragment as the flow places it, and what is needed to go on from it.
1164#[derive(Clone, Debug)]
1165struct Fragment {
1166 frame: Frame,
1167 next: Option<Rc<Spill>>, // what lays out the fragment after, none once the block has ended here
1168 skip: bool, // empty here while a later fragment is not: the block waits for the next region
1169}
1170
1171/// What carries a breakable block over a region break: the means of laying out its next fragment, and
1172/// what a block of fixed height has left. A [`Work`] holds one, and a copy of the work holds the same one,
1173/// so laying a region out again starts from the right place.
1174#[derive(Debug)]
1175pub(super) struct Spill {
1176 pub(super) child: Rc<MultiChild>,
1177 pub(super) nested: Nested,
1178 pub(super) k: usize, // fragments yielded
1179 pub(super) fixed: Option<(f64, f64)>, // a fixed height, whole and what is left of it
1180}
1181
1182/// What lays out a block's fragments.
1183#[derive(Clone, Debug)]
1184pub(super) enum Nested {
1185 Flow(Box<FlowCursor>, Option<[Rel; 4]>), // the body flowed through the regions, grown by a pad's padding
1186 Frames(VecDeque<Frame>, Regions), // frames laid out as one piece, and the regions they were laid out in
1187}
1188
1189/// A placed child's vertical alignment: `auto` (a float's choice), none (in the flow), or an edge.
1190#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1191pub(super) enum PlaceY {
1192 Auto,
1193 Flow,
1194 At(Fixed),
1195}
1196
1197#[derive(Debug)]
1198pub(super) struct PlacedChild {
1199 pub(super) align_x: Fixed,
1200 pub(super) align_y: PlaceY,
1201 pub(super) parent: bool, // `scope: "parent"`
1202 pub(super) float: bool,
1203 pub(super) clearance: f64,
1204 pub(super) dx: Rel,
1205 pub(super) dy: Rel,
1206 pub(super) alignment: Option<Alignment>, // `auto` is none
1207 pub(super) mark: u64, // the float's place in the flow, its frame's parent
1208 pub(super) elem: Content,
1209 pub(super) styles: StyleChain,
1210 pub(super) cell: RefCell<Option<(Fingerprint, Frame)>>,
1211}
1212
1213impl PlacedChild {
1214 /// The body laid out in the base size, unexpanded, under the placement's alignment.
1215 fn layout(&self, engine: &mut Engine, base: (f64, f64)) -> Outcome<Frame> {
1216 let region = Regions::one(base.0, base.1, false, false);
1217 let key = region.key();
1218 if let Some((k, f)) = &*self.cell.borrow() {
1219 if *k == key {
1220 return Ok(f.clone());
1221 }
1222 }
1223 let align = match self.alignment {
1224 Some(a) => a,
1225 None => Alignment { x: Some(HAlign::Center), y: Some(VAlign::Horizon) },
1226 };
1227 let mods = res!(Modifiers::get(&self.styles));
1228 let outer = unlink(&self.styles, &mods.link);
1229 let styles = match ElemKind::Align.field_id("alignment") {
1230 Some(id) => outer.chain(&crate::eval::styles::Styles::from_style(
1231 crate::eval::styles::Style::Property(crate::eval::styles::Property::new(
1232 ElemKind::Align, id, Value::Alignment(align), self.elem.span())))),
1233 None => outer,
1234 };
1235 let body = match res!(field(&self.elem, &self.styles, "body")) {
1236 Some(v) => res!(v.cast::<Content>()),
1237 None => Content::empty(),
1238 };
1239 let mut frame = res!(layout_frame_in(engine, self.elem.place(), &body, &styles, region));
1240 frame.modify(&mods);
1241 if self.float {
1242 frame.parent = Some(self.mark);
1243 }
1244 *self.cell.borrow_mut() = Some((key, frame.clone()));
1245 Ok(frame)
1246 }
1247}
1248
1249// Collection
1250
1251/// Collects one realised pair into prepared children, Typst's `collect`. A paragraph is set into lines
1252/// here, when the cursor reaches it, since line layout does not depend on the concrete regions. `alone` is
1253/// whether the pair is the whole of the flow, which lets a block expand into the region's height.
1254fn collect_pair(
1255 engine: &mut Engine,
1256 p: &Pair,
1257 alone: bool,
1258 cfg: CollectCfg,
1259 par: &mut ParSituation,
1260 out: &mut Vec<Child>,
1261)
1262 -> Outcome<()>
1263{
1264 if let Some(t) = &p.tag {
1265 out.push(Child::Tag(t.clone()));
1266 return Ok(());
1267 }
1268 let c = &p.content;
1269 let styles = &p.styles;
1270 let kind = match c.kind() {
1271 Some(k) => k,
1272 None => return Ok(()),
1273 };
1274 match kind {
1275 ElemKind::V => {
1276 let amount = res!(field(c, styles, "amount"));
1277 let weak = bool_of(res!(field(c, styles, "weak")), false) as u8;
1278 match amount.as_ref().and_then(|a| spacing_of(styles, a)) {
1279 Some(Spacing::Rel(r)) => out.push(Child::Rel(r, weak)),
1280 Some(Spacing::Fr(f)) => out.push(Child::Fr(f, weak)),
1281 None => (),
1282 }
1283 },
1284 ElemKind::Par => {
1285 res!(collect_par(engine, c, styles, cfg, *par, out));
1286 *par = ParSituation::Consecutive;
1287 },
1288 ElemKind::Block => {
1289 let body = match res!(field(c, styles, "body")) {
1290 None | Some(Value::None) => Body::Empty,
1291 Some(v) => Body::Content(res!(v.cast::<Content>())),
1292 };
1293 res!(collect_block(res!(BlockSpec::new(c.clone(), styles, body, true)), alone, None, out));
1294 *par = ParSituation::Other;
1295 },
1296 ElemKind::Place => res!(collect_place(engine, c, styles, out)),
1297 ElemKind::PlaceFlush => out.push(Child::Flush),
1298 ElemKind::Colbreak => {
1299 out.push(Child::Break(bool_of(res!(field(c, styles, "weak")), false)));
1300 *par = ParSituation::First;
1301 },
1302 ElemKind::Pagebreak => return Err(engine.error_hint(DiagnosticKind::Type, c.span(),
1303 "pagebreaks are not allowed inside of containers", "try using a `#colbreak()` instead")),
1304 // Shown by Typst as breakable blocks with a layout routine of their own.
1305 ElemKind::Pad | ElemKind::Stack | ElemKind::Columns | ElemKind::Grid | ElemKind::Table
1306 | ElemKind::Layout | ElemKind::Equation | ElemKind::List | ElemKind::Enum => {
1307 let spec = res!(BlockSpec::new(c.clone(), styles, Body::Layouter, false));
1308 res!(collect_block(spec, alone, Some(true), out));
1309 *par = ParSituation::Other;
1310 },
1311 // Shown by Typst as unbreakable blocks with a layout routine of their own; a fractional height
1312 // makes the block a share of the region's free space.
1313 ElemKind::Image | ElemKind::Line | ElemKind::Rect | ElemKind::Square | ElemKind::Circle
1314 | ElemKind::Ellipse | ElemKind::Polygon | ElemKind::Curve | ElemKind::Move | ElemKind::Scale
1315 | ElemKind::Rotate | ElemKind::Skew | ElemKind::Repeat => {
1316 let spec = res!(BlockSpec::new(c.clone(), styles, Body::Layouter, false));
1317 res!(collect_block(spec, alone, Some(false), out));
1318 *par = ParSituation::Other;
1319 },
1320 // A tag carried as an element marks where its element starts or ends.
1321 ElemKind::Tag => if let Some(t) = Tag::from_content(c) {
1322 out.push(Child::Tag(t));
1323 },
1324 // Introspection elements mark their place with their tags and lay out nothing.
1325 k if k.family() == Family::Intro => (),
1326 other => engine.warn(DiagnosticKind::Unsupported, c.span(), fmt!("{} was ignored during paged export", other.name())),
1327 }
1328 Ok(())
1329}
1330
1331/// A fragment that is inline only: its lines with leading, the tags at either end kept outside them.
1332fn collect_inline(engine: &mut Engine, pairs: &[Pair], cfg: CollectCfg, out: &mut Vec<Child>) -> Outcome<()> {
1333 let start = pairs.iter().take_while(|p| p.is_tag()).count();
1334 let end = pairs.len() - pairs[start..].iter().rev().take_while(|p| p.is_tag()).count();
1335 let inner = &pairs[start..end];
1336 let styles = StyleChain::trunk(inner.iter().map(|p| &p.styles));
1337 for p in &pairs[..start] {
1338 if let Some(t) = &p.tag {
1339 out.push(Child::Tag(t.clone()));
1340 }
1341 }
1342 let region = Regions::one(cfg.width, cfg.height, cfg.expand, false).region();
1343 let nodes = res!(crate::flow::par::layout_inline(engine, inner, &styles, region, cfg.expand));
1344 res!(collect_lines(nodes, &styles, out));
1345 for p in &pairs[end..] {
1346 if let Some(t) = &p.tag {
1347 out.push(Child::Tag(t.clone()));
1348 }
1349 }
1350 Ok(())
1351}
1352
1353/// A paragraph: its body set into lines, with the paragraph spacing on either side. `situation` is where the
1354/// flow stands, which decides the first-line indent.
1355fn collect_par(
1356 engine: &mut Engine,
1357 par: &Content,
1358 styles: &StyleChain,
1359 cfg: CollectCfg,
1360 situation: ParSituation,
1361 out: &mut Vec<Child>,
1362)
1363 -> Outcome<()>
1364{
1365 let region = Regions::one(cfg.width, cfg.height, cfg.expand, false).region();
1366 let nodes = res!(engine.descend(|engine| crate::flow::par::layout_par(engine, par, styles, region, situation)));
1367 let spacing = res!(par_spacing(par, styles));
1368 out.push(Child::Rel(spacing, 4));
1369 res!(collect_lines(nodes, styles, out));
1370 out.push(Child::Rel(spacing, 4));
1371 Ok(())
1372}
1373
1374/// The paragraph spacing in force, Typst's 1.2em by default.
1375fn par_spacing(par: &Content, styles: &StyleChain) -> Outcome<Rel> {
1376 let v = if par.is(ElemKind::Par) {
1377 res!(field(par, styles, "spacing"))
1378 } else {
1379 res!(chain_field(styles, ElemKind::Par, "spacing"))
1380 };
1381 Ok(match v.and_then(|v| rel_of(styles, &v)) {
1382 Some(r) => r,
1383 None => Rel::pt(1.2 * styles.font_size()),
1384 })
1385}
1386
1387/// The widow and orphan costs in force, as ratios (Typst's `text.costs`, 100% each by default).
1388fn costs(styles: &StyleChain) -> Outcome<(f64, f64)> {
1389 let (mut widow, mut orphan) = (1.0, 1.0);
1390 if let Some(Value::Dict(d)) = res!(chain_field(styles, ElemKind::Text, "costs")) {
1391 if let Some(Value::Ratio(r)) = d.get("widow") {
1392 widow = r.0;
1393 }
1394 if let Some(Value::Ratio(r)) = d.get("orphan") {
1395 orphan = r.0;
1396 }
1397 }
1398 Ok((widow, orphan))
1399}
1400
1401/// A paragraph's set lines as children: each line with the leading before it, and the space it needs to
1402/// keep an orphan or widow with its partner, as Typst's `lines`. The glue the line setter puts between two
1403/// lines is their leading.
1404fn collect_lines(nodes: Vec<Node>, styles: &StyleChain, out: &mut Vec<Child>) -> Outcome<()> {
1405 let align = res!(alignment(styles));
1406 let (widow, orphan) = res!(costs(styles));
1407 // The lines, each with the leading above it; tags between lines keep their order.
1408 enum Entry {
1409 Line(Frame, f64),
1410 Tag(Tag),
1411 }
1412 let mut entries: Vec<Entry> = Vec::new();
1413 let mut lead = 0.0;
1414 for n in nodes {
1415 match n {
1416 Node::Glue(g) => lead += g.natural.to_pt(),
1417 Node::Tag(t) => entries.push(Entry::Tag(t)),
1418 Node::Penalty(_) => (),
1419 Node::Anchor(_) | Node::Mark(_) | Node::Float(_) | Node::Columns(_) | Node::PageColumns(_)
1420 | Node::RepeatHead(_) | Node::RepeatFoot(_) => (),
1421 other => {
1422 entries.push(Entry::Line(Frame::from_node(other), lead));
1423 lead = 0.0;
1424 },
1425 }
1426 }
1427 let lines: Vec<(f64, f64)> = entries.iter().filter_map(|e| match e {
1428 Entry::Line(f, l) => Some((f.h, *l)),
1429 Entry::Tag(_) => None,
1430 }).collect();
1431 let len = lines.len();
1432 let prevent_orphans = orphan > 0.0 && len >= 2;
1433 let prevent_widows = widow > 0.0 && len >= 2;
1434 let prevent_all = len == 3 && prevent_orphans && prevent_widows;
1435 let height_at = |i: usize| lines.get(i).map(|l| l.0).unwrap_or(0.0);
1436 let lead_at = |i: usize| lines.get(i).map(|l| l.1).unwrap_or(0.0);
1437 let mut i = 0usize;
1438 for e in entries {
1439 match e {
1440 Entry::Tag(t) => out.push(Child::Tag(t)),
1441 Entry::Line(frame, l) => {
1442 if i > 0 {
1443 out.push(Child::Rel(Rel::pt(l), 5));
1444 }
1445 let need = if prevent_all && i == 0 {
1446 height_at(0) + lead_at(1) + height_at(1) + lead_at(2) + height_at(2)
1447 } else if prevent_orphans && i == 0 {
1448 height_at(0) + lead_at(1) + height_at(1)
1449 } else if prevent_widows && i >= 2 && i + 2 == len {
1450 height_at(len - 2) + lead_at(len - 1) + height_at(len - 1)
1451 } else {
1452 frame.h
1453 };
1454 out.push(Child::Line(LineChild { frame, align, need }));
1455 i += 1;
1456 },
1457 }
1458 }
1459 Ok(())
1460}
1461
1462/// A block, with its spacing above and below: Typst's `block` collection. `breakable` is forced for an
1463/// element Typst shows through a layout routine: `Some(false)` for one that lays out in one region.
1464fn collect_block(spec: BlockSpec, alone: bool, breakable: Option<bool>, out: &mut Vec<Child>) -> Outcome<()> {
1465 let styles = spec.styles.clone();
1466 let align = res!(alignment(&styles));
1467 let sticky = bool_of(res!(spec.field("sticky")), false);
1468 let breakable = match breakable {
1469 Some(false) => false,
1470 _ => bool_of(res!(spec.field("breakable")), true),
1471 };
1472 // A fractional height: a block's own, or that of a shape or image, which Typst's show passes on.
1473 let fr = if spec.explicit {
1474 match res!(spec.sizing("height")) {
1475 Sizing::Fr(f) => Some(f),
1476 _ => None,
1477 }
1478 } else {
1479 match res!(field(&spec.elem, &styles, "height")) {
1480 Some(Value::Fraction(f)) => Some(f.0),
1481 _ => None,
1482 }
1483 };
1484 let above = res!(block_spacing(&spec, "above"));
1485 let below = res!(block_spacing(&spec, "below"));
1486 out.push(above);
1487 if !breakable || fr.is_some() {
1488 out.push(Child::Single(Rc::new(SingleChild { align, sticky, alone, fr, spec, cell: RefCell::new(None) })));
1489 } else {
1490 out.push(Child::Multi(Rc::new(MultiChild { align, sticky, alone, spec })));
1491 }
1492 out.push(below);
1493 Ok(())
1494}
1495
1496/// A block's spacing above or below: its own, or `spacing` where that side was not given, else the
1497/// paragraph spacing. Explicit spacing is weakness 3, fractional 2, the paragraph fallback 4.
1498fn block_spacing(spec: &BlockSpec, side: &str) -> Outcome<Child> {
1499 let v = match res!(spec.field(side)) {
1500 Some(v) => Some(v),
1501 None => res!(spec.field("spacing")),
1502 };
1503 Ok(match v {
1504 None | Some(Value::Auto) | Some(Value::None) => Child::Rel(res!(par_spacing(&spec.elem, &spec.styles)), 4),
1505 Some(v) => match spacing_of(&spec.styles, &v) {
1506 Some(Spacing::Rel(r)) => Child::Rel(r, 3),
1507 Some(Spacing::Fr(f)) => Child::Fr(f, 2),
1508 None => Child::Rel(res!(par_spacing(&spec.elem, &spec.styles)), 4),
1509 },
1510 })
1511}
1512
1513/// A placed element: Typst's `place` collection, with its errors.
1514fn collect_place(engine: &mut Engine, elem: &Content, styles: &StyleChain, out: &mut Vec<Child>) -> Outcome<()> {
1515 let alignment = match res!(field(elem, styles, "alignment")) {
1516 None => Some(Alignment { x: Some(HAlign::Start), y: None }),
1517 Some(Value::Auto) => None,
1518 Some(Value::Alignment(a)) => Some(a),
1519 Some(other) => return Err(engine.error(DiagnosticKind::Type, elem.span(), fmt!(
1520 "expected alignment or auto, found {}", other.ty().long_name()))),
1521 };
1522 let r = res!(rtl(styles));
1523 let align_x = match alignment {
1524 None => Fixed::Center,
1525 Some(a) => fix_h(a.x.unwrap_or(HAlign::Start), r),
1526 };
1527 let align_y = match alignment {
1528 None => PlaceY::Auto,
1529 Some(a) => match a.y {
1530 None => PlaceY::Flow,
1531 Some(v) => PlaceY::At(fix_v(v)),
1532 },
1533 };
1534 let parent = matches!(res!(field(elem, styles, "scope")), Some(Value::Str(s)) if s.as_str() == "parent");
1535 let float = bool_of(res!(field(elem, styles, "float")), false);
1536 match (float, align_y) {
1537 (true, PlaceY::Flow) | (true, PlaceY::At(Fixed::Center)) => return Err(engine.error(DiagnosticKind::Type, elem.span(),
1538 "vertical floating placement must be `auto`, `top`, or `bottom`")),
1539 (false, PlaceY::Auto) => return Err(engine.error_hint(DiagnosticKind::Type, elem.span(),
1540 "automatic positioning is only available for floating placement",
1541 "you can enable floating placement with `place(float: true, ..)`")),
1542 _ => (),
1543 }
1544 if !float && parent {
1545 return Err(engine.error_hint(DiagnosticKind::Type, elem.span(),
1546 "parent-scoped positioning is currently only available for floating placement",
1547 "you can enable floating placement with `place(float: true, ..)`"));
1548 }
1549 let clearance = match res!(field(elem, styles, "clearance")) {
1550 Some(Value::Length(l)) => abs_of(styles, l),
1551 _ => 1.5 * styles.font_size(),
1552 };
1553 let dx = res!(field(elem, styles, "dx")).and_then(|v| rel_of(styles, &v)).unwrap_or_default();
1554 let dy = res!(field(elem, styles, "dy")).and_then(|v| rel_of(styles, &v)).unwrap_or_default();
1555 // A float is read where its `place` stands: its location when it has one, else one handed out now.
1556 let mark = match elem.location() {
1557 Some(l) => l.0,
1558 None => engine.locator.locate(ElemKind::Place, elem.fingerprint()).0,
1559 };
1560 if float {
1561 out.push(Child::Mark(mark));
1562 }
1563 out.push(Child::Placed(Rc::new(PlacedChild {
1564 align_x,
1565 align_y,
1566 parent,
1567 float,
1568 clearance,
1569 dx,
1570 dy,
1571 alignment,
1572 mark,
1573 elem: elem.clone(),
1574 styles: styles.clone(),
1575 cell: RefCell::new(None),
1576 })));
1577 Ok(())
1578}
1579
1580// Composition
1581
1582/// A control event in flow layout: finish the region (out of room, or `true` for a column break), relay a
1583/// scope out after an insertion, or a fatal error.
1584enum Stop {
1585 Finish(bool),
1586 Relayout(bool), // `true` for the parent scope, `false` for the column
1587 Error(Error<ErrTag>),
1588}
1589
1590type FlowResult<T> = std::result::Result<T, Stop>;
1591
1592// Propagates an `Outcome` error as a fatal `Stop`.
1593macro_rules! fl {
1594 ($e:expr) => {
1595 match $e {
1596 Ok(v) => v,
1597 Err(e) => return Err(Stop::Error(e)),
1598 }
1599 };
1600}
1601
1602// Propagates any `Stop`.
1603macro_rules! st {
1604 ($e:expr) => {
1605 match $e {
1606 Ok(v) => v,
1607 Err(s) => return Err(s),
1608 }
1609 };
1610}
1611
1612/// What an insertion is known by once handled: a float by its child, a footnote by its location.
1613#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
1614pub(super) enum Skip {
1615 Child(usize),
1616 Loc(Location),
1617}
1618
1619/// The work flow layout has left: Typst's `Work`.
1620#[derive(Clone, Debug)]
1621pub(super) struct Work {
1622 pub(super) idx: usize, // the first child not yet processed
1623 pub(super) spill: Option<Rc<Spill>>,
1624 pub(super) floats: Vec<(usize, Rc<PlacedChild>)>, // floats queued for a later region, by child
1625 pub(super) footnotes: Vec<Content>, // footnotes queued for a later region
1626 pub(super) footnote_spill: Option<Vec<Frame>>, // the rest of a footnote that did not fit
1627 pub(super) tags: Vec<Pending>, // tags and marks waiting for the next frame
1628 pub(super) skips: Rc<HashMap<Skip, usize>>, // insertions already placed, and the child they belong to
1629}
1630
1631impl Work {
1632 fn new() -> Self {
1633 Self {
1634 idx: 0,
1635 spill: None,
1636 floats: Vec::new(),
1637 footnotes: Vec::new(),
1638 footnote_spill: None,
1639 tags: Vec::new(),
1640 skips: Rc::new(HashMap::new()),
1641 }
1642 }
1643
1644 fn extend_skips(&mut self, skips: &[(Skip, usize)]) {
1645 if !skips.is_empty() {
1646 let set = Rc::make_mut(&mut self.skips);
1647 for (s, at) in skips {
1648 set.insert(*s, *at);
1649 }
1650 }
1651 }
1652
1653 /// Forgets the insertions of children already passed, which are never offered again. A breakable block
1654 /// that spilled is not passed: `idx` moved beyond it when its first fragment was set, but its later
1655 /// fragments still carry what it holds -- a footnote's marker among them -- so its insertions are kept
1656 /// until the spill is done, or a footnote that split at its foot would be set again in full.
1657 fn prune(&mut self) {
1658 let live = match self.spill {
1659 Some(_) => self.idx.saturating_sub(1), // the spilled block is the child before `idx`
1660 None => self.idx,
1661 };
1662 if self.skips.values().any(|at| *at < live) {
1663 Rc::make_mut(&mut self.skips).retain(|_, at| *at >= live);
1664 }
1665 }
1666}
1667
1668#[derive(Clone, Debug)]
1669pub(super) struct ColumnConfig {
1670 pub(super) count: usize,
1671 pub(super) width: f64,
1672 pub(super) gutter: f64,
1673 pub(super) rtl: bool,
1674}
1675
1676#[derive(Clone, Debug)]
1677pub(super) struct FootnoteConfig {
1678 pub(super) separator: Content,
1679 pub(super) clearance: f64,
1680 pub(super) gap: f64,
1681 pub(super) expand: bool,
1682}
1683
1684#[derive(Clone, Debug)]
1685pub(super) struct Config {
1686 pub(super) mode: FlowMode,
1687 pub(super) shared: StyleChain,
1688 pub(super) columns: ColumnConfig,
1689 pub(super) footnote: FootnoteConfig,
1690}
1691
1692fn configuration(shared: &StyleChain, regions: &Regions, columns: usize, gutter: Rel, mode: FlowMode) -> Outcome<Config> {
1693 let count = if regions.w.is_finite() { columns.max(1) } else { 1 };
1694 let gutter = gutter.relative_to(regions.base().0);
1695 let width = (regions.w - gutter * (count as f64 - 1.0)) / count as f64;
1696 let fs = shared.font_size();
1697 let length = |v: Option<Value>, default: f64| match v {
1698 Some(Value::Length(l)) => abs_of(shared, l),
1699 _ => default * fs,
1700 };
1701 let clearance = length(res!(chain_field(shared, ElemKind::FootnoteEntry, "clearance")), 1.0);
1702 let gap = length(res!(chain_field(shared, ElemKind::FootnoteEntry, "gap")), 0.5);
1703 let separator = match res!(chain_field(shared, ElemKind::FootnoteEntry, "separator")) {
1704 Some(Value::Content(c)) => c,
1705 Some(Value::None) => Content::empty(),
1706 _ => default_separator(),
1707 };
1708 Ok(Config {
1709 mode,
1710 shared: shared.clone(),
1711 columns: ColumnConfig { count, width, gutter, rtl: res!(rtl(shared)) },
1712 footnote: FootnoteConfig {
1713 separator,
1714 clearance,
1715 gap,
1716 expand: regions.expand_x,
1717 },
1718 })
1719}
1720
1721/// Typst's footnote separator: `line(length: 30% + 0pt, stroke: 0.5pt)`.
1722fn default_separator() -> Content {
1723 let mut fields = Vec::new();
1724 if let Some(id) = ElemKind::Line.field_id("length") {
1725 fields.push((id, Value::Relative(Relative { rel: Ratio(0.3), abs: Length::zero() })));
1726 }
1727 if let Some(id) = ElemKind::Line.field_id("stroke") {
1728 fields.push((id, Value::Length(Length::pt(0.5))));
1729 }
1730 Content::new(ElemKind::Line, fields, Span::detached())
1731}
1732
1733/// Lays out one region of a flow, with its column and page insertions: Typst's `compose`.
1734fn compose(
1735 engine: &mut Engine,
1736 pull: &mut Pull,
1737 work: &mut Work,
1738 config: &Config,
1739 regions: &Regions,
1740)
1741 -> Outcome<Frame>
1742{
1743 let mut c = Composer {
1744 engine,
1745 pull,
1746 work,
1747 config,
1748 column: 0,
1749 page_base: regions.base(),
1750 page_ins: Insertions::default(),
1751 column_ins: Insertions::default(),
1752 footnote_spill: None,
1753 footnote_queue: Vec::new(),
1754 };
1755 c.page(regions)
1756}
1757
1758struct Composer<'a> {
1759 engine: &'a mut Engine,
1760 pull: &'a mut Pull,
1761 work: &'a mut Work,
1762 config: &'a Config,
1763 column: usize,
1764 page_base: (f64, f64),
1765 page_ins: Insertions,
1766 column_ins: Insertions,
1767 footnote_spill: Option<Vec<Frame>>,
1768 footnote_queue: Vec<Content>,
1769}
1770
1771impl<'a> Composer<'a> {
1772 /// A page or container region with its page-scoped insertions, relaid out whenever a parent-scoped float
1773 /// is placed.
1774 fn page(&mut self, regions: &Regions) -> Outcome<Frame> {
1775 let checkpoint = self.work.clone();
1776 let output = loop {
1777 let mut pod = regions.clone();
1778 pod.h -= self.page_ins.height();
1779 match self.page_contents(&pod) {
1780 Ok(frame) => break frame,
1781 Err(Stop::Relayout(true)) => {
1782 *self.work = checkpoint.clone();
1783 continue;
1784 },
1785 Err(Stop::Error(e)) => return Err(e),
1786 Err(_) => return Err(err!(
1787 "A column finish or column relayout escaped a column; flow composition is inconsistent."; Bug)),
1788 }
1789 };
1790 let ins = std::mem::take(&mut self.page_ins);
1791 Ok(ins.finalize(self.work, self.config, output))
1792 }
1793
1794 /// The inner contents of a page region: one column, or several stitched side by side.
1795 fn page_contents(&mut self, regions: &Regions) -> FlowResult<Frame> {
1796 let count = self.config.columns.count;
1797 if count == 1 {
1798 return self.column(regions);
1799 }
1800 let column_h = regions.h;
1801 let mut backlog = Vec::new();
1802 for h in std::iter::once(column_h).chain(regions.backlog.iter().copied()) {
1803 for _ in 0..count {
1804 backlog.push(h);
1805 }
1806 }
1807 backlog.remove(0);
1808 let mut inner = Regions {
1809 w: self.config.columns.width,
1810 h: column_h,
1811 full: regions.full,
1812 backlog,
1813 last: regions.last,
1814 expand_x: true,
1815 expand_y: regions.expand_y,
1816 };
1817 let mut output = Frame::new(regions.w, if regions.expand_y { regions.h } else { 0.0 });
1818 let mut offset = 0.0;
1819 for i in 0..count {
1820 self.column = i;
1821 let frame = st!(self.column(&inner));
1822 if !regions.expand_y && frame.h > output.h {
1823 output.h = frame.h;
1824 }
1825 let width = frame.w;
1826 let x = if self.config.columns.rtl { regions.w - offset - width } else { offset };
1827 offset += width + self.config.columns.gutter;
1828 if i == 0 && frame.has_baseline() {
1829 output.baseline = Some(frame.baseline());
1830 }
1831 output.push_frame(x, 0.0, frame);
1832 inner.next();
1833 }
1834 Ok(output)
1835 }
1836
1837 /// A column with its column insertions, relaid out whenever a column float or a footnote is placed.
1838 fn column(&mut self, regions: &Regions) -> FlowResult<Frame> {
1839 self.column_ins = Insertions::default();
1840 if let Some(spill) = self.work.footnote_spill.take() {
1841 fl!(self.footnote_spill_in(spill, regions.base()));
1842 }
1843 let checkpoint = self.work.clone();
1844 let inner = loop {
1845 let mut pod = regions.clone();
1846 pod.h -= self.column_ins.height();
1847 match self.column_contents(&pod) {
1848 Ok(frame) => break frame,
1849 Err(Stop::Relayout(false)) => {
1850 *self.work = checkpoint.clone();
1851 continue;
1852 },
1853 Err(Stop::Finish(_)) => return Err(Stop::Error(err!(
1854 "A region finish escaped distribution; flow composition is inconsistent."; Bug))),
1855 Err(other) => return Err(other),
1856 }
1857 };
1858 let queued = std::mem::take(&mut self.footnote_queue);
1859 self.work.footnotes.extend(queued);
1860 if let Some(spill) = self.footnote_spill.take() {
1861 self.work.footnote_spill = Some(spill);
1862 }
1863 let ins = std::mem::take(&mut self.column_ins);
1864 Ok(ins.finalize(self.work, self.config, inner))
1865 }
1866
1867 /// A column's in-flow contents, after the footnotes and floats queued from earlier regions.
1868 fn column_contents(&mut self, regions: &Regions) -> FlowResult<Frame> {
1869 for note in std::mem::take(&mut self.work.footnotes) {
1870 let mut r = regions.clone();
1871 st!(self.footnote(note, &mut r, 0.0, false));
1872 }
1873 for (idx, placed) in std::mem::take(&mut self.work.floats) {
1874 st!(self.float(idx, placed, regions, false, false));
1875 }
1876 distribute(self, regions)
1877 }
1878
1879 /// Places a float in its scope's top or foot area and asks for the scope to be relaid out, or queues it
1880 /// for a later region when it does not fit: Typst's `Composer::float`. `clearance` is whether in-flow
1881 /// content already stands in the region; `migratable` whether a footnote in the float may move it.
1882 fn float(&mut self, idx: usize, placed: Rc<PlacedChild>, regions: &Regions, clearance: bool, migratable: bool)
1883 -> FlowResult<()>
1884 {
1885 let key = Skip::Child(idx);
1886 if self.skipped(key) {
1887 return Ok(());
1888 }
1889 if !self.work.floats.is_empty() {
1890 self.work.floats.push((idx, placed));
1891 return Ok(());
1892 }
1893 let base = if placed.parent { self.page_base } else { regions.base() };
1894 let frame = fl!(placed.layout(self.engine, base));
1895 let remaining = if placed.parent {
1896 let n = self.config.columns.count - self.column;
1897 let mut sum = 0.0;
1898 for i in 0..n {
1899 sum += regions.nth(i).unwrap_or(0.0);
1900 }
1901 sum / self.config.columns.count as f64
1902 } else {
1903 regions.h
1904 };
1905 let clear = if clearance { placed.clearance } else { 0.0 };
1906 let need = frame.h + clear;
1907 if !fits(remaining, need) && regions.may_progress() {
1908 self.work.floats.push((idx, placed));
1909 return Ok(());
1910 }
1911 st!(self.footnotes(regions, &frame, need, false, migratable));
1912 let align_y = match placed.align_y {
1913 PlaceY::At(a) => a,
1914 _ => {
1915 // The midpoint rule: to the top when the float's centre would sit in the upper half were it set
1916 // in the flow, else to the foot.
1917 let used = base.1 - remaining;
1918 let ratio = (used + need / 2.0) / base.1;
1919 if ratio <= 0.5 { Fixed::Start } else { Fixed::End }
1920 },
1921 };
1922 let clearance = placed.clearance;
1923 let parent = placed.parent;
1924 let area = if parent { &mut self.page_ins } else { &mut self.column_ins };
1925 area.push_float(placed, clearance, frame, align_y);
1926 area.skips.push((key, idx));
1927 Err(Stop::Relayout(parent))
1928 }
1929
1930 /// Lays out the footnotes whose markers a frame (or the tags waiting for it) holds, at the root only:
1931 /// Typst's `Composer::footnotes`. `flow_need` is the in-flow space the frame takes; for a breakable
1932 /// frame each marker's own offset is used instead.
1933 fn footnotes(&mut self, regions: &Regions, frame: &Frame, flow_need: f64, breakable: bool, migratable: bool)
1934 -> FlowResult<()>
1935 {
1936 if self.config.mode != FlowMode::Root {
1937 return Ok(());
1938 }
1939 let mut notes: Vec<(f64, Content)> = Vec::new();
1940 for t in &self.work.tags {
1941 if let Pending::Tag(Tag::Start(c)) = t {
1942 if c.is(ElemKind::Footnote) {
1943 notes.push((0.0, c.clone()));
1944 }
1945 }
1946 }
1947 find_footnotes(frame, 0.0, &mut notes);
1948 if notes.is_empty() {
1949 return Ok(());
1950 }
1951 let mut relayout = false;
1952 let mut regions = regions.clone();
1953 let mut migratable = migratable && !breakable;
1954 for (y, elem) in notes {
1955 let need = if breakable { y } else { flow_need };
1956 match self.footnote(elem, &mut regions, need, migratable) {
1957 Ok(()) => (),
1958 Err(Stop::Relayout(_)) => relayout = true,
1959 Err(other) => return Err(other),
1960 }
1961 migratable = false;
1962 }
1963 if relayout {
1964 return Err(Stop::Relayout(false));
1965 }
1966 Ok(())
1967 }
1968
1969 /// One footnote into the column's foot area: Typst's `Composer::footnote`.
1970 fn footnote(&mut self, elem: Content, regions: &mut Regions, flow_need: f64, migratable: bool) -> FlowResult<()> {
1971 let loc = match elem.location() {
1972 Some(l) => l,
1973 None => return Ok(()),
1974 };
1975 if matches!(fl!(field(&elem, &self.config.shared, "body")), Some(Value::Label(_))) || self.skipped(Skip::Loc(loc)) {
1976 return Ok(());
1977 }
1978 if self.footnote_spill.is_some() || !self.footnote_queue.is_empty() {
1979 self.footnote_queue.push(elem);
1980 return Ok(());
1981 }
1982 let mut separator = None;
1983 let mut sep_need = 0.0;
1984 if self.column_ins.footnotes.is_empty() {
1985 let frame = fl!(self.layout_separator(regions.base()));
1986 sep_need += self.config.footnote.clearance + frame.h;
1987 separator = Some(frame);
1988 }
1989 let mut pod = regions.clone();
1990 pod.expand_y = false;
1991 pod.h -= flow_need + sep_need + self.config.footnote.gap;
1992 let mut frames = fl!(self.layout_entry(&elem, pod));
1993 let mut nested = Vec::new();
1994 for f in &frames {
1995 find_footnotes(f, 0.0, &mut nested);
1996 }
1997 let exist_non_empty = frames.iter().any(|f| !f.is_empty());
1998 if frames.is_empty() {
1999 frames.push(Frame::new(0.0, 0.0));
2000 }
2001 let first = frames.remove(0);
2002 let note_need = self.config.footnote.gap + first.h;
2003 if first.is_empty() && exist_non_empty {
2004 if migratable && regions.may_progress() {
2005 return Err(Stop::Finish(false));
2006 } else if regions.may_progress() || flow_need != 0.0 {
2007 self.footnote_queue.push(elem);
2008 return Ok(());
2009 }
2010 }
2011 if let Some(frame) = separator {
2012 self.column_ins.push_separator(self.config, frame);
2013 regions.h -= sep_need;
2014 }
2015 self.column_ins.push_footnote(self.config, first);
2016 self.column_ins.skips.push((Skip::Loc(loc), self.work.idx));
2017 regions.h -= note_need;
2018 if !frames.is_empty() {
2019 self.footnote_spill = Some(frames);
2020 }
2021 for (_, note) in nested {
2022 match self.footnote(note, regions, flow_need, migratable) {
2023 Ok(()) | Err(Stop::Relayout(_)) => (),
2024 Err(other) => return Err(other),
2025 }
2026 }
2027 Err(Stop::Relayout(false))
2028 }
2029
2030 /// The rest of a footnote that broke across regions, at the top of this column's foot area.
2031 fn footnote_spill_in(&mut self, mut frames: Vec<Frame>, base: (f64, f64)) -> Outcome<()> {
2032 let separator = res!(self.layout_separator(base));
2033 self.column_ins.push_separator(self.config, separator);
2034 if !frames.is_empty() {
2035 let first = frames.remove(0);
2036 self.column_ins.push_footnote(self.config, first);
2037 }
2038 if !frames.is_empty() {
2039 self.footnote_spill = Some(frames);
2040 }
2041 Ok(())
2042 }
2043
2044 fn layout_separator(&mut self, base: (f64, f64)) -> Outcome<Frame> {
2045 let regions = Regions::one(base.0, base.1, self.config.footnote.expand, false);
2046 layout_frame(self.engine, &self.config.footnote.separator, &self.config.shared, regions)
2047 }
2048
2049 /// A footnote's entry, Typst's `footnote.entry` of the note, laid out under the flow's shared styles.
2050 fn layout_entry(&mut self, elem: &Content, pod: Regions) -> Outcome<Vec<Frame>> {
2051 let id = match ElemKind::FootnoteEntry.field_id("note") {
2052 Some(id) => id,
2053 None => return Err(err!(
2054 "footnote.entry has no `note` field in its schema, so a footnote's entry cannot be built."; Unimplemented)),
2055 };
2056 let entry = Content::new(ElemKind::FootnoteEntry, vec![(id, Value::Content(elem.clone()))], elem.span());
2057 // The entry is laid out at a place made from the note's location, as Typst's `Locator::synthesize`, so it
2058 // is the same entry each time the note is composed.
2059 let place = elem.location().map(Place::synthesise);
2060 let mut frames = res!(layout_fragment_in(self.engine, place, &entry, &self.config.shared, pod));
2061 // The entry is read after its footnote for introspection.
2062 if let Some(loc) = elem.location() {
2063 for f in &mut frames {
2064 f.parent = Some(loc.0);
2065 }
2066 }
2067 Ok(frames)
2068 }
2069
2070 /// A breakable block's fragment from the continuation `from`, or the one already laid out in this region
2071 /// from the same state.
2072 fn fragment(&mut self, child: &Rc<MultiChild>, from: Option<&Rc<Spill>>, regions: &Regions)
2073 -> Outcome<Fragment>
2074 {
2075 let key = regions.key();
2076 let c = Rc::as_ptr(child) as usize;
2077 let f = from.map(|s| Rc::as_ptr(s) as usize).unwrap_or(0);
2078 if let Some(m) = self.pull.memo.iter().find(|m| m.child == c && m.from == f && m.key == key) {
2079 return Ok(m.out.clone());
2080 }
2081 let out = res!(child.fragment(self.engine, from, regions));
2082 self.pull.memo.push(Memo { child: c, from: f, key, out: out.clone() });
2083 Ok(out)
2084 }
2085
2086 fn skipped(&self, key: Skip) -> bool {
2087 self.work.skips.contains_key(&key)
2088 || self.page_ins.skips.iter().any(|(k, _)| *k == key)
2089 || self.column_ins.skips.iter().any(|(k, _)| *k == key)
2090 }
2091
2092 fn insertion_width(&self) -> f64 { self.column_ins.width.max(self.page_ins.width) }
2093}
2094
2095/// The floats and footnotes of a region's top and foot areas.
2096#[derive(Default)]
2097struct Insertions {
2098 top: Vec<(Rc<PlacedChild>, Frame)>,
2099 bottom: Vec<(Rc<PlacedChild>, Frame)>,
2100 footnotes: Vec<Frame>,
2101 separator: Option<Frame>,
2102 top_size: f64,
2103 bottom_size: f64,
2104 width: f64,
2105 skips: Vec<(Skip, usize)>,
2106}
2107
2108impl Insertions {
2109 fn push_float(&mut self, placed: Rc<PlacedChild>, clearance: f64, frame: Frame, align_y: Fixed) {
2110 self.width = self.width.max(frame.w);
2111 let amount = frame.h + clearance;
2112 if align_y == Fixed::Start {
2113 self.top_size += amount;
2114 self.top.push((placed, frame));
2115 } else {
2116 self.bottom_size += amount;
2117 self.bottom.push((placed, frame));
2118 }
2119 }
2120
2121 fn push_footnote(&mut self, config: &Config, frame: Frame) {
2122 self.width = self.width.max(frame.w);
2123 self.bottom_size += config.footnote.gap + frame.h;
2124 self.footnotes.push(frame);
2125 }
2126
2127 fn push_separator(&mut self, config: &Config, frame: Frame) {
2128 self.width = self.width.max(frame.w);
2129 self.bottom_size += config.footnote.clearance + frame.h;
2130 self.separator = Some(frame);
2131 }
2132
2133 fn height(&self) -> f64 { self.top_size + self.bottom_size }
2134
2135 /// The region's frame: top floats, the in-flow contents, then foot floats, the separator and the
2136 /// footnotes, as Typst orders them.
2137 fn finalize(self, work: &mut Work, config: &Config, inner: Frame) -> Frame {
2138 work.extend_skips(&self.skips);
2139 if self.top.is_empty() && self.bottom.is_empty() && self.separator.is_none() && self.footnotes.is_empty() {
2140 return inner;
2141 }
2142 let (w, h) = (inner.w, inner.h + self.height());
2143 let mut output = Frame::new(w, h);
2144 let mut top = 0.0;
2145 let mut bottom = h - self.bottom_size;
2146 for (p, frame) in self.top {
2147 let x = p.align_x.position(w - frame.w) + p.dx.relative_to(w);
2148 let y = top + p.dy.relative_to(h);
2149 top += frame.h + p.clearance;
2150 output.push_frame(x, y, frame);
2151 }
2152 if inner.has_baseline() {
2153 output.baseline = Some(self.top_size + inner.baseline());
2154 }
2155 output.push_frame(0.0, self.top_size, inner);
2156 for (p, frame) in self.bottom {
2157 bottom += p.clearance;
2158 let x = p.align_x.position(w - frame.w) + p.dx.relative_to(w);
2159 let y = bottom + p.dy.relative_to(h);
2160 bottom += frame.h;
2161 output.push_frame(x, y, frame);
2162 }
2163 if let Some(frame) = self.separator {
2164 bottom += config.footnote.clearance;
2165 let fh = frame.h;
2166 output.push_frame(0.0, bottom, frame);
2167 bottom += fh;
2168 }
2169 for frame in self.footnotes {
2170 bottom += config.footnote.gap;
2171 let fh = frame.h;
2172 output.push_frame(0.0, bottom, frame);
2173 bottom += fh;
2174 }
2175 output
2176 }
2177}
2178
2179// Distribution
2180
2181/// An item laid out in a region, not yet aligned.
2182#[derive(Clone, Debug)]
2183enum DItem {
2184 Tag(Pending),
2185 Abs(f64, u8), // spacing and its weakness
2186 Fr(f64, u8, Option<Rc<SingleChild>>), // fractional spacing, or a fractional block
2187 Frame(Frame, Align2),
2188 Placed(Frame, Rc<PlacedChild>), // an absolutely placed child
2189}
2190
2191struct Snapshot {
2192 work: Work,
2193 items: usize,
2194}
2195
2196/// Distributes as many children as fit into the first region and returns its frame: Typst's `distribute`.
2197fn distribute(c: &mut Composer, regions: &Regions) -> FlowResult<Frame> {
2198 let mut d = Distributor { c, regions: regions.clone(), items: Vec::new(), sticky: None, stickable: None };
2199 let init = d.snapshot();
2200 let forced = match d.run() {
2201 Ok(()) => fl!(d.all_placed()),
2202 Err(Stop::Finish(f)) => f,
2203 Err(other) => return Err(other),
2204 };
2205 d.finalize(regions, init, forced)
2206}
2207
2208struct Distributor<'c, 'a> {
2209 c: &'c mut Composer<'a>,
2210 regions: Regions,
2211 items: Vec<DItem>,
2212 sticky: Option<Snapshot>,
2213 stickable: Option<bool>,
2214}
2215
2216impl<'c, 'a> Distributor<'c, 'a> {
2217 fn run(&mut self) -> FlowResult<()> {
2218 if let Some(spill) = self.c.work.spill.take() {
2219 st!(self.multi_spill(spill));
2220 }
2221 loop {
2222 let idx = self.c.work.idx;
2223 let child = match fl!(self.c.pull.get(self.c.engine, idx)) {
2224 Some(c) => c,
2225 None => break,
2226 };
2227 st!(self.child(idx, &child));
2228 self.c.work.idx += 1;
2229 }
2230 Ok(())
2231 }
2232
2233 /// Is everything placed and nothing left in the work, now the children have run out?
2234 fn all_placed(&mut self) -> Outcome<bool> {
2235 let w = &self.c.work;
2236 let pending = w.spill.is_some() || !w.floats.is_empty() || w.footnote_spill.is_some() || !w.footnotes.is_empty();
2237 Ok(!pending && res!(self.c.pull.get(self.c.engine, self.c.work.idx)).is_none())
2238 }
2239
2240 fn child(&mut self, idx: usize, child: &Child) -> FlowResult<()> {
2241 match child {
2242 Child::Tag(t) => self.c.work.tags.push(Pending::Tag(t.clone())),
2243 Child::Mark(m) => self.c.work.tags.push(Pending::Mark(*m)),
2244 Child::Rel(r, w) => self.rel(*r, *w),
2245 Child::Fr(f, w) => self.fr(*f, *w),
2246 Child::Line(l) => st!(self.line(l)),
2247 Child::Single(s) => st!(self.single(s)),
2248 Child::Multi(m) => st!(self.multi(m)),
2249 Child::Placed(p) => st!(self.placed(idx, p)),
2250 Child::Flush => st!(self.flush()),
2251 Child::Break(weak) => st!(self.break_(*weak)),
2252 }
2253 Ok(())
2254 }
2255
2256 fn flush_tags(&mut self) {
2257 if !self.c.work.tags.is_empty() {
2258 for t in self.c.work.tags.drain(..) {
2259 self.items.push(DItem::Tag(t));
2260 }
2261 }
2262 }
2263
2264 fn rel(&mut self, r: Rel, weakness: u8) {
2265 let amount = r.relative_to(self.regions.base().1);
2266 if weakness > 0 && !self.keep_weak_rel(amount, weakness) {
2267 return;
2268 }
2269 self.regions.h -= amount;
2270 self.items.push(DItem::Abs(amount, weakness));
2271 }
2272
2273 fn fr(&mut self, f: f64, weakness: u8) {
2274 if weakness > 0 && !self.keep_weak_fr(f, weakness) {
2275 return;
2276 }
2277 self.trim_spacing();
2278 self.items.push(DItem::Fr(f, weakness, None));
2279 }
2280
2281 /// Keeps weak spacing only where something before it supports it, merging it into a preceding weak
2282 /// spacing: the stronger, or the larger of equal strength, wins.
2283 fn keep_weak_rel(&mut self, amount: f64, weakness: u8) -> bool {
2284 let mut i = self.items.len();
2285 while i > 0 {
2286 i -= 1;
2287 match self.items[i] {
2288 DItem::Abs(prev, pw) if pw >= 1 => {
2289 if weakness <= pw && (weakness < pw || amount > prev) {
2290 self.regions.h -= amount - prev;
2291 self.items[i] = DItem::Abs(amount, weakness);
2292 }
2293 return false;
2294 },
2295 DItem::Tag(_) | DItem::Abs(_, _) | DItem::Placed(..) => (),
2296 DItem::Fr(_, _, None) => return false,
2297 DItem::Frame(..) | DItem::Fr(_, _, Some(_)) => return true,
2298 }
2299 }
2300 false
2301 }
2302
2303 fn keep_weak_fr(&mut self, f: f64, weakness: u8) -> bool {
2304 let mut i = self.items.len();
2305 while i > 0 {
2306 i -= 1;
2307 match self.items[i] {
2308 DItem::Fr(prev, pw, None) if pw >= 1 => {
2309 if weakness <= pw && (weakness < pw || f > prev) {
2310 self.items[i] = DItem::Fr(f, weakness, None);
2311 }
2312 return false;
2313 },
2314 DItem::Tag(_) | DItem::Abs(..) | DItem::Placed(..) => (),
2315 DItem::Fr(_, _, None) => return true,
2316 DItem::Frame(..) | DItem::Fr(_, _, Some(_)) => return true,
2317 }
2318 }
2319 false
2320 }
2321
2322 /// Drops the last weak spacing, if nothing but tags, strong spacing and placed items follow it.
2323 fn trim_spacing(&mut self) {
2324 let mut i = self.items.len();
2325 while i > 0 {
2326 i -= 1;
2327 match self.items[i] {
2328 DItem::Abs(amount, w) if w >= 1 => {
2329 self.regions.h += amount;
2330 self.items.remove(i);
2331 break;
2332 },
2333 DItem::Fr(_, w, None) if w >= 1 => {
2334 self.items.remove(i);
2335 break;
2336 },
2337 DItem::Tag(_) | DItem::Abs(..) | DItem::Placed(..) => (),
2338 DItem::Frame(..) | DItem::Fr(..) => break,
2339 }
2340 }
2341 }
2342
2343 /// The trailing weak spacing, which a float may reclaim because it would collapse at a break.
2344 fn weak_spacing(&self) -> f64 {
2345 for item in self.items.iter().rev() {
2346 match item {
2347 DItem::Abs(amount, w) if *w >= 1 => return *amount,
2348 DItem::Tag(_) | DItem::Abs(..) | DItem::Placed(..) => (),
2349 DItem::Frame(..) | DItem::Fr(..) => break,
2350 }
2351 }
2352 0.0
2353 }
2354
2355 fn line(&mut self, line: &LineChild) -> FlowResult<()> {
2356 if !fits(self.regions.h, line.frame.h) && self.regions.may_progress() {
2357 return Err(Stop::Finish(false));
2358 }
2359 // A line whose widow or orphan partner does not fit here, but would in the next region, goes there.
2360 if !fits(self.regions.h, line.need) && self.regions.nth(1).map(|h| fits(h, line.need)).unwrap_or(false) {
2361 return Err(Stop::Finish(false));
2362 }
2363 self.frame(line.frame.clone(), line.align, false, false)
2364 }
2365
2366 fn single(&mut self, single: &Rc<SingleChild>) -> FlowResult<()> {
2367 let (bw, bh) = self.regions.base();
2368 let frame = fl!(single.layout(self.c.engine, bw, bh, self.regions.expand_x, self.regions.expand_y));
2369 if let Some(fr) = single.fr {
2370 let regions = self.regions.clone();
2371 st!(self.c.footnotes(&regions, &frame, 0.0, false, true));
2372 self.flush_tags();
2373 self.items.push(DItem::Fr(fr, 0, Some(single.clone())));
2374 return Ok(());
2375 }
2376 if !fits(self.regions.h, frame.h) && self.regions.may_progress() {
2377 return Err(Stop::Finish(false));
2378 }
2379 self.frame(frame, single.align, single.sticky, false)
2380 }
2381
2382 /// A breakable block's first fragment, in this region. The rest of the block waits in the work, as the
2383 /// continuation that lays out its next fragment.
2384 fn multi(&mut self, multi: &Rc<MultiChild>) -> FlowResult<()> {
2385 if self.regions.is_full() {
2386 return Err(Stop::Finish(false));
2387 }
2388 let frag = fl!(self.c.fragment(multi, None, &self.regions));
2389 // A first fragment left empty while a later one is not leaves this region alone, so that no invisible
2390 // orphan ends it.
2391 if frag.skip && self.regions.may_progress() {
2392 return Err(Stop::Finish(false));
2393 }
2394 st!(self.frame(frag.frame, multi.align, multi.sticky, true));
2395 if let Some(next) = frag.next {
2396 self.c.work.spill = Some(next);
2397 self.c.work.idx += 1;
2398 return Err(Stop::Finish(false));
2399 }
2400 Ok(())
2401 }
2402
2403 /// The rest of a breakable block, in this region: the fragment its continuation lays out.
2404 fn multi_spill(&mut self, spill: Rc<Spill>) -> FlowResult<()> {
2405 if self.regions.is_full() {
2406 self.c.work.spill = Some(spill);
2407 return Err(Stop::Finish(false));
2408 }
2409 let child = spill.child.clone();
2410 let frag = fl!(self.c.fragment(&child, Some(&spill), &self.regions));
2411 st!(self.frame(frag.frame, child.align, false, true));
2412 if let Some(next) = frag.next {
2413 self.c.work.spill = Some(next);
2414 return Err(Stop::Finish(false));
2415 }
2416 Ok(())
2417 }
2418
2419 /// An in-flow frame, from a line or a block: sticky blocks remember where a run of them began, so the
2420 /// run can move with the block it sticks to.
2421 fn frame(&mut self, frame: Frame, align: Align2, sticky: bool, breakable: bool) -> FlowResult<()> {
2422 if sticky {
2423 if self.sticky.is_none() {
2424 let progress = self.regions.may_progress();
2425 if *self.stickable.get_or_insert(progress) {
2426 self.sticky = Some(self.snapshot());
2427 }
2428 }
2429 } else if !frame.is_empty() {
2430 self.sticky = None;
2431 self.stickable = None;
2432 }
2433 let regions = self.regions.clone();
2434 st!(self.c.footnotes(&regions, &frame, frame.h, breakable, true));
2435 self.regions.h -= frame.h;
2436 self.flush_tags();
2437 self.items.push(DItem::Frame(frame, align));
2438 Ok(())
2439 }
2440
2441 fn placed(&mut self, idx: usize, placed: &Rc<PlacedChild>) -> FlowResult<()> {
2442 if placed.float {
2443 let weak = self.weak_spacing();
2444 self.regions.h += weak;
2445 let clearance = self.items.iter().any(|i| matches!(i, DItem::Frame(..)));
2446 let regions = self.regions.clone();
2447 st!(self.c.float(idx, placed.clone(), &regions, clearance, true));
2448 self.regions.h -= weak;
2449 } else {
2450 let frame = fl!(placed.layout(self.c.engine, self.regions.base()));
2451 let regions = self.regions.clone();
2452 st!(self.c.footnotes(&regions, &frame, 0.0, true, true));
2453 self.flush_tags();
2454 self.items.push(DItem::Placed(frame, placed.clone()));
2455 }
2456 Ok(())
2457 }
2458
2459 fn flush(&mut self) -> FlowResult<()> {
2460 if !self.c.work.floats.is_empty() {
2461 return Err(Stop::Finish(false));
2462 }
2463 Ok(())
2464 }
2465
2466 fn break_(&mut self, weak: bool) -> FlowResult<()> {
2467 if (!weak || !self.items.is_empty()) && (!self.regions.backlog.is_empty() || self.regions.last.is_some()) {
2468 self.c.work.idx += 1;
2469 return Err(Stop::Finish(true));
2470 }
2471 Ok(())
2472 }
2473
2474 fn snapshot(&self) -> Snapshot { Snapshot { work: self.c.work.clone(), items: self.items.len() } }
2475
2476 fn restore(&mut self, s: Snapshot) {
2477 *self.c.work = s.work;
2478 self.items.truncate(s.items);
2479 }
2480
2481 fn migratable(&self, item: &DItem) -> bool {
2482 match item {
2483 DItem::Tag(_) => true,
2484 DItem::Frame(f, _) => f.w == 0.0 && f.h == 0.0 && f.items.iter().all(|(_, _, i)|
2485 matches!(i, Item::Tag(_) | Item::Node(Node::Mark(_)))),
2486 DItem::Placed(_, p) => !p.float,
2487 _ => false,
2488 }
2489 }
2490
2491 /// Arranges the items into the region's frame: alignment, and fractional spacing and blocks sharing the
2492 /// free space. A region that ended on a sticky run hands that run on to the next.
2493 fn finalize(mut self, region: &Regions, init: Snapshot, forced: bool) -> FlowResult<Frame> {
2494 if forced {
2495 self.flush_tags();
2496 } else if !self.items.is_empty() && self.items.iter().all(|i| self.migratable(i)) {
2497 self.restore(init);
2498 } else if let Some(s) = self.sticky.take() {
2499 self.restore(s);
2500 }
2501 self.trim_spacing();
2502
2503 let mut frs = 0.0;
2504 let mut used = (0.0f64, 0.0f64);
2505 let mut has_fr_child = false;
2506 for item in &self.items {
2507 match item {
2508 DItem::Abs(v, _) => used.1 += v,
2509 DItem::Fr(v, _, child) => {
2510 frs += v;
2511 has_fr_child |= child.is_some();
2512 },
2513 DItem::Frame(f, _) => {
2514 used.1 += f.h;
2515 used.0 = used.0.max(f.w);
2516 },
2517 DItem::Tag(_) | DItem::Placed(..) => (),
2518 }
2519 }
2520 let mut fr_space = 0.0;
2521 if frs > 0.0 && region.h.is_finite() {
2522 fr_space = region.h - used.1;
2523 used.1 = region.h;
2524 }
2525 let mut fr_frames = Vec::new();
2526 if has_fr_child {
2527 for item in &self.items {
2528 if let DItem::Fr(v, _, Some(single)) = item {
2529 let length = share(*v, frs, fr_space);
2530 let frame = fl!(single.layout(self.c.engine, region.w, length, region.expand_x, region.expand_y));
2531 used.0 = used.0.max(frame.w);
2532 fr_frames.push(frame);
2533 }
2534 }
2535 }
2536 if !region.expand_x {
2537 used.0 = used.0.max(self.c.insertion_width());
2538 }
2539 let size = (
2540 if region.expand_x { region.w } else { used.0.min(region.w) },
2541 if region.expand_y { region.h } else { used.1.min(region.h) },
2542 );
2543 let free = size.1 - used.1;
2544
2545 let mut output = Frame::new(size.0, size.1);
2546 let mut ruler = Fixed::Start;
2547 let mut offset = 0.0;
2548 let mut fr_frames = fr_frames.into_iter();
2549 let mut baseline_set = false;
2550 for item in std::mem::take(&mut self.items) {
2551 match item {
2552 DItem::Tag(t) => {
2553 let y = offset + ruler.position(free);
2554 output.push(0.0, y, t.item());
2555 },
2556 DItem::Abs(v, _) => offset += v,
2557 DItem::Fr(v, _, single) => {
2558 let length = share(v, frs, fr_space);
2559 if let Some(s) = single {
2560 if let Some(frame) = fr_frames.next() {
2561 let x = s.align.x.position(size.0 - frame.w);
2562 output.push_frame(x, offset, frame);
2563 }
2564 }
2565 offset += length;
2566 },
2567 DItem::Frame(frame, align) => {
2568 ruler = ruler.max(align.y);
2569 let x = align.x.position(size.0 - frame.w);
2570 let y = offset + ruler.position(free);
2571 offset += frame.h;
2572 if !baseline_set {
2573 if frame.has_baseline() {
2574 output.baseline = Some(y + frame.baseline());
2575 }
2576 baseline_set = true;
2577 }
2578 output.push_frame(x, y, frame);
2579 },
2580 DItem::Placed(frame, p) => {
2581 let x = p.align_x.position(size.0 - frame.w);
2582 let y = match p.align_y {
2583 PlaceY::At(a) => a.position(size.1 - frame.h),
2584 _ => offset + ruler.position(free),
2585 };
2586 let dx = p.dx.relative_to(size.0);
2587 let dy = p.dy.relative_to(size.1);
2588 output.push_frame(x + dx, y + dy, frame);
2589 },
2590 }
2591 }
2592 Ok(output)
2593 }
2594}
2595
2596/// A fraction's share of the remaining space, Typst's `Fr::share`.
2597fn share(fr: f64, total: f64, remaining: f64) -> f64 {
2598 let ratio = fr / total;
2599 if ratio.is_finite() && remaining.is_finite() { (ratio * remaining).max(0.0) } else { 0.0 }
2600}
2601
2602// Blocks
2603
2604/// An unbreakable block, Typst's `layout_single_block`: sized, inset, filled, stroked and clipped.
2605fn layout_single(engine: &mut Engine, spec: &BlockSpec, region: &Regions) -> Outcome<Frame> {
2606 let width = res!(spec.sizing("width"));
2607 layout_single_sized(engine, spec, region, width)
2608}
2609
2610/// An inline `box` as one frame, Typst's `layout_box`: sized, inset, clipped, filled and stroked as an
2611/// unbreakable block is, then its baseline moved. `share` is the width a fractional `width` takes. The
2612/// region is the line's: relative sizes resolve against its base.
2613pub fn layout_box(engine: &mut Engine, elem: &Content, styles: &StyleChain, region: Region, share: Option<f64>)
2614 -> Outcome<Frame>
2615{
2616 let body = match res!(field(elem, styles, "body")) {
2617 Some(Value::Content(c)) => Body::Content(c),
2618 _ => Body::Empty,
2619 };
2620 let spec = res!(BlockSpec::new(elem.clone(), styles, body, true));
2621 let width = match share {
2622 Some(w) => Sizing::Rel(Rel::pt(w)),
2623 None => res!(spec.sizing("width")),
2624 };
2625 let mut frame = res!(layout_single_sized(engine, &spec, &Regions::from_region(region), width));
2626 // The baseline moves after the size and inset are final, so a relative shift reads the final height.
2627 let (at, shift) = match res!(field(elem, styles, "baseline")) {
2628 Some(Value::Dict(d)) => (d.get("at").cloned(), d.get("shift").cloned()),
2629 Some(v @ Value::Alignment(_)) => (Some(v), None),
2630 Some(Value::Auto) | Some(Value::None) | None => (None, None),
2631 Some(v) => (None, Some(v)),
2632 };
2633 if let Some(Value::Alignment(a)) = at {
2634 let pos = match a.y {
2635 Some(VAlign::Top) => 0.0,
2636 Some(VAlign::Horizon) => frame.h / 2.0,
2637 Some(VAlign::Bottom) => frame.h,
2638 None => frame.baseline(),
2639 };
2640 frame.baseline = Some(pos);
2641 }
2642 if let Some(v) = shift {
2643 let by = rel_of(styles, &v).map(|r| r.relative_to(frame.h)).unwrap_or(0.0);
2644 if by != 0.0 {
2645 frame.baseline = Some(frame.baseline() - by);
2646 }
2647 }
2648 Ok(frame)
2649}
2650
2651fn layout_single_sized(engine: &mut Engine, spec: &BlockSpec, region: &Regions, width: Sizing) -> Outcome<Frame> {
2652 let styles = &spec.styles;
2653 let height = res!(spec.sizing("height"));
2654 let inset = sides_rel(styles, res!(spec.field("inset")));
2655 let pod = unbreakable_pod(width, height, &inset, region.w, region.h);
2656 let mut frame = match &spec.body {
2657 Body::Empty => Frame::new(0.0, 0.0),
2658 Body::Content(c) => res!(layout_frame_in(engine, spec.elem.place(), c, styles, pod.clone())),
2659 Body::Layouter => {
2660 let mut p = pod.clone();
2661 p.expand_x = (pod.expand_x || region.expand_x) && pod.w.is_finite();
2662 p.expand_y = (pod.expand_y || region.expand_y) && pod.h.is_finite();
2663 res!(layout_single_layouter(engine, &spec.elem, styles, &p, &pod))
2664 },
2665 };
2666 if pod.expand_x {
2667 frame.w = pod.w;
2668 }
2669 if pod.expand_y {
2670 frame.h = pod.h;
2671 }
2672 if !sides_zero(&inset) {
2673 grow(&mut frame, &inset);
2674 }
2675 res!(decorate(engine, spec, &mut frame, true));
2676 frame.modify(&spec.mods);
2677 if spec.explicit && spec.elem.label().is_some() {
2678 frame.label();
2679 }
2680 Ok(frame)
2681}
2682
2683/// Is the element a grid or a table? Typst sizes one to its columns and rows, never to the region it is in.
2684fn is_grid(elem: &Content) -> bool {
2685 matches!(elem.kind(), Some(ElemKind::Grid | ElemKind::Table))
2686}
2687
2688/// A fragment's body laid out, before it is sized, inset or painted.
2689struct Laid {
2690 frame: Frame,
2691 tall: Option<f64>, // the height an expanding block's frame is given
2692 pod: Regions,
2693 next: Option<Rc<Spill>>,
2694}
2695
2696impl MultiChild {
2697 /// A breakable block, Typst's `layout_multi_block`, one fragment at a time: the first (`from` none), or
2698 /// the one after those the continuation `from` has laid out. The body is flowed into the region, the
2699 /// frame then sized, inset, clipped, filled and stroked, and the continuation returned unless the block
2700 /// ended here. A first fragment left empty while a later one is not takes no fill, and is flagged so that
2701 /// the flow puts the block in the next region whole, as Typst does.
2702 fn fragment(self: &Rc<Self>, engine: &mut Engine, from: Option<&Rc<Spill>>, regions: &Regions)
2703 -> Outcome<Fragment>
2704 {
2705 let spec = &self.spec;
2706 let styles = &spec.styles;
2707 let mut own = regions.clone();
2708 own.expand_y &= self.alone;
2709 let inset = sides_rel(styles, res!(spec.field("inset")));
2710 let Laid { mut frame, tall, pod, next } = res!(self.lay(engine, from, &own));
2711 let first = from.is_none();
2712 let skip = first && frame.is_empty() && match &next {
2713 Some(n) => res!(self.later(engine, n, &own)),
2714 None => false,
2715 };
2716 if pod.expand_x {
2717 frame.w = pod.w;
2718 }
2719 if pod.expand_y {
2720 if let Some(h) = tall {
2721 frame.h = h;
2722 }
2723 }
2724 if !sides_zero(&inset) {
2725 grow(&mut frame, &inset);
2726 }
2727 res!(decorate(engine, spec, &mut frame, !skip));
2728 frame.modify(&spec.mods);
2729 // A label goes on every frame but an empty orphan one, which it would make non-empty.
2730 if spec.explicit && spec.elem.label().is_some() && !skip {
2731 frame.label();
2732 }
2733 Ok(Fragment { frame, next, skip })
2734 }
2735
2736 /// One fragment's body, as the continuation `from` (or the start) lays it out in `regions`, a layer of its
2737 /// own as Typst's `layout_multi_block` is.
2738 fn lay(self: &Rc<Self>, engine: &mut Engine, from: Option<&Rc<Spill>>, regions: &Regions) -> Outcome<Laid> {
2739 engine.descend(|engine| self.lay_in(engine, from, regions))
2740 }
2741
2742 fn lay_in(self: &Rc<Self>, engine: &mut Engine, from: Option<&Rc<Spill>>, regions: &Regions) -> Outcome<Laid> {
2743 let spec = &self.spec;
2744 let styles = &spec.styles;
2745 let width = res!(spec.sizing("width"));
2746 let height = res!(spec.sizing("height"));
2747 let inset = sides_rel(styles, res!(spec.field("inset")));
2748 let k = from.map(|s| s.k).unwrap_or(0);
2749 // A fixed height is spread over the regions it spans: its whole, and what is left of it.
2750 let fixed = match (from, height) {
2751 (Some(s), _) => s.fixed,
2752 (None, Sizing::Rel(r)) => {
2753 let whole = r.relative_to(regions.full);
2754 Some((whole, whole))
2755 },
2756 (None, _) => None,
2757 };
2758 let pod = breakable_pod(width, height, &inset, regions, fixed);
2759 let mut nested = match from {
2760 Some(s) => s.nested.clone(),
2761 None => res!(self.start(engine, &pod, regions)),
2762 };
2763 let (frame, done, tall) = match &mut nested {
2764 Nested::Flow(cursor, padding) => {
2765 let inner = self.inner(&pod, regions);
2766 let pod_k = match padding {
2767 Some(pad) => pad_regions(&inner, pad),
2768 None => inner,
2769 };
2770 // The body's flow is the fragment layer Typst's `layout_fragment` is.
2771 let (mut f, done) = res!(engine.descend(|engine| -> Outcome<(Frame, bool)> {
2772 let f = res!(cursor.region(engine, &pod_k));
2773 let done = res!(cursor.is_done(engine));
2774 Ok((f, done))
2775 }));
2776 if let Some(pad) = padding {
2777 grow(&mut f, pad);
2778 }
2779 let done = done && (!pod_k.expand_y || pod_k.backlog.is_empty());
2780 (f, done, Some(pod.h))
2781 },
2782 Nested::Frames(q, pod0) => {
2783 let f = q.pop_front().unwrap_or_default();
2784 (f, q.is_empty(), pod0.nth(k))
2785 },
2786 };
2787 let next = if done {
2788 None
2789 } else {
2790 let fixed = fixed.map(|(whole, left)| (whole, (left - pod.h).max(0.0)));
2791 Some(Rc::new(Spill { child: self.clone(), nested, k: k + 1, fixed }))
2792 };
2793 Ok(Laid { frame, tall, pod, next })
2794 }
2795
2796 /// Does a fragment after the first hold anything? Typst judges this on the whole block laid out at once;
2797 /// here the later fragments are laid out one at a time, each dropped as soon as it is seen, until one with
2798 /// something in it turns up or the block ends. The regions are the ones the block's own come from.
2799 fn later(self: &Rc<Self>, engine: &mut Engine, from: &Rc<Spill>, regions: &Regions) -> Outcome<bool> {
2800 let mut r = regions.clone();
2801 let mut cur = from.clone();
2802 while r.may_break() {
2803 r.next();
2804 let laid = res!(self.lay(engine, Some(&cur), &r));
2805 if !laid.frame.is_empty() {
2806 return Ok(true);
2807 }
2808 match laid.next {
2809 Some(n) => cur = n,
2810 None => return Ok(false),
2811 }
2812 }
2813 Ok(false)
2814 }
2815
2816 /// The regions a layout routine lays its body out in: the block's own, expanded as its parent's are. A
2817 /// grid or table takes none of the parent's expansion: its frame is as wide as its columns and as tall
2818 /// as its rows whatever the region, so that `align` has room to place it, alone on a page or not. A
2819 /// fractional column or row still fills the region, through the size of the plan.
2820 fn inner(&self, pod: &Regions, regions: &Regions) -> Regions {
2821 let mut p = pod.clone();
2822 if matches!(self.spec.body, Body::Layouter) {
2823 let from = !is_grid(&self.spec.elem);
2824 p.expand_x = (pod.expand_x || (from && regions.expand_x)) && pod.w.is_finite();
2825 p.expand_y = (pod.expand_y || (from && regions.expand_y)) && pod.h.is_finite();
2826 }
2827 p
2828 }
2829
2830 /// What lays out the block's fragments, made when the first is asked for. A body laid out as one piece
2831 /// (an auto-width block, a grid, a stack) is laid out whole here, with the regions as they stand, and
2832 /// handed out a frame at a time: Typst equalises the widths of an auto-width block's fragments, which
2833 /// needs them all.
2834 fn start(&self, engine: &mut Engine, pod: &Regions, regions: &Regions) -> Outcome<Nested> {
2835 let spec = &self.spec;
2836 let styles = &spec.styles;
2837 match &spec.body {
2838 Body::Empty => {
2839 let mut v = VecDeque::new();
2840 v.push_back(Frame::new(0.0, 0.0));
2841 if pod.expand_y {
2842 for _ in 0..pod.backlog.len() {
2843 v.push_back(Frame::new(0.0, 0.0));
2844 }
2845 }
2846 Ok(Nested::Frames(v, pod.clone()))
2847 },
2848 Body::Content(c) => {
2849 let place = spec.elem.place();
2850 if pod.expand_x {
2851 let cursor = res!(flow_cursor(engine, place, c, styles, pod, 1, Rel::zero(), c.span()));
2852 return Ok(Nested::Flow(Box::new(cursor), None));
2853 }
2854 let mut frags = res!(layout_fragment_in(engine, place, c, styles, pod.clone()));
2855 // An auto-width body that came out at different widths in different regions is relaid out at the
2856 // widest, so every fragment of the block is as wide as the others.
2857 if frags.windows(2).any(|w| (w[0].w - w[1].w).abs() >= EPS) {
2858 let max = frags.iter().map(|f| f.w).fold(0.0, f64::max);
2859 let mut p = pod.clone();
2860 p.w = max;
2861 p.expand_x = true;
2862 frags = res!(layout_fragment_in(engine, place, c, styles, p));
2863 }
2864 Ok(Nested::Frames(frags.into(), pod.clone()))
2865 },
2866 Body::Layouter => {
2867 let inner = self.inner(pod, regions);
2868 let elem = &spec.elem;
2869 match elem.kind() {
2870 Some(ElemKind::Pad) => {
2871 let (padding, body) = res!(pad_parts(elem, styles));
2872 let cursor = res!(flow_cursor(
2873 engine, elem.place(), &body, styles, &pad_regions(&inner, &padding), 1, Rel::zero(), elem.span()));
2874 Ok(Nested::Flow(Box::new(cursor), Some(padding)))
2875 },
2876 Some(ElemKind::Columns) => {
2877 let (count, gutter, body) = res!(columns_parts(engine, elem, styles));
2878 let cursor = res!(flow_cursor(engine, elem.place(), &body, styles, &inner, count, gutter, elem.span()));
2879 Ok(Nested::Flow(Box::new(cursor), None))
2880 },
2881 Some(ElemKind::Layout) => {
2882 let content = res!(layout_content(engine, elem, styles, inner.base()));
2883 let cursor = res!(flow_cursor(engine, elem.place(), &content, styles, &inner, 1, Rel::zero(), content.span()));
2884 Ok(Nested::Flow(Box::new(cursor), None))
2885 },
2886 _ => {
2887 let frames = res!(layout_multi_layouter(engine, elem, styles, &inner));
2888 Ok(Nested::Frames(frames.into(), pod.clone()))
2889 },
2890 }
2891 },
2892 }
2893 }
2894}
2895
2896/// A flow over the realised body of a container, to be filled region by region. The body is realised at
2897/// `place`, the container's.
2898#[allow(clippy::too_many_arguments)]
2899fn flow_cursor(
2900 engine: &mut Engine,
2901 place: Option<Place>,
2902 content: &Content,
2903 styles: &StyleChain,
2904 regions: &Regions,
2905 columns: usize,
2906 gutter: Rel,
2907 span: Span,
2908)
2909 -> Outcome<FlowCursor>
2910{
2911 engine.descend_fragment(span, |engine| {
2912 let (pairs, inline) = res!(engine.within(place, |engine| realise::realise_fragment(engine, content, styles)));
2913 let mode = if inline { FlowMode::Inline } else { FlowMode::Block };
2914 FlowCursor::new(engine, Feed::list(pairs), styles, regions, columns, gutter, mode, span)
2915 })
2916}
2917
2918/// The regions shrunk by a padding that each side resolves against the region itself: Typst's `pad`.
2919fn pad_regions(regions: &Regions, padding: &[Rel; 4]) -> Regions {
2920 let ix = Rel { ratio: padding[0].ratio + padding[2].ratio, abs: padding[0].abs + padding[2].abs };
2921 let iy = Rel { ratio: padding[1].ratio + padding[3].ratio, abs: padding[1].abs + padding[3].abs };
2922 regions.map(|w, h| (w - ix.relative_to(w), h - iy.relative_to(h)))
2923}
2924
2925/// The region for an unbreakable container's content: its size resolved against the base, less the inset,
2926/// expanded on an axis the container sizes.
2927fn unbreakable_pod(width: Sizing, height: Sizing, inset: &[Rel; 4], bw: f64, bh: f64) -> Regions {
2928 let w = match width {
2929 Sizing::Auto | Sizing::Fr(_) => bw,
2930 Sizing::Rel(r) => r.relative_to(bw),
2931 };
2932 let h = match height {
2933 Sizing::Auto | Sizing::Fr(_) => bh,
2934 Sizing::Rel(r) => r.relative_to(bh),
2935 };
2936 let (w, h) = if sides_zero(inset) { (w, h) } else { shrink(w, h, inset) };
2937 let expand_x = width != Sizing::Auto && w.is_finite();
2938 let expand_y = height != Sizing::Auto && h.is_finite();
2939 Regions::one(w, h, expand_x, expand_y)
2940}
2941
2942/// The regions for a breakable container's content: a fixed height (its whole, and what is left of it)
2943/// spread over the regions it spans, the inset taken from every region.
2944fn breakable_pod(width: Sizing, height: Sizing, inset: &[Rel; 4], regions: &Regions, fixed: Option<(f64, f64)>) -> Regions {
2945 let (bw, _) = regions.base();
2946 let mut pod = match fixed {
2947 Some((whole, left)) => {
2948 let (first, rest) = spread_height(left, regions);
2949 Regions {
2950 w: regions.w,
2951 h: first,
2952 full: whole,
2953 backlog: rest,
2954 last: None,
2955 expand_x: regions.expand_x,
2956 expand_y: regions.expand_y,
2957 }
2958 },
2959 None => regions.clone(),
2960 };
2961 pod.w = match width {
2962 Sizing::Auto | Sizing::Fr(_) => regions.w,
2963 Sizing::Rel(r) => r.relative_to(bw),
2964 };
2965 if !sides_zero(inset) {
2966 pod = pad_regions(&pod, inset);
2967 }
2968 pod.expand_x = width != Sizing::Auto && pod.w.is_finite();
2969 pod.expand_y = height != Sizing::Auto && pod.h.is_finite();
2970 pod
2971}
2972
2973/// A fixed height spread over the regions: as much as each takes, the rest overflowing the last. Typst's
2974/// `distribute`.
2975fn spread_height(height: f64, regions: &Regions) -> (f64, Vec<f64>) {
2976 let mut out = Vec::new();
2977 let mut left = height;
2978 if left <= 0.0 {
2979 return (left, Vec::new());
2980 }
2981 let mut r = regions.clone();
2982 loop {
2983 let limited = r.h.clamp(0.0, left);
2984 out.push(limited);
2985 left -= limited;
2986 if approx_empty(left) || !r.may_break() || (!r.may_progress() && approx_empty(limited)) {
2987 break;
2988 }
2989 r.next();
2990 }
2991 if !approx_empty(left) {
2992 if let Some(last) = out.last_mut() {
2993 *last += left;
2994 }
2995 }
2996 let first = out.remove(0);
2997 (first, out)
2998}
2999
3000/// A block's clip, fill and stroke, drawn behind its contents. The fill and stroke are Typst's rectangle
3001/// with the block's paint, stroke, corner radii and outset, laid out as a `rect` of the frame's size.
3002fn decorate(engine: &mut Engine, spec: &BlockSpec, frame: &mut Frame, paint: bool) -> Outcome<()> {
3003 let styles = &spec.styles;
3004 let fill = res!(spec.field("fill")).filter(|v| !v.is_none());
3005 let stroke = res!(spec.field("stroke")).filter(|v| !v.is_none());
3006 let radius = res!(spec.field("radius"));
3007 let outset = res!(spec.field("outset"));
3008 if bool_of(res!(spec.field("clip")), false) {
3009 let out = sides_rel(styles, outset.clone());
3010 let outs = [
3011 out[0].relative_to(frame.w),
3012 out[1].relative_to(frame.h),
3013 out[2].relative_to(frame.w),
3014 out[3].relative_to(frame.h),
3015 ];
3016 let path = res!(crate::flow::visual::clip_path(frame.w, frame.h, styles.font_size(),
3017 radius.clone(), stroke.clone(), outs));
3018 frame.clip(path);
3019 }
3020 if !paint || (fill.is_none() && stroke.is_none()) || res!(vis::is_hidden(styles)) {
3021 return Ok(());
3022 }
3023 let mut fields = Vec::new();
3024 let mut set = |name: &str, v: Value| {
3025 if let Some(id) = ElemKind::Rect.field_id(name) {
3026 fields.push((id, v));
3027 }
3028 };
3029 set("width", Value::Length(Length::pt(frame.w)));
3030 set("height", Value::Length(Length::pt(frame.h)));
3031 set("fill", fill.unwrap_or(Value::None));
3032 set("stroke", stroke.unwrap_or(Value::None));
3033 set("radius", radius.unwrap_or(Value::Length(Length::zero())));
3034 set("outset", outset.unwrap_or(Value::Length(Length::zero())));
3035 set("inset", Value::Length(Length::zero()));
3036 let rect = Content::new(ElemKind::Rect, fields, spec.span());
3037 let region = Regions::one(frame.w, frame.h, false, false).region();
3038 let node = res!(crate::flow::visual::layout_visual(engine, &rect, styles, region));
3039 frame.prepend(vec![(0.0, 0.0, Item::Node(node))]);
3040 Ok(())
3041}
3042
3043// Layout routines
3044
3045/// An element Typst shows through a single-region layout routine.
3046fn layout_single_layouter(
3047 engine: &mut Engine,
3048 elem: &Content,
3049 styles: &StyleChain,
3050 pod: &Regions,
3051 sized: &Regions, // the pod before the region's own expansion, which a shape sizes itself against
3052)
3053 -> Outcome<Frame>
3054{
3055 match elem.kind() {
3056 Some(k) if k.family() == Family::Visual => {
3057 // A shape or an image with no body of its own has no baseline, as in Typst: its baseline is its
3058 // bottom, wherever a later height puts that.
3059 let laid = res!(crate::flow::visual::layout_frame(engine, elem, styles, sized.region()));
3060 let node = res!(crate::flow::visual::frame_to_node(engine, &laid, elem.span()));
3061 let mut frame = Frame::from_node(node);
3062 if laid.baseline.is_none() {
3063 frame.baseline = None;
3064 }
3065 Ok(frame)
3066 },
3067 _ => {
3068 let mut frames = res!(layout_multi_layouter(engine, elem, styles, pod));
3069 Ok(if frames.is_empty() { Frame::new(0.0, 0.0) } else { frames.swap_remove(0) })
3070 },
3071 }
3072}
3073
3074/// An element Typst shows through a layout routine with the regions at hand.
3075fn layout_multi_layouter(engine: &mut Engine, elem: &Content, styles: &StyleChain, regions: &Regions) -> Outcome<Vec<Frame>> {
3076 let kind = match elem.kind() {
3077 Some(k) => k,
3078 None => return Ok(vec![Frame::new(0.0, 0.0)]),
3079 };
3080 match kind {
3081 ElemKind::Pad => layout_pad(engine, elem, styles, regions),
3082 ElemKind::Stack => layout_stack(engine, elem, styles, regions),
3083 ElemKind::Columns => layout_columns(engine, elem, styles, regions),
3084 ElemKind::Layout => layout_layout(engine, elem, styles, regions),
3085 ElemKind::List | ElemKind::Enum => crate::flow::lists::layout(engine, elem, styles, regions),
3086 ElemKind::Grid | ElemKind::Table => {
3087 let rows = res!(crate::flow::grid::layout_rows(engine, elem, styles, regions.region()));
3088 let (nodes, breaks) = (&rows.nodes, &rows.breaks);
3089 split_list(nodes.clone(), regions, breaks, |gi, r, head, skip| rows.split(engine, styles, gi, r, head, skip))
3090 },
3091 ElemKind::Equation => {
3092 let node = res!(crate::flow::math::layout_equation(engine, elem, styles, regions.region()));
3093 Ok(vec![Frame::from_node(node)])
3094 },
3095 k if k.family() == Family::Visual => {
3096 let node = res!(crate::flow::visual::layout_visual(engine, elem, styles, regions.region()));
3097 Ok(vec![Frame::from_node(node)])
3098 },
3099 other => Err(engine.error(DiagnosticKind::Type, elem.span(), fmt!("{} cannot be laid out as a block", other.path()))),
3100 }
3101}
3102
3103/// A `pad`'s four paddings, left, top, right and bottom, and its body.
3104fn pad_parts(elem: &Content, styles: &StyleChain) -> Outcome<([Rel; 4], Content)> {
3105 let rest = res!(field(elem, styles, "rest"));
3106 let x = match res!(field(elem, styles, "x")) { Some(v) => Some(v), None => rest.clone() };
3107 let y = match res!(field(elem, styles, "y")) { Some(v) => Some(v), None => rest };
3108 let mut padding = [Rel::zero(); 4];
3109 for (i, (name, axis)) in [("left", &x), ("top", &y), ("right", &x), ("bottom", &y)].into_iter().enumerate() {
3110 let v = match res!(field(elem, styles, name)) { Some(v) => Some(v), None => axis.clone() };
3111 padding[i] = v.and_then(|v| rel_of(styles, &v)).unwrap_or_default();
3112 }
3113 let body = match res!(field(elem, styles, "body")) {
3114 Some(v) => res!(v.cast::<Content>()),
3115 None => Content::empty(),
3116 };
3117 Ok((padding, body))
3118}
3119
3120/// `pad`: the body laid out in regions shrunk by the padding, each frame grown back by it.
3121fn layout_pad(engine: &mut Engine, elem: &Content, styles: &StyleChain, regions: &Regions) -> Outcome<Vec<Frame>> {
3122 let (padding, body) = res!(pad_parts(elem, styles));
3123 let mut frames = res!(layout_fragment_in(engine, elem.place(), &body, styles, pad_regions(regions, &padding)));
3124 for f in &mut frames {
3125 grow(f, &padding);
3126 }
3127 Ok(frames)
3128}
3129
3130/// A `columns`' count, gutter and body.
3131fn columns_parts(engine: &mut Engine, elem: &Content, styles: &StyleChain) -> Outcome<(usize, Rel, Content)> {
3132 let count = match res!(field(elem, styles, "count")) {
3133 Some(Value::Int(n)) if n > 0 => n as usize,
3134 Some(Value::Int(_)) => return Err(engine.error(DiagnosticKind::Type, elem.span(), "number must be positive")),
3135 _ => 2,
3136 };
3137 let gutter = res!(field(elem, styles, "gutter")).and_then(|v| rel_of(styles, &v)).unwrap_or(Rel { ratio: 0.04, abs: 0.0 });
3138 let body = match res!(field(elem, styles, "body")) {
3139 Some(v) => res!(v.cast::<Content>()),
3140 None => Content::empty(),
3141 };
3142 Ok((count, gutter, body))
3143}
3144
3145/// `columns(n)`: the body flowed through `n` column regions per region, as a page's columns are.
3146fn layout_columns(engine: &mut Engine, elem: &Content, styles: &StyleChain, regions: &Regions) -> Outcome<Vec<Frame>> {
3147 let (count, gutter, body) = res!(columns_parts(engine, elem, styles));
3148 engine.descend_fragment(elem.span(), |engine| {
3149 let (pairs, inline) = res!(engine.within(elem.place(), |engine| realise::realise_fragment(engine, &body, styles)));
3150 let mode = if inline { FlowMode::Inline } else { FlowMode::Block };
3151 layout_flow_pairs(engine, pairs, styles, regions.clone(), count, gutter, mode, elem.span())
3152 })
3153}
3154
3155/// `layout(size => ..)`: the function called under context with the base size of the regions, its result
3156/// displayed.
3157fn layout_content(engine: &mut Engine, elem: &Content, styles: &StyleChain, base: (f64, f64)) -> Outcome<Content> {
3158 let func = match res!(field(elem, styles, "func")) {
3159 Some(Value::Func(f)) => f,
3160 _ => return Err(err!(
3161 "layout has no `func` field in its schema, or it holds no function; `layout(..)` cannot run."; Unimplemented)),
3162 };
3163 let (w, h) = base;
3164 let mut size = Dict::new();
3165 size.insert("width", Value::Length(Length::pt(w)));
3166 size.insert("height", Value::Length(Length::pt(h)));
3167 let mut args = crate::eval::args::Args::new(elem.span());
3168 args.push(elem.span(), Value::dict(size));
3169 let outer = std::mem::replace(&mut engine.context, Context { location: elem.location(), styles: Some(styles.clone()) });
3170 let result = engine.call_func(&func, args);
3171 engine.context = outer;
3172 let value = res!(result);
3173 crate::eval::content::display(engine, value, elem.span())
3174}
3175
3176/// `layout(size => ..)`: the function's result flowed through the regions.
3177fn layout_layout(engine: &mut Engine, elem: &Content, styles: &StyleChain, regions: &Regions) -> Outcome<Vec<Frame>> {
3178 let content = res!(layout_content(engine, elem, styles, regions.base()));
3179 layout_fragment_in(engine, elem.place(), &content, styles, regions.clone())
3180}
3181
3182/// A vertical node list (a grid's rows) broken across the regions: each region takes the boxes that fit,
3183/// breaking only where the list allows -- at glue after a box, or at a penalty that is not forbidden. A
3184/// repeated header armed in the list is set again at the top of every region the rows spill onto, and a
3185/// repeated footer armed in it closes every region but the last, straight after the rows, its height kept
3186/// free in each.
3187fn split_list<F>(nodes: Vec<Node>, regions: &Regions, breaks: &[Option<usize>], mut split: F) -> Outcome<Vec<Frame>>
3188 where F: FnMut(usize, &Regions, f64, bool) -> Outcome<RowSplit>
3189{
3190 let mut s = Splitter {
3191 regions: regions.clone(),
3192 frames: Vec::new(),
3193 cur: Frame::new(0.0, 0.0),
3194 y: 0.0,
3195 boxes: false,
3196 tail: 0.0,
3197 base: 0.0,
3198 head: None,
3199 foot: None,
3200 };
3201 let mut at_break = true; // a break is allowed before the next box
3202 let mut prev_box = false;
3203 let mut pending: Option<(usize, Vec<BoxNode>)> = None; // the parts of a breakable row ahead
3204 let mut i = 0;
3205 while i < nodes.len() {
3206 match &nodes[i] {
3207 Node::Glue(g) => {
3208 if s.boxes {
3209 s.y += g.natural.to_pt();
3210 s.tail += g.natural.to_pt();
3211 }
3212 if prev_box {
3213 at_break = true;
3214 }
3215 prev_box = false;
3216 },
3217 Node::Penalty(p) => {
3218 if p.is_forced() && s.boxes && s.regions.may_break() {
3219 s.next_region();
3220 at_break = true;
3221 } else if p.is_forbidden() {
3222 at_break = false;
3223 } else {
3224 at_break = true;
3225 }
3226 prev_box = false;
3227 },
3228 Node::RepeatHead(h) => s.head = h.as_ref().map(|b| (**b).clone()),
3229 Node::RepeatFoot(f) => s.foot = f.as_ref().map(|b| (**b).clone()),
3230 Node::Anchor(_) | Node::Tag(_) | Node::Mark(_) => s.cur.push(0.0, s.y, Item::Node(nodes[i].clone())),
3231 Node::Float(_) | Node::Columns(_) | Node::PageColumns(_) => (),
3232 node => {
3233 if at_break {
3234 let atom = atom_height(&nodes, i);
3235 let foot = s.foot.as_ref().map(|f| f.dims.vextent().to_pt()).unwrap_or(0.0);
3236 let room = s.regions.h - s.y - foot;
3237 if !fits(room, atom) {
3238 // A row that breaks is set into the regions it needs, after what is welded above it; one
3239 // that does not goes whole to the next region, which a first row does too when the
3240 // region has not its full height.
3241 pending = res!(break_row(&nodes, breaks, i, &s, room, s.may_progress(), &mut split));
3242 if pending.is_none() && s.may_progress() {
3243 s.next_region();
3244 let room = s.regions.h - s.y;
3245 if !fits(room, atom) {
3246 pending = res!(break_row(&nodes, breaks, i, &s, room, false, &mut split));
3247 }
3248 }
3249 }
3250 }
3251 match pending.take() {
3252 Some((j, parts)) if j == i => {
3253 s.place_parts(parts);
3254 at_break = false;
3255 prev_box = true;
3256 i += 1;
3257 continue;
3258 },
3259 other => pending = other,
3260 }
3261 s.place(node.clone());
3262 at_break = false;
3263 prev_box = true;
3264 },
3265 }
3266 i += 1;
3267 }
3268 s.finish();
3269 Ok(s.frames)
3270}
3271
3272/// The breakable row that ends the atom starting at `start` (a row alone, or one welded below a header), broken
3273/// to fit `room` when it can be: the node holding its first part's box and the parts, if it breaks.
3274fn break_row<F>(
3275 nodes: &[Node],
3276 breaks: &[Option<usize>],
3277 start: usize,
3278 s: &Splitter,
3279 room: f64,
3280 skip: bool,
3281 split: &mut F,
3282)
3283 -> Outcome<Option<(usize, Vec<BoxNode>)>>
3284 where F: FnMut(usize, &Regions, f64, bool) -> Outcome<RowSplit>
3285{
3286 let (mut h, mut head, mut prev_box) = (0.0, s.head.as_ref().map(|b| b.dims.vextent().to_pt()), false);
3287 let mut row = None;
3288 for (k, n) in nodes.iter().enumerate().skip(start) {
3289 match n {
3290 Node::Glue(g) => {
3291 if prev_box {
3292 break;
3293 }
3294 h += g.natural.to_pt();
3295 },
3296 Node::Penalty(p) => {
3297 if !p.is_forbidden() {
3298 break;
3299 }
3300 prev_box = false;
3301 },
3302 Node::RepeatHead(b) => head = b.as_ref().map(|b| b.dims.vextent().to_pt()),
3303 Node::Anchor(_) | Node::Tag(_) | Node::Mark(_) | Node::RepeatFoot(_) | Node::Float(_)
3304 | Node::Columns(_) | Node::PageColumns(_) => (),
3305 other => {
3306 row = breaks.get(k).copied().flatten().map(|gi| (k, gi, h));
3307 h += other.vextent().to_pt();
3308 prev_box = true;
3309 },
3310 }
3311 }
3312 let (k, gi, lead) = match row {
3313 Some(r) => r,
3314 None => return Ok(None),
3315 };
3316 let mut r = s.regions.clone();
3317 r.h = room - lead;
3318 Ok(match res!(split(gi, &r, head.unwrap_or(0.0), skip)) {
3319 RowSplit::Parts(parts) => Some((k, parts)),
3320 RowSplit::Skip | RowSplit::Whole => None,
3321 })
3322}
3323
3324struct Splitter {
3325 regions: Regions,
3326 frames: Vec<Frame>,
3327 cur: Frame,
3328 y: f64,
3329 boxes: bool, // the region holds a box
3330 tail: f64, // the gutters since the last box, left out of a region that ends there
3331 base: f64, // the height a region starts at: what its repeated header takes
3332 head: Option<BoxNode>,
3333 foot: Option<BoxNode>,
3334}
3335
3336impl Splitter {
3337 fn place(&mut self, node: Node) {
3338 let d = node_dims(&node).unwrap_or_default();
3339 self.cur.w = self.cur.w.max(d.width.to_pt());
3340 if !self.boxes && self.cur.baseline.is_none() {
3341 self.cur.baseline = Some(self.y + d.height.to_pt());
3342 }
3343 let h = node.vextent().to_pt();
3344 self.cur.push(0.0, self.y, Item::Node(node));
3345 self.y += h;
3346 self.boxes = true;
3347 self.tail = 0.0;
3348 }
3349
3350 /// Would the next region give more room? Typst's `may_progress` on the room left, which what has been placed
3351 /// beyond the repeated header has shortened.
3352 fn may_progress(&self) -> bool { self.y > self.base + EPS || self.regions.may_progress() }
3353
3354 /// A row broken across regions: its first part here, each other in a region of its own.
3355 fn place_parts(&mut self, parts: Vec<BoxNode>) {
3356 for (k, part) in parts.into_iter().enumerate() {
3357 if k > 0 {
3358 self.next_region();
3359 }
3360 self.place(Node::VBox(part));
3361 }
3362 }
3363
3364 fn finish(&mut self) {
3365 let mut done = std::mem::replace(&mut self.cur, Frame::new(0.0, 0.0));
3366 done.h = if self.regions.expand_y { self.regions.h } else { self.y - self.tail };
3367 // A grid is as wide as its columns, and no wider than the region where they overflow it: Typst places
3368 // an overflowing grid at the region's start, whatever the alignment.
3369 done.w = if self.regions.expand_x { self.regions.w } else { done.w.min(self.regions.w) };
3370 self.frames.push(done);
3371 }
3372
3373 /// Closes the region (with the repeated footer, if one is armed) and opens the next (with the repeated
3374 /// header, if one is armed).
3375 fn next_region(&mut self) {
3376 if let Some(foot) = self.foot.clone() {
3377 self.place(Node::VBox(foot));
3378 }
3379 self.finish();
3380 self.regions.next();
3381 self.y = 0.0;
3382 self.tail = 0.0;
3383 self.boxes = false;
3384 if let Some(head) = self.head.clone() {
3385 self.place(Node::VBox(head));
3386 }
3387 self.base = self.y;
3388 }
3389}
3390
3391/// The height of the boxes from `start` up to the list's next legal breakpoint.
3392fn atom_height(nodes: &[Node], start: usize) -> f64 {
3393 let mut h = 0.0;
3394 let mut prev_box = false;
3395 for n in &nodes[start..] {
3396 match n {
3397 Node::Glue(g) => {
3398 if prev_box {
3399 break;
3400 }
3401 h += g.natural.to_pt();
3402 },
3403 Node::Penalty(p) => {
3404 if !p.is_forbidden() {
3405 break;
3406 }
3407 prev_box = false;
3408 },
3409 Node::Anchor(_) | Node::Tag(_) | Node::Mark(_) | Node::RepeatHead(_) | Node::RepeatFoot(_)
3410 | Node::Float(_) | Node::Columns(_) | Node::PageColumns(_) => (),
3411 other => {
3412 h += other.vextent().to_pt();
3413 prev_box = true;
3414 },
3415 }
3416 }
3417 h
3418}
3419
3420/// `stack`: children set along a direction with spacing between them, Typst's `layout_stack`.
3421fn layout_stack(engine: &mut Engine, elem: &Content, styles: &StyleChain, regions: &Regions) -> Outcome<Vec<Frame>> {
3422 let dir = match res!(field(elem, styles, "dir")) {
3423 Some(Value::Direction(d)) => d,
3424 _ => Direction::Ttb,
3425 };
3426 let spacing = match res!(field(elem, styles, "spacing")) {
3427 None | Some(Value::None) => None,
3428 Some(v) => spacing_of(styles, &v),
3429 };
3430 let children = match res!(field(elem, styles, "children")) {
3431 Some(Value::Array(a)) => (*a).clone(),
3432 _ => Vec::new(),
3433 };
3434 let mut s = Stacker::new(dir, regions.clone(), elem.span());
3435 let mut deferred: Option<Spacing> = None;
3436 // Each child is realised at a place of its own under the stack's, so it is located alike whenever the
3437 // stack is laid out again.
3438 let mut places = elem.place().map(Locator::new);
3439 for child in children {
3440 let content = match child {
3441 Value::Content(c) => c,
3442 Value::Str(t) => Content::text(&t),
3443 other => match spacing_of(styles, &other) {
3444 Some(sp) => {
3445 s.spacing(sp, styles);
3446 deferred = None;
3447 continue;
3448 },
3449 None => res!(other.cast::<Content>()),
3450 },
3451 };
3452 // `h` in a horizontal stack and `v` in a vertical one are spacing, transparently.
3453 let transparent = match (s.vertical, content.kind()) {
3454 (false, Some(ElemKind::H)) | (true, Some(ElemKind::V)) => res!(field(&content, styles, "amount"))
3455 .and_then(|a| spacing_of(styles, &a)),
3456 _ => None,
3457 };
3458 if let Some(sp) = transparent {
3459 s.spacing(sp, styles);
3460 deferred = None;
3461 continue;
3462 }
3463 if let Some(sp) = deferred {
3464 s.spacing(sp, styles);
3465 }
3466 let place = places.as_mut().map(|l| l.next(content.kind().unwrap_or(ElemKind::Sequence), content.shell()));
3467 res!(s.block(engine, place, &content, styles));
3468 deferred = spacing;
3469 }
3470 res!(s.finish_region(engine));
3471 Ok(s.finished)
3472}
3473
3474pub(super) enum StackItem {
3475 Abs(f64),
3476 Fr(f64),
3477 Frame(Frame, Align2),
3478}
3479
3480pub(super) struct Stacker {
3481 vertical: bool,
3482 positive: bool,
3483 regions: Regions,
3484 expand: (bool, bool),
3485 initial: (f64, f64),
3486 used_main: f64,
3487 used_cross: f64,
3488 fr: f64,
3489 items: Vec<StackItem>,
3490 finished: Vec<Frame>,
3491 span: Span,
3492}
3493
3494impl Stacker {
3495 pub(super) fn new(dir: Direction, mut regions: Regions, span: Span) -> Self {
3496 let vertical = matches!(dir, Direction::Ttb | Direction::Btt);
3497 let expand = (regions.expand_x, regions.expand_y);
3498 // Children do not expand along the stacking axis.
3499 if vertical {
3500 regions.expand_y = false;
3501 } else {
3502 regions.expand_x = false;
3503 }
3504 let initial = (regions.w, regions.h);
3505 Self {
3506 vertical,
3507 positive: matches!(dir, Direction::Ttb | Direction::Ltr),
3508 regions,
3509 expand,
3510 initial,
3511 used_main: 0.0,
3512 used_cross: 0.0,
3513 fr: 0.0,
3514 items: Vec::new(),
3515 finished: Vec::new(),
3516 span,
3517 }
3518 }
3519
3520 pub(super) fn spacing(&mut self, sp: Spacing, _styles: &StyleChain) {
3521 match sp {
3522 Spacing::Rel(r) => {
3523 let base = if self.vertical { self.regions.base().1 } else { self.regions.base().0 };
3524 let resolved = r.relative_to(base);
3525 let remaining = if self.vertical { self.regions.h } else { self.regions.w };
3526 let limited = resolved.min(remaining);
3527 if self.vertical {
3528 self.regions.h -= limited;
3529 }
3530 self.used_main += limited;
3531 self.items.push(StackItem::Abs(resolved));
3532 },
3533 Spacing::Fr(f) => {
3534 self.fr += f;
3535 self.items.push(StackItem::Fr(f));
3536 },
3537 }
3538 }
3539
3540 fn block(&mut self, engine: &mut Engine, place: Option<Place>, block: &Content, styles: &StyleChain) -> Outcome<()> {
3541 if self.regions.is_full() {
3542 res!(self.finish_region(engine));
3543 }
3544 // The alignment along the stacking axis a child asks for: an `align` child's own, a styled child's,
3545 // else the alignment in force.
3546 let align = match block {
3547 Content::Styled(st) => res!(alignment(&styles.chain(&st.styles))),
3548 c if c.is(ElemKind::Align) => {
3549 let a = res!(field(c, styles, "alignment"));
3550 let chained = match (a, ElemKind::Align.field_id("alignment")) {
3551 (Some(v), Some(id)) => styles.chain(&crate::eval::styles::Styles::from_style(
3552 crate::eval::styles::Style::Property(crate::eval::styles::Property::new(
3553 ElemKind::Align, id, v, c.span())))),
3554 _ => styles.clone(),
3555 };
3556 res!(alignment(&chained))
3557 },
3558 _ => res!(alignment(styles)),
3559 };
3560 let frames = res!(layout_fragment_in(engine, place, block, styles, self.regions.clone()));
3561 self.fragment(engine, align, frames)
3562 }
3563
3564 /// A child with a layout routine of its own, Typst's `StackLayoutChild::CustomLayouter`: the routine is
3565 /// given the regions left and returns the child's frames, which take the alignment in force.
3566 pub(super) fn custom<F>(&mut self, engine: &mut Engine, styles: &StyleChain, lay: F) -> Outcome<()>
3567 where F: FnOnce(&mut Engine, &Regions) -> Outcome<Vec<Frame>>
3568 {
3569 if self.regions.is_full() {
3570 res!(self.finish_region(engine));
3571 }
3572 let align = res!(alignment(styles));
3573 let frames = res!(lay(engine, &self.regions));
3574 self.fragment(engine, align, frames)
3575 }
3576
3577 /// Takes laid out frames, a block's or a custom routine's, into the regions.
3578 fn fragment(&mut self, engine: &mut Engine, align: Align2, frames: Vec<Frame>) -> Outcome<()> {
3579 let n = frames.len();
3580 for (i, frame) in frames.into_iter().enumerate() {
3581 let (main, cross) = if self.vertical { (frame.h, frame.w) } else { (frame.w, frame.h) };
3582 if self.vertical {
3583 self.regions.h -= frame.h;
3584 }
3585 self.used_main += main;
3586 self.used_cross = self.used_cross.max(cross);
3587 self.items.push(StackItem::Frame(frame, align));
3588 if i + 1 < n {
3589 res!(self.finish_region(engine));
3590 }
3591 }
3592 Ok(())
3593 }
3594
3595 fn finish_region(&mut self, engine: &mut Engine) -> Outcome<()> {
3596 let used = if self.vertical { (self.used_cross, self.used_main) } else { (self.used_main, self.used_cross) };
3597 let mut size = (
3598 (if self.expand.0 { self.initial.0 } else { used.0 }).min(self.initial.0),
3599 (if self.expand.1 { self.initial.1 } else { used.1 }).min(self.initial.1),
3600 );
3601 let full = if self.vertical { self.initial.1 } else { self.initial.0 };
3602 let remaining = full - self.used_main;
3603 if self.fr > 0.0 && full.is_finite() {
3604 self.used_main = full;
3605 if self.vertical {
3606 size.1 = full;
3607 } else {
3608 size.0 = full;
3609 }
3610 }
3611 if !size.0.is_finite() || !size.1.is_finite() {
3612 return Err(engine.error(DiagnosticKind::Type, self.span, "stack spacing is infinite"));
3613 }
3614 let mut output = Frame::new(size.0, size.1);
3615 let mut cursor = 0.0;
3616 let mut ruler = if self.positive { Fixed::Start } else { Fixed::End };
3617 let fr = self.fr;
3618 for item in std::mem::take(&mut self.items) {
3619 match item {
3620 StackItem::Abs(v) => cursor += v,
3621 StackItem::Fr(v) => cursor += share(v, fr, remaining),
3622 StackItem::Frame(frame, align) => {
3623 let a_main = if self.vertical { align.y } else { align.x };
3624 let a_cross = if self.vertical { align.x } else { align.y };
3625 ruler = if self.positive { ruler.max(a_main) } else { ruler.min(a_main) };
3626 let parent = if self.vertical { size.1 } else { size.0 };
3627 let child = if self.vertical { frame.h } else { frame.w };
3628 let main = ruler.position(parent - self.used_main)
3629 + if self.positive { cursor } else { self.used_main - child - cursor };
3630 let cross_extent = if self.vertical { size.0 - frame.w } else { size.1 - frame.h };
3631 let cross = a_cross.position(cross_extent);
3632 let (x, y) = if self.vertical { (cross, main) } else { (main, cross) };
3633 cursor += child;
3634 output.push_frame(x, y, frame);
3635 },
3636 }
3637 }
3638 self.regions.next();
3639 self.initial = (self.regions.w, self.regions.h);
3640 self.used_main = 0.0;
3641 self.used_cross = 0.0;
3642 self.fr = 0.0;
3643 self.finished.push(output);
3644 Ok(())
3645 }
3646
3647 /// Closes the last region and hands over every region's frame.
3648 pub(super) fn finish(mut self, engine: &mut Engine) -> Outcome<Vec<Frame>> {
3649 res!(self.finish_region(engine));
3650 Ok(self.finished)
3651 }
3652}