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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
use std::hash::Hash;
use std::hash::Hasher;

use super::Shape;
use super::ShapeCase;

impl Hash for Shape {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.case_hash.hash(state);
    }
}

/// 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() as u64
                });
                ("::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() as u64
                });
                ("::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() as u64
                });
                ("::All", xor_hash).hash(state)
            }
            Self::Name(name, subpath) => ("::Name", name, subpath).hash(state),
            Self::None => "::None".hash(state),
            Self::Error {
                message,
                range,
                partial,
            } => ("::Error", message, range, partial).hash(state),
        }
    }
}

impl ShapeCase {
    pub fn compute_hash(&self) -> u64 {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        self.hash(&mut hasher);
        hasher.finish() as u64
    }
}