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