Implement flex and box layouting 📏

4 files changed, 414 insertions, 94 deletions

diff --git a/src/layout/boxed.rs b/src/layout/boxed.rs
index b75ea75a..2ee2dbdc 100644
--- a/src/layout/boxed.rs
+++ b/src/layout/boxed.rs
@@ -1,17 +1,18 @@
-//! Definitive layouting of boxes.
+//! Block-style layouting of boxes.
 
 use crate::doc::{Document, Page, TextAction};
 use crate::font::Font;
-use super::{Layouter, LayoutContext, Size2D};
+use crate::size::{Size, Size2D};
+use super::LayoutSpace;
 
 
-/// A box layout has a fixed width and height and consists of actions.
+/// A box layout has a fixed width and height and composes of actions.
 #[derive(Debug, Clone)]
 pub struct BoxLayout {
     /// The size of the box.
-    dimensions: Size2D,
+    pub dimensions: Size2D,
     /// The actions composing this layout.
-    actions: Vec<TextAction>,
+    pub actions: Vec<TextAction>,
 }
 
 impl BoxLayout {
@@ -28,25 +29,68 @@ impl BoxLayout {
     }
 }
 
+/// The context for layouting boxes.
+#[derive(Debug, Copy, Clone)]
+pub struct BoxContext {
+    /// The space to layout the boxes in.
+    pub space: LayoutSpace,
+}
+
 /// Layouts boxes block-style.
 #[derive(Debug)]
