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

commonware_codec/types/
hash_map.rs
