Skip to main content

graphrt_core/
variables.rs

1//! [`Variables`]: the small ordered map of named values a node produces and a
2//! pool namespace holds.
3//!
4//! A node's outputs become its namespace in the variable pool and travel in its
5//! [`Event::NodeSucceeded`](crate::event::Event::NodeSucceeded) unchanged:
6//! `Variables` is a reference-counted handle, so storing the outputs, emitting
7//! them and taking pool snapshots share one allocation instead of copying the
8//! map. Writes copy the entries only while they are shared (copy-on-write).
9//!
10//! Nodes produce a handful of variables, so entries are kept in insertion order
11//! in a flat vector (the first few stored inline in the shared allocation) and
12//! looked up by a linear scan, which beats hashing at these sizes. Names are
13//! [`VarName`]s, which hold a `&'static str` without allocating.
14
15use std::borrow::Borrow;
16use std::collections::HashMap;
17use std::fmt;
18use std::hash::{Hash, Hasher};
19use std::ops::{Deref, Index};
20use std::sync::Arc;
21
22use indexmap::IndexMap;
23use serde::{Deserialize, Deserializer, Serialize, Serializer};
24use smallvec::SmallVec;
25
26use crate::value::Value;
27
28/// Name of a variable in a [`Variables`] map.
29///
30/// Built from a string literal it costs no allocation (`"text".into()`); other
31/// names are stored as a shared `Arc<str>`. Compares, hashes and orders as the
32/// string it holds.
33#[derive(Clone)]
34pub struct VarName(NameRepr);
35
36#[derive(Clone)]
37enum NameRepr {
38    Static(&'static str),
39    Shared(Arc<str>),
40}
41
42impl VarName {
43    /// A name from a string literal, usable in `const` contexts.
44    pub const fn from_static(name: &'static str) -> Self {
45        Self(NameRepr::Static(name))
46    }
47
48    pub fn as_str(&self) -> &str {
49        match &self.0 {
50            NameRepr::Static(name) => name,
51            NameRepr::Shared(name) => name,
52        }
53    }
54}
55
56impl Deref for VarName {
57    type Target = str;
58
59    fn deref(&self) -> &str {
60        self.as_str()
61    }
62}
63
64impl AsRef<str> for VarName {
65    fn as_ref(&self) -> &str {
66        self.as_str()
67    }
68}
69
70impl Borrow<str> for VarName {
71    fn borrow(&self) -> &str {
72        self.as_str()
73    }
74}
75
76impl PartialEq for VarName {
77    fn eq(&self, other: &Self) -> bool {
78        self.as_str() == other.as_str()
79    }
80}
81
82impl Eq for VarName {}
83
84impl PartialEq<str> for VarName {
85    fn eq(&self, other: &str) -> bool {
86        self.as_str() == other
87    }
88}
89
90impl PartialEq<&str> for VarName {
91    fn eq(&self, other: &&str) -> bool {
92        self.as_str() == *other
93    }
94}
95
96impl Hash for VarName {
97    fn hash<H: Hasher>(&self, state: &mut H) {
98        self.as_str().hash(state);
99    }
100}
101
102impl PartialOrd for VarName {
103    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
104        Some(self.cmp(other))
105    }
106}
107
108impl Ord for VarName {
109    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
110        self.as_str().cmp(other.as_str())
111    }
112}
113
114impl fmt::Display for VarName {
115    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
116        f.write_str(self.as_str())
117    }
118}
119
120impl fmt::Debug for VarName {
121    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
122        fmt::Debug::fmt(self.as_str(), f)
123    }
124}
125
126impl From<&'static str> for VarName {
127    fn from(name: &'static str) -> Self {
128        Self::from_static(name)
129    }
130}
131
132impl From<String> for VarName {
133    fn from(name: String) -> Self {
134        Self(NameRepr::Shared(Arc::from(name)))
135    }
136}
137
138impl From<&String> for VarName {
139    fn from(name: &String) -> Self {
140        Self(NameRepr::Shared(Arc::from(name.as_str())))
141    }
142}
143
144impl From<Box<str>> for VarName {
145    fn from(name: Box<str>) -> Self {
146        Self(NameRepr::Shared(Arc::from(name)))
147    }
148}
149
150impl From<Arc<str>> for VarName {
151    fn from(name: Arc<str>) -> Self {
152        Self(NameRepr::Shared(name))
153    }
154}
155
156impl From<&Arc<str>> for VarName {
157    fn from(name: &Arc<str>) -> Self {
158        Self(NameRepr::Shared(Arc::clone(name)))
159    }
160}
161
162impl From<VarName> for String {
163    fn from(name: VarName) -> Self {
164        name.as_str().to_owned()
165    }
166}
167
168impl From<VarName> for Arc<str> {
169    fn from(name: VarName) -> Self {
170        match name.0 {
171            NameRepr::Static(name) => Arc::from(name),
172            NameRepr::Shared(name) => name,
173        }
174    }
175}
176
177impl Serialize for VarName {
178    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
179        serializer.serialize_str(self.as_str())
180    }
181}
182
183impl<'de> Deserialize<'de> for VarName {
184    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
185        String::deserialize(deserializer).map(Self::from)
186    }
187}
188
189/// Entries stored inline in the shared allocation before spilling to the heap.
190/// Most nodes produce at most this many outputs.
191const INLINE_ENTRIES: usize = 4;
192
193/// Above this many entries, bulk inserts deduplicate names through a hash
194/// index instead of a scan per entry.
195const LINEAR_DEDUP_LIMIT: usize = 32;
196
197type Entries = SmallVec<[(VarName, Value); INLINE_ENTRIES]>;
198
199/// Ordered map of variable names to values, shared on clone.
200///
201/// Iteration follows insertion order; inserting an existing name replaces its
202/// value in place. Cloning is a reference-count bump and an empty map holds no
203/// allocation. Lookups scan the entries, so the map suits the handful of
204/// variables a node produces, not large dictionaries (use a
205/// [`Value::Object`] for those).
206///
207/// ```
208/// use graphrt_core::variables::Variables;
209/// use graphrt_core::Value;
210///
211/// let mut outputs = Variables::new();
212/// outputs.insert("text", Value::from("hi"));
213/// let shared = outputs.clone(); // no copy
214/// assert_eq!(shared.get("text"), Some(&Value::from("hi")));
215/// assert_eq!(outputs["missing"], Value::Null);
216/// ```
217#[derive(Clone, Default)]
218pub struct Variables {
219    entries: Option<Arc<Entries>>,
220}
221
222/// Returned by indexing a [`Variables`] with a missing name.
223static NULL: Value = Value::Null;
224
225impl Variables {
226    pub const fn new() -> Self {
227        Self { entries: None }
228    }
229
230    fn entries(&self) -> &[(VarName, Value)] {
231        self.entries.as_deref().map_or(&[], |entries| entries.as_slice())
232    }
233
234    /// Entries for writing: allocated on first use, copied if shared.
235    fn entries_mut(&mut self) -> &mut Entries {
236        Arc::make_mut(self.entries.get_or_insert_with(Default::default))
237    }
238
239    fn position(&self, name: &str) -> Option<usize> {
240        self.entries().iter().position(|(key, _)| key.as_str() == name)
241    }
242
243    pub fn len(&self) -> usize {
244        self.entries().len()
245    }
246
247    pub fn is_empty(&self) -> bool {
248        self.entries().is_empty()
249    }
250
251    pub fn get(&self, name: &str) -> Option<&Value> {
252        self.entries().iter().find(|(key, _)| key.as_str() == name).map(|(_, value)| value)
253    }
254
255    pub fn get_key_value(&self, name: &str) -> Option<(&VarName, &Value)> {
256        self.entries().iter().find(|(key, _)| key.as_str() == name).map(|(key, value)| (key, value))
257    }
258
259    /// Mutable access to a value (copies the entries first if they are shared).
260    pub fn get_mut(&mut self, name: &str) -> Option<&mut Value> {
261        let position = self.position(name)?;
262        self.entries_mut().get_mut(position).map(|(_, value)| value)
263    }
264
265    pub fn contains_key(&self, name: &str) -> bool {
266        self.position(name).is_some()
267    }
268
269    /// Insert or replace. A replaced value keeps its position and is returned.
270    pub fn insert(&mut self, name: impl Into<VarName>, value: Value) -> Option<Value> {
271        let name = name.into();
272        if let Some(slot) = self.get_mut(&name) {
273            return Some(std::mem::replace(slot, value));
274        }
275        self.entries_mut().push((name, value));
276        None
277    }
278
279    /// [`Variables::insert`] for a borrowed name: the name is only copied when
280    /// it is new, so overwriting an existing variable allocates nothing.
281    pub fn insert_str(&mut self, name: &str, value: Value) -> Option<Value> {
282        if let Some(slot) = self.get_mut(name) {
283            return Some(std::mem::replace(slot, value));
284        }
285        self.entries_mut().push((VarName::from(Arc::<str>::from(name)), value));
286        None
287    }
288
289    /// Remove a variable, keeping the order of the others.
290    pub fn remove(&mut self, name: &str) -> Option<Value> {
291        let position = self.position(name)?;
292        let entries = self.entries_mut();
293        (position < entries.len()).then(|| entries.remove(position).1)
294    }
295
296    /// Reserve room for `additional` more entries.
297    pub fn reserve(&mut self, additional: usize) {
298        if additional > 0 {
299            self.entries_mut().reserve(additional);
300        }
301    }
302
303    /// `(name, value)` pairs in insertion order.
304    pub fn iter(&self) -> Iter<'_> {
305        Iter { entries: self.entries().iter() }
306    }
307
308    pub fn keys(&self) -> impl DoubleEndedIterator<Item = &str> + ExactSizeIterator + '_ {
309        self.entries().iter().map(|(key, _)| key.as_str())
310    }
311
312    /// Entries with their [`VarName`]s (cloning a name never copies its text).
313    pub(crate) fn named_entries(&self) -> impl Iterator<Item = (&VarName, &Value)> + '_ {
314        self.entries().iter().map(|(name, value)| (name, value))
315    }
316
317    pub fn values(&self) -> impl DoubleEndedIterator<Item = &Value> + ExactSizeIterator + '_ {
318        self.entries().iter().map(|(_, value)| value)
319    }
320
321    /// Whether both maps share the same storage (a clone of one another, unchanged since).
322    pub fn ptr_eq(&self, other: &Self) -> bool {
323        match (&self.entries, &other.entries) {
324            (Some(a), Some(b)) => Arc::ptr_eq(a, b),
325            (None, None) => true,
326            _ => false,
327        }
328    }
329
330    /// Copy into an `IndexMap` with owned names.
331    pub fn to_index_map(&self) -> IndexMap<String, Value> {
332        self.iter().map(|(name, value)| (name.to_owned(), value.clone())).collect()
333    }
334}
335
336impl fmt::Debug for Variables {
337    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
338        f.debug_map().entries(self.iter()).finish()
339    }
340}
341
342/// Map equality: the same names with equal values, in any order.
343impl PartialEq for Variables {
344    fn eq(&self, other: &Self) -> bool {
345        self.len() == other.len() && self.iter().all(|(name, value)| other.get(name) == Some(value))
346    }
347}
348
349/// Indexing a missing name yields [`Value::Null`] instead of panicking.
350impl Index<&str> for Variables {
351    type Output = Value;
352
353    fn index(&self, name: &str) -> &Value {
354        self.get(name).unwrap_or(&NULL)
355    }
356}
357
358impl<K: Into<VarName>> Extend<(K, Value)> for Variables {
359    fn extend<I: IntoIterator<Item = (K, Value)>>(&mut self, iter: I) {
360        let iter = iter.into_iter();
361        if self.len().saturating_add(iter.size_hint().0) <= LINEAR_DEDUP_LIMIT {
362            for (name, value) in iter {
363                self.insert(name, value);
364            }
365            return;
366        }
367        let entries = self.entries_mut();
368        let mut index: HashMap<VarName, usize> =
369            entries.iter().enumerate().map(|(position, (name, _))| (name.clone(), position)).collect();
370        for (name, value) in iter {
371            let name = name.into();
372            match index.get(name.as_str()).and_then(|&position| entries.get_mut(position)) {
373                Some(slot) => slot.1 = value,
374                None => {
375                    index.insert(name.clone(), entries.len());
376                    entries.push((name, value));
377                }
378            }
379        }
380    }
381}
382
383impl<K: Into<VarName>> FromIterator<(K, Value)> for Variables {
384    fn from_iter<I: IntoIterator<Item = (K, Value)>>(iter: I) -> Self {
385        let mut variables = Self::new();
386        variables.extend(iter);
387        variables
388    }
389}
390
391impl<K: Into<VarName>, const N: usize> From<[(K, Value); N]> for Variables {
392    fn from(entries: [(K, Value); N]) -> Self {
393        entries.into_iter().collect()
394    }
395}
396
397impl From<IndexMap<String, Value>> for Variables {
398    fn from(map: IndexMap<String, Value>) -> Self {
399        // Keys of an `IndexMap` are unique: no deduplication needed.
400        let entries: Entries = map.into_iter().map(|(name, value)| (VarName::from(name), value)).collect();
401        if entries.is_empty() { Self::new() } else { Self { entries: Some(Arc::new(entries)) } }
402    }
403}
404
405impl From<Variables> for IndexMap<String, Value> {
406    fn from(variables: Variables) -> Self {
407        variables.into_iter().map(|(name, value)| (String::from(name), value)).collect()
408    }
409}
410
411/// Borrowing iterator over a [`Variables`] map.
412#[derive(Clone, Debug)]
413pub struct Iter<'a> {
414    entries: std::slice::Iter<'a, (VarName, Value)>,
415}
416
417impl<'a> Iterator for Iter<'a> {
418    type Item = (&'a str, &'a Value);
419
420    fn next(&mut self) -> Option<Self::Item> {
421        self.entries.next().map(|(name, value)| (name.as_str(), value))
422    }
423
424    fn size_hint(&self) -> (usize, Option<usize>) {
425        self.entries.size_hint()
426    }
427}
428
429impl DoubleEndedIterator for Iter<'_> {
430    fn next_back(&mut self) -> Option<Self::Item> {
431        self.entries.next_back().map(|(name, value)| (name.as_str(), value))
432    }
433}
434
435impl ExactSizeIterator for Iter<'_> {}
436
437impl<'a> IntoIterator for &'a Variables {
438    type Item = (&'a str, &'a Value);
439    type IntoIter = Iter<'a>;
440
441    fn into_iter(self) -> Iter<'a> {
442        self.iter()
443    }
444}
445
446/// Owning iterator over a [`Variables`] map (copies the entries if shared).
447pub struct IntoIter {
448    entries: smallvec::IntoIter<[(VarName, Value); INLINE_ENTRIES]>,
449}
450
451impl fmt::Debug for IntoIter {
452    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
453        f.debug_struct("IntoIter").field("remaining", &self.entries.len()).finish()
454    }
455}
456
457impl Iterator for IntoIter {
458    type Item = (VarName, Value);
459
460    fn next(&mut self) -> Option<Self::Item> {
461        self.entries.next()
462    }
463
464    fn size_hint(&self) -> (usize, Option<usize>) {
465        self.entries.size_hint()
466    }
467}
468
469impl DoubleEndedIterator for IntoIter {
470    fn next_back(&mut self) -> Option<Self::Item> {
471        self.entries.next_back()
472    }
473}
474
475impl ExactSizeIterator for IntoIter {}
476
477impl IntoIterator for Variables {
478    type Item = (VarName, Value);
479    type IntoIter = IntoIter;
480
481    fn into_iter(self) -> IntoIter {
482        let entries = self.entries.map(Arc::unwrap_or_clone).unwrap_or_default();
483        IntoIter { entries: entries.into_iter() }
484    }
485}
486
487impl Serialize for Variables {
488    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
489        serializer.collect_map(self.iter())
490    }
491}
492
493impl<'de> Deserialize<'de> for Variables {
494    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
495        // Later duplicates replace earlier values, as with `IndexMap`.
496        IndexMap::<String, Value>::deserialize(deserializer).map(Self::from)
497    }
498}
499
500#[cfg(test)]
501mod tests {
502    use super::*;
503
504    #[test]
505    fn insert_replaces_in_place_and_keeps_order() {
506        let mut vars = Variables::new();
507        assert!(vars.is_empty());
508        assert_eq!(vars.insert("a", Value::Int(1)), None);
509        assert_eq!(vars.insert(String::from("b"), Value::Int(2)), None);
510        assert_eq!(vars.insert("a", Value::Int(3)), Some(Value::Int(1)));
511        assert_eq!(vars.keys().collect::<Vec<_>>(), ["a", "b"]);
512        assert_eq!(vars["a"], Value::Int(3));
513        assert_eq!(vars["missing"], Value::Null);
514        assert_eq!(vars.insert_str("b", Value::Int(4)), Some(Value::Int(2)));
515        assert_eq!(vars.insert_str("c", Value::Int(5)), None);
516        assert_eq!(vars.remove("a"), Some(Value::Int(3)));
517        assert_eq!(vars.remove("a"), None);
518        assert_eq!(vars.keys().collect::<Vec<_>>(), ["b", "c"]);
519    }
520
521    #[test]
522    fn clones_share_until_written() {
523        let mut a = Variables::from([("x", Value::Int(1))]);
524        let b = a.clone();
525        assert!(a.ptr_eq(&b));
526        a.insert("x", Value::Int(2));
527        assert!(!a.ptr_eq(&b));
528        assert_eq!(b["x"], Value::Int(1));
529        assert_eq!(a["x"], Value::Int(2));
530    }
531
532    #[test]
533    fn bulk_inserts_deduplicate_names() {
534        let small: Variables = [("k", Value::Int(1)), ("k", Value::Int(2))].into_iter().collect();
535        assert_eq!(small.len(), 1);
536        assert_eq!(small["k"], Value::Int(2));
537        let large: Variables = (0..100).chain(0..100).map(|i| (format!("k{i}"), Value::Int(i))).collect();
538        assert_eq!(large.len(), 100);
539        assert_eq!(large.keys().nth(42), Some("k42"));
540    }
541
542    #[test]
543    fn equality_ignores_order() {
544        let a = Variables::from([("x", Value::Int(1)), ("y", Value::Int(2))]);
545        let b = Variables::from([("y", Value::Int(2)), ("x", Value::Int(1))]);
546        assert_eq!(a, b);
547        assert_ne!(a, Variables::from([("x", Value::Int(1))]));
548    }
549
550    #[test]
551    fn serializes_as_an_ordered_map() {
552        let vars = Variables::from([("z", Value::Int(1)), ("a", Value::from("s"))]);
553        let json = serde_json::to_string(&vars).unwrap_or_default();
554        assert_eq!(json, r#"{"z":1,"a":"s"}"#);
555        let back: Variables = serde_json::from_str(&json).unwrap_or_default();
556        assert_eq!(back, vars);
557        assert_eq!(IndexMap::from(back.clone()).keys().collect::<Vec<_>>(), ["z", "a"]);
558        assert_eq!(Variables::from(vars.to_index_map()), vars);
559    }
560
561    #[test]
562    fn names_compare_as_strings() {
563        let literal = VarName::from("name");
564        let shared = VarName::from(String::from("name"));
565        assert_eq!(literal, shared);
566        assert_eq!(literal, "name");
567        assert_eq!(String::from(shared.clone()), "name");
568        assert_eq!(Arc::<str>::from(literal).as_ref(), "name");
569        assert_eq!(format!("{shared} {shared:?}"), "name \"name\"");
570    }
571}