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    use bigdecimal::ToPrimitive;
78
79    #[test]
80    fn insertion_order_is_preserved() {
81        let mut m = OrderedMap::new();
82        m.insert("b".to_string(), Value::int(1));
83        m.insert("a".to_string(), Value::int(2));
84        m.insert("c".to_string(), Value::int(3));
85        let keys: Vec<&str> = m.iter().map(|(k, _)| k.as_str()).collect();
86        assert_eq!(keys, ["b", "a", "c"]);
87    }
88
89    #[test]
90    fn reinsert_keeps_position_but_updates_value() {
91        let mut m = OrderedMap::new();
92        m.insert("x".to_string(), Value::int(1));
93        m.insert("y".to_string(), Value::int(2));
94        m.insert("x".to_string(), Value::int(9));
95        assert_eq!(m.len(), 2);
96        let entries: Vec<(&str, i64)> = m
97            .iter()
98            .map(|(k, v)| match v {
99                Value::Int(n) => (k.as_str(), n.to_i64().unwrap()),
100                _ => panic!("expected an Int"),
101            })
102            .collect();
103        assert_eq!(entries, [("x", 9), ("y", 2)]);
104    }
105
106    #[test]
107    fn remove_preserves_remaining_order() {
108        let mut m = OrderedMap::new();
109        m.insert("a".to_string(), Value::int(1));
110        m.insert("b".to_string(), Value::int(2));
111        m.insert("c".to_string(), Value::int(3));
112        assert!(m
113            .remove("b")
114            .is_some_and(|v| crate::values_equal(&v, &Value::int(2))));
115        assert!(m.remove("z").is_none());
116        let keys: Vec<&str> = m.iter().map(|(k, _)| k.as_str()).collect();
117        assert_eq!(keys, ["a", "c"]);
118    }
119
120    #[test]
121    fn get_and_contains_and_clear() {
122        let mut m = OrderedMap::new();
123        m.insert("k".to_string(), Value::str("v"));
124        assert!(m.contains_key("k"));
125        assert!(matches!(m.get("k"), Some(Value::Str(s)) if &**s == "v"));
126        assert!(m.get("nope").is_none());
127        m.clear();
128        assert!(m.is_empty());
129    }
130}
doge_runtime/ordered_map.rs

doge_runtime/
ordered_map.rs
