From 594809e35b9e768f1a50926cf5e7a9df41ba7d16 Mon Sep 17 00:00:00 2001
From: Laurenz <laurmaedje@gmail.com>
Date: Tue, 17 Aug 2021 22:04:18 +0200
Subject: Library functions behave more imperatively

- Templates scope state changes
- State-modifying function operate in place instead of returning a template
- Internal template representation contains actual owned nodes instead of a pointer to a syntax tree + an expression map
- No more wide calls
---
 src/eval/mod.rs      | 201 +++++++++++++++------
 src/eval/state.rs    | 266 ++++++++++++++++++++++++++++
 src/eval/template.rs | 490 +++++++++++++++++++++++++++++++++++++++++++--------
 src/eval/value.rs    |  11 +-
 4 files changed, 831 insertions(+), 137 deletions(-)
 create mode 100644 src/eval/state.rs

(limited to 'src/eval')

diff --git a/src/eval/mod.rs b/src/eval/mod.rs
index d8ce7884..d4989371 100644
--- a/src/eval/mod.rs
+++ b/src/eval/mod.rs
@@ -1,4 +1,4 @@
-//! Evaluation of syntax trees.
+//! Evaluation of syntax trees into modules.
 
 #[macro_use]
 mod array;
@@ -10,6 +10,7 @@ mod capture;
 mod function;
 mod ops;
 mod scope;
+mod state;
 mod str;
 mod template;
 
@@ -19,39 +20,38 @@ pub use capture::*;
 pub use dict::*;
 pub use function::*;
 pub use scope::*;
+pub use state::*;
 pub use template::*;
 pub use value::*;
 
 use std::cell::RefMut;
 use std::collections::HashMap;
+use std::fmt::Write;
 use std::io;
 use std::mem;
 use std::path::PathBuf;
 use std::rc::Rc;
 
 use crate::diag::{At, Error, StrResult, Trace, Tracepoint, TypResult};
-use crate::geom::{Angle, Fractional, Length, Relative};
+use crate::geom::{Angle, Fractional, Gen, Length, Relative};
 use crate::image::ImageStore;
+use crate::layout::{ParChild, ParNode, StackChild, StackNode};
 use crate::loading::Loader;
 use crate::parse::parse;
 use crate::source::{SourceId, SourceStore};
 use crate::syntax::visit::Visit;
 use crate::syntax::*;
-use crate::util::RefMutExt;
+use crate::util::{EcoString, RefMutExt};
 use crate::Context;
 
 /// Evaluate a parsed source file into a module.
-pub fn eval(
-    ctx: &mut Context,
-    source: SourceId,
-    ast: Rc<SyntaxTree>,
-) -> TypResult<Module> {
+pub fn eval(ctx: &mut Context, source: SourceId, ast: &SyntaxTree) -> TypResult<Module> {
     let mut ctx = EvalContext::new(ctx, source);
     let template = ast.eval(&mut ctx)?;
     Ok(Module { scope: ctx.scopes.top, template })
 }
 
-/// An evaluated module, ready for importing or execution.
+/// An evaluated module, ready for importing or instantiation.
 #[derive(Debug, Clone, PartialEq)]
 pub struct Module {
     /// The top-level definitions that were bound in this module.
@@ -74,8 +74,8 @@ pub struct EvalContext<'a> {
     pub modules: HashMap<SourceId, Module>,
     /// The active scopes.
     pub scopes: Scopes<'a>,
-    /// The expression map for the currently built template.
-    pub map: ExprMap,
+    /// The currently built template.
+    pub template: Template,
 }
 
 impl<'a> EvalContext<'a> {
@@ -88,7 +88,7 @@ impl<'a> EvalContext<'a> {
             route: vec![source],
             modules: HashMap::new(),
             scopes: Scopes::new(Some(&ctx.std)),
-            map: ExprMap::new(),
+            template: Template::new(),
         }
     }
 
@@ -158,17 +158,17 @@ pub trait Eval {
     fn eval(&self, ctx: &mut EvalContext) -> TypResult<Self::Output>;
 }
 
-impl Eval for Rc<SyntaxTree> {
+impl Eval for SyntaxTree {
     type Output = Template;
 
     fn eval(&self, ctx: &mut EvalContext) -> TypResult<Self::Output> {
-        let map = {
-            let prev = mem::take(&mut ctx.map);
+        Ok({
+            let prev = mem::take(&mut ctx.template);
+            ctx.template.save();
             self.walk(ctx)?;
-            mem::replace(&mut ctx.map, prev)
-        };
-
-        Ok(TemplateTree { tree: Rc::clone(self), map }.into())
+            ctx.template.restore();
+            mem::replace(&mut ctx.template, prev)
+        })
     }
 }
 
@@ -671,43 +671,6 @@ impl Eval for IncludeExpr {
     }
 }
 
-/// Walk a node in a template, filling the context's expression map.
-pub trait Walk {
-    /// Walk the node.
-    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()>;
-}
-
-impl Walk for SyntaxTree {
-    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
-        for node in self.iter() {
-            node.walk(ctx)?;
-        }
-        Ok(())
-    }
-}
-
-impl Walk for SyntaxNode {
-    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
-        match self {
-            Self::Space => {}
-            Self::Text(_) => {}
-            Self::Linebreak(_) => {}
-            Self::Parbreak(_) => {}
-            Self::Strong(_) => {}
-            Self::Emph(_) => {}
-            Self::Raw(_) => {}
-            Self::Heading(n) => n.body.walk(ctx)?,
-            Self::List(n) => n.body.walk(ctx)?,
-            Self::Enum(n) => n.body.walk(ctx)?,
-            Self::Expr(n) => {
-                let value = n.eval(ctx)?;
-                ctx.map.insert(n as *const _, value);
-            }
-        }
-        Ok(())
-    }
-}
-
 /// Try to mutably access the value an expression points to.
 ///
 /// This only works if the expression is a valid lvalue.
