Refactor layouting a bit

Notably:
- Handle aspect ratio in fixed node
- Inline constraint inflation into pad node

12 files changed, 278 insertions, 272 deletions

diff --git a/src/layout/background.rs b/src/layout/background.rs
index 76ce431b..793782fd 100644
--- a/src/layout/background.rs
+++ b/src/layout/background.rs
@@ -26,9 +26,8 @@ impl Layout for BackgroundNode {
         regions: &Regions,
     ) -> Vec<Constrained<Rc<Frame>>> {
         let mut frames = self.child.layout(ctx, regions);
-        for frame in &mut frames {
-            let mut new = Frame::new(frame.size, frame.baseline);
 
+        for Constrained { item: frame, .. } in &mut frames {
             let (point, geometry) = match self.shape {
                 BackgroundShape::Rect => (Point::zero(), Geometry::Rect(frame.size)),
                 BackgroundShape::Ellipse => {
@@ -36,11 +35,15 @@ impl Layout for BackgroundNode {
                 }
             };
 
-            let prev = std::mem::take(&mut frame.item);
+            // Create a new frame with the background geometry and the child's
+            // frame.
+            let empty = Frame::new(frame.size, frame.baseline);
+            let prev = std::mem::replace(frame, Rc::new(empty));
+            let new = Rc::make_mut(frame);
             new.push(point, Element::Geometry(geometry, self.fill));
             new.push_frame(Point::zero(), prev);
-            *Rc::make_mut(&mut frame.item) = new;
         }
+
         frames
     }
 }
diff --git a/src/layout/constraints.rs b/src/layout/constraints.rs
index d13433ec..1a26daeb 100644
--- a/src/layout/constraints.rs
+++ b/src/layout/constraints.rs
@@ -1,7 +1,5 @@
 use std::ops::Deref;
 
-use crate::util::OptionExt;
-
 use super::*;
 
 /// Carries an item that is only valid in certain regions and the constraints
@@ -61,36 +59,14 @@ impl Constraints {
             && base.eq_by(&self.base, |x, y| y.map_or(true, |y| x.approx_eq(y)))
     }
 
-    /// 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,
-    ) {
+    /// Set the appropriate base constraints for linear width and height sizing.
+    pub fn set_base_if_linear(&mut self, base: Size, sizing: Spec<Option<Linear>>) {
         // 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 sizing.horizontal.map_or(false, |l| l.is_relative()) {
+            self.base.horizontal = Some(base.width);
         }
-        if size.vertical.map_or(false, |l| l.is_relative()) {
-            self.base.vertical = Some(regions.base.height);
+        if sizing.vertical.map_or(false, |l| l.is_relative()) {
+            self.base.vertical = Some(base.height);
         }
     }
-
-    /// Changes all constraints by adding the `size` to them if they are `Some`.
-    pub fn inflate(&mut self, size: Size, regions: &Regions) {
-        for spec in [&mut self.min, &mut self.max] {
-            if let Some(horizontal) = spec.horizontal.as_mut() {
-                *horizontal += size.width;
-            }
-            if let Some(vertical) = spec.vertical.as_mut() {
-                *vertical += size.height;
-            }
-        }
-
-        self.exact.horizontal.and_set(Some(regions.current.width));
-        self.exact.vertical.and_set(Some(regions.current.height));
-        self.base.horizontal.and_set(Some(regions.base.width));
-        self.base.vertical.and_set(Some(regions.base.height));
-    }
 }
diff --git a/src/layout/fixed.rs b/src/layout/fixed.rs
index 9fa2af8a..7f292f14 100644
--- a/src/layout/fixed.rs
+++ b/src/layout/fixed.rs
@@ -1,3 +1,5 @@
+use decorum::N64;
+
 use super::*;
 
 /// A node that can fix its child's width and height.
@@ -8,6 +10,10 @@ pub struct FixedNode {
     pub width: Option<Linear>,
     /// The fixed height, if any.
     pub height: Option<Linear>,
+    /// The fixed aspect ratio between width and height.
+    ///
+    /// The resulting frame will satisfy `width = aspect * height`.
+    pub aspect: Option<N64>,
     /// The child node whose size to fix.
     pub child: LayoutNode,
 }
