use std::collections::{HashMap, HashSet, VecDeque};
use std::fmt;
use std::hash::{Hash, Hasher};
use std::sync::Arc;
use crate::dsl::{NodeDoc, NodePolicy, Workflow};
use crate::node::{ConfigError, Node, NodeRole, Registry};
pub const SOURCE_HANDLE: &str = "source";
pub const FAIL_BRANCH: &str = "fail-branch";
pub type NodeIx = usize;
pub type EdgeIx = usize;
pub struct GraphNode {
pub id: Arc<str>,
pub kind: String,
pub title: String,
pub parent: Option<NodeIx>,
pub policy: NodePolicy,
pub role: NodeRole,
pub node: Arc<dyn Node>,
pub doc: NodeDoc,
}
impl fmt::Debug for GraphNode {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("GraphNode").field("id", &self.id).field("kind", &self.kind).field("role", &self.role).finish()
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct GraphEdge {
pub id: Arc<str>,
pub source: NodeIx,
pub target: NodeIx,
pub handle: Arc<str>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Scope {
pub owner: Option<NodeIx>,
pub entry: NodeIx,
pub nodes: Vec<NodeIx>,
}
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum GraphError {
#[error(transparent)]
Config(#[from] ConfigError),
#[error("duplicate node id `{0}`")]
DuplicateNode(String),
#[error("duplicate edge id `{0}`")]
DuplicateEdge(String),
#[error("edge `{edge}` references unknown node `{node}`")]
MissingNode { edge: String, node: String },
#[error("node `{node}` references unknown parent `{parent}`")]
MissingParent { node: String, parent: String },
#[error("node `{0}` has a parent that is not a container node")]
ParentNotContainer(String),
#[error("container nesting cycle at node `{0}`")]
ParentCycle(String),
#[error("edge `{edge}` crosses scopes (`{source_node}` -> `{target}`)")]
CrossScopeEdge { edge: String, source_node: String, target: String },
#[error("cycle detected in scope `{scope}` involving node `{node}`")]
Cycle { scope: String, node: String },
#[error("scope `{scope}` has no entry node")]
NoEntry { scope: String },
#[error("scope `{scope}` has multiple entry nodes: {nodes:?}")]
MultipleEntries { scope: String, nodes: Vec<String> },
#[error("graph has no nodes")]
Empty,
#[error("workflow cannot be serialized: {0}")]
Unserializable(String),
#[error("invalid node id `{id}`: {reason}")]
InvalidNodeId { id: String, reason: String },
#[error("node `{node}` references `{selector}`, but no node or variable namespace `{namespace}` exists")]
UnknownReference { node: String, selector: String, namespace: String },
}
const RESERVED_NAMESPACES: &[&str] = &[crate::pool::SYS, crate::pool::ENV, crate::pool::CONVERSATION];
fn validate_node_id(id: &str) -> Result<(), GraphError> {
let reason = if id.is_empty() {
Some("must not be empty")
} else if RESERVED_NAMESPACES.contains(&id) {
Some("is a reserved variable namespace")
} else if id.contains('.') {
Some("must not contain `.` (it separates selector parts)")
} else if id.chars().any(char::is_whitespace) {
Some("must not contain whitespace")
} else {
None
};
match reason {
Some(reason) => Err(GraphError::InvalidNodeId { id: id.to_owned(), reason: reason.to_owned() }),
None => Ok(()),
}
}
pub struct Graph {
nodes: Vec<GraphNode>,
edges: Vec<GraphEdge>,
index: HashMap<Arc<str>, NodeIx>,
outgoing: Vec<Vec<EdgeIx>>,
incoming: Vec<Vec<EdgeIx>>,
scopes: HashMap<Option<NodeIx>, Scope>,
warnings: Vec<String>,
fingerprint: String,
workflow: Workflow,
}
impl fmt::Debug for Graph {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Graph")
.field("nodes", &self.nodes.len())
.field("edges", &self.edges.len())
.field("fingerprint", &self.fingerprint)
.finish()
}
}
impl Graph {
pub fn build(workflow: Workflow, registry: &Registry) -> Result<Self, GraphError> {
let docs = &workflow.graph.nodes;
if docs.is_empty() {
return Err(GraphError::Empty);
}
let mut index: HashMap<Arc<str>, NodeIx> = HashMap::with_capacity(docs.len());
for (ix, doc) in docs.iter().enumerate() {
validate_node_id(&doc.id)?;
if index.insert(Arc::from(doc.id.as_str()), ix).is_some() {
return Err(GraphError::DuplicateNode(doc.id.clone()));
}
}
let mut nodes = Vec::with_capacity(docs.len());
for doc in docs {
let parent = match &doc.parent {
Some(p) => Some(
*index
.get(p.as_str())
.ok_or_else(|| GraphError::MissingParent { node: doc.id.clone(), parent: p.clone() })?,
),
None => None,
};
let node = registry.build(doc)?;
nodes.push(GraphNode {
id: Arc::from(doc.id.as_str()),
kind: doc.kind.clone(),
title: doc.label().to_owned(),
parent,
policy: doc.policy.clone(),
role: node.role(),
node,
doc: doc.clone(),
});
}
for (ix, n) in nodes.iter().enumerate() {
if let Some(p) = n.parent {
if nodes.get(p).map(|pn| pn.role) != Some(NodeRole::Container) {
return Err(GraphError::ParentNotContainer(n.id.to_string()));
}
}
let mut seen = HashSet::new();
let mut cur = Some(ix);
while let Some(c) = cur {
if !seen.insert(c) {
return Err(GraphError::ParentCycle(n.id.to_string()));
}
cur = nodes.get(c).and_then(|x| x.parent);
}
}
let mut edges = Vec::with_capacity(workflow.graph.edges.len());
let mut edge_ids = HashSet::new();
let mut outgoing = vec![Vec::new(); nodes.len()];
let mut incoming = vec![Vec::new(); nodes.len()];
for (i, e) in workflow.graph.edges.iter().enumerate() {
let id: Arc<str> = Arc::from(e.id.clone().unwrap_or_else(|| format!("{}-{}-{i}", e.source, e.target)));
if !edge_ids.insert(id.clone()) {
return Err(GraphError::DuplicateEdge(id.to_string()));
}
let lookup = |n: &str| {
index
.get(n)
.copied()
.ok_or_else(|| GraphError::MissingNode { edge: id.to_string(), node: n.to_owned() })
};
let source = lookup(&e.source)?;
let target = lookup(&e.target)?;
let (sp, tp) = (nodes.get(source).and_then(|n| n.parent), nodes.get(target).and_then(|n| n.parent));
if sp != tp {
return Err(GraphError::CrossScopeEdge {
edge: id.to_string(),
source_node: e.source.clone(),
target: e.target.clone(),
});
}
let ex = edges.len();
edges.push(GraphEdge {
id,
source,
target,
handle: Arc::from(e.handle.as_deref().filter(|h| !h.is_empty()).unwrap_or(SOURCE_HANDLE)),
});
if let Some(o) = outgoing.get_mut(source) {
o.push(ex);
}
if let Some(inc) = incoming.get_mut(target) {
inc.push(ex);
}
}
let mut members: HashMap<Option<NodeIx>, Vec<NodeIx>> = HashMap::new();
for (ix, n) in nodes.iter().enumerate() {
members.entry(n.parent).or_default().push(ix);
}
for (ix, n) in nodes.iter().enumerate() {
if n.role == NodeRole::Container {
members.entry(Some(ix)).or_default();
}
}
let mut warnings = Vec::new();
let mut scopes = HashMap::new();
for (owner, scope_nodes) in members {
let scope_name =
owner.and_then(|o| nodes.get(o)).map(|n| n.id.to_string()).unwrap_or_else(|| "root".into());
let entry = find_entry(&nodes, &incoming, owner, &scope_nodes, &scope_name)?;
let order = topo_order(&scope_nodes, &outgoing, &incoming, &edges, &nodes, &scope_name)?;
let reachable = reachable_from(entry, &outgoing, &edges);
for &ix in &scope_nodes {
if !reachable.contains(&ix) {
if let Some(n) = nodes.get(ix) {
warnings
.push(format!("node `{}` is not reachable from the entry of scope `{scope_name}`", n.id));
}
}
}
scopes.insert(owner, Scope { owner, entry, nodes: order });
}
validate_references(&nodes, &index, &mut warnings)?;
let fingerprint = fingerprint(&workflow)?;
Ok(Self { nodes, edges, index, outgoing, incoming, scopes, warnings, fingerprint, workflow })
}
pub fn from_text(text: &str, registry: &Registry) -> Result<Self, crate::Error> {
let wf = Workflow::parse(text)?;
Ok(Self::build(wf, registry)?)
}
pub fn nodes(&self) -> &[GraphNode] {
&self.nodes
}
pub fn edges(&self) -> &[GraphEdge] {
&self.edges
}
pub fn node(&self, ix: NodeIx) -> Option<&GraphNode> {
self.nodes.get(ix)
}
pub fn edge(&self, ix: EdgeIx) -> Option<&GraphEdge> {
self.edges.get(ix)
}
pub fn index_of(&self, id: &str) -> Option<NodeIx> {
self.index.get(id).copied()
}
pub fn node_by_id(&self, id: &str) -> Option<&GraphNode> {
self.index_of(id).and_then(|ix| self.nodes.get(ix))
}
pub fn outgoing(&self, ix: NodeIx) -> &[EdgeIx] {
self.outgoing.get(ix).map(Vec::as_slice).unwrap_or_default()
}
pub fn incoming(&self, ix: NodeIx) -> &[EdgeIx] {
self.incoming.get(ix).map(Vec::as_slice).unwrap_or_default()
}
pub fn root_scope(&self) -> Option<&Scope> {
self.scopes.get(&None)
}
pub fn scope_of(&self, container: NodeIx) -> Option<&Scope> {
self.scopes.get(&Some(container))
}
pub fn is_descendant(&self, ix: NodeIx, ancestor: NodeIx) -> bool {
let mut cur = self.nodes.get(ix).and_then(|n| n.parent);
while let Some(c) = cur {
if c == ancestor {
return true;
}
cur = self.nodes.get(c).and_then(|n| n.parent);
}
false
}
pub fn warnings(&self) -> &[String] {
&self.warnings
}
pub fn fingerprint(&self) -> &str {
&self.fingerprint
}
pub fn workflow(&self) -> &Workflow {
&self.workflow
}
}
fn validate_references(
nodes: &[GraphNode],
index: &HashMap<Arc<str>, NodeIx>,
warnings: &mut Vec<String>,
) -> Result<(), GraphError> {
for (ix, n) in nodes.iter().enumerate() {
for selector in n.node.inputs() {
let namespace = selector.namespace();
if RESERVED_NAMESPACES.contains(&namespace) {
continue;
}
let Some(&target) = index.get(namespace) else {
return Err(GraphError::UnknownReference {
node: n.id.to_string(),
selector: selector.to_string(),
namespace: namespace.to_owned(),
});
};
if !is_visible(nodes, ix, target) {
warnings.push(format!(
"node `{}` references `{selector}` from a different container body; it will resolve to null",
n.id
));
}
}
}
Ok(())
}
fn is_visible(nodes: &[GraphNode], from: NodeIx, target: NodeIx) -> bool {
let parent_of = |ix: NodeIx| nodes.get(ix).and_then(|n| n.parent);
let target_scope = parent_of(target);
let mut scope = parent_of(from);
loop {
if scope == target_scope {
return true;
}
match scope {
Some(s) => scope = parent_of(s),
None => break,
}
}
let mut cur = target_scope;
while let Some(c) = cur {
if c == from {
return true;
}
cur = parent_of(c);
}
false
}
fn find_entry(
nodes: &[GraphNode],
incoming: &[Vec<EdgeIx>],
owner: Option<NodeIx>,
scope_nodes: &[NodeIx],
scope_name: &str,
) -> Result<NodeIx, GraphError> {
let wanted = if owner.is_some() { NodeRole::ScopeStart } else { NodeRole::Root };
let explicit: Vec<NodeIx> =
scope_nodes.iter().copied().filter(|&ix| nodes.get(ix).map(|n| n.role) == Some(wanted)).collect();
let candidates = if explicit.is_empty() {
scope_nodes.iter().copied().filter(|&ix| incoming.get(ix).is_none_or(Vec::is_empty)).collect()
} else {
explicit
};
match candidates.as_slice() {
[] => Err(GraphError::NoEntry { scope: scope_name.to_owned() }),
[one] => Ok(*one),
many => Err(GraphError::MultipleEntries {
scope: scope_name.to_owned(),
nodes: many.iter().filter_map(|&ix| nodes.get(ix)).map(|n| n.id.to_string()).collect(),
}),
}
}
fn topo_order(
scope_nodes: &[NodeIx],
outgoing: &[Vec<EdgeIx>],
incoming: &[Vec<EdgeIx>],
edges: &[GraphEdge],
nodes: &[GraphNode],
scope_name: &str,
) -> Result<Vec<NodeIx>, GraphError> {
let mut indeg: HashMap<NodeIx, usize> =
scope_nodes.iter().map(|&ix| (ix, incoming.get(ix).map_or(0, Vec::len))).collect();
let mut queue: VecDeque<NodeIx> = scope_nodes.iter().copied().filter(|ix| indeg.get(ix) == Some(&0)).collect();
let mut order = Vec::with_capacity(scope_nodes.len());
while let Some(ix) = queue.pop_front() {
order.push(ix);
for &ex in outgoing.get(ix).map(Vec::as_slice).unwrap_or_default() {
if let Some(e) = edges.get(ex) {
if let Some(d) = indeg.get_mut(&e.target) {
*d = d.saturating_sub(1);
if *d == 0 {
queue.push_back(e.target);
}
}
}
}
}
if order.len() != scope_nodes.len() {
let stuck = scope_nodes
.iter()
.find(|ix| indeg.get(ix).is_some_and(|d| *d > 0))
.and_then(|&ix| nodes.get(ix))
.map(|n| n.id.to_string())
.unwrap_or_default();
return Err(GraphError::Cycle { scope: scope_name.to_owned(), node: stuck });
}
Ok(order)
}
fn reachable_from(entry: NodeIx, outgoing: &[Vec<EdgeIx>], edges: &[GraphEdge]) -> HashSet<NodeIx> {
let mut seen = HashSet::from([entry]);
let mut stack = vec![entry];
while let Some(ix) = stack.pop() {
for &ex in outgoing.get(ix).map(Vec::as_slice).unwrap_or_default() {
if let Some(e) = edges.get(ex) {
if seen.insert(e.target) {
stack.push(e.target);
}
}
}
}
seen
}
fn fingerprint(workflow: &Workflow) -> Result<String, GraphError> {
struct Fnv(u64);
impl Hasher for Fnv {
fn finish(&self) -> u64 {
self.0
}
fn write(&mut self, bytes: &[u8]) {
for b in bytes {
self.0 ^= u64::from(*b);
self.0 = self.0.wrapping_mul(0x0100_0000_01b3);
}
}
}
let mut h = Fnv(0xcbf2_9ce4_8422_2325);
let text = workflow.canonical_graph_json().map_err(|e| GraphError::Unserializable(e.to_string()))?;
text.hash(&mut h);
Ok(format!("{:016x}", h.finish()))
}