@@ -754,3 +717,129 @@ impl Access for CallExpr {
         })
     }
 }
+
+/// Walk a syntax node and fill the currently built template.
+pub trait Walk {
+    /// Walk the node.
+    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()>;
+}
+
+impl Walk for SyntaxTree {
+    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
+        for node in self.iter() {
+            node.walk(ctx)?;
+        }
+        Ok(())
+    }
+}
+
+impl Walk for SyntaxNode {
+    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
+        match self {
+            Self::Space => ctx.template.space(),
+            Self::Linebreak(_) => ctx.template.linebreak(),
+            Self::Parbreak(_) => ctx.template.parbreak(),
+            Self::Strong(_) => {
+                ctx.template.modify(|state| state.font_mut().strong ^= true);
+            }
+            Self::Emph(_) => {
+                ctx.template.modify(|state| state.font_mut().emph ^= true);
+            }
+            Self::Text(text) => ctx.template.text(text),
+            Self::Raw(raw) => raw.walk(ctx)?,
+            Self::Heading(heading) => heading.walk(ctx)?,
+            Self::List(list) => list.walk(ctx)?,
+            Self::Enum(enum_) => enum_.walk(ctx)?,
+            Self::Expr(expr) => match expr.eval(ctx)? {
+                Value::None => {}
+                Value::Int(v) => ctx.template.text(v.to_string()),
+                Value::Float(v) => ctx.template.text(v.to_string()),
+                Value::Str(v) => ctx.template.text(v),
+                Value::Template(v) => ctx.template += v,
+                // For values which can't be shown "naturally", we print the
+                // representation in monospace.
+                other => ctx.template.monospace(other.to_string()),
+            },
+        }
+        Ok(())
+    }
+}
+
+impl Walk for RawNode {
+    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
+        if self.block {
+            ctx.template.parbreak();
+        }
+
+        ctx.template.monospace(&self.text);
+
+        if self.block {
+            ctx.template.parbreak();
+        }
+
+        Ok(())
+    }
+}
+
+impl Walk for HeadingNode {
+    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
+        let level = self.level;
+        let body = self.body.eval(ctx)?;
+
+        ctx.template.parbreak();
+        ctx.template.save();
+        ctx.template.modify(move |state| {
+            let font = state.font_mut();
+            let upscale = 1.6 - 0.1 * level as f64;
+            font.size *= upscale;
+            font.strong = true;
+        });
+        ctx.template += body;
+        ctx.template.restore();
+        ctx.template.parbreak();
+
+        Ok(())
+    }
+}
+
+impl Walk for ListItem {
+    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
+        let body = self.body.eval(ctx)?;
+        walk_item(ctx, '•'.into(), body);
+        Ok(())
+    }
+}
+
+impl Walk for EnumItem {
+    fn walk(&self, ctx: &mut EvalContext) -> TypResult<()> {
+        let body = self.body.eval(ctx)?;
+        let mut label = EcoString::new();
+        write!(&mut label, "{}.", self.number.unwrap_or(1)).unwrap();
+        walk_item(ctx, label, body);
+        Ok(())
+    }
+}
+
+/// Walk a list or enum item, converting it into a stack.
+fn walk_item(ctx: &mut EvalContext, label: EcoString, body: Template) {
+    ctx.template += Template::from_block(move |state| {
+        let label = ParNode {
+            dir: state.dirs.cross,
+            line_spacing: state.line_spacing(),
+            children: vec![ParChild::Text(
+                label.clone(),
+                state.aligns.cross,
+                Rc::clone(&state.font),
+            )],
+        };
+        StackNode {
+            dirs: Gen::new(state.dirs.main, state.dirs.cross),
+            aspect: None,
+            children: vec![
+                StackChild::Any(label.into(), Gen::default()),
+                StackChild::Spacing((state.font.size / 2.0).into()),
+                StackChild::Any(body.to_stack(&state).into(), Gen::default()),
+            ],
+        }
+    });
+}
diff --git a/src/eval/state.rs b/src/eval/state.rs
new file mode 100644
index 00000000..760a830a
--- /dev/null
+++ b/src/eval/state.rs
@@ -0,0 +1,266 @@
+use std::rc::Rc;
+
+use crate::color::{Color, RgbaColor};
+use crate::font::{
+    FontFamily, FontStretch, FontStyle, FontVariant, FontWeight, VerticalFontMetric,
+};
+use crate::geom::*;
+use crate::layout::Paint;
+use crate::paper::{PaperClass, PAPER_A4};
+
+/// Defines an set of properties a template can be instantiated with.
+#[derive(Debug, Clone, Eq, PartialEq, Hash)]
+pub struct State {
+    /// The direction for text and other inline objects.
+    pub dirs: Gen<Dir>,
+    /// The alignments of layouts in their parents.
+    pub aligns: Gen<Align>,
+    /// The page settings.
+    pub page: Rc<PageState>,
+    /// The paragraph settings.
+    pub par: Rc<ParState>,
+    /// The font settings.
+    pub font: Rc<FontState>,
+}
+
+impl State {
+    /// Access the `page` state mutably.
+    pub fn page_mut(&mut self) -> &mut PageState {
+        Rc::make_mut(&mut self.page)
+    }
+
+    /// Access the `par` state mutably.
+    pub fn par_mut(&mut self) -> &mut ParState {
+        Rc::make_mut(&mut self.par)
+    }
+
+    /// Access the `font` state mutably.
+    pub fn font_mut(&mut self) -> &mut FontState {
+        Rc::make_mut(&mut self.font)
+    }
+
+    /// The resolved line spacing.
+    pub fn line_spacing(&self) -> Length {
+        self.par.line_spacing.resolve(self.font.size)
+    }
+
+    /// The resolved paragraph spacing.
+    pub fn par_spacing(&self) -> Length {
+        self.par.par_spacing.resolve(self.font.size)
+    }
+}
+
+impl Default for State {
+    fn default() -> Self {
+        Self {
+            dirs: Gen::new(Dir::LTR, Dir::TTB),
+            aligns: Gen::splat(Align::Start),
+            page: Rc::new(PageState::default()),
+            par: Rc::new(ParState::default()),
+            font: Rc::new(FontState::default()),
+        }
+    }
+}
+
+/// Defines page properties.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
+pub struct PageState {
+    /// The class of this page.
+    pub class: PaperClass,
+    /// The width and height of the page.
+    pub size: Size,
+    /// The amount of white space on each side of the page. If a side is set to
+    /// `None`, the default for the paper class is used.
+    pub margins: Sides<Option<Linear>>,
+}
+
+impl PageState {
+    /// The resolved margins.
+    pub fn margins(&self) -> Sides<Linear> {
+        let default = self.class.default_margins();
+        Sides {
+            left: self.margins.left.unwrap_or(default.left),
+            top: self.margins.top.unwrap_or(default.top),
+            right: self.margins.right.unwrap_or(default.right),
+            bottom: self.margins.bottom.unwrap_or(default.bottom),
+        }
+    }
+}
+
+impl Default for PageState {
+    fn default() -> Self {
+        let paper = PAPER_A4;
+        Self {
+            class: paper.class(),
+            size: paper.size(),
+            margins: Sides::splat(None),
+        }
+    }
+}
+
+/// Defines paragraph properties.
+#[derive(Debug, Clone, Eq, PartialEq, Hash)]
+pub struct ParState {
+    /// The spacing between paragraphs (dependent on scaled font size).
+    pub par_spacing: Linear,
+    /// The spacing between lines (dependent on scaled font size).
+    pub line_spacing: Linear,
+}
+
+impl Default for ParState {
+    fn default() -> Self {
+        Self {
+            par_spacing: Relative::new(1.0).into(),
+            line_spacing: Relative::new(0.5).into(),
+        }
+    }
+}
+
+/// Defines font properties.
+#[derive(Debug, Clone, Eq, PartialEq, Hash)]
+pub struct FontState {
+    /// Whether 300 extra font weight should be added to what is defined by the
+    /// `variant`.
+    pub strong: bool,
+    /// Whether the the font style defined by the `variant` should be inverted.
+    pub emph: bool,
+    /// Whether a monospace font should be preferred.
+    pub monospace: bool,
+    /// The font size.
+    pub size: Length,
+    /// The selected font variant (the final variant also depends on `strong`
+    /// and `emph`).
+    pub variant: FontVariant,
+    /// The top end of the text bounding box.
+    pub top_edge: VerticalFontMetric,
+    /// The bottom end of the text bounding box.
+    pub bottom_edge: VerticalFontMetric,
+    /// Glyph color.
+    pub fill: Paint,
+    /// A list of font families with generic class definitions (the final
+    /// family list also depends on `monospace`).
+    pub families: Rc<FamilyState>,
+    /// The specifications for a strikethrough line, if any.
+    pub strikethrough: Option<Rc<LineState>>,
+    /// The specifications for a underline, if any.
+    pub underline: Option<Rc<LineState>>,
+    /// The specifications for a overline line, if any.
+    pub overline: Option<Rc<LineState>>,
+}
+
+impl FontState {
+    /// The resolved variant with `strong` and `emph` factored in.
+    pub fn variant(&self) -> FontVariant {
+        let mut variant = self.variant;
+
+        if self.strong {
+            variant.weight = variant.weight.thicken(300);
+        }
+
+        if self.emph {
+            variant.style = match variant.style {
+                FontStyle::Normal => FontStyle::Italic,
+                FontStyle::Italic => FontStyle::Normal,
+                FontStyle::Oblique => FontStyle::Normal,
+            }
+        }
+
+        variant
+    }
+
+    /// The resolved family iterator.
+    pub fn families(&self) -> impl Iterator<Item = &str> + Clone {
+        let head = self
+            .monospace
+            .then(|| self.families.monospace.as_slice())
+            .unwrap_or_default();
+
+        let core = self.families.list.iter().flat_map(move |family| {
+            match family {
+                FontFamily::Named(name) => std::slice::from_ref(name),
+                FontFamily::Serif => &self.families.serif,
+                FontFamily::SansSerif => &self.families.sans_serif,
+                FontFamily::Monospace => &self.families.monospace,
+            }
+        });
+
+        head.iter()
+            .chain(core)
+            .chain(self.families.base.iter())
+            .map(String::as_str)
+    }
+
+    /// Access the `families` state mutably.
+    pub fn families_mut(&mut self) -> &mut FamilyState {
+        Rc::make_mut(&mut self.families)
+    }
+}
+
+impl Default for FontState {
+    fn default() -> Self {
+        Self {
+            families: Rc::new(FamilyState::default()),
+            variant: FontVariant {
+                style: FontStyle::Normal,
+                weight: FontWeight::REGULAR,
+                stretch: FontStretch::NORMAL,
+            },
+            strong: false,
+            emph: false,
+            monospace: false,
+            size: Length::pt(11.0),
+            top_edge: VerticalFontMetric::CapHeight,
+            bottom_edge: VerticalFontMetric::Baseline,
+            fill: Paint::Color(Color::Rgba(RgbaColor::BLACK)),
+            strikethrough: None,
+            underline: None,
+            overline: None,
+        }
+    }
+}
+
+/// Font family definitions.
+#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+pub struct FamilyState {
+    /// The user-defined list of font families.
+    pub list: Rc<Vec<FontFamily>>,
+    /// Definition of serif font families.
+    pub serif: Rc<Vec<String>>,
+    /// Definition of sans-serif font families.
+    pub sans_serif: Rc<Vec<String>>,
+    /// Definition of monospace font families used for raw text.
+    pub monospace: Rc<Vec<String>>,
+    /// Base fonts that are tried as last resort.
+    pub base: Rc<Vec<String>>,
+}
+
+impl Default for FamilyState {
+    fn default() -> Self {
+        Self {
+            list: Rc::new(vec![FontFamily::Serif]),
+            serif: Rc::new(vec!["eb garamond".into()]),
+            sans_serif: Rc::new(vec!["pt sans".into()]),
+            monospace: Rc::new(vec!["inconsolata".into()]),
+            base: Rc::new(vec![
+                "twitter color emoji".into(),
+                "latin modern math".into(),
+            ]),
+        }
+    }
+}
+
+/// Defines a line that is positioned over, under or on top of text.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
+pub struct LineState {
+    /// Stroke color of the line, defaults to the text color if `None`.
+    pub stroke: Option<Paint>,
+    /// Thickness of the line's strokes (dependent on scaled font size), read
+    /// from the font tables if `None`.
+    pub thickness: Option<Linear>,
+    /// Position of the line relative to the baseline (dependent on scaled font
+    /// size), read from the font tables if `None`.
+    pub offset: Option<Linear>,
+    /// Amount that the line will be longer or shorter than its associated text
+    /// (dependent on scaled font size).
+    pub extent: Linear,
+}
diff --git a/src/eval/template.rs b/src/eval/template.rs
index 96aa8a86..595e5554 100644
--- a/src/eval/template.rs
+++ b/src/eval/template.rs
@@ -1,28 +1,145 @@
-use std::collections::HashMap;
 use std::convert::TryFrom;
 use std::fmt::{self, Debug, Display, Formatter};
