1use 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
20pub const SOURCE_HANDLE: &str = "source";
22pub const FAIL_BRANCH: &str = "fail-branch";
24
25pub type NodeIx = usize;
27pub type EdgeIx = usize;
29
30pub struct GraphNode {
32 pub id: Arc<str>,
33 pub kind: Arc<str>,
35 pub title: Arc<str>,
36 pub parent: Option<NodeIx>,
38 pub policy: NodePolicy,
39 pub role: NodeRole,
40 pub node: Arc<dyn Node>,
41 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#[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#[derive(Clone, Debug, PartialEq, Eq)]
62pub struct Scope {
63 pub owner: Option<NodeIx>,
65 pub entry: NodeIx,
67 pub nodes: Vec<NodeIx>,
69}
70
71#[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
107const 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
128pub 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 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 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 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 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 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 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 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 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 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 pub fn root_scope(&self) -> Option<&Scope> {
327 self.scopes.get(&None)
328 }
329
330 pub fn scope_of(&self, container: NodeIx) -> Option<&Scope> {
332 self.scopes.get(&Some(container))
333 }
334
335 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 pub fn warnings(&self) -> &[String] {
349 &self.warnings
350 }
351
352 pub fn fingerprint(&self) -> &str {
354 &self.fingerprint
355 }
356
357 pub fn workflow(&self) -> &Workflow {
359 &self.workflow
360 }
361}
362
363fn 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
401fn 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 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 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 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
505fn 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}