-pub struct BoxLayouter<'a, 'p> {
-    ctx: &'a LayoutContext<'a, 'p>,
+pub struct BoxLayouter {
+    ctx: BoxContext,
     actions: Vec<TextAction>,
+    dimensions: Size2D,
+    usable: Size2D,
+    cursor: Size2D,
 }
 
-impl<'a, 'p> BoxLayouter<'a, 'p> {
+impl BoxLayouter {
     /// Create a new box layouter.
-    pub fn new(ctx: &'a LayoutContext<'a, 'p>) -> BoxLayouter<'a, 'p> {
+    pub fn new(ctx: BoxContext) -> BoxLayouter {
+        let space = ctx.space;
         BoxLayouter {
             ctx,
             actions: vec![],
+            dimensions: Size2D::zero(),
+            usable: space.usable(),
+            cursor: Size2D::new(space.padding.left, space.padding.right),
         }
     }
 
     /// Add a sublayout.
     pub fn add_box(&mut self, layout: BoxLayout) {
-        unimplemented!()
+        // In the flow direction (vertical) add the layout and in the second
+        // direction just consider the maximal size of any child layout.
+        let new = Size2D {
+            x: crate::size::max(self.dimensions.x, layout.dimensions.x),
+            y: self.dimensions.y + layout.dimensions.y,
+        };
+
+        if self.overflows(new) {
+            panic!("box layouter: would overflow in add_box");
+        }
+
+        // Apply the dimensions because they fit.
+        self.dimensions = new;
+
+        // Move all actions into this layout and translate absolute positions.
+        self.actions.push(TextAction::MoveAbsolute(self.cursor));
+        self.actions.extend(super::translate_actions(self.cursor, layout.actions));
+
+        // Adjust the cursor.
+        self.cursor.y += layout.dimensions.y;
+    }
+
+    /// Add some space in between two boxes.
+    pub fn add_space(&mut self, space: Size) {
+        if self.overflows(self.dimensions + Size2D::with_y(space)) {
+            panic!("box layouter: would overflow in add_space");
+        }
+
+        self.cursor.y += space;
+        self.dimensions.y += space;
     }
 
     /// Add a sublayout at an absolute position.
@@ -54,20 +98,34 @@ impl<'a, 'p> BoxLayouter<'a, 'p> {
         self.actions.push(TextAction::MoveAbsolute(position));
         self.actions.extend(layout.actions);
     }
-}
 
-impl Layouter for BoxLayouter<'_, '_> {
-    type Layout = BoxLayout;
+    /// Whether this layouter contains any items.
+    pub fn is_empty(&self) -> bool {
+        self.actions.is_empty()
+    }
+
+    /// The remaining space for new boxes.
+    pub fn remaining(&self) -> Size2D {
+        Size2D {
+            x: self.usable.x,
+            y: self.usable.y - self.dimensions.y,
+        }
+    }
 
     /// Finish the layouting and create a box layout from this.
-    fn finish(self) -> BoxLayout {
+    pub fn finish(self) -> BoxLayout {
         BoxLayout {
-            dimensions: self.ctx.space.dimensions.clone(),
-            actions: self.actions
+            dimensions: if self.ctx.space.shrink_to_fit {
+                self.dimensions.padded(self.ctx.space.padding)
+            } else {
+                self.ctx.space.dimensions
+            },
+            actions: self.actions,
         }
     }
 
-    fn is_empty(&self) -> bool {
-        self.actions.is_empty()
+    /// Whether the given box is bigger than what we can hold.
+    fn overflows(&self, dimensions: Size2D) -> bool {
+        dimensions.x > self.usable.x || dimensions.y > self.usable.y
     }
 }
diff --git a/src/layout/flex.rs b/src/layout/flex.rs
index faddc95a..924ebec5 100644
--- a/src/layout/flex.rs
+++ b/src/layout/flex.rs
@@ -1,61 +1,171 @@
 //! Flexible and lazy layouting of boxes.
 
-use super::{Layouter, LayoutContext, BoxLayout};
+use crate::doc::TextAction;
+use crate::size::Size2D;
+use super::{LayoutSpace, BoxLayout};
 
 
 /// A flex layout consists of a yet unarranged list of boxes.
 #[derive(Debug, Clone)]
 pub struct FlexLayout {
     /// The sublayouts composing this layout.
-    layouts: Vec<BoxLayout>,
+    pub units: Vec<FlexUnit>,
+    /// The layout space to arrange in.
+    pub ctx: FlexContext,
 }
 
-impl FlexLayout {
-    /// Compute the layout.
-    pub fn into_box(self) -> BoxLayout {
-        // TODO: Do the justification.
-        unimplemented!()
-    }
-}
-
-/// Layouts boxes next to each other (inline-style) lazily.
-#[derive(Debug)]
-pub struct FlexLayouter<'a, 'p> {
-    ctx: &'a LayoutContext<'a, 'p>,
-    layouts: Vec<BoxLayout>,
+/// A unit in a flex layout.
+#[derive(Debug, Clone)]
+pub enum FlexUnit {
+    /// A content unit to be arranged flexibly.
+    Boxed(BoxLayout),
+    /// A unit which acts as glue between two [`FlexUnit::Boxed`] units and
+    /// is only present if there was no flow break in between the two surrounding boxes.
+    Glue(BoxLayout),
 }
 
-impl<'a, 'p> FlexLayouter<'a, 'p> {
+impl FlexLayout {
     /// Create a new flex layouter.
-    pub fn new(ctx: &'a LayoutContext<'a, 'p>) -> FlexLayouter<'a, 'p> {
-        FlexLayouter {
+    pub fn new(ctx: FlexContext) -> FlexLayout {
+        FlexLayout {
             ctx,
-            layouts: vec![],
+            units: vec![],
         }
     }
 
     /// Add a sublayout.
     pub fn add_box(&mut self, layout: BoxLayout) {
-        self.layouts.push(layout);
+        self.units.push(FlexUnit::Boxed(layout));
+    }
+
+    /// Add a glue layout which can be replaced by a line break.
+    pub fn add_glue(&mut self, glue: BoxLayout) {
+        self.units.push(FlexUnit::Glue(glue));
     }
 
     /// Add all sublayouts of another flex layout.
     pub fn add_flexible(&mut self, layout: FlexLayout) {
-        self.layouts.extend(layout.layouts);
+        self.units.extend(layout.units);
+    }
+
+    /// Whether this layouter contains any items.
+    pub fn is_empty(&self) -> bool {
+        self.units.is_empty()
+    }
+
+    /// Compute the justified layout.
+    pub fn into_box(self) -> BoxLayout {
+        FlexFinisher::new(self).finish()
     }
 }
 
-impl Layouter for FlexLayouter<'_, '_> {
-    type Layout = FlexLayout;
+/// The context for flex layouting.
+#[derive(Debug, Copy, Clone)]
+pub struct FlexContext {
+    /// The space to layout the boxes in.
+    pub space: LayoutSpace,
+    /// The flex spacing (like line spacing).
+    pub flex_spacing: f32,
+}
 
-    /// Finish the layouting and create a flexible layout from this.
-    fn finish(self) -> FlexLayout {
-        FlexLayout {
-            layouts: self.layouts
+/// Finishes a flex layout by justifying the positions of the individual boxes.
+#[derive(Debug)]
+struct FlexFinisher {
+    units: Vec<FlexUnit>,
+    ctx: FlexContext,
+    actions: Vec<TextAction>,
+    dimensions: Size2D,
+    usable: Size2D,
+    cursor: Size2D,
+    line: Size2D,
+}
+
+impl FlexFinisher {
+    /// Create the finisher from the layout.
+    fn new(layout: FlexLayout) -> FlexFinisher {
+        let space = layout.ctx.space;
+        FlexFinisher {
+            units: layout.units,
+            ctx: layout.ctx,
+            actions: vec![],
+            dimensions: Size2D::zero(),
+            usable: space.usable(),
+            cursor: Size2D::new(space.padding.left, space.padding.top),
+            line: Size2D::zero(),
+        }
+    }
+
+    /// Finish the flex layout into the justified box layout.
+    fn finish(mut self) -> BoxLayout {
+        // Move the units out of the layout.
+        let units = self.units;
+        self.units = vec![];
+
+        // Arrange the units.
+        for unit in units {
+            match unit {
+                FlexUnit::Boxed(boxed) => self.boxed(boxed),
+                FlexUnit::Glue(glue) => self.glue(glue),
+            }
         }
+
+        // Flush everything to get the correct dimensions.
+        self.newline();
+
+        BoxLayout {
+            dimensions: if self.ctx.space.shrink_to_fit {
+                self.dimensions.padded(self.ctx.space.padding)
+            } else {
+                self.ctx.space.dimensions
+            },
+            actions: self.actions,
+        }
+    }
+
+    /// Layout the box.
+    fn boxed(&mut self, boxed: BoxLayout) {
+        // Move to the next line if necessary.
+        if self.line.x + boxed.dimensions.x > self.usable.x {
+            // If it still does not fit, we stand no chance.
+            if boxed.dimensions.x > self.usable.x {
+                panic!("flex layouter: box is to wide");
+            }
+
+            self.newline();
+        }
+
+        self.append(boxed);
+    }
+
+    /// Layout the glue.
+    fn glue(&mut self, glue: BoxLayout) {
+        // Only add the glue if it fits on the line, otherwise move to the next line.
+        if self.line.x + glue.dimensions.x > self.usable.x {
+            self.newline();
+        } else {
+            self.append(glue);
+        }
+    }
+
+    /// Append a box to the layout without checking anything.
+    fn append(&mut self, layout: BoxLayout) {
+        // Move all actions into this layout and translate absolute positions.
+        self.actions.push(TextAction::MoveAbsolute(self.cursor));
+        self.actions.extend(super::translate_actions(self.cursor, layout.actions));
+
+        // Adjust the sizes.
+        self.line.x += layout.dimensions.x;
+        self.line.y = crate::size::max(self.line.y, layout.dimensions.y);
+        self.cursor.x += layout.dimensions.x;
     }
 
-    fn is_empty(&self) -> bool {
-        self.layouts.is_empty()
+    /// Move to the next line.
+    fn newline(&mut self) {
+        self.line.y *= self.ctx.flex_spacing;
+        self.dimensions.x = crate::size::max(self.dimensions.x, self.line.x);
+        self.dimensions.y += self.line.y;
+        self.cursor.x = self.ctx.space.padding.left;
+        self.cursor.y += self.line.y;
+        self.line = Size2D::zero();
     }
 }
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 8b0c3004..64eeb00a 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -1,28 +1,20 @@
 //! The layouting engine.
 
+use crate::doc::TextAction;
 use crate::font::{FontLoader, FontError};
-use crate::size::{Size2D, SizeBox};
+use crate::size::{Size, Size2D, SizeBox};
 use crate::syntax::{SyntaxTree, Node};
 use crate::style::TextStyle;
 
-mod boxed;
-mod flex;
+use self::flex::{FlexLayout, FlexContext};
+use self::boxed::{BoxLayout, BoxContext, BoxLayouter};
+use self::text::TextContext;
 
-pub use flex::{FlexLayout, FlexLayouter};
-pub use boxed::{BoxLayout, BoxLayouter};
+pub mod text;
+pub mod boxed;
+pub mod flex;
 
 
-/// Types that layout components and can be finished into some kind of layout.
-pub trait Layouter {
-    type Layout;
-
-    /// Finish the layouting and create the layout from this.
-    fn finish(self) -> Self::Layout;
-
-    /// Whether this layouter contains any items.
-    fn is_empty(&self) -> bool;
-}
-
 /// A collection of layouted content.
 #[derive(Debug, Clone)]
 pub enum Layout {
@@ -44,54 +36,152 @@ pub struct LayoutContext<'a, 'p> {
 }
 
 /// Spacial constraints for layouting.
-#[derive(Debug, Clone)]
+#[derive(Debug, Copy, Clone)]
 pub struct LayoutSpace {
     /// The maximum size of the box to layout in.
     pub dimensions: Size2D,
     /// Padding that should be respected on each side.
     pub padding: SizeBox,
+    /// Whether to shrink the dimensions to fit the content or the keep the
+    /// original ones.
+    pub shrink_to_fit: bool,
+}
+
+impl LayoutSpace {
+    /// The actually usable area.
+    pub fn usable(&self) -> Size2D {
+        Size2D {
+            x: self.dimensions.x - self.padding.left - self.padding.right,
+            y: self.dimensions.y - self.padding.top - self.padding.bottom,
+        }
+    }
 }
 
 /// Layout a syntax tree in a given context.
 pub fn layout(tree: &SyntaxTree, ctx: &LayoutContext) -> LayoutResult<BoxLayout> {
-    // The top-level layouter and the sub-level layouter.
-    let mut box_layouter = BoxLayouter::new(ctx);
-    let mut flex_layouter = FlexLayouter::new(ctx);
-
-    // The current text style.
-    let mut italic = false;
-    let mut bold = false;
-
-    // Walk all nodes and layout them.
-    for node in &tree.nodes {
-        match node {
-            Node::Text(text) => {
-                unimplemented!()
-            },
-            Node::Space => {
-                unimplemented!()
-            },
-            Node::Newline => {
-                unimplemented!()
-            },
+    Layouter::new(tree, ctx).layout()
+}
+
+/// Transforms a syntax tree into a box layout.
+#[derive(Debug)]
+struct Layouter<'a, 'p> {
+    tree: &'a SyntaxTree,
+    box_layouter: BoxLayouter,
+    flex_layout: FlexLayout,
+    flex_ctx: FlexContext,
+    text_ctx: TextContext<'a, 'p>,
+}
 
-            // Toggle the text styles.
-            Node::ToggleItalics => italic = !italic,
-            Node::ToggleBold => bold = !bold,
+impl<'a, 'p> Layouter<'a, 'p> {
+    /// Create a new layouter.
+    fn new(tree: &'a SyntaxTree, ctx: &LayoutContext<'a, 'p>) -> Layouter<'a, 'p> {
+        // The top-level context for arranging paragraphs.
+        let box_ctx = BoxContext { space: ctx.space };
+
+        // The sub-level context for arranging pieces of text.
+        let flex_ctx = FlexContext {
+            space: LayoutSpace {
+                dimensions: ctx.space.usable(),
+                padding: SizeBox::zero(),
+                shrink_to_fit: true,
+            },
+            flex_spacing: ctx.style.line_spacing,
+        };
+
+        // The mutable context for layouting single pieces of text.
+        let text_ctx = TextContext {
+            loader: &ctx.loader,
+            style: ctx.style.clone(),
+        };
+
+        Layouter {
+            tree,
+            box_layouter: BoxLayouter::new(box_ctx),
+            flex_layout: FlexLayout::new(flex_ctx),
+            flex_ctx,
+            text_ctx,
+        }
+    }
 
-            Node::Func(func) => {
-                unimplemented!()
+    /// Layout the tree into a box.
+    fn layout(mut self) -> LayoutResult<BoxLayout> {
+        // Walk all nodes and layout them.
+        for node in &self.tree.nodes {
+            match node {
+                // Layout a single piece of text.
+                Node::Text(text) => {
+                    let boxed = self::text::layout(text, &self.text_ctx)?;
+                    self.flex_layout.add_box(boxed);
+                },
+                Node::Space => {
+                    if !self.flex_layout.is_empty() {
+                        let boxed = self::text::layout(" ", &self.text_ctx)?;
+                        self.flex_layout.add_glue(boxed);
+                    }
+                },
+
+                // Finish the current flex layout and add it to the box layouter.
+                // Then start a new flex layouting process.
+                Node::Newline => {
+                    // Finish the current paragraph into a box and add it.
+                    self.add_paragraph_spacing();
+                    let boxed = self.flex_layout.into_box();
+                    self.box_layouter.add_box(boxed);
+
+                    // Create a fresh flex layout for the next paragraph.
+                    self.flex_ctx.space.dimensions = self.box_layouter.remaining();
+                    self.flex_layout = FlexLayout::new(self.flex_ctx);
+                },
+
+                // Toggle the text styles.
+                Node::ToggleItalics => self.text_ctx.style.italic = !self.text_ctx.style.italic,
+                Node::ToggleBold => self.text_ctx.style.bold = !self.text_ctx.style.bold,
+
+                // Execute a function.
+                Node::Func(_) => unimplemented!(),
             }
         }
+
+        // If there are remainings, add them to the layout.
+        if !self.flex_layout.is_empty() {
+            self.add_paragraph_spacing();
+            let boxed = self.flex_layout.into_box();
+            self.box_layouter.add_box(boxed);
+        }
+
+        Ok(self.box_layouter.finish())
     }
 
-    // If there are remainings, add them to the layout.
-    if !flex_layouter.is_empty() {
-        let boxed = flex_layouter.finish().into_box();
-        box_layouter.add_box(boxed);
+    /// Add the spacing between two paragraphs.
+    fn add_paragraph_spacing(&mut self) {
+        let size = Size::points(self.text_ctx.style.font_size)
+            * (self.text_ctx.style.line_spacing * self.text_ctx.style.paragraph_spacing - 1.0);
+        self.box_layouter.add_space(size);
     }
+}
+
+/// Translate a stream of text actions by an offset.
+pub fn translate_actions<I>(offset: Size2D, actions: I) -> TranslatedActions<I::IntoIter>
+    where I: IntoIterator<Item=TextAction> {
+    TranslatedActions { offset, iter: actions.into_iter() }
+}
 
-    Ok(box_layouter.finish())
+/// An iterator over the translated text actions, created by [`translate_actions`].
+pub struct TranslatedActions<I> where I: Iterator<Item=TextAction> {
+    offset: Size2D,
+    iter: I,
+}
+
+impl<I> Iterator for TranslatedActions<I> where I: Iterator<Item=TextAction> {
+    type Item = TextAction;
+
+    fn next(&mut self) -> Option<TextAction> {
+        use TextAction::*;
+        self.iter.next().map(|action| match action {
+            MoveAbsolute(pos) => MoveAbsolute(pos + self.offset),
+            a => a,
+        })
+    }
 }
 
 /// The error type for layouting.
diff --git a/src/layout/text.rs b/src/layout/text.rs
new file mode 100644
index 00000000..8aa76c4c
--- /dev/null
+++ b/src/layout/text.rs
@@ -0,0 +1,62 @@
+//! Layouting of text into boxes.
+
+use crate::doc::TextAction;
+use crate::font::FontQuery;
+use crate::size::{Size, Size2D};
+use super::*;
+
+
+/// The context for text layouting.
+#[derive(Debug, Clone)]
+pub struct TextContext<'a, 'p> {
+    /// Loads fonts matching queries.
+    pub loader: &'a FontLoader<'p>,
+    /// Base style to set text with.
+    pub style: TextStyle,
+}
+
+/// Layout one piece of text without any breaks as one continous box.
+pub fn layout(text: &str, ctx: &TextContext) -> LayoutResult<BoxLayout> {
+    let mut actions = Vec::new();
+    let mut active_font = std::usize::MAX;
+    let mut buffer = String::new();
+    let mut width = Size::zero();
+
+    // Walk the characters.
+    for character in text.chars() {
+        // Retrieve the best font for this character.
+        let (index, font) = ctx.loader.get(FontQuery {
+            families: ctx.style.font_families.clone(),
+            italic: ctx.style.italic,
+            bold: ctx.style.bold,
+            character,
+        }).ok_or_else(|| LayoutError::NoSuitableFont(character))?;
+
+        // Add the char width to the total box width.
+        let char_width = font.widths[font.map(character) as usize] * ctx.style.font_size;
+        width += char_width;
+
+        // Change the font if necessary.
+        if active_font != index {
+            if !buffer.is_empty() {
+                actions.push(TextAction::WriteText(buffer));
+                buffer = String::new();
+            }
+
+            actions.push(TextAction::SetFont(index, ctx.style.font_size));
+            active_font = index;
+        }
+
+        buffer.push(character);
+    }
+
+    // Write the remaining characters.
+    if !buffer.is_empty() {
+        actions.push(TextAction::WriteText(buffer));
+    }
+
+    Ok(BoxLayout {
+        dimensions: Size2D::new(width, Size::points(ctx.style.font_size)),
+        actions,
+    })
+}