commonware_codec/types/
hash_map.rs

1//! Codec implementations for HashMap (requires std).
2//!
3//! For portability and consistency between architectures,
4//! the size of the map must fit within a [u32].
5
6use crate::{
7    codec::{BufsMut, EncodeSize, Read, Write},
8    error::Error,
9    types::read_ordered_map,
10    RangeCfg,
11};
12use bytes::{Buf, BufMut};
13use std::{collections::HashMap, hash::Hash};
14
15const HASHMAP_TYPE: &str = "HashMap";
16
17// ---------- HashMap ----------
18
19impl<K: Ord + Hash + Eq + Write, V: Write> Write for HashMap<K, V> {
20    fn write(&self, buf: &mut impl BufMut) {
21        self.len().write(buf);
22
23        // Sort the keys to ensure deterministic encoding
24        let mut entries: Vec<_> = self.iter().collect();
25        entries.sort_by(|a, b| a.0.cmp(b.0));
26        for (k, v) in entries {
27            k.write(buf);
28            v.write(buf);
29        }
30    }
31
32    fn write_bufs(&self, buf: &mut impl BufsMut) {
33        self.len().write(buf);
34
35        // Sort the keys to ensure deterministic encoding
36        let mut entries: Vec<_> = self.iter().collect();
37        entries.sort_by(|a, b| a.0.cmp(b.0));
38        for (k, v) in entries {
39            k.write_bufs(buf);
40            v.write_bufs(buf);
41        }
42    }
43}
44
45impl<K: Ord + Hash + Eq + EncodeSize, V: EncodeSize> EncodeSize for HashMap<K, V> {
46    fn encode_size(&self) -> usize {
47        // Start with the size of the length prefix
48        let mut size = self.len().encode_size();
49
50        // Add the encoded size of each key and value
51        // Note: Iteration order doesn't matter for size calculation.
52        for (k, v) in self {
53            size += k.encode_size();
54            size += v.encode_size();
55        }
56        size
57    }
58
59    fn encode_inline_size(&self) -> usize {
60        // Start with the size of the length prefix
61        let mut size = self.len().encode_size();
62
63        // Add the encoded size of each key and value
64        // Note: Iteration order doesn't matter for size calculation.
65        for (k, v) in self {
66            size += k.encode_inline_size();
67            size += v.encode_inline_size();
68        }
69        size
70    }
71}
72
73// Read implementation for HashMap
74impl<K: Read + Clone + Ord + Hash + Eq, V: Read + Clone> Read for HashMap<K, V> {
75    type Cfg = (RangeCfg<usize>, (K::Cfg, V::Cfg));
76
77    fn read_cfg(buf: &mut impl Buf, (range, (k_cfg, v_cfg)): &Self::Cfg) -> Result<Self, Error> {
78        // Read and validate the length prefix
79        let len = usize::read_cfg(buf, range)?;
80        let mut map = Self::with_capacity(len);
81
82        // Read items in ascending order
83        read_ordered_map(
84            buf,
85            len,
86            k_cfg,
87            v_cfg,
88            |k, v| map.insert(k, v),
89            HASHMAP_TYPE,
90        )?;
91
92        Ok(map)
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    use crate::{Decode, Encode, FixedSize};
100    use bytes::{Bytes, BytesMut};
101    use std::fmt::Debug;
102
103    // Manual round trip test function for HashMap with non-default configs
104    fn round_trip_hash<K, V, KCfg, VCfg>(
105        map: &HashMap<K, V>,
106        range_cfg: RangeCfg<usize>,
107        k_cfg: KCfg,
108        v_cfg: VCfg,
109    ) where
110        K: Write + EncodeSize + Read<Cfg = KCfg> + Clone + Ord + Hash + Eq + PartialEq + Debug,
111        V: Write + EncodeSize + Read<Cfg = VCfg> + Clone + PartialEq + Debug,
112        HashMap<K, V>: Read<Cfg = (RangeCfg<usize>, (K::Cfg, V::Cfg))>
113            + Decode<Cfg = (RangeCfg<usize>, (K::Cfg, V::Cfg))>
114            + PartialEq
115            + Write
116            + EncodeSize,
117    {
118        let encoded = map.encode();
119        assert_eq!(encoded.len(), map.encode_size());
120        let config_tuple = (range_cfg, (k_cfg, v_cfg));
121        let decoded = HashMap::<K, V>::decode_cfg(encoded, &config_tuple)
122            .expect("decode_cfg failed for HashMap");
123        assert_eq!(map, &decoded);
124    }
125
126    // --- HashMap Tests ---
127
128    #[test]
129    fn test_empty_hashmap() {
130        let map = HashMap::<u32, u64>::new();
131        round_trip_hash(&map, (..).into(), (), ());
132        assert_eq!(map.encode_size(), 1);
133        let encoded = map.encode();
134        assert_eq!(encoded, 0usize.encode());
135    }
136
137    #[test]
138    fn test_simple_hashmap_u32_u64() {
139        let mut map = HashMap::new();
140        map.insert(1u32, 100u64);
141        map.insert(5u32, 500u64);
142        map.insert(2u32, 200u64);
143        round_trip_hash(&map, (..).into(), (), ());
144        assert_eq!(map.encode_size(), 1 + 3 * (u32::SIZE + u64::SIZE));
145    }
146
147    #[test]
148    fn test_large_hashmap() {
149        // Fixed-size items
150        let mut map = HashMap::new();
151        for i in 0..1000 {
152            map.insert(i as u16, i as u64 * 2);
153        }
154        round_trip_hash(&map, (0..=1000).into(), (), ());
155
156        // Variable-size items
157        let mut map = HashMap::new();
158        for i in 0..1000usize {
159            map.insert(i, 1000usize + i);
160        }
161        round_trip_hash(
162            &map,
163            (0..=1000).into(),
164            (..=1000).into(),
165            (1000..=2000).into(),
166        );
167    }
168
169    #[test]
170    fn test_hashmap_with_variable_values() {
171        let mut map = HashMap::new();
172        map.insert(Bytes::from_static(b"apple"), vec![1, 2]);
173        map.insert(Bytes::from_static(b"banana"), vec![3, 4, 5]);
174        map.insert(Bytes::from_static(b"cherry"), vec![]);
175
176        let map_range = RangeCfg::from(0..=10);
177        let key_range = RangeCfg::from(..=10);
178        let val_range = RangeCfg::from(0..=100);
179
180        round_trip_hash(&map, map_range, key_range, (val_range, ()));
181    }
182
183    #[test]
184    fn test_hashmap_decode_length_limit_exceeded() {
185        let mut map = HashMap::new();
186        map.insert(1u32, 100u64);
187        map.insert(5u32, 500u64);
188
189        let encoded = map.encode();
190        let config_tuple = ((0..=1).into(), ((), ()));
191
192        let result = HashMap::<u32, u64>::decode_cfg(encoded, &config_tuple);
193        assert!(matches!(result, Err(Error::InvalidLength(2))));
194    }
195
196    #[test]
197    fn test_hashmap_decode_value_length_limit_exceeded() {
198        let mut map = HashMap::new();
199        map.insert(Bytes::from_static(b"key1"), vec![1u8, 2u8, 3u8, 4u8, 5u8]);
200
201        let key_range = RangeCfg::from(..=10);
202        let map_range = RangeCfg::from(0..=10);
203        let restrictive_val_range = RangeCfg::from(0..=3);
204
205        let encoded = map.encode();
206        let config_tuple = (map_range, (key_range, (restrictive_val_range, ())));
207        let result = HashMap::<Bytes, Vec<u8>>::decode_cfg(encoded, &config_tuple);
208
209        assert!(matches!(result, Err(Error::InvalidLength(5))));
210    }
211
212    #[test]
213    fn test_hashmap_decode_invalid_key_order() {
214        let mut encoded = BytesMut::new();
215        2usize.write(&mut encoded); // Map length = 2
216        5u32.write(&mut encoded); // Key 5
217        500u64.write(&mut encoded); // Value 500
218        2u32.write(&mut encoded); // Key 2 (out of order)
219        200u64.write(&mut encoded); // Value 200
220
221        let range = (..).into();
222        let config_tuple = (range, ((), ()));
223
224        let result = HashMap::<u32, u64>::decode_cfg(encoded, &config_tuple);
225        assert!(matches!(
226            result,
227            Err(Error::Invalid("HashMap", "Keys must ascend"))
228        ));
229    }
230
231    #[test]
232    fn test_hashmap_decode_duplicate_key() {
233        let mut encoded = BytesMut::new();
234        2usize.write(&mut encoded); // Map length = 2
235        1u32.write(&mut encoded); // Key 1
236        100u64.write(&mut encoded); // Value 100
237        1u32.write(&mut encoded); // Duplicate Key 1
238        200u64.write(&mut encoded); // Value 200
239
240        let range = (..).into();
241        let config_tuple = (range, ((), ()));
242
243        let result = HashMap::<u32, u64>::decode_cfg(encoded, &config_tuple);
244        assert!(matches!(
245            result,
246            Err(Error::Invalid("HashMap", "Duplicate key"))
247        ));
248    }
249
250    #[test]
251    fn test_hashmap_decode_end_of_buffer_key() {
252        let mut map = HashMap::new();
253        map.insert(1u32, 100u64);
254        map.insert(5u32, 500u64);
255
256        let mut encoded = map.encode();
257        encoded.truncate(map.encode_size() - 10); // Truncate during last key/value pair
258
259        let range = (..).into();
260        let config_tuple = (range, ((), ()));
261        let result = HashMap::<u32, u64>::decode_cfg(encoded, &config_tuple);
262        assert!(matches!(result, Err(Error::EndOfBuffer)));
263    }
264
265    #[test]
266    fn test_hashmap_decode_end_of_buffer_value() {
267        let mut map = HashMap::new();
268        map.insert(1u32, 100u64);
269        map.insert(5u32, 500u64);
270
271        let mut encoded = map.encode();
272        encoded.truncate(map.encode_size() - 4); // Truncate during last value
273
274        let range = RangeCfg::from(..);
275        let config_tuple = (range, ((), ()));
276        let result = HashMap::<u32, u64>::decode_cfg(encoded, &config_tuple);
277        assert!(matches!(result, Err(Error::EndOfBuffer)));
278    }
279
280    #[test]
281    fn test_hashmap_decode_extra_data() {
282        let mut map = HashMap::new();
283        map.insert(1u32, 100u64);
284
285        let mut encoded = map.encode_mut();
286        encoded.put_u8(0xFF); // Add extra byte
287
288        // Use decode_cfg which enforces buffer is fully consumed
289        let config_tuple = ((..).into(), ((), ()));
290        let result = HashMap::<u32, u64>::decode_cfg(encoded.clone(), &config_tuple);
291        assert!(matches!(result, Err(Error::ExtraData(1))));
292
293        // Verify that read_cfg would succeed (doesn't check for extra data)
294        let read_result = HashMap::<u32, u64>::read_cfg(&mut encoded, &config_tuple);
295        assert!(read_result.is_ok());
296        let decoded_map = read_result.unwrap();
297        assert_eq!(decoded_map.len(), 1);
298        assert_eq!(decoded_map.get(&1u32), Some(&100u64));
299    }
300
301    #[test]
302    fn test_hashmap_deterministic_encoding() {
303        // In-order
304        let mut map2 = HashMap::new();
305        (0..=1000u32).for_each(|i| {
306            map2.insert(i, i * 2);
307        });
308
309        // Reverse order
310        let mut map1 = HashMap::new();
311        (0..=1000u32).rev().for_each(|i| {
312            map1.insert(i, i * 2);
313        });
314
315        assert_eq!(map1.encode(), map2.encode());
316    }
317
318    #[test]
319    fn test_hashmap_conformity() {
320        // Case 1: Empty HashMap<u8, u16>
321        let map1 = HashMap::<u8, u16>::new();
322        let mut expected1 = BytesMut::new();
323        0usize.write(&mut expected1); // Length 0
324        assert_eq!(map1.encode(), expected1.freeze());
325
326        // Case 2: Simple HashMap<u8, u16>
327        // Keys are sorted for encoding: 1, 2
328        let mut map2 = HashMap::<u8, u16>::new();
329        map2.insert(2u8, 0xBBBBu16); // Inserted out of order
330        map2.insert(1u8, 0xAAAAu16);
331
332        let mut expected2 = BytesMut::new();
333        2usize.write(&mut expected2); // Length 2
334        1u8.write(&mut expected2); // Key 1
335        0xAAAAu16.write(&mut expected2); // Value for key 1
336        2u8.write(&mut expected2); // Key 2
337        0xBBBBu16.write(&mut expected2); // Value for key 2
338        assert_eq!(map2.encode(), expected2.freeze());
339
340        // Case 3: HashMap<u16, bool>
341        // Keys are sorted for encoding: 0x0101, 0x0202, 0x0303
342        let mut map3 = HashMap::<u16, bool>::new();
343        map3.insert(0x0303u16, true);
344        map3.insert(0x0101u16, false);
345        map3.insert(0x0202u16, true);
346
347        let mut expected3 = BytesMut::new();
348        3usize.write(&mut expected3); // Length 3
349        0x0101u16.write(&mut expected3); // Key 0x0101
350        false.write(&mut expected3); // Value false (0x00)
351        0x0202u16.write(&mut expected3); // Key 0x0202
352        true.write(&mut expected3); // Value true (0x01)
353        0x0303u16.write(&mut expected3); // Key 0x0303
354        true.write(&mut expected3); // Value true (0x01)
355        assert_eq!(map3.encode(), expected3.freeze());
356
357        // Case 4: HashMap with Bytes as key and Vec<u8> as value
358        // Keys are sorted for encoding: "a", "b"
359        let mut map4 = HashMap::<Bytes, Vec<u8>>::new();
360        map4.insert(Bytes::from_static(b"b"), vec![20u8, 21u8]);
361        map4.insert(Bytes::from_static(b"a"), vec![10u8]);
362
363        let mut expected4 = BytesMut::new();
364        2usize.write(&mut expected4); // Map length = 2
365
366        // Key "a" (length 1, 'a')
367        Bytes::from_static(b"a").write(&mut expected4);
368        // Value vec![10u8] (length 1, 10u8)
369        vec![10u8].write(&mut expected4);
370
371        // Key "b" (length 1, 'b')
372        Bytes::from_static(b"b").write(&mut expected4);
373        // Value vec![20u8, 21u8] (length 2, 20u8, 21u8)
374        vec![20u8, 21u8].write(&mut expected4);
375
376        assert_eq!(map4.encode(), expected4.freeze());
377    }
378
379    #[cfg(feature = "arbitrary")]
380    mod conformance {
381        use super::*;
382        use crate::conformance::CodecConformance;
383
384        commonware_conformance::conformance_tests! {
385            CodecConformance<HashMap<u32, u32>>,
386        }
387    }
388}
commonware_codec/types/hash_map.rs

commonware_codec/types/
hash_map.rs
