1use std::{
15 collections::{BTreeMap, BTreeSet, VecDeque},
16 fmt,
17 panic::{AssertUnwindSafe, catch_unwind},
18};
19
20use schemars::{JsonSchema, Schema, SchemaGenerator, json_schema};
21use serde::{Deserialize, Deserializer, Serialize, Serializer, de};
22use thiserror::Error;
23
24use crate::{
25 BoundedJson, CapabilityIdentity, Checkpoint, CheckpointBarrier, CheckpointBarrierError,
26 CheckpointId, CheckpointState, CheckpointStateError, CheckpointWrite, CheckpointWriteError,
27 ChildRunPolicyError, Digest, GraphChildRunPolicy, GraphReference, NodeActivation, NodeControl,
28 NodeControlKind, NodeId, NodeStateUpdate, NodeTerminalOutput, NodeWait, NodeWaits,
29 NodeWaitsError, PendingNodeResult, ReadyNodes, RouteId, SchemaReference, Superstep,
30};
31
32const MEBIBYTE: usize = 1024 * 1024;
33
34#[derive(Clone, Debug, Deserialize, Eq, Hash, JsonSchema, PartialEq, Serialize)]
36#[serde(deny_unknown_fields)]
37pub struct GraphReducerReference {
38 identity: CapabilityIdentity,
39 definition_digest: Digest,
40}
41
42impl GraphReducerReference {
43 #[must_use]
45 pub const fn new(identity: CapabilityIdentity, definition_digest: Digest) -> Self {
46 Self {
47 identity,
48 definition_digest,
49 }
50 }
51
52 #[must_use]
54 pub const fn identity(&self) -> &CapabilityIdentity {
55 &self.identity
56 }
57
58 #[must_use]
60 pub const fn definition_digest(&self) -> Digest {
61 self.definition_digest
62 }
63}
64
65#[derive(Clone, Copy, Debug, Eq, JsonSchema, PartialEq, Serialize)]
67#[serde(deny_unknown_fields)]
68pub struct GraphExecutionLimits {
69 maximum_supersteps: Superstep,
70 maximum_parallelism: u16,
71}
72
73impl GraphExecutionLimits {
74 pub const fn new(
81 maximum_supersteps: Superstep,
82 maximum_parallelism: u16,
83 ) -> Result<Self, GraphExecutionLimitsError> {
84 if maximum_supersteps.get() == 0 {
85 return Err(GraphExecutionLimitsError::ZeroSupersteps);
86 }
87 if maximum_parallelism == 0 {
88 return Err(GraphExecutionLimitsError::ZeroParallelism);
89 }
90 if maximum_parallelism as usize > ReadyNodes::MAX_LEN {
91 return Err(
92 GraphExecutionLimitsError::ParallelismAboveFrameworkMaximum {
93 maximum: ReadyNodes::MAX_LEN,
94 actual: maximum_parallelism as usize,
95 },
96 );
97 }
98 Ok(Self {
99 maximum_supersteps,
100 maximum_parallelism,
101 })
102 }
103
104 #[must_use]
106 pub const fn maximum_supersteps(self) -> Superstep {
107 self.maximum_supersteps
108 }
109
110 #[must_use]
112 pub const fn maximum_parallelism(self) -> u16 {
113 self.maximum_parallelism
114 }
115}
116
117impl<'de> Deserialize<'de> for GraphExecutionLimits {
118 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
119 where
120 D: Deserializer<'de>,
121 {
122 #[derive(Deserialize)]
123 #[serde(deny_unknown_fields)]
124 struct Wire {
125 maximum_supersteps: Superstep,
126 maximum_parallelism: u16,
127 }
128
129 let wire = Wire::deserialize(deserializer)?;
130 Self::new(wire.maximum_supersteps, wire.maximum_parallelism).map_err(de::Error::custom)
131 }
132}
133
134#[derive(Clone, Debug, Eq, Error, PartialEq)]
136#[non_exhaustive]
137pub enum GraphExecutionLimitsError {
138 #[error("graph maximum supersteps must be positive")]
140 ZeroSupersteps,
141 #[error("graph maximum parallelism must be positive")]
143 ZeroParallelism,
144 #[error("graph maximum parallelism is {actual}; framework maximum is {maximum}")]
146 ParallelismAboveFrameworkMaximum {
147 maximum: usize,
149 actual: usize,
151 },
152}
153
154#[derive(Clone, Debug, Eq, JsonSchema, PartialEq, Serialize)]
156#[serde(deny_unknown_fields)]
157pub struct GraphRoute {
158 route_id: RouteId,
159 successors: ReadyNodes,
160}
161
162impl GraphRoute {
163 pub fn new(route_id: RouteId, successors: ReadyNodes) -> Result<Self, GraphRouteError> {
170 if successors.is_empty() {
171 return Err(GraphRouteError::EmptySuccessors);
172 }
173 Ok(Self {
174 route_id,
175 successors,
176 })
177 }
178
179 #[must_use]
181 pub const fn route_id(&self) -> &RouteId {
182 &self.route_id
183 }
184
185 #[must_use]
187 pub const fn successors(&self) -> &ReadyNodes {
188 &self.successors
189 }
190}
191
192impl<'de> Deserialize<'de> for GraphRoute {
193 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
194 where
195 D: Deserializer<'de>,
196 {
197 #[derive(Deserialize)]
198 #[serde(deny_unknown_fields)]
199 struct Wire {
200 route_id: RouteId,
201 successors: ReadyNodes,
202 }
203
204 let wire = Wire::deserialize(deserializer)?;
205 Self::new(wire.route_id, wire.successors).map_err(de::Error::custom)
206 }
207}
208
209#[derive(Clone, Debug, Eq, Error, PartialEq)]
211#[non_exhaustive]
212pub enum GraphRouteError {
213 #[error("graph route successors must not be empty")]
215 EmptySuccessors,
216}
217
218#[derive(Clone, Debug, Eq, PartialEq)]
220pub struct GraphRoutes(Box<[GraphRoute]>);
221
222impl GraphRoutes {
223 pub const MAX_LEN: usize = 256;
225
226 pub fn try_new<I>(routes: I) -> Result<Self, GraphRoutesError>
233 where
234 I: IntoIterator<Item = GraphRoute>,
235 {
236 let mut values = Vec::new();
237 let mut identities = BTreeSet::new();
238 for route in routes {
239 if values.len() == Self::MAX_LEN {
240 return Err(GraphRoutesError::TooMany {
241 maximum: Self::MAX_LEN,
242 actual: Self::MAX_LEN + 1,
243 });
244 }
245 if !identities.insert(route.route_id.clone()) {
246 return Err(GraphRoutesError::Duplicate {
247 route_id: route.route_id,
248 });
249 }
250 values.push(route);
251 }
252 values.sort_unstable_by(|left, right| left.route_id.cmp(&right.route_id));
253 Ok(Self(values.into_boxed_slice()))
254 }
255
256 #[must_use]
258 pub fn empty() -> Self {
259 Self(Box::new([]))
260 }
261
262 #[must_use]
264 pub const fn len(&self) -> usize {
265 self.0.len()
266 }
267
268 #[must_use]
270 pub const fn is_empty(&self) -> bool {
271 self.0.is_empty()
272 }
273
274 pub fn iter(&self) -> impl ExactSizeIterator<Item = &GraphRoute> {
276 self.0.iter()
277 }
278
279 #[must_use]
281 pub fn get(&self, route_id: &RouteId) -> Option<&GraphRoute> {
282 self.0
283 .binary_search_by(|route| route.route_id.cmp(route_id))
284 .ok()
285 .map(|index| &self.0[index])
286 }
287}
288
289impl Default for GraphRoutes {
290 fn default() -> Self {
291 Self::empty()
292 }
293}
294
295impl Serialize for GraphRoutes {
296 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
297 where
298 S: Serializer,
299 {
300 serializer.collect_seq(self.iter())
301 }
302}
303
304impl<'de> Deserialize<'de> for GraphRoutes {
305 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
306 where
307 D: Deserializer<'de>,
308 {
309 let values = Vec::<GraphRoute>::deserialize(deserializer)?;
310 Self::try_new(values).map_err(de::Error::custom)
311 }
312}
313
314impl JsonSchema for GraphRoutes {
315 fn schema_name() -> std::borrow::Cow<'static, str> {
316 "GraphRoutes".into()
317 }
318
319 fn schema_id() -> std::borrow::Cow<'static, str> {
320 concat!(module_path!(), "::GraphRoutes").into()
321 }
322
323 fn json_schema(generator: &mut SchemaGenerator) -> Schema {
324 json_schema!({
325 "type": "array",
326 "items": generator.subschema_for::<GraphRoute>(),
327 "maxItems": 256,
328 "description": "Routes are serialized in ascending RouteId order and runtime rejects duplicate identities."
329 })
330 }
331}
332
333#[derive(Clone, Debug, Eq, Error, PartialEq)]
335#[non_exhaustive]
336pub enum GraphRoutesError {
337 #[error("graph node contains {actual} routes; maximum is {maximum}")]
339 TooMany {
340 maximum: usize,
342 actual: usize,
344 },
345 #[error("graph node contains duplicate route {route_id}")]
347 Duplicate {
348 route_id: RouteId,
350 },
351}
352
353#[derive(Clone, Debug, Eq, JsonSchema, PartialEq, Serialize)]
355#[serde(deny_unknown_fields)]
356pub struct GraphNode {
357 node_id: NodeId,
358 #[serde(skip_serializing_if = "Option::is_none")]
359 continue_to: Option<ReadyNodes>,
360 routes: GraphRoutes,
361 #[serde(skip_serializing_if = "Option::is_none")]
362 wait_to: Option<ReadyNodes>,
363 terminal: bool,
364}
365
366impl GraphNode {
367 pub fn new(
379 node_id: NodeId,
380 continue_to: Option<ReadyNodes>,
381 routes: GraphRoutes,
382 wait_to: Option<ReadyNodes>,
383 terminal: bool,
384 ) -> Result<Self, GraphNodeError> {
385 if continue_to.as_ref().is_some_and(ReadyNodes::is_empty) {
386 return Err(GraphNodeError::EmptyContinueSuccessors);
387 }
388 if wait_to.as_ref().is_some_and(ReadyNodes::is_empty) {
389 return Err(GraphNodeError::EmptyWaitSuccessors);
390 }
391 if continue_to.is_none() && routes.is_empty() && wait_to.is_none() && !terminal {
392 return Err(GraphNodeError::NoControlOutcome);
393 }
394 Ok(Self {
395 node_id,
396 continue_to,
397 routes,
398 wait_to,
399 terminal,
400 })
401 }
402
403 #[must_use]
405 pub const fn node_id(&self) -> &NodeId {
406 &self.node_id
407 }
408
409 #[must_use]
411 pub const fn continue_to(&self) -> Option<&ReadyNodes> {
412 self.continue_to.as_ref()
413 }
414
415 #[must_use]
417 pub const fn routes(&self) -> &GraphRoutes {
418 &self.routes
419 }
420
421 #[must_use]
423 pub const fn wait_to(&self) -> Option<&ReadyNodes> {
424 self.wait_to.as_ref()
425 }
426
427 #[must_use]
429 pub const fn allows_terminal(&self) -> bool {
430 self.terminal
431 }
432
433 fn successor_sets(&self) -> impl Iterator<Item = &ReadyNodes> {
434 self.continue_to
435 .iter()
436 .chain(self.routes.iter().map(GraphRoute::successors))
437 .chain(self.wait_to.iter())
438 }
439
440 const fn is_boundary(&self) -> bool {
441 self.terminal || self.wait_to.is_some()
442 }
443}
444
445impl<'de> Deserialize<'de> for GraphNode {
446 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
447 where
448 D: Deserializer<'de>,
449 {
450 #[derive(Deserialize)]
451 #[serde(deny_unknown_fields)]
452 struct Wire {
453 node_id: NodeId,
454 continue_to: Option<ReadyNodes>,
455 routes: GraphRoutes,
456 wait_to: Option<ReadyNodes>,
457 terminal: bool,
458 }
459
460 let wire = Wire::deserialize(deserializer)?;
461 Self::new(
462 wire.node_id,
463 wire.continue_to,
464 wire.routes,
465 wire.wait_to,
466 wire.terminal,
467 )
468 .map_err(de::Error::custom)
469 }
470}
471
472#[derive(Clone, Debug, Eq, Error, PartialEq)]
474#[non_exhaustive]
475pub enum GraphNodeError {
476 #[error("graph node must declare at least one control outcome")]
478 NoControlOutcome,
479 #[error("graph continue successors must not be empty")]
481 EmptyContinueSuccessors,
482 #[error("graph wait successors must not be empty")]
484 EmptyWaitSuccessors,
485}
486
487#[derive(Clone, Eq, JsonSchema, PartialEq, Serialize)]
489#[serde(deny_unknown_fields)]
490pub struct CompiledGraph {
491 identity: CapabilityIdentity,
492 input_schema: SchemaReference,
493 state_schema: SchemaReference,
494 update_schema: SchemaReference,
495 output_schema: SchemaReference,
496 reducer: GraphReducerReference,
497 entry_nodes: ReadyNodes,
498 #[schemars(length(max = 1024))]
499 nodes: Box<[GraphNode]>,
500 limits: GraphExecutionLimits,
501 #[serde(skip_serializing_if = "Option::is_none")]
502 child_runs: Option<GraphChildRunPolicy>,
503 definition_digest: Digest,
504}
505
506impl CompiledGraph {
507 pub const MAX_NODES: usize = ReadyNodes::MAX_LEN;
509 pub const MAX_ROUTES: usize = Self::MAX_NODES * GraphRoutes::MAX_LEN;
511 pub const MAX_DEFINITION_BYTES: usize = 2 * MEBIBYTE;
513
514 #[allow(clippy::too_many_arguments)]
522 pub fn compile<I>(
523 identity: CapabilityIdentity,
524 input_schema: SchemaReference,
525 state_schema: SchemaReference,
526 update_schema: SchemaReference,
527 output_schema: SchemaReference,
528 reducer: GraphReducerReference,
529 entry_nodes: ReadyNodes,
530 nodes: I,
531 limits: GraphExecutionLimits,
532 ) -> Result<Self, GraphCompileError>
533 where
534 I: IntoIterator<Item = GraphNode>,
535 {
536 Self::build(
537 identity,
538 input_schema,
539 state_schema,
540 update_schema,
541 output_schema,
542 reducer,
543 entry_nodes,
544 nodes,
545 limits,
546 None,
547 None,
548 )
549 }
550
551 #[allow(clippy::too_many_arguments)]
552 fn build<I>(
553 identity: CapabilityIdentity,
554 input_schema: SchemaReference,
555 state_schema: SchemaReference,
556 update_schema: SchemaReference,
557 output_schema: SchemaReference,
558 reducer: GraphReducerReference,
559 entry_nodes: ReadyNodes,
560 nodes: I,
561 limits: GraphExecutionLimits,
562 child_runs: Option<GraphChildRunPolicy>,
563 supplied_digest: Option<Digest>,
564 ) -> Result<Self, GraphCompileError>
565 where
566 I: IntoIterator<Item = GraphNode>,
567 {
568 let by_id = collect_graph_nodes(nodes)?;
569 validate_compiled_shape(&by_id, &entry_nodes, limits)?;
570
571 let nodes = by_id.into_values().collect::<Vec<_>>().into_boxed_slice();
572 let mut graph = Self {
573 identity,
574 input_schema,
575 state_schema,
576 update_schema,
577 output_schema,
578 reducer,
579 entry_nodes,
580 nodes,
581 limits,
582 child_runs,
583 definition_digest: Digest::sha256([]),
584 };
585 if let Some(policy) = &graph.child_runs {
586 policy.validate_nodes(&graph)?;
587 }
588 let canonical = graph.canonical_definition_bytes()?;
589 if canonical.len() > Self::MAX_DEFINITION_BYTES {
590 return Err(GraphCompileError::DefinitionTooLarge {
591 maximum: Self::MAX_DEFINITION_BYTES,
592 actual: canonical.len(),
593 });
594 }
595 graph.definition_digest = Digest::sha256(&canonical);
596 if supplied_digest.is_some_and(|digest| digest != graph.definition_digest) {
597 return Err(GraphCompileError::DigestMismatch);
598 }
599 Ok(graph)
600 }
601
602 pub fn with_child_runs(self, policy: GraphChildRunPolicy) -> Result<Self, GraphCompileError> {
609 Self::build(
610 self.identity,
611 self.input_schema,
612 self.state_schema,
613 self.update_schema,
614 self.output_schema,
615 self.reducer,
616 self.entry_nodes,
617 self.nodes.into_vec(),
618 self.limits,
619 Some(policy),
620 None,
621 )
622 }
623
624 #[must_use]
626 pub const fn child_runs(&self) -> Option<&GraphChildRunPolicy> {
627 self.child_runs.as_ref()
628 }
629
630 #[must_use]
632 pub const fn identity(&self) -> &CapabilityIdentity {
633 &self.identity
634 }
635
636 #[must_use]
638 pub const fn input_schema(&self) -> &SchemaReference {
639 &self.input_schema
640 }
641
642 #[must_use]
644 pub const fn state_schema(&self) -> &SchemaReference {
645 &self.state_schema
646 }
647
648 #[must_use]
650 pub const fn update_schema(&self) -> &SchemaReference {
651 &self.update_schema
652 }
653
654 #[must_use]
656 pub const fn output_schema(&self) -> &SchemaReference {
657 &self.output_schema
658 }
659
660 #[must_use]
662 pub const fn reducer(&self) -> &GraphReducerReference {
663 &self.reducer
664 }
665
666 #[must_use]
668 pub const fn entry_nodes(&self) -> &ReadyNodes {
669 &self.entry_nodes
670 }
671
672 #[must_use]
674 pub const fn nodes(&self) -> &[GraphNode] {
675 &self.nodes
676 }
677
678 #[must_use]
680 pub const fn limits(&self) -> GraphExecutionLimits {
681 self.limits
682 }
683
684 #[must_use]
686 pub const fn definition_digest(&self) -> Digest {
687 self.definition_digest
688 }
689
690 #[must_use]
692 pub fn reference(&self) -> GraphReference {
693 GraphReference::new(
694 self.identity.clone(),
695 self.definition_digest,
696 self.state_schema.clone(),
697 )
698 }
699
700 pub fn canonical_definition_bytes(&self) -> Result<Vec<u8>, GraphCompileError> {
706 serde_json_canonicalizer::to_vec(&GraphDefinitionDigestWire {
707 identity: &self.identity,
708 input_schema: &self.input_schema,
709 state_schema: &self.state_schema,
710 update_schema: &self.update_schema,
711 output_schema: &self.output_schema,
712 reducer: &self.reducer,
713 entry_nodes: &self.entry_nodes,
714 nodes: &self.nodes,
715 limits: self.limits,
716 child_runs: self.child_runs.as_ref(),
717 })
718 .map_err(|_| GraphCompileError::CanonicalSerialization)
719 }
720
721 #[must_use]
723 pub fn node(&self, node_id: &NodeId) -> Option<&GraphNode> {
724 self.nodes
725 .binary_search_by(|node| node.node_id.cmp(node_id))
726 .ok()
727 .map(|index| &self.nodes[index])
728 }
729
730 pub fn plan_barrier<V, R>(
738 &self,
739 base: &Checkpoint,
740 results: &[PendingNodeResult],
741 successor_id: CheckpointId,
742 schemas: &V,
743 reducer: &R,
744 ) -> Result<GraphBarrierPlan, GraphBarrierPlanError>
745 where
746 V: GraphSchemaValidator + ?Sized,
747 R: GraphReducer + ?Sized,
748 {
749 GraphBarrierPlanner::new(self, base, results, successor_id, schemas, reducer).plan()
750 }
751}
752
753fn collect_graph_nodes<I>(nodes: I) -> Result<BTreeMap<NodeId, GraphNode>, GraphCompileError>
754where
755 I: IntoIterator<Item = GraphNode>,
756{
757 let mut by_id = BTreeMap::new();
758 let mut route_count = 0_usize;
759 let mut route_owners = BTreeMap::new();
760 for node in nodes {
761 if by_id.len() == CompiledGraph::MAX_NODES {
762 return Err(GraphCompileError::TooManyNodes {
763 maximum: CompiledGraph::MAX_NODES,
764 actual: CompiledGraph::MAX_NODES + 1,
765 });
766 }
767 route_count =
768 route_count
769 .checked_add(node.routes.len())
770 .ok_or(GraphCompileError::TooManyRoutes {
771 maximum: CompiledGraph::MAX_ROUTES,
772 actual: usize::MAX,
773 })?;
774 if route_count > CompiledGraph::MAX_ROUTES {
775 return Err(GraphCompileError::TooManyRoutes {
776 maximum: CompiledGraph::MAX_ROUTES,
777 actual: route_count,
778 });
779 }
780 for route in node.routes.iter() {
781 if let Some(first_node) =
782 route_owners.insert(route.route_id.clone(), node.node_id.clone())
783 {
784 return Err(GraphCompileError::DuplicateRoute {
785 route_id: route.route_id.clone(),
786 first_node,
787 second_node: node.node_id.clone(),
788 });
789 }
790 }
791 let node_id = node.node_id.clone();
792 if by_id.insert(node_id.clone(), node).is_some() {
793 return Err(GraphCompileError::DuplicateNode { node_id });
794 }
795 }
796 if by_id.is_empty() {
797 return Err(GraphCompileError::EmptyNodes);
798 }
799 Ok(by_id)
800}
801
802fn validate_compiled_shape(
803 nodes: &BTreeMap<NodeId, GraphNode>,
804 entry_nodes: &ReadyNodes,
805 limits: GraphExecutionLimits,
806) -> Result<(), GraphCompileError> {
807 if entry_nodes.is_empty() {
808 return Err(GraphCompileError::EmptyEntryNodes);
809 }
810 if entry_nodes.len() > usize::from(limits.maximum_parallelism) {
811 return Err(GraphCompileError::ParallelismExceeded {
812 node_id: None,
813 maximum: usize::from(limits.maximum_parallelism),
814 actual: entry_nodes.len(),
815 });
816 }
817 for entry in entry_nodes {
818 if !nodes.contains_key(entry) {
819 return Err(GraphCompileError::MissingEntryNode {
820 node_id: entry.clone(),
821 });
822 }
823 }
824 for node in nodes.values() {
825 validate_node_successors(nodes, node, limits)?;
826 }
827 validate_reachability(nodes, entry_nodes)?;
828 validate_boundary_paths(nodes)
829}
830
831fn validate_node_successors(
832 nodes: &BTreeMap<NodeId, GraphNode>,
833 node: &GraphNode,
834 limits: GraphExecutionLimits,
835) -> Result<(), GraphCompileError> {
836 for successors in node.successor_sets() {
837 if successors.len() > usize::from(limits.maximum_parallelism) {
838 return Err(GraphCompileError::ParallelismExceeded {
839 node_id: Some(node.node_id.clone()),
840 maximum: usize::from(limits.maximum_parallelism),
841 actual: successors.len(),
842 });
843 }
844 for successor in successors {
845 if !nodes.contains_key(successor) {
846 return Err(GraphCompileError::MissingSuccessorNode {
847 from_node: node.node_id.clone(),
848 target: successor.clone(),
849 });
850 }
851 }
852 }
853 Ok(())
854}
855
856impl fmt::Debug for CompiledGraph {
857 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
858 formatter
859 .debug_struct("CompiledGraph")
860 .field("identity", &self.identity)
861 .field("input_schema", &self.input_schema)
862 .field("state_schema", &self.state_schema)
863 .field("update_schema", &self.update_schema)
864 .field("output_schema", &self.output_schema)
865 .field("reducer", &self.reducer)
866 .field("entry_nodes", &self.entry_nodes)
867 .field("node_count", &self.nodes.len())
868 .field("limits", &self.limits)
869 .field("child_runs", &self.child_runs)
870 .field("definition_digest", &self.definition_digest)
871 .finish_non_exhaustive()
872 }
873}
874
875impl<'de> Deserialize<'de> for CompiledGraph {
876 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
877 where
878 D: Deserializer<'de>,
879 {
880 #[derive(Deserialize)]
881 #[serde(deny_unknown_fields)]
882 struct Wire {
883 identity: CapabilityIdentity,
884 input_schema: SchemaReference,
885 state_schema: SchemaReference,
886 update_schema: SchemaReference,
887 output_schema: SchemaReference,
888 reducer: GraphReducerReference,
889 entry_nodes: ReadyNodes,
890 nodes: Vec<GraphNode>,
891 limits: GraphExecutionLimits,
892 child_runs: Option<GraphChildRunPolicy>,
893 definition_digest: Digest,
894 }
895
896 let wire = Wire::deserialize(deserializer)?;
897 Self::build(
898 wire.identity,
899 wire.input_schema,
900 wire.state_schema,
901 wire.update_schema,
902 wire.output_schema,
903 wire.reducer,
904 wire.entry_nodes,
905 wire.nodes,
906 wire.limits,
907 wire.child_runs,
908 Some(wire.definition_digest),
909 )
910 .map_err(de::Error::custom)
911 }
912}
913
914#[derive(Serialize)]
915struct GraphDefinitionDigestWire<'a> {
916 identity: &'a CapabilityIdentity,
917 input_schema: &'a SchemaReference,
918 state_schema: &'a SchemaReference,
919 update_schema: &'a SchemaReference,
920 output_schema: &'a SchemaReference,
921 reducer: &'a GraphReducerReference,
922 entry_nodes: &'a ReadyNodes,
923 nodes: &'a [GraphNode],
924 limits: GraphExecutionLimits,
925 #[serde(skip_serializing_if = "Option::is_none")]
926 child_runs: Option<&'a GraphChildRunPolicy>,
927}
928
929fn validate_reachability(
930 nodes: &BTreeMap<NodeId, GraphNode>,
931 entries: &ReadyNodes,
932) -> Result<(), GraphCompileError> {
933 let mut reachable = BTreeSet::new();
934 let mut queue = VecDeque::new();
935 for entry in entries {
936 queue.push_back(entry.clone());
937 }
938 while let Some(node_id) = queue.pop_front() {
939 if !reachable.insert(node_id.clone()) {
940 continue;
941 }
942 let node = &nodes[&node_id];
943 for successors in node.successor_sets() {
944 for successor in successors {
945 queue.push_back(successor.clone());
946 }
947 }
948 }
949 if let Some(node_id) = nodes.keys().find(|node_id| !reachable.contains(*node_id)) {
950 return Err(GraphCompileError::UnreachableNode {
951 node_id: node_id.clone(),
952 });
953 }
954 Ok(())
955}
956
957fn validate_boundary_paths(nodes: &BTreeMap<NodeId, GraphNode>) -> Result<(), GraphCompileError> {
958 let mut can_reach_boundary = nodes
959 .values()
960 .filter(|node| node.is_boundary())
961 .map(|node| node.node_id.clone())
962 .collect::<BTreeSet<_>>();
963 loop {
964 let before = can_reach_boundary.len();
965 for node in nodes.values() {
966 if can_reach_boundary.contains(&node.node_id) {
967 continue;
968 }
969 if node.successor_sets().any(|successors| {
970 successors
971 .iter()
972 .any(|successor| can_reach_boundary.contains(successor))
973 }) {
974 can_reach_boundary.insert(node.node_id.clone());
975 }
976 }
977 if can_reach_boundary.len() == before {
978 break;
979 }
980 }
981 if let Some(node_id) = nodes
982 .keys()
983 .find(|node_id| !can_reach_boundary.contains(*node_id))
984 {
985 return Err(GraphCompileError::NoBoundaryPath {
986 node_id: node_id.clone(),
987 });
988 }
989 Ok(())
990}
991
992#[derive(Clone, Debug, Eq, Error, PartialEq)]
994#[non_exhaustive]
995pub enum GraphCompileError {
996 #[error("compiled graph must contain at least one node")]
998 EmptyNodes,
999 #[error("compiled graph contains {actual} nodes; maximum is {maximum}")]
1001 TooManyNodes {
1002 maximum: usize,
1004 actual: usize,
1006 },
1007 #[error("compiled graph contains duplicate node {node_id}")]
1009 DuplicateNode {
1010 node_id: NodeId,
1012 },
1013 #[error("compiled graph must contain at least one entry node")]
1015 EmptyEntryNodes,
1016 #[error("compiled graph entry node {node_id} does not exist")]
1018 MissingEntryNode {
1019 node_id: NodeId,
1021 },
1022 #[error("compiled graph node {from_node} references missing successor {target}")]
1024 MissingSuccessorNode {
1025 from_node: NodeId,
1027 target: NodeId,
1029 },
1030 #[error("compiled graph route {route_id} is declared by both {first_node} and {second_node}")]
1032 DuplicateRoute {
1033 route_id: RouteId,
1035 first_node: NodeId,
1037 second_node: NodeId,
1039 },
1040 #[error("compiled graph contains {actual} routes; maximum is {maximum}")]
1042 TooManyRoutes {
1043 maximum: usize,
1045 actual: usize,
1047 },
1048 #[error("compiled graph ready set contains {actual} nodes; graph maximum is {maximum}")]
1050 ParallelismExceeded {
1051 node_id: Option<NodeId>,
1053 maximum: usize,
1055 actual: usize,
1057 },
1058 #[error("compiled graph node {node_id} is unreachable from every entry")]
1060 UnreachableNode {
1061 node_id: NodeId,
1063 },
1064 #[error("compiled graph node {node_id} cannot reach a wait or terminal boundary")]
1066 NoBoundaryPath {
1067 node_id: NodeId,
1069 },
1070 #[error("compiled graph descriptor is {actual} bytes; maximum is {maximum}")]
1072 DefinitionTooLarge {
1073 maximum: usize,
1075 actual: usize,
1077 },
1078 #[error("compiled graph canonical serialization failed")]
1080 CanonicalSerialization,
1081 #[error("compiled graph definition digest does not match its fields")]
1083 DigestMismatch,
1084 #[error(transparent)]
1086 ChildPolicy(#[from] ChildRunPolicyError),
1087}
1088
1089#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
1095#[non_exhaustive]
1096pub enum GraphSchemaValidationError {
1097 #[error("value was rejected by the pinned schema")]
1099 Rejected,
1100 #[error("pinned schema was unavailable")]
1102 Unavailable,
1103}
1104
1105pub trait GraphSchemaValidator: Send + Sync {
1111 fn validate(
1113 &self,
1114 schema: &SchemaReference,
1115 value: &BoundedJson,
1116 ) -> Result<(), GraphSchemaValidationError>;
1117}
1118
1119#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
1121#[non_exhaustive]
1122pub enum GraphReducerError {
1123 #[error("graph reducer rejected the ordered update batch")]
1125 Rejected,
1126 #[error("pinned graph reducer was unavailable")]
1128 Unavailable,
1129 #[error("graph reducer exceeded an enforced resource limit")]
1131 ResourceLimit,
1132}
1133
1134#[derive(Clone, Copy, Debug)]
1136pub struct GraphReducerInput<'a> {
1137 node_id: &'a NodeId,
1138 update: &'a NodeStateUpdate,
1139}
1140
1141impl<'a> GraphReducerInput<'a> {
1142 const fn new(node_id: &'a NodeId, update: &'a NodeStateUpdate) -> Self {
1143 Self { node_id, update }
1144 }
1145
1146 #[must_use]
1148 pub const fn node_id(self) -> &'a NodeId {
1149 self.node_id
1150 }
1151
1152 #[must_use]
1154 pub const fn update(self) -> &'a NodeStateUpdate {
1155 self.update
1156 }
1157}
1158
1159pub trait GraphReducer: Send + Sync {
1167 fn reference(&self) -> &GraphReducerReference;
1169
1170 fn reduce(
1172 &self,
1173 state: &BoundedJson,
1174 updates: &[GraphReducerInput<'_>],
1175 ) -> Result<BoundedJson, GraphReducerError>;
1176}
1177
1178#[derive(Clone, Debug, Eq, PartialEq)]
1180#[non_exhaustive]
1181pub enum GraphBarrierDisposition {
1182 Continue,
1184 Wait {
1186 waits: NodeWaits,
1188 },
1189 Terminal {
1191 output: NodeTerminalOutput,
1193 },
1194}
1195
1196impl GraphBarrierDisposition {
1197 #[must_use]
1199 pub const fn waits(&self) -> Option<&NodeWaits> {
1200 match self {
1201 Self::Wait { waits } => Some(waits),
1202 Self::Continue | Self::Terminal { .. } => None,
1203 }
1204 }
1205
1206 #[must_use]
1208 pub const fn terminal_output(&self) -> Option<&NodeTerminalOutput> {
1209 match self {
1210 Self::Terminal { output } => Some(output),
1211 Self::Continue | Self::Wait { .. } => None,
1212 }
1213 }
1214}
1215
1216#[derive(Clone, Debug, Eq, PartialEq)]
1218pub struct GraphBarrierPlan {
1219 barrier: CheckpointBarrier,
1220 disposition: GraphBarrierDisposition,
1221}
1222
1223impl GraphBarrierPlan {
1224 #[must_use]
1226 pub const fn barrier(&self) -> &CheckpointBarrier {
1227 &self.barrier
1228 }
1229
1230 #[must_use]
1232 pub const fn disposition(&self) -> &GraphBarrierDisposition {
1233 &self.disposition
1234 }
1235
1236 #[must_use]
1238 pub fn into_parts(self) -> (CheckpointBarrier, GraphBarrierDisposition) {
1239 (self.barrier, self.disposition)
1240 }
1241}
1242
1243struct GraphBarrierPlanner<'a, V: ?Sized, R: ?Sized> {
1244 graph: &'a CompiledGraph,
1245 base: &'a Checkpoint,
1246 results: &'a [PendingNodeResult],
1247 successor_id: CheckpointId,
1248 schemas: &'a V,
1249 reducer: &'a R,
1250}
1251
1252impl<'a, V, R> GraphBarrierPlanner<'a, V, R>
1253where
1254 V: GraphSchemaValidator + ?Sized,
1255 R: GraphReducer + ?Sized,
1256{
1257 const fn new(
1258 graph: &'a CompiledGraph,
1259 base: &'a Checkpoint,
1260 results: &'a [PendingNodeResult],
1261 successor_id: CheckpointId,
1262 schemas: &'a V,
1263 reducer: &'a R,
1264 ) -> Self {
1265 Self {
1266 graph,
1267 base,
1268 results,
1269 successor_id,
1270 schemas,
1271 reducer,
1272 }
1273 }
1274
1275 fn plan(self) -> Result<GraphBarrierPlan, GraphBarrierPlanError> {
1276 self.validate_checkpoint()?;
1277 if self.reducer.reference() != self.graph.reducer() {
1278 return Err(GraphBarrierPlanError::ReducerReferenceMismatch);
1279 }
1280 validate_schema(
1281 self.schemas,
1282 self.graph.state_schema(),
1283 self.base.state().data(),
1284 GraphValueKind::BaseState,
1285 None,
1286 )?;
1287
1288 let ordered = self.ordered_results()?;
1289 let resolved = self.resolve_controls(&ordered)?;
1290 let state = self.reduce_state(&resolved.reducer_inputs)?;
1291 let successor =
1292 CheckpointWrite::successor(self.successor_id, self.base, state, resolved.ready_nodes)
1293 .map_err(|source| GraphBarrierPlanError::InvalidSuccessor { source })?;
1294 let heads = ordered.iter().map(|result| result.head());
1295 let barrier = CheckpointBarrier::new(self.base, successor, heads)
1296 .map_err(|source| GraphBarrierPlanError::InvalidBarrier { source })?;
1297 Ok(GraphBarrierPlan {
1298 barrier,
1299 disposition: resolved.disposition,
1300 })
1301 }
1302
1303 fn resolve_controls(
1304 &self,
1305 ordered: &[&'a PendingNodeResult],
1306 ) -> Result<ResolvedControls<'a>, GraphBarrierPlanError> {
1307 let mut reducer_inputs = Vec::with_capacity(ordered.len());
1308 let mut next_nodes = BTreeSet::new();
1309 let mut waits = Vec::<NodeWait>::new();
1310 let mut terminal = None;
1311
1312 for result in ordered {
1313 let intent = result.intent();
1314 let node_id = intent.activation().node_id();
1315 let node = self.graph.node(node_id).ok_or_else(|| {
1316 GraphBarrierPlanError::UnknownReadyNode {
1317 node_id: node_id.clone(),
1318 }
1319 })?;
1320 if let Some(update) = intent.state_change().update() {
1321 if update.schema() != self.graph.update_schema() {
1322 return Err(GraphBarrierPlanError::UpdateSchemaMismatch {
1323 node_id: node_id.clone(),
1324 });
1325 }
1326 validate_schema(
1327 self.schemas,
1328 update.schema(),
1329 update.data(),
1330 GraphValueKind::NodeUpdate,
1331 Some(node_id),
1332 )?;
1333 reducer_inputs.push(GraphReducerInput::new(node_id, update));
1334 }
1335
1336 match intent.control() {
1337 NodeControl::Continue => {
1338 let successors = node.continue_to().ok_or_else(|| {
1339 GraphBarrierPlanError::UndeclaredControl {
1340 node_id: node_id.clone(),
1341 control: NodeControlKind::Continue,
1342 }
1343 })?;
1344 next_nodes.extend(successors.iter().cloned());
1345 }
1346 NodeControl::Route { route_id } => {
1347 let route = node.routes().get(route_id).ok_or_else(|| {
1348 GraphBarrierPlanError::UndeclaredRoute {
1349 node_id: node_id.clone(),
1350 route_id: route_id.clone(),
1351 }
1352 })?;
1353 next_nodes.extend(route.successors().iter().cloned());
1354 }
1355 NodeControl::Wait { waits: node_waits } => {
1356 let successors =
1357 node.wait_to()
1358 .ok_or_else(|| GraphBarrierPlanError::UndeclaredControl {
1359 node_id: node_id.clone(),
1360 control: NodeControlKind::Wait,
1361 })?;
1362 next_nodes.extend(successors.iter().cloned());
1363 waits.extend(node_waits.iter().cloned());
1364 }
1365 NodeControl::Terminal { output } => {
1366 if !node.allows_terminal() {
1367 return Err(GraphBarrierPlanError::UndeclaredControl {
1368 node_id: node_id.clone(),
1369 control: NodeControlKind::Terminal,
1370 });
1371 }
1372 if output.schema() != self.graph.output_schema() {
1373 return Err(GraphBarrierPlanError::TerminalOutputSchemaMismatch {
1374 node_id: node_id.clone(),
1375 });
1376 }
1377 validate_schema(
1378 self.schemas,
1379 output.schema(),
1380 output.data(),
1381 GraphValueKind::TerminalOutput,
1382 Some(node_id),
1383 )?;
1384 if terminal.replace(output.clone()).is_some() {
1385 return Err(GraphBarrierPlanError::TerminalNotExclusive);
1386 }
1387 }
1388 }
1389 }
1390
1391 let disposition = resolve_disposition(ordered.len(), &next_nodes, waits, terminal)?;
1392 if next_nodes.len() > usize::from(self.graph.limits.maximum_parallelism) {
1393 return Err(GraphBarrierPlanError::SuccessorParallelismExceeded {
1394 maximum: usize::from(self.graph.limits.maximum_parallelism),
1395 actual: next_nodes.len(),
1396 });
1397 }
1398 let ready_nodes = ReadyNodes::try_new(next_nodes).map_err(|_| {
1399 GraphBarrierPlanError::SuccessorParallelismExceeded {
1400 maximum: ReadyNodes::MAX_LEN,
1401 actual: ReadyNodes::MAX_LEN + 1,
1402 }
1403 })?;
1404 Ok(ResolvedControls {
1405 reducer_inputs,
1406 ready_nodes,
1407 disposition,
1408 })
1409 }
1410
1411 fn reduce_state(
1412 &self,
1413 reducer_inputs: &[GraphReducerInput<'_>],
1414 ) -> Result<CheckpointState, GraphBarrierPlanError> {
1415 let reduced = if reducer_inputs.is_empty() {
1416 self.base.state().data().clone()
1417 } else {
1418 catch_unwind(AssertUnwindSafe(|| {
1419 self.reducer
1420 .reduce(self.base.state().data(), reducer_inputs)
1421 }))
1422 .map_err(|_| GraphBarrierPlanError::ReducerPanicked)?
1423 .map_err(|source| GraphBarrierPlanError::ReducerFailed { source })?
1424 };
1425 validate_schema(
1426 self.schemas,
1427 self.graph.state_schema(),
1428 &reduced,
1429 GraphValueKind::ReducedState,
1430 None,
1431 )?;
1432 CheckpointState::new(self.graph.state_schema().clone(), reduced)
1433 .map_err(|source| GraphBarrierPlanError::InvalidReducedState { source })
1434 }
1435
1436 fn validate_checkpoint(&self) -> Result<(), GraphBarrierPlanError> {
1437 if self.base.graph() != &self.graph.reference() {
1438 return Err(GraphBarrierPlanError::GraphReferenceMismatch);
1439 }
1440 if self.base.superstep() == Superstep::INITIAL
1441 && self.base.ready_nodes() != self.graph.entry_nodes()
1442 {
1443 return Err(GraphBarrierPlanError::InitialReadySetMismatch);
1444 }
1445 if self.base.superstep().get() >= self.graph.limits.maximum_supersteps.get() {
1446 return Err(GraphBarrierPlanError::SuperstepLimitReached {
1447 maximum: self.graph.limits.maximum_supersteps,
1448 actual: self.base.superstep(),
1449 });
1450 }
1451 if self.base.ready_nodes().len() > usize::from(self.graph.limits.maximum_parallelism) {
1452 return Err(GraphBarrierPlanError::BaseParallelismExceeded {
1453 maximum: usize::from(self.graph.limits.maximum_parallelism),
1454 actual: self.base.ready_nodes().len(),
1455 });
1456 }
1457 for node_id in self.base.ready_nodes() {
1458 if self.graph.node(node_id).is_none() {
1459 return Err(GraphBarrierPlanError::UnknownReadyNode {
1460 node_id: node_id.clone(),
1461 });
1462 }
1463 }
1464 Ok(())
1465 }
1466
1467 fn ordered_results(&self) -> Result<Vec<&PendingNodeResult>, GraphBarrierPlanError> {
1468 if self.results.len() != self.base.ready_nodes().len() {
1469 return Err(GraphBarrierPlanError::ResultCountMismatch {
1470 expected: self.base.ready_nodes().len(),
1471 actual: self.results.len(),
1472 });
1473 }
1474 let mut ordered = BTreeMap::new();
1475 for result in self.results {
1476 let activation = result.intent().activation();
1477 if activation.base_checkpoint() != &self.base.head() {
1478 return Err(GraphBarrierPlanError::ResultBaseMismatch {
1479 node_id: activation.node_id().clone(),
1480 });
1481 }
1482 if !activation.graph_namespace().is_root() {
1483 return Err(GraphBarrierPlanError::NonRootActivation {
1484 node_id: activation.node_id().clone(),
1485 });
1486 }
1487 let expected = NodeActivation::for_ready_root(self.base, activation.node_id().clone())
1488 .map_err(|_| GraphBarrierPlanError::ActivationMismatch {
1489 node_id: activation.node_id().clone(),
1490 })?;
1491 if activation != &expected {
1492 return Err(GraphBarrierPlanError::ActivationMismatch {
1493 node_id: activation.node_id().clone(),
1494 });
1495 }
1496 if ordered
1497 .insert(activation.node_id().clone(), result)
1498 .is_some()
1499 {
1500 return Err(GraphBarrierPlanError::DuplicateResultNode {
1501 node_id: activation.node_id().clone(),
1502 });
1503 }
1504 }
1505 for node_id in self.base.ready_nodes() {
1506 if !ordered.contains_key(node_id) {
1507 return Err(GraphBarrierPlanError::MissingResultNode {
1508 node_id: node_id.clone(),
1509 });
1510 }
1511 }
1512 Ok(ordered.into_values().collect())
1513 }
1514}
1515
1516struct ResolvedControls<'a> {
1517 reducer_inputs: Vec<GraphReducerInput<'a>>,
1518 ready_nodes: ReadyNodes,
1519 disposition: GraphBarrierDisposition,
1520}
1521
1522fn resolve_disposition(
1523 result_count: usize,
1524 next_nodes: &BTreeSet<NodeId>,
1525 waits: Vec<NodeWait>,
1526 terminal: Option<NodeTerminalOutput>,
1527) -> Result<GraphBarrierDisposition, GraphBarrierPlanError> {
1528 if let Some(output) = terminal {
1529 if result_count != 1 || !waits.is_empty() || !next_nodes.is_empty() {
1530 return Err(GraphBarrierPlanError::TerminalNotExclusive);
1531 }
1532 return Ok(GraphBarrierDisposition::Terminal { output });
1533 }
1534 if waits.is_empty() {
1535 if next_nodes.is_empty() {
1536 return Err(GraphBarrierPlanError::AdvancingBarrierWithoutSuccessor);
1537 }
1538 return Ok(GraphBarrierDisposition::Continue);
1539 }
1540 NodeWaits::try_new(waits)
1541 .map(|waits| GraphBarrierDisposition::Wait { waits })
1542 .map_err(|source| GraphBarrierPlanError::InvalidWaitBatch { source })
1543}
1544
1545fn validate_schema<V>(
1546 schemas: &V,
1547 schema: &SchemaReference,
1548 value: &BoundedJson,
1549 kind: GraphValueKind,
1550 node_id: Option<&NodeId>,
1551) -> Result<(), GraphBarrierPlanError>
1552where
1553 V: GraphSchemaValidator + ?Sized,
1554{
1555 match catch_unwind(AssertUnwindSafe(|| schemas.validate(schema, value))) {
1556 Ok(Ok(())) => Ok(()),
1557 Ok(Err(source)) => Err(GraphBarrierPlanError::SchemaValidation {
1558 kind,
1559 node_id: node_id.cloned(),
1560 source,
1561 }),
1562 Err(_) => Err(GraphBarrierPlanError::SchemaValidatorPanicked {
1563 kind,
1564 node_id: node_id.cloned(),
1565 }),
1566 }
1567}
1568
1569#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1571#[non_exhaustive]
1572pub enum GraphValueKind {
1573 BaseState,
1575 NodeUpdate,
1577 TerminalOutput,
1579 ReducedState,
1581}
1582
1583impl fmt::Display for GraphValueKind {
1584 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
1585 formatter.write_str(match self {
1586 Self::BaseState => "base state",
1587 Self::NodeUpdate => "node update",
1588 Self::TerminalOutput => "terminal output",
1589 Self::ReducedState => "reduced state",
1590 })
1591 }
1592}
1593
1594#[derive(Clone, Debug, Eq, Error, PartialEq)]
1596#[non_exhaustive]
1597pub enum GraphBarrierPlanError {
1598 #[error("checkpoint graph reference does not match the compiled graph")]
1600 GraphReferenceMismatch,
1601 #[error("initial checkpoint ready set does not match compiled graph entries")]
1603 InitialReadySetMismatch,
1604 #[error("graph superstep limit {maximum} was reached at checkpoint {actual}")]
1606 SuperstepLimitReached {
1607 maximum: Superstep,
1609 actual: Superstep,
1611 },
1612 #[error("base checkpoint has {actual} ready nodes; graph maximum is {maximum}")]
1614 BaseParallelismExceeded {
1615 maximum: usize,
1617 actual: usize,
1619 },
1620 #[error("base checkpoint contains unknown ready node {node_id}")]
1622 UnknownReadyNode {
1623 node_id: NodeId,
1625 },
1626 #[error("loaded reducer does not match the compiled graph reference")]
1628 ReducerReferenceMismatch,
1629 #[error("barrier contains {actual} results; expected {expected}")]
1631 ResultCountMismatch {
1632 expected: usize,
1634 actual: usize,
1636 },
1637 #[error("barrier contains duplicate result node {node_id}")]
1639 DuplicateResultNode {
1640 node_id: NodeId,
1642 },
1643 #[error("barrier is missing result node {node_id}")]
1645 MissingResultNode {
1646 node_id: NodeId,
1648 },
1649 #[error("result for node {node_id} does not belong to the base checkpoint")]
1651 ResultBaseMismatch {
1652 node_id: NodeId,
1654 },
1655 #[error("result for node {node_id} belongs to a non-root graph namespace")]
1657 NonRootActivation {
1658 node_id: NodeId,
1660 },
1661 #[error("result activation for node {node_id} does not match the base checkpoint")]
1663 ActivationMismatch {
1664 node_id: NodeId,
1666 },
1667 #[error("node {node_id} update schema does not match the compiled graph")]
1669 UpdateSchemaMismatch {
1670 node_id: NodeId,
1672 },
1673 #[error("node {node_id} terminal output schema does not match the compiled graph")]
1675 TerminalOutputSchemaMismatch {
1676 node_id: NodeId,
1678 },
1679 #[error("graph {kind} schema validation failed")]
1681 SchemaValidation {
1682 kind: GraphValueKind,
1684 node_id: Option<NodeId>,
1686 #[source]
1688 source: GraphSchemaValidationError,
1689 },
1690 #[error("graph {kind} schema validator panicked")]
1692 SchemaValidatorPanicked {
1693 kind: GraphValueKind,
1695 node_id: Option<NodeId>,
1697 },
1698 #[error("node {node_id} selected undeclared {control:?} control")]
1700 UndeclaredControl {
1701 node_id: NodeId,
1703 control: NodeControlKind,
1705 },
1706 #[error("node {node_id} selected undeclared route {route_id}")]
1708 UndeclaredRoute {
1709 node_id: NodeId,
1711 route_id: RouteId,
1713 },
1714 #[error("terminal graph result must be the only activation in its barrier")]
1716 TerminalNotExclusive,
1717 #[error("non-terminal graph barrier must produce at least one successor")]
1719 AdvancingBarrierWithoutSuccessor,
1720 #[error("successor contains {actual} ready nodes; graph maximum is {maximum}")]
1722 SuccessorParallelismExceeded {
1723 maximum: usize,
1725 actual: usize,
1727 },
1728 #[error("graph wait controls do not form one valid batch: {source}")]
1730 InvalidWaitBatch {
1731 #[source]
1733 source: NodeWaitsError,
1734 },
1735 #[error("graph reducer failed: {source}")]
1737 ReducerFailed {
1738 #[source]
1740 source: GraphReducerError,
1741 },
1742 #[error("graph reducer panicked")]
1744 ReducerPanicked,
1745 #[error("reduced graph state is invalid: {source}")]
1747 InvalidReducedState {
1748 #[source]
1750 source: CheckpointStateError,
1751 },
1752 #[error("derived graph successor is invalid: {source}")]
1754 InvalidSuccessor {
1755 #[source]
1757 source: CheckpointWriteError,
1758 },
1759 #[error("derived graph barrier is invalid: {source}")]
1761 InvalidBarrier {
1762 #[source]
1764 source: CheckpointBarrierError,
1765 },
1766}
1767
1768#[cfg(test)]
1769mod tests {
1770 use super::*;
1771 use crate::{
1772 AttemptId, CapabilityName, CapabilityReference, EventId, FencingEpoch, IssuerId,
1773 JournalHead, JournalSequence, JsonLimits, NodeInvocationBindings, NodeStateChange,
1774 PendingNodeResultIntent, PrincipalIdentity, RunFence, RunId, RunTimerKind, SchemaId,
1775 SubjectId, TenantId, TimerId, Timestamp, Version,
1776 };
1777 use proptest::prelude::*;
1778 use serde_json::{Value, from_value, json, to_value};
1779
1780 fn identity(name: &str) -> CapabilityIdentity {
1781 CapabilityIdentity::new(
1782 PrincipalIdentity::new(
1783 "https://issuer.example.com/stateknot"
1784 .parse::<IssuerId>()
1785 .unwrap(),
1786 "graph-registry".parse::<SubjectId>().unwrap(),
1787 ),
1788 CapabilityReference::new(
1789 name.parse::<CapabilityName>().unwrap(),
1790 Version::new(1, 0, 0),
1791 ),
1792 )
1793 }
1794
1795 fn schema(name: &str) -> SchemaReference {
1796 SchemaReference::new(
1797 format!("https://schemas.example.com/{name}")
1798 .parse::<SchemaId>()
1799 .unwrap(),
1800 Version::new(1, 0, 0),
1801 Digest::sha256(name),
1802 )
1803 }
1804
1805 fn node_ids(values: &[&str]) -> ReadyNodes {
1806 ReadyNodes::try_new(values.iter().map(|value| NodeId::new(*value).unwrap())).unwrap()
1807 }
1808
1809 fn route(route_id: &str, successors: &[&str]) -> GraphRoute {
1810 GraphRoute::new(RouteId::new(route_id).unwrap(), node_ids(successors)).unwrap()
1811 }
1812
1813 fn node(
1814 node_id: &str,
1815 continue_to: Option<&[&str]>,
1816 routes: Vec<GraphRoute>,
1817 wait_to: Option<&[&str]>,
1818 terminal: bool,
1819 ) -> GraphNode {
1820 GraphNode::new(
1821 NodeId::new(node_id).unwrap(),
1822 continue_to.map(node_ids),
1823 GraphRoutes::try_new(routes).unwrap(),
1824 wait_to.map(node_ids),
1825 terminal,
1826 )
1827 .unwrap()
1828 }
1829
1830 fn limits(maximum_parallelism: u16) -> GraphExecutionLimits {
1831 GraphExecutionLimits::new(Superstep::new(64).unwrap(), maximum_parallelism).unwrap()
1832 }
1833
1834 fn parallel_graph() -> CompiledGraph {
1835 CompiledGraph::compile(
1836 identity("orders.graph"),
1837 schema("input"),
1838 schema("state"),
1839 schema("update"),
1840 schema("output"),
1841 GraphReducerReference::new(identity("orders.reducer"), Digest::sha256(b"reducer-v1")),
1842 node_ids(&["alpha", "beta"]),
1843 [
1844 node("join", None, Vec::new(), None, true),
1845 node("beta", None, vec![route("beta.ok", &["join"])], None, false),
1846 node("alpha", Some(&["join"]), Vec::new(), None, false),
1847 ],
1848 limits(4),
1849 )
1850 .unwrap()
1851 }
1852
1853 fn parallel_four_graph() -> CompiledGraph {
1854 CompiledGraph::compile(
1855 identity("parallel-four.graph"),
1856 schema("parallel-four-input"),
1857 schema("parallel-four-state"),
1858 schema("parallel-four-update"),
1859 schema("parallel-four-output"),
1860 GraphReducerReference::new(
1861 identity("parallel-four.reducer"),
1862 Digest::sha256(b"parallel-four-reducer-v1"),
1863 ),
1864 node_ids(&["alpha", "beta", "delta", "gamma"]),
1865 [
1866 node("join", None, Vec::new(), None, true),
1867 node("alpha", Some(&["join"]), Vec::new(), None, false),
1868 node("beta", Some(&["join"]), Vec::new(), None, false),
1869 node("delta", Some(&["join"]), Vec::new(), None, false),
1870 node("gamma", Some(&["join"]), Vec::new(), None, false),
1871 ],
1872 limits(4),
1873 )
1874 .unwrap()
1875 }
1876
1877 fn tenant() -> TenantId {
1878 TenantId::new("tenant-graph-test").unwrap()
1879 }
1880
1881 fn run_id() -> RunId {
1882 "01912345-6789-7abc-8def-0123456789a1".parse().unwrap()
1883 }
1884
1885 fn timestamp(offset: i64) -> Timestamp {
1886 let base = "2030-01-01T00:00:00.000000Z".parse::<Timestamp>().unwrap();
1887 Timestamp::from_unix_micros(base.unix_micros() + offset * 1_000_000).unwrap()
1888 }
1889
1890 fn journal(sequence: u64) -> JournalHead {
1891 JournalHead::new(
1892 tenant(),
1893 run_id(),
1894 JournalSequence::new(sequence).unwrap(),
1895 format!("01912345-6789-7abc-8def-0123456789{sequence:02x}")
1896 .parse::<EventId>()
1897 .unwrap(),
1898 timestamp(i64::try_from(sequence).unwrap()),
1899 Digest::sha256(sequence.to_be_bytes()),
1900 )
1901 }
1902
1903 fn checkpoint_id(suffix: &str) -> CheckpointId {
1904 format!("01912345-6789-7abc-8def-0123456788{suffix}")
1905 .parse()
1906 .unwrap()
1907 }
1908
1909 fn checkpoint(graph: &CompiledGraph) -> Checkpoint {
1910 let state = CheckpointState::new(
1911 graph.state_schema().clone(),
1912 BoundedJson::try_from_value_with_limits(json!({"order": []}), JsonLimits::MAXIMUM)
1913 .unwrap(),
1914 )
1915 .unwrap();
1916 let write = CheckpointWrite::initial(
1917 tenant(),
1918 run_id(),
1919 checkpoint_id("a1"),
1920 graph.reference(),
1921 state,
1922 graph.entry_nodes().clone(),
1923 )
1924 .unwrap();
1925 Checkpoint::commit(write, journal(1)).unwrap()
1926 }
1927
1928 fn result(
1929 graph: &CompiledGraph,
1930 base: &Checkpoint,
1931 node_name: &str,
1932 sequence: u64,
1933 control: NodeControl,
1934 ) -> PendingNodeResult {
1935 let node_id = NodeId::new(node_name).unwrap();
1936 let activation = NodeActivation::for_ready_root(base, node_id).unwrap();
1937 let update = NodeStateUpdate::new(
1938 graph.update_schema().clone(),
1939 BoundedJson::try_from_value_with_limits(
1940 json!({"value": node_name}),
1941 JsonLimits::MAXIMUM,
1942 )
1943 .unwrap(),
1944 )
1945 .unwrap();
1946 let intent = PendingNodeResultIntent::new(
1947 activation.clone(),
1948 NodeStateChange::Update { update },
1949 control,
1950 NodeInvocationBindings::empty(),
1951 )
1952 .unwrap();
1953 PendingNodeResult::commit(
1954 intent,
1955 RunFence::new(
1956 tenant(),
1957 run_id(),
1958 format!("01912345-6789-7abc-8def-0123456787{sequence:02x}")
1959 .parse::<AttemptId>()
1960 .unwrap(),
1961 FencingEpoch::new(sequence).unwrap(),
1962 ),
1963 journal(sequence + 1),
1964 )
1965 .unwrap()
1966 }
1967
1968 struct AcceptSchemas;
1969
1970 impl GraphSchemaValidator for AcceptSchemas {
1971 fn validate(
1972 &self,
1973 _schema: &SchemaReference,
1974 _value: &BoundedJson,
1975 ) -> Result<(), GraphSchemaValidationError> {
1976 Ok(())
1977 }
1978 }
1979
1980 struct StableReducer {
1981 reference: GraphReducerReference,
1982 }
1983
1984 impl GraphReducer for StableReducer {
1985 fn reference(&self) -> &GraphReducerReference {
1986 &self.reference
1987 }
1988
1989 fn reduce(
1990 &self,
1991 _state: &BoundedJson,
1992 updates: &[GraphReducerInput<'_>],
1993 ) -> Result<BoundedJson, GraphReducerError> {
1994 BoundedJson::try_from_value_with_limits(
1995 json!({
1996 "order": updates
1997 .iter()
1998 .map(|input| input.node_id().as_str())
1999 .collect::<Vec<_>>()
2000 }),
2001 JsonLimits::MAXIMUM,
2002 )
2003 .map_err(|_| GraphReducerError::ResourceLimit)
2004 }
2005 }
2006
2007 #[test]
2008 fn compilation_is_canonical_reachable_and_integrity_bound() {
2009 let forward = parallel_graph();
2010 let reverse = CompiledGraph::compile(
2011 forward.identity().clone(),
2012 forward.input_schema().clone(),
2013 forward.state_schema().clone(),
2014 forward.update_schema().clone(),
2015 forward.output_schema().clone(),
2016 forward.reducer().clone(),
2017 forward.entry_nodes().clone(),
2018 forward.nodes().iter().cloned().rev(),
2019 forward.limits(),
2020 )
2021 .unwrap();
2022 assert_eq!(forward, reverse);
2023 assert_eq!(
2024 forward.canonical_definition_bytes().unwrap(),
2025 reverse.canonical_definition_bytes().unwrap()
2026 );
2027 assert_eq!(
2028 forward.definition_digest(),
2029 Digest::sha256(forward.canonical_definition_bytes().unwrap())
2030 );
2031 assert_eq!(
2032 from_value::<CompiledGraph>(to_value(&forward).unwrap()).unwrap(),
2033 forward
2034 );
2035 assert_eq!(
2036 forward.reference().definition_digest(),
2037 forward.definition_digest()
2038 );
2039 assert!(forward.nodes().iter().map(GraphNode::node_id).is_sorted());
2040
2041 let mut tampered = to_value(&forward).unwrap();
2042 tampered["nodes"][2]["terminal"] = json!(false);
2043 assert!(from_value::<CompiledGraph>(tampered).is_err());
2044 }
2045
2046 #[test]
2047 fn compilation_rejects_missing_unreachable_nonterminating_and_duplicate_routes() {
2048 let compile = |nodes: Vec<GraphNode>| {
2049 CompiledGraph::compile(
2050 identity("invalid.graph"),
2051 schema("input"),
2052 schema("state"),
2053 schema("update"),
2054 schema("output"),
2055 GraphReducerReference::new(
2056 identity("invalid.reducer"),
2057 Digest::sha256(b"invalid-reducer"),
2058 ),
2059 node_ids(&["entry"]),
2060 nodes,
2061 limits(8),
2062 )
2063 };
2064
2065 assert!(matches!(
2066 compile(vec![node(
2067 "entry",
2068 Some(&["missing"]),
2069 Vec::new(),
2070 None,
2071 false
2072 )]),
2073 Err(GraphCompileError::MissingSuccessorNode { .. })
2074 ));
2075 assert!(matches!(
2076 compile(vec![
2077 node("entry", None, Vec::new(), None, true),
2078 node("orphan", None, Vec::new(), None, true),
2079 ]),
2080 Err(GraphCompileError::UnreachableNode { .. })
2081 ));
2082 assert!(matches!(
2083 compile(vec![node(
2084 "entry",
2085 Some(&["entry"]),
2086 Vec::new(),
2087 None,
2088 false
2089 )]),
2090 Err(GraphCompileError::NoBoundaryPath { .. })
2091 ));
2092 assert!(matches!(
2093 compile(vec![
2094 node("entry", None, vec![route("same", &["second"])], None, true,),
2095 node("second", None, vec![route("same", &["entry"])], None, true,),
2096 ]),
2097 Err(GraphCompileError::DuplicateRoute { .. })
2098 ));
2099 }
2100
2101 #[test]
2102 fn parallel_reduction_and_routing_ignore_completion_order() {
2103 let graph = parallel_graph();
2104 let base = checkpoint(&graph);
2105 let alpha = result(&graph, &base, "alpha", 2, NodeControl::Continue);
2106 let beta = result(
2107 &graph,
2108 &base,
2109 "beta",
2110 3,
2111 NodeControl::Route {
2112 route_id: RouteId::new("beta.ok").unwrap(),
2113 },
2114 );
2115 let reducer = StableReducer {
2116 reference: graph.reducer().clone(),
2117 };
2118 let successor_id = checkpoint_id("a2");
2119 let forward = graph
2120 .plan_barrier(
2121 &base,
2122 &[alpha.clone(), beta.clone()],
2123 successor_id,
2124 &AcceptSchemas,
2125 &reducer,
2126 )
2127 .unwrap();
2128 let reverse = graph
2129 .plan_barrier(
2130 &base,
2131 &[beta, alpha],
2132 successor_id,
2133 &AcceptSchemas,
2134 &reducer,
2135 )
2136 .unwrap();
2137
2138 assert_eq!(forward, reverse);
2139 assert_eq!(forward.disposition(), &GraphBarrierDisposition::Continue);
2140 assert_eq!(
2141 forward.barrier().successor().ready_nodes(),
2142 &node_ids(&["join"])
2143 );
2144 assert_eq!(
2145 forward.barrier().successor().state().data().as_value(),
2146 &json!({"order": ["alpha", "beta"]})
2147 );
2148 assert!(
2149 forward
2150 .barrier()
2151 .result_heads()
2152 .iter()
2153 .map(|head| head.activation().node_id())
2154 .is_sorted()
2155 );
2156 }
2157
2158 proptest! {
2159 #![proptest_config(ProptestConfig::with_cases(64))]
2160
2161 #[test]
2162 fn every_parallel_completion_permutation_produces_the_same_barrier(
2163 ordering_keys in proptest::collection::vec(any::<u32>(), 4),
2164 ) {
2165 let graph = parallel_four_graph();
2166 let base = checkpoint(&graph);
2167 let results = [
2168 result(&graph, &base, "alpha", 2, NodeControl::Continue),
2169 result(&graph, &base, "beta", 3, NodeControl::Continue),
2170 result(&graph, &base, "delta", 4, NodeControl::Continue),
2171 result(&graph, &base, "gamma", 5, NodeControl::Continue),
2172 ];
2173 let reducer = StableReducer {
2174 reference: graph.reducer().clone(),
2175 };
2176 let successor_id = checkpoint_id("a4");
2177 let expected = graph
2178 .plan_barrier(
2179 &base,
2180 &results,
2181 successor_id,
2182 &AcceptSchemas,
2183 &reducer,
2184 )
2185 .unwrap();
2186 let mut indices = [0_usize, 1, 2, 3];
2187 indices.sort_unstable_by_key(|index| (ordering_keys[*index], *index));
2188 let permuted = indices
2189 .into_iter()
2190 .map(|index| results[index].clone())
2191 .collect::<Vec<_>>();
2192 let actual = graph
2193 .plan_barrier(
2194 &base,
2195 &permuted,
2196 successor_id,
2197 &AcceptSchemas,
2198 &reducer,
2199 )
2200 .unwrap();
2201
2202 prop_assert_eq!(actual, expected);
2203 }
2204 }
2205
2206 fn wait_graph() -> CompiledGraph {
2207 CompiledGraph::compile(
2208 identity("wait.graph"),
2209 schema("wait-input"),
2210 schema("wait-state"),
2211 schema("wait-update"),
2212 schema("wait-output"),
2213 GraphReducerReference::new(identity("wait.reducer"), Digest::sha256(b"wait-reducer")),
2214 node_ids(&["sleep-a", "sleep-b"]),
2215 [
2216 node("done", None, Vec::new(), None, true),
2217 node("sleep-a", None, Vec::new(), Some(&["done"]), false),
2218 node("sleep-b", None, Vec::new(), Some(&["done"]), false),
2219 ],
2220 limits(4),
2221 )
2222 .unwrap()
2223 }
2224
2225 fn timer_wait(suffix: &str) -> NodeWaits {
2226 NodeWaits::try_new([NodeWait::timer(
2227 format!("01912345-6789-7abc-8def-0123456786{suffix}")
2228 .parse::<TimerId>()
2229 .unwrap(),
2230 RunTimerKind::Sleep,
2231 timestamp(10),
2232 )])
2233 .unwrap()
2234 }
2235
2236 #[test]
2237 fn parallel_waits_form_one_batch_and_retain_declared_resume_successors() {
2238 let graph = wait_graph();
2239 let base = checkpoint(&graph);
2240 let a = result(
2241 &graph,
2242 &base,
2243 "sleep-a",
2244 2,
2245 NodeControl::Wait {
2246 waits: timer_wait("a1"),
2247 },
2248 );
2249 let b = result(
2250 &graph,
2251 &base,
2252 "sleep-b",
2253 3,
2254 NodeControl::Wait {
2255 waits: timer_wait("a2"),
2256 },
2257 );
2258 let reducer = StableReducer {
2259 reference: graph.reducer().clone(),
2260 };
2261 let plan = graph
2262 .plan_barrier(
2263 &base,
2264 &[b, a],
2265 checkpoint_id("a3"),
2266 &AcceptSchemas,
2267 &reducer,
2268 )
2269 .unwrap();
2270
2271 assert_eq!(plan.disposition().waits().unwrap().len(), 2);
2272 assert_eq!(
2273 plan.barrier().successor().ready_nodes(),
2274 &node_ids(&["done"])
2275 );
2276 }
2277
2278 #[test]
2279 fn terminal_control_is_schema_checked_and_exclusive() {
2280 let graph = CompiledGraph::compile(
2281 identity("terminal.graph"),
2282 schema("terminal-input"),
2283 schema("terminal-state"),
2284 schema("terminal-update"),
2285 schema("terminal-output"),
2286 GraphReducerReference::new(
2287 identity("terminal.reducer"),
2288 Digest::sha256(b"terminal-reducer"),
2289 ),
2290 node_ids(&["finish"]),
2291 [node("finish", None, Vec::new(), None, true)],
2292 limits(1),
2293 )
2294 .unwrap();
2295 let base = checkpoint(&graph);
2296 let output = NodeTerminalOutput::new(
2297 graph.output_schema().clone(),
2298 BoundedJson::try_from_value_with_limits(json!({"ok": true}), JsonLimits::MAXIMUM)
2299 .unwrap(),
2300 )
2301 .unwrap();
2302 let finished = result(
2303 &graph,
2304 &base,
2305 "finish",
2306 2,
2307 NodeControl::Terminal {
2308 output: output.clone(),
2309 },
2310 );
2311 let reducer = StableReducer {
2312 reference: graph.reducer().clone(),
2313 };
2314 let plan = graph
2315 .plan_barrier(
2316 &base,
2317 &[finished],
2318 checkpoint_id("a4"),
2319 &AcceptSchemas,
2320 &reducer,
2321 )
2322 .unwrap();
2323 assert_eq!(plan.disposition().terminal_output(), Some(&output));
2324 assert!(plan.barrier().successor().ready_nodes().is_empty());
2325
2326 let wrong_reducer = StableReducer {
2327 reference: GraphReducerReference::new(
2328 identity("other.reducer"),
2329 Digest::sha256(b"other"),
2330 ),
2331 };
2332 assert_eq!(
2333 graph.plan_barrier(
2334 &base,
2335 &[],
2336 checkpoint_id("a5"),
2337 &AcceptSchemas,
2338 &wrong_reducer,
2339 ),
2340 Err(GraphBarrierPlanError::ReducerReferenceMismatch)
2341 );
2342 }
2343
2344 #[test]
2345 fn schema_and_reducer_panics_fail_closed() {
2346 struct PanicSchemas;
2347 impl GraphSchemaValidator for PanicSchemas {
2348 fn validate(
2349 &self,
2350 _schema: &SchemaReference,
2351 _value: &BoundedJson,
2352 ) -> Result<(), GraphSchemaValidationError> {
2353 panic!("schema adapter bug")
2354 }
2355 }
2356 struct PanicReducer {
2357 reference: GraphReducerReference,
2358 }
2359 impl GraphReducer for PanicReducer {
2360 fn reference(&self) -> &GraphReducerReference {
2361 &self.reference
2362 }
2363
2364 fn reduce(
2365 &self,
2366 _state: &BoundedJson,
2367 _updates: &[GraphReducerInput<'_>],
2368 ) -> Result<BoundedJson, GraphReducerError> {
2369 panic!("reducer bug")
2370 }
2371 }
2372
2373 let graph = parallel_graph();
2374 let base = checkpoint(&graph);
2375 let alpha = result(&graph, &base, "alpha", 2, NodeControl::Continue);
2376 let beta = result(
2377 &graph,
2378 &base,
2379 "beta",
2380 3,
2381 NodeControl::Route {
2382 route_id: RouteId::new("beta.ok").unwrap(),
2383 },
2384 );
2385 let stable = StableReducer {
2386 reference: graph.reducer().clone(),
2387 };
2388 assert!(matches!(
2389 graph.plan_barrier(
2390 &base,
2391 &[alpha.clone(), beta.clone()],
2392 checkpoint_id("b1"),
2393 &PanicSchemas,
2394 &stable,
2395 ),
2396 Err(GraphBarrierPlanError::SchemaValidatorPanicked { .. })
2397 ));
2398 let panicking = PanicReducer {
2399 reference: graph.reducer().clone(),
2400 };
2401 assert_eq!(
2402 graph.plan_barrier(
2403 &base,
2404 &[alpha, beta],
2405 checkpoint_id("b2"),
2406 &AcceptSchemas,
2407 &panicking,
2408 ),
2409 Err(GraphBarrierPlanError::ReducerPanicked)
2410 );
2411 }
2412
2413 #[test]
2414 fn graph_schemas_are_closed_and_publish_collection_bounds() {
2415 let graph_schema = to_value(schemars::schema_for!(CompiledGraph)).unwrap();
2416 assert_eq!(graph_schema["additionalProperties"], Value::Bool(false));
2417 assert_eq!(
2418 graph_schema["properties"]["nodes"]["maxItems"],
2419 json!(CompiledGraph::MAX_NODES)
2420 );
2421 let routes_schema = to_value(schemars::schema_for!(GraphRoutes)).unwrap();
2422 assert_eq!(routes_schema["maxItems"], json!(GraphRoutes::MAX_LEN));
2423 }
2424}