Introduce `FlowNode`

10 files changed, 297 insertions, 52 deletions

diff --git a/src/eval/template.rs b/src/eval/template.rs
index 18104638..795a7049 100644
--- a/src/eval/template.rs
+++ b/src/eval/template.rs
@@ -9,7 +9,7 @@ use crate::diag::StrResult;
 use crate::geom::{Align, Dir, GenAxis, Length, Linear, Sides, Size};
 use crate::layout::{BlockLevel, BlockNode, InlineLevel, InlineNode, PageNode};
 use crate::library::{
-    Decoration, PadNode, ParChild, ParNode, Spacing, StackChild, StackNode,
+    Decoration, FlowChild, FlowNode, PadNode, ParChild, ParNode, Spacing,
 };
 use crate::style::Style;
 use crate::util::EcoString;
@@ -148,12 +148,12 @@ impl Template {
         Self(Rc::new(vec![TemplateNode::Decorated(deco, self)]))
     }
 
-    /// Build the stack node resulting from instantiating the template with the
+    /// Build the flow node resulting from instantiating the template with the
     /// given style.
-    pub fn to_stack(&self, style: &Style) -> StackNode {
+    pub fn to_flow(&self, style: &Style) -> FlowNode {
         let mut builder = Builder::new(style, false);
         builder.template(self);
-        builder.build_stack()
+        builder.build_flow()
     }
 
     /// Build the layout tree resulting from instantiating the template with the
@@ -240,10 +240,10 @@ struct Builder {
     /// The finished page nodes.
     finished: Vec<PageNode>,
     /// When we are building the top-level layout trees, this contains metrics
-    /// of the page. While building a stack, this is `None`.
+    /// of the page. While building a flow, this is `None`.
     page: Option<PageBuilder>,
-    /// The currently built stack of paragraphs.
-    stack: StackBuilder,
+    /// The currently built flow of paragraphs.
+    flow: FlowBuilder,
 }
 
 impl Builder {
@@ -254,7 +254,7 @@ impl Builder {
             snapshots: vec![],
             finished: vec![],
             page: pages.then(|| PageBuilder::new(style, true)),
-            stack: StackBuilder::new(style),
+            flow: FlowBuilder::new(style),
         }
     }
 
@@ -284,9 +284,9 @@ impl Builder {
             TemplateNode::Text(text) => self.text(text),
             TemplateNode::Spacing(axis, amount) => self.spacing(*axis, *amount),
             TemplateNode::Decorated(deco, template) => {
-                self.stack.par.push(ParChild::Decorate(deco.clone()));
+                self.flow.par.push(ParChild::Decorate(deco.clone()));
                 self.template(template);
-                self.stack.par.push(ParChild::Undecorate);
+                self.flow.par.push(ParChild::Undecorate);
             }
             TemplateNode::Inline(f) => self.inline(f(&self.style)),
             TemplateNode::Block(f) => self.block(f(&self.style)),
@@ -296,67 +296,66 @@ impl Builder {
 
     /// Push a word space into the active paragraph.
     fn space(&mut self) {
-        self.stack.par.push_soft(self.make_text_node(' '));
+        self.flow.par.push_soft(self.make_text_node(' '));
     }
 
     /// Apply a forced line break.
     fn linebreak(&mut self) {
-        self.stack.par.push_hard(self.make_text_node('\n'));
+        self.flow.par.push_hard(self.make_text_node('\n'));
     }
 
     /// Apply a forced paragraph break.
     fn parbreak(&mut self) {
         let amount = self.style.par_spacing();
-        self.stack.finish_par(&self.style);
-        self.stack
-            .push_soft(StackChild::Spacing(Spacing::Linear(amount.into())));
+        self.flow.finish_par(&self.style);
+        self.flow
+            .push_soft(FlowChild::Spacing(Spacing::Linear(amount.into())));
     }
 
     /// Apply a forced page break.
     fn pagebreak(&mut self, keep: bool, hard: bool) {
         if let Some(builder) = &mut self.page {
             let page = mem::replace(builder, PageBuilder::new(&self.style, hard));
-            let stack = mem::replace(&mut self.stack, StackBuilder::new(&self.style));
-            self.finished.extend(page.build(stack.build(), keep));
+            let flow = mem::replace(&mut self.flow, FlowBuilder::new(&self.style));
+            self.finished.extend(page.build(flow.build(), keep));
         }
     }
 
     /// Push text into the active paragraph.
     fn text(&mut self, text: impl Into<EcoString>) {
-        self.stack.par.push(self.make_text_node(text));
+        self.flow.par.push(self.make_text_node(text));
     }
 
     /// Push an inline node into the active paragraph.
     fn inline(&mut self, node: impl Into<InlineNode>) {
         let align = self.style.aligns.inline;
-        self.stack.par.push(ParChild::Node(node.into(), align));
+        self.flow.par.push(ParChild::Node(node.into(), align));
     }
 
-    /// Push a block node into the active stack, finishing the active paragraph.
+    /// Push a block node into the active flow, finishing the active paragraph.
     fn block(&mut self, node: impl Into<BlockNode>) {
         self.parbreak();
-        self.stack
-            .push(StackChild::Node(node.into(), self.style.aligns.block));
+        self.flow.push(FlowChild::Node(node.into(), self.style.aligns.block));
         self.parbreak();
     }
 
-    /// Push spacing into the active paragraph or stack depending on the `axis`.
+    /// Push spacing into the active paragraph or flow depending on the `axis`.
     fn spacing(&mut self, axis: GenAxis, spacing: Spacing) {
         match axis {
             GenAxis::Block => {
-                self.stack.finish_par(&self.style);
-                self.stack.push_hard(StackChild::Spacing(spacing));
+                self.flow.finish_par(&self.style);
+                self.flow.push_hard(FlowChild::Spacing(spacing));
             }
             GenAxis::Inline => {
-                self.stack.par.push_hard(ParChild::Spacing(spacing));
+                self.flow.par.push_hard(ParChild::Spacing(spacing));
             }
         }
     }
 
-    /// Finish building and return the created stack.
-    fn build_stack(self) -> StackNode {
+    /// Finish building and return the created flow.
+    fn build_flow(self) -> FlowNode {
         assert!(self.page.is_none());
-        self.stack.build()
+        self.flow.build()
     }
 
     /// Finish building and return the created layout tree.
@@ -392,7 +391,7 @@ impl PageBuilder {
         }
     }
 
-    fn build(self, child: StackNode, keep: bool) -> Option<PageNode> {
+    fn build(self, child: FlowNode, keep: bool) -> Option<PageNode> {
         let Self { size, padding, hard } = self;
         (!child.children.is_empty() || (keep && hard)).then(|| PageNode {
             size,
@@ -401,33 +400,31 @@ impl PageBuilder {
     }
 }
 
-struct StackBuilder {
-    dir: Dir,
-    children: Vec<StackChild>,
-    last: Last<StackChild>,
+struct FlowBuilder {
+    children: Vec<FlowChild>,
+    last: Last<FlowChild>,
     par: ParBuilder,
 }
 
-impl StackBuilder {
+impl FlowBuilder {
     fn new(style: &Style) -> Self {
         Self {
-            dir: Dir::TTB,
             children: vec![],
             last: Last::None,
             par: ParBuilder::new(style),
         }
     }
 
-    fn push(&mut self, child: StackChild) {
+    fn push(&mut self, child: FlowChild) {
         self.children.extend(self.last.any());
         self.children.push(child);
     }
 
-    fn push_soft(&mut self, child: StackChild) {
+    fn push_soft(&mut self, child: FlowChild) {
         self.last.soft(child);
     }
 
-    fn push_hard(&mut self, child: StackChild) {
+    fn push_hard(&mut self, child: FlowChild) {
         self.last.hard();
         self.children.push(child);
     }
@@ -439,13 +436,13 @@ impl StackBuilder {
         }
     }
 
-    fn build(self) -> StackNode {
-        let Self { dir, mut children, par, mut last } = self;
+    fn build(self) -> FlowNode {
+        let Self { mut children, par, mut last } = self;
         if let Some(par) = par.build() {
             children.extend(last.any());
             children.push(par);
         }
-        StackNode { dir, children }
+        FlowNode { children }
     }
 }
 
@@ -499,10 +496,10 @@ impl ParBuilder {
         self.children.push(child);
     }
 
-    fn build(self) -> Option<StackChild> {
+    fn build(self) -> Option<FlowChild> {
         let Self { align, dir, leading, children, .. } = self;
         (!children.is_empty())
-            .then(|| StackChild::Node(ParNode { dir, leading, children }.pack(), align))
+            .then(|| FlowChild::Node(ParNode { dir, leading, children }.pack(), align))
     }
 }
 
diff --git a/src/eval/walk.rs b/src/eval/walk.rs
index 6d5df5ba..d1eb7ac1 100644
--- a/src/eval/walk.rs
+++ b/src/eval/walk.rs
@@ -138,7 +138,7 @@ fn walk_item(ctx: &mut EvalContext, label: EcoString, body: Template) {
         GridNode {
             tracks: Spec::new(vec![TrackSizing::Auto; 2], vec![]),
             gutter: Spec::new(vec![TrackSizing::Linear(spacing.into())], vec![]),
-            children: vec![label.pack(), body.to_stack(style).pack()],
+            children: vec![label.pack(), body.to_flow(style).pack()],
         }
     });
 }
diff --git a/src/library/container.rs b/src/library/container.rs
index b2591cce..4b52139f 100644
--- a/src/library/container.rs
+++ b/src/library/container.rs
@@ -13,7 +13,7 @@ pub fn box_(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
             width,
             height,
             fill: fill.map(Paint::Color),
-            child: Some(body.to_stack(style).pack()),
+            child: Some(body.to_flow(style).pack()),
         }
     })))
 }
@@ -22,6 +22,6 @@ pub fn box_(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
 pub fn block(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
     let body: Template = args.expect("body")?;
     Ok(Value::Template(Template::from_block(move |style| {
-        body.to_stack(style)
+        body.to_flow(style)
     })))
 }
diff --git a/src/library/flow.rs b/src/library/flow.rs
new file mode 100644
index 00000000..f422a62b
--- /dev/null
+++ b/src/library/flow.rs
@@ -0,0 +1,245 @@
+use std::fmt::{self, Debug, Formatter};
+
+use super::prelude::*;
+use super::Spacing;
+
+/// `flow`: A vertical flow of paragraphs and other layout nodes.
+pub fn flow(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
+    enum Child {
+        Spacing(Spacing),
+        Any(Template),
+    }
+
+    castable! {
+        Child,
+        Expected: "linear, fractional or template",
+        Value::Length(v) => Self::Spacing(Spacing::Linear(v.into())),
+        Value::Relative(v) => Self::Spacing(Spacing::Linear(v.into())),
+        Value::Linear(v) => Self::Spacing(Spacing::Linear(v)),
+        Value::Fractional(v) => Self::Spacing(Spacing::Fractional(v)),
+        Value::Template(v) => Self::Any(v),
+    }
+
+    let children: Vec<Child> = args.all().collect();
+
+    Ok(Value::Template(Template::from_block(move |style| {
+        let children = children
+            .iter()
+            .map(|child| match child {
+                Child::Spacing(spacing) => FlowChild::Spacing(*spacing),
+                Child::Any(child) => {
+                    FlowChild::Node(child.to_flow(style).pack(), style.aligns.block)
+                }
+            })
+            .collect();
+
+        FlowNode { children }
+    })))
+}
+
+/// A vertical flow of content consisting of paragraphs and other layout nodes.
+///
+/// This node is reponsible for layouting both the top-level content flow and
+/// the contents of boxes.
+#[derive(Debug, Hash)]
+pub struct FlowNode {
+    /// The children that compose the flow. There are different kinds of
+    /// children for different purposes.
+    pub children: Vec<FlowChild>,
+}
+
+/// A child of a flow node.
+#[derive(Hash)]
+pub enum FlowChild {
+    /// Vertical spacing between other children.
+    Spacing(Spacing),
+    /// Any block node and how to align it in the flow.
+    Node(BlockNode, Align),
+}
+
+impl BlockLevel for FlowNode {
+    fn layout(
+        &self,
+        ctx: &mut LayoutContext,
+        regions: &Regions,
+    ) -> Vec<Constrained<Rc<Frame>>> {
+        FlowLayouter::new(self, regions.clone()).layout(ctx)
+    }
+}
+
+impl Debug for FlowChild {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        match self {
+            Self::Spacing(v) => write!(f, "Spacing({:?})", v),
+            Self::Node(node, _) => node.fmt(f),
+        }
+    }
+}
+
+/// Performs flow layout.
+struct FlowLayouter<'a> {
+    /// The flow node to layout.
+    flow: &'a FlowNode,
+    /// Whether the flow should expand to fill the region.
+    expand: Spec<bool>,
+    /// The region to layout into.
+    regions: Regions,
+    /// The full size of `regions.current` that was available before we started
+    /// subtracting.
+    full: Size,
+    /// The size used by the frames for the current region.
+    used: Size,
+    /// The sum of fractional ratios in the current region.
+    fr: Fractional,
+    /// Spacing and layouted nodes.
+    items: Vec<FlowItem>,
+    /// Finished frames for previous regions.
+    finished: Vec<Constrained<Rc<Frame>>>,
+}
+
+/// A prepared item in a flow layout.
+enum FlowItem {
+    /// Absolute spacing between other items.
+    Absolute(Length),
+    /// Fractional spacing between other items.
+    Fractional(Fractional),
+    /// A layouted child node.
+    Frame(Rc<Frame>, Align),
+}
+
+impl<'a> FlowLayouter<'a> {
+    /// Create a new flow layouter.
+    fn new(flow: &'a FlowNode, mut regions: Regions) -> Self {
+        // Disable vertical expansion for children.
+        let expand = regions.expand;
+        regions.expand.y = false;
+
+        Self {
+            flow,
+            expand,
+            full: regions.current,
+            regions,
+            used: Size::zero(),
+            fr: Fractional::zero(),
+            items: vec![],
+            finished: vec![],
+        }
+    }
+
+    /// Layout all children.
+    fn layout(mut self, ctx: &mut LayoutContext) -> Vec<Constrained<Rc<Frame>>> {
+        for child in &self.flow.children {
+            match *child {
+                FlowChild::Spacing(Spacing::Linear(v)) => {
+                    self.layout_absolute(v);
+                }
+                FlowChild::Spacing(Spacing::Fractional(v)) => {
+                    self.items.push(FlowItem::Fractional(v));
+                    self.fr += v;
+                }
+                FlowChild::Node(ref node, align) => {
+                    self.layout_node(ctx, node, align);
+                }
+            }
+        }
+
+        self.finish_region();
+        self.finished
+    }
+
+    /// Layout absolute spacing.
+    fn layout_absolute(&mut self, amount: Linear) {
+        // Resolve the linear, limiting it to the remaining available space.
+        let remaining = &mut self.regions.current.h;
+        let resolved = amount.resolve(self.full.h);
+        let limited = resolved.min(*remaining);
+        *remaining -= limited;
+        self.used.h += limited;
+        self.items.push(FlowItem::Absolute(resolved));
+    }
+
+    /// Layout a block node.
+    fn layout_node(&mut self, ctx: &mut LayoutContext, node: &BlockNode, align: Align) {
+        let frames = node.layout(ctx, &self.regions);
+        let len = frames.len();
+        for (i, frame) in frames.into_iter().enumerate() {
+            // Grow our size.
+            let size = frame.item.size;
+            self.used.h += size.h;
+            self.used.w.set_max(size.w);
+
+            // Remember the frame and shrink available space in the region for the
+            // following children.
+            self.items.push(FlowItem::Frame(frame.item, align));
+            self.regions.current.h -= size.h;
+
+            if i + 1 < len {
+                self.finish_region();
+            }
+        }
+    }
+
+    /// Finish the frame for one region.
+    fn finish_region(&mut self) {
+        // Determine the size that remains for fractional spacing.
+        let remaining = self.full.h - self.used.h;
+
+        // Determine the size of the flow in this region dependening on whether
+        // the region expands.
+        let mut size = Size::new(
+            if self.expand.x { self.full.w } else { self.used.w },
+            if self.expand.y { self.full.h } else { self.used.h },
+        );
+
+        // Expand fully if there are fr spacings.
+        if !self.fr.is_zero() && self.full.h.is_finite() {
+            size.h = self.full.h;
+        }
+
+        let mut output = Frame::new(size, size.h);
+        let mut before = Length::zero();
+        let mut ruler = Align::Start;
+        let mut first = true;
+
+        // Place all frames.
+        for item in self.items.drain(..) {
+            match item {
+                FlowItem::Absolute(v) => before += v,
+                FlowItem::Fractional(v) => {
+                    let ratio = v / self.fr;
+                    if remaining.is_finite() && ratio.is_finite() {
+                        before += ratio * remaining;
+                    }
+                }
+                FlowItem::Frame(frame, align) => {
+                    ruler = ruler.max(align);
+
+                    // Align vertically.
+                    let y =
+                        ruler.resolve(Dir::TTB, before .. before + size.h - self.used.h);
+
+                    let pos = Point::new(Length::zero(), y);
+                    if first {
+                        // The baseline of the flow is that of the first frame.
+                        output.baseline = pos.y + frame.baseline;
+                        first = false;
+                    }
+
+                    before += frame.size.h;
+                    output.push_frame(pos, frame);
+                }
+            }
+        }
+
+        // Generate tight constraints for now.
+        let mut cts = Constraints::new(self.expand);
+        cts.exact = self.full.to_spec().map(Some);
+        cts.base = self.regions.base.to_spec().map(Some);
+
+        self.regions.next();
+        self.full = self.regions.current;
+        self.used = Size::zero();
+        self.fr = Fractional::zero();
+        self.finished.push(output.constrain(cts));
+    }
+}
diff --git a/src/library/grid.rs b/src/library/grid.rs
index 0fe778b2..c69762fd 100644
--- a/src/library/grid.rs
+++ b/src/library/grid.rs
@@ -45,7 +45,7 @@ pub fn grid(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
         GridNode {
             tracks: tracks.clone(),
             gutter: gutter.clone(),
-            children: children.iter().map(|child| child.to_stack(style).pack()).collect(),
+            children: children.iter().map(|child| child.to_flow(style).pack()).collect(),
         }
     })))
 }