@@ -16,33 +22,74 @@ impl Layout for FixedNode {
     fn layout(
         &self,
         ctx: &mut LayoutContext,
-        regions: &Regions,
+        &Regions { current, base, expand, .. }: &Regions,
     ) -> Vec<Constrained<Rc<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);
+        // Fill in width or height if aspect ratio and the other is given.
+        let aspect = self.aspect.map(N64::into_inner);
+        let width = self.width.or(self.height.zip(aspect).map(|(h, a)| a * h));
+        let height = self.height.or(self.width.zip(aspect).map(|(w, a)| w / a));
 
-        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)),
-        );
+        // Prepare constraints.
+        let mut constraints = Constraints::new(expand);
+        constraints.set_base_if_linear(base, Spec::new(width, height));
 
-        // If one dimension was not specified, the `current` size needs to remain static.
-        if self.width.is_none() {
+        // If the size for one axis isn't specified, the `current` size along
+        // that axis needs to remain the same for the result to be reusable.
+        if width.is_none() {
             constraints.exact.horizontal = Some(current.width);
         }
-        if self.height.is_none() {
+
+        if 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);
+        // Resolve the linears based on the current width and height.
+        let mut size = Size::new(
+            width.map_or(current.width, |w| w.resolve(base.width)),
+            height.map_or(current.height, |h| h.resolve(base.height)),
+        );
+
+        // If width or height aren't set for an axis, the base should be
+        // inherited from the parent for that axis.
+        let base = Size::new(
+            width.map_or(base.width, |_| size.width),
+            height.map_or(base.height, |_| size.height),
+        );
+
+        // Handle the aspect ratio.
+        if let Some(aspect) = aspect {
+            constraints.exact = current.to_spec().map(Some);
+            constraints.min = Spec::splat(None);
+            constraints.max = Spec::splat(None);
+
+            let width = size.width.min(aspect * size.height);
+            size = Size::new(width, width / aspect);
+        }
+
+        // If width or height are fixed, the child should fill the available
+        // space along that axis.
+        let expand = Spec::new(width.is_some(), height.is_some());
+
+        // Layout the child.
+        let mut regions = Regions::one(size, base, expand);
         let mut frames = self.child.layout(ctx, &regions);
 
-        if let Some(frame) = frames.first_mut() {
-            frame.constraints = constraints;
+        // If we have an aspect ratio and the child is content-sized, we need to
+        // relayout with expansion.
+        if let Some(aspect) = aspect {
+            if width.is_none() && height.is_none() {
+                let needed = frames[0].size.cap(size);
+                let width = needed.width.max(aspect * needed.height);
+                regions.current = Size::new(width, width / aspect);
+                regions.expand = Spec::splat(true);
+                frames = self.child.layout(ctx, &regions);
+            }
         }
 
+        // Overwrite the child's constraints with ours.
+        frames[0].constraints = constraints;
+        assert_eq!(frames.len(), 1);
+
         frames
     }
 }
diff --git a/src/layout/frame.rs b/src/layout/frame.rs
index 2e3b838e..0c307dd4 100644
--- a/src/layout/frame.rs
+++ b/src/layout/frame.rs
@@ -19,11 +19,13 @@ pub struct Frame {
     children: Vec<(Point, Child)>,
 }
 
-/// A frame can contain multiple children: elements or other frames, complete
-/// with their children.
+/// A frame can contain two different kinds of children: a leaf element or a
+/// nested frame.
 #[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
 enum Child {
+    /// A leaf node in the frame tree.
     Element(Element),
+    /// An interior node.
     Frame(Rc<Frame>),
 }
 
