doge_runtime/
ordered_map.rs

1//! The backing store for `Value::Dict`: a string→`Value` map that remembers the
2//! order keys were first inserted. Doge dicts are insertion-ordered (like
3//! Python's), so iteration, printing, and `keys()`/`values()`/`items()` are all
4//! deterministic.
5//!
6//! It is a `Vec<(String, Value)>` with linear-scan lookups. Script-sized dicts
7//! are small, so the simplicity is worth more than the asymptotics an ordered
8//! hash map would buy; if dicts ever grow large this is the one place to revisit.
9
10use crate::value::Value;
11
12/// An insertion-ordered string→`Value` map.
13#[derive(Debug, Default)]
14pub struct OrderedMap {
15    entries: Vec<(String, Value)>,
16}
17
18impl OrderedMap {
19    /// An empty map.
20    pub fn new() -> Self {
21        OrderedMap {
22            entries: Vec::new(),
23        }
24    }
25
26    /// The number of entries.
27    pub fn len(&self) -> usize {
28        self.entries.len()
29    }
30
31    /// Whether the map has no entries.
32    pub fn is_empty(&self) -> bool {
33        self.entries.is_empty()
34    }
35
36    /// The value for `key`, if present.
37    pub fn get(&self, key: &str) -> Option<&Value> {
38        self.entries.iter().find(|(k, _)| k == key).map(|(_, v)| v)
39    }
40
41    /// Whether `key` is present.
42    pub fn contains_key(&self, key: &str) -> bool {
43        self.entries.iter().any(|(k, _)| k == key)
44    }
45
46    /// Insert or update. A new key is appended; an existing key keeps its
47    /// original position and only its value is replaced (Python semantics).
48    pub fn insert(&mut self, key: String, value: Value) {
49        if let Some((_, slot)) = self.entries.iter_mut().find(|(k, _)| *k == key) {
50            *slot = value;
51        } else {
52            self.entries.push((key, value));
53        }
54    }
55
56    /// Remove `key`, returning its value if it was present. The remaining
57    /// entries keep their relative order.
58    pub fn remove(&mut self, key: &str) -> Option<Value> {
59        let pos = self.entries.iter().position(|(k, _)| k == key)?;
60        Some(self.entries.remove(pos).1)
61    }
62
63    /// Drop every entry.
64    pub fn clear(&mut self) {
65        self.entries.clear();
66    }
67
68    /// Iterate entries in insertion order.
69    pub fn iter(&self) -> impl Iterator<Item = &(String, Value)> {
70        self.entries.iter()
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn insertion_order_is_preserved() {
80        let mut m = OrderedMap::new();
81        m.insert("b".to_string(), Value::Int(1));
82        m.insert("a".to_string(), Value::Int(2));
83        m.insert("c".to_string(), Value::Int(3));
84        let keys: Vec<&str> = m.iter().map(|(k, _)| k.as_str()).collect();
85        assert_eq!(keys, ["b", "a", "c"]);
86    }
87
88    #[test]
89    fn reinsert_keeps_position_but_updates_value() {
90        let mut m = OrderedMap::new();
91        m.insert("x".to_string(), Value::Int(1));
92        m.insert("y".to_string(), Value::Int(2));
93        m.insert("x".to_string(), Value::Int(9));
94        assert_eq!(m.len(), 2);
95        let entries: Vec<(&str, i64)> = m
96            .iter()
97            .map(|(k, v)| match v {
98                Value::Int(n) => (k.as_str(), *n),
99                _ => panic!("expected an Int"),
100            })
101            .collect();
102        assert_eq!(entries, [("x", 9), ("y", 2)]);
103    }
104
105    #[test]
106    fn remove_preserves_remaining_order() {
107        let mut m = OrderedMap::new();
108        m.insert("a".to_string(), Value::Int(1));
109        m.insert("b".to_string(), Value::Int(2));
110        m.insert("c".to_string(), Value::Int(3));
111        assert!(matches!(m.remove("b"), Some(Value::Int(2))));
112        assert!(m.remove("z").is_none());
113        let keys: Vec<&str> = m.iter().map(|(k, _)| k.as_str()).collect();
114        assert_eq!(keys, ["a", "c"]);
115    }
116
117    #[test]
118    fn get_and_contains_and_clear() {
119        let mut m = OrderedMap::new();
120        m.insert("k".to_string(), Value::str("v"));
121        assert!(m.contains_key("k"));
122        assert!(matches!(m.get("k"), Some(Value::Str(s)) if &**s == "v"));
123        assert!(m.get("nope").is_none());
124        m.clear();
125        assert!(m.is_empty());
126    }
127}
doge_runtime/ordered_map.rs

doge_runtime/
ordered_map.rs
