Add a cache for unchanged layouts

Co-Authored-By: Laurenz <laurmaedje@gmail.com>

6 files changed, 68 insertions, 11 deletions

diff --git a/bench/src/bench.rs b/bench/src/bench.rs
index 5acf15f8..f6ea9398 100644
--- a/bench/src/bench.rs
+++ b/bench/src/bench.rs
@@ -2,6 +2,7 @@ use std::path::Path;
 
 use criterion::{criterion_group, criterion_main, Criterion};
 
+use typst::cache::Cache;
 use typst::env::{Env, FsLoader};
 use typst::eval::eval;
 use typst::exec::{exec, State};
@@ -42,14 +43,14 @@ fn benchmarks(c: &mut Criterion) {
         let syntax_tree = parse(&src).output;
         let expr_map = eval(&mut env, &syntax_tree, &scope).output;
         let layout_tree = exec(&mut env, &syntax_tree, &expr_map, state.clone()).output;
-        let frames = layout(&mut env, &layout_tree);
+        let frames = layout(&mut env, &mut Cache::new(), &layout_tree);
 
         // Bench!
         bench!("parse": parse(&src));
         bench!("eval": eval(&mut env, &syntax_tree, &scope));
         bench!("exec": exec(&mut env, &syntax_tree, &expr_map, state.clone()));
-        bench!("layout": layout(&mut env, &layout_tree));
-        bench!("typeset": typeset(&mut env, &src, &scope, state.clone()));
+        bench!("layout": layout(&mut env, &mut Cache::new(), &layout_tree));
+        bench!("typeset": typeset(&mut env, &mut Cache::new(), &src, &scope, state.clone()));
         bench!("pdf": pdf::export(&env, &frames));
     }
 }
diff --git a/src/cache.rs b/src/cache.rs
new file mode 100644
index 00000000..4cf97ba6
--- /dev/null
+++ b/src/cache.rs
@@ -0,0 +1,34 @@
+//! Caching for incremental compilation.
+
+use std::collections::HashMap;
+
+use crate::layout::{Frame, Regions};
+
+/// A cache for incremental compilation.
+#[derive(Default, Debug, Clone)]
+pub struct Cache {
+    /// A map that holds the layouted nodes from past compilations.
+    pub frames: HashMap<u64, FramesEntry>,
+}
+
+impl Cache {
+    /// Create a new, empty cache.
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    /// Clear the cache.
+    pub fn clear(&mut self) {
+        self.frames.clear();
+    }
+}
+
+/// Frames from past compilations and checks for their validity in future
+/// compilations.
+#[derive(Debug, Clone)]
+pub struct FramesEntry {
+    /// The regions in which these frames are valid.
+    pub regions: Regions,
+    /// Cached frames for a node.
+    pub frames: Vec<Frame>,
+}
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 207d5bed..51b9bc64 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -23,12 +23,13 @@ use std::hash::{Hash, Hasher};
 use decorum::NotNan;
 use fxhash::FxHasher64;
 
+use crate::cache::{Cache, FramesEntry};
 use crate::env::Env;
 use crate::geom::*;
 
 /// Layout a tree into a collection of frames.
