commonware_codec/types/
hash_set.rs

1//! Codec implementations for HashSet (requires std).
2//!
3//! For portability and consistency between architectures,
4//! the size of the set must fit within a [u32].
5
6use crate::{
7    Buf, RangeCfg,
8    codec::{BufsMut, EncodeSize, Read, Write},
9    error::Error,
10    types::read_ordered_set,
11};
12use bytes::BufMut;
13use std::{collections::HashSet, hash::Hash};
14
15const HASHSET_TYPE: &str = "HashSet";
16
17impl<K: Ord + Write, S> Write for HashSet<K, S> {
18    fn write(&self, buf: &mut impl BufMut) {
19        self.len().write(buf);
20
21        // Sort the items to ensure deterministic encoding
22        let mut items: Vec<_> = self.iter().collect();
23        items.sort_unstable();
24        for item in items {
25            item.write(buf);
26        }
27    }
28
29    fn write_bufs(&self, buf: &mut impl BufsMut) {
30        self.len().write(buf);
31
32        // Sort the items to ensure deterministic encoding
33        let mut items: Vec<_> = self.iter().collect();
34        items.sort_unstable();
35        for item in items {
36            item.write_bufs(buf);
37        }
38    }
39}
40
41impl<K: EncodeSize, S> EncodeSize for HashSet<K, S> {
42    fn encode_size(&self) -> usize {
43        let mut size = self.len().encode_size();
44
45        // Note: Iteration order doesn't matter for size calculation.
46        for item in self {
47            size += item.encode_size();
48        }
49        size
50    }
51
52    fn encode_inline_size(&self) -> usize {
53        let mut size = self.len().encode_size();
54
55        // Note: Iteration order doesn't matter for size calculation.
56        for item in self {
57            size += item.encode_inline_size();
58        }
59        size
60    }
61}
62
63impl<K: Read + Ord + Hash> Read for HashSet<K> {
64    type Cfg = (RangeCfg<usize>, K::Cfg);
65
66    fn read_cfg(buf: &mut impl Buf, (range, cfg): &Self::Cfg) -> Result<Self, Error> {
67        // Read and validate the length prefix
68        let len = usize::read_cfg(buf, range)?;
69        let mut set = Self::with_capacity(len.min(buf.remaining()));
70
71        // Read items in ascending order
72        read_ordered_set(buf, len, cfg, |item| set.insert(item), HASHSET_TYPE)?;
73
74        Ok(set)
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81    use crate::{
82        FixedSize,
83        codec::{Decode, Encode},
84        types::tests::TrackingWriteBuf,
85    };
86    use bytes::{Bytes, BytesMut};
87    use std::{collections::BTreeSet, fmt::Debug};
88
89    // Generic round trip test function for HashSet
90    fn round_trip_hash<K>(set: &HashSet<K>, range_cfg: RangeCfg<usize>, item_cfg: K::Cfg)
91    where
92        K: Write + EncodeSize + Read + Ord + Hash + Debug,
93        HashSet<K>: Read<Cfg = (RangeCfg<usize>, K::Cfg)>
94            + Decode<Cfg = (RangeCfg<usize>, K::Cfg)>
95            + Debug
96            + PartialEq
97            + Write
98            + EncodeSize,
99    {
100        let encoded = set.encode();
101        assert_eq!(set.encode_size(), encoded.len());
102        let config_tuple = (range_cfg, item_cfg);
103        let decoded = HashSet::<K>::decode_cfg(encoded, &config_tuple).expect("decode_cfg failed");
104        assert_eq!(set, &decoded);
105    }
106
107    // --- HashSet Tests ---
108
109    #[test]
110    fn test_empty_hashset() {
111        let set = HashSet::<u32>::new();
112        round_trip_hash(&set, (..).into(), ());
113        assert_eq!(set.encode_size(), 1); // varint 0
114        let encoded = set.encode();
115        assert_eq!(encoded, Bytes::from_static(&[0]));
116    }
117
118    #[test]
119    fn test_simple_hashset_u32() {
120        let mut set = HashSet::new();
121        set.insert(1u32);
122        set.insert(5u32);
123        set.insert(2u32);
124        round_trip_hash(&set, (..).into(), ());
125        // Size calculation: varint len + size of each item (order doesn't matter for size)
126        assert_eq!(set.encode_size(), 1 + 3 * u32::SIZE);
127        // Encoding check: items must be sorted (1, 2, 5)
128        let mut expected = BytesMut::new();
129        3usize.write(&mut expected); // Set length = 3
130        1u32.write(&mut expected);
131        2u32.write(&mut expected);
132        5u32.write(&mut expected);
133        assert_eq!(set.encode(), expected.freeze());
134    }
135
136    #[test]
137    fn test_large_hashset() {
138        // Fixed-size items
139        let set: HashSet<_> = (0..1000u16).collect();
140        round_trip_hash(&set, (1000..=1000).into(), ());
141
142        // Variable-size items
143        let set: HashSet<_> = (0..1000usize).collect();
144        round_trip_hash(&set, (1000..=1000).into(), (..=1000).into());
145    }
146
147    #[test]
148    fn test_hashset_with_variable_items() {
149        let mut set = HashSet::new();
150        set.insert(Bytes::from_static(b"apple"));
151        set.insert(Bytes::from_static(b"banana"));
152        set.insert(Bytes::from_static(b"cherry"));
153
154        let set_range = 0..=10;
155        let item_range = ..=10; // Range for Bytes length
156
157        round_trip_hash(&set, set_range.into(), item_range.into());
158    }
159
160    #[test]
161    fn test_hashset_decode_length_limit_exceeded() {
162        let mut set = HashSet::new();
163        set.insert(1u32);
164        set.insert(5u32);
165
166        let encoded = set.encode();
167        let config_tuple = ((0..=1).into(), ());
168
169        let result = HashSet::<u32>::decode_cfg(encoded, &config_tuple);
170        assert!(matches!(result, Err(Error::InvalidLength(2))));
171    }
172
173    #[test]
174    fn test_hashset_decode_item_length_limit_exceeded() {
175        let mut set = HashSet::new();
176        set.insert(Bytes::from_static(b"longitem")); // 8 bytes
177
178        let set_range = 0..=10;
179        let restrictive_item_range = ..=5; // Limit item length
180
181        let encoded = set.encode();
182        let config_tuple = (set_range.into(), restrictive_item_range.into());
183        let result = HashSet::<Bytes>::decode_cfg(encoded, &config_tuple);
184
185        assert!(matches!(result, Err(Error::InvalidLength(8))));
186    }
187
188    #[test]
189    fn test_hashset_decode_invalid_item_order() {
190        let mut encoded = BytesMut::new();
191        2usize.write(&mut encoded); // Set length = 2
192        5u32.write(&mut encoded); // Item 5
193        2u32.write(&mut encoded); // Item 2 (out of order)
194
195        let config_tuple = ((..).into(), ());
196
197        let result = HashSet::<u32>::decode_cfg(encoded, &config_tuple);
198        assert!(matches!(
199            result,
200            Err(Error::Invalid("HashSet", "Items must ascend"))
201        ));
202    }
203
204    #[test]
205    fn test_hashset_decode_duplicate_item() {
206        let mut encoded = BytesMut::new();
207        2usize.write(&mut encoded); // Set length = 2
208        1u32.write(&mut encoded); // Item 1
209        1u32.write(&mut encoded); // Duplicate Item 1
210
211        let config_tuple = ((..).into(), ());
212        let result = HashSet::<u32>::decode_cfg(encoded, &config_tuple);
213        assert!(matches!(
214            result,
215            Err(Error::Invalid("HashSet", "Duplicate item"))
216        ));
217    }
218
219    #[test]
220    fn test_hashset_decode_end_of_buffer() {
221        let mut set = HashSet::new();
222        set.insert(1u32);
223        set.insert(5u32);
224
225        let mut encoded = set.encode(); // Will be sorted: [1, 5]
226        encoded.truncate(set.encode_size() - 2); // Truncate during last item (5)
227
228        let config_tuple = ((..).into(), ());
229        let result = HashSet::<u32>::decode_cfg(encoded, &config_tuple);
230        assert!(matches!(result, Err(Error::EndOfBuffer)));
231    }
232
233    #[test]
234    fn test_hashset_decode_extra_data() {
235        let mut set = HashSet::new();
236        set.insert(1u32);
237
238        let mut encoded = set.encode_mut();
239        encoded.put_u8(0xFF); // Add extra byte
240
241        // Use decode_cfg which enforces buffer is fully consumed
242        let config_tuple = ((..).into(), ()); // Clone range for read_cfg later
243        let result = HashSet::<u32>::decode_cfg(encoded.clone(), &config_tuple);
244        assert!(matches!(result, Err(Error::ExtraData(1))));
245
246        // Verify that read_cfg would succeed (doesn't check for extra data)
247        let read_result = HashSet::<u32>::read_cfg(&mut encoded.clone(), &config_tuple);
248        assert!(read_result.is_ok());
249        let decoded_set = read_result.unwrap();
250        assert_eq!(decoded_set.len(), 1);
251        assert!(decoded_set.contains(&1u32));
252    }
253
254    #[test]
255    fn test_hashset_deterministic_encoding() {
256        let mut set1 = HashSet::new();
257        (0..1000u32).for_each(|i| {
258            set1.insert(i);
259        });
260
261        let mut set2 = HashSet::new();
262        (0..1000u32).rev().for_each(|i| {
263            set2.insert(i);
264        });
265
266        assert_eq!(set1.encode(), set2.encode());
267    }
268
269    #[test]
270    fn test_hashset_encoding_matches_ordered_set() {
271        // Ordered sets provide the canonical encoding across collection sizes.
272        for len in [0, 1, 20, 128, 1024] {
273            let ordered: BTreeSet<_> = (0..len)
274                .map(|key: u32| Bytes::copy_from_slice(&key.to_le_bytes()))
275                .collect();
276            let expected = ordered.encode();
277
278            // Insertion order must not affect the encoded bytes.
279            for reverse in [false, true] {
280                let mut entries: Vec<_> = ordered.iter().cloned().collect();
281                if reverse {
282                    entries.reverse();
283                }
284                let set: HashSet<_> = entries.into_iter().collect();
285                assert_eq!(set.encode(), expected);
286
287                // Bytes items exercise external chunks alongside inline lengths.
288                let mut buf = TrackingWriteBuf::new();
289                set.write_bufs(&mut buf);
290                assert_eq!(buf.freeze(), expected);
291            }
292        }
293    }
294
295    #[test]
296    fn test_hashset_conformity() {
297        // Case 1: Empty HashSet<u8>
298        let set1 = HashSet::<u8>::new();
299        let mut expected1 = BytesMut::new();
300        0usize.write(&mut expected1); // Length 0
301        assert_eq!(set1.encode(), expected1.freeze());
302        assert_eq!(set1.encode_size(), 1);
303
304        // Case 2: Simple HashSet<u8>
305        // HashSet will sort items for encoding: 1, 2, 5
306        let mut set2 = HashSet::<u8>::new();
307        set2.insert(5u8);
308        set2.insert(1u8);
309        set2.insert(2u8);
310
311        let mut expected2 = BytesMut::new();
312        3usize.write(&mut expected2); // Length 3
313        1u8.write(&mut expected2); // Item 1
314        2u8.write(&mut expected2); // Item 2
315        5u8.write(&mut expected2); // Item 5
316        assert_eq!(set2.encode(), expected2.freeze());
317        assert_eq!(set2.encode_size(), 1 + 3);
318
319        // Case 3: HashSet<Bytes>
320        // HashSet sorts items for encoding: "apple", "banana", "cherry"
321        let mut set3 = HashSet::<Bytes>::new();
322        set3.insert(Bytes::from_static(b"cherry"));
323        set3.insert(Bytes::from_static(b"apple"));
324        set3.insert(Bytes::from_static(b"banana"));
325
326        let mut expected3 = BytesMut::new();
327        3usize.write(&mut expected3); // Length 3
328        Bytes::from_static(b"apple").write(&mut expected3);
329        Bytes::from_static(b"banana").write(&mut expected3);
330        Bytes::from_static(b"cherry").write(&mut expected3);
331        assert_eq!(set3.encode(), expected3.freeze());
332        let expected_size = 1usize.encode_size()
333            + Bytes::from_static(b"apple").encode_size()
334            + Bytes::from_static(b"banana").encode_size()
335            + Bytes::from_static(b"cherry").encode_size();
336        assert_eq!(set3.encode_size(), expected_size);
337    }
338
339    #[test]
340    fn test_hashset_malicious_allocation() {
341        // A length prefix advertising the maximum wire-encodable length (u32::MAX) with a
342        // single-element payload must fail with [Error::EndOfBuffer] without attempting the
343        // advertised allocation.
344        let mut malicious_buf = BytesMut::new();
345        (u32::MAX as usize).write(&mut malicious_buf);
346        1u32.write(&mut malicious_buf);
347
348        let result = HashSet::<u32>::decode_cfg(malicious_buf.freeze(), &((..).into(), ()));
349        assert!(matches!(result, Err(Error::EndOfBuffer)));
350    }
351
352    #[cfg(feature = "arbitrary")]
353    mod conformance {
354        use super::*;
355        use crate::conformance::CodecConformance;
356
357        commonware_conformance::conformance_tests! {
358            CodecConformance<HashSet<u32>>
359        }
360    }
361}
commonware_codec/types/hash_set.rs

commonware_codec/types/
hash_set.rs
