#[cfg(test)]
#[path = "graph_composition_tests.rs"]
mod tests;
use std::{
collections::{BTreeMap, BTreeSet, VecDeque},
sync::Arc,
};
use serde::Serialize;
use thiserror::Error;
use crate::{
CompiledGraph, Digest, GraphCompileError, GraphNode, GraphReference, GraphRoute, GraphRoutes,
NodeId, ReadyNodes, RouteId,
};
#[derive(Clone, Debug)]
pub struct SharedStateSubgraph {
graph: Arc<CompiledGraph>,
ports: BTreeSet<NodeId>,
}
impl SharedStateSubgraph {
pub fn new(graph: CompiledGraph) -> Result<Self, GraphCompositionError> {
if graph.child_runs().is_some() {
return Err(GraphCompositionError::ChildDelegationUnsupported);
}
let mut ports = BTreeSet::new();
for node in graph.nodes() {
if node.allows_terminal() {
if node.continue_to().is_some()
|| !node.routes().is_empty()
|| node.wait_to().is_some()
{
return Err(GraphCompositionError::MixedReturnPort {
node_id: node.node_id().clone(),
});
}
ports.insert(node.node_id().clone());
}
}
if ports.is_empty() {
return Err(GraphCompositionError::MissingReturnPorts);
}
if graph.entry_nodes().iter().any(|id| ports.contains(id)) {
return Err(GraphCompositionError::EntryIsReturnPort);
}
validate_finite_template(&graph, &ports)?;
Ok(Self {
graph: Arc::new(graph),
ports,
})
}
#[must_use]
pub fn graph(&self) -> &CompiledGraph {
&self.graph
}
pub fn return_ports(&self) -> impl ExactSizeIterator<Item = &NodeId> {
self.ports.iter()
}
}
#[derive(Clone, Debug)]
pub struct GraphSubgraphCall {
node_id: NodeId,
subgraph: SharedStateSubgraph,
maximum_iterations: u16,
repeat_port: Option<NodeId>,
return_routes: BTreeMap<NodeId, RouteId>,
}
impl GraphSubgraphCall {
#[must_use]
pub const fn once(node_id: NodeId, subgraph: SharedStateSubgraph) -> Self {
Self {
node_id,
subgraph,
maximum_iterations: 1,
repeat_port: None,
return_routes: BTreeMap::new(),
}
}
pub fn bounded_loop(
node_id: NodeId,
subgraph: SharedStateSubgraph,
repeat_port: NodeId,
maximum_iterations: u16,
) -> Result<Self, GraphCompositionError> {
if maximum_iterations == 0 || usize::from(maximum_iterations) > CompiledGraph::MAX_NODES {
return Err(GraphCompositionError::InvalidIterationLimit);
}
if !subgraph.ports.contains(&repeat_port) {
return Err(GraphCompositionError::UnknownRepeatPort { port: repeat_port });
}
Ok(Self {
node_id,
subgraph,
maximum_iterations,
repeat_port: Some(repeat_port),
return_routes: BTreeMap::new(),
})
}
pub fn with_return_routes<I>(mut self, routes: I) -> Result<Self, GraphCompositionError>
where
I: IntoIterator<Item = (NodeId, RouteId)>,
{
let mut bindings = BTreeMap::new();
let mut used = BTreeSet::new();
for (port, route) in routes {
if !self.subgraph.ports.contains(&port)
|| !used.insert(route.clone())
|| bindings.insert(port, route).is_some()
{
return Err(GraphCompositionError::ReturnRoutesMismatch {
node_id: self.node_id,
});
}
}
if bindings.len() != self.subgraph.ports.len() {
return Err(GraphCompositionError::ReturnRoutesMismatch {
node_id: self.node_id,
});
}
self.return_routes = bindings;
Ok(self)
}
fn matches_return(&self, port: &NodeId, route: &RouteId) -> bool {
self.return_routes
.get(port)
.map_or_else(|| port.as_str() == route.as_str(), |bound| bound == route)
}
}
#[derive(Clone, Debug, Eq, PartialEq, Serialize)]
pub struct GraphNodeSource {
graph: GraphReference,
node_id: NodeId,
call_site: NodeId,
iteration: u16,
#[serde(skip_serializing_if = "BTreeMap::is_empty")]
routes: BTreeMap<RouteId, RouteId>,
}
impl GraphNodeSource {
#[must_use]
pub const fn graph(&self) -> &GraphReference {
&self.graph
}
#[must_use]
pub const fn node_id(&self) -> &NodeId {
&self.node_id
}
#[must_use]
pub const fn call_site(&self) -> &NodeId {
&self.call_site
}
#[must_use]
pub const fn iteration(&self) -> u16 {
self.iteration
}
#[must_use]
pub fn route_id(&self, source: &RouteId) -> Option<&RouteId> {
self.routes.get(source)
}
}
#[derive(Clone, Debug)]
pub struct GraphComposition {
graph: CompiledGraph,
sources: BTreeMap<NodeId, GraphNodeSource>,
}
impl GraphComposition {
#[allow(clippy::too_many_lines)]
pub fn compile<I>(parent: CompiledGraph, calls: I) -> Result<Self, GraphCompositionError>
where
I: IntoIterator<Item = GraphSubgraphCall>,
{
let (by_id, count) = collect_calls(&parent, calls)?;
if by_id.is_empty() {
return Ok(Self {
graph: parent,
sources: BTreeMap::new(),
});
}
if parent.child_runs().is_some() {
return Err(GraphCompositionError::ChildDelegationUnsupported);
}
let mut sources = BTreeMap::new();
let mut identities = BTreeMap::new();
for call in by_id.values() {
for iteration in 0..call.maximum_iterations {
for (ordinal, node) in call.subgraph.graph.nodes().iter().enumerate() {
if call.subgraph.ports.contains(node.node_id()) {
continue;
}
let (generated, source) =
lower_identity(&parent, call, node, iteration, ordinal)?;
if parent.node(&generated).is_some()
|| sources.insert(generated.clone(), source).is_some()
{
return Err(GraphCompositionError::IdentityCollision);
}
identities.insert(
(call.node_id.clone(), iteration, node.node_id().clone()),
generated,
);
}
}
}
let mut entries = BTreeMap::new();
for call in by_id.values() {
for iteration in 0..call.maximum_iterations {
let nodes =
call.subgraph.graph.entry_nodes().iter().map(|id| {
identities[&(call.node_id.clone(), iteration, id.clone())].clone()
});
entries.insert((call.node_id.clone(), iteration), ready(nodes)?);
}
}
let redirect_parent = |id: &NodeId| -> Vec<NodeId> {
entries
.get(&(id.clone(), 0))
.map_or_else(|| vec![id.clone()], |nodes| nodes.iter().cloned().collect())
};
let mut nodes = Vec::with_capacity(count);
for node in parent.nodes() {
if let Some(call) = by_id.get(node.node_id()) {
for iteration in 0..call.maximum_iterations {
let redirect_child = |id: &NodeId| -> Vec<NodeId> {
if !call.subgraph.ports.contains(id) {
return vec![
identities[&(call.node_id.clone(), iteration, id.clone())].clone(),
];
}
if call.repeat_port.as_ref() == Some(id)
&& iteration + 1 < call.maximum_iterations
{
return entries[&(call.node_id.clone(), iteration + 1)]
.iter()
.cloned()
.collect();
}
node.routes()
.iter()
.find(|route| call.matches_return(id, route.route_id()))
.into_iter()
.flat_map(|route| route.successors().iter().flat_map(&redirect_parent))
.collect()
};
for child in call.subgraph.graph.nodes() {
if !call.subgraph.ports.contains(child.node_id()) {
let generated = identities
[&(call.node_id.clone(), iteration, child.node_id().clone())]
.clone();
let routes = &sources[&generated].routes;
nodes.push(remap_node(
child,
generated,
&redirect_child,
Some(routes),
)?);
}
}
}
} else {
nodes.push(remap_node(
node,
node.node_id().clone(),
&redirect_parent,
None,
)?);
}
}
let entry_nodes = ready(parent.entry_nodes().iter().flat_map(redirect_parent))?;
let graph = CompiledGraph::compile(
parent.identity().clone(),
parent.input_schema().clone(),
parent.state_schema().clone(),
parent.update_schema().clone(),
parent.output_schema().clone(),
parent.reducer().clone(),
entry_nodes,
nodes,
parent.limits(),
)?;
Ok(Self { graph, sources })
}
#[must_use]
pub const fn graph(&self) -> &CompiledGraph {
&self.graph
}
pub fn node_sources(&self) -> impl ExactSizeIterator<Item = (&NodeId, &GraphNodeSource)> {
self.sources.iter()
}
#[must_use]
pub fn node_source(&self, node_id: &NodeId) -> Option<&GraphNodeSource> {
self.sources.get(node_id)
}
#[must_use]
pub fn into_graph(self) -> CompiledGraph {
self.graph
}
}
fn collect_calls(
parent: &CompiledGraph,
calls: impl IntoIterator<Item = GraphSubgraphCall>,
) -> Result<(BTreeMap<NodeId, GraphSubgraphCall>, usize), GraphCompositionError> {
let mut by_id = BTreeMap::new();
let mut count = parent.nodes().len();
for call in calls {
if by_id.contains_key(&call.node_id) {
return Err(GraphCompositionError::DuplicateCallSite {
node_id: call.node_id,
});
}
validate_call(parent, &call)?;
let body_count = call.subgraph.graph.nodes().len() - call.subgraph.ports.len();
count = count - 1 + body_count * usize::from(call.maximum_iterations);
if count > CompiledGraph::MAX_NODES {
return Err(GraphCompositionError::ExpansionTooLarge);
}
by_id.insert(call.node_id.clone(), call);
}
Ok((by_id, count))
}
fn lower_identity(
parent: &CompiledGraph,
call: &GraphSubgraphCall,
node: &GraphNode,
iteration: u16,
ordinal: usize,
) -> Result<(NodeId, GraphNodeSource), GraphCompositionError> {
let mut source = GraphNodeSource {
graph: call.subgraph.graph.reference(),
node_id: node.node_id().clone(),
call_site: call.node_id.clone(),
iteration,
routes: BTreeMap::new(),
};
let wire = serde_json::json!({
"domain": "stateknot.graph-composition.v1", "parent": parent.reference(),
"graph": source.graph, "call_site": source.call_site, "iteration": iteration,
"maximum_iterations": call.maximum_iterations, "repeat_port": call.repeat_port,
"return_routes": call.return_routes,
});
let bytes = serde_json_canonicalizer::to_vec(&wire)
.map_err(|_| GraphCompositionError::CanonicalSerialization)?;
let digest = Digest::sha256(bytes).to_string();
let generated = NodeId::new(format!("skc-{}-{ordinal:04}", &digest[7..]))
.map_err(|_| GraphCompositionError::CanonicalSerialization)?;
for route in node.routes().iter() {
let bytes = serde_json_canonicalizer::to_vec(&serde_json::json!({
"domain": "stateknot.graph-composition.route.v1", "node_id": generated, "route_id": route.route_id(),
})).map_err(|_| GraphCompositionError::CanonicalSerialization)?;
let digest = Digest::sha256(bytes).to_string();
let route_id = RouteId::new(format!("skr-{}", &digest[7..]))
.map_err(|_| GraphCompositionError::CanonicalSerialization)?;
source.routes.insert(route.route_id().clone(), route_id);
}
Ok((generated, source))
}
fn successors(node: &GraphNode) -> impl Iterator<Item = &NodeId> {
node.continue_to()
.into_iter()
.chain(node.routes().iter().map(GraphRoute::successors))
.chain(node.wait_to())
.flat_map(ReadyNodes::iter)
}
fn validate_finite_template(
graph: &CompiledGraph,
ports: &BTreeSet<NodeId>,
) -> Result<(), GraphCompositionError> {
let mut incoming: BTreeMap<_, usize> = graph
.nodes()
.iter()
.map(|node| (node.node_id(), 0))
.collect();
let mut depths: BTreeMap<_, u64> = graph
.nodes()
.iter()
.map(|node| (node.node_id(), 1))
.collect();
for node in graph.nodes() {
for id in successors(node) {
*incoming
.get_mut(id)
.ok_or(GraphCompositionError::IdentityCollision)? += 1;
}
}
let mut queue: VecDeque<_> = incoming
.iter()
.filter_map(|(&id, &count)| (count == 0).then_some(id))
.collect();
let mut visited = 0;
while let Some(id) = queue.pop_front() {
visited += 1;
let depth = depths[id];
if !ports.contains(id) && depth > graph.limits().maximum_supersteps().get() {
return Err(GraphCompositionError::TemplateStepLimit);
}
let node = graph
.node(id)
.ok_or(GraphCompositionError::IdentityCollision)?;
for next in successors(node) {
let next_depth = depths
.get_mut(next)
.ok_or(GraphCompositionError::IdentityCollision)?;
*next_depth = (*next_depth).max(depth + 1);
let count = incoming
.get_mut(next)
.ok_or(GraphCompositionError::IdentityCollision)?;
*count -= 1;
if *count == 0 {
queue.push_back(next);
}
}
}
if visited != graph.nodes().len() {
return Err(GraphCompositionError::CyclicTemplate);
}
Ok(())
}
fn validate_call(
parent: &CompiledGraph,
call: &GraphSubgraphCall,
) -> Result<(), GraphCompositionError> {
let node =
parent
.node(&call.node_id)
.ok_or_else(|| GraphCompositionError::UnknownCallSite {
node_id: call.node_id.clone(),
})?;
if node.continue_to().is_some()
|| node.wait_to().is_some()
|| node.allows_terminal()
|| node.routes().len() != call.subgraph.ports.len()
|| node.routes().iter().any(|route| {
!call
.subgraph
.ports
.iter()
.any(|id| call.matches_return(id, route.route_id()))
})
{
return Err(GraphCompositionError::ReturnRoutesMismatch {
node_id: call.node_id.clone(),
});
}
let child = &call.subgraph.graph;
if parent.input_schema() != child.input_schema()
|| parent.state_schema() != child.state_schema()
|| parent.update_schema() != child.update_schema()
|| parent.output_schema() != child.output_schema()
|| parent.reducer() != child.reducer()
{
return Err(GraphCompositionError::SharedStateContractMismatch {
node_id: call.node_id.clone(),
});
}
if parent.limits().maximum_parallelism() > child.limits().maximum_parallelism() {
return Err(GraphCompositionError::TemplateParallelismLimit {
node_id: call.node_id.clone(),
});
}
Ok(())
}
fn ready(nodes: impl IntoIterator<Item = NodeId>) -> Result<ReadyNodes, GraphCompositionError> {
let mut unique = BTreeSet::new();
for id in nodes {
unique.insert(id);
if unique.len() > ReadyNodes::MAX_LEN {
return Err(GraphCompositionError::ExpansionTooLarge);
}
}
ReadyNodes::try_new(unique).map_err(|_| GraphCompositionError::ExpansionTooLarge)
}
fn remap_node(
node: &GraphNode,
id: NodeId,
redirect: &impl Fn(&NodeId) -> Vec<NodeId>,
route_ids: Option<&BTreeMap<RouteId, RouteId>>,
) -> Result<GraphNode, GraphCompositionError> {
let remap = |nodes: &ReadyNodes| ready(nodes.iter().flat_map(redirect));
let routes = node
.routes()
.iter()
.map(|route| {
let route_id = route_ids.map_or_else(
|| route.route_id().clone(),
|ids| ids[route.route_id()].clone(),
);
GraphRoute::new(route_id, remap(route.successors())?)
.map_err(|_| GraphCompositionError::ExpansionTooLarge)
})
.collect::<Result<Vec<_>, _>>()?;
GraphNode::new(
id,
node.continue_to().map(remap).transpose()?,
GraphRoutes::try_new(routes).map_err(|_| GraphCompositionError::ExpansionTooLarge)?,
node.wait_to().map(remap).transpose()?,
node.allows_terminal(),
)
.map_err(|_| GraphCompositionError::ExpansionTooLarge)
}
#[derive(Clone, Debug, Eq, Error, PartialEq)]
#[non_exhaustive]
pub enum GraphCompositionError {
#[error("static composition does not support child delegation declarations")]
ChildDelegationUnsupported,
#[error("subgraph return port {node_id} also declares executable controls")]
MixedReturnPort {
node_id: NodeId,
},
#[error("subgraph has no return ports")]
MissingReturnPorts,
#[error("subgraph entry cannot be a return port")]
EntryIsReturnPort,
#[error("subgraph template contains a cycle; use a bounded loop call")]
CyclicTemplate,
#[error("subgraph body path exceeds its maximum supersteps")]
TemplateStepLimit,
#[error("loop iterations must be between 1 and 1024")]
InvalidIterationLimit,
#[error("loop repeat port {port} is not a subgraph return port")]
UnknownRepeatPort {
port: NodeId,
},
#[error("duplicate subgraph call-site {node_id}")]
DuplicateCallSite {
node_id: NodeId,
},
#[error("unknown subgraph call-site {node_id}")]
UnknownCallSite {
node_id: NodeId,
},
#[error("subgraph call-site {node_id} must declare exactly its return routes")]
ReturnRoutesMismatch {
node_id: NodeId,
},
#[error("subgraph call-site {node_id} has incompatible schema or reducer pins")]
SharedStateContractMismatch {
node_id: NodeId,
},
#[error("parent parallelism exceeds subgraph ceiling at {node_id}")]
TemplateParallelismLimit {
node_id: NodeId,
},
#[error("expanded graph exceeds a node, route, or ready-set ceiling")]
ExpansionTooLarge,
#[error("graph composition identity cannot be canonicalized")]
CanonicalSerialization,
#[error("graph composition node identity collision")]
IdentityCollision,
#[error(transparent)]
Graph(#[from] GraphCompileError),
}