Constraints (#31)

14 files changed, 426 insertions, 85 deletions

diff --git a/src/geom/gen.rs b/src/geom/gen.rs
index 075b7377..57dc277d 100644
--- a/src/geom/gen.rs
+++ b/src/geom/gen.rs
@@ -23,6 +23,14 @@ impl<T> Gen<T> {
         Self { cross: value.clone(), main: value }
     }
 
+    /// Maps the individual fields with `f`.
+    pub fn map<F, U>(self, mut f: F) -> Gen<U>
+    where
+        F: FnMut(T) -> U,
+    {
+        Gen { cross: f(self.cross), main: f(self.main) }
+    }
+
     /// Convert to the specific representation.
     pub fn to_spec(self, main: SpecAxis) -> Spec<T> {
         match main {
diff --git a/src/geom/linear.rs b/src/geom/linear.rs
index c3216b21..38d19b13 100644
--- a/src/geom/linear.rs
+++ b/src/geom/linear.rs
@@ -40,6 +40,11 @@ impl Linear {
     pub fn is_zero(self) -> bool {
         self.rel.is_zero() && self.abs.is_zero()
     }
+
+    /// Whether there is a linear component.
+    pub fn is_relative(&self) -> bool {
+        !self.rel.is_zero()
+    }
 }
 
 impl Display for Linear {
diff --git a/src/geom/size.rs b/src/geom/size.rs
index 4b94d0ae..7967dbdc 100644
--- a/src/geom/size.rs
+++ b/src/geom/size.rs
@@ -50,6 +50,11 @@ impl Size {
         Point::new(self.width, self.height)
     }
 
+    /// Convert to a Spec.
+    pub fn to_spec(self) -> Spec<Length> {
+        Spec::new(self.width, self.height)
+    }
+
     /// Convert to the generic representation.
     pub fn to_gen(self, main: SpecAxis) -> Gen<Length> {
         match main {
diff --git a/src/geom/spec.rs b/src/geom/spec.rs
index d0da3bca..f8f62f9f 100644
--- a/src/geom/spec.rs
+++ b/src/geom/spec.rs
@@ -26,6 +26,17 @@ impl<T> Spec<T> {
         }
     }
 
+    /// Maps the individual fields with `f`.
+    pub fn map<F, U>(self, mut f: F) -> Spec<U>
+    where
+        F: FnMut(T) -> U,
+    {
+        Spec {
+            horizontal: f(self.horizontal),
+            vertical: f(self.vertical),
+        }
+    }
+
     /// Convert to the generic representation.
     pub fn to_gen(self, main: SpecAxis) -> Gen<T> {
         match main {
@@ -33,6 +44,15 @@ impl<T> Spec<T> {
             SpecAxis::Vertical => Gen::new(self.horizontal, self.vertical),
         }
     }
+
+    /// Compare to whether two instances are equal when compared field-by-field
+    /// with `f`.
+    pub fn eq_by<U, F>(&self, other: &Spec<U>, eq: F) -> bool
+    where
+        F: Fn(&T, &U) -> bool,
+    {
+        eq(&self.vertical, &other.vertical) && eq(&self.horizontal, &other.horizontal)
+    }
 }
 
 impl Spec<Length> {
diff --git a/src/layout/background.rs b/src/layout/background.rs
index 3a76a264..41138bdf 100644
--- a/src/layout/background.rs
+++ b/src/layout/background.rs
@@ -19,7 +19,11 @@ pub enum BackgroundShape {
 }
 
 impl Layout for BackgroundNode {
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>> {
         let mut frames = self.child.layout(ctx, regions);
 
         for frame in &mut frames {
@@ -31,7 +35,7 @@ impl Layout for BackgroundNode {
             };
 
             let element = Element::Geometry(shape, self.fill);
-            frame.elements.insert(0, (point, element));
+            frame.item.elements.insert(0, (point, element));
         }
 
         frames
diff --git a/src/layout/fixed.rs b/src/layout/fixed.rs
index 233c27f3..19876987 100644
--- a/src/layout/fixed.rs
+++ b/src/layout/fixed.rs
@@ -12,16 +12,37 @@ pub struct FixedNode {
 }
 
 impl Layout for FixedNode {
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>> {
         let Regions { current, base, .. } = regions;
+        let mut constraints = Constraints::new(regions.expand);
+        constraints.set_base_using_linears(Spec::new(self.width, self.height), &regions);
+
         let size = Size::new(
             self.width.map_or(current.width, |w| w.resolve(base.width)),
             self.height.map_or(current.height, |h| h.resolve(base.height)),
         );
 
+        // If one dimension was not specified, the `current` size needs to remain static.
+        if self.width.is_none() {
+            constraints.exact.horizontal = Some(current.width);
+        }
+        if self.height.is_none() {
+            constraints.exact.vertical = Some(current.height);
+        }
+
         let expand = Spec::new(self.width.is_some(), self.height.is_some());
         let regions = Regions::one(size, expand);
-        self.child.layout(ctx, &regions)
+        let mut frames = self.child.layout(ctx, &regions);
+
+        if let Some(frame) = frames.first_mut() {
+            frame.constraints = constraints;
+        }
+
+        frames
     }
 }
 
diff --git a/src/layout/frame.rs b/src/layout/frame.rs
index 55f7f99a..5e5bcfe8 100644
--- a/src/layout/frame.rs
+++ b/src/layout/frame.rs
@@ -1,10 +1,11 @@
+use serde::{Deserialize, Serialize};
+
+use super::{Constrained, Constraints};
 use crate::color::Color;
 use crate::font::FaceId;
 use crate::geom::{Length, Path, Point, Size};
 use crate::image::ImageId;
 
-use serde::{Deserialize, Serialize};
-
 /// A finished layout with elements at fixed positions.
 #[derive(Default, Debug, Clone, PartialEq, Serialize, Deserialize)]
 pub struct Frame {
@@ -39,6 +40,11 @@ impl Frame {
             }
         }
     }
+
+    /// Wraps the frame with constraints.
+    pub fn constrain(self, constraints: Constraints) -> Constrained<Self> {
+        Constrained { item: self, constraints }
+    }
 }
 
 /// The building block frames are composed of.
diff --git a/src/layout/grid.rs b/src/layout/grid.rs
index 52e07d0d..6b8976a0 100644
--- a/src/layout/grid.rs
+++ b/src/layout/grid.rs
@@ -28,7 +28,11 @@ pub enum TrackSizing {
 }
 
 impl Layout for GridNode {
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>> {
         // Prepare grid layout by unifying content and gutter tracks.
         let mut layouter = GridLayouter::new(self, regions.clone());
 
@@ -71,8 +75,10 @@ struct GridLayouter<'a> {
     fr: Fractional,
     /// Rows in the current region.
     lrows: Vec<Row>,
+    /// Constraints for the active region.
+    constraints: Constraints,
     /// Frames for finished regions.
-    finished: Vec<Frame>,
+    finished: Vec<Constrained<Frame>>,
 }
 
 /// Produced by initial row layout, auto and linear rows are already finished,
@@ -138,6 +144,7 @@ impl<'a> GridLayouter<'a> {
             cols,
             rows,
             children: &grid.children,
+            constraints: Constraints::new(regions.expand),
             regions,
             rcols,
             lrows: vec![],
@@ -150,6 +157,16 @@ impl<'a> GridLayouter<'a> {
 
     /// Determine all column sizes.
     fn measure_columns(&mut self, ctx: &mut LayoutContext) {
+        enum Case {
+            PurelyLinear,
+            Fitting,
+            Overflowing,
+            Exact,
+        }
+
+        // The different cases affecting constraints.
+        let mut case = Case::PurelyLinear;
+
         // Sum of sizes of resolved linear tracks.
         let mut linear = Length::zero();
 
@@ -164,13 +181,20 @@ impl<'a> GridLayouter<'a> {
         // fractional tracks.
         for (&col, rcol) in self.cols.iter().zip(&mut self.rcols) {
             match col {
-                TrackSizing::Auto => {}
+                TrackSizing::Auto => {
+                    case = Case::Fitting;
+                }
                 TrackSizing::Linear(v) => {
                     let resolved = v.resolve(base.cross);
                     *rcol = resolved;
                     linear += resolved;
+                    *self.constraints.base.get_mut(self.cross) =
+                        Some(self.regions.base.get(self.cross));
+                }
+                TrackSizing::Fractional(v) => {
+                    case = Case::Fitting;
+                    fr += v;
                 }
-                TrackSizing::Fractional(v) => fr += v,
             }
         }
 
@@ -184,13 +208,33 @@ impl<'a> GridLayouter<'a> {
             // otherwise shrink auto columns.
             let remaining = available - auto;
             if remaining >= Length::zero() {
-                self.grow_fractional_columns(remaining, fr);
+                if !fr.is_zero() {
+                    self.grow_fractional_columns(remaining, fr);
+                    case = Case::Exact;
+                }
             } else {
                 self.shrink_auto_columns(available, count);
+                case = Case::Exact;
             }
+        } else if let Case::Fitting = case {
+            case = Case::Overflowing;
         }
 
         self.used.cross = self.rcols.iter().sum();
+
+        match case {
+            Case::PurelyLinear => {}
+            Case::Fitting => {
+                *self.constraints.min.get_mut(self.cross) = Some(self.used.cross);
+            }
+            Case::Overflowing => {
+                *self.constraints.max.get_mut(self.cross) = Some(linear);
+            }
+            Case::Exact => {
+                *self.constraints.exact.get_mut(self.cross) =
+                    Some(self.regions.current.get(self.cross));
+            }
+        }
     }
 
     /// Measure the size that is available to auto columns.
@@ -268,7 +312,7 @@ impl<'a> GridLayouter<'a> {
     }
 
     /// Layout the grid row-by-row.
-    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Frame> {
+    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Frame>> {
         for y in 0 .. self.rows.len() {
             match self.rows[y] {
                 TrackSizing::Auto => {
@@ -276,12 +320,16 @@ impl<'a> GridLayouter<'a> {
                 }
                 TrackSizing::Linear(v) => {
                     let base = self.regions.base.get(self.main);
+                    if v.is_relative() {
+                        *self.constraints.base.get_mut(self.main) = Some(base);
+                    }
                     let resolved = v.resolve(base);
                     let frame = self.layout_single_row(ctx, resolved, y);
                     self.push_row(ctx, frame);
                 }
                 TrackSizing::Fractional(v) => {
                     self.fr += v;
+                    *self.constraints.exact.get_mut(self.main) = Some(self.full);
                     self.lrows.push(Row::Fr(v, y));
                 }
             }
@@ -326,7 +374,11 @@ impl<'a> GridLayouter<'a> {
             self.push_row(ctx, frame);
         } else {
             let frames = self.layout_multi_row(ctx, first, &rest, y);
-            for frame in frames {
+            let len = frames.len();
+            for (i, frame) in frames.into_iter().enumerate() {
+                if i + 1 != len {
+                    *self.constraints.exact.get_mut(self.main) = Some(self.full);
+                }
                 self.push_row(ctx, frame);
             }
         }
@@ -348,7 +400,7 @@ impl<'a> GridLayouter<'a> {
                 let size = Gen::new(rcol, length).to_size(self.main);
                 let regions = Regions::one(size, Spec::splat(true));
                 let frame = node.layout(ctx, &regions).remove(0);
-                output.push_frame(pos.to_point(self.main), frame);
+                output.push_frame(pos.to_point(self.main), frame.item);
             }
 
             pos.cross += rcol;
@@ -385,7 +437,7 @@ impl<'a> GridLayouter<'a> {
                 // Push the layouted frames into the individual output frames.
                 let frames = node.layout(ctx, &regions);
                 for (output, frame) in outputs.iter_mut().zip(frames) {
-                    output.push_frame(pos.to_point(self.main), frame);
+                    output.push_frame(pos.to_point(self.main), frame.item);
                 }
             }
 
@@ -404,6 +456,7 @@ impl<'a> GridLayouter<'a> {
         while !self.regions.current.get(self.main).fits(length)
             && !self.regions.in_full_last()
         {
+            *self.constraints.max.get_mut(self.main) = Some(self.used.main + length);
             self.finish_region(ctx);
         }
 
@@ -417,6 +470,7 @@ impl<'a> GridLayouter<'a> {
         // Determine the size of the region.
         let length = if self.fr.is_zero() { self.used.main } else { self.full };
         let size = self.to_size(length);
+        *self.constraints.min.get_mut(self.main) = Some(length);
 
         // The frame for the region.
         let mut output = Frame::new(size, size.height);
@@ -449,7 +503,8 @@ impl<'a> GridLayouter<'a> {
         self.full = self.regions.current.get(self.main);
         self.used.main = Length::zero();
         self.fr = Fractional::zero();
-        self.finished.push(output);
+        self.finished.push(output.constrain(self.constraints));
+        self.constraints = Constraints::new(self.regions.expand);
     }
 
     /// Get the node in the cell in column `x` and row `y`.
diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs
new file mode 100644
index 00000000..427df079
--- /dev/null
+++ b/src/layout/incremental.rs
@@ -0,0 +1,147 @@
+use std::{collections::HashMap, ops::Deref};
+
+use super::*;
+
+/// Caches layouting artifacts.
+#[derive(Default, Debug, Clone)]
+pub struct LayoutCache {
+    /// Maps from node hashes to the resulting frames and regions in which the
+    /// frames are valid.
+    pub frames: HashMap<u64, FramesEntry>,
+}
+
+impl LayoutCache {
+    /// Create a new, empty layout cache.
+    pub fn new() -> Self {
+        Self { frames: HashMap::new() }
+    }
+
+    /// Clear the cache.
+    pub fn clear(&mut self) {
+        self.frames.clear();
+    }
+}
+
+#[derive(Debug, Clone)]
+/// Cached frames from past layouting.
+pub struct FramesEntry {
+    /// The cached frames for a node.
+    pub frames: Vec<Constrained<Frame>>,
+}
+
+impl FramesEntry {
+    /// Checks if the cached [`Frame`] is valid for the given regions.
+    pub fn check(&self, mut regions: Regions) -> Option<Vec<Constrained<Frame>>> {
+        for (i, frame) in self.frames.iter().enumerate() {
+            if (i != 0 && !regions.next()) || !frame.constraints.check(&regions) {
+                return None;
+            }
+        }
+
+        Some(self.frames.clone())
+    }
+}
+
+#[derive(Debug, Copy, Clone, PartialEq)]
+pub struct Constraints {
+    /// The minimum available length in the region.
+    pub min: Spec<Option<Length>>,
+    /// The maximum available length in the region.
+    pub max: Spec<Option<Length>>,
+    /// The available length in the region.
+    pub exact: Spec<Option<Length>>,
+    /// The base length of the region used for relative length resolution.
+    pub base: Spec<Option<Length>>,
+    /// The expand settings of the region.
+    pub expand: Spec<bool>,
+}
+
+impl Constraints {
+    /// Create a new region constraint.
+    pub fn new(expand: Spec<bool>) -> Self {
+        Self {
+            min: Spec::default(),
+            max: Spec::default(),
+            exact: Spec::default(),
+            base: Spec::default(),
+            expand,
+        }
+    }
+
+    /// Set the appropriate base constraints for (relative) width and height
+    /// metrics, respectively.
+    pub fn set_base_using_linears(
+        &mut self,
+        size: Spec<Option<Linear>>,
+        regions: &Regions,
+    ) {
+        // The full sizes need to be equal if there is a relative component in the sizes.
+        if size.horizontal.map_or(false, |l| l.is_relative()) {
+            self.base.horizontal = Some(regions.base.width);
+        }
+        if size.vertical.map_or(false, |l| l.is_relative()) {
+            self.base.vertical = Some(regions.base.height);
+        }
+    }
+
+    fn check(&self, regions: &Regions) -> bool {
+        if self.expand != regions.expand {
+            return false;
+        }
+
+        let base = regions.base.to_spec();
+        let current = regions.current.to_spec();
+
+        current.eq_by(&self.min, |x, y| y.map_or(true, |y| x >= &y))
+            && current.eq_by(&self.max, |x, y| y.map_or(true, |y| x < &y))
+            && current.eq_by(&self.exact, |x, y| y.map_or(true, |y| x == &y))
+            && base.eq_by(&self.base, |x, y| y.map_or(true, |y| x == &y))
+    }
+
+    /// Changes all constraints by adding the argument to them if they are set.
+    pub fn mutate(&mut self, size: Size) {
+        for x in &mut [self.min, self.max, self.exact, self.base] {
+            if let Some(horizontal) = x.horizontal.as_mut() {
+                *horizontal += size.width;
+            }
+            if let Some(vertical) = x.vertical.as_mut() {
+                *vertical += size.height;
+            }
+        }
+    }
+}
+
+#[derive(Debug, Copy, Clone, PartialEq)]
+pub struct Constrained<T> {
+    pub item: T,
+    pub constraints: Constraints,
+}
+
+impl<T> Deref for Constrained<T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        &self.item
+    }
+}
+
+pub trait OptionExt {
+    fn set_min(&mut self, other: Length);
+    fn set_max(&mut self, other: Length);
+}
+
+impl OptionExt for Option<Length> {
+    fn set_min(&mut self, other: Length) {
+        match self {
+            Some(x) => x.set_min(other),
+            None => *self = Some(other),
+        }
+    }
+
+    fn set_max(&mut self, other: Length) {
+        match self {
+            Some(x) => x.set_max(other),
+            None => *self = Some(other),
+        }
+    }
+}
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 9c4222c8..15c80017 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -4,6 +4,7 @@ mod background;
 mod fixed;
 mod frame;
 mod grid;
+mod incremental;
 mod pad;
 mod par;
 mod shaping;
@@ -13,16 +14,18 @@ pub use background::*;
 pub use fixed::*;
 pub use frame::*;
 pub use grid::*;
+pub use incremental::*;
 pub use pad::*;
 pub use par::*;
 pub use shaping::*;
 pub use stack::*;
 
 use std::any::Any;
-use std::collections::HashMap;
 use std::fmt::{self, Debug, Formatter};
 use std::hash::{Hash, Hasher};
 
+use fxhash::FxHasher64;
+
 use crate::cache::Cache;
 use crate::geom::*;
 use crate::loading::Loader;
@@ -64,7 +67,7 @@ impl PageRun {
         let Size { width, height } = self.size;
         let expand = Spec::new(width.is_finite(), height.is_finite());
         let regions = Regions::repeat(self.size, expand);
-        self.child.layout(ctx, &regions)
+        self.child.layout(ctx, &regions).into_iter().map(|c| c.item).collect()
     }
 }
 
@@ -80,26 +83,34 @@ impl AnyNode {
     where
         T: Layout + Debug + Clone + PartialEq + Hash + 'static,
     {
-        let hash = fxhash::hash64(&node);
+        let mut state = FxHasher64::default();
+        node.type_id().hash(&mut state);
+        node.hash(&mut state);
+        let hash = state.finish();
+
         Self { node: Box::new(node), hash }
     }
 }
 
 impl Layout for AnyNode {
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
-        if let Some(hit) = ctx.cache.layout.frames.get(&self.hash) {
-            if &hit.regions == regions {
-                return hit.frames.clone();
-            }
-        }
-
-        let frames = self.node.layout(ctx, regions);
-        ctx.cache.layout.frames.insert(self.hash, FramesEntry {
-            regions: regions.clone(),
-            frames: frames.clone(),
-        });
-
-        frames
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>> {
+        ctx.cache
+            .layout
+            .frames
+            .get(&self.hash)
+            .and_then(|x| x.check(regions.clone()))
+            .unwrap_or_else(|| {
+                let frames = self.node.layout(ctx, regions);
+                ctx.cache
+                    .layout
+                    .frames
+                    .insert(self.hash, FramesEntry { frames: frames.clone() });
+                frames
+            })
     }
 }
 
@@ -160,7 +171,11 @@ where
 /// Layout a node.
 pub trait Layout {
     /// Layout the node into the given regions.
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame>;
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>>;
 }
 
 /// The context for layouting.
@@ -171,33 +186,6 @@ pub struct LayoutContext<'a> {
     pub cache: &'a mut Cache,
 }
 
-/// Caches layouting artifacts.
-pub struct LayoutCache {
-    /// Maps from node hashes to the resulting frames and regions in which the
-    /// frames are valid.
-    pub frames: HashMap<u64, FramesEntry>,
-}
-
-impl LayoutCache {
-    /// Create a new, empty layout cache.
-    pub fn new() -> Self {
-        Self { frames: HashMap::new() }
-    }
-
-    /// Clear the cache.
-    pub fn clear(&mut self) {
-        self.frames.clear();
-    }
-}
-
-/// Cached frames from past layouting.
-pub struct FramesEntry {
-    /// The regions in which these frames are valid.
-    pub regions: Regions,
-    /// The cached frames for a node.
-    pub frames: Vec<Frame>,
-}
-
 /// A sequence of regions to layout into.
 #[derive(Debug, Clone, PartialEq)]
 pub struct Regions {
@@ -261,10 +249,13 @@ impl Regions {
     }
 
     /// Advance to the next region if there is any.
-    pub fn next(&mut self) {
+    pub fn next(&mut self) -> bool {
         if let Some(size) = self.backlog.pop().or(self.last) {
             self.current = size;
             self.base = size;
+            true
+        } else {
+            false
         }
     }
 
diff --git a/src/layout/pad.rs b/src/layout/pad.rs
index ccf0d5e1..c212ec8a 100644
--- a/src/layout/pad.rs
+++ b/src/layout/pad.rs
@@ -10,8 +10,12 @@ pub struct PadNode {
 }
 
 impl Layout for PadNode {
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
-        let regions = regions.map(|size| size - self.padding.resolve(size).size());
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>> {
+        let mut regions = regions.map(|size| size - self.padding.resolve(size).size());
 
         let mut frames = self.child.layout(ctx, &regions);
         for frame in &mut frames {
@@ -19,12 +23,23 @@ impl Layout for PadNode {
             let padding = self.padding.resolve(padded);
             let origin = Point::new(padding.left, padding.top);
 
-            frame.size = padded;
-            frame.baseline += origin.y;
+            frame.item.size = padded;
+            frame.item.baseline += origin.y;
 
-            for (point, _) in &mut frame.elements {
+            for (point, _) in &mut frame.item.elements {
                 *point += origin;
             }
+
+            frame.constraints.mutate(padding.size() * -1.0);
+
+            if self.padding.left.is_relative() || self.padding.right.is_relative() {
+                frame.constraints.base.horizontal = Some(regions.base.width);
+            }
+            if self.padding.top.is_relative() || self.padding.bottom.is_relative() {
+                frame.constraints.base.vertical = Some(regions.base.height);
+            }
+
+            regions.next();
         }
 
         frames
diff --git a/src/layout/par.rs b/src/layout/par.rs
index 40c36421..814f88ed 100644
--- a/src/layout/par.rs
+++ b/src/layout/par.rs
@@ -33,7 +33,11 @@ pub enum ParChild {
 }
 
 impl Layout for ParNode {
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>> {
         // Collect all text into one string used for BiDi analysis.
         let text = self.collect_text();
 
@@ -145,7 +149,7 @@ impl<'a> ParLayouter<'a> {
                 }
                 ParChild::Any(ref node, align) => {
                     let frame = node.layout(ctx, regions).remove(0);
-                    items.push(ParItem::Frame(frame, align));
+                    items.push(ParItem::Frame(frame.item, align));
                     ranges.push(range);
                 }
             }
@@ -161,7 +165,11 @@ impl<'a> ParLayouter<'a> {
     }
 
     /// Find first-fit line breaks and build the paragraph.
-    fn layout(self, ctx: &mut LayoutContext, regions: Regions) -> Vec<Frame> {
+    fn layout(
+        self,
+        ctx: &mut LayoutContext,
+        regions: Regions,
+    ) -> Vec<Constrained<Frame>> {
         let mut stack = LineStack::new(self.line_spacing, regions);
 
         // The current line attempt.
@@ -182,7 +190,20 @@ impl<'a> ParLayouter<'a> {
             // line cannot be broken up further.
             if !stack.regions.current.fits(line.size) {
                 if let Some((last_line, last_end)) = last.take() {
+                    if !stack.regions.current.width.fits(line.size.width) {
+                        stack.constraints.max.horizontal.set_min(line.size.width);
+                    }
+
+                    if !stack.regions.current.height.fits(line.size.height) {
+                        stack
+                            .constraints
+                            .max
+                            .vertical
+                            .set_min(stack.size.height + line.size.height);
+                    }
+
                     stack.push(last_line);
+                    stack.constraints.min.vertical = Some(stack.size.height);
                     start = last_end;
                     line = LineLayout::new(ctx, &self, start .. end);
                 }
@@ -192,6 +213,7 @@ impl<'a> ParLayouter<'a> {
             while !stack.regions.current.height.fits(line.size.height)
                 && !stack.regions.in_full_last()
             {
+                stack.constraints.max.vertical.set_min(line.size.height);
                 stack.finish_region(ctx);
             }
 
@@ -203,20 +225,25 @@ impl<'a> ParLayouter<'a> {
                 start = end;
                 last = None;
 
+                stack.constraints.min.vertical = Some(stack.size.height);
+
                 // If there is a trailing line break at the end of the
                 // paragraph, we want to force an empty line.
                 if mandatory && end == self.bidi.text.len() {
                     stack.push(LineLayout::new(ctx, &self, end .. end));
+                    stack.constraints.min.vertical = Some(stack.size.height);
                 }
             } else {
                 // Otherwise, the line fits both horizontally and vertically
                 // and we remember it.
+                stack.constraints.min.horizontal.set_max(line.size.width);
                 last = Some((line, end));
             }
         }
 
         if let Some((line, _)) = last {
             stack.push(line);
+            stack.constraints.min.vertical = Some(stack.size.height);
         }
 
         stack.finish(ctx)
@@ -279,7 +306,8 @@ struct LineStack<'a> {
     regions: Regions,
     size: Size,
     lines: Vec<LineLayout<'a>>,
-    finished: Vec<Frame>,
+    finished: Vec<Constrained<Frame>>,
+    constraints: Constraints,
 }
 
 impl<'a> LineStack<'a> {
@@ -287,6 +315,7 @@ impl<'a> LineStack<'a> {
     fn new(line_spacing: Length, regions: Regions) -> Self {
         Self {
             line_spacing,
+            constraints: Constraints::new(regions.expand),
             regions,
             size: Size::zero(),
             lines: vec![],
@@ -311,6 +340,7 @@ impl<'a> LineStack<'a> {
     fn finish_region(&mut self, ctx: &LayoutContext) {
         if self.regions.expand.horizontal {
             self.size.width = self.regions.current.width;
+            self.constraints.exact.horizontal = Some(self.regions.current.width);
         }
 
         let mut output = Frame::new(self.size, self.size.height);
@@ -330,13 +360,14 @@ impl<'a> LineStack<'a> {
             output.push_frame(pos, frame);
         }
 
+        self.finished.push(output.constrain(self.constraints));
         self.regions.next();
+        self.constraints = Constraints::new(self.regions.expand);
         self.size = Size::zero();
-        self.finished.push(output);
     }
 
     /// Finish the last region and return the built frames.
-    fn finish(mut self, ctx: &LayoutContext) -> Vec<Frame> {
+    fn finish(mut self, ctx: &LayoutContext) -> Vec<Constrained<Frame>> {
         self.finish_region(ctx);
         self.finished
     }
diff --git a/src/layout/stack.rs b/src/layout/stack.rs
index 8c47597b..f504d61e 100644
--- a/src/layout/stack.rs
+++ b/src/layout/stack.rs
@@ -28,7 +28,11 @@ pub enum StackChild {
 }
 
 impl Layout for StackNode {
-    fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Frame>> {
         StackLayouter::new(self, regions.clone()).layout(ctx)
     }
 }
@@ -56,11 +60,13 @@ struct StackLayouter<'a> {
     used: Gen<Length>,
     /// The alignment ruler for the current region.
     ruler: Align,
+    /// The constraints for the current region.
+    constraints: Constraints,
     /// Offset, alignment and frame for all children that fit into the current
     /// region. The exact positions are not known yet.
     frames: Vec<(Length, Gen<Align>, Frame)>,
     /// Finished frames for previous regions.
-    finished: Vec<Frame>,
+    finished: Vec<Constrained<Frame>>,
 }
 
 impl<'a> StackLayouter<'a> {
@@ -81,6 +87,7 @@ impl<'a> StackLayouter<'a> {
             stack,
             main,
             expand,
+            constraints: Constraints::new(regions.expand),
             regions,
             full,
             used: Gen::zero(),
@@ -91,13 +98,18 @@ impl<'a> StackLayouter<'a> {
     }
 
     /// Layout all children.
-    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Frame> {
+    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Frame>> {
         for child in &self.stack.children {
             match *child {
                 StackChild::Spacing(amount) => self.space(amount),
                 StackChild::Any(ref node, aligns) => {
-                    for frame in node.layout(ctx, &self.regions) {
-                        self.push_frame(frame, aligns);
+                    let nodes = node.layout(ctx, &self.regions);
+                    let len = nodes.len();
+                    for (i, frame) in nodes.into_iter().enumerate() {
+                        if i + 1 != len {
+                            self.constraints.exact = self.full.to_spec().map(Some);
+                        }
+                        self.push_frame(frame.item, aligns);
                     }
                 }
             }
@@ -109,7 +121,8 @@ impl<'a> StackLayouter<'a> {
 
     /// Add main-axis spacing into the current region.
     fn space(&mut self, amount: Length) {
-        // Cap the spacing to the remaining available space.
+        // 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.main);
         let capped = amount.min(*remaining);
 
@@ -132,6 +145,7 @@ impl<'a> StackLayouter<'a> {
         while !self.regions.current.get(self.main).fits(size.main)
             && !self.regions.in_full_last()
         {
+            self.constraints.max.get_mut(self.main).set_min(size.main);
             self.finish_region();
         }
 
@@ -156,12 +170,25 @@ impl<'a> StackLayouter<'a> {
         // Determine the stack's size dependening on whether the region is
         // fixed.
         let mut size = Size::new(
-            if expand.horizontal { self.full.width } else { used.width },
-            if expand.vertical { self.full.height } else { used.height },
+            if expand.horizontal {
+                self.constraints.exact.horizontal = Some(self.full.width);
+                self.full.width
+            } else {
+                self.constraints.min.horizontal = Some(used.width);
+                used.width
+            },
+            if expand.vertical {
+                self.constraints.exact.vertical = Some(self.full.height);
+                self.full.height
+            } else {
+                self.constraints.min.vertical = Some(used.height);
+                used.height
+            },
         );
 
         // Make sure the stack's size satisfies the aspect ratio.
         if let Some(aspect) = self.stack.aspect {
+            self.constraints.exact = self.regions.current.to_spec().map(Some);
             let width = size
                 .width
                 .max(aspect.into_inner() * size.height)
@@ -216,6 +243,7 @@ impl<'a> StackLayouter<'a> {
         self.full = self.regions.current;
         self.used = Gen::zero();
         self.ruler = Align::Start;
-        self.finished.push(output);
+        self.finished.push(output.constrain(self.constraints));
+        self.constraints = Constraints::new(self.regions.expand);
     }
 }
diff --git a/src/library/image.rs b/src/library/image.rs
index e926b955..7e8489e5 100644
--- a/src/library/image.rs
+++ b/src/library/image.rs
@@ -2,7 +2,7 @@ use ::image::GenericImageView;
 
 use super::*;
 use crate::image::ImageId;
-use crate::layout::{AnyNode, Element, Frame, Layout, LayoutContext, Regions};
+use crate::layout::{AnyNode, Constrained, Constraints, Element, Frame, Layout, LayoutContext, Regions};
 
 /// `image`: An image.
 ///
@@ -52,8 +52,11 @@ struct ImageNode {
 }
 
 impl Layout for ImageNode {
-    fn layout(&self, _: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
+    fn layout(&self, _: &mut LayoutContext, regions: &Regions) -> Vec<Constrained<Frame>> {
         let Regions { current, base, .. } = regions;
+        let mut constraints = Constraints::new(regions.expand);
+        constraints.set_base_using_linears(Spec::new(self.width, self.height), regions);
+
         let width = self.width.map(|w| w.resolve(base.width));
         let height = self.height.map(|w| w.resolve(base.height));
 
@@ -66,6 +69,8 @@ impl Layout for ImageNode {
             (Some(width), None) => Size::new(width, width / pixel_ratio),
             (None, Some(height)) => Size::new(height * pixel_ratio, height),
             (None, None) => {
+                constraints.exact = current.to_spec().map(Some);
+
                 let ratio = current.width / current.height;
                 if ratio < pixel_ratio && current.width.is_finite() {
                     Size::new(current.width, current.width / pixel_ratio)
@@ -81,7 +86,7 @@ impl Layout for ImageNode {
 
         let mut frame = Frame::new(size, size.height);
         frame.push(Point::zero(), Element::Image(self.id, size));
-        vec![frame]
+        vec![frame.constrain(constraints)]
     }
 }