Implement font fallback 🚀

4 files changed, 273 insertions, 131 deletions

diff --git a/src/engine/mod.rs b/src/engine/mod.rs
index c588e5c3..d9d16965 100644
--- a/src/engine/mod.rs
+++ b/src/engine/mod.rs
@@ -1,8 +1,11 @@
 //! Core typesetting engine.
 
+use std::cell::{RefCell, Ref};
+use std::collections::HashMap;
+use std::mem::swap;
 use crate::syntax::{SyntaxTree, Node};
 use crate::doc::{Document, Page, Text, TextCommand};
-use crate::font::{Font, FontFamily, FontFilter, FontError};
+use crate::font::{Font, FontFamily, FontInfo, FontError};
 use crate::Context;
 
 mod size;
@@ -11,16 +14,21 @@ pub use size::Size;
 
 /// The core typesetting engine, transforming an abstract syntax tree into a document.
 pub struct Engine<'t> {
-    // Immutable
+    // Input
     tree: &'t SyntaxTree<'t>,
     ctx: &'t Context<'t>,
 
-    // Mutable
-    fonts: Vec<Font>,
-    active_font: usize,
+    // Internal
+    font_loader: FontLoader<'t>,
+
+    // Output
     text_commands: Vec<TextCommand>,
-    current_line: String,
-    current_width: Size,
+
+    // Intermediates
+    active_font: usize,
+    current_text: String,
+    current_line_width: Size,
+    current_max_vertical_move: Size,
 }
 
 impl<'t> Engine<'t> {
@@ -29,121 +37,287 @@ impl<'t> Engine<'t> {
         Engine {
             tree,
             ctx: context,
-            fonts: vec![],
-            active_font: 0,
+            font_loader: FontLoader::new(context),
             text_commands: vec![],
-            current_line: String::new(),
-            current_width: Size::zero(),
+            active_font: std::usize::MAX,
+            current_text: String::new(),
+            current_line_width: Size::zero(),
+            current_max_vertical_move: Size::zero(),
         }
     }
 
     /// Generate the abstract document.
     pub(crate) fn typeset(mut self) -> TypeResult<Document> {
-        // Load font defined by style
-        let mut font = None;
-        let filter = FontFilter::new(&self.ctx.style.font_families);
-        for provider in &self.ctx.font_providers {
-            let available = provider.available();
-            for info in available {
-                if filter.matches(info) {
-                    if let Some(mut source) = provider.get(info) {
-                        let mut program = Vec::new();
-                        source.read_to_end(&mut program)?;
-                        font = Some(Font::new(program)?);
-                        break;
-                    }
-                }
+        // Start by moving to a suitable position.
+        self.move_start();
+
+        // Iterate through the documents nodes.
+        for node in &self.tree.nodes {
+            match node {
+                Node::Word(word) => self.write_word(word)?,
+                Node::Space => self.write_space()?,
+                Node::Newline => (),
+                Node::ToggleItalics | Node::ToggleBold | Node::ToggleMath => unimplemented!(),
+                Node::Func(_) => unimplemented!(),
             }
         }
 
-        let font = match font {
-            Some(font) => font,
-            None => return Err(TypesetError::MissingFont),
-        };
+        // Flush the text buffer.
+        self.write_buffered_text();
+
+        let fonts =  self.font_loader.into_fonts();
 
-        self.fonts.push(font);
-        self.active_font = 0;
+        println!("fonts: {:?}", fonts.len());
+
+        // Create a document with one page from the contents.
+        Ok(Document {
+            pages: vec![Page {
+                width: self.ctx.style.width,
+                height: self.ctx.style.height,
+                text: vec![Text {
+                    commands: self.text_commands,
+                }],
+            }],
+            fonts,
+        })
+    }
 
+    /// Move to the starting position defined by the style.
+    fn move_start(&mut self) {
         // Move cursor to top-left position
         self.text_commands.push(TextCommand::Move(
             self.ctx.style.margin_left,
             self.ctx.style.height - self.ctx.style.margin_top
         ));
+    }
 
-        // Set the current font
-        self.text_commands.push(TextCommand::SetFont(0, self.ctx.style.font_size));
+    /// Move to a new line.
+    fn move_newline(&mut self) {
+        let vertical_move = - if self.current_max_vertical_move == Size::zero() {
+            // If max vertical move is still zero, the line is empty and we take the
+            // font size from the previous line.
+            self.ctx.style.font_size
+                * self.ctx.style.line_spacing
+                * self.font_loader.get_at(self.active_font).metrics.ascender
+        } else {
+            self.current_max_vertical_move
+        };
 
-        // Iterate through the documents nodes.
-        for node in &self.tree.nodes {
-            match node {
-                Node::Word(word) => self.write_word(word),
+        self.text_commands.push(TextCommand::Move(Size::zero(), vertical_move));
+        self.current_max_vertical_move = Size::zero();
+        self.current_line_width = Size::zero();
+    }
 
-                Node::Space => self.write_space(),
-                Node::Newline => (),
+    /// Set the current font.
+    fn set_font(&mut self, index: usize) {
+        self.text_commands.push(TextCommand::SetFont(index, self.ctx.style.font_size));
+        self.active_font = index;
+    }
 
-                Node::ToggleItalics | Node::ToggleBold | Node::ToggleMath => unimplemented!(),
-                Node::Func(_) => unimplemented!(),
+    /// Write a word.
+    fn write_word(&mut self, word: &str) -> TypeResult<()> {
+        let width = self.width(word)?;
+
+        // If this would overflow, we move to a new line and finally write the previous one.
+        if self.would_overflow(width) {
+            self.write_buffered_text();
+            self.move_newline();
+        }
+
+        for c in word.chars() {
+            let (index, _) = self.get_font_for(c)?;
+            if index != self.active_font {
+                self.write_buffered_text();
+                self.set_font(index);
             }
+            self.current_text.push(c);
+            let char_width = self.char_width(c).unwrap();
+            self.current_line_width += char_width;
         }
 
-        // Create a page from the contents.
-        let page = Page {
-            width: self.ctx.style.width,
-            height: self.ctx.style.height,
-            text: vec![Text {
-                commands: self.text_commands,
-            }],
-        };
+        Ok(())
+    }
 
-        Ok(Document {
-            pages: vec![page],
-            fonts: self.fonts,
-        })
+    /// Write the space character: `' '`.
+    fn write_space(&mut self) -> TypeResult<()> {
+        let space_width = self.char_width(' ')?;
+
+        if !self.would_overflow(space_width) && self.current_line_width > Size::zero() {
+            self.write_word(" ")?;
+        }
+
+        Ok(())
     }
 
-    fn write_word(&mut self, word: &str) {
-        let font = &self.fonts[self.active_font];
+    /// Write a text command with the buffered text.
+    fn write_buffered_text(&mut self) {
+        if !self.current_text.is_empty() {
+            let mut current_text = String::new();
+            swap(&mut self.current_text, &mut current_text);
+            self.text_commands.push(TextCommand::Text(current_text));
+        }
+    }
 
-        let width = self.width(word);
-        if self.would_overflow(width) {
-            let vertical_move = - self.ctx.style.font_size
-                * self.ctx.style.line_spacing
-                * font.metrics.ascender;
-            self.text_commands.push(TextCommand::Move(Size::zero(), vertical_move));
+    /// Whether the current line plus the extra `width` would overflow the line.
+    fn would_overflow(&self, width: Size) -> bool {
+        let max_width = self.ctx.style.width
+            - self.ctx.style.margin_left - self.ctx.style.margin_right;
+        self.current_line_width + width > max_width
+    }
 
-            self.current_line.clear();
-            self.current_width = Size::zero();
+    /// The width of a word when printed out.
+    fn width(&self, word: &str) -> TypeResult<Size> {
+        let mut width = Size::zero();
+        for c in word.chars() {
+            width += self.char_width(c)?;
         }
+        Ok(width)
+    }
 
-        self.text_commands.push(TextCommand::Text(word.to_owned()));
-        self.current_line.push_str(word);
-        self.current_width += width;
+    /// The width of a char when printed out.
+    fn char_width(&self, character: char) -> TypeResult<Size> {
+        let font = self.get_font_for(character)?.1;
+        Ok(font.widths[font.map(character) as usize] * self.ctx.style.font_size)
     }
 
-    fn write_space(&mut self) {
-        let space_width = self.width(" ");
+    /// Load a font that has the character we need.
+    fn get_font_for(&self, character: char) -> TypeResult<(usize, Ref<Font>)> {
+        let res = self.font_loader.get(FontQuery {
+            families: &self.ctx.style.font_families,
+            italic: false,
+            bold: false,
+            character,
+        }).ok_or_else(|| TypesetError::MissingFont)?;
+        Ok(res)
+    }
+}
+
+/// Serves matching fonts given a query.
+struct FontLoader<'t> {
+    /// The context containing the used font providers.
+    context: &'t Context<'t>,
+    /// All available fonts indexed by provider.
+    availables: Vec<&'t [FontInfo]>,
+    /// Allows to lookup fonts by their infos.
+    indices: RefCell<HashMap<FontInfo, usize>>,
+    /// Allows to retrieve cached results for queries.
+    matches: RefCell<HashMap<FontQuery<'t>, usize>>,
+    /// All loaded fonts.
+    loaded: RefCell<Vec<Font>>,
+    /// Indexed by outside and indices maps to internal indices.
+    external: RefCell<Vec<usize>>,
+}
 
-        if !self.would_overflow(space_width) && !self.current_line.is_empty() {
-            self.text_commands.push(TextCommand::Text(" ".to_owned()));
-            self.current_line.push_str(" ");
-            self.current_width += space_width;
+impl<'t> FontLoader<'t> {
+    /// Create a new font loader.
+    pub fn new(context: &'t Context<'t>) -> FontLoader {
+        let availables = context.font_providers.iter()
+            .map(|prov| prov.available()).collect();
+
+        FontLoader {
+            context,
+            availables,
+            indices: RefCell::new(HashMap::new()),
+            matches: RefCell::new(HashMap::new()),
+            loaded: RefCell::new(vec![]),
+            external: RefCell::new(vec![]),
         }
     }
 
-    fn width(&self, word: &str) -> Size {
-        let font = &self.fonts[self.active_font];
-        word.chars()
-            .map(|c| font.widths[font.map(c) as usize] * self.ctx.style.font_size)
-            .sum()
+    /// Return the list of fonts.
+    pub fn into_fonts(self) -> Vec<Font> {
+        // FIXME: Don't clone here.
+        let fonts = self.loaded.into_inner();
+        self.external.into_inner().into_iter().map(|index| fonts[index].clone()).collect()
     }
 
-    fn would_overflow(&self, width: Size) -> bool {
-        let max_width = self.ctx.style.width
-            - self.ctx.style.margin_left
-            - self.ctx.style.margin_right;
+    /// Return the best matching font and it's index (if there is any) given the query.
+    pub fn get(&self, query: FontQuery<'t>) -> Option<(usize, Ref<Font>)> {
+        if let Some(index) = self.matches.borrow().get(&query) {
+            let external = self.external.borrow().iter().position(|i| i == index).unwrap();
+            return Some((external, self.get_at_internal(*index)));
+        }
 
-        self.current_width + width > max_width
+        // Go through all available fonts and try to find one.
+        for family in query.families {
+            for (p, available) in self.availables.iter().enumerate() {
+                for info in available.iter() {
+                    if Self::matches(query, &family, info) {
+                        if let Some((index, font)) = self.try_load(info, p) {
+                            if font.mapping.contains_key(&query.character) {
+                                self.matches.borrow_mut().insert(query, index);
+
+                                let pos = self.external.borrow().iter().position(|&i| i == index);
+                                let external = pos.unwrap_or_else(|| {
+                                    let external = self.external.borrow().len();
+                                    self.external.borrow_mut().push(index);
+                                    external
+                                });
+
+                                return Some((external, font));
+                            }
+                        }
+                    }
+                }
+            }
+        }
+
+        None
+    }
+
+    /// Return a loaded font at an index. Panics if the index is out of bounds.
+    pub fn get_at(&self, index: usize) -> Ref<Font> {
+        let internal = self.external.borrow()[index];
+        self.get_at_internal(internal)
     }
+
+    /// Try to load the font with the given info from the provider.
+    fn try_load(&self, info: &FontInfo,  provider: usize) -> Option<(usize, Ref<Font>)> {
+        if let Some(index) = self.indices.borrow().get(info) {
+            return Some((*index, self.get_at_internal(*index)));
+        }
+
+        if let Some(mut source) = self.context.font_providers[provider].get(info) {
+            let mut program = Vec::new();
+            source.read_to_end(&mut program).ok()?;
+
+            let font = Font::new(program).ok()?;
+
+            let index = self.loaded.borrow().len();
+            println!("loading at interal index: {}", index);
+            self.loaded.borrow_mut().push(font);
+            self.indices.borrow_mut().insert(info.clone(), index);
+
+            Some((index, self.get_at_internal(index)))
+        } else {
+            None
+        }
+    }
+
+    /// Return a loaded font at an internal index. Panics if the index is out of bounds.
+    fn get_at_internal(&self, index: usize) -> Ref<Font> {
+        Ref::map(self.loaded.borrow(), |loaded| &loaded[index])
+    }
+
+    /// Check whether the query and the current family match the info.
+    fn matches(query: FontQuery, family: &FontFamily, info: &FontInfo) -> bool {
+        info.families.contains(family)
+          && info.italic == query.italic && info.bold == query.bold
+    }
+}
+
+/// A query for a font with specific properties.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
+struct FontQuery<'a> {
+    /// A fallback list of font families to accept. The first family in this list, that also
+    /// satisfies the other conditions, shall be returned.
+    families: &'a [FontFamily],
+    /// Whether the font shall be in italics.
+    italic: bool,
+    /// Whether the font shall be in boldface.
+    bold: bool,
+    /// Which character we need.
+    character: char,
 }
 
 /// Default styles for typesetting.
diff --git a/src/export/pdf.rs b/src/export/pdf.rs
index b466f225..4b42f5c2 100644
--- a/src/export/pdf.rs
+++ b/src/export/pdf.rs
@@ -58,7 +58,7 @@ impl<'d, W: Write> PdfEngine<'d, W> {
         let pages = (page_tree + 1, page_tree + doc.pages.len() as Ref);
         let content_count = doc.pages.iter().flat_map(|p| p.text.iter()).count() as Ref;
         let contents = (pages.1 + 1, pages.1 + content_count);
-        let fonts = (contents.1 + 1, contents.1 + 4 * doc.fonts.len() as Ref);
+        let fonts = (contents.1 + 1, contents.1 + 5 * doc.fonts.len() as Ref);
         let offsets = Offsets { catalog, page_tree, pages, contents, fonts };
 
         // Create a subsetted PDF font for each font in the document.
@@ -109,10 +109,14 @@ impl<'d, W: Write> PdfEngine<'d, W> {
         // The document catalog.
         self.writer.write_obj(self.offsets.catalog, &Catalog::new(self.offsets.page_tree))?;
 
+        // The font resources.
+        let fonts = (0 .. self.fonts.len())
+            .map(|i| Resource::Font((i + 1) as u32, self.offsets.fonts.0 + 5 * i as u32));
+
         // The root page tree.
         self.writer.write_obj(self.offsets.page_tree, PageTree::new()
             .kids(ids(self.offsets.pages))
-            .resource(Resource::Font(1, self.offsets.fonts.0))
+            .resources(fonts)
         )?;
 
         // The page objects.
diff --git a/src/font.rs b/src/font.rs
index f596af0f..53d31a41 100644
--- a/src/font.rs
+++ b/src/font.rs
@@ -172,7 +172,7 @@ pub struct FontMetrics {
     pub weight_class: u16,
 }
 
-/// A type that provides fonts matching given criteria.
+/// A type that provides fonts.
 pub trait FontProvider {
     /// Returns the font with the given info if this provider has it.
     fn get(&self, info: &FontInfo) -> Option<Box<dyn FontData>>;
@@ -194,7 +194,7 @@ impl<T> FontData for T where T: Read + Seek {}
 /// Describes a font.
 ///
 /// Can be constructed conventiently with the [`font_info`] macro.
-#[derive(Debug, Clone, Eq, PartialEq)]
+#[derive(Debug, Clone, Eq, PartialEq, Hash)]
 pub struct FontInfo {
     /// The font families this font is part of.
     pub families: Vec<FontFamily>,
@@ -274,50 +274,8 @@ macro_rules! font_info {
     (@__gen Monospace) => {  $crate::font::FontFamily::Monospace };
 }
 
-/// Criteria to filter fonts.
-#[derive(Debug, Clone, Eq, PartialEq)]
-pub struct FontFilter<'a> {
-    /// A fallback list of font families to accept. The first family in this list, that also
-    /// satisfies the other conditions, shall be returned.
-    pub families: &'a [FontFamily],
-    /// If some, matches only italic/non-italic fonts, otherwise any.
-    pub italic: Option<bool>,
-    /// If some, matches only bold/non-bold fonts, otherwise any.
-    pub bold: Option<bool>,
-}
-
-impl<'a> FontFilter<'a> {
-    /// Create a new font config with the given families.
-    ///
-    /// All other fields are set to [`None`] and match anything.
-    pub fn new(families: &'a [FontFamily]) -> FontFilter<'a> {
-        FontFilter {
-            families,
-            italic: None,
-            bold: None,
-        }
-    }
-
-    /// Set the italic value to something.
-    pub fn italic(&mut self, italic: bool) -> &mut Self {
-        self.italic = Some(italic); self
-    }
-
-    /// Set the bold value to something.
-    pub fn bold(&mut self, bold: bool) -> &mut Self {
-        self.bold = Some(bold); self
-    }
-
-    /// Whether this filter matches the given info.
-    pub fn matches(&self, info: &FontInfo) -> bool {
-        self.italic.map(|i| i == info.italic).unwrap_or(true)
-          && self.bold.map(|i| i == info.bold).unwrap_or(true)
-          && self.families.iter().any(|family| info.families.contains(family))
-    }
-}
-
 /// A family of fonts (either generic or named).
-#[derive(Debug, Clone, Eq, PartialEq)]
+#[derive(Debug, Clone, Eq, PartialEq, Hash)]
 pub enum FontFamily {
     SansSerif,
     Serif,
diff --git a/src/lib.rs b/src/lib.rs
index 65955d48..f8c0c59b 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -20,7 +20,7 @@
 //! use typeset::export::pdf::PdfExporter;
 //!
 //! // Simple example source code.
-//! let src = "Hello World from Typeset!";
+//! let src = "Hello World from Typeset! 🌍";
 //!
 //! // Create a compiler with a font provider that provides three fonts
 //! // (the default sans-serif fonts and a fallback for the emoji).
@@ -145,6 +145,7 @@ error_type! {
 #[cfg(test)]
 mod test {
     use std::fs::File;
+    use std::io::BufWriter;
     use crate::Compiler;
     use crate::export::pdf::PdfExporter;
     use crate::font::FileSystemFontProvider;
@@ -167,7 +168,7 @@ mod test {
 
         // Write to file
         let path = format!("../target/typeset-pdf-{}.pdf", name);
-        let file = File::create(path).unwrap();
+        let file = BufWriter::new(File::create(path).unwrap());
         let exporter = PdfExporter::new();
         exporter.export(&document, file).unwrap();
     }
@@ -194,6 +195,11 @@ mod test {
     }
 
     #[test]
+    fn mixed_emoji() {
+        test("mixed-emoji", "Hello World 🌍!")
+    }
+
+    #[test]
     fn long_wikipedia() {
         test("wikipedia", r#"
             Typesetting is the composition of text by means of arranging physical types or the