diff options
Diffstat (limited to 'crates/typst-library/src/layout/flow.rs')
| -rw-r--r-- | crates/typst-library/src/layout/flow.rs | 583 |
1 files changed, 583 insertions, 0 deletions
diff --git a/crates/typst-library/src/layout/flow.rs b/crates/typst-library/src/layout/flow.rs new file mode 100644 index 00000000..accd092a --- /dev/null +++ b/crates/typst-library/src/layout/flow.rs @@ -0,0 +1,583 @@ +use std::mem; + +use super::{ + AlignElem, BlockElem, ColbreakElem, ColumnsElem, ParElem, PlaceElem, Spacing, VElem, +}; +use crate::meta::{FootnoteElem, FootnoteEntry}; +use crate::prelude::*; +use crate::visualize::{ + CircleElem, EllipseElem, ImageElem, LineElem, PathElem, PolygonElem, RectElem, + SquareElem, +}; + +/// Arranges spacing, paragraphs and block-level elements into a flow. +/// +/// This element is responsible for layouting both the top-level content flow +/// and the contents of boxes. +/// +/// Display: Flow +/// Category: layout +#[element(Layout)] +pub struct FlowElem { + /// The children that will be arranges into a flow. + #[variadic] + pub children: Vec<Content>, +} + +impl Layout for FlowElem { + #[tracing::instrument(name = "FlowElem::layout", skip_all)] + fn layout( + &self, + vt: &mut Vt, + styles: StyleChain, + regions: Regions, + ) -> SourceResult<Fragment> { + let mut layouter = FlowLayouter::new(regions, styles); + + for mut child in &self.children() { + let outer = styles; + let mut styles = styles; + if let Some((elem, map)) = child.to_styled() { + child = elem; + styles = outer.chain(map); + } + + if let Some(elem) = child.to::<VElem>() { + layouter.layout_spacing(vt, elem, styles)?; + } else if let Some(elem) = child.to::<ParElem>() { + layouter.layout_par(vt, elem, styles)?; + } else if child.is::<LineElem>() + || child.is::<RectElem>() + || child.is::<SquareElem>() + || child.is::<EllipseElem>() + || child.is::<CircleElem>() + || child.is::<ImageElem>() + || child.is::<PolygonElem>() + || child.is::<PathElem>() + { + let layoutable = child.with::<dyn Layout>().unwrap(); + layouter.layout_single(vt, layoutable, styles)?; + } else if child.is::<MetaElem>() { + let mut frame = Frame::new(Size::zero()); + frame.meta(styles, true); + layouter.items.push(FlowItem::Frame { + frame, + aligns: Axes::new(Align::Top, Align::Left), + sticky: true, + movable: false, + }); + } else if child.can::<dyn Layout>() { + layouter.layout_multiple(vt, child, styles)?; + } else if child.is::<ColbreakElem>() { + if !layouter.regions.backlog.is_empty() || layouter.regions.last.is_some() + { + layouter.finish_region()?; + } + } else { + bail!(child.span(), "unexpected flow child"); + } + } + + layouter.finish() + } +} + +/// Performs flow layout. +struct FlowLayouter<'a> { + /// Whether this is the root flow. + root: bool, + /// The regions to layout children into. + regions: Regions<'a>, + /// The shared styles. + styles: StyleChain<'a>, + /// Whether the flow should expand to fill the region. + expand: Axes<bool>, + /// The initial size of `regions.size` that was available before we started + /// subtracting. + initial: Size, + /// Whether the last block was a paragraph. + last_was_par: bool, + /// Spacing and layouted blocks for the current region. + items: Vec<FlowItem>, + /// Whether we have any footnotes in the current region. + has_footnotes: bool, + /// Footnote configuration. + footnote_config: FootnoteConfig, + /// Finished frames for previous regions. + finished: Vec<Frame>, +} + +/// Cached footnote configuration. +struct FootnoteConfig { + separator: Content, + clearance: Abs, + gap: Abs, +} + +/// A prepared item in a flow layout. +#[derive(Debug)] +enum FlowItem { + /// Spacing between other items and whether it is weak. + Absolute(Abs, bool), + /// Fractional spacing between other items. + Fractional(Fr), + /// A frame for a layouted block, how to align it, whether it sticks to the + /// item after it (for orphan prevention), and whether it is movable + /// (to keep it together with its footnotes). + Frame { frame: Frame, aligns: Axes<Align>, sticky: bool, movable: bool }, + /// An absolutely placed frame. + Placed(Frame), + /// A footnote frame (can also be the separator). + Footnote(Frame), +} + +impl FlowItem { + /// The inherent height of the item. + fn height(&self) -> Abs { + match self { + Self::Absolute(v, _) => *v, + Self::Fractional(_) | Self::Placed(_) => Abs::zero(), + Self::Frame { frame, .. } | Self::Footnote(frame) => frame.height(), + } + } +} + +impl<'a> FlowLayouter<'a> { + /// Create a new flow layouter. + fn new(mut regions: Regions<'a>, styles: StyleChain<'a>) -> Self { + let expand = regions.expand; + + // Disable vertical expansion & root for children. + regions.expand.y = false; + let root = mem::replace(&mut regions.root, false); + + Self { + root, + regions, + styles, + expand, + initial: regions.size, + last_was_par: false, + items: vec![], + has_footnotes: false, + footnote_config: FootnoteConfig { + separator: FootnoteEntry::separator_in(styles), + clearance: FootnoteEntry::clearance_in(styles), + gap: FootnoteEntry::gap_in(styles), + }, + finished: vec![], + } + } + + /// Layout vertical spacing. + #[tracing::instrument(name = "FlowLayouter::layout_spacing", skip_all)] + fn layout_spacing( + &mut self, + vt: &mut Vt, + v: &VElem, + styles: StyleChain, + ) -> SourceResult<()> { + self.layout_item( + vt, + match v.amount() { + Spacing::Rel(rel) => FlowItem::Absolute( + rel.resolve(styles).relative_to(self.initial.y), + v.weakness(styles) > 0, + ), + Spacing::Fr(fr) => FlowItem::Fractional(fr), + }, + ) + } + + /// Layout a paragraph. + #[tracing::instrument(name = "FlowLayouter::layout_par", skip_all)] + fn layout_par( + &mut self, + vt: &mut Vt, + par: &ParElem, + styles: StyleChain, + ) -> SourceResult<()> { + let aligns = AlignElem::alignment_in(styles).resolve(styles); + let leading = ParElem::leading_in(styles); + let consecutive = self.last_was_par; + let lines = par + .layout(vt, styles, consecutive, self.regions.base(), self.regions.expand.x)? + .into_frames(); + + let mut sticky = self.items.len(); + for (i, item) in self.items.iter().enumerate().rev() { + match *item { + FlowItem::Absolute(_, _) => {} + FlowItem::Frame { sticky: true, .. } => sticky = i, + _ => break, + } + } + + if let Some(first) = lines.first() { + if !self.regions.size.y.fits(first.height()) && !self.regions.in_last() { + let carry: Vec<_> = self.items.drain(sticky..).collect(); + self.finish_region()?; + for item in carry { + self.layout_item(vt, item)?; + } + } + } + + for (i, frame) in lines.into_iter().enumerate() { + if i > 0 { + self.layout_item(vt, FlowItem::Absolute(leading, true))?; + } + + self.layout_item( + vt, + FlowItem::Frame { frame, aligns, sticky: false, movable: true }, + )?; + } + + self.last_was_par = true; + Ok(()) + } + + /// Layout into a single region. + #[tracing::instrument(name = "FlowLayouter::layout_single", skip_all)] + fn layout_single( + &mut self, + vt: &mut Vt, + content: &dyn Layout, + styles: StyleChain, + ) -> SourceResult<()> { + let aligns = AlignElem::alignment_in(styles).resolve(styles); + let sticky = BlockElem::sticky_in(styles); + let pod = Regions::one(self.regions.base(), Axes::splat(false)); + let frame = content.layout(vt, styles, pod)?.into_frame(); + self.layout_item(vt, FlowItem::Frame { frame, aligns, sticky, movable: true })?; + self.last_was_par = false; + Ok(()) + } + + /// Layout into multiple regions. + fn layout_multiple( + &mut self, + vt: &mut Vt, + block: &Content, + styles: StyleChain, + ) -> SourceResult<()> { + // Placed elements that are out of flow produce placed items which + // aren't aligned later. + if let Some(placed) = block.to::<PlaceElem>() { + if placed.out_of_flow(styles) { + let frame = block.layout(vt, styles, self.regions)?.into_frame(); + self.layout_item(vt, FlowItem::Placed(frame))?; + return Ok(()); + } + } else if self.regions.is_full() { + // Skip directly if region is already full. + self.finish_region()?; + } + + // How to align the block. + let aligns = if let Some(align) = block.to::<AlignElem>() { + align.alignment(styles) + } else if let Some((_, local)) = block.to_styled() { + AlignElem::alignment_in(styles.chain(local)) + } else { + AlignElem::alignment_in(styles) + } + .resolve(styles); + + // Temporarily delegerate rootness to the columns. + let is_root = self.root; + if is_root && block.is::<ColumnsElem>() { + self.root = false; + self.regions.root = true; + } + + // Layout the block itself. + let sticky = BlockElem::sticky_in(styles); + let fragment = block.layout(vt, styles, self.regions)?; + let mut notes = Vec::new(); + + for (i, frame) in fragment.into_iter().enumerate() { + // Find footnotes in the frame. + if self.root { + find_footnotes(&mut notes, &frame); + } + + if i > 0 { + self.finish_region()?; + } + + self.layout_item( + vt, + FlowItem::Frame { frame, aligns, sticky, movable: false }, + )?; + } + + if self.root && !self.handle_footnotes(vt, &mut notes, false, false)? { + self.finish_region()?; + self.handle_footnotes(vt, &mut notes, false, true)?; + } + + self.root = is_root; + self.regions.root = false; + self.last_was_par = false; + + Ok(()) + } + + /// Layout a finished frame. + #[tracing::instrument(name = "FlowLayouter::layout_item", skip_all)] + fn layout_item(&mut self, vt: &mut Vt, item: FlowItem) -> SourceResult<()> { + match item { + FlowItem::Absolute(v, weak) => { + if weak + && !self + .items + .iter() + .any(|item| matches!(item, FlowItem::Frame { .. })) + { + return Ok(()); + } + self.regions.size.y -= v + } + FlowItem::Fractional(_) => {} + FlowItem::Frame { ref frame, movable, .. } => { + let size = frame.size(); + if !self.regions.size.y.fits(size.y) && !self.regions.in_last() { + self.finish_region()?; + } + + self.regions.size.y -= size.y; + if self.root && movable { + let mut notes = Vec::new(); + find_footnotes(&mut notes, frame); + self.items.push(item); + if !self.handle_footnotes(vt, &mut notes, true, false)? { + let item = self.items.pop(); + self.finish_region()?; + self.items.extend(item); + self.regions.size.y -= size.y; + self.handle_footnotes(vt, &mut notes, true, true)?; + } + return Ok(()); + } + } + FlowItem::Placed(_) => {} + FlowItem::Footnote(_) => {} + } + + self.items.push(item); + Ok(()) + } + + /// Finish the frame for one region. + fn finish_region(&mut self) -> SourceResult<()> { + // Trim weak spacing. + while self + .items + .last() + .map_or(false, |item| matches!(item, FlowItem::Absolute(_, true))) + { + self.items.pop(); + } + + // Determine the used size. + let mut fr = Fr::zero(); + let mut used = Size::zero(); + let mut footnote_height = Abs::zero(); + let mut first_footnote = true; + for item in &self.items { + match item { + FlowItem::Absolute(v, _) => used.y += *v, + FlowItem::Fractional(v) => fr += *v, + FlowItem::Frame { frame, .. } => { + let size = frame.size(); + used.y += size.y; + used.x.set_max(size.x); + } + FlowItem::Placed(_) => {} + FlowItem::Footnote(frame) => { + let size = frame.size(); + footnote_height += size.y; + if !first_footnote { + footnote_height += self.footnote_config.gap; + } + first_footnote = false; + used.x.set_max(size.x); + } + } + } + used.y += footnote_height; + + // Determine the size of the flow in this region depending on whether + // the region expands. Also account for fractional spacing and + // footnotes. + let mut size = self.expand.select(self.initial, used).min(self.initial); + if (fr.get() > 0.0 || self.has_footnotes) && self.initial.y.is_finite() { + size.y = self.initial.y; + } + + let mut output = Frame::new(size); + let mut offset = Abs::zero(); + let mut ruler = Align::Top; + let mut footnote_offset = size.y - footnote_height; + + // Place all frames. + for item in self.items.drain(..) { + match item { + FlowItem::Absolute(v, _) => { + offset += v; + } + FlowItem::Fractional(v) => { + let remaining = self.initial.y - used.y; + offset += v.share(fr, remaining); + } + FlowItem::Frame { frame, aligns, .. } => { + ruler = ruler.max(aligns.y); + let x = aligns.x.position(size.x - frame.width()); + let y = offset + ruler.position(size.y - used.y); + let pos = Point::new(x, y); + offset += frame.height(); + output.push_frame(pos, frame); + } + FlowItem::Footnote(frame) => { + let pos = Point::with_y(footnote_offset); + footnote_offset += frame.height() + self.footnote_config.gap; + output.push_frame(pos, frame); + } + FlowItem::Placed(frame) => { + output.push_frame(Point::zero(), frame); + } + } + } + + // Advance to the next region. + self.finished.push(output); + self.regions.next(); + self.initial = self.regions.size; + self.has_footnotes = false; + Ok(()) + } + + /// Finish layouting and return the resulting fragment. + fn finish(mut self) -> SourceResult<Fragment> { + if self.expand.y { + while !self.regions.backlog.is_empty() { + self.finish_region()?; + } + } + + self.finish_region()?; + Ok(Fragment::frames(self.finished)) + } +} + +impl FlowLayouter<'_> { + /// Processes all footnotes in the frame. + #[tracing::instrument(skip_all)] + fn handle_footnotes( + &mut self, + vt: &mut Vt, + notes: &mut Vec<FootnoteElem>, + movable: bool, + force: bool, + ) -> SourceResult<bool> { + let items_len = self.items.len(); + let notes_len = notes.len(); + + // Process footnotes one at a time. + let mut k = 0; + while k < notes.len() { + if notes[k].is_ref() { + k += 1; + continue; + } + + if !self.has_footnotes { + self.layout_footnote_separator(vt)?; + } + + self.regions.size.y -= self.footnote_config.gap; + let frames = FootnoteEntry::new(notes[k].clone()) + .pack() + .layout(vt, self.styles, self.regions.with_root(false))? + .into_frames(); + + // If the entries didn't fit, abort (to keep footnote and entry + // together). + if !force + && (k == 0 || movable) + && frames.first().map_or(false, Frame::is_empty) + { + // Remove existing footnotes attempts because we need to + // move the item to the next page. + notes.truncate(notes_len); + + // Undo region modifications. + for item in self.items.drain(items_len..) { + self.regions.size.y -= item.height(); + } + + return Ok(false); + } + + let prev = notes.len(); + for (i, frame) in frames.into_iter().enumerate() { + find_footnotes(notes, &frame); + if i > 0 { + self.finish_region()?; + self.layout_footnote_separator(vt)?; + self.regions.size.y -= self.footnote_config.gap; + } + self.regions.size.y -= frame.height(); + self.items.push(FlowItem::Footnote(frame)); + } + + k += 1; + + // Process the nested notes before dealing with further top-level + // notes. + let nested = notes.len() - prev; + if nested > 0 { + notes[k..].rotate_right(nested); + } + } + + Ok(true) + } + + /// Layout and save the footnote separator, typically a line. + #[tracing::instrument(skip_all)] + fn layout_footnote_separator(&mut self, vt: &mut Vt) -> SourceResult<()> { + let expand = Axes::new(self.regions.expand.x, false); + let pod = Regions::one(self.regions.base(), expand); + let separator = &self.footnote_config.separator; + + let mut frame = separator.layout(vt, self.styles, pod)?.into_frame(); + frame.size_mut().y += self.footnote_config.clearance; + frame.translate(Point::with_y(self.footnote_config.clearance)); + + self.has_footnotes = true; + self.regions.size.y -= frame.height(); + self.items.push(FlowItem::Footnote(frame)); + + Ok(()) + } +} + +/// Finds all footnotes in the frame. +#[tracing::instrument(skip_all)] +fn find_footnotes(notes: &mut Vec<FootnoteElem>, frame: &Frame) { + for (_, item) in frame.items() { + match item { + FrameItem::Group(group) => find_footnotes(notes, &group.frame), + FrameItem::Meta(Meta::Elem(content), _) + if !notes.iter().any(|note| note.0.location() == content.location()) => + { + let Some(footnote) = content.to::<FootnoteElem>() else { continue }; + notes.push(footnote.clone()); + } + _ => {} + } + } +} |