Introduce page / block / inline levels

13 files changed, 433 insertions, 449 deletions

diff --git a/src/layout/constraints.rs b/src/layout/constraints.rs
index f88b2add..7dc16446 100644
--- a/src/layout/constraints.rs
+++ b/src/layout/constraints.rs
@@ -7,7 +7,7 @@ pub struct Constrained<T> {
     /// The item that is only valid if the constraints are fullfilled.
     pub item: T,
     /// Constraints on regions in which the item is valid.
-    pub constraints: Constraints,
+    pub cts: Constraints,
 }
 
 /// Describe regions that match them.
diff --git a/src/layout/frame.rs b/src/layout/frame.rs
index 0e986fe4..82f60e22 100644
--- a/src/layout/frame.rs
+++ b/src/layout/frame.rs
@@ -19,69 +19,6 @@ pub struct Frame {
     pub children: Vec<(Point, FrameChild)>,
 }
 
-/// A frame can contain two different kinds of children: a leaf element or a
-/// nested frame.
-#[derive(Clone, Eq, PartialEq, Serialize, Deserialize)]
-pub enum FrameChild {
-    /// A leaf node in the frame tree.
-    Element(Element),
-    /// An interior group.
-    Group(Rc<Frame>),
-}
-
-/// The building block frames are composed of.
-#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
-pub enum Element {
-    /// Shaped text.
-    Text(Text),
-    /// A geometric shape and the paint which with it should be filled or
-    /// stroked (which one depends on the kind of geometry).
-    Geometry(Geometry, Paint),
-    /// A raster image.
-    Image(ImageId, Size),
-    /// A link to an external resource.
-    Link(String, Size),
-}
-
-/// A run of shaped text.
-#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
-pub struct Text {
-    /// The font face the glyphs are contained in.
-    pub face_id: FaceId,
-    /// The font size.
-    pub size: Length,
-    /// The width of the text run.
-    pub width: Length,
-    /// Glyph color.
-    pub fill: Paint,
-    /// The glyphs.
-    pub glyphs: Vec<Glyph>,
-}
-
-/// A glyph in a run of shaped text.
-#[derive(Debug, Copy, Clone, Eq, PartialEq, Serialize, Deserialize)]
-pub struct Glyph {
-    /// The glyph's index in the face.
-    pub id: u16,
-    /// The advance width of the glyph.
-    pub x_advance: Em,
-    /// The horizontal offset of the glyph.
-    pub x_offset: Em,
-}
-
-/// A geometric shape.
-#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
-pub enum Geometry {
-    /// A filled rectangle with its origin in the topleft corner.
-    Rect(Size),
-    /// A filled ellipse with its origin in the center.
-    Ellipse(Size),
-    /// A stroked line to a point (relative to its position) with a thickness.
-    Line(Point, Length),
-    /// A filled bezier path.
-    Path(Path),
-}
-
 impl Frame {
     /// Create a new, empty frame.
     #[track_caller]
@@ -117,15 +54,52 @@ impl Frame {
         }
     }
 
-    /// Wrap the frame with constraints.
-    pub fn constrain(self, constraints: Constraints) -> Constrained<Rc<Self>> {
-        Constrained { item: Rc::new(self), constraints }
-    }
-
     /// An iterator over all elements in the frame and its children.
     pub fn elements(&self) -> Elements {
         Elements { stack: vec![(0, Point::zero(), self)] }
     }
+
+    /// Wrap the frame with constraints.
+    pub fn constrain(self, cts: Constraints) -> Constrained<Rc<Self>> {
+        Constrained { item: Rc::new(self), cts }
+    }
+}
+
+impl Debug for Frame {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        struct Children<'a>(&'a [(Point, FrameChild)]);
+
+        impl Debug for Children<'_> {
+            fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+                f.debug_map().entries(self.0.iter().map(|(k, v)| (k, v))).finish()
+            }
+        }
+
+        f.debug_struct("Frame")
+            .field("size", &self.size)
+            .field("baseline", &self.baseline)
+            .field("children", &Children(&self.children))
+            .finish()
+    }
+}
+
+/// A frame can contain two different kinds of children: a leaf element or a
+/// nested frame.
+#[derive(Clone, Eq, PartialEq, Serialize, Deserialize)]
+pub enum FrameChild {
+    /// A leaf node in the frame tree.
+    Element(Element),
+    /// An interior group.
+    Group(Rc<Frame>),
+}
+
+impl Debug for FrameChild {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        match self {
+            Self::Element(element) => element.fmt(f),
+            Self::Group(frame) => frame.fmt(f),
+        }
+    }
 }
 
 /// An iterator over all elements in a frame, alongside with their positions.
@@ -159,29 +133,55 @@ impl<'a> Iterator for Elements<'a> {
     }
 }
 
-impl Debug for Frame {
-    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        struct Children<'a>(&'a [(Point, FrameChild)]);
+/// The building block frames are composed of.
+#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
+pub enum Element {
+    /// Shaped text.
+    Text(Text),
+    /// A geometric shape and the paint which with it should be filled or
+    /// stroked (which one depends on the kind of geometry).
+    Geometry(Geometry, Paint),
+    /// A raster image.
+    Image(ImageId, Size),
+    /// A link to an external resource.
+    Link(String, Size),
+}
 
-        impl Debug for Children<'_> {
-            fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-                f.debug_map().entries(self.0.iter().map(|(k, v)| (k, v))).finish()
-            }
-        }
+/// A run of shaped text.
+#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
+pub struct Text {
+    /// The font face the glyphs are contained in.
+    pub face_id: FaceId,
+    /// The font size.
+    pub size: Length,
+    /// The width of the text run.
+    pub width: Length,
+    /// Glyph color.
+    pub fill: Paint,
+    /// The glyphs.
+    pub glyphs: Vec<Glyph>,
+}
 
