Skip to main content

relate_core/value/
props.rs

1//! Fitted property map. A `BTreeMap` leaf reserves eleven key/value slots,
2//! so a two-property node keeps about 800 bytes of empty capacity. Create
3//! scratch retains one map per new node for the whole statement, and that
4//! slack dominated the create token-to-RSS ratio. This map stores the
5//! occupied entries in sorted order and fits the buffer to the next power
6//! of two, the same reservation the workspace meter charges.
7
8use std::collections::BTreeMap;
9use std::sync::Arc;
10
11use serde::de::Deserializer;
12use serde::ser::{SerializeMap, Serializer};
13use serde::{Deserialize, Serialize};
14
15use super::Value;
16
17/// Sorted `(key, value)` entries with capacity fitted to
18/// [`reserved_slot_count`].
19#[derive(Clone, Debug, PartialEq, Default)]
20pub struct PropertyMap {
21    entries: Vec<(String, Value)>,
22}
23
24impl PropertyMap {
25    pub fn new() -> Self {
26        Self {
27            entries: Vec::new(),
28        }
29    }
30
31    pub fn len(&self) -> usize {
32        self.entries.len()
33    }
34
35    pub fn is_empty(&self) -> bool {
36        self.entries.is_empty()
37    }
38
39    /// Buffer slots actually reserved. Empty maps reserve nothing.
40    pub fn slot_capacity(&self) -> usize {
41        self.entries.capacity()
42    }
43
44    pub fn get(&self, key: &str) -> Option<&Value> {
45        self.index_of(key).map(|i| &self.entries[i].1)
46    }
47
48    pub fn contains_key(&self, key: &str) -> bool {
49        self.index_of(key).is_some()
50    }
51
52    pub fn iter(&self) -> impl Iterator<Item = (&String, &Value)> {
53        self.entries.iter().map(|(key, value)| (key, value))
54    }
55
56    /// The sorted entries as a slice — the ADR-0462 depth walk's child
57    /// enumeration needs a nameable iterator type, so it borrows the storage
58    /// rather than the opaque [`PropertyMap::iter`] adapter.
59    pub(crate) fn entries(&self) -> &[(String, Value)] {
60        &self.entries
61    }
62
63    pub fn keys(&self) -> impl Iterator<Item = &String> {
64        self.entries.iter().map(|(key, _)| key)
65    }
66
67    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut Value> {
68        self.entries.iter_mut().map(|(_, value)| value)
69    }
70
71    pub fn insert(&mut self, key: String, value: Value) -> Option<Value> {
72        match self.index_of(&key) {
73            Some(i) => Some(std::mem::replace(&mut self.entries[i].1, value)),
74            None => {
75                let i = self
76                    .entries
77                    .partition_point(|(have, _)| have.as_str() < key.as_str());
78                self.entries.insert(i, (key, value));
79                fit_entries(&mut self.entries);
80                None
81            }
82        }
83    }
84
85    pub fn remove(&mut self, key: &str) -> Option<Value> {
86        let i = self.index_of(key)?;
87        let (_, value) = self.entries.remove(i);
88        fit_entries(&mut self.entries);
89        Some(value)
90    }
91
92    fn index_of(&self, key: &str) -> Option<usize> {
93        self.entries
94            .binary_search_by(|(have, _)| have.as_str().cmp(key))
95            .ok()
96    }
97}
98
99impl From<PropertyMap> for BTreeMap<String, Value> {
100    fn from(map: PropertyMap) -> Self {
101        map.entries.into_iter().collect()
102    }
103}
104
105impl PartialEq<BTreeMap<String, Value>> for PropertyMap {
106    fn eq(&self, other: &BTreeMap<String, Value>) -> bool {
107        self.len() == other.len()
108            && self
109                .iter()
110                .all(|(key, value)| other.get(key) == Some(value))
111    }
112}
113
114impl std::ops::Index<&str> for PropertyMap {
115    type Output = Value;
116
117    fn index(&self, key: &str) -> &Self::Output {
118        self.get(key)
119            .unwrap_or_else(|| panic!("missing property {key}"))
120    }
121}
122
123impl From<BTreeMap<String, Value>> for PropertyMap {
124    fn from(map: BTreeMap<String, Value>) -> Self {
125        let mut entries: Vec<(String, Value)> = map.into_iter().collect();
126        fit_entries(&mut entries);
127        Self { entries }
128    }
129}
130
131/// `Arc` is a fundamental type, so `From<BTreeMap> for Arc<PropertyMap>`
132/// is an orphan impl. Callers wrap with [`PropertyMap::share`].
133impl PropertyMap {
134    pub fn share(map: impl Into<PropertyMap>) -> Arc<Self> {
135        Arc::new(map.into())
136    }
137}
138
139impl<'a> IntoIterator for &'a PropertyMap {
140    type Item = (&'a String, &'a Value);
141    type IntoIter = std::iter::Map<
142        std::slice::Iter<'a, (String, Value)>,
143        fn(&'a (String, Value)) -> (&'a String, &'a Value),
144    >;
145
146    fn into_iter(self) -> Self::IntoIter {
147        self.entries.iter().map(|(key, value)| (key, value))
148    }
149}
150
151impl Serialize for PropertyMap {
152    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
153        let mut map = serializer.serialize_map(Some(self.entries.len()))?;
154        for (key, value) in &self.entries {
155            map.serialize_entry(key, value)?;
156        }
157        map.end()
158    }
159}
160
161impl<'de> Deserialize<'de> for PropertyMap {
162    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
163        Ok(PropertyMap::from(BTreeMap::<String, Value>::deserialize(
164            deserializer,
165        )?))
166    }
167}
168
169/// `0` for an empty map, otherwise the next power of two. Matches the
170/// workspace meter's vector reservation.
171pub fn reserved_slot_count(len: usize) -> usize {
172    if len == 0 {
173        0
174    } else {
175        len.next_power_of_two()
176    }
177}
178
179fn fit_entries(entries: &mut Vec<(String, Value)>) {
180    let want = reserved_slot_count(entries.len());
181    if entries.capacity() == want {
182        return;
183    }
184    let mut fitted = Vec::with_capacity(want);
185    fitted.append(entries);
186    if fitted.capacity() > want {
187        fitted.shrink_to(want);
188    }
189    *entries = fitted;
190}
191
192#[cfg(test)]
193mod tests {
194    use super::*;
195
196    #[test]
197    fn two_entries_reserve_two_slots() {
198        let map = PropertyMap::from(BTreeMap::from([
199            ("payload".to_string(), Value::Int(1)),
200            ("id".to_string(), Value::Int(2)),
201        ]));
202        assert_eq!(map.len(), 2);
203        assert_eq!(map.slot_capacity(), 2);
204        assert_eq!(map.get("id"), Some(&Value::Int(2)));
205        assert_eq!(map.get("payload"), Some(&Value::Int(1)));
206        let keys: Vec<_> = map.keys().map(String::as_str).collect();
207        assert_eq!(keys, ["id", "payload"]);
208    }
209
210    #[test]
211    fn growing_past_two_slots_fits_to_four() {
212        let mut map = PropertyMap::from(BTreeMap::from([
213            ("a".to_string(), Value::Int(1)),
214            ("b".to_string(), Value::Int(2)),
215        ]));
216        map.insert("c".into(), Value::Int(3));
217        assert_eq!(map.slot_capacity(), 4);
218        assert_eq!(map.remove("b"), Some(Value::Int(2)));
219        assert_eq!(map.slot_capacity(), 2);
220    }
221}