Split out four new crates (#5302)

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, &regions, 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)
+    }
+}