Skip to main content

stateknot_core/
graph.rs

1// Copyright 2026 StateKnot contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Canonical graph definitions and deterministic superstep planning.
5//!
6//! A compiled graph is declarative, bounded, schema-pinned, and independent of
7//! executable Rust code. Its digest is computed from canonical descriptor
8//! bytes and is the exact value retained by checkpoints. Barrier planning then
9//! verifies complete pending results, validates every typed value, invokes one
10//! exactly pinned pure reducer outside storage transactions, resolves control
11//! branches in stable node order, and produces the existing atomic
12//! [`CheckpointBarrier`] intent.
13
14use 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/// Exact executable reducer revision required by a compiled graph.
35#[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    /// Constructs an immutable reducer reference.
44    #[must_use]
45    pub const fn new(identity: CapabilityIdentity, definition_digest: Digest) -> Self {
46        Self {
47            identity,
48            definition_digest,
49        }
50    }
51
52    /// Returns the owner-qualified reducer identity.
53    #[must_use]
54    pub const fn identity(&self) -> &CapabilityIdentity {
55        &self.identity
56    }
57
58    /// Returns the checksum of the exact reducer implementation contract.
59    #[must_use]
60    pub const fn definition_digest(&self) -> Digest {
61        self.definition_digest
62    }
63}
64
65/// Hard execution ceilings embedded in one graph definition.
66#[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    /// Constructs positive limits below framework and storage ceilings.
75    ///
76    /// # Errors
77    ///
78    /// Returns [`GraphExecutionLimitsError`] for a zero superstep or
79    /// parallelism limit, or for parallelism above [`ReadyNodes::MAX_LEN`].
80    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    /// Returns the maximum number of barriers that may execute.
105    #[must_use]
106    pub const fn maximum_supersteps(self) -> Superstep {
107        self.maximum_supersteps
108    }
109
110    /// Returns the maximum number of ready nodes in one superstep.
111    #[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/// Invalid compiled graph execution limits.
135#[derive(Clone, Debug, Eq, Error, PartialEq)]
136#[non_exhaustive]
137pub enum GraphExecutionLimitsError {
138    /// A graph could execute no barrier.
139    #[error("graph maximum supersteps must be positive")]
140    ZeroSupersteps,
141    /// A graph could schedule no entry or successor node.
142    #[error("graph maximum parallelism must be positive")]
143    ZeroParallelism,
144    /// A graph limit exceeded the immutable ready-set ceiling.
145    #[error("graph maximum parallelism is {actual}; framework maximum is {maximum}")]
146    ParallelismAboveFrameworkMaximum {
147        /// Immutable framework ceiling.
148        maximum: usize,
149        /// Rejected graph limit.
150        actual: usize,
151    },
152}
153
154/// One declared conditional branch and its non-empty successor set.
155#[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    /// Constructs one declared route.
164    ///
165    /// # Errors
166    ///
167    /// Returns [`GraphRouteError::EmptySuccessors`] when selecting the route
168    /// would silently dead-end without a terminal result.
169    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    /// Returns the stable route identity.
180    #[must_use]
181    pub const fn route_id(&self) -> &RouteId {
182        &self.route_id
183    }
184
185    /// Returns the route's deterministic successor set.
186    #[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/// Invalid conditional graph route.
210#[derive(Clone, Debug, Eq, Error, PartialEq)]
211#[non_exhaustive]
212pub enum GraphRouteError {
213    /// A non-terminal branch contained no successor.
214    #[error("graph route successors must not be empty")]
215    EmptySuccessors,
216}
217
218/// Canonically ordered, duplicate-free route collection for one node.
219#[derive(Clone, Debug, Eq, PartialEq)]
220pub struct GraphRoutes(Box<[GraphRoute]>);
221
222impl GraphRoutes {
223    /// Hard maximum number of routes declared by one node.
224    pub const MAX_LEN: usize = 256;
225
226    /// Constructs a stable route collection.
227    ///
228    /// # Errors
229    ///
230    /// Returns [`GraphRoutesError`] for duplicate identities or an oversized
231    /// collection.
232    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    /// Returns an empty route collection.
257    #[must_use]
258    pub fn empty() -> Self {
259        Self(Box::new([]))
260    }
261
262    /// Returns the number of declared routes.
263    #[must_use]
264    pub const fn len(&self) -> usize {
265        self.0.len()
266    }
267
268    /// Returns whether no conditional route is declared.
269    #[must_use]
270    pub const fn is_empty(&self) -> bool {
271        self.0.is_empty()
272    }
273
274    /// Iterates routes in stable identity order.
275    pub fn iter(&self) -> impl ExactSizeIterator<Item = &GraphRoute> {
276        self.0.iter()
277    }
278
279    /// Resolves one exact route identity.
280    #[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/// Invalid route collection for one node.
334#[derive(Clone, Debug, Eq, Error, PartialEq)]
335#[non_exhaustive]
336pub enum GraphRoutesError {
337    /// The per-node route ceiling was exceeded.
338    #[error("graph node contains {actual} routes; maximum is {maximum}")]
339    TooMany {
340        /// Immutable per-node ceiling.
341        maximum: usize,
342        /// First count beyond the ceiling.
343        actual: usize,
344    },
345    /// One route identity was repeated by the same node.
346    #[error("graph node contains duplicate route {route_id}")]
347    Duplicate {
348        /// Repeated identity.
349        route_id: RouteId,
350    },
351}
352
353/// Declarative control surface for one stable graph node.
354#[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    /// Constructs one compiled node control declaration.
368    ///
369    /// `continue_to` is selected by [`NodeControl::Continue`], `routes` by
370    /// [`NodeControl::Route`], and `wait_to` is the ready set retained while a
371    /// [`NodeControl::Wait`] suspends the run. `terminal` authorizes one exact
372    /// terminal output. Every non-terminal successor set must be non-empty.
373    ///
374    /// # Errors
375    ///
376    /// Returns [`GraphNodeError`] when the node exposes no control outcome or
377    /// declares an empty continuation/wait successor set.
378    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    /// Returns the stable node identity.
404    #[must_use]
405    pub const fn node_id(&self) -> &NodeId {
406        &self.node_id
407    }
408
409    /// Returns successors selected by an unconditional continuation.
410    #[must_use]
411    pub const fn continue_to(&self) -> Option<&ReadyNodes> {
412        self.continue_to.as_ref()
413    }
414
415    /// Returns declared conditional routes.
416    #[must_use]
417    pub const fn routes(&self) -> &GraphRoutes {
418        &self.routes
419    }
420
421    /// Returns successors retained by a durable wait outcome.
422    #[must_use]
423    pub const fn wait_to(&self) -> Option<&ReadyNodes> {
424        self.wait_to.as_ref()
425    }
426
427    /// Returns whether this node may complete the graph.
428    #[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/// Invalid local control shape for one graph node.
473#[derive(Clone, Debug, Eq, Error, PartialEq)]
474#[non_exhaustive]
475pub enum GraphNodeError {
476    /// No result control value could be accepted.
477    #[error("graph node must declare at least one control outcome")]
478    NoControlOutcome,
479    /// `continue` would silently dead-end.
480    #[error("graph continue successors must not be empty")]
481    EmptyContinueSuccessors,
482    /// A resolved wait would have no declared continuation.
483    #[error("graph wait successors must not be empty")]
484    EmptyWaitSuccessors,
485}
486
487/// Canonical, schema-pinned declarative graph compiled before admission.
488#[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    /// Hard node ceiling for one compiled graph.
508    pub const MAX_NODES: usize = ReadyNodes::MAX_LEN;
509    /// Hard aggregate route ceiling for one compiled graph.
510    pub const MAX_ROUTES: usize = Self::MAX_NODES * GraphRoutes::MAX_LEN;
511    /// Hard canonical descriptor byte ceiling.
512    pub const MAX_DEFINITION_BYTES: usize = 2 * MEBIBYTE;
513
514    /// Compiles and checksums one trusted declarative graph descriptor.
515    ///
516    /// # Errors
517    ///
518    /// Rejects duplicate/missing identities, unreachable nodes, paths that
519    /// cannot reach a wait or terminal boundary, limit violations, and
520    /// canonical descriptors above the hard byte ceiling.
521    #[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    /// Pins finite child delegation declarations into a new graph definition.
603    ///
604    /// The resulting reference differs from this graph's old reference. Bind
605    /// executors only after this call. Graphs without a policy retain their
606    /// exact previous canonical encoding and delegate nothing. Target registry
607    /// closure and live admission checks remain separate requirements.
608    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    /// Returns the exact delegation policy, or no authority to select children.
625    #[must_use]
626    pub const fn child_runs(&self) -> Option<&GraphChildRunPolicy> {
627        self.child_runs.as_ref()
628    }
629
630    /// Returns the owner-qualified graph identity.
631    #[must_use]
632    pub const fn identity(&self) -> &CapabilityIdentity {
633        &self.identity
634    }
635
636    /// Returns the admitted graph input schema.
637    #[must_use]
638    pub const fn input_schema(&self) -> &SchemaReference {
639        &self.input_schema
640    }
641
642    /// Returns the immutable checkpoint state schema.
643    #[must_use]
644    pub const fn state_schema(&self) -> &SchemaReference {
645        &self.state_schema
646    }
647
648    /// Returns the schema every node update must use.
649    #[must_use]
650    pub const fn update_schema(&self) -> &SchemaReference {
651        &self.update_schema
652    }
653
654    /// Returns the successful terminal output schema.
655    #[must_use]
656    pub const fn output_schema(&self) -> &SchemaReference {
657        &self.output_schema
658    }
659
660    /// Returns the exact executable reducer revision.
661    #[must_use]
662    pub const fn reducer(&self) -> &GraphReducerReference {
663        &self.reducer
664    }
665
666    /// Returns the deterministic initial ready set.
667    #[must_use]
668    pub const fn entry_nodes(&self) -> &ReadyNodes {
669        &self.entry_nodes
670    }
671
672    /// Returns compiled nodes in stable identity order.
673    #[must_use]
674    pub const fn nodes(&self) -> &[GraphNode] {
675        &self.nodes
676    }
677
678    /// Returns immutable graph execution limits.
679    #[must_use]
680    pub const fn limits(&self) -> GraphExecutionLimits {
681        self.limits
682    }
683
684    /// Returns SHA-256 over the exact canonical definition bytes.
685    #[must_use]
686    pub const fn definition_digest(&self) -> Digest {
687        self.definition_digest
688    }
689
690    /// Returns the compact reference stored by every checkpoint.
691    #[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    /// Returns exact canonical descriptor bytes excluding the redundant digest.
701    ///
702    /// # Errors
703    ///
704    /// Fails closed if the canonical serializer rejects the closed descriptor.
705    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    /// Looks up one compiled node by exact identity.
722    #[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    /// Plans one complete deterministic barrier outside a storage transaction.
731    ///
732    /// # Errors
733    ///
734    /// Rejects graph/checkpoint drift, incomplete or substituted results,
735    /// schema failures, unpinned reducers, invalid controls, step/parallelism
736    /// limits, reducer panic/failure, and successor/barrier construction errors.
737    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/// Invalid canonical graph definition.
993#[derive(Clone, Debug, Eq, Error, PartialEq)]
994#[non_exhaustive]
995pub enum GraphCompileError {
996    /// No executable node was declared.
997    #[error("compiled graph must contain at least one node")]
998    EmptyNodes,
999    /// The graph exceeded the immutable node ceiling.
1000    #[error("compiled graph contains {actual} nodes; maximum is {maximum}")]
1001    TooManyNodes {
1002        /// Immutable ceiling.
1003        maximum: usize,
1004        /// First count beyond the ceiling.
1005        actual: usize,
1006    },
1007    /// A stable node identity was repeated.
1008    #[error("compiled graph contains duplicate node {node_id}")]
1009    DuplicateNode {
1010        /// Repeated node identity.
1011        node_id: NodeId,
1012    },
1013    /// No initial runnable node was declared.
1014    #[error("compiled graph must contain at least one entry node")]
1015    EmptyEntryNodes,
1016    /// An entry identity was absent from the node table.
1017    #[error("compiled graph entry node {node_id} does not exist")]
1018    MissingEntryNode {
1019        /// Missing identity.
1020        node_id: NodeId,
1021    },
1022    /// A control branch referenced an absent node.
1023    #[error("compiled graph node {from_node} references missing successor {target}")]
1024    MissingSuccessorNode {
1025        /// Declaring node.
1026        from_node: NodeId,
1027        /// Missing target.
1028        target: NodeId,
1029    },
1030    /// A route identity was reused by two nodes.
1031    #[error("compiled graph route {route_id} is declared by both {first_node} and {second_node}")]
1032    DuplicateRoute {
1033        /// Reused route identity.
1034        route_id: RouteId,
1035        /// First declaring node.
1036        first_node: NodeId,
1037        /// Second declaring node.
1038        second_node: NodeId,
1039    },
1040    /// The graph exceeded its aggregate route ceiling.
1041    #[error("compiled graph contains {actual} routes; maximum is {maximum}")]
1042    TooManyRoutes {
1043        /// Immutable ceiling.
1044        maximum: usize,
1045        /// Rejected count.
1046        actual: usize,
1047    },
1048    /// A declared ready set exceeded graph-specific parallelism.
1049    #[error("compiled graph ready set contains {actual} nodes; graph maximum is {maximum}")]
1050    ParallelismExceeded {
1051        /// Declaring node, or `None` for the entry set.
1052        node_id: Option<NodeId>,
1053        /// Graph-specific ceiling.
1054        maximum: usize,
1055        /// Rejected count.
1056        actual: usize,
1057    },
1058    /// A node could never be activated from any entry.
1059    #[error("compiled graph node {node_id} is unreachable from every entry")]
1060    UnreachableNode {
1061        /// Unreachable identity.
1062        node_id: NodeId,
1063    },
1064    /// A node could not reach a wait or terminal boundary.
1065    #[error("compiled graph node {node_id} cannot reach a wait or terminal boundary")]
1066    NoBoundaryPath {
1067        /// Non-terminating identity.
1068        node_id: NodeId,
1069    },
1070    /// The canonical descriptor exceeded its resource ceiling.
1071    #[error("compiled graph descriptor is {actual} bytes; maximum is {maximum}")]
1072    DefinitionTooLarge {
1073        /// Immutable byte ceiling.
1074        maximum: usize,
1075        /// Observed canonical bytes.
1076        actual: usize,
1077    },
1078    /// Canonical JSON serialization unexpectedly failed.
1079    #[error("compiled graph canonical serialization failed")]
1080    CanonicalSerialization,
1081    /// Persisted definition checksum did not match the descriptor.
1082    #[error("compiled graph definition digest does not match its fields")]
1083    DigestMismatch,
1084    /// Delegation declarations violate their closed policy or parent node set.
1085    #[error(transparent)]
1086    ChildPolicy(#[from] ChildRunPolicyError),
1087}
1088
1089/// Public-safe reason a schema registry could not validate a value.
1090///
1091/// Registries retain detailed diagnostics in protected telemetry. The graph
1092/// planner intentionally carries only this closed classification so schema or
1093/// user data cannot leak through errors, logs, or protocol adapters.
1094#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
1095#[non_exhaustive]
1096pub enum GraphSchemaValidationError {
1097    /// The value did not satisfy the exact pinned schema.
1098    #[error("value was rejected by the pinned schema")]
1099    Rejected,
1100    /// The exact schema implementation was unavailable.
1101    #[error("pinned schema was unavailable")]
1102    Unavailable,
1103}
1104
1105/// Local registry capable of validating one exact schema-pinned JSON value.
1106///
1107/// Implementations must resolve only pre-registered canonical schema bytes and
1108/// verify [`SchemaReference::digest`] before validation. They must not fetch a
1109/// schema from its URI while a run is executing.
1110pub trait GraphSchemaValidator: Send + Sync {
1111    /// Validates `value` against the exact immutable schema reference.
1112    fn validate(
1113        &self,
1114        schema: &SchemaReference,
1115        value: &BoundedJson,
1116    ) -> Result<(), GraphSchemaValidationError>;
1117}
1118
1119/// Public-safe failure returned by one pure graph reducer.
1120#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
1121#[non_exhaustive]
1122pub enum GraphReducerError {
1123    /// The ordered state/update combination was semantically invalid.
1124    #[error("graph reducer rejected the ordered update batch")]
1125    Rejected,
1126    /// The pinned implementation could not execute on this worker.
1127    #[error("pinned graph reducer was unavailable")]
1128    Unavailable,
1129    /// The reducer could not satisfy an enforced resource bound.
1130    #[error("graph reducer exceeded an enforced resource limit")]
1131    ResourceLimit,
1132}
1133
1134/// One immutable update presented to a reducer in canonical node order.
1135#[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    /// Returns the stable logical node identity controlling reduction order.
1147    #[must_use]
1148    pub const fn node_id(self) -> &'a NodeId {
1149        self.node_id
1150    }
1151
1152    /// Returns the exact schema-pinned update.
1153    #[must_use]
1154    pub const fn update(self) -> &'a NodeStateUpdate {
1155        self.update
1156    }
1157}
1158
1159/// Exactly pinned pure reducer implementation used by graph planning.
1160///
1161/// The runtime invokes this trait only after all external model/tool work has
1162/// committed and never while a storage transaction is open. Implementations
1163/// must be deterministic, side-effect free, bounded, and must treat `updates`
1164/// in the supplied order. Reducer conformance tests remain a release gate;
1165/// recovery re-executes the reducer and compares the resulting barrier intent.
1166pub trait GraphReducer: Send + Sync {
1167    /// Returns the immutable implementation identity loaded by the registry.
1168    fn reference(&self) -> &GraphReducerReference;
1169
1170    /// Reduces an ordered update batch into candidate successor state.
1171    fn reduce(
1172        &self,
1173        state: &BoundedJson,
1174        updates: &[GraphReducerInput<'_>],
1175    ) -> Result<BoundedJson, GraphReducerError>;
1176}
1177
1178/// Semantic lifecycle outcome selected by one complete graph barrier.
1179#[derive(Clone, Debug, Eq, PartialEq)]
1180#[non_exhaustive]
1181pub enum GraphBarrierDisposition {
1182    /// Commit the successor and keep ordinary active execution.
1183    Continue,
1184    /// Commit the successor and atomically suspend on these conditions.
1185    Wait {
1186        /// Complete stable condition batch gathered from node results.
1187        waits: NodeWaits,
1188    },
1189    /// Commit the terminal successor and complete with this validated output.
1190    Terminal {
1191        /// Exact graph output to convert into the admitted agent result.
1192        output: NodeTerminalOutput,
1193    },
1194}
1195
1196impl GraphBarrierDisposition {
1197    /// Returns the wait batch for a suspending barrier.
1198    #[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    /// Returns the terminal output for a successful terminal barrier.
1207    #[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/// Complete deterministic plan ready for an existing atomic barrier API.
1217#[derive(Clone, Debug, Eq, PartialEq)]
1218pub struct GraphBarrierPlan {
1219    barrier: CheckpointBarrier,
1220    disposition: GraphBarrierDisposition,
1221}
1222
1223impl GraphBarrierPlan {
1224    /// Returns the integrity-bound atomic checkpoint barrier intent.
1225    #[must_use]
1226    pub const fn barrier(&self) -> &CheckpointBarrier {
1227        &self.barrier
1228    }
1229
1230    /// Returns the lifecycle action selected by complete node controls.
1231    #[must_use]
1232    pub const fn disposition(&self) -> &GraphBarrierDisposition {
1233        &self.disposition
1234    }
1235
1236    /// Consumes the plan into its storage barrier and lifecycle disposition.
1237    #[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/// Closed value class used in public-safe graph validation failures.
1570#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1571#[non_exhaustive]
1572pub enum GraphValueKind {
1573    /// Immutable base checkpoint state.
1574    BaseState,
1575    /// One node's typed update.
1576    NodeUpdate,
1577    /// One graph terminal output.
1578    TerminalOutput,
1579    /// Reducer-produced successor state.
1580    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/// Failure to derive one deterministic, storage-ready barrier plan.
1595#[derive(Clone, Debug, Eq, Error, PartialEq)]
1596#[non_exhaustive]
1597pub enum GraphBarrierPlanError {
1598    /// The checkpoint pinned another graph definition or state schema.
1599    #[error("checkpoint graph reference does not match the compiled graph")]
1600    GraphReferenceMismatch,
1601    /// Superstep zero did not contain the exact compiled entry set.
1602    #[error("initial checkpoint ready set does not match compiled graph entries")]
1603    InitialReadySetMismatch,
1604    /// The next barrier would exceed the graph step ceiling.
1605    #[error("graph superstep limit {maximum} was reached at checkpoint {actual}")]
1606    SuperstepLimitReached {
1607        /// Compiled ceiling.
1608        maximum: Superstep,
1609        /// Current checkpoint position.
1610        actual: Superstep,
1611    },
1612    /// The current checkpoint already exceeded graph parallelism.
1613    #[error("base checkpoint has {actual} ready nodes; graph maximum is {maximum}")]
1614    BaseParallelismExceeded {
1615        /// Compiled ceiling.
1616        maximum: usize,
1617        /// Rejected count.
1618        actual: usize,
1619    },
1620    /// A checkpoint referenced a node absent from the compiled graph.
1621    #[error("base checkpoint contains unknown ready node {node_id}")]
1622    UnknownReadyNode {
1623        /// Unknown identity.
1624        node_id: NodeId,
1625    },
1626    /// The reducer implementation did not match its pinned reference.
1627    #[error("loaded reducer does not match the compiled graph reference")]
1628    ReducerReferenceMismatch,
1629    /// The complete result count differed from the ready set.
1630    #[error("barrier contains {actual} results; expected {expected}")]
1631    ResultCountMismatch {
1632        /// Exact ready-node count.
1633        expected: usize,
1634        /// Supplied result count.
1635        actual: usize,
1636    },
1637    /// One ready node appeared more than once.
1638    #[error("barrier contains duplicate result node {node_id}")]
1639    DuplicateResultNode {
1640        /// Duplicated identity.
1641        node_id: NodeId,
1642    },
1643    /// One expected ready node had no result.
1644    #[error("barrier is missing result node {node_id}")]
1645    MissingResultNode {
1646        /// Missing identity.
1647        node_id: NodeId,
1648    },
1649    /// A result belonged to another immutable checkpoint.
1650    #[error("result for node {node_id} does not belong to the base checkpoint")]
1651    ResultBaseMismatch {
1652        /// Rejected result node.
1653        node_id: NodeId,
1654    },
1655    /// Root graph planning received a nested activation.
1656    #[error("result for node {node_id} belongs to a non-root graph namespace")]
1657    NonRootActivation {
1658        /// Rejected result node.
1659        node_id: NodeId,
1660    },
1661    /// A result's logical input did not match deterministic activation derivation.
1662    #[error("result activation for node {node_id} does not match the base checkpoint")]
1663    ActivationMismatch {
1664        /// Rejected result node.
1665        node_id: NodeId,
1666    },
1667    /// One update substituted another schema.
1668    #[error("node {node_id} update schema does not match the compiled graph")]
1669    UpdateSchemaMismatch {
1670        /// Rejected result node.
1671        node_id: NodeId,
1672    },
1673    /// One terminal output substituted another schema.
1674    #[error("node {node_id} terminal output schema does not match the compiled graph")]
1675    TerminalOutputSchemaMismatch {
1676        /// Rejected result node.
1677        node_id: NodeId,
1678    },
1679    /// The exact schema implementation rejected or could not validate a value.
1680    #[error("graph {kind} schema validation failed")]
1681    SchemaValidation {
1682        /// Closed value class.
1683        kind: GraphValueKind,
1684        /// Producing node for update/output values.
1685        node_id: Option<NodeId>,
1686        /// Public-safe registry classification.
1687        #[source]
1688        source: GraphSchemaValidationError,
1689    },
1690    /// A schema adapter panicked instead of returning a closed failure.
1691    #[error("graph {kind} schema validator panicked")]
1692    SchemaValidatorPanicked {
1693        /// Closed value class.
1694        kind: GraphValueKind,
1695        /// Producing node for update/output values.
1696        node_id: Option<NodeId>,
1697    },
1698    /// A result selected a control kind absent from its node declaration.
1699    #[error("node {node_id} selected undeclared {control:?} control")]
1700    UndeclaredControl {
1701        /// Producing node.
1702        node_id: NodeId,
1703        /// Rejected control kind.
1704        control: NodeControlKind,
1705    },
1706    /// A result selected an undeclared conditional route.
1707    #[error("node {node_id} selected undeclared route {route_id}")]
1708    UndeclaredRoute {
1709        /// Producing node.
1710        node_id: NodeId,
1711        /// Rejected route.
1712        route_id: RouteId,
1713    },
1714    /// Terminal completion was mixed with another active result/control.
1715    #[error("terminal graph result must be the only activation in its barrier")]
1716    TerminalNotExclusive,
1717    /// An ordinary advancing barrier resolved no successor.
1718    #[error("non-terminal graph barrier must produce at least one successor")]
1719    AdvancingBarrierWithoutSuccessor,
1720    /// Combined branches exceeded graph parallelism.
1721    #[error("successor contains {actual} ready nodes; graph maximum is {maximum}")]
1722    SuccessorParallelismExceeded {
1723        /// Compiled ceiling.
1724        maximum: usize,
1725        /// Rejected combined count.
1726        actual: usize,
1727    },
1728    /// Parallel waits could not form one atomic registration batch.
1729    #[error("graph wait controls do not form one valid batch: {source}")]
1730    InvalidWaitBatch {
1731        /// Exact wait collection failure.
1732        #[source]
1733        source: NodeWaitsError,
1734    },
1735    /// The pure reducer returned a closed failure.
1736    #[error("graph reducer failed: {source}")]
1737    ReducerFailed {
1738        /// Public-safe reducer classification.
1739        #[source]
1740        source: GraphReducerError,
1741    },
1742    /// Reducer code panicked instead of returning a closed failure.
1743    #[error("graph reducer panicked")]
1744    ReducerPanicked,
1745    /// Reducer output could not become integrity-bound checkpoint state.
1746    #[error("reduced graph state is invalid: {source}")]
1747    InvalidReducedState {
1748        /// Exact state construction failure.
1749        #[source]
1750        source: CheckpointStateError,
1751    },
1752    /// The derived successor violated checkpoint invariants.
1753    #[error("derived graph successor is invalid: {source}")]
1754    InvalidSuccessor {
1755        /// Exact checkpoint-write failure.
1756        #[source]
1757        source: CheckpointWriteError,
1758    },
1759    /// The final barrier violated complete-set or integrity invariants.
1760    #[error("derived graph barrier is invalid: {source}")]
1761    InvalidBarrier {
1762        /// Exact barrier failure.
1763        #[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}