Basic manual tracking

7 files changed, 236 insertions, 62 deletions

diff --git a/src/export/render.rs b/src/export/render.rs
index 163707eb..9f088433 100644
--- a/src/export/render.rs
+++ b/src/export/render.rs
@@ -246,7 +246,12 @@ fn render_outline_glyph(
     // doesn't exist, yet.
     let bitmap = crate::memo::memoized_ref(
         (&ctx.fonts, text.face_id, id),
-        |(fonts, face_id, id)| pixglyph::Glyph::load(fonts.get(face_id).ttf(), id),
+        |(fonts, face_id, id)| {
+            (
+                pixglyph::Glyph::load(fonts.get(face_id).ttf(), id),
+                ((), (), ()),
+            )
+        },
         |glyph| glyph.as_ref().map(|g| g.rasterize(ts.tx, ts.ty, ppem)),
     )?;
 
diff --git a/src/font.rs b/src/font.rs
index 108ade10..0791bb6f 100644
--- a/src/font.rs
+++ b/src/font.rs
@@ -236,6 +236,11 @@ fn shared_prefix_words(left: &str, right: &str) -> usize {
         .count()
 }
 
+impl_track_empty!(FontStore);
+impl_track_empty!(&'_ mut FontStore);
+impl_track_hash!(FaceId);
+impl_track_hash!(GlyphId);
+
 /// A font face.
 pub struct Face {
     /// The raw face data, possibly shared with other faces from the same
diff --git a/src/lib.rs b/src/lib.rs
index 34e87c5e..bcbf8478 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -34,6 +34,8 @@
 #[macro_use]
 pub mod util;
 #[macro_use]
+pub mod memo;
+#[macro_use]
 pub mod geom;
 #[macro_use]
 pub mod diag;
@@ -45,13 +47,13 @@ pub mod frame;
 pub mod image;
 pub mod library;
 pub mod loading;
-pub mod memo;
 pub mod model;
 pub mod parse;
 pub mod source;
 pub mod syntax;
 
 use std::collections::HashMap;
+use std::hash::Hasher;
 use std::path::PathBuf;
 use std::sync::Arc;
 
@@ -61,7 +63,8 @@ use crate::font::FontStore;
 use crate::frame::Frame;
 use crate::image::ImageStore;
 use crate::loading::Loader;
-use crate::model::{PinBoard, StyleMap};
+use crate::memo::Track;
+use crate::model::{PinBoard, PinConstraint, StyleMap};
 use crate::source::{SourceId, SourceStore};
 
 /// Typeset a source file into a collection of layouted frames.
@@ -104,6 +107,18 @@ impl Context {
     }
 }
 
+impl Track for &mut Context {
+    type Constraint = PinConstraint;
+
+    fn key<H: Hasher>(&self, hasher: &mut H) {
+        self.pins.key(hasher);
+    }
+
+    fn matches(&self, constraint: &Self::Constraint) -> bool {
+        self.pins.matches(constraint)
+    }
+}
+
 /// Compilation configuration.
 pub struct Config {
     /// The compilation root.
diff --git a/src/memo.rs b/src/memo.rs
index 2eee071c..4d192f39 100644
--- a/src/memo.rs
+++ b/src/memo.rs
@@ -4,7 +4,7 @@ use std::any::Any;
 use std::cell::RefCell;
 use std::collections::HashMap;
 use std::fmt::{self, Display, Formatter};
-use std::hash::{Hash, Hasher};
+use std::hash::Hasher;
 
 thread_local! {
     /// The thread-local cache.
@@ -24,7 +24,7 @@ where
 
 /// An entry in the cache.
 struct CacheEntry {
-    /// The memoized function's result.
+    /// The memoized function's result plus constraints on the input.
     data: Box<dyn Any>,
     /// How many evictions have passed since the entry has been last used.
     age: usize,
@@ -37,9 +37,9 @@ struct CacheEntry {
 /// copy of the results in the cache.
 ///
 /// Note that `f` must be a pure function.
-pub fn memoized<I, O>(input: I, f: fn(input: I) -> O) -> O
+pub fn memoized<I, O>(input: I, f: fn(input: I) -> (O, I::Constraint)) -> O
 where
-    I: Hash,
+    I: Track,
     O: Clone + 'static,
 {
     memoized_ref(input, f, Clone::clone)
@@ -54,24 +54,38 @@ where
 ///   the cache.
 ///
 /// Note that `f` must be a pure function, while `g` does not need to be pure.
-pub fn memoized_ref<I, O, G, R>(input: I, f: fn(input: I) -> O, g: G) -> R
+pub fn memoized_ref<I, O, G, R>(
+    input: I,
+    f: fn(input: I) -> (O, I::Constraint),
+    g: G,
+) -> R
 where
-    I: Hash,
+    I: Track,
     O: 'static,
     G: Fn(&O) -> R,
 {
-    let hash = fxhash::hash64(&(f, &input));
+    let mut state = fxhash::FxHasher64::default();
+    input.key(&mut state);
+
+    let key = state.finish();
     let result = with(|cache| {
-        let entry = cache.get_mut(&hash)?;
+        let entry = cache.get_mut(&key)?;
         entry.age = 0;
-        entry.data.downcast_ref().map(|output| g(output))
+        entry
+            .data
+            .downcast_ref::<(O, I::Constraint)>()
+            .filter(|(_, constraint)| input.matches(constraint))
+            .map(|(output, _)| g(output))
     });
 
     result.unwrap_or_else(|| {
         let output = f(input);
-        let result = g(&output);
-        let entry = CacheEntry { data: Box::new(output), age: 0 };
-        with(|cache| cache.insert(hash, entry));
+        let result = g(&output.0);
+        let entry = CacheEntry {
+            data: Box::new(output) as Box<(O, I::Constraint)> as Box<dyn Any>,
+            age: 0,
+        };
+        with(|cache| cache.insert(key, entry));
         result
     })
 }
@@ -110,14 +124,79 @@ impl Display for Eviction {
     }
 }
 
-// These impls are temporary and incorrect.
+/// Tracks input dependencies of a memoized function.
+pub trait Track {
+    /// The type of constraint generated by this input.
+    type Constraint: 'static;
+
+    /// Feed the key portion of the input into a hasher.
+    fn key<H: Hasher>(&self, hasher: &mut H);
 
-impl Hash for crate::font::FontStore {
-    fn hash<H: Hasher>(&self, _: &mut H) {}
+    /// Whether this instance matches the given constraint.
+    fn matches(&self, constraint: &Self::Constraint) -> bool;
 }
 
-impl Hash for crate::Context {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        self.pins.hash(state);
+impl<T: Track> Track for &T {
+    type Constraint = T::Constraint;
+
+    fn key<H: Hasher>(&self, hasher: &mut H) {
+        Track::key(*self, hasher)
+    }
+
+    fn matches(&self, constraint: &Self::Constraint) -> bool {
+        Track::matches(*self, constraint)
     }
 }
+
+macro_rules! impl_track_empty {
+    ($ty:ty) => {
+        impl $crate::memo::Track for $ty {
+            type Constraint = ();
+
+            fn key<H: std::hash::Hasher>(&self, _: &mut H) {}
+
+            fn matches(&self, _: &Self::Constraint) -> bool {
+                true
+            }
+        }
+    };
+}
+
+macro_rules! impl_track_hash {
+    ($ty:ty) => {
+        impl $crate::memo::Track for $ty {
+            type Constraint = ();
+
+            fn key<H: std::hash::Hasher>(&self, hasher: &mut H) {
+                std::hash::Hash::hash(self, hasher)
+            }
+
+            fn matches(&self, _: &Self::Constraint) -> bool {
+                true
+            }
+        }
+    };
+}
+
+macro_rules! impl_track_tuple {
+    ($($idx:tt: $field:ident),*) => {
+        #[allow(unused_variables)]
+        impl<$($field: Track),*> Track for ($($field,)*) {
+            type Constraint = ($($field::Constraint,)*);
+
+            fn key<H: Hasher>(&self, hasher: &mut H) {
+                $(self.$idx.key(hasher);)*
+            }
+
+            fn matches(&self, constraint: &Self::Constraint) -> bool {
+                true $(&& self.$idx.matches(&constraint.$idx))*
+            }
+        }
+    };
+}
+
+impl_track_tuple! {}
+impl_track_tuple! { 0: A }
+impl_track_tuple! { 0: A, 1: B }
+impl_track_tuple! { 0: A, 1: B, 2: C }
+impl_track_tuple! { 0: A, 1: B, 2: C, 3: D }
diff --git a/src/model/layout.rs b/src/model/layout.rs
index 92d73977..b0247258 100644
--- a/src/model/layout.rs
+++ b/src/model/layout.rs
@@ -5,7 +5,7 @@ use std::fmt::{self, Debug, Formatter, Write};
 use std::hash::Hash;
 use std::sync::Arc;
 
-use super::{Barrier, NodeId, Resolve, StyleChain, StyleEntry};
+use super::{Barrier, NodeId, PinConstraint, Resolve, StyleChain, StyleEntry};
 use crate::diag::TypResult;
 use crate::eval::{RawAlign, RawLength};
 use crate::frame::{Element, Frame};
@@ -132,6 +132,8 @@ impl Regions {
     }
 }
 
+impl_track_hash!(Regions);
+
 /// A type-erased layouting node with a precomputed hash.
 #[derive(Clone, Hash)]
 pub struct LayoutNode(Arc<Prehashed<dyn Bounds>>);
@@ -221,19 +223,32 @@ impl Layout for LayoutNode {
         regions: &Regions,
         styles: StyleChain,
     ) -> TypResult<Vec<Arc<Frame>>> {
-        let (result, at, pins) = crate::memo::memoized(
+        let prev = ctx.pins.dirty.replace(false);
+
+        let (result, at, fresh, dirty) = crate::memo::memoized(
             (self, &mut *ctx, regions, styles),
             |(node, ctx, regions, styles)| {
+                let hash = fxhash::hash64(&ctx.pins);
                 let at = ctx.pins.cursor();
+
                 let entry = StyleEntry::Barrier(Barrier::new(node.id()));
                 let result = node.0.layout(ctx, regions, entry.chain(&styles));
-                (result, at, ctx.pins.from(at))
+
+                let fresh = ctx.pins.from(at);
+                let dirty = ctx.pins.dirty.get();
+                let constraint = PinConstraint(dirty.then(|| hash));
+                ((result, at, fresh, dirty), ((), constraint, (), ()))
             },
         );
 
+        ctx.pins.dirty.replace(prev || dirty);
+
         // Replay the side effect in case of caching. This should currently be
         // more or less the only relevant side effect on the context.
-        ctx.pins.replay(at, pins);
+        if dirty {
+            ctx.pins.replay(at, fresh);
+        }
+
         result
     }
 
@@ -242,6 +257,8 @@ impl Layout for LayoutNode {
     }
 }
 
+impl_track_hash!(LayoutNode);
+
 impl Default for LayoutNode {
     fn default() -> Self {
         EmptyNode.pack()
diff --git a/src/model/locate.rs b/src/model/locate.rs
index 97c14034..495203aa 100644
--- a/src/model/locate.rs
+++ b/src/model/locate.rs
@@ -1,4 +1,6 @@
+use std::cell::Cell;
 use std::fmt::{self, Debug, Formatter};
+use std::hash::{Hash, Hasher};
 use std::sync::Arc;
 
 use super::Content;
@@ -6,6 +8,7 @@ use crate::diag::TypResult;
 use crate::eval::{Args, Array, Dict, Func, Value};
 use crate::frame::{Element, Frame, Location};
 use crate::geom::{Point, Transform};
+use crate::memo::Track;
 use crate::syntax::Spanned;
 use crate::util::EcoString;
 use crate::Context;
@@ -84,7 +87,7 @@ struct SingleNode(Spanned<Func>);
 
 impl SingleNode {
     fn realize(&self, ctx: &mut Context) -> TypResult<Content> {
-        let idx = ctx.pins.cursor();
+        let idx = ctx.pins.cursor;
         let pin = ctx.pins.get_or_create(None, None);
         let dict = pin.encode(None);
         let args = Args::new(self.0.span, [Value::Dict(dict)]);
@@ -105,7 +108,7 @@ struct EntryNode {
 
 impl EntryNode {
     fn realize(&self, ctx: &mut Context) -> TypResult<Content> {
-        let idx = ctx.pins.cursor();
+        let idx = ctx.pins.cursor;
         let pin = ctx.pins.get_or_create(Some(self.group.clone()), self.value.clone());
 
         // Determine the index among the peers.
@@ -155,7 +158,7 @@ impl AllNode {
 }
 
 /// Manages document pins.
-#[derive(Debug, Clone, Hash)]
+#[derive(Debug, Clone)]
 pub struct PinBoard {
     /// All currently active pins.
     list: Vec<Pin>,
@@ -164,14 +167,63 @@ pub struct PinBoard {
     /// If larger than zero, the board is frozen and the cursor will not be
     /// advanced. This is used to disable pinning during measure-only layouting.
     frozen: usize,
+    /// Whether the board was accessed.
+    pub(super) dirty: Cell<bool>,
 }
 
 impl PinBoard {
     /// Create an empty pin board.
     pub fn new() -> Self {
-        Self { list: vec![], cursor: 0, frozen: 0 }
+        Self {
+            list: vec![],
+            cursor: 0,
+            frozen: 0,
+            dirty: Cell::new(false),
+        }
+    }
+}
+
+/// Internal methods for implementation of locatable nodes.
+impl PinBoard {
+    /// Access or create the next pin.
+    fn get_or_create(&mut self, group: Option<Group>, value: Option<Value>) -> Pin {
+        self.dirty.set(true);
+        if self.frozen() {
+            return Pin::default();
+        }
+
+        let cursor = self.cursor;
+        self.cursor += 1;
+        if self.cursor >= self.list.len() {
+            self.list.resize(self.cursor, Pin::default());
+        }
+
+        let pin = &mut self.list[cursor];
+        pin.group = group;
+        pin.value = value;
+        pin.clone()
     }
 
+    /// Encode a group into a user-facing array.
+    fn encode_group(&self, group: &Group) -> Array {
+        self.dirty.set(true);
+        let mut all: Vec<_> = self.iter().filter(|pin| pin.is_in(group)).collect();
+        all.sort_by_key(|pin| pin.flow);
+        all.iter()
+            .enumerate()
+            .map(|(index, member)| Value::Dict(member.encode(Some(index))))
+            .collect()
+    }
+
+    /// Iterate over all pins on the board.
+    fn iter(&self) -> std::slice::Iter<Pin> {
+        self.dirty.set(true);
+        self.list.iter()
+    }
+}
+
+/// Caching related methods.
+impl PinBoard {
     /// The current cursor.
     pub fn cursor(&self) -> usize {
         self.cursor
@@ -190,7 +242,10 @@ impl PinBoard {
             self.list.splice(at .. end, pins);
         }
     }
+}
 
+/// Control methods that are called during layout.
+impl PinBoard {
     /// Freeze the board to prevent modifications.
     pub fn freeze(&mut self) {
         self.frozen += 1;
@@ -205,11 +260,15 @@ impl PinBoard {
     pub fn frozen(&self) -> bool {
         self.frozen > 0
     }
+}
 
+/// Methods that are called in between layout passes.
+impl PinBoard {
     /// Reset the cursor and remove all unused pins.
     pub fn reset(&mut self) {
         self.list.truncate(self.cursor);
         self.cursor = 0;
+        self.dirty.set(false);
     }
 
     /// Locate all pins in the frames.
@@ -230,39 +289,6 @@ impl PinBoard {
     pub fn unresolved(&self, prev: &Self) -> usize {
         self.list.len() - self.list.iter().zip(&prev.list).filter(|(a, b)| a == b).count()
     }
-
-    /// Access or create the next pin.
-    fn get_or_create(&mut self, group: Option<Group>, value: Option<Value>) -> Pin {
-        if self.frozen() {
-            return Pin::default();
-        }
-
-        let cursor = self.cursor;
-        self.cursor += 1;
-        if self.cursor >= self.list.len() {
-            self.list.resize(self.cursor, Pin::default());
-        }
-
-        let pin = &mut self.list[cursor];
-        pin.group = group;
-        pin.value = value;
-        pin.clone()
-    }
-
-    /// Iterate over all pins on the board.
-    fn iter(&self) -> std::slice::Iter<Pin> {
-        self.list.iter()
-    }
-
-    /// Encode a group into a user-facing array.
-    fn encode_group(&self, group: &Group) -> Array {
-        let mut all: Vec<_> = self.iter().filter(|pin| pin.is_in(group)).collect();
-        all.sort_by_key(|pin| pin.flow);
-        all.iter()
-            .enumerate()
-            .map(|(index, member)| Value::Dict(member.encode(Some(index))))
-            .collect()
-    }
 }
 
 /// Locate all pins in a frame.
@@ -295,6 +321,31 @@ fn locate_in_frame(
     }
 }
 
+impl Hash for PinBoard {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.list.hash(state);
+        self.cursor.hash(state);
+        self.frozen.hash(state);
+    }
+}
+
+/// Describes pin usage.
+#[derive(Debug, Copy, Clone)]
+pub struct PinConstraint(pub Option<u64>);
+
+impl Track for PinBoard {
+    type Constraint = PinConstraint;
+
+    fn key<H: Hasher>(&self, _: &mut H) {}
+
+    fn matches(&self, constraint: &Self::Constraint) -> bool {
+        match constraint.0 {
+            Some(hash) => fxhash::hash64(self) == hash,
+            None => true,
+        }
+    }
+}
+
 /// A document pin.
 #[derive(Debug, Clone, PartialEq, Hash)]
 pub struct Pin {
diff --git a/src/model/styles.rs b/src/model/styles.rs
index 82194792..9e723171 100644
--- a/src/model/styles.rs
+++ b/src/model/styles.rs
@@ -394,6 +394,8 @@ impl PartialEq for StyleChain<'_> {
     }
 }
 
+impl_track_hash!(StyleChain<'_>);
+
 /// An iterator over the values in a style chain.
 struct Values<'a, K> {
     entries: Entries<'a>,