jsonschema_value/
unique.rs

1use crate::cmp;
2use ahash::{AHashSet, AHasher};
3use serde_json::Value;
4use std::{
5    borrow::Borrow,
6    hash::{Hash, Hasher},
7};
8
9// Based on implementation proposed by Sven Marnach:
10// https://stackoverflow.com/questions/60882381/what-is-the-fastest-correct-way-to-detect-that-there-are-no-duplicates-in-a-json
11pub(crate) struct HashedValue<'a>(&'a Value);
12
13impl PartialEq for HashedValue<'_> {
14    fn eq(&self, other: &Self) -> bool {
15        cmp::equal(self.0, other.0)
16    }
17}
18
19impl Eq for HashedValue<'_> {}
20
21impl Hash for HashedValue<'_> {
22    fn hash<H: Hasher>(&self, state: &mut H) {
23        match self.0 {
24            Value::Null => state.write_u32(3_221_225_473), // chosen randomly
25            Value::Bool(ref item) => item.hash(state),
26            Value::Number(ref item) => {
27                if let Some(number) = item.as_f64() {
28                    number.to_bits().hash(state);
29                } else if let Some(number) = item.as_u64() {
30                    number.hash(state);
31                } else if let Some(number) = item.as_i64() {
32                    number.hash(state);
33                }
34            }
35            Value::String(ref item) => item.hash(state),
36            Value::Array(ref items) => {
37                for item in items {
38                    HashedValue(item).hash(state);
39                }
40            }
41            Value::Object(ref items) => {
42                let mut hash = 0;
43                for (key, value) in items {
44                    // We have no way of building a new hasher of type `H`, so we
45                    // hardcode using the default hasher of a hash map.
46                    let mut item_hasher = AHasher::default();
47                    key.hash(&mut item_hasher);
48                    HashedValue(value).hash(&mut item_hasher);
49                    hash ^= item_hasher.finish();
50                }
51                state.write_u64(hash);
52            }
53        }
54    }
55}
56
57// Empirically calculated threshold after which the validator resorts to hashing.
58// Calculated for an array of mixed types, large homogeneous arrays of primitive values might be
59// processed faster with different thresholds, but this one gives a good baseline for the common
60// case.
61pub(crate) const ITEMS_SIZE_THRESHOLD: usize = 15;
62
63// Generic over `Borrow<Value>` so both borrowed `serde_json` slices and the `Cow<Value>` handles
64// materialized from other representations run the same duplicate-detection algorithm.
65#[inline]
66#[must_use]
67pub fn is_unique<T: Borrow<Value>>(items: &[T]) -> bool {
68    let size = items.len();
69    if size <= 1 {
70        // Empty arrays and one-element arrays always contain unique elements
71        true
72    } else if let [first, second] = items {
73        !cmp::equal(first.borrow(), second.borrow())
74    } else if let [first, second, third] = items {
75        !cmp::equal(first.borrow(), second.borrow())
76            && !cmp::equal(first.borrow(), third.borrow())
77            && !cmp::equal(second.borrow(), third.borrow())
78    } else if size <= ITEMS_SIZE_THRESHOLD {
79        // If the array size is small enough we can compare all elements pairwise, which will
80        // be faster than calculating hashes for each element, even if the algorithm is O(N^2)
81        let mut idx = 0_usize;
82        while idx < items.len() {
83            let mut inner_idx = idx + 1;
84            while inner_idx < items.len() {
85                if cmp::equal(items[idx].borrow(), items[inner_idx].borrow()) {
86                    return false;
87                }
88                inner_idx += 1;
89            }
90            idx += 1;
91        }
92        true
93    } else {
94        let mut seen = AHashSet::with_capacity(size);
95        items
96            .iter()
97            .map(|item| HashedValue(item.borrow()))
98            .all(move |x| seen.insert(x))
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::{is_unique, ITEMS_SIZE_THRESHOLD};
105    use serde_json::{json, Value};
106    use test_case::test_case;
107
108    #[test_case(&[] => true; "empty array")]
109    #[test_case(&[json!(1)] => true; "one element array")]
110    #[test_case(&[json!(1), json!(2)] => true; "two unique elements")]
111    #[test_case(&[json!(1), json!(1)] => false; "two non-unique elements")]
112    #[test_case(&[json!(1), json!(2), json!(3)] => true; "three unique elements")]
113    #[test_case(&[json!(1), json!(2), json!(1)] => false; "three non-unique elements")]
114    #[test_case(&[json!(1), json!(2), json!(3), json!(4), json!(5), json!(6), json!(7), json!(8), json!(9), json!(10), json!(11), json!(12), json!(13), json!(14), json!(15), json!(1.0)] => false; "positive numbers with fractions")]
115    #[test_case(&[json!(-1), json!(-2), json!(-3), json!(-4), json!(-5), json!(-6), json!(-7), json!(-8), json!(-9), json!(-10), json!(-11), json!(-12), json!(-13), json!(-14), json!(-15), json!(-1.0)] => false; "negative numbers with fractions")]
116    #[test_case(&[json!(1), json!("string"), json!(true), json!(null), json!({"key": "value"}), json!([1, 2, 3])] => true; "mixed types")]
117    #[test_case(&[json!({"a": 1, "b": 1}), json!({"a": 1, "b": 2}), json!({"a": 1, "b": 3})] => true; "complex objects unique")]
118    #[test_case(&[json!({"a": 1, "b": 2}), json!({"b": 2, "a": 1}), json!({"a": 1, "b": 2})] => false; "complex objects non-unique")]
119    fn test_is_unique(items: &[Value]) -> bool {
120        is_unique(items)
121    }
122
123    #[test_case(ITEMS_SIZE_THRESHOLD => true; "small array unique")]
124    #[test_case(ITEMS_SIZE_THRESHOLD + 1 => true; "large array unique")]
125    fn test_unique_arrays(size: usize) -> bool {
126        let arr = (1..=size).map(|i| json!(i)).collect::<Vec<_>>();
127        is_unique(&arr)
128    }
129
130    #[test_case(ITEMS_SIZE_THRESHOLD => false; "small array non-unique")]
131    #[test_case(ITEMS_SIZE_THRESHOLD + 1 => false; "large array non-unique")]
132    fn test_non_unique_arrays(size: usize) -> bool {
133        let mut arr = (1..=size).map(|i| json!(i)).collect::<Vec<_>>();
134        arr[size - 1] = json!(1);
135        is_unique(&arr)
136    }
137}
jsonschema_value/unique.rs

jsonschema_value/
unique.rs