-        f.debug_struct("Frame")
-            .field("size", &self.size)
-            .field("baseline", &self.baseline)
-            .field("children", &Children(&self.children))
-            .finish()
-    }
+/// A glyph in a run of shaped text.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Serialize, Deserialize)]
+pub struct Glyph {
+    /// The glyph's index in the face.
+    pub id: u16,
+    /// The advance width of the glyph.
+    pub x_advance: Em,
+    /// The horizontal offset of the glyph.
+    pub x_offset: Em,
 }
 
-impl Debug for FrameChild {
-    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        match self {
-            Self::Element(element) => element.fmt(f),
-            Self::Group(frame) => frame.fmt(f),
-        }
-    }
+/// A geometric shape.
+#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
+pub enum Geometry {
+    /// A filled rectangle with its origin in the topleft corner.
+    Rect(Size),
+    /// A filled ellipse with its origin in the center.
+    Ellipse(Size),
+    /// A stroked line to a point (relative to its position) with a thickness.
+    Line(Point, Length),
+    /// A filled bezier path.
+    Path(Path),
 }
diff --git a/src/layout/grid.rs b/src/layout/grid.rs
index 2553fc2f..22581696 100644
--- a/src/layout/grid.rs
+++ b/src/layout/grid.rs
@@ -9,7 +9,7 @@ pub struct GridNode {
     /// Defines sizing of gutter rows and columns between content.
     pub gutter: Spec<Vec<TrackSizing>>,
     /// The nodes to be arranged in a grid.
-    pub children: Vec<LayoutNode>,
+    pub children: Vec<BlockNode>,
 }
 
 /// Defines how to size a grid cell along an axis.
@@ -23,7 +23,7 @@ pub enum TrackSizing {
     Fractional(Fractional),
 }
 
