Basic manual tracking

1 files changed, 97 insertions, 18 deletions

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 }