-pub fn layout(env: &mut Env, tree: &Tree) -> Vec<Frame> {
-    tree.layout(&mut LayoutContext { env })
+pub fn layout(env: &mut Env, cache: &mut Cache, tree: &Tree) -> Vec<Frame> {
+    tree.layout(&mut LayoutContext { env, cache })
 }
 
 /// A tree of layout nodes.
@@ -96,7 +97,19 @@ impl AnyNode {
 
 impl Layout for AnyNode {
     fn layout(&self, ctx: &mut LayoutContext, regions: &Regions) -> Vec<Frame> {
-        self.node.layout(ctx, regions)
+        if let Some(hit) = ctx.cache.frames.get(&self.hash()) {
+            if &hit.regions == regions {
+                return hit.frames.clone();
+            }
+        }
+
+        let frames = self.node.layout(ctx, regions);
+        ctx.cache.frames.insert(self.hash(), FramesEntry {
+            regions: regions.clone(),
+            frames: frames.clone(),
+        });
+
+        frames
     }
 }
 
@@ -164,6 +177,9 @@ pub trait Layout {
 pub struct LayoutContext<'a> {
     /// The environment from which fonts are gathered.
     pub env: &'a mut Env,
+    /// A cache which enables reuse of layout artifacts from past compilation
+    /// cycles.
+    pub cache: &'a mut Cache,
 }
 
 /// A sequence of regions to layout into.
diff --git a/src/lib.rs b/src/lib.rs
index 2802c386..8742aeb8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -32,6 +32,7 @@
 pub mod diag;
 #[macro_use]
 pub mod eval;
+pub mod cache;
 pub mod color;
 pub mod env;
 pub mod exec;
@@ -46,6 +47,7 @@ pub mod pretty;
 pub mod syntax;
 pub mod util;
 
+use crate::cache::Cache;
 use crate::diag::Pass;
 use crate::env::Env;
 use crate::eval::Scope;
@@ -55,6 +57,7 @@ use crate::layout::Frame;
 /// Process source code directly into a collection of frames.
 pub fn typeset(
     env: &mut Env,
+    cache: &mut Cache,
     src: &str,
     scope: &Scope,
     state: State,
@@ -62,7 +65,7 @@ pub fn typeset(
     let parsed = parse::parse(src);
     let evaluated = eval::eval(env, &parsed.output, scope);
     let executed = exec::exec(env, &parsed.output, &evaluated.output, state);
-    let frames = layout::layout(env, &executed.output);
+    let frames = layout::layout(env, cache, &executed.output);
 
     let mut diags = parsed.diags;
     diags.extend(evaluated.diags);
diff --git a/src/main.rs b/src/main.rs
index 9a112d5a..aef0f573 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -3,6 +3,7 @@ use std::path::{Path, PathBuf};
 
 use anyhow::{anyhow, bail, Context};
 
+use typst::cache::Cache;
 use typst::diag::Pass;
 use typst::env::{Env, FsLoader};
 use typst::exec::State;
@@ -39,11 +40,12 @@ fn main() -> anyhow::Result<()> {
     loader.search_system();
 
     let mut env = Env::new(loader);
-
+    let mut cache = Cache::new();
     let scope = library::new();
     let state = State::default();
 
-    let Pass { output: frames, diags } = typeset(&mut env, &src, &scope, state);
+    let Pass { output: frames, diags } =
+        typeset(&mut env, &mut cache, &src, &scope, state);
     if !diags.is_empty() {
         let map = LineMap::new(&src);
         for diag in diags {
diff --git a/tests/typeset.rs b/tests/typeset.rs
index 0d862c81..57693cfd 100644
--- a/tests/typeset.rs
+++ b/tests/typeset.rs
@@ -13,6 +13,7 @@ use tiny_skia::{
 use ttf_parser::{GlyphId, OutlineBuilder};
 use walkdir::WalkDir;
 
+use typst::cache::Cache;
 use typst::color;
 use typst::diag::{Diag, DiagSet, Level, Pass};
 use typst::env::{Env, FsLoader, ImageId};
@@ -212,7 +213,6 @@ fn test_part(
     let compare_ref = local_compare_ref.unwrap_or(compare_ref);
 
     let mut scope = library::new();
-
     let panics = Rc::new(RefCell::new(vec![]));
     register_helpers(&mut scope, Rc::clone(&panics));
 
@@ -222,7 +222,8 @@ fn test_part(
     state.page.size = Size::new(Length::pt(120.0), Length::raw(f64::INFINITY));
     state.page.margins = Sides::splat(Some(Length::pt(10.0).into()));
 
-    let Pass { output: mut frames, diags } = typeset(env, &src, &scope, state);
+    let Pass { output: mut frames, diags } =
+        typeset(env, &mut Cache::new(), &src, &scope, state);
     if !compare_ref {
         frames.clear();
     }