-impl Layout for GridNode {
+impl BlockLevel for GridNode {
     fn layout(
         &self,
         ctx: &mut LayoutContext,
@@ -40,9 +40,9 @@ impl Layout for GridNode {
     }
 }
 
-impl From<GridNode> for LayoutNode {
-    fn from(grid: GridNode) -> Self {
-        Self::new(grid)
+impl From<GridNode> for BlockNode {
+    fn from(node: GridNode) -> Self {
+        Self::new(node)
     }
 }
 
@@ -55,7 +55,7 @@ struct GridLayouter<'a> {
     /// The row tracks including gutter tracks.
     rows: Vec<TrackSizing>,
     /// The children of the grid.
-    children: &'a [LayoutNode],
+    children: &'a [BlockNode],
     /// The regions to layout into.
     regions: Regions,
     /// Resolved column sizes.
@@ -546,7 +546,7 @@ impl<'a> GridLayouter<'a> {
     ///
     /// Returns `None` if it's a gutter cell.
     #[track_caller]
-    fn cell(&self, x: usize, y: usize) -> Option<&'a LayoutNode> {
+    fn cell(&self, x: usize, y: usize) -> Option<&'a BlockNode> {
         assert!(x < self.cols.len());
         assert!(y < self.rows.len());
 
diff --git a/src/layout/image.rs b/src/layout/image.rs
index eb2fc221..59b4c6ef 100644
--- a/src/layout/image.rs
+++ b/src/layout/image.rs
@@ -13,31 +13,23 @@ pub struct ImageNode {
     pub height: Option<Linear>,
 }
 
-impl Layout for ImageNode {
-    fn layout(
-        &self,
-        ctx: &mut LayoutContext,
-        regions: &Regions,
-    ) -> Vec<Constrained<Rc<Frame>>> {
+impl InlineLevel for ImageNode {
+    fn layout(&self, ctx: &mut LayoutContext, space: Length, base: Size) -> Frame {
         let img = ctx.images.get(self.id);
         let pixel_size = Spec::new(img.width() as f64, img.height() as f64);
         let pixel_ratio = pixel_size.x / pixel_size.y;
 
-        let width = self.width.map(|w| w.resolve(regions.base.w));
-        let height = self.height.map(|w| w.resolve(regions.base.h));
-
-        let mut cts = Constraints::new(regions.expand);
-        cts.set_base_if_linear(regions.base, Spec::new(self.width, self.height));
+        let width = self.width.map(|w| w.resolve(base.w));
+        let height = self.height.map(|w| w.resolve(base.h));
 
         let size = match (width, height) {
             (Some(width), Some(height)) => Size::new(width, height),
             (Some(width), None) => Size::new(width, width / pixel_ratio),
             (None, Some(height)) => Size::new(height * pixel_ratio, height),
             (None, None) => {
-                cts.exact.x = Some(regions.current.w);
-                if regions.current.w.is_finite() {
+                if space.is_finite() {
                     // Fit to width.
-                    Size::new(regions.current.w, regions.current.w / pixel_ratio)
+                    Size::new(space, space / pixel_ratio)
                 } else {
                     // Unbounded width, we have to make up something,
                     // so it is 1pt per pixel.
@@ -48,12 +40,12 @@ impl Layout for ImageNode {
 
         let mut frame = Frame::new(size, size.h);
         frame.push(Point::zero(), Element::Image(self.id, size));
-        vec![frame.constrain(cts)]
+        frame
     }
 }
 
-impl From<ImageNode> for LayoutNode {
-    fn from(image: ImageNode) -> Self {
-        Self::new(image)
+impl From<ImageNode> for InlineNode {
+    fn from(node: ImageNode) -> Self {
+        Self::new(node)
     }
 }
diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs
index 19a41a22..2f6dccd0 100644
--- a/src/layout/incremental.rs
+++ b/src/layout/incremental.rs
@@ -230,7 +230,7 @@ impl FramesEntry {
         let mut iter = regions.iter();
         self.frames.iter().all(|frame| {
             iter.next().map_or(false, |(current, base)| {
-                frame.constraints.check(current, base, regions.expand)
+                frame.cts.check(current, base, regions.expand)
             })
         })
     }
@@ -400,7 +400,7 @@ mod tests {
     fn empty_frames() -> Vec<Constrained<Rc<Frame>>> {
         vec![Constrained {
             item: Rc::new(Frame::default()),
-            constraints: Constraints::new(Spec::splat(false)),
+            cts: Constraints::new(Spec::splat(false)),
         }]
     }
 
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index ee74ff6f..5c5e2ffd 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -10,10 +10,8 @@ mod pad;
 mod par;
 mod regions;
 mod shape;
-mod shaping;
-mod spacing;
 mod stack;
-mod tree;
+mod text;
 
 pub use self::image::*;
 pub use constraints::*;
@@ -25,12 +23,10 @@ pub use pad::*;
 pub use par::*;
 pub use regions::*;
 pub use shape::*;
-pub use shaping::*;
-pub use spacing::*;
 pub use stack::*;
-pub use tree::*;
+pub use text::*;
 
-use std::fmt::Debug;
+use std::fmt::{self, Debug, Formatter};
 use std::rc::Rc;
 
 use crate::font::FontStore;
@@ -39,10 +35,20 @@ use crate::image::ImageStore;
 use crate::util::OptionExt;
 use crate::Context;
 
-/// Layout a tree into a collection of frames.
-pub fn layout(ctx: &mut Context, tree: &LayoutTree) -> Vec<Rc<Frame>> {
+#[cfg(feature = "layout-cache")]
+use {
+    fxhash::FxHasher64,
+    std::any::Any,
+    std::hash::{Hash, Hasher},
+};
+
+/// Layout a page-level node into a collection of frames.
+pub fn layout<T>(ctx: &mut Context, node: &T) -> Vec<Rc<Frame>>
+where
+    T: PageLevel + ?Sized,
+{
     let mut ctx = LayoutContext::new(ctx);
-    tree.layout(&mut ctx)
+    node.layout(&mut ctx)
 }
 
 /// The context for layouting.
@@ -73,12 +79,198 @@ impl<'a> LayoutContext<'a> {
     }
 }
 
-/// Layout a node.
-pub trait Layout: Debug {
-    /// Layout the node into the given regions.
+/// Page-level nodes directly produce frames representing pages.
+///
+/// Such nodes create their own regions instead of being supplied with them from
+/// some parent.
+pub trait PageLevel: Debug {
+    /// Layout the node, producing one frame per page.
+    fn layout(&self, ctx: &mut LayoutContext) -> Vec<Rc<Frame>>;
+}
+
+/// Layouts its children onto one or multiple pages.
+#[derive(Debug)]
+pub struct PageNode {
+    /// The size of the page.
+    pub size: Size,
+    /// The node that produces the actual pages.
+    pub child: BlockNode,
+}
+
+impl PageLevel for PageNode {
+    fn layout(&self, ctx: &mut LayoutContext) -> Vec<Rc<Frame>> {
+        // When one of the lengths is infinite the page fits its content along
+        // that axis.
+        let expand = self.size.to_spec().map(Length::is_finite);
+        let regions = Regions::repeat(self.size, self.size, expand);
+        self.child.layout(ctx, &regions).into_iter().map(|c| c.item).collect()
+    }
+}
+
+impl<T> PageLevel for T
+where
+    T: AsRef<[PageNode]> + Debug + ?Sized,
+{
+    fn layout(&self, ctx: &mut LayoutContext) -> Vec<Rc<Frame>> {
+        self.as_ref().iter().flat_map(|node| node.layout(ctx)).collect()
+    }
+}
+
+/// Block-level nodes can be layouted into a sequence of regions.
+///
+/// They return one frame per used region alongside constraints that define
+/// whether the result is reusable in other regions.
+pub trait BlockLevel: Debug {
+    /// Layout the node into the given regions, producing constrained frames.
     fn layout(
         &self,
         ctx: &mut LayoutContext,
         regions: &Regions,
     ) -> Vec<Constrained<Rc<Frame>>>;
 }
+
+/// A dynamic [block-level](BlockLevel) layouting node.
+#[derive(Clone)]
+pub struct BlockNode {
+    node: Rc<dyn BlockLevel>,
+    #[cfg(feature = "layout-cache")]
+    hash: u64,
+}
+
+impl BlockNode {
+    /// Create a new dynamic node from any block-level node.
+    #[cfg(not(feature = "layout-cache"))]
+    pub fn new<T>(node: T) -> Self
+    where
+        T: BlockLevel + 'static,
+    {
+        Self { node: Rc::new(node) }
+    }
+
+    /// Create a new dynamic node from any block-level node.
+    #[cfg(feature = "layout-cache")]
+    pub fn new<T>(node: T) -> Self
+    where
+        T: BlockLevel + Hash + 'static,
+    {
+        Self {
+            hash: hash_node(&node),
+            node: Rc::new(node),
+        }
+    }
+}
+
+impl BlockLevel for BlockNode {
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Rc<Frame>>> {
+        #[cfg(not(feature = "layout-cache"))]
+        return self.node.layout(ctx, regions);
+
+        #[cfg(feature = "layout-cache")]
+        ctx.layouts.get(self.hash, regions).unwrap_or_else(|| {
+            ctx.level += 1;
+            let frames = self.node.layout(ctx, regions);
+            ctx.level -= 1;
+
+            let entry = FramesEntry::new(frames.clone(), ctx.level);
+
+            #[cfg(debug_assertions)]
+            if !entry.check(regions) {
+                eprintln!("node: {:#?}", self.node);
+                eprintln!("regions: {:#?}", regions);
+                eprintln!(
+                    "constraints: {:#?}",
+                    frames.iter().map(|c| c.cts).collect::<Vec<_>>()
+                );
+                panic!("constraints did not match regions they were created for");
+            }
+
+            ctx.layouts.insert(self.hash, entry);
+            frames
+        })
+    }
+}
+
+#[cfg(feature = "layout-cache")]
+impl Hash for BlockNode {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        state.write_u64(self.hash);
+    }
+}
+
+impl Debug for BlockNode {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.node.fmt(f)
+    }
+}
+
+/// Inline-level nodes are layouted as part of paragraph layout.
+///
+/// They only know the width and not the height of the paragraph's region and
+/// return only a single frame.
+pub trait InlineLevel: Debug {
+    /// Layout the node into a frame.
+    fn layout(&self, ctx: &mut LayoutContext, space: Length, base: Size) -> Frame;
+}
+
+/// A dynamic [inline-level](InlineLevel) layouting node.
+#[derive(Clone)]
+pub struct InlineNode {
+    node: Rc<dyn InlineLevel>,
+    #[cfg(feature = "layout-cache")]
+    hash: u64,
+}
+
+impl InlineNode {
+    /// Create a new dynamic node from any inline-level node.
+    #[cfg(not(feature = "layout-cache"))]
+    pub fn new<T>(node: T) -> Self
+    where
+        T: InlineLevel + 'static,
+    {
+        Self { node: Rc::new(node) }
+    }
+
+    /// Create a new dynamic node from any inline-level node.
+    #[cfg(feature = "layout-cache")]
+    pub fn new<T>(node: T) -> Self
+    where
+        T: InlineLevel + Hash + 'static,
+    {
+        Self {
+            hash: hash_node(&node),
+            node: Rc::new(node),
+        }
+    }
+}
+
+impl InlineLevel for InlineNode {
+    fn layout(&self, ctx: &mut LayoutContext, space: Length, base: Size) -> Frame {
+        self.node.layout(ctx, space, base)
+    }
+}
+
+#[cfg(feature = "layout-cache")]
+impl Hash for InlineNode {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        state.write_u64(self.hash);
+    }
+}
+
+impl Debug for InlineNode {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.node.fmt(f)
+    }
+}
+
+/// Hash a node alongside its type id.
+#[cfg(feature = "layout-cache")]
+fn hash_node(node: &(impl Hash + 'static)) -> u64 {
+    let mut state = FxHasher64::default();
+    node.type_id().hash(&mut state);
+    node.hash(&mut state);
+    state.finish()
+}
diff --git a/src/layout/pad.rs b/src/layout/pad.rs
index dfe6dc47..20fcc161 100644
--- a/src/layout/pad.rs
+++ b/src/layout/pad.rs
@@ -7,10 +7,10 @@ pub struct PadNode {
     /// The amount of padding.
     pub padding: Sides<Linear>,
     /// The child node whose sides to pad.
-    pub child: LayoutNode,
+    pub child: BlockNode,
 }
 
-impl Layout for PadNode {
+impl BlockLevel for PadNode {
     fn layout(
         &self,
         ctx: &mut LayoutContext,
@@ -22,7 +22,7 @@ impl Layout for PadNode {
             &regions.map(|size| size - self.padding.resolve(size).size()),
         );
 
-        for (Constrained { item: frame, constraints }, (current, base)) in
+        for (Constrained { item: frame, cts }, (current, base)) in
             frames.iter_mut().zip(regions.iter())
         {
             fn solve_axis(length: Length, padding: Linear) -> Length {
@@ -46,7 +46,7 @@ impl Layout for PadNode {
             new.push_frame(origin, prev);
 
             // Inflate min and max contraints by the padding.
-            for spec in [&mut constraints.min, &mut constraints.max] {
+            for spec in [&mut cts.min, &mut cts.max] {
                 if let Some(x) = spec.x.as_mut() {
                     *x += padding.size().w;
                 }
@@ -56,18 +56,18 @@ impl Layout for PadNode {
             }
 
             // Set exact and base constraints if the child had them.
-            constraints.exact.x.and_set(Some(current.w));
-            constraints.exact.y.and_set(Some(current.h));
-            constraints.base.x.and_set(Some(base.w));
-            constraints.base.y.and_set(Some(base.h));
+            cts.exact.x.and_set(Some(current.w));
+            cts.exact.y.and_set(Some(current.h));
+            cts.base.x.and_set(Some(base.w));
+            cts.base.y.and_set(Some(base.h));
 
             // Also set base constraints if the padding is relative.
             if self.padding.left.is_relative() || self.padding.right.is_relative() {
-                constraints.base.x = Some(base.w);
+                cts.base.x = Some(base.w);
             }
 
             if self.padding.top.is_relative() || self.padding.bottom.is_relative() {
-                constraints.base.y = Some(base.h);
+                cts.base.y = Some(base.h);
             }
         }
 
@@ -75,8 +75,8 @@ impl Layout for PadNode {
     }
 }
 
-impl From<PadNode> for LayoutNode {
-    fn from(pad: PadNode) -> Self {
-        Self::new(pad)
+impl From<PadNode> for BlockNode {
+    fn from(node: PadNode) -> Self {
+        Self::new(node)
     }
 }
diff --git a/src/layout/par.rs b/src/layout/par.rs
index cf37f005..1c618fff 100644
--- a/src/layout/par.rs
+++ b/src/layout/par.rs
@@ -18,7 +18,7 @@ pub struct ParNode {
     /// The inline direction of this paragraph.
     pub dir: Dir,
     /// The spacing to insert between each line.
-    pub line_spacing: Length,
+    pub leading: Length,
     /// The nodes to be arranged in a paragraph.
     pub children: Vec<ParChild>,
 }
@@ -31,10 +31,10 @@ pub enum ParChild {
     /// A run of text and how to align it in its line.
     Text(EcoString, Align, Rc<TextStyle>, Vec<Decoration>),
     /// Any child node and how to align it in its line.
-    Any(LayoutNode, Align, Vec<Decoration>),
+    Any(InlineNode, Align, Vec<Decoration>),
 }
 
-impl Layout for ParNode {
+impl BlockLevel for ParNode {
     fn layout(
         &self,
         ctx: &mut LayoutContext,
@@ -88,9 +88,9 @@ impl ParNode {
     }
 }
 
-impl From<ParNode> for LayoutNode {
-    fn from(par: ParNode) -> Self {
-        Self::new(par)
+impl From<ParNode> for BlockNode {
+    fn from(node: ParNode) -> Self {
+        Self::new(node)
     }
 }
 
@@ -110,7 +110,7 @@ struct ParLayouter<'a> {
     /// The top-level direction.
     dir: Dir,
     /// The line spacing.
-    line_spacing: Length,
+    leading: Length,
     /// Bidirectional text embedding levels for the paragraph.
     bidi: BidiInfo<'a>,
     /// Layouted children and separated text runs.
@@ -143,14 +143,14 @@ impl<'a> ParLayouter<'a> {
                     // TODO: Also split by language and script.
                     for (subrange, dir) in split_runs(&bidi, range) {
                         let text = &bidi.text[subrange.clone()];
-                        let shaped = shape(ctx, text, dir, style);
+                        let shaped = shape(ctx, text, style, dir);
                         items.push(ParItem::Text(shaped, *align, decos));
                         ranges.push(subrange);
                     }
                 }
                 ParChild::Any(node, align, decos) => {
-                    let frame = node.layout(ctx, regions).remove(0);
-                    items.push(ParItem::Frame(frame.item, *align, decos));
+                    let frame = node.layout(ctx, regions.current.w, regions.base);
+                    items.push(ParItem::Frame(frame, *align, decos));
                     ranges.push(range);
                 }
             }
@@ -158,7 +158,7 @@ impl<'a> ParLayouter<'a> {
 
         Self {
             dir: par.dir,
-            line_spacing: par.line_spacing,
+            leading: par.leading,
             bidi,
             items,
             ranges,
@@ -171,7 +171,7 @@ impl<'a> ParLayouter<'a> {
         ctx: &mut LayoutContext,
         regions: Regions,
     ) -> Vec<Constrained<Rc<Frame>>> {
-        let mut stack = LineStack::new(self.line_spacing, regions);
+        let mut stack = LineStack::new(self.leading, regions);
 
         // The current line attempt.
         // Invariant: Always fits into `stack.regions.current`.
@@ -196,18 +196,18 @@ impl<'a> ParLayouter<'a> {
                     // the width of the region must not fit the width of the
                     // tried line.
                     if !stack.regions.current.w.fits(line.size.w) {
-                        stack.constraints.max.x.set_min(line.size.w);
+                        stack.cts.max.x.set_min(line.size.w);
                     }
 
                     // Same as above, but for height.
                     if !stack.regions.current.h.fits(line.size.h) {
-                        let too_large = stack.size.h + self.line_spacing + line.size.h;
-                        stack.constraints.max.y.set_min(too_large);
+                        let too_large = stack.size.h + self.leading + line.size.h;
+                        stack.cts.max.y.set_min(too_large);
                     }
 
                     stack.push(last_line);
 
-                    stack.constraints.min.y = Some(stack.size.h);
+                    stack.cts.min.y = Some(stack.size.h);
                     start = last_end;
                     line = LineLayout::new(ctx, &self, start .. end);
                 }
@@ -223,8 +223,8 @@ impl<'a> ParLayouter<'a> {
                 // Again, the line must not fit. It would if the space taken up
                 // plus the line height would fit, therefore the constraint
                 // below.
-                let too_large = stack.size.h + self.line_spacing + line.size.h;
-                stack.constraints.max.y.set_min(too_large);
+                let too_large = stack.size.h + self.leading + line.size.h;
+                stack.cts.max.y.set_min(too_large);
 
                 stack.finish_region(ctx);
             }
@@ -247,18 +247,18 @@ impl<'a> ParLayouter<'a> {
                     }
                 }
 
-                stack.constraints.min.y = Some(stack.size.h);
+                stack.cts.min.y = Some(stack.size.h);
             } else {
                 // Otherwise, the line fits both horizontally and vertically
                 // and we remember it.
-                stack.constraints.min.x.set_max(line.size.w);
+                stack.cts.min.x.set_max(line.size.w);
                 last = Some((line, end));
             }
         }
 
         if let Some((line, _)) = last {
             stack.push(line);
-            stack.constraints.min.y = Some(stack.size.h);
+            stack.cts.min.y = Some(stack.size.h);
         }
 
         stack.finish(ctx)
@@ -292,7 +292,7 @@ enum ParItem<'a> {
     /// A shaped text run with consistent direction.
     Text(ShapedText<'a>, Align, &'a [Decoration]),
     /// A layouted child node.
-    Frame(Rc<Frame>, Align, &'a [Decoration]),
+    Frame(Frame, Align, &'a [Decoration]),
 }
 
 impl ParItem<'_> {
@@ -463,10 +463,10 @@ impl<'a> LineLayout<'a> {
                 ParItem::Frame(ref frame, align, decos) => {
                     let mut frame = frame.clone();
                     for deco in decos {
-                        deco.apply(ctx, Rc::make_mut(&mut frame));
+                        deco.apply(ctx, &mut frame);
                     }
                     let pos = position(&frame, align);
-                    output.push_frame(pos, frame);
+                    output.merge_frame(pos, frame);
                 }
             }
         }
@@ -522,23 +522,23 @@ impl<'a> LineLayout<'a> {
 
 /// Stacks lines on top of each other.
 struct LineStack<'a> {
-    line_spacing: Length,
+    leading: Length,
     full: Size,
     regions: Regions,
     size: Size,
     lines: Vec<LineLayout<'a>>,
     finished: Vec<Constrained<Rc<Frame>>>,
-    constraints: Constraints,
+    cts: Constraints,
     overflowing: bool,
 }
 
 impl<'a> LineStack<'a> {
     /// Create an empty line stack.
-    fn new(line_spacing: Length, regions: Regions) -> Self {
+    fn new(leading: Length, regions: Regions) -> Self {
         Self {
-            line_spacing,
+            leading,
             full: regions.current,
-            constraints: Constraints::new(regions.expand),
+            cts: Constraints::new(regions.expand),
             regions,
             size: Size::zero(),
             lines: vec![],
@@ -549,12 +549,12 @@ impl<'a> LineStack<'a> {
 
     /// Push a new line into the stack.
     fn push(&mut self, line: LineLayout<'a>) {
-        self.regions.current.h -= line.size.h + self.line_spacing;
+        self.regions.current.h -= line.size.h + self.leading;
 
         self.size.w.set_max(line.size.w);
         self.size.h += line.size.h;
         if !self.lines.is_empty() {
-            self.size.h += self.line_spacing;
+            self.size.h += self.leading;
         }
 
         self.lines.push(line);
@@ -564,13 +564,13 @@ impl<'a> LineStack<'a> {
     fn finish_region(&mut self, ctx: &LayoutContext) {
         if self.regions.expand.x {
             self.size.w = self.regions.current.w;
-            self.constraints.exact.x = Some(self.regions.current.w);
+            self.cts.exact.x = Some(self.regions.current.w);
         }
 
         if self.overflowing {
-            self.constraints.min.y = None;
-            self.constraints.max.y = None;
-            self.constraints.exact = self.full.to_spec().map(Some);
+            self.cts.min.y = None;
+            self.cts.max.y = None;
+            self.cts.exact = self.full.to_spec().map(Some);
         }
 
         let mut output = Frame::new(self.size, self.size.h);
@@ -586,14 +586,14 @@ impl<'a> LineStack<'a> {
                 first = false;
             }
 
-            offset += frame.size.h + self.line_spacing;
+            offset += frame.size.h + self.leading;
             output.merge_frame(pos, frame);
         }
 
-        self.finished.push(output.constrain(self.constraints));
+        self.finished.push(output.constrain(self.cts));
         self.regions.next();
         self.full = self.regions.current;
-        self.constraints = Constraints::new(self.regions.expand);
+        self.cts = Constraints::new(self.regions.expand);
         self.size = Size::zero();
     }
 
diff --git a/src/layout/shape.rs b/src/layout/shape.rs
index 3469f660..13d5418f 100644
--- a/src/layout/shape.rs
+++ b/src/layout/shape.rs
@@ -1,6 +1,7 @@
 use std::f64::consts::SQRT_2;
 
 use super::*;
+use crate::util::RcExt;
 
 /// Places its child into a sizable and fillable shape.
 #[derive(Debug)]
@@ -15,7 +16,7 @@ pub struct ShapeNode {
     /// How to fill the shape, if at all.
     pub fill: Option<Paint>,
     /// The child node to place into the shape, if any.
-    pub child: Option<LayoutNode>,
+    pub child: Option<BlockNode>,
 }
 
 /// The type of a shape.
@@ -31,40 +32,15 @@ pub enum ShapeKind {
     Ellipse,
 }
 
-impl Layout for ShapeNode {
-    fn layout(
-        &self,
-        ctx: &mut LayoutContext,
-        regions: &Regions,
-    ) -> Vec<Constrained<Rc<Frame>>> {
+impl InlineLevel for ShapeNode {
+    fn layout(&self, ctx: &mut LayoutContext, space: Length, base: Size) -> Frame {
         // Resolve width and height relative to the region's base.
-        let width = self.width.map(|w| w.resolve(regions.base.w));
-        let height = self.height.map(|h| h.resolve(regions.base.h));
-
-        // Generate constraints.
-        let constraints = {
-            let mut cts = Constraints::new(regions.expand);
-            cts.set_base_if_linear(regions.base, Spec::new(self.width, self.height));
-
-            // Set tight exact and base constraints if the child is
-            // automatically sized since we don't know what the child might do.
-            if self.width.is_none() {
-                cts.exact.x = Some(regions.current.w);
-                cts.base.x = Some(regions.base.w);
-            }
-
-            // Same here.
-            if self.height.is_none() {
-                cts.exact.y = Some(regions.current.h);
-                cts.base.y = Some(regions.base.h);
-            }
-
-            cts
-        };
+        let width = self.width.map(|w| w.resolve(base.w));
+        let height = self.height.map(|h| h.resolve(base.h));
 
         // Layout.
-        let mut frames = if let Some(child) = &self.child {
-            let mut node: &dyn Layout = child;
+        let mut frame = if let Some(child) = &self.child {
+            let mut node: &dyn BlockLevel = child;
 
             let padded;
             if matches!(self.shape, ShapeKind::Circle | ShapeKind::Ellipse) {
@@ -79,14 +55,12 @@ impl Layout for ShapeNode {
 
             // The "pod" is the region into which the child will be layouted.
             let mut pod = {
-                let size = Size::new(
-                    width.unwrap_or(regions.current.w),
-                    height.unwrap_or(regions.current.h),
-                );
+                let size =
+                    Size::new(width.unwrap_or(space), height.unwrap_or(Length::inf()));
 
                 let base = Size::new(
-                    if width.is_some() { size.w } else { regions.base.w },
-                    if height.is_some() { size.h } else { regions.base.h },
+                    if width.is_some() { size.w } else { base.w },
+                    if height.is_some() { size.h } else { base.h },
                 );
 
                 let expand = Spec::new(width.is_some(), height.is_some());
@@ -108,17 +82,15 @@ impl Layout for ShapeNode {
 
             // Validate and set constraints.
             assert_eq!(frames.len(), 1);
-            frames[0].constraints = constraints;
-            frames
+            Rc::take(frames.into_iter().next().unwrap().item)
         } else {
             // Resolve shape size.
             let size = Size::new(width.unwrap_or_default(), height.unwrap_or_default());
-            vec![Frame::new(size, size.h).constrain(constraints)]
+            Frame::new(size, size.h)
         };
 
         // Add background shape if desired.
         if let Some(fill) = self.fill {
-            let frame = Rc::make_mut(&mut frames[0].item);
             let (pos, geometry) = match self.shape {
                 ShapeKind::Square | ShapeKind::Rect => {
                     (Point::zero(), Geometry::Rect(frame.size))
@@ -131,12 +103,12 @@ impl Layout for ShapeNode {
             frame.prepend(pos, Element::Geometry(geometry, fill));
         }
 
-        frames
+        frame
     }
 }
 
-impl From<ShapeNode> for LayoutNode {
-    fn from(shape: ShapeNode) -> Self {
-        Self::new(shape)
+impl From<ShapeNode> for InlineNode {
+    fn from(node: ShapeNode) -> Self {
+        Self::new(node)
     }
 }
diff --git a/src/layout/spacing.rs b/src/layout/spacing.rs
deleted file mode 100644
index 68fab3e6..00000000
--- a/src/layout/spacing.rs
+++ /dev/null
@@ -1,50 +0,0 @@
-use super::*;
-
-/// Spacing between other nodes.
-#[derive(Debug)]
-#[cfg_attr(feature = "layout-cache", derive(Hash))]
-pub struct SpacingNode {
-    /// Which axis to space on.
-    pub axis: SpecAxis,
-    /// How much spacing to add.
-    pub amount: Linear,
-}
-
-impl Layout for SpacingNode {
-    fn layout(
-        &self,
-        _: &mut LayoutContext,
-        regions: &Regions,
-    ) -> Vec<Constrained<Rc<Frame>>> {
-        let base = regions.base.get(self.axis);
-        let resolved = self.amount.resolve(base);
-        let limit = regions.current.get(self.axis);
-
-        // Generate constraints.
-        let mut cts = Constraints::new(regions.expand);
-        if self.amount.is_relative() {
-            cts.base.set(self.axis, Some(base));
-        }
-
-        // If the spacing fits into the region, any larger region would also do.
-        // If it was limited though, any change it region size might lead to
-        // different results.
-        if resolved < limit {
-            cts.min.set(self.axis, Some(resolved));
-        } else {
-            cts.exact.set(self.axis, Some(limit));
-        }
-
-        // Create frame with limited spacing size along spacing axis and zero
-        // extent along the other axis.
-        let mut size = Size::zero();
-        size.set(self.axis, resolved.min(limit));
-        vec![Frame::new(size, size.h).constrain(cts)]
-    }
-}
-
-impl From<SpacingNode> for LayoutNode {
-    fn from(spacing: SpacingNode) -> Self {
-        Self::new(spacing)
-    }
-}
diff --git a/src/layout/stack.rs b/src/layout/stack.rs
index 4b9328a7..bbaf022b 100644
--- a/src/layout/stack.rs
+++ b/src/layout/stack.rs
@@ -12,7 +12,16 @@ pub struct StackNode {
     pub children: Vec<StackChild>,
 }
 
-impl Layout for StackNode {
+/// A child of a stack node.
+#[cfg_attr(feature = "layout-cache", derive(Hash))]
+pub enum StackChild {
+    /// Spacing between other nodes.
+    Spacing(Linear),
+    /// Any block node and how to align it in the stack.
+    Any(BlockNode, Align),
+}
+
+impl BlockLevel for StackNode {
     fn layout(
         &self,
         ctx: &mut LayoutContext,
@@ -22,37 +31,18 @@ impl Layout for StackNode {
     }
 }
 
-impl From<StackNode> for LayoutNode {
-    fn from(stack: StackNode) -> Self {
-        Self::new(stack)
-    }
-}
-
-/// A child of a stack node.
-#[cfg_attr(feature = "layout-cache", derive(Hash))]
-pub struct StackChild {
-    /// The node itself.
-    pub node: LayoutNode,
-    /// How to align the node along the block axis.
-    pub align: Align,
-}
-
-impl StackChild {
-    /// Create a new stack child.
-    pub fn new(node: impl Into<LayoutNode>, align: Align) -> Self {
-        Self { node: node.into(), align }
-    }
-
-    /// Create a spacing stack child.
-    pub fn spacing(amount: impl Into<Linear>, axis: SpecAxis) -> Self {
-        Self::new(SpacingNode { amount: amount.into(), axis }, Align::Start)
+impl From<StackNode> for BlockNode {
+    fn from(node: StackNode) -> Self {
+        Self::new(node)
     }
 }
 
 impl Debug for StackChild {
     fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        write!(f, "{:?}: ", self.align)?;
-        self.node.fmt(f)
+        match self {
+            Self::Spacing(v) => write!(f, "Spacing({:?})", v),
+            Self::Any(node, _) => node.fmt(f),
+        }
     }
 }
 
@@ -106,12 +96,17 @@ impl<'a> StackLayouter<'a> {
     /// Layout all children.
     fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Rc<Frame>>> {
         for child in &self.stack.children {
-            let frames = child.node.layout(ctx, &self.regions);
-            let len = frames.len();
-            for (i, frame) in frames.into_iter().enumerate() {
-                self.push_frame(frame.item, child.align);
-                if i + 1 < len {
-                    self.finish_region();
+            match *child {
+                StackChild::Spacing(amount) => self.space(amount),
+                StackChild::Any(ref node, align) => {
+                    let frames = node.layout(ctx, &self.regions);
+                    let len = frames.len();
+                    for (i, frame) in frames.into_iter().enumerate() {
+                        self.push_frame(frame.item, align);
+                        if i + 1 < len {
+                            self.finish_region();
+                        }
+                    }
                 }
             }
         }
@@ -120,6 +115,22 @@ impl<'a> StackLayouter<'a> {
         self.finished
     }
 
+    /// Add block-axis spacing into the current region.
+    fn space(&mut self, amount: Linear) {
+        // Resolve the linear.
+        let full = self.full.get(self.axis);
+        let resolved = amount.resolve(full);
+
+        // Cap the spacing to the remaining available space. This action does
+        // not directly affect the constraints because of the cap.
+        let remaining = self.regions.current.get_mut(self.axis);
+        let capped = resolved.min(*remaining);
+
+        // Grow our size and shrink the available space in the region.
+        self.used.block += capped;
+        *remaining -= capped;
+    }
+
     /// Push a frame into the current region.
     fn push_frame(&mut self, frame: Rc<Frame>, align: Align) {
         // Grow our size.
diff --git a/src/layout/shaping.rs b/src/layout/text.rs
index 7bd2646d..a89d7e3b 100644
--- a/src/layout/shaping.rs
+++ b/src/layout/text.rs
@@ -3,7 +3,7 @@ use std::ops::Range;
 
 use rustybuzz::UnicodeBuffer;
 
-use super::{Element, Frame, Glyph, LayoutContext, Text};
+use super::*;
 use crate::font::{Face, FaceId, FontVariant};
 use crate::geom::{Dir, Em, Length, Point, Size};
 use crate::style::TextStyle;
@@ -13,8 +13,8 @@ use crate::util::SliceExt;
 pub fn shape<'a>(
     ctx: &mut LayoutContext,
     text: &'a str,
-    dir: Dir,
     style: &'a TextStyle,
+    dir: Dir,
 ) -> ShapedText<'a> {
     let mut glyphs = vec![];
     if !text.is_empty() {
@@ -23,16 +23,15 @@ pub fn shape<'a>(
             &mut glyphs,
             0,
             text,
-            dir,
             style.size,
             style.variant(),
             style.families(),
             None,
+            dir,
         );
     }
 
     let (size, baseline) = measure(ctx, &glyphs, style);
-
     ShapedText {
         text,
         dir,
@@ -134,7 +133,7 @@ impl<'a> ShapedText<'a> {
                 glyphs: Cow::Borrowed(glyphs),
             }
         } else {
-            shape(ctx, &self.text[text_range], self.dir, self.style)
+            shape(ctx, &self.text[text_range], self.style, self.dir)
         }
     }
 
@@ -209,11 +208,11 @@ fn shape_segment<'a>(
     glyphs: &mut Vec<ShapedGlyph>,
     base: usize,
     text: &str,
-    dir: Dir,
     size: Length,
     variant: FontVariant,
     mut families: impl Iterator<Item = &'a str> + Clone,
     mut first_face: Option<FaceId>,
+    dir: Dir,
 ) {
     // Select the font family.
     let (face_id, fallback) = loop {
@@ -316,11 +315,11 @@ fn shape_segment<'a>(
                 glyphs,
                 base + range.start,
                 &text[range],
-                dir,
                 size,
                 variant,
                 families.clone(),
                 first_face,
+                dir,
             );
 
             face = ctx.fonts.get(face_id);
diff --git a/src/layout/tree.rs b/src/layout/tree.rs
deleted file mode 100644
index 181bb611..00000000
--- a/src/layout/tree.rs
+++ /dev/null
@@ -1,132 +0,0 @@
-use std::fmt::{self, Debug, Formatter};
-
-use super::*;
-
-#[cfg(feature = "layout-cache")]
-use {
-    fxhash::FxHasher64,
-    std::any::Any,
-    std::hash::{Hash, Hasher},
-};
-
-/// A tree of layout nodes.
-pub struct LayoutTree {
-    /// Runs of pages with the same properties.
-    pub runs: Vec<PageRun>,
-}
-
-impl LayoutTree {
-    /// Layout the tree into a collection of frames.
-    pub fn layout(&self, ctx: &mut LayoutContext) -> Vec<Rc<Frame>> {
-        self.runs.iter().flat_map(|run| run.layout(ctx)).collect()
-    }
-}
-
-impl Debug for LayoutTree {
-    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        f.debug_list().entries(&self.runs).finish()
-    }
-}
-
-/// A run of pages that all have the same properties.
-#[derive(Debug)]
-pub struct PageRun {
-    /// The size of each page.
-    pub size: Size,
-    /// The layout node that produces the actual pages (typically a
-    /// [`StackNode`]).
-    pub child: LayoutNode,
-}
-
-impl PageRun {
-    /// Layout the page run.
-    pub fn layout(&self, ctx: &mut LayoutContext) -> Vec<Rc<Frame>> {
-        // When one of the lengths is infinite the page fits its content along
-        // that axis.
-        let expand = self.size.to_spec().map(Length::is_finite);
-        let regions = Regions::repeat(self.size, self.size, expand);
-        self.child.layout(ctx, &regions).into_iter().map(|c| c.item).collect()
-    }
-}
-
-/// A dynamic layouting node.
-#[derive(Clone)]
-pub struct LayoutNode {
-    node: Rc<dyn Layout>,
-    #[cfg(feature = "layout-cache")]
-    hash: u64,
-}
-
-impl LayoutNode {
-    /// Create a new instance from any node that satisifies the required bounds.
-    #[cfg(not(feature = "layout-cache"))]
-    pub fn new<T>(node: T) -> Self
-    where
-        T: Layout + 'static,
-    {
-        Self { node: Rc::new(node) }
-    }
-
-    /// Create a new instance from any node that satisifies the required bounds.
-    #[cfg(feature = "layout-cache")]
-    pub fn new<T>(node: T) -> Self
-    where
-        T: Layout + Hash + 'static,
-    {
-        let hash = {
-            let mut state = FxHasher64::default();
-            node.type_id().hash(&mut state);
-            node.hash(&mut state);
-            state.finish()
-        };
-
-        Self { node: Rc::new(node), hash }
-    }
-}
-
-impl Layout for LayoutNode {
-    fn layout(
-        &self,
-        ctx: &mut LayoutContext,
-        regions: &Regions,
-    ) -> Vec<Constrained<Rc<Frame>>> {
-        #[cfg(not(feature = "layout-cache"))]
-        return self.node.layout(ctx, regions);
-
-        #[cfg(feature = "layout-cache")]
-        ctx.layouts.get(self.hash, regions).unwrap_or_else(|| {
-            ctx.level += 1;
-            let frames = self.node.layout(ctx, regions);
-            ctx.level -= 1;
-
-            let entry = FramesEntry::new(frames.clone(), ctx.level);
-
-            #[cfg(debug_assertions)]
-            if !entry.check(regions) {
-                eprintln!("node: {:#?}", self.node);
-                eprintln!("regions: {:#?}", regions);
-                eprintln!(
-                    "constraints: {:#?}",
-                    frames.iter().map(|c| c.constraints).collect::<Vec<_>>()
-                );
-                panic!("constraints did not match regions they were created for");
-            }
-
-            ctx.layouts.insert(self.hash, entry);
-            frames
-        })
-    }
-}
-
-impl Debug for LayoutNode {
-    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        self.node.fmt(f)
-    }
-}
-
-#[cfg(feature = "layout-cache")]
-impl Hash for LayoutNode {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        state.write_u64(self.hash);
-    }
-}