diff options
Diffstat (limited to 'crates/typst-layout/src/flow')
| -rw-r--r-- | crates/typst-layout/src/flow/block.rs | 401 | ||||
| -rw-r--r-- | crates/typst-layout/src/flow/collect.rs | 648 | ||||
| -rw-r--r-- | crates/typst-layout/src/flow/compose.rs | 877 | ||||
| -rw-r--r-- | crates/typst-layout/src/flow/distribute.rs | 525 | ||||
| -rw-r--r-- | crates/typst-layout/src/flow/mod.rs | 381 |
5 files changed, 2832 insertions, 0 deletions
diff --git a/crates/typst-layout/src/flow/block.rs b/crates/typst-layout/src/flow/block.rs new file mode 100644 index 00000000..1dd98812 --- /dev/null +++ b/crates/typst-layout/src/flow/block.rs @@ -0,0 +1,401 @@ +use once_cell::unsync::Lazy; +use smallvec::SmallVec; +use typst_library::diag::SourceResult; +use typst_library::engine::Engine; +use typst_library::foundations::{Packed, Resolve, StyleChain}; +use typst_library::introspection::Locator; +use typst_library::layout::{ + Abs, Axes, BlockBody, BlockElem, Fragment, Frame, FrameKind, Region, Regions, Rel, + Sides, Size, Sizing, +}; +use typst_library::visualize::Stroke; +use typst_utils::Numeric; + +use crate::shapes::{clip_rect, fill_and_stroke}; + +/// Lay this out as an unbreakable block. +#[typst_macros::time(name = "block", span = elem.span())] +pub fn layout_single_block( + elem: &Packed<BlockElem>, + engine: &mut Engine, + locator: Locator, + styles: StyleChain, + region: Region, +) -> SourceResult<Frame> { + // Fetch sizing properties. + let width = elem.width(styles); + let height = elem.height(styles); + let inset = elem.inset(styles).unwrap_or_default(); + + // Build the pod regions. + let pod = unbreakable_pod(&width.into(), &height, &inset, styles, region.size); + + // Layout the body. + let body = elem.body(styles); + let mut frame = match body { + // If we have no body, just create one frame. Its size will be + // adjusted below. + None => Frame::hard(Size::zero()), + + // If we have content as our body, just layout it. + Some(BlockBody::Content(body)) => { + crate::layout_frame(engine, body, locator.relayout(), styles, pod)? + } + + // If we have a child that wants to layout with just access to the + // base region, give it that. + Some(BlockBody::SingleLayouter(callback)) => { + callback.call(engine, locator, styles, pod)? + } + + // If we have a child that wants to layout with full region access, + // we layout it. + Some(BlockBody::MultiLayouter(callback)) => { + let expand = (pod.expand | region.expand) & pod.size.map(Abs::is_finite); + let pod = Region { expand, ..pod }; + callback.call(engine, locator, styles, pod.into())?.into_frame() + } + }; + + // Explicit blocks are boundaries for gradient relativeness. + if matches!(body, None | Some(BlockBody::Content(_))) { + frame.set_kind(FrameKind::Hard); + } + + // Enforce a correct frame size on the expanded axes. Do this before + // applying the inset, since the pod shrunk. + frame.set_size(pod.expand.select(pod.size, frame.size())); + + // Apply the inset. + if !inset.is_zero() { + crate::pad::grow(&mut frame, &inset); + } + + // Prepare fill and stroke. + let fill = elem.fill(styles); + let stroke = elem + .stroke(styles) + .unwrap_or_default() + .map(|s| s.map(Stroke::unwrap_or_default)); + + // Only fetch these if necessary (for clipping or filling/stroking). + let outset = Lazy::new(|| elem.outset(styles).unwrap_or_default()); + let radius = Lazy::new(|| elem.radius(styles).unwrap_or_default()); + + // Clip the contents, if requested. + if elem.clip(styles) { + let size = frame.size() + outset.relative_to(frame.size()).sum_by_axis(); + frame.clip(clip_rect(size, &radius, &stroke)); + } + + // Add fill and/or stroke. + if fill.is_some() || stroke.iter().any(Option::is_some) { + fill_and_stroke(&mut frame, fill, &stroke, &outset, &radius, elem.span()); + } + + // Assign label to each frame in the fragment. + if let Some(label) = elem.label() { + frame.label(label); + } + + Ok(frame) +} + +/// Lay this out as a breakable block. +#[typst_macros::time(name = "block", span = elem.span())] +pub fn layout_multi_block( + elem: &Packed<BlockElem>, + engine: &mut Engine, + locator: Locator, + styles: StyleChain, + regions: Regions, +) -> SourceResult<Fragment> { + // Fetch sizing properties. + let width = elem.width(styles); + let height = elem.height(styles); + let inset = elem.inset(styles).unwrap_or_default(); + + // Allocate a small vector for backlogs. + let mut buf = SmallVec::<[Abs; 2]>::new(); + + // Build the pod regions. + let pod = breakable_pod(&width.into(), &height, &inset, styles, regions, &mut buf); + + // Layout the body. + let body = elem.body(styles); + let mut fragment = match body { + // If we have no body, just create one frame plus one per backlog + // region. We create them zero-sized; if necessary, their size will + // be adjusted below. + None => { + let mut frames = vec![]; + frames.push(Frame::hard(Size::zero())); + if pod.expand.y { + let mut iter = pod; + while !iter.backlog.is_empty() { + frames.push(Frame::hard(Size::zero())); + iter.next(); + } + } + Fragment::frames(frames) + } + + // If we have content as our body, just layout it. + Some(BlockBody::Content(body)) => { + let mut fragment = + crate::layout_fragment(engine, body, locator.relayout(), styles, pod)?; + + // If the body is automatically sized and produced more than one + // fragment, ensure that the width was consistent across all + // regions. If it wasn't, we need to relayout with expansion. + if !pod.expand.x + && fragment + .as_slice() + .windows(2) + .any(|w| !w[0].width().approx_eq(w[1].width())) + { + let max_width = + fragment.iter().map(|frame| frame.width()).max().unwrap_or_default(); + let pod = Regions { + size: Size::new(max_width, pod.size.y), + expand: Axes::new(true, pod.expand.y), + ..pod + }; + fragment = crate::layout_fragment(engine, body, locator, styles, pod)?; + } + + fragment + } + + // If we have a child that wants to layout with just access to the + // base region, give it that. + Some(BlockBody::SingleLayouter(callback)) => { + let pod = Region::new(pod.base(), pod.expand); + callback.call(engine, locator, styles, pod).map(Fragment::frame)? + } + + // If we have a child that wants to layout with full region access, + // we layout it. + // + // For auto-sized multi-layouters, we propagate the outer expansion + // so that they can decide for themselves. We also ensure again to + // only expand if the size is finite. + Some(BlockBody::MultiLayouter(callback)) => { + let expand = (pod.expand | regions.expand) & pod.size.map(Abs::is_finite); + let pod = Regions { expand, ..pod }; + callback.call(engine, locator, styles, pod)? + } + }; + + // Prepare fill and stroke. + let fill = elem.fill(styles); + let stroke = elem + .stroke(styles) + .unwrap_or_default() + .map(|s| s.map(Stroke::unwrap_or_default)); + + // Only fetch these if necessary (for clipping or filling/stroking). + let outset = Lazy::new(|| elem.outset(styles).unwrap_or_default()); + let radius = Lazy::new(|| elem.radius(styles).unwrap_or_default()); + + // Fetch/compute these outside of the loop. + let clip = elem.clip(styles); + let has_fill_or_stroke = fill.is_some() || stroke.iter().any(Option::is_some); + let has_inset = !inset.is_zero(); + let is_explicit = matches!(body, None | Some(BlockBody::Content(_))); + + // Skip filling/stroking the first frame if it is empty and a non-empty + // one follows. + let mut skip_first = false; + if let [first, rest @ ..] = fragment.as_slice() { + skip_first = has_fill_or_stroke + && first.is_empty() + && rest.iter().any(|frame| !frame.is_empty()); + } + + // Post-process to apply insets, clipping, fills, and strokes. + for (i, (frame, region)) in fragment.iter_mut().zip(pod.iter()).enumerate() { + // Explicit blocks are boundaries for gradient relativeness. + if is_explicit { + frame.set_kind(FrameKind::Hard); + } + + // Enforce a correct frame size on the expanded axes. Do this before + // applying the inset, since the pod shrunk. + frame.set_size(pod.expand.select(region, frame.size())); + + // Apply the inset. + if has_inset { + crate::pad::grow(frame, &inset); + } + + // Clip the contents, if requested. + if clip { + let size = frame.size() + outset.relative_to(frame.size()).sum_by_axis(); + frame.clip(clip_rect(size, &radius, &stroke)); + } + + // Add fill and/or stroke. + if has_fill_or_stroke && (i > 0 || !skip_first) { + fill_and_stroke(frame, fill.clone(), &stroke, &outset, &radius, elem.span()); + } + } + + // Assign label to each frame in the fragment. + if let Some(label) = elem.label() { + for frame in fragment.iter_mut() { + frame.label(label); + } + } + + Ok(fragment) +} + +/// Builds the pod region for an unbreakable sized container. +pub(crate) fn unbreakable_pod( + width: &Sizing, + height: &Sizing, + inset: &Sides<Rel<Abs>>, + styles: StyleChain, + base: Size, +) -> Region { + // Resolve the size. + let mut size = Size::new( + match width { + // - For auto, the whole region is available. + // - Fr is handled outside and already factored into the `region`, + // so we can treat it equivalently to 100%. + Sizing::Auto | Sizing::Fr(_) => base.x, + // Resolve the relative sizing. + Sizing::Rel(rel) => rel.resolve(styles).relative_to(base.x), + }, + match height { + Sizing::Auto | Sizing::Fr(_) => base.y, + Sizing::Rel(rel) => rel.resolve(styles).relative_to(base.y), + }, + ); + + // Take the inset, if any, into account. + if !inset.is_zero() { + size = crate::pad::shrink(size, inset); + } + + // If the child is manually, the size is forced and we should enable + // expansion. + let expand = Axes::new( + *width != Sizing::Auto && size.x.is_finite(), + *height != Sizing::Auto && size.y.is_finite(), + ); + + Region::new(size, expand) +} + +/// Builds the pod regions for a breakable sized container. +fn breakable_pod<'a>( + width: &Sizing, + height: &Sizing, + inset: &Sides<Rel<Abs>>, + styles: StyleChain, + regions: Regions, + buf: &'a mut SmallVec<[Abs; 2]>, +) -> Regions<'a> { + let base = regions.base(); + + // The vertical region sizes we're about to build. + let first; + let full; + let backlog: &mut [Abs]; + let last; + + // If the block has a fixed height, things are very different, so we + // handle that case completely separately. + match height { + Sizing::Auto | Sizing::Fr(_) => { + // If the block is automatically sized, we can just inherit the + // regions. + first = regions.size.y; + full = regions.full; + buf.extend_from_slice(regions.backlog); + backlog = buf; + last = regions.last; + } + + Sizing::Rel(rel) => { + // Resolve the sizing to a concrete size. + let resolved = rel.resolve(styles).relative_to(base.y); + + // Since we're manually sized, the resolved size is the base height. + full = resolved; + + // Distribute the fixed height across a start region and a backlog. + (first, backlog) = distribute(resolved, regions, buf); + + // If the height is manually sized, we don't want a final repeatable + // region. + last = None; + } + }; + + // Resolve the horizontal sizing to a concrete width and combine + // `width` and `first` into `size`. + let mut size = Size::new( + match width { + Sizing::Auto | Sizing::Fr(_) => regions.size.x, + Sizing::Rel(rel) => rel.resolve(styles).relative_to(base.x), + }, + first, + ); + + // Take the inset, if any, into account, applying it to the + // individual region components. + let (mut full, mut last) = (full, last); + if !inset.is_zero() { + crate::pad::shrink_multiple(&mut size, &mut full, backlog, &mut last, inset); + } + + // If the child is manually, the size is forced and we should enable + // expansion. + let expand = Axes::new( + *width != Sizing::Auto && size.x.is_finite(), + *height != Sizing::Auto && size.y.is_finite(), + ); + + Regions { size, full, backlog, last, expand } +} + +/// Distribute a fixed height spread over existing regions into a new first +/// height and a new backlog. +fn distribute<'a>( + height: Abs, + mut regions: Regions, + buf: &'a mut SmallVec<[Abs; 2]>, +) -> (Abs, &'a mut [Abs]) { + // Build new region heights from old regions. + let mut remaining = height; + loop { + let limited = regions.size.y.clamp(Abs::zero(), remaining); + buf.push(limited); + remaining -= limited; + if remaining.approx_empty() + || !regions.may_break() + || (!regions.may_progress() && limited.approx_empty()) + { + break; + } + regions.next(); + } + + // If there is still something remaining, apply it to the + // last region (it will overflow, but there's nothing else + // we can do). + if !remaining.approx_empty() { + if let Some(last) = buf.last_mut() { + *last += remaining; + } + } + + // Distribute the heights to the first region and the + // backlog. There is no last region, since the height is + // fixed. + (buf[0], &mut buf[1..]) +} diff --git a/crates/typst-layout/src/flow/collect.rs b/crates/typst-layout/src/flow/collect.rs new file mode 100644 index 00000000..aee5d508 --- /dev/null +++ b/crates/typst-layout/src/flow/collect.rs @@ -0,0 +1,648 @@ +use std::cell::RefCell; +use std::fmt::{self, Debug, Formatter}; +use std::hash::Hash; + +use bumpalo::boxed::Box as BumpBox; +use bumpalo::Bump; +use comemo::{Track, Tracked, TrackedMut}; +use once_cell::unsync::Lazy; +use typst_library::diag::{bail, SourceResult}; +use typst_library::engine::{Engine, Route, Sink, Traced}; +use typst_library::foundations::{Packed, Resolve, Smart, StyleChain}; +use typst_library::introspection::{ + Introspector, Location, Locator, LocatorLink, SplitLocator, Tag, TagElem, +}; +use typst_library::layout::{ + Abs, AlignElem, Alignment, Axes, BlockElem, ColbreakElem, FixedAlignment, FlushElem, + Fr, Fragment, Frame, PagebreakElem, PlaceElem, PlacementScope, Ratio, Region, + Regions, Rel, Size, Sizing, Spacing, VElem, +}; +use typst_library::model::ParElem; +use typst_library::routines::{Pair, Routines}; +use typst_library::text::TextElem; +use typst_library::World; + +use super::{layout_multi_block, layout_single_block}; + +/// Collects all elements of the flow into prepared children. These are much +/// simpler to handle than the raw elements. +#[typst_macros::time] +pub fn collect<'a>( + engine: &mut Engine, + bump: &'a Bump, + children: &[Pair<'a>], + locator: Locator<'a>, + base: Size, + expand: bool, +) -> SourceResult<Vec<Child<'a>>> { + Collector { + engine, + bump, + children, + locator: locator.split(), + base, + expand, + output: Vec::with_capacity(children.len()), + last_was_par: false, + } + .run() +} + +/// State for collection. +struct Collector<'a, 'x, 'y> { + engine: &'x mut Engine<'y>, + bump: &'a Bump, + children: &'x [Pair<'a>], + base: Size, + expand: bool, + locator: SplitLocator<'a>, + output: Vec<Child<'a>>, + last_was_par: bool, +} + +impl<'a> Collector<'a, '_, '_> { + /// Perform the collection. + fn run(mut self) -> SourceResult<Vec<Child<'a>>> { + for &(child, styles) in self.children { + if let Some(elem) = child.to_packed::<TagElem>() { + self.output.push(Child::Tag(&elem.tag)); + } else if let Some(elem) = child.to_packed::<VElem>() { + self.v(elem, styles); + } else if let Some(elem) = child.to_packed::<ParElem>() { + self.par(elem, styles)?; + } else if let Some(elem) = child.to_packed::<BlockElem>() { + self.block(elem, styles); + } else if let Some(elem) = child.to_packed::<PlaceElem>() { + self.place(elem, styles)?; + } else if child.is::<FlushElem>() { + self.output.push(Child::Flush); + } else if let Some(elem) = child.to_packed::<ColbreakElem>() { + self.output.push(Child::Break(elem.weak(styles))); + } else if child.is::<PagebreakElem>() { + bail!( + child.span(), "pagebreaks are not allowed inside of containers"; + hint: "try using a `#colbreak()` instead", + ); + } else { + bail!(child.span(), "{} is not allowed here", child.func().name()); + } + } + + Ok(self.output) + } + + /// Collect vertical spacing into a relative or fractional child. + fn v(&mut self, elem: &'a Packed<VElem>, styles: StyleChain<'a>) { + self.output.push(match elem.amount { + Spacing::Rel(rel) => Child::Rel(rel.resolve(styles), elem.weak(styles) as u8), + Spacing::Fr(fr) => Child::Fr(fr), + }); + } + + /// Collect a paragraph into [`LineChild`]ren. This already performs line + /// layout since it is not dependent on the concrete regions. + fn par( + &mut self, + elem: &'a Packed<ParElem>, + styles: StyleChain<'a>, + ) -> SourceResult<()> { + let align = AlignElem::alignment_in(styles).resolve(styles); + let leading = ParElem::leading_in(styles); + let spacing = ParElem::spacing_in(styles); + let costs = TextElem::costs_in(styles); + + let lines = crate::layout_inline( + self.engine, + &elem.children, + self.locator.next(&elem.span()), + styles, + self.last_was_par, + self.base, + self.expand, + )? + .into_frames(); + + self.output.push(Child::Rel(spacing.into(), 4)); + + // Determine whether to prevent widow and orphans. + let len = lines.len(); + let prevent_orphans = + costs.orphan() > Ratio::zero() && len >= 2 && !lines[1].is_empty(); + let prevent_widows = + costs.widow() > Ratio::zero() && len >= 2 && !lines[len - 2].is_empty(); + let prevent_all = len == 3 && prevent_orphans && prevent_widows; + + // Store the heights of lines at the edges because we'll potentially + // need these later when `lines` is already moved. + let height_at = |i| lines.get(i).map(Frame::height).unwrap_or_default(); + let front_1 = height_at(0); + let front_2 = height_at(1); + let back_2 = height_at(len.saturating_sub(2)); + let back_1 = height_at(len.saturating_sub(1)); + + for (i, frame) in lines.into_iter().enumerate() { + if i > 0 { + self.output.push(Child::Rel(leading.into(), 5)); + } + + // To prevent widows and orphans, we require enough space for + // - all lines if it's just three + // - the first two lines if we're at the first line + // - the last two lines if we're at the second to last line + let need = if prevent_all && i == 0 { + front_1 + leading + front_2 + leading + back_1 + } else if prevent_orphans && i == 0 { + front_1 + leading + front_2 + } else if prevent_widows && i >= 2 && i + 2 == len { + back_2 + leading + back_1 + } else { + frame.height() + }; + + self.output + .push(Child::Line(self.boxed(LineChild { frame, align, need }))); + } + + self.output.push(Child::Rel(spacing.into(), 4)); + self.last_was_par = true; + + Ok(()) + } + + /// Collect a block into a [`SingleChild`] or [`MultiChild`] depending on + /// whether it is breakable. + fn block(&mut self, elem: &'a Packed<BlockElem>, styles: StyleChain<'a>) { + let locator = self.locator.next(&elem.span()); + let align = AlignElem::alignment_in(styles).resolve(styles); + let alone = self.children.len() == 1; + let sticky = elem.sticky(styles); + let breakable = elem.breakable(styles); + let fr = match elem.height(styles) { + Sizing::Fr(fr) => Some(fr), + _ => None, + }; + + let fallback = Lazy::new(|| ParElem::spacing_in(styles)); + let spacing = |amount| match amount { + Smart::Auto => Child::Rel((*fallback).into(), 4), + Smart::Custom(Spacing::Rel(rel)) => Child::Rel(rel.resolve(styles), 3), + Smart::Custom(Spacing::Fr(fr)) => Child::Fr(fr), + }; + + self.output.push(spacing(elem.above(styles))); + + if !breakable || fr.is_some() { + self.output.push(Child::Single(self.boxed(SingleChild { + align, + sticky, + alone, + fr, + elem, + styles, + locator, + cell: CachedCell::new(), + }))); + } else { + self.output.push(Child::Multi(self.boxed(MultiChild { + align, + sticky, + alone, + elem, + styles, + locator, + cell: CachedCell::new(), + }))); + }; + + self.output.push(spacing(elem.below(styles))); + self.last_was_par = false; + } + + /// Collects a placed element into a [`PlacedChild`]. + fn place( + &mut self, + elem: &'a Packed<PlaceElem>, + styles: StyleChain<'a>, + ) -> SourceResult<()> { + let alignment = elem.alignment(styles); + let align_x = alignment.map_or(FixedAlignment::Center, |align| { + align.x().unwrap_or_default().resolve(styles) + }); + let align_y = alignment.map(|align| align.y().map(|y| y.resolve(styles))); + let scope = elem.scope(styles); + let float = elem.float(styles); + + match (float, align_y) { + (true, Smart::Custom(None | Some(FixedAlignment::Center))) => bail!( + elem.span(), + "vertical floating placement must be `auto`, `top`, or `bottom`" + ), + (false, Smart::Auto) => bail!( + elem.span(), + "automatic positioning is only available for floating placement"; + hint: "you can enable floating placement with `place(float: true, ..)`" + ), + _ => {} + } + + if !float && scope == PlacementScope::Parent { + bail!( + elem.span(), + "parent-scoped positioning is currently only available for floating placement"; + hint: "you can enable floating placement with `place(float: true, ..)`" + ); + } + + let locator = self.locator.next(&elem.span()); + let clearance = elem.clearance(styles); + let delta = Axes::new(elem.dx(styles), elem.dy(styles)).resolve(styles); + self.output.push(Child::Placed(self.boxed(PlacedChild { + align_x, + align_y, + scope, + float, + clearance, + delta, + elem, + styles, + locator, + alignment, + cell: CachedCell::new(), + }))); + + Ok(()) + } + + /// Wraps a value in a bump-allocated box to reduce its footprint in the + /// [`Child`] enum. + fn boxed<T>(&self, value: T) -> BumpBox<'a, T> { + BumpBox::new_in(value, self.bump) + } +} + +/// A prepared child in flow layout. +/// +/// The larger variants are bump-boxed to keep the enum size down. +#[derive(Debug)] +pub enum Child<'a> { + /// An introspection tag. + Tag(&'a Tag), + /// Relative spacing with a specific weakness level. + Rel(Rel<Abs>, u8), + /// Fractional spacing. + Fr(Fr), + /// An already layouted line of a paragraph. + Line(BumpBox<'a, LineChild>), + /// An unbreakable block. + Single(BumpBox<'a, SingleChild<'a>>), + /// A breakable block. + Multi(BumpBox<'a, MultiChild<'a>>), + /// An absolutely or floatingly placed element. + Placed(BumpBox<'a, PlacedChild<'a>>), + /// A place flush. + Flush, + /// An explicit column break. + Break(bool), +} + +/// A child that encapsulates a layouted line of a paragraph. +#[derive(Debug)] +pub struct LineChild { + pub frame: Frame, + pub align: Axes<FixedAlignment>, + pub need: Abs, +} + +/// A child that encapsulates a prepared unbreakable block. +#[derive(Debug)] +pub struct SingleChild<'a> { + pub align: Axes<FixedAlignment>, + pub sticky: bool, + pub alone: bool, + pub fr: Option<Fr>, + elem: &'a Packed<BlockElem>, + styles: StyleChain<'a>, + locator: Locator<'a>, + cell: CachedCell<SourceResult<Frame>>, +} + +impl SingleChild<'_> { + /// Build the child's frame given the region's base size. + pub fn layout(&self, engine: &mut Engine, region: Region) -> SourceResult<Frame> { + self.cell.get_or_init(region, |mut region| { + // Vertical expansion is only kept if this block is the only child. + region.expand.y &= self.alone; + layout_single_impl( + engine.routines, + engine.world, + engine.introspector, + engine.traced, + TrackedMut::reborrow_mut(&mut engine.sink), + engine.route.track(), + self.elem, + self.locator.track(), + self.styles, + region, + ) + }) + } +} + +/// The cached, internal implementation of [`SingleChild::layout`]. +#[comemo::memoize] +#[allow(clippy::too_many_arguments)] +fn layout_single_impl( + routines: &Routines, + world: Tracked<dyn World + '_>, + introspector: Tracked<Introspector>, + traced: Tracked<Traced>, + sink: TrackedMut<Sink>, + route: Tracked<Route>, + elem: &Packed<BlockElem>, + locator: Tracked<Locator>, + styles: StyleChain, + region: Region, +) -> SourceResult<Frame> { + let link = LocatorLink::new(locator); + let locator = Locator::link(&link); + let mut engine = Engine { + routines, + world, + introspector, + traced, + sink, + route: Route::extend(route), + }; + + layout_single_block(elem, &mut engine, locator, styles, region) + .map(|frame| frame.post_processed(styles)) +} + +/// A child that encapsulates a prepared breakable block. +#[derive(Debug)] +pub struct MultiChild<'a> { + pub align: Axes<FixedAlignment>, + pub sticky: bool, + alone: bool, + elem: &'a Packed<BlockElem>, + styles: StyleChain<'a>, + locator: Locator<'a>, + cell: CachedCell<SourceResult<Fragment>>, +} + +impl<'a> MultiChild<'a> { + /// Build the child's frames given regions. + pub fn layout<'b>( + &'b self, + engine: &mut Engine, + regions: Regions, + ) -> SourceResult<(Frame, Option<MultiSpill<'a, 'b>>)> { + let fragment = self.layout_full(engine, regions)?; + + // Extract the first frame. + let mut frames = fragment.into_iter(); + let frame = frames.next().unwrap(); + + // If there's more, return a `spill`. + let mut spill = None; + if frames.next().is_some() { + spill = Some(MultiSpill { + multi: self, + full: regions.full, + first: regions.size.y, + backlog: vec![], + min_backlog_len: regions.backlog.len(), + }); + } + + Ok((frame, spill)) + } + + /// The shared internal implementation of [`Self::layout`] and + /// [`MultiSpill::layout`]. + fn layout_full( + &self, + engine: &mut Engine, + regions: Regions, + ) -> SourceResult<Fragment> { + self.cell.get_or_init(regions, |mut regions| { + // Vertical expansion is only kept if this block is the only child. + regions.expand.y &= self.alone; + layout_multi_impl( + engine.routines, + engine.world, + engine.introspector, + engine.traced, + TrackedMut::reborrow_mut(&mut engine.sink), + engine.route.track(), + self.elem, + self.locator.track(), + self.styles, + regions, + ) + }) + } +} + +/// The cached, internal implementation of [`MultiChild::layout_full`]. +#[comemo::memoize] +#[allow(clippy::too_many_arguments)] +fn layout_multi_impl( + routines: &Routines, + world: Tracked<dyn World + '_>, + introspector: Tracked<Introspector>, + traced: Tracked<Traced>, + sink: TrackedMut<Sink>, + route: Tracked<Route>, + elem: &Packed<BlockElem>, + locator: Tracked<Locator>, + styles: StyleChain, + regions: Regions, +) -> SourceResult<Fragment> { + let link = LocatorLink::new(locator); + let locator = Locator::link(&link); + let mut engine = Engine { + routines, + world, + introspector, + traced, + sink, + route: Route::extend(route), + }; + + layout_multi_block(elem, &mut engine, locator, styles, regions).map(|mut fragment| { + for frame in &mut fragment { + frame.post_process(styles); + } + fragment + }) +} + +/// The spilled remains of a `MultiChild` that broke across two regions. +#[derive(Debug, Clone)] +pub struct MultiSpill<'a, 'b> { + multi: &'b MultiChild<'a>, + first: Abs, + full: Abs, + backlog: Vec<Abs>, + min_backlog_len: usize, +} + +impl MultiSpill<'_, '_> { + /// Build the spill's frames given regions. + pub fn layout( + mut self, + engine: &mut Engine, + regions: Regions, + ) -> SourceResult<(Frame, Option<Self>)> { + // The first region becomes unchangable and committed to our backlog. + self.backlog.push(regions.size.y); + + // The remaining regions are ephemeral and may be replaced. + let mut backlog: Vec<_> = + self.backlog.iter().chain(regions.backlog).copied().collect(); + + // Remove unnecessary backlog items to prevent it from growing + // unnecessarily, changing the region's hash. + while backlog.len() > self.min_backlog_len + && backlog.last().copied() == regions.last + { + backlog.pop(); + } + + // Build the pod with the merged regions. + let pod = Regions { + size: Size::new(regions.size.x, self.first), + expand: regions.expand, + full: self.full, + backlog: &backlog, + last: regions.last, + }; + + // Extract the not-yet-processed frames. + let mut frames = self + .multi + .layout_full(engine, pod)? + .into_iter() + .skip(self.backlog.len()); + + // Ensure that the backlog never shrinks, so that unwrapping below is at + // least fairly safe. Note that the whole region juggling here is + // fundamentally not ideal: It is a compatibility layer between the old + // (all regions provided upfront) & new (each region provided on-demand, + // like an iterator) layout model. This approach is not 100% correct, as + // in the old model later regions could have an effect on earlier + // frames, but it's the best we can do for now, until the multi + // layouters are refactored to the new model. + self.min_backlog_len = self.min_backlog_len.max(backlog.len()); + + // Save the first frame. + let frame = frames.next().unwrap(); + + // If there's more, return a `spill`. + let mut spill = None; + if frames.next().is_some() { + spill = Some(self); + } + + Ok((frame, spill)) + } + + /// The alignment of the breakable block. + pub fn align(&self) -> Axes<FixedAlignment> { + self.multi.align + } +} + +/// A child that encapsulates a prepared placed element. +#[derive(Debug)] +pub struct PlacedChild<'a> { + pub align_x: FixedAlignment, + pub align_y: Smart<Option<FixedAlignment>>, + pub scope: PlacementScope, + pub float: bool, + pub clearance: Abs, + pub delta: Axes<Rel<Abs>>, + elem: &'a Packed<PlaceElem>, + styles: StyleChain<'a>, + locator: Locator<'a>, + alignment: Smart<Alignment>, + cell: CachedCell<SourceResult<Frame>>, +} + +impl PlacedChild<'_> { + /// Build the child's frame given the region's base size. + pub fn layout(&self, engine: &mut Engine, base: Size) -> SourceResult<Frame> { + self.cell.get_or_init(base, |base| { + let align = self.alignment.unwrap_or_else(|| Alignment::CENTER); + let aligned = AlignElem::set_alignment(align).wrap(); + + let mut frame = crate::layout_frame( + engine, + &self.elem.body, + self.locator.relayout(), + self.styles.chain(&aligned), + Region::new(base, Axes::splat(false)), + )?; + + if self.float { + frame.set_parent(self.elem.location().unwrap()); + } + + Ok(frame.post_processed(self.styles)) + }) + } + + /// The element's location. + pub fn location(&self) -> Location { + self.elem.location().unwrap() + } +} + +/// Wraps a parameterized computation and caches its latest output. +/// +/// - When the computation is performed multiple times consecutively with the +/// same argument, reuses the cache. +/// - When the argument changes, the new output is cached. +#[derive(Clone)] +struct CachedCell<T>(RefCell<Option<(u128, T)>>); + +impl<T> CachedCell<T> { + /// Create an empty cached cell. + fn new() -> Self { + Self(RefCell::new(None)) + } + + /// Perform the computation `f` with caching. + fn get_or_init<F, I>(&self, input: I, f: F) -> T + where + I: Hash, + T: Clone, + F: FnOnce(I) -> T, + { + let input_hash = typst_utils::hash128(&input); + + let mut slot = self.0.borrow_mut(); + if let Some((hash, output)) = &*slot { + if *hash == input_hash { + return output.clone(); + } + } + + let output = f(input); + *slot = Some((input_hash, output.clone())); + output + } +} + +impl<T> Default for CachedCell<T> { + fn default() -> Self { + Self::new() + } +} + +impl<T> Debug for CachedCell<T> { + fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { + f.pad("CachedCell(..)") + } +} diff --git a/crates/typst-layout/src/flow/compose.rs b/crates/typst-layout/src/flow/compose.rs new file mode 100644 index 00000000..932ccc9a --- /dev/null +++ b/crates/typst-layout/src/flow/compose.rs @@ -0,0 +1,877 @@ +use std::num::NonZeroUsize; + +use typst_library::diag::SourceResult; +use typst_library::engine::Engine; +use typst_library::foundations::{Content, NativeElement, Packed, Resolve, Smart}; +use typst_library::introspection::{ + Counter, CounterDisplayElem, CounterState, CounterUpdate, Location, Locator, + SplitLocator, Tag, +}; +use typst_library::layout::{ + Abs, Axes, Dir, FixedAlignment, Fragment, Frame, FrameItem, OuterHAlignment, + PlacementScope, Point, Region, Regions, Rel, Size, +}; +use typst_library::model::{ + FootnoteElem, FootnoteEntry, LineNumberingScope, Numbering, ParLineMarker, +}; +use typst_syntax::Span; +use typst_utils::NonZeroExt; + +use super::{distribute, Config, FlowResult, LineNumberConfig, PlacedChild, Stop, Work}; + +/// Composes the contents of a single page/region. A region can have multiple +/// columns/subregions. +/// +/// The composer is primarily concerned with layout of out-of-flow insertions +/// (floats and footnotes). It does this in per-page and per-column loops that +/// rerun when a new float is added (since it affects the regions available to +/// the distributor). +/// +/// To lay out the in-flow contents of individual subregions, the composer +/// invokes [distribution](distribute). +pub fn compose( + engine: &mut Engine, + work: &mut Work, + config: &Config, + locator: Locator, + regions: Regions, +) -> SourceResult<Frame> { + Composer { + engine, + config, + page_base: regions.base(), + column: 0, + page_insertions: Insertions::default(), + column_insertions: Insertions::default(), + work, + footnote_spill: None, + footnote_queue: vec![], + } + .page(locator, regions) +} + +/// State for composition. +/// +/// Sadly, we need that many lifetimes because &mut references are invariant and +/// it would force the lifetimes of various things to be equal if they +/// shared a lifetime. +/// +/// The only interesting lifetimes are 'a and 'b. See [Work] for more details +/// about them. +pub struct Composer<'a, 'b, 'x, 'y> { + pub engine: &'x mut Engine<'y>, + pub work: &'x mut Work<'a, 'b>, + pub config: &'x Config<'x>, + column: usize, + page_base: Size, + page_insertions: Insertions<'a, 'b>, + column_insertions: Insertions<'a, 'b>, + // These are here because they have to survive relayout (we could lose the + // footnotes otherwise). For floats, we revisit them anyway, so it's okay to + // use `work.floats` directly. This is not super clean; probably there's a + // better way. + footnote_spill: Option<std::vec::IntoIter<Frame>>, + footnote_queue: Vec<Packed<FootnoteElem>>, +} + +impl<'a, 'b> Composer<'a, 'b, '_, '_> { + /// Lay out a container/page region, including container/page insertions. + fn page(mut self, locator: Locator, regions: Regions) -> SourceResult<Frame> { + // This loop can restart region layout when requested to do so by a + // `Stop`. This happens when there is a parent-scoped float. + let checkpoint = self.work.clone(); + let output = loop { + // Shrink the available space by the space used by page + // insertions. + let mut pod = regions; + pod.size.y -= self.page_insertions.height(); + + match self.page_contents(locator.relayout(), pod) { + Ok(frame) => break frame, + Err(Stop::Finish(_)) => unreachable!(), + Err(Stop::Relayout(PlacementScope::Column)) => unreachable!(), + Err(Stop::Relayout(PlacementScope::Parent)) => { + *self.work = checkpoint.clone(); + continue; + } + Err(Stop::Error(err)) => return Err(err), + }; + }; + drop(checkpoint); + + Ok(self.page_insertions.finalize(self.work, self.config, output)) + } + + /// Lay out the inner contents of a container/page. + fn page_contents(&mut self, locator: Locator, regions: Regions) -> FlowResult<Frame> { + // No point in create column regions, if there's just one! + if self.config.columns.count == 1 { + return self.column(locator, regions); + } + + // Create a backlog for multi-column layout. + let column_height = regions.size.y; + let backlog: Vec<_> = std::iter::once(&column_height) + .chain(regions.backlog) + .flat_map(|&h| std::iter::repeat(h).take(self.config.columns.count)) + .skip(1) + .collect(); + + // Subregions for column layout. + let mut inner = Regions { + size: Size::new(self.config.columns.width, column_height), + backlog: &backlog, + expand: Axes::new(true, regions.expand.y), + ..regions + }; + + // The size of the merged frame hosting multiple columns. + let size = Size::new( + regions.size.x, + if regions.expand.y { regions.size.y } else { Abs::zero() }, + ); + + let mut output = Frame::hard(size); + let mut offset = Abs::zero(); + let mut locator = locator.split(); + + // Lay out the columns and stitch them together. + for i in 0..self.config.columns.count { + self.column = i; + let frame = self.column(locator.next(&()), inner)?; + + if !regions.expand.y { + output.size_mut().y.set_max(frame.height()); + } + + let width = frame.width(); + let x = if self.config.columns.dir == Dir::LTR { + offset + } else { + regions.size.x - offset - width + }; + offset += width + self.config.columns.gutter; + + output.push_frame(Point::with_x(x), frame); + inner.next(); + } + + Ok(output) + } + + /// Lay out a column, including column insertions. + fn column(&mut self, locator: Locator, regions: Regions) -> FlowResult<Frame> { + // Reset column insertion when starting a new column. + self.column_insertions = Insertions::default(); + + // Process footnote spill. + if let Some(spill) = self.work.footnote_spill.take() { + self.footnote_spill(spill, regions.base())?; + } + + // This loop can restart column layout when requested to do so by a + // `Stop`. This happens when there is a column-scoped float. + let checkpoint = self.work.clone(); + let inner = loop { + // Shrink the available space by the space used by column + // insertions. + let mut pod = regions; + pod.size.y -= self.column_insertions.height(); + + match self.column_contents(pod) { + Ok(frame) => break frame, + Err(Stop::Finish(_)) => unreachable!(), + Err(Stop::Relayout(PlacementScope::Column)) => { + *self.work = checkpoint.clone(); + continue; + } + err => return err, + } + }; + drop(checkpoint); + + self.work.footnotes.extend(self.footnote_queue.drain(..)); + if let Some(spill) = self.footnote_spill.take() { + self.work.footnote_spill = Some(spill); + } + + let insertions = std::mem::take(&mut self.column_insertions); + let mut output = insertions.finalize(self.work, self.config, inner); + + // Lay out per-column line numbers. + if let Some(line_config) = &self.config.line_numbers { + layout_line_numbers( + self.engine, + self.config, + line_config, + locator, + self.column, + &mut output, + )?; + } + + Ok(output) + } + + /// Lay out the inner contents of a column. + fn column_contents(&mut self, regions: Regions) -> FlowResult<Frame> { + // Process pending footnotes. + for note in std::mem::take(&mut self.work.footnotes) { + self.footnote(note, &mut regions.clone(), Abs::zero(), false)?; + } + + // Process pending floats. + for placed in std::mem::take(&mut self.work.floats) { + self.float(placed, ®ions, false)?; + } + + distribute(self, regions) + } + + /// Lays out an item with floating placement. + /// + /// This is called from within [`distribute`]. When the float fits, this + /// returns an `Err(Stop::Relayout(..))`, which bubbles all the way through + /// distribution and is handled in [`Self::page`] or [`Self::column`] + /// (depending on `placed.scope`). + /// + /// When the float does not fit, it is queued into `work.floats`. The + /// value of `clearance` that between the float and flow content is needed + /// --- it is set if there are already distributed items. + pub fn float( + &mut self, + placed: &'b PlacedChild<'a>, + regions: &Regions, + clearance: bool, + ) -> FlowResult<()> { + // If the float is already processed, skip it. + let loc = placed.location(); + if self.skipped(loc) { + return Ok(()); + } + + // If there is already a queued float, queue this one as well. We + // don't want to disrupt the order. + if !self.work.floats.is_empty() { + self.work.floats.push(placed); + return Ok(()); + } + + // Determine the base size of the chosen scope. + let base = match placed.scope { + PlacementScope::Column => regions.base(), + PlacementScope::Parent => self.page_base, + }; + + // Lay out the placed element. + let frame = placed.layout(self.engine, base)?; + + // Determine the remaining space in the scope. This is exact for column + // placement, but only an approximation for page placement. + let remaining = match placed.scope { + PlacementScope::Column => regions.size.y, + PlacementScope::Parent => { + let remaining: Abs = regions + .iter() + .map(|size| size.y) + .take(self.config.columns.count - self.column) + .sum(); + remaining / self.config.columns.count as f64 + } + }; + + // We only require clearance if there is other content. + let clearance = if clearance { placed.clearance } else { Abs::zero() }; + let need = frame.height() + clearance; + + // If the float doesn't fit, queue it for the next region. + if !remaining.fits(need) && regions.may_progress() { + self.work.floats.push(placed); + return Ok(()); + } + + // Handle footnotes in the float. + self.footnotes(regions, &frame, need, false)?; + + // Determine the float's vertical alignment. We can unwrap the inner + // `Option` because `Custom(None)` is checked for during collection. + let align_y = placed.align_y.map(Option::unwrap).unwrap_or_else(|| { + // When the float's vertical midpoint would be above the middle of + // the page if it were layouted in-flow, we use top alignment. + // Otherwise, we use bottom alignment. + let used = base.y - remaining; + let half = need / 2.0; + let ratio = (used + half) / base.y; + if ratio <= 0.5 { + FixedAlignment::Start + } else { + FixedAlignment::End + } + }); + + // Select the insertion area where we'll put this float. + let area = match placed.scope { + PlacementScope::Column => &mut self.column_insertions, + PlacementScope::Parent => &mut self.page_insertions, + }; + + // Put the float there. + area.push_float(placed, frame, align_y); + area.skips.push(loc); + + // Trigger relayout. + Err(Stop::Relayout(placed.scope)) + } + + /// Lays out footnotes in the `frame` if this is the root flow and there are + /// any. The value of `breakable` indicates whether the element that + /// produced the frame is breakable. If not, the frame is treated as atomic. + pub fn footnotes( + &mut self, + regions: &Regions, + frame: &Frame, + flow_need: Abs, + breakable: bool, + ) -> FlowResult<()> { + // Footnotes are only supported at the root level. + if !self.config.root { + return Ok(()); + } + + // Search for footnotes. + let mut notes = vec![]; + for tag in &self.work.tags { + let Tag::Start(elem) = tag else { continue }; + let Some(note) = elem.to_packed::<FootnoteElem>() else { continue }; + notes.push((Abs::zero(), note.clone())); + } + find_in_frame_impl::<FootnoteElem>(&mut notes, frame, Abs::zero()); + if notes.is_empty() { + return Ok(()); + } + + let mut relayout = false; + let mut regions = *regions; + let mut migratable = !breakable && regions.may_progress(); + + for (y, elem) in notes { + // The amount of space used by the in-flow content that contains the + // footnote marker. For a breakable frame, it's the y position of + // the marker. For an unbreakable frame, it's the full height. + let flow_need = if breakable { y } else { flow_need }; + + // Process the footnote. + match self.footnote(elem, &mut regions, flow_need, migratable) { + // The footnote was already processed or queued. + Ok(()) => {} + // First handle more footnotes before relayouting. + Err(Stop::Relayout(_)) => relayout = true, + // Either of + // - A `Stop::Finish` indicating that the frame's origin element + // should migrate to uphold the footnote invariant. + // - A fatal error. + err => return err, + } + + // We only migrate the origin frame if the first footnote's first + // line didn't fit. + migratable = false; + } + + // If this is set, we laid out at least one footnote, so we need a + // relayout. + if relayout { + return Err(Stop::Relayout(PlacementScope::Column)); + } + + Ok(()) + } + + /// Handles a single footnote. + fn footnote( + &mut self, + elem: Packed<FootnoteElem>, + regions: &mut Regions, + flow_need: Abs, + migratable: bool, + ) -> FlowResult<()> { + // Ignore reference footnotes and already processed ones. + let loc = elem.location().unwrap(); + if elem.is_ref() || self.skipped(loc) { + return Ok(()); + } + + // If there is already a queued spill or footnote, queue this one as + // well. We don't want to disrupt the order. + let area = &mut self.column_insertions; + if self.footnote_spill.is_some() || !self.footnote_queue.is_empty() { + self.footnote_queue.push(elem); + return Ok(()); + } + + // If there weren't any footnotes so far, account for the footnote + // separator. + let mut separator = None; + let mut separator_need = Abs::zero(); + if area.footnotes.is_empty() { + let frame = + layout_footnote_separator(self.engine, self.config, regions.base())?; + separator_need += self.config.footnote.clearance + frame.height(); + separator = Some(frame); + } + + // Prepare regions for the footnote. + let mut pod = *regions; + pod.expand.y = false; + pod.size.y -= flow_need + separator_need + self.config.footnote.gap; + + // Layout the footnote entry. + let frames = layout_footnote(self.engine, self.config, &elem, pod)?.into_frames(); + + // Find nested footnotes in the entry. + let nested = find_in_frames::<FootnoteElem>(&frames); + + // Extract the first frame. + let mut iter = frames.into_iter(); + let first = iter.next().unwrap(); + let note_need = self.config.footnote.gap + first.height(); + + // If the first frame is empty, then none of its content fit. If + // possible, we then migrate the origin frame to the next region to + // uphold the footnote invariant (that marker and entry are on the same + // page). If not, we just queue the footnote for the next page. + if first.is_empty() { + if migratable { + return Err(Stop::Finish(false)); + } else { + self.footnote_queue.push(elem); + return Ok(()); + } + } + + // Save the separator. + if let Some(frame) = separator { + area.push_footnote_separator(self.config, frame); + regions.size.y -= separator_need; + } + + // Save the footnote's frame. + area.push_footnote(self.config, first); + area.skips.push(loc); + regions.size.y -= note_need; + + // Save the spill. + if !iter.as_slice().is_empty() { + self.footnote_spill = Some(iter); + } + + // Lay out nested footnotes. + for (_, note) in nested { + self.footnote(note, regions, flow_need, migratable)?; + } + + // Since we laid out a footnote, we need a relayout. + Err(Stop::Relayout(PlacementScope::Column)) + } + + /// Handles spillover from a footnote. + fn footnote_spill( + &mut self, + mut iter: std::vec::IntoIter<Frame>, + base: Size, + ) -> SourceResult<()> { + let area = &mut self.column_insertions; + + // Create and save the separator. + let separator = layout_footnote_separator(self.engine, self.config, base)?; + area.push_footnote_separator(self.config, separator); + + // Save the footnote's frame. + let frame = iter.next().unwrap(); + area.push_footnote(self.config, frame); + + // Save the spill. + if !iter.as_slice().is_empty() { + self.footnote_spill = Some(iter); + } + + Ok(()) + } + + /// Checks whether an insertion was already processed and doesn't need to be + /// handled again. + fn skipped(&self, loc: Location) -> bool { + self.work.skips.contains(&loc) + || self.page_insertions.skips.contains(&loc) + || self.column_insertions.skips.contains(&loc) + } + + /// The amount of width needed by insertions. + pub fn insertion_width(&self) -> Abs { + self.column_insertions.width.max(self.page_insertions.width) + } +} + +/// Lay out the footnote separator, typically a line. +fn layout_footnote_separator( + engine: &mut Engine, + config: &Config, + base: Size, +) -> SourceResult<Frame> { + crate::layout_frame( + engine, + &config.footnote.separator, + Locator::root(), + config.shared, + Region::new(base, Axes::new(config.footnote.expand, false)), + ) +} + +/// Lay out a footnote. +fn layout_footnote( + engine: &mut Engine, + config: &Config, + elem: &Packed<FootnoteElem>, + pod: Regions, +) -> SourceResult<Fragment> { + let loc = elem.location().unwrap(); + crate::layout_fragment( + engine, + &FootnoteEntry::new(elem.clone()).pack(), + Locator::synthesize(loc), + config.shared, + pod, + ) + .map(|mut fragment| { + for frame in &mut fragment { + frame.set_parent(loc); + } + fragment + }) +} + +/// An additive list of insertions. +#[derive(Default)] +struct Insertions<'a, 'b> { + top_floats: Vec<(&'b PlacedChild<'a>, Frame)>, + bottom_floats: Vec<(&'b PlacedChild<'a>, Frame)>, + footnotes: Vec<Frame>, + footnote_separator: Option<Frame>, + top_size: Abs, + bottom_size: Abs, + width: Abs, + skips: Vec<Location>, +} + +impl<'a, 'b> Insertions<'a, 'b> { + /// Add a float to the top or bottom area. + fn push_float( + &mut self, + placed: &'b PlacedChild<'a>, + frame: Frame, + align_y: FixedAlignment, + ) { + self.width.set_max(frame.width()); + + let amount = frame.height() + placed.clearance; + let pair = (placed, frame); + + if align_y == FixedAlignment::Start { + self.top_size += amount; + self.top_floats.push(pair); + } else { + self.bottom_size += amount; + self.bottom_floats.push(pair); + } + } + + /// Add a footnote to the bottom area. + fn push_footnote(&mut self, config: &Config, frame: Frame) { + self.width.set_max(frame.width()); + self.bottom_size += config.footnote.gap + frame.height(); + self.footnotes.push(frame); + } + + /// Add a footnote separator to the bottom area. + fn push_footnote_separator(&mut self, config: &Config, frame: Frame) { + self.width.set_max(frame.width()); + self.bottom_size += config.footnote.clearance + frame.height(); + self.footnote_separator = Some(frame); + } + + /// The combined height of the top and bottom area (includings clearances). + /// Subtracting this from the total region size yields the available space + /// for distribution. + fn height(&self) -> Abs { + self.top_size + self.bottom_size + } + + /// Produce a frame for the full region based on the `inner` frame produced + /// by distribution or column layout. + fn finalize(self, work: &mut Work, config: &Config, inner: Frame) -> Frame { + work.extend_skips(&self.skips); + + if self.top_floats.is_empty() + && self.bottom_floats.is_empty() + && self.footnote_separator.is_none() + && self.footnotes.is_empty() + { + return inner; + } + + let size = inner.size() + Size::with_y(self.height()); + + let mut output = Frame::soft(size); + let mut offset_top = Abs::zero(); + let mut offset_bottom = size.y - self.bottom_size; + + for (placed, frame) in self.top_floats { + let x = placed.align_x.position(size.x - frame.width()); + let y = offset_top; + let delta = placed.delta.zip_map(size, Rel::relative_to).to_point(); + offset_top += frame.height() + placed.clearance; + output.push_frame(Point::new(x, y) + delta, frame); + } + + output.push_frame(Point::with_y(self.top_size), inner); + + // We put floats first and then footnotes. This differs from what LaTeX + // does and is a little inconsistent w.r.t column vs page floats (page + // floats are below footnotes because footnotes are per column), but + // it's what most people (including myself) seem to intuitively expect. + // We experimented with the LaTeX ordering in 0.12.0-rc1, but folks were + // surprised and considered this strange. In LaTeX, it can be changed + // with `\usepackage[bottom]{footmisc}`. We could also consider adding + // configuration in the future. + for (placed, frame) in self.bottom_floats { + offset_bottom += placed.clearance; + let x = placed.align_x.position(size.x - frame.width()); + let y = offset_bottom; + let delta = placed.delta.zip_map(size, Rel::relative_to).to_point(); + offset_bottom += frame.height(); + output.push_frame(Point::new(x, y) + delta, frame); + } + + if let Some(frame) = self.footnote_separator { + offset_bottom += config.footnote.clearance; + let y = offset_bottom; + offset_bottom += frame.height(); + output.push_frame(Point::with_y(y), frame); + } + + for frame in self.footnotes { + offset_bottom += config.footnote.gap; + let y = offset_bottom; + offset_bottom += frame.height(); + output.push_frame(Point::with_y(y), frame); + } + + output + } +} + +/// Lay out the given collected lines' line numbers to an output frame. +/// +/// The numbers are placed either on the left margin (left border of the frame) +/// or on the right margin (right border). Before they are placed, a line number +/// counter reset is inserted if we're in the first column of the page being +/// currently laid out and the user requested for line numbers to be reset at +/// the start of every page. +fn layout_line_numbers( + engine: &mut Engine, + config: &Config, + line_config: &LineNumberConfig, + locator: Locator, + column: usize, + output: &mut Frame, +) -> SourceResult<()> { + let mut locator = locator.split(); + + // Reset page-scoped line numbers if currently at the first column. + if column == 0 && line_config.scope == LineNumberingScope::Page { + let reset = layout_line_number_reset(engine, config, &mut locator)?; + output.push_frame(Point::zero(), reset); + } + + // Find all line markers. + let mut lines = find_in_frame::<ParLineMarker>(output); + if lines.is_empty() { + return Ok(()); + } + + // Assume the line numbers aren't sorted by height. They must be sorted so + // we can deduplicate line numbers below based on vertical proximity. + lines.sort_by_key(|&(y, _)| y); + + // Used for horizontal alignment. + let mut max_number_width = Abs::zero(); + + // This is used to skip lines that are too close together. + let mut prev_bottom = None; + + // Buffer line number frames so we can align them horizontally later before + // placing, based on the width of the largest line number. + let mut line_numbers = vec![]; + + // Layout the lines. + for &(y, ref marker) in &lines { + if prev_bottom.is_some_and(|bottom| y < bottom) { + // Lines are too close together. Display as the same line number. + continue; + } + + // Layout the number and record its width in search of the maximium. + let frame = layout_line_number(engine, config, &mut locator, &marker.numbering)?; + + // Note that this line.y is larger than the previous due to sorting. + // Therefore, the check at the top of the loop ensures no line numbers + // will reasonably intersect with each other. We enforce a minimum + // spacing of 1pt between consecutive line numbers in case a zero-height + // frame is used. + prev_bottom = Some(y + frame.height().max(Abs::pt(1.0))); + max_number_width.set_max(frame.width()); + line_numbers.push((y, marker, frame)); + } + + for (y, marker, frame) in line_numbers { + // The last column will always place line numbers at the end + // margin. This should become configurable in the future. + let margin = { + let opposite = + config.columns.count >= 2 && column + 1 == config.columns.count; + if opposite { OuterHAlignment::End } else { marker.number_margin } + .resolve(config.shared) + }; + + // Determine how much space to leave between the column and the number. + let clearance = match marker.number_clearance { + Smart::Auto => line_config.default_clearance, + Smart::Custom(rel) => rel.resolve(config.shared), + }; + + // Compute the base X position. + let x = match margin { + // Move the number to the left of the left edge (at 0pt) by the maximum + // width and the clearance. + FixedAlignment::Start => -max_number_width - clearance, + // Move the number to the right edge and add clearance. + FixedAlignment::End => output.width() + clearance, + // Can't happen due to `OuterHAlignment`. + FixedAlignment::Center => unreachable!(), + }; + + // Determine how much to shift the number due to its alignment. + let shift = { + let align = marker + .number_align + .map(|align| align.resolve(config.shared)) + .unwrap_or_else(|| margin.inv()); + align.position(max_number_width - frame.width()) + }; + + // Compute the final position of the number and add it to the output. + let pos = Point::new(x + shift, y); + output.push_frame(pos, frame); + } + + Ok(()) +} + +/// Creates a frame that resets the line number counter. +fn layout_line_number_reset( + engine: &mut Engine, + config: &Config, + locator: &mut SplitLocator, +) -> SourceResult<Frame> { + let counter = Counter::of(ParLineMarker::elem()); + let update = CounterUpdate::Set(CounterState::init(false)); + let content = counter.update(Span::detached(), update); + crate::layout_frame( + engine, + &content, + locator.next(&()), + config.shared, + Region::new(Axes::splat(Abs::zero()), Axes::splat(false)), + ) +} + +/// Layout the line number associated with the given line marker. +/// +/// Produces a counter update and counter display with counter key +/// `ParLineMarker`. We use `ParLineMarker` as it is an element which is not +/// exposed to the user and we don't want to expose the line number counter at +/// the moment, given that its semantics are inconsistent with that of normal +/// counters (the counter is updated based on height and not on frame order / +/// layer). When we find a solution to this, we should switch to a counter on +/// `ParLine` instead, thus exposing the counter as `counter(par.line)` to the +/// user. +fn layout_line_number( + engine: &mut Engine, + config: &Config, + locator: &mut SplitLocator, + numbering: &Numbering, +) -> SourceResult<Frame> { + let counter = Counter::of(ParLineMarker::elem()); + let update = CounterUpdate::Step(NonZeroUsize::ONE); + let numbering = Smart::Custom(numbering.clone()); + + // Combine counter update and display into the content we'll layout. + let content = Content::sequence(vec![ + counter.clone().update(Span::detached(), update), + CounterDisplayElem::new(counter, numbering, false).pack(), + ]); + + // Layout the number. + let mut frame = crate::layout_frame( + engine, + &content, + locator.next(&()), + config.shared, + Region::new(Axes::splat(Abs::inf()), Axes::splat(false)), + )?; + + // Ensure the baseline of the line number aligns with the line's baseline. + frame.translate(Point::with_y(-frame.baseline())); + + Ok(frame) +} + +/// Collect all matching elements and their vertical positions in the frame. +/// +/// On each subframe we encounter, we add that subframe's position to `prev_y`, +/// until we reach a tag, at which point we add the tag's position and finish. +/// That gives us the absolute height of the tag from the start of the root +/// frame. +fn find_in_frame<T: NativeElement>(frame: &Frame) -> Vec<(Abs, Packed<T>)> { + let mut output = vec![]; + find_in_frame_impl(&mut output, frame, Abs::zero()); + output +} + +/// Collect all matching elements and their vertical positions in the frames. +fn find_in_frames<T: NativeElement>(frames: &[Frame]) -> Vec<(Abs, Packed<T>)> { + let mut output = vec![]; + for frame in frames { + find_in_frame_impl(&mut output, frame, Abs::zero()); + } + output +} + +fn find_in_frame_impl<T: NativeElement>( + output: &mut Vec<(Abs, Packed<T>)>, + frame: &Frame, + y_offset: Abs, +) { + for (pos, item) in frame.items() { + let y = y_offset + pos.y; + match item { + FrameItem::Group(group) => find_in_frame_impl(output, &group.frame, y), + FrameItem::Tag(Tag::Start(elem)) => { + if let Some(elem) = elem.to_packed::<T>() { + output.push((y, elem.clone())); + } + } + _ => {} + } + } +} diff --git a/crates/typst-layout/src/flow/distribute.rs b/crates/typst-layout/src/flow/distribute.rs new file mode 100644 index 00000000..1852f7ca --- /dev/null +++ b/crates/typst-layout/src/flow/distribute.rs @@ -0,0 +1,525 @@ +use typst_library::introspection::Tag; +use typst_library::layout::{ + Abs, Axes, FixedAlignment, Fr, Frame, FrameItem, Point, Region, Regions, Rel, Size, +}; +use typst_utils::Numeric; + +use super::{ + Child, Composer, FlowResult, LineChild, MultiChild, MultiSpill, PlacedChild, + SingleChild, Stop, Work, +}; + +/// Distributes as many children as fit from `composer.work` into the first +/// region and returns the resulting frame. +pub fn distribute(composer: &mut Composer, regions: Regions) -> FlowResult<Frame> { + let mut distributor = Distributor { + composer, + regions, + items: vec![], + sticky: None, + stickable: false, + }; + let init = distributor.snapshot(); + let forced = match distributor.run() { + Ok(()) => distributor.composer.work.done(), + Err(Stop::Finish(forced)) => forced, + Err(err) => return Err(err), + }; + let region = Region::new(regions.size, regions.expand); + distributor.finalize(region, init, forced) +} + +/// State for distribution. +/// +/// See [Composer] regarding lifetimes. +struct Distributor<'a, 'b, 'x, 'y, 'z> { + /// The composer that is used to handle insertions. + composer: &'z mut Composer<'a, 'b, 'x, 'y>, + /// Regions which are continously shrunk as new items are added. + regions: Regions<'z>, + /// Already laid out items, not yet aligned. + items: Vec<Item<'a, 'b>>, + /// A snapshot which can be restored to migrate a suffix of sticky blocks to + /// the next region. + sticky: Option<DistributionSnapshot<'a, 'b>>, + /// Whether there was at least one proper block. Otherwise, sticky blocks + /// are disabled (or else they'd keep being migrated). + stickable: bool, +} + +/// A snapshot of the distribution state. +struct DistributionSnapshot<'a, 'b> { + work: Work<'a, 'b>, + items: usize, +} + +/// A laid out item in a distribution. +enum Item<'a, 'b> { + /// An introspection tag. + Tag(&'a Tag), + /// Absolute spacing and its weakness level. + Abs(Abs, u8), + /// Fractional spacing or a fractional block. + Fr(Fr, Option<&'b SingleChild<'a>>), + /// A frame for a laid out line or block. + Frame(Frame, Axes<FixedAlignment>), + /// A frame for an absolutely (not floatingly) placed child. + Placed(Frame, &'b PlacedChild<'a>), +} + +impl Item<'_, '_> { + /// Whether this item should be migrated to the next region if the region + /// consists solely of such items. + fn migratable(&self) -> bool { + match self { + Self::Tag(_) => true, + Self::Frame(frame, _) => { + frame.size().is_zero() + && frame.items().all(|(_, item)| { + matches!(item, FrameItem::Link(_, _) | FrameItem::Tag(_)) + }) + } + Self::Placed(_, placed) => !placed.float, + _ => false, + } + } +} + +impl<'a, 'b> Distributor<'a, 'b, '_, '_, '_> { + /// Distributes content into the region. + fn run(&mut self) -> FlowResult<()> { + // First, handle spill of a breakable block. + if let Some(spill) = self.composer.work.spill.take() { + self.multi_spill(spill)?; + } + + // If spill are taken care of, process children until no space is left + // or no children are left. + while let Some(child) = self.composer.work.head() { + self.child(child)?; + self.composer.work.advance(); + } + + Ok(()) + } + + /// Processes a single child. + /// + /// - Returns `Ok(())` if the child was successfully processed. + /// - Returns `Err(Stop::Finish)` if a region break should be triggered. + /// - Returns `Err(Stop::Relayout(_))` if the region needs to be relayouted + /// due to an insertion (float/footnote). + /// - Returns `Err(Stop::Error(_))` if there was a fatal error. + fn child(&mut self, child: &'b Child<'a>) -> FlowResult<()> { + match child { + Child::Tag(tag) => self.tag(tag), + Child::Rel(amount, weakness) => self.rel(*amount, *weakness), + Child::Fr(fr) => self.fr(*fr), + Child::Line(line) => self.line(line)?, + Child::Single(single) => self.single(single)?, + Child::Multi(multi) => self.multi(multi)?, + Child::Placed(placed) => self.placed(placed)?, + Child::Flush => self.flush()?, + Child::Break(weak) => self.break_(*weak)?, + } + Ok(()) + } + + /// Processes a tag. + fn tag(&mut self, tag: &'a Tag) { + self.composer.work.tags.push(tag); + } + + /// Generate items for pending tags. + fn flush_tags(&mut self) { + if !self.composer.work.tags.is_empty() { + let tags = &mut self.composer.work.tags; + self.items.extend(tags.iter().copied().map(Item::Tag)); + tags.clear(); + } + } + + /// Processes relative spacing. + fn rel(&mut self, amount: Rel<Abs>, weakness: u8) { + let amount = amount.relative_to(self.regions.base().y); + if weakness > 0 && !self.keep_spacing(amount, weakness) { + return; + } + + self.regions.size.y -= amount; + self.items.push(Item::Abs(amount, weakness)); + } + + /// Processes fractional spacing. + fn fr(&mut self, fr: Fr) { + self.trim_spacing(); + self.items.push(Item::Fr(fr, None)); + } + + /// Decides whether to keep weak spacing based on previous items. If there + /// is a preceding weak spacing, it might be patched in place. + fn keep_spacing(&mut self, amount: Abs, weakness: u8) -> bool { + for item in self.items.iter_mut().rev() { + match *item { + Item::Abs(prev_amount, prev_weakness @ 1..) => { + if weakness <= prev_weakness + && (weakness < prev_weakness || amount > prev_amount) + { + self.regions.size.y -= amount - prev_amount; + *item = Item::Abs(amount, weakness); + } + return false; + } + Item::Tag(_) | Item::Abs(..) | Item::Placed(..) => {} + Item::Fr(.., None) => return false, + Item::Frame(..) | Item::Fr(.., Some(_)) => return true, + } + } + false + } + + /// Trims trailing weak spacing from the items. + fn trim_spacing(&mut self) { + for (i, item) in self.items.iter().enumerate().rev() { + match *item { + Item::Abs(amount, 1..) => { + self.regions.size.y += amount; + self.items.remove(i); + break; + } + Item::Tag(_) | Item::Abs(..) | Item::Placed(..) => {} + Item::Frame(..) | Item::Fr(..) => break, + } + } + } + + /// The amount of trailing weak spacing. + fn weak_spacing(&mut self) -> Abs { + for item in self.items.iter().rev() { + match *item { + Item::Abs(amount, 1..) => return amount, + Item::Tag(_) | Item::Abs(..) | Item::Placed(..) => {} + Item::Frame(..) | Item::Fr(..) => break, + } + } + Abs::zero() + } + + /// Processes a line of a paragraph. + fn line(&mut self, line: &'b LineChild) -> FlowResult<()> { + // If the line doesn't fit and a followup region may improve things, + // finish the region. + if !self.regions.size.y.fits(line.frame.height()) && self.regions.may_progress() { + return Err(Stop::Finish(false)); + } + + // If the line's need, which includes its own height and that of + // following lines grouped by widow/orphan prevention, does not fit into + // the current region, but does fit into the next region, finish the + // region. + if !self.regions.size.y.fits(line.need) + && self + .regions + .iter() + .nth(1) + .is_some_and(|region| region.y.fits(line.need)) + { + return Err(Stop::Finish(false)); + } + + self.frame(line.frame.clone(), line.align, false, false) + } + + /// Processes an unbreakable block. + fn single(&mut self, single: &'b SingleChild<'a>) -> FlowResult<()> { + // Lay out the block. + let frame = single.layout( + self.composer.engine, + Region::new(self.regions.base(), self.regions.expand), + )?; + + // Handle fractionally sized blocks. + if let Some(fr) = single.fr { + self.composer.footnotes(&self.regions, &frame, Abs::zero(), false)?; + self.flush_tags(); + self.items.push(Item::Fr(fr, Some(single))); + return Ok(()); + } + + // If the block doesn't fit and a followup region may improve things, + // finish the region. + if !self.regions.size.y.fits(frame.height()) && self.regions.may_progress() { + return Err(Stop::Finish(false)); + } + + self.frame(frame, single.align, single.sticky, false) + } + + /// Processes a breakable block. + fn multi(&mut self, multi: &'b MultiChild<'a>) -> FlowResult<()> { + // Skip directly if the region is already (over)full. `line` and + // `single` implicitly do this through their `fits` checks. + if self.regions.is_full() { + return Err(Stop::Finish(false)); + } + + // Lay out the block. + let (frame, spill) = multi.layout(self.composer.engine, self.regions)?; + self.frame(frame, multi.align, multi.sticky, true)?; + + // If the block didn't fully fit into the current region, save it into + // the `spill` and finish the region. + if let Some(spill) = spill { + self.composer.work.spill = Some(spill); + self.composer.work.advance(); + return Err(Stop::Finish(false)); + } + + Ok(()) + } + + /// Processes spillover from a breakable block. + fn multi_spill(&mut self, spill: MultiSpill<'a, 'b>) -> FlowResult<()> { + // Skip directly if the region is already (over)full. + if self.regions.is_full() { + self.composer.work.spill = Some(spill); + return Err(Stop::Finish(false)); + } + + // Lay out the spilled remains. + let align = spill.align(); + let (frame, spill) = spill.layout(self.composer.engine, self.regions)?; + self.frame(frame, align, false, true)?; + + // If there's still more, save it into the `spill` and finish the + // region. + if let Some(spill) = spill { + self.composer.work.spill = Some(spill); + return Err(Stop::Finish(false)); + } + + Ok(()) + } + + /// Processes an in-flow frame, generated from a line or block. + fn frame( + &mut self, + frame: Frame, + align: Axes<FixedAlignment>, + sticky: bool, + breakable: bool, + ) -> FlowResult<()> { + if sticky { + // If the frame is sticky and we haven't remembered a preceding + // sticky element, make a checkpoint which we can restore should we + // end on this sticky element. + if self.stickable && self.sticky.is_none() { + self.sticky = Some(self.snapshot()); + } + } else if !frame.is_empty() { + // If the frame isn't sticky, we can forget a previous snapshot. + self.stickable = true; + self.sticky = None; + } + + // Handle footnotes. + self.composer + .footnotes(&self.regions, &frame, frame.height(), breakable)?; + + // Push an item for the frame. + self.regions.size.y -= frame.height(); + self.flush_tags(); + self.items.push(Item::Frame(frame, align)); + Ok(()) + } + + /// Processes an absolutely or floatingly placed child. + fn placed(&mut self, placed: &'b PlacedChild<'a>) -> FlowResult<()> { + if placed.float { + // If the element is floatingly placed, let the composer handle it. + // It might require relayout because the area available for + // distribution shrinks. We make the spacing occupied by weak + // spacing temporarily available again because it can collapse if it + // ends up at a break due to the float. + let weak_spacing = self.weak_spacing(); + self.regions.size.y += weak_spacing; + self.composer.float( + placed, + &self.regions, + self.items.iter().any(|item| matches!(item, Item::Frame(..))), + )?; + self.regions.size.y -= weak_spacing; + } else { + let frame = placed.layout(self.composer.engine, self.regions.base())?; + self.composer.footnotes(&self.regions, &frame, Abs::zero(), true)?; + self.flush_tags(); + self.items.push(Item::Placed(frame, placed)); + } + Ok(()) + } + + /// Processes a float flush. + fn flush(&mut self) -> FlowResult<()> { + // If there are still pending floats, finish the region instead of + // adding more content to it. + if !self.composer.work.floats.is_empty() { + return Err(Stop::Finish(false)); + } + Ok(()) + } + + /// Processes a column break. + fn break_(&mut self, weak: bool) -> FlowResult<()> { + // If there is a region to break into, break into it. + if (!weak || !self.items.is_empty()) + && (!self.regions.backlog.is_empty() || self.regions.last.is_some()) + { + self.composer.work.advance(); + return Err(Stop::Finish(true)); + } + Ok(()) + } + + /// Arranges the produced items into an output frame. + /// + /// This performs alignment and resolves fractional spacing and blocks. + fn finalize( + mut self, + region: Region, + init: DistributionSnapshot<'a, 'b>, + forced: bool, + ) -> FlowResult<Frame> { + if forced { + // If this is the very end of the flow, flush pending tags. + self.flush_tags(); + } else if !self.items.is_empty() && self.items.iter().all(Item::migratable) { + // Restore the initial state of all items are migratable. + self.restore(init); + } else { + // If we ended on a sticky block, but are not yet at the end of + // the flow, restore the saved checkpoint to move the sticky + // suffix to the next region. + if let Some(snapshot) = self.sticky.take() { + self.restore(snapshot) + } + } + + self.trim_spacing(); + + let mut frs = Fr::zero(); + let mut used = Size::zero(); + let mut has_fr_child = false; + + // Determine the amount of used space and the sum of fractionals. + for item in &self.items { + match item { + Item::Abs(v, _) => used.y += *v, + Item::Fr(v, child) => { + frs += *v; + has_fr_child |= child.is_some(); + } + Item::Frame(frame, _) => { + used.y += frame.height(); + used.x.set_max(frame.width()); + } + Item::Tag(_) | Item::Placed(..) => {} + } + } + + // When we have fractional spacing, occupy the remaining space with it. + let mut fr_space = Abs::zero(); + if frs.get() > 0.0 && region.size.y.is_finite() { + fr_space = region.size.y - used.y; + used.y = region.size.y; + } + + // Lay out fractionally sized blocks. + let mut fr_frames = vec![]; + if has_fr_child { + for item in &self.items { + let Item::Fr(v, Some(single)) = item else { continue }; + let length = v.share(frs, fr_space); + let pod = Region::new(Size::new(region.size.x, length), region.expand); + let frame = single.layout(self.composer.engine, pod)?; + used.x.set_max(frame.width()); + fr_frames.push(frame); + } + } + + // Also consider the width of insertions for alignment. + if !region.expand.x { + used.x.set_max(self.composer.insertion_width()); + } + + // Determine the region's size. + let size = region.expand.select(region.size, used.min(region.size)); + let free = size.y - used.y; + + let mut output = Frame::soft(size); + let mut ruler = FixedAlignment::Start; + let mut offset = Abs::zero(); + let mut fr_frames = fr_frames.into_iter(); + + // Position all items. + for item in self.items { + match item { + Item::Tag(tag) => { + let y = offset + ruler.position(free); + let pos = Point::with_y(y); + output.push(pos, FrameItem::Tag(tag.clone())); + } + Item::Abs(v, _) => { + offset += v; + } + Item::Fr(v, single) => { + let length = v.share(frs, fr_space); + if let Some(single) = single { + let frame = fr_frames.next().unwrap(); + let x = single.align.x.position(size.x - frame.width()); + let pos = Point::new(x, offset); + output.push_frame(pos, frame); + } + offset += length; + } + Item::Frame(frame, align) => { + ruler = ruler.max(align.y); + + let x = align.x.position(size.x - frame.width()); + let y = offset + ruler.position(free); + let pos = Point::new(x, y); + offset += frame.height(); + + output.push_frame(pos, frame); + } + Item::Placed(frame, placed) => { + let x = placed.align_x.position(size.x - frame.width()); + let y = match placed.align_y.unwrap_or_default() { + Some(align) => align.position(size.y - frame.height()), + _ => offset + ruler.position(free), + }; + + let pos = Point::new(x, y) + + placed.delta.zip_map(size, Rel::relative_to).to_point(); + + output.push_frame(pos, frame); + } + } + } + + Ok(output) + } + + /// Create a snapshot of the work and items. + fn snapshot(&self) -> DistributionSnapshot<'a, 'b> { + DistributionSnapshot { + work: self.composer.work.clone(), + items: self.items.len(), + } + } + + /// Restore a snapshot of the work and items. + fn restore(&mut self, snapshot: DistributionSnapshot<'a, 'b>) { + *self.composer.work = snapshot.work; + self.items.truncate(snapshot.items); + } +} diff --git a/crates/typst-layout/src/flow/mod.rs b/crates/typst-layout/src/flow/mod.rs new file mode 100644 index 00000000..7cbec59a --- /dev/null +++ b/crates/typst-layout/src/flow/mod.rs @@ -0,0 +1,381 @@ +//! Layout of content into a [`Frame`] or [`Fragment`]. + +mod block; +mod collect; +mod compose; +mod distribute; + +pub(crate) use self::block::unbreakable_pod; + +use std::collections::HashSet; +use std::num::NonZeroUsize; +use std::rc::Rc; + +use bumpalo::Bump; +use comemo::{Track, Tracked, TrackedMut}; +use ecow::EcoVec; +use typst_library::diag::{bail, At, SourceDiagnostic, SourceResult}; +use typst_library::engine::{Engine, Route, Sink, Traced}; +use typst_library::foundations::{Content, Packed, Resolve, StyleChain}; +use typst_library::introspection::{ + Introspector, Location, Locator, LocatorLink, SplitLocator, Tag, +}; +use typst_library::layout::{ + Abs, ColumnsElem, Dir, Em, Fragment, Frame, PageElem, PlacementScope, Region, + Regions, Rel, Size, +}; +use typst_library::model::{FootnoteElem, FootnoteEntry, LineNumberingScope, ParLine}; +use typst_library::routines::{Arenas, Pair, RealizationKind, Routines}; +use typst_library::text::TextElem; +use typst_library::World; +use typst_utils::{NonZeroExt, Numeric}; + +use self::block::{layout_multi_block, layout_single_block}; +use self::collect::{ + collect, Child, LineChild, MultiChild, MultiSpill, PlacedChild, SingleChild, +}; +use self::compose::{compose, Composer}; +use self::distribute::distribute; + +/// Lays out content into a single region, producing a single frame. +pub fn layout_frame( + engine: &mut Engine, + content: &Content, + locator: Locator, + styles: StyleChain, + region: Region, +) -> SourceResult<Frame> { + layout_fragment(engine, content, locator, styles, region.into()) + .map(Fragment::into_frame) +} + +/// Lays out content into multiple regions. +/// +/// When laying out into just one region, prefer [`layout_frame`]. +pub fn layout_fragment( + engine: &mut Engine, + content: &Content, + locator: Locator, + styles: StyleChain, + regions: Regions, +) -> SourceResult<Fragment> { + layout_fragment_impl( + engine.routines, + engine.world, + engine.introspector, + engine.traced, + TrackedMut::reborrow_mut(&mut engine.sink), + engine.route.track(), + content, + locator.track(), + styles, + regions, + NonZeroUsize::ONE, + Rel::zero(), + ) +} + +/// Layout the columns. +/// +/// This is different from just laying out into column-sized regions as the +/// columns can interact due to parent-scoped placed elements. +#[typst_macros::time(span = elem.span())] +pub fn layout_columns( + elem: &Packed<ColumnsElem>, + engine: &mut Engine, + locator: Locator, + styles: StyleChain, + regions: Regions, +) -> SourceResult<Fragment> { + layout_fragment_impl( + engine.routines, + engine.world, + engine.introspector, + engine.traced, + TrackedMut::reborrow_mut(&mut engine.sink), + engine.route.track(), + &elem.body, + locator.track(), + styles, + regions, + elem.count(styles), + elem.gutter(styles), + ) +} + +/// The cached, internal implementation of [`layout_fragment`]. +#[comemo::memoize] +#[allow(clippy::too_many_arguments)] +fn layout_fragment_impl( + routines: &Routines, + world: Tracked<dyn World + '_>, + introspector: Tracked<Introspector>, + traced: Tracked<Traced>, + sink: TrackedMut<Sink>, + route: Tracked<Route>, + content: &Content, + locator: Tracked<Locator>, + styles: StyleChain, + regions: Regions, + columns: NonZeroUsize, + column_gutter: Rel<Abs>, +) -> SourceResult<Fragment> { + if !regions.size.x.is_finite() && regions.expand.x { + bail!(content.span(), "cannot expand into infinite width"); + } + if !regions.size.y.is_finite() && regions.expand.y { + bail!(content.span(), "cannot expand into infinite height"); + } + + let link = LocatorLink::new(locator); + let mut locator = Locator::link(&link).split(); + let mut engine = Engine { + routines, + world, + introspector, + traced, + sink, + route: Route::extend(route), + }; + + engine.route.check_layout_depth().at(content.span())?; + + let arenas = Arenas::default(); + let children = (engine.routines.realize)( + RealizationKind::Container, + &mut engine, + &mut locator, + &arenas, + content, + styles, + )?; + + layout_flow( + &mut engine, + &children, + &mut locator, + styles, + regions, + columns, + column_gutter, + false, + ) +} + +/// Lays out realized content into regions, potentially with columns. +#[allow(clippy::too_many_arguments)] +pub(crate) fn layout_flow( + engine: &mut Engine, + children: &[Pair], + locator: &mut SplitLocator, + shared: StyleChain, + mut regions: Regions, + columns: NonZeroUsize, + column_gutter: Rel<Abs>, + root: bool, +) -> SourceResult<Fragment> { + // Prepare configuration that is shared across the whole flow. + let config = Config { + root, + shared, + columns: { + let mut count = columns.get(); + if !regions.size.x.is_finite() { + count = 1; + } + + let gutter = column_gutter.relative_to(regions.base().x); + let width = (regions.size.x - gutter * (count - 1) as f64) / count as f64; + let dir = TextElem::dir_in(shared); + ColumnConfig { count, width, gutter, dir } + }, + footnote: FootnoteConfig { + separator: FootnoteEntry::separator_in(shared), + clearance: FootnoteEntry::clearance_in(shared), + gap: FootnoteEntry::gap_in(shared), + expand: regions.expand.x, + }, + line_numbers: root.then(|| LineNumberConfig { + scope: ParLine::numbering_scope_in(shared), + default_clearance: { + let width = if PageElem::flipped_in(shared) { + PageElem::height_in(shared) + } else { + PageElem::width_in(shared) + }; + (0.026 * width.unwrap_or_default()) + .clamp(Em::new(0.75).resolve(shared), Em::new(2.5).resolve(shared)) + }, + }), + }; + + // Collect the elements into pre-processed children. These are much easier + // to handle than the raw elements. + let bump = Bump::new(); + let children = collect( + engine, + &bump, + children, + locator.next(&()), + Size::new(config.columns.width, regions.full), + regions.expand.x, + )?; + + let mut work = Work::new(&children); + let mut finished = vec![]; + + // This loop runs once per region produced by the flow layout. + loop { + let frame = compose(engine, &mut work, &config, locator.next(&()), regions)?; + finished.push(frame); + + // Terminate the loop when everything is processed, though draining the + // backlog if necessary. + if work.done() && (!regions.expand.y || regions.backlog.is_empty()) { + break; + } + + regions.next(); + } + + Ok(Fragment::frames(finished)) +} + +/// The work that is left to do by flow layout. +/// +/// The lifetimes 'a and 'b are used across flow layout: +/// - 'a is that of the content coming out of realization +/// - 'b is that of the collected/prepared children +#[derive(Clone)] +struct Work<'a, 'b> { + /// Children that we haven't processed yet. This slice shrinks over time. + children: &'b [Child<'a>], + /// Leftovers from a breakable block. + spill: Option<MultiSpill<'a, 'b>>, + /// Queued floats that didn't fit in previous regions. + floats: EcoVec<&'b PlacedChild<'a>>, + /// Queued footnotes that didn't fit in previous regions. + footnotes: EcoVec<Packed<FootnoteElem>>, + /// Spilled frames of a footnote that didn't fully fit. Similar to `spill`. + footnote_spill: Option<std::vec::IntoIter<Frame>>, + /// Queued tags that will be attached to the next frame. + tags: EcoVec<&'a Tag>, + /// Identifies floats and footnotes that can be skipped if visited because + /// they were already handled and incorporated as column or page level + /// insertions. + skips: Rc<HashSet<Location>>, +} + +impl<'a, 'b> Work<'a, 'b> { + /// Create the initial work state from a list of children. + fn new(children: &'b [Child<'a>]) -> Self { + Self { + children, + spill: None, + floats: EcoVec::new(), + footnotes: EcoVec::new(), + footnote_spill: None, + tags: EcoVec::new(), + skips: Rc::new(HashSet::new()), + } + } + + /// Get the first unprocessed child, from the start of the slice. + fn head(&self) -> Option<&'b Child<'a>> { + self.children.first() + } + + /// Mark the `head()` child as processed, advancing the slice by one. + fn advance(&mut self) { + self.children = &self.children[1..]; + } + + /// Whether all work is done. This means we can terminate flow layout. + fn done(&self) -> bool { + self.children.is_empty() + && self.spill.is_none() + && self.floats.is_empty() + && self.footnote_spill.is_none() + && self.footnotes.is_empty() + } + + /// Add skipped floats and footnotes from the insertion areas to the skip + /// set. + fn extend_skips(&mut self, skips: &[Location]) { + if !skips.is_empty() { + Rc::make_mut(&mut self.skips).extend(skips.iter().copied()); + } + } +} + +/// Shared configuration for the whole flow. +struct Config<'x> { + /// Whether this is the root flow, which can host footnotes and line + /// numbers. + root: bool, + /// The styles shared by the whole flow. This is used for footnotes and line + /// numbers. + shared: StyleChain<'x>, + /// Settings for columns. + columns: ColumnConfig, + /// Settings for footnotes. + footnote: FootnoteConfig, + /// Settings for line numbers. + line_numbers: Option<LineNumberConfig>, +} + +/// Configuration of footnotes. +struct FootnoteConfig { + /// The separator between flow content and footnotes. Typically a line. + separator: Content, + /// The amount of space left above the separator. + clearance: Abs, + /// The gap between footnote entries. + gap: Abs, + /// Whether horizontal expansion is enabled for footnotes. + expand: bool, +} + +/// Configuration of columns. +struct ColumnConfig { + /// The number of columns. + count: usize, + /// The width of each column. + width: Abs, + /// The amount of space between columns. + gutter: Abs, + /// The horizontal direction in which columns progress. Defined by + /// `text.dir`. + dir: Dir, +} + +/// Configuration of line numbers. +struct LineNumberConfig { + /// Where line numbers are reset. + scope: LineNumberingScope, + /// The default clearance for `auto`. + default_clearance: Abs, +} + +/// The result type for flow layout. +/// +/// The `Err(_)` variant incorporate control flow events for finishing and +/// relayouting regions. +type FlowResult<T> = Result<T, Stop>; + +/// A control flow event during flow layout. +enum Stop { + /// Indicates that the current subregion should be finished. Can be caused + /// by a lack of space (`false`) or an explicit column break (`true`). + Finish(bool), + /// Indicates that the given scope should be relayouted. + Relayout(PlacementScope), + /// A fatal error. + Error(EcoVec<SourceDiagnostic>), +} + +impl From<EcoVec<SourceDiagnostic>> for Stop { + fn from(error: EcoVec<SourceDiagnostic>) -> Self { + Stop::Error(error) + } +} |