Allow grid cells to span multiple regions. (#30)

7 files changed, 335 insertions, 54 deletions

diff --git a/src/geom/length.rs b/src/geom/length.rs
index e9ba0853..21843d3e 100644
--- a/src/geom/length.rs
+++ b/src/geom/length.rs
@@ -4,7 +4,7 @@ use serde::{Deserialize, Serialize};
 use super::*;
 
 /// An absolute length.
-#[derive(Default, Copy, Clone, PartialEq, PartialOrd, Hash)]
+#[derive(Default, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
 #[derive(Serialize, Deserialize)]
 #[serde(transparent)]
 pub struct Length {
@@ -85,7 +85,7 @@ impl Length {
 
     /// Set to the minimum of this and another length.
     pub fn set_min(&mut self, other: Self) {
-        *self = self.min(other);
+        *self = (*self).min(other);
     }
 
     /// The maximum of this and another length.
@@ -95,7 +95,7 @@ impl Length {
 
     /// Set to the maximum of this and another length.
     pub fn set_max(&mut self, other: Self) {
-        *self = self.max(other);
+        *self = (*self).max(other);
     }
 
     /// Whether the other length fits into this one (i.e. is smaller).
diff --git a/src/layout/grid.rs b/src/layout/grid.rs
index 3ba6c16b..64c33097 100644
--- a/src/layout/grid.rs
+++ b/src/layout/grid.rs
@@ -25,6 +25,7 @@ impl From<GridNode> for AnyNode {
     }
 }
 
+#[derive(Debug)]
 struct GridLayouter<'a> {
     cross: SpecAxis,
     main: SpecAxis,
@@ -32,11 +33,12 @@ struct GridLayouter<'a> {
     rows: Vec<TrackSizing>,
     cells: Vec<Cell<'a>>,
     regions: Regions,
-    rrows: Vec<(usize, Option<Length>)>,
+    rrows: Vec<(usize, Option<Length>, Option<Vec<Option<Frame>>>)>,
     rcols: Vec<Length>,
     finished: Vec<Frame>,
 }
 
+#[derive(Debug)]
 enum Cell<'a> {
     Node(&'a AnyNode),
     Gutter,
@@ -233,95 +235,263 @@ impl<'a> GridLayouter<'a> {
         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)))
+                    (Some(l.resolve(self.regions.base.get(self.main))), None)
                 }
                 TrackSizing::Auto => {
                     let mut max = Length::zero();
-                    for (x, len) in self.rcols.iter().enumerate() {
+                    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 regions = Regions::one(
-                                Gen::new(*len, current).to_size(self.main),
-                                Spec::splat(false),
-                            );
-                            let frame = node.layout(ctx, &regions).remove(0);
-                            max = max.max(frame.size.get(self.main));
+                            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()))
                         }
                     }
-                    Some(max)
+
+                    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)
                 }
                 TrackSizing::Fractional(f) => {
                     total_frs += f.get();
-                    None
+                    (None, None)
                 }
             };
 
-            if let Some(resolved) = resolved {
+            if let (Some(resolved), _) = resolved {
                 while !current.fits(resolved) && !self.regions.in_full_last() {
-                    self.finish_region(ctx, total_frs);
+                    self.finish_region(ctx, total_frs, None);
                     current = self.regions.current.get(self.main);
                     total_frs = 0.0;
                 }
                 current -= resolved;
             }
 
-            self.rrows.push((y, resolved));
+            self.rrows.push((y, resolved.0, resolved.1));
         }
 
-        self.finish_region(ctx, total_frs);
+        self.finish_region(ctx, total_frs, None);
         self.finished
     }
 
-    fn finish_region(&mut self, ctx: &mut LayoutContext, total_frs: f64) {
+    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;
+        }
+
         let mut pos = Gen::splat(Length::zero());
-        let mut frame = Frame::new(Size::zero(), 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()])
+        } else {
+            None
+        };
 
-        for (x, &w) in self.rcols.iter().enumerate() {
-            let total: Length = self.rrows.iter().filter_map(|(_, x)| *x).sum();
-            let available = self.regions.current.get(self.main) - total;
-            total_cross += w;
-
-            for (y, h) in self.rrows.iter() {
-                let element = self.get(x, *y);
-                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()
-                    }
+        self.finished.push(frame);
+
+        let frame_len = self.finished.len();
+
+        let total_row_height: Length = self.rrows.iter().filter_map(|(_, x, _)| *x).sum();
+
+        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 {
-                    unreachable!("non-fractional tracks are already resolved");
-                };
+                    Length::zero()
+                }
+            } else {
+                unreachable!("non-fractional tracks are already resolved");
+            };
+            total_main += h;
 
-                if x == 0 {
-                    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];
                 }
+            } else {
+                let mut overshoot_columns = vec![];
+                for (x, &w) in self.rcols.iter().enumerate() {
+                    let element = self.get(x, y);
 
-                if let Cell::Node(n) = element {
-                    let regions = Regions::one(
-                        Gen::new(w, h).to_size(self.main),
-                        Spec::splat(false),
-                    );
-                    let item = n.layout(ctx, &regions).remove(0);
-                    frame.push_frame(pos.to_point(self.main), item);
+                    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 += w;
                 }
 
-                pos.main += h;
+                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);
+                        }
+                    }
+                }
             }
-            pos.main = Length::zero();
-            pos.cross += w;
+
+            pos.cross = Length::zero();
+            pos.main += h;
         }
 