-use std::ops::{Add, AddAssign, Deref};
+use std::mem;
+use std::ops::{Add, AddAssign};
 use std::rc::Rc;
 
-use super::{Str, Value};
+use super::{State, Str};
 use crate::diag::StrResult;
-use crate::exec::ExecContext;
-use crate::syntax::{Expr, SyntaxTree};
+use crate::geom::{Align, Dir, Gen, GenAxis, Length, Linear, Sides, Size};
+use crate::layout::{
+    LayoutNode, LayoutTree, PadNode, PageRun, ParChild, ParNode, StackChild, StackNode,
+};
 use crate::util::EcoString;
 
 /// A template value: `[*Hi* there]`.
-#[derive(Debug, Default, Clone)]
+#[derive(Default, Clone)]
 pub struct Template(Rc<Vec<TemplateNode>>);
 
+/// One node in a template.
+#[derive(Clone)]
+enum TemplateNode {
+    /// A word space.
+    Space,
+    /// A line break.
+    Linebreak,
+    /// A paragraph break.
+    Parbreak,
+    /// A page break.
+    Pagebreak(bool),
+    /// Plain text.
+    Text(EcoString),
+    /// Spacing.
+    Spacing(GenAxis, Linear),
+    /// An inline node builder.
+    Inline(Rc<dyn Fn(&State) -> LayoutNode>),
+    /// An block node builder.
+    Block(Rc<dyn Fn(&State) -> LayoutNode>),
+    /// Save the current state.
+    Save,
+    /// Restore the last saved state.
+    Restore,
+    /// A function that can modify the current state.
+    Modify(Rc<dyn Fn(&mut State)>),
+}
+
 impl Template {
-    /// Create a new template from a vector of nodes.
-    pub fn new(nodes: Vec<TemplateNode>) -> Self {
-        Self(Rc::new(nodes))
+    /// Create a new, empty template.
+    pub fn new() -> Self {
+        Self(Rc::new(vec![]))
+    }
+
+    /// Create a template from a builder for an inline-level node.
+    pub fn from_inline<F, T>(f: F) -> Self
+    where
+        F: Fn(&State) -> T + 'static,
+        T: Into<LayoutNode>,
+    {
+        let node = TemplateNode::Inline(Rc::new(move |s| f(s).into()));
+        Self(Rc::new(vec![node]))
+    }
+
+    /// Create a template from a builder for a block-level node.
+    pub fn from_block<F, T>(f: F) -> Self
+    where
+        F: Fn(&State) -> T + 'static,
+        T: Into<LayoutNode>,
+    {
+        let node = TemplateNode::Block(Rc::new(move |s| f(s).into()));
+        Self(Rc::new(vec![node]))
+    }
+
+    /// Add a word space to the template.
+    pub fn space(&mut self) {
+        self.make_mut().push(TemplateNode::Space);
+    }
+
+    /// Add a line break to the template.
+    pub fn linebreak(&mut self) {
+        self.make_mut().push(TemplateNode::Linebreak);
+    }
+
+    /// Add a paragraph break to the template.
+    pub fn parbreak(&mut self) {
+        self.make_mut().push(TemplateNode::Parbreak);
+    }
+
+    /// Add a page break to the template.
+    pub fn pagebreak(&mut self, keep: bool) {
+        self.make_mut().push(TemplateNode::Pagebreak(keep));
+    }
+
+    /// Add text to the template.
+    pub fn text(&mut self, text: impl Into<EcoString>) {
+        self.make_mut().push(TemplateNode::Text(text.into()));
+    }
+
+    /// Add text, but in monospace.
+    pub fn monospace(&mut self, text: impl Into<EcoString>) {
+        self.save();
+        self.modify(|state| state.font_mut().monospace = true);
+        self.text(text);
+        self.restore();
+    }
+
+    /// Add spacing along an axis.
+    pub fn spacing(&mut self, axis: GenAxis, spacing: Linear) {
+        self.make_mut().push(TemplateNode::Spacing(axis, spacing));
+    }
+
+    /// Register a restorable snapshot.
+    pub fn save(&mut self) {
+        self.make_mut().push(TemplateNode::Save);
+    }
+
+    /// Ensure that later nodes are untouched by state modifications made since
+    /// the last snapshot.
+    pub fn restore(&mut self) {
+        self.make_mut().push(TemplateNode::Restore);
     }
 
-    /// Iterate over the contained template nodes.
-    pub fn iter(&self) -> std::slice::Iter<TemplateNode> {
-        self.0.iter()
+    /// Modify the state.
+    pub fn modify<F>(&mut self, f: F)
+    where
+        F: Fn(&mut State) + 'static,
+    {
+        self.make_mut().push(TemplateNode::Modify(Rc::new(f)));
+    }
+
+    /// Build the stack node resulting from instantiating the template in the
+    /// given state.
+    pub fn to_stack(&self, state: &State) -> StackNode {
+        let mut builder = Builder::new(state, false);
+        builder.template(self);
+        builder.build_stack()
+    }
+
+    /// Build the layout tree resulting from instantiating the template in the
+    /// given state.
+    pub fn to_tree(&self, state: &State) -> LayoutTree {
+        let mut builder = Builder::new(state, true);
+        builder.template(self);
+        builder.build_tree()
     }
 
     /// Repeat this template `n` times.
@@ -33,9 +150,14 @@ impl Template {
             .ok_or_else(|| format!("cannot repeat this template {} times", n))?;
 
         Ok(Self(Rc::new(
-            self.iter().cloned().cycle().take(count).collect(),
+            self.0.iter().cloned().cycle().take(count).collect(),
         )))
     }
+
+    /// Return a mutable reference to the inner vector.
+    fn make_mut(&mut self) -> &mut Vec<TemplateNode> {
+        Rc::make_mut(&mut self.0)
+    }
 }
 
 impl Display for Template {
@@ -44,6 +166,12 @@ impl Display for Template {
     }
 }
 
+impl Debug for Template {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        f.pad("Template { .. }")
+    }
+}
+
 impl PartialEq for Template {
     fn eq(&self, other: &Self) -> bool {
         Rc::ptr_eq(&self.0, &other.0)
@@ -73,7 +201,7 @@ impl Add<Str> for Template {
     type Output = Self;
 
     fn add(mut self, rhs: Str) -> Self::Output {
-        Rc::make_mut(&mut self.0).push(TemplateNode::Str(rhs.into()));
+        Rc::make_mut(&mut self.0).push(TemplateNode::Text(rhs.into()));
         self
     }
 }
@@ -82,86 +210,306 @@ impl Add<Template> for Str {
     type Output = Template;
 
     fn add(self, mut rhs: Template) -> Self::Output {
-        Rc::make_mut(&mut rhs.0).insert(0, TemplateNode::Str(self.into()));
+        Rc::make_mut(&mut rhs.0).insert(0, TemplateNode::Text(self.into()));
         rhs
     }
 }
 
-impl From<TemplateTree> for Template {
-    fn from(tree: TemplateTree) -> Self {
-        Self::new(vec![TemplateNode::Tree(tree)])
-    }
+/// Transforms from template to layout representation.
+struct Builder {
+    /// The active state.
+    state: State,
+    /// Snapshots of the state.
+    snapshots: Vec<State>,
+    /// The tree of finished page runs.
+    tree: LayoutTree,
+    /// When we are building the top-level layout trees, this contains metrics
+    /// of the page. While building a stack, this is `None`.
+    page: Option<PageBuilder>,
+    /// The currently built stack of paragraphs.
+    stack: StackBuilder,
 }
 
-impl From<TemplateFunc> for Template {
-    fn from(func: TemplateFunc) -> Self {
-        Self::new(vec![TemplateNode::Func(func)])
+impl Builder {
+    /// Create a new builder with a base state.
+    fn new(state: &State, pages: bool) -> Self {
+        Self {
+            state: state.clone(),
+            snapshots: vec![],
+            tree: LayoutTree { runs: vec![] },
+            page: pages.then(|| PageBuilder::new(state, true)),
+            stack: StackBuilder::new(state),
+        }
+    }
+
+    /// Build a template.
+    fn template(&mut self, template: &Template) {
+        for node in template.0.iter() {
+            self.node(node);
+        }
+    }
+
+    /// Build a template node.
+    fn node(&mut self, node: &TemplateNode) {
+        match node {
+            TemplateNode::Save => self.snapshots.push(self.state.clone()),
+            TemplateNode::Restore => {
+                let state = self.snapshots.pop().unwrap();
+                let newpage = state.page != self.state.page;
+                self.state = state;
+                if newpage {
+                    self.pagebreak(true, false);
+                }
+            }
+            TemplateNode::Space => self.space(),
+            TemplateNode::Linebreak => self.linebreak(),
+            TemplateNode::Parbreak => self.parbreak(),
+            TemplateNode::Pagebreak(keep) => self.pagebreak(*keep, true),
+            TemplateNode::Text(text) => self.text(text),
+            TemplateNode::Spacing(axis, amount) => self.spacing(*axis, *amount),
+            TemplateNode::Inline(f) => self.inline(f(&self.state)),
+            TemplateNode::Block(f) => self.block(f(&self.state)),
+            TemplateNode::Modify(f) => f(&mut self.state),
+        }
+    }
+
+    /// Push a word space into the active paragraph.
+    fn space(&mut self) {
+        self.stack.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'));
+    }
+
+    /// Apply a forced paragraph break.
+    fn parbreak(&mut self) {
+        let amount = self.state.par_spacing();
+        self.stack.finish_par(&self.state);
+        self.stack.push_soft(StackChild::Spacing(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.state, hard));
+            let stack = mem::replace(&mut self.stack, StackBuilder::new(&self.state));
+            self.tree.runs.extend(page.build(stack.build(), keep));
+        }
+    }
+
+    /// Push text into the active paragraph.
+    ///
+    /// The text is split into lines at newlines.
+    fn text(&mut self, text: impl Into<EcoString>) {
+        self.stack.par.push(self.make_text_node(text));
+    }
+
+    /// Push an inline node into the active paragraph.
+    fn inline(&mut self, node: impl Into<LayoutNode>) {
+        let align = self.state.aligns.cross;
+        self.stack.par.push(ParChild::Any(node.into(), align));
+    }
+
+    /// Push a block node into the active stack, finishing the active paragraph.
+    fn block(&mut self, node: impl Into<LayoutNode>) {
+        self.parbreak();
+        let aligns = self.state.aligns;
+        self.stack.push(StackChild::Any(node.into(), aligns));
+        self.parbreak();
     }
-}
 
-impl From<Str> for Template {
-    fn from(string: Str) -> Self {
-        Self::new(vec![TemplateNode::Str(string.into())])
+    /// Push spacing into the active paragraph or stack depending on the `axis`.
+    fn spacing(&mut self, axis: GenAxis, amount: Linear) {
+        match axis {
+            GenAxis::Main => {
+                self.stack.finish_par(&self.state);
+                self.stack.push_hard(StackChild::Spacing(amount));
+            }
+            GenAxis::Cross => {
+                self.stack.par.push_hard(ParChild::Spacing(amount));
+            }
+        }
+    }
+
+    /// Finish building and return the created stack.
+    fn build_stack(self) -> StackNode {
+        assert!(self.page.is_none());
+        self.stack.build()
+    }
+
+    /// Finish building and return the created layout tree.
+    fn build_tree(mut self) -> LayoutTree {
+        assert!(self.page.is_some());
+        self.pagebreak(true, false);
+        self.tree
+    }
+
+    /// Construct a text node with the given text and settings from the active
+    /// state.
+    fn make_text_node(&self, text: impl Into<EcoString>) -> ParChild {
+        ParChild::Text(
+            text.into(),
+            self.state.aligns.cross,
+            Rc::clone(&self.state.font),
+        )
     }
 }
 
-/// One node of a template.
-///
-/// Evaluating a template expression creates only a single node. Adding multiple
-/// templates can yield multi-node templates.
-#[derive(Debug, Clone)]
-pub enum TemplateNode {
-    /// A template that was evaluated from a template expression.
-    Tree(TemplateTree),
-    /// A function template that can implement custom behaviour.
-    Func(TemplateFunc),
-    /// A template that was converted from a string.
-    Str(EcoString),
+struct PageBuilder {
+    size: Size,
+    padding: Sides<Linear>,
+    hard: bool,
 }
 
-/// A template that consists of a syntax tree plus already evaluated
-/// expressions.
-#[derive(Debug, Clone)]
-pub struct TemplateTree {
-    /// The syntax tree of the corresponding template expression.
-    pub tree: Rc<SyntaxTree>,
-    /// The evaluated expressions in the syntax tree.
-    pub map: ExprMap,
+impl PageBuilder {
+    fn new(state: &State, hard: bool) -> Self {
+        Self {
+            size: state.page.size,
+            padding: state.page.margins(),
+            hard,
+        }
+    }
+
+    fn build(self, child: StackNode, keep: bool) -> Option<PageRun> {
+        let Self { size, padding, hard } = self;
+        (!child.children.is_empty() || (keep && hard)).then(|| PageRun {
+            size,
+            child: PadNode { padding, child: child.into() }.into(),
+        })
+    }
 }
 
-/// A map from expressions to the values they evaluated to.
-///
-/// The raw pointers point into the expressions contained in some
-/// [`SyntaxTree`]. Since the lifetime is erased, the tree could go out of scope
-/// while the hash map still lives. Although this could lead to lookup panics,
-/// it is safe since the pointers are never dereferenced.
-pub type ExprMap = HashMap<*const Expr, Value>;
+struct StackBuilder {
+    dirs: Gen<Dir>,
+    children: Vec<StackChild>,
+    last: Last<StackChild>,
+    par: ParBuilder,
+}
 
-/// A reference-counted dynamic template node that can implement custom
-/// behaviour.
-#[derive(Clone)]
-pub struct TemplateFunc(Rc<dyn Fn(&mut ExecContext)>);
+impl StackBuilder {
+    fn new(state: &State) -> Self {
+        Self {
+            dirs: state.dirs,
+            children: vec![],
+            last: Last::None,
+            par: ParBuilder::new(state),
+        }
+    }
 
-impl TemplateFunc {
-    /// Create a new function template from a rust function or closure.
-    pub fn new<F>(f: F) -> Self
-    where
-        F: Fn(&mut ExecContext) + 'static,
-    {
-        Self(Rc::new(f))
+    fn push(&mut self, child: StackChild) {
+        self.children.extend(self.last.any());
+        self.children.push(child);
+    }
+
+    fn push_soft(&mut self, child: StackChild) {
+        self.last.soft(child);
+    }
+
+    fn push_hard(&mut self, child: StackChild) {
+        self.last.hard();
+        self.children.push(child);
+    }
+
+    fn finish_par(&mut self, state: &State) {
+        let par = mem::replace(&mut self.par, ParBuilder::new(state));
+        if let Some(par) = par.build() {
+            self.push(par);
+        }
+    }
+
+    fn build(self) -> StackNode {
+        let Self { dirs, mut children, par, mut last } = self;
+        if let Some(par) = par.build() {
+            children.extend(last.any());
+            children.push(par);
+        }
+        StackNode { dirs, aspect: None, children }
     }
 }
 
-impl Debug for TemplateFunc {
-    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        f.debug_struct("TemplateFunc").finish()
+struct ParBuilder {
+    aligns: Gen<Align>,
+    dir: Dir,
+    line_spacing: Length,
+    children: Vec<ParChild>,
+    last: Last<ParChild>,
+}
+
+impl ParBuilder {
+    fn new(state: &State) -> Self {
+        Self {
+            aligns: state.aligns,
+            dir: state.dirs.cross,
+            line_spacing: state.line_spacing(),
+            children: vec![],
+            last: Last::None,
+        }
+    }
+
+    fn push(&mut self, child: ParChild) {
+        if let Some(soft) = self.last.any() {
+            self.push_inner(soft);
+        }
+        self.push_inner(child);
+    }
+
+    fn push_soft(&mut self, child: ParChild) {
+        self.last.soft(child);
+    }
+
+    fn push_hard(&mut self, child: ParChild) {
+        self.last.hard();
+        self.push_inner(child);
+    }
+
+    fn push_inner(&mut self, child: ParChild) {
+        if let ParChild::Text(curr_text, curr_props, curr_align) = &child {
+            if let Some(ParChild::Text(prev_text, prev_props, prev_align)) =
+                self.children.last_mut()
+            {
+                if prev_align == curr_align && prev_props == curr_props {
+                    prev_text.push_str(&curr_text);
+                    return;
+                }
+            }
+        }
+
+        self.children.push(child);
+    }
+
+    fn build(self) -> Option<StackChild> {
+        let Self { aligns, dir, line_spacing, children, .. } = self;
+        (!children.is_empty()).then(|| {
+            let node = ParNode { dir, line_spacing, children };
+            StackChild::Any(node.into(), aligns)
+        })
     }
 }
 
-impl Deref for TemplateFunc {
-    type Target = dyn Fn(&mut ExecContext);
+/// Finite state machine for spacing coalescing.
+enum Last<N> {
+    None,
+    Any,
+    Soft(N),
+}
+
+impl<N> Last<N> {
+    fn any(&mut self) -> Option<N> {
+        match mem::replace(self, Self::Any) {
+            Self::Soft(soft) => Some(soft),
+            _ => None,
+        }
+    }
+
+    fn soft(&mut self, soft: N) {
+        if let Self::Any = self {
+            *self = Self::Soft(soft);
+        }
+    }
 
-    fn deref(&self) -> &Self::Target {
-        self.0.as_ref()
+    fn hard(&mut self) {
+        *self = Self::None;
     }
 }
diff --git a/src/eval/value.rs b/src/eval/value.rs
index 62899cc1..99efc2e5 100644
--- a/src/eval/value.rs
+++ b/src/eval/value.rs
@@ -3,10 +3,9 @@ use std::cmp::Ordering;
 use std::fmt::{self, Debug, Display, Formatter};
 use std::rc::Rc;
 
-use super::{ops, Array, Dict, Function, Str, Template, TemplateFunc};
+use super::{ops, Array, Dict, Function, Str, Template};
 use crate::color::{Color, RgbaColor};
 use crate::diag::StrResult;
-use crate::exec::ExecContext;
 use crate::geom::{Angle, Fractional, Length, Linear, Relative};
 use crate::syntax::Spanned;
 use crate::util::EcoString;
@@ -51,14 +50,6 @@ pub enum Value {
 }
 
 impl Value {
-    /// Create a new template consisting of a single function node.
-    pub fn template<F>(f: F) -> Self
-    where
-        F: Fn(&mut ExecContext) + 'static,
-    {
-        Self::Template(TemplateFunc::new(f).into())
-    }
-
     /// The name of the stored value's type.
     pub fn type_name(&self) -> &'static str {
         match self {
-- 
cgit v1.2.3