diff --git a/src/layout/grid.rs b/src/layout/grid.rs
index 0a189513..ed408ab8 100644
--- a/src/layout/grid.rs
+++ b/src/layout/grid.rs
@@ -263,7 +263,7 @@ impl<'a> GridLayouter<'a> {
             let mut resolved = Length::zero();
             for node in (0 .. self.rows.len()).filter_map(|y| self.cell(x, y)) {
                 let size = Gen::new(available, Length::inf()).to_size(self.main);
-                let regions = Regions::one(size, Spec::splat(false));
+                let regions = Regions::one(size, size, Spec::splat(false));
                 let frame = node.layout(ctx, &regions).remove(0);
                 resolved.set_max(frame.size.get(self.cross));
             }
@@ -405,7 +405,7 @@ impl<'a> GridLayouter<'a> {
         for (x, &rcol) in self.rcols.iter().enumerate() {
             if let Some(node) = self.cell(x, y) {
                 let size = Gen::new(rcol, length).to_size(self.main);
-                let regions = Regions::one(size, Spec::splat(true));
+                let regions = Regions::one(size, size, Spec::splat(true));
                 let frame = node.layout(ctx, &regions).remove(0);
                 output.push_frame(pos.to_point(self.main), frame.item);
             }
@@ -432,7 +432,8 @@ impl<'a> GridLayouter<'a> {
             .collect();
 
         // Prepare regions.
-        let mut regions = Regions::one(self.to_size(first), Spec::splat(true));
+        let size = self.to_size(first);
+        let mut regions = Regions::one(size, size, Spec::splat(true));
         regions.backlog = rest.iter().rev().map(|&v| self.to_size(v)).collect();
 
         // Layout the row.
diff --git a/src/layout/image.rs b/src/layout/image.rs
index 2c20642b..02a907f5 100644
--- a/src/layout/image.rs
+++ b/src/layout/image.rs
@@ -19,11 +19,10 @@ impl Layout for ImageNode {
     fn layout(
         &self,
         ctx: &mut LayoutContext,
-        regions: &Regions,
+        &Regions { current, base, expand, .. }: &Regions,
     ) -> Vec<Constrained<Rc<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 mut constraints = Constraints::new(expand);
+        constraints.set_base_if_linear(base, Spec::new(self.width, self.height));
 
         let width = self.width.map(|w| w.resolve(base.width));
         let height = self.height.map(|w| w.resolve(base.height));
diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs
index 9a788c91..0fc668c3 100644
--- a/src/layout/incremental.rs
+++ b/src/layout/incremental.rs
@@ -6,7 +6,6 @@ use itertools::Itertools;
 
 use super::*;
 
-const CACHE_SIZE: usize = 20;
 const TEMP_LEN: usize = 5;
 const TEMP_LAST: usize = TEMP_LEN - 1;
 
@@ -23,22 +22,26 @@ pub struct LayoutCache {
     /// In how many compilations this cache has been used.
     age: usize,
     /// What cache eviction policy should be used.
-    policy: EvictionStrategy,
+    policy: EvictionPolicy,
+    /// The maximum number of entries this cache should have. Can be exceeded if
+    /// there are more must-keep entries.
+    max_size: usize,
 }
 
 impl LayoutCache {
     /// Create a new, empty layout cache.
-    pub fn new(policy: EvictionStrategy) -> Self {
+    pub fn new(policy: EvictionPolicy, max_size: usize) -> Self {
         Self {
             frames: HashMap::default(),
             age: 0,
             policy,
+            max_size,
         }
     }
 
     /// Whether the cache is empty.
     pub fn is_empty(&self) -> bool {
-        self.len() == 0
+        self.frames.values().all(|entry| entry.is_empty())
     }
 
     /// Amount of items in the cache.
@@ -108,38 +111,34 @@ impl LayoutCache {
             }
 
             let last = entry.temperature[TEMP_LAST];
-
             for i in (1 .. TEMP_LEN).rev() {
                 entry.temperature[i] = entry.temperature[i - 1];
             }
 
             entry.temperature[0] = 0;
             entry.temperature[TEMP_LAST] += last;
-
             entry.age += 1;
         }
 
         self.evict();
-
         self.frames.retain(|_, v| !v.is_empty());
     }
 
+    /// Evict the cache according to the policy.
     fn evict(&mut self) {
         let len = self.len();
-        if len <= CACHE_SIZE {
+        if len <= self.max_size {
             return;
         }
 
         match self.policy {
-            EvictionStrategy::LeastRecentlyUsed => {
+            EvictionPolicy::LeastRecentlyUsed => {
                 // We find the element with the largest cooldown that cannot fit
                 // anymore.
                 let threshold = self
-                    .frames
-                    .values()
-                    .flatten()
+                    .entries()
                     .map(|f| Reverse(f.cooldown()))
-                    .k_smallest(len - CACHE_SIZE)
+                    .k_smallest(len - self.max_size)
                     .last()
                     .unwrap()
                     .0;
@@ -148,13 +147,11 @@ impl LayoutCache {
                     entries.retain(|e| e.cooldown() < threshold);
                 }
             }
-            EvictionStrategy::LeastFrequentlyUsed => {
+            EvictionPolicy::LeastFrequentlyUsed => {
                 let threshold = self
-                    .frames
-                    .values()
-                    .flatten()
+                    .entries()
                     .map(|f| N32::from(f.hits() as f32 / f.age() as f32))
-                    .k_smallest(len - CACHE_SIZE)
+                    .k_smallest(len - self.max_size)
                     .last()
                     .unwrap();
 
@@ -164,30 +161,23 @@ impl LayoutCache {
                     });
                 }
             }
-            EvictionStrategy::Random => {
+            EvictionPolicy::Random => {
                 // Fraction of items that should be kept.
-                let threshold = CACHE_SIZE as f32 / len as f32;
+                let threshold = self.max_size as f32 / len as f32;
                 for entries in self.frames.values_mut() {
                     entries.retain(|_| rand::random::<f32>() > threshold);
                 }
             }
-            EvictionStrategy::Patterns => {
-                let kept = self
-                    .frames
-                    .values()
-                    .flatten()
-                    .filter(|f| f.properties().must_keep())
-                    .count();
-
-                let remaining_capacity = CACHE_SIZE - kept.min(CACHE_SIZE);
+            EvictionPolicy::Patterns => {
+                let kept = self.entries().filter(|f| f.properties().must_keep()).count();
+
+                let remaining_capacity = self.max_size - kept.min(self.max_size);
                 if len - kept <= remaining_capacity {
                     return;
                 }
 
                 let threshold = self
-                    .frames
-                    .values()
-                    .flatten()
+                    .entries()
                     .filter(|f| !f.properties().must_keep())
                     .map(|f| N32::from(f.hits() as f32 / f.age() as f32))
                     .k_smallest((len - kept) - remaining_capacity)
@@ -201,7 +191,7 @@ impl LayoutCache {
                     });
                 }
             }
-            EvictionStrategy::None => {}
+            EvictionPolicy::None => {}
         }
     }
 }
@@ -267,6 +257,11 @@ impl FramesEntry {
         self.temperature[0] != 0
     }
 
+    /// Get the total amount of hits over the lifetime of this item.
+    pub fn hits(&self) -> usize {
+        self.temperature.iter().sum()
+    }
+
     /// The amount of consecutive cycles in which this item has not been used.
     pub fn cooldown(&self) -> usize {
         let mut cycle = 0;
@@ -279,11 +274,7 @@ impl FramesEntry {
         cycle
     }
 
-    /// Get the total amount of hits over the lifetime of this item.
-    pub fn hits(&self) -> usize {
-        self.temperature.iter().sum()
-    }
-
+    /// Properties that describe how this entry's temperature evolved.
     pub fn properties(&self) -> PatternProperties {
         let mut all_zeros = true;
         let mut multi_use = false;
@@ -332,15 +323,13 @@ impl FramesEntry {
             all_zeros = false;
         }
 
-        decreasing = decreasing && !all_same;
-
         PatternProperties {
             mature: self.age >= TEMP_LEN,
             hit: self.temperature[0] >= 1,
             top_level: self.level == 0,
             all_zeros,
             multi_use,
-            decreasing,
+            decreasing: decreasing && !all_same,
             sparse,
             abandoned,
         }
@@ -349,7 +338,7 @@ impl FramesEntry {
 
 /// Cache eviction strategies.
 #[derive(Debug, Copy, Clone, Eq, PartialEq)]
-pub enum EvictionStrategy {
+pub enum EvictionPolicy {
     /// Evict the least recently used item.
     LeastRecentlyUsed,
     /// Evict the least frequently used item.
@@ -362,7 +351,7 @@ pub enum EvictionStrategy {
     None,
 }
 
-impl Default for EvictionStrategy {
+impl Default for EvictionPolicy {
     fn default() -> Self {
         Self::Patterns
     }
@@ -415,23 +404,23 @@ impl PatternProperties {
 mod tests {
     use super::*;
 
-    fn empty_frame() -> Vec<Constrained<Rc<Frame>>> {
+    fn empty_frames() -> Vec<Constrained<Rc<Frame>>> {
         vec![Constrained {
             item: Rc::new(Frame::default()),
             constraints: Constraints::new(Spec::splat(false)),
         }]
     }
 
-    fn zero_region() -> Regions {
-        Regions::one(Size::zero(), Spec::splat(false))
+    fn zero_regions() -> Regions {
+        Regions::one(Size::zero(), Size::zero(), Spec::splat(false))
     }
 
     #[test]
-    fn test_temperature() {
-        let mut cache = LayoutCache::new(EvictionStrategy::None);
-        let zero_region = zero_region();
-        cache.policy = EvictionStrategy::None;
-        cache.insert(0, empty_frame(), 0);
+    fn test_incremental_temperature() {
+        let mut cache = LayoutCache::new(EvictionPolicy::None, 20);
+        let regions = zero_regions();
+        cache.policy = EvictionPolicy::None;
+        cache.insert(0, empty_frames(), 0);
 
         let entry = cache.frames.get(&0).unwrap().first().unwrap();
         assert_eq!(entry.age(), 1);
@@ -439,7 +428,7 @@ mod tests {
         assert_eq!(entry.used_cycles, 0);
         assert_eq!(entry.level, 0);
 
-        cache.get(0, &zero_region).unwrap();
+        cache.get(0, &regions).unwrap();
         let entry = cache.frames.get(&0).unwrap().first().unwrap();
         assert_eq!(entry.age(), 1);
         assert_eq!(entry.temperature, [1, 0, 0, 0, 0]);
@@ -450,7 +439,7 @@ mod tests {
         assert_eq!(entry.temperature, [0, 1, 0, 0, 0]);
         assert_eq!(entry.used_cycles, 1);
 
-        cache.get(0, &zero_region).unwrap();
+        cache.get(0, &regions).unwrap();
         for _ in 0 .. 4 {
             cache.turnaround();
         }
@@ -462,10 +451,10 @@ mod tests {
     }
 
     #[test]
-    fn test_properties() {
-        let mut cache = LayoutCache::new(EvictionStrategy::None);
-        cache.policy = EvictionStrategy::None;
-        cache.insert(0, empty_frame(), 1);
+    fn test_incremental_properties() {
+        let mut cache = LayoutCache::new(EvictionPolicy::None, 20);
+        cache.policy = EvictionPolicy::None;
+        cache.insert(0, empty_frames(), 1);
 
         let props = cache.frames.get(&0).unwrap().first().unwrap().properties();
         assert_eq!(props.top_level, false);
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 9700004d..96bd7e7e 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -10,6 +10,7 @@ mod image;
 mod incremental;
 mod pad;
 mod par;
+mod regions;
 mod shaping;
 mod stack;
 mod tree;
@@ -24,13 +25,11 @@ pub use grid::*;
 pub use incremental::*;
 pub use pad::*;
 pub use par::*;
+pub use regions::*;
 pub use shaping::*;
 pub use stack::*;
 pub use tree::*;
 
-use std::hash::Hash;
-#[cfg(feature = "layout-cache")]
-use std::hash::Hasher;
 use std::rc::Rc;
 
 use crate::font::FontStore;
@@ -45,16 +44,6 @@ pub fn layout(ctx: &mut Context, tree: &LayoutTree) -> Vec<Rc<Frame>> {
     tree.layout(&mut ctx)
 }
 
-/// Layout a node.
-pub trait Layout {
-    /// Layout the node into the given regions.
-    fn layout(
-        &self,
-        ctx: &mut LayoutContext,
-        regions: &Regions,
-    ) -> Vec<Constrained<Rc<Frame>>>;
-}
-
 /// The context for layouting.
 pub struct LayoutContext<'a> {
     /// Stores parsed font faces.
@@ -83,94 +72,12 @@ impl<'a> LayoutContext<'a> {
     }
 }
 
-/// A sequence of regions to layout into.
-#[derive(Debug, Clone, Eq, PartialEq)]
-pub struct Regions {
-    /// The remaining size of the current region.
-    pub current: Size,
-    /// The base size for relative sizing.
-    pub base: Size,
-    /// A stack of followup regions.
-    ///
-    /// Note that this is a stack and not a queue! The size of the next region is
-    /// `backlog.last()`.
-    pub backlog: Vec<Size>,
-    /// The final region that is repeated once the backlog is drained.
-    pub last: Option<Size>,
-    /// Whether nodes should expand to fill the regions instead of shrinking to
-    /// fit the content.
-    ///
-    /// This property is only handled by nodes that have the ability to control
-    /// their own size.
-    pub expand: Spec<bool>,
-}
-
-impl Regions {
-    /// Create a new region sequence with exactly one region.
-    pub fn one(size: Size, expand: Spec<bool>) -> Self {
-        Self {
-            current: size,
-            base: size,
-            backlog: vec![],
-            last: None,
-            expand,
-        }
-    }
-
-    /// Create a new sequence of same-size regions that repeats indefinitely.
-    pub fn repeat(size: Size, expand: Spec<bool>) -> Self {
-        Self {
-            current: size,
-            base: size,
-            backlog: vec![],
-            last: Some(size),
-            expand,
-        }
-    }
-
-    /// Create new regions where all sizes are mapped with `f`.
-    pub fn map<F>(&self, mut f: F) -> Self
-    where
-        F: FnMut(Size) -> Size,
-    {
-        let mut regions = self.clone();
-        regions.mutate(|s| *s = f(*s));
-        regions
-    }
-
-    /// Whether `current` is a fully sized (untouched) copy of the last region.
-    ///
-    /// If this is true, calling `next()` will have no effect.
-    pub fn in_full_last(&self) -> bool {
-        self.backlog.is_empty() && self.last.map_or(true, |size| self.current == size)
-    }
-
-    /// An iterator that returns pairs of `(current, base)` that are equivalent
-    /// to what would be produced by calling [`next()`](Self::next) repeatedly
-    /// until all regions are exhausted.
-    pub fn iter(&self) -> impl Iterator<Item = (Size, Size)> + '_ {
-        let first = std::iter::once((self.current, self.base));
-        let backlog = self.backlog.iter().rev();
-        let last = self.last.iter().cycle();
-        first.chain(backlog.chain(last).map(|&s| (s, s)))
-    }
-
-    /// Advance to the next region if there is any.
-    pub fn next(&mut self) {
-        if let Some(size) = self.backlog.pop().or(self.last) {
-            self.current = size;
-            self.base = size;
-        }
-    }
-
-    /// Mutate all contained sizes in place.
-    pub fn mutate<F>(&mut self, mut f: F)
-    where
-        F: FnMut(&mut Size),
-    {
-        f(&mut self.current);
-        f(&mut self.base);
-        self.last.as_mut().map(|x| f(x));
-        self.backlog.iter_mut().for_each(f);
-    }
+/// Layout a node.
+pub trait Layout {
+    /// Layout the node into the given regions.
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Rc<Frame>>>;
 }
diff --git a/src/layout/pad.rs b/src/layout/pad.rs
index 31571bb3..51025e3c 100644
--- a/src/layout/pad.rs
+++ b/src/layout/pad.rs
@@ -16,51 +16,64 @@ impl Layout for PadNode {
         ctx: &mut LayoutContext,
         regions: &Regions,
     ) -> Vec<Constrained<Rc<Frame>>> {
-        let mut regions = regions.clone();
         let mut frames = self.child.layout(
             ctx,
             &regions.map(|size| size - self.padding.resolve(size).size()),
         );
 
-        for frame in &mut frames {
-            let padded = solve(self.padding, frame.size);
+        for (Constrained { item: frame, constraints }, (current, base)) in
+            frames.iter_mut().zip(regions.iter())
+        {
+            fn solve_axis(length: Length, padding: Linear) -> Length {
+                (length + padding.abs) / (1.0 - padding.rel.get())
+            }
+
+            // Solve for the size `padded` that satisfies (approximately):
+            // `padded - padding.resolve(padded).size() == size`
+            let padded = Size::new(
+                solve_axis(frame.size.width, self.padding.left + self.padding.right),
+                solve_axis(frame.size.height, self.padding.top + self.padding.bottom),
+            );
+
             let padding = self.padding.resolve(padded);
             let origin = Point::new(padding.left, padding.top);
 
-            let mut new = Frame::new(padded, frame.baseline + origin.y);
-            let prev = std::mem::take(&mut frame.item);
-            new.push_frame(origin, prev);
+            // Inflate min and max contraints by the padding.
+            for spec in [&mut constraints.min, &mut constraints.max] {
+                if let Some(horizontal) = spec.horizontal.as_mut() {
+                    *horizontal += padding.size().width;
+                }
+                if let Some(vertical) = spec.vertical.as_mut() {
+                    *vertical += padding.size().height;
+                }
+            }
 
-            frame.constraints.inflate(padding.size(), &regions);
+            // Set exact and base constraints if the child had them.
+            constraints.exact.horizontal.and_set(Some(current.width));
+            constraints.exact.vertical.and_set(Some(current.height));
+            constraints.base.horizontal.and_set(Some(base.width));
+            constraints.base.vertical.and_set(Some(base.height));
 
+            // Also set base constraints if the padding is relative.
             if self.padding.left.is_relative() || self.padding.right.is_relative() {
-                frame.constraints.base.horizontal = Some(regions.base.width);
+                constraints.base.horizontal = Some(base.width);
             }
+
             if self.padding.top.is_relative() || self.padding.bottom.is_relative() {
-                frame.constraints.base.vertical = Some(regions.base.height);
+                constraints.base.vertical = Some(base.height);
             }
 
-            regions.next();
-            *Rc::make_mut(&mut frame.item) = new;
+            // Create a new larger frame and place the child's frame inside it.
+            let empty = Frame::new(padded, frame.baseline + origin.y);
+            let prev = std::mem::replace(frame, Rc::new(empty));
+            let new = Rc::make_mut(frame);
+            new.push_frame(origin, prev);
         }
 
         frames
     }
 }
 
-/// Solve for the size `padded` that satisfies (approximately):
-/// `padded - padding.resolve(padded).size() == size`
-fn solve(padding: Sides<Linear>, size: Size) -> Size {
-    fn solve_axis(length: Length, padding: Linear) -> Length {
-        (length + padding.abs) / (1.0 - padding.rel.get())
-    }
-
-    Size::new(
-        solve_axis(size.width, padding.left + padding.right),
-        solve_axis(size.height, padding.top + padding.bottom),
-    )
-}
-
 impl From<PadNode> for LayoutNode {
     fn from(pad: PadNode) -> Self {
         Self::new(pad)
diff --git a/src/layout/regions.rs b/src/layout/regions.rs
new file mode 100644
index 00000000..daecca45
--- /dev/null
+++ b/src/layout/regions.rs
@@ -0,0 +1,93 @@
+use crate::geom::{Size, Spec};
+
+/// A sequence of regions to layout into.
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct Regions {
+    /// The remaining size of the current region.
+    pub current: Size,
+    /// The base size for relative sizing.
+    pub base: Size,
+    /// A stack of followup regions.
+    ///
+    /// Note that this is a stack and not a queue! The size of the next region is
+    /// `backlog.last()`.
+    pub backlog: Vec<Size>,
+    /// The final region that is repeated once the backlog is drained.
+    pub last: Option<Size>,
+    /// Whether nodes should expand to fill the regions instead of shrinking to
+    /// fit the content.
+    ///
+    /// This property is only handled by nodes that have the ability to control
+    /// their own size.
+    pub expand: Spec<bool>,
+}
+
+impl Regions {
+    /// Create a new region sequence with exactly one region.
+    pub fn one(size: Size, base: Size, expand: Spec<bool>) -> Self {
+        Self {
+            current: size,
+            base,
+            backlog: vec![],
+            last: None,
+            expand,
+        }
+    }
+
+    /// Create a new sequence of same-size regions that repeats indefinitely.
+    pub fn repeat(size: Size, base: Size, expand: Spec<bool>) -> Self {
+        Self {
+            current: size,
+            base,
+            backlog: vec![],
+            last: Some(size),
+            expand,
+        }
+    }
+
+    /// Create new regions where all sizes are mapped with `f`.
+    pub fn map<F>(&self, mut f: F) -> Self
+    where
+        F: FnMut(Size) -> Size,
+    {
+        let mut regions = self.clone();
+        regions.mutate(|s| *s = f(*s));
+        regions
+    }
+
+    /// Whether `current` is a fully sized (untouched) copy of the last region.
+    ///
+    /// If this is true, calling `next()` will have no effect.
+    pub fn in_full_last(&self) -> bool {
+        self.backlog.is_empty() && self.last.map_or(true, |size| self.current == size)
+    }
+
+    /// An iterator that returns pairs of `(current, base)` that are equivalent
+    /// to what would be produced by calling [`next()`](Self::next) repeatedly
+    /// until all regions are exhausted.
+    pub fn iter(&self) -> impl Iterator<Item = (Size, Size)> + '_ {
+        let first = std::iter::once((self.current, self.base));
+        let backlog = self.backlog.iter().rev();
+        let last = self.last.iter().cycle();
+        first.chain(backlog.chain(last).map(|&s| (s, s)))
+    }
+
+    /// Advance to the next region if there is any.
+    pub fn next(&mut self) {
+        if let Some(size) = self.backlog.pop().or(self.last) {
+            self.current = size;
+            self.base = size;
+        }
+    }
+
+    /// Mutate all contained sizes in place.
+    pub fn mutate<F>(&mut self, mut f: F)
+    where
+        F: FnMut(&mut Size),
+    {
+        f(&mut self.current);
+        f(&mut self.base);
+        self.last.as_mut().map(|x| f(x));
+        self.backlog.iter_mut().for_each(f);
+    }
+}
diff --git a/src/layout/stack.rs b/src/layout/stack.rs
index 504c64aa..51d17807 100644
--- a/src/layout/stack.rs
+++ b/src/layout/stack.rs
@@ -1,5 +1,3 @@
-use decorum::N64;
-
 use super::*;
 
 /// A node that stacks its children.
@@ -11,10 +9,6 @@ pub struct StackNode {
     /// The children are stacked along the `main` direction. The `cross`
     /// direction is required for aligning the children.
     pub dirs: Gen<Dir>,
-    /// The fixed aspect ratio between width and height, if any.
-    ///
-    /// The resulting frames will satisfy `width = aspect * height`.
-    pub aspect: Option<N64>,
     /// The nodes to be stacked.
     pub children: Vec<StackChild>,
 }
@@ -83,10 +77,6 @@ impl<'a> StackLayouter<'a> {
         // Disable expansion on the main axis for children.
         regions.expand.set(main, false);
 
-        if let Some(aspect) = stack.aspect {
-            regions.current = regions.current.with_aspect(aspect.into_inner());
-        }
-
         Self {
             stack,
             main,
@@ -161,6 +151,7 @@ impl<'a> StackLayouter<'a> {
                 .max
                 .get_mut(self.main)
                 .set_min(self.used.main + size.main);
+
             self.finish_region();
         }
 
@@ -184,7 +175,7 @@ impl<'a> StackLayouter<'a> {
 
         // Determine the stack's size dependening on whether the region is
         // fixed.
-        let mut size = Size::new(
+        let size = Size::new(
             if expand.horizontal {
                 self.constraints.exact.horizontal = Some(self.full.width);
                 self.full.width
@@ -201,20 +192,6 @@ impl<'a> StackLayouter<'a> {
             },
         );
 
-        // Make sure the stack's size satisfies the aspect ratio.
-        if let Some(aspect) = self.stack.aspect {
-            self.constraints.exact = self.full.to_spec().map(Some);
-            self.constraints.min = Spec::splat(None);
-            self.constraints.max = Spec::splat(None);
-            let width = size
-                .width
-                .max(aspect.into_inner() * size.height)
-                .min(self.full.width)
-                .min(aspect.into_inner() * self.full.height);
-
-            size = Size::new(width, width / aspect.into_inner());
-        }
-
         if self.overflowing {
             self.constraints.min.vertical = None;
             self.constraints.max.vertical = None;
@@ -259,10 +236,6 @@ impl<'a> StackLayouter<'a> {
         }
 
         self.regions.next();
-        if let Some(aspect) = self.stack.aspect {
-            self.regions.current = self.regions.current.with_aspect(aspect.into_inner());
-        }
-
         self.full = self.regions.current;
         self.used = Gen::zero();
         self.ruler = Align::Start;
diff --git a/src/layout/tree.rs b/src/layout/tree.rs
index 4b21e05c..1899a4d2 100644
--- a/src/layout/tree.rs
+++ b/src/layout/tree.rs
@@ -4,6 +4,9 @@ use std::any::Any;
 use std::fmt::{self, Debug, Formatter};
 
 #[cfg(feature = "layout-cache")]
+use std::hash::{Hash, Hasher};
+
+#[cfg(feature = "layout-cache")]
 use fxhash::FxHasher64;
 
 /// A tree of layout nodes.
@@ -37,7 +40,7 @@ impl PageRun {
         // that axis.
         let Size { width, height } = self.size;
         let expand = Spec::new(width.is_finite(), height.is_finite());
-        let regions = Regions::repeat(self.size, expand);
+        let regions = Regions::repeat(self.size, self.size, expand);
         self.child.layout(ctx, &regions).into_iter().map(|c| c.item).collect()
     }
 }