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}`{}", 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 #[error("node `{node}`: {message}")]
111 InvalidField { node: String, path: String, message: String },
112 #[error("edge `{edge}`: {message}")]
114 UnknownHandle { edge: String, message: String },
115}
116
117use crate::validate::did_you_mean;
118
119pub(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
140pub 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 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 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 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 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 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 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 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 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 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 pub fn root_scope(&self) -> Option<&Scope> {
356 self.scopes.get(&None)
357 }
358
359 pub fn scope_of(&self, container: NodeIx) -> Option<&Scope> {
361 self.scopes.get(&Some(container))
362 }
363
364 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 pub fn warnings(&self) -> &[String] {
378 &self.warnings
379 }
380
381 pub fn fingerprint(&self) -> &str {
383 &self.fingerprint
384 }
385
386 pub fn workflow(&self) -> &Workflow {
388 &self.workflow
389 }
390}
391
392fn 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
432fn 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
447fn 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 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 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 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
551fn 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}