Query cache

4 files changed, 95 insertions, 13 deletions

diff --git a/src/eval/layout.rs b/src/eval/layout.rs
index 1090aafc..38ad3977 100644
--- a/src/eval/layout.rs
+++ b/src/eval/layout.rs
@@ -221,8 +221,10 @@ impl Layout for LayoutNode {
         regions: &Regions,
         styles: StyleChain,
     ) -> TypResult<Vec<Arc<Frame>>> {
-        // TODO(query)
-        self.0.layout(ctx, regions, styles.barred(self.id()))
+        ctx.query((self, regions, styles), |ctx, (node, regions, styles)| {
+            node.0.layout(ctx, regions, styles.barred(node.id()))
+        })
+        .clone()
     }
 
     fn pack(self) -> LayoutNode {
diff --git a/src/eval/show.rs b/src/eval/show.rs
index b0fb8172..a85c70e2 100644
--- a/src/eval/show.rs
+++ b/src/eval/show.rs
@@ -43,7 +43,10 @@ impl ShowNode {
 
 impl Show for ShowNode {
     fn show(&self, ctx: &mut Context, styles: StyleChain) -> TypResult<Template> {
-        self.0.show(ctx, styles)
+        ctx.query((self, styles), |ctx, (node, styles)| {
+            node.0.show(ctx, styles)
+        })
+        .clone()
     }
 
     fn pack(self) -> ShowNode {
diff --git a/src/export/render.rs b/src/export/render.rs
index 1a08b60b..ff35390e 100644
--- a/src/export/render.rs
+++ b/src/export/render.rs
@@ -7,7 +7,6 @@ use tiny_skia as sk;
 use ttf_parser::{GlyphId, OutlineBuilder};
 use usvg::FitTo;
 
-use crate::font::Face;
 use crate::frame::{Element, Frame, Geometry, Group, Shape, Stroke, Text};
 use crate::geom::{self, Length, Paint, PathElement, Size, Transform};
 use crate::image::{Image, RasterImage, Svg};
@@ -115,17 +114,15 @@ fn render_text(
     ctx: &mut Context,
     text: &Text,
 ) {
-    let face = ctx.fonts.get(text.face_id);
-
     let mut x = 0.0;
     for glyph in &text.glyphs {
         let id = GlyphId(glyph.id);
         let offset = x + glyph.x_offset.resolve(text.size).to_f32();
         let ts = ts.pre_translate(offset, 0.0);
 
-        render_svg_glyph(canvas, ts, mask, text, face, id)
-            .or_else(|| render_bitmap_glyph(canvas, ts, mask, text, face, id))
-            .or_else(|| render_outline_glyph(canvas, ts, mask, text, face, id));
+        render_svg_glyph(canvas, ts, mask, ctx, text, id)
+            .or_else(|| render_bitmap_glyph(canvas, ts, mask, ctx, text, id))
+            .or_else(|| render_outline_glyph(canvas, ts, mask, ctx, text, id));
 
         x += glyph.x_advance.resolve(text.size).to_f32();
     }
@@ -136,10 +133,11 @@ fn render_svg_glyph(
     canvas: &mut sk::Pixmap,
     ts: sk::Transform,
     _: Option<&sk::ClipMask>,
+    ctx: &mut Context,
     text: &Text,
-    face: &Face,
     id: GlyphId,
 ) -> Option<()> {
+    let face = ctx.fonts.get(text.face_id);
     let mut data = face.ttf().glyph_svg_image(id)?;
 
     // Decompress SVGZ.
@@ -186,12 +184,13 @@ fn render_bitmap_glyph(
     canvas: &mut sk::Pixmap,
     ts: sk::Transform,
     mask: Option<&sk::ClipMask>,
+    ctx: &mut Context,
     text: &Text,
-    face: &Face,
     id: GlyphId,
 ) -> Option<()> {
     let size = text.size.to_f32();
     let ppem = size * ts.sy;
+    let face = ctx.fonts.get(text.face_id);
     let raster = face.ttf().glyph_raster_image(id, ppem as u16)?;
     let img = RasterImage::parse(&raster.data).ok()?;
 
@@ -211,8 +210,8 @@ fn render_outline_glyph(
     canvas: &mut sk::Pixmap,
     ts: sk::Transform,
     mask: Option<&sk::ClipMask>,
+    ctx: &mut Context,
     text: &Text,
-    face: &Face,
     id: GlyphId,
 ) -> Option<()> {
     let ppem = text.size.to_f32() * ts.sy;
@@ -221,6 +220,7 @@ fn render_outline_glyph(
     // rasterization can't be used due to very large text size or weird
     // scale/skewing transforms.
     if ppem > 100.0 || ts.kx != 0.0 || ts.ky != 0.0 || ts.sx != ts.sy {
+        let face = ctx.fonts.get(text.face_id);
         let path = {
             let mut builder = WrappedPathBuilder(sk::PathBuilder::new());
             face.ttf().outline_glyph(id, &mut builder)?;
@@ -241,7 +241,11 @@ fn render_outline_glyph(
     // TODO(query)
     // Try to retrieve a prepared glyph or prepare it from scratch if it
     // doesn't exist, yet.
-    let glyph = pixglyph::Glyph::load(face.ttf(), id)?;
+    let glyph = ctx
+        .query((text.face_id, id), |ctx, (face_id, id)| {
+            pixglyph::Glyph::load(ctx.fonts.get(face_id).ttf(), id)
+        })
+        .as_ref()?;
 
     // Rasterize the glyph with `pixglyph`.
     let bitmap = glyph.rasterize(ts.tx, ts.ty, ppem);
diff --git a/src/lib.rs b/src/lib.rs
index 458c8cec..8ef538c5 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -48,7 +48,10 @@ pub mod parse;
 pub mod source;
 pub mod syntax;
 
+use std::any::Any;
 use std::collections::HashMap;
+use std::fmt::{self, Display, Formatter};
+use std::hash::Hash;
 use std::path::PathBuf;
 use std::sync::Arc;
 
@@ -76,6 +79,8 @@ pub struct Context {
     styles: Arc<StyleMap>,
     /// Cached modules.
     modules: HashMap<SourceId, Module>,
+    /// Cached queries.
+    cache: HashMap<u64, CacheEntry>,
     /// The stack of imported files that led to evaluation of the current file.
     route: Vec<SourceId>,
     /// The dependencies of the current evaluation process.
@@ -206,6 +211,7 @@ impl ContextBuilder {
             std: self.std.unwrap_or_else(|| Arc::new(library::new())),
             styles: self.styles.unwrap_or_default(),
             modules: HashMap::new(),
+            cache: HashMap::new(),
             route: vec![],
             deps: vec![],
         }
@@ -217,3 +223,70 @@ impl Default for ContextBuilder {
         Self { std: None, styles: None }
     }
 }
+
+/// An entry in the query cache.
+struct CacheEntry {
+    /// The query's results.
+    data: Box<dyn Any>,
+    /// How many evictions have passed since the entry has been last used.
+    age: usize,
+}
+
+impl Context {
+    /// Execute a query.
+    ///
+    /// This hashes all inputs to the query and then either returns a cached
+    /// version or executes the query, saves the results in the cache and
+    /// returns a reference to them.
+    pub fn query<I, O>(
+        &mut self,
+        input: I,
+        query: fn(ctx: &mut Self, input: I) -> O,
+    ) -> &O
+    where
+        I: Hash,
+        O: 'static,
+    {
+        let hash = fxhash::hash64(&input);
+        if !self.cache.contains_key(&hash) {
+            let output = query(self, input);
+            self.cache.insert(hash, CacheEntry { data: Box::new(output), age: 0 });
+        }
+
+        let entry = self.cache.get_mut(&hash).unwrap();
+        entry.age = 0;
+        entry.data.downcast_ref().expect("oh no, a hash collision")
+    }
+
+    /// Garbage-collect the query cache. This deletes elements which haven't
+    /// been used in a while.
+    ///
+    /// Returns details about the eviction.
+    pub fn evict(&mut self) -> Eviction {
+        const MAX_AGE: usize = 5;
+
+        let before = self.cache.len();
+        self.cache.retain(|_, entry| {
+            entry.age += 1;
+            entry.age <= MAX_AGE
+        });
+
+        Eviction { before, after: self.cache.len() }
+    }
+}
+
+/// Details about a cache eviction.
+pub struct Eviction {
+    /// The number of items in the cache before the eviction.
+    pub before: usize,
+    /// The number of items in the cache after the eviction.
+    pub after: usize,
+}
+
+impl Display for Eviction {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        writeln!(f, "Before: {}", self.before)?;
+        writeln!(f, "Evicted: {}", self.before - self.after)?;
+        writeln!(f, "After: {}", self.after)
+    }
+}