+        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.rrows.clear();
-        self.regions.next();
-        self.finished.push(frame);
+        for _ in 0 .. (max_regions.max(1)) {
+            self.regions.next();
+        }
+
+        if let Some(frames) = collected_frames.as_ref() {
+            if frames.iter().all(|i| i.is_none()) {
+                collected_frames = None;
+            }
+        }
+
+        collected_frames
     }
 
     fn get(&self, x: usize, y: usize) -> &Cell<'a> {
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 4153fc3c..6f536e20 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -280,4 +280,32 @@ impl Regions {
         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()
+        }
+    }
 }
diff --git a/src/library/grid.rs b/src/library/grid.rs
index 79070e79..192dee9d 100644
--- a/src/library/grid.rs
+++ b/src/library/grid.rs
@@ -36,7 +36,9 @@ pub fn grid(ctx: &mut EvalContext, args: &mut FuncArgs) -> Value {
     let columns = args.eat_named::<Tracks>(ctx, "columns").unwrap_or_default();
     let rows = args.eat_named::<Tracks>(ctx, "rows").unwrap_or_default();
     let column_dir = args.eat_named(ctx, "column-dir");
-    let gutter = args.eat_named::<Tracks>(ctx, "gutter").unwrap_or_default();
+    let gutter = args.eat_named::<Linear>(ctx, "gutter")
+        .map(|v| Tracks(vec![TrackSizing::Linear(v)]))
+        .unwrap_or_default();
     let gutter_columns = args.eat_named::<Tracks>(ctx, "gutter-columns");
     let gutter_rows = args.eat_named::<Tracks>(ctx, "gutter-rows");
     let children = args.eat_all::<TemplateValue>(ctx);
diff --git a/tests/ref/layout/grid-3.png b/tests/ref/layout/grid-3.png
new file mode 100644
index 00000000..ec37e46e
--- /dev/null
+++ b/tests/ref/layout/grid-3.png
diff --git a/tests/typ/layout/grid-1.typ b/tests/typ/layout/grid-1.typ
index 6a4aee87..827a98a7 100644
--- a/tests/typ/layout/grid-1.typ
+++ b/tests/typ/layout/grid-1.typ
@@ -25,7 +25,8 @@
 ---
 #grid(
     columns: (auto, auto, 40%),
-    gutter: (1fr,),
+    gutter-columns: (1fr,),
+    gutter-rows: (1fr,),
     rect(fill: eastern)[dddaa aaa aaa],
     rect(fill: conifer)[ccc],
     rect(width: 100%, fill: #dddddd)[aaa],
@@ -52,3 +53,4 @@
     rows: (1fr, auto, 2fr),
     [], rect(width: 100%)[A bit more to the top], [],
 )
+
diff --git a/tests/typ/layout/grid-3.typ b/tests/typ/layout/grid-3.typ
new file mode 100644
index 00000000..6ef0ab83
--- /dev/null
+++ b/tests/typ/layout/grid-3.typ
@@ -0,0 +1,79 @@
+// Test grid cells that overflow to the next region.
+
+---
+#page(width: 5cm, height: 3cm)
+#grid(
+    columns: 2,
+    gutter-rows: 3 * (8pt,),
+    [Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
+
+    Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis.],
+    [Text that is rather short],
+    [Fireflies],
+    [Critical],
+    [Decorum],
+    [Rampage],
+)
+
+---
+// Test a column that starts overflowing right after another row/column did
+// that.
+#page(width: 5cm, height: 2cm)
+#grid(
+    columns: 4 * (1fr,),
+    gutter-rows: (10pt,),
+    gutter-columns: (0pt, 10%),
+    image("../../res/rhino.png"),
+    align(right, rect(width: 100%, fill: eastern)[LoL]),
+    "rofl",
+    "\nA" * 3,
+    "Ha!\n" * 3,
+)
+
+---
+// Test two columns in the same row overflowing by a different amount.
+#page(width: 5cm, height: 2cm)
+#grid(
+    columns: 3 * (1fr,),
+    gutter-rows: (8pt,),
+    gutter-columns: (0pt, 10%),
+    [A], [B], [C],
+    "Ha!\n" * 6,
+    "rofl",
+    "\nA" * 3,
+    [hello],
+    [darkness],
+    [my old]
+)
+
+---
+// Test grid within a grid, overflowing.
+#page(width: 5cm, height: 2.25cm)
+#grid(
+    columns: 4 * (1fr,),
+    gutter-rows: (10pt,),
+    gutter-columns: (0pt, 10%),
+    [A], [B], [C], [D],
+    grid(columns: 2, [A], [B], "C\n"*3, [D]),
+    align(right, rect(width: 100%, fill: eastern)[LoL]),
+    "rofl",
+    "E\n"*4,
+)
+
+---
+// Test partition of `fr` units before and after multi-region layout.
+#page(width: 5cm, height: 4cm)
+#grid(
+    columns: 2 * (1fr,),
+    rows: (1fr, 2fr, auto, 1fr, 1cm),
+    gutter-rows: 4 * (10pt,),
+    rect(height: 100%, width: 100%, fill: #ff0000)[No height],
+    [foo],
+    rect(height: 100%, width: 100%, fill: #fc0030)[Still no height],
+    [bar],
+    [The nature of being itself is in question. Am I One? Am I Many? What is being alive?],
+    [baz],
+    [The answer],
+    [42],
+    [Other text of interest],
+)