diff --git a/src/library/mod.rs b/src/library/mod.rs
index e6cb0d9d..d96b370a 100644
--- a/src/library/mod.rs
+++ b/src/library/mod.rs
@@ -6,6 +6,7 @@
 mod align;
 mod container;
 mod deco;
+mod flow;
 mod grid;
 mod image;
 mod pad;
@@ -35,6 +36,7 @@ pub use self::image::*;
 pub use align::*;
 pub use container::*;
 pub use deco::*;
+pub use flow::*;
 pub use grid::*;
 pub use pad::*;
 pub use page::*;
@@ -71,6 +73,7 @@ pub fn new() -> Scope {
     std.def_func("align", align);
     std.def_func("box", box_);
     std.def_func("block", block);
+    std.def_func("flow", flow);
     std.def_func("pad", pad);
     std.def_func("move", move_);
     std.def_func("stack", stack);
diff --git a/src/library/pad.rs b/src/library/pad.rs
index 8c3c0f53..d17a4ca2 100644
--- a/src/library/pad.rs
+++ b/src/library/pad.rs
@@ -19,7 +19,7 @@ pub fn pad(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
     Ok(Value::Template(Template::from_block(move |style| {
         PadNode {
             padding,
-            child: body.to_stack(style).pack(),
+            child: body.to_flow(style).pack(),
         }
     })))
 }
diff --git a/src/library/shape.rs b/src/library/shape.rs
index 1eba2285..5be26aa4 100644
--- a/src/library/shape.rs
+++ b/src/library/shape.rs
@@ -78,7 +78,7 @@ fn shape_impl(
         fill: Some(Paint::Color(
             fill.unwrap_or(Color::Rgba(RgbaColor::new(175, 175, 175, 255))),
         )),
-        child: body.as_ref().map(|template| template.to_stack(style).pack()),
+        child: body.as_ref().map(|template| template.to_flow(style).pack()),
     }))
 }
 
diff --git a/src/library/stack.rs b/src/library/stack.rs
index ffd9b44f..78ae506d 100644
--- a/src/library/stack.rs
+++ b/src/library/stack.rs
@@ -40,7 +40,7 @@ pub fn stack(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
                         children.push(StackChild::Spacing(v));
                     }
 
-                    let node = template.to_stack(style).pack();
+                    let node = template.to_flow(style).pack();
                     children.push(StackChild::Node(node, style.aligns.block));
                     delayed = spacing;
                 }
diff --git a/src/library/transform.rs b/src/library/transform.rs
index 846a7262..b7e5e36c 100644
--- a/src/library/transform.rs
+++ b/src/library/transform.rs
@@ -15,7 +15,7 @@ pub fn move_(_: &mut EvalContext, args: &mut Args) -> TypResult<Value> {
                 width: None,
                 height: None,
                 fill: None,
-                child: Some(body.to_stack(style).pack()),
+                child: Some(body.to_flow(style).pack()),
             },
         }
     })))