Skip to main content

graphrt_core/
pool.rs

1//! Selectors and the variable pool.
2//!
3//! A [`Selector`] addresses a value as `namespace.name[.path...]`, where the
4//! namespace is a node id or one of the reserved namespaces ([`SYS`], [`ENV`],
5//! [`CONVERSATION`]). The [`VariablePool`] stores one [`Variables`] map per
6//! namespace (shared on clone), and the namespace table itself is shared too:
7//! cloning a pool (for a node context, an iteration item or a loop round) is
8//! O(1), and writes copy only the touched namespace (plus the table, when it is
9//! shared). A node's outputs become its namespace without being copied.
10
11use std::collections::HashMap;
12use std::fmt;
13use std::hash::{BuildHasher, BuildHasherDefault, Hasher};
14use std::sync::{Arc, OnceLock};
15
16use indexmap::IndexMap;
17use serde::{Deserialize, Deserializer, Serialize, Serializer};
18
19use crate::value::{Value, ValueType};
20use crate::variables::Variables;
21
22/// System variables (`sys.query`, `sys.files`, `sys.run_id`, ...). Written by the host only.
23pub const SYS: &str = "sys";
24/// Environment variables / secrets. Supplied by the host, never persisted in snapshots.
25pub const ENV: &str = "env";
26/// Conversation-scoped variables. Persisted by the host between runs.
27pub const CONVERSATION: &str = "conversation";
28
29/// Address of a value: `[namespace, name, path...]`.
30#[derive(Clone, PartialEq, Eq, Hash)]
31pub struct Selector {
32    parts: Arc<[Arc<str>]>,
33}
34
35/// Error for malformed selectors.
36#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
37#[error("invalid selector `{0}`: needs at least a namespace and a name")]
38pub struct InvalidSelector(pub String);
39
40impl Selector {
41    /// Build from parts. Requires at least two non-empty parts.
42    pub fn new<I, S>(parts: I) -> Result<Self, InvalidSelector>
43    where
44        I: IntoIterator<Item = S>,
45        S: AsRef<str>,
46    {
47        let parts: Vec<Arc<str>> = parts.into_iter().map(|p| Arc::from(p.as_ref())).collect();
48        if parts.len() < 2 || parts.iter().any(|p| p.is_empty()) {
49            return Err(InvalidSelector(parts.join(".")));
50        }
51        Ok(Self { parts: parts.into() })
52    }
53
54    /// Parse a dotted selector such as `llm.text` or `start.user.name`.
55    pub fn parse(dotted: &str) -> Result<Self, InvalidSelector> {
56        Self::new(dotted.split('.'))
57    }
58
59    /// Two-part selector `namespace.name`.
60    pub fn of(namespace: &str, name: &str) -> Self {
61        Self { parts: vec![Arc::from(namespace), Arc::from(name)].into() }
62    }
63
64    pub fn namespace(&self) -> &str {
65        self.parts.first().map(AsRef::as_ref).unwrap_or_default()
66    }
67
68    pub fn name(&self) -> &str {
69        self.parts.get(1).map(AsRef::as_ref).unwrap_or_default()
70    }
71
72    /// Path below the variable (`a.b.c` -> `[c]`).
73    pub fn path(&self) -> &[Arc<str>] {
74        self.parts.get(2..).unwrap_or_default()
75    }
76
77    pub fn parts(&self) -> &[Arc<str>] {
78        &self.parts
79    }
80
81    /// The `namespace.name` prefix of this selector.
82    pub fn root(&self) -> Selector {
83        Selector::of(self.namespace(), self.name())
84    }
85
86    /// Append path parts.
87    pub fn child(&self, part: &str) -> Selector {
88        let mut parts: Vec<Arc<str>> = self.parts.to_vec();
89        parts.push(Arc::from(part));
90        Selector { parts: parts.into() }
91    }
92}
93
94impl fmt::Display for Selector {
95    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
96        f.write_str(&self.parts.join("."))
97    }
98}
99
100impl fmt::Debug for Selector {
101    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
102        write!(f, "Selector({self})")
103    }
104}
105
106impl Serialize for Selector {
107    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
108        self.parts.iter().map(AsRef::as_ref).collect::<Vec<&str>>().serialize(serializer)
109    }
110}
111
112impl<'de> Deserialize<'de> for Selector {
113    /// Accepts `["node", "var"]` or `"node.var"`.
114    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
115        #[derive(Deserialize)]
116        #[serde(untagged)]
117        enum Repr {
118            List(Vec<String>),
119            Dotted(String),
120        }
121        let sel = match Repr::deserialize(deserializer)? {
122            Repr::List(parts) => Selector::new(parts),
123            Repr::Dotted(s) => Selector::parse(&s),
124        };
125        sel.map_err(serde::de::Error::custom)
126    }
127}
128
129type Namespace = Variables;
130type ShardMap = HashMap<Arc<str>, Namespace, BuildHasherDefault<NamespaceHasher>>;
131
132/// Hasher for namespace names in the shard maps.
133///
134/// Every node commit looks its namespace up, and SipHash (the std default) was
135/// a visible share of the engine's per-node cost. Names are short ids from the
136/// workflow document or the host, so a word-at-a-time multiplicative hash
137/// (FxHash-style) suffices; it is keyed per process so collisions cannot be
138/// precomputed.
139#[derive(Clone, Copy)]
140struct NamespaceHasher(u64);
141
142/// Per-process key of [`NamespaceHasher`].
143fn namespace_hash_seed() -> u64 {
144    static SEED: OnceLock<u64> = OnceLock::new();
145    *SEED.get_or_init(|| std::collections::hash_map::RandomState::new().build_hasher().finish())
146}
147
148impl Default for NamespaceHasher {
149    fn default() -> Self {
150        Self(namespace_hash_seed())
151    }
152}
153
154impl NamespaceHasher {
155    fn add(&mut self, word: u64) {
156        self.0 = (self.0.rotate_left(5) ^ word).wrapping_mul(0x517c_c1b7_2722_0a95);
157    }
158}
159
160impl Hasher for NamespaceHasher {
161    fn finish(&self) -> u64 {
162        // The multiply leaves the low bits (the table's bucket index) weakest.
163        self.0.rotate_left(26)
164    }
165
166    fn write(&mut self, bytes: &[u8]) {
167        let mut chunks = bytes.chunks_exact(8);
168        for chunk in &mut chunks {
169            let mut word = [0u8; 8];
170            word.copy_from_slice(chunk);
171            self.add(u64::from_le_bytes(word));
172        }
173        let rest = chunks.remainder();
174        if !rest.is_empty() {
175            let mut word = [0u8; 8];
176            if let Some(head) = word.get_mut(..rest.len()) {
177                head.copy_from_slice(rest);
178            }
179            self.add(u64::from_le_bytes(word));
180        }
181    }
182
183    fn write_u8(&mut self, byte: u8) {
184        self.add(u64::from(byte));
185    }
186}
187/// `None` until a namespace hashing to the shard is written.
188type Shard = Option<Arc<ShardMap>>;
189
190/// Number of shards in the namespace table. Every node owns a namespace, so a
191/// large graph has many; sharding keeps a copy-on-write update proportional to
192/// one shard instead of the whole table while snapshots are shared with
193/// running nodes.
194const SHARDS: usize = 32;
195
196/// Namespace table split into [`SHARDS`] independently shared maps. Cloning is
197/// O(1); an update copies at most the shard array (`SHARDS` pointers) and one shard.
198///
199/// Shards and the shard array are allocated on first write: an empty table
200/// costs no allocation, where eagerly creating every shard cost 33 per pool
201/// and a pool is created for every execution frame.
202#[derive(Clone, Default)]
203struct Table {
204    shards: Option<Arc<[Shard; SHARDS]>>,
205    /// Initial capacity of a shard map when it is created.
206    shard_capacity: usize,
207}
208
209/// Shard index of a namespace (FNV-1a: stable and fast for short ids).
210fn shard_of(namespace: &str) -> usize {
211    let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
212    for byte in namespace.bytes() {
213        hash ^= u64::from(byte);
214        hash = hash.wrapping_mul(0x0100_0000_01b3);
215    }
216    // The remainder is below SHARDS, so the conversion cannot fail.
217    usize::try_from(hash % SHARDS as u64).unwrap_or(0)
218}
219
220impl Table {
221    fn shard(&self, namespace: &str) -> Option<&ShardMap> {
222        self.shards.as_ref()?.get(shard_of(namespace))?.as_deref()
223    }
224
225    /// Mutable shard holding `namespace`, allocating or copying shared structure as needed.
226    #[allow(clippy::indexing_slicing)] // shard_of() < SHARDS by construction
227    fn shard_mut(&mut self, namespace: &str) -> &mut ShardMap {
228        let capacity = self.shard_capacity;
229        let shards = Arc::make_mut(self.shards.get_or_insert_with(Default::default));
230        let shard = shards[shard_of(namespace)]
231            .get_or_insert_with(|| Arc::new(HashMap::with_capacity_and_hasher(capacity, Default::default())));
232        Arc::make_mut(shard)
233    }
234
235    fn get(&self, namespace: &str) -> Option<&Namespace> {
236        self.shard(namespace)?.get(namespace)
237    }
238
239    fn entry(&mut self, namespace: &str) -> &mut Namespace {
240        let shard = self.shard_mut(namespace);
241        // Reuse the existing key (a reference-count bump) instead of allocating
242        // a new `Arc<str>` on every write to a namespace that already exists.
243        let key = shard.get_key_value(namespace).map_or_else(|| Arc::from(namespace), |(key, _)| Arc::clone(key));
244        shard.entry(key).or_default()
245    }
246
247    /// Like [`Table::entry`], but a new namespace takes `namespace` as its key
248    /// (a reference-count bump) instead of allocating a copy.
249    fn entry_shared(&mut self, namespace: &Arc<str>) -> &mut Namespace {
250        let shard = self.shard_mut(namespace);
251        let key =
252            shard.get_key_value(namespace.as_ref()).map_or_else(|| Arc::clone(namespace), |(key, _)| Arc::clone(key));
253        shard.entry(key).or_default()
254    }
255
256    fn remove(&mut self, namespace: &str) {
257        if self.get(namespace).is_some() {
258            self.shard_mut(namespace).remove(namespace);
259        }
260    }
261
262    fn iter(&self) -> impl Iterator<Item = (&Arc<str>, &Namespace)> {
263        self.shards.iter().flat_map(|shards| shards.iter().flatten()).flat_map(|shard| shard.iter())
264    }
265}
266
267/// Store a node's outputs in its namespace. An empty namespace (the usual
268/// case: a node's first commit) takes the outputs map itself, a reference-count
269/// bump; otherwise the outputs are merged in.
270fn store_outputs(namespace: &mut Namespace, outputs: &Variables) {
271    if namespace.is_empty() {
272        namespace.clone_from(outputs);
273        return;
274    }
275    namespace.reserve(outputs.len());
276    for (name, value) in outputs.named_entries() {
277        namespace.insert(name.clone(), value.clone());
278    }
279}
280
281/// Variable storage for one execution frame.
282#[derive(Clone, Default)]
283pub struct VariablePool {
284    namespaces: Table,
285}
286
287impl fmt::Debug for VariablePool {
288    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
289        let mut map = f.debug_map();
290        for (ns, vars) in self.namespaces.iter() {
291            map.entry(ns, vars);
292        }
293        map.finish()
294    }
295}
296
297impl VariablePool {
298    pub fn new() -> Self {
299        Self::default()
300    }
301
302    /// An empty pool sized for about `namespaces` namespaces (the engine passes
303    /// the graph's node count), so filling it does not keep regrowing its maps.
304    pub(crate) fn with_namespace_capacity(namespaces: usize) -> Self {
305        // Shards fill unevenly; a quarter of headroom avoids most regrowth.
306        let shard_capacity = (namespaces + namespaces / 4) / SHARDS;
307        Self { namespaces: Table { shards: None, shard_capacity } }
308    }
309
310    /// Resolve a selector, descending into nested values. Missing values return `None`.
311    pub fn get(&self, selector: &Selector) -> Option<Value> {
312        let root = self.namespaces.get(selector.namespace())?.get(selector.name())?;
313        if selector.path().is_empty() { Some(root.clone()) } else { root.get_path(selector.path()) }
314    }
315
316    /// Resolve a selector, returning [`Value::Null`] when absent.
317    pub fn get_or_null(&self, selector: &Selector) -> Value {
318        self.get(selector).unwrap_or(Value::Null)
319    }
320
321    /// Set `namespace.name`. Any path in the selector is ignored; use [`VariablePool::set_path`]
322    /// for nested writes.
323    pub fn set(&mut self, selector: &Selector, value: Value) {
324        self.insert(selector.namespace(), selector.name(), value);
325    }
326
327    /// Set a variable by namespace and name.
328    pub fn insert(&mut self, namespace: &str, name: &str, value: Value) {
329        self.namespaces.entry(namespace).insert_str(name, value);
330    }
331
332    /// Write into a nested path, creating intermediate objects as needed.
333    /// Array elements are addressed by index; writing past the end of an array
334    /// is an error (nothing is written).
335    pub fn set_path(&mut self, selector: &Selector, value: Value) -> Result<(), PathError> {
336        if selector.path().is_empty() {
337            self.set(selector, value);
338            return Ok(());
339        }
340        let current = self.get(&selector.root()).unwrap_or(Value::Null);
341        let updated = write_path(current, selector.path(), value)
342            .map_err(|index| PathError { selector: selector.to_string(), index })?;
343        self.set(selector, updated);
344        Ok(())
345    }
346
347    /// Remove one variable.
348    pub fn remove(&mut self, selector: &Selector) -> Option<Value> {
349        if !self.namespaces.get(selector.namespace())?.contains_key(selector.name()) {
350            return None;
351        }
352        self.namespaces.entry(selector.namespace()).remove(selector.name())
353    }
354
355    /// Drop a whole namespace (e.g. a node's outputs before a loop round re-runs it).
356    pub fn remove_namespace(&mut self, namespace: &str) {
357        self.namespaces.remove(namespace);
358    }
359
360    /// Bulk-insert a node's outputs. Into an empty namespace this shares
361    /// `outputs` instead of copying it.
362    pub fn set_outputs(&mut self, namespace: &str, outputs: &Variables) {
363        store_outputs(self.namespaces.entry(namespace), outputs);
364    }
365
366    /// [`VariablePool::set_outputs`] for a namespace the caller already holds as
367    /// an `Arc<str>` (the engine's node ids), which avoids copying the name.
368    pub(crate) fn set_outputs_shared(&mut self, namespace: &Arc<str>, outputs: &Variables) {
369        store_outputs(self.namespaces.entry_shared(namespace), outputs);
370    }
371
372    /// All variables in a namespace.
373    pub fn namespace(&self, namespace: &str) -> Option<&Variables> {
374        self.namespaces.get(namespace)
375    }
376
377    pub fn contains(&self, selector: &Selector) -> bool {
378        self.get(selector).is_some()
379    }
380
381    /// Iterate `(namespace, name, value)`.
382    pub fn iter(&self) -> impl Iterator<Item = (&str, &str, &Value)> {
383        self.namespaces.iter().flat_map(|(ns, vars)| vars.iter().map(move |(k, v)| (ns.as_ref(), k, v)))
384    }
385
386    /// Serializable form for snapshots. The [`ENV`] namespace is excluded: the host
387    /// must supply environment variables again on resume. Secrets in other
388    /// namespaces are stored as `{"$secret": "redacted"}` markers and restored as
389    /// redacted secrets (see [`Value::redacted_secret`]).
390    pub fn to_snapshot(&self) -> PoolSnapshot {
391        let mut out: IndexMap<String, IndexMap<String, Value>> = IndexMap::new();
392        let mut entries: Vec<(&Arc<str>, &Namespace)> = self.namespaces.iter().collect();
393        entries.sort_by(|a, b| a.0.cmp(b.0));
394        for (ns, vars) in entries {
395            if ns.as_ref() == ENV {
396                continue;
397            }
398            out.insert(ns.to_string(), vars.iter().map(|(k, v)| (k.to_string(), v.to_snapshot_value())).collect());
399        }
400        PoolSnapshot(out)
401    }
402
403    /// Restore from a snapshot (env variables must be re-applied by the caller).
404    pub fn from_snapshot(snapshot: PoolSnapshot) -> Self {
405        let mut pool = Self::new();
406        for (ns, vars) in snapshot.0 {
407            let restored: Variables = vars.into_iter().map(|(k, v)| (k, v.from_snapshot_value())).collect();
408            store_outputs(pool.namespaces.entry(&ns), &restored);
409        }
410        pool
411    }
412
413    /// Insert a typed declared variable, validating it against its declared type.
414    pub fn insert_typed(
415        &mut self,
416        namespace: &str,
417        name: &str,
418        ty: ValueType,
419        value: Value,
420    ) -> Result<(), crate::value::TypeMismatch> {
421        let v = ty.coerce(value)?;
422        self.insert(namespace, name, v);
423        Ok(())
424    }
425}
426
427/// Persistable variable pool contents (`namespace -> name -> value`).
428#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
429#[serde(transparent)]
430pub struct PoolSnapshot(pub IndexMap<String, IndexMap<String, Value>>);
431
432/// Error writing a nested path.
433#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
434#[error("cannot write `{selector}`: array index {index} is out of range")]
435pub struct PathError {
436    pub selector: String,
437    pub index: usize,
438}
439
440/// Returns the out-of-range index on failure.
441fn write_path(current: Value, path: &[Arc<str>], value: Value) -> Result<Value, usize> {
442    let Some((head, rest)) = path.split_first() else {
443        return Ok(value);
444    };
445    match current {
446        Value::Array(items) if head.parse::<usize>().is_ok() => {
447            let idx = head.parse::<usize>().unwrap_or(0);
448            let mut items = Arc::unwrap_or_clone(items);
449            let slot = items.get_mut(idx).ok_or(idx)?;
450            let old = std::mem::take(slot);
451            *slot = write_path(old, rest, value)?;
452            Ok(Value::Array(Arc::new(items)))
453        }
454        other => {
455            let mut map = match other {
456                Value::Object(m) => Arc::unwrap_or_clone(m),
457                _ => IndexMap::new(),
458            };
459            // Take the old value in place so the key keeps its position.
460            let old = map.get_mut(head.as_ref()).map(std::mem::take).unwrap_or(Value::Null);
461            map.insert(head.to_string(), write_path(old, rest, value)?);
462            Ok(Value::Object(Arc::new(map)))
463        }
464    }
465}
466
467#[cfg(test)]
468mod tests {
469    use super::*;
470
471    fn sel(s: &str) -> Selector {
472        Selector::parse(s).unwrap_or_else(|_| Selector::of("bad", "bad"))
473    }
474
475    #[test]
476    fn selector_parsing() {
477        assert!(Selector::parse("a").is_err());
478        assert!(Selector::parse("a..b").is_err());
479        let s = sel("n.v.x.y");
480        assert_eq!(s.namespace(), "n");
481        assert_eq!(s.name(), "v");
482        assert_eq!(s.path().len(), 2);
483        let from_list: Result<Selector, _> = serde_json::from_str("[\"n\",\"v\"]");
484        let from_str: Result<Selector, _> = serde_json::from_str("\"n.v\"");
485        assert_eq!(from_list.ok(), from_str.ok());
486    }
487
488    #[test]
489    fn namespace_hasher_separates_similar_ids() {
490        let hash = |s: &str| BuildHasherDefault::<NamespaceHasher>::default().hash_one(s);
491        assert_eq!(hash("node_12"), hash("node_12"));
492        let ids: std::collections::HashSet<u64> = (0..10_000).map(|i| hash(&format!("n{i}"))).collect();
493        assert_eq!(ids.len(), 10_000);
494        // Ids differing only past the first 8-byte word, or by a trailing byte.
495        assert_ne!(hash("longer_node_id_a"), hash("longer_node_id_b"));
496        assert_ne!(hash("abcdefgh"), hash("abcdefgh\0"));
497    }
498
499    #[test]
500    fn outputs_become_the_namespace_without_a_copy() {
501        let outputs = Variables::from([("text", Value::from("hi"))]);
502        let mut p = VariablePool::new();
503        p.set_outputs("llm", &outputs);
504        assert!(p.namespace("llm").is_some_and(|ns| ns.ptr_eq(&outputs)));
505        // A namespace that already holds variables merges instead.
506        p.insert("loop", "i", Value::Int(1));
507        p.set_outputs("loop", &outputs);
508        let merged = p.namespace("loop").map(|ns| ns.keys().collect::<Vec<_>>());
509        assert_eq!(merged, Some(vec!["i", "text"]));
510        assert_eq!(outputs.len(), 1, "the caller's map is not modified");
511    }
512
513    #[test]
514    fn presized_pool_behaves_like_a_new_one() {
515        let mut p = VariablePool::with_namespace_capacity(1_000);
516        p.insert("n", "x", Value::Int(1));
517        let mut q = p.clone();
518        q.insert("n", "x", Value::Int(2));
519        assert_eq!(p.get(&sel("n.x")), Some(Value::Int(1)));
520        assert_eq!(q.get(&sel("n.x")), Some(Value::Int(2)));
521        assert!(VariablePool::with_namespace_capacity(0).get(&sel("n.x")).is_none());
522    }
523
524    #[test]
525    fn many_namespaces_stay_addressable() {
526        let mut p = VariablePool::new();
527        for i in 0..2_000 {
528            p.insert(&format!("node{i}"), "v", Value::Int(i));
529        }
530        for i in 0..2_000 {
531            assert_eq!(p.get(&sel(&format!("node{i}.v"))), Some(Value::Int(i)));
532        }
533    }
534
535    #[test]
536    fn clone_is_copy_on_write() {
537        let mut a = VariablePool::new();
538        a.insert("n", "x", Value::Int(1));
539        let mut b = a.clone();
540        b.insert("n", "x", Value::Int(2));
541        assert_eq!(a.get(&sel("n.x")), Some(Value::Int(1)));
542        assert_eq!(b.get(&sel("n.x")), Some(Value::Int(2)));
543    }
544
545    #[test]
546    fn nested_get_and_set() {
547        let mut p = VariablePool::new();
548        p.set_path(&sel("n.obj.a.b"), Value::from("deep")).unwrap();
549        p.insert("n", "list", Value::from_json(serde_json::json!([1, 2])));
550        p.set_path(&sel("n.list.1"), Value::Int(9)).unwrap();
551        assert_eq!(p.get(&sel("n.list")), Some(Value::from_json(serde_json::json!([1, 9]))));
552        assert!(p.set_path(&sel("n.list.5"), Value::Int(9)).is_err());
553        assert_eq!(p.get(&sel("n.obj.a.b")), Some(Value::from("deep")));
554        assert_eq!(p.get(&sel("n.obj.missing")), None);
555    }
556
557    #[test]
558    fn snapshot_excludes_env() {
559        let mut p = VariablePool::new();
560        p.insert(ENV, "KEY", Value::Secret(Arc::from("s3cret")));
561        p.insert("n", "x", Value::Int(1));
562        let snap = p.to_snapshot();
563        let json = serde_json::to_string(&snap).unwrap_or_default();
564        assert!(!json.contains("s3cret"));
565        assert!(!json.contains("env"));
566        let restored = VariablePool::from_snapshot(snap);
567        assert_eq!(restored.get(&sel("n.x")), Some(Value::Int(1)));
568    }
569}