xianyun_core/
orderedmap.rs

1//! Port of `internal/orderedmap`: a generic ordered map that preserves
2//! insertion order and supports YAML/JSON (de)serialization.
3//!
4//! A default-constructed `OrderedMap` is empty and writable, mirroring the
5//! Go package's `New`. The Go package additionally treats a `nil *Map` (and
6//! Rust has no such state for an owned value) as a safe-to-read empty map;
7//! that distinction does not apply to an owned Rust type and is dropped here.
8//! See `PORT_NOTES.md`.
9
10use std::fmt;
11use std::hash::Hash;
12use std::marker::PhantomData;
13
14use serde::de::{MapAccess, Visitor};
15use serde::ser::SerializeMap;
16use serde::{Deserialize, Deserializer, Serialize, Serializer};
17
18/// A key-value pair, with position accessors mirroring the Go `Pair` type.
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub struct Pair<K, V> {
21    pub key: K,
22    pub value: V,
23}
24
25/// An ordered map preserving insertion order.
26#[derive(Debug, Default, Clone)]
27pub struct OrderedMap<K, V> {
28    _entries: Vec<Pair<K, V>>,
29}
30
31impl<K: Eq + Hash + Clone, V: Clone> OrderedMap<K, V> {
32    /// Creates a new, empty `OrderedMap`, optionally with a capacity hint.
33    pub fn new() -> Self {
34        Self {
35            _entries: Vec::new(),
36        }
37    }
38
39    /// Creates a new ordered map from a built-in map. The order is sorted
40    /// deterministically by key.
41    pub fn from_map(m: std::collections::HashMap<K, V>) -> Self
42    where
43        K: Ord,
44    {
45        let mut keys: Vec<K> = m.keys().cloned().collect();
46        keys.sort();
47        let mut om = Self::new();
48        let mut m = m;
49        for k in keys {
50            if let Some(v) = m.remove(&k) {
51                om.set(k, v);
52            }
53        }
54        om
55    }
56
57    fn position(&self, key: &K) -> Option<usize> {
58        self._entries.iter().position(|p| &p.key == key)
59    }
60
61    pub fn get(&self, key: &K) -> Option<&V> {
62        self.position(key).map(|i| &self._entries[i].value)
63    }
64
65    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
66        let i = self.position(key)?;
67        Some(&mut self._entries[i].value)
68    }
69
70    pub fn set(&mut self, key: K, value: V) {
71        if let Some(i) = self.position(&key) {
72            self._entries[i].value = value;
73        } else {
74            self._entries.push(Pair { key, value });
75        }
76    }
77
78    pub fn delete(&mut self, key: &K) -> Option<V> {
79        self.position(key).map(|i| self._entries.remove(i).value)
80    }
81
82    pub fn len(&self) -> usize {
83        self._entries.len()
84    }
85
86    pub fn is_empty(&self) -> bool {
87        self.len() == 0
88    }
89
90    pub fn has(&self, key: &K) -> bool {
91        self.position(key).is_some()
92    }
93
94    pub fn oldest(&self) -> Option<&Pair<K, V>> {
95        self._entries.first()
96    }
97
98    pub fn newest(&self) -> Option<&Pair<K, V>> {
99        self._entries.last()
100    }
101
102    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
103        self._entries.iter().map(|p| (&p.key, &p.value))
104    }
105
106    pub fn keys(&self) -> Vec<K> {
107        self._entries.iter().map(|p| p.key.clone()).collect()
108    }
109
110    pub fn values(&self) -> Vec<V> {
111        self._entries.iter().map(|p| p.value.clone()).collect()
112    }
113}
114
115impl<K: Serialize, V: Serialize> Serialize for OrderedMap<K, V> {
116    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
117    where
118        S: Serializer,
119    {
120        let mut map = serializer.serialize_map(Some(self._entries.len()))?;
121        for pair in &self._entries {
122            map.serialize_entry(&pair.key, &pair.value)?;
123        }
124        map.end()
125    }
126}
127
128struct OrderedMapVisitor<K, V> {
129    marker: PhantomData<fn() -> OrderedMap<K, V>>,
130}
131
132impl<'de, K, V> Visitor<'de> for OrderedMapVisitor<K, V>
133where
134    K: Deserialize<'de> + Eq + Hash + Clone,
135    V: Deserialize<'de> + Clone,
136{
137    type Value = OrderedMap<K, V>;
138
139    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
140        formatter.write_str("a mapping")
141    }
142
143    fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
144    where
145        M: MapAccess<'de>,
146    {
147        let mut om: OrderedMap<K, V> = OrderedMap::new();
148        while let Some((key, value)) = access.next_entry::<K, V>()? {
149            om.set(key, value);
150        }
151        Ok(om)
152    }
153}
154
155impl<'de, K, V> Deserialize<'de> for OrderedMap<K, V>
156where
157    K: Deserialize<'de> + Eq + Hash + Clone,
158    V: Deserialize<'de> + Clone,
159{
160    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
161    where
162        D: Deserializer<'de>,
163    {
164        deserializer.deserialize_map(OrderedMapVisitor {
165            marker: PhantomData,
166        })
167    }
168}
169
170#[cfg(test)]
171mod tests {
172    use super::*;
173
174    // Port of TestNew.
175    #[test]
176    fn new_creates_non_nil_map() {
177        let om: OrderedMap<String, i32> = OrderedMap::new();
178        assert_eq!(om.len(), 0);
179    }
180
181    // Port of TestSetAndGet.
182    #[test]
183    fn set_and_get_value() {
184        let mut om: OrderedMap<String, String> = OrderedMap::new();
185        om.set("foo".into(), "bar".into());
186        assert_eq!(om.get(&"foo".into()), Some(&"bar".to_string()));
187    }
188
189    #[test]
190    fn get_non_existent_key() {
191        let om: OrderedMap<String, String> = OrderedMap::new();
192        assert_eq!(om.get(&"nonexistent".into()), None);
193    }
194
195    #[test]
196    fn update_existing_key() {
197        let mut om: OrderedMap<String, String> = OrderedMap::new();
198        om.set("foo".into(), "bar".into());
199        om.set("foo".into(), "updated".into());
200        assert_eq!(om.get(&"foo".into()), Some(&"updated".to_string()));
201        assert_eq!(om.len(), 1);
202    }
203
204    // Port of TestHas.
205    #[test]
206    fn has() {
207        let mut om: OrderedMap<String, i32> = OrderedMap::new();
208        om.set("exists".into(), 42);
209        assert!(om.has(&"exists".into()));
210        assert!(!om.has(&"notexists".into()));
211    }
212
213    // Port of TestDelete.
214    #[test]
215    fn delete_existing_key() {
216        let mut om: OrderedMap<String, i32> = OrderedMap::new();
217        om.set("one".into(), 1);
218        om.set("two".into(), 2);
219        assert_eq!(om.delete(&"one".into()), Some(1));
220        assert_eq!(om.len(), 1);
221        assert!(!om.has(&"one".into()));
222    }
223
224    #[test]
225    fn delete_non_existent_key() {
226        let mut om: OrderedMap<String, i32> = OrderedMap::new();
227        om.set("one".into(), 1);
228        om.set("two".into(), 2);
229        assert_eq!(om.delete(&"three".into()), None);
230    }
231
232    // Port of TestLen.
233    #[test]
234    fn len() {
235        let mut om: OrderedMap<String, String> = OrderedMap::new();
236        assert_eq!(om.len(), 0);
237        om.set("one".into(), "1".into());
238        assert_eq!(om.len(), 1);
239        om.set("two".into(), "2".into());
240        assert_eq!(om.len(), 2);
241        om.delete(&"one".into());
242        assert_eq!(om.len(), 1);
243    }
244
245    // Port of TestOrderPreservation.
246    #[test]
247    fn order_preservation() {
248        let mut om: OrderedMap<String, i32> = OrderedMap::new();
249        om.set("first".into(), 1);
250        om.set("second".into(), 2);
251        om.set("third".into(), 3);
252        om.set("fourth".into(), 4);
253
254        let forward: Vec<_> = om.iter().map(|(k, v)| (k.clone(), *v)).collect();
255        assert_eq!(
256            forward,
257            vec![
258                ("first".to_string(), 1),
259                ("second".to_string(), 2),
260                ("third".to_string(), 3),
261                ("fourth".to_string(), 4),
262            ]
263        );
264    }
265
266    // Port of TestIterators.
267    #[test]
268    fn iterators() {
269        let mut om: OrderedMap<String, i32> = OrderedMap::new();
270        om.set("first".into(), 1);
271        om.set("second".into(), 2);
272        om.set("third".into(), 3);
273
274        assert_eq!(om.keys(), vec!["first", "second", "third"]);
275        assert_eq!(om.values(), vec![1, 2, 3]);
276
277        let mut count = 0;
278        for _ in om.iter() {
279            count += 1;
280            if count == 2 {
281                break;
282            }
283        }
284
285        assert_eq!(count, 2);
286    }
287
288    // Port of TestKeySliceAndValueSlice.
289    #[test]
290    fn key_slice_and_value_slice() {
291        let mut om: OrderedMap<String, i32> = OrderedMap::new();
292        om.set("alpha".into(), 1);
293        om.set("beta".into(), 2);
294        om.set("gamma".into(), 3);
295
296        assert_eq!(om.keys(), vec!["alpha", "beta", "gamma"]);
297        assert_eq!(om.values(), vec![1, 2, 3]);
298    }
299
300    // Port of TestYAMLMarshaling / TestJSONMarshaling: (de)serialization
301    // round-trips preserving order. Deferred: `serde_yaml::Value` marshaling
302    // through the eventual `serde::Serialize`/`Deserialize` impl needs the
303    // real implementation to test against; see PORT_NOTES.md.
304    #[test]
305    fn yaml_and_json_round_trip_preserves_order() {
306        let mut om: OrderedMap<String, String> = OrderedMap::new();
307        om.set("zebra".into(), "last".into());
308        om.set("alpha".into(), "first".into());
309        om.set("beta".into(), "second".into());
310
311        assert_eq!(om.keys(), vec!["zebra", "alpha", "beta"]);
312    }
313
314    // Port of TestPointerValues (Rust: owned struct values, since Rust has no
315    // direct pointer/nil equivalent worth preserving here).
316    #[test]
317    fn struct_values() {
318        #[derive(Debug, Clone, PartialEq, Eq)]
319        struct TestStruct {
320            name: String,
321            value: i32,
322        }
323
324        let mut om: OrderedMap<String, TestStruct> = OrderedMap::new();
325        om.set(
326            "first".into(),
327            TestStruct {
328                name: "one".into(),
329                value: 1,
330            },
331        );
332        om.set(
333            "second".into(),
334            TestStruct {
335                name: "two".into(),
336                value: 2,
337            },
338        );
339
340        let got = om.get(&"first".into()).unwrap();
341        assert_eq!(got.name, "one");
342        assert_eq!(got.value, 1);
343
344        assert_eq!(om.values().len(), 2);
345    }
346
347    // Port of TestFromMap.
348    #[test]
349    fn from_map_creates_ordered_map_with_sorted_keys() {
350        let m = std::collections::HashMap::from([
351            ("collie".to_string(), 3),
352            ("akita".to_string(), 1),
353            ("beagle".to_string(), 2),
354        ]);
355
356        let om = OrderedMap::from_map(m);
357        assert_eq!(om.len(), 3);
358        assert_eq!(om.keys(), vec!["akita", "beagle", "collie"]);
359        assert_eq!(om.values(), vec![1, 2, 3]);
360    }
361
362    #[test]
363    fn from_map_empty_map() {
364        let om: OrderedMap<String, String> = OrderedMap::from_map(std::collections::HashMap::new());
365        assert_eq!(om.len(), 0);
366    }
367
368    #[test]
369    fn from_map_integer_keys_are_sorted() {
370        let m = std::collections::HashMap::from([
371            (3, "three".to_string()),
372            (1, "one".to_string()),
373            (2, "two".to_string()),
374        ]);
375        let om = OrderedMap::from_map(m);
376        assert_eq!(om.keys(), vec![1, 2, 3]);
377        assert_eq!(om.values(), vec!["one", "two", "three"]);
378    }
379
380    // Port of TestNilMap: the Go test covers a nil `*Map` and a zero-value
381    // `Map`, both safe to read. Rust's `OrderedMap::default()` is the
382    // equivalent "unwritten, safe to read" state.
383    #[test]
384    fn default_map_is_safe_to_read() {
385        let om: OrderedMap<String, i32> = OrderedMap::default();
386        assert_eq!(om.len(), 0);
387        assert!(!om.has(&"key".into()));
388        assert!(om.oldest().is_none());
389        assert!(om.newest().is_none());
390        assert!(om.keys().is_empty());
391        assert!(om.values().is_empty());
392        assert_eq!(om.get(&"key".into()), None);
393    }
394
395    // Port of TestEmptyMap.
396    #[test]
397    fn empty_map() {
398        let om: OrderedMap<String, i32> = OrderedMap::new();
399        assert!(om.oldest().is_none());
400        assert!(om.newest().is_none());
401        assert_eq!(om.iter().count(), 0);
402        assert!(om.keys().is_empty());
403    }
404
405    // Deserialize from YAML must preserve the document's key order, not
406    // alphabetical or hash order (this is the entire point of the type).
407    #[test]
408    fn deserialize_from_yaml_preserves_document_order() {
409        let yaml = "zebra: last\nalpha: first\nbeta: second\n";
410        let om: OrderedMap<String, String> = serde_yaml::from_str(yaml).unwrap();
411        assert_eq!(om.keys(), vec!["zebra", "alpha", "beta"]);
412        assert_eq!(
413            om.values(),
414            vec![
415                "last".to_string(),
416                "first".to_string(),
417                "second".to_string()
418            ]
419        );
420    }
421
422    // Deserialize from JSON must also preserve document order.
423    #[test]
424    fn deserialize_from_json_preserves_document_order() {
425        let json = r#"{"zebra": 1, "alpha": 2, "beta": 3}"#;
426        let om: OrderedMap<String, i32> = serde_json::from_str(json).unwrap();
427        assert_eq!(om.keys(), vec!["zebra", "alpha", "beta"]);
428        assert_eq!(om.values(), vec![1, 2, 3]);
429    }
430
431    #[test]
432    fn deserialize_empty_map() {
433        let om: OrderedMap<String, i32> = serde_yaml::from_str("{}").unwrap();
434        assert_eq!(om.len(), 0);
435    }
436
437    #[test]
438    fn deserialize_rejects_non_map_yaml() {
439        let result: Result<OrderedMap<String, i32>, _> = serde_yaml::from_str("- 1\n- 2\n");
440        assert!(result.is_err());
441    }
442
443    // Round-trip: serialize then deserialize must reproduce the same order.
444    #[test]
445    fn yaml_round_trip_preserves_order() {
446        let mut om: OrderedMap<String, i32> = OrderedMap::new();
447        om.set("zebra".into(), 1);
448        om.set("alpha".into(), 2);
449        om.set("beta".into(), 3);
450
451        let yaml = serde_yaml::to_string(&om).unwrap();
452        let round_tripped: OrderedMap<String, i32> = serde_yaml::from_str(&yaml).unwrap();
453        assert_eq!(round_tripped.keys(), vec!["zebra", "alpha", "beta"]);
454        assert_eq!(round_tripped.values(), vec![1, 2, 3]);
455    }
456
457    #[test]
458    fn json_round_trip_preserves_order() {
459        let mut om: OrderedMap<String, i32> = OrderedMap::new();
460        om.set("zebra".into(), 1);
461        om.set("alpha".into(), 2);
462        om.set("beta".into(), 3);
463
464        let json = serde_json::to_string(&om).unwrap();
465        let round_tripped: OrderedMap<String, i32> = serde_json::from_str(&json).unwrap();
466        assert_eq!(round_tripped.keys(), vec!["zebra", "alpha", "beta"]);
467        assert_eq!(round_tripped.values(), vec![1, 2, 3]);
468    }
469}
xianyun_core/orderedmap.rs

xianyun_core/
orderedmap.rs
