1use 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
22pub const SYS: &str = "sys";
24pub const ENV: &str = "env";
26pub const CONVERSATION: &str = "conversation";
28
29#[derive(Clone, PartialEq, Eq, Hash)]
31pub struct Selector {
32 parts: Arc<[Arc<str>]>,
33}
34
35#[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 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 pub fn parse(dotted: &str) -> Result<Self, InvalidSelector> {
56 Self::new(dotted.split('.'))
57 }
58
59 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 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 pub fn root(&self) -> Selector {
83 Selector::of(self.namespace(), self.name())
84 }
85
86 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 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#[derive(Clone, Copy)]
140struct NamespaceHasher(u64);
141
142fn 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 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}
187type Shard = Option<Arc<ShardMap>>;
189
190const SHARDS: usize = 32;
195
196#[derive(Clone, Default)]
203struct Table {
204 shards: Option<Arc<[Shard; SHARDS]>>,
205 shard_capacity: usize,
207}
208
209fn 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 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 #[allow(clippy::indexing_slicing)] 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 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 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
267fn 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#[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 pub(crate) fn with_namespace_capacity(namespaces: usize) -> Self {
305 let shard_capacity = (namespaces + namespaces / 4) / SHARDS;
307 Self { namespaces: Table { shards: None, shard_capacity } }
308 }
309
310 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 pub fn get_or_null(&self, selector: &Selector) -> Value {
318 self.get(selector).unwrap_or(Value::Null)
319 }
320
321 pub fn set(&mut self, selector: &Selector, value: Value) {
324 self.insert(selector.namespace(), selector.name(), value);
325 }
326
327 pub fn insert(&mut self, namespace: &str, name: &str, value: Value) {
329 self.namespaces.entry(namespace).insert_str(name, value);
330 }
331
332 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 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 pub fn remove_namespace(&mut self, namespace: &str) {
357 self.namespaces.remove(namespace);
358 }
359
360 pub fn set_outputs(&mut self, namespace: &str, outputs: &Variables) {
363 store_outputs(self.namespaces.entry(namespace), outputs);
364 }
365
366 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 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 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 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 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 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#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
429#[serde(transparent)]
430pub struct PoolSnapshot(pub IndexMap<String, IndexMap<String, Value>>);
431
432#[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
440fn 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 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 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 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}