Refactor grid row layout

7 files changed, 464 insertions, 523 deletions

diff --git a/src/geom/length.rs b/src/geom/length.rs
index 21843d3e..ecfe5616 100644
--- a/src/geom/length.rs
+++ b/src/geom/length.rs
@@ -18,6 +18,11 @@ impl Length {
         Self { raw: N64::from(0.0) }
     }
 
+    /// The inifinite length.
+    pub fn inf() -> Self {
+        Self { raw: N64::from(f64::INFINITY) }
+    }
+
     /// Create a length from a number of points.
     pub fn pt(pt: f64) -> Self {
         Self::with_unit(pt, LengthUnit::Pt)
@@ -203,6 +208,12 @@ impl Sum for Length {
     }
 }
 
+impl<'a> Sum<&'a Length> for Length {
+    fn sum<I: Iterator<Item = &'a Length>>(iter: I) -> Self {
+        iter.copied().fold(Length::zero(), Add::add)
+    }
+}
+
 /// Different units of length measurement.
 #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
 pub enum LengthUnit {
diff --git a/src/geom/size.rs b/src/geom/size.rs
index 1c411fb3..4b94d0ae 100644
--- a/src/geom/size.rs
+++ b/src/geom/size.rs
@@ -57,6 +57,13 @@ impl Size {
             SpecAxis::Vertical => Gen::new(self.width, self.height),
         }
     }
+
+    /// Find the largest contained size that satisfies the given `aspect` ratio.
+    pub fn with_aspect(self, aspect: f64) -> Self {
+        let width = self.width.min(aspect * self.height);
+        let height = width / aspect;
+        Size::new(width, height)
+    }
 }
 
 impl Get<SpecAxis> for Size {
diff --git a/src/layout/frame.rs b/src/layout/frame.rs
index 119aeea6..55f7f99a 100644
--- a/src/layout/frame.rs
+++ b/src/layout/frame.rs
@@ -6,7 +6,7 @@ use crate::image::ImageId;
 use serde::{Deserialize, Serialize};
 
 /// A finished layout with elements at fixed positions.
-#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
+#[derive(Default, Debug, Clone, PartialEq, Serialize, Deserialize)]
 pub struct Frame {
     /// The size of the frame.
     pub size: Size,
@@ -31,8 +31,12 @@ impl Frame {
     /// Add all elements of another frame, placing them relative to the given
     /// position.
     pub fn push_frame(&mut self, pos: Point, subframe: Self) {
-        for (subpos, element) in subframe.elements {
-            self.push(pos + subpos, element);
+        if pos == Point::zero() && self.elements.is_empty() {
+            self.elements = subframe.elements;
+        } else {
+            for (subpos, element) in subframe.elements {
+                self.push(pos + subpos, element);
+            }
         }
     }
 }
diff --git a/src/layout/grid.rs b/src/layout/grid.rs
index 6ea99476..52e07d0d 100644
--- a/src/layout/grid.rs
+++ b/src/layout/grid.rs
@@ -16,9 +16,27 @@ pub struct GridNode {
     pub children: Vec<AnyNode>,
 }
 
+/// Defines how to size a grid cell along an axis.
+#[derive(Debug, Copy, Clone, PartialEq, Hash)]
+pub enum TrackSizing {
+    /// Fit the cell to its contents.
+    Auto,
+    /// A length stated in absolute values and fractions of the parent's size.
+    Linear(Linear),
+    /// A length that is the fraction of the remaining free space in the parent.
+    Fractional(Fractional),
+}
+
 impl Layout for GridNode {
     fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
-        GridLayouter::new(self, regions.clone()).layout(ctx)
+        // Prepare grid layout by unifying content and gutter tracks.
+        let mut layouter = GridLayouter::new(self, regions.clone());
+
+        // Determine all column sizes.
+        layouter.measure_columns(ctx);
+
+        // Layout the grid row-by-row.
+        layouter.layout(ctx)
     }
 }
 
@@ -28,125 +46,123 @@ impl From<GridNode> for AnyNode {
     }
 }
 
-#[derive(Debug)]
+/// Performs grid layout.
 struct GridLayouter<'a> {
+    /// The axis of the cross direction.
     cross: SpecAxis,
+    /// The axis of the main direction.
     main: SpecAxis,
+    /// The column tracks including gutter tracks.
     cols: Vec<TrackSizing>,
+    /// The row tracks including gutter tracks.
     rows: Vec<TrackSizing>,
-    cells: Vec<Cell<'a>>,
+    /// The children of the grid.
+    children: &'a [AnyNode],
+    /// The region to layout into.
     regions: Regions,
+    /// Resolved column sizes.
     rcols: Vec<Length>,
-    rrows: Vec<(usize, Option<Length>, Option<Vec<Option<Frame>>>)>,
+    /// The full main size of the current region.
+    full: Length,
+    /// The used-up size of the current region. The cross size is determined
+    /// once after columns are resolved and not touched again.
+    used: Gen<Length>,
+    /// The sum of fractional ratios in the current region.
+    fr: Fractional,
+    /// Rows in the current region.
+    lrows: Vec<Row>,
+    /// Frames for finished regions.
     finished: Vec<Frame>,
 }
 
