shape/
hashing.rs

1use std::hash::Hash;
2use std::hash::Hasher;
3
4use super::ShapeCase;
5use crate::helpers::inner_hasher;
6
7/// Because [`ShapeCase`] uses [`indexmap::IndexMap`] and [`indexmap::IndexSet`]
8/// for its Object, One, and All variants, the default derived Hash trait
9/// implementation does not work. Instead, we hash those cases manually, using a
10/// commutative operation (XOR) to combine the order-insensitive hashes of the
11/// elements.
12///
13/// ## Why plain XOR is safe here
14///
15/// XOR has two known footguns when used as an order-insensitive combiner:
16///
17/// 1. **Self-cancellation (`h ⊕ h = 0`):** if the same element-hash appears
18///    twice in the fold, the two contributions cancel out. Unreachable here:
19///    each combined sequence comes from an `IndexMap`/`IndexSet`, which
20///    deduplicates entries by key/value before iteration, so no element-hash
21///    can appear more than once.
22///
23/// 2. **Cross-cancellation (distinct elements that happen to hash to the same
24///    `u64`):** if two *distinct* elements collide in the inner hasher's
25///    64-bit output, their contributions XOR-cancel. With a deterministic
26///    inner hasher (the previous behavior) an attacker could precompute such
27///    collisions offline. With this implementation, inner hashers are
28///    constructed via [`crate::helpers::inner_hasher`], which is seeded from
29///    a per-process random `RandomState` — the same protection that
30///    `std::collections::HashMap` relies on for its outer key hashing. Finding
31///    a collision now requires either a birthday-paradox attack with `~2^32`
32///    distinct inputs (negligible at practical scale) or breaking `SipHash`
33///    with a random key, neither of which is feasible to engineer
34///    adversarially.
35///
36/// Within a single process run, equal shapes still hash to equal values (the
37/// random seed is initialized once and reused for every inner hasher). Raw
38/// `u64` hash output differs across process boundaries, which already matches
39/// the behavior any default `HashMap` lookup exhibits.
40impl Hash for ShapeCase {
41    fn hash<H: Hasher>(&self, state: &mut H) {
42        match self {
43            Self::Bool(value) => ("::Bool", value).hash(state),
44            Self::String(value) => ("::String", value).hash(state),
45            Self::Int(value) => ("::Int", value).hash(state),
46            Self::Float => "::Float".hash(state),
47            Self::Null => "::Null".hash(state),
48            Self::Array { prefix, tail } => ("::Array", prefix, tail).hash(state),
49            Self::Object { fields, rest } => {
50                // Plain XOR — `IndexMap` ensures each key is iterated once
51                // (no self-cancellation), and `inner_hasher()` is randomly
52                // seeded (no precomputable cross-cancellation). See the
53                // module-level doc for the full argument.
54                let fields_hash = fields.iter().fold(0, |acc, (key, value)| {
55                    let mut fields_hasher = inner_hasher();
56                    key.hash(&mut fields_hasher);
57                    value.hash(&mut fields_hasher);
58                    acc ^ fields_hasher.finish()
59                });
60                ("::Object", fields_hash, rest).hash(state);
61            }
62            Self::One(shapes) => {
63                // Plain XOR — `IndexSet`-backed union, same safety argument
64                // as the `::Object` arm above.
65                let xor_hash = shapes.iter().fold(0, |acc, shape| {
66                    let mut shape_hasher = inner_hasher();
67                    shape.hash(&mut shape_hasher);
68                    acc ^ shape_hasher.finish()
69                });
70                ("::One", xor_hash).hash(state);
71            }
72            Self::All(shapes) => {
73                // Plain XOR — `IndexSet`-backed intersection, same safety
74                // argument as the `::Object` arm above.
75                let xor_hash = shapes.iter().fold(0, |acc, shape| {
76                    let mut shape_hasher = inner_hasher();
77                    shape.hash(&mut shape_hasher);
78                    acc ^ shape_hasher.finish()
79                });
80                ("::All", xor_hash).hash(state);
81            }
82            // Ignore the WeakScope in order to maintain a stable hash
83            // before/after Namespace finalization.
84            Self::Name(name, _weak) => ("::Name", name).hash(state),
85            Self::Unknown => "::Unknown".hash(state),
86            Self::None => "::None".hash(state),
87        }
88    }
89}
shape/hashing.rs

shape/
hashing.rs
