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 map per namespace behind an
6//! `Arc`, and the namespace table itself is shared too: cloning a pool (for a
7//! node context, an iteration item or a loop round) is O(1), and writes copy
8//! only the touched namespace (plus the table, when it is shared).
9
10use std::collections::HashMap;
11use std::fmt;
12use std::sync::Arc;
13
14use indexmap::IndexMap;
15use serde::{Deserialize, Deserializer, Serialize, Serializer};
16
17use crate::value::{Value, ValueType};
18
19/// System variables (`sys.query`, `sys.files`, `sys.run_id`, ...). Written by the host only.
20pub const SYS: &str = "sys";
21/// Environment variables / secrets. Supplied by the host, never persisted in snapshots.
22pub const ENV: &str = "env";
23/// Conversation-scoped variables. Persisted by the host between runs.
24pub const CONVERSATION: &str = "conversation";
25
26/// Address of a value: `[namespace, name, path...]`.
27#[derive(Clone, PartialEq, Eq, Hash)]
28pub struct Selector {
29    parts: Arc<[Arc<str>]>,
30}
31
32/// Error for malformed selectors.
33#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
34#[error("invalid selector `{0}`: needs at least a namespace and a name")]
35pub struct InvalidSelector(pub String);
36
37impl Selector {
38    /// Build from parts. Requires at least two non-empty parts.
39    pub fn new<I, S>(parts: I) -> Result<Self, InvalidSelector>
40    where
41        I: IntoIterator<Item = S>,
42        S: AsRef<str>,
43    {
44        let parts: Vec<Arc<str>> = parts.into_iter().map(|p| Arc::from(p.as_ref())).collect();
45        if parts.len() < 2 || parts.iter().any(|p| p.is_empty()) {
46            return Err(InvalidSelector(parts.join(".")));
47        }
48        Ok(Self { parts: parts.into() })
49    }
50
51    /// Parse a dotted selector such as `llm.text` or `start.user.name`.
52    pub fn parse(dotted: &str) -> Result<Self, InvalidSelector> {
53        Self::new(dotted.split('.'))
54    }
55
56    /// Two-part selector `namespace.name`.
57    pub fn of(namespace: &str, name: &str) -> Self {
58        Self { parts: vec![Arc::from(namespace), Arc::from(name)].into() }
59    }
60
61    pub fn namespace(&self) -> &str {
62        self.parts.first().map(AsRef::as_ref).unwrap_or_default()
63    }
64
65    pub fn name(&self) -> &str {
66        self.parts.get(1).map(AsRef::as_ref).unwrap_or_default()
67    }
68
69    /// Path below the variable (`a.b.c` -> `[c]`).
70    pub fn path(&self) -> &[Arc<str>] {
71        self.parts.get(2..).unwrap_or_default()
72    }
73
74    pub fn parts(&self) -> &[Arc<str>] {
75        &self.parts
76    }
77
78    /// The `namespace.name` prefix of this selector.
79    pub fn root(&self) -> Selector {
80        Selector::of(self.namespace(), self.name())
81    }
82
83    /// Append path parts.
84    pub fn child(&self, part: &str) -> Selector {
85        let mut parts: Vec<Arc<str>> = self.parts.to_vec();
86        parts.push(Arc::from(part));
87        Selector { parts: parts.into() }
88    }
89}
90
91impl fmt::Display for Selector {
92    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
93        f.write_str(&self.parts.join("."))
94    }
95}
96
97impl fmt::Debug for Selector {
98    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99        write!(f, "Selector({self})")
100    }
101}
102
103impl Serialize for Selector {
104    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
105        self.parts.iter().map(AsRef::as_ref).collect::<Vec<&str>>().serialize(serializer)
106    }
107}
108
109impl<'de> Deserialize<'de> for Selector {
110    /// Accepts `["node", "var"]` or `"node.var"`.
111    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
112        #[derive(Deserialize)]
113        #[serde(untagged)]
114        enum Repr {
115            List(Vec<String>),
116            Dotted(String),
117        }
118        let sel = match Repr::deserialize(deserializer)? {
119            Repr::List(parts) => Selector::new(parts),
120            Repr::Dotted(s) => Selector::parse(&s),
121        };
122        sel.map_err(serde::de::Error::custom)
123    }
124}
125
126type Namespace = Arc<IndexMap<Arc<str>, Value>>;
127type ShardMap = HashMap<Arc<str>, Namespace>;
128/// `None` until a namespace hashing to the shard is written.
129type Shard = Option<Arc<ShardMap>>;
130
131/// Number of shards in the namespace table. Every node owns a namespace, so a
132/// large graph has many; sharding keeps a copy-on-write update proportional to
133/// one shard instead of the whole table while snapshots are shared with
134/// running nodes.
135const SHARDS: usize = 32;
136
137/// Namespace table split into [`SHARDS`] independently shared maps. Cloning is
138/// O(1); an update copies at most the shard array (`SHARDS` pointers) and one shard.
139///
140/// Shards and the shard array are allocated on first write: an empty table
141/// costs no allocation, where eagerly creating every shard cost 33 per pool
142/// and a pool is created for every execution frame.
143#[derive(Clone, Default)]
144struct Table {
145    shards: Option<Arc<[Shard; SHARDS]>>,
146}
147
148/// Shard index of a namespace (FNV-1a: stable and fast for short ids).
149fn shard_of(namespace: &str) -> usize {
150    let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
151    for byte in namespace.bytes() {
152        hash ^= u64::from(byte);
153        hash = hash.wrapping_mul(0x0100_0000_01b3);
154    }
155    // The remainder is below SHARDS, so the conversion cannot fail.
156    usize::try_from(hash % SHARDS as u64).unwrap_or(0)
157}
158
159impl Table {
160    fn shard(&self, namespace: &str) -> Option<&ShardMap> {
161        self.shards.as_ref()?.get(shard_of(namespace))?.as_deref()
162    }
163
164    /// Mutable shard holding `namespace`, allocating or copying shared structure as needed.
165    #[allow(clippy::indexing_slicing)] // shard_of() < SHARDS by construction
166    fn shard_mut(&mut self, namespace: &str) -> &mut ShardMap {
167        let shards = Arc::make_mut(self.shards.get_or_insert_with(Default::default));
168        Arc::make_mut(shards[shard_of(namespace)].get_or_insert_with(Default::default))
169    }
170
171    fn get(&self, namespace: &str) -> Option<&Namespace> {
172        self.shard(namespace)?.get(namespace)
173    }
174
175    fn entry(&mut self, namespace: &str) -> &mut Namespace {
176        let shard = self.shard_mut(namespace);
177        // Reuse the existing key (a reference-count bump) instead of allocating
178        // a new `Arc<str>` on every write to a namespace that already exists.
179        let key = shard.get_key_value(namespace).map_or_else(|| Arc::from(namespace), |(key, _)| Arc::clone(key));
180        shard.entry(key).or_default()
181    }
182
183    /// Like [`Table::entry`], but a new namespace takes `namespace` as its key
184    /// (a reference-count bump) instead of allocating a copy.
185    fn entry_shared(&mut self, namespace: &Arc<str>) -> &mut Namespace {
186        let shard = self.shard_mut(namespace);
187        let key =
188            shard.get_key_value(namespace.as_ref()).map_or_else(|| Arc::clone(namespace), |(key, _)| Arc::clone(key));
189        shard.entry(key).or_default()
190    }
191
192    fn remove(&mut self, namespace: &str) {
193        if self.get(namespace).is_some() {
194            self.shard_mut(namespace).remove(namespace);
195        }
196    }
197
198    fn iter(&self) -> impl Iterator<Item = (&Arc<str>, &Namespace)> {
199        self.shards.iter().flat_map(|shards| shards.iter().flatten()).flat_map(|shard| shard.iter())
200    }
201}
202
203fn insert_outputs(namespace: &mut Namespace, outputs: &IndexMap<String, Value>) {
204    let ns = Arc::make_mut(namespace);
205    ns.reserve(outputs.len());
206    for (k, v) in outputs {
207        ns.insert(Arc::from(k.as_str()), v.clone());
208    }
209}
210
211/// Variable storage for one execution frame.
212#[derive(Clone, Default)]
213pub struct VariablePool {
214    namespaces: Table,
215}
216
217impl fmt::Debug for VariablePool {
218    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
219        let mut map = f.debug_map();
220        for (ns, vars) in self.namespaces.iter() {
221            map.entry(ns, vars);
222        }
223        map.finish()
224    }
225}
226
227impl VariablePool {
228    pub fn new() -> Self {
229        Self::default()
230    }
231
232    /// Resolve a selector, descending into nested values. Missing values return `None`.
233    pub fn get(&self, selector: &Selector) -> Option<Value> {
234        let root = self.namespaces.get(selector.namespace())?.get(selector.name())?;
235        if selector.path().is_empty() { Some(root.clone()) } else { root.get_path(selector.path()) }
236    }
237
238    /// Resolve a selector, returning [`Value::Null`] when absent.
239    pub fn get_or_null(&self, selector: &Selector) -> Value {
240        self.get(selector).unwrap_or(Value::Null)
241    }
242
243    /// Set `namespace.name`. Any path in the selector is ignored; use [`VariablePool::set_path`]
244    /// for nested writes.
245    pub fn set(&mut self, selector: &Selector, value: Value) {
246        self.insert(selector.namespace(), selector.name(), value);
247    }
248
249    /// Set a variable by namespace and name.
250    pub fn insert(&mut self, namespace: &str, name: &str, value: Value) {
251        Arc::make_mut(self.namespaces.entry(namespace)).insert(Arc::from(name), value);
252    }
253
254    /// Write into a nested path, creating intermediate objects as needed.
255    /// Array elements are addressed by index; writing past the end of an array
256    /// is an error (nothing is written).
257    pub fn set_path(&mut self, selector: &Selector, value: Value) -> Result<(), PathError> {
258        if selector.path().is_empty() {
259            self.set(selector, value);
260            return Ok(());
261        }
262        let current = self.get(&selector.root()).unwrap_or(Value::Null);
263        let updated = write_path(current, selector.path(), value)
264            .map_err(|index| PathError { selector: selector.to_string(), index })?;
265        self.set(selector, updated);
266        Ok(())
267    }
268
269    /// Remove one variable.
270    pub fn remove(&mut self, selector: &Selector) -> Option<Value> {
271        if !self.namespaces.get(selector.namespace())?.contains_key(selector.name()) {
272            return None;
273        }
274        Arc::make_mut(self.namespaces.entry(selector.namespace())).shift_remove(selector.name())
275    }
276
277    /// Drop a whole namespace (e.g. a node's outputs before a loop round re-runs it).
278    pub fn remove_namespace(&mut self, namespace: &str) {
279        self.namespaces.remove(namespace);
280    }
281
282    /// Bulk-insert a node's outputs.
283    pub fn set_outputs(&mut self, namespace: &str, outputs: &IndexMap<String, Value>) {
284        insert_outputs(self.namespaces.entry(namespace), outputs);
285    }
286
287    /// [`VariablePool::set_outputs`] for a namespace the caller already holds as
288    /// an `Arc<str>` (the engine's node ids), which avoids copying the name.
289    pub(crate) fn set_outputs_shared(&mut self, namespace: &Arc<str>, outputs: &IndexMap<String, Value>) {
290        insert_outputs(self.namespaces.entry_shared(namespace), outputs);
291    }
292
293    /// All variables in a namespace.
294    pub fn namespace(&self, namespace: &str) -> Option<&IndexMap<Arc<str>, Value>> {
295        self.namespaces.get(namespace).map(AsRef::as_ref)
296    }
297
298    pub fn contains(&self, selector: &Selector) -> bool {
299        self.get(selector).is_some()
300    }
301
302    /// Iterate `(namespace, name, value)`.
303    pub fn iter(&self) -> impl Iterator<Item = (&str, &str, &Value)> {
304        self.namespaces.iter().flat_map(|(ns, vars)| vars.iter().map(move |(k, v)| (ns.as_ref(), k.as_ref(), v)))
305    }
306
307    /// Serializable form for snapshots. The [`ENV`] namespace is excluded: the host
308    /// must supply environment variables again on resume. Secrets in other
309    /// namespaces are stored as `{"$secret": "redacted"}` markers and restored as
310    /// redacted secrets (see [`Value::redacted_secret`]).
311    pub fn to_snapshot(&self) -> PoolSnapshot {
312        let mut out: IndexMap<String, IndexMap<String, Value>> = IndexMap::new();
313        let mut entries: Vec<(&Arc<str>, &Namespace)> = self.namespaces.iter().collect();
314        entries.sort_by(|a, b| a.0.cmp(b.0));
315        for (ns, vars) in entries {
316            if ns.as_ref() == ENV {
317                continue;
318            }
319            out.insert(ns.to_string(), vars.iter().map(|(k, v)| (k.to_string(), v.to_snapshot_value())).collect());
320        }
321        PoolSnapshot(out)
322    }
323
324    /// Restore from a snapshot (env variables must be re-applied by the caller).
325    pub fn from_snapshot(snapshot: PoolSnapshot) -> Self {
326        let mut pool = Self::new();
327        for (ns, vars) in snapshot.0 {
328            for (k, v) in vars {
329                pool.insert(&ns, &k, v.from_snapshot_value());
330            }
331        }
332        pool
333    }
334
335    /// Insert a typed declared variable, validating it against its declared type.
336    pub fn insert_typed(
337        &mut self,
338        namespace: &str,
339        name: &str,
340        ty: ValueType,
341        value: Value,
342    ) -> Result<(), crate::value::TypeMismatch> {
343        let v = ty.coerce(value)?;
344        self.insert(namespace, name, v);
345        Ok(())
346    }
347}
348
349/// Persistable variable pool contents (`namespace -> name -> value`).
350#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
351#[serde(transparent)]
352pub struct PoolSnapshot(pub IndexMap<String, IndexMap<String, Value>>);
353
354/// Error writing a nested path.
355#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
356#[error("cannot write `{selector}`: array index {index} is out of range")]
357pub struct PathError {
358    pub selector: String,
359    pub index: usize,
360}
361
362/// Returns the out-of-range index on failure.
363fn write_path(current: Value, path: &[Arc<str>], value: Value) -> Result<Value, usize> {
364    let Some((head, rest)) = path.split_first() else {
365        return Ok(value);
366    };
367    match current {
368        Value::Array(items) if head.parse::<usize>().is_ok() => {
369            let idx = head.parse::<usize>().unwrap_or(0);
370            let mut items = Arc::unwrap_or_clone(items);
371            let slot = items.get_mut(idx).ok_or(idx)?;
372            let old = std::mem::take(slot);
373            *slot = write_path(old, rest, value)?;
374            Ok(Value::Array(Arc::new(items)))
375        }
376        other => {
377            let mut map = match other {
378                Value::Object(m) => Arc::unwrap_or_clone(m),
379                _ => IndexMap::new(),
380            };
381            // Take the old value in place so the key keeps its position.
382            let old = map.get_mut(head.as_ref()).map(std::mem::take).unwrap_or(Value::Null);
383            map.insert(head.to_string(), write_path(old, rest, value)?);
384            Ok(Value::Object(Arc::new(map)))
385        }
386    }
387}
388
389#[cfg(test)]
390mod tests {
391    use super::*;
392
393    fn sel(s: &str) -> Selector {
394        Selector::parse(s).unwrap_or_else(|_| Selector::of("bad", "bad"))
395    }
396
397    #[test]
398    fn selector_parsing() {
399        assert!(Selector::parse("a").is_err());
400        assert!(Selector::parse("a..b").is_err());
401        let s = sel("n.v.x.y");
402        assert_eq!(s.namespace(), "n");
403        assert_eq!(s.name(), "v");
404        assert_eq!(s.path().len(), 2);
405        let from_list: Result<Selector, _> = serde_json::from_str("[\"n\",\"v\"]");
406        let from_str: Result<Selector, _> = serde_json::from_str("\"n.v\"");
407        assert_eq!(from_list.ok(), from_str.ok());
408    }
409
410    #[test]
411    fn clone_is_copy_on_write() {
412        let mut a = VariablePool::new();
413        a.insert("n", "x", Value::Int(1));
414        let mut b = a.clone();
415        b.insert("n", "x", Value::Int(2));
416        assert_eq!(a.get(&sel("n.x")), Some(Value::Int(1)));
417        assert_eq!(b.get(&sel("n.x")), Some(Value::Int(2)));
418    }
419
420    #[test]
421    fn nested_get_and_set() {
422        let mut p = VariablePool::new();
423        p.set_path(&sel("n.obj.a.b"), Value::from("deep")).unwrap();
424        p.insert("n", "list", Value::from_json(serde_json::json!([1, 2])));
425        p.set_path(&sel("n.list.1"), Value::Int(9)).unwrap();
426        assert_eq!(p.get(&sel("n.list")), Some(Value::from_json(serde_json::json!([1, 9]))));
427        assert!(p.set_path(&sel("n.list.5"), Value::Int(9)).is_err());
428        assert_eq!(p.get(&sel("n.obj.a.b")), Some(Value::from("deep")));
429        assert_eq!(p.get(&sel("n.obj.missing")), None);
430    }
431
432    #[test]
433    fn snapshot_excludes_env() {
434        let mut p = VariablePool::new();
435        p.insert(ENV, "KEY", Value::Secret(Arc::from("s3cret")));
436        p.insert("n", "x", Value::Int(1));
437        let snap = p.to_snapshot();
438        let json = serde_json::to_string(&snap).unwrap_or_default();
439        assert!(!json.contains("s3cret"));
440        assert!(!json.contains("env"));
441        let restored = VariablePool::from_snapshot(snap);
442        assert_eq!(restored.get(&sel("n.x")), Some(Value::Int(1)));
443    }
444}