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