Make values hashable

6 files changed, 82 insertions, 11 deletions

diff --git a/src/eval/array.rs b/src/eval/array.rs
index 4ed172ab..7ff5fb74 100644
--- a/src/eval/array.rs
+++ b/src/eval/array.rs
@@ -20,7 +20,7 @@ macro_rules! array {
 }
 
 /// An array of values with clone-on-write value semantics.
-#[derive(Default, Clone, PartialEq)]
+#[derive(Default, Clone, PartialEq, Hash)]
 pub struct Array(Arc<Vec<Value>>);
 
 impl Array {
diff --git a/src/eval/class.rs b/src/eval/class.rs
index acdf38e6..c4880e9a 100644
--- a/src/eval/class.rs
+++ b/src/eval/class.rs
@@ -1,4 +1,5 @@
 use std::fmt::{self, Debug, Formatter, Write};
+use std::hash::{Hash, Hasher};
 
 use super::{Args, EvalContext, Func, StyleMap, Template, Value};
 use crate::diag::TypResult;
@@ -103,6 +104,13 @@ impl PartialEq for Class {
     }
 }
 
+impl Hash for Class {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        (self.construct as usize).hash(state);
+        (self.set as usize).hash(state);
+    }
+}
+
 /// Construct an instance of a class.
 pub trait Construct {
     /// Construct an instance of this class from the arguments.
diff --git a/src/eval/dict.rs b/src/eval/dict.rs
index 0aa9fd4b..03871fa0 100644
--- a/src/eval/dict.rs
+++ b/src/eval/dict.rs
@@ -19,7 +19,7 @@ macro_rules! dict {
 }
 
 /// A dictionary from strings to values with clone-on-write value semantics.
-#[derive(Default, Clone, PartialEq)]
+#[derive(Default, Clone, PartialEq, Hash)]
 pub struct Dict(Arc<BTreeMap<EcoString, Value>>);
 
 impl Dict {
diff --git a/src/eval/func.rs b/src/eval/func.rs
index 887f7989..b7b9c9cd 100644
--- a/src/eval/func.rs
+++ b/src/eval/func.rs
@@ -1,4 +1,5 @@
 use std::fmt::{self, Debug, Formatter, Write};
+use std::hash::{Hash, Hasher};
 use std::sync::Arc;
 
 use super::{Cast, Eval, EvalContext, Scope, Value};
@@ -8,10 +9,11 @@ use crate::syntax::{Span, Spanned};
 use crate::util::EcoString;
 
 /// An evaluatable function.
-#[derive(Clone)]
+#[derive(Clone, Hash)]
 pub struct Func(Arc<Repr>);
 
 /// The different kinds of function representations.
+#[derive(Hash)]
 enum Repr {
     /// A native rust function.
     Native(Native),
@@ -89,7 +91,14 @@ struct Native {
     pub func: fn(&mut EvalContext, &mut Args) -> TypResult<Value>,
 }
 
+impl Hash for Native {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        (self.func as usize).hash(state);
+    }
+}
+
 /// A user-defined closure.
+#[derive(Hash)]
 pub struct Closure {
     /// The name of the closure.
     pub name: Option<EcoString>,
@@ -138,7 +147,7 @@ impl Closure {
 }
 
 /// Evaluated arguments to a function.
-#[derive(Clone, PartialEq)]
+#[derive(Clone, PartialEq, Hash)]
 pub struct Args {
     /// The span of the whole argument list.
     pub span: Span,
@@ -147,7 +156,7 @@ pub struct Args {
 }
 
 /// An argument to a function call: `12` or `draw: false`.
-#[derive(Clone, PartialEq)]
+#[derive(Clone, PartialEq, Hash)]
 pub struct Arg {
     /// The span of the whole argument.
     pub span: Span,
diff --git a/src/eval/scope.rs b/src/eval/scope.rs
index 3e79afc1..1539b4af 100644
--- a/src/eval/scope.rs
+++ b/src/eval/scope.rs
@@ -1,6 +1,7 @@
 use std::cell::RefCell;
-use std::collections::HashMap;
+use std::collections::BTreeMap;
 use std::fmt::{self, Debug, Formatter};
+use std::hash::{Hash, Hasher};
 use std::iter;
 use std::sync::Arc;
 
@@ -68,7 +69,7 @@ impl<'a> Scopes<'a> {
 #[derive(Default, Clone)]
 pub struct Scope {
     /// The mapping from names to slots.
-    values: HashMap<EcoString, Slot>,
+    values: BTreeMap<EcoString, Slot>,
 }
 
 impl Scope {
@@ -126,6 +127,16 @@ impl Scope {
     }
 }
 
+impl Hash for Scope {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.values.len().hash(state);
+        for (name, value) in self.values.iter() {
+            name.hash(state);
+            value.borrow().hash(state);
+        }
+    }
+}
+
 impl Debug for Scope {
     fn fmt(&self, f: &mut Formatter) -> fmt::Result {
         f.write_str("Scope ")?;
diff --git a/src/eval/value.rs b/src/eval/value.rs
index 44e62c50..02ed6558 100644
--- a/src/eval/value.rs
+++ b/src/eval/value.rs
@@ -1,7 +1,7 @@
 use std::any::Any;
 use std::cmp::Ordering;
 use std::fmt::{self, Debug, Formatter};
-use std::hash::Hash;
+use std::hash::{Hash, Hasher};
 use std::sync::Arc;
 
 use super::{ops, Args, Array, Class, Dict, Func, Template};
@@ -173,6 +173,33 @@ impl PartialOrd for Value {
     }
 }
 
+impl Hash for Value {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        std::mem::discriminant(self).hash(state);
+        match self {
+            Self::None => {}
+            Self::Auto => {}
+            Self::Bool(v) => v.hash(state),
+            Self::Int(v) => v.hash(state),
+            Self::Float(v) => v.to_bits().hash(state),
+            Self::Length(v) => v.hash(state),
+            Self::Angle(v) => v.hash(state),
+            Self::Relative(v) => v.hash(state),
+            Self::Linear(v) => v.hash(state),
+            Self::Fractional(v) => v.hash(state),
+            Self::Color(v) => v.hash(state),
+            Self::Str(v) => v.hash(state),
+            Self::Array(v) => v.hash(state),
+            Self::Dict(v) => v.hash(state),
+            Self::Template(v) => v.hash(state),
+            Self::Func(v) => v.hash(state),
+            Self::Args(v) => v.hash(state),
+            Self::Class(v) => v.hash(state),
+            Self::Dyn(v) => v.hash(state),
+        }
+    }
+}
+
 impl From<i32> for Value {
     fn from(v: i32) -> Self {
         Self::Int(v as i64)
@@ -210,14 +237,14 @@ impl From<Dynamic> for Value {
 }
 
 /// A dynamic value.
-#[derive(Clone)]
+#[derive(Clone, Hash)]
 pub struct Dynamic(Arc<dyn Bounds>);
 
 impl Dynamic {
     /// Create a new instance from any value that satisifies the required bounds.
     pub fn new<T>(any: T) -> Self
     where
-        T: Type + Debug + PartialEq + Sync + Send + 'static,
+        T: Type + Debug + PartialEq + Hash + Sync + Send + 'static,
     {
         Self(Arc::new(any))
     }
@@ -254,11 +281,12 @@ trait Bounds: Debug + Sync + Send + 'static {
     fn as_any(&self) -> &dyn Any;
     fn dyn_eq(&self, other: &Dynamic) -> bool;
     fn dyn_type_name(&self) -> &'static str;
+    fn hash64(&self) -> u64;
 }
 
 impl<T> Bounds for T
 where
-    T: Type + Debug + PartialEq + Sync + Send + 'static,
+    T: Type + Debug + PartialEq + Hash + Sync + Send + 'static,
 {
     fn as_any(&self) -> &dyn Any {
         self
@@ -275,6 +303,21 @@ where
     fn dyn_type_name(&self) -> &'static str {
         T::TYPE_NAME
     }
+
+    fn hash64(&self) -> u64 {
+        // Also hash the TypeId since nodes with different types but
+        // equal data should be different.
+        let mut state = fxhash::FxHasher64::default();
+        self.type_id().hash(&mut state);
+        self.hash(&mut state);
+        state.finish()
+    }
+}
+
+impl Hash for dyn Bounds {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        state.write_u64(self.hash64());
+    }
 }
 
 /// The type of a value.