-#[derive(Debug)]
-enum Cell<'a> {
-    Node(&'a AnyNode),
-    Gutter,
+/// Produced by initial row layout, auto and linear rows are already finished,
+/// fractional rows not yet.
+enum Row {
+    /// Finished row frame of auto or linear row.
+    Frame(Frame),
+    /// Ratio of a fractional row and y index of the track.
+    Fr(Fractional, usize),
 }
 
 impl<'a> GridLayouter<'a> {
-    fn new(grid: &'a GridNode, regions: Regions) -> Self {
-        let cross = grid.dirs.cross.axis();
-        let main = grid.dirs.main.axis();
-
+    /// Prepare grid layout by unifying content and gutter tracks.
+    fn new(grid: &'a GridNode, mut regions: Regions) -> Self {
         let mut cols = vec![];
         let mut rows = vec![];
-        let mut cells = vec![];
 
-        // A grid always needs to have at least one column.
-        let content_cols = grid.tracks.cross.len().max(1);
+        // Number of content columns: Always at least one.
+        let c = grid.tracks.cross.len().max(1);
 
-        // Create at least as many rows as specified and also at least as many
-        // as necessary to place each item.
-        let content_rows = {
+        // Number of content rows: At least as many as given, but also at least
+        // as many as needed to place each item.
+        let r = {
             let len = grid.children.len();
-            let specified = grid.tracks.main.len();
-            let necessary = len / content_cols + (len % content_cols).clamp(0, 1);
-            specified.max(necessary)
+            let given = grid.tracks.main.len();
+            let needed = len / c + (len % c).clamp(0, 1);
+            given.max(needed)
         };
 
-        // Collect the track sizing for all columns, including gutter columns.
-        for i in 0 .. content_cols {
-            cols.push(grid.tracks.cross.get_or_last(i));
-            if i < content_cols - 1 {
-                cols.push(grid.gutter.cross.get_or_last(i));
-            }
-        }
+        let auto = TrackSizing::Auto;
+        let zero = TrackSizing::Linear(Linear::zero());
+        let get_or = |tracks: &[_], idx, default| {
+            tracks.get(idx).or(tracks.last()).copied().unwrap_or(default)
+        };
 
-        // Collect the track sizing for all rows, including gutter rows.
-        for i in 0 .. content_rows {
-            rows.push(grid.tracks.main.get_or_last(i));
-            if i < content_rows - 1 {
-                rows.push(grid.gutter.main.get_or_last(i));
-            }
+        // Collect content and gutter columns.
+        for x in 0 .. c {
+            cols.push(get_or(&grid.tracks.cross, x, auto));
+            cols.push(get_or(&grid.gutter.cross, x, zero));
         }
 
-        // Build up the matrix of cells, including gutter cells.
-        for (i, item) in grid.children.iter().enumerate() {
-            cells.push(Cell::Node(item));
-
-            let row = i / content_cols;
-            let col = i % content_cols;
-
-            if col < content_cols - 1 {
-                // Push gutter after each child.
-                cells.push(Cell::Gutter);
-            } else if row < content_rows - 1 {
-                // Except for the last child of each row.
-                // There we push a gutter row.
-                for _ in 0 .. cols.len() {
-                    cells.push(Cell::Gutter);
-                }
-            }
+        // Collect content and gutter rows.
+        for y in 0 .. r {
+            rows.push(get_or(&grid.tracks.main, y, auto));
+            rows.push(get_or(&grid.gutter.main, y, zero));
         }
 
-        // Fill the thing up.
-        while cells.len() < cols.len() * rows.len() {
-            cells.push(Cell::Gutter);
-        }
+        // Remove superfluous gutter tracks.
+        cols.pop();
+        rows.pop();
+
+        let cross = grid.dirs.cross.axis();
+        let main = grid.dirs.main.axis();
+        let full = regions.current.get(main);
+        let rcols = vec![Length::zero(); cols.len()];
+
+        // We use the regions only for auto row measurement.
+        regions.expand = Gen::new(true, false).to_spec(main);
 
         Self {
             cross,
             main,
             cols,
             rows,
-            cells,
+            children: &grid.children,
             regions,
-            rcols: vec![],
-            rrows: vec![],
+            rcols,
+            lrows: vec![],
+            full,
+            used: Gen::zero(),
+            fr: Fractional::zero(),
             finished: vec![],
         }
     }
 
-    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Frame> {
-        self.rcols = self.resolve_columns(ctx);
-        self.layout_rows(ctx);
-        self.finished
-    }
+    /// Determine all column sizes.
+    fn measure_columns(&mut self, ctx: &mut LayoutContext) {
+        // Sum of sizes of resolved linear tracks.
+        let mut linear = Length::zero();
 
-    /// Determine the size of all columns.
-    fn resolve_columns(&self, ctx: &mut LayoutContext) -> Vec<Length> {
+        // Sum of fractions of all fractional tracks.
+        let mut fr = Fractional::zero();
+
+        // Generic version of current and base size.
         let current = self.regions.current.to_gen(self.main);
         let base = self.regions.base.to_gen(self.main);
 
-        // Prepare vector for resolved column lengths.
-        let mut rcols = vec![Length::zero(); self.cols.len()];
-
-        // - Sum of sizes of resolved linear tracks,
-        // - Sum of fractions of all fractional tracks,
-        // - Sum of sizes of resolved (through layouting) auto tracks,
-        // - Number of auto tracks.
-        let mut linear = Length::zero();
-        let mut fr = Fractional::zero();
-        let mut auto = Length::zero();
-        let mut auto_count = 0;
-
-        // Resolve size of linear columns and compute the sum of all fractional
-        // tracks.
-        for (&col, rcol) in self.cols.iter().zip(&mut rcols) {
+        // Resolve the size of all linear columns and compute the sum of all
+        // fractional tracks.
+        for (&col, rcol) in self.cols.iter().zip(&mut self.rcols) {
             match col {
                 TrackSizing::Auto => {}
                 TrackSizing::Linear(v) => {
@@ -158,379 +174,303 @@ impl<'a> GridLayouter<'a> {
             }
         }
 
-        // Size available to auto columns (not used by fixed-size columns).
+        // Size that is not used by fixed-size columns.
         let available = current.cross - linear;
-        if available <= Length::zero() {
-            return rcols;
+        if available >= Length::zero() {
+            // Determine size of auto columns.
+            let (auto, count) = self.measure_auto_columns(ctx, available);
+
+            // If there is remaining space, distribute it to fractional columns,
+            // otherwise shrink auto columns.
+            let remaining = available - auto;
+            if remaining >= Length::zero() {
+                self.grow_fractional_columns(remaining, fr);
+            } else {
+                self.shrink_auto_columns(available, count);
+            }
         }
 
-        // Resolve size of auto columns by laying out all cells in those
+        self.used.cross = self.rcols.iter().sum();
+    }
+
+    /// Measure the size that is available to auto columns.
+    fn measure_auto_columns(
+        &mut self,
+        ctx: &mut LayoutContext,
+        available: Length,
+    ) -> (Length, usize) {
+        let mut auto = Length::zero();
+        let mut count = 0;
+
+        // Determine size of auto columns by laying out all cells in those
         // columns, measuring them and finding the largest one.
-        for (x, (&col, rcol)) in self.cols.iter().zip(&mut rcols).enumerate() {
-            if col == TrackSizing::Auto {
-                let mut resolved = Length::zero();
-
-                for (y, &row) in self.rows.iter().enumerate() {
-                    if let Cell::Node(node) = self.get(x, y) {
-                        // Set the correct main size if the row is fixed-size.
-                        let main = match row {
-                            TrackSizing::Linear(v) => v.resolve(base.main),
-                            _ => current.main,
-                        };
-
-                        let size = Gen::new(available, main).to_size(self.main);
-                        let regions = Regions::one(size, Spec::splat(false));
-                        let frame = node.layout(ctx, &regions).remove(0);
-                        resolved = resolved.max(frame.size.get(self.cross))
-                    }
-                }
+        for (x, &col) in self.cols.iter().enumerate() {
+            if col != TrackSizing::Auto {
+                continue;
+            }
 
-                *rcol = resolved;
-                auto += resolved;
-                auto_count += 1;
+            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 frame = node.layout(ctx, &regions).remove(0);
+                resolved.set_max(frame.size.get(self.cross));
             }
+
+            self.rcols[x] = resolved;
+            auto += resolved;
+            count += 1;
         }
 
-        // If there is remaining space, distribute it to fractional columns,
-        // otherwise shrink auto columns.
-        let remaining = available - auto;
-        if remaining >= Length::zero() {
-            for (&col, rcol) in self.cols.iter().zip(&mut rcols) {
-                if let TrackSizing::Fractional(v) = col {
-                    let ratio = v / fr;
-                    if ratio.is_finite() {
-                        *rcol = ratio * remaining;
-                    }
-                }
-            }
-        } else {
-            // The fair share each auto column may have.
-            let fair = available / auto_count as f64;
-
-            // The number of overlarge auto columns and the space that will be
-            // equally redistributed to them.
-            let mut overlarge: usize = 0;
-            let mut redistribute = available;
-
-            for (&col, rcol) in self.cols.iter().zip(&mut rcols) {
-                if col == TrackSizing::Auto {
-                    if *rcol > fair {
-                        overlarge += 1;
-                    } else {
-                        redistribute -= *rcol;
-                    }
+        (auto, count)
+    }
+
+    /// Distribute remaining space to fractional columns.
+    fn grow_fractional_columns(&mut self, remaining: Length, fr: Fractional) {
+        for (&col, rcol) in self.cols.iter().zip(&mut self.rcols) {
+            if let TrackSizing::Fractional(v) = col {
+                let ratio = v / fr;
+                if ratio.is_finite() {
+                    *rcol = ratio * remaining;
                 }
             }
+        }
+    }
 
-            // Redistribute the space equally.
-            let share = redistribute / overlarge as f64;
-            if overlarge > 0 {
-                for (&col, rcol) in self.cols.iter().zip(&mut rcols) {
-                    if col == TrackSizing::Auto && *rcol > fair {
-                        *rcol = share;
-                    }
+    /// Redistribute space to auto columns so that each gets a fair share.
+    fn shrink_auto_columns(&mut self, available: Length, count: usize) {
+        // The fair share each auto column may have.
+        let fair = available / count as f64;
+
+        // The number of overlarge auto columns and the space that will be
+        // equally redistributed to them.
+        let mut overlarge: usize = 0;
+        let mut redistribute = available;
+
+        // Find out the number of and space used by overlarge auto columns.
+        for (&col, rcol) in self.cols.iter().zip(&mut self.rcols) {
+            if col == TrackSizing::Auto {
+                if *rcol > fair {
+                    overlarge += 1;
+                } else {
+                    redistribute -= *rcol;
                 }
             }
         }
 
-        rcols
+        // Redistribute the space equally.
+        let share = redistribute / overlarge as f64;
+        for (&col, rcol) in self.cols.iter().zip(&mut self.rcols) {
+            if col == TrackSizing::Auto && *rcol > fair {
+                *rcol = share;
+            }
+        }
     }
 
-    fn layout_rows(&mut self, ctx: &mut LayoutContext) {
-        // Determine non-`fr` row heights
-        let mut total_frs = 0.0;
-        let mut current = self.regions.current.get(self.main);
-
+    /// Layout the grid row-by-row.
+    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Frame> {
         for y in 0 .. self.rows.len() {
-            let resolved = match self.rows[y] {
-                TrackSizing::Linear(l) => {
-                    (Some(l.resolve(self.regions.base.get(self.main))), None)
-                }
+            match self.rows[y] {
                 TrackSizing::Auto => {
-                    let mut max = Length::zero();
-                    let mut local_max = max;
-                    let mut multi_region = false;
-                    let mut last_size = vec![];
-                    for (x, &col_size) in self.rcols.iter().enumerate() {
-                        if let Cell::Node(node) = self.get(x, y) {
-                            let colsize = Gen::new(col_size, current).to_size(self.main);
-
-                            let mut regions = self.regions.map(|mut s| {
-                                *s.get_mut(self.cross) = col_size;
-                                s
-                            });
-
-                            regions.base = colsize;
-                            regions.current = colsize;
-                            regions.expand = Spec::splat(false);
-
-                            let mut frames = node.layout(ctx, &regions);
-                            multi_region |= frames.len() > 1;
-                            last_size.push((
-                                frames.len() - 1,
-                                frames.last().unwrap().size.get(self.main),
-                            ));
-                            let frame = frames.remove(0);
-                            local_max = local_max.max(frame.size.get(self.main));
-
-                            if !multi_region {
-                                max = local_max;
-                            }
-                        } else {
-                            last_size.push((0, Length::zero()))
-                        }
-                    }
-
-                    let overshoot = if multi_region {
-                        self.rrows.push((y, Some(local_max), None));
-                        let res = self.finish_region(ctx, total_frs, Some(last_size));
-                        max = if let Some(overflow) = res.as_ref() {
-                            overflow
-                                .iter()
-                                .filter_map(|x| x.as_ref())
-                                .map(|x| x.size.get(self.main))
-                                .max()
-                                .unwrap_or(Length::zero())
-                        } else {
-                            local_max
-                        };
-
-                        current = self.regions.current.get(self.main);
-                        total_frs = 0.0;
-                        if res.is_none() {
-                            continue;
-                        }
-
-                        res
-                    } else {
-                        None
-                    };
-
-                    // If multi-region results: finish_regions, returning
-                    // the last non-set frames.
-                    (Some(max), overshoot)
+                    self.layout_auto_row(ctx, y);
                 }
-                TrackSizing::Fractional(f) => {
-                    total_frs += f.get();
-                    (None, None)
+                TrackSizing::Linear(v) => {
+                    let base = self.regions.base.get(self.main);
+                    let resolved = v.resolve(base);
+                    let frame = self.layout_single_row(ctx, resolved, y);
+                    self.push_row(ctx, frame);
                 }
-            };
-
-            if let (Some(resolved), _) = resolved {
-                while !current.fits(resolved) && !self.regions.in_full_last() {
-                    self.finish_region(ctx, total_frs, None);
-                    current = self.regions.current.get(self.main);
-                    total_frs = 0.0;
+                TrackSizing::Fractional(v) => {
+                    self.fr += v;
+                    self.lrows.push(Row::Fr(v, y));
                 }
-                current -= resolved;
             }
-
-            self.rrows.push((y, resolved.0, resolved.1));
         }
 
-        self.finish_region(ctx, total_frs, None);
+        self.finish_region(ctx);
+        self.finished
     }
 
-    fn finish_region(
-        &mut self,
-        ctx: &mut LayoutContext,
-        total_frs: f64,
-        multiregion_sizing: Option<Vec<(usize, Length)>>,
-    ) -> Option<Vec<Option<Frame>>> {
-        if self.rrows.is_empty() {
-            return None;
+    /// Layout a row with automatic size along the main axis. Such a row may
+    /// break across multiple regions.
+    fn layout_auto_row(&mut self, ctx: &mut LayoutContext, y: usize) {
+        let mut first = Length::zero();
+        let mut rest: Vec<Length> = vec![];
+
+        // Determine the size for each region of the row.
+        for (x, &rcol) in self.rcols.iter().enumerate() {
+            if let Some(node) = self.cell(x, y) {
+                let cross = self.cross;
+                self.regions.mutate(|size| *size.get_mut(cross) = rcol);
+
+                let mut sizes = node
+                    .layout(ctx, &self.regions)
+                    .into_iter()
+                    .map(|frame| frame.size.get(self.main));
+
+                if let Some(size) = sizes.next() {
+                    first.set_max(size);
+                }
+
+                for (resolved, size) in rest.iter_mut().zip(&mut sizes) {
+                    resolved.set_max(size);
+                }
+
+                rest.extend(sizes);
+            }
         }
 
-        let mut pos = Gen::splat(Length::zero());
-        let frame = Frame::new(Size::zero(), Length::zero());
-        let mut total_cross = Length::zero();
-        let mut total_main = Length::zero();
-        let mut max_regions = 0;
-        let mut collected_frames = if multiregion_sizing.is_some() {
-            Some(vec![None; self.rcols.len()])
+        // Layout the row.
+        if rest.is_empty() {
+            let frame = self.layout_single_row(ctx, first, y);
+            self.push_row(ctx, frame);
         } else {
-            None
-        };
+            let frames = self.layout_multi_row(ctx, first, &rest, y);
+            for frame in frames {
+                self.push_row(ctx, frame);
+            }
+        }
+    }
 
-        self.finished.push(frame);
+    /// Layout a row with a fixed size along the main axis.
+    fn layout_single_row(
+        &self,
+        ctx: &mut LayoutContext,
+        length: Length,
+        y: usize,
+    ) -> Frame {
+        let size = self.to_size(length);
+        let mut output = Frame::new(size, size.height);
+        let mut pos = Gen::zero();
+
+        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 frame = node.layout(ctx, &regions).remove(0);
+                output.push_frame(pos.to_point(self.main), frame);
+            }
 
-        let frame_len = self.finished.len();
+            pos.cross += rcol;
+        }
 
-        let total_row_height: Length = self.rrows.iter().filter_map(|(_, x, _)| *x).sum();
+        output
+    }
 
-        for &(y, h, ref layouted) in self.rrows.iter().as_ref() {
-            let last = self.rrows.last().map_or(false, |(o, _, _)| &y == o);
-            let available = self.regions.current.get(self.main) - total_row_height;
-            let h = if let Some(len) = h {
-                len
-            } else if let TrackSizing::Fractional(f) = self.rows[y] {
-                if total_frs > 0.0 {
-                    let res = available * (f.get() / total_frs);
-                    if res.is_finite() { res } else { Length::zero() }
-                } else {
-                    Length::zero()
-                }
-            } else {
-                unreachable!("non-fractional tracks are already resolved");
-            };
-            total_main += h;
-
-            if let Some(layouted) = layouted {
-                for (col_index, frame) in layouted.into_iter().enumerate() {
-                    if let Some(frame) = frame {
-                        self.finished
-                            .get_mut(frame_len - 1)
-                            .unwrap()
-                            .push_frame(pos.to_point(self.main), frame.clone());
-                    }
-                    pos.cross += self.rcols[col_index];
+    /// Layout a row spanning multiple regions.
+    fn layout_multi_row(
+        &self,
+        ctx: &mut LayoutContext,
+        first: Length,
+        rest: &[Length],
+        y: usize,
+    ) -> Vec<Frame> {
+        // Prepare frames.
+        let mut outputs: Vec<_> = std::iter::once(first)
+            .chain(rest.iter().copied())
+            .map(|v| self.to_size(v))
+            .map(|size| Frame::new(size, size.height))
+            .collect();
+
+        // Prepare regions.
+        let mut regions = Regions::one(self.to_size(first), Spec::splat(true));
+        regions.backlog = rest.iter().rev().map(|&v| self.to_size(v)).collect();
+
+        // Layout the row.
+        let mut pos = Gen::zero();
+        for (x, &rcol) in self.rcols.iter().enumerate() {
+            if let Some(node) = self.cell(x, y) {
+                regions.mutate(|size| *size.get_mut(self.cross) = rcol);
+
+                // 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);
                 }
-            } else {
-                let mut overshoot_columns = vec![];
-                for (x, &w) in self.rcols.iter().enumerate() {
-                    let element = self.get(x, y);
-
-                    if y == 0 {
-                        total_cross += w;
-                    }
+            }
 
-                    if let Cell::Node(n) = element {
-                        let region_size = Gen::new(w, h).to_size(self.main);
-                        let regions = if last {
-                            if let Some(last_sizes) = multiregion_sizing.as_ref() {
-                                let mut regions = self.regions.map(|mut s| {
-                                    *s.get_mut(self.cross) = w;
-                                    s
-                                });
-
-                                regions.base = region_size;
-                                regions.current = region_size;
-                                regions.expand = Spec::splat(true);
-
-                                let (last_region, last_size) = last_sizes[x];
-                                regions.unique_regions(last_region + 1);
-                                *regions
-                                    .nth_mut(last_region)
-                                    .unwrap()
-                                    .get_mut(self.main) = last_size;
-                                regions
-                            } else {
-                                Regions::one(region_size, Spec::splat(true))
-                            }
-                        } else {
-                            Regions::one(region_size, Spec::splat(true))
-                        };
-                        let mut items = n.layout(ctx, &regions);
-                        let item = items.remove(0);
-
-                        if last && multiregion_sizing.is_some() {
-                            max_regions = max_regions.max(items.len());
-                            overshoot_columns.push((x, items));
-                        } else {
-                            assert_eq!(items.len(), 0);
-                        }
-
-                        self.finished
-                            .get_mut(frame_len - 1)
-                            .unwrap()
-                            .push_frame(pos.to_point(self.main), item);
-                    }
+            pos.cross += rcol;
+        }
 
-                    pos.cross += w;
-                }
+        outputs
+    }
 
-                if overshoot_columns.iter().any(|(_, items)| !items.is_empty()) {
-                    for (x, col) in overshoot_columns {
-                        let mut cross_offset = Length::zero();
-                        for col in 0 .. x {
-                            cross_offset += self.rcols[col];
-                        }
-
-
-                        let collected_frames = collected_frames.as_mut().unwrap();
-                        *collected_frames.get_mut(x).unwrap() =
-                            col.get(max_regions - 1).cloned();
-
-                        for (cell_index, subcell) in col.into_iter().enumerate() {
-                            if cell_index >= max_regions - 1 {
-                                continue;
-                            }
-                            let frame = if let Some(frame) =
-                                self.finished.get_mut(frame_len + cell_index)
-                            {
-                                frame
-                            } else {
-                                let frame = Frame::new(Size::zero(), Length::zero());
-                                // The previous frame always exists: either the
-                                // last iteration created it or it is the normal
-                                // frame.
-                                self.finished.push(frame);
-                                self.finished.last_mut().unwrap()
-                            };
-                            let pos = Gen::new(cross_offset, Length::zero());
-                            frame
-                                .size
-                                .get_mut(self.cross)
-                                .set_max(pos.cross + subcell.size.get(self.cross));
-                            frame
-                                .size
-                                .get_mut(self.main)
-                                .set_max(subcell.size.get(self.main));
-                            frame.baseline = frame.size.height;
-                            frame.push_frame(pos.to_point(self.main), subcell);
-                        }
-                    }
-                }
-            }
+    /// Push a row frame into the current or next fitting region, finishing
+    /// regions (including layouting fractional rows) if necessary.
+    fn push_row(&mut self, ctx: &mut LayoutContext, frame: Frame) {
+        let length = frame.size.get(self.main);
 
-            pos.cross = Length::zero();
-            pos.main += h;
+        // Skip to fitting region.
+        while !self.regions.current.get(self.main).fits(length)
+            && !self.regions.in_full_last()
+        {
+            self.finish_region(ctx);
         }
 
-        let frame = self.finished.get_mut(frame_len - 1).unwrap();
-        frame.size = Gen::new(total_cross, total_main).to_size(self.main);
-        frame.baseline = frame.size.height;
+        *self.regions.current.get_mut(self.main) -= length;
+        self.used.main += length;
+        self.lrows.push(Row::Frame(frame));
+    }
 
-        self.rrows.clear();
-        for _ in 0 .. (max_regions.max(1)) {
-            self.regions.next();
-        }
+    /// Finish rows for one region.
+    fn finish_region(&mut self, ctx: &mut LayoutContext) {
+        // 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);
+
+        // The frame for the region.
+        let mut output = Frame::new(size, size.height);
+        let mut pos = Gen::zero();
+
+        // Determine the remaining size for fractional rows.
+        let remaining = self.full - self.used.main;
+
+        // Place finished rows and layout fractional rows.
+        for row in std::mem::take(&mut self.lrows) {
+            let frame = match row {
+                Row::Frame(frame) => frame,
+                Row::Fr(v, y) => {
+                    let ratio = v / self.fr;
+                    if remaining > Length::zero() && ratio.is_finite() {
+                        let resolved = ratio * remaining;
+                        self.layout_single_row(ctx, resolved, y)
+                    } else {
+                        continue;
+                    }
+                }
+            };
 
-        if let Some(frames) = collected_frames.as_ref() {
-            if frames.iter().all(|i| i.is_none()) {
-                collected_frames = None;
-            }
+            let main = frame.size.get(self.main);
+            output.push_frame(pos.to_point(self.main), frame);
+            pos.main += main;
         }
 
-        collected_frames
+        self.regions.next();
+        self.full = self.regions.current.get(self.main);
+        self.used.main = Length::zero();
+        self.fr = Fractional::zero();
+        self.finished.push(output);
     }
 
-    fn get(&self, x: usize, y: usize) -> &Cell<'a> {
+    /// Get the node in the cell in column `x` and row `y`.
+    ///
+    /// Returns `None` if it's a gutter cell.
+    fn cell(&self, x: usize, y: usize) -> Option<&'a AnyNode> {
         assert!(x < self.cols.len());
         assert!(y < self.rows.len());
-        self.cells.get(y * self.cols.len() + x).unwrap()
-    }
-}
-
-trait TracksExt {
-    /// Get the sizing for the track at the given `idx` or fallback to the
-    /// last defined track or `auto`.
-    fn get_or_last(&self, idx: usize) -> TrackSizing;
-}
 
-impl TracksExt for Vec<TrackSizing> {
-    fn get_or_last(&self, idx: usize) -> TrackSizing {
-        self.get(idx).or(self.last()).copied().unwrap_or(TrackSizing::Auto)
+        // Even columns and rows are children, odd ones are gutter.
+        if x % 2 == 0 && y % 2 == 0 {
+            let c = 1 + self.cols.len() / 2;
+            self.children.get((y / 2) * c + x / 2)
+        } else {
+            None
+        }
     }
-}
 
-/// Defines how to size a grid cell along an axis.
-#[derive(Debug, Copy, Clone, PartialEq, Hash)]
-pub enum TrackSizing {
-    /// Fit the cell to its contents.
-    Auto,
-    /// A length stated in absolute values and fractions of the parent's size.
-    Linear(Linear),
-    /// A length that is the fraction of the remaining free space in the parent.
-    Fractional(Fractional),
+    /// Return a size where the cross axis spans the whole grid and the main
+    /// axis the given length.
+    fn to_size(&self, main_size: Length) -> Size {
+        Gen::new(self.used.cross, main_size).to_size(self.main)
+    }
 }
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 6f536e20..9c4222c8 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -23,8 +23,6 @@ use std::collections::HashMap;
 use std::fmt::{self, Debug, Formatter};
 use std::hash::{Hash, Hasher};
 
-use decorum::N64;
-
 use crate::cache::Cache;
 use crate::geom::*;
 use crate::loading::Loader;
@@ -245,18 +243,14 @@ impl Regions {
         }
     }
 
-    /// Map the size of all regions.
+    /// Create new regions where all sizes are mapped with `f`.
     pub fn map<F>(&self, mut f: F) -> Self
     where
         F: FnMut(Size) -> Size,
     {
-        Self {
-            current: f(self.current),
-            base: f(self.base),
-            backlog: self.backlog.iter().copied().map(|s| f(s)).collect(),
-            last: self.last.map(f),
-            expand: self.expand,
-        }
+        let mut regions = self.clone();
+        regions.mutate(|s| *s = f(*s));
+        regions
     }
 
     /// Whether `current` is a fully sized (untouched) copy of the last region.
@@ -274,38 +268,14 @@ impl Regions {
         }
     }
 
-    /// Shrink `current` to ensure that the aspect ratio can be satisfied.
-    pub fn apply_aspect_ratio(&mut self, aspect: N64) {
-        let width = self.current.width.min(aspect.into_inner() * self.current.height);
-        let height = width / aspect.into_inner();
-        self.current = Size::new(width, height);
-    }
-
-    /// Appends new elements to the backlog such that the behavior of `next`
-    /// does not change. Panics when used with finite regions.
-    pub fn backlogify(&mut self, count: usize) {
-        for _ in 0 .. count {
-            self.backlog.push(self.last.unwrap())
-        }
-    }
-
-    /// Ensures that enough unique regions are present, including the current
-    /// and last ones. Panics when used with finite regions.
-    pub fn unique_regions(&mut self, count: usize) {
-        if self.backlog.len() < count.max(2) - 2 {
-            self.backlogify((count - 2) - self.backlog.len());
-        }
-    }
-
-    /// Returns a mutable reference to the size of the `n`th region.
-    pub fn nth_mut(&mut self, n: usize) -> Option<&mut Size> {
-        let backlog_len = self.backlog.len();
-        if n == 0 {
-            Some(&mut self.current)
-        } else if n <= backlog_len {
-            self.backlog.get_mut(backlog_len - n)
-        } else {
-            self.last.as_mut()
-        }
+    /// 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/par.rs b/src/layout/par.rs
index d2992040..40c36421 100644
--- a/src/layout/par.rs
+++ b/src/layout/par.rs
@@ -40,12 +40,12 @@ impl Layout for ParNode {
         // Find out the BiDi embedding levels.
         let bidi = BidiInfo::new(&text, Level::from_dir(self.dir));
 
-        // Build a representation of the paragraph on which we can do
-        // linebreaking without layouting each and every line from scratch.
-        let layout = ParLayout::new(ctx, regions, self, bidi);
+        // Prepare paragraph layout by bulding a representation on which we can
+        // do line breaking without layouting each and every line from scratch.
+        let layouter = ParLayouter::new(self, ctx, regions, bidi);
 
         // Find suitable linebreaks.
-        layout.build(ctx, regions.clone(), self)
+        layouter.layout(ctx, regions.clone())
     }
 }
 
@@ -102,9 +102,11 @@ impl Debug for ParChild {
 
 /// A paragraph representation in which children are already layouted and text
 /// is separated into shapable runs.
-struct ParLayout<'a> {
+struct ParLayouter<'a> {
     /// The top-level direction.
     dir: Dir,
+    /// The line spacing.
+    line_spacing: Length,
     /// Bidirectional text embedding levels for the paragraph.
     bidi: BidiInfo<'a>,
     /// Layouted children and separated text runs.
@@ -113,12 +115,12 @@ struct ParLayout<'a> {
     ranges: Vec<Range>,
 }
 
-impl<'a> ParLayout<'a> {
-    /// Build a paragraph layout for the given node.
+impl<'a> ParLayouter<'a> {
+    /// Prepare initial shaped text and layouted children.
     fn new(
+        par: &'a ParNode,
         ctx: &mut LayoutContext,
         regions: &Regions,
-        par: &'a ParNode,
         bidi: BidiInfo<'a>,
     ) -> Self {
         // Prepare an iterator over each child an the range it spans.
@@ -142,26 +144,25 @@ impl<'a> ParLayout<'a> {
                     }
                 }
                 ParChild::Any(ref node, align) => {
-                    let mut frames = node.layout(ctx, regions).into_iter();
-                    let frame = frames.next().unwrap();
-                    assert!(frames.next().is_none());
+                    let frame = node.layout(ctx, regions).remove(0);
                     items.push(ParItem::Frame(frame, align));
                     ranges.push(range);
                 }
             }
         }
 
-        Self { dir: par.dir, bidi, items, ranges }
+        Self {
+            dir: par.dir,
+            line_spacing: par.line_spacing,
+            bidi,
+            items,
+            ranges,
+        }
     }
 
     /// Find first-fit line breaks and build the paragraph.
-    fn build(
-        self,
-        ctx: &mut LayoutContext,
-        regions: Regions,
-        par: &ParNode,
-    ) -> Vec<Frame> {
-        let mut stack = LineStack::new(par.line_spacing, regions);
+    fn layout(self, ctx: &mut LayoutContext, regions: Regions) -> Vec<Frame> {
+        let mut stack = LineStack::new(self.line_spacing, regions);
 
         // The current line attempt.
         // Invariant: Always fits into `stack.regions.current`.
@@ -272,37 +273,41 @@ impl ParItem<'_> {
     }
 }
 
-/// A simple layouter that stacks lines into regions.
+/// Stacks lines on top of each other.
 struct LineStack<'a> {
     line_spacing: Length,
     regions: Regions,
-    finished: Vec<Frame>,
-    lines: Vec<LineLayout<'a>>,
     size: Size,
+    lines: Vec<LineLayout<'a>>,
+    finished: Vec<Frame>,
 }
 
 impl<'a> LineStack<'a> {
+    /// Create an empty line stack.
     fn new(line_spacing: Length, regions: Regions) -> Self {
         Self {
             line_spacing,
             regions,
-            finished: vec![],
-            lines: vec![],
             size: Size::zero(),
+            lines: vec![],
+            finished: vec![],
         }
     }
 
+    /// Push a new line into the stack.
     fn push(&mut self, line: LineLayout<'a>) {
-        self.size.height += line.size.height;
+        self.regions.current.height -= line.size.height + self.line_spacing;
+
         self.size.width.set_max(line.size.width);
+        self.size.height += line.size.height;
         if !self.lines.is_empty() {
             self.size.height += self.line_spacing;
         }
 
-        self.regions.current.height -= line.size.height + self.line_spacing;
         self.lines.push(line);
     }
 
+    /// Finish the frame for one region.
     fn finish_region(&mut self, ctx: &LayoutContext) {
         if self.regions.expand.horizontal {
             self.size.width = self.regions.current.width;
@@ -312,7 +317,7 @@ impl<'a> LineStack<'a> {
         let mut offset = Length::zero();
         let mut first = true;
 
-        for line in std::mem::take(&mut self.lines) {
+        for line in self.lines.drain(..) {
             let frame = line.build(ctx, self.size.width);
 
             let pos = Point::new(Length::zero(), offset);
@@ -325,11 +330,12 @@ impl<'a> LineStack<'a> {
             output.push_frame(pos, frame);
         }
 
-        self.finished.push(output);
         self.regions.next();
         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> {
         self.finish_region(ctx);
         self.finished
@@ -340,8 +346,10 @@ impl<'a> LineStack<'a> {
 /// paragraph's text. This type enables you to cheaply measure the size of a
 /// line in a range before comitting to building the line's frame.
 struct LineLayout<'a> {
-    /// The paragraph the line was created in.
-    par: &'a ParLayout<'a>,
+    /// The direction of the line.
+    dir: Dir,
+    /// Bidi information about the paragraph.
+    bidi: &'a BidiInfo<'a>,
     /// The range the line spans in the paragraph.
     line: Range,
     /// A reshaped text item if the line sliced up a text item at the start.
@@ -363,7 +371,7 @@ struct LineLayout<'a> {
 
 impl<'a> LineLayout<'a> {
     /// Create a line which spans the given range.
-    fn new(ctx: &mut LayoutContext, par: &'a ParLayout<'a>, mut line: Range) -> Self {
+    fn new(ctx: &mut LayoutContext, par: &'a ParLayouter<'a>, mut line: Range) -> Self {
         // Find the items which bound the text range.
         let last_idx = par.find(line.end.saturating_sub(1)).unwrap();
         let first_idx = if line.is_empty() {
@@ -436,7 +444,8 @@ impl<'a> LineLayout<'a> {
         }
 
         Self {
-            par,
+            dir: par.dir,
+            bidi: &par.bidi,
             line,
             first,
             items,
@@ -474,7 +483,7 @@ impl<'a> LineLayout<'a> {
 
             // FIXME: Ruler alignment for RTL.
             let pos = Point::new(
-                ruler.resolve(self.par.dir, offset .. free + offset),
+                ruler.resolve(self.dir, offset .. free + offset),
                 self.baseline - frame.baseline,
             );
 
@@ -494,7 +503,6 @@ impl<'a> LineLayout<'a> {
 
         // Find the paragraph that contains the line.
         let para = self
-            .par
             .bidi
             .paragraphs
             .iter()
@@ -502,7 +510,7 @@ impl<'a> LineLayout<'a> {
             .unwrap();
 
         // Compute the reordered ranges in visual order (left to right).
-        let (levels, runs) = self.par.bidi.visual_runs(para, self.line.clone());
+        let (levels, runs) = self.bidi.visual_runs(para, self.line.clone());
 
         // Find the items for each run.
         for run in runs {
diff --git a/src/layout/stack.rs b/src/layout/stack.rs
index a6d83695..8c47597b 100644
--- a/src/layout/stack.rs
+++ b/src/layout/stack.rs
@@ -39,7 +39,7 @@ impl From<StackNode> for AnyNode {
     }
 }
 
-#[derive(Debug)]
+/// Performs stack layout.
 struct StackLayouter<'a> {
     /// The stack node to layout.
     stack: &'a StackNode,
@@ -49,9 +49,6 @@ struct StackLayouter<'a> {
     expand: Spec<bool>,
     /// The region to layout into.
     regions: Regions,
-    /// 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)>,
     /// The full size of `regions.current` that was available before we started
     /// subtracting.
     full: Size,
@@ -59,11 +56,15 @@ struct StackLayouter<'a> {
     used: Gen<Length>,
     /// The alignment ruler for the current region.
     ruler: Align,
+    /// 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>,
 }
 
 impl<'a> StackLayouter<'a> {
+    /// Create a new stack layouter.
     fn new(stack: &'a StackNode, mut regions: Regions) -> Self {
         let main = stack.dirs.main.axis();
         let full = regions.current;
@@ -73,7 +74,7 @@ impl<'a> StackLayouter<'a> {
         *regions.expand.get_mut(main) = false;
 
         if let Some(aspect) = stack.aspect {
-            regions.apply_aspect_ratio(aspect);
+            regions.current = regions.current.with_aspect(aspect.into_inner());
         }
 
         Self {
@@ -81,26 +82,21 @@ impl<'a> StackLayouter<'a> {
             main,
             expand,
             regions,
-            finished: vec![],
-            frames: vec![],
             full,
             used: Gen::zero(),
             ruler: Align::Start,
+            frames: vec![],
+            finished: vec![],
         }
     }
 
+    /// Layout all children.
     fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Frame> {
         for child in &self.stack.children {
             match *child {
-                StackChild::Spacing(amount) => self.push_spacing(amount),
+                StackChild::Spacing(amount) => self.space(amount),
                 StackChild::Any(ref node, aligns) => {
-                    let mut frames = node.layout(ctx, &self.regions).into_iter();
-                    if let Some(frame) = frames.next() {
-                        self.push_frame(frame, aligns);
-                    }
-
-                    for frame in frames {
-                        self.finish_region();
+                    for frame in node.layout(ctx, &self.regions) {
                         self.push_frame(frame, aligns);
                     }
                 }
@@ -111,7 +107,8 @@ impl<'a> StackLayouter<'a> {
         self.finished
     }
 
-    fn push_spacing(&mut self, amount: Length) {
+    /// Add main-axis spacing into the current region.
+    fn space(&mut self, amount: Length) {
         // Cap the spacing to the remaining available space.
         let remaining = self.regions.current.get_mut(self.main);
         let capped = amount.min(*remaining);
@@ -121,60 +118,65 @@ impl<'a> StackLayouter<'a> {
         *remaining -= capped;
     }
 
+    /// Push a frame into the current or next fitting region, finishing regions
+    /// if necessary.
     fn push_frame(&mut self, frame: Frame, aligns: Gen<Align>) {
-        let size = frame.size;
+        let size = frame.size.to_gen(self.main);
 
         // Don't allow `Start` after `End` in the same region.
-        if self.ruler > aligns.main {
+        if aligns.main < self.ruler {
             self.finish_region();
         }
 
-        // Adjust the ruler.
-        self.ruler = aligns.main;
-
         // Find a fitting region.
-        while !self.regions.current.fits(size) && !self.regions.in_full_last() {
+        while !self.regions.current.get(self.main).fits(size.main)
+            && !self.regions.in_full_last()
+        {
             self.finish_region();
         }
 
-        // Remember the frame with offset and alignment.
-        self.frames.push((self.used.main, aligns, frame));
+        // Shrink available space in the region.
+        *self.regions.current.get_mut(self.main) -= size.main;
 
-        // Grow our size and shrink available space in the region.
-        let gen = size.to_gen(self.main);
-        self.used.main += gen.main;
-        self.used.cross.set_max(gen.cross);
-        *self.regions.current.get_mut(self.main) -= gen.main;
+        // Grow our size.
+        let offset = self.used.main;
+        self.used.main += size.main;
+        self.used.cross.set_max(size.cross);
+        self.ruler = aligns.main;
+
+        // Remember the frame with offset and alignment.
+        self.frames.push((offset, aligns, frame));
     }
 
+    /// Finish the frame for one region.
     fn finish_region(&mut self) {
-        let used = self.used.to_size(self.main);
         let expand = self.expand;
+        let used = self.used.to_size(self.main);
 
         // Determine the stack's size dependening on whether the region is
         // fixed.
-        let mut stack_size = Size::new(
+        let mut size = Size::new(
             if expand.horizontal { self.full.width } else { used.width },
             if expand.vertical { self.full.height } else { used.height },
         );
 
         // Make sure the stack's size satisfies the aspect ratio.
         if let Some(aspect) = self.stack.aspect {
-            let width = stack_size
+            let width = size
                 .width
-                .max(aspect.into_inner() * stack_size.height)
+                .max(aspect.into_inner() * size.height)
                 .min(self.full.width)
                 .min(aspect.into_inner() * self.full.height);
 
-            stack_size = Size::new(width, width / aspect.into_inner());
+            size = Size::new(width, width / aspect.into_inner());
         }
 
-        let mut output = Frame::new(stack_size, stack_size.height);
+        let mut output = Frame::new(size, size.height);
         let mut first = true;
 
         // Place all frames.
-        for (offset, aligns, frame) in std::mem::take(&mut self.frames) {
-            let stack_size = stack_size.to_gen(self.main);
+        for (offset, aligns, frame) in self.frames.drain(..) {
+            let stack_size = size.to_gen(self.main);
             let child_size = frame.size.to_gen(self.main);
 
             // Align along the cross axis.
@@ -206,10 +208,9 @@ impl<'a> StackLayouter<'a> {
             output.push_frame(pos, frame);
         }
 
-        // Move on to the next region.
         self.regions.next();
         if let Some(aspect) = self.stack.aspect {
-            self.regions.apply_aspect_ratio(aspect);
+            self.regions.current = self.regions.current.with_aspect(aspect.into_inner());
         }
 
         self.full = self.regions.current;