Make values hashable

11 files changed, 219 insertions, 31 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.
diff --git a/src/geom/angle.rs b/src/geom/angle.rs
index acf3803d..ef3276e8 100644
--- a/src/geom/angle.rs
+++ b/src/geom/angle.rs
@@ -123,7 +123,7 @@ impl Sum for Angle {
     }
 }
 /// Different units of angular measurement.
-#[derive(Copy, Clone, Eq, PartialEq)]
+#[derive(Copy, Clone, Eq, PartialEq, Hash)]
 pub enum AngularUnit {
     /// Radians.
     Rad,
diff --git a/src/geom/length.rs b/src/geom/length.rs
index a095b9ad..c5fbfd76 100644
--- a/src/geom/length.rs
+++ b/src/geom/length.rs
@@ -211,7 +211,7 @@ impl<'a> Sum<&'a Self> for Length {
 }
 
 /// Different units of length measurement.
-#[derive(Copy, Clone, Eq, PartialEq)]
+#[derive(Copy, Clone, Eq, PartialEq, Hash)]
 pub enum LengthUnit {
     /// Points.
     Pt,
diff --git a/src/syntax/ast.rs b/src/syntax/ast.rs
index 560d7c30..8b88096a 100644
--- a/src/syntax/ast.rs
+++ b/src/syntax/ast.rs
@@ -30,7 +30,7 @@ macro_rules! node {
         node!{$(#[$attr])* $name: NodeKind::$variant}
     };
     ($(#[$attr:meta])* $name:ident: $variants:pat) => {
-        #[derive(Debug, Clone, PartialEq)]
+        #[derive(Debug, Clone, PartialEq, Hash)]
         #[repr(transparent)]
         $(#[$attr])*
         pub struct $name(RedNode);
@@ -138,7 +138,7 @@ impl EmphNode {
 }
 
 /// A raw block with optional syntax highlighting: `` `...` ``.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone, PartialEq, Hash)]
 pub struct RawNode {
     /// An optional identifier specifying the language to syntax-highlight in.
     pub lang: Option<EcoString>,
@@ -151,7 +151,7 @@ pub struct RawNode {
 }
 
 /// A math formula: `$a^2 + b^2 = c^2$`.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone, PartialEq, Hash)]
 pub struct MathNode {
     /// The formula between the dollars / brackets.
     pub formula: EcoString,
@@ -213,7 +213,7 @@ impl EnumNode {
 }
 
 /// An expression.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone, PartialEq, Hash)]
 pub enum Expr {
     /// A literal: `1`, `true`, ...
     Lit(Lit),
@@ -504,7 +504,7 @@ impl UnaryExpr {
 }
 
 /// A unary operator.
-#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
 pub enum UnOp {
     /// The plus operator: `+`.
     Pos,
@@ -573,7 +573,7 @@ impl BinaryExpr {
 }
 
 /// A binary operator.
-#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
 pub enum BinOp {
     /// The addition operator: `+`.
     Add,
@@ -707,7 +707,7 @@ impl BinOp {
 }
 
 /// The associativity of a binary operator.
-#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
 pub enum Associativity {
     /// Left-associative: `a + b + c` is equivalent to `(a + b) + c`.
     Left,
@@ -745,7 +745,7 @@ impl CallArgs {
 }
 
 /// An argument to a function call.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone, PartialEq, Hash)]
 pub enum CallArg {
     /// A positional argument: `12`.
     Pos(Expr),
@@ -814,7 +814,7 @@ impl ClosureExpr {
 }
 
 /// A parameter to a closure.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone, PartialEq, Hash)]
 pub enum ClosureParam {
     /// A positional parameter: `x`.
     Pos(Ident),
@@ -1059,7 +1059,7 @@ impl ImportExpr {
 }
 
 /// The items that ought to be imported from a file.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone, PartialEq, Hash)]
 pub enum Imports {
     /// All items in the scope of the file should be imported.
     Wildcard,
diff --git a/src/syntax/mod.rs b/src/syntax/mod.rs
index a26384e1..c0de081d 100644
--- a/src/syntax/mod.rs
+++ b/src/syntax/mod.rs
@@ -6,6 +6,7 @@ mod pretty;
 mod span;
 
 use std::fmt::{self, Debug, Display, Formatter};
+use std::hash::{Hash, Hasher};
 use std::ops::Range;
 use std::sync::Arc;
 
@@ -21,7 +22,7 @@ use crate::source::SourceId;
 use crate::util::EcoString;
 
 /// An inner or leaf node in the untyped green tree.
-#[derive(Clone, PartialEq)]
+#[derive(Clone, PartialEq, Hash)]
 pub enum Green {
     /// A reference-counted inner node.
     Node(Arc<GreenNode>),
@@ -101,7 +102,7 @@ impl Debug for Green {
 }
 
 /// An inner node in the untyped green tree.
-#[derive(Clone, PartialEq)]
+#[derive(Clone, PartialEq, Hash)]
 pub struct GreenNode {
     /// Node metadata.
     data: GreenData,
@@ -209,7 +210,7 @@ impl Debug for GreenNode {
 }
 
 /// Data shared between inner and leaf nodes.
-#[derive(Clone, PartialEq)]
+#[derive(Clone, PartialEq, Hash)]
 pub struct GreenData {
     /// What kind of node this is (each kind would have its own struct in a
     /// strongly typed AST).
@@ -250,7 +251,7 @@ impl Debug for GreenData {
 /// A owned wrapper for a green node with span information.
 ///
 /// Owned variant of [`RedRef`]. Can be [cast](Self::cast) to an AST node.
-#[derive(Clone, PartialEq)]
+#[derive(Clone, PartialEq, Hash)]
 pub struct RedNode {
     id: SourceId,
     offset: usize,
@@ -325,7 +326,7 @@ impl Debug for RedNode {
 /// A borrowed wrapper for a [`GreenNode`] with span information.
 ///
 /// Borrowed variant of [`RedNode`]. Can be [cast](Self::cast) to an AST node.
-#[derive(Copy, Clone, PartialEq)]
+#[derive(Copy, Clone, PartialEq, Hash)]
 pub struct RedRef<'a> {
     id: SourceId,
     offset: usize,
@@ -716,7 +717,7 @@ pub enum NodeKind {
 }
 
 /// Where in a node an error should be annotated.
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 pub enum ErrorPos {
     /// At the start of the node.
     Start,
@@ -932,3 +933,119 @@ impl Display for NodeKind {
         f.pad(self.as_str())
     }
 }
+
+impl Hash for NodeKind {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        std::mem::discriminant(self).hash(state);
+        match self {
+            Self::LeftBracket => {}
+            Self::RightBracket => {}
+            Self::LeftBrace => {}
+            Self::RightBrace => {}
+            Self::LeftParen => {}
+            Self::RightParen => {}
+            Self::Star => {}
+            Self::Underscore => {}
+            Self::Comma => {}
+            Self::Semicolon => {}
+            Self::Colon => {}
+            Self::Plus => {}
+            Self::Minus => {}
+            Self::Slash => {}
+            Self::Eq => {}
+            Self::EqEq => {}
+            Self::ExclEq => {}
+            Self::Lt => {}
+            Self::LtEq => {}
+            Self::Gt => {}
+            Self::GtEq => {}
+            Self::PlusEq => {}
+            Self::HyphEq => {}
+            Self::StarEq => {}
+            Self::SlashEq => {}
+            Self::Not => {}
+            Self::And => {}
+            Self::Or => {}
+            Self::With => {}
+            Self::Dots => {}
+            Self::Arrow => {}
+            Self::None => {}
+            Self::Auto => {}
+            Self::Let => {}
+            Self::Set => {}
+            Self::Show => {}
+            Self::Wrap => {}
+            Self::If => {}
+            Self::Else => {}
+            Self::For => {}
+            Self::In => {}
+            Self::As => {}
+            Self::While => {}
+            Self::Break => {}
+            Self::Continue => {}
+            Self::Return => {}
+            Self::Import => {}
+            Self::Include => {}
+            Self::From => {}
+            Self::Markup(c) => c.hash(state),
+            Self::Space(n) => n.hash(state),
+            Self::Linebreak => {}
+            Self::Parbreak => {}
+            Self::Text(s) => s.hash(state),
+            Self::TextInLine(s) => s.hash(state),
+            Self::NonBreakingSpace => {}
+            Self::EnDash => {}
+            Self::EmDash => {}
+            Self::Escape(c) => c.hash(state),
+            Self::Strong => {}
+            Self::Emph => {}
+            Self::Raw(raw) => raw.hash(state),
+            Self::Math(math) => math.hash(state),
+            Self::List => {}
+            Self::Heading => {}
+            Self::Enum => {}
+            Self::EnumNumbering(num) => num.hash(state),
+            Self::Ident(v) => v.hash(state),
+            Self::Bool(v) => v.hash(state),
+            Self::Int(v) => v.hash(state),
+            Self::Float(v) => v.to_bits().hash(state),
+            Self::Length(v, u) => (v.to_bits(), u).hash(state),
+            Self::Angle(v, u) => (v.to_bits(), u).hash(state),
+            Self::Percentage(v) => v.to_bits().hash(state),
+            Self::Fraction(v) => v.to_bits().hash(state),
+            Self::Str(v) => v.hash(state),
+            Self::Array => {}
+            Self::Dict => {}
+            Self::Named => {}
+            Self::Template => {}
+            Self::Group => {}
+            Self::Block => {}
+            Self::Unary => {}
+            Self::Binary => {}
+            Self::Call => {}
+            Self::CallArgs => {}
+            Self::Spread => {}
+            Self::Closure => {}
+            Self::ClosureParams => {}
+            Self::WithExpr => {}
+            Self::LetExpr => {}
+            Self::SetExpr => {}
+            Self::ShowExpr => {}
+            Self::WrapExpr => {}
+            Self::IfExpr => {}
+            Self::WhileExpr => {}
+            Self::ForExpr => {}
+            Self::ForPattern => {}
+            Self::ImportExpr => {}
+            Self::ImportItems => {}
+            Self::IncludeExpr => {}
+            Self::BreakExpr => {}
+            Self::ContinueExpr => {}
+            Self::ReturnExpr => {}
+            Self::LineComment => {}
+            Self::BlockComment => {}
+            Self::Error(pos, msg) => (pos, msg).hash(state),
+            Self::Unknown(src) => src.hash(state),
+        }
+    }
+}
diff --git a/src/syntax/span.rs b/src/syntax/span.rs
index ab2797f6..d1e29dd3 100644
--- a/src/syntax/span.rs
+++ b/src/syntax/span.rs
@@ -5,7 +5,7 @@ use std::ops::Range;
 use crate::source::SourceId;
 
 /// A value with the span it corresponds to in the source code.
-#[derive(Copy, Clone, Eq, PartialEq)]
+#[derive(Copy, Clone, Eq, PartialEq, Hash)]
 pub struct Spanned<T> {
     /// The spanned value.
     pub v: T,
@@ -46,7 +46,7 @@ impl<T: Debug> Debug for Spanned<T> {
 }
 
 /// Bounds of a slice of source code.
-#[derive(Copy, Clone, Eq, PartialEq)]
+#[derive(Copy, Clone, Eq, PartialEq, Hash)]
 pub struct Span {
     /// The id of the source file.
     pub source: SourceId,