Make values hashable

3 files changed, 135 insertions, 18 deletions

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,