Skip to main content

graphrt_core/
graph.rs

1//! Compiled, validated, immutable graph.
2//!
3//! A [`Graph`] is built once from a [`Workflow`] document and shared (via
4//! `Arc`) by every run and every container frame. Runtime state (node and
5//! edge status) lives in the engine's per-frame state, never in the graph, so
6//! a graph can execute any number of runs concurrently.
7//!
8//! Each node belongs to exactly one *scope*: the root scope, or the body of a
9//! container node (iteration / loop). Edges never cross scopes, and every
10//! scope must be acyclic and have exactly one entry node.
11
12use std::collections::{HashMap, HashSet, VecDeque};
13use std::fmt;
14use std::hash::{Hash, Hasher};
15use std::sync::Arc;
16
17use crate::dsl::{NodeDoc, NodePolicy, Workflow};
18use crate::node::{ConfigError, Node, NodeRole, Registry};
19
20/// Default edge handle for non-branch nodes.
21pub const SOURCE_HANDLE: &str = "source";
22/// Handle taken when a node with the `fail-branch` strategy fails.
23pub const FAIL_BRANCH: &str = "fail-branch";
24
25/// Index of a node in [`Graph::nodes`].
26pub type NodeIx = usize;
27/// Index of an edge in [`Graph::edges`].
28pub type EdgeIx = usize;
29
30/// A compiled node.
31pub struct GraphNode {
32    pub id: Arc<str>,
33    pub kind: String,
34    pub title: String,
35    /// Owning container, `None` for the root scope.
36    pub parent: Option<NodeIx>,
37    pub policy: NodePolicy,
38    pub role: NodeRole,
39    pub node: Arc<dyn Node>,
40    /// The source document (kept for introspection and tooling).
41    pub doc: NodeDoc,
42}
43
44impl fmt::Debug for GraphNode {
45    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46        f.debug_struct("GraphNode").field("id", &self.id).field("kind", &self.kind).field("role", &self.role).finish()
47    }
48}
49
50/// A compiled edge.
51#[derive(Clone, Debug, PartialEq, Eq)]
52pub struct GraphEdge {
53    pub id: Arc<str>,
54    pub source: NodeIx,
55    pub target: NodeIx,
56    pub handle: Arc<str>,
57}
58
59/// One scope: the root graph or a container body.
60#[derive(Clone, Debug, PartialEq, Eq)]
61pub struct Scope {
62    /// Container node owning this scope, `None` for the root.
63    pub owner: Option<NodeIx>,
64    /// Entry node.
65    pub entry: NodeIx,
66    /// Nodes in this scope, in topological order.
67    pub nodes: Vec<NodeIx>,
68}
69
70/// Graph construction / validation error.
71#[derive(Debug, thiserror::Error)]
72#[non_exhaustive]
73pub enum GraphError {
74    #[error(transparent)]
75    Config(#[from] ConfigError),
76    #[error("duplicate node id `{0}`")]
77    DuplicateNode(String),
78    #[error("duplicate edge id `{0}`")]
79    DuplicateEdge(String),
80    #[error("edge `{edge}` references unknown node `{node}`")]
81    MissingNode { edge: String, node: String },
82    #[error("node `{node}` references unknown parent `{parent}`")]
83    MissingParent { node: String, parent: String },
84    #[error("node `{0}` has a parent that is not a container node")]
85    ParentNotContainer(String),
86    #[error("container nesting cycle at node `{0}`")]
87    ParentCycle(String),
88    #[error("edge `{edge}` crosses scopes (`{source_node}` -> `{target}`)")]
89    CrossScopeEdge { edge: String, source_node: String, target: String },
90    #[error("cycle detected in scope `{scope}` involving node `{node}`")]
91    Cycle { scope: String, node: String },
92    #[error("scope `{scope}` has no entry node")]
93    NoEntry { scope: String },
94    #[error("scope `{scope}` has multiple entry nodes: {nodes:?}")]
95    MultipleEntries { scope: String, nodes: Vec<String> },
96    #[error("graph has no nodes")]
97    Empty,
98    #[error("workflow cannot be serialized: {0}")]
99    Unserializable(String),
100    #[error("invalid node id `{id}`: {reason}")]
101    InvalidNodeId { id: String, reason: String },
102    #[error("node `{node}` references `{selector}`, but no node or variable namespace `{namespace}` exists")]
103    UnknownReference { node: String, selector: String, namespace: String },
104}
105
106/// Namespaces that are not node ids.
107const RESERVED_NAMESPACES: &[&str] = &[crate::pool::SYS, crate::pool::ENV, crate::pool::CONVERSATION];
108
109fn validate_node_id(id: &str) -> Result<(), GraphError> {
110    let reason = if id.is_empty() {
111        Some("must not be empty")
112    } else if RESERVED_NAMESPACES.contains(&id) {
113        Some("is a reserved variable namespace")
114    } else if id.contains('.') {
115        Some("must not contain `.` (it separates selector parts)")
116    } else if id.chars().any(char::is_whitespace) {
117        Some("must not contain whitespace")
118    } else {
119        None
120    };
121    match reason {
122        Some(reason) => Err(GraphError::InvalidNodeId { id: id.to_owned(), reason: reason.to_owned() }),
123        None => Ok(()),
124    }
125}
126
127/// An executable graph.
128pub struct Graph {
129    nodes: Vec<GraphNode>,
130    edges: Vec<GraphEdge>,
131    index: HashMap<Arc<str>, NodeIx>,
132    outgoing: Vec<Vec<EdgeIx>>,
133    incoming: Vec<Vec<EdgeIx>>,
134    scopes: HashMap<Option<NodeIx>, Scope>,
135    warnings: Vec<String>,
136    fingerprint: String,
137    workflow: Workflow,
138}
139
140impl fmt::Debug for Graph {
141    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
142        f.debug_struct("Graph")
143            .field("nodes", &self.nodes.len())
144            .field("edges", &self.edges.len())
145            .field("fingerprint", &self.fingerprint)
146            .finish()
147    }
148}
149
150impl Graph {
151    /// Build and validate a graph from a workflow document.
152    pub fn build(workflow: Workflow, registry: &Registry) -> Result<Self, GraphError> {
153        let docs = &workflow.graph.nodes;
154        if docs.is_empty() {
155            return Err(GraphError::Empty);
156        }
157
158        // Nodes.
159        let mut index: HashMap<Arc<str>, NodeIx> = HashMap::with_capacity(docs.len());
160        for (ix, doc) in docs.iter().enumerate() {
161            validate_node_id(&doc.id)?;
162            if index.insert(Arc::from(doc.id.as_str()), ix).is_some() {
163                return Err(GraphError::DuplicateNode(doc.id.clone()));
164            }
165        }
166        let mut nodes = Vec::with_capacity(docs.len());
167        for doc in docs {
168            let parent = match &doc.parent {
169                Some(p) => Some(
170                    *index
171                        .get(p.as_str())
172                        .ok_or_else(|| GraphError::MissingParent { node: doc.id.clone(), parent: p.clone() })?,
173                ),
174                None => None,
175            };
176            let node = registry.build(doc)?;
177            nodes.push(GraphNode {
178                id: Arc::from(doc.id.as_str()),
179                kind: doc.kind.clone(),
180                title: doc.label().to_owned(),
181                parent,
182                policy: doc.policy.clone(),
183                role: node.role(),
184                node,
185                doc: doc.clone(),
186            });
187        }
188
189        // Parents must be containers and nesting must be acyclic.
190        for (ix, n) in nodes.iter().enumerate() {
191            if let Some(p) = n.parent {
192                if nodes.get(p).map(|pn| pn.role) != Some(NodeRole::Container) {
193                    return Err(GraphError::ParentNotContainer(n.id.to_string()));
194                }
195            }
196            let mut seen = HashSet::new();
197            let mut cur = Some(ix);
198            while let Some(c) = cur {
199                if !seen.insert(c) {
200                    return Err(GraphError::ParentCycle(n.id.to_string()));
201                }
202                cur = nodes.get(c).and_then(|x| x.parent);
203            }
204        }
205
206        // Edges.
207        let mut edges = Vec::with_capacity(workflow.graph.edges.len());
208        let mut edge_ids = HashSet::new();
209        let mut outgoing = vec![Vec::new(); nodes.len()];
210        let mut incoming = vec![Vec::new(); nodes.len()];
211        for (i, e) in workflow.graph.edges.iter().enumerate() {
212            let id: Arc<str> = Arc::from(e.id.clone().unwrap_or_else(|| format!("{}-{}-{i}", e.source, e.target)));
213            if !edge_ids.insert(id.clone()) {
214                return Err(GraphError::DuplicateEdge(id.to_string()));
215            }
216            let lookup = |n: &str| {
217                index
218                    .get(n)
219                    .copied()
220                    .ok_or_else(|| GraphError::MissingNode { edge: id.to_string(), node: n.to_owned() })
221            };
222            let source = lookup(&e.source)?;
223            let target = lookup(&e.target)?;
224            let (sp, tp) = (nodes.get(source).and_then(|n| n.parent), nodes.get(target).and_then(|n| n.parent));
225            if sp != tp {
226                return Err(GraphError::CrossScopeEdge {
227                    edge: id.to_string(),
228                    source_node: e.source.clone(),
229                    target: e.target.clone(),
230                });
231            }
232            let ex = edges.len();
233            edges.push(GraphEdge {
234                id,
235                source,
236                target,
237                handle: Arc::from(e.handle.as_deref().filter(|h| !h.is_empty()).unwrap_or(SOURCE_HANDLE)),
238            });
239            if let Some(o) = outgoing.get_mut(source) {
240                o.push(ex);
241            }
242            if let Some(inc) = incoming.get_mut(target) {
243                inc.push(ex);
244            }
245        }
246
247        // Scopes.
248        let mut members: HashMap<Option<NodeIx>, Vec<NodeIx>> = HashMap::new();
249        for (ix, n) in nodes.iter().enumerate() {
250            members.entry(n.parent).or_default().push(ix);
251        }
252        // Containers without children still get an (invalid) scope check below.
253        for (ix, n) in nodes.iter().enumerate() {
254            if n.role == NodeRole::Container {
255                members.entry(Some(ix)).or_default();
256            }
257        }
258
259        let mut warnings = Vec::new();
260        let mut scopes = HashMap::new();
261        for (owner, scope_nodes) in members {
262            let scope_name =
263                owner.and_then(|o| nodes.get(o)).map(|n| n.id.to_string()).unwrap_or_else(|| "root".into());
264            let entry = find_entry(&nodes, &incoming, owner, &scope_nodes, &scope_name)?;
265            let order = topo_order(&scope_nodes, &outgoing, &incoming, &edges, &nodes, &scope_name)?;
266            // Reachability from the entry: unreachable nodes never run.
267            let reachable = reachable_from(entry, &outgoing, &edges);
268            for &ix in &scope_nodes {
269                if !reachable.contains(&ix) {
270                    if let Some(n) = nodes.get(ix) {
271                        warnings
272                            .push(format!("node `{}` is not reachable from the entry of scope `{scope_name}`", n.id));
273                    }
274                }
275            }
276            scopes.insert(owner, Scope { owner, entry, nodes: order });
277        }
278
279        validate_references(&nodes, &index, &mut warnings)?;
280
281        let fingerprint = fingerprint(&workflow)?;
282        Ok(Self { nodes, edges, index, outgoing, incoming, scopes, warnings, fingerprint, workflow })
283    }
284
285    /// Parse (JSON or YAML) and build in one step.
286    pub fn from_text(text: &str, registry: &Registry) -> Result<Self, crate::Error> {
287        let wf = Workflow::parse(text)?;
288        Ok(Self::build(wf, registry)?)
289    }
290
291    pub fn nodes(&self) -> &[GraphNode] {
292        &self.nodes
293    }
294
295    pub fn edges(&self) -> &[GraphEdge] {
296        &self.edges
297    }
298
299    pub fn node(&self, ix: NodeIx) -> Option<&GraphNode> {
300        self.nodes.get(ix)
301    }
302
303    pub fn edge(&self, ix: EdgeIx) -> Option<&GraphEdge> {
304        self.edges.get(ix)
305    }
306
307    /// Look up a node index by id.
308    pub fn index_of(&self, id: &str) -> Option<NodeIx> {
309        self.index.get(id).copied()
310    }
311
312    pub fn node_by_id(&self, id: &str) -> Option<&GraphNode> {
313        self.index_of(id).and_then(|ix| self.nodes.get(ix))
314    }
315
316    pub fn outgoing(&self, ix: NodeIx) -> &[EdgeIx] {
317        self.outgoing.get(ix).map(Vec::as_slice).unwrap_or_default()
318    }
319
320    pub fn incoming(&self, ix: NodeIx) -> &[EdgeIx] {
321        self.incoming.get(ix).map(Vec::as_slice).unwrap_or_default()
322    }
323
324    /// The root scope.
325    pub fn root_scope(&self) -> Option<&Scope> {
326        self.scopes.get(&None)
327    }
328
329    /// The body scope of a container node.
330    pub fn scope_of(&self, container: NodeIx) -> Option<&Scope> {
331        self.scopes.get(&Some(container))
332    }
333
334    /// Whether `ix` is (transitively) inside container `ancestor`.
335    pub fn is_descendant(&self, ix: NodeIx, ancestor: NodeIx) -> bool {
336        let mut cur = self.nodes.get(ix).and_then(|n| n.parent);
337        while let Some(c) = cur {
338            if c == ancestor {
339                return true;
340            }
341            cur = self.nodes.get(c).and_then(|n| n.parent);
342        }
343        false
344    }
345
346    /// Non-fatal findings (e.g. unreachable nodes).
347    pub fn warnings(&self) -> &[String] {
348        &self.warnings
349    }
350
351    /// Stable fingerprint of the source document, used to validate snapshots.
352    pub fn fingerprint(&self) -> &str {
353        &self.fingerprint
354    }
355
356    /// The source document.
357    pub fn workflow(&self) -> &Workflow {
358        &self.workflow
359    }
360}
361
362/// Check every selector a node declares in [`Node::inputs`]:
363///
364/// - its namespace must be a reserved namespace (`sys`, `env`, `conversation`)
365///   or a node id — otherwise the build fails, so typos surface at load time
366///   instead of silently resolving to null at run time;
367/// - a referenced node should be visible: in the same scope or an enclosing
368///   one (including the enclosing containers themselves), or inside the
369///   referencing container's own body. Other references only produce a warning,
370///   because they resolve to null at run time.
371fn validate_references(
372    nodes: &[GraphNode],
373    index: &HashMap<Arc<str>, NodeIx>,
374    warnings: &mut Vec<String>,
375) -> Result<(), GraphError> {
376    for (ix, n) in nodes.iter().enumerate() {
377        for selector in n.node.inputs() {
378            let namespace = selector.namespace();
379            if RESERVED_NAMESPACES.contains(&namespace) {
380                continue;
381            }
382            let Some(&target) = index.get(namespace) else {
383                return Err(GraphError::UnknownReference {
384                    node: n.id.to_string(),
385                    selector: selector.to_string(),
386                    namespace: namespace.to_owned(),
387                });
388            };
389            if !is_visible(nodes, ix, target) {
390                warnings.push(format!(
391                    "node `{}` references `{selector}` from a different container body; it will resolve to null",
392                    n.id
393                ));
394            }
395        }
396    }
397    Ok(())
398}
399
400/// Whether node `from` can read the outputs of node `target`.
401fn is_visible(nodes: &[GraphNode], from: NodeIx, target: NodeIx) -> bool {
402    let parent_of = |ix: NodeIx| nodes.get(ix).and_then(|n| n.parent);
403    let target_scope = parent_of(target);
404    // Same or enclosing scope.
405    let mut scope = parent_of(from);
406    loop {
407        if scope == target_scope {
408            return true;
409        }
410        match scope {
411            Some(s) => scope = parent_of(s),
412            None => break,
413        }
414    }
415    // Inside the referencing node's own body (a container reading its body outputs).
416    let mut cur = target_scope;
417    while let Some(c) = cur {
418        if c == from {
419            return true;
420        }
421        cur = parent_of(c);
422    }
423    false
424}
425
426fn find_entry(
427    nodes: &[GraphNode],
428    incoming: &[Vec<EdgeIx>],
429    owner: Option<NodeIx>,
430    scope_nodes: &[NodeIx],
431    scope_name: &str,
432) -> Result<NodeIx, GraphError> {
433    let wanted = if owner.is_some() { NodeRole::ScopeStart } else { NodeRole::Root };
434    let explicit: Vec<NodeIx> =
435        scope_nodes.iter().copied().filter(|&ix| nodes.get(ix).map(|n| n.role) == Some(wanted)).collect();
436    let candidates = if explicit.is_empty() {
437        // Fall back to the unique node without incoming edges.
438        scope_nodes.iter().copied().filter(|&ix| incoming.get(ix).is_none_or(Vec::is_empty)).collect()
439    } else {
440        explicit
441    };
442    match candidates.as_slice() {
443        [] => Err(GraphError::NoEntry { scope: scope_name.to_owned() }),
444        [one] => Ok(*one),
445        many => Err(GraphError::MultipleEntries {
446            scope: scope_name.to_owned(),
447            nodes: many.iter().filter_map(|&ix| nodes.get(ix)).map(|n| n.id.to_string()).collect(),
448        }),
449    }
450}
451
452fn topo_order(
453    scope_nodes: &[NodeIx],
454    outgoing: &[Vec<EdgeIx>],
455    incoming: &[Vec<EdgeIx>],
456    edges: &[GraphEdge],
457    nodes: &[GraphNode],
458    scope_name: &str,
459) -> Result<Vec<NodeIx>, GraphError> {
460    let mut indeg: HashMap<NodeIx, usize> =
461        scope_nodes.iter().map(|&ix| (ix, incoming.get(ix).map_or(0, Vec::len))).collect();
462    let mut queue: VecDeque<NodeIx> = scope_nodes.iter().copied().filter(|ix| indeg.get(ix) == Some(&0)).collect();
463    let mut order = Vec::with_capacity(scope_nodes.len());
464    while let Some(ix) = queue.pop_front() {
465        order.push(ix);
466        for &ex in outgoing.get(ix).map(Vec::as_slice).unwrap_or_default() {
467            if let Some(e) = edges.get(ex) {
468                if let Some(d) = indeg.get_mut(&e.target) {
469                    *d = d.saturating_sub(1);
470                    if *d == 0 {
471                        queue.push_back(e.target);
472                    }
473                }
474            }
475        }
476    }
477    if order.len() != scope_nodes.len() {
478        let stuck = scope_nodes
479            .iter()
480            .find(|ix| indeg.get(ix).is_some_and(|d| *d > 0))
481            .and_then(|&ix| nodes.get(ix))
482            .map(|n| n.id.to_string())
483            .unwrap_or_default();
484        return Err(GraphError::Cycle { scope: scope_name.to_owned(), node: stuck });
485    }
486    Ok(order)
487}
488
489fn reachable_from(entry: NodeIx, outgoing: &[Vec<EdgeIx>], edges: &[GraphEdge]) -> HashSet<NodeIx> {
490    let mut seen = HashSet::from([entry]);
491    let mut stack = vec![entry];
492    while let Some(ix) = stack.pop() {
493        for &ex in outgoing.get(ix).map(Vec::as_slice).unwrap_or_default() {
494            if let Some(e) = edges.get(ex) {
495                if seen.insert(e.target) {
496                    stack.push(e.target);
497                }
498            }
499        }
500    }
501    seen
502}
503
504/// FNV-1a over the canonical JSON of the graph section (stable across processes,
505/// unlike `DefaultHasher`).
506fn fingerprint(workflow: &Workflow) -> Result<String, GraphError> {
507    struct Fnv(u64);
508    impl Hasher for Fnv {
509        fn finish(&self) -> u64 {
510            self.0
511        }
512        fn write(&mut self, bytes: &[u8]) {
513            for b in bytes {
514                self.0 ^= u64::from(*b);
515                self.0 = self.0.wrapping_mul(0x0100_0000_01b3);
516            }
517        }
518    }
519    let mut h = Fnv(0xcbf2_9ce4_8422_2325);
520    let text = workflow.canonical_graph_json().map_err(|e| GraphError::Unserializable(e.to_string()))?;
521    text.hash(&mut h);
522    Ok(format!("{:016x}", h.finish()))
523}