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: String,
34 pub title: String,
35 pub parent: Option<NodeIx>,
37 pub policy: NodePolicy,
38 pub role: NodeRole,
39 pub node: Arc<dyn Node>,
40 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#[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#[derive(Clone, Debug, PartialEq, Eq)]
61pub struct Scope {
62 pub owner: Option<NodeIx>,
64 pub entry: NodeIx,
66 pub nodes: Vec<NodeIx>,
68}
69
70#[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
106const 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
127pub 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 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 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 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 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 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 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 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 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 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 pub fn root_scope(&self) -> Option<&Scope> {
326 self.scopes.get(&None)
327 }
328
329 pub fn scope_of(&self, container: NodeIx) -> Option<&Scope> {
331 self.scopes.get(&Some(container))
332 }
333
334 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 pub fn warnings(&self) -> &[String] {
348 &self.warnings
349 }
350
351 pub fn fingerprint(&self) -> &str {
353 &self.fingerprint
354 }
355
356 pub fn workflow(&self) -> &Workflow {
358 &self.workflow
359 }
360}
361
362fn 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
400fn 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 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 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 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
504fn 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}