1#[cfg(test)]
8#[path = "graph_composition_tests.rs"]
9mod tests;
10
11use std::{
12 collections::{BTreeMap, BTreeSet, VecDeque},
13 sync::Arc,
14};
15
16use serde::Serialize;
17use thiserror::Error;
18
19use crate::{
20 CompiledGraph, Digest, GraphCompileError, GraphNode, GraphReference, GraphRoute, GraphRoutes,
21 NodeId, ReadyNodes, RouteId,
22};
23
24#[derive(Clone, Debug)]
35pub struct SharedStateSubgraph {
36 graph: Arc<CompiledGraph>,
37 ports: BTreeSet<NodeId>,
38}
39
40impl SharedStateSubgraph {
41 pub fn new(graph: CompiledGraph) -> Result<Self, GraphCompositionError> {
48 if graph.child_runs().is_some() {
49 return Err(GraphCompositionError::ChildDelegationUnsupported);
50 }
51 let mut ports = BTreeSet::new();
52 for node in graph.nodes() {
53 if node.allows_terminal() {
54 if node.continue_to().is_some()
55 || !node.routes().is_empty()
56 || node.wait_to().is_some()
57 {
58 return Err(GraphCompositionError::MixedReturnPort {
59 node_id: node.node_id().clone(),
60 });
61 }
62 ports.insert(node.node_id().clone());
63 }
64 }
65 if ports.is_empty() {
66 return Err(GraphCompositionError::MissingReturnPorts);
67 }
68 if graph.entry_nodes().iter().any(|id| ports.contains(id)) {
69 return Err(GraphCompositionError::EntryIsReturnPort);
70 }
71 validate_finite_template(&graph, &ports)?;
72 Ok(Self {
73 graph: Arc::new(graph),
74 ports,
75 })
76 }
77
78 #[must_use]
80 pub fn graph(&self) -> &CompiledGraph {
81 &self.graph
82 }
83
84 pub fn return_ports(&self) -> impl ExactSizeIterator<Item = &NodeId> {
86 self.ports.iter()
87 }
88}
89
90#[derive(Clone, Debug)]
96pub struct GraphSubgraphCall {
97 node_id: NodeId,
98 subgraph: SharedStateSubgraph,
99 maximum_iterations: u16,
100 repeat_port: Option<NodeId>,
101 return_routes: BTreeMap<NodeId, RouteId>,
102}
103
104impl GraphSubgraphCall {
105 #[must_use]
107 pub const fn once(node_id: NodeId, subgraph: SharedStateSubgraph) -> Self {
108 Self {
109 node_id,
110 subgraph,
111 maximum_iterations: 1,
112 repeat_port: None,
113 return_routes: BTreeMap::new(),
114 }
115 }
116
117 pub fn bounded_loop(
130 node_id: NodeId,
131 subgraph: SharedStateSubgraph,
132 repeat_port: NodeId,
133 maximum_iterations: u16,
134 ) -> Result<Self, GraphCompositionError> {
135 if maximum_iterations == 0 || usize::from(maximum_iterations) > CompiledGraph::MAX_NODES {
136 return Err(GraphCompositionError::InvalidIterationLimit);
137 }
138 if !subgraph.ports.contains(&repeat_port) {
139 return Err(GraphCompositionError::UnknownRepeatPort { port: repeat_port });
140 }
141 Ok(Self {
142 node_id,
143 subgraph,
144 maximum_iterations,
145 repeat_port: Some(repeat_port),
146 return_routes: BTreeMap::new(),
147 })
148 }
149
150 pub fn with_return_routes<I>(mut self, routes: I) -> Result<Self, GraphCompositionError>
157 where
158 I: IntoIterator<Item = (NodeId, RouteId)>,
159 {
160 let mut bindings = BTreeMap::new();
161 let mut used = BTreeSet::new();
162 for (port, route) in routes {
163 if !self.subgraph.ports.contains(&port)
164 || !used.insert(route.clone())
165 || bindings.insert(port, route).is_some()
166 {
167 return Err(GraphCompositionError::ReturnRoutesMismatch {
168 node_id: self.node_id,
169 });
170 }
171 }
172 if bindings.len() != self.subgraph.ports.len() {
173 return Err(GraphCompositionError::ReturnRoutesMismatch {
174 node_id: self.node_id,
175 });
176 }
177 self.return_routes = bindings;
178 Ok(self)
179 }
180
181 fn matches_return(&self, port: &NodeId, route: &RouteId) -> bool {
182 self.return_routes
183 .get(port)
184 .map_or_else(|| port.as_str() == route.as_str(), |bound| bound == route)
185 }
186}
187
188#[derive(Clone, Debug, Eq, PartialEq, Serialize)]
194pub struct GraphNodeSource {
195 graph: GraphReference,
196 node_id: NodeId,
197 call_site: NodeId,
198 iteration: u16,
199 #[serde(skip_serializing_if = "BTreeMap::is_empty")]
200 routes: BTreeMap<RouteId, RouteId>,
201}
202
203impl GraphNodeSource {
204 #[must_use]
206 pub const fn graph(&self) -> &GraphReference {
207 &self.graph
208 }
209 #[must_use]
211 pub const fn node_id(&self) -> &NodeId {
212 &self.node_id
213 }
214 #[must_use]
216 pub const fn call_site(&self) -> &NodeId {
217 &self.call_site
218 }
219 #[must_use]
221 pub const fn iteration(&self) -> u16 {
222 self.iteration
223 }
224
225 #[must_use]
228 pub fn route_id(&self, source: &RouteId) -> Option<&RouteId> {
229 self.routes.get(source)
230 }
231}
232
233#[derive(Clone, Debug)]
242pub struct GraphComposition {
243 graph: CompiledGraph,
244 sources: BTreeMap<NodeId, GraphNodeSource>,
245}
246
247impl GraphComposition {
248 #[allow(clippy::too_many_lines)]
261 pub fn compile<I>(parent: CompiledGraph, calls: I) -> Result<Self, GraphCompositionError>
262 where
263 I: IntoIterator<Item = GraphSubgraphCall>,
264 {
265 let (by_id, count) = collect_calls(&parent, calls)?;
266 if by_id.is_empty() {
267 return Ok(Self {
268 graph: parent,
269 sources: BTreeMap::new(),
270 });
271 }
272 if parent.child_runs().is_some() {
273 return Err(GraphCompositionError::ChildDelegationUnsupported);
274 }
275
276 let mut sources = BTreeMap::new();
277 let mut identities = BTreeMap::new();
278 for call in by_id.values() {
279 for iteration in 0..call.maximum_iterations {
280 for (ordinal, node) in call.subgraph.graph.nodes().iter().enumerate() {
281 if call.subgraph.ports.contains(node.node_id()) {
282 continue;
283 }
284 let (generated, source) =
285 lower_identity(&parent, call, node, iteration, ordinal)?;
286 if parent.node(&generated).is_some()
287 || sources.insert(generated.clone(), source).is_some()
288 {
289 return Err(GraphCompositionError::IdentityCollision);
290 }
291 identities.insert(
292 (call.node_id.clone(), iteration, node.node_id().clone()),
293 generated,
294 );
295 }
296 }
297 }
298 let mut entries = BTreeMap::new();
299 for call in by_id.values() {
300 for iteration in 0..call.maximum_iterations {
301 let nodes =
302 call.subgraph.graph.entry_nodes().iter().map(|id| {
303 identities[&(call.node_id.clone(), iteration, id.clone())].clone()
304 });
305 entries.insert((call.node_id.clone(), iteration), ready(nodes)?);
306 }
307 }
308 let redirect_parent = |id: &NodeId| -> Vec<NodeId> {
309 entries
310 .get(&(id.clone(), 0))
311 .map_or_else(|| vec![id.clone()], |nodes| nodes.iter().cloned().collect())
312 };
313 let mut nodes = Vec::with_capacity(count);
314 for node in parent.nodes() {
315 if let Some(call) = by_id.get(node.node_id()) {
316 for iteration in 0..call.maximum_iterations {
317 let redirect_child = |id: &NodeId| -> Vec<NodeId> {
318 if !call.subgraph.ports.contains(id) {
319 return vec![
320 identities[&(call.node_id.clone(), iteration, id.clone())].clone(),
321 ];
322 }
323 if call.repeat_port.as_ref() == Some(id)
324 && iteration + 1 < call.maximum_iterations
325 {
326 return entries[&(call.node_id.clone(), iteration + 1)]
327 .iter()
328 .cloned()
329 .collect();
330 }
331 node.routes()
333 .iter()
334 .find(|route| call.matches_return(id, route.route_id()))
335 .into_iter()
336 .flat_map(|route| route.successors().iter().flat_map(&redirect_parent))
337 .collect()
338 };
339 for child in call.subgraph.graph.nodes() {
340 if !call.subgraph.ports.contains(child.node_id()) {
341 let generated = identities
342 [&(call.node_id.clone(), iteration, child.node_id().clone())]
343 .clone();
344 let routes = &sources[&generated].routes;
345 nodes.push(remap_node(
346 child,
347 generated,
348 &redirect_child,
349 Some(routes),
350 )?);
351 }
352 }
353 }
354 } else {
355 nodes.push(remap_node(
356 node,
357 node.node_id().clone(),
358 &redirect_parent,
359 None,
360 )?);
361 }
362 }
363 let entry_nodes = ready(parent.entry_nodes().iter().flat_map(redirect_parent))?;
364 let graph = CompiledGraph::compile(
365 parent.identity().clone(),
366 parent.input_schema().clone(),
367 parent.state_schema().clone(),
368 parent.update_schema().clone(),
369 parent.output_schema().clone(),
370 parent.reducer().clone(),
371 entry_nodes,
372 nodes,
373 parent.limits(),
374 )?;
375 Ok(Self { graph, sources })
376 }
377
378 #[must_use]
380 pub const fn graph(&self) -> &CompiledGraph {
381 &self.graph
382 }
383 pub fn node_sources(&self) -> impl ExactSizeIterator<Item = (&NodeId, &GraphNodeSource)> {
385 self.sources.iter()
386 }
387 #[must_use]
389 pub fn node_source(&self, node_id: &NodeId) -> Option<&GraphNodeSource> {
390 self.sources.get(node_id)
391 }
392 #[must_use]
394 pub fn into_graph(self) -> CompiledGraph {
395 self.graph
396 }
397}
398
399fn collect_calls(
400 parent: &CompiledGraph,
401 calls: impl IntoIterator<Item = GraphSubgraphCall>,
402) -> Result<(BTreeMap<NodeId, GraphSubgraphCall>, usize), GraphCompositionError> {
403 let mut by_id = BTreeMap::new();
404 let mut count = parent.nodes().len();
405 for call in calls {
406 if by_id.contains_key(&call.node_id) {
407 return Err(GraphCompositionError::DuplicateCallSite {
408 node_id: call.node_id,
409 });
410 }
411 validate_call(parent, &call)?;
412 let body_count = call.subgraph.graph.nodes().len() - call.subgraph.ports.len();
413 count = count - 1 + body_count * usize::from(call.maximum_iterations);
414 if count > CompiledGraph::MAX_NODES {
415 return Err(GraphCompositionError::ExpansionTooLarge);
416 }
417 by_id.insert(call.node_id.clone(), call);
418 }
419 Ok((by_id, count))
420}
421
422fn lower_identity(
423 parent: &CompiledGraph,
424 call: &GraphSubgraphCall,
425 node: &GraphNode,
426 iteration: u16,
427 ordinal: usize,
428) -> Result<(NodeId, GraphNodeSource), GraphCompositionError> {
429 let mut source = GraphNodeSource {
430 graph: call.subgraph.graph.reference(),
431 node_id: node.node_id().clone(),
432 call_site: call.node_id.clone(),
433 iteration,
434 routes: BTreeMap::new(),
435 };
436 let wire = serde_json::json!({
437 "domain": "stateknot.graph-composition.v1", "parent": parent.reference(),
438 "graph": source.graph, "call_site": source.call_site, "iteration": iteration,
439 "maximum_iterations": call.maximum_iterations, "repeat_port": call.repeat_port,
440 "return_routes": call.return_routes,
441 });
442 let bytes = serde_json_canonicalizer::to_vec(&wire)
443 .map_err(|_| GraphCompositionError::CanonicalSerialization)?;
444 let digest = Digest::sha256(bytes).to_string();
445 let generated = NodeId::new(format!("skc-{}-{ordinal:04}", &digest[7..]))
449 .map_err(|_| GraphCompositionError::CanonicalSerialization)?;
450 for route in node.routes().iter() {
451 let bytes = serde_json_canonicalizer::to_vec(&serde_json::json!({
452 "domain": "stateknot.graph-composition.route.v1", "node_id": generated, "route_id": route.route_id(),
453 })).map_err(|_| GraphCompositionError::CanonicalSerialization)?;
454 let digest = Digest::sha256(bytes).to_string();
455 let route_id = RouteId::new(format!("skr-{}", &digest[7..]))
456 .map_err(|_| GraphCompositionError::CanonicalSerialization)?;
457 source.routes.insert(route.route_id().clone(), route_id);
458 }
459 Ok((generated, source))
460}
461
462fn successors(node: &GraphNode) -> impl Iterator<Item = &NodeId> {
463 node.continue_to()
464 .into_iter()
465 .chain(node.routes().iter().map(GraphRoute::successors))
466 .chain(node.wait_to())
467 .flat_map(ReadyNodes::iter)
468}
469
470fn validate_finite_template(
471 graph: &CompiledGraph,
472 ports: &BTreeSet<NodeId>,
473) -> Result<(), GraphCompositionError> {
474 let mut incoming: BTreeMap<_, usize> = graph
475 .nodes()
476 .iter()
477 .map(|node| (node.node_id(), 0))
478 .collect();
479 let mut depths: BTreeMap<_, u64> = graph
480 .nodes()
481 .iter()
482 .map(|node| (node.node_id(), 1))
483 .collect();
484 for node in graph.nodes() {
485 for id in successors(node) {
486 *incoming
487 .get_mut(id)
488 .ok_or(GraphCompositionError::IdentityCollision)? += 1;
489 }
490 }
491 let mut queue: VecDeque<_> = incoming
492 .iter()
493 .filter_map(|(&id, &count)| (count == 0).then_some(id))
494 .collect();
495 let mut visited = 0;
496 while let Some(id) = queue.pop_front() {
497 visited += 1;
498 let depth = depths[id];
499 if !ports.contains(id) && depth > graph.limits().maximum_supersteps().get() {
500 return Err(GraphCompositionError::TemplateStepLimit);
501 }
502 let node = graph
503 .node(id)
504 .ok_or(GraphCompositionError::IdentityCollision)?;
505 for next in successors(node) {
506 let next_depth = depths
507 .get_mut(next)
508 .ok_or(GraphCompositionError::IdentityCollision)?;
509 *next_depth = (*next_depth).max(depth + 1);
510 let count = incoming
511 .get_mut(next)
512 .ok_or(GraphCompositionError::IdentityCollision)?;
513 *count -= 1;
514 if *count == 0 {
515 queue.push_back(next);
516 }
517 }
518 }
519 if visited != graph.nodes().len() {
520 return Err(GraphCompositionError::CyclicTemplate);
521 }
522 Ok(())
523}
524
525fn validate_call(
526 parent: &CompiledGraph,
527 call: &GraphSubgraphCall,
528) -> Result<(), GraphCompositionError> {
529 let node =
530 parent
531 .node(&call.node_id)
532 .ok_or_else(|| GraphCompositionError::UnknownCallSite {
533 node_id: call.node_id.clone(),
534 })?;
535 if node.continue_to().is_some()
536 || node.wait_to().is_some()
537 || node.allows_terminal()
538 || node.routes().len() != call.subgraph.ports.len()
539 || node.routes().iter().any(|route| {
540 !call
541 .subgraph
542 .ports
543 .iter()
544 .any(|id| call.matches_return(id, route.route_id()))
545 })
546 {
547 return Err(GraphCompositionError::ReturnRoutesMismatch {
548 node_id: call.node_id.clone(),
549 });
550 }
551 let child = &call.subgraph.graph;
552 if parent.input_schema() != child.input_schema()
553 || parent.state_schema() != child.state_schema()
554 || parent.update_schema() != child.update_schema()
555 || parent.output_schema() != child.output_schema()
556 || parent.reducer() != child.reducer()
557 {
558 return Err(GraphCompositionError::SharedStateContractMismatch {
559 node_id: call.node_id.clone(),
560 });
561 }
562 if parent.limits().maximum_parallelism() > child.limits().maximum_parallelism() {
563 return Err(GraphCompositionError::TemplateParallelismLimit {
564 node_id: call.node_id.clone(),
565 });
566 }
567 Ok(())
568}
569
570fn ready(nodes: impl IntoIterator<Item = NodeId>) -> Result<ReadyNodes, GraphCompositionError> {
571 let mut unique = BTreeSet::new();
574 for id in nodes {
575 unique.insert(id);
576 if unique.len() > ReadyNodes::MAX_LEN {
577 return Err(GraphCompositionError::ExpansionTooLarge);
578 }
579 }
580 ReadyNodes::try_new(unique).map_err(|_| GraphCompositionError::ExpansionTooLarge)
581}
582
583fn remap_node(
584 node: &GraphNode,
585 id: NodeId,
586 redirect: &impl Fn(&NodeId) -> Vec<NodeId>,
587 route_ids: Option<&BTreeMap<RouteId, RouteId>>,
588) -> Result<GraphNode, GraphCompositionError> {
589 let remap = |nodes: &ReadyNodes| ready(nodes.iter().flat_map(redirect));
590 let routes = node
591 .routes()
592 .iter()
593 .map(|route| {
594 let route_id = route_ids.map_or_else(
595 || route.route_id().clone(),
596 |ids| ids[route.route_id()].clone(),
597 );
598 GraphRoute::new(route_id, remap(route.successors())?)
599 .map_err(|_| GraphCompositionError::ExpansionTooLarge)
600 })
601 .collect::<Result<Vec<_>, _>>()?;
602 GraphNode::new(
603 id,
604 node.continue_to().map(remap).transpose()?,
605 GraphRoutes::try_new(routes).map_err(|_| GraphCompositionError::ExpansionTooLarge)?,
606 node.wait_to().map(remap).transpose()?,
607 node.allows_terminal(),
608 )
609 .map_err(|_| GraphCompositionError::ExpansionTooLarge)
610}
611
612#[derive(Clone, Debug, Eq, Error, PartialEq)]
614#[non_exhaustive]
615pub enum GraphCompositionError {
616 #[error("static composition does not support child delegation declarations")]
618 ChildDelegationUnsupported,
619 #[error("subgraph return port {node_id} also declares executable controls")]
621 MixedReturnPort {
622 node_id: NodeId,
624 },
625 #[error("subgraph has no return ports")]
627 MissingReturnPorts,
628 #[error("subgraph entry cannot be a return port")]
630 EntryIsReturnPort,
631 #[error("subgraph template contains a cycle; use a bounded loop call")]
633 CyclicTemplate,
634 #[error("subgraph body path exceeds its maximum supersteps")]
636 TemplateStepLimit,
637 #[error("loop iterations must be between 1 and 1024")]
639 InvalidIterationLimit,
640 #[error("loop repeat port {port} is not a subgraph return port")]
642 UnknownRepeatPort {
643 port: NodeId,
645 },
646 #[error("duplicate subgraph call-site {node_id}")]
648 DuplicateCallSite {
649 node_id: NodeId,
651 },
652 #[error("unknown subgraph call-site {node_id}")]
654 UnknownCallSite {
655 node_id: NodeId,
657 },
658 #[error("subgraph call-site {node_id} must declare exactly its return routes")]
660 ReturnRoutesMismatch {
661 node_id: NodeId,
663 },
664 #[error("subgraph call-site {node_id} has incompatible schema or reducer pins")]
666 SharedStateContractMismatch {
667 node_id: NodeId,
669 },
670 #[error("parent parallelism exceeds subgraph ceiling at {node_id}")]
672 TemplateParallelismLimit {
673 node_id: NodeId,
675 },
676 #[error("expanded graph exceeds a node, route, or ready-set ceiling")]
678 ExpansionTooLarge,
679 #[error("graph composition identity cannot be canonicalized")]
681 CanonicalSerialization,
682 #[error("graph composition node identity collision")]
684 IdentityCollision,
685 #[error(transparent)]
687 Graph(#[from] GraphCompileError),
688}