shape/
hashing.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
use super::ShapeCase;
use crate::case_enum::Error;
use std::hash::Hash;
use std::hash::Hasher;

/// Because [`ShapeCase`] uses [`IndexMap`] and [`IndexSet`] for its Object, One, and All
/// variants, the default derived Hash trait implementation does not work.
/// Instead, we hash those cases manually, using a commutative operation to
/// combine the order-insensitive hashes of the elements.
impl Hash for ShapeCase {
    fn hash<H: Hasher>(&self, state: &mut H) {
        match self {
            Self::Bool(value) => ("::Bool", value).hash(state),
            Self::String(value) => ("::String", value).hash(state),
            Self::Int(value) => ("::Int", value).hash(state),
            Self::Float => "::Float".hash(state),
            Self::Null => "::Null".hash(state),
            Self::Array { prefix, tail } => ("::Array", prefix, tail).hash(state),
            Self::Object { fields, rest } => {
                // Hash each (key, value) pair and then combine the hashes with
                // a commutative operation like XOR (without sorting the keys).
                let fields_hash = fields.iter().fold(0, |acc, (key, value)| {
                    let mut fields_hasher = std::collections::hash_map::DefaultHasher::new();
                    key.hash(&mut fields_hasher);
                    value.hash(&mut fields_hasher);
                    // TODO Is XOR the best operation here?
                    acc ^ fields_hasher.finish()
                });
                ("::Object", fields_hash, rest).hash(state);
            }
            Self::One(shapes) => {
                let xor_hash = shapes.iter().fold(0, |acc, shape| {
                    let mut shape_hasher = std::collections::hash_map::DefaultHasher::new();
                    shape.hash(&mut shape_hasher);
                    acc ^ shape_hasher.finish()
                });
                ("::One", xor_hash).hash(state);
            }
            Self::All(shapes) => {
                let xor_hash = shapes.iter().fold(0, |acc, shape| {
                    let mut shape_hasher = std::collections::hash_map::DefaultHasher::new();
                    shape.hash(&mut shape_hasher);
                    acc ^ shape_hasher.finish()
                });
                ("::All", xor_hash).hash(state);
            }
            Self::Name(name, subpath) => ("::Name", name, subpath).hash(state),
            Self::Unknown => "::Unknown".hash(state),
            Self::None => "::None".hash(state),
            Self::Error(Error { message, partial }) => ("::Error", message, partial).hash(state),